A Cyclic Polytabloid Proof of Saxl’s Conjecture

Proof. Arrange the blocks as columns of a tableau t of shape \theta, in nonincreasing order of their sizes, and place each ordered block from top to bottom. Tableau entries are the distinct elements of B. A row tabloid \{t'\} records the set of entries in each row. Let M^\theta be the permutation module spanned by these row tabloids. Send \{t'\} to the word assigning letter i to every entry of row i. This is an S_B-equivariant bijection from the tabloid basis of M^\theta to the word basis of content \theta. If C_t is the subgroup permuting entries within each column of t, the polytabloid

maps to v_L: in a column, the position action replaces a permutation of the letters by its inverse, which has the same sign. In particular this vector is nonzero, since the original row word has coefficient 1. The span of all translates of e_t is the Specht module S^\theta, irreducible over \C by the standard polytabloid construction [Jam78, Definitions 4.1 and 4.3, Theorem 4.12]. This proves the assertion. The argument applies to a dual space with any chosen basis; alternatively, an invertible basis change on that space induces an invertible map on its position tensor power commuting with S_B.□

Proof. The case n=0 is immediate from the trivial representation of S_0. Assume henceforth that n>0. Transitivity of induction and Remark 2.2 show that the multiplicity of S^\tau counts chains

whose successive differences are horizontal strips. Each strip raises the first column’s height by at most one, so \nu^{(k)} has at most k rows. Since it is contained in \tau,

For k>\ell, both initial sums equal n, since \tau has at most \ell rows. This proves necessity of dominance. If \tau=\theta, equality forces \nu^{(k)} to be exactly the first k rows of \theta. These diagrams do form a chain of the required kind, proving multiplicity one.

For sufficiency, suppose \tau\unrhd\theta and induct on \ell. For \ell=1, necessarily \tau=(n). For \ell>1, put t=\theta_\ell. There are at least t columns of \tau, since \tau_1\ge\theta_1\ge t. Delete a bottom box from each of the t tallest columns, choosing the rightmost columns first among equal heights, and call the remaining diagram \nu. Its column heights are still nonincreasing: unequal adjacent heights differ by at least one, and within any group of equal heights precisely a suffix is lowered. Thus \nu is a partition and \tau/\nu is a horizontal t-strip. For every k\ge1 its loss in the first k rows is

there are \tau_{k+1} columns taller than k, and the rule selects these before any column whose bottom box belongs to the first k rows. If the loss is zero, the desired dominance inequality for \nu follows immediately. If it is positive and k<\ell, then

For completeness, dominance at \ell gives \len(\tau)\le\ell, and dominance at \ell-1 gives \tau_\ell\le t. All \tau_\ell columns of height \ell are therefore selected, so the last row disappears and \len(\nu)\le\ell-1. Hence all remaining initial sums equal the total n-t, and \nu\unrhd(\theta_1,\ldots,\theta_{\ell-1}). Induction gives a chain ending at \nu; appending the deleted strip gives Equation (2.6) ending at \tau.

Finally, the stabilizer of a word with prescribed letter multiplicities is the product of the symmetric groups on its equal-letter position sets. Reordering those multiplicities conjugates this subgroup, giving the asserted isomorphism of permutation modules.□

Proof. Fix m, abbreviate G=G_m, and let \epsilon be the one-dimensional sign representation, also denoting its character by \epsilon. By Young’s rule, conjugation of dominance, and the sign-twist identity in Equation (2.3), it is enough to show that W_m\otimes\epsilon contains every constituent of M^{\rho_m}. We will find the cyclic module generated by v_{R_m}\otimes v_{R_m} inside an isomorphic image of W_m\otimes\epsilon, then map that module onto M^{\rho_m}. The row subgroup

acts on v_{R_m} by \epsilon|_{H_R}. Consequently the unnormalized signed diagonal average is exactly

To see that u\ne0, let a_0(i,j)=i and consider the corresponding word e_{a_0}. It is fixed by H_R. Its coefficient in v_{C_m} is 1: within each increasingly ordered column it is the identity assignment 1,2,\ldots,m+1-j. The coefficient of e_{a_0} in every h v_{C_m} is therefore also 1, since h^{-1}e_{a_0}=e_{a_0}. Its coefficient in u is |H_R|=\prod_{r=1}^m r!, which is nonzero.

We next identify the alternating line in V_R. Frobenius reciprocity, the induction identity for a sign twist, and Remark 2.3 give

For the last equality, V_R\otimes\epsilon\cong S^{\rho_m} by self-conjugacy of the staircase, and S^{\rho_m} has multiplicity one in M^{\rho_m}. As v_{R_m} is nonzero and alternating under H_R, it spans the line in Equation (3.5).

