2

Let $a_n$ and $b_n$ be two sequences. I'm trying to understand the difference between $a_n = o(b_n)$ and $a_n \ll b_n$.

$a_n = o(b_n)$ as $n \to \infty$ if $a_n/b_n \to 0.$

$a_n \ll b_n$ if $a_n \ge 0$ and $a_n = o(b_n).$

What is the importance of the requirement that $a_n$ be nonnegative in the second definition?

theQman
  • 1,097
  • 1
    I don’t think your second definition is correct. Certainly it is not how $\ll$ is used in my field. – Clayton Nov 01 '18 at 16:56

2 Answers2

1

Little-oh notation just checks that $a_n$ grows at a slower rate than $b_n$. For instance, $a_n = -n$ and $b_n = n^2$, then $a_n = o(b_n)$. The $a_n \geq 0$ is supposed to mean that $b_n$ eventually is greater than $a_n$. Here, "greater than" refers to the total order on the sequence's values, which is not mentioned in the first definition.

Still, that definition seems incomplete to me. We wouldn't intuitively say $a_n \ll b_n$ if $a_n = n$ and $b_n = -n^2$, yet that fulfills the given definition for "$\ll$".

Larry B.
  • 3,384
  • Thank you. I just noticed a footnote in my book mentioning that "we assume $b_n>0$ for sufficiently large $n$. Does this remedy the situation? – theQman Nov 01 '18 at 17:14
  • If we implicitly accept that $a_n \ll b_n$ qualifies the $n$ as "sufficiently large", then sure. It's uncomfortable leaving so much as unspoken background context, though. – Larry B. Nov 01 '18 at 18:17
1

The standard definition of $a_n\ll b_n$ is equivalent to $a_n=O(b_n)$. That is, $|a_n|\leq C|b_n|$ for some constant $C>0$ and all sufficiently large $n$. So, for example, if we put $a_n=n\sin n$, we have $a_n\ll n$ since $|a_n|\leq 1\cdot n$, but we don't have $a_n=o(n)$.

Clayton
  • 24,751
  • This may be the standard definition in some fields (at a guess: number theory?), but I do want to comment that $\ll$ does traditionally correspond to $o$ and not $O$ in extremal combinatorics and the theory of random graphs, as I've seen it used. – Misha Lavrov Mar 06 '19 at 18:34
  • @MishaLavrov: Interesting. Certainly the notation has been around at least since Davenport's book Multiplicative Number Theory and Titchmarsh's book The Theory of the Riemann Zeta Function. In fact, I think I have a book that attributes it back to Landau using it this way. Certainly neither of the books I mention are new, so I wonder when the meaning of the notation changed. (Of course, I'm not familiar with extremal combinatorics or the theory of random graphs). – Clayton Mar 06 '19 at 19:15
  • 1
    Alon & Spencer's Probabilistic Method uses $\ll$ for $o(b_n)$, and it might be almost as old as Davenport's book. I guess graph theorists and number theorists just don't go to each other's talks enough! – Misha Lavrov Mar 06 '19 at 20:17
  • (Actually, no, checking carefully Alon & Spencer's book is 19 years newer. Bollobas's Random Graphs would definitely have settled the issue but as far as I can tell he doesn't use $\ll$ at all...) – Misha Lavrov Mar 06 '19 at 23:11
  • @MishaLavrov Well, at any rate, I suppose your latter statement remains true haha; I'll have to make it a point to attend some seminars. – Clayton Mar 06 '19 at 23:55