Why is $O(x^{\alpha + \epsilon}) \neq O(x^{\alpha})$ if $\epsilon$ is arbitrarily small but greater than $0$?

46 Views Asked by At

There are several equivalent formulations of the Riemann hypotheses that utilize the big O notation. For example, it is known that $M(x) = O\left(x^{\frac12+\epsilon}\right)$ for all $\epsilon > 0$, where $M(x)$ is the Mertens function is equivalent to the Riemann hypothesis being true.

Since $\epsilon$ can be chosen arbitrarily small, I'm wondering why $O\left(x^{\frac12 + \epsilon}\right)$ is not the same thing as $O\left(x^{\frac12}\right)$?

Using the definition of $O$, we get that if $f(x)=O\left(x^{\frac12+\epsilon}\right)$, then that there is an $M$ such that $|f(x)| \leq M|x^{\frac12+\epsilon}|$ for some $x > x_0$.

Since $\epsilon$ can chosen arbitrarily small, why can't we take the limit of the right-hand side, so that $\lim_{\epsilon \to 0} M|x^{\frac12+\epsilon}| = M|x^{\frac12}|$, which would suggest that $O(x^{\frac12 + \epsilon}) = O(x^{\frac12})$?

1

There are 1 best solutions below

1
On BEST ANSWER

In this case, the burden of proof is really on you to prove that you can take the limit on the right hand side (you can't). In mathematics, we sometimes get so used to being able to 'take limits' that we forget that we can only do so in certain special cases - and that these special cases all require proof.

Here's an explicit counterexample for you. For simplicity, I'll show that $O(x^{1+\epsilon})$ for all $\epsilon>0$ does not imply $O(x)$. It should be fairly simple to replace $1$ by $\frac12$.

Let $f(x)=x\log(x)$. Clearly, $f(x)$ is not $O(x)$, since $\log(x)\to\infty$. We will show that $f(x)$ is $O(x^{1+\epsilon})$ as $x\to\infty$ for all $\epsilon>0$.

Indeed, we have $f(x)/x^{1+\epsilon}=x^{-\epsilon}\log(x)$. Since $\epsilon>0$, $x^{-\epsilon}\log(x)\to0$ as $x\to\infty$. Therefore, $f(x)$ is actually $o(x^{1+\epsilon})$ for $\epsilon>0$, so it is certainly $O(x^{1+\epsilon})$.


If instead we take $g(x)=\sqrt{x}\log(x)$ then $g(x)$ is $O\left(x^{\frac12+\epsilon}\right)$ for all $\epsilon>0$ but not $O\left(x^{\frac12}\right)$.


I'll try and explain why your argument doesn't work. It is true that $\lim_{\epsilon\to0}M\left|x^{\frac12+\epsilon}\right|=M\left|x^{\frac12}\right|$, but you are forgetting that $M$ may depend on $\epsilon$. In this case, $M(\epsilon)\to\infty$ as $\epsilon\to0$, such that we have $$ M(\epsilon)\left|x^{\frac12+\epsilon}\right|\to\infty $$ as $\epsilon\to0$.