|
This article is cited in 2 scientific papers (total in 2 papers)
Discrete Functions
Improved asymptotic estimates for the number of correlation-immune Boolean functions and mappings
K. N. Pankov Moscow Technical University of Communications and Informatics, Moscow
Abstract:
For linear combinations of coordinate functions of a random Boolean mapping from the vectorspace Vn of all binary vectors of length n to the vectorspace Vm, 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→∞, m∈{2,3,4} and k(5+2log2n)+6m⩽n(518−γ′) for any 0<γ′<5/18, k=O(n/lnn):
\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*}
Keywords:
random binary mapping, local limit theorem, weights of subfunctions, correlation-immune function.
Citation:
K. N. Pankov, “Improved asymptotic estimates for the number of correlation-immune Boolean functions and mappings”, Prikl. Diskr. Mat. Suppl., 2018, no. 11, 49–52
Linking options:
https://www.mathnet.ru/eng/pdma405 https://www.mathnet.ru/eng/pdma/y2018/i11/p49
|
Statistics & downloads: |
Abstract page: | 174 | Full-text PDF : | 42 | References: | 27 |
|