AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_prune_full_class_cover_of_middle_fullness

theoremverified

Current-scale middle-bit fullness ensures that every vertex of the pruned model lies in a full pruned class. Fullness and half-distance coverage remain explicit; no count preservation is asserted.

Statement

theorem cycle_power_dyadic_prune_full_class_cover_of_middle_fullness
    (k : ℕ) (x : ℤ → ℕ → Bool)
    (hmid : ∀ (p : ℤ) (a : ℕ), 2^k ≤ a → a < 3*2^k → x p a = true →
      ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true)
    (hcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+1) ∧
      x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+2^(k+1)) = true) :
    ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+1) ∧
      ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x (v-(a : ℤ))) i = true
Source
Routine bridge for OP-205 / RT-1 fullness induction. The stronger idea that full classes at every vertex force general shape remains conjectural; reduced-neighbour shortcuts have guarded countermodels in experiment6657.
Verified
27 Oct 2026
Axioms
Quot.soundpropext
Built on 2
Used by 2

The proof, explained

To show that every vertex v ∈ ℤ belongs to a full pruned class, the proof applies the half-distance coverage hypothesis to obtain an offset a < 2^(k+1) where the configuration x(v - a, ·) is true at both a and a + 2^(k+1). It then invokes cycle_power_dyadic_half_owner_full_prune_of_middle, which establishes that middle-bit fullness and two true bits separated by 2^(k+1) guarantee that the lifted dyadic class at v - a is identically true everywhere.

  1. For an arbitrary vertex v ∈ ℤ, there is an offset a < 2^(k+1) such that x(v - a, a) = true and x(v - a, a + 2^(k+1)) = true.

    Fix an arbitrary vertex v ∈ ℤ. Instantiating the coverage hypothesis hcover at v provides an index a < 2^(k+1) where the configuration x at base v - a is true at both a and a + 2^(k+1).

    lines 11–12

      intro v
      rcases hcover v with ⟨a, ha, h0, h1⟩
  2. The vertex v belongs to a full pruned class.

    Using the index a obtained from coverage, the bound a < 2^(k+1) holds directly. Applying cycle_power_dyadic_half_owner_full_prune_of_middle to the base position v - a with the two true values at a and a + 2^(k+1) proves that the lifted dyadic vector cycle_power_dyadic_b_lift k (x (v - a)) is true for every index i < 2^(k+1).

    line 13

    uses cycle_power_dyadic_half_owner_full_prune_of_middle

      exact ⟨a, ha, cycle_power_dyadic_half_owner_full_prune_of_middle k x hmid (v - (a : ℤ)) a ha h0 h1⟩
cycle_power_dyadic_half_owner_full_prune_of_middle
Under the middle-bit fullness hypothesis, if a configuration at base p takes the value true at both an offset a < 2^(k+1) and a + 2^(k+1), then its dyadic lift is identically true at all indices i < 2^(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

open Finsettheorem cycle_power_dyadic_prune_full_class_cover_of_middle_fullness    (k : ℕ) (x : ℤ → ℕ → Bool)    (hmid : ∀ (p : ℤ) (a : ℕ), 2^k ≤ a → a < 3*2^k → x p a = true →      ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true)    (hcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+1) ∧      x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+2^(k+1)) = true) :    ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+1) ∧      ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x (v-(a : ℤ))) i = true := by  intro v  rcases hcover v with ⟨a, ha, h0, h1⟩  exact ⟨a, ha, cycle_power_dyadic_half_owner_full_prune_of_middle k x hmid (v - (a : ℤ)) a ha h0 h1⟩
See it in the graphDiscuss this resultChallenge it