good_slopes_gap_mod_105
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.
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).
uses
ZMod.castHom,gs105_crt3,gs105_crt35private 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]
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.
uses
congrArg,gs105_crt_self,gs105_split_crtprivate 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 _ _
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).
uses
gs105_unit3,Function.comp_def,map_add,map_mulprivate 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
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.
classical by_contra hnot have hlarge : 40 < (good_slopes 105 f).card := by omega
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.
uses
good_slopes_unit_cover_mod105obtain ⟨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)
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.
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
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|.
uses
Finset.card_image_of_injective,add_right_cancelhave 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)
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.
uses
Finset.card_image_of_injective,gs105_split_crtlet 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⟩
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.
uses
gs105_crt3,gs105_crt35,gs105_bij_pair_iff,Fintype.bijective_iff_injective_and_cardhave 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⟩
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.
uses
gs105_unit3,Finset.disjoint_left.mpr,card_union_of_disjoint,card_productlet 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
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.
uses
good_slopes_two_row_fiber_rigidityhave 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)
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.
uses
gs105_unit3,gs105_bij_pair_iff,Fintype.bijective_iff_injective_and_cardhave 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
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.
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.
- The proof includes several helper definitions and theorems established for Chinese Remainder Theorem arithmetic between ℤ/105ℤ and ℤ/3ℤ × ℤ/35ℤ (verified by finite exhaustive search), leading up to the main argument which relies on the two-row fiber rigidity theorem good_slopes_two_row_fiber_rigidity.
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.
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