The carry of Rule 30

The identity (proved)

x(i, t+1) = x(i−1, t) XOR x(i, t) XOR c(i, t)
c(i, t)   = (1 − x(i, t)) · x(i+1, t)  =  x(i+1, t) · x(i+1, t+1)

The first line is the rule itself, written as the Gray step plus a correction. The second line is the discovery: the correction equals the AND of the column to the right at two consecutive times. Proof in one line: if x(i+1, t) = 1 the rule gives x(i+1, t+1) = 1 − x(i, t), which is the correction; if x(i+1, t) = 0 both sides are 0. Equivalently, in space-time form, x(i, t+1) XOR x(i+1, t) x(i+1, t+1) = x(i−1, t) XOR x(i, t).

The arithmetic twin

Multiplying a binary number by three is the same Gray step plus carries: bit k of 3n is n_k XOR n_k−1 XOR carry. Rule 30 is Rule 60 plus a one-cell correction; the powers of three are Rule 60 plus the carries of an addition. That is the sense in which Rule 30 sits beside Collatz and Mahler's 3/2 problem: one XOR skeleton, and a nonlinearity that is a carry.

The column carry, solved exactly under the coin measure (proved)

Fill the whole line with fair coins, which Rule 30 preserves. Then every column is a sequence of independent fair coins, and by the identity the carry feeding a column, c(t) = a(t)·a(t+1) with a the column to its right, is the sliding AND of fair coins: a two-state hidden chain, not a Markov chain of any finite order. Its correlation is exactly 1/3 at lag 1 and exactly 0 at every larger lag. The chance of a carry, given that the previous m steps carried nothing, is F(m+1) / (2 F(m+3)) with F the Fibonacci numbers: 1/6, 1/5, 3/16, 5/26, 4/21, 13/68 for m = 1..6. Its entropy rate is

h = 1 − (1/16) Σg≥1 F(g) 2−g log₂ F(g) = 0.69924320338768 bits per step.

Along the leftward light-speed diagonal the carry is independent Bernoulli(1/4); along the rightward one it has long memory. On rings, the count of carries per row has no finite transition matrix of Holte's kind (the owner's question), while the count of adjacent black pairs nearly does, with spectrum near the powers of −1/2.