Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


The question below might be well known, and using different words (I made these up, I'm not a number theorist or specialist in combinatorics)

For all integers $n\geq 2$ denote by $\mathcal{P}(n)$ the set of partitions of $n$, see here for a definition

We say that a postive integer $k$ is $\mathbf{n}$-squarable if there exist $(p_1,\ldots,p_t) \in \mathcal{P}(n)$ such that $k=\sum_{i=1}^t{p_i}^2$.

Let $\alpha(n)=\lfloor (n^2-3n)/4\rfloor$.

I would like to show that the integers $n, n+2, n+4,\ldots ,n+2\alpha(n)$ are $n$-squarable.

If we need to reduce a bit the size of $\alpha(n)$ to make it easier to prove this, I'd happily do that.

Also, given $n$ and $k$ as above, could we find a "constructive" algorithm that would find a partition of $n$ verifying $k=\sum_{i=1}^t{p_i}^2$ (without calculating all elements of $\mathcal{P}(n)$ and then doing a search, obviously).

Thank you.

share|improve this question
is there a special reason why you consider numbers with the same parity of $n$? (i.e. why not $n,n+1,n+2,n+3,\dots$?) –  Pietro Majer Nov 3 '12 at 12:33
@Pietro $\sum p_i \equiv \sum p_i^2 \mod 2$. –  Felipe Voloch Nov 3 '12 at 13:08
add comment

2 Answers

Every integer is a sum of three triangular numbers (Gauss). Let $k > n$ be given with $k-n$ even. Then $(k-n)/2 = r(r-1)/2+s(s-1)/2+t(t-1)/2$, so $k = n -(r+s+t) + r^2+s^2+t^2$. If $n > r+s+t$, then $1,1,\ldots,1$ ($n -(r+s+t)$ times), $r,s,t$ is a partition of $n$ with squares summing to $k$. Clearly $r+s+t = O(\sqrt k)$ so you get an $\alpha(n) \ge cn^2$. I am not sure if the constant $c$ here is $1/4$.

share|improve this answer
This should work for all $k\le \frac{n^2}{3}-3$ by Cauchy-Schwarz. –  Gjergji Zaimi Nov 3 '12 at 3:08
@Gjergji, what do you mean exactly by "This should work"? –  Portland Nov 3 '12 at 23:34
add comment

Let $N$ be the number you want to get as a sum of squares. Let $k$ be the first number to square. Then $N$ is $n$-squareable if $N-k^2$ is $n-k$ squareable, right? Now let's play the usual game. Suppose we want to show that all numbers from $n$ to $A(n)$ of correct parity are $n$-squareable and know it for $n\le m-1$. Let $m\le N\le A(m)$. We should be able to find $k$ such that $m-k\le N-k^2\le A(m-k)$. Trying $k=1$, we see that we can assume $N>A(m-1)$. Then we can go up to $k=[\sqrt{A(m-1)-m+1}]=q(m)$ for sure. Thus, we can take $A(m)=A(m-k)+k^2$ with any $k$ up to $q(m)$. Let now $c^2=\liminf_{m\to\infty}m^{-2}A(m)$. Then we can take $k>am$ with any $a<c$ eventually and get $c^2\ge c^2+c^2(1-c)^2$ whence $c=1$. Well, formally I need to show that $c>0$ to claim that, but this is not hard. First, you check that $A(m)\ge 2m-1$ by replacing $1^2+1^2$ with $2^2$ a few times and then use $k$ up to $m/5$, say, as the first square and see that you can add anything from $m-k$ to $2m-2k-1$ to it and the resulting intervals overlap as long as $2k-1+m-k\le 2m-2k+1$, which is OK with $k\approx \frac m4$. Thus, eventually, you can fly to the top. However, the takeoff is pretty bumpy, and is better left to computers.

This is constructive enough, though will require "special considerations" for small $m$ (up to $50$ or so if you are aiming exactly at what you wrote).

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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