The proof
Source
Main.lean · 29603 lines · 1.6 MB
Showing the first 500 of 29603 lines. The whole file is 1.6 MB; download it to read the rest.
/-! # Erdős 94, regular `n`-gon variant: reusable infrastructure
Paste-ready body for a `Main.lean` (it goes inside `namespace Bounty`, after the task header
`import Mathlib`, `import FormalConjectures.ErdosProblems.«94»`, `import TaskSupport`).
It passes the validator's static token policy: no attributes, instances, `set_option`, `#`-commands,
notation, `sorry`, or references to the forbidden source theorem.
* (a) `rngon_card`, `ngonPt_dist`, `rngon_dist_of_mem`: the regular `n`-gon has `n` vertices and
the vertices `k`, `l` are `2 |sin (π (k - l) / n)|` apart.
* (b) `rngon_sum_sq`: `∑ f(u)² = ngonValue n`, which is `n · C(n,2)` for odd `n` and
`n · C(n,2) - n²/4` for even `n` (`ngonValue_odd`, `ngonValue_even`).
Route: `sum_sq_mult_eq` (for any finite set, `∑ f(u)² = E/4` where `E` counts ordered pairs of
ordered pairs at equal distance) and `rngon_pairEnergy` (`E = n²(2(n-1) - [n even])`).
Explicit forms: `rngon_sum_sq_odd`, `rngon_sum_sq_even`. Per-chord ("equivalently") form:
`rngon_mult_chord` (chord `2 sin (π j / n)`, `0 < j < n/2`, has multiplicity `n`),
`rngon_mult_diameter` (even `n`: the diameter `2` has multiplicity `n/2`), `rngon_mult_le`
(no distance of the regular `n`-gon has multiplicity above `n`).
* (c) `sum_sq_le_of_mult_le` / `sum_sq_le_rngon`: if every distance class of an `n`-point set has
at most `n` pairs, then `∑ f(u)² ≤ ngonValue n` = the regular `n`-gon value.
* Reductions of the task statement: `target_iff_closed_form` (RHS replaced by `ngonValue n`),
`target_of_large_class` (proof mode: only sets with a class of more than `n` pairs remain),
`not_target_of_frequently` (counterexample mode: beat `ngonValue n` for infinitely many `n`).
* Helpers for explicit point sets: `pairEnergy_eq_sq` (squared distances), `dist_vec2_sq`.
All lemmas live in `Bounty.Erdos94Infra` and use only `propext`, `Classical.choice`, `Quot.sound`.
-/
namespace Erdos94Infra
open Finset
/-! ### (a) The regular `n`-gon: vertices, chord lengths, cardinality -/
/-- The `k`-th vertex of `Erdos94.regularNGon n`, written exactly as in its definition. -/
noncomputable def ngonPt (n k : ℕ) : EuclideanSpace ℝ (Fin 2) :=
!₂[Real.cos (2 * Real.pi * k / n), Real.sin (2 * Real.pi * k / n)]
theorem rngon_eq_image_range (n : ℕ) : Erdos94.regularNGon n = (range n).image (ngonPt n) := rfl
theorem chord_sq (c d : ℝ) :
(Real.cos (c + d) - Real.cos (c - d)) ^ 2 + (Real.sin (c + d) - Real.sin (c - d)) ^ 2
= (2 * Real.sin d) ^ 2 := by
rw [Real.cos_add, Real.cos_sub, Real.sin_add, Real.sin_sub]
linear_combination (4 * Real.sin d ^ 2) * Real.sin_sq_add_cos_sq c
/-- Chord length: the vertices `k` and `l` of the regular `n`-gon are `2 |sin (π (k - l) / n)|`
apart. -/
theorem ngonPt_dist (n k l : ℕ) :
dist (ngonPt n k) (ngonPt n l) = 2 * |Real.sin (Real.pi * ((k : ℝ) - l) / n)| := by
rw [EuclideanSpace.dist_eq]
simp only [ngonPt, Fin.sum_univ_two, Real.dist_eq, sq_abs, WithLp.ofLp_toLp,
Matrix.cons_val_zero, Matrix.cons_val_one]
have hk : 2 * Real.pi * (k : ℝ) / n
= Real.pi * ((k : ℝ) + l) / n + Real.pi * ((k : ℝ) - l) / n := by ring
have hl : 2 * Real.pi * (l : ℝ) / n
= Real.pi * ((k : ℝ) + l) / n - Real.pi * ((k : ℝ) - l) / n := by ring
rw [hk, hl, chord_sq, Real.sqrt_sq_eq_abs, abs_mul, abs_two]
theorem ngonPt_injOn (n : ℕ) : Set.InjOn (ngonPt n) (range n : Set ℕ) := by
intro k hk l hl hkl
simp only [coe_range, Set.mem_Iio] at hk hl
have hn : (0 : ℝ) < n := by exact_mod_cast (show 0 < n by omega)
have h0 : dist (ngonPt n k) (ngonPt n l) = 0 := by rw [hkl, dist_self]
rw [ngonPt_dist] at h0
have hs : Real.sin (Real.pi * ((k : ℝ) - l) / n) = 0 := by
have : |Real.sin (Real.pi * ((k : ℝ) - l) / n)| = 0 := by
linarith [abs_nonneg (Real.sin (Real.pi * ((k : ℝ) - l) / n))]
exact abs_eq_zero.mp this
obtain ⟨m, hm⟩ := Real.sin_eq_zero_iff.mp hs
have hm2 : (m : ℝ) * Real.pi * n = Real.pi * ((k : ℝ) - l) := (eq_div_iff hn.ne').mp hm
have hm3 : Real.pi * ((m : ℝ) * n - ((k : ℝ) - l)) = 0 := by linear_combination hm2
have hm4 : (m : ℝ) * n = (k : ℝ) - l := by
rcases mul_eq_zero.mp hm3 with h | h
· exact absurd h Real.pi_ne_zero
· linarith
have hmz : m * (n : ℤ) = (k : ℤ) - l := by exact_mod_cast hm4
have hm0 : m = 0 := by
rcases lt_trichotomy m 0 with h | h | h
· have : m * (n : ℤ) ≤ -(n : ℤ) := by nlinarith
omega
· exact h
· have : (n : ℤ) ≤ m * (n : ℤ) := by nlinarith
omega
subst hm0
omega
/-- The regular `n`-gon has exactly `n` vertices (for every `n`, including `0`). -/
theorem rngon_card (n : ℕ) : (Erdos94.regularNGon n).card = n := by
rw [rngon_eq_image_range, card_image_of_injOn (ngonPt_injOn n), card_range]
/-- Every pair of vertices of the regular `n`-gon is `(ngonPt n k, ngonPt n l)` with `k, l < n`,
at distance `2 |sin (π (k - l) / n)|`. -/
theorem rngon_dist_of_mem (n : ℕ) {x y : EuclideanSpace ℝ (Fin 2)}
(hx : x ∈ Erdos94.regularNGon n) (hy : y ∈ Erdos94.regularNGon n) :
∃ k < n, ∃ l < n, x = ngonPt n k ∧ y = ngonPt n l ∧
dist x y = 2 * |Real.sin (Real.pi * ((k : ℝ) - l) / n)| := by
rw [rngon_eq_image_range, mem_image] at hx hy
obtain ⟨k, hk, rfl⟩ := hx
obtain ⟨l, hl, rfl⟩ := hy
exact ⟨k, mem_range.mp hk, l, mem_range.mp hl, rfl, rfl, ngonPt_dist n k l⟩
/-- The chord from vertex `0` to vertex `j ≤ n` has length `2 sin (π j / n)`. -/
theorem ngonPt_dist_zero (n j : ℕ) (hj : j ≤ n) :
dist (ngonPt n j) (ngonPt n 0) = 2 * Real.sin (Real.pi * j / n) := by
rw [ngonPt_dist, Nat.cast_zero, sub_zero, abs_of_nonneg]
apply Real.sin_nonneg_of_nonneg_of_le_pi
· positivity
· rcases Nat.eq_zero_or_pos n with rfl | hn
· simp [Real.pi_pos.le]
· rw [div_le_iff₀ (by exact_mod_cast hn)]
have : (j : ℝ) ≤ n := by exact_mod_cast hj
nlinarith [Real.pi_pos]
/-! ### Energy: `∑ f(u)²` for an arbitrary finite set -/
section Energy
variable {X : Type*} [MetricSpace X]
/-- Number of ordered pairs `(x, y)` of ordered pairs of distinct points with
`dist x.1 x.2 = dist y.1 y.2`. -/
noncomputable def pairEnergy (P : Finset X) : ℕ :=
∑ x ∈ P.offDiag, ∑ y ∈ P.offDiag, if dist x.1 x.2 = dist y.1 y.2 then 1 else 0
theorem sum_card_sq_eq_pairEnergy (P : Finset X) :
∑ u ∈ distanceSet P, (P.offDiag.filter (fun x => dist x.1 x.2 = u)).card ^ 2
= pairEnergy P := by
unfold pairEnergy
simp_rw [card_filter, sq, sum_mul_sum]
rw [sum_comm]
refine sum_congr rfl (fun x hx => ?_)
rw [sum_comm]
refine sum_congr rfl (fun y _ => ?_)
have hxD : dist x.1 x.2 ∈ distanceSet P := mem_image_of_mem _ hx
rw [sum_eq_single (dist x.1 x.2)]
· simp [eq_comm]
· intro u _ hu
simp [Ne.symm hu]
· intro h
exact absurd hxD h
/-- `distanceMultiplicity` is exactly half the number of ordered pairs at that distance. -/
theorem mult_cast (P : Finset X) (u : ℝ) :
(distanceMultiplicity P u : ℝ) = ((P.offDiag.filter (fun x => dist x.1 x.2 = u)).card : ℝ) / 2 := by
unfold distanceMultiplicity
obtain ⟨r, hr⟩ := even_card_offDiag_filter_dist_eq P u
rw [hr, show r + r = 2 * r by ring, Nat.mul_div_cancel_left _ (by norm_num)]
push_cast
ring
/-- For any finite set, `∑ f(u)² = E / 4`. -/
theorem sum_sq_mult_eq (P : Finset X) :
∑ u ∈ distanceSet P, (distanceMultiplicity P u : ℝ) ^ 2 = (pairEnergy P : ℝ) / 4 := by
rw [← sum_card_sq_eq_pairEnergy, Nat.cast_sum, sum_div]
refine sum_congr rfl (fun u _ => ?_)
rw [mult_cast]
push_cast
ring
theorem offDiag_image_of_injective {ι : Type*} [DecidableEq X] (s : Finset ι) {q : ι → X}
(hq : Function.Injective q) : (s.image q).offDiag = s.offDiag.image (Prod.map q q) := by
ext ⟨a, b⟩
simp only [mem_offDiag, mem_image, Prod.exists, Prod.map_apply, Prod.mk.injEq]
constructor
· rintro ⟨⟨i, hi, rfl⟩, ⟨j, hj, rfl⟩, hne⟩
exact ⟨i, j, ⟨hi, hj, fun h => hne (by rw [h])⟩, rfl, rfl⟩
· rintro ⟨i, j, ⟨hi, hj, hij⟩, rfl, rfl⟩
exact ⟨⟨i, hi, rfl⟩, ⟨j, hj, rfl⟩, fun h => hij (hq h)⟩
theorem pairEnergy_image {ι : Type*} [DecidableEq X] (s : Finset ι) {q : ι → X}
(hq : Function.Injective q) :
pairEnergy (s.image q) = ∑ x ∈ s.offDiag, ∑ y ∈ s.offDiag,
if dist (q x.1) (q x.2) = dist (q y.1) (q y.2) then 1 else 0 := by
unfold pairEnergy
rw [offDiag_image_of_injective s hq, sum_image (fun x _ y _ h => (hq.prodMap hq) h)]
refine sum_congr rfl (fun x _ => ?_)
rw [sum_image (fun x _ y _ h => (hq.prodMap hq) h)]
rfl
theorem card_filter_dist_image {ι : Type*} [DecidableEq X] (s : Finset ι) {q : ι → X}
(hq : Function.Injective q) (u : ℝ) :
((s.image q).offDiag.filter (fun x => dist x.1 x.2 = u)).card
= ∑ x ∈ s.offDiag, if dist (q x.1) (q x.2) = u then 1 else 0 := by
rw [card_filter, offDiag_image_of_injective s hq, sum_image (fun x _ y _ h => (hq.prodMap hq) h)]
rfl
/-- `pairEnergy` with squared distances (handy for explicit point sets: no square roots). -/
theorem pairEnergy_eq_sq (P : Finset X) :
pairEnergy P = ∑ x ∈ P.offDiag, ∑ y ∈ P.offDiag,
if dist x.1 x.2 ^ 2 = dist y.1 y.2 ^ 2 then 1 else 0 := by
unfold pairEnergy
refine sum_congr rfl (fun x _ => sum_congr rfl (fun y _ => ?_))
have key : dist x.1 x.2 = dist y.1 y.2 ↔ dist x.1 x.2 ^ 2 = dist y.1 y.2 ^ 2 := by
rw [sq_eq_sq_iff_abs_eq_abs, abs_of_nonneg dist_nonneg, abs_of_nonneg dist_nonneg]
by_cases h : dist x.1 x.2 = dist y.1 y.2
· rw [if_pos h, if_pos (key.mp h)]
· rw [if_neg h, if_neg (fun h' => h (key.mpr h'))]
end Energy
/-- Squared distance of explicit points of the plane. -/
theorem dist_vec2_sq (a b c d : ℝ) :
dist (!₂[a, b] : EuclideanSpace ℝ (Fin 2)) !₂[c, d] ^ 2 = (a - c) ^ 2 + (b - d) ^ 2 := by
rw [EuclideanSpace.dist_eq, Real.sq_sqrt (by positivity)]
simp [Fin.sum_univ_two, Real.dist_eq, sq_abs]
/-! ### (b) The regular `n`-gon, indexed by `ZMod n` -/
section ZModIndex
variable (n : ℕ) [NeZero n]
theorem rngon_eq_image_zmod :
Erdos94.regularNGon n = (univ : Finset (ZMod n)).image (fun z => ngonPt n z.val) := by
rw [rngon_eq_image_range]
ext x
simp only [mem_image, mem_range, mem_univ, true_and]
constructor
· rintro ⟨k, hk, rfl⟩
exact ⟨(k : ZMod n), by rw [ZMod.val_natCast, Nat.mod_eq_of_lt hk]⟩
· rintro ⟨z, rfl⟩
exact ⟨z.val, ZMod.val_lt z, rfl⟩
theorem zq_injective : Function.Injective (fun z : ZMod n => ngonPt n z.val) := by
intro z w h
apply ZMod.val_injective
exact ngonPt_injOn n (by simp [ZMod.val_lt z]) (by simp [ZMod.val_lt w]) h
theorem sin_sq_eq_half (x : ℝ) : Real.sin x ^ 2 = (1 - Real.cos (2 * x)) / 2 := by
rw [Real.cos_two_mul]
linarith [Real.sin_sq_add_cos_sq x]
theorem two_pi_div_eq_iff (a b k : ℤ) :
2 * (Real.pi * b / n) = 2 * k * Real.pi + 2 * (Real.pi * a / n) ↔ b = k * n + a := by
have hn : (n : ℝ) ≠ 0 := by exact_mod_cast NeZero.ne n
have hc : (2 * Real.pi / n : ℝ) ≠ 0 := div_ne_zero (by positivity) hn
have key : 2 * (Real.pi * b / n) - (2 * k * Real.pi + 2 * (Real.pi * a / n))
= (2 * Real.pi / n) * ((b : ℝ) - (k * n + a)) := by
field_simp
rw [← sub_eq_zero, key, mul_eq_zero, or_iff_right hc, sub_eq_zero]
constructor
· intro h
exact_mod_cast h
· intro h
rw [h]
push_cast
ring
theorem two_pi_div_eq_iff' (a b k : ℤ) :
2 * (Real.pi * b / n) = 2 * k * Real.pi - 2 * (Real.pi * a / n) ↔ b = k * n - a := by
have h := two_pi_div_eq_iff n (-a) b k
push_cast at h
rw [show (2 * k * Real.pi - 2 * (Real.pi * a / n) : ℝ)
= 2 * k * Real.pi + 2 * (Real.pi * -(a : ℝ) / n) by ring, h]
constructor <;> intro h' <;> linarith
/-- The key arithmetic characterisation of equal chords. -/
theorem abs_sin_eq_iff (a b : ℤ) :
|Real.sin (Real.pi * a / n)| = |Real.sin (Real.pi * b / n)| ↔
((a : ZMod n) = b ∨ (a : ZMod n) = -b) := by
rw [← sq_eq_sq_iff_abs_eq_abs, sin_sq_eq_half, sin_sq_eq_half]
have step : (1 - Real.cos (2 * (Real.pi * a / n))) / 2 = (1 - Real.cos (2 * (Real.pi * b / n))) / 2
↔ Real.cos (2 * (Real.pi * a / n)) = Real.cos (2 * (Real.pi * b / n)) := by
constructor <;> intro h <;> linarith
rw [step, Real.cos_eq_cos_iff]
have hneg : ((a : ZMod n) = -b) ↔ ((-b : ℤ) : ZMod n) = a := by
push_cast
exact eq_comm
rw [hneg, ZMod.intCast_eq_intCast_iff_dvd_sub, ZMod.intCast_eq_intCast_iff_dvd_sub]
constructor
· rintro ⟨k, hk | hk⟩
· left
exact ⟨k, by rw [(two_pi_div_eq_iff n a b k).mp hk]; ring⟩
· right
exact ⟨k, by rw [(two_pi_div_eq_iff' n a b k).mp hk]; ring⟩
· rintro (⟨k, hk⟩ | ⟨k, hk⟩)
· exact ⟨k, Or.inl ((two_pi_div_eq_iff n a b k).mpr (by linarith))⟩
· exact ⟨k, Or.inr ((two_pi_div_eq_iff' n a b k).mpr (by linarith))⟩
theorem zq_dist (z w : ZMod n) :
dist (ngonPt n z.val) (ngonPt n w.val)
= 2 * |Real.sin (Real.pi * ((((z.val : ℤ) - w.val : ℤ)) : ℝ) / n)| := by
rw [ngonPt_dist]
push_cast
ring_nf
theorem zq_dist_eq_iff (z w z' w' : ZMod n) :
dist (ngonPt n z.val) (ngonPt n w.val) = dist (ngonPt n z'.val) (ngonPt n w'.val) ↔
(z - w = z' - w' ∨ z - w = -(z' - w')) := by
rw [zq_dist, zq_dist]
have h2 : ∀ x y : ℝ, 2 * |x| = 2 * |y| ↔ |x| = |y| := fun x y => by
constructor <;> intro h <;> linarith
rw [h2, abs_sin_eq_iff]
have hz : ∀ z w : ZMod n, ((((z.val : ℤ) - w.val : ℤ)) : ZMod n) = z - w := by
intro z w
push_cast
simp
rw [hz, hz]
/-- Summing a function of the difference over ordered pairs of distinct residues. -/
theorem sum_offDiag_sub (F : ZMod n → ℕ) :
∑ x ∈ (univ : Finset (ZMod n)).offDiag, F (x.1 - x.2)
= n * ∑ d ∈ (univ : Finset (ZMod n)).erase 0, F d := by
have h1 : (univ : Finset (ZMod n)).offDiag
= (univ ×ˢ univ).filter (fun x : ZMod n × ZMod n => x.1 ≠ x.2) := by
ext x
simp
rw [h1, sum_filter, univ_product_univ, Fintype.sum_prod_type]
have h2 : ∀ a : ZMod n, (∑ b : ZMod n, if a ≠ b then F (a - b) else 0)
= ∑ d ∈ (univ : Finset (ZMod n)).erase 0, F d := by
intro a
rw [← filter_ne' univ 0, sum_filter]
exact Fintype.sum_equiv (Equiv.subLeft a) _ _ (fun b => by simp [sub_eq_zero])
rw [sum_congr rfl (fun a _ => h2 a), sum_const, card_univ, ZMod.card, smul_eq_mul]
theorem card_neg_eq_self :
((univ.erase (0 : ZMod n)).filter (fun d => d = -d)).card = if Even n then 1 else 0 := by
have key : ∀ d : ZMod n, (d ∈ univ.erase 0 ∧ d = -d) ↔ 2 * d.val = n := by
intro d
rw [mem_erase, eq_comm (a := d) (b := -d), ZMod.neg_eq_self_iff]
constructor
· rintro ⟨⟨hd, -⟩, h | h⟩
· exact absurd h hd
· exact h
· intro h
refine ⟨⟨?_, mem_univ _⟩, Or.inr h⟩
rintro rfl
rw [ZMod.val_zero] at h
exact NeZero.ne n (by omega)
split_ifs with he
· obtain ⟨m, hm⟩ := he
have hm0 : 0 < m := by
have := NeZero.ne n
omega
have hmv : (m : ZMod n).val = m := by rw [ZMod.val_natCast, Nat.mod_eq_of_lt (by omega)]
rw [card_eq_one]
refine ⟨(m : ZMod n), ?_⟩
ext d
rw [mem_filter, key d, mem_singleton]
constructor
· intro h
apply ZMod.val_injective
rw [hmv]
omega
· rintro rfl
rw [hmv]
omega
· rw [card_eq_zero, filter_eq_empty_iff]
intro d hd hdd
have := (key d).mp ⟨hd, hdd⟩
exact he ⟨d.val, by omega⟩
theorem sum_pair_count :
(∑ d ∈ (univ : Finset (ZMod n)).erase 0, if d = -d then (1 : ℕ) else 2)
= 2 * (n - 1) - if Even n then 1 else 0 := by
rw [sum_ite, sum_const, sum_const, smul_eq_mul, smul_eq_mul, mul_one, card_neg_eq_self]
have htot := card_filter_add_card_filter_not (s := (univ : Finset (ZMod n)).erase 0)
(fun d => d = -d)
rw [card_erase_of_mem (mem_univ _), card_univ, ZMod.card, card_neg_eq_self] at htot
split_ifs at htot ⊢ <;> omega
theorem zmod_pair_count :
(∑ x ∈ (univ : Finset (ZMod n)).offDiag, ∑ y ∈ (univ : Finset (ZMod n)).offDiag,
if x.1 - x.2 = y.1 - y.2 ∨ x.1 - x.2 = -(y.1 - y.2) then (1 : ℕ) else 0)
= n * n * (2 * (n - 1) - if Even n then 1 else 0) := by
have inner : ∀ d : ZMod n, (∑ y ∈ (univ : Finset (ZMod n)).offDiag,
if d = y.1 - y.2 ∨ d = -(y.1 - y.2) then (1 : ℕ) else 0)
= n * ∑ e ∈ (univ : Finset (ZMod n)).erase 0, if d = e ∨ d = -e then (1 : ℕ) else 0 :=
fun d => sum_offDiag_sub n (fun e => if d = e ∨ d = -e then (1 : ℕ) else 0)
rw [sum_congr rfl (fun x _ => inner (x.1 - x.2))]
rw [sum_offDiag_sub n (fun d => n * ∑ e ∈ (univ : Finset (ZMod n)).erase 0,
if d = e ∨ d = -e then (1 : ℕ) else 0)]
have pair : ∀ d ∈ (univ : Finset (ZMod n)).erase 0,
n * (∑ e ∈ (univ : Finset (ZMod n)).erase 0, if d = e ∨ d = -e then (1 : ℕ) else 0)
= n * (if d = -d then 1 else 2) := by
intro d hd
have hd0 : d ≠ 0 := (mem_erase.mp hd).1
rw [sum_boole]
have hset : ((univ : Finset (ZMod n)).erase 0).filter (fun e => d = e ∨ d = -e) = {d, -d} := by
ext e
simp only [mem_filter, mem_erase, mem_univ, and_true, mem_insert, mem_singleton]
constructor
· rintro ⟨-, h | h⟩
· exact Or.inl h.symm
· right
rw [h, neg_neg]
· rintro (rfl | rfl)
· exact ⟨hd0, Or.inl rfl⟩
· exact ⟨neg_ne_zero.mpr hd0, Or.inr (neg_neg _).symm⟩
rw [hset]
split_ifs with h
· rw [← h, pair_eq_singleton, card_singleton]
rfl
· rw [card_pair h]
rfl
rw [sum_congr rfl pair, ← mul_sum, sum_pair_count]
ring
theorem rngon_pairEnergy :
pairEnergy (Erdos94.regularNGon n) = n * n * (2 * (n - 1) - if Even n then 1 else 0) := by
rw [rngon_eq_image_zmod, pairEnergy_image _ (zq_injective n), ← zmod_pair_count]
refine sum_congr rfl (fun x _ => sum_congr rfl (fun y _ => ?_))
by_cases h : x.1 - x.2 = y.1 - y.2 ∨ x.1 - x.2 = -(y.1 - y.2)
· rw [if_pos ((zq_dist_eq_iff n x.1 x.2 y.1 y.2).mpr h), if_pos h]
· rw [if_neg (fun h' => h ((zq_dist_eq_iff n x.1 x.2 y.1 y.2).mp h')), if_neg h]
theorem card_filter_pm (d : ZMod n) (hd : d ≠ 0) :
(((univ : Finset (ZMod n)).erase 0).filter (fun e => e = d ∨ e = -d)).card
= if d = -d then 1 else 2 := by
have hset : ((univ : Finset (ZMod n)).erase 0).filter (fun e => e = d ∨ e = -d) = {d, -d} := by
ext e
simp only [mem_filter, mem_erase, mem_univ, and_true, mem_insert, mem_singleton]
constructor
· rintro ⟨-, h⟩
exact h
· rintro (rfl | rfl)
· exact ⟨hd, Or.inl rfl⟩
· exact ⟨neg_ne_zero.mpr hd, Or.inr rfl⟩
rw [hset]
split_ifs with h
· rw [← h, pair_eq_singleton, card_singleton]
· rw [card_pair h]
/-- Ordered pairs of distinct vertices at the chord of residue `d ≠ 0`: `n` or `2n` of them. -/
theorem rngon_card_filter_residue (d : ZMod n) (hd : d ≠ 0) :
((Erdos94.regularNGon n).offDiag.filter
(fun x => dist x.1 x.2 = dist (ngonPt n d.val) (ngonPt n 0))).card
= n * (if d = -d then 1 else 2) := by
rw [rngon_eq_image_zmod, card_filter_dist_image _ (zq_injective n)]
have h0 : ngonPt n 0 = ngonPt n (0 : ZMod n).val := by rw [ZMod.val_zero]
rw [h0]
have hterm : ∀ x ∈ (univ : Finset (ZMod n)).offDiag,
(if dist (ngonPt n x.1.val) (ngonPt n x.2.val)
= dist (ngonPt n d.val) (ngonPt n (0 : ZMod n).val) then (1 : ℕ) else 0)
= if x.1 - x.2 = d ∨ x.1 - x.2 = -d then (1 : ℕ) else 0 := by
intro x _
have key := zq_dist_eq_iff n x.1 x.2 d 0
rw [sub_zero] at key
by_cases h : x.1 - x.2 = d ∨ x.1 - x.2 = -d
· rw [if_pos (key.mpr h), if_pos h]
· rw [if_neg (fun h' => h (key.mp h')), if_neg h]
rw [sum_congr rfl hterm, sum_offDiag_sub n (fun e => if e = d ∨ e = -d then (1 : ℕ) else 0),
sum_boole, card_filter_pm n d hd, Nat.cast_id]
/-- Multiplicity of the chord of residue `d ≠ 0`: `n`, or `n / 2` for the diameter `d = -d`. -/
theorem rngon_mult_residue (d : ZMod n) (hd : d ≠ 0) :
distanceMultiplicity (Erdos94.regularNGon n) (dist (ngonPt n d.val) (ngonPt n 0))
= if d = -d then n / 2 else n := by
unfold distanceMultiplicity
rw [rngon_card_filter_residue n d hd]
split_ifs <;> omega
end ZModIndex
/-- Each chord `2 sin (π j / n)` with `0 < j < n / 2` has multiplicity exactly `n`. -/
theorem rngon_mult_chord (n j : ℕ) (hj : 0 < j) (hjn : 2 * j < n) :
distanceMultiplicity (Erdos94.regularNGon n) (2 * Real.sin (Real.pi * j / n)) = n := by
have : NeZero n := ⟨by omega⟩
have hjv : (j : ZMod n).val = j := by rw [ZMod.val_natCast, Nat.mod_eq_of_lt (by omega)]
have hd : (j : ZMod n) ≠ 0 := by
intro h
have := congrArg ZMod.val h
rw [hjv, ZMod.val_zero] at this
omega
have hnd : ¬ ((j : ZMod n) = -(j : ZMod n)) := by
intro h
rcases (ZMod.neg_eq_self_iff (j : ZMod n)).mp h.symm with h' | h'
· exact hd h'
· rw [hjv] at h'
omega
rw [← ngonPt_dist_zero n j (by omega), ← hjv, rngon_mult_residue n _ hd, if_neg hnd]
/-- For even `n > 0` the diameter `2` has multiplicity exactly `n / 2`. -/
theorem rngon_mult_diameter (n : ℕ) (he : Even n) (hn : 0 < n) :
distanceMultiplicity (Erdos94.regularNGon n) 2 = n / 2 := by
obtain ⟨m, hm⟩ := he
have : NeZero n := ⟨by omega⟩
have hmv : (m : ZMod n).val = m := by rw [ZMod.val_natCast, Nat.mod_eq_of_lt (by omega)]
have hd : (m : ZMod n) ≠ 0 := by
intro h
have := congrArg ZMod.val h
rw [hmv, ZMod.val_zero] at this
omega
have hnd : (m : ZMod n) = -(m : ZMod n) :=
((ZMod.neg_eq_self_iff (m : ZMod n)).mpr (Or.inr (by rw [hmv]; omega))).symm
have hm0 : (0 : ℝ) < m := by exact_mod_cast (show 0 < m by omega)
have h2 : (2 : ℝ) = dist (ngonPt n (m : ZMod n).val) (ngonPt n 0) := by
rw [hmv, ngonPt_dist_zero n m (by omega)]
have hpi : Real.pi * (m : ℝ) / n = Real.pi / 2 := by
rw [hm, Nat.cast_add, div_eq_div_iff (ne_of_gt (by linarith)) (by norm_num)]
ring
rw [hpi, Real.sin_pi_div_two]
ring
rw [h2, rngon_mult_residue n _ hd, if_pos hnd]
/-- No distance of the regular `n`-gon has multiplicity above `n`. -/
theorem rngon_mult_le (n : ℕ) (u : ℝ) : distanceMultiplicity (Erdos94.regularNGon n) u ≤ n := by
rcases Nat.eq_zero_or_pos n with rfl | hn
· simp [distanceMultiplicity, Erdos94.regularNGon]Provenance