AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_exact_endpoints

theoremverified

Exact ownership of all dyadic distances in a radius-2^m model with positive exponent forces both endpoints of every rooted class to be selected.

Statement

theorem cycle_power_dyadic_exact_endpoints
    (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool)
    (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) :
    ∀ p : ℤ, x p 0 = true ∧ x p (2^m-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
Used by 12

The proof, explained

The theorem is proved by specializing the exact dyadic ownership hypothesis to scale $j = 0$, which is valid since $m \ge 1$. At this scale, the sum has length $2^0 = 1$, reducing to a single term asserting that the conjunction $x(p, 0) \land x(p, 2^m - 1)$ has numerical value $1$. Because a boolean conjunction can only evaluate to $1$ when both operands are true, both $x(p, 0)$ and $x(p, 2^m - 1)$ must be true.

  1. For any integer $p$, the numerical value of the conjunction $x(p, 0) \land x(p, 2^m - 1)$ equals $1$.

    Fix an arbitrary $p \in \mathbb{Z}$. Because $m \ge 1$, we have $0 < m$ by linear arithmetic, allowing us to instantiate the exact dyadic ownership hypothesis (hexact) at scale $j = 0$ and base vertex $v = p$. Since $2^0 = 1$, the sum over the range of length $2^0$ contains only the single index $a = 0$. Simplifying $p - 0 = p$ and $0 + 2^m - 2^0 = 2^m - 1$ reduces the sum to $(x(p, 0) \land x(p, 2^m - 1)).\text{toNat} = 1$.

    lines 10–12

    uses pow_zero, sum_range_one, Nat.cast_zero, sub_zero, zero_add

      intro p
      have he := hexact 0 (by omega) p
      simp only [pow_zero, sum_range_one, Nat.cast_zero, sub_zero, zero_add] at he
  2. Both endpoints are selected: $x(p, 0) = \text{true}$ and $x(p, 2^m - 1) = \text{true}$.

    We consider the four possible truth values of the pair $(x(p, 0), x(p, 2^m - 1))$. If either boolean value is false, their conjunction is false, yielding a numerical value of $0$, which contradicts the equality $(x(p, 0) \land x(p, 2^m - 1)).\text{toNat} = 1$. The only consistent case is when both $x(p, 0)$ and $x(p, 2^m - 1)$ are true, which directly matches the goal.

    line 13

      cases h₀ : x p 0 <;> cases h₁ : x p (2^m-1) <;> simp [h₀,h₁] at he ⊢
pow_zero
Any element raised to the power 0 equals 1 ($a^0 = 1$).
sum_range_one
The sum of a function over the singleton range {0} equals the function evaluated at 0.
Nat.cast_zero
The natural number 0 casts to 0 in any additive monoid with one.
sub_zero
Subtracting 0 from an element leaves it unchanged ($a - 0 = a$).
zero_add
Adding 0 to an element on the left leaves it unchanged ($0 + a = a$).

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_endpoints    (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool)    (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1) :    ∀ p : ℤ, x p 0 = true ∧ x p (2^m-1) = true := by  intro p  have he := hexact 0 (by omega) p  simp only [pow_zero, sum_range_one, Nat.cast_zero, sub_zero, zero_add] at he  cases h₀ : x p 0 <;> cases h₁ : x p (2^m-1) <;> simp [h₀,h₁] at he ⊢
See it in the graphDiscuss this resultChallenge it