Page 38 -

III
The Erd˝ os–Fuchs Theorem

There has always been some fascination with the possibility of near
constancy of the representation functions r i (n) (of I (7), (8) and (9)).
In Chapter I we treated the case of r + (n) and showed that this could
noteventuallybeconstant.Thefactthatr(n)cannotbeconstantforan
infinite set is really trivial since r(n) is odd for n 2a, a ∈ A, and
even otherwise. The case of r − (n) is more difficult, and we will treat
it in this chapter as an introduction to the analysis in the Erd˝ os–Fuchs
theorem.
The Erd˝ os–Fuchs theorem involves the question of just how nearly
constant r(n) can be on average. Historically this all began with the
2
setA {n : n ∈ N 0 },thesetofperfectsquares,andtheobservation
that then r(0)+r(1)+r(2)+···+r(n) , the average value, is exactly equal to
n+1
1 times the number of lattice points in the quarter disc x, y ≥ 0,
n+1
2
2
x + y ≤ n. Consideration of the double Riemann integral shows
that this average approaches the area of the unit quarter circle, namely
r(0)+r(1)+r(2)+···+r(n) π
π/4, and so for this set A, → (r(n) is on
n+1 4
average equal to the constant π/4.)
The difficult question is how quickly this limit is approached. Thus
fairly simple reasoning shows that

r(0) + r(1) + r(2) + ··· + r(n) π 1
+ O √ ,
n + 1 4 n
whereas more involved analysis shows that

r(0) + r(1) + r(2) + ··· + r(n) π 1
+ O .
n + 1 4 n 2/3

31