On the persistence of zeros

I think I have a proof of the aperiodicity of the center column in Wolfram’s Rule 30 open question.

Outline

  1. Instead of assigning ones and zeros, we’ll be using boolean algebra to represent cell values. This allows us to ratchet up the complexity of the system in a more understandable way. We let $k$ be the number of contiguous variables we start out with, also known as our seed row.
  2. We show that the presence of a pure zero is sufficient to prevent cycling.
  3. We demonstrate by induction that adding a variable to our seed row cannot result in a cycle.

1. Computing Rule 30 as boolean expressions.

The principle is simple. Rather than starting with ones and zeros, we start with an arbitrary number of variables. All subsequent calculations are carried out in the same way. The principle operation is still $f(a,b,c)=a+b+c+bc \pmod 2$.

To give some concept of this, see the three examples below, representing 1-, 2- and 3-variable configurations respectively.

Note that when carrying out the Rule 30 function in this context, we can do some simple optimizing simplification to keep things clean. Exponents can be dropped without effect, as $1^m=1$ and $0^m=0$. Terms with even coefficients can be dropped completely, as they’re modded out, and odd coefficients can be omitted, i.e. an implied $1$.

2. The utility of zero.

This is not to be confused with the more typical $0$ you’d find in a cellular automaton; the $0$s we’re concerned with are boolean expressions, and thus are much more infrequent.

Well, not to start. As you can see in the tables above, the 1-variable version has a roughly equal number of $a$ and $0$ cells. Moving on to the 2-variable version, I believe the expected frequency drops to $1/4$. For the 3-variable version, it drops to $1/8$, and the dropoff becomes steeper from there. At best the expectation for a pure $0$ goes as $2^k$, although I’m still working on whether it could actually be doubly exponential. Fortunately, that’s a detail which doesn’t impact the proof.

We can assign a $1$ value to any single one of our seed variables and effectively horizontally translate the entire structure. If we want, we can even assign values corresponding to a later row, which has the effect of translating the structure vertically. In this case, all we need to realize is that if we encounter a $0$-expression cell, it means that no possible setting of the current seed variables can toggle this bit.

Since we could place our initial $1$ seed cell way to the left, or way to the right, yet have it make no difference, it indicates that the corresponding $k$ cells in the row with the zero are all $0$-valued, in the typical sense. This in turn indicates a “white triangle” of width at least $k$, and implies a vertical run of $0$ cells of at least $k/2$, the height of the triangle.

If we are able to start with an arbitrarily large $k$ and still be guaranteed to find a $0$ (or “null”) expression eventually, that directly implies an arbitrarily large run of $0$ values in the center column. For any alleged period of length $p$, we need only set $k >2p$ and we show such a cycle cannot exist.

3. Proof of existence.

Inspection of boolean tables like the ones above make it clear that when adding one variable at a time to the end of the seed row, the behavior of the resulting values is predictable in some ways. One way to interpret things is that cells may be defined in terms of their left and right neighbors; when adding a variable to the end of the seed row, it equates to values flowing to the right, roughly speaking.

This means that a null expression can only take on some other value if the cell to its immediate left has some other value; to be more clear, upon the addition of a seed variable, a null expression cannot change if the cell to its left is also null.

All we need to show is that there is at least one of these null expressions with a buddy to the left. So here, we use a sort of infinite descent argument. For us to lose all of our null expressions in the column would require that the column to our left had lost all of its nulls after adding the previous seed variable; the cells’ content is additive when treated in this way, and so the same pattern of cells will be filled in each new column.

Leave a comment