Skip to main content

Section 5.3 A more general Sieve

For convenience suppose \(x\) is an integer and write

\begin{equation*} S(y):=\sum_{n\leq y}f(n), \end{equation*}

for \(1\leq y\leq x.\) If \(y\lt 1,\) we use the convention that \(S(y)=0.\) Then

\begin{align*} \sum_{n\leq x}f(n)g(n) \amp=\sum_{n\leq x}g(n)(S(n)-S(n-1))\\ \amp =g(x)S(x)-\sum_{n\leq x-1}S(n)(g(n+1)-g(n))\\ \amp =g(x)S(x)-\sum_{n\leq x-1}S(n)\int_{n}^{n+1}g'(t)dt\\ \amp =g(x)S(x)-\int_{1}^{x}S(t)g'(t)dt \end{align*}

which is the desired result.

It is common for us to apply partial summation to partial sums of reciprocal sums. In fact, if we use the prime number theorem in the-form

\begin{equation*} \pi(x)=\frac{x}{\log(x)}+O\left(\frac{x}{\log^2(x)}\right), \end{equation*}

we can show the following result.

Set \(g(x)=\dfrac{1}{x},\) and

\begin{equation*} f(n)= \begin{cases} 1 \amp \hspace{2mm} if \hspace{2mm} n \hspace{2mm} is \hspace{2mm} prime \\ 0 \amp \hspace{2mm} if \hspace{2mm} n \hspace{2mm} is \hspace{2mm} not \hspace{2mm} prime \end{cases} \end{equation*}

Applying partial summation, we have that

\begin{equation*} \sum_{p\leq x}\frac{1}{p}=\frac{\pi(x)}{x}+\int_2^x\frac{\pi(t)}{t^2}dt. \end{equation*}

Since all of the functions are non-negative in the above, we can substitute with Chebyshev's estimates the asymptotic order relation

\begin{equation*} \pi(x)\asymp\frac{x}{\log(x)}, \end{equation*}

to give

\begin{equation*} \sum_{p\leq x}\frac{1}{p}\asymp \frac{1}{\log(x)}+\int_2^x\frac{1}{t\log(t)}dt. \end{equation*}

Using integration by parts we set \(u = \log(t)\) so that \(du =\dfrac{1}{t}dt,\) and so

\begin{align*} \sum_{p\leq x}\frac{1}{p} \amp\asymp \int_2^x \frac{1}{t\log(t)}dt+O\left(\frac{1}{\log(x)}\right)\\ \amp\asymp \int_{\log(2)}^{\log(x)} \frac{1}{u}du+O\left(\frac{1}{\log(x)}\right)\\ \amp\asymp \log(\log(x))+O\left(\frac{1}{\log(x)}\right), \end{align*}

which gives the result.

Note that using a stronger version of the prime number theorem one can show that there is a real constant \(C\) so that

\begin{equation*} \sum_{p\leq x}\frac{1}{p}=\log(\log(x))+C+O\left(\frac{1}{\log(x)}\right). \end{equation*}

We will use this stronger version in what follows.

The following discussion of \(B\)-smooth numbers is taken from the paper Smooth numbers and the quadratic sieve (2008) by Carl Pomerance.

Definition 5.3.3.

Denote by \(\varphi(x, B)\) the counting function of the \(B\)-smooth numbers in the interval \([1, x].\) That is,

\begin{equation*} \varphi(x,B)=\# \{m\in[1,X]: \hspace{2mm} \mathrm{if} \hspace{2mm} p\vert m \hspace{2mm} \mathrm{then} \hspace{2mm} p\leq B\}. \end{equation*}

We will use a very simple sieve to estimate \(\varphi(x, x^{1/2}).\) The sieve will be the principle of inclusion-exclusion, with a single exclusion, since no number up to \(x\) is divisible by two primes that are larger than \(x^{1/2}.\) Thus

\begin{equation*} \varphi(x,x^{1/2})=\lfloor x\rfloor-\sum_{\sqrt{x}\lt p\leq x}\left\lfloor\frac{x}{p}\right\rfloor. \end{equation*}

This identity uses the fact that there are exactly \(\lfloor\frac{x}{p}\rfloor\) multiples of \(p\) in the interval \([1, x],\) and since the multiples of \(p\) are not \(x^{1/2}\)-smooth they must be excluded. We can use the identity

\begin{equation*} \lfloor x \rfloor=x-\{x\}, \end{equation*}

where \(\{x\}\) is the fractional part, to give

\begin{align*} \varphi(x,x^{1/2})\amp =\lfloor x\rfloor-\sum_{\sqrt{x}\lt p\leq x}\left\lfloor\frac{x}{p}\right\rfloor\\ \amp =x-\{x\}-\sum_{\sqrt{x}\lt p\leq x}\left(\frac{x}{p}-\left\{\frac{x}{p}\right\}\right)\\ \amp =x-\sum_{\sqrt{x}\lt p\leq x}\frac{x}{p}+O(\pi(x)-\pi(x^{1/2}))\\ \amp =x\left(1-\sum_{\sqrt{x}\lt p\leq x}\frac{1}{p}\right)+O\left(\frac{x}{\log(x)}\right) \end{align*}

Now using the previous theorem, we have

\begin{align*} \sum_{\sqrt{x}\lt p\leq x}\frac{1}{p}\amp =\sum_{p\leq x}\frac{1}{p}-\sum_{p\leq x^{1/2}}\frac{1}{p}\\ \amp =\log(\log(x))-\log(\log(\sqrt{x}))+O\left(\frac{1}{\log(\sqrt(x))}\right)\\ \amp =\log(2)+O\left(\frac{1}{\log(\sqrt(x))}\right). \end{align*}

Thus we finally gain

\begin{equation*} \varphi(x,x^{1/2})=(1-\log(2))x+O\left(\frac{x}{\log(x)}\right), \end{equation*}

so that

\begin{equation*} \frac{\varphi(x,x^{1/2})}{x}\approx 1-\log(2) \end{equation*}

as \(x\rightarrow\infty.\) Since \(1-\log(2) \cong .3069\) we have shown that about \(30\%\) of all numbers have no prime factors above their square root.