Twisting the diagonal tensor product can be done in its second factor: the reassociation

is a G-isomorphism. Choose a G-isomorphism \phi:V_C\otimes\epsilon\longrightarrow V_R, which exists by Equation (3.3) and \rho_m^t=\rho_m, and choose 0\ne z\in\epsilon. Since u is H_R-fixed, u\otimes z is alternating under H_R. It follows from Equation (3.5) that \phi(u\otimes z)=c\,v_{R_m} for some c\ne0. Tensor Equation (3.4) with z and apply the reassociation in Equation (3.6), followed by \id\otimes\phi. The right-hand side becomes c(v_{R_m}\otimes v_{R_m}). Thus the image of W_m\otimes\epsilon under this isomorphism contains

We construct a surjection from Z_m onto M^{\rho_m}. Let E_{\mathrm{out}} have basis f_1,\ldots,f_{2m-1} and define the linear map

Regroup the two input layers by position, using ordinary tensor reassociation, and apply q at every position. Then project onto the span \mathcal M_\alpha of words in which letter r occurs exactly r times for 1\le r\le m, and no letter greater than m occurs. Thus the content is \alpha=(1,2,\ldots,m,0,\ldots,0) in the output alphabet. Denote the resulting linear map by

Both operations commute with position permutations: the same local map q is used everywhere, and content is unchanged by G. Hence Q is G-equivariant.

Consider any summand in the expansion of v_{R_m}\otimes v_{R_m}. On a row of length r, write its two assignments as (a_1,\ldots,a_r) and (b_1,\ldots,b_r), each a permutation of 1,\ldots,r, and put c_j=a_j+b_j-1. Then

For a term retained by the content projection, the sum of squared output letters over the whole triangle is \sum_{r=1}^m r^3. Summing Equation (3.9) over the rows forces equality on every row. Thus c_j=r at every position in the row of length r. There is only one possible retained output word, namely

It remains to compute its coefficient. On a row of length r, each of the r! assignments a_j=\pi(j) has the unique compatible assignment b_j=r+1-\pi(j). The latter is the permutation \omega_r\pi, where \omega_r(j)=r+1-j, so the product of the two alternating signs is

The row contributions are independent. In particular, there is no cancellation, and the exact image is

The stabilizer of t_m is exactly H_R, since its equal-letter sets are the rows of B_m. Its orbit is a basis of \mathcal M_\alpha, and hence

This also explains why the increasing content (1,2,\ldots,m) gives the usual module indexed by the decreasing partition \rho_m: reordering the content parts conjugates the standard Young subgroup.

By Remark 2.3, every S^\tau with \tau\unrhd\rho_m occurs in the quotient in Equation (3.11). Semisimplicity and Equation (3.7) imply that it occurs in W_m\otimes\epsilon. If \rho_m\unrhd\lambda, reversal of dominance under conjugation gives \lambda^t\unrhd\rho_m^t=\rho_m. Taking \tau=\lambda^t and twisting back by \epsilon proves that S^\lambda occurs in W_m.□

Proof. The relation (gh)\otimes a=g\otimes ha, for h\in H, has the same image on both sides, so \Phi is well-defined. It is equivariant and surjective. Choose g_A\in G with g_AD=A for every A\in\Omega, and let \pi_A:T\to T_A be the coordinate projection. Since

we have g_A^{-1}\pi_A(y)\in A_0 for y\in\C[G]z. Define

Replacing g_A by g_Ah does not change this expression, because g_Ah\otimes h^{-1}a=g_A\otimes a in the balanced tensor product. Clearly \Phi\Psi(y)=\sum_A\pi_A(y)=y. For g\otimes a, set A=gD and write g=g_Ah with h\in H. Only its A-sector is nonzero, and hence

Thus the displayed maps are inverse isomorphisms.□

Proof. Projection and the high positions. Use the ordinary tensor identification

Put E_{\mathrm{lo}}=\Span(e_1,\ldots,e_s) and E_{\mathrm{hi}}=\Span(e_{s+1},\ldots,e_m). On a pair-letter basis vector define

The same local projection is used at every position, so P_s commutes with G. Call a retained position high when both letters are greater than s.

In a retained word of w_m, let A be the set of high positions. Alternation in the first layer gives row counts r_i=\max(h+1-i,0), and alternation in the second gives column counts d_j=\max(h+1-j,0), for 1\le i,j\le m. For each 1\le k\le m, these counts satisfy

Column j can contribute at most \min(k,d_j) high positions to the first k rows. Equality of the sums in Equation (4.6) therefore forces equality in every column. For d_j>0, take k=d_j: all its d_j high positions occupy the first d_j rows. Columns with d_j=0 have no high positions. Consequently

