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.

Statement

Let ${\displaystyle {\mathcal {A}}\subseteq \mathbb {N} }$ be an infinite subset of the natural numbers and ${\displaystyle r_{{\mathcal {A}},h}(n)}$ its representation function, which denotes the number of ways that a natural number ${\displaystyle n}$ can be expressed as the sum of ${\displaystyle h}$ elements of ${\displaystyle {\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 ${\displaystyle k_{1}+\cdots +k_{h}\leqslant x}$, where ${\displaystyle k_{1},\ldots ,k_{h}\in {\mathcal {A}}}$. The theorem then states that, for any given ${\displaystyle 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 ${\displaystyle {\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 ${\displaystyle {\mathcal {Q}}:=\{0,1,4,9,\ldots \}}$ of perfect squares one has

$${\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 ${\displaystyle 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 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[3] 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[4] 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. Horváth[5] 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}$.

General case (h ≥ 2)

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[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)}<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}$.

Non-linear approximations

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, 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 ${\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.

See also

• Erdős–Tetali theorem: For any ${\displaystyle h\geq 2}$, there is a set ${\displaystyle {\mathcal {A}}\subseteq \mathbb {N} }$ which satisfies ${\displaystyle r_{{\mathcal {A}},h}(n)=\Theta (\log(n))}$. (Existence of economical bases)
• Erdős–Turán conjecture on additive bases: If ${\displaystyle {\mathcal {A}}\subseteq \mathbb {N} }$ is an additive basis of order 2, then ${\displaystyle r_{{\mathcal {A}},2}(n)\neq O(1)}$. (Bases cannot be too economical)

References

• Erdős, P.; Fuchs, W. H. J. (1956). "On a Problem of Additive Number Theory". J. London Math. Soc. 31 (1): 67–73. doi:10.1112/jlms/s1-31.1.67. hdl:2027/mdp.39015095244037.
• Newman, D. J. (1998). Analytic number theory. GTM. 177. New York: Springer. pp. 31–38. ISBN 0-387-98308-2.
• Halberstam, H.; Roth, K. F. (1983) [1966]. Sequences (2nd ed.). Berlin, New York: Springer-Verlag. ISBN 978-0-387-90801-4. MR 0210679.
  1. Hardy, G. H. (1915). "On the expression of a number as the sum of two squares". Quart. J. Math. 46: 263–83.
  2. Erdős, P.; Turán, P. (1941). "On a problem of Sidon in additive number theory, and some related problems". J. London Math. Soc. 16: 212–5.
  3. Sárközy, A. (1980). "On a theorem of Erdős and Fuchs". Acta Arith. 37: 333–338.
  4. Montgomery, H. L.; Vaughan, R. C. (1990). "On the Erdős–Fuchs theorem". A tribute to Paul Erdős. Cambridge Univ. Press: 331–338.
  5. Horváth, G. (2004). "An improvement of an extension of a theorem of Erdős and Fuchs". Acta Math. Hung. 104: 27–37.
  6. Tang, Min (2009). "On a generalization of a theorem of Erdős and Fuchs". Discrete Math. 309: 6288–6293.
  7. Horváth, G. (2002). "On a theorem of Erdős and Fuchs". Acta Arith. 103 (4): 321–328.
  8. 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.