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 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[]
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 of perfect squares one has
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 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)[]
The 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[]
Yet 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[]
- 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[]
- ^ 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". A tribute to Paul Erdős. Cambridge University Press. pp. 331–338. doi:10.1017/CBO9780511983917.025.
- ^ 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: 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. 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[]
- 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.
- Theorems in combinatorics
- Theorems in number theory
- Paul Erdős