, , ,

Dirichlet's theorem on diophantine approximation tells us that we can approximate any real number by rational numbers quite well, namely:

Theorem 1. For any real

θ

and any positive integer

N

, there exist integers

a

and

q

, with

1 \leq q \leq N

, such that

| θ - \frac{a}{q} | < \frac{1}{q N} .

Moreover, the bound

1 / (q N)

is best possible, apart from the constant factor. To see this, it suffices to consider the golden ratio

θ = (\sqrt{5} - 1) / 2

(see [3,§11.8] ). During his work in [1] , the first author accidentally stumbled across the following analogous question:

Question 1. For any real

θ

and any positive integer

N

, give an upper bound for

{min}_{a_{1}, a_{2}, q_{1}, q_{2} \in Z 1 \leq q_{1}, q_{2} \leq N} | \frac{a_{1}}{q_{1}} + \frac{a_{2}}{q_{2}} - θ | .

With the golden ratio in mind, we know that the upper bound can be no better than

O (1 / (q_{1} q_{2} N^{2}))

. So, what is the best possible upper bound?

More generally,

Question 2. Let

k

be a positive integer. For any real

θ

and any positive integer

N

, give an upper bound for

{min}_{a_{1}, . . ., a_{k}, q_{1}, . . ., q_{k} \in Z 1 \leq q_{1}, . . ., q_{k} \leq N} | \frac{a_{1}}{q_{1}} + \cdot \cdot \cdot + \frac{a_{k}}{q_{k}} - θ | .

To these, we have the following result:

Theorem 2. Let

k

be a positive integer. For any real

θ

and any positive integer

N

, there exist integers

a_{1}, . . ., a_{k}

q_{1}, . . ., q_{k}

, with

1 \leq q_{1}, . . . q_{k} \leq N

, such that

| \frac{a_{1}}{q_{1}} + \cdot \cdot \cdot + \frac{a_{k}}{q_{k}} - θ | ≪ N^{- k} .

The bound

N^{- k}

is best possible in the sense that, for some

θ

, the minimum in Question 2 can be as large as

N^{- k}

. For example, if one considers

θ = 1 / (2 N^{k})

| \frac{a_{1}}{q_{1}} + \dots + \frac{a_{k}}{q_{k}} - θ | \geq \frac{1}{2 N^{k}}

for any choice of

a_{1}, . . ., a_{k}, q_{1}, . . ., q_{k}

, with

1 \leq q_{1}, . . ., q_{k} \leq N

. However, one expects such pathological examples to be relatively rare, and so one may wonder if it is possible to obtain a sharper upper bound involving the

q_{i}

's. For example, is it possible to replace

N^{- k}

(q_{1} \dots q_{k})^{- 1} N^{- k}

in Theorem 2 ? We shall briefly address this issue in the last section.

2 Proof of Theorem 2

Lemma. Suppose that

k \geq 1

is an integer. There is a number

x_{0} (k) \geq 1

such that

\sum_{1 \leq q_{1}, . . ., q_{k} \leq x}^{*} q_{1} \dots q_{k} ≫ x^{2 k},

whenever

x \geq x_{0} (k)

. Here,

\sum^{*}

denotes a summation over the

k

-tuples

q_{1}, . . ., q_{k}

such that

(q_{i}, q_{j}) = 1

whenever

1 \leq i < j \leq k

Proof. It suffices to show that

\begin{matrix} \sum_{n \leq x (n, m) = 1} φ (n)^{α} n^{1 - α} ≫ x^{2} φ (m) m^{- 1}, \end{matrix}

(1)

whenever

0 \leq α \leq k - 1

1 \leq m \leq x^{k - 1}

, and

x \geq x_{0} (k)

. The conclusion of the lemma will then follow by successive applications of 1 with

α = 0, 1, . . ., k - 1

to the summations over

q_{k}, q_{k - 1}, . . ., q_{1}

We now proceed to establish 1 . We start by showing that

\begin{matrix} \sum_{n \leq x (n, m) = 1} {(\frac{n}{φ (n)})}^{α} ≪ x φ (m) m^{- 1} . \end{matrix}

(2)

Define the multiplicative functions

