AFTD Auto-Formalizing Theoretical Domains

latin_double_three_tail_permanent_of_profile

theoremverified

A filling with the canonical column profile has exactly four legal permutations for a new top row of length k+1.

Statement

theorem latin_double_three_tail_permanent_of_profile (k : ℕ) (hk : 5 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ) (hp : latin_double_three_tail_profile k T) : Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) = 4
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
26 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_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…
  • 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_top_row_availability_eq_one_iffThe availability entry equals one exactly when the prospective positive symbol does not already occur in that column.
  • matrix_permanent_from_blocks_zero_one_twoFor any commutative semiring R and any square matrices A over m and D over n, the permanent of the block matrix with A in the top-left, 0…
  • mem_latin_column_symbolsA symbol belongs to a column-symbol set exactly when a cell of that column has that value.
  • latin_column_symbolsThe finite set of symbols appearing in column j of a fixed filling T of a Young diagram d.
Used by 1

The proof, explained

To count the number of legal ways to complete the top row of a Latin tableau satisfying the canonical column profile, the proof computes the permanent of its (k+1) × (k+1) availability matrix. It first shows that matrix permanents are invariant under simultaneous row and column permutations (permanent_equiv). Next, it shows that the availability matrix for any profile-satisfying filling can be transformed via row and column bijections into an upper-triangular block matrix (canonical) composed of a 3×3 head block, an m×m staircase block, and a 3×3 tail block. Finally, applying the block upper-triangular permanent product formula gives a permanent of 2 × 1 × 2 = 4.

  1. The permanent of a matrix is invariant under simultaneously permuting its rows and columns by bijections.

    Unfolding the definition of the permanent, the sum over all permutations is reindexed by conjugation with the row and column equivalences using Fintype.sum_equiv and Equiv.equivCongr. Then, for each fixed permutation, the product of matrix entries across rows is reindexed using Fintype.prod_equiv along the column equivalence.

    lines 8–13

    uses Fintype.sum_equiv, Equiv.equivCongr, Fintype.prod_equiv, Matrix.submatrix_apply, Equiv.equivCongr_apply_apply, Equiv.symm_apply_apply

      unfold Matrix.permanent
      refine Fintype.sum_equiv (Equiv.equivCongr c r) _ _ ?_
      intro σ
      refine Fintype.prod_equiv c _ _ ?_
      intro i
      simp only [Matrix.submatrix_apply,Equiv.equivCongr_apply_apply,Equiv.symm_apply_apply]
  2. Every non-identity permutation of Fin n has an index i strictly smaller than its image σ(i).

    Suppose for contradiction that σ(i) ≤ i for all i. Since σ is not the identity, there exists some index i with σ(i) ≠ i, and hence σ(i) < i. Summing over all elements gives ∑ σ(j) < ∑ j. However, reindexing the sum by the permutation σ gives ∑ σ(j) = ∑ j via Equiv.sum_comp, a contradiction.

    lines 17–30

    uses Equiv.ext, Fin.ext, Finset.sum_lt_sum, Finset.mem_univ, Equiv.sum_comp

      by_contra h
      push Not at h
      have hex : ∃ i, σ i ≠ i := by
        by_contra hh
        push Not at hh
        exact hne (by apply Equiv.ext; intro i; exact hh i)
      obtain ⟨i,hi⟩ := hex
      have hi' : (σ i).val ≠ i.val := fun he => hi (Fin.ext he)
      have hi_le := h i
      have hi_lt : (σ i).val < i.val := by omega
      have hsum := Finset.sum_lt_sum (fun j (_ : j ∈ (Finset.univ : Finset (Fin n))) => h j)
        ⟨i,Finset.mem_univ _,hi_lt⟩
      have heq := Equiv.sum_comp σ (fun j : Fin n => j.val)
      omega
  3. The staircase matrix of size n (entries 1 for i ≤ j and 0 for i > j) has permanent 1.

    In the permanent sum over all permutations, any non-identity permutation has an index i with i < σ(i) by perm_has_rise, which means entry (σ(i), i) is 0 because σ(i) > i. Thus, every non-identity permutation contributes 0 to the sum by Finset.prod_eq_zero. Only the identity permutation contributes, giving a single product of 1s, which equals 1.

    lines 34–44

    uses Finset.sum_eq_single, perm_has_rise, Finset.prod_eq_zero, Finset.mem_univ

      classical
      unfold Matrix.permanent
      have heq : (∑ σ : Equiv.Perm (Fin n), ∏ i : Fin n, stair n (σ i) i) =
          ∏ i : Fin n, stair n ((1 : Equiv.Perm (Fin n)) i) i := by
        apply Finset.sum_eq_single
        · intro σ _ hσ
          obtain ⟨i,hi⟩ := perm_has_rise σ hσ
          apply Finset.prod_eq_zero (Finset.mem_univ i)
          simp only [stair,show ¬ (σ i).val ≤ i.val by omega,ite_false]
        · simp
      simpa [stair] using heq
  4. The 3×3 head matrix (for any column c) and tail matrix (for any shift s) each have permanent equal to 2. automation

    Both head c and tail (s+1) are explicit 3×3 matrices with 0-1 entries. Lean verifies by finite evaluation across all 3! = 6 permutations that each has permanent 2.

    lines 53–54

    private lemma head_perm : ∀ c : Fin 3, (head c).permanent = 2 := by decide
    private lemma tail_perm : ∀ s : Fin 3, (tail (s.val+1)).permanent = 2 := by decide
  5. The canonical block upper-triangular matrix has permanent 4.

    The canonical matrix is partitioned into an upper-left 3×3 block head c and a lower-right (m+3)×(m+3) block, with a zero lower-left block. The lower-right block is itself block upper-triangular with diagonal blocks stair m and tail (s+1). Applying the block upper-triangular permanent product formula twice decomposes the permanent into the product of the three diagonal permanents: 2 * (1 * 2) = 4.

    lines 60–67

    uses matrix_permanent_from_blocks_zero_one_two_zero_two_one, head_perm, tail_perm, permanent_stair

      have hinner : (Matrix.fromBlocks (stair m) (Matrix.of fun _ _ => 1) 0 (tail (s.val+1))).permanent =
          (stair m).permanent * (tail (s.val+1)).permanent :=
        matrix_permanent_from_blocks_zero_one_two_zero_two_one _ _ _
      calc
        (canonical m c (s.val+1)).permanent = (head c).permanent *
            (Matrix.fromBlocks (stair m) (Matrix.of fun _ _ => 1) 0 (tail (s.val+1))).permanent :=
          matrix_permanent_from_blocks_zero_one_two_zero_two_one _ _ _
        _ = 4 := by rw [hinner,head_perm,tail_perm,permanent_stair]
  6. The index set Fin 3 ⊕ (Fin m ⊕ Fin 3) is in bijection with Fin (m+6) via column and reversed row maps.

    The column map cols m is defined by composing canonical sum bijections that partition Fin (m+6) into consecutive intervals of lengths 3, m, and 3. The row map rows m reverses this order, sending an element to m + 6 - (cols m x + 1). The values on each of the three block components follow by definition.

    lines 72–77

        (finCongr (by omega))
    private def rows (m : ℕ) : I m ≃ Fin (m+6) := (cols m).trans Fin.revPerm
    private lemma cols_left (m : ℕ) (i : Fin 3) : (cols m (.inl i)).val = i.val := by rfl
    private lemma cols_mid (m : ℕ) (i : Fin m) : (cols m (.inr (.inl i))).val = 3+i.val := by rfl
    private lemma cols_tail (m : ℕ) (i : Fin 3) : (cols m (.inr (.inr i))).val = 3+(m+i.val) := by rfl
    private lemma rows_val (m : ℕ) (x : I m) : (rows m x).val = m+6-((cols m x).val+1) := by rfl
  7. The 1-based row symbols under the row bijection are m+6-i on the left block, m+3-i on the middle block, and 3-i on the tail block.

    Unfolding rows_val and the respective column formulas cols_left, cols_mid, and cols_tail, linear integer arithmetic simplifies the reversed row positions into the exact row symbol values.

    lines 97–106

    uses rows_val, cols_left, cols_mid, cols_tail

      rw [rows_val,cols_left]
      omega
    private lemma rows_mid_symbol (m : ℕ) (i : Fin m) :
        (rows m (.inr (.inl i))).val+1 = m+3-i.val := by
      rw [rows_val,cols_mid]
      omega
    private lemma rows_tail_symbol (m : ℕ) (i : Fin 3) :
        (rows m (.inr (.inr i))).val+1 = 3-i.val := by
      rw [rows_val,cols_tail]
      omega
  8. The forbidden symbol sets for the left, middle, and tail columns match their canonical interval descriptions.

    Substituting the column formulas cols_left, cols_mid, and cols_tail into the piecewise definition of profile_sets, the index bounds identify which case applies for each block: columns in Fin 3 get the left profile, columns in Fin m get the middle staircase interval, and the three tail columns get the low pair and empty sets.

    lines 111–128

    uses cols_left, cols_mid, cols_tail, Fin.ext_iff

      simp only [profile_sets,cols_left,j.isLt,ite_true,Fin.ext_iff]
    
    private lemma sets_mid (m : ℕ) (c : Fin 3) (s : ℕ) (j : Fin m) :
        profile_sets m c s (cols m (.inr (.inl j))) = Finset.Icc 1 (m+2-j.val) := by
      have h0 : ¬ 3+j.val < 3 := by omega
      have h1 : 3+j.val < m+3 := by omega
      simp only [profile_sets,cols_mid,h0,h1,ite_false,ite_true]
      congr 1
      omega
    
    private lemma sets_tail (m : ℕ) (c : Fin 3) (s : ℕ) (j : Fin 3) :
        profile_sets m c s (cols m (.inr (.inr j))) =
          if j.val = 0 then Finset.Icc 1 3 \ {s} else if j.val = 1 then {s} else ∅ := by
      have h0 : ¬ 3+(m+j.val) < 3 := by omega
      have h1 : ¬ 3+(m+j.val) < m+3 := by omega
      have h2 : (3+(m+j.val) = m+3) ↔ j.val = 0 := by omega
      have h3 : (3+(m+j.val) = m+4) ↔ j.val = 1 := by omega
      simp only [profile_sets,cols_tail,h0,h1,h2,h3,ite_false]
  9. Membership of 3 - i in {1, 2, 3} \ {s+1} is equivalent to 3 - i ≠ s+1.

    Because i is in Fin 3, the value 3 - i is always between 1 and 3. Thus, being in the interval {1, 2, 3} is automatic, leaving only the condition that 3 - i does not equal s+1.

    lines 132–136

    uses Finset.mem_sdiff, Finset.mem_Icc, Finset.mem_singleton

      rw [Finset.mem_sdiff,Finset.mem_Icc,Finset.mem_singleton]
      constructor
      · exact fun h => h.2
      · intro h
        exact ⟨⟨by omega,by omega⟩,h⟩
  10. Conjugating profile_matrix by the row and column bijections equals canonical m c (s+1). automation

    Equality of the matrices is checked entry by entry across all 3×3 = 9 block combinations. In each block, substituting the row symbols and column forbidden sets reduces the matrix entry comparison to determining whether the row symbol belongs to the column set, which split_ifs and linear arithmetic resolve to match the block definition of canonical.

    lines 140–152

    uses Matrix.submatrix_apply, rows_left_symbol, rows_mid_symbol, rows_tail_symbol, sets_left, sets_mid, sets_tail, low_pair_mem

      ext x y
      rcases x with i | (i | i) <;> rcases y with j | (j | j)
      all_goals simp only [Matrix.submatrix_apply,profile_matrix,
        rows_left_symbol,rows_mid_symbol,rows_tail_symbol,
        sets_left,sets_mid,sets_tail,canonical,
        Matrix.fromBlocks_apply₁₁,Matrix.fromBlocks_apply₁₂,
        Matrix.fromBlocks_apply₂₁,Matrix.fromBlocks_apply₂₂,Matrix.of_apply,Matrix.zero_apply,
        head,tail,stair]
      all_goals split_ifs at *
      all_goals (try simp_rw [low_pair_mem] at *)
      all_goals (try simp_all only [Finset.mem_Icc,Finset.mem_union,
        Finset.mem_singleton,Finset.mem_sdiff,Finset.notMem_empty,Fin.ext_iff])
      all_goals try omega
  11. The permanent of profile_matrix m c (s+1) is 4.

    By permanent_equiv, the permanent of profile_matrix equals that of its submatrix under rows m and cols m. By profile_reindex, this submatrix is canonical m c (s+1), which has permanent 4 by canonical_perm.

    lines 156–157

    uses permanent_equiv, profile_reindex, canonical_perm

      rw [← permanent_equiv _ (rows m) (cols m),profile_reindex]
      exact canonical_perm m c s
  12. The top-row availability matrix has entry 0 when a symbol is present in that column, and 1 when absent.

    By definition, the availability matrix entry is 1 when no cell in column j has value i+1, and 0 otherwise. This condition is equivalent to i+1 not belonging to the column symbols set, which rewrites the entry to 0 if present and 1 if absent.

    lines 170–178

    uses mem_latin_column_symbols, ite_not

      have h : (∀ a : d.cells, a.val.2 = j.val → T a ≠ i.val+1) ↔
          i.val+1 ∉ latin_column_symbols d T j.val := by
        constructor
        · intro hP hmem
          obtain ⟨a,ha,hval⟩ := (mem_latin_column_symbols d T j.val (i.val+1)).mp hmem
          exact hP a ha hval
        · intro hP a ha hval
          exact hP ((mem_latin_column_symbols d T j.val (i.val+1)).mpr ⟨a,ha,hval⟩)
      simp only [latin_top_row_availability,h,ite_not]
  13. Column m+5 of shape D(m) has no cells, so its set of column symbols is empty.

    In the double-three-tail Young diagram of parameter m+5, every cell has column index strictly less than m+5. Hence, column m+5 contains no cells, and its image under the filling T is empty.

    lines 182–189

    uses Finset.eq_empty_iff_forall_notMem.mpr, mem_latin_column_symbols, lt_of_lt_of_le, max_le

      apply Finset.eq_empty_iff_forall_notMem.mpr
      intro x hx
      obtain ⟨a,ha,_⟩ := (mem_latin_column_symbols _ _ _ _).mp hx
      have hm := a.property
      simp only [D,latin_double_three_tail_shape,Finset.mem_filter,Finset.mem_product,Finset.mem_range] at hm
      have hb := hm.1.2
      have hb' : a.val.2 < m+5 := lt_of_lt_of_le hb (max_le le_rfl (by omega))
      omega
  14. Any filling satisfying the canonical column profile has its availability matrix equal to profile_matrix.

    Unpacking the profile hypothesis provides parameters c and s and the symbol sets for each column. A case split on column index j matches each column's symbols with profile_sets, using empty_column for the final column. Applying availability_entry then equates the availability matrix with profile_matrix m c (s+1).

    lines 194–223

    uses Finset.mem_Icc, empty_column, availability_entry

      obtain ⟨snat,hs,cnat,hc,hfirst,hmid,hpair,hlast⟩ := hp
      have hs' := Finset.mem_Icc.mp hs
      let c : Fin 3 := ⟨cnat,hc⟩
      let s : Fin 3 := ⟨snat-1,by omega⟩
      have hsnat : s.val+1 = snat := by dsimp [s]; omega
      have hk2 : m+5-2 = m+3 := by omega
      have hk1 : m+5-1 = m+4 := by omega
      simp only [hk2,hk1] at hfirst hmid hpair hlast
      rw [← hsnat] at hpair hlast
      refine ⟨c,s,?_⟩
      have hsets (j : Fin (m+6)) :
          latin_column_symbols (D m) T j.val = profile_sets m c (s.val+1) j := by
        by_cases h0 : j.val < 3
        · rw [profile_sets,if_pos h0]
          exact hfirst j.val h0
        · by_cases h1 : j.val < m+3
          · rw [profile_sets,if_neg h0,if_pos h1]
            exact hmid j.val (by omega) h1
          · by_cases h2 : j.val = m+3
            · rw [profile_sets,if_neg h0,if_neg h1,if_pos h2,h2]
              exact hpair
            · by_cases h3 : j.val = m+4
              · rw [profile_sets,if_neg h0,if_neg h1,if_neg h2,if_pos h3,h3]
                exact hlast
              · have hj : j.val = m+5 := by omega
                rw [profile_sets,if_neg h0,if_neg h1,if_neg h2,if_neg h3]
                rw [hj,empty_column]
      ext i j
      rw [availability_entry,hsets]
      rfl
  15. For any tableau of size k ≥ 5 with the canonical profile, the top-row availability permanent is 4.

    Writing k = m + 5 with m ≥ 0, availability_of_profile identifies the top-row availability matrix with profile_matrix m c (s+1), whose permanent is 4 by profile_permanent. The main theorem latin_double_three_tail_permanent_of_profile follows directly by calling this target result.

    lines 228–236

    uses availability_of_profile, profile_permanent, LatinTailProfilePermanent.target

      obtain ⟨m,rfl⟩ : ∃ m, k = m+5 := ⟨k-5,by omega⟩
      obtain ⟨c,s,heq⟩ := availability_of_profile m T hp
      change (latin_top_row_availability (D m) T (m+6)).permanent = 4
      rw [heq]
      exact profile_permanent m c s
    end LatinTailProfilePermanent
    
    theorem latin_double_three_tail_permanent_of_profile (k : ℕ) (hk : 5 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ) (hp : latin_double_three_tail_profile k T) : Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) = 4 := by
      exact LatinTailProfilePermanent.target k hk T hp
