Improved asymptotic estimates for the number of correlation-immune Boolean functions and mappings

K. N. Pankov

Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 49-52

Résumé

For linear combinations of coordinate functions of a random Boolean mapping from the vectorspace $V_n$ of all binary vectors of length $n$ to the vectorspace $V_m$, the local limit theorem for the joint distribution of weights of some their subfunctions is improved. By means of this theorem, we have obtained an asymptotic formula for $|K(m,n,k)|$ that is the number of correlation-immune of order $k$ functions as $n\to\infty$, $m\in\{2,3,4\}$ and $k(5+2\log_2n)+6m\le n(\frac5{18}-\gamma')$ for any $0\gamma'5/18$, $k=\mathrm O(n/\ln n)$: \begin{gather*} \log _2|K(m,n,k)|\sim m2^n+\left(\frac{n+1+\log_2\pi}2-k\right)(2^m-1)-m2^{m-1}-\\ -(2^m-1)\left(\frac{n-k}2{n\choose k}+\log_2\sqrt\frac\pi2\sum_{s=0}^k{n\choose s}\right)+(2\cdot3^{m-2}-1)\sum_{s=0}^k{n\choose s}. \end{gather*} Also, we have obtained improved asymptotic estimates for the number $|K(n,1,k)|$ as $n\to\infty$, $k\frac n{\ln n}\left(\frac{\ln2}4-\varepsilon\right)$ for any $0\varepsilon\ln2/4$: \begin{gather*} \log_2|K[n,1,k]|\sim2^n-\frac12\left((n-k){n\choose k}-n\right)-k-\\ -\left(\frac{n-k}2{n\choose k}+\sum_{s=0}^k{n\choose s}\log_2\sqrt\frac\pi2-1\right)\log_2\sqrt{\pi/2}. \end{gather*}

Détail

Keywords: random binary mapping, local limit theorem, weights of subfunctions, correlation-immune function.