Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 204 / 1

Let $\alpha ={\inf }_{r\ge 1}{a}_r/r$. The inequality $a_n/n\ge \alpha$ gives ${\mathrm{liminf}}_n{a}_n/n\ge \alpha$. Fix $r$ and write $n=qr+s$, where $0\le s<r$. Repeated subadditivity gives $a_n\le q{a}_r+a_s$ when $s>0$, with the evident omission when $s=0$. Since the finitely many remainders $a_s$ are bounded,Taking the infimum over $r$ proves the Fekete lemma:

Splitting any $(m+n)$-step self-avoiding walk after $m$ steps and translating its remaining segment to the origin injects it into an ordered pair of an $m$-step and an $n$-step self-avoiding walk. Hence $b_{m+n}\le b_m{b}_n$. The sequence $a_n=\log b_n$ is subadditive, so the Fekete lemma givesExponentiating proves existence of the connective constant $\kappa ={\lim }_n{b}_n^{1/n}$.

After the first of the four possible steps, a self-avoiding walk has at most three choices at every stage because it cannot immediately reverse its preceding step. Thus $b_n\le 4\cdot 3^{n-1}$ and $\kappa \le 3$. On the other hand, every sequence of $n$ north or east steps is self-avoiding, so $b_n\ge 2^n$ and $\kappa \ge 2$.

Consider walks assembled from blocks $E$, $E{N}^k$, and $E{S}^k$ with $k\ge 1$. Their horizontal coordinate increases once in every block, and within each vertical line they move monotonically, so every such walk is self-avoiding. If $c_n$ counts these walks by total length, its ordinary generating function isIts positive dominant singularity is $z=\sqrt{2}-1$, so ${\lim }_n{c}_n^{1/n}=1+\sqrt{2}$. Since $b_n\ge c_n$,