$\sim$ symbol in asymptotic analysis

Question

I would like to know what is the actual meaning of the $\sim$ symbol in asymptotic analysis. Specifically wherever I look it seems to mean the following: $$\lim\limits_{n\to \infty}\dfrac{f(n)}{g(n)} = 1$$

But if one looks at this question there are people that use the symbol to mean $$\lim\limits_{n\to \infty}\dfrac{f(n)}{g(n)} = C$$ for some constant $C$. I assume this second case is something that big-theta $\Theta$ would be better used for than tilde $\sim$.

I am looking for a solid reference where I could see the usage of tilde symbol as presented in the second case.

Answer 1

I found the notation you're asking for. From this and the various other known interpretations*, it should be clear that "the actual meaning of the $\sim$ symbol", even when dealing with asymptotic results, does not exist. Rather, like many notations, it is a convention that depends on the author. I'd guess one reason is that although "asymptotic analysis" is arguably its own field, its results are particularly suited to being applied in other fields, and of course different fields want different things from their notation.

* I mean of course the much more common notation $a_n\sim b_n \iff a_n/b_n\to 1$, readily found in Wikipedia and sources therein, although even this has minor variants.

1 $a\sim b$ in the sense of the linked question's answer Relation between $m$th Fibonacci number and Golden Ratio

This can be found in the following 2015 book "Stochastic Partial Differential Equations" by Sergey V. Lototsky and Boris L. Rozovsky, page 2 (Springerlink)(Google Books Preview):

Notation $a_{k} \sim b_{k}$ means $\lim _{k \rightarrow \infty} a_{k} / b_{k}=c \in(0, \infty),$ and if $c=1,$ we will emphasize it by writing $a_{k} \simeq b_{k} .$ Notation $a_{k} \asymp b_{k}$ means $0<c_{1} \leq a_{k} / b_{k} \leq c_{2}<$ $\infty$ for all sufficiently larger $k .$ The same notations $\sim, \simeq,$ and $\asymp$ can be used for functions. For example, as $x \rightarrow \infty,$ we have $$ 2 x^{2}+x \sim x^{2}, x+5 \simeq x, x^{2}(2+\sin x) /(1+x) \asymp x $$

Below I also give two "near misses".

2 $f\sim Ag$ instead of $f\sim g$

I found this a while back in this over 100 years old paper "Oscillating Dirichlet's Integrals" by G.H. Hardy (Quarterly Journal of Pure and Applied Mathematics, v.44 (1912)). Hardy was among the first few who began to use asymptotic notation. You can see it here:

The case (iii) includes certain special cases of importance. It may happen, for example, that $f / \phi$ tends to a definite limit: we then write $$ f \mathbin{\style{display: inline-block; transform: rotate(90deg)}{)|(}} \phi $$ Finally, it may happen that this limit is unity: we then write $$ f \sim \phi $$ It will be convenient, in order to avoid the frequent use of a rather inelegant symbol, to write $$ f \sim A \phi $$ instead of $f \mathbin{\style{display: inline-block; transform: rotate(90deg)}{)|(}} \phi.$ The notation implies that " there is a constant $A,$ not zero, such that $f \sim A \phi$". There is, of course, no implication that the various values of $A$ are the same;

3 $a\sim b$ in the sense of $a=\Theta(b)$

From Terry Tao's 'Compactness and Contradiction', page xii (which can be found in this extract):

I will, however, mention a few notational conventions that I will use throughout. The cardinality of a finite set $E$ will be denoted $|E| .$ We will use the asymptotic notation $X=O(Y), X \ll Y,$ or $Y \gg X$ to denote the estimate $|X| \leq C Y$ for some absolute constant $C>0 .$ In some cases we will need this constant $C$ to depend on a parameter $(\mathrm{e} . \mathrm{g} ., d),$ in which case we shall indicate this dependence by subscripts, e.g., $X=O_{d}(Y)$ or $X \ll_{d} Y$ We also sometimes use $X \sim Y$ as a synonym for $X \ll Y \ll X$.

That is, he is using $X\sim Y$ the way you'd use $Y=\Theta(X)$. Note that $a\sim b$ in the sense of 1 above implies $a=\Theta(b)$, and the implication is not reversible, since the limit might not exist.

Finally I should point out what someone correctly commented: there is also the asymptotic series notation, $f\sim\sum_{n=0}^\infty a_n \phi_n$, but its quite hard to mistake the two from context.