Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 30 / 1

This is the Fekete lemma, with its possible extended-real limit made explicit. Put $L={\inf }_{m\ge 1}{x}_m/m$. Since $x_n\le n{x}_1$, $L$ cannot be $+\infty$; it may be $-\infty$.

Fix $m\ge 1$ and write $n=qm+r$, with $0\le r<m$. Repeated subadditivity giveswhere for this calculation set $x_0=0$. The finitely many possible remainder terms are bounded. Since $q/n\to 1/m$,This holds for every $m$, whereas $x_n/n\ge L$ by the definition of an infimum. If $L$ is finite, the upper and lower bounds agree. If $L=-\infty$, choosing $m$ with arbitrarily negative $x_m/m$ shows that $x_n/n\to -\infty$. ThusA finite real limit is not guaranteed: $x_n=-n^2$ is a subadditive sequence and has $x_n/n=-n\to -\infty$. If the limit is intended to be real rather than extended real, one must add a linear lower bound.

Split a self-avoiding walk of length $m+n$ after its first $m$ steps. Its prefix is one of the $c_m$ walks, and its translated suffix is a self-avoiding walk of length $n$ from the origin. The pair determines the original walk, although not every pair can be concatenated without intersection. ThereforeAll $c_n$ are positive, so $x_n=\log c_n$ is a subadditive sequence. The Fekete lemma gives existence of ${\lim }_n{n}^{-1}\log c_n$ and consequently of the connective constant.

For a lower bound, all words of length $n$ using only north and east steps produce distinct self-avoiding walks: the sum of the two coordinates increases at each step. Thus $c_n\ge 2^n$. For an upper bound, there are four choices for the first step and at most three thereafter, since a self-avoiding walk cannot immediately reverse its previous edge. Hence $c_n\le 43^{n-1}$. Taking $n$th roots provesThe elementary upper bound counts all non-backtracking walks, including some that self-intersect, so it is an upper estimate rather than an equality.

Count partially directed self-avoiding walks using north, east and west steps. Within one horizontal level, a self-avoiding walk must move consistently east or consistently west. It can change horizontal direction only after a north step. Conversely, these rules guarantee self-avoidance: every visited horizontal level is new, and its horizontal run is monotone.

Let $a_n$ count these walks, including $a_0=1$. A horizontal run has generating functionEvery walk decomposes uniquely into an initial horizontal run followed by zero or more pairs consisting of a north step and a horizontal run. Therefore the generating function isComparing coefficients yields $a_0=1$, $a_1=3$, and $a_n=2a_{n-1}+a_{n-2}$ for $n\ge 2$. Solving this linear recurrence relation givesThese are a subset of all self-avoiding walks, so $c_n\ge a_n$ andAllowing either horizontal direction at successive heights gives the strict gain over the north-east-only family.