Schnirelmann density

Template:Short description 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 Lev Schnirelmann, who was the first to study it.<ref name=Schnirelmann1>Schnirelmann, L.G. (1930). "On the additive properties of numbers", first published in "Proceedings of the Don Polytechnic Institute in Novocherkassk" (in Russian), vol XIV (1930), pp. 3-27, and reprinted in "Uspekhi Matematicheskikh Nauk" (in Russian), 1939, no. 6, 9–25.</ref><ref name=Schnirelmann2>Schnirelmann, L.G. (1933). First published as "Über additive Eigenschaften von Zahlen" in "Mathematische Annalen" (in German), vol 107 (1933), 649-690, and reprinted as "On the additive properties of numbers" in "Uspekhin. Matematicheskikh Nauk" (in Russian), 1940, no. 7, 7–46.</ref>

Definition

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

<math>\sigma A = \inf_n \frac{A(n)}{n},</math>

where A(n) denotes the number of elements of A not exceeding n and inf is infimum.<ref name=N961912>Nathanson (1996) pp.191–192</ref>

The Schnirelmann density is well-defined even if the limit of A(n)/n as Template:Nowrap fails to exist (see upper and lower asymptotic density).

Properties

By definition, Template:Nowrap and Template:Nowrap for all n, and therefore Template:Nowrap, and Template:Nowrap if and only if Template:Nowrap. Furthermore,

<math>\sigma A=0 \Rightarrow \forall \epsilon>0\ \exists n\ A(n) < \epsilon n.</math>

Sensitivity

The Schnirelmann density is sensitive to the first values of a set:

<math>\forall k \ k \notin A \Rightarrow \sigma A \le 1-1/k</math>.

In particular,

<math>1 \notin A \Rightarrow \sigma A = 0</math>

and

<math>2 \notin A \Rightarrow \sigma A \le \frac{1}{2}.</math>

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.

Schnirelmann's theorems

If we set <math>\mathfrak{G}^2 = \{k^2\}_{k=1}^{\infty}</math>, then Lagrange's four-square theorem can be restated as <math> \sigma(\mathfrak{G}^2 \oplus \mathfrak{G}^2 \oplus \mathfrak{G}^2 \oplus \mathfrak{G}^2) = 1</math>. (Here the symbol <math>A\oplus B</math> denotes the sumset of <math>A\cup\{0\}</math> and <math>B\cup\{0\}</math>.) It is clear that <math> \sigma \mathfrak{G}^2 = 0</math>. In fact, we still have <math> \sigma(\mathfrak{G}^2 \oplus \mathfrak{G}^2) = 0</math>, and one might ask at what point the sumset attains Schnirelmann density 1 and how does it increase. It actually is the case that <math> \sigma(\mathfrak{G}^2 \oplus \mathfrak{G}^2 \oplus \mathfrak{G}^2) = 5/6</math> and one sees that sumsetting <math>\mathfrak{G}^2</math> once again yields a more populous set, namely all of <math>\N</math>. 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 <math>A</math> and <math>B</math> be subsets of <math>\N</math>. Then

<math>\sigma(A \oplus B) \ge \sigma A + \sigma B - \sigma A \cdot \sigma B.</math>

Note that <math>\sigma A + \sigma B - \sigma A \cdot \sigma B = 1 - (1 - \sigma A)(1 - \sigma B)</math>. Inductively, we have the following generalization.

Corollary. Let <math>A_i \subseteq \N</math> be a finite family of subsets of <math>\N</math>. Then

<math>\sigma\left(\bigoplus_i A_i\right) \ge 1 - \prod_{i}\left(1 - \sigma A_i\right).</math>

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

Theorem. Let <math>A</math> and <math>B</math> be subsets of <math>\N</math>. If <math>\sigma A + \sigma B \ge 1</math>, then

<math>A \oplus B = \N.</math>

Theorem. (Schnirelmann) Let <math>A \subseteq \N</math>. If <math>\sigma A > 0</math> then there exists <math>k</math> such that

<math>\bigoplus^k_{i=1} A=\N.</math>

Additive bases

A subset <math>A \subseteq \N</math> with the property that <math>A \oplus A \oplus \cdots \oplus A = \N</math> for a finite sum, is called an additive basis, and the least number of summands required is called the degree (sometimes order) 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 <math>\mathfrak{G}^2 = \{k^2\}_{k=1}^{\infty}</math> is an additive basis of degree 4. (About an open problem for additive bases, see Erdős–Turán conjecture on additive bases.)

Mann's theorem

Historically the theorems above were pointers to the following result, at one time known as the <math>\alpha + \beta</math> hypothesis. It was used by Edmund Landau and was finally proved by Henry Mann in 1942.

Theorem. Template:Harv Let <math>A</math> and <math>B</math> be subsets of <math>\N</math>. In case that <math>A \oplus B \ne \N</math>, we still have

