Skip to Main Content

Enumerative Combinatorics of Lattice Polymers

Nathan Clisby

Communicated by Notices Associate Editor Emilie Purvine

Article cover

Why Study Lattice Polymers?

There are three principal reasons to study lattice polymers. For physicists (and mathematicians interested in applications), the miraculous phenomenon of “universality” means that exact information about real-world polymer systems can be obtained by studying highly idealized models such as lattice polymers. For mathematicians (and physicists who appreciate mathematical beauty), the physically motivated models are mathematically appealing, and have rich combinatorial structure. The third reason is that it is just a really fun research topic.⁠Footnote1 It’s possible that the author is somewhat biased.

Figure 1.

A self-avoiding walk (left) and a self-avoiding polygon (right) on the square lattice.

The most fundamental model is the self-avoiding walk Flo49MS93, which is a walk that starts at the origin of a lattice and moves successively to neighboring sites, with the rule that self-intersections are forbidden. An example of a self-avoiding walk on the square lattice is shown in Figure 1, together with a self-avoiding polygon, which is a walk that returns to the origin but is otherwise self-avoiding.

Formally, an -step self-avoiding walk on is a mapping with at the origin, steps of unit Euclidean length so that for each , and the self-avoidance constraint enforced by for all . We are interested in the number of walks of length , which we denote by , the number of polygons of length , which we denote by , and other properties such as the mean squared distance of the end of an -step walk from the origin,

which measures the typical size of a walk.

It is widely believed that the following asymptotic behavior occurs for the self-avoiding walk on a regular lattice in any dimension:

where is a lattice-dependent growth constant, and and are universal critical exponents that only depend on the dimension of the lattice. Simple random walks undergo Brownian motion, and have and , while walks that move at a steady speed, that is “ballistically,” have . For self-avoiding walks there are exact conjectures for of and , and precise numerical estimates from Monte Carlo simulations for of and (the numbers in parentheses indicate the uncertainty in the final digit), while for the self-avoidance constraint is sufficiently weak that critical exponents assume their random walk values and , with logarithmic corrections when .

Self-avoiding walks are self-similar fractal objects, with fractal dimension . As for , self-avoiding walks are visibly more spread out than simple random walks, but do not move ballistically. This can be observed in the image at the start of the article that shows a self-avoiding walk of 1 billion steps on the square lattice, generated using a Markov chain Monte Carlo procedure known as the pivot algorithm.

The self-similarity of two-dimensional self-avoiding walks can be observed in Figure 2. Starting at the top left corner there is a walk of one billion steps. Then, by following the arrows one has a sequence of subwalks of length steps that are obtained by zooming into the original walk. It is impossible (at least to the author) to distinguish between different length scales until the underlying lattice becomes apparent. This image also serves as a striking “proof by picture” that , as subwalks of length are scaled by , where is a fixed constant. If was even slightly different from the conjectured value of , then the size of the images of these subwalks would noticeably change as is varied from 10 to .

Figure 2.

Zooming in to a self-avoiding walk with steps on the square lattice. Starting from the top left, subwalks have steps, with each successive subwalk appearing as a red section in the larger walk. The scale factor for the length- subwalk is , where is a fixed constant.

The self-avoiding walk is intimately related to other models in lattice statistical mechanics, as it is the limit of the so-called -vector model; the famous Ising model corresponds to .

Remarkably, self-avoiding walks can be used to gain exact information about real-world polymer systems due to the phenomenon of universality. Universality is the observation that when a change of state, or phase transition, with a diverging correlation length occurs for a model in statistical mechanics, that sufficiently similar systems in the same “universality class” will have exactly the same kind of behavior in the limit of large system size, and the fine-grained details of the model do not matter.

The key feature that determines the behavior of real polymer chains in a good solvent is the excluded volume constraint, and this property is exactly captured by the self-avoiding walk model. Thus, real polymers, self-avoiding walks on any three-dimensional lattice, weakly avoiding walks that penalize but do not forbid self-intersections, and various semirealistic models of polymers in all have the same value of . Self-avoiding walks also capture other universal properties, such as the fact that knots are ubiquitous in long polymers; as the probability of a self-avoiding polygon being knotted approaches 1 exponentially rapidly.

