Dense Stable Patterns

Noam Elkies has shown in his paper The still-Life density problem and its generalizations that a stable pattern in Conway's Life cannot have a density of more than 0.5. This immediately implies that a stable n×n pattern cannot have a population in excess of (n²+2n+1)/2. For small enough n it is feasible to compute exactly the maximum population that a stable n×n pattern can have. I will denote this population by P(n). I computed the value of P(n) for n<11 in February 2000, and put up this webpage a few weeks later. Later I found out that these values (and more) had already been calculated by Robert Bosch, who has published a paper on the subject, and another paper dealing with the equivalent problem in two related cellular automata. Links to copies of these papers can be found on Robert Bosch's web-site. There is another paper on the subject by Barbara M. Smith.

First note that P(n) = ½n² + O(n), because of the upper bound shown above and the possibility of using still-lifes like the one in the following diagram.

In the following table, the attained by column describes the pattern or patterns that attain the population P(n). The d0 and d1 columns give the density of these patterns (to 4 decimal places) considered as subsets of the n×n square (in the case of d0) or as subsets of a surrounding (n+1)×(n+1) square (in the case of d1). The results for n<5 are trivial. The n=6 and n=7 results were probably first determined by Harold McIntosh in September 1992. Results for higher values of n are due to Robert Bosch.

 n   P(n)  attained by           d0       d1

 1    0    vacuum              0.0000   0.0000
 2    4    block               1.0000   0.4444
 3    6    ship                0.6667   0.3750
 4    8    pond or long ship   0.5000   0.3200
 5   16    four blocks         0.6400   0.4444
 6   18    (see Note 1)        0.5000   0.3673
 7   28    (see Note 2)        0.5714   0.4375
 8   36    nine blocks         0.5625   0.4444
 9   43    (see Note 3)        0.5309   0.4300
10   54    (see Note 4)        0.5400   0.4463
11   64    (see Note 4)        0.5289   0.4444
12   76    (see Note 4)        0.5278   0.4497
13   90    (see Note 4)        0.5325   0.4592

Note 1.
The following are the 6×6 stable patterns of population 18.

Note 2.
The following is the 7×7 stable pattern of population 28.

Note 3.
The following are the 9×9 stable patterns of population 43.

Note 4.
There are hundreds of 10×10 stable patterns of population 54. I have made no attempt to sort them out, but if you want to see the unsorted file then you can download it (19K gzipped ASCII file). Example 10×10, 11×11, 12×12 and 13×13 stable patterns of maximum density are shown below.

Some maximally dense NxN stable patterns for N=10,...,13

To My Life Page To Life Lexicon Home Page

This page is maintained by Stephen Silver
(e-mail: life

argentum.freeserve.co.uk)
Last updated: 2002 Sep 20
Original URL: http://www.argentum.freeserve.co.uk/dense.htm