converting asymptotic little-oh into big-oh

Question

Let $f(n)$ be a random function such that $f(n)\cdot n^{1/4-\epsilon}\to 0$ for all $\epsilon>0$. Say we know that $f(n)\cdot n^{1/4}\not\to 0$. Does this imply that $f(n)=\tilde O(n^{-1/4})$?

(where the $\tilde{O}$ means up to log factors).

Answer 1

If $f(n)\cdot n^{1/4 - \varepsilon}\rightarrow 0$, then $f(n) \in o(n^{\varepsilon-1/4}) \subseteq O(n^{\varepsilon-1/4})$. If this is true for all $\varepsilon > 0$, then $$ f(n) \in \bigcap_{\varepsilon > 0} o(n^{\varepsilon - 1/4}). $$ Moreover, if $f(n)\cdot n^{1/4}\not\rightarrow 0,$ then $f(n)\not\in o(n^{-1/4})$, although it could still be in the larger class $O(n^{-1/4})$. So you know exactly this: $$ f(n)\in \bigcap_{\varepsilon > 0} o(n^{\varepsilon - 1/4}) \setminus o(n^{-1/4}). $$ Another way to say this is that $f(n)=n^{-1/4}g(n)$, where $g(n)$ grows more slowly than any polynomial, but does not converge to zero. Your (corrected) question is, does this imply that $$ f(n) \in \tilde{O}(n^{-1/4})=\bigcup_{k}O(n^{-1/4}\log^k n )\; ? $$ In other words, is it necessary that $g(n)$ grows more slowly than some power of $\log n$? Strictly speaking, the answer is no. There are functions that grow more slowly than any polynomial but more rapidly than any power of the logarithm; e.g., $g(n)=\exp(\sqrt{\log n})$. If $f(n) = n^{-1/4} g(n)$ for some such function, then it can fit between what you know and what you'd like to claim.