I'm going to be clear about definitions before I start so there's no ambiguity. Let D be a subset of the complex numbers and let $f: D \to \mathbb{R}^{+}$ be a positive real-valued map defined on D. We will write $f(x) = O(g(x))$ if $g: D \to \mathbb{R}^{+}$ and there exists a positive constant A such that:

$\displaystyle |f(x)| \leq Ag(x)$

for all x in D. If we have that $f(x) = O(g(x))$ and $g(x) = O(f(x))$, then we write $f(x) \asymp g(x)$. If D is unbounded (like the naturals or non-negative reals) then we will also write $f(x) \sim g(x)$ to mean:

$\displaystyle \lim_{|x| \to \infty} \frac{f(x)}{g(x)} = 1.$

The point of all this: I've occasionally used in proofs the intuition that $f(x) \sim g(x)$ implies $f(x) \asymp g(x)$, though the converse is definitely false. I've set about trying to convince myself with a proof, but I've only got as far as proving it for $D = \mathbb{N}$, and even putting D as the non-negative reals gets me close but not quite there. Any ideas?

  • $\begingroup$ I don't understand why f has to be complex-valued and g has to be positive real-valued, especially if you're going to use them symmetrically. $\endgroup$ – Thierry Zell Jan 11 '11 at 14:34
  • $\begingroup$ This is true, thanks for mentioning that. I used definitions from a textbook to avoid mistakes, but for my question we may just as well define with both f and g positive real-valued. $\endgroup$ – Sputnik Jan 11 '11 at 14:38
  • $\begingroup$ The other problem that I see is the use of $x \to \infty$ . If D is a subset of the reals, it seems fairly unambiguous; not so if it is a subset of the complexes (there are several different ways you can go to infinity in the complex plane, and they can give different limits). $\endgroup$ – Thierry Zell Jan 11 '11 at 14:49
  • $\begingroup$ A assume that by $\lim_{x\rightarrow\infty}$ you mean $\lim_{|x|\rightarrow\infty}$? In any case, the claim is false: $f(x)$ could blow up at 0, say. $\endgroup$ – Alex B. Jan 11 '11 at 14:52
  • $\begingroup$ Sorry, yes it should be $lim_{|x| \to \infty}$. $\endgroup$ – Sputnik Jan 11 '11 at 15:04

The result is false if $D$ is not closed: take a boundary point $a\not\in D$ and let $f(x)=|x-a|$ and $g(x)=1+f(x)$.

If $D$ is closed, it is true. There is some $R>0$ so that $\tfrac12 f(x) < g(x) < 2f(x)$ whenever $|x| > R$. On the other hand, on the compact set $\{x\in D\colon |x|\le R\}$ there are bounds $0 < m \le f(x) \le M$ and $0 < m \le g(x) \le M$. The result $f(x)\asymp g(x)$ follows immediately.

| cite | improve this answer | |
  • 3
    $\begingroup$ I assume, of course, that the functions are continuous. Otherwise, anything can happen. $\endgroup$ – Harald Hanche-Olsen Jan 11 '11 at 14:54
  • $\begingroup$ Wonderful, thanks :). This sheds a lot more light on it, and shows me where I need to tighten up conditions. $\endgroup$ – Sputnik Jan 11 '11 at 15:12
  • 4
    $\begingroup$ Though ordinarily $f(x)=O(g(x))$ and $f(x)\asymp g(x)$ are defined so that the condition need only hold for sufficiently large x... $\endgroup$ – Harry Altman Jan 11 '11 at 21:21

My version would be this: $f(x) \sim g(x) \Longrightarrow f(x) \asymp g(x)$ is TRUE with the usual definitions, which differ from what we see above. Suppose $f, g$ are positive functions on $\mathbb R$. I want to write $$ f(x) = O(g(x)) \text{ as } x \to \infty $$ iff $$ \limsup_{x \to \infty} \frac{f(x)}{g(x)} < \infty , $$ then write $f(x) \asymp g(x)$ iff $f(x) = O(g(x))$ and $g(x) = O(f(x))$, which is to say $$ 0 < \liminf_{x\to\infty} \frac{f(x)}{g(x)} \le \limsup_{x \to \infty} \frac{f(x)}{g(x)} < \infty . $$ With THIS definition, it is a consequence of $f(x) \sim g(x)$ with the stated definition: $$ \lim_{x\to\infty} \frac{f(x)}{g(x)} = 1. $$

| cite | improve this answer | |
  • $\begingroup$ Thank you for this alternative. This may be off-topic, but it is implicit in your definition that $\displaystyle \limsup_{x \to \infty} \frac{g(x)}{f(x)} = \left( \liminf_{x \to \infty} \frac{f(x)}{g(x)} \right)^{-1}$. Could you perhaps explain where that comes from? $\endgroup$ – Sputnik Jan 15 '11 at 12:11
  • $\begingroup$ $x \mapsto 1/x$ reverses order in the positive reals. $\endgroup$ – Gerald Edgar Jan 15 '11 at 13:55

If $f$ and $g$ are functions $\mathbb{R} \rightarrow \mathbb{R}$, it is common to write $f(x) = O(g(x))$, or $f(x) \ll g(x)$, to mean that $|f(x)| \leq A g(x)$ for sufficiently large $x$. For example, one might see

$$\pi(x; q, a) \gg \frac{x}{\phi(q) \log(x)},$$

where the left hand side is the number of primes $\leq x$ congruent to $a$ modulo $q$. I don't think any analytic number theorist would hesitate to write this (if $(a, q) = 1$), even though the left side is zero for $x < a$.

In other words, at least in the part of mathematics I'm familiar with, the claim you make is true, even if the functions are not continuous, if you implicitly assume that you are allowed to choose $D$ to avoid any trouble spots.

| cite | improve this answer | |
  • 1
    $\begingroup$ equivalent? if $\lim f(x)/g(x) = 2$, then $f(x) \asymp g(x)$ but not $f(x) \sim g(x)$. $\endgroup$ – Gerald Edgar Jan 11 '11 at 20:32
  • $\begingroup$ Oops, that is not what I meant to say. Edited my answer, thanks. $\endgroup$ – Frank Thorne Jan 11 '11 at 21:37
  • $\begingroup$ That is odd. I always thought the $\ll$ notation implied little oh. $\endgroup$ – Harald Hanche-Olsen Jan 11 '11 at 22:29
  • $\begingroup$ Harald -- I have seen this before actually! (Before I started grad school and took a grad class in applied math). In analytic number theory $\ll$ is universally big-O, but I guess this is not necessarily universal across fields. $\endgroup$ – Frank Thorne Jan 12 '11 at 6:20
  • 1
    $\begingroup$ Thanks for this; it's very much in the vein of the kind of work I'm doing. I heartily agree that it makes sense in number theory to take the definition for sufficiently large $x$, but on several occasions I've seen authors use the stronger condition above. (In particular, in some lecture notes by Heath-Brown which I've been using for my dissertation, and a sieve methods monograph by Ram Murty.) I wanted to see what was necessary to make the intuition '$\sim$ implies $\asymp$' hold in the stronger case. $\endgroup$ – Sputnik Jan 15 '11 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.