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.
Contents
- Statement
- Theorems of Erds Fuchs type
- Improved versions for h 2
- The general case h 2
- Non linear approximations
- References
The theorem is named after Paul Erdős and Wolfgang Heinrich Johannes Fuchs, who published it in 1956.
Statement
Let
which counts (also taking order into account) the number of solutions to
cannot be satisfied; that is, there is no
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 that in the case of the sequence
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
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
This theorem has been extended in a number of different directions. In 1980, A. Sárközy considered two sequences which are "near" in some sense. He proved the following:
Theorem (Sárközy, 1980). If
In 1990, H. L. Montgomery and R. C. Vaughan where able to remove the log from the right-hand side of Erdös-Fuchs original statement, showing that
cannot hold. In 2004, G. Horváth extended both these results, proving the following:
Theorem (Horváth, 2004). If
The general case (h ≥ 2)
The natural generalization to Erdös-Fuchs theorem, namely for
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
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
Theorem (Bateman-Kohlbecker-Tull, 1963). Let
where
At the end of their paper, it is also remarked that it is possible to extend their method to obtain results considering