RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat. Suppl.: Year: Volume: Issue: Page: Find

 Prikl. Diskr. Mat. Suppl., 2016, Issue 9, Pages 36–38 (Mi pdma262)

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-\lceil\sqrt{\frac12\log_2 k}+\frac{c+(-1)^\varepsilon}2\rceil+1$$
as $n\to\infty$.

Keywords: Boolean functions, affinity level, quadratic form.

DOI: https://doi.org/10.17223/2226308X/9/15

Full text: PDF file (494 kB)
References: PDF file   HTML file

UDC: 519.719.325

Citation: A. V. Cheremushkin, “On quadratic form rank distribution and asymptotic bounds of affinity level”, Prikl. Diskr. Mat. Suppl., 2016, no. 9, 36–38

Citation in format AMSBIB
\Bibitem{Che16} \by A.~V.~Cheremushkin \paper On quadratic form rank distribution and asymptotic bounds of affinity level \jour Prikl. Diskr. Mat. Suppl. \yr 2016 \issue 9 \pages 36--38 \mathnet{http://mi.mathnet.ru/pdma262} \crossref{https://doi.org/10.17223/2226308X/9/15}