For the zero-one matrix recording membership in A, this is the equality case of the row and column margin inequalities [Rys57, Section 2]. The specific staircase margins in Equation (4.6) make every prefix bound an equality.

Factorization with signs. In a row or column block of length r, its intersection with D is its initial segment of length a=\max(r-s,0); its intersection with F has length b=\min(r,s). The retained assignments put the high letters s+1,\ldots,r on the first segment and the low letters 1,\ldots,b on the second. Let \Alt denote the unnormalized alternation of a displayed list, placed in the indicated segment, with \Alt(\varnothing)=1. The part of the block tensor with this prescribed high set is exactly

Here the high list is empty when r\le s. Indeed, every high letter precedes every low letter in the position order, giving ab inversions; all other inversions are internal to the two independently permuted lists. Every such pair of permutations occurs once. In particular, when r<s the formula is just the original alternation on e_1,\ldots,e_r.

Rows and columns both have the length list m,m-1,\ldots,1. Thus their cross signs in Equation (4.8) multiply to

Identify E_h with E_{\mathrm{hi}} by e_a\mapsto e_{s+a}, and write \widetilde w_h and \widetilde W_h for the images of w_h and W_h in the two high-letter layers on D. The low portions are precisely the blocks of R_F,C_F. Regrouping the factors over the disjoint sets D,F introduces no signs, and hence

The nonvanishing follows also directly from the nonzero alternating tensors on each disjoint block.

The two factors of H=S_D\times S_F act independently on this tensor, while each acts diagonally on the two layers over its own position set. Therefore

The second equality follows by expanding tensors of linear combinations of the two separate orbit sets.

The coordinate sectors. Let \Omega be the set of subsets A\subset B_m of size |D|. Within the pair-letter space define

These are the coordinate spans of words high exactly on A. They have disjoint word bases, so their sum is direct, and gT_A=T_{gA}. By Equation (4.9), z\in T_D; the stabilizer of D in G is exactly H. Apply Remark 4.1 and Equation (4.10) to obtain

Since P_s is equivariant, P_s(W_m)=\C[G]P_s(w_m)=\C[G]z. Its restriction to W_m, followed by the inverse map \Psi in Equation (4.4) and the identification of A_0 in Equation (4.10), gives Equation (4.5). The image of this ambient projection need not lie in the two original Specht factors; the composition is still a surjective G-equivariant linear map onto the displayed module. Semisimplicity over \C proves the last assertion.□

Proof. The two singleton blocks require the first row-layer index and last column-layer index to be 1. The coefficient of an alternating pair in path order is J_{ab}. Hence the left side of Equation (5.4) is exactly

Reading the contracted indices successively from a_1 to b_K gives

The transpose at an even position records that its column index is encountered before its row index. For X=\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right), direct multiplication gives

There are m-1 even positions, yielding the stated sign. In particular, adjugation is a linear operation on \Mat_2(\C).□

Proof. Fix a permutation \pi and let j be the local slot occupied by M_1=I. Deleting I leaves a permutation of M_2,\ldots,M_r. Its sign is exactly the sign acquired when those pairwise anticommuting matrices are reordered. Moving I from its first canonical slot to slot j contributes (-1)^{j-1} to \sgn(\pi) and changes no matrix product. It follows that

By Equation (5.6), adjugation fixes I and negates each of the other basis matrices. Write \epsilon_j=1 if p+j-1 is even, and 0 otherwise. Adjugation therefore contributes the additional sign (-1)^{e-\epsilon_j}. Since \epsilon_j\equiv\delta+j-1\pmod2, the total sign is (-1)^{e-\delta}, independently of \pi. All r! summands in Equation (5.8) consequently agree, proving Equation (5.9), including r=1. Finally, the canonical products for r=1,2,3,4 are respectively I,Z,J,-I, which gives Equation (5.10).□

Proof. Let r_1,\ldots,r_c be the column lengths of \eta in their usual order, so 1\leq r_j\leq4 and \sum_jr_j=K. Partition the path into consecutive segments of these lengths, beginning at s_j=1+\sum_{i<j}r_i. For any ordered basis N_1,\ldots,N_4 of V^*, let t_N be the dual tensor whose factor on segment j is

The segments are the columns of a tableau of shape \eta and the initial basis entries label its rows. By Remark 2.1, their product t_N is a polytabloid, and

First take N_i=M_i. Multilinearity of Equation (5.4) and the definition of t_M give

Indeed, summing independently over the permutations within each segment is exactly the distributive expansion of the displayed ordered product. The segments are consecutive, so no matrix factors are interchanged in this factorization. By Remark 5.2, B is invertible.

