Multipartite nearly orthogonal sets over finite fields

Abstract

For a field $\mathbb{F}$ and integers $d,k$ and $\ell$, a set $A\subseteq {\mathbb{F}}^d$ is called $(k,\ell )$-nearly orthogonal if all vectors in $A$ are non-self-orthogonal and every $k+1$ vectors in $A$ contain $\ell +1$ pairwise orthogonal vectors. Recently, Haviv, Mattheus, Milojević and Wigderson have improved the lower bound on nearly orthogonal sets over finite fields, using counting arguments and a hypergraph container lemma. They showed that for every prime $p$ and an integer $\ell$, there is a constant $\hat{I}´(p,\ell )$ such that for every field $\mathbb{F}$ of characteristic $p$ and for all integers $d\ge k\ge \ell +1$, ${\mathbb{F}}^d$ contains a $(k,\ell )$-nearly orthogonal set of size $d^{\hat{I}´k/\log k}$. This nearly matches an upper bound $\left(\genfrac{}{}{0ex}{}{d+k}{k}\right)$ coming from Ramsey theory. Moreover, they proved the same lower bound for the size of a largest set $A$ where for any two subsets of $A$ of size $k+1$ each, there is a vector in one of the subsets orthogonal to a vector in the other one. We prove a common generalisation of this result, showing that essentially the same lower bound holds for the size of a largest set $A\subseteq {\mathbb{F}}^d$ with the stronger property that given any family of subsets $A_1,\dots ,A_{\ell +1}\subseteq A$, each of size $k+1$, we can find a vector in each $A_i$ such that they are all pairwise orthogonal. Rather than combining both counting and container arguments, we make use of a multipartite asymmetric container lemma that allows for non-uniform co-degree conditions. This lemma was first discovered by Campos, Coulson, Serra and Wötzel, and we provide a new and short proof for this lemma.

9 pages