How does this product over finite primes represents density of certain natural numbers?

81 Views Asked by At

Let $p_{i}$ be the $i^{th}$ prime. I read that the product

$\prod_{i=1}^{n} \big( 1 - \frac{1}{p_{i}} \big)$ represents the density of primes that are not divisible by any of the $p_{1}, p_{2}, \ldots , p_{n}$.

I realized that density of natural numbers divisible by any one of the $p_{i}$ is $\frac{1}{p_{i}}$; by any two of them is $\frac{1}{p_{i}p_{j}}$ with $i \neq j$ and so on. Note that each of these sets are infinite.

It appears that inclusion exclusion here is done on density level to obtain that the set of natural numbers divisible by at least of these primes $p_{i}$ has density

$\sum_{i=1}^{n} \frac{1}{p_{i}} - \sum_{i\neq j} \frac{1}{p_{i}p_{j}} + ... + (-1)^{n} \frac{1}{p_{1}p_{2} \cdots p_{n}} $

and hence the set of natural numbers not divisible by any of these $p_{i}$ has density

$1 - \sum_{i=1}^{n} \frac{1}{p_{i}} - \sum_{i\neq j} \frac{1}{p_{i}p_{j}} + ... + (-1)^{n} \frac{1}{p_{1}p_{2} \cdots p_{n}} = \prod_{i=1}^{n} \big( 1 - \frac{1}{p_{i}} \big) $

However,

  1. Is such exclusion-inclusion allowed in density arguments? If yes, why?

  2. If yes, what conditions do the sets $A_{1}, A_{2}, \ldots, A_{k}$ need to satisfy before I can start using analogous argument on these sets?

1

There are 1 best solutions below

6
On BEST ANSWER

Sure, you can use inclusion-exclusion like this. Just intersect all your sets with $[1,N]$ and use ordinary inclusion-exclusion to count them. Then divide by $N$ and take the limit as $N\to\infty$. More generally, this would work for any finite collection of sets $A_1,A_2,\dots,A_k$ such that every intersection of a subcollection of them has a natural density.

In this case, though, you can just count directly instead of using inclusion-exclusion. By the Chinese remainder theorem, there are exactly $\prod_{i=1}^n(p_i-1)$ residues mod $\prod_{i=1}^np_i$ that are not divisible by any $p_i$, since you just need the residue mod each $p_i$ to be nonzero and these can be chosen independently.