dual_melas_seq_period
For a field F finite-dimensional over ZMod 2, a natural number k, elements α, c ∈ F such that α has order 2^k - 1, and index i, dual_melas_seq α c (i + (2^k - 1)) = dual_melas_seq α c i.
Statement
theorem dual_melas_seq_period {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (α c : F) (hprim : IsPrimitiveRoot α (2 ^ k - 1)) (i : ℕ) : dual_melas_seq α c (i + (2 ^ k - 1)) = dual_melas_seq α c i
- Source
- step towards dual_melas_adjacent_cyclic_patterns_bivariate_poisson_limit
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- dual_melas_seqFor a field F equipped with an algebra structure over ZMod 2 and finite-dimensional over ZMod 2, elements α, c : F, and index i : ℕ,…
The proof, explained
The dual Melas binary trace sequence evaluates the field trace of α^i + c * (α⁻¹)^i over ZMod 2. Because α is a primitive root of order 2^k - 1, both α and its inverse α⁻¹ raised to the power 2^k - 1 equal 1. Consequently, the powers α^i and (α⁻¹)^i are each periodic with period 2^k - 1. Unfolding the definition of the sequence and substituting these periodic powers yields the claim.
Both α and α⁻¹ satisfy α^(2^k - 1) = 1 and (α⁻¹)^(2^k - 1) = 1.
Since α is assumed to be a primitive root of order 2^k - 1 (hypothesis `hprim`), raising α to the power 2^k - 1 gives 1 (`hprim.pow_eq_one`). Inverting both sides and applying `inv_pow` and `inv_one` yields (α⁻¹)^(2^k - 1) = (α^(2^k - 1))⁻¹ = 1⁻¹ = 1.
uses
hprim.pow_eq_one,inv_pow,inv_onehave hα : α ^ (2 ^ k - 1) = 1 := hprim.pow_eq_one have hinv : (α⁻¹) ^ (2 ^ k - 1) = 1 := by rw [inv_pow, hα, inv_one]
The powers α^i and (α⁻¹)^i are periodic with period 2^k - 1: α^(i + (2^k - 1)) = α^i and (α⁻¹)^(i + (2^k - 1)) = (α⁻¹)^i.
By exponent addition (`pow_add`), α^(i + (2^k - 1)) decomposes as α^i * α^(2^k - 1). Substituting α^(2^k - 1) = 1 and simplifying with `mul_one` leaves α^i. The identical deduction applies to α⁻¹, using (α⁻¹)^(2^k - 1) = 1.
uses
pow_add,mul_onehave e1 : α ^ (i + (2 ^ k - 1)) = α ^ i := by rw [pow_add, hα, mul_one] have e2 : (α⁻¹) ^ (i + (2 ^ k - 1)) = (α⁻¹) ^ i := by rw [pow_add, hinv, mul_one]
dual_melas_seq α c (i + (2^k - 1)) = dual_melas_seq α c i
By definition, dual_melas_seq α c j evaluates the field trace of α^j + c * (α⁻¹)^j. Replacing the powers α^(i + (2^k - 1)) and (α⁻¹)^(i + (2^k - 1)) with α^i and (α⁻¹)^i using the established equalities `e1` and `e2` shows that the sequence value at i + (2^k - 1) is identical to that at index i.
uses
dual_melas_seqsimp only [dual_melas_seq, e1, e2]
hprim.pow_eq_one- A primitive root of order k raised to the power k equals 1: if ζ is a primitive k-th root of unity, then ζ^k = 1.
inv_pow- The n-th power of an inverse equals the inverse of the n-th power: (a⁻¹)^n = (a^n)⁻¹.
inv_one- The multiplicative inverse of the identity element 1 is 1: 1⁻¹ = 1.
pow_add- Powers add when multiplying powers of the same base: a^(m + n) = a^m * a^n.
mul_one- Multiplying any element by 1 yields the element itself: a * 1 = a.
dual_melas_seq- The dual Melas binary trace sequence, defined by dual_melas_seq α c i = Tr(α^i + c * (α⁻¹)^i), where Tr is the field trace down to ZMod 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.
/-- The dual Melas binary trace sequence has period 2^k - 1 when α is a primitive root of order 2^k - 1. -/theorem dual_melas_seq_period {F : Type*} [Field F] [Algebra (ZMod 2) F] [FiniteDimensional (ZMod 2) F] (k : ℕ) (α c : F) (hprim : IsPrimitiveRoot α (2 ^ k - 1)) (i : ℕ) : dual_melas_seq α c (i + (2 ^ k - 1)) = dual_melas_seq α c i := by have hα : α ^ (2 ^ k - 1) = 1 := hprim.pow_eq_one have hinv : (α⁻¹) ^ (2 ^ k - 1) = 1 := by rw [inv_pow, hα, inv_one] have e1 : α ^ (i + (2 ^ k - 1)) = α ^ i := by rw [pow_add, hα, mul_one] have e2 : (α⁻¹) ^ (i + (2 ^ k - 1)) = (α⁻¹) ^ i := by rw [pow_add, hinv, mul_one] simp only [dual_melas_seq, e1, e2]