Nearly Orthogonal Sets over Finite Fields
<|reference_start|>Nearly Orthogonal Sets over Finite Fields: 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 $\delta = \delta (p)$, such that for every field $\mathbb{F}$ of characteristic $p$ and for all integers $k \geq 2$ and $d \geq k^{1/(p-1)}$, there exists a $k$-nearly orthogonal set of at least $d^{\delta \cdot k^{1/(p-1)}/ \log k}$ vectors of $\mathbb{F}^d$. In particular, for the binary field we obtain a set of $d^{\Omega( 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^{\Omega( \log k / \log \log k)}$ (Alon and Szegedy, Graphs and Combin., 1999). The proof combines probabilistic and spectral arguments.<|reference_end|>
@article{chawin2024nearly,
    title={Nearly Orthogonal Sets over Finite Fields},
    author={Dror Chawin and Ishay Haviv},
    journal={arXiv preprint arXiv:2402.08274},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.08274},
    primaryClass={cs.CG cs.DM cs.IT math.CO math.IT}
}