Universal Tensor Squares for Symmetric Groups

1 Introduction

For a partition \lambda\vdash n, write S^\lambda for the corresponding irreducible complex representation of the symmetric group S_n. Its Kronecker coefficients are

where the tensor product carries the diagonal action. We prove the following statement.

The partition \lambda is fixed for each degree: it does not vary with the desired constituent \nu. In particular the trivial and sign representations both occur. The latter forces \lambda to be self-conjugate, since

Our construction meets this necessary condition throughout.

The Steinberg character already gives this unipotent coverage in every degree [11, Proposition 33], and staircase labels give it at triangular degrees [12, Theorem 1.1]. The corollary identifies further covering squares using the same labels that solve the symmetric-group problem.

1.1 History and significance

Pak, Panova, and Vallejo formulate the assertion for n\ge3, with n\ne4,9, as the tensor square conjecture for symmetric groups [17, Conjecture 1.1]. The case n=1 is immediate. Hence Theorem 1.1 resolves that conjecture affirmatively, including every nontriangular degree.

The related Saxl conjecture specifies the staircase partition \rho_m=(m,m-1,\ldots,1) at the triangular degree N_m=m(m+1)/2; see [17, Conjecture 1.2]. Saxl proposed it at the UCLA Combinatorics Seminar on 20 March 2012, as recorded in [17, Footnote 2]. It is a more specific assertion about a distinguished family, but only at triangular degrees. Earlier work established substantial support families: Pak, Panova, and Vallejo gave a character-nonvanishing test for constituents of self-conjugate squares [17, Lemma 1.3], while Ikenmeyer proved the staircase assertion for partitions comparable with the staircase in dominance order [9, Theorem 2.1]. His triangular arrangement of alternating tensors and nonzero contractions [9, Sections 3–5] is a methodological predecessor of the cyclic construction used here. Heide, Saxl, Tiep, and Zalesski conjectured the analogous tensor-square covering property for alternating simple groups [8, Remark 1.3(3)], partly motivated by Thompson’s conjugacy-class-square conjecture for finite simple groups.

Several complementary approaches explain the strength of the square problem. Luo and Sellke proved that staircase squares contain almost all partitions under both the uniform and Plancherel measures, and obtained full fourth-power coverage in all sufficiently large degrees, using modified shapes at nontriangular degrees [14, Theorems 1.4–1.6]. Harman and Ryba subsequently proved full coverage for every staircase tensor cube [7, Theorem 1.1]. Spin-character methods gave Bessenrodt all double-hook constituents, and Li proved the triple-hook case: these are targets with two and three diagonal cells, respectively [1, Theorem 4.10][13, Theorem 4.22]. Modular methods yield, among other families, all 2-height-zero constituents and framed staircases [3, Theorems 5.2 and 5.5]. More recent semigroup and generalized-block criteria give additional constituent families [5, Theorem 1.6]. These results concern different support families or tensor powers: neither almost-all coverage nor a third or fourth power gives the universal square required here.

The passage to nontriangular degrees also has a direct antecedent. Outside degrees 2,4,9, Li conjectured universal-square support for every self-conjugate staircase-like partition in a parity-dependent family, and asked whether suitable additions of one or two boxes preserve universal-square support [13, Section 5.5, Definition 5.3, Conjecture 1 and Problem 5.4]. Our large-degree construction uses a different family, making matching additions to the first two rows and columns of a parity-compatible staircase. The proof controls all constituents of the chosen enlargement; the candidate is fixed before the target is specified. Bessenrodt and Bowman formulate stronger conjectural refinements in terms of symmetric and alternating parts of tensor squares [2, Conjectures 10.2–10.3]; the tensor product in Theorem 1.1 is the ordinary diagonal tensor square.

We use the stronger cyclic form of the staircase result proved in A Cyclic Polytabloid Proof of Saxl’s Conjecture [16, Theorem 3.1]. The exact theorem and generator are specified in Theorem 2.4. The new task here is to pass from staircase degrees to all the degrees in Theorem 1.1.

1.2 The proof and its reusable ingredients

The obstacle is not simply to place a smaller staircase inside a larger diagram. Its constituents must survive a map from the actual enlarged square, and attachments can introduce cancelling alternating terms. Section 3 constructs the fixed self-conjugate partition for each large degree. Two complementary sufficient tests show that its square contains a prescribed target.

The first test, developed in Section 4, starts with one tensor obtained by alternating along the candidate’s rows in the first factor and its columns in the second. A coordinate projection of its diagonal orbit separates a smaller triangle from a width-two band and two attached diagrams. The projected module is the full induction of the triangle and complement modules. The cyclic staircase input supplies every constituent on the triangle, so branching reduces the task to finding a supported complement diagram contained in the desired target. The band is an odd path of alternating pairs: its contraction is a word of two-by-two matrices and adjugates. The attachments are handled by nondegenerate symmetric forms and a parity-sensitive Littlewood–Richardson splitting. Keeping the attached dual columns away from the path endpoints makes every surviving term factor, so the nonzero contractions do not cancel.

