Skip to main content
added 161 characters in body
Source Link

I'm trying to arrive at estimate 1.17 (page 21) of Koukoulopoulos lecture notes [https://dms.umontreal.ca/~koukoulo/documents/notes/sievemethods.pdf]

$$\#\{n \leq x : p|n \Rightarrow p > \sqrt{x}\} = \frac{(2e^{- \gamma}+ o(1))x}{\log x} + O(4^{(1+o(1))\frac{\sqrt{x}}{\log x}})$$

In the error term I can see that we are using the Prime Number Theorem, but i don't see how we get the $1+o(1)$ or how to get the $o(1)$ in the main term

We start with $\#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = \lfloor{x}\rfloor - \sum_{i=1}^{r}\lfloor{\frac{x}{p_{i}}\rfloor}\pm\dots$ by an inclusion-exclusion argument.

We have the estimate that $\lfloor{x}\rfloor = x + O(1).$ Therefore we obtain $\#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = x \prod_{p \leq \sqrt{x}}\Big(1 - \frac{1}{p}\Big).$

Using Merten's theorem that for $z \geq 2$ we have $\prod_{p \leq z}\Big(1 - \frac{1}{p}\Big) = \frac{e^{- \gamma}}{\log z}\Big(1 + O\Big(\frac{1}{\log z}\Big)\Big),$ gives

$$ \#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = \frac{xe^{- \gamma}}{\log{\sqrt{x}}}\Big(1 + O\Big(\frac{1}{\log{\sqrt{x}}}\Big)\Big) = \frac{2xe^{-\gamma}}{\log x}\Big(1 + O\Big(\frac{2}{\log x}\Big)\Big).$$

I can rewrite the inclusion-exclusion argument in terms of the Mobius function as is done in equation 1.1.6 (page 20), but then I don't see how we get the overall result.

It's mostly the asymptotic notation that I'm stuck on as I'm not too familiar with it yet, particularly using "little oh" notation inside of "big oh" notation.

Thanks.

I'm trying to arrive at estimate 1.17 (page 21) of Koukoulopoulos lecture notes [https://dms.umontreal.ca/~koukoulo/documents/notes/sievemethods.pdf]

$$\#\{n \leq x : p|n \Rightarrow p > \sqrt{x}\} = \frac{(2e^{- \gamma}+ o(1))x}{\log x} + O(4^{(1+o(1))\frac{\sqrt{x}}{\log x}})$$

We start with $\#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = \lfloor{x}\rfloor - \sum_{i=1}^{r}\lfloor{\frac{x}{p_{i}}\rfloor}\pm\dots$ by an inclusion-exclusion argument.

We have the estimate that $\lfloor{x}\rfloor = x + O(1).$ Therefore we obtain $\#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = x \prod_{p \leq \sqrt{x}}\Big(1 - \frac{1}{p}\Big).$

Using Merten's theorem that for $z \geq 2$ we have $\prod_{p \leq z}\Big(1 - \frac{1}{p}\Big) = \frac{e^{- \gamma}}{\log z}\Big(1 + O\Big(\frac{1}{\log z}\Big)\Big),$ gives

$$ \#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = \frac{xe^{- \gamma}}{\log{\sqrt{x}}}\Big(1 + O\Big(\frac{1}{\log{\sqrt{x}}}\Big)\Big) = \frac{2xe^{-\gamma}}{\log x}\Big(1 + O\Big(\frac{2}{\log x}\Big)\Big).$$

I can rewrite the inclusion-exclusion argument in terms of the Mobius function as is done in equation 1.1.6 (page 20), but then I don't see how we get the overall result.

It's mostly the asymptotic notation that I'm stuck on as I'm not too familiar with it yet, particularly using "little oh" notation inside of "big oh" notation.

Thanks.

I'm trying to arrive at estimate 1.17 (page 21) of Koukoulopoulos lecture notes [https://dms.umontreal.ca/~koukoulo/documents/notes/sievemethods.pdf]

$$\#\{n \leq x : p|n \Rightarrow p > \sqrt{x}\} = \frac{(2e^{- \gamma}+ o(1))x}{\log x} + O(4^{(1+o(1))\frac{\sqrt{x}}{\log x}})$$

In the error term I can see that we are using the Prime Number Theorem, but i don't see how we get the $1+o(1)$ or how to get the $o(1)$ in the main term

We start with $\#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = \lfloor{x}\rfloor - \sum_{i=1}^{r}\lfloor{\frac{x}{p_{i}}\rfloor}\pm\dots$ by an inclusion-exclusion argument.

We have the estimate that $\lfloor{x}\rfloor = x + O(1).$ Therefore we obtain $\#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = x \prod_{p \leq \sqrt{x}}\Big(1 - \frac{1}{p}\Big).$

Using Merten's theorem that for $z \geq 2$ we have $\prod_{p \leq z}\Big(1 - \frac{1}{p}\Big) = \frac{e^{- \gamma}}{\log z}\Big(1 + O\Big(\frac{1}{\log z}\Big)\Big),$ gives

$$ \#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = \frac{xe^{- \gamma}}{\log{\sqrt{x}}}\Big(1 + O\Big(\frac{1}{\log{\sqrt{x}}}\Big)\Big) = \frac{2xe^{-\gamma}}{\log x}\Big(1 + O\Big(\frac{2}{\log x}\Big)\Big).$$

I can rewrite the inclusion-exclusion argument in terms of the Mobius function as is done in equation 1.1.6 (page 20), but then I don't see how we get the overall result.

It's mostly the asymptotic notation that I'm stuck on as I'm not too familiar with it yet, particularly using "little oh" notation inside of "big oh" notation.

Thanks.

Source Link

Prime counting function estimate sieve of Eratosthenes-Legendre

I'm trying to arrive at estimate 1.17 (page 21) of Koukoulopoulos lecture notes [https://dms.umontreal.ca/~koukoulo/documents/notes/sievemethods.pdf]

$$\#\{n \leq x : p|n \Rightarrow p > \sqrt{x}\} = \frac{(2e^{- \gamma}+ o(1))x}{\log x} + O(4^{(1+o(1))\frac{\sqrt{x}}{\log x}})$$

We start with $\#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = \lfloor{x}\rfloor - \sum_{i=1}^{r}\lfloor{\frac{x}{p_{i}}\rfloor}\pm\dots$ by an inclusion-exclusion argument.

We have the estimate that $\lfloor{x}\rfloor = x + O(1).$ Therefore we obtain $\#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = x \prod_{p \leq \sqrt{x}}\Big(1 - \frac{1}{p}\Big).$

Using Merten's theorem that for $z \geq 2$ we have $\prod_{p \leq z}\Big(1 - \frac{1}{p}\Big) = \frac{e^{- \gamma}}{\log z}\Big(1 + O\Big(\frac{1}{\log z}\Big)\Big),$ gives

$$ \#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = \frac{xe^{- \gamma}}{\log{\sqrt{x}}}\Big(1 + O\Big(\frac{1}{\log{\sqrt{x}}}\Big)\Big) = \frac{2xe^{-\gamma}}{\log x}\Big(1 + O\Big(\frac{2}{\log x}\Big)\Big).$$

I can rewrite the inclusion-exclusion argument in terms of the Mobius function as is done in equation 1.1.6 (page 20), but then I don't see how we get the overall result.

It's mostly the asymptotic notation that I'm stuck on as I'm not too familiar with it yet, particularly using "little oh" notation inside of "big oh" notation.

Thanks.