$$\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?

  • $\begingroup$ This was a fun question to answer. I liked it =) $\endgroup$ – 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,

  • $\begingroup$ Patrick, the OP has the extra condition that $p_i < p_j$. $\endgroup$ – Alexander Vlasev Dec 7 '11 at 3:23
  • $\begingroup$ I think I'm finally done editing. Heh $\endgroup$ – Patrick Da Silva Dec 7 '11 at 3:33
  • $\begingroup$ Oh, thanks for the remark Aleks. Looks like I'm not done editing.. $\endgroup$ – Patrick Da Silva Dec 7 '11 at 3:34
  • 2
    $\begingroup$ 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$. $\endgroup$ – Patrick Da Silva Dec 7 '11 at 19:01
  • 1
    $\begingroup$ @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. $\endgroup$ – 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$.

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

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.