AFTD Auto-Formalizing Theoretical Domains

dual_melas_shift_equiv_imp_eval_mul_eval_eq

theoremverified

If binary polynomials f and g are shift-equivalent modulo the product of the minimal polynomials of α and α⁻¹, and α is nonzero, then f(α) * f(α⁻¹) = g(α) * g(α⁻¹).

Statement

theorem dual_melas_shift_equiv_imp_eval_mul_eval_eq
    {F : Type*} [Field F] [Algebra (ZMod 2) F]
    (α : F) (hα : α ≠ 0) (f g : Polynomial (ZMod 2))
    (hsim : dual_melas_shift_equiv α f g) :
    Polynomial.aeval α f * Polynomial.aeval α⁻¹ f =
      Polynomial.aeval α g * Polynomial.aeval α⁻¹ g
Source
arXiv:2610.38017 Lemma 5
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • dual_melas_shift_equivTwo binary polynomials f and g are shift-equivalent modulo the product of the minimal polynomials of α and α⁻¹ over 𝔽₂ if there exists a…
Used by 1

Read back from the Lean

For any field $F$ equipped with a $\\mathbb{Z}/2\\mathbb{Z}$-algebra structure, any non-zero element $\\alpha \\in F$, and any polynomials $f, g \\in (\\mathbb{Z}/2\\mathbb{Z})[X]$: if $f$ and $g$ satisfy dual_melas_shift_equiv α f g, then $f(\\alpha) f(\\alpha^{-1}) = g(\\alpha) g(\\alpha^{-1})$ in $F$ (where evaluation is via the algebra map Polynomial.aeval).

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

Two binary polynomials f and g are shift-equivalent when their difference f - X^j * g is a multiple of minpoly(α) * minpoly(α⁻¹). Evaluating this relation at α and α⁻¹ annihilates the right-hand side, establishing that f(α) = α^j * g(α) and f(α⁻¹) = (α^j)⁻¹ * g(α⁻¹). Multiplying these two equations together causes the factors α^j and (α^j)⁻¹ to cancel out, proving f(α) * f(α⁻¹) = g(α) * g(α⁻¹).

  1. There exist an exponent j ∈ ℕ and a polynomial q such that f - X^j * g = minpoly(α) * minpoly(α⁻¹) * q.

    Unpacking the definition of shift-equivalence (dual_melas_shift_equiv α f g) yields a shift exponent j and a quotient polynomial q witnessing that the minimal polynomial product divides f - X^j * g.

    line 8

      rcases hsim with ⟨j, q, hq⟩
  2. f(α) = α^j * g(α)

    Evaluating both sides of f - X^j * g = minpoly(α) * minpoly(α⁻¹) * q at α turns the left-hand side into f(α) - α^j * g(α). Since evaluation is a homomorphism and minpoly(α)(α) = 0, the right-hand side simplifies to 0, which implies f(α) = α^j * g(α).

    lines 9–13

    uses map_sub, map_mul, Polynomial.aeval_X_pow, minpoly.aeval, zero_mul, sub_eq_zero.mp

      have h1 : Polynomial.aeval α (f - Polynomial.X ^ j * g) =
          Polynomial.aeval α (minpoly (ZMod 2) α * minpoly (ZMod 2) α⁻¹ * q) := by
        rw [hq]
      simp only [map_sub, map_mul, Polynomial.aeval_X_pow, minpoly.aeval, zero_mul] at h1
      have hα_eval : Polynomial.aeval α f = α ^ j * Polynomial.aeval α g := sub_eq_zero.mp h1
  3. f(α⁻¹) = (α^j)⁻¹ * g(α⁻¹)

    Evaluating the same polynomial relation at α⁻¹ gives f(α⁻¹) - (α⁻¹)^j * g(α⁻¹) on the left. The right-hand side vanishes because minpoly(α⁻¹)(α⁻¹) = 0. Using (α⁻¹)^j = (α^j)⁻¹, this yields f(α⁻¹) - (α^j)⁻¹ * g(α⁻¹) = 0, so f(α⁻¹) = (α^j)⁻¹ * g(α⁻¹).

    lines 14–18

    uses map_sub, map_mul, Polynomial.aeval_X_pow, minpoly.aeval, mul_zero, zero_mul, inv_pow, sub_eq_zero.mp

      have h2 : Polynomial.aeval α⁻¹ (f - Polynomial.X ^ j * g) =
          Polynomial.aeval α⁻¹ (minpoly (ZMod 2) α * minpoly (ZMod 2) α⁻¹ * q) := by
        rw [hq]
      simp only [map_sub, map_mul, Polynomial.aeval_X_pow, minpoly.aeval, mul_zero, zero_mul, inv_pow] at h2
      have hαinv_eval : Polynomial.aeval α⁻¹ f = (α ^ j)⁻¹ * Polynomial.aeval α⁻¹ g := sub_eq_zero.mp h2
  4. f(α) * f(α⁻¹) = g(α) * g(α⁻¹)

    Substituting the evaluation formulas for f(α) and f(α⁻¹) into their product yields (α^j * g(α)) * ((α^j)⁻¹ * g(α⁻¹)). By commutativity and associativity, the scalar factors group into α^j * (α^j)⁻¹. Since α ≠ 0, α^j is nonzero, so α^j * (α^j)⁻¹ = 1, leaving g(α) * g(α⁻¹).

    lines 19–25

    uses pow_ne_zero, mul_inv_cancel₀, one_mul

      rw [hα_eval, hαinv_eval]
      have hpow_ne : α ^ j ≠ 0 := pow_ne_zero j hα
      calc
        (α ^ j * Polynomial.aeval α g) * ((α ^ j)⁻¹ * Polynomial.aeval α⁻¹ g)
          = (α ^ j * (α ^ j)⁻¹) * (Polynomial.aeval α g * Polynomial.aeval α⁻¹ g) := by ring
        _ = 1 * (Polynomial.aeval α g * Polynomial.aeval α⁻¹ g) := by rw [mul_inv_cancel₀ hpow_ne]
        _ = Polynomial.aeval α g * Polynomial.aeval α⁻¹ g := one_mul _
