# are elementary symmetric polynomials concave on probability distributions?

Let $S_{n,k}=\sum_{S\subset[n],|S|=k}\prod_{i\in S} x_i$ be the elementary symmetric polynomial of degree $k$ on $n$ variables. Consider this polynomial as a function, in particular a function on probability distributions on $n$ items. It is not hard to see that this function is maximized at the uniform distribution. I am wondering if there is a "convexity"-based approach to show this. Specifically, is $S_{n,k}$ concave on probability distributions on $n$ items?

• Specifically, if it is concave on probability distributions, then applying this to a uniform convex combination of a probability distribution and its rotations would yield the above maximization at the uniform distributions. – miforbes Jul 9 '13 at 12:50

(I know this question is ancient, but I happened to run into it while looking for something else.)

While I am not sure if $S_{n,k}$ is concave on the probability simplex, you can prove the result you want and many other similar useful things using Schur concavity. A sketch follows.

A vector $y\in \mathbb{R}_+^n$ majorizes $x \in \mathbb{R}_+^n$ if the following inequalities are satisfied:

$$\sum_{j=1}^i{x_{(j)}} \leq \sum_{j=1}^i{y_{(j)}}$$ for all $i$, and $\sum_{i=1}^n x_i = \sum_{i=1}^n y_i$. Here $x_{(j)}$ is the $j$-th largest coordinate of $x$ and similarly for $y$. Let's write this $x \prec y$. For intuition it's useful to know that $x \prec y$ if and only if $x$ is in the convex hull of vectors you get by permuting the coordinates of $y$.

A function is Schur-concave if $x \prec y \implies f(x) \geq f(y)$. A simple sufficient condition for Schur concavity is that $\partial f(x)/\partial x_i \ge \partial f(x)/\partial x_j$ whenever $x_i \le x_j$. It is easy to verify that $S_{n,k}$ satisfies this condition for any $n$,$k$.

Notice that $x=(1/n, \ldots, 1/n)$ is majorized by every vector $y$ in the probability simplex. You can see this for example by noticing that the sum of $i$ random coordinates of $y$ is $i/n$, so surely the sum of the $i$ largest coordinates is at least as much. Equivalently, $x$ is the average of all permutations of $y$. This observation, and the Schur concavity of $S_{n,k}$ imply $S_{n,k}(x) \ge S_{n,k}(y)$.

In fact, $S_{n,k}^{1/k}$ is concave on the positive orthant, and this implies what you want. This is itself a special case of much more powerful results about the concavity of mixed volumes. But the Schur concavity approach is elementary and pretty widely applicable.

• Thanks Sasho. My hope was for a slick Jensen-type proof, as is done with maximizing Shannon entropy. At some point since my original question, I did come across Schur-convexity (see "Majorization and the Birthday Inequality" by Clevenson and Watkins, jstor.org/stable/2691301 ). I guess this answer is probably this slickest I'll find (assuming that the proof about $S^{1/k}_{n,k}$ being concave you mention is less easy.) – miforbes Jul 4 '15 at 11:10
• I have seen two kinds of proofs that $S_{n,k}^{1/k}$ is concave. Some are elementary (i.e. use little to no heavy machinery) but are long and messy. On the other hand there is a slick proof by Khovanskii math.toronto.edu/askold/1984-Doklady-6-English.pdf of the Alexandrov-Fenchel inequalities for mixed discriminants (and even mixed hyperbolic forms) using hyperbolic polynomials. – Sasho Nikolov Jul 4 '15 at 12:22
• To clarify my comment above: $S_{n,k}$ is a special case of a mixed discriminant, and Alexandrov-Fenchel is equivalent to a concavity property of mixed discriminants that implies the concavity of $S_{n,k}^{1/k}$. Alexandrov-Fenchel for hyperbolic forms is vastly more general than concavity of $S_{n,k}$, but Khovanskii's proof is the only one I have seen that doesn't involve long tedious calculations. Here is one of the elementary proofs I have found: cms.math.ca/cjm/a144993. BTW, cute article about the birthday paradox! – Sasho Nikolov Jul 4 '15 at 14:44
• Thanks! I'll take a look. (Indeed, the birthday paradox was what got into this.) – miforbes Jul 5 '15 at 19:19