number_theory.prime_counting ⟷ Mathlib.NumberTheory.PrimeCounting

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -5,7 +5,7 @@ Authors: Bolton Bailey
 -/
 import Data.Nat.PrimeFin
 import Data.Nat.Totient
-import Data.Finset.LocallyFinite.Basic
+import Order.Interval.Finset.Basic
 import Data.Nat.Count
 import Data.Nat.Nth
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

@@ -5,7 +5,7 @@ Authors: Bolton Bailey
 -/
 import Data.Nat.PrimeFin
 import Data.Nat.Totient
-import Data.Finset.LocallyFinite
+import Data.Finset.LocallyFinite.Basic
 import Data.Nat.Count
 import Data.Nat.Nth
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

@@ -3,11 +3,11 @@ Copyright (c) 2021 Bolton Bailey. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bolton Bailey
 -/
-import Mathbin.Data.Nat.PrimeFin
-import Mathbin.Data.Nat.Totient
-import Mathbin.Data.Finset.LocallyFinite
-import Mathbin.Data.Nat.Count
-import Mathbin.Data.Nat.Nth
+import Data.Nat.PrimeFin
+import Data.Nat.Totient
+import Data.Finset.LocallyFinite
+import Data.Nat.Count
+import Data.Nat.Nth
 
 #align_import number_theory.prime_counting from "leanprover-community/mathlib"@"1b089e3bdc3ce6b39cd472543474a0a137128c6c"
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

