digit_exchange_walsh_root_poly_eval
Evaluating the root polynomial C(v^2) + (X^2+X+C c)^2 * (C(s^2) + C(t^2) X^2 + C t X) at a gives v^2 + (a^2+a+c)^2 (s^2 + t^2 a^2 + t a).
Statement
theorem digit_exchange_walsh_root_poly_eval
(m : ℕ) (c v s t a : GaloisField 2 m) :
(Polynomial.C (v ^ 2) + (Polynomial.X ^ 2 + Polynomial.X + Polynomial.C c) ^ 2 *
(Polynomial.C (s ^ 2) + Polynomial.C (t ^ 2) * Polynomial.X ^ 2 + Polynomial.C t * Polynomial.X)
: Polynomial (GaloisField 2 m)).eval a
= v ^ 2 + (a ^ 2 + a + c) ^ 2 * (s ^ 2 + t ^ 2 * a ^ 2 + t * a)- Source
- step towards op_1608_digit_exchange_walsh_le_six
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- not_is_intersective_sq_add_oneThe polynomial $X^2 + 1$ does not have an integer root modulo every positive integer (in particular modulo 3).
The proof, explained
The evaluation of the polynomial at a is established by standard simplification of polynomial evaluation in the Galois field. The evaluation homomorphism distributes over addition, multiplication, and powers, maps constant polynomials C(k) to k, and substitutes X with a, making both sides syntactically identical.
Evaluating the polynomial at a yields v² + (a² + a + c)² (s² + t² a² + t a). automation
Evaluating a polynomial at an element a distributes across addition, multiplication, and powers, replaces constant polynomials C(k) with k, and replaces the indeterminate X with a. Applying these simplification rules transforms the left-hand side directly into the right-hand side, closing the equation by reflexivity. The lemma passed to `simpa` is unused by the simplifier.
uses
not_is_intersective_sq_add_one= v ^ 2 + (a ^ 2 + a + c) ^ 2 * (s ^ 2 + t ^ 2 * a ^ 2 + t * a) := by first | exact not_is_intersective_sq_add_one | (apply not_is_intersective_sq_add_one <;> assumption) | (apply not_is_intersective_sq_add_one <;> simp_all) | simpa using not_is_intersective_sq_add_one
not_is_intersective_sq_add_one- The polynomial X² + 1 ∈ ℤ[X] is not intersective, meaning there exists a positive integer m modulo which X² + 1 has no roots.
- The proof script uses a fallback chain `first | ... | simpa using not_is_intersective_sq_add_one`, characteristic of automated proof search or repair. The lemma `not_is_intersective_sq_add_one` is an unrelated statement about roots of integer polynomials modulo integers; it is completely unused in the mathematical argument, and `simp` alone solves the goal by evaluating the polynomial.
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 digit_exchange_walsh_root_poly_eval (m : ℕ) (c v s t a : GaloisField 2 m) : (Polynomial.C (v ^ 2) + (Polynomial.X ^ 2 + Polynomial.X + Polynomial.C c) ^ 2 * (Polynomial.C (s ^ 2) + Polynomial.C (t ^ 2) * Polynomial.X ^ 2 + Polynomial.C t * Polynomial.X) : Polynomial (GaloisField 2 m)).eval a = v ^ 2 + (a ^ 2 + a + c) ^ 2 * (s ^ 2 + t ^ 2 * a ^ 2 + t * a) := by first | exact not_is_intersective_sq_add_one | (apply not_is_intersective_sq_add_one <;> assumption) | (apply not_is_intersective_sq_add_one <;> simp_all) | simpa using not_is_intersective_sq_add_one