Skip to main content
AlexKontorovich/PrimeNumberTheoremAnd
Source indexedlemma · leanprover/lean4:v4.32.0

sum_lambda_eq_sum_mu_div_sq

PrimeNumberTheoremAnd.Consequences · PrimeNumberTheoremAnd/Consequences.lean:2096 to 2130

Mathematical statement

Exact Lean statement

lemma sum_lambda_eq_sum_mu_div_sq (N : ℕ) :
    ∑ n ∈ Finset.Icc 1 N, ((-1 : ℝ) ^ (Ω n)) =
    ∑ d ∈ Finset.Icc 1 (Nat.sqrt N), ∑ k ∈ Finset.Icc 1 (N / d^2), (μ k : ℝ)

Complete declaration

Lean source

Canonical source
Full Lean sourceLean 4
lemma sum_lambda_eq_sum_mu_div_sq (N : ) :    ∑ n  Finset.Icc 1 N, ((-1 : ) ^ (Ω n)) =    ∑ d  Finset.Icc 1 (Nat.sqrt N), ∑ k  Finset.Icc 1 (N / d^2), (μ k : ) := by      have h_sum_rewrite : ∑ n  Finset.Icc 1 N, (-1 : ) ^ (Ω n) = ∑ n  Finset.Icc 1 N, ∑ d  (Finset.Icc 1 N).filter (fun d => d^2 ∣ n), (μ (n / d^2) : ) := by        have h_sum_rewrite :  n  Finset.Icc 1 N, (-1 : ) ^ (Ω n) = ∑ d  (Finset.Icc 1 N).filter (fun d => d^2 ∣ n), (μ (n / d^2) : ) := by          intro n hn          have h_lambda_eq : ((-1 : ) ^ (Ω n)) = ∑ d  (Finset.Icc 1 n).filter (fun d => d^2 ∣ n), (μ (n / d^2) : ) := by            convert lambda_eq_sum_sq_dvd_mu n ( by linarith [ Finset.mem_Icc.mp hn ] ) using 1;          rw [ h_lambda_eq, Finset.sum_subset ];          · exact fun x hx => Finset.mem_filter.mpr  Finset.mem_Icc.mpr  Finset.mem_Icc.mp ( Finset.mem_filter.mp hx |>.1 ) |>.1, by linarith [ Finset.mem_Icc.mp ( Finset.mem_filter.mp hx |>.1 ) |>.2, Finset.mem_Icc.mp hn |>.2 ] , Finset.mem_filter.mp hx |>.2 ;          · simp +zetaDelta only [mem_Icc, mem_filter, not_and, and_imp, Int.cast_eq_zero] at *            exact fun x hx₁ hx₂ hx₃ hx₄ => False.elim <| hx₄ hx₁ ( by nlinarith [ Nat.le_of_dvd ( by linarith ) hx₃ ] ) hx₃;        exact Finset.sum_congr rfl h_sum_rewrite;      rw [ h_sum_rewrite, Finset.sum_sigma' ];      have h_reindex : ∑ x  (Finset.Icc 1 N).sigma fun (n : ) => {d  Finset.Icc 1 N | d ^ 2 ∣ n}, (μ (x.fst / x.snd ^ 2) : ) = ∑ d  Finset.Icc 1 (Nat.sqrt N), ∑ k  Finset.Icc 1 (N / d ^ 2), (μ k : ) := by        have : Finset.filter (fun x => x.snd ^ 2x.fst) (Finset.Icc 1 N ×ˢ Finset.Icc 1 N) = Finset.biUnion (Finset.Icc 1 (Nat.sqrt N)) (fun d => Finset.image (fun k => (d ^ 2 * k, d)) (Finset.Icc 1 (N / d ^ 2))) := by          ext n, d          simp only [Finset.mem_filter, Finset.mem_product, Finset.mem_Icc, Finset.mem_biUnion, Finset.mem_image, Prod.mk.injEq]          constructor          · intro ⟨⟨⟨hn1, hn2, hd1, hd2, hdiv            exact d, hd1, by rw [Nat.le_sqrt]; nlinarith [Nat.le_of_dvd (by linarith) hdiv], n / d ^ 2, Nat.div_pos (Nat.le_of_dvd (by linarith) hdiv) (by nlinarith), Nat.div_le_div_right hn2, Nat.mul_div_cancel' hdiv, rfl          · rintro a, ha₁, ha₂, b, hb₁, hb₂, hn, hd            rw [ hn,  hd]            exact ⟨⟨⟨by nlinarith, by nlinarith [Nat.div_mul_le_self N (a ^ 2)], ha₁, by nlinarith [Nat.sqrt_le N], dvd_mul_right _ _        rw [ Finset.sum_sigma' ];        apply Finset.sum_bij (fun x _ => x.snd, x.fst / x.snd ^ 2);        · simp_all +decide only [Finset.ext_iff, mem_filter, mem_product, mem_Icc, mem_biUnion, mem_image, Prod.forall,            Prod.mk.injEq, ↓existsAndEq, and_true, exists_and_left, mem_sigma, true_and, and_imp]          exact fun x hx₁ hx₂ hx₃ hx₄ hx₅ =>  by nlinarith [ Nat.le_of_dvd ( by linarith ) hx₅, Nat.lt_succ_sqrt N ], Nat.div_pos ( Nat.le_of_dvd ( by linarith ) hx₅ ) ( by positivity ), Nat.div_le_div_right hx₂ ;        · simp +contextual [ Finset.mem_sigma, Finset.mem_filter ];          aesop;        · simp +zetaDelta only [mem_sigma, mem_Icc, mem_filter, exists_prop, Sigma.exists, and_imp] at *          exact fun b hb₁ hb₂ hb₃ hb₄ =>  b.fst ^ 2 * b.snd, b.fst,   by nlinarith, by nlinarith [ Nat.div_mul_le_self N ( b.fst ^ 2 ) ] ,  by nlinarith, by nlinarith [ Nat.div_mul_le_self N ( b.fst ^ 2 ) ] , by norm_num , by simp +decide [ Nat.mul_div_cancel_left _ ( by nlinarith : 0 < b.fst ^ 2 ) ] ;        · aesop;      convert h_reindex using 1