# On a double sum involving prime numbers

$$\sum_{i,j=1}^{\infty}\left[\frac{x}{p_ip_j}\right]=x\sum_{p_ip_j\leq x}\frac{1}{p_ip_j}+O(x),p_i< p_j$$ where $p_i$ is the $i$th prime, and "[ ]" represents the largest integer not exceeding...

I don't know how to deal with it. Could you give me a proof?

• This was a fun question to answer. I liked it =) – Patrick Da Silva Dec 7 '11 at 4:43

The sum on the left is $$\sum_{i,j=1}^{\infty} \left[ \frac x{p_i p_j} \right] = \sum_{p_i p_j \le x} \left[ \frac{x}{p_i p_j} \right]$$ because if $p_i p_j > x$ then the integer part is just $0$, hence you don't need to sum over infinitely many terms. It remains to see that there is $O(x)$ terms in that sum, since $$z = [z] + \{z\} \qquad \text{ with } \qquad \{z\} \le 1.$$ so that you can look at the sum on the left as the sum on your right + the remainders, which you will only need to "count" how many of them appear, since all the terms you will sum will be less than $1$. Hence showing that there is at most $O(x)$ terms in that sum shows that you can bound the remainder's sum by $O(x) \times 1 = O(x)$.

The number of terms in that sum is \begin{align*} \# \left\{ (p_i,p_j) \, | \, p_i p_j \le x, p_i < p_j \right\} &\le \, \# \left \{ n \, | \, n \text{ is composite }, n \le x \right \} \\ &= x - \pi(x) \\ &\sim x - \frac {x}{\log x} \\ &= O(x). \end{align*} (A rough bound though would just be $x$ and it would still be $O(x)$, I just thought I'd do a little better.)

(ADDED : Aleks was wondering why my inequality held, so I'll add the proof here. Call the set with the prime couples $A$ and the set with the composites $B$. The application which takes a couple $(p_i, p_j)$ with $p_i < p_j$ to their product $p_i p_j = n$ is injective, for if $p_i^1 p_j^1 = n_1 = n_2 = p_i^2 p_j^2$, since $p_i^k < p_j^k$ we must have $p_i^1 = p_i^2$ and $p_j^1 = p_j^2$. Since this application is injective, $\# A \le \# B$. )

This gives you \begin{align*} \sum_{i,j=1}^{\infty} \left[ \frac{x}{p_i p_j} \right] &= \sum_{p_i p_j \le x} \left[ \frac x{p_i p_j} \right]\\ &= \sum_{p_i p_j \le x} \left( \frac x{p_i p_j} - \left\{ \frac{x}{p_ip_j} \right\} \right)\\ &= x \left( \sum_{p_i p_j \le x} \frac 1{p_i p_j} \right) - \sum_{p_i p_j \le x} \left\{ \frac{x}{p_ip_j} \right\} \end{align*} and since the last sum contains $O(x)$ terms less than $1$, it is $O(x)$.

Hope that helps,

• Patrick, the OP has the extra condition that $p_i < p_j$. – Alexander Vlasev Dec 7 '11 at 3:23
• I think I'm finally done editing. Heh – Patrick Da Silva Dec 7 '11 at 3:33
• Oh, thanks for the remark Aleks. Looks like I'm not done editing.. – Patrick Da Silva Dec 7 '11 at 3:34
• Your formula is not right ; it goes more like $$\sum_{i=1}^{\pi(x)} \pi(x/p_i)$$ which is strictly less what you're looking for. You can't just sum it like you did ; $\pi$ is clearly not a linear function in $p_i$. – Patrick Da Silva Dec 7 '11 at 19:01
• @PatrickDaSilva: Ok ya, I forgot. It is cool though: $$\sum_{pq\leq x}\frac{1}{pq}=\left(\log\log x\right)^{2}+B_{1}^{2}-\frac{\pi^{2}}{6}+O\left(\frac{\log \log x}{\log x}\right),$$ where $B_1$ is Mertens Constant. – Eric Naslund Dec 9 '11 at 6:08

Since $\pi_2(x):=\#\{n \leq x:\omega(n)=2 \}\ll \frac{x}{(\log x)^2}(\log \log x)^2$, the error term is $\frac{x}{(\log x)^2}(\log \log x)^2=o(x).$ $\omega(n)$ denotes the number of primes dividing $n$.

• Why does $n$ still appear in the error term? Also note that $x$ might be a real number, not an integer. – Patrick Da Silva Dec 7 '11 at 19:03
• Good question but. The dot is usually used to separate two different statements. – Captain Darling Dec 8 '11 at 13:01
• XD Haha. Nice. I thought it was just a weird way of multiplying stuff, sorry for that one. – Patrick Da Silva Dec 8 '11 at 16:38
• This is not completely correct, rather $\pi_2(x)\sim \frac{x}{\log x}\log\log x.$ – Eric Naslund Dec 9 '11 at 5:36