cycle_power_dyadic_rank_count_balance
At every nontrivial dyadic tree rank, exact long-edge coverage is a two-term occupancy balance L_j(v)+R_j(v+D-2^j)=1, uniformly in the radius. Each term is therefore at most one.
Statement
theorem cycle_power_dyadic_rank_count_balance (m j : ℕ) (hj : 1 ≤ j) (hjm : j < m) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) = (range (2 ^ m)).sum (fun a => (x p a).toNat)) (hexact : ∀ v : ℤ, (range (2 ^ j)).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j)).toNat) = 1) : ∀ v : ℤ, (range (2 ^ (j - 1))).sum (fun a => (x (v - ((2 ^ (j - 1) + a : ℕ) : ℤ)) (2 ^ (j - 1) + a)).toNat) + (range (2 ^ (j - 1))).sum (fun a => (x (v + ((2 ^ m - 2 ^ j : ℕ) : ℤ) - ((2 ^ m - 2 ^ j + a : ℕ) : ℤ)) (2 ^ m - 2 ^ j + a)).toNat) = 1
- Source
- Uniform structural helper for OP-205 / RT-1 following arXiv:2610.15635 Section 3. This exact rank-flow identity is a helper, not a new graph covering theorem or research advance.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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_tight_class_parentEquality in the dyadic class weight bound forces all rooted-tree parent implications at every smaller dyadic scale, uniformly in the arc…
- Used by 2
- cycle_power_dyadic_boundary_pairing_of_terminal_eight_lower_boundFor any dyadic radius at least eight, a periodic tight Boolean class model with exact dyadic-edge coverage and all ordinary coverage has…
- cycle_power_dyadic_rank_right_drop_boundCoverage one step above a dyadic long distance bounds the drop in right-block occupancy by the old boundary-pair bit, after accounting for…
The proof, explained
The theorem shows that exact long-edge coverage at rank j decomposes into a balance between two occupancy sums over 2^(j-1) points that total 1. The proof splits the exact-coverage sum of length 2^j into lower and upper halves of length q = 2^(j-1). The tightness hypothesis implies parent-child implications that simplify the conjunction in each half to a single indicator: the upper half reduces to the indicators at positions q + a, while the lower half reduces to shifted indicators at d + a where d = 2^m - 2^j. Substituting both reductions back into the coverage equation yields the two-term balance.
Fix an arbitrary vertex v ∈ ℤ, define the block size q = 2^(j-1) and shift d = 2^m - 2^j, and establish 2^j = q + q and 2^j ≤ 2^m.
We introduce the vertex v and define the half-rank length q = 2^(j-1) and displacement d = 2^m - 2^j. Arithmetic on exponents shows 2^j = 2^(j-1) * 2 = q + q, and monotonicity of powers gives 2^j ≤ 2^m since j < m.
uses
pow_succ,Nat.pow_le_pow_rightintro v let q := 2 ^ (j - 1) let d := 2 ^ m - 2 ^ j have hpow : 2 ^ j = q + q := by have he : j = (j - 1) + 1 := by omega rw [he, pow_succ] dsimp [q] omega have hdm : 2 ^ j ≤ 2 ^ m := Nat.pow_le_pow_right (by decide) (by omega)
Split the exact coverage sum of length 2^j at vertex v into a lower half and an upper half, both of length q, summing to 1.
We instantiate the tightness property across all positions using cycle_power_dyadic_tight_class_parent. We then take the exact coverage hypothesis at v, replace 2^j with q + q, and split the sum over [0, q + q) into two sums over [0, q) via sum_range_add.
uses
cycle_power_dyadic_tight_class_parent,sum_range_addhave hp := fun p => cycle_power_dyadic_tight_class_parent m j hj hjm (x p) (htight p) have he := hexact v rw [hpow, sum_range_add] at he
The lower half of the sum simplifies to the sum over a ∈ [0, q) of x(v + d - (d + a), d + a).
For every index a in the lower half (a < q = 2^(j-1)), the tightness implication states that if x is true at a + 2^m - 2^j = d + a, it must also be true at a. Hence the conjunction x(v - a, a) && x(v - a, d + a) simplifies to just x(v - a, d + a). Rewriting the vertex coordinate v - a as v + d - (d + a) gives the claimed lower sum.
uses
sum_congr,mem_range.mphave hlow : (range q).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - (q + q))).toNat) = (range q).sum (fun a => (x (v + (d : ℤ) - ((d + a : ℕ) : ℤ)) (d + a)).toNat) := by apply sum_congr rfl intro a ha have haq : a < q := mem_range.mp ha have hp' := (hp (v - (a : ℤ)) a (by omega)).1 haq have hi : a + 2 ^ m - 2 ^ j = d + a := by dsimp [d]; omega have hi' : a + 2 ^ m - (q + q) = d + a := by dsimp [d]; omega have hv : v + (d : ℤ) - ((d + a : ℕ) : ℤ) = v - (a : ℤ) := by push_cast; ring rw [hi] at hp' rw [hi', hv] cases hb : x (v - (a : ℤ)) (d + a) · simp [hb] · simp [hb, hp' hb]
The upper half of the sum simplifies to the sum over a ∈ [0, q) of x(v - (q + a), q + a).
For an index in the upper half, written as q + a with a < q, the rank index satisfies 2^(j-1) ≤ q + a < 2^j. By the tightness property, an active bit at q + a forces an active bit at q + a + 2^m - 2^j. Therefore, the conjunction reduces directly to the indicator at q + a.
uses
sum_congr,mem_range.mp,Bool.true_and,congrArghave hhigh : (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a) && x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 ^ m - (q + q))).toNat) = (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat) := by apply sum_congr rfl intro a ha have haq : a < q := mem_range.mp ha have hp' := (hp (v - ((q + a : ℕ) : ℤ)) (q + a) (by omega)).2 (by omega) have hi : q + a + 2 ^ m - (q + q) = q + a + 2 ^ m - 2 ^ j := by omega rw [hi] cases hb : x (v - ((q + a : ℕ) : ℤ)) (q + a) · simp [hb] · simpa only [Bool.true_and] using congrArg Bool.toNat (hp' hb)
The sum of the upper-half and lower-half occupancy terms equals 1. automation
Substituting the simplified expressions for the lower and upper halves into the split exact-coverage equation yields lower + upper = 1. Commutativity of integer addition establishes upper + lower = 1, closing the goal.
rw [hlow, hhigh] at he change (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat) + (range q).sum (fun a => (x (v + (d : ℤ) - ((d + a : ℕ) : ℤ)) (d + a)).toNat) = 1 omega
pow_succ- For any element a of a monoid and natural number n, a^(n+1) = a^n * a.
Nat.pow_le_pow_right- For a positive base n, the power function is monotonic in the exponent: if i ≤ j, then n^i ≤ n^j.
cycle_power_dyadic_tight_class_parent- For a tight dyadic class of order m at rank j < m, an active bit at position a + 2^m - 2^j implies an active bit at position a when a < 2^(j-1), and an active bit at position a implies an active bit at a + 2^m - 2^j when 2^(j-1) ≤ a < 2^j.
sum_range_add- A sum over the range [0, n+m) splits into the sum over [0, n) plus the sum over [0, m) with indices shifted by n.
sum_congr- Two sums over finite sets are equal if the sets are equal and their summands agree at every element.
mem_range.mp- If m belongs to the range of n, then m < n.
Bool.true_and- The boolean conjunction true && b simplifies to b.
congrArg- Equality is preserved under function application: if a₁ = a₂, then f a₁ = f a₂.
- The final tactic omega handles commutativity of addition to rearrange the two sums into the syntactic order requested by the goal.
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 Finsettheorem cycle_power_dyadic_rank_count_balance (m j : ℕ) (hj : 1 ≤ j) (hjm : j < m) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) = (range (2 ^ m)).sum (fun a => (x p a).toNat)) (hexact : ∀ v : ℤ, (range (2 ^ j)).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j)).toNat) = 1) : ∀ v : ℤ, (range (2 ^ (j - 1))).sum (fun a => (x (v - ((2 ^ (j - 1) + a : ℕ) : ℤ)) (2 ^ (j - 1) + a)).toNat) + (range (2 ^ (j - 1))).sum (fun a => (x (v + ((2 ^ m - 2 ^ j : ℕ) : ℤ) - ((2 ^ m - 2 ^ j + a : ℕ) : ℤ)) (2 ^ m - 2 ^ j + a)).toNat) = 1 := by intro v let q := 2 ^ (j - 1) let d := 2 ^ m - 2 ^ j have hpow : 2 ^ j = q + q := by have he : j = (j - 1) + 1 := by omega rw [he, pow_succ] dsimp [q] omega have hdm : 2 ^ j ≤ 2 ^ m := Nat.pow_le_pow_right (by decide) (by omega) have hp := fun p => cycle_power_dyadic_tight_class_parent m j hj hjm (x p) (htight p) have he := hexact v rw [hpow, sum_range_add] at he have hlow : (range q).sum (fun a => (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - (q + q))).toNat) = (range q).sum (fun a => (x (v + (d : ℤ) - ((d + a : ℕ) : ℤ)) (d + a)).toNat) := by apply sum_congr rfl intro a ha have haq : a < q := mem_range.mp ha have hp' := (hp (v - (a : ℤ)) a (by omega)).1 haq have hi : a + 2 ^ m - 2 ^ j = d + a := by dsimp [d]; omega have hi' : a + 2 ^ m - (q + q) = d + a := by dsimp [d]; omega have hv : v + (d : ℤ) - ((d + a : ℕ) : ℤ) = v - (a : ℤ) := by push_cast; ring rw [hi] at hp' rw [hi', hv] cases hb : x (v - (a : ℤ)) (d + a) · simp [hb] · simp [hb, hp' hb] have hhigh : (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a) && x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 ^ m - (q + q))).toNat) = (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat) := by apply sum_congr rfl intro a ha have haq : a < q := mem_range.mp ha have hp' := (hp (v - ((q + a : ℕ) : ℤ)) (q + a) (by omega)).2 (by omega) have hi : q + a + 2 ^ m - (q + q) = q + a + 2 ^ m - 2 ^ j := by omega rw [hi] cases hb : x (v - ((q + a : ℕ) : ℤ)) (q + a) · simp [hb] · simpa only [Bool.true_and] using congrArg Bool.toNat (hp' hb) rw [hlow, hhigh] at he change (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat) + (range q).sum (fun a => (x (v + (d : ℤ) - ((d + a : ℕ) : ℤ)) (d + a)).toNat) = 1 omega