Larger Nearly Orthogonal Sets over Finite Fields

For a field F and integers d and k, a set A ⊆ Fᵈ is called k-nearly orthogonal if its members are non-self-orthogonal and every $k+1$ vectors of A include an orthogonal pair. We prove that for every prime p there exists some δ = δ(p)>0, such that for every field F of characteristic p and for all integers k ≥ 2 and d ≥ k, there exists a k-nearly orthogonal set of at least dδ · k/log k vectors of Fᵈ. The size of the set is optimal up to the log k term in the exponent. We further prove two extensions of this result. In the first, we provide a large set A of non-self-orthogonal vectors of Fᵈ such that for every two subsets of A of size $k+1$ each, some vector of one of the subsets is orthogonal to some vector of the other. In the second extension, every $k+1$ vectors of the produced set A include +1 pairwise orthogonal vectors for an arbitrary fixed integer 1 ≤ ≤ k. The proofs involve probabilistic and spectral arguments and the hypergraph container method.