How many sorted projections determine n points in k dimensions?

Abstract

Let d₁,…,d_m be directions in ℝ^k, where k≥ 2. A multiset X of n points of ℝ^k projects to the m multisets of numbers {{x· d_j : x∈ 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₂ 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 loglog 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(klog₂ 2n)+k+1 directions suffices. For k≤ 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(klog nloglog 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.

Higher-order many-sorted categorial algebras via generalized hep-derivors
J. Climent Vidal, E. Cosme Llópez, R. Ruiz Mora +1
arXiv2 Nov 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
How many points does an affine algebraic set have in residue classes modulo n ?
Mihai Prunescu
arXiv14 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theory Logic & foundationsarXiv
Lenses make many points: Pure point spectrum disproves Simon's L² conjecture
Simon Becker, Mengxuan Yang
arXiv22 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEs Mathematical physicsarXiv
Bernstein type results for stationary points of variational integrals with subquadratic growth in two dimensions
Michael Bildhauer, Martin Fuchs
arXiv1 Sep 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv
Positive sectional curvature on exotic spheres in infinitely many dimensions
Fernando Galaz-García
arXiv22 Oct 2026PreprintCC BY 4.0Full textGeometry & topologyarXiv

Cite

BibTeX RIS

BibTeX

@misc{lester2026many,
  title = {{How many sorted projections determine n points in k dimensions?}},
  author = {Christopher Gorham Lester and Raymond Hau Sørensen},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06470},
  eprint = {2611.06470},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06470},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - How many sorted projections determine n points in k dimensions?
AU  - Christopher Gorham Lester
AU  - Raymond Hau Sørensen
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06470
UR  - https://arxiv.org/abs/2611.06470
AB  - Let d_1,…,d_m be directions in ℝ^k, where k≥ 2. A multiset X of n points of ℝ^k projects to the m multisets of numbers {{x· d_j : x∈ 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 loglog 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(klog_2 2n)+k+1 directions suffices. For k≤ 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(klog nloglog 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.
ER  -

Abstract

Related

Cite