:Schnirelmann density

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

:$\backslash sigma\; A\; =\; \backslash inf\_n\; \backslash frac\{A(n)\}\{n\},$

where A(n) denotes the number of elements of A not exceeding n and inf is infimum.Nathanson (1996) pp.191–192

The Schnirelmann density is well-defined even if the limit of A(n)/n as {{nowrap|n → ∞}} fails to exist (see upper and lower asymptotic density).

By definition, {{nowrap|0 ≤ A(n) ≤ n}} and {{nowrap|n σA ≤ A(n)}} for all n, and therefore {{nowrap|0 ≤ σA ≤ 1}}, and {{nowrap|σA {{=}} 1}} if and only if {{nowrap|A {{=}} N}}. Furthermore,

:

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

: $\backslash forall\; k\; \backslash \; k\; \backslash notin\; A\; \backslash Rightarrow\; \backslash sigma\; A\; \backslash le\; 1-1/k$.

In particular,

:$1\; \backslash notin\; A\; \backslash Rightarrow\; \backslash sigma\; A\; =\; 0$

and

:$2\; \backslash notin\; A\; \backslash Rightarrow\; \backslash sigma\; A\; \backslash le\; \backslash frac\{1\}\{2\}.$

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.

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

$\backslash sigma(A\; \backslash oplus\; B)\; \backslash ge\; \backslash sigma\; A\; +\; \backslash sigma\; B\; -\; \backslash sigma\; A\; \backslash cdot\; \backslash sigma\; B.$

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

Corollary. Let $A\_i\; \backslash subseteq\; \backslash N$ be a finite family of subsets of $\backslash N$. Then

$\backslash sigma\backslash left(\backslash bigoplus\_i\; A\_i\backslash right)\; \backslash ge\; 1\; -\; \backslash prod\_\{i\}\backslash left(1\; -\; \backslash sigma\; A\_i\backslash right).$

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

Theorem. Let $A$ and $B$ be subsets of $\backslash N$. If $\backslash sigma\; A\; +\; \backslash sigma\; B\; \backslash ge\; 1$, then

$A\; \backslash oplus\; B\; =\; \backslash N.$

Theorem. (Schnirelmann) Let $A\; \backslash subseteq\; \backslash N$. If $\backslash sigma\; A\; >\; 0$ then there exists $k$ such that

$\backslash bigoplus^k\_\{i=1\}\; A=\backslash N.$

A subset $A\; \backslash subseteq\; \backslash N$ with the property that $A\; \backslash oplus\; A\; \backslash oplus\; \backslash cdots\; \backslash oplus\; A\; =\; \backslash N$ 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 $\backslash mathfrak\{G\}^2\; =\; \backslash \{k^2\backslash \}\_\{k=1\}^\{\backslash infty\}$ is an additive basis of degree 4. (About an open problem for additive bases, see Erdős–Turán conjecture on additive bases.)

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

Theorem. {{harv|Mann|1942}} Let $A$ and $B$ be subsets of $\backslash N$. In case that $A\; \backslash oplus\; B\; \backslash ne\; \backslash N$, we still have

$\backslash sigma(A\; \backslash oplus\; B)\; \backslash ge\; \backslash sigma\; A\; +\; \backslash sigma\; B.$

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

