2026-08-15T23:16:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19984 2024-06-06T06:21:14Z ddc:004 open_access

Nearly Orthogonal Sets over Finite Fields Chawin, Dror Haviv, Ishay Nearly orthogonal sets Finite fields For a field 𝔽 and integers d and k, a set of vectors of 𝔽^d 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 𝔽 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)} / log k} vectors of 𝔽^d. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dror Chawin and Ishay Haviv 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.39 urn:nbn:de:0030-drops-199848 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.39 eng https://creativecommons.org/licenses/by/4.0/legalcode