Counting Balanced Boolean Functions in n Variables with Bounded Degree

Abstract

We consider the problem of obtaining good upper and lower bounds on the number of balanced Boolean functions in n variables with degree less than or equal to k. This is the same as the problem of finding bounds on the number of codewords of weight 2^n-1 in the Reed–Muller code of length 2ⁿ and order k. We state several conjectures and use them to obtain good bounds. We believe that the conjectures will be highly useful for further research.

Keywords:

• Primary 94C10
• Secondary 94B65, 11T71
• Boolean functions
• balanced
• Reed-Muller codes