prefix_reversal_gcd_diff_necessary
If three prefix reversals of lengths k, m, n with 2 ≤ k < m < n generate the symmetric group Equiv.Perm (Fin n), then gcd(n - m, n - k) = 1.
Statement
theorem prefix_reversal_gcd_diff_necessary (k m n : ℕ)
(hk : 2 ≤ k) (hkm : k < m) (hmn : m < n)
(hgen : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} = ⊤) :
Nat.gcd (n - m) (n - k) = 1- Formalizes
- arXiv:2610.30892 Lemma 3.2
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- prefixReversalFor integers n and k, prefixReversal n k is the permutation in the symmetric group Equiv.Perm (Fin n) that reverses the first k elements…
Read back from the Lean
For any natural numbers $k$, $m$, and $n$, if $2 \le k$, $k < m$, $m < n$, and the subgroup of the symmetric group on $\mathrm{Fin}(n)$ (Equiv.Perm (Fin n)) generated by the three prefix reversals prefixReversal n k, prefixReversal n m, and prefixReversal n n is the entire symmetric group (equal to $\top$), then the greatest common divisor of $n - m$ and $n - k$ is $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 by contradiction. Assuming gcd(n - m, n - k) = d > 1, the three prefix reversals cannot generate the entire symmetric group because they all preserve a non-trivial structure. If d = 2 and n is even, all three lengths are even, so the generators preserve the block partition ⌊x / 2⌋. If d = 2 and n is odd, all lengths are odd, so they all preserve the position parity x % 2. If d ≥ 3, all three reversals preserve the non-trivial subset of positions congruent to 0 or n - 1 modulo d. In every case, the generated subgroup lies inside a proper subgroup, contradicting the generation hypothesis.
For j < k, the prefix reversal of length k maps j to k - 1 - j.
By definition, prefixReversal inverts the order of indices strictly less than k and leaves indices greater than or equal to k fixed; simplifying with the hypothesis j < k and k ≤ n yields (k - 1) - j.
lemma prefix_reversal_gcd_diff_necessary_apply_of_lt (n k : ℕ) (j : Fin n) (h : j.val < k) (hk : k ≤ n) : (prefixReversal n k j).val = k - 1 - j.val := by simp [prefixReversal, h, hk]
For j ≥ k, the prefix reversal of length k fixes j.
Since k ≤ j, the condition j < k is false by linear arithmetic (omega). Simplifying the definition with this fact confirms that j is mapped to itself.
lemma prefix_reversal_gcd_diff_necessary_apply_of_ge (n k : ℕ) (j : Fin n) (h : k ≤ j.val) : prefixReversal n k j = j := by have hlt : ¬ j.val < k := by omega simp [prefixReversal, hlt]
If d ∣ n - i, then i - 1 and n - 1 are equal modulo d.
The divisibility d ∣ n - i means i ≡ n [MOD d], so their casts to ℤ/d coincide by ZMod.natCast_eq_natCast_iff and Nat.modEq_iff_dvd'. Subtracting 1 on both sides via Nat.cast_sub gives (i - 1 : ℤ/d) = (n - 1 : ℤ/d).
uses
ZMod.natCast_eq_natCast_iff,Nat.modEq_iff_dvd',Nat.cast_sublemma prefix_reversal_gcd_diff_necessary_cast_pred_eq (d n i : ℕ) (hi : i ≤ n) (hi1 : 1 ≤ i) (hn1 : 1 ≤ n) (hdiv : d ∣ n - i) : ((i - 1 : ℕ) : ZMod d) = ((n - 1 : ℕ) : ZMod d) := by have hcast : (i : ZMod d) = (n : ZMod d) := by rw [ZMod.natCast_eq_natCast_iff] exact (Nat.modEq_iff_dvd' hi).mpr hdiv have hi_sub : ((i - 1 : ℕ) : ZMod d) = (i : ZMod d) - 1 := by rw [Nat.cast_sub hi1]; norm_num have hn_sub : ((n - 1 : ℕ) : ZMod d) = (n : ZMod d) - 1 := by rw [Nat.cast_sub hn1]; norm_num rw [hi_sub, hn_sub, hcast]
In ℤ/d, x ∈ {0, t} if and only if t - x ∈ {0, t}.
The map x ↦ t - x is an involution that swaps 0 and t: when x = 0, t - x = t; when x = t, t - x = 0. In both directions, abel and simplification verify the equivalence.
lemma prefix_reversal_gcd_diff_necessary_zmod_pair_reverse {d : ℕ} (t x : ZMod d) : (x = 0 ∨ x = t) ↔ (t - x = 0 ∨ t - x = t) := by constructor · rintro (h | h) · right; rw [h]; simp · left; rw [h]; simp · rintro (h | h) · right calc x = t - (t - x) := by abel _ = t - 0 := by rw [h] _ = t := by simp · left calc x = t - (t - x) := by abel _ = t - t := by rw [h] _ = 0 := by simp
If d ∣ n - i, the prefix reversal of length i preserves the pair condition x ≡ 0 ∨ x ≡ n - 1 [MOD d].
If x < i, the reversal sends x to i - 1 - x, which equals (n - 1) - x in ℤ/d because d ∣ n - i; by the previous involution lemma, this image is in {0, n - 1} if and only if x is. If x ≥ i, the reversal fixes x, so the condition is trivially invariant.
uses
prefix_reversal_gcd_diff_necessary_apply_of_lt,Nat.cast_sub,prefix_reversal_gcd_diff_necessary_cast_pred_eq,prefix_reversal_gcd_diff_necessary_zmod_pair_reverse,prefix_reversal_gcd_diff_necessary_apply_of_gelemma prefix_reversal_gcd_diff_necessary_set_preserved {d n i : ℕ} (hi1 : 1 ≤ i) (hi2 : i ≤ n) (hn1 : 1 ≤ n) (hdiv : d ∣ n - i) : ∀ x : Fin n, ((x.val : ZMod d) = 0 ∨ (x.val : ZMod d) = ((n - 1 : ℕ) : ZMod d)) ↔ (((prefixReversal n i x).val : ZMod d) = 0 ∨ ((prefixReversal n i x).val : ZMod d) = ((n - 1 : ℕ) : ZMod d)) := by intro x by_cases hx : x.val < i · have hcalc : (((prefixReversal n i x).val : ZMod d)) = ((n - 1 : ℕ) : ZMod d) - (x.val : ZMod d) := by rw [prefix_reversal_gcd_diff_necessary_apply_of_lt n i x hx hi2] have hxle : x.val ≤ i - 1 := by omega rw [Nat.cast_sub hxle] have hpred : ((i - 1 : ℕ) : ZMod d) = ((n - 1 : ℕ) : ZMod d) := prefix_reversal_gcd_diff_necessary_cast_pred_eq d n i hi2 hi1 hn1 hdiv rw [hpred] rw [hcalc] exact prefix_reversal_gcd_diff_necessary_zmod_pair_reverse _ _ · have hxge : i ≤ x.val := by omega rw [prefix_reversal_gcd_diff_necessary_apply_of_ge n i x hxge]
When i is even, the prefix reversal of length i preserves the block relation ⌊x / 2⌋ = ⌊y / 2⌋.
We case split on whether x < i and y < i. When both lie in the prefix, each is reflected as z ↦ i - 1 - z; since i is even, this reversal preserves the pairs of consecutive elements {2m, 2m + 1}, as verified by omega. When one or both lie outside the prefix, the identity action on the complement ensures blocks are preserved.
uses
prefix_reversal_gcd_diff_necessary_apply_of_lt,prefix_reversal_gcd_diff_necessary_apply_of_gelemma prefix_reversal_gcd_diff_necessary_pair_preserved {n i : ℕ} (hi : i % 2 = 0) (hin : i ≤ n) : ∀ x y : Fin n, x.val / 2 = y.val / 2 ↔ (prefixReversal n i x).val / 2 = (prefixReversal n i y).val / 2 := by intro x y by_cases hx : x.val < i · by_cases hy : y.val < i · rw [prefix_reversal_gcd_diff_necessary_apply_of_lt n i x hx hin, prefix_reversal_gcd_diff_necessary_apply_of_lt n i y hy hin] constructor <;> intro h <;> omega · have hyge : i ≤ y.val := by omega rw [prefix_reversal_gcd_diff_necessary_apply_of_lt n i x hx hin, prefix_reversal_gcd_diff_necessary_apply_of_ge n i y hyge] constructor <;> intro h <;> omega · have hxge : i ≤ x.val := by omega by_cases hy : y.val < i · rw [prefix_reversal_gcd_diff_necessary_apply_of_ge n i x hxge, prefix_reversal_gcd_diff_necessary_apply_of_lt n i y hy hin] constructor <;> intro h <;> omega · have hyge : i ≤ y.val := by omega rw [prefix_reversal_gcd_diff_necessary_apply_of_ge n i x hxge, prefix_reversal_gcd_diff_necessary_apply_of_ge n i y hyge]
When i is odd, the prefix reversal of length i preserves the parity x % 2 of every element.
For any index z < i, the reversal maps z to i - 1 - z. Since i is odd, i - 1 is even, so (i - 1 - z) % 2 = z % 2. For z ≥ i, z is unchanged, so every index preserves its parity modulo 2.
uses
prefix_reversal_gcd_diff_necessary_apply_of_lt,prefix_reversal_gcd_diff_necessary_apply_of_gelemma prefix_reversal_gcd_diff_necessary_parity_fiber {n i : ℕ} (hi : i % 2 = 1) (hin : i ≤ n) : ∀ x y : Fin n, x.val % 2 = y.val % 2 ↔ (prefixReversal n i x).val % 2 = (prefixReversal n i y).val % 2 := by intro x y have key : ∀ z : Fin n, z.val % 2 = (prefixReversal n i z).val % 2 := by intro z by_cases hz : z.val < i · rw [prefix_reversal_gcd_diff_necessary_apply_of_lt n i z hz hin]; omega · have hzge : i ≤ z.val := by omega rw [prefix_reversal_gcd_diff_necessary_apply_of_ge n i z hzge] rw [key x, key y]
The set of permutations stabilizing a subset S is a subgroup of Equiv.Perm α.
The identity permutation stabilizes S; composition preserves S by Equiv.Perm.mul_apply and transitivity of iff; and inverses preserve S by evaluating the stabilization condition at the preimage.
uses
Equiv.Perm.mul_applydef prefix_reversal_gcd_diff_necessary_stabilizer_set {α : Type} (S : Set α) : Subgroup (Equiv.Perm α) where carrier := {σ | ∀ x, x ∈ S ↔ σ x ∈ S} one_mem' := by intro x; simp mul_mem' := by intro σ τ hσ hτ x rw [Equiv.Perm.mul_apply] exact (hτ x).trans (hσ (τ x)) inv_mem' := by intro σ hσ x have h := (hσ (σ⁻¹ x)).symm simpa using h
The set of permutations preserving fibers of a function q is a subgroup of Equiv.Perm (Fin n).
The identity preserves fibers; composition preserves fibers by Equiv.Perm.mul_apply and transitivity; and inversion preserves fibers by substituting inverse values.
uses
Equiv.Perm.mul_applydef prefix_reversal_gcd_diff_necessary_fiber_rel {n : ℕ} (q : Fin n → ℕ) : Subgroup (Equiv.Perm (Fin n)) where carrier := {σ | ∀ x y, q x = q y ↔ q (σ x) = q (σ y)} one_mem' := by intro x y; simp mul_mem' := by intro σ τ hσ hτ x y rw [Equiv.Perm.mul_apply] exact (hτ x y).trans (hσ (τ x) (τ y)) inv_mem' := by intro σ hσ x y have h := (hσ (σ⁻¹ x) (σ⁻¹ y)).symm simpa using h
If a ∈ S and b ∉ S, the stabilizer of S is a proper subgroup of Equiv.Perm (Fin n).
If the stabilizer were the full group ⊤, the transposition Equiv.swap a b would belong to it. But swapping a and b moves a ∈ S to b ∉ S, which violates the invariance of S.
uses
Subgroup.mem_top,Equiv.swap_apply_leftlemma prefix_reversal_gcd_diff_necessary_stabilizer_set_ne_top {n : ℕ} (S : Set (Fin n)) (a b : Fin n) (ha : a ∈ S) (hb : b ∉ S) : prefix_reversal_gcd_diff_necessary_stabilizer_set S ≠ ⊤ := by intro htop have hmem : Equiv.swap a b ∈ prefix_reversal_gcd_diff_necessary_stabilizer_set S := by rw [htop]; exact Subgroup.mem_top _ have h := hmem a rw [Equiv.swap_apply_left] at h exact hb (h.mp ha)
If q a = q b and q a ≠ q c with b ≠ a and c ≠ a, the fiber-preserving subgroup is proper.
If the subgroup were ⊤, the transposition Equiv.swap b c would preserve fibers. Evaluating at a and b shows q a = q b ↔ q a = q c since a is fixed by the transposition, contradicting q a = q b and q a ≠ q c.
uses
Subgroup.mem_top,Equiv.swap_apply_of_ne_of_ne,Ne.symm,Equiv.swap_apply_leftlemma prefix_reversal_gcd_diff_necessary_fiber_ne_top {n : ℕ} (q : Fin n → ℕ) {a b c : Fin n} (hab : q a = q b) (hac : q a ≠ q c) (hba : b ≠ a) (hca : c ≠ a) : prefix_reversal_gcd_diff_necessary_fiber_rel q ≠ ⊤ := by intro htop have hmem : Equiv.swap b c ∈ prefix_reversal_gcd_diff_necessary_fiber_rel q := by rw [htop]; exact Subgroup.mem_top _ have h := hmem a b rw [Equiv.swap_apply_of_ne_of_ne (a := b) (b := c) (x := a) (Ne.symm hba) (Ne.symm hca), Equiv.swap_apply_left] at h exact hac (h.mp hab)
In ℤ/d with d > 1, 1 ≠ 0.
If 1 = 0 in ℤ/d, taking canonical representatives via ZMod.val and congrArg gives 1 = 0 in ℕ, a contradiction by omega.
uses
congrArg,ZMod.val_zero,ZMod.val_cast_of_ltlemma prefix_reversal_gcd_diff_necessary_zmod_one_ne_zero {d : ℕ} (hd : 1 < d) : (1 : ZMod d) ≠ 0 := by intro h have hv := congrArg ZMod.val h rw [ZMod.val_zero] at hv have h1 : ZMod.val (1 : ZMod d) = 1 := by simpa using ZMod.val_cast_of_lt hd omega
In ℤ/d with d > 2, 2 ≠ 0.
If 2 = 0 in ℤ/d, taking canonical representatives gives 2 = 0 in ℕ since 2 < d, which is impossible by omega.
uses
congrArg,ZMod.val_zero,ZMod.val_cast_of_ltlemma prefix_reversal_gcd_diff_necessary_zmod_two_ne_zero {d : ℕ} (hd : 2 < d) : (2 : ZMod d) ≠ 0 := by intro h have hv := congrArg ZMod.val h rw [ZMod.val_zero] at hv have h2 : ZMod.val (2 : ZMod d) = 2 := by simpa using ZMod.val_cast_of_lt hd omega
In ℤ/d with d > 2, 2 ≠ 1.
If 2 = 1 in ℤ/d, taking canonical representatives gives 2 = 1 in ℕ since 1 < d and 2 < d, which is impossible by omega.
uses
congrArg,ZMod.val_cast_of_ltlemma prefix_reversal_gcd_diff_necessary_zmod_two_ne_one {d : ℕ} (hd : 2 < d) : (2 : ZMod d) ≠ 1 := by intro h have hv := congrArg ZMod.val h have h2 : ZMod.val (2 : ZMod d) = 2 := by simpa using ZMod.val_cast_of_lt hd have h1 : ZMod.val (1 : ZMod d) = 1 := by simpa using ZMod.val_cast_of_lt (by omega : 1 < d) omega
For d ≥ 3 and any t ∈ ℤ/d, there is an element y ∉ {0, t}.
If t = 0, y = 1 works since 1 ≠ 0. If t = 1, y = 2 works since 2 ≠ 0 and 2 ≠ 1. If t ∉ {0, 1}, y = 1 works since 1 ≠ 0 and 1 ≠ t.
uses
prefix_reversal_gcd_diff_necessary_zmod_one_ne_zero,prefix_reversal_gcd_diff_necessary_zmod_two_ne_zero,prefix_reversal_gcd_diff_necessary_zmod_two_ne_onelemma prefix_reversal_gcd_diff_necessary_exists_zmod_not_pair {d : ℕ} (hd3 : 3 ≤ d) (t : ZMod d) : ∃ y : ZMod d, y ≠ 0 ∧ y ≠ t := by by_cases ht0 : t = 0 · refine ⟨1, prefix_reversal_gcd_diff_necessary_zmod_one_ne_zero (by omega), ?_⟩ intro h rw [ht0] at h exact prefix_reversal_gcd_diff_necessary_zmod_one_ne_zero (by omega) h · by_cases ht1 : t = 1 · refine ⟨2, prefix_reversal_gcd_diff_necessary_zmod_two_ne_zero (by omega), ?_⟩ intro h rw [ht1] at h exact prefix_reversal_gcd_diff_necessary_zmod_two_ne_one (by omega) h · refine ⟨1, prefix_reversal_gcd_diff_necessary_zmod_one_ne_zero (by omega), ?_⟩ intro h exact ht1 h.symm
For d > 0, the canonical representative y.val of any y ∈ ℤ/d satisfies y.val < d.
The condition d > 0 provides an instance of NeZero d, and ZMod.val_lt establishes that the value is strictly less than d.
uses
ZMod.val_ltlemma prefix_reversal_gcd_diff_necessary_zmod_val_lt {d : ℕ} (hd : 0 < d) (y : ZMod d) : y.val < d := by haveI : NeZero d := ⟨by omega⟩ exact ZMod.val_lt y
For d > 0, casting y.val back to ℤ/d yields y.
With NeZero d from d > 0, ZMod.natCast_zmod_val shows that casting the canonical representative y.val back to ℤ/d recovers y.
uses
ZMod.natCast_zmod_vallemma prefix_reversal_gcd_diff_necessary_cast_val {d : ℕ} (hd : 0 < d) (y : ZMod d) : ((y.val : ℕ) : ZMod d) = y := by haveI : NeZero d := ⟨by omega⟩ exact ZMod.natCast_zmod_val y /-- Generation of the symmetric group by three prefix reversals requires gcd(n - m, n - k) = 1. -/
Suppose for contradiction that d = gcd(n - m, n - k) ≠ 1; then 0 < d ≤ n and d divides n - k and n - m.
From 2 ≤ k < m < n, we have 1 ≤ n and 0 < n - k. By definition of gcd, d ∣ n - k and d ∣ n - m, which implies d > 0 by Nat.pos_of_dvd_of_pos and d ≤ n - k ≤ n by Nat.le_of_dvd.
uses
Nat.gcd_dvd_right,Nat.gcd_dvd_left,Nat.pos_of_dvd_of_pos,Nat.le_of_dvdtheorem prefix_reversal_gcd_diff_necessary (k m n : ℕ) (hk : 2 ≤ k) (hkm : k < m) (hmn : m < n) (hgen : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} = ⊤) : Nat.gcd (n - m) (n - k) = 1 := by by_contra hne set d := Nat.gcd (n - m) (n - k) with hd have hn1 : 1 ≤ n := by omega have hkn : k ≤ n := by omega have hmn' : m ≤ n := by omega have hk1 : 1 ≤ k := by omega have hm1 : 1 ≤ m := by omega have hdivk : d ∣ n - k := hd ▸ Nat.gcd_dvd_right _ _ have hdivm : d ∣ n - m := hd ▸ Nat.gcd_dvd_left _ _ have hdpos : 0 < d := Nat.pos_of_dvd_of_pos hdivk (by omega) have hdn : d ≤ n := by have h1 : d ≤ n - k := Nat.le_of_dvd (by omega) hdivk omega
If d = 2 and n is even, all three prefix reversals preserve the block partition ⌊x / 2⌋, yielding a proper subgroup and a contradiction.
Since d < 3 and d ≠ 1, we must have d = 2. When n is even, 2 ∣ n - k and 2 ∣ n - m force k and m to be even. The fiber-preserving subgroup for q(x) = x.val / 2 is proper because q(0) = q(1) ≠ q(2). By prefix_reversal_gcd_diff_necessary_pair_preserved, all three generators preserve q, so their closure is contained in this proper subgroup, contradicting that they generate ⊤.
uses
Nat.lt_or_ge,Nat.mod_two_eq_zero_or_one,prefix_reversal_gcd_diff_necessary_fiber_ne_top,Subgroup.closure_le,prefix_reversal_gcd_diff_necessary_pair_preserved,le_refl,le_antisymm,le_toprcases Nat.lt_or_ge d 3 with hd3 | hd3 · have hd2' : d = 2 := by omega have hdivk2 : 2 ∣ n - k := hd2' ▸ hdivk have hdivm2 : 2 ∣ n - m := hd2' ▸ hdivm have hn4 : 4 ≤ n := by omega rcases Nat.mod_two_eq_zero_or_one n with hnpar | hnpar · have hk2 : k % 2 = 0 := by obtain ⟨c, hc⟩ := hdivk2; omega have hm2 : m % 2 = 0 := by obtain ⟨c, hc⟩ := hdivm2; omega set q : Fin n → ℕ := fun x => x.val / 2 with hq have hK : prefix_reversal_gcd_diff_necessary_fiber_rel q ≠ ⊤ := by refine prefix_reversal_gcd_diff_necessary_fiber_ne_top q (a := ⟨0, by omega⟩) (b := ⟨1, by omega⟩) (c := ⟨2, by omega⟩) ?_ ?_ ?_ ?_ · show (0:ℕ)/2 = 1/2; rfl · show (0:ℕ)/2 ≠ 2/2; norm_num · show (⟨1, by omega⟩ : Fin n) ≠ ⟨0, by omega⟩; intro h; simp at h · show (⟨2, by omega⟩ : Fin n) ≠ ⟨0, by omega⟩; intro h; simp at h have hsub : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} ≤ prefix_reversal_gcd_diff_necessary_fiber_rel q := by rw [Subgroup.closure_le] intro g hg simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hg rcases hg with rfl | rfl | rfl · exact prefix_reversal_gcd_diff_necessary_pair_preserved hk2 hkn · exact prefix_reversal_gcd_diff_necessary_pair_preserved hm2 hmn' · exact prefix_reversal_gcd_diff_necessary_pair_preserved (by omega) (le_refl n) rw [hgen] at hsub exact hK (le_antisymm le_top hsub)
If d = 2 and n is odd, all three prefix reversals preserve parity x % 2, yielding a proper subgroup and a contradiction.
When n is odd, 2 ∣ n - k and 2 ∣ n - m force k and m to be odd. The fiber-preserving subgroup for q(x) = x.val % 2 is proper because q(0) = q(2) ≠ q(1). Since k, m, n are all odd, prefix_reversal_gcd_diff_necessary_parity_fiber shows each generator preserves parity, placing their closure in a proper subgroup and contradicting generation of ⊤.
uses
prefix_reversal_gcd_diff_necessary_fiber_ne_top,Subgroup.closure_le,prefix_reversal_gcd_diff_necessary_parity_fiber,le_refl,le_antisymm,le_top· have hk2 : k % 2 = 1 := by obtain ⟨c, hc⟩ := hdivk2; omega have hm2 : m % 2 = 1 := by obtain ⟨c, hc⟩ := hdivm2; omega set q : Fin n → ℕ := fun x => x.val % 2 with hq have hK : prefix_reversal_gcd_diff_necessary_fiber_rel q ≠ ⊤ := by refine prefix_reversal_gcd_diff_necessary_fiber_ne_top q (a := ⟨0, by omega⟩) (b := ⟨2, by omega⟩) (c := ⟨1, by omega⟩) ?_ ?_ ?_ ?_ · show (0:ℕ)%2 = 2%2; norm_num · show (0:ℕ)%2 ≠ 1%2; norm_num · show (⟨2, by omega⟩ : Fin n) ≠ ⟨0, by omega⟩; intro h; simp at h · show (⟨1, by omega⟩ : Fin n) ≠ ⟨0, by omega⟩; intro h; simp at h have hsub : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} ≤ prefix_reversal_gcd_diff_necessary_fiber_rel q := by rw [Subgroup.closure_le] intro g hg simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hg rcases hg with rfl | rfl | rfl · exact prefix_reversal_gcd_diff_necessary_parity_fiber hk2 hkn · exact prefix_reversal_gcd_diff_necessary_parity_fiber hm2 hmn' · exact prefix_reversal_gcd_diff_necessary_parity_fiber (by omega) (le_refl n) rw [hgen] at hsub exact hK (le_antisymm le_top hsub)
If d ≥ 3, the set S = {x : Fin n | x.val ≡ 0 ∨ x.val ≡ n - 1 [MOD d]} has a proper stabilizer subgroup.
The index 0 belongs to S because 0 ≡ 0 [MOD d]. Since d ≥ 3, there exists y ∈ ℤ/d not in {0, n - 1 [MOD d]}, and its representative y.val < d ≤ n gives an element of Fin n outside S. By prefix_reversal_gcd_diff_necessary_stabilizer_set_ne_top, S is a proper, non-empty subset, so its stabilizer is proper.
uses
prefix_reversal_gcd_diff_necessary_exists_zmod_not_pair,prefix_reversal_gcd_diff_necessary_zmod_val_lt,prefix_reversal_gcd_diff_necessary_stabilizer_set_ne_top,Or.inl,Nat.cast_zero,prefix_reversal_gcd_diff_necessary_cast_val· set S : Set (Fin n) := {x : Fin n | (x.val : ZMod d) = 0 ∨ (x.val : ZMod d) = ((n - 1 : ℕ) : ZMod d)} with hS have hK : prefix_reversal_gcd_diff_necessary_stabilizer_set S ≠ ⊤ := by obtain ⟨y, hy0, hyt⟩ := prefix_reversal_gcd_diff_necessary_exists_zmod_not_pair hd3 ((n - 1 : ℕ) : ZMod d) have hyv : y.val < n := by have h1 : y.val < d := prefix_reversal_gcd_diff_necessary_zmod_val_lt (by omega) y omega refine prefix_reversal_gcd_diff_necessary_stabilizer_set_ne_top S ⟨0, by omega⟩ ⟨y.val, hyv⟩ ?_ ?_ · show ((0:ℕ) : ZMod d) = 0 ∨ ((0:ℕ) : ZMod d) = ((n - 1 : ℕ) : ZMod d) exact Or.inl (Nat.cast_zero) · show ¬ (((y.val : ℕ) : ZMod d) = 0 ∨ ((y.val : ℕ) : ZMod d) = ((n - 1 : ℕ) : ZMod d)) rw [prefix_reversal_gcd_diff_necessary_cast_val (by omega) y] exact fun h => h.elim hy0 hyt
If d ≥ 3, all three generators stabilize S, so their closure is contained in the proper stabilizer, contradiction.
Because d ∣ n - k, d ∣ n - m, and d ∣ n - n = 0, prefix_reversal_gcd_diff_necessary_set_preserved shows that each of the three prefix reversals stabilizes S. By Subgroup.closure_le, their generated subgroup is contained in the stabilizer of S, contradicting that the generators generate the full symmetric group ⊤.
uses
Subgroup.closure_le,prefix_reversal_gcd_diff_necessary_set_preserved,le_refl,Nat.sub_self,Nat.dvd_zero,le_antisymm,le_tophave hsub : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} ≤ prefix_reversal_gcd_diff_necessary_stabilizer_set S := by rw [Subgroup.closure_le] intro g hg simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hg rcases hg with rfl | rfl | rfl · exact prefix_reversal_gcd_diff_necessary_set_preserved hk1 hkn hn1 hdivk · exact prefix_reversal_gcd_diff_necessary_set_preserved hm1 hmn' hn1 hdivm · refine prefix_reversal_gcd_diff_necessary_set_preserved hn1 (le_refl n) hn1 ?_ rw [Nat.sub_self] exact Nat.dvd_zero d rw [hgen] at hsub exact hK (le_antisymm le_top hsub)
ZMod.natCast_eq_natCast_iff- Two natural numbers cast to the same element in ℤ/c if and only if they are congruent modulo c.
Nat.modEq_iff_dvd'- For a ≤ b, a ≡ b [MOD n] if and only if n divides b - a.
Nat.cast_sub- For m ≤ n, casting n - m to an additive group with one equals the cast of n minus the cast of m.
prefix_reversal_gcd_diff_necessary_apply_of_lt- If j < k and k ≤ n, the prefix reversal of length k sends j to k - 1 - j.
prefix_reversal_gcd_diff_necessary_cast_pred_eq- If i ≤ n, 1 ≤ i, 1 ≤ n, and d ∣ n - i, then i - 1 and n - 1 are equal when cast to ℤ/d.
prefix_reversal_gcd_diff_necessary_zmod_pair_reverse- In ℤ/d, an element x is 0 or t if and only if t - x is 0 or t.
prefix_reversal_gcd_diff_necessary_apply_of_ge- If k ≤ j, the prefix reversal of length k leaves j unchanged.
Equiv.Perm.mul_apply- Permutation composition evaluates as (f * g)(x) = f(g(x)).
Subgroup.mem_top- Every element of a group belongs to the top subgroup ⊤.
Equiv.swap_apply_left- The transposition swapping a and b sends a to b.
Equiv.swap_apply_of_ne_of_ne- A transposition swapping a and b fixes any element x different from both a and b.
Ne.symm- Inequality is symmetric: if a ≠ b then b ≠ a.
congrArg- Applying a function to both sides of an equality preserves equality.
ZMod.val_zero- The canonical representative of 0 in ℤ/n is 0 in ℕ.
ZMod.val_cast_of_lt- For a < n, the canonical representative in ℕ of the cast of a in ℤ/n is a.
prefix_reversal_gcd_diff_necessary_zmod_one_ne_zero- In ℤ/d with d > 1, 1 is not equal to 0.
prefix_reversal_gcd_diff_necessary_zmod_two_ne_zero- In ℤ/d with d > 2, 2 is not equal to 0.
prefix_reversal_gcd_diff_necessary_zmod_two_ne_one- In ℤ/d with d > 2, 2 is not equal to 1.
ZMod.val_lt- The canonical representative in ℕ of an element in ℤ/n is strictly less than n.
ZMod.natCast_zmod_val- Casting the canonical representative y.val back to ℤ/n recovers the element y.
Nat.gcd_dvd_right- The greatest common divisor of a and b divides b.
Nat.gcd_dvd_left- The greatest common divisor of a and b divides a.
Nat.pos_of_dvd_of_pos- If m divides n and n > 0, then m > 0.
Nat.le_of_dvd- If m divides n and n > 0, then m ≤ n.
Nat.lt_or_ge- For any two natural numbers n and m, either n < m or n ≥ m.
Nat.mod_two_eq_zero_or_one- Every natural number is either 0 or 1 modulo 2.
prefix_reversal_gcd_diff_necessary_fiber_ne_top- The fiber-preserving subgroup of q is proper if there exist elements with q(a) = q(b) ≠ q(c).
Subgroup.closure_le- The subgroup closure of a subset S is contained in K if and only if S ⊆ K.
prefix_reversal_gcd_diff_necessary_pair_preserved- Prefix reversal of even length i preserves the block relation ⌊x / 2⌋ = ⌊y / 2⌋.
le_refl- The order relation ≤ is reflexive: a ≤ a.
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
le_top- Every element in a preorder with a top element satisfies a ≤ ⊤.
prefix_reversal_gcd_diff_necessary_parity_fiber- Prefix reversal of odd length i preserves the parity relation x % 2 = y % 2.
prefix_reversal_gcd_diff_necessary_exists_zmod_not_pair- In ℤ/d with d ≥ 3, for any t there exists y with y ≠ 0 and y ≠ t.
prefix_reversal_gcd_diff_necessary_zmod_val_lt- For d > 0, the canonical representative y.val of any y ∈ ℤ/d is strictly less than d.
prefix_reversal_gcd_diff_necessary_stabilizer_set_ne_top- The set stabilizer subgroup of a subset S is proper if S contains an element a and misses an element b.
Or.inl- Disjunction introduction from the left: p implies p ∨ q.
Nat.cast_zero- Casting 0 to an additive monoid with one yields 0.
prefix_reversal_gcd_diff_necessary_cast_val- For d > 0, casting the numerical value of y ∈ ℤ/d back to ℤ/d yields y.
prefix_reversal_gcd_diff_necessary_set_preserved- If d ∣ n - i, prefix reversal of length i preserves the property of being congruent to 0 or n - 1 modulo d.
Nat.sub_self- For any natural number n, n - n = 0.
Nat.dvd_zero- Every natural number divides 0.
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.
lemma prefix_reversal_gcd_diff_necessary_apply_of_lt (n k : ℕ) (j : Fin n) (h : j.val < k) (hk : k ≤ n) : (prefixReversal n k j).val = k - 1 - j.val := by simp [prefixReversal, h, hk]lemma prefix_reversal_gcd_diff_necessary_apply_of_ge (n k : ℕ) (j : Fin n) (h : k ≤ j.val) : prefixReversal n k j = j := by have hlt : ¬ j.val < k := by omega simp [prefixReversal, hlt]lemma prefix_reversal_gcd_diff_necessary_cast_pred_eq (d n i : ℕ) (hi : i ≤ n) (hi1 : 1 ≤ i) (hn1 : 1 ≤ n) (hdiv : d ∣ n - i) : ((i - 1 : ℕ) : ZMod d) = ((n - 1 : ℕ) : ZMod d) := by have hcast : (i : ZMod d) = (n : ZMod d) := by rw [ZMod.natCast_eq_natCast_iff] exact (Nat.modEq_iff_dvd' hi).mpr hdiv have hi_sub : ((i - 1 : ℕ) : ZMod d) = (i : ZMod d) - 1 := by rw [Nat.cast_sub hi1]; norm_num have hn_sub : ((n - 1 : ℕ) : ZMod d) = (n : ZMod d) - 1 := by rw [Nat.cast_sub hn1]; norm_num rw [hi_sub, hn_sub, hcast]lemma prefix_reversal_gcd_diff_necessary_zmod_pair_reverse {d : ℕ} (t x : ZMod d) : (x = 0 ∨ x = t) ↔ (t - x = 0 ∨ t - x = t) := by constructor · rintro (h | h) · right; rw [h]; simp · left; rw [h]; simp · rintro (h | h) · right calc x = t - (t - x) := by abel _ = t - 0 := by rw [h] _ = t := by simp · left calc x = t - (t - x) := by abel _ = t - t := by rw [h] _ = 0 := by simplemma prefix_reversal_gcd_diff_necessary_set_preserved {d n i : ℕ} (hi1 : 1 ≤ i) (hi2 : i ≤ n) (hn1 : 1 ≤ n) (hdiv : d ∣ n - i) : ∀ x : Fin n, ((x.val : ZMod d) = 0 ∨ (x.val : ZMod d) = ((n - 1 : ℕ) : ZMod d)) ↔ (((prefixReversal n i x).val : ZMod d) = 0 ∨ ((prefixReversal n i x).val : ZMod d) = ((n - 1 : ℕ) : ZMod d)) := by intro x by_cases hx : x.val < i · have hcalc : (((prefixReversal n i x).val : ZMod d)) = ((n - 1 : ℕ) : ZMod d) - (x.val : ZMod d) := by rw [prefix_reversal_gcd_diff_necessary_apply_of_lt n i x hx hi2] have hxle : x.val ≤ i - 1 := by omega rw [Nat.cast_sub hxle] have hpred : ((i - 1 : ℕ) : ZMod d) = ((n - 1 : ℕ) : ZMod d) := prefix_reversal_gcd_diff_necessary_cast_pred_eq d n i hi2 hi1 hn1 hdiv rw [hpred] rw [hcalc] exact prefix_reversal_gcd_diff_necessary_zmod_pair_reverse _ _ · have hxge : i ≤ x.val := by omega rw [prefix_reversal_gcd_diff_necessary_apply_of_ge n i x hxge]lemma prefix_reversal_gcd_diff_necessary_pair_preserved {n i : ℕ} (hi : i % 2 = 0) (hin : i ≤ n) : ∀ x y : Fin n, x.val / 2 = y.val / 2 ↔ (prefixReversal n i x).val / 2 = (prefixReversal n i y).val / 2 := by intro x y by_cases hx : x.val < i · by_cases hy : y.val < i · rw [prefix_reversal_gcd_diff_necessary_apply_of_lt n i x hx hin, prefix_reversal_gcd_diff_necessary_apply_of_lt n i y hy hin] constructor <;> intro h <;> omega · have hyge : i ≤ y.val := by omega rw [prefix_reversal_gcd_diff_necessary_apply_of_lt n i x hx hin, prefix_reversal_gcd_diff_necessary_apply_of_ge n i y hyge] constructor <;> intro h <;> omega · have hxge : i ≤ x.val := by omega by_cases hy : y.val < i · rw [prefix_reversal_gcd_diff_necessary_apply_of_ge n i x hxge, prefix_reversal_gcd_diff_necessary_apply_of_lt n i y hy hin] constructor <;> intro h <;> omega · have hyge : i ≤ y.val := by omega rw [prefix_reversal_gcd_diff_necessary_apply_of_ge n i x hxge, prefix_reversal_gcd_diff_necessary_apply_of_ge n i y hyge]lemma prefix_reversal_gcd_diff_necessary_parity_fiber {n i : ℕ} (hi : i % 2 = 1) (hin : i ≤ n) : ∀ x y : Fin n, x.val % 2 = y.val % 2 ↔ (prefixReversal n i x).val % 2 = (prefixReversal n i y).val % 2 := by intro x y have key : ∀ z : Fin n, z.val % 2 = (prefixReversal n i z).val % 2 := by intro z by_cases hz : z.val < i · rw [prefix_reversal_gcd_diff_necessary_apply_of_lt n i z hz hin]; omega · have hzge : i ≤ z.val := by omega rw [prefix_reversal_gcd_diff_necessary_apply_of_ge n i z hzge] rw [key x, key y]def prefix_reversal_gcd_diff_necessary_stabilizer_set {α : Type} (S : Set α) : Subgroup (Equiv.Perm α) where carrier := {σ | ∀ x, x ∈ S ↔ σ x ∈ S} one_mem' := by intro x; simp mul_mem' := by intro σ τ hσ hτ x rw [Equiv.Perm.mul_apply] exact (hτ x).trans (hσ (τ x)) inv_mem' := by intro σ hσ x have h := (hσ (σ⁻¹ x)).symm simpa using hdef prefix_reversal_gcd_diff_necessary_fiber_rel {n : ℕ} (q : Fin n → ℕ) : Subgroup (Equiv.Perm (Fin n)) where carrier := {σ | ∀ x y, q x = q y ↔ q (σ x) = q (σ y)} one_mem' := by intro x y; simp mul_mem' := by intro σ τ hσ hτ x y rw [Equiv.Perm.mul_apply] exact (hτ x y).trans (hσ (τ x) (τ y)) inv_mem' := by intro σ hσ x y have h := (hσ (σ⁻¹ x) (σ⁻¹ y)).symm simpa using hlemma prefix_reversal_gcd_diff_necessary_stabilizer_set_ne_top {n : ℕ} (S : Set (Fin n)) (a b : Fin n) (ha : a ∈ S) (hb : b ∉ S) : prefix_reversal_gcd_diff_necessary_stabilizer_set S ≠ ⊤ := by intro htop have hmem : Equiv.swap a b ∈ prefix_reversal_gcd_diff_necessary_stabilizer_set S := by rw [htop]; exact Subgroup.mem_top _ have h := hmem a rw [Equiv.swap_apply_left] at h exact hb (h.mp ha)lemma prefix_reversal_gcd_diff_necessary_fiber_ne_top {n : ℕ} (q : Fin n → ℕ) {a b c : Fin n} (hab : q a = q b) (hac : q a ≠ q c) (hba : b ≠ a) (hca : c ≠ a) : prefix_reversal_gcd_diff_necessary_fiber_rel q ≠ ⊤ := by intro htop have hmem : Equiv.swap b c ∈ prefix_reversal_gcd_diff_necessary_fiber_rel q := by rw [htop]; exact Subgroup.mem_top _ have h := hmem a b rw [Equiv.swap_apply_of_ne_of_ne (a := b) (b := c) (x := a) (Ne.symm hba) (Ne.symm hca), Equiv.swap_apply_left] at h exact hac (h.mp hab)lemma prefix_reversal_gcd_diff_necessary_zmod_one_ne_zero {d : ℕ} (hd : 1 < d) : (1 : ZMod d) ≠ 0 := by intro h have hv := congrArg ZMod.val h rw [ZMod.val_zero] at hv have h1 : ZMod.val (1 : ZMod d) = 1 := by simpa using ZMod.val_cast_of_lt hd omegalemma prefix_reversal_gcd_diff_necessary_zmod_two_ne_zero {d : ℕ} (hd : 2 < d) : (2 : ZMod d) ≠ 0 := by intro h have hv := congrArg ZMod.val h rw [ZMod.val_zero] at hv have h2 : ZMod.val (2 : ZMod d) = 2 := by simpa using ZMod.val_cast_of_lt hd omegalemma prefix_reversal_gcd_diff_necessary_zmod_two_ne_one {d : ℕ} (hd : 2 < d) : (2 : ZMod d) ≠ 1 := by intro h have hv := congrArg ZMod.val h have h2 : ZMod.val (2 : ZMod d) = 2 := by simpa using ZMod.val_cast_of_lt hd have h1 : ZMod.val (1 : ZMod d) = 1 := by simpa using ZMod.val_cast_of_lt (by omega : 1 < d) omegalemma prefix_reversal_gcd_diff_necessary_exists_zmod_not_pair {d : ℕ} (hd3 : 3 ≤ d) (t : ZMod d) : ∃ y : ZMod d, y ≠ 0 ∧ y ≠ t := by by_cases ht0 : t = 0 · refine ⟨1, prefix_reversal_gcd_diff_necessary_zmod_one_ne_zero (by omega), ?_⟩ intro h rw [ht0] at h exact prefix_reversal_gcd_diff_necessary_zmod_one_ne_zero (by omega) h · by_cases ht1 : t = 1 · refine ⟨2, prefix_reversal_gcd_diff_necessary_zmod_two_ne_zero (by omega), ?_⟩ intro h rw [ht1] at h exact prefix_reversal_gcd_diff_necessary_zmod_two_ne_one (by omega) h · refine ⟨1, prefix_reversal_gcd_diff_necessary_zmod_one_ne_zero (by omega), ?_⟩ intro h exact ht1 h.symmlemma prefix_reversal_gcd_diff_necessary_zmod_val_lt {d : ℕ} (hd : 0 < d) (y : ZMod d) : y.val < d := by haveI : NeZero d := ⟨by omega⟩ exact ZMod.val_lt ylemma prefix_reversal_gcd_diff_necessary_cast_val {d : ℕ} (hd : 0 < d) (y : ZMod d) : ((y.val : ℕ) : ZMod d) = y := by haveI : NeZero d := ⟨by omega⟩ exact ZMod.natCast_zmod_val y/-- Generation of the symmetric group by three prefix reversals requires gcd(n - m, n - k) = 1. -/theorem prefix_reversal_gcd_diff_necessary (k m n : ℕ) (hk : 2 ≤ k) (hkm : k < m) (hmn : m < n) (hgen : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} = ⊤) : Nat.gcd (n - m) (n - k) = 1 := by by_contra hne set d := Nat.gcd (n - m) (n - k) with hd have hn1 : 1 ≤ n := by omega have hkn : k ≤ n := by omega have hmn' : m ≤ n := by omega have hk1 : 1 ≤ k := by omega have hm1 : 1 ≤ m := by omega have hdivk : d ∣ n - k := hd ▸ Nat.gcd_dvd_right _ _ have hdivm : d ∣ n - m := hd ▸ Nat.gcd_dvd_left _ _ have hdpos : 0 < d := Nat.pos_of_dvd_of_pos hdivk (by omega) have hdn : d ≤ n := by have h1 : d ≤ n - k := Nat.le_of_dvd (by omega) hdivk omega rcases Nat.lt_or_ge d 3 with hd3 | hd3 · have hd2' : d = 2 := by omega have hdivk2 : 2 ∣ n - k := hd2' ▸ hdivk have hdivm2 : 2 ∣ n - m := hd2' ▸ hdivm have hn4 : 4 ≤ n := by omega rcases Nat.mod_two_eq_zero_or_one n with hnpar | hnpar · have hk2 : k % 2 = 0 := by obtain ⟨c, hc⟩ := hdivk2; omega have hm2 : m % 2 = 0 := by obtain ⟨c, hc⟩ := hdivm2; omega set q : Fin n → ℕ := fun x => x.val / 2 with hq have hK : prefix_reversal_gcd_diff_necessary_fiber_rel q ≠ ⊤ := by refine prefix_reversal_gcd_diff_necessary_fiber_ne_top q (a := ⟨0, by omega⟩) (b := ⟨1, by omega⟩) (c := ⟨2, by omega⟩) ?_ ?_ ?_ ?_ · show (0:ℕ)/2 = 1/2; rfl · show (0:ℕ)/2 ≠ 2/2; norm_num · show (⟨1, by omega⟩ : Fin n) ≠ ⟨0, by omega⟩; intro h; simp at h · show (⟨2, by omega⟩ : Fin n) ≠ ⟨0, by omega⟩; intro h; simp at h have hsub : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} ≤ prefix_reversal_gcd_diff_necessary_fiber_rel q := by rw [Subgroup.closure_le] intro g hg simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hg rcases hg with rfl | rfl | rfl · exact prefix_reversal_gcd_diff_necessary_pair_preserved hk2 hkn · exact prefix_reversal_gcd_diff_necessary_pair_preserved hm2 hmn' · exact prefix_reversal_gcd_diff_necessary_pair_preserved (by omega) (le_refl n) rw [hgen] at hsub exact hK (le_antisymm le_top hsub) · have hk2 : k % 2 = 1 := by obtain ⟨c, hc⟩ := hdivk2; omega have hm2 : m % 2 = 1 := by obtain ⟨c, hc⟩ := hdivm2; omega set q : Fin n → ℕ := fun x => x.val % 2 with hq have hK : prefix_reversal_gcd_diff_necessary_fiber_rel q ≠ ⊤ := by refine prefix_reversal_gcd_diff_necessary_fiber_ne_top q (a := ⟨0, by omega⟩) (b := ⟨2, by omega⟩) (c := ⟨1, by omega⟩) ?_ ?_ ?_ ?_ · show (0:ℕ)%2 = 2%2; norm_num · show (0:ℕ)%2 ≠ 1%2; norm_num · show (⟨2, by omega⟩ : Fin n) ≠ ⟨0, by omega⟩; intro h; simp at h · show (⟨1, by omega⟩ : Fin n) ≠ ⟨0, by omega⟩; intro h; simp at h have hsub : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} ≤ prefix_reversal_gcd_diff_necessary_fiber_rel q := by rw [Subgroup.closure_le] intro g hg simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hg rcases hg with rfl | rfl | rfl · exact prefix_reversal_gcd_diff_necessary_parity_fiber hk2 hkn · exact prefix_reversal_gcd_diff_necessary_parity_fiber hm2 hmn' · exact prefix_reversal_gcd_diff_necessary_parity_fiber (by omega) (le_refl n) rw [hgen] at hsub exact hK (le_antisymm le_top hsub) · set S : Set (Fin n) := {x : Fin n | (x.val : ZMod d) = 0 ∨ (x.val : ZMod d) = ((n - 1 : ℕ) : ZMod d)} with hS have hK : prefix_reversal_gcd_diff_necessary_stabilizer_set S ≠ ⊤ := by obtain ⟨y, hy0, hyt⟩ := prefix_reversal_gcd_diff_necessary_exists_zmod_not_pair hd3 ((n - 1 : ℕ) : ZMod d) have hyv : y.val < n := by have h1 : y.val < d := prefix_reversal_gcd_diff_necessary_zmod_val_lt (by omega) y omega refine prefix_reversal_gcd_diff_necessary_stabilizer_set_ne_top S ⟨0, by omega⟩ ⟨y.val, hyv⟩ ?_ ?_ · show ((0:ℕ) : ZMod d) = 0 ∨ ((0:ℕ) : ZMod d) = ((n - 1 : ℕ) : ZMod d) exact Or.inl (Nat.cast_zero) · show ¬ (((y.val : ℕ) : ZMod d) = 0 ∨ ((y.val : ℕ) : ZMod d) = ((n - 1 : ℕ) : ZMod d)) rw [prefix_reversal_gcd_diff_necessary_cast_val (by omega) y] exact fun h => h.elim hy0 hyt have hsub : Subgroup.closure {prefixReversal n k, prefixReversal n m, prefixReversal n n} ≤ prefix_reversal_gcd_diff_necessary_stabilizer_set S := by rw [Subgroup.closure_le] intro g hg simp only [Set.mem_insert_iff, Set.mem_singleton_iff] at hg rcases hg with rfl | rfl | rfl · exact prefix_reversal_gcd_diff_necessary_set_preserved hk1 hkn hn1 hdivk · exact prefix_reversal_gcd_diff_necessary_set_preserved hm1 hmn' hn1 hdivm · refine prefix_reversal_gcd_diff_necessary_set_preserved hn1 (le_refl n) hn1 ?_ rw [Nat.sub_self] exact Nat.dvd_zero d rw [hgen] at hsub exact hK (le_antisymm le_top hsub)