The Still-Life Density Problem and its Generalizations
| Title: | The Still-Life Density Problem and its Generalizations |
| Author: | Elkies, Noam David |
| Citation: | 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. |
| Access Status: | At the direction of the depositing author this work is not currently accessible through DASH. |
| Full Text & Related Files: |
Elkies - The still-Life density problem.pdf (284.1Kb; PDF) 
|
| 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/9905194 |
| Citable link to this page: | http://nrs.harvard.edu/urn-3:HUL.InstRepos:3351711 |
This item appears in the following Collection(s)
-
FAS Scholarly Articles [5137]
Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
Contact administrator regarding this item (to report mistakes or request changes)
