Erdős-Fuchs theorem

Let A be a set of natural numbers. Let Rn(A) be the number of ways to represent n as a sum of two elements in A, that is,


Erdős-Fuchs theorem [1, 2] states that if c>0, then

nNRn(A)=cN+o(N14log-12N) (1)

cannot hold.

On the other hand, Ruzsa [5] constructed a set for which


Montgomery and Vaughan [4] improved on the original Erdős-Fuchs theorem by showing that for every c>0


holds. In [4] a result of Jurkat is cited which appeared in the Ph. D. thesis of Hayashi [3] which improves N14log-12N in (1) to N14.


  • 1 Paul Erdős and Wolfgang H.J. Fuchs. On a problem of additive number theory. J. Lond. Math. Soc., 31:67–73, 1956. 0070.04104.
  • 2 Heini Halberstam and Klaus Friedrich Roth. Sequences. Springer-Verlag, second edition, 1983. 0498.10001.
  • 3 E. K. Hayashi. Omega theorems for the iterated additive convolution of non-negative arithmetic functionMathworldPlanetmath. PhD thesis, University of Illinois at Urbana-Champaign, 1973.
  • 4 H. L. Montgomery and R. C. Vaughan. On the Erdős-Fuchs theorems. In A tribute to Paul Erdős, pages 331–338. Cambridge Univ. Press, Cambridge, 1990. 0715.11005.
  • 5 Imre Ruzsa. A converse to a theorem of Erdős and Fuchs. J. Number TheoryMathworldPlanetmathPlanetmath, 62(2):397–402, 1997. 0872.11014.
Title Erdős-Fuchs theorem
Canonical name ErdHosFuchsTheorem
Date of creation 2013-03-22 13:20:59
Last modified on 2013-03-22 13:20:59
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 12
Author bbukh (348)
Entry type Theorem
Classification msc 11B34