AFTD Auto-Formalizing Theoretical Domains

cyclic_mds_subgroup_rigidity

theoremverifiedformalization

Theorem 3.1 of arXiv:2610.28047: Let F be a finite field of cardinality q and L a field extension of F of degree k. Let H be a cyclic subgroup of Lˣ of order n with 2 ≤ k ≤ n - 2. If every subset of H of size at most k is linearly independent over F (is_trace_mds_subgroup F H k), then for every divisor d > 1 of n, the multiplicative order of q modulo d is k; in particular, every prime l dividing n satisfies ord_l(q) = k and k ∣ l - 1; n is odd; gcd(n, q - 1) = 1; gcd(n, k) = 1; and n = m * k + 1 for some integer m ≥ 2.

Statement

theorem cyclic_mds_subgroup_rigidity {F L : Type*} [Field F] [Fintype F] [Field L] [Algebra F L]
    (q n k : ℕ) (H : Subgroup Lˣ) [Fintype H] (hH_cyc : IsCyclic H) (hH_card : Fintype.card H = n)
    (hq : Fintype.card F = q) (hdim : Module.finrank F L = k) (hk : 2 ≤ k) (hkn : k ≤ n - 2)
    (h_mds : is_trace_mds_subgroup F H k) :
    (∀ d : ℕ, d ∣ n → 1 < d → orderOf (q : ZMod d) = k) ∧
    (∀ l : ℕ, Nat.Prime l → l ∣ n → orderOf (q : ZMod l) = k ∧ k ∣ l - 1) ∧
    Odd n ∧ Nat.gcd n (q - 1) = 1 ∧ Nat.gcd n k = 1 ∧ ∃ m ≥ 2, n = m * k + 1
Formalizes
arXiv:2610.28047 Theorem 3.1 -- Length Bounds for Irreducible Cyclic MDS Codes
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • subgroup_rigidity_order_of_mdsLet H be a cyclic subgroup of order n in the multiplicative group of a degree-k field extension L of F_q with 2 <= k <= n - 2. If every…
  • order_rigidity_arithmetic_consequencesIf 2 <= k <= n - 2 and ord_d(q) = k for every divisor d > 1 of n, then every prime l dividing n satisfies ord_l(q) = k and k | (l - 1), n…
  • is_trace_mds_subgroupA subgroup H of L^x satisfies the MDS property of dimension k over F if every subset of H of size at most k is linearly independent over F.

Read back from the Lean

