3
$\begingroup$

I need to show that, if $G(k)$ is the solution to Waring's Problem for $k$ and for sufficiently large $n$, then:

$$G(k) \ge k + 1$$

So I need to establish that:

$$x_1^k + x_2^k + \dots + x_k^k = n \tag{1}$$

fails for an arbitrary number of values. I've a few solutions to this, but they seem outside the scope of the course (4th year Ele.Num.Theory).

A hint is that we should use an earlier result that the number of solutions to:

$$x_1 + x_2 + \dots + x_k \le n$$ is $$\binom{n + k}{n}$$

I don't see how I can establish the result given this information. Maybe there's a better way?

$\endgroup$
  • $\begingroup$ thank you for the edits monhawk. I'm still getting used to Latex $\endgroup$ – user45793 Oct 24 '12 at 10:10
  • $\begingroup$ What I have so far is that there are $n^{\frac{1}{k}} + 1$ values for $x_i$ that could possibly satisfy $(1)$. Hence, choosing $k$ of them where repetitions are allowed and order is unimportant is: $$\binom{n^{1/k} + k + 1}{n^{1/k} + 1} $$ which is greater than the number of solutions to: $$x_1^k + x_2^k + \dots + x_k^k \le n$$ which is in turn greater than the number of solutions to $(1)$. Than just need to show this last binomial coefficient grows at a rate less than $1$ for large $n$? Can someone confirm I'm on the right track with this? $\endgroup$ – user45793 Oct 24 '12 at 16:33
0
$\begingroup$

Hint 1: You use the result to count the number of different ways to choose $k$ things from a pool of $m$ where order is unimportant but repetitions are allowed.

Hint 2: What is the largest that $x_i$ could possibly be?

Hint 3: How many solutions are there to $x_1^k + \cdots + x_k^k \color{blue}\le n$?

$\endgroup$
  • $\begingroup$ Thanks for the reply! Doesn't the first result count the number of ways to partition n into k+1 partitions? And ya, $x_i \le n^{1/k}$ $\endgroup$ – user45793 Oct 24 '12 at 8:28
  • 1
    $\begingroup$ @Carl Yes. Note that there is a correspondence between $k+1$ numbers summing to exactly $n$ and an inventory of $n$ things chosen from a pool of $k+1$. $\endgroup$ – Erick Wong Oct 24 '12 at 8:33
  • $\begingroup$ Am I on the right track? Im still at this $\endgroup$ – user45793 Oct 24 '12 at 16:00
  • 1
    $\begingroup$ @Carl Yes. You just need to show that $\binom{n^{1/k} + k + 1}{n^{1/k} + 1} < n$ for large enough $n$. Then there are fewer sums than there are values between 1 and $n$ (technically you should show that the difference between the LHS and RHS is arbitrarily large). $\endgroup$ – Erick Wong Oct 24 '12 at 16:41
0
$\begingroup$

I just received an answer for this. It may or may not be what you're looking for: Bounds for Waring's Problem

$\endgroup$

Your Answer

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