AFTD Auto-Formalizing Theoretical Domains

cycle_power_sixteen_block_second_eighth_monotone

theoremverified

Under the Geometry hypotheses and the global no-vertical condition C_t implies A_t, the second eighth is an initial segment: u<=t<2h and C_t selected imply C_u selected.

Statement

theorem cycle_power_sixteen_block_second_eighth_monotone
    (h : ℕ) (x : ℤ → ℕ → Bool) (M : CyclePowerSixteenBlock.Geometry h x)
    (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true)
    (p : ℤ) (u t : ℕ) (hut : u ≤ t) (ht : t < 2*h)
    (hC : x p (2*h+t) = true) : x p (2*h+u) = true
Source
Uniform structural reduction for OP-205 / RT-1 following arXiv:2610.15635. The main covering theorem and vertical-defect exclusion remain open. Experiments8048/8049 suggested the two ordinary distances; the proof is uniform in h and uses Lean only. No advance flag.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The theorem proves that within the second eighth (indices 2h ≤ 2h + t < 4h), the set of selected nodes is downward closed: if u ≤ t < 2h and node 2h + t is selected on row p, then node 2h + u is also selected. For u < t, setting L = t - u and invoking the covering property on diagonal v = p + 2h + u at distance 12h + L yields a selected pair (a, a + 12h + L) on row r = v - a. A case analysis on a and a + L shows that the cases a + L < 2h and a < 2h are ruled out by uniqueness of diagonal pairs (M.own6 and M.own7), while the case a ≥ 2h uses child prefix forcing and M.own7 to establish r = p and a = 2h + u, directly identifying the covered node x r a as the desired node x p (2h + u).

  1. If u = t, the claim holds immediately.

    When u = t, the goal x p (2*h + u) = true is identical to the given hypothesis hC : x p (2*h + t) = true.

    lines 10–11

      by_cases he : u=t
      · simpa only [he] using hC
  2. For u < t, choose a covering pair at distance 12h + L along the diagonal v = p + 2h + u, and deduce the existence of selected nodes at indices t and 14h + t on row p.

    Assuming u ≠ t, we have u < t. Let L = t - u, so 0 < L < 2h. On the diagonal line v = p + 2h + u, the covering property M.cover with step distance 12h + L yields an offset a < 4h - L such that on row r = v - a, both x r a = true and x r (a + 12h + L) = true. In addition, from x p (2h + t) = true and t < 2h, the no-vertical condition nov gives x p t = true, and M.childZ ensures that the corresponding node in the eighth block x p (14h + t) = true is also selected.

    lines 12–21

    uses M.pos, M.cover, M.childZ

      have hut' : u < t := by omega
      let L := t-u
      have hL : 0 < L := by dsimp [L]; omega
      have hLq : L < 2*h := by dsimp [L]; omega
      let v : ℤ := p+(2*h : ℕ)+(u : ℤ)
      obtain ⟨a,ha,hA,hB⟩ := M.cover (12*h+L) (by have := M.pos; omega) (by omega) v
      let r : ℤ := v-(a : ℤ)
      have ha4 : a < 4*h-L := by omega
      have hAt := nov p t ht hC
      have hZt := M.childZ p t ht hC
  3. The case a + L < 2h leads to a contradiction.

    If a + L < 2h, the parent condition M.parent6 implies that the selected node at a + L + 12h forces its parent x r (a + L) = true to be selected. The pairs (r, a + L) and (p, 2h + t) lie on the same diagonal line (since r + a + L = v + L = p + 2h + t) and both have distance-12h selected partners. By uniqueness of 6-step pairs (M.own6), r = p. This equality implies a = 2h + u ≥ 2h, which contradicts a + L < 2h.

    lines 22–31

    uses M.parent6, M.own6

      by_cases ha0 : a+L < 2*h
      · have hl : x r (a+L) = true := by
          apply (M.parent6 r (a+L) (by omega)).1 ha0
          convert hB using 1 <;> congr 1 <;> omega
        have heq := M.own6 r p (a+L) (2*h+t) (by omega) (by omega)
          (by dsimp [r,v,L]; omega) hl
          (by convert hB using 1 <;> congr 1 <;> omega) hC
          (by convert hZt using 1 <;> congr 1 <;> omega)
        dsimp [r,v,L] at heq
        omega
  4. The case a + L ≥ 2h with a < 2h also leads to a contradiction.

    If a + L ≥ 2h and a < 2h, let b = a + L - 2h. Then b < 2h and b ≤ a. By prefix monotonicity in the first eighth (M.lowMono), x r a = true implies x r b = true. Furthermore, b + 14h = a + 12h + L, so x r (b + 14h) = true. Comparing (r, b) with (p, t) on the common diagonal r + b = p + t, uniqueness of 7-step pairs (M.own7) yields r = p. This again implies a = 2h + u ≥ 2h, contradicting a < 2h.

    lines 32–41

    uses M.lowMono, M.own7

      · by_cases haq : a < 2*h
        · let b := a+L-2*h
          have hb : b < 2*h := by dsimp [b]; omega
          have hba : b ≤ a := by dsimp [b]; omega
          have hl : x r b = true := M.lowMono r b a hba haq hA
          have hz : x r (b+14*h) = true := by convert hB using 1 <;> congr 1 <;> dsimp [b] <;> omega
          have heq := M.own7 r p b t hb ht (by dsimp [r,v,b,L]; omega) hl hz hAt
            (by convert hZt using 1 <;> congr 1 <;> omega)
          dsimp [r,v,L] at heq
          omega
  5. In the remaining case a ≥ 2h, the row equality r = p holds and establishes x p (2h + u) = true.

    When a ≥ 2h, let b = a - 2h < 2h. Then 2h + b = a, so row r has a selected child node x r (2h + b) = true. By cycle_power_sixteen_block_child_forces_full_prefix, the entire first eighth on row r is selected; in particular, x r (b + L) = true since b + L < 2h. Moreover, (b + L) + 14h = a + 12h + L is selected. By uniqueness of 7-step pairs (M.own7) on the diagonal r + b + L = p + t, we deduce r = p. Expanding r = p gives a = 2h + u, so the selected node x r a = true obtained from covering is precisely x p (2h + u) = true.

    lines 42–51

    uses cycle_power_sixteen_block_child_forces_full_prefix, M.own7

        · let b := a-2*h
          have hb : b < 2*h := by dsimp [b]; omega
          have hbL : b+L < 2*h := by dsimp [b]; omega
          have hc : x r (2*h+b) = true := by convert hA using 1 <;> congr 1 <;> dsimp [b] <;> omega
          have hfull := cycle_power_sixteen_block_child_forces_full_prefix h x M nov r b hb hc
          have hz : x r (b+L+14*h) = true := by convert hB using 1 <;> congr 1 <;> dsimp [b] <;> omega
          have heq := M.own7 r p (b+L) t hbL ht (by dsimp [r,v,b,L]; omega) (hfull (b+L) hbL) hz hAt
            (by convert hZt using 1 <;> congr 1 <;> omega)
          dsimp [r,v] at heq
          convert hA using 1 <;> congr 1 <;> omega
