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.

Some additional remarks.

- 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.
- 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.
- 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.)

onlycritical 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. $\endgroup$3more comments