# Cellular Automata: Does there exist an initial group of cells in a square lattice which never zeroes out completely?

Fix a positive integer $k$.

Given an infinite grid of squares, each of them is assigned a nonnegative integer value. Furthermore, only finitely many of these values are nonzero. Call this state Generation $0$. In Generation $n+1$, a cell is given the value:

• $0$ if the sum of its four neighbors in Generation $n$ was not divisible by $k$;
• $\frac{1}{k}*\text{(The sum of its four neighbors in Generation n)}$ otherwise.

The question is this: Does there exist an initial configuration such that the grid does not eventually become all zeroes?

For $k\ge 4$, the answer is easily no; one can prove this using the sum of all the grid's numbers as a monovariant. For $k\le 2$, the answer is easily yes; for $k=2$ consider two diagonally adjacent "$1$"s. But what about $k=3$??

A similar question can be posed for a hexagonal grid (considering six instead of four neighbors). Here, it is yes for $k\ge 6$ and no for $k\le 3$. But what about $k=4, 5$??

Sidenote: These questions arose when I was fooling around with numbers on graph paper the other day, and I have no idea whether they are solved or open, known or new. Heuristically, it seems that every square configuration should die out for $k=3$, as the sum of all entries will, on average, multiply by $\frac{4}{9}$ after each generation. But there might also exist some extraordinary initial configuration which results in infinite expansion.

Example: The picture below shows a sample when $k=3$ on a square grid (only nonzero entries shown). The grid would die out after Generation 2.

Edit: fixed a typo; now things should be clear.

• You have not said what the fixed integer $k$ has to do with the automaton. Commented Nov 25, 2013 at 23:47
• I have fixed the typo, things should make sense now. Commented Nov 26, 2013 at 1:17
• You are using $4$ neighbours, not $8$, it seems? Commented Nov 26, 2013 at 6:54

For $k=4$, a checkerboard pattern of 1's does not die out.
For $k=3$, the honeycomb pattern does not die out.