How many sorted projections determine any n points in k dimensions?
math.CO, cs.DM, cs.IT, cs.LG, math.IT
Submitted: 2026-11-04
Updated: 2026-11-19
Comments: 33 pages, 9 figures. v2: added word "any" to title, improved a bound following comment from ZM26, added three small special cases, removed unicode from an anc file, and added a statement about deep sets. v3: no new results, but many small text edits for clarity, and also added appendix with four new figures to aid in indexation of results
Code: https://github.com/kesterlester/Echinocoder
License: http://creativecommons.org/licenses/by/4.0/
The gist: Let d 1,,d m be directions in R k, where k at least 2.
Terminology
Abstract
Let d 1,,d m be directions in R k, where k at least 2. A multiset X of n points of R k projects to the m multisets of numbers x times 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) 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(n 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) (2n) (k 2 2n)+k+1 directions suffices. For k at most 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 k: almost every choice of O(k n 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.65 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.
Sources
- Permutation Invariant Representations with Applications to Graph Deep Learning
- Relationships between the Phase Retrieval Problem and Permutation Invariant Embeddings
- Stability of sorting based embeddings
- Low Dimensional Invariant Embeddings for Universal Geometric Learning
- Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings
- Lorentz and permutation invariants of particles I
- Lorentz and permutation invariants of particles II
- List Recovery for Random Low-Rate Linear Codes
- Dimension reduction, exact recovery, and error estimates for sparse reconstruction in phase space
- Lorentz and permutation invariants of particles III: constraining non-standard sources of parity violation
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality