Erdős–Fuchs theorem

In mathematics, in the area of additive number theory, the Erdős–Fuchs theorem is a statement about the number of ways that numbers can be represented as a sum of elements of a given additive basis, stating that the average order of this number cannot be too close to being a linear function.

The theorem is named after Paul Erdős and Wolfgang Heinrich Johannes Fuchs, who published it in 1956.^[1]

Statement

Let ${\mathcal {A}}\subseteq \mathbb {N}$ be an infinite subset of the natural numbers and $r_{{\mathcal {A}},h}(n)$ its representation function, which denotes the number of ways that a natural number $n$ can be expressed as the sum of $h$ elements of ${\mathcal {A}}$ (taking order into account). We then consider the accumulated representation function $s_{{\mathcal {A}},h}(x):=\sum _{n\leqslant x}r_{{\mathcal {A}},h}(n),$ which counts (also taking order into account) the number of solutions to $k_{1}+\cdots +k_{h}\leqslant x$ , where $k_{1},\ldots ,k_{h}\in {\mathcal {A}}$ . The theorem then states that, for any given $c>0$ , the relation $s_{{\mathcal {A}},2}(n)=cn+o\left(n^{1/4}\log(n)^{-1/2}\right)$ cannot be satisfied; that is, there is no ${\mathcal {A}}\subseteq \mathbb {N}$ satisfying the above estimate.

Theorems of Erdős–Fuchs type

The Erdős–Fuchs theorem has an interesting history of precedents and generalizations. In 1915, it was already known by G. H. Hardy^[2] that in the case of the sequence ${\mathcal {Q}}:=\{0,1,4,9,\ldots \}$ of perfect squares one has $\limsup _{n\to +\infty }{\frac {\left|s_{{\mathcal {Q}},2}(n)-\pi n\right|}{n^{1/4}\log(n)^{1/4}}}>0$ This estimate is a little better than that described by Erdős–Fuchs, but at the cost of a slight loss of precision, P. Erdős and W. H. J. Fuchs achieved complete generality in their result (at least for the case $h=2$ ). Another reason this result is so celebrated may be due to the fact that, in 1941, P. Erdős and P. Turán^[3] conjectured that, subject to the same hypotheses as in the theorem stated, the relation $s_{{\mathcal {A}},2}(n)=cn+O(1)$ could not hold. This fact remained unproven until 1956, when Erdős and Fuchs obtained their theorem, which is even stronger than the previously conjectured estimate.

Improved versions for h = 2

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 ${\mathcal {A}}=\{a_{1}<a_{2}<\ldots \}$ and ${\mathcal {B}}=\{b_{1}<b_{2}<\ldots \}$ are two infinite subsets of natural numbers with $a_{i}-b_{i}=o{\big (}a_{i}^{1/2}\log(a_{i})^{-1}{\big )}$ , then $|\{(i,j):a_{i}+b_{j}\leqslant n\}|=cn+o{\big (}n^{1/4}\log(n)^{-1/2}{\big )}$ cannot hold for any constant $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 $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 ${\mathcal {A}}=\{a_{1}<a_{2}<\ldots \}$ and ${\mathcal {B}}=\{b_{1}<b_{2}<\ldots \}$ are infinite subsets of natural numbers with $a_{i}-b_{i}=o{\big (}a_{i}^{1/2}{\big )}$ and $|{\mathcal {A}}\cap [0,n]|-|{\mathcal {B}}\cap [0,n]|=O(1)$ , then $|\{(i,j):a_{i}+b_{j}\leqslant n\}|=cn+o{\big (}n^{1/4}{\big )}$ cannot hold for any constant $c>0$ .

General case (h ≥ 2)

The natural generalization to Erdős–Fuchs theorem, namely for $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 $h\geqslant 2$ the relation $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 ${\mathcal {A}}^{(j)}=\{a_{1}^{(j)}<a_{2}^{(j)}<\ldots \}$ ( $j=1,\ldots ,k$ ) are $k$ (at least two) infinite subsets of natural numbers and the following estimates are valid:

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

then the relation:

|\{(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 $c>0$ .

Non-linear approximations

Yet another direction in which the Erdős–Fuchs theorem can be improved is by considering approximations to $s_{{\mathcal {A}},h}(n)$ other than $cn$ for some $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 $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 $s_{{\mathcal {A}},2}(n)=nL(n)+o{\big (}n^{1/4}\log(n)^{-1/2}L(n)^{\alpha }{\big )}$ , where $\alpha =3/4$ if $L(x)$ is bounded, and $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 $n^{\gamma }$ with $\gamma \neq 1$ , but such results are deemed as not sufficiently definitive.