<math>\sigma(A \oplus B) \ge \sigma A + \sigma B.</math>

An analogue of this theorem for lower asymptotic density was obtained by Kneser.<ref>Nathanson (1990) p.397</ref> At a later date, E. Artin and P. Scherk simplified the proof of Mann's theorem.<ref>E. Artin and P. Scherk (1943) On the sums of two sets of integers, Ann. of Math 44, page=138-142.</ref>

Waring's problem

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

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

<math> x_1^k + x_2^k + \cdots + x_N^k = n</math>

and <math> R_N^k(n)</math> to be the number of non-negative integral solutions to the inequality

<math> 0 \le x_1^k + x_2^k + \cdots + x_N^k \le n,</math>

in the variables <math> x_i</math>, respectively. Thus <math> R_N^k(n) = \sum_{i=0}^n r_N^k(i)</math>. We have

• <math> r_N^k(n)>0 \leftrightarrow n \in N\mathfrak{G}^k, </math>
• <math> R_N^k(n) \ge \left(\frac{n}{N}\right)^{\frac{N}{k}}.</math>

The volume of the <math>N</math>-dimensional body defined by <math> 0 \le x_1^k + x_2^k + \cdots + x_N^k \le n</math>, is bounded by the volume of the hypercube of size <math> n^{1/k}</math>, hence <math>R_N^k(n) = \sum_{i=0}^n r_N^k(i) \leq n^{N/k}</math>. The hard part is to show that this bound still works on the average, i.e.,

Lemma. (Linnik) For all <math>k \in \N</math> there exists <math>N \in \N</math> and a constant <math>c = c(k)</math>, depending only on <math>k</math>, such that for all <math>n \in \N</math>,

<math>r_N^k(m) < cn^{\frac{N}{k}-1}</math>

for all <math>0 \le m \le n.</math>

With this at hand, the following theorem can be elegantly proved.

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

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

Corollary. Template:Harv For all <math>k</math> there exists <math>N</math>, depending only on <math>k</math>, such that every positive integer <math>n</math> can be expressed as the sum of at most <math>N</math> many <math>k</math>-th powers.

Schnirelmann's constant

In 1930 Schnirelmann used these ideas in conjunction with the Brun sieve to prove Schnirelmann's theorem,<ref name=Schnirelmann1/><ref name=Schnirelmann2/> that any natural number greater than 1 can be written as the sum of not more than C prime numbers, where C is an effectively computable constant:<ref name=N96208>Nathanson (1996) p.208</ref> Schnirelmann obtained C < 800000.<ref>Gelfond & Linnik (1966) p.136</ref> Schnirelmann's constant is the lowest number C with this property.<ref name=N96208/>

Olivier Ramaré showed in Template:Harv that Schnirelmann's constant is at most 7,<ref name=N96208/> 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.<ref name=N96208/>

In 2013, Harald Helfgott proved Goldbach's weak conjecture for all odd numbers. Therefore, Schnirelmann's constant is at most 4.<ref>Template:Cite arXiv</ref><ref>Template:Cite arXiv</ref><ref>Template:Cite arXiv</ref><ref>Template:Cite arXiv</ref>

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:

<math>\sigma(A+\mathfrak{G}^2)>\sigma(A)\text{ for }0<\sigma(A)<1.</math>

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

<math>\sigma(A+B)\geq \alpha+ \frac{\alpha(1-\alpha)}{2k}\,,</math><ref name=Rus177>Ruzsa (2009) p.177</ref>

and this was improved by Plünnecke to

<math>\sigma(A+B)\geq \alpha^{1-\frac{1}{k}}\ . </math><ref name=Rus179>Ruzsa (2009) p.179</ref>

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<ref>Template:Cite journal</ref> as he constructed an essential component that has x^o(1) elements less than x. More precisely, the sequence has

<math>e^{(\log x)^c}</math>

elements less than x for some c < 1. This was improved by E. Wirsing to

<math>e^{\sqrt{\log x}\log\log x}.</math>

For a while, it remained an open problem how many elements an essential component must have. Finally, Ruzsa determined that for every ε > 0 there is an essential component which has at most c(log x)^1+ε elements up to x, but there is no essential component which has c(log x)^1+o(1) elements up to x.<ref> Imre Z. Ruzsa, Essential Components, Proceedings of the London Mathematical Society, Volume s3-54, Issue 1, January 1987, Pages 38–56, https://doi.org/10.1112/plms/s3-54.1.38 01 January 1987</ref><ref name=Rus184>Ruzsa (2009) p.184</ref>

References

• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite book Has a proof of Mann's theorem and the Schnirelmann-density proof of Waring's conjecture.
• Template:Cite journal
• Template:Cite book
• Template:Cite book