All Terminal Bubbles Programs Yield the Elementary Symmetric Polynomials

Abstract

R. L. Graham has discussed various combinatorial aspects of the behavior of magnetic domains or “bubbles“.1 Representing 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_{k} = left{matrix{P_{i} cup P_{i} & {rm if} & k = i cr P_{i} cap P_{i} & {rm if} & k = j cr P_{k} & {rm otherwise}}right}, quad k = 1,cdots, n.$.