# Proof of an (Elementary) Inequality Involving Elementary Symmetric Polynomials

Let $$x_1,\dots, x_n$$ be $$n$$ variables. For brevity I'll use the following notation: for $$I \subset \{1,\dots , n\}$$ define $$x_I := \prod_{i \in I} x_i.$$ Let $$e_k(x_1,\dots, x_n)$$ be an elementary symmetric polynomial. That is $$e_k(x_1,\dots, x_n) = \sum_{\substack{I \in \binom{[n]}{k}}} x_I.$$ Suppose that we have the following conditions on $$x_1,\dots, x_n$$: $$\sum_{i=1}^n x_i = 1 \qquad \text{and} \qquad x_i \geq 0$$ I have been trying to prove the following inequality without Lagrange multipliers: $$e_k(x_1,\dots x_n) \leq \frac{\binom{n}{k}}{n^{k}}$$

(1) I have made an (albeit feeble) attempt using AM-GM. Any hints on how one might proceed without Lagrange Multipliers would be very much appreciated.

(2) Additionally, when one does use Lagrange Multipliers I have been having trouble arguing that the maximum does indeed occur when $$x_1 = \cdots = x_n = \frac{1}{n}.$$

• For $k=2$, you have $2e_2=(\sum_k x_k)^2-\sum_k x_k^2=1-\sum_k x_k^2$. Next, Cauchy-Schwarz gives us $||X||^2||Y||^2 \geq <X,Y>^2$ where $X=(x_1,\ldots,x_n)$ and $Y=(1,\ldots,1)$, so $(n^2)\sum_k x_k^2 \geq (\sum_k x_k)^2=1$ with equality iff $X$ and $Y$ are proportional. So, the $k=2$ case is finished. Jan 21, 2023 at 8:42
• @JazzGuitar7 Since variables $x_1,\cdots, x_n$ are basically free, Lagrange multipliers does not help more than taking derivative directly. Jan 22, 2023 at 3:46

You can proceed by induction over $$n$$. The claim holds for $$n=1$$. Since

$$e_k(x_1,\ldots,x_{n+1})=e_k(x_1,\ldots,x_n)+x_{n+1}e_{k-1}(1,\ldots,x_n)\;,$$

assuming that the claim holds for $$n$$ and maximizing this for fixed $$x_{n+1}$$ by scaling the constraint in the claim for $$n$$ by $$1-x_{n+1}$$ shows that the maximum is

$$\frac{\binom nk}{n^k}(1-x_{n+1})^k+x_{n+1}\frac{\binom n{k-1}}{n^{k-1}}(1-x_{n+1})^{k-1}\\=\frac{\binom nk}{n^k}(1-x_{n+1})^{k-1}\left(1-x_{n+1}+\frac{kn}{n-k+1}\cdot x_{n+1}\right)\;.$$

Setting the derivative with respect to $$x_{n+1}$$ to zero yields

$$-(k-1)\left(1-x_{n+1}+\frac{kn}{n-k+1}\cdot x_{n+1}\right)+(1-x_{n+1})\left(\frac{kn}{n-k+1}-1\right)=0\;.$$

You can check by substitution that the solution is $$x_{n+1}=\frac1{n+1}$$ as required.

• Nice. Since what you are maximizing is a product, perhaps there is a nice rewriting of it as another product, that allows to show the result using only AM-GM and not the derivative Jan 21, 2023 at 10:48

All $$x_i$$ are nonnegative. For brevity, I will write $$e_k(x_1,\cdots, x_n)$$ as $$e_{n,k}$$ when the variables are $$x_1,\cdots, x_n$$.

### First proof, a refined inequality.

Let $$f$$ be a sequence of nonincreasing positive integers $$(f_1, \cdots, f_\ell)$$ such that $$\sum_if_i=k$$. Consider all distinct terms of the form $$x_{i_1}^{f_1}x_{i_2}^{f_2}\cdots x_{i_\ell}^{f_\ell}$$ where $$\{i_1,i_2,\cdots, i_\ell\}$$ is a subset of $$[n]$$ with $$\ell$$ elements. The sum of all those terms is called the monomial symmetric polynomial of type $$f$$ over $$x_1, \cdots, x_n$$, denoted by $$m_{n,f}$$.

