cycle_power_dyadic_class_weight_le
For every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
Statement
theorem cycle_power_dyadic_class_weight_le (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) : cycle_power_dyadic_class_weight m b ≤ (Finset.range (2 ^ m)).sum (fun i => (b i).toNat)
- Source
- Uniform route for OP-205 and RT-1, arXiv:2610.15635 Section 3. Existing k=3,7,15 weight certificates suggest this dyadic tree. The sparse distance graph is obtained recursively by attaching one leaf to every vertex; tight classes are connected subtrees containing the distinguished endpoint edge.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 55
- cycle_power_dyadic_tight_class_pruneDeleting a tight dyadic class's middle two quarters and compressing the remaining outer quarters preserves equality between its dyadic…
- cycle_power_dyadic_prune_single_distance_coverDeleting and compressing the middle quarters preserves coverage at one fixed distance d below the new radius, using only original coverage…
- cycle_power_dyadic_neighbour_pair_count_prune_topAt the boundary rank of middle-quarter pruning, the neighbour pair count changes by exactly four boundary bits.
- cycle_power_dyadic_no_island_half_owner_orderIn a tight dyadic full-coverage class model with explicit no-island shapes, the root owning the next half-radius edge is at least the root…
- cycle_power_dyadic_no_island_cornerConditional uniform strong corner law for every cut of every dyadic radius in a tight two-interval full-cover model with exact dyadic…
- cycle_power_dyadic_class_weight_eq_of_sum_eqIf the total sum of dyadic class weights over all residues equals the total sum of active counts, then pointwise equality holds for every…
- cycle_power_dyadic_no_island_pruneDeleting middle quarters preserves the no-island property of a Boolean class.
- cycle_power_dyadic_b_lift_highMiddle-quarter pruning maps every smaller-scale right endpoint to its original larger-scale position.
- cycle_power_dyadic_no_island_of_middle_full_pruneIn a tight exact full ordinary-cover dyadic integer model, current-scale middle-bit fullness alone implies that every class has no…
- cycle_power_dyadic_weighted_threshold_tightFor positive dyadic exponent, every common-threshold profile below total mixture mass is tight when all original profiles of the…
- cycle_power_dyadic_full_prune_root_separationTwo roots whose pruned classes are full must be separated by at least one quarter of the original radius.
- cycle_power_dyadic_half_monotone_of_full_class_coverA tight exact full ordinary-cover dyadic integer model with a full class covering every vertex is monotone toward the endpoints separately…
- cycle_power_dyadic_outer_quarter_monotone_of_sixteen_block_coreConditional on upper-vertical exclusion only at dyadic block sizes h=2^j, every tight all-rank-exact fully ordinarily covered dyadic model…
- cycle_power_dyadic_no_island_middle_cornerConditional uniform corner law for every cut strictly between one quarter and one half of the dyadic radius, under tight two-interval…
- cycle_power_dyadic_prune_range_counterexampleThere is a period-12 tight radius-16 class model with exact dyadic long-edge coverage and full ordinary coverage, whose original active…
- cycle_power_dyadic_prune_full_class_cover_of_middle_fullnessCurrent-scale middle-bit fullness ensures that every vertex of the pruned model lies in a full pruned class. Fullness and half-distance…
- cycle_power_dyadic_neighbour_pair_count_prune_lowDeleting the middle two quarters preserves each strictly smaller neighbour pair count.
- cycle_power_dyadic_neighbour_weight_boundA tight rooted dyadic class satisfies a uniform weighted bound for the ordinary distances one below the dyadic long distances, with a…
- cycle_power_dyadic_outer_eighth_owner_orderIn a tight exact fully ordinarily covered dyadic model of radius2^(k+3), monotone outer eighths imply that roots owning consecutive edges…
- cycle_power_dyadic_outer_projection_pruneSuccessive direct outer projections form a compatible middle-quarter pruning hierarchy.
- cycle_power_dyadic_no_island_no_long_prefixConditional shape-model half-width theorem: a class with an initial selected interval extending strictly beyond half the radius cannot…
- cycle_power_dyadic_outer_eighth_cornerIn a tight exact fully ordinarily covered dyadic model of radius2^(k+3), suppose all outer eighths are monotone. For every root p and…
- cycle_power_dyadic_pair_count_pruneDeleting the middle two quarters preserves each smaller dyadic pair count.
- cycle_power_dyadic_full_prune_fractional_counterexampleSeventeen genuine tight radius-64 dyadic rooted profiles with positive integer multiplicities totaling1192 have expected size7, exact…
- cycle_power_dyadic_b_lift_lowMiddle-quarter pruning preserves every smaller-scale left position.
- cycle_power_dyadic_no_island_of_outer_projection_fullnessA tight exact full-coverage model has no-island class shape if every selected middle bit at EVERY direct outer projection level forces the…
- cycle_power_dyadic_neighbour_pair_count_top_boundThe largest neighbour pair count of a tight rooted class is controlled by its middle-quarter leaves and the two central bits.
- cycle_power_dyadic_prune_count_of_lower_boundIn a finite periodic tight dyadic class model with original count t+1, a pointwise lower bound t on the pruned active counts implies exact…
- cycle_power_dyadic_prune_count_iff_right_half_periodUnder the dyadic pruning balance hypotheses, preservation of active count t is equivalent to half-radius periodicity of right-half…
- simple_graph_cycle_power_dyadic_cover_class_spanningEvery label class of an optimal m+1-layer cover at dyadic bandwidth is spanned by an endpoint-distance pair: each vertex lies in a class…
- cycle_power_dyadic_tight_class_spanningA nonempty subset attaining equality in the uniform dyadic weight bound contains both endpoints of its arc.
- cycle_power_dyadic_tight_class_middle_parentEquality in the uniform dyadic class weight bound forces each selected middle-quarter position to have its matched outer-quarter parent…
- cycle_power_dyadic_half_owner_full_prune_of_middleIf every selected middle-quarter bit forces a full prune, then every class owning a half-radius edge has a full prune.
- cycle_power_dyadic_full_prune_outerFullness after middle-quarter pruning means that both outer quarters of the original class are entirely selected.
- cycle_power_dyadic_hierarchy_half_monotone_of_middle_full_pruneA compatible hierarchy of tight exact full-coverage dyadic models has monotone endpoint halves at every level, provided every selected…
- cycle_power_dyadic_half_owner_order_of_middle_full_pruneIf selected middle bits force full prunes and the retained outer quarters are monotone toward the endpoints, then coverage only at the…
- cycle_power_dyadic_outer_projection_comp_pruneA direct projection after deleting the original middle quarters equals the same direct projection of the original class at every smaller…
- cycle_power_dyadic_prune_cover_of_middle_parentIf every selected middle-quarter position has its matched outer-quarter parent selected, deleting and compressing the middle quarters…
- cycle_power_dyadic_no_island_middle_imp_full_pruneIf a tight dyadic two-interval class contains any middle-quarter vertex, deleting the middle two quarters leaves a full smaller class.…
- cycle_power_dyadic_outer_quarter_monotone_of_eight_block_extensionAssuming the local eight-block extension predicate at every positive block size, every tight exact fully ordinarily covered dyadic model…
- cycle_power_dyadic_no_island_rank_owner_orderUnder no-island class shape, tightness, exact dyadic edges and full ordinary coverage, the unique owner roots of consecutive edges are…
- 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…
- cycle_power_dyadic_prune_exactDeleting the middle two quarters of every class preserves every smaller-scale exact dyadic long-edge count, without changing the class…
- cycle_power_dyadic_outer_projection_modelEvery valid direct outer projection preserves tight dyadic weight, exact dyadic edges and full ordinary coverage. No scalar active-count…
- cycle_power_dyadic_half_monotone_of_middle_full_pruneOne uniform induction step: if all middle marks have full prunes and both retained outer quarters are monotone toward their endpoints,…
- cycle_power_dyadic_int_weight_le_cardFor a finite integer set of diameter at most 2^m-1, weight its endpoint-distance pairs by two and its other dyadic long-distance pairs by…
- cycle_power_dyadic_prune_coverDeleting each tight dyadic class's middle two quarters and compressing its outer quarters preserves coverage of all distances smaller than…
- cycle_power_dyadic_tight_class_internal_neighbourEvery selected nonendpoint offset of a tight dyadic class has a selected incident dyadic edge at some positive rank below its exponent.
- cycle_power_middle_quarter_prune_count_balanceFor a four-quarter class model with parent implications, constant original active count t+1, and exact half-distance coverage, pruning…
- simple_graph_cycle_power_dyadic_class_model_tight_weightsEvery rooted dyadic class of an optimal cover is tight: the dyadic class weight of the arc equals its cardinality.
- cycle_power_dyadic_alternating_half_tightIn 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…
- cycle_power_dyadic_end_shell_fullness_of_no_islandConversely, no-island shape in a tight exact full-coverage dyadic model forces both complete dyadic end blocks whenever either next-shell…
- cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_monoCurrent middle-bit fullness and monotonicity of both halves of the pruned model imply monotonicity of both original halves, in a tight…
- cycle_power_dyadic_prune_count_balanceTight dyadic classes with constant active count t+1 and exact half-distance coverage satisfy the exact pruning balance…
- 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…
The proof, explained
The theorem is proved by induction on the scale m = k + 1. For the step from scale k + 1 to scale k + 2, a lifted sequence of length 2^(k+1) is constructed by discarding the two middle blocks of length 2^k and concatenating the first and fourth blocks. The dyadic weight at scale k + 2 decomposes into the weight of the lifted sequence plus a cross-block correlation term; by the induction hypothesis and blockwise bounding, the lifted weight accounts for the first and fourth blocks while the cross-block terms are bounded by the second and third blocks, totaling at most the sum over the entire scale 2^(k+2).
For any booleans x and y, (x ∧ y).toNat ≤ x.toNat.
Checked by case exhaustion over the four possible boolean combinations of x and y.
cases x <;> cases y <;> decide
For any booleans x and y, (x ∧ y).toNat ≤ y.toNat.
Checked by case exhaustion over the four possible boolean combinations of x and y.
cases x <;> cases y <;> decide
The sum of f over range 4L decomposes into the sum of four blocks of length L, starting at 0, L, 2L, and 3L.
Partitioning 4L as L + (L + (L + L)) and applying sum_range_add three times breaks the sum into four intervals of length L. Presburger arithmetic simplifies the offset indices L + (L + x) = 2L + x and L + (L + (L + x)) = 3L + x.
uses
sum_range_addhave h4 : 4 * L = L + (L + (L + L)) := by omega rw [h4] rw [sum_range_add, sum_range_add, sum_range_add] have h2 : (fun x => f (L + (L + x))) = (fun x => f (2 * L + x)) := by funext x; congr 1; omega have h3 : (fun x => f (L + (L + (L + x)))) = (fun x => f (3 * L + x)) := by funext x; congr 1; omega rw [h2, h3] omega
The lifted sequence matches b at the boundaries: b_lift(0) = b(0) and b_lift(2^(k+1) - 1) = b(2^(k+2) - 1).
At index 0, since 0 < 2^k, the definition of cycle_power_dyadic_b_lift takes the first branch giving b(0). At the right boundary 2^(k+1) - 1, the index is at least 2^k, so it shifts by 2^(k+1), giving index (2^(k+1) - 1) + 2^(k+1) = 2^(k+2) - 1.
uses
pow_succ',mul_comm,Nat.two_pow_pos,if_pos,Nat.one_le_two_pow,if_neg,not_lt_of_gehave hk1 : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ', mul_comm] have hk2 : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ', mul_comm] have hpos : 0 < 2 ^ k := Nat.two_pow_pos k have h_b0 : cycle_power_dyadic_b_lift k b 0 = b 0 := by dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hpos] have h_last : cycle_power_dyadic_b_lift k b (2 ^ (k + 1) - 1) = b (2 ^ (k + 2) - 1) := by dsimp [cycle_power_dyadic_b_lift] have hge : 2 ^ k ≤ 2 ^ (k + 1) - 1 := by have : 1 ≤ 2 ^ k := Nat.one_le_two_pow; omega rw [if_neg (not_lt_of_ge hge)] congr 1 have : 1 ≤ 2 ^ (k + 1) := Nat.one_le_two_pow; omega
The dyadic class weight at scale k + 2 isolates the top scale term as the cross-block sum over range 2^(k+1).
Unfolding cycle_power_dyadic_class_weight and separating the j = k + 1 term using sum_range_succ yields the remaining sum for j ≤ k plus the top scale term. Since k + 1 ≠ 0, the top scale conditional reduces to the cross-block sum with offset 2^(k+2) - 2^(k+1) = 2^(k+1).
uses
sum_range_succ,if_neg,Nat.succ_ne_zerounfold cycle_power_dyadic_class_weight rw [sum_range_succ] have h_last_term : (if k + 1 = 0 then 0 else ∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 2) - 2 ^ (k + 1))).toNat) = ∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat := by rw [if_neg (Nat.succ_ne_zero k)] congr 1 ext i congr 2 congr 1 omega rw [h_last_term]
For each scale j ≤ k, the dyadic weight terms of b match those of the lifted sequence.
For j = 0 both terms are zero. For 0 < j ≤ k and i < 2^j ≤ 2^k, the first index i < 2^k so the lift equals b(i). The second index i + 2^(k+1) - 2^j is at least 2^k, so the lift shifts it by 2^(k+1) to i + 2^(k+2) - 2^j, exactly matching the term for b.
uses
sum_congr,mem_range,Nat.lt_succ_iff.mp,Nat.pow_le_pow_right,lt_of_lt_of_le,if_pos,if_neg,not_lt_of_gehave h_sum_eq : (∑ j ∈ range (k + 1), if j = 0 then 0 else ∑ i ∈ range (2 ^ j), (b i && b (i + 2 ^ (k + 2) - 2 ^ j)).toNat) = (∑ j ∈ range (k + 1), if j = 0 then 0 else ∑ i ∈ range (2 ^ j), (cycle_power_dyadic_b_lift k b i && cycle_power_dyadic_b_lift k b (i + 2 ^ (k + 1) - 2 ^ j)).toNat) := by apply sum_congr rfl intro j hj simp only [mem_range] at hj have hj_le : j ≤ k := Nat.lt_succ_iff.mp hj split_ifs with hj0 · rfl · apply sum_congr rfl intro i hi simp only [mem_range] at hi have hi_lt : i < 2 ^ k := by have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le exact lt_of_lt_of_le hi this have h1 : cycle_power_dyadic_b_lift k b i = b i := by dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hi_lt] have hge : 2 ^ k ≤ i + 2 ^ (k + 1) - 2 ^ j := by have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le omega have h2 : cycle_power_dyadic_b_lift k b (i + 2 ^ (k + 1) - 2 ^ j) = b (i + 2 ^ (k + 2) - 2 ^ j) := by dsimp [cycle_power_dyadic_b_lift] rw [if_neg (not_lt_of_ge hge)] congr 1 have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le omega rw [h1, h2]
The dyadic class weight at scale k + 2 equals the class weight of the lifted sequence at scale k + 1 plus the cross-block sum over range 2^(k+1).
Substituting the boundary evaluations and the term-by-term equality of the sums for j ≤ k into the unfolded class weight expression completes the recurrence relation.
rw [h_b0, h_last, h_sum_eq] omega
Setting L = 2^k, the range 2^(k+1) splits into two blocks of length L for both the lifted sum and the cross-block sum.
Expressing 2^(k+1) = L + L and 2^(k+2) = 4L via power and multiplication lemmas, sum_range_add decomposes both the lifted sum and the cross-block sum into two sums over range L.
uses
pow_succ',two_mul,pow_add,mul_comm,sum_range_addlet L := 2 ^ k have hk1 : 2 ^ (k + 1) = L + L := by show 2 ^ (k + 1) = 2 ^ k + 2 ^ k rw [pow_succ', two_mul] have hk2 : 2 ^ (k + 2) = 4 * L := by show 2 ^ (k + 2) = 4 * 2 ^ k calc 2 ^ (k + 2) = 2 ^ k * 2 ^ 2 := pow_add 2 k 2 _ = 2 ^ k * 4 := rfl _ = 4 * 2 ^ k := mul_comm _ _ rw [hk1] rw [sum_range_add, sum_range_add]
The two blocks of the lifted sequence equal block 0 and block 3 of b, respectively.
On [0, L), the lift index satisfies i < 2^k, so the lift equals b(i). On [L, 2L), the index L + i ≥ 2^k, so the lift shifts by 2^(k+1) = 2L, resulting in b(3L + i).
uses
sum_congr,mem_range,if_pos,if_neg,not_lt_of_ge,pow_succ',mul_commhave h_lift1 : (∑ i ∈ range L, (cycle_power_dyadic_b_lift k b i).toNat) = ∑ i ∈ range L, (b i).toNat := by apply sum_congr rfl intro i hi simp only [mem_range] at hi dsimp [cycle_power_dyadic_b_lift, L] at * rw [if_pos hi] have h_lift2 : (∑ i ∈ range L, (cycle_power_dyadic_b_lift k b (L + i)).toNat) = ∑ i ∈ range L, (b (3 * L + i)).toNat := by apply sum_congr rfl intro i hi dsimp [cycle_power_dyadic_b_lift] have hge : 2 ^ k ≤ L + i := by dsimp [L]; omega rw [if_neg (not_lt_of_ge hge)] congr 2 have : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ', mul_comm] dsimp [L] omega
The two halves of the cross-block sum are bounded by block 2 and block 1 of b, respectively.
Using pointwise boolean inequalities (x ∧ y).toNat ≤ y.toNat and (x ∧ y).toNat ≤ x.toNat, the first cross block (b(i) ∧ b(2L+i)).toNat is bounded by b(2L+i).toNat (block 2), and the second cross block (b(L+i) ∧ b(3L+i)).toNat is bounded by b(L+i).toNat (block 1).
uses
sum_le_sum,cycle_power_dyadic_bool_and_toNat_le_right,cycle_power_dyadic_bool_and_toNat_le_lefthave h_cross1 : (∑ i ∈ range L, (b i && b (i + (L + L))).toNat) ≤ ∑ i ∈ range L, (b (2 * L + i)).toNat := by apply sum_le_sum intro i hi have : i + (L + L) = 2 * L + i := by omega rw [this] exact cycle_power_dyadic_bool_and_toNat_le_right (b i) (b (2 * L + i)) have h_cross2 : (∑ i ∈ range L, (b (L + i) && b (L + i + (L + L))).toNat) ≤ ∑ i ∈ range L, (b (L + i)).toNat := by apply sum_le_sum intro i hi exact cycle_power_dyadic_bool_and_toNat_le_left (b (L + i)) (b (L + i + (L + L)))
The lifted sequence sum plus the cross-block sum is at most the total sum of b over range 2^(k+2).
Combining the evaluations of the lifted blocks (blocks 0 and 3) with the bounds on the cross blocks (blocks 2 and 1) gives the sum of all four length-L blocks, which equals the total sum over range 4L = 2^(k+2) by cycle_power_dyadic_sum_range_four_blocks.
uses
cycle_power_dyadic_sum_range_four_blocksrw [h_lift1, h_lift2] rw [hk2] rw [cycle_power_dyadic_sum_range_four_blocks] omega
For k = 0, the dyadic class weight at scale 1 is at most the number of selected positions in range 2.
At scale 1, the weight simplifies to 2 * (b(0) ∧ b(1)).toNat, while the range sum is b(0).toNat + b(1).toNat. Exhaustive boolean evaluation confirms the inequality 2(b_0 ∧ b_1) ≤ b_0 + b_1 in all four cases.
uses
sum_range_one,ite_true,add_zero,sum_range_succinduction k generalizing b with | zero => unfold cycle_power_dyadic_class_weight rw [sum_range_one] simp only [ite_true, add_zero] norm_num rw [sum_range_succ, sum_range_one] cases b 0 <;> cases b 1 <;> decide
If the weight bound holds at scale k + 1, it also holds at scale k + 2.
By the recurrence cycle_power_dyadic_class_weight_succ, the weight at scale k + 2 splits into the lifted weight at scale k + 1 plus the cross term. The induction hypothesis bounds the lifted weight by the sum of the lifted sequence, and cycle_power_dyadic_sum_lift_and_cross_le bounds that sum plus the cross term by the sum of b over range 2^(k+2).
uses
cycle_power_dyadic_class_weight_succ,le_trans,add_le_add_left,cycle_power_dyadic_sum_lift_and_cross_le| succ k ih => rw [cycle_power_dyadic_class_weight_succ] exact le_trans (add_le_add_left (ih (cycle_power_dyadic_b_lift k b)) _) (cycle_power_dyadic_sum_lift_and_cross_le k b)For every m ≥ 1, the dyadic class weight at scale m is at most the number of selected positions in range 2^m.
Writing m = (m - 1) + 1 via Nat.sub_add_cancel, the result follows immediately from the inductive lemma cycle_power_dyadic_class_weight_le_aux with k = m - 1.
uses
Nat.sub_add_cancel,cycle_power_dyadic_class_weight_le_auxhave h : m = (m - 1) + 1 := (Nat.sub_add_cancel hm).symm rw [h] exact cycle_power_dyadic_class_weight_le_aux (m - 1) b
sum_range_add- A sum over range n + m splits into a sum over range n and an offset sum over range m.
pow_succ'- Powers satisfy a ^ (n + 1) = a * a ^ n.
mul_comm- Multiplication is commutative.
Nat.two_pow_pos- Powers of 2 are strictly positive: 0 < 2 ^ w.
if_pos- An if-then-else expression evaluates to the then-branch when the condition holds.
Nat.one_le_two_pow- Every power of two is at least 1: 1 ≤ 2 ^ n.
if_neg- An if-then-else expression evaluates to the else-branch when the condition is false.
not_lt_of_ge- If a ≤ b, then b is not strictly less than a.
sum_range_succ- A sum over range n + 1 equals the sum over range n plus the n-th term.
Nat.succ_ne_zero- The successor of a natural number is never zero: n + 1 ≠ 0.
sum_congr- Sums of pointwise equal functions over equal sets are equal.
mem_range- A natural number m belongs to range n if and only if m < n.
Nat.lt_succ_iff.mp- If j < k + 1, then j ≤ k.
Nat.pow_le_pow_right- Exponentiation with a positive base is non-decreasing in the exponent: if i ≤ j then n ^ i ≤ n ^ j.
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
two_mul- Multiplying by 2 equals adding to oneself: 2 * n = n + n.
pow_add- Exponents add under multiplication: a ^ (m + n) = a ^ m * a ^ n.
sum_le_sum- If f(i) ≤ g(i) pointwise on a finite set, then the sum of f is at most the sum of g.
cycle_power_dyadic_bool_and_toNat_le_right- For booleans x and y, (x ∧ y).toNat ≤ y.toNat.
cycle_power_dyadic_bool_and_toNat_le_left- For booleans x and y, (x ∧ y).toNat ≤ x.toNat.
cycle_power_dyadic_sum_range_four_blocks- The sum of f over range 4L decomposes into four blocks of length L starting at 0, L, 2L, and 3L.
sum_range_one- A sum over range 1 equals the evaluation at 0.
ite_true- An if-then-else with condition True evaluates to the first branch.
add_zero- Adding zero to an element leaves it unchanged: a + 0 = a.
cycle_power_dyadic_class_weight_succ- The dyadic class weight at scale k + 2 equals the class weight of the lifted sequence at scale k + 1 plus the cross-block sum over range 2 ^ (k + 1).
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
add_le_add_left- Adding a common term to both sides preserves inequality: if b ≤ c then b + a ≤ c + a.
cycle_power_dyadic_sum_lift_and_cross_le- The sum of the lifted sequence plus the cross-block sum on range 2 ^ (k + 1) is at most the total sum of b on range 2 ^ (k + 2).
Nat.sub_add_cancel- If m ≤ n, then (n - m) + m = n.
cycle_power_dyadic_class_weight_le_aux- For every natural number k, the dyadic class weight at scale k + 1 is at most the sum of b over range 2 ^ (k + 1).
- The Presburger arithmetic tactic omega automatically dispatches integer and linear inequalities on indices.
- The base case at scale 2 and the boolean inequalities are checked by finite case exhaustion (decide).
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 Finsetdef cycle_power_dyadic_b_lift (k : ℕ) (b : ℕ → Bool) : ℕ → Bool := fun x => if x < 2 ^ k then b x else b (x + 2 ^ (k + 1))lemma cycle_power_dyadic_bool_and_toNat_le_left (x y : Bool) : (x && y).toNat ≤ x.toNat := by cases x <;> cases y <;> decidelemma cycle_power_dyadic_bool_and_toNat_le_right (x y : Bool) : (x && y).toNat ≤ y.toNat := by cases x <;> cases y <;> decidelemma cycle_power_dyadic_sum_range_four_blocks (L : ℕ) (f : ℕ → ℕ) : ∑ i ∈ range (4 * L), f i = (∑ i ∈ range L, f i) + (∑ i ∈ range L, f (L + i)) + (∑ i ∈ range L, f (2 * L + i)) + (∑ i ∈ range L, f (3 * L + i)) := by have h4 : 4 * L = L + (L + (L + L)) := by omega rw [h4] rw [sum_range_add, sum_range_add, sum_range_add] have h2 : (fun x => f (L + (L + x))) = (fun x => f (2 * L + x)) := by funext x; congr 1; omega have h3 : (fun x => f (L + (L + (L + x)))) = (fun x => f (3 * L + x)) := by funext x; congr 1; omega rw [h2, h3] omegalemma cycle_power_dyadic_class_weight_succ (k : ℕ) (b : ℕ → Bool) : cycle_power_dyadic_class_weight (k + 2) b = cycle_power_dyadic_class_weight (k + 1) (cycle_power_dyadic_b_lift k b) + ∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat := by have hk1 : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ', mul_comm] have hk2 : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ', mul_comm] have hpos : 0 < 2 ^ k := Nat.two_pow_pos k have h_b0 : cycle_power_dyadic_b_lift k b 0 = b 0 := by dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hpos] have h_last : cycle_power_dyadic_b_lift k b (2 ^ (k + 1) - 1) = b (2 ^ (k + 2) - 1) := by dsimp [cycle_power_dyadic_b_lift] have hge : 2 ^ k ≤ 2 ^ (k + 1) - 1 := by have : 1 ≤ 2 ^ k := Nat.one_le_two_pow; omega rw [if_neg (not_lt_of_ge hge)] congr 1 have : 1 ≤ 2 ^ (k + 1) := Nat.one_le_two_pow; omega unfold cycle_power_dyadic_class_weight rw [sum_range_succ] have h_last_term : (if k + 1 = 0 then 0 else ∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 2) - 2 ^ (k + 1))).toNat) = ∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat := by rw [if_neg (Nat.succ_ne_zero k)] congr 1 ext i congr 2 congr 1 omega rw [h_last_term] have h_sum_eq : (∑ j ∈ range (k + 1), if j = 0 then 0 else ∑ i ∈ range (2 ^ j), (b i && b (i + 2 ^ (k + 2) - 2 ^ j)).toNat) = (∑ j ∈ range (k + 1), if j = 0 then 0 else ∑ i ∈ range (2 ^ j), (cycle_power_dyadic_b_lift k b i && cycle_power_dyadic_b_lift k b (i + 2 ^ (k + 1) - 2 ^ j)).toNat) := by apply sum_congr rfl intro j hj simp only [mem_range] at hj have hj_le : j ≤ k := Nat.lt_succ_iff.mp hj split_ifs with hj0 · rfl · apply sum_congr rfl intro i hi simp only [mem_range] at hi have hi_lt : i < 2 ^ k := by have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le exact lt_of_lt_of_le hi this have h1 : cycle_power_dyadic_b_lift k b i = b i := by dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hi_lt] have hge : 2 ^ k ≤ i + 2 ^ (k + 1) - 2 ^ j := by have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le omega have h2 : cycle_power_dyadic_b_lift k b (i + 2 ^ (k + 1) - 2 ^ j) = b (i + 2 ^ (k + 2) - 2 ^ j) := by dsimp [cycle_power_dyadic_b_lift] rw [if_neg (not_lt_of_ge hge)] congr 1 have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le omega rw [h1, h2] rw [h_b0, h_last, h_sum_eq] omegalemma cycle_power_dyadic_sum_lift_and_cross_le (k : ℕ) (b : ℕ → Bool) : (∑ i ∈ range (2 ^ (k + 1)), (cycle_power_dyadic_b_lift k b i).toNat) + (∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat) ≤ ∑ i ∈ range (2 ^ (k + 2)), (b i).toNat := by let L := 2 ^ k have hk1 : 2 ^ (k + 1) = L + L := by show 2 ^ (k + 1) = 2 ^ k + 2 ^ k rw [pow_succ', two_mul] have hk2 : 2 ^ (k + 2) = 4 * L := by show 2 ^ (k + 2) = 4 * 2 ^ k calc 2 ^ (k + 2) = 2 ^ k * 2 ^ 2 := pow_add 2 k 2 _ = 2 ^ k * 4 := rfl _ = 4 * 2 ^ k := mul_comm _ _ rw [hk1] rw [sum_range_add, sum_range_add] have h_lift1 : (∑ i ∈ range L, (cycle_power_dyadic_b_lift k b i).toNat) = ∑ i ∈ range L, (b i).toNat := by apply sum_congr rfl intro i hi simp only [mem_range] at hi dsimp [cycle_power_dyadic_b_lift, L] at * rw [if_pos hi] have h_lift2 : (∑ i ∈ range L, (cycle_power_dyadic_b_lift k b (L + i)).toNat) = ∑ i ∈ range L, (b (3 * L + i)).toNat := by apply sum_congr rfl intro i hi dsimp [cycle_power_dyadic_b_lift] have hge : 2 ^ k ≤ L + i := by dsimp [L]; omega rw [if_neg (not_lt_of_ge hge)] congr 2 have : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ', mul_comm] dsimp [L] omega have h_cross1 : (∑ i ∈ range L, (b i && b (i + (L + L))).toNat) ≤ ∑ i ∈ range L, (b (2 * L + i)).toNat := by apply sum_le_sum intro i hi have : i + (L + L) = 2 * L + i := by omega rw [this] exact cycle_power_dyadic_bool_and_toNat_le_right (b i) (b (2 * L + i)) have h_cross2 : (∑ i ∈ range L, (b (L + i) && b (L + i + (L + L))).toNat) ≤ ∑ i ∈ range L, (b (L + i)).toNat := by apply sum_le_sum intro i hi exact cycle_power_dyadic_bool_and_toNat_le_left (b (L + i)) (b (L + i + (L + L))) rw [h_lift1, h_lift2] rw [hk2] rw [cycle_power_dyadic_sum_range_four_blocks] omegalemma cycle_power_dyadic_class_weight_le_aux (k : ℕ) (b : ℕ → Bool) : cycle_power_dyadic_class_weight (k + 1) b ≤ (Finset.range (2 ^ (k + 1))).sum (fun i => (b i).toNat) := by induction k generalizing b with | zero => unfold cycle_power_dyadic_class_weight rw [sum_range_one] simp only [ite_true, add_zero] norm_num rw [sum_range_succ, sum_range_one] cases b 0 <;> cases b 1 <;> decide | succ k ih => rw [cycle_power_dyadic_class_weight_succ] exact le_trans (add_le_add_left (ih (cycle_power_dyadic_b_lift k b)) _) (cycle_power_dyadic_sum_lift_and_cross_le k b)theorem cycle_power_dyadic_class_weight_le (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) : cycle_power_dyadic_class_weight m b ≤ (Finset.range (2 ^ m)).sum (fun i => (b i).toNat) := by have h : m = (m - 1) + 1 := (Nat.sub_add_cancel hm).symm rw [h] exact cycle_power_dyadic_class_weight_le_aux (m - 1) b