Much is known about self-avoiding walks, but rather less has been proved. Two stand-out results are the proof by Hara and Slade HS92, via the lace expansion, that for the critical exponents exist and assume random walk values, and the proof by Duminil-Copin and Smirnov DCS12, via the introduction of a parafermionic observable that satisfies a remarkable discrete holomorphicity condition, that for the honeycomb lattice. But, although there is overwhelming numerical evidence in favor of the correctness of the asymptotic forms for and given above, there is as yet no proof of this for and .

For , it is believed that in the scaling limit, where and the appropriately scaled lattice spacing approaches zero, that the two-dimensional self-avoiding walk model converges to Schramm-Loewner Evolution (SLE) with parameter . A proof of this would immediately confirm the conjectured exponent values for the two-dimensional self-avoiding walk, and much else, and would surely be worthy of a Fields Medal.

For , the situation is even more challenging, and the prospects of proving any strong results seem remote. Therefore, current efforts to improve our understanding of three-dimensional lattice polymer systems are focused on experimental mathematics efforts in computer enumeration and Monte Carlo simulation to deepen our qualitative and quantitative understanding of the behavior of these systems.

Despite the large gaps in what has been proved about self-avoiding walks, it has been an extraordinarily rich model in inspiring progress in combinatorics, mathematical physics, probability, and polymer science. Going into detail on these topics would require rather more space than I have available (see MS93JvR15 for more of these details) and in this article I will instead narrowly focus on aspects of lattice polymers related to enumerative combinatorics. Although the self-avoiding walk model has not been solved, it has inspired a fabulously diverse ecosystem of combinatorially interesting solvable models. Without even the slightest pretense at comprehensiveness, I will concentrate on enumerative combinatorial aspects of a select few models of lattice polymers to convey some of the goals and methods of this research area. In addition, one of the most powerful experimental mathematics approaches to the quantitative understanding of self-avoiding walks and related models is to perform exact enumerations on the computer. I will briefly explain the combinatorial and geometric insights that are at the heart of the most efficient known algorithms for the enumeration of self-avoiding walks in two and three dimensions.

I will now give a brief overview of the use of generating functions in the study of lattice polymers.

Generating Functions

For any combinatorial sequence , with , we may associate a generating function

For lattice models of polymers, typically is the number of walks of length , and we say that is the parameter that is conjugate to the length of the walk. Stealing a vivid metaphor from Wilf Wil94, “a generating function is a clothesline on which we hang up a sequence of numbers for display.” This generating function may be purely formal, but often we can study the behavior of via the analytic properties of ; this is the domain of analytic combinatorics.

We may want to keep track of additional properties besides length, in which case we will construct a multivariate generating function. For example, for Dyck paths (defined later) we construct a generating function that weights contacts with a surface

with the number of Dyck paths with contacts and of length . We can treat and as purely formal parameters, or we can give them particular values. In particular, is the generating function for Dyck paths counted by length alone. If we treat as a fixed constant, then is a function of , and we can consider the walks to be weighted objects. In this case, there is a direct correspondence between and so-called Boltzmann weights in statistical mechanics that determine how the lattice polymer will behave as a function of temperature.

When models in statistical mechanics have a phase transition from one state to another, this will manifest as a singularity in the generating function at a critical point. For the generating functions of lattice polymers that we will discuss, this critical point is also the leading singularity of the generating function. For single variable generating functions, such as , the leading singularity, , is a constant, while for multivariate generating functions the location and nature of the critical point may be a function of the other parameters.

If the leading behavior of the generating function at is a power-law singularity with exponent , that is,

with analytic in the vicinity of , then

where is the growth constant for the sequence and .

Thus, there is a correspondence between the leading power-law singularity in the generating function and the power-law factor of the asymptotic behavior of the associated sequence. In particular, a pole in the generating function with will mean that the sequence will grow as a pure exponential with no power-law correction.

More complicated analytical forms and associated asymptotic behavior are possible, including confluent exponents and the occurrence of multiple leading singularities, both of which result in additive power-law corrections for the sequence. Still more exotic behavior may occur, such as stretched exponential asymptotics like

