AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_exact_half_cover

theoremverified

Exact dyadic pair ownership supplies a witness covering every edge at half the radius, with the distance normalized to a power of two.

Statement

theorem cycle_power_dyadic_exact_half_cover
    (k : ℕ) (x : ℤ → ℕ → Bool)
    (hexact : ∀ j < k+2, ∀ v : ℤ, (range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+2)-2^j)).toNat) = 1) :
    ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+1) ∧ x (v-(a : ℤ)) a = true ∧
      x (v-(a : ℤ)) (a+2^(k+1)) = true
Source
Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 2

The proof, explained

The proof specializes the dyadic exact ownership hypothesis to the index j = k + 1, where the interval length is 2^(k+1) (half the cycle radius 2^(k+2)). Applying cycle_power_exact_pair_exists yields an index a < 2^(k+1) with both endpoint indicators active. Elementary dyadic arithmetic then reduces the offset a + 2^(k+2) - 2^(k+1) to a + 2^(k+1).

  1. 2^(k+2) = 2 * 2^(k+1) automation

    Rewriting 2^(k+2) as 2^(k+1) * 2 using pow_succ, the identity follows by commutativity of multiplication, handled by linear arithmetic.

    line 11

    uses pow_succ

      have hD : 2^(k+2) = 2*2^(k+1) := by rw [pow_succ]; omega
  2. For any vertex v : ℤ, there exists an index a < 2^(k+1) such that x(v - a, a) = true and x(v - a, a + 2^(k+2) - 2^(k+1)) = true.

    Fix a vertex v. Since k + 1 < k + 2 (by linear arithmetic), we instantiate the dyadic exactness hypothesis hexact at index j = k + 1. Applying cycle_power_exact_pair_exists with cycle length D = 2^(k+2) and range R = 2^(k+1) then yields a witness a < 2^(k+1) satisfying both boolean conditions.

    lines 12–14

    uses cycle_power_exact_pair_exists

      intro v
      obtain ⟨a, ha, h₀, h₁⟩ := cycle_power_exact_pair_exists (2^(k+2)) (2^(k+1)) x
        (hexact (k+1) (by omega)) v
  3. a + 2^(k+2) - 2^(k+1) = a + 2^(k+1) automation

    Linear integer arithmetic simplifies the index expression using the identity 2^(k+2) = 2 * 2^(k+1) in scope.

    line 15

      have he : a+2^(k+2)-2^(k+1) = a+2^(k+1) := by omega
  4. The witness a satisfies a < 2^(k+1), x(v - a, a) = true, and x(v - a, a + 2^(k+1)) = true.

    We package the witness a, the bound a < 2^(k+1), and the first equality x(v - a, a) = true. Rewriting the second equality using the arithmetic identity replaces a + 2^(k+2) - 2^(k+1) by a + 2^(k+1), concluding the proof.

    line 16

      exact ⟨a, ha, h₀, by simpa only [he] using h₁⟩
pow_succ
For any monoid element a and natural number n, a^(n+1) = a^n * a.
cycle_power_exact_pair_exists
If for every vertex v the sum over a in [0, R) of the indicator for pair ownership (x(v - a, a) ∧ x(v - a, a + D - R)) equals 1, then for every vertex v there exists some index a < R where both indicators are true.

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_dyadic_exact_half_cover    (k : ℕ) (x : ℤ → ℕ → Bool)    (hexact : ∀ j < k+2, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+2)-2^j)).toNat) = 1) :    ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+1) ∧ x (v-(a : ℤ)) a = true ∧      x (v-(a : ℤ)) (a+2^(k+1)) = true := by  have hD : 2^(k+2) = 2*2^(k+1) := by rw [pow_succ]; omega  intro v  obtain ⟨a, ha, h₀, h₁⟩ := cycle_power_exact_pair_exists (2^(k+2)) (2^(k+1)) x    (hexact (k+1) (by omega)) v  have he : a+2^(k+2)-2^(k+1) = a+2^(k+1) := by omega  exact ⟨a, ha, h₀, by simpa only [he] using h₁⟩
See it in the graphDiscuss this resultChallenge it