Nearly Orthogonal Sets over Finite Fields

Abstract

For a field $\mathbb{F}$ and integers $d$ and $k$, a set of vectors of ${\mathbb{F}}^d$ is called $k$-nearly orthogonal if its members are non-self-orthogonal and every $k+1$ of them include an orthogonal pair. We prove that for every prime $p$ there exists a positive constant $\hat{I}´=\hat{I}´(p)$, such that for every field $\mathbb{F}$ of characteristic $p$ and for all integers $k\ge 2$ and $d\ge k^{1/(p-1)}$, there exists a $k$-nearly orthogonal set of at least $d^{\hat{I}´\cdot k^{1/(p-1)}/\log k}$ vectors of ${\mathbb{F}}^d$. In particular, for the binary field we obtain a set of $d^{\hat{I}\text{c◯}(k/\log k)}$ vectors, and this is tight up to the $\log k$ term in the exponent. For comparison, the best known lower bound over the reals is $d^{\hat{I}\text{c◯}(\log k/\log \log k)}$ (Alon and Szegedy, Graphs and Combin., 1999). The proof combines probabilistic and spectral arguments.

19 pages