Namespaces
Variants
Actions

Difference between revisions of "Waring problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
A problem in number theory formulated in 1770 by E. Waring in the following form: Any natural number is a sum of 4 squares, of 9 cubes and of 19 fourth-powers. In other words, for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w0971001.png" /> there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w0971002.png" />, depending only on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w0971003.png" />, such that every natural number is the sum of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w0971004.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w0971005.png" />-th powers of non-negative integers. D. Hilbert in 1909 was the first to give a general solution of Waring's problem with a very rough estimate of the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w0971006.png" /> as a function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w0971007.png" />; this is why the problem is sometimes known as the Hilbert–Waring problem. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w0971008.png" /> be the number of solutions of the equation
+
{{TEX|done}}
 +
A problem in number theory formulated in 1770 by E. Waring in the following form: Any natural number is a sum of 4 squares, of 9 cubes and of 19 fourth-powers. In other words, for all $n\geq2$ there exists a $k=k(n)$, depending only on $n$, such that every natural number is the sum of $k$ $n$-th powers of non-negative integers. D. Hilbert in 1909 was the first to give a general solution of Waring's problem with a very rough estimate of the value of $k$ as a function of $n$; this is why the problem is sometimes known as the Hilbert–Waring problem. Let $J_{k,n}(N)$ be the number of solutions of the equation
  
<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/w/w097/w097100/w0971009.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$x_1^n+\cdots+x_k^n=N$$
  
in non-negative integers. Hilbert's theorem then states that there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710010.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710011.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710012.png" />. G.H. Hardy and J.E. Littlewood, who applied the [[Circle method|circle method]] to the Waring problem, demonstrated in 1928 that for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710013.png" /> the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710014.png" /> is given by an asymptotic formula of the type
+
in non-negative integers. Hilbert's theorem then states that there exists a $K=k(n)$ for which $J_{K,n}(N)\geq1$ for any $N\geq1$. G.H. Hardy and J.E. Littlewood, who applied the [[Circle method|circle method]] to the Waring problem, demonstrated in 1928 that for $k\geq(n-2)2^{n-1}+5$ the value of $J_{k,n}(N)$ is given by an asymptotic formula of the type
  
<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/w/w097/w097100/w09710015.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$J_{k,n}(N)=AN^{k/n-1}+O(N^{k/n-1-\gamma}),$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710016.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710018.png" /> are constants. Consequently, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710019.png" />, equation (1) has a solution. This result gave rise to three problems: Determine the order of the three quantities <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710022.png" /> which are the smallest integers for which: a) equation (1) is solvable for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710024.png" />; b) equation (1) is solvable for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710026.png" />; or c) the asymptotic formula (2) applies to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710027.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710028.png" />.
+
where $A=A(N)\geq c_0>0$, while $c_0$ and $\gamma>0$ are constants. Consequently, if $N\geq N_0(n)$, equation (1) has a solution. This result gave rise to three problems: Determine the order of the three quantities $G(n)$, $g(n)$, $k_0(n)$ which are the smallest integers for which: a) equation (1) is solvable for $k\geq G(n)$ and $N\geq N_0(n)$; b) equation (1) is solvable for $k\geq g(n)$ and $N\geq 1$; or c) the asymptotic formula (2) applies to $J_{k,n}(N)$ if $k\geq k_0(n)$.
  
a) It is known that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710029.png" />. It was proved in 1934 by I.M. Vinogradov, using his own method, that
+
a) It is known that $G(n)\geq n+1$. It was proved in 1934 by I.M. Vinogradov, using his own method, that
  
<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/w/w097/w097100/w09710030.png" /></td> </tr></table>
+
$$G(n)\leq 3n(\ln n+9).$$
  
Moreover, many results are available concerning <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710031.png" /> for small values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710032.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710033.png" /> (H. Davenport, 1939); <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710034.png" /> (Yu.V. Linnik, 1942).
+
Moreover, many results are available concerning $G(n)$ for small values of $n$: $G(4)=16$ (H. Davenport, 1939); $G(3)=7$ (Yu.V. Linnik, 1942).
  
 
b) It was shown in 1936 by L. Dickson and S. Pillai, who also used the [[Vinogradov method|Vinogradov method]], that
 
b) It was shown in 1936 by L. Dickson and S. Pillai, who also used the [[Vinogradov method|Vinogradov method]], that
  
<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/w/w097/w097100/w09710035.png" /></td> </tr></table>
+
$$G(n)=2^n+\left[\left(\frac{3}{2}\right)^n\right]-2$$
  
for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710036.png" /> for which
+
for all $n>6$ for which
  
<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/w/w097/w097100/w09710037.png" /></td> </tr></table>
+
$$\left(\frac{3}{2}\right)^n-\left[\left(\frac{3}{2}\right)^n\right]\leq 1-\left(\frac{1}{2}\right)^n\left\{\left[\left(\frac{3}{2}\right)^n\right]+2\right\}.$$
  
The last condition was demonstrated in 1957 by K. Mahler for all sufficiently large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710038.png" />.
+
The last condition was demonstrated in 1957 by K. Mahler for all sufficiently large $n$.
  
 
c) The best result of all must be credited to Vinogradov, who showed that
 
c) The best result of all must be credited to Vinogradov, who showed that
 +
$$k_0(n)\leq 4n^2\ln n.$$
  
