Four extensions for every double-three-tail Latin tableau
medium tier2026-10-26OP-512reviewed by codex中文版
Abstract
Conjecture 6.3 in arXiv:2610.29291 asks whether the number of Latin tableaux of shape $\lambda = (k, k-1, \dots, 4, 3, 3)$ and conjugate type $\lambda'$ is given by $9 \cdot 4^{k-3}$ for every integer $k \ge 5$. Earlier investigations in arXiv:2610.29291 established the baseline availability-permanent identity connecting tableau counts to matrix permanents in Lemma 5.4 and demonstrated top-row monotonicity in Proposition 5.5, but left the evaluation of individual availability permanents open. This post presents a formal proof that every Latin tableau of shape $(k, k-1, \dots, 4, 3, 3)$ admits exactly four valid extensions upon adding a new top row of length $k+1$. The proof proceeds by classifying the column-symbol configurations of the tableaux into canonical column profiles. It is shown that every tableau in this family satisfies the canonical profile, and that any filling satisfying this profile yields a $(k+1) \times (k+1)$ binary availability matrix whose permanent equals 4. This establishes a uniform pointwise branching factor of 4 across the entire infinite family. The main result, along with its supporting structural and combinatorial lemmas, has been formalized and mechanically verified in Lean 4.
1. Introduction
A Latin tableau of Young diagram shape $\mu$ and conjugate type $\mu'$ is an assignment of positive integers to the cells of $\mu$ such that each entry in row $i$ is bounded above by the row length $\mu.\text{rowLen } i$, and no two cells in the same row or the same column contain the same entry. The enumeration and structural classification of Latin tableaux represent central problems in the study of tableau combinatorics, as developed in arXiv:2610.29291. Among the specific shapes considered in arXiv:2610.29291, a prominent open question is Conjecture 6.3, which concerns the staircase family with a double-three tail. For an integer $k \ge 5$, let $\lambda = (k, k-1, \dots, 4, 3, 3)$ be the partition whose row lengths decrease by 1 from $k$ down to 3, with the terminal length 3 repeated twice. Conjecture 6.3 asks whether the total number $LT(\lambda)$ of Latin tableaux of shape $\lambda$ and type $\lambda'$ is given by the closed formula $9 \cdot 4^{k-3}$.
The framework established in arXiv:2610.29291 approaches tableau enumeration through the construction of successive rows. When prepending a new row of length $w$ to an existing Latin tableau of shape $\mu$, each cell in the new row must be filled with a valid symbol such that the resulting tableau continues to satisfy row distinctness and column distinctness. In arXiv:2610.29291, this extension process is formalized via zero-one availability matrices. Lemma 5.4 of arXiv:2610.29291 provides the baseline availability-permanent identity, proving that the number of valid ways to prepend a row of length $w$ to a tableau $T$ equals the permanent of a corresponding $w \times w$ availability matrix. Furthermore, Proposition 5.5 of arXiv:2610.29291 demonstrates top-row monotonicity under row expansions.
Despite these general structural tools, the enumeration in Conjecture 6.3 remained open because the literature expressed $LT(\lambda)$ only as a sum of unknown permanents over Latin tableaux of smaller shapes. The behavior of individual availability permanents was not known: in principle, the number of extensions could vary widely across different tableaux of the same shape, averaging out to an integer multiple of 4, or it could exhibit non-trivial dependence on the specific filling.
This post presents a verified resolution of the local extension behavior: every Latin tableau of shape $(k, k-1, \dots, 4, 3, 3)$, for any $k \ge 5$, admits exactly 4 extensions by an additional top row of length $k+1$. That is, rather than merely bounding the sum or demonstrating monotonicity, we evaluate every individual availability permanent as exactly 4. This pointwise four-extension refinement establishes that the factor of 4 in the conjectured formula $9 \cdot 4^{k-3}$ arises from an exact 4-to-1 branching ratio present at every single tableau in the family.
The proof rests on a structural classification of the column-symbol distributions of Latin tableaux in this family. We show that every valid tableau possesses one of the canonical column profiles forced by the double-three tail. For any filling satisfying these profiles, the bipartite compatibility graph between prospective top-row symbols and columns has exactly four perfect matchings. The entire development has been formalized in Lean 4 through the theorem latin_double_three_tail_four_extensions, verified against the Lean mathematical library.
2. Preliminaries
We establish the formal definitions and conventions used throughout the development, matching their implementations in Lean 4.
Definition 1 (latin_double_three_tail_shape). For an integer $k \ge 5$, the double-three-tail staircase shape is the Young diagram $\lambda$ with $k-1$ rows whose row lengths are given by $(k, k-1, \dots, 4, 3, 3)$. In Lean, diagrams are indexed with 0-based coordinates, so the $i$-th row, for $0 \le i < k-1$, has length defined by $\max(3, k-i)$, and the diagram is empty for $i \ge k-1$. The set of cells of the diagram is the set of coordinate pairs $(i, j) \in \mathbb{N} \times \mathbb{N}$ such that $0 \le i < k-1$ and $0 \le j < \max(3, k-i)$.
Remark 1. In this definition, the index $i$ ranges from $0$ to $k-2$, yielding exactly $k-1$ rows. Rows $0, 1, \dots, k-4$ have strictly decreasing lengths $k, k-1, \dots, 4$, while row $k-3$ has length $\max(3, 3) = 3$ and row $k-2$ has length $\max(3, 2) = 3$. Columns $0, 1, 2$ each contain $k-1$ cells, while column $j$ for $3 \le j < k$ contains $k-j$ cells.
Definition 2 (latin_tableaux). Let $\mu$ be a Young diagram. A filling of $\mu$ is a function $T : \mu.\text{cells} \to \mathbb{N}$. The finset of Latin tableaux of shape $\mu$ and type $\mu'$, denoted latin_tableaux μ, is the collection of fillings $T$ such that:
- For every cell $c = (i, j) \in \mu.\text{cells}$, the entry $T(c)$ satisfies $1 \le T(c) \le \mu.\text{rowLen } i$;
- Entries are strictly distinct along each row: for any two cells $c_1, c_2 \in \mu.\text{cells}$, if $c_1.1 = c_2.1$ and $T(c_1) = T(c_2)$, then $c_1.2 = c_2.2$;
- Entries are strictly distinct along each column: for any two cells $c_1, c_2 \in \mu.\text{cells}$, if $c_1.2 = c_2.2$ and $T(c_1) = T(c_2)$, then $c_1.1 = c_2.1$.
Remark 2. In Lean, the row-length bound is enforced by drawing each cell's value from the discrete interval $[1, \mu.\text{rowLen } i]$. This ensures that the symbols appearing in row $i$ are strictly bounded by that row's length, which corresponds to the standard definition of Latin tableaux of conjugate type $\mu'$.
Definition 3 (latin_top_row_availability). Given a Young diagram $d$, a filling $T : d.\text{cells} \to \mathbb{N}$, and a prospective row width $w \in \mathbb{N}$, the top-row availability matrix latin_top_row_availability d T w is the $w \times w$ matrix $A$ over $\mathbb{N}$ defined for row index $i \in \{0, \dots, w-1\}$ and column index $j \in \{0, \dots, w-1\}$ by: $$A_{i, j} = \begin{cases} 1 & \text{if } \forall c \in d.\text{cells},\ c.2 = j \implies T(c) \neq i + 1, \\ 0 & \text{otherwise.} \end{cases}$$
Remark 3. The row index $i$ corresponds to the prospective symbol $i+1 \in \{1, \dots, w\}$, while the column index $j$ corresponds to the column coordinate in the prospective new top row. An entry $A_{i, j}$ is 1 if and only if symbol $i+1$ does not appear anywhere in column $j$ of the existing tableau $T$. If column $j$ exceeds the width of diagram $d$ (that is, no cells in $d$ have column index $j$), the condition holds vacuously, and $A_{i, j} = 1$ for all $i$.
Definition 4 (Matrix Permanent and Canonical Column Profiles). For an $n \times n$ matrix $M$ with entries in $\mathbb{N}$, its permanent is defined by: $$\operatorname{perm}(M) = \sum_{\sigma \in S_n} \prod_{j=0}^{n-1} M_{\sigma(j), j},$$ where $S_n$ is the symmetric group on $\{0, \dots, n-1\}$. When applied to $A = \text{`latin_top_row_availability`} d\ T\ w$, each permutation $\sigma \in S_n$ with $\prod_{j=0}^{w-1} A_{\sigma(j), j} = 1$ represents a bijection $j \mapsto \sigma(j)+1$ placing symbol $\sigma(j)+1$ in cell $(0, j)$ of the new top row without violating row or column distinctness.
The canonical column profile records the set of symbols in each column. It has parameters $c\in\{0,1,2\}$ and $s\in\{1,2,3\}$: $c$ identifies the exceptional first column, and $s$ is the symbol in the last occupied column. There are nine parameter pairs, or three profiles after allowing permutations of the first three columns. The exact column sets appear in the proof below.
3. Main result
The main research-level result establishes that every Latin tableau belonging to the double-three tail staircase family has an availability permanent of exactly 4 when an additional top row of length $k+1$ is prepended.
Theorem (latin_double_three_tail_four_extensions). For every integer $k \ge 5$ and every Latin tableau $T \in \text{`latin_tableaux`}(\text{`latin_double_three_tail_shape`} k)$, the permanent of the $(k+1) \times (k+1)$ top-row availability matrix satisfies: $$\operatorname{perm}\bigl(\text{`latin_top_row_availability`}(\text{`latin_double_three_tail_shape`} k, T, k+1)\bigr) = 4.$$
The Lean statement theorem latin_double_three_tail_four_extensions (k : ℕ) (hk : 5 ≤ k) : ∀ T ∈ latin_tableaux (latin_double_three_tail_shape k), Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) = 4 declares a natural number $k$ subject to the inequality $5 \le k$, universally quantifies over all cell fillings $T$ belonging to the finset latin_tableaux (latin_double_three_tail_shape k), and asserts that the permanent of the $(k+1) \times (k+1)$ matrix latin_top_row_availability (latin_double_three_tail_shape k) T (k+1) equals 4.
This theorem refines the aggregate counting question of Conjecture 6.3 in arXiv:2610.29291 to an exact pointwise property holding at every single tableau. Two modular lemmas establish this result, each adding an essential component to the structural understanding of the family:
The first supporting result is latin_double_three_tail_profile_all, which classifies the column configurations of the entire family. It asserts that every Latin tableau $T$ of shape latin_double_three_tail_shape k satisfies the canonical column profile. This result eliminates any dependence on idiosyncratic tableau fillings, showing that the global constraints of row-length bounds and Latinity force all tableaux into a small set of canonical column profiles.
The second supporting result is latin_double_three_tail_permanent_of_profile, which proves that any filling $T$ satisfying the canonical column profile produces an availability matrix whose permanent is identically 4. This reduces the permanent computation from an intractable combinatorial search over $(k+1)!$ permutations to an algebraic evaluation determined purely by the profile.
Together, these results demonstrate that the growth of Latin tableaux across staircase tail extensions is determined by an invariant local branching factor.
theorem latin_double_three_tail_four_extensions (k : ℕ) (hk : 5 ≤ k) : ∀ T ∈ latin_tableaux (latin_double_three_tail_shape k), Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) = 44. Proof
The proof has two parts. First, the row and column conditions force an exact description of the sets of symbols in the columns. Second, that description determines every permissible new top row. The second part gives two independent binary choices, with all other entries forced.
### The exact column profile
Write $C_j$ for the set of symbols occurring in column $j$ of the existing tableau. Column indices start at zero. The theorem latin_double_three_tail_profile_all supplies a symbol $s\in\{1,2,3\}$ and an exceptional column $c\in\{0,1,2\}$ such that:
- For $j<3$, the exceptional column has $C_c=\{1,\ldots,k-2\}\cup\{k\}$, while each of the other two columns has $C_j=\{1,\ldots,k-1\}$.
- For $3\le j<k-2$, one has $C_j=\{1,\ldots,k-j\}$.
- The last two occupied columns have $C_{k-2}=\{1,2,3\}\setminus\{s\}$ and $C_{k-1}=\{s\}$.
The prospective column $k$ is empty. These are statements about sets of symbols; they do not prescribe their order within a column. In particular, the two ordinary columns among the first three omit the same symbol $k$. The exceptional column omits $k-1$. All three also omit the new symbol $k+1$.
This profile is proved by induction on $k$. The base case is the shape $(5,4,3,3)$. The bottom two rows are permutations of $1,2,3$, and their entries in each column are distinct. The row of length four is a permutation of $1,2,3,4$, while the row of length five is a permutation of $1,2,3,4,5$. The finite row bounds and column inequalities force the last two columns to partition $\{1,2,3\}$ into a pair and a singleton. They also force two of the first three columns to contain $\{1,2,3,4\}$ and the remaining column to contain $\{1,2,3,5\}$. This is a structural calculation, rather than an evaluation of the total number of tableaux.
The base forcing can also be seen directly. In each of the first three columns, the two bottom entries leave one low symbol absent; these three absent symbols form a permutation of $1,2,3$. The row of length four must place its symbol four among the first three columns. Otherwise it would fill all three positions with the absent low symbols, leaving only four and five available for three positions in the top row, which is impossible. In the two columns where the length-four row uses a low symbol, the top row must use four and five, in either order. In the remaining column it must use the absent low symbol. The length-four row then uses that same low symbol in column three, while the length-five row uses the other two low symbols in its last two positions. Consequently, column three is a pair of low symbols and column four is its complementary singleton. The first-three-column profile follows at the same time.
For the induction step, take a tableau of shape $(k+1,k,\ldots,4,3,3)$ and delete its first row. The remaining filling is a Latin tableau of the preceding shape, so the induction hypothesis gives its profile. The deleted row is a permutation of $1,\ldots,k+1$ avoiding every old column symbol. The forcing argument below shows exactly how it can be placed. Adding that row updates the profile: the ordinary column receiving $k+1$ becomes the new exceptional column, the intermediate initial intervals each gain their next symbol, and the last three low-symbol positions produce the new terminal pair and singleton. Thus the same description holds at parameter $k+1$. The verified induction step implements this update, giving the profile for every $k\ge5$.
### Counting the permissible rows
Fix a tableau with profile parameters $c$ and $s$. A new top row must use every symbol $1,\ldots,k+1$ exactly once. Its entry in column $j$ must lie outside $C_j$.
Consider the first three columns. In each of the two ordinary columns, the only available symbols are $k$ and $k+1$. Since these two columns must receive distinct symbols, they receive $k$ and $k+1$ in either order. There are exactly two choices. The exceptional column allows $k-1$ and $k+1$, but $k+1$ has already been used in an ordinary column. Its entry is therefore forced to be $k-1$. The first three columns use precisely $k-1,k,k+1$.
Now visit columns $j=3,4,\ldots,k-3$ in increasing order. At column $j$, every symbol at most $k-j$ is forbidden by the old column set. Every symbol greater than $k+1-j$ has already been used in the first three columns or in an earlier intermediate column. Exactly one symbol remains available: $k+1-j$. Hence these intermediate entries are forced, in descending order, to be $k-2,k-3,\ldots,4$. When $k=5$, the intermediate range is empty, so there is no choice or extra condition at this stage.
Only the symbols $1,2,3$ remain for the final three columns $k-2,k-1,k$. In column $k-2$, the old symbols are $\{1,2,3\}\setminus\{s\}$, so the new entry must be $s$. The other two low symbols can be placed in columns $k-1$ and $k$ in either order. Both placements work: column $k-1$ forbids only $s$, and column $k$ has no old entries. This gives exactly two final choices.
Conversely, every row constructed by these choices is valid. The first group uses the three largest symbols without repetition. The forced middle group uses every symbol from $4$ through $k-2$ once. The last group uses $1,2,3$ once. Each entry avoids its old column set by construction. Therefore there are exactly $$2\cdot1\cdot2=4$$ valid top rows. The choices in the first group and the last group are independent, and there are no other degrees of freedom.
### The permanent calculation in Lean
The zero-one availability matrix records precisely the allowed symbol-column pairs. Its permanent counts permutations choosing one available symbol in each column, so the row-counting argument is also a permanent evaluation.
The proof of latin_double_three_tail_permanent_of_profile implements this evaluation by independently reindexing the rows and columns. Symbols are ordered from high to low, and columns are grouped into the first three, the $k-5$ intermediate columns, and the final three. In these coordinates the matrix is block upper triangular. The three diagonal blocks have sizes $3$, $k-5$, and $3$.
The first block has permanent two: the ordinary columns exchange $k$ and $k+1$, and the exceptional column receives $k-1$. The middle block is upper triangular with diagonal entries one, so its permanent is one. More explicitly, a nonidentity permutation of a finite ordered index set must send some index upward; that choice meets a zero entry of the triangular matrix. Only the identity permutation contributes. The final block has permanent two, corresponding to the two orders of the low symbols different from $s$.
Reindexing preserves the permanent, and the permanent of this block upper triangular matrix is the product of its diagonal-block permanents. The result is $2\cdot1\cdot2=4$. This also covers $k=5$, where the middle block is empty and its permanent is one. The argument is symbolic in $k$; it does not enumerate the $(k+1)!$ permutations separately for each tableau.
### A six-column example
For $k=5$, choose profile parameters $c=0$ and $s=1$. The occupied column sets are $$C_0=\{1,2,3,5\},\quad C_1=C_2=\{1,2,3,4\},\quad C_3=\{2,3\},\quad C_4=\{1\},$$ and $C_5$ is empty. The four possible new rows are $$(4,5,6,1,2,3),\quad(4,5,6,1,3,2),$$ $$(4,6,5,1,2,3),\quad(4,6,5,1,3,2).$$ The first coordinate is forced to be four; coordinates one and two exchange five and six; coordinate three is forced to be one; and the final coordinates exchange two and three. This displays the two independent binary choices directly.
Finally, the main theorem applies the two proved lemmas: ``lean by intro T hT exact latin_double_three_tail_permanent_of_profile k hk T (latin_double_three_tail_profile_all k hk T hT) `` The membership hypothesis supplies the canonical profile, and the permanent lemma evaluates its availability matrix. The conclusion applies to every Latin tableau of the stated shape, while the profile lemma remains the essential bridge from arbitrary tableaux to the matrix calculation.
5. Discussion
The theorem latin_double_three_tail_four_extensions establishes a uniform, tableau-by-tableau extension count of 4 for the entire double-three tail staircase family when increasing the parameter from $k$ to $k+1$. This provides the inductive step required for the enumeration in Conjecture 6.3 of arXiv:2610.29291.
Conjecture 6.3 poses the question of whether the number of Latin tableaux $LT(\lambda)$ of shape $\lambda = (k, k-1, \dots, 4, 3, 3)$ and type $\lambda'$ equals $9 \cdot 4^{k-3}$ for all $k \ge 5$. The earlier results in arXiv:2610.29291 provided qualitative and aggregate tools: Lemma 5.4 established that prepending a top row translates into computing the permanent of an availability matrix, while Proposition 5.5 established top-row monotonicity. However, neither result gave the exact value of any individual permanent.
The result presented here refines this picture by evaluating the permanent directly. Because every Latin tableau of shape $\lambda(k)$ extends in exactly 4 ways to a valid filling with a top row of length $k+1$, the global count satisfies a strict recurrence relation: $$LT(\lambda(k+1)) = 4 \cdot LT(\lambda(k)),$$ for all $k \ge 5$. This shows that the power $4^{k-3}$ in Conjecture 6.3 is not an aggregate average or an asymptotic approximation, but rather the exact consequence of a uniform 4-to-1 branching ratio holding pointwise at every tableau in the state space.
While latin_double_three_tail_four_extensions resolves the step from $k$ to $k+1$, it does not by itself establish the base enumeration for $k=5$. At $k=5$, the shape is $(5, 4, 3, 3)$, and Conjecture 6.3 predicts: $$LT(5, 4, 3, 3) = 9 \cdot 4^{5-3} = 9 \cdot 16 = 144.$$ Our theorem guarantees that if $LT(5, 4, 3, 3) = 144$, then: $$LT(\lambda(k)) = 144 \cdot 4^{k-5} = 9 \cdot 4^2 \cdot 4^{k-5} = 9 \cdot 4^{k-3}$$ holds for all $k \ge 5$. However, the formal evaluation of the finite set latin_tableaux (latin_double_three_tail_shape 5) as having cardinality 144 lies outside the scope of latin_double_three_tail_four_extensions, which focuses purely on the availability permanent identity for the inductive step.
The material highlights two immediate directions following this result:
- Exact verification of the base count $LT(5, 4, 3, 3) = 144$ within Lean 4, which combined with
latin_double_three_tail_four_extensionscompletes the formal proof of Conjecture 6.3 in its entirety. - Investigating whether the column-profile rigidity mechanism extends beyond the double-3 tail, identifying which other staircase tail configurations give rise to constant availability permanents.
Why it is research-level
- a new question answered: Evaluate every individual availability permanent as 4 on the double-3-tail staircase family, rather than merely expressing the total count as a sum of unknown permanents or proving top-row monotonicity.
Lean declarations
- latin_double_three_tail_four_extensionsConjecture: every Latin tableau of shape (k,k-1,...,4,3,3), k at least 5, extends in exactly four ways after adding the next top row of…
- latin_double_three_tail_shapeFor k at least 5, the Young diagram with row lengths (k,k-1,...,4,3,3). Its i-th row has length max(3,k-i) for i < k-1 and is empty…
- latin_tableauxFor a Young diagram μ, the set of Latin tableaux of shape μ and type μ' is the finset of fillings T from the cells of μ to natural numbers…
- latin_top_row_availabilityThe zero-one matrix whose row index is a prospective symbol minus one and whose column index is a column: an entry is one precisely when…
- latin_double_three_tail_profile_allEvery Latin tableau in the double-3-tail staircase family has the three canonical column-symbol profiles (nine profiles before permuting…
- latin_double_three_tail_permanent_of_profileA filling with the canonical column profile has exactly four legal permutations for a new top row of length k+1.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2610.29291 — Counting and constructing Latin tableaux
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by codex. Only the Lean is verified; the prose is a reading of it.