Erdős–Fuchs theorem

This theorem has been extended in a number of different directions. In 1980, A. Sárközy[4] considered two sequences which are "near" in some sense. He proved the following:

• Theorem (Sárközy, 1980). If ${\displaystyle {\mathcal {A}}=\{a_{1}<a_{2}<\ldots \}}$ and ${\displaystyle {\mathcal {B}}=\{b_{1}<b_{2}<\ldots \}}$ are two infinite subsets of natural numbers with ${\displaystyle a_{i}-b_{i}=o{\big (}a_{i}^{1/2}\log(a_{i})^{-1}{\big )}}$, then ${\displaystyle |\{(i,j):a_{i}+b_{j}\leqslant n\}|=cn+o{\big (}n^{1/4}\log(n)^{-1/2}{\big )}}$ cannot hold for any constant ${\displaystyle c>0}$.

In 1990, H. L. Montgomery and R. C. Vaughan[5] were able to remove the log from the right-hand side of Erdős–Fuchs original statement, showing that

$${\displaystyle s_{{\mathcal {A}},2}(n)=cn+o(n^{1/4})}$$

cannot hold. In 2004, Gábor Horváth[6] extended both these results, proving the following:

• Theorem (Horváth, 2004). If ${\displaystyle {\mathcal {A}}=\{a_{1}<a_{2}<\ldots \}}$ and ${\displaystyle {\mathcal {B}}=\{b_{1}<b_{2}<\ldots \}}$ are infinite subsets of natural numbers with ${\displaystyle a_{i}-b_{i}=o{\big (}a_{i}^{1/2}{\big )}}$ and ${\displaystyle |{\mathcal {A}}\cap [0,n]|-|{\mathcal {B}}\cap [0,n]|=O(1)}$, then ${\displaystyle |\{(i,j):a_{i}+b_{j}\leqslant n\}|=cn+o{\big (}n^{1/4}{\big )}}$ cannot hold for any constant ${\displaystyle c>0}$.

The natural generalization to Erdős–Fuchs theorem, namely for ${\displaystyle h\geqslant 3}$, is known to hold with same strength as the Montgomery–Vaughan's version. In fact, M. Tang[7] showed in 2009 that, in the same conditions as in the original statement of Erdős–Fuchs, for every ${\displaystyle h\geqslant 2}$ the relation

$${\displaystyle s_{{\mathcal {A}},h}(n)=cn+o(n^{1/4})}$$

cannot hold. In another direction, in 2002, Gábor Horváth[8] gave a precise generalization of Sárközy's 1980 result, showing that

• Theorem (Horváth, 2002) If ${\displaystyle {\mathcal {A}}^{(j)}=\{a_{1}^{(j)}<a_{2}^{(j)}<\ldots \}}$ (${\displaystyle j=1,\ldots ,k}$) are ${\displaystyle k}$ (at least two) infinite subsets of natural numbers and the following estimates are valid:

1. ${\displaystyle a_{i}^{(1)}-a_{i}^{(2)}=o{\big (}(a_{i}^{(1)})^{1/2}\log(a_{i}^{(1)})^{-k/2}{\big )}}$
2. ${\displaystyle |{\mathcal {A}}^{(j)}\cap [0,n]|=\Theta {\big (}|{\mathcal {A}}^{(1)}\cap [0,n]|{\big )}}$ (for ${\displaystyle j=3,\ldots ,k}$)

then the relation:

${\displaystyle |\{(i_{1},\ldots ,i_{k}):a_{i_{1}}^{(1)}+\ldots +a_{i_{k}}^{(k)}\leqslant n,~a_{i_{j}}^{(j)}\in {\mathcal {A}}^{(j)}(j=1,\ldots ,k)\}|=cn+o{\big (}n^{1/4}\log(n)^{1-3k/4}{\big )}}$

cannot hold for any constant ${\displaystyle c>0}$.

Yet another direction in which the Erdős–Fuchs theorem can be improved is by considering approximations to ${\displaystyle s_{{\mathcal {A}},h}(n)}$ other than ${\displaystyle cn}$ for some ${\displaystyle c>0}$. In 1963, Paul T. Bateman, Eugene E. Kohlbecker and Jack P. Tull[9] proved a slightly stronger version of the following:

• Theorem (Bateman–Kohlbecker–Tull, 1963). Let ${\displaystyle L(x)}$ be a slowly varying function which is either convex or concave from some point onward. Then, on the same conditions as in the original Erdős–Fuchs theorem, we cannot have ${\displaystyle s_{{\mathcal {A}},2}(n)=nL(n)+o{\big (}n^{1/4}\log(n)^{-1/2}L(n)^{\alpha }{\big )}}$, where ${\displaystyle \alpha =3/4}$ if ${\displaystyle L(x)}$ is bounded, and ${\displaystyle 1/4}$ otherwise.

At the end of their paper, it is also remarked that it is possible to extend their method to obtain results considering ${\displaystyle n^{\gamma }}$ with ${\displaystyle \gamma \neq 1}$, but such results are deemed as not sufficiently definitive.