On the rank of random quadratic form over finite field

A. V. Cheremushkin

Prikladnaâ diskretnaâ matematika, no. 1 (2017), pp. 29-37.

Résumé

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(x_1,\dots,x_n)=\sum_{1\le i,j\le n}a_{ij}x_ix_j$ over finite field $\mathrm{GF}(q)$. The cases of odd and even characteristics are separately considered. If $q$ is odd, then the $\mathrm{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\neq i$, $1\le i,j\le n$. It is proved that, for any odd $q$ and $0$, the lower bound for the rank of the almost all quadratic forms $f$ in $n$ variables is the following: $\mathrm{rank}(f)\geq n-\left\lceil\sqrt{2\log_q n}+c\right\rceil+1$ as $n\to\infty$. In the case of even $q$, the $\mathrm{rank}(f)$ of $f$ is defined as the rank of a bilinear form $f(x+y)+f(x)+f(y)$. If $q=2^m$, $m\ge1$, $n=2k+\varepsilon$, $\varepsilon\in\{0,1\}$, $0$, then the lower bound for the rank of the almost all quadratic forms $f$ in $n$ variables is the following: $\mathrm{rank}(f)\geq 2k-2\left\lceil\sqrt{\dfrac12\log_qk}+\dfrac{c+(-1)^\varepsilon}4\right\rceil+2$ as $k\to\infty$. An another form of this inequality is $\mathrm{rank}(f)>n-\left\lceil\sqrt{2\log_q n}+c'\right\rceil+1$, where $0$. As a corollary, an asymptotic lower bound for the minimal size $\beta_0(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+\varepsilon$, $\varepsilon=0,1$, $c>0$. Then for the almost all graphs $G$ with $n$ vertices, the lower bound for the minimal vertex cover size is the following: $\beta_0(G)\ge k-\left\lceil\sqrt{\dfrac12\log_2 k}+\dfrac{c+(-1)^\varepsilon}4\right\rceil+1$ as $k\to\infty$.

Détail

Keywords: finite field, symplectic group, quadratic form.

Bibliographie

[1] Dixon L. E., Linear Groups with an Expositions to the Galois Field Theory, Publ. by B. G. Teubner, Leipzig, 1901

[2] Mullen G. L., Panario D., Handbook of Finite Fields, CRC Press, A Chapman Hall Book, 2013 | Zbl

[3] D'edonne Zh., Geometry of Classical Groups, Mir Publ., Moscow, 1974 (in Russian) | MR

[4] MacWilliams F. J., Sloane N. J. A., The Theory of Error-Correcting Codes, North Holland, 1977 | MR | Zbl

[5] Burbaki N., Algebra: Modules, Rings Forms, Nauka Publ., Moscow, 1960 (in Russian) | MR