Namespaces
Variants
Actions

Difference between revisions of "Additive basis"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
 +
{{TEX|done}}
 
''for the natural numbers''
 
''for the natural numbers''
  
A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a1301101.png" /> of non-negative integers is called an additive basis of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a1301102.png" /> if every non-negative integer may be written in at least one way as a sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a1301103.png" />, with all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a1301104.png" />. One is usually only interested to represent in such a way all sufficiently large positive integers and speaks then of an asymptotic additive basis. For example, the set of squares is an asymptotic additive basis of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a1301105.png" /> (Lagrange's theorem). Most of the results about asymptotic additive bases deal with the existence of  "thin"  bases, for various meanings of the word thin.
+
A set $B$ of non-negative integers is called an additive basis of order $h$ if every non-negative integer may be written in at least one way as a sum $b_1+\dots+b_h$, with all $b_i\in B$. One is usually only interested to represent in such a way all sufficiently large positive integers and speaks then of an asymptotic additive basis. For example, the set of squares is an asymptotic additive basis of order $4$ (Lagrange's theorem). Most of the results about asymptotic additive bases deal with the existence of  "thin"  bases, for various meanings of the word thin.
  
For a given set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a1301106.png" /> one writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a1301107.png" /> for the number of representations of the non-negative integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a1301108.png" /> as a sum of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a1301109.png" /> terms from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011010.png" />, the order of addition being insignificant. A well-known theorem of P. Erdős [[#References|[a1]]] claims that there is an asymptotic basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011011.png" /> with
+
For a given set $B\subseteq\mathbf N$ one writes $r_{B,h}(x)$ for the number of representations of the non-negative integer $x$ as a sum of $h$ terms from $B$, the order of addition being insignificant. A well-known theorem of P. Erdős [[#References|[a1]]] claims that there is an asymptotic basis $B$ with
  
<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/a/a130/a130110/a13011012.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
$$C_1\log x\leq r_{B,2}(x)\leq C_2\log x,\tag{a1}$$
  
when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011013.png" /> is sufficiently large. It is an open problem (as of 2000) if one can have a basis with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011014.png" />. The famous Erdős–Turán conjecture states that, for any asymptotic basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011015.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011016.png" />, the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011018.png" />, cannot be bounded.
+
when $x$ is sufficiently large. It is an open problem (as of 2000) if one can have a basis with $r_{B,2}(x)=o(\log x)$. The famous Erdős–Turán conjecture states that, for any asymptotic basis $B$ of order $2$, the sequence $r_{B,2}(x)$, $x\in\mathbf N$, cannot be bounded.
  
Erdős' construction is probabilistic. He shows that if one takes the integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011019.png" /> to be in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011020.png" /> with probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011021.png" />, for a sufficiently large positive constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011022.png" />, then with probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011023.png" /> the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011024.png" /> is an asymptotic basis satisfying (a1) for suitable constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011026.png" />, for all but finitely many positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011027.png" />. See also [[#References|[a5]]] for a modified probabilistic construction which can be derandomized to yield a polynomial-time algorithm for the determination of such a basis up to any desired integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011028.png" />.
+
Erdős' construction is probabilistic. He shows that if one takes the integer $x$ to be in $B$ with probability $K(\log(x)/x)^{1/2}$, for a sufficiently large positive constant $K$, then with probability $1$ the set $B$ is an asymptotic basis satisfying \ref{a1} for suitable constants $C_1$ and $C_2$, for all but finitely many positive integers $x$. See also [[#References|[a5]]] for a modified probabilistic construction which can be derandomized to yield a polynomial-time algorithm for the determination of such a basis up to any desired integer $n$.
  
Erdős' result was subsequently extended [[#References|[a2]]] to bases of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011029.png" />, where the obstacle of having the random variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011030.png" /> no more independent for different <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011031.png" /> was removed with the help of Janson's inequality [[#References|[a3]]]. Janson's inequality has also been used by J. Spencer [[#References|[a6]]] to prove that one may take a small subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011032.png" /> of the squares, of size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011033.png" /> which is still an asymptotic additive basis of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011034.png" />.
+
Erdős' result was subsequently extended [[#References|[a2]]] to bases of order $h>2$, where the obstacle of having the random variables $r_{B,h}(x)$ no more independent for different $x$ was removed with the help of Janson's inequality [[#References|[a3]]]. Janson's inequality has also been used by J. Spencer [[#References|[a6]]] to prove that one may take a small subset $A$ of the squares, of size $|A\cap[1,x]|\leq Cx^{1/4}\log x$ which is still an asymptotic additive basis of order $4$.
  
Another measure for a basis being small is that of minimality. An asymptotic additive basis of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011035.png" /> is called minimal if it has no proper subset that is an asymptotic additive basis of the same order. Such bases are known to exist for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011036.png" />. For example, in [[#References|[a4]]] it is proved that for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011037.png" /> and every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011038.png" /> there exists a minimal asymptotic basis of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011039.png" /> and with counting function of the order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011040.png" />.
+
Another measure for a basis being small is that of minimality. An asymptotic additive basis of order $h$ is called minimal if it has no proper subset that is an asymptotic additive basis of the same order. Such bases are known to exist for all $h$. For example, in [[#References|[a4]]] it is proved that for every $h$ and every $\alpha<1/h$ there exists a minimal asymptotic basis of order $h$ and with counting function of the order $x^\alpha$.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Erdős,  "Problems and results in additive number theory" , ''Colloque sur la Theorié des Nombres (CBRM, Bruxelles)'' , G. Thone  (1955)  pp. 255–259</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Erdős,  P. Tetali,  "Representations of integers as the sum of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a130/a130110/a13011041.png" /> terms"  ''Random Struct. Algor.'' , '''1''' :  3  (1990)  pp. 245–261</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  S. Janson,  "Poisson approximation for large deviations"  ''Random Struct. Algor.'' , '''1''' :  2  (1990)  pp. 221–229</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  X.-D. Jia,  M.B. Nathanson,  "A simple construction for minimal asymptotic bases"  ''Acta Arith.'' , '''52''' :  2  (1989)  pp. 95–101</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M. Kolountzakis,  "An effective additive basis for the integers"  ''Discr. Math.'' , '''145'''  (1995)  pp. 1–3; 307–313</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  J. Spencer,  "Four squares with few squares" , ''Number Theory (New York, 1991-1995)'' , Springer  (1996)  pp. 295–297</TD></TR></table>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P. Erdős,  "Problems and results in additive number theory" , ''Colloque sur la Theorié des Nombres (CBRM, Bruxelles)'' , G. Thone  (1955)  pp. 255–259</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P. Erdős,  P. Tetali,  "Representations of integers as the sum of $k$ terms"  ''Random Struct. Algor.'' , '''1''' :  3  (1990)  pp. 245–261</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  S. Janson,  "Poisson approximation for large deviations"  ''Random Struct. Algor.'' , '''1''' :  2  (1990)  pp. 221–229</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  X.-D. Jia,  M.B. Nathanson,  "A simple construction for minimal asymptotic bases"  ''Acta Arith.'' , '''52''' :  2  (1989)  pp. 95–101</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M. Kolountzakis,  "An effective additive basis for the integers"  ''Discr. Math.'' , '''145'''  (1995)  pp. 1–3; 307–313</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  J. Spencer,  "Four squares with few squares" , ''Number Theory (New York, 1991-1995)'' , Springer  (1996)  pp. 295–297</TD></TR></table>

Revision as of 18:51, 28 June 2015

for the natural numbers

A set $B$ of non-negative integers is called an additive basis of order $h$ if every non-negative integer may be written in at least one way as a sum $b_1+\dots+b_h$, with all $b_i\in B$. One is usually only interested to represent in such a way all sufficiently large positive integers and speaks then of an asymptotic additive basis. For example, the set of squares is an asymptotic additive basis of order $4$ (Lagrange's theorem). Most of the results about asymptotic additive bases deal with the existence of "thin" bases, for various meanings of the word thin.

For a given set $B\subseteq\mathbf N$ one writes $r_{B,h}(x)$ for the number of representations of the non-negative integer $x$ as a sum of $h$ terms from $B$, the order of addition being insignificant. A well-known theorem of P. Erdős [a1] claims that there is an asymptotic basis $B$ with

$$C_1\log x\leq r_{B,2}(x)\leq C_2\log x,\tag{a1}$$

when $x$ is sufficiently large. It is an open problem (as of 2000) if one can have a basis with $r_{B,2}(x)=o(\log x)$. The famous Erdős–Turán conjecture states that, for any asymptotic basis $B$ of order $2$, the sequence $r_{B,2}(x)$, $x\in\mathbf N$, cannot be bounded.

Erdős' construction is probabilistic. He shows that if one takes the integer $x$ to be in $B$ with probability $K(\log(x)/x)^{1/2}$, for a sufficiently large positive constant $K$, then with probability $1$ the set $B$ is an asymptotic basis satisfying \ref{a1} for suitable constants $C_1$ and $C_2$, for all but finitely many positive integers $x$. See also [a5] for a modified probabilistic construction which can be derandomized to yield a polynomial-time algorithm for the determination of such a basis up to any desired integer $n$.

Erdős' result was subsequently extended [a2] to bases of order $h>2$, where the obstacle of having the random variables $r_{B,h}(x)$ no more independent for different $x$ was removed with the help of Janson's inequality [a3]. Janson's inequality has also been used by J. Spencer [a6] to prove that one may take a small subset $A$ of the squares, of size $|A\cap[1,x]|\leq Cx^{1/4}\log x$ which is still an asymptotic additive basis of order $4$.

Another measure for a basis being small is that of minimality. An asymptotic additive basis of order $h$ is called minimal if it has no proper subset that is an asymptotic additive basis of the same order. Such bases are known to exist for all $h$. For example, in [a4] it is proved that for every $h$ and every $\alpha<1/h$ there exists a minimal asymptotic basis of order $h$ and with counting function of the order $x^\alpha$.

References

[a1] P. Erdős, "Problems and results in additive number theory" , Colloque sur la Theorié des Nombres (CBRM, Bruxelles) , G. Thone (1955) pp. 255–259
[a2] P. Erdős, P. Tetali, "Representations of integers as the sum of $k$ terms" Random Struct. Algor. , 1 : 3 (1990) pp. 245–261
[a3] S. Janson, "Poisson approximation for large deviations" Random Struct. Algor. , 1 : 2 (1990) pp. 221–229
[a4] X.-D. Jia, M.B. Nathanson, "A simple construction for minimal asymptotic bases" Acta Arith. , 52 : 2 (1989) pp. 95–101
[a5] M. Kolountzakis, "An effective additive basis for the integers" Discr. Math. , 145 (1995) pp. 1–3; 307–313
[a6] J. Spencer, "Four squares with few squares" , Number Theory (New York, 1991-1995) , Springer (1996) pp. 295–297
How to Cite This Entry:
Additive basis. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Additive_basis&oldid=36528
This article was adapted from an original article by Mihail N. Kolountzakis (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article