APM_2F005 - Algorithms For Discrete Mathematics Bachelor 2
Lecturer: Lucas Gerin

ToolBox # 3: Asymptotics

Table of contents

References

Lecture notes of MAA102.

I. Review of little-o, big-0, $\sim$,...

I.1. Definitions

For the sake of simplicity we review the definitions in the case of positive sequences.

Definition. Let $(a_n)_{n\geq 0},(b_n)_{n\geq 0}$ be sequences of positive real numbers.
  • $a_n=\mathcal{O}(b_n)$ if there exists $C>0$ such that for all $n$, $a_n\leq Cb_n$.
  • $a_n=\Omega(b_n)$ if there exists $c>0$ such that for all $n$, $a_n\geq cb_n$. (Observe that $a_n=\Omega(b_n)$ if and only if $b_n=\mathcal{O}(a_n)$.)
  • $a_n=\Theta(b_n)$ if $a_n=\mathcal{O}(b_n)$ and $a_n=\Omega(b_n)$.
  • $a_n=\mathrm{o}(b_n)$ if $a_n=\varepsilon_n b_n$ for some sequence $\varepsilon_n\to 0$.
  • $a_n\sim b_n$ if $a_n=b_n(1+o(1))$, i.e. $\frac{a_n}{b_n}\to 1$.

I.2 Applications to exponential growth rates

Imagine that we observe a sequence $(a_n)_n$ which seems to grow exponentially fast. More precisely we make the guess that $$ a_n\stackrel{n\to+\infty}{\sim} cn^\alpha \rho^n, $$ for some $c>0, \alpha\in\mathbb{R}, \rho>1$. The dominating term in the above approximation is of course $\rho^n$. How to approximate $\rho$ from an observation of $a_0,a_1,\dots, a_n$ ?

Proposition. Let $(a_n)_{n\geq 0}$ be a positive sequence such that $$ a_n= cn^\alpha \rho^n(1+\varepsilon_n) $$ for some $\varepsilon_n=\mathcal{O}(1/n)$. Then both sequences $$ \left(\frac{a_{n+1}}{a_n}\right)_{n\geq 0},\qquad \left((a_n)^{1/n}\right)_{n\geq 0} $$ converge to $\rho$. More precisely, \begin{align*} \frac{a_{n+1}}{a_n}&=\rho\left(1+\frac{\alpha}{n}+\varepsilon_{n+1}-\varepsilon_n+\mathrm{o}(1/n)+\mathrm{o}(\varepsilon_n) \right),\\ (a_n)^{1/n}&=\rho\left(1+\alpha\frac{\log(n)}{n}+\mathrm{o}(\log(n)/n) \right),\\ \end{align*}

Proof of the Proposition
Case of $a_{n+1}/a_n$. \begin{align*} \frac{a_{n+1}}{a_n}&=\frac{c(n+1)^\alpha \rho^{n+1}(1+\varepsilon_{n+1})}{cn^\alpha \rho^n(1+\varepsilon_n)},\\ &=\rho \left(\frac{n+1}{n}\right)^{\alpha} (1+\varepsilon_{n+1})(1-\varepsilon_{n}+o(\varepsilon_{n}))\qquad \text{ (Recall }1/(1+u)=1-u+o(u).)\\ &=\rho \left(1+\frac{1}{n}\right)^{\alpha} (1+\varepsilon_{n+1}-\varepsilon_{n}+o(\varepsilon_{n}))\\ &=\rho \left(1+\frac{\alpha}{n}+o(1/n)\right) (1+\varepsilon_{n+1}-\varepsilon_{n}+o(\varepsilon_{n}))\qquad \text{ (Recall }(1+u)^\alpha=1+\alpha u+o(u).)\\ &=\rho\left(1+\frac{\alpha}{n}+\varepsilon_{n+1}-\varepsilon_n+\mathrm{o}(1/n)+\mathrm{o}(\varepsilon_n) \right). \end{align*}

Case of $a_{n}^{1/n}$. \begin{align*} a_{n}^{1/n}&=\exp\big(\frac{1}{n}\log (cn^\alpha \rho^n(1+\varepsilon_n))\big),\\ &=e^{c/n} \exp(\alpha\log(n)/n) \times \rho\times \exp\big(\frac{\varepsilon_n}{n}\big)\\ &=\rho\left(1+\alpha\frac{\log(n)}{n}+\mathrm{o}(\log(n)/n) \right), \end{align*} since $\frac{\varepsilon_n}{n}=\mathrm{o}(\log(n)/n)$.
End of proof .

In order to compare the two estimates (and check that the first one is the best), let us illustrate the convergence in the case of the $n$-th Fibonacci numbers. In that case we have that $$ F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n+o(1), $$ which is (a stronger form of) hypothesis above with $c=1/\sqrt{5},\alpha=0,\rho=(1+\sqrt{5})/2$. Observe that in this case $\varepsilon_n =\mathrm{o}(\rho^{-n})=\mathrm{o}(1/n)$.

II An example of asymptotics: the prime-counting function

For $x\in \mathbb{N}$ let $$ \pi(x)=\mathrm{card}\left\{\text{prime numbers }\leq x\right\}. $$ Thus $\pi(1)=0,\pi(2)=1,\pi(3)=2,\pi(4)=2,\dots$ In tutorials we will investigate the asymptotic behaviour of $(\pi(x))_x$. Let us state and prove bounds for $\pi(x)$.

