AFTD Auto-Formalizing Theoretical Domains

cycle_power_gap_sides_pair_card

theoremverified

For a profile rooted below g at most D, whose selected distance D-R pairs cross the two blocks, its pair count equals the number of compressed side pairs at forward distance R.

Statement

theorem cycle_power_gap_sides_pair_card
    (D R g r : ℕ) (hRD : R ≤ D) (hg : g ≤ D) (hr : r < g) (b : ℕ → Bool)
    (hcross : ∀ a < R, b a = true → b (a+D-R) = true →
      r+a < g ∧ D ≤ r+(a+D-R)) :
    (range R).sum (fun a => (b a && b (a+D-R)).toNat) =
      (((cycle_power_gap_left_side g r b).product (cycle_power_gap_right_side D g r b)).filter
        (fun p : Fin g × Fin g => p.2.val+R = p.1.val)).card
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 3
  • cycle_power_gap_left_sideThe lower-block vertices of a rooted profile, represented by their absolute positions in Fin g.
  • cycle_power_gap_right_sideThe upper-block vertices of a rooted profile, represented in Fin g after subtracting the radius.
  • bool_sum_eq_card_filterA Boolean profile summed through toNat over a natural range counts exactly its true offsets in that range.
Used by 1
  • cycle_power_dyadic_gap_side_treeBetween two full roots at distance g at most the radius, the compressed sides of every interior tight class satisfy the tree identity:…

The proof, explained

