2
$\begingroup$

I was wondering if the order between multiplication and little o can be exchanged, for example, $$x \times o(\frac{y}{x}) = o(y)?$$

I am a little confused.

In the example, I need to consider the case when $x$ goes to infinity, and don't know if eliminating $x$ will be a good idea. As far as I know, it is correct that $\lim_{x\rightarrow \infty} x \times o(\frac{y}{x}) =0$, but I can't get $\lim_{x\rightarrow \infty} o(y) =0$. So I think $$x \times o(\frac{y}{x}) = o(y)$$ is not true?

Added: My case is that given $x \times o_{t\rightarrow \infty}(t^2)$ and $t=\sqrt{y/x}$, so I get $x \times o_{y/x \rightarrow \infty}(y/x)$. Now with this meaning and my consideration when x goes to infinity, is $x \times o_{y/x \rightarrow \infty}(y/x)$ same as $o_{y \rightarrow \infty}(y)$ or as $o_{y/x \rightarrow \infty}(y)$? Is it right that $\lim_{x\rightarrow \infty} f(x,y)=0, \forall f \in x \times o(y/x)$?

Thanks!

  • 0
    @Qiaochu: See my update please.2011-05-16
  • 1
    Despite the use of equal signs with little $o$ notation, it's important to remember that $o(f(x))$ is actually a set.2011-05-16
  • 0
    As you can read between the lines of Qiaochu Yuan answer $\lim_{x\to\infty} o(y)$ has no meaning.2011-05-16
  • 0
    @AD: by $\lim_{x\rightarrow \infty} o(y) =0$, I mean $\lim_{x\rightarrow \infty} f =0, \forall f \in o(y)$2011-05-16

1 Answers 1

7

You have every right to be confused; little-o notation itself is problematic, and this question highlights at least two of its problems.

Let's be completely precise. We say that $f(x) \in o_{x \to \infty}(g(x))$ (note the subscript) if $\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0$. This is the most precise form of little-o notation: I have not used an equals sign (because $o(g(x))$ is not a function), I have specified what variable the notation refers to, and I have even specified what its limit is. (Most people who use little-o or related notations don't bother to do any of these things, and the result can be quite confusing if you aren't aware of the context.)

Thus $f(y) \in o_{y \to \infty}(y)$ if $\lim_{y \to \infty} \frac{f(y)}{y} = 0$. In this situation, we might want to interpret

$$f(x, y) \in x o_{x \to \infty} \left( \frac{y}{x} \right)$$

to mean that

$$\frac{f(x, y)}{x} \in o_{x \to \infty} \left( \frac{y}{x} \right)$$

where $y$ is possibly a function of $x$. This is equivalent, of course, to $\lim_{x \to \infty} \frac{f(x, y)}{y} = 0$, so it is equivalent to the statement that

$$f(x, y) \in o_{x \to \infty}(y).$$

But your question is a little confusing, because you have two variables $x$ and $y$ and you didn't specify which one of them the little-o notation refers to, and you also didn't refer to $f$. Both of these are weaknesses of little-o notation itself.

  • 0
    This is answer is correct, with a minor addition. As little $o$ notation is normally used, the statement $o(f(x)) = o(g(x))$ is taken to mean $o(f(x))\subset o(g(x))$; this is what you show above, proving the given "equality". Edit: I should specify that this is how it's normally used in algorithmic analysis, which is what $O$ notation is mostly for.2011-05-16
  • 0
    Really? That seems even more problematic.2011-05-16
  • 0
    @Qiaochu: Thank you! My case is that I have $x \times o_{t\rightarrow\infty}(t^2)$ and $t=\sqrt(y)/\sqrt(x)$, so I get $x \times o(y/x)$, where I don't know what is the proper subscript for $o$. Now with this meaning and my consideration when $x$ goes to infinity, is $x \times o(y/x)$ same as $o(y)$? Is it right that $\lim_{x\rightarrow\infty}x \times o(y/x) =0$?2011-05-16
  • 0
    @Jessie: I'm a little confused. You say that $t \to \infty$. How are $x$ and $y$ changing with respect to $t$? Is one of them fixed?2011-05-16
  • 0
    $x$ $y$ and $t$ are varying subject to $ t=\sqrt(y/x)$.2011-05-16
  • 0
    @Jessie: that last expression you've got there isn't particularly well-defined: I don't really know what it means to take the limit of a little-o expression. You need to be a little more careful about how you use it. But if I understand you correctly, then yes, it should still be true that you can replace $x o(y/x)$ by $o(y)$ in any valid use of little-o notation, regardless of what variable is going to infinity.2011-05-16
  • 0
    @Qiaochu: the last expression means that $\lim_{x\rightarrow \infty} f(x,y)=0, \forall f \in x \times o(y/x)$. If it is now clear, is it right or wrong? How about $\lim_{x\rightarrow \infty} f(y)=0, \forall f \in o(y)$?2011-05-16
  • 0
    @Jessie: it's still not clear. Is that little-o still referring to $t$? If it is, then you need to decide what order you're taking the limits in $x$ and in $t$. Can you just explain what situation prompted you to consider this?2011-05-16
  • 0
    @Qiaochu: The little o comes from a Taylor expansion and then there is variable substitution. I think all the little o are referring to $t$. See my update to my post.2011-05-16
  • 0
    *Let's be completely precise.* Sorry to say that you almost deliver but not quite... With your definition, it is impossible to prove that $x\sin(x)=o(x^2\sin(x))$ when $x\to+\infty$, for example. Compare with [this](http://math.stackexchange.com/questions/72412/big-and-small-o-notation-help/72421#72421).2011-10-23
  • 0
    @Didier: hmm. I'm not used to applying little-o notation to functions that aren't positive and monotonic, but according to Wikipedia it seems you're right. Would you like to post an answer correcting mine?2011-10-23
  • 0
    Thanks for the suggestion but I will not comply. One reason is that this is not the exact scope of the question here, another is that I already explained this stuff [there](http://math.stackexchange.com/questions/72412/big-and-small-o-notation-help/72421#72421). (Yes *I am right* and, frankly, I am surprised to see you refer to Wikipedia as the *arbitre des élégances* for such a matter. Even coming from somebody more into algebra than analysis (whatever that means), this is akin to discussing whether the center of a group is always a distinguished subgroup or not, and turning to WP to decide.)2011-10-23