Erdős-Fuchs theorem

From Encyclopedia of Mathematics
Jump to: navigation, search

2020 Mathematics Subject Classification: Primary: 11B34 [MSN][ZBL]

A statement about the number of ways that positive integers can be represented as a sum of two elements of a given set, stating that the average order of this number cannot be close to being a linear function. Given a subset $A$ of the natural numbers let $r(n)$ denote the number of ways that a natural number $n$ can be expressed as the sum of two elements of $A$ (taking order into account). We consider the average $$ R(n) = (r(1)+r(2)+\cdots+r(n) ) / n \ . $$ The theorem states that $$ R(n) = C + O\left(n^{-3/4-\epsilon}\right) $$ cannot hold unless $C=0$


  • P. Erdős, W.H.J. Fuchs, On a Problem of Additive Number TheoryJournal of the London Mathematical Society 31 (1956) 67–73 DOI 10.1112/jlms/s1-31.1.67 Zbl 0070.04104
  • D.J. Newman, "Analytic number theory", Graduate Texts in Mathematics 177 Springer (1998) ISBN 0-387-98308-2 Zbl 0887.11001
How to Cite This Entry:
Erdős-Fuchs theorem. Encyclopedia of Mathematics. URL: