AFTD Auto-Formalizing Theoretical Domains

good_slopes_gap_mod_105

theoremverifiedoriginal

Every non-extremal permutation f of ℤ/105ℤ satisfies |D_{105}(f)| ≤ 40: (good_slopes 105 f).card ≤ 40.

Statement

theorem good_slopes_gap_mod_105 (f : Equiv.Perm (ZMod 105)) (hf : ¬ is_extremal_perm 105 f) : (good_slopes 105 f).card ≤ 40
Related work
arXiv:2611.04551, Question 10.2 and Table 3; the modulus-105 case is left open there.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • good_slopesGiven a natural number n with n ≠ 0 (via [NeZero n]) and a permutation f of ℤ/nℤ, good_slopes n f is the finite set (Finset) of elements m…
  • is_extremal_permGiven n with [NeZero n], a permutation f of ℤ/nℤ is extremal if the number of its good slopes (the cardinality of good_slopes n f) equals…
  • good_slopes_mem_iffA slope m is good for the permutation f of ℤ/nℤ exactly when x ↦ f(x) + m·x is a bijection of ℤ/nℤ: m ∈ D_n(f) ↔ Function.Bijective (fun x…
  • zero_mem_good_slopesZero is always a good slope of every permutation of ℤ/nℤ, since x ↦ f(x) + 0·x = f(x) is a permutation; in particular D_n(f) is nonempty:…
  • good_slopes_unit_cover_mod105For every permutation modulo 105, a unit c exists such that adding c to each good slope yields a unit modulo 105.
  • good_slopes_two_row_fiber_rigidityLet X be a finite set of 105 elements with input and output coordinate functions over Z/3 and Z/35, and assume the pair of input…

Read back from the Lean

For every permutation $f$ of $\mathbb{Z}/105\mathbb{Z}$, if $f$ is not an extremal permutation mod 105 (that is, the cardinality of good_slopes 105 f is not equal to $\text{Nat.totient}(105)$), then the cardinality of good_slopes 105 f is at most 40.

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: suppose the permutation f of ℤ/105ℤ has strictly more than 40 good slopes. Shifting f by an appropriate unit c normalizes the good slopes into a subset A of units of ℤ/105ℤ of size greater than 40. Under the Chinese Remainder Theorem isomorphism ℤ/105ℤ ≅ ℤ/3ℤ × ℤ/35ℤ, elements of A correspond to pairs of units whose coordinate maps are injective. Because ℤ/3ℤ has only two units (1 and 2), the sum of the sizes of the two unit fibers exceeds 40, which by a two-row fiber rigidity theorem forces both fibers to be completely full. Consequently, A contains all 48 units of ℤ/105ℤ, meaning f has φ(105) = 48 good slopes, contradicting the assumption that f is non-extremal.

  1. Define the CRT projections and reconstruction between ℤ/105ℤ and ℤ/3ℤ × ℤ/35ℤ, and verify their round-trip identities.

    We define the canonical ring homomorphisms from ℤ/105ℤ to ℤ/3ℤ and ℤ/35ℤ via ZMod.castHom, and define the reconstruction gs105_crt(a, b) = 70a + 36b mod 105. By finite exhaustive check (decide), we verify that projection after reconstruction recovers the original coordinates (gs105_crt3, gs105_crt35), that reconstructing the projections recovers x (gs105_crt_self), and that splitting the reconstruction gives (a, b) (gs105_split_crt).

    lines 4–11

    uses ZMod.castHom, gs105_crt3, gs105_crt35

    private def gs105_c3 : ZMod 105 →+* ZMod 3 := ZMod.castHom (by decide : 3 ∣ 105) (ZMod 3)
    private def gs105_c35 : ZMod 105 →+* ZMod 35 := ZMod.castHom (by decide : 35 ∣ 105) (ZMod 35)
    private def gs105_crt (a : ZMod 3) (b : ZMod 35) : ZMod 105 := 70 * a.val + 36 * b.val
    private theorem gs105_crt3 : ∀ a : ZMod 3, ∀ b : ZMod 35, gs105_c3 (gs105_crt a b) = a := by decide +revert
    private theorem gs105_crt35 : ∀ a : ZMod 3, ∀ b : ZMod 35, gs105_c35 (gs105_crt a b) = b := by decide +revert
    private theorem gs105_crt_self : ∀ x : ZMod 105, gs105_crt (gs105_c3 x) (gs105_c35 x) = x := by decide +revert
    private def gs105_split (x : ZMod 105) : ZMod 3 × ZMod 35 := (gs105_c3 x,gs105_c35 x)
    private theorem gs105_split_crt (a : ZMod 3) (b : ZMod 35) : gs105_split (gs105_crt a b) = (a,b) := by simp [gs105_split, gs105_crt3, gs105_crt35]
  2. The CRT splitting map gs105_split : ℤ/105ℤ → ℤ/3ℤ × ℤ/35ℤ is a bijection.

    Injectivity holds by applying gs105_crt to equal image pairs and simplifying with gs105_crt_self using congrArg. Surjectivity holds because any pair p is the image of gs105_crt(p.1, p.2) via gs105_split_crt.

    lines 12–22

    uses congrArg, gs105_crt_self, gs105_split_crt

    private theorem gs105_split_bij : Function.Bijective gs105_split := by
      constructor
      · intro x y h
        have h1 := congrArg Prod.fst h
        have h2 := congrArg Prod.snd h
        have hc := congrArg (fun p : ZMod 3 × ZMod 35 => gs105_crt p.1 p.2) h
        simpa only [gs105_split, gs105_crt_self] using hc
      · intro p
        refine ⟨gs105_crt p.1 p.2, ?_⟩
        exact gs105_split_crt _ _
    
  3. The units of ℤ/3ℤ are {1, 2}, and bijectivity of x ↦ f(x) + mx on ℤ/105ℤ is equivalent to bijectivity of the coordinate map into ℤ/3ℤ × ℤ/35ℤ.

    We verify by finite decision that a ∈ ℤ/3ℤ is a unit iff a = 1 or a = 2 (gs105_unit3). By composing with the bijection gs105_split and rewriting with the homomorphism properties map_add and map_mul and Function.comp_def, bijectivity on ℤ/105ℤ is equivalent to bijectivity of the pair of coordinate maps (gs105_bij_pair_iff).

    lines 23–34

    uses gs105_unit3, Function.comp_def, map_add, map_mul

    private theorem gs105_unit3 : ∀ a : ZMod 3, IsUnit a ↔ a = 1 ∨ a = 2 := by decide +revert
    
    private theorem gs105_bij_pair_iff (f : ZMod 105 → ZMod 105) (m : ZMod 105) :
        Function.Bijective (fun x => f x + m*x) ↔
        Function.Bijective (fun x => (gs105_c3 (f x) + gs105_c3 m * gs105_c3 x, gs105_c35 (f x) + gs105_c35 m * gs105_c35 x)) := by
      have h := gs105_split_bij.of_comp_iff' (fun x => f x + m*x)
      simpa only [Function.comp_def, gs105_split, map_add, map_mul] using h.symm
    
    open Finset
    
    /-- For the smallest unsettled modulus n = 105, every non-extremal permutation has at most 40 good slopes. -/
    theorem good_slopes_gap_mod_105 (f : Equiv.Perm (ZMod 105)) (hf : ¬ is_extremal_perm 105 f) : (good_slopes 105 f).card ≤ 40 := by
  4. Assume for contradiction that the number of good slopes of f is strictly greater than 40.

    We argue by contradiction (by_contra). If |good_slopes 105 f| ≤ 40 is false, linear integer arithmetic (omega) yields |good_slopes 105 f| > 40.

    lines 35–37

      classical
      by_contra hnot
      have hlarge : 40 < (good_slopes 105 f).card := by omega
  5. Shift f by a unit c so that every good slope is mapped to a unit in the shifted set A.

    Using good_slopes_unit_cover_mod105, we choose a unit c such that m + c is a unit for all good slopes m. We define the normalized map normalized105(x) = f(x) - cx and define A as the image of the good slopes under translation by c.

    lines 38–40

    uses good_slopes_unit_cover_mod105

      obtain ⟨c, hc, hcover⟩ := good_slopes_unit_cover_mod105 f
      let normalized105 : ZMod 105 → ZMod 105 := fun x => f x - c*x
      let A : Finset (ZMod 105) := (good_slopes 105 f).image (fun m => m+c)
  6. An element u belongs to A if and only if x ↦ normalized105(x) + ux is bijective.

    Since normalized105(x) + (m + c)x = f(x) + mx by ring arithmetic, bijectivity of the shifted map with slope u = m + c is equivalent to bijectivity of the original map with slope m.

    lines 41–62

      have hA (u : ZMod 105) : u ∈ A ↔ Function.Bijective (fun x => normalized105 x + u*x) := by
        constructor
        · intro hu
          obtain ⟨m, hm, rfl⟩ := mem_image.mp hu
          have hm' := (mem_filter.mp hm).2
          have he : (fun x : ZMod 105 => normalized105 x + (m+c)*x) = (fun x => f x + m*x) := by
            funext x
            dsimp [normalized105]
            ring
          rw [he]
          exact hm'
        · intro hu
          apply mem_image.mpr
          refine ⟨u-c, ?_, by ring⟩
          apply mem_filter.mpr
          refine ⟨mem_univ _, ?_⟩
          have he : (fun x : ZMod 105 => f x + (u-c)*x) = (fun x => normalized105 x + u*x) := by
            funext x
            dsimp [normalized105]
            ring
          rw [he]
          exact hu
  7. Every element of A is a unit of ℤ/105ℤ, and |A| equals the number of good slopes of f.

    Every element in A is of the form m + c with m a good slope, hence a unit by the choice of c. Translation by c is injective by add_right_cancel, so Finset.card_image_of_injective gives |A| = |good_slopes 105 f|.

    lines 63–68

    uses Finset.card_image_of_injective, add_right_cancel

      have hAunit : ∀ u ∈ A, IsUnit u := by
        intro u hu
        obtain ⟨m, hm, rfl⟩ := mem_image.mp hu
        exact hcover m hm
      have hAcard : A.card = (good_slopes 105 f).card :=
        Finset.card_image_of_injective _ (fun _ _ h => add_right_cancel h)
  8. The set A embeds bijectively via CRT into a set pairs105 of pairs in ℤ/3ℤ × ℤ/35ℤ, with |pairs105| = |A|.

    We map A by the Chinese Remainder Theorem splitting gs105_split into ℤ/3ℤ × ℤ/35ℤ. Since this splitting is bijective, the image pairs105 has size |A| by Finset.card_image_of_injective, and (a, b) ∈ pairs105 if and only if gs105_crt a b ∈ A by gs105_split_crt.

    lines 69–78

    uses Finset.card_image_of_injective, gs105_split_crt

      let pairs105 : Finset (ZMod 3 × ZMod 35) := A.image gs105_split
      have hFcard : pairs105.card = A.card := Finset.card_image_of_injective _ gs105_split_bij.1
      have hFmem (a : ZMod 3) (b : ZMod 35) : (a,b) ∈ pairs105 ↔ gs105_crt a b ∈ A := by
        constructor
        · intro h
          obtain ⟨u, hu, he⟩ := mem_image.mp h
          have heq : u = gs105_crt a b := gs105_split_bij.1 (he.trans (gs105_split_crt a b).symm)
          simpa [heq] using hu
        · intro h
          exact mem_image.mpr ⟨gs105_crt a b, h, gs105_split_crt a b⟩
  9. A pair (a, b) lies in pairs105 if and only if a is a unit in ℤ/3ℤ, b is a unit in ℤ/35ℤ, and the product coordinate map is injective.

    An element u = gs105_crt a b is a unit if and only if both a and b are units, using gs105_crt3 and gs105_crt35. Bijectivity of x ↦ normalized105(x) + ux is equivalent by gs105_bij_pair_iff to bijectivity of the coordinate pair map, which on a finite set of equal domain and codomain is equivalent to injectivity by Fintype.bijective_iff_injective_and_card.

    lines 79–97

    uses gs105_crt3, gs105_crt35, gs105_bij_pair_iff, Fintype.bijective_iff_injective_and_card

      have hF (a : ZMod 3) (b : ZMod 35) : (a,b) ∈ pairs105 ↔
          IsUnit a ∧ IsUnit b ∧ Function.Injective (fun x : ZMod 105 =>
            (gs105_c3 (normalized105 x) + a*gs105_c3 x, gs105_c35 (normalized105 x) + b*gs105_c35 x)) := by
        constructor
        · intro h
          have hu : IsUnit (gs105_crt a b) := hAunit _ ((hFmem a b).1 h)
          have huv : IsUnit a ∧ IsUnit b := by
            constructor
            · simpa only [gs105_crt3] using gs105_c3.isUnit_map hu
            · simpa only [gs105_crt35] using gs105_c35.isUnit_map hu
          have hbij := (gs105_bij_pair_iff normalized105 (gs105_crt a b)).1 ((hA _).1 ((hFmem a b).1 h))
          rw [gs105_crt3, gs105_crt35] at hbij
          exact ⟨huv.1, huv.2, hbij.1⟩
        · rintro ⟨ha, hb, hi⟩
          apply (hFmem a b).2
          apply (hA _).2
          apply (gs105_bij_pair_iff normalized105 (gs105_crt a b)).2
          rw [gs105_crt3, gs105_crt35]
          exact (Fintype.bijective_iff_injective_and_card _).2 ⟨hi, by simp⟩
  10. The set pairs105 partitions into two disjoint rows {1} × R(1) and {2} × R(2), whose cardinalities satisfy |R(1)| + |R(2)| > 40.

    In ℤ/3ℤ, the only units are 1 and 2 by gs105_unit3, so pairs105 is the disjoint union of {1} × R(1) and {2} × R(2). By card_union_of_disjoint and card_product, |pairs105| = |R(1)| + |R(2)|. Since |pairs105| = |A| = |good_slopes 105 f| > 40, we have |R(1)| + |R(2)| > 40.

    lines 98–129

    uses gs105_unit3, Finset.disjoint_left.mpr, card_union_of_disjoint, card_product

      let R : ZMod 3 → Finset (ZMod 35) := fun a => univ.filter fun b =>
          IsUnit b ∧ Function.Injective (fun x : ZMod 105 => (gs105_c3 (normalized105 x) + a*gs105_c3 x, gs105_c35 (normalized105 x) + b*gs105_c35 x))
      have hdecomp : pairs105 = (({1} : Finset (ZMod 3)) ×ˢ R 1) ∪ (({2} : Finset (ZMod 3)) ×ˢ R 2) := by
        ext ⟨a,b⟩
        rw [hF a b]
        simp only [mem_union, mem_product, mem_singleton, R, mem_filter, mem_univ, true_and]
        constructor
        · rintro ⟨ha, hb, hi⟩
          rcases (gs105_unit3 a).1 ha with ha | ha
          · left
            subst a
            exact ⟨rfl, hb, hi⟩
          · right
            subst a
            exact ⟨rfl, hb, hi⟩
        · rintro (⟨ha, hb, hi⟩ | ⟨ha, hb, hi⟩)
          · subst a
            exact ⟨(gs105_unit3 1).2 (Or.inl rfl), hb, hi⟩
          · subst a
            exact ⟨(gs105_unit3 2).2 (Or.inr rfl), hb, hi⟩
      have hdisj : Disjoint (({1} : Finset (ZMod 3)) ×ˢ R 1) (({2} : Finset (ZMod 3)) ×ˢ R 2) := by
        apply Finset.disjoint_left.mpr
        intro ⟨a,b⟩ h1 h2
        simp only [mem_product, mem_singleton] at h1 h2
        have h12 : (1 : ZMod 3) ≠ 2 := by decide
        exact h12 (h1.1.symm.trans h2.1)
      have hcount : pairs105.card = (R 1).card + (R 2).card := by
        rw [hdecomp, card_union_of_disjoint hdisj, card_product, card_product]
        simp
      have hrows : 40 < (R 1).card + (R 2).card := by
        rw [← hcount, hFcard, hAcard]
        exact hlarge
  11. By two-row fiber rigidity, both rows R(1) and R(2) are completely full of all units in ℤ/35ℤ.

    Applying good_slopes_two_row_fiber_rigidity to rows 1 and 2 with total unit count > 40, we conclude that every unit b ∈ (ℤ/35ℤ)ˣ yields an injective coordinate map for both a = 1 and a = 2.

    lines 130–131

    uses good_slopes_two_row_fiber_rigidity

      have hstrong := good_slopes_two_row_fiber_rigidity gs105_c3 (fun x => gs105_c3 (normalized105 x)) gs105_c35 (fun x => gs105_c35 (normalized105 x)) 1 2
          (by simp) (by change Function.Injective gs105_split; exact gs105_split_bij.1) (by simpa [R] using hrows)
  12. Every unit of ℤ/105ℤ belongs to A.

    For any unit u ∈ (ℤ/105ℤ)ˣ, its mod 3 reduction is 1 or 2 by gs105_unit3, and its mod 35 reduction is a unit. By the rigidity conclusion, the corresponding coordinate map is injective, hence bijective (Fintype.bijective_iff_injective_and_card), so u ∈ A by gs105_bij_pair_iff.

    lines 132–144

    uses gs105_unit3, gs105_bij_pair_iff, Fintype.bijective_iff_injective_and_card

      have hAll : ∀ u : ZMod 105, IsUnit u → u ∈ A := by
        intro u hu
        have hu' : IsUnit (gs105_c3 u) ∧ IsUnit (gs105_c35 u) := ⟨gs105_c3.isUnit_map hu, gs105_c35.isUnit_map hu⟩
        have ha := (gs105_unit3 _).1 hu'.1
        apply (hA u).2
        apply (gs105_bij_pair_iff normalized105 u).2
        apply (Fintype.bijective_iff_injective_and_card _).2
        refine ⟨?_, by simp⟩
        rcases ha with ha | ha
        · rw [ha]
          exact hstrong.1 _ hu'.2
        · rw [ha]
          exact hstrong.2 _ hu'.2
  13. The set A equals the entire unit group (ℤ/105ℤ)ˣ of size 48, contradicting the non-extremality of f. automation

    Since A contains all units and consists only of units, A equals the group of units U of ℤ/105ℤ, which has size φ(105) = 48. Then |good_slopes 105 f| = |A| = 48 = φ(105), which means f is an extremal permutation (is_extremal_perm), contradicting the hypothesis ¬ is_extremal_perm 105 f. Linear arithmetic (omega) closes the contradiction.

    lines 145–155

      let U : Finset (ZMod 105) := univ.filter fun u => IsUnit u
      have hAU : A = U := by
        ext u
        simp only [U, mem_filter, mem_univ, true_and]
        exact ⟨hAunit u, hAll u⟩
      have hUcard : U.card = 48 := by decide
      apply hf
      unfold is_extremal_perm
      have ht : Nat.totient 105 = 48 := by decide
      rw [hAU, hUcard] at hAcard
      omega
ZMod.castHom
The canonical ring homomorphism ZMod n →+* R when m ∣ n and R has characteristic m.
gs105_crt3
The projection to ℤ/3ℤ of the CRT reconstruction of (a, b) equals a.
gs105_crt35
The projection to ℤ/35ℤ of the CRT reconstruction of (a, b) equals b.
congrArg
If two inputs are equal, applying any function to both produces equal values.
gs105_crt_self
Reconstructing from the CRT projections of an element x ∈ ℤ/105ℤ recovers x.
gs105_split_crt
The CRT splitting of the CRT reconstruction of (a, b) recovers the original pair (a, b).
gs105_unit3
An element of ℤ/3ℤ is a unit if and only if it equals 1 or 2.
Function.comp_def
The definition of function composition: (f ∘ g)(x) = f(g(x)).
map_add
A homomorphism preserves addition: f(x + y) = f(x) + f(y).
map_mul
A homomorphism preserves multiplication: f(x * y) = f(x) * f(y).
good_slopes_unit_cover_mod105
For every permutation f of ℤ/105ℤ, there exists a unit c such that m + c is a unit for every good slope m of f.
Finset.card_image_of_injective
The image of a finite set under an injective map has the same cardinality as the original set.
add_right_cancel
In an additive structure with right cancellation, a + b = c + b implies a = c.
gs105_bij_pair_iff
The map x ↦ f(x) + mx on ℤ/105ℤ is bijective if and only if the induced coordinate map into ℤ/3ℤ × ℤ/35ℤ is bijective.
Fintype.bijective_iff_injective_and_card
A map between finite types of the same cardinality is bijective if and only if it is injective.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first belongs to the second.
card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
card_product
The cardinality of the Cartesian product of two finite sets is the product of their cardinalities.
good_slopes_two_row_fiber_rigidity
For coordinate maps into ℤ/3ℤ × ℤ/35ℤ on a space of size 105, if the total number of unit slopes yielding injective maps in rows a and a' exceeds 40, then every unit slope in both rows yields an injective map.

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

set_option maxHeartbeats 4000000set_option maxRecDepth 10000private def gs105_c3 : ZMod 105 →+* ZMod 3 := ZMod.castHom (by decide : 3 ∣ 105) (ZMod 3)private def gs105_c35 : ZMod 105 →+* ZMod 35 := ZMod.castHom (by decide : 35 ∣ 105) (ZMod 35)private def gs105_crt (a : ZMod 3) (b : ZMod 35) : ZMod 105 := 70 * a.val + 36 * b.valprivate theorem gs105_crt3 : ∀ a : ZMod 3, ∀ b : ZMod 35, gs105_c3 (gs105_crt a b) = a := by decide +revertprivate theorem gs105_crt35 : ∀ a : ZMod 3, ∀ b : ZMod 35, gs105_c35 (gs105_crt a b) = b := by decide +revertprivate theorem gs105_crt_self : ∀ x : ZMod 105, gs105_crt (gs105_c3 x) (gs105_c35 x) = x := by decide +revertprivate def gs105_split (x : ZMod 105) : ZMod 3 × ZMod 35 := (gs105_c3 x,gs105_c35 x)private theorem gs105_split_crt (a : ZMod 3) (b : ZMod 35) : gs105_split (gs105_crt a b) = (a,b) := by simp [gs105_split, gs105_crt3, gs105_crt35]private theorem gs105_split_bij : Function.Bijective gs105_split := by  constructor  · intro x y h    have h1 := congrArg Prod.fst h    have h2 := congrArg Prod.snd h    have hc := congrArg (fun p : ZMod 3 × ZMod 35 => gs105_crt p.1 p.2) h    simpa only [gs105_split, gs105_crt_self] using hc  · intro p    refine ⟨gs105_crt p.1 p.2, ?_⟩    exact gs105_split_crt _ _private theorem gs105_unit3 : ∀ a : ZMod 3, IsUnit a ↔ a = 1 ∨ a = 2 := by decide +revertprivate theorem gs105_bij_pair_iff (f : ZMod 105 → ZMod 105) (m : ZMod 105) :    Function.Bijective (fun x => f x + m*x) ↔    Function.Bijective (fun x => (gs105_c3 (f x) + gs105_c3 m * gs105_c3 x, gs105_c35 (f x) + gs105_c35 m * gs105_c35 x)) := by  have h := gs105_split_bij.of_comp_iff' (fun x => f x + m*x)  simpa only [Function.comp_def, gs105_split, map_add, map_mul] using h.symmopen Finset/-- For the smallest unsettled modulus n = 105, every non-extremal permutation has at most 40 good slopes. -/theorem good_slopes_gap_mod_105 (f : Equiv.Perm (ZMod 105)) (hf : ¬ is_extremal_perm 105 f) : (good_slopes 105 f).card ≤ 40 := by  classical  by_contra hnot  have hlarge : 40 < (good_slopes 105 f).card := by omega  obtain ⟨c, hc, hcover⟩ := good_slopes_unit_cover_mod105 f  let normalized105 : ZMod 105 → ZMod 105 := fun x => f x - c*x  let A : Finset (ZMod 105) := (good_slopes 105 f).image (fun m => m+c)  have hA (u : ZMod 105) : u ∈ A ↔ Function.Bijective (fun x => normalized105 x + u*x) := by    constructor    · intro hu      obtain ⟨m, hm, rfl⟩ := mem_image.mp hu      have hm' := (mem_filter.mp hm).2      have he : (fun x : ZMod 105 => normalized105 x + (m+c)*x) = (fun x => f x + m*x) := by        funext x        dsimp [normalized105]        ring      rw [he]      exact hm'    · intro hu      apply mem_image.mpr      refine ⟨u-c, ?_, by ring⟩      apply mem_filter.mpr      refine ⟨mem_univ _, ?_⟩      have he : (fun x : ZMod 105 => f x + (u-c)*x) = (fun x => normalized105 x + u*x) := by        funext x        dsimp [normalized105]        ring      rw [he]      exact hu  have hAunit : ∀ u ∈ A, IsUnit u := by    intro u hu    obtain ⟨m, hm, rfl⟩ := mem_image.mp hu    exact hcover m hm  have hAcard : A.card = (good_slopes 105 f).card :=    Finset.card_image_of_injective _ (fun _ _ h => add_right_cancel h)  let pairs105 : Finset (ZMod 3 × ZMod 35) := A.image gs105_split  have hFcard : pairs105.card = A.card := Finset.card_image_of_injective _ gs105_split_bij.1  have hFmem (a : ZMod 3) (b : ZMod 35) : (a,b) ∈ pairs105 ↔ gs105_crt a b ∈ A := by    constructor    · intro h      obtain ⟨u, hu, he⟩ := mem_image.mp h      have heq : u = gs105_crt a b := gs105_split_bij.1 (he.trans (gs105_split_crt a b).symm)      simpa [heq] using hu    · intro h      exact mem_image.mpr ⟨gs105_crt a b, h, gs105_split_crt a b⟩  have hF (a : ZMod 3) (b : ZMod 35) : (a,b) ∈ pairs105 ↔      IsUnit a ∧ IsUnit b ∧ Function.Injective (fun x : ZMod 105 =>        (gs105_c3 (normalized105 x) + a*gs105_c3 x, gs105_c35 (normalized105 x) + b*gs105_c35 x)) := by    constructor    · intro h      have hu : IsUnit (gs105_crt a b) := hAunit _ ((hFmem a b).1 h)      have huv : IsUnit a ∧ IsUnit b := by        constructor        · simpa only [gs105_crt3] using gs105_c3.isUnit_map hu        · simpa only [gs105_crt35] using gs105_c35.isUnit_map hu      have hbij := (gs105_bij_pair_iff normalized105 (gs105_crt a b)).1 ((hA _).1 ((hFmem a b).1 h))      rw [gs105_crt3, gs105_crt35] at hbij      exact ⟨huv.1, huv.2, hbij.1⟩    · rintro ⟨ha, hb, hi⟩      apply (hFmem a b).2      apply (hA _).2      apply (gs105_bij_pair_iff normalized105 (gs105_crt a b)).2      rw [gs105_crt3, gs105_crt35]      exact (Fintype.bijective_iff_injective_and_card _).2 ⟨hi, by simp⟩  let R : ZMod 3 → Finset (ZMod 35) := fun a => univ.filter fun b =>      IsUnit b ∧ Function.Injective (fun x : ZMod 105 => (gs105_c3 (normalized105 x) + a*gs105_c3 x, gs105_c35 (normalized105 x) + b*gs105_c35 x))  have hdecomp : pairs105 = (({1} : Finset (ZMod 3)) ×ˢ R 1) ∪ (({2} : Finset (ZMod 3)) ×ˢ R 2) := by    ext ⟨a,b⟩    rw [hF a b]    simp only [mem_union, mem_product, mem_singleton, R, mem_filter, mem_univ, true_and]    constructor    · rintro ⟨ha, hb, hi⟩      rcases (gs105_unit3 a).1 ha with ha | ha      · left        subst a        exact ⟨rfl, hb, hi⟩      · right        subst a        exact ⟨rfl, hb, hi⟩    · rintro (⟨ha, hb, hi⟩ | ⟨ha, hb, hi⟩)      · subst a        exact ⟨(gs105_unit3 1).2 (Or.inl rfl), hb, hi⟩      · subst a        exact ⟨(gs105_unit3 2).2 (Or.inr rfl), hb, hi⟩  have hdisj : Disjoint (({1} : Finset (ZMod 3)) ×ˢ R 1) (({2} : Finset (ZMod 3)) ×ˢ R 2) := by    apply Finset.disjoint_left.mpr    intro ⟨a,b⟩ h1 h2    simp only [mem_product, mem_singleton] at h1 h2    have h12 : (1 : ZMod 3) ≠ 2 := by decide    exact h12 (h1.1.symm.trans h2.1)  have hcount : pairs105.card = (R 1).card + (R 2).card := by    rw [hdecomp, card_union_of_disjoint hdisj, card_product, card_product]    simp  have hrows : 40 < (R 1).card + (R 2).card := by    rw [← hcount, hFcard, hAcard]    exact hlarge  have hstrong := good_slopes_two_row_fiber_rigidity gs105_c3 (fun x => gs105_c3 (normalized105 x)) gs105_c35 (fun x => gs105_c35 (normalized105 x)) 1 2      (by simp) (by change Function.Injective gs105_split; exact gs105_split_bij.1) (by simpa [R] using hrows)  have hAll : ∀ u : ZMod 105, IsUnit u → u ∈ A := by    intro u hu    have hu' : IsUnit (gs105_c3 u) ∧ IsUnit (gs105_c35 u) := ⟨gs105_c3.isUnit_map hu, gs105_c35.isUnit_map hu⟩    have ha := (gs105_unit3 _).1 hu'.1    apply (hA u).2    apply (gs105_bij_pair_iff normalized105 u).2    apply (Fintype.bijective_iff_injective_and_card _).2    refine ⟨?_, by simp⟩    rcases ha with ha | ha    · rw [ha]      exact hstrong.1 _ hu'.2    · rw [ha]      exact hstrong.2 _ hu'.2  let U : Finset (ZMod 105) := univ.filter fun u => IsUnit u  have hAU : A = U := by    ext u    simp only [U, mem_filter, mem_univ, true_and]    exact ⟨hAunit u, hAll u⟩  have hUcard : U.card = 48 := by decide  apply hf  unfold is_extremal_perm  have ht : Nat.totient 105 = 48 := by decide  rw [hAU, hUcard] at hAcard  omega
See it in the graphDiscuss this resultChallenge it