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$.
Fulltext:
PDF file (494 kB)