0

I don't understand what is meant by the following use of little-oh.

The most obvious method to find small prime divisors of $n$ is trial division: divide $n$ by $2, 3, 5,$ etc. This takes time $y^{1 + o(1)}$ if $n$ has $y^{o(1)}$ bits. (Daniel J. Bernstein. "How to find small factors of integers." Page 2.

Here's my attempt at reading this.

Suppose $f \in o(1)$. By definition, for any $c > 0$, there's a natural number $n_0$ such that for any $n \geq n_0$, $0 \leq f < c \times 1 = c.$ (AFAIK, $c$ is a real number.) That seems to imply that $f = 0$ because that's the only thing that could be less than any $c > 0$, but that's surely not what the author is saying in his paper. What am I missing here? How should I read it? Thank you.

T. Ingram
  • 29
  • The notation $f = o(1)$ means that $\lim_{n \to \infty} {f(n) \over 1} = 0$. You've swapped the quantors: it should be "for any $c>0$ there exists $n_0$ such that for any $n > n_0$, $f(n) < c$". – Artur Riazanov Dec 18 '17 at 00:55
  • Fixed the quantifiers. Thanks. Regarding your definition, it seems equivalent to mine, is it not? – T. Ingram Dec 18 '17 at 01:18
  • @T.Ingram it is equivalent. "That seems to imply that $f=0$ because that's..." That reasoning is incorrect. The assertion is that $f(n) < c$ for all $n\geq n_0$. For instance, $f(n) = 1/n \in o(1)$, because for any $c>0$, picking some $n_0 > 1/c$, then $$f(n) = \frac{1}{n} \leq \frac{1}{n_0} < c$$ for all $n\geq n_0$. – adfriedman Dec 18 '17 at 20:09
  • Maybe I got carried away because $1/n$ goes to zero as $n$ grows larger, but it doesn't mean it's zero for all $n$. Reinterpreting the paper citation then it seems to me he's saying to find a small factor of $n$ it takes time $y \times b$ where $b$ is the number of bits of the integer to be factored. For instance, if $y = 2$, then the number of operations it takes to find a small factor of $n$ is the double of the number of bits in $n$. Is that correct? My scratch paper: $y^{1 + o(1)} = y y^{o(1)}$. – T. Ingram Dec 18 '17 at 20:49

0 Answers0