This is a sketch of seminar I will deliver to undergraduate problem solvers, and I feel like this is a good chance to fill more advanced math content into my blog. I like going deep in small concepts, but bigger projects like this also brings much fun.
I will split into three parts as follows.
I. Motivation
II. Contest problems
III. More problems and generalization
Enjoy :)
*
1. Introduction
Why growth rate? We start with a very simple example.
Example 1. Consider the limit $\lim _{x\to \infty}\frac{2x^2-3x-2}{x^2+7x+100} = 2$.
Before the access to the $\varepsilon - \delta$ approach, students are taught to bound the function by simpler fractions with clear limit then apply squeezing. It's a torturing analytical workout and students often get lost in the process.
Everyone knows clearly the answer is $2/1 = 2$, the problem is how do we reach there. Then we ask the question: why is that clear in the first place?
The answer is the order -- both are of order $x^2$. Once we divide by the order we have the limit
$\frac{2+o(1)}{1+o(1)} \to \frac{2}{1} = 2$.
The essence is to identify the order work around it. And the important takeaway of the seminar as to be laid below -- is to show that such thinking is widely applicable, far more than simple real analysis exercise.
To this end, let us recall a simple but important lemma, the polynomial dominance:
Lemma. Suppose $f(x), g(x)$ are polynomials of order $m,n$ with $m>n$, then there exists $L>0$ such that $|f(x)|>|g(x)|$ for all $|x|>L$. Call $f$ dominates $g$ (over applicable domain).
Proof. Exercise(!).
Every polynomial order is a distinct growth rate with a strict order. Actually the same applies to non-integer power although that is not our main focus today.
Think about a smooth function $f \in \mathbb{R}$. For each point $x\in \mathbb{R}$ we have a converging Taylor expansion $f(c) = \sum a_{n,c}(x-c)^n$ then we know $f(x)\approx a_m(x-c)^m$ around $x=c$ where $a_m$ is the lowest non-zero coefficient. The same applies when you look into the complex space where the poles and zeros are decided by the leading terms (both in positive negative powers) in the Laurent series.
Of course, one may extend the complex plane to the Riemann sphere (or by projective geometry in words of some geometers), one my find that infinity and behavior at infinity is merely zeros and poles at another point!
There are for sure more growth order than just polynomial. Exponential and log grwoth are the most typical one. Their growth rate is characterized by whatever quicker and slower than polynomial.
Lemma. Let $a>1$. Then the exponential function $a^x$ dominates any polynomial and the log function $\log _a x$ is dominated by any (non-constant) polynomial over $x >0$.
Exponential curve is even more common in branches of mathematics, in particular on anything involving time. Since exponential functions of larger base also dominates that of lower base -- we actually get to know the growth rate by bounding such function.
Suppose we have an (eventually) increasing function on our hand. The growth rate has to be one of those -- log, polynomial, exponential (of course, sub-log and hyperexponential as well), and these growth rates are mutually exclusive. Then within the same category each subclasses -- bases of exponentials or order of polynomials (well logs of different bases are constant multiples of each other) -- are mutually exclusive in the sense that one always dominates another and forms a total order in it. Knowing the growth rate pretty much locks the behavior, and in some problems the functions themselves.
The aim of the seminar, is to appreciate how common growth order becomes a crucial piece of information that can be used, or acts as a motivation towards the solution of a problem.
To start with, we lay down even more examples where undergraduate results uses growth rate as a centerpiece of the argument.
2. Classic examples
Let us look at some relatively accessible examples. We emphasize that the growth rate often provide crucial information.
First, we look at more results in complex analysis.
Example 2. (Liouville) Suppose $f$ is an entire function with $|f(z)|\leq M|z|^k$ for some $M>0$ and non-negative integer $k$, then $f$ is a polynomial of degree at most $k$.
Proof. Cauchy's integral formula.
In other words, any non-polynomial entire function admits a path $\gamma$ such that $|f(\gamma(t))|$ is not bounded by polynomials.
Example 3. (Rouché) Let $f,g$ be holomorphic over closed region $K$. If $|f(z)|>|g(z)|$ for all $z\in \partial K$ then $f$ and $f+g$ has equal number of zeros in $K$.
Proof. Argument principle. Note that it also extends to poles counting (!).
The inequality $|f(z)|>|g(z)|$ does not necessarily means $g$ is dominated by $f$ even just over $K$ but classic examples involve a higher degree polynomial and a lower degree polynomial, showing how the dominating term dictates the behavior of the function.
Example 4. (Ergodic Markov chain) Denote the correspondant matrix of the chain $A$, then $A$ has eigenvalue $\lambda _1 = 1 \geq |\lambda _2| \geq |\lambda _3|\ldots$. Furthermore, the error term (the $L_{\infty}$ distance) from the terminal state $v_{\infty}$ has decay rate dominated by the second eigenvalue. More precisely for $v_k$ the $k$-th state vector satisfies $\| v_k-v_{\infty}\|_{\infty} = O(|\lambda _2|^k)$.
Proof. Perron-Frobenius. This second eigenvalue characterization is quite widely used in fields like harmonic analysis. Note that we implicitly infer the chain to be finite reversible so that we don't run into non-trivial Jordan blocks.
Example 5. (Liouville approximation) If $x$ is an irrational algebraic number of order $n$ then there exists constant $c_x>0$ such that $|x-\frac{p}{q}| > c_xq^{-n}$ for all integers $p,q$ with $q>0$.
Proof. Elementary number theory. I feel like I have been applying tricks avoiding proofs too much here. Perhaps left as exercise.
This time, the function or concern is the approximability -- we don't necessarily need a continuous function to talk about growth rate. The result basically says approximability is bounded below be the decaying factor $q^{-n}$.
We conclude our introduction with a heavyweight classic.
Example 6. (PNT) $\pi (x) \sim x/\ln x$.
Proof. By wikipedia...joking but seriously the analysis details are so delicate despite the simple idea.
This result is not proving by capturing the growth rate. Instead, the result itself is about growth rate and it becomes the pillar of analytical number theory, one among the most important branch in modern mathematics. Much of the problems here starts from a counting function that turns out to be much, much more fundamental...like the Riemann hypothesis which is also a growth rate problem in nature.
But don't worry, we are not here trying to prove anything big. We just demonstrated how common such concept is, and we try to equip such mindset to facilitate problem solving.
(Cont.)
