---
OA_place: repository
OA_type: green
_id: '22163'
abstract:
- lang: eng
  text: "For a field F and integers d and k, a set A ⊆ Fd is called k-nearly orthogonal
    if its\r\nmembers are non-self-orthogonal and every k + 1 vectors of A include
    an orthogonal pair.\r\nWe prove that for every prime p there exists some δ = δ(p)>
    0, such that for every field\r\nF of characteristic p and for all integers k ≥
    2 and d ≥ k, there exists a k-nearly orthogonal\r\nset of at least dδ·k/ logk
    vectors of Fd. The size of the set is optimal up to the logk term\r\nin the exponent.
    We further prove two extensions of this result. In the first, we provide a\r\nlarge
    set A of non-self-orthogonal vectors of Fd such that for every two subsets of
    A of\r\nsize k+1 each, some vector of one of the subsets is orthogonal to some
    vector of the other.\r\nIn the second extension, every k + 1 vectors of the produced
    set A include ℓ + 1 pairwise\r\northogonal vectors for an arbitrary fixed integer
    1 ≤ ℓ ≤ k. The proofs involve probabilistic\r\nand spectral arguments and the
    hypergraph container method"
article_number: '114373'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Ishay
  full_name: Haviv, Ishay
  last_name: Haviv
- first_name: Sam
  full_name: Mattheus, Sam
  last_name: Mattheus
- first_name: Aleksa
  full_name: Milojević, Aleksa
  last_name: Milojević
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Haviv I, Mattheus S, Milojević A, Wigderson Y. Larger nearly orthogonal sets
    over finite fields. <i>Discrete Mathematics</i>. 2025;348(4). doi:<a href="https://doi.org/10.1016/j.disc.2024.114373">10.1016/j.disc.2024.114373</a>
  apa: Haviv, I., Mattheus, S., Milojević, A., &#38; Wigderson, Y. (2025). Larger
    nearly orthogonal sets over finite fields. <i>Discrete Mathematics</i>. Elsevier.
    <a href="https://doi.org/10.1016/j.disc.2024.114373">https://doi.org/10.1016/j.disc.2024.114373</a>
  chicago: Haviv, Ishay, Sam Mattheus, Aleksa Milojević, and Yuval Wigderson. “Larger
    Nearly Orthogonal Sets over Finite Fields.” <i>Discrete Mathematics</i>. Elsevier,
    2025. <a href="https://doi.org/10.1016/j.disc.2024.114373">https://doi.org/10.1016/j.disc.2024.114373</a>.
  ieee: I. Haviv, S. Mattheus, A. Milojević, and Y. Wigderson, “Larger nearly orthogonal
    sets over finite fields,” <i>Discrete Mathematics</i>, vol. 348, no. 4. Elsevier,
    2025.
  ista: Haviv I, Mattheus S, Milojević A, Wigderson Y. 2025. Larger nearly orthogonal
    sets over finite fields. Discrete Mathematics. 348(4), 114373.
  mla: Haviv, Ishay, et al. “Larger Nearly Orthogonal Sets over Finite Fields.” <i>Discrete
    Mathematics</i>, vol. 348, no. 4, 114373, Elsevier, 2025, doi:<a href="https://doi.org/10.1016/j.disc.2024.114373">10.1016/j.disc.2024.114373</a>.
  short: I. Haviv, S. Mattheus, A. Milojević, Y. Wigderson, Discrete Mathematics 348
    (2025).
das_tickbox: '1'
date_created: 2026-06-29T10:53:05Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2026-07-14T08:17:17Z
day: '01'
doi: 10.1016/j.disc.2024.114373
extern: '1'
external_id:
  arxiv:
  - '2404.01057'
intvolume: '       348'
issue: '4'
keyword:
- Nearly orthogonal sets
- Ramsey theory
- Finite fields
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: 'https://doi.org/10.48550/arXiv.2404.01057 '
month: '04'
oa: 1
oa_version: Preprint
publication: Discrete Mathematics
publication_identifier:
  issn:
  - 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Larger nearly orthogonal sets over finite fields
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 348
year: '2025'
...