with .

Generating functions may have a wide variety of analytical properties. In order of increasing generality, they may be:

Polynomial, in the case where there are only a finite number of objects. For example, self-avoiding walks in a 4 by 4 grid.

Rational, where the only singularities are poles.

Algebraic, so that the generating function is a solution of a polynomial equation.

Differentiably finite (D-finite), or holonomic, so that the generating function is a solution of a linear differential equation with polynomial coefficients.

Differentiably algebraic (D-algebraic), so that the generating function is a solution of a polynomial equation involving , the function, and its derivatives.

None of the above!

For solvable models, the goal is to find an explicit expression for the generating function—perhaps as an algebraic expression, or as the solution of a higher order ODE—or at least to find a polynomial-time algorithm for generating coefficients.

The anisotropic generating function for self-avoiding polygons on the square lattice, for which vertical steps have different weights than horizontal steps, is not D-finite Rec06. If one then sets the vertical and horizontal weights to be equal one obtains the standard model for self-avoiding polygons on the square lattice. Therefore, in the absence of a miraculous and unexpected cancellation of singularities, the generating function for self-avoiding polygons is not D-finite. This strongly suggests that it will be, at best, extremely challenging to find exact solutions for self-avoiding walks and self-avoiding polygons on the square lattice.

In this case, our goal is to learn as much about the model as possible by finding efficient algorithms to enumerate the objects, so as to determine as many as possible terms of the sequence .

Consequently, we seek to determine the properties of this sequence via series analysis techniques. The most powerful general technique is the method of differential approximants Gut89, which takes the finite approximation of the generating function and finds a linear ordinary differential equation with polynomial coefficients that reproduces these initial terms. Features of the model such as and the associated critical exponent can then be estimated by analyzing the singularities of the differential equation.

The application of sophisticated computer enumeration and series analysis techniques to problems in lattice statistical mechanics was pioneered from the late 1950s by Domb and Sykes (see, e.g., DS61) and their many collaborators including Fisher, Essam, and Gaunt.

It can be extremely powerful to apply series analysis techniques to series expansions for problems that are suspected of being solvable, or more precisely to have D-finite generating functions. If, for example, it is found that a differential equation involving 100 coefficients is able to exactly reproduce 1000 terms of a sequence that has been found by other means, one would be very confident that the true generating function is in fact the solution of the differential equation. Such a discovery does not constitute a proof, but once the solution is known it is usually much easier to prove that it is correct! Furthermore, when the generating function can be proved to be D-finite, with a priori upper bounds available for the order and degree of the associated differential equation, then this guessing procedure can be made fully rigorous Zei90.

The Model Spectrum

One characteristic that distinguishes different models of walks is how much information must be maintained about the walk as it gets longer, so as to correctly calculate weights and avoid self-intersections.

Variants of directed walks can on occasion completely forget about their past behavior, while so-called “prudent” walks (defined later) can never completely forget about their past behavior, but can condense that information to a finite set of parameters. In contrast, the most physically relevant model, self-avoiding walks, requires that the walk remember its entire past behavior. Indeed, each step of a self-avoiding walk of length depends on every other step, and it is incorrect to think of a self-avoiding walk as being generated step-by-step as it is a truly non-Markovian process.

This makes it straightforward to solve simple variants of directed models, challenging to solve models such as prudent walks that require more information to be retained, and extremely difficult—perhaps even impossible—to solve variants of the self-avoiding walk model.

A unifying principle for exact solutions and efficient enumeration algorithms is that a geometric or combinatorial insight must be gained that allows for independence between different parts of the walk, where the dependence between different parts is mediated by a finite (for solutions) or reduced (for algorithms) set of parameters.

Our goal is to find as much information as possible about the sequences and generating functions of lattice polymer models. In particular, we wish to understand the functional form of the generating function and to determine features such as critical exponents exactly, or to estimate them as accurately as possible. In this way we can gain insight into the phase transitions of the model, and by universality these models may also tell us about real-world systems.

