Associative universal gates

The Boolean function NAND is famously universal, in that any Boolean function on n inputs and m outputs can be implemented as a circuit composed entirely of NAND gates. For example, the exclusive-or operation, A XOR B, can be written as:

(A NAND (B NAND B)) NAND (B NAND (A NAND A))

This raises the question: are there any associative universal functions? It is routine to check that none of the 16 two-input Boolean functions are simultaneously associative and universal, but perhaps we can replace the set {true, false} with a larger set such that a function of this form exists?

Even better, can we find a nontrivial finite group G such that any function from G^n to G^m can be implemented as an n-input m-output circuit composed entirely of 2-input ‘multiplication gates’ (which merely multiply the two inputs, viewed as group elements)?

This is not possible if there is a homomorphism from G to [the additive group of] a finite field F: the induced function from F^n to F^m must be linear, and there exist nonlinear functions from F^n to F^m, so certain functions from F^n to F^m are not realisable as a circuit of multiplication gates. It follows that there exist functions from G^n to G^m which are not realisable as a circuit of multiplication gates either.

If the group G is solvable, then it must have a homomorphism to a nontrivial Abelian group (the quotient of G by its commutator subgroup), which in turn has a homomorphism to a nontrivial prime-power cyclic group (by the structure theorem), which is indeed the additive group of a finite field.

Consequently, we can restrict attention to unsolvable groups, the smallest example of which is A_5, the alternating group on five elements.

Universality of group operation in A_5

Let γ = (1 2 3 4 5) and consider the function:

f(x) = ((x^15 γ)^6 γ^4)^4

Usefully, the image of f contains exactly two elements — γ and the identity — which we’ll call ‘true’ and ‘false’.

Following the idea from the proof of Barrington’s theorem, we can also implement Boolean logic gates. Specifically, the elements γ = (1 2 3 4 5), δ = (1 3 5 4 2), and ε = (1 3 2 5 4) are all conjugate to each other in A_5, and ε is the group commutator of γ and δ. A Boolean AND gate (which expects each input to be either the identity or γ) can be implemented by:

• conjugating one of the inputs by an appropriate constant (so that if it were originally γ, it becomes δ);
• taking the commutator of that with the other input (resulting in ε iff both inputs were γ);
• conjugating the output by an appropriate constant (so that the output is γ rather than ε).

Similarly, a NOT gate can be implemented by multiplying the input by γ^4 and then conjugating by an appropriate double-transposition. This means that we can construct arbitrary Boolean logic circuits out of ‘A_5 composition gates’ together with constants.

Finally, since every element of A_5 can be obtained by multiplying together a bunch of conjugates of γ, then for each pair of elements α, β of A_5 we can create a ‘demultiplexer gate’ which outputs α when the input is γ and outputs β when the input is the identity — this is analogous to the ‘ternary operator’ (x ? α : β) familiar from many programming languages.

Consequently, we can implement an arbitrary function from (A_5)^n to A_5 by doing the following:

• for each of the n inputs, multiply it by each of the 60 elements of A_5 and apply f to each of these 60 results (so for each of the n inputs, we get a 60-bit ‘signature’ which acts as an (inefficient!) injective binary encoding of that input);
• apply some complicated Boolean logic circuit composed of the AND and NOT gates described above, which has 60 Boolean outputs (containing a one-hot encoding of the output of the function);
• apply appropriate demultiplexer gates to the outputs (so that one of these 60 outputs is the desired output, and the other 59 outputs are the identity element) and multiply the results together (in any order!).

An arbitrary function from (A_5)^n to (A_5)^m can then be implemented by m non-interacting single-output circuits of the above form, all sharing the same n inputs.

Note that this is a very inefficient construction, but it suffices to establish the universality of the composition gate for A_5-valued logic. We’ll discuss efficiency more in a later post, when we discuss Barrington’s theorem and applications thereof.