The still-Life density problem and its generalizations
Abstract
Description
A "still Life" is a subset S of the square lattice Z^2 fixed under the transition rule of Conway's Game of Life, i.e. a subset satisfying the following three conditions:
1. No element of Z^2-S has exactly three neighbors in S;
2. Every element of S has at least two neighbors in S;
3. Every element of S has at most three neighbors in S.
Here a ``neighbor'' of any x \in Z^2 is one of the eight lattice points closest to x other than x itself. The "still-Life conjecture" is the assertion that a still Life cannot have density greater than 1/2 (a bound easily attained, for instance by {(x,y): x is even}). We prove this conjecture, showing that in fact condition 3 alone ensures that S has density at most 1/2. We then consider variations of the problem such as changing the number of allowed neighbors or the definition of neighborhoods; using a variety of methods we find some partial results and many new open problems and conjectures.
29 pages, including many figures drawn as LaTeX "pictures"
29 pages, including many figures drawn as LaTeX "pictures"