Orbits of Boolean functions

J. Gorodkin
Discrete Applied Mathematics 75, 269-275, 1997.


The group of congruences and permutations of the two-colored N-dimensional Boolean cube is considered. The total number of orbits generated by these automorphisms are shown to scale as 22N/(2N+1N!) when N tends to infinity. The probability that a randomly chosen function will belong to an orbit containing the maximum possible number of elements, 2N+1N!, approaches one as N goes to infinity. Simulations for N<=6 are in agreement with the scaling predictions.

Keyword(s): Boolean functions; Orbits; Equivalence classes; Counting; Neural networks