M.pos
The block size parameter h is strictly positive (0 < h).
M.cover
For any step size 1 ≤ d < 16h and any diagonal line v, there exists an offset a < 16h - d such that both (v - a, a) and (v - a, a + d) are selected.
M.childZ
If a child node at 2h + a is selected (with a < 2h), then the corresponding node in the eighth block at 14h + a is also selected.
M.parent6
For a < 4h, if a < 2h then selection of a + 12h implies selection of a; if 2h ≤ a then selection of a implies selection of a + 12h.
M.own6
Uniqueness of 6-step parent-child pairs: if two pairs on the same diagonal line p + a = r + b (with a, b < 4h) both have selected nodes at offset 0 and offset 12h, then p = r.
M.lowMono
Prefix monotonicity in the first eighth: if a ≤ b < 2h and node b is selected on row p, then node a is also selected on row p.
M.own7
Uniqueness of 7-step parent-child pairs: if two pairs on the same diagonal line p + a = r + b (with a, b < 2h) both have selected nodes at offset 0 and offset 14h, then p = r.
cycle_power_sixteen_block_child_forces_full_prefix
If any child node 2h + t (with t < 2h) is selected on row p, then every node in the first eighth (s < 2h) on row p is selected.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_sixteen_block_second_eighth_monotone    (h : ℕ) (x : ℤ → ℕ → Bool) (M : CyclePowerSixteenBlock.Geometry h x)    (nov : ∀ p a, a < 2*h → x p (2*h+a) = true → x p a = true)    (p : ℤ) (u t : ℕ) (hut : u ≤ t) (ht : t < 2*h)    (hC : x p (2*h+t) = true) : x p (2*h+u) = true := by  by_cases he : u=t  · simpa only [he] using hC  have hut' : u < t := by omega  let L := t-u  have hL : 0 < L := by dsimp [L]; omega  have hLq : L < 2*h := by dsimp [L]; omega  let v : ℤ := p+(2*h : ℕ)+(u : ℤ)  obtain ⟨a,ha,hA,hB⟩ := M.cover (12*h+L) (by have := M.pos; omega) (by omega) v  let r : ℤ := v-(a : ℤ)  have ha4 : a < 4*h-L := by omega  have hAt := nov p t ht hC  have hZt := M.childZ p t ht hC  by_cases ha0 : a+L < 2*h  · have hl : x r (a+L) = true := by      apply (M.parent6 r (a+L) (by omega)).1 ha0      convert hB using 1 <;> congr 1 <;> omega    have heq := M.own6 r p (a+L) (2*h+t) (by omega) (by omega)      (by dsimp [r,v,L]; omega) hl      (by convert hB using 1 <;> congr 1 <;> omega) hC      (by convert hZt using 1 <;> congr 1 <;> omega)    dsimp [r,v,L] at heq    omega  · by_cases haq : a < 2*h    · let b := a+L-2*h      have hb : b < 2*h := by dsimp [b]; omega      have hba : b ≤ a := by dsimp [b]; omega      have hl : x r b = true := M.lowMono r b a hba haq hA      have hz : x r (b+14*h) = true := by convert hB using 1 <;> congr 1 <;> dsimp [b] <;> omega      have heq := M.own7 r p b t hb ht (by dsimp [r,v,b,L]; omega) hl hz hAt        (by convert hZt using 1 <;> congr 1 <;> omega)      dsimp [r,v,L] at heq      omega    · let b := a-2*h      have hb : b < 2*h := by dsimp [b]; omega      have hbL : b+L < 2*h := by dsimp [b]; omega      have hc : x r (2*h+b) = true := by convert hA using 1 <;> congr 1 <;> dsimp [b] <;> omega      have hfull := cycle_power_sixteen_block_child_forces_full_prefix h x M nov r b hb hc      have hz : x r (b+L+14*h) = true := by convert hB using 1 <;> congr 1 <;> dsimp [b] <;> omega      have heq := M.own7 r p (b+L) t hbL ht (by dsimp [r,v,b,L]; omega) (hfull (b+L) hbL) hz hAt        (by convert hZt using 1 <;> congr 1 <;> omega)      dsimp [r,v] at heq      convert hA using 1 <;> congr 1 <;> omega
See it in the graphDiscuss this resultChallenge it