# Are there unique solutions for $n=\sum_{j=1}^{g(k)} a_j^k$?

Edward Waring, asks whether for every natural number $n$ there exists an associated positive integer s such that every natural number is the sum of at most $s$ $k$th powers of natural numbers (for example, every number is the sum of at most 4 squares, or 9 cubes, or 19 fourth powers, etc.) from here.

I ask: Are there unique solutions for $n=\sum_{j=1}^{g(k)} a_j^k$, with $a_u\neq a_v \geq0 \; , \; \forall u\neq v$?

$g(k)$ being the minimum number $s$ of $k$th powers needed to represent all integers. $14$ would be an example of a unique decomposition (into $0^2+1^2+2^2+3^2$).

Non-unique decompositions for $k=2$ can be constructed by letting $n=(a_0+x)^2+\sum_{j=1}^3 a_j^2$ and $a_0=x+\sum_{j=1}^3 a_j$. Robert gave a formula for cubes below.

So another question is: How can one test that a certain $n$ has a unique solution, or even better how can I calculate the number of respresentations? As Gerry points out in his comment, a prime $p=4k+1\;$ has a unique representation $p=a^2+b^2$ with $0<a<b\;$ (Thue's Lemma).

Partial answer for $k=2$ (from here)

The sequence of positive integers whose representation as a sum of four squares is unique is:

1, 2, 3, 5, 6, 7, 8, 11, 14, 15, 23, 24, 32, 56, 96, 128, 224... (sequence A006431 in OEIS).

These integers consist of the seven odd numbers $1, 3, 5, 7, 11, 15, 23$ and all numbers of the form $2 × 4^k, 6 × 4^k$ or $14 × 4^k$.

Partial, therefore, because $23=1^2+2^2+2\times 3^2$ (answer, because $14\times 4^k$ is unique).

Another way to look at it, uses ${g(k)}$-dimensional vector spaces $V$ over $\mathbb N_0^+$ that are provided with an $k$-norm $||a||_k=\left( \sum_{j=1}^{g(k)} a_j^k \right)^{1/k}$ and the additional conditions that $a_u\neq a_v \geq0 \; , \; \forall u\neq v$. Now there is a set of length-preserving operations $U_p$, that transforms vectors, from a defined range $\mathcal R (U_p)$. An example operation was shown above. In this framework the question sounds like:

Which vectors of $V$ lie outside the union of all $\mathcal R (U_p)$?

-
There is a (relatively simple to prove) theorem due to Sprague (from 1940s) stating that all the integers larger than 128 can be written as sums of unequal squares. 128 cannot be written as a sum of unequal squares, so that variant of the question is fully settled. Similar results exist for cubes (and higher). I don't know about Waring type of bounds on the number of terms, though. They would probably work for large integers only. Not really your variant, I know. May be a useful buzzword when looking for more information? – Jyrki Lahtonen Jan 30 '12 at 14:38
I don't know. The idea is simple. You show by brute force checking that you can always pick a subset of $1^2,2^2,3^2,\ldots,10^2$ such that it has any desired sum $n$ in the range $129\le n\le192$. Then the complements of those sums give you similar representations for numbers $m$ in the range $385-192=193\le m\le 385-129=256.$ ($\sum_{k=1}^{10}k^2=385$) This range $[129,256]$ is longer than $11^2$, so adding that term to the mix proves it for all the integers up to $256+11^2=377$. Then add $12^2$ et cetera. – Jyrki Lahtonen Jan 30 '12 at 14:48
An example for cubes of the kind of identity you're considering is $(a_1 + 2 x)^3 + \sum_{j=2}^9 a_j^3 = a_1^3 + \sum_{j=2}^9 (a_j + x)^3$ where $x = {\frac {-2\,{a_{{1}}}^{2}+{a_{{2}}}^{2}+{a_{{3}}}^{2}+{a_{{4}}}^ {2}+{a_{{5}}}^{2}+{a_{{6}}}^{2}+{a_{{7}}}^{2}+{a_{{8}}}^{2}+{a_{{9}}}^ {2}}{4\,a_{{1}}-a_{{2}}-a_{{3}}-a_{{4}}-a_{{5}}-a_{{6}}-a_{{7}}-a_{{8} }-a_{{9}}}}$ – Robert Israel Jan 31 '12 at 20:54
F Halter-Koch, Darstellung naturlicher Zahlen als Summe von Quadraten, Acta Arith 42 (1982) 11-20 proves that if $n\gt157$ is odd then it is a sum of four distinct non-zero coprime squares. The result is used in Bateman, Hildebrand, Purdy, Sums of distinct squares, Acta Arith 67 (1994) 349-380, which is available at matwbn.icm.edu.pl/ksiazki/aa/aa67/aa6745.pdf – Gerry Myerson Jan 31 '12 at 23:22
Also of possible interest is oeis.org/A001661 "Largest number not the sum of distinct n-th powers." – Gerry Myerson Jan 31 '12 at 23:27