AFTD Auto-Formalizing Theoretical Domains

good_slopes_missing_prime_squarefree

theoremverified

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

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.

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

    lines 5–14

    uses ZMod.natCast_eq_zero_iff, Nat.mul_div_cancel_left, Nat.Prime.pos

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

    lines 18–35

    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_units

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

    lines 39–52

    uses add_left_cancel, mul_right_cancel₀, div_mul_cancel₀, add_sub_cancel, good_slopes_missing_prime_squarefree_zmod_prime_sum_pow_pred

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

    lines 56–76

    uses sum_fiberwise_of_maps_to, ZMod.castHom_surjective, AddMonoidHom.card_fiber_eq_of_mem_range, sum_congr, sum_const, nsmul_eq_mul

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

    lines 77–84

    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_zero

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

    lines 85–104

    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_one

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

    lines 107–111

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

    lines 112–124

    uses good_slopes_mem_iff, sum_congr, map_add, map_mul

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

    lines 125–130

    uses sum_comm, sum_congr, good_slopes_missing_prime_squarefree_zmod_prime_sum_affine_pow

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

    lines 131–133

    uses good_slopes_missing_prime_squarefree_sum_indicator_lift, good_slopes_missing_prime_squarefree_div_ne_zero

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

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

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