Multipartite Nearly Orthogonal Sets Over Finite Fields

Abstract For a field $$\mathbb {F}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math> and integers d , k and $$\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> , a set $$A \subseteq \mathbb {F}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>⊆</mml:mo> <mml:msup> <mml:mrow> <mml:mi>F</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:mrow> </mml:math> is called $$(k,\ell )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -nearly orthogonal if all vectors in A are non-self-orthogonal and every $$k+1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> vectors in A contain $$\ell + 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> 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 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> , there is a constant $$\delta (p,\ell )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>p</mml:mi> <mml:mo>,</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> such that for every field $$\mathbb {F}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math> of characteristic p and for all integers $$d \ge k \ge \ell + 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≥</mml:mo> <mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , $$\mathbb {F}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>F</mml:mi> </mml:mrow> <mml:mi>d</mml:mi> </mml:msup> </mml:math> contains a $$(k,\ell )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>ℓ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -nearly orthogonal set of size $$d^{\delta k / \log k}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>d</mml:mi> <mml:mrow> <mml:mi>δ</mml:mi> <mml:mi>k</mml:mi> <mml:mo>/</mml:mo> <mml:mo>log</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> </mml:msup> </mml:math> . This nearly matches an upper bound $$\left( {\begin{array}{c}d+k\ k\end{array}}\right) $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfenced> <mml:mrow> <mml:mtable> <mml:mtr> <mml:mtd> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>+</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> </mml:mtd> </mml:mtr> <