latin_double_three_tail_count_formula
The open formula in arXiv:2610.29291 Conjecture 6.3: the number of Latin tableaux of shape (k,k-1,...,4,3,3) is 9 times 4 to the power k-3 for every k at least 5.
Statement
theorem latin_double_three_tail_count_formula (k : ℕ) (hk : 5 ≤ k) : latin_tableaux_count (latin_double_three_tail_shape k) = 9 * 4^(k-3)- Related work
- The explicitly open Conjecture 6.3 of https://arxiv.org/html/2610.29291v1. This is the paper's conjecture, not a theorem it proves and not a conjecture originating here. The pointwise four-extension and column-profile proof route was proposed here in experiments 4100, 4103 and 4106.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_tableaux_countThe number of Latin tableaux of shape $\mu$ and type $\mu'$, denoted $LT(\mu)$, is the cardinality of the finset of Latin tableaux of…
- latin_double_three_tail_count_baseThere are exactly 144 Latin tableaux of shape (5,4,3,3).
- latin_double_three_tail_count_stepThe number of tableaux of the next shape is the sum of availability permanents over all tableaux of the previous shape.
- 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_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…
The proof, explained
The theorem is proved by induction on $k \ge 5$. The base case $k = 5$ evaluates directly from the base count of 144 Latin tableaux. For the inductive step, the number of tableaux of shape $k + 1$ is expressed as a sum of availability matrix permanents over tableaux of shape $k$. Since each tableau extends in exactly 4 ways, the sum factors as 4 times the count at $k$, which the induction hypothesis and basic exponent arithmetic turn into $9 \cdot 4^{(k+1)-3}$.
The formula holds for the base case $k = 5$.
We proceed by induction on $k \ge 5$. For the base case $k = 5$, the count of Latin tableaux of shape $(5, 4, 3, 3)$ is given as 144 by `latin_double_three_tail_count_base`, and direct arithmetic evaluation (`norm_num`) confirms that $144 = 9 \cdot 4^{5-3} = 9 \cdot 16$.
uses
latin_double_three_tail_count_baseinduction' hk with k hk ih · rw [latin_double_three_tail_count_base] norm_num
The count of Latin tableaux of shape $k + 1$ equals the sum over all tableaux $T$ of shape $k$ of the permanent of their top-row availability matrix.
In the inductive step, recording $5 \le k$ allows rewriting the count of tableaux of shape $k + 1$ using `latin_double_three_tail_count_step`, which translates the extension of tableaux to the next shape into a sum of matrix permanents.
uses
latin_double_three_tail_count_step· have hk_le : 5 ≤ k := hk rw [latin_double_three_tail_count_step k hk_le]
Every Latin tableau of shape $k$ has exactly 4 extensions, reducing the sum to a constant summand 4.
By `latin_double_three_tail_four_extensions`, the top-row availability permanent is identically 4 for every tableau of shape $k$. Applying congruence of sums (`Finset.sum_congr`) replaces the permanent in each term of the sum with 4.
uses
latin_double_three_tail_four_extensions,Finset.sum_congrhave h_four : ∀ T ∈ latin_tableaux (latin_double_three_tail_shape k), (latin_top_row_availability (latin_double_three_tail_shape k) T (k + 1)).permanent = 4 := latin_double_three_tail_four_extensions k hk_le rw [Finset.sum_congr rfl h_four]
The sum evaluates to $(9 \cdot 4^{k-3}) \cdot 4$ by the induction hypothesis.
Summing the constant 4 over the set of tableaux of shape $k$ produces 4 times the number of such tableaux (`Finset.sum_const` and `nsmul_eq_mul`). Restating this cardinality as the count function, we substitute the induction hypothesis `ih` to replace the count with $9 \cdot 4^{k-3}$.
uses
Finset.sum_const,nsmul_eq_mulrw [Finset.sum_const, nsmul_eq_mul] change latin_tableaux_count (latin_double_three_tail_shape k) * 4 = 9 * 4 ^ (k + 1 - 3) rw [ih]
The expression $(9 \cdot 4^{k-3}) \cdot 4$ equals $9 \cdot 4^{(k+1)-3}$, completing the inductive step.
Because $k \ge 5$, integer arithmetic (`omega`) shows $(k + 1) - 3 = (k - 3) + 1$. Rewriting via `pow_succ` gives $4^{(k-3)+1} = 4^{k-3} \cdot 4$, and semiring simplification (`ring`) completes the equality.
uses
pow_succhave h_exp : k + 1 - 3 = (k - 3) + 1 := by omega rw [h_exp, pow_succ] ring
latin_double_three_tail_count_base- The number of Latin tableaux of shape $(5, 4, 3, 3)$ is 144.
latin_double_three_tail_count_step- For $k \ge 5$, the number of Latin tableaux of shape $k+1$ is the sum over all Latin tableaux $T$ of shape $k$ of the permanent of the top-row availability matrix for extending $T$.
latin_double_three_tail_four_extensions- For $k \ge 5$, every Latin tableau of shape $k$ has top-row availability permanent equal to 4 (that is, exactly 4 extensions to shape $k+1$).
Finset.sum_congr- If two finite sets are equal and two functions agree on every element of the set, their sums over that set are equal.
Finset.sum_const- The sum of a constant value $b$ over a finite set $s$ is the cardinality of $s$ times $b$ (as scalar multiplication).
nsmul_eq_mul- Scalar multiplication of a semiring element by a natural number $n$ equals algebraic multiplication by $n$.
pow_succ- In a monoid, $a^{n+1} = a^n \cdot a$.
- The combinatorial core of the inductive step—that every tableau of shape $k$ admits exactly 4 valid extensions to shape $k+1$, formulated as the permanent of an availability matrix—is established separately in `latin_double_three_tail_four_extensions`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem latin_double_three_tail_count_formula (k : ℕ) (hk : 5 ≤ k) : latin_tableaux_count (latin_double_three_tail_shape k) = 9 * 4^(k-3) := by induction' hk with k hk ih · rw [latin_double_three_tail_count_base] norm_num · have hk_le : 5 ≤ k := hk rw [latin_double_three_tail_count_step k hk_le] have h_four : ∀ T ∈ latin_tableaux (latin_double_three_tail_shape k), (latin_top_row_availability (latin_double_three_tail_shape k) T (k + 1)).permanent = 4 := latin_double_three_tail_four_extensions k hk_le rw [Finset.sum_congr rfl h_four] rw [Finset.sum_const, nsmul_eq_mul] change latin_tableaux_count (latin_double_three_tail_shape k) * 4 = 9 * 4 ^ (k + 1 - 3) rw [ih] have h_exp : k + 1 - 3 = (k - 3) + 1 := by omega rw [h_exp, pow_succ] ring