Fekete's lemma

Remarks

Fix $m \ge 1$ and write each $n$ as $n = qm + r$ with integers $q \ge 0$ and $1 \le r \le m$. Subadditivity gives $a_n \le q a_m + a_r$, so $a_n / n \le (q m / n)(a_m / m) + a_r / n$. As $n \to \infty$ the last term tends to $0$ and $qm/n$ tends to $1$, so $\limsup a_n / n \le a_m / m$. Taking the infimum over $m$ gives $\limsup a_n/n \le \inf_m a_m/m \le \liminf a_n/n$, which proves the claim. The limit can be $-\infty$: the sequence $a_n = -n^2$ is subadditive, since $-(m+n)^2 \le -m^2 - n^2$, and $a_n / n = -n$. A typical use: if $c_n > 0$ and $c_{m+n} \le c_m c_n$ for all $m, n$, then $a_n = \log c_n$ is subadditive, so $c_n^{1/n}$ converges to $\inf_n c_n^{1/n}$. For a bounded linear operator $A$ on a Banach space with no power equal to $0$, this applies to $c_n = \norm{A^n}$. The same lemma is often called the subadditivity lemma.

Going deeper

For a student

The lemma turns a crude inequality into the existence of a growth rate, without any formula for the terms. It is used to define constants such as the connective constant of self-avoiding walks, entropies, and the spectral radius $\lim_n \norm{A^n}^{1/n}$. Kingman's subadditive ergodic theorem is a random version of the same idea. For a superadditive sequence, with $a_{m+n} \ge a_m + a_n$, apply the lemma to $-a_n$: then $a_n / n$ tends to $\sup_n a_n / n$.