Exponential Growth

So why can’t we just use the brute force solution?

The answer is, of course, — “it is too slow”. In particular, for these examples I have just described, the number of objects of size $n$ grows exponentially with $n$. It isn’t too hard to see that, for example, the number of SAWs on the square lattice must satisfy $$\begin{align*} 2^n & \leq \text{ # SAWs of length \(n\) } \leq 4^n \end{align*}$$ Consequently, even if we could use a brute force method to compute stuff about — say $a_{N}$ — we’d have a very hard time computing anything about $a_{N+10}$, let alone $a_{2N}$.

One of the standard tools used to prove that a sequence of numbers grows exponentially, is to use Fekete’s lemma.

Fekete’s lemma:

Let $\{a_n\}$ be a submultiplicative sequence. That is $a_{n+k} \leq a_n \cdot a_k$. Then the limit $$\begin{align*} \lim_{n \to \infty} a_n^{1/n} &= \text{ exists } = \inf a_n^{1/n} \end{align*}$$ Similarly, if $\{b_n\}$ be a supermultiplicative sequence. That is $b_{n+k} \geq b_n \cdot b_k$. Then the limit $$\begin{align*} \lim_{n \to \infty} b_n^{1/n} &= \text{ exists } = \sup b_n^{1/n} \end{align*}$$

This idea was used by Hammersley & Morton to prove that the number of self-avoiding walks (and polygons) grow exponentially with rate $\mu$. See the diagram below:

Any self-avoiding walk of length $n+k$ can be cut into a pair of walks of length $n$ and length $k$ respectively, but separating them at their $n^{th}$ vertex. The converse is false. Hence we have $$\begin{align*} a_{n+k} \leq a_n \cdot a_k \end{align*}$$

Similarly, if we take any two self-avoiding polygons, we can always glue them together to make a new polygon (as below). However, the converse is false, we cannot cut a SAP in two to make two smaller SAPs.

Hence we have $$\begin{align*} a_{2n+2k} \geq a_{2n} a_{2k} \end{align*}$$ Thus both self-avoiding walks and self-avoiding polygons grow exponentially. With more work (and a very clever idea) you can actually prove they grow at the same exponential rate.

To be more precise:

• self-avoiding walks and polygons (counted by number of edges) in 2d grow as $2.64^n$ (ish) and $4.68^n$ (ish) — see Jacobsen, Scullard & Guttmann (2016) and Clisby (2013) for much more precise estimates.
• the number of knot digrams (counted by crossings) is conjectured to grow as (about) $11.4^n$ — see Jacobsen & Zinn-Justin (2002)
• the number of knot-types of crossing number $n$ grows at least as fast as $2^n$ and at most as $10.39^n$ — see Ernst & Sumners (1987) and Welsh (1992) (and subsequent improvement by) Stoimenow (2004).

So, because we cannot count these objects exactly, and we don’t have a good way to compute their number (or other facts about them) — we resort to counting them approximately. This brings us to “approximate counting” and the closely related topic of “flat histogram sampling”.