The Still-Life Density Problem and its Generalizations
View/ Open
Elkies - The still-Life density problem (277.4Kb)
Access Status
Full text of the requested work is not available in DASH at this time ("restricted access"). For more information on restricted deposits, see our FAQ.Author
Metadata
Show full item recordCitation
Elkies, Noam D. 1998. The still-life density problem and its generalizations. In Voronoi's Impact on Modern Science, Book I. Proceedings of the Institute of Mathematics of the National Academy of Sciences of Ukraine,21:228-253. [Kiev], Ukraine: Institute of Mathematics.Abstract
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.
Other Sources
http://arxiv.org/abs/math/9905194Citable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:3351711
Collections
- FAS Scholarly Articles [18292]
Contact administrator regarding this item (to report mistakes or request changes)