AFTD Auto-Formalizing Theoretical Domains

latin_double_three_tail_count_step

theoremverified

The number of tableaux of the next shape is the sum of availability permanents over all tableaux of the previous shape.

Statement

theorem latin_double_three_tail_count_step (k : ℕ) (hk : 5 ≤ k) : latin_tableaux_count (latin_double_three_tail_shape (k+1)) = ∑ T ∈ latin_tableaux (latin_double_three_tail_shape k), Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1))
Source
Helper for the open enumeration problem in https://arxiv.org/html/2610.29291v1, Conjecture 6.3, using the availability-permanent identity of Lemma 5.4. Exact computational route: experiments 4100, 4103 and 4106.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • 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_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_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_shape_rowLen_succDeleting the top row of the shape at k+1 leaves the shape at k, with row indices shifted by one.
  • latin_double_three_tail_profile_succInduction step for the double-3-tail staircase profile: for k >= 5, if every Latin tableau of shape (k,k-1,...,4,3,3) has the canonical…
  • latin_double_three_tail_shape_rowLenThe row-length sanity formula for the staircase with two bottom rows of length three.
  • mem_latin_double_three_tail_shapeA cell (i,j) belongs to the double-3-tail shape exactly when i < k-1 and j < max(3,k-i).
  • latin_double_three_tail_profileThe proposed column profile: among the first three columns, two contain [1,k-1] and one contains [1,k-2] together with k; intermediate…
Used by 1

The proof, explained

