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 k^1/ (p-1), there exists a k-nearly orthogonal set of at least d^ k^{1/ (p-1) / k} vectors of Fᵈ. In particular, for the binary field we obtain a set of d^ (k / k) vectors, and this is tight up to the k term in the exponent. For comparison, the best known lower bound over the reals is d^ (k / k) (Alon and Szegedy, Graphs and Combin. , 1999). The proof combines probabilistic and spectral arguments.