Larger nearly orthogonal sets over finite fields

For a field F and integers d and k, a set A ⊆ Fd 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/ logk vectors of Fd. The size of the set is optimal up to the logk 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 Fd 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