Aleksandr Ya. Khinchin’s clear and engaging style displays Three Pearls of Number Theory in the best possible light. In this 1945 letter sent to a former student, he carefully explains how to use elementary techniques in clever ways to prove Van Der Waerden’s theorem on arithmetic progressions, Mann’s theorem, and Waring’s problem. These proofs showcase how creativity in establishing new definitions and operations can yield powerful results, without necessarily having to resort to heavy abstraction.

Given the age of Khinchin’s letter and the fact that the wikipedia page on the entire subfield he introduces is little more than a stub, one might be happily surprised to discover that the underlying ideas have actually been modernized and expanded under the new name of additive combinatorics. In fact, Terence Tao and Van H. Vu’s Additive Combinatorics textbook even includes two exercises, 5.1.6 and 5.1.7, on the Schnirelmann density, a key concept in Khinchin’s letter.

We wanted to look into these problems here for old time’s sake. Problem 5.1.7, which asks us to prove the Schnirelmann inequality, was historically the first of the two to be solved. Problem 5.1.6 is a sharper version of this inequality that was conjectured by Landau and Schnirelmann and proved by Mann and is typically known as Mann’s theorem. In this book we are actually given a slightly differently-stated version of Mann’s theorem and asked in this exercise to derive some corollaries including this inequality.

In this post we state and then prove 5.1.6., which culminates in proving that every set of integers of positive Schnirelmann density that contains 0 is a basis for the positive integers.

Brief notational interlude

We will simplify some of the notation used in the textbook: $|A \cap [1,n]|$ is the counting function denoted $A(n)$ in traditional texts. In plain English it means the number of positive elements of $A$ not exceeding $n$. We also replace $|[1,n]|$ by its value $n$.

That gives the definition of Schnirelmann density as:

$$ \sigma(A) = \inf_{n > 0} \frac{A(n)}{n} $$

Part 1: overview

The first part of the problem asks us to show that if $A$ and $B$ are any sets of integers with $0 \in A$ and $0 \in B$, then:

$$ \sigma(A+B) \geq \text{min } (\sigma(A) + \sigma(B), 1) $$

Unpacking the notation, we have to prove this inequality:

$$ \inf_{n > 0} \frac{(A+B)(n)}{n} \geq \text{min} \left(\inf_{n > 0} \frac{A(n)}{n} + \inf_{n > 0} \frac{B(n)}{n}, 1 \right) $$

Note that the maximum value of the left-hand-side (LHS) is 1 and that this occurs only when $A+B \supseteq \mathbb{Z}^{+}$ (that is, when $A+B$ contains all positive integers).

To prove the inequality we are given a version of Mann’s Theorem, which we will call Theorem (1) here:

Theorem 1: If we can fix some $0 < \alpha < 1$ s.t. $A(n) + B(n) \geq \alpha n$, for all $n$ with $n \geq 0$, then $(A+B)(n) \geq \alpha n$, for all $n \geq 0$.

Part 1: proving the first two cases

We will proceed by breaking the problem down into three cases:

  • $\sigma(A) + \sigma(B) = 0$, or
  • $0 < \sigma(A) + \sigma(B) < 1$, or
  • $\sigma(A) + \sigma(B) \geq 1$.

The third case is more complicated than the first two, and will require a more complicated (and more interesting!) approach.

> Case 1

If $\sigma(A) + \sigma(B) = 0$, the right-hand-side (RHS) of the desired inequality to prove is $0$. And since the Schnirelmann density is nonnegative, we have $\sigma(A+B) \geq 0$, proving the inequality $\sigma(A+B) \geq \min(\sigma(A) + \sigma(B), 1)$.

> Case 2

Suppose $0 < \sigma(A) + \sigma(B) < 1$.

By definition of the Schnirelmann density, for all $n > 0$:

$$ \frac{A(n)}{n} \geq \sigma(A), \quad \frac{B(n)}{n} \geq \sigma(B) $$

Adding these inequalities:

$$ \frac{A(n)}{n} + \frac{B(n)}{n} \geq \sigma(A) + \sigma(B) $$
$$ A(n)+B(n) \geq n(\sigma(A)+\sigma(B)) $$

Also, when $n=0$, we trivially have $A(n)=B(n)=0 \geq 0$, so this last inequality holds for all $n \geq 0$.

Since $0 < \sigma(A) + \sigma(B) < 1$, we can take $\alpha = \sigma(A) + \sigma(B)$ and apply Theorem (1), giving us $(A+B)(n) \geq n(\sigma(A) + \sigma(B))$ for all $n \geq 0.$

Therefore $\frac{(A+B)(n)}{n} \geq \sigma(A)+\sigma(B)$ for all $n > 0$. Taking the infimum over all $n > 0$ on the LHS, we get $\sigma(A+B) \geq \sigma(A) + \sigma(B)$.

> Case 3 and a nice counting argument

The third case supposes $\sigma(A) + \sigma(B) \geq 1$. Then the RHS is $1$, and since the Schnirelmann density cannot exceed $1$, we need to prove $\sigma(A+B)=1$.

To resume, the third case asks us to prove the following: if $0 \in A$, $0 \in B$, and $\sigma(A) + \sigma(B) \geq 1$, then $\sigma(A + B) = 1$. That means that we need to prove that the set $A+B$ contains all of the positive integers.

The following proof is taken from Hua Luogeng’s Introduction to Number Theory (theorem 2.2, p. 516 in the 1982 English edition). It sets up a contradiction via counting.

Let $C = A+B$. Suppose for the sake of contradiction that there is a least positive integer $m \notin C$.

