AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_fold_struct_step

theoremverified

Induction step through the fold. If every model at exponent t (t ≥ 2) has alternating bit 1 and endpoint-only classes without bit 1, then so does a model at exponent t+1 provided its left count is 2^t-periodic and its two middle bits 2^t-1, 2^t vanish in classes without bit 1 (the latter may assume alternation and the vanishing of all other inner bits).

Statement

theorem cycle_power_dyadic_fold_struct_step (t : ℕ) (ht : 2 ≤ t)
    (ih : ∀ (y : ℤ → ℕ → Bool),
      (∀ p, cycle_power_dyadic_class_weight t (y p) =
        (Finset.range (2^t)).sum (fun a => (y p a).toNat)) →
      (∀ j < t, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>
        (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+2^t-2^j)).toNat) = 1) →
      (∀ d : ℕ, 1 ≤ d → d < 2^t → ∀ v : ℤ,
        ∃ a : ℕ, a < 2^t-d ∧ y (v-(a : ℤ)) a = true ∧
          y (v-(a : ℤ)) (a+d) = true) →
      (∀ v : ℤ, (Finset.range (2^t)).sum (fun a =>
        (y (v-(a : ℤ)) a).toNat) = t+1) →
      (∀ p : ℤ, y (p+1) 1 = !y p 1) ∧
      (∀ p : ℤ, y p 1 = false → ∀ j, 0 < j → j < 2^t - 1 → y p j = false))
    (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight (t+1) (x p) =
      (Finset.range (2^(t+1))).sum (fun a => (x p a).toNat))
    (hexact : ∀ j < t+1, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(t+1)-2^j)).toNat) = 1)
    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(t+1) → ∀ v : ℤ,
      ∃ a : ℕ, a < 2^(t+1)-d ∧ x (v-(a : ℤ)) a = true ∧
        x (v-(a : ℤ)) (a+d) = true)
    (hcount : ∀ v : ℤ, (Finset.range (2^(t+1))).sum (fun a =>
      (x (v-(a : ℤ)) a).toNat) = (t+1)+1)
    (hfold : ∀ v : ℤ, (Finset.range (2^t)).sum (fun a => (x (v-(a : ℤ)) a).toNat) =
      (Finset.range (2^t)).sum (fun a => (x (v+(2:ℤ)^t-(a : ℤ)) a).toNat))
    (hmid : (∀ p : ℤ, x (p+1) 1 = !x p 1) →
      (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^(t+1) - 1 → j ≠ 2^t - 1 → j ≠ 2^t →
        x p j = false) →
      ∀ p : ℤ, x p 1 = false → x p (2^t - 1) = false ∧ x p (2^t) = false) :
    (∀ p : ℤ, x (p+1) 1 = !x p 1) ∧
    (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^(t+1) - 1 → x p j = false)
Source
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). Session 2026-11-09: folding offsets modulo 2^t (experiment 19407).
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • cycle_power_dyadic_fold_modelThe fold of a tight dyadic class model. If x is a tight, exactly dyadically covered, fully covered integer Boolean class model at exponent…
  • 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

The proof, explained

