# Maximum of $\sum_{i\neq j} n_in_j$

Let $\{n_i\}_{i=1}^k$ be $k$ natural number so that $\sum_{i=1}^k n_i=n$. Then what is the maximum of $\sum_\limits{i\neq j} n_in_j$?

Because \begin{align} \sum_{i\ne j}n_in_j &=\left(\sum_{i=1}^kn_i\right)^2-\sum_{i=1}^kn_i^2\\ &=n^2-\sum_{i=1}^kn_i^2 \end{align} So maximizing $\sum\limits_{i\ne j}n_in_j$ is equivalent to minimizing $\sum\limits_{i=1}^kn_i^2$.

By Hölder's Inequality, \begin{align} k\sum_{i=1}^kn_i^2 &=\sum_{i=1}^k1^2\sum_{i=1}^kn_i^2\\ &\ge\left(\sum_{i=1}^kn_i\right)^2\\[9pt] &=n^2 \end{align} and we can realize this minimum by letting $n_i=\frac nk$.

However, $n_i$ are supposed to be integers, so we need to make a small adjustment. Although we may not be able to set $n_i=\frac nk$ since this might not be an integer, we must have that $|n_i-n_j|\le1$. Suppose not, and that for some $i,j$, we have that $n_i-n_j\gt1$. Then $$n_i-n_j-1\gt0$$ and therefore \begin{align} (n_i-1)^2+(n_j+1)^2 &=n_i^2+n_j^2-2(n_i-n_j-1)\\ &\lt n_i^2+n_j^2 \end{align} which means that $n_i$ and $n_j$ are not part of a minimal arrangement. Thus, we must have $|n_i-n_j|\le1$. This implies that $n-k\left\lfloor\frac nk\right\rfloor$ of the $n_i$ must equal $\left\lfloor\frac nk\right\rfloor+1$ and the rest must equal $\left\lfloor\frac nk\right\rfloor$.

Thus, with this minimal arrangement for the sum of the squares, we get \begin{align} \sum_{i\ne j}n_in_j &=n^2-\sum_{i=1}^kn_i^2\\ &\le n^2-k\left\lfloor\frac nk\right\rfloor^2-\left(n-k\left\lfloor\frac nk\right\rfloor\right)\left(2\left\lfloor\frac nk\right\rfloor+1\right)\\ \end{align}

• How are you sure that $n_i=n/k$ is a natural number? – A.Γ. Oct 17 '17 at 17:11
• @A.Γ.: That should be handled now. – robjohn Oct 18 '17 at 10:00

You can rework the expression: $$\sum_{i\neq j} n_i n_j = \sum_i n_i \sum_j n_i - \sum_i n_i^2 = n^2 - \sum_i n_i^2,$$ so the problem can be addressed by minimizing $\sum_i n_i^2$ under the same constraint.

Clearly, for the optimal solution $$\max_{i,j} |n_i - n_j| \leq 1.$$ Indeed, if it weren't the case, the value of the sum could be decreased by moving a unit from the greatest $n_i$ to the lowest. Clearly, one of the optimal solutions is such that the $l$ first numbers are be equal to $a+1$ and the rest are equal to $a$. Then $$\sum_i n_i = l (a+1) + (k-l) a = ka + l.$$ The optimal values are $a = n/k$ (integer division), $l = n\%k$ (remainder of the integer division). So the minimal value of $\sum_i n_i^2$ is equal to $$(n\%k)(n/k+1)^2 + (k-n\%k)(n/k)^2$$ and $$\min \sum_{i\neq j}n_i n_j = n^2 - (n\%k)(n/k+1)^2 - (k-n\%k)(n/k)^2.$$ Note that when $n\%k = 0$, one recovers the solution that I had found previously in the unconstrained case, i.e. $$n^2 - n^2/k$$ (see the edit history of this post for details)

• Why do you think that $n_i=n/k$ is a natural number? – A.Γ. Oct 16 '17 at 16:17
• woops, I had skipped the work "natural"... – Roberto Rastapopoulos Oct 16 '17 at 16:18
• Should be fixed now. :) – Roberto Rastapopoulos Oct 16 '17 at 16:38