Metraipolis › archive › dc_f143152387bb
How many sorted projections determine n points in k dimensions? — arXiv:2611.06470
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06470
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:22:41.381Z
- SHA-256 of the archived text
cd445ea405591fb4b6433fc852921aa1cae9a1b48222d8441a12147de87d10e2- Stable URL of this page
https://metraipolis.com/documento/dc_f143152387bb
How to cite
How many sorted projections determine n points in k dimensions? — arXiv:2611.06470 — arXiv (en), https://arxiv.org/abs/2611.06470 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f143152387bb (Metraipolis archive dc_f143152387bb, sha256 cd445ea405591fb4b6433fc852921aa1cae9a1b48222d8441a12147de87d10e2)
BibTeX
@misc{dcf143152387bb,
title = {How many sorted projections determine n points in k dimensions? — arXiv:2611.06470},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06470},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f143152387bb; sha256 cd445ea405591fb4b6433fc852921aa1cae9a1b48222d8441a12147de87d10e2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06470. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Let $d_1,\dots,d_m$ be directions in $\mathbb{R}^k$, where $k\ge 2$. A multiset $X$ of $n$ points of $\mathbb{R}^k$ projects to the $m$ multisets of numbers $\{\{x\cdot d_j : x\in X\}\}$, or equivalently to the $m$ sorted lists of these numbers. How many directions are needed for these projections to determine every multiset of $n$ points? Two simple bounds are known in every dimension: more than $(k-1)\log_2 n$ directions are always needed, and $(k-1)n+1$ directions in general position always suffice. In the plane much more is known: Matousek, Privetivy and Skovron showed that almost every choice of $O(\log n \log\log n)$ directions suffices. Whether anything similar holds in higher dimensions was left open by Dym, Wellershoff, Tsoukanis, Levy and Balan. We observe that two lemmas of Hair and Sahai, proved for list recovery of random linear codes, answer that question, and by tightening their argument we show that in every dimension almost every choice of $(4k-2)\ln(2n)\ln(k\log_2 2n)+k+1$ directions suffices. For $k\le 10$ this beats the linear bound once $n$ is larger than about 100: for example, 144 directions suffice for multisets of 1000 points in the plane, and an exact computation lowers this to 133. Letting some of the random blocks in their argument fail removes a factor $\log k$: almost every choice of $O(k\log n\log\log n)$ directions suffices, uniformly in $k$ and $n$. We also show that $2k-1$ directions never determine three points, so that the logarithmic lower bound is not tight; that every $m$ directions in the plane fail on some pair of multisets of size $O(1.78^m)$, improving the bound $O(1.80^m)$ of Matousek, Privetivy and Skovron; and that for each $k$, $m$ and $n$, either almost every choice of $m$ directions works or almost none does.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM); Information Theory (cs.IT); Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.06470 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:15:49.039Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).