The induction step projects a model x at exponent t+1 to a folded model y(p, a) = x(p, a) || x(p, a + 2^t) at exponent t, which satisfies the induction hypothesis via `cycle_power_dyadic_fold_model`. A parent-child implication from class tightness ensures that bit 1 of the folded model coincides with bit 1 of x, transferring alternation to x. The vanishing of inner bits in y then forces all inner bits of x to vanish except possibly the two middle positions 2^t-1 and 2^t, which vanish by the assumption `hmid`.

  1. The folded model y(p, a) = x(p, a) || x(p, a + 2^t) satisfies the induction hypothesis at exponent t, yielding bit-1 alternation and inner-bit vanishing for y.

    Since t ≥ 2, we have 1 ≤ t. Applying `cycle_power_dyadic_fold_model` establishes that the folded model y(p, a) := x(p, a) || x(p, a + 2^t) satisfies the four model conditions at exponent t: tightness of class weights, exactness of chord sums, distance covering, and total vertex count. The induction hypothesis (`ih`) applied to y then gives two properties: bit 1 alternates across classes (y(p+1, 1) = !y(p, 1)), and whenever y(p, 1) = false, all inner bits y(p, j) vanish for 0 < j < 2^t - 1.

    lines 32–35

    uses cycle_power_dyadic_fold_model

      have ht1 : 1 ≤ t := by omega
      obtain ⟨yt, yex, ycv, ycn⟩ :=
        cycle_power_dyadic_fold_model t ht1 x htight hexact hcover hcount hfold
      obtain ⟨yalt, yend⟩ := ih (fun p a => x p a || x p (a + 2^t)) yt yex ycv ycn
  2. The powers of 2 satisfy 2 ≤ 2^(t-1), 2^t = 2 * 2^(t-1), and 2^(t+1) = 2 * 2^t.

    Because t ≥ 2, we have t - 1 ≥ 1, so 2 = 2^1 ≤ 2^(t-1) by monotonicity of powers (`Nat.pow_le_pow_right`). The recurrence identity `pow_succ'` rewrites 2^t as 2 * 2^(t-1) and 2^(t+1) as 2 * 2^t.

    lines 36–40

    uses Nat.pow_le_pow_right, pow_succ'

      have hQ : 2 ≤ 2^(t-1) := by
        calc 2 = 2^1 := by norm_num
          _ ≤ 2^(t-1) := Nat.pow_le_pow_right (by norm_num) (by omega)
      have h2t : (2:ℕ)^t = 2 * 2^(t-1) := by rw [← pow_succ']; congr 1; omega
      have hs : (2:ℕ)^(t+1) = 2 * 2^t := by rw [pow_succ']
  3. Bit 1 of the folded model equals bit 1 of x: (x p 1 || x p (1 + 2^t)) = x p 1 for every class p.

    By `cycle_power_dyadic_fold_parents`, tightness of x(p) implies that for any index a < 2^(t-1), if x(p, a + 2^t) = true then x(p, a) = true. Since 1 < 2 ≤ 2^(t-1), this parent implication applies at a = 1. Therefore x(p, 1 + 2^t) cannot be true when x(p, 1) is false, which simplifies the disjunction x(p, 1) || x(p, 1 + 2^t) to x(p, 1).

    lines 41–47

    uses cycle_power_dyadic_fold_parents

      have hone : ∀ p : ℤ, (x p 1 || x p (1 + 2^t)) = x p 1 := by
        intro p
        have h3 := (cycle_power_dyadic_fold_parents t ht1 (x p) (htight p)).1 1 (by omega)
        revert h3
        generalize x p (1 + 2^t) = u
        generalize x p 1 = w
        cases w <;> cases u <;> simp
  4. Bit 1 of x alternates across classes: x(p+1, 1) = !x(p, 1) for all p.

    The induction hypothesis for y established y(p+1, 1) = !y(p, 1). Replacing y(·, 1) with x(·, 1) using the identity (x p 1 || x p (1 + 2^t)) = x p 1 directly yields x(p+1, 1) = !x(p, 1).

    lines 48–52

      have halt : ∀ p : ℤ, x (p+1) 1 = !x p 1 := by
        intro p
        have h := yalt p
        simp only [hone] at h
        exact h
  5. In classes where x(p, 1) = false, all inner bits x(p, j) vanish for 0 < j < 2^(t+1) - 1, except possibly the two middle bits j = 2^t - 1 and j = 2^t.

    Assume x(p, 1) = false, so y(p, 1) = false. For any index j with 0 < j < 2^(t+1) - 1 such that j ≠ 2^t - 1 and j ≠ 2^t, we compare j with 2^t via `lt_or_gt_of_ne`: - If j < 2^t, then 0 < j < 2^t - 1, so the induction hypothesis gives y(p, j) = false. Since y(p, j) = x(p, j) || x(p, j + 2^t), `Bool.or_eq_false_iff` forces x(p, j) = false. - If j > 2^t, the shifted index j' = j - 2^t satisfies 0 < j' < 2^t - 1 because j < 2^(t+1) - 1 = 2 * 2^t - 1. The induction hypothesis gives y(p, j') = false, meaning x(p, j') || x(p, j) = false, which again implies x(p, j) = false by `Bool.or_eq_false_iff`.

    lines 53–64

    uses lt_or_gt_of_ne, Bool.or_eq_false_iff

      have hpart : ∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^(t+1) - 1 → j ≠ 2^t - 1 → j ≠ 2^t →
          x p j = false := by
        intro p hp j hj1 hj2 hj3 hj4
        have hy1 : (x p 1 || x p (1 + 2^t)) = false := by rw [hone]; exact hp
        rcases lt_or_gt_of_ne hj4 with h | h
        · have h5 := yend p hy1 j hj1 (by omega)
          simp only [Bool.or_eq_false_iff] at h5
          exact h5.1
        · have h5 := yend p hy1 (j - 2^t) (by omega) (by omega)
          simp only [Bool.or_eq_false_iff] at h5
          rw [show j - 2^t + 2^t = j by omega] at h5
          exact h5.2
  6. The model x satisfies bit-1 alternation and inner-bit vanishing in classes without bit 1: for all p with x(p, 1) = false, x(p, j) = false for every 0 < j < 2^(t+1) - 1.

    The goal combines the alternation already proved with the vanishing of all inner bits. For any class p with x(p, 1) = false and any 0 < j < 2^(t+1) - 1: - If j = 2^t - 1 or j = 2^t, the middle-bit hypothesis `hmid` applies because its premises (bit-1 alternation and the vanishing of all non-middle inner bits) have been established, proving both middle bits vanish. - If j ≠ 2^t - 1 and j ≠ 2^t, the previous step directly gives x(p, j) = false.

    lines 65–71

      refine ⟨halt, ?_⟩
      intro p hp j hj1 hj2
      by_cases hj3 : j = 2^t - 1
      · rw [hj3]; exact (hmid halt hpart p hp).1
      by_cases hj4 : j = 2^t
      · rw [hj4]; exact (hmid halt hpart p hp).2
      exact hpart p hp j hj1 hj2 hj3 hj4
cycle_power_dyadic_fold_model
under the tightness, chord exactness, distance covering, vertex count, and left-count periodicity conditions at exponent t+1, the folded model y(p, a) = x(p, a) ∨ x(p, a + 2^t) satisfies the corresponding four conditions at exponent t
Nat.pow_le_pow_right
for any positive integer base n and natural numbers i ≤ j, n^i ≤ n^j
pow_succ'
in any monoid, a^(n+1) = a * a^n
cycle_power_dyadic_fold_parents
in a tight class at exponent t+1 (t ≥ 1), if an upper bit a + 2^t is true for a < 2^(t-1), then its lower parent bit a must also be true
lt_or_gt_of_ne
in a linear order, if a ≠ b then either a < b or b < a
Bool.or_eq_false_iff
for booleans x and y, x || y = false if and only if x = false and y = false

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_fold_struct_step (t : ℕ) (ht : 2 ≤ t)    (ih : ∀ (y : ℤ → ℕ → Bool),      (∀ p, cycle_power_dyadic_class_weight t (y p) =        (Finset.range (2^t)).sum (fun a => (y p a).toNat)) →      (∀ j < t, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>        (y (v-(a : ℤ)) a && y (v-(a : ℤ)) (a+2^t-2^j)).toNat) = 1) →      (∀ d : ℕ, 1 ≤ d → d < 2^t → ∀ v : ℤ,        ∃ a : ℕ, a < 2^t-d ∧ y (v-(a : ℤ)) a = true ∧          y (v-(a : ℤ)) (a+d) = true) →      (∀ v : ℤ, (Finset.range (2^t)).sum (fun a =>        (y (v-(a : ℤ)) a).toNat) = t+1) →      (∀ p : ℤ, y (p+1) 1 = !y p 1) ∧      (∀ p : ℤ, y p 1 = false → ∀ j, 0 < j → j < 2^t - 1 → y p j = false))    (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight (t+1) (x p) =      (Finset.range (2^(t+1))).sum (fun a => (x p a).toNat))    (hexact : ∀ j < t+1, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(t+1)-2^j)).toNat) = 1)    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(t+1) → ∀ v : ℤ,      ∃ a : ℕ, a < 2^(t+1)-d ∧ x (v-(a : ℤ)) a = true ∧        x (v-(a : ℤ)) (a+d) = true)    (hcount : ∀ v : ℤ, (Finset.range (2^(t+1))).sum (fun a =>      (x (v-(a : ℤ)) a).toNat) = (t+1)+1)    (hfold : ∀ v : ℤ, (Finset.range (2^t)).sum (fun a => (x (v-(a : ℤ)) a).toNat) =      (Finset.range (2^t)).sum (fun a => (x (v+(2:ℤ)^t-(a : ℤ)) a).toNat))    (hmid : (∀ p : ℤ, x (p+1) 1 = !x p 1) →      (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^(t+1) - 1 → j ≠ 2^t - 1 → j ≠ 2^t →        x p j = false) →      ∀ p : ℤ, x p 1 = false → x p (2^t - 1) = false ∧ x p (2^t) = false) :    (∀ p : ℤ, x (p+1) 1 = !x p 1) ∧    (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^(t+1) - 1 → x p j = false) := by  have ht1 : 1 ≤ t := by omega  obtain ⟨yt, yex, ycv, ycn⟩ :=    cycle_power_dyadic_fold_model t ht1 x htight hexact hcover hcount hfold  obtain ⟨yalt, yend⟩ := ih (fun p a => x p a || x p (a + 2^t)) yt yex ycv ycn  have hQ : 2 ≤ 2^(t-1) := by    calc 2 = 2^1 := by norm_num      _ ≤ 2^(t-1) := Nat.pow_le_pow_right (by norm_num) (by omega)  have h2t : (2:ℕ)^t = 2 * 2^(t-1) := by rw [← pow_succ']; congr 1; omega  have hs : (2:ℕ)^(t+1) = 2 * 2^t := by rw [pow_succ']  have hone : ∀ p : ℤ, (x p 1 || x p (1 + 2^t)) = x p 1 := by    intro p    have h3 := (cycle_power_dyadic_fold_parents t ht1 (x p) (htight p)).1 1 (by omega)    revert h3    generalize x p (1 + 2^t) = u    generalize x p 1 = w    cases w <;> cases u <;> simp  have halt : ∀ p : ℤ, x (p+1) 1 = !x p 1 := by    intro p    have h := yalt p    simp only [hone] at h    exact h  have hpart : ∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^(t+1) - 1 → j ≠ 2^t - 1 → j ≠ 2^t →      x p j = false := by    intro p hp j hj1 hj2 hj3 hj4    have hy1 : (x p 1 || x p (1 + 2^t)) = false := by rw [hone]; exact hp    rcases lt_or_gt_of_ne hj4 with h | h    · have h5 := yend p hy1 j hj1 (by omega)      simp only [Bool.or_eq_false_iff] at h5      exact h5.1    · have h5 := yend p hy1 (j - 2^t) (by omega) (by omega)      simp only [Bool.or_eq_false_iff] at h5      rw [show j - 2^t + 2^t = j by omega] at h5      exact h5.2  refine ⟨halt, ?_⟩  intro p hp j hj1 hj2  by_cases hj3 : j = 2^t - 1  · rw [hj3]; exact (hmid halt hpart p hp).1  by_cases hj4 : j = 2^t  · rw [hj4]; exact (hmid halt hpart p hp).2  exact hpart p hp j hj1 hj2 hj3 hj4
See it in the graphDiscuss this resultChallenge it