How many sorted projections determine n points in k dimensions?

Christopher Gorham Lester; Raymond Hau Sørensen

math.CONov 4, 2026

How many sorted projections determine n points in k dimensions?

Authors: Christopher Gorham Lester, Raymond Hau Sørensen

Organizations: Cavendish Laboratory, Department of Physics, University of Cambridge, UK

Abstract

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.

Figures & tables

Figure 1: Bounds on the number of directions that separate multisets of

n

points in

\mathbb{R}^{k}

, for

k=2,\dots,10

(thin and light to thick and dark): (a) before this paper and (b) now; this paper’s bounds are blue. Every list of fewer directions than the lower curve fails [ DWTLB26 , Theorem 5] (for

k=2

, [ BL90 ] and [ MPŠ08 ] ), in (b) for

k\geq 3

also by Theorem 1.2 . The upper curve is the smallest known upper bound: the linear bound

(k-1)n+1

, for every list in general position [ Rén52 , HSW24 ] ; for almost every list, in (a) for

k=2

the bound

5\log_{2}^{3}(2n)

of [ MPŠ08 , Proposition 3.1] , and in (b)

m^{\flat}_{k,\mathrm{bal}}(n)

of Theorem 1.1 , with the closed form

m^{\mathrm{CF}}_{k}(n)

dotted (on this range the smaller of

m^{\mathrm{CF}}_{k}(n)

and

m^{\mathrm{HD}}_{k}(n)

, Remark 5.5 ). Better lower bounds for

k=2

( [ MPŠ08 ] and Theorem 1.3 ) and the solved cases with

n\leq 5

are in Figures 2 and 3 , and Table S1 gives numbers. Drawn by plot_bounds.py in the accompanying code.

Figure 2: The best bounds on

m_{k}(n)

known before this paper, for

k=2,\dots,5

, including those for single values of

n

m_{k}(n)

lies in the shaded range between the upper and lower bounds (black). Each half of the shading has the colour of the bound credited on its side, named in the legend, and where the two meet a label names the reference credited with

m_{k}(n)

. The credits follow fixed rules from a database of what each reference states ( bounds.toml in the accompanying code): a bound goes to the earliest reference that states it. The figures show only results that come with a proof a reader can check; findings made in floating point are acknowledged in the text instead (Remark 3.1 and the provenance note).

Figure 3: As Figure 2 , with the results of this paper. Three points is Theorem 1.2 , The plane is Theorem 1.3 , and

m^{\flat}_{k,\mathrm{bal}}(n)

is from Theorem 1.1 . Values that others found in floating point and we verified exactly (Remark 3.1 ) are credited to this paper.

Panel of Figure 4 — Figure 4: A pinning pattern for $k=2$ , drawn as an abstract coloured graph (the positions of the vertices mean nothing). (a) A matching graph on six points, $a_{1},a_{2},a_{3}$ from $X$ (filled) and $b_{1},b_{2},b_{3}$ from $Y$ (open), for four directions. The edges of colour $j$ , a perfect matching, have the colour and line style of $d_{j}$ in the key. So every point has exactly one edge of each colour, and edges that meet at a point always have different colours. On the shaded set $W=\{a_{1},a_{2},b_{1},b_{2}\}$ , the tree $T_{1}$ is drawn with wiggles and uses colours $1$ and $2$ ; the tree $T_{2}$ is drawn with springs and uses colours $3$ and $4$ . Each tree needs two colours: colour $1$ pairs $W$ into $\{a_{1},b_{1}\}$ and $\{a_{2},b_{2}\}$ , and colour $2$ joins the two pairs, and likewise for colours $3$ and $4$ ; since edges that meet have different colours, the two colours of each tree alternate along it. The trees share vertices, and even the pairs $a_{1}b_{1}$ and $a_{2}b_{1}$ , but no colour. Straight edges are used by neither tree. (b) Why such a pattern pins $W$ , as in the proof of Lemma 4.3 . With $b_{1}$ at the origin, the six tree edges give a square system $M(D)\,p=0$ in the coordinates of $a_{1},a_{2},b_{2}$ ; the row of an edge of colour $j$ carries the first coordinate of $d_{j}$ in the $x_{1}$ columns and its second in the $x_{2}$ columns. Shown is $M$ at the useless but legal directions $d_{1}=d_{2}=e_{1}$ , $d_{3}=d_{4}=e_{2}$ (a witness, in the sense of Section 2 ), which are consistent because no colour is in both trees. The rows of $T_{1}$ lose their $x_{2}$ entries and those of $T_{2}$ their $x_{1}$ entries, so $M$ is block-diagonal, and each block, a spanning tree taken outward from $b_{1}$ , is triangular with determinant $-1$ . So $P(D)=\det M(D)$ is $1$ here, and is not identically zero. (For these trees, $P(D)=\det(d_{1},d_{4})\det(d_{2},d_{3})\det(d_{1},d_{3})$ .)

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

	The list $D$ of $m\geq k$ directions is drawn	general	generic	almost every
		position	lists	list
