# Monthly Archives: August 2014

## Writing Natural Numbers as Sums of Primes

The prime numbers are defined in terms of the multiplicative structure of the natural numbers, $$\mathbf{N}$$. Specifically, the definition of prime–that $$p \in \mathbf{N}$$ is prime if it has no non-trivial divisors–only refers to multiplication, not addition. The additive structure of the prime numbers is much less well understood, and indeed, many of the most famous open problems and deepest theorems in number theory concern the additive structure of the primes. For example, see the twin primes conjecture, the Goldbach conjecture, the abc conjecture, and the Green-Tao theorem. In this post, we consider a much weaker variant of the Goldbach Conjecture:

Theorem 1. Every natural number $$m$$ with $$1 < m < 2^{n + 1}$$ can be written as a sum of at most $$n$$ primes. Before giving a rigorous proof of Theorem 1, we give the following intuitive motivation. Suppose we were asked to find relatively few primes $$p_1, p_2, \ldots, p_k$$ whose sum is $$m$$. A reasonable way to proceed would be to find, say, the largest prime $$p_1 < m - 1$$. Then taking $$m_1 = m - p_1$$, we need only find primes $$p_2, \ldots, p_k$$ whose sum is $$m_1$$. Thus, we have reduced the problem of writing $$m$$ as a sum of primes to writing the strictly smaller $$m_1$$ as a sum of primes. Iterating this procedure, we will eventually find $$p_1, p_2, \ldots, p_k$$ with $$m = p_1 + p_2 + \cdots + p_k$$. The only question is how large $$k$$ must be. Theorem suggests that we should be able to always have $$k \leq \lfloor \log_2 (m) \rfloor$$. The key fact that we will use to prove that $$k \leq \lfloor\log_2(m) \rfloor$$ suffices is a statement about the density of the primes: Bertrand’s Postulate.

Bertrand’s Postulate. For every natural number $$m > 1$$ there exists a prime $$p$$ satisfying $$m < p < 2 m$$. Bertrand's Postulate is precisely the key piece we need in order to use the heuristic described above to prove Theorem 1. Indeed, Bertrand's Postulate shows that the prime $$p_1$$ satisfies $$p_1 > (m – 1) / 2$$. Thus, $$m_1 = m – p_1 \leq m / 2$$. Since each iteration of our procedure for finding $$p_1, \ldots, p_k$$ cuts the size of the problem in half, the process should terminate after $$\log_2 m$$ iterations. We are now ready to formalize this intuition with a proof.

Proof of Theorem 1. We argue by induction on $$n$$. For the base case, $$n = 1$$, the only natural numbers $$m$$ with $$1 < m < 2^{n+1}$$ are $$m = 2, 3$$. Since both of these numbers are prime, the theorem holds. For the inductive step, suppose Theorem 1 holds for some fixed $$n > 1$$. We will show that Theorem 1 also holds for $$n+1$$. Suppose $$m$$ satisfies $$1 < m < 2^{n + 2}$$. Let $$p_1$$ be the largest prime with $$p_1 < m - 1$$. By Bertrand's Postulate, $$p_1 > (m – 1) / 2$$, thus $$m_1 = m – p_1$$ satisfies $$m_1 < 2^{n + 1}$$. By the inductive hypothesis, $$m_1$$ is the sum of primes $$m_1 = p_2 + p_3 + \cdots + p_k$$ with $$k \leq n + 1$$. Thus, $$m = p_1 + m_1 = p_1 + p_2 + \cdots p_k$$ is the sum of at most $$n + 1$$ primes, as desired. ∎