The proof partitions the Latin tableaux of shape k + 1 by their restriction to shape k using fiberwise counting. For each tableau T of shape k, the fiber consists of all valid extensions to shape k + 1, which is shown to be in bijection with permutations of Fin (k + 1) that do not clash with T in any column. Finally, the count of such collision-avoiding permutations is identified with the permanent of the top-row availability matrix.

  1. Any cell in row 0 of the shape k + 1 has column index strictly less than k + 1.

    By mem_latin_double_three_tail_shape, a cell (i, j) in shape k + 1 satisfies j < max 3 (k + 1 - i). For row 0 (i = 0), Nat.sub_zero simplifies this to j < max 3 (k + 1). Since k ≥ 2, max_eq_right simplifies the maximum to k + 1, yielding j < k + 1.

    lines 1–6

    uses mem_latin_double_three_tail_shape, Nat.sub_zero, max_eq_right

    theorem latin_double_three_tail_count_step_top_lt (k : ℕ) (hk : 2 ≤ k) (c : (latin_double_three_tail_shape (k + 1)).cells)
        (h0 : c.1.1 = 0) : c.1.2 < k + 1 := by
      have h := (mem_latin_double_three_tail_shape (k + 1) c.1.1 c.1.2).mp c.2
      rw [h0, Nat.sub_zero, max_eq_right (by omega)] at h
      exact h.2
    
  2. Shifting any cell in shape k + 1 with nonzero row index up by one row yields a cell in shape k.

    By mem_latin_double_three_tail_shape, the cell has row index c.1 < k and column index c.2 < max 3 (k + 1 - c.1). Since c.1 ≠ 0, k - (c.1 - 1) = k + 1 - c.1, so the column bound matches that of shape k, and c.1 - 1 < k - 1 follows by linear arithmetic. This also provides the well-definedness for extending any tableau T of shape k by a row 0 permutation.

    lines 7–19

    uses mem_latin_double_three_tail_shape

    theorem latin_double_three_tail_count_step_low_mem (k : ℕ) (c : (latin_double_three_tail_shape (k + 1)).cells)
        (h0 : c.1.1 ≠ 0) : (c.1.1 - 1, c.1.2) ∈ (latin_double_three_tail_shape k).cells := by
      have h := (mem_latin_double_three_tail_shape (k + 1) c.1.1 c.1.2).mp c.2
      apply (mem_latin_double_three_tail_shape k (c.1.1 - 1) c.1.2).mpr
      have : k - (c.1.1 - 1) = k + 1 - c.1.1 := by omega
      rw [this]
      exact ⟨by omega, h.2⟩
    
    def latin_double_three_tail_count_step_ext (k : ℕ) (hk : 2 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ)
        (σ : Equiv.Perm (Fin (k + 1))) : (latin_double_three_tail_shape (k + 1)).cells → ℕ :=
      fun c => if h : c.1.1 = 0 then (σ ⟨c.1.2, latin_double_three_tail_count_step_top_lt k hk c h⟩).val + 1
        else T ⟨(c.1.1 - 1, c.1.2), latin_double_three_tail_count_step_low_mem k c h⟩
    
  3. Row 0 of shape k + 1 has length k + 1.

    Evaluating the row length formula via latin_double_three_tail_shape_rowLen, row 0 has length max 3 (k + 1 - 0) by if_pos because 0 < k. Since k ≥ 2, max_eq_right evaluates this maximum to k + 1.

    lines 20–24

    uses latin_double_three_tail_shape_rowLen, if_pos, max_eq_right

    theorem latin_double_three_tail_count_step_row0 (k : ℕ) (hk : 2 ≤ k) :
        (latin_double_three_tail_shape (k + 1)).rowLen 0 = k + 1 := by
      rw [latin_double_three_tail_shape_rowLen, if_pos (by omega)]
      exact max_eq_right (by omega)
    
  4. In any Latin tableau of shape k + 1, the entries in row 0 are integers between 1 and k + 1.

    By definition of a Latin tableau, each cell's value lies in the interval from 1 to the length of its row. For row 0, latin_double_three_tail_count_step_row0 shows the row length is k + 1, so Finset.mem_Icc implies the entry at (0, j) satisfies 1 ≤ T'(0, j) ≤ k + 1.

    lines 25–33

    uses latin_double_three_tail_profile_succ_top_mem, latin_double_three_tail_count_step_row0, Finset.mem_Icc

    theorem latin_double_three_tail_count_step_top_bound (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ)
        (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) (j : ℕ) (hj : j < k + 1) :
        1 ≤ T' ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩ ∧
          T' ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩ ≤ k + 1 := by
      simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT
      have h := hT.1 ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩
      simp only [latin_double_three_tail_count_step_row0 k hk, Finset.mem_Icc] at h
      exact h
    
  5. The entries in row 0 of a Latin tableau of shape k + 1 define a permutation of Fin (k + 1).

    We define a function sending j to T'(0, j) - 1, which lies in Fin (k + 1) by latin_double_three_tail_count_step_top_bound. Row injectivity of the tableau implies that equal values must come from the same column, so the function is injective via Fin.ext and Fin.mk.injEq. On a finite type, injectivity is equivalent to bijectivity by Finite.injective_iff_bijective.mp, yielding a permutation via Equiv.ofBijective.

    lines 34–48

    uses latin_double_three_tail_profile_succ_top_mem, latin_double_three_tail_count_step_top_bound, Finite.injective_iff_bijective.mp, Fin.mk.injEq, Fin.ext

    noncomputable def latin_double_three_tail_count_step_perm (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ)
        (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) : Equiv.Perm (Fin (k + 1)) :=
      Equiv.ofBijective (fun j => ⟨T' ⟨(0, j.val), latin_double_three_tail_profile_succ_top_mem k j.val (by omega) j.isLt⟩ - 1,
        by have := latin_double_three_tail_count_step_top_bound k hk T' hT j.val j.isLt; omega⟩)
        (Finite.injective_iff_bijective.mp (by
          intro a b hab
          simp only [Fin.mk.injEq] at hab
          have ha := latin_double_three_tail_count_step_top_bound k hk T' hT a.val a.isLt
          have hb := latin_double_three_tail_count_step_top_bound k hk T' hT b.val b.isLt
          have heq : T' ⟨(0, a.val), latin_double_three_tail_profile_succ_top_mem k a.val (by omega) a.isLt⟩ =
              T' ⟨(0, b.val), latin_double_three_tail_profile_succ_top_mem k b.val (by omega) b.isLt⟩ := by omega
          simp only [latin_tableaux, Finset.mem_filter] at hT
          exact Fin.ext (hT.2.1 ⟨(0, a.val), latin_double_three_tail_profile_succ_top_mem k a.val (by omega) a.isLt⟩
            ⟨(0, b.val), latin_double_three_tail_profile_succ_top_mem k b.val (by omega) b.isLt⟩ rfl heq)))
    
  6. The value of the extracted permutation at column j plus 1 recovers the tableau entry T'(0, j).

    Unfolding the definition of the permutation and using Equiv.ofBijective_apply, the permutation value is T'(0, j) - 1. Adding 1 and using the lower bound 1 ≤ T'(0, j) from latin_double_three_tail_count_step_top_bound recovers T'(0, j) by linear arithmetic.

    lines 49–56

    uses latin_double_three_tail_count_step_top_bound, Equiv.ofBijective_apply

    theorem latin_double_three_tail_count_step_perm_apply (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ)
        (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) (j : Fin (k + 1)) :
        ((latin_double_three_tail_count_step_perm k hk T' hT j).val : ℕ) + 1 =
          T' ⟨(0, j.val), latin_double_three_tail_profile_succ_top_mem k j.val (by omega) j.isLt⟩ := by
      have := latin_double_three_tail_count_step_top_bound k hk T' hT j.val j.isLt
      simp only [latin_double_three_tail_count_step_perm, Equiv.ofBijective_apply]
      omega
    
  7. Setup of the bijection between tableaux of shape k + 1 restricting to T and permutations avoiding column collisions with T.

    We apply Finset.card_bij' with the forward map extracting the row 0 permutation via latin_double_three_tail_count_step_perm and the backward map extending T by a permutation σ via latin_double_three_tail_count_step_ext.

    lines 57–67

    uses Finset.card_bij'

    theorem latin_double_three_tail_count_step_fiber (k : ℕ) (hk : 2 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ)
        (hT : T ∈ latin_tableaux (latin_double_three_tail_shape k)) :
        ((latin_tableaux (latin_double_three_tail_shape (k + 1))).filter
          (fun T' => latin_double_three_tail_profile_succ_restrict k T' = T)).card =
        (Finset.univ.filter (fun σ : Equiv.Perm (Fin (k + 1)) => ∀ j : Fin (k + 1),
          ∀ c : (latin_double_three_tail_shape k).cells, c.val.2 = j.val → T c ≠ (σ j).val + 1)).card := by
      have hT' := hT
      simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT'
      obtain ⟨hb, hr, hcl⟩ := hT'
      refine Finset.card_bij' (fun T' h => latin_double_three_tail_count_step_perm k hk T' (Finset.mem_filter.mp h).1)
        (fun σ _ => latin_double_three_tail_count_step_ext k hk T σ) (hi := ?_) (hj := ?_) (left_inv := ?_) (right_inv := ?_)
  8. The permutation extracted from an extending tableau T' has no column collisions with T.

    If σ(j) + 1 equaled T(c) for some cell c in column j, then by latin_double_three_tail_count_step_perm_apply and the restriction hypothesis, T'(0, j) would equal T'(c.1 + 1, j). This contradicts column injectivity of T' because row 0 and row c.1 + 1 are distinct, completing the forward direction using true_and.

    lines 68–77

    uses latin_double_three_tail_count_step_perm_apply, true_and

      · intro T' h
        obtain ⟨hT1, hres⟩ := Finset.mem_filter.mp h
        simp only [Finset.mem_filter, Finset.mem_univ, true_and]
        intro j c hcj heq
        rw [latin_double_three_tail_count_step_perm_apply] at heq
        rw [← hres] at heq
        have hT1' := hT1
        simp only [latin_tableaux, Finset.mem_filter] at hT1'
        have := hT1'.2.2 _ _ hcj heq
        simp at this
  9. Extending T by a non-conflicting permutation σ yields a valid Latin tableau of shape k + 1.

    In row 0, entries (σ(j) : ℕ) + 1 satisfy the row length bound k + 1 by latin_double_three_tail_count_step_row0 and Finset.mem_Icc. In lower rows, entries come from T and satisfy the row bounds using latin_double_three_tail_shape_rowLen_succ and Nat.sub_add_cancel. Row injectivity follows from injectivity of σ on row 0 via Fin.ext and from T on lower rows. Column injectivity holds because σ avoids all values appearing in T in each column, and within lower rows it follows from column injectivity of T, handling cases using dif_pos and dif_neg together with latin_double_three_tail_count_step_top_lt and latin_double_three_tail_count_step_low_mem.

    lines 78–113

    uses latin_double_three_tail_count_step_row0, latin_double_three_tail_count_step_top_lt, latin_double_three_tail_count_step_low_mem, latin_double_three_tail_shape_rowLen_succ, Nat.sub_add_cancel, dif_pos, dif_neg, Fin.ext, Finset.mem_Icc

      · intro σ hσ
        have hσ := (Finset.mem_filter.mp hσ).2
        refine Finset.mem_filter.mpr ⟨?_, ?_⟩
        · simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset]
          refine ⟨fun c => ?_, fun c1 c2 h1 h2 => ?_, fun c1 c2 h1 h2 => ?_⟩
          · simp only [latin_double_three_tail_count_step_ext]
            split_ifs with h0
            · rw [Finset.mem_Icc, h0, latin_double_three_tail_count_step_row0 k hk]
              exact ⟨by omega, by have := (σ ⟨c.1.2, latin_double_three_tail_count_step_top_lt k hk c h0⟩).isLt; omega⟩
            · have := hb ⟨(c.1.1 - 1, c.1.2), latin_double_three_tail_count_step_low_mem k c h0⟩
              have e2 : (latin_double_three_tail_shape (k + 1)).rowLen c.1.1 =
                  (latin_double_three_tail_shape k).rowLen (c.1.1 - 1) := by
                have := latin_double_three_tail_shape_rowLen_succ k (c.1.1 - 1)
                rwa [Nat.sub_add_cancel (by omega)] at this
              rw [e2]
              exact this
          · simp only [latin_double_three_tail_count_step_ext] at h2
            by_cases h0 : c1.1.1 = 0
            · have h0' : c2.1.1 = 0 := by omega
              rw [dif_pos h0, dif_pos h0'] at h2
              have := σ.injective (Fin.ext (by simpa using h2))
              simpa using this
            · have h0' : c2.1.1 ≠ 0 := by omega
              rw [dif_neg h0, dif_neg h0'] at h2
              exact hr _ _ (by simp [h1]) h2
          · simp only [latin_double_three_tail_count_step_ext] at h2
            by_cases h0 : c1.1.1 = 0 <;> by_cases h0' : c2.1.1 = 0
            · omega
            · rw [dif_pos h0, dif_neg h0'] at h2
              exact absurd h2.symm (hσ ⟨c1.1.2, latin_double_three_tail_count_step_top_lt k hk c1 h0⟩ _ (by simp [h1]))
            · rw [dif_neg h0, dif_pos h0'] at h2
              exact absurd h2 (hσ ⟨c2.1.2, latin_double_three_tail_count_step_top_lt k hk c2 h0'⟩ _ (by simp [h1]))
            · rw [dif_neg h0, dif_neg h0'] at h2
              have := hcl _ _ (by simp [h1]) h2
              simp at this
              omega
  10. The restriction of the extended tableau back to shape k recovers T.

    For any cell c of shape k, its restriction evaluates the extended tableau at (c.1 + 1, c.2). Since the row index c.1 + 1 is nonzero, the extension evaluates to T(c.1 + 1 - 1, c.2) = T(c) by dif_neg.

    lines 114–117

    uses dif_neg

        · funext c
          simp only [latin_double_three_tail_profile_succ_restrict, latin_double_three_tail_count_step_ext]
          rw [dif_neg (by simp)]
          congr 1
  11. The forward and backward maps between extending tableaux and non-conflicting permutations are mutual inverses.

    On the left, an extending tableau T' is reconstructed from its extracted permutation on row 0 via latin_double_three_tail_count_step_perm_apply and from its restriction T on lower rows, proving equality using Subtype.ext and Prod.ext. On the right, extracting the permutation from the extension of σ immediately recovers σ since (σ(j) + 1) - 1 = σ(j).

    lines 118–133

    uses latin_double_three_tail_count_step_perm_apply, Subtype.ext, Prod.ext

      · intro T' h
        obtain ⟨hT1, hres⟩ := Finset.mem_filter.mp h
        funext c
        simp only [latin_double_three_tail_count_step_ext]
        split_ifs with h0
        · rw [latin_double_three_tail_count_step_perm_apply]
          congr 1
          exact Subtype.ext (Prod.ext h0.symm rfl)
        · rw [← hres]
          simp only [latin_double_three_tail_profile_succ_restrict]
          congr 1
          exact Subtype.ext (Prod.ext (by simp; omega) rfl)
      · intro σ hσ
        ext j
        simp [latin_double_three_tail_count_step_perm, latin_double_three_tail_count_step_ext]
    
  12. The total count of tableaux of shape k + 1 is the sum over tableaux T of shape k of the sizes of their extension fibers.

    Unfolding latin_tableaux_count, we partition the tableaux of shape k + 1 according to their restriction to shape k using Finset.card_eq_sum_card_fiberwise and latin_double_three_tail_profile_succ_restrict_mem. We then apply Finset.sum_congr to equate each summand with the fiber size, noting latin_double_three_tail_profile_succ.

    lines 134–140

    uses latin_double_three_tail_profile_succ, Finset.card_eq_sum_card_fiberwise, latin_double_three_tail_profile_succ_restrict_mem, Finset.sum_congr

    theorem latin_double_three_tail_count_step (k : ℕ) (hk : 5 ≤ k) : latin_tableaux_count (latin_double_three_tail_shape (k+1)) = ∑ T ∈ latin_tableaux (latin_double_three_tail_shape k), Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) := by
      have _hsucc := @latin_double_three_tail_profile_succ
      unfold latin_tableaux_count
      rw [Finset.card_eq_sum_card_fiberwise (f := latin_double_three_tail_profile_succ_restrict k)
        (t := latin_tableaux (latin_double_three_tail_shape k))
        (fun T' hT' => latin_double_three_tail_profile_succ_restrict_mem k T' hT')]
      refine Finset.sum_congr rfl fun T hT => ?_
  13. For each tableau T of shape k, its fiber size equals the permanent of the top-row availability matrix.

    By latin_double_three_tail_count_step_fiber, the fiber size is the number of permutations avoiding column collisions with T, which Finset.card_filter writes as a sum of 0-1 indicators. Unfolding Matrix.permanent and latin_top_row_availability, the permanent is the sum over permutations of the product of column availability indicators. By Finset.prod_boole, this product equals 1 precisely when σ avoids collisions in all columns, matching the fiber indicator; simplifying with Finset.mem_univ and true_imp_iff completes the proof.

    lines 141–145

    uses latin_double_three_tail_count_step_fiber, Finset.card_filter, Finset.sum_congr, Finset.prod_boole, Finset.mem_univ, true_imp_iff

      rw [latin_double_three_tail_count_step_fiber k (by omega) T hT, Finset.card_filter]
      unfold Matrix.permanent latin_top_row_availability
      refine Finset.sum_congr rfl fun σ _ => ?_
      rw [Finset.prod_boole]
      simp only [Finset.mem_univ, true_imp_iff]
Equiv.ofBijective_apply
Evaluating an equivalence constructed from a bijection yields the same result as applying the underlying function.
Fin.ext
Two elements of Fin n are equal if their underlying natural values are equal.
Fin.mk.injEq
Two elements of Fin n constructed from underlying naturals are equal if and only if those naturals are equal.
Finset.card_bij'
Two finite sets have equal cardinality if there exist maps between them that are mutual inverses on the respective sets.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set is the sum of the cardinalities of its fibers under a map to another finite set.
Finset.card_filter
The number of elements in a finite set satisfying a predicate equals the sum over the set of the predicate's 0-1 indicator function.
Finset.mem_Icc
An integer belongs to the closed interval [a, b] if and only if a ≤ x ≤ b.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.prod_boole
A finite product of 0-1 indicators equals 1 if the condition holds for every element in the index set, and 0 otherwise.
Finset.sum_congr
Two finite sums are equal if their index sets are identical and their summands agree at every index.
Finite.injective_iff_bijective.mp
An injective endofunction on a finite type is bijective.
Nat.sub_zero
Subtracting zero from a natural number leaves it unchanged (n - 0 = n).
Nat.sub_add_cancel
If m ≤ n, then (n - m) + m = n.
dif_neg
A dependent if-then-else expression reduces to its else branch when the condition is false.
dif_pos
A dependent if-then-else expression reduces to its then branch when the condition is true.
if_pos
A conditional expression evaluates to its then branch when the condition is true.
latin_double_three_tail_count_step_fiber
The number of Latin tableaux of shape k + 1 restricting to a fixed tableau T of shape k equals the number of permutations of Fin (k + 1) that do not clash with T in any column.
latin_double_three_tail_count_step_low_mem
If a cell in latin_double_three_tail_shape (k + 1) has nonzero row index, decrementing its row index produces a valid cell in latin_double_three_tail_shape k.
latin_double_three_tail_count_step_perm_apply
The value of the permutation induced by a tableau of shape k + 1 at column j, plus 1, equals the entry at (0, j) in the tableau.
latin_double_three_tail_count_step_row0
For k ≥ 2, row 0 of latin_double_three_tail_shape (k + 1) has length k + 1.
latin_double_three_tail_count_step_top_bound
In any Latin tableau of shape k + 1 with k ≥ 2, every entry in row 0 lies between 1 and k + 1.
latin_double_three_tail_count_step_top_lt
For k ≥ 2, any cell in row 0 of latin_double_three_tail_shape (k + 1) has column index strictly less than k + 1.
latin_double_three_tail_profile_succ
If all Latin tableaux of shape k satisfy the profile property, then all Latin tableaux of shape k + 1 do as well.
latin_double_three_tail_profile_succ_restrict_mem
Restricting a Latin tableau of shape k + 1 by dropping row 0 yields a valid Latin tableau of shape k.
latin_double_three_tail_profile_succ_top_mem
For k ≥ 1 and j < k + 1, the cell (0, j) belongs to latin_double_three_tail_shape (k + 1).
latin_double_three_tail_shape_rowLen
The length of row i in latin_double_three_tail_shape k is max 3 (k - i) if i < k - 1, and 0 otherwise.
latin_double_three_tail_shape_rowLen_succ
The length of row i + 1 in latin_double_three_tail_shape (k + 1) equals the length of row i in latin_double_three_tail_shape k.
max_eq_right
If a ≤ b, then max a b = b.
mem_latin_double_three_tail_shape
A pair (i, j) belongs to latin_double_three_tail_shape k if and only if i < k - 1 and j < max 3 (k - i).
Prod.ext
Two ordered pairs are equal if their first components are equal and their second components are equal.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
true_and
The logical proposition True ∧ p is equivalent to p.
true_imp_iff
The implication True → p is equivalent to p.

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_step_top_lt (k : ℕ) (hk : 2 ≤ k) (c : (latin_double_three_tail_shape (k + 1)).cells)    (h0 : c.1.1 = 0) : c.1.2 < k + 1 := by  have h := (mem_latin_double_three_tail_shape (k + 1) c.1.1 c.1.2).mp c.2  rw [h0, Nat.sub_zero, max_eq_right (by omega)] at h  exact h.2theorem latin_double_three_tail_count_step_low_mem (k : ℕ) (c : (latin_double_three_tail_shape (k + 1)).cells)    (h0 : c.1.1 ≠ 0) : (c.1.1 - 1, c.1.2) ∈ (latin_double_three_tail_shape k).cells := by  have h := (mem_latin_double_three_tail_shape (k + 1) c.1.1 c.1.2).mp c.2  apply (mem_latin_double_three_tail_shape k (c.1.1 - 1) c.1.2).mpr  have : k - (c.1.1 - 1) = k + 1 - c.1.1 := by omega  rw [this]  exact ⟨by omega, h.2⟩def latin_double_three_tail_count_step_ext (k : ℕ) (hk : 2 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ)    (σ : Equiv.Perm (Fin (k + 1))) : (latin_double_three_tail_shape (k + 1)).cells → ℕ :=  fun c => if h : c.1.1 = 0 then (σ ⟨c.1.2, latin_double_three_tail_count_step_top_lt k hk c h⟩).val + 1    else T ⟨(c.1.1 - 1, c.1.2), latin_double_three_tail_count_step_low_mem k c h⟩theorem latin_double_three_tail_count_step_row0 (k : ℕ) (hk : 2 ≤ k) :    (latin_double_three_tail_shape (k + 1)).rowLen 0 = k + 1 := by  rw [latin_double_three_tail_shape_rowLen, if_pos (by omega)]  exact max_eq_right (by omega)theorem latin_double_three_tail_count_step_top_bound (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ)    (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) (j : ℕ) (hj : j < k + 1) :    1 ≤ T' ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩ ∧      T' ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩ ≤ k + 1 := by  simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT  have h := hT.1 ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j (by omega) hj⟩  simp only [latin_double_three_tail_count_step_row0 k hk, Finset.mem_Icc] at h  exact hnoncomputable def latin_double_three_tail_count_step_perm (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ)    (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) : Equiv.Perm (Fin (k + 1)) :=  Equiv.ofBijective (fun j => ⟨T' ⟨(0, j.val), latin_double_three_tail_profile_succ_top_mem k j.val (by omega) j.isLt⟩ - 1,    by have := latin_double_three_tail_count_step_top_bound k hk T' hT j.val j.isLt; omega⟩)    (Finite.injective_iff_bijective.mp (by      intro a b hab      simp only [Fin.mk.injEq] at hab      have ha := latin_double_three_tail_count_step_top_bound k hk T' hT a.val a.isLt      have hb := latin_double_three_tail_count_step_top_bound k hk T' hT b.val b.isLt      have heq : T' ⟨(0, a.val), latin_double_three_tail_profile_succ_top_mem k a.val (by omega) a.isLt⟩ =          T' ⟨(0, b.val), latin_double_three_tail_profile_succ_top_mem k b.val (by omega) b.isLt⟩ := by omega      simp only [latin_tableaux, Finset.mem_filter] at hT      exact Fin.ext (hT.2.1 ⟨(0, a.val), latin_double_three_tail_profile_succ_top_mem k a.val (by omega) a.isLt⟩        ⟨(0, b.val), latin_double_three_tail_profile_succ_top_mem k b.val (by omega) b.isLt⟩ rfl heq)))theorem latin_double_three_tail_count_step_perm_apply (k : ℕ) (hk : 2 ≤ k) (T' : (latin_double_three_tail_shape (k + 1)).cells → ℕ)    (hT : T' ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) (j : Fin (k + 1)) :    ((latin_double_three_tail_count_step_perm k hk T' hT j).val : ℕ) + 1 =      T' ⟨(0, j.val), latin_double_three_tail_profile_succ_top_mem k j.val (by omega) j.isLt⟩ := by  have := latin_double_three_tail_count_step_top_bound k hk T' hT j.val j.isLt  simp only [latin_double_three_tail_count_step_perm, Equiv.ofBijective_apply]  omegatheorem latin_double_three_tail_count_step_fiber (k : ℕ) (hk : 2 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ)    (hT : T ∈ latin_tableaux (latin_double_three_tail_shape k)) :    ((latin_tableaux (latin_double_three_tail_shape (k + 1))).filter      (fun T' => latin_double_three_tail_profile_succ_restrict k T' = T)).card =    (Finset.univ.filter (fun σ : Equiv.Perm (Fin (k + 1)) => ∀ j : Fin (k + 1),      ∀ c : (latin_double_three_tail_shape k).cells, c.val.2 = j.val → T c ≠ (σ j).val + 1)).card := by  have hT' := hT  simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT'  obtain ⟨hb, hr, hcl⟩ := hT'  refine Finset.card_bij' (fun T' h => latin_double_three_tail_count_step_perm k hk T' (Finset.mem_filter.mp h).1)    (fun σ _ => latin_double_three_tail_count_step_ext k hk T σ) (hi := ?_) (hj := ?_) (left_inv := ?_) (right_inv := ?_)  · intro T' h    obtain ⟨hT1, hres⟩ := Finset.mem_filter.mp h    simp only [Finset.mem_filter, Finset.mem_univ, true_and]    intro j c hcj heq    rw [latin_double_three_tail_count_step_perm_apply] at heq    rw [← hres] at heq    have hT1' := hT1    simp only [latin_tableaux, Finset.mem_filter] at hT1'    have := hT1'.2.2 _ _ hcj heq    simp at this  · intro σ hσ    have hσ := (Finset.mem_filter.mp hσ).2    refine Finset.mem_filter.mpr ⟨?_, ?_⟩    · simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset]      refine ⟨fun c => ?_, fun c1 c2 h1 h2 => ?_, fun c1 c2 h1 h2 => ?_⟩      · simp only [latin_double_three_tail_count_step_ext]        split_ifs with h0        · rw [Finset.mem_Icc, h0, latin_double_three_tail_count_step_row0 k hk]          exact ⟨by omega, by have := (σ ⟨c.1.2, latin_double_three_tail_count_step_top_lt k hk c h0⟩).isLt; omega⟩        · have := hb ⟨(c.1.1 - 1, c.1.2), latin_double_three_tail_count_step_low_mem k c h0⟩          have e2 : (latin_double_three_tail_shape (k + 1)).rowLen c.1.1 =              (latin_double_three_tail_shape k).rowLen (c.1.1 - 1) := by            have := latin_double_three_tail_shape_rowLen_succ k (c.1.1 - 1)            rwa [Nat.sub_add_cancel (by omega)] at this          rw [e2]          exact this      · simp only [latin_double_three_tail_count_step_ext] at h2        by_cases h0 : c1.1.1 = 0        · have h0' : c2.1.1 = 0 := by omega          rw [dif_pos h0, dif_pos h0'] at h2          have := σ.injective (Fin.ext (by simpa using h2))          simpa using this        · have h0' : c2.1.1 ≠ 0 := by omega          rw [dif_neg h0, dif_neg h0'] at h2          exact hr _ _ (by simp [h1]) h2      · simp only [latin_double_three_tail_count_step_ext] at h2        by_cases h0 : c1.1.1 = 0 <;> by_cases h0' : c2.1.1 = 0        · omega        · rw [dif_pos h0, dif_neg h0'] at h2          exact absurd h2.symm (hσ ⟨c1.1.2, latin_double_three_tail_count_step_top_lt k hk c1 h0⟩ _ (by simp [h1]))        · rw [dif_neg h0, dif_pos h0'] at h2          exact absurd h2 (hσ ⟨c2.1.2, latin_double_three_tail_count_step_top_lt k hk c2 h0'⟩ _ (by simp [h1]))        · rw [dif_neg h0, dif_neg h0'] at h2          have := hcl _ _ (by simp [h1]) h2          simp at this          omega    · funext c      simp only [latin_double_three_tail_profile_succ_restrict, latin_double_three_tail_count_step_ext]      rw [dif_neg (by simp)]      congr 1  · intro T' h    obtain ⟨hT1, hres⟩ := Finset.mem_filter.mp h    funext c    simp only [latin_double_three_tail_count_step_ext]    split_ifs with h0    · rw [latin_double_three_tail_count_step_perm_apply]      congr 1      exact Subtype.ext (Prod.ext h0.symm rfl)    · rw [← hres]      simp only [latin_double_three_tail_profile_succ_restrict]      congr 1      exact Subtype.ext (Prod.ext (by simp; omega) rfl)  · intro σ hσ    ext j    simp [latin_double_three_tail_count_step_perm, latin_double_three_tail_count_step_ext]theorem latin_double_three_tail_count_step (k : ℕ) (hk : 5 ≤ k) : latin_tableaux_count (latin_double_three_tail_shape (k+1)) = ∑ T ∈ latin_tableaux (latin_double_three_tail_shape k), Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) := by  have _hsucc := @latin_double_three_tail_profile_succ  unfold latin_tableaux_count  rw [Finset.card_eq_sum_card_fiberwise (f := latin_double_three_tail_profile_succ_restrict k)    (t := latin_tableaux (latin_double_three_tail_shape k))    (fun T' hT' => latin_double_three_tail_profile_succ_restrict_mem k T' hT')]  refine Finset.sum_congr rfl fun T hT => ?_  rw [latin_double_three_tail_count_step_fiber k (by omega) T hT, Finset.card_filter]  unfold Matrix.permanent latin_top_row_availability  refine Finset.sum_congr rfl fun σ _ => ?_  rw [Finset.prod_boole]  simp only [Finset.mem_univ, true_imp_iff]
See it in the graphDiscuss this resultChallenge it