The second test, in Section 5, works in the full square, using column alternations in both factors. It allows independent position permutations in the two layers before applying a common projection. Label the two alphabets by positive integers; a pair of letters a,a' has output a+a'-1. Components can then be separated by both the numbers and sums of their outputs. This combines four-row path supports, two-row symmetric-form supports, and an additional three-row support construction. This size-and-sum projection, as well as the explicit attachment criterion, can be applied independently of the final degree estimates.

These tests divide the targets by their initial row and column sums. The balance test supplies a target whenever its first four rows or first four columns have small total size. For a remaining target, failure of the band test in both orientations bounds the first few row sums and column sums simultaneously. Section 6 shows that, for large parameters, a diagram satisfying both bounds has less area than the target’s prescribed size. Two exact capacity calculations settle the remaining bounded parameters. The Murnaghan–Nakayama recursion of Section 7 verifies every eligible degree at most 64. The latter computes exact residues of whole Kronecker-coefficient vectors, not floating-point approximations. We prove the soundness of every test and pruning rule used by the programs and include their complete source. Thus the finite computations close specified finite cases rather than impose an unproved threshold on positivity.

Section 2 fixes the common polytabloid conventions and the exact cyclic companion input before either construction begins. Section 8 assembles the candidate, the support tests, and the finite range. Appendices A and B supply the two proof-critical programs; the accompanying source also contains their independent checking tools.

2 Representation-theoretic tools

We fix the tensor conventions used by both the coordinate projections and the staircase input. The two transfer mechanisms below are dual polytabloid detection of a constituent and ordinary induction on disjoint position sets.

All representations are finite-dimensional over \C. A partition is padded with zeros when needed; \lambda^t denotes its conjugate. For partitions of the same integer, \lambda\unrhd\mu means \sum_{i\le k}\lambda_i\ge\sum_{i\le k}\mu_i for every k. Conjugation reverses dominance. Every symmetric-group representation is semisimple, every Specht module is self-dual, and S^\lambda\otimes\sgn\cong S^{\lambda^t}. We use the standard Specht construction, Young’s rule, branching, Schur–Weyl duality, and the Littlewood–Richardson and Pieri rules [10, 6, 15]. Their precise consequences needed below are recorded here.

2.1 Alternating blocks and dual tests

We realize Specht modules by column alternation and detect constituents by contracting with dual tensors. This viewpoint also underlies Ikenmeyer’s triangular construction [9, Sections 3–5].

Let B be a finite set of positions, and let E have ordered basis e_1,\ldots,e_D. For an ordered block A=(b_1,\ldots,b_k), k\le D, put

with the displayed factors placed at b_1,\ldots,b_k. For a set partition \mathcal A of B, put v_{\mathcal A}=\bigotimes_{A\in\mathcal A}v_A. Changing the order of one block changes only the overall sign. The position action of S_B is the usual permutation of tensor factors; all regroupings of factors are ordinary tensor identifications and add no signs.

If the block sizes are the column lengths of \theta, then

Indeed, arrange the blocks as tableau columns, and send a row tabloid to the word assigning letter i to its ith row. Column alternation sends its polytabloid to v_{\mathcal A}, which is nonzero because the initial row word has coefficient one. The same construction applies in a dual alphabet; see [10, Definitions 4.1 and 4.3, Theorem 4.12] for the Specht construction and ordinary irreducibility.

2.2 Support under induction

Throughout, combining constituents on disjoint position sets means ordinary induction from the product of their symmetric groups, not a Kronecker product. We use \boxtimes for an outer tensor product. Let c_{\alpha,\beta}^{\gamma} denote the Littlewood–Richardson coefficient, equivalently the multiplicity of S^\gamma in \Ind(S^\alpha\boxtimes S^\beta). This is the induction form of the LR rule [10, Rule 16.4]; its polynomial \GL counterpart is [15, Appendix A, (6.1)]. Only support, rather than equality of multiplicities, is required.

We also use two other immediate forms of the LR rule. First, c_{\alpha,(t)}^\gamma>0 precisely when \gamma/\alpha is a horizontal t-strip, meaning at most one new cell per column. This is Pieri’s rule [15, Chapter I, (5.16)–(5.17)]. Second, if \alpha fits in a rectangle, its rotated complement \beta satisfies c_{\alpha,\beta}^{\text{rectangle}}=1. For a rectangle (w^j), the complement has parts \beta_i=w-\alpha_{j+1-i}, and the Schur-character formula gives \mathbb S_\beta(\C^j)\cong\det^w\otimes \mathbb S_\alpha(\C^j)^* [15, Chapter I, (3.1); Appendix A, (8.2) and (8.4)]. Since \mathbb S_{(w^j)}(\C^j)=\det^w, the LR tensor-product rule and Schur’s lemma give the asserted multiplicity one. The zero-area case uses the empty partition, and the stated induction conventions include empty partitions as well.

