I simply found an asymptotic relation for $\sum_{n\le x}\mu(n)o(\frac xn)$ like below:

$$\sum_{n\le x}\mu(n)o(\frac xn)=o(x\sum_{n\le x}\frac 1n)=o (x\log x) $$

But Basil Gordon, an American mathematician, in his thesis found that like below:

$$\sum_{n\le x}\mu (n)o (\frac xn)=\sum_{n\le\frac x{\log x}}\mu (n)o (\frac xn)+\sum_{\frac x{\log x}\le n \le x}\mu (n)O (\frac xn) $$

Then since $|\mu (n)|\le 1$

$$o (\sum_{n\le\frac x{\log x}}\frac xn)=o (x\log x) $$


$$O (\sum_{\frac x {\log x}\le n\le x}\frac xn)=O (x\log x-x\log\frac x{\log x})=O (x\log\log x)=o (x\log x) $$

Could anyone explain for me why Basil Gordon has done that like this? Is my answer wrong?

  • $\begingroup$ Big-oh of $x\log\log x$ is sharper than little-oh of $x\log x$. $\endgroup$ – Gerry Myerson Jun 28 at 12:51
  • $\begingroup$ @Gerry Myerson My question is when we can arrive to $o (x\log x) $ by a short proof, why Basil Gordon arrived to $o(x\log x) $ by a long proof? $\endgroup$ – user678879 Jun 28 at 17:36
  • $\begingroup$ How do you justify $\sum_{n\le x}\mu(n)o(\frac xn)=o(x\sum_{n\le x}\frac1n)$ $\endgroup$ – reuns Jun 28 at 17:49
  • $\begingroup$ @reuns Since $|\mu (n)|\le 1$ it follows from $o (f)+o (g)=o (f+g) $. $\endgroup$ – user678879 Jun 28 at 17:52
  • $\begingroup$ No. $\sum_{n \le x} \mu(n) o(1/n^2) = O(\sum_{n \le x} 1/n^2)=O(1)$ not $o(1)$. $\endgroup$ – reuns Jun 28 at 17:53

Use small o notation with a special care on which variable goes to infinity. What you said is basically the following.

Claim(?): Let $f(n,x)$ be a function in $n$ and $x$. Suppose $\lim \frac{f(n,x)}{x/n} = 0$. Then we have $\lim \frac{\sum_{n\leq x} f(n,x)}{\sum_{n \leq x} x/n} = 0$.

Is this claim true? It depends on context (so I intentionally omit how the limit goes). What you wrote in your question, you interpreted small o notation by $\lim_{n\leq x, x\rightarrow\infty} f(n,x) = 0 $ uniformly in $n\leq x$.

I haven't looked into his thesis, but based on what was written, I assume what the author meant by the formula $o(x/n)$ is any function of the form $\phi(x/n)$ where $\phi$ is a function which satisfies $\lim_{u\rightarrow \infty} \phi(u) / u = 0$. (or, $o(x/n)$ uniformly as $x/n \rightarrow \infty$). What makes you more confusing is that, in the last formula $o(x log x)$, his limit was taken as $x \rightarrow \infty$. So it is indeed the same notation with different meaning from line to line. So, I'll write $o_{x/n}$ to denote the former and $o_x$ for the latter. Then your interpretation is $$ \sum_{n\leq x} o_x \left ( \frac{x}{n} \right ) = x o_x \left (\sum_{n\leq x} \frac{1}{n} \right ) = o_x (x \log x),$$ which is obviously true. I believe the author's intention was $$ \sum_{n\leq x} o_{x/n} (x/n) = o_x ( x \log x),$$ which is not automatic(for instance, when $x/2\leq n\leq x$, $x/n$ is bounded so we don't know if it is $o_x(1)$. Thus the author goes in two steps to handle this.

What reuns said I believe is that $\sum_{n\leq x} o_n (1/n^2) \neq o_x(1)$. So it all depends on the context after all.


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.