If $\sigma(B) = 0$, then since $\sigma(A) + \sigma(B) \geq 1$ in this third case, we have $\sigma(A) = 1$. So $A \supseteq \mathbb{ℤ}^{⁺}$ and $A + B \supseteq \mathbb{ℤ}^{⁺}$, giving $\sigma(A + B) = 1$. So we can assume $\sigma(B) > 0$.

Since $\sigma(B) > 0$ we have $1 \in B$ (otherwise we would have $B(1)=0$, with $\sigma(B) \leq B(1) = 0$). Since $0 \in A$, we have $1 \in C$. Therefore, $m \geq 2$. Since $0 \in A$ we also have $m \notin B$.

Consider natural numbers $a$ and $m-b$ neither of which exceed $m-1$, with $a \in A$ and $b \in B$.

Each $a$ is different from $m - b$ because $a = m-b$ would give $m = a+b$ and contradict $m \notin C$. Since both $a$ and $m-b$ do not exceed $m-1$, there are at most $m-1$ distinct values among all such $a$ and $m-b$.

Let us count these numbers in a different way and arrive at a contradiction. The number of numbers $a$ and $m-b$ is by definition $A(m-1) + B(m-1)$. We know that:

$$ A(m-1) \geq (m-1)\sigma(A) $$

Since $m \notin B$, we have $B(m-1)=B(m)$. We have $B(m) \geq m\sigma(B)$ by definition. And $m\sigma(B) > (m-1)\sigma(B)$, with strict inequality because $\sigma(B)>0$. To summarize this chain of reasoning:

$$ B(m-1) = B(m) \geq m\sigma(B) > (m-1)\sigma(B) $$

So we have:

$$ \begin{align*} A(m-1) + B(m-1) &> (m-1)\sigma(A) + (m-1)\sigma(B) \\ &= (m-1)(\sigma(A) + \sigma(B)) \\ &\geq m-1 \end{align*} $$

This contradicts the claim that the number of numbers $a$ and $m-b$ does not exceed $m-1$, completing our proof.

> A visual example

It might be helpful to see an example that illustrates the double counting argument above. Consider the case $m = 8$:

The counting argument illustrated for m=8

We assumed $m \notin C = A+B$. A collision at slot $s$ would mean $a = s$ and $m - b = s$, so $a + b = m \in C$, giving a contradiction. So the two sets must be disjoint within $\{1, \ldots, m-1\}$. But $A(m-1) + B(m-1) > (m-1)(\sigma(A) + \sigma(B)) \geq m-1$, which means there are too many marks for $m-1$ slots.

Part 2

For part 2, the textbook asks us to show that if $0 \in A$ and $\sigma(A) \geq \frac{1}{k}$ for some integer $k > 0$, then $kA$ contains all of the positive integers.

Note that we can write: $\sigma(1A) \geq \text{min } (1\sigma(A), 1)$.

This leads us to define our inductive hypothesis as:

$$ \sigma(jA) \geq \text{min } (j\sigma(A), 1) $$

We will proceed inductively on $j$ using the theorem we proved in part 1.

For the base case $j = 1$, we need to prove $\sigma(A) \geq \text{min } (\sigma(A), 1)$. Since $\text{min } (\sigma(A), 1) = \sigma(A)$ by definition of density, this is just trivially $\sigma(A) = \sigma(A)$.

We now have to prove the inductive step:

$$ \sigma((j+1)A) \geq \text{min } ((j+1)(\sigma(A)), 1) $$
$$ \sigma(A+jA) \geq \text{min} (\sigma(A)+j\sigma(A), 1) $$

We have $0 \in A$ so $0 \in jA$, so we can apply the result of part 1:

$$ \sigma(A+jA) \geq \text{min } (\sigma(A) + \sigma(jA), 1) $$

We want to apply the inductive hypothesis but to do so we need a case split.

If $j\sigma(A) < 1$, we get by the inductive hypothesis $\sigma(jA) \geq j\sigma(A)$, which we can swap into the inequality we had above:

$$ \sigma(A+jA) \geq \text{min} (\sigma(A) + j\sigma(A), 1) $$

to get the desired result.

Else we have $j\sigma(A) \geq 1$. By the inductive hypothesis $\sigma(jA) \geq \min(j\sigma(A),1)$, and so $\sigma(jA) \geq 1$, so we have $\sigma(A)+\sigma(jA) \geq 1$. So the RHS is $1$. For the LHS, we apply the result we proved in Part 1 Case 3: since $0 \in A$ and $\sigma(A) + \sigma(jA) \geq 1$, then $\sigma(A + jA) = 1$. This completes our proof by induction.

We can now complete Part 2. We are given $0 \in A$ and $\sigma(A) \geq \frac{1}{k}$, so $k\sigma(A) \geq 1$, so we can use what we proved above. So $\sigma(kA) \geq \min(k\sigma(A), 1) = 1$. Therefore $\sigma(kA) = 1$, which means $kA$ contains all of the positive integers.

References

  • Aleksandr Ya. Khinchin, Three Pearls of Number Theory, Graylock Press, Baltimore, 1952, reprinted by Dover Publications, Mineola, 1998.

  • Terence Tao, Van H. Vu, Additive Combinatorics, Cambridge University Press, Cambridge, 2006, https://doi.org/10.1017/CBO9780511755149.

  • Hua Loo Keng [Hua Luogeng], Introduction to Number Theory, Springer-Verlag, Berlin, 1982, https://doi.org/10.1007/978-3-642-68130-1.