All Terminal Bubbles Programs Yield the Elementary Symmetric Polynomials
Robert P. Kurshan · Bell System Technical Journal · 1970
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_{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.$.