f (n) = {\begin{matrix} {(n / φ (n))}^{α} & if (n, m) = 1, \\ 0 & if (n, m) > 1, \end{matrix} g (n) = \sum_{d | n} f (d) μ (n / d) .

Then

g (n) \geq 0

, and

\begin{matrix} \sum_{n \leq x} f (n) & = \sum_{n \leq x} \sum_{d | n} g (d) = \sum_{d \leq x} g (d) ⌊ \frac{x}{d} ⌋ \leq x \sum_{d \leq x} g (d) d^{- 1} \end{matrix}

\begin{matrix} \leq x \prod_{p \leq x} \sum_{ν = 0}^{\infty} g (p^{ν}) p^{- ν} = x \prod_{p \leq x} (1 - p^{- 1}) \sum_{ν = 0}^{\infty} f (p^{ν}) p^{- ν} \end{matrix}

\begin{matrix} \leq x \prod_{p | m p \leq x} (1 - p^{- 1}) \prod_{p} (1 + \frac{p^{α} - (p - 1)^{α}}{p (p - 1)^{α}}) \end{matrix}

\begin{matrix} \leq x \prod_{p | m} (1 - p^{- 1}) \prod_{p} (1 + \frac{p^{α} - (p - 1)^{α}}{p (p - 1)^{α}}) + O (1) . \end{matrix}

\begin{matrix}  \end{matrix}

The last inequality follows on noting that

m

has at most

k - 2

prime divisors

p > x

, and hence,

\prod_{p | m p > x} (1 - p^{- 1}) = 1 + O (x^{- 1}) .

This proves 2 . On the other hand, when

α = 0

, we have

\sum_{n \leq x (n, m) = 1} n = \sum_{d | m} μ (d) d \sum_{k \leq x / d} k = \frac{φ (m)}{2 m} x^{2} + O (x τ (m)),

whence

\begin{matrix} \sum_{n \leq x (n, m) = 1} n^{1 / 2} \geq x^{- 1 / 2} \sum_{n \leq x (n, m) = 1} n ≫ x^{3 / 2} φ (m) m^{- 1} . \end{matrix}

(3)

Finally, 1 follows from 2 , 3 , and Cauchy's inequality:

\sum_{n \leq x (n, m) = 1} φ (n)^{α} n^{1 - α} \geq {\sum_{n \leq x (n, m) = 1} n^{1 / 2}}^{2} {\sum_{n \leq x (n, m) = 1} {(\frac{n}{φ (n)})}^{α}}^{- 1} ≫ x^{2} φ (m) m^{- 1} .

□

Proof of Theorem 2 . For

0 < Δ < 1 / 2

, define

t (x) = max (1 - | x | / Δ, 0), g (x) = \sum_{n = - \infty}^{\infty} t (x - n) .

The function

g

has a Fourier expansion

g (x) = \sum_{h = - \infty}^{\infty} {\hat{g}}_{h} e (h x), {\hat{g}}_{h} = Δ {(\frac{sin π Δ h}{π Δ h})}^{2} .

We consider the sum

\begin{matrix} S = \sum_{1 \leq q_{1}, . . ., q_{k} \leq N}^{*} \sum_{a_{1} = 1}^{q_{1}} . . . \sum_{a_{k} = 1}^{q_{k}} g (\frac{a_{1}}{q_{1}} + \cdot \cdot \cdot + \frac{a_{k}}{q_{k}} - θ), \end{matrix}

(4)

where

\sum^{*}

has the same meaning as in the Lemma. Putting in the Fourier expansion for

g

, we get

\begin{matrix} S = & \sum_{1 \leq q_{1}, . . ., q_{k} \leq N}^{*} \sum_{a_{1} = 1}^{q_{1}} . . . \sum_{a_{k} = 1}^{q_{k}} \sum_{h = - \infty}^{\infty} {\hat{g}}_{h} e (h (\frac{a_{1}}{q_{1}} + \cdot \cdot \cdot + \frac{a_{k}}{q_{k}} - θ)) \end{matrix}

(5)

\begin{matrix} = & \sum_{1 \leq q_{1}, . . ., q_{k} \leq N}^{*} \sum_{h = - \infty}^{\infty} {\hat{g}}_{h} e (- h θ) \sum_{a_{1} = 1}^{q_{1}} e (h a_{1} / q_{1}) . . . \sum_{a_{k} = 1}^{q_{k}} e (h a_{k} / q_{k}) \end{matrix}

\begin{matrix} = & \sum_{1 \leq q_{1}, . . ., q_{k} \leq N}^{*} q_{1} \dots q_{k} \sum_{h = - \infty q_{1} \dots q_{k} | h}^{\infty} {\hat{g}}_{h} e (- h θ), \end{matrix}

\begin{matrix}  \end{matrix}

\sum_{a = 1}^{q} e (h a / q) = {\begin{matrix} q & if q | h, \\ 0 & otherwise . \end{matrix}

m

is a positive integer and

Δ \leq m^{- 1}

, we have

\begin{matrix} \begin{matrix} \sum_{h \neq 0} | {\hat{g}}_{m h} | & \leq 2 {\sum_{h = 1}^{H} Δ + \frac{1}{Δ m^{2}} \sum_{h = H + 1}^{\infty} h^{- 2}} & \leq 2 (H Δ + \frac{1}{H Δ m^{2}}) \leq 6 m^{- 1}, \end{matrix} \end{matrix}

(6)

where

H = ⌈ (Δ m)^{- 1} ⌉

; whereas if

Δ > m^{- 1}

, we have

\begin{matrix} \sum_{h \neq 0} | {\hat{g}}_{m h} | \leq \frac{2 ζ (2)}{Δ m^{2}} \leq 4 m^{- 1} . \end{matrix}

(7)

Putting 6 and 7 (with

m = q_{1} \dots q_{k}

) into 5 , we obtain

S = Δ \sum_{1 \leq q_{1}, . . ., q_{k} \leq N}^{*} q_{1} \dots q_{k} + O (N^{k}),

the

O

-implied constant being absolute (in fact, it is

6

). Therefore, upon choosing

Δ = c N^{- k}

with a sufficiently large

c > 0

, it follows from the Lemma that

S > 0

. Hence, by 4 ,

g (\frac{a_{1}}{q_{1}} + \cdot \cdot \cdot + \frac{a_{k}}{q_{k}} - θ) > 0

for some integers

a_{1}, . . ., a_{k}, q_{1}, . . ., q_{k}

with

1 \leq q_{1}, . . ., q_{k} \leq N

. Then, by the definition of

g

| \frac{a_{1}}{q_{1}} + \cdot \cdot \cdot + \frac{a_{k}}{q_{k}} - n - θ | \leq c N^{- k}

for some integer

n

. This establishes the theorem. □

3 Closing remarks

We conclude this note with a short discussion of possible improvement on the bound

N^{- k}

in Theorem 2 . For example, is it possible to replace

N^{- k}

(q_{1} \dots q_{k})^{- 1} N^{- k}

? While such a result may appear to be the right generalization of Dirichlet's theorem, it is not true in general. Indeed, suppose that for any real

θ

, there exist integers

a_{1}, . . ., a_{k}, q_{1}, . . ., q_{k}

, with

1 \leq q_{1}, . . ., q_{k} \leq N

, such that

\begin{matrix} | \frac{a_{1}}{q_{1}} + \dots + \frac{a_{k}}{q_{k}} - θ | \leq \frac{C}{q_{1} \dots q_{k} N^{k}} . \end{matrix}

(8)

Then

\begin{matrix} [0, 1] \subseteq ⋃_{q \in D_{k} (N)} ⋃_{0 \leq a \leq q} {θ \in R : | θ - a / q | \leq C / (q N^{k})}, \end{matrix}

(9)

where

D_{k} (N)

denotes the set of least common denominators of the sums appearing on the left side of 8 . By a result of Erdös [2] ,

D_{k} (N)

has cardinality

| D_{k} (N) | ≪ N^{k} (log N)^{- c}

for some constant

c = c (k) > 0

, so it follows from 9 that

1 \leq \sum_{q \in D_{k} (N)} \sum_{0 \leq a \leq q} \frac{2 C}{q N^{k}} \leq 4 C N^{- k} | D_{k} (N) | ≪ (log N)^{- c},

which is impossible when

N \to \infty

. On the other hand, one may hypothesize that the set of fractions with denominators in

D_{k} (N)

is distributed similarly to the set of all fractions

a / q

with denominators

q \leq N^{k}

. Under such a hypothesis, one might hope for an estimate with

| D_{k} (N) |^{- 1}

in place of the term

(log 3 N)^{c} N^{- k}

on the right side of 10 below, and such an estimate, if true, would be essentially best possible. However, upon observing that

| D_{k} (N) | \geq \sum_{q_{1} \leq N} \dots \sum_{q_{k} \leq N} d (q_{1} \dots q_{k})^{- 1} \geq {\sum_{q \leq N} d (q)^{- 1}}^{k} ≫ N^{k} (log 3 N)^{- k},

we will take a more cautious approach and pose the following

Question 3. Let

k

be a positive integer. Determine the least value of

c_{k}

such that for any real

θ

and any positive integer

N

, there exist integers

a_{1}, . . ., a_{k}

q_{1}, . . ., q_{k}

, with

1 \leq q_{1}, . . ., q_{k} \leq N

, such that

\begin{matrix} | \frac{a_{1}}{q_{1}} + \cdot \cdot \cdot + \frac{a_{k}}{q_{k}} - θ | ≪ \frac{(log 3 N)^{c_{k}}}{q_{1} \dots q_{k} N^{k}} . \end{matrix}

(10)

We leave the answer to this question to the future.

Acknowledgement. The first author would like to thank the American Institute of Mathematics for support. The second author would like to thank Jeff Vaaler for several enlightening conversations on this and related topics.

References

Tsz Ho Chan, Finding Almost Squares II, preprint, 2005, arXiv:math.NT/0503438.
P. Erdös, An asymptotic inequality in the theory of numbers, Vestnik Leningrad. Univ. 15 (1960), no. 13, 41-49 (in Russian).
G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford University Press, 1979.

American Institute of Mathematics, 360 Portage Avenue, Palo Alto, CA 94306, U.S.A. E-mail address: thchan@aimath.org Department of Mathematics, 1 University Station, C1200, The University of Texas at Austin, Austin, TX 78712, U.S.A. E-mail address: kumchev@math.utexas.edu

Tsz Ho Chan

Angel V. Kumchev