Nearly Orthogonal Sets over Finite Fields

For a field F and integers d and k, a set of vectors of Fᵈ is called k-nearly orthogonal if its members are non-self-orthogonal and every $k+1$ of them include an orthogonal pair. We prove that for every prime p there exists a positive constant δ = δ (p), such that for every field F of characteristic p and for all integers k ≥ 2 and d ≥ k1/(p-1), there exists a k-nearly orthogonal set of at least d^δ · k1/(p-1)/ log k vectors of Fᵈ. In particular, for the binary field we obtain a set of dΩ( k /log k) vectors, and this is tight up to the log k term in the exponent. For comparison, the best known lower bound over the reals is dΩ( log k / log log k) (Alon and Szegedy, Graphs and Combin., 1999). The proof combines probabilistic and spectral arguments.