Suppose $x$ is a **unknown** sequence of non-negative integers with $n$ elements and $\sum\_{i=1}^n x\_i = c$ for a constant $c$.


What is the minimum possible value of $\sum\_{i=1}^n x\_i(x\_i-1)(x\_i-2)$?


I know the answer when we want a lower bound for $\sum\_{i=1}^n x\_i(x\_i-1)$. We can expand it and use the *Cauchy-Schwarz Inequality*. But I don't see anything for solving it in this form.


PS: Actually I want a good lower bound over this expression; by good I mean non-trivial ones.



Minimum possible value of $\sum_{i=1}^n x_i(x_i-1)(x_i-2)$ for fixed sum
(Updated as per suggestions in the comments.)


I will use
$$
S[x]\equiv \sum\_{i=1}^n x\_i(x\_i-1)(x\_i-2).
$$
Obviously, $S[x]\geq 0$.


First, let $n=2$, and set $x\_1=c/2+y$ and $x\_2=c/2-y$. Then
$$
\sum\_{i=1}^n x\_i(x\_i-1)(x\_i-2)=\frac{(c-2)(12y^2+c(c-4))}{4}.
$$
This means that for $c>2$ the minimum is achieved for the minimal possible value of $|y|$, which is either $0$ or $\pm \tfrac{1}{2}$ depending on whether $c$ is even or odd, which corresponds to $x\_1=x\_2$ or $x\_1=x\_2\pm 1$.


Now, consider a general $n>1$. Suppose that there is a pair $i,j$ such that $|x\_i-x\_j|>1$. Suppose that $x\_i+x\_j>2$. Then by the above argument, we can alter the values of $x\_i,x\_j$ while preserving $x\_i+x\_j$ to make sure that $|x\_i-x\_j|\leq 1$ and decrease the sum $S[x]$ by doing so. If instead $x\_i+x\_j\leq 2$, then we must have that $x\_i=0$ and $x\_j=2$ or vice versa. Therefore, if $x$ achieves the minimum of $S[x]$, then for every pair $i,j$ we have $|x\_i-x\_j|\leq 1$ or $\{x\_i,x\_j\}=\{0,2\}$. If the latter option holds for at least one pair $i,j$ then, by the former property, the only other value allowed in the sequence is $1$.


The above argument implies that if a sequence $x$ achieves the minimum of $S[x]$, then one of two options hold:


1. $x\_i=a$ or $x\_i=a+1$, $\forall i\in \{1,\cdots,n\}$, for some integer $a$. (This includes the case when all $x\_i$ are identical.)
2. $x\_i\in \{0,1,2\}$, $\forall i\in \{1,\cdots,n\}$.


The second option can only be realized for $c\leq 2n$ in which case the minimum of $S[x]=0$ can be achieved. For $c>2n$ we need to solve the following problem: let $a\geq 0$ and $0\leq q<n$ be integers such that $(n-q)a+q(a+1)=c$. What is the minimal value of $S(q,a)=(n-q)a(a-1)(a-2)+q(a+1)a(a-1)$? (We can assume that $q<n$ since $q=n$ is equivalent to $q=0$ with $a$ replaced by $a+1$.)


The condition $(n-q)a+q(a+1)=c$ is equivalent to $na+q=c$, which uniquely determines $a=\lfloor c/n\rfloor$ and $q=c-na$, which in turn uniquely fixes the value of $S(q,a)$ which gives the tight lower bound.


