Erdős–Fuchs theorem explained

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

l{A}\subseteq N be an infinite subset of the natural numbers and r _{l{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 l{A} (taking order into account). We then consider the accumulated representation function$$s\_(x)\; :=\; \backslash sum\_\; r\_(n),$$which counts (also taking order into account) the number of solutions to k _{1} + … + k _{h} \leqslant x , where k _{1,\ldots,k} _{h} \in l{A} . The theorem then states that, for any given c> 0 , the relation$$s\_(n)\; =\; cn\; +\; o\backslash left(n^\backslash log(n)^\; \backslash right)$$cannot be satisfied; that is, there is no l{A}\subseteq 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

l{Q}:=\{0,1,4,9,\ldots\} of perfect squares one has$$\backslash limsup\_\; \backslash frac\; >\; 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\_(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

l{A} = \{a _{1} < a _{2} <\ldots\} and l{B} = \{b _{1} < b _{2} < \ldots\} are two infinite subsets of natural numbers with a _{i} - b _{i} = o ( a ^{1 / 2} _{i} log (a ^{-1} _{i)} ) , then |\{(i,j):a _{i+b} _{j} \leqslant n\}| = cn + o ( n ^{1/4} log (n) ^{-1/2} ) 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\_(n)\; =\; cn\; +\; o(n^)$$cannot hold. In 2004, Gábor Horváth^[6] extended both these results, proving the following:

• Theorem (Horváth, 2004). If

l{A}=\{a _{1<a} _{2<\ldots\}} and l{B}=\{b _{1<b} _{2<\ldots\}} are infinite subsets of natural numbers with a _{i-b} _{i} = o ( a ^{1 / 2} _{i} ) and | l{A}\cap[0,n]| - | l{B}\cap[0,n]| = O( 1 ) , then |\{(i,j):a _{i+b} _{j} \leqslant n\}| = cn + o ( n ^{1/4} ) 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\_(n)\; =\; cn\; +\; o(n^)$$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

l{A} ^{(j)} = \{a ^{(j)} _{2 <\ldots\}} (j =1 ,\ldots,k ) are k (at least two) infinite subsets of natural numbers and the following estimates are valid:

1. a ^{( 1 )} _{i} - a ^{( 2 )} _{i} = o ( (a ^{1 / 2} _{i)} log (a ^{( 1 )} _{i} ) ^{-k/2} )
2. | l{A} ^{(j)} \cap[ 0 ,n]| = \Theta ( | l{A} ^{(1)} \cap[ 0 ,n]| ) (for j =3 ,\ldots,k )

then the relation:

|\{(i _{1,\ldots,} i ^{( 1 )} _{i _{1}} + \ldots + a ^{(k)} _{i _{k}} \leqslant n,~ a ^{(j)} _{i _{j}} \in l{A} ^{(j)} (j =1 ,\ldots,k)\}| = cn + o ( n ^{1/4} log (n) ^{1-3k/4} )

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 _{l{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 _{l{A} , 2 }(n) = nL(n) + o ( n ^{1/4} log (n) ^{-1/2} L(n) ^{\alpha} ) , 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 ≠ 1 , but such results are deemed as not sufficiently definitive.

See also

• Erdős–Tetali theorem: For any

h \geq 2 , there is a set l{A}\subseteq N which satisfies r _{l{A} ,h}(n) = \Theta( log (n)) . (Existence of economical bases)

• Erdős–Turán conjecture on additive bases: If

l{A}\subseteq N is an additive basis of order 2, then r _{l{A} , 2 }(n) ≠ O( 1 ) . (Bases cannot be too economical)

Further reading

• Book: Donald J. Newman . Newman . Analytic number theory . . 177 . 1998 . 0-387-98308-2 . 31–38 . Springer . New York .
• Book: Halberstam . H. . Roth . K. F. . Sequences . Sequences (book) . 1966 . . Berlin, New York . 2nd . 978-0-387-90801-4 . 1983 . 0210679. Heini Halberstam. Klaus Roth.

Notes and References

1. On a Problem of Additive Number Theory . Erdős . Paul Erdős . Fuchs . Journal of the London Mathematical Society . 1956 . 31 . 1 . 67–73 . 10.1112/jlms/s1-31.1.67 . P.. W. H. J.. 2027/mdp.39015095244037 . free .
2. Hardy. G. H.. 1915. On the expression of a number as the sum of two squares. Quarterly Journal of Mathematics. 46. 263–83.
3. Erdős. P.. Turán. P.. 1941. On a problem of Sidon in additive number theory, and some related problems. Journal of the London Mathematical Society. Series 1. 16. 4. 212–215. 10.1112/jlms/s1-16.4.212.
4. Sárközy. András. 1980. On a theorem of Erdős and Fuchs. Acta Arithmetica. 37. 333–338. 10.4064/aa-37-1-333-338. free.
5. Book: Montgomery. H. L.. Vaughan. R. C.. A . Baker . B . Bollobas . A . Hajnal . 1990. On the Erdős–Fuchs theorem. A tribute to Paul Erdős. Cambridge University Press. 331–338. 10.1017/CBO9780511983917.025. 9780511983917 .
6. Horváth. G.. 2004. An improvement of an extension of a theorem of Erdős and Fuchs. Acta Mathematica Hungarica. 104. 27–37. 10.1023/B:AMHU.0000034360.41926.5a. free.
7. Tang. Min. 2009. On a generalization of a theorem of Erdős and Fuchs. Discrete Mathematics. 309. 21 . 6288–6293. 10.1016/j.disc.2009.07.006. free.
8. Horváth. Gábor. 2002. On a theorem of Erdős and Fuchs. Acta Arithmetica. 103. 4. 321–328. 10.4064/aa103-4-2. 2002AcAri.103..321H . free.
9. Bateman. Paul T.. Paul T. Bateman. Kohlbecker. Eugene E.. Tull. Jack P.. 1963. On a theorem of Erdős and Fuchs in additive number theory. Proceedings of the American Mathematical Society. 14. 278–284. 2. 10.1090/S0002-9939-1963-0144876-1. free.