# 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 two elements of a given set, stating that the average order of this number cannot be too close of being a linear function.

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

## Statement

Let ${\textstyle {\mathcal {A}}\subseteq \mathbb {N} }$ be an infinite subset of the natural numbers and ${\textstyle r_{{\mathcal {A}},h}(n)}$ its representation function, which denotes the number of ways that a natural number ${\textstyle n}$ can be expressed as the sum of ${\textstyle h}$ elements of ${\textstyle {\mathcal {A}}}$ (taking order into account). We then consider the accumulated representation function:

${\displaystyle 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 ${\textstyle k_{1}+\cdots +k_{h}\leqslant x}$, where ${\textstyle k_{1},\ldots ,k_{h}\in {\mathcal {A}}}$. The theorem then states that, for any given ${\textstyle c>0}$, the relation

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

cannot be satisfied; that is, there is no ${\textstyle {\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[1] that in the case of the sequence ${\textstyle {\mathcal {Q}}:=\{0,1,4,9,\ldots \}}$ of perfect squares one have

${\displaystyle \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 ${\textstyle 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[2] conjectured that, subject to the same hypotheses as in the theorem stated, the relation

${\displaystyle s_{{\mathcal {A}},2}(n)=cn+O(1)}$

could not hold. This fact remained unproved until 1956 when Erdös and Fuchs obtained their theorem, which is much 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[3] considered two sequences which are "near" in some sense. He proved the following:

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

In 1990, H. L. Montgomery and R. C. Vaughan[4] where 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. Horváth[5] extended both these results, proving the following:

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

### The general case (h ≥ 2)

The natural generalization to Erdös-Fuchs theorem, namely for ${\textstyle h\geqslant 3}$, is known to hold with same strength as the Montgomery-Vaughan's version. In fact, M. Tang[6] 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. Horváth[7] 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)} (${\displaystyle j=1,\ldots ,k}$) are ${\displaystyle k}$ (at least two) infinite subsets of natural numbers and the following estimates are valid:

• ${\displaystyle a_{i}^{(1)}-a_{i}^{(2)}=o{\big (}(a_{i}^{(1)})^{1/2}\log(a_{i}^{(1)})^{-k/2}{\big )}}$

• ${\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 ${\textstyle c>0}$.

### Non-linear approximations

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

Theorem (Bateman-Kohlbecker-Tull, 1963). Let ${\textstyle 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 ${\textstyle \alpha =3/4}$ if ${\textstyle L(x)}$ is bounded and ${\textstyle 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.

## References

• ^ Hardy, G. H. (1915). "On the expression of a number as the sum of two squares". Quart. J. Math. 46: 263–83.
• ^ Erdös, P.; Turán, P. (1941). "On a problem of Sidon in additive number theory, and some related problems". J. Lond. math. Soc. 16: 212–5.
• ^ Sárközy, A. (1980). "On a theorem of Erdös and Fuchs". Acta Arith. 37: 333–338.
• ^ Montgomery, H. L.; Vaughan, R. C. (1990). "On the Erdös-Fuchs theorem". A tribute to Paul Erdös. Cambridge Univ. Press: 331–338.
• ^ Horváth, G. (2004). "An improvement of an extension of a theorem of Erdös and Fuchs". Acta Math. Hung. 104: 27–37.
• ^ Tang, Min (2009). "On a generalization of a theorem of Erdös and Fuchs". Disc. Math. 309: 6288–6293.
• ^ Horváth, G. (2002). "On a theorem of Erdös and Fuchs". Acta Arith. 103 (4): 321–328.
• ^ Bateman, P. T.; Kohlbecker, E. E.; Tull, J. P. (1963). "On a theorem of Erdös and Fuchs in additive number theory". Proc. Am. math. Soc. 14: 278–84.