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/ k vectors of Fᵈ. The size of the set is optimal up to the 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.