AFTD Auto-Formalizing Theoretical Domains

cycle_power_exact_pair_exists

theoremverified

An exact Boolean pair-count sum of one supplies a selected owning pair.

Statement

theorem cycle_power_exact_pair_exists
    (D R : ℕ) (x : ℤ → ℕ → Bool)
    (hexact : ∀ v : ℤ, (range R).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) = 1) :
    ∀ v : ℤ, ∃ a : ℕ, a < R ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+D-R) = 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 2
  • cycle_power_gap_exact_side_ownerExact distance D-R ownership in an integer model gives unique compressed gap-side owners for every forward distance-R pair on Fin g, when…
  • cycle_power_dyadic_exact_half_coverExact dyadic pair ownership supplies a witness covering every edge at half the radius, with the distance normalized to a power of two.

The proof, explained

To show the existence of an index a < R satisfying the condition for a given v, the proof observes that the sum of the Boolean indicators over a ∈ range R is 1, hence non-zero. By exists_ne_zero_of_sum_ne_zero, there must exist an index a < R whose term is non-zero. A case analysis on the Boolean values of the two factors shows that their conjunction can only be non-zero when both factors are true.

  1. For any integer v, there exists an index a in range R whose summand is non-zero.

    We introduce an arbitrary integer v. The assumption hexact states that the sum of (x(v - a, a) && x(v - a, a + D - R)).toNat over a ∈ range R is equal to 1. Since 1 ≠ 0, this sum is non-zero (verified by decide). Applying exists_ne_zero_of_sum_ne_zero produces an index a ∈ range R for which the summand is non-zero.

    lines 10–13

    uses exists_ne_zero_of_sum_ne_zero

      intro v
      obtain ⟨a, ha, he⟩ := exists_ne_zero_of_sum_ne_zero
        (show (range R).sum (fun a =>
          (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) ≠ 0 by rw [hexact v]; decide)
  2. The index a satisfies a < R, reducing the goal to showing that both Boolean factors are true.

    From a ∈ range R, the lemma mem_range.mp yields a < R. Providing a and this bound as the witness for the existential quantifier leaves the remaining goal to prove that x(v - a, a) = true and x(v - a, a + D - R) = true.

    line 14

    uses mem_range.mp

      refine ⟨a, mem_range.mp ha, ?_⟩
  3. Both x(v - a, a) and x(v - a, a + D - R) are true.

    We perform a case split on the Boolean values of x(v - a, a) and x(v - a, a + D - R). In the three cases where either term is false, the conjunction evaluates to false and its numerical value is 0, which contradicts the established fact that the summand is non-zero. In the remaining case where both terms are true, the conjunction is true, establishing the claim.

    lines 15–17

    uses Bool.false_and, Bool.true_and, Bool.toNat_false, Bool.toNat_true, ne_eq, not_true_eq_false, and_self

      cases h₀ : x (v-(a : ℤ)) a <;> cases h₁ : x (v-(a : ℤ)) (a+D-R) <;>
        simp_all only [Bool.false_and, Bool.true_and, Bool.toNat_false, Bool.toNat_true,
          ne_eq, not_true_eq_false, and_self]
exists_ne_zero_of_sum_ne_zero
If the sum of a function over a finite set is non-zero, then the function takes a non-zero value at some element of the set.
mem_range.mp
If a natural number belongs to `range n`, then it is strictly less than `n`.
Bool.false_and
The conjunction of `false` with any Boolean value is `false`.
Bool.true_and
The conjunction of `true` with any Boolean value `b` equals `b`.
Bool.toNat_false
The natural number corresponding to `false` is 0.
Bool.toNat_true
The natural number corresponding to `true` is 1.
ne_eq
The inequality `a ≠ b` is defined as the negation of equality, `¬(a = b)`.
not_true_eq_false
The negation of `True` is equal to `False`.
and_self
For any proposition `p`, the conjunction `p ∧ p` is equivalent to `p`.

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_exact_pair_exists    (D R : ℕ) (x : ℤ → ℕ → Bool)    (hexact : ∀ v : ℤ, (range R).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) = 1) :    ∀ v : ℤ, ∃ a : ℕ, a < R ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+D-R) = true := by  intro v  obtain ⟨a, ha, he⟩ := exists_ne_zero_of_sum_ne_zero    (show (range R).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-R)).toNat) ≠ 0 by rw [hexact v]; decide)  refine ⟨a, mem_range.mp ha, ?_⟩  cases h₀ : x (v-(a : ℤ)) a <;> cases h₁ : x (v-(a : ℤ)) (a+D-R) <;>    simp_all only [Bool.false_and, Bool.true_and, Bool.toNat_false, Bool.toNat_true,      ne_eq, not_true_eq_false, and_self]
See it in the graphDiscuss this resultChallenge it