The problem. For a partition lambda of n, let S^lambda denote the
irreducible complex representation of the symmetric group S_n indexed
by lambda. The Kronecker coefficients are
g(lambda,mu,nu) = dim Hom_{S_n}(S^nu,S^lambda (x) S^mu),
the dimension of the space of S_n-equivariant maps from S^nu to
S^lambda tensor S^mu, where the tensor carries the diagonal S_n
action. A COVERING SQUARE for n is a partition lambda of n satisfying
g(lambda,lambda,nu) > 0 for every partition nu of n. A single
irreducible S^lambda then has a tensor square S^lambda tensor S^lambda
that contains every irreducible S^nu as a direct summand. The tensor
square conjecture for symmetric groups, formulated by Pak, Panova and
Vallejo, asserts that a covering square exists for every n at least
three other than 4 and 9. The tensor squares of S_n are square
matrices rather than square diagrams, so this is a question about
Kronecker coefficients, not about Young diagrams in the naive sense.
./ref-1304.0738v2.pdf
The precise form of the assertion is the following.
MAIN THEOREM. For every positive integer n other than 2, 4 and 9,
there exists a partition lambda of n such that g(lambda,lambda,nu)
is strictly positive for every partition nu of n.
The partition lambda can be chosen to depend only on n, not on the
desired constituent nu. The construction that produces lambda is
explicit and is fixed before any particular nu is considered.
Necessary self-conjugacy. The sign representation on S_n forces a
strong structural condition on any covering lambda. Put nu = (1^n),
the sign partition. Then nu itself equals its own conjugate
nu^t = (n), and S^nu is the sign character of S_n. For a general
partition lambda, vanishing of the Kronecker coefficient
g(lambda,lambda,(1^n)) is equivalent to inequality of lambda and its
conjugate lambda^t. In detail, S^lambda tensor sign is isomorphic to
S^{lambda^t}, so
g(lambda,lambda,(1^n))
= dim Hom_{S_n}(S^lambda, S^lambda tensor sign)
= dim Hom_{S_n}(S^lambda, S^{lambda^t}).
Schur's lemma gives the value 1 when lambda = lambda^t and 0
otherwise. Every covering square therefore comes from a
SELF-CONJUGATE partition, one equal to its own transpose.
For a covering square, positivity of g(lambda,lambda,nu) is equivalent
to nonvanishing of the inner product
g(lambda,lambda,nu)
= (1/n!) sum_{rho} chi^lambda(rho)^2 chi^nu(rho) / z_rho,
where chi^lambda(rho) is the character of S^lambda on the conjugacy
class of cycle type rho, and z_rho = prod_j j^{m_j(rho)} m_j(rho)!.
Real-valuedness of symmetric-group characters justifies the square.
This is the form used for the finite character computation of small
degrees, and it also gives every nonvanishing test its meaning.
The related Saxl conjecture. Saxl conjectured in 2012 that, for the
staircase rho_m = (m, m-1, ..., 1) at the triangular degree
N_m = m(m+1)/2, the square S^{rho_m} tensor S^{rho_m} contains every
S^nu for nu of N_m. Only triangular degrees and only the staircase
partition are permitted; all other degrees, and all other candidate
partitions, are excluded.
./ref-1304.0738v2.pdf
Refinements and flanking results. Ikenmeyer proved the staircase case
for every nu dominated by rho_m, using triangular arrangements of
alternating tensors with nonvanishing contractions. Luo and Sellke
showed staircase squares contain almost every nu under both the
uniform and Plancherel measures, and proved full containment for the
fourth power. Harman and Ryba proved the cube version for every
staircase. Modular and spin methods produced further infinite
families: double hooks (Bessenrodt), 2-height-zero types and framed
staircases (Bessenrodt-Bowman-Sutton), triple hooks (Li), semi-
group and generalized-block classes (Ebrahimi), and Catalan-shape
formulas (Brown-van Willigenburg-Zabrocki). An alternating-group
analogue has been proposed by Heide, Saxl, Tiep, and Zalesski. A
dominance-minimality approach has been withdrawn by its author for
mathematical reasons stated at the arxiv version.
./ref-1410.6549v2.pdf
./ref-1511.02387v2.pdf
./ref-2206.13769v2.pdf
./ref-1704.00707v1.pdf
./ref-2202.03066v3.pdf
./ref-1903.07717v3.pdf
./ref-1811.10967v4.pdf
./ref-2511.03484v3.pdf
./ref-1209.1768.pdf
./ref-0809.3469v1.pdf
Why adaptation is delicate. For general n no small staircase in a
larger partition is adequate: attached cells can cancel alternating
terms, and no polynomial identity survives generically. Two sufficient
tests, BAND and BALANCE, avoid this by projecting a single alternating
tensor of a fixed self-conjugate lambda and verifying nonvanishing
contractions. Between them they cover every target, once the candidate
is chosen. Residual intermediate parameters and all small degrees are
settled by two short programs whose soundness is established
abstractly and whose output is recorded. Both programs target only
sufficient conditions; neither claims exactness of any Kronecker
coefficient.
Partitions. Write lambda |- n for a partition of n. Its transpose
lambda^t has i-th part equal to #{j : lambda_j >= i}. A standard Young
tableau is a filling of the Young diagram with 1, ..., n that increases
strictly along rows and down columns. The number f^lambda of standard
tableaux equals dim S^lambda.
./james-1978.pdf
The Specht modules via column alternation. Fix a basis e_1, ..., e_m
of C^m with m at least the number of rows of lambda. For an ordered
block A = (a_1, ..., a_k) of positions, set
v_A = sum_{pi in S_k} sgn(pi) e_{pi(1)} tensor ... tensor e_{pi(k)},
placed at a_1, ..., a_k in the given order. For a set partition
A = {A_1, ..., A_k} of {1, ..., n}, put v_A = v_{A_1} tensor ... tensor
v_{A_k}. If |A_i| equals the i-th column height of theta, then
C[S_n] v_A is isomorphic to S^theta as S_n-modules. Changing the order
of blocks changes only the overall sign. Two tensors related this way
generate the same submodule, so the construction is robust to
reordering.
Character formula. For partitions lambda, mu, nu of n,
g(lambda,mu,nu)
= (1/n!) sum_{rho} chi^lambda(rho) chi^mu(rho) chi^nu(rho)
/ z_rho,
where chi^alpha(rho) is the character of S^alpha on the conjugacy class
of cycle type rho, and z_rho = prod_j j^{m_j(rho)} m_j(rho)!. Symmetric
group characters are real, hence positivity of g(lambda,lambda,nu) is
exactly positivity of the sum without absolute values. This identity
underpins every nonvanishing test.
Littlewood-Richardson rule. For partitions alpha, beta, gamma of
sizes a, b, a+b, the coefficient c^gamma_{alpha,beta} counts
Littlewood-Richardson skew tableaux of shape gamma/alpha with content
beta. Two consequences appear repeatedly:
(Pieri) c^gamma_{alpha,(t)} > 0 iff gamma/alpha is a horizontal
strip of size t, and c^gamma_{alpha,(1^t)} > 0 iff gamma/alpha is
a vertical strip of size t.
(Rectangle complement) if alpha and beta are complementary shapes
inside a rectangle gamma = (w^j), then c^gamma_{alpha,beta} = 1.
The induction form: for a finite list A = (a_1, ..., a_k) of sum n,
and a partition nu |- n, the multiplicity of S^nu in
Ind^{S_n}_{S_{a_1} x ... x S_{a_k}} (1 (...) 1) is
sum_{alpha_1, ..., alpha_k} prod_i c^{beta_i}_{alpha_i, (a_i)},
taken over chains nu = beta_1 >= beta_2 >= ... >= beta_{k+1} = empty
in which beta_i/beta_{i+1} is a horizontal strip of size a_i. The
partition obtained by sorting A into nonincreasing order contributes
multiplicity one.
./ref-math_9704228v1.pdf
./james-1978.pdf
Macdonald (Symmetric Functions and Hall Polynomials, Chapter I
Sections 5 and 9) and Fulton and Harris (Representation Theory: A
First Course, Chapters 4 and 6) give the classical foundations for
the LR rule, Pieri's formula, and the symmetric-group character
theory used throughout. Zelevinsky (Littlewood-Richardson semigroups)
develops the multiplicative structure of LR coefficients. The
specific even-row decomposition of Sym^m(Sym^2 E) used in the
balance construction is Macdonald Chapter I Section 5 Example 5(a).
Young support lemma. For a finite list A = (a_1, ..., a_k) of
positive integers of sum n, the module
Ind^{S_n}_{S_{a_1} x ... x S_{a_k}} 1
contains S^nu precisely when the column heights h_1 >= h_2 >= ... of nu
satisfy
sum_{j=1}^m h_j <= P_A(m) := sum_{a in A} min(m, a), m = 1, 2, ...
This is Young's rule applied to Ind of a trivial representation from
a Young subgroup, expressed in column form. Equivalent formulation: nu
dominates (A sorted nonincreasingly) in the dominance order on
partitions of n.
Dual-polytabloid test. Fix a tensor space (C^m)^{tensor n} with m
ordered alphabets e_1, ..., e_m. Let theta |- n have at most m rows.
Then S^theta appears in C[S_n] z for a tensor z if and only if z has a
nonzero contraction with a dual tableau whose columns are the column
blocks of theta, for some placement of these columns and some ordered
basis of (C^m)^*. Quantifier order: some placement, some basis. The
support condition is therefore an existential statement in finite-
dimensional linear algebra and admits no cancellation, only
vanishing. Ikenmeyer's triangular arrangements (Section 3 of that paper) use this form directly.
./ref-1410.6549v2.pdf
The candidate partition. Let n be outside {2, 4, 9}. Choose
M = M(n) to be the largest integer with N_M = M(M+1)/2 <= n and
N_M congruent to n mod 2; set r = (n - N_M)/2. For n >= 45 with n odd,
or n >= 66 with n even, M >= 9. Set b = floor(r/2), s = 1 + (r mod 2),
and K = 2M - 1. Maximality of M constrains r through the parity
period of N_M = M(M+1)/2 modulo 2, which cycles odd, odd, even,
even. If M is congruent to 1 or 3 mod 4, then r <= (M-1)/2; if M
is congruent to 0 or 2 mod 4, then r <= 3M/2 + 2. In particular,
r < 2M+5 always. Define the partition L |- n by its row lengths, and,
by self-conjugacy, its column lengths, both equal to
(M+b+s-1, M+b-1, M-2, M-3, ..., 3, 2^{b+1}, 1^s),
where 2^{b+1} denotes b+1 columns of length two and 1^s denotes s
columns of length one. Direct counting of cells verifies L = L^t.
Two structural features are used repeatedly. The BIG PAIR is the pair
of columns of heights M+b+s-1 and M+b-1; their total size is
2M + 2b + s - 2 = 2M + r - 1 = K + r = T. The STAIRCASE D consists of
the cells (i,j) of L with i, j >= 1 and i + j <= M - 1; as a partition
D is the staircase rho_{M-2} = (M-2, M-3, ..., 2, 1). The BAND is the
complement F = L \ D, of size K + 2r.
The cyclic staircase theorem. For an integer m >= 1 let rho_m =
(m, m-1, ..., 1) and B_m = {(i,j) : i, j >= 1, i + j <= m + 1}.
Let R_m and C_m be the row and column set partitions of B_m, ordered
by increasing j within each row and by increasing i within each
column. Use the ordered alphabet e_1, ..., e_m in both tensor factors
and set
w_m = v_{R_m} tensor v_{C_m} in S^{rho_m} tensor S^{rho_m},
W_m = C[S_{B_m}] w_m,
with the diagonal action of S_{B_m}.
CSA THEOREM. For every integer m >= 1 and every partition
alpha |- N_m, S^alpha occurs in W_m.
The row-column generator w_m is special. A generic vector of the
ambient square S^{rho_m} tensor S^{rho_m} contains every irreducible as
a direct summand of the ambient module, but not in the cyclic span of
that single vector. The tensor w_m, built from the ordered row and
column alternations at their natural interleaving, is a specific
vector whose orbit already contains every constituent.
./ref-1410.6549v2.pdf
cyclic_polytabloid_saxl_v2.txt
Ikenmeyer's triangular constructions supply one specific family of
contractions for partitions near the staircase, and the complete proof
of CSA, via successive consecutive-column contractions and generic
choice of basis, appears in the cyclic-polytabloid preprint. Common
relabelings of the two ordered alphabets and changes of block order
preserve the conclusion up to an overall sign. The whole square
S^L tensor S^L contains S^nu for every nu once the two sufficient
tests exhibit S^nu in the cyclic span of a specific tensor of
S^L tensor S^L.
The band criterion. Let lambda |- n = |L| have column heights
h_1 >= h_2 >= ... and row lengths w_1 >= w_2 >= ..., with zeros
appended. Suppose integers d, q satisfy
1 <= d <= 4, 0 <= q <= 8,
sum_{i=1}^{d} w_i >= K,
d q + 7 + d <= K,
sum_{i=1}^{q} max(0, floor((h_i-d)/2)) >= r.
Then S^lambda occurs in S^L tensor S^L.
The three inequalities have separate jobs. The first reserves
enough row length at the top of the target for a path of length
K. The second confines the path away from the two ends of the
staircase so attachments cannot cancel against endpoint
alternations. The third provides q even pieces of total capacity
2r that feed the two extra attachments.
Reduction to F. Regard L as its set B of cells. Let v_R, v_C be
the alternating block tensors for its rows and columns, and put
W_L = C[S_B](v_R tensor v_C), a submodule of S^L tensor S^L
by self-conjugacy of L. Put
D = {(i,j) : i, j >= 1, i + j <= M - 1}, F = B \ D.
D is the staircase rho_{M-2} of size N_{M-2}; F has size K + 2r.
LEMMA (Triangle quotient). There is an S_B-equivariant quotient
W_L -> Ind^{S_B}_{S_D x S_F} (W_{M-2} boxtimes U_F),
where W_{M-2} is the cyclic module of CSA and U_F is generated
by the row and column block alternations on F, with the initial
alphabet on every remaining block.
The proof is a single projection. Set ell = M + b + s - 1, the
largest row and column length of L. In both alphabets mark
{3, 4, ..., M-1} union {M+b},
comprising M-2 letters. For each i the initial alphabet of row
or column i contains
t_i = max(M-1-i, 0)
marked letters, exactly the number of D-cells in that row or
column. Project the pair-letter tensor onto words whose two
letters at every position share marking status. The projected
space is a direct sum T = oplus_{A subset B, |A| = |D|} T_A, with
g T_A = T_{g A}. The row-column generator v_R tensor v_C lies in
T_D and its projection is, up to overall sign, w_{M-2} tensor u_F.
LEMMA (Sector induction). Let G act transitively on a finite
set Omega, let T = oplus_{A in Omega} T_A with g T_A = T_{g A},
fix D in Omega with stabilizer H, and let z in T_D. The map
Ind^{G}_{H}(C[H] z) -> C[G] z is an isomorphism of G-modules.
Sector induction turns the projected module into the Ind of the
two local modules, proving the triangle quotient. The proposition
therefore reduces to: for every target lambda satisfying the
three inequalities, exhibit a subpartition mu subseteq lambda of
size |F| with S^mu in U_F. Young branching then puts S^mu in
Res_{S_F} S^lambda, Frobenius reciprocity gives c^lambda_{alpha,mu}
> 0 for some alpha |- |D|, and CSA gives S^alpha in W_{M-2} for
every such alpha.
cyclic_polytabloid_saxl_v2.txt
Odd-path support. For an odd integer k = 2t+1, put alternating pairs
in the first tensor layer at positions (2,3), (4,5), ..., (k-1,k),
with the singleton letter 1 at position 1. In the second layer put
alternating pairs at positions (1,2), (3,4), ..., (k-2,k-1), with the
singleton letter 1 at position k. Denote the resulting pair-letter
tensor by u_k in (C^4)^{tensor k}, viewed as (Mat_2(C))^{tensor k}.
LEMMA (Odd-path support). The cyclic S_k-span of u_k contains
every S^alpha for alpha |- k with at most four rows. Moreover,
for any finite family of ordered lists a_1, ..., a_c with
1 <= a_i <= 4 and sum a_i = k, and any simultaneous placement of
their dual polytabloid columns along positions 1..k, a single
ordered basis of Mat_2(C) can be chosen so that all contractions
with u_k are nonzero at once.
Proof of the first statement. Use the ordered basis
M_1 = I, M_2 = Z = diag(1,-1),
M_3 = T = offdiag(1,1), M_4 = J = Z T.
The last three are traceless, invertible, and pairwise anticommuting.
Adjugation fixes I and negates the other three. For a segment of
length a <= 4 starting at global position p, put D_j(Y) = Y for odd
j and D_j(Y) = adj(Y) for even j, and define the alternated block
matrix
A_{a,p} = sum_{pi in S_a} sgn(pi) D_p(M_{pi(1)}) ... D_{p+a-1}(M_{pi(a)}).
Let e be the number of even positions in this segment and epsilon its
left endpoint parity. Then
A_{a,p} = a! (-1)^{e - epsilon} M_1 ... M_a.
Indeed, if I occupies the local slot j, its displacement contributes
(-1)^{j-1} to the sign, and reordering the remaining three matrices
reproduces the permutation sign by anticommutation. The adjugations
contribute (-1)^{e - epsilon_j}, and epsilon_j = epsilon + j - 1 mod 2,
so the total sign is (-1)^{e - epsilon} independently of pi. Every
right hand side is invertible.
Contracting the tensor u_k with the dual polytabloid of a partition
alpha inside 4 rows now reads off as (-1)^t [B]_{11}, where B is the
ordered product of the invertible matrices A_{a_i, p_i}. Choose an
eigenvector of B with nonzero eigenvalue beta and a matrix Q in
GL_2(C) sending it to the first coordinate vector. Replacing every
M_i by Q M_i Q^{-1} preserves the anticommutation relations and the
adjugation identities, and yields a basis in which the contraction
equals (-1)^t beta != 0. The second assertion follows by iterating
over the finite list of placements: the nonvanishing locus of each
contraction is a nonzero polynomial in the entries of the common
basis, and GL_4(C) is irreducible, so the intersection of the finitely
many nonempty Zariski-open loci is nonempty. The dual-polytabloid
test then gives S^alpha in the cyclic span of u_k for every such
alpha.
./ref-1410.6549v2.pdf
The two attachments. The band F carries, along with the K-position
path, two extra column blocks at either end. Each block has row
counts of shape E = (b+delta, b) with delta in {0,1}. The odd
path lemma controls the path; the attachment lemmas control the
extras.
LEMMA (One extra copy). Let E = (b+delta, b) with b >= 0 and
delta in {0,1}. Let Z_E be the cyclic span of the row-column
alternating generator of E on its two alphabets. Then the sign
twist Z_E tensor sgn contains S^alpha for every partition
alpha |- 2b+delta with at most four rows, all even row lengths
when delta = 0, and exactly one odd row length when delta = 1.
Proof. Suppose b >= 1; boundary cases b = 0 are immediate. Let v
be the long-row alternating vector and p the short-column
alternating vector of E; they generate S^{E^t} and S^E. Let H act
by permuting positions within each short column. Signed averaging
of the tensor product gives
sum_{h in H} sgn(h) h(v tensor p) = v_0 tensor p,
where v_0 = sum_{h in H} h v is nonzero because the word placing
letter j in short column j is H-fixed with coefficient one.
Regrouping the product by positions, each short column repetition
becomes
H_0 = e_11 tensor e_22 + e_22 tensor e_11
- e_12 tensor e_21 - e_21 tensor e_12,
a nondegenerate symmetric form on the four-dimensional span of
{e_ac = e_a tensor e_c}. If delta = 1, an extra singleton e_11
remains.
For alpha |- 2b with even row lengths, pair adjacent columns of
its dual tableau; the paired columns have equal height. Place the
b copies of H_0 in the corresponding row pairs, contract against
the paired dual columns: the result is a product of factorials
times a common sign, hence nonzero. Lemma (Dual-polytabloid test)
then proves the containment. For delta = 1, isolate the odd-
height column; it contributes a single factor 1, and the rest is
paired by matching equal column heights.
LEMMA (Two extras). Let E_+ and E_- denote the two attachment
blocks, satisfying |E_+| + |E_-| = 2r, and let z_+ and z_-
denote their row-column alternating generators. Then the
cyclic span of z_+ tensor z_- contains S^{theta_+} tensor
S^{theta_-} for every pair (theta_+, theta_-) of partitions
with at most four rows, each having the parity required by its
copy, and with |theta_+| = |theta_-| = r when r is even, or
|theta_+| = r+1, |theta_-| = r-1 when r is odd.
Proof. Apply the one-extra lemma separately to Z_{E_+} with the
sign twist and to Z_{E_-} without. Use sector induction to
combine the two attachments into a single cyclic pair-letter
tensor. Each attachment has an independent ordered basis of
pair-letters; the two bases concatenate as a common ordered basis,
and every contraction with a dual polytabloid of shape theta_+
tensor theta_- is nonzero.
./ref-1410.6549v2.pdf
Attaching without cancellation. Fix a target lambda satisfying
the three inequalities of the band criterion. The proof exhibits
a specific subdiagram mu subseteq lambda of size |F| and computes
its dual-polytabloid contraction with U_F. Let
e_1 >= ... >= e_t > 0 be the even list with t <= q,
sum_{i=1}^t e_i = 2r, e_i <= h_i - d, produced by the greedy
rule on max(0, floor((h_i - d)/2)). The third band inequality
guarantees such a list exists.
LEMMA (Band subdiagram). There is a subdiagram mu subseteq lambda
of size |F|, together with a placement of its dual polytabloid
columns on positions 1..K of the path and on the attachment
positions, such that the dual-polytabloid contraction with U_F
is nonzero.
Proof. Set mu's column heights to
mu_i = h_i - e_i (1 <= i <= t),
mu_i = h_i - f_i (t < i <= d + q),
mu_i = 0 (i > d + q),
where the integers f_i >= 0 are chosen by the greedy rule so that
sum_{i=t+1}^{d+q} f_i = N_{M-2} - 2r, making |mu| = |F|. All f_i
are bounded by h_i and by the excess of lambda over the staircase
skeleton, so mu subseteq lambda. The path portion of mu is the
specific subdiagram of rows and columns indexed 1..K with column
heights mu_i for i <= d + q and zeros thereafter; the extra
portion is the diagram eta with columns e_1, ..., e_t.
Now place the dual tableau columns of mu along the flag
N_1, ..., N_d, Q_1, ..., Q_dimX, N_{d+1}, ..., N_4.
For every nonempty path column take its first d positions from
N_1, ..., N_d, its next a_i positions (down to the column height of
mu) from Q_1, ..., Q_{a_i}, and its last min(4-d, remaining) from
N_{d+1}, ..., N_4. The path portion contributes the alternating
contraction (nonzero by the odd-path lemma); each extra column
contributes the corresponding contraction (nonzero by the
two-extras lemma); the two contributions are multiplied because
the flag is arranged as N-prefix, Q-middle, N-suffix with no
overlap. The endpoint inequality d q + 7 + d <= K ensures the
disjoint support of the three flag regions. So the full contraction
is nonzero and by Lemma (Dual-polytabloid test) S^mu occurs in U_F.
Closing the band criterion. With S^mu in U_F for the mu constructed
the triangle quotient of L gives S^lambda in
Ind^{S_B}_{S_D x S_F}(W_{M-2} boxtimes S^mu). This is contained in
S^L tensor S^L, and the target lambda is arbitrary among partitions
of n satisfying the three inequalities. The band criterion follows.
./ref-1410.6549v2.pdf
The balance criterion. The second sufficient test uses the full
square S^L tensor S^L, with both factors realized by column-
alternating tensors on the SAME column blocks. Each column of
length k is projected onto words whose pair-letter sum a + a' - 1
equals k. The projection commutes with all position permutations.
Two columns with disjoint output ranges can be combined as a
tensor product, and then induced via Young's rule. This is slower
than the band criterion (its local supports involve whole column
blocks) but it addresses targets the band test misses.
Notation. For integers t >= 0 and j >= 1,
H_j(t) = {nu |- t : number of rows of nu <= j};
E_j(t) = {nu in H_j(t) : every row length of nu is even};
O_4(t) = {nu in H_4(t) : the transpose nu^t has at least one
odd-height column}.
For positive c and s in {1, 2}, let P_3(c, s) denote the set of
partitions of c + s + 3 with at most three rows obtained from a
member of E_3(c) by successively adding a horizontal strip of
size 3 and then of size s. All support statements are
inclusions of S_n-modules with no assertion about multiplicities.
Local table. Each type of column block of L, projected to a
specific output interval, supplies one of these local supports:
(i) a copies of length k, output {k} -> (ak) (trivial);
(ii) a neighboring pair u, u-1 (total 2u-1), outputs
[u-1, u] -> H_4(2u-1);
(iii) a wedge q+2, q (total 2q+2), outputs [q, 2q+3]
-> O_4(2q+2);
(iv) b+1 copies of length two (total c = 2b+2), outputs {2}
-> E_2(c);
(v) the length-three block together with the b+1 copies of
length two and s singletons (total c+3+s), outputs
[1, 3] -> P_3(c, s).
./ref-2202.03066v3.pdf
Entries (i), (iv), (v) are proved by the symmetric-pair lemma and
the symmetric-pair and three-row lemmas. Entries (ii) and (iii) follow from the
odd-path and short-form calculations applied to the columns of L
themselves, together with Pieri fillings.
Separation by size and sum. Partition the column blocks of L
into disjoint sub-collections B_1, ..., B_v on disjoint position
sets D_1, ..., D_v, used identically in both tensor factors. Let
d_{B_i} = |B_i| be the block size. Suppose I_1, ..., I_v are
nonempty intervals of integers with every element of I_i strictly
below every element of I_{i+1}. Let W_i be the image of the
alternating block tensor Y_{B_i} tensor Y_{B_i} under the
coordinate projection retaining words all of whose outputs lie in
I_i.
LEMMA (Separation). The support of S^L tensor S^L contains
the support of
Ind^{S_n}_{S_{d_B1} x ... x S_{d_Bv}}
(W_1 boxtimes ... boxtimes W_v).
Proof. Retain from the full pair-word space the words whose
outputs lie in U_i I_i and for which the outputs in I_i have
cardinality d_{B_i} and sum sigma_{B_i}, simultaneously in i.
This projection commutes with all position permutations. After
projecting, the tensor splits as a product over i of the
corresponding local projected tensors, because the position sets
D_i are disjoint and the output ranges I_i are disjoint. Summing
over all re-orderings of the factors produces the induced module.
Symmetric pairs. The length-two columns of L pair up to give a
nondegenerate symmetric form on the two-letter space.
LEMMA (Symmetric pairs). Let m >= 0, let E have dimension j,
let H in Sym^2 E be nondegenerate. The position-permutation
span of H^{tensor m} in E^{tensor 2m} contains every member of
E_j(2m). Moreover, the polynomial GL(E)-module Sym^m(Sym^2 E)
contains the Schur module of each such partition.
Proof. Choose an orthonormal basis of E for H, so
H = sum_{i=1}^j e_i tensor e_i. A diagram with even row
lengths has its columns paired into equal-height pairs. Place
the two positions of each copy of H in corresponding cells of
two paired columns. Contract against the usual column-
alternating dual tensor. For a pair of columns of height h,
the two permutations must agree, their signs multiply to one,
and the contribution is h!; the whole contraction is thus the
product of these factorials, nonzero. Lemma (Dual-polytabloid
test) proves the first statement.
For the second, use the natural embedding of Sym^m(Sym^2 E)
into E^{tensor 2m} with the m pairs of positions fixed, and
choose the dual tableau placements by matching paired columns. The same
contraction proves that this GL(E)-stable subspace has a
nonzero projection to the indicated Schur-Weyl isotypic space.
Complete reducibility then gives the required Schur module.
./ref-2202.03066v3.pdf
The three-row assembly. The short columns of L include one
block of length three, b+1 copies of length two, and s copies of
length one; their total size is c + 3 + s.
LEMMA (Three-row assembly). The cyclic span of the assembled
tensor z_3 tensor H^{tensor(b+1)} tensor (e_11)^{tensor s},
projected to outputs in [1,3], contains S^nu for every nu in
P_3(c, s). In particular for s = 1, the length-three block
gives a horizontal strip of size three over E_3(c), and for
s = 2 the two singletons give a horizontal strip of size two.
Proof sketch. The length-three block projects to a symmetric
triple: the alternating sum over S_3 tensored against a
two-letter space gives an element of Sym^3(C^2) tensor ...,
a symmetric three-fold tensor. Combined with the b+1 copies
of H (quadratic forms) and the s singletons (linear terms),
the assembled tensor is a polynomial in three generically
chosen data:
Q in Sym^2(E) (a quadratic form), x, y in E (vectors).
Varying Q, x, y densely fills the GL(E)-invariant space
Sym^{b+1}(Sym^2 E) tensor Sym^s E tensor Sym^3 E,
because a linear functional annihilating the span
yields a multihomogeneous polynomial in (Q,x,y) that vanishes
on a dense open set and hence identically. The first factor
supplies every type in E_3(c) by the symmetric-pair lemma;
the Sym^s E factor supplies a horizontal strip of size s by
Pieri; and the Sym^3 E factor supplies a horizontal strip of
size 3 by Pieri. Two Pieri applications therefore produce
every type in P_3(c, s). Schur-Weyl duality transfers these
GL(E)-types back to the corresponding S_D-types in the local
projected module.
./ref-2202.03066v3.pdf
LEMMA (Two-path component). For every integer q >= 0, the
column pair of heights q+2 and q, projected to outputs in
[q, 2q+3], contains O_4(2q+2). If q >= 3, inducing this
support with a trivial representation of size two contains
H_4(2q+4).
Proof. In each tensor layer, mark pair labels 1, ..., q and
singletons q+1 and q+2. For 0 <= p <= q, form odd paths of
sizes 2p+1 and 2(q-p)+1. On the first path, use first-layer
pair labels 1, ..., p and second-layer pair labels
q-p+1, ..., q; on the second path use the complementary
intervals in each layer. Give the first path the initial
first-layer singleton q+1 and the terminal second-layer
singleton q+2, and the second path the remaining singletons.
Internal outputs are q or q+1; endpoint outputs are at least
q; all outputs are at most 2q+3. Each pair word therefore
survives the projection. The odd-path support lemma supplies
nonzero contractions on both paths; the paths use disjoint
position sets, so their product is a nonzero polynomial in a
common ordered basis. A common generic basis makes the
contraction nonzero, giving O_4(2q+2).
For the second claim, let eta in H_4(2q+4) with q >= 3. Remove
a horizontal two-strip so that the result has at least one
odd-height column. If eta has no odd-height column, any
horizontal two-strip removal creates two. If eta has at least
four odd-height columns, such a strip cannot remove all of
them. If eta has exactly two odd-height columns, its width
ensures an even-height column also exists; remove one cell
from an odd-height and one from an even-height column,
choosing the rightmost of each selected height, so heights are
preserved weakly decreasing. This is a horizontal two-strip
removal. The two-path support then contains a transition
compatible with the removed strip via the Sep and Pieri local
table entries.
./ref-1410.6549v2.pdf
The balance bound. Assume M >= 9 and let h_1 >= h_2 >= ... be
column heights of a target nu |- n. If
sum_{i=1}^4 h_i <= 2M - 2,
then S^nu occurs in S^L tensor S^L. The same conclusion holds if
the four-small condition is met for the column heights of nu^t.
Proof. Decompose L into local blocks (the big pair; the length-two
columns; the length-three block; the middle lengths 3, ..., M-2;
the singletons) so that each block's support from the local table
applies. The output ranges are disjoint:
singletons: output 1;
length-two and length-three: outputs 2 and 3;
adjacent middle pair (u, u-1): outputs u-1 and u;
big pair: outputs M-1 or above.
The separation lemma makes these into independent induced pieces;
reassociation combines the big pair with the singleton strip (when
s = 2) and the length-two and length-three blocks with each other
(when c > M). This produces a multiset A of trivial-factor sizes
of total n.
Two uniform bounds on A:
|A| >= 2M - 5, and max A <= M + 1.
When c <= M there are p = M - 4 middle lengths; a run of p
consecutive pairs contributes 2p - (p mod 2) >= 2p - 1 parts;
with at least five other parts this gives 2M - 5. When c > M, the
length-three block with the twos contributes two balanced parts
of total c+3; then p = M - 5 is odd and the run contributes
2M - 11, plus at least six more from the big and short parts,
so |A| >= 2M - 5. The largest middle or short part is at most M.
The largest big-component part is at most ceil((T+2)/4) <=
ceil((7M/2+3)/4) <= M + 1, using r <= 3M/2+2. Hence
n / max A >= N_M / (M+1) = M/2 > (2M - 2)/4.
Verify the Young support lemma. Target has at least four columns
(otherwise four-small gives n <= 2M - 2 < N_M), so h_1 <= 2M - 5
and P_A(1) = |A| >= 2M - 5 >= h_1. The four big-component parts
are each at least two, so P_A(2) >= |A| + 4 >= 2M - 1, and
P_A(3) is the same. For k >= 4, decreasing heights and four-small
give sum_{i=1}^k h_i <= min(n, k(2M-2)/4). With B = max A, the
inequality min(k, a) >= ka/B for k <= B gives
P_A(k) >= min(n, kn/B). Since n/B >= M/2 > (2M-2)/4, dominance
holds for every k. Young's rule gives S^nu in the induced trivial
module, hence in S^L tensor S^L. The sign twist from self-
conjugacy of L handles transposed targets.
Capacity exhaustion. With the band and balance criteria
established, it remains to show that they cover every target at
every degree. Three regimes are distinguished by M.
Large M. Take d = 4 and q = 8, which satisfy 0 <= q <= 8 and
4q + 7 + d = 43 <= K = 2M - 1 for M >= 22. If the balance bound
already handles the target (h_1 + h_2 + h_3 + h_4 <= 2M - 2, or
the same for nu^t), then containment is direct. Otherwise
H_4 >= 2M - 1 and W_4 >= 2M - 1.
If the band test failed in both orientations,
sum_{i=1}^8 max(0, floor((h_i - 4)/2)) <= r - 1,
and likewise for w. The termwise inequality
x <= 2 max(0, floor((x - 4)/2)) + 5 (x >= 0)
then gives H_8, W_8 <= S := 2r + 38. The following bound converts
this into a contradiction.
LEMMA (Rectangle bound). Let i, j >= 1 and suppose H_i <= U
and W_j <= V. Then
n <= max(U + V - 1, floor(U V / (i j))).
Proof. If the cell at row j and column i is absent, every cell
lies in the first i columns or the first j rows (these two strips
cover the diagram and share only the corner cell), so
n <= U + V - 1. Otherwise the intersection is an i-by-j
rectangle. Put x = h_i >= j and y = w_j >= i. Every cell outside
both strips lies in the x-by-y corner, and that corner is missing
the i-by-j intersection plus the two strips within it, giving at
most (x - j)(y - i) = (U/i - j)(V/j - i) = UV/(ij) - U - V + ij
remaining cells outside. Therefore (i j) n <= UV. Combined with
the first case, n <= max(U + V - 1, floor(UV/(ij))).
Applying the rectangle bound to H_8, W_8 <= S with i = j = 8 gives
n <= max(2S - 1, S^2/64). On the other hand N_M + 2r = n with
N_M = M(M+1)/2, and r <= 3M/2 + 2 by maximality of M, so
n - 2S + 1 >= (M^2 - 5M - 158)/2 > 0,
64 n - S^2 >= 23 M^2 - 28 M - 1508 > 0,
both positive at M = 22 and increasing thereafter. Contradiction.
The band criterion therefore succeeds for at least one orientation
of every target at M >= 22.
Intermediate M. For 9 <= M <= 21, let d be the least integer
with H_d >= K and e the least with W_e >= K, both in {1, 2, 3, 4}.
Set
q_f = min(8, floor((2M - 8 - f) / f)) (1 <= f <= 4)
and the finite set of prefix bounds
E_{M,r}(d, e) = {(d - 1, 2M - 2) : d > 1}
union {(q_f, 2r - 2 + q_f (f + 1)) :
e <= f <= 4, q_f > 0}.
If neither band test succeeds for the two orientations, every pair
(i, U) in E_{M,r}(d, e) satisfies H_i <= U, and the transposed
set bounds row prefixes. The termwise inequality
x <= 2 max(0, floor((x - f)/2)) + f + 1 (x >= 0)
combined with the rectangle bound gives a contradiction for
every target outside the finite set
{(10, 8), ..., (10, 17)} union {(12, 14), ..., (12, 20)}
union {(14, 22), (14, 23)}.
Exceptions. Each of the nineteen residual pairs is settled by a
recursive enumeration gen. The algorithm allocates integers
delta_i with 0 <= delta_i <= min(4, h_i) and sum_i delta_i = T =
K + r (with at least one odd delta_i when s = 2), tests the
residual diagram (column heights h_i - delta_i) against the lower-
component supports via the packing scheme of the balance bound,
and recurses. A successful allocation certifies the target by
Young's rule support closure; the recursion enumerates every
target up to the pruning implied by the local supports.
The arithmetic is exact; the tests certify sufficient conditions
rather than approximate Kronecker coefficients.
Small degrees. For degrees n <= 64 the capacity arguments do not
directly apply (M can fall below 9), but a finite character
calculation settles every such n directly.
PROPOSITION (Finite check). For every integer 1 <= n <= 64
other than 2, 4, 9, there is a self-conjugate partition
lambda of n with g(lambda, lambda, nu) > 0 for every nu |- n.
Proof. Write chi^lambda(rho) for the character of S^lambda on
the conjugacy class of cycle type rho. The character inner-
product formula gives
g(lambda, lambda, nu)
= sum_{rho |- n} chi^lambda(rho)^2 chi^nu(rho) / z_rho,
where z_rho = prod_j j^{m_j(rho)} m_j(rho)! and
m_j(rho) = number of parts of rho of size j. Symmetric-group
characters are real, so the square is legitimate.
Invariant vector. In a call calc(s, k, e, v), s is the
remaining cycle type size, k the current bound on part sizes,
e the count of size-k parts already selected. Reached states
have 0 <= s <= 64, k >= 1, e >= 0. Set rho_1 = 0 for the empty
partition and m_j = m_j(rho). Define
F_{s,k,e}(v)_nu
= sum_{rho |- s, rho_1 <= k}
chi_v(rho)^2 chi^nu(rho)
e! / (k^{m_k} (e+m_k)!)
prod_{1<=j<k} 1 / (j^{m_j} m_j!).
Only states with e+m_k <= 64 are reached, so all denominators
are invertible. For 2 <= k <= s, separating m_k = 0 from
m_k > 0 gives
F_{s,k,e}(v) = F_{s,k-1,0}(v)
+ (1/(k(e+1))) R_k F_{s-k,k,e+1}(R_k^T v),
where R_k is the operator that multiplies the nu-coordinate by
chi^nu(rho') for a single new part of size k added to rho.
When m_k = 0, the counter resets. Each call decreases (s, k)
lexicographically. Base cases: F_{0,k,e}(v) = v_empty^2;
F_{s,s,0}(v) is used when s < k (since no size-k part remains);
and F_{s,1,0}(v) = (1/s!) d_s (d_s^T v)^2 for the dimension
vector d_s of S_s irreducibles (computed via Young-lattice
chains on the empty partition).
Bit encoding. Let B_lambda = {64 + lambda_j - j : 1 <= j <= 64}
subset {0, ..., 127} be the beta set of lambda. Moving one bead
from x to an empty position x+k adds a border strip of size k;
the number of beads passed along the way gives its leg length,
and the sign is (-1)^leg. With b the bit mask of B_lambda,
b & ((~b) >> k) selects the permitted starting positions. With
m = 2^x and t = 2^{x+k}, the mask (t - 2m) contains precisely
the bits strictly between x and x+k, so cnt(((t - 2m) & b))
gives the strip leg length. The routine op implements R_k or
R_k^T according to its direction argument. All operations are
exact 128-bit integer; the program treats modular arithmetic
with an explicit prime, then confirms output again without
reduction.
Execution. The computation for n = 1, ..., 64 other than
2, 4, 9 was performed with GNU C++ 13.3.0. All 61 invocations
returned successfully, and the run record stores the exit
statuses rather than the selected partitions. The successful
returns witness the required existence statement in every
eligible degree of the finite range.
./james-1978.pdf
Proof of the main theorem.
Let M = M(n) be the largest integer with N_M = M(M+1)/2
<= n and N_M congruent to n mod 2. If M < 9, then n <= 64 and
the finite-check proposition supplies a covering square.
Otherwise L = L(n) is the candidate partition. If r = 0, L is
the staircase rho_M, and CSA supplies every constituent of
S^{rho_M} tensor S^{rho_M} directly. If r > 0 fix any nu |- n.
The capacity exhaustion guarantees one of: balance condition
h_1 + h_2 + h_3 + h_4 <= 2M - 2 holds for nu or its transpose,
in which case the balance bound gives containment; or a band
test succeeds in one orientation, in which case the band
criterion supplies containment. Either way S^nu occurs in
S^L tensor S^L. Since L depends only on n, one square covers
every nu |- n.
./ref-1304.0738v2.pdf
cyclic_polytabloid_saxl_v2.txt
Unipotent tensor squares. The construction carries over to
unipotent characters of the finite general linear groups.
COROLLARY. For every n not in {2, 4, 9}, choose one self-
conjugate partition lambda_n supplied by the main theorem. For
every prime power q, let U_q^lambda denote the unipotent
complex character of GL_n(F_q) indexed by lambda. Then
U_q^{lambda_n} tensor U_q^{lambda_n} contains U_q^{nu} for
every nu |- n.
Proof. Letellier proved that the unipotent Kronecker
coefficient of GL_n(F_q) is nonnegative and, as q -> 1, reduces
to the ordinary Kronecker coefficient with a constant-term
bound. Combined with g(lambda_n, lambda_n, nu) > 0 from the
main theorem, the unipotent coefficient is strictly positive
in every prime power q.
./ref-2312.09157v3.pdf
Remark on the excluded degrees. Direct computation for n <= 64
finds a covering square precisely when n is not in {2, 4, 9}. At
n = 2 the only self-conjugate candidates are (2) and (1,1), and
neither squares to contain both irreducibles. At n = 4 similar
direct computation eliminates every self-conjugate candidate. At
n = 9 the self-conjugate partitions also fail to cover every
irreducible. These are the only exclusions in the finite range;
the argument for larger n treats the exception set as fixed.