Proposition. For every integer $x$ $$ \log_2(\log_2(x))-1\leq \pi(x)\leq x, $$ where $\log_2()$ stands for the logarithm in basis $2$.
(In particular there are infinitely many primes.) We first prove a preliminary lemma.
Lemma. Let $p_n$ be the $n$-th prime: $p_1=2,p_2=3,p_3=5,\dots$. Then $$ p_n\leq 2^{2^n}. $$

Proof of the lemma.
The proof goes by induction, the idea is to make effective the proof by Euclid that there are infinitely many primes.

For $n=1$ the inequality is clear. Assume it holds up to some $n\geq 1$. The integer $p_1p_2\dots p_n +1$ must have a prime factor. It cannot be any of the terms $p_1,\dots,p_n$ so we have found a new prime between $p_n$ and $p_1p_2\dots p_n +1$. Thus \begin{align*} p_{n+1}&\leq p_1p_2\dots p_n +1\\ &\leq 2^{2^1}2^{2^2}\dots 2^{2^n} +1\\ &=2^{2+2^2+\dots+2^n}+1\\ &=2^{2^{n+1}-2}+1\\ &=2^{2^{n+1}}(1/4+2^{-n-1})\leq 2^{2^{n+1}}. \end{align*}

End of proof of the Lemma.

Proof of the Proposition.
The upper bound $\pi(x)\leq x$ is obvious so we focus on the lower bound. By definition of $x\mapsto \pi(x)$ we have for every integer $x$ that $$ p_{\pi(x)}\leq x <p_{\pi(x)+1}. $$ Using the Lemma we therefore have $$ x\leq 2^{2^{\pi(x)+1}}. $$ Taking twice the logarithm (in basis 2) of both sides we obtain $$ \log_2(\log_2(x))\leq \pi(x)+1. $$

End of proof of the Proposition.

Remarks.
  • We can observe empirically that this is a very poor lower bound. Indeed for $n=100000$, $$ \log_2(\log_2(100000))-1=2.0539...\qquad \text{ while }\qquad \pi(100000)=9592 $$
  • The true estimate for $p_n$ and $\pi(n)$ are known for a while but the proof is way more complicated. The prime number theorem states that $$ p_n\sim n\log(n),\qquad \pi(x)\sim \frac{x}{\log(x)}. $$ Chebyshev, in the 1840s, was the first to establish significant bounds for $\pi(x)$. The first proof of the prime number theorem was independently given by Hadamard and de la Vallée Poussin in 1896, building on foundational work by Riemann.

III. Dynamics (Review from MAA102)

In experimental mathematics we often encounter sequences defined (more or less explicitly) by a recurrence of the form $u_{n+1}=f(u_n)$. Let us recall from MAA102 how to deal with such recurrences.

Proposition. Let $a\in\mathbb{R}$ and $f$ be a map $\mathbb{R}\to\mathbb{R}$. Let $(u_n)_{n\geq 0}$ be the sequence defined by $$ \begin{cases} &u_0=a,\\ &u_{n+1}=f(u_n)\ \text{ for all }n\geq 0. \end{cases} $$ If $(u_n)$ has a finite limit $\ell$ and if $f$ is continuous then $\ell$ must satisfy $\ell=f(\ell)$.
The proof only consists in letting $n\to +\infty$ in the recurrence. Let us see how to apply it on a particular case. Let $$ u_0=1, u_1=\sqrt{2},\ u_2=\sqrt{2}^{\sqrt{2}},\dots , u_n=\sqrt{2}^{\sqrt{2}^{{\dots}^{\sqrt{2}^{\sqrt{2}}}}}. $$ In a more compact way: \begin{cases} &u_0=1,\\ &u_{n+1}=\sqrt{2}^{u_n}\ \text{ for all }n\geq 0. \end{cases}

The above script seems to indicate that $u_n \to 2$. The following plot gives an insight of what happens:

Indeed, $x\mapsto \sqrt{2}^x$ has two fixed points $x=2$ and $x=4$. The interval $[0,2]$ is clearly stable under $f$ and in this interval $\sqrt{2}^x \geq x$. This shows that $(u_n)$ is bounded and increasing, so it converges and the limit $\ell$ is the only fixed point of $f$ in that interval: $\ell=2$.

Actually one can do better. First observe that $f'(x)=\log(\sqrt{2})\sqrt{2}^x$ so that the mean value theorem applied to the interval $[0,2]$ says that, for every $x,y\in [0,2]$ $$ |f(x)-f(y)|\leq \sup_{[0,2]} f'\times |x-y|= \log(\sqrt{2})\sqrt{2}^2\times |x-y|=\log(2)|x-y|. $$ In other words, $f$ is contraction. This implies, for $n\geq m$, $$ |u_n-u_m|\leq \log(2)|u_{n-1}-u_{m-1}|\leq \log(2)^2|u_{n-2}-u_{m-2}|\leq \dots \leq\log(2)^{m}|u_{n-m}-u_{0}|\leq \log(2)^{m}\times 1. $$ Letting $n\to +\infty$ (while letting $m$ fixed) gives finally $$ |\ell-u_m|\leq \log(2)^{m}, $$ so that the convergence is exponentially fast.