Counting equivalence classes for monomial rotation symmetric Boolean functions with prime dimension

摘要

Recently much progress has been made on the old problem of determining the equivalence classes of Boolean functions under permutation of the variables. In this paper we prove an asymptotic formula for the number of equivalence classes under permutation for degree d monomial rotation symmetric (MRS) functions, in the cases where d >= 3 is arbitrary and the number of variables n is a prime. Our counting formula has two main terms and an error term; this is the first instance of such a detailed result for Boolean function equivalence classes which is valid for arbitrary degree and infinitely many n. We also prove an exact formula for the count of the equivalence classes when d = 5; this extends previous work for d = 3 and 4.