The theorem equates the number of indices a < R where both b a and b (a + D - R) hold with the number of pairs (i, j) in the product of the left and right gap sides satisfying the distance condition j + R = i. First, the sum of booleans is rewritten as the cardinality of the filtered index set S = {a < R | b a && b (a + D - R) = true}. The proof then establishes a bijection between S and the target set via a ↦ (r + a, r + a - R), using the crossing hypothesis `hcross` to guarantee that both coordinates land strictly below g. Injectivity follows from equating the first coordinates, and surjectivity follows by choosing a = i - r for any valid pair (i, j).

  1. The sum of boolean indicator values is reformulated as the cardinality of the subset S ⊆ {0, ..., R-1} of indices where both b a and b (a + D - R) hold.

    Rewriting with `bool_sum_eq_card_filter` transforms the sum of boolean terms into the cardinality of the filtered set S = {a ∈ {0, ..., R-1} | (b a && b (a + D - R)) = true}. The proof then binds S as a local definition.

    lines 12–14

    uses bool_sum_eq_card_filter

      classical
      rw [bool_sum_eq_card_filter]
      let S := (range R).filter (fun a => (b a && b (a+D-R)) = true)
  2. The candidate mapping f : S → Fin g × Fin g defined by f(a) = (r + a, r + a - R) is well-defined, and the goal is restated as |S| = |T|.

    For any a ∈ S, both b a and b (a + D - R) evaluate to true (via `Bool.and_eq_true`). The crossing hypothesis `hcross` guarantees that r + a < g and D ≤ r + (a + D - R). Together with R ≤ D, linear arithmetic (`omega`) implies r + a - R < g, ensuring that both coordinates are valid elements of Fin g. The proof then reformulates the goal as equating the cardinality of S to that of the filtered product set T.

    lines 15–25

    uses Bool.and_eq_true

      let f (a : ℕ) (ha : a ∈ S) : Fin g × Fin g :=
        (⟨r+a, by
          have hb := (mem_filter.mp ha).2
          have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb
          exact (hcross a (mem_range.mp (mem_filter.mp ha).1) hbb.1 hbb.2).1⟩,
         ⟨r+a-R, by
          have hb := (mem_filter.mp ha).2
          have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb
          have hc := hcross a (mem_range.mp (mem_filter.mp ha).1) hbb.1 hbb.2
          omega⟩)
      change S.card = _
  3. It suffices to show that f is a bijection from S onto the target set T.

    Applying `card_bij` with the mapping f reduces the equality of cardinalities |S| = |T| to three subgoals: verifying that f maps S into T, that f is injective on S, and that f maps S surjectively onto T.

    line 26

    uses card_bij

      apply card_bij f
  4. For every a ∈ S, its image f(a) belongs to the target set T.

    Let a ∈ S. Using `Bool.and_eq_true` and `hcross`, both b a and b (a + D - R) are true. To establish that f(a) lies in T, three conditions are verified: first, the left coordinate r + a satisfies r ≤ r + a and (r + a) - r = a, so it belongs to `cycle_power_gap_left_side g r b` using `mem_univ`; second, the right coordinate r + a - R satisfies r + a - R < r (since a < R) and D + (r + a - R) - r = a + D - R, placing it in `cycle_power_gap_right_side D g r b` using `mem_univ`; third, the forward distance condition (r + a - R) + R = r + a holds by linear arithmetic (`omega`).

    lines 27–45

    uses Bool.and_eq_true, mem_univ

      · intro a ha
        have haR := mem_range.mp (mem_filter.mp ha).1
        have hb := (mem_filter.mp ha).2
        have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb
        have hc := hcross a haR hbb.1 hbb.2
        apply mem_filter.mpr
        constructor
        · apply mem_product.mpr
          constructor
          · apply mem_filter.mpr
            refine ⟨mem_univ _, by dsimp [f]; omega, ?_⟩
            have he : (f a ha).1.val-r = a := by dsimp [f]; omega
            simpa only [he] using hbb.1
          · apply mem_filter.mpr
            refine ⟨mem_univ _, by dsimp [f]; omega, ?_⟩
            have he : D+(f a ha).2.val-r = a+D-R := by dsimp [f]; omega
            simpa only [he] using hbb.2
        · dsimp [f]
          omega
  5. The mapping f is injective on S.

    Assuming f(a) = f(a') for a, a' ∈ S, applying `congrArg` with the first-component projection gives r + a = r + a'. Linear arithmetic (`omega`) immediately yields a = a'.

    lines 46–49

    uses congrArg

      · intro a ha a' ha' he
        have heval := congrArg (fun p : Fin g × Fin g => p.1.val) he
        dsimp [f] at heval
        omega
  6. The mapping f is surjective onto T.

    Given a pair p = (i, j) in the target set T, its defining properties give j + R = i, r ≤ i with b (i - r) = true, and j < r with b (D + j - r) = true. Setting a = i - r, linear arithmetic (`omega`) shows a < R (since i = j + R and j < r) and a + D - R = D + j - r. Hence a ∈ S by `Bool.and_eq_true`. Finally, the equality f(a) = p is verified componentwise using `Prod.ext` and `Fin.ext`, where `omega` checks r + (i - r) = i and r + (i - r) - R = j.

    lines 50–65

    uses Bool.and_eq_true, Prod.ext, Fin.ext

      · intro p hp
        have hdist := (mem_filter.mp hp).2
        have hparts := mem_product.mp (mem_filter.mp hp).1
        have hri := (mem_filter.mp hparts.1).2.1
        have hbi := (mem_filter.mp hparts.1).2.2
        have hjr := (mem_filter.mp hparts.2).2.1
        have hbj := (mem_filter.mp hparts.2).2.2
        have haR : p.1.val-r < R := by omega
        have haoff : (p.1.val-r)+D-R = D+p.2.val-r := by omega
        have ha : p.1.val-r ∈ S := by
          apply mem_filter.mpr
          refine ⟨mem_range.mpr haR, ?_⟩
          simp only [Bool.and_eq_true, haoff]
          exact ⟨hbi, hbj⟩
        refine ⟨p.1.val-r, ha, ?_⟩
        apply Prod.ext <;> apply Fin.ext <;> dsimp [f] <;> omega
bool_sum_eq_card_filter
The sum over {0, ..., N-1} of a boolean predicate converted to natural numbers equals the cardinality of the subset where the predicate evaluates to true.
Bool.and_eq_true
A boolean conjunction a && b equals true if and only if both a and b equal true.
card_bij
Two finite sets have equal cardinality if there exists a map between them that lands in the target, is injective, and is surjective.
mem_univ
Every element of a finite type belongs to the universal finite set univ.
congrArg
Applying a function to equal inputs produces equal outputs.
Prod.ext
Two ordered pairs are equal if and only if their respective first and second components are equal.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural number values are equal.

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_gap_sides_pair_card    (D R g r : ℕ) (hRD : R ≤ D) (hg : g ≤ D) (hr : r < g) (b : ℕ → Bool)    (hcross : ∀ a < R, b a = true → b (a+D-R) = true →      r+a < g ∧ D ≤ r+(a+D-R)) :    (range R).sum (fun a => (b a && b (a+D-R)).toNat) =      (((cycle_power_gap_left_side g r b).product (cycle_power_gap_right_side D g r b)).filter        (fun p : Fin g × Fin g => p.2.val+R = p.1.val)).card := by  classical  rw [bool_sum_eq_card_filter]  let S := (range R).filter (fun a => (b a && b (a+D-R)) = true)  let f (a : ℕ) (ha : a ∈ S) : Fin g × Fin g :=    (⟨r+a, by      have hb := (mem_filter.mp ha).2      have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb      exact (hcross a (mem_range.mp (mem_filter.mp ha).1) hbb.1 hbb.2).1⟩,     ⟨r+a-R, by      have hb := (mem_filter.mp ha).2      have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb      have hc := hcross a (mem_range.mp (mem_filter.mp ha).1) hbb.1 hbb.2      omega⟩)  change S.card = _  apply card_bij f  · intro a ha    have haR := mem_range.mp (mem_filter.mp ha).1    have hb := (mem_filter.mp ha).2    have hbb : b a = true ∧ b (a+D-R) = true := by simpa only [Bool.and_eq_true] using hb    have hc := hcross a haR hbb.1 hbb.2    apply mem_filter.mpr    constructor    · apply mem_product.mpr      constructor      · apply mem_filter.mpr        refine ⟨mem_univ _, by dsimp [f]; omega, ?_⟩        have he : (f a ha).1.val-r = a := by dsimp [f]; omega        simpa only [he] using hbb.1      · apply mem_filter.mpr        refine ⟨mem_univ _, by dsimp [f]; omega, ?_⟩        have he : D+(f a ha).2.val-r = a+D-R := by dsimp [f]; omega        simpa only [he] using hbb.2    · dsimp [f]      omega  · intro a ha a' ha' he    have heval := congrArg (fun p : Fin g × Fin g => p.1.val) he    dsimp [f] at heval    omega  · intro p hp    have hdist := (mem_filter.mp hp).2    have hparts := mem_product.mp (mem_filter.mp hp).1    have hri := (mem_filter.mp hparts.1).2.1    have hbi := (mem_filter.mp hparts.1).2.2    have hjr := (mem_filter.mp hparts.2).2.1    have hbj := (mem_filter.mp hparts.2).2.2    have haR : p.1.val-r < R := by omega    have haoff : (p.1.val-r)+D-R = D+p.2.val-r := by omega    have ha : p.1.val-r ∈ S := by      apply mem_filter.mpr      refine ⟨mem_range.mpr haR, ?_⟩      simp only [Bool.and_eq_true, haoff]      exact ⟨hbi, hbj⟩    refine ⟨p.1.val-r, ha, ?_⟩    apply Prod.ext <;> apply Fin.ext <;> dsimp [f] <;> omega
See it in the graphDiscuss this resultChallenge it