AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_defective_halves_eliminate_middle

theoremverified

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

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.

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

    lines 11–15

    uses pow_succ

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

    lines 16–17

      let v : ℤ := ((2^(t-1) : ℕ) : ℤ) - 1
      have hv : s + 2*v + 2 - ((2^t : ℕ) : ℤ) = s := by dsimp [v]; push_cast at hint ⊢; omega
  3. 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.

    lines 18–19

    uses Or.inl

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

    lines 20–21

    uses Or.inr

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

    lines 22–23

      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

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