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.
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:
which counts (also taking order into account) the number of solutions to , where . The theorem then states that, for any given , the relation
cannot be satisfied; that is, there is no satisfying the above estimate.
Theorems of Erdös-Fuchs type
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 ). Another reason this result is so celebrated may be due to the fact that, in 1941, P. Erdös and P. Turán conjectured that, subject to the same hypotheses as in the theorem stated, the relation
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
Theorem (Sárközy, 1980). If and are two infinite subsets of natural numbers with , then cannot hold for any constant .
Theorem (Horváth, 2004). If and are infinite subsets of natural numbers with and , then cannot hold for any constant .
The 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 showed in 2009 that, in the same conditions as in the original statement of Erdös-Fuchs, for every the relation
cannot hold. In another direction, in 2002, G. Horváth gave a precise generalization of Sárközy's 1980 result, showing that
Theorem (Horváth, 2002) If () are (at least two) infinite subsets of natural numbers and the following estimates are valid:
then the relation:
cannot hold for any constant .
Yet another direction in which the Erdös-Fuchs theorem can be improved is by considering approximations to other than for some . In 1963, P. T. Bateman, E. E. Kohlbecker and J. P. Tull 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.
- Erdős, P.; Fuchs, W. H. J. (1956). "On a Problem of Additive Number Theory". J. Lond. math. Soc. 31 (1): 67–73. doi:10.1112/jlms/s1-31.1.67.
- 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) . Sequences (2nd ed.). Berlin, New York: Springer-Verlag. ISBN 978-0-387-90801-4. MR 0210679.
- 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.