# Symmetric polynomial inequality arising from the fixed-point measure of a random permutation

A somewhat strange elementary polynomial inequality came up recently in my work, and I wonder if anyone has seen other things that are reminiscent of what follows.

Given $$n$$ non-negative reals $$a_1, a_2, \dots, a_n \in \mathbb{R}_{\ge 0}$$, define the fixed-point weight $$w(\pi)$$ of a permutation $$\pi \in S_n$$ by $$w(\pi) = \prod_{\{j:j=\pi(j)\}} a_j,$$ where the empty product evaluates to $$1$$ (i.e., derangements get weight 1).

I believe the following inequality to be true, but do not see how to prove it.

Conjecture For $$a_1, a_2, \dots, a_n \ge 0$$, we have $$\mathbb{E}_{\pi \in S_n} [w(\pi)] \ge \mathbb{E}_{\{i,j\} \in\binom{[n]}{2}} [\sqrt{a_i a_j}],$$ where the expectation on the left is uniformly over all permutations $$\pi \in S_n$$ and the expectation on the right is uniformly over all 2-element subsets of $$\{1, \dots, n\}$$.

For example, the conjectural inequality for $$n = 3$$ (when scaled up by a factor of 6) is the claim that for $$a_1, a_2, a_3 \ge 0$$, we have

$$2 + a_1 + a_2 + a_3 + a_1a_2a_3 \ge 2\sqrt{a_1a_2} + 2\sqrt{a_2a_3} + 2 \sqrt{a_1a_3},$$

which I can verify, but not in any way that seems to generalise. Mathematica also tells me that this inequality holds for n = 4, for what it's worth.

1. The left hand side may also be seen as the permanent of the matrix with $$a_1, a_2, \dots, a_n$$ on the diagonal, and 1's off the diagonal. I wonder, but have no idea, if things like the Alexandrov--Fenchel inequalities might be relevant.
2. When all the $$a_i$$ are equal to some $$a$$, the right hand side is just $$a$$, while the left hand side is the expectation of $$a^X$$, where $$X$$ is the number of fixed points of a random permutation, and since $$X$$ has mean $$1$$, the claim follows from Jensen's inequality.
3. The right hand side is clearly the symmetric Muirhead mean of the numbers $$a_1, a_2, \dots, a_n$$ associated with the vector $$(1/2,1/2,0, \dots, 0)$$. The left hand side is a weighted linear combination of the elementary symmetric polynomials (which are themselves Muirhead means as well) in $$a_1, a_2, \dots, a_n$$, with the weights coming from the fixed-point measure of a uniform permutation. It is tempting to appeal to Muirhead's inequality in some form that I might not be seeing (but some of the elementary symmetric polynomials beat the Muirhead mean on the right, and some others don't.)
• A bolder claim that also appears to survive computer verification is as follows. Write each $a_i$ as $b_i^2$ to get rid of square roots, and look at $f(b_1, \dots, b_n)$, the difference between the LHS and the RHS of the conjectural inequality. It appears then that only critical points of $f$ are $(-1,\dots,-1)$, $(0,\dots,0)$ and $(1, \dots, 1)$ -- this claim, if true, should likely settle the original conjecture with a bit of effort.
– BPN
Jan 19, 2022 at 21:32
• For $n=3$ it is true that the multiset $(1,1,a_1,a_2,a_3,a_1a_2a_3)$ log-majorizes the multiset $(\sqrt{a_1a_2},\sqrt{a_1a_2},\sqrt{a_1a_3},\sqrt{a_1a_3},\sqrt{a_2a_3},\sqrt{a_2a_3})$ with the same product. Maybe such majorization holds for larger $n$ too? Jan 20, 2022 at 14:36
• Dear Fedor, I've been looking through the majorisation literature (in vain, it is rather vast) since it seems relevant, but I'm far from an expert. Could you possibly spell out what you mean in a little bit of detail -- does said majorisation imply the inequality?
– BPN
Jan 20, 2022 at 15:59
• @FedorPetrov: This appears to be true! In more elementary terms, you are saying that $\dbinom{n}{2} \cdot \sum\limits_{w \in S_n} \left| \sum\limits_{\substack{j \in \left[n\right];\\ w\left(j\right) = j}} b_j - t\right| \geq n! \sum\limits_{1\leq i<j \leq n} \left|\dfrac{b_i + b_j}{2} - t\right|$ for any $n$ reals $b_1, b_2, \ldots, b_n$ and any real $t$ (where we set $\left[n\right] = \left\{1,2,\ldots,n\right\}$). This seems to hold for some random choices of $b_i$'s for $n$ up to $8$ using Sage. Jan 21, 2022 at 12:22
• Note that the case $n = 3$ of this conjecture says (after simplifying and cancelling $3$) that every four reals $a, b, c, t$ satisfy $2\left|t\right| + \left|a-t\right| + \left|b-t\right| + \left|c-t\right| + \left|a+b+c-t\right| \geq \left|b+c-2t\right| + \left|c+a-2t\right| + \left|a+b-2t\right|$. And this inequality is indeed easy to prove: it follows from the Popoviciu inequality (Theorem 2a in cip.ifi.lmu.de/~grinberg/Popoviciu.pdf , applied to the function $x \mapsto \left|x-t\right|$) and the fact that $2\left|t\right| + \left|a+b+c-t\right| \geq \left|a+b+c-3t\right|$. Jan 21, 2022 at 12:48

Not an answer, just too long for a comment: Set $$a_i=b_i^2$$, and let $$E_n=E_n(b_1,\dots,b_n)$$ be the left hand side minus the right hand side (and multiplied by $$n!$$). The assertion can be verified for $$n=3, 4, 5$$ by squares of polynomials. It is easy to see that $$E_3$$ is not a sum of squares, however \begin{align*} (1+b_1^2b_2^2)E_3 &= 2(1-b_1b_2)^2 + (b_1 + b_2 - b_3-b_1^2b_2^2b_3)^2 + (b_1b_2)^2(b_1 -b_2)^2. \end{align*} Similarly \begin{align*} E_4 &= (b_4b_1 + b_2b_3 - 2)^2 + (b_4b_2 + b_1b_3 - 2)^2 + (b_1b_2 - b_4b_3)^2\\ &\quad + 2(b_3 - b_4)^2 + 2(b_1 - b_2)^2 + (1 - b_1b_2b_3b_4)^2. \end{align*} For $$E_5$$ there is also such an SOS representation over the rationals. However, the ones I found are very messy. (And for $$E_6$$ I only found a real approximation.) The problem is that already for $$n=4$$ such representations are far from unique, so they do not tend to have rational coefficients.
• Your final inequality appears to be violated for $n=3, a_1=a_2=a_3=\frac{1}{2}$ ?