7
$\begingroup$

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

  • 0
    This was a fun question to answer. I liked it =)2011-12-07

2 Answers 2

6

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,

  • 0
    Patrick, the OP has the extra condition that $p_i < p_j$.2011-12-07
  • 0
    I think I'm finally done editing. Heh2011-12-07
  • 0
    Oh, thanks for the remark Aleks. Looks like I'm not done editing..2011-12-07
  • 0
    I was going to post as well and then I noticed the condition. I'm not sure the counting will work as well for that situation.2011-12-07
  • 0
    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$. Are you convinced? (The $1$'s and $2$'s are not exponents, they're superscripts.) I think this is pertinent to my answer so I'll add it.2011-12-07
  • 0
    I was just thinking how there are $\pi(x)$ primes less than or equal to $x$ and that there are $\pi(x)(\pi(x)-1)/2$ pairs of such primes $p_i < p_j$. This number is roughly $x^2/\log(x)^2$ which I think is of strictly higher order than $x$.2011-12-07
  • 2
    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$.2011-12-07
  • 0
    @Patick: When you write $\sum_{p_ip_j} \frac{1}{p_ip_j}$ do not forget that $p_ip_j\leq x$, since this series does not converge. Also here is a fun problem for you: Can you give a nicer formula for $\sum_{p_1p_2\leq x}\frac{1}{p_1p_2}$? The first term is $(\log \log x)^2$ but what is next?2011-12-09
  • 0
    @Eric : Actually that's just a typo, the $ \le x$ thing. Man, I'm not into "terms of asymptotic things", you know that.2011-12-09
  • 1
    @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.2011-12-09
0

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$.

  • 0
    Why does $n$ still appear in the error term? Also note that $x$ might be a real number, not an integer.2011-12-07
  • 0
    Good question but. The dot is usually used to separate two different statements.2011-12-08
  • 0
    XD Haha. Nice. I thought it was just a weird way of multiplying stuff, sorry for that one.2011-12-08
  • 0
    This is not completely correct, rather $\pi_2(x)\sim \frac{x}{\log x}\log\log x.$2011-12-09