# Schnirelmann density

In mathematics, the Schnirelmann density of a sequence of numbers is a way to measure how "dense" the sequence is. It is named after Russian mathematician L.G. Schnirelmann, who was the first to study it.

Intuitively, we feel that there are "more" odd numbers than perfect squares; however, the set of odd numbers is not in fact "bigger" than the set of perfect squares: both sets are infinite and countable and can therefore be put in one-one correspondence. Clearly, we need a better way to formalize our intuitive notion. This is what the Schnirelmann density does.

## Definition

The Schnirelmann density of a set of natural numbers is defined as follows

Definition. Let ${\displaystyle A\subseteq \mathbb {N} }$. We write ${\displaystyle A(n)}$ to denote ${\displaystyle \#(A\cap \{1,2,\ldots n\})}$, the number of elements of ${\displaystyle A}$ not exceeding ${\displaystyle n}$. The Schnirelmann natural density of ${\displaystyle A}$ is defined as:

${\displaystyle \sigma A=\inf _{n}{\frac {A(n)}{n}}}$

Here inf is infimum.

This definition resolves the obvious problem with simply defining the density as the limit of ${\displaystyle A(n)/n}$ as ${\displaystyle n\to \infty }$, which might not exist (see asymptotic density). The Schnirelmann density, on the other hand, is always defined.

## Properties

The Schnirelmann density function ${\displaystyle \sigma }$ has the following properties. For ${\displaystyle A\subseteq \mathbb {N} }$

1. ${\displaystyle 0\leq \sigma A\leq 1}$
2. ${\displaystyle \forall n\ A(n)\geq n\sigma A}$
3. ${\displaystyle \sigma A=1\leftrightarrow A=\mathbb {N} }$
4. ${\displaystyle 1\notin A\rightarrow \sigma A=0}$
5. ${\displaystyle \sigma A=0\rightarrow \forall \epsilon >0\ \exists n\ A(n)<\epsilon n}$

One might wonder what is the utility of such a density function, if it is extremely sensitive to the first values of a set. Schnirelmann and Linnik exploited this as we shall see.

## Schnirelmann's theorems

If we set ${\displaystyle {\mathfrak {G}}^{2}=\{k^{2}\}_{k=1}^{\infty }}$, then Lagrange's four-square theorem can be restated as ${\displaystyle \sigma ({\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2})=1}$. (The symbol ${\displaystyle A\oplus B}$ denotes the sumset of ${\displaystyle A}$ and ${\displaystyle B}$.) It is clear that ${\displaystyle \sigma {\mathfrak {G}}^{2}=0}$. In fact, we still have ${\displaystyle \sigma ({\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2})=0}$, and one might ask at what point the sumset attains Schnirelmann density 1 and how does it increase. It actually is the case that ${\displaystyle \sigma ({\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2}\oplus {\mathfrak {G}}^{2})=5/6}$ and one sees that sumsetting ${\displaystyle {\mathfrak {G}}^{2}}$ once again yields a more populous set, namely all of ${\displaystyle \mathbb {N} }$. Schnirelmann further succeeded in developing these ideas into the following theorems, aiming towards Additive Number Theory, and proving them to be a novel resource (if not greatly powerful) to attack important problems, such as Waring's problem and Goldbach's conjecture.

Theorem. Let ${\displaystyle A}$ and ${\displaystyle B}$ be subsets of ${\displaystyle \mathbb {N} }$. Then

${\displaystyle \sigma (A\oplus B)\geq \sigma A+\sigma B-\sigma A\cdot \sigma B}$

Note that ${\displaystyle \sigma A+\sigma B-\sigma A\cdot \sigma B=1-(1-\sigma A)(1-\sigma B)}$. Inductively, we have the following generalization.

Corollary. Let ${\displaystyle A_{i}\subseteq \mathbb {N} }$ be a finite family of subsets of ${\displaystyle \mathbb {N} }$. Then

${\displaystyle \sigma (\bigoplus _{i}A_{i})\geq 1-\prod _{i}(1-\sigma A_{i})}$

The theorem provides the first insights on the how sumsets accumulate. It seems unfortunate that its conclusion stops short of showing ${\displaystyle \sigma }$ being superadditive. Yet, Schnirelmann provided us with the following results, which sufficed for most of his purpose.

Theorem. Let ${\displaystyle A}$ and ${\displaystyle B}$ be subsets of ${\displaystyle \mathbb {N} }$. If ${\displaystyle \sigma A+\sigma B\geq 1}$, then

${\displaystyle A\oplus B=\mathbb {N} }$

Theorem. (Schnirelmann) Let ${\displaystyle A\subseteq \mathbb {N} }$. If ${\displaystyle \sigma A>0}$ then there exists ${\displaystyle k}$ such that

${\displaystyle \bigoplus _{i=1}^{k}A=\mathbb {N} }$

A subset ${\displaystyle A\subseteq \mathbb {N} }$ with the property that ${\displaystyle A\oplus A\oplus \cdots \oplus A=\mathbb {N} }$ for a finite sum, is called an additive basis, and the least number of summands required is called the degree of the basis. Thus, the last theorem states that any set with positive Schnirelmann density is an additive basis. In this terminology, the set of squares ${\displaystyle {\mathfrak {G}}^{2}=\{k^{2}\}_{k=1}^{\infty }}$ is an additive basis of degree 4.

## Mann's theorem

Historically, the theorems above were pointers to the following result, which the best possible refinement of Theorem 1, and proved to be difficult to attack. It became known as the ${\displaystyle \alpha +\beta }$ hypothesis, used by Landau in the proof of Theorem 1.1 and finally proved by Mann in 1942.

Theorem. (Mann, 1942) Let ${\displaystyle A}$ and ${\displaystyle B}$ be subsets of ${\displaystyle \mathbb {N} }$. In case that ${\displaystyle A\oplus B\neq \mathbb {N} }$, we still have

${\displaystyle \sigma (A\oplus B)\geq \sigma A+\sigma B}$

## Waring's problem

Let ${\displaystyle k}$ and ${\displaystyle N}$ be natural numbers. Let ${\displaystyle {\mathfrak {G}}^{k}=\{i^{k}\}_{i=1}^{\infty }}$. Define ${\displaystyle r_{N}^{k}(n)}$ to be the number of non-negative integral solutions to the equation

${\displaystyle x_{1}^{k}+x_{2}^{k}+\cdots +x_{N}^{k}=n\,}$

and ${\displaystyle R_{N}^{k}(n)}$ to be the number of non-negative integral solutions to the inequality

${\displaystyle 0\leq x_{1}^{k}+x_{2}^{k}+\cdots +x_{N}^{k}\leq n,\,}$

in the variables ${\displaystyle x_{i}}$, respectively. Thus ${\displaystyle R_{N}^{k}(n)=\sum _{i=0}^{n}r_{N}^{k}(i)}$. We have

• ${\displaystyle r_{N}^{k}(n)\leftrightarrow n\in N{\mathfrak {G}}^{k},}$
• ${\displaystyle R_{N}^{k}(n)\geq \left({\frac {n}{N}}\right)^{\frac {N}{k}}.}$

The volume of the ${\displaystyle N}$-dimensional body defined by ${\displaystyle 0\leq x_{1}^{k}+x_{2}^{k}+\cdots +x_{N}^{k}\leq n}$, is bounded by the volume of the hypercube of size ${\displaystyle n^{1/k}}$, hence ${\displaystyle R_{N}^{k}(n)=\sum _{i=0}^{n}r_{N}^{k}(i)=n^{N/k}}$. The hard part is to show that this bound still works on the average, i.e.,

Lemma. (Linnik) For all ${\displaystyle k\in \mathbb {N} }$ there exists ${\displaystyle N\in \mathbb {N} }$ and a constant ${\displaystyle c=c(n)}$, depending only on ${\displaystyle k}$, such that for all ${\displaystyle n\in \mathbb {N} }$,

${\displaystyle r_{N}^{k}(m)

for all ${\displaystyle 0\leq m\leq n.\,}$

With this at hand, the following theorem can be elegantly proved. (The reader is invited to give a proof of this...)

Theorem. For all ${\displaystyle k}$ there exists ${\displaystyle N}$ for which ${\displaystyle \sigma (N{\mathfrak {G}}^{k})>0}$.

We have thus established the general solution to Waring's Problem:

Corollary. (Hilbert, 1909) For all ${\displaystyle k}$ there exists ${\displaystyle N}$, depending only on ${\displaystyle k}$, such that every positive integer ${\displaystyle n}$ can be expressed as the sum of at most ${\displaystyle N}$ many ${\displaystyle k}$-th powers.