In additive number theory, 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.
Contents
- Definition
- Properties
- Sensitivity
- Schnirelmanns theorems
- Additive bases
- Manns theorem
- Warings problem
- Schnirelmanns constant
- Essential components
- References
Definition
The Schnirelmann density of a set of natural numbers A is defined as
where A(n) denotes the number of elements of A not exceeding n and inf is infimum.
The Schnirelmann density is well-defined even if the limit of A(n)/n as n → ∞ fails to exist (see asymptotic density).
Properties
By definition, 0 ≤ A(n) ≤ n and n σA ≤ A(n) for all n, and therefore 0 ≤ σA ≤ 1, and σA = 1 if and only if A = N. Furthermore,
Sensitivity
The Schnirelmann density is sensitive to the first values of a set:
In particular,
and
Consequently, the Schnirelmann densities of the even numbers and the odd numbers, which one might expect to agree, are 0 and 1/2 respectively. Schnirelmann and Yuri Linnik exploited this sensitivity as we shall see.
Schnirelmann's theorems
If we set
Theorem. Let
Note that
Corollary. Let
The theorem provides the first insights on how sumsets accumulate. It seems unfortunate that its conclusion stops short of showing
Theorem. Let
Theorem. (Schnirelmann) Let
Additive bases
A subset
Mann's theorem
Historically the theorems above were pointers to the following result, at one time known as the
Theorem. (Mann 1942) Let
An analogue of this theorem for lower asymptotic density was obtained by Kneser. At a later date, E. Artin and P. Scherk simplified the proof of Mann's theorem.
Waring's problem
Let
and
in the variables
The volume of the
Lemma. (Linnik) For all
for all
With this at hand, the following theorem can be elegantly proved.
Theorem. For all
We have thus established the general solution to Waring's Problem:
Corollary. (Hilbert 1909) For all
Schnirelmann's constant
In 1930 Schnirelmann used these ideas in conjunction with the Brun sieve to prove Schnirelmann's theorem, that any natural number greater than one can be written as the sum of not more than C prime numbers, where C is an effectively computable constant: Schnirelmann obtained C < 800000. Schnirelmann's constant is the lowest number C with this property.
Olivier Ramaré showed in (Ramaré 1995) that Schnirelmann's constant is at most 7, improving the earlier upper bound of 19 obtained by Hans Riesel and R. C. Vaughan.
Schnirelmann's constant is at least 3; Goldbach's conjecture implies that this is the constant's actual value.
Essential components
Khintchin proved that the sequence of squares, though of zero Schnirelmann density, when added to a sequence of Schnirelmann density between 0 and 1, increases the density:
This was soon simplified and extended by Erdős, who showed, that if A is any sequence with Schnirelmann density α and B is an additive basis of order k then
and this was improved by Plünnecke to
Sequences with this property, of increasing density less than one by addition, were named essential components by Khintchin. Linnik showed that an essential component need not be an additive basis as he constructed an essential component that has xo(1) elements less than x. More precisely, the sequence has
elements less than x for some c < 1. This was improved by E. Wirsing to
For a while, it remained an open problem how many elements an essential component must have. Finally, Ruzsa determined that an essential component has at least (log x)c elements up to x, for some c > 1, and for every c > 1 there is an essential component which has at most (log x)c elements up to x.