AFTD Auto-Formalizing Theoretical Domains

latin_double_three_tail_shape_rowLen

theoremverified

The row-length sanity formula for the staircase with two bottom rows of length three.

Statement

theorem latin_double_three_tail_shape_rowLen (k i : ℕ) :
    (latin_double_three_tail_shape k).rowLen i =
      if i < k - 1 then max 3 (k - i) else 0
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
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 6

The proof, explained

The row length formula is established by antisymmetry (le_antisymm), proving upper and lower bounds between the row length and the piecewise expression V = if i < k - 1 then max 3 (k - i) else 0. Both directions argue by contradiction using the characterization that a cell (i, j) belongs to a Young diagram if and only if j is strictly less than rowLen i. For the upper bound, assuming rowLen i > V places (i, V) in the diagram, contradicting its explicit definition; for the lower bound, the cell (i, rowLen i) cannot lie in the diagram, forcing V ≤ rowLen i.

  1. It suffices to show that the row length (latin_double_three_tail_shape k).rowLen i is both bounded above and bounded below by the value if i < k - 1 then max 3 (k - i) else 0.

    By the antisymmetry of ≤ on the natural numbers (le_antisymm), an equality a = b follows from the two inequalities a ≤ b and b ≤ a.

    line 4

    uses le_antisymm

      apply le_antisymm
  2. (latin_double_three_tail_shape k).rowLen i ≤ if i < k - 1 then max 3 (k - i) else 0

    We proceed by contradiction: suppose the row length strictly exceeds V = (if i < k - 1 then max 3 (k - i) else 0). Then the cell (i, V) must belong to the Young diagram because its column coordinate V is strictly less than the row length (YoungDiagram.mem_iff_lt_rowLen.mpr). By the explicit definition of the diagram (mem_latin_double_three_tail_shape), cell membership requires both i < k - 1 and V < max 3 (k - i). Case splitting on i < k - 1: if i < k - 1, then V = max 3 (k - i), yielding max 3 (k - i) < max 3 (k - i), an impossibility; if i ≥ k - 1, the required condition i < k - 1 is directly violated. Both cases produce a contradiction via linear integer arithmetic (omega).

    lines 5–9

    uses YoungDiagram.mem_iff_lt_rowLen.mpr, mem_latin_double_three_tail_shape

      · by_contra h
        have hh : (i, if i < k - 1 then max 3 (k - i) else 0) ∈
            latin_double_three_tail_shape k := YoungDiagram.mem_iff_lt_rowLen.mpr (by omega)
        rw [mem_latin_double_three_tail_shape] at hh
        split_ifs at hh <;> omega
  3. (latin_double_three_tail_shape k).rowLen i = if i < k - 1 then max 3 (k - i) else 0

    We prove the reverse inequality (if i < k - 1 then max 3 (k - i) else 0) ≤ (latin_double_three_tail_shape k).rowLen i by contradiction. Let r = (latin_double_three_tail_shape k).rowLen i, and assume for contradiction that V > r. The boundary cell (i, r) cannot belong to the diagram, because by YoungDiagram.mem_iff_lt_rowLen that would require r < r, which contradicts irreflexivity of strict inequality (lt_irrefl). According to mem_latin_double_three_tail_shape, non-membership means that the conjunction i < k - 1 ∧ r < max 3 (k - i) is false. Case splitting on the condition i < k - 1 in the contradiction hypothesis: if i < k - 1, the hypothesis asserts r < max 3 (k - i), meaning both conjuncts hold, a contradiction; if i ≥ k - 1, the hypothesis asserts r < 0, which is impossible for a natural number. Both branches are ruled out by linear arithmetic (omega), establishing the lower bound and completing the equality.

    lines 10–16

    uses YoungDiagram.mem_iff_lt_rowLen, lt_irrefl, mem_latin_double_three_tail_shape

      · by_contra h
        have hh : (i, (latin_double_three_tail_shape k).rowLen i) ∉
            latin_double_three_tail_shape k := by
          rw [YoungDiagram.mem_iff_lt_rowLen]
          exact lt_irrefl _
        rw [mem_latin_double_three_tail_shape] at hh
        split_ifs at h <;> omega
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.
YoungDiagram.mem_iff_lt_rowLen.mpr
In a Young diagram, if a column index j is strictly less than the length of row i, then the cell (i, j) belongs to the diagram.
YoungDiagram.mem_iff_lt_rowLen
A cell (i, j) belongs to a Young diagram if and only if j is strictly less than the length of row i.
mem_latin_double_three_tail_shape
A cell (i, j) belongs to latin_double_three_tail_shape k if and only if i < k - 1 and j < max 3 (k - i).
lt_irrefl
Strict inequality is irreflexive: a < a is always false.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem latin_double_three_tail_shape_rowLen (k i : ℕ) :    (latin_double_three_tail_shape k).rowLen i =      if i < k - 1 then max 3 (k - i) else 0 := by  apply le_antisymm  · by_contra h    have hh : (i, if i < k - 1 then max 3 (k - i) else 0) ∈        latin_double_three_tail_shape k := YoungDiagram.mem_iff_lt_rowLen.mpr (by omega)    rw [mem_latin_double_three_tail_shape] at hh    split_ifs at hh <;> omega  · by_contra h    have hh : (i, (latin_double_three_tail_shape k).rowLen i) ∉        latin_double_three_tail_shape k := by      rw [YoungDiagram.mem_iff_lt_rowLen]      exact lt_irrefl _    rw [mem_latin_double_three_tail_shape] at hh    split_ifs at h <;> omega
See it in the graphDiscuss this resultChallenge it