dual_melas_shift_equiv_imp_eval_mul_eval_eq
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
- dual_melas_non_degenerate_orbit_shift_equiv_iffLet k ≥ 3, let F be a finite field of order 2^k, and let α ∈ F be primitive of order 2^k - 1. For binary polynomials f and g such that f…
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(α⁻¹).
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.
rcases hsim with ⟨j, q, hq⟩
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(α).
uses
map_sub,map_mul,Polynomial.aeval_X_pow,minpoly.aeval,zero_mul,sub_eq_zero.mphave 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
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(α⁻¹).
uses
map_sub,map_mul,Polynomial.aeval_X_pow,minpoly.aeval,mul_zero,zero_mul,inv_pow,sub_eq_zero.mphave 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
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(α⁻¹).
uses
pow_ne_zero,mul_inv_cancel₀,one_mulrw [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
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.
/-- 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 _