2
$\begingroup$

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.

$\endgroup$
16
  • $\begingroup$ You're righ, it is used for asymptotic equivalence. The most general definition is that there exists a function $\varepsilon(n)$ with $\lim_{n\to\infty}\varepsilon(n)=0$ such that $f(n)=\bigl(1+ \varepsilon(n)\bigr)g(n)$ . $\endgroup$
    – Bernard
    Apr 22 '20 at 8:58
  • $\begingroup$ You mean $\lim\limits_{n\to \infty} f(n) = \bigl(1+ \varepsilon(n)\bigr)g(n)$ with your last equality? $\endgroup$ Apr 22 '20 at 10:05
  • $\begingroup$ Not at all, it is supposed to be valid for all $n$. It is a more explicit way to write $f(n)-g(n)=o(g(n))$. $\endgroup$
    – Bernard
    Apr 22 '20 at 10:25
  • 1
    $\begingroup$ No. The standard definition, as you know, uses $c=1$ (with some drawbacks, as explained in the English Wikipedia notice. I think – but I'm no specialist – that, used in this extended sense, the notation has to be explained before. $\endgroup$
    – Bernard
    Apr 22 '20 at 11:26
  • 1
    $\begingroup$ I think it is worth mentioning that $f(x) = \Theta(g(x))$ does not imply $f(x)/g(x) \to C$ for some constant $C \neq 0$. The quotient might not converge $\endgroup$
    – marlasca23
    Jul 2 '20 at 7:51
2
+50
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ What about the answers in the related question where people are using it to mean that the limit tends to a constant instead of $1$? Specifically where the user Rocherz says in comment "$F_m \sim \phi^m$ actually means $\displaystyle \lim_{m\to\infty} \dfrac{F_m}{\phi^m}$ is constant." Are they wrong? $\endgroup$ Jul 3 '20 at 14:04
  • 1
    $\begingroup$ @MichaelMunta That's not $\Theta$ at all, that's stronger. I've seen that as well, in some old papers. I know an old paper where Hardy wrote $f\sim Ag$, for this meaning, but $A$ here was not a number, rather the notation $\sim A$ somewhat abusively means that there existed some number $A$ such that $f/g\to A$. But if you want exactly that notation in a paper, I don't recall which paper... Theres many different 'related' and 'roughly the same' meanings of $\sim$ unfortunately $\endgroup$ Jul 3 '20 at 14:10
  • $\begingroup$ @MichaelMunta I might have time (but not now). to look for more sources for other variants, for the Hardy's paper its in this question I asked math.stackexchange.com/questions/3318508/… $\endgroup$ Jul 3 '20 at 14:33
  • $\begingroup$ @MichaelMunta updated my answer $\endgroup$ Jul 4 '20 at 3:54

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.