converting asymptotic little-oh into big-oh 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).
 A: 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.
