AFTD Auto-Formalizing Theoretical Domains

quinticDecoder_eval_parity

theoremverifiedformalization

For any integer z ∈ {-1, 0, 1} and any Boolean b, the formal polynomial quinticDecoder evaluated at 2 * (z : ℝ) + bit b equals bit b.

Statement

theorem quinticDecoder_eval_parity (z : ℤ) (hz : z = -1 ∨ z = 0 ∨ z = 1) (b : Bool) :
    quinticDecoder.eval (2 * (z : ℝ) + bit b) = bit b
Formalizes
arXiv:2610.19174 Theorem 3.2.1
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • quinticDecoderThe formal polynomial quinticDecoder of type Polynomial ℝ is defined as Polynomial.C (1 / 15 : ℝ) * (Polynomial.C 2 * Polynomial.X ^ 5 -…
  • bitThe real embedding of a Boolean value, sending false to 0 and true to 1.

Read back from the Lean

For every integer $z$, assuming that $z = -1$, $z = 0$, or $z = 1$, and for every boolean $b$, evaluating the polynomial quinticDecoder at the real number $2z + \text{bit}(b)$ yields $\text{bit}(b)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem is proved by finite case analysis across all possible values of z ∈ {-1, 0, 1} and b ∈ {false, true}, yielding six cases in total. In each case, the definitions of the quintic decoder polynomial and the Boolean-to-real bit conversion are unfolded. The resulting polynomial evaluations at -2, -1, 0, 1, 2, and 3 are then verified to match the corresponding bit values (0, 1, 0, 1, 0, 1) through direct numerical calculation.

  1. For all z ∈ {-1, 0, 1} and b ∈ {false, true}, evaluating quinticDecoder at 2z + bit b gives bit b.

    The proof proceeds by finite case exhaustion. The hypothesis z = -1 ∨ z = 0 ∨ z = 1 is split into the three possible values of z, and b is split into false and true, producing six subgoals in total. Unfolding the definitions of quinticDecoder and bit reduces each subgoal to evaluating the polynomial at one of the points {-2, -1, 0, 1, 2, 3}. For z = 0 and b = false, the evaluation at 0 simplifies immediately to 0; for the remaining five cases, direct numerical calculation (via norm_num) verifies that the polynomial evaluates to the expected bit value (0 at -2 and 2; 1 at -1, 1, and 3).

    line 4

    uses quinticDecoder, bit

      rcases hz with rfl | rfl | rfl <;> cases b <;> simp [quinticDecoder, bit] <;> norm_num
quinticDecoder
The degree-5 polynomial (1/15) * (2X^5 - 5X^4 - 10X^3 + 20X^2 + 8X) over ℝ.
bit
The function mapping a Boolean value to a real number, sending true to 1 and false to 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

/-- Evaluation of the quintic decoder on points of the form 2z + b for z ∈ {-1, 0, 1}. -/theorem quinticDecoder_eval_parity (z : ℤ) (hz : z = -1 ∨ z = 0 ∨ z = 1) (b : Bool) :    quinticDecoder.eval (2 * (z : ℝ) + bit b) = bit b := by  rcases hz with rfl | rfl | rfl <;> cases b <;> simp [quinticDecoder, bit] <;> norm_num
See it in the graphDiscuss this resultChallenge it