# Represent an integer as a sum of n non-consecutive squares

Is it possible to decompose an integer into a sum of n unique squares ,even though they are not necessarily consecutive.

For instance, How would I obtain the sequence 1*1 + 7*7 + 14*14 + 37*37 given the integer 1615 or 11*11 + 15*15 + 29*29 + 43*43 + 69*69 given the integer 7797.

• Not if the integer is 2, 3, 6, 7, ..., assuming “unique” means pairwise distinct. Jun 30 '14 at 15:25
• The question is vague: is $n$ a fixed number (like $5$ in GH from MO's answer)? What does consecutive have to do with the problem?
– Lucia
Jun 30 '14 at 15:37
• One might say consecutive has nothing to do with the problem. Unfortunately, neither answer addresses the nonconsecutive aspect, focussing instead on no repeated summands. I assume the post disallows sums that include e.g. 2209 and 2304 as members of the same sum.
Jun 30 '14 at 17:56

OEIS A001422 gives the full list of natural numbers not expressible as the sum of distinct squares: $$\begin{array}{c} 2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, \\ 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128. \end{array}$$ The reference is

R. Sprague, Über Zerlegungen in ungleiche Quadratzahlen, Math. Z. 51 (1948), 289$-$290.

(This two-page paper is several decades before Halter-Koch 1982, which concerns decompositions into exactly $5$ distinct squares.)

Added later: The Sprague paper is elementary and constructive, thus also answering the OP's question "How would I obtain [a sum-of-distinct-squares representation] given the integer". Basically, starting from $n$, subtract the first square larger than $n/2$, and repeat until you first reach a number less than $300$. That number will still exceed $128$, so to finish consult a table with a distinct-square representation of each of the integers in $(128,300)$. Such a table was routine to compute even in 1948, and is basically trivial with the computer.

For example, applying this technique to the OP's $1615$ yields $1615 = 29^2 + 20^2 + 14^2 + 178$, and then for instance $178 = 13^2 + 3^2$ or $178 = 12^2 + 5^2 + 3^2$.

If we read "even though they are not consecutive" in the strict sense that no pair of consecutive squares is allowed in the sum, then much the same technique must still work, though with thresholds somewhat larger than $128$ and $300$, and subtracting from $n$ the smallest $k$ such that $n-k^2 < (k-1)^2$ (not just less than $k^2$).

• Knowing Halter-Koch, one can of course easily recover this list; e.g. in gp:  P = prod(m=1,15,1+q^(m^2),1+O(q^246)); for(n=1,245,if(polcoeff(P,n)==0,print(n))) Jun 30 '14 at 15:50
• Yes, the last technique is ore or less what Thompson and I did with odd squares in our paper: subtract off the largest possible odd square until you get into a low range where you can check everything case by case. Jun 30 '14 at 23:42
• But that can't tell you that at most $11$ squares suffice; you must have given some other argument to obtain that result. Jun 30 '14 at 23:46
• Yes, you are right, I was being a little loose: Pall proved in AMM in 1933 that every integer which is 4 (mod 8) and greater than 412 is a sum of 4 distinct odd squares, and we use that as a starting point to show that between 4 and 11 distinct odd squares work for any integer (obviously depending on its congruence (mod 8) ). We also used a 1955 result of Schinzel about sums of 3 squares. – Jul 1 '14 at 7:28
• I should say that as far as the character-theoretic application was concerned, the fact that the number of odd squares was at most 11 was not really necessary- any number would have done, as long as they were distinct odd squares. – Jul 1 '14 at 7:29

Yes, by Lagrange's four-square theorem. More generally, for any $k$ there is an $s$ such that any natural number is the sum of $s$ $k$-th powers, see Waring's problem.

Added 1. Halter-Koch proved in 1982 that any integer greater than 245 is the sum of 5 distinct squares, see Satz 4 here. He also determined which numbers are not the sum of 4 distinct squares (there infinitely many exceptions, but only finitely many exceptions that are not divisible by 4), see Satz 3 here.

Added 2. For representability as a sum of more distinct squares, see the paper by Bateman, Hildebrand, Purdy here. For example, Table I in this paper tells us that any integer greater than 343296 is the sum of 100 distinct squares.

Added 3. It is straightforward to show that for any $d>0$, every sufficiently large $n$ is the sum of squares of 5 natural numbers whose minimal distance is at least $d$. This is because, by the circle method, the number of representations $n=n_1^2+\dots +n_5^2$ is $\gg n^{3/2}$, while the number of representations with $|n_i-n_j|<d$ for some $1\leq i<j\leq 5$ is $\ll_{d,\epsilon} n^{1+\epsilon}$ for any $\epsilon>0$.

• This doesn't address the issue of uniqueness.
– Noah S
Jun 30 '14 at 15:28
• hmm, does that answer the OP's question for any $n$? Jun 30 '14 at 15:28
• The reference to Bateman, Hildebrand, Purdy reminded me of a paper by Montgomery and Vorhauer, which you might also find interesting. The paper is: ams.org/journals/mcom/2004-73-245/S0025-5718-03-01513-8/…
– Lucia
Jun 30 '14 at 15:56
• Small point: The number of representations by a quatenary form may grow like $\sigma(n)$, so you should probably put $\ll_d n^{1+\epsilon}$ for the number of representations with $|n_i-n_j|<d$.
– Lucia
Jun 30 '14 at 19:35
• @Lucia: Thank you! (I have already fixed this before your comment.)
– GH from MO
Jun 30 '14 at 19:36

John Thompson and I proved in a paper about character theory of the Alternating group that for $m > 1922$, it is possible to express $m$ as a sum of at most $11$ distinct odd squares.

• Thus, non-consecutive.
– Felipe Voloch
Jun 30 '14 at 18:55
• Any thoughts on how many such representations a number s could have?
• I expect quite a lot as $n$ gets larger, but I don't have a formal proof of that. Jun 30 '14 at 19:00