dual_melas_non_degenerate_orbit_shift_equiv_iff
Let 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 is non-degenerate (neither α nor α⁻¹ is a root of f), f and g are shift-equivalent modulo the product of the minimal polynomials of α and α⁻¹ if and only if f(α) * f(α⁻¹) = g(α) * g(α⁻¹).
Statement
theorem dual_melas_non_degenerate_orbit_shift_equiv_iff {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) : dual_melas_shift_equiv α f g ↔ Polynomial.aeval α f * Polynomial.aeval α⁻¹ f = Polynomial.aeval α g * Polynomial.aeval α⁻¹ g
- Formalizes
- arXiv:2610.38017 Lemma 5
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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.
- dual_melas_shift_equiv_imp_eval_mul_eval_eqIf binary polynomials f and g are shift-equivalent modulo the product of the minimal polynomials of α and α⁻¹, and α is nonzero, then f(α)…
- dual_melas_eval_mul_eval_eq_imp_shift_equivLet $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…
Read back from the Lean
Let $F$ be a finite field that is an algebra over $\mathbb{Z}/2\mathbb{Z}$. Let $k \ge 3$ be a natural number such that $|F| = 2^k$, and 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, and assume $f$ is non-degenerate with respect to $\alpha$ (that is, dual_melas_is_non_degenerate α f).
Then $f$ and $g$ are shift-equivalent with respect to $\alpha$ (dual_melas_shift_equiv α f g) if and only if
$$(\text{aeval } \alpha \, f) \cdot (\text{aeval } \alpha^{-1} \, f) = (\text{aeval } \alpha \, g) \cdot (\text{aeval } \alpha^{-1} \, g)$$
in $F$.
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
The proof decomposes the logical equivalence into two directions, each resolved by a dedicated helper theorem. For the forward direction, shift equivalence implies equality of the evaluation products via dual_melas_shift_equiv_imp_eval_mul_eval_eq, where α ≠ 0 follows because α has primitive order 2^k - 1 > 0 since k ≥ 3. For the reverse direction, equality of the evaluation products implies shift equivalence directly via dual_melas_eval_mul_eval_eq_imp_shift_equiv using the hypothesis that f is non-degenerate.
Shift equivalence implies equality of evaluation products: f(α) f(α⁻¹) = g(α) g(α⁻¹).
To establish the forward direction, we assume f and g are shift-equivalent. Since k ≥ 3, monotonicity of powers (Nat.pow_le_pow_right) gives 2^k ≥ 2^3 = 8, so linear integer arithmetic (omega) verifies 2^k - 1 ≠ 0. Because α is a primitive (2^k - 1)-th root of unity and the order is non-zero, α ≠ 0 by IsPrimitiveRoot.ne_zero. The forward implication then follows directly from dual_melas_shift_equiv_imp_eval_mul_eval_eq.
uses
Nat.pow_le_pow_right,IsPrimitiveRoot.ne_zero,dual_melas_shift_equiv_imp_eval_mul_eval_eqconstructor · intro hsim have hn : 2 ^ k - 1 ≠ 0 := by have h3 : 2 ^ 3 ≤ 2 ^ k := Nat.pow_le_pow_right (by norm_num) hk omega exact dual_melas_shift_equiv_imp_eval_mul_eval_eq α (IsPrimitiveRoot.ne_zero hprim hn) f g hsim
Conversely, equality of evaluation products implies shift equivalence: if f(α) f(α⁻¹) = g(α) g(α⁻¹), then f and g are shift-equivalent.
For the reverse direction, we assume f(α) f(α⁻¹) = g(α) g(α⁻¹). Since f is non-degenerate and the field F has order 2^k with k ≥ 3, dual_melas_eval_mul_eval_eq_imp_shift_equiv applies directly to conclude that f and g are shift-equivalent.
uses
dual_melas_eval_mul_eval_eq_imp_shift_equiv· intro heval exact dual_melas_eval_mul_eval_eq_imp_shift_equiv k hk hcard α hprim f g hnondeg heval
Nat.pow_le_pow_right- For a positive base n, if i ≤ j then n^i ≤ n^j.
IsPrimitiveRoot.ne_zero- A primitive k-th root of unity with non-zero order k ≠ 0 in a nontrivial monoid with zero is non-zero.
dual_melas_shift_equiv_imp_eval_mul_eval_eq- If α ≠ 0 and polynomials f, g are shift-equivalent modulo the dual Melas generator, then f(α)f(α⁻¹) = g(α)g(α⁻¹).
dual_melas_eval_mul_eval_eq_imp_shift_equiv- In a field of order 2^k (with k ≥ 3) and α primitive of order 2^k - 1, if f is non-degenerate and f(α)f(α⁻¹) = g(α)g(α⁻¹), then f and g are shift-equivalent modulo the dual Melas generator.
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.
/-- Characterization of non-degenerate orbits: shift equivalence modulo dual Melas generator iff f(α)f(α⁻¹) = g(α)g(α⁻¹). -/theorem dual_melas_non_degenerate_orbit_shift_equiv_iff {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) : dual_melas_shift_equiv α f g ↔ Polynomial.aeval α f * Polynomial.aeval α⁻¹ f = Polynomial.aeval α g * Polynomial.aeval α⁻¹ g := by constructor · intro hsim have hn : 2 ^ k - 1 ≠ 0 := by have h3 : 2 ^ 3 ≤ 2 ^ k := Nat.pow_le_pow_right (by norm_num) hk omega exact dual_melas_shift_equiv_imp_eval_mul_eval_eq α (IsPrimitiveRoot.ne_zero hprim hn) f g hsim · intro heval exact dual_melas_eval_mul_eval_eq_imp_shift_equiv k hk hcard α hprim f g hnondeg heval