Smooth numbers

For s : Finset ℕ we define the set Nat.factoredNumbers s of "s-factored numbers" consisting of the positive natural numbers all of whose prime factors are in s, and we provide some API for this.

We then define the set Nat.smoothNumbers n consisting of the positive natural numbers all of whose prime factors are strictly less than n. This is the special case s = Finset.range n of the set of s-factored numbers.

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. It is obtained from the more general bijection between ℕ × (factoredNumbers s) and factoredNumbers (s ∪ {p}); see Nat.equivProdNatFactoredNumbers.

Additionally, we define Nat.smoothNumbersUpTo N n as the Finset of n-smooth numbers up to and including N, and similarly Nat.roughNumbersUpTo for its complement in {1, ..., N}, and we provide some API, in particular bounds for their cardinalities; see Nat.smoothNumbersUpTo_card_le and Nat.roughNumbersUpTo_card_le.

def Nat.primesBelow (n : ℕ) : Finset ℕ

primesBelow n is the set of primes less than n as a Finset.

Equations

• n.primesBelow = Finset.filter (fun (p : ℕ) => Nat.Prime p) (Finset.range n)

@[simp]

theorem Nat.primesBelow_zero : Nat.primesBelow 0 = ∅

theorem Nat.mem_primesBelow {k : ℕ} {n : ℕ} : n ∈ k.primesBelow ↔ n < k ∧ Nat.Prime n

theorem Nat.prime_of_mem_primesBelow {p : ℕ} {n : ℕ} (h : p ∈ n.primesBelow) : Nat.Prime p

theorem Nat.lt_of_mem_primesBelow {p : ℕ} {n : ℕ} (h : p ∈ n.primesBelow) : p < n

theorem Nat.primesBelow_succ (n : ℕ) : n.succ.primesBelow = if Nat.Prime n then insert n n.primesBelow else n.primesBelow

theorem Nat.not_mem_primesBelow (n : ℕ) : n ∉ n.primesBelow

s-factored numbers

def Nat.factoredNumbers (s : Finset ℕ) : Set ℕ

factoredNumbers s, for a finite set s of natural numbers, is the set of positive natural numbers all of whose prime factors are in s.

Equations

• Nat.factoredNumbers s = {m : ℕ | m ≠ 0 ∧ ∀ p ∈ m.factors, p ∈ s}

theorem Nat.mem_factoredNumbers {s : Finset ℕ} {m : ℕ} : m ∈ Nat.factoredNumbers s ↔ m ≠ 0 ∧ ∀ p ∈ m.factors, p ∈ s

instance Nat.instDecidablePredMemSetFactoredNumbers (s : Finset ℕ) : DecidablePred fun (x : ℕ) => x ∈ Nat.factoredNumbers s

Membership in Nat.factoredNumbers n is decidable.

Equations

• Nat.instDecidablePredMemSetFactoredNumbers s = inferInstanceAs (DecidablePred fun (x : ℕ) => x ∈ {m : ℕ | m ≠ 0 ∧ ∀ p ∈ m.factors, p ∈ s})

