2000 Mathematics Subject Classification. 11J04, 11K60.
<ph f="txb">Approximating reals by sums of rationals</ph>

### Angel V. Kumchev

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
• Abstract. We study how well a real number can be approximated by sums of two or more rational numbers with denominators up to a certain size.

1 Introduction and main result

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 $\theta$  and any positive integer $N$  , there exist integers $a$  and $q$  , with $1\le q\le N$  , such that $|\theta -\frac{a}{q}|<\frac{1}{qN}.$
Moreover, the bound $1/\left(qN\right)$  is best possible, apart from the constant factor. To see this, it suffices to consider the golden ratio $\theta =\left(\sqrt{5}-1\right)/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 $\theta$  and any positive integer $N$  , give an upper bound for ${min}_{{a}_{1},{a}_{2},{q}_{1},{q}_{2}\in \mathbb{Z}1\le {q}_{1},{q}_{2}\le N}|\frac{{a}_{1}}{{q}_{1}}+\frac{{a}_{2}}{{q}_{2}}-\theta |.$
With the golden ratio in mind, we know that the upper bound can be no better than $O\left(1/\left({q}_{1}{q}_{2}{N}^{2}\right)\right)$  . So, what is the best possible upper bound?
More generally,
Question 2. Let $k$  be a positive integer. For any real $\theta$  and any positive integer $N$  , give an upper bound for ${min}_{{a}_{1},...,{a}_{k},{q}_{1},...,{q}_{k}\in \mathbb{Z}1\le {q}_{1},...,{q}_{k}\le N}|\frac{{a}_{1}}{{q}_{1}}+\cdot \cdot \cdot +\frac{{a}_{k}}{{q}_{k}}-\theta |.$
To these, we have the following result:
Theorem 2. Let $k$  be a positive integer. For any real $\theta$  and any positive integer $N$  , there exist integers ${a}_{1},...,{a}_{k}$  , ${q}_{1},...,{q}_{k}$  , with $1\le {q}_{1},...{q}_{k}\le N$  , such that $|\frac{{a}_{1}}{{q}_{1}}+\cdot \cdot \cdot +\frac{{a}_{k}}{{q}_{k}}-\theta |\ll {N}^{-k}.$
The bound ${N}^{-k}$  is best possible in the sense that, for some $\theta$  , the minimum in Question  2 can be as large as ${N}^{-k}$  . For example, if one considers $\theta =1/\left(2{N}^{k}\right)$  , $|\frac{{a}_{1}}{{q}_{1}}+\cdots +\frac{{a}_{k}}{{q}_{k}}-\theta |\ge \frac{1}{2{N}^{k}}$  for any choice of ${a}_{1},...,{a}_{k},{q}_{1},...,{q}_{k}$  , with $1\le {q}_{1},...,{q}_{k}\le 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}$  by $\left({q}_{1}\cdots {q}_{k}{\right)}^{-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\ge 1$  is an integer. There is a number ${x}_{0}\left(k\right)\ge 1$  such that ${\sum }_{1\le {q}_{1},...,{q}_{k}\le x}^{*}{q}_{1}\cdots {q}_{k}\gg {x}^{2k},$  whenever $x\ge {x}_{0}\left(k\right)$  . Here, ${\sum }^{*}$  denotes a summation over the $k$  -tuples ${q}_{1},...,{q}_{k}$  such that $\left({q}_{i},{q}_{j}\right)=1$  whenever $1\le i  .
• Proof. It suffices to show that  $\begin{array}{c}{\sum }_{n\le x\left(n,m\right)=1}\phi \left(n{\right)}^{\alpha }{n}^{1-\alpha }\gg {x}^{2}\phi \left(m\right){m}^{-1},\end{array}$ (1)
whenever $0\le \alpha \le k-1$  , $1\le m\le {x}^{k-1}$  , and $x\ge {x}_{0}\left(k\right)$  . The conclusion of the lemma will then follow by successive applications of  1 with $\alpha =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{array}{c}{\sum }_{n\le x\left(n,m\right)=1}{\left(\frac{n}{\phi \left(n\right)}\right)}^{\alpha }\ll x\phi \left(m\right){m}^{-1}.\end{array}$ (2)
Define the multiplicative functions $f\left(n\right)=\left\{\begin{array}{cc}{\left(n/\phi \left(n\right)\right)}^{\alpha }& \text{if}\left(n,m\right)=1,\\ 0& \text{if}\left(n,m\right)>1,\end{array}g\left(n\right)={\sum }_{d|n}f\left(d\right)\mu \left(n/d\right).$  Then $g\left(n\right)\ge 0$  , and
 $\begin{array}{cc}{\sum }_{n\le x}f\left(n\right)& ={\sum }_{n\le x}{\sum }_{d|n}g\left(d\right)={\sum }_{d\le x}g\left(d\right)⌊\frac{x}{d}⌋\le x{\sum }_{d\le x}g\left(d\right){d}^{-1}\end{array}$
 $\begin{array}{cc}& \le x{\prod }_{p\le x}{\sum }_{\nu =0}^{\infty }g\left({p}^{\nu }\right){p}^{-\nu }=x{\prod }_{p\le x}\left(1-{p}^{-1}\right){\sum }_{\nu =0}^{\infty }f\left({p}^{\nu }\right){p}^{-\nu }\end{array}$
 $\begin{array}{cc}& \le x{\prod }_{p|mp\le x}\left(1-{p}^{-1}\right){\prod }_{p}\left(1+\frac{{p}^{\alpha }-\left(p-1{\right)}^{\alpha }}{p\left(p-1{\right)}^{\alpha }}\right)\end{array}$
 $\begin{array}{cc}& \le x{\prod }_{p|m}\left(1-{p}^{-1}\right){\prod }_{p}\left(1+\frac{{p}^{\alpha }-\left(p-1{\right)}^{\alpha }}{p\left(p-1{\right)}^{\alpha }}\right)+O\left(1\right).\end{array}$
 $\begin{array}{}\end{array}$
The last inequality follows on noting that $m$  has at most $k-2$  prime divisors $p>x$  , and hence, ${\prod }_{p|mp>x}\left(1-{p}^{-1}\right)=1+O\left({x}^{-1}\right).$  This proves  2 . On the other hand, when $\alpha =0$  , we have ${\sum }_{n\le x\left(n,m\right)=1}n={\sum }_{d|m}\mu \left(d\right)d{\sum }_{k\le x/d}k=\frac{\phi \left(m\right)}{2m}{x}^{2}+O\left(x\tau \left(m\right)\right),$  whence  $\begin{array}{c}{\sum }_{n\le x\left(n,m\right)=1}{n}^{1/2}\ge {x}^{-1/2}{\sum }_{n\le x\left(n,m\right)=1}n\gg {x}^{3/2}\phi \left(m\right){m}^{-1}.\end{array}$ (3)
Finally,  1 follows from  2 ,  3 , and Cauchy's inequality: ${\sum }_{n\le x\left(n,m\right)=1}\phi \left(n{\right)}^{\alpha }{n}^{1-\alpha }\ge {\left\{{\sum }_{n\le x\left(n,m\right)=1}{n}^{1/2}\right\}}^{2}{\left\{{\sum }_{n\le x\left(n,m\right)=1}{\left(\frac{n}{\phi \left(n\right)}\right)}^{\alpha }\right\}}^{-1}\gg {x}^{2}\phi \left(m\right){m}^{-1}.$
• Proof of Theorem  2 . For $0<\Delta <1/2$  , define $t\left(x\right)=max\left(1-|x|/\Delta ,0\right),g\left(x\right)={\sum }_{n=-\infty }^{\infty }t\left(x-n\right).$  The function $g$  has a Fourier expansion $g\left(x\right)={\sum }_{h=-\infty }^{\infty }{\stackrel{^}{g}}_{h}e\left(hx\right),{\stackrel{^}{g}}_{h}=\Delta {\left(\frac{sin\pi \Delta h}{\pi \Delta h}\right)}^{2}.$  We consider the sum  $\begin{array}{c}\mathcal{S}={\sum }_{1\le {q}_{1},...,{q}_{k}\le N}^{*}{\sum }_{{a}_{1}=1}^{{q}_{1}}...{\sum }_{{a}_{k}=1}^{{q}_{k}}g\left(\frac{{a}_{1}}{{q}_{1}}+\cdot \cdot \cdot +\frac{{a}_{k}}{{q}_{k}}-\theta \right),\end{array}$ (4)
where ${\sum }^{*}$  has the same meaning as in the Lemma. Putting in the Fourier expansion for $g$  , we get
 $\begin{array}{cc}\mathcal{S}=& {\sum }_{1\le {q}_{1},...,{q}_{k}\le N}^{*}{\sum }_{{a}_{1}=1}^{{q}_{1}}...{\sum }_{{a}_{k}=1}^{{q}_{k}}{\sum }_{h=-\infty }^{\infty }{\stackrel{^}{g}}_{h}e\left(h\left(\frac{{a}_{1}}{{q}_{1}}+\cdot \cdot \cdot +\frac{{a}_{k}}{{q}_{k}}-\theta \right)\right)\end{array}$ (5)
 $\begin{array}{cc}=& {\sum }_{1\le {q}_{1},...,{q}_{k}\le N}^{*}{\sum }_{h=-\infty }^{\infty }{\stackrel{^}{g}}_{h}e\left(-h\theta \right){\sum }_{{a}_{1}=1}^{{q}_{1}}e\left(h{a}_{1}/{q}_{1}\right)...{\sum }_{{a}_{k}=1}^{{q}_{k}}e\left(h{a}_{k}/{q}_{k}\right)\end{array}$
 $\begin{array}{cc}=& {\sum }_{1\le {q}_{1},...,{q}_{k}\le N}^{*}{q}_{1}\cdots {q}_{k}{\sum }_{h=-\infty {q}_{1}\cdots {q}_{k}|h}^{\infty }{\stackrel{^}{g}}_{h}e\left(-h\theta \right),\end{array}$
 $\begin{array}{}\end{array}$
as ${\sum }_{a=1}^{q}e\left(ha/q\right)=\left\{\begin{array}{cc}q& \text{if}q|h,\\ 0& \text{otherwise}.\end{array}$  If $m$  is a positive integer and $\Delta \le {m}^{-1}$  , we have  $\begin{array}{c}\begin{array}{cccc}{\sum }_{h\mathbf{\ne }0}|{\stackrel{^}{g}}_{mh}|& \le 2\left\{{\sum }_{h=1}^{H}\Delta +\frac{1}{\Delta {m}^{2}}{\sum }_{h=H+1}^{\infty }{h}^{-2}\right\}& & \le 2\left(H\Delta +\frac{1}{H\Delta {m}^{2}}\right)\le 6{m}^{-1},\end{array}\end{array}$ (6)
where $H=⌈\left(\Delta m{\right)}^{-1}⌉$  ; whereas if $\Delta >{m}^{-1}$  , we have  $\begin{array}{c}{\sum }_{h\mathbf{\ne }0}|{\stackrel{^}{g}}_{mh}|\le \frac{2\zeta \left(2\right)}{\Delta {m}^{2}}\le 4{m}^{-1}.\end{array}$ (7)
Putting  6 and  7 (with $m={q}_{1}\cdots {q}_{k}$  ) into  5 , we obtain $\mathcal{S}=\Delta {\sum }_{1\le {q}_{1},...,{q}_{k}\le N}^{*}{q}_{1}\cdots {q}_{k}+O\left({N}^{k}\right),$  the $O$  -implied constant being absolute (in fact, it is $6$  ). Therefore, upon choosing $\Delta =c{N}^{-k}$  with a sufficiently large $c>0$  , it follows from the Lemma that $\mathcal{S}>0$  . Hence, by  4 , $g\left(\frac{{a}_{1}}{{q}_{1}}+\cdot \cdot \cdot +\frac{{a}_{k}}{{q}_{k}}-\theta \right)>0$  for some integers ${a}_{1},...,{a}_{k},{q}_{1},...,{q}_{k}$  with $1\le {q}_{1},...,{q}_{k}\le N$  . Then, by the definition of $g$  , $|\frac{{a}_{1}}{{q}_{1}}+\cdot \cdot \cdot +\frac{{a}_{k}}{{q}_{k}}-n-\theta |\le 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}$  by $\left({q}_{1}\cdots {q}_{k}{\right)}^{-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 $\theta$  , there exist integers ${a}_{1},...,{a}_{k},{q}_{1},...,{q}_{k}$  , with $1\le {q}_{1},...,{q}_{k}\le N$  , such that
 $\begin{array}{c}|\frac{{a}_{1}}{{q}_{1}}+\cdots +\frac{{a}_{k}}{{q}_{k}}-\theta |\le \frac{C}{{q}_{1}\cdots {q}_{k}{N}^{k}}.\end{array}$ (8)
Then
 $\begin{array}{c}\left[0,1\right]\subseteq {\bigcup }_{q\in {\mathcal{D}}_{k}\left(N\right)}{\bigcup }_{0\le a\le q}\left\{\theta \in \mathbb{R}:|\theta -a/q|\le C/\left(q{N}^{k}\right)\right\},\end{array}$ (9)
where ${\mathcal{D}}_{k}\left(N\right)$  denotes the set of least common denominators of the sums appearing on the left side of  8 . By a result of Erdös [2, ${\mathcal{D}}_{k}\left(N\right)$  has cardinality $|{\mathcal{D}}_{k}\left(N\right)|\ll {N}^{k}\left(logN{\right)}^{-c}$  for some constant $c=c\left(k\right)>0$  , so it follows from  9 that $1\le {\sum }_{q\in {\mathcal{D}}_{k}\left(N\right)}{\sum }_{0\le a\le q}\frac{2C}{q{N}^{k}}\le 4C{N}^{-k}|{\mathcal{D}}_{k}\left(N\right)|\ll \left(logN{\right)}^{-c},$  which is impossible when $N\to \infty$  . On the other hand, one may hypothesize that the set of fractions with denominators in ${\mathcal{D}}_{k}\left(N\right)$  is distributed similarly to the set of all fractions $a/q$  with denominators $q\le {N}^{k}$  . Under such a hypothesis, one might hope for an estimate with $|{\mathcal{D}}_{k}\left(N\right){|}^{-1}$  in place of the term $\left(log3N{\right)}^{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 $|{\mathcal{D}}_{k}\left(N\right)|\ge {\sum }_{{q}_{1}\le N}\cdots {\sum }_{{q}_{k}\le N}d\left({q}_{1}\cdots {q}_{k}{\right)}^{-1}\ge {\left\{{\sum }_{q\le N}d\left(q{\right)}^{-1}\right\}}^{k}\gg {N}^{k}\left(log3N{\right)}^{-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 $\theta$  and any positive integer $N$  , there exist integers ${a}_{1},...,{a}_{k}$  , ${q}_{1},...,{q}_{k}$  , with $1\le {q}_{1},...,{q}_{k}\le N$  , such that
 $\begin{array}{c}|\frac{{a}_{1}}{{q}_{1}}+\cdot \cdot \cdot +\frac{{a}_{k}}{{q}_{k}}-\theta |\ll \frac{\left(log3N{\right)}^{{c}_{k}}}{{q}_{1}\cdots {q}_{k}{N}^{k}}.\end{array}$ (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

1. Tsz Ho Chan, Finding Almost Squares II, preprint, 2005, arXiv:math.NT/0503438.
2. P. Erdös, An asymptotic inequality in the theory of numbers, Vestnik Leningrad. Univ. 15 (1960), no. 13, 41-49 (in Russian).
3. 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