# Find the maximum of $\sum \limits_{i<j<k}x_{i}x_{j}x_{k}(x_{i}+x_{j}+x_{k})$

Question:

Find the maximum of the value $$F=\sum_{1\le i<j<k\le n}x_{i}x_{j}x_{k}(x_{i}+x_{j}+x_{k})$$ over all $n -$tuples $(x_1, \ldots, x_n),$ satisfying $x_i \geq 0$ and $\sum_{i=1}^{n} x_i =1.$

if we find following the maximum of the value $$G=\sum_{i<j}x_{i}x_{j}(x_{i}+x_{j})$$ Following is solution $$\sum_{1\le i<j\le n}x_{i}x_{j}(x_{i}+x_{j})=\sum_{i\ne j}x^2_{i}x_{j}=\sum_{i,j=1}^{n}x^2_{i}x_{j}-\sum_{i=1}^{n}x^3_{i}=\sum_{i=1}^{n}x^2_{i}(1-x_{i})\le\dfrac{1}{4}\sum_{i=1}^{n}x_{i}=\dfrac{1}{4}$$ if and only if $x_{1}=x_{2}=\dfrac{1}{2}.x_{3}=x_{4}=\cdots=x_{n}=0$

so I odeled on the binary thinking of speculation,$F\le\dfrac{1}{27}?$

when $x_{1}=x_{2}=x_{3}=\dfrac{1}{3},x_{4}=x_{5}=\cdots=x_{n}=0$, However for $4\le n\le 9$,let $x_{1}=x_{2}=\cdots=x_{n}=\dfrac{1}{n}$,I get $F=\dfrac{\binom{n-1}{2}}{n^3}$.when $n=4$,then $F=\dfrac{3}{64}>\dfrac{1}{27}$.then I can't which maximum for $F$

• compare to IMO1999 problem 2 cs.cornell.edu/~asdas/imo/imo/isoln/isoln992.html – Fedor Petrov Feb 17 '17 at 7:07
• I voted to close : this is a basic problem in optimization that can be solved by using standard techniques of differential calculus. – Paul Broussous Feb 17 '17 at 9:29
• @PaulBroussous I disagree. Standard techniques reduce it to a system of polynomial equations whose solution is not obvious. – Neil Strickland Feb 17 '17 at 9:50
• Numerical investigation (for $n\leq 10$) suggests that the maximum is always $3/64$, attained at points where four of the $x_i$ are $1/4$ and the rest are zero. The constraints $x_i\geq 0$ are definitely needed for this to be true. Maple can solve the relevant equations exactly for $n\leq 6$, but not for $n=7$. – Neil Strickland Feb 17 '17 at 9:58
• @NeilStrickland Starting from $n=5$ there is a larger maximum $\frac6{125}$, attainable with five of the $x_i$ equal to $\frac15$ and the rest zero. – მამუკა ჯიბლაძე Feb 17 '17 at 10:16

Look at a point of maximum. If one of the variables equals 0, we deal with $n-1$ instead $n$. If all are positive, by Lagrange multipliers the partial derivatives in all variables are equal. Look at a partial derivative in $x_n$, it is $$2x_n\left(\sum_{i<j<n} x_ix_j\right)+\sum_{i<j<n}x_ix_j(x_i+x_j)=\\=2x_n(\sigma_2-x_n(\sigma_1-x_n)))+S-x_n^2(\sigma_1-x_n)-x_n(p_2-x_n^2),$$ where $\sigma_1=\sum x_i,\sigma_2=\sum_{i<j} x_ix_j,p_2=\sum x_i^2,S=\sum_{i<j} x_ix_j(x_i+x_j).$ We see that $x_n$ as all other $x_i$'s are the roots of the same cubic equation $$4x^3-3\sigma_1 x^2+(2\sigma_2-p_2)x={\rm const},$$ thus they take at most three different values.
Assume that they take three distinct values $a,b,c$ with multiplicities $\alpha,\beta,\gamma$. By Vieta theorem for the above cubic we get $a+b+c=3\sigma_1/4=3/4(\alpha a+\beta b+\gamma c)$, and without loss of generality we may suppose that $\gamma=1$, i.e., $c=(3\alpha-1)a+(3\beta-1)b$. Substitute it to $ab+bc+ac=2\sigma_2-p_2=\sigma_1^2-2p_2$ we quickly get a contradiction (please check this).
Now assume that $x_i$'s take two different values $a$, $b$ with multiplicities $\alpha,\beta$. We have $4(a^3-b^3)+(\sigma_1^2-2p_2)(a-b)=3\sigma_1(a^2-b^2)$, dividing by $a-b$ we get $$(4-5\alpha+\alpha^2)a^2+(4-5\beta+\beta^2)b^2=(3\alpha+3\beta-2\alpha\beta-4)ab.$$ It is not hard to see that this is impossible when $\alpha\geqslant 4$, $\beta\geqslant 4$. If, say, $\alpha=1$, we get $b=\beta-4$, so this is possible for $n-1=\beta\geqslant 6$, the value of our sum equals $\beta(\beta-1)(\beta-3)/(32(\beta-2)^3)$, worse than $6/125$.The cases when $\alpha=2$ and $\alpha=3$ are computationally painful, but it looks that again the value is less than $6/125$.
• Just to tidy this up a bit, we have $\sigma_1=1$ and $p_2=\sigma_1^2-2\sigma_2=1-2\sigma_2$, so the cubic is $4x^3-3x^2+(4\sigma_2-1)x=\text{constant}$ – Neil Strickland Feb 17 '17 at 11:37