|
This article is cited in 4 scientific papers (total in 4 papers)
Discrete Functions
Refined asymptotic estimates for the number of (n,m,k)-resilient Boolean mappings
K. N. Pankovab a Moscow Technological University, Moscow
b Moscow Technical University of Communications and Informatics, Moscow
Abstract:
For linear combinations of coordinate functions of a random Boolean mapping, a local limit theorem for the distribution of subsets of their spectral coefficients is improved. By means of this theorem, we obtain an asymptotic formula for the R(m,n,k)| –the number of (n,m,k)-resilient functions as n→∞, m∈{1,2,3,4} and k≤n(1−ε)5+2log2n for any 0<ε<1, k=O(nlnn):
log2|R(m,n,k)|∼m2n−(2m−1)(n−k2(nk)+log2√π2k∑s=0(ns))++(2⋅3m−2−1)Ind{m≠1}k∑s=0(ns).
Also, we obtain upper and lower asymptotic estimates for the number |R(m,n,k)| as n→∞, k(5+2log2n)+5m⩽ for any 0<\varepsilon<1:
\begin{gather*}
-\varepsilon_1(m-1)\sum_{s=0}^k{n\choose s}<\log _2|R(m,n,k)|-m2^n+(2^m-1)\left(\frac{n-k}2{n\choose k}+\log_2\sqrt\frac\pi2\sum_{s=0}^k{n\choose s}\right)<\\
<\varepsilon_2(m-2)(2^m-1)\sum_{s=0}^k{n\choose s}+\sum_{s=0}^k{n\choose s}\qquad\text{for any}\quad\varepsilon_1,\varepsilon_2\quad(0<\varepsilon_1,\varepsilon_2<1).
\end{gather*}
Keywords:
random binary mapping, local limit theorem, spectral coefficient, resilient vector Boolean function.
Citation:
K. N. Pankov, “Refined asymptotic estimates for the number of (n,m,k)-resilient Boolean mappings”, Prikl. Diskr. Mat. Suppl., 2017, no. 10, 46–49
Linking options:
https://www.mathnet.ru/eng/pdma354 https://www.mathnet.ru/eng/pdma/y2017/i10/p46
|
Statistics & downloads: |
Abstract page: | 176 | Full-text PDF : | 52 | References: | 41 |
|