cycle_power_dyadic_tight_class_spanning
A nonempty subset attaining equality in the uniform dyadic weight bound contains both endpoints of its arc.
Statement
theorem cycle_power_dyadic_tight_class_spanning (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) (hw : cycle_power_dyadic_class_weight m b = (Finset.range (2 ^ m)).sum (fun i => (b i).toNat)) (hne : ∃ i < 2 ^ m, b i = true) : b 0 = true ∧ b (2 ^ m - 1) = true
- 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 4
- 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_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- 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…
The proof, explained
The theorem is proved by induction on k where the scale is m = k + 1, established in an auxiliary lemma for all non-negative k. In the base case m = 1, the tightness condition forces 2 * (b 0 && b 1) = b 0 + b 1, which requires both endpoints to be true whenever at least one is true. In the induction step, the indicator b is compressed into a lifted indicator b_lift at scale k+1; a weight decomposition and the general upper bound sandwich the weight of b_lift, showing that b_lift is tight and nonempty. Applying the induction hypothesis to b_lift and reading off its endpoints through the definition of the lift proves that both endpoints of b are true.
In the base case k = 0, the dyadic weight equality reduces to 2 * (b 0 && b 1).toNat = (b 0).toNat + (b 1).toNat.
We proceed by induction on k. In the base case k = 0, the arc length is 2^1 = 2. Unfolding the definition of dyadic class weight for m = 1, the inner sum over intermediate dyadic scales contains only j = 0 and thus evaluates to 0, leaving only the boundary term 2 * (b 0 && b 1).toNat. The sum of b(i) over the range of size 2 is (b 0).toNat + (b 1).toNat. Equating the weight with the sum yields the simplified equality.
uses
Finset.sum_range_succinduction' k with k ih · intro b hw hne have hw' : 2 * (b 0 && b 1).toNat = (b 0).toNat + (b 1).toNat := by have h1 : cycle_power_dyadic_class_weight 1 b = 2 * (b 0 && b 1).toNat := by dsimp [cycle_power_dyadic_class_weight]; simp have h2 : (Finset.range (2 ^ 1)).sum (fun i => (b i).toNat) = (b 0).toNat + (b 1).toNat := by simp [Finset.sum_range_succ] linarith [hw, h1, h2]
In the base case, both endpoints b 0 and b 1 are true.
From the nonemptiness hypothesis, there exists an index i < 2 such that b i = true. If b 0 were false, then i must be 1, giving b 1 = true; substituting these into the base case equation yields 2 * 0 = 0 + 1, a contradiction. Thus b 0 = true. Similarly, if b 1 were false, then 2 * 0 = 1 + 0, another contradiction. Hence both b 0 = true and b 1 = true.
obtain ⟨i, hi, hbi⟩ := hne have h0 : b 0 = true := by by_contra h have hb0 : b 0 = false := Bool.eq_false_iff.2 h have hb1 : b 1 = true := by interval_cases i · rw [hb0] at hbi; contradiction · exact hbi rw [hb0, hb1] at hw' revert hw'; decide have h1 : b 1 = true := by by_contra h have hb1 : b 1 = false := Bool.eq_false_iff.2 h rw [h0, hb1] at hw' revert hw'; decide exact ⟨h0, h1⟩
At the induction step, the lifted indicator b_lift attains equality in the dyadic weight bound at scale k+1.
For the induction step, define b_lift by b(x) for x < 2^k and b(x + 2^(k+1)) for x ≥ 2^k. The dyadic weight at scale k+2 splits into the weight of b_lift at scale k+1 plus the sum of cross-terms b(i) && b(i + 2^(k+1)). By general bounds, the weight of b_lift is at most its sum, and the sum of b_lift plus the cross-terms is at most the total sum of b. Because b attains equality overall, each inequality in this chain must hold with equality, so b_lift is tight at scale k+1.
uses
cycle_power_dyadic_class_weight_succ,cycle_power_dyadic_class_weight_le_aux,cycle_power_dyadic_sum_lift_and_cross_le· intro b hw hne let b_lift := cycle_power_dyadic_b_lift k b have h_split := cycle_power_dyadic_class_weight_succ k b have h_le1 := cycle_power_dyadic_class_weight_le_aux k b_lift have h_le2 := cycle_power_dyadic_sum_lift_and_cross_le k b have hw_lift : cycle_power_dyadic_class_weight (k + 1) b_lift = ∑ i ∈ Finset.range (2 ^ (k + 1)), (b_lift i).toNat := by linarith [hw, h_split, h_le1, h_le2]
The lifted indicator b_lift is nonempty on the range 0 to 2^(k+1)-1.
Suppose for contradiction that b_lift is identically false on the range 0 to 2^(k+1)-1. By the definition of b_lift, this implies b(j) = false for j < 2^k and b(j + 2^(k+1)) = false for j ≥ 2^k. Consequently, every cross term b(j) && b(j + 2^(k+1)) is false, so both the sum of b_lift and the sum of cross-terms vanish. This would force the weight of b to be at most 0. But by nonemptiness of b, at least one value is true, so the total sum is at least 1, contradicting the equality between weight and sum.
uses
Finset.sum_congr,Bool.toNat_false,Bool.toNat_true,Finset.single_le_sum,Nat.zero_lehave hne_lift : ∃ j < 2 ^ (k + 1), b_lift j = true := by by_contra h have hall : ∀ j < 2 ^ (k + 1), b_lift j = false := by intro j hj have : ¬ (b_lift j = true) := fun ht => h ⟨j, hj, ht⟩ exact Bool.eq_false_iff.2 this have h_cross : ∀ j < 2 ^ (k + 1), (b j && b (j + 2 ^ (k + 1))) = false := by intro j hj dsimp [b_lift, cycle_power_dyadic_b_lift] at hall have hj_lift := hall j hj split_ifs at hj_lift with h_lt · rw [hj_lift]; rfl · rw [hj_lift]; cases b j <;> rfl have s1 : ∑ i ∈ Finset.range (2 ^ (k + 1)), (b_lift i).toNat = 0 := by rw [Finset.sum_congr rfl (fun x hx => by rw [hall x (Finset.mem_range.1 hx), Bool.toNat_false])] simp have s2 : ∑ i ∈ Finset.range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat = 0 := by rw [Finset.sum_congr rfl (fun x hx => by rw [h_cross x (Finset.mem_range.1 hx), Bool.toNat_false])] simp obtain ⟨i, hi, hbi⟩ := hne have h_sum_pos : 1 ≤ ∑ x ∈ Finset.range (2 ^ (k + 2)), (b x).toNat := by calc 1 = (b i).toNat := by rw [hbi, Bool.toNat_true] _ ≤ ∑ x ∈ Finset.range (2 ^ (k + 2)), (b x).toNat := Finset.single_le_sum (f := fun x => (b x).toNat) (fun _ _ => Nat.zero_le _) (Finset.mem_range.2 hi) linarith [hw, h_split, h_le1, s1, s2, h_sum_pos]
Both endpoints b 0 and b (2^(k+2) - 1) are true, completing the induction step.
Applying the induction hypothesis to b_lift, which is tight and nonempty at scale k+1, shows that both b_lift 0 = true and b_lift (2^(k+1) - 1) = true. Since 0 < 2^k, the definition of b_lift gives b_lift 0 = b 0. Since 2^(k+1) - 1 ≥ 2^k, the upper endpoint evaluates via the second branch to b((2^(k+1) - 1) + 2^(k+1)) = b(2^(k+2) - 1). Thus both endpoints of b are true.
uses
Nat.two_pow_pos,pow_succ,Nat.one_le_two_pow,if_neg,mul_twohave ih_res := ih b_lift hw_lift hne_lift have h0_lift : b_lift 0 = b 0 := by dsimp [b_lift, cycle_power_dyadic_b_lift] have : 0 < 2 ^ k := Nat.two_pow_pos k simp [this] have hlast_lift : b_lift (2 ^ (k + 1) - 1) = b (2 ^ (k + 2) - 1) := by dsimp [b_lift, cycle_power_dyadic_b_lift] have hge : ¬ (2 ^ (k + 1) - 1 < 2 ^ k) := by rw [pow_succ] have : 1 ≤ 2 ^ k := Nat.one_le_two_pow omega simp only [if_neg hge] congr 1 have : 2 ^ (k + 2) = 2 ^ (k + 1) + 2 ^ (k + 1) := by rw [pow_succ, mul_two] have : 1 ≤ 2 ^ (k + 1) := Nat.one_le_two_pow omega rw [h0_lift] at ih_res rw [hlast_lift] at ih_res exact ih_res
The main theorem holds for any m ≥ 1.
Using the hypothesis m ≥ 1, we write m = (m - 1) + 1 and invoke the auxiliary lemma with k = m - 1.
uses
Nat.sub_add_cancel,cycle_power_dyadic_tight_class_spanning_auxhave h : m = (m - 1) + 1 := (Nat.sub_add_cancel hm).symm rw [h] at hw hne ⊢ exact cycle_power_dyadic_tight_class_spanning_aux (m - 1) b hw hne
Bool.toNat_false- The natural number representation of the boolean value false is 0.
Bool.toNat_true- The natural number representation of the boolean value true is 1.
Finset.single_le_sum- For any non-negative function on a finite set, the value at an individual element is at most the total sum over the set.
Finset.sum_congr- If two finite sets are equal and two functions agree on every element of the set, their sums over the set are equal.
Finset.sum_range_succ- The sum of a function over the range 0 to n equals the sum over 0 to n-1 plus the term at n.
Nat.zero_le- Every natural number is greater than or equal to zero.
Nat.one_le_two_pow- Any power of two is at least one.
Nat.sub_add_cancel- Subtracting m from n and then adding m yields n, provided m ≤ n.
Nat.two_pow_pos- Any power of two is strictly positive.
cycle_power_dyadic_class_weight_le_aux- The dyadic class weight of a boolean function at scale k+1 is at most the sum of its values over the range 0 to 2^(k+1)-1.
cycle_power_dyadic_class_weight_succ- The dyadic class weight at scale k+2 decomposes as the dyadic class weight of the lifted indicator at scale k+1 plus the sum of cross terms between the lower and upper halves.
cycle_power_dyadic_sum_lift_and_cross_le- The sum of the lifted indicator plus the sum of cross terms over the lower half is bounded above by the total sum of the original function over the full range 0 to 2^(k+2)-1.
cycle_power_dyadic_tight_class_spanning_aux- A nonempty boolean function achieving equality in the dyadic weight bound at scale k+1 is true at both endpoints 0 and 2^(k+1)-1.
if_neg- If the condition of an if-then-else expression is false, the expression evaluates to the else branch.
mul_two- Multiplying a number by two is equivalent to adding the number to itself.
pow_succ- Raising a base to the power n + 1 equals the base raised to n multiplied by the base.
- In Step 3, tightness of the lifted indicator b_lift is obtained via a sandwich argument: the weight of b at scale k+2 decomposes into the weight of b_lift plus cross-terms, each bounded by their respective sums. Because the total weight matches the total sum, all intermediate inequalities must hold with equality, which linarith verifies.
- In Step 5, identifying the endpoints of b_lift with 0 and 2^(k+2)-1 depends on whether the index is below 2^k; the arithmetic on powers of two is handled by omega.
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.
lemma cycle_power_dyadic_tight_class_spanning_aux (k : ℕ) : ∀ (b : ℕ → Bool), cycle_power_dyadic_class_weight (k + 1) b = ∑ i ∈ Finset.range (2 ^ (k + 1)), (b i).toNat → (∃ i < 2 ^ (k + 1), b i = true) → b 0 = true ∧ b (2 ^ (k + 1) - 1) = true := by induction' k with k ih · intro b hw hne have hw' : 2 * (b 0 && b 1).toNat = (b 0).toNat + (b 1).toNat := by have h1 : cycle_power_dyadic_class_weight 1 b = 2 * (b 0 && b 1).toNat := by dsimp [cycle_power_dyadic_class_weight]; simp have h2 : (Finset.range (2 ^ 1)).sum (fun i => (b i).toNat) = (b 0).toNat + (b 1).toNat := by simp [Finset.sum_range_succ] linarith [hw, h1, h2] obtain ⟨i, hi, hbi⟩ := hne have h0 : b 0 = true := by by_contra h have hb0 : b 0 = false := Bool.eq_false_iff.2 h have hb1 : b 1 = true := by interval_cases i · rw [hb0] at hbi; contradiction · exact hbi rw [hb0, hb1] at hw' revert hw'; decide have h1 : b 1 = true := by by_contra h have hb1 : b 1 = false := Bool.eq_false_iff.2 h rw [h0, hb1] at hw' revert hw'; decide exact ⟨h0, h1⟩ · intro b hw hne let b_lift := cycle_power_dyadic_b_lift k b have h_split := cycle_power_dyadic_class_weight_succ k b have h_le1 := cycle_power_dyadic_class_weight_le_aux k b_lift have h_le2 := cycle_power_dyadic_sum_lift_and_cross_le k b have hw_lift : cycle_power_dyadic_class_weight (k + 1) b_lift = ∑ i ∈ Finset.range (2 ^ (k + 1)), (b_lift i).toNat := by linarith [hw, h_split, h_le1, h_le2] have hne_lift : ∃ j < 2 ^ (k + 1), b_lift j = true := by by_contra h have hall : ∀ j < 2 ^ (k + 1), b_lift j = false := by intro j hj have : ¬ (b_lift j = true) := fun ht => h ⟨j, hj, ht⟩ exact Bool.eq_false_iff.2 this have h_cross : ∀ j < 2 ^ (k + 1), (b j && b (j + 2 ^ (k + 1))) = false := by intro j hj dsimp [b_lift, cycle_power_dyadic_b_lift] at hall have hj_lift := hall j hj split_ifs at hj_lift with h_lt · rw [hj_lift]; rfl · rw [hj_lift]; cases b j <;> rfl have s1 : ∑ i ∈ Finset.range (2 ^ (k + 1)), (b_lift i).toNat = 0 := by rw [Finset.sum_congr rfl (fun x hx => by rw [hall x (Finset.mem_range.1 hx), Bool.toNat_false])] simp have s2 : ∑ i ∈ Finset.range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat = 0 := by rw [Finset.sum_congr rfl (fun x hx => by rw [h_cross x (Finset.mem_range.1 hx), Bool.toNat_false])] simp obtain ⟨i, hi, hbi⟩ := hne have h_sum_pos : 1 ≤ ∑ x ∈ Finset.range (2 ^ (k + 2)), (b x).toNat := by calc 1 = (b i).toNat := by rw [hbi, Bool.toNat_true] _ ≤ ∑ x ∈ Finset.range (2 ^ (k + 2)), (b x).toNat := Finset.single_le_sum (f := fun x => (b x).toNat) (fun _ _ => Nat.zero_le _) (Finset.mem_range.2 hi) linarith [hw, h_split, h_le1, s1, s2, h_sum_pos] have ih_res := ih b_lift hw_lift hne_lift have h0_lift : b_lift 0 = b 0 := by dsimp [b_lift, cycle_power_dyadic_b_lift] have : 0 < 2 ^ k := Nat.two_pow_pos k simp [this] have hlast_lift : b_lift (2 ^ (k + 1) - 1) = b (2 ^ (k + 2) - 1) := by dsimp [b_lift, cycle_power_dyadic_b_lift] have hge : ¬ (2 ^ (k + 1) - 1 < 2 ^ k) := by rw [pow_succ] have : 1 ≤ 2 ^ k := Nat.one_le_two_pow omega simp only [if_neg hge] congr 1 have : 2 ^ (k + 2) = 2 ^ (k + 1) + 2 ^ (k + 1) := by rw [pow_succ, mul_two] have : 1 ≤ 2 ^ (k + 1) := Nat.one_le_two_pow omega rw [h0_lift] at ih_res rw [hlast_lift] at ih_res exact ih_restheorem cycle_power_dyadic_tight_class_spanning (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) (hw : cycle_power_dyadic_class_weight m b = (Finset.range (2 ^ m)).sum (fun i => (b i).toNat)) (hne : ∃ i < 2 ^ m, b i = true) : b 0 = true ∧ b (2 ^ m - 1) = true := by have h : m = (m - 1) + 1 := (Nat.sub_add_cancel hm).symm rw [h] at hw hne ⊢ exact cycle_power_dyadic_tight_class_spanning_aux (m - 1) b hw hne