A strict four-row permanent inequality and permutation moments

Proof of Theorem 1.1. A zero function makes the assertion immediate. By homogeneity, normalize each nonzero function to have \|f_i\|_2=1. The resulting space of quadruples is compact. The exponent-two Carlen–Lieb–Loss inequality is strict everywhere on this space except at the single quadruple f_i\equiv1. Its normalization follows directly from

The equality classification for nonzero nonnegative columns gives exactly the stated exceptional quadruple [5, Theorem 1.1 and equation (1.4)].

All scalar expectations and inner products on four points use uniform measure: \E_jh(j)=\tfrac14\sum_jh(j) and \langle g,h\rangle=\tfrac14\sum_jg(j)h(j). Fix p_*\in(4/3,2). Near that quadruple, the means are positive, so renormalize by the means and write f_i=1+g_i, with \E_jg_i(j)=0. Let

For i\ne j, uniform sampling without replacement gives

Consequently the total quadratic term is

For a law \nu at total-variation distance at most \varepsilon from u, the change in each quadratic expectation is at most 2\varepsilon\|g_i\|_\infty\|g_j\|_\infty. On four points, \|g_i\|_\infty\le2\|g_i\|_2, so the total change is at most an absolute constant times \varepsilon V. All linear terms are zero under \nu, because every coordinate marginal is uniform. Each cubic or quartic term is at most an absolute constant times bV when b\le1/2. Indeed, bound all but two factors by b and apply Cauchy–Schwarz to the remaining factors; their squared expectations use only the uniform marginals. Thus

Taylor’s formula on [1/2,3/2], uniformly for p\in[p_*,2], gives

Taking pth roots and multiplying the four factors gives

All constants are uniform on the fixed interval of exponents. Since (p_*-1)/2>1/6, first choose b_*>0 and \varepsilon_*>0 small enough that the error terms in (5) and (6) fit inside this strict gap. The desired inequality then holds for every p\in[p_*,2] whenever b<b_* and \|\nu-u\|_{\TV}\le\varepsilon_*, with exact uniform marginals.

Return to the L^2-normalized compact space. The condition just obtained contains a fixed open neighborhood \mathcal U of its constant quadruple. On the compact complement of \mathcal U, the exponent-two inequality has a positive minimum gap. Both sides are continuous in the functions; they are also continuous in the exponent and in the probability masses of \nu. Choose p_0\in[p_*,2) sufficiently close to two, then 0<\varepsilon\le\varepsilon_* sufficiently small, so that this gap remains positive on the complement. The local argument applies on \mathcal U with these same constants. These two regions cover all normalized quadruples, proving the theorem.□

Proof. Induct on b. Fix the first b-1 coordinates and apply Theorem 1.1 to the last coordinate. The four resulting functions on b-1 coordinates are

The induction hypothesis applies to their product, and its p_0th-power sums are precisely the full product-measure sums in the assertion.□

Proof. Each layer averages a subgroup H\cong(S_2)^{N/2}. The sign character averages to zero. Young’s rule says that an irreducible with H-fixed vectors must dominate the partition (2^{N/2}), so it has at most N/2 rows. For the norm assertion, equality in a product of orthogonal projections on a unit vector would force that vector to be fixed by every layer. It would then be fixed by every coordinate-edge transposition. Edge transpositions of a connected graph generate its full symmetric group, whereas a nontrivial irreducible has no invariant vector.□

Proof. Schur orthogonality normalizes u to have mass one. Write V_\alpha\otimes\overline{V_\alpha}=\bigoplus_\nu V_\nu\otimes\mathbb C^{a_\nu}, and let P_\nu be its isotypic projection. Character orthogonality gives

The two commuting positive operators Q\otimes I and I\otimes\bar Q satisfy

The partial trace of P_\nu over either factor commutes with the irreducible action on the other. Its trace is a_\nu D_\nu, so it equals (a_\nu D_\nu/D_\alpha)I. The preceding character average is therefore at most a_\nu.

