AFTD Auto-Formalizing Theoretical Domains

alpha_elementary_lexical_meet

theoremverified

Proposed helper discharging the lexical common-prefix hypothesis in the published adjacency criterion for a valid negative-cell elementary operation.

Statement

theorem alpha_elementary_lexical_meet (a b : List ℕ) (i : ℕ)
    (ha : alpha_is_lexical a) (hb : alpha_is_lexical b)
    (hi : i % 2 = 1) (hstep : alpha_elementary_cell_step a b i) :
    alpha_is_lexical (alpha_lexical_meet a b) ∧
      1 < (alpha_lexical_meet a b).sum + 1 ∧
      (alpha_lexical_meet a b).sum + 1 < a.sum + 1
Source
Run-length helpers for OP-392, arXiv:2610.24758, Conjecture 1; lexical sequences and elementary operations from arXiv:0810.5205, Definitions 1.1, Section 2, Theorem 3.1 and Corollary 3.3. No new research advance is claimed for these supporting statements.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • alpha_is_lexicalA nonempty positive sequence strictly larger than all its proper nonempty suffixes.
  • alpha_elementary_cell_stepOne source elementary split or conjugation, with a zero-based cell index.
  • alpha_lexical_meetThe common left factor, including the minimum value at the first unequal cell.
  • alpha_lexical_ltThe source alternating lexicographic order on positive integer sequences.
  • alpha_signed_cellA cell of a positive sequence, with alternating signs and zero padding.
  • alpha_lexical_meet_is_lexicalThe source common-prefix meet of two nonempty positive lexical sequences is lexical, even if their sums differ.
Used by 1

The proof, explained

