\documentclass[11pt]{article} \usepackage[a4paper,margin=2.5cm]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{enumitem} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref} % ---------------------------------------------------------------- theorems \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{convention}[theorem]{Convention} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} % ---------------------------------------------------------------- macros \newcommand{\R}{\mathbb{R}} \newcommand{\Sph}{\mathrm{S}} % sphere S(c,t); S(c,U) union over radii U \newcommand{\Bis}{\mathrm{H}} % perpendicular bisector H(p,q) \newcommand{\Dist}{\mathcal{D}} % set of pairwise distances \newcommand{\Bg}{\mathrm{Big}} \newcommand{\rk}{\operatorname{rank}} \newcommand{\aff}{\operatorname{aff}} \newcommand{\dirsp}{\operatorname{dir}} \newcommand{\Hyp}{\mathrm{Hyp}} \newcommand{\Sm}{\mathrm{Sm}} \newcommand{\Good}{\mathrm{Good}} \newcommand{\Cov}{\mathrm{Cov}} \newcommand{\Ex}{\mathrm{Ex}} \newcommand{\Ty}{\mathrm{Ty}} \newcommand{\Lst}{L^{\ast}} % L_{k*}(D+2) \newcommand{\kst}{k^{\ast}} \newcommand{\smin}{\sigma_{\min}} \newcommand{\dd}[2]{|#1#2|} % distance |xy| \newcommand{\binomc}[2]{\tbinom{#1}{#2}} \newcommand{\eps}{\varepsilon} \title{Subexponential bounds for distinct-distance subsets:\\ $f_d(n)=2^{O_n(\sqrt d\,\log d)}$ for every fixed $n$\\[4pt] \large (an affirmative answer to Erd\H{o}s Problem \#1088, subject to expert verification)} \author{% Will Howe \and Grant Huffman \and Jensen Kohlmeyer \and Liam Kruer\\[4pt] \footnotesize The mathematics was developed by AI agents (Claude, Anthropic) in sessions directed by the authors;\\ \footnotesize see the statement on AI assistance and verification in Section~\ref{sec:ai}.} \date{Draft manuscript, November 10, 2026} \emergencystretch=2em \begin{document} \maketitle \begin{abstract} For integers $n\ge 3$ and $d\ge 1$ let $f_d(n)$ be the least $m$ such that every set of $m$ points in $\R^d$ contains $n$ points whose $\binom n2$ pairwise distances are all distinct. Erd\H{o}s asked whether $f_d(n)=2^{o(d)}$ for every fixed $n$; the classical bound is exponential in $d$. We prove that $f_d(n)\le 2^{C_n\sqrt d\,\log(d+2)}$ for every fixed $n\ge 3$, which would answer the question affirmatively. The main new tool is a rank--rectangle theorem (Theorem~LR): if every entry of a real matrix of rank $r$ equals one of $k$ prescribed functions, each depending only on the row or only on the column, then there is a rectangle of relative size $2^{-O(k^3\sqrt{r}\log r)}$ in each direction on which a single one of these functions describes all entries. Its proof combines Rothvoss's hyperplane-rounding proof of Lovett's bound with a rescaling at the largest gap and a cleaning step. The geometric part of the argument is a downward induction over ``levels'' (rainbow sets $S$ together with a ground set $W$ of points extending $S$), with a polynomial-method kill step at each level and a structural class-count statement proved by repeated use of Theorem~LR. \emph{Verification status:} every step was written out and checked by independent AI referee passes. The whole argument has also been formalized in Lean~4 with Mathlib. The formalization proves the statement \texttt{Erdos1088.erdos\_1088} of the Google DeepMind \emph{formal-conjectures} repository verbatim, using only Lean's standard axioms (Section~\ref{sec:lean}). No human expert has reviewed the informal argument yet. See Section~\ref{sec:ai}. \end{abstract} \tableofcontents % ==================================================================== \section{Introduction}\label{sec:intro} % ==================================================================== \subsection{The problem} A finite set $A\subset\R^d$ is \emph{rainbow} if its $\binom{|A|}{2}$ pairwise distances are pairwise distinct (sets with at most two points are rainbow). A set $X$ is \emph{rainbow-$n$-free} if it contains no rainbow subset of size $n$. For $n\ge 3$ and $d\ge 1$ let $f_d(n)$ be the least $m$ such that every set of $m$ points of $\R^d$ contains a rainbow $n$-subset, and let \[ s_n(j):=\sup\{|X| : X\subset\R^{N}\text{ finite, rainbow-$n$-free, } \dim\aff X\le j\} \] (the ambient dimension $N$ is irrelevant). Then $f_d(n)=s_n(d)+1$, and $s_n(0)=1$. Erd\H{o}s asked whether $f_d(n)=2^{o(d)}$ for every fixed $n$; this is Problem~\#1088 on the Erd\H{o}s problems website~\cite{EP1088}.\footnote{Within the project the problem is also tracked under the identifier JSP-000905.} We prove that the answer is yes, with a much stronger quantitative bound. \begin{theorem}[Main Theorem]\label{thm:main-intro} For every fixed $n\ge 3$ there is a constant $C_n$ such that every set of more than $2^{C_n\sqrt d\,\log_2(d+2)}$ points of $\R^d$ contains $n$ points with all $\binom n2$ pairwise distances distinct. That is, $f_d(n)=2^{O_n(\sqrt d\log d)}=2^{o(d)}$. \end{theorem} \subsection{History} As recorded on the problem page~\cite{EP1088}, Erd\H{o}s and Straus showed $f_d(n)\le c_n^{\,d}$ for a constant $c_n$; the problem asks whether the exponential dependence on $d$ is necessary. In the other direction, $s$-distance sets with $s=\binom n2-1$ are rainbow-$n$-free, since a rainbow $n$-set needs $\binom n2$ distinct distances. For instance the $0/1$-vectors of weight $w$ in $\R^{d+1}$ lie in a $d$-dimensional affine subspace and determine only the distances $\sqrt{2i}$, $1\le i\le w$; with $w=\binom n2-1$ this gives $f_d(n)>\binom{d+1}{\binom n2-1}$ for $d+1\ge \binom n2 -1$. So $f_d(n)$ grows at least polynomially in $d$, with degree depending on $n$, and we are not aware of any super-polynomial lower bound. For $n=3$ the problem is classical and polynomial: a set is rainbow-$3$-free exactly when every three of its points span an isosceles triangle, where collinear triples with two equal distances count as (degenerate) isosceles triangles. Blokhuis~\cite{Blokhuis} proved that an isosceles set in $\R^d$ has at most $\binom{d+2}{2}$ points. His argument is purely metric, so it covers degenerate triples, and it gives $f_d(3)\le\binom{d+2}2+1$. For $n\ge 4$ we know of no bound of the form $2^{o(d)}$ in the literature before the present work. \subsection{The new tool: Theorem LR} The geometric part of our argument repeatedly produces matrices of the form $M[x,w]=|x-w|^2$, of rank at most $D+2$, in which every entry is ``explained'' by one of boundedly many simple causes. A typical cause is $|x-w|=|w-t|$ for a fixed point $t$, which depends only on the column $w$. Another is $|x-w|=|x-t|$, which depends only on the row $x$. A third is $|x-w|=d$ for a fixed number $d$. The tool that converts such a cover into geometric structure is the following rank--rectangle theorem (Theorem~\ref{thm:LR}). \medskip\noindent\textbf{Theorem LR (informal).} \emph{Let $M\in\R^{m\times n}$ have rank at most $r$, and let $\tau_1,\dots,\tau_k$ be functions on $[m]\times[n]$, each depending only on the row or only on the column. If every entry satisfies $M[x,w]=\tau_i(x,w)$ for some $i$, then there are $R\subseteq[m]$, $C\subseteq[n]$ and a single $i$ with $M=\tau_i$ on $R\times C$, $|R|\ge 2^{-L}m$ and $|C|\ge 2^{-L}n$, where $L=O(k^3\sqrt{r+2}\,\log(r+2))$.} \medskip For Boolean matrices this is the rectangle form of Lovett's bound~\cite{Lovett}, in Rothvoss's formulation~\cite{Rothvoss}. Our proof follows Rothvoss's hyperplane-rounding argument and adds two ingredients. The first is a normal form, obtained on a sub-rectangle of constant relative size, which allows us to rescale the matrix at its largest gap \emph{by a row function, a column function or a constant}. This keeps a margin even when the type values accumulate. The second is a cleaning step, the Gavinsky--Lovett lemma (Lemma~\ref{lem:GL}), applied to a Hadamard product, whose rank enters only logarithmically. \begin{remark}[possible independent interest; to be confirmed by experts]\label{rem:SS} The special case in which all types are column functions concerns \emph{$k$-listable} matrices, in which every column takes at most $k$ distinct values. Here Theorem~LR yields a column-constant submatrix of relative size $2^{-O(k^3\sqrt d\log d)}$ in each direction for rank-$d$ matrices (Corollary~\ref{cor:RQlist}). By Singer--Sudan~\cite[Prop.~2.3]{SingerSudan}, a parallel $k$-partitioned point--hyperplane configuration in $\R^d$ yields a $k$-listable matrix of rank at most $d$. A column-constant (``$1$-listable'') submatrix of it then yields a complete bipartite subgraph of the incidence graph, of proportional size up to a factor depending on $k$. Singer and Sudan write that ``the best bound we know for parallel 3-partitioned configurations is $2^{-\tilde O(d)}$'' (\cite{SingerSudan}, arXiv version~5, Section~1). As far as we can tell, Corollary~\ref{cor:RQlist} improves this to $2^{-O(\sqrt d\log d)}$ for every fixed $k$. Our literature search (summarised in Section~\ref{sec:concl}) was limited, and the observation follows from Rothvoss's proof in a few lines, so experts may regard it as known. The claim of improvement must be confirmed by experts before it is relied on. Theorem~LR does not bear on the log-rank conjecture, which would require $2^{-\mathrm{polylog}(d)}$. \end{remark} \subsection{Prior in-project work} This manuscript builds on earlier notes of a peer session in the same project~\cite{Peer}. Those notes recorded the problem, its literature and the lower-bound constructions above. They also contained polynomial-method ``peeling'' lemmas: a point all of whose distances to the rest of a set lie in a short list can be removed using a low-degree polynomial in the lifted coordinates $(|y|^2,y)$. Lemma~H below (Lemma~\ref{lem:H}) is a two-sided variant of those peeling lemmas, in which each pair needs to be ``killed'' from one side only, at the price of squaring the dimension. The present argument does not use the other results of those notes, which include reductions to prime sets and twin analyses. \subsection{Verification status} We state this plainly, because the result would resolve a problem of Erd\H{o}s and the argument is long. \begin{itemize}[leftmargin=2em] \item The mathematics was developed by AI agents (Claude, Anthropic) in sessions directed by the team. \item Each component was checked by at least one independent AI referee pass. These passes found and repaired one genuine gap, a threshold gap in the top-level argument (fix F1, incorporated in Section~\ref{sec:top}), together with a number of expository gaps, all addressed here. \item \textbf{Machine-checked.} The complete argument has been formalized in Lean~4 (Section~\ref{sec:lean}). The formal proof establishes the statement of Problem~\#1088 in the formal-conjectures repository verbatim. It depends only on the axioms \texttt{propext}, \texttt{Classical.choice} and \texttt{Quot.sound}, and it has no \texttt{sorry}. The formalization proves Theorem~LR with a weaker dependence on~$k$ than stated here; this suffices for the Main Theorem. \item \textbf{No human expert has reviewed the informal argument.} Theorem~LR is new and unpublished, and every later step depends on it. It is the component we most want checked by specialists. \item This manuscript consolidates the project notes. A few routine changes made in the consolidation, listed in Section~\ref{sec:ai}, have not themselves been refereed; among them are some explicit constants and the direct single-cap write-up of Theorem~R$^+$. \item The finite, threshold-free implications were also tested by computer in exact arithmetic. Because every threshold in the argument is astronomically large, such tests are sanity checks only and cannot test the asymptotic claims (Section~\ref{sec:concl}). \end{itemize} Until an expert check has been carried out, the Main Theorem should be regarded as a \emph{candidate} solution. \subsection{Organisation} Section~\ref{sec:structure} gives an overview of the proof, the linear order of dependencies and the threshold tower. Section~\ref{sec:prelim} collects the classical tools: John's theorem, Sheppard's formula, the cleaning lemma (with proof), Lemma~H, the Caro--Wei and K\"onig theorems, and the orthogonal split. Section~\ref{sec:LR} proves Theorem~LR. Section~\ref{sec:G1} proves the label lemma and its consequence~G1 for pairs with disjoint label sets. Section~\ref{sec:framework} sets up the level-configurations, the hereditary relative bound~HR and the kill step. Section~\ref{sec:top} treats the top three levels. Sections~\ref{sec:core} and~\ref{sec:slicing} prove the class-count statement at the lower levels: the Core Lemma and the Slicing Lemma. Section~\ref{sec:main} closes the induction and proves the Main Theorem. Section~\ref{sec:concl} contains concluding remarks and the computational sanity checks, and Section~\ref{sec:ai} the statement on AI assistance and the acknowledgements. % ==================================================================== \section{Structure of the proof}\label{sec:structure} % ==================================================================== Throughout, $n\ge 4$ is fixed; the case $n=3$ is Blokhuis's theorem. $X$ is a finite rainbow-$n$-free set of affine dimension at most $D\ge 1$, and $h:=s_n(\lfloor D/2\rfloor)$. The proof is a \emph{halving recursion}: we show \begin{equation}\label{eq:halving-intro} s_n(D)\;\le\;2^{C_n\sqrt D\log_2(D+2)}\,\bigl(s_n(\lfloor D/2\rfloor)+1\bigr)\qquad(D\ge 1), \end{equation} and iterating~\eqref{eq:halving-intro} gives $s_n(d)=2^{O_n(\sqrt d\log d)}$ (Lemma~\ref{lem:halving}). The quantity $h$ enters only through the \emph{orthogonal split} (Lemma~\ref{lem:OR}). If $R,C\subseteq X$ and $\langle x-x',w-w'\rangle=0$ for all $x,x'\in R$ and $w,w'\in C$, then one of $R,C$ has affine dimension at most $\lfloor D/2\rfloor$, so $\min(|R|,|C|)\le h$. Every rectangle produced by Theorem~LR in the geometric part ends in such an orthogonal split. \subsection{Levels} A \emph{level-$j$ configuration} (Definition~\ref{def:config}) is a triple $(S,W,\sigma)$. Here $S\subseteq X$ is a rainbow set with $|S|=j$, and $W\subseteq X\setminus S$ consists of points $x$ with $S\cup\{x\}$ rainbow. The number $\sigma$ is a \emph{cap}: every sphere centred at a point of $S$ meets $W$ in fewer than $\sigma$ points. The statement \begin{center} \textbf{Claim$(j)$:} every level-$j$ configuration with $\sigma\ge\smin$ has $|W|\le\Gamma_j\,\sigma$ \end{center} is proved by downward induction on $j$, from $j=n-2$ to $j=0$. Claim$(0)$, applied to $(\emptyset,X,\smin)$, gives $|X|\le\Gamma_0\smin$. Here $\Gamma_0=(D+2)^{O_n(1)}$ and $\smin=2^{O_n(\sqrt D\log D)}(h+1)$, which is~\eqref{eq:halving-intro}. \subsection{The induction step} Each step from Claim$(j+1)$ to Claim$(j)$ follows one pattern. \begin{enumerate}[label=(\roman*),leftmargin=2.2em] \item \emph{Kill step} (Lemma~\ref{lem:kill}, Theorem~\ref{thm:Rplus}). Each $b\in W$ receives a polynomial $F_b$ of bounded degree in the lifted coordinates $(|y|^2,y)$. Its factors are spheres about $b$ with the radii of the \emph{big} classes of $b$, together with some degenerate loci. Apart from at most $j^2\sigma$ points where a distance from $x$ to $S$ equals one from $b$ to $S$, each $x\ne b$ with $F_b(x)\ne 0$ extends $S\cup\{b\}$ to a rainbow set and lies in a small class of $b$ in the kill step. These extending points form a level-$(j+1)$ configuration and are few by Claim$(j+1)$. Caro--Wei and Lemma~H (a pair needs to be killed from one side only) then bound $|W|$. This works as long as every $b\in W$ has at most $K=O_n(1)$ big classes. \item \emph{Few big classes.} At the top levels $j\ge n-4$ this is not needed. If $b$ has two big classes, then $n-4$ points of $S$ serve as ``spread'' points: together with $b$ and an auxiliary point $a$ they form an $(n-2)$-set. A label-counting argument (G1) and Theorem~LR then show that the auxiliary points $a$ which are not killed are few (Section~\ref{sec:top}; this is Theorem~R$^+$, written out in full for a single cap). At the lower levels $j=r\le n-5$ there are not enough spread points. Instead we prove the class-count statement \textbf{E1$_r$}: every $b\in W$ has fewer than $K_r=12\cdot 6^{\,n-5-r}$ big classes (Theorem~\ref{thm:E1}). \item \emph{Proof of E1$_r$.} Suppose $b$ has $K_r$ big classes. We pass to a \emph{rainbow family}: centres $B\ni b$ and pairwise disjoint classes $C_k$ on which every point of $B$ has a constant distance, with all these constant labels distinct. The \emph{Slicing Lemma} (Section~\ref{sec:slicing}) adds one centre at a time and loses a factor $6$ in the number of classes. Its proof uses K\"onig's theorem, the relative bound HR and Theorem~LR. After $n-5-r$ slicing rounds there are $n-4-r$ centres and $12$ classes. The \emph{Core Lemma} (Section~\ref{sec:core}) shows that this is impossible, using two auxiliary points, G1, HR and three applications of Theorem~LR. \item \emph{Hereditary relative bound HR$_r$} (Lemma~\ref{lem:HR}). It is a direct consequence of Claim$(r+1)$: for $c\in W$, $V\subseteq W\setminus\{c\}$ and $\theta\ge\sigma$, at most $\Gamma'_r\theta$ points of $V$ lie in classes of $c$ that meet $V$ in fewer than $\theta$ points, after excluding the prescribed radii and bisectors in Lemma~\ref{lem:HR}. The explicit constant is $\Gamma'_r=\Gamma_{r+1}+r^2$. This is the only place where the induction hypothesis enters the proof of E1$_r$, and it turns ``$c$ has few heavy classes'' into a \emph{covering} statement, which is what the cleaning lemma needs. \end{enumerate} \subsection{Linear order of dependencies} The results are proved in the following order. Each item uses only earlier items, and none uses the statement it is proving (there is no circularity). \begin{enumerate}[label=\arabic*.,leftmargin=2em] \item Classical tools (Section~\ref{sec:prelim}). John's theorem and Sheppard's formula (cited); the cleaning lemma GL (proved); the Hadamard-product rank bound HP and the dimension count DIM (proved); Lemma~H (proved); Caro--Wei and K\"onig (cited); the orthogonal split OR (proved); the halving lemma (proved). \item Theorem~LR (Section~\ref{sec:LR}). Lemma~R (margin rounding), Lemmas~A and~B, Lemma~NF (normal form), then Theorem~LR, followed by Corollary~\ref{cor:RQlist}. \item The label lemma and G1 (Section~\ref{sec:G1}), from LR and OR. \item Configurations; Lemma~HR$_r$ and the kill Lemma~\ref{lem:kill}, both assuming Claim$(r+1)$ (Section~\ref{sec:framework}). \item Theorem~R$^+$: Claim$(j)$ for $j=n-2,n-3,\dots,\max(n-4,0)$ (Section~\ref{sec:top}), from G1, LR, GL, HP, OR, Lemma~H, Caro--Wei, DIM and the two-distribution Lemma~\ref{lem:twodist}. \item For $n\ge 5$: the Core Lemma (Section~\ref{sec:core}) and the Slicing Lemma (Section~\ref{sec:slicing}), each assuming HR$_r$; then Theorem~E1$_r$. \item The downward induction $\text{Claim}(r+1)\Rightarrow\text{HR}_r\Rightarrow\text{E1}_r\Rightarrow \text{Claim}(r)$ for $r=n-5,\dots,0$ (Section~\ref{sec:main}). \item The Main Theorem, from Claim$(0)$ and the halving lemma (Section~\ref{sec:main}). \end{enumerate} The induction over levels takes place at a fixed dimension $D$, and the only input from dimensions below $D$ is the finite number $h=s_n(\lfloor D/2\rfloor)$. The recursion~\eqref{eq:halving-intro} is therefore an ordinary induction on $D$. \subsection{The threshold tower} All constants depend only on $n$ and $D$, except $\smin$, which also depends on $h$. They are defined in the following order, and each definition uses only quantities defined before it (Section~\ref{sec:main} gives the details). \begin{enumerate}[label=(T\arabic*),leftmargin=2.6em] \item Type counts $k'$, $k_c(r)$, $k_{\mathrm{sl}}(r,p)$; the class counts $K_r$; their maximum $\kst$. These depend on $n$ only. \item $\Lst:=L_{\kst}(D+2)$ from Theorem~LR; then $\mu:=2^{\Lst}(h+1)$, $e:=2^{\Lst+1}(h+1)$, $e_A:=2^{\Lst+2}(h+1)$, and \[\smin:=2^{\Lst+2+2n}(h+1).\] So $\smin$ depends only on $n$, $D$ and $h$, and not on any $\Gamma$. \item $Q:=2^{44}n^4(D+2)^{8k'}$ and $\Gamma_{n-2}:=4(n-2)^2$; then $\Gamma_{n-3}$ and $\Gamma_{n-4}$ by~\eqref{eq:Gamma-top} (for $n=4$ these are $\Gamma_1,\Gamma_0$, and the tower ends here). \item For $r=n-5,n-6,\dots,0$, in this order: $\Gamma'_r:=\Gamma_{r+1}+r^2$, then the ratios $\theta_{\mathrm{rel}}$, $\eps$, $\hat M_{\mathrm{core}}$, $\theta_{\mathrm{sl}}$, $\hat m_p$ and ${\mathrm{ratio}}_r$ (all functions of $n$, $D$ and $\Gamma'_r$), and then $\Gamma_r$ by~\eqref{eq:Gamma-low}. \end{enumerate} Every $\Gamma_j$, $\Gamma'_r$ and ${\mathrm{ratio}}_r$ is a pure number, at most $(D+2)^{c_n}$, and does not depend on the cap $\sigma$. Every absolute error term occurring in the proofs ($\mu$, $e$, $e_A$, $2\cdot 4^{n-2}\mu+4$, $4^n\mu$, and $1$) is at most $\smin\le\sigma$. These are the two facts that allow the caps to vary freely inside the induction: Claim$(j+1)$ is applied with caps $\theta\ge\sigma$, $Q\sigma$ and ${\mathrm{ratio}}_r\sigma$, all of which are at least $\smin$. % ==================================================================== \section{Notation, conventions and classical tools}\label{sec:prelim} % ==================================================================== \subsection{Notation} For $x,y\in\R^D$ we write $\dd xy:=|x-y|$. For $c\in\R^D$ and $t>0$, $\Sph(c,t):=\{y:\dd yc=t\}$ is the sphere with centre $c$ and radius $t$, and for a set $U$ of positive reals $\Sph(c,U):=\bigcup_{u\in U}\Sph(c,u)$. For $p\ne q$, $\Bis(p,q):=\{y:\dd yp=\dd yq\}$ is the perpendicular bisector hyperplane. For a finite set $A$, $\Dist(A):=\{\dd xy: x\ne y\in A\}$ is its set of distances. If $A$ is rainbow then $|\Dist(A)|=\binom{|A|}2$. If $c$ is a point and $V$ a set, a \emph{class of $c$ in $V$} is a nonempty set $V\cap\Sph(c,t)$ with $t>0$. Two spheres about the same centre with different radii are disjoint, so the classes of $c$ in $V$ partition $V\setminus\{c\}$. The \emph{lifted coordinates} of $y\in\R^D$ are $(|y|^2,y_1,\dots,y_D)$. Every sphere equation $\dd yc^2-t^2=|y|^2-2\langle y,c\rangle+|c|^2-t^2$ and every bisector equation $\dd yp^2-\dd yq^2=-2\langle y,p-q\rangle+|p|^2-|q|^2$ is an affine function of the lifted coordinates. Since an affine isometry changes neither distances nor affine dimension, we may and do assume that a set of affine dimension at most $D$ lies in $\R^D$. \begin{convention}[rectangles and rounding]\label{conv:rounding} A \emph{rectangle} of a matrix with row set $A$ and column set $B$ is a product $A'\times B'$ with $A'\subseteq A$ and $B'\subseteq B$. Every rectangle produced below is nonempty, and its size bounds are real inequalities: a conclusion $|A'|\ge 2^{-L}|A|$ with $2^{-L}|A|<1$ just says that $A'\ne\emptyset$. In the cleaning lemma, ``half'' means at least $|A|/2$ (hence at least $\lceil |A|/2\rceil$). Whenever a bound on a set $Z$ is deduced from a bound on a half $Z''\subseteq Z$, we use $|Z|\le 2|Z''|$. \end{convention} \subsection{Two classical facts used in the rounding lemma} \begin{theorem}[John~\cite{John}; see also~\cite{Ball}]\label{thm:John} If $K\subset\R^s$ is a compact convex body that is symmetric about $0$ and has nonempty interior, then there is an ellipsoid $E$ centred at $0$ with $E\subseteq K\subseteq\sqrt s\,E$. \end{theorem} \begin{theorem}[Sheppard's formula~\cite{Sheppard}; see also~\cite{GW}]\label{thm:Sheppard} Let $u,v\in\R^s$ be unit vectors with $\langle u,v\rangle=a$ and let $g\sim N(0,I_s)$. Then $\Pr[\langle g,u\rangle\ge0\text{ and }\langle g,v\rangle\ge0]=\tfrac12-\tfrac{\arccos a}{2\pi} =\tfrac14+\tfrac{\arcsin a}{2\pi}$. \end{theorem} Consequently this probability is at least $\tfrac14$ if $a\ge 0$. If $a\le -b$ with $0\le b\le 1$, it is at most $\tfrac14-\tfrac{\arcsin b}{2\pi}\le\tfrac14(1-\tfrac{2b}{\pi})$, because $\arcsin b\ge b$. \subsection{Rank tools} \begin{lemma}[Hadamard products, HP]\label{lem:HP} For matrices $A,B$ of the same shape, $\rk(A\circ B)\le\rk A\cdot\rk B$, where $\circ$ is the entrywise product. \end{lemma} \begin{proof} Write $A=\sum_{i\le\rk A}a_ib_i^{T}$ and $B=\sum_{j\le\rk B}c_jd_j^{T}$. Then $A\circ B=\sum_{i,j}(a_i\circ c_j)(b_i\circ d_j)^{T}$. \end{proof} \begin{lemma}[distance matrices]\label{lem:distrank} Let $x_1,\dots,x_m,w_1,\dots,w_{m'}\in\R^D$ and let $f,g$ be real functions on the index sets. The matrix $[\,\dd{x_i}{w_j}^2-f(i)-g(j)\,]_{i,j}$ has rank at most $D+2$. \end{lemma} \begin{proof} It equals $(|x_i|^2-f(i))\mathbf 1^{T}+\mathbf 1(|w_j|^2-g(j))^{T}-2[\langle x_i,w_j\rangle]$, a sum of matrices of rank at most $1$, $1$ and $D$. \end{proof} In particular, each of the following matrices has rank at most $D+2$: $[\dd xa^2-v^2]$ for a constant $v$; $[\dd xa^2-v(a)^2]$ for a column function $v$; and $[\dd xa^2-\dd xs^2]$ for a fixed point $s$ (take $f(x)=\dd xs^2$). By Lemma~\ref{lem:HP}, a Hadamard product of $k$ such matrices has rank at most $(D+2)^k$. \begin{lemma}[cleaning lemma, GL; Gavinsky--Lovett~\cite{GavinskyLovett}, cf.~{\cite[Lemma 4.7]{HMST}}] \label{lem:GL} Let $B$ be a matrix over a field, with row set $A$ ($|A|=m$) and column set $B_0$ ($|B_0|=n$), and with $\rk B\le R$ for some $R\ge 1$. Suppose $B$ has at most $mn/(16R)$ nonzero entries. Then there are $A''\subseteq A$ and $B''\subseteq B_0$ with $|A''|\ge 7m/8$, $|B''|\ge n/2$ and $B=0$ on $A''\times B''$. \end{lemma} \begin{proof} Call a column \emph{light} if it has at most $m/(8R)$ nonzero entries. If $c$ columns are heavy then $c\,m/(8R)0\}$ and $Q^-:=\{(x,w):N_{xw}<0\}$, and suppose $|Q^+|\ge\delta mn$ with $0<\delta\le\frac12$. Put $T:=\lceil\pi K\sqrt s\,\ln(2/\delta^2)\rceil$. Then there are $X'\subseteq[m]$ and $Y'\subseteq[n]$ with \[ |X'|\ge\tfrac\delta2 4^{-T}m,\qquad |Y'|\ge\tfrac\delta24^{-T}n,\qquad |(X'\times Y')\cap Q^-|\le\delta|X'||Y'|. \] \end{lemma} \begin{proof} Let $s_0:=\rk N$. Then $1\le s_0\le s$, since $N$ has nonzero entries. Write $N_{xw}=\langle u_x,v_w\rangle$ with $u_x,v_w\in\R^{s_0}$, where the $u_x$ span $\R^{s_0}$. The body $K_0:=\operatorname{conv}\{\pm u_x\}$ is symmetric with nonempty interior. By Theorem~\ref{thm:John} there is an ellipsoid $E$ with $E\subseteq K_0\subseteq\sqrt{s_0}E$. Choose a linear map $A$ with $A(E)=s_0^{-1/4}B$, where $B$ is the unit ball, and replace $u_x$ by $Au_x$ and $v_w$ by $A^{-T}v_w$. This preserves all inner products, and now $s_0^{-1/4}B\subseteq K_0\subseteq s_0^{1/4}B$. Hence $|u_x|\le s_0^{1/4}$. Moreover $v_w\ne0$, because $N_{xw}\ne0$. The point $z:=s_0^{-1/4}v_w/|v_w|$ lies in $K_0$, so \[ s_0^{-1/4}|v_w|=\langle z,v_w\rangle\le\max_x|\langle u_x,v_w\rangle|\le K, \] that is, $|v_w|\le Ks_0^{1/4}$. For the unit vectors $\hat u_x,\hat v_w$ we get $|\langle\hat u_x,\hat v_w\rangle|\ge \frac{1/2}{K\sqrt{s_0}}\ge b:=\frac1{2K\sqrt s}$, with the sign of $N_{xw}$. Let $g_1,\dots,g_T$ be independent standard Gaussian vectors in $\R^{s_0}$. Put $X':=\{x:\langle\hat u_x,g_t\rangle\ge0\ \forall t\}$ and $Y':=\{w:\langle\hat v_w,g_t\rangle\ge0\ \forall t\}$, and $\mathcal R:=X'\times Y'$. By Theorem~\ref{thm:Sheppard} and independence, $\Pr[(x,w)\in\mathcal R]\ge 4^{-T}$ for $(x,w)\in Q^+$, and $\Pr[(x,w)\in\mathcal R]\le4^{-T}(1-2b/\pi)^T\le 4^{-T}e^{-2bT/\pi}$ for $(x,w)\in Q^-$. Since $2bT/\pi=T/(\pi K\sqrt s)\ge\ln(2/\delta^2)$, we get \[ \mathbb E|\mathcal R\cap Q^-|\le\tfrac{\delta^2}{2}mn4^{-T}\le\tfrac\delta2\,\mathbb E|\mathcal R\cap Q^+|, \qquad \mathbb E|\mathcal R\cap Q^+|\ge\delta mn4^{-T}. \] Hence $\mathbb E\bigl[|\mathcal R\cap Q^+|-\delta^{-1}|\mathcal R\cap Q^-|\bigr]\ge\frac12\mathbb E|\mathcal R\cap Q^+| \ge\frac\delta2mn4^{-T}$. Fix an outcome attaining at least this value. For it, $|\mathcal R\cap Q^-|\le\delta|\mathcal R\cap Q^+|\le\delta|\mathcal R|$ and $|\mathcal R|\ge\frac\delta2 mn4^{-T}$. Since $|X'|\le m$ and $|Y'|\le n$, both size bounds follow. \end{proof} \subsection{Refinements and the normal form} A \emph{refinement of cost $(c_1,c_2)$} of a rectangle $R_0\times C_0$ is a rectangle $R\times C\subseteq R_0\times C_0$ with $|R|\ge|R_0|/c_1$ and $|C|\ge|C_0|/c_2$. Every property stated ``everywhere on'' a rectangle is inherited by its refinements. A \emph{basic quantity} is a positive row function, a positive column function or a positive constant. A function $\Delta$ on a rectangle is \emph{$c$-comparable} to a basic quantity $Q$ if $Q\le|\Delta|\le cQ$ everywhere on it. \begin{lemma}[Lemma A]\label{lem:A} Let $a$ be a row function and $b$ a column function on $R_0\times C_0$. There is a refinement of cost $(4,2)$ on which either (i) $a$ is constant, or (ii) for some $\theta$ we have $a(x)>\theta\ge b(w)$ everywhere, or $a(x)<\theta\le b(w)$ everywhere. \end{lemma} \begin{proof} Let $\theta$ be a median of $a$ on $R_0$, so that at least half of the rows have $a\le\theta$ and at least half have $a\ge\theta$. If $|\{a=\theta\}|\ge|R_0|/4$, take $\{a=\theta\}\times C_0$; this is case (i). Otherwise $\{a>\theta\}$ and $\{a<\theta\}$ each contain at least $|R_0|/4$ rows. One of $\{b\le\theta\}$ and $\{b\ge\theta\}$ contains at least $|C_0|/2$ columns. Take $\{a>\theta\}\times\{b\le\theta\}$ or $\{a<\theta\}\times\{b\ge\theta\}$ accordingly; this is case (ii). \end{proof} \begin{lemma}[Lemma B]\label{lem:B} Let $\Delta>0$ be a row function and $E\ge0$ a column function on $R_0\times C_0$. There is a refinement of cost $(4,4)$ on which (a) $\Delta\ge2E$ everywhere, or (b) $E\ge2\Delta$ everywhere, or (c) for some $s>0$ both $\Delta$ and $E$ take values in $(s/4,4s)$. \end{lemma} \begin{proof} Let $s$ be a median of $E$ on $C_0$. If $s=0$, then $\{E=0\}$ contains at least half of the columns and $\Delta>0=2E$ there: case (a). Let $s>0$. If $|\{\Delta\ge2s\}|\ge|R_0|/4$, take $\{\Delta\ge2s\}\times\{E\le s\}$: case (a). Else, if $|\{\Delta\le s/2\}|\ge|R_0|/4$, take $\{\Delta\le s/2\}\times\{E\ge s\}$: case (b). Otherwise $R_1:=\{s/2<\Delta<2s\}$ contains more than $|R_0|/2$ rows. If $|\{E\le s/4\}|\ge|C_0|/4$, take $R_1\times\{E\le s/4\}$: case (a). Else, if $|\{E\ge4s\}|\ge|C_0|/4$, take $R_1\times\{E\ge4s\}$: case (b). Otherwise $\{s/4\theta\ge b$ (the other case is symmetric), we have $a-b=\Delta+E$ with $\Delta:=a-\theta>0$ a row function and $E:=\theta-b\ge0$ a column function. Lemma~\ref{lem:B}, at cost $(4,4)$, gives one of three cases: (a) $\Delta\le a-b\le\frac32\Delta$; (b) $E\le a-b\le\frac32E$, where $E\ge2\Delta>0$; or (c) $s/20$ is $16$-comparable to a basic quantity. \end{itemize} Each pair costs at most $(16,8)$, so all pairs together cost at most $16^{\binom k2}$ per side. On the resulting rectangle, every difference of two surviving types has a constant strict sign and is $16$-comparable to a basic quantity. Since the values at a fixed $(x,w)$ are real numbers, these signs define one strict total order, and every entry has exactly one type in $\mathcal T'$. This gives (NF1) and~(NF2). For (NF3), let $J_{\mathrm{row}}$, $J_{\mathrm{col}}$, $J_{\mathrm{const}}$ be the sets of $j$ for which $Q_j$ is a row function, a column function or a constant. Split the rows according to which $j\in J_{\mathrm{row}}$ maximises $Q_j(x)$, keeping a largest part (cost at most $k$). On the result some $j_r$ satisfies $Q_{j_r}=R^\ast:=\max_{J_{\mathrm{row}}}Q_j$. Do the same for the columns, which gives $j_c$ with $Q_{j_c}=C^\ast:=\max_{J_{\mathrm{col}}}Q_j$. Let $j_s$ attain $s^\ast:=\max_{J_{\mathrm{const}}}Q_j$. Apply Lemma~\ref{lem:B} to $(R^\ast,C^\ast)$. In case (a) ($R^\ast\ge2C^\ast$), split the rows into $\{R^\ast\ge s^\ast\}$ and $\{R^\asts/4>s^\ast/4$ and $C^\ast<4s<16R^\ast$, so $j^\ast=j_r$ works with factor~$16$. If some $J_\bullet$ is empty, the corresponding comparison is simply omitted. The cost of this step is at most $(8k,8k)$. The total cost is at most $16^{\binom k2}\cdot 8k\le2^{2k^2+3}$ per side. \end{proof} \subsection{Proof of Theorem LR} We use induction on $k$. For $k=1$ take $R=[m]$ and $C=[n]$. Let $k\ge2$, and apply Lemma~\ref{lem:NF} to $[m]\times[n]$, obtaining $R_0\times C_0$ and $\mathcal T'$. If $k'=1$ we are done. Otherwise, by (NF2) and (NF3), $g_{j^\ast}\ge Q_{j^\ast}$ and $g_j\le16Q_j\le256Q_{j^\ast}$ for every $j$. So the spread $\mathcal S:=\tau_{(k')}-\tau_{(1)}=\sum_jg_j$ satisfies $\mathcal S\le256(k'-1)Q_{j^\ast}$. Put \[ z:=\tfrac12\bigl(\tau_{(j^\ast)}+\tau_{(j^\ast+1)}\bigr),\qquad \sigma:=Q_{j^\ast},\qquad N:=(M-z)/\sigma \quad\text{(entrywise, on $R_0\times C_0$)}. \] Each $\tau$ is a row or a column function, so $z=\varphi(x)+\vartheta(w)$ for functions $\varphi,\vartheta$. Since $\sigma$ is a basic quantity, $1/\sigma=\alpha(x)\beta(w)$ with $\alpha,\beta>0$ (one of them $\equiv1$). Hence $N=\mathrm{diag}(\alpha)\,(M-\varphi\mathbf 1^T-\mathbf 1\vartheta^T)\,\mathrm{diag}(\beta)$ has rank at most $r+2$. By (NF1) each entry has a unique type $\tau_{(i)}$. If $i\le j^\ast$, then $-256(k'-1)\le-\mathcal S/\sigma\le N\le-g_{j^\ast}/(2\sigma)\le-\frac12$. If $i>j^\ast$, then $\frac12\le N\le256(k'-1)$. So $\frac12\le|N|\le K:=256(k-1)$, and the sign of $N$ records on which side of the gap $j^\ast$ the type of the entry lies. Replacing $N$ by $-N$ if necessary, we may assume that $Q^+=\{N>0\}$ contains at least half of the entries of $R_0\times C_0$. Let $\mathcal T_{\mathrm{maj}}$ be the types on the positive side and $\mathcal T_{\mathrm{min}}$ those on the negative side. Both are nonempty, because $1\le j^\ast2^{\Lst+1}h . \end{equation} Since $\Lst\ge L_{k}(D+2)$ for every $k\le\kst$, any rectangle given by Theorem~\ref{thm:LR} with at most $\kst$ types for a matrix of rank at most $D+2$ has both sides of relative size at least $2^{-\Lst}$. \subsection{Configurations} \begin{definition}[level-$j$ configuration]\label{def:config} Let $0\le j\le n-2$. A \emph{level-$j$ configuration} is a triple $(S,W,\sigma)$ consisting of a rainbow set $S\subseteq X$ with $|S|=j$, a set $W\subseteq X\setminus S$ such that $S\cup\{x\}$ is rainbow for every $x\in W$, and a real $\sigma>0$ (the \emph{cap}) such that \[ |W\cap\Sph(s,t)|<\sigma\qquad\text{for all }s\in S,\ t>0 . \] For $j=0$ the cap condition is void, and $(\emptyset,W,\sigma)$ is a configuration for every $W\subseteq X$ and every $\sigma>0$. For $b\in W$ put \begin{gather*} R_b:=\Dist(S\cup\{b\})=\Dist(S)\cup\{\dd bs:s\in S\},\\ \Bg_b(\tau):=\{\lambda>0:\lambda\notin R_b,\ |W\cap\Sph(b,\lambda)|\ge\tau\}\quad(\tau>0). \end{gather*} \end{definition} If $(S,W,\sigma)$ is a level-$j$ configuration, $W'\subseteq W$ and $\sigma'\ge\sigma$, then $(S,W',\sigma')$ is again a level-$j$ configuration. \begin{definition}[Claim$(j)$]\label{def:claim} For $0\le j\le n-2$ and a real $\Gamma_j\ge1$, \textbf{Claim$(j)$} (with constant $\Gamma_j$) is the statement: \emph{every level-$j$ configuration $(S,W,\sigma)$ with $\sigma\ge\smin$ satisfies $|W|\le\Gamma_j\sigma$.} \end{definition} Claim$(j)$ quantifies over \emph{all} configurations and \emph{all} caps $\sigma\ge\smin$, and $\Gamma_j$ does not depend on $\sigma$. This uniformity is what allows the lemmas below to apply Claim$(j+1)$ with caps other than $\sigma$. \begin{lemma}[extension]\label{lem:ext} Let $(S,W,\sigma)$ be a level-$j$ configuration, and let $b\in W$ and $x\in W\setminus\{b\}$. Suppose that $\dd xb\notin R_b$, that $x\notin\bigcup_{s\in S}\Bis(b,s)$, and that $\dd xs\ne\dd b{s'}$ for all $s,s'\in S$. Then $S\cup\{b,x\}$ is rainbow. Moreover, at most $j^2\sigma$ points $x\in W$ satisfy $\dd xs=\dd b{s'}$ for some $s,s'\in S$; there are no such points if $j=0$. \end{lemma} \begin{proof} The distances of $S\cup\{b,x\}$ are those of $S$, the numbers $\dd bs$ and $\dd xs$ ($s\in S$), and $\dd bx$. The sets $\Dist(S)\cup\{\dd bs\}$ and $\Dist(S)\cup\{\dd xs\}$ are rainbow because $b,x\in W$. By hypothesis $\dd bs\ne\dd x{s'}$, $\dd bx\notin\Dist(S)\cup\{\dd bs\}$ and $\dd bx\ne\dd xs$, and $b,x\notin S$ are distinct. For the second statement: such points lie on one of the $j^2$ spheres $\Sph(s,\dd b{s'})$, each of which meets $W$ in fewer than $\sigma$ points. \end{proof} \subsection{The hereditary relative bound} \begin{lemma}[HR$_r$]\label{lem:HR} Let $0\le r\le n-3$ and assume Claim$(r+1)$ with constant $\Gamma_{r+1}$. Put $\Gamma'_r:=\Gamma_{r+1}+r^2$. Let $(S,W,\sigma)$ be a level-$r$ configuration with $\sigma\ge\smin$, let $c\in W$, $V\subseteq W\setminus\{c\}$ and $\theta\ge\sigma$. Then \[ \Bigl|\Bigl\{x\in V:\ \dd xc\notin R_c,\ x\notin\textstyle\bigcup_{s\in S}\Bis(c,s),\ |V\cap\Sph(c,\dd xc)|<\theta\Bigr\}\Bigr| \;\le\;\Gamma'_r\,\theta . \] \end{lemma} \begin{proof} Let $V_0$ be the set on the left. Let $V_2$ be the set of $x\in V_0$ with $\dd xs=\dd c{s'}$ for some $s,s'\in S$. By Lemma~\ref{lem:ext}, $|V_2|\le r^2\sigma\le r^2\theta$. Put $V_1:=V_0\setminus V_2$. For $x\in V_1$ the set $S\cup\{c,x\}$ is rainbow, by Lemma~\ref{lem:ext}. We claim that $(S\cup\{c\},V_1,\theta)$ is a level-$(r+1)$ configuration. Indeed, $S\cup\{c\}$ is rainbow because $c\in W$, and $V_1\subseteq X\setminus(S\cup\{c\})$. A sphere about $s\in S$ meets $V_1\subseteq W$ in fewer than $\sigma\le\theta$ points. If a sphere $\Sph(c,t)$ meets $V_1$ in a point $x$, then $t=\dd xc$ and $|V_1\cap\Sph(c,t)|\le|V\cap\Sph(c,\dd xc)|<\theta$. Since $\theta\ge\smin$, Claim$(r+1)$ gives $|V_1|\le\Gamma_{r+1}\theta$. \end{proof} \begin{remark}[the bisector exception]\label{rem:bisector} Points of $V$ on the bisectors $\Bis(c,s)$ are not controlled by Lemma~\ref{lem:HR}, and neither are points on spheres about $c$ with radius in $R_c$. In every application such points are handled by Theorem~\ref{thm:LR}. A point $x\in\Bis(c,s)$ satisfies $\dd xc^2=\dd xs^2$, which is a \emph{row type} of the matrix $[\dd xc^2]$ (rows $x$, columns $c$). A single-type rectangle of this type has $R\subseteq\Bis(s,c)$ for all its columns $c$, so Lemma~\ref{lem:typeOR} applies. The radii in $R_c$ are column functions ($\dd cs$) or constants ($d\in\Dist(S)$). \end{remark} \subsection{The kill step} \begin{lemma}[kill step]\label{lem:kill} Let $0\le r\le n-3$ and assume Claim$(r+1)$ with constant $\Gamma_{r+1}$. Let $(S,W,\sigma)$ be a level-$r$ configuration with $\sigma\ge\smin$, let $\tau\ge\sigma$, and let $K\ge0$ be an integer such that $|\Bg_b(\tau)|\le K$ for every $b\in W$. Then \[ |W|\le P(K,r)\,\bigl(2\Gamma_{r+1}\tau+2r^2\sigma+1\bigr),\qquad P(K,r):=\binom{D+1+e_{K,r}}{e_{K,r}}^{2},\quad e_{K,r}:=K+2r+\tbinom r2 . \] \end{lemma} \begin{proof} For $b\in W$ define \begin{gather*} \Delta_b(y):=\prod_{s\in S}\bigl(\dd yb^2-\dd ys^2\bigr)\prod_{s\in S}\bigl(\dd yb^2-\dd bs^2\bigr) \prod_{d\in\Dist(S)}\bigl(\dd yb^2-d^2\bigr),\\ F_b(y):=\Delta_b(y)\prod_{\lambda\in\Bg_b(\tau)}\bigl(\dd yb^2-\lambda^2\bigr). \end{gather*} $F_b$ is a product of at most $e_{K,r}$ affine functions of the lifted coordinates, so by Lemma~\ref{lem:DIM} all $F_b$ lie in one space of dimension $\binom{D+1+e_{K,r}}{e_{K,r}}$. At $y=b$ the factors equal $-\dd bs^2$, $-\dd bs^2$, $-d^2$ and $-\lambda^2$, all nonzero (recall $b\notin S$), so $F_b(b)\ne0$. \emph{Claim: for every $b\in W$, at most $\Gamma_{r+1}\tau+r^2\sigma$ points $x\in W\setminus\{b\}$ have $F_b(x)\ne0$.} Let $F_b(x)\ne0$. Then $\dd xb\notin\Bg_b(\tau)\cup R_b$ and $x\notin\bigcup_s\Bis(b,s)$. By Lemma~\ref{lem:ext}, either $x$ is one of at most $r^2\sigma$ points with $\dd xs=\dd b{s'}$, or $S\cup\{b,x\}$ is rainbow and $x\in W':=\{x\in W\setminus\{b\}:S\cup\{b,x\}\text{ rainbow},\ \dd xb\notin\Bg_b(\tau)\}$. The triple $(S\cup\{b\},W',\tau)$ is a level-$(r+1)$ configuration. Indeed, $S\cup\{b\}$ is rainbow. Spheres about $s\in S$ meet $W'$ in fewer than $\sigma\le\tau$ points. If $x\in W'\cap\Sph(b,t)$, then $t=\dd xb\notin R_b$, because $S\cup\{b,x\}$ is rainbow, and $t\notin\Bg_b(\tau)$; hence $|W'\cap\Sph(b,t)|\le|W\cap\Sph(b,t)|<\tau$. Since $\tau\ge\smin$, Claim$(r+1)$ gives $|W'|\le\Gamma_{r+1}\tau$. Let $G$ be the graph on $W$ in which $\{x,b\}$ is an edge if $F_b(x)\ne0$ and $F_x(b)\ne0$. By the claim, $G$ has at most $|W|(\Gamma_{r+1}\tau+r^2\sigma)$ edges, so its average degree is at most $2(\Gamma_{r+1}\tau+r^2\sigma)$. By Theorem~\ref{thm:CW}, $G$ has an independent set $I$ with $|I|\ge|W|/(2\Gamma_{r+1}\tau+2r^2\sigma+1)$. For distinct $x,y\in I$ we have $F_x(y)=0$ or $F_y(x)=0$, so Lemma~\ref{lem:H} gives $|I|\le\binom{D+1+e_{K,r}}{e_{K,r}}^2=P(K,r)$. \end{proof} \begin{remark}[on the constants of Lemma~\ref{lem:kill}]\label{rem:killconst} The square in $P(K,r)$ comes from Lemma~H, where a pair is killed from one side only. The term $+1$ comes from Caro--Wei. When the lemma is applied with $\tau=\rho\sigma$ for a number $\rho\ge1$, we use $1\le\sigma$ (by~\eqref{eq:absorb}) to write the bound as $|W|\le P(K,r)(2\rho\Gamma_{r+1}+2r^2+1)\,\sigma$. This is a pure multiple of the cap. \end{remark} % ==================================================================== \section{The top levels: Theorem R$^+$ with a single cap}\label{sec:top} % ==================================================================== In this section we prove Claim$(j)$ for $j=n-2,n-3,n-4$ (for $n=4$: $j=2,1,0$). At these levels a point with two big classes is handled directly, using $n-4$ points of $S$ as ``spread'' points; no class-count statement is needed. \begin{theorem}[Theorem R$^+$]\label{thm:Rplus} Put $Q:=2^{44}n^4(D+2)^{8k'}$, $\Gamma_{n-2}:=4(n-2)^2$, and for $j=n-3,n-4$ \begin{equation}\label{eq:Gamma-top} \Gamma_j:=P^+_j\,\bigl(2Q\Gamma_{j+1}+2(j^2+2n)+1\bigr),\qquad P^+_j:=\binom{D+1+e_j}{e_j}^{2},\quad e_j:=2+2j+\tbinom j2 . \end{equation} Then Claim$(j)$ holds with constant $\Gamma_j$ for $j=n-2,n-3,n-4$. \end{theorem} \begin{remark}[provenance and referee fixes]\label{rem:Rplus-prov} This is Theorem~R$^+$ of the project notes. There it was formulated with a sequence of thresholds $\tau_0<\tau_1<\cdots$, one for each point of $S$. An AI referee pass (report ``REFEREE\_R'') found it correct subject to three fixes: \textbf{F1}, a genuine threshold gap in Step~A, repaired by the branch at $\theta=Q^{1/2}\sigma$ in Step~4 below; \textbf{F2}, the auxiliary points $a$ must be taken in $W\setminus\{b\}$; \textbf{F3}, an undefined threshold $\tau_{-1}$, which is moot here because only the points of $S'$ are used and $S'=\emptyset$ is allowed. A later referee pass (``referee15'', item~X1) asked that the single-cap version be written out in full rather than obtained by a translation remark. This section does so. In particular the two-class count (``Lemma~S2'') and the ``four-case analysis'' of the notes appear below as Step~3 and Lemma~\ref{lem:twodist}. The ``level switch'' for $n\ge6$ that was sketched in the notes after that referee pass is not needed: the configuration formalism of Section~\ref{sec:framework} replaces it. For $n=4$ the Main Theorem follows from Theorem~\ref{thm:Rplus} alone. An earlier, longer proof of the case $n=4$ in the project notes, together with the editorial items of its referee report that concern only that proof, is superseded and not used here. \end{remark} \subsection{The base level} \begin{proof}[Proof of Claim$(n-2)$] Let $(S,W,\sigma)$ be a level-$(n-2)$ configuration with $\sigma\ge\smin$. Then $S$ is a rainbow $(n-2)$-set and every $x\in W$ is $S$-generic, i.e.\ $W\subseteq Y_S$ in the notation of Section~\ref{sec:G1}. For every real $v$, $\deg_W(v)\le\sum_{s\in S}|W\cap\Sph(s,v)|<(n-2)\sigma$. Suppose $|W|\ge4(n-2)^2\sigma$. Then $\deg_W(v)<|W|/(4(n-2))$ for all $v$, and Corollary~\ref{cor:G1}(c) gives $|W|\le2\cdot4^{n-2}\mu+4\le\smin\le\sigma<4(n-2)^2\sigma$, a contradiction. Hence $|W|<4(n-2)^2\sigma=\Gamma_{n-2}\sigma$. \end{proof} \subsection{Two distributions} \begin{lemma}[two-distribution lemma]\label{lem:twodist} Let $p=(p_t)$ and $q=(q_t)$ be finitely supported probability distributions on $\R$, let $\rho\ne\rho'$ be reals and $0\le\eta\le1/16$. Suppose \[ (1-p_{\rho'})(1-q_\rho)-\sum_{t\notin\{\rho,\rho'\}}p_tq_t\;\le\;\eta . \] Then there is a real $t^\ast\notin\{\rho,\rho'\}$ with $p_{\rho'}+p_{t^\ast}\ge1-\eta^{1/4}$ or $q_\rho+q_{t^\ast}\ge1-\eta^{1/4}$. \end{lemma} \begin{proof} Let $\alpha:=1-p_{\rho'}$ and $\beta:=1-q_\rho$. If $\alpha\le\eta^{1/4}$ or $\beta\le\eta^{1/4}$, the claim holds with any $t^\ast\notin\{\rho,\rho'\}$. Otherwise $\alpha\beta>\sqrt\eta$. For $t\notin\{\rho,\rho'\}$ put $p'_t:=p_t/\alpha$ and $q'_t:=q_t/\beta$. Then $p'_t,q'_t\le1$, $\sum_tp'_t\le1$ and $\sum_tq'_t\le1$ (sums over $t\notin\{\rho,\rho'\}$), and the hypothesis gives $\sum_tp'_tq'_t\ge1-\eta/(\alpha\beta)\ge1-\epsilon$ with $\epsilon:=\sqrt\eta<1$. Let $t^\ast\notin\{\rho,\rho'\}$ maximise $q'_t$. Then $1-\epsilon\le\sum_tp'_tq'_t\le q'_{t^\ast}$, and $1-\epsilon\le p'_{t^\ast}q'_{t^\ast}+\sum_{t\ne t^\ast}q'_t\le p'_{t^\ast}+(1-q'_{t^\ast})\le p'_{t^\ast}+\epsilon$. So $p'_{t^\ast}\ge1-2\epsilon$, and $p_{\rho'}+p_{t^\ast}=(1-\alpha)+\alpha p'_{t^\ast}\ge1-2\sqrt\eta\ge1-\eta^{1/4}$, where the last step uses $\eta\le1/16$. \end{proof} \subsection{A column with two big classes (Step A)} For a level-$j$ configuration $(S,W,\sigma)$ and $b\in W$ let $\Delta_b$ be the polynomial of Lemma~\ref{lem:kill}: $\Delta_b(y)=\prod_{s}(\dd yb^2-\dd ys^2)\prod_s(\dd yb^2-\dd bs^2)\prod_{d\in\Dist(S)}(\dd yb^2-d^2)$. If $\Delta_b(a)\ne0$ then $\dd ab\notin R_b$ and $a\notin\bigcup_s\Bis(b,s)$. \begin{lemma}[Step A]\label{lem:stepA} Let $\max(n-4,0)\le j\le n-3$, and let $(S,W,\sigma)$ be a level-$j$ configuration with $\sigma\ge\smin$. Let $b\in W$ and let $\rho_1\ne\rho_2$ be elements of $\Bg_b(Q\sigma)$. Put $C_\nu:=W\cap\Sph(b,\rho_\nu)$ for $\nu=1,2$, so that $|C_\nu|\ge Q\sigma$. Then the set \[ A:=\{a\in W\setminus\{b\}:\ \dd ab\notin\{\rho_1,\rho_2\},\ \Delta_b(a)\ne0\} \] has $|A|\le e_A+(j^2+2(n-4))\sigma$. \end{lemma} \begin{proof} Fix $S'\subseteq S$ with $|S'|=n-4$; this is possible since $j\ge n-4$. Let $A_0$ be the set of $a\in A$ such that $\dd as\ne\dd b{s'}$ for all $s,s'\in S$, and $a\notin\Sph(s,\rho_1)\cup\Sph(s,\rho_2)$ for all $s\in S'$. By Lemma~\ref{lem:ext} and the cap condition, $|A\setminus A_0|\le j^2\sigma+2(n-4)\sigma$. It remains to show $|A_0|\le e_A$. \emph{Step 1: the $(n-2)$-set $T$.} For $a\in A_0$ let $T=T(a):=\{b,a\}\cup S'$, so $|T|=n-2$. Since $\dd ab\notin R_b$, $a\notin\bigcup_s\Bis(b,s)$ and $\dd as\ne\dd b{s'}$, Lemma~\ref{lem:ext} shows that $S\cup\{b,a\}$ is rainbow, hence so is $T$. Moreover $\rho_\nu\notin\Dist(T)$, where $\Dist(T)=\Dist(S')\cup\{\dd bs,\dd as:s\in S'\}\cup\{\dd ab\}$. Indeed, $\rho_\nu\notin R_b\supseteq\Dist(S')\cup\{\dd bs\}$ by the definition of $\Bg_b$; $\rho_\nu\ne\dd ab$ since $a\in A$; and $\rho_\nu\ne\dd as$ for $s\in S'$ by the definition of $A_0$. \emph{Step 2: non-generic points.} Fix $a\in A_0$ and $\nu\in\{1,2\}$, and let $x\in C_\nu$. Then $x\notin T$: $x\ne b$ since $\dd xb=\rho_\nu>0$, $x\ne a$ since $\dd ab\ne\rho_\nu$, and $x\notin S$ since $W\cap S=\emptyset$. The label set of $x$ is $L_x=\{\rho_\nu,\dd xa\}\cup\{\dd xs:s\in S'\}$. If $x$ is not $T$-generic, then $x$ lies in \[ \Sph\bigl(a,\Dist(T)\cup\{\rho_\nu\}\bigr)\ \cup\ \bigcup_{s\in S'}\Bis(a,s)\ \cup\ \Sm_\nu(a), \] where \[ \Sm_\nu(a):=\bigcup_{s\in S'}\Sph\bigl(s,\{\rho_\nu,\dd ab\}\cup\{\dd b{s'},\dd a{s'}:s'\in S'\}\bigr). \] Indeed, the possible coincidences among $\Dist(T)\cup L_x$ are the following. $\Dist(T)$ itself is rainbow. Equalities among the $\dd xs$, or between some $\dd xs$ and $\Dist(S')$, are impossible because $S\cup\{x\}$ is rainbow. Equalities $\dd xs\in\{\rho_\nu,\dd ab,\dd b{s'},\dd a{s'}\}$ put $x$ in $\Sm_\nu(a)$. An equality $\dd xs=\dd xa$ puts $x$ in $\Bis(a,s)$. An equality $\dd xa\in\Dist(T)\cup\{\rho_\nu\}$ puts $x$ on a sphere about $a$. Finally $\rho_\nu\notin\Dist(T)$ by Step~1. The set $\Sm_\nu(a)$ is a union of $(n-4)(2n-6)$ spheres about points of $S$, so $|C_\nu\cap\Sm_\nu(a)|\le 2n^2\sigma$. \emph{Step 3: counting cross pairs (``Lemma S2'').} Fix $a\in A_0$ and put $P:=C_1\cap Y_T$ and $Q':=C_2\cap Y_T$. These are disjoint, since $\rho_1\ne\rho_2$. Let $E$ be the set of pairs $(x,w)\in P\times Q'$ with $\dd xa=\dd wa$, or $\dd xa=\rho_2$, or $\dd wa=\rho_1$. We claim \begin{equation}\label{eq:S2} |(P\times Q')\setminus E|\le\bigl(4^{n-2}\mu+n(n-4)\sigma\bigr)(|P|+|Q'|). \end{equation} By Corollary~\ref{cor:G1}(b), at most $4^{n-2}\mu(|P|+|Q'|)$ pairs are label-disjoint. Let $(x,w)\notin E$ share a label, where $L_x=\{\rho_1,\dd xa\}\cup\{\dd xs\}_{s\in S'}$ and $L_w=\{\rho_2,\dd wa\}\cup\{\dd ws\}_{s\in S'}$. Since $\rho_1\ne\rho_2$ and $(x,w)\notin E$, the shared value involves some $s\in S'$, so one of the following holds. Either $\dd xs\in\{\dd w{s'},\rho_2,\dd wa\}$: then for fixed $w$ the point $x$ lies on one of $(n-4)(n-2)$ spheres about points of $S'$, which gives at most $(n-4)(n-2)\sigma|Q'|$ pairs. Or $\dd ws\in\{\rho_1,\dd xa\}$: this gives at most $2(n-4)\sigma|P|$ pairs. Since $(n-4)(n-2)\le n(n-4)$ and $2(n-4)\le n(n-4)$, \eqref{eq:S2} follows. \emph{Step 4: one of the two classes is covered.} Fix $a\in A_0$ and put $\theta:=Q^{1/2}\sigma$. We claim that there are $\nu\in\{1,2\}$ and a real $t^\ast=t^\ast(a)$ such that, with $V(a):=\Dist(T)\cup\{\rho_1,\rho_2,t^\ast\}$, \begin{equation}\label{eq:stepA-cover} \Bigl|C_\nu\setminus\Bigl(\Sph(a,V(a))\cup\bigcup_{s\in S'}\Bis(a,s)\Bigr)\Bigr|\le\frac{|C_\nu|}{16(D+2)^{k'}} . \end{equation} We use $|C_\nu|\ge Q\sigma$ and the bounds $Q^{-1/2}=2^{-22}n^{-2}(D+2)^{-4k'}\le2^{-5}(D+2)^{-k'}$ and $2n^2/Q\le2^{-5}(D+2)^{-k'}$. \begin{itemize}[leftmargin=1.5em] \item If $|P|<\theta$, Step~2 shows that the left side of~\eqref{eq:stepA-cover} for $\nu=1$ is at most $|P|+|C_1\cap\Sm_1(a)|<(Q^{1/2}+2n^2)\sigma\le(Q^{-1/2}+2n^2/Q)|C_1|\le|C_1|/(16(D+2)^{k'})$. The case $|Q'|<\theta$ is symmetric, with $\nu=2$. \item Otherwise $|P|,|Q'|\ge\theta$. Put $\eta:=(4^{n-2}\mu+n(n-4)\sigma)(1/|P|+1/|Q'|)$. Since $4^n\mu\le\smin\le\sigma$, we have $4^{n-2}\mu\le\sigma/16$, and therefore \[ \eta\le\frac{2(\sigma/16+n^2\sigma)}{Q^{1/2}\sigma}\le 3n^2Q^{-1/2}\le2^{-20}(D+2)^{-4k'}\le\tfrac1{16}. \] Let $p_t:=|P\cap\Sph(a,t)|/|P|$ and $q_t:=|Q'\cap\Sph(a,t)|/|Q'|$. For independent uniform $x\in P$ and $w\in Q'$, \[ \Pr[(x,w)\notin E]=\Pr[\dd xa\ne\rho_2,\ \dd wa\ne\rho_1,\ \dd xa\ne\dd wa] =(1-p_{\rho_2})(1-q_{\rho_1})-\sum_{t\notin\{\rho_1,\rho_2\}}p_tq_t, \] and by~\eqref{eq:S2} this is at most $\eta$. Lemma~\ref{lem:twodist} (with $\rho=\rho_1$, $\rho'=\rho_2$) gives $t^\ast$ with $p_{\rho_2}+p_{t^\ast}\ge1-\eta^{1/4}$ or $q_{\rho_1}+q_{t^\ast}\ge1-\eta^{1/4}$. We can take $t^\ast>0$, since the two distributions are supported on positive distances. In the first case all but $\eta^{1/4}|P|$ points of $P$ lie on $\Sph(a,\{\rho_2,t^\ast\})$. Together with Step~2, the left side of~\eqref{eq:stepA-cover} for $\nu=1$ is at most $\eta^{1/4}|C_1|+2n^2\sigma\le(2^{-5}(D+2)^{-k'}+2n^2/Q)|C_1|$, which is at most $|C_1|/(16(D+2)^{k'})$. The second case is symmetric, with $\nu=2$. \end{itemize} \emph{Step 5: GL, LR and OR.} Let $A_\nu$ be the set of $a\in A_0$ for which~\eqref{eq:stepA-cover} holds with this $\nu$. Then $A_0=A_1\cup A_2$; say $|A_1|\ge|A_0|/2$ (the other case is symmetric). Note $A_1\cap C_1=\emptyset$. List $V(a)$ as $v_1(a),\dots,v_{t+3}(a)$, where $t=\binom{n-2}2$ and entries are repeated if $|V(a)|h$, so $|C'|\le h$. Hence $|A''|\le2^{\Lst}h$, $|A_1|\le2^{\Lst+1}h$ and $|A_0|\le2^{\Lst+2}h2^{\Lst+1}h$. \end{enumerate} \end{lemma} \begin{proof} (P3) is the definition of $\eps$, and (P6) follows from~\eqref{eq:absorb}. We have $1/\eps=96\cdot32\,\Gamma'(D+2)^{k_3(w_2)+k_4(w_2)}\le3\cdot2^{10}\Gamma'(D+2)^{k_c}$. For (P1), the first term of $\delta_1$ is at most $6\cdot2^{10}\,4^{n-2}\Gamma'(D+2)^{k_c}\sigma/M$, using $\mu\le\sigma$. This is at most $1/(2^{10}\Gamma'(D+2)^{k_c})$ because $M\ge M_{\mathrm{core}}\ge6\cdot2^{20}4^{n-2}\Gamma'^2(D+2)^{2k_c}\sigma$. The second term is at most $1/(2^{10}\Gamma'(D+2)^{k_c})$ because $M\ge3\cdot2^{10}n^2\Gamma'(D+2)^{k_c}\sigma$. (P2) holds because $M\ge6\cdot2^{10}n^2\Gamma'(D+2)^{k_c}\sigma\ge2n^2\sigma/\eps$. (P4) and (P5) hold because $k_4(w_1),k_5\le k_c$, $r+1\le n$ and $\Gamma'\ge1$. \end{proof} \subsection{Notation for two auxiliary points} Fix $l\ne m$ in $I$. For $a_1\in C_l$ and $a_2\in C_m$ put $T=T(a_1,a_2):=S\cup B\cup\{a_1,a_2\}$. These are $n-2$ distinct points, since $r+p=n-4$, $a_1\ne a_2$, and $a_1,a_2\notin S\cup B$ by (F4). For $x\notin T$ let $L_x:=\{\dd xy:y\in T\}$. For $x\in C_k$ we have $L_x=\{\dd xs\}_{s\in S}\cup\beta(k)\cup\{\dd x{a_1},\dd x{a_2}\}$ by (F2). Let $Y_T$ be the set of $T$-generic points, and put \[ \Hyp(a_1,a_2):=\bigcup_{s\in S,\,i=1,2}\Bis(s,a_i),\qquad \Sm(a_1,a_2):=\bigcup_{s\in S}\Sph\bigl(s,\{\dd{a_i}{s'}:i=1,2,\ s'\in S\}\cup\{\dd{a_1}{a_2}\}\bigr). \] Both are empty if $r=0$. $\Sm$ is a union of $r(2r+1)$ spheres about points of $S$, so it meets $W$ in at most $r(2r+1)\sigma\le2n^2\sigma$ points. By (F2), \begin{equation}\label{eq:DT} \Dist(T)=\Dist(S\cup B)\cup\{\dd{a_i}s:i=1,2,\ s\in S\}\cup\beta(l)\cup\beta(m)\cup\{\dd{a_1}{a_2}\},\qquad|\Dist(T)|\le t . \end{equation} \begin{definition}[validity]\label{def:valid} A pair $(k,k')$ is \emph{valid for $(a_1,a_2)$} if $k\ne k'$ are in $I\setminus\{l,m\}$, $T(a_1,a_2)$ is rainbow, and $(\beta(k)\cup\beta(k'))\cap\Dist(T)=\emptyset$. \end{definition} Validity is used only in Steps~0--2, to obtain the inclusions there. The properties $\Good_k$ and $\Cov_k$ defined below are properties of \emph{arbitrary} pairs $(a_1,a_2)\in C_l\times C_m$. Steps~3--5 count them over all of $C_l\times C_m$, and validity enters Step~5 only through the set $V_{lm}$ of pairs on which it holds (referee item~F). \subsection{Step 0: non-generic loci} \begin{lemma}[Step 0]\label{lem:step0} Let $T$ be rainbow, $k\in I\setminus\{l,m\}$ and $\beta(k)\cap\Dist(T)=\emptyset$. Every $x\in C_k\setminus Y_T$ lies in \[ \Sph\bigl(a_1,\Dist(T)\cup\beta(k)\bigr)\cup\Sph\bigl(a_2,\Dist(T)\cup\beta(k)\bigr)\cup\Bis(a_1,a_2)\cup\Hyp(a_1,a_2)\cup\Sm(a_1,a_2). \] \end{lemma} \begin{proof} First, $x\notin T$, because $C_k$ is disjoint from $S\cup B$, $C_l$ and $C_m$. We list the possible coincidences among $\Dist(T)\cup L_x$. $\Dist(T)$ is rainbow. Equalities among the $\dd xs$ and $\beta(k)$, or between these and $\Dist(S\cup B)$, are excluded by (F4) and (F3). The case $\dd xs\in\beta(l)\cup\beta(m)$ is excluded by (F5). Equalities $\dd xs\in\{\dd{a_i}{s'},\dd{a_1}{a_2}\}$ give $\Sm$. An equality $\dd xs=\dd x{a_i}$ gives $\Hyp$. An equality $\dd x{a_i}\in\Dist(T)\cup\beta(k)$ gives a sphere about $a_i$, and $\dd x{a_1}=\dd x{a_2}$ gives $\Bis(a_1,a_2)$. Finally $\beta(k)\cap\Dist(T)=\emptyset$ by hypothesis. \end{proof} \subsection{Step 1: a trichotomy} For $k\in I\setminus\{l,m\}$ put \[ \Lambda_k(a_1,a_2):=\Sph\bigl(a_1,\Dist(T)\cup\beta(k)\bigr)\cup\Sph\bigl(a_2,\Dist(T)\cup\beta(k)\bigr)\cup\Bis(a_1,a_2)\cup\Hyp(a_1,a_2). \] \begin{definition}[$\Good$]\label{def:good} $\Good_k(a_1,a_2)$ holds if there are a set $\Omega$ of at most $w_1$ positive reals and a set $\Ex\subseteq C_k$ with $|\Ex|\le\delta_1|C_k|$ such that $C_k\subseteq\Sph(a_1,\Omega)\cup\Sph(a_2,\Omega)\cup\Bis(a_1,a_2)\cup\Hyp(a_1,a_2)\cup\Ex$. \end{definition} \begin{lemma}[Step 1]\label{lem:step1} Let $(k,k')$ be valid for $(a_1,a_2)$. Then $\Good_k(a_1,a_2)$ holds, or \[ \bigl|C_{k'}\setminus\bigl(\Lambda_{k'}(a_1,a_2)\cup\Sph(a_1,\beta(k))\cup\Sph(a_2,\beta(k))\bigr)\bigr|<2\eps|C_{k'}|. \tag*{(ii)$_{k,k'}$} \] \end{lemma} \begin{proof} Put $P:=C_k\cap Y_T$, $Q:=C_{k'}\cap Y_T$ and $Q':=\{w\in Q:L_w\cap\beta(k)=\emptyset\}$. \emph{Case $|Q'|\ge\eps|C_{k'}|$.} $P$ and $Q'$ are disjoint subsets of $Y_T$. By Corollary~\ref{cor:G1}(b), at most $4^{n-2}\mu(|C_k|+|C_{k'}|)$ pairs $(w,x)\in Q'\times P$ are label-disjoint. So some $w_0\in Q'$ is label-disjoint from at most $\mathrm{ex}:=4^{n-2}\mu(|C_k|+|C_{k'}|)/(\eps|C_{k'}|)$ points of $P$. Let $x\in P$ be any other point, so that $L_x\cap L_{w_0}\ne\emptyset$. Now $\beta(k)\cap L_{w_0}=\emptyset$, because $\beta(k)\cap\beta(k')=\emptyset$ (F3), $\dd{w_0}s\notin\beta(k)$ (F5), and $w_0\in Q'$. So the common value is $\dd xs$ for some $s$, or $\dd x{a_i}$ for some $i$, and it lies in $L_{w_0}$. If it is $\dd xs$, then $\dd xs\notin\beta(k')$ by (F5), so $\dd xs\in\{\dd{w_0}{s'}\}_{s'}\cup\{\dd{w_0}{a_1},\dd{w_0}{a_2}\}$, and $x$ lies on one of $r(r+2)$ spheres about points of $S$. If it is $\dd x{a_i}$, then $x\in\Sph(a_i,L_{w_0})$. Combining this with Lemma~\ref{lem:step0}, $C_k$ is covered as in Definition~\ref{def:good} with $\Omega:=L_{w_0}\cup\Dist(T)\cup\beta(k)$, where $|\Omega|\le(n-2)+t+p=w_1$, and with $\Ex$ consisting of the at most $\mathrm{ex}$ label-disjoint partners, the fewer than $r(r+2)\sigma$ points on the spheres just described, and the fewer than $r(2r+1)\sigma$ points of $C_k\cap\Sm$. Since $|C_k|,|C_{k'}|\ge M$, \[ |\Ex|\le\Bigl(\frac{4^{n-2}\mu}{\eps}\Bigl(\frac1{|C_{k'}|}+\frac1{|C_k|}\Bigr)+\frac{3n^2\sigma}{M}\Bigr)|C_k|\le\delta_1|C_k|, \] so $\Good_k(a_1,a_2)$ holds. \emph{Case $|Q'|<\eps|C_{k'}|$.} By Lemma~\ref{lem:step0} applied to $k'$ (valid since $\beta(k')\cap\Dist(T)=\emptyset$), $C_{k'}\setminus Q\subseteq\Lambda_{k'}\cup\Sm$. If $w\in Q\setminus Q'$, then $L_w\cap\beta(k)\ne\emptyset$. Since $\dd ws\notin\beta(k)$ (F5) and $\beta(k')\cap\beta(k)=\emptyset$ (F3), this means $\dd w{a_i}\in\beta(k)$ for some $i$, i.e.\ $w\in\Sph(a_1,\beta(k))\cup\Sph(a_2,\beta(k))$. Hence the set in (ii)$_{k,k'}$ is contained in $Q'\cup(C_{k'}\cap\Sm)$, which has fewer than $\eps|C_{k'}|+2n^2\sigma\le2\eps|C_{k'}|$ points, by (P2). \end{proof} \subsection{Step 2: summing over $k$} \begin{lemma}[Step 2]\label{lem:step2} Fix $a_1,a_2$ and $k'\in I\setminus\{l,m\}$. Let $J\subseteq I\setminus\{l,m,k'\}$ with $|J|\ge3$ be such that, for every $k\in J$, $(k,k')$ is valid and (ii)$_{k,k'}$ holds. Then \[ \Cov_{k'}(a_1,a_2):\qquad |C_{k'}\setminus\Lambda_{k'}(a_1,a_2)|<6\eps|C_{k'}| . \] \end{lemma} \begin{proof} Let $c:=|C_{k'}\setminus\Lambda_{k'}|$ and assume $c\ge2\eps|C_{k'}|$. For each $k\in J$, by (ii)$_{k,k'}$, more than $c-2\eps|C_{k'}|$ points of $C_{k'}\setminus\Lambda_{k'}$ lie in $\Sph(a_1,\beta(k))\cup\Sph(a_2,\beta(k))$. By (F3) the radius sets $\beta(k)$, $k\in J$, are pairwise disjoint, so the sets $\Sph(a_1,\beta(k))$, $k\in J$, are pairwise disjoint, and likewise for $a_2$. Summing over $J$ gives $|J|(c-2\eps|C_{k'}|)<2c$, i.e.\ $c(|J|-2)<2|J|\eps|C_{k'}|$, so $c<6\eps|C_{k'}|$ as $|J|\ge3$. \end{proof} Note that $\Cov_{k'}(a_1,a_2)$ has the shape of $\Good_{k'}(a_1,a_2)$ with $\Omega:=\Dist(T)\cup\beta(k')$, so that $|\Omega|\le t+p=w_2$, and $\Ex:=C_{k'}\setminus\Lambda_{k'}$, so that $|\Ex|<6\eps|C_{k'}|$. Here $\Omega$ depends on $(a_1,a_2)$ through $\Dist(T)$. \subsection{Step 3: the two-centre lemma} \begin{definition}[$w$-few]\label{def:wfew} Let $j\in I\setminus\{l,m\}$, $w\in\{w_1,w_2\}$ and $a_2\in C_m$. Put $\theta_w:=\max(\theta_{\mathrm{rel}}(w)|C_j|,\sigma)$ and $\theta'_w:=\theta_w+r\sigma$. We say that \emph{$a_2$ is $w$-few on $C_j$} if there is a set $\Xi$ of at most $w+r+\binom r2$ positive reals with \[ \Bigl|C_j\setminus\Bigl(\Sph(a_2,\Xi)\cup\bigcup_{s\in S}\Bis(a_2,s)\Bigr)\Bigr|\le\Gamma'\theta'_w . \] This property depends only on $(a_2,j,w)$. \end{definition} \begin{lemma}[Step 3, two-centre lemma]\label{lem:step3} Let $j\in I\setminus\{l,m\}$, $a_2\in C_m$, $w\in\{w_1,w_2\}$ and $0<\delta\le\theta_{\mathrm{rel}}(w)/(16(D+2)^{k_3(w)})$. Let $Z\subseteq C_l$, and suppose that for each $a_1\in Z$ there are a set $\Omega(a_1)$ of at most $w$ positive reals and a set $\Ex(a_1)\subseteq C_j$ with $|\Ex(a_1)|\le\delta|C_j|$ such that \[ C_j\subseteq\Sph(a_1,\Omega(a_1))\cup\Sph(a_2,\Omega(a_1))\cup\Bis(a_1,a_2)\cup\Hyp(a_1,a_2)\cup\Ex(a_1). \] If $a_2$ is not $w$-few on $C_j$, then $|Z|\le(w+1)e$. \end{lemma} \begin{proof} For a real $\lambda>0$ let $R_\lambda:=(C_j\cap\Sph(a_2,\lambda))\setminus\bigcup_{s\in S}\Sph(s,\lambda)$ and $Z_\lambda:=\{a_1\in Z:\lambda\notin\Omega(a_1)\}$. Let $a_1\in Z_\lambda$ and $x\in R_\lambda\setminus\Ex(a_1)$. Then $x\notin\Sph(a_2,\Omega(a_1))$, since $\dd x{a_2}=\lambda\notin\Omega(a_1)$. Also $x\notin\Bis(s,a_2)$, since otherwise $\dd xs=\lambda$. If $x\in\Bis(a_1,a_2)$ then $\dd x{a_1}=\lambda$, and if $x\in\Bis(s,a_1)$ then $\dd x{a_1}=\dd xs$. Hence \begin{equation}\label{eq:31} \dd x{a_1}^2\in\{v^2:v\in\Omega(a_1)\}\cup\{\lambda^2\}\cup\{\dd xs^2:s\in S\}\qquad(x\in R_\lambda\setminus\Ex(a_1)). \end{equation} \emph{Claim: if $|R_\lambda|\ge\theta_w$, then $|Z_\lambda|\le e$.} Take rows $R_\lambda$ and columns $Z_\lambda$; they are disjoint, as $C_j\cap C_l=\emptyset$. List $\Omega(a_1)$ as $v_1(a_1),\dots,v_w(a_1)$, repeating entries if necessary, and put \[ \mathcal B[x,a_1]:=\prod_{i\le w}\bigl(\dd x{a_1}^2-v_i(a_1)^2\bigr)\cdot\bigl(\dd x{a_1}^2-\lambda^2\bigr)\cdot\prod_{s\in S}\bigl(\dd x{a_1}^2-\dd xs^2\bigr). \] This is a product of $k_3(w)=w+1+r$ factors, so $\rk\mathcal B\le(D+2)^{k_3(w)}$. By~\eqref{eq:31}, column $a_1$ has nonzero entries only in $\Ex(a_1)$, hence at most $\delta|C_j|\le\theta_{\mathrm{rel}}(w)|C_j|/(16(D+2)^{k_3(w)})\le|R_\lambda|/(16(D+2)^{k_3(w)})$ of them. Lemma~\ref{lem:GL} gives $R''\times Z''$ with $|R''|\ge|R_\lambda|/2$, $|Z''|\ge|Z_\lambda|/2$ and $\mathcal B=0$ there. On $R''\times Z''$ the matrix $[\dd x{a_1}^2]$ is covered by $k_3(w)\le\kst$ types: the column functions $v_i(a_1)^2$, the constant $\lambda^2$, and the row functions $\dd xs^2$. Theorem~\ref{thm:LR} and Lemma~\ref{lem:typeOR} (note $S\cap Z''=\emptyset$) give $R'''\times Z'''$ with $\min(|R'''|,|Z'''|)\le h$, where $|R'''|\ge2^{-\Lst}|R_\lambda|/2\ge2^{-\Lst-1}\sigma>h$ by (P6). So $|Z'''|\le h$, hence $|Z''|\le2^{\Lst}h$ and $|Z_\lambda|\le2^{\Lst+1}h\le e$. Suppose first that there are $w+1$ distinct radii $\lambda_1,\dots,\lambda_{w+1}$ with $|R_{\lambda_i}|\ge\theta_w$. Since $|\Omega(a_1)|\le w$, every $a_1\in Z$ lies in some $Z_{\lambda_i}$, so $|Z|\le(w+1)e$. Otherwise let $\Xi_h$ be the set of the at most $w$ radii with $|R_\lambda|\ge\theta_w$, and put $\Xi:=\Xi_h\cup R_{a_2}$, so that $|\Xi|\le w+r+\binom r2$. Let $x\in C_j$ with $x\notin\bigcup_s\Bis(a_2,s)$ and $\lambda:=\dd x{a_2}\notin\Xi$. Then $|R_\lambda|<\theta_w$, so $|C_j\cap\Sph(a_2,\lambda)|<\theta_w+r\sigma=\theta'_w$, because the spheres $\Sph(s,\lambda)$, $s\in S$, meet $W$ in fewer than $r\sigma$ points in total. Apply HR$_r$ with $c:=a_2\in W$, $V:=C_j\subseteq W\setminus\{a_2\}$ and threshold $\theta'_w\ge\sigma$. Since $\lambda\notin R_{a_2}$, every such $x$ is counted there, so there are at most $\Gamma'\theta'_w$ of them. Hence $a_2$ is $w$-few on $C_j$. \end{proof} So Lemma~\ref{lem:step3} says: \emph{if $a_2$ is not $w$-few on $C_j$, then $|Z|\le(w+1)e$} (referee item~X4). \subsection{Step 4: few $w$-few centres} \begin{lemma}[Step 4]\label{lem:step4} For $j\in I\setminus\{l,m\}$ and $w\in\{w_1,w_2\}$, the set $F$ of points $a_2\in C_m$ that are $w$-few on $C_j$ has $|F|\le e$. \end{lemma} \begin{proof} Take rows $C_j$ and columns $F$ (disjoint). For $a_2\in F$ let $\Xi(a_2)$ be as in Definition~\ref{def:wfew}, padded to exactly $w+r+\binom r2$ entries, and put $\mathcal B[x,a_2]:=\prod_{v\in\Xi(a_2)}(\dd x{a_2}^2-v^2)\prod_{s\in S}(\dd x{a_2}^2-\dd xs^2)$. This is a product of $k_4(w)$ factors, so $\rk\mathcal B\le(D+2)^{k_4(w)}$. Column $a_2$ has at most $\Gamma'\theta'_w$ nonzero entries, and \[ \Gamma'\theta'_w\le\Gamma'\theta_{\mathrm{rel}}(w)|C_j|+\Gamma'(r+1)\sigma\le\frac{|C_j|}{32(D+2)^{k_4(w)}}+\frac{|C_j|}{32(D+2)^{k_4(w)}}, \] by the definition of $\theta_{\mathrm{rel}}$ and (P4) (as $k_4(w)\le k_4(w_1)$). Lemma~\ref{lem:GL} gives a zero rectangle $C''\times F''$ with halves. There $[\dd x{a_2}^2]$ is covered by $k_4(w)\le\kst$ types: the column functions $a_2\mapsto v(a_2)^2$ given by the (padded) entries $v$ of $\Xi(a_2)$, and the row functions $\dd xs^2$. Theorem~\ref{thm:LR} and Lemma~\ref{lem:typeOR} give a rectangle with $\min\le h$, whose row side is at least $2^{-\Lst}|C_j|/2>h$ by (P6). So $|F''|\le2^{\Lst}h$ and $|F|\le e$. \end{proof} \begin{corollary}\label{cor:step34} Let $j\in I\setminus\{l,m\}$, $w\in\{w_1,w_2\}$ and $\delta$ be as in Lemma~\ref{lem:step3}, and suppose that for every $a_2\in C_m$ the set $Z(a_2)\subseteq C_l$ satisfies the hypothesis of Lemma~\ref{lem:step3}. Then $\sum_{a_2\in C_m}|Z(a_2)|\le e|C_l|+(w+1)e|C_m|$. \end{corollary} \begin{proof} The at most $e$ points $a_2$ that are $w$-few on $C_j$ (Lemma~\ref{lem:step4}) contribute at most $|C_l|$ each. Every other $a_2$ contributes at most $(w+1)e$, by Lemma~\ref{lem:step3}. \end{proof} We apply Corollary~\ref{cor:step34} in two ways, for each $j\in I\setminus\{l,m\}$: \begin{enumerate}[label=(\alph*)] \item $Z(a_2):=\{a_1\in C_l:\Good_j(a_1,a_2)\}$, with $w=w_1$ and $\delta=\delta_1$, which is admissible by (P1). This gives $|\{(a_1,a_2):\Good_j(a_1,a_2)\}|\le e|C_l|+(w_1+1)e|C_m|$. \item $Z(a_2):=\{a_1\in C_l:\Cov_j(a_1,a_2)\}$, with $w=w_2$ and $\delta=6\eps$, which is admissible by (P3); see the remark after Lemma~\ref{lem:step2}. This gives $|\{(a_1,a_2):\Cov_j(a_1,a_2)\}|\le e|C_l|+(w_2+1)e|C_m|$. \end{enumerate} \subsection{Step 5: counting, and the contradiction} Let $\Pi$ be the set of pairs $(a_1,a_2)\in C_l\times C_m$ with $\dd{a_1}s=\dd{a_2}{s'}$ for some $s,s'\in S$. For fixed $a_2$, at most $r^2\sigma$ points $a_1$ qualify (cap), so $|\Pi|\le r^2\sigma|C_m|$; and $\Pi=\emptyset$ if $r=0$. Put \[ \Ty(a_1,a_2):=\Dist(S\cup B)\cup\beta(l)\cup\beta(m)\cup\{\dd{a_1}s:s\in S\}\cup\{\dd{a_2}s:s\in S\}, \] a list of at most $\binom{r+p}2+2p+2r=k_5$ numbers, and $V_{lm}:=\{(a_1,a_2)\notin\Pi:\dd{a_1}{a_2}\notin\Ty(a_1,a_2)\}$. \begin{lemma}\label{lem:51} $T(a_1,a_2)$ is rainbow if and only if $(a_1,a_2)\notin\Pi$ and $\dd{a_1}{a_2}\notin\Ty(a_1,a_2)$. \end{lemma} \begin{proof} The distances of $T$ are $\Dist(S\cup B)$, $\dd{a_1}s$, $\beta(l)$, $\dd{a_2}s$, $\beta(m)$ and $\dd{a_1}{a_2}$. The sets $S\cup B\cup\{a_i\}$ are rainbow (F4), $\beta(l)\cap\beta(m)=\emptyset$ (F3), and $\dd{a_1}s\notin\beta(m)$ and $\dd{a_2}s\notin\beta(l)$ (F5). So the only possible coincidences are $\dd{a_1}s=\dd{a_2}{s'}$ (that is, $\Pi$) and $\dd{a_1}{a_2}\in\Ty$. \end{proof} Let $(a_1,a_2)\in V_{lm}$. Then $T$ is rainbow. By (F3) at most one index $k^\bullet\in I$ has $\dd{a_1}{a_2}\in\beta(k^\bullet)$, and $k^\bullet\notin\{l,m\}$ since $\beta(l)\cup\beta(m)\subseteq\Ty$. Put $I_0:=I\setminus\{l,m,k^\bullet\}$, so $|I_0|\ge9$. For $k\in I_0$ we have $\beta(k)\cap\Dist(T)=\emptyset$ by~\eqref{eq:DT}, (F3), (F5) and $k\ne k^\bullet$. Hence every $(k,k')$ with $k\ne k'$ in $I_0$ is valid. Let $g:=|\{k\in I_0:\Good_k(a_1,a_2)\}|$. If $g\le|I_0|-4$, then for each $k'\in I_0$ the set $J:=\{k\in I_0\setminus\{k'\}:\text{not }\Good_k(a_1,a_2)\}$ has $|J|\ge3$, and (ii)$_{k,k'}$ holds for $k\in J$ by Lemma~\ref{lem:step1}; so $\Cov_{k'}(a_1,a_2)$ holds by Lemma~\ref{lem:step2}, for every $k'\in I_0$. In either case \[ |\{k\in I\setminus\{l,m\}:\Good_k(a_1,a_2)\}|+|\{k\in I\setminus\{l,m\}:\Cov_k(a_1,a_2)\}|\ge6\qquad((a_1,a_2)\in V_{lm}). \] Summing over $(a_1,a_2)\in C_l\times C_m$ and applying (a) and (b) to each of the $10$ indices $j\in I\setminus\{l,m\}$, \[ 6|V_{lm}|\le10\bigl[2e|C_l|+(w_1+w_2+2)e|C_m|\bigr]\le10(w_1+w_2+2)\,e\,(|C_l|+|C_m|). \] So the density of $V_{lm}$ in $C_l\times C_m$ is at most $\frac{10}6(w_1+w_2+2)e(\frac1{|C_m|}+\frac1{|C_l|})\le4(w_1+w_2+2)e/M$ (referee item~B: the factor $10/6$ is the ratio of the number of indices summed, $10$, to the guaranteed count, $6$). The density of $\Pi$ is at most $r^2\sigma/|C_l|\le r^2\sigma/M$. Since $w_1+w_2+2=n^2-2n-2-2rh$ and $|C|\ge2^{-\Lst}|C_m|/2>h$, using (P6). Lemma~\ref{lem:typeOR} (rows $a_1\in R$, columns $a_2\in C$, $S\cap C=\emptyset$) gives $\min(|R|,|C|)\le h$, a contradiction. This proves Theorem~\ref{thm:core}. \qed \begin{remark} For $n=5$ and $r=0$ (so $p=1$) the sets $\Hyp$, $\Sm$ and $\Pi$ are empty, $R_{a_2}=\emptyset$, and only column functions and constants occur. In this case the proof is the argument for $f_d(5)$ written in the project's round~13 and refereed separately (``referee14''), up to the values of the constants. For general $r$ the proof adds row types $\dd xs^2$, coming from the bisectors $\Bis(s,a_i)$, and the small classes of points of $S$, whose costs are absorbed in $\delta_1$, in $\eps$ and in Step~5. \end{remark} % ==================================================================== \section{The Slicing Lemma and the class-count theorem E1$_r$}\label{sec:slicing} % ==================================================================== The setting is that of Section~\ref{sec:core}: $n\ge5$, $0\le r\le n-5$, $(S,W,\sigma)$ is a level-$r$ configuration with $\sigma\ge\smin$, and HR$_r$ holds for it with constant $\Gamma'\ge1$. \subsection{The Slicing Lemma} \begin{lemma}[Slicing Lemma]\label{lem:slicing} Let $0\le r\le n-6$, let $K\ge1$, and let $\mathcal F=(B,(C_k,\beta(k))_{k\in I})$ be a rainbow family at level $r$ with $1\le p=|B|\le n-5-r$ and $|I|\ge6K$. Put \[ k_{\mathrm{sl}}:=3K-1+\tbinom{r+p}2+2p+2r,\qquad\theta_{\mathrm{sl}}:=\frac1{16\,\Gamma'(D+2)^{k_{\mathrm{sl}}}},\qquad M_{\mathrm{sl}}:=\frac{2n(n+K)\sigma}{\theta_{\mathrm{sl}}}, \] and assume $k_{\mathrm{sl}}\le\kst$. If $M(\mathcal F)\ge M_{\mathrm{sl}}$, then there are a point $c\in\bigcup_kC_k$ and a rainbow family $\mathcal F'=(B\cup\{c\},(C'_k,\beta'(k))_{k\in I'})$ at level $r$ with $I'\subseteq I$, $|I'|=K$, $C'_k\subseteq C_k$ and $M(\mathcal F')\ge\theta_{\mathrm{sl}}M(\mathcal F)/2$. \end{lemma} \begin{proof} Discard indices so that $|I|=6K$, and put $M:=M(\mathcal F)$. Fix $\pi\in I$. For $c\in C_\pi$ the set $S\cup B\cup\{c\}$ is rainbow by (F4), and since $\dd c{b_i}=\beta_i(\pi)$, \[ \Phi(c):=\Dist(S\cup B\cup\{c\})=\Dist(S\cup B)\cup\beta(\pi)\cup\{\dd cs:s\in S\},\qquad|\Phi(c)|\le\tbinom{r+p}2+p+r . \] Note that $R_c=\Dist(S)\cup\{\dd cs\}\subseteq\Phi(c)$. Let $G_c$ be the bipartite graph with left vertex set $I\setminus\{\pi\}$ and right vertex set $\R_{>0}$, in which $k\sim\lambda$ if $\lambda\notin\Phi(c)\cup\beta(k)$ and $|C_k\cap\Sph(c,\lambda)|\ge\theta_{\mathrm{sl}}|C_k|$. Each $k$ has at most $1/\theta_{\mathrm{sl}}$ neighbours, so only finitely many right vertices are non-isolated, and we regard $G_c$ as a finite graph. \emph{(a) Few bad centres.} Let $Z_{\mathrm{bad}}$ be the set of $c\in C_\pi$ for which $G_c$ has no matching of size $3K$. We show $|Z_{\mathrm{bad}}|\le2e$. For $c\in Z_{\mathrm{bad}}$, Theorem~\ref{thm:Konig} gives a vertex cover $\mathcal A(c)\cup\Lambda_0(c)$, with $\mathcal A(c)\subseteq I\setminus\{\pi\}$, $\Lambda_0(c)\subseteq\R_{>0}$ and $|\mathcal A(c)|+|\Lambda_0(c)|\le3K-1$. Call $c$ \emph{$k$-few} for every $k\in I\setminus(\{\pi\}\cup\mathcal A(c))$; then every edge at $k$ ends in $\Lambda_0(c)$. Let $c$ be $k$-few, and let $x\in C_k$ satisfy $x\notin\bigcup_s\Bis(c,s)$ and $\lambda:=\dd xc\notin\Lambda_0(c)\cup\Phi(c)\cup\beta(k)$. Then $(k,\lambda)$ is not an edge, since $\lambda\notin\Lambda_0(c)$. As $\lambda\notin\Phi(c)\cup\beta(k)$, this means $|C_k\cap\Sph(c,\lambda)|<\theta_{\mathrm{sl}}|C_k|$. Also $\lambda\notin R_c$. Now apply HR$_r$ with $c\in W$, $V:=C_k\subseteq W\setminus\{c\}$ and threshold $\theta:=\theta_{\mathrm{sl}}|C_k|$; this is admissible since $\theta\ge\theta_{\mathrm{sl}}M_{\mathrm{sl}}=2n(n+K)\sigma\ge\sigma$. So the number of such $x$ is at most $\Gamma'\theta_{\mathrm{sl}}|C_k|=|C_k|/(16(D+2)^{k_{\mathrm{sl}}})$. Hence the matrix \[ \mathcal B_k[x,c]:=\prod_{v\in\Lambda_0(c)\cup\Phi(c)\cup\beta(k)}\bigl(\dd xc^2-v^2\bigr)\prod_{s\in S}\bigl(\dd xc^2-\dd xs^2\bigr) \] (with $\Lambda_0(c)$ padded to $3K-1$ entries, so that there are at most $k_{\mathrm{sl}}$ factors, and $\rk\mathcal B_k\le(D+2)^{k_{\mathrm{sl}}}$) has at most $|C_k|/(16(D+2)^{k_{\mathrm{sl}}})$ nonzero entries in every column $c$ that is $k$-few. Each $c\in Z_{\mathrm{bad}}$ is $k$-few for at least $(6K-1)-(3K-1)=3K$ indices $k$. So some $k$ has $Z_k:=\{c\in Z_{\mathrm{bad}}:c\text{ is $k$-few}\}$ with $|Z_k|\ge3K|Z_{\mathrm{bad}}|/(6K-1)\ge|Z_{\mathrm{bad}}|/2$. Take rows $C_k$ and columns $Z_k\subseteq C_\pi$ (disjoint). Lemma~\ref{lem:GL} gives a zero rectangle $C_k''\times Z_k''$ of $\mathcal B_k$ with halves. There $[\dd xc^2]$ is covered by at most $k_{\mathrm{sl}}\le\kst$ types: column functions (the entries of $\Lambda_0(c)$, and $\dd cs^2$), constants (the elements of $\Dist(S\cup B)$, $\beta(\pi)$ and $\beta(k)$), and row functions $\dd xs^2$. Theorem~\ref{thm:LR} and Lemma~\ref{lem:typeOR} give a single-type rectangle $R\times C$ with $\min(|R|,|C|)\le h$ and $|R|\ge2^{-\Lst}|C_k|/2>h$ (as $|C_k|\ge M\ge\sigma$). So $|C|\le h$, hence $|Z_k''|\le2^{\Lst}h$, $|Z_k|\le e$ and $|Z_{\mathrm{bad}}|\le2e$. \emph{(b) Choice of $c$.} Since $|C_\pi|\ge M\ge M_{\mathrm{sl}}>2\sigma\ge2e$, there is $c\in C_\pi\setminus Z_{\mathrm{bad}}$. Fix such a $c$ and a matching $\{(k,\lambda_k):k\in I_1\}$ of $G_c$ with $|I_1|=3K$; the $\lambda_k$ are distinct. \emph{(c) Label conflicts.} Consider the digraph on $I_1$ with an arc $k\to k'$ whenever $k'\ne k$ and $\lambda_k\in\beta(k')$. By (F3) each $\lambda_k$ equals at most one of the pairwise distinct numbers $\beta_i(k')$, so every out-degree is at most $1$. The underlying graph therefore has at most $3K$ edges, hence average degree at most $2$, and Theorem~\ref{thm:CW} gives an independent set of size at least $3K/3=K$. Let $I'$ consist of $K$ of its elements. For distinct $k,k'\in I'$ we then have $\lambda_k\notin\beta(k')$. \emph{(d) The new family.} Put $B':=B\cup\{c\}$, $\beta'(k):=(\beta(k),\lambda_k)$ and \[ C'_k:=\bigl(C_k\cap\Sph(c,\lambda_k)\bigr)\setminus\bigcup_{s\in S}\Sph\bigl(s,\{\dd c{s'}:s'\in S\}\cup\{\lambda_{k'}:k'\in I'\}\bigr)\qquad(k\in I'). \] Then $|C'_k|\ge\theta_{\mathrm{sl}}|C_k|-r(r+K)\sigma\ge\theta_{\mathrm{sl}}M-n(n+K)\sigma\ge\theta_{\mathrm{sl}}M/2$, because $\theta_{\mathrm{sl}}M\ge\theta_{\mathrm{sl}}M_{\mathrm{sl}}=2n(n+K)\sigma$. We verify (F1)--(F5) for $\mathcal F'$. \begin{itemize}[leftmargin=1.5em] \item[(F1)] $c\notin S\cup B$, and $S\cup B\cup\{c\}$ is rainbow, by (F4) for $c\in C_\pi$. \item[(F2)] $\dd x{b_i}=\beta_i(k)$ and $\dd xc=\lambda_k$ on $C'_k$. \item[(F3)] The old values are pairwise distinct (F3), and the $\lambda_k$ are pairwise distinct (matching). For $k\in I'$, $\lambda_k\notin\beta(k)$ (edge rule) and $\lambda_k\notin\beta(k')$ for $k'\in I'\setminus\{k\}$ (independence). None of the values lies in $\Dist(S\cup B\cup\{c\})=\Phi(c)$: $\lambda_k\notin\Phi(c)$ by the edge rule; $\beta_i(k)\notin\Dist(S\cup B)$ by (F3); $\beta_i(k)\ne\beta_{i'}(\pi)$ by (F3), as $k\ne\pi$; and $\beta_i(k)\ne\dd cs$ by (F5) for $c$. \item[(F4)] Let $x\in C'_k$. Then $x\notin S\cup B\cup\{c\}$, because $x\in C_k$, which is disjoint from $C_\pi\ni c$. The distances of $S\cup B\cup\{c,x\}$ are those of $S\cup B\cup\{x\}$ (rainbow), those of $S\cup B\cup\{c\}$ (rainbow), and $\dd xc=\lambda_k$. The cross coincidences are excluded as follows. $\dd xs=\dd c{s'}$ is excluded by the removal in the definition of $C'_k$. $\dd xs\in\beta(\pi)$ is excluded by (F5). $\beta_i(k)=\dd cs$ is excluded by (F5) for $c$. $\beta_i(k)=\beta_{i'}(\pi)$ is excluded by (F3). $\lambda_k\in\Phi(c)$ and $\lambda_k\in\beta(k)$ are excluded by the edge rule. Finally $\lambda_k=\dd xs$ is excluded by the removal. \item[(F5)] For $x\in C'_k$ and $s\in S$: $\dd xs\notin\beta(I')$ by (F5) for $\mathcal F$, and $\dd xs\ne\lambda_{k'}$ by the removal. \end{itemize} So $\mathcal F'$ is a rainbow family with $p+1$ centres, $|I'|=K$ and $M(\mathcal F')\ge\theta_{\mathrm{sl}}M/2$. \end{proof} \subsection{The class-count theorem} \begin{theorem}[E1$_r$]\label{thm:E1} Let $0\le r\le n-5$, and write $K^{(p)}:=K^{(r,p)}$ for $1\le p\le n-4-r$ (Definition~\ref{def:typecounts}), so that $K^{(1)}=K_r$ and $K^{(n-4-r)}=12$. For $1\le p\le n-5-r$ let $k_{\mathrm{sl}}(p):=k_{\mathrm{sl}}(r,p)$, $\theta_{\mathrm{sl}}(p):=1/(16\Gamma'(D+2)^{k_{\mathrm{sl}}(p)})$ and $\hat M_{\mathrm{sl}}(p):=2n(n+K^{(p+1)})/\theta_{\mathrm{sl}}(p)$. Define $\hat m_{n-4-r}:=\hat M_{\mathrm{core}}$ (Section~\ref{sec:core}) and, for $p=n-5-r,\dots,1$, \[ \hat m_p:=\max\bigl(\hat M_{\mathrm{sl}}(p),\,2\hat m_{p+1}/\theta_{\mathrm{sl}}(p)\bigr),\qquad\text{and}\qquad {\mathrm{ratio}}_r:=2\hat m_1+2n(n+K_r). \] These numbers depend only on $n$, $D$ and $\Gamma'$. If HR$_r$ holds with constant $\Gamma'$, then $|\Bg_b({\mathrm{ratio}}_r\,\sigma)|0$ and $\Gamma\ge 0$ in the kill step, and $B\subseteq X$ in the Core Lemma. It found no gap in the argument. \end{itemize} \paragraph{Availability.} The Lean source, build instructions and audit scripts are available at \url{https://github.com/H0W4RD-dev/erdos-1088-lean}. \end{sloppypar} % ==================================================================== \section{AI assistance and verification; credits}\label{sec:ai} % ==================================================================== \subsection*{AI assistance and verification} The mathematics in this manuscript was developed by AI agents (Claude, Anthropic) in research sessions directed by the team. The agents proposed the strategy, proved the lemmas, and wrote the project notes from which this manuscript was assembled. The manuscript itself was also prepared by an AI agent. The arguments were checked by \emph{independent AI referee passes}: separate agent sessions that had not written the material under review, re-derived each step by hand, and ran their own computer tests. In summary: \begin{itemize}[leftmargin=1.5em] \item one pass on Theorem~\ref{thm:LR} (with Lemma~\ref{lem:R}, the cleaning lemma, Lemmas~A, B and NF), on Corollary~\ref{cor:RQlist} and its relation to~\cite{SingerSudan}, and on an earlier proof of the case $n=4$. Verdict: correct, with editorial remarks only; \item one pass on the kill step, the two-class count and Theorem~R$^+$. Verdict: correct after fixes F1--F3, of which F1 repaired a genuine gap; \item one pass on the case $n=5$ of the class-count argument. Verdict: correct with expository gaps; items A--G of that report are addressed in Sections~\ref{sec:framework}--\ref{sec:core}; \item one pass on the general-$n$ argument (configurations, HR, kill step, Core Lemma, Slicing Lemma, threshold tower). Verdict: correct with expository gaps; items X1--X6 of that report are addressed in Sections~\ref{sec:prelim}, \ref{sec:framework}--\ref{sec:main} and~\ref{sec:concl}. \end{itemize} Each referee found the material under review correct, conditional on its inputs. All of them identified Theorem~\ref{thm:LR}, which is new and unpublished, as the weakest link. \textbf{No human expert has reviewed any part of this argument.} AI referee passes can miss errors, and several passes sharing similar blind spots is a real possibility. The Lean formalization of Section~\ref{sec:lean} was also written by AI agents. It removes the dependence on the referees for the \emph{formal} statement: Lean's kernel checks every step. Two things remain for human judgement: whether the formal statement faithfully captures Erd\H{o}s's question, and the sharper form of Theorem~\ref{thm:LR} stated here, whose NF3 step is not formalized. We also note what has \emph{not} been refereed in the present form. While consolidating the project notes into this manuscript we made some routine changes, and these have not been checked by any referee pass. They are: the explicit choices $Q=2^{44}n^4(D+2)^{8k'}$, $\smin=2^{\Lst+2+2n}(h+1)$ and $e_A=2^{\Lst+2}(h+1)$; the explicit constant $2^{14}$ in $L_k(r)$ and the explicit cost bounds in Lemma~\ref{lem:NF}; the column-basis proof of the cleaning lemma; the self-contained statement and proof of Lemma~\ref{lem:twodist}; the direct (rather than translated) single-cap proof of Theorem~\ref{thm:Rplus}; and the explicit growth recursion in Lemma~\ref{lem:growth}. We believe these changes are correct and harmless, but they are part of what an expert should check. \subsection*{Authors and credits} The authors are Will Howe (H0W4RD-dev), Grant Huffman (Ghuffy1), Jensen Kohlmeyer (jenw1n) and Liam Kruer (lkruer). Will Howe directed the AI research sessions that produced the proof and the Lean formalization. We acknowledge the prior in-project work of a peer session~\cite{Peer}, on which Section~\ref{sec:intro} and Lemma~\ref{lem:H} build. \subsection*{Contact} Will Howe, \texttt{howew@purdue.edu}; Grant Huffman, \texttt{huffma97@purdue.edu}; Jensen Kohlmeyer, \texttt{jenwin@purdue.edu}; Liam Kruer, \texttt{kruerl@purdue.edu}. % ==================================================================== \begin{thebibliography}{99} % ==================================================================== \bibitem{Ball} K.~Ball, An elementary introduction to modern convex geometry, in: \emph{Flavors of Geometry}, MSRI Publications~31, Cambridge University Press, 1997, pp.~1--58. \bibitem{Blokhuis} A.~Blokhuis, \emph{Few-distance sets}, CWI Tract~7, Centrum voor Wiskunde en Informatica, Amsterdam, 1984. \bibitem{Caro} Y.~Caro, New results on the independence number, Technical Report, Tel Aviv University, 1979. \bibitem{EP1088} T.~F.~Bloom, Erd\H{o}s Problem \#1088, \url{https://www.erdosproblems.com/1088}. The problem page records the Erd\H{o}s--Straus bound $f_d(n)\le c_n^d$ and its source. \bibitem{GavinskyLovett} D.~Gavinsky and S.~Lovett, En route to the log-rank conjecture: new reductions and equivalent formulations, in: \emph{Automata, Languages, and Programming (ICALP 2014)}, Lecture Notes in Computer Science~8572, Springer, 2014, pp.~514--524. \bibitem{GW} M.~X.~Goemans and D.~P.~Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, \emph{J.~ACM} \textbf{42} (1995), 1115--1145. \bibitem{HMST} Z.~Hunter, A.~Milojevi\'c, B.~Sudakov and I.~Tomon, Disjoint pairs in set systems and combinatorics of low rank matrices, arXiv:2411.13510. \bibitem{John} F.~John, Extremum problems with inequalities as subsidiary conditions, in: \emph{Studies and Essays Presented to R.~Courant on his 60th Birthday}, Interscience, New York, 1948, pp.~187--204. \bibitem{Konig} D.~K\H{o}nig, Gr\'afok \'es m\'atrixok, \emph{Matematikai \'es Fizikai Lapok} \textbf{38} (1931), 116--119. \bibitem{Lovett} S.~Lovett, Communication is bounded by root of rank, \emph{J.~ACM} \textbf{63} (2016), Article~1; arXiv:1306.1877. \bibitem{Peer} Prior in-project work: research notes on Erd\H{o}s Problem \#1088 by a peer AI session of the same project (notes file \texttt{e1088.md}, 2026), unpublished. \bibitem{Rothvoss} T.~Rothvo\ss, A direct proof for Lovett's bound on the communication complexity of low rank matrices, arXiv:1409.6366, 2014. \bibitem{Sheppard} W.~F.~Sheppard, On the application of the theory of error to cases of normal distribution and normal correlation, \emph{Philos. Trans. Roy. Soc. London Ser.~A} \textbf{192} (1899), 101--167. \bibitem{SingerSudan} N.~Singer and M.~Sudan, Point-hyperplane incidence geometry and the log-rank conjecture, arXiv:2101.09592 (version~5, 2022). \bibitem{SudakovTomon} B.~Sudakov and I.~Tomon, Matrix discrepancy and the log-rank conjecture, arXiv:2311.18524. \bibitem{Wei} V.~K.~Wei, A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum 81-11217-9, 1981. \end{thebibliography} \end{document}