AFTD Auto-Formalizing Theoretical Domains

latin_double_three_tail_profile_succ

theoremverified

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
Used by 2

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.

  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.

    lines 13–59

      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
  2. 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.

    lines 60–63

    uses Ne.symm

      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)
  3. 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.

    lines 65–81

      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
  4. 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.

    lines 83–105

    uses Nat.strong_induction_on, le_total, max_eq_right, max_eq_left

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

    lines 106–124

    uses max_eq_right, max_eq_left, le_rfl

      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; omega
  6. 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.

    lines 128–132

    uses mem_latin_double_three_tail_shape

      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⟩
  7. 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).

    lines 136–137

    uses mem_latin_double_three_tail_shape, lt_of_lt_of_le, le_max_right

      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 _ _)⟩
  8. 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.

    lines 146–154

    uses latin_tableaux, Finset.mem_filter, Fintype.mem_piFinset, latin_double_three_tail_shape_rowLen_succ, latin_double_three_tail_profile_succ_lift_mem

      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 this
  9. 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).

    lines 160–180

    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⟩
  10. 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.

    lines 184–191

    uses mem_latin_column_symbols, Finset.notMem_empty, iff_false, mem_latin_double_three_tail_shape, max_le

      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)
      omega
  11. 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.

    lines 198–226

    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_mem

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

    lines 227–255

    uses Finset.mem_Icc, if_pos, Finset.mem_union, Finset.mem_singleton, not_or, not_and, if_neg, Finset.mem_sdiff, not_not

      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⟩
  13. 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.

    lines 256–261

    uses latin_double_three_tail_profile_succ_core

      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
  14. 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'.

    lines 262–279

    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_singleton

      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
  15. 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).

    lines 280–298

    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
  16. 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.

    lines 303–305

    uses latin_double_three_tail_profile_succ_step, latin_double_three_tail_profile_succ_restrict_mem

      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))
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.

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