good_slopes_missing_prime_squarefree
Let n be squarefree and nonzero, let the prime p divide n, and let f be a permutation modulo n. Then some residue modulo p is missed by every good slope of f.
Statement
theorem good_slopes_missing_prime_squarefree (n p : ℕ) [NeZero n] [NeZero p] (hn : Squarefree n) (hp : Nat.Prime p) (hd : p ∣ n) (f : Equiv.Perm (ZMod n)) : ∃ a : ZMod p, ∀ m ∈ good_slopes n f, ZMod.castHom hd (ZMod p) m ≠ a- Source
- Squarefree case of the prime-residue assertion in arXiv:2611.01465, Theorem 3.1, generalizing good_slopes_missing_prime105.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- 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…
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod. - g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 1
- good_slopes_unit_cover_squarefreeFor every nonzero squarefree modulus and permutation, some unit can be added to all its good slopes to make them units.
The proof, explained
We argue by contradiction: suppose every residue a modulo p is the reduction of some good slope m(a), so that x ↦ f(x) + m(a) * x is a permutation of ZMod n. We evaluate the double sum S = ∑_{a ∈ ZMod p} ∑_{x ∈ ZMod n} (c(f(x)) + a * c(x))^(p-1) in ZMod p in two ways. Summing over x first, the permutation property makes the inner sum a constant independent of a, so the outer sum over the p elements of ZMod p vanishes, giving S = 0. Exchanging the order of summation, the sum over a is an affine power sum that evaluates to -1 if c(x) ≠ 0 and 0 if c(x) = 0, which sums over ZMod n to (n/p) * 1 = n/p in ZMod p. Equating the two evaluations forces n/p = 0 in ZMod p, which implies p^2 divides n and contradicts the squarefreeness of n.
If n is squarefree, p is prime, and p divides n, then n/p is non-zero modulo p.
Suppose, for contradiction, that n/p = 0 in ZMod p, which means p divides n/p by ZMod.natCast_eq_zero_iff. Since p divides n, write n = p * k. Then (p * k) / p = k by Nat.mul_div_cancel_left and Nat.Prime.pos, so k is a multiple of p, say k = p * m. Substituting this back gives n = p * (p * m) = p^2 * m, so p^2 divides n. Because n is squarefree, this implies p is a unit, contradicting that p is prime.
uses
ZMod.natCast_eq_zero_iff,Nat.mul_div_cancel_left,Nat.Prime.posintro h0 have h_dvd : p ∣ (n / p) := (ZMod.natCast_eq_zero_iff (n / p) p).mp h0 have hp2 : p * p ∣ n := by rcases hd with ⟨k, rfl⟩ rcases h_dvd with ⟨m, hm⟩ have : (p * k) / p = k := Nat.mul_div_cancel_left k (Nat.Prime.pos hp) rw [this] at hm subst hm exact ⟨m, by ring⟩ exact hp.not_isUnit (hn p hp2)
For any prime p, the sum of (p-1)-th powers over all elements of ZMod p is -1.
Since p ≥ 2, the exponent p - 1 is positive (Nat.sub_pos_of_lt), so 0^(p-1) = 0 by zero_pow and ne_of_gt. The group of units (ZMod p)ˣ embeds injectively into ZMod p via Units.val_injective with image equal to the non-zero elements ZMod p \ {0}, because units are non-zero (Units.ne_zero) and every non-zero element lifts to a unit (Units.mk0). By sum_sdiff, sum_singleton, and add_zero, the sum over all elements equals the sum of (p-1)-th powers over the units. By FiniteField.sum_pow_units, the sum of powers over units in a finite field equals -1 when the order minus one divides the power. Here |ZMod p| = p by ZMod.card, so p - 1 divides p - 1, and the sum evaluates to -1.
uses
ZMod.card,Nat.sub_pos_of_lt,zero_pow,ne_of_gt,Units.val_injective,Units.ne_zero,Units.mk0,sum_sdiff,sum_singleton,add_zero,FiniteField.sum_pow_unitshave hcard : Fintype.card (ZMod p) = p := ZMod.card p have hp_pos : 0 < p - 1 := Nat.sub_pos_of_lt hp.1.two_le have h0 : (0 : ZMod p) ^ (p - 1) = 0 := zero_pow (ne_of_gt hp_pos) let φ : (ZMod p)ˣ ↪ ZMod p := ⟨fun x ↦ x, Units.val_injective⟩ have hmap : univ.map φ = univ \ {0} := by ext x simp only [mem_map, mem_univ, Function.Embedding.coeFn_mk, true_and, mem_sdiff, mem_singleton, φ] constructor · rintro ⟨u, rfl⟩; exact Units.ne_zero u · intro hx; exact ⟨Units.mk0 x hx, rfl⟩ calc ∑ x : ZMod p, x ^ (p - 1) = ∑ x ∈ univ \ {(0 : ZMod p)}, x ^ (p - 1) := by rw [← sum_sdiff ({0} : Finset (ZMod p)).subset_univ, sum_singleton, h0, add_zero] _ = ∑ x : (ZMod p)ˣ, (x ^ (p - 1) : ZMod p) := by simp [φ, ← hmap, univ.sum_map φ] _ = if Fintype.card (ZMod p) - 1 ∣ p - 1 then -1 else 0 := FiniteField.sum_pow_units (ZMod p) (p - 1) _ = -1 := by rw [hcard] simp
For x, y in ZMod p, the affine power sum ∑_{a} (y + a * x)^(p-1) is 0 if x = 0 and -1 if x ≠ 0.
We split into cases on whether x = 0. If x = 0, every term is y^(p-1), and summing this constant over the p elements of ZMod p yields p * y^(p-1) = 0. If x ≠ 0, the affine map a ↦ y + a * x is bijective on ZMod p: it is injective by additive cancellation (add_left_cancel) and multiplicative cancellation by non-zero x (mul_right_cancel₀), and surjective because the preimage of z is (z - y) / x via div_mul_cancel₀ and add_sub_cancel. Re-indexing the sum by this bijection turns it into ∑_{u : ZMod p} u^(p-1), which equals -1 by good_slopes_missing_prime_squarefree_zmod_prime_sum_pow_pred.
uses
add_left_cancel,mul_right_cancel₀,div_mul_cancel₀,add_sub_cancel,good_slopes_missing_prime_squarefree_zmod_prime_sum_pow_predsplit_ifs with hx · subst hx simp · have hbij : Function.Bijective (fun a : ZMod p => y + a * x) := by refine ⟨?_, ?_⟩ · intro a b hab have : a * x = b * x := add_left_cancel hab exact mul_right_cancel₀ hx this · intro z refine ⟨(z - y) / x, ?_⟩ dsimp rw [div_mul_cancel₀ (z - y) hx, add_sub_cancel] rw [hbij.sum_comp (fun u => u ^ (p - 1))] exact good_slopes_missing_prime_squarefree_zmod_prime_sum_pow_pred p
The sum of F(c(x)) over x in ZMod n factors as the fiber cardinality |c⁻¹(0)| times the sum of F(y) over y in ZMod p, where F(y) = (if y = 0 then 0 else -1).
Using sum_fiberwise_of_maps_to, we decompose the sum over ZMod n into fibers of the canonical ring homomorphism c : ZMod n →+* ZMod p. Since c is surjective by ZMod.castHom_surjective, all fibers have equal size |c⁻¹(0)| by AddMonoidHom.card_fiber_eq_of_mem_range. On each fiber {x | c(x) = y}, the summand F(c(x)) is constantly F(y) by sum_congr, so the fiber sum is |{x | c(x) = y}| * F(y) using sum_const and nsmul_eq_mul. Replacing each fiber size with |c⁻¹(0)| yields the factorization.
uses
sum_fiberwise_of_maps_to,ZMod.castHom_surjective,AddMonoidHom.card_fiber_eq_of_mem_range,sum_congr,sum_const,nsmul_eq_mullet c := ZMod.castHom hd (ZMod p) let F : ZMod p → ZMod p := fun y => if y = 0 then 0 else -1 have hfib := (sum_fiberwise_of_maps_to (g := c) (s := univ) (t := univ) (fun _ _ => mem_univ _) (fun x => F (c x))).symm change (∑ x : ZMod n, F (c x)) = ((n / p : ℕ) : ZMod p) rw [hfib] have hsurj := ZMod.castHom_surjective hd have hfiber_eq : ∀ y : ZMod p, #{x : ZMod n | c x = y} = #{x : ZMod n | c x = 0} := by intro y exact AddMonoidHom.card_fiber_eq_of_mem_range c.toAddMonoidHom (hsurj y) (hsurj 0) have hstep1 : (∑ j : ZMod p, ∑ i ∈ univ with c i = j, F (c i)) = ∑ j : ZMod p, (#{i : ZMod n | c i = j} : ZMod p) * F j := by apply sum_congr rfl intro y _ have : (∑ x ∈ univ.filter (fun x => c x = y), F (c x)) = ∑ x ∈ univ.filter (fun x => c x = y), F y := by apply sum_congr rfl intro x hx simp only [mem_filter, mem_univ, true_and] at hx rw [hx] rw [this, sum_const, nsmul_eq_mul] rw [hstep1] simp_rw [hfiber_eq]
Each fiber of the homomorphism c : ZMod n →+* ZMod p has cardinality n / p.
The sum of the fiber sizes over all y in ZMod p equals the total cardinality of ZMod n, which is n, by card_eq_sum_card_fiberwise, card_univ, and ZMod.card. Since all p fibers have the same size, this sum simplifies to p * |c⁻¹(0)| = n using sum_const and nsmul_eq_mul. Dividing by p via Nat.eq_div_of_mul_eq_right, which applies because p is a prime and thus non-zero (Nat.Prime.ne_zero), gives |c⁻¹(0)| = n / p.
uses
card_eq_sum_card_fiberwise,card_univ,ZMod.card,sum_const,nsmul_eq_mul,Nat.eq_div_of_mul_eq_right,Nat.Prime.ne_zerohave hsum_card : ∑ y : ZMod p, #{x : ZMod n | c x = y} = n := by have h := (card_eq_sum_card_fiberwise (f := c) (s := (univ : Finset (ZMod n))) (t := (univ : Finset (ZMod p))) (fun _ _ => mem_univ _)).symm rw [card_univ, ZMod.card] at h exact h simp_rw [hfiber_eq] at hsum_card rw [sum_const, card_univ, ZMod.card, nsmul_eq_mul] at hsum_card have hcard_val : #{x : ZMod n | c x = 0} = n / p := Nat.eq_div_of_mul_eq_right (Nat.Prime.ne_zero hp.1) hsum_card
The sum of F(y) over all y in ZMod p is 1, and therefore the lifted sum over ZMod n equals n / p in ZMod p.
We factor |c⁻¹(0)| out of the sum using mul_sum. Splitting ZMod p into {0} and its complement ZMod p \ {0} via subset_univ, sum_sdiff, and add_comm, the term at 0 contributes F(0) = 0 (zero_add), while on the non-zero elements F(y) is constantly -1 by sum_congr. The complement has size p - 1 by card_sdiff_of_subset, card_singleton, card_univ, and ZMod.card, so the sum over ZMod p is (p - 1) * (-1) via sum_const and nsmul_eq_mul. Modulo p, p - 1 = -1 by Nat.cast_sub, so this product is (-1) * (-1) = 1. Multiplying by the fiber size n / p (mul_one) concludes that the total sum equals n / p in ZMod p.
uses
mul_sum,subset_univ,sum_sdiff,add_comm,zero_add,sum_congr,sum_const,card_sdiff_of_subset,card_singleton,card_univ,ZMod.card,nsmul_eq_mul,Nat.cast_sub,mul_onerw [← mul_sum] have hs : ({0} : Finset (ZMod p)) ⊆ univ := subset_univ _ have hsplit : (∑ y : ZMod p, F y) = (∑ y ∈ ({0} : Finset (ZMod p)), F y) + (∑ y ∈ univ \ ({0} : Finset (ZMod p)), F y) := by rw [← sum_sdiff hs, add_comm] have hzero : (∑ y ∈ ({0} : Finset (ZMod p)), F y) = 0 := by simp [F] have hrest : (∑ y ∈ univ \ ({0} : Finset (ZMod p)), F y) = ∑ y ∈ univ \ ({0} : Finset (ZMod p)), (-1 : ZMod p) := by apply sum_congr rfl intro y hy simp only [mem_sdiff, mem_singleton] at hy simp [F, hy.2] have hsumF : (∑ y : ZMod p, F y) = 1 := by rw [hsplit, hzero, zero_add, hrest, sum_const, card_sdiff_of_subset hs, card_singleton, card_univ, ZMod.card, nsmul_eq_mul] have hsub : ((p - 1 : ℕ) : ZMod p) = -1 := by have h1 : (1 : ℕ) ≤ p := hp.1.pos have h2 := Nat.cast_sub (R := ZMod p) h1 rw [h2] simp rw [hsub] ring rw [hsumF, mul_one, hcard_val]
Assuming for contradiction that every residue in ZMod p is hit by the reduction of some good slope, there exists a good slope m(a) reducing to a for each a in ZMod p.
We assume the negation of the theorem for contradiction (by_contra). Pushing the negation inside the quantifiers (push Not) gives that for every residue a in ZMod p, there is some slope m in good_slopes n f such that c(m) = a. We choose such a slope m(a) for each a using the choose tactic.
have : Fact (Nat.Prime p) := ⟨hp⟩ let c : ZMod n →+* ZMod p := ZMod.castHom hd (ZMod p) by_contra h_all push Not at h_all choose m hm hma using h_all
Summing over x first, the double sum ∑_{a} ∑_{x} (c(f(x)) + a * c(x))^(p-1) in ZMod p is 0.
Define total = ∑_{x : ZMod n} (c(x))^(p-1). For each a in ZMod p, since m(a) is a good slope, the map x ↦ f(x) + m(a) * x is a permutation of ZMod n by good_slopes_mem_iff. Because c is a ring homomorphism (map_add, map_mul) and c(m(a)) = a, we have c(f(x) + m(a) * x) = c(f(x)) + a * c(x). Re-indexing the sum by this bijection shows that the inner sum over x equals total for every a. Summing this constant value over all p elements a in ZMod p yields p * total = 0 in ZMod p.
uses
good_slopes_mem_iff,sum_congr,map_add,map_mullet total : ZMod p := ∑ x : ZMod n, (c x) ^ (p - 1) have hsum (a : ZMod p) : (∑ x : ZMod n, (c (f x) + a * c x) ^ (p - 1)) = total := by have hbij : Function.Bijective (fun x : ZMod n => f x + m a * x) := (good_slopes_mem_iff n f (m a)).mp (hm a) calc _ = ∑ x : ZMod n, (c (f x + m a * x)) ^ (p - 1) := by apply sum_congr rfl intro x _ rw [map_add, map_mul, hma a] _ = total := hbij.sum_comp (fun x => (c x) ^ (p - 1)) have houter : (∑ a : ZMod p, ∑ x : ZMod n, (c (f x) + a * c x) ^ (p - 1)) = 0 := by simp_rw [hsum] simp [total]
Exchanging the summation order expresses the double sum as ∑_{x : ZMod n} (if c(x) = 0 then 0 else -1).
We interchange the order of summation using sum_comm. For each fixed x in ZMod n, the inner sum over a in ZMod p is an affine power sum along a line with slope c(x) and intercept c(f(x)). By good_slopes_missing_prime_squarefree_zmod_prime_sum_affine_pow, this inner sum equals 0 if c(x) = 0 and -1 if c(x) ≠ 0. Applying this simplification inside sum_congr gives the claimed sum over x.
uses
sum_comm,sum_congr,good_slopes_missing_prime_squarefree_zmod_prime_sum_affine_powhave hinner : (∑ a : ZMod p, ∑ x : ZMod n, (c (f x) + a * c x) ^ (p - 1)) = ∑ x : ZMod n, if c x = 0 then 0 else (-1 : ZMod p) := by rw [sum_comm] apply sum_congr rfl intro x _ exact good_slopes_missing_prime_squarefree_zmod_prime_sum_affine_pow p (c x) (c (f x))
Equating the two evaluations shows n / p = 0 in ZMod p, which contradicts the squarefreeness of n.
Equating the two expressions for the double sum shows that ∑_{x : ZMod n} (if c(x) = 0 then 0 else -1) = 0. By good_slopes_missing_prime_squarefree_sum_indicator_lift, this sum equals n / p in ZMod p, which would force n / p = 0 in ZMod p. However, good_slopes_missing_prime_squarefree_div_ne_zero proves that n / p ≠ 0 in ZMod p because n is squarefree, p is prime, and p divides n. This contradiction proves that some residue modulo p must be missed by all good slopes.
uses
good_slopes_missing_prime_squarefree_sum_indicator_lift,good_slopes_missing_prime_squarefree_div_ne_zerohave heq : (∑ x : ZMod n, if c x = 0 then 0 else (-1 : ZMod p)) = 0 := hinner.symm.trans houter rw [good_slopes_missing_prime_squarefree_sum_indicator_lift n p hd ‹_›] at heq exact good_slopes_missing_prime_squarefree_div_ne_zero n p hn hp hd heq
ZMod.natCast_eq_zero_iff- In ZMod b, the natural number a casts to 0 if and only if b divides a.
Nat.mul_div_cancel_left- If n > 0, then (n * m) / n = m for natural numbers.
Nat.Prime.pos- Every prime natural number is strictly positive.
ZMod.card- The cardinality of ZMod n as a finite type is n.
Nat.sub_pos_of_lt- If m < n, then n - m > 0 for natural numbers.
zero_pow- Raising zero to any non-zero power in a monoid with zero gives zero.
ne_of_gt- A strictly greater element in a preorder is not equal to the lesser element.
Units.val_injective- The coercion from the group of units into the underlying monoid is injective.
Units.ne_zero- The value of a unit in a nontrivial monoid with zero is never zero.
Units.mk0- Constructs a unit from any non-zero element in a group with zero.
sum_sdiff- Splitting a finite set into a subset and its difference decomposes a sum into the sum over the difference plus the sum over the subset.
sum_singleton- The sum of a function over a singleton set equals the value of the function at that element.
add_zero- Adding zero to an element in an additive zero class leaves it unchanged.
FiniteField.sum_pow_units- In a finite field K, the sum of i-th powers of all units is -1 if |K| - 1 divides i, and 0 otherwise.
add_left_cancel- In an additive cancellation structure, a + b = a + c implies b = c.
mul_right_cancel₀- In a structure where non-zero multiplication cancels, if b ≠ 0 and a * b = c * b, then a = c.
div_mul_cancel₀- Dividing an element by a non-zero element and multiplying by it recovers the original element.
add_sub_cancel- In an additive commutative group, adding b - a to a gives b.
good_slopes_missing_prime_squarefree_zmod_prime_sum_pow_pred- For any prime p, the sum of (p-1)-th powers over all elements of ZMod p equals -1.
sum_fiberwise_of_maps_to- Summing a function over a finite set s equals summing fiberwise over the preimages under a map g : s → t.
ZMod.castHom_surjective- If m divides n, the canonical projection homomorphism from ZMod n to ZMod m is surjective.
AddMonoidHom.card_fiber_eq_of_mem_range- Any two elements in the range of an additive group homomorphism have fibers of equal cardinality.
sum_congr- Sums of pointwise equal functions over equal finite sets are equal.
sum_const- The sum of a constant over a finite set is the cardinality of the set times the constant.
nsmul_eq_mul- Natural number scalar multiplication in a semiring coincides with multiplication by the natural number cast.
card_eq_sum_card_fiberwise- The cardinality of a finite set equals the sum of the cardinalities of its fibers under a map.
card_univ- The cardinality of the universal finset is the cardinality of the finite type.
Nat.eq_div_of_mul_eq_right- If c ≠ 0 and c * a = b for natural numbers, then a = b / c.
Nat.Prime.ne_zero- A prime natural number is non-zero.
mul_sum- A common factor can be distributed across or factored out of a finite sum in a semiring.
subset_univ- Every finset of a finite type is a subset of the universal finset.
add_comm- Addition in an additive commutative magma is commutative.
zero_add- Adding zero on the left leaves an element unchanged.
card_sdiff_of_subset- The cardinality of the set difference t \ s for a subset s ⊆ t is the difference of their cardinalities.
card_singleton- A singleton finset has cardinality 1.
Nat.cast_sub- The cast of a natural difference n - m for m ≤ n equals the difference of their casts in an additive group with one.
mul_one- Multiplying an element by 1 leaves it unchanged.
good_slopes_mem_iff- An element m is a good slope for a permutation f if and only if x ↦ f(x) + mx is bijective.
map_add- An additive homomorphism preserves addition.
map_mul- A multiplicative homomorphism preserves multiplication.
sum_comm- The order of summation in a finite double sum can be swapped.
good_slopes_missing_prime_squarefree_zmod_prime_sum_affine_pow- In ZMod p, the sum of (p-1)-th powers along an affine line a ↦ y + ax is 0 if x = 0 and -1 if x ≠ 0.
good_slopes_missing_prime_squarefree_sum_indicator_lift- The sum over ZMod n of the indicator function (-1 if x mod p ≠ 0, and 0 if x mod p = 0) equals n/p modulo p.
good_slopes_missing_prime_squarefree_div_ne_zero- If n is squarefree and the prime p divides n, then n/p is non-zero in ZMod p.
- The Lean formalization constructs the ring homomorphism c = ZMod.castHom : ZMod n →+* ZMod p explicitly and carries out the calculation inside the prime field ZMod p.
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.
open Finsetprivate lemma good_slopes_missing_prime_squarefree_div_ne_zero (n p : ℕ) (hn : Squarefree n) (hp : Nat.Prime p) (hd : p ∣ n) : ((n / p : ℕ) : ZMod p) ≠ 0 := by intro h0 have h_dvd : p ∣ (n / p) := (ZMod.natCast_eq_zero_iff (n / p) p).mp h0 have hp2 : p * p ∣ n := by rcases hd with ⟨k, rfl⟩ rcases h_dvd with ⟨m, hm⟩ have : (p * k) / p = k := Nat.mul_div_cancel_left k (Nat.Prime.pos hp) rw [this] at hm subst hm exact ⟨m, by ring⟩ exact hp.not_isUnit (hn p hp2)private lemma good_slopes_missing_prime_squarefree_zmod_prime_sum_pow_pred (p : ℕ) [hp : Fact (Nat.Prime p)] : (∑ x : ZMod p, x ^ (p - 1)) = -1 := by have hcard : Fintype.card (ZMod p) = p := ZMod.card p have hp_pos : 0 < p - 1 := Nat.sub_pos_of_lt hp.1.two_le have h0 : (0 : ZMod p) ^ (p - 1) = 0 := zero_pow (ne_of_gt hp_pos) let φ : (ZMod p)ˣ ↪ ZMod p := ⟨fun x ↦ x, Units.val_injective⟩ have hmap : univ.map φ = univ \ {0} := by ext x simp only [mem_map, mem_univ, Function.Embedding.coeFn_mk, true_and, mem_sdiff, mem_singleton, φ] constructor · rintro ⟨u, rfl⟩; exact Units.ne_zero u · intro hx; exact ⟨Units.mk0 x hx, rfl⟩ calc ∑ x : ZMod p, x ^ (p - 1) = ∑ x ∈ univ \ {(0 : ZMod p)}, x ^ (p - 1) := by rw [← sum_sdiff ({0} : Finset (ZMod p)).subset_univ, sum_singleton, h0, add_zero] _ = ∑ x : (ZMod p)ˣ, (x ^ (p - 1) : ZMod p) := by simp [φ, ← hmap, univ.sum_map φ] _ = if Fintype.card (ZMod p) - 1 ∣ p - 1 then -1 else 0 := FiniteField.sum_pow_units (ZMod p) (p - 1) _ = -1 := by rw [hcard] simpprivate lemma good_slopes_missing_prime_squarefree_zmod_prime_sum_affine_pow (p : ℕ) [hp : Fact (Nat.Prime p)] (x y : ZMod p) : (∑ a : ZMod p, (y + a * x) ^ (p - 1)) = if x = 0 then 0 else -1 := by split_ifs with hx · subst hx simp · have hbij : Function.Bijective (fun a : ZMod p => y + a * x) := by refine ⟨?_, ?_⟩ · intro a b hab have : a * x = b * x := add_left_cancel hab exact mul_right_cancel₀ hx this · intro z refine ⟨(z - y) / x, ?_⟩ dsimp rw [div_mul_cancel₀ (z - y) hx, add_sub_cancel] rw [hbij.sum_comp (fun u => u ^ (p - 1))] exact good_slopes_missing_prime_squarefree_zmod_prime_sum_pow_pred pprivate lemma good_slopes_missing_prime_squarefree_sum_indicator_lift (n p : ℕ) [NeZero n] [NeZero p] (hd : p ∣ n) (hp : Fact (Nat.Prime p)) : (∑ x : ZMod n, if ZMod.castHom hd (ZMod p) x = 0 then (0 : ZMod p) else (-1 : ZMod p)) = ((n / p : ℕ) : ZMod p) := by let c := ZMod.castHom hd (ZMod p) let F : ZMod p → ZMod p := fun y => if y = 0 then 0 else -1 have hfib := (sum_fiberwise_of_maps_to (g := c) (s := univ) (t := univ) (fun _ _ => mem_univ _) (fun x => F (c x))).symm change (∑ x : ZMod n, F (c x)) = ((n / p : ℕ) : ZMod p) rw [hfib] have hsurj := ZMod.castHom_surjective hd have hfiber_eq : ∀ y : ZMod p, #{x : ZMod n | c x = y} = #{x : ZMod n | c x = 0} := by intro y exact AddMonoidHom.card_fiber_eq_of_mem_range c.toAddMonoidHom (hsurj y) (hsurj 0) have hstep1 : (∑ j : ZMod p, ∑ i ∈ univ with c i = j, F (c i)) = ∑ j : ZMod p, (#{i : ZMod n | c i = j} : ZMod p) * F j := by apply sum_congr rfl intro y _ have : (∑ x ∈ univ.filter (fun x => c x = y), F (c x)) = ∑ x ∈ univ.filter (fun x => c x = y), F y := by apply sum_congr rfl intro x hx simp only [mem_filter, mem_univ, true_and] at hx rw [hx] rw [this, sum_const, nsmul_eq_mul] rw [hstep1] simp_rw [hfiber_eq] have hsum_card : ∑ y : ZMod p, #{x : ZMod n | c x = y} = n := by have h := (card_eq_sum_card_fiberwise (f := c) (s := (univ : Finset (ZMod n))) (t := (univ : Finset (ZMod p))) (fun _ _ => mem_univ _)).symm rw [card_univ, ZMod.card] at h exact h simp_rw [hfiber_eq] at hsum_card rw [sum_const, card_univ, ZMod.card, nsmul_eq_mul] at hsum_card have hcard_val : #{x : ZMod n | c x = 0} = n / p := Nat.eq_div_of_mul_eq_right (Nat.Prime.ne_zero hp.1) hsum_card rw [← mul_sum] have hs : ({0} : Finset (ZMod p)) ⊆ univ := subset_univ _ have hsplit : (∑ y : ZMod p, F y) = (∑ y ∈ ({0} : Finset (ZMod p)), F y) + (∑ y ∈ univ \ ({0} : Finset (ZMod p)), F y) := by rw [← sum_sdiff hs, add_comm] have hzero : (∑ y ∈ ({0} : Finset (ZMod p)), F y) = 0 := by simp [F] have hrest : (∑ y ∈ univ \ ({0} : Finset (ZMod p)), F y) = ∑ y ∈ univ \ ({0} : Finset (ZMod p)), (-1 : ZMod p) := by apply sum_congr rfl intro y hy simp only [mem_sdiff, mem_singleton] at hy simp [F, hy.2] have hsumF : (∑ y : ZMod p, F y) = 1 := by rw [hsplit, hzero, zero_add, hrest, sum_const, card_sdiff_of_subset hs, card_singleton, card_univ, ZMod.card, nsmul_eq_mul] have hsub : ((p - 1 : ℕ) : ZMod p) = -1 := by have h1 : (1 : ℕ) ≤ p := hp.1.pos have h2 := Nat.cast_sub (R := ZMod p) h1 rw [h2] simp rw [hsub] ring rw [hsumF, mul_one, hcard_val]theorem good_slopes_missing_prime_squarefree (n p : ℕ) [NeZero n] [NeZero p] (hn : Squarefree n) (hp : Nat.Prime p) (hd : p ∣ n) (f : Equiv.Perm (ZMod n)) : ∃ a : ZMod p, ∀ m ∈ good_slopes n f, ZMod.castHom hd (ZMod p) m ≠ a := by have : Fact (Nat.Prime p) := ⟨hp⟩ let c : ZMod n →+* ZMod p := ZMod.castHom hd (ZMod p) by_contra h_all push Not at h_all choose m hm hma using h_all let total : ZMod p := ∑ x : ZMod n, (c x) ^ (p - 1) have hsum (a : ZMod p) : (∑ x : ZMod n, (c (f x) + a * c x) ^ (p - 1)) = total := by have hbij : Function.Bijective (fun x : ZMod n => f x + m a * x) := (good_slopes_mem_iff n f (m a)).mp (hm a) calc _ = ∑ x : ZMod n, (c (f x + m a * x)) ^ (p - 1) := by apply sum_congr rfl intro x _ rw [map_add, map_mul, hma a] _ = total := hbij.sum_comp (fun x => (c x) ^ (p - 1)) have houter : (∑ a : ZMod p, ∑ x : ZMod n, (c (f x) + a * c x) ^ (p - 1)) = 0 := by simp_rw [hsum] simp [total] have hinner : (∑ a : ZMod p, ∑ x : ZMod n, (c (f x) + a * c x) ^ (p - 1)) = ∑ x : ZMod n, if c x = 0 then 0 else (-1 : ZMod p) := by rw [sum_comm] apply sum_congr rfl intro x _ exact good_slopes_missing_prime_squarefree_zmod_prime_sum_affine_pow p (c x) (c (f x)) have heq : (∑ x : ZMod n, if c x = 0 then 0 else (-1 : ZMod p)) = 0 := hinner.symm.trans houter rw [good_slopes_missing_prime_squarefree_sum_indicator_lift n p hd ‹_›] at heq exact good_slopes_missing_prime_squarefree_div_ne_zero n p hn hp hd heq