AFTD Auto-Formalizing Theoretical Domains

prefix_reversal_gcd_diff_necessary

theoremverifiedformalization

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.

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

    lines 1–5

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

    lines 6–11

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

    lines 12–23

    uses ZMod.natCast_eq_natCast_iff, Nat.modEq_iff_dvd', Nat.cast_sub

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

    lines 24–40

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

    lines 41–61

    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_ge

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

    lines 62–84

    uses prefix_reversal_gcd_diff_necessary_apply_of_lt, prefix_reversal_gcd_diff_necessary_apply_of_ge

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

    lines 85–97

    uses prefix_reversal_gcd_diff_necessary_apply_of_lt, prefix_reversal_gcd_diff_necessary_apply_of_ge

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

    lines 98–110

    uses Equiv.Perm.mul_apply

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

    lines 111–123

    uses Equiv.Perm.mul_apply

    def 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
    
  10. 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.

    lines 124–133

    uses Subgroup.mem_top, Equiv.swap_apply_left

    lemma 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)
    
  11. 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.

    lines 134–145

    uses Subgroup.mem_top, Equiv.swap_apply_of_ne_of_ne, Ne.symm, Equiv.swap_apply_left

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

    lines 146–153

    uses congrArg, ZMod.val_zero, ZMod.val_cast_of_lt

    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
      omega
    
  13. 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.

    lines 154–161

    uses congrArg, ZMod.val_zero, ZMod.val_cast_of_lt

    lemma 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
    
  14. 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.

    lines 162–170

    uses congrArg, ZMod.val_cast_of_lt

    lemma 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
    
  15. 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.

    lines 171–186

    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_one

    lemma 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
    
  16. 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.

    lines 187–191

    uses ZMod.val_lt

    lemma 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
    
  17. 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.

    lines 192–197

    uses ZMod.natCast_zmod_val

    lemma 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. -/
  18. 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.

    lines 198–214

    uses Nat.gcd_dvd_right, Nat.gcd_dvd_left, Nat.pos_of_dvd_of_pos, Nat.le_of_dvd

    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
  19. 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 ⊤.

    lines 215–241

    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_top

      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)
  20. 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 ⊤.

    lines 242–262

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

    lines 263–277

    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
  22. 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 ⊤.

    lines 278–290

    uses Subgroup.closure_le, prefix_reversal_gcd_diff_necessary_set_preserved, le_refl, Nat.sub_self, Nat.dvd_zero, le_antisymm, le_top

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

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