Orbits of Boolean functions

✍ Scribed by J. Gorodkin

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 434 KB
• Volume: 75
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00092-3

✦ Synopsis

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 22"/(2y+'N!) when N tends to infinity. The probability that a randomly chosen function will belong to an orbit containing the maximum possible number of elements, 2'v+' N!, approaches one as N goes to infinity. Simulations for N <6 are in agreement with the scaling predictions.