Let $F$ and $L$ be fields such that $F$ is finite and $L$ is an $F$-algebra. Let $q, n, k \in \mathbb{N}$, and let $H$ be a finite cyclic subgroup of the unit group $L^\times$. Assume: 1. $|H| = n$, 2. $|F| = q$, 3. the dimension $[L : F]$ (Module.finrank F L) equals $k$, 4. $2 \le k$, 5. $k \le n - 2$, and 6. is_trace_mds_subgroup F H k holds: every finite subset $S \subseteq H$ with $|S| \le k$ is linearly independent over $F$ when viewed as a subset of $L$. Then all of the following hold: 1. For every divisor $d$ of $n$ with $d > 1$, the multiplicative order of $q$ in $\mathbb{Z}/d\mathbb{Z}$ is $k$. 2. For every prime divisor $l$ of $n$, the multiplicative order of $q$ in $\mathbb{Z}/l\mathbb{Z}$ is $k$, and $k$ divides $l - 1$. 3. $n$ is odd. 4. $\gcd(n, q - 1) = 1$. 5. $\gcd(n, k) = 1$. 6. There exists an integer $m \ge 2$ such that $n = m k + 1$.

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 proceeds in two main steps. First, the MDS condition on the cyclic subgroup H implies that the multiplicative order of q modulo any non-trivial divisor d of n is equal to the extension degree k. Second, purely arithmetic deductions from this order-rigidity property yield the remaining structural constraints: every prime factor l of n satisfies k ∣ (l - 1), n is odd, n is coprime to both q - 1 and k, and n has the form m * k + 1 with m ≥ 2.

  1. For every divisor d > 1 of n, the multiplicative order of q modulo d is k.

    Applying `subgroup_rigidity_order_of_mds` establishes that the trace MDS property of the cyclic subgroup H forces the order of q modulo any non-trivial divisor d of n to equal the dimension k of the extension.

    lines 9–10

    uses subgroup_rigidity_order_of_mds

      have h1 : ∀ d : ℕ, d ∣ n → 1 < d → orderOf (q : ZMod d) = k :=
        subgroup_rigidity_order_of_mds q n k H hH_cyc hH_card hq hdim hk hkn h_mds
  2. The five arithmetic consequences on n, q, and k hold: every prime factor l of n satisfies ord_l(q) = k and k ∣ (l - 1), n is odd, gcd(n, q - 1) = 1, gcd(n, k) = 1, and n = m * k + 1 for some integer m ≥ 2.

    Applying `order_rigidity_arithmetic_consequences` deduces these five purely arithmetic conclusions directly from the order-rigidity condition h1 and the dimension bounds 2 ≤ k ≤ n - 2.

    line 11

    uses order_rigidity_arithmetic_consequences

      obtain ⟨h2, h3, h4, h5, h6⟩ := order_rigidity_arithmetic_consequences q n k hk hkn h1
  3. All six conclusions of the theorem hold simultaneously.

    Combine the order-rigidity property h1 with the five arithmetic consequences h2 through h6 to complete the conjunction.

    line 12

      exact ⟨h1, h2, h3, h4, h5, h6⟩
subgroup_rigidity_order_of_mds
If H is a cyclic trace MDS subgroup of order n in a degree-k extension of a finite field of order q, with 2 ≤ k ≤ n - 2, then for every divisor d > 1 of n, the multiplicative order of q modulo d is k.
order_rigidity_arithmetic_consequences
If 2 ≤ k ≤ n - 2 and the order of q modulo every divisor d > 1 of n is k, then every prime factor l of n satisfies ord_l(q) = k and k ∣ (l - 1); n is odd; gcd(n, q - 1) = 1; gcd(n, k) = 1; and n = m * k + 1 for some integer m ≥ 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

/-- Theorem 3.1 of arXiv:2610.28047: Subgroup rigidity for irreducible cyclic MDS codes in the trace realization. -/theorem cyclic_mds_subgroup_rigidity {F L : Type*} [Field F] [Fintype F] [Field L] [Algebra F L]    (q n k : ℕ) (H : Subgroup Lˣ) [Fintype H] (hH_cyc : IsCyclic H) (hH_card : Fintype.card H = n)    (hq : Fintype.card F = q) (hdim : Module.finrank F L = k) (hk : 2 ≤ k) (hkn : k ≤ n - 2)    (h_mds : is_trace_mds_subgroup F H k) :    (∀ d : ℕ, d ∣ n → 1 < d → orderOf (q : ZMod d) = k) ∧    (∀ l : ℕ, Nat.Prime l → l ∣ n → orderOf (q : ZMod l) = k ∧ k ∣ l - 1) ∧    Odd n ∧ Nat.gcd n (q - 1) = 1 ∧ Nat.gcd n k = 1 ∧ ∃ m ≥ 2, n = m * k + 1 := by  have h1 : ∀ d : ℕ, d ∣ n → 1 < d → orderOf (q : ZMod d) = k :=    subgroup_rigidity_order_of_mds q n k H hH_cyc hH_card hq hdim hk hkn h_mds  obtain ⟨h2, h3, h4, h5, h6⟩ := order_rigidity_arithmetic_consequences q n k hk hkn h1  exact ⟨h1, h2, h3, h4, h5, h6⟩
See it in the graphDiscuss this resultChallenge it