AFTD Auto-Formalizing Theoretical Domains

dual_melas_seq_period

theoremverified

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.

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

    lines 5–6

    uses hprim.pow_eq_one, inv_pow, inv_one

      have hα : α ^ (2 ^ k - 1) = 1 := hprim.pow_eq_one
      have hinv : (α⁻¹) ^ (2 ^ k - 1) = 1 := by rw [inv_pow, hα, inv_one]
  2. 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.

    lines 7–8

    uses pow_add, mul_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]
  3. 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.

    line 9

    uses dual_melas_seq

      simp 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

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