Erdős–Fuchs theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, in the area of combinatorial 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 close to being a linear function.

The theorem is named after Paul Erdős and Wolfgang Heinrich Johannes Fuchs.


Let A be a subset of the natural numbers and 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) = \frac{r(1)+r(2)+\cdots+r(n)}{n}.

The theorem states that

R(n) = C + O\left(n^{-3/4-\varepsilon}\right)

cannot hold unless C = 0.