availability_of_profile
For any filling with the canonical column profile, the top-row availability matrix equals profile_matrix m c (s+1) for some parameters c, s in Fin 3.
availability_entry
The availability matrix entry at row i and column j is 0 if symbol i+1 appears in column j of the tableau, and 1 otherwise.
canonical_perm
The permanent of the canonical block upper-triangular matrix canonical m c (s+1) equals 4.
cols_left
The column equivalence maps an index i from the left block Fin 3 to i in Fin (m+6).
cols_mid
The column equivalence maps an index i from the middle block Fin m to 3+i in Fin (m+6).
cols_tail
The column equivalence maps an index i from the tail block Fin 3 to 3+m+i in Fin (m+6).
empty_column
Column m+5 of the double-three-tail shape has no cells, so its set of column symbols is empty.
Equiv.ext
Two equivalences between types are equal if they produce the same value on every input.
Equiv.equivCongr_apply_apply
Applying a conjugated equivalence ((e₁ ≃ e₂) σ) to e₁(x) yields e₂(σ(x)).
Equiv.equivCongr
Equivalences between two pairs of types induce an equivalence between their spaces of bijections.
Equiv.sum_comp
Summing a function over a finite type is invariant under precomposition with a permutation of the index type.
Equiv.symm_apply_apply
Applying the inverse of an equivalence to its image returns the original element.
Fin.ext_iff
Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Fin.ext
Two elements of Fin n are equal if their underlying natural number values are equal.
Finset.eq_empty_iff_forall_notMem.mpr
A finite set is empty if and only if no element belongs to it.
Finset.mem_Icc
An element belongs to the closed interval [a, b] if and only if a ≤ x ≤ b.
Finset.mem_sdiff
An element belongs to a set difference A \ B if and only if it is in A and not in B.
Finset.mem_singleton
An element belongs to a singleton set {a} if and only if it equals a.
Finset.mem_univ
Every element of a finite type belongs to the universal set Finset.univ.
Finset.prod_eq_zero
A product over a finite set is zero if at least one factor is zero.
Finset.sum_eq_single
If all terms in a finite sum except for one are zero, the sum equals that single term.
Finset.sum_lt_sum
If f ≤ g on a finite set and f < g strictly for at least one element, then the sum of f is strictly less than the sum of g.
Fintype.prod_equiv
A finite product is invariant under reindexing by an equivalence of index types.
Fintype.sum_equiv
A finite sum is invariant under reindexing by an equivalence of index types.
head_perm
The permanent of head c is 2 for any c in Fin 3.
ite_not
Negating the condition of an if-then-else expression swaps the then and else branches.
LatinTailProfilePermanent.target
The target lemma proving that the permanent of the top-row availability matrix is 4 for any tableau of size k ≥ 5 with the canonical profile.
low_pair_mem
For i, s in Fin 3, 3 - i belongs to {1, 2, 3} \ {s+1} if and only if 3 - i ≠ s+1.
lt_of_lt_of_le
Strict inequality is transitive with non-strict inequality: a < b and b ≤ c imply a < c.
matrix_permanent_from_blocks_zero_one_two_zero_two_one
The permanent of a block upper-triangular matrix with a zero lower-left block equals the product of the permanents of its two diagonal blocks.
max_le
If a ≤ c and b ≤ c, then max(a, b) ≤ c.
mem_latin_column_symbols
A symbol x is in the column symbols of column j if and only if some cell in column j has entry x.
Matrix.submatrix_apply
The (i, j) entry of the submatrix formed by row map r and column map c is A(r(i), c(j)).
perm_has_rise
Any non-identity permutation of Fin n has an index i strictly smaller than its image σ(i).
permanent_equiv
The permanent of a matrix is invariant under simultaneously permuting its rows and columns by bijections.
permanent_stair
The permanent of the staircase matrix (1 on and above the diagonal, 0 below) is 1.
profile_permanent
The permanent of profile_matrix m c (s+1) is 4.
profile_reindex
Conjugating profile_matrix by the row and column bijections yields canonical m c (s+1).
rows_left_symbol
The 1-based symbol corresponding to row index i in the left block Fin 3 is m + 6 - i.
rows_mid_symbol
The 1-based symbol corresponding to row index i in the middle block Fin m is m + 3 - i.
rows_tail_symbol
The 1-based symbol corresponding to row index i in the tail block Fin 3 is 3 - i.
rows_val
The row bijection maps an index x to m + 6 - (cols m x + 1).
sets_left
The profile forbidden set for a left column j in Fin 3 is {1, ..., m+3} ∪ {m+5} if j = c, and {1, ..., m+4} otherwise.
sets_mid
The profile forbidden set for a middle column j in Fin m is {1, ..., m+2-j}.
sets_tail
The profile forbidden set for a tail column j in Fin 3 is {1, 2, 3} \ {s} when j = 0, {s} when j = 1, and ∅ when j = 2.
tail_perm
The permanent of tail (s+1) is 2 for any s in Fin 3.

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

