# Integer minimizers of sum of squares given sum constraint

"Given positive integers $$k,n$$ and nonnegative integers $$x_1,x_2,...,x_n$$ satisfying $$x_1 + x_2 + \dots+ x_n = k$$, is it true that $$x_1^2+x_2^2+\dots+x_n^2$$ is minimized if and only if $$|x_i-x_j|\leq1$$ for all $$i,j$$ ?"

Hello. I am reading one paper where I am not sure how to deal with this part. So basically, we want to distribute $$k$$ identical objects into $$n$$ identical boxes, and minimize the sum of squares of the numbers of objects in the boxes. So I denote the number of objects by $$x_i$$ and formulate the problem above. It is claimed that when the distribution is as even as possible, then the sum of squares of $$x_i$$'s is minimized.

This does look intuitively true (or does it?), but I am not sure how to prove this if it is true.

This feels like a constrained integer least square problem but I never studied it. What I tried is to use AM-QM inequality to have a bound by first changing the above absolute value into $$(x_i - x_j)^2\leq 1$$ and then expanding this and summing all over the pairs, but I only get a lower bound $$\frac{k^2}{n}$$ and an upper bound $$\frac{k^2}{n} + \frac{n-1}{2}$$. Perhaps pigeonhole then can be used to find some pairs of $$i,j$$ with $$|x_i - x_j|\geq2$$ for some pair, but I am still stuck.

Trying to be exact, the most even distribution must be like $$k = (q+1)r+q(n-r)$$ where $$q,r$$ are the quotient,remainder in the division algorithm. I could not proceed any further. In general, I think instead of finding the exact minimum, we only need to show that if $$|x_i - x_j|\geq 2$$, then the sum is greater than when we use the most even distribution. This way the two directions of the statement are handled simultaneously.

Any suggestion is appreciated. Thanks!

Hint

Suppose that $$x \ge y +2$$ are integers. Then $$(x-1)^2 + (y+1)^2= x^2+y^2-2(x-y)+2 \lt x^2+y^2$$

If the difference between the elements of an ordered pair of integers is greater or equal to two, you can find an ordered pair having the same sum, a difference decreased by two and such that the sum of their squares is less than the initial sum of squares.

Based on that fact, you can derive a proof by induction of your result.

• @user10354138 Yes for sure! Typo corrected. Aug 12, 2021 at 11:41