Namespaces
Variants
Actions

Difference between revisions of "Waring problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (MSC)
(Structure overhaul.)
Line 2: Line 2:
 
{{MSC|11P05}}
 
{{MSC|11P05}}
  
A problem in number theory formulated in 1770 by
+
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
E. Waring in the following form: Any natural number is a sum of 4
+
Hilbert–Waring problem. Let $J_{k,n}(N)$ be the number of solutions of the equation
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$$
+
\begin{equation}\label{war}x_1^n+\cdots+x_k^n=N\end{equation}
  
in non-negative integers. Hilbert's theorem then states that there
+
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
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
 
  
$$J_{k,n}(N)=AN^{k/n-1}+O(N^{k/n-1-\gamma}),$$
+
\begin{equation}\label{asym}J_{k,n}(N)=AN^{k/n-1}+O(N^{k/n-1-\gamma}),\end{equation}
  
where $A=A(N)\geq c_0>0$, while $c_0$ and $\gamma>0$ are
+
where $A=A(N)\geq c_0>0$, while $c_0$ and $\gamma>0$ are constants. Consequently, if $N\geq N_0(n)$, equation \ref{war} has a solution.
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
+
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.).
I.M. Vinogradov, using his own method, that
+
 
 +
Research on Waring's problem has mainly focused on sharpening estimates for the following three questions:
 +
# Find the smallest $k$ such that \ref{war} has solutions for all sufficiently large $N$;
 +
# Find the smallest $k$ such that \ref{war} has solutions for all $N$;
 +
# Find the smallest $k$ such that the number of solutions to \ref{war}, $J_{k,n}(N)$, is given by the asymptotic formula \ref{asym}.
 +
 
 +
These quantities are known as $G(n)$, $g(n)$, and $k_0(n)$ respectively. Clearly, $k_0(n)\geq G(n)$ and $g(n)\geq G(n)$. The progress on bounds for these quantities is detailed below.
 +
 
 +
== Solvable for $N$ sufficiently large ==
 +
Let $G(n)$ be the smallest integer such that equation \ref{war} is solvable for $k\geq G(n)$ and $N$ sufficiently large depending on $n$.
 +
 
 +
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).$$
 
$$G(n)\leq 3n(\ln n+9).$$
  
Moreover, many results are available concerning $G(n)$ for small
+
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).
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
+
== Solvable for all $N$ ==
[[Vinogradov method|Vinogradov method]], that
+
 
 +
Let $g(n)$ be the smallest integer such that equation \ref{war} is solvable for $k\geq g(n)$ and $N\geq1$.
 +
 
 +
It was shown in 1936 by L. Dickson and S. Pillai, who also used the [[Vinogradov method|Vinogradov method]], that
  
 
$$G(n)=2^n+\left[\left(\frac{3}{2}\right)^n\right]-2$$
 
$$G(n)=2^n+\left[\left(\frac{3}{2}\right)^n\right]-2$$
  
for all $n>6$ for which
+
for all $n>6$ for which
  
$$\left(\frac{3}{2}\right)^n-\left[\left(\frac{3}{2}\right)^n\right]\leq
+
$$\left(\frac{3}{2}\right)^n-\left[\left(\frac{3}{2}\right)^n\right]\leq1-\left(\frac{1}{2}\right)^n\left\{\left[\left(\frac{3}{2}\right)^n\right]+2\right\}.$$
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
+
The last condition was demonstrated in 1957 by K. Mahler for all sufficiently large $n$.  
sufficiently large $n$.
 
  
c) The best result of all must be credited to Vinogradov, who showed
+
It is known that $g(2)=4$ (J.L. Lagrange, 1770), $g(3)=9$ (A. Wieferich, A. Kempner, 1912), $g(4)=19$ (R. Balusabramanian, J. Deshouillers, F. Dress, 1986), $g(5)=37$ (Chen-Jingrun, 1964). See also [[Circle method|Circle method]] and {{Cite|HaWr}}–{{Cite|Sh}}.
that
 
$$k_0(n)\leq 4n^2\ln n.$$
 
  
 +
== Asymptotic formula ==
 +
Let $k_0(n)$ be the smallest integer such that the asymptotic formula \ref{asym} applies to $J_{k,n}(N)$ if $k\geq k_0(n)$.
  
An elementary proof of Waring's problem was given in 1942 by
+
The best result of all must be credited to Vinogradov, who showed that
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
+
$$k_0(n)\leq 4n^2\ln n.$$
in trying to solve it, powerful methods in
 
[[Analytic number theory|analytic number theory]] had to be created.
 
  
====References====
+
==References==
 
