===================================================================== A CYCLIC POLYTABLOID PROOF OF SAXL'S CONJECTURE reader's edition -- the complete proof, written out in plain language ===================================================================== WHO THIS IS FOR. A reader who knows what a group is, what a vector space is, and what a permutation is, and nothing else about representation theory. Everything used is either proved below or named once in PART 2 with a reference. Every main result carries a short NAME in capitals (for example "LEMMA (PATH CONTRACTION)") so you can jump back to it. HOW TO READ IT. PART 0 states the theorem, gives the plan, and checks small cases. PART 1 builds the vocabulary. PART 2 supplies the standard tools. PART 3 records three general facts about splitting representations into pieces. PARTS 4-9 are the proof itself, in order: the cyclic module, the dominated case, the band quotient, the band support, the strip reduction, and the final induction. A reader in a hurry can read PART 0, then PART 9 and PART 8, then go back for the ingredients. NOTATION. n, m are positive integers. N_m = 1+2+...+m = m(m+1)/2. S_n is the group of permutations of n letters. A PARTITION is a nonincreasing list of positive integers; alpha |- n means its sum is n. S^alpha (the "Specht module") is the irreducible representation of S_n attached to alpha; PART 1 and PART 2 recall its construction. The STAIRCASE is rho_m = (m, m-1, ..., 2, 1), a partition of N_m. B_m is a triangular array of cells. G_m is the group of all permutations of the cells of B_m. The symbol (x) is the tensor product, "~=" means "isomorphic as representations", and sum, prod, >=, <=, != keep their usual meanings. All vector spaces are over the complex numbers C and are finite dimensional. --------------------------------------------------------------------- PART 0 -- THE THEOREM, THE PLAN, AND SMALL CASES --------------------------------------------------------------------- ANSWER 0.1 (one-sentence statement). Take the staircase partition rho_m = (m, m-1, ..., 2, 1). Its irreducible representation, squared and split into irreducibles, contains EVERY irreducible representation of the symmetric group on N_m letters. ANSWER 0.2 (precise statement). For partitions alpha, beta, lambda of n define the Kronecker coefficient g(alpha, beta, lambda) = dim Hom_{S_n}(S^lambda, S^alpha (x) S^beta), the multiplicity of S^lambda in the tensor product S^alpha (x) S^beta, where S_n acts diagonally: g(v (x) w) = gv (x) gw. (PART 1 and PART 3 define every term.) Then: THEOREM (SAXL). For every m >= 1 and every partition lambda of N_m, g(rho_m, rho_m, lambda) > 0. The claim is uniform in m and in lambda. No hypothesis on lambda is allowed: not "lambda is a hook", not "lambda is near the staircase", not "lambda has few rows". Reference: Ikenmeyer, "The Saxl conjecture and the dominance order", arXiv:1410.6549. ANSWER 0.3 (why it is not obvious). The square has dimension (dim S^{rho_m})^2, which is enormous, while the number of partitions of N_m grows only like exp(c * sqrt(N_m)); so there is plenty of room. But room is not enough. A tensor product is assembled by a fixed algebraic machine (Young's rule and Pieri, PART 2) that in general produces only shapes of a restricted type. For a generic pair (alpha, beta) the Kronecker coefficients are unknown and deciding whether one is nonzero is famously hard. The content of the theorem is that for this one very special pair the support is everything. ANSWER 0.4 (what is actually proved -- the stronger statement). Place the N_m tensor positions in a triangular array B_m (PART 4). Inside the N_m-fold tensor power of C^m sit a vector v_R (the "row polytabloid") and a vector v_C (the "column polytabloid"); both are alternating sums, and the span of either is a copy of S^{rho_m}. Put w_m = v_R (x) v_C, W_m = span of all permutations of the positions applied to w_m. Then: THEOREM (CYCLIC STAIRCASE SUPPORT). For every m >= 1 and every partition lambda of N_m, the irreducible S^lambda occurs in W_m. This implies THEOREM (SAXL), because W_m sits inside the tensor square S^{rho_m} (x) S^{rho_m}; support in the smaller module forces support in the whole square. The gain is that W_m is generated by ONE vector, so an induction can track that vector through every step. THEOREM (CYCLIC STAIRCASE SUPPORT) is what PARTS 4-9 prove. ANSWER 0.5 (the proof in four moves). MOVE 1 (PART 5). If lambda is "dominated" by the staircase, get it directly: twist by the sign representation, average over row permutations, and fold the triangle onto a permutation module. MOVE 2 (PART 6). Cut the triangle into a smaller triangle B_h and a BAND F of width s = 1 or 2. A coordinate projection sends w_m to the tensor product of the smaller staircase generator and an explicit band generator. Because the projection lands in disjoint coordinate "pockets", the image of W_m is the full INDUCED module Ind(W_h (x) U_{m,s}). MOVE 3 (PART 7). For the width-two band, pair the generator with explicit matrix-valued test vectors. The pairing evaluates a product of 2x2 matrices; alternating test vectors give an invertible product, and conjugation makes one entry nonzero. That puts every shape with at most four rows inside U_{m,2}. MOVE 4 (PARTS 8-9). A shape outside the dominated range is reached from a smaller shape either by ONE horizontal strip of size m (width-one cut) or by AT MOST FOUR horizontal strips of total size 2m-1 (width-two cut). Then induction on m finishes. ANSWER 0.6 (small cases). For m = 1: N_1 = 1, rho_1 = (1), the group is trivial, and the only partition of 1 is (1); true. For m = 2: N_2 = 3, rho_2 = (2,1), and S^{(2,1)} is the two-dimensional irreducible of S_3. Its square is four-dimensional, and the three irreducibles of S_3 have dimensions 1, 2, 1 with sum 4, so the square is exactly their sum, each once. So the theorem already holds at m = 2 with no room to spare in the sense of multiplicity. ANSWER 0.7 (a size sanity check for m = 3). N_3 = 6 and rho_3 = (3,2,1) has dimension 16 (hook-length formula, ANSWER 2.10), so the square has dimension 256. The eleven partitions of 6 have dimensions 1, 5, 9, 10, 5, 16, 10, 5, 9, 5, 1, whose sum is 76 <= 256. So no dimension obstruction exists. This is not a proof; it is reassurance that the statement is not absurd. ANSWER 0.8 (what a counterexample would be). A shape lambda of size N_m that the machinery of dominance and induction cannot reach. PARTS 5-9 rule this out: every lambda is either dominated by the staircase (MOVE 1) or reachable from a smaller staircase by at most four horizontal strips (MOVE 4), and the band of MOVE 3 carries every shape with at most four rows. The number four is exactly the largest number of strips MOVE 4 can need, so four is not an accident. --------------------------------------------------------------------- PART 1 -- THE VOCABULARY --------------------------------------------------------------------- ANSWER 1.1 (partition, diagram, size, length). A partition of n is a list alpha = (alpha_1, ..., alpha_k) of positive integers with alpha_1 >= alpha_2 >= ... >= alpha_k and sum alpha_i = n; write alpha |- n. Its SIZE is n, its LENGTH len(alpha) is k (the empty list is the partition of 0, with length 0). The DIAGRAM of alpha is the set of cells (i,j) with 1 <= i <= k and 1 <= j <= alpha_i, drawn as left- justified rows of lengths alpha_1, alpha_2, ..., alpha_k. For instance (3,2,1) is three rows of lengths 3, 2, 1: size 6, length 3. ANSWER 1.2 (conjugate). The conjugate alpha^t has j-th part (alpha^t)_j = #{ i : alpha_i >= j }, the number of rows of length at least j; equivalently, transpose the diagram (rows become columns). Examples: (3,2,1)^t = (3,2,1), so the staircase is self-conjugate; (4,1)^t = (2,1,1,1). Always (alpha^t)^t = alpha and |alpha^t| = |alpha|. Conjugation is NOT "reverse the parts"; it counts columns. ANSWER 1.3 (representation, irreducible). A representation of a group G on a vector space V is a rule assigning to each g in G an invertible linear map V -> V with (gh)v = g(hv) and the identity acting trivially. A subrepresentation is a subspace carried into itself by every g. V is IRREDUCIBLE if its only subrepresentations are 0 and V. We write S^alpha for the irreducible of the symmetric group attached to a partition alpha (defined in ANSWER 1.4); these are exactly all the irreducibles of S_n (THEOREM (JAMES), ANSWER 2.9). ANSWER 1.4 (Specht module). Fix alpha |- n and fill the diagram of alpha with 1, 2, ..., n, each once; the result is a TABLEAU t. Two tableaux are ROW-EQUIVALENT when each row holds the same set of numbers; the class {t} of all tableaux row-equivalent to t is a ROW TABLOID, and S_n permutes tabloids by permuting entries. Let C_t be the subgroup of permutations that preserve each COLUMN of t as a set, and define the POLYTABLOID e_t = sum over c in C_t of sgn(c) * c {t}, with sgn the sign (+1 even, -1 odd). Then the span of { g e_t : g in S_n } is the SPECHT MODULE S^alpha. It is irreducible, depends on alpha only up to isomorphism, and the S^alpha for alpha |- n are exactly the irreducibles of S_n (THEOREM (JAMES)). Reference: James 1978, The Representation Theory of the Symmetric Groups. ANSWER 1.5 (tensor product, diagonal action). If V and W are representations of G, then V (x) W is spanned by symbols v (x) w, is bilinear in (v,w), and carries the DIAGONAL action g(v (x) w) = gv (x) gw. For example C^p (x) C^q ~= C^{pq} for the trivial group. ANSWER 1.6 (Kronecker coefficient). For partitions alpha, beta, lambda of n, g(alpha, beta, lambda) = dim Hom_{S_n}(S^lambda, S^alpha (x) S^beta), where Hom is the space of S_n-equivariant linear maps (maps phi with phi(gv) = g phi(v)). Since S_n is completely reducible (ANSWER 3.1), this number equals the MULTIPLICITY of S^lambda as a summand of S^alpha (x) S^beta. Thus g(alpha, beta, lambda) > 0 means exactly "S^lambda occurs in the square". ANSWER 1.7 (dominance, and why conjugation reverses it). For partitions of the same size write lambda >= mu when lambda_1 + ... + lambda_k >= mu_1 + ... + mu_k for every k >= 1, missing parts counted as 0. (Once k is large both sides are n.) This is a PARTIAL order. Example: (3,2,1) dominates (2,2,2), and (3,3) dominates (4,1,1); note (3,3) and (4,1,1) lie on opposite sides of (3,2,1). Dominance reverses under conjugation: lambda >= mu <=> mu^t >= lambda^t. Proof: for every integer q >= 1, sum_i max(lambda_i - q, 0) = max_{k>=0} ( sum_{i<=k} lambda_i - k q ), sum_{j<=q} lambda^t_j = n - sum_i max(lambda_i - q, 0). So lambda >= mu increases the first display and therefore decreases the second; this implication applied to conjugates gives the converse. ANSWER 1.8 (horizontal strip). If nu is contained in lambda (each part of nu at most the corresponding part of lambda), the skew diagram lambda/nu is the set of cells of lambda not in nu. It is a HORIZONTAL STRIP when each of its columns contains at most one cell, i.e. it is a union of boxes at the ends of rows, never two stacked. Example: (4,2)/(3,1) is a horizontal strip (cells in columns 4 and 2); (3,2,1)/(1) has cells (1,2),(1,3),(2,1),(2,2),(3,1); columns 1 and 2 each get two cells, so it is not. ANSWER 1.9 (induction of representations). If H is a subgroup of a finite group G and A is a representation of H, the induced representation is Ind_H^G A = C[G] (x)_{C[H]} A, the tensor of the group algebra with A over the subalgebra C[H]; G acts by left multiplication in the first factor. Concretely it has dimension [G:H] * dim A and is a direct sum of one copy of A in each coset of H. Reference: Fulton-Harris, Proposition 3.3 and Section 3.3 (disjoint cosets). ANSWER 1.10 (sign representation and sign twist). The SIGN representation sgn of S_n is one-dimensional, with g acting by sgn(g) (+1 or -1). Twisting a representation by the sign changes the group action by that sign: (S^lambda (x) sgn) carries g acting as sgn(g) g on S^lambda. For Specht modules the twist only transposes the shape: S^lambda (x) sgn ~= S^{lambda^t}. Reference: James 1978, Theorems 6.7. ANSWER 1.11 ("separate" versus "diagonal" products). Two representations P of H and Q of K combine to the OUTER tensor product P (boxtimes) Q, a representation of H x K by (h,k)(p (x) q) = hp (x) kq, where the two groups act on DIFFERENT factors. This is only notation for "let the two subgroups act on the two tensor factors independently", which is what happens in PARTS 6-9; it never involves a diagonal action. The companion "diagonal" product (x) of ANSWER 1.5 has ONE group acting on both factors; the two usages are always written differently. --------------------------------------------------------------------- PART 2 -- THE STANDARD TOOLS --------------------------------------------------------------------- ANSWER 2.1 (word basis and the position action). Let B be a finite set of positions and E a vector space with ordered basis e_1, ..., e_d. The tensor power E^{tensor B} (one factor for each position in B) has the WORD BASIS e_a = tensor over b in B of e_{a(b)}, indexed by functions a: B -> {1,...,d}. The group S_B acts by permuting positions: g e_a = e_{a o g^{-1}} , i.e. (g e_a) at position b equals e_{a(g^{-1} b)}. Regrouping a tensor product that is indexed by a set B into a product over a set partition of B is an ordinary tensor identification and introduces NO signs; signs enter only through explicit alternating sums (ANSWER 2.3). ANSWER 2.2 (block tensors). Let L be a set partition of B whose blocks all have size at most d. For each block A choose an ordering A = (b_1, ..., b_r) and set v_A = sum over pi in S_r of sgn(pi) * (e_{pi(1)} at b_1) (x) ... (x) (e_{pi(r)} at b_r), v_L = tensor over A in L of v_A . Changing the ordering of a block multiplies v_A, hence v_L, by a sign. Every nonzero word coefficient of v_L is +1 or -1: on a block of size r the letters used are exactly 1, ..., r, each once. ANSWER 2.3 (LEMMA: ALTERNATING BLOCKS ARE POLYTABLOIDS). With L, B, E as in ANSWER 2.2 define theta_i = #{ A in L : |A| >= i }, so the block sizes, written in nonincreasing order, are the COLUMN lengths of theta. Then C[S_B] v_L ~= S^theta . The same statement holds if E is replaced by the dual space E^* with any chosen basis. Proof. Arrange the blocks as the columns of a tableau t of shape theta, tallest columns first and each ordered block placed top to bottom, using the cells of B as entries. A row tabloid {t'} records the set of entries in each row; the permutation module M^theta is spanned by these tabloids. Send {t'} to the word that assigns the letter i to every entry of row i. Row i of theta has theta_i cells, so this word has content theta (letter i occurs theta_i times); the map is an S_B-equivariant linear bijection from the tabloid basis of M^theta onto the word basis of content theta. Let C_t be the subgroup permuting entries within each column of t. Under this bijection the polytabloid e_t = sum_{c in C_t} sgn(c) c {t} maps to v_L: in a single column-slot, applying a column permutation c to the entries replaces the assignment pi of letters by its inverse, and a permutation and its inverse have the same sign. The image is nonzero (the identity assignment of letters has coefficient 1). By definition (THEOREM (JAMES), ANSWER 2.9) the span of the translates of e_t is the Specht module S^theta. This proves C[S_B] v_L ~= S^theta. For a dual space the same proof runs with any chosen basis: an invertible basis change on E^* induces an invertible S_B-equivariant map on its tensor power. QED ANSWER 2.4 (self-duality and the sign twist). For every alpha |- n, (S^alpha)^* ~= S^alpha and S^alpha (x) sgn ~= S^{alpha^t} . The first holds because the standard inner product on the tabloid space makes the Specht module self-dual; the second is ANSWER 1.10. Reference: James 1978, Theorems 4.12 and 6.7. ANSWER 2.5 (LEMMA: PIERI). For nu |- a and b >= 0, Ind_{S_a x S_b}^{S_{a+b}} ( S^nu (boxtimes) 1 ) ~= direct sum, over partitions lambda |- a+b with lambda containing nu and lambda/nu a horizontal strip of size b, of S^lambda , each summand once. (Here S_a x S_b sits inside S_{a+b} as the permutations of the first a and last b letters.) Reference: James 1978, Section 16, Rule 16.4 (the one-row case of Littlewood-Richardson; all b skew entries are 1, so column strictness is exactly the horizontal-strip condition). ANSWER 2.6 (LEMMA: YOUNG'S RULE). Let theta = (theta_1, ..., theta_l) |- n. The permutation module has the induced realization M^theta = Ind_{S_{theta_1} x ... x S_{theta_l}}^{S_n} 1 , where S_{theta_1} x ... x S_{theta_l} permutes the first theta_1 letters, the next theta_2 letters, and so on. Then S^tau occurs in M^theta if and only if tau >= theta; and S^theta occurs with multiplicity exactly one. Also, the permutation module attached to any reordering of the parts of theta is isomorphic to M^theta. Proof. The case n = 0 is trivial. By transitivity of induction and PIERI (ANSWER 2.5), the multiplicity of S^tau in M^theta counts chains empty = nu^(0) c= nu^(1) c= ... c= nu^(l) = tau, |nu^(k) / nu^(k-1)| = theta_k , whose successive differences are horizontal strips (here "c=" means "contained in"). NECESSITY. A horizontal strip raises the first-column height by at most one, so nu^(k) has at most k rows; since nu^(k) is contained in tau, theta_1 + ... + theta_k = |nu^(k)| <= tau_1 + ... + tau_k . For k >= l both sides are n. This is tau >= theta. If tau = theta, all inequalities are equalities, forcing nu^(k) to be the first k rows of theta; these diagrams do form such a chain, so the multiplicity is one. SUFFICIENCY. Assume tau >= theta and induct on l. For l = 1, tau = (n). For l > 1 let t = theta_l. There are at least t columns of tau, since tau_1 >= theta_1 >= t. Delete the bottom box of each of the t TALLEST columns, choosing the RIGHTMOST columns first among equal heights; call the rest nu. The column heights of nu are still nonincreasing: distinct adjacent heights differ by at least one, and inside any group of equal heights exactly a suffix is lowered. So nu is a partition and tau/nu is a horizontal t-strip. For every k >= 1 the loss in the first k rows is (tau_1 + ... + tau_k) - (nu_1 + ... + nu_k) = max(0, t - tau_{k+1}), because the tau_{k+1} columns of height more than k are deleted before any column whose bottom box lies in the first k rows. If this loss is zero, the desired inequality nu_1 + ... + nu_k >= theta_1 + ... + theta_k is immediate. If it is positive and k < l, then nu_1 + ... + nu_k = (tau_1 + ... + tau_{k+1}) - t >= (theta_1 + ... + theta_{k+1}) - t >= theta_1 + ... + theta_k . Finally, dominance at l gives len(tau) <= l and dominance at l-1 gives tau_l <= t, so ALL tau_l columns of height l are deleted; the last row of nu disappears, len(nu) <= l-1, and every remaining initial sum equals the total n - t. Hence nu >= (theta_1, ..., theta_{l-1}), and induction gives a chain ending at nu; appending the deleted strip gives the chain ending at tau. This proves sufficiency and one occurrence of S^theta, and hence the lemma. The "reordering" statement holds because the stabilizer of a word with prescribed letter multiplicities is the product of the symmetric groups on its equal-letter position sets, and reordering the multiplicities conjugates that product. QED ANSWER 2.7 (COROLLARY: what M^{rho_m} contains). Take theta = rho_m = (m, m-1, ..., 1). Then M^{rho_m} contains S^{rho_m} exactly once, and it contains S^tau for every tau with tau >= rho_m. This is exactly YOUNG'S RULE applied to theta = rho_m; it is used in PART 5. ANSWER 2.8 (COROLLARY: chains of strips). Applying PIERI repeatedly, as in the proof of YOUNG'S RULE, shows: if nu = nu^(0) c= nu^(1) c= ... c= nu^(q) = lambda are partitions with every difference nu^(i)/nu^(i-1) a horizontal strip, then S^lambda occurs in the representation induced from S^nu (boxtimes) 1, where the induction runs from the Young subgroup permuting the q strips' position sets separately up to the full symmetric group. This is the device that turns a chain of strips into a constituent statement in PARTS 8-9. ANSWER 2.9 (THEOREM (JAMES): the complete list). The modules S^alpha for alpha |- n are pairwise non-isomorphic, irreducible, and exhaust the irreducible representations of S_n. Reference: James 1978, Theorems 4.12 and 6.7. ANSWER 2.10 (hook-length formula). For alpha |- n with diagram cells (i,j), the HOOK LENGTH of (i,j) is h(i,j) = (alpha_i - j) + (alpha^t_j - i) + 1, the number of cells of alpha in the same row to the right, plus those in the same column below, plus the cell itself. Then dim S^alpha = n! / ( product over cells (i,j) of h(i,j) ). For instance alpha = (3,2,1) has hook lengths 5, 3, 1, 3, 1, 1, product 45, and dim S^{(3,2,1)} = 720/45 = 16, as used in ANSWER 0.7. Reference: James 1978, Chapter 20 (or any standard text). --------------------------------------------------------------------- PART 3 -- THREE GENERAL FACTS ABOUT SPLITTING INTO PIECES --------------------------------------------------------------------- ANSWER 3.1 (complete reducibility). Every finite-dimensional complex representation of a finite group is a direct sum of irreducible subrepresentations. Consequences used below: (a) the multiplicity of an irreducible S^lambda in a module V equals dim Hom_G(S^lambda, V); (b) if a module has an irreducible QUOTIENT of type lambda, then it has an irreducible SUBMODULE of type lambda, i.e. lambda occurs as a summand. Reference: Fulton-Harris, Proposition 1.5 and Corollary 1.6. ANSWER 3.2 (Frobenius reciprocity). For H a subgroup of a finite group G, a representation A of H, and a representation V of G, Hom_G( Ind_H^G A , V ) ~= Hom_H( A , Res_H^G V ), where Res_H^G V is V viewed as an H-module. In words: an H-equivariant map A -> V produces a G-equivariant map Ind_H^G A -> V and conversely. Reference: Fulton-Harris, Proposition 3.17. Also used: induction is transitive ( Ind_K^G Ind_H^K A ~= Ind_H^G A ) and distributive over direct sums, and dimensions multiply: dim Ind_H^G A = [G:H] dim A. ANSWER 3.3 (invariant pairing gives a map into a dual). Let E have a basis e_1,...,e_d and E^* the dual basis. The evaluation pairing between E^{tensor B} and (E^*)^{tensor B} pairs a word e_a with the dual word of the same index to 1 and different indices to 0. For g in S_B, < g u , g t > = < u , t > , because g only moves both sides along the same permutation of positions. Hence if T is a subspace of (E^*)^{tensor B} stable under S_B, then x |--> ( t |--> < x , t > ) is an S_B-equivariant linear map from E^{tensor B} to the dual T^*. On generators it reads phi(gx)(t) = = = (g phi(x))(t). This is used in PART 7, as the map PHI there, to detect constituents. ANSWER 3.4 (Schur, and when an equivariant map is onto). Over C, a nonzero S_B-equivariant linear map from an irreducible module to an irreducible module is an isomorphism; more generally the image of an equivariant map is a subrepresentation. Hence an equivariant map whose target is irreducible and whose image is nonzero is ONTO that target. This is exactly what turns a single nonzero pairing in PART 7 into a statement that a whole irreducible occurs. --------------------------------------------------------------------- PART 4 -- THE TRIANGLE AND THE CYCLIC MODULE W_m --------------------------------------------------------------------- ANSWER 4.1 (the position set B_m). For m >= 1 let B_m = { (i,j) in Z_{>=1}^2 : i + j <= m + 1 }. This is a triangular array: row i has cells j = 1, 2, ..., m+1-i, so |B_m| = (m) + (m-1) + ... + 1 = N_m. For example B_3 has rows of lengths 3, 2, 1. Let G_m = S_{B_m} be the group of all permutations of these N_m cells. ANSWER 4.2 (rows and columns as set partitions). Let R_m = { R_{m,i} : 1 <= i <= m }, R_{m,i} = { (i,j) : 1 <= j <= m+1-i }, C_m = { C_{m,j} : 1 <= j <= m }, C_{m,j} = { (i,j) : 1 <= i <= m+1-j }, be the set partitions of B_m into rows and into columns. Order each row by increasing j and each column by increasing i. Both set partitions have block sizes m, m-1, ..., 1, one block of each size. ANSWER 4.3 (the row and column generators, and their type). Let E_m = C^m with ordered basis e_1, ..., e_m. Build the block tensors v_{R_m} and v_{C_m} from ANSWER 2.2 (each block of size r uses the letters e_1, ..., e_r in an alternating sum). For a set partition with block sizes m, m-1, ..., 1, the shape theta of ANSWER 2.3 satisfies theta_i = #{ blocks of size >= i } = m - i + 1, i.e. theta = rho_m. Therefore, by LEMMA (ALTERNATING BLOCKS ARE POLYTABLOIDS), V_R := C[G_m] v_{R_m} ~= S^{rho_m}, V_C := C[G_m] v_{C_m} ~= S^{rho_m}. ANSWER 4.4 (the cyclic module W_m). Place the two layers in the same positions B_m and use the DIAGONAL action of G_m on the tensor product: w_m = v_{R_m} (x) v_{C_m} in E_m^{tensor B_m} (x) E_m^{tensor B_m}, W_m = C[G_m] w_m (its cyclic span). Because each layer is a G_m-module of type rho_m, W_m is a submodule of V_R (x) V_C ~= S^{rho_m} (x) S^{rho_m}. Here (x) on the right is the diagonal product of ANSWER 1.5: one g acts on both Specht factors at once. ANSWER 4.5 (the statement we prove). Recall lambda ranges over all partitions of N_m. THEOREM (CYCLIC STAIRCASE SUPPORT). For every m >= 1 and every partition lambda of N_m, the irreducible S^lambda occurs as a submodule (equivalently, as a summand) of W_m. ANSWER 4.6 (why this implies THEOREM (SAXL)). By ANSWER 4.4, W_m is a submodule of S^{rho_m} (x) S^{rho_m}. If S^lambda occurs in W_m it occurs in that tensor square, so g(rho_m, rho_m, lambda) > 0. Conversely the theorem asks for more than positivity, but only positivity is needed for Saxl. The rest of the file proves THEOREM (CYCLIC STAIRCASE SUPPORT) by induction on m; the induction is assembled in PART 9 out of PARTS 5-8. --------------------------------------------------------------------- PART 5 -- MOVE 1: THE DOMINATED CASE --------------------------------------------------------------------- Throughout, rho_m = (m, m-1, ..., 1) and lambda is a partition of N_m. This part proves that every shape "dominated by the staircase" already occurs in W_m, and with that finishes MOVE 1 of the plan. ANSWER 5.1 (PROPOSITION: DOMINATED CASE). If rho_m >= lambda, then S^lambda occurs as a submodule of W_m. Recall (ANSWER 1.7) that rho_m >= lambda means each initial sum lambda_1 + ... + lambda_k is at most the staircase sum m + (m-1) + ... + (m+1-k), for every k. The proof has six steps, labelled (a)-(f) inside. Write eps for the sign representation of G_m (ANSWER 1.10) and remember the sign twist S^mu (x) eps ~= S^{mu^t} (ANSWER 2.4). Proof of the PROPOSITION. (a) REDUCTION TO A STATEMENT ABOUT W_m (x) eps. Since rho_m is its own conjugate, conjugation of dominance (ANSWER 1.7) gives rho_m >= lambda <=> lambda^t >= rho_m^t = rho_m . Twisting twice by the sign does nothing, so S^lambda occurs in W_m <=> S^{lambda^t} occurs in W_m (x) eps . By YOUNG'S RULE (ANSWER 2.7) the constituents of the permutation module M^{rho_m} are exactly the S^tau with tau >= rho_m. Therefore it suffices to prove the following single statement: (STAR) W_m (x) eps contains S^tau for every tau >= rho_m. We now prove (STAR). (b) THE SIGNED AVERAGE, AND WHY IT IS NONZERO. Let H_R = product over i of S_{R_{m,i}} be the row subgroup of G_m (it permutes the cells within each row and only within rows). By construction v_{R_m} is alternating inside every row, so each h in H_R acts on it by the sign: h v_{R_m} = eps(h) v_{R_m} . Applying such an h diagonally to w_m = v_{R_m} (x) v_{C_m} gives h w_m = eps(h) v_{R_m} (x) h v_{C_m}, hence eps(h) h w_m = v_{R_m} (x) h v_{C_m}. Summing over h in H_R, sum_{h in H_R} eps(h) h w_m = v_{R_m} (x) u, u := sum_{h in H_R} h v_{C_m} . We claim u is not zero. Consider the word a_0 given by a_0(i,j) = i (the i-th row is filled with the letter i). It is unchanged by any row permutation, so h^{-1} e_{a_0} = e_{a_0} for all h in H_R. Its coefficient in v_{C_m} is 1: within each (increasingly ordered) column, a_0 assigns the letters 1, 2, ..., (column length) in order, which is the identity assignment and enters the alternating sum with sign +1. Therefore its coefficient in every h v_{C_m} is also 1, and its coefficient in u is |H_R| = (m)! (m-1)! ... (1)! != 0 . So u != 0, and v_{R_m} (x) u != 0. (c) THE ALTERNATING LINE IN V_R IS ONE-DIMENSIONAL. The space of H_R-equivariant maps from eps to V_R (equivalently, the eps-isotypic line of V_R as an H_R-module) has dimension dim Hom_{H_R}( eps , Res_{H_R} V_R ) = dim Hom_{G_m}( Ind_{H_R}^{G_m} eps , V_R ) (Frobenius, ANSWER 3.2) = dim Hom_{G_m}( M^{rho_m} (x) eps , V_R ) ( Ind_{H_R}^{G_m} eps = M^{rho_m} (x) eps ) = dim Hom_{G_m}( M^{rho_m} , V_R (x) eps ) (twist by eps on V_R) = dim Hom_{G_m}( M^{rho_m} , S^{rho_m} ) ( V_R (x) eps ~= S^{rho_m} as rho_m^t = rho_m ) = 1 . ( S^{rho_m} occurs once in M^{rho_m}, ANSWER 2.7 ) Since v_{R_m} is nonzero and alternating under H_R, it spans this one- dimensional line. (d) FOLDING THE TWIST INTO ONE FACTOR. The reassociation (V_R (x) V_C) (x) eps -> V_R (x) (V_C (x) eps), (x (x) y) (x) z |-> x (x) (y (x) z) is an isomorphism of G_m-modules. Choose a G_m-isomorphism phi : V_C (x) eps -> V_R (possible because both sides are copies of S^{rho_m}), and a nonzero element z of the one-dimensional space eps. As u is H_R-fixed (it is a sum of all its translates), the vector u (x) z satisfies h (u (x) z) = u (x) h z = eps(h) (u (x) z), so it is alternating under H_R, i.e. lies in the eps-component. Its image phi(u (x) z) therefore lies in the eps-line of V_R, which by (c) is C v_{R_m}: phi(u (x) z) = c v_{R_m}, c != 0 (c != 0 because phi is injective and u (x) z != 0). Now tensor the identity of (b) with z, reassociate by (d), and apply id (x) phi: ( sum_h eps(h) h w_m ) (x) z |--> v_{R_m} (x) phi(u (x) z) = c (v_{R_m} (x) v_{R_m}) . The left side is a vector of W_m (x) eps (a combination of translates of w_m, then tensored with z). Because the reassociation-and-phi map is a G_m-isomorphism, its image of the whole submodule W_m (x) eps is a submodule containing c(v_{R_m} (x) v_{R_m}). Hence it contains the cyclic module Z_m := C[G_m] ( v_{R_m} (x) v_{R_m} ) inside V_R (x) V_R . We will find every S^tau, tau >= rho_m, inside Z_m; then it occurs also in the isomorphic copy W_m (x) eps, proving (STAR). (e) A G-EQUIVARIANT MAP FROM Z_m ONTO A PERMUTATION MODULE. Let E_out have basis f_1, ..., f_{2m-1} and define the local linear map q : E_m (x) E_m -> E_out, q(e_a (x) e_b) = f_{a+b-1} . Regroup the two tensor layers by position (ANSWER 2.1) and apply q at every position; then project onto the span M_alpha of words in which the letter r occurs exactly r times for 1 <= r <= m and no letter exceeds m. The content is alpha = (1, 2, ..., m, 0, ..., 0), and M_alpha is the word module of that content. Call the resulting linear map Q : E_m^{tensor B_m} (x) E_m^{tensor B_m} -> M_alpha . It is G_m-equivariant: the local map q is the same at every position, and content is unchanged by permuting positions. We compute Q on v_{R_m} (x) v_{R_m}. In a summand of v_{R_m} (x) v_{R_m}, on a row of length r the two assignments are (a_1,...,a_r) and (b_1,...,b_r), each a permutation of 1,...,r; set c_j = a_j + b_j - 1. Then sum_j c_j = 2 * (1 + 2 + ... + r) - r = r^2 , sum_j c_j^2 - r^3 = sum_j (c_j - r)^2 >= 0 . (Cauchy-Schwarz, termwise) Summed over all rows, a term retained by the content projection has total sum over positions of (output letter)^2 = sum_{r=1}^m r * r^2 = sum_{r=1}^m r^3 , because letter r occurs r times. But the rows contribute lengths m, m-1, ..., 1, so the same total also equals sum over rows of (row's contribution) >= sum over rows of (r^3) = sum_{r=1}^m r^3. Every row therefore meets its inequality with equality, i.e. c_j = r at every cell of the row of length r. There is thus exactly one retained output word, t_m = tensor over (i,j) in B_m of f_{m+1-i} , the word that puts the letter m+1-i on every cell of row i. (f) THE COEFFICIENT IS NONZERO, AND THE QUOTIENT IS M^{rho_m}. On a row of length r, each of the r! choices a_j = pi(j) has the unique compatible assignment b_j = r+1-pi(j) = (omega_r o pi)(j), where omega_r(j) = r+1-j. The two alternating signs multiply to sgn(pi) sgn(omega_r o pi) = sgn(omega_r) = (-1)^{r(r-1)/2} . The rows are independent, so there is no cancellation and Q(v_{R_m} (x) v_{R_m}) = ( (-1)^{ sum_{r=1}^m r(r-1)/2 } * (1! 2! ... m!) ) * t_m != 0 . The stabilizer in G_m of t_m is exactly H_R, because the equal-letter sets of t_m are exactly the rows of B_m. Hence the orbit G_m t_m is a basis of M_alpha and Q(Z_m) = C[G_m] t_m = M_alpha ~= M^{rho_m} (the last isomorphism reorders the content (1,...,m) back to rho_m; see ANSWER 2.6). So Q restricted to Z_m is a G_m-equivariant surjection Z_m -> M^{rho_m}. By YOUNG'S RULE (ANSWER 2.7) every S^tau with tau >= rho_m is a constituent of M^{rho_m}; since M^{rho_m} is a quotient of Z_m, all these S^tau are constituents of Z_m. By complete reducibility (ANSWER 3.1) they occur as submodules of Z_m, hence of W_m (x) eps. This proves (STAR), and by (a) it proves the PROPOSITION. QED --------------------------------------------------------------------- PART 6 -- MOVE 2: CUTTING OFF A BAND AND THE INDUCED QUOTIENT --------------------------------------------------------------------- The dominated case (PART 5) handles shapes below the staircase. For the rest we cut the triangle into a smaller triangle plus a thin BAND along the hypotenuse, and express W_m as a quotient of a full INDUCED module built from the smaller triangle and the band. This part proves the quotient; PART 7 studies the band. ANSWER 6.1 (the band data). Fix s in {1, 2} and put h = m - s >= 1, D = B_h (the smaller triangle), F = B_m minus D (the band), G = G_m, H = S_D x S_F (a subgroup of G). The band has |F| = N_m - N_h = s(2m-s+1)/2 cells: for s = 1 it is the single antidiagonal i+j = m+1 (m cells); for s = 2 it is the two outermost diagonals (2m-1 cells). Let R_F and C_F be the set partitions of F into the nonempty intersections of F with the rows and columns of B_m (orders inherited). Every block of R_F or C_F has size at most s. On two layers with alphabet 1, ..., s define the band generator and its cyclic module u_{m,s} = v_{R_F} (x) v_{C_F}, U_{m,s} = C[S_F] u_{m,s} . The index m records the length of the band. Our target is a quotient of W_m induced from W_h (boxtimes) U_{m,s}. ANSWER 6.2 (LEMMA: SECTOR INDUCTION). Let a finite group G act transitively on a finite set Omega. Suppose a G-module T is a direct sum T = direct sum over A in Omega of T_A , with g T_A = T_{gA} . Fix D in Omega, let H be its stabilizer in G, and take z in T_D. Put A_0 = C[H] z. Then the map PHI : C[G] (x)_{C[H]} A_0 -> C[G] z, g (x) a |-> g a is an isomorphism of G-modules. Proof. The defining relation (gh)(x)a = g(x)ha of the balanced tensor gives the same image on both sides, so PHI is well defined, G-equivariant, and onto. For the inverse, for each A choose g_A in G with g_A D = A, and let pi_A: T -> T_A be the coordinate projection. Since C[G] z = direct sum over A of g_A A_0, with g_A A_0 contained in T_A, each g_A^{-1} pi_A(y), for y in C[G] z, lies in A_0. Define PSI(y) = sum over A in Omega of g_A (x) g_A^{-1} pi_A(y) . Replacing g_A by g_A h (h in H) does not change g_A (x) g_A^{-1} pi_A(y), because g_A h (x) h^{-1} a = g_A (x) a in the balanced tensor. Clearly PHI PSI (y) = sum_A pi_A(y) = y. Conversely, for g (x) a let A = gD and write g = g_A h; only the A-sector is nonzero, and PSI PHI (g (x) a) = g_A (x) h a = g (x) a. So PHI and PSI are mutually inverse. QED ANSWER 6.3 (PROPOSITION: BAND QUOTIENT). For the data of ANSWER 6.1 there is a surjective G_m-equivariant linear map W_m ->> Ind_{S_D x S_F}^{S_{B_m}} ( W_h (boxtimes) U_{m,s} ) . In particular every irreducible constituent of the right side is also a constituent of W_m. Proof, in five steps. (a) THE LOCAL PROJECTION AND THE HIGH POSITIONS. Use the ordinary tensor identification E_m^{tensor B_m} (x) E_m^{tensor B_m} ~= (E_m (x) E_m)^{tensor B_m}. Call letters 1, ..., s LOW and letters s+1, ..., m HIGH, and put E_lo = span(e_1,...,e_s), E_hi = span(e_{s+1},...,e_m). On a single pair-letter basis vector define p_s(e_a (x) e_b) = e_a (x) e_b if (a <= s and b <= s) or (a > s and b > s); p_s(e_a (x) e_b) = 0 otherwise; and set P_s = p_s^{tensor B_m}. The same local map is used at every position, so P_s commutes with G = G_m. A retained position is HIGH when both of its letters are above s. (b) THE HIGH SET IS EXACTLY D. Let A be the set of high positions in a retained word of w_m. In row i the first alternating layer uses the letters 1, ..., m+1-i in some order; among these exactly r_i = max(h+1-i, 0) exceed s (they are s+1, ..., m+1-i when that range is nonempty). Since a cell survives the projection only if its high first letter is accompanied by a high second letter, row i has exactly r_i high cells. Likewise, in column j the second layer uses 1, ..., m+1-j, of which d_j = max(h+1-j, 0) exceed s, so column j has exactly d_j high cells. Thus the 0-1 matrix of the set A has row sums r_i and column sums d_j. Now r_i and d_j are exactly the row and column counts of the smaller triangle B_h, and for every k, r_1 + ... + r_k = #{ (i,j) in B_h : i <= k } = sum over j of min(k, d_j) . The number of A-cells in the first k rows is r_1 + ... + r_k, while column j has only d_j cells total, so it contributes at most min(k, d_j) of them; the two counts agree only if every column j puts ALL its d_j high cells in its top d_j rows. Hence A = { (i,j) in B_m : i <= h+1-j } = B_h = D . (Equivalently, this is the equality case of the Ryser row-column margin inequalities.) So the projected generator P_s(w_m) is concentrated on words that are high exactly on the smaller triangle D. (c) 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), and its intersection with F has length b = min(r, s). A retained assignment puts the high letters s+1, ..., r on the initial segment and the low letters 1, ..., b on the final segment. Let Alt(list) denote the unnormalized alternation of a displayed list (Alt of the empty list is 1). The part of the block tensor with this prescribed high set is exactly (-1)^{a b} * Alt(e_{s+1}, ..., e_r) (x) Alt(e_1, ..., e_b) . Indeed, in the position order every high letter precedes every low letter, contributing a b inversions; all other inversions are internal to the two independently permuted lists, and every such pair of permutations occurs once. When r <= s the high list is empty and this is just the original alternation. Rows and columns both have the length list m, m-1, ..., 1, so their cross signs multiply to product over r of (-1)^{2 max(r-s,0) min(r,s)} = 1 . Identify E_h with E_hi by e_a |-> e_{s+a}, and write w-tilde_h and W-tilde_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 R_F and C_F. Regrouping the factors over the disjoint sets D and F introduces no signs, so z := P_s(w_m) = w-tilde_h (x) u_{m,s} != 0 (the tensors are nonzero because each nonzero block has a coefficient 1). (d) THE SUBGROUP ORBIT. The two factors of H = S_D x S_F act on z independently, while each acts diagonally on the two layers over its own position set. Hence A_0 := C[H] z = span{ (sigma w-tilde_h) (x) (tau u_{m,s}) : sigma in S_D, tau in S_F } = W-tilde_h (boxtimes) U_{m,s} ~= W_h (boxtimes) U_{m,s} . The middle equality expands tensors of linear combinations of the two separate orbit sets. (e) COORDINATE SECTORS. Let Omega be the set of subsets A of B_m of size |D|. Inside the pair-letter space define T_A = (E_hi (x) E_hi)^{tensor A} (x) (E_lo (x) E_lo)^{tensor (B_m minus A)} . These are the coordinate spans of words that are high exactly on A. They have disjoint word bases, so their sum is direct, and g T_A = T_{gA}. By (c), z lies in T_D, and the stabilizer of D in G is exactly H. Now apply LEMMA (SECTOR INDUCTION) with this Omega and A_0 from (d): C[G] z ~= Ind_H^G A_0 ~= Ind_H^G ( W_h (boxtimes) U_{m,s} ) . Since P_s is equivariant, P_s(W_m) = C[G] P_s(w_m) = C[G] z. Restricting this composition to W_m, then applying the inverse map PSI of ANSWER 6.2 and the identification of A_0 in (d), gives the surjection W_m ->> Ind_H^G ( W_h (boxtimes) U_{m,s} ) . The image of this ambient projection need not sit inside the two original Specht factors; the composition is nevertheless a well-defined surjective G-equivariant map onto the displayed induced module. Complete reducibility (ANSWER 3.1) then makes every irreducible constituent of the right side a constituent of W_m. QED --------------------------------------------------------------------- PART 7 -- MOVE 3: WHAT THE BANDS CARRY --------------------------------------------------------------------- PART 6 reduces the problem to constituents of the induced modules Ind ( W_h (boxtimes) U_{m,s} ). To use that reduction we must know which irreducibles occur inside the band modules U_{m,1} and U_{m,2}. The width-one band is trivial; the width-two band carries every shape with at most four rows, and that is MOVE 3. ANSWER 7.1 (the width-one band is trivial). Take s = 1, so h = m - 1, D = B_{m-1}, and F is the antidiagonal i+j = m+1, with m cells. Inside the band, every row block and every column block is a SINGLE cell, and both layers use only the letter 1. Thus u_{m,1} is a nonzero constant word tensor, fixed by every permutation of F, and U_{m,1} ~= S^{(m)} (the trivial representation; here m >= 2). So the width-one cut can only reach shapes whose difference from a smaller shape is one horizontal strip of size m. This is exactly PIERI and feeds case (i) of PART 9. ANSWER 7.2 (the width-two band, and the path). Take s = 2, so h = m - 2, D = B_{m-2}, and F = B_m minus B_{m-2} is the union of the two outermost antidiagonals: the outer diagonal i+j = m+1 (m cells) and the next diagonal i+j = m (m-1 cells), for a total of K = |F| = 2m - 1 cells. Number the cells of F along the zigzag path p_{2j-1} = (m+1-j, j) for 1 <= j <= m, (outer diagonal), p_{2j} = (m-j, j) for 1 <= j <= m-1, (next diagonal). Reading along increasing path index, this walks up the band like a staircase. In this numbering the ROW blocks are the singleton p_1 and the pairs (2,3),(4,5),...,(K-1,K); the COLUMN blocks are the pairs (1,2),(3,4),...,(K-2,K-1) and the singleton p_K. Order each pair by increasing path index and let u be the resulting alternating band tensor. The row orders agree with increasing j, but each of the m-1 column pairs reverses increasing i, so u = (-1)^{m-1} u_{m,2}, U_{m,2} = C[S_F] u . The overall sign does not matter for support, so from here we work with u. ANSWER 7.3 (pair-letters become 2x2 matrices). Put E = C^2 with basis e_1, e_2 and V = E (x) E. Ordinary tensor reassociation (ANSWER 2.1) identifies the two band layers, regrouped by position, with V^{tensor K} in the path order of ANSWER 7.2. Identify the dual V^* with the 2x2 matrices Mat_2(C) by letting a matrix X take the VALUE X_{ab} on the pair e_a (x) e_b. All pairings below are the bilinear evaluation pairing. Write J = [[0, 1], [-1, 0]], adj(X) = [[d, -b], [-c, a]] for X = [[a, b], [c, d]]. ANSWER 7.4 (LEMMA: PATH CONTRACTION). For arbitrary X_1, ..., X_K in Mat_2(C), < u , X_1 (x) ... (x) X_K > = (-1)^{m-1} [ X_1 adj(X_2) X_3 adj(X_4) ... X_{K-2} adj(X_{K-1}) X_K ]_{11} , where [.]_{11} means the (1,1) entry. Proof. The two singleton blocks force the first row-layer index to be 1 (the row singleton p_1 carries the letter e_1 in the row layer) and the last column-layer index to be 1 (the column singleton p_K carries e_1 in the column layer). The coefficient of an alternating pair, in path order, is the entry J_{ab} of J. Writing a_q for the row-layer index and b_q for the column-layer index at position q, the left side equals sum over indices with a_1 = b_K = 1, of ( product_{l=1}^{m-1} J_{b_{2l-1}, b_{2l}} J_{a_{2l}, a_{2l+1}} ) ( product_{q=1}^K (X_q)_{a_q b_q} ). Reading the contracted indices in order from a_1 to b_K turns this into the single matrix entry [ X_1 J X_2^T J X_3 J X_4^T J ... X_{K-2} J X_{K-1}^T J X_K ]_{11} . The transpose on the even positions records that a pair's column index is met before its row index. For X = [[a,b],[c,d]] a direct multiplication gives adj(X) = tr(X) I - X, and J X^T J = - adj(X) . There are m-1 even positions, so replacing each J X^T J by -adj(X) produces the sign (-1)^{m-1}. In particular adjugation is a linear operation on Mat_2(C). QED ANSWER 7.5 (a matrix basis whose alternations are always invertible). We will test shapes by feeding carefully chosen matrices X_q into the contraction formula. Fix once and for all the ordered basis of V^*: M_1 = I = [[1,0],[0,1]], M_2 = Z = [[1,0],[0,-1]], M_3 = T = [[0,1],[1,0]], M_4 = J = Z T = [[0,1],[-1,0]]. These four are linearly independent (I, Z span the diagonal matrices; T, J span the off-diagonal ones). The last three are traceless and pairwise anticommute, and Z^2 = T^2 = I, J^2 = -I, so all four are invertible. ANSWER 7.6 (LEMMA: SEGMENT ALTERNATION). For a global path position q define the linear operation D_q on Mat_2(C) by D_q(X) = X if q is odd, D_q(X) = adj(X) if q is even. For a segment of r <= 4 consecutive positions beginning at position p, define its alternating matrix A_{r,p} = sum over pi in S_r of sgn(pi) D_p(M_{pi(1)}) D_{p+1}(M_{pi(2)}) ... D_{p+r-1}(M_{pi(r)}) . Let e be the number of even positions among p, ..., p+r-1, and let delta = 1 if p is even and 0 otherwise. Then A_{r,p} = r! (-1)^{e - delta} M_1 M_2 ... M_r , so every A_{r,p} is invertible. Their values are r = 1 : I (p odd), I (p even) r = 2 : -2 Z (p odd), 2 Z (p even) r = 3 : -6 J (p odd), -6 J (p even) r = 4 : -24 I (p odd), 24 I (p even) (using M_1 M_2 = I, M_1 M_2 M_3 = Z T = J, M_1 M_2 M_3 M_4 = J J = -I). Proof. Fix a permutation pi and let j be the local slot occupied by M_1 = I. Deleting that I leaves a permutation of M_2, ..., M_r, whose sign is exactly the sign picked up when those pairwise anticommuting matrices are reordered into their canonical order. Moving I from slot 1 to slot j contributes (-1)^{j-1} to sgn(pi) and changes no matrix product, so sgn(pi) M_{pi(1)} ... M_{pi(r)} = (-1)^{j-1} M_1 ... M_r . By ANSWER 7.4, adjugation fixes I and negates each of Z, T, J. Writing epsilon_j = 1 if position p+j-1 is even and 0 otherwise, adjugation adds the sign (-1)^{e - epsilon_j}. Since epsilon_j is congruent to delta+j-1 mod 2, the total sign is (-1)^{e-delta}, independent of pi. Hence all r! summands of A_{r,p} agree, giving the formula for every r (including r = 1). Substituting the canonical products I, Z, J, -I gives the table. QED ANSWER 7.7 (PROPOSITION: FOUR-ROW SUPPORT OF THE WIDTH-TWO BAND). For every m >= 3 and every partition eta of 2m-1 with len(eta) <= 4, the irreducible S^eta occurs in U_{m,2}. Proof. Let r_1, ..., r_c be the column lengths of eta in order, so 1 <= r_j <= 4 and r_1 + ... + r_c = K. Cut the path into CONSECUTIVE segments of these lengths, the j-th beginning at position s_j = 1 + r_1 + ... + r_{j-1}. For any ordered basis N_1, ..., N_4 of V^*, let t_N be the dual tensor whose factor on segment j is sum over pi in S_{r_j} of sgn(pi) N_{pi(1)} (x) ... (x) N_{pi(r_j)} . The segments are the columns of a tableau of shape eta, and the initial basis entries label its rows. By LEMMA (ALTERNATING BLOCKS ARE POLYTABLOIDS) (ANSWER 2.3, applied in the dual space with chosen basis) the product t_N is a polytabloid and T_N = C[S_F] t_N is an irreducible submodule of (V^*)^{tensor K} of type eta. First take N_i = M_i. By multilinearity of the contraction formula (ANSWER 7.4) and the definition of t_M, < u , t_M > = (-1)^{m-1} [ B ]_{11} , B = A_{r_1, s_1} A_{r_2, s_2} ... A_{r_c, s_c} . Indeed, summing independently over the permutations within each segment is exactly the distributive expansion of this ordered product; the segments are consecutive, so no matrix factor is moved across another. By LEMMA (SEGMENT ALTERNATION) (ANSWER 7.6) the matrix B is invertible. Now apply the map PHI of ANSWER 3.3: the invariant evaluation pairing gives Phi : U_{m,2} -> T_N^* , Phi(x)(t) = < x , t > . As shown in ANSWER 3.3 this is S_F-equivariant. We want Phi nonzero on the generator u. If [B]_{11} happened to vanish, conjugate to fix it: the identity adj(X) = tr(X) I - X gives D_q(Q X Q^{-1}) = Q D_q(X) Q^{-1} for every Q in GL_2(C). Choose an eigenvector v of B with eigenvalue beta != 0 (B is invertible), choose Q carrying v to the first coordinate vector, and set N_i = Q M_i Q^{-1}. This is again an ordered basis, and every alternating segment matrix becomes Q A Q^{-1}, so their product becomes Q B Q^{-1}. Since (Q B Q^{-1}) e_1 = beta e_1, < u , t_N > = (-1)^{m-1} [ Q B Q^{-1} ]_{11} = (-1)^{m-1} beta != 0 . Only the TEST covectors changed; u and its endpoint letters are exactly those fixed in ANSWERS 7.2-7.4. So Phi is nonzero on the generator u. Since u generates U_{m,2} and Phi is equivariant, the image is a nonzero subrepresentation of the irreducible (V^*)^{tensor K}-summand T_N^*, which by Schur (ANSWER 3.4) is all of T_N^*. By self-duality (ANSWER 2.4), T_N^* has type eta, so S^eta is a constituent of U_{m,2}. QED ANSWER 7.8 (the conjugation really is needed: an example). Take m = 3 and eta = (2,2,1), whose column lengths are 3, 2, so the two segments begin at positions 1 and 4. Their alternating matrices are A_{3,1} = -6 J and A_{2,4}, where position 4 is even and positions 4,5 are (even, odd), so A_{2,4} = 2 Z. The product is B = (-6 J)(2 Z) = 12 T, whose (1,1) entry is 0, so the naive basis fails. The matrix Q = [[1, 1], [1, 2]] has Q T Q^{-1} = [[1, 0], [3, -1]], whose (1,1) entry is 1; the resulting pairing is 12, and m-1 = 2 gives (-1)^{m-1} = 1, so < u, t_N > = 12 != 0. This is exactly the rescue performed in the proof of ANSWER 7.7. --------------------------------------------------------------------- PART 8 -- MOVE 4: THE HORIZONTAL-STRIP REDUCTION --------------------------------------------------------------------- This is the last combinatorial input. It says that a shape lambda outside the dominance range can always be reached from a SMALLER staircase-sized shape by one or a few horizontal strips, with sharply controlled sizes. ANSWER 8.1 (LEMMA: HORIZONTAL-STRIP REDUCTION). Let m >= 2 and let lambda be a partition of N_m that is NOT dominated by the staircase rho_m (i.e. rho_m >= lambda fails). Then at least one of the following holds. (i) There is a partition nu of N_{m-1} such that lambda/nu is a horizontal strip of size m. (ii) One has m >= 5, and there are partitions nu = lambda^(0) c= lambda^(1) c= ... c= lambda^(q) = lambda, with q <= 4, nu a partition of N_{m-2}, and every difference lambda^(i)/lambda^(i-1) a NONEMPTY horizontal strip; their total size is 2m - 1. (Here "c=" again means "contained in".) Proof, two cases. CASE (i): lambda_1 >= m (a long enough first row). List the column heights of lambda as a weakly decreasing sequence h_1 >= h_2 >= ... >= h_c (so h is the conjugate lambda^t). Since lambda_1 = c >= m there are at least m nonzero columns. Remove the bottom cell of each of the RIGHTMOST m nonempty columns, i.e. subtract 1 from h_{c-m+1}, ..., h_c. The rightmost columns are the shortest, so subtracting 1 from this suffix keeps the sequence weakly decreasing and nonnegative (the entry just before the suffix is at least as large as the first modified entry, and the whole suffix drops by the same amount). Hence the remaining cells form a partition nu, and the removed cells are one per column, a horizontal strip of size m. Since N_m - m = N_{m-1}, we have nu |- N_{m-1}. This is (i). CASE (ii): lambda_1 <= m - 1 (short first row). First find a failure index. The staircase's first m parts sum to N_m, and lambda has the same total N_m, so failure of rho_m >= lambda gives some index k < m with lambda_1 + ... + lambda_k > k m - k(k-1)/2 (compare with the staircase prefix m + (m-1) + ... + (m-k+1) = k m - k(k-1)/2). For k <= 3 this is impossible, because lambda_1 <= m-1 forces lambda_1 + ... + lambda_k <= k (m-1) <= k m - k(k-1)/2 (the right inequality is k(k-1)/2 <= k, true for k <= 3). Hence 4 <= k < m and in particular m >= 5. Because the parts decrease, the mean of the first four is at least the mean of the first k, so lambda_1 + ... + lambda_4 >= (4/k)(lambda_1 + ... + lambda_k) > (4/k)(k m - k(k-1)/2) = 4m - 2(k-1) (since (4/k) k(k-1)/2 = 2(k-1)) >= 2m + 4 (since k <= m-1 gives 2(k-1) <= 2m-4) > 2m - 1 . So the first four rows already contain MORE than 2m-1 cells; this is the "four-row capacity" that makes a four-strip reduction possible. Now "sweep". A FULL SWEEP removes the bottom cell of every nonempty column. If the current row lengths are (a_1 >= a_2 >= ...), a full sweep lowers every positive column height by 1, so the new row lengths are (a_2, a_3, ...): the sweep deletes exactly a_1 cells (one bottom cell in each of the a_1 columns) and replaces (a_1, a_2, ...) by (a_2, a_3, ...). The deleted cells are one per column, a horizontal strip of size a_1. Starting from lambda, the first full sweep removes lambda_1 cells and leaves (lambda_2, lambda_3, ...); the next removes lambda_2; in general four full sweeps from lambda remove lambda_1 + lambda_2 + lambda_3 + lambda_4 cells. Because lambda_1 + ... + lambda_4 > 2m-1, we can remove exactly 2m-1 cells as follows. Perform FULL sweeps while the number R of cells still to be removed exceeds the number of nonempty columns of the current diagram; the count R decreases by the current first row length each time, so after at most three full sweeps R becomes at most the current first row length, i.e. at most the current number of nonempty columns. Then perform one PARTIAL sweep: remove the bottom cell of the R rightmost nonempty columns. Since R is at most the number of columns, this is legal; and it is the same suffix operation as in case (i), so it again leaves a partition. Altogether we used at most 3 + 1 = 4 horizontal strips (at most three full, one partial), each nonempty, removing exactly 2m - 1 cells. The remainder nu has size N_m - (2m-1) = (m-1)(m-2)/2 = N_{m-2} . Reversing the order of the sweeps gives the chain in (ii). This proves the LEMMA. QED ANSWER 8.2 (four strips can really be necessary). Take m = 13 and lambda = (8 repeated 11 times, then 3), that is 8, 8, ..., 8 (eleven times), 3 . Its size is 11*8 + 3 = 91 = N_13. Its first twelve parts sum to 91 while the staircase 13, 12, ..., 2 sums to 90, so domination fails at k = 12, and case (ii) applies. The diagram has 8 columns (lambda_1 = 8), so any horizontal strip in it has at most 8 cells; three strips could remove at most 24 cells, fewer than the required 2m-1 = 25. The sweeps remove 8 + 8 + 8 (three full sweeps) and then 1 cell in a partial sweep, total 25, leaving nu = (8 repeated 7 times, 7, 3), of size 56 + 7 + 3 = 66 = N_11. So four strips are genuinely needed, and the bound q <= 4 is sharp. --------------------------------------------------------------------- PART 9 -- THE INDUCTION, AND BOTH MAIN THEOREMS --------------------------------------------------------------------- We now assemble MOVE 1 (PART 5), the band quotient (PART 6), the band supports (PART 7), and the strip reduction (PART 8) into the induction that proves THEOREM (CYCLIC STAIRCASE SUPPORT), from which THEOREM (SAXL) follows. ANSWER 9.1 (PROOF OF THEOREM (CYCLIC STAIRCASE SUPPORT)). We show: for every m >= 1 and every partition lambda of N_m, the irreducible S^lambda occurs in W_m. Induct on m. BASE m = 1. N_1 = 1, G_1 is the one-element group, W_1 is one-dimensional, and the only partition of 1 is (1). So S^{(1)} occurs in W_1. True. INDUCTIVE STEP. Fix m >= 2, assume the statement holds for all positive indices smaller than m, and fix lambda |- N_m. There are two cases. If rho_m >= lambda, PROPOSITION (DOMINATED CASE) (ANSWER 5.1) supplies S^lambda directly. So assume rho_m >= lambda fails, and apply LEMMA (HORIZONTAL-STRIP REDUCTION) (ANSWER 8.1). CASE (i) OF THE LEMMA: one horizontal strip of size m. By ANSWER 8.1(i) there is nu |- N_{m-1} with lambda/nu a horizontal strip of size m. Take the band cut with s = 1, so h = m-1, D = B_{m-1}, F of size m, and U_{m,1} is the trivial module S^{(m)} (ANSWER 7.1). By the induction hypothesis S^nu occurs in W_{m-1}. By PIERI (ANSWER 2.5), S^lambda occurs in Ind_{S_D x S_F}^{S_{B_m}} ( S^nu (boxtimes) 1 ) , because lambda/nu is a horizontal m-strip. Since S^nu is a summand of W_{m-1}, this induced module is a summand of Ind ( W_{m-1} (boxtimes) U_{m,1} ), which by PROPOSITION (BAND QUOTIENT) (ANSWER 6.3) is a quotient of W_m. Hence S^lambda is a constituent of W_m (complete reducibility, ANSWER 3.1). CASE (ii) OF THE LEMMA: at most four strips totalling 2m-1. By ANSWER 8.1(ii), m >= 5 and there is a chain nu = lambda^(0) c= lambda^(1) c= ... c= lambda^(q) = lambda, with q <= 4, nu |- N_{m-2}, and each difference a nonempty horizontal strip, the total size being K = 2m - 1. Put b_i = |lambda^(i)| - |lambda^(i-1)|, so b_1 + ... + b_q = K. Choose q disjoint subsets of F (of the width-two band, |F| = K) of sizes b_1, ..., b_q, and form the permutation module A = Ind_{S_{b_1} x ... x S_{b_q}}^{S_F} 1 ~= direct sum over eta |- K of (S_F^eta)^{oplus a_eta} , with nonnegative integer multiplicities a_eta. By repeated PIERI and transitivity of induction (ANSWER 3.2), the shape S^lambda occurs in Ind_{S_D x S_F}^{S_{B_m}} ( S^nu (boxtimes) A ) , equivalently (STAR-ii) sum over eta of a_eta * c_{nu,eta}^lambda > 0 , where c_{nu,eta}^lambda = dim Hom( S^lambda, Ind ( S^nu (boxtimes) S^eta ) ) are nonnegative integers. Every constituent of A has at most q <= 4 rows: start from the empty diagram and add the q horizontal strips one at a time; each strip adds boxes with at most one per column, so it can create at most one new row, and q strips create at most q rows. Thus (STAR-ii) gives some eta with at most four rows, a_eta > 0, and c_{nu,eta}^lambda > 0. By PROPOSITION (FOUR-ROW SUPPORT) (ANSWER 7.7; applicable because len(eta) <= 4 and eta |- K, and m >= 5 >= 3) the irreducible S^eta occurs in U_{m,2}. By the induction hypothesis S^nu occurs in W_{m-2} (the index m-2 >= 1 because m >= 5). Since c_{nu,eta}^lambda > 0, S^lambda occurs in Ind ( S^nu (boxtimes) S^eta ), which is a summand of Ind ( W_{m-2} (boxtimes) U_{m,2} ). By PROPOSITION (BAND QUOTIENT) (ANSWER 6.3, with s = 2, h = m-2) this last is a quotient of W_m. Hence S^lambda is a constituent of W_m. Both cases produce S^lambda in W_m, completing the induction. The smaller modules invoked, W_{m-1} and W_{m-2}, both have positive indices (m-1 >= 1, and in case (ii) m-2 >= 3), so the induction is well-founded. This proves THEOREM (CYCLIC STAIRCASE SUPPORT). QED ANSWER 9.2 (PROOF OF THEOREM (SAXL)). W_m is a submodule of S^{rho_m} (x) S^{rho_m}, the tensor square of the staircase irreducible under the diagonal action (ANSWER 4.4). THEOREM (CYCLIC STAIRCASE SUPPORT) (ANSWER 9.1) supplies every S^lambda, lambda |- N_m, inside that submodule, hence inside the tensor square. Therefore g(rho_m, rho_m, lambda) = dim Hom( S^lambda, S^{rho_m} (x) S^{rho_m} ) is positive for every m >= 1 and every partition lambda of N_m. This is THEOREM (SAXL). QED ===================================================================== SUMMARY OF THE LOGICAL DEPENDENCE ===================================================================== Vocabulary and tools: PARTS 1-3 (partitions, Specht modules, dominance, horizontal strips, induction, complete reducibility, Frobenius reciprocity, the invariant pairing). The key construction: PART 4 (the triangle B_m and the cyclic module W_m = C[G_m](v_R (x) v_C)). PART 5 (MOVE 1). rho_m >= lambda => S^lambda in W_m. Method: sign twist, row-average onto v_R (x) u with u != 0, fold the twist into the column factor, extract Z_m = C[G](v_R (x) v_R), map Z_m onto M^{rho_m} via q(e_a (x) e_b) = f_{a+b-1} and a content projection, then Young's rule. PART 6 (MOVE 2). A coordinate projection P_s gives a SURJECTION W_m ->> Ind ( W_h (boxtimes) U_{m,s} ), s = 1 or 2, h = m - s. Method: the high set is forced to be exactly B_h; the generator factors as w_h (x) u_{m,s}; disjoint coordinate sectors realise the disjoint-coset model of induction. PART 7 (MOVE 3). U_{m,1} is trivial; U_{m,2} contains every S^eta with len(eta) <= 4. Method: path contraction of a word of 2x2 matrices; a matrix basis whose alternated segment products are invertible; conjugation to make the endpoint entry nonzero. PART 8 (MOVE 4). Outside the dominance range, lambda is one horizontal m-strip above N_{m-1}, or at most four strips totalling 2m-1 above N_{m-2}. The number four is sharp (ANSWER 8.2). PART 9. Induction on m assembles all four moves into THEOREM (CYCLIC STAIRCASE SUPPORT), which immediately yields THEOREM (SAXL). This is the complete proof. Every ingredient is either proved above or cited in PARTS 2-3.