The theorem proves that an elementary cell step from a lexical list a to another lexical list b at an odd index i produces a lexical meet alpha_lexical_meet a b that is lexical, has sum plus one strictly greater than 1, and has sum plus one strictly less than a.sum + 1. Lexicality of the meet is handled directly by the library theorem alpha_lexical_meet_is_lexical. The proof splits into the two cases of an elementary operation: splitting a cell of value at least 2 into two cells, or merging a cell of value 1 into its left neighbour. In each case, a and b share a common prefix and diverge at the modified cell, allowing an auxiliary lemma to express their meet as the common prefix followed by the smaller cell value. Finally, positivity of the elements ensures the meet's sum is at least 1, while omission of positive trailing entries guarantees the meet's sum is strictly smaller than that of a.

  1. If two lists share a common prefix p and differ at the next position (x ≠ y), their lexical meet is p ++ [min x y].

    We prove the auxiliary lemma `alpha_elementary_lexical_meet_aux_meet` by induction on the prefix `p`. When `p` is empty, the lists diverge at the very first element with distinct values `x` and `y`, so `alpha_lexical_meet` directly yields `[min x y]` by definition. When `p = z :: p'`, both lists begin with `z`, so the definition preserves `z` and recurses on `p'`; the induction hypothesis then shows that the result is `(z :: p') ++ [min x y]`.

    lines 1–6

    theorem alpha_elementary_lexical_meet_aux_meet (p s t : List ℕ) (x y : ℕ) (hxy : x ≠ y) :
        alpha_lexical_meet (p ++ x :: s) (p ++ y :: t) = p ++ [min x y] := by
      induction p with
      | nil => simp [alpha_lexical_meet, hxy]
      | cons z p ih => simp [alpha_lexical_meet, ih]
    
  2. The lexical meet alpha_lexical_meet a b satisfies alpha_is_lexical.

    We unpack the assumption that `a` is lexical into non-emptiness, positivity of all entries, and the signed lexical condition for drops. We also unpack the step hypothesis into the bound `i < a.length` and the disjunction describing the elementary cell operation. Applying the known lemma `alpha_lexical_meet_is_lexical` to the lexical lists `a` and `b` establishes that their meet is lexical.

    lines 7–16

    uses alpha_lexical_meet_is_lexical

    theorem alpha_elementary_lexical_meet (a b : List ℕ) (i : ℕ)
        (ha : alpha_is_lexical a) (hb : alpha_is_lexical b)
        (hi : i % 2 = 1) (hstep : alpha_elementary_cell_step a b i) :
        alpha_is_lexical (alpha_lexical_meet a b) ∧
          1 < (alpha_lexical_meet a b).sum + 1 ∧
          (alpha_lexical_meet a b).sum + 1 < a.sum + 1 := by
      obtain ⟨hane, hapos, halex⟩ := ha
      obtain ⟨hl, hstep'⟩ := hstep
      have hlex : alpha_is_lexical (alpha_lexical_meet a b) :=
        alpha_lexical_meet_is_lexical a b ⟨hane, hapos, halex⟩ hb
  3. In the split cell case (a[i] > 1), a decomposes as take i a ++ (a[i] :: drop (i + 1) a) and b decomposes as take i a ++ ((a[i] - 1) :: 1 :: drop (i + 1) a).

    In the first branch of the cell operation, cell `i` has value at least 2 and is split into `a[i] - 1` and `1`. Using `List.drop_eq_getElem_cons` and `List.getD_eq_getElem`, `List.drop i a` expands as `a[i] :: List.drop (i + 1) a`. Recombining with `List.take i a` via `List.take_append_drop` yields the decomposed form of `a`. Rewriting with the definition of `b` from the hypothesis gives the corresponding decomposition of `b`.

    lines 17–25

    uses List.drop_eq_getElem_cons, List.getD_eq_getElem, List.take_append_drop

      rcases hstep' with ⟨hgt, hbeq⟩ | ⟨hipos, h1, hbeq⟩
      · have hdrop : List.drop i a = a.getD i 0 :: List.drop (i + 1) a := by
          rw [List.getD_eq_getElem a 0 hl, List.drop_eq_getElem_cons hl]
        have haeq : a = List.take i a ++ (a.getD i 0 :: List.drop (i + 1) a) := by
          have h := List.take_append_drop i a
          rw [hdrop] at h
          exact h.symm
        have hbeq' : b = List.take i a ++ ((a.getD i 0 - 1) :: (1 :: List.drop (i + 1) a)) := by
          rw [hbeq]; simp
  4. In the split case, the lexical meet is take i a ++ [a[i] - 1], with sum (take i a).sum + (a[i] - 1), while a has sum (take i a).sum + a[i] + (drop (i + 1) a).sum.

    Since `a[i] > 1`, we have `a[i] ≠ a[i] - 1` and `min a[i] (a[i] - 1) = a[i] - 1`. Both `a` and `b` share the prefix `take i a` and diverge at index `i` with values `a[i]` and `a[i] - 1`. Applying `alpha_elementary_lexical_meet_aux_meet` shows their meet is `take i a ++ [a[i] - 1]`. Computing the sum of this list and the sum of `a` from their decompositions gives the explicit sum formulas, using `Nat.add_assoc` to reassociate the terms.

    lines 26–35

    uses alpha_elementary_lexical_meet_aux_meet, Nat.add_assoc

        have hmin : min (a.getD i 0) (a.getD i 0 - 1) = a.getD i 0 - 1 := by omega
        have hmeet : alpha_lexical_meet a b = List.take i a ++ [a.getD i 0 - 1] := by
          conv_lhs => rw [haeq, hbeq']
          rw [alpha_elementary_lexical_meet_aux_meet (List.take i a) (List.drop (i + 1) a)
              (1 :: List.drop (i + 1) a) (a.getD i 0) (a.getD i 0 - 1) (by omega), hmin]
        have hsum_meet : (alpha_lexical_meet a b).sum = (List.take i a).sum + (a.getD i 0 - 1) := by
          rw [hmeet]; simp
        have hsum_a : a.sum = (List.take i a).sum + a.getD i 0 + (List.drop (i + 1) a).sum := by
          conv_lhs => rw [haeq]
          simp [Nat.add_assoc]
  5. In the split case, the sum of the meet plus 1 is strictly between 1 and a.sum + 1.

    Because `a[i] ≥ 2`, the term `a[i] - 1` is at least 1, so the sum of the meet is at least 1, which implies `1 < (meet).sum + 1`. Moreover, `a[i] - 1 < a[i]` and the remaining tail entries are nonnegative, so `(meet).sum + 1 < a.sum + 1`. Both inequalities are closed by `omega`.

    line 36

        exact ⟨hlex, by rw [hsum_meet]; omega, by rw [hsum_meet, hsum_a]; omega⟩
  6. In the merged cell case (i > 0 and a[i] = 1), a decomposes around indices i - 1 and i, while b replaces a[i - 1] with a[i - 1] + 1 and removes a[i].

    In the second branch of the cell operation, `i > 0` and `a[i] = 1`, and cell `i` is merged into cell `i - 1`. Applying `List.drop_eq_getElem_cons` twice (at `i - 1` and at `i`) together with `List.getD_eq_getElem` decomposes `List.drop (i - 1) a` into `a[i - 1] :: a[i] :: List.drop (i + 1) a`. Recombining with `List.take (i - 1) a` via `List.take_append_drop` yields the decomposed form of `a`. Substituting into the formula for `b` from the hypothesis gives `take (i - 1) a ++ ((a[i - 1] + 1) :: drop (i + 1) a)`.

    lines 37–49

    uses List.drop_eq_getElem_cons, List.getD_eq_getElem, List.take_append_drop

      · have hlt1 : i - 1 < a.length := by omega
        have hsub : i - 1 + 1 = i := by omega
        have hdrop1 : List.drop (i - 1) a =
            a.getD (i - 1) 0 :: (a.getD i 0 :: List.drop (i + 1) a) := by
          rw [List.getD_eq_getElem a 0 hlt1, List.drop_eq_getElem_cons hlt1, hsub,
            List.getD_eq_getElem a 0 hl, List.drop_eq_getElem_cons hl]
        have haeq : a = List.take (i - 1) a ++
            (a.getD (i - 1) 0 :: (a.getD i 0 :: List.drop (i + 1) a)) := by
          have h := List.take_append_drop (i - 1) a
          rw [hdrop1] at h
          exact h.symm
        have hbeq' : b = List.take (i - 1) a ++ ((a.getD (i - 1) 0 + 1) :: List.drop (i + 1) a) := by
          rw [hbeq]; simp
  7. In the merged case, the lexical meet is take (i - 1) a ++ [a[i - 1]], with sum (take (i - 1) a).sum + a[i - 1], while a has sum (take (i - 1) a).sum + a[i - 1] + a[i] + (drop (i + 1) a).sum.

    Lists `a` and `b` share the prefix `take (i - 1) a` and diverge at index `i - 1` with values `a[i - 1]` and `a[i - 1] + 1`. By `alpha_elementary_lexical_meet_aux_meet`, their meet is `take (i - 1) a ++ [min a[i - 1] (a[i - 1] + 1)]`. Since `a[i - 1] ≤ a[i - 1] + 1`, `Nat.min_eq_left` reduces the minimum to `a[i - 1]`. Summing both lists gives the explicit sum formulas, reassociated with `Nat.add_assoc`.

    lines 50–60

    uses alpha_elementary_lexical_meet_aux_meet, Nat.min_eq_left, Nat.add_assoc

        have hmeet : alpha_lexical_meet a b = List.take (i - 1) a ++ [a.getD (i - 1) 0] := by
          conv_lhs => rw [haeq, hbeq']
          rw [alpha_elementary_lexical_meet_aux_meet (List.take (i - 1) a)
              (a.getD i 0 :: List.drop (i + 1) a) (List.drop (i + 1) a) (a.getD (i - 1) 0)
              (a.getD (i - 1) 0 + 1) (by omega), Nat.min_eq_left (by omega)]
        have hsum_meet : (alpha_lexical_meet a b).sum = (List.take (i - 1) a).sum + a.getD (i - 1) 0 := by
          rw [hmeet]; simp
        have hsum_a : a.sum = (List.take (i - 1) a).sum + a.getD (i - 1) 0 + a.getD i 0 +
            (List.drop (i + 1) a).sum := by
          conv_lhs => rw [haeq]
          simp [Nat.add_assoc]
  8. In the merged case, the sum of the meet plus 1 is strictly between 1 and a.sum + 1, completing the proof.

    Since `a` is lexical, all its elements are strictly positive; in particular, `a[i - 1] > 0` (via `List.getElem_mem` and `List.getD_eq_getElem`). Therefore the sum of the meet is at least `a[i - 1] ≥ 1`, showing `1 < (meet).sum + 1`. In addition, `a` contains the extra positive entry `a[i] = 1`, making the sum of `a` strictly larger than that of the meet, so `(meet).sum + 1 < a.sum + 1`. Both bounds are verified by `omega`.

    lines 61–63

    uses List.getD_eq_getElem, List.getElem_mem

        have hypos : 0 < a.getD (i - 1) 0 :=
          hapos _ (by rw [List.getD_eq_getElem a 0 hlt1]; exact List.getElem_mem hlt1)
        exact ⟨hlex, by rw [hsum_meet]; omega, by rw [hsum_meet, hsum_a]; omega⟩
alpha_lexical_meet_is_lexical
The lexical meet of two lexical lists is itself lexical.
List.drop_eq_getElem_cons
Dropping i elements from a list of length greater than i yields the element at index i followed by dropping i + 1 elements.
List.getD_eq_getElem
Accessing a list with default value getD at a valid index equals indexing with getElem.
List.take_append_drop
Concatenating the prefix of length i and the suffix dropping i elements reconstructs the original list.
alpha_elementary_lexical_meet_aux_meet
If two lists share a prefix p and differ at the next elements x and y (with x ≠ y), their lexical meet equals p ++ [min x y].
Nat.add_assoc
Addition of natural numbers is associative: (n + m) + k = n + (m + k).
Nat.min_eq_left
If a ≤ b, then min a b = a.
List.getElem_mem
Any element accessed by valid indexing belongs to the list.

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 alpha_elementary_lexical_meet_aux_meet (p s t : List ℕ) (x y : ℕ) (hxy : x ≠ y) :    alpha_lexical_meet (p ++ x :: s) (p ++ y :: t) = p ++ [min x y] := by  induction p with  | nil => simp [alpha_lexical_meet, hxy]  | cons z p ih => simp [alpha_lexical_meet, ih]theorem alpha_elementary_lexical_meet (a b : List ℕ) (i : ℕ)    (ha : alpha_is_lexical a) (hb : alpha_is_lexical b)    (hi : i % 2 = 1) (hstep : alpha_elementary_cell_step a b i) :    alpha_is_lexical (alpha_lexical_meet a b) ∧      1 < (alpha_lexical_meet a b).sum + 1 ∧      (alpha_lexical_meet a b).sum + 1 < a.sum + 1 := by  obtain ⟨hane, hapos, halex⟩ := ha  obtain ⟨hl, hstep'⟩ := hstep  have hlex : alpha_is_lexical (alpha_lexical_meet a b) :=    alpha_lexical_meet_is_lexical a b ⟨hane, hapos, halex⟩ hb  rcases hstep' with ⟨hgt, hbeq⟩ | ⟨hipos, h1, hbeq⟩  · have hdrop : List.drop i a = a.getD i 0 :: List.drop (i + 1) a := by      rw [List.getD_eq_getElem a 0 hl, List.drop_eq_getElem_cons hl]    have haeq : a = List.take i a ++ (a.getD i 0 :: List.drop (i + 1) a) := by      have h := List.take_append_drop i a      rw [hdrop] at h      exact h.symm    have hbeq' : b = List.take i a ++ ((a.getD i 0 - 1) :: (1 :: List.drop (i + 1) a)) := by      rw [hbeq]; simp    have hmin : min (a.getD i 0) (a.getD i 0 - 1) = a.getD i 0 - 1 := by omega    have hmeet : alpha_lexical_meet a b = List.take i a ++ [a.getD i 0 - 1] := by      conv_lhs => rw [haeq, hbeq']      rw [alpha_elementary_lexical_meet_aux_meet (List.take i a) (List.drop (i + 1) a)          (1 :: List.drop (i + 1) a) (a.getD i 0) (a.getD i 0 - 1) (by omega), hmin]    have hsum_meet : (alpha_lexical_meet a b).sum = (List.take i a).sum + (a.getD i 0 - 1) := by      rw [hmeet]; simp    have hsum_a : a.sum = (List.take i a).sum + a.getD i 0 + (List.drop (i + 1) a).sum := by      conv_lhs => rw [haeq]      simp [Nat.add_assoc]    exact ⟨hlex, by rw [hsum_meet]; omega, by rw [hsum_meet, hsum_a]; omega⟩  · have hlt1 : i - 1 < a.length := by omega    have hsub : i - 1 + 1 = i := by omega    have hdrop1 : List.drop (i - 1) a =        a.getD (i - 1) 0 :: (a.getD i 0 :: List.drop (i + 1) a) := by      rw [List.getD_eq_getElem a 0 hlt1, List.drop_eq_getElem_cons hlt1, hsub,        List.getD_eq_getElem a 0 hl, List.drop_eq_getElem_cons hl]    have haeq : a = List.take (i - 1) a ++        (a.getD (i - 1) 0 :: (a.getD i 0 :: List.drop (i + 1) a)) := by      have h := List.take_append_drop (i - 1) a      rw [hdrop1] at h      exact h.symm    have hbeq' : b = List.take (i - 1) a ++ ((a.getD (i - 1) 0 + 1) :: List.drop (i + 1) a) := by      rw [hbeq]; simp    have hmeet : alpha_lexical_meet a b = List.take (i - 1) a ++ [a.getD (i - 1) 0] := by      conv_lhs => rw [haeq, hbeq']      rw [alpha_elementary_lexical_meet_aux_meet (List.take (i - 1) a)          (a.getD i 0 :: List.drop (i + 1) a) (List.drop (i + 1) a) (a.getD (i - 1) 0)          (a.getD (i - 1) 0 + 1) (by omega), Nat.min_eq_left (by omega)]    have hsum_meet : (alpha_lexical_meet a b).sum = (List.take (i - 1) a).sum + a.getD (i - 1) 0 := by      rw [hmeet]; simp    have hsum_a : a.sum = (List.take (i - 1) a).sum + a.getD (i - 1) 0 + a.getD i 0 +        (List.drop (i + 1) a).sum := by      conv_lhs => rw [haeq]      simp [Nat.add_assoc]    have hypos : 0 < a.getD (i - 1) 0 :=      hapos _ (by rw [List.getD_eq_getElem a 0 hlt1]; exact List.getElem_mem hlt1)    exact ⟨hlex, by rw [hsum_meet]; omega, by rw [hsum_meet, hsum_a]; omega⟩
See it in the graphDiscuss this resultChallenge it