On the Number of Affine Equivalence Classes of Boolean Functions

2020/07/24 by Hou, Xiang-dong
#06E30 #20G40 #94B05 #94D10 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2007.12308

Abstract

Let R(r,n) be the rth order Reed-Muller code of length 2ⁿ. The affine linear group AGL(n,\Bbb F₂) 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.

Related

• Computing the Number of Equivalent Classes on R(s,n)/R(k,n)
• Classification of some cosets of Reed-Muller codes
• Asymptotically optimal Boolean functions
• Codes from A_m-invariant polynomials
• On the number of equivalence classes of invertible Boolean functions under action of permutation of variables on domain and range