2024/02/13 by Chawin, Dror, Haviv, Ishay
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2402.08274
For a field \mathbbF and integers d and k, a set of vectors of \mathbbFd 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 \mathbbF 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 \mathbbFd. 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.