{"history":[],"article":{"id":"3a440ca3-f25f-49ef-9aa4-abf78605a996","title":"Schnirelmann density","slug":"schnirelmann-density","content":":::summary\n:::\n\n# \nIn [additive number theory](https://bliptext.com/articles/additive-number-theory), the **Schnirelmann density** of a [sequence](https://bliptext.com/articles/sequence) of numbers is a way to measure how \"dense\" the [sequence](https://bliptext.com/articles/sequence) is.\nIt is named after [Russian](https://bliptext.com/articles/russia) [mathematician](https://bliptext.com/articles/mathematician) [Lev Schnirelmann](https://bliptext.com/articles/lev-schnirelmann), who was the first to study it.\n\n# Definition\nThe **Schnirelmann density** of a set of [natural numbers](https://bliptext.com/articles/natural-number) A is defined as where A(n) denotes the number of elements of A not exceeding n and inf is [infimum](https://bliptext.com/articles/infimum).\nThe Schnirelmann density is well-defined even if the limit of A(n)/n as n → ∞ fails to exist (see [upper and lower asymptotic density](https://bliptext.com/articles/natural-density)).\n\n# Properties\nBy definition, 0 ≤ A(n) ≤ n and n σA ≤ A(n) for all n, and therefore 0 ≤ σA ≤ 1, and if and only if.\nFurthermore,\n\n## Sensitivity\nThe Schnirelmann density is sensitive to the first values of a set:\nIn particular,\nand\nConsequently, the Schnirelmann densities of the even numbers and the odd numbers, which one might expect to agree, are 0 and 1/2 respectively.\nSchnirelmann and [Yuri Linnik](https://bliptext.com/articles/yuri-linnik) exploited this sensitivity.\n\n# Schnirelmann's theorems\nIf we set, then [Lagrange's four-square theorem](https://bliptext.com/articles/lagrange-s-four-square-theorem) can be restated as.\n(Here the symbol A\\oplus B denotes the [sumset](https://bliptext.com/articles/sumset) of A\\cup\\{0\\} and B\\cup\\{0\\}.) It is clear that.\nIn fact, we still have, and one might ask at what point the sumset attains Schnirelmann density 1 and how does it increase.\nIt actually is the case that and one sees that sumsetting once again yields a more populous set, namely all of \\N.\nSchnirelmann 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](https://bliptext.com/articles/) and [Goldbach's conjecture](https://bliptext.com/articles/).\n

\n**Theorem.** Let A and B be subsets of \\N.\nThen\nNote that.\nInductively, we have the following generalization.\n
\n**Corollary.** Let be a finite family of subsets of \\N.\nThen\nThe theorem provides the first insights on how sumsets accumulate.\nIt seems unfortunate that its conclusion stops short of showing \\sigma being [superadditive](https://bliptext.com/articles/superadditive).\nYet, Schnirelmann provided us with the following results, which sufficed for most of his purpose.\n
\n**Theorem.** Let A and B be subsets of \\N.\nIf, then\n
\n**Theorem.** (Schnirelmann) Let.\nIf then there exists k such that\n\n# Additive bases\nA subset with the property that for a finite sum, is called an [additive basis](https://bliptext.com/articles/additive-basis), and the least number of summands required is called the degree (sometimes order) of the basis.\nThus, the last theorem states that any set with positive Schnirelmann density is an additive basis.\nIn this terminology, the set of squares is an additive basis of degree 4.\n(About an open problem for additive bases, see [Erdős–Turán conjecture on additive bases](https://bliptext.com/articles/erd-s-tur-n-conjecture-on-additive-bases).)\n\n# Mann's theorem\nHistorically the theorems above were pointers to the following result, at one time known as the hypothesis.\nIt was used by [Edmund Landau](https://bliptext.com/articles/edmund-landau) and was finally proved by [Henry Mann](https://bliptext.com/articles/henry-mann) in 1942.\n
\n**Theorem.** Let A and B be subsets of \\N.\nIn case that, we still have\nAn analogue of this theorem for lower asymptotic density was obtained by Kneser.\nAt a later date, [E. Artin](https://bliptext.com/articles/emil-artin) and P. Scherk simplified the proof of Mann's theorem.\n\n# Waring's problem\nLet k and N be natural numbers.\nLet.\nDefine r_N^k(n) to be the number of non-negative integral solutions to the equation\nand R_N^k(n) to be the number of non-negative integral solutions to the inequality\nin the variables x_i, respectively.\nThus.\nWe have\nThe volume of the N-dimensional body defined by, is bounded by the volume of the hypercube of size n^{1/k}, hence.\nThe hard part is to show that this bound still works on the average, i.e.,\n
\n**Lemma.** (Linnik) For all k \\in \\N there exists N \\in \\N and a constant c = c(k), depending only on k, such that for all n \\in \\N,\nfor all\nWith this at hand, the following theorem can be elegantly proved.\n
\n**Theorem.** For all k there exists N for which.\nWe have thus established the general solution to Waring's Problem:\n
\n**Corollary.** 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.\n\n# Schnirelmann's constant\nIn 1930 Schnirelmann used these ideas in conjunction with the [Brun sieve](https://bliptext.com/articles/brun-sieve) to prove **Schnirelmann's theorem**, that any [natural number](https://bliptext.com/articles/natural-number) greater than 1 can be written as the sum of not more than C [prime numbers](https://bliptext.com/articles/prime-numbers), where C is an effectively computable constant: Schnirelmann obtained C < 800000.\n**Schnirelmann's constant** is the lowest number C with this property.\n[Olivier Ramaré](https://bliptext.com/articles/olivier-ramar) showed in that Schnirelmann's constant is at most 7, improving the earlier upper bound of 19 obtained by [Hans Riesel](https://bliptext.com/articles/hans-riesel) and [R. C. Vaughan](https://bliptext.com/articles/robert-charles-vaughan-mathematician).\nSchnirelmann's constant is at least 3; [Goldbach's conjecture](https://bliptext.com/articles/goldbach-s-conjecture) implies that this is the constant's actual value.\nIn 2013, [Harald Helfgott](https://bliptext.com/articles/harald-helfgott) proved Goldbach's weak conjecture for all odd numbers.\nTherefore, Schnirelmann's constant is at most 4.\n\n# Essential components\n[Khintchin](https://bliptext.com/articles/aleksandr-khinchin) 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:\nThis was soon simplified and extended by [Erdős](https://bliptext.com/articles/paul-erd-s), who showed, that if A is any sequence with Schnirelmann density α and B is an additive basis of order k then\nand this was improved by Plünnecke to\nSequences with this property, of increasing density less than one by addition, were named **essential components** by Khintchin.\n[Linnik](https://bliptext.com/articles/yuri-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.\nMore precisely, the sequence has\nelements less than x for some c < 1.\nThis was improved by [E. Wirsing](https://bliptext.com/articles/eduard-wirsing) to\nFor a while, it remained an open problem how many elements an essential component must have.\nFinally, [Ruzsa](https://bliptext.com/articles/imre-z-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.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T19:15:12.118Z","updated_at":"2025-01-25T19:15:12.118Z","search_vector":"'densiti':2 'schnirelmann':1","search_content":" \n \n\n# \nIn [additive number theory](https://bliptext.com/articles/additive-number-theory), the **Schnirelmann density** of a [sequence](https://bliptext.com/articles/sequence) of numbers is a way to measure how \"dense\" the [sequence](https://bliptext.com/articles/sequence) is.\nIt is named after [Russian](https://bliptext.com/articles/russia) [mathematician](https://bliptext.com/articles/mathematician) [Lev Schnirelmann](https://bliptext.com/articles/lev-schnirelmann), who was the first to study it.\n\n# Definition\nThe **Schnirelmann density** of a set of [natural numbers](https://bliptext.com/articles/natural-number) A is defined as where A(n) denotes the number of elements of A not exceeding n and inf is [infimum](https://bliptext.com/articles/infimum).\nThe Schnirelmann density is well-defined even if the limit of A(n)/n as n → ∞ fails to exist (see [upper and lower asymptotic density](https://bliptext.com/articles/natural-density)).\n\n# Properties\nBy definition, 0 ≤ A(n) ≤ n and n σA ≤ A(n) for all n, and therefore 0 ≤ σA ≤ 1, and if and only if.\nFurthermore,\n\n## Sensitivity\nThe Schnirelmann density is sensitive to the first values of a set:\nIn particular,\nand\nConsequently, the Schnirelmann densities of the even numbers and the odd numbers, which one might expect to agree, are 0 and 1/2 respectively.\nSchnirelmann and [Yuri Linnik](https://bliptext.com/articles/yuri-linnik) exploited this sensitivity.\n\n# Schnirelmann's theorems\nIf we set, then [Lagrange's four-square theorem](https://bliptext.com/articles/lagrange-s-four-square-theorem) can be restated as.\n(Here the symbol A\\oplus B denotes the [sumset](https://bliptext.com/articles/sumset) of A\\cup\\{0\\} and B\\cup\\{0\\}.) It is clear that.\nIn fact, we still have, and one might ask at what point the sumset attains Schnirelmann density 1 and how does it increase.\nIt actually is the case that and one sees that sumsetting once again yields a more populous set, namely all of \\N.\nSchnirelmann 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](https://bliptext.com/articles/) and [Goldbach's conjecture](https://bliptext.com/articles/).\n \n**Theorem.** Let A and B be subsets of \\N.\nThen\nNote that.\nInductively, we have the following generalization.\n \n**Corollary.** Let be a finite family of subsets of \\N.\nThen\nThe theorem provides the first insights on how sumsets accumulate.\nIt seems unfortunate that its conclusion stops short of showing \\sigma being [superadditive](https://bliptext.com/articles/superadditive).\nYet, Schnirelmann provided us with the following results, which sufficed for most of his purpose.\n \n**Theorem.** Let A and B be subsets of \\N.\nIf, then\n \n**Theorem.** (Schnirelmann) Let.\nIf then there exists k such that\n\n# Additive bases\nA subset with the property that for a finite sum, is called an [additive basis](https://bliptext.com/articles/additive-basis), and the least number of summands required is called the degree (sometimes order) of the basis.\nThus, the last theorem states that any set with positive Schnirelmann density is an additive basis.\nIn this terminology, the set of squares is an additive basis of degree 4.\n(About an open problem for additive bases, see [Erdős–Turán conjecture on additive bases](https://bliptext.com/articles/erd-s-tur-n-conjecture-on-additive-bases).)\n\n# Mann's theorem\nHistorically the theorems above were pointers to the following result, at one time known as the hypothesis.\nIt was used by [Edmund Landau](https://bliptext.com/articles/edmund-landau) and was finally proved by [Henry Mann](https://bliptext.com/articles/henry-mann) in 1942.\n \n**Theorem.** Let A and B be subsets of \\N.\nIn case that, we still have\nAn analogue of this theorem for lower asymptotic density was obtained by Kneser.\nAt a later date, [E. Artin](https://bliptext.com/articles/emil-artin) and P. Scherk simplified the proof of Mann's theorem.\n\n# Waring's problem\nLet k and N be natural numbers.\nLet.\nDefine r_N^k(n) to be the number of non-negative integral solutions to the equation\nand R_N^k(n) to be the number of non-negative integral solutions to the inequality\nin the variables x_i, respectively.\nThus.\nWe have\nThe volume of the N-dimensional body defined by, is bounded by the volume of the hypercube of size n^{1/k}, hence.\nThe hard part is to show that this bound still works on the average, i.e.,\n \n**Lemma.** (Linnik) For all k \\in \\N there exists N \\in \\N and a constant c = c(k), depending only on k, such that for all n \\in \\N,\nfor all\nWith this at hand, the following theorem can be elegantly proved.\n \n**Theorem.** For all k there exists N for which.\nWe have thus established the general solution to Waring's Problem:\n \n**Corollary.** 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.\n\n# Schnirelmann's constant\nIn 1930 Schnirelmann used these ideas in conjunction with the [Brun sieve](https://bliptext.com/articles/brun-sieve) to prove **Schnirelmann's theorem**, that any [natural number](https://bliptext.com/articles/natural-number) greater than 1 can be written as the sum of not more than C [prime numbers](https://bliptext.com/articles/prime-numbers), where C is an effectively computable constant: Schnirelmann obtained C 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.","revisionCount":0},"hasMore":false,"nextCursor":null}

History