|
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\to\infty$, $m\in\{1,2,3,4\}$ and $k\leq\frac{n(1-\varepsilon)}{5+2\log _2n}$ for any $0<\varepsilon <1$, $k=\mathrm O(\frac n{\ln n})$:
\begin{gather*}
\log _2|R(m,n,k)|\sim 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)+\\
+(2\cdot3^{m-2}-1)\mathrm{Ind}\{m\neq1\}\sum_{s=0}^k{n\choose s}.
\end{gather*}
Also, we obtain upper and lower asymptotic estimates for the number $|R(m,n,k)|$ as $n\to\infty$, $k(5+2\log _2n)+5m\le n(1-\varepsilon)$ 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: | 145 | Full-text PDF : | 45 | References: | 36 |
|