3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$?) $\endgroup$ Nov 3, 2012 at 12:33
  • 1
    $\begingroup$ @Pietro $\sum p_i \equiv \sum p_i^2 \mod 2$. $\endgroup$ Nov 3, 2012 at 13:08

2 Answers 2

5
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ This should work for all $k\le \frac{n^2}{3}-3$ by Cauchy-Schwarz. $\endgroup$ Nov 3, 2012 at 3:08
  • $\begingroup$ @Gjergji, what do you mean exactly by "This should work"? $\endgroup$
    – Portland
    Nov 3, 2012 at 23:34
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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