What are the densest regular patterns that cover the plane in Conway's game of Life?

competition/games/life.density New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

What are the densest regular patterns that cover the plane in Conway's
game of Life?

I'm interested in finding regular patterns in Conway's "life", that
cover the plane as densely as possible.

What are the greatest densities achievable -

(i) with a time-periodic pattern, preferably stationary;

(ii) that preferably contains no groups of live cells infinite in
extent.

-- Bill Taylor <wft@math.canterbury.ac.nz>

Show solution

Bill Taylor (wft@math.canterbury.ac.nz) wrote:
: (i) with a time-periodic pattern, preferably stationary;

The cute name for a period-1 pattern is a "still life".  It seems 1/2
is the greatest possible density.  Noam Elkies outlined a proof
approach for the stronger result that no pattern of maximum adjacency
degree 3 can have density over 1/2.  I'm not sure he's polished it
into a complete proof yet.  Here are some density-1/2 still-lifes,
mostly from Noam and earlier sources.

                                 Chicken wire
 . x x x x . . . . x x x x    . . x x . . x x . .
 . x . . x . x x . x . . x    x x . . x x . . x x
 . x . . x . x x . x . . x    . . x x . . x x . .
 . x x x x . . . . x x x x    x x . . x x . . x x
 x . . . . x x x x . . . .    . . x x . . x x . .
 x . x x . x . . x . x x .    x x . . x x . . x x
 x . x x . x . . x . x x .    . . x x . . x x . .
 x . . . . x x x x . . . .    x x . . x x . . x x

 x x . . x x x x . . x x          x x x x . x x x x . x x x x
 . x . x . . . x . x . .          x . . x . x . . x . x . . x
 x . . x x x x . . x x x          x . . x . x . . x . x . . x
 . x x . . . . x x . . .          x x x x . x x x x . x x x x
 x . . x x x x . . x x x          . . . . x . . . . x . . . .
 . x . x . . . x . x . .          . x x . x . x x . x . x x .
 x x . . x x x x . . x x          . x x . x . x x . x . x x .
 . . x x . . . . x x . .          . . . . x . . . . x . . . .
                                  x x x x . x x x x . x x x x
 . . . . x . . . . x . . . . x    x . . x . x . . x . x . . x
 x x x x . x x x x . x x x x .    x . . x . x . . x . x . . x
 x . . x . x . . x . x . . x .    x x x x . x x x x . x x x x
 x . x . . x . x . . x . x . .    . . . . x . . . . x . . . .
 x . x x x x . x x x x . x x x    . x x . x . x x . x . x x .
 . x . . . . x . . . . x . . .    . x x . x . x x . x . x x .
 . x . x x . x . x x . x . x x    . . . . x . . . . x . . . .
 . x . x x . x . x x . x . x x
 . x . . . . x . . . . x . . .
 x . x x x x . x x x x . x x x        x x x x . x x x x .
 x . x . . x . x . . x . x . .        . . . . x . . . . x
 . . x . x . . x . x . . x . x        . x x . x . x x . x
 x x x . x x x x . x x x x . x        . x . x x . x . x x
                                      . x . . . . x . . .
                                      x . x x x x . x x x
 x x x x x x x x . . . . . . . .      x . x . . x . x . .
 x . . . . . . x . x x x x x x .      x . x . . x . x . .
 x . x x x x . x . x . . . . x .      x . x x x x . x x x
 x . x . . x . x . x . x x . x .      . x . . . . x . . .
 x . x . . x . x . x . x x . x .      . x . x x . x . x x
 x . x x x x . x . x . . . . x .      x x . x . x x . x .
 x . . . . . . x . x x x x x x .      . . . x . . . . x .
 x x x x x x x x . . . . . . . .      x x x . x x x x . x
 . . . . . . . . x x x x x x x x
 . x x x x x x . x . . . . . . x
 . x . . . . x . x . x x x x . x      x x x x . . x x x x . .
 . x . x x . x . x . x . . x . x      x . . . x . x . . . x .
 . x . x x . x . x . x . . x . x      . x x x x . . x x x x .
 . x . . . . x . x . x x x x . x      . x . . . x . x . . . x
 . x x x x x x . x . . . . . . x      . . x x x x . . x x x x
 . . . . . . . . x x x x x x x x      x . x . . . x . x . . .

: (ii) that preferably contains no groups of live cells infinite in
: extent.

Well, the above qualify, but my favorite still life (because it's my
own invention) is the following:

 . . . x x x x x x x x x x
       . . . . . . . . . x
       x x x x x x x x . x
       x . . . . . . x . x
       x . x x x x . x . x
       x . x . . x . x . x
       x . x . . x . x . x
       x . x . x x . x . x
       x . x . x . . x . x
       x . x . x . . x . x
       x . x . x x x x . x
       x . x . . . . . . x
       x . x x x x x x x x
       x . . . . . . . . .
       x x x x x x x x x x . . .

Not only does it have an infinite connected group, it _is_ an infinite
connected group.  Rich Schroeppel has shown that there is no finite
connected still-life other than the 2x2 block, but this can be
modified by adding spirals to make uncountably many infinite connected
still-lifes.  I don't know if there's any i.c.s-l. that is not made up
of such spirals, though.  Could there be one that has lacunae?

-- Dan Hoey <Hoey@AIC.NRL.Navy.Mil>