4
$\begingroup$

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}} $$

I have had two difficulties:

(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}. $$

Thanks in advance for your help.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 21, 2023 at 8:42
  • 1
    $\begingroup$ @JazzGuitar7 Since variables $x_1,\cdots, x_n$ are basically free, Lagrange multipliers does not help more than taking derivative directly. $\endgroup$
    – Apass.Jack
    Jan 22, 2023 at 3:46

4 Answers 4

5
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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 $\endgroup$ Jan 21, 2023 at 10:48
4
$\begingroup$

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<a_n$, 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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

Your inequality follow immediately from the Maclaurin's inequality.

The Maclaurin inequality we can prove by the Rolle's theorem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .