cycle_power_dyadic_alternating_half_tight
In a tight, exactly dyadically covered model at exponent m+1 (m >= 1) with alternating bit 1, for every class with bit 1 both its even half and its odd half are tight at exponent m (class weight equal to cardinality).
Statement
theorem cycle_power_dyadic_alternating_half_tight (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (m+1) (x p) = (Finset.range (2^(m+1))).sum (fun a => (x p a).toNat)) (hexact : ∀ j < (m+1), ∀ v : ℤ, (Finset.range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(m+1)-2^j)).toNat) = 1) (halt : ∀ p : ℤ, x (p+1) 1 = !x p 1) (p : ℤ) (hp : x p 1 = true) (e : ℕ) (he : e < 2) : cycle_power_dyadic_class_weight m (fun b => x p (2*b+e)) = (Finset.range (2^m)).sum (fun b => (x p (2*b+e)).toNat)
- Source
- Helper for RT-1 (OP-205, arXiv:2610.15635): rungs of cycle_power_dyadic_alternating_half_model (the even and odd halves of the bit-1 classes of an alternating endpoint-only dyadic model form a model one exponent lower)
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- cycle_power_dyadic_class_weight_parity_splitFor any Boolean class b and m >= 1, with D = 2^(m+1): the dyadic class weight of b at exponent m+1, plus [b_0 and b_(D-2)] plus [b_1 and…
- 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_boundary_pair_of_alternatingIn an exactly dyadically covered model at exponent M >= 2 whose bit 1 alternates along the roots, every class has boundary pairing: offset…
- cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
- cycle_power_sum_range_doubleA sum over the first 2n indices equals the sum over n consecutive even-odd pairs.
- 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.
- Used by 1
- cycle_power_dyadic_alternating_half_modelHalf models. In a tight, exactly dyadically covered, fully covered integer Boolean class model at exponent m+1 (m ≥ 2) with m+2 active…
The proof, explained
The proof uses a parity split formula that relates the class weight at exponent m+1 to the sum of the class weights of its even and odd halves at exponent m, along with boundary correction terms. Because the model is exact and alternates on bit 1 with x(p, 1) = true, all boundary terms evaluate to 1, while tightness at exponent m+1 allows replacing the total weight with the total bit sum, which decomposes into the sum of the even and odd cardinalities. Since each half's class weight is bounded above by its cardinality and their sums coincide, both halves must attain their upper bounds with equality.
The endpoint bits x(p, 0) and x(p, 2^(m+1) - 1) are true, and the near-boundary bit x(p, 2^(m+1) - 2) equals x(p, 1).
By cycle_power_dyadic_exact_endpoints applied at exponent m + 1 (with 1 ≤ m + 1 verified by omega), exactness implies that the endpoints x(p, 0) and x(p, 2^(m+1) - 1) are both true. By cycle_power_dyadic_boundary_pair_of_alternating (with 2 ≤ m + 1 verified by omega), exactness and the alternating bit condition imply x(p, 2^(m+1) - 2) = x(p, 1).
uses
cycle_power_dyadic_exact_endpoints,cycle_power_dyadic_boundary_pair_of_alternatinghave hend := cycle_power_dyadic_exact_endpoints (m+1) (by omega) x hexact p have hH := cycle_power_dyadic_boundary_pair_of_alternating (m+1) (by omega) x hexact halt p
The sum of the cardinalities of the even and odd halves plus the two boundary terms equals twice the endpoint term plus the sum of the even and odd class weights.
We instantiate the parity split formula cycle_power_dyadic_class_weight_parity_split for x(p), which relates the class weight at exponent m + 1 to the weights of the even and odd halves at exponent m. Rewriting with the endpoint values, the boundary relation, hp (x(p, 1) = true), and htight replaces the total weight by the total bit sum over range 2^(m+1). Then, rewriting 2^(m+1) = 2 * 2^m via pow_succ, cycle_power_sum_range_double, and Finset.sum_add_distrib splits the total bit sum into the sum over even indices and the sum over odd indices.
uses
cycle_power_dyadic_class_weight_parity_split,pow_succ,cycle_power_sum_range_double,Finset.sum_add_distribhave hsplit := cycle_power_dyadic_class_weight_parity_split m hm (x p) rw [hend.1, hend.2, hH, hp, htight p] at hsplit have hpow : 2 ^ (m + 1) = 2 * 2 ^ m := by rw [pow_succ]; omega rw [hpow, cycle_power_sum_range_double, Finset.sum_add_distrib] at hsplit
Each half's class weight is bounded above by its cardinality, and the parity split equation reduces to equality between the sum of cardinalities and the sum of class weights.
By cycle_power_dyadic_class_weight_le, the class weight at exponent m of the even half is bounded above by its cardinality, and likewise for the odd half. Simplifying the boolean terms (true && true).toNat to 1 via Bool.and_self and Bool.toNat_true reduces the parity identity to (sum of even bits) + (sum of odd bits) + 1 + 1 = 2 * 1 + (even weight) + (odd weight).
uses
cycle_power_dyadic_class_weight_le,Bool.and_self,Bool.toNat_truehave hE := cycle_power_dyadic_class_weight_le m hm (fun i => x p (2 * i)) have hO := cycle_power_dyadic_class_weight_le m hm (fun i => x p (2 * i + 1)) simp only [Bool.and_self, Bool.toNat_true] at hsplit
For each e < 2, the class weight of the half b ↦ x(p, 2b + e) equals its cardinality.
We split into cases on e < 2 using interval_cases e. For e = 0, Nat.add_zero simplifies 2b + 0 to 2b. Since the even weight and odd weight are each bounded above by their respective cardinalities, and the sum of the weights equals the sum of the cardinalities, neither inequality can be strict. Linear arithmetic (omega) closes both the e = 0 and e = 1 cases.
uses
Nat.add_zerointerval_cases e · simp only [Nat.add_zero]; omega · omega
cycle_power_dyadic_exact_endpoints- In an exact dyadic model at exponent m ≥ 1, for every class p, the boundary bits x(p, 0) and x(p, 2^m - 1) are both true.
cycle_power_dyadic_boundary_pair_of_alternating- In an exact dyadic model at exponent M ≥ 2 with alternating bit 1, the near-boundary bit x(p, 2^M - 2) equals x(p, 1) for every class p.
cycle_power_dyadic_class_weight_parity_split- For any bit sequence b and m ≥ 1, the class weight at exponent m + 1 plus two boundary overlap terms equals twice the endpoint overlap plus the sum of the class weights of the even half and the odd half at exponent m.
pow_succ- In a monoid, a^(n + 1) = a^n * a.
cycle_power_sum_range_double- The sum of a function over the range 2n equals the sum over the range n of the paired even and odd values f(2i) + f(2i + 1).
Finset.sum_add_distrib- The sum of a sum of two functions over a finite set distributes into the sum of the first plus the sum of the second.
cycle_power_dyadic_class_weight_le- For m ≥ 1, the dyadic class weight of a bit sequence at exponent m is at most the sum of its bits (its cardinality) over the range 2^m.
Bool.and_self- For every boolean b, b && b = b.
Bool.toNat_true- The numerical value of the boolean true is 1.
Nat.add_zero- Adding zero to any natural number leaves it unchanged: n + 0 = n.
- In lines 20 and 21, the automated arithmetic tactic omega deduces the equality of each half with its upper bound from the facts that weight(even) ≤ sum(even), weight(odd) ≤ sum(odd), and weight(even) + weight(odd) = sum(even) + sum(odd).
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.
theorem cycle_power_dyadic_alternating_half_tight (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (m+1) (x p) = (Finset.range (2^(m+1))).sum (fun a => (x p a).toNat)) (hexact : ∀ j < (m+1), ∀ v : ℤ, (Finset.range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(m+1)-2^j)).toNat) = 1) (halt : ∀ p : ℤ, x (p+1) 1 = !x p 1) (p : ℤ) (hp : x p 1 = true) (e : ℕ) (he : e < 2) : cycle_power_dyadic_class_weight m (fun b => x p (2*b+e)) = (Finset.range (2^m)).sum (fun b => (x p (2*b+e)).toNat) := by have hend := cycle_power_dyadic_exact_endpoints (m+1) (by omega) x hexact p have hH := cycle_power_dyadic_boundary_pair_of_alternating (m+1) (by omega) x hexact halt p have hsplit := cycle_power_dyadic_class_weight_parity_split m hm (x p) rw [hend.1, hend.2, hH, hp, htight p] at hsplit have hpow : 2 ^ (m + 1) = 2 * 2 ^ m := by rw [pow_succ]; omega rw [hpow, cycle_power_sum_range_double, Finset.sum_add_distrib] at hsplit have hE := cycle_power_dyadic_class_weight_le m hm (fun i => x p (2 * i)) have hO := cycle_power_dyadic_class_weight_le m hm (fun i => x p (2 * i + 1)) simp only [Bool.and_self, Bool.toNat_true] at hsplit interval_cases e · simp only [Nat.add_zero]; omega · omega