An asymptotic formula for the number of correlation-immune Boolean functions of order~$k$

O. V. Denisov

Diskretnaya Matematika, Tome 3 (1991) no. 2, pp. 25-46.

Résumé

We obtain an asymptotic formula for the $N(n,k)$-number of correlation-immune Boolean $n$-variable functions of order $k$. We prove that as $n\to\infty$ $$ N(n,k)\sim\frac{2^{2^n}}{2^k\exp\biggl(\sum_{i=1}^k\Bigl(\ln\sqrt\frac{\pi}2+\Bigl(\frac n2-i\Bigr)\ln2\Bigr)\binom ni\biggr)}\,, $$ where $k$ is a fixed constant that does not depend on $n$ $(k=1,2,\dots$).