map_sub
A homomorphism preserves subtraction: f(a - b) = f(a) - f(b).
map_mul
A homomorphism preserves multiplication: f(x * y) = f(x) * f(y).
Polynomial.aeval_X_pow
Evaluating the monomial X^n at x gives x^n.
minpoly.aeval
The minimal polynomial of an element evaluates to zero at that element: minpoly(x)(x) = 0.
zero_mul
Multiplication by zero on the left equals zero: 0 * a = 0.
sub_eq_zero.mp
If a - b = 0, then a = b.
mul_zero
Multiplication by zero on the right equals zero: a * 0 = 0.
inv_pow
Taking the n-th power of an inverse is equal to the inverse of the n-th power: (a⁻¹)^n = (a^n)⁻¹.
pow_ne_zero
In a domain or reduced monoid with zero, if a ≠ 0, then a^n ≠ 0.
mul_inv_cancel₀
In a group with zero, if a ≠ 0, then a * a⁻¹ = 1.
one_mul
Multiplying by 1 on the left is the identity: 1 * a = a.

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

/-- Shift-equivalent polynomials have equal product of evaluations at α and α⁻¹. -/theorem dual_melas_shift_equiv_imp_eval_mul_eval_eq    {F : Type*} [Field F] [Algebra (ZMod 2) F]    (α : F) (hα : α ≠ 0) (f g : Polynomial (ZMod 2))    (hsim : dual_melas_shift_equiv α f g) :    Polynomial.aeval α f * Polynomial.aeval α⁻¹ f =      Polynomial.aeval α g * Polynomial.aeval α⁻¹ g := by  rcases hsim with ⟨j, q, hq⟩  have h1 : Polynomial.aeval α (f - Polynomial.X ^ j * g) =      Polynomial.aeval α (minpoly (ZMod 2) α * minpoly (ZMod 2) α⁻¹ * q) := by    rw [hq]  simp only [map_sub, map_mul, Polynomial.aeval_X_pow, minpoly.aeval, zero_mul] at h1  have hα_eval : Polynomial.aeval α f = α ^ j * Polynomial.aeval α g := sub_eq_zero.mp h1  have h2 : Polynomial.aeval α⁻¹ (f - Polynomial.X ^ j * g) =      Polynomial.aeval α⁻¹ (minpoly (ZMod 2) α * minpoly (ZMod 2) α⁻¹ * q) := by    rw [hq]  simp only [map_sub, map_mul, Polynomial.aeval_X_pow, minpoly.aeval, mul_zero, zero_mul, inv_pow] at h2  have hαinv_eval : Polynomial.aeval α⁻¹ f = (α ^ j)⁻¹ * Polynomial.aeval α⁻¹ g := sub_eq_zero.mp h2  rw [hα_eval, hαinv_eval]  have hpow_ne : α ^ j ≠ 0 := pow_ne_zero j hα  calc    (α ^ j * Polynomial.aeval α g) * ((α ^ j)⁻¹ * Polynomial.aeval α⁻¹ g)      = (α ^ j * (α ^ j)⁻¹) * (Polynomial.aeval α g * Polynomial.aeval α⁻¹ g) := by ring    _ = 1 * (Polynomial.aeval α g * Polynomial.aeval α⁻¹ g) := by rw [mul_inv_cancel₀ hpow_ne]    _ = Polynomial.aeval α g * Polynomial.aeval α⁻¹ g := one_mul _
See it in the graphDiscuss this resultChallenge it