subgroup_rigidity_order_of_mds
Let 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 subset of H of size at most k is linearly independent over F_q, then for every divisor d > 1 of n, the multiplicative order of q modulo d equals k.
Statement
theorem subgroup_rigidity_order_of_mds {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
- Formalizes
- arXiv:2610.28047 Theorem 3.1
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
- subgroup_units_pow_card_dvdFor a subgroup H of Lˣ where [L:F] = k and |F| = q, any divisor d of |H| satisfies q^k ≡ 1 (mod d).
- Used by 1
- cyclic_mds_subgroup_rigidityTheorem 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…
Read back from the Lean
Let $F$ and $L$ be fields with $F$ finite, and let $L$ be an $F$-algebra. Let $q, n, k$ be natural numbers. Let $H$ be a finite cyclic subgroup of the multiplicative group $L^\times$ of order $n$. Suppose $|F| = q$, the dimension $[L : F] = \operatorname{finrank}_F(L) = k$, $2 \le k$, and $k \le n - 2$. Suppose further that $H$ is a trace MDS subgroup of order $k$ (i.e., every subset of $H$ of size at most $k$ is linearly independent over $F$ when viewed as elements of $L$). Then for every natural number $d$, if $d$ divides $n$ and $d > 1$, the multiplicative order of $q$ in the ring $\mathbb{Z}/d\mathbb{Z}$ is equal to $k$.
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
To show that the order r of q modulo d equals k for any divisor d > 1 of n, the proof sandwiches k between r and the degree m = [F(x) : F] of the subfield generated by an element x ∈ H of exact order d. Lagrange's theorem on H ≤ Lˣ implies d ∣ (q^k - 1), so r divides k and hence r ≤ k. Since x has order d and d ∣ (q^r - 1), x is invariant under the r-th Frobenius iterate, which implies m ∣ r (by an auxiliary lemma equating extension degree with Frobenius order) and so m ≤ r < d. Finally, if m < k, the powers 1, x, ..., x^m would form a set of m + 1 ≤ k elements in H lying in the m-dimensional subfield F(x), contradicting the MDS hypothesis that any subset of H of size at most k is linearly independent over F. Thus k ≤ m ≤ r ≤ k, forcing r = k.
If an element x in a finite field extension L/F satisfies x^(|F|^r) = x, then the degree [F(x) : F] divides r.
Let K = F(x). The order of the Frobenius F-algebra endomorphism of K equals [K : F] by FiniteField.orderOf_frobeniusAlgHom. By orderOf_dvd_iff_pow_eq_one, it suffices to show that the r-th power of the Frobenius map is the identity on K. Since K is generated by {x}, an algebra homomorphism on K is determined by its value on x (IntermediateField.adjoin_algHom_ext). Applying the r-th iterate of Frobenius to x raises it to |F|^r, which equals x by assumption hx, so the map is the identity. Hence [K : F] divides r.
uses
FiniteField.orderOf_frobeniusAlgHom,orderOf_dvd_iff_pow_eq_one,IntermediateField.adjoin_algHom_ext,AlgHom.coe_pow,FiniteField.coe_frobeniusAlgHom,pow_iterate,AlgHom.one_apply,Subtype.extlet K : IntermediateField F L := IntermediateField.adjoin F {x} haveI : Finite K := inferInstance have hord : orderOf (FiniteField.frobeniusAlgHom F K) = Module.finrank F K := FiniteField.orderOf_frobeniusAlgHom F K rw [← hord] refine orderOf_dvd_iff_pow_eq_one.mpr ?_ refine IntermediateField.adjoin_algHom_ext F (s := {x}) ?_ intro y hy obtain rfl : y = x := by simpa using hy rw [AlgHom.coe_pow, FiniteField.coe_frobeniusAlgHom, pow_iterate, AlgHom.one_apply] exact Subtype.ext (by simpa using hx)
Fix a divisor d of n with d > 1; L is a finite field with |L| = q^k, q ≥ 2, and n ≥ 4.
Introduce the divisor d dividing n with d > 1. Since [L : F] = k ≥ 2 > 0 and F is finite, L is a finite-dimensional vector space over F and hence finite. Its cardinality is |F|^[L : F] = q^k via Module.card_eq_pow_finrank. Since F is a field, |F| = q ≥ 2 by Fintype.one_lt_card, and the inequalities 2 ≤ k ≤ n - 2 imply n ≥ 4.
uses
Module.finite_of_finrank_pos,Module.finite_of_finite,Fintype.ofFinite,Fintype.one_lt_card,Module.card_eq_pow_finrankclassical intro d hdn hd1 haveI : Module.Finite F L := Module.finite_of_finrank_pos (by rw [hdim]; omega) haveI : Finite L := Module.finite_of_finite F haveI : Fintype L := Fintype.ofFinite L have hnk : 4 ≤ n := by omega have hq2 : 2 ≤ q := by rw [← hq]; exact Fintype.one_lt_card have hcardL : Fintype.card L = q ^ k := by rw [Module.card_eq_pow_finrank (K := F) (V := L), hq, hdim]
d divides q^k - 1, and consequently the multiplicative order r of q modulo d divides k, with 0 < r ≤ k.
By Lagrange's theorem (Subgroup.card_subgroup_dvd_card), the order of H divides |Lˣ| = q^k - 1, so n divides q^k - 1. Because d divides n, transitivity of divisibility gives d ∣ (q^k - 1). In ZMod d, this translates to q^k = 1. Therefore, the multiplicative order r = orderOf (q : ZMod d) divides k. Since k ≥ 2 > 0, this yields 0 < r ≤ k.
uses
Nat.card_eq_fintype_card,Subgroup.card_subgroup_dvd_card,Fintype.card_units,dvd_trans,ZMod.natCast_eq_zero_iff,Nat.one_le_pow,Nat.sub_add_cancel,zero_add,orderOf_dvd_iff_pow_eq_one,Nat.le_of_dvd,Nat.pos_of_dvd_of_poshave key : d ∣ q ^ k - 1 := by have h1 : Fintype.card H ∣ Fintype.card Lˣ := by rw [← Nat.card_eq_fintype_card, ← Nat.card_eq_fintype_card] exact Subgroup.card_subgroup_dvd_card H rw [hH_card, Fintype.card_units, hcardL] at h1 exact dvd_trans hdn h1 haveI : NeZero d := ⟨by omega⟩ have hqk : (q : ZMod d) ^ k = 1 := by have hzero : ((q ^ k - 1 : ℕ) : ZMod d) = 0 := (ZMod.natCast_eq_zero_iff _ _).mpr key have hone : 1 ≤ q ^ k := Nat.one_le_pow k q (by omega) calc (q : ZMod d) ^ k = ((q ^ k : ℕ) : ZMod d) := by push_cast; ring _ = ((q ^ k - 1 + 1 : ℕ) : ZMod d) := by rw [Nat.sub_add_cancel hone] _ = ((q ^ k - 1 : ℕ) : ZMod d) + 1 := by push_cast; ring _ = 1 := by rw [hzero, zero_add] have hr_dvd_k : orderOf (q : ZMod d) ∣ k := orderOf_dvd_iff_pow_eq_one.mpr hqk have hrle : orderOf (q : ZMod d) ≤ k := Nat.le_of_dvd (by omega) hr_dvd_k have hrpos : 0 < orderOf (q : ZMod d) := Nat.pos_of_dvd_of_pos hr_dvd_k (by omega)
The multiplicative order r of q modulo d is strictly less than d.
Since q^k = 1 in ZMod d with k ≠ 0, q is invertible modulo d, so gcd(q, d) = 1. By Euler's theorem, the order of q in the group of units (ZMod d)ˣ divides the group order φ(d) = Nat.totient d. Since d > 1, φ(d) < d, which implies r ≤ φ(d) ≤ d - 1 < d.
uses
isUnit_pow_iff,isUnit_one,ZMod.isUnit_iff_coprime,ZMod.coe_unitOfCoprime,orderOf_units,ZMod.card_units_eq_totient,orderOf_dvd_card,Nat.totient_pos,Nat.le_of_dvd,Nat.totient_lthave hr_lt_d : orderOf (q : ZMod d) < d := by have hunit : IsUnit (q : ZMod d) := (isUnit_pow_iff (by omega : k ≠ 0)).mp (hqk ▸ isUnit_one) have hcop : q.Coprime d := (ZMod.isUnit_iff_coprime q d).mp hunit have hdiv : orderOf (q : ZMod d) ∣ Nat.totient d := by rw [← ZMod.coe_unitOfCoprime q hcop, orderOf_units, ← ZMod.card_units_eq_totient] exact orderOf_dvd_card have htpos : 0 < Nat.totient d := Nat.totient_pos.mpr (by omega) have hle : orderOf (q : ZMod d) ≤ d - 1 := by have h1 := Nat.le_of_dvd htpos hdiv have h2 := Nat.totient_lt d hd1 omega omega
There exists an element x ∈ H of exact order d, which satisfies x^d = 1 in L.
Since H is cyclic of order n, choose a generator g ∈ H of order n. Set x = g^(n / d) ∈ H. Because d divides n, x has order d in H, and thus also in Lˣ. In particular, x^d = 1 in L.
uses
IsCyclic.exists_ofOrder_eq_natCard,Nat.card_eq_fintype_card,orderOf_pow_orderOf_div,Subgroup.orderOf_coe,pow_orderOf_eq_one,congrArgobtain ⟨g, hg⟩ := IsCyclic.exists_ofOrder_eq_natCard (α := H) have hgn : orderOf g = n := by rw [hg, Nat.card_eq_fintype_card, hH_card] set x : H := g ^ (n / d) with hx_def have hx_ord : orderOf x = d := by rw [hx_def, ← hgn] exact orderOf_pow_orderOf_div (by omega) (by rw [hgn]; exact hdn) have hxL_ord : orderOf ((x : Lˣ)) = d := by rw [Subgroup.orderOf_coe, hx_ord] have hx_d : ((x : Lˣ) : L) ^ d = 1 := by have h := pow_orderOf_eq_one (x : Lˣ) rw [hxL_ord] at h simpa using congrArg (fun u : Lˣ => (u : L)) h
The element x satisfies x^(q^r) = x in L, where r is the multiplicative order of q modulo d.
By definition of order, q^r ≡ 1 mod d, so d divides q^r - 1. Writing q^r - 1 = t * d, we have x^(q^r - 1) = (x^d)^t = 1^t = 1. Multiplying both sides by x gives x^(q^r) = x.
uses
pow_orderOf_eq_one,ZMod.natCast_eq_natCast_iff,Nat.modEq_iff_dvd',Nat.one_le_pow,pow_mul,one_pow,Nat.sub_add_cancel,pow_add,one_mul,pow_onehave hdvd_r : d ∣ q ^ orderOf (q : ZMod d) - 1 := by have hrpow : (q : ZMod d) ^ orderOf (q : ZMod d) = 1 := pow_orderOf_eq_one _ have h : q ^ orderOf (q : ZMod d) ≡ 1 [MOD d] := (ZMod.natCast_eq_natCast_iff (q ^ orderOf (q : ZMod d)) 1 d).mp (by simpa using hrpow) exact (Nat.modEq_iff_dvd' (Nat.one_le_pow _ q (by omega))).mp h.symm have hxL_pow : ((x : Lˣ) : L) ^ (q ^ orderOf (q : ZMod d)) = ((x : Lˣ) : L) := by obtain ⟨t, ht⟩ := hdvd_r have h1 : ((x : Lˣ) : L) ^ (q ^ orderOf (q : ZMod d) - 1) = 1 := by rw [ht, pow_mul, hx_d, one_pow] rw [← Nat.sub_add_cancel (Nat.one_le_pow _ q (by omega)), pow_add, h1, one_mul, pow_one]
The extension degree m = [F(x) : F] divides r, and therefore m ≤ r.
Let K = F(x) be the subfield generated by x over F, and let m = [K : F]. Since x^(q^r) = x with |F| = q, the auxiliary lemma subgroup_rigidity_order_of_mds_finrank_adjoin_dvd shows that m divides r. Since r > 0, m is positive and m ≤ r.
uses
subgroup_rigidity_order_of_mds_finrank_adjoin_dvd,Nat.eq_zero_or_pos,Nat.le_of_dvdset K : IntermediateField F L := IntermediateField.adjoin F {((x : Lˣ) : L)} with hK set m : ℕ := Module.finrank F K with hm have hmdvd : m ∣ orderOf (q : ZMod d) := by have := subgroup_rigidity_order_of_mds_finrank_adjoin_dvd (F := F) (L := L) (r := orderOf (q : ZMod d)) (x := ((x : Lˣ) : L)) (by rw [hq]; exact hxL_pow) simpa [hm, hK] using this have hmle : m ≤ orderOf (q : ZMod d) := by rcases Nat.eq_zero_or_pos m with h0 | hpos · omega · exact Nat.le_of_dvd hrpos hmdvd
The MDS property forces k ≤ m, where m = [F(x) : F].
Suppose for contradiction that m < k. Since m ≤ r < d, we have m ≤ d - 1. Define φ(j) = x^j ∈ H for 0 ≤ j ≤ m. Because the order of x is d and the exponents j are strictly less than d, these powers are all distinct, so φ is injective. Thus S = {1, x, ..., x^m} has cardinality m + 1 ≤ k. By the MDS hypothesis, S is linearly independent over F in L. However, every x^j lies in K = F(x), so S is a linearly independent subset of the m-dimensional F-vector space K. This implies |S| ≤ [K : F] = m, contradicting |S| = m + 1. Hence k ≤ m.
uses
congrArg,pow_eq_pow_iff_modEq,Finset.card_image_of_injOn,Finset.card_range,IntermediateField.subset_adjoin,pow_mem,LinearIndependent.of_comp,Submodule.subtype,LinearIndependent.fintype_card_le_finrankhave hkm : k ≤ m := by by_contra hcon push Not at hcon have hmd' : m ≤ d - 1 := by omega let φ : ℕ → H := fun j => ⟨((x : Lˣ)) ^ j, H.pow_mem x.2 j⟩ have hφinj : Set.InjOn φ ↑(Finset.range (m + 1)) := by intro j hj j' hj' heq rw [Finset.mem_coe, Finset.mem_range] at hj hj' have heq2 : ((x : Lˣ)) ^ j = ((x : Lˣ)) ^ j' := by have h2 := congrArg (fun u : H => ((u : Lˣ))) heq simpa [φ] using h2 have hmod : j ≡ j' [MOD d] := by have h3 := pow_eq_pow_iff_modEq.mp heq2 rwa [hxL_ord] at h3 exact hmod.eq_of_lt_of_lt (by omega) (by omega) set S : Finset H := (Finset.range (m + 1)).image φ with hS have hScard : S.card = m + 1 := by rw [hS, Finset.card_image_of_injOn hφinj, Finset.card_range] have hSk : S.card ≤ k := by omega have hind := h_mds S hSk have hmem : ∀ u : S, ((u.1 : Lˣ) : L) ∈ K := by intro u obtain ⟨j, hj, hju⟩ := Finset.mem_image.mp u.2 have hu : u.1 = φ j := hju.symm rw [hu] have hxK : ((x : Lˣ) : L) ∈ K := IntermediateField.subset_adjoin F {((x : Lˣ) : L)} (Set.mem_singleton _) have hp : ((φ j : H) : Lˣ) = ((x : Lˣ)) ^ j := rfl rw [hp] push_cast exact pow_mem hxK j have hindK : LinearIndependent F (fun u : S => (⟨((u.1 : Lˣ) : L), hmem u⟩ : ↥K.toSubmodule)) := LinearIndependent.of_comp (Submodule.subtype K.toSubmodule) hind have hfin : Fintype.card S ≤ Module.finrank F ↥K.toSubmodule := hindK.fintype_card_le_finrank rw [Fintype.card_coe, hScard] at hfin have hfm : Module.finrank F ↥K.toSubmodule = m := rfl omega
The multiplicative order of q modulo d equals k. automation
Linear arithmetic over ℕ combines the inequalities k ≤ m, m ≤ r, and r ≤ k to conclude that r = k.
omega
FiniteField.orderOf_frobeniusAlgHom- The order of the Frobenius algebra endomorphism of a finite extension K/F equals the extension degree [K : F].
orderOf_dvd_iff_pow_eq_one- The order of an element divides n if and only if its n-th power is 1.
IntermediateField.adjoin_algHom_ext- Two algebra homomorphisms on an adjoined intermediate field are equal if they agree on the generating set.
AlgHom.coe_pow- The coercion of the n-th power of an algebra homomorphism to a function is the n-th iterate of the function.
FiniteField.coe_frobeniusAlgHom- The Frobenius algebra endomorphism of an extension of K is given by raising each element to the cardinality of K.
pow_iterate- Iterating the power map x ↦ x^k n times yields x ↦ x^(k^n).
AlgHom.one_apply- The identity algebra homomorphism evaluates to the identity function.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
Module.finite_of_finrank_pos- A module with strictly positive finite rank over a field is finite-dimensional (finitely generated).
Module.finite_of_finite- A finite-dimensional module over a finite ring is finite as a type.
Fintype.ofFinite- A finite type can be equipped with a Fintype instance.
Fintype.one_lt_card- Any nontrivial finite type has cardinality strictly greater than 1.
Module.card_eq_pow_finrank- The cardinality of a finite-dimensional vector space over a finite field is the field size raised to the dimension.
Nat.card_eq_fintype_card- The generic cardinality Nat.card of a finite type equals its Fintype.card.
Subgroup.card_subgroup_dvd_card- By Lagrange's theorem, the cardinality of any subgroup divides the cardinality of the ambient group.
Fintype.card_units- The number of units in a finite field is one less than the cardinality of the field.
dvd_trans- Divisibility is transitive: if a divides b and b divides c, then a divides c.
ZMod.natCast_eq_zero_iff- An integer a maps to zero modulo b if and only if b divides a.
Nat.one_le_pow- If m > 0, then m^n ≥ 1 for any exponent n.
Nat.sub_add_cancel- For natural numbers with m ≤ n, (n - m) + m = n.
zero_add- Adding zero on the left is the identity.
Nat.le_of_dvd- If n > 0 and m divides n, then m ≤ n.
Nat.pos_of_dvd_of_pos- If m divides n and n > 0, then m > 0.
isUnit_pow_iff- For a non-zero exponent n, an element a is a unit if and only if a^n is a unit.
isUnit_one- The identity element 1 is a unit.
ZMod.isUnit_iff_coprime- An integer m is a unit modulo n if and only if m and n are coprime.
ZMod.coe_unitOfCoprime- The unit formed from a coprime integer x coerces back to x in ZMod n.
orderOf_units- The order of a unit in the group of units equals the order of its coercion in the ambient monoid.
ZMod.card_units_eq_totient- The cardinality of the group of units of ZMod n is Euler's totient φ(n).
orderOf_dvd_card- The order of any element in a finite group divides the cardinality of the group.
Nat.totient_pos- Euler's totient φ(n) is strictly positive if and only if n > 0.
Nat.totient_lt- For any integer n > 1, Euler's totient satisfies φ(n) < n.
IsCyclic.exists_ofOrder_eq_natCard- Every finite cyclic group has a generator whose order equals the group cardinality.
orderOf_pow_orderOf_div- If an element has order N and d divides N, then raising it to the power N/d yields an element of order d.
Subgroup.orderOf_coe- The order of an element in a subgroup equals the order of its inclusion in the ambient group.
pow_orderOf_eq_one- Raising an element to the power of its order yields 1.
congrArg- Applying a function to equal inputs gives equal outputs.
ZMod.natCast_eq_natCast_iff- Two natural numbers have equal residue modulo c if and only if they are congruent modulo c.
Nat.modEq_iff_dvd'- For a ≤ b, a ≡ b mod n is equivalent to n dividing b - a.
pow_mul- In a monoid, a^(m * n) = (a^m)^n.
one_pow- Any power of 1 is 1.
pow_add- In a monoid, a^(m + n) = a^m * a^n.
one_mul- Multiplying by 1 on the left leaves the element unchanged.
pow_one- An element raised to the first power is itself.
subgroup_rigidity_order_of_mds_finrank_adjoin_dvd- If an element x in a finite extension of F satisfies x^(|F|^r) = x, then the degree of F(x) over F divides r.
Nat.eq_zero_or_pos- Every natural number is either zero or strictly positive.
pow_eq_pow_iff_modEq- In a cancellative monoid, x^n = x^m if and only if n ≡ m modulo the order of x.
Finset.card_image_of_injOn- The image of a finite set under an injective map has the same cardinality as the set.
Finset.card_range- The cardinality of the range {0, ..., n - 1} is n.
IntermediateField.subset_adjoin- A set is contained in the intermediate field it adjoins.
pow_mem- A subfield or submonoid contains all powers of any of its elements.
LinearIndependent.of_comp- A family of vectors is linearly independent if its composition with an injective linear map is linearly independent.
Submodule.subtype- The canonical inclusion of a submodule into its ambient module.
LinearIndependent.fintype_card_le_finrank- The cardinality of a linearly independent set is at most the dimension of the ambient module.
- The lemma `subgroup_rigidity_order_of_mds_finrank_adjoin_dvd` proved in lines 8–18 is used as a sub-routine in line 85.
- The final step uses the `omega` tactic to conclude r = k from the chain of inequalities k ≤ m ≤ r ≤ k.
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.
open IntermediateField in/-- If a finite-field element `x` satisfies `x ^ (#F ^ r) = x`, then the degree of itsminimal polynomial over `F` divides `r`. -/lemma subgroup_rigidity_order_of_mds_finrank_adjoin_dvd {F L : Type*} [Field F] [Fintype F] [Field L] [Algebra F L] [Finite L] {r : ℕ} {x : L} (hx : x ^ (Fintype.card F ^ r) = x) : Module.finrank F (IntermediateField.adjoin F {x}) ∣ r := by let K : IntermediateField F L := IntermediateField.adjoin F {x} haveI : Finite K := inferInstance have hord : orderOf (FiniteField.frobeniusAlgHom F K) = Module.finrank F K := FiniteField.orderOf_frobeniusAlgHom F K rw [← hord] refine orderOf_dvd_iff_pow_eq_one.mpr ?_ refine IntermediateField.adjoin_algHom_ext F (s := {x}) ?_ intro y hy obtain rfl : y = x := by simpa using hy rw [AlgHom.coe_pow, FiniteField.coe_frobeniusAlgHom, pow_iterate, AlgHom.one_apply] exact Subtype.ext (by simpa using hx)/-- Subgroup rigidity: any cyclic subgroup of order n with the MDS property forces the order of q mod d to be k for every divisor d > 1 of n. -/theorem subgroup_rigidity_order_of_mds {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 := by classical intro d hdn hd1 haveI : Module.Finite F L := Module.finite_of_finrank_pos (by rw [hdim]; omega) haveI : Finite L := Module.finite_of_finite F haveI : Fintype L := Fintype.ofFinite L have hnk : 4 ≤ n := by omega have hq2 : 2 ≤ q := by rw [← hq]; exact Fintype.one_lt_card have hcardL : Fintype.card L = q ^ k := by rw [Module.card_eq_pow_finrank (K := F) (V := L), hq, hdim] have key : d ∣ q ^ k - 1 := by have h1 : Fintype.card H ∣ Fintype.card Lˣ := by rw [← Nat.card_eq_fintype_card, ← Nat.card_eq_fintype_card] exact Subgroup.card_subgroup_dvd_card H rw [hH_card, Fintype.card_units, hcardL] at h1 exact dvd_trans hdn h1 haveI : NeZero d := ⟨by omega⟩ have hqk : (q : ZMod d) ^ k = 1 := by have hzero : ((q ^ k - 1 : ℕ) : ZMod d) = 0 := (ZMod.natCast_eq_zero_iff _ _).mpr key have hone : 1 ≤ q ^ k := Nat.one_le_pow k q (by omega) calc (q : ZMod d) ^ k = ((q ^ k : ℕ) : ZMod d) := by push_cast; ring _ = ((q ^ k - 1 + 1 : ℕ) : ZMod d) := by rw [Nat.sub_add_cancel hone] _ = ((q ^ k - 1 : ℕ) : ZMod d) + 1 := by push_cast; ring _ = 1 := by rw [hzero, zero_add] have hr_dvd_k : orderOf (q : ZMod d) ∣ k := orderOf_dvd_iff_pow_eq_one.mpr hqk have hrle : orderOf (q : ZMod d) ≤ k := Nat.le_of_dvd (by omega) hr_dvd_k have hrpos : 0 < orderOf (q : ZMod d) := Nat.pos_of_dvd_of_pos hr_dvd_k (by omega) have hr_lt_d : orderOf (q : ZMod d) < d := by have hunit : IsUnit (q : ZMod d) := (isUnit_pow_iff (by omega : k ≠ 0)).mp (hqk ▸ isUnit_one) have hcop : q.Coprime d := (ZMod.isUnit_iff_coprime q d).mp hunit have hdiv : orderOf (q : ZMod d) ∣ Nat.totient d := by rw [← ZMod.coe_unitOfCoprime q hcop, orderOf_units, ← ZMod.card_units_eq_totient] exact orderOf_dvd_card have htpos : 0 < Nat.totient d := Nat.totient_pos.mpr (by omega) have hle : orderOf (q : ZMod d) ≤ d - 1 := by have h1 := Nat.le_of_dvd htpos hdiv have h2 := Nat.totient_lt d hd1 omega omega obtain ⟨g, hg⟩ := IsCyclic.exists_ofOrder_eq_natCard (α := H) have hgn : orderOf g = n := by rw [hg, Nat.card_eq_fintype_card, hH_card] set x : H := g ^ (n / d) with hx_def have hx_ord : orderOf x = d := by rw [hx_def, ← hgn] exact orderOf_pow_orderOf_div (by omega) (by rw [hgn]; exact hdn) have hxL_ord : orderOf ((x : Lˣ)) = d := by rw [Subgroup.orderOf_coe, hx_ord] have hx_d : ((x : Lˣ) : L) ^ d = 1 := by have h := pow_orderOf_eq_one (x : Lˣ) rw [hxL_ord] at h simpa using congrArg (fun u : Lˣ => (u : L)) h have hdvd_r : d ∣ q ^ orderOf (q : ZMod d) - 1 := by have hrpow : (q : ZMod d) ^ orderOf (q : ZMod d) = 1 := pow_orderOf_eq_one _ have h : q ^ orderOf (q : ZMod d) ≡ 1 [MOD d] := (ZMod.natCast_eq_natCast_iff (q ^ orderOf (q : ZMod d)) 1 d).mp (by simpa using hrpow) exact (Nat.modEq_iff_dvd' (Nat.one_le_pow _ q (by omega))).mp h.symm have hxL_pow : ((x : Lˣ) : L) ^ (q ^ orderOf (q : ZMod d)) = ((x : Lˣ) : L) := by obtain ⟨t, ht⟩ := hdvd_r have h1 : ((x : Lˣ) : L) ^ (q ^ orderOf (q : ZMod d) - 1) = 1 := by rw [ht, pow_mul, hx_d, one_pow] rw [← Nat.sub_add_cancel (Nat.one_le_pow _ q (by omega)), pow_add, h1, one_mul, pow_one] set K : IntermediateField F L := IntermediateField.adjoin F {((x : Lˣ) : L)} with hK set m : ℕ := Module.finrank F K with hm have hmdvd : m ∣ orderOf (q : ZMod d) := by have := subgroup_rigidity_order_of_mds_finrank_adjoin_dvd (F := F) (L := L) (r := orderOf (q : ZMod d)) (x := ((x : Lˣ) : L)) (by rw [hq]; exact hxL_pow) simpa [hm, hK] using this have hmle : m ≤ orderOf (q : ZMod d) := by rcases Nat.eq_zero_or_pos m with h0 | hpos · omega · exact Nat.le_of_dvd hrpos hmdvd have hkm : k ≤ m := by by_contra hcon push Not at hcon have hmd' : m ≤ d - 1 := by omega let φ : ℕ → H := fun j => ⟨((x : Lˣ)) ^ j, H.pow_mem x.2 j⟩ have hφinj : Set.InjOn φ ↑(Finset.range (m + 1)) := by intro j hj j' hj' heq rw [Finset.mem_coe, Finset.mem_range] at hj hj' have heq2 : ((x : Lˣ)) ^ j = ((x : Lˣ)) ^ j' := by have h2 := congrArg (fun u : H => ((u : Lˣ))) heq simpa [φ] using h2 have hmod : j ≡ j' [MOD d] := by have h3 := pow_eq_pow_iff_modEq.mp heq2 rwa [hxL_ord] at h3 exact hmod.eq_of_lt_of_lt (by omega) (by omega) set S : Finset H := (Finset.range (m + 1)).image φ with hS have hScard : S.card = m + 1 := by rw [hS, Finset.card_image_of_injOn hφinj, Finset.card_range] have hSk : S.card ≤ k := by omega have hind := h_mds S hSk have hmem : ∀ u : S, ((u.1 : Lˣ) : L) ∈ K := by intro u obtain ⟨j, hj, hju⟩ := Finset.mem_image.mp u.2 have hu : u.1 = φ j := hju.symm rw [hu] have hxK : ((x : Lˣ) : L) ∈ K := IntermediateField.subset_adjoin F {((x : Lˣ) : L)} (Set.mem_singleton _) have hp : ((φ j : H) : Lˣ) = ((x : Lˣ)) ^ j := rfl rw [hp] push_cast exact pow_mem hxK j have hindK : LinearIndependent F (fun u : S => (⟨((u.1 : Lˣ) : L), hmem u⟩ : ↥K.toSubmodule)) := LinearIndependent.of_comp (Submodule.subtype K.toSubmodule) hind have hfin : Fintype.card S ≤ Module.finrank F ↥K.toSubmodule := hindK.fintype_card_le_finrank rw [Fintype.card_coe, hScard] at hfin have hfm : Module.finrank F ↥K.toSubmodule = m := rfl omega omega