Namespaces
Variants
Actions

Difference between revisions of "Density of a sequence"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
A concept in general additive number theory, in which one studies addition laws for sequences of general form. The density of a sequence is a measure of what part of the sequence of all natural numbers belongs to a given sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d0311201.png" /> of integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d0311202.png" />. By the density of a sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d0311203.png" /> one means the density <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d0311204.png" /> (introduced in 1930 by L.G. Shnirel'man) of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d0311205.png" />, namely
+
{{TEX|done}}
 +
A concept in general additive number theory, in which one studies addition laws for sequences of general form. The density of a sequence is a measure of what part of the sequence of all natural numbers belongs to a given sequence $A=\{a_k\}$ of integers $a_0=0<1\leq a_1<\dots<a_k$. By the density of a sequence $A$ one means the density $d(A)$ (introduced in 1930 by L.G. Shnirel'man) of $A$, namely
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d0311206.png" /></td> </tr></table>
+
$$d(A)=\inf\frac{A(n)}{n},$$
  
 
where
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d0311207.png" /></td> </tr></table>
+
$$A(n)=\sum_{1\leq a_k\leq n}1.$$
  
The density <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d0311208.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d0311209.png" /> coincides with the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112010.png" /> of all non-negative integers. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112011.png" /> be the arithmetic sum of two sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112013.png" />, i.e. the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112014.png" /> where the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112015.png" /> are taken without repetition. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112016.png" />, one puts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112017.png" />, and similarly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112018.png" />, etc. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112019.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112020.png" /> is called a basis of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112022.png" />. On examining the structures of sets obtained by summing sequences determined only by their densities, one uses the following theorems on the density of the sum of two sequences:
+
The density $d(A)=1$ if and only if $A$ coincides with the set $\mathbf N_0$ of all non-negative integers. Let $A+B$ be the arithmetic sum of two sequences $A=\{a_k\}$ and B=\{b_t}\, i.e. the set $A+B=\{a_k+b_t\}$ where the numbers $a_k+b_t$ are taken without repetition. If $A=B$, one puts $2A=A+A$, and similarly $3A=A+A+A$, etc. If $hA=\mathbf N_0$, then $A$ is called a basis of order $h$. On examining the structures of sets obtained by summing sequences determined only by their densities, one uses the following theorems on the density of the sum of two sequences:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112023.png" /></td> </tr></table>
+
$$d(A+B)\geq d(A)+d(B)-d(A)d(B)$$
  
 
(Shnirel'man's inequality) and the stronger inequality
 
(Shnirel'man's inequality) and the stronger inequality
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112024.png" /></td> </tr></table>
+
$$d(A+B)\geq\min(d(A)+d(B),1)$$
  
 
(the Mann–Dyson inequality).
 
(the Mann–Dyson inequality).
  
Shnirel'man's inequality implies that any sequence of positive density is a basis of finite order. This can be used in additive problems, in which one frequently sums sequences of zero density by the preliminary construction of new sequences with positive density from the given ones. For example, it has been shown by sieve methods that the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112025.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112026.png" /> runs through the prime numbers, has positive density. Shnirel'man's theorem follows from this: There exists an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112027.png" /> such that any natural number is the sum of at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031120/d03112028.png" /> prime numbers. This theorem gives a solution to the so-called weak Goldbach problem (see also [[Additive number theory|Additive number theory]]).
+
Shnirel'man's inequality implies that any sequence of positive density is a basis of finite order. This can be used in additive problems, in which one frequently sums sequences of zero density by the preliminary construction of new sequences with positive density from the given ones. For example, it has been shown by sieve methods that the sequence $\{p\}+\{p\}$, where $p$ runs through the prime numbers, has positive density. Shnirel'man's theorem follows from this: There exists an integer $c_0>0$ such that any natural number is the sum of at most $c_0$ prime numbers. This theorem gives a solution to the so-called weak Goldbach problem (see also [[Additive number theory|Additive number theory]]).
  
 
A variant of this concept of density is that of [[Asymptotic density|asymptotic density]], a particular case of this being the natural density. The concept of density is also extended to numerical sequences differing from the natural sequence, for example to the sequence of integers in algebraic number fields. As a result it is possible to examine bases in algebraic fields.
 
A variant of this concept of density is that of [[Asymptotic density|asymptotic density]], a particular case of this being the natural density. The concept of density is also extended to numerical sequences differing from the natural sequence, for example to the sequence of integers in algebraic number fields. As a result it is possible to examine bases in algebraic fields.

Revision as of 08:41, 22 August 2014

A concept in general additive number theory, in which one studies addition laws for sequences of general form. The density of a sequence is a measure of what part of the sequence of all natural numbers belongs to a given sequence $A=\{a_k\}$ of integers $a_0=0<1\leq a_1<\dots<a_k$. By the density of a sequence $A$ one means the density $d(A)$ (introduced in 1930 by L.G. Shnirel'man) of $A$, namely

$$d(A)=\inf\frac{A(n)}{n},$$

where

$$A(n)=\sum_{1\leq a_k\leq n}1.$$

The density $d(A)=1$ if and only if $A$ coincides with the set $\mathbf N_0$ of all non-negative integers. Let $A+B$ be the arithmetic sum of two sequences $A=\{a_k\}$ and B=\{b_t}\, i.e. the set $A+B=\{a_k+b_t\}$ where the numbers $a_k+b_t$ are taken without repetition. If $A=B$, one puts $2A=A+A$, and similarly $3A=A+A+A$, etc. If $hA=\mathbf N_0$, then $A$ is called a basis of order $h$. On examining the structures of sets obtained by summing sequences determined only by their densities, one uses the following theorems on the density of the sum of two sequences:

$$d(A+B)\geq d(A)+d(B)-d(A)d(B)$$

(Shnirel'man's inequality) and the stronger inequality

$$d(A+B)\geq\min(d(A)+d(B),1)$$

(the Mann–Dyson inequality).

Shnirel'man's inequality implies that any sequence of positive density is a basis of finite order. This can be used in additive problems, in which one frequently sums sequences of zero density by the preliminary construction of new sequences with positive density from the given ones. For example, it has been shown by sieve methods that the sequence $\{p\}+\{p\}$, where $p$ runs through the prime numbers, has positive density. Shnirel'man's theorem follows from this: There exists an integer $c_0>0$ such that any natural number is the sum of at most $c_0$ prime numbers. This theorem gives a solution to the so-called weak Goldbach problem (see also Additive number theory).

A variant of this concept of density is that of asymptotic density, a particular case of this being the natural density. The concept of density is also extended to numerical sequences differing from the natural sequence, for example to the sequence of integers in algebraic number fields. As a result it is possible to examine bases in algebraic fields.

References

[1] A.O. Gel'fond, Yu.V. Linnik, "Elementary methods in the analytic theory of numbers" , M.I.T. (1966) (Translated from Russian)
[2] H.H. Ostmann, "Additive Zahlentheorie" , Springer (1956)
How to Cite This Entry:
Density of a sequence. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Density_of_a_sequence&oldid=33074
This article was adapted from an original article by B.M. Bredikhin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article