On quadratic form rank distribution and asymptotic bounds of affinity level

A. V. Cheremushkin

Prikladnaya Diskretnaya Matematika. Supplement, no. 9 (2016), pp. 36-38

Résumé

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$.

Détail

Keywords: Boolean functions, affinity level, quadratic form.