1

the Legendre sieve method gives us an upper bound $S$ for the numbers that are not relatively prime to $P_{z}$ up to $x$ where $P_{z}$ is the product of prime number less than z

$S=x\prod_{p<z}(1-\frac{1}{p})+O(2^{\pi (z)})$

I don't understand why the error term is $2^{\pi (z)}$ can someone explain where it came from ?

Abdo
  • 167
  • 1
    How many terms have been changed from $\bigl\lfloor \frac{x}{d}\bigr\rfloor$ to $\frac{x}{d}$ in order to obtain the main term $x\prod_{p < z}(1 - \frac{1}{p})$? – Daniel Fischer Jun 10 '20 at 10:45
  • @Daniel Fischer i don't understand – Abdo Jun 10 '20 at 15:38
  • Have you seen the formula for the exact number of $n \leqslant x$ that are coprime to $P_z$? – Daniel Fischer Jun 10 '20 at 17:43
  • @ Daniel Fischer yes I read the proof but I don't understand why the error term is $2^{z}$. Can you explain – Abdo Jun 10 '20 at 20:42
  • 1
    The exact number is $$B_z(x) = \sum_{d \mid P_z} \mu(d)\biggl\lfloor \frac{x}{d}\biggr\rfloor,,$$ where $\mu$ is the Möbius function. The sum has precisely $2^{\pi(z)}$ terms. Writing $\lfloor y\rfloor = y - \lbrace y\rbrace$, we obtain $$B_z(x) = x\prod_{p \leqslant z}\biggl(1 - \frac{1}{p}\biggr) - \sum_{d \mid P_z} \mu(d)\biggl\lbrace \frac{x}{d}\biggr\rbrace,.$$ That last sum is the error term. It contains $2^{\pi(z)}$ terms, each of which is smaller than $1$ in absolute value. Hence the error is bounded by $2^{\pi(z)}$. – Daniel Fischer Jun 10 '20 at 20:51
  • 1
    Well. I just saw that you used a strict inequality, $p < z$. Then the occurrences of $\pi(z)$ should be replaced with $\pi(\lceil z\rceil - 1) \leqslant \pi(z)$. No big difference, only more inconvenient typography. – Daniel Fischer Jun 10 '20 at 20:54
  • But why you say that there is a $2^{(\pi (z))}$ terms – Abdo Jun 10 '20 at 20:54
  • 1
    Because $P_z$ has that many divisors, it is the product of $\pi(z)$ (or $\pi(\lceil z\rceil - 1)$ for the strict inequality) primes. – Daniel Fischer Jun 10 '20 at 20:57
  • But you choose 2 and not 3 or another number – Abdo Jun 10 '20 at 20:58
  • 1
    I didn't choose, it comes out naturally from the divisor function. Do you know the formula for that? – Daniel Fischer Jun 10 '20 at 21:02
  • Can you explain more – Abdo Jun 10 '20 at 21:10
  • 1
    See e.g. here for the divisor function. In $P_z$, all exponents are $1$, so $\tau(P_z) = (1+1)^{r}$, where $r$ is the number of primes dividing $P_z$. – Daniel Fischer Jun 10 '20 at 21:31

0 Answers0