@@ -102,7 +102,7 @@ theorem primeCounting'_add_le {a k : ℕ} (h0 : 0 < a) (h1 : a < k) (n : ℕ) :
       apply card_union_le
     _ ≤ π' k + ((Ico k (k + n)).filterₓ Prime).card := by
       rw [prime_counting', count_eq_card_filter_range]
-    _ ≤ π' k + ((Ico k (k + n)).filterₓ (coprime a)).card :=
+    _ ≤ π' k + ((Ico k (k + n)).filterₓ (Coprime a)).card :=
       by
       refine' add_le_add_left (card_le_of_subset _) k.prime_counting'
       simp only [subset_iff, and_imp, mem_filter, mem_Ico]

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

@@ -2,11 +2,6 @@
 Copyright (c) 2021 Bolton Bailey. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bolton Bailey
-
-! This file was ported from Lean 3 source module number_theory.prime_counting
-! leanprover-community/mathlib commit 1b089e3bdc3ce6b39cd472543474a0a137128c6c
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Nat.PrimeFin
 import Mathbin.Data.Nat.Totient
@@ -14,6 +9,8 @@ import Mathbin.Data.Finset.LocallyFinite
 import Mathbin.Data.Nat.Count
 import Mathbin.Data.Nat.Nth
 
+#align_import number_theory.prime_counting from "leanprover-community/mathlib"@"1b089e3bdc3ce6b39cd472543474a0a137128c6c"
+
 /-!
 # The Prime Counting Function
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/d30d31261cdb4d2f5e612eabc3c4bf45556350d5

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bolton Bailey
 
 ! This file was ported from Lean 3 source module number_theory.prime_counting
-! leanprover-community/mathlib commit 7fdd4f3746cb059edfdb5d52cba98f66fce418c0
+! leanprover-community/mathlib commit 1b089e3bdc3ce6b39cd472543474a0a137128c6c
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -17,6 +17,9 @@ import Mathbin.Data.Nat.Nth
 /-!
 # The Prime Counting Function
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 In this file we define the prime counting function: the function on natural numbers that returns
 the number of primes less than or equal to its input.
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/f2ad3645af9effcdb587637dc28a6074edc813f9

@@ -44,40 +44,53 @@ namespace Nat
 
 open Finset
 
+#print Nat.primeCounting' /-
 /-- A variant of the traditional prime counting function which gives the number of primes
 *strictly* less than the input. More convenient for avoiding off-by-one errors.
 -/
 def primeCounting' : ℕ → ℕ :=
   Nat.count Prime
 #align nat.prime_counting' Nat.primeCounting'
+-/
 
+#print Nat.primeCounting /-
 /-- The prime counting function: Returns the number of primes less than or equal to the input. -/
 def primeCounting (n : ℕ) : ℕ :=
   primeCounting' (n + 1)
 #align nat.prime_counting Nat.primeCounting
+-/
 
 scoped notation "π" => Nat.primeCounting
 
 scoped notation "π'" => Nat.primeCounting'
 
+#print Nat.monotone_primeCounting' /-
 theorem monotone_primeCounting' : Monotone primeCounting' :=
   count_monotone Prime
 #align nat.monotone_prime_counting' Nat.monotone_primeCounting'
+-/
 
+#print Nat.monotone_primeCounting /-
 theorem monotone_primeCounting : Monotone primeCounting :=
   monotone_primeCounting'.comp (monotone_id.AddConst _)
 #align nat.monotone_prime_counting Nat.monotone_primeCounting
+-/
 
+#print Nat.primeCounting'_nth_eq /-
 @[simp]
 theorem primeCounting'_nth_eq (n : ℕ) : π' (nth Prime n) = n :=
   count_nth_of_infinite infinite_setOf_prime _
 #align nat.prime_counting'_nth_eq Nat.primeCounting'_nth_eq
+-/
 
+#print Nat.prime_nth_prime /-
 @[simp]
 theorem prime_nth_prime (n : ℕ) : Prime (nth Prime n) :=
   nth_mem_of_infinite infinite_setOf_prime _
 #align nat.prime_nth_prime Nat.prime_nth_prime
+-/
 
+#print Nat.primeCounting'_add_le /-
 /-- A linear upper bound on the size of the `prime_counting'` function -/
 theorem primeCounting'_add_le {a k : ℕ} (h0 : 0 < a) (h1 : a < k) (n : ℕ) :
     π' (k + n) ≤ π' k + Nat.totient a * (n / a + 1) :=
@@ -103,6 +116,7 @@ theorem primeCounting'_add_le {a k : ℕ} (h0 : 0 < a) (h1 : a < k) (n : ℕ) :
       rw [add_le_add_iff_left]
       exact Ico_filter_coprime_le k n h0
 #align nat.prime_counting'_add_le Nat.primeCounting'_add_le
+-/
 
 end Nat
 

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

@@ -56,10 +56,8 @@ def primeCounting (n : ℕ) : ℕ :=
   primeCounting' (n + 1)
 #align nat.prime_counting Nat.primeCounting
 
--- mathport name: prime_counting
 scoped notation "π" => Nat.primeCounting
 
--- mathport name: prime_counting'
 scoped notation "π'" => Nat.primeCounting'
 
 theorem monotone_primeCounting' : Monotone primeCounting' :=

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bolton Bailey
 
 ! This file was ported from Lean 3 source module number_theory.prime_counting
-! leanprover-community/mathlib commit 16de0889b9e841c59af6cfece272b9276f9bf5ae
+! leanprover-community/mathlib commit 7fdd4f3746cb059edfdb5d52cba98f66fce418c0
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -72,12 +72,12 @@ theorem monotone_primeCounting : Monotone primeCounting :=
 
 @[simp]
 theorem primeCounting'_nth_eq (n : ℕ) : π' (nth Prime n) = n :=
-  count_nth_of_infinite _ infinite_setOf_prime _
+  count_nth_of_infinite infinite_setOf_prime _
 #align nat.prime_counting'_nth_eq Nat.primeCounting'_nth_eq
 
 @[simp]
 theorem prime_nth_prime (n : ℕ) : Prime (nth Prime n) :=
-  nth_mem_of_infinite _ infinite_setOf_prime _
+  nth_mem_of_infinite infinite_setOf_prime _
 #align nat.prime_nth_prime Nat.prime_nth_prime
 
 /-- A linear upper bound on the size of the `prime_counting'` function -/

mathlib commit https://github.com/leanprover-community/mathlib/commit/7e5137f579de09a059a5ce98f364a04e221aabf0

@@ -104,7 +104,6 @@ theorem primeCounting'_add_le {a k : ℕ} (h0 : 0 < a) (h1 : a < k) (n : ℕ) :
       by
       rw [add_le_add_iff_left]
       exact Ico_filter_coprime_le k n h0
-    
 #align nat.prime_counting'_add_le Nat.primeCounting'_add_le
 
 end Nat

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

Make all the notations that unambiguously should inherit the docstring of their definition actually inherit it.

Also write a few docstrings by hand. I only wrote the ones I was competent to write and which I was sure of. Some docstrings come from mathlib3 as they were lost during the early port.

This PR is only intended as a first pass There are many more docstrings to add.

@@ -51,9 +51,9 @@ def primeCounting (n : ℕ) : ℕ :=
   primeCounting' (n + 1)
 #align nat.prime_counting Nat.primeCounting
 
-scoped notation "π" => Nat.primeCounting
+@[inherit_doc] scoped notation "π" => Nat.primeCounting
 
-scoped notation "π'" => Nat.primeCounting'
+@[inherit_doc] scoped notation "π'" => Nat.primeCounting'
 
 theorem monotone_primeCounting' : Monotone primeCounting' :=
   count_monotone Prime

Change a few lemma names that have historically bothered me.

• Finset.card_le_of_subset → Finset.card_le_card
• Multiset.card_le_of_le → Multiset.card_le_card
• Multiset.card_lt_of_lt → Multiset.card_lt_card
• Set.ncard_le_of_subset → Set.ncard_le_ncard
• Finset.image_filter → Finset.filter_image
• CompleteLattice.finset_sup_compact_of_compact → CompleteLattice.isCompactElement_finset_sup

@@ -90,7 +90,7 @@ theorem primeCounting'_add_le {a k : ℕ} (h0 : 0 < a) (h1 : a < k) (n : ℕ) :
     _ ≤ π' k + ((Ico k (k + n)).filter Prime).card := by
       rw [primeCounting', count_eq_card_filter_range]
     _ ≤ π' k + ((Ico k (k + n)).filter (Coprime a)).card := by
-      refine' add_le_add_left (card_le_of_subset _) k.primeCounting'
+      refine' add_le_add_left (card_le_card _) k.primeCounting'
       simp only [subset_iff, and_imp, mem_filter, mem_Ico]
       intro p succ_k_le_p p_lt_n p_prime
       constructor

@@ -73,7 +73,7 @@ theorem prime_nth_prime (n : ℕ) : Prime (nth Prime n) :=
   nth_mem_of_infinite infinite_setOf_prime _
 #align nat.prime_nth_prime Nat.prime_nth_prime
 
-/-- The cardninality of the finset `primesBelow n` equals the counting function
+/-- The cardinality of the finset `primesBelow n` equals the counting function
 `primeCounting'` at `n`. -/
 lemma primesBelow_card_eq_primeCounting' (n : ℕ) : n.primesBelow.card = primeCounting' n := by
   simp only [primesBelow, primeCounting']

We define the set Nat.smoothNumbers n consisting of the positive natural numbers all of whose prime factors are strictly less than n.

We also define the finite set Nat.primesBelow n to be the set of prime numbers less than n.

The main definition Nat.equivProdNatSmoothNumbers establishes the bijection between ℕ × (smoothNumbers p) and smoothNumbers (p+1) given by sending (e, n) to p^e * n. Here p is a prime number.

This is in preparation of Euler Products; see this Zulip thread.

@@ -3,11 +3,9 @@ Copyright (c) 2021 Bolton Bailey. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bolton Bailey
 -/
-import Mathlib.Data.Nat.PrimeFin
 import Mathlib.Data.Nat.Totient
-import Mathlib.Data.Finset.LocallyFinite
-import Mathlib.Data.Nat.Count
 import Mathlib.Data.Nat.Nth
+import Mathlib.NumberTheory.SmoothNumbers
 
 #align_import number_theory.prime_counting from "leanprover-community/mathlib"@"7fdd4f3746cb059edfdb5d52cba98f66fce418c0"
 
@@ -75,6 +73,12 @@ theorem prime_nth_prime (n : ℕ) : Prime (nth Prime n) :=
   nth_mem_of_infinite infinite_setOf_prime _
 #align nat.prime_nth_prime Nat.prime_nth_prime
 
+/-- The cardninality of the finset `primesBelow n` equals the counting function
+`primeCounting'` at `n`. -/
+lemma primesBelow_card_eq_primeCounting' (n : ℕ) : n.primesBelow.card = primeCounting' n := by
+  simp only [primesBelow, primeCounting']
+  exact (count_eq_card_filter_range Prime n).symm
+
 /-- A linear upper bound on the size of the `primeCounting'` function -/
 theorem primeCounting'_add_le {a k : ℕ} (h0 : 0 < a) (h1 : a < k) (n : ℕ) :
     π' (k + n) ≤ π' k + Nat.totient a * (n / a + 1) :=

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -85,7 +85,7 @@ theorem primeCounting'_add_le {a k : ℕ} (h0 : 0 < a) (h1 : a < k) (n : ℕ) :
       apply card_union_le
     _ ≤ π' k + ((Ico k (k + n)).filter Prime).card := by
       rw [primeCounting', count_eq_card_filter_range]
-    _ ≤ π' k + ((Ico k (k + n)).filter (coprime a)).card := by
+    _ ≤ π' k + ((Ico k (k + n)).filter (Coprime a)).card := by
       refine' add_le_add_left (card_le_of_subset _) k.primeCounting'
       simp only [subset_iff, and_imp, mem_filter, mem_Ico]
       intro p succ_k_le_p p_lt_n p_prime

This reverts commit 6f8e8104. Unfortunately this bump was not linted correctly, as CI did not run runLinter Mathlib.

We can unrevert once that's fixed.

@@ -85,7 +85,7 @@ theorem primeCounting'_add_le {a k : ℕ} (h0 : 0 < a) (h1 : a < k) (n : ℕ) :
       apply card_union_le
     _ ≤ π' k + ((Ico k (k + n)).filter Prime).card := by
       rw [primeCounting', count_eq_card_filter_range]
-    _ ≤ π' k + ((Ico k (k + n)).filter (Coprime a)).card := by
+    _ ≤ π' k + ((Ico k (k + n)).filter (coprime a)).card := by
       refine' add_le_add_left (card_le_of_subset _) k.primeCounting'
       simp only [subset_iff, and_imp, mem_filter, mem_Ico]
       intro p succ_k_le_p p_lt_n p_prime

Some changes have already been review and delegated in #6910 and #7148.

The diff that needs looking at is https://github.com/leanprover-community/mathlib4/pull/7174/commits/64d6d07ee18163627c8f517eb31455411921c5ac

The std bump PR was insta-merged already!

Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -85,7 +85,7 @@ theorem primeCounting'_add_le {a k : ℕ} (h0 : 0 < a) (h1 : a < k) (n : ℕ) :
       apply card_union_le
     _ ≤ π' k + ((Ico k (k + n)).filter Prime).card := by
       rw [primeCounting', count_eq_card_filter_range]
-    _ ≤ π' k + ((Ico k (k + n)).filter (coprime a)).card := by
+    _ ≤ π' k + ((Ico k (k + n)).filter (Coprime a)).card := by
       refine' add_le_add_left (card_le_of_subset _) k.primeCounting'
       simp only [subset_iff, and_imp, mem_filter, mem_Ico]
       intro p succ_k_le_p p_lt_n p_prime

• depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

@@ -2,11 +2,6 @@
 Copyright (c) 2021 Bolton Bailey. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Bolton Bailey
-
-! This file was ported from Lean 3 source module number_theory.prime_counting
-! leanprover-community/mathlib commit 7fdd4f3746cb059edfdb5d52cba98f66fce418c0
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Data.Nat.PrimeFin
 import Mathlib.Data.Nat.Totient
@@ -14,6 +9,8 @@ import Mathlib.Data.Finset.LocallyFinite
 import Mathlib.Data.Nat.Count
 import Mathlib.Data.Nat.Nth
 
+#align_import number_theory.prime_counting from "leanprover-community/mathlib"@"7fdd4f3746cb059edfdb5d52cba98f66fce418c0"
+
 /-!
 # The Prime Counting Function