Page 56 -

V. The Waring Problem
50
A. Theorem (Dirichlet). Given a real x and a positive integer M,
there exists an integer a and a positive number b ≤ M such that
a 1
|x − |≤ .
b (M+1)b
Proof. Consider the numbers 0, x,2x,3x, ..., Mx all reduced
(mod 1). Clearly, two of these must be within 1 of each other.
M+1
If these two differ by bx, then 1 ≤ b ≤ M and bx (mod 1) is, in
1
magnitude, ≤ . Next pick an integer a that makes bx − a equal
M+1
1 a 1
to bx (mod 1). So |bx −a|≤ which means |x − |≤ ,
(M+1) b (M+1)b
as asserted. Q.E.D.
We also point out that this is a best possible result as the choice
1
x shows for every M. (Again, we may assume that (a, b)
M+1
1 for, if they have a common divisior, this would make the inequality
|b|≤ M even truer).

B. Schnirelmann’s Theorem. If S is a set of integers with positive
Schnirelmann density and 0 ∈ S, then every non-negative integer is
the sum of at most k members of S for some k ≥ 1.

Lemma 1. Let S have density α and 0 ∈ S. Then S ⊕ S has density
2
at least 2α − α .
Proof. AllthegapsinthesetS arecoveredinpartbythetranslation
of S by the term of S just before this gap. Hence, at least the fraction
α of this gap gets covered. So from this covering we have density α
from S itself and α times the gaps. Altogether, then, we indeed have
2
α + αà 1 − αð 2α − α , as claimed.

Lemma 2. If S has density α> 1 , then S ⊕ S contains all the
2
positive integers.

Proof. Fix an integer n which is arbitrary, let A be the subset of
S which lies ≤ n, and let B be the set of all n minus elements of
S. Since A contains more than n/2 elements and B contains at least
n/2 elements, the Pigeonhole principle guarantees that they overlap.
So suppose they overlap at k. Since k ∈ A,weget k ∈ S, and since