Erdős-Fuchs Theorem

The Erdős-Fuchs theorem rules out an overly regular average for the additive representation function of an infinite set of nonnegative integers. If

$R_A(N)=|{(a,b) in A×A:a+b<=N}|,$

then there is no constant for which

Here pairs are ordered, repetitions are allowed, denotes little-O notation, and is the natural logarithm (Erdős and Fuchs 1956).

Montgomery and Vaughan (1990) removed the logarithmic factor, showing that even an error is impossible. In particular, cannot hold for an infinite set and positive .

This is problem 763 in the Erdős problems collection (Bloom 2026).

References

Bloom, T. F. "Erdős Problem 763." Accessed Oct. 26, 2026. https://www.erdosproblems.com/763.

Erdős, P. and Fuchs, W. H. J. "On a Problem of Additive Number Theory." J. London Math. Soc. 31, 67-73, 1956. https://doi.org/10.1112/jlms/s1-31.1.67.

Montgomery, H. L. and Vaughan, R. C. "On the Erdős-Fuchs Theorems." In A Tribute to Paul Erdős (Ed. A. Baker, B. Bollobás, and A. Hajnal). Cambridge, England: Cambridge University Press, pp. 331-338, 1990. https://doi.org/10.1017/CBO9780511983917.025.

Erdős-Fuchs Theorem

See also

Explore with Wolfram|Alpha

References

Cite this as:

Subject classifications