latin_double_three_tail_permanent_of_profile
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
- 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…
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.
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.
uses
Fintype.sum_equiv,Equiv.equivCongr,Fintype.prod_equiv,Matrix.submatrix_apply,Equiv.equivCongr_apply_apply,Equiv.symm_apply_applyunfold 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]
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.
uses
Equiv.ext,Fin.ext,Finset.sum_lt_sum,Finset.mem_univ,Equiv.sum_compby_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
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.
uses
Finset.sum_eq_single,perm_has_rise,Finset.prod_eq_zero,Finset.mem_univclassical 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
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.
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
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.
uses
matrix_permanent_from_blocks_zero_one_two_zero_two_one,head_perm,tail_perm,permanent_stairhave 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]
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.
(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
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.
uses
rows_val,cols_left,cols_mid,cols_tailrw [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
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.
uses
cols_left,cols_mid,cols_tail,Fin.ext_iffsimp 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]
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.
uses
Finset.mem_sdiff,Finset.mem_Icc,Finset.mem_singletonrw [Finset.mem_sdiff,Finset.mem_Icc,Finset.mem_singleton] constructor · exact fun h => h.2 · intro h exact ⟨⟨by omega,by omega⟩,h⟩
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.
uses
Matrix.submatrix_apply,rows_left_symbol,rows_mid_symbol,rows_tail_symbol,sets_left,sets_mid,sets_tail,low_pair_memext 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
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.
uses
permanent_equiv,profile_reindex,canonical_permrw [← permanent_equiv _ (rows m) (cols m),profile_reindex] exact canonical_perm m c s
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.
uses
mem_latin_column_symbols,ite_nothave 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]
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.
uses
Finset.eq_empty_iff_forall_notMem.mpr,mem_latin_column_symbols,lt_of_lt_of_le,max_leapply 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
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).
uses
Finset.mem_Icc,empty_column,availability_entryobtain ⟨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
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.
uses
availability_of_profile,profile_permanent,LatinTailProfilePermanent.targetobtain ⟨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.
- The permanents of the 3×3 head and tail blocks (head_perm and tail_perm) are computed by Lean's kernel reflection via decide, which exhaustively checks all 3! = 6 permutations.
- The reindexing equivalence (profile_reindex) proves matrix equality across all 9 block combinations using an automated case split (split_ifs) and integer linear arithmetic (omega).
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.
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