theorem Nat.mem_factoredNumbers_of_dvd {s : Finset ℕ} {m : ℕ} {k : ℕ} (h : m ∈ Nat.factoredNumbers s) (h' : k ∣ m) : k ∈ Nat.factoredNumbers s

A number that divides an s-factored number is itself s-factored.

theorem Nat.mem_factoredNumbers_iff_forall_le {s : Finset ℕ} {m : ℕ} : m ∈ Nat.factoredNumbers s ↔ m ≠ 0 ∧ ∀ p ≤ m, Nat.Prime p → p ∣ m → p ∈ s

m is s-factored if and only if m is nonzero and all prime divisors ≤ m of m are in s.

theorem Nat.mem_factoredNumbers' {s : Finset ℕ} {m : ℕ} : m ∈ Nat.factoredNumbers s ↔ ∀ (p : ℕ), Nat.Prime p → p ∣ m → p ∈ s

m is s-factored if and only if all prime divisors of m are in s.

theorem Nat.ne_zero_of_mem_factoredNumbers {s : Finset ℕ} {m : ℕ} (h : m ∈ Nat.factoredNumbers s) : m ≠ 0

theorem Nat.primeFactors_subset_of_mem_factoredNumbers {s : Finset ℕ} {m : ℕ} (hm : m ∈ Nat.factoredNumbers s) : m.primeFactors ⊆ s

The Finset of prime factors of an s-factored number is contained in s.

theorem Nat.mem_factoredNumbers_of_primeFactors_subset {s : Finset ℕ} {m : ℕ} (hm : m ≠ 0) (hp : m.primeFactors ⊆ s) : m ∈ Nat.factoredNumbers s

If m ≠ 0 and the Finset of prime factors of m is contained in s, then m is s-factored.

theorem Nat.mem_factoredNumbers_iff_primeFactors_subset {s : Finset ℕ} {m : ℕ} : m ∈ Nat.factoredNumbers s ↔ m ≠ 0 ∧ m.primeFactors ⊆ s

m is s-factored if and only if m ≠ 0 and its Finset of prime factors is contained in s.

@[simp]

theorem Nat.factoredNumbers_empty : Nat.factoredNumbers ∅ = {1}

theorem Nat.mul_mem_factoredNumbers {s : Finset ℕ} {m : ℕ} {n : ℕ} (hm : m ∈ Nat.factoredNumbers s) (hn : n ∈ Nat.factoredNumbers s) : m * n ∈ Nat.factoredNumbers s

The product of two s-factored numbers is again s-factored.

theorem Nat.prod_mem_factoredNumbers (s : Finset ℕ) (n : ℕ) : (List.filter (fun (x : ℕ) => decide (x ∈ s)) n.factors).prod ∈ Nat.factoredNumbers s

The product of the prime factors of n that are in s is an s-factored number.

theorem Nat.factoredNumbers_insert (s : Finset ℕ) {N : ℕ} (hN : ¬Nat.Prime N) : Nat.factoredNumbers (insert N s) = Nat.factoredNumbers s

The sets of s-factored and of s ∪ {N}-factored numbers are the same when N is not prime. See Nat.equivProdNatFactoredNumbers for when N is prime.

theorem Nat.factoredNumbers_mono {s : Finset ℕ} {t : Finset ℕ} (hst : s ≤ t) : Nat.factoredNumbers s ⊆ Nat.factoredNumbers t

theorem Nat.factoredNumbers_compl {N : ℕ} {s : Finset ℕ} (h : N.primesBelow ≤ s) : (Nat.factoredNumbers s)ᶜ \ {0} ⊆ {n : ℕ | N ≤ n}

The non-zero non-s-factored numbers are ≥ N when s contains all primes less than N.

theorem Nat.pow_mul_mem_factoredNumbers {s : Finset ℕ} {p : ℕ} {n : ℕ} (hp : Nat.Prime p) (e : ℕ) (hn : n ∈ Nat.factoredNumbers s) : p ^ e * n ∈ Nat.factoredNumbers (insert p s)

If p is a prime and n is s-factored, then every product p^e * n is s ∪ {p}-factored.

theorem Nat.Prime.factoredNumbers_coprime {s : Finset ℕ} {p : ℕ} {n : ℕ} (hp : Nat.Prime p) (hs : p ∉ s) (hn : n ∈ Nat.factoredNumbers s) : p.Coprime n

If p ∉ s is a prime and n is s-factored, then p and n are coprime.

theorem Nat.factoredNumbers.map_prime_pow_mul {F : Type u_1} [CommSemiring F] {f : ℕ → F} (hmul : ∀ {m n : ℕ}, m.Coprime n → f (m * n) = f m * f n) {s : Finset ℕ} {p : ℕ} (hp : Nat.Prime p) (hs : p ∉ s) (e : ℕ) {m : ↑(Nat.factoredNumbers s)} : f (p ^ e * ↑m) = f (p ^ e) * f ↑m

If f : ℕ → F is multiplicative on coprime arguments, p ∉ s is a prime and m is s-factored, then f (p^e * m) = f (p^e) * f m.

def Nat.equivProdNatFactoredNumbers {s : Finset ℕ} {p : ℕ} (hp : Nat.Prime p) (hs : p ∉ s) : ℕ × ↑(Nat.factoredNumbers s) ≃ ↑(Nat.factoredNumbers (insert p s))

We establish the bijection from ℕ × factoredNumbers s to factoredNumbers (s ∪ {p}) given by (e, n) ↦ p^e * n when p ∉ s is a prime. See Nat.factoredNumbers_insert for when p is not prime.

Equations

• One or more equations did not get rendered due to their size.

@[simp]

theorem Nat.equivProdNatFactoredNumbers_apply {s : Finset ℕ} {p : ℕ} {e : ℕ} {m : ℕ} (hp : Nat.Prime p) (hs : p ∉ s) (hm : m ∈ Nat.factoredNumbers s) : ↑((Nat.equivProdNatFactoredNumbers hp hs) (e, ⟨m, hm⟩)) = p ^ e * m

@[simp]

theorem Nat.equivProdNatFactoredNumbers_apply' {s : Finset ℕ} {p : ℕ} (hp : Nat.Prime p) (hs : p ∉ s) (x : ℕ × ↑(Nat.factoredNumbers s)) : ↑((Nat.equivProdNatFactoredNumbers hp hs) x) = p ^ x.1 * ↑x.2

n-smooth numbers

def Nat.smoothNumbers (n : ℕ) : Set ℕ

smoothNumbers n is the set of n-smooth positive natural numbers, i.e., the positive natural numbers all of whose prime factors are less than n.

Equations

• n.smoothNumbers = {m : ℕ | m ≠ 0 ∧ ∀ p ∈ m.factors, p < n}

theorem Nat.mem_smoothNumbers {n : ℕ} {m : ℕ} : m ∈ n.smoothNumbers ↔ m ≠ 0 ∧ ∀ p ∈ m.factors, p < n

theorem Nat.smoothNumbers_eq_factoredNumbers (n : ℕ) : n.smoothNumbers = Nat.factoredNumbers (Finset.range n)

The n-smooth numbers agree with the Finset.range n-factored numbers.

theorem Nat.smmoothNumbers_eq_factoredNumbers_primesBelow (n : ℕ) : n.smoothNumbers = Nat.factoredNumbers n.primesBelow

The n-smooth numbers agree with the primesBelow n-factored numbers.

instance Nat.instDecidablePredMemSetSmoothNumbers (n : ℕ) : DecidablePred fun (x : ℕ) => x ∈ n.smoothNumbers

Membership in Nat.smoothNumbers n is decidable.

Equations

• n.instDecidablePredMemSetSmoothNumbers = inferInstanceAs (DecidablePred fun (x : ℕ) => x ∈ {m : ℕ | m ≠ 0 ∧ ∀ p ∈ m.factors, p < n})

theorem Nat.mem_smoothNumbers_of_dvd {n : ℕ} {m : ℕ} {k : ℕ} (h : m ∈ n.smoothNumbers) (h' : k ∣ m) : k ∈ n.smoothNumbers

A number that divides an n-smooth number is itself n-smooth.

theorem Nat.mem_smoothNumbers_iff_forall_le {n : ℕ} {m : ℕ} : m ∈ n.smoothNumbers ↔ m ≠ 0 ∧ ∀ p ≤ m, Nat.Prime p → p ∣ m → p < n

m is n-smooth if and only if m is nonzero and all prime divisors ≤ m of m are less than n.

theorem Nat.mem_smoothNumbers' {n : ℕ} {m : ℕ} : m ∈ n.smoothNumbers ↔ ∀ (p : ℕ), Nat.Prime p → p ∣ m → p < n

m is n-smooth if and only if all prime divisors of m are less than n.

theorem Nat.primeFactors_subset_of_mem_smoothNumbers {m : ℕ} {n : ℕ} (hms : m ∈ n.smoothNumbers) : m.primeFactors ⊆ n.primesBelow

The Finset of prime factors of an n-smooth number is contained in the Finset of primes below n.

theorem Nat.mem_smoothNumbers_of_primeFactors_subset {m : ℕ} {n : ℕ} (hm : m ≠ 0) (hp : m.primeFactors ⊆ Finset.range n) : m ∈ n.smoothNumbers

m is an n-smooth number if the Finset of its prime factors consists of numbers < n.

theorem Nat.mem_smoothNumbers_iff_primeFactors_subset {m : ℕ} {n : ℕ} : m ∈ n.smoothNumbers ↔ m ≠ 0 ∧ m.primeFactors ⊆ n.primesBelow

m is an n-smooth number if and only if m ≠ 0 and the Finset of its prime factors is contained in the Finset of primes below n

theorem Nat.ne_zero_of_mem_smoothNumbers {n : ℕ} {m : ℕ} (h : m ∈ n.smoothNumbers) : m ≠ 0

Zero is never a smooth number

@[simp]

theorem Nat.smoothNumbers_zero : Nat.smoothNumbers 0 = {1}

theorem Nat.mul_mem_smoothNumbers {m₁ : ℕ} {m₂ : ℕ} {n : ℕ} (hm1 : m₁ ∈ n.smoothNumbers) (hm2 : m₂ ∈ n.smoothNumbers) : m₁ * m₂ ∈ n.smoothNumbers

The product of two n-smooth numbers is an n-smooth number.

theorem Nat.prod_mem_smoothNumbers (n : ℕ) (N : ℕ) : (List.filter (fun (x : ℕ) => decide (x < N)) n.factors).prod ∈ N.smoothNumbers

The product of the prime factors of n that are less than N is an N-smooth number.

theorem Nat.smoothNumbers_succ {N : ℕ} (hN : ¬Nat.Prime N) : N.succ.smoothNumbers = N.smoothNumbers

The sets of N-smooth and of (N+1)-smooth numbers are the same when N is not prime. See Nat.equivProdNatSmoothNumbers for when N is prime.

@[simp]

theorem Nat.smoothNumbers_one : Nat.smoothNumbers 1 = {1}

theorem Nat.smoothNumbers_mono {N : ℕ} {M : ℕ} (hNM : N ≤ M) : N.smoothNumbers ⊆ M.smoothNumbers

theorem Nat.mem_smoothNumbers_of_lt {m : ℕ} {n : ℕ} (hm : 0 < m) (hmn : m < n) : m ∈ n.smoothNumbers

All m, 0 < m < n are n-smooth numbers

theorem Nat.smoothNumbers_compl (N : ℕ) : N.smoothNumbersᶜ \ {0} ⊆ {n : ℕ | N ≤ n}

The non-zero non-N-smooth numbers are ≥ N.

theorem Nat.pow_mul_mem_smoothNumbers {p : ℕ} {n : ℕ} (hp : p ≠ 0) (e : ℕ) (hn : n ∈ p.smoothNumbers) : p ^ e * n ∈ p.succ.smoothNumbers

If p is positive and n is p-smooth, then every product p^e * n is (p+1)-smooth.

theorem Nat.Prime.smoothNumbers_coprime {p : ℕ} {n : ℕ} (hp : Nat.Prime p) (hn : n ∈ p.smoothNumbers) : p.Coprime n

If p is a prime and n is p-smooth, then p and n are coprime.

theorem Nat.map_prime_pow_mul {F : Type u_1} [CommSemiring F] {f : ℕ → F} (hmul : ∀ {m n : ℕ}, m.Coprime n → f (m * n) = f m * f n) {p : ℕ} (hp : Nat.Prime p) (e : ℕ) {m : ↑p.smoothNumbers} : f (p ^ e * ↑m) = f (p ^ e) * f ↑m

If f : ℕ → F is multiplicative on coprime arguments, p is a prime and m is p-smooth, then f (p^e * m) = f (p^e) * f m.

def Nat.equivProdNatSmoothNumbers {p : ℕ} (hp : Nat.Prime p) : ℕ × ↑p.smoothNumbers ≃ ↑p.succ.smoothNumbers

We establish the bijection from ℕ × smoothNumbers p to smoothNumbers (p+1) given by (e, n) ↦ p^e * n when p is a prime. See Nat.smoothNumbers_succ for when p is not prime.

Equations

• Nat.equivProdNatSmoothNumbers hp = ((Equiv.prodCongrRight fun (x : ℕ) => Equiv.setCongr ⋯).trans (Nat.equivProdNatFactoredNumbers hp ⋯)).trans (Equiv.setCongr ⋯)

@[simp]

theorem Nat.equivProdNatSmoothNumbers_apply {p : ℕ} {e : ℕ} {m : ℕ} (hp : Nat.Prime p) (hm : m ∈ p.smoothNumbers) : ↑((Nat.equivProdNatSmoothNumbers hp) (e, ⟨m, hm⟩)) = p ^ e * m

@[simp]

theorem Nat.equivProdNatSmoothNumbers_apply' {p : ℕ} (hp : Nat.Prime p) (x : ℕ × ↑p.smoothNumbers) : ↑((Nat.equivProdNatSmoothNumbers hp) x) = p ^ x.1 * ↑x.2

Smooth and rough numbers up to a bound

We consider the sets of smooth and non-smooth ("rough") positive natural numbers ≤ N and prove bounds for their sizes.

def Nat.smoothNumbersUpTo (N : ℕ) (k : ℕ) : Finset ℕ

The k-smooth numbers up to and including N as a Finset

Equations

• N.smoothNumbersUpTo k = Finset.filter (fun (x : ℕ) => x ∈ k.smoothNumbers) (Finset.range N.succ)

theorem Nat.mem_smoothNumbersUpTo {N : ℕ} {k : ℕ} {n : ℕ} : n ∈ N.smoothNumbersUpTo k ↔ n ≤ N ∧ n ∈ k.smoothNumbers

def Nat.roughNumbersUpTo (N : ℕ) (k : ℕ) : Finset ℕ

The positive non-k-smooth (so "k-rough") numbers up to and including N as a Finset

Equations

• N.roughNumbersUpTo k = Finset.filter (fun (n : ℕ) => n ≠ 0 ∧ n ∉ k.smoothNumbers) (Finset.range N.succ)

theorem Nat.smoothNumbersUpTo_card_add_roughNumbersUpTo_card (N : ℕ) (k : ℕ) : (N.smoothNumbersUpTo k).card + (N.roughNumbersUpTo k).card = N

theorem Nat.eq_prod_primes_mul_sq_of_mem_smoothNumbers {n : ℕ} {k : ℕ} (h : n ∈ k.smoothNumbers) : ∃ s ∈ k.primesBelow.powerset, ∃ (m : ℕ), n = m ^ 2 * s.prod id

A k-smooth number can be written as a square times a product of distinct primes < k.

theorem Nat.smoothNumbersUpTo_subset_image (N : ℕ) (k : ℕ) : N.smoothNumbersUpTo k ⊆ Finset.image (fun (x : Finset ℕ × ℕ) => match x with | (s, m) => m ^ 2 * s.prod id) (k.primesBelow.powerset ×ˢ (Finset.range N.sqrt.succ).erase 0)

The set of k-smooth numbers ≤ N is contained in the set of numbers of the form m^2 * P, where m ≤ √N and P is a product of distinct primes < k.

theorem Nat.smoothNumbersUpTo_card_le (N : ℕ) (k : ℕ) : (N.smoothNumbersUpTo k).card ≤ 2 ^ k.primesBelow.card * N.sqrt

The cardinality of the set of k-smooth numbers ≤ N is bounded by 2^π(k-1) * √N.

theorem Nat.roughNumbersUpTo_eq_biUnion (N : ℕ) (k : ℕ) : N.roughNumbersUpTo k = (N.succ.primesBelow \ k.primesBelow).biUnion fun (p : ℕ) => Finset.filter (fun (m : ℕ) => m ≠ 0 ∧ p ∣ m) (Finset.range N.succ)

The set of k-rough numbers ≤ N can be written as the union of the sets of multiples ≤ N of primes k ≤ p ≤ N.

theorem Nat.roughNumbersUpTo_card_le (N : ℕ) (k : ℕ) : (N.roughNumbersUpTo k).card ≤ ∑ p ∈ N.succ.primesBelow \ k.primesBelow, N / p

The cardinality of the set of k-rough numbers ≤ N is bounded by the sum of ⌊N/p⌋ over the primes k ≤ p ≤ N.