(i)	with independent directions, each from a distribution that gives no mass to hyperplanes through the origin	yes	if $k=2$	—
(ii)	with a density on $\mathbb{R}^{mk}$ , or with the unit vectors $d_{j}/\lvert d_{j}\rvert$ having a density on the product of $m$ unit spheres	yes	yes	yes
(iii)	with independent coordinates, none of which takes any single value with positive probability	yes	yes	—
(iv)	with rounded coordinates, or from a finite set of lists	—	—	—

Appendix

Table 1: Ways of drawing random directions, and what holds with probability one (Lemma A.7 ). “Yes” under “generic lists” or “almost every list” means that every property of the paper that holds for generic lists, or for almost every list, then holds with probability one. A dash means that nothing is guaranteed. Independent standard normal coordinates satisfy (i)–(iii); independent directions uniform on the unit sphere satisfy (i) and (ii); independent directions uniform on a small circle of the unit sphere of

\mathbb{R}^{3}

satisfy only (i).

Result	Condition on the directions
Theorems 1.2 and 1.3 , Lemmas 2.1 – 2.5 and 3.2	none: they hold for every list
Lemma 2.6 (the linear bound)	general position (Definition A.1 )
Corollary 4.4 and Theorem 1.1	generic lists, and so almost every list (Definition A.4 )
Theorem 1.4	generic lists, and lists with algebraically independent coordinates (Definition A.5 )
Corollary 6.1	random, drawn as in (ii) or (iii) of Table 1
Corollary 6.2	the axes fixed, and almost every choice of the other directions

Appendix

Table 2: The conditions that each result puts on the directions.

Panel of Figure 5 — Figure 5: The conditions of this appendix on a list of $m\geq k$ directions in $\mathbb{R}^{k}$ , drawn as sets for $k\geq 3$ (for $k=2$ the two outer ovals coincide), and the set $S$ of lists that separate multisets of size $n$ , shaded. (a) When $m^{\sharp}_{k}(n)\leq m\leq(k-1)n$ , $S$ contains every list with algebraically independent coordinates (Theorem 1.1 and Lemma A.6 ), but not every list in general position (Remark A.3 ). (b) When $m\geq(k-1)n+1$ , $S$ contains every list in general position (Lemma 2.6 ). When a shorter list separates, $S$ also contains lists with two parallel directions (repeat a direction of the shorter list), so $S$ reaches outside the outer oval. Areas mean nothing: every set drawn has full measure, so the sets differ only by sets of measure zero.

	$n=10^{2}$	$10^{3}$	$10^{4}$	$10^{6}$	$10^{9}$
$k=2$
every list fails below	$10$	$14$	$18$	$26$	$38$
succeed from, before this paper	$101$	$1001$	$10\,001$	$45\,854^{*}$	$147\,481^{*}$
$m^{\mathrm{HS}}_{k}(n)$ , from [ HS26 ] as written	$364$	$558$	$764$	$1198$	$1890$
$m^{\mathrm{HSE}}_{k}(n)$ , equation ( 3 )	$288$	$458$	$638$	$1024$	$1646$
$m^{\mathrm{CF}}_{k}(n)$ , equation ( 2 )	$90$	$144$	$203$	$329$	$533$

Appendix

Table S1: Numbers of directions for separating multisets of

n

points in

\mathbb{R}^{2}

and

\mathbb{R}^{3}

, as in Figure 1 . Every list of fewer directions than the first row fails: for

k=2

by Theorem 1.3 , and at

n=10^{2}

equally by the constructions of [ MPŠ08 ] (their product lemma applied to their examples with three and nine directions); for

k=3

by Theorem 1.2 and the logarithmic bound (before Theorem 1.2 , one fewer, except at

n=10^{4}

). The second row is the smallest number of directions from which lists were known to succeed before this paper: the linear bound

(k-1)n+1

, for every list in general position [ Rén52 , HSW24 ] , or, for the starred entries, the bound

5\log_{2}^{3}(2n)

of [ MPŠ08 , Proposition 3.1] with the constant that they state, for almost every list. The remaining rows are for almost every list: Hair and Sahai’s lemmas as their proof writes them (Section 5 ),

m^{\mathrm{HSE}}_{k}(n)

, which is their final inequality evaluated exactly (equation ( 3 )), and the four bounds of Theorem 1.1 .

m^{\flat}_{k,\mathrm{bal}}(n)

is the smallest known upper bound, and

m^{\mathrm{CF}}_{k}(n)

the smallest known in closed form for these

k

. Printed, with the credits, by boundsdb.py --table in the accompanying code; flatbound.py checks the rows for

m^{\flat}_{k,\mathrm{eq}}(n)

and

m^{\flat}_{k,\mathrm{bal}}(n)

by a direct search.

