AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_tight_class_inner_imp_one

theoremverified

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
Used by 1

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.

  1. 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).

    lines 7–11

    uses pow_succ', Nat.pow_le_pow_right

      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)
  2. 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`.

    lines 12–16

    uses Nat.strong_induction_on

      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 =>
  3. 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).

    lines 17–23

    uses Nat.pow_log_le_self, Nat.lt_pow_succ_log_self, pow_succ

          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
  4. 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.

    lines 24–30

    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_cancel

          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
  5. 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).

    line 31

    uses Nat.lt_or_ge

          rcases Nat.lt_or_ge j (2 ^ (m - 1)) with hlow | hup
  6. 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.

    lines 32–35

          · -- 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
  7. In the lower half, if j = 1, then b 1 = true.

    If j = 1, substituting into b j = true immediately yields b 1 = true.

    lines 36–37

            by_cases hj1' : j = 1
            · subst hj1'; exact hb
  8. 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.

    lines 38–52

    uses Nat.eq_zero_or_pos, Nat.pow_le_pow_right

            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
  9. 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.

    lines 53–54

            · exact ih (2 ^ (s + 1) - 1 - j) (by rw [← hjr]; omega) (j + 2 ^ m - 2 ^ (s + 1)) (by omega)
                (by omega) (by omega) hb'
  10. 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.

    lines 55–59

          · -- 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)
  11. 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.

    lines 60–72

    uses Nat.pow_le_pow_right

            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)
  12. 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.

    line 73

            · exact ih a (by omega) a (by omega) (by omega) (by omega) hb'
  13. 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.

    lines 74–75

      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.

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

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
See it in the graphDiscuss this resultChallenge it