MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Waring's problem (previously asked about here) asks, for each integer $k \ge 2$, what is the smallest integer $g(k)$ such that any positive integer can be written as a sum of $g(k)$ kth powers. We have $g(2) = 4$, $g(3) = 9$, etc. A (harder) variant asks what the smallest integer $G(k)$ is such that all sufficiently large integers can be written as a sum of $G(k)$ kth powers.

I have two related questions:

  1. What is known if we relax the condition ``any positive integer'' and only require a positive-density subset? More precisely, we look for the smallest $g'(k)$ for which there is some $S \subset \mathbb{Z}_{>0}$ of positive density such that any $x \in S$ can be written as $g'(k)$ $k$th powers. Then we have $g'(2) = 3$, while $G(2) = 4$; and $g'(3) = 4$, while it is only known that $4 \le G(3) \le 7$. Is anything known about $g'(k)$ for k = 4,5, or larger?

  2. For fixed k, is there an efficient algorithm that, given n, writes n as a sum of $g(k)$ kth powers? What about decomposing n into the minimal number of kth powers for that n? (Here `efficient' means polynomial in log(n).)

Edit: Wikipedia says that ``In the absence of congruence restrictions, a density argument suggests that G(k) should equal k + 1.'' So perhaps this is the answer to (1)?

share|cite|improve this question
If I understand correctly (never guaranteed), then g'(2) = 3. See LeVeque, Topics in Number Theory, Volume II, Section 7-5, The integers representable as the sum of two squares. The count up to some x is asymptotically constant * x / sqrt( log x). Available Dover reprint. – Will Jagy Jan 22 '10 at 1:39
Yes, you are right. I was recalling the result that any prime congruent to 1 mod 4 is the sum of two squares. But the primes aren't dense in Z. :) Post edited. Actually for my application densities like c*x/poly(log x) would be sufficient...but no need to complicate things. – David Mandell Freeman Jan 22 '10 at 1:56
I'm starting to understand the question. How do you know g'(3) = 4 ? – Will Jagy Jan 22 '10 at 2:28
g'(2) = 3 since a positive-density subset of the integers can be written as a sum of three squares. Specifically, all the integers which are not of the form $4^m (8k+7)$ can be written this way; that set has density 5/6. @Will: cx/sqrt(log x) is correct, and not enough; we need a constant times x. – Michael Lugo Jan 22 '10 at 3:09
The result g'(3) = 4 is the main result of Davenport, H. "On Waring's Problem for Cubes." Acta Math. 71, 123-143, 1939 – David Mandell Freeman Jan 22 '10 at 7:57

Regarding question 1, it is easy to prove that $g'(k) \ge k$, and the expectation is that $g'(k)=k$ for all $k \ge 3$. But the equality is an open question even for $k=3$. See Deshouillers, Jean-Marc; Hennecart, François; Landreau, Bernard; Sums of powers: an arithmetic refinement to the probabilistic model of Erdös and Rényi. Acta Arith. 85 (1998), no. 1, 13-33, and other papers by these authors.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.