Elementary symmetric polynomials under the fixed point measure

Ayush Khaitan, Ishan Mata, Bhargav Narayanan · 2025

Read Elementary symmetric polynomials under the fixed point measure by Ayush Khaitan, Ishan Mata, Bhargav Narayanan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-12178.txt.

Introduction

Ayush Khaitan, Ishan Mata, and Bhargav Narayanan prove a surprising inequality in this 2025 arXiv paper in combinatorics. The setting joins two classic objects: elementary symmetric polynomials, which average products of numbers, and random permutations, the shuffles of a list. The fixed point measure weights each shuffle by the numbers sitting in the spots the shuffle leaves unmoved.

Under that weighting, the authors show the average product over fixed points beats a certain average over all pairs of spots. The bound cannot be improved, since cases exist where equality nearly holds. To prove it, they build a set of differential operators that drive a steady flow, pushing the quantities until the inequality becomes clear. Such exact results are rare in this corner of probability, and the flow method may serve other problems.

Catalog record

CREATORAyush Khaitan, Ishan Mata, Bhargav Narayanan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-12178

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Elementary symmetric polynomials under the fixed point measure Ayush Khaitan, Ishan Mata, Bhargav Narayanan Abstract . We identify a surprising inequality satisfied by elementary symmetric polynomials under the action of the fixed point measure of a random permutation. Concretely, for any collection of n n non-negative real numbers a 1 , … , a n ∈ ℝ ≥ 0 a_{1},\dots,a_{n}\in\mathbb{R}_{\geq 0} , we prove that 1 n ! ∑ π ∈ S n [ ∏ { i : i = π ⁡ ( i ) } a i ] ≥ 1 ( n 2 ) ∑ S ∈ ( [ n ] 2 ) [ ( ∏ { i ∈ S } a i ) 1 / 2 ] , \frac{1}{n!}\sum_{\pi\in S_{n}}\left[\prod_{\{i:i=\pi(i)\}}a_{i}\right]\geq\frac{1}{\binom{n}{2}}\sum_{S\in\binom{[n]}{2}}\left[\left(\prod_{\{i\in S\}}a_{i}\right)^{1/2}\right], and this bound is sharp. To prove this elementary inequality, we construct a collection of differential operators to set up a monotone flow that then allows us to establish the inequality. 2010 Mathematics Subject Classification Primary 05A20; Secondary 05E05, 15A15 1. Introduction For integers 0\leq k\leq n , the elementary symmetric polynomial e_{k}(\mathbf{x}) in the variables \mathbf{x}=(x_{1},\dots,x_{n}) is defined by e_{k}(\mathbf{x})=\sum_{S\in\binom{[n]}{k}}\prod_{i\in S}x_{i}, and its normalised counterpart s_{k}(\mathbf{x}) is given by s_{k}(\mathbf{x})=e_{k}(\mathbf{x})/\binom{n}{k} ; here, we write \binom{[n]}{k} for the family of k -element subsets of [n]=\{1,\dots,n\} , and as is standard, interpret any product over the empty set as being one, so that e_{0}(\mathbf{x})=s_{0}(\mathbf{x})=1 . Inequalities involving the elementary symmetric polynomials are a classical subject of study. To give but two famous examples, for any sequence \mathbf{a}=(a_{1},\dots,a_{n}) of non-negative reals, a well-known theorem of Newton asserts that the sequence \{s_{k}(\mathbf{a})\}_{k=0}^{n} is log-concave, and this in turn implies another well-known result of Maclaurin that the sequence \{(s_{k}(\mathbf{a}))^{1/k}\}_{k=1}^{n} is non-increasing; for a survey of these and other related results, see [ 2 , 5 ] . In this paper, we shall prove a new inequality involving the elementary symmetric polynomials, one that arises from the action of the fixed point measure of a random permutation on these polynomials. Writing \fix(\pi) for the set of fixed points of a permutation \pi:[n]\to[n] and S_{n} for the symmetric group over [n] , our main result is as follows. Theorem 1.1 . For any collection \mathbf{a}=(a_{1},\dots,a_{n}) of n\geq 2 non-negative reals, we have (1) \mathbb{E}_{\pi\in S_{n}}\left[\prod_{i\in\fix(\pi)}a_{i}\right]\geq\mathbb{E}_{S\in\binom{[n]}{2}}\left[\left(\prod_{i\in S}a_{i}\right)^{1/2}\right], where both expectations are over the respective uniform measures; furthermore, provided n\geq 3 , equality holds if and only if a_{i}=1 for all 1\leq i\leq n . In terms of the rencontres numbers D(n,k) that count the number of permutations of an n -element set with exactly k fixed points, Theorem 1.1 may be reformulated as follows: for any collection \mathbf{a}=(a_{1},\dots,a_{n}) of n non-negative reals, we have \sum_{k=0}^{n}d({n,k})s_{k}\left(\mathbf{a}\right)\geq s_{2}\left(\sqrt{\mathbf{a}}\right), where d(n,k) is the fraction D(n,k)/n! and \sqrt{\mathbf{a}}=(\sqrt{a_{1}},\dots,\sqrt{a_{n}}) is the vector of non-negative square roots of the elements of \mathbf{a} . While the statement of Theorem 1.1 appears to be somewhat unmotivated and magical on the surface, it arises naturally in the context of lower bounds for the matrix permanent , a subject about which we hope to say more elsewhere. Here, we content ourselves with pointing out that the left-hand side of the inequality in Theorem 1.1 is easily seen to be \per(M(\mathbf{a}))/n! , where M(\mathbf{a}) is the n\times n matrix whose diagonal entries are a_{1},\dots,a_{n} and whose off-diagonal entries are all one. Our proof of Theorem 1.1 relies on a somewhat unusual approach. Concretely, we construct a collection of differential operators to set up a monotone flow that allows us to locate (within some compact subset of the domain where it suffices to establish the inequality) the critical points of the difference between the left-hand side and the right-hand side of ( 1 ). To get a sense of the difficulties involved in proving Theorem 1.1 , and to appreciate why our proof of Theorem 1.1 requires such machinery, it will be helpful to consider the result in some special cases and for small values of n\in\mathbb{N} . When all the a_{i} are equal, say to a , then the right-hand side of ( 1 ) is just a , while the left-hand side of ( 1 ) is \mathbb{E}[a^{X}] , where X is the number of fixed points of a uniformly random permutation; since \mathbb{E}[X]=1 , the result in this case follows from convexity via Jensen’s inequality. It is tempting to look for a similar argument that relies on simple convexity in the general case; such a proof might well exist, but we have tried hard to find such an argument and have nothing to show for our efforts. The statement of Theorem 1.1 is easy to check for n=2 since it asserts (after scaling by a factor of 2!=2 ) that 1+a_{1}a_{2}\geq 2\sqrt{a_{1}a_{2}} for any a_{1},a_{2}\geq 0 ; this is of course immediate from the AM–GM inequality. Our main result is already non-trivial for n=3 . In this case, the inequality asserts (now, after scaling by a factor of 3!=6 ) that for any a_{1},a_{2},a_{3}\geq 0 , we have (2) 2+a_{1}+a_{2}+a_{3}+a_{1}a_{2}a_{3}\geq 2\sqrt{a_{1}a_{2}}+2\sqrt{a_{2}a_{3}}+2\sqrt{a_{1}a_{3}}. It is not too difficult to prove ( 2 ), but what is striking to us is the fact that every elementary proof of ( 2 ) that we know of appears to break symmetry in the variables (a_{1},a_{2},a_{3}) in some way (even though ( 2 ) is itself completely symmetric). For example, we may deduce ( 2 ) from a well-known inequality of Schur [ 5 ] that says that for any x,y,z\geq 0 , we have x(x-y)(x-z)+y(y-z)(y-x)+z(z-x)(z-y)\geq 0 ; that said, the proof of this inequality itself involves some symmetry breaking, and indeed, it is known, see [ 3 , 6 ] , that on account of this symmetry breaking, there are no natural extensions of Schur’s inequality that apply to four or more non-negative reals. In fact, we can quantify the difficulty in proving ( 1 ) a little more precisely. First, it is not too hard to show that the validity of ( 2 ) (and thus ( 1 ) as well) has no ‘sum of squares’-certificate in the ring of polynomials. Second, there is a rather powerful inequality due to Muirhead [ 4 ] that allows one to compare two symmetric means of non-negative reals. The right-hand side of ( 1 ) is a symmetric Muirhead mean of the numbers a_{1},\dots,a_{n} (associated with the vector (1/2,1/2,0,\dots,0) ), while the left-hand side is a weighted linear combination of the elementary symmetric polynomials, which are themselves Muirhead means of the numbers a_{1},\dots,a_{n} as well. However, it can be shown that even ( 2 ), the specialisation of ( 1 ) to three variables, is not in the Muirhead semiring in the sense of [ 1 ] , or in other words, that ( 2 ) does not follow (in a logically precise sense) from Muirhead’s inequality. The rest of this paper is organised as follows. Our proof of Theorem 1.1 via the construction of a monotone flow is given in Section 2 . We conclude with a discussion of open questions in Section 3 . 2. Proof of the main result We shall prove Theorem 1.1 , for n\geq 4 , through an analysis of the critical points of an appropriately defined real-valued function over \mathbb{R}_{\geq 0}^{n} . To

Read the complete text