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{array}{c}{a}_i+a_j=n\\ a_i,a_j\in A\end{array}}1.$$

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

$$\sum _{n\le 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\le 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$

$$\underset{N\le M}{\max }\left|\sum _{n\le N}{R}_n(A)-cn\right|=\mathrm{\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}}$.

Title	Erdős-Fuchs theorem
Canonical name	ErdHosFuchsTheorem
Date of creation	2013-03-22 13:20:59
Last modified on	2013-03-22 13:20:59
Owner	bbukh (348)
Last modified by	bbukh (348)
Numerical id	12
Author	bbukh (348)
Entry type	Theorem
Classification	msc 11B34