On quadratic form rank distribution and asymptotic bounds of affinity level

An affinity level la(f) of a Boolean function f is defined as minimal number of variable fixations, that produce an affine function. A general affinity level 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 ^ c ^ 1. If n = 2k + e, 0 ^ e ^ 1, then for almost all quadratic forms of n variables, as n ^ го.

Keywords

Authors

References