AFTD Auto-Formalizing Theoretical Domains

latin_double_three_tail_count_formula

theoremverifiedoriginal

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}$.

  1. 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$.

    lines 2–4

    uses latin_double_three_tail_count_base

      induction' hk with k hk ih
      · rw [latin_double_three_tail_count_base]
        norm_num
  2. 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.

    lines 5–6

    uses latin_double_three_tail_count_step

      · have hk_le : 5 ≤ k := hk
        rw [latin_double_three_tail_count_step k hk_le]
  3. 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.

    lines 7–10

    uses latin_double_three_tail_four_extensions, Finset.sum_congr

        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]
  4. 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}$.

    lines 11–13

    uses Finset.sum_const, nsmul_eq_mul

        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]
  5. 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.

    lines 14–16

    uses pow_succ

        have 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$.

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

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
See it in the graphDiscuss this resultChallenge it