AFTD Auto-Formalizing Theoretical Domains

cycle_power_sixteen_block_child_forces_full_prefix

theoremverified

Under the explicit Geometry hypotheses and the global no-vertical-defect condition C_t implies A_t, every root with any selected C_t has its entire first2h prefix selected.

Statement

theorem cycle_power_sixteen_block_child_forces_full_prefix
    (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 : ℤ) (t : ℕ) (ht : t < 2*h) (hC : x p (2*h+t) = true) :
    ∀ s < 2*h, x p s = 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 1
Used by 2

The proof, explained

We prove the claim by contradiction, assuming some prefix position s < 2h is false. The no-vertical-defect condition ensures that x(p, t) = true because its corresponding child bit x(p, 2h+t) is true. If s ≤ t, downward prefix monotonicity forces x(p, s) = true, an immediate contradiction. If s > t, having both the parent bit x(p, t) and child bit x(p, 2h+t) true while a later prefix bit x(p, s) is false contradicts the no-vertical-overlap theorem.

  1. Assuming for contradiction that some prefix bit is false, the root must also satisfy x(p, t) = true.

    We proceed by contradiction: suppose there exists an index s < 2h such that x(p, s) is not true. Since boolean values are binary, x(p, s) must be false by Bool.eq_false_iff.mpr. Meanwhile, applying the no-vertical-defect hypothesis nov to x(p, 2h+t) = true establishes that x(p, t) = true.

    lines 10–13

    uses Bool.eq_false_iff.mpr

      intro s hs
      by_contra hn
      have hmiss : x p s = false := Bool.eq_false_iff.mpr hn
      have hA := nov p t ht hC
  2. The index s cannot be less than or equal to t.

    We split on whether s ≤ t. If s ≤ t, downward prefix monotonicity (M.lowMono) implies x(p, s) = true from x(p, t) = true and t < 2h. But this contradicts our assumption that x(p, s) = false. Therefore, s ≤ t is impossible.

    lines 14–17

    uses M.lowMono

      by_cases hst : s ≤ t
      · have ha := M.lowMono p s t hst ht hA
        rw [hmiss] at ha
        contradiction
  3. The remaining case s > t is also impossible, concluding the proof.

    When s ≤ t fails, linear arithmetic (omega) gives t < s. Together with s < 2h, x(p, t) = true, x(p, 2h+t) = true, and x(p, s) = false, this satisfies the hypotheses of cycle_power_sixteen_block_no_vertical_overlap, which rules out vertical overlap and yields a contradiction.

    line 18

    uses cycle_power_sixteen_block_no_vertical_overlap

      · exact cycle_power_sixteen_block_no_vertical_overlap h x M nov p t s (by omega) hs hA hC hmiss
Bool.eq_false_iff.mpr
A boolean is false if and only if it is not true; here used in the direction that if b ≠ true, then b = false.
M.lowMono
Within the initial prefix of length 2h, true values are downward-closed: if a ≤ b < 2h and the bit at b is true, then the bit at a is true.
cycle_power_sixteen_block_no_vertical_overlap
Under the geometry and no-vertical-defect conditions, a root cannot simultaneously have x(p, t) = true, x(p, 2h+t) = true, and x(p, s) = false for indices t < s < 2h.

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_child_forces_full_prefix    (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 : ℤ) (t : ℕ) (ht : t < 2*h) (hC : x p (2*h+t) = true) :    ∀ s < 2*h, x p s = true := by  intro s hs  by_contra hn  have hmiss : x p s = false := Bool.eq_false_iff.mpr hn  have hA := nov p t ht hC  by_cases hst : s ≤ t  · have ha := M.lowMono p s t hst ht hA    rw [hmiss] at ha    contradiction  · exact cycle_power_sixteen_block_no_vertical_overlap h x M nov p t s (by omega) hs hA hC hmiss
See it in the graphDiscuss this resultChallenge it