The tools we have at our disposal in this endeavor are, in order of preference, exact solutions, polynomial time algorithms for enumeration, exponential algorithms for exact enumeration, and finally Monte Carlo methods of approximate enumeration. We will touch on each of the exact methods in this article, starting with the exact solution of directed walk models.

Directed Walks

We begin by considering the simplest model of all: directed walks on the square lattice. Walks start at the origin, and are able to move either to the north or east with each step. See Figure 3 for example configurations.

Figure 3.

Directed walks on the square lattice of 100 steps (left) and 1000 steps (right).

The directed nature of the walk means that there is never any possibility for self-intersection, and so choices are completely unrestricted. By convention, we take the number of walks with zero steps to be 1, and then there will be two walks of length 1, and in general

The associated generating function is

We can see that the only singularity of the generating function is a simple pole, that , and the growth constant . Rather than enumerating the walks directly, an alternative approach is to find a functional equation for the generating function. We recognize that either a directed walk has zero steps (corresponding to ), or has a step to the north or east (weight ) followed by another directed walk. So

and rearranging gives the same answer as the direct approach.

One notable feature of directed walks is that they are anisotropic: although they are self-similar fractal objects, their scaling behavior depends on the direction. As can be observed in Figure 3, in the SW-NE direction, the directed walk is moving ballistically with constant speed away from the origin so that , whereas in the NW-SE direction the walk is performing a one-dimensional random walk.

We next determine the generating function for a simple modification of directed walks with periodic boundary conditions in the north direction, so that self-intersections may occur when the walk winds around the cylinder of circumference . We show an example of these directed walks with in Figure 4. Playing around with small configurations shows that the number of cylinder walks when with steps is , which is suspiciously reminiscent of the Fibonacci sequence. By partitioning the set of walks into those that end in an east step, and those that end in a north step, it is straightforward to show that the recurrence relation for the Fibonacci sequence is indeed satisfied, that is, for .

Figure 4.

Example of a directed self-avoiding walk on a cylinder of circumference .

Instead of obtaining an expression for for arbitrary directly, we will derive a functional equation. We recognize that either the walk never takes an east step, in which case it can take either north steps, or it does take at least one east step, in which case it can take north steps, then one east step, followed by another walk. Thus,

If we take , then the generating function is

To determine an explicit expression for , we need to perform a partial fraction decomposition and observe that

where is the golden ratio, and . With a bit of algebra we find that

