AFTD Auto-Formalizing Theoretical Domains

digit_exchange_walsh_root_poly_eval

theoremverified

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

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.

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

    line 6

    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.

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