On the Number of Affine Equivalence Classes of Boolean Functions

07/24/2020

∙

by   Xiang-dong Hou, et al.

∙

0

∙

share

Let R(r,n) be the rth order Reed-Muller code of length 2^n. The affine linear group AGL(n, F_2) acts naturally on R(r,n). We derive two formulas concerning the number of orbits of this action: (i) an explicit formula for the number of AGL orbits of R(n,n), and (ii) an asymptotic formula for the number of AGL orbits of R(n,n)/R(1,n). The number of AGL orbits of R(n,n) has been numerically computed by several authors for n≤ 10; result (i) is a theoretic solution to the question. Result (ii) answers a question by MacWilliams and Sloane.