Integer partition and sum of squares - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T08:45:40Z http://mathoverflow.net/feeds/question/111328 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111328/integer-partition-and-sum-of-squares Integer partition and sum of squares Portland 2012-11-03T01:10:33Z 2012-11-05T19:48:14Z <p>Hello,</p> <p>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) </p> <p>For all integers $n\geq 2$ denote by $\mathcal{P}(n)$ the set of partitions of $n$, <a href="http://en.wikipedia.org/wiki/Partition_%28number_theory%29" rel="nofollow">see here for a definition</a></p> <p>We say that a postive integer $k$ is <strong><em>$\mathbf{n}$-squarable</em></strong> if there exist $(p_1,\ldots,p_t) \in \mathcal{P}(n)$ such that $k=\sum_{i=1}^t{p_i}^2$.</p> <p>Let $\alpha(n)=\lfloor (n^2-3n)/4\rfloor$.</p> <blockquote> <p>I would like to show that the integers $n, n+2, n+4,\ldots ,n+2\alpha(n)$ are $n$-squarable.</p> </blockquote> <p>If we need to reduce a bit the size of $\alpha(n)$ to make it easier to prove this, I'd happily do that.</p> <p>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).</p> <p>Thank you.</p> http://mathoverflow.net/questions/111328/integer-partition-and-sum-of-squares/111334#111334 Answer by Felipe Voloch for Integer partition and sum of squares Felipe Voloch 2012-11-03T02:31:21Z 2012-11-03T02:31:21Z <p>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$.</p> http://mathoverflow.net/questions/111328/integer-partition-and-sum-of-squares/111459#111459 Answer by fedja for Integer partition and sum of squares fedja 2012-11-04T13:16:26Z 2012-11-04T13:16:26Z <p>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 <code>$a&lt;c$</code> 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, <em>eventually</em>, you can fly to the top. However, the takeoff is pretty bumpy, and is better left to computers.</p> <p>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). </p>