On the rank of random quadratic form over finite field | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 35. DOI: 10.17223/20710410/35/3

The weights of Boolean functions of degree two are closely related to the ranks of quadratic forms. Though the weights of Reed - Muller codes are intensively researched in coding theory, the ranks of quadratic forms are not sufficiently studied. The article contains some asymptotic properties of the rank of a random quadratic form f(ж1,...,ж_п) = E ijij over finite field GF(q). The cases of odd and Uneven characteristics are separately considered. If q is odd, then the rank(f) of f is defined as the rank of the symmetric matrix (b_ij) with b_ii = a_ii, b_ij = (a_ij + a_ji)/2, j = i, 1 ^ i, j ^ n. It is proved that, for any odd q and 0 < с < 1, the lower bound for the rank of the almost all quadratic forms f in n variables is the following: rank(f) ^ n - [д/2log_qn + c| + 1 as n ^ те. In the case of even q, the rank(f) of f is defined as the rank of a bilinear form f (ж + y) + f (ж) + f (y). If q = 2, m ^ 1, n = 2k + e, e € {0,1}, 0 < с < 1, then the lower bound for the rank of the almost all quadratic forms f in n variables is the following: + 2 as k ^ те. An another form of 2"' 4 this inequality is rank(f) > n - [д/2 log_q n + с| +1, where 0 < с' < 1. As a corollary, an asymptotic lower bound for the minimal size ^o(G) of a vertex cover of a graph G with n vertices is obtained. The vertex cover of G is a set S of vertices in G such that every arc in G is incident to a vertex in S. Let n = 2k + e, e = 0,1, с > 0. Then for the almost all graphs G with n vertices, the lower bound for the minimal vertex cover 1log„ k + +<1> rank(f) ^ 2k - 2 size is the following: e₀(G) ^ k - ilog₂ k + + 1 as k ^ те.