==== TABLE OF CONTENTS ====
The-higher-dimensional-Erdos-distinct-distances-conjecture//figures/motion-partition.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//figures/proof-map.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//figures/scale-profile.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//paper.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//preamble.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/approximation.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/classical-incidence.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/concentration.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/depth.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/introduction.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/motions.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/polynomial.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/profiles.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/reduction.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/secants.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/sparse-cones.tex
The-higher-dimensional-Erdos-distinct-distances-conjecture//references.bib
===========================
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//figures/motion-partition.tex ====
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.95]
\fill[gray!13] (0,0) rectangle (4,4);
\draw[thick] (0,0) rectangle (4,4);
\draw[gray!45] (2,0)--(2,4) (0,2)--(4,2);
\fill[white] (2,2) rectangle (3,3);
\draw[thick] (2,2) rectangle (3,3);
\fill[green!18] (3,2) rectangle (4,3);
\draw[green!45!black,thick] (3,2) rectangle (4,3);
\draw[blue!65!black,dashed,thick] (2,2) rectangle (4,4);
\fill (3.22,2.29) circle (1.8pt);
\node[anchor=east] at (3.16,2.29) {$x$};
\node at (2.5,2.5) {$Q'$};
\node at (3.56,2.58) {$E$};
\node[blue!65!black] at (3.3,3.53) {$A_0$};
\node at (0.8,3.5) {$Q\setminus Q'$};
\node[anchor=north] at (2,-0.12) {A region with one dyadic hole};
\node[align=left,anchor=west,text width=6.0cm] at (4.7,2.25)
{Choose a dyadic cube $A_0$ containing $x$ at scale $s$.\\[4pt]
If the hole meets $A_0$, nesting places it in one child.\\[4pt]
Another child $E$ remains in the region and provides volume
comparable to $s^3$ in three dimensions.};
\end{tikzpicture}
\caption{A two-dimensional illustration of the thickness argument in
Lemma~\ref{mot:partition}. The volume estimate is proved for
three-dimensional cubes. It holds near the hole as well as near the
outer boundary, and survives every rigid motion. This makes the
packing argument independent of the depth of the dyadic subdivision.}
\label{mot:partition-figure}
\end{figure}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//figures/motion-partition.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//figures/proof-map.tex ====
\begin{tikzpicture}[
box/.style={draw=linkblue!65,rounded corners=2pt,fill=figuregray,
align=center,font=\small,text width=4.65cm,
minimum height=1.15cm,inner sep=5pt},
application/.style={align=center,font=\small,text width=4.1cm,
inner sep=3pt},
arrow/.style={-{Latex[length=2mm]},thick,draw=linkblue!80}]
\node[box] (poly) at (-3.2,0.65)
{Polynomial estimates\\and scale profiles\\
Sections~\ref{poly:section} and~\ref{sec:profiles}};
\node[box] (geo) at (3.2,0.65)
{Secant geometry\\and terminal-curve deletion\\
Section~\ref{geo:section}};
\node[box,text width=8.8cm] (sparse) at (0,-1.6)
{\textbf{Sparse-cones argument} (Section~\ref{sec:sparse-cones})\\
Common windows: rank and outer endpoint\\
Separated windows: rank and final curve endpoint,\\
using projection depth at actual centers};
\node[box] (stars) at (0,-3.8)
{Symmetric direction selection\\with independent evaluations\\
Proposition~\ref{red:independent-stars}};
\node[box] (graph) at (0,-5.7)
{Equal-distance graph\\and its pair flats\\
Section~\ref{sec:reduction}};
\node[box,text width=3.8cm] (conc) at (-5.3,-5.7)
{Uniform concentration\\of evaluation flats\\
Appendix~\ref{conc:section}};
\node[box,text width=3.25cm] (motions) at (5.4,-5.7)
{Very rich motions\\in dimension three\\
Section~\ref{mot:section}};
\node[draw=linkblue!65,rounded corners=2pt,fill=figuregray,
minimum width=9cm,minimum height=2.4cm,inner sep=0pt]
(applications) at (0,-9) {};
\node[font=\small\bfseries,align=center] at (0,-8.08)
{Applications to the retained pair flats};
\node[application] (global) at (-2.25,-9.2)
{Global concentration\\and the Hilbert bound:\\rank lower bound\\
Lemmas~\ref{red:global-concentration} and~\ref{poly:hilbert}};
\node[application] (local) at (2.25,-9.2)
{Local concentration:\\cap on neighbor flats in a\\
proper low-degree zero set\\
Lemma~\ref{red:local-concentration}};
\draw[linkblue!25] (0,-8.55) -- (0,-9.94);
\node[box,text width=5.8cm,fill=figureblue] (end) at (0,-11.45)
{One random sample\\with fixed inclusion probability\\
and a rank contradiction\\
Proposition~\ref{red:main-contradiction}};
\draw[arrow] (poly.south) -- ([xshift=-3.2cm]sparse.north);
\draw[arrow] (geo.south) -- ([xshift=3.2cm]sparse.north);
\draw[arrow] (sparse.south) -- (stars.north);
\draw[arrow] (stars.south) -- (graph.north);
\draw[arrow] (graph.south) -- (applications.north);
\draw[arrow] (conc.south) -- (applications.north west);
\draw[arrow] (motions.south) --
node[pos=.48,right,xshift=3pt,align=left,font=\footnotesize,inner sep=3pt]
{\(d=3\) deletion\\for the local\\isotropic cap}
(local.north east);
\draw[arrow] (applications.south) -- (end.north);
\end{tikzpicture}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//figures/proof-map.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//figures/scale-profile.tex ====
\begin{tikzpicture}[x=5.7cm,y=.65cm,font=\small,
profile/.style={very thick,draw=linkblue},
cut/.style={densely dashed,draw=linkblue!55}]
\fill[figureblue] (-.4,0) rectangle (.3,4.25);
\draw[-{Latex[length=2mm]}] (-1.07,0) -- (-1.07,4.6)
node[above right] {Carrier dimension $l=d-j$};
\foreach \l in {0,1,2,3,4}{
\draw (-1.09,\l) -- (-1.05,\l);
\node[left] at (-1.09,\l) {$\l$};
}
\foreach \b/\i in {-.8/1,-.4/2,.3/3,.9/4}{
\draw[cut] (\b,-.65) -- (\b,4.25);
\node[below] at (\b,-.65) {$b_\i$};
}
\draw[-{Latex[length=2mm]}] (-1.07,-.65) -- (1.14,-.65)
node[below left,yshift=-13pt] {Normalized time $b$};
\node[below] at (-1,-.65) {$-1$};
\node[below] at (1,-.65) {$1$};
\draw[profile] (-1,4) -- (-.8,4);
\draw[profile] (-.8,3) -- (-.4,3);
\draw[profile] (-.4,2) -- (.3,2);
\draw[profile] (.3,1) -- (.9,1);
\draw[profile] (.9,0) -- (1,0);
\draw[profile,dotted] (-.8,4) -- (-.8,3);
\draw[profile,dotted] (-.4,3) -- (-.4,2);
\draw[profile,dotted] (.3,2) -- (.3,1);
\draw[profile,dotted] (.9,1) -- (.9,0);
\node[align=center] at (-.05,3.35)
{$(j,l)=(2,2)$\\[2pt]$\sigma(b)=e_2T_s(b)^2$};
\end{tikzpicture}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//figures/scale-profile.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//paper.tex ====
\documentclass[11pt]{article}
\input{preamble}
\title{The higher-dimensional Erd\H{o}s distinct-distances conjecture}
\author{OpenAI}
\date{September 23, 2026}
\begin{document}
\maketitle
\begin{abstract}
For every fixed integer $d\ge3$, we prove that every set of $n\ge2$ distinct
points in $\mathbb R^d$ determines at least $c_d n^{2/d}$ distinct
distances, where $c_d>0$ depends only on $d$. This resolves the
higher-dimensional Erd\H{o}s distinct-distances conjecture positively.
\end{abstract}
\input{sections/introduction}
\FloatBarrier
\tableofcontents
\input{sections/reduction}
\input{sections/polynomial}
\input{sections/secants}
\input{sections/profiles}
\input{sections/sparse-cones}
\input{sections/motions}
\appendix
\input{sections/concentration}
\input{sections/classical-incidence}
\bibliographystyle{plain}
\bibliography{references}
\end{document}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//paper.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//preamble.tex ====
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,mathtools,amsthm}
\usepackage{microtype,enumitem,booktabs,array}
\usepackage{flafter,placeins}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,fit,backgrounds,calc,patterns,decorations.pathreplacing}
\usepackage{xcolor}
\definecolor{linkblue}{RGB}{28,62,101}
\definecolor{figureblue}{RGB}{223,234,246}
\definecolor{figuregray}{RGB}{242,244,247}
\usepackage[colorlinks=true,linkcolor=linkblue,citecolor=linkblue,urlcolor=linkblue,bookmarksnumbered=true,bookmarksdepth=2,pdfusetitle]{hyperref}
\setcounter{tocdepth}{2}
\urlstyle{same}
\usepackage[nameinlink,capitalise,noabbrev]{cleveref}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\DeclareMathOperator{\Env}{Env}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\mult}{mult}
\DeclareMathOperator{\Span}{span}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\Spec}{Spec}
\DeclareMathOperator{\Sing}{Sing}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Res}{Res}
\DeclareMathOperator{\lcm}{lcm}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\PP}{\mathbb P}
\newcommand{\E}{\mathbb E}
\newcommand{\Prob}{\mathbb P}
\setlength{\emergencystretch}{1.5em}
\allowdisplaybreaks[2]
\raggedbottom
\clubpenalty=10000
\widowpenalty=10000
\usepackage{needspace,etoolbox}
\pretocmd{\subsection}{\Needspace{9\baselineskip}}{}{\PackageError{paper}{Subsection spacing hook failed}{}}
\BeforeBeginEnvironment{theorem}{\Needspace{5\baselineskip}}
\BeforeBeginEnvironment{proposition}{\Needspace{5\baselineskip}}
\BeforeBeginEnvironment{lemma}{\Needspace{5\baselineskip}}
\BeforeBeginEnvironment{corollary}{\Needspace{5\baselineskip}}
\BeforeBeginEnvironment{remark}{\Needspace{5\baselineskip}}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//preamble.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/approximation.tex ====
\subsection{Approximate complete intersections}
\label{aci:section}
We prove Walsh's approximate complete-intersection theorem
\cite[Theorem~1.3]{walsh2020}. The partial-degree framework and the
construction of compatible cuts follow
\cite[Definition~2.2 and Lemma~5.3]{walsh2020}.
The comparison of restriction spaces appears in the proof of
\cite[Lemma~3.5]{walsh2020}. Walsh obtains a corresponding prefix
degree estimate for his chosen cuts
\cite[Theorem~5.5]{walsh2020}.
We prove the forms needed here; the component Hilbert bounds in
Lemma~\ref{poly:hilbert} are the only quantitative algebraic input.
In particular, this proof is independent
of Theorem~\ref{conc:theorem}.
\begin{theorem}[Approximate complete intersection]
\label{aci:theorem}
\label{conc:walsh}
For every $n$ there is a constant $C_n$ with the following property.
If $V\subset\mathbb A^n_{\mathbb C}$ is irreducible of codimension
$c>0$, there are nonconstant polynomials $f_1,\ldots,f_c\in I(V)$ such
that $V$ is an irreducible component of $Z(f_1,\ldots,f_c)$ and
\[
\prod_{i=1}^c\deg f_i\le C_n\deg V.
\]
\end{theorem}
Here and below, a component \emph{containing $V$} means that it contains
the whole irreducible variety $V$. Set
\[
I_{\le t}(V)=I(V)\cap\mathbb C[x_1,\ldots,x_n]_{\le t},
\qquad
H_V(t)=\dim_{\mathbb C}
\bigl(\mathbb C[x_1,\ldots,x_n]_{\le t}/I_{\le t}(V)\bigr).
\]
For $1\le i\le c$, define $\delta_i$ to be the smallest integer $t$
such that every irreducible component of $Z(I_{\le t}(V))$ containing
$V$ has codimension at least $i$. The notation $Z(I_{\le t}(V))$
means the zero set of a basis of this finite-dimensional vector space.
Finite generation of $I(V)$ shows that these integers exist, and their
definition gives
\begin{equation}
1\le\delta_1\le\cdots\le\delta_c.
\label{aci:partial-degrees}
\end{equation}
We also put $\delta_0=0$.
\begin{lemma}[Compatible partial cuts]
\label{aci:cuts}
There are $f_i\in I_{\le\delta_i}(V)$, $1\le i\le c$, such that
every component of $Z(f_1,\ldots,f_i)$ containing $V$ has codimension
exactly $i$.
For any such choice, if $0\le j0$ and $b_n\ge1$ such that an
irreducible $k$-dimensional variety $X$ satisfies
\begin{equation}
H_X(m)\le b_n\deg(X)m^k\qquad(m\ge1),
\label{aci:rank-upper}
\end{equation}
and, if $X$ is a component of a system whose equations have degrees at
most $m$, then
\begin{equation}
H_X(m)\ge a_n\deg(X)m^k\qquad(m\ge1).
\label{aci:rank-lower}
\end{equation}
The second assertion is the bound at the equation degree in
\eqref{poly:hilbert-at-L}, applied with $L=m$. It permits other
components of the system to have larger dimension. The lower bound
also holds for $X=\mathbb A^n$, after decreasing $a_n$, directly from
$H_{\mathbb A^n}(m)=\binom{m+n}{n}$.
Suppose \eqref{aci:prefix-degree} is known for smaller indices, and
let $U$ be a component at index $s$. If $\delta_s=1$, the entire
product in \eqref{aci:prefix-degree} is $1$, and $\deg U\ge1$ proves
the claim. Otherwise set
\[
m=\delta_s-1,\qquad
j=\max\{i:0\le i1$. Therefore some component $T$ is not divisible by
$g$, and B\'ezout bounds their common lines by $3D\deg g$.
Every flat line belongs to exactly one irreducible factor of $f$:
membership in two factors would make the entire line critical.
Summing the preceding bound over the nonplanar factors gives at most
$3D^2$ flat lines. Factors having no smooth real point contain no
flat line and do not need a separate argument.
\end{proof}
\subsection{The higher-richness line theorem}
\begin{theorem}[Guth--Katz, higher richness]\label{ci:rich-lines}
Let $\mathcal L$ be $L$ distinct lines in $\mathbb R^3$, with at most
$B_0$ in any affine plane. For every integer $k\ge3$, the number
$R_k$ of points lying on at least $k$ lines satisfies
\[
R_k\le C\left(\frac{L^{3/2}}{k^2}
+\frac{LB_0}{k^3}+\frac Lk\right).
\]
There is no assumption about lines on quadrics in this theorem.
\end{theorem}
\begin{proof}
We first prove a uniform version. Let $S$ be a set of $s$ points each
incident to between $k$ and $2k$ lines. Suppose at least $L/100$ lines
each contain at least $sk/(100L)$ points of $S$. We will prove the
stated bound for $s$.
Fix a sufficiently small absolute $\varepsilon>0$. We may assume
\begin{equation}\label{ci:large-s}
s>A\left(L^{3/2}k^{-2}+Lk^{-1}\right),
\end{equation}
where $A$ will be chosen sufficiently large. By
Theorem~\ref{ci:st}, this assumption implies $s\le C L^2k^{-3}$.
Choose
\[
r=\left\lfloor\theta L^2s^{-1}k^{-3}\right\rfloor,
\]
where the constant $\theta$ is sufficiently large. Thus $r\ge1$
and $r$ is comparable to the expression inside the floor.
Lemma~\ref{ci:partition} gives a polynomial $f$ of degree
$D\le Cr$. We claim that at most $\varepsilon s$ points of $S$ lie
outside $Z(f)$.
Otherwise, among its $O(r^3)$ sign cells, at least $c_\varepsilon r^3$
contain at least $c_\varepsilon s/r^3$ points of $S$. To verify this,
discard cells with fewer than a small fixed multiple of
$\varepsilon s/r^3$ points and use the uniform upper bound
$Cs/r^3$ for the others. Each line meets at most $D+1=O(r)$ cells.
One of the retained cells is therefore met by at most
$C_\varepsilon L/r^2$ lines. Apply Theorem~\ref{ci:st} inside it:
\[
\frac{s}{r^3}
\le C_\varepsilon\left(\frac{L^2}{r^4k^3}
+\frac L{r^2k}\right).
\]
Substitution of $r$ gives
\[
s\le C_\varepsilon\left(\theta^{-1}s
+\theta L^3s^{-1}k^{-4}\right).
\]
Choose $\theta$ first so that the first term can be absorbed. The
resulting inequality $s\le C_\varepsilon\sqrt\theta L^{3/2}k^{-2}$
contradicts \eqref{ci:large-s} when $A$ is sufficiently large. This
proves the claim.
Replacing $f$ by its square-free part does not change its zero set
and can only lower its degree. The same estimates and
\eqref{ci:large-s} give
\begin{equation}\label{ci:small-degree}
D\le C\theta L^2s^{-1}k^{-3},\qquad
\frac D{sk/L}\le\frac{C\theta}{A^2},\qquad
\frac D{\sqrt L}\le\frac{C\theta}{Ak}.
\end{equation}
Write $\mathcal L_Z$ for the lines contained in $Z(f)$, and $S_*$ for
the points of $S$ lying on at least three lines of $\mathcal L_Z$.
A point of $(S\cap Z(f))\setminus S_*$ lies on at least $k-2$ lines
outside $\mathcal L_Z$. Each such line has at most $D$ points on
$Z(f)$. Hence
\[
|S\setminus S_*|\le\varepsilon s+\frac{LD}{k-2}
\le\left(\varepsilon+\frac{3C\theta}{A^2}\right)s.
\]
Choose $A$ so large that this is at most $2\varepsilon s$.
Let $\mathcal L_0$ be the at least $L/100$ lines in the uniformity
assumption. If such a line contains fewer than $sk/(200L)$ points
of $S_*$, it contains at least $sk/(200L)$ points of $S\setminus S_*$.
But this latter set has at most $2k|S\setminus S_*|\le4\varepsilon sk$
incidences. Thus at most $800\varepsilon L$ lines of
$\mathcal L_0$ fail to contain $sk/(200L)$ points of $S_*$. With
$\varepsilon$ small enough, at least $L/200$ lines succeed.
All points of $S_*$ are critical or flat by Lemma~\ref{ci:flat}.
On each successful line one of these two kinds occurs at least
$sk/(400L)$ times. By \eqref{ci:small-degree} this is more than
$3D$, on enlarging $A$. Every successful line is consequently a
critical line or a flat line. Lemma~\ref{ci:flat} and the last bound
in \eqref{ci:small-degree} show that fewer than $L/400$ of them are
critical or flat on nonplanar components. At least $L/400$ therefore
lie in plane components of $Z(f)$. There are at most $D$ such
components, so one contains at least $L/(400D)$ lines. It follows
that
\[
B_0\ge\frac L{400D}\ge c\frac{sk^3}{L},
\qquad s\le C LB_0k^{-3}.
\]
Together with the alternative to \eqref{ci:large-s}, this proves the
uniform version with an absolute constant $C_0$.
We remove the uniformity assumption by induction on $L$, keeping this
same constant $C_0$. Let $\mathcal L_1$ consist of the lines containing
at least $sk/(100L)$ points of $S$. If $|\mathcal L_1|\ge L/100$,
we have already finished. Otherwise the other lines supply fewer
than $sk/100$ incidences, and at least $9s/10$ points of $S$ lie on
at least $9k/10$ lines of $\mathcal L_1$. Partition these points
according as their multiplicity in $\mathcal L_1$ is at least $k$ or
less than $k$. One class has at least $9s/20$ points. Its
multiplicities lie between $k_1$ and $2k_1$, where either $k_1=k$ or
$k_1=\lceil9k/10\rceil\ge3$. The induction hypothesis applies with
$L_1=|\mathcal L_1|KH(m,s)$. Repeatedly
delete a line having fewer than
\[
T=\frac K4(\sqrt m+s)
\]
distinct intersection points with other currently retained lines.
Each deletion loses fewer than $T$ two-rich points. The remaining
set of $M\le m$ lines therefore has more than $3KH(m,s)/4$
two-rich points and is nonempty. Every remaining line has at
least $T$ distinct intersections with the other remaining lines.
Select each remaining line independently with probability $64/K$.
For each fixed remaining line choose one witness line at every
distinct intersection point. These witnesses are distinct. The
number $X$ of selected witnesses is a binomial random variable
with mean at least $16\sqrt m$. The elementary binomial tail
bound $\Pr(X<\mathbb EX/2)\le\exp(-\mathbb EX/8)$ gives
\[
\Pr(X<8\sqrt m)\le e^{-2\sqrt m}.
\]
For completeness, this tail bound follows by applying Markov's
inequality to $e^{-\lambda X}$ and the inequality
$1+p(e^{-\lambda}-1)\le\exp(p(e^{-\lambda}-1))$, then taking
$\lambda=\log2$; the resulting exponent is at most
$-\mathbb EX/8$. A union bound over all remaining lines costs at
most $me^{-2\sqrt m}\le e^{-2}<1/4$. Markov's inequality also
shows that with probability at least $1/2$ the number $q$ of
selected lines is at most $128M/K$. There is therefore a choice
with both properties. It necessarily has $q\ge1$.
Set $D=\lceil\sqrt{6q}\rceil$. A polynomial of degree at most
$D$ has $\binom{D+3}{3}$ coefficients, and vanishing on a line
imposes at most $D+1$ linear conditions. Since
$(D+3)(D+2)>6q$, there is a nonzero real polynomial vanishing on
every selected line. Moreover
\[
D<4\sqrt q,\qquad D^2\le2048m/K,
\]
and $D<8\sqrt m$ for our choice of $K$. Each remaining line
contains at least $8\sqrt m$ distinct points on the selected
lines, so the polynomial vanishes identically on all $M$ remaining
lines. Replace it by its square-free part.
Factor the polynomial over $\mathbb C$. Retain the real,
absolutely irreducible, geometrically ruled factors. At most
$b\le18D^2$ of the $M$ lines fail to lie on their union. Indeed,
Lemma~\ref{ci:flecnode} bounds the lines on each nonruled factor
of degree $d_i$ by $17d_i^2$. A real line on a factor which is
not real up to a scalar also lies on its distinct conjugate;
B\'ezout bounds such lines by $d_i^2$. Summing these bounds and
using $\sum d_i\le D$ proves the assertion. Thus
\[
b\le36864m/K\le m/4.
\]
Every one of these $b$ lines meets the retained ruled union in at
most $D$ points, since it is not contained in that union.
Lemma~\ref{ci:ruled-count} bounds intersections among the ruled
lines by $5Dm+sm/2$. The induction hypothesis, with the original
cap $s$, bounds intersections among the $b$ other lines by
$KH(b,s)$. Altogether the remaining configuration has at most
\[
6Dm+sm/2+KH(b,s)
\le(49+K/4)H(m,s)
\]
two-rich points. Here $D<8\sqrt m$ and
$H(b,s)\le H(m,s)/4$ were used. Taking $K>98$, in addition to
the preceding requirements, contradicts the lower bound
$3KH(m,s)/4$. This completes the induction.
\end{proof}
\subsection{The planar distinct-distance estimate}
\begin{lemma}[Concentration of planar Cayley lines]\label{ci:cayley-caps}
For two finite planar sets $U,V$ of sizes $u,v$, the $uv$ lines
\eqref{ci:cayley-line} have at most $\min(u,v)$ members in a plane
and at most $6u+2v$ members in a regulus.
\end{lemma}
\begin{proof}
Distinctness and the plane bound were proved in
Corollary~\ref{ci:planar-motions}. Fix $x\in U$ and allow the
other endpoint $y$ to range over all of $\mathbb R^2$. These lines
partition $(t,c)$-space: at every point their equation uniquely
determines
\[
y=(I+tJ)^{-1}\bigl((I-tJ)x-2c\bigr).
\]
Their nonparallel directions and lack of intersections mean that
they are pairwise skew even projectively. The polynomial vector
field
\[
W_x(t,c)=\bigl(1+t^2,(tI+J)(c-x)\bigr)
\]
is nowhere zero over $\mathbb R$ and tangent to this family.
Indeed along its line through $(t,c)$ the derivative of $c$ with
respect to $t$ is $(tI+J)(c-x)/(1+t^2)=-J(x+y)/2$.
Let a regulus have irreducible quadratic equation $f=0$. Every
line in this fixed-$x$ family contained in the regulus is a common
line of $f$ and $W_x\cdot\nabla f$. The latter has degree at
most three. If there are at least seven such lines, B\'ezout
forces
\[
W_x\cdot\nabla f=h f
\]
for a polynomial $h$. Every member of the fixed-$x$ family
through a real point of the regulus is then entirely contained
in it. To verify this without an appeal to invariance of flows,
restrict to that line and write $g(t)=f(t,c(t))$. The identity
becomes
\[
(1+t^2)g'(t)=h(t,c(t))g(t).
\]
A nonzero polynomial $g$ cannot have a real root: at a root its
derivative has strictly smaller vanishing order, while $1+t^2$
does not vanish. The chosen line has such a root, so $g$ is
identically zero.
Thus this fixed-$x$ family supplies a full real affine ruling of the
regulus. Its lines are pairwise projectively skew, so they all
belong to the same ruling. Conversely, coverage of every real
affine point implies that no real affine line of that ruling is
missing. A ruling line contained in the plane at infinity is
irrelevant here.
Different fixed-$x$ families share no line, because the slope
and intercept recover both endpoints. There are only two
rulings, so at most two values of $x$ contribute seven or more
lines. They contribute at most $2v$ lines in all; the others
contribute at most $6u$. This proves the claimed cap.
\end{proof}
\begin{theorem}[Planar distinct distances]\label{ci:planar-distances}
Every finite set $Q\subset\mathbb R^2$ of $n\ge2$ points determines
at least $c n/\log(2n)$ distinct positive distances.
\end{theorem}
\begin{proof}
Two distinct ordered matches determine a unique orientation-preserving
planar isometry whenever the matched segments have the same positive
length. There are consequently finitely many direct isometries
with at least two matches from $Q$ to itself. Rotate a second copy
of $Q$ by a generic rotation $R_0$ to form $Q'=R_0Q$. We may
ensure that none of the direct isometries with two matches from
$Q$ to $Q'$ has linear part $-I$: each is $R_0g$ for one of the
finitely many just described, and each excludes only one rotation
$R_0$. All these motions therefore lie in the Cayley chart used
in \eqref{ci:cayley-line}. Translations lie in this chart as well.
Use the $n^2$ lines for the pairs $(x,y)\in Q\times Q'$.
Lemma~\ref{ci:cayley-caps} gives plane cap $n$ and regulus cap
$8n$. Theorem~\ref{ci:two-rich} bounds the two-rich points by
$Cn^3$. For $3\le k\le n$, Theorem~\ref{ci:rich-lines} bounds
the $k$-rich points by
\[
C\left(\frac{n^3}{k^2}+\frac{n^3}{k^3}+\frac{n^2}{k}\right)
\le C'\frac{n^3}{k^2}.
\]
Multiplicity equals the number of matches, by the bijective
Cayley representation, and it is at most $n$.
For each positive distance $\rho$ let $a_\rho$ be the number of
ordered pairs of distinct points of $Q$ at distance $\rho$.
The corresponding number for $Q'$ is also $a_\rho$. Every
ordered pair of equally long nonzero segments, one from each
cloud, gives the unique direct isometry described above. A motion
with $k$ matches contributes exactly $k(k-1)$ such pairs.
Splitting multiplicities into intervals $[2^j,2^{j+1})$, $j\ge1$,
and using the preceding bounds yields
\[
\sum_\rho a_\rho^2
=\sum_g k_g(k_g-1)
\le C n^3\log(2n).
\]
Since $\sum_\rho a_\rho=n(n-1)$, Cauchy--Schwarz gives
\[
|\Delta(Q)|\ge
\frac{n^2(n-1)^2}{Cn^3\log(2n)}
\ge c\frac n{\log(2n)}.
\]
\end{proof}
\begin{corollary}[Planar occupancy]\label{ci:planar-occupancy}
If a finite set in Euclidean space determines at most $M\ge1$ positive
distances, then any affine two-plane contains at most
$CM\log(2M)$ of its points. In particular, along a sequence with
$B\longrightarrow\infty$ and $M=o(B^2)$, every two-plane has at
most $B^{2+o(1)}$ points, uniformly in the plane.
\end{corollary}
\begin{proof}
For an occupancy $n\ge2$, Theorem~\ref{ci:planar-distances} gives
$n\le CM\log(2n)$. The elementary inequality
$\log(2n)\le C\sqrt n$ first yields $n\le C'M^2$; substitute
this back into the logarithm to get $n\le C''M\log(2M)$.
Occupancies zero and one are harmless. If $M=o(B^2)$, eventually
$M\le B^2$, so the uniform bound is $O(B^2\log(2B))$, which is
$B^{2+o(1)}$.
\end{proof}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/classical-incidence.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/concentration.tex ====
\section{Uniform concentration of evaluation flats}
\label{conc:section}
We prove the algebraic estimate used twice in the distance argument. Its
constant is uniform in the scale parameter. The distinction between the
two versions below is essential: the global family has a cardinality
bound, whereas a family inside one of its flats need not have one.
Throughout this section, varieties are reduced complex algebraic
varieties. The degree of an affine variety means the degree of its
projective closure; the degree of a pure-dimensional union is the sum of
the degrees of its irreducible components. Constants denoted by $C_e$
may change from line to line and depend only on $e$.
Let $E$ be a complex vector space of dimension $e\geq3$, and write
\[
S=\bigwedge^2E^*,\qquad n=\binom e2,\qquad
r=e-1,\qquad s_0=n-r=\binom{e-1}{2}.
\]
An element $z\in S$ is regarded as a skew map $E\to E^*$. Set
\[
\mathcal Q=\{[v:y]\in\mathbf P(E\oplus E^*):y(v)=0\}.
\]
For $\lambda=[v:y]\in\mathcal Q$ with $v\ne0$, define
\begin{equation}
F_\lambda=\{z\in S:zv=y\},\qquad
K_v=\{z\in S:zv=0\}.
\label{conc:flat-model}
\end{equation}
Evaluation at $v$ maps $S$ onto the $r$-dimensional annihilator of $v$.
Consequently $F_\lambda$ is a nonempty affine $s_0$-flat, with direction
$K_v=\bigwedge^2(E/\mathbb Cv)^*$. Distinct parameters give distinct
flats. Indeed, the common radical of the forms in $K_v$ is exactly
$\mathbb Cv$: the quotient has dimension at least two, and each of its
nonzero vectors is detected by an alternating form. The direction of
the flat therefore recovers $[v]$, and its prescribed evaluation recovers
$y$ with the same normalization.
A maximal projective linear subspace of $\mathcal Q$ is a
$\mathbf P^r$. Equivalently, it is the projectivization of an
$e$-dimensional totally isotropic subspace for the quadratic form
$(v,y)\mapsto y(v)$.
\begin{theorem}[Uniform concentration]
\label{conc:theorem}
Fix $C_0\geq1$. Let $A\geq1$ and let $\mathcal P$ be a finite set of
distinct parameters $[v:y]\in\mathcal Q$, all with $v\ne0$. Assume:
\begin{enumerate}
\item[(i)] For every $\lambda\in\mathcal P$ there is a homogeneous polynomial
of positive degree at most $C_0A$ which is nonzero at $\lambda$ and
zero at every other member of $\mathcal P$.
\item[(ii)] Every projective $\mathbf P^r\subset\mathcal Q$ contains at most
$C_0A^{r-1}$ members of $\mathcal P$.
\end{enumerate}
There is a constant $C=C(e,C_0)$ such that
\begin{equation}
\#\{\lambda\in\mathcal P:F_\lambda\subset V\}
\leq C\deg(V)A^h,
\qquad \dim V=s_0+h,\quad 1\leq h0$ and is a component of $Z(f_1,\ldots,f_c)$, where
\[
\deg f_i\leq D,\qquad
\prod_i\deg f_i\leq C_n\deg V,\qquad D\geq1,
\]
with the dimensional constant from Theorem~\ref{conc:walsh}.
There are polynomials $g_1,\ldots,g_c\in I(V)$ of degrees $O_n(D)$
whose differentials are independent at the generic point of $V$.
Moreover, a polynomial $H_0$ of degree $O_n(D)$, nonzero on $V$, can be
chosen so that $V\setminus Z(H_0)$ is smooth and has tangent space
\[
T_zV=\bigcap_{i=1}^c\ker dg_i(z)
\qquad(z\in V\setminus Z(H_0)).
\]
\end{lemma}
\begin{proof}
Put $P=I(V)$ and consider the regular local ring
\[
R=\mathbb C[x_1,\ldots,x_n]_P,\qquad
\mathfrak m=PR,\qquad K=R/\mathfrak m=\mathbb C(V).
\]
Its dimension is $c$. Because $V$ is an isolated component of the
common zero set at its generic point, $J=(f_1,\ldots,f_c)R$ is
$\mathfrak m$-primary. Its generators form a parameter sequence,
which is regular because $R$ is Cohen--Macaulay
\cite[Tags~00OQ, 00NQ, and 02JN]{stacksproject}.
We first bound the length of $R/J$ by a dimensional constant.
Write $k=\dim V$. A general projective linear projection of
$\overline V$ to $\mathbf P^k$, with center in the hyperplane at
infinity disjoint from $\overline V$, is finite and has degree
$\deg V$. Finiteness follows because a positive-dimensional projective
fiber would meet its hyperplane lying in the projection center.
Restricting to the affine chart and changing affine coordinates gives
base coordinates $t_1,\ldots,t_k$ and complementary coordinates
$w_1,\ldots,w_c$. Over $F=\mathbb C(t_1,\ldots,t_k)$, the generic
fiber of $V$ is a closed point of $\mathbb A^c_F$ with residue field
$K$, where $[K:F]=\deg V$. Localizing $F[w_1,\ldots,w_c]$ at that
point gives the same ring $R$.
After extending $F$ to an algebraic closure, this point splits into
$[K:F]$ points, since the extension is separable. The sum of their
local intersection multiplicities for the equations $f_i$ is
$[K:F]\operatorname{length}_R(R/J)$. They are isolated common zeros;
other components of the system do not affect their isolated B\'ezout
bound \cite[Theorem~12.3 and Example~12.3.1]{fulton1998}.
The equations $f_i$ define hypersurfaces in regular local ambient
rings, so these factors are Cohen--Macaulay and the isolated
complete-intersection multiplicity equals the quotient length;
see \cite[Example~12.3.7(ii)--(iii)]{fulton1998} for this identification
and its Cohen--Macaulay hypothesis. Hence
\begin{equation}
\operatorname{length}_R(R/J)
\leq\frac{\prod_i\deg f_i}{\deg V}\leq C_n.
\label{conc:local-length}
\end{equation}
Choose an integer $L=O_n(1)$ at least this length. The maximal ideal
of an Artinian local ring of length at most $L$ has $L$th power zero,
so
\begin{equation}
\mathfrak m^L\subset J.
\label{conc:adic-bound}
\end{equation}
We construct the $g_i$ one at a time. Suppose $g_1,\ldots,g_u$ have
independent classes in $\mathfrak m/\mathfrak m^2$, where $u0$, choose a $u$-square
Jacobian block $J_0$ of $(g_1,\ldots,g_u)$ whose determinant $\Delta$
is nonzero in $K$. If $J_t$ is any remaining column, form a polynomial
vector field having coefficient $\Delta$ in coordinate $t$ and
coefficients $-\operatorname{adj}(J_0)J_t$ in the chosen coordinates.
These $n-u$ fields, denoted by $\delta_\alpha$, satisfy
\[
\delta_\alpha g_i=0\quad(1\leq i\leq u)
\]
as polynomial identities. Thus they extend to $R$ and descend to
$R_u$. If the $g_i$ have maximum degree $E_u$, the coefficient degrees
of these fields are $O_n(E_u)$.
At the generic point, the fields span the common kernel of the
$d g_i$. The conormal map
$\mathfrak m/\mathfrak m^2\to K^n$, $f\mapsto df$, is injective there,
as $V$ is generically smooth in characteristic zero. It follows that
the residue evaluations of the $\delta_\alpha$ span the dual of
$\mathfrak m_u/\mathfrak m_u^2$. These residue evaluations are
$K$-linear: the extra Leibniz term from differentiating a coefficient
has a factor in $\mathfrak m_u$.
Take an $f_i$ of order $b$ as above. A derivation lowers adic order by
at most one, so fewer than $b$ of these derivations still give zero
residue. Some composition of $b$ of them has nonzero residue. Indeed,
the leading term of $f_i$ belongs to the degree-$b$ piece of the graded
ring of $R_u$ \cite[Tag~00NO]{stacksproject}, namely
\[
\mathfrak m_u^b/\mathfrak m_u^{b+1}
\simeq\operatorname{Sym}^b_K(\mathfrak m_u/\mathfrak m_u^2).
\]
Its polarization is nonzero in characteristic zero. Since the residue
functionals span the dual, some $b$-tuple detects it. In computing
that residue, terms in which a derivation hits a coefficient retain a
positive-order factor and vanish. This gives exactly the asserted
iterated derivative.
Stop immediately before the last differentiation and call the resulting
polynomial $g_{u+1}$. Its residue in $R_u$ is zero, so it belongs to
$P$. Its derivative has nonzero residue, so its class in
$\mathfrak m_u/\mathfrak m_u^2$ is nonzero. It adds an independent
conormal. This procedure uses at most $L-1$ derivatives per stage and
at most $c$ stages. Applying a polynomial field of coefficient degree
$T$ to a degree-$B$ polynomial gives degree at most $B+T-1$; the bounds
on $L$ and $c$ therefore keep every $g_i$ of degree $O_n(D)$.
Finally choose a $c$-square minor $H_0$ of the Jacobian of the $g_i$
which is nonzero on $V$. Its degree is $O_n(D)$. Where it is nonzero,
the common zero set of the $g_i$ is locally smooth of dimension $n-c$.
The contained variety $V$ has the same dimension, so its germ equals
that smooth germ. This proves the assertion about tangent spaces.
\end{proof}
\subsection{Recovering actual rulings from tangent directions}
In a chart $v_a=1$, a \emph{ruling incidence} is an irreducible set of
pairs $(z,v)$ for which $z+K_v\subset V$. Its parameter map is
\begin{equation}
(z,v)\longmapsto[v:zv].
\label{conc:parameter-map}
\end{equation}
The point of the next lemma is that both the number of such incidences
and the degree of their exceptional set can be controlled.
\begin{lemma}[Controlled ruling incidences]
\label{conc:rulings}
Let $V\subset S$ be irreducible of dimension $k=s_0+h$, with
$1\leq h0\).
We claim that \(A_*=H_*\). Otherwise let
\(q=\dim(A_*\cap H_*)K_2>\cdots>K_{r-1}>C_0,
\]
to be fixed below in terms of $e,C_0$. Consider an allowed carrier
$V$ of dimension $s_0+h$, with $1\leq hK_hA$. Let $ph$, so $\dim W=s_0+i$. From
\eqref{conc:description-product},
\begin{equation}
\deg V\geq C_n^{-1}\deg W(K_hA)^{i-h}.
\label{conc:degree-comparison}
\end{equation}
In Case (b), the minimal first equation has degree at most $C_0A$.
Since $K_h>C_0$, it belongs to the prefix. Therefore $p\geq1$,
$ih\\i\text{ available}}}
\frac{CR_i}{K_h^{i-h}}\right\},
\qquad1\leq h4C+4,\qquad \kappa>4Cc_1.
\]
Take $K_{r-1}\geq\max(2,C_0+1)$, and successively set
$K_h=\kappa K_{h+1}$ for $h=r-2,\ldots,1$. Define barriers
\[
B_h=c_1K_hB_{h-1}\quad(1\leq h1$, each term in its right
side is strictly less than $TB_h$, contradicting maximality. Hence
$R_h\leq B_h$ for every available index. This is
\eqref{conc:bound}, with a constant depending only on $e,C_0$.
\end{proof}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/concentration.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/depth.tex ====
\subsection{Projection depth for separated windows}\label{dep:section}
We retain the notation and contradiction regime \eqref{red:regime}.
Let $P_x,P_y$ be the two pieces selected by
Proposition~\ref{prof:pair-selection}, in separated windows of widths
$v$ and $s$, respectively. Thus $v,s\to\infty$, both are
$o(\log B)$, and either $v/s\to0$ or $v/s\to\infty$.
The limiting normalized drop profile is the same for both pieces.
Before using the target plateaux, omit from $P_y$ the points left
unassigned by the global terminal assignment in
Proposition~\ref{prof:pair-selection}. Its proof bounds their number
by $o(|P_y|)$ uniformly over the pieces, so this removes
$o(|P_x||P_y|)$ ordered pairs. Continue to write $P_y$ for the
retained target set. It has size $N\exp(-o(s))$ and inherits the
profile conclusions, since it is a $(1-o(1))$ fraction of the
selected piece. The proposition below uses this retained $P_y$.
For the target piece write
\[
D_i=B\exp(b_i s),\quad e_j=\prod_{i\le j}D_i,
\quad l=d-j,
\]
and consider a positive-dimensional plateau after at least one drop.
The path equations defining its current system have degrees
$B\exp(O(s))$. For this plateau, fix one containing
$l$-dimensional carrier for each point of $P_y$. On the final
one-dimensional plateau use its carrier from the global terminal
assignment. Pool repeated carriers and denote the resulting family
by $\mathcal Y$, with disjoint assigned target sets of masses $n_Y$.
Thus $\sum_{Y\in\mathcal Y}n_Y=|P_y|$. All later incidence and list
restrictions use this fixed assignment.
Our objective is a lower bound for the degree of the distinct
projected components carrying any fixed positive fraction of target
mass. Several components may share a projected image, and each
projection may have degree greater than one. We control this combined
multiplicity after deleting negligible incidence mass.
Give a center--component incidence $(p,Y)$ normalized weight
$n_Y/(|P_x||P_y|)$. The weight of a collection is thus the probability
that a uniformly chosen center and a uniformly chosen assigned target
point determine an incidence in that collection.
We use the following precise interpretation of exponential accuracy.
An assertion with a factor $\exp(o(s))$ in a lower bound means that
for every fixed $\epsilon>0$ it holds with the smaller factor
$\exp(-\epsilon s)$ for all sufficiently large members of the
sequence, after the stated vanishing-mass deletions.
All finite choices of plateaux, density constants, and positive
logarithmic tolerances can be imposed simultaneously.
\begin{proposition}[Projected degree in separated windows]
\label{dep:projected-degree}
For each fixed positive tolerance $\epsilon$, one can discard
center--target-component incidences of total normalized weight
$o(1)$, and then discard $o(|P_x|)$ centers, so that the following
holds. For each remaining center $p$, every target component $Y$
whose incidence $(p,Y)$ remains satisfies
$\dim\overline{\pi_pY}=l$. For every subcollection of those components
carrying at least a fixed positive fraction of $|P_y|$, the distinct
projected components have summed degree at least
\begin{equation}\label{dep:degree-bound}
\frac{e_j}{R}\exp(-\epsilon s).
\end{equation}
The assertion is uniform over those subcollections, including ones
chosen after $p$ and after subsequent equations have been chosen.
The following values of $R$ are valid:
\begin{align}
R&=D_1 &&\text{in either orientation};
\label{dep:first-R}\\
R&=B\exp\left(-s\sum_{i>j}b_i\right)
&&\text{if }v/s\longrightarrow0;
\label{dep:narrow-R}\\
R&=B\exp(-2s)
&&\text{if }v/s\longrightarrow\infty,
\quad b_{j+1}>0,\quad l0$ independent of the sequence. After fixing
$\epsilon$ and any finite batch of plateaux and tolerances, the
incidence and center deletions are independent of the later fixed
choice of $\rho$; only the large-index threshold may depend on
$\rho$.
\end{proposition}
\begin{proof}
We first explain the degree and mass bookkeeping common to all three
cases, then prove their depth bounds.
\paragraph{Components, multiplicity, and incidence deletions.}
Proposition~\ref{prof:budget} gives
\begin{equation}\label{dep:carrier-budget}
\sum_{Y\in\mathcal Y}\deg Y\le e_j\exp(o(s)),
\qquad
\sum_{Y\in\mathcal A} n_Y
\le \deg(\mathcal A)\left(\prod_{i>j}D_i\right)\exp(o(s))
\end{equation}
for every subcollection $\mathcal A$.
Since $\sum_i b_i=0$ and $|P_y|=N\exp(-o(s))$, every subcollection
of fixed positive assigned mass has degree at least
$e_j\exp(-o(s))$.
Every $Y\in\mathcal Y$ is an irreducible component of the fixed target
path locus, by the component argument at the start of the proof of
Proposition~\ref{prof:regularity}. Larger components elsewhere remain
in the target equations.
Projection from $p$ can drop the dimension of $Y$ only if its generic
fiber is a line. For a fixed general smooth $y\in Y$, this puts $p$
in the proper affine tangent flat $y+T_yY$. The flat cap makes the
proportion of such centers at most $B^{-c_0+o(1)}$, uniformly for each
$Y$. Also, Corollary~\ref{poly:high-multiplicity} puts centers where
$\operatorname{mult}_pY>\deg(Y)/2$ in a hypersurface of bounded degree.
The initial full-dimensional no-capture property of the center piece
makes their proportion $o(1)$: its initial cutoff is $B^{1+o(1)}$,
well above every bounded degree. Average both conclusions with weights
$n_Y/|P_y|$. They remove only $o(1)$ of the center--component incidence
mass.
At every retained incidence, the point-projection formula gives
\begin{equation}\label{dep:projection-formula}
t_p(Y)\deg\overline{\pi_pY}
=\deg Y-\operatorname{mult}_pY
\ge\tfrac12\deg Y,
\end{equation}
where $t_p(Y)$ is the generic map degree. For a fixed $p$, group
components having the same projected image $Z$ and define their depth
to be the sum of their map degrees. If all retained groups have depth
at most $R\exp(\eta s)$, then any subcollection of degree $a$ has
projected degree at least
\begin{equation}\label{dep:depth-to-degree}
a\big/\bigl(2R\exp(\eta s)\bigr).
\end{equation}
Thus it suffices to bound depth after negligible weighted incidence
deletions. Fixed constants and the errors in
\eqref{dep:carrier-budget} are absorbed by choosing
$\eta>0$ sufficiently smaller than the desired $\epsilon$.
Whenever the deleted incidence mass is $\alpha=o(1)$, Markov's
inequality leaves all but $\sqrt\alpha$ of the centers with deleted
target mass at most $\sqrt\alpha$. Every later subcollection of
fixed positive mass still has positive mass after this deletion.
This is the uniformity mechanism in the proposition. No union bound
over the possible subcollections will be needed.
\paragraph{The first-cut bound.}
Use the system at the first plateau after a drop. Its equations have
degrees at most $D_1\exp(o(s))$, and every current descendant is
contained in this first system. The regularity conclusion of
Proposition~\ref{prof:regularity} makes its relevant carrier unique
and smooth at all but $o(|P_y|)$ assigned target points. For each such
point $q$, centers $p$ in its affine tangent flat form a
$B^{-c_0+o(1)}$ fraction of the source piece.
If, for a center and a current descendant $Y$, the generic joining ray
were contained in the first system, then the same containment holds
for every point of $Y$ where the ray is defined, by polynomial
identity. At an assigned regular point $q$ the line would lie locally
in its unique first carrier, so its direction would be tangent there.
The preceding averaging therefore discards all such
center--descendant incidences at negligible mass. On every other
generic ray at least one first-system equation restricts nontrivially.
Its degree bounds the number of distinct intersections with all
current target components by $D_1\exp(o(s))$. In characteristic zero,
the generic fibers defining the map degrees consist of distinct
points. This proves the depth bound for \eqref{dep:first-R}.
Only regularity of the carrier is used here; the original path
equations need not themselves have full Jacobian rank.
\paragraph{Centers in the narrower window.}
Suppose $v/s\to0$. The center piece can be simultaneously isolated as
zero-dimensional components of equations of degree
\[
L=B\exp(o(s)),\qquad |P_x|=N\exp(o(s)),
\]
where the second error is signed. Fix $Y\in\mathcal Y$, and choose
$y$ general on it, also general for the projections from all finitely
many actual centers. For each center, count the additional moving
roots $z\ne y,p$ on target components whose images agree with
$\overline{\pi_pY}$. These points are generic on their components.
Here this includes avoiding their intersections with the other members
of the same finite family $\mathcal Y$. Their number is the group
depth minus the one fixed root $y$.
Parametrize such pairs by
\[
p=y+t(z-y),\qquad z\in\bigcup_{Z\in\mathcal Y}Z.
\]
Impose the center-isolating equations on this parametrization.
At every counted solution the image point $p$ is isolated in the
center system. At its root $z$, the target union is locally just
the one member of $\mathcal Y$ containing that root, by the preceding
genericity condition. The generic ray has finite intersection with
that component, so the fiber is locally finite. Thus the solution is
isolated on the variety parametrized by $(z,t)$.
This variety has dimension $l+1$ and degree at most a dimensional
constant times $\sum_Z\deg Z$; the pulled-back equations have degree
at most $2L$. The isolated-intersection form of B\'ezout therefore
bounds the total number, over all centers, by
\begin{equation}\label{dep:narrow-root-count}
C e_j\exp(o(s))L^{l+1}.
\end{equation}
Possible larger components of the center equations away from their
isolated sample points do not affect this count.
Divide \eqref{dep:narrow-root-count} by $|P_x|$. Its value, to the
stated accuracy, is
\[
\frac{e_j B^{l+1}}{N}
=B\exp\left(s\sum_{i\le j}b_i\right)
=B\exp\left(-s\sum_{i>j}b_i\right)=R.
\]
The fixed root adds only one; $R=B^{1+o(1)}\to\infty$.
For every fixed logarithmic slack $\eta>0$, Markov's inequality bounds
the proportion of centers whose depth at this $Y$ exceeds
$R\exp(\eta s)$ by $\exp(-\eta s+o(s))$.
Weighted averaging in $Y$, followed by the row deletion already
described, proves \eqref{dep:narrow-R}.
\paragraph{Centers in the wider window: the generic lists.}
Suppose $v/s\to\infty$, $b_{j+1}>0$, and $l0\}\ge l,
\qquad k0\) such that
every finite set \(P\subset\mathbb R^d\) of \(n\ge2\) distinct points
satisfies
\[
|\Delta(P)|\ge c_d n^{2/d}.
\]
\end{theorem}
This resolves the higher-dimensional Erd\H{o}s distinct-distances
conjecture positively. No assumption is made on the position, spacing,
or concentration of the points. The power of \(n\) is optimal:
the integer grid \(\{1,\ldots,t\}^d\) has \(t^d\) points, and its squared
distances are integers between \(1\) and \(d(t-1)^2\). In the plane,
the square-grid construction gives \(O(n/\sqrt{\log n})\)
distances~\cite{erdos1946}; the planar problem consequently
has a different conjectural order.
\subsection{Historical context and the methods of the proof}
Higher-dimensional distance estimates developed in part through
incidence bounds for curves and spheres. Clarkson, Edelsbrunner,
Guibas, Sharir, and Welzl bounded the number of pairs realizing a fixed
positive distance in three dimensions, giving a distinct-distance
lower bound at the square-root scale, up to a slowly growing
factor~\cite{ClarksonEdelsbrunnerGuibasSharirWelzl1990}.
Aronov, Pach, Sharir, and Tardos improved the three-dimensional lower
bound to \(\Omega_\varepsilon(n^{77/141-\varepsilon})\) for each
\(\varepsilon>0\) and propagated improvements to higher
dimensions~\cite{AronovPachSharirTardos2004}.
Their three-dimensional estimate is \emph{pinned}: it finds a point
of the given set from which that many distinct distances occur.
Solymosi and Vu developed two recursive inequalities connecting
distance bounds in lower and higher dimensions
\cite[Theorems~2.1--2.2]{SolymosiVu2008}.
The recurrences have separate forms for the total number of distances
and for the maximum number measured from one point of the set. We use
the forms for total distances in the comparisons below. Their original theorem gives
\(\Omega(n^{0.5643})\) distances in dimension three and
\(\Omega_d(n^{2/d-2/(d(d+2))})\) for every fixed \(d\ge4\)
\cite[Theorem~1.1]{SolymosiVu2008}.
A different approach counts repeated distances through rigid motions
matching subsets of the point sets. Elekes and Sharir developed this viewpoint for the planar
problem~\cite{elekessharir2011}. Guth and Katz reduced the resulting
planar motion count to incidences of points and lines in three-dimensional
space and combined polynomial partitioning with ruled-surface geometry to prove
the planar bound \(\Omega(n/\log n)\)
\cite[Theorem~1.1 and Sections~2--4]{guthkatz2015}.
That bound supplies the two-dimensional input to our induction.
Bardwell-Evans and Sheffer extended the rigid-motion approach to
higher dimensions through a reduction to incidences of
\((d-1)\)-flats in \(\mathbb R^{2d-1}\)
\cite{BardwellEvansSheffer2019}. Their work identifies structural
restrictions on the resulting flats and the need to control their
concentration in algebraic varieties.
Combining the Guth--Katz planar bound with the first Solymosi--Vu
recurrence gives \(\Omega(n^{3/5}/(\log n)^{2/5})\) distances in
dimension three~\cite[Theorem~2.1]{SolymosiVu2008}.
More recently, Tidor, Yu, and Zakharov proved
\(n^{2/3-o(1)}\) distinct distances for arbitrary point sets in
\(\mathbb R^3\)~\cite[Theorem~1.1]{tidoryuzakharov2026}.
Inserting their three-dimensional distance bound into the Solymosi--Vu
recurrences gives \(n^{8/17-o(1)}\) in dimension four and
\(n^{3/8-o(1)}\) in dimension five
\cite[Corollaries~2.3 and~2.6]{SolymosiVu2008}.
The \(o(1)\) terms here absorb the subpolynomial loss in that input.
The leading exponents in these two deductions still fall below the
conjectured value \(2/d\).
Bounds for points on prescribed surfaces, or for distances from a
single point, have different hypotheses or conclusions.\footnote{An
earlier manuscript of Aksoy Yazici claimed
the constant-factor bound in all dimensions \(d\ge3\), but was
withdrawn by the author because the proof of its Theorem~1.2 is not
correct~\cite{AksoyYazici2020Withdrawn}.}
Tidor, Yu, and Zakharov's proof develops rigid-motion flat geometry,
regular approximate complete intersections, and degree-sensitive
incidence estimates. These methods provide close antecedents for
several parts of the argument below: the physical and
opposite-orientation flat families, the recovery of actual families
of contained flats from tangent data, and the geometric treatment of
projected curves
\cite[Sections~3--6 and~10.2--10.3]{tidoryuzakharov2026}.
The algebraic argument draws on Hilbert function estimates of Chardin
and Chardin--Philippon
\cite{chardin1989,chardinphilippon1999,chardinphilippon2002erratum},
and on Walsh's work on approximate complete intersections and
algebraic concentration~\cite{walsh2020,walsh2023}.
Hilbert functions measure how many independent
polynomial conditions a set can impose. Approximate complete
intersections cut out an irreducible variety as a component of the
common zero set of equations whose product of degrees is controlled
by the variety's degree.
We use these two ideas to keep track of concentration at several
polynomial degree scales. The uniform concentration theorem for
evaluation flats of skew forms, including its exceptional parameter
families, is proved in full in Appendix~\ref{conc:section}.
The real incidence arguments, including the planar distinct-distance
bound, are supplied in Appendix~\ref{ci:section}; their relation to
the work of Szemer\'edi--Trotter, Beck, Elekes--Sharir, and Guth--Katz
is recorded where each argument is used.
\subsection{Why the constant factor matters}
An estimate \(|\Delta(P)|\ge n^{2/d-o(1)}\) does not by itself imply
Theorem~\ref{thm:main}. The ratio \(|\Delta(P)|/n^{2/d}\) could still
tend to zero more slowly than every negative power of \(n\).
To obtain a constant factor, the proof must exclude every such
sequence, without first fixing a power saving.
We therefore argue in the least dimension \(d\ge3\) in which the
theorem could fail, and use the notation
\[
N=|P|,\qquad B=N^{1/d},\qquad A=B^2,\qquad
M=1+|\Delta(P)|.
\]
Failure would give a sequence with \(N\to\infty\) and \(M/A\to0\).
The lower-dimensional bounds limit the number of points in any
proper affine flat. They do not prevent substantial concentration
on more general varieties, nor do they identify a single polynomial
degree at which all of that concentration can be studied.
The multiscale argument below addresses this second difficulty.
\subsection{Overview of the proof}
\paragraph{1. Select directions that admit interpolation.}
For distinct points \(p,q\), let
\(\pi_p(q)=[q-p]\in\mathbb P^{d-1}\) denote their projective direction.
We seek a positive fraction of the unordered pairs of points such
that, at each center \(p\), homogeneous polynomials of degree
\(\lfloor A\rfloor\) can prescribe arbitrary values at the selected
displacement vectors \(q-p\). Equivalently, the corresponding evaluation
vectors are linearly independent. The selection must be symmetric:
a pair is retained or removed at both endpoints.
The principal geometric obstruction would be a collection \(C_p\)
of projective curves at each center, each curve spanning at most a
projective plane, with total degree \(o(N/A)\), such that almost
every pair \(\{p,q\}\) satisfies
\[
\pi_p(q)\in C_p\quad\hbox{or}\quad\pi_q(p)\in C_q.
\]
The union of the corresponding lines through \(p\) is a cone;
the small total degree explains the term \emph{sparse cones}.
Theorem~\ref{sc:theorem} rules out this coverage, including the
choice of either endpoint for each pair. Once it is excluded, greedy
removal of curves containing too many directions leaves a positive
fraction of pairs with controlled concentration on every projective
variety. A maximal symmetric selection then gives the interpolation
property (Propositions~\ref{red:directions} and
\ref{red:independent-stars}). This last linear-algebra argument costs
only a fixed fraction of pairs.
\paragraph{2. Exclude sparse cones at all degree scales.}
The sparse-cones theorem occupies the central part of the paper.
Section~\ref{sec:profiles} divides the point set according to how
successive polynomial equations cut down the dimension of the
varieties containing its points. It tests degrees in windows
\([B e^{-s},B e^s]\) with several width parameters \(s\), instead of
fixing a single power of \(N\). Points isolated by equations of
sufficiently small degree form a core that is handled directly.
Each remaining piece carries a fixed chain of proper hypersurface
cuts, ending in isolated points.
A cut is proper when its equation does not vanish identically on
the component being cut. The testing degrees at these cuts form a
\emph{scale profile}. Between consecutive cuts, the dimension stays
constant, and Hilbert-function estimates give a lower bound on the
growth of polynomial restriction rank. B\'ezout's theorem bounds
the degrees and point counts of the intervening components.
The comparison uses labels \((p,\pi_p(q))\), which record both the
center and the direction of an ordered pair. At each fixed center,
sparse-cone coverage puts the directions on curves of small total
degree, limiting their polynomial rank. The profiles give an incompatible rank lower bound
for a positive fraction of pairs. A complication is that radial
projection can identify several components, or several points on
one component. Section~\ref{geo:section} controls this behavior by
secant geometry. For separated windows, Subsection~\ref{dep:section}
bounds the resulting loss of degree at the actual centers.
Two limiting cases leave no strict margin in the general rank
comparison. At the outermost degree window, common equations with
independent differentials on most components allow a direct geometric
comparison of their projected images. At the last one-dimensional
stage for narrower center windows, the argument identifies the projection
of the assigned terminal curve with a curve in the covering family.
A global estimate has already removed all such incidences at a
cost of \(o(N^2)\) pairs (Proposition~\ref{geo:terminal}). These two
arguments in Section~\ref{sec:sparse-cones} supply the endpoint
control needed for an arbitrarily slow limit \(M/A\to0\).
\paragraph{3. Turn equal distances into intersections of flats.}
Take a generic rotated copy \(Q\) of \(P\) and transport the selected
pairs to \(Q\). For \((p,q)\in P\times Q\),
consider the affine flat
\[
F_{p,q}=\{(Z,c):Z(p+q)/2+c=(p-q)/2\},
\qquad Z^{\mathsf T}=-Z,\quad c\in\mathbb C^d.
\]
The coordinates \((Z,c)\) identify with skew forms on
\(\mathbb C^{d+1}\) by adjoining \(c\) as the last column and
\(-c^{\mathsf T}\) as the last row, with last diagonal entry zero.
Join \((p,q)\) to \((p',q')\)
when both physical pairs have been selected in Step 1 and
\(|p-p'|=|q-q'|\). Cauchy--Schwarz gives
\(\Omega(N^4/M)\) edges. On \(F_{p,q}\), the intersection with a
neighbor is the flat defined by
\[
Z(u+w)=u-w,\qquad u=p'-p,\quad w=q'-q.
\]
The interpolation property ensures that these local flats are
distinct and that their parameters have polynomial separators of
degree \(O(A)\): one parameter can be distinguished from all the
others by a polynomial of that degree.
Appendix~\ref{conc:section} proves concentration bounds for these
evaluation flats, both in the full skew-form space and inside one
fixed pair flat. In the local application an exceptional parameter
family corresponds to many matches under one rigid motion. For
\(d\ge4\), its required size bound follows from the total number of
points. For \(d=3\), Section~\ref{mot:section} bounds
\(\sum_g |gP\cap Q|^2\) over motions with at least \(CA\) matches
by \(O(N^4/A)\), with both orientations included. Removing the
corresponding edges costs \(o(N^4/M)\). After this removal and
pruning vertices of small degree, the minimum number of neighbors,
divided by \(A^{d-1}\), tends to infinity.
The local concentration bound says that
a nonzero polynomial of degree at most \(A\) on a pair flat can
vanish on at most \(O(A^{d-1})\) of its neighbor flats.
\paragraph{4. Sample once and compare polynomial ranks.}
The remaining contradiction is short. Sample the retained pair flats
independently with a small fixed probability. With positive probability,
the sample is small enough that the global concentration bound forces
the whole family to impose more independent polynomial conditions
in degree \(\lfloor A\rfloor\) than the sample. Simultaneously,
every retained flat has more than \(CA^{d-1}\) sampled neighbors.
Thus a polynomial of degree at most \(\lfloor A\rfloor\) vanishes on every sampled flat
but is nonzero on at least one retained flat \(F\).
The restriction of the polynomial to
\(F\) then violates local concentration. The sample uses one fixed
probability, and all concentration constants are uniform; this is
where the preceding quantitative estimates produce the positive
constant in Theorem~\ref{thm:main}.
\paragraph{Organization and prerequisites.}
Section~\ref{sec:reduction} carries out Steps 1, 3, and 4, assuming
the sparse-cones, concentration, and rich-motion theorems. It can
therefore be read first as the formal assembly of the argument.
Section~\ref{poly:section} proves the polynomial interpolation,
regularity, and multiplicity estimates. Sections~\ref{geo:section}
through~\ref{sec:sparse-cones} establish the geometric and multiscale
arguments of Step 2. Section~\ref{mot:section} proves the rich-motion
estimate, and Appendices~\ref{conc:section} and~\ref{ci:section}
provide the concentration and real incidence foundations.
Figure~\ref{fig:proof-map} summarizes the principal dependencies.
We use characteristic-zero algebraic geometry, including projective
degree and B\'ezout's theorem, generic linear sections, regular local
rings and Koszul resolutions, and projective-bundle intersection
formulas. The precise forms needed are specified where they are
used. Constants may depend on the fixed ambient dimension; any
additional dependence is indicated explicitly.
\begin{figure}[htbp]
\centering
\input{figures/proof-map}
\caption{Principal dependencies. Both endpoint arguments belong to the
sparse-cones theorem. The separated-window argument uses projection depth
at actual centers. Global concentration combines with the component
Hilbert bound; the rich-motion bound permits the \(d=3\) edge deletion
that supplies the local isotropic cap. The contradiction uses one sample with a
fixed inclusion probability. Appendix~\ref{ci:section} supplies the planar
induction base and the real incidence inputs to the geometric and motion
arguments.}
\label{fig:proof-map}
\end{figure}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/introduction.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/motions.tex ====
\section{Very rich rigid motions in three dimensions}
\label{mot:section}
In this section a rigid motion is an affine map
\(g(x)=Sx+h\), where \(S\in O(3)\); both orientations are included.
For finite clouds \(X,Y\subset\mathbb R^3\), put
\[
X_g=\{x\in X:g(x)\in Y\},
\qquad k_g(X,Y)=|X_g|.
\]
When \(X=Y=P\), write simply \(k_g\).
We shall prove the following finite statement. Its hypothesis holds
eventually along the contradiction sequences used in the main proof.
\begin{theorem}[Very rich motions]
\label{mot:rich}
There are absolute constants \(C_{\mathrm{rich}},K_{\mathrm{rich}}>0\)
with the following property. Let \(P\subset\mathbb R^3\) consist of
\(N\ge2\) distinct points, and set
\[
A=N^{2/3},\qquad M=1+|\Delta(P)|.
\]
If \(M\le A\), then the motions satisfying
\(k_g\ge C_{\mathrm{rich}}A\) form a finite set and
\begin{equation}
\label{mot:rich-sum}
\sum_{g:\,k_g\ge C_{\mathrm{rich}}A} k_g^2
\le K_{\mathrm{rich}}\frac{N^4}{A}.
\end{equation}
The same estimate holds with \(k_g=|gP\cap Q|\) for any rigidly
congruent copy \(Q\) of \(P\).
\end{theorem}
In particular, the constants in \eqref{mot:rich-sum} do not depend on
the rate at which \(M/A\) tends to zero. The finite hypothesis
\(M\le A\) will be used only through the elementary line cap
\begin{equation}
\label{mot:physical-line-cap}
|P\cap L|\le 2M\le2A
\qquad\text{for every affine line }L.
\end{equation}
Indeed, after fixing a point of \(P\cap L\), each nonzero distance
from it occurs at most twice on \(L\). Thus the sharper bound
\(1+2(M-1)\) also holds.
We shall prove the same assertion for two clouds \(X,Y\) of at most
\(N\) points, with \(A=N^{2/3}\), whenever every line contains at most
\(2A\) points of either cloud: the motions with
\(k_g(X,Y)\ge C_{\mathrm{rich}}A\) form a finite set, and their squared
match counts satisfy \eqref{mot:rich-sum} with \(k_g(X,Y)\) in place of
\(k_g\). Both orientations remain included. The line cap above
supplies this hypothesis for \(P\) and every congruent copy. We will
divide the clouds into small regions so that each motion has matches in
a controlled number of region pairs. Within each pair, a local estimate
handles motions whose matches are not concentrated on a line; we count
the remaining local contributions through lines in the full clouds and
their possible images.
The passage from equal-distance configurations to rigid motions is the
Elekes--Sharir framework~\cite{elekessharir2011}, used by Guth and
Katz in the planar problem~\cite{guthkatz2015}. The physical and
opposite-orientation flat families below are the rigid-motion geometry
developed by Tidor, Yu, and Zakharov
\cite[Section~3]{tidoryuzakharov2026}. We give the construction and every
estimate needed here. The incidence inputs are the
Szemer\'edi--Trotter bound, Theorem~\ref{ci:st}, and the
higher-richness Guth--Katz bound, Theorem~\ref{ci:rich-lines}.
\subsection{Two elementary consequences of planar incidence bounds}
We use the following form of Beck's dichotomy~\cite{beck1983}, derived from
Szemer\'edi--Trotter, including for real projective direction sets.
\begin{lemma}[Many lines and many anchors]
\label{mot:beck}
There are absolute constants \(\delta_0,\gamma_0>0\) such that the
following holds. If a finite set of \(n\) distinct real points has
at most \(\delta_0 n\) points on any line, then it spans at least
\(\gamma_0 n^2\) distinct lines. Moreover at least
\(\gamma_0 n\) of its points each lie on at least
\(\gamma_0 n\) of these spanned lines.
The assertion holds in any fixed real affine space, and in a real
projective plane after choosing a generic affine chart.
\end{lemma}
\begin{proof}
A generic real planar projection preserves the distinct points and
all noncollinear triples of a finite affine configuration. It
therefore suffices to work in the plane. Theorem~\ref{ci:st} gives
\begin{equation}
\label{mot:st-rich}
\#\{L:|L\cap X|\ge u\}
\le C_0\left(\frac{n^2}{u^3}+\frac nu\right),
\qquad u\ge2.
\end{equation}
For a large fixed integer \(u_0\), sum over dyadic occupancies
\(u=2^j u_0\), up to the maximum occupancy \(\delta_0 n\).
The number of ordered pairs of distinct points on lines in these
buckets is at most
\[
C_1\sum_{u}
\left(\frac{n^2}{u}+nu\right)
\le C_2\left(\frac{n^2}{u_0}+\delta_0 n^2\right).
\]
Choose \(u_0\) large and then \(\delta_0\) small, both absolute,
so this is less than one half of all ordered pairs. A positive
fraction of the pairs consequently lie on lines containing fewer
than \(u_0\) points. Each such line accounts for fewer than
\(u_0^2\) ordered pairs, so there are at least \(c_0n^2\) spanned
lines for an absolute \(c_0>0\). The finitely many small values of
\(n\) cause no difficulty: when \(\delta_0n<2\), the hypothesis
is impossible for \(n\ge2\).
The sum, over the points, of the numbers of incident spanned lines
is at least \(2c_0n^2\), whereas each point is incident to at most
\(n-1\) such lines. It follows that at least \(c_0n\) points
are incident to at least \(c_0n\) spanned lines, after decreasing
\(c_0\) if necessary. Take \(\gamma_0\le c_0\).
A generic projective chart puts a finite projective configuration
in the affine plane without changing its incidences.
\end{proof}
We shall also need an effective notion of richness for planes.
For a finite cloud \(X\) and an occupied plane \(\Pi\), define
\[
e_X(\Pi)
=|X\cap\Pi|-\max_{L\subset\Pi}|X\cap L|.
\]
Only planes containing a noncollinear triple can have positive
effective size, so the planes counted in the next lemma form a
finite family.
The next lemma is motivated by the nondegenerate rich-plane bounds of
Elekes and T\'oth \cite{elekestoth2005}. Its effective-size formulation
in the high-richness range and the double-counting proof below are local;
we do not invoke their theorem verbatim.
\begin{lemma}[Planes of large effective size]
\label{mot:effective-planes}
There are absolute constants \(C_2,K_2>0\) such that, for a cloud
\(X\subset\mathbb R^3\) with \(|X|\le m\), \(m\ge1\), and
\(H\ge C_2m^{2/3}\),
\[
\#\{\Pi:e_X(\Pi)\ge H\}\le K_2\frac{m^2}{H^2}.
\]
\end{lemma}
\begin{proof}
We may assume \(H\le m\). First consider a plane for which a
richest line contains at least half of \(X\cap\Pi\).
That line contains at least \(H\) points, and there are at least
\(H\) points of \(X\cap\Pi\) off the line. By
\eqref{mot:st-rich}, applied after a generic projection, the
number of \(H\)-rich lines of \(X\) is
\[
O\left(\frac{m^2}{H^3}+\frac mH\right)=O(m/H).
\]
Here \(H\ge\sqrt m\), after increasing \(C_2\).
For any fixed line, distinct planes containing it have disjoint
sets of points off that line. There are therefore at most
\(m/H\) planes of the present kind through each such rich line.
This part contributes \(O(m^2/H^2)\).
For the remaining planes no line contains half their points.
Bucket their occupancies in \([K,2K)\), where
\(K=2^jH\), and let \(f\) denote the number in one bucket.
Any fixed spatial line belongs to at most \(2m/K\) of these
planes, since each such plane has at least \(K/2\) points off
the line and those off-line sets are disjoint.
For \(x\in X\), let \(r_x\) be the number of bucket planes
containing \(x\), and put \(I=\sum_xr_x\). Thus
\(Kf\le I<2Kf\). The sum \(J\), over ordered distinct pairs
of bucket planes, of their common sample-point counts satisfies
\begin{equation}
\label{mot:plane-pairs-lower}
J=\sum_xr_x(r_x-1)
\ge \frac{K^2f^2}{m}-2Kf.
\end{equation}
To bound \(J\) from above, fix one bucket plane \(\Pi\).
Separate its intersection lines with the other planes according
as their occupancy is less than \(C_3\sqrt K\) or at least
\(C_3\sqrt K\), where \(C_3\ge2\) is a fixed constant.
The first class contributes at most \(C_3\sqrt K\,f\).
Within \(\Pi\), the number \(a\) of distinct lines in the second
class obeys, again by \eqref{mot:st-rich},
\[
a\le C_4\left(C_3^{-3}+C_3^{-1}\right)\sqrt K
=O(\sqrt K).
\]
Their total summed occupancy is \(O(K)\). Indeed, if a point is
on \(s\ge1\) of these lines, then
\(s\le1+\binom{s}{2}\); and two distinct lines have at most one
common point. Hence the total occupancy is at most
\[
|X\cap\Pi|+\binom a2=O(K).
\]
Each such intersection line belongs to at most \(2m/K\) bucket
planes. Their contribution for the fixed \(\Pi\) is therefore
\(O(m)\). Summing over \(\Pi\) gives
\begin{equation}
\label{mot:plane-pairs-upper}
J\le C_5 f(m+\sqrt K\,f).
\end{equation}
For sufficiently large \(C_2\), the assumption
\(K\ge C_2m^{2/3}\) ensures
\(K^2/m\ge2C_5\sqrt K\). Combining
\eqref{mot:plane-pairs-lower} and
\eqref{mot:plane-pairs-upper}, and using \(K\le m\), now gives
\(f=O(m^2/K^2)\). The sum over dyadic \(K\ge H\) is geometric,
which proves the lemma.
\end{proof}
\subsection{A local bound for motions without a rich matched line}
Choose constants \(0<\eta_1\ll\eta_2\ll1\) as follows.
First choose \(\eta_2\) so small that
\(4\eta_2/\gamma_0\le\delta_0/2\), where
\(\delta_0,\gamma_0\) are from Lemma~\ref{mot:beck}.
Then choose
\[
0<\eta_1\le\min\{\eta_2/100,\delta_0/8\}.
\]
These constants remain fixed throughout the section.
For a bucket \(\ell\le k_g(X,Y)<2\ell\), call a motion
\emph{line type} if some line contains at least \(\eta_1\ell\)
points of \(X_g\). Among the other motions, call it
\emph{planar type} if some plane contains at least
\(\eta_2\ell\) points of \(X_g\), and \emph{general type}
otherwise.
\begin{lemma}[Local motion bound]
\label{mot:local}
There are absolute constants \(C_{\mathrm{loc}},K_{\mathrm{loc}}>0\)
such that, if \(m\ge1\), \(|X|,|Y|\le m\), and
\(\ell\ge C_{\mathrm{loc}}m^{2/3}\), the number of non-line-type
motions satisfying \(\ell\le k_g(X,Y)<2\ell\) is at most
\[
K_{\mathrm{loc}}\frac{m^3}{\ell^{3/2}}.
\]
Both orientation classes are counted.
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{mot:local}]
We first prove the general-type case by a polynomial argument.
Every non-line-type match set contains a noncollinear triple.
The images of an ordered noncollinear triple determine a spatial
isometry up to two choices, and determine it uniquely if its
orientation is specified. Thus all motion lists considered in
the proof of Lemma~\ref{mot:local} are finite.
Separate the two orientations. Composing the second cloud with a
fixed reflection when necessary reduces either list to reversing
motions \(g(x)=Sx+h\), with \(\det S=-1\). Next rotate the
second cloud generically, applying the same rotation to every
motion in the finite list. We may and do arrange that:
\begin{enumerate}
\item \(\ker(I+S)\) is a line for each counted motion;
\item projection perpendicular to that line preserves
noncollinearity for every noncollinear triple in its match set.
\end{enumerate}
To justify these simultaneous choices, for any one fixed \(S\),
left multiplication by a rotation ranges over the entire negative
component of \(O(3)\). Outside the proper locus \(S=-I\), its
\(-1\) eigenspace is a line with arbitrary generic direction.
For a fixed noncollinear triple, the projection fails precisely
when that line direction belongs to the two-dimensional direction
space of the triple's plane. This is a proper algebraic condition.
There are finitely many motions and triples, so a rotation avoiding
all these proper conditions exists. Counts, distances, and
line/plane occupancies are preserved by this change of coordinates.
\subsubsection{The two families of null three-flats}
Use coordinates \((w,c)\in\mathbb R^3\oplus\mathbb R^3\), with
\(Zx=w\times x\), and equip this six-space with the nondegenerate
quadratic form
\[
\mathfrak q(w,c)=w\cdot c.
\]
Its associated symmetric bilinear form is
\[
\mathcal B((w,c),(w',c'))=w\cdot c'+w'\cdot c.
\]
For a possible point pair \((x,y)\in X\times Y\), set
\(v=(x+y)/2\), \(b=(x-y)/2\), and define
\begin{equation}
\label{mot:pair-flat}
F_{x,y}=\{(w,c):b=w\times v+c\}.
\end{equation}
This is an affine three-flat. Its directions obey
\(\delta c=-\delta w\times v\), so
\(\mathfrak q(\delta w,\delta c)=0\). Its direction space is
therefore maximal totally null and equals its
\(\mathcal B\)-orthogonal space.
Fix one reversing motion, and choose positively oriented orthonormal
coordinates with its axis \(\ker(I+S)\) equal to
\(\mathbb R e_3\). The perpendicular block \(S_\perp\) belongs
to \(SO(2)\), and \(I+S_\perp\) is invertible. On the full graph
\(y=Sx+h\), there are constants \(v_0,\omega\in\mathbb R\) and
\(d=(d_1,d_2)\in\mathbb R^2\) such that
\begin{equation}
\label{mot:graph-cayley}
v_3=v_0,\qquad b_\perp=\omega Jv_\perp+d,
\qquad J(a_1,a_2)=(-a_2,a_1).
\end{equation}
Here \(v_0=h_3/2\), and
\((I-S_\perp)(I+S_\perp)^{-1}=\omega J\).
The map from the physical point \(x\) to
\((v_1,v_2,b_3)\) is an invertible real affine map: its linear
blocks are \((I+S_\perp)/2\) and \(1\).
Define the motion flat by
\begin{equation}
\label{mot:motion-flat}
G_g=\{(w,c):w_3=\omega,\
c_1+v_0w_2=d_1,\
c_2-v_0w_1=d_2\}.
\end{equation}
It is another affine three-flat. Its directions satisfy
\[
\delta w_3=0,\qquad
\delta c_1=-v_0\delta w_2,\qquad
\delta c_2=v_0\delta w_1,
\]
with \(\delta c_3\) free, so they too are maximal totally null.
If \(y=g(x)\), its intersection with the pair flat is the plane
\begin{equation}
\label{mot:dual-plane}
H_{g,x}=F_{x,g(x)}\cap G_g:
\quad \tau+\xi v_1+\eta v_2=b_3,
\qquad (\xi,\eta,\tau)=(-w_2,w_1,c_3).
\end{equation}
These are the usual graph-dual planes of the transformed physical
points \((v_1,v_2,b_3)\).
The orthonormal coordinates used to describe a particular \(G_g\)
are only a means of writing its equations: within the normalized
orientation class under consideration, every flat is regarded in the
same original parameter six-space. Simultaneous rotations
\((w,c)\mapsto(Rw,Rc)\) preserve \(\mathfrak q\), so the null
properties just checked hold there for the whole family.
We record the needed distinctness assertions explicitly.
First, different matched physical points give different planes
\(H_{g,x}\), since their transformed coordinates are distinct.
Second, in a fixed pair flat \(F_{x,y}\), whose free coordinates
are \(w\), the incident plane from a motion with unit axis \(a\)
has equation \(w\cdot a=\omega\). This affine plane determines
\((a,\omega)\) up to simultaneous sign. Since the quarter-turn
operator \(J_a:x\mapsto a\times x\) on \(a^\perp\) also changes sign
with \(a\), the operator \(\omega J_a\), and hence \(S\), is
determined. The match \(g(x)=y\) then fixes \(h\). Hence different
incident motions give distinct planes in \(F_{x,y}\).
Finally, the whole affine flat \(G_g\) determines \(g\). Its
direction space intersects the pure-translation subspace
\(\{\delta w=0\}\) in precisely the axis line
\(\{\delta c\parallel a\}\), recovering that unoriented axis.
Choose either orientation of it. Projection of \(G_g\) to
\(w\)-space recovers \(\omega\); its direction coupling in
\eqref{mot:motion-flat} recovers \(v_0\); and the affine constants
then recover \(d\). Equation~\eqref{mot:graph-cayley} gives
\[
S_\perp=(I-\omega J)(I+\omega J)^{-1},\qquad
h_\perp=-(I+S_\perp)d,\qquad h_3=2v_0,
\]
and \(Sa=-a\). These reconstruct the physical motion, independently
of the arbitrary oriented coordinates used in the reconstruction.
Thus the \(G_g\) are distinct as well.
\subsubsection{Polynomial construction and descent}
Suppose that one orientation class contains at least
\[
T=\left\lceil K_3\frac{m^3}{\ell^{3/2}}\right\rceil
\]
general-type motions, where the absolute constant \(K_3\) will be
chosen large. Restrict to exactly \(T\) of them. Form the
bipartite incidence graph between these motions and their point-pair
labels. It has at least \(T\ell\) edges and at most \(m^2\)
label vertices. Repeatedly remove a motion vertex of degree below
\(\ell/4\), or a label vertex of degree below
\(T\ell/(4m^2)\). The total number of edges removed in the first
way is less than \(T\ell/4\), and in the second way less than
\(T\ell/4\). A nonempty graph remains, in which the two minimum
degree bounds hold. Every retained motion has between \(\ell/4\)
and \(2\ell\) retained matches. Its retained physical cloud still
has fewer than \(\eta_1\ell\) points on any line and fewer than
\(\eta_2\ell\) on any plane.
An ambient polynomial of degree at most \(D\) has
\(\binom{D+6}{6}\) coefficients. Vanishing on any one affine
three-flat imposes at most \(\binom{D+3}{3}\) linear conditions.
Thus a sufficiently large absolute multiple of \(T^{1/3}\),
rounded upward, is a degree \(D\) for which there is a nonzero
polynomial \(f\) vanishing on all retained \(G_g\). We may take
\begin{equation}
\label{mot:degree-bound}
D\le C_6K_3^{1/3}\frac{m}{\sqrt\ell}.
\end{equation}
We used \(\ell\le m\) here; if this fails the motion bucket is
empty. Choose \(K_3\) sufficiently large that
\[
\frac{T\ell}{4m^2}>D.
\]
Every retained pair flat then contains more than \(D\) distinct
incident planes on which \(f\) vanishes. A nonzero polynomial of
degree at most \(D\) on an affine three-space cannot vanish on
more than \(D\) distinct planes: their distinct affine linear
equations would all be factors. Therefore \(f\) vanishes on every
retained pair flat as well.
We next show that every first partial derivative of \(f\) vanishes
on every retained motion flat. For a polynomial \(h\), define its
raised gradient by
\[
dh_z(u)=\mathcal B(\nabla_{\mathcal B}h(z),u).
\]
If \(h\) vanishes on a maximal null affine flat, its raised
gradient at a point of that flat belongs to its direction space,
because that space equals its orthogonal. At an intersection of
three transverse planes \(H_{g,x_i}\) in \(G_g\), the raised
gradient of \(f\) therefore belongs to the directions of
\(G_g\) and of all three incident pair flats. Its direction in
\(G_g\) belongs to all three plane directions, whose intersection
is zero. Hence \(df=0\) there, so all ordinary first partial
derivatives vanish at that point.
There are enough such points to force a derivative to vanish on the
whole of \(G_g\). Work in its transformed physical cloud of
\(n_g\in[\ell/4,2\ell)\) retained points. Affine invertibility
preserves all line and plane occupancy bounds. Since
\(\eta_1\ell\le\delta_0 n_g\), Lemma~\ref{mot:beck} gives at
least \(\gamma_0\ell/4\) anchor points, each with at least
\(\gamma_0\ell/4\) distinct outgoing projective directions.
For a fixed such anchor, a projective line of directions corresponds
to a physical plane through the anchor and contains at most
\(\eta_2\ell\) of these distinct directions. The choice of
\(\eta_2\) permits a second application of Lemma~\ref{mot:beck}.
It gives at least \(c_7\ell^2\) distinct physical planes through
the anchor and two other noncollinear points, for an absolute
\(c_7>0\).
All these spanned planes are nonvertical in the coordinates
\((v_1,v_2,b_3)\), by the generic projection chosen above. Each
is the graph of a unique affine function of \((v_1,v_2)\).
Graph duality in \eqref{mot:dual-plane} therefore converts them
into \(c_7\ell^2\) distinct transverse triple-intersection points
in the anchor plane \(H_{g,x}\). They lie on the arrangement of
at most \(2\ell\) distinct lines obtained by intersecting this
anchor plane with the other incident planes. A line in this
arrangement contains at most \(2\ell\) distinct intersection
points with the other lines. Since each of the designated points
lies on at least two arrangement lines, counting these incidences
shows that at least \(c_8\ell\) distinct lines each contain at
least \(c_8\ell\) designated points, for an absolute \(c_8>0\).
Choose a fixed \(\varepsilon>0\) smaller than both
\(c_8/2\) and \(\gamma_0/8\). After \(K_3\) has been fixed,
increase \(C_{\mathrm{loc}}\) so that
\(\ell\ge C_{\mathrm{loc}}m^{2/3}\) and
\eqref{mot:degree-bound} imply \(D<\varepsilon\ell\).
Each first derivative of \(f\), whose degree is less than \(D\),
now vanishes on all the rich lines just found: its univariate
restriction has more zeros than its degree. It consequently
vanishes on the entire anchor plane, by the same distinct-factor
argument in dimension two. There are at least
\(\gamma_0\ell/4>D\) distinct anchor planes, so the derivative
vanishes on \(G_g\).
Every first derivative therefore vanishes on all retained motion
flats, and the earlier propagation through the retained label
degrees makes it vanish on all retained pair flats. The same
argument applies to it, with strictly smaller degree and the same
geometric configuration. Iteration implies that a nonzero constant
derivative of \(f\) vanishes on a nonempty flat, a contradiction
in characteristic zero. This proves the general-type bound
\(O(m^3/\ell^{3/2})\) for each orientation class.
\subsubsection{Planar type}
For two finite planar clouds of sizes \(a,a'\),
Corollary~\ref{ci:planar-motions} bounds the number of planar
isometries giving at least \(u\) matches, for an integer \(u\ge3\), by
\begin{equation}
\label{mot:planar-placements}
O\left(\frac{(aa')^{3/2}}{u^2}\right)
\qquad (u\le\min\{a,a'\}).
\end{equation}
The corollary counts both orientations. Its proof uses the
higher-richness Guth--Katz line theorem
\cite[Theorem~4.5]{guthkatz2015} with a plane cap; that theorem has no
regulus hypothesis.
Now take a planar-type motion in the local bucket. Choose a plane
\(\Pi\) with at least \(\eta_2\ell\) matched source points and
put \(\Pi'=g\Pi\). Remove a richest ambient line from
\(X\cap\Pi\), and a richest ambient line from \(Y\cap\Pi'\).
Each deletion loses fewer than \(\eta_1\ell\) matches, by the
non-line-type assumption. At least
\[
(\eta_2-2\eta_1)\ell\ge\eta_0\ell,
\qquad \eta_0=\eta_2/2,
\]
matches remain. In particular
\(e_X(\Pi),e_Y(\Pi')\ge\eta_0\ell\).
Bucket these two effective sizes in \([h,2h)\) and \([h',2h')\),
where \(h,h'\) run dyadically from \(\eta_0\ell\).
Choose \(C_{\mathrm{loc}}\) also large enough that
\(\eta_0\ell\ge C_2m^{2/3}\) and \(\eta_0\ell\ge3\).
Lemma~\ref{mot:effective-planes} supplies at most
\(O(m^4/(h^2(h')^2))\) ordered supporting plane pairs in these
buckets. For each fixed pair, choose the two richest lines once
and for all, and choose orthonormal affine coordinates on the two
planes. Write \(a,a'\) for the sizes of the reduced planar clouds,
so \(a<2h\) and \(a'<2h'\). A motion being counted restricts to a
planar isometry with at least
\(k_0=\lceil\eta_0\ell\rceil\ge3\) matches. If
\(k_0>\min\{a,a'\}\), there are no such restrictions; otherwise
\eqref{mot:planar-placements}, applied with \(u=k_0\), bounds them by
\(O((hh')^{3/2}/\ell^2)\). Each planar restriction extends to a
spatial isometry in at most two ways, according to the image of the
unit normal. The constants therefore remain absolute.
Multiplying and summing the two geometric dyadic series gives
\[
\#\{\text{planar-type motions}\}
\le C\frac{m^4}{\ell^2}
\sum_{h,h'\ge\eta_0\ell}(hh')^{-1/2}
\le C'\frac{m^4}{\ell^3}
\le C''\frac{m^3}{\ell^{3/2}}.
\]
The last inequality uses \(\ell\ge C_{\mathrm{loc}}m^{2/3}\).
Together with the general-type proof, this completes
Lemma~\ref{mot:local}, taking \(K_{\mathrm{loc}}\) larger than
the sum of the constants obtained for the two orientations and
the planar-type estimate. The order of choices was
\(\eta_2\), \(\eta_1\), then \(K_3\), then
\(C_{\mathrm{loc}}\), and finally \(K_{\mathrm{loc}}\).
\end{proof}
\subsection{A spatial subdivision with uniform overlap}
We now prepare to apply Lemma~\ref{mot:local} to subsets of the full
clouds. For \(r,m\ge1\), suppose temporarily that each cloud has been
divided into disjoint regions containing at most \(m\) of its points, and that at
most \(Kr\) pairs of regions can contain matches of any fixed motion,
where \(K>0\) is an absolute constant. If \(n_{R,R'}(g)\) is the
number of matches from points of \(X\) in region \(R\) to points of
\(Y\) in region \(R'\), these counts sum to \(k_g(X,Y)\), and at most
\(Kr\) are nonzero. Hence
\begin{equation}
\label{mot:region-discard}
\sum_{\substack{R,R'\\ n_{R,R'}(g)0).
\end{equation}
Thus, for a motion with at least \(k>0\) matches, taking \(b\) to be a
sufficiently small fixed multiple of \(k/r\) retains a fixed fraction
of its matches in region pairs with local count at least \(b\).
Divide the retained local counts into buckets
\(\ell\le n_{R,R'}(g)<2\ell\) with \(\ell\ge b\). If the later
parameter choice makes
\(b\ge C_{\mathrm{loc}}m^{2/3}\), the non-line-type bound of
Lemma~\ref{mot:local} applies in every such bucket. A motion of line
type in one local bucket instead supplies a source line and its image
line, each containing at least \(\eta_1\ell\ge\eta_1b\) points of its
full cloud. We will count these local contributions through their
physical lines.
For each fixed \(r\) with \(1\le r\le N\), the next lemma constructs
the required subdivision once on each cloud, independently of the motion,
with \(O(r)\) regions and \(m=8N/r\).
Its geometric property controls intersections of the regions themselves
under every rigid motion, and hence the number of region pairs that can
contain matches.
\begin{lemma}[Subdivision into cubes and cubes with one hole]
\label{mot:partition}
Let \(N\ge1\) and \(1\le r\le N\), with \(r\) allowed to be
real. For every cloud \(X\subset\mathbb R^3\) of size at most
\(N\), there is a half-open cube containing \(X\) and a finite
partition \(\mathcal R_X\) of that cube such that:
\begin{enumerate}
\item every region is a half-open dyadic cube, or the difference
\(Q\setminus Q'\) of a half-open dyadic cube and one strict
dyadic descendant;
\item \(|\mathcal R_X|\le19r\), and every region contains at most
\(8N/r\) points of \(X\);
\item there is an absolute constant \(K_{\mathrm{part}}\) such
that, for any two partitions obtained this way and every rigid
motion \(g\),
\[
\#\{(R,R')\in\mathcal R_X\times\mathcal R_Y:
g(R)\cap R'\ne\varnothing\}
\le K_{\mathrm{part}}r.
\]
\end{enumerate}
In particular the matches of any motion occur in at most
\(K_{\mathrm{part}}r\) pairs of regions.
\end{lemma}
\begin{proof}
Put \(\mu=N/r\ge1\). Choose a containing half-open cube and
subdivide a dyadic cube whenever it contains more than \(\mu\)
sample points. Call these subdivided cubes heavy. The procedure
terminates: distinct points in a finite cloud have positive minimum
separation, so sufficiently small cubes contain at most one point.
If the root cube is light, it alone is the required partition.
Otherwise the heavy cubes form a finite rooted tree, with edges to
heavy children. Let \(L\) be the number of its leaves and \(B\)
the number of its vertices with at least two heavy children.
The heavy leaves are disjoint and each contains more than \(\mu\)
points, so \(Ls/4\), and
lies within distance \(\sqrt3\,s\) of \(x\). Use this child
as \(E\). This proves \eqref{mot:thickness}, including at all
included half-open boundary points. The statement is unchanged
by a rigid motion.
Consider the two disjoint region families
\(g(\mathcal R_X)\) and \(\mathcal R_Y\). Charge each
intersecting pair to the member with smaller outer side, breaking
ties by a fixed preference between the families. Fix a charged
region \(R\) with outer side \(s\), and let \(c_R\) be the
center of its outer cube. For each partner \(R'\), choose
\(x_{R'}\in R\cap R'\). The outer side of \(R'\) is at least
\(s\), so \eqref{mot:thickness} gives a set
\[
E_{R'}\subset R'\cap B(x_{R'},\sqrt3\,s),\qquad
\operatorname{vol}(E_{R'})\ge(s/4)^3.
\]
All these sets lie in \(B(c_R,3\sqrt3\,s/2)\). They are
pairwise disjoint because the partners belong to one partition.
Comparing their volumes with that ball bounds their number by an
absolute constant. Summing the charges over at most \(38r\)
regions proves the intersection estimate. A matched point lies in
a unique region of each partition, so the assertion about matches
follows as well.
\end{proof}
\input{figures/motion-partition}
\FloatBarrier
\subsection{Counting prescribed images of rich lines}
We give the two elementary geometric facts needed for the line-type
contributions. In the first lemma a line-match weight is the full
number of source points on the specified line mapped to target
points on its specified image line.
\begin{lemma}[Two prescribed line images]
\label{mot:line-images}
Let \((L_1,L_2)\) and \((L'_1,L'_2)\) be ordered pairs of distinct
affine lines in \(\mathbb R^3\).
\begin{enumerate}
\item If the source lines are nonparallel, at most eight rigid
motions map \(L_i\) onto \(L'_i\) for \(i=1,2\).
\item If the source lines are parallel, the target lines must be
parallel at the same positive separation. There are at most four
possible orthogonal linear parts, and for each one the admissible
translations form one affine line parallel to the target lines.
If all four lines contain at most \(H\) points of their respective
clouds, then
\begin{equation}
\label{mot:parallel-weight}
\sum_g w_1(g)w_2(g)\le4H^3,
\end{equation}
where only motions with positive product are included. That set
of motions is finite.
\end{enumerate}
Both conclusions allow both orientation classes.
\end{lemma}
\begin{proof}
For nonparallel lines choose unit directions \(a_1,a_2\) and
\(b_1,b_2\). The orthogonal part \(S\) of a motion must satisfy
\(Sa_i=\varepsilon_i b_i\), with
\(\varepsilon_i\in\{1,-1\}\). There are at most four sign
choices. Each compatible choice determines the isometry on the
two-dimensional span of \(a_1,a_2\), and there are at most two
choices on its perpendicular line. For each resulting \(S\),
the condition on its translation \(h\) imposed by each line is
an affine line in translation space with direction \(b_i\).
Those two affine lines are nonparallel, so their intersection
has at most one point. This proves the bound of eight, whether
the original lines intersect or are skew.
For parallel lines choose unit directions \(a,b\). Let \(d\)
be the nonzero perpendicular separation vector from \(L_1\) to
\(L_2\), and let \(e\) be the analogous vector for the ordered
target pair. Orthogonality forces
\[
Sa=\pm b,\qquad Sd=e.
\]
These equations determine \(S\) on a two-dimensional space,
with at most two choices on its perpendicular line. There are
therefore at most four orthogonal parts in total. For any fixed
one, mapping the first source line onto the first target line
fixes the translation modulo a scalar multiple of \(b\); the
second-line condition is then either impossible or automatically
satisfied. This proves the geometric assertion.
Parametrize one such translation family by a real number \(\tau\).
Each pair of a source sample point on \(L_1\) and a target sample
point on \(L'_1\) determines a unique \(\tau\). Thus
\[
\sum_\tau w_1(\tau)
\le |X\cap L_1|\,|Y\cap L'_1|\le H^2,
\qquad w_2(\tau)\le H.
\]
Only finitely many \(\tau\) have positive first weight. The
product sum for this linear part is at most \(H^3\); summing over
at most four parts proves \eqref{mot:parallel-weight}. This
argument sums the actual translations and introduces no
discretization of the continuous family.
\end{proof}
\begin{lemma}[Parallel pairs at a fixed separation]
\label{mot:parallel-pairs}
Let \(\mathcal L\) be a finite family of at most \(L\) distinct
lines in \(\mathbb R^3\). For each \(\rho>0\), the number of
ordered parallel pairs in \(\mathcal L\) at separation \(\rho\)
is \(O(L^{3/2})\), with an absolute implicit constant.
\end{lemma}
\begin{proof}
In one parallelism class of size \(q\), intersect the lines with
the plane through the origin perpendicular to their common
direction. Their intersection points are distinct, and line
separation equals the Euclidean distance of these points.
Form the graph whose edges join points at distance \(\rho\).
Two different vertices have at most two common neighbors, because
two distinct circles of radius \(\rho\) have at most two common
points. If the graph has \(e\) edges and degrees \(d_z\), then
\[
\sum_z\binom{d_z}{2}\le2\binom q2,
\qquad
(2e)^2\le q\sum_zd_z^2\le3q^3.
\]
In the last inequality we used the preceding bound and
\(2e\le q(q-1)\). Hence there are \(O(q^{3/2})\) ordered
pairs in this class. Sum over the classes, using
\(\sum_jq_j^{3/2}\le(\sum_jq_j)^{3/2}\le L^{3/2}\).
\end{proof}
\subsection{Proof of the very-rich-motion estimate}
\begin{proof}[Proof of Theorem~\ref{mot:rich}]
We prove the stronger assertion stated at the start of the section.
Let \(X,Y\) be
clouds of at most \(N\) points, put \(A=N^{2/3}\), and suppose
that each line contains at most \(2A\) points of either cloud.
Write \(k_g=k_g(X,Y)\) throughout this proof. We prove
\eqref{mot:rich-sum} with this notation. This implies
the asserted result by \eqref{mot:physical-line-cap}. Alternatively,
the claim for a congruent copy follows by composing the motions
with the inverse of the congruence, which preserves their match
counts and bijects the two orientation classes as appropriate.
Fix the absolute constants
\[
\alpha=\frac1{14},\qquad
\beta=\frac1{4K_{\mathrm{part}}},\qquad
\nu=\frac{\eta_1}{4}.
\]
Choose \(C_{\mathrm{rich}}\) sufficiently large that
\begin{equation}
\label{mot:constant-choices}
C_{\mathrm{rich}}>4,\qquad
\frac\beta4 C_{\mathrm{rich}}^{9/14}
\ge C_{\mathrm{loc}},\qquad
\eta_1\beta C_{\mathrm{rich}}^{3/7}\ge1,\qquad
\nu C_{\mathrm{rich}}\ge4.
\end{equation}
All constants on the right have already been fixed. These choices
are independent of \(N\) and of the clouds.
Every motion with at least \(C_{\mathrm{rich}}A\) matches has a
noncollinear matched triple, because the line cap is \(2A\).
The finite choice of source and target ordered triples and the
at-most-two extensions per triple prove finiteness of the motion
set in the sum. In particular, possible continuous families of
motions fixing a line are below the threshold unless they have
additional noncollinear matches, in which case this same finite
triple argument applies.
Bucket the high motions by
\[
k\le k_g(X,Y)<2k,\qquad
k=tA,\qquad t=2^jC_{\mathrm{rich}}\le N^{1/3}.
\]
If no such \(t\) exists, the sum is empty. In a nonempty bucket
set
\begin{equation}
\label{mot:subdivision-parameters}
r=t^{1+\alpha},\qquad
m=8N/r,\qquad
b=\beta k/r=\beta A t^{-\alpha}.
\end{equation}
Since \(t\le N^{1/3}\) and \(\alpha<2\), we have
\(1\le r\le N\), so Lemma~\ref{mot:partition} applies to both
clouds. It supplies at most \(19r\) regions in each partition,
each with at most \(m\) points.
For the partitions just chosen, put \(X_R=X\cap R\) and
\(Y_{R'}=Y\cap R'\). The local count is
\(n_{R,R'}(g)=k_g(X_R,Y_{R'})\). These counts sum to \(k_g\),
and at most \(K_{\mathrm{part}}r\) are nonzero. By
\eqref{mot:region-discard}, discarding those below \(b\) removes
at most \(K_{\mathrm{part}}rb=k/4\) matches. At least \(3k/4\)
matches remain.
Bucket each remaining local count into
\(\ell\le n_{R,R'}(g)<2\ell\), with \(\ell=2^i b\), and
use the line/planar/general classification of
Lemma~\ref{mot:local} for the clouds \(X_R,Y_{R'}\) in that local
bucket. A single global motion may contribute different local types
in different region pairs.
The local lower threshold is valid, since
\begin{equation}
\label{mot:local-scale-check}
\frac{b}{m^{2/3}}
=\frac\beta4\,t^{(2-\alpha)/3}
=\frac\beta4\,t^{9/14}
\ge C_{\mathrm{loc}}.
\end{equation}
We shall also need the full-cloud rich-line threshold
\(q=\eta_1b\) to be at least \(\sqrt N\). The inequality
\(t\le N^{1/3}\) gives \(N^{1/6}\ge t^{1/2}\), so
\begin{equation}
\label{mot:rich-line-scale}
\frac{q}{\sqrt N}
=\eta_1\beta N^{1/6}t^{-\alpha}
\ge\eta_1\beta t^{1/2-\alpha}
=\eta_1\beta t^{3/7}\ge1.
\end{equation}
In particular these rich lines contain at least two points in every
nonempty bucket. One may also record the power margin
\(b\ge\beta N^{9/14}\), although only
\eqref{mot:rich-line-scale} is needed below.
\paragraph{Motions with substantial non-line-type mass.}
Let \(\mathcal G_0\) consist of the motions in the global bucket
whose retained local non-line-type counts have total at least
\(k/4\). For a fixed region pair and a local richness bucket,
Lemma~\ref{mot:local} bounds the number of non-line-type motions
by \(K_{\mathrm{loc}}m^3/\ell^{3/2}\). Their local match mass
is therefore at most \(2K_{\mathrm{loc}}m^3/\sqrt\ell\).
Summing the geometric series over \(\ell=2^i b\) gives
\(O(m^3/\sqrt b)\) for each fixed region pair. The bound remains
valid after restriction to our global bucket. There are at most
\((19r)^2\) possible region pairs, whence
\begin{equation}
\label{mot:nonline-mass}
|\mathcal G_0|\,k^2
\le C k r^2\frac{m^3}{\sqrt b}
\le C' N^3\frac{k}{r\sqrt b}
=C''N^3\sqrt A\,t^{-\alpha/2}
=C''\frac{N^4}{A}\,t^{-1/28}.
\end{equation}
The equality \(N^3\sqrt A=N^4/A\) uses \(A=N^{2/3}\).
\paragraph{Motions whose retained mass is mostly line type.}
For every remaining motion, at least \(k/2\) retained matches
belong to line-type local buckets. In each such region pair,
choose one source line containing at least \(\eta_1\ell\) of
its local matches, and retain those matches as assigned line
matches. Since \(n_{R,R'}(g)<2\ell\), this retains at least
\(\eta_1/2\) of that local count. Thus the assigned line-match
mass \(W_g\) satisfies
\[
W_g\ge\nu k,\qquad \nu=\eta_1/4.
\]
A physical source point participates in at most one region-pair
count for a fixed motion. Hence no assigned match is repeated.
Pool assignments belonging to the same full source line \(L\),
and write its weight as \(w_{g,L}\). Its target line is necessarily
\(gL\), and
\begin{equation}
\label{mot:pooled-line-weights}
\sum_Lw_{g,L}=W_g\ge\nu k,
\qquad 0\le w_{g,L}\le2A.
\end{equation}
Every line appearing on either side contains at least
\(\eta_1b=q\) ambient sample points, because it was chosen in a
local bucket with \(\ell\ge b\).
Let \(\mathcal L_X,\mathcal L_Y\) be the full lists of these
\(q\)-rich lines of the two clouds. These are finite lists of
spanned lines. Equations~\eqref{mot:st-rich} and
\eqref{mot:rich-line-scale} imply
\begin{equation}
\label{mot:rich-line-number}
|\mathcal L_X|,|\mathcal L_Y|
\le C\left(\frac{N^2}{q^3}+\frac Nq\right)
\le C'\frac Nb.
\end{equation}
Denote a common upper bound in \eqref{mot:rich-line-number} by
\(L_*=C'N/b\).
The diagonal weights can be removed without losing a fixed
fraction. Indeed, by \eqref{mot:constant-choices} and
\eqref{mot:pooled-line-weights},
\(W_g\ge\nu k\ge4A\). Consequently
\begin{equation}
\label{mot:distinct-line-pair-mass}
\sum_{L_1\ne L_2}w_{g,L_1}w_{g,L_2}
=W_g^2-\sum_Lw_{g,L}^2
\ge W_g^2-2AW_g
\ge\tfrac12\nu^2 k^2.
\end{equation}
Sum this quantity over the remaining motions. For nonparallel
source line pairs, there are at most \(L_*^4\) prescriptions of
an ordered source pair and its ordered target pair. By
Lemma~\ref{mot:line-images}, each prescription has at most eight
motions, and each product of weights is at most \((2A)^2\).
Their total contribution is thus \(O(A^2L_*^4)\).
For a parallel ordered source pair, fix its positive separation
\(\rho\). Lemma~\ref{mot:parallel-pairs} gives at most
\(O(L_*^{3/2})\) ordered target pairs at that separation, including
all target parallelism classes. There are at most \(L_*^2\)
source pairs. For every prescription, the pooled selected weights
are bounded by the full line-match weights in
Lemma~\ref{mot:line-images}; with \(H=2A\), its bound is
\(O(A^3)\). Therefore the total parallel contribution is
\(O(A^3L_*^{7/2})\).
If \(\mathcal G_1\) denotes the remaining motions, the two cases
and \eqref{mot:distinct-line-pair-mass} give
\begin{equation}
\label{mot:line-mass}
|\mathcal G_1|\,k^2
\le C\left(A^2(N/b)^4+A^3(N/b)^{7/2}\right).
\end{equation}
This counts both orientations. In the parallel case it sums the
whole continuous translation family through its finite positive
match support, rather than assuming a bounded number of motions
for the two prescribed lines.
\paragraph{Summing the global buckets.}
From \(b=\beta A t^{-\alpha}\), with its fixed positive
\(\beta\), the two terms in \eqref{mot:line-mass} are
\begin{align}
\label{mot:nonparallel-exponent}
A^2(N/b)^4&=O\left(N^{8/3}t^{4\alpha}\right)
=O\left(N^{8/3}t^{2/7}\right),\\
\label{mot:parallel-exponent}
A^3(N/b)^{7/2}&=O\left(N^{19/6}t^{7\alpha/2}\right)
=O\left(N^{19/6}t^{1/4}\right).
\end{align}
Summing these increasing geometric series up to
\(t\le N^{1/3}\) gives respectively
\[
O\left(N^{58/21}\right)
\quad\text{and}\quad
O\left(N^{13/4}\right).
\]
Both are bounded by \(O(N^{10/3})=O(N^4/A)\); in fact they save
the powers \(N^{-4/7}\) and \(N^{-1/12}\), respectively.
The decreasing geometric series in
\eqref{mot:nonline-mass} gives
\[
\sum_{j\ge0}
O\left(\frac{N^4}{A}
(2^jC_{\mathrm{rich}})^{-1/28}\right)
=O(N^4/A).
\]
Finally \(k_g<2k\) in each global bucket, so replacing its
cardinality times \(k^2\) by the sum of the actual \(k_g^2\)
costs at most a factor of four. The two types exhaust every
bucket, proving \eqref{mot:rich-sum}.
\end{proof}
\begin{remark}[Scope of the threshold and the deletion cost]
\label{mot:scope}
The finite line cap is essential for the sum over motions to make
sense. For a collinear sample without such a high threshold,
infinitely many rotations about its containing line fix every
point. In Theorem~\ref{mot:rich} each counted motion has a
noncollinear matched triple, which removes this issue.
For the reduction in this paper, \(M=o(A)\) guarantees the finite
hypothesis \(M\le A\) eventually. Deleting every existing graph
edge whose endpoints are matches of the same motion above the threshold
costs at most \(\sum_g\binom{k_g}{2}=O(N^4/A)\). Counting an edge for
several motions can only increase this upper bound. In the proof of
Lemma~\ref{red:local-concentration}, the real Gram-matrix calculation
uses this deletion to bound the parameters in every local maximal
isotropic plane.
\end{remark}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/motions.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/polynomial.tex ====
\section{Polynomial interpolation, regularity, and multiplicity}
\label{poly:section}
We record the algebraic facts used below, with their degree dependence. The
ambient dimension in this section is denoted by $n$ and is fixed. Constants
written $C_n$ depend only on $n$; they may be increased between statements.
Varieties are reduced unless a local quotient or an intersection scheme is
explicitly specified. The degree of an affine variety is the degree of its
projective closure. For a family of distinct irreducible components of one
dimension, its degree is the sum of their degrees. Components are counted
only once, even if they occur in more than one defining system.
The section supplies interpolation from defining equations, restriction-rank
bounds from component degrees, common equations with controlled exceptional
degree, and tests for high multiplicity and projection loss. We first
prove isolated-point interpolation. Applying it on generic fibers will
then give the rank and regularity estimates.
For a subset $T\subset\C^n$, put
\[
H_T(D)=\dim_{\C}\bigl(\C[x_1,\ldots,x_n]_{\le D}/
I(T)_{\le D}\bigr),\qquad D\in\mathbb Z_{\ge0}.
\]
Here $I(T)$ consists of the polynomials vanishing on $T$. The degree-$D$
envelope is
\[
\Env_D(T)=\{x:f(x)=0\text{ for every }f\in I(T)_{\le D}\}.
\]
Its defining collection can be replaced by a finite basis of
$I(T)_{\le D}$. Directly from the definition,
\begin{equation}\label{poly:envelope-equality}
H_{\Env_D(T)}(D)=H_T(D).
\end{equation}
For a projective set we use restrictions of homogeneous polynomials of
exact degree $D$. Dehomogenizing in any affine chart meeting every
component gives the same rank: homogenization identifies polynomials of
degree at most $D$ with homogeneous polynomials of degree $D$, and a
polynomial vanishes on a component if and only if it vanishes on a dense
affine part of that component. We always choose charts generically for
the finitely many points and components under discussion.
We use the following forms of the elementary intersection facts. A
proper hypersurface section of a pure $k$-dimensional variety of degree
$a$, by a polynomial of degree $q$, has reduced support of pure dimension
$k-1$ and degree at most $aq$; the section may be empty in an affine
chart. Successive proper sections obey the corresponding product bound.
More generally, the degrees, with local intersection multiplicities, of
isolated components of an intersection are at most the B\'ezout product,
even if the same equations have larger components elsewhere. One obtains
this latter form by taking generic linear combinations locally at the
isolated components, perturbing to proper intersections, and specializing:
the isolated intersection multiplicities are positive and persist in the
specialization, whereas intersections on other components can only add
to the total. We will never replace an isolated component by a
subvariety lying inside a larger component.
These intersection bounds are the componentwise refined B\'ezout
inequality \cite[Theorem~12.3 and Example~12.3.1]{fulton1998}.
For isolated complete intersections of hypersurfaces in a regular
ambient space, intersection multiplicity equals local quotient length.
The hypersurface factors are Cohen--Macaulay, as required in
\cite[Example~12.3.7(ii)--(iii)]{fulton1998}.
\subsection{Separators supplied by the distance set}
\begin{lemma}[Physical separators and sample bounds]\label{poly:separators}
Let $P\subset\R^n$ be finite and let $M=1+|\Delta(P)|$. Each $p\in P$
has a polynomial $s_p$ of degree at most $2(M-1)$ such that
\[
s_p(p)=1,\qquad s_p(q)=0\quad(q\in P\setminus\{p\}).
\]
If $V\subset\C^n$ is a pure $u$-dimensional variety of degree $a$, then
\begin{equation}\label{poly:physical-count}
|P\cap V|\le C_n aM^u.
\end{equation}
Moreover, $P$ is precisely the common zero set of a system of polynomials
of degree at most $2M+1$. In particular, all its points are isolated
components of that system.
\end{lemma}
\begin{proof}
For $p\in P$ define
\[
s_p(x)=\prod_{\rho\in\Delta(P)}
\frac{\sum_{j=1}^n(x_j-p_j)^2-\rho^2}{-\rho^2}.
\]
Every denominator is nonzero. The stated values on the real sample
follow even though we subsequently regard $s_p$ as a polynomial over
$\C$.
We prove \eqref{poly:physical-count} by induction on $u$ and add over the
irreducible components of $V$. For $u=0$ the number of points is at most
$a$. Suppose $V$ is irreducible of positive dimension and contains a
sample point $p$. The polynomial $s_p$ does not vanish identically on
$V$, because it is nonzero at $p$, and it vanishes at every other sample
point of $V$. Its proper section has degree at most $2Ma$. The induction
hypothesis therefore gives
\[
|P\cap V|\le 1+C_n(2Ma)M^{u-1}.
\]
Increasing the dimension-dependent constant proves the claim. This
argument requires no smoothness or general-position assumption on the
sample points.
Finally use the polynomials
\begin{equation}\label{poly:exact-isolation}
1-\sum_{p\in P}s_p(x),\qquad
(x_j-p_j)s_p(x)\quad(p\in P,\ 1\le j\le n).
\end{equation}
They vanish at every point of $P$. At any common zero, the first equation
forces some $s_p$ to be nonzero, and the corresponding $n$ coordinate
equations then force $x=p$. Thus there are no additional zeros.
\end{proof}
\subsection{Interpolation at isolated points}
The next lemma concerns the isolated points of a system, not a system
whose entire zero set is necessarily finite. This distinction will be
needed for envelopes and for intermediate cuts.
\begin{lemma}[A determinant in a local parameter quotient]
\label{poly:socle}
Let $F$ be an algebraically closed field, let
$R=F[Z_1,\ldots,Z_c]_{(Z_1,\ldots,Z_c)}$, and suppose
$f_1,\ldots,f_c\in R$ generate an ideal of finite colength. If
\[
(f_1,\ldots,f_c)^{\mathsf t}
=Q(Z)(Z_1,\ldots,Z_c)^{\mathsf t},
\]
then the class of $\det Q$ in $R/(f_1,\ldots,f_c)$ is nonzero.
\end{lemma}
\begin{proof}
The coordinate parameters form a regular sequence. The regular local
ring $R$ is Cohen--Macaulay, so the $c$ elements $f_i$, being a system of
parameters, also form a regular sequence
\cite[Tags~00OQ, 00NQ, and 02JN]{stacksproject}. Their Koszul complexes
are therefore free resolutions of $R/(f)$ and $R/(Z)=F$, respectively
\cite[Tag~062F]{stacksproject}.
The matrix $Q$ induces a chain map from the first Koszul resolution to
the second, lifting the quotient map $R/(f)\longrightarrow F$; its map
in top degree is multiplication by $\det Q$.
For completeness, the vanishing needed to see that this top map is
nonzero is especially simple. The coordinate Koszul resolution gives
\[
\operatorname{Ext}^i_R(F,R)=0\quad(ia/2$ for every $p\in S$.
For any specified $x_*\notin X$, there is a polynomial of degree
at most $2(n+1)$ which vanishes on $S$ and is nonzero at $x_*$.
In particular the specified high-multiplicity centers lie in a
proper hypersurface of degree bounded in terms of the ambient
dimension alone.
\end{corollary}
\begin{proof}
For a zero-dimensional irreducible variety, $X$ is one reduced
point, and a linear polynomial suffices. In positive dimension
apply Lemma~\ref{poly:projection}(ii) to the projective closure,
the finite set $S$, and $x_*$. Compose a homogeneous defining
equation of the image with the linear forms of the projection and
dehomogenize in the original affine chart. The resulting polynomial
has degree at most $a$ and is nonzero at $x_*$. Choose the target
chart to contain the finitely many specified images. Its
dehomogenization differs locally from this polynomial by a unit,
so its order at every $p\in S$ is at least $\mult_pX$: composition
does not decrease order, and hypersurface multiplicity equals the
order of its equation. Apply Lemma~\ref{poly:compression} with
$r=\lfloor a/2\rfloor+1$.
\end{proof}
\begin{corollary}[A tangent hyperplane controls the projection loss]
\label{poly:tangent-projection}
Let an irreducible affine curve $C$ lie in a variety $X$ smooth at
$p\in C$. Suppose $C$ has a point $z$ for which the direction
$z-p$ is not in $T_pX$. Then
\[
\mult_pC\le\tfrac12\deg C.
\]
Consequently, if projection of $C$ from $p$ is nonconstant, its
image degree times its generic map degree is at least
$\tfrac12\deg C$.
\end{corollary}
\begin{proof}
Choose an affine hyperplane through $p+T_pX$ which does not contain
$z$. Its linear equation $\ell$ restricts to an element of
$\mathfrak m_{X,p}^2$, because its value and differential on $X$
both vanish at $p$. On the curve it therefore belongs to
$\mathfrak m_{C,p}^2$, and it is not identically zero.
The one-dimensional reduced local ring of the curve is
Cohen--Macaulay. Thus, writing $R=\mathcal O_{C,p}$, the local
intersection number with the hyperplane is
$\operatorname{length}(R/(\ell))$, and
$\operatorname{length}(R/(\ell^j))=
j\operatorname{length}(R/(\ell))$.
Since $(\ell^j)\subseteq\mathfrak m_{C,p}^{2j}$, comparison with
the Hilbert--Samuel leading term gives
\[
\operatorname{length}(R/(\ell))\ge2\mult_pC.
\]
B\'ezout bounds this local intersection number by $\deg C$.
The final assertion follows from
\eqref{poly:point-projection-formula}.
\end{proof}
\begin{lemma}[The plane-curve polar bound]\label{poly:polar}
Let $C\subset\PP^2_{\C}$ be a reduced plane curve of degree $a$.
If $m_q=\mult_qC$, then
\begin{equation}\label{poly:polar-sum}
\sum_{q:\,m_q\ge2}m_q(m_q-1)\le a(a-1),
\qquad
\sum_{q:\,m_q\ge2}m_q^2\le2a(a-1).
\end{equation}
The sums include points on any chosen line at infinity.
\end{lemma}
\begin{proof}
Write $C=\{F=0\}$ with $F$ homogeneous and squarefree. A general
first polar
\[
G=\lambda_0\frac{\partial F}{\partial X_0}
+\lambda_1\frac{\partial F}{\partial X_1}
+\lambda_2\frac{\partial F}{\partial X_2}
\]
has degree $a-1$ and has no irreducible factor in common with $F$.
Indeed, for every irreducible factor $F_i$ some derivative of $F_i$
is nonzero modulo $F_i$ in characteristic zero. Modulo $F_i$, the
corresponding derivative of $F$ is this derivative times the product
of the other factors. A generic coefficient vector avoids
vanishing identically on each of the finitely many components.
In an affine chart at $q$, write $f$ for the local equation of the
curve. The three dehomogenized derivatives of $F$ are, after
renaming the coordinates,
\[
f_x,\qquad f_y,\qquad af-xf_x-yf_y.
\]
Each has order at least $m_q-1$, so the local equation of $G$ has
order at least $m_q-1$. The elementary local intersection
inequality gives
\[
I_q(F,G)\ge m_q(m_q-1).
\]
One can see that inequality directly on the reduced local branches:
a branch of multiplicity $b$ has a primitive parametrization whose
two coordinates have minimum order $b$, and substituting into a
polynomial of order $c$ gives order at least $bc$. Add over the
branches to obtain the displayed bound. Since $F$ and $G$ have no
common component, B\'ezout gives total intersection number $a(a-1)$
and in particular makes the set of points with $m_q\ge2$ finite.
This proves the first inequality. The second follows from
$m^2\le2m(m-1)$ for every integer $m\ge2$.
\end{proof}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/polynomial.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/profiles.tex ====
\section{Polynomial scale profiles}\label{sec:profiles}
We work along the contradiction sequence, with
\[
N=|P|,\qquad B=N^{1/d},\qquad A=B^2,\qquad M=o(A).
\]
In this section a further parameter $\delta\to0$ is given, and
$E=\delta N/A$. The parameter will be the total directional degree in
the sparse-cones argument. All constants below may depend on $d$.
Our aim is to partition the sample into pieces on which successive
polynomial cutting degrees can be recorded uniformly. The resulting
profiles will bound component masses from above and polynomial
restriction ranks from below.
\subsection{Conventions and the partition}
For a width $s\to\infty$, $s\le\log B$, put
\begin{equation}\label{prof:testing-degree}
T_s(b)=B\exp(bs).
\end{equation}
Degrees are rounded to integers. Throughout, an estimate
$U\ge V\exp(-o(s))$ means
\[
\liminf\frac{\log(U/V)}s\ge0.
\]
Equivalently, every fixed $\varepsilon>0$ can replace $o(s)$ by
$\varepsilon s$, for all sufficiently large indices. The analogous
convention applies to upper bounds. We only use such errors in the
presence of a subsequently specified strict positive margin.
A \emph{piece} below is a subset of the sample, together with one path
of polynomial cuts. The entire path, rather than a different path at
each point, is attached to the piece. At every point on the piece each
successive cut is proper on every component of the preceding local
system. We refer to the irreducible components of that system meeting
the piece as its \emph{carriers}. Different points can have different
carriers. Properness at the counted points will suffice for every
degree estimate.
At testing degree $D$, the normalized time is $\log(D/B)/s$.
We record each cut at the testing time when it is made; its actual
degree may be smaller. When the $d$ recorded times on a path have
subsequential limits $b_1,\ldots,b_d$,
we call each open interval between consecutive distinct limits a
\emph{plateau}. Its number of completed cuts, and hence its local
dimension, is constant. We also use initial and final plateaux for
the intervals before the first and after the last limiting cut.
\begin{proposition}[Multiscale partition]\label{prof:partition}
There are $s_*\to\infty$ and partitions of all but $o(N)$ sample points
into a core and non-core pieces with the following properties.
\begin{enumerate}
\item The core is simultaneously isolated by equations of a degree $L$
such that $EL^2=o(N)$.
\item Each non-core piece has a dyadic width
$s=2^{-a}\log B\ge s_*$ and size $n=N\exp(-o(s))$. Its path has $d$
proper hypersurface cuts. Along any sequence of pieces, after passing
to a subsequence, their normalized cut times converge to
\[
-1\le b_1\le\cdots\le b_d\le1,\qquad
\max_i|b_i|\ge\tfrac12.
\]
The degree of cut $i$ is at most
$D_i\exp(o(s))$, where $D_i=B\exp(b_i s)$.
\item Let $b$ lie strictly between consecutive distinct limiting cut
times, and let $j=\#\{i:b_ii}a_r<\frac{a_i}{9}.
\]
If a residual survives at step $i$, every later terminal piece inside
it has size at least
$m\exp(-a_i/2-\sum_{r>i}a_r)$. A proper cut available when
extraction stopped captured fewer than $m\exp(-a_i)$ residual points.
Its captured fraction in that terminal piece is consequently at most
\begin{equation}\label{prof:fragmentation-bound}
\exp\left(-\frac{a_i}{2}+\sum_{r>i}a_r\right)
\le \exp(-7a_i/18)\longrightarrow0.
\end{equation}
This proves the required no-capture assertion on any limiting open
plateau. To allow a fixed multiplicative factor in the testing
degree, choose a slightly later grid time which is still inside that
plateau.
At a fixed index the nodes in all these trees are disjoint. Their
discarded residual mass is at most $\exp(-a_i/2)$ times their total
mass. Thus the regularization discards at most
\begin{equation}\label{prof:window-discard}
C_d N(1+\sqrt{\log s})\exp(-s^{1/10}/2)
\end{equation}
points at width $s$. This estimate is summable over windows even if
$s_*$ grows arbitrarily slowly. To see this, reverse their order and
bound by widths $2^m u$, $m\ge0$, with $u\ge s_*$. Put $t=u^{1/10}$
and $c=(\log2)/10$. The inequalities
\[
2^{m/10}\ge1+cm,\qquad
\sqrt{\log(2^m u)}\le\sqrt{\log u}+\sqrt{m\log2}
\]
bound the sum of the fractions in~\eqref{prof:window-discard} by
\[
C_d e^{-t/2}\sum_{m\ge0}
(1+\sqrt{\log u}+\sqrt{m\log2})e^{-ctm/2}
=O_d((1+\sqrt{\log u})e^{-u^{1/10}/2})=o(1).
\]
The separately discarded small remainders have fractions
$\exp(-s^{1/3})$ and are summable by the same argument. No factor
equal to the number of windows is used.
The discarded mass is therefore negligible across all windows.
We check the remaining size and cut-time conditions.
Each retained terminal piece has size at least its initial batch size
times $\exp(-o(s^{1/3}))$, and hence is $N\exp(-o(s))$. The inherited
lower boundary is negligible even relative to the smallest such
piece, since
\[
\frac{N\exp(-\sqrt{2s})}
{N\exp(-\sqrt{s}-o(s^{1/3}))}
=\exp(-(\sqrt2-1)\sqrt{s}+o(s^{1/3}))\to0.
\]
There are exactly $d$ cuts on a path. Their times have subsequential
limits $b_1\le\cdots\le b_d$ in $[-1,1]$. For a first-type batch,
some cut occurs by limiting time $-1/2$: otherwise its defining
polynomial would capture the entire piece in an initial
full-dimensional no-capture interval. For a remainder piece the
last cut cannot have limiting time less than $1/2$. Otherwise its
path would isolate more than $N\exp(-\sqrt{s})$ points by equations
of degree at most $B\exp(s/2)$, contradicting termination of the
second greedy operation. This proves the imbalance and all stated
properties. The estimates were uniform over nodes and pieces, which
also proves the final sequence quantifier.
\end{proof}
\subsection{Degree budgets and propagation of rank}
The partition supplies paths and intervals on which proper tests
capture few points. We now prove that their degree scales are
balanced and control both component masses and restriction ranks.
In particular, small exceptional component degree will imply small
sample mass.
For a limiting profile define
\begin{equation}\label{prof:profile-functions}
D_i=B e^{b_i s},\qquad e_j=\prod_{i\le j}D_i,\qquad e_0=1,
\qquad \sigma(b)=\prod_{i=1}^d\min(T_s(b),D_i).
\end{equation}
On a plateau after $j$ cuts, $\sigma(b)=e_jT_s(b)^{d-j}$.
Figure~\ref{fig:scale-profile} illustrates this relation.
\begin{proposition}[Budgets and balanced profiles]\label{prof:budget}
For every non-core profile,
\begin{equation}\label{prof:balance}
\sum_{i=1}^d b_i=0,\qquad b_1<0j}D_i\right)\exp(o(s))
\end{equation}
points. This counts all points touching those components, whether
or not they have been assigned to them. Finally, for every fixed
$\alpha>0$, every subset $S$ of at least $\alpha n$ piece points has
\begin{equation}\label{prof:rank-budget}
H_S(T_s(b))\ge\sigma(b)\exp(-o(s))
\end{equation}
at each interior testing time, and with the usual limiting
interpretation at a cut time.
\end{proposition}
\begin{proof}
Apply B\'ezout successively, retaining the proper intersections
through counted points. It gives the carrier degree bound and,
after applying the later cuts to a specified carrier subcollection,
\eqref{prof:mass-budget}. Applied to the entire path it gives
$n\le(\prod_iD_i)\exp(o(s))$. Since $n=N\exp(-o(s))$ and $N=B^d$,
this proves $\sum_i b_i\ge0$.
We prove~\eqref{prof:rank-budget} by propagation through the finitely
many plateaux; the assertion is always for every fixed positive
density subset, including subsets chosen during the proof. Before
the first cut, no nonzero polynomial of the testing degree can
vanish on $S$. Its envelope is therefore the ambient space, whose
rank is comparable to $T_s(b)^d$.
On a plateau of dimension $l$, let $V$ be the testing-degree envelope
of $S$. At all but $o(n)$ points of $S$, at least one local carrier
is contained in $V$. Indeed, if no carrier through a point is
contained, a generic linear combination of the envelope equations
is proper on all those carriers and vanishes at the point. There
are finitely many components and sample points, so the combination
can be chosen simultaneously; no-capture then applies.
For this envelope, choose at each such point one contained local
carrier, and choose one irreducible component of $V$ containing each
distinct carrier so chosen. Let the points inherit the component
chosen for their carrier. Group all irreducible components of $V$ by
dimension, counting the points by these choices; components receiving
no points remain in the degree of their group. Some dimension $h\ge l$
group, of total degree $a$, covers a fixed positive fraction of $S$.
Writing $S'$ for that fraction and $T=T_s(b)$, the component Hilbert
bounds give
\[
H_S(T)=H_V(T)\gtrsim aT^h,\qquad
H_{S'}(T')\lesssim a(T'+1)^h\quad(T'0$ and the $d-2$ later
entries are at least $b_2$, contradicting the zero sum because
$d>2$. This proves~\eqref{prof:balance}.
\end{proof}
\begin{figure}[htbp]
\centering
\input{figures/scale-profile}
\caption{An illustrative limiting profile in dimension four, with fixed
window width $s$ and cut times $(b_1,b_2,b_3,b_4)=(-0.8,-0.4,0.3,0.9)$.
The degree scales are $D_i=T_s(b_i)$, where $T_s(b)=B e^{bs}$, and
$e_j=\prod_{i\le j}D_i$. On the highlighted open plateau $(b_2,b_3)$,
two cuts have occurred and $\sigma(b)=e_2T_s(b)^2$.
The staircase shows carrier dimension; its vertical drops are schematic.
General profiles may have coincident limiting cuts.}
\label{fig:scale-profile}
\end{figure}
\FloatBarrier
\subsection{Testing individual components and products}
\begin{proposition}[Regularity and individual cuts]\label{prof:regularity}
Inside an open plateau, individual proper cuts of degree $O(T_s(b))$
on the different carriers collectively capture only $o(n)$ points.
At a slightly later interior testing time there are common equations
for the entire carrier family whose Jacobian has full codimension
rank at all but $o(n)$ points. At those surviving points the carrier
is unique and smooth, and its tangent space is testable by equations
and minors of the same interior degree scale.
The assertions also hold for the union of two such families, and
for unions from $\exp(o(s))$ pieces with the same limiting profile
and width, provided each piece retains its own assigned masses.
Common equations vanish on the whole union. In particular, two
different members of that union cannot meet at a surviving point
where the common Jacobian has full rank.
Flat carriers which are not defined over $\R$ may be discarded
with negligible mass.
\end{proposition}
\begin{proof}
Every carrier used here is an irreducible component of its fixed
path locus. Indeed, at every point of the piece on that carrier,
the successive proper cuts give the current local dimension. A
larger irreducible component containing the carrier would pass
through that point and contradict this local dimension. The path
locus may have larger components elsewhere; they remain in its
equations.
Let the plateau start at time $\beta0$. A label map is a rational map $\phi$
from pairs to a fixed affine space, with bounded-degree coordinate
numerators and denominators on the chosen charts. The image assigned
to carriers $X,Y$ is the closure of $\phi(X\times Y)$.
\begin{lemma}[Product testing]\label{prof:product-testing}
Take two pieces, or the pooled pieces described above, in a common
window with the same limiting profile. On a fixed plateau, fix in
each set an assignment of every point to one carrier of its original
piece that contains it. These assignments precede the tests below
and are retained under later restrictions. Let $X,Y$ denote the
assigned carriers of a pair, and fix an interior testing time $b$.
A polynomial of degree $O(T_s(b))$ captures only
$o(n_xn_y)$ pairs at which it does not vanish identically on
$X\times Y$. The same holds for a number of rational tests bounded
independently of the sequence, provided their denominators are
nonzero at the pairs concerned and their numerator polynomials have
degree $O(T_s(b))$ on the chosen charts, with a common implied
constant.
Consequently an equation system containing the labels of a dense
graph contains the complete assigned component images at all but
a negligible fraction of its pairs, whenever the label map has
bounded degree on these charts and the cleared numerator polynomials
of all pulled-back equations have degree $O(T_s(b))$ with a common
implied constant. The denominators used in these pullbacks must be
nonzero at the actual pairs concerned. For any collection of rational
rank tests whose size is bounded independently of the sequence and
which are generically nonzero on the relevant assigned images, the
tests are nonzero at all but $o(n_xn_y)$ corresponding actual pairs,
provided their denominators are nonzero there and their cleared
pullback numerators obey the same degree bound.
\end{lemma}
\begin{proof}
For an actual source point $p$, apply the individual-cut conclusion
of Proposition~\ref{prof:regularity} on every target carrier $Y$
on which the specialization is nonidentically zero.
For the other case, fix $Y$. If the polynomial is not identically
zero on $X\times Y$, choose a generic $y\in Y$ for which its
specialization is nonidentically zero on each such $X$.
The same individual-cut conclusion on the source bounds points $p$ where the polynomial vanishes
identically on $Y$. Average this bound with the target masses of
the $Y$'s. The fixed assigned sets are disjoint within each factor,
so these weighted sums are unambiguous even when carriers meet.
For pooled pieces, retain their original mass accounting.
All bounds are uniform over the polynomial and the
pieces by their sequence formulation.
For a system of equations, pull back each equation and clear its
chart denominator separately. The resulting numerator polynomials
vanish at the actual system points and have the common degree bound.
On every component product carrying a pair on the chart whose image
is not contained in the system, at least one numerator is
nonidentically zero. A generic linear combination of the numerators
is therefore nonidentically zero on every such product
simultaneously. It has the same degree bound: a finite basis of
their span suffices, regardless of the number of system equations.
Apply the first assertion to this combination.
For rank tests use their cleared pullback numerators. When a rank
condition is expressed by minors whose cleared numerators obey the
common degree bound, a generic linear combination of those numerators
is nonidentically zero on every relevant component product where the
rank condition holds generically, and its zero set contains every
rank failure. A bounded number of the resulting
tests has a union of failure sets of size $o(n_xn_y)$. A slightly
later interior time absorbs the uniform constant in the degree
bound. This proves the last assertion without assuming that sample
points are generic on their carriers.
\end{proof}
\subsection{Selecting the two windows}
\begin{proposition}[Selection of profile pairs]\label{prof:pair-selection}
For every $p\in P$, let $C_p$ be a finite family of irreducible
projective curves in $\PP^{d-1}$, each spanning a projective subspace
of dimension at most two, with total degree at most $E=\delta N/A$.
Suppose that $1-o(1)$ of
the unordered pairs $\{p,q\}$ satisfy $\pi_p(q)\in C_p$ or
$\pi_q(p)\in C_q$. After the global terminal deletion described
below, one of the following configurations occurs.
\begin{enumerate}
\item A core of positive relative size is covered.
\item Two sequences of non-core pieces have a common dyadic width
$s$, the same limiting profile, and an ordered product covered in
one orientation with positive relative density.
\item Two sequences of non-core pieces have widths with ratio
tending to infinity, both $o(\log B)$, the same limiting profile,
and such a positively covered ordered product.
\end{enumerate}
In the common outermost window $s=\log B$, the two factors may
instead be the same pool of pieces in a shrinking profile bin.
That pool has size $n\ge N\sqrt\delta$, is the union of
$\exp(o(s))$ pieces, and retains all the preceding degree, mass,
regularity, and product-testing conclusions to exponential
accuracy. All selected incidences may be required to lie on
physical lines containing at most $B^{o(1)}$ sample points.
The global terminal deletion means the following. Whenever a
target point was assigned to its carrier curve after the
$(d-1)$st cut, its projection from the center is not a curve
contained in the center's directional family.
\end{proposition}
\begin{proof}
Assign each point of every non-core piece to one of its carrier
curves after the $(d-1)$st cut. Omit assignments to nonreal lines.
Such a line contains at most one real point, so the omitted
fraction in a piece is at most
\[
\frac{e_{d-1}\exp(o(s))}{n}
=D_d^{-1}\exp(o(s))=o(1),
\]
using~\eqref{prof:balance}. This is uniform over pieces. Every
point is assigned at most once; pool repeated curves. Apply
Proposition~\ref{geo:terminal} once to this global assignment. It removes
only $o(N^2)$ ordered incidences, and hence leaves the required
almost-complete unoriented coverage. Assignments retain their
original meaning if pieces are later pooled.
If the core has positive relative size, the cone over a
directional family has degree $O(E)$ and dimension at most two.
The core's isolation equations, restricted to its components,
and B\'ezout bound its intersections with the core by $O(EL^2)$
per center. This is $o(N)$, so neither orientation can cover a
positive fraction of the core pairs. This resolves the first
alternative. Otherwise discard the core.
Here are details of the remaining selection, including the order
of the limits. First fix a precision $1/h$, and partition the
compact space of normalized drop lists and values of
$s/\log B\in[0,1]$ into finitely many bins of that diameter.
Also bin the dyadic index modulo an integer tending to infinity
with $h$. Two independent random retained points fall in one
common bin with probability bounded below by a positive constant
depending only on $h$. Thus the relative uncovered probability
conditional on this agreement tends to zero for fixed $h$.
Select a pair of pieces with small relative uncovered
probability, and pass to an orientation containing at least half
the covered pairs. Now let $h$ tend to infinity sufficiently
slowly with the sample index. This standard diagonal choice
retains conditional coverage while making the profiles and
normalized widths converge to the same limits.
The selected dyadic indices are either equal on a subsequence,
or their difference tends to infinity, by their congruence
condition. In the latter case the width ratio tends to infinity.
Their normalized widths have the same limit, so that limit must
be zero. This proves the two window alternatives.
There is a useful refinement at the outermost window. If its
total mass tends to zero, discard it before the selection. If
its mass is bounded below on a subsequence, work only there.
For each fixed precision choose a largest profile bin and use
its pool as both factors. It has a fixed positive mass at that
precision, and its relative uncovered fraction tends to zero.
In the diagonal choice increase precision slowly enough that
its mass is at least $N\sqrt\delta$ and
$N\exp(-o(\log B))$. This is possible because $\delta\to0$.
Each constituent piece has size $N\exp(-o(s))$ uniformly, so
there are only $\exp(o(s))$ of them. Their profiles differ by
$o(1)$, and the conclusions for pooled families follow from
Proposition~\ref{prof:regularity} and
Lemma~\ref{prof:product-testing}.
Finally, Szemer\'edi--Trotter, with a generic planar projection,
makes the fraction of ordered pairs on lines of occupancy above
a threshold $H$ arbitrarily small as $H\to\infty$: summing its
dyadic rich-line estimate gives $O(N^2/H+N h_{\max})$, and the
proper-flat bound gives $h_{\max}=o(N)$. At each fixed selection
precision first choose $H$ large enough for its conditioning
probability. Increase the precision sufficiently slowly that
$H\le B^{o(1)}$ and all the preceding conditional errors still
vanish. This is compatible with the outer-pool mass condition.
All constants and precisions are fixed before taking each
asymptotic limit; the final diagonal sequence merely combines
these finitely specified requirements.
\end{proof}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/profiles.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/reduction.tex ====
\section{The reduction to sparse cones and concentration}
\label{sec:reduction}
This section proves Theorem~\ref{thm:main} from the sparse-cones theorem,
the rich-motion theorem, and the uniform concentration theorem.
Their proofs occupy the later sections and appendices. We include the
selection and sampling arguments here, since keeping their constants
uniform is essential.
\subsection{The contradiction regime}
Suppose that Theorem~\ref{thm:main} fails, and take the least dimension
\(d\ge3\) in which it fails. There is then a sequence of finite sets
\(P\subset\mathbb R^d\) for which, with
\begin{equation}\label{red:regime}
N=|P|,\qquad M=1+|\Delta(P)|,\qquad
B=N^{1/d},\qquad A=B^2,
\qquad N\longrightarrow\infty,\quad M/A\longrightarrow0.
\end{equation}
Here and below a statement along the sequence is understood after
discarding finitely many terms, if necessary. The fact that
\(N\to\infty\) follows because a set of at least two points determines
at least one distance. Adding \(1\) to the number of distances does
not affect the vanishing ratio.
For \(3\le u0\) such that every proper real
affine flat contains at most \(N B^{-c_0}\) points for all sufficiently
large terms of the sequence. The same assertion holds for a proper
complex affine flat when only its real sample points are counted.
Planes have the more precise bound \(B^{2+o(1)}\).
\end{lemma}
\begin{proof}
From a point on a line, any positive distance has at most two realizations
on that line. For a circle, use a sample point on the circle: the
intersection with a circle of prescribed positive radius about that
point has at most two points. These observations include the sample
point itself after using \(M=1+|\Delta(P)|\).
The planar bound is Corollary~\ref{ci:planar-occupancy}. The other bounds
follow by applying the lower-dimensional assertion to the points in
the flat, whose pairwise distances are among the distances of \(P\).
Since \(M\le B^2\), the planar bound is \(O(B^2\log B)\), while a proper
flat of dimension \(u\ge3\) contains \(O(B^u)\) points. Thus, for example,
\(c_0=1/2\) works after advancing along the sequence. A complex affine
flat containing real points contains their real affine span, whose
real dimension is at most its complex dimension. Applying the real
bound to that span proves the last assertion.
\end{proof}
We use complex varieties for polynomial arguments. Degree means the
degree of the projective closure; for a family of components of a fixed
dimension it means the sum of their degrees. A projective direction
from \(p\) is denoted by
\[
\pi_p(q)=[q-p]\in\mathbb P^{d-1}.
\]
Restriction of polynomials of degree at most \(D\) to an affine set
\(T\) has rank \(H_T(D)\). In projective space we use homogeneous
polynomials of degree exactly \(D\). The degree-\(D\) envelope
\(\Env_D(T)\) is the common zero locus of all such polynomials
vanishing on \(T\). Its rank at that degree equals \(H_T(D)\).
Here is the form of the sparse-cones theorem that we will use.
\begin{quote}
In the regime~\eqref{red:regime}, one cannot assign to each \(p\in P\)
a union \(C_p\) of irreducible projective curves, each spanning a
projective space of dimension at most two, with
\[
\deg C_p\le\delta N/A,\qquad\delta\to0,
\]
such that all but \(o(N^2)\) unordered pairs \(\{p,q\}\) satisfy
\(\pi_p(q)\in C_p\) or \(\pi_q(p)\in C_q\).
\end{quote}
This is Theorem~\ref{sc:theorem}. Both the alternative between the two
endpoints and the absence of a prescribed rate for \(\delta\) are
important.
\subsection{A symmetric selection of directions}
\begin{proposition}\label{red:directions}
After passing to a subsequence, there is an undirected graph
\(\mathcal G\) on \(P\) with at least \(cN^2\) edges such that, for every
vertex \(p\) and every irreducible projective variety
\(Y\subset\mathbb P^{d-1}\) of dimension \(a\),
\begin{equation}\label{eq:direction-count}
\#\{q:\{p,q\}\in\mathcal G,\ \pi_p(q)\in Y\}
\le C\,\deg(Y)A^a.
\end{equation}
The positive constants \(c,C\) are fixed along the subsequence.
\end{proposition}
\begin{proof}
First discard pairs on lines containing more than \(H\) sample points,
where \(H\) will be a sufficiently large fixed constant.
A generic planar projection preserves the relevant distinct points,
lines, and incidences. The rich-line consequence of
Theorem~\ref{ci:st} therefore bounds the number of physical lines with
at least \(t\) points by
\[
C(N^2/t^3+N/t),\qquad t\ge2.
\]
If \(L_{\max}=o(N)\) is the maximum occupancy, a dyadic sum gives
\[
\#\{\text{discarded pairs}\}
\le C N^2/H+C N L_{\max}=O(N^2/H)+o(N^2).
\]
At each \(p\), independently of the other stars, greedily remove
directions on any irreducible curve spanning at most a projective plane
that currently contains more than \(K A\) times its degree many
partners. Each removal contains at least one previously unremoved
partner, so the process terminates. Record the curves chosen in that
star. Their total degree is at most \(N/(KA)\), because their charged
partner sets are disjoint. Now keep an unordered pair only when it
survived both endpoint procedures.
There must be fixed \(H,K\) and a subsequence on which a positive
fraction of pairs survives. Otherwise, a diagonal choice with
\(H,K\to\infty\) sufficiently slowly would make the surviving fraction
tend to zero, while the first, rich-line discard also has vanishing
fraction. The recorded curves would then cover all but \(o(N^2)\)
pairs from one endpoint or the other and have total degree at most
\(N/(KA)=o(N/A)\) in every star. This contradicts
Theorem~\ref{sc:theorem}. Fix such \(H,K\) and a positive-density
subsequence.
We prove~\eqref{eq:direction-count} by induction on \(a\). For \(a=0\)
it is the light-line bound. Fix a variety \(Y\) of dimension \(a\ge1\),
a center \(p\), and the selected partners counted on \(Y\). Let \(U\)
be the real linear span of their displacements from \(p\), and put
\(\ell=\dim U\). There is nothing to prove if this collection is empty.
Consider a full radius class about \(p\), meaning all points of \(P\)
at one prescribed distance from \(p\). Suppose it has \(L\ge2M\)
distinct orthogonal projections to \(U\), and choose physical points
\(z_1,\ldots,z_L\in P\) in that class representing those projections.
For each counted partner \(q\), the distances
\(|q-z_i|\), including zero when it occurs, take at most \(M\) values.
Consequently at least
\[
L^2/M-L\ge L^2/(2M)
\]
ordered pairs \(i\ne j\) have equal distance to \(q\).
As the \(z_i\) lie in a common radius class,
\[
|q-z_i|=|q-z_j|
\quad\Longrightarrow\quad
(q-p)\cdot(z_i-z_j)=0.
\]
The projection of \(z_i-z_j\) to \(U\) is nonzero. The resulting
hyperplane section is proper on \(Y\): if its linear equation vanished
on \(Y\), it would vanish on all counted displacements and hence on
\(U\), which is impossible for its nonzero normal in \(U\).
B\'ezout's theorem and the induction hypothesis bound the number of
partners on each section by \(C\deg(Y)A^{a-1}\). Double counting gives
\[
\#\{q\text{ counted}\}\frac{L^2}{2M}
\le C L^2\deg(Y)A^{a-1}.
\]
This is~\eqref{eq:direction-count}, since \(M\le A\).
In the remaining case, each of the at most \(M\) radius classes has
fewer than \(2M\) projections to \(U\). Thus the full sample has
\(O(M^2)\) fibers on which both the radius about \(p\) and the
projection to \(U\) are fixed.
A fiber lies on a sphere in an affine space of dimension \(d-\ell\).
If \(\ell\ge4\) and \(d-\ell\ge3\), lower-dimensional induction bounds
each fiber by \(O(M^{(d-\ell)/2})\). If \(d-\ell=2\), the circle bound
is \(O(M)\); if \(d-\ell\le1\), the fiber has at most two points.
In all cases the total is \(O(M^{d/2})\), contradicting
\(N/M^{d/2}\to\infty\). Thus this alternative is impossible when
\(\ell\ge4\).
It remains to consider \(\ell\le3\).
For \(a\ge2\), Lemma~\ref{red:flat-caps} bounds the counted partners
by \(O(A^2)\), which is sufficient. If the span is the entire space,
then \(d=3\) and the trivial bound \(N=A^{3/2}\) is sufficient instead.
For \(a=1\), either \(Y\subset\mathbb P(U_{\mathbb C})\), in which case
the greedy curve bound applies, or its intersection with that
projective subspace is proper and consists of at most \(\deg Y\)
points. The light-line bound handles the latter case. This completes
the induction. Fixed increases in the constants at the finitely many
dimensions are harmless.
\end{proof}
\begin{proposition}[Independent evaluations in every star]
\label{red:independent-stars}
A further symmetric selection retains at least \(c'N^2\) pairs and
has the following property: the direction-evaluation vectors of the
partners in each star are linearly independent for homogeneous
polynomials of degree \(D=\lfloor A\rfloor\).
In particular each selected star admits homogeneous separators of
degree \(D\).
\end{proposition}
\begin{proof}
First consider any subset \(S\) of the partners in one star, counting
physical partners even when their projective directions agree.
Form the projective envelope of those directions at degree \(D\).
Assign each direction to an irreducible component containing it, and
group these components by dimension. For a group of total degree \(a_j\)
and dimension \(j\), Proposition~\ref{red:directions} bounds the assigned
physical partners by \(C a_j A^j\). The component Hilbert lower bound
in Lemma~\ref{poly:hilbert}, applied at the defining degree \(D\), gives
\[
H_S(D)=H_{\Env_D(S)}(D)\ge c_d a_jD^j.
\]
There are at most \(d\) groups, and \(D\asymp A\). Therefore
\begin{equation}\label{eq:star-rank}
H_S(D)\ge c_1|S|
\end{equation}
with a fixed \(c_1>0\), uniformly for every subset \(S\).
Take a maximal undirected subset of the edges from
Proposition~\ref{red:directions} whose evaluations are independent at
both endpoints. Each omitted edge is blocked at an endpoint: its
evaluation vector lies in the span of the selected vectors there.
Charge it to one such endpoint. If the selected degree at \(p\) is
\(s_p\), all vectors charged to \(p\) together have rank at most \(s_p\).
Equation~\eqref{eq:star-rank} bounds their number by \(s_p/c_1\).
Summing over vertices bounds the number of omitted edges by
\(2/c_1\) times the number of selected edges. Positive density follows.
Independent evaluation vectors mean that the evaluation map onto the
coordinates indexed by the star is surjective. Taking the coordinate
basis in its image gives the asserted homogeneous separators.
\end{proof}
Write \(\mathcal S\) for this final selection. A selected star has at
most one partner in any projective direction, since two proportional
evaluation vectors could not be independent.
\subsection{The equal-distance graph and its pair flats}
Take \(Q=RP\), where \(R\) is a sufficiently generic real rotation,
and transport \(\mathcal S\) to \(Q\).
On the \(N^2\) vertices \((p,q)\in P\times Q\), put an edge between
\((p,q)\) and \((p',q')\) exactly when
\[
\{p,p'\}\in\mathcal S,\qquad
\{q,q'\}\in R\mathcal S,\qquad |p-p'|=|q-q'|.
\]
If \(s_\rho\) is the number of selected physical pairs of length
\(\rho\), the number of these edges is
\(2\sum_\rho s_\rho^2\). Cauchy--Schwarz gives
\begin{equation}\label{eq:equality-edges}
2\sum_\rho s_\rho^2
\ge \frac{2|\mathcal S|^2}{M}
\ge c_2 N^4/M.
\end{equation}
For \(d=3\), let \(g(x)=Sx+h\), with \(S\in O(3)\) and
\(h\in\mathbb R^3\), range over spatial isometries, and define its set
of matched graph vertices by
\[
V_g=\{(p,g(p)):p\in P,\ g(p)\in Q\},\qquad k_g=|V_g|.
\]
The map \(g\mapsto R^{-1}\circ g\) preserves match counts and identifies
these motions with motions from \(P\) to itself. Since \(M\le A\)
eventually, Theorem~\ref{mot:rich} shows that the motions with
\(k_g\ge C_{\mathrm{rich}}A\) form a finite family, with both
orientations included.
Delete every existing graph edge whose endpoints both belong to one
of these sets \(V_g\). The number of deleted edges is at most
\[
\sum_{k_g\ge C_{\mathrm{rich}}A}\binom{k_g}{2}
\le\frac12\sum_{k_g\ge C_{\mathrm{rich}}A}k_g^2
\le\frac{K_{\mathrm{rich}}}{2}\frac{N^4}{A}
=o(N^4/M).
\]
Overlapping sets \(V_g\) can only decrease the actual deletion count.
After this deletion, no vertex can have at least
\(C_{\mathrm{rich}}A\) remaining neighbors which, together with that
vertex, are matches of one spatial isometry. Such a motion would have
at least \(C_{\mathrm{rich}}A\) matches, and all those incident edges
would have been deleted.
In every dimension, let \(E_0\) be the edge count at the start of
pruning, and repeatedly delete vertices of degree below
\(E_0/(2N^2)\). The total number of deleted edges is less than
\(E_0/2\), so at least one edge survives.
The resulting nonempty graph \(\mathcal H\) has minimum degree
\begin{equation}\label{eq:minimum-degree}
\delta(\mathcal H)\ge c_3N^2/M,\qquad
\delta(\mathcal H)/A^{d-1}\longrightarrow\infty.
\end{equation}
Only subsets of the original stars have been retained, so their
independence and separators remain valid.
Identify skew forms on \(\mathbb C^{d+1}\) with matrices
\[
\begin{pmatrix} Z&c\\-c^{\mathsf T}&0\end{pmatrix},
\qquad Z^{\mathsf T}=-Z,\quad c\in\mathbb C^d.
\]
The pair \((p,q)\) defines an affine flat
\begin{equation}\label{eq:pair-flat}
F_{p,q}=\{(Z,c):Zv_0+c=y_0\},\qquad
v_0=(p+q)/2,\quad y_0=(p-q)/2 .
\end{equation}
Its dimension is \(s_0=d(d-1)/2\). Distinct pairs give distinct flats:
at \(Z=0\) one recovers \(y_0\), and equality for every skew \(Z\)
then recovers \(v_0\).
Each \(F_{p,q}\) is the complexification of the corresponding real
point-pair flat in the construction of Bardwell-Evans and Sheffer
before their generic section
\cite[Theorem~6.1]{BardwellEvansSheffer2019}.
The parameter in the split quadric of
\(\mathbb P(\mathbb C^{d+1}\oplus(\mathbb C^{d+1})^*)\) is
\begin{equation}\label{eq:global-parameter}
[v:y]=[(v_0,1):(y_0,-v_0\cdot y_0)].
\end{equation}
Indeed, on \(F_{p,q}\),
\[
\begin{pmatrix}Z&c\\-c^{\mathsf T}&0\end{pmatrix}
\binom{v_0}{1}
=\binom{Zv_0+c}{-c\cdot v_0}
=\binom{y_0}{-v_0\cdot y_0},
\]
where the last coordinate uses \(v_0\cdot Zv_0=0\). Conversely, the
first \(d\) coordinates of this evaluation equation give
\eqref{eq:pair-flat}. Thus \(F_{p,q}\) is exactly the evaluation flat
for this parameter. This parameter satisfies \(y(v)=0\) and \(v\ne0\).
We next check every hypothesis needed for the two different versions
of Theorem~\ref{conc:theorem}.
\subsection{Global and local concentration}
\begin{lemma}[Global concentration]\label{red:global-concentration}
For the retained pair flats, an irreducible variety \(V\) of dimension
\(s_0+h\) in skew-form space contains at most
\[
C\deg(V)A^h
\]
of the flats, for \(0\le h\le d\), where the endpoint \(h=d\)
denotes the ambient space.
\end{lemma}
\begin{proof}
In Theorem~\ref{conc:theorem}, take \(e=d+1\), so \(r=d\).
Physical separators from Lemma~\ref{poly:separators}, one in \(p\)
and one in \(q\), have a product of degree \(O(M)\). Express them
in the coordinates \(v_0,y_0\) and homogenize with the last coordinate
of \(v\), which is \(1\) on every parameter. They give positive-degree
homogeneous separators of degree \(O(M)\le O(A)\).
Suppose parameters lie in one projective maximal isotropic plane.
Their original real representatives in~\eqref{eq:global-parameter}
belong to its underlying isotropic vector space. Polarization gives,
for any two of them,
\[
(v_0-v'_0)\cdot(y_0-y'_0)=0,\qquad
|p-p'|^2=|q-q'|^2.
\]
The first physical coordinate \(p\) is therefore injective on this
set of parameters, because \(p=p'\) forces \(q=q'\).
There are at most \(N\le A^{d-1}\) such parameters.
The total number of parameters is at most \(N^2=A^d\).
Thus Specification (a) of Theorem~\ref{conc:theorem} applies, with one
fixed constant absorbing the separator degree.
For \(h=0\), an irreducible variety containing a same-dimensional
flat equals that flat. For \(h=d\), the total-count bound suffices.
These give the two endpoints.
\end{proof}
Fix a retained vertex \((p,q)\). On its flat, use \(Z\) as coordinates,
so \(c=y_0-Zv_0\). A neighbor \((p',q')\), with
\(u=p'-p\) and \(w=q'-q\), cuts out
\begin{equation}\label{eq:neighbor-flat}
Z(u+w)=u-w.
\end{equation}
Here \(u,w\) are nonzero real vectors with \(|u|=|w|\).
The rotation \(R\) may be chosen to ensure \(u+w\ne0\) simultaneously
for the finite set of relevant displacement pairs.
\begin{lemma}[Local concentration]\label{red:local-concentration}
Every nonzero polynomial of degree at most \(A\) on \(F_{p,q}\)
contains in its zero set at most \(C A^{d-1}\) of the neighbor flats
in~\eqref{eq:neighbor-flat}.
\end{lemma}
\begin{proof}
The local skew-form model has \(e=d\), \(r=d-1\), and parameters
\[
[v:y]=[u+w:u-w].
\]
They lie on the split quadric, with nonzero \(v\).
They are distinct. Indeed, proportional parameters give
\((u',w')=\lambda(u,w)\). Since the vectors are real and nonzero,
\(\lambda\) is real; uniqueness of a selected partner in its projective
direction first gives \(u'=u\), then \(\lambda=1\) and \(w'=w\).
Multiply a homogeneous direction separator for \(u\) by one for \(w\)
and substitute \(u=(v+y)/2\), \(w=(v-y)/2\).
The product has degree \(O(A)\) and separates the corresponding
neighbor parameter from all others. No physical scale ambiguity
remains, because each selected star contains at most one physical
partner in each projective direction.
For parameters in a common maximal isotropic plane, polarization on
the original real representatives gives
\[
(u_i-w_i)\cdot(u_j+w_j)
+(u_j-w_j)\cdot(u_i+w_i)=0,
\]
or equivalently
\[
u_i\cdot u_j=w_i\cdot w_j.
\]
The rule \(u_i\mapsto w_i\) is a well-defined real isometry on their
spans: every linear relation is preserved by equality of the Gram
matrices and positive definiteness of the real norm.
Extend it to some \(S\in O(d)\). Every neighbor in this isotropic
plane, together with the center, is a match for
\(x\mapsto q+S(x-p)\).
For \(d\ge4\), the number of such neighbors is at most
\(N=A^{d/2}\le A^{d-2}\). For \(d=3\), a collection with at least
\(C_{\mathrm{rich}}A\) neighbors would, together with the center,
violate the survivor property established when the rich match edges
were deleted. The surviving cap is therefore
\(O(A)\). This establishes precisely the isotropic hypothesis
\(O(A^{r-1})\) in every dimension. In particular no restriction to
orientation-preserving motions was made.
Factor the polynomial on \(F_{p,q}\) into irreducible hypersurfaces.
Each component has excess dimension \(h=d-2=r-1\) above a neighbor
flat, and lies in a hypersurface of degree at most \(A\).
Specification (b) of Theorem~\ref{conc:theorem} applies to it; that
specification has no total-count hypothesis. Summing its bound
\(C\deg(V)A^{d-2}\) over components of total degree at most \(A\)
proves the result.
\end{proof}
\subsection{One random sample completes the proof}
\begin{proposition}\label{red:main-contradiction}
The graph \(\mathcal H\) cannot satisfy both bounds in
Lemmas~\ref{red:global-concentration} and
\ref{red:local-concentration}.
\end{proposition}
\begin{proof}
Let \(\mathcal F\) be the family of retained global pair flats and
\(m=|\mathcal F|\). At degree \(D=\lfloor A\rfloor\), form the
envelope of their union. Each flat is contained in one of its
irreducible components. Assign it to one such component and group
components by their dimensions \(s_0+h\), \(0\le h\le d\).
If a group has total degree \(a_h\), global concentration bounds its
assigned flats by \(C a_h A^h\). The Hilbert lower bound at the
defining degree gives
\[
H_{\bigcup\mathcal F}(D)
\ge c a_hD^{s_0+h}.
\]
There are only \(d+1\) groups. Since \(D\asymp A\),
\begin{equation}\label{eq:global-rank-lower}
H_{\bigcup\mathcal F}(D)\ge c_4mA^{s_0}.
\end{equation}
This includes the case in which the envelope is the entire ambient
space.
Choose each flat independently with a small fixed probability
\(\theta>0\). With probability at least \(1/2\), the number selected
is at most \(2\theta m\), by Markov's inequality.
On that event their restriction rank is at most
\[
2\theta m\binom{D+s_0}{s_0}\le C_4\theta m A^{s_0}.
\]
Choose \(\theta\) so small that this is less than the right side
of~\eqref{eq:global-rank-lower}.
At any vertex the sampled neighbors have binomial distribution of
mean at least \(\theta\delta(\mathcal H)\). The probability of fewer
than half that mean is at most
\(\exp(-c\theta\delta(\mathcal H))\).
There are at most \(N^2\) vertices, and
\(\delta(\mathcal H)\gg A^{d-1}\), a fixed positive power of \(N\).
A union bound shows that, with probability tending to one, every
vertex has at least
\(\theta\delta(\mathcal H)/2\gg A^{d-1}\) sampled neighbors.
Both events thus hold for some choice of sample.
Its rank is strictly smaller than that of all flats. Hence a
polynomial \(f\) of degree at most \(D\) vanishes on every sampled
flat but does not vanish identically on some \(F\in\mathcal F\).
For each sampled neighbor \(F'\), it vanishes on the neighbor flat
\(F\cap F'\) inside \(F\). These neighbor flats are distinct by the
local parameter check above. There are more than \(C A^{d-1}\)
of them, contradicting Lemma~\ref{red:local-concentration} applied
to the nonzero restriction \(f|_F\).
\end{proof}
Proposition~\ref{red:main-contradiction}, together with the three
ingredients proved below, rules out~\eqref{red:regime} in the least
possible failing dimension. Thus there is no failing dimension.
Equivalently, in each fixed dimension the ratio
\(|\Delta(P)|/|P|^{2/d}\) has a positive infimum: if it did not, a
sequence with ratio tending to zero would give~\eqref{red:regime}.
This proves Theorem~\ref{thm:main}, including its constant-factor
strength.
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/reduction.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/secants.tex ====
\section{Secants and terminal curves}\label{geo:section}
We work in the contradiction regime \eqref{red:regime}.
In particular, $N=B^d$, $A=B^2$, and $M=o(A)$.
We use the flat bounds of Lemma~\ref{red:flat-caps}: for some fixed
$c_0>0$ every proper complex affine flat contains at most $NB^{-c_0}$
sample points, a plane contains at most $B^{2+o(1)}$ sample points,
and a line contains at most $2M$ sample points.
The complex-flat assertion follows by taking the real affine span of
its real points. Constants throughout this section depend only on $d$.
For an affine point $p$, write
\[
\pi_p(y)=[y-p]\in\mathbb P^{d-1},\qquad y\ne p.
\]
All varieties in the geometric arguments are reduced complex varieties;
their degrees are degrees of projective closures.
\subsection{The secant tangent calculation}
The generic conclusion is a form of generalized trisecant geometry;
compare \cite[Section~3.2]{kaminskikanelbelovteicher2008}. We give the
tangent calculation because the assertion for a particular pair is
also needed.
\begin{lemma}[Secants and a particular-pair version]\label{geo:secants}
Let $X,Y\subset\mathbb A^d$ be irreducible varieties of dimensions
$k,l\ge1$. Suppose that for a general pair $(x,y)\in X\times Y$ the
connecting direction is in neither $T_xX$ nor $T_yY$.
Let $Y'$ be another irreducible $l$-dimensional variety, possibly equal
to $Y$. If a general such line has a further point
$z\in Y'\setminus\{x,y\}$, then $k\le l$.
If $k=l$, then $X$ and $Y$ lie in a common affine $(k+1)$-flat.
More generally, when $k=l$, equality of the projected tangent spaces
at a general pair already implies this common-flat conclusion,
without an assumption about a further root.
There is also the following local assertion. Suppose $p\in X$ and
$q\in Y$ are smooth, and the map
\[
\psi(x,y)=(x,\pi_x(y))
\]
has differential of rank $k+l$ at $(p,q)$.
Suppose a smooth local variety $W$ of dimension $k+l$ at
$(p,\pi_pq)$ contains both product images
$\psi(X\times Y)$ and $\psi(X\times Y')$ locally at the relevant
pairs. If $z\in Y'\setminus\{p,q\}$ has $\pi_pz=\pi_pq$, then
\[
\overline{T_pX}\subseteq\overline{T_qY}
\quad\hbox{in }\mathbb C^d/\mathbb C(q-p).
\tag{\ref*{geo:secants}.1}\label{geo:tangent-inclusion}
\]
Here bars denote the images of vector tangent spaces. In particular,
if these images have dimensions $k=l$ and are unequal, no such $z$
exists. The same source component $X$ must occur at both roots.
\end{lemma}
\begin{proof}
Choose a direction chart by requiring one coordinate of the direction
to equal one. Write $y-x=a u$ and $z-x=b u$ in that chart; the two
nonzero longitudinal parameters $a,b$ are distinct.
For a source velocity $\xi\in T_xX$, variation of $x$ with the other
endpoint fixed has direction derivative $-\bar\xi/a$ at $y$, and
$-\bar\xi/b$ at $z$. The first coordinates of these two image tangent
vectors are both $\xi$. Their difference is therefore vertical and
has direction component $(b^{-1}-a^{-1})\bar\xi$.
At a general pair the product image has dimension $k+l$: its first
coordinate records the $k$ source directions, and injectivity of the
target tangent modulo the connecting line supplies $l$ vertical
directions. If the further root exists generally, the two irreducible
product images coincide. Indeed they have the same dimension $k+l$,
and the first is contained in the second on a dense set. At a general
smooth image point their tangent spaces agree. The vertical kernel of
the first product image is exactly $\overline{T_yY}$.
The preceding subtraction gives
$\overline{T_xX}\subseteq\overline{T_yY}$ and hence $k\le l$.
This calculation also proves the local assertion: the full-rank first
product identifies its tangent image with $T W$, whose vertical kernel
is $\overline{T_qY}$. Source variation with the second root held fixed
still gives tangent vectors in $T W$. No assertion that the second
root belongs to the finite sample is used.
When $k=l$, the projected tangents agree. Thus
\[
T_xX\subseteq T_yY+\mathbb C(x-y),
\qquad
T_yY\subseteq T_xX+\mathbb C(x-y).
\]
Fix a general $y$. Project $X$ projectively away from the affine tangent
plane $y+T_yY$. The first inclusion says that this projection has zero
differential wherever it is defined. In characteristic zero a rational
map with zero differential has zero-dimensional image: on function
fields, every function in its image has zero differential and is
constant. Its irreducible image is consequently one point.
Thus $X$ lies in an affine $(k+1)$-flat containing $y+T_yY$.
The case in which $X$ already lies in the projection center gives the
same conclusion. Interchanging $X,Y$ bounds both affine spans by
$k+1$. If one span has dimension $k+1$, the preceding flat for each
general point of the other variety must equal that span, so it contains
both varieties. If both spans have dimension $k$, both varieties are
flats, and the displayed tangent inclusions say directly that their
affine join has dimension at most $k+1$.
\end{proof}
\subsection{A generic count for families of carriers}
The next formulation separates the geometric count from the scale
regularization in Section~\ref{sec:profiles}.
\begin{lemma}[Generic projection depth]\label{geo:generic-depth}
Let $\mathcal X,\mathcal Y$ be finite families of distinct irreducible
carriers of dimensions $k\ge l\ge1$, where $k0$, one can discard component pairs of
total product weight $o(1)$, and obtain for each remaining source
component $X$ a list $\mathcal Y_X$ of target components, such that:
for every $Y\in\mathcal Y_X$, at a general pair $(x,y)\in X\times Y$
both projected tangents are injective and the number of moving roots
on $\bigcup_{Z\in\mathcal Y_X}Z$ over $\pi_xy$ is at most
$\exp(\epsilon w)$. This counts the generic map degrees of all listed
components sharing that projected image, and excludes the undefined
root $x$.
The hypotheses apply to the two carrier configurations used below:
in a common window, $k=l$, $w=s$, and $e=e_j$; in separated subpower
windows, $w=\log B$, and, when $k=l$, $e=B^{d-l}$.
\end{lemma}
\begin{proof}
First discard pairs for which a general connecting line is tangent at
one endpoint. For a fixed target component $Y$, choose a general
smooth $y\in Y$. Every source component tangent in this sense is
contained in the fixed proper affine flat $y+T_yY$.
Its total assigned source mass is at most $NB^{-c_0}$.
After division by $n_x$, this is $B^{-c_0+o(1)}$.
Average with target weights. The argument with source and target
interchanged removes tangencies at the other endpoint. The choices
of tangent points can be made simultaneously for the finite lists.
For $k=l$, also discard pairs lying in a common $(k+1)$-flat when one
member is nonlinear. That nonlinear member spans the flat: its span
cannot have dimension $k$ unless it is itself a flat. Fixing that
member therefore pins down a proper flat containing the other
member's assigned points. The same flat bound and weighted averaging
show that these pairs have product weight $o(1)$.
Lemma~\ref{geo:secants} now rules out a third moving root except when
$k=l$ and the source and first target are flats in a common
$(k+1)$-flat $H$. Every further listed target with the same projection
must also lie in $H$: for a general $x\in X$, its affine join with $x$
equals $H$. It is a flat, since the nonlinear exception was removed.
Each such flat contributes exactly one moving root. Thus it remains
to bound the number of listed flats in $H$ for most weighted pairs.
The flat members are already distinct within each family. In the slice,
identify a flat occurring in both families and add its two weights; this
changes the bounds by at most a factor two. Fix a small constant
$\eta>0$. Delete flats of normalized weight less than
$e^{-1}\exp(-\eta w)$; their total weight is
$\exp(-\eta w+o(w))$. Slice all remaining flats by a common generic
real projective subspace of codimension $k$. Each becomes a point,
and each generated $(k+1)$-flat becomes a line. For these finite
families, genericity ensures that distinct generated flats yield
distinct lines and that a sliced point belongs to such a line exactly
when the original flat is contained in the corresponding $H$.
The number of sliced points is at most $e\exp(o(w))$.
Let $t_H$ be their number on the line for $H$. The lower weight cutoff
and the physical flat bound give
\[
t_H\le e\exp(\eta w+o(w))B^{-c_0}.
\]
Choose $\etad_i/2$. There are only boundedly many such
centers for each curve. To see this, take a generic birational plane
projection, preserving or increasing multiplicities at this finite
list of points, as in Lemma~\ref{poly:projection}. For a reduced plane
curve of degree $D$, intersection with a general polar derivative
gives
\begin{equation}\label{geo:polar-bound}
\sum_{z:\,\operatorname{mult}_z\ge2}
(\operatorname{mult}_z)^2\le 2D(D-1).
\end{equation}
Indeed the intersection multiplicity at a point of multiplicity $m$
is at least $m(m-1)$, and $m^2\le2m(m-1)$ for $m\ge2$.
A nonlinear irreducible degree-two curve has no point of multiplicity
greater than one; for all other degrees this bounds the number with
multiplicity greater than half the degree by an absolute constant.
The deletion therefore costs $O(\sum n_i)=O(N)$ pairs.
Projection to a line requires the curve and center to lie in one fixed
plane; these pairs cost $o(N^2)$ by the plane cap.
Group the remaining curves at $p$ by their common nonlinear projection
$\gamma$. Let $t_i$ be the generic degree of $\pi_p:Y_i\dashrightarrow
\gamma$ in this group. The point-projection formula, obtained from the
linear-system degree formula with its base-point contribution
\cite[Proposition~4.4]{fulton1998}, and the multiplicity deletion give
\begin{equation}\label{geo:map-degree-comparison}
d_i-\operatorname{mult}_pY_i=t_i e_\gamma,
\qquad d_i\le2t_i e_\gamma.
\end{equation}
An ordered triple $(i,j,k)$ in a group is called valid if each index
occurs at most its corresponding map degree. We claim that for each
fixed ordered triple of curve indices
\begin{equation}\label{geo:triple-center-bound}
\sum_{p:\,(i,j,k)\text{ valid at }p} e_\gamma^{-2}\le C.
\end{equation}
Choose $v$ general on $Y_i$, simultaneously for the finite list of
centers in this sum. Distinct centers give distinct directions from
$v$, since $v$ can avoid all the lines joining pairs of centers.
The map degrees $t_i,t_j,t_k$ still refer to projection from each
original center $p$; projection from $v$ will be used to count the
directions of those centers.
We first claim that, viewed from $v$, each of $Y_j,Y_k$ projects
birationally to a plane curve, and that the two plane images are
distinct unless $Y_j=Y_k$. A general line joining $v\in Y_i$ to a
point of either target curve is tangent at neither endpoint.
Otherwise, after fixing the tangent endpoint, the other nonlinear
curve would lie in its tangent line. Thus the non-tangency hypothesis
of Lemma~\ref{geo:secants} holds.
Failure of birationality would give a further point on the same
target curve over a general joining direction. Equality of the two
plane images for $Y_j\ne Y_k$ would give a further point on the
other target curve. In either case Lemma~\ref{geo:secants} puts
$Y_i$ and the first target curve in a common plane. At any center
$p$ contributing to the sum, the curves belong to one original
nonlinear group. If the two curves are distinct, this is impossible:
projection from a point in their plane has
a line image, whereas projection from outside that plane is
injective. If the first target is $Y_i$ itself, the conclusion makes
$Y_i$ planar. The repeated first index then makes validity at that
center require
$t_i\ge2$, whereas a planar curve in a nonlinear group is projected
from outside its plane and has map degree one. This proves the claim.
For a valid center $p$, the line $pv$ consequently gives at least
\[
r_j=t_j-\mathbf1_{i=j},\qquad
r_k=t_k-\mathbf1_{i=k}
\]
distinct preimages other than $v$ on the respective curves. They can
be chosen generic on those curves by the original choice of $v$.
Birationality identifies the normalizations of the projective closures
of the curve and its plane image. These distinct generic smooth
preimages therefore give distinct normalization points, hence distinct
branches at the corresponding point of the plane image. Validity and
\eqref{geo:map-degree-comparison} imply
\[
r_j\ge t_j/2\ge d_j/(4e_\gamma),\qquad
r_k\ge t_k/2\ge d_k/(4e_\gamma).
\]
If the two plane images are distinct, B\'ezout bounds the sum of their
local multiplicity products at these distinct projected centers by
$d_jd_k$. If they agree, then $j=k$, and the residual multiplicity
is at least two: it is $t_j\ge2$ when $i\ne j$, and $t_i-1\ge2$
when all indices agree. Equation~\eqref{geo:polar-bound} bounds the
sum of squared residual multiplicities by $2d_j^2$.
Both cases give \eqref{geo:triple-center-bound}.
Discard once more groups of mass $W_{p,\gamma}\le KMe_\gamma$.
Their contribution is $O(NME)=o(N^2)$.
In a larger group, an invalid ordered triple must repeat an index
whose map degree is at most two. Such an index has mass at most
$4CMe_\gamma$ by \eqref{geo:curve-mass} and
\eqref{geo:map-degree-comparison}. The weight of invalid triples is
at most
\[
3W_{p,\gamma}\sum_{t_i\le2}n_i^2
\le 12CMe_\gamma W_{p,\gamma}^2.
\]
Choose $K$ so this is at most half of $W_{p,\gamma}^3$.
If the remaining pair mass were at least $\varepsilon N^2$, H\"older
in each row and then in the centers would imply
\[
\sum_{p,\gamma}\frac{1}{e_\gamma^2}
\sum_{(i,j,k)\text{ valid}}n_i n_j n_k
\ge \frac{\varepsilon^3N^4}{2E^2}.
\]
Indeed $\sum_\gamma W_{p,\gamma}^3/e_\gamma^2\ge
(\sum_\gamma W_{p,\gamma})^3/E^2$, and the sum of the row cubes is
at least their total cubed divided by $N^2$.
On the other hand, \eqref{geo:triple-center-bound} bounds this expression
by $C\sum_{i,j,k}n_i n_j n_k\le CN^3$.
For $d=3$ we have $E=\delta N^{1/3}$, so $N^4/E^2$ exceeds $N^3$
by an unbounded factor. This contradiction proves the proposition.
\end{proof}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/secants.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/sparse-cones.tex ====
\section{The sparse-cones assertion}\label{sec:sparse-cones}
We retain the contradiction hypotheses, including the
lower-dimensional induction bounds and their proper-flat
consequences. For $p\in\R^d$ and $y\ne p$, write $\pi_p(y)=[y-p]$.
A directional curve family is a finite family of curves in
$\PP^{d-1}$; membership means membership in its union, and its
total degree is the sum of the component degrees.
\begin{theorem}[Sparse cones]\label{sc:theorem}
Along a sequence with $M=o(A)$, there cannot be families $C_p$,
one for each $p\in P$, of irreducible projective curves, each
spanning projective dimension at most two, such that
\[
\deg C_p\le E=\delta N/A,\qquad \delta\to0,
\]
and $1-o(1)$ of the unordered pairs $\{p,q\}$ satisfy
$\pi_p(q)\in C_p$ or $\pi_q(p)\in C_q$.
\end{theorem}
Suppose these data exist. Apply the results of Section~\ref{sec:profiles}.
The positive-mass core alternative is already contradictory.
We must treat a common window and two widely separated windows.
The selected covered incidences retain the global terminal deletion and
the light-line restriction in Proposition~\ref{prof:pair-selection}.
For the common-window rank estimate we will also use auxiliary graphs
of arbitrary ordered pairs $(p,q)$ with $p\ne q$ on the same selected point sets.
That estimate will be proved without a coverage or light-line hypothesis.
We use affine charts of the label map
\begin{equation}\label{sc:label-map}
\psi(x,y)=(x,\pi_x(y)).
\end{equation}
For each finite family under discussion, these charts may be chosen to
contain all actual labels and to meet every component image.
The map and its pullbacks have bounded degree on these charts;
constant factors in testing degree fit inside a chosen open
plateau. A \emph{dense graph} means at least a fixed positive
fraction of the ordered product of the two selected pieces.
Assertions about dense graphs always include arbitrary further
fixed positive-density restrictions and subsequences.
\subsection{Product images and rank in a common window}
Consider two pieces with width $s$ and the same limiting profile,
or the outermost pool allowed by Proposition~\ref{prof:pair-selection}.
Use $D_i,e_j,\sigma$ from~\eqref{prof:profile-functions}.
For an ordered graph $\Gamma$ on these pieces, write
$H(T)=H_{\psi(\Gamma)}(T)$ for the restriction rank of its labels.
We first make the passage from carrier pairs to product images precise.
The same construction will be used in the rank argument and, with one
fixed choice of parameters, at the outermost endpoint. Its last estimate
applies to every later choice of image subfamily.
\begin{lemma}[Retained products and their image degree]
\label{sc:retained-products}
Fix a common positive-dimensional plateau after $j$ cuts, of dimension
$k=d-j0$, one may discard $o(n_x)$ source points and
$o(n_y)$ target points. Write $m_x,m_y$ for the remaining counts, so
$m_x=(1-o(1))n_x$ and $m_y=(1-o(1))n_y$. One may then discard carrier
pairs of total assigned product mass $o(m_xm_y)$, with the following conclusions.
Each remaining point is assigned to its unique smooth carrier in the
union of the two physical families. Repeated carriers are pooled within
each family, and every flat carrier with positive assigned mass is real.
There are common physical equations for the whole original union whose Jacobian
has full codimension rank at these points. A single polynomial
$g_{\rm ph}$, a linear combination of maximal Jacobian minors, is nonzero
at every retained point. The equations and this test have degrees
$O(T_s(\tau))$.
When the two factors are the same pool, the point deletion and the
assignment may be taken to be the same in both roles.
Write $\mathcal R$ for the retained ordered carrier pairs and
\[
Z_{X,Y}=\overline{\psi(X\times Y)}\qquad((X,Y)\in\mathcal R).
\]
Every $Z_{X,Y}$ has dimension $2k$, and at a general pair the connecting
direction is transverse to both physical tangent spaces. Let $U$ be the
reduced union of the distinct $Z_{X,Y}$. Then
\begin{equation}\label{sc:retained-image-upper}
\deg U\le e_j^2\exp(o(s)).
\end{equation}
For any subfamily $\mathcal J$ of these distinct images, including one
chosen after further equations have been chosen, its represented carrier
pairs have normalized assigned mass at most
\begin{equation}\label{sc:retained-image-mass}
\frac{1}{m_xm_y}
\sum_{\substack{(X,Y)\in\mathcal R\\Z_{X,Y}\in\mathcal J}}n_Xn_Y
\le \frac{\deg\bigl(\bigcup_{Z\in\mathcal J}Z\bigr)}{e_j^2}
\exp(\varepsilon s+o(s)).
\end{equation}
Here $n_X,n_Y$ are the assigned masses after the point deletions.
\end{lemma}
\begin{proof}
Choose fixed times $\tau_{\rm eq}<\tau_{\rm test}<\tau$ between the start
of the plateau and $\tau$. Use the earlier part of this interval for
the equation choices in Proposition~\ref{prof:regularity}, leaving the
strict gap up to $\tau_{\rm test}$ for its minor and proper-cut tests at
the sample points. Apply its union version to the two physical carrier families.
It removes the negligible point sets excluded by its regularity conclusion
and supplies common equations for the whole union. At each remaining
point there is now a unique smooth carrier. Denote by $g_{\rm ph}$ the
common combination of maximal minors whose zeros were removed in this
step. Discard every such point
whose carrier is a nonreal flat, using the degree-one proper sections in
the last paragraph of that proposition. This costs another
$o(n_x)+o(n_y)$ points. The source and target assignments are now
unambiguous. Each assigned carrier belongs to the point's own original
piece path: that path already supplies a carrier through the point, and
uniqueness in the full union identifies it with the assigned member.
For two copies of the same pool take the union of the two negligible
point deletions in both roles; the resulting assignment is the same.
Extend the retained assignments by assigning each deleted point to a
containing carrier of its original piece before any later product tests,
using the same extension in both roles for a common pool. Product testing
on the original sets then retains the present assignments under restriction, and its
$o(n_xn_y)$ pair loss is also $o(m_xm_y)$. Pool equal retained carriers
within each of the two lists and omit members with zero mass.
All these choices have been made inside the interval ending at $\tau$,
which gives the stated degree bound.
The pooled budgets, with each original piece still supplying the bound
for its own points, give
\begin{equation}\label{sc:retained-carrier-weights}
\begin{gathered}
\max\left\{\sum_X\deg X,\sum_Y\deg Y\right\}\le e_j\exp(o(s)),\\
\frac{n_X}{m_x}\le\frac{\deg X}{e_j}\exp(o(s)),\qquad
\frac{n_Y}{m_y}\le\frac{\deg Y}{e_j}\exp(o(s)).
\end{gathered}
\end{equation}
Indeed, the mass of a carrier in one piece is at most
$\deg(X)(N/e_j)\exp(o(s))$, and pooling $\exp(o(s))$ pieces changes
this by only $\exp(o(s))$. The remaining point counts are still
$N\exp(-o(s))$. A flat has degree one, so its number and its normalized
weight satisfy the hypotheses of Lemma~\ref{geo:generic-depth} with
$w=s$ and $e=e_j$. The flat members are real by the preceding deletion.
Apply that lemma now with the fixed $\varepsilon$. Let
$\mathcal Y_X$ be its target list for $X$, and set
$\mathcal R=\{(X,Y):Y\in\mathcal Y_X\}$. The removed carrier pairs
have normalized product weight $o(1)$, hence account for $o(m_xm_y)$
actual pairs. This deletion includes pairs generically tangent at either
endpoint. Thus the target tangent projects injectively at a general pair,
and the first coordinate of $\psi$ records all source tangent directions;
the product image has dimension $2k$. The preimages of a general
$2k$-fold linear section of that image are isolated away from the base
locus of the bounded-degree map on $X\times Y$. The isolated-intersection
form of B\'ezout therefore gives
$\deg Z_{X,Y}\le C_d\deg X\deg Y$, and
\eqref{sc:retained-image-upper} follows from
\eqref{sc:retained-carrier-weights}.
We prove the uniform subfamily estimate while keeping these same lists.
Images belonging to different source carriers are distinct: the closure
of the first projection of $Z_{X,Y}$ is $X$. Fix one source $X$ and one
of its distinct images $Z$. To identify its source fibers, take its
closure $\widehat Z\subset X\times\PP^{d-1}$ before restricting the
direction coordinate to our affine chart. Localizing the ideal of the
rational image at $\C(X)$ identifies the generic fiber with the closure
of the projection of $Y$ from the generic source point. This fiber is
geometrically integral, since it is the image closure of the geometrically
integral variety $Y_{\C(X)}$. After restricting $X$ to a dense open,
the projective family is flat with geometrically integral fibers of a
constant degree $d_Z$; this uses generic flatness, geometric integrality after
shrinking, and constancy of the Hilbert polynomial in a flat projective
family \cite[Tags~052A, 0559, 0C0E, and 0B9T]{stacksproject}.
We may also require that projection of $Y$ from each $x$ in this open set
has dimension $k$, by generic target transversality.
Its closed image is then a $k$-dimensional irreducible subvariety of the
$k$-dimensional integral fiber, so it equals the whole fiber. Make these
restrictions simultaneously for the finite image and target lists.
Thus all targets with $Z_{X,Y}=Z$ have the same complete projected image
at a common general $x\in X$. Write $t_x(Y)$ for their generic map degrees.
The fixed list bound says
\[
\sum_{Y:\,(X,Y)\in\mathcal R,\ Z_{X,Y}=Z}t_x(Y)
\le \exp(\varepsilon s).
\]
For a general $x$, the point-projection formula gives
$\deg Y-\operatorname{mult}_xY=t_x(Y)d_Z$.
The multiplicity is zero unless $X=Y$. In that case $x$ is smooth and
the multiplicity is one; a coincident flat pair was deleted as tangential.
Consequently $\deg Y\le2t_x(Y)d_Z$ for every target in this sum.
Choose $k$ general affine hyperplanes in the source coordinates. They
meet $X$ in $\deg X$ points of the preceding open set. Then choose $k$
general hyperplanes in the direction coordinates; on each complete fiber
they give $d_Z$ points, with multiplicity. The choices can be made so
all these points lie in the selected label chart and avoid intersections
between distinct images. The resulting mixed section of $Z$ therefore
has $\deg X\,d_Z$ points. The $2k$ blockwise hyperplanes are also affine
linear equations in the full label space. Their homogenizations restrict
to linear equations on the ordinary projective closure of $Z$, where all
the counted affine points are isolated intersections. The isolated-intersection
form of B\'ezout bounds their total multiplicity by the ordinary degree,
even if the same equations have additional components at infinity.
Applying this to a reduced image subfamily and summing the preceding
map-degree bound gives
\[
\sum_{\substack{(X,Y)\in\mathcal R\\Z_{X,Y}\in\mathcal J}}
\deg X\deg Y
\le C_d\exp(\varepsilon s)
\deg\bigl(\bigcup_{Z\in\mathcal J}Z\bigr).
\]
Multiplying the two weight bounds in
\eqref{sc:retained-carrier-weights} proves
\eqref{sc:retained-image-mass}. No further generic-depth deletion is
made when $\mathcal J$ is chosen.
\end{proof}
\begin{lemma}[Common-window label rank]\label{sc:common-rank}
Let $\Gamma\subset\{(p,q)\in S_x\times S_y:p\ne q\}$ be any dense graph
on the selected pieces or pool; its pairs need not be covered by the $C_p$.
For its labels, at an interior testing time
before the last cut,
\begin{equation}\label{sc:label-rank}
H(T_s(b))\ge
\sigma(b)^2\min\left(1,\frac{T_s(b)}{D_1D_2}\right)
\exp(-o(s)).
\end{equation}
The convention is a lower limit after dividing the logarithm
by $s$; in particular it permits any prescribed fixed positive
logarithmic tolerance, uniformly for dense subgraphs.
\end{lemma}
\begin{proof}
On the initial full-dimensional interval,
Lemma~\ref{prof:product-testing}, or its two successive
full-dimensional no-capture arguments, forces the testing-degree
envelope of a dense label graph to be the whole label space.
Its rank is comparable to $T^{2d-1}$. Since $D_1D_2\ge T^2$
there, this is at least the right side of~\eqref{sc:label-rank}.
On a positive-dimensional plateau after $j\ge1$ cuts put
$k=d-j$. Choose a physical regularity time between the start of this
plateau and the current testing time $b$.
When $k0$. When $k=d-1$, apply
Proposition~\ref{prof:regularity} to the union of the two physical
families, discard its rank-failure and nonreal-flat points, and assign each
survivor to its unique carrier from its original path. Use the same
supported extension to the original point sets before product testing,
and pool equal retained carriers with their assigned masses. The fixed
tangent-flat argument and the proper-flat
cap then discard carrier pairs generically tangent at either endpoint.
In both cases the point and carrier-pair losses remove only a negligible
fraction of the graph, and every remaining complete product image
$\overline{\psi(X\times Y)}$ has dimension $2k$.
Product testing forces these complete images into the testing-degree
envelope at almost all remaining graph pairs.
For this fixed envelope, choose one irreducible envelope component
containing each distinct complete image occurring at those surviving
pairs. Let the pairs with that image inherit its choice. Group all
envelope components by dimension and count each surviving pair in the
group of its chosen component; components receiving no pairs remain in
the degree of their group. Every chosen component has dimension at
least $2k$, so some dimension $h\ge2k$ group carries a positive
fraction of the graph. Write $a$ for its degree and $\Gamma'$ for
the graph portion it carries.
If $h\ge2k+1$, the Hilbert bounds give
\[
H(T)\gtrsim aT^h,\qquad
H_{\psi(\Gamma')}(T')\lesssim a(T'+1)^h.
\]
Borrow~\eqref{sc:label-rank} from a time just before the cut
starting this plateau. The required right side grows with
exponent at most $2k+1$ within the plateau, so growth with
exponent $h$ suffices. Endpoint approximation costs an
arbitrarily small fixed multiple of $s$ in the logarithm.
It remains to bound $a$ when $h=2k$. Each image assigned to this group
is an irreducible $2k$-fold contained in its chosen irreducible
$2k$-dimensional envelope component, and therefore equals that component.
If $k=d-1$, necessarily $j=1$, and the projection of a generic
target hypersurface from a generic source point fills direction
space. For each source carrier $X$ the product image is thus
$X\times\PP^{d-1}$ in these label coordinates. A positive
mass of pairs requires a positive source mass. The carrier
mass budget therefore gives
\[
a\gtrsim e_1\exp(-o(s))=D_1\exp(-o(s)).
\]
The resulting rank $D_1T^{2d-2}\exp(-o(s))$ is sufficient:
on this plateau $T\le D_2$ to exponential accuracy and
\[
D_1^2T^{2d-2}\min(1,T/(D_1D_2))
\le D_1T^{2d-2}.
\]
Now suppose $k0$, and retains the
terminal deletion and the light-line restriction. Let $k$ be the
dimension of the final open plateau, $j=d-k$, and let $\beta=b_j<1$
be its starting time. Balance gives
\begin{equation}\label{sc:outer-budgets}
1\le k\max\{\beta,1+b_1+b_2\}.
\end{equation}
Such choices exist because $b_1+b_2<0$. Reserve the interval
$(\beta,\tau)$ for the finitely many physical regularity choices,
use $t_0$ for the image envelope and $t_1$ for the common label equations,
and reserve $(t_1,t_2)$ for the later pullback tests. Now fix
\[
0<\varepsilon<\tfrac14(t_1-t_0).
\]
Also fix the endpoint approximation and the logarithmic tolerances in
the rank argument below smaller than a quarter of both positive gaps
$t_0-\beta$ and $t_0-(1+b_1+b_2)$.
Apply Lemma~\ref{sc:retained-products} to the two copies of this pool,
with $\tau$ and $\varepsilon$ just fixed. Use its same-pool deletion
and assignment, and retain its common physical equations and
$g_{\rm ph}$ for the full original union of final-plateau carriers.
When $k\ge2$, make one further point deletion before fixing the final
product family. The carriers whose affine spans have dimension at most
$k+1$ number at most $e_j\exp(o(s))$, and each lies in a proper flat
containing at most $B^{k+1+o(1)}$ sample points. The points assigned to
all these carriers therefore have total mass at most
\[
B^{d-2k}B^{k+1+o(1)}=B^{d-k+1+o(1)}=o(n_0).
\]
Discard them in both roles. No such deletion is made when $k=1$.
Write $S$ for the resulting pool, $n=|S|$, and $\mathcal C$ for its
positive-mass physical carriers. Then
\begin{equation}\label{sc:outer-retained-pool}
n=(1-o(1))n_0\ge(1-o(1))N\sqrt\delta,
\qquad n=N\exp(-o(s)).
\end{equation}
Restrict the returned carrier pairs to $\mathcal C\times\mathcal C$
and call this fixed set $\mathcal R$. Its omitted assigned product mass
is still $o(n^2)$. The old assigned weights only decreased in the last
point deletion, while the normalizing point count changed by a factor
$1-o(1)$. Thus \eqref{sc:retained-image-mass} remains valid, with the
same $\varepsilon$ and an adjusted $o(s)$, for every subfamily of the
distinct images
\[
Z_{X,Y}=\overline{\psi(X\times Y)},\qquad (X,Y)\in\mathcal R.
\]
Let $U$ be their reduced union. This is the final product-image family
for this endpoint; we will only take subfamilies of it. In particular
$\deg U\le e_j^2\exp(o(s))$. Restrict $\Gamma_0$ to $S\times S$ and
to the carrier pairs in $\mathcal R$, and call the result $\Gamma$.
The point and carrier-pair deletions together cost $o(n_0^2)$ pairs, so
$|\Gamma|\gtrsim n^2$.
When $k=1$, the unique carrier of each surviving target is its globally
assigned terminal curve from Proposition~\ref{prof:pair-selection}.
Indeed, the final plateau is then after the $(d-1)$st cut. The curve
chosen in that global assignment belongs to the full original carrier
union used by the common physical equations, so uniqueness at the target
identifies it with the current carrier. If that global assignment was
omitted because its chosen curve was a nonreal line, uniqueness would
make the current carrier that line, and the nonreal-flat point deletion
has removed the point. Thus no globally unassigned target remains in
this case.
\begin{lemma}[Regular product images at the endpoint]
\label{sc:outer-regularity}
For the fixed $\mathcal R$ and $U$ above, there is a subfamily
$\mathcal R_{\rm sm}\subseteq\mathcal R$ whose omitted assigned product
mass is $o(n^2)$, and one system of label equations of degree at most
$B^{2-c}$ for some fixed $c>0$, with the following properties.
The equations contain every complete image $Z_{X,Y}$ for
$(X,Y)\in\mathcal R_{\rm sm}$. Outside $o(n^2)$ further actual pairs
assigned to $\mathcal R_{\rm sm}$, their common zero locus is smooth of
dimension $2k$ at the label, the product map has differential rank
$2k$, and the connecting direction is transverse to both physical
tangent spaces. If $k\ge2$, the two projected tangent spaces are also
unequal there. The equations and every polynomial test used for these
actual-pair conclusions have degree at most $B^{2-c}$.
\end{lemma}
\begin{proof}
Put $T_i=T_s(t_i)$ and form
\[
V=\operatorname{Env}_{T_0}(U).
\]
For each distinct image $Z\subset U$, choose once an irreducible component
$W(Z)$ of $V$ containing the whole image. Every assigned pair represented
by $Z$ inherits that choice. Since $\dim Z=2k$, a chosen component has
dimension at least $2k$; equality implies $W(Z)=Z$.
We first show that the images assigned to larger components represent
only $o(n^2)$ product mass. Otherwise, after taking a subsequence, some
dimension $h\ge2k+1$ group represents a fixed positive normalized mass.
Form an auxiliary graph $\Lambda_h$ from all actual ordered pairs in
those assigned products, omitting the diagonal where $\psi$ is undefined.
Disjointness of the assignments makes its size equal to that product
mass before the omission, and the diagonal has at most $n$ pairs.
Thus $\Lambda_h$ is dense in $S\times S$. This graph is independent of
the covered graph $\Gamma$; the arbitrary-graph scope of
Lemma~\ref{sc:common-rank} applies to it.
Every label of $\Lambda_h$ lies in the chosen dimension-$h$ component
containing its complete product image.
Write $a_h$ for the total degree of the dimension-$h$ component group of
$V$, including components receiving no images. Its upper Hilbert bound
at an earlier degree $T'$ controls $H_{\psi(\Lambda_h)}(T')$, while its
lower envelope bound gives $H_V(T_0)\gtrsim a_hT_0^h$. Borrow the
common-window label rank at a time just before $\beta$, with the fixed
endpoint tolerance chosen above. If $\beta=-1$ and no earlier testing
degree is at least one, use the rank-one boundary convention in
Lemma~\ref{sc:common-rank}; then all $j$ earlier cut times equal $-1$
and the required boundary rank is one to exponential accuracy.
On the final plateau $\sigma(b)=e_jT_s(b)^k$. Propagating with
$h\ge2k+1$ therefore gives
\[
H_V(T_0)\ge e_j^2T_0^{2k}
\min\left\{\frac{T_0}{T_s(\beta)},
\frac{T_0}{D_1D_2}\right\}
\exp(-\xi s-o(s)),
\]
where the fixed $\xi>0$ can be smaller than both gaps specified after
\eqref{sc:outer-time-choice}. The two factors have normalized logarithms
$t_0-\beta$ and $t_0-(1+b_1+b_2)$, respectively, so the lower bound has
a strict positive margin. But envelope equality and the upper Hilbert
bound on the pure $2k$-dimensional family $U$ give
\[
H_V(T_0)=H_U(T_0)\le C e_j^2T_0^{2k}\exp(o(s)).
\]
This contradiction proves the claimed product-mass deletion.
Let $\mathcal I$ be the distinct images left after that deletion.
Each is an actual irreducible $2k$-dimensional component of the single
locus $V$, defined by equations of degree at most $T_0$; larger components
elsewhere in $V$ are kept in those equations. Also
$\deg\mathcal I\le\deg U\le e_j^2\exp(o(s))$.
Apply Lemma~\ref{poly:regularity} to this pure component family at degree
$T_1$. Its equations vanish on the whole family $\mathcal I$.
The exceptional image subfamily $\mathcal E$ has total degree at most
\[
C\deg(\mathcal I)\frac{T_0}{T_1}
\le e_j^2\exp(-(t_1-t_0)s+o(s)).
\]
Use \eqref{sc:retained-image-mass} for this particular subfamily of the
already fixed $U$. Its represented normalized pair mass is at most
\[
\exp(-(t_1-t_0-\varepsilon)s+o(s))=o(1).
\]
Here the same $\varepsilon$-lists chosen before $U$ are used; no new
generic-depth deletion depends on $\mathcal E$. Let
$\mathcal R_{\rm sm}$ consist of the carrier pairs represented by
$\mathcal I\setminus\mathcal E$. The two image deletions have omitted
only $o(n^2)$ assigned product mass.
The regularity lemma supplies a common polynomial $g$ of degree $O(T_1)$,
a linear combination of maximal Jacobian minors, which is nonzero on each
image in $\mathcal I\setminus\mathcal E$. The single rational pullback
$g\circ\psi$ has a cleared numerator of degree $O(T_1)$ on the chosen
charts, nonidentically zero on every carrier pair in $\mathcal R_{\rm sm}$.
Product testing, with its
internal times in $(t_1,t_2)$, removes its actual zeros at a cost of
$o(n^2)$ pairs. At every surviving label the common equations are locally
a smooth $2k$-fold. They still vanish on all of $\mathcal I$, including
its exceptional components.
It remains to test the two tangent injectivities at actual pairs.
Write $f_a$ for the common physical equations chosen before $\tau$, and
$v=q-p$. At a point $r\in S$, their Jacobian has kernel $T_r$, the tangent
space of its unique carrier. Thus $v\notin T_r$ exactly when at least one
polynomial $\nabla f_a(r)\mathbin{\cdot}v$ is nonzero. These tests have
degree $O(T_s(\tau))$ in $(p,q)$. On every retained carrier pair the
source collection and the target collection each contain a generically
nonzero test, by the fixed generic-depth deletion. For each endpoint,
choose a generic constant linear combination nonzero on every retained
product. Product testing removes its actual zeros at cost $o(n^2)$.
The target injectivity, together with the source coordinate of $\psi$,
gives differential rank $2k$; the source injectivity is retained
separately for the secant step.
If $k\ge2$, every remaining physical carrier spans dimension at least
$k+2$ by the preceding carrier deletion. Equality of the two projected tangent
spaces at a general retained pair would put both carriers in a common
$(k+1)$-flat by Lemma~\ref{geo:secants}, which is impossible. This
inequality also has a bounded-degree test using the same physical
equations. Put $c'=d-k$ and write $a_i(r)=\nabla f_i(r)$. On the
full-rank transverse locus the row vectors
\[
(a_i(r)\mathbin{\cdot}v)a_j(r)
-(a_j(r)\mathbin{\cdot}v)a_i(r)
\]
span the $(c'-1)$-dimensional annihilator of $T_r+\mathbb Cv$.
Indeed, they lie in that annihilator, and choosing one row with nonzero
value on $v$ expresses every row combination annihilating $v$ in their
span. The two projected tangent spaces are unequal exactly when the
combined row spans for $r=p,q$ have rank at least $c'$. Their
$c'\times c'$ minors are polynomials of degree $O(T_s(\tau))$. Choose a generic
combination nonzero on every retained product, and apply product testing
once more to remove its actual zeros. All these tests fit in
the interval reserved below $t_2$. Since $s=\log B$ and $t_2<1$, their
degrees and the common label-equation degrees are at most $B^{2-c}$ for
some fixed $c>0$. This proves the lemma.
\end{proof}
Restrict $\Gamma$ by the carrier-pair and actual-pair deletions in
Lemma~\ref{sc:outer-regularity}. It still has $\gtrsim n^2$ pairs.
Fix a center $p\in S$. If a component $\gamma$ of $C_p$ is not contained
in the specialized common label equations, choose one such equation
nonzero on $\gamma$. B\'ezout bounds its intersections with $\gamma$ by
$O(\deg\gamma\,B^{2-c})$. Summing over these components gives
$O(EB^{2-c})$ directions. Each supporting physical line has at most
$B^{o(1)}$ sample points, by the light-line restriction on $\Gamma$.
The corresponding target fraction is therefore at most
\[
C\frac{EB^{2-c+o(1)}}{n}
\le C\sqrt\delta\,B^{-c+o(1)}=o(1).
\]
This is uniform in $p$, so discarding all these incidences costs $o(n^2)$.
For a remaining component $\gamma\subset C_p$, take a marked pair
$(p,q)$ in the graph with $\pi_p(q)\in\gamma$. Let $X,Y$ be its unique
physical carriers. Near this label the common equations give a smooth
$2k$-fold $W$, and $\psi:X\times Y\to W$ has full differential rank at
$(p,q)$. The analytic inverse function theorem therefore gives a local
biholomorphism. On the affine open containing $q$ where $\pi_p$ is
regular, consider the algebraic preimage $Y\cap\pi_p^{-1}(\gamma)$.
Because $\psi$ records the source coordinate, its local inverse identifies
the reduced analytic germ of this preimage at $q$ with the germ of
$\gamma$ at $\pi_p(q)$. That germ is pure one-dimensional. Algebraic and
analytic local dimensions agree over $\C$, so an algebraic irreducible
component of the preimage containing any selected inverse branch is a
curve through $q$. Let $C$
be its closure in $Y$. The selected branch projects nonconstantly to
$\gamma$; hence $\overline{\pi_pC}=\gamma$, since $\gamma$ is irreducible.
If $k=1$, this curve is the target carrier $Y$ itself. The identity
with the global terminal assignment established above now gives
$\overline{\pi_pY}=\gamma\subset C_p$, exactly an incidence removed by
Proposition~\ref{prof:pair-selection}. This resolves $k=1$.
Suppose $k\ge2$. For each remaining marked pair over $\gamma$, choose
one such irreducible lift, and pool repeated physical curves. Retain its
carrier pair $(X,Y)\in\mathcal R_{\rm sm}$. The physical minor test
$g_{\rm ph}(q)$ and the label and tangent tests are nonzero at its marked
point, so their restrictions are nonzero on the lift and hold on a
nonempty open part of it. Choose one general direction on $\gamma$, common to this finite
family, avoiding the exceptional loci, branch values, and images of
intersections between distinct lifts. Each lift then contributes its
generic map degree in distinct roots, and roots from distinct lifts are
also distinct.
There can be at most one such root in total. At their common label the
same label equations are smooth of dimension $2k$ and contain every
complete product image attached to these lifts. All products use the
same source carrier $X$: it is the unique member of the full physical
family at $p$. If two roots $q',z'$ were distinct, the first product
would have full differential rank at $(p,q')$, and the complete second
product would also lie in the same local label system. The
particular-pair assertion of Lemma~\ref{geo:secants} would then give
\[
\overline{T_pX}\subseteq\overline{T_{q'}Y}
\quad\text{in }\mathbb C^d/\mathbb C(q'-p).
\]
Both spaces have dimension $k$ by the two tangent-injectivity tests, so
they would be equal, contrary to the tangent-inequality test. Hence
\begin{equation}\label{sc:lift-map-degree}
\sum_{C\text{ distinct chosen lifts over }\gamma}
\deg(C\longrightarrow\gamma)\le1.
\end{equation}
Finally, each lift loses at most half its physical degree under projection.
If $p\in C\subset Y$, uniqueness for the full original physical family
at $p$ forces $Y=X$. The carrier $X$ is smooth at $p$, and the marked
point $q\in C$ has $q-p\notin T_pX$ by the source tangent test.
Corollary~\ref{poly:tangent-projection} therefore gives
$\operatorname{mult}_pC\le\deg C/2$. If $p\notin C$, the multiplicity
is zero. In both cases the point-projection formula yields
\[
\deg\gamma\,\deg(C\to\gamma)
=\deg C-\operatorname{mult}_pC\ge\tfrac12\deg C.
\]
Together with \eqref{sc:lift-map-degree}, this bounds the total degree of
the lifts over $\gamma$ by $2\deg\gamma$. Every remaining target in the
row lies on a chosen lift. The physical curve bound in
Lemma~\ref{poly:separators}, summed over $\gamma\subset C_p$, bounds their
number by $CEM$. But
\[
\frac{EM}{n}\le C\sqrt\delta\,\frac MA\longrightarrow0.
\]
Every remaining row thus has $o(n)$ partners, contradicting the surviving
$\gtrsim n^2$ graph. This resolves the common outermost endpoint.
To treat separated windows, we next bound the projected degree at the
actual source centers.
\input{sections/depth}
\subsection{Rank propagation for separated windows}
Let $v$ be the source width and $s$ the target width, with
$v/s\to0$ or $v/s\to\infty$. Both are $o(\log B)$.
Their limiting normalized profile $(b_i)$ is the same, but
$T_s,D_i,e_j,\sigma$ below refer only to the target window.
The source and target piece sizes are respectively
$N\exp(-o(v))$ and $N\exp(-o(s))$; we do not replace the
former error by $o(s)$ when $v\gg s$.
Use the retained target set and fixed plateau assignments in
Proposition~\ref{dep:projected-degree}. Its final one-dimensional
assignment is the persistent global terminal assignment, after the
negligible omission of globally unassigned targets. Apply the proposition
for the finite batch of plateaux and logarithmic tolerances needed in an
argument, take the union of its negligible incidence deletions, and apply
row Markov once. Call the remaining source centers typical. This set is chosen independently
of the later fixed density threshold $\rho>0$; only the large-index
threshold may depend on $\rho$. Thus the same typical centers serve
every later subcollection of fixed positive target mass, including one
chosen after the center and a testing-degree envelope. On a plateau of
dimension $l=d-j$, every retained individual carrier projects with
dimension $l$, and such a subcollection has distinct projected degree at least
\begin{equation}\label{sc:projected-degree-interface}
(e_j/R)\exp(-o(s)).
\end{equation}
The permitted depth denominators are
\begin{align}
R&=D_1 &&\text{always},\label{sc:R-first}\\
R&=B\exp\left(-s\sum_{i>j}b_i\right)
&&\text{if }v/s\to0,\label{sc:R-narrow}\\
R&=B\exp(-2s)
&&\text{if }v/s\to\infty,\ b_{j+1}>0,
\ l0$ through all plateaux up to the final
endpoint, except possibly the final one-dimensional
plateau when the center window is narrower. The constant
may be decreased finitely many times during propagation.
The assertion is needed only at fixed interior testing
times and their one-sided limiting endpoints.
\end{lemma}
\begin{proof}
On the initial interval target no-capture, applied to the
pullback of a direction polynomial, gives rank comparable
to $T^{d-1}$. Its ratio to $\sigma(b)T/A$ is
\[
\frac{A}{T^2}=\exp(-2bs).
\]
This has a strict positive margin near the first cut,
since $b_1<0$.
On a plateau of dimension $l$, consider the testing-degree envelope of
the directions to the current row subset. For each fixed assigned target
carrier whose projection is not contained in this envelope, a generic
linear combination of its pulled-back equations is a proper cut on that
carrier. The combination can be chosen simultaneously for the finite
carrier list. Use a slightly later interior time for the fixed pullback
and pooling costs. Every counted target on such a carrier lies in the
cut. The individual-cut conclusion
of Proposition~\ref{prof:regularity} therefore removes only $o(|P_y|)$
such targets, uniformly in the center and the envelope. Hence the
complete projection of the assigned carrier is contained in the envelope
at almost all remaining counted targets.
For this fixed envelope, choose one irreducible component containing each
distinct projected carrier occurring at those targets, and let the targets
inherit the choice for their projected carrier. Group all envelope
components by dimension, counting targets by these choices; components
receiving no targets remain in the degree of their group. Some group of
dimension $h\ge l$ carries a fixed positive fraction of the target mass.
If $h>l$, that group borrows the preceding bound with growth exponent
$h\ge l+1$. This preserves the required growth exponent of $\sigma T$
on the plateau. Approximate the preceding endpoint closely enough that
the lost logarithmic tolerance is a small fraction of the existing $c$.
If $h=l$, each projected carrier assigned to this group equals its chosen
envelope component, since both are irreducible of dimension $l$.
The projected degree lower bound~\eqref{sc:projected-degree-interface}
and the envelope Hilbert bound give
\[
H(T)\gtrsim T^l e_j/R\,\exp(-o(s)).
\]
Relative to $\sigma T/A=e_jT^{l+1}/A$, this supplies the
ratio $A/(RT)$, to exponential accuracy. It suffices to
have a strict negative normalized logarithm for
$R D_{j+1}/A$, the worst point at the next endpoint.
The three choices give, respectively,
\begin{equation}\label{sc:strict-margins}
b_1+b_{j+1},\qquad
-\sum_{i>j+1}b_i,\qquad
b_{j+1}-2.
\end{equation}
The first is strictly negative on the hypersurface
plateau, by $b_1+b_2<0$, and whenever $b_{j+1}\le0$.
For wider centers all remaining cases have
$b_{j+1}>0$ and $l0$, the second choice has a strict margin when
$l\ge2$, since its sum includes a positive later entry.
Only $l=1$ gives zero rather than a strict margin.
There are at most $d$ distinct cut times. Choose all
endpoint approximations and fixed logarithmic tolerances
smaller than a sufficiently small fraction of the
finitely many positive margins just displayed. Decrease
$c$ when necessary. This completes the propagation.
The degree bounds and prior rank statements quantify
over every dense restriction, so choosing a different
dimension group or dense subset for different centers
does not change the argument.
\end{proof}
For directions covered by $C_p$ the upper bound is
\begin{equation}\label{sc:row-upper}
H(T)\le CE(T+1).
\end{equation}
If the strict margin reaches the last endpoint, choose a
fixed time just below it with $\sigma(b)/N\ge\exp(-c s/2)$
to exponential accuracy. Equations~\eqref{sc:strict-rank}
and~\eqref{sc:row-upper} then have a ratio tending to
infinity, at least $\delta^{-1}\exp(c s/3)$ for large
indices. This contradicts the positive density of
covered rows.
\subsection{The final curve plateau for narrower centers}
At the remaining zero-margin endpoint, all but $o(|P_y|)$ of the covered
targets in each typical row will have their fixed assigned terminal curve
project onto a component of the covering family $C_p$. These are exactly
the incidences excluded by the global terminal deletion.
The only remaining case has $v/s\to0$ and a final
one-dimensional target plateau, $b_{d-1}0$, $T_0=T_s(b_0)$, and
$T_1=T_s(b_{\rm eq})=T_0\exp(\eta s)$. Fix $0<\varepsilon<\eta$.
Include this tolerance for the final plateau in the finite depth batch,
and use the typical-center set for the combined batch. Its deletion is
made before the envelopes below are chosen. Apply the preceding rank
argument with this combined finite batch; its bounds then hold for every
fixed positive-density restriction. Only now, for each typical center, let
\[
V_p=\operatorname{Env}_{T_0}(C_p)
\]
be the envelope of the entire directional family, not
just of its observed incidences. Its testing rank is
at most $CE(T_0+1)$.
First, a component group of $V_p$ of dimension $h\ge2$
cannot contain covered targets of mass at least $\rho|P_y|$ for any
fixed $\rho>0$. Indeed take that actual subset and borrow its strict rank
bound from just before the final plateau. The Hilbert bounds for
the envelope group propagate this with exponent
$h\ge2$, exactly the required exponent of $\sigma T$
on a one-dimensional plateau. At $b_0$ sufficiently
close to $b_d$ it contradicts~\eqref{sc:row-upper}.
If their target mass were not $o(|P_y|)$ uniformly over the typical
centers, a subsequence would supply one such fixed $\rho$ and contradict
this bound on the same typical-center set. Thus we may discard all
actual labels on the larger components at a cost of $o(|P_y|)$ per row,
including labels at their intersections with curves;
we do not try to cut those intersections by equations
of possibly excessive degree.
Let $\mathcal F_p$ be the family of every one-dimensional irreducible
component of $V_p$, whether or not it is already represented by an
assigned target projection. We will impose common equations on this
whole family so that they also contain any covering component through a
surviving label. The envelope Hilbert lower bound for its entire
one-dimensional component group and the rank upper bound imply
\begin{equation}\label{sc:last-family-degree}
\deg\mathcal F_p=O(E).
\end{equation}
We next place the projection of the fixed assigned terminal curve in
this family. For each such carrier $Y$ whose projection is not contained
in $V_p$, a generic linear combination of the pulled-back envelope
equations is a proper cut on $Y$. Choose the combination simultaneously
for the finite carrier list, and use a slightly later interior time for
the fixed pullback and pooling costs. Every covered target assigned to
one of these carriers lies in that cut. The individual-cut conclusion of
Proposition~\ref{prof:regularity} therefore removes only $o(|P_y|)$ such
targets, uniformly in $p$. This applies to the persistent global
assignment fixed before the depth bounds, including targets at physical
carrier intersections.
At every remaining covered target its assigned projection is contained in $V_p$.
It has dimension one because we retained the depth proof's deletion of
every dimension-dropping incidence. An irreducible component of $V_p$
containing this projected curve cannot have higher dimension: it would
also contain the observed label, which was excluded from every such
component. Hence the assigned projection is itself a member of
$\mathcal F_p$.
The components of $\mathcal F_p$ are isolated components of the equations
of degree $T_0$ defining $V_p$, even though that locus
may also have higher-dimensional components elsewhere.
Lemma~\ref{poly:regularity} gives equations of degree at most $T_1$
vanishing on the whole family $\mathcal F_p$, with generic full rank except on
components of total degree
\begin{equation}\label{sc:last-exceptional-degree}
O(E T_0/T_1)=O(\delta(N/A)\exp(-\eta s)).
\end{equation}
These exceptional components carry negligible target
mass. This assertion uses the dense-subcollection
uniformity of the depth lemma: on this plateau
\[
\frac{e_{d-1}}{R}
=\frac{N/D_d}{B\exp(-b_d s)}=\frac NA.
\]
Thus any subcollection carrying a fixed positive fraction of $|P_y|$
has projected degree at least
$(N/A)\exp(-\varepsilon s)$ for the fixed tolerance selected before
the depth deletion. Compare
with~\eqref{sc:last-exceptional-degree}. The ratio is
$O(\delta\exp(- (\eta-\varepsilon)s))\to0$.
Indeed, take the physical assigned carriers whose projections belong to
the exceptional family. Their distinct projected degree is bounded by
that family's degree, so they cannot carry a fixed positive fraction of $|P_y|$.
If their mass were not $o(|P_y|)$ uniformly over typical centers, one fixed
positive density along a subsequence would contradict this comparison.
This applies to the family selected by the envelope and its equations,
without changing the fixed target assignment or the earlier depth deletion.
The identity $RD_d=A$ explains the room in this comparison: the projection
depth and the last physical cut together cost $A$, while regularity supplies
the strict gap $\eta-\varepsilon>0$ in the logarithmic degree scale.
One must not instead compare
$(N/A)\exp(-o(s))$ directly with $\delta N/A$; the latter
comparison would be unjustified for arbitrarily slowly
vanishing $\delta$.
The regularity lemma supplies one polynomial $g_p$ of degree $O(T_1)$,
a linear combination of maximal Jacobian minors, which is nonzero on
every retained projected component. Its pullback to each corresponding
fixed assigned physical curve is therefore a proper rational test, with
cleared numerator of degree $O(T_1)$. Apply the individual-cut conclusion
of Proposition~\ref{prof:regularity}, using the reserved time
$b_{\rm test}$, to remove the zeros of these numerators at $o(|P_y|)$
targets. This is uniform in the center. At every surviving label
$g_p\ne0$, so the common equations have full rank there.
At a surviving covered label, take a component $\gamma$
of $C_p$ through it. Since $C_p\subset V_p$, this curve
lies in a component of $V_p$. That component cannot have
larger dimension, by the preceding exclusion. Hence
$\gamma$ is a member of $\mathcal F_p$. The common
equations have full rank at the label, so this member
equals the projected member of $\mathcal F_p$ through the same label.
That member is the projection of the persistent assigned terminal curve.
Thus this curve projects onto $\gamma\subset C_p$, exactly the terminal incidence
removed in Proposition~\ref{prof:pair-selection}, a
contradiction.
\begin{proof}[Proof of Theorem~\ref{sc:theorem}]
The profile-pair selection exhausts the possibilities.
A positive core is impossible by its isolation degree.
The common-window rank bound contradicts coverage except
at the outermost endpoint, where the lift argument gives
the contradiction. For separated windows, strict row
rank propagation contradicts coverage except on the
final narrow-center curve plateau, which the preceding
argument resolves by common regularity and terminal
deletion. Thus the proposed almost-complete sparse-cone
coverage cannot exist.
\end{proof}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//sections/sparse-cones.tex ====
==== BEGIN The-higher-dimensional-Erdos-distinct-distances-conjecture//references.bib ====
@misc{stacksproject,
author = {{The Stacks Project Authors}},
title = {The Stacks Project},
year = {2026},
url = {https://stacks.math.columbia.edu},
note = {Cited by permanent tags; consulted September 23 and October 1, 2026.
\href{https://stacks.math.columbia.edu/tag/0578}{Tag 0578},
\href{https://stacks.math.columbia.edu/tag/00OQ}{Tag 00OQ},
\href{https://stacks.math.columbia.edu/tag/00NO}{Tag 00NO},
\href{https://stacks.math.columbia.edu/tag/00NQ}{Tag 00NQ},
\href{https://stacks.math.columbia.edu/tag/00NA}{Tag 00NA},
\href{https://stacks.math.columbia.edu/tag/02JN}{Tag 02JN},
\href{https://stacks.math.columbia.edu/tag/062F}{Tag 062F},
\href{https://stacks.math.columbia.edu/tag/052A}{Tag 052A},
\href{https://stacks.math.columbia.edu/tag/0559}{Tag 0559},
\href{https://stacks.math.columbia.edu/tag/0C0E}{Tag 0C0E}, and
\href{https://stacks.math.columbia.edu/tag/0B9T}{Tag 0B9T}}
}
@book{hatcher2002,
author = {Hatcher, Allen},
title = {Algebraic Topology},
publisher = {Cambridge University Press},
year = {2002},
url = {https://pi.math.cornell.edu/~hatcher/AT/AT.pdf},
note = {\href{https://pi.math.cornell.edu/~hatcher/AT/AT.pdf}{Author's electronic edition}}
}
@article{erdos1946,
author = {Erd{\H{o}}s, P.},
title = {On sets of distances of {$n$} points},
journal = {The American Mathematical Monthly},
volume = {53},
number = {5},
pages = {248--250},
year = {1946},
doi = {10.1080/00029890.1946.11991674},
url = {https://users.renyi.hu/~p_erdos/1946-03.pdf},
note = {\href{https://users.renyi.hu/~p_erdos/1946-03.pdf}{Original article}}
}
@article{guthkatz2015,
author = {Guth, Larry and Katz, Nets Hawk},
title = {On the {Erd{\H{o}}s} distinct distances problem in the plane},
journal = {Annals of Mathematics},
volume = {181},
number = {1},
pages = {155--190},
year = {2015},
doi = {10.4007/annals.2015.181.1.2},
eprint = {1011.4105},
archivePrefix = {arXiv},
primaryClass = {math.CO},
url = {https://annals.math.princeton.edu/2015/181-1/p02},
note = {\href{https://doi.org/10.4007/annals.2015.181.1.2}{Published article};
\href{https://arxiv.org/abs/1011.4105v3}{arXiv:1011.4105v3, 28 June 2011}.
Theorem numbering in the text refers to this arXiv version}
}
@article{szemereditrotter1983,
author = {Szemer{\'e}di, Endre and Trotter, Jr., William T.},
title = {Extremal problems in discrete geometry},
journal = {Combinatorica},
volume = {3},
number = {3--4},
pages = {381--392},
year = {1983},
doi = {10.1007/BF02579194},
url = {https://link.springer.com/article/10.1007/BF02579194},
note = {\href{https://doi.org/10.1007/BF02579194}{Published article}}
}
@article{walsh2020,
author = {Walsh, Miguel N.},
title = {The polynomial method over varieties},
journal = {Inventiones mathematicae},
volume = {222},
number = {2},
pages = {469--512},
year = {2020},
doi = {10.1007/s00222-020-00975-6},
eprint = {1811.07865},
archivePrefix = {arXiv},
primaryClass = {math.AG},
url = {https://link.springer.com/article/10.1007/s00222-020-00975-6},
note = {\href{https://doi.org/10.1007/s00222-020-00975-6}{Published article};
\href{https://arxiv.org/abs/1811.07865v2}{arXiv:1811.07865v2, 12 June 2020}}
}
@book{fulton1998,
author = {Fulton, William},
title = {Intersection Theory},
series = {Ergebnisse der Mathematik und ihrer Grenzgebiete. 3.~Folge},
volume = {2},
edition = {Second},
publisher = {Springer},
year = {1998},
doi = {10.1007/978-1-4612-1700-8},
url = {https://link.springer.com/book/10.1007/978-1-4612-1700-8},
note = {\href{https://doi.org/10.1007/978-1-4612-1700-8}{Second edition}}
}
@book{hartshorne1977,
author = {Hartshorne, Robin},
title = {Algebraic Geometry},
series = {Graduate Texts in Mathematics},
volume = {52},
publisher = {Springer-Verlag},
address = {New York},
year = {1977},
doi = {10.1007/978-1-4757-3849-0},
url = {https://link.springer.com/book/10.1007/978-1-4757-3849-0},
note = {\href{https://doi.org/10.1007/978-1-4757-3849-0}{Publisher's edition}}
}
@misc{tidoryuzakharov2026,
author = {Tidor, Jonathan and Yu, Hung-Hsun Hans and Zakharov, Dmitrii},
title = {The {Erd{\H{o}}s} distinct distances problem in {$\mathbb{R}^3$}},
howpublished = {Preprint, arXiv:2608.14454v1 [math.CO]},
year = {2026},
eprint = {2608.14454},
archivePrefix = {arXiv},
primaryClass = {math.CO},
doi = {10.48550/arXiv.2608.14454},
url = {https://arxiv.org/abs/2608.14454v1},
note = {\href{https://arxiv.org/abs/2608.14454v1}{Version 1, submitted 14 August 2026}}
}
@article{ClarksonEdelsbrunnerGuibasSharirWelzl1990,
author = {Clarkson, Kenneth L. and Edelsbrunner, Herbert and Guibas, Leonidas J. and Sharir, Micha and Welzl, Emo},
title = {Combinatorial complexity bounds for arrangements of curves and spheres},
journal = {Discrete \& Computational Geometry},
volume = {5},
pages = {99--160},
year = {1990},
doi = {10.1007/BF02187783}
}
@article{AronovPachSharirTardos2004,
author = {Aronov, Boris and Pach, J{\'a}nos and Sharir, Micha and Tardos, G{\'a}bor},
title = {Distinct distances in three and higher dimensions},
journal = {Combinatorics, Probability and Computing},
volume = {13},
number = {3},
pages = {283--293},
year = {2004},
doi = {10.1017/S0963548304006091}
}
@article{SolymosiVu2008,
author = {Solymosi, J{\'o}zsef and Vu, Van H.},
title = {Near optimal bounds for the {Erd{\H{o}}s} distinct distances problem in high dimensions},
journal = {Combinatorica},
volume = {28},
number = {1},
pages = {113--125},
year = {2008},
doi = {10.1007/s00493-008-2099-1}
}
@article{BardwellEvansSheffer2019,
author = {Bardwell-Evans, Sam and Sheffer, Adam},
title = {A reduction for the distinct distances problem in {$\mathbb{R}^d$}},
journal = {Journal of Combinatorial Theory, Series A},
volume = {166},
pages = {171--225},
year = {2019},
doi = {10.1016/j.jcta.2019.02.010},
eprint = {1705.10963},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1705.10963v2},
note = {\href{https://doi.org/10.1016/j.jcta.2019.02.010}{Published article};
\href{https://arxiv.org/abs/1705.10963v2}{arXiv:1705.10963v2, 6 April 2019}.
Numbered locators in the text refer to this arXiv version}
}
@misc{AksoyYazici2020Withdrawn,
author = {Aksoy Yazici, Esen},
title = {{Erd{\H{o}}s} distance problem in {$\mathbb{R}^d$}},
year = {2020},
eprint = {2002.01248},
archivePrefix = {arXiv},
note = {Withdrawn by the author on February 12, 2020},
url = {https://arxiv.org/abs/2002.01248}
}
@article{chardin1989,
author={Chardin, Marc},
title={Une majoration de la fonction de {Hilbert} et ses cons\'equences pour l'interpolation alg\'ebrique},
journal={Bulletin de la Soci\'et\'e Math\'ematique de France},
volume={117}, number={3}, pages={305--318}, year={1989},
doi={10.24033/bsmf.2124},
url={https://numdam.org/articles/10.24033/bsmf.2124/}
}
@article{chardinphilippon1999,
author={Chardin, Marc and Philippon, Patrice},
title={R\'egularit\'e et interpolation},
journal={Journal of Algebraic Geometry}, volume={8}, number={3},
pages={471--481}, year={1999},
url={https://webusers.imj-prg.fr/~marc.chardin/publications/textes/11.RI.pdf},
note={See also the erratum, Journal of Algebraic Geometry 11(3) (2002), 599--600}
}
@article{chardinphilippon2002erratum,
author={Chardin, Marc and Philippon, Patrice},
title={Erratum to ``R\'egularit\'e et interpolation''},
journal={Journal of Algebraic Geometry}, volume={11}, number={3},
pages={599--600}, year={2002},
url={https://webusers.imj-prg.fr/~marc.chardin/publications/textes/11.Err.pdf}
}
@article{walsh2023,
author = {Walsh, Miguel N.},
title = {Concentration estimates for algebraic intersections},
journal = {American Journal of Mathematics},
volume = {145}, number = {2}, pages = {435--475}, year = {2023},
eprint = {1906.05843}, archivePrefix = {arXiv}, primaryClass = {math.AG},
url = {https://arxiv.org/abs/1906.05843v2},
note = {\href{https://arxiv.org/abs/1906.05843v2}{arXiv:1906.05843v2, 26 December 2019}.
Section locators in the text refer to this arXiv version}
}
@article{szekely1997,
author = {Sz{\'e}kely, L{\'a}szl{\'o} A.},
title = {Crossing Numbers and Hard {Erd\H{o}s} Problems in Discrete Geometry},
journal = {Combinatorics, Probability and Computing},
volume = {6}, number = {3}, pages = {353--358}, year = {1997},
doi = {10.1017/S0963548397002976},
url = {https://www.cs.tau.ac.il/~michas/szekely.pdf}
}
@incollection{ajtai1982crossing,
author = {Ajtai, Mikl{\'o}s and Chv{\'a}tal, Va{\v{s}}ek and Newborn, Monroe M. and Szemer{\'e}di, Endre},
title = {Crossing-Free Subgraphs},
booktitle = {Theory and Practice of Combinatorics},
series = {North-Holland Mathematics Studies}, volume = {60},
pages = {9--12}, publisher = {North-Holland}, year = {1982},
doi = {10.1016/S0304-0208(08)73484-4}
}
@book{leighton1983,
author = {Leighton, Frank Thomson},
title = {Complexity Issues in {VLSI}: Optimal Layouts for the Shuffle-Exchange Graph and Other Networks},
publisher = {MIT Press}, year = {1983},
isbn = {9780262121040},
url = {https://mitpress.mit.edu/9780262121040/complexity-issues-in-vlsi/}
}
@article{stonetukey1942,
author = {Stone, A. H. and Tukey, John W.},
title = {Generalized ``sandwich'' theorems},
journal = {Duke Mathematical Journal},
volume = {9}, number = {2}, pages = {356--359}, year = {1942},
doi = {10.1215/S0012-7094-42-00925-6}
}
@article{elekeskaplansharir2011,
author = {Elekes, Gy{\"o}rgy and Kaplan, Haim and Sharir, Micha},
title = {On lines, joints, and incidences in three dimensions},
journal = {Journal of Combinatorial Theory, Series A},
volume = {118}, number = {3}, pages = {962--977}, year = {2011},
doi = {10.1016/j.jcta.2010.11.008},
eprint = {0905.1583}, archivePrefix = {arXiv}, primaryClass = {math.CO},
url = {https://arxiv.org/abs/0905.1583}
}
@article{guthkatz2010kakeya,
author = {Guth, Larry and Katz, Nets Hawk},
title = {Algebraic methods in discrete analogs of the {Kakeya} problem},
journal = {Advances in Mathematics},
volume = {225}, number = {5}, pages = {2828--2839}, year = {2010},
doi = {10.1016/j.aim.2010.05.015},
eprint = {0812.1043}, archivePrefix = {arXiv}, primaryClass = {math.CO},
url = {https://arxiv.org/abs/0812.1043}
}
@article{elekessharir2011,
author = {Elekes, Gy{\"o}rgy and Sharir, Micha},
title = {Incidences in Three Dimensions and Distinct Distances in the Plane},
journal = {Combinatorics, Probability and Computing},
volume = {20}, number = {4}, pages = {571--608}, year = {2011},
doi = {10.1017/S0963548311000137},
eprint = {1005.0982}, archivePrefix = {arXiv}, primaryClass = {cs.CG},
url = {https://arxiv.org/abs/1005.0982}
}
@article{beck1983,
author = {Beck, J{\'o}zsef},
title = {On the lattice property of the plane and some problems of {Dirac}, {Motzkin} and {Erd\H{o}s} in combinatorial geometry},
journal = {Combinatorica},
volume = {3}, number = {3--4}, pages = {281--297}, year = {1983},
doi = {10.1007/BF02579184}
}
@article{kaminskikanelbelovteicher2008,
author={Kaminski, J. Y. and Kanel-Belov, A. and Teicher, M.},
title={Trisecant lemma for nonequidimensional varieties},
journal={Journal of Mathematical Sciences},
volume={149}, number={2}, pages={1087--1097}, year={2008},
doi={10.1007/s10958-008-0047-7},
eprint={0712.3878}, archivePrefix={arXiv},
url={https://arxiv.org/abs/0712.3878}
}
@article{ran1991,
author={Ran, Ziv},
title={The (dimension + 2)-secant lemma},
journal={Inventiones Mathematicae},
volume={106}, pages={65--71}, year={1991},
doi={10.1007/BF01243904},
url={https://link.springer.com/article/10.1007/BF01243904}
}
@inproceedings{elekestoth2005,
author = {Elekes, Gy{\"o}rgy and T{\'o}th, Csaba D.},
title = {Incidences of not-too-degenerate hyperplanes},
booktitle = {Proceedings of the Twenty-First Annual Symposium on Computational Geometry},
year = {2005},
pages = {16--21},
doi = {10.1145/1064092.1064098},
url = {https://doi.org/10.1145/1064092.1064098},
note = {\href{https://doi.org/10.1145/1064092.1064098}{Published article}}
}
==== END The-higher-dimensional-Erdos-distinct-distances-conjecture//references.bib ====