# 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  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  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  a result of Jurkat is cited which appeared in the Ph. D. thesis of Hayashi  which improves $N^{\frac{1}{4}}\log^{-\frac{1}{2}}N$ in (1) to $N^{\frac{1}{4}}$.

## References

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