cyclic_mds_subgroup_rigidity
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.
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.
uses
subgroup_rigidity_order_of_mdshave 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_mdsThe 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.
uses
order_rigidity_arithmetic_consequencesobtain ⟨h2, h3, h4, h5, h6⟩ := order_rigidity_arithmetic_consequences q n k hk hkn h1All 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.
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
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.
/-- 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⟩