cycle_power_dyadic_tight_class_inner_imp_one
For m ≥ 2 and a tight dyadic class b : ℕ → Bool at exponent m (class weight equal to class size) with b 1 = b (2^m - 2) and b (2i) = b (2i+1) whenever 1 ≤ i and i + 1 < 2^(m-1): every inner bit forces bit 1, i.e. if 0 < j < 2^m - 1 and b j = true then b 1 = true.
Statement
theorem cycle_power_dyadic_tight_class_inner_imp_one (m : ℕ) (hm : 2 ≤ m) (b : ℕ → Bool) (htight : cycle_power_dyadic_class_weight m b = (Finset.range (2 ^ m)).sum (fun a => (b a).toNat)) (h1 : b 1 = b (2 ^ m - 2)) (hpr : ∀ i, 1 ≤ i → i + 1 < 2 ^ (m - 1) → b (2 * i) = b (2 * i + 1)) : ∀ j, 0 < j → j < 2 ^ m - 1 → b j = true → b 1 = true
- Source
- Research thread RT-1, OP-205 (arXiv:2610.15635, Theorems 1.3-1.4: eq(C_n^k) for k+1 = 2^m, n even, (k+1) not dividing n). Helper for cycle_power_dyadic_alternating_paired_of_pairing.
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- 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_paired_of_pairingFor m ≥ 2, a tight, exactly dyadically covered integer Boolean class model x : ℤ → ℕ → Bool at exponent m with x p 1 = x p (2^m - 2) for…
The proof, explained
The proof establishes by strong induction on the boundary distance r = min(j, 2^m - 1 - j) that any inner bit j with b j = true forces b 1 = true. At dyadic scale s = ⌊log₂ r⌋, tightness of the dyadic class provides parent transfer relations between indices at scale s + 1 < m. Depending on whether j lies in the lower or upper half of the range, this transfer either lands on a boundary bit (which forces b 1 = true using the hypothesis b 1 = b (2^m - 2) combined with the pairing of adjacent bits) or reaches a bit whose boundary distance is strictly smaller than r, completing the induction.
2^m = 2 * 2^(m - 1) and 2 ≤ 2^(m - 1).
Because m ≥ 2, we rewrite 2^m as 2 * 2^(m - 1) using `pow_succ'`. Moreover, since 1 ≤ m - 1, power monotonicity (`Nat.pow_le_pow_right`) yields 2 = 2^1 ≤ 2^(m - 1).
uses
pow_succ',Nat.pow_le_pow_righthave hD : 2 ^ m = 2 * 2 ^ (m - 1) := by rw [← pow_succ']; congr 1; omega have hH : 2 ≤ 2 ^ (m - 1) := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ (m - 1) := Nat.pow_le_pow_right (by norm_num) (by omega)
It suffices to prove by strong induction on r that any inner bit j with boundary distance r = min(j, 2^m - 1 - j) and b j = true forces b 1 = true.
We state the generalized property `key`, parameterized by the distance r = min(j, 2^m - 1 - j) from j to the boundary {0, 2^m - 1}, and set up strong induction on r via `Nat.strong_induction_on`.
uses
Nat.strong_induction_onhave key : ∀ r, ∀ j, 0 < j → j < 2 ^ m - 1 → min j (2 ^ m - 1 - j) = r → b j = true → b 1 = true := by intro r induction r using Nat.strong_induction_on with | _ r ih =>
The distance r is positive and bounded by 2^(m - 1), with dyadic scale s = ⌊log₂ r⌋ satisfying 2^s ≤ r < 2^(s+1) and 2^(s+1) = 2 * 2^s.
Because 0 < j < 2^m - 1, the distance r is nonzero (`hr0`). Setting s = ⌊log₂ r⌋, `Nat.pow_log_le_self` and `Nat.lt_pow_succ_log_self` guarantee 2^s ≤ r < 2^(s+1). Rewriting with `pow_succ` gives 2^(s+1) = 2 * 2^s, and linear arithmetic shows r < 2^(m - 1).
uses
Nat.pow_log_le_self,Nat.lt_pow_succ_log_self,pow_succintro j hj0 hj1 hr hb have hr0 : r ≠ 0 := by omega set s := Nat.log 2 r with hs have hs1 : 2 ^ s ≤ r := Nat.pow_log_le_self 2 hr0 have hs2 : r < 2 ^ (s + 1) := Nat.lt_pow_succ_log_self (by norm_num) r have hsp : 2 ^ (s + 1) = 2 * 2 ^ s := by rw [pow_succ]; ring have hrH : r < 2 ^ (m - 1) := by omega
The dyadic scale satisfies s + 1 < m, and the dyadic parent transfer relations P hold at scale s + 1.
Chaining 2^s ≤ r < 2^(m - 1) using `lt_of_le_of_lt` and strict monotonicity of powers (`Nat.pow_lt_pow_iff_right`) implies s < m - 1, so s + 1 < m and 2^(s+1) ≤ 2^(m - 1) by `Nat.pow_le_pow_right`. We instantiate the theorem `cycle_power_dyadic_tight_class_parent` at scale s + 1 and simplify with `Nat.add_sub_cancel` to obtain the parent transfer relations P.
uses
lt_of_le_of_lt,Nat.pow_lt_pow_iff_right,Nat.pow_le_pow_right,cycle_power_dyadic_tight_class_parent,Nat.add_sub_cancelhave hsm : s + 1 < m := by have : 2 ^ s < 2 ^ (m - 1) := lt_of_le_of_lt hs1 hrH have := (Nat.pow_lt_pow_iff_right (by norm_num : 1 < 2)).mp this omega have hsle : 2 ^ (s + 1) ≤ 2 ^ (m - 1) := Nat.pow_le_pow_right (by norm_num) (by omega) have P := cycle_power_dyadic_tight_class_parent m (s + 1) (by omega) hsm b htight simp only [Nat.add_sub_cancel] at P
Split into cases depending on whether j is in the lower half (j < 2^(m - 1)) or the upper half (j ≥ 2^(m - 1)).
We split into two cases using `Nat.lt_or_ge`: either j < 2^(m - 1) or j ≥ 2^(m - 1).
uses
Nat.lt_or_gercases Nat.lt_or_ge j (2 ^ (m - 1)) with hlow | hup
In the lower half, j = r and truth transfers upward to the shifted bit: b (j + 2^m - 2^(s+1)) = true.
When j < 2^(m - 1), min(j, 2^m - 1 - j) = j, so j = r. Since 2^s ≤ j < 2^(s+1), the second branch of the parent relation P applies to a = j, transferring b j = true to b (j + 2^m - 2^(s+1)) = true.
· -- lower bit: j = r have hjr : j = r := by omega rw [← hjr] at hs1 hs2 hrH have hb' := (P j (by omega)).2 hs1 hb
In the lower half, if j = 1, then b 1 = true.
If j = 1, substituting into b j = true immediately yields b 1 = true.
by_cases hj1' : j = 1 · subst hj1'; exact hb
In the lower half, if j = 2^(s+1) - 1, then b 1 = true.
Since j ≠ 1, we must have 1 ≤ s (`Nat.eq_zero_or_pos`), which implies 2 ≤ 2^s (`Nat.pow_le_pow_right`). Thus j is odd: j = 2(2^s - 1) + 1. By the adjacent pairing hypothesis `hpr`, b (j - 1) = b j = true. The parent relation P applied to the even index 2(2^s - 1) ≥ 2^s transfers truth to 2(2^s - 1) + 2^m - 2^(s+1) = 2^m - 2. By hypothesis `h1` (b 1 = b (2^m - 2)), this gives b 1 = true.
uses
Nat.eq_zero_or_pos,Nat.pow_le_pow_rightby_cases hjt : j = 2 ^ (s + 1) - 1 · -- use the pairing with j - 1, whose parent is 2^m - 2 have hs0 : 1 ≤ s := by rcases Nat.eq_zero_or_pos s with h0 | h0 · rw [h0] at hjt; norm_num at hjt; omega · exact h0 have hs2' : 2 ≤ 2 ^ s := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ s := Nat.pow_le_pow_right (by norm_num) hs0 have hp := hpr (2 ^ s - 1) (by omega) (by omega) rw [show 2 * (2 ^ s - 1) + 1 = j by omega] at hp rw [← hp] at hb have := (P (2 * (2 ^ s - 1)) (by omega)).2 (by omega) hb rw [show 2 * (2 ^ s - 1) + 2 ^ m - 2 ^ (s + 1) = 2 ^ m - 2 by omega] at this rw [h1]; exact this
In the lower half, if j < 2^(s+1) - 1, then b 1 = true by induction.
The shifted bit j' = j + 2^m - 2^(s+1) has distance to the upper boundary 2^m - 1 - j' = 2^(s+1) - 1 - j. Since j ≥ 2^s and j < 2^(s+1) - 1, this distance is strictly less than r = j. Applying the strong induction hypothesis `ih` to j' gives b 1 = true.
· exact ih (2 ^ (s + 1) - 1 - j) (by rw [← hjr]; omega) (j + 2 ^ m - 2 ^ (s + 1)) (by omega) (by omega) (by omega) hb'
In the upper half, j = 2^m - 1 - r, and for a = 2^(s+1) - 1 - r we have a < 2^s and b a = true.
When j ≥ 2^(m - 1), the boundary distance is 2^m - 1 - j = r, so j = 2^m - 1 - r. Setting a = 2^(s+1) - 1 - r, we have a < 2^s (because r ≥ 2^s) and j = a + 2^m - 2^(s+1). By the first branch of the parent relation P at index a, b j = true transfers downward to b a = true.
· -- upper bit: j = 2^m - 1 - r have hjr : j = 2 ^ m - 1 - r := by omega set a := 2 ^ (s + 1) - 1 - r with ha have hja : j = a + 2 ^ m - 2 ^ (s + 1) := by omega have hb' : b a = true := (P a (by omega)).1 (by omega) (by rw [← hja]; exact hb)
In the upper half, if a = 0, then b 1 = true.
When a = 0, r = 2^(s+1) - 1. If s = 0, then r = 1 and j = 2^m - 2, so b 1 = b j = true by `h1`. If s > 0, then 2 ≤ 2^s (`Nat.pow_le_pow_right`), and j = 2(2^(m-1) - 2^s) is an even index. By the pairing hypothesis `hpr`, b (j + 1) = b j = true. Since j + 1 = 1 + 2^m - 2^(s+1) and 1 < 2^s, the first branch of P at index 1 transfers truth to b 1 = true.
uses
Nat.pow_le_pow_rightby_cases ha0 : a = 0 · by_cases hs0 : s = 0 · -- j = 2^m - 2 have h2s : 2 ^ s = 1 := by rw [hs0]; rfl have : j = 2 ^ m - 2 := by omega rw [h1, ← this]; exact hb · have hs2' : 2 ≤ 2 ^ s := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ s := Nat.pow_le_pow_right (by norm_num) (by omega) have hp := hpr (2 ^ (m - 1) - 2 ^ s) (by omega) (by omega) rw [show 2 * (2 ^ (m - 1) - 2 ^ s) = j by omega] at hp rw [hp] at hb exact (P 1 (by omega)).1 (by omega) (by rw [show 1 + 2 ^ m - 2 ^ (s + 1) = j + 1 by omega]; exact hb)
In the upper half, if a ≠ 0, then b 1 = true by induction.
When a ≠ 0, we have 0 < a < 2^s ≤ r < 2^(m - 1), so the boundary distance of a is a, which is strictly less than r. Applying the induction hypothesis `ih` to a with b a = true gives b 1 = true.
· exact ih a (by omega) a (by omega) (by omega) (by omega) hb'
For any inner bit j with b j = true, b 1 = true.
Given any inner index 0 < j < 2^m - 1 with b j = true, we specialize the induction lemma `key` with r = min(j, 2^m - 1 - j) to conclude that b 1 = true.
intro j hj0 hj1 hb exact key _ j hj0 hj1 rfl hb
pow_succ'- For any base a in a monoid and exponent n, a^(n+1) = a * a^n.
Nat.pow_le_pow_right- If n > 0 and i ≤ j, then n^i ≤ n^j.
Nat.strong_induction_on- Principle of strong (complete) induction on ℕ: to prove p(n) for all n, it suffices to prove p(n) assuming p(m) for all m < n.
Nat.pow_log_le_self- For any base b and nonzero x, b^(⌊log_b x⌋) ≤ x.
Nat.lt_pow_succ_log_self- For base b > 1 and any x, x < b^(⌊log_b x⌋ + 1).
pow_succ- For any base a in a monoid and exponent n, a^(n+1) = a^n * a.
lt_of_le_of_lt- If a ≤ b and b < c in a preorder, then a < c.
Nat.pow_lt_pow_iff_right- For base a > 1, a^n < a^m if and only if n < m.
cycle_power_dyadic_tight_class_parent- In a tight dyadic class at exponent m, at scale j with 1 ≤ j < m, for any a < 2^j: if a < 2^(j-1) then b(a + 2^m - 2^j) = true implies b(a) = true; and if a ≥ 2^(j-1) then b(a) = true implies b(a + 2^m - 2^j) = true.
Nat.add_sub_cancel- For natural numbers n and m, (n + m) - m = n.
Nat.lt_or_ge- For natural numbers n and m, either n < m or n ≥ m.
Nat.eq_zero_or_pos- For any natural number n, either n = 0 or n > 0.
- Many algebraic identities and inequality checks (such as the index shifts 2(2^s - 1) + 2^m - 2^(s+1) = 2^m - 2 and 1 + 2^m - 2^(s+1) = j + 1) are discharged automatically by the linear arithmetic tactic `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.
theorem cycle_power_dyadic_tight_class_inner_imp_one (m : ℕ) (hm : 2 ≤ m) (b : ℕ → Bool) (htight : cycle_power_dyadic_class_weight m b = (Finset.range (2 ^ m)).sum (fun a => (b a).toNat)) (h1 : b 1 = b (2 ^ m - 2)) (hpr : ∀ i, 1 ≤ i → i + 1 < 2 ^ (m - 1) → b (2 * i) = b (2 * i + 1)) : ∀ j, 0 < j → j < 2 ^ m - 1 → b j = true → b 1 = true := by have hD : 2 ^ m = 2 * 2 ^ (m - 1) := by rw [← pow_succ']; congr 1; omega have hH : 2 ≤ 2 ^ (m - 1) := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ (m - 1) := Nat.pow_le_pow_right (by norm_num) (by omega) have key : ∀ r, ∀ j, 0 < j → j < 2 ^ m - 1 → min j (2 ^ m - 1 - j) = r → b j = true → b 1 = true := by intro r induction r using Nat.strong_induction_on with | _ r ih => intro j hj0 hj1 hr hb have hr0 : r ≠ 0 := by omega set s := Nat.log 2 r with hs have hs1 : 2 ^ s ≤ r := Nat.pow_log_le_self 2 hr0 have hs2 : r < 2 ^ (s + 1) := Nat.lt_pow_succ_log_self (by norm_num) r have hsp : 2 ^ (s + 1) = 2 * 2 ^ s := by rw [pow_succ]; ring have hrH : r < 2 ^ (m - 1) := by omega have hsm : s + 1 < m := by have : 2 ^ s < 2 ^ (m - 1) := lt_of_le_of_lt hs1 hrH have := (Nat.pow_lt_pow_iff_right (by norm_num : 1 < 2)).mp this omega have hsle : 2 ^ (s + 1) ≤ 2 ^ (m - 1) := Nat.pow_le_pow_right (by norm_num) (by omega) have P := cycle_power_dyadic_tight_class_parent m (s + 1) (by omega) hsm b htight simp only [Nat.add_sub_cancel] at P rcases Nat.lt_or_ge j (2 ^ (m - 1)) with hlow | hup · -- lower bit: j = r have hjr : j = r := by omega rw [← hjr] at hs1 hs2 hrH have hb' := (P j (by omega)).2 hs1 hb by_cases hj1' : j = 1 · subst hj1'; exact hb by_cases hjt : j = 2 ^ (s + 1) - 1 · -- use the pairing with j - 1, whose parent is 2^m - 2 have hs0 : 1 ≤ s := by rcases Nat.eq_zero_or_pos s with h0 | h0 · rw [h0] at hjt; norm_num at hjt; omega · exact h0 have hs2' : 2 ≤ 2 ^ s := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ s := Nat.pow_le_pow_right (by norm_num) hs0 have hp := hpr (2 ^ s - 1) (by omega) (by omega) rw [show 2 * (2 ^ s - 1) + 1 = j by omega] at hp rw [← hp] at hb have := (P (2 * (2 ^ s - 1)) (by omega)).2 (by omega) hb rw [show 2 * (2 ^ s - 1) + 2 ^ m - 2 ^ (s + 1) = 2 ^ m - 2 by omega] at this rw [h1]; exact this · exact ih (2 ^ (s + 1) - 1 - j) (by rw [← hjr]; omega) (j + 2 ^ m - 2 ^ (s + 1)) (by omega) (by omega) (by omega) hb' · -- upper bit: j = 2^m - 1 - r have hjr : j = 2 ^ m - 1 - r := by omega set a := 2 ^ (s + 1) - 1 - r with ha have hja : j = a + 2 ^ m - 2 ^ (s + 1) := by omega have hb' : b a = true := (P a (by omega)).1 (by omega) (by rw [← hja]; exact hb) by_cases ha0 : a = 0 · by_cases hs0 : s = 0 · -- j = 2^m - 2 have h2s : 2 ^ s = 1 := by rw [hs0]; rfl have : j = 2 ^ m - 2 := by omega rw [h1, ← this]; exact hb · have hs2' : 2 ≤ 2 ^ s := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ s := Nat.pow_le_pow_right (by norm_num) (by omega) have hp := hpr (2 ^ (m - 1) - 2 ^ s) (by omega) (by omega) rw [show 2 * (2 ^ (m - 1) - 2 ^ s) = j by omega] at hp rw [hp] at hb exact (P 1 (by omega)).1 (by omega) (by rw [show 1 + 2 ^ m - 2 ^ (s + 1) = j + 1 by omega]; exact hb) · exact ih a (by omega) a (by omega) (by omega) (by omega) hb' intro j hj0 hj1 hb exact key _ j hj0 hj1 rfl hb