2.3 The cyclic staircase input

For m\ge1, set

Let R_m and C_m be the actual row and column set partitions of B_m. Order each row by increasing j and each column by increasing i. In each tensor layer use the ordered alphabet e_1,\ldots,e_m. With the unnormalized initial-letter alternations defined above, set

The action in (2.3) is diagonal.

The complete proof is given in Section 6 of the companion [16], with the same ordered row and column blocks as here. The bibliography records the separate preprint’s stable article identifier. It is important that the theorem concerns the specified row/column generator, not merely the ambient staircase square. Common relabelings of the two ordered alphabets and changes of block orders preserve the assertion.

3 A fixed self-conjugate candidate

We now choose one diagram for the degree, before fixing a desired constituent. The construction preserves self-conjugacy by attaching transpose-matched cells to a staircase; its parameter bounds will later make the two support tests exhaustive.

Set N_0=0 and choose the largest nonnegative M for which N_M\le n and N_M\equiv n\pmod2, and put

Only M\ge9 will be used in this construction; smaller degrees will be treated separately.

Figure 1 shows the matched additions in a small instance. The path-incidence picture in Figure 2 will describe a different decomposition of the same construction.

When r=0, the candidate is the staircase itself, and Theorem 2.4 already supplies all constituents. For r>0 we give two sufficient support tests. For a target \nu, write its column heights and row lengths as

with zeros appended. Both tests refer to the single square S^L\otimes S^L fixed above. We are free to interchange h and w by Lemma 3.1.

The coverage has four steps. A small first-four row or column sum is handled by Proposition 5.7. Otherwise the band criterion covers every M\ge22 and all intermediate parameters apart from the nineteen pairs in (6.5); the exact capacity check handles those pairs. Proposition 7.1 handles all eligible degrees at most 64, completing the small-index remainder. The two finite checks thus have separate, explicitly bounded roles.

4 The band criterion

We use the parameters and the self-conjugate diagram L from (3.3), and write K=2M-1. In particular, r=2b+s-1. The following criterion supplies constituents whose diagrams have enough room for a path and its two attachments.

The three inequalities have separate roles: the first gives room for the path, the second reserves space at its endpoints, and the third provides the even column heights needed for the attachments. We first force the smaller cyclic triangle, then find nonzero path and attachment contractions, and finally show that they combine without cancellation. All alternating tensors use the conventions of Section 2; changing the order of a block changes only its overall sign.

4.1 A forced triangle and a full induced quotient

We first record the elementary induction fact used here and in the balance constructions. It is the coordinate-sector principle of [16, Section 4], applied to the marked alphabets of the enlarged diagram.

Regard L as its set B of cells, with rows and columns indexed from one. Let v_R,v_C be the alternating block tensors for its rows and columns, respectively, and put

Both factors have type L, since L is self-conjugate; hence W_L\subseteq S^L\otimes S^L after choosing the Specht identifications. Let

Thus D is the staircase of order M-2, and |F|=K+2r.

4.2 The path and its two attachments

Write \delta=s-1\in\{0,1\} and E=(b+\delta,b), omitting zero parts. Each copy of E has area r. To decompose F, start with the boundary cells i+j=M or M+1 in the staircase B_M. They form a width-two path of length K. Move its endpoint singletons from (M,1) and (1,M) to (\ell,1) and (1,\ell), respectively. More precisely, the resulting path positions are p_1,\ldots,p_K, where

The northeastern attachment is

with an interval interpreted as empty when its upper endpoint is smaller than its lower endpoint. Let E_- be its transpose. These sets are pairwise disjoint and exhaust F. The attachment E_+ has shape E, and E_- has the transposed incidence pattern.

Along the path, the column pairs are (p_1,p_2),(p_3,p_4),\ldots,(p_{K-2},p_{K-1}), with a column singleton at p_K. The row pairs are (p_2,p_3),(p_4,p_5),\ldots,(p_{K-1},p_K), with a row singleton at p_1. Only the first two column pairs and the last two row pairs belong to blocks extended by attachment cells.

Relabel the unmarked alphabet in increasing order, starting at one. Let P be the four-dimensional pair-letter space spanned by e_a\otimes e_c with a,c\le2. Let

Only letters available in the complement alphabet are included in these spans. There are b+\delta letters above two, so

In particular, every extra diagram of size 2r fits this actual alphabet; when r=0, both the diagram and X are empty. No cell of F is simultaneously in one of its two long rows and one of its two long columns, so every pair letter in u_F lies in P\oplus X.

