- Schnirelmann density
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.
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).
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,
The Schnirelmann density is sensitive to the first values of a set:
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.
If we set , then Lagrange's four-square theorem can be restated as . (Here the symbol denotes the sumset of and .) It is clear that . In fact, we still have , and one might ask at what point the sumset attains Schnirelmann density 1 and how does it increase. It actually is the case that and one sees that sumsetting once again yields a more populous set, namely all of . 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 . Then
Note that . Inductively, we have the following generalization.
Corollary. Let be a finite family of subsets of . Then
The theorem provides the first insights on how sumsets accumulate. It seems unfortunate that its conclusion stops short of showing σ 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 . If , then
Theorem. (Schnirelmann) Let . If σA > 0 then there exists k such that
A subset with the property that 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 is an additive basis of degree 4.
Historically the theorems above were pointers to the following result, at one time known as the α + β hypothesis. It was used by Edmund Landau and was finally proved by Henry Mann in 1942.
Theorem. (Mann 1942) Let A and B be subsets of . In case that , we still have
Let k and N be natural numbers. Let . Define to be the number of non-negative integral solutions to the equation
and to be the number of non-negative integral solutions to the inequality
in the variables xi, respectively. Thus . We have
The volume of the N-dimensional body defined by , is bounded by the volume of the hypercube of size n1 / k, hence . The hard part is to show that this bound still works on the average, i.e.,
Lemma. (Linnik) For all there exists and a constant c = c(k), depending only on k, such that for all ,
With this at hand, the following theorem can be elegantly proved.
Theorem. For all k there exists N for which .
We have thus established the general solution to Waring's Problem:
Corollary. (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 1931 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's constant is the lowest number C with this property.
Schnirelmann's constant is at least 3; Goldbach's conjecture implies that this is the constant's actual value.
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
Sequences with this property 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.
- Hilbert, David (1909). "Beweis für die Darstellbarkeit der ganzen Zahlen durch eine feste Anzahl nter Potenzen (Waringsches Problem)". Mathematische Annalen 67 (3): 281–300. doi:10.1007/BF01450405. ISSN 0025-5831. MR1511530
- Schnirelmann, L.G. (1933). "Über additive Eigenschaften von Zahlen" (in German). Math. Ann. 107: 649–690. doi:10.1007/BF01448914.
- Mann, Henry B. (1942). "A proof of the fundamental theorem on the density of sums of sets of positive integers". Annals of Mathematics. Second Series (Annals of Mathematics) 43 (3): 523–527. doi:10.2307/1968807. ISSN 0003-486X. JSTOR 1968807. MR0006748
- Mann, Henry B. (1976). Addition Theorems: The Addition Theorems of Group Theory and Number Theory (Corrected reprint of 1965 Wiley ed.). Huntington, New York: Robert E. Krieger Publishing Company. ISBN 0-88275-418-1. MR424744.
- Ramaré, O. (1995). "On Šnirel'man's constant". Annali della Scuola Normale Superiore di Pisa. Classe di Scienze. Serie IV 22 (4): 645–706. http://www.numdam.org/item?id=ASNSP_1995_4_22_4_645_0. Retrieved 2011-03-28.
- Nathanson, Melvyn B. (1996). Additive Number Theory: the Classical Bases. Graduate Texts in Mathematics. 164. Springer-Verlag. p. 192. ISBN 0-387-94656-X.
- Khinchin, A. Ya. (1998). Three Pearls of Number Theory. Mineola, NY: Dover. ISBN 978-0486400266 Has a proof of Mann's theorem and the Schnirelmann-density proof of Waring's conjecture.
- Cojocaru, Alina Carmen; Murty, M. Ram (2005). An introduction to sieve methods and their applications. London Mathematical Society Student Texts. 66. Cambridge University Press. pp. 100–105. ISBN 0-521-61275-6.
Wikimedia Foundation. 2010.
Look at other dictionaries:
Density (disambiguation) — Density and dense usually refer to a measure of how much of some entity is within a fixed amount of space. Types of density include: In physics, density of mass: Density, mass per volume Area density or surface density, mass over a (two… … Wikipedia
Densité de Schnirelmann — Pour les articles homonymes, voir Densité (homonymie). En mathématiques, la densité de Schnirelmann d un ensemble d entiers naturels non nuls est un nombre qui mesure de quelle façon cet ensemble est « dense » . Elle a été nommée en l… … Wikipédia en Français
Densite de Schnirelmann — Densité de Schnirelmann En mathématiques, la densité de Schnirelmann d une suite de nombres est une manière de mesurer de quelle façon la suite est « dense ». Elle a été nommée en l honneur du mathématicien russe L.G. Schnirelmann, qui… … Wikipédia en Français
Lev Schnirelmann — Lev Genrikhovich Schnirelmann ( ru. Лев Генрихович Шнирельман), also Shnirelman, Shnirel man (born January 2, 1905 in Gomel, died September 24, 1938 in Moscow) was a Soviet mathematician who sought to prove Goldbach s conjecture. In 1931, using… … Wikipedia
Natural density — In number theory, asymptotic density (or natural density or arithmetic density) is one of the possibilities to measure how large a subset of the set of natural numbers is. Intuitively, we think that there are more positive integers than perfect… … Wikipedia
List of Russian mathematicians — Andrey Kolmogorov, a preeminent 20th century mathematician. This list of Russian mathematicians includes the famous mathematicians from the Russian Empire, the Soviet Union and the Russian Federation. This list is incomplete; you can help by … Wikipedia
List of Russian people — The Millennium of Russia monument in Veliky Novgorod, featuring the statues and reliefs of the most celebrated people in the first 1000 years of Russian history … Wikipedia
Artin's conjecture on primitive roots — In mathematics, the Artin conjecture is a conjecture on the set of primes p modulo which a given integer a > 1 is a primitive root. The conjecture was made by Emil Artin to Helmut Hasse on September 27, 1927, according to the latter s diary.The… … Wikipedia
List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… … Wikipedia
List of exceptional set concepts — This is a list of exceptional set concepts. In mathematics, and in particular in mathematical analysis, it is very useful to be able to characterise subsets of a given set X as small , in some definite sense, or large if their complement in X is… … Wikipedia