{{main|Waring's problem}}

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

:$x\_1^k\; +\; x\_2^k\; +\; \backslash cdots\; +\; x\_N^k\; =\; n$

and $R\_N^k(n)$ to be the number of non-negative integral solutions to the inequality

:$0\; \backslash le\; x\_1^k\; +\; x\_2^k\; +\; \backslash cdots\; +\; x\_N^k\; \backslash le\; n,$

in the variables $x\_i$, respectively. Thus $R\_N^k(n)\; =\; \backslash sum\_\{i=0\}^n\; r\_N^k(i)$. We have

• $r\_N^k(n)>0\; \backslash leftrightarrow\; n\; \backslash in\; N\backslash mathfrak\{G\}^k,$
• $R\_N^k(n)\; \backslash ge\; \backslash left(\backslash frac\{n\}\{N\}\backslash right)^\{\backslash frac\{N\}\{k\}\}.$

The volume of the $N$-dimensional body defined by $0\; \backslash le\; x\_1^k\; +\; x\_2^k\; +\; \backslash cdots\; +\; x\_N^k\; \backslash le\; n$, is bounded by the volume of the hypercube of size $n^\{1/k\}$, hence $R\_N^k(n)\; =\; \backslash sum\_\{i=0\}^n\; r\_N^k(i)\; \backslash leq\; n^\{N/k\}$. The hard part is to show that this bound still works on the average, i.e.,

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

for all $0\; \backslash le\; m\; \backslash le\; n.$

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

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

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

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

In 1930 Schnirelmann used these ideas in conjunction with the Brun sieve to prove Schnirelmann's theorem, 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:Nathanson (1996) p.208 Schnirelmann obtained C < 800000.Gelfond & Linnik (1966) p.136 Schnirelmann's constant is the lowest number C with this property.

Olivier Ramaré showed in {{harv|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.

In 2013, Harald Helfgott proved Goldbach's weak conjecture for all odd numbers. Therefore, Schnirelmann's constant is at most 4.{{cite arXiv |eprint=1305.2897 |title = Major arcs for Goldbach's theorem|last = Helfgott|first = Harald A. |class=math.NT |year=2013}}{{cite arXiv |eprint=1205.5252 |title = Minor arcs for Goldbach's problem |last = Helfgott|first = Harald A.|class=math.NT |year=2012}}{{cite arXiv |eprint=1312.7748 |title = The ternary Goldbach conjecture is true|last = Helfgott|first = Harald A. |class=math.NT |year=2013}}{{cite arXiv | eprint=1501.05438| last=Helfgoot | first=Harald A. | class = math.NT | year = 2015 | title=The ternary Goldbach problem}}

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

: $\backslash sigma(A+B)\backslash geq\; \backslash alpha+\; \backslash frac\{\backslash alpha(1-\backslash alpha)\}\{2k\}\backslash ,,$Ruzsa (2009) p.177

and this was improved by Plünnecke to

:$\backslash sigma(A+B)\backslash geq\; \backslash alpha^\{1-\backslash frac\{1\}\{k\}\}\backslash \; .$Ruzsa (2009) p.179

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{{cite journal | first=Yu. V. | last=Linnik | authorlink=Yuri Linnik | title=On Erdõs's theorem on the addition of numerical sequences | journal=Mat. Sb. | volume=10 | year=1942 | pages=67–78 | zbl=0063.03574 }} as he constructed an essential component that has x^o(1) elements less than x. More precisely, the sequence has

: $e^\{(\backslash log\; x)^c\}$

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

: $e^\{\backslash sqrt\{\backslash log\; x\}\backslash log\backslash log\; x\}.$

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. Imre Z. Ruzsa, [https://academic.oup.com/plms/article-abstract/s3-54/1/38/1440975 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 1987Ruzsa (2009) p.184

{{reflist}}

• {{Cite journal | last1=Hilbert | first1=David | author1-link=David Hilbert | title=Beweis für die Darstellbarkeit der ganzen Zahlen durch eine feste Anzahl nter Potenzen (Waringsches Problem) | doi=10.1007/BF01450405 | mr=1511530 | year=1909 | journal=Mathematische Annalen | issn=0025-5831 | volume=67 | issue=3 | pages=281–300 | s2cid=179177986 | url=https://zenodo.org/record/1428266 }}
• {{cite journal | first=L.G. | last=Schnirelmann | authorlink=Lev Schnirelmann | title=On additive properties of numbers | language=Russian | journal=Ann. Inst. Polytechn. Novočerkassk | volume=14 | pages=3–28 | year=1930 |jfm= 56.0892.02 }}
• {{cite journal | first=L.G. |last=Schnirelmann | authorlink=Lev Schnirelmann | title=Über additive Eigenschaften von Zahlen | language=German | journal=Math. Ann. | volume=107 | pages=649–690 | year=1933 | doi=10.1007/BF01448914 | zbl=0006.10402 |s2cid=123067485 }}
• {{Cite journal |last=Mann |first=Henry B.| authorlink=Henry Mann| title=A proof of the fundamental theorem on the density of sums of sets of positive integers | doi=10.2307/1968807 | mr=0006748 | year=1942 | journal=Annals of Mathematics | series = Second Series | issn=0003-486X | volume=43 | pages=523–527 | issue=3 | jstor=1968807 | zbl=0061.07406 }}
• {{cite book | first1=A.O. | last1=Gelfond | authorlink1=Alexander Gelfond | first2=Yu. V. | last2=Linnik | authorlink2=Yuri Linnik | title=Elementary Methods in Analytic Number Theory | publisher=George Allen & Unwin | year=1966 | editor=L.J. Mordell | editor-link=Louis J. Mordell }}
• {{cite book |last=Mann |first=Henry B. |authorlink=Henry Mann |title=Addition Theorems: The Addition Theorems of Group Theory and Number Theory

|publisher= Robert E. Krieger Publishing Company

|location=Huntington, New York |year=1976 |edition=Corrected reprint of 1965 Wiley |isbn=978-0-88275-418-5 |mr=424744 }}

• {{cite book | zbl=0722.11007 | last=Nathanson | first=Melvyn B. | chapter=Best possible results on the density of sumsets | pages=395–403 | editor1-last=Berndt | editor1-first=Bruce C. | editor1-link=Bruce C. Berndt | editor2-last=Diamond | editor2-first=Harold G. | editor3-last=Halberstam | editor3-first=Heini | editor3-link=Heini Halberstam |display-editors = 3 | editor4-last=Hildebrand | editor4-first=Adolf | title=Analytic number theory. Proceedings of a conference in honor of Paul T. Bateman, held on April 25-27, 1989, at the University of Illinois, Urbana, IL (USA) | series=Progress in Mathematics | volume=85 | location=Boston | publisher=Birkhäuser | year=1990 | isbn=978-0-8176-3481-0 }}
• {{cite journal | first=O. | last=Ramaré | authorlink=Olivier Ramaré | title=On Šnirel'man's constant | journal=Annali della Scuola Normale Superiore di Pisa. Classe di Scienze. Serie IV | volume=22 | year=1995 | issue=4 | pages=645–706 | url = http://www.numdam.org/item?id=ASNSP_1995_4_22_4_645_0 | access-date = 2011-03-28 | zbl=0851.11057 }}
• {{cite book | title=Additive Number Theory: the Classical Bases | volume=164 | series=Graduate Texts in Mathematics | first=Melvyn B. | last=Nathanson | publisher=Springer-Verlag | year=1996 | isbn=978-0-387-94656-6 | zbl=0859.11002 }}
• {{cite book | first=Melvyn B. | last=Nathanson | title=Elementary Methods in Number Theory | volume=195 | series=Graduate Texts in Mathematics | publisher=Springer-Verlag | year=2000 | isbn=978-0-387-98912-9 | zbl=0953.11002 | pages=359–367 }}
• {{Cite book | author1-link = Aleksandr Khinchin | last1 = Khinchin | first1 = A. Ya. | title = Three Pearls of Number Theory | publisher = Dover | location = Mineola, NY | date = 1998 | isbn = 978-0-486-40026-6 }} Has a proof of Mann's theorem and the Schnirelmann-density proof of Waring's conjecture.
• {{cite journal | first1=Emil | last1=Artin |author1-link=Emil Artin| first2=Peter | last2=Scherk | title=On the sum of two sets of integers | year=1943 | journal=Annals of Mathematics | volume=44 | issue=2 | pages=138–142|doi=10.2307/1968760|jstor=1968760 }}
• {{cite book | first1=Alina Carmen | last1=Cojocaru|author1-link= Alina Carmen Cojocaru | first2=M. Ram | last2=Murty | author2-link=M. Ram Murty | title=An introduction to sieve methods and their applications | series=London Mathematical Society Student Texts | volume=66 | publisher=Cambridge University Press | isbn=978-0-521-61275-3 | pages=100–105 | year=2005 }}
• {{cite book | last=Ruzsa | first=Imre Z. | chapter=Sumsets and structure | pages=[https://archive.org/details/combinatorialnum00gero_519/page/n91 87]–210 | editor1-last=Geroldinger | editor1-first=Alfred | editor2-last=Ruzsa | editor2-first=Imre Z. | others=Elsholtz, C.; Freiman, G.; Hamidoune, Y. O.; Hegyvári, N.; Károlyi, G.; Nathanson, M.; Solymosi, J.; Stanchescu, Y. With a foreword by Javier Cilleruelo, Marc Noy and Oriol Serra (Coordinators of the DocCourse) | title=Combinatorial number theory and additive group theory | url=https://archive.org/details/combinatorialnum00gero_519 | url-access=registration | series=Advanced Courses in Mathematics CRM Barcelona | location=Basel | publisher=Birkhäuser | year=2009 | isbn=978-3-7643-8961-1 | zbl=1221.11026 }}

Category:Additive number theory

Category:Mathematical constants