Discrete & Computational Geometry Математика

Multipartite Nearly Orthogonal Sets Over Finite Fields

Rajko Nenadov, Lander Verlinde
Springer Nature · 2026-06-30 · DOI 10.1007/s00454-026-00858-2

Аннотация

Abstract For a field $$\mathbb {F}$$ F and integers d , k and $$\ell $$ ℓ , a set $$A \subseteq \mathbb {F}^d$$ A ⊆ F d is called $$(k,\ell )$$ ( k , ℓ ) -nearly orthogonal if all vectors in A are non-self-orthogonal and every $$k+1$$ k + 1 vectors in A contain $$\ell + 1$$ ℓ + 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 $$\delta (p,\ell )$$ δ ( p , ℓ ) such that for every field $$\mathbb {F}$$ F of characteristic p and for all integers $$d \ge k \ge \ell + 1$$ d ≥ k ≥ ℓ + 1 , $$\mathbb {F}^d$$ F d contains a $$(k,\ell )$$ ( k , ℓ ) -nearly orthogonal set of size $$d^{\delta k / \log k}$$ d δ k / log k . This nearly matches an upper bound $$\left( {\begin{array}{c}d+k\\ k\end{array}}\right) $$ d + k k 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$$ 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$$ A ⊆ F d with the stronger property that given any family of subsets $$A_1, \ldots , A_{\ell +1} \subseteq A$$ A 1 , … , A ℓ + 1 ⊆ A , each of size $$k+1$$ k + 1 , we can find a vector in each $$A_i$$ 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.

Читать у издателя →