{|
 
{|
 
|-
 
|-
Line 83: Line 66:
 
|-
 
|-
 
|valign="top"|{{Ref|Vi2}}||valign="top"| I.M. Vinogradov, "The method of trigonometric sums in the theory of numbers", Interscience (1954) (Translated from Russian)
 
|valign="top"|{{Ref|Vi2}}||valign="top"| I.M. Vinogradov, "The method of trigonometric sums in the theory of numbers", Interscience (1954) (Translated from Russian)
|-
 
|}
 
 
 
====Comments====
 
It is known that $g(2)=4$ (J.L. Lagrange, 1770), $g(3)=9$
 
(A. Wieferich, A. Kempner, 1912), $g(4)=19$ (R. Balusabramanian,
 
J. Deshouillers, F. Dress, 1986), $g(5)=37$ (Chen-Jingrun, 1964). See also
 
[[Circle method|Circle method]] and
 
{{Cite|HaWr}}–{{Cite|Sh}}.
 
 
====References====
 
{|
 
 
|-
 
|-
 
|valign="top"|{{Ref|HaWr}}||valign="top"| G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers", Oxford Univ. Press (1979) pp. Chapt. 6
 
|valign="top"|{{Ref|HaWr}}||valign="top"| G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers", Oxford Univ. Press (1979) pp. Chapt. 6

Revision as of 11:12, 23 April 2012

2020 Mathematics Subject Classification: Primary: 11P05 [MSN][ZBL]

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

\begin{equation}\label{war}x_1^n+\cdots+x_k^n=N\end{equation}

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

\begin{equation}\label{asym}J_{k,n}(N)=AN^{k/n-1}+O(N^{k/n-1-\gamma}),\end{equation}

where $A=A(N)\geq c_0>0$, while $c_0$ and $\gamma>0$ are constants. Consequently, if $N\geq N_0(n)$, equation \ref{war} has a solution.

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.).

Research on Waring's problem has mainly focused on sharpening estimates for the following three questions:

  1. Find the smallest $k$ such that \ref{war} has solutions for all sufficiently large $N$;
  2. Find the smallest $k$ such that \ref{war} has solutions for all $N$;
  3. Find the smallest $k$ such that the number of solutions to \ref{war}, $J_{k,n}(N)$, is given by the asymptotic formula \ref{asym}.

These quantities are known as $G(n)$, $g(n)$, and $k_0(n)$ respectively. Clearly, $k_0(n)\geq G(n)$ and $g(n)\geq G(n)$. The progress on bounds for these quantities is detailed below.

Solvable for $N$ sufficiently large

Let $G(n)$ be the smallest integer such that equation \ref{war} is solvable for $k\geq G(n)$ and $N$ sufficiently large depending on $n$.

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).

Solvable for all $N$

Let $g(n)$ be the smallest integer such that equation \ref{war} is solvable for $k\geq g(n)$ and $N\geq1$.

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]\leq1-\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$.

It is known that $g(2)=4$ (J.L. Lagrange, 1770), $g(3)=9$ (A. Wieferich, A. Kempner, 1912), $g(4)=19$ (R. Balusabramanian, J. Deshouillers, F. Dress, 1986), $g(5)=37$ (Chen-Jingrun, 1964). See also Circle method and [HaWr][Sh].

Asymptotic formula

Let $k_0(n)$ be the smallest integer such that the asymptotic formula \ref{asym} applies to $J_{k,n}(N)$ if $k\geq k_0(n)$.

The best result of all must be credited to Vinogradov, who showed that

$$k_0(n)\leq 4n^2\ln n.$$

References

[De] B.N. Delone, "The Peterburg school of number theory", Moscow-Leningrad (1947) (In Russian)
[Hu] 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)
[Kh] A.Ya. Khinchin, "Three pearls of number theory", Graylock (1952) (Translated from Russian)
[Vi] I.M. Vinogradov, "Selected works", Springer (1985) (Translated from Russian)
[Vi2] I.M. Vinogradov, "The method of trigonometric sums in the theory of numbers", Interscience (1954) (Translated from Russian)
[HaWr] G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers", Oxford Univ. Press (1979) pp. Chapt. 6
[Sh] D. Shanks, "Solved and unsolved problems in number theory", Chelsea, reprint (1978)
[Va] R.C. Vaughan, "The Hardy–Littlewood method", Cambridge Univ. Press (1981)
How to Cite This Entry:
Waring problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Waring_problem&oldid=25151
This article was adapted from an original article by A.A. Karatsuba (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article