تقرير
Larger Nearly Orthogonal Sets over Finite Fields
| العنوان: | Larger Nearly Orthogonal Sets over Finite Fields |
|---|---|
| المؤلفون: | Haviv, Ishay, Mattheus, Sam, Milojević, Aleksa, Wigderson, Yuval |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Computational Geometry, Computer Science - Discrete Mathematics |
| الوصف: | For a field $\mathbb{F}$ and integers $d$ and $k$, a set ${\cal A} \subseteq \mathbb{F}^d$ is called $k$-nearly orthogonal if its members are non-self-orthogonal and every $k+1$ vectors of ${\cal A}$ include an orthogonal pair. We prove that for every prime $p$ there exists some $\delta = \delta(p)>0$, such that for every field $\mathbb{F}$ of characteristic $p$ and for all integers $k \geq 2$ and $d \geq k$, there exists a $k$-nearly orthogonal set of at least $d^{\delta \cdot k/\log k}$ vectors of $\mathbb{F}^d$. The size of the set is optimal up to the $\log k$ term in the exponent. We further prove two extensions of this result. In the first, we provide a large set ${\cal A}$ of non-self-orthogonal vectors of $\mathbb{F}^d$ such that for every two subsets of ${\cal A}$ of size $k+1$ each, some vector of one of the subsets is orthogonal to some vector of the other. In the second extension, every $k+1$ vectors of the produced set ${\cal A}$ include $\ell+1$ pairwise orthogonal vectors for an arbitrary fixed integer $1 \leq \ell \leq k$. The proofs involve probabilistic and spectral arguments and the hypergraph container method. Comment: 12 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2404.01057 |
| رقم الأكسشن: | edsarx.2404.01057 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |