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?

  • 0
    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?2012-10-24

2 Answers 2

0

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

  • 1
    @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).2012-10-24
0

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