$n$	$k$	$m^{\sharp}_{k}(n)$	$m^{\flat}_{k,\mathrm{eq}}(n)$	$m^{\flat}_{k,\mathrm{bal}}(n)$
$10^{2}$	$2$	$82$	$82$	$82$
	$3$	$162$	$162$	$160$
	$8$	$640$	$630$	$622$
	$10$	$860$	$814$	$812$
	$20$	$2040$	$1752$	$1751$
$10^{3}$	$2$	$134$	$134$	$133$

Appendix

Table S2: Numerical comparison of the bound

m^{\sharp}_{k}(n)

(equation ( 1a )), in which all

k

blocks must connect

W

, the equal-block bound

m^{\flat}_{k,\mathrm{eq}}(n)

(equation ( 1b )), and the balanced-block bound

m^{\flat}_{k,\mathrm{bal}}(n)

(equation ( 1c )) of Theorem 1.1 , for

n\in\{10^{2},10^{3},10^{4},10^{6}\}

and

k\in\{2,3,8,10,20\}

. Allowing

q>k

blocks and requiring only

k

of them to connect

W

reduces the number of directions needed, with larger savings as the dimension

k

grows. Computed by flatbound.py in the accompanying code.

Random Projection

See all 9 papers

Aug 21, 2026

Sorting from Counterexamples

Consider the following problem of learning an unknown linear order on

n

items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to

k

of the returned counterexamples may be untruthful, where

k

is not known in advance. We determine the optimal query complexity up to constant factors:

Θ(n\log n + nk).

Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order

n

. The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in

\mathbb{R}^d

, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of

O(d^2\log n+dk)

and a lower bound of

Ω(d\log n+dk)

, leaving a factor of

d

gap in the noiseless term.

Noga Alon, Shay Moran, Shlomo Moran

Princeton University, Princeton, NJ 08544, USA, and Tel Aviv University, Tel Aviv 69978, Israel. · Technion – Israel Institute of Technology and Google Research. · Technion – Israel Institute of Technology.

Query Complexity Pairwise Ranking Active Learning

Ask PDF

Jul 3, 2026

Dimension Reduction for Curves: Simplified and Generalized

We revisit random projections for reducing the dimension of high-dimensional polygonal curves. Drawing from the toolbox of randomized linear algebra, we give a considerably simplified proof of the known

O(\varepsilon^{-2}\log(nm))

bound on the target dimension of a random projection that preserves the continuous Fréchet distance of polygonal curves up to a factor

(1\pm\varepsilon)

. Our proof is based on the concept of sparse oblivious subspace embeddings. While previous techniques were limited to the case of the Fréchet distance, our techniques are fairly general and extend to all possible distance measures that involve the maximum, a sum or an integral over Euclidean distances between pairs of points on both input curves. We define a generalized dissimilarity measure for curves that includes several popular measures such as Fréchet,

q

-DTW, Hausdorff, etc. as special cases and show that the same dimension reduction technique works for this generalized dissimilarity measure. Finally, we apply the same framework for dimension reduction to piecewise linear surfaces, after extending the distance measure suitably to such surfaces.

Matthijs Ebbens, Jie Lu, Alexander Munteanu

TU Dortmund, Germany

Dimensionality Reduction

Ask PDF

Jul 9, 2026

High-Dimensional Procrustes Matching via Tree Counts

Suppose we observe two sets of

n

Gaussian vectors in

\mathbb{R}^d

, with the promise that, after applying a permutation of

[n]

and a rotation of

\mathbb{R}^d

, the two sets are

ρ

-correlated. The Procrustes matching problem asks us to recover the unknown permutation of

[n]

that aligns the two sets. The problem is well-studied in the low-dimensional regime

d=O(\log n)

, but the high-dimensional regime

d\gg \log n

has remained largely uncharted: prior matching guarantees require nearly perfect correlation

ρ=1-o(1)

, even for information-theoretic recovery. Our main result is a polynomial-time algorithm for exact recovery at constant correlation. The algorithm works by computing and comparing weighted counts of a specially chosen family of ``wide'' trees. So long as

d\ge \mathrm{polylog}(n)

, the algorithm succeeds with high probability for any

ρ^2>\sqrtα

, where

α\approx 0.338

is Otter's tree-counting constant. We complement this algorithmic result with an improved information-theoretic guarantee, showing that exact recovery is possible when

ρ^2 \gtrsim \max\{\log n/d,\sqrt{\log n/n}\}

. We also carry out a low-degree advantage calculation, which suggests that the condition

ρ^2 > \sqrtα

is necessary for any tree-counting algorithm.

Xiaochun Niu, Tselil Schramm, Jiaming Xu

The Fuqua School of Business, Duke University, Durham NC, USA · Department of Statistics, Stanford University, Stanford, CA, USA

Orthogonal Procrustes Alignment Low-Degree Polynomial Method

Ask PDF

Abstract

Random Projection

Explore similar work

Sorting from Counterexamples

Dimension Reduction for Curves: Simplified and Generalized

High-Dimensional Procrustes Matching via Tree Counts