Hamming weights of correlation immune Boolean functions

The set of correlation immune (CI) Boolean functions can be partitioned int o several disjoint sets depending on the Hamming weight of their output col umn. We show that the number of n variable CI functions of Hamming weight 2 a + 2 is strictly greater than the number of such functions of weight 2a fo r 2a < 2(n-1). This seemingly intuitive result turns out to be quite diffic ult to prove. The combinatorial structure of CI functions revealed here red uces the enumeration problem of CI functions to the enumeration problem of balanced CI functions. (C) 1999 Elsevier Science B.V. All rights reserved.