dual_melas_eval_mul_eval_eq_imp_shift_equiv
Let $k \ge 3$, let $F$ be a finite field of order $2^k$, and let $\alpha \in F$ be a primitive $(2^k - 1)$-th root of unity. Let $f, g \in \mathbb{F}_2[X]$. If $f$ is non-degenerate with respect to $\alpha$ (i.e., $f(\alpha) \ne 0$ and $f(\alpha^{-1}) \ne 0$) and $f(\alpha) f(\alpha^{-1}) = g(\alpha) g(\alpha^{-1})$, then $f$ and $g$ are shift-equivalent modulo the product of the minimal polynomials over $\mathbb{F}_2$ of $\alpha$ and $\alpha^{-1}$ (that is, $\operatorname{minpoly}_{\mathbb{F}_2}(\alpha) \cdot \operatorname{minpoly}_{\mathbb{F}_2}(\alpha^{-1})$ divides $f - X^j g$ for some $j \in \mathbb{N}$).
Statement
theorem dual_melas_eval_mul_eval_eq_imp_shift_equiv {F : Type*} [Field F] [Fintype F] [Algebra (ZMod 2) F] (k : ℕ) (hk : 3 ≤ k) (hcard : Fintype.card F = 2 ^ k) (α : F) (hprim : IsPrimitiveRoot α (2 ^ k - 1)) (f g : Polynomial (ZMod 2)) (hnondeg : dual_melas_is_non_degenerate α f) (heval : Polynomial.aeval α f * Polynomial.aeval α⁻¹ f = Polynomial.aeval α g * Polynomial.aeval α⁻¹ g) : dual_melas_shift_equiv α f g
- Source
- arXiv:2610.38017 Lemma 5
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- dual_melas_is_non_degenerateA binary polynomial f is non-degenerate with respect to α if neither α nor α⁻¹ is a root of f under polynomial evaluation.
- 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
Let $F$ be a finite field equipped with an algebra structure over $\mathbb{Z}/2\mathbb{Z}$. Let $k \ge 3$ be a natural number such that the cardinality of $F$ is $2^k$. Let $\alpha \in F$ be a primitive $(2^k - 1)$-th root of unity. Let $f, g \in (\mathbb{Z}/2\mathbb{Z})[X]$ be polynomials.
Assume that:
1. $f$ is non-degenerate with respect to $\alpha$ (dual_melas_is_non_degenerate α f),
2. $\text{aeval}(\alpha, f) \cdot \text{aeval}(\alpha^{-1}, f) = \text{aeval}(\alpha, g) \cdot \text{aeval}(\alpha^{-1}, g)$.
Then $f$ and $g$ are shift-equivalent with respect to $\alpha$ (dual_melas_shift_equiv α f g).
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
To show that $f$ and $g$ are shift-equivalent, the ratio $w = f(\alpha) g(\alpha)^{-1} \in F^\times$ is expressed as a power of the primitive root, $w = \alpha^j$, via Lagrange's theorem in $F^\times$. Using the assumption $f(\alpha) f(\alpha^{-1}) = g(\alpha) g(\alpha^{-1})$, this implies $f(\alpha^{-1}) = \alpha^{-j} g(\alpha^{-1})$, so both $\alpha$ and $\alpha^{-1}$ are roots of $f - X^j g$, meaning their respective minimal polynomials over $\mathbb{F}_2$ divide $f - X^j g$. Finally, the two minimal polynomials are coprime because their equality would force $\alpha$ and $\alpha^{-1}$ to be Galois conjugates, implying $2^k - 1 \mid 2^i + 1$ via the Frobenius automorphism, which is arithmetically impossible for $k \ge 3$.
Set $n = 2^k - 1$ and establish that $n > 0$ and $2^k \equiv 1 \pmod n$.
Since $k \ge 3$, $2^k \ge 2^3 = 8$, so $n = 2^k - 1 \ge 7 > 0$. Rewriting $2^k = n + 1$, its remainder modulo $n$ is 1, which establishes $2^k \equiv 1 \pmod n$.
uses
Nat.pow_le_pow_right,Nat.ModEqset n := 2^k - 1 with hn have hn_pos : 0 < n := by have h8 : 8 ≤ 2^k := by calc 8 = 2^3 := by norm_num _ ≤ 2^k := Nat.pow_le_pow_right (by norm_num) hk omega have h2k : (2^k) ≡ 1 [MOD n] := by rw [Nat.ModEq] have hkn : 2^k = n + 1 := by omega rw [hkn] simp
For any $m \in \mathbb{N}$, $2^m \equiv 2^{m \bmod k} \pmod n$.
Writing $m = k (m / k) + (m \bmod k)$ by division with remainder, $2^m = (2^k)^{m / k} \cdot 2^{m \bmod k} \equiv 1^{m / k} \cdot 2^{m \bmod k} \equiv 2^{m \bmod k} \pmod n$.
uses
Nat.div_add_mod,pow_add,pow_mul,Nat.ModEq.pow,one_pow,Nat.ModEq.mul,Nat.ModEq.reflhave hreduce : (2^m) ≡ (2^(m % k)) [MOD n] := by conv_lhs => rw [← Nat.div_add_mod m k] rw [pow_add, pow_mul] have hp : (2^k)^(m/k) ≡ 1^(m/k) [MOD n] := Nat.ModEq.pow (m/k) h2k simp only [one_pow] at hp have := Nat.ModEq.mul hp (Nat.ModEq.refl (2^(m % k))) simpa using this
Assuming $n \mid (2^m + 1)$ implies $n \mid (2^{m \bmod k} + 1)$.
Suppose for contradiction that $n \mid (2^m + 1)$, so $2^m + 1 \equiv 0 \pmod n$. Since $2^m \equiv 2^{m \bmod k} \pmod n$, adding 1 gives $2^{m \bmod k} + 1 \equiv 2^m + 1 \equiv 0 \pmod n$, meaning $n$ divides $2^{m \bmod k} + 1$.
uses
Nat.ModEq,Nat.mod_eq_zero_of_dvd,Nat.ModEq.add,Nat.ModEq.refl,Nat.dvd_of_mod_eq_zerointro h have hzero : (2^m + 1) ≡ 0 [MOD n] := by rw [Nat.ModEq, Nat.mod_eq_zero_of_dvd h] simp have hred : (2^(m % k) + 1) ≡ 0 [MOD n] := by have h1 : (2^m + 1) ≡ (2^(m % k) + 1) [MOD n] := Nat.ModEq.add hreduce (Nat.ModEq.refl 1) exact h1.symm.trans hzero have hdiv : n ∣ 2^(m % k) + 1 := by rw [Nat.ModEq] at hred exact Nat.dvd_of_mod_eq_zero hred
The reduced expression satisfies $2^{m \bmod k} + 1 < n$.
Because $m \bmod k < k$, we have $m \bmod k \le k - 1$, hence $2^{m \bmod k} \le 2^{k-1}$. Since $k \ge 3$, $2^{k-1} \ge 4$, which implies $2^{k-1} + 1 < 2 \cdot 2^{k-1} - 1 = 2^k - 1 = n$. Combining these gives $2^{m \bmod k} + 1 < n$.
uses
Nat.mod_lt,Nat.pow_le_pow_right,pow_succ'have hr : m % k < k := Nat.mod_lt m (by omega) have hlt : 2^(m % k) + 1 < n := by have hle : 2^(m % k) ≤ 2^(k-1) := Nat.pow_le_pow_right (by norm_num) (by omega) have hlt2 : 2^(k-1) + 1 < n := by have hk1 : k - 1 + 1 = k := by omega have hpow : 2^k = 2 * 2^(k-1) := by conv_lhs => rw [← hk1] rw [pow_succ'] have hge : 4 ≤ 2^(k-1) := by calc 4 = 2^2 := by norm_num _ ≤ 2^(k-1) := Nat.pow_le_pow_right (by norm_num) (by omega) have hn2 : n = 2 * 2^(k-1) - 1 := by rw [hn, hpow] rw [hn2]; omega omega
Conclude that $2^k - 1$ cannot divide $2^m + 1$.
Since $2^{m \bmod k} + 1 > 0$ and $n$ divides it, $n \le 2^{m \bmod k} + 1$. But Step 4 proved $2^{m \bmod k} + 1 < n$, which is a contradiction.
uses
Nat.le_of_dvd,lt_irreflhave hpos : 0 < 2^(m % k) + 1 := by positivity have hle' : n ≤ 2^(m % k) + 1 := Nat.le_of_dvd hpos hdiv exact absurd (hlt.trans_le hle') (lt_irrefl _)
Assuming $\alpha$ and $\alpha^{-1}$ are conjugate roots yields an automorphism $\sigma \in \operatorname{Gal}(F/\mathbb{F}_2)$ with $\sigma(\alpha) = \alpha^{-1}$.
If $\alpha$ and $\alpha^{-1}$ are conjugate roots over $\mathbb{F}_2$, there exists a field automorphism $\sigma$ over $\mathbb{F}_2$ with $\sigma(\alpha^{-1}) = \alpha$. Since $\sigma$ preserves multiplication and 1, $\sigma(\alpha) \cdot \sigma(\alpha^{-1}) = 1$, which gives $\sigma(\alpha) \cdot \alpha = 1$, whence $\sigma(\alpha) = \alpha^{-1}$.
uses
IsConjRoot.exists_algEquiv,Nat.pow_le_pow_right,map_mul,mul_inv_cancel₀,map_one,eq_inv_of_mul_eq_one_leftintro hconj obtain ⟨σ, hσ⟩ := IsConjRoot.exists_algEquiv hconj have h8 : 8 ≤ 2^k := by calc 8 = 2^3 := by norm_num _ ≤ 2^k := Nat.pow_le_pow_right (by norm_num) hk have hα0 : α ≠ 0 := (hprim.isUnit (by omega)).ne_zero have hmul : σ α * σ α⁻¹ = 1 := by rw [← map_mul, mul_inv_cancel₀ hα0, map_one] have hσ' : σ α = α⁻¹ := by rw [hσ] at hmul exact eq_inv_of_mul_eq_one_left hmul
The automorphism $\sigma$ is an iterate of the Frobenius map, giving $\alpha^{2^i} = \alpha^{-1}$ for some index $i$.
The Galois group $\operatorname{Gal}(F/\mathbb{F}_2)$ of a finite field is cyclic generated by the Frobenius map $x \mapsto x^2$. Therefore $\sigma = \operatorname{Frob}^i$ for some integer index $i$, meaning $\sigma(\alpha) = \alpha^{2^i}$. Consequently $\alpha^{2^i} = \alpha^{-1}$.
uses
FiniteField.bijective_frobeniusAlgEquivOfAlgebraic_pow,FiniteField.frobeniusAlgEquivOfAlgebraic,AlgEquiv.coe_pow,FiniteField.coe_frobeniusAlgEquivOfAlgebraic_iterateobtain ⟨i, hi⟩ := (FiniteField.bijective_frobeniusAlgEquivOfAlgebraic_pow (ZMod 2) F).2 σ have hi' : FiniteField.frobeniusAlgEquivOfAlgebraic (ZMod 2) F ^ (i:ℕ) = σ := hi have hpow_eval : ∀ (t : ℕ), (FiniteField.frobeniusAlgEquivOfAlgebraic (ZMod 2) F ^ t) α = α ^ (2 ^ t) := by intro t rw [AlgEquiv.coe_pow, FiniteField.coe_frobeniusAlgEquivOfAlgebraic_iterate] simp have hval : α ^ (2 ^ (i:ℕ)) = α⁻¹ := by rw [← hpow_eval (i:ℕ), hi', hσ']
Deduce that $(2^k - 1) \mid (2^i + 1)$, contradicting the arithmetic key lemma.
Multiplying $\alpha^{2^i} = \alpha^{-1}$ by $\alpha$ yields $\alpha^{2^i + 1} = 1$. Since $\alpha$ is a primitive $(2^k - 1)$-th root of unity, its order $2^k - 1$ divides $2^i + 1$. This directly contradicts the arithmetic lemma from Step 5, proving that $\alpha$ and $\alpha^{-1}$ cannot be conjugate roots over $\mathbb{F}_2$.
uses
pow_succ,inv_mul_cancel₀,dual_melas_eval_mul_eval_eq_imp_shift_equiv_arith_keyhave h1 : α ^ (2 ^ (i:ℕ) + 1) = 1 := by rw [pow_succ, hval, inv_mul_cancel₀ hα0] have hdvd : (2^k - 1) ∣ 2 ^ (i:ℕ) + 1 := hprim.dvd_of_pow_eq_one _ h1 exact dual_melas_eval_mul_eval_eq_imp_shift_equiv_arith_key k (i:ℕ) hk hdvd
The evaluations $f(\alpha)$, $f(\alpha^{-1})$, $g(\alpha)$, and $g(\alpha^{-1})$ are all non-zero.
By the non-degeneracy hypothesis, $f(\alpha) \ne 0$ and $f(\alpha^{-1}) \ne 0$, so their product is non-zero. Since $g(\alpha) g(\alpha^{-1}) = f(\alpha) f(\alpha^{-1})$, neither $g(\alpha)$ nor $g(\alpha^{-1})$ can be zero.
uses
Nat.pow_le_pow_right,mul_ne_zero,zero_mul,mul_zeroobtain ⟨hfu, hfv⟩ := hnondeg have h8 : 8 ≤ 2^k := by calc 8 = 2^3 := by norm_num _ ≤ 2^k := Nat.pow_le_pow_right (by norm_num) hk have hα0 : α ≠ 0 := (hprim.isUnit (by omega)).ne_zero have huv : Polynomial.aeval α f * Polynomial.aeval α⁻¹ f ≠ 0 := mul_ne_zero hfu hfv have ha0 : Polynomial.aeval α g ≠ 0 := by intro h exact huv (by rw [heval, h, zero_mul]) have hb0 : Polynomial.aeval α⁻¹ g ≠ 0 := by intro h exact huv (by rw [heval, h, mul_zero]) have hne : (2^k - 1) ≠ 0 := by omega haveI : NeZero (2^k - 1) := ⟨hne⟩
The ratio $w = f(\alpha) / g(\alpha)$ equals $\alpha^j$ for some $j \in \mathbb{N}$.
Because $f(\alpha)$ and $g(\alpha)$ are non-zero, $w = f(\alpha) g(\alpha)^{-1}$ is a non-zero element in $F$. In the field $F$ of order $2^k$, every non-zero element satisfies $w^{2^k - 1} = 1$. Since $\alpha$ is a primitive $(2^k - 1)$-th root of unity, the powers of $\alpha$ exhaust the roots of unity of this order, so $w = \alpha^j$ for some $j$.
uses
mul_ne_zero,inv_ne_zero,FiniteField.pow_card_sub_one_eq_oneset w := Polynomial.aeval α f * (Polynomial.aeval α g)⁻¹ with hw_def have hw0 : w ≠ 0 := by rw [hw_def] exact mul_ne_zero hfu (inv_ne_zero ha0) have hwpow : w ^ (2^k - 1) = 1 := by have h := FiniteField.pow_card_sub_one_eq_one w hw0 rwa [hcard] at h obtain ⟨j, hjlt, hj⟩ := hprim.eq_pow_of_pow_eq_one hwpow
The evaluations satisfy $f(\alpha) = \alpha^j g(\alpha)$ and $f(\alpha^{-1}) = \alpha^{-j} g(\alpha^{-1})$.
From $w = \alpha^j$ and the definition of $w$, clearing the denominator gives $f(\alpha) = \alpha^j g(\alpha)$. Next, using $f(\alpha) f(\alpha^{-1}) = g(\alpha) g(\alpha^{-1})$, we divide by $f(\alpha)$ to get $f(\alpha^{-1}) = (g(\alpha) / f(\alpha)) g(\alpha^{-1}) = w^{-1} g(\alpha^{-1}) = (\alpha^j)^{-1} g(\alpha^{-1})$.
uses
mul_assoc,inv_mul_cancel₀,mul_one,mul_inv_rev,inv_inv,one_mulhave hgoal1 : Polynomial.aeval α f = α^j * Polynomial.aeval α g := by rw [hj, hw_def, mul_assoc, inv_mul_cancel₀ ha0, mul_one] have hgoal2 : Polynomial.aeval α⁻¹ f = (α^j)⁻¹ * Polynomial.aeval α⁻¹ g := by rw [hj, hw_def, mul_inv_rev, inv_inv] calc Polynomial.aeval α⁻¹ f = (Polynomial.aeval α f)⁻¹ * (Polynomial.aeval α f * Polynomial.aeval α⁻¹ f) := by rw [← mul_assoc, inv_mul_cancel₀ hfu, one_mul] _ = (Polynomial.aeval α f)⁻¹ * (Polynomial.aeval α g * Polynomial.aeval α⁻¹ g) := by rw [heval] _ = Polynomial.aeval α g * (Polynomial.aeval α f)⁻¹ * Polynomial.aeval α⁻¹ g := by ring
Both $\operatorname{minpoly}_{\mathbb{F}_2}(\alpha)$ and $\operatorname{minpoly}_{\mathbb{F}_2}(\alpha^{-1})$ divide the difference polynomial $f - X^j g$.
Evaluating $f - X^j g$ at $\alpha$ gives $f(\alpha) - \alpha^j g(\alpha) = 0$. Evaluating at $\alpha^{-1}$ gives $f(\alpha^{-1}) - (\alpha^{-1})^j g(\alpha^{-1}) = f(\alpha^{-1}) - (\alpha^j)^{-1} g(\alpha^{-1}) = 0$. Since $\alpha$ and $\alpha^{-1}$ are roots of $f - X^j g$, their minimal polynomials over $\mathbb{F}_2$ each divide $f - X^j g$.
uses
map_sub,map_mul,map_pow,aeval_X,sub_self,inv_pow,minpoly.dvdhave hzα : Polynomial.aeval α (f - X^j * g) = 0 := by simp only [map_sub, map_mul, map_pow, aeval_X] rw [hgoal1, sub_self] have hzαinv : Polynomial.aeval α⁻¹ (f - X^j * g) = 0 := by simp only [map_sub, map_mul, map_pow, aeval_X] rw [inv_pow, hgoal2, sub_self] have hdvd1 : minpoly (ZMod 2) α ∣ f - X^j * g := minpoly.dvd (ZMod 2) α hzα have hdvd2 : minpoly (ZMod 2) α⁻¹ ∣ f - X^j * g := minpoly.dvd (ZMod 2) α⁻¹ hzαinv
The minimal polynomials $\operatorname{minpoly}_{\mathbb{F}_2}(\alpha)$ and $\operatorname{minpoly}_{\mathbb{F}_2}(\alpha^{-1})$ are coprime over $\mathbb{F}_2$.
Both minimal polynomials are irreducible over $\mathbb{F}_2$. If they were not coprime, they would divide each other, and being monic irreducible polynomials, they would be equal. Equality of their minimal polynomials means $\alpha$ and $\alpha^{-1}$ are conjugate roots over $\mathbb{F}_2$, which was shown to be impossible in Step 8. Therefore they are coprime.
uses
minpoly.irreducible,IsIntegral.of_finite,Irreducible.coprime_iff_not_dvd,Irreducible.associated_of_dvd,Polynomial.eq_of_monic_of_associated,minpoly.monic,dual_melas_eval_mul_eval_eq_imp_shift_equiv_not_conjhave hcop : IsCoprime (minpoly (ZMod 2) α) (minpoly (ZMod 2) α⁻¹) := by have hp : Irreducible (minpoly (ZMod 2) α) := minpoly.irreducible (IsIntegral.of_finite (ZMod 2) α) have hq : Irreducible (minpoly (ZMod 2) α⁻¹) := minpoly.irreducible (IsIntegral.of_finite (ZMod 2) α⁻¹) rw [Irreducible.coprime_iff_not_dvd hp] intro hdvd have hassoc : Associated (minpoly (ZMod 2) α) (minpoly (ZMod 2) α⁻¹) := Irreducible.associated_of_dvd hp hq hdvd have heq : minpoly (ZMod 2) α = minpoly (ZMod 2) α⁻¹ := Polynomial.eq_of_monic_of_associated (minpoly.monic (IsIntegral.of_finite (ZMod 2) α)) (minpoly.monic (IsIntegral.of_finite (ZMod 2) α⁻¹)) hassoc exact dual_melas_eval_mul_eval_eq_imp_shift_equiv_not_conj k hk F α hprim heq
The product $\operatorname{minpoly}_{\mathbb{F}_2}(\alpha) \cdot \operatorname{minpoly}_{\mathbb{F}_2}(\alpha^{-1})$ divides $f - X^j g$.
Because the two minimal polynomials are coprime and each divides $f - X^j g$, their product also divides $f - X^j g$. This provides the witness $j$ demonstrating shift equivalence.
exact ⟨j, hcop.mul_dvd hdvd1 hdvd2⟩
AlgEquiv.coe_pow- The coercion of the $n$-th power of an algebra equivalence equals its $n$-fold composition.
FiniteField.bijective_frobeniusAlgEquivOfAlgebraic_pow- The Galois group of a finite extension of finite fields is cyclically generated by the Frobenius automorphism.
FiniteField.coe_frobeniusAlgEquivOfAlgebraic_iterate- The $n$-fold iteration of the Frobenius automorphism maps $x \mapsto x^{|K|^n}$.
FiniteField.frobeniusAlgEquivOfAlgebraic- The Frobenius algebra automorphism of an algebraic field extension over a finite field.
FiniteField.pow_card_sub_one_eq_one- In a finite field, every non-zero element satisfies $a^{|K| - 1} = 1$.
Irreducible.associated_of_dvd- Two irreducible elements where one divides the other are associated.
Irreducible.coprime_iff_not_dvd- In a Bézout domain, an irreducible element is coprime to an element if and only if it does not divide it.
IsConjRoot.exists_algEquiv- Conjugate roots in a normal extension are related by an algebra automorphism.
IsIntegral.of_finite- Every element in a finite-dimensional algebra is integral over the base ring.
Nat.ModEq- Modular congruence $a \equiv b \pmod n$, defined by $a \bmod n = b \bmod n$.
Nat.ModEq.add- Modular congruence is preserved under addition: if $a \equiv b$ and $c \equiv d \pmod n$, then $a + c \equiv b + d \pmod n$.
Nat.ModEq.mul- Modular congruence is preserved under multiplication: if $a \equiv b$ and $c \equiv d \pmod n$, then $a c \equiv b d \pmod n$.
Nat.ModEq.pow- Modular congruence is preserved under exponentiation: if $a \equiv b \pmod n$, then $a^m \equiv b^m \pmod n$.
Nat.ModEq.refl- Modular congruence is reflexive: $a \equiv a \pmod n$.
Nat.div_add_mod- Division with remainder identity: $n \cdot (m / n) + (m \bmod n) = m$.
Nat.dvd_of_mod_eq_zero- If $n \bmod m = 0$, then $m \mid n$.
Nat.le_of_dvd- If $0 < n$ and $m \mid n$, then $m \le n$.
Nat.mod_eq_zero_of_dvd- If $m \mid n$, then $n \bmod m = 0$.
Nat.mod_lt- For $y > 0$, the remainder $x \bmod y$ is strictly less than $y$.
Nat.pow_le_pow_right- For a base $n > 0$, if $i \le j$ then $n^i \le n^j$.
Polynomial.eq_of_monic_of_associated- Two monic polynomials that are associated are equal.
aeval_X- Evaluating the polynomial variable $X$ at $x$ yields $x$.
dual_melas_eval_mul_eval_eq_imp_shift_equiv_arith_key- For $k \ge 3$ and any $m \in \mathbb{N}$, $2^k - 1$ does not divide $2^m + 1$.
dual_melas_eval_mul_eval_eq_imp_shift_equiv_not_conj- For $k \ge 3$, a primitive $(2^k - 1)$-th root of unity $\alpha$ and its inverse $\alpha^{-1}$ are not conjugate roots over $\mathbb{F}_2$.
eq_inv_of_mul_eq_one_left- In a division monoid, if $a \cdot b = 1$, then $a = b^{-1}$.
inv_inv- The inverse of an inverse is the original element: $(a^{-1})^{-1} = a$.
inv_ne_zero- If $a \ne 0$, then $a^{-1} \ne 0$.
inv_mul_cancel₀- In a group with zero, $a^{-1} \cdot a = 1$ for any non-zero $a$.
inv_pow- In a division monoid, $(a^{-1})^n = (a^n)^{-1}$.
lt_irrefl- Strict inequality is irreflexive: $\neg (a < a)$.
map_mul- A multiplicative homomorphism preserves multiplication: $f(x y) = f(x) f(y)$.
map_one- A monoid homomorphism preserves the identity element: $f(1) = 1$.
map_pow- A monoid homomorphism preserves powers: $f(a^n) = f(a)^n$.
map_sub- An additive group homomorphism preserves subtraction: $f(a - b) = f(a) - f(b)$.
minpoly.dvd- If $x$ is a root of polynomial $p$, then $\operatorname{minpoly}(x)$ divides $p$.
minpoly.irreducible- The minimal polynomial of an integral element over a domain is irreducible.
minpoly.monic- The minimal polynomial of an integral element is monic.
mul_assoc- Multiplication is associative: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$.
mul_inv_rev- The inverse of a product is the reversed product of inverses: $(a \cdot b)^{-1} = b^{-1} \cdot a^{-1}$.
mul_inv_cancel₀- In a group with zero, $a \cdot a^{-1} = 1$ for any non-zero $a$.
mul_ne_zero- In a domain, the product of two non-zero elements is non-zero.
mul_one- Multiplication by 1 on the right is the identity: $a \cdot 1 = a$.
mul_zero- Multiplication by zero on the right yields zero: $a \cdot 0 = 0$.
one_mul- Multiplication by 1 on the left is the identity: $1 \cdot a = a$.
one_pow- Any power of 1 is 1: $1^n = 1$.
pow_add- Exponent addition rule: $a^{m + n} = a^m \cdot a^n$.
pow_mul- Exponent multiplication rule: $a^{m \cdot n} = (a^m)^n$.
pow_succ- Successor power rule: $a^{n+1} = a^n \cdot a$.
pow_succ'- Successor power rule: $a^{n+1} = a \cdot a^n$.
sub_self- Subtracting an element from itself yields zero: $a - a = 0$.
zero_mul- Multiplication by zero on the left yields zero: $0 \cdot b = 0$.
- The proof relies on two helper lemmas established beforehand in the file: an arithmetic lemma stating that $2^k - 1$ cannot divide $2^m + 1$ when $k \ge 3$, and a Galois-theoretic consequence showing that $\alpha$ and $\alpha^{-1}$ cannot be conjugate roots over $\mathbb{F}_2$.
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.
open Polynomiallemma dual_melas_eval_mul_eval_eq_imp_shift_equiv_arith_key (k m : ℕ) (hk : 3 ≤ k) : ¬ (2^k - 1) ∣ (2^m + 1) := by set n := 2^k - 1 with hn have hn_pos : 0 < n := by have h8 : 8 ≤ 2^k := by calc 8 = 2^3 := by norm_num _ ≤ 2^k := Nat.pow_le_pow_right (by norm_num) hk omega have h2k : (2^k) ≡ 1 [MOD n] := by rw [Nat.ModEq] have hkn : 2^k = n + 1 := by omega rw [hkn] simp have hreduce : (2^m) ≡ (2^(m % k)) [MOD n] := by conv_lhs => rw [← Nat.div_add_mod m k] rw [pow_add, pow_mul] have hp : (2^k)^(m/k) ≡ 1^(m/k) [MOD n] := Nat.ModEq.pow (m/k) h2k simp only [one_pow] at hp have := Nat.ModEq.mul hp (Nat.ModEq.refl (2^(m % k))) simpa using this intro h have hzero : (2^m + 1) ≡ 0 [MOD n] := by rw [Nat.ModEq, Nat.mod_eq_zero_of_dvd h] simp have hred : (2^(m % k) + 1) ≡ 0 [MOD n] := by have h1 : (2^m + 1) ≡ (2^(m % k) + 1) [MOD n] := Nat.ModEq.add hreduce (Nat.ModEq.refl 1) exact h1.symm.trans hzero have hdiv : n ∣ 2^(m % k) + 1 := by rw [Nat.ModEq] at hred exact Nat.dvd_of_mod_eq_zero hred have hr : m % k < k := Nat.mod_lt m (by omega) have hlt : 2^(m % k) + 1 < n := by have hle : 2^(m % k) ≤ 2^(k-1) := Nat.pow_le_pow_right (by norm_num) (by omega) have hlt2 : 2^(k-1) + 1 < n := by have hk1 : k - 1 + 1 = k := by omega have hpow : 2^k = 2 * 2^(k-1) := by conv_lhs => rw [← hk1] rw [pow_succ'] have hge : 4 ≤ 2^(k-1) := by calc 4 = 2^2 := by norm_num _ ≤ 2^(k-1) := Nat.pow_le_pow_right (by norm_num) (by omega) have hn2 : n = 2 * 2^(k-1) - 1 := by rw [hn, hpow] rw [hn2]; omega omega have hpos : 0 < 2^(m % k) + 1 := by positivity have hle' : n ≤ 2^(m % k) + 1 := Nat.le_of_dvd hpos hdiv exact absurd (hlt.trans_le hle') (lt_irrefl _)lemma dual_melas_eval_mul_eval_eq_imp_shift_equiv_not_conj (k : ℕ) (hk : 3 ≤ k) (F : Type*) [Field F] [Fintype F] [Algebra (ZMod 2) F] (α : F) (hprim : IsPrimitiveRoot α (2^k - 1)) : ¬ IsConjRoot (ZMod 2) α α⁻¹ := by intro hconj obtain ⟨σ, hσ⟩ := IsConjRoot.exists_algEquiv hconj have h8 : 8 ≤ 2^k := by calc 8 = 2^3 := by norm_num _ ≤ 2^k := Nat.pow_le_pow_right (by norm_num) hk have hα0 : α ≠ 0 := (hprim.isUnit (by omega)).ne_zero have hmul : σ α * σ α⁻¹ = 1 := by rw [← map_mul, mul_inv_cancel₀ hα0, map_one] have hσ' : σ α = α⁻¹ := by rw [hσ] at hmul exact eq_inv_of_mul_eq_one_left hmul obtain ⟨i, hi⟩ := (FiniteField.bijective_frobeniusAlgEquivOfAlgebraic_pow (ZMod 2) F).2 σ have hi' : FiniteField.frobeniusAlgEquivOfAlgebraic (ZMod 2) F ^ (i:ℕ) = σ := hi have hpow_eval : ∀ (t : ℕ), (FiniteField.frobeniusAlgEquivOfAlgebraic (ZMod 2) F ^ t) α = α ^ (2 ^ t) := by intro t rw [AlgEquiv.coe_pow, FiniteField.coe_frobeniusAlgEquivOfAlgebraic_iterate] simp have hval : α ^ (2 ^ (i:ℕ)) = α⁻¹ := by rw [← hpow_eval (i:ℕ), hi', hσ'] have h1 : α ^ (2 ^ (i:ℕ) + 1) = 1 := by rw [pow_succ, hval, inv_mul_cancel₀ hα0] have hdvd : (2^k - 1) ∣ 2 ^ (i:ℕ) + 1 := hprim.dvd_of_pow_eq_one _ h1 exact dual_melas_eval_mul_eval_eq_imp_shift_equiv_arith_key k (i:ℕ) hk hdvd/-- Equal product of evaluations at α and α⁻¹ implies shift equivalence for non-degenerate f. -/theorem dual_melas_eval_mul_eval_eq_imp_shift_equiv {F : Type*} [Field F] [Fintype F] [Algebra (ZMod 2) F] (k : ℕ) (hk : 3 ≤ k) (hcard : Fintype.card F = 2 ^ k) (α : F) (hprim : IsPrimitiveRoot α (2 ^ k - 1)) (f g : Polynomial (ZMod 2)) (hnondeg : dual_melas_is_non_degenerate α f) (heval : Polynomial.aeval α f * Polynomial.aeval α⁻¹ f = Polynomial.aeval α g * Polynomial.aeval α⁻¹ g) : dual_melas_shift_equiv α f g := by obtain ⟨hfu, hfv⟩ := hnondeg have h8 : 8 ≤ 2^k := by calc 8 = 2^3 := by norm_num _ ≤ 2^k := Nat.pow_le_pow_right (by norm_num) hk have hα0 : α ≠ 0 := (hprim.isUnit (by omega)).ne_zero have huv : Polynomial.aeval α f * Polynomial.aeval α⁻¹ f ≠ 0 := mul_ne_zero hfu hfv have ha0 : Polynomial.aeval α g ≠ 0 := by intro h exact huv (by rw [heval, h, zero_mul]) have hb0 : Polynomial.aeval α⁻¹ g ≠ 0 := by intro h exact huv (by rw [heval, h, mul_zero]) have hne : (2^k - 1) ≠ 0 := by omega haveI : NeZero (2^k - 1) := ⟨hne⟩ set w := Polynomial.aeval α f * (Polynomial.aeval α g)⁻¹ with hw_def have hw0 : w ≠ 0 := by rw [hw_def] exact mul_ne_zero hfu (inv_ne_zero ha0) have hwpow : w ^ (2^k - 1) = 1 := by have h := FiniteField.pow_card_sub_one_eq_one w hw0 rwa [hcard] at h obtain ⟨j, hjlt, hj⟩ := hprim.eq_pow_of_pow_eq_one hwpow have hgoal1 : Polynomial.aeval α f = α^j * Polynomial.aeval α g := by rw [hj, hw_def, mul_assoc, inv_mul_cancel₀ ha0, mul_one] have hgoal2 : Polynomial.aeval α⁻¹ f = (α^j)⁻¹ * Polynomial.aeval α⁻¹ g := by rw [hj, hw_def, mul_inv_rev, inv_inv] calc Polynomial.aeval α⁻¹ f = (Polynomial.aeval α f)⁻¹ * (Polynomial.aeval α f * Polynomial.aeval α⁻¹ f) := by rw [← mul_assoc, inv_mul_cancel₀ hfu, one_mul] _ = (Polynomial.aeval α f)⁻¹ * (Polynomial.aeval α g * Polynomial.aeval α⁻¹ g) := by rw [heval] _ = Polynomial.aeval α g * (Polynomial.aeval α f)⁻¹ * Polynomial.aeval α⁻¹ g := by ring have hzα : Polynomial.aeval α (f - X^j * g) = 0 := by simp only [map_sub, map_mul, map_pow, aeval_X] rw [hgoal1, sub_self] have hzαinv : Polynomial.aeval α⁻¹ (f - X^j * g) = 0 := by simp only [map_sub, map_mul, map_pow, aeval_X] rw [inv_pow, hgoal2, sub_self] have hdvd1 : minpoly (ZMod 2) α ∣ f - X^j * g := minpoly.dvd (ZMod 2) α hzα have hdvd2 : minpoly (ZMod 2) α⁻¹ ∣ f - X^j * g := minpoly.dvd (ZMod 2) α⁻¹ hzαinv have hcop : IsCoprime (minpoly (ZMod 2) α) (minpoly (ZMod 2) α⁻¹) := by have hp : Irreducible (minpoly (ZMod 2) α) := minpoly.irreducible (IsIntegral.of_finite (ZMod 2) α) have hq : Irreducible (minpoly (ZMod 2) α⁻¹) := minpoly.irreducible (IsIntegral.of_finite (ZMod 2) α⁻¹) rw [Irreducible.coprime_iff_not_dvd hp] intro hdvd have hassoc : Associated (minpoly (ZMod 2) α) (minpoly (ZMod 2) α⁻¹) := Irreducible.associated_of_dvd hp hq hdvd have heq : minpoly (ZMod 2) α = minpoly (ZMod 2) α⁻¹ := Polynomial.eq_of_monic_of_associated (minpoly.monic (IsIntegral.of_finite (ZMod 2) α)) (minpoly.monic (IsIntegral.of_finite (ZMod 2) α⁻¹)) hassoc exact dual_melas_eval_mul_eval_eq_imp_shift_equiv_not_conj k hk F α hprim heq exact ⟨j, hcop.mul_dvd hdvd1 hdvd2⟩