Number Theory: An Introduction to Mathematics

1 Minkowski’s Lattice Point Theorem 329

The continued fraction algorithm enables one to find rational approximations to
irrational numbers. The subject ofDiophantine approximationis concerned with the
more general problem of solving inequalities in integers. From Proposition 3 we can
immediately obtain a result in this area due to Dirichlet (1842):

Proposition 4Let A=(αjk)be an n×m real matrix and let t> 1 be real. Then there
exist integers q 1 ,...,qm,p 1 ,...,pn, with 0 <max(|q 1 |,...,|qm|)<tn/m, such that

∣

∣

∣

∣

∑m

k= 1

αjkqk−pj

∣

∣

∣

∣≤^1 /t (^1 ≤j≤n).

Proof Since the matrix
(
t−n/mIm 0
tA tIn

)

has determinant 1, it follows from Proposition 3 that there exists a nonzero vector

x=

(

q

−p

)

∈Zn+m

such that

|qk|<tn/m(k= 1 ,...,m),

∣

∣

∣

∣

∑m

k= 1

αjkqk−pj

∣

∣

∣

∣≤^1 /t(j=^1 ,...,n).

Sinceq=Owould imply|pj|<1foralljand hencep=O, which contradicts
x=O,wemusthavemaxk|qk|>0.

Corollary 5Let A=(αjk)be an n×m real matrix such that Az∈/Znfor any nonzero
vector z∈Zm. Then there exist infinitely many(m+n)-tuples q 1 ,...,qm,p 1 ,...,pn
of integers with greatest common divisor 1 and with arbitrarily large values of

‖q‖=max(|q 1 |,...,|qm|)

such that
∣
∣
∣
∣

∑m

k= 1

αjkqk−pj

∣

∣

∣

∣<‖q‖

−m/n ( 1 ≤j≤n).

Proof Letq 1 ,...,qm,p 1 ,...,pnbe integers satisfying the conclusions of Proposi-
tion 4 for somet >1. Evidently we may assume thatq 1 ,...,qm,p 1 ,...,pnhave
no common divisor greater than 1. For given∑ q 1 ,...,qm,letδjbe the distance of
m
k= 1 αjkqkfrom the nearest integer and putδ=maxδj(^1 ≤j≤n). By hypothesis
0 <δ<1, and by construction

δ≤ 1 /t<‖q‖−m/n.