AFTD Auto-Formalizing Theoretical Domains

dual_melas_eval_mul_eval_eq_imp_shift_equiv

theoremverified

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

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

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

    lines 5–15

    uses Nat.pow_le_pow_right, Nat.ModEq

      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
  2. 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$.

    lines 16–22

    uses Nat.div_add_mod, pow_add, pow_mul, Nat.ModEq.pow, one_pow, Nat.ModEq.mul, Nat.ModEq.refl

      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
  3. 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$.

    lines 23–33

    uses Nat.ModEq, Nat.mod_eq_zero_of_dvd, Nat.ModEq.add, Nat.ModEq.refl, Nat.dvd_of_mod_eq_zero

      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
  4. 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$.

    lines 34–47

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

    lines 48–50

    uses Nat.le_of_dvd, lt_irrefl

      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 _)
  6. 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}$.

    lines 56–66

    uses IsConjRoot.exists_algEquiv, Nat.pow_le_pow_right, map_mul, mul_inv_cancel₀, map_one, eq_inv_of_mul_eq_one_left

      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
  7. 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}$.

    lines 67–74

    uses FiniteField.bijective_frobeniusAlgEquivOfAlgebraic_pow, FiniteField.frobeniusAlgEquivOfAlgebraic, AlgEquiv.coe_pow, FiniteField.coe_frobeniusAlgEquivOfAlgebraic_iterate

      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σ']
  8. 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$.

    lines 75–78

    uses pow_succ, inv_mul_cancel₀, dual_melas_eval_mul_eval_eq_imp_shift_equiv_arith_key

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

    lines 90–103

    uses Nat.pow_le_pow_right, mul_ne_zero, zero_mul, mul_zero

      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⟩
  10. 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$.

    lines 104–111

    uses mul_ne_zero, inv_ne_zero, FiniteField.pow_card_sub_one_eq_one

      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
  11. 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})$.

    lines 112–121

    uses mul_assoc, inv_mul_cancel₀, mul_one, mul_inv_rev, inv_inv, one_mul

      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
  12. 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$.

    lines 122–129

    uses map_sub, map_mul, map_pow, aeval_X, sub_self, inv_pow, minpoly.dvd

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

    lines 130–143

    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_conj

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

    line 144

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

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

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