cycle_power_dyadic_defective_halves_eliminate_middle
The two phase-specific defect-free half models eliminate both middle bits at a fixed root.
Statement
theorem cycle_power_dyadic_defective_halves_eliminate_middle (t : ℕ) (ht : 1 ≤ t) (x : ℤ → ℕ → Bool) (s : ℤ) (hno : ∀ (y : ℤ → ℕ → Bool) (e : ℤ → Bool) (shift : ℤ), (shift = 0 ∨ shift = (2 : ℤ)^(t-1)) → cycle_power_dyadic_defective_half_model t y e shift → ∀ v, e v = false) (h0 : cycle_power_dyadic_defective_half_model t (fun q a => x (s + 2*q + 1) (2*a)) (fun v => x (s + 2*v + 2 - ((2^t : ℕ) : ℤ)) (2^t - 1)) 0) (h1 : cycle_power_dyadic_defective_half_model t (fun q a => x (s + 2*q + 1) (2*a+1)) (fun v => x (s + 2*v + 2 - ((2^t : ℕ) : ℤ)) (2^t)) ((2 : ℤ)^(t-1))) : x s (2^t - 1) = false ∧ x s (2^t) = false
- Source
- Indexing assembly for the RT-1 middle-bit reduction.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cycle_power_dyadic_defective_half_modelA dyadic half model with a Boolean defect: lower ranks have unique owners, top-rank ownership and the active count each lose one at a…
The proof, explained
The hypothesis hno states that any defective half model at shift 0 or 2^(t - 1) must have an identically false defect function. Hypotheses h0 and h1 provide two such models whose defect functions evaluate the grid x at column indices 2^t - 1 and 2^t, respectively, and at row index s + 2*v + 2 - 2^t. Choosing the specific integer v = 2^(t - 1) - 1 causes this row index to collapse algebraically to s, so evaluating both defect-free conclusions at v immediately sets the two middle bits at root s to false.
The identity 2^t = 2 * 2^(t - 1) holds in both the natural numbers and the integers.
Since t ≥ 1, we can express t as (t - 1) + 1. Rewriting with the successor power rule pow_succ gives 2^t = 2^(t - 1) * 2 = 2 * 2^(t - 1) in ℕ. Casting this equality into ℤ preserves the relationship over the integers.
uses
pow_succhave hnat : (2:ℕ)^t = 2 * 2^(t-1) := by have hh : t = (t-1)+1 := by omega conv_lhs => rw [hh, pow_succ] omega have hint : ((2^t : ℕ) : ℤ) = 2 * ((2^(t-1) : ℕ) : ℤ) := by exact_mod_cast hnat
For v = 2^(t - 1) - 1 ∈ ℤ, the row index expression s + 2*v + 2 - 2^t simplifies to s.
Substituting v = 2^(t - 1) - 1 into the expression yields s + 2*(2^(t - 1) - 1) + 2 - 2^t = s + 2*2^(t - 1) - 2 + 2 - 2^t. Because 2^t = 2*2^(t - 1), the powers of two and the constant terms cancel out, leaving s.
let v : ℤ := ((2^(t-1) : ℕ) : ℤ) - 1 have hv : s + 2*v + 2 - ((2^t : ℕ) : ℤ) = s := by dsimp [v]; push_cast at hint ⊢; omega
x (s + 2*v + 2 - 2^t) (2^t - 1) = false.
Hypothesis h0 provides an even-phase defective half model with shift 0 whose defect function is e₀(v) = x (s + 2*v + 2 - 2^t) (2^t - 1). Applying the defect-elimination hypothesis hno with shift = 0 (using Or.inl to satisfy the disjunction shift = 0 ∨ shift = 2^(t - 1)) at point v forces e₀(v) to be false.
uses
Or.inlhave a := hno (fun q a => x (s+2*q+1) (2*a)) (fun v => x (s+2*v+2-((2^t:ℕ):ℤ)) (2^t-1)) 0 (Or.inl rfl) h0 v
x (s + 2*v + 2 - 2^t) (2^t) = false.
Hypothesis h1 provides an odd-phase defective half model with shift 2^(t - 1) whose defect function is e₁(v) = x (s + 2*v + 2 - 2^t) (2^t). Applying hno with shift = 2^(t - 1) (using Or.inr to satisfy the disjunction) at point v forces e₁(v) to be false.
uses
Or.inrhave b := hno (fun q a => x (s+2*q+1) (2*a+1)) (fun v => x (s+2*v+2-((2^t:ℕ):ℤ)) (2^t)) ((2:ℤ)^(t-1)) (Or.inr rfl) h1 v
x s (2^t - 1) = false ∧ x s (2^t) = false.
Rewriting the index s + 2*v + 2 - 2^t to s in both defect equations transforms them into x s (2^t - 1) = false and x s (2^t) = false, which together establish the conjunction.
rw [hv] at a b exact ⟨a,b⟩
pow_succ- In any monoid, raising an element to the power n + 1 equals raising it to the power n and multiplying by the element: a^(n+1) = a^n * a.
Or.inl- Constructs a proof of the disjunction P ∨ Q from a proof of the left disjunct P.
Or.inr- Constructs a proof of the disjunction P ∨ Q from a proof of the right disjunct Q.
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_defective_halves_eliminate_middle (t : ℕ) (ht : 1 ≤ t) (x : ℤ → ℕ → Bool) (s : ℤ) (hno : ∀ (y : ℤ → ℕ → Bool) (e : ℤ → Bool) (shift : ℤ), (shift = 0 ∨ shift = (2 : ℤ)^(t-1)) → cycle_power_dyadic_defective_half_model t y e shift → ∀ v, e v = false) (h0 : cycle_power_dyadic_defective_half_model t (fun q a => x (s + 2*q + 1) (2*a)) (fun v => x (s + 2*v + 2 - ((2^t : ℕ) : ℤ)) (2^t - 1)) 0) (h1 : cycle_power_dyadic_defective_half_model t (fun q a => x (s + 2*q + 1) (2*a+1)) (fun v => x (s + 2*v + 2 - ((2^t : ℕ) : ℤ)) (2^t)) ((2 : ℤ)^(t-1))) : x s (2^t - 1) = false ∧ x s (2^t) = false := by have hnat : (2:ℕ)^t = 2 * 2^(t-1) := by have hh : t = (t-1)+1 := by omega conv_lhs => rw [hh, pow_succ] omega have hint : ((2^t : ℕ) : ℤ) = 2 * ((2^(t-1) : ℕ) : ℤ) := by exact_mod_cast hnat let v : ℤ := ((2^(t-1) : ℕ) : ℤ) - 1 have hv : s + 2*v + 2 - ((2^t : ℕ) : ℤ) = s := by dsimp [v]; push_cast at hint ⊢; omega have a := hno (fun q a => x (s+2*q+1) (2*a)) (fun v => x (s+2*v+2-((2^t:ℕ):ℤ)) (2^t-1)) 0 (Or.inl rfl) h0 v have b := hno (fun q a => x (s+2*q+1) (2*a+1)) (fun v => x (s+2*v+2-((2^t:ℕ):ℤ)) (2^t)) ((2:ℤ)^(t-1)) (Or.inr rfl) h1 v rw [hv] at a b exact ⟨a,b⟩