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

  • 1
    $\begingroup$ 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. $\endgroup$ – Will Jagy Jan 22 '10 at 1:39
  • $\begingroup$ 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. $\endgroup$ – David Mandell Freeman Jan 22 '10 at 1:56
  • $\begingroup$ I'm starting to understand the question. How do you know g'(3) = 4 ? $\endgroup$ – Will Jagy Jan 22 '10 at 2:28
  • $\begingroup$ 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. $\endgroup$ – Michael Lugo Jan 22 '10 at 3:09
  • $\begingroup$ The result g'(3) = 4 is the main result of Davenport, H. "On Waring's Problem for Cubes." Acta Math. 71, 123-143, 1939 $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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