=====================================================================
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) = <gx,t> = <x, g^{-1} 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.