<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/w/w097/w097100/w09710039.png" /></td> </tr></table>
 
  
An elementary proof of Waring's problem was given in 1942 by Yu.V. Linnik. There exist many different generalizations of Waring's problem (the variables run through a certain subset of the set of natural numbers; the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710040.png" /> is represented by polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710041.png" /> rather than by monomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097100/w09710042.png" />; equation (1) is replaced by a congruence, etc.).
+
An elementary proof of Waring's problem was given in 1942 by Yu.V. Linnik. There exist many different generalizations of Waring's problem (the variables run through a certain subset of the set of natural numbers; the number $N$ is represented by polynomials $f_1(x_1),\ldots,f_k(x_k)$ rather than by monomials $x_1^n,\ldots,x_k^n$; equation (1) is replaced by a congruence, etc.).
  
 
The special importance of Waring's problem consists in the fact that in trying to solve it, powerful methods in [[Analytic number theory|analytic number theory]] had to be created.
 
The special importance of Waring's problem consists in the fact that in trying to solve it, powerful methods in [[Analytic number theory|analytic number theory]] had to be created.

Revision as of 09:04, 20 April 2012

A problem in number theory formulated in 1770 by E. Waring in the following form: Any natural number is a sum of 4 squares, of 9 cubes and of 19 fourth-powers. In other words, for all $n\geq2$ there exists a $k=k(n)$, depending only on $n$, such that every natural number is the sum of $k$ $n$-th powers of non-negative integers. D. Hilbert in 1909 was the first to give a general solution of Waring's problem with a very rough estimate of the value of $k$ as a function of $n$; this is why the problem is sometimes known as the Hilbert–Waring problem. Let $J_{k,n}(N)$ be the number of solutions of the equation

$$x_1^n+\cdots+x_k^n=N$$

in non-negative integers. Hilbert's theorem then states that there exists a $K=k(n)$ for which $J_{K,n}(N)\geq1$ for any $N\geq1$. G.H. Hardy and J.E. Littlewood, who applied the circle method to the Waring problem, demonstrated in 1928 that for $k\geq(n-2)2^{n-1}+5$ the value of $J_{k,n}(N)$ is given by an asymptotic formula of the type

$$J_{k,n}(N)=AN^{k/n-1}+O(N^{k/n-1-\gamma}),$$

where $A=A(N)\geq c_0>0$, while $c_0$ and $\gamma>0$ are constants. Consequently, if $N\geq N_0(n)$, equation (1) has a solution. This result gave rise to three problems: Determine the order of the three quantities $G(n)$, $g(n)$, $k_0(n)$ which are the smallest integers for which: a) equation (1) is solvable for $k\geq G(n)$ and $N\geq N_0(n)$; b) equation (1) is solvable for $k\geq g(n)$ and $N\geq 1$; or c) the asymptotic formula (2) applies to $J_{k,n}(N)$ if $k\geq k_0(n)$.

a) It is known that $G(n)\geq n+1$. It was proved in 1934 by I.M. Vinogradov, using his own method, that

$$G(n)\leq 3n(\ln n+9).$$

Moreover, many results are available concerning $G(n)$ for small values of $n$: $G(4)=16$ (H. Davenport, 1939); $G(3)=7$ (Yu.V. Linnik, 1942).

b) It was shown in 1936 by L. Dickson and S. Pillai, who also used the Vinogradov method, that

$$G(n)=2^n+\left[\left(\frac{3}{2}\right)^n\right]-2$$

for all $n>6$ for which

$$\left(\frac{3}{2}\right)^n-\left[\left(\frac{3}{2}\right)^n\right]\leq 1-\left(\frac{1}{2}\right)^n\left\{\left[\left(\frac{3}{2}\right)^n\right]+2\right\}.$$

The last condition was demonstrated in 1957 by K. Mahler for all sufficiently large $n$.

c) The best result of all must be credited to Vinogradov, who showed that $$k_0(n)\leq 4n^2\ln n.$$


An elementary proof of Waring's problem was given in 1942 by Yu.V. Linnik. There exist many different generalizations of Waring's problem (the variables run through a certain subset of the set of natural numbers; the number $N$ is represented by polynomials $f_1(x_1),\ldots,f_k(x_k)$ rather than by monomials $x_1^n,\ldots,x_k^n$; equation (1) is replaced by a congruence, etc.).

The special importance of Waring's problem consists in the fact that in trying to solve it, powerful methods in analytic number theory had to be created.

References

[1] I.M. Vinogradov, "Selected works" , Springer (1985) (Translated from Russian)
[2] I.M. Vinogradov, "The method of trigonometric sums in the theory of numbers" , Interscience (1954) (Translated from Russian)
[3] L.-K. Hua, "Abschätzungen von Exponentialsummen und ihre Anwendung in der Zahlentheorie" , Enzyklopaedie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen , 1 : 2 (1959) (Heft 13, Teil 1)
[4] B.N. Delone, "The Peterburg school of number theory" , Moscow-Leningrad (1947) (In Russian)
[5] A.Ya. Khinchin, "Three pearls of number theory" , Graylock (1952) (Translated from Russian)


Comments

It is known that (J.L. Lagrange, 1770), (A. Wieferich, A. Kempner, 1912), (R. Balusabramanian, J. Deshouillers, F. Dress, 1986), (Chen-Jingrun, 1964). See also Circle method and [a1][a3].

References

[a1] G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapt. 6
[a2] R.C. Vaughan, "The Hardy–Littlewood method" , Cambridge Univ. Press (1981)
[a3] D. Shanks, "Solved and unsolved problems in number theory" , Chelsea, reprint (1978)
How to Cite This Entry:
Waring problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Waring_problem&oldid=24851
This article was adapted from an original article by A.A. Karatsuba (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article