All Terminal Bubbles Programs Yield the Elementary Symmetric Polynomials

R. L. Graham has discussed various combinatorial aspects of the behavior of magnetic domains or “bubbles“.1Representing the initial state of a configuration of n magnetic domains by the n-tuple of indeterminates B = (X1, …, Xn), he showed that subsequent configurations of magnetic domains obtainable (within the constraints of the problem) correspond exactly to subsequent n-tuples of Boolean expressions in the Xi's∗obtainable from B through an application to B of a product of transformations (“commands” in Ref. 1) of the form Tij(1 ≦ j … n) where if P = (P1, …, Pn) is an n-tuple of Boolean expressions in the Xi's, then Tij(P) = (Q1…, Qn),Qₖ = ᵢ ∪ Pᵢ & if & k = i Pᵢ ∩ Pᵢ & if & k = j Pₖ & otherwise\, k = 1,⋯, n..