AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_gap_side_tree

theoremverified

Between two full roots at distance g at most the radius, the compressed sides of every interior tight class satisfy the tree identity: total side size is one plus the sum of its dyadic forward pair counts.

Statement

theorem cycle_power_dyadic_gap_side_tree
    (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool)
    (htight : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) =
      (range (2^m)).sum (fun i => (x p i).toNat))
    (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1)
    (g : ℕ) (hg : g ≤ 2^m)
    (hfull₀ : ∀ i < 2^m, x 0 i = true)
    (hfullg : ∀ i < 2^m, x (g : ℤ) i = true) :
    ∀ r : Fin (g-1),
      (cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ))).card +
      (cycle_power_gap_right_side (2^m) g (r.val+1) (x ((r.val+1 : ℕ) : ℤ))).card =
      1 + (range m).sum (fun j =>
        (((cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ))).product
          (cycle_power_gap_right_side (2^m) g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)))).filter
            (fun p : Fin g × Fin g => p.2.val+2^j = 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 9
Used by 1

The proof, explained

The proof establishes the tree identity for the gap between two full roots by first showing that no active bits of an interior tight class fall into the gap [g, 2^m), so the total Hamming weight partitions into the sizes of the left and right gap sides. Using tightness and the tree edge formula for classes with active endpoints, this total size is rewritten as 1 plus the sum of dyadic pair counts across all dyadic levels j < m. Finally, because every active dyadic pair must cross from the left gap side to the right gap side, each dyadic pair count matches term-by-term with the number of pairs in the product of the two sides separated by 2^j.

  1. For any index r in Fin (g - 1), the interior offset r' = r.val + 1 satisfies 0 < r' and r' < g.

    We introduce the gap position r. Since r.val is non-negative and strictly less than g - 1, linear arithmetic establishes that r' = r.val + 1 lies strictly between 0 and g.

    lines 21–23

      intro r
      have hr₀ : 0 < r.val+1 := by omega
      have hrg : r.val+1 < g := by have := r.isLt; omega
  2. The total Hamming weight of x(r') on {0, ..., 2^m - 1} decomposes into the sum of the sizes of the left and right gap sides.

    By cycle_power_dyadic_two_full_roots_overlap_empty, any active bit a < 2^m in x(r') satisfies either r' + a < g or 2^m ≤ r' + a, meaning the intermediate gap [g, 2^m) contains no active bits. Then cycle_power_gap_sides_card uses this gap-avoidance property to equate the total Hamming weight of x(r') to the sum of the sizes of cycle_power_gap_left_side and cycle_power_gap_right_side.

    lines 24–27

    uses cycle_power_dyadic_two_full_roots_overlap_empty, cycle_power_gap_sides_card

      have hgap := cycle_power_dyadic_two_full_roots_overlap_empty
        m hm x htight hexact g hg hfull₀ hfullg (r.val+1) hr₀ hrg
      have hcard := cycle_power_gap_sides_card (2^m) g (r.val+1) hg hrg
        (x ((r.val+1 : ℕ) : ℤ)) hgap
  3. The sum of the sizes of the left and right gap sides equals 1 plus the sum over levels j < m of the dyadic pair counts.

    Exactness implies via cycle_power_dyadic_exact_endpoints that both endpoints 0 and 2^m - 1 are active in x(r'). We replace the sum of side cardinalities with the Hamming weight via the decomposition hcard, replace the Hamming weight with the dyadic class weight via the tightness hypothesis htight, and apply cycle_power_dyadic_class_weight_as_tree_edges to expand the class weight as 1 plus the sum over j < m of the dyadic pair counts.

    lines 28–29

    uses cycle_power_dyadic_exact_endpoints, cycle_power_dyadic_class_weight_as_tree_edges

      have hends := cycle_power_dyadic_exact_endpoints m hm x hexact ((r.val+1 : ℕ) : ℤ)
      rw [← hcard, ← htight, cycle_power_dyadic_class_weight_as_tree_edges m hm _ hends]
  4. It suffices to show that at each scale j < m, the dyadic pair count equals the number of pairs in the left and right gap sides with separation 2^j.

    Stripping the leading constant 1 with congr 1 reduces the goal to an equality of sums over j ∈ range m. We apply sum_congr to reduce the equality of sums to proving pointwise equality of the summands for each individual j < m.

    lines 30–32

    uses sum_congr

      congr 1
      apply sum_congr rfl
      intro j hj
  5. For each level j < m, the dyadic pair count at scale 2^j equals the number of pairs (p₁, p₂) in left_side × right_side satisfying p₂ + 2^j = p₁.

    By cycle_power_dyadic_two_full_roots_pair_crosses, every active dyadic pair at level j crosses the gap: its first index satisfies r' + a < g (placing it in the left side) and its second satisfies 2^m ≤ r' + (a + 2^m - 2^j) (placing it in the right side). Applying cycle_power_gap_sides_pair_card with R = 2^j ≤ 2^m then proves that the dyadic pair sum coincides with the number of pairs in the filtered product of the left and right gap sides with offset 2^j.

    lines 33–37

    uses cycle_power_gap_sides_pair_card, Nat.pow_le_pow_right, Nat.le_of_lt, mem_range.mp, cycle_power_dyadic_two_full_roots_pair_crosses

      exact cycle_power_gap_sides_pair_card (2^m) (2^j) g (r.val+1)
        (Nat.pow_le_pow_right (by decide) (Nat.le_of_lt (mem_range.mp hj))) hg hrg
        (x ((r.val+1 : ℕ) : ℤ))
        (cycle_power_dyadic_two_full_roots_pair_crosses m x hexact g hg
          hfull₀ hfullg (r.val+1) hr₀ hrg j (mem_range.mp hj))
cycle_power_dyadic_two_full_roots_overlap_empty
Between two full roots at distance g ≤ 2^m, no active bit of an interior class falls in the overlap gap [g, 2^m).
cycle_power_gap_sides_card
If no active bit lands in the gap [g, D), the total Hamming weight of b on range D is the sum of the cardinalities of its left and right gap sides.
cycle_power_dyadic_exact_endpoints
In an exact dyadic system, every class has both of its boundary bits (at index 0 and 2^m - 1) set to true.
cycle_power_dyadic_class_weight_as_tree_edges
When both boundary bits are true, the dyadic class weight equals 1 plus the sum over levels j < m of the dyadic pair counts.
sum_congr
Two finite sums over equal index sets are equal if their summands agree on every element of the index set.
cycle_power_gap_sides_pair_card
If every active pair of separation R crosses the gap, the number of such pairs equals the number of pairs in the left side × right side separated by R.
Nat.pow_le_pow_right
For base n > 0, exponentiation preserves non-strict inequality: i ≤ j implies n^i ≤ n^j.
Nat.le_of_lt
A strict inequality n < m implies the non-strict inequality n ≤ m.
mem_range.mp
Membership in the range {0, ..., n - 1} implies being strictly less than n.
cycle_power_dyadic_two_full_roots_pair_crosses
Between two full roots, every active dyadic pair at scale 2^j crosses the gap, having its first element below g and its second at or above 2^m.

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_gap_side_tree    (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool)    (htight : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) =      (range (2^m)).sum (fun i => (x p i).toNat))    (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1)    (g : ℕ) (hg : g ≤ 2^m)    (hfull₀ : ∀ i < 2^m, x 0 i = true)    (hfullg : ∀ i < 2^m, x (g : ℤ) i = true) :    ∀ r : Fin (g-1),      (cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ))).card +      (cycle_power_gap_right_side (2^m) g (r.val+1) (x ((r.val+1 : ℕ) : ℤ))).card =      1 + (range m).sum (fun j =>        (((cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ))).product          (cycle_power_gap_right_side (2^m) g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)))).filter            (fun p : Fin g × Fin g => p.2.val+2^j = p.1.val)).card) := by  intro r  have hr₀ : 0 < r.val+1 := by omega  have hrg : r.val+1 < g := by have := r.isLt; omega  have hgap := cycle_power_dyadic_two_full_roots_overlap_empty    m hm x htight hexact g hg hfull₀ hfullg (r.val+1) hr₀ hrg  have hcard := cycle_power_gap_sides_card (2^m) g (r.val+1) hg hrg    (x ((r.val+1 : ℕ) : ℤ)) hgap  have hends := cycle_power_dyadic_exact_endpoints m hm x hexact ((r.val+1 : ℕ) : ℤ)  rw [← hcard, ← htight, cycle_power_dyadic_class_weight_as_tree_edges m hm _ hends]  congr 1  apply sum_congr rfl  intro j hj  exact cycle_power_gap_sides_pair_card (2^m) (2^j) g (r.val+1)    (Nat.pow_le_pow_right (by decide) (Nat.le_of_lt (mem_range.mp hj))) hg hrg    (x ((r.val+1 : ℕ) : ℤ))    (cycle_power_dyadic_two_full_roots_pair_crosses m x hexact g hg      hfull₀ hfullg (r.val+1) hr₀ hrg j (mem_range.mp hj))
See it in the graphDiscuss this resultChallenge it