Thus we have , , and as a bonus we have an explicit expression for the Fibonacci numbers in terms of the golden ratio. Note that is less for cylinder walks than for directed walks; the additional restriction placed on the walks makes them less numerous. Generalizations of Fibonacci numbers are obtained for higher , for example the so-called Tribonacci numbers for ; the On-Line Encyclopedia of Integer Sequences (https://oeis.org) is an amazing resource for discovering interesting sequences.

Dyck Paths

The final directed model we will consider is Dyck paths with contact weights. Dyck paths are directed paths on the rotated square lattice with allowed steps being north-east and south-east, with the extra conditions that the path must always have but start and end with ; see Figure 5 for an example. The boundary is a mathematical abstraction of an impenetrable surface. We weight each step taken by , and associate an additional weight with each return to the surface. If we set , then contacts are penalized, if we set , then the weights have no effect on the generating function at all, and if we set , then contacts are reinforced.

Figure 5.

Example of a Dyck path with 10 steps, and two returns to the surface. The associated weight is .

We are introducing this model both because it has interesting combinatorics, and also because it is an extremely simple model of polymer adsorption. We shall see that there is a special value of where the Dyck path will transform from being typically far from the surface, or “desorbed,” to typically being close to the surface, or “adsorbed.” That is, a phase transition will occur. The contact weight can be related to experimental quantities used to induce adsorption such as temperature and solvent quality.

To find a functional equation we condition on the first return to the surface. Either a Dyck path has zero steps (contributing weight ), or it consists of a step above the surface (weight ), then a Dyck path above the surface (where the contact weights are ignored, hence set to 1), then a step down to the surface (weight ), followed by another Dyck path. This functional equation can be represented pictorially as

If we let we obtain a quadratic functional equation for :

where the appropriate branch is chosen to ensure that the solution corresponds to the physical model, which has positive coefficients. We point out that has the expansion

where is the th Catalan number, one of the most famous of all sequences. Thus

and by comparing with we observe that and (the same as directed walks) for unweighted Dyck paths.

Now, we can write in terms of to obtain the full solution:

Note that is a function of , and therefore any coefficients involving an odd power of must be identically zero. This reflects the fact that there must be an even number of steps to return to the surface.

Our expression for has strikingly different qualitative behavior depending on the value of the weight , which may be identified with two different universality classes. For , the leading singularity is an algebraic singularity at , so and the rate of exponential growth is thus independent of ; this is the de-sorbed phase. For , the leading singularity is a pole at ; this is the adsorbed phase.

Dyck paths with contact weights thus provide a qualitative model of the physical adsorption phase transition that is observed with real polymers.

With some extra work RvR04, it is possible to show that the mean number of contacts for a -step weighted Dyck path is to leading order given by

This conforms with what we might expect: when the polymer is desorbed with , there are on average a finite number of contacts as we would expect the polymer to only approach the surface in the vicinity of the ends. When , the number of contacts is proportional to , which is consistent with the polymer being adsorbed or stuck to the surface. Finally, precisely at , we have a critical phase where the system changes from being desorbed to adsorbed, and in this case there are contacts, with .

For real polymers in two dimensions, it is believed that the exponent is in fact exactly the same as for weighted Dyck paths, while in three dimensions the question is not fully settled, but the best available evidence is that BOP18.

There is an enormous zoo of directed walk models that are studied for reasons of mathematical interest and physical relevance. These models can be fiendishly difficult to solve, unlike the simple examples presented here. But, for now we move on to a family of models for which steps in all directions are allowed, and thus is closer to the physically relevant self-avoiding walk model.

Prudent Walks

Prudent walks are walks that make prudent choices to avoid the possibility of self-intersection, by never taking a step towards a site they have previously visited. A short example of a prudent walk is shown in Figure 6, with the region that currently cannot be stepped towards highlighted on the right.

Figure 6.

A prudent walk on the square lattice (left), and on the right the shaded rectangle shows the region that the walk cannot step towards.

This method of avoidance is significantly less crude than was the case for directed walks, but does not require the arbitrarily long memory of detailed structure that is characteristic of self-avoiding walks. This is illustrated in Figure 6, where on the right the details of the structure of the walk in the shaded region are completely irrelevant to the future choices that may be available—it is safe to forget everything except for the dimensions of the shaded region. The rules for self-avoidance can be encoded by keeping track of the direction of motion, and the bounding rectangle of previously visited sites.

One consequence of the prudent rule is that at each step the end of the walk lies on its bounding rectangle,⁠Footnote2 The converse is not true—there are walks for which every step lies on the bounding rectangle that are imprudent. and this leads to four natural subcategories of prudent walks: 1-sided prudent walks that are always on the eastern boundary of the rectangle, 2-sided prudent walks that always lie on the northern or eastern boundaries, 3-sided prudent walks that lie on the western, northern, or eastern boundaries, and finally 4-sided prudent walks (or, just prudent walks) that can lie on any boundary. Note that 2-, 3-, and 4-sided prudent walks are not time-reversible.

Two random 4-sided prudent walks are shown in Figure 7. The short walk of 100 steps could almost be mistaken for a self-avoiding walk (compare with the subwalk of 100 steps in Figure 2), but longer walks are very clearly directed.

Figure 7.

4-sided prudent walks of 100 steps (left) and 1000 steps (right).

1-sided prudent walks are more commonly known as partially directed walks, and can move either north, east, or south. We recognize that either the walk never takes an east step, in which case it can take an arbitrary number of north or south steps, or it does take at least one east step, in which case it can take an arbitrary number of north or south steps, then one east step, followed by another walk. Thus,

The leading singularity is a pole at , and so the growth constant is . Partially directed walks are more numerous than directed walks, but qualitatively they behave in exactly the same way.

2-sided prudent walks are considerably more interesting, as walks can move in all four directions and more information needs to be retained to find a suitable functional equation. The principal insight that allows a functional equation to be constructed is that with each step the 2-sided walk may either take a step along either the northern or eastern boundaries, or the walk may inflate the boundary by taking an east step from the eastern boundary, or a north step from the northern boundary. When this inflation step occurs the walk can forget about its past behavior, with the exception of the relative location of the north-east corner. The resulting generating function is

Despite their increased freedom as compared to 1-sided walks, 2-sided walks nonetheless behave as directed walks moving in the north-east direction. This is reflected in the fact that the leading singularity is a pole at that is a solution of . This corresponds to a growth constant of . As this growth constant is strictly larger than the value for 1-sided prudent walks, we see that 2-sided prudent walks are exponentially more numerous.

3-sided prudent walks are much more challenging still, but Bousquet-Mélou BM10 in a tour de force was able to find an appropriate functional equation using the conditional independence after an inflationary step occurs, and then to obtain a closed form expression for the generating function as an infinite sum. Bousquet-Mélou explains that besides the length, information about additional “catalytic” parameters must be retained in the construction of the functional relation. For 2-sided walks, a single catalytic variable that tracks the distance of the end to the north-east corner of the bounding rectangle suffices, while for 3- and 4-sided walks it is necessary to retain two and three catalytic variables, respectively. These catalytic variables contain all of the necessary information about the past behavior of a walk so that the future behavior can be correctly modeled.

3-sided walks asymptotically have the same growth rate as 2-sided walks, and after some extra freedom in their initial stage behave in the same manner as 2-sided walks by settling down to follow the diagonal in either the north-east or north-west directions.

Interestingly, in contrast to the other models we have seen, the generating function for 3-sided prudent walks is not D-finite. Bousquet-Mélou showed that the generating function is meromorphic in the disk , but with infinitely many poles occurring in the disk. The striking feature is that 3-sided prudent walks have a straightforward, natural definition, but nonetheless have a wickedly complicated solution. Perhaps there is another, more natural, formulation of the solution that captures the simplicity of the underlying problem?

Finally, no explicit expression has been obtained for 4-sided prudent walks. There is a functional equation BM10 for , the generating function for prudent walks ending on the northern edge of the bounding rectangle, involving three catalytic variables:

where the desired generating function is obtained by setting the catalytic variables to one, . There is a polynomial-time algorithm based on the functional equation to generate series coefficients, and it was recently proved that the limiting large behavior is exactly the same as 2- and 3-sided prudent walks PST17.

It is arguable that this means that the model has been “solved,” in the sense that we exactly know the limiting large behavior, and can quantitatively understand any features of the model to arbitrary precision. But, it would be far more satisfying to have an explicit solution, and preferably one that captures the simplicity and elegance of the model itself.

A key question is: can the generating function be written in a convenient or illuminating form, or as the solution of a natural equation without catalytic variables?

If progress could be made on this problem it would perhaps give hints as to how to make progress on other difficult lattice polymer problems. And, just maybe, this would also give some information about what a solution of the full two-dimensional self-avoiding walk problem might look like.

We also note that, disappointingly, each of the prudent walk models has , and thus behave as directed walks. It is not clear how to devise a solvable model that has .

This takes us to the boundary of lattice polymer models that can be considered solvable, and we now jump to the other side of the fence.

Self-Avoiding Walks on

The simplest method of computer enumeration of combinatorial objects is to generate each of the objects that are being counted, which I will refer to as brute force enumeration. Then, the computational complexity of the algorithm is determined completely by the asymptotic growth in number of the objects.

The secret to inventing an effective enumeration algorithm is to find a combinatorial or geometric insight that will allow one to count less numerous objects instead.

The length-doubling algorithm SBB11, the fastest known method for counting three-dimensional self-avoiding walks, uses a brilliant insight involving inclusion-exclusion to get an exponential improvement in computational complexity.

We start with the observation that every walk of length can be uniquely split into two -step self-avoiding walks at the midpoint. Therefore, is the number of pairs of nonintersecting -step self-avoiding walks.

We generate the set of all self-avoiding walks of steps starting at the origin. By definition, , so this requires CPU time . We label all of the sites that the walks visit (there will be sites), and we let be the set of walks that pass through site , and be the set of pairs of walks that pass through site . Finally, we count , first through the observation that the number of mutually avoiding pairs is the same as the number of all pairs () minus the number of pairs with at least one intersection:

We then apply the standard inclusion-exclusion formula for , summing over all subsets of the set of visited sites, and partitioning by the size of :

Finally, we recognize that the number of pairs of walks that pass through a particular set of sites is the square of the number of individual walks that pass through the set. Thus we obtain the final formula:

Most sets are empty, because each walk has steps, and so any collection of more than sites must be empty. The powerset for each walk has elements, so this means that there are at most nonempty sets in the sum.

Heuristically speaking, via the magic of the inclusion-exclusion formula the length-doubling algorithm transforms the problem of counting all possible ways that the half-walks can avoid each other to counting all possible ways that the half-walks can intersect.

This transformation results in a significant reduction in computational complexity: neglecting power-law factors, we have changed the computational effort to enumerate from to . The computational complexity per step decreases from () for brute force enumeration to () for the length-doubling algorithm.

This method has been used to enumerate up to SBB11.⁠Footnote3 . Then, series analysis gives estimates of and , which are very accurate, but less so than values available from Monte Carlo simulations using the pivot algorithm.

Self-Avoiding Polygons on

The finite lattice method is the most powerful known method for enumerating self-avoiding walks and polygons in two dimensions. We will not go into the details of how it is applied CJ12, but instead will concentrate on communicating the central idea.

For Dyck paths and prudent walks, earlier parts of the walk are independent of later ones. But, this is not a good strategy for self-avoiding walks or polygons, as each step depends on all others. Instead, we use spatial independence, by dividing configurations with a boundary which ensures that the two sides are independent of each other modulo topological information on how the boundary edges can join up. Thus we build configurations site-by-site, instead of step-by-step.

We will describe the simpler case of self-avoiding polygons on the square lattice, but the same method can be applied to self-avoiding walks with minor technical tweaks.

We start by observing that each polygon has a unique minimum bounding rectangle. Therefore, if we wish to enumerate all self-avoiding polygons of steps, we can enumerate all polygons that touch each side of a particular rectangle, and then sum over all possible rectangles. (This is where the moniker “finite lattice method” comes from.)

Next, if we build up this set of polygons in a particular rectangle site-by-site, we do not need to remember all of the details of the polygons that are being generated. Instead, we can enumerate all partial configurations to the left of the boundary of the built-up region that are compatible with a given future topology that specifies how occupied edges on the boundary must be joined up. See Figure 8, which shows two configurations that are compatible with a given boundary; the details of the configurations can be safely forgotten, and it is only necessary to keep track of the boundary state.

Figure 8.

Two partial configurations to the left of the boundary that are compatible with the same boundary topology to the right.

Partial configurations are built up by moving the boundary through the rectangle site-by-site, as shown by the moving boundary in Figure 9.

Figure 9.

The arrow shows how the boundary is deformed so that a particular site (shown as a solid circle) that is initially on the right-hand side of the boundary ends up on the left-hand side of the boundary. The example configuration is a “bad” polygon configuration with many boundary edges, while a set of good columns is shown in green.

Thus, the problem of enumerating self-avoiding polygons of steps has been converted to the problem of enumerating boundary configurations that are compatible with self-avoiding polygons of steps. The efficiency of the method is determined by the number of boundary configurations, which in turn is determined by the maximum number of occupied edges on the boundary. The occurrence of bad configurations, such as in Figure 9, with edges concentrated on a particular column means that the number of boundary configurations grows exponentially with . It can be shown that the algorithmic complexity per step is at most , but the method of pruning JG99CJ12 brings this down to about 1.20.

This is a dramatic improvement over the exponential complexity for the brute force method, which has complexity , and consequently far longer sequences can be generated.

On the square lattice, the finite lattice method has been used to enumerate self-avoiding polygons of up to 130 steps CJ12,⁠Footnote4 . and self-avoiding walks of up to 79 steps Jen13.⁠Footnote5