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
editLet be an infinite subset of the natural numbers and its representation function, which denotes the number of ways that a natural number can be expressed as the sum of elements of (taking order into account). We then consider the accumulated representation function
Theorems of Erdős–Fuchs type
editThe 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 of perfect squares one has
Improved versions for h = 2
editThis 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 and are two infinite subsets of natural numbers with , then cannot hold for any constant .
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
- Theorem (Horváth, 2004). If and are infinite subsets of natural numbers with and , then cannot hold for any constant .
General case (h ≥ 2)
editThe natural generalization to Erdős–Fuchs theorem, namely for , 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 the relation
- Theorem (Horváth, 2002) If ( ) are (at least two) infinite subsets of natural numbers and the following estimates are valid:
- (for )
- then the relation:
-
- cannot hold for any constant .
Non-linear approximations
editYet another direction in which the Erdős–Fuchs theorem can be improved is by considering approximations to other than for some . 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 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 , where if is bounded, and otherwise.
At the end of their paper, it is also remarked that it is possible to extend their method to obtain results considering with , but such results are deemed as not sufficiently definitive.
See also
edit- Erdős–Tetali theorem: For any , there is a set which satisfies . (Existence of economical bases)
- Erdős–Turán conjecture on additive bases: If is an additive basis of order 2, then . (Bases cannot be too economical)
References
edit- ^ Erdős, P.; Fuchs, W. H. J. (1956). "On a Problem of Additive Number Theory". Journal of the London Mathematical Society. 31 (1): 67–73. doi:10.1112/jlms/s1-31.1.67. hdl:2027/mdp.39015095244037.
- ^ Hardy, G. H. (1915). "On the expression of a number as the sum of two squares". Quarterly Journal of Mathematics. 46: 263–83.
- ^ 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. doi:10.1112/jlms/s1-16.4.212.
- ^ Sárközy, András (1980). "On a theorem of Erdős and Fuchs". Acta Arithmetica. 37: 333–338. doi:10.4064/aa-37-1-333-338.
- ^ Montgomery, H. L.; Vaughan, R. C. (1990). "On the Erdős–Fuchs theorem". In Baker, A; Bollobas, B; Hajnal, A (eds.). A tribute to Paul Erdős. Cambridge University Press. pp. 331–338. doi:10.1017/CBO9780511983917.025. ISBN 9780511983917.
- ^ Horváth, G. (2004). "An improvement of an extension of a theorem of Erdős and Fuchs". Acta Mathematica Hungarica. 104: 27–37. doi:10.1023/B:AMHU.0000034360.41926.5a.
- ^ Tang, Min (2009). "On a generalization of a theorem of Erdős and Fuchs". Discrete Mathematics. 309 (21): 6288–6293. doi:10.1016/j.disc.2009.07.006.
- ^ Horváth, Gábor (2002). "On a theorem of Erdős and Fuchs". Acta Arithmetica. 103 (4): 321–328. Bibcode:2002AcAri.103..321H. doi:10.4064/aa103-4-2.
- ^ Bateman, Paul T.; 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 (2): 278–284. doi:10.1090/S0002-9939-1963-0144876-1.
Further reading
edit- Newman, D. J. (1998). Analytic number theory. GTM. Vol. 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.