Let $\pi_2(x)=\#\{n\leq x:n=p_1p_2\}$, where $p_1$ and $p_2$ are two distinct primes. I was told to prove that $$ \pi_2(x)=\sum_{p\leq \sqrt{x}}\pi\left ( \frac{x}{p} \right )+O\left ( \frac{x}{(\log x)^2} \right )\tag{1} $$ using the hints $\pi_2(x)=\sum_{p_1\leq \sqrt{x}}\sum_{p_1< p_2\leq x/p_1} 1$ and $\pi(x)=O(x/\log x) $.

The second hint comes from PNT. I tried to prove the first hint myself. Unfortunately I am not familiar with this kind of rewriting the summation signs. Suppose WLOG that $p_1<p_2$. Then $p_1^2<p_1p_2\leq x$, which implies that $p_1< \sqrt{x}$ and $p_1<p_2\leq x/p_1$. Looking at the hint, one index has $p_1\leq \sqrt{x}$ instead of $p_1<\sqrt{x}$. Is there something I misunderstand, or how do I fix this?

I see that $\sum_{p_1< p_2\leq x/p_1} 1=\pi(x/p_1)$, if I am not mistaken, but I do not know where the error term comes from.


It doesn't matter whether we use the strict inequality $p_1 < \sqrt{x}$ or the non-strict $p_1 \leqslant \sqrt{x}$. If $x$ is not the square of a prime, then both inequalities give the same range of primes for the outer sum. If $x = p^2$ for a prime $p$, then the outer sum includes $p$ with the non-strict inequality, but not with the strict inequality. However, in that case we have $p = \frac{x}{p}$, and the range of the inner sum, $p < p_2 \leqslant \frac{x}{p}$ is empty, hence the inner sum is $0$. So both ways give the same sum.

We get the formula by grouping the $n \leqslant x$ that are the product of two different primes by their smaller prime factor. For fixed $p_1 \leqslant \sqrt{x}$, the map $q \mapsto p_1\cdot q$ is a bijection between the set of primes that are greater than $p_1$ and not greater than $\frac{x}{p_1}$ and the set $\{ n \leqslant x : n = p_1p_2, p_1 < p_2\}$, so there are precisely

$$\pi\biggl(\frac{x}{p_1}\biggr) - \pi(p_1)$$

non-square semiprimes not exceeding $x$ whose smaller prime factor is $p_1$. Since the smallest prime factor of a composite $n$ never exceeds $\sqrt{n}$, every semiprime not exceeding $x$ has a prime factor $\leqslant \sqrt{x}$. This gives the formula

$$\pi_2(x) = \sum_{p_1 \leqslant \sqrt{x}} \sum_{p_1 < p_2 \leqslant x/p_1} 1 = \sum_{p_1 \leqslant \sqrt{x}} \Biggl(\pi\biggl(\frac{x}{p_1}\biggr) - \pi(p_1)\Biggr).$$

The error term is then

$$- \sum_{p\leqslant \sqrt{x}}\pi(p),$$

and you can estimate that using the prime number theorem. [It's good to know that if $p$ is the $k$-th prime, then $\pi(p) = k$, so the sum is of the form $1 + 2 + \dotsc + m$.]

  • $\begingroup$ I never knew about replacing the summation index through the bijection function. I tried googling about it, but found only this page 3 in the end. I don't really get about your explanation of the first hint. If I understand you correctly, you focused on the inner sum sign where $p_1\leq \sqrt{x}$ is fixed. The sets you gave look equal to me, $\{n\leq x: n=p_1p_2, p_1<p_2\}$ and $\{p_2:p_1<p_2\leq x/p_1\}$, don't they? Thanks for your time. $\endgroup$ – Hopeless Dec 18 '16 at 17:58
  • $\begingroup$ When we have a sum $\sum\limits_{x \in A} 1$, that is the number of elements of $A$. If we have a bijection $B \to A$, that is the same as the number of elements of $B$. We want to count the number of elements of $S(x) = \{ n \leqslant x : n = p_1 p_2, p_1 < p_2\}$. For that, we partition $S(x)$ into the subsets with the same smaller prime factor, for every prime $p$, let $S(x,p) = \{ n \leqslant x : n = pq, p < q\}$. Then $S(x)$ is the disjoint union of the $S(x,p)$, so $\operatorname{card} S(x) = \sum_p \operatorname{card} S(x,p)$. Now for $p > \sqrt{x}$ (already for $p\geqslant\sqrt{x}$) $\endgroup$ – Daniel Fischer Dec 18 '16 at 18:44
  • $\begingroup$ we have $S(x,p) = \varnothing$, so $$\operatorname{card} S(x) = \sum_{p \leqslant \sqrt{x}} \operatorname{card} S(x,p) = \sum_{p\leqslant \sqrt{x}} \sum_{n \in S(x,p)} 1.$$ We use the bijection $q \mapsto pq$ between $A(x,p) := \{ q : q \text{ prime}, p < q, pq \leqslant x\}$ and $S(x,p)$ to count the number of elements of $S(x,p)$. For the number of elements of $A(x,p)$, we know an easy expression: it's the number of primes $\leqslant x/p$ minus the number of primes $\leqslant p$, $\pi(x/p) - \pi(p)$. $\endgroup$ – Daniel Fischer Dec 18 '16 at 18:44
  • $\begingroup$ The two sets $\{ n \leq x : n = p_1p_2, p_1 < p_2\}$ and $\{p_2 : p_1 < p_2 \leq x/p_1\}$ aren't equal, the elements of the first set are composite numbers, and the elements of the second set are primes. But there is an obvious bijection between these sets (multiplication or division by $p_1$, depending on which direction), so these sets have the same number of elements, and for the purpose of counting elements, we can substitute one with the other. $\endgroup$ – Daniel Fischer Dec 18 '16 at 18:48
  • 1
    $\begingroup$ $$\sum_{p\leqslant \sqrt{x}} \pi(p) = \sum_{k = 1}^{\pi(\sqrt{x})} k = \frac{\pi(\sqrt{x})\bigl(\pi(\sqrt{x}) + 1\bigr)}{2}.$$ Now using the PNT, we have $$\frac{\pi(\sqrt{x})\bigl(\pi(\sqrt{x}) + 1\bigr)}{2} = \frac{1}{2} \bigl(\pi(\sqrt{x})^2 + \pi(\sqrt{x})\bigr) \approx \frac{1}{2}\Biggl(\biggl(\frac{\sqrt{x}}{\log \sqrt{x}}\biggr)^2 + \frac{\sqrt{x}}{\log \sqrt{x}}\Biggr) = 2\frac{x}{(\log x)^2} + \frac{\sqrt{x}}{\log x}.$$ $\endgroup$ – Daniel Fischer Dec 18 '16 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.