cycle_power_dyadic_gap_side_tree
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
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- cycle_power_dyadic_two_full_roots_pair_crossesBetween full classes rooted at zero and g with g at most the dyadic radius, every selected dyadic pair of an interior root has its lower…
- cycle_power_dyadic_two_full_roots_overlap_emptyIn a tight exact dyadic model, an interior class between full roots zero and g, with g at most the radius, cannot select a vertex in the…
- cycle_power_dyadic_exact_endpointsExact ownership of all dyadic distances in a radius-2^m model with positive exponent forces both endpoints of every rooted class to be…
- cycle_power_dyadic_class_weight_as_tree_edgesFor a positive-exponent dyadic profile containing both endpoints, its weighted class count is one plus its unweighted number of selected…
- 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.
- cycle_power_gap_sides_cardIf r is below g, g is at most D, and every selected offset of a radius-D profile is localized below absolute vertex g or at least D, its…
- cycle_power_gap_sides_pair_cardFor 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…
- Used by 1
- cycle_power_dyadic_full_gap_sides_convexIn a tight exact full ordinary-coverage dyadic model, all compressed sides between full roots zero and g are intervals when g lies between…
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.
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.
intro r have hr₀ : 0 < r.val+1 := by omega have hrg : r.val+1 < g := by have := r.isLt; omega
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.
uses
cycle_power_dyadic_two_full_roots_overlap_empty,cycle_power_gap_sides_cardhave 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
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.
uses
cycle_power_dyadic_exact_endpoints,cycle_power_dyadic_class_weight_as_tree_edgeshave 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]
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.
uses
sum_congrcongr 1 apply sum_congr rfl intro j hj
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.
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_crossesexact 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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))