For example, $$m_{4,\{2,1\}}=x_1^2x_2+x_1^2x_3+x_1^2x_4$$ $$+x_2^2x_1+x_2^2x_3 + x_2^2x_4$$ $$+x_3^2x_1+x_3^2x_2+ x_3^2x_4$$ $$+x_4^2x_1+x_4^2x_2+x_4^2x_3$$. The basic symmetrical polynomail $$e_{n,k}$$ is none other than $$m_{n,\underbrace{\{1,1,\cdots,1\}}_{k\ 1's}}$$, which has $$n\choose k$$ terms.

A refined inequality: Let $$m_{n,f}$$ be a monomial symmetric polynomial with $$\sum_{f_i\in f}f_i=k\le n$$. Then $$\frac{m_{n,f}}{\|m_{n,f}\|}\ge \frac{e_{n,k}}{\|e_{n,k}\|}$$ where $$\|p\|$$ is the number of terms in a monomial symmetric polynomial $$p$$. The equality holds if either $$m_{n,f}=e_{n,k}$$ or all terms in $$m_{n,f}$$ are equal (which means either all terms are zero or all $$x_i$$ are equal).

This is the special case of Muirhead inequality with $$b=(1,1,\cdots,1,0,0,\cdots,0)$$, where there are $$k$$ $$1$$'s and $$n-k$$ $$0$$'s in $$b$$.

Explanation of a proof: Let me illustrate the simple idea of the proof in the the special case of $$n=4, f=(2,1)$$, $$\frac{m_{4,\{2,1\}}}{12}\ge \frac{e_{4,3}}4$$. By AM-GM, we have the following. $$\frac{x_1^2x_2+x_1^2x_3+x_2^2x_1+x_2^2x_3+x_3^2x_1+x_3^2x_2}6\ge x_1x_2x_3$$ $$\frac{x_1^2x_2+x_1^2x_4+x_2^2x_1+x_2^2x_4+x_4^2x_1+x_4^2x_2}6\ge x_1x_2x_4$$ $$\frac{x_1^2x_3+x_1^2x_4+x_3^2x_1+x_3^2x_4+x_4^2x_1+x_4^2x_3}6\ge x_1x_3x_4$$ $$\frac{x_2^2x_3+x_2^2x_4+x_3^2x_2+x_3^2x_4+x_4^2x_2+x_4^2x_3}6\ge x_2x_3x_4$$ Adding them together, we get the desired specialized inequality.

For general $$n$$ and $$f$$, we can apply AM-GM to all terms in $$m_{n,f}$$ that only involve $$x_{i_1},x_{i_2},\cdots,x_{i_k}$$, for the term $$x_{i_1}x_{i_2}\cdots x_{i_k}$$. Adding all inequalities thus obtained for every term in $$e_{n,k}$$, we will prove the inequality. The actual computation is omitted here.

The refined inequality above says that for any monomial symmetric polynomial over $$x_1,\cdots, x_n$$ of any type, the average of its terms is no less than the average of terms in $$e_{n,k}$$. Since (the expansion of) $$(\sum_ix_i)^k$$ is a positive linear combination of those kinds of polynomials, the average of all $$n^k$$ terms in it is no less than the average of terms in $$e_{n,k}$$. That is $$\frac{(\sum_ix_i)^k}{n^k}\ge \frac{e_{n,k}}{n\choose k}.$$ The equality holds if $$k=1$$ or each $$x_i$$ is $$\frac1n$$. If the equality holds, then $$\frac{m_{n, \{k\}}}n=e_{n,k}$$, which implies $$k=1$$ or all $$x_i$$ are equal, i.e., to $$\frac1n$$.

### Second proof, induction on the number of variables

Claim. For nonnegative numbers $$x_1, \cdots, x_n$$ and integer $$1\le k\le n$$, we have $$e_{n,k} \leq \binom{n}{k}\left(\frac{\sum_i x_i}n\right)^{k}$$ where the equality holds iff $$k=1$$ or all $$x_i$$'s are equal. The inequality in the question is the case when $$\sum_ix_i=1$$.

Let us prove the claim by induction on $$n$$. The base case when $$n=1$$ is trivial.

Suppose it is true for smaller $$n$$. Assume $$n\ge2$$. Assume $$k\ge2$$; otherwise with $$k=1$$, the situation is trivial. Let $$S=\sum_{i=1}^n x_i$$.

\begin{aligned} e_{n,k}&=e_{n-1,k-1}x_n+ e_{n-1,k}\\ &\le \binom{n-1}{k-1}\left(\frac{S-x_n}{n-1}\right)^{k-1}x_n + \binom{n-1}{k}\left(\frac{S-x_n}{n-1}\right)^{k}\\ &= \frac1k\binom{n-1}{k-1}\left(\frac1{n-1}\right)^{k}(S-x_n)^{k-1}(k(n-1)x_n+(n-k)(S-x_n))\\ &= \frac1k\binom{n-1}{k-1}\left(\frac1{n-1}\right)^{k}(S-x_n)^{k-1}((k-1)nx_n+(n-k)S)\\ \end{aligned} where the inequality above comes from the induction hypothesis. \begin{aligned} (S-x_n)^{k-1}&((k-1)nx_n+(n-k)S)\\ &=\frac1{n^{k-1}}(n(S-x_n))^{k-1}((k-1)nx_n+(n-k)S)^1\\ &\le \frac1{n^{k-1}}\left(\frac{(k-1)\cdot n(S-x_n)+1\cdot((k-1)nx_n+(n-k)S)}{k}\right)^k\\ &= \frac1{n^{k-1}}\left((n-1)S\right)^k \end{aligned} where the inequality is the AM-GM inequality. So, $$e_{n,k}\le\frac1k\binom{n-1}{k-1}\left(\frac1{n-1}\right)^{k}\frac1{n^{k-1}}\left((n-1)S\right)^k={n\choose k}\left(\frac Sn\right)^k$$

The equality in the inequality holds iff $$x_1,\cdots, x_{n-1}$$ are all equal by induction hypothesis and $$n(S-x_n)=(k-1)nx_n+(n-k)S$$ from AM-GM, which means $$x_n=\frac S{n}$$. Hence, we must have $$x_i=\frac Sn$$ for all $$i$$. Induction on $$n$$ is complete.

### Third proof, assuming the maximum can be reached.

Suppose $$e_k(x_1,\dots x_n)$$ reaches the maximum when $$(x_1, \cdots, x_n)=(a_1, \cdots, a_n)$$. WLOG assume $$n\ge3$$ and $$a_1\le a_2\cdots\le a_n$$.

Since $$e_k(a_1,\dots, a_n)\ge e_k(\frac1n,\frac1n,\cdots,\frac1n)>0$$, we must have $$e_{k-2}(a_2, a_3, \cdots, a_{n-1})>0$$. .

If $$a_1, then $$e_k(\frac{a_1+a_n}2, a_2,a_3, \cdots, a_{n-1}, \frac{a_1+a_n}2)-e_k(a_1,\cdots, a_n)\\=e_{k-2}(a_2, a_3, \cdots, a_{n-1})\left(\frac{a_n-a_1}2\right)^2>0,$$ which contradicts with the maximality of $$e_k(a_1,\cdots, a_n)$$. Hence $$a_1=a_n$$, i.e., all $$a_i$$ are equal. The wanted inequality follows easily.

This proof is basically a copy of Ewan Delanoy's answer.

Here is yet another proof. Let $$i\lt j$$ be any two indices in $$[|1..n|]$$. Denote by $$t_1 \lt t_2 \lt\ldots,t_{n-2}$$ the other indices in $$[|1..n|]$$ and let $$y_k=x_{t_k}$$.

We can write

$$e_k(x_1,\ldots,x_n)=e_{k}(y_1,\ldots,y_{n-2})+e_{k-1}(y_1,\ldots,y_{n-2})(x_i+x_j)+ e_{k-2}(y_1,\ldots,y_{n-2})x_ix_j$$

From this, we see that if $$(x_i,x_j)$$ is replaced by $$(\frac{x_i+x_j}{2},\frac{x_i+x_j}{2})$$, the sum stays the same but the product gets larger, so we get a larger value. In fact, we get a strictly larger value, unless all the coordinates are zero (indeed, if $$e_{k-2}(y_1,\ldots,y_{n-2})=0$$, then all the monomials appearing in it must also be zero, hence $$e_{k-1}(y_1,\ldots,y_{n-2})=0$$ and $$e_k(x_1,\ldots,x_n)=0$$ also).

In particular, if $$(x_1,\ldots,x_n)$$ is a point where the maximum is attained, we must have $$x_i=x_j$$. Since this holds for any two indices, all the coordinates are equal, and the rest is easy.