AFTD Auto-Formalizing Theoretical Domains

subgroup_rigidity_order_of_mds

theoremverifiedformalization

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.

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

    lines 8–18

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

      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)
  2. 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.

    lines 22–30

    uses Module.finite_of_finrank_pos, Module.finite_of_finite, Fintype.ofFinite, Fintype.one_lt_card, Module.card_eq_pow_finrank

      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]
  3. 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.

    lines 31–47

    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_pos

      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)
  4. 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.

    lines 48–59

    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_lt

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

    lines 60–71

    uses IsCyclic.exists_ofOrder_eq_natCard, Nat.card_eq_fintype_card, orderOf_pow_orderOf_div, Subgroup.orderOf_coe, pow_orderOf_eq_one, congrArg

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

    lines 72–81

    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_one

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

    lines 82–91

    uses subgroup_rigidity_order_of_mds_finrank_adjoin_dvd, Nat.eq_zero_or_pos, Nat.le_of_dvd

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

    lines 92–128

    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_finrank

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

    line 129

      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.

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

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