# Erdős-Fuchs theorem

Let $A$ be a set of natural numbers. Let $R_{n}(A)$ be the number of ways to represent $n$ as a sum of two elements in $A$, that is,

 $R_{n}(A)=\sum_{\begin{subarray}{c}a_{i}+a_{j}=n\\ a_{i},a_{j}\in A\end{subarray}}1.$

Erdős-Fuchs theorem [1, 2] states that if $c>0$, then

 $\sum_{n\leq N}R_{n}(A)=cN+o\left(N^{\frac{1}{4}}\log^{-\frac{1}{2}}N\right)$ (1)

cannot hold.

On the other hand, Ruzsa [5] constructed a set for which

 $\sum_{n\leq N}R_{n}(A)=cN+O\left(N^{\frac{1}{4}}\log N\right).$

Montgomery and Vaughan [4] improved on the original Erdős-Fuchs theorem by showing that for every $c>0$

 $\max_{N\leq M}\left\lvert\sum_{n\leq N}R_{n}(A)-cn\right\rvert=\Omega\left(M^{% \frac{1}{4}}\log^{-\frac{1}{4}}M\right)$

holds. In [4] a result of Jurkat is cited which appeared in the Ph. D. thesis of Hayashi [3] which improves $N^{\frac{1}{4}}\log^{-\frac{1}{2}}N$ in (1) to $N^{\frac{1}{4}}$.

## References

• 1 Paul Erdős and Wolfgang H.J. Fuchs. On a problem of additive number theory. J. Lond. Math. Soc., 31:67–73, 1956. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0070.04104Zbl 0070.04104.
• 2 Heini Halberstam and Klaus Friedrich Roth. Springer-Verlag, second edition, 1983. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0498.10001Zbl 0498.10001.
• 3 E. K. Hayashi. Omega theorems for the iterated additive convolution of non-negative arithmetic function. PhD thesis, University of Illinois at Urbana-Champaign, 1973.
• 4 H. L. Montgomery and R. C. Vaughan. On the Erdős-Fuchs theorems. In A tribute to Paul Erdős, pages 331–338. Cambridge Univ. Press, Cambridge, 1990. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0715.11005Zbl 0715.11005.
• 5 Imre Ruzsa. A converse to a theorem of Erdős and Fuchs. , 62(2):397–402, 1997. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0872.11014Zbl 0872.11014.
Title Erdős-Fuchs theorem ErdHosFuchsTheorem 2013-03-22 13:20:59 2013-03-22 13:20:59 bbukh (348) bbukh (348) 12 bbukh (348) Theorem msc 11B34