Fix a natural number $n\geq 1$. Let $a_1, \ldots, a_n$ be $n$ real numbers such that $a_i>0$ for each $i$. Show that for each natural $k$ with $0\leq k\leq n$ $$e_k(a_1,\ldots, a_n)\geq\binom{n}{k}(a_1\cdot\cdots\cdot a_n)^{k/n}$$ where $e_k(x_1, \ldots, x_n)$ denotes the $k$th symmetric polynomial with $n$ arguments and where we make the convention that $e_0(x_1,\ldots, x_n)=1$.

Here's the proof I gave:

It suffices to prove the claim assuming that $a_1\cdot\cdots\cdot a_n=1$. For if this is not the case, then setting $\overline{a_i}=a_i/(a_1\cdot\cdots\cdot a_n)^{1/n}$ will give $$\overline{a_1}\cdot\cdots\cdot\overline{a_n}=1$$ and the general claim will follow from the fact that $$e_k(\overline{a_1},\ldots,\overline{a_n})=\frac{1}{(a_1\cdot\cdots\cdot a_n)^{k/n}} e_k(a_1,\ldots,a_n)$$

Thus we prove that if $a_1\cdot\cdots\cdot a_n=1$ then $e_k(a_1,\ldots,a_n)\geq\binom{n}{k}$. We induct on $n$ (we go through Pascal's Triangle row-by-row left-to-right). Note that this claim is trivial for $k=0$ or $k=n$. Thus when $n=1$, the claim holds for $k=0$ and $k=n$. Now assume the claim is true for the natural number $m$ and all natural $k$ with $0\leq k\leq m$; we show that the claim is true for the natural number $m+1$ and all natural $k$ with $0\leq k\leq m+1$. Since $$e_0(a_1,\ldots, a_{m+1})=1=\binom{m+1}{0}$$ the claim follows trivially. And since $$e_1(a_1,\ldots, a_{m+1})=a_1+\cdots+a_{m+1}\geq m+1$$ is a special case of the Arithmetic-Geometric Mean Inequality we have that this case holds as well. Without loss of generality we can assume that $a_1\leq \cdots\leq a_{m+1}$. This ordering implies that $a_{m+1}\geq 1$ since a product of numbers strictly greater than 0 and strictly less than 1 cannot multiply to 1. Now note that $$e_{k+1}(a_1\ldots, a_{m+1})=e_{k+1}(a_1,\ldots,a_m)+a_{m+1}e_{k}(a_1,\ldots,a_m)$$ for $1\leq k+1\leq m$. Thus $$e_{k+1}(a_1,\ldots, a_{m+1})\geq\binom{m}{k+1}+a_{m+1}\binom{m}{k}\geq\binom{m}{k+1}+\binom{m}{k}=\binom{m+1}{k+1}$$ And since $e_{m+1}(a_1,\ldots,a_{m+1})=a_1\cdot\cdots\cdot a_{m+1}=1=\binom{m+1}{m+1}$, the claim follows by induction.

Two questions. First, is this proof correct? Second, can someone come up with a slicker proof? Moving through Pascal's Triangle is kind of messy. Perhaps someone knows certain recursive relations between the symmetric polynomials that would make this easier, or other interesting inequalities (I suspect some identity with binomial coefficients will have to be used in another proof).


Your proof is correct. Here is an alternative proof.

As you do we assume $a_1\cdots a_n=1$ and $a_1\leq\cdots\leq a_n$ and prove that $e_k(a_1,\ldots,a_n)\geq\binom{n}{k}$. We do this using Lagrange multipliers, noting that $$\frac{\partial}{\partial x_i}e_k(x_1,\ldots,x_n)=e_{k-1}(x_1,\ldots,\widehat{x_i},\ldots,x_n)$$ We need to solve the system of equations $$e_{k-1}(a_1,\ldots,\widehat{a_i},\ldots,a_n)+\lambda(a_1\cdots\widehat{a_i}\cdots a_n)=0$$ These all hold when $$\lambda=-\frac{e_{k-1}(a_1,\ldots,\widehat{a_i},\ldots,a_n)}{a_1\cdots\widehat{a_i}\cdots a_n}$$ or in other words when $$a_je_{k-1}(a_1,\ldots,\widehat{a_i},\ldots,a_n)=a_ie_{k-1}(a_1,\ldots,\widehat{a_j},\ldots,a_n)$$ for all $i,j$. In this case $$(a_j-a_i)e_{k-1}(a_1,\ldots,\widehat{a_i},\ldots,a_n)+a_i(a_j-a_i)e_{k-2}(a_1,\ldots,\widehat{a_i},\ldots,\widehat{a_j},\ldots,a_n)=0$$ which we can see using the nifty tricks $$ab-cd=(a-c)b+c(b-d)$$ and $$e_{k-1}(a_1,\ldots,\widehat{a_i},\ldots,a_n)-e_{k-1}(a_1,\ldots,\widehat{a_j},\ldots,a_n)=(a_j-a_i)e_{k-2}(a_1,\ldots,\widehat{a_i},\ldots,\widehat{a_j},\ldots,a_n)$$ and this implies that $a_i=1$ for all $i$ because $a_i-a_j$ must be $0$ for all $i,j$. Thus the unique extreme point is where $a_i=1$ for all $i$, at which $$e_k(a_1,\ldots,a_n)=\binom{n}{k}$$ To see that this is a minimum, consider the case where $a_i=N^{-\frac{1}{n-1}}$ for all $i<n$ and $a_n=N$. In that case $$e_k(a_1,a_2,\ldots,a_n)=a_ne_{k-1}(a_1,\ldots,a_{n-1})+e_k(a_1,\ldots,a_{n-1})=N\binom{n-1}{k-1}N^{-\frac{k-1}{n-1}}+N^{-\frac{k}{n-1}}\binom{n-1}{k}\geq N^{\frac{n-k}{n-1}}$$ which increases without bound as $N\to\infty$, except in the case where $k=n$ in which case the function is always $1$ for all choices of $a_1,\ldots,a_n$.

| cite | improve this answer | |

I used this to come up with a slightly more general class of inequalities:

$$\frac{e_k^n(x^\frac{1}{k}_1,...,x^\frac{1}{k}_n)}{{{n}\choose{k}}} \leq \frac{e_{k-1}^n(x^\frac{1}{k-1}_1,...,x^\frac{1}{k-1}_n)}{{{n}\choose{k-1}}}$$

With equality iff $x_1 = x_2 = ... = x_n$

For example, when $n=4$

\begin{align*} \sqrt[4]{x y z w} &\leq \frac{\sqrt[3]{xyz}+\sqrt[3]{xyw}+\sqrt[3]{xwz}+\sqrt[3]{yzw}}{4} \\ &\leq \frac{\sqrt{xy}+\sqrt{xz}+\sqrt{xw}+\sqrt{yz}+\sqrt{yw}+\sqrt{wz}}{6} \\ &\leq \frac{x+y+z+w}{4} \end{align*}

First, when $k=n$, we have $e_n^n(x^\frac{1}{n}_1,...,x^\frac{1}{n}_n) \leq \frac{e_{n-1}^n(x^\frac{1}{n-1}_1,...,x^\frac{1}{n-1}_n)}{n}$, which is proven by you with the mapping $a_i \mapsto a_i^{1/k}$ and $k \mapsto (n-1)$.

Now for $1<k<n$, we have

\begin{align*} \frac{e_k^n(x^\frac{1}{k}_1,...,x^\frac{1}{k}_n)}{{{n}\choose{k}}} &= \sum_{1 \leq j_1 < j_2 < ... < j_k} \frac{e_k^k(x^\frac{1}{k}_{j_1},...,x^\frac{1}{k}_{j_k})}{{{n}\choose{k}}} \\ & \leq \sum_{1 \leq j_1 < j_2 < ... < j_k} \frac{e_{k-1}^k(x^\frac{1}{k-1}_{j_1},...,x^\frac{1}{k-1}_{j_k})}{k{{n}\choose{k}}} \\ &= \sum_{1 \leq j_1 < j_2 < ... < j_k} \sum_{i_{j_1} < i_{j_2} < ... < i_{j_{k-1}}} \frac{e_{k-1}^{k-1}(x^\frac{1}{k-1}_{i_{j_1}},...,x^\frac{1}{k-1}_{i_{j_{k-1}}})}{k{{n}\choose{k}}} \\ &= \sum_{1 \leq j_1 < j_2 < ... < j_{k-1}} (n-k+1)\frac{e_{k-1}^{k-1}(x^\frac{1}{k-1}_{j_1},...,x^\frac{1}{k-1}_{j_{k-1}})}{k{{n}\choose{k}}} \\ &= \frac{e_{k-1}^n(x^\frac{1}{k-1}_1,...,x^\frac{1}{k-1}_n)}{{{n}\choose{k-1}}} \end{align*}

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy