|
Discrete Functions
On quadratic form rank distribution and asymptotic bounds of affinity level
A. V. Cheremushkinab a Academy of Cryptography of Russian Federation, Moscow
b Research Institute "Kvant", Moscow
Abstract:
An affinity level $\operatorname{la}(f)$ of a Boolean function $f$ is defined as minimal number of variable fixations, that produce an affine function. A general affinity level $\mathcal La(f)$ of Boolean function $f$ is defined as minimal number of fixations of variable linear combination values, that produce an affine function. The general affinity level of quadratic form equals $r$ iff the rank of quadratic form equals $2r$. The paper contains some asymptotic properties of the rank of quadratic forms. As a corollary some asymptotic bounds of the general affinity level of quadratic forms are formulated. Let $0\le c\le1$. If $n=2k+\varepsilon$, $0\le\varepsilon\le1$, then for almost all quadratic forms of $n$ variables,
$$
\operatorname{la}(f)\geq\mathcal La(f)\geq k-\left\lceil\sqrt{\frac12\log_2 k}+\frac{c+(-1)^\varepsilon}2\right\rceil+1
$$
as $n\to\infty$.
Keywords:
Boolean functions, affinity level, quadratic form.
Citation:
A. V. Cheremushkin, “On quadratic form rank distribution and asymptotic bounds of affinity level”, Prikl. Diskr. Mat. Suppl., 2016, no. 9, 36–38
Linking options:
https://www.mathnet.ru/eng/pdma262 https://www.mathnet.ru/eng/pdma/y2016/i9/p36
|
Statistics & downloads: |
Abstract page: | 153 | Full-text PDF : | 45 | References: | 36 |
|