Let $m,n \in \mathbb{N}$ and $m \geq n \geq 2$ and $x_1,x_2,...x_n \in \mathbb{N}_{\geq 1}$ such as $x_1+x_2+...+x_n=m$. Find $\min P$ with $P= \sum_{i=1}^{n} x_i^2.$


closed as off-topic by user9072, fedja, Stefan Kohl, Franz Lemmermeyer, Felipe Voloch Nov 1 '15 at 21:11

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Community, fedja, Franz Lemmermeyer, Felipe Voloch
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Where does this come from? And what do you mean by "find". Obviously one can try all the possibilities... $\endgroup$ – Igor Rivin Nov 1 '15 at 13:59
  • 7
    $\begingroup$ Won't the minimum simply be attained by taking the $x_i$ to be as close to one another as possible. So take some of them equal to $\lfloor m/n\rfloor$ and the others equal to $\lceil m/n\rceil$ to make the sum equal to $m$. $\endgroup$ – Joe Silverman Nov 1 '15 at 14:02
  • $\begingroup$ Solve this using Calculus Lagrange multipliers. The solution will be Joe's solution. $\endgroup$ – Daniel Parry Nov 1 '15 at 14:48
  • 3
    $\begingroup$ So, to be specific, $$P=q^2n+(2q+1)r$$ where $m=nq+r$ with $0 \le r \le m-1.$ The results from taking $r$ of the $x_i$ to be $q+1$ and the remaining $n-r$ to be $q.$ $\endgroup$ – Aaron Meyerowitz Nov 1 '15 at 15:31

This is a low-tech explanation of Joe Silverman's comment (but see also Geoff Robinson's response).

Proposition. The minimum is attained when the variables differ by at most $1$, i.e. when each $x_i$ is either $\lfloor m/n\rfloor$ or $\lceil m/n\rceil$.

Proof. If $x_i-x_j\geq 2$, say, then replacing $x_i$ (resp. $x_j$) by $x_i-1$ (resp. $x_j+1$) yields a better $n$-tuple, because $$(x_i-1)+(x_j+1)=x_i+x_j\qquad\text{but}\qquad (x_i-1)^2+(x_j+1)^2<x_i^2+x_j^2.$$

Remark. Note that the proposition determines a unique $n$-tuple for the minimum, namely the number of $\lfloor m/n\rfloor$'s and $\lceil m/n\rceil$'s is determined by the residue of $m$ modulo $n$.

  • 1
    $\begingroup$ Clean,and better than what I said! $\endgroup$ – Geoff Robinson Nov 1 '15 at 15:40

It is hard to find a precise answer, since there are some choices of $m,n$ which are easier than others . Lagrange's identity gives $\left( \sum_{i} x_{i}\right)^{2} + \sum_{i<j} (x_i -x_j)^{2} = n P$, which is relevant.


This is a quadratic integer linear programming problem, see this 2014 paper (by Christian Bliekú, Pierre Bonami , and Andrea Lodi) for a survey of what is known. (this problem is positive definite, so not as hard as the hardest case).


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