Nearly Orthogonal Sets over Finite Fields
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929347654320128 |
|---|---|
| author | Chawin, Dror Haviv, Ishay |
| author_facet | Chawin, Dror Haviv, Ishay |
| contents | For a field $\mathbb{F}$ and integers $d$ and $k$, a set of vectors of $\mathbb{F}^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 $\mathbb{F}$ of characteristic $p$ and for all integers $k \geq 2$ and $d \geq k^{1/(p-1)}$, there exists a $k$-nearly orthogonal set of at least $d^{δ\cdot k^{1/(p-1)}/ \log k}$ vectors of $\mathbb{F}^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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08274 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Nearly Orthogonal Sets over Finite Fields Chawin, Dror Haviv, Ishay Computational Geometry Discrete Mathematics Information Theory Combinatorics For a field $\mathbb{F}$ and integers $d$ and $k$, a set of vectors of $\mathbb{F}^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 $\mathbb{F}$ of characteristic $p$ and for all integers $k \geq 2$ and $d \geq k^{1/(p-1)}$, there exists a $k$-nearly orthogonal set of at least $d^{δ\cdot k^{1/(p-1)}/ \log k}$ vectors of $\mathbb{F}^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. |
| title | Nearly Orthogonal Sets over Finite Fields |
| topic | Computational Geometry Discrete Mathematics Information Theory Combinatorics |
| url | https://arxiv.org/abs/2402.08274 |