A permutation fixes exactly 4^{\#\mathrm{cycles}(g)} color strings. This is a permutation character, so its expansion in irreducible characters has nonnegative integer coefficients. Apply the preceding inequality to that expansion. It yields the first asserted bound, since a_\nu is the multiplicity of \nu in \chi_\alpha^2.

Finally the color-string representation is the direct sum, over all color-class sizes m_1+\cdots+m_4=m, of \Ind_{S_{m_1}\times\cdots\times S_{m_4}}^{S_m}\one. Frobenius reciprocity identifies its inner product with \chi_\alpha^2 as the sum of the dimensions of the commuting algebras of the corresponding restrictions of V_\alpha. Those dimensions are the sums of squared multiplicities displayed in the statement.□

Proof. The central estimate for a residual shape \delta\vdash t is

To prove it, let the multiplicity on the left before squaring be c. Restriction and induction dimensions give, respectively,

Multiplying and cancelling the positive dimensions proves (15). It is essential here to combine one restriction estimate and one induction estimate.

Both C(\alpha) and t_h(\alpha) are invariant under conjugation, so orient \alpha with its first row of length m-k, where k=k(\alpha). Remove its first h rows and then the first h columns of the remainder. The residual straight diagram \delta has size t=t_h(\alpha). Deleting a first row leaves an interlacing partition, so reversing that deletion adds a horizontal strip. Deleting a first column gives the vertical analogue.

More explicitly, let \ell\le2h be the number of nonempty removed lines, let their lengths be a_1,\ldots,a_\ell, and let \xi_j be the trivial character of S_{a_j} for a removed row and the sign character for a removed column. Then

contains V_\alpha by the Pieri rules. Thus each multiplicity in a restriction of V_\alpha is bounded by the corresponding multiplicity in W. We will use this comparison only for tuples \boldsymbol\beta that occur in the original restriction of V_\alpha. For those tuples, the first-row inequality in the Littlewood–Richardson rule says \alpha_1\le\sum_i\beta_{i,1}, and hence

Every intermediate diagram in a Pieri chain ending at such a \beta_i is contained in it, and has at most k boxes below its first row. The number of partitions of any size at most m satisfying that condition is at most

One way to see this is to choose the first-row length, and encode the tail by its row lengths and column lengths along a Durfee square of side at most \sqrt k. Padding the two lists to length \lceil\sqrt k\rceil gives the displayed upper bound. For k=0, only the first-row length is needed.

Fix such a final tuple \boldsymbol\beta, and put H_{\boldsymbol\beta}=\prod_{i=1}^4S_{|\beta_i|}. Mackey’s formula for \Res_{H_{\boldsymbol\beta}}W indexes the decomposition by allocations of the residual factor and the \ell strip factors among these classes. There are at most (m+1)^{4(\ell+1)} allocation matrices. For each allocation, restrict V_\delta to the four allocated subsets, then add the allocated horizontal or vertical strips within each color class by Pieri. A chain ending at \beta_i consists of diagrams contained in \beta_i, so every one obeys the small-tail bound just counted. Choosing the residual tuple and all subsequent diagrams costs at most Q_m(k)^{4(\ell+1)}. Each Pieri transition is multiplicity free, and (15) bounds the residual multiplicity by 4^{t/2}. Therefore

There are at most Q_m(k)^4 possible final occurring tuples. Squaring this bound and summing over them gives 4^t times \exp\{C(1+h)(1+\sqrt k)\log(2m)\}, proving (14). No tail estimate for the other constituents of W is required.□

Proof. For the assertion about k, orient the parent with its longest side as first row. The first-row inequality gives a bound by its row deficit on the sum of the child row deficits; each child’s k is no larger than its row deficit. If the parent’s longest side is a column, transpose every partition, which preserves Littlewood–Richardson multiplicities.

Write s_\nu for the ordinary Schur function, and s_\nu(X\mid Y) for its hook-Schur specialization [14, Definition 1(a)]. For the assertion about t_h, take h ordinary variables X, h transpose variables Y, and an unlimited ordinary alphabet Z. Variables in X,Y have degree zero and those in Z have degree one. The positive hook-Schur tableau rule uses ordinary entries weakly along rows and strictly down columns, and transpose entries strictly along rows and weakly down columns [9, Section 2]. For s_\nu(X\mid Y), order all X letters before all Y letters, so the ordinary entries occupy a subdiagram. The rule gives s_\nu(X\mid Y)\ne0 exactly when \nu_{h+1}\le h. For completeness, a tableau over h ordinary and h transpose letters cannot fill an (h+1)-by-(h+1) square: the ordinary subdiagram has at most h rows, and the transpose-filled remainder has at most h columns in each remaining row. Conversely, fill the first h rows with their ordinary row letters and the remaining boxes with their transpose column letters. This realizes every diagram in that hook.

Writing p_j for the jth power sum, the supersymmetric substitution is

Applied to the ordinary Schur coproduct, it gives

Its coefficients are nonnegative. The largest subdiagram of \lambda in the (h,h) hook is the union of its first h rows and first h columns. The smallest degree in Z is therefore exactly t_h(\lambda); the corresponding skew Schur function is nonzero on an unlimited alphabet.

Apply this substitution to \prod_i s_{\alpha_i}=\sum_\lambda c^{\lambda}_{\boldsymbol\alpha}s_\lambda. The product on the left has minimum Z-degree \sum_i t_h(\alpha_i). Every summand on the right has nonnegative coefficients, so an occurring parent’s minimum degree cannot be smaller. This is (17).□

Proof. Isolating the first-row deficit. Let \mathcal I_s be the set of ordered injections from [s] into the n positions, with \mathcal I_0 a singleton. The sweep induces a transition matrix T_s on this set. Write

This is the ordinary, unnormalized trace on the indicated permutation module.

The permutation module on \mathcal I_s is \operatorname{Ind}_{S_{n-s}}^{S_n}\mathbf1. By repeated branching, the multiplicity of V_\lambda in it is the number of standard tableaux of skew shape \lambda/(n-s). Assume s\le k and n\ge2k. Every occurring partition has the form \lambda=(n-j,\mu) with 0\le j\le s and \mu\vdash j. The skew shape consists of the tail \mu and a row of s-j cells whose columns exceed n-s\ge k\ge\mu_1. These components share neither a row nor a column. Choosing the j entries of the tail and then a standard tableau on it gives multiplicity \binom{s}{j}D_\mu. Hence

Binomial inversion gives

where positivity follows from the positive semidefiniteness of each B_\lambda. It remains to bound this inverse without losing its cancellation.

For fixed initial and final positions of one card, there is exactly one possible path through the successive coordinate layers: at layer i, its first i processed coordinates have their final values and its remaining coordinates still have their initial values. Thus fixed endpoints for s cards prescribe all their paths. If two tracked cards use the same switch, the two prescribed coin requirements either disagree, making the endpoints impossible, or agree, saving one coin. If e is the number of switches shared by two tracked cards along a realized sweep, the transition probability to its realized endpoint is therefore 2^{-ds+e}=n^{-s}2^e. Averaging first over the realized endpoint and then over a uniform initial injection gives the exact identity

Choose k distinct uniform initial positions X_1,\ldots,X_k, independently of the coins of one complete sweep. For this realized sweep, form a graph G on all n initial positions, joining two positions if their cards share a switch. Each vertex has degree d. The graph is simple: after two cards meet at coordinate i, their positions differ at that coordinate forever, so they cannot meet at a later coordinate. Let G_X be the graph induced on the selected tags, and let e(S) count its edges with both endpoints in S\subseteq[k]. The marginal initial positions of every such subset are a uniform injection. Thus, with

Equations (19) and (18) imply

A predecessor selection is a collection D of directed pairs (i,j) with 1\le j<i\le k, at most one pair having any given first coordinate. Write |D| for its number of pairs and \operatorname{supp}D for their endpoints. Expanding the product defining w(S) gives

Also 2^{e(S)}=\sum_{H\subseteq E(G_X[S])}1. If \operatorname{supp}H denotes the vertices incident to the edges of H, then summing over S in (20) yields the exact cancellation identity

Indeed, a term supported on U has coefficient \sum_{S\supseteq U}(-1)^{k-|S|}, which is zero unless U=[k]. Thus only an encounter-edge set and a predecessor selection that together cover every tag survive the inversion. We may now bound their absolute sum without losing that covering constraint.

Counting the covering configurations. Two elementary facts about G control the possible encounter subgraphs. First, every set of v vertices spans at most

edges, with 0\log_2 0=0. To prove this by induction on d, split the initial positions according to the last processed coordinate. Before the last layer, these two halves remain separate. If the chosen set has v_0,v_1 positions in them, induction bounds the earlier encounters by \tfrac12v_0\log_2v_0+\tfrac12v_1\log_2v_1, and the last matching adds at most \min(v_0,v_1) edges. This is at most \tfrac12v\log_2v because the binary entropy H_2(p)=-p\log_2p-(1-p)\log_2(1-p), with 0\log_2 0=0, satisfies H_2(p)\ge2\min(p,1-p) by concavity on each half of [0,1].

Second, if F is a specified forest on v selected tags with c components, then, conditional on the entire sweep,

Choose one root position per component and then successively place each child at one of at most d neighbors of its parent. This gives the first inequality even if some counted placements fail to be injective. For v\le k\le n^{1/100} and sufficiently large n,

which gives the second inequality.

Let an encounter-edge set H use v vertices and have c nontrivial connected components. Then 2c\le v, and H contains a spanning forest with v-c edges. For fixed v,c, there are at most (2k)^{2v} choices for its vertex set and forest: choose the vertex set, root every component at its least vertex, and record a parent or a root marker for every vertex. For any realization and any such forest, the number of possible edge sets extending it is at most

by (22). A canonical choice of spanning forest for each H, or simply overcounting all spanning forests, therefore bounds the expected number of these H by

For v=c=0, the empty edge set contributes one, which also obeys this upper bound.

There are at most \binom{k}{q}k^q\le(2k)^{2q} predecessor selections with q pairs. The covering condition in (21) implies v+2q\ge k. Since d/n\le1, v-c\ge v/2, and there are at most (k+1)^3 triples (v,c,q), the preceding estimates show that

Impossible triples only enlarge this upper bound. Uniformly for 1\le k\le n^{1/100}, sufficiently large n satisfies

For example, the first left side is at most 4\sqrt{\log_2n}\,n^{-19/40}, and the last left side is at most 16n^{3/100}. Every term in (24) is therefore at most n^{-2(v+2q)/5}\le n^{-2k/5}, proving 0\le b_k\le n^{-3k/10}.

From the trace bound to stopping. If \lambda_1=n-k with 1\le k\le n^{1/100}, its term in b_k has coefficient D_\mu\ge1, so \Tr B_\lambda\le n^{-3k/10}. The eigenvalues are nonnegative, and consequently

Choosing the labels of the k cells below the first row and then their order gives D_\lambda\le\binom nk k!\le n^k. Hence

If instead \lambda'_1=n-k>n/2, every matching projection vanishes on V_\lambda. Indeed, its fixed-space dimension is the multiplicity of V_\lambda in \operatorname{Ind}_{S_2^{n/2}}^{S_n}\mathbf1. Repeated horizontal Pieri shows that every constituent is obtained by adding n/2 horizontal strips of size two. Each strip adds at most one cell to the first column, so every constituent has first-column height at most n/2. Thus B_\lambda=0 in the case under consideration. For k=0, the trivial representation has the claimed value one and the sign representation is annihilated by a matching projection.

Finally, Lemma 3.1 gives operator norm strictly less than one on every nontrivial irreducible at each fixed n. There are only finitely many powers of two below N_0 and finitely many irreducibles at each of them. Increasing r to one fixed even r_0\ge4 therefore gives the stated stopping estimate also at these remaining sizes. Larger powers preserve the estimate because B is a positive semidefinite contraction.□

Proof. At a level with node size m, let q_m be the number of charged nodes and let their deficits be k_1,\ldots,k_{q_m}. By Lemma 4.3, their sum is at most K. Expanded nodes satisfy k_i>m^{.01}, so their number is at most K/m^{.01}. A charged child of size m has an expanded parent of size 4m, and there are four children per parent. Consequently, after changing one absolute constant,

The root also satisfies these bounds when expanded. A stopped root already has F\le1 and satisfies the conclusion directly.

At that level choose

The lower-order terms in the choice and restriction costs are bounded by

Cauchy–Schwarz gives \sum_i\sqrt{k_i}\le\sqrt{q_mK}. The terms arising from the ceiling and the constant one are therefore at most CKm^{-.005}\log(2m). For the terms involving m^a, use both bounds in (27):

For the second inequality, q_m\le\sqrt{(N/m)(CK/m^{.01})}. These costs are summable geometric tails because level sizes differ by a factor four. All charged nodes have size greater than M/4, including the stopped children of the last expanded level. Choosing M large makes their total at most \epsilon K.

It remains to sum the leading hook terms. At every level, iteration of Lemma 4.3 bounds the sum of t_{h_m} over charged nodes by t_{h_m}(\lambda). Follow one root box (i,j) and write s=\min(i,j). It can contribute only if

The eligible sizes m form part of a geometric progression of ratio four, all larger than M/4. By increasing M so that (M/4)^a\ge4^a H, their number is at most

Indeed the number is bounded by the positive part of one plus the logarithm of the ratio of the upper endpoint (s\sqrt{N/K})^{1/a} to the lower endpoint M/4, divided by \log4; the choice of M absorbs the extra one. Replacing \log(s/H) by its positive part can only enlarge the bound.

Boxes in the longest first row or column never contribute, since h_m\ge1. There are exactly K remaining boxes. Multiply their level counts by \theta\log4 and add the lower-order costs. This proves (26).□

Proof. The hook-length formula separates the first row exactly:

If K<N/3, a nonzero numerator occurs only for j\le K, so the logarithm of the inverted product is at most K/(N-2K+1). For K\ge N/3, split the columns at height \sqrt N. There are at most \sqrt N columns taller than this; each contributes at most \log(1+N). In the remaining columns, bound \log(1+x) by x and sum the denominators harmonically. Their contribution is at most \sqrt N(1+\log N). Since \binom NK\ge(N/K)^K, this proves (28).

Every box contributing to R_H lies in \zeta. At root coordinates (i,j), its hook in \zeta has length at most

Take a reverse linear extension of the Young diagram order on \zeta, numbering its boxes from 1 to K. The number assigned to each box is at least its hook length, because all boxes to its right and below precede it. The product of all number-to-hook ratios is exactly D_\zeta, and every ratio is at least one.

Suppose t boxes contribute to R_H. Their distinct assigned numbers have product at least t!. Keeping only their ratios in the hook product gives, for t>0,

The last inequality follows by maximizing t\log(4eK/(tH)) over t>0. For t=0, the assertion is immediate.

Finally we prove \log D_\lambda\ge cK without losing uniformity in the shape. If K<N/3, (28) already gives this for large N. Put L=\lambda_1=\max(\lambda_1,\lambda'_1). If K\ge N/3 and L\ge N/8, retain the first row and an order ideal of b=\lfloor N/32\rfloor boxes in the lower diagram. Place 1,\ldots,b in the first b boxes of the top row, choose any b of the remaining L labels for the lower diagram, fill those lower boxes in a fixed standard order, and fill the rest of the top row increasingly. This gives \binom Lb\ge4^b standard tableaux of the retained diagram. Every such tableau extends to \lambda. If L<N/8, every hook is shorter than N/4, so D_\lambda\ge N!/(N/4)^N\ge(4/e)^N. These cases give one absolute positive c.□

Proof of the moment assertion in Theorem 1.2. Fix the constants in their logical order. Theorem 1.1 first gives p_0 and \theta<1/2. Choose \delta>0 so small that

The universal degree constant c in Lemma 6.2 is independent of this choice. Choose H sufficiently large and \epsilon sufficiently small that \epsilon+4b/H<(1-b)c/4. Then choose the cutoff M required by Lemma 6.1, increasing it further so that the errors E_{N,K} in Lemma 6.2 are less than (1-b)cK/(4b) whenever N>M. This is possible uniformly: the first error divided by K is O(1/N), and the second is O(\log N/\sqrt N) in its stated range.

Only now choose the even moment r. It must make the four-site column law admissible for Theorem 1.1, enforce the sparse stopping rule, and make F_r\le1 for all nontrivial shapes of all dyadic sizes at most M. These are finitely many or fixed-threshold requirements, by Lemmas 3.1 and 5.1; all persist on increasing r.

For an expanded root, (26), (28) and (29) give

Here we discarded the additional negative term -bK\log(N/K)/2. Thus \eta=(1-b)/2>0 works at every expanded root. At a stopped root F_r\le1\le D_\lambda^{1-\eta}. The row representation has F_r=1, while the column representation is killed by Lemma 3.1. This proves the moment assertion for every dyadic N.□