Integer partition and sum of squares - MathOverflow

Integer partition and sum of squares

2012-11-03T01:10:33Z

Hello,

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.

Answer by Felipe Voloch for Integer partition and sum of squares

2012-11-03T02:31:21Z

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

Answer by fedja for Integer partition and sum of squares

2012-11-04T13:16:26Z

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).