The identity \adj(X)=\tr(X)I-X also shows that, for every Q\in\GL_2(\C),

Choose an eigenvector v of B with eigenvalue \beta; invertibility gives \beta\ne0. Choose Q taking v to the first coordinate vector and set N_i=QM_iQ^{-1}. Conjugation is an invertible linear operation on V^*, so these N_i are still an ordered basis. Each alternating segment matrix is now QA_{r_j,s_j}Q^{-1}, and their ordered product is QBQ^{-1}. Since (QBQ^{-1})e_1=\beta e_1,

Only the test covectors have changed; u and its endpoint letters remain those fixed in Equations (5.3) and (5.5).

The invariant evaluation pairing defines

For g\in S_F, its equivariance follows explicitly from \Phi(gx)(t)=\langle x,g^{-1}t\rangle=(g\Phi(x))(t). By Equation (5.12) this map is nonzero on the particular generator u. Its target is irreducible and, by the self-duality in Equation (2.3), has type \eta. Thus \Phi is surjective, and semisimplicity proves the claimed occurrence in U_{m,2}.□

Proof. Unlike the deletion in Remark 2.3, this reduction need not preserve a prescribed dominance inequality; a rightmost suffix suffices to preserve the partition. If \lambda_1\ge m, remove the bottom box in each of the rightmost m nonempty columns. Subtracting one from this suffix of the column-height sequence preserves weak decrease and nonnegativity. The remaining boxes therefore form a partition \nu, and the deleted boxes form a horizontal strip. Since N_m-m=N_{m-1}, this proves (i).

Suppose instead that \lambda_1\le m-1. Failure of domination gives an index k<m with

The index is less than m because the first m parts of the staircase already have sum N_m. For k\le3, however,

Thus 4\le k<m, and in particular m\ge5. Because the parts decrease, the mean of the first four is at least the mean of the first k. Hence

A full sweep removes the bottom box of every nonempty column. If the current row lengths are (\alpha_1,\alpha_2,\ldots), subtracting one from all its positive column heights gives row lengths (\alpha_2,\alpha_3,\ldots). The remaining diagram is nested in the original one, and the removed cells form a horizontal strip of size \alpha_1. Four full sweeps starting from \lambda would therefore remove \lambda_1+\cdots+\lambda_4 boxes.

Perform full sweeps until the remaining number of boxes to be removed is at most the number of nonempty columns, then remove that number of bottom boxes from the rightmost columns. The suffix argument in the first paragraph shows that this last partial sweep also leaves a partition. By Equation (6.2), at most four nonempty sweeps remove exactly 2m-1 boxes. Their remainder has size N_m-(2m-1)=N_{m-2}. Reversing the sequence gives (ii).□

Proof of Remark 3.1. We induct on m. The module W_1 is the one-dimensional representation of the one-element group, so the assertion holds at m=1.

Let m\ge2, suppose the assertion holds for all smaller positive indices, and fix \lambda\vdash N_m. If \rho_m\unrhd\lambda, then Remark 3.2 supplies S^\lambda in W_m. Otherwise apply Remark 6.1.

In case (i), use the band cut with s=1, so |D|=N_{m-1} and |F|=m. The width-one band module U_{m,1} is trivial. By the induction hypothesis, S_D^\nu is a constituent of W_{m-1}. By Remark 2.2, S_{B_m}^\lambda occurs in

Consequently it occurs in the quotient from Remark 4.2 and hence in W_m.

In case (ii), put K=2m-1 and use the cut with s=2. Write b_i=|\lambda^{(i)}|-|\lambda^{(i-1)}|, so that b_1+\cdots+b_q=K and q\le4. Choose disjoint subsets of F of these sizes and form the permutation module

Repeated application of Remark 2.2, followed by transitivity of induction, shows that S_{B_m}^\lambda is a constituent of \Ind_{S_D\times S_F}^{S_{B_m}}(S_D^\nu\boxtimes A). Equivalently,

Here the coefficients are nonnegative integers. Moreover, every constituent of A has at most q rows: starting from the empty diagram, each of the q horizontal-strip additions can introduce at most one new row, because two new rows would both require a new box in the first column. Thus Equation (6.3) provides some \eta with at most four rows, a_\eta>0, and c_{\nu,\eta}^{\lambda}>0.

□

Proof of Remark 1.1. The two factors generating W_m have Specht type \rho_m. Thus W_m is a submodule of S^{\rho_m}\otimes_{\C}S^{\rho_m} under the diagonal action. Remark 3.1 supplies every S^\lambda in that submodule, so g(\rho_m,\rho_m,\lambda)>0 for every permitted m and \lambda.□