latin_double_three_tail_profile_succ
Induction 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 column-symbol profile, then so does every Latin tableau of shape (k+1,k,...,4,3,3).
Statement
theorem latin_double_three_tail_profile_succ (k : ℕ) (hk : 5 ≤ k)
(ih : ∀ T ∈ latin_tableaux (latin_double_three_tail_shape k), latin_double_three_tail_profile k T) :
∀ T ∈ latin_tableaux (latin_double_three_tail_shape (k + 1)), latin_double_three_tail_profile (k + 1) T- Source
- Helper for latin_double_three_tail_profile_all (the open enumeration problem of https://arxiv.org/html/2610.29291v1, Conjecture 6.3): the induction step of its plan.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- 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_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_column_symbolsThe finite set of symbols appearing in column j of a fixed filling T of a Young diagram d.
- mem_latin_column_symbolsA symbol belongs to a column-symbol set exactly when a cell of that column has that value.
- 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_shape_rowLenThe row-length sanity formula for the staircase with two bottom rows of length three.
- 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.
- Used by 2
- latin_double_three_tail_profile_allEvery Latin tableau in the double-3-tail staircase family has the three canonical column-symbol profiles (nine profiles before permuting…
- latin_double_three_tail_count_stepThe number of tableaux of the next shape is the sum of availability permanents over all tableaux of the previous shape.
The proof, explained
To prove the induction step for the double-3-tail Latin tableau profile from k to k+1, we restrict any Latin tableau T of shape k+1 by dropping its top row, obtaining a valid Latin tableau of shape k that satisfies the induction hypothesis. The entries along the top row x(j) = T(0, j) are constrained by injectivity and the column symbols in the rows below. A core combinatorial lemma, proved via strong induction and column constraints, determines all top row entries and shows that the full tableau T satisfies the canonical column-symbol profile for shape k+1.
Among the first three columns, the two columns other than c take the values k and k+1.
For any column j < 3 distinct from c, hypothesis h0r ensures x(j) ≥ k, while x(j) ≤ k + 1, so x(j) ∈ {k, k + 1}. Case analysis on c ∈ {0, 1, 2} shows that the two other columns cannot take the same value by injectivity of x, so exactly one column c' takes k + 1 and the other takes k.
have hreg : ∃ c', c' < 3 ∧ c' ≠ c ∧ x c' = k + 1 ∧ ∀ j < 3, j ≠ c → j ≠ c' → x j = k := by have hb : ∀ j < 3, j ≠ c → x j = k ∨ x j = k + 1 := by intro j hj hjc have := h0r j hj hjc have := (hx j (by omega)).2 omega interval_cases c · rcases hb 1 (by omega) (by omega) with h1 | h1 · refine ⟨2, by omega, by omega, ?_, ?_⟩ · rcases hb 2 (by omega) (by omega) with h2 | h2 · exact absurd (hinj 1 (by omega) 2 (by omega) (h1.trans h2.symm)) (by omega) · exact h2 · intro j hj h0 h2; have : j = 1 := by omega subst this; exact h1 · refine ⟨1, by omega, by omega, h1, ?_⟩ intro j hj h0 h1'; have : j = 2 := by omega subst this rcases hb 2 (by omega) (by omega) with h2 | h2 · exact h2 · exact absurd (hinj 1 (by omega) 2 (by omega) (h1.trans h2.symm)) (by omega) · rcases hb 0 (by omega) (by omega) with h1 | h1 · refine ⟨2, by omega, by omega, ?_, ?_⟩ · rcases hb 2 (by omega) (by omega) with h2 | h2 · exact absurd (hinj 0 (by omega) 2 (by omega) (h1.trans h2.symm)) (by omega) · exact h2 · intro j hj h0 h2; have : j = 0 := by omega subst this; exact h1 · refine ⟨0, by omega, by omega, h1, ?_⟩ intro j hj h0 h1'; have : j = 2 := by omega subst this rcases hb 2 (by omega) (by omega) with h2 | h2 · exact h2 · exact absurd (hinj 0 (by omega) 2 (by omega) (h1.trans h2.symm)) (by omega) · rcases hb 0 (by omega) (by omega) with h1 | h1 · refine ⟨1, by omega, by omega, ?_, ?_⟩ · rcases hb 1 (by omega) (by omega) with h2 | h2 · exact absurd (hinj 0 (by omega) 1 (by omega) (h1.trans h2.symm)) (by omega) · exact h2 · intro j hj h0 h2; have : j = 0 := by omega subst this; exact h1 · refine ⟨0, by omega, by omega, h1, ?_⟩ intro j hj h0 h1'; have : j = 1 := by omega subst this rcases hb 1 (by omega) (by omega) with h2 | h2 · exact h2 · exact absurd (hinj 0 (by omega) 1 (by omega) (h1.trans h2.symm)) (by omega) obtain ⟨c', hc'3, hc'c, hc'v, hrest⟩ := hreg
The top entry of column c is x(c) = k - 1.
By hypothesis h0c, x(c) is either k - 1 or k + 1. Since column c' takes x(c') = k + 1 and c ≠ c', injectivity of x rules out x(c) = k + 1, leaving x(c) = k - 1.
uses
Ne.symmhave hcv : x c = k - 1 := by rcases h0c with h | h · exact h · exact absurd (hinj c (by omega) c' (by omega) (h.trans hc'v.symm)) (Ne.symm hc'c)
No column j ≥ 3 can have top entry x(j) ≥ k - 1.
Suppose j ≥ 3 and x(j) ≥ k - 1. Since x(j) ≤ k + 1, x(j) must be k - 1, k, or k + 1. But these three values are already taken by the first three columns: x(c) = k - 1, x(c') = k + 1, and the remaining column takes k. By injectivity of x, j would have to equal one of {0, 1, 2}, contradicting j ≥ 3.
have htop : ∀ j, 3 ≤ j → j ≤ k → k - 1 ≤ x j → False := by intro j hj3 hjk hv have hle := (hx j hjk).2 have : x j = x c ∨ x j = x c' ∨ ∃ i < 3, i ≠ c ∧ i ≠ c' ∧ x j = x i := by by_cases h1 : x j = k - 1 · left; omega by_cases h2 : x j = k + 1 · right; left; omega right; right have hxk : x j = k := by omega have : ∃ i < 3, i ≠ c ∧ i ≠ c' := ⟨3 - c - c', by omega, by omega, by omega⟩ obtain ⟨i, hi, hic, hic'⟩ := this exact ⟨i, hi, hic, hic', by rw [hxk, hrest i hi hic hic']⟩ rcases this with h | h | ⟨i, hi, -, -, h⟩ · have := hinj j hjk c (by omega) h; omega · have := hinj j hjk c' (by omega) h; omega · have := hinj j hjk i (by omega) h; omega
For all 3 ≤ j ≤ k, the top entry satisfies x(j) ≤ max(3, k + 1 - j).
We prove the upper bound by strong induction on j. If x(j) > max(3, k + 1 - j), then x(j) < k - 1 by the previous step, so setting i = k + 1 - x(j) gives 3 ≤ i < j. By the induction hypothesis on i, x(i) ≤ max(3, k + 1 - i) = x(j). But i < k - 2, so hypothesis hmid gives x(i) > k - i = x(j) - 1, forcing x(i) = x(j). This contradicts the injectivity of x since i < j.
uses
Nat.strong_induction_on,le_total,max_eq_right,max_eq_lefthave hub : ∀ j, 3 ≤ j → j ≤ k → x j ≤ max 3 (k + 1 - j) := by intro j induction j using Nat.strong_induction_on with | _ j ih => intro hj3 hjk by_contra hcon push_neg at hcon have hv := (hx j hjk).2 by_cases hbig : k - 1 ≤ x j · exact htop j hj3 hjk hbig · set i := k + 1 - x j with hi have hi3 : 3 ≤ i := by omega have hij : i < j := by rcases le_total 3 (k + 1 - j) with h | h · rw [max_eq_right h] at hcon; omega · rw [max_eq_left h] at hcon; omega have h1 := ih i hij hi3 (by omega) have hik2 : i < k - 2 := by omega have h2 := hmid i hi3 hik2 have : x i = x j := by rw [max_eq_right (by omega)] at h1; omega have := hinj i (by omega) j hjk this omega
The values of x on all remaining columns are completely determined, completing the core lemma.
For middle columns 3 ≤ j < k - 2, sandwiching between x(j) ≤ k + 1 - j and x(j) > k - j gives x(j) = k + 1 - j. At column k - 2, x(k - 2) ≤ 3 implies x(k - 2) = s by hypothesis hpair. The remaining values x(k - 1) and x(k) are bounded in {1, 2, 3}, and injectivity ensures x(k) ≠ s and x(k - 1) ≠ x(k).
uses
max_eq_right,max_eq_left,le_rflhave hmid' : ∀ j, 3 ≤ j → j < k - 2 → x j = k + 1 - j := by intro j hj3 hjk have h1 := hub j hj3 (by omega) have h2 := hmid j hj3 hjk rw [max_eq_right (by omega)] at h1 omega have hk2 : x (k - 2) = s := by have h1 := hub (k - 2) (by omega) (by omega) rw [max_eq_left (by omega)] at h1 exact hpair h1 have hk1 := hub (k - 1) (by omega) (by omega) have hk0 := hub k (by omega) le_rfl rw [max_eq_left (by omega)] at hk1 hk0 refine ⟨c', hc'3, hc'c, hc'v, hcv, hrest, hmid', hk2, (hx _ (by omega)).1, hk1, (hx _ le_rfl).1, hk0, ?_, ?_⟩ · intro h have := hinj k le_rfl (k - 2) (by omega) (h.trans hk2.symm); omega · intro h have := hinj (k - 1) (by omega) k le_rfl h; omega
Shifting the row index of a cell in shape k down by 1 yields a cell in shape k+1.
A pair (i, j) belongs to the double-3-tail shape of parameter k precisely when i < k - 1 and j < max(3, k - i). Under the shift (i, j) ↦ (i + 1, j), the row length condition (k + 1) - (i + 1) = k - i is preserved, so (i + 1, j) belongs to shape k + 1.
uses
mem_latin_double_three_tail_shapehave h := (mem_latin_double_three_tail_shape k c.1.1 c.1.2).mp c.2 apply (mem_latin_double_three_tail_shape (k + 1) (c.1.1 + 1) c.1.2).mpr have : k + 1 - (c.1.1 + 1) = k - c.1.1 := by omega rw [this] exact ⟨by omega, h.2⟩
Every position (0, j) for j < k+1 is a cell of shape k+1.
The row length of row 0 in shape k+1 is max(3, k+1) = k+1. Hence (0, j) satisfies the cell condition j < max(3, k + 1).
uses
mem_latin_double_three_tail_shape,lt_of_lt_of_le,le_max_rightapply (mem_latin_double_three_tail_shape (k + 1) 0 j).mpr exact ⟨by omega, lt_of_lt_of_le (by omega) (le_max_right _ _)⟩
The restriction of a Latin tableau of shape k+1 by dropping the top row is a valid Latin tableau of shape k.
Row length bounds are preserved because row i+1 of shape k+1 has the same length as row i of shape k by latin_double_three_tail_shape_rowLen_succ. Row injectivity and column injectivity are directly inherited from the original tableau T.
uses
latin_tableaux,Finset.mem_filter,Fintype.mem_piFinset,latin_double_three_tail_shape_rowLen_succ,latin_double_three_tail_profile_succ_lift_memsimp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT ⊢ obtain ⟨hb, hr, hc⟩ := hT refine ⟨fun c => ?_, fun c1 c2 h1 h2 => ?_, fun c1 c2 h1 h2 => ?_⟩ · have := hb ⟨(c.1.1 + 1, c.1.2), latin_double_three_tail_profile_succ_lift_mem k c⟩ rw [latin_double_three_tail_shape_rowLen_succ] at this exact this · exact hr ⟨_, latin_double_three_tail_profile_succ_lift_mem k c1⟩ ⟨_, latin_double_three_tail_profile_succ_lift_mem k c2⟩ (by simp [h1]) h2 · have := hc ⟨_, latin_double_three_tail_profile_succ_lift_mem k c1⟩ ⟨_, latin_double_three_tail_profile_succ_lift_mem k c2⟩ h1 h2 simpa using this
The column symbols of T in column j decompose into the top entry T(0, j) and the column symbols of the restricted tableau.
A cell in column j of shape k+1 either has row index 0 (giving entry T(0, j)) or row index i+1 (which corresponds to cell (i, j) in the restricted tableau of shape k).
uses
Finset.mem_insert,mem_latin_column_symbols,mem_latin_double_three_tail_shape,latin_double_three_tail_profile_succ_top_mem,latin_double_three_tail_profile_succ_lift_mem(latin_column_symbols (latin_double_three_tail_shape k) (latin_double_three_tail_profile_succ_restrict k T) j) := by ext x rw [Finset.mem_insert, mem_latin_column_symbols, mem_latin_column_symbols] constructor · rintro ⟨⟨⟨i, j'⟩, hc⟩, hj', hx⟩ simp only at hj' subst hj' cases i with | zero => left; exact hx.symm | succ i => right have hm : (i, j') ∈ (latin_double_three_tail_shape k).cells := by have h := (mem_latin_double_three_tail_shape (k + 1) (i + 1) j').mp hc apply (mem_latin_double_three_tail_shape k i j').mpr have : k + 1 - (i + 1) = k - i := by omega rw [this] at h exact ⟨by omega, h.2⟩ exact ⟨⟨(i, j'), hm⟩, rfl, hx⟩ · rintro (hx | ⟨c, hcj, hx⟩) · exact ⟨⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk hj⟩, rfl, hx.symm⟩ · exact ⟨⟨(c.1.1 + 1, c.1.2), latin_double_three_tail_profile_succ_lift_mem k c⟩, hcj, hx⟩
Column k of shape k contains no cells, so its column-symbol set is empty.
Any cell (i, j) in shape k must satisfy j < max(3, k - i) ≤ k, which is impossible for j = k.
uses
mem_latin_column_symbols,Finset.notMem_empty,iff_false,mem_latin_double_three_tail_shape,max_leext x simp only [mem_latin_column_symbols, Finset.notMem_empty, iff_false] rintro ⟨⟨⟨i, j⟩, hc⟩, hj, -⟩ simp only at hj subst hj have h := (mem_latin_double_three_tail_shape j i j).mp hc have : max 3 (j - i) ≤ j := max_le (by omega) (by omega) omega
The top row sequence x(j) = T(0, j) defines an injection into {1, ..., k+1} disjoint from the restricted column symbols.
Entries in row 0 are bounded by row length k+1, and row injectivity of T ensures x is injective on {0, ..., k}. Column injectivity of T ensures the top entry x(j) cannot appear in column j below row 0.
uses
latin_tableaux,Finset.mem_filter,Fintype.mem_piFinset,latin_double_three_tail_profile_succ_top_mem,dif_pos,latin_double_three_tail_shape_rowLen,if_pos,max_eq_right,Finset.mem_Icc,mem_latin_column_symbols,latin_double_three_tail_profile_succ_lift_memhave hT' := hT simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT' obtain ⟨hb, hr, hcl⟩ := hT' have hk1 : 1 ≤ k := by omega let x : ℕ → ℕ := fun j => if h : j < k + 1 then T ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk1 h⟩ else 0 have hxdef : ∀ j (h : j < k + 1), T ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk1 h⟩ = x j := by intro j h; simp only [x, dif_pos h] have hrow0 : (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) have hx : ∀ j ≤ k, 1 ≤ x j ∧ x j ≤ k + 1 := by intro j hj have := hb ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk1 (by omega)⟩ rw [hxdef j (by omega)] at this simp only [hrow0, Finset.mem_Icc] at this exact this have hinj : ∀ i ≤ k, ∀ j ≤ k, x i = x j → i = j := by intro i hi j hj h rw [← hxdef i (by omega), ← hxdef j (by omega)] at h exact hr ⟨(0, i), latin_double_three_tail_profile_succ_top_mem k i hk1 (by omega)⟩ ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk1 (by omega)⟩ rfl h have hcol : ∀ j ≤ k, x j ∉ latin_column_symbols (latin_double_three_tail_shape k) (latin_double_three_tail_profile_succ_restrict k T) j := by intro j hj hmem rw [mem_latin_column_symbols] at hmem obtain ⟨c, hcj, hcx⟩ := hmem rw [← hxdef j (by omega)] at hcx have := hcl ⟨_, latin_double_three_tail_profile_succ_lift_mem k c⟩ ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk1 (by omega)⟩ hcj hcx simp at this
The hypotheses of the core combinatorial lemma hold for x and the parameters of the restricted tableau.
From the known column profile of the restricted tableau, column c is missing only k-1 and k+1, while columns j < 3 distinct from c are missing only values ≥ k. Similarly, middle columns exclude 1, ..., k-j (forcing x(j) > k-j), and column k-2 excludes {1, 2, 3} \\ {s}.
uses
Finset.mem_Icc,if_pos,Finset.mem_union,Finset.mem_singleton,not_or,not_and,if_neg,Finset.mem_sdiff,not_notobtain ⟨s, hs, c, hc3, hfirst, hmid, hpair, hlast⟩ := hprof rw [Finset.mem_Icc] at hs have h0c : x c = k - 1 ∨ x c = k + 1 := by have h1 := hcol c (by omega) rw [hfirst c hc3, if_pos rfl] at h1 have h2 := hx c (by omega) simp only [Finset.mem_union, Finset.mem_Icc, Finset.mem_singleton, not_or, not_and] at h1 omega have h0r : ∀ j < 3, j ≠ c → k ≤ x j := by intro j hj hjc have h1 := hcol j (by omega) rw [hfirst j hj, if_neg hjc] at h1 have h2 := hx j (by omega) simp only [Finset.mem_Icc, not_and] at h1 omega have hmid0 : ∀ j, 3 ≤ j → j < k - 2 → k - j < x j := by intro j hj3 hjk have h1 := hcol j (by omega) rw [hmid j hj3 hjk] at h1 have h2 := hx j (by omega) simp only [Finset.mem_Icc, not_and] at h1 omega have hpair0 : x (k - 2) ≤ 3 → x (k - 2) = s := by intro h3 have h1 := hcol (k - 2) (by omega) rw [hpair] at h1 have h2 := hx (k - 2) (by omega) simp only [Finset.mem_sdiff, Finset.mem_Icc, Finset.mem_singleton, not_and, not_not] at h1 exact h1 ⟨h2.1, h3⟩
The core lemma determines all top row values, and x(k-1) ≠ s.
Applying latin_double_three_tail_profile_succ_core yields the column parameter c' and explicit values for x. In particular, x(k-2) = s, which by injectivity implies x(k-1) ≠ s.
uses
latin_double_three_tail_profile_succ_coreobtain ⟨c', hc'3, hc'c, hc'v, hcv, hrest, hmid', hk2, h1a, h1b, h0a, h0b, hks, hk10⟩ := latin_double_three_tail_profile_succ_core k s c hk hc3 x hx hinj h0c h0r hmid0 hpair0 have hk1s : x (k - 1) ≠ s := by intro h have := hinj (k - 1) (by omega) (k - 2) (by omega) (h.trans hk2.symm) omega
The column symbols of T in the first three columns satisfy the profile conditions for shape k+1.
Inserting the top entries into the restricted column sets shows that column c' (receiving k+1) has symbol set {1, ..., k-1} ∪ {k+1}, column c (receiving k-1) has symbol set {1, ..., k-1}, and the third column (receiving k) has symbol set {1, ..., k}, matching the profile definition with distinguished column c'.
uses
latin_double_three_tail_profile,Finset.mem_Icc.mpr,latin_double_three_tail_profile_succ_col_succ,if_pos,if_neg,Ne.symm,Finset.mem_insert,Finset.mem_union,Finset.mem_Icc,Finset.mem_singletonunfold latin_double_three_tail_profile refine ⟨x k, Finset.mem_Icc.mpr ⟨h0a, h0b⟩, c', hc'3, ?_, ?_, ?_, ?_⟩ · intro j hj rw [latin_double_three_tail_profile_succ_col_succ k j hk1 (by omega), hxdef j (by omega), hfirst j hj] by_cases hjc : j = c · subst hjc rw [if_pos rfl, if_neg (Ne.symm hc'c), hcv] ext v; simp only [Finset.mem_insert, Finset.mem_union, Finset.mem_Icc, Finset.mem_singleton] omega · rw [if_neg hjc] by_cases hjc' : j = c' · subst hjc' rw [if_pos rfl, hc'v] ext v; simp only [Finset.mem_insert, Finset.mem_union, Finset.mem_Icc, Finset.mem_singleton] omega · rw [if_neg hjc', hrest j hj hjc hjc'] ext v; simp only [Finset.mem_insert, Finset.mem_Icc] omega
The column symbols of T in all remaining columns satisfy the profile conditions for shape k+1.
For 3 ≤ j < k-1, inserting x(j) = k+1-j extends {1, ..., k-j} to {1, ..., k+1-j}. At column k-1, inserting x(k-1) into {s} yields {1, 2, 3} \\ {x(k)}. At column k, inserting x(k) into the empty set gives {x(k)}, completing the profile with new tail parameter s' = x(k).
uses
latin_double_three_tail_profile_succ_col_succ,Finset.mem_insert,Finset.mem_Icc,Finset.mem_sdiff,Finset.mem_singleton,latin_double_three_tail_profile_succ_col_empty· intro j hj3 hjk rw [latin_double_three_tail_profile_succ_col_succ k j hk1 (by omega), hxdef j (by omega)] by_cases hjk2 : j < k - 2 · rw [hmid j hj3 hjk2, hmid' j hj3 hjk2] ext v; simp only [Finset.mem_insert, Finset.mem_Icc] omega · have hj : j = k - 2 := by omega subst hj rw [hpair, hk2] ext v; simp only [Finset.mem_insert, Finset.mem_sdiff, Finset.mem_Icc, Finset.mem_singleton] by_cases hv : v = s <;> omega · have e : k + 1 - 2 = k - 1 := by omega rw [e, latin_double_three_tail_profile_succ_col_succ k (k - 1) hk1 (by omega), hxdef (k - 1) (by omega), hlast] ext v; simp only [Finset.mem_insert, Finset.mem_sdiff, Finset.mem_Icc, Finset.mem_singleton] by_cases hv : v = x k <;> omega · have e : k + 1 - 1 = k := by omega rw [e, latin_double_three_tail_profile_succ_col_succ k k hk1 (by omega), hxdef k (by omega), latin_double_three_tail_profile_succ_col_empty k (by omega)] rfl
Every Latin tableau of shape k+1 has the double-3-tail profile, completing the induction step.
Given T of shape k+1, its restriction to shape k is a valid Latin tableau by latin_double_three_tail_profile_succ_restrict_mem, so by induction hypothesis ih it has profile k. Applying latin_double_three_tail_profile_succ_step then establishes profile k+1 for T.
uses
latin_double_three_tail_profile_succ_step,latin_double_three_tail_profile_succ_restrict_memintro T hT exact latin_double_three_tail_profile_succ_step k hk T hT (ih _ (latin_double_three_tail_profile_succ_restrict_mem k T hT))
not_or- De Morgan's law for disjunction: ¬(p ∨ q) ↔ ¬p ∧ ¬q.
not_and- Negation of conjunction: ¬(a ∧ b) ↔ a → ¬b.
not_not- Double negation elimination: ¬¬a ↔ a.
Ne.symm- Symmetry of inequality: if a ≠ b then b ≠ a.
Nat.strong_induction_on- Strong induction on ℕ: to prove P(n) for all n, it suffices to prove P(n) assuming P(m) for all m < n.
le_total- Totality of linear order: for any a and b, a ≤ b or b ≤ a.
max_eq_right- If a ≤ b, then max a b = b.
max_eq_left- If b ≤ a, then max a b = a.
le_rfl- Reflexivity of preorder: a ≤ a.
lt_of_lt_of_le- Transitivity of strict and non-strict inequality: if a < b and b ≤ c, then a < c.
le_max_right- In a linear order, b ≤ max a b.
max_le- If a ≤ c and b ≤ c, then max a b ≤ c.
Finset.mem_filter- Membership in a filtered finite set: x ∈ s.filter p ↔ x ∈ s ∧ p x.
Fintype.mem_piFinset- Membership in a product finite set of functions: f ∈ Fintype.piFinset t ↔ ∀ a, f a ∈ t a.
Finset.mem_insert- Membership in an inserted finite set: a ∈ insert b s ↔ a = b ∨ a ∈ s.
Finset.mem_Icc- Membership in a closed interval: x ∈ Finset.Icc a b ↔ a ≤ x ∧ x ≤ b.
Finset.mem_Icc.mpr- If a ≤ x and x ≤ b, then x belongs to the closed interval Finset.Icc a b.
Finset.mem_sdiff- Membership in a set difference: a ∈ s \\ t ↔ a ∈ s ∧ a ∉ t.
Finset.mem_union- Membership in a union: a ∈ s ∪ t ↔ a ∈ s ∨ a ∈ t.
Finset.mem_singleton- Membership in a singleton set: b ∈ {a} ↔ b = a.
Finset.notMem_empty- The empty set has no elements: a ∉ ∅.
iff_false- Equivalence to False simplifies to negation: (p ↔ False) = ¬p.
dif_pos- Evaluation of dependent if-then-else when the condition is true: dite c t e = t hc.
if_pos- If condition c is true, then (if c then t else e) = t.
if_neg- If condition c is false, then (if c then t else e) = e.
mem_latin_double_three_tail_shape- Characterization of cells: (i, j) belongs to the double-3-tail shape of parameter k if and only if i < k - 1 and j < max 3 (k - i).
latin_double_three_tail_shape_rowLen- Row length of the double-3-tail shape: row i has length max 3 (k - i) for i < k - 1, and 0 otherwise.
latin_double_three_tail_shape_rowLen_succ- Row length of shifted rows: row i+1 in shape k+1 has the same length as row i in shape k.
latin_tableaux- Definition of Latin tableaux of a Young diagram: assignments of values bounded by row length that are injective on each row and each column.
mem_latin_column_symbols- Characterization of column symbols: x ∈ latin_column_symbols d T j if and only if some cell in column j has entry x.
latin_double_three_tail_profile- The canonical column-symbol profile property for a Latin tableau of double-3-tail shape of parameter k.
latin_double_three_tail_profile_succ_core- Core combinatorial lemma: from the constraints on the top row of the tableau, determines all top row values and column profiles.
latin_double_three_tail_profile_succ_lift_mem- Cell lifting: if c is a cell of shape k, then shifting its row index down by 1 yields a cell of shape k+1.
latin_double_three_tail_profile_succ_top_mem- The top-row cell (0, j) belongs to shape k+1 for any j < k+1.
latin_double_three_tail_profile_succ_restrict_mem- Dropping the top row of a Latin tableau of shape k+1 yields a valid Latin tableau of shape k.
latin_double_three_tail_profile_succ_col_succ- The column symbols of shape k+1 in column j are obtained by inserting the top row entry T(0, j) into the column symbols of the restricted tableau.
latin_double_three_tail_profile_succ_col_empty- Column k in shape k contains no cells, so its set of column symbols is empty.
latin_double_three_tail_profile_succ_step- Step lemma: if the restricted tableau has profile k, then the full tableau has profile k+1.
- The subtableau is obtained by shifting row indices i ↦ i + 1, which formally corresponds to restricting along a diagram embedding.
- Case distinctions on small column indices (c ∈ {0, 1, 2}) and interval bounds are handled through linear integer arithmetic via 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 408 tactics.
theorem latin_double_three_tail_profile_succ_core (k s c : ℕ) (hk : 5 ≤ k) (hc : c < 3) (x : ℕ → ℕ) (hx : ∀ j ≤ k, 1 ≤ x j ∧ x j ≤ k + 1) (hinj : ∀ i ≤ k, ∀ j ≤ k, x i = x j → i = j) (h0c : x c = k - 1 ∨ x c = k + 1) (h0r : ∀ j < 3, j ≠ c → k ≤ x j) (hmid : ∀ j, 3 ≤ j → j < k - 2 → k - j < x j) (hpair : x (k - 2) ≤ 3 → x (k - 2) = s) : ∃ c', c' < 3 ∧ c' ≠ c ∧ x c' = k + 1 ∧ x c = k - 1 ∧ (∀ j < 3, j ≠ c → j ≠ c' → x j = k) ∧ (∀ j, 3 ≤ j → j < k - 2 → x j = k + 1 - j) ∧ x (k - 2) = s ∧ 1 ≤ x (k - 1) ∧ x (k - 1) ≤ 3 ∧ 1 ≤ x k ∧ x k ≤ 3 ∧ x k ≠ s ∧ x (k - 1) ≠ x k := by -- the two regular columns take k and k+1 have hreg : ∃ c', c' < 3 ∧ c' ≠ c ∧ x c' = k + 1 ∧ ∀ j < 3, j ≠ c → j ≠ c' → x j = k := by have hb : ∀ j < 3, j ≠ c → x j = k ∨ x j = k + 1 := by intro j hj hjc have := h0r j hj hjc have := (hx j (by omega)).2 omega interval_cases c · rcases hb 1 (by omega) (by omega) with h1 | h1 · refine ⟨2, by omega, by omega, ?_, ?_⟩ · rcases hb 2 (by omega) (by omega) with h2 | h2 · exact absurd (hinj 1 (by omega) 2 (by omega) (h1.trans h2.symm)) (by omega) · exact h2 · intro j hj h0 h2; have : j = 1 := by omega subst this; exact h1 · refine ⟨1, by omega, by omega, h1, ?_⟩ intro j hj h0 h1'; have : j = 2 := by omega subst this rcases hb 2 (by omega) (by omega) with h2 | h2 · exact h2 · exact absurd (hinj 1 (by omega) 2 (by omega) (h1.trans h2.symm)) (by omega) · rcases hb 0 (by omega) (by omega) with h1 | h1 · refine ⟨2, by omega, by omega, ?_, ?_⟩ · rcases hb 2 (by omega) (by omega) with h2 | h2 · exact absurd (hinj 0 (by omega) 2 (by omega) (h1.trans h2.symm)) (by omega) · exact h2 · intro j hj h0 h2; have : j = 0 := by omega subst this; exact h1 · refine ⟨0, by omega, by omega, h1, ?_⟩ intro j hj h0 h1'; have : j = 2 := by omega subst this rcases hb 2 (by omega) (by omega) with h2 | h2 · exact h2 · exact absurd (hinj 0 (by omega) 2 (by omega) (h1.trans h2.symm)) (by omega) · rcases hb 0 (by omega) (by omega) with h1 | h1 · refine ⟨1, by omega, by omega, ?_, ?_⟩ · rcases hb 1 (by omega) (by omega) with h2 | h2 · exact absurd (hinj 0 (by omega) 1 (by omega) (h1.trans h2.symm)) (by omega) · exact h2 · intro j hj h0 h2; have : j = 0 := by omega subst this; exact h1 · refine ⟨0, by omega, by omega, h1, ?_⟩ intro j hj h0 h1'; have : j = 1 := by omega subst this rcases hb 1 (by omega) (by omega) with h2 | h2 · exact h2 · exact absurd (hinj 0 (by omega) 1 (by omega) (h1.trans h2.symm)) (by omega) obtain ⟨c', hc'3, hc'c, hc'v, hrest⟩ := hreg have hcv : x c = k - 1 := by rcases h0c with h | h · exact h · exact absurd (hinj c (by omega) c' (by omega) (h.trans hc'v.symm)) (Ne.symm hc'c) -- values ≥ k-1 are taken by the first three columns have htop : ∀ j, 3 ≤ j → j ≤ k → k - 1 ≤ x j → False := by intro j hj3 hjk hv have hle := (hx j hjk).2 have : x j = x c ∨ x j = x c' ∨ ∃ i < 3, i ≠ c ∧ i ≠ c' ∧ x j = x i := by by_cases h1 : x j = k - 1 · left; omega by_cases h2 : x j = k + 1 · right; left; omega right; right have hxk : x j = k := by omega have : ∃ i < 3, i ≠ c ∧ i ≠ c' := ⟨3 - c - c', by omega, by omega, by omega⟩ obtain ⟨i, hi, hic, hic'⟩ := this exact ⟨i, hi, hic, hic', by rw [hxk, hrest i hi hic hic']⟩ rcases this with h | h | ⟨i, hi, -, -, h⟩ · have := hinj j hjk c (by omega) h; omega · have := hinj j hjk c' (by omega) h; omega · have := hinj j hjk i (by omega) h; omega -- upper bound by strong induction have hub : ∀ j, 3 ≤ j → j ≤ k → x j ≤ max 3 (k + 1 - j) := by intro j induction j using Nat.strong_induction_on with | _ j ih => intro hj3 hjk by_contra hcon push_neg at hcon have hv := (hx j hjk).2 by_cases hbig : k - 1 ≤ x j · exact htop j hj3 hjk hbig · set i := k + 1 - x j with hi have hi3 : 3 ≤ i := by omega have hij : i < j := by rcases le_total 3 (k + 1 - j) with h | h · rw [max_eq_right h] at hcon; omega · rw [max_eq_left h] at hcon; omega have h1 := ih i hij hi3 (by omega) have hik2 : i < k - 2 := by omega have h2 := hmid i hi3 hik2 have : x i = x j := by rw [max_eq_right (by omega)] at h1; omega have := hinj i (by omega) j hjk this omega have hmid' : ∀ j, 3 ≤ j → j < k - 2 → x j = k + 1 - j := by intro j hj3 hjk have h1 := hub j hj3 (by omega) have h2 := hmid j hj3 hjk rw [max_eq_right (by omega)] at h1 omega have hk2 : x (k - 2) = s := by have h1 := hub (k - 2) (by omega) (by omega) rw [max_eq_left (by omega)] at h1 exact hpair h1 have hk1 := hub (k - 1) (by omega) (by omega) have hk0 := hub k (by omega) le_rfl rw [max_eq_left (by omega)] at hk1 hk0 refine ⟨c', hc'3, hc'c, hc'v, hcv, hrest, hmid', hk2, (hx _ (by omega)).1, hk1, (hx _ le_rfl).1, hk0, ?_, ?_⟩ · intro h have := hinj k le_rfl (k - 2) (by omega) (h.trans hk2.symm); omega · intro h have := hinj (k - 1) (by omega) k le_rfl h; omegatheorem latin_double_three_tail_profile_succ_lift_mem (k : ℕ) (c : (latin_double_three_tail_shape k).cells) : (c.1.1 + 1, c.1.2) ∈ (latin_double_three_tail_shape (k + 1)).cells := by have h := (mem_latin_double_three_tail_shape k c.1.1 c.1.2).mp c.2 apply (mem_latin_double_three_tail_shape (k + 1) (c.1.1 + 1) c.1.2).mpr have : k + 1 - (c.1.1 + 1) = k - c.1.1 := by omega rw [this] exact ⟨by omega, h.2⟩theorem latin_double_three_tail_profile_succ_top_mem (k j : ℕ) (hk : 1 ≤ k) (hj : j < k + 1) : (0, j) ∈ (latin_double_three_tail_shape (k + 1)).cells := by apply (mem_latin_double_three_tail_shape (k + 1) 0 j).mpr exact ⟨by omega, lt_of_lt_of_le (by omega) (le_max_right _ _)⟩def latin_double_three_tail_profile_succ_restrict (k : ℕ) (T : (latin_double_three_tail_shape (k + 1)).cells → ℕ) : (latin_double_three_tail_shape k).cells → ℕ := fun c => T ⟨(c.1.1 + 1, c.1.2), latin_double_three_tail_profile_succ_lift_mem k c⟩theorem latin_double_three_tail_profile_succ_restrict_mem (k : ℕ) (T : (latin_double_three_tail_shape (k + 1)).cells → ℕ) (hT : T ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) : latin_double_three_tail_profile_succ_restrict k T ∈ latin_tableaux (latin_double_three_tail_shape k) := by simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT ⊢ obtain ⟨hb, hr, hc⟩ := hT refine ⟨fun c => ?_, fun c1 c2 h1 h2 => ?_, fun c1 c2 h1 h2 => ?_⟩ · have := hb ⟨(c.1.1 + 1, c.1.2), latin_double_three_tail_profile_succ_lift_mem k c⟩ rw [latin_double_three_tail_shape_rowLen_succ] at this exact this · exact hr ⟨_, latin_double_three_tail_profile_succ_lift_mem k c1⟩ ⟨_, latin_double_three_tail_profile_succ_lift_mem k c2⟩ (by simp [h1]) h2 · have := hc ⟨_, latin_double_three_tail_profile_succ_lift_mem k c1⟩ ⟨_, latin_double_three_tail_profile_succ_lift_mem k c2⟩ h1 h2 simpa using thistheorem latin_double_three_tail_profile_succ_col_succ (k j : ℕ) (hk : 1 ≤ k) (hj : j < k + 1) (T : (latin_double_three_tail_shape (k + 1)).cells → ℕ) : latin_column_symbols (latin_double_three_tail_shape (k + 1)) T j = insert (T ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk hj⟩) (latin_column_symbols (latin_double_three_tail_shape k) (latin_double_three_tail_profile_succ_restrict k T) j) := by ext x rw [Finset.mem_insert, mem_latin_column_symbols, mem_latin_column_symbols] constructor · rintro ⟨⟨⟨i, j'⟩, hc⟩, hj', hx⟩ simp only at hj' subst hj' cases i with | zero => left; exact hx.symm | succ i => right have hm : (i, j') ∈ (latin_double_three_tail_shape k).cells := by have h := (mem_latin_double_three_tail_shape (k + 1) (i + 1) j').mp hc apply (mem_latin_double_three_tail_shape k i j').mpr have : k + 1 - (i + 1) = k - i := by omega rw [this] at h exact ⟨by omega, h.2⟩ exact ⟨⟨(i, j'), hm⟩, rfl, hx⟩ · rintro (hx | ⟨c, hcj, hx⟩) · exact ⟨⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk hj⟩, rfl, hx.symm⟩ · exact ⟨⟨(c.1.1 + 1, c.1.2), latin_double_three_tail_profile_succ_lift_mem k c⟩, hcj, hx⟩theorem latin_double_three_tail_profile_succ_col_empty (k : ℕ) (hk : 3 ≤ k) (T : (latin_double_three_tail_shape k).cells → ℕ) : latin_column_symbols (latin_double_three_tail_shape k) T k = ∅ := by ext x simp only [mem_latin_column_symbols, Finset.notMem_empty, iff_false] rintro ⟨⟨⟨i, j⟩, hc⟩, hj, -⟩ simp only at hj subst hj have h := (mem_latin_double_three_tail_shape j i j).mp hc have : max 3 (j - i) ≤ j := max_le (by omega) (by omega) omegatheorem latin_double_three_tail_profile_succ_step (k : ℕ) (hk : 5 ≤ k) (T : (latin_double_three_tail_shape (k + 1)).cells → ℕ) (hT : T ∈ latin_tableaux (latin_double_three_tail_shape (k + 1))) (hprof : latin_double_three_tail_profile k (latin_double_three_tail_profile_succ_restrict k T)) : latin_double_three_tail_profile (k + 1) T := by have hT' := hT simp only [latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset] at hT' obtain ⟨hb, hr, hcl⟩ := hT' have hk1 : 1 ≤ k := by omega let x : ℕ → ℕ := fun j => if h : j < k + 1 then T ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk1 h⟩ else 0 have hxdef : ∀ j (h : j < k + 1), T ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk1 h⟩ = x j := by intro j h; simp only [x, dif_pos h] have hrow0 : (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) have hx : ∀ j ≤ k, 1 ≤ x j ∧ x j ≤ k + 1 := by intro j hj have := hb ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk1 (by omega)⟩ rw [hxdef j (by omega)] at this simp only [hrow0, Finset.mem_Icc] at this exact this have hinj : ∀ i ≤ k, ∀ j ≤ k, x i = x j → i = j := by intro i hi j hj h rw [← hxdef i (by omega), ← hxdef j (by omega)] at h exact hr ⟨(0, i), latin_double_three_tail_profile_succ_top_mem k i hk1 (by omega)⟩ ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk1 (by omega)⟩ rfl h have hcol : ∀ j ≤ k, x j ∉ latin_column_symbols (latin_double_three_tail_shape k) (latin_double_three_tail_profile_succ_restrict k T) j := by intro j hj hmem rw [mem_latin_column_symbols] at hmem obtain ⟨c, hcj, hcx⟩ := hmem rw [← hxdef j (by omega)] at hcx have := hcl ⟨_, latin_double_three_tail_profile_succ_lift_mem k c⟩ ⟨(0, j), latin_double_three_tail_profile_succ_top_mem k j hk1 (by omega)⟩ hcj hcx simp at this obtain ⟨s, hs, c, hc3, hfirst, hmid, hpair, hlast⟩ := hprof rw [Finset.mem_Icc] at hs have h0c : x c = k - 1 ∨ x c = k + 1 := by have h1 := hcol c (by omega) rw [hfirst c hc3, if_pos rfl] at h1 have h2 := hx c (by omega) simp only [Finset.mem_union, Finset.mem_Icc, Finset.mem_singleton, not_or, not_and] at h1 omega have h0r : ∀ j < 3, j ≠ c → k ≤ x j := by intro j hj hjc have h1 := hcol j (by omega) rw [hfirst j hj, if_neg hjc] at h1 have h2 := hx j (by omega) simp only [Finset.mem_Icc, not_and] at h1 omega have hmid0 : ∀ j, 3 ≤ j → j < k - 2 → k - j < x j := by intro j hj3 hjk have h1 := hcol j (by omega) rw [hmid j hj3 hjk] at h1 have h2 := hx j (by omega) simp only [Finset.mem_Icc, not_and] at h1 omega have hpair0 : x (k - 2) ≤ 3 → x (k - 2) = s := by intro h3 have h1 := hcol (k - 2) (by omega) rw [hpair] at h1 have h2 := hx (k - 2) (by omega) simp only [Finset.mem_sdiff, Finset.mem_Icc, Finset.mem_singleton, not_and, not_not] at h1 exact h1 ⟨h2.1, h3⟩ obtain ⟨c', hc'3, hc'c, hc'v, hcv, hrest, hmid', hk2, h1a, h1b, h0a, h0b, hks, hk10⟩ := latin_double_three_tail_profile_succ_core k s c hk hc3 x hx hinj h0c h0r hmid0 hpair0 have hk1s : x (k - 1) ≠ s := by intro h have := hinj (k - 1) (by omega) (k - 2) (by omega) (h.trans hk2.symm) omega unfold latin_double_three_tail_profile refine ⟨x k, Finset.mem_Icc.mpr ⟨h0a, h0b⟩, c', hc'3, ?_, ?_, ?_, ?_⟩ · intro j hj rw [latin_double_three_tail_profile_succ_col_succ k j hk1 (by omega), hxdef j (by omega), hfirst j hj] by_cases hjc : j = c · subst hjc rw [if_pos rfl, if_neg (Ne.symm hc'c), hcv] ext v; simp only [Finset.mem_insert, Finset.mem_union, Finset.mem_Icc, Finset.mem_singleton] omega · rw [if_neg hjc] by_cases hjc' : j = c' · subst hjc' rw [if_pos rfl, hc'v] ext v; simp only [Finset.mem_insert, Finset.mem_union, Finset.mem_Icc, Finset.mem_singleton] omega · rw [if_neg hjc', hrest j hj hjc hjc'] ext v; simp only [Finset.mem_insert, Finset.mem_Icc] omega · intro j hj3 hjk rw [latin_double_three_tail_profile_succ_col_succ k j hk1 (by omega), hxdef j (by omega)] by_cases hjk2 : j < k - 2 · rw [hmid j hj3 hjk2, hmid' j hj3 hjk2] ext v; simp only [Finset.mem_insert, Finset.mem_Icc] omega · have hj : j = k - 2 := by omega subst hj rw [hpair, hk2] ext v; simp only [Finset.mem_insert, Finset.mem_sdiff, Finset.mem_Icc, Finset.mem_singleton] by_cases hv : v = s <;> omega · have e : k + 1 - 2 = k - 1 := by omega rw [e, latin_double_three_tail_profile_succ_col_succ k (k - 1) hk1 (by omega), hxdef (k - 1) (by omega), hlast] ext v; simp only [Finset.mem_insert, Finset.mem_sdiff, Finset.mem_Icc, Finset.mem_singleton] by_cases hv : v = x k <;> omega · have e : k + 1 - 1 = k := by omega rw [e, latin_double_three_tail_profile_succ_col_succ k k hk1 (by omega), hxdef k (by omega), latin_double_three_tail_profile_succ_col_empty k (by omega)] rfltheorem latin_double_three_tail_profile_succ (k : ℕ) (hk : 5 ≤ k) (ih : ∀ T ∈ latin_tableaux (latin_double_three_tail_shape k), latin_double_three_tail_profile k T) : ∀ T ∈ latin_tableaux (latin_double_three_tail_shape (k + 1)), latin_double_three_tail_profile (k + 1) T := by intro T hT exact latin_double_three_tail_profile_succ_step k hk T hT (ih _ (latin_double_three_tail_profile_succ_restrict_mem k T hT))