The selection in Lemma 4.4 refers to fixed regions of F and need not commute with position permutations. We will use the factorization inside a dual-polytabloid contraction: the endpoint placement in the final proof will force precisely these selected terms to survive.

4.3 Contractions on an odd path

For t\ge0, Brown, van Willigenburg, and Zabrocki [4, Corollary 4.1] proved that the square of S^{(t+1,t)} contains exactly the partitions of 2t+1 with at most four rows, each with multiplicity one. We need this support in a specified cyclic path tensor, with any consecutive placement of the dual columns. The following proof extends the explicit contraction in [16, Section 5] to every odd length, including a single position, and gives the common-basis conclusion needed for several paths at once in the balance constructions.

4.4 The support of the two extra copies

The path supplies the four-row component. We now determine enough support in each attachment to supply every even-column diagram required by the last inequality of Proposition 4.1. The first step adapts the signed-average argument of [16, Section 3] to the two-row attachment.

4.5 Attaching without cancellation

The local contractions are now available. The remaining issue is their interaction: an elongated dual column could in principle mix path and attachment covectors. The endpoint clearance in the criterion allows us to place the covectors so that all mixed assignments vanish.

5 Balance tests

Retain the self-conjugate candidate L in Equation (3.3). For this second support test we use the full square S^L\otimes S^L, with both factors realized by column-alternating tensors on the same column blocks. Put

Thus c is the total size of the columns of length two, and T is the sum of the two largest column lengths. We prove that a target occurs whenever its first four column heights have sum at most 2M-2. The local components below supply balanced lists of trivial-factor sizes, whose induced support is tested by Young’s rule. We then establish an additional three-row support statement for the bounded capacity checks.

For reference, write

If t is even, let \mathcal O_4(t) be the members of \mathcal H_4(t) having an odd-height column. Finally, \mathcal P_3(c,s) denotes the partitions with at most three rows obtained from a member of \mathcal E_3(c) by adding a horizontal strip of size three and then a horizontal strip of size s. All support statements below mean inclusion, without any assertion about multiplicities.

5.1 Separating components by output values