Lean’s trace was cut to the first 400 of 410 tactics.

open scoped BigOperatorsset_option maxHeartbeats 1000000set_option maxRecDepth 4000namespace LatinTailProfilePermanentprivate lemma permanent_equiv {α β : Type} [Fintype α] [DecidableEq α]    [Fintype β] [DecidableEq β] (A : Matrix β β ℕ) (r c : α ≃ β) :    (A.submatrix r c).permanent = A.permanent := by  unfold Matrix.permanent  refine Fintype.sum_equiv (Equiv.equivCongr c r) _ _ ?_  intro σ  refine Fintype.prod_equiv c _ _ ?_  intro i  simp only [Matrix.submatrix_apply,Equiv.equivCongr_apply_apply,Equiv.symm_apply_apply]private lemma perm_has_rise {n : ℕ} (σ : Equiv.Perm (Fin n)) (hne : σ ≠ 1) :    ∃ i, i.val < (σ i).val := by  by_contra h  push Not at h  have hex : ∃ i, σ i ≠ i := by    by_contra hh    push Not at hh    exact hne (by apply Equiv.ext; intro i; exact hh i)  obtain ⟨i,hi⟩ := hex  have hi' : (σ i).val ≠ i.val := fun he => hi (Fin.ext he)  have hi_le := h i  have hi_lt : (σ i).val < i.val := by omega  have hsum := Finset.sum_lt_sum (fun j (_ : j ∈ (Finset.univ : Finset (Fin n))) => h j)    ⟨i,Finset.mem_univ _,hi_lt⟩  have heq := Equiv.sum_comp σ (fun j : Fin n => j.val)  omegaprivate def stair (n : ℕ) : Matrix (Fin n) (Fin n) ℕ := fun i j => if i.val ≤ j.val then 1 else 0private lemma permanent_stair (n : ℕ) : (stair n).permanent = 1 := by  classical  unfold Matrix.permanent  have heq : (∑ σ : Equiv.Perm (Fin n), ∏ i : Fin n, stair n (σ i) i) =      ∏ i : Fin n, stair n ((1 : Equiv.Perm (Fin n)) i) i := by    apply Finset.sum_eq_single    · intro σ _ hσ      obtain ⟨i,hi⟩ := perm_has_rise σ hσ      apply Finset.prod_eq_zero (Finset.mem_univ i)      simp only [stair,show ¬ (σ i).val ≤ i.val by omega,ite_false]    · simp  simpa [stair] using heqprivate def head (c : Fin 3) : Matrix (Fin 3) (Fin 3) ℕ := fun i j =>  if i.val = 0 then 1 else if i.val = 1 then (if j ≠ c then 1 else 0)    else if j = c then 1 else 0private def tail (s : ℕ) : Matrix (Fin 3) (Fin 3) ℕ := fun i j =>  if j.val = 0 then (if 3 - i.val = s then 1 else 0)  else if j.val = 1 then (if 3 - i.val ≠ s then 1 else 0) else 1private lemma head_perm : ∀ c : Fin 3, (head c).permanent = 2 := by decideprivate lemma tail_perm : ∀ s : Fin 3, (tail (s.val+1)).permanent = 2 := by decideprivate abbrev I (m : ℕ) := Fin 3 ⊕ (Fin m ⊕ Fin 3)private def canonical (m : ℕ) (c : Fin 3) (s : ℕ) : Matrix (I m) (I m) ℕ :=  Matrix.fromBlocks (head c) (Matrix.of fun _ _ => 1) 0    (Matrix.fromBlocks (stair m) (Matrix.of fun _ _ => 1) 0 (tail s))private lemma canonical_perm (m : ℕ) (c s : Fin 3) : (canonical m c (s.val+1)).permanent = 4 := by  have hinner : (Matrix.fromBlocks (stair m) (Matrix.of fun _ _ => 1) 0 (tail (s.val+1))).permanent =      (stair m).permanent * (tail (s.val+1)).permanent :=    matrix_permanent_from_blocks_zero_one_two_zero_two_one _ _ _  calc    (canonical m c (s.val+1)).permanent = (head c).permanent *        (Matrix.fromBlocks (stair m) (Matrix.of fun _ _ => 1) 0 (tail (s.val+1))).permanent :=      matrix_permanent_from_blocks_zero_one_two_zero_two_one _ _ _    _ = 4 := by rw [hinner,head_perm,tail_perm,permanent_stair]private def cols (m : ℕ) : I m ≃ Fin (m+6) :=  ((Equiv.sumCongr (Equiv.refl (Fin 3)) (finSumFinEquiv : Fin m ⊕ Fin 3 ≃ Fin (m+3))).trans    (finSumFinEquiv : Fin 3 ⊕ Fin (m+3) ≃ Fin (3+(m+3)))).trans    (finCongr (by omega))private def rows (m : ℕ) : I m ≃ Fin (m+6) := (cols m).trans Fin.revPermprivate lemma cols_left (m : ℕ) (i : Fin 3) : (cols m (.inl i)).val = i.val := by rflprivate lemma cols_mid (m : ℕ) (i : Fin m) : (cols m (.inr (.inl i))).val = 3+i.val := by rflprivate lemma cols_tail (m : ℕ) (i : Fin 3) : (cols m (.inr (.inr i))).val = 3+(m+i.val) := by rflprivate lemma rows_val (m : ℕ) (x : I m) : (rows m x).val = m+6-((cols m x).val+1) := by rflend LatinTailProfilePermanentopen scoped BigOperatorsset_option maxHeartbeats 1000000set_option maxRecDepth 4000namespace LatinTailProfilePermanentprivate def profile_sets (m : ℕ) (c : Fin 3) (s : ℕ) (j : Fin (m+6)) : Finset ℕ :=  if j.val < 3 then    (if j.val = c.val then Finset.Icc 1 (m+3) ∪ {m+5} else Finset.Icc 1 (m+4))  else if j.val < m+3 then Finset.Icc 1 (m+5-j.val)  else if j.val = m+3 then Finset.Icc 1 3 \ {s}  else if j.val = m+4 then {s} else ∅private def profile_matrix (m : ℕ) (c : Fin 3) (s : ℕ) : Matrix (Fin (m+6)) (Fin (m+6)) ℕ :=  fun i j => if i.val+1 ∈ profile_sets m c s j then 0 else 1private lemma rows_left_symbol (m : ℕ) (i : Fin 3) :    (rows m (.inl i)).val+1 = m+6-i.val := by  rw [rows_val,cols_left]  omegaprivate lemma rows_mid_symbol (m : ℕ) (i : Fin m) :    (rows m (.inr (.inl i))).val+1 = m+3-i.val := by  rw [rows_val,cols_mid]  omegaprivate lemma rows_tail_symbol (m : ℕ) (i : Fin 3) :    (rows m (.inr (.inr i))).val+1 = 3-i.val := by  rw [rows_val,cols_tail]  omegaprivate lemma sets_left (m : ℕ) (c : Fin 3) (s : ℕ) (j : Fin 3) :    profile_sets m c s (cols m (.inl j)) =      if j = c then Finset.Icc 1 (m+3) ∪ {m+5} else Finset.Icc 1 (m+4) := by  simp only [profile_sets,cols_left,j.isLt,ite_true,Fin.ext_iff]private lemma sets_mid (m : ℕ) (c : Fin 3) (s : ℕ) (j : Fin m) :    profile_sets m c s (cols m (.inr (.inl j))) = Finset.Icc 1 (m+2-j.val) := by  have h0 : ¬ 3+j.val < 3 := by omega  have h1 : 3+j.val < m+3 := by omega  simp only [profile_sets,cols_mid,h0,h1,ite_false,ite_true]  congr 1  omegaprivate lemma sets_tail (m : ℕ) (c : Fin 3) (s : ℕ) (j : Fin 3) :    profile_sets m c s (cols m (.inr (.inr j))) =      if j.val = 0 then Finset.Icc 1 3 \ {s} else if j.val = 1 then {s} else ∅ := by  have h0 : ¬ 3+(m+j.val) < 3 := by omega  have h1 : ¬ 3+(m+j.val) < m+3 := by omega  have h2 : (3+(m+j.val) = m+3) ↔ j.val = 0 := by omega  have h3 : (3+(m+j.val) = m+4) ↔ j.val = 1 := by omega  simp only [profile_sets,cols_tail,h0,h1,h2,h3,ite_false]private lemma low_pair_mem (i s : Fin 3) :    3-i.val ∈ (Finset.Icc 1 3 \ {s.val+1}) ↔ 3-i.val ≠ s.val+1 := by  rw [Finset.mem_sdiff,Finset.mem_Icc,Finset.mem_singleton]  constructor  · exact fun h => h.2  · intro h    exact ⟨⟨by omega,by omega⟩,h⟩private lemma profile_reindex (m : ℕ) (c s : Fin 3) :    (profile_matrix m c (s.val+1)).submatrix (rows m) (cols m) = canonical m c (s.val+1) := by  ext x y  rcases x with i | (i | i) <;> rcases y with j | (j | j)  all_goals simp only [Matrix.submatrix_apply,profile_matrix,    rows_left_symbol,rows_mid_symbol,rows_tail_symbol,    sets_left,sets_mid,sets_tail,canonical,    Matrix.fromBlocks_apply₁₁,Matrix.fromBlocks_apply₁₂,    Matrix.fromBlocks_apply₂₁,Matrix.fromBlocks_apply₂₂,Matrix.of_apply,Matrix.zero_apply,    head,tail,stair]  all_goals split_ifs at *  all_goals (try simp_rw [low_pair_mem] at *)  all_goals (try simp_all only [Finset.mem_Icc,Finset.mem_union,    Finset.mem_singleton,Finset.mem_sdiff,Finset.notMem_empty,Fin.ext_iff])  all_goals try omegaprivate lemma profile_permanent (m : ℕ) (c s : Fin 3) :    (profile_matrix m c (s.val+1)).permanent = 4 := by  rw [← permanent_equiv _ (rows m) (cols m),profile_reindex]  exact canonical_perm m c send LatinTailProfilePermanentopen scoped BigOperatorsset_option maxHeartbeats 1000000set_option maxRecDepth 4000namespace LatinTailProfilePermanentprivate abbrev D (m : ℕ) := latin_double_three_tail_shape (m+5)private lemma availability_entry (d : YoungDiagram) (T : d.cells → ℕ) (w : ℕ) (i j : Fin w) :    latin_top_row_availability d T w i j =      if i.val+1 ∈ latin_column_symbols d T j.val then 0 else 1 := by  have h : (∀ a : d.cells, a.val.2 = j.val → T a ≠ i.val+1) ↔      i.val+1 ∉ latin_column_symbols d T j.val := by    constructor    · intro hP hmem      obtain ⟨a,ha,hval⟩ := (mem_latin_column_symbols d T j.val (i.val+1)).mp hmem      exact hP a ha hval    · intro hP a ha hval      exact hP ((mem_latin_column_symbols d T j.val (i.val+1)).mpr ⟨a,ha,hval⟩)  simp only [latin_top_row_availability,h,ite_not]private lemma empty_column (m : ℕ) (T : (D m).cells → ℕ) :    latin_column_symbols (D m) T (m+5) = ∅ := by  apply Finset.eq_empty_iff_forall_notMem.mpr  intro x hx  obtain ⟨a,ha,_⟩ := (mem_latin_column_symbols _ _ _ _).mp hx  have hm := a.property  simp only [D,latin_double_three_tail_shape,Finset.mem_filter,Finset.mem_product,Finset.mem_range] at hm  have hb := hm.1.2  have hb' : a.val.2 < m+5 := lt_of_lt_of_le hb (max_le le_rfl (by omega))  omegaprivate lemma availability_of_profile (m : ℕ) (T : (D m).cells → ℕ)    (hp : latin_double_three_tail_profile (m+5) T) :    ∃ c s : Fin 3, latin_top_row_availability (D m) T (m+6) = profile_matrix m c (s.val+1) := by  obtain ⟨snat,hs,cnat,hc,hfirst,hmid,hpair,hlast⟩ := hp  have hs' := Finset.mem_Icc.mp hs  let c : Fin 3 := ⟨cnat,hc⟩  let s : Fin 3 := ⟨snat-1,by omega⟩  have hsnat : s.val+1 = snat := by dsimp [s]; omega  have hk2 : m+5-2 = m+3 := by omega  have hk1 : m+5-1 = m+4 := by omega  simp only [hk2,hk1] at hfirst hmid hpair hlast  rw [← hsnat] at hpair hlast  refine ⟨c,s,?_⟩  have hsets (j : Fin (m+6)) :      latin_column_symbols (D m) T j.val = profile_sets m c (s.val+1) j := by    by_cases h0 : j.val < 3    · rw [profile_sets,if_pos h0]      exact hfirst j.val h0    · by_cases h1 : j.val < m+3      · rw [profile_sets,if_neg h0,if_pos h1]        exact hmid j.val (by omega) h1      · by_cases h2 : j.val = m+3        · rw [profile_sets,if_neg h0,if_neg h1,if_pos h2,h2]          exact hpair        · by_cases h3 : j.val = m+4          · rw [profile_sets,if_neg h0,if_neg h1,if_neg h2,if_pos h3,h3]            exact hlast          · have hj : j.val = m+5 := by omega            rw [profile_sets,if_neg h0,if_neg h1,if_neg h2,if_neg h3]            rw [hj,empty_column]  ext i j  rw [availability_entry,hsets]  rflprivate lemma target (k : ℕ) (hk : 5 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ)    (hp : latin_double_three_tail_profile k T) :    Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) = 4 := by  obtain ⟨m,rfl⟩ : ∃ m, k = m+5 := ⟨k-5,by omega⟩  obtain ⟨c,s,heq⟩ := availability_of_profile m T hp  change (latin_top_row_availability (D m) T (m+6)).permanent = 4  rw [heq]  exact profile_permanent m c send LatinTailProfilePermanenttheorem latin_double_three_tail_permanent_of_profile (k : ℕ) (hk : 5 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ) (hp : latin_double_three_tail_profile k T) : Matrix.permanent (latin_top_row_availability (latin_double_three_tail_shape k) T (k+1)) = 4 := by  exact LatinTailProfilePermanent.target k hk T hp
See it in the graphDiscuss this resultChallenge it