import IncidenceMoments import ResidueMoment namespace CRTMoments open scoped BigOperators open KKFiniteCoreDraft IncidenceMoments /-- Canonical residues satisfying all local forbidden conditions on T. -/ def residues (T : Finset ℕ) (Ω : ℕ → Finset ℕ) : Finset ℕ := (Finset.range (period T)).filter (fun r => ∀ p ∈ T, r % p ∈ Ω p) def Canonical (T : Finset ℕ) (Ω : ℕ → Finset ℕ) : Prop := ∀ p ∈ T, ∀ a ∈ Ω p, a < p /-- Squarefree subset-product divisibility is exactly simultaneous local incidence. -/ theorem subset_divisor_iff (S T : Finset ℕ) (Ω : ℕ → Finset ℕ) (hS : PrimeFamily S) (hTS : T ⊆ S) (n : ℕ) : period T ∣ incidence S Ω n ↔ ∀ p ∈ T, n % p ∈ Ω p := by constructor · intro hd p hp apply (prime_dvd_incidence_iff S Ω hS p n (hTS hp)).mp exact (Finset.dvd_prod_of_mem id hp).trans hd · intro hn exact Finset.prod_dvd_prod_of_subset _ _ _ (fun p hp => Finset.mem_filter.mpr ⟨hTS hp, hn p hp⟩) lemma period_pos (T : Finset ℕ) (hT : PrimeFamily T) : 0 < period T := Finset.prod_pos (fun p hp => (hT p hp).pos) lemma prime_dvd_period (T : Finset ℕ) (p : ℕ) (hp : p ∈ T) : p ∣ period T := Finset.dvd_prod_of_mem id hp /-- Canonical reduction preserves every local condition in the subset modulus. -/ theorem mod_mem_residues_iff (T : Finset ℕ) (Ω : ℕ → Finset ℕ) (hT : PrimeFamily T) (n : ℕ) : n % period T ∈ residues T Ω ↔ ∀ p ∈ T, n % p ∈ Ω p := by simp only [residues, Finset.mem_filter, Finset.mem_range] have hb := Nat.mod_lt n (period_pos T hT) have hm : ∀ p ∈ T, (n % period T) % p = n % p := fun p hp => Nat.mod_mod_of_dvd n (prime_dvd_period T p hp) constructor · rintro ⟨_, hn⟩ intro p hp simpa only [hm p hp] using hn p hp · intro hn refine ⟨hb, ?_⟩ intro p hp rw [hm p hp] exact hn p hp lemma primes_pairwise (T : Finset ℕ) (hT : PrimeFamily T) : Set.Pairwise (↑T : Set ℕ) Nat.Coprime := by intro p hp q hq hn exact (hT p hp).coprime_iff_not_dvd.mpr (by intro hd exact hn ((Nat.dvd_prime (hT q hq)).mp hd |>.resolve_left (hT p hp).ne_one)) /-- Product-modulus uniqueness reuses Mathlib's finite-list CRT equivalence. -/ lemma modEq_period (T : Finset ℕ) (hT : PrimeFamily T) (a b : ℕ) (h : ∀ p ∈ T, Nat.ModEq p a b) : Nat.ModEq (period T) a b := by have pp : T.toList.Pairwise Nat.Coprime := T.nodup_toList.pairwise_of_forall_ne (by intro p hp q hq hn exact primes_pairwise T hT (Finset.mem_toList.mp hp) (Finset.mem_toList.mp hq) hn) have hh := (Nat.modEq_list_map_prod_iff (s := id) pp).mpr (by simpa only [Finset.mem_toList, id_eq] using h) simpa only [Finset.prod_map_toList, period, id_eq] using hh abbrev LocalChoices (T : Finset ℕ) (Ω : ℕ → Finset ℕ) := (p : T) → ↥(Ω p.val) def residueMap (T : Finset ℕ) (Ω : ℕ → Finset ℕ) (r : ↥(residues T Ω)) : LocalChoices T Ω := fun p => ⟨r.val % p.val, (Finset.mem_filter.mp r.property).2 p.val p.property⟩ lemma residueMap_injective (T : Finset ℕ) (Ω : ℕ → Finset ℕ) (hT : PrimeFamily T) : Function.Injective (residueMap T Ω) := by intro r s heq have hm : Nat.ModEq (period T) r.val s.val := modEq_period T hT _ _ (by intro p hp exact congrArg (fun f : LocalChoices T Ω => (f ⟨p, hp⟩).val) heq) apply Subtype.ext exact hm.eq_of_lt_of_lt (Finset.mem_range.mp (Finset.mem_filter.mp r.property).1) (Finset.mem_range.mp (Finset.mem_filter.mp s.property).1) lemma residueMap_surjective (T : Finset ℕ) (Ω : ℕ → Finset ℕ) (hT : PrimeFamily T) (hΩ : Canonical T Ω) : Function.Surjective (residueMap T Ω) := by intro f let a : ℕ → ℕ := fun p => if hp : p ∈ T then (f ⟨p, hp⟩).val else 0 have hs : ∀ p ∈ T, (id p : ℕ) ≠ 0 := fun p hp => (hT p hp).ne_zero let c := Nat.chineseRemainderOfFinset a id T hs (primes_pairwise T hT) have hc : ∀ p (hp : p ∈ T), (c : ℕ) % p = (f ⟨p, hp⟩).val := by intro p hp have ha : a p < p := by simp only [a, dite_eq_left hp] exact hΩ p hp _ (f ⟨p, hp⟩).property have hm := c.property p hp change (c : ℕ) % p = a p % p at hm rw [Nat.mod_eq_of_lt ha] at hm simpa only [a, dite_eq_left hp] using hm have hmem : (c : ℕ) ∈ residues T Ω := Finset.mem_filter.mpr ⟨Finset.mem_range.mpr (Nat.chineseRemainderOfFinset_lt_prod a id hs (primes_pairwise T hT)), fun p hp => by rw [hc p hp]; exact (f ⟨p, hp⟩).property⟩ refine ⟨⟨c, hmem⟩, ?_⟩ funext p apply Subtype.ext exact hc p.val p.property /-- Exact CRT cardinality of the canonical simultaneous forbidden residues. -/ theorem residues_card (T : Finset ℕ) (Ω : ℕ → Finset ℕ) (hT : PrimeFamily T) (hΩ : Canonical T Ω) : (residues T Ω).card = ∏ p ∈ T, (Ω p).card := by have he := Fintype.card_congr (Equiv.ofBijective (residueMap T Ω) ⟨residueMap_injective T Ω hT, residueMap_surjective T Ω hT hΩ⟩) calc (residues T Ω).card = ∏ p : T, (Ω p.val).card := by simpa only [Fintype.card_coe, Fintype.card_pi] using he _ = _ := Finset.prod_coe_sort T (fun p => (Ω p).card) /-- The divisor moment now counts the actual canonical CRT residue set. -/ theorem divisor_moment_eq_residue_count (X : ℕ) (S T : Finset ℕ) (Ω : ℕ → Finset ℕ) (hS : PrimeFamily S) (hTS : T ⊆ S) : (∑ t ∈ support X S Ω, if period T ∣ t then weight X S Ω t else 0) = ResidueMoment.residueSetCount X (period T) (residues T Ω) := by rw [divisor_moment] congr 1 ext n simp only [interval, Finset.mem_filter, subset_divisor_iff S T Ω hS hTS n, mod_mem_residues_iff T Ω (fun p hp => hS p (hTS hp)) n] /-- The complete real-valued moment remainder, with g(d) proved by CRT. -/ theorem real_divisor_moment_remainder (X : ℕ) (S T : Finset ℕ) (Ω : ℕ → Finset ℕ) (hS : PrimeFamily S) (hTS : T ⊆ S) (hΩ : Canonical T Ω) : |((∑ t ∈ support X S Ω, if period T ∣ t then weight X S Ω t else 0 : ℕ) : ℝ) - ((X : ℝ) / period T) * (∏ p ∈ T, (Ω p).card : ℕ)| ≤ (∏ p ∈ T, (Ω p).card : ℕ) := by have hT : PrimeFamily T := fun p hp => hS p (hTS hp) have hA : ∀ a ∈ residues T Ω, a < period T := fun a ha => Finset.mem_range.mp (Finset.mem_filter.mp ha).1 have h := ResidueMoment.residueSetCount_discrepancy_real X (period T) (residues T Ω) (period_pos T hT) hA rw [divisor_moment_eq_residue_count X S T Ω hS hTS] simpa only [residues_card T Ω hT hΩ, mul_comm] using h #print axioms subset_divisor_iff #print axioms mod_mem_residues_iff #print axioms modEq_period #print axioms residueMap_injective #print axioms residueMap_surjective #print axioms residues_card #print axioms divisor_moment_eq_residue_count #print axioms real_divisor_moment_remainder end CRTMoments