Use independent ordered alphabets in the two Specht factors. A pair of letters (a,a') has output

For a collection B of column blocks on a position set D_B, let v_B be their alternating tensor and put Y_B=\C[S_{D_B}]v_B. By Equation (2.1), this is the Specht module whose column lengths are the sizes of the blocks in B. Realize both copies of Y_B on D_B. Every pair word occurring in their tensor square has the same number of positions and the same output sum:

Indeed, a block of length k uses 1,\ldots,k once in each factor, so its output sum is 2(1+\cdots+k)-k=k^2. Permuting positions within D_B, independently in the two layers, preserves these totals.

The local support guarantees proved in the following subsections are summarized in Table 1. The entries concerning the largest two lengths use q=M+b-1. When s=1, their lengths are q+1,q; when s=2, their lengths are q+2,q.

After applying Lemma 5.1, transitivity of induction permits us to combine selected factors in any order. In particular, the big pair can be combined with the singleton component even though their output ranges are not adjacent.

5.2 Coordinate functionals and path components

We first explain exactly how a surviving word coordinate supplies a path vector after the two sign twists.

In a tensor square, these two sign twists cancel. To make the passage through a projection explicit, let P:X\otimes X\longrightarrow W be a local coordinate projection onto its image. Its dual embeds W^* in (X\otimes X)^*. For a surviving pair word, its coordinate functional \epsilon satisfies \epsilon(Pz)=\epsilon(z), so its restriction belongs to this embedded copy of W^*. Lemma 5.2 identifies it with a nonzero multiple of the product of the two alternating vectors on its equal-letter blocks. Its entire position-permutation span remains in W^*. Finding a path among these products therefore proves support in W itself, since complex Specht modules are self-dual. In the next two lemmas, zero column lengths are omitted.

For the candidate diagram, the big component has T positions. When s=1, Lemma 5.3 supplies \mathcal H_4(T). When s=2, its two singleton columns can supply a trivial representation of size two at output one; Lemma 5.1 and Lemma 5.4 then supply \mathcal H_4(T+2). The big component’s outputs are at least M-1 in both cases.

5.3 Symmetric pairs and short strips

The path calculations handle the long columns. For the short-column components we use a direct fact about repeated symmetric tensors. Its polynomial-module conclusion is Littlewood’s classical even-row decomposition of symmetric powers of a symmetric square [15, Chapter I, Section 5, Example 5(a); Appendix A, Section 7, Example (1)]. The explicit contraction below also detects the prescribed tensor, which is what our coordinate projection requires.

An isolated length-k block, projected to constant output k, has the pair labels (a,k+1-a) for 1\le a\le k. Reversing one block’s labels shows that all terms in the projected tensor have the same sign. It is a nonzero symmetric tensor and hence supplies the trivial type of size k. For several equal-length blocks, the projected product still has coefficients of one common sign. Its full position average is nonzero, supplying the trivial type of their total size. This proves the first row of Table 1.

On an aligned length-two block, projection to constant output two gives, up to a common nonzero scalar,

This is a nondegenerate symmetric form on the two-letter space \Span(e_{12},e_{21}). Thus b+1 such blocks supply \mathcal E_2(c) by Lemma 5.5.

In our applications, the size-one strip is a singleton column at output one, and the size-three strip is the length-three block at output three. These ranges are disjoint from output two, so Lemma 5.1 justifies the required inductions.

5.4 The first-four-column bound

We now combine the local path and symmetric-pair supports. The aim is to replace each component by a list of trivial-factor sizes and then verify Young’s dominance inequalities for the entire target.

For positive integers t,j, let \operatorname{pack}(t,j) be the list of j integers whose entries differ by at most one and sum to t; zero entries, if any, are omitted. Young’s rule implies that the support obtained by inducing trivial factors of these sizes is exactly \mathcal H_j(t). Indeed, every partition of t with at most j rows dominates the balanced j-part partition, whereas a partition with more than j rows fails its jth dominance inequality. Thus a local component supplying \mathcal H_j(t) may contribute \operatorname{pack}(t,j) to a list of trivial-factor sizes for a support calculation.

5.5 A three-row component

The following construction is independent of the big pair and will be used in the cases M=10,12,14.

5.6 Using the local supports in capacity tests

The capacity tests use these local supports in two ways. First, they retain partitions with at most three rows whose entire dominance upper set lies in \mathcal P_3(c,s). The precise condition in Equation (6.8) guarantees the full induced-trivial support associated with each retained partition’s row lengths. Combining these lower supports with balanced middle parts gives the dominance bounds used below.

Second, they allocate at most four cells from each target column to the big pair, with total allocation T and at least one odd allocation when s=2. If the residual diagram is supplied by the other components, Lemma 2.3 combines the columnwise allocations to give the target. The exact allocation test and its support justification are given in Lemma 6.5.

6 Exhaustion of the capacity conditions

The balance and band constructions cover complementary shapes. A small sum of the first four rows or columns gives balance support. Otherwise both orientations have room for the path in the band criterion. Failure of that criterion then bounds both row and column prefixes, forcing an upper bound on the whole diagram’s area. We use this contradiction for large parameters and for most intermediate parameters. Nineteen pairs remain, for which we enumerate targets using the proved support tests.

Throughout this section, M\ge9 and r>0, and M,r,b,s,L,K have the meanings fixed above. Put

where h and w are the column heights and row lengths of a target partition of n, extended by zeros. Since L is self-conjugate, we may apply every test to either orientation of the target.

By Proposition 5.7, any target not already supplied satisfies

6.1 Two opposite prefixes

For the remaining intermediate cases, retain the least adequate core height in each orientation. Let d be least with H_d\ge K and e least with W_e\ge K; by Equation (6.1), both belong to \{1,2,3,4\}. Define

and the following finite set of pairs consisting of a prefix length and an upper bound for its sum:

If neither band test succeeds, every pair (i,U) in this set satisfies H_i\le U. Indeed minimality of d gives its first element, and W_f\ge K for f\ge e; failure of the band test with this f,q_f, followed by Equation (6.3), gives the other elements. Similarly, \mathcal D_{M,r}(e,d) bounds the row prefixes. The indices are crossed because enough room in the first f rows allows the band criterion to test the excess heights of columns, and conversely after transposition.

6.2 The nineteen exceptional cases

For the remaining parameters we first assemble induced supports of full degree. When these do not settle a target, we allocate cells to a constituent with at most four rows on the big pair and test the residual diagram against the lower components. A recursive enumeration checks that every target is covered by one of these supports or by the band criterion. All arithmetic is exact; the tests certify the sufficient support conditions, rather than approximate Kronecker coefficients.

For a multiset A of positive integers, write

By Lemma 2.2, inducing trivial representations of the sizes in A has precisely the support of partitions \gamma\vdash\|A\| satisfying

We call this the support associated with A. For integers u,j>0, let \operatorname{pack}(u,j) be the multiset of j integers \lfloor(u+i)/j\rfloor, 0\le i<j, with zero entries omitted. This is the balanced division from Section 5. Every use below has u\ge j, so the code’s fixed-length tuples have no zero entries. The implementation in Appendix A follows these constructions with integer lists and sets.

For a consecutive increasing list J of middle lengths, let \mathcal P(J) be the following collection of multisets. If |J| is even, pair consecutive entries u,u+1, replacing each pair by \operatorname{pack}(2u+1,4). If |J| is odd, choose an entry with an even number of predecessors, retain it as a single entry, and perform this pairing separately on the two remaining even lists. The empty list gives the empty multiset. Thus every member of \mathcal P(J) has the support supplied by those middle components, by Lemma 5.3 and Lemma 5.1. The function bal enumerates this collection.

Full-degree supports. Construct a collection \mathcal B as follows. For each row of Table 2 having the prescribed value of s, and each R\in\mathcal P(J), take the multiset union of R with the displayed parts. The indices (t,x) match those in the code. Omit a row if x>c.

Here t=2 combines the two singleton cells with the big pair; x=1 combines the singleton with the length-two blocks; and x=3 combines the length-three block with those blocks. The singleton left in the first row contributes the part 1. Every A\in\mathcal B has \|A\|=n, and its support is supplied by Lemmas 5.3, 5.4, and 5.6, combined by Lemma 5.1.

Supports below the big pair. These full-degree supports sometimes settle the target immediately. For the remaining targets we seek a columnwise allocation

with at least one odd \delta_i when s=2. The big pair supplies the partition with column-height multiset (\delta_i) by Lemmas 5.3 and 5.4. We therefore need lower-component support for the residual partition, whose column heights are the decreasing rearrangement of (h_i-\delta_i) and whose size is n-T. Lemma 2.3 will combine these two constituents.

Next construct a collection \mathcal C for the components other than the big pair. Write u=c+3+s, and let \mathcal G consist of the partitions of u with at most three rows obtained from a partition of c with even row lengths by successively adding horizontal strips of sizes 3 and s. Proposition 5.8 supplies all of \mathcal G on the blocks of lengths at most three. For partitions of equal size, write \alpha\unrhd\beta for dominance of row lengths. Retain a partition a of u with at most three rows if

No partition of more than three rows can dominate a, since its first three rows have sum strictly less than u. Thus Lemma 2.2 says that the entire support associated with the row lengths of a is available on the lower blocks. For each retained a and each R\in\mathcal P((4,5,\ldots,M-2)), put their multiset union in \mathcal C. Every resulting multiset has total n-T and supplied support. We may delete A from \mathcal C if its decreasing rearrangement strictly dominates that of another member B: every partition dominating A also dominates B, so this deletion does not shrink the union of their supports. Deleting all such members simultaneously is harmless: every descending chain in this finite strict dominance order terminates at a retained member whose support contains the supports of its predecessors.

These definitions explain the construction of B and C in the code. The function parts lists all partitions with at most three parts. For such partitions a,b, the function strip tests the interlacing inequalities

which are exactly the horizontal-strip condition. The calls have the prescribed size differences 3 and s. The list bad is the complement of \mathcal G, so the test excluding any \alpha\in\texttt{bad} dominating a is exactly Equation (6.8). The final dominance deletion is the valid deletion just described.

Safe pruning of partial diagrams. The available supports have now been specified. The next bound determines when an initial column list already certifies every possible completion.

The predicate bound(A,a) is exactly Equation (6.9); it returns false on an empty prefix. The predicate F(a,b) applies the band test, using known column and row prefixes and the largest admissible q=\min(8,\lfloor(K-7-d)/d\rfloor) for each d=1,\ldots,4. The lists contain exact initial row and column lengths. Summing only the known entries therefore gives lower bounds for both sums in the band criterion, since every capacity summand is nonnegative. Extending either prefix cannot invalidate a successful test. Thus the predicate stop(a,b), which accepts either band orientation or any support from \mathcal B, certifies all completions of these prefixes. Its use before the diagram is fully constructed is justified by Lemma 6.4.

Certifying a completed allocation. If prefix pruning does not settle a target, the next routine allocates cells to the big pair and tests the residual diagram against the lower supports. Only successful allocations are used.

Exhausting the targets. We have justified what each successful test certifies. It remains to show that the recursive search visits every target not already certified.

The calls run(m,r) in Appendix A were executed for every pair in Equation (6.5). All nineteen calls completed with every assertion satisfied; none was omitted using the optional earlier rectangle test. This verifies the remaining finite assertion in Lemma 6.6. As supplementary checks on the implementation, the accompanying capacity_independent.py compared diagonal-hook enumeration with ordinary partition enumeration for every 1\le n\le40 (113,696 emitted partitions in the selected orientation), checked the three-row Pieri support sets in all nineteen cases by a separate columnwise test, checked the totals of the multisets in \mathcal B and \mathcal C, and checked 748,716 prefix-bound instances for 1\le n\le16. These checks all passed; the preceding invariants, rather than their smaller degree ranges, justify exhaustive coverage in the nineteen required cases.

7 Small degrees by exact character calculation

The capacity calculations apply to the fixed large-degree candidate. For the remaining small degrees we instead calculate exact character residues, checking one self-conjugate candidate against every target. A nonzero residue certifies a positive integer multiplicity; no estimate or reconstruction of that integer is needed. We give the invariant of the calculation and its implementation bounds. The source is reproduced in Appendix B.

7.1 A recurrence for the entire coefficient vector

Write \chi^\lambda(\rho) for the character of S^\lambda on the conjugacy class of cycle type \rho. If m_j(\rho) is the number of parts of size j, put z_\rho=\prod_j j^{m_j(\rho)}m_j(\rho)!. The character inner-product formula gives

since symmetric-group characters are real. The program computes this sum for every \nu\vdash n at once, recursively selecting the parts of \rho in decreasing order.

Calculations take place in \mathbb F_p, where p\in\{1000000007,1000000009\}. Both numbers are prime, as is checked by trial division through 31622. Since n\le64<p, every denominator in (7.1) is invertible modulo p. All character values and vectors below are interpreted in this field. For s\geq0, let \mathcal P_s be the partitions of s, including the empty partition when s=0. For a vector v=(v_\lambda)_{\lambda\in\mathcal P_s}, write

Let [\lambda] denote the coordinate vector with entry one at \lambda and zero elsewhere, so \chi_{[\lambda]}=\chi^\lambda.

A border strip is an edge-connected skew diagram containing no 2\times2 square; its leg length is one less than its number of occupied rows. Let R_k denote the matrix that adds a border strip of size k, with entry (-1)^{\text{leg length}} for each permitted addition. Its source and target degrees will be understood from context. For v of degree s and \rho\vdash s-k, the Murnaghan–Nakayama rule [15, Chapter I, §7, Example 5][10, Rule 21.1] gives

In a call calc(s,k,e,v), the remaining cycle type has total size s and no part larger than k; e counts the size-k parts already selected. The extra counter records the factorial in z_\rho when several equal parts are selected successively. Reached states have 0\le s\le64, k\ge1, and e\ge0. Set \rho_1=0 for the empty partition and abbreviate m_j=m_j(\rho). Define F_{s,k,e}(v) by its \nu coordinate

Only states with e+m_k\leq64 are reached, so all displayed denominators are invertible. For 2\leq k\leq s, separating the terms with m_k=0 from those with m_k>0 yields

Indeed, (7.2) supplies the three character factors, while for m=m_k>0 the coefficient of the second term is

When m_k=0, the counter contributes only e!/e!=1, so the first term resets it to zero. The counter is needed precisely when another part of size k is selected. Each recursive call decreases (s,k) in lexicographic order: either the largest permitted part decreases, or the remaining degree decreases. The recursion therefore terminates.

The base cases are exact. At degree zero the answer is v_\varnothing^2. If 0<s<k, no size-k part remains, so F_{s,k,e}(v)=F_{s,s,0}(v): the factor involving e in (7.3) is then e!/e!=1. Calls with k=1 always have e=0, since this case is returned immediately rather than recursed into. Writing d_s=(\dim S^\nu)_{\nu\vdash s} gives

The vector d_s is computed by successive applications of R_1 to the empty partition: the resulting Young-lattice chains are standard tableaux. The array named fac in the source stores inverse factorials. Finally, a zero vector R_k^{\mathsf T}v contributes zero to the second term of (7.4); omitting that branch is therefore valid even if the vector is zero only modulo p.

The recurrence and base cases prove by induction on (s,k) that calc(s,k,e,v) returns F_{s,k,e}(v). At the initial call s=k=n and e=0, the weight in (7.3) is 1/z_\rho. Thus (7.1) identifies the output as

7.2 Exact implementation

Pad a partition \lambda with zero parts to length 64, and encode it by the beta set

There are 64 beads, and their positions sum to 2016+|\lambda|. The partition enumeration starts with B_\varnothing=\{0,\ldots,63\} and moves the jth bead to 64+\lambda_j-j while selecting nonincreasing parts. It enumerates every partition exactly once.

Moving a bead from x to an empty position x+k adds a border strip of size k. If the bead passes r other beads, the strip occupies r+1 rows, giving the sign (-1)^r. For the bit mask b of B_\lambda, the expression

selects just the permitted starting positions. Its top k bits are zero, so every selected position satisfies x+k\leq127. With m=2^x and t=2^{x+k}, the mask t-2m has exactly the bits strictly between the two positions. Thus cnt((t-m-m)&b) supplies precisely the strip leg length. The routine op implements R_k or its transpose according to its direction argument.

The finite beta-set identity

shows that sym tests self-conjugacy by requiring opposite bits at positions i and 127-i. Searching only these diagrams is legitimate; indeed

The floating-point score orders candidates by the logarithm of their hook product. It is finite and affects only search order, never the arithmetic certificate or the list of available candidates. The search stops as soon as one candidate passes the test for every target.

We record the implementation bounds to make the use of machine arithmetic explicit. Residues lie in [0,p-1]; their sum is at most 2000000016, within a signed 32-bit integer, and their product fits a signed 64-bit integer. All mask shifts are between 0 and 127 and use unsigned 128-bit arithmetic. The possible final enumeration argument pos=-1 occurs only after the last part has been placed, and the routine returns before shifting. Bit scans receive nonzero masks. All degree indices lie in [0,64]. In a non-base recursive step k\geq2, at most 32 parts of size k can be selected, so the inverse-array indices are also in range.

The partition-count recurrence, adding parts of sizes 1,2,\ldots,64, gives

The largest padded hash table has 4194304 entries and is at most half full. Hash arithmetic wraps only in unsigned types; collisions are resolved by equality of complete 128-bit masks. To see that every queried mask occurs in its table, sort its 64 occupied positions as b_1>\cdots>b_{64}\geq0. The numbers b_j-64+j are nonnegative and nonincreasing, hence form a partition. Moving one bead by k increases their sum by k, so the lookup is in precisely the enumerated target degree. Conversely, a size-at-most-64 partition never requires a position outside the mask.

7.3 Reproducibility and independent checks

The files smallcode_submitted.cpp, smallcode_dump.cpp, and smallcode_verify.py accompany this proof under verification/code/; the execution records are under verification/computation/. From verification/code/, the complete check can be reproduced in Bash by

g++ -O3 -std=c++17 smallcode_submitted.cpp -o smallcode_submitted
python3 smallcode_verify.py runs 1 3 {5..8} {10..64} \
  --seconds 300 --log ../computation/recheck.log

Each child has a 1536-MiB address-space limit, a 300-second wall limit and a 301-second CPU limit. The driver returns failure if any child fails or times out. The complete expected set of eligible degrees must be checked: the three excluded degrees are deliberately skipped by the C++ program and their zero exit statuses do not certify a square.

As an independent check of the implementation, the dump harness exposes every square vector at degrees 1 through 12, together with dimensions, self-conjugacy flags, and a nontrivial mixed input vector. The Python verifier computes integer characters by enumerating contained grid diagrams and testing border strips for connectivity and the absence of a 2\times2 square. Thus its strip enumeration and signs do not reuse the bead implementation. It checks character orthogonality, computes exact integer Kronecker coefficients using conjugacy-class sizes, and compares every exposed coefficient modulo both primes. Every comparison passed, including the dimensions and mixed vectors; the exact calculation also finds no covering square in degrees 2,4,9. The dump harness ran through degree 12 with undefined-behavior sanitization enabled and reported no failure. These checks are recorded in verification/computation/character-independent-1-12.log and can be repeated with

g++ -O2 -std=c++17 -fsanitize=undefined \
  -fno-sanitize-recover=all smallcode_dump.cpp -o smallcode_dump_ubsan
python3 smallcode_verify.py compare {1..12} \
  --log ../computation/recheck-independent.log

Before comparing coefficients, the Python verifier requires every expected record to occur exactly once, including every square vector under both moduli. Its fault-injection tests reject missing or duplicate records even when the child exits successfully. These tests can be run with

python3 -m unittest -v test_smallcode_verify.py

8 Completion of the proof

The finite calculations in this proof serve two distinct purposes. The capacity programs exhaust the explicitly listed intermediate parameters of the fixed family L; the character program proves existence directly in all eligible degrees at most 64. Neither calculation assumes that the fixed family works beyond a numerically observed threshold. Beyond the listed finite ranges, the sufficient tests and diagram-area inequalities give the proof.

A Exact capacity verification

The following standalone Python 3 file, verification/code/capacity_checks.py, contains both finite capacity checks. The mathematical justification of its tests and pruning rules is in Section 6. From the verification/code directory, run

Assertions must be enabled: do not use -O. The accompanying verification/code/capacity_independent.py provides separate checks of enumeration and dominance. In the listing, B and C are the collections of full-degree and lower support multisets of Section 6. The routines bound, hit, and gen implement, respectively, the prefix bound, the big-pair allocation, and diagonal-hook enumeration.

B Exact square-coefficient verification

This is the complete C++ verifier justified in Section 7. Compile with a compiler supporting unsigned __int128, for example g++ -O3 -std=c++17, and supply one integer degree 1\le n\le64, n\notin\{2,4,9\}, as its argument. A zero exit status certifies the search for that supplied degree only. The three excluded degrees are deliberately skipped without certification. The accompanying independent harness and execution records are described in verification/computation/README.md. The arrays masks and dimv store beta sets and dimensions; fac stores inverse factorials. The routines op and calc implement the border-strip operator and the coefficient-vector recurrence of Section 7.