cycle_power_dyadic_fold_struct_step
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
- simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_fold_countConditional reduction of OP-205 to a single count identity plus a middle-bit lemma: if for every t ≥ 4 every model at exponent t+1 has…
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`.
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.
uses
cycle_power_dyadic_fold_modelhave 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
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.
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']
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).
uses
cycle_power_dyadic_fold_parentshave 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
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).
have halt : ∀ p : ℤ, x (p+1) 1 = !x p 1 := by intro p have h := yalt p simp only [hone] at h exact h
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`.
uses
lt_or_gt_of_ne,Bool.or_eq_false_iffhave 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
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.
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
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_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