The statements $f(n) = O(n^{\epsilon})$ for all $\epsilon > 0$ and $f(n) = n^{o(1)}$.

Question

Consider the statements \begin{align} \tag{A} f(n) &= O(n^{\epsilon}) \text{ for all } \epsilon > 0 \\ \tag{B} f(n) &= n^{o(1)} \end{align}

Questions:

1. It's clear that (B) implies (A). Does (A) imply (B)?

2. If the answer to the first question is no, is there a more brief way to write (A)?

Answer 1

Consider the statements \begin{align} \tag{$A$} f(n) &= O(n^{\epsilon}) \text{ for all } \epsilon > 0 \\ \tag{$B$} f(n) &= n^{o(1)} \\ \tag{$C$} f(n) &= o(n^{\epsilon}) \text{ for all } \epsilon > 0 \end{align} These statements are equivalent to each other.

To see this, we first rewrite the statements by unwrapping their definitions and taking logarithms. \begin{align} \tag{$A$} \forall \epsilon > 0 \,\, \exists c > 0 \,\, \exists N \,\, \forall n \geq N : \,\, \frac{\log f(n)}{\log n} &\leq \epsilon + \frac{\log c}{\log n} \\ \tag{$B$} \forall \epsilon > 0 \,\, \exists N \,\, \forall n \geq N : \,\, \frac{\log f(n)}{\log n} &\leq \epsilon \\ \tag{$C$} \forall \epsilon > 0 \,\, \forall \eta > 0 \,\, \exists N \,\, \forall n \geq N : \,\, \frac{\log f(n)}{\log n} &\leq \epsilon + \frac{\log \eta}{\log n} \end{align}

Now we show that $(A) \Leftrightarrow (B) \Leftrightarrow (C)$ by proving (i.e., sketching the proofs of) all the pairwise implications.

$(A) \Rightarrow (B)$: Let $\epsilon^{\prime} > 0$ be given. Put $\epsilon = \epsilon^{\prime}/2$. Write down $(A)$ with this choice of $\epsilon$. Take $N^{\prime} \geq N$ large enough that $$ \frac{\log c}{\log n} \leq \frac{\epsilon^{\prime}}{2} \text{ for all } n \geq N^{\prime}. $$ This gives (a primed version of) $(B)$.

$(B) \Rightarrow (A)$: $(B)$ implies $(A)$ with $c=1$

$(A) \Rightarrow (C)$: Let $\epsilon^{\prime} > 0$ and $\eta^{\prime} > 0$ be given. Put $\epsilon = \epsilon^{\prime}/2$. Write down $(A)$ with this choice of $\epsilon$. Take $N^{\prime} \geq N$ large enough that $$ \frac{\log c}{\log n} \leq \frac{\epsilon^{\prime}}{4} \leq \frac{\epsilon^{\prime}}{2} + \frac{\log \eta^{\prime}}{\log n} \text{ for all } n \geq N^{\prime}. $$ This gives (a primed version of) $(C)$.

$(C) \Rightarrow (A)$: Clear.

$(B) \Rightarrow (C)$: Let $\epsilon^{\prime} > 0$ and $\eta^{\prime} > 0$ be given. Put $\epsilon = \epsilon^{\prime}/2$. Write down $(B)$ with this choice of $\epsilon$. Take $N^{\prime} \geq N$ large enough that $$ 0 \leq \frac{\epsilon^{\prime}}{2} + \frac{\log \eta^{\prime}}{\log n} \text{ for all } n \geq N^{\prime}. $$ This gives (a primed version of) $(C)$.

$(C) \Rightarrow (B)$: Write down $(C)$ with $\eta=1$.