11
$\begingroup$

I've read that Conway's Game of Life (CGOL) can have unbounded growth from a finite initial number of alive cells (e.g. a glider gun). However, if CGOL is played on a torus, space (the number of cells) becomes finite, and glider guns are guaranteed to eventually destructively interfere with themselves.

Because of this, I wondered about the maximum proportion of alive cells on a torus. To be specific,

What is the maximum stable density of alive cells in CGOL on a torus, where density means proportion of alive cells out of all cells, and stable means this density occurs infinitely many times (as opposed to the recurrence of position: a glider might have nonperiodic position, but stable density)

Please let me know if my question is ambiguous, poorly phrased, or self-contradictory - I struggle to be precise with my questions.

$\endgroup$
2
  • 2
    $\begingroup$ If you fix the configuration of cells on the torus, with a fixed number of cells, it follows that the set of CGOL positions is finite, and therefore every CGOL game on that torus is eventually periodic. So the maximum stable density on that torus is the same as the maximum density of a periodic position. $\endgroup$
    – Lee Mosher
    Jun 23 '21 at 20:47
  • $\begingroup$ But then one might ask how the maximum stable density varies as one changes the configuration of cells on the torus. $\endgroup$
    – Lee Mosher
    Jun 23 '21 at 20:50
5
$\begingroup$

In the specific case of a pattern that is fixed under the rules of the Game of Life, the maximum density is 1/2, as shown by Noam Elkies in The still-Life density problem and its generalizations.

Elkies also presents (on page 22) a simple example of a period 6 oscillator with maximum density 3/4. Here are all its phases: \begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&1&0&0&0&0&0&0\\ \hline 1&1&0&0&0&0&0&0\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0&0&1&0&0&0&0&1\\ \hline 0&0&1&0&0&0&0&1\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&1&1&1&0&0&1&1\\ \hline 1&1&1&1&0&0&1&1\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0&0&0&0&1&1&0&0\\ \hline 0&0&0&0&1&1&0&0\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0&0&0&1&0&0&1&0\\ \hline 0&0&0&1&0&0&1&0\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 0&0&1&1&1&1&1&1\\ \hline 0&0&1&1&1&1&1&1\\ \hline \end{array}

$\endgroup$
6
  • $\begingroup$ Could you correct your hyperlink? Thank you! $\endgroup$ Jun 23 '21 at 21:06
  • $\begingroup$ I believe you meant to link to arxiv.org/pdf/math/9905194.pdf $\endgroup$ Jun 23 '21 at 21:08
  • $\begingroup$ @RonShvartsman Thanks, I fixed it. I also noticed that Elkies includes an example of an oscillator attaining density 3/4 and added it to the answer. $\endgroup$ Jun 23 '21 at 21:36
  • $\begingroup$ @EricMSchmidt Thank you for the answer! However, I found myself a little lost in the language of the paper; is it true that the author deals with a toroidal lattice at the beginning of section B, when they state, "[We can] change the definition of adjacency in L so x, y are adjacent only if they differ by a unit vector, so each x ∈ L has 4 neighbors ... We then define δ4(n) to be the maximum density of a set S ⊆ L each of whose elements has at most n neighbors in L relative to this smaller 4-point neighborhood"? $\endgroup$ Jun 23 '21 at 23:18
  • 1
    $\begingroup$ @RonShvartsman The paper defines things using an infinite square lattice rather than a torus. However a pattern on a torus is equivalent to an infinite doubly periodic pattern. So you can view the period 6 oscillator as being on a torus if you like. $\endgroup$ Jun 24 '21 at 0:48
2
$\begingroup$

I think it'll be hard to beat

\begin{array}{|c|c|} \hline 1&1\\ \hline 0&0\\ \hline \end{array}

$\endgroup$
3
  • $\begingroup$ It would be interesting to know what the maximum stable density on a torus with two odd dimensions would be. $\endgroup$ Jun 23 '21 at 20:52
  • $\begingroup$ Good point Bram28, this seems a reasonable lower bound. However, I'm hoping that someone could provide an analytical method for dealing with such a question. $\endgroup$ Jun 23 '21 at 20:56
  • 1
    $\begingroup$ @RonShvartsman I know ... someone smarter than I am may be able to do that :P Anyway, here's my candidate winner. Nice question! $\endgroup$
    – Bram28
    Jun 23 '21 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.