This article is cited in
1 paper
Theoretical Foundations of Applied Discrete Mathematics
On the rank of random quadratic form over finite field
A. V. Cheremushkin Technology Federal State Unitary Enterprise "Research Institute Kvant", Moscow, Russia
Abstract:
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<c<1$, 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<c<1$, 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<c'<1$. 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$.
Keywords:
finite field, symplectic group, quadratic form.
UDC:
519.719.1
DOI:
10.17223/20710410/35/3
Fulltext:
PDF file (588 kB)