Classification of Boolean functions under the affine group
This page reports the numerical experiments related to the classification of the Boolean Functions in less than 7 variables that I computed in November in 2009.
Let m be a positive integer. The space of Boolean functions from GF(2)^m into GF(2) is denoted by RM(k,m). This notation comes from coding theory, it is the Reed-Muller code of order k in m variables. The affine group AG(2, m) acts over the spaces RM(k,m), and thus on RM(k,m)/RM(s,m) when s<=k. Two Boolean functions f and g are said to be equivalent modulo RM(k, m) if there exists an affine transformation A in AG(2,m) such that
The affine group has order :
it can be generated by three transformations : the shift S, a transvection T and a nontrivial translation U. The affine group acts over RM(k,m) and also over RM(k,m)/RM(s,m). A formula for the rank n(m,s,k) of the action of AG(2,m) over RM(k,m)/RM(s,m) ( s<=k ) was determined by Xiang-Dong Hou,
AGL(m, 2) Acting on R(r, m)/R(s, m), journal of algebra 171/3 (1995) It satisfies :The main objective of this numerical experiment was to rebuild the data of the n(6,1,6) = 150357 classes of Boolean functions obtained in a nice way by James Maiorana. See,
A classification of the cosets of the Reed-Muller code R(1,6) Math. Comp. 57 (1991). Indeed, in his paper Maiorana gives global information on the data but not the details that are somewhere on some microfilms... For people who like cardinality group : There exists recent papers with similar classification. For example, An Braeken, Yuri L. Borissov, Svetla Nikova, Bart Preneel: Classification of Boolean Functions of 6 Variables or Less with Respect to Some Cryptographic Properties. The very simple (almost naive) method that I used to obtain the classifications below work very well for all the cases, and could be used for classification in seven variables but it was not my goal. h = 0
G = S, T, U
fix= #GA(m)
h=x_1 x_2 ... x_m
S, T, U
fix= #GA(m)
We proceed by descent to obtain the classification modulo RM(m-2,m), modulo RM(m-3,m),... From a class h modulo RM(k,m), we construct the class modulo RM(k-1,m), using the action of fix(h) over RM(k-1,m). Note that if h is is fixed by A, the action of A on h+f, where f lies in RM(k-1,m), is given by the relation :
That is the usual action of A on f, plus a boundary term h+h^A. We use a naive algorithm to calculate the orbits of RM(k-1,m) under the action f -> h + h^A + f^A modulo RM(k-2,m). If the orbit size of f is N, then the fixator of h+f has order #fix(h)/N and we can use Schreier-Sims method to compute the fixator of h+f. In particular, for the classification of RM(6,6), we only need to work with binomial(6,3) = 20 bits vectors.
h = Boolean functions.
List of the Generators of the fixator group of h
fix = order of the fixator group.
pl@fedora/agl> ./anfload.exe -m6 -f class-2-6.txt -d3 -z0 -p"%x%n%s"displays 10 classes of function of degree 3 in 6 variables from the file class-2-6.txt such that Walsh coedfficient do not vanish...
#command line : ./anfload.exe -m6 -f class-2-6.txt -d3 -z0 -p%x%n%s --- selected 6-bit functions : anf=abc+cd+be+af 28 [-8] 36 [8] anf=bd+cd+acd+abe+ce+af 28 [-8] 36 [8] anf=ad+bd+cd+bcd+be+ce+ace+abf+cf 28 [-8] 36 [8] anf=cde+abf 6 [-12] 24 [-4] 25 [4] 8 [12] 1 [36] anf=ac+cde+abf 6 [-12] 25 [-4] 24 [4] 6 [12] 2 [20] 1 [28] anf=bc+ad+cde+abf 7 [-12] 24 [-4] 22 [4] 8 [12] 3 [20] anf=bd+ae+cde+abf+cf 9 [-12] 20 [-4] 22 [4] 12 [12] 1 [20] anf=ace+bce+bde+bcf+adf 45 [-4] 18 [12] 1 [28] anf=ab+ace+bce+bde+bcf+adf 15 [-12] 46 [4] 3 [20] anf=ab+cd+ace+bce+bde+bcf+adf 1 [-20] 42 [-4] 21 [12] # 10 Boolean functions among 150357 classes