RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1991 Volume 3, Issue 2, Pages 25–46 (Mi dm785)

This article is cited in 10 papers

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

O. V. Denisov


Abstract: 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$).

UDC: 519.716

Received: 25.04.1990


 English version:
Discrete Mathematics and Applications, 1992, 2:4, 407–426

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024