64c3814
==== TABLE OF CONTENTS ====
The-hypercube-Ramsey-number-has-linear-order//figures/endpoint-comparisons.tex
The-hypercube-Ramsey-number-has-linear-order//figures/overview.tex
The-hypercube-Ramsey-number-has-linear-order//main.tex
The-hypercube-Ramsey-number-has-linear-order//references.tex
The-hypercube-Ramsey-number-has-linear-order//sections/01-introduction.tex
The-hypercube-Ramsey-number-has-linear-order//sections/01-regime-guide.tex
The-hypercube-Ramsey-number-has-linear-order//sections/02-reduction-and-notation.tex
The-hypercube-Ramsey-number-has-linear-order//sections/03-general-conventions-and-probabilistic-tools.tex
The-hypercube-Ramsey-number-has-linear-order//sections/04-bias-versus-purity-at-power-widths.tex
The-hypercube-Ramsey-number-has-linear-order//sections/05-a-constant-broad-high-neighborhood-case.tex
The-hypercube-Ramsey-number-has-linear-order//sections/06-very-small-polynomial-width-on-the-broad-side-polynomial-defect.tex
The-hypercube-Ramsey-number-has-linear-order//sections/07-a-small-power-key-grid.tex
The-hypercube-Ramsey-number-has-linear-order//sections/08-asymmetric-pure-patches-under-2.tex
The-hypercube-Ramsey-number-has-linear-order//sections/09-intermediate-powers-of-bias.tex
The-hypercube-Ramsey-number-has-linear-order//sections/10-full-dimensional-cluster-patches.tex
The-hypercube-Ramsey-number-has-linear-order//sections/11-jump-to-large-bias-only-at-linear-budget.tex
The-hypercube-Ramsey-number-has-linear-order//sections/12-the-two-deep-orientations-some-estimates.tex
The-hypercube-Ramsey-number-has-linear-order//sections/13-patch-tiling-under-9.tex
The-hypercube-Ramsey-number-has-linear-order//sections/14-internal-solver-and-profiles-for-these-tilings.tex
The-hypercube-Ramsey-number-has-linear-order//sections/15-high-modes-of-the-tiling.tex
The-hypercube-Ramsey-number-has-linear-order//sections/16-low-modes-geometry-and-cell-states.tex
The-hypercube-Ramsey-number-has-linear-order//sections/17-initial-list-gates-and-resampling-estimates.tex
The-hypercube-Ramsey-number-has-linear-order//sections/18-late-dynamics-and-its-transfer-problem.tex
The-hypercube-Ramsey-number-has-linear-order//sections/proof-inputs.tex
The-hypercube-Ramsey-number-has-linear-order//sections/regime-table.tex
===========================

==== BEGIN The-hypercube-Ramsey-number-has-linear-order//figures/endpoint-comparisons.tex ====
\begin{figure}[tbp]
\centering
\begin{tikzpicture}[
  box/.style={draw=black!65,rounded corners=2pt,fill=black!2,
    align=center,font=\small,inner sep=6pt,text width=12.1cm,
    minimum height=1.05cm},
  arrow/.style={-{Stealth[length=2mm]},line width=.65pt,draw=black!75},
  note/.style={font=\footnotesize,align=left,text width=5.6cm}
]
\node[box] (actual) at (0,0)
  {Specified endpoint pairs on a completed run\\
   Retain the events that each stage is reached and each pair test holds};
\node[box] (late) at (0,-2.3)
  {Independent reference outputs within each late class,\\
   conditional on its entering history};
\node[box] (lists) at (0,-4.6)
  {Initial assignment conditioned to avoid terminal failures\\
   Evaluate \(\mathbf1_{\mathcal G}\Phi(S_{\rm fin})\)};
\node[box] (initial) at (0,-6.9)
  {Initial assignment before conditioning on terminal avoidance\\
   Use permutation pools and finite resampling; retain \(\mathcal G\)};
\node[box] (fresh) at (0,-9.2)
  {Independent fresh cell states given the same fixed pools\\
   Use the calibrated cell strategies; retain \(\mathcal G\)};
\node[box] (iid) at (0,-11.5)
  {Fresh cell states with independent uniform pool slots\\
   Retain individual pool typicality \(\mathcal T\)};

\draw[arrow] (actual) -- (late)
  node[midway,right=3pt,note]
  {Bound the late outputs one class at a time, in reverse order\\
   Proposition~\ref{prop:late-assignment}};
\draw[arrow] (late) -- (lists)
  node[midway,right=3pt,note]
  {Integrate pair-hit factors with their side-data gates\\
   Bound~\eqref{eq:source-27}};
\draw[arrow] (lists) -- (initial)
  node[midway,right=3pt,note]
  {Conditioned expectation is at most\\
   \(1+o(1)\) times its preconditioning value\\
   Proposition~\ref{prop:terminal-avoidance}};
\draw[arrow] (initial) -- (fresh)
  node[midway,right=3pt,note]
  {Bound the same nonnegative test by fresh sampling at fixed pools\\
   Proposition~\ref{prop:initial-resampling-comparison}};
\draw[arrow] (fresh) -- (iid)
  node[midway,right=3pt,note]
  {First weaken \(\mathcal G\) to \(\mathcal T\), then compare slots\\
   Lemma~\ref{lem:late-classes-cells}};
\end{tikzpicture}
\caption{Upper comparisons for the endpoint product in
Proposition~\ref{prop:low-endpoint-kernels}.
The first two operations alternate, one class at a time in reverse order.
The late comparisons are conditional at each class, with the entering
history indicator retained until that comparison; each pair side-data
gate remains until its hit factor is integrated.
The pool gate \(\mathcal G\) includes individual typicality and
\eqref{eq:source-23} throughout the fixed deterministic simulation
horizons. It is retained through the fixed-pool resampling comparison,
then weakened to individual typicality \(\mathcal T\) before the slot
comparison. Every arrow bounds the indicated nonnegative test; none
asserts equality of laws or independence after avoidance.
The diagram stops before the later within-cell label, bin, pool and
history comparisons for nonisolated rows.}
\label{fig:endpoint-comparisons}
\end{figure}

==== END The-hypercube-Ramsey-number-has-linear-order//figures/endpoint-comparisons.tex ====

==== BEGIN The-hypercube-Ramsey-number-has-linear-order//figures/overview.tex ====
\begin{figure}[p]
\centering
\begin{tikzpicture}[
  x=1cm,y=1cm,
  box/.style={draw=black!65,rounded corners=2pt,fill=black!2,
    align=center,font=\small,inner sep=6pt,text width=6.0cm},
  wide/.style={box,text width=12.7cm},
  arrow/.style={-{Stealth[length=2mm]},line width=.65pt,draw=black!75}
]
\node[wide] (bad) at (0,0)
  {Hypothetical counterexamples (Section~\ref{sec:reduction-and-notation}):\\
   $n\to\infty$, $C_n=N/2^n\to\infty$, $N\le n2^n$};
\node[wide] (small) at (0,-1.8)
  {Weighted densities are close to $1/2$ at small widths\\
   after excluding configurations that yield a cube\\
   (Sections~\ref{sec:bias-versus-purity-at-power-widths}--\ref{sec:a-small-power-key-grid})};
\node[box] (intermediate) at (-3.4,-4.0)
  {Density bounds extend to unequal\\
   widths on the two host sides\\
   (Sections~\ref{sec:asymmetric-pure-patches-under-2}--\ref{sec:intermediate-powers-of-bias})};
\node[box] (clusters) at (3.4,-4.0)
  {Full-dimensional cluster patches\\
   are excluded
   (Section~\ref{sec:full-dimensional-cluster-patches})};
\node[wide] (deep) at (0,-6.3)
  {Discrepancy holds at a small linear width on either side\\
   and a power width on the other\\
   (Sections~\ref{sec:jump-to-large-bias-only-at-linear-budget}--\ref{sec:the-two-deep-orientations-some-estimates})};
\node[wide] (tiling) at (0,-8.3)
  {Disjoint host patches of one color and orientation\\
   receive subcubes specified by initial coordinates\\
   (Sections~\ref{sec:patch-tiling-under-9}--\ref{sec:internal-solver-and-profiles-for-these-tilings})};
\node[box] (high) at (-3.4,-10.8)
  {Larger gains (Section~\ref{sec:high-modes-of-the-tiling})\\
   Odd labels are assigned injectively\\
   Even column sums give Hall};
\node[box] (low) at (3.4,-10.8)
  {Smaller gains (Sections~\ref{sec:low-modes-geometry-and-cell-states}--\ref{sec:late-dynamics-and-its-transfer-problem})\\
   Preserve lists through late assignments\\
   Joint pair bounds give Hall};
\node[wide] (cube) at (0,-13.3)
  {A monochromatic copy of $Q_n$: contradiction\\
   Hence $\sup_{n\ge0}R(Q_n)/2^n<\infty$};
\draw[arrow] (bad) -- (small);
\draw[arrow] (small.south) -- (0,-2.75) -| (intermediate.north);
\draw[arrow] (small.south) -- (0,-2.75) -| (clusters.north);
\draw[arrow] (intermediate.south) |- (0,-5.45) -- (deep.north);
\draw[arrow] (clusters.south) |- (0,-5.45) -- (deep.north);
\draw[arrow] (deep) -- (tiling);
\draw[arrow] (clusters.east) -- ++(.42,0) |- (tiling.east);
\draw[arrow] (tiling.south) -- (0,-9.3) -| (high.north);
\draw[arrow] (tiling.south) -- (0,-9.3) -| (low.north);
\draw[arrow] (high.south) |- (0,-12.05) -- (cube.north);
\draw[arrow] (low.south) |- (0,-12.05) -- (cube.north);
\end{tikzpicture}
\caption{Logical dependencies of the proof. Each reduction is carried out
along the hypothetical counterexample sequence, passing to subsequences
and removing a vanishing fraction of labels where needed. The separate
arrow from cluster exclusion to patch extraction records its second use:
it bounds the measured scales of the remaining cluster patches.
One common color and orientation are fixed before cube allocation.
The final estimates apply to every sequence $C_n\to\infty$, with no
prescribed rate of divergence.}
\label{fig:proof-roadmap}
\end{figure}
==== END The-hypercube-Ramsey-number-has-linear-order//figures/overview.tex ====

==== BEGIN The-hypercube-Ramsey-number-has-linear-order//main.tex ====
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage[margin=1.05in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{needspace}
\usepackage{booktabs,array,longtable}
\usepackage{enumitem}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,fit,calc}
\usepackage{xcolor}
\usepackage{hyperref}
\hypersetup{colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,
  urlcolor=blue!45!black,pdftitle={The hypercube Ramsey number has linear order},
  pdfauthor={OpenAI}}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\setlist{itemsep=2pt,topsep=5pt,parsep=0pt}
\setlength{\emergencystretch}{2em}
\allowdisplaybreaks[2]
\setcounter{tocdepth}{2}
\title{The hypercube Ramsey number has linear order}
\author{OpenAI}
\date{September 23, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove that the two-color Ramsey number of the $n$-dimensional binary cube
is at most $C2^n$, where $C$ is an absolute constant. This resolves positively
the hypercube Ramsey conjecture of Burr and Erd\H{o}s.
\end{abstract}
\input{sections/01-introduction.tex}
\clearpage
\tableofcontents
\clearpage
\input{sections/proof-inputs.tex}
\clearpage
\appendix
\input{sections/regime-table.tex}
\clearpage
\phantomsection
\addcontentsline{toc}{section}{\refname}
\input{references.tex}
\end{document}
==== END The-hypercube-Ramsey-number-has-linear-order//main.tex ====

==== BEGIN The-hypercube-Ramsey-number-has-linear-order//references.tex ====
\begin{thebibliography}{99}

\bibitem{azuma1967}
K.~Azuma,
Weighted sums of certain dependent random variables,
\emph{Tohoku Mathematical Journal}
(2) \textbf{19} (1967), no.~3, 357--367.
\url{https://doi.org/10.2748/tmj/1178243286}.

\bibitem{beck1983}
J.~Beck,
An upper bound for diagonal Ramsey numbers,
\emph{Studia Scientiarum Mathematicarum Hungarica}
\textbf{18} (1983), no.~2--4, 401--406.

\bibitem{burr-erdos1975}
S.~A.~Burr and P.~Erd\H{o}s,
On the magnitude of generalized Ramsey numbers for graphs,
in \emph{Infinite and Finite Sets}, Vol.~I (Keszthely, 1973),
Colloquia Mathematica Societatis J\'anos Bolyai \textbf{10},
North-Holland, Amsterdam, 1975, pp.~215--240.
\url{https://www.renyi.hu/~p_erdos/1975-26.pdf}.

\bibitem{chvatal-rodl-szemeredi-trotter1983}
V.~Chv\'atal, V.~R\"odl, E.~Szemer\'edi and W.~T.~Trotter, Jr.,
The Ramsey number of a graph with bounded maximum degree,
\emph{Journal of Combinatorial Theory, Series B}
\textbf{34} (1983), no.~3, 239--243.
\url{https://doi.org/10.1016/0095-8956(83)90037-0}.

\bibitem{conlon2009bipartite}
D.~Conlon,
Hypergraph packing and sparse bipartite Ramsey numbers,
\emph{Combinatorics, Probability and Computing}
\textbf{18} (2009), no.~6, 913--923.
\url{https://doi.org/10.1017/S0963548309990174}.

\bibitem{conlon-fox-lee-sudakov2016}
D.~Conlon, J.~Fox, C.~Lee and B.~Sudakov,
Ramsey numbers of cubes versus cliques,
\emph{Combinatorica} \textbf{36} (2016), 37--70.
\url{https://doi.org/10.1007/s00493-014-3010-x}.

\bibitem{conlon-fox-sudakov2016}
D.~Conlon, J.~Fox and B.~Sudakov,
Short proofs of some extremal results II,
\emph{Journal of Combinatorial Theory, Series B} \textbf{121}
(2016), 173--196.
\url{https://doi.org/10.1016/j.jctb.2016.03.005}.

\bibitem{dirr-dondl-grimmett-holroyd-scheutzow2010}
N.~Dirr, P.~W.~Dondl, G.~R.~Grimmett, A.~E.~Holroyd and M.~Scheutzow,
Lipschitz percolation,
\emph{Electronic Communications in Probability} \textbf{15} (2010), 14--21.
\url{https://doi.org/10.1214/ecp.v15-1521}.

\bibitem{erdos-lovasz1975}
P.~Erd\H{o}s and L.~Lov\'asz,
Problems and results on \(3\)-chromatic hypergraphs and some related questions,
in \emph{Infinite and Finite Sets} (Keszthely, 1973),
Colloquia Mathematica Societatis J\'anos Bolyai \textbf{10} (1975), 609--627.
\url{https://users.renyi.hu/~p_erdos/1975-34.pdf}.

\bibitem{erdos-spencer1991}
P.~Erd\H{o}s and J.~Spencer,
Lopsided Lov\'asz Local Lemma and Latin transversals,
\emph{Discrete Applied Mathematics} \textbf{30} (1991),
nos.~2--3, 151--154.
\url{https://doi.org/10.1016/0166-218X(91)90040-4}.

\bibitem{finner1992}
H.~Finner,
A generalization of H\"older's inequality and some probability inequalities,
\emph{The Annals of Probability} \textbf{20} (1992), no.~4, 1893--1901.
\url{https://doi.org/10.1214/aop/1176989534}.

\bibitem{fiz-pontiveros-griffiths-morris-saxton-skokan2014}
G.~Fiz Pontiveros, S.~Griffiths, R.~Morris, D.~Saxton and J.~Skokan,
The Ramsey number of the clique and the hypercube,
\emph{Journal of the London Mathematical Society}
\textbf{89} (2014), no.~3, 680--702.
\url{https://doi.org/10.1112/jlms/jdu004}.

\bibitem{fiz-pontiveros-griffiths-morris-saxton-skokan2016}
G.~Fiz Pontiveros, S.~Griffiths, R.~Morris, D.~Saxton and J.~Skokan,
On the Ramsey number of the triangle and the cube,
\emph{Combinatorica} \textbf{36} (2016), 71--89.
\url{https://doi.org/10.1007/s00493-015-3089-8}.

\bibitem{fox-sudakov2009}
J.~Fox and B.~Sudakov,
Density theorems for bipartite graphs and related Ramsey-type results,
\emph{Combinatorica} \textbf{29} (2009), no.~2, 153--196.
\url{https://doi.org/10.1007/s00493-009-2475-5}.

\bibitem{freedman1975}
D.~A.~Freedman,
On tail probabilities for martingales,
\emph{The Annals of Probability} \textbf{3} (1975), no.~1, 100--118.
\url{https://doi.org/10.1214/aop/1176996452}.

\bibitem{gandhi-khuller-parthasarathy-srinivasan2006}
R.~Gandhi, S.~Khuller, S.~Parthasarathy and A.~Srinivasan,
Dependent rounding and its applications to approximation algorithms,
\emph{Journal of the ACM} \textbf{53} (2006), no.~3, 324--360.
\url{https://doi.org/10.1145/1147954.1147956}.

\bibitem{gowers1998}
W.~T.~Gowers,
A new proof of Szemer\'edi's theorem for arithmetic progressions of length four,
\emph{Geometric and Functional Analysis} \textbf{8} (1998), no.~3, 529--551.
\url{https://doi.org/10.1007/s000390050065}.

\bibitem{graham-rodl-rucinski2001}
R.~L.~Graham, V.~R\"odl and A.~Ruci\'nski,
On bipartite graphs with linear Ramsey numbers,
\emph{Combinatorica} \textbf{21} (2001), no.~2, 199--209.
\url{https://doi.org/10.1007/s004930100018}.

\bibitem{haeupler-saha-srinivasan2011}
B.~Haeupler, B.~Saha and A.~Srinivasan,
New constructive aspects of the Lov\'asz Local Lemma,
\emph{Journal of the ACM} \textbf{58} (2011), no.~6,
Article~28, 1--28.
\url{https://doi.org/10.1145/2049697.2049702}.

\bibitem{hall1935}
P.~Hall,
On representatives of subsets,
\emph{Journal of the London Mathematical Society}
(1) \textbf{10} (1935), no.~1, 26--30.
\url{https://doi.org/10.1112/jlms/s1-10.37.26}.

\bibitem{hamming1950}
R.~W.~Hamming,
Error detecting and error correcting codes,
\emph{Bell System Technical Journal} \textbf{29} (1950), no.~2, 147--160.
\url{https://doi.org/10.1002/j.1538-7305.1950.tb00463.x}.

\bibitem{harris-srinivasan2017}
D.~G.~Harris and A.~Srinivasan,
Algorithmic and enumerative aspects of the Moser--Tardos distribution,
\emph{ACM Transactions on Algorithms} \textbf{13} (2017), no.~3,
Article~33, 1--40.
\url{https://doi.org/10.1145/3039869}.

\bibitem{hoeffding1963}
W.~Hoeffding,
Probability inequalities for sums of bounded random variables,
\emph{Journal of the American Statistical Association}
\textbf{58} (1963), no.~301, 13--30.
\url{https://doi.org/10.1080/01621459.1963.10500830}.

\bibitem{kakutani1941}
S.~Kakutani,
A generalization of Brouwer's fixed point theorem,
\emph{Duke Mathematical Journal} \textbf{8} (1941), no.~3, 457--459.
\url{https://doi.org/10.1215/S0012-7094-41-00838-4}.

\bibitem{kostochka-rodl2001}
A.~V.~Kostochka and V.~R\"odl,
On graphs with small Ramsey numbers,
\emph{Journal of Graph Theory} \textbf{37} (2001), no.~4, 198--204.
\url{https://doi.org/10.1002/jgt.1014}.

\bibitem{lee2017}
C.~Lee,
Ramsey numbers of degenerate graphs,
\emph{Annals of Mathematics} (2) \textbf{185} (2017), no.~3, 791--829.
\url{https://doi.org/10.4007/annals.2017.185.3.2}.

\bibitem{lu-szekely2007}
L.~Lu and L.~A.~Sz\'ekely,
Using Lov\'asz local lemma in the space of random injections,
\emph{The Electronic Journal of Combinatorics}
\textbf{14} (2007), no.~1, Research Paper~63.
\url{https://doi.org/10.37236/981}.

\bibitem{moser-tardos2010}
R.~A.~Moser and G.~Tardos,
A constructive proof of the general Lov\'asz Local Lemma,
\emph{Journal of the ACM} \textbf{57} (2010), no.~2,
Article~11, 1--15.
\url{https://doi.org/10.1145/1667053.1667060}.

\bibitem{mota-sarkozy-schacht-taraz2015}
G.~O.~Mota, G.~N.~S\'ark\"ozy, M.~Schacht and A.~Taraz,
Ramsey numbers for bipartite graphs with small bandwidth,
\emph{European Journal of Combinatorics} \textbf{48}
(2015), 165--176.
\url{https://doi.org/10.1016/j.ejc.2015.02.018}.

\bibitem{ramsey1930}
F.~P.~Ramsey,
On a problem of formal logic,
\emph{Proceedings of the London Mathematical Society}
(2) \textbf{30} (1930), 264--286.
\url{https://doi.org/10.1112/plms/s2-30.1.264}.

\bibitem{shi2001}
L.~Shi,
Cube Ramsey numbers are polynomial,
\emph{Random Structures \& Algorithms} \textbf{19} (2001), no.~2, 99--101.
\url{https://doi.org/10.1002/rsa.1021}.

\bibitem{shi2007}
L.~Shi,
The tail is cut for Ramsey numbers of cubes,
\emph{Discrete Mathematics} \textbf{307} (2007), no.~2, 290--292.
\url{https://doi.org/10.1016/j.disc.2006.07.005}.

\bibitem{sudakov2003}
B.~Sudakov,
A few remarks on Ramsey--Tur\'an-type problems,
\emph{Journal of Combinatorial Theory, Series B}
\textbf{88} (2003), no.~1, 99--106.
\url{https://doi.org/10.1016/S0095-8956(02)00038-2}.

\bibitem{tikhomirov2024}
K.~Tikhomirov,
A remark on the Ramsey number of the hypercube,
\emph{European Journal of Combinatorics} \textbf{120}
(2024), article 103954.
\url{https://doi.org/10.1016/j.ejc.2024.103954}.
Preprint: \url{https://arxiv.org/abs/2208.14568}.

\end{thebibliography}
==== END The-hypercube-Ramsey-number-has-linear-order//references.tex ====

==== BEGIN The-hypercube-Ramsey-number-has-linear-order//sections/01-introduction.tex ====
\section{Introduction}
\label{sec:introduction}

Let $Q_n$ be the graph with vertex set $\{0,1\}^n$ in which two vertices
are adjacent when they differ in exactly one coordinate. For a finite graph
$H$, let $R(H)$ be the least positive integer $M$ such that every red-blue
coloring of the edges of $K_M$ contains a monochromatic subgraph isomorphic
to $H$. The copy is not required to be induced.

\begin{theorem}\label{thm:main}
There is an absolute constant $C>0$ such that
\[
R(Q_n)\le C2^n
\qquad\text{for every integer }n\ge0.
\]
\end{theorem}

\subsection{The problem and its historical development}

In their 1975 paper, Burr and Erd\H{o}s called a family of graphs an
\emph{$L$-set} if one constant bounds the Ramsey number of every member
by that constant times its order~\cite[Section~1]{burr-erdos1975}.
The arboricity of a graph is the minimum number of forests into which its
edges can be partitioned. They conjectured that every family of uniformly
bounded arboricity is an $L$-set. A graph is \emph{$d$-degenerate} if every nonempty subgraph
has a vertex of degree at most $d$; uniformly bounded arboricity and
uniformly bounded degeneracy are equivalent boundedness conditions for
families~\cite[Section~3]{burr-erdos1975}. Burr and Erd\H{o}s raised the
cube question separately in Section~7, asking whether the cubes form an
$L$-set. Theorem~\ref{thm:main} resolves that question positively.

The cube question sits at a natural density boundary. The first-moment
lower bound used by Burr and Erd\H{o}s implies that a family with one linear
Ramsey constant must satisfy
$e(H)/|V(H)|=O(\log |V(H)|)$ as its graph orders grow, where $e(H)$ is
the number of edges~\cite[Lemma~4.3 and Section~7]{burr-erdos1975}.
For the cube,
$e(Q_n)/|V(Q_n)|=n/2=\tfrac12\log_2|V(Q_n)|$.
Thus cubes reach the logarithmic order of edges per vertex that this
necessary condition still permits. They test linear Ramsey growth beyond
families with bounded degeneracy, at the largest possible order of this
density parameter up to a constant factor.

For $n\ge1$, parity of the coordinate sum gives the connected cube two
bipartition classes of size $2^{n-1}$. The standard lower-bound coloring
with two blocks~\cite[Introduction]{conlon-fox-lee-sudakov2016} gives
$R(Q_n)\ge3\cdot2^{n-1}-1$. Indeed, for $n\ge2$, take blocks of sizes
$2^n-1$ and $2^{n-1}-1$, color edges inside each block red, and color
crossing edges blue. Each red component is too small for $Q_n$, while a
blue copy would need $2^{n-1}$ vertices in each block. The case $n=1$ is
immediate. Theorem~\ref{thm:main} therefore determines the order of
$R(Q_n)$. It gives no numerical value for $C$ and does not determine
whether $R(Q_n)/2^n$ converges or what its limiting value would be.

One line of progress established linear Ramsey growth when a sparsity
parameter is fixed. Chv\'atal, R\"odl, Szemer\'edi and Trotter proved in
1983 that graphs of any fixed maximum degree have Ramsey number linear in
their order, with a constant depending on the degree~\cite{chvatal-rodl-szemeredi-trotter1983}.
Lee later proved the
corresponding assertion for every fixed degeneracy, resolving the
bounded-degeneracy form of the Burr--Erd\H{o}s conjecture~\cite[Theorem~1.1]{lee2017}.
These results did not settle the cube question
because both the maximum degree and the degeneracy of $Q_n$ equal $n$:
their constants may grow with the dimension.

A second line sought quantitative estimates when the degree grows with
the graph. Early work on cubes includes Beck's 1983 paper~\cite{beck1983}.
Graham, R\"odl and Ruci\'nski proved that a bipartite graph $H$ of maximum
degree at most $\Delta\ge1$ satisfies
$R(H)<8(8\Delta)^\Delta |V(H)|$~\cite[Theorem~1]{graham-rodl-rucinski2001}.
For $Q_n$ with $n\ge1$, whose order is $m=2^n$, this gives $R(Q_n)<8(16n)^n$, or
$m^{O(\log\log m)}$. Shi then obtained a bound polynomial in $m$, using a
refinement of Kostochka and R\"odl's common-neighborhood lemma~\cite{kostochka-rodl2001,shi2001},
and later refined the estimate~\cite{shi2007}. This moved the cube problem from a growing exponent in
$m$ to a fixed exponent.

The next estimates approached and then improved on the quadratic scale.
For positive integers $n$, Fox and Sudakov obtained
$R(Q_n)\le n2^{2n+5}$~\cite[Corollary~1.3]{fox-sudakov2009}, and Conlon,
Fox and Sudakov obtained
$R(Q_n)\le2^{2n+6}$~\cite[Corollary~4.2]{conlon-fox-sudakov2016}.
Lee's Theorem~1.3 and the paragraph following it give
$R(Q_n)\le2^{2n}+n^2 2^n$ for all sufficiently large $n$~\cite{lee2017}.
Tikhomirov's exponential improvement is
$R(Q_n)\le2^{2n-cn+1}+2$ for an absolute $c>0$ and all sufficiently large
$n$~\cite[Corollary~1.2]{tikhomirov2024}.
In terms of $m=2^n$, these estimates pass from an extra logarithmic factor
above $m^2$, to a constant multiple of $m^2$, to $(1+o(1))m^2$, and
finally to an exponent below $2$. The present theorem reaches a constant
multiple of $m$.

\paragraph{Consequences for related graph families.}
The bound transfers to targets occupying a controlled fraction of an
ambient cube. If $H$ is a not necessarily induced subgraph of $Q_d$ and
$2^d\le A|V(H)|$ for a fixed $A\ge1$, monotonicity gives
$R(H)\le R(Q_d)\le C2^d\le CA|V(H)|$. The bound on the ambient order
controls the constant for the smaller target.

For example, let $d\ge0$ and $k\ge1$ be integers, and let $F$ be a
spanning subgraph of $Q_d$. Its \emph{Cartesian power} $F^{\square k}$
has vertex set $V(F)^k$; two tuples are adjacent when they agree in all
but one coordinate and the two entries there are adjacent in $F$.
Concatenating the $k$ blocks of cube coordinates makes this product a
spanning subgraph of $Q_{dk}$. Consequently,
\[
R(F^{\square k})\le R(Q_{dk})\le C2^{dk}=C|V(F)|^k,
\]
with the same absolute $C$ for all permitted $F,d,k$.

This includes Cartesian powers of paths on $2^d$ vertices for $d\ge1$,
and cycles on $2^d$ vertices for $d\ge2$. Starting with the order $0,1$
for $Q_1$, obtain an order of $Q_d$ by prefixing $0$ to the order of
$Q_{d-1}$ and then $1$ to its reverse. Consecutive vertices are adjacent,
and for $d\ge2$ the first and last vertices are also adjacent, giving the
cycle. Writing $P_a$ for the path on $a$ vertices, Mota, S\'ark\"ozy,
Schacht and Taraz proved
$R(P_a\square P_b)=(3/2+o(1))ab$ as $ab\to\infty$ for positive integers
$a,b$~\cite[Corollary~1.4]{mota-sarkozy-schacht-taraz2015}.
Their framework fixes the degree and does not give a constant uniform in
a growing number of Cartesian factors; the deduction above does so when
the factor spans a cube.

\subsection{Background on embedding and sampling}

The common-neighborhood method addresses a basic extension step in
bipartite embedding. Once one target class has been placed, each vertex in
the other class needs an unused common neighbor of its already placed
neighbors. Under their respective density and size assumptions,
Kostochka and R\"odl's deterministic lemma~\cite[Lemma~1]{kostochka-rodl2001}
and Sudakov's probabilistic argument~\cite[Section~2]{sudakov2003} find
large host sets in which every subset of a prescribed size has many common
neighbors; Sudakov explicitly drew on Gowers's earlier sampling idea~\cite[Section~4, Lemma~11]{gowers1998}.
Later proofs allow a controlled
collection of exceptional subsets and arrange the first embedding so that
target neighborhoods avoid them. Conlon uses a hypergraph packing
argument~\cite{conlon2009bipartite}; independently, Fox and Sudakov use an
auxiliary hypergraph embedding~\cite[Lemmas~2.1--2.2]{fox-sudakov2009}.
Conlon, Fox and Sudakov use local avoidance of exceptional subsets and
collisions~\cite[Section~4]{conlon-fox-sudakov2016}.
These refinements give bounds of the form $2^{O(\Delta)}m$ for bipartite
targets of order $m$ and maximum degree $\Delta$, but the exponential
dependence on $\Delta=n$ still costs a power of the cube order.
Lee's embedding records a penalty for small common neighborhoods,
controls its average over target neighborhoods, and embeds the most
constrained vertices first~\cite[Section~2]{lee2017}.

Tikhomirov~\cite[Sections~1, 5 and~6]{tikhomirov2024} identifies an obstruction
to mapping a whole cube bipartition uniformly into one prepared set.
His proof instead distinguishes dispersed common neighborhoods, a denser
subgraph, and a block structure suited to a facet-wise cube embedding.
These density and structural alternatives provide a useful methodological
comparison for the reductions below. His Theorem~1.1 is a density theorem
for one color: for all sufficiently large $n$, it embeds $Q_n$ in every
bipartite graph of density at least $1/2$ whose two parts each have at least
$2^{(2-c)n}$ vertices, for an absolute $c>0$. The present proof uses the
absence of a cube in both colors of a counterexample to derive discrepancy.

A distinct line studies $R(Q_n,K_s)$, the least order of a complete graph
whose every red-blue edge coloring contains a red $Q_n$ or a blue $K_s$.
Conlon, Fox, Lee and Sudakov proved $R(Q_n,K_s)\le c_s2^n$ for every fixed
$s\ge3$~\cite[Theorem~1.1]{conlon-fox-lee-sudakov2016}.
Fiz Pontiveros, Griffiths, Morris, Saxton and Skokan obtained the triangle
asymptotic $R(Q_n,K_3)=(1+o(1))2^{n+1}$~\cite[Theorem~1.1]{fiz-pontiveros-griffiths-morris-saxton-skokan2016},
and their theorem for a fixed clique gives
\[
R(Q_n,K_s)=(s-1)(2^n-1)+1
\]
for each fixed $s\ge3$ and all sufficiently large $n$~\cite[Theorem~1.1]{fiz-pontiveros-griffiths-morris-saxton-skokan2014}.
The cube tilings in the Conlon--Fox--Lee--Sudakov and triangle papers use
subcubes obtained by fixing initial coordinates, then control the edges
between adjacent pieces. The present proof uses that geometry with piece
sizes chosen from retained patch masses and with different control of
crossing edges. These conclusions for a fixed clique do not imply the diagonal
cube theorem, where the target in both colors grows with $n$.

The task in the present diagonal problem is to retain a constant
multiplicative loss when the host order is only a slowly diverging multiple
of $2^n$. We work with a hypothetical counterexample sequence having two
disjoint host sides of size $N$ each and $N/2^n\to\infty$, with no
prescribed rate of divergence.

\input{sections/01-regime-guide.tex}

Figure~\ref{fig:proof-roadmap} records the dependencies between the
reductions. In particular, the cluster exclusion is used both before the
deep discrepancy conclusion and during the later patch extraction.
\input{figures/overview.tex}

\Needspace{24\baselineskip}
\subsection{Terminology}

All constants and exponents are fixed before $n\to\infty$. A fixed
threshold for a small patch scale need not grow with $n$.

\begin{center}
\begin{tabular}{@{}p{.22\linewidth}p{.71\linewidth}@{}}
\toprule
Term or symbol & Meaning \\
\midrule
Position or role & A vertex of the cube being embedded. \\
Label & A vertex of the host graph. \\
$X,Y,N$ & Disjoint host sides, each initially of size $N$; later width
normalizations continue to use this original $N$. \\
$C_n$ & The ratio $N/2^n$, tending to infinity at an unspecified rate. \\
Width of $\mu$ & $\log(N\max_x\mu(x))$, with natural logarithms. \\
Patch and $M_i$ & In the final tiling, a pair of retained host sets of common
size $M_i$, used for a portion of the cube. Earlier patches are specified
by their laws. \\
Raw law & The specified law before the avoidance constraints of the stage
being discussed. \\
Gate & An event indicator included in a probability or likelihood to
restrict it to specified local conditions; it does not normalize the law. \\
Profile & A probability distribution on a finite set of permitted local
choices, chosen to balance expected label masses. \\
\bottomrule
\end{tabular}
\end{center}
==== END The-hypercube-Ramsey-number-has-linear-order//sections/01-introduction.tex ====

==== BEGIN The-hypercube-Ramsey-number-has-linear-order//sections/01-regime-guide.tex ====
\subsection{The four phases of the proof}
\label{sec:four-proof-phases}

A \emph{role} is a vertex of the cube being embedded, and a \emph{label}
is a vertex of the host graph. We map the even and odd roles to disjoint
host sides. The construction must preserve every cube edge in one color
and assign distinct labels to distinct roles. After an injective assignment
$f$ of the odd roles, the possible labels for an even role $v$ form the
common-neighbor set
\[
 L_v=\bigcap_{u\sim v}N_G(f(u)),
\]
where $G$ is the chosen color. Most embedding arguments below construct
probability laws $p_v$ supported on $L_v$ with
$\sum_v p_v(x)\le1$ for every host label $x$. Summing over any set of roles
then gives Hall's condition and hence distinct representatives. In the
last part of the proof, we instead construct random two-element subsets
of $L_v$ and bound directly the probability that any collection of these
sets violates Hall's condition.

To describe the reductions, a \emph{patch} will mean a pair of host sets,
one on each side, with specified sampling laws $\mu,\nu$; the required
density properties vary between the constructions. Write
\[
 d_G(\mu,\nu)=\Pr\{xy\in G\},\qquad x\sim\mu,\quad y\sim\nu
 \quad\text{independently}.
\]
The \emph{width} of $\mu$ is $\log(N\max_x\mu(x))$: a width bound $w$
allows no atom larger than $e^w/N$. In particular, the uniform law on
$M$ labels has width $\log(N/M)$. A discrepancy bound controls
$|d_G(\mu,\nu)-1/2|$ for every pair of laws within specified width budgets.
An orientation specifies which host side receives the first law; reversing
it interchanges the sides and their width budgets.

A patch property is \emph{available} if, for some fixed $\kappa>0$ and
all sufficiently large $n$, a patch satisfying it exists after every
removal of at most $\kappa N$ labels from each side. The patch may
change with the removed sets.

\begin{enumerate}[leftmargin=*]
\item \textbf{Reduce to a sequence and construct the probability tools.}
If the theorem fails, Section~\ref{sec:reduction-and-notation} gives
counterexamples with two disjoint host sides of size $N$, where
$n\to\infty$, $N/2^n\to\infty$, and $N\le n2^n$. The construction must
work without any prescribed rate for the middle limit.
Section~\ref{sec:general-conventions-and-probabilistic-tools} provides
mixtures of patch laws with small average label masses, locally determined
choices of random data, and ways to sample labels injectively while
controlling their joint probabilities.

\item \textbf{Use density gains or deduce discrepancy.}
By Lemma~\ref{lem:stabilization}, we may pass to a subsequence and
remove $o(N)$ labels from each side so that each tested patch property is
either absent or available. At prescribed power widths,
Section~\ref{sec:bias-versus-purity-at-power-widths} then shows that
available bias of at least a suitable negative power of $n$ forces an
available nearly monochromatic patch at doubled widths, unless a cube can
already be embedded. The broad-side and
small-grid constructions in
Sections~\ref{sec:a-constant-broad-high-neighborhood-case}--\ref{sec:a-small-power-key-grid}
then embed a cube under their respective concentration and high-degree
hypotheses. These implications, applied in both colors of a counterexample,
exclude bias throughout an initial range of widths: every permitted law
pair has density close to one half.
Sections~\ref{sec:asymmetric-pure-patches-under-2}--\ref{sec:jump-to-large-bias-only-at-linear-budget}
extend this range, allowing much greater concentration on one side than
on the other. They also exclude the full-dimensional cluster witnesses
of Section~\ref{sec:full-dimensional-cluster-patches}, in which many
labels have unusually large pairwise common neighborhoods.
Section~\ref{sec:the-two-deep-orientations-some-estimates} records the
resulting discrepancy bounds with a small linear width budget on either
side and a power width on the other. The cluster exclusion also bounds
the scales of the smaller cluster patches used next.

\item \textbf{Allocate the cube to patches and use the larger gains.}
Section~\ref{sec:patch-tiling-under-9} extracts disjoint patches and
retains a family with one color, one orientation, and one of the finitely
many constructions described there. It allocates the cube to these
patches by subcubes obtained by fixing initial coordinates, with sizes
proportional to the patch sizes. This is the geometry used in earlier
cube-versus-clique tilings~\cite{conlon-fox-lee-sudakov2016,fiz-pontiveros-griffiths-morris-saxton-skokan2016}.
The fixed coordinates identify the cube edges crossing between patches.

Smaller host sets and crossing edges reduce the available common
neighborhoods, so the construction needs a compensating gain. For
comparison, suppose that each of $n$ independent restrictions retains
each label with probability $1/2+\delta$. A set of size $M$ would then
leave an expected $M(1/2+\delta)^n$ labels. Relative to $N2^{-n}$, the factor is
$(M/N)(1+2\delta)^n$: the accumulated density surplus can compensate for
the smaller support. The proof obtains the needed gain either from edge
density or from common-neighbor density inside cluster patches, and
bounds the additional losses from crossing edges and dependent choices.
Section~\ref{sec:internal-solver-and-profiles-for-these-tilings}
constructs the laws used inside cluster patches. When the gain is large
enough, Section~\ref{sec:high-modes-of-the-tiling} assigns the odd roles
injectively and bounds the column sums of the even laws supported on
$L_v$. Hall's theorem then completes the embedding.

\item \textbf{Complete the cases with smaller gains.}
Sections~\ref{sec:low-modes-geometry-and-cell-states}
and~\ref{sec:initial-list-gates-and-resampling-estimates} first assign
the odd roles and preserve lists for the even roles. A fixed linear map
on cube words partitions the odd roles into syndrome classes; a chosen
$O(\log n)$ of these classes receive provisional labels. Their labels
are replaced later, one class at a time, from reserved host sets. Each
even role has at most one neighbor in each late class.
Section~\ref{sec:late-dynamics-and-its-transfer-problem} controls how
these replacements shorten its list and leaves two distinct candidates
adjacent to all its assigned odd neighbors. A joint bound on the
candidate pairs rules out Hall-deficient collections, giving distinct
even labels.
\end{enumerate}

Appendix~\ref{app:regime-table} collects the quantitative branches,
including their width, density, and loss budgets. It is a reference for
the parameter choices after the corresponding constructions have been
introduced.

\paragraph{The probability comparisons.}
A recurring construction samples a hidden $k$-tuple on the first host
side and requires neighboring odd labels to be adjacent to every entry.
Given these odd labels, the tuple's conditional distribution is supported
on the $k$th Cartesian power of their common neighborhood. A bound on its largest atom
therefore gives a lower bound on the size of that neighborhood. The tuple
can also influence which observations are selected. Its likelihood must
include that selection event, with the selection rule recomputed when the
tuple is varied. Lemma~\ref{lem:gated-posterior} formulates this comparison;
Section~\ref{sec:bias-versus-purity-at-power-widths} gives its first
application.

Injectivity introduces another dependence. The calibrated sampler in
Lemma~\ref{lem:near-product-injection} preserves individual marginals
exactly and bounds probabilities of several specified outputs by their
product probabilities times a controlled factor. Exact marginals are
needed in later cluster constructions whose scales may remain fixed.
The clock sampler in Lemma~\ref{lem:clock-sampling} also avoids specified
local failures and provides a joint upper bound. Summing such bounds
against nonnegative functions permits the common-neighbor and load
estimates to be used after injective sampling. The later sequential
assignment requires further conditional comparisons, developed where the
successive observations are defined in
Section~\ref{sec:late-dynamics-and-its-transfer-problem}.
==== END The-hypercube-Ramsey-number-has-linear-order//sections/01-regime-guide.tex ====

==== BEGIN The-hypercube-Ramsey-number-has-linear-order//sections/02-reduction-and-notation.tex ====
\section{Reduction and notation}
\label{sec:reduction-and-notation}

We prove Theorem~\ref{thm:main} by contradiction along sequences.
All constants in an asymptotic argument, including exponents unless
explicitly indicated otherwise, are independent of \(n\).

\begin{lemma}[Counterexample sequence]\label{lem:counterexample-sequence}
If \(R(Q_n)/2^n\) is unbounded, there is a sequence of dimensions and
red-blue colorings between disjoint sets \(X,Y\), each of size \(N\),
with no monochromatic \(Q_n\) across the two sides, such that
\[
 n\longrightarrow\infty,\qquad C_n=N/2^n\longrightarrow\infty,\qquad N\le n2^n.
\]
\end{lemma}
\begin{proof}
Each fixed dimension has finite Ramsey number by the finite Ramsey
theorem~\cite{ramsey1930}. Thus an unbounded ratio has a subsequence along
which both the dimensions and the ratios tend to infinity. For each such
\(n\), take a coloring of \(K_{R(Q_n)-1}\) containing no monochromatic
\(Q_n\), and set
\[
N=\min\left\{\left\lfloor\frac{R(Q_n)-1}{2}\right\rfloor,
                 n2^n\right\}.
\]
Choose \(2N\) of its vertices and split them into equal sides. Restriction
to the cross edges cannot create a monochromatic cube. Moreover,
\(N/2^n\to\infty\), since both terms in the defining minimum have ratios
tending to infinity.
\end{proof}

Fix such a sequence for the remainder of the proof. We will contradict its
existence without imposing any rate of growth on \(C_n\).

Write \(A\) and \(B\) for the even and odd vertices of \(Q_n\). We call
these vertices \emph{roles} or \emph{positions}, and call host vertices
\emph{labels}. Usually the embedding sends \(A\) to \(X\) and \(B\) to
\(Y\); we may interchange the host sides. Distances between cube positions
are Hamming distances.

After labels have been discarded, all size and law normalizations still
use the original side size \(N\), unless another normalization is stated.
For a probability law \(\mu\) on either host side, define its \emph{width}
by
\[
 \operatorname{width}(\mu)=\log\bigl(N\max_x\mu(x)\bigr).
\]
Thus the uniform law on a set of \(M\) labels has width \(\log(N/M)\).
All logarithms are natural.

For a color \(G\) and laws \(\mu\) on \(X\), \(\nu\) on \(Y\), put
\[
 d_G(\mu,\nu)=\sum_{x\in X}\sum_{y\in Y}
                  \mu(x)\nu(y)\mathbf 1_{\{xy\in G\}}.
\]
This is the edge density seen by independent draws from the two laws.
A label in an argument of \(d_G\) denotes its point mass. A label
\emph{hits} another label in \(G\) when the two are adjacent in that
color. We leave integer roundoffs in scales and layer counts implicit
when the accompanying asymptotic inequalities have slack.

The tools in Section~\ref{sec:general-conventions-and-probabilistic-tools}
are used throughout. Sections~\ref{sec:bias-versus-purity-at-power-widths}--\ref{sec:a-small-power-key-grid}
establish the initial discrepancy bound~\eqref{eq:source-2};
Sections~\ref{sec:asymmetric-pure-patches-under-2}--\ref{sec:jump-to-large-bias-only-at-linear-budget}
exclude asymmetric purity, intermediate bias, full-dimensional clusters,
and the linear-budget jump.
Section~\ref{sec:the-two-deep-orientations-some-estimates} records the
resulting deep discrepancy and interaction estimates.
Sections~\ref{sec:patch-tiling-under-9}--\ref{sec:high-modes-of-the-tiling}
extract patches, allocate the cube, and exclude the high modes.
Sections~\ref{sec:low-modes-geometry-and-cell-states}--\ref{sec:late-dynamics-and-its-transfer-problem}
handle the bounded and low modes, ending with the two-endpoint Hall
estimate. Figure~\ref{fig:proof-roadmap} shows the dependencies between
these reductions.
==== END The-hypercube-Ramsey-number-has-linear-order//sections/02-reduction-and-notation.tex ====

==== BEGIN The-hypercube-Ramsey-number-has-linear-order//sections/03-general-conventions-and-probabilistic-tools.tex ====
\section{General conventions and probabilistic tools}
\label{sec:general-conventions-and-probabilistic-tools}

This section supplies the finite tools used throughout the proof. We first
retain witness families after small removals and balance their expected
label loads. We then prove conditional probability comparisons, a local
construction for choosing centers, and two samplers that assign distinct
labels. Each later application specifies the laws and local tests to which
these tools are applied.

\begin{definition}[Availability]
A witness has specified supports on the current host sides. After a pair
of label removals, it remains a witness if both supports are wholly
retained. A family is \textbf{available} along a sequence if some constant
\(\kappa>0\) has the following property: eventually, after every removal
of at most \(\kappa N\) labels from each side, at least one witness remains.
The witness may be chosen anew for each pair of removals.
\end{definition}

\begin{lemma}[Stabilization and finite menus]\label{lem:stabilization}
For a countable list of existence properties defined by witnesses
intrinsic to their supports, we can pass to a subsequence and discard
\(o(N)\) labels so that each property is either eventually absent or
available. Every fixed earlier availability survives with a smaller fixed
removal tolerance. An available finite union has an available member after
passing to a subsequence. An available menu can be replaced by a finite
menu at each dimension.
\end{lemma}

\begin{proof}
Treat the properties in order. If the current property can be eliminated
by \(o(N)\) additional removals along a subsequence, make those removals
and pass to that subsequence. Otherwise it is available: failure of every
fixed tolerance would let us choose successive dimensions at which
removals of size at most \(N/j\) eliminate the property, producing just
such a subsequence. Diagonalize these nested subsequences, choosing each
term sufficiently far out that the accumulated removals have size
\(o(N)\). For each fixed earlier stage, the later removals eventually use
less than half of its tolerance. Its availability therefore persists with
half that tolerance, while an absence persists under every further removal.

For an available union of \(k\) families with tolerance \(\kappa\), use
\(\kappa/k\) as the removal tolerance for each member. If no member were
available on a subsequence, we could combine their eliminating sets and
eliminate the union within its tolerance. Finally, there are only finitely
many pairs of label subsets at any fixed dimension. For each allowed
removal pair choose one surviving witness. These representatives form a
finite menu with the same availability.
\end{proof}

\begin{lemma}[Balanced mixtures and simultaneous profiles]\label{lem:balanced-profiles}
Let a finite patch menu be available with tolerance \(\kappa>0\), and let
patch \(i\) carry laws \((\mu_i,\nu_i)\) on its two supports. There is a
probability distribution on the menu such that, coordinatewise,
\[
 \mathbb E_i\mu_i,\ \mathbb E_i\nu_i\le K/N
\]
for a constant \(K\).

More generally, let finitely many players have finite action sets and
choose their actions independently according to probability distributions
called \emph{profiles}. Conditional on the realized actions, fix each
player's output-vector rule independently of the profiles. Suppose that,
for every choice of the other players' profiles, a player can meet its
fixed expected-vector upper bounds by a mixture of its actions. Then
there is a profile for every player under which all these bounds hold
simultaneously.
\end{lemma}

\begin{proof}
For the first assertion, assign nonnegative prices to labels on the
disjoint union of the host sides, and let \(P\) be their total. If \(P=0\)
there is nothing to prove. Otherwise, fewer than \(\kappa N\) labels on
either side have price greater than \(2P/(\kappa N)\). Availability gives
a patch avoiding all these labels. Each of its two laws then has expected
price at most \(2P/(\kappa N)\), so its pair-vector has price at most
\(4P/(\kappa N)\). If the convex hull of the pair-vectors contained no
vector bounded coordinatewise by \(4/(\kappa N)\), separation from that
downward-closed region would give nonnegative prices contradicting this
inequality. Thus \(K=4/\kappa\) suffices.

For the second assertion, write \(X_j\) for player \(j\)'s output vector
and \(b_j\) for its prescribed upper bound. With the other profiles
\(p_{-j}\) fixed, its feasible responses form
\[
 \mathcal R_j(p_{-j})
   =\{q_j:\mathbb E_{q_j,p_{-j}}X_j\le b_j\}.
\]
These sets are nonempty by hypothesis, and are closed and convex because
expectation is linear in \(q_j\). Since the action sets are finite and the
output rules are fixed, the expectations are continuous in all profiles;
hence the response correspondence has closed graph. The product of these
correspondences has a fixed point by Kakutani's theorem~\cite{kakutani1941}.
At that point every player's expected-vector bound holds.
\end{proof}

A kernel below may be a \emph{subprobability}, a nonnegative measure of
mass at most one. For example, a row \(p_v\), indexed by a cube role
\(v\), may be set to zero when its local construction is invalid.
Auxiliary experiments may instead use a specified fallback draw to
continue sampling. The final rows on a successful outcome must be
probability measures. If they are supported on the allowed labels and
\(\sum_v p_v(y)\le1\) for each label \(y\), then for every set \(S\) of
roles,
\[
 |S|=\sum_y\sum_{v\in S}p_v(y)
 \le\left|\bigcup_{v\in S}\operatorname{supp}p_v\right|.
\]
Hall's theorem~\cite{hall1935} therefore gives distinct allowed
representatives.

\begin{definition}[Raw experiments, gates, and stage histories]
A \emph{raw experiment} is the specified sampling law before the avoidance
constraints currently under discussion are imposed. A \emph{local gate}
is an event determined by the declared local inputs; retaining the gate
means multiplying by its indicator, rather than conditioning the
reference law on it. A \emph{successful prehistory} is an entering stage
history on which that stage's stated hypotheses hold. Comparisons are
made separately at each such history.
\end{definition}

The next comparisons bound expectations of arbitrary nonnegative tests.
An absolute estimate for the probability of failure would not suffice
when the test itself has very small probability.

\begin{lemma}[Conditional avoidance comparison]\label{lem:conditional-avoidance}
Let \(E_i\) be finitely many bad events with a symmetric neighbor relation
\(\sim\). Suppose that, whenever defined, the probability of \(E_i\)
conditioned on avoidance of any subset of its nonneighbors other than
itself is at most \(p_i\). Independent underlying variables, with events
joined when their variable scopes overlap, satisfy this hypothesis with
\(p_i=\Pr(E_i)\). Assume
\[
 p_i\le x_i\prod_{j\sim i}(1-x_j),\qquad 0\le x_i<1.
\]
Then all the events can be avoided with positive probability. For any set
\(S\) of indices not containing \(i\),
\(\Pr(E_i\mid \bigcap_{j\in S}E_j^c)\le x_i\).

Write \(A_S=\bigcap_{j\in S}E_j^c\). For disjoint index sets \(S,T\) and
any nonnegative random variable \(W\),
\[
 \mathbb E[W\mid A_{S\cup T}]
 \le \prod_{j\in T}(1-x_j)^{-1}\mathbb E[W\mid A_S].
\]
If an additional event \(F\) has conditional probability at most \(p_F\)
under avoidance of any subset of its nonneighbors, then
\[
 \Pr(F\mid A_S)\le
 p_F\prod_{j\in S:\,j\sim F}(1-x_j)^{-1}.
\]
\end{lemma}

\begin{proof}
The local lemma and its conditional induction go back to Erd\H{o}s and
Lov\'asz~\cite[Section~2]{erdos-lovasz1975}. Erd\H{o}s and
Spencer introduced the lopsided nonneighbor condition~\cite[Section~1]{erdos-spencer1991};
see Lu and Sz\'ekely~\cite[Lemma~3]{lu-szekely2007} for the asymmetric
formulation used here.
Here is the induction for the stated hypotheses. Split a conditioning
set into nonneighbors and neighbors of \(E_i\). The numerator is bounded
by \(p_i\) after discarding neighbor-avoidance conditions. By induction,
each neighbor-avoidance condition has conditional probability at least
\(1-x_j\), so the denominator is at least their product. This proves
\(\Pr(E_i\mid A_S)\le x_i\), and simultaneously proves positivity of all
avoidance probabilities. In particular,
\[
 \Pr(A_T\mid A_S)\ge\prod_{j\in T}(1-x_j).
\]
Inserting \(\mathbf1_{A_T}\le1\) in the conditional expectation of
\(W\), then dividing by this lower bound, proves the first comparison.
The same argument for \(F\) removes only its neighbors and uses its own
conditional nonneighbor bound for the remaining numerator.
\end{proof}

For independent underlying variables, removing all avoidance constraints
that touch a specified set of variables makes those variables independent
of the remaining avoidance event. They can then be integrated under their
raw laws. In applications we impose avoidance separately at each entering
history; we do not reweight earlier draws by the probability of later
avoidance.

\begin{lemma}[Scattered moments]\label{lem:scattered-moments}
Let \(Z_v\ge0\), indexed by a finite role set \(U\), be bounded by \(L\)
on a success event. Each role has a near set, including itself, of size at
most \(f|U|\). Suppose that for any sequence of at most \(n\) indices,
each outside the near sets of its predecessors, the joint product
expectation with the success indicator is at most \(K^n\) times the
product of deterministic comparison means \(d_v\), where \(K\ge1\).
Then
\[
 \mathbb E\!\left[\mathbf1_{\rm success}
       \bigl(|U|^{-1}\textstyle\sum_v Z_v\bigr)^n\right]
 \le K^n\bigl(|U|^{-1}\textstyle\sum_v d_v+nfL\bigr)^n.
\]
\end{lemma}

\begin{proof}
Expand the power by drawing \(n\) indices independently and uniformly
from \(U\). Mark a position as removed if its index lies in the near set
of any preceding index. On success each removed factor costs at most
\(L\); the unremoved indices satisfy the joint-comparison hypothesis.
For each removal pattern, apply that comparison, then discard the
separation conditions at the unremoved positions. Sum over the indices
in reverse order. At an unremoved position the factor is
\(|U|^{-1}\sum_v d_v\). At a removed position the necessary proximity
condition permits at most an \(nf\) fraction of indices, so its factor is
at most \(nfL\). Summing over all removal patterns gives the claimed
binomial expansion.
\end{proof}

We may first apply the joint comparison conditional on a successful
prehistory, retaining its indicator, and only afterwards discard
nonlocal restrictions for an upper bound. Typically \(nfL=o(1)\), while
\(K\) and the average of the \(d_v\)'s are bounded. Markov's inequality
at a sufficiently large constant threshold then permits a union over
\(\exp(O(n))\) columns. For \(Z_v=Np_v(y)\), the resulting bound on the
average gives
\[
 \sum_{v\in U}p_v(y)
   =\frac{|U|}{N}\left(|U|^{-1}\sum_{v\in U}Z_v\right)=o(1)
\]
when \(|U|=O(2^n)\), since \(N=C_n2^n\) and \(C_n\to\infty\).
The exceptional probability here includes the success indicator. We also
use this argument with patch-specific sizes.

\begin{lemma}[Gated posterior comparison]\label{lem:gated-posterior}
Fix any earlier information in a reference experiment. Let a candidate
\(z\) have prior law \(\pi\), and let \(F_z(t)\) be the likelihood of data
\(t\) together with a required event. Thus \(F_z\) includes the event
indicator and may have total mass less than one. Set
\[
 m(t)=\int F_z(t)\,d\pi(z).
\]
Use one common reference measure for all data densities; in a finite
space these may simply be masses. If \(Q\) is any reference probability
law on the data fixed by the earlier information and \(\epsilon>0\), then the joint
probability of the required event and
\(\{m(t)<\epsilon Q(t)\}\cup\{m(t)=0\}\) is at most \(\epsilon\).
If also \(F_z(t)\le e^sQ(t)\), the posterior
\(F_z(t)\,d\pi(z)/m(t)\) outside this exception is dominated by
\(e^s\epsilon^{-1}\pi\). Integrating the posterior against the required-event
data measure recovers the prior experiment with its gate retained.
\end{lemma}

\begin{proof}
The data measure with the required event has density \(m\). Its mass on
\(\{m<\epsilon Q\}\) is at most \(\epsilon\int Q=\epsilon\), and its
mass where \(m=0\) is zero. On the complement,
\(F_z/m\le e^s/\epsilon\). Finally, for any nonnegative test \(h\),
\[
 \int m(t)\int h(z,t)\frac{F_z(t)}{m(t)}\,d\pi(z)\,dt
   =\int\!\int h(z,t)F_z(t)\,dt\,d\pi(z),
\]
with the left integrand set to zero where \(m=0\). This is the asserted
cancellation.
\end{proof}

The gate and every selection rule in \(F_z\) must be recomputed as \(z\)
varies. To use this estimate after an assignment, we first compare the
joint law of the required outputs with the reference experiment. Only
then may we remove nonlocal prehistory restrictions, keeping the local
gate inside \(F_z\).

\subsection{Geometric height device}
\label{sec:geometric-height-device}

We next choose centers in Hamming balls while keeping the choices at
nearby sites geometrically compatible. A center has an ID consisting of
its location and level. The construction gives neighboring sites levels
that differ by at most one, and bounds the number of active IDs they can
consult. Its path-maximum rule is related to the admissible-path
construction of Lipschitz percolation~\cite[Sections~4--5]{dirr-dondl-grimmett-holroyd-scheutzow2010}.
Here eligibility may depend on all the sampled center positions, so the
independence needed in the proof comes only after separating those
positions from the later activations.

Let the queried sites form a subset \(S\) of \(Q_d\), where
\(d=\Theta(n)\). A horizontal step may join queried sites at Hamming
distance at most a fixed positive integer \(D\), including a step that
stays at the same site. Prospective center locations range over all of
\(Q_d\). Write \(V\) for the volume of a radius-\(r\) ball in \(Q_d\).
For levels \(0,\ldots,H\), the random experiment has three stages:
\begin{enumerate}[label=(\roman*),leftmargin=*]
\item At each vertex of \(Q_d\) and each level, independently, put a
prospective center with probability \(\lambda/V\), where
\(\lambda=n^{J_0}\) and the fixed constant \(J_0>2\). Write \(P\) for
all these prospective positions.
\item Using \(P\) and any auxiliary information, specify for every
site-level \((v,j)\) an eligible set \(E(v,j)\) of prospective centers in
its same-level \(r\)-ball. The required size is \(|E(v,j)|\ge\lambda/3\).
\item After those choices, activate each prospective center independently
with probability \(n^{b_0}/\lambda\). Write \(A\) for these activation
variables, where \(0b_0+(D+1)\rho\).
\end{itemize}
Choose fixed \(0<\sigma<\zeta<1\), \(0<\theta<1\), and \(a>0\) such that
\[
 b_0>a>\zeta+\sigma+(1-\theta),\qquad b>a+4\sigma.
\]

A space-level path stays in levels \([0,H]\). Its permitted steps are an
upward vertical step from a bad site-level, or a downward step of one
level together with a horizontal step. For a queried site \(v\), restrict
the whole path to spatial distance \(2DH\) from \(v\). Define the
\emph{long height} \(h(v)\) to be the largest \(j\) for which \((v,j)\)
is reachable by such a path from any level-zero start. A rule with a
shorter consultation radius restricts the same paths to the smaller ball.
If the resulting height equals \(H\) or its site-level is bad, the rule
makes no selection.

\begin{lemma}[Local height selection]\label{lem:height-selection}
In this experiment, take
\[
 R_0=\lceil\log^2 n\rceil,\qquad
 R_i=MR_{i-1},\qquad M=\lceil n^\sigma\rceil,
\]
and let \(H=R_h\) be the first scale at least \(n^{1-\zeta}\). Thus
\(H=O(n^{1-\zeta+\sigma})\).
\begin{enumerate}[label=(\roman*),leftmargin=*]
\item Except on an event of probability at most \(\exp(-n^{1+c})\), for
some fixed \(c>0\), whenever all eligible sets have the required sizes,
the long heights lie in \(\{0,\ldots,H-1\}\), their site-levels are good,
and their values differ by at most one on horizontal steps. Computing a
long height uses only bad statuses within spatial distance \(2DH\).
\item At a fixed site, on correct eligible-set sizes throughout its
consultation domain, the probability of positive long height is at most
\(\exp(-n^c)\) for some fixed \(c>0\). This remains true if one specified
prospective center is forced present.
\item If \(\theta>.9\), \(m=n^{\alpha+o(1)}\) for fixed \(\alpha>0\), and
\(\sqrt m\le H\), replacing the consultation radius by
\(D\lfloor\sqrt m\rfloor\) changes the path maximum with probability
\(o(\exp(-2m^{1/5}))\), on the same correct sizes. This estimate also
allows one forced prospective center.
\end{enumerate}
All bounds on correct sizes concern intersection with that event, not
conditioning on it. The local bounds in (ii) and (iii) also hold when,
for each fixed \(P\), one takes the supremum of the conditional activation
probability over fixed legal eligibilities, and only then averages over
\(P\).

At a good chosen height, independent pre-randomized site-level ties can
select a uniform eligible active ID. For fixed \(P,E\) of the required
sizes and a specified present ID \(c\) at level zero,
\[
 \Pr_{A,\,\mathrm{ties}}(h(v)=0\text{ and }c\text{ is selected}\mid P,E)
 \le 3/\lambda.
\]
The long and short rules may use the same ties and invalid-choice
conventions.
\end{lemma}

\begin{proof}
\noindent\textbf{Step 1: the path event to be estimated.}\quad
Use the metric
\[
 \operatorname{dist}((v,j),(v',j'))
   =\max\bigl(|j-j'|,\lceil d_H(v,v')/D\rceil\bigr).
\]
There are a bounded number of scales. Choose
\(1/4\le\eta_h<\cdots<\eta_0\le1/2\) with fixed positive gaps. A
scale-\(i\) failure from a specified point is a path stopped when it first
reaches metric distance \(R_i\), with net rise at least \(-\eta_iR_i\).
We will bound its probability by \(\exp(-n^aR_i^\theta)\), in the uniform
form specified below. The proof first finds many separated short failures inside a long one.
Their center balls may overlap. Removing the shared regions, while
allowing a small loss in the size and crowd thresholds, makes the short
failures depend on disjoint random inputs.

Fix a deterministic domain \(\mathcal D\) of allowed site-level paths and
a deterministic set \(\mathcal C\) of location-levels that may provide
centers. Both eligibility and crowd counts use only \(\mathcal C\).
At scale \(i\), require eligibility
size at least \(s_i\lambda\) and call a crowd bad above \(t_i n^b\), where
\(s_i\) increase strictly within \([1/8,1/4]\) and \(t_i\) increase
strictly within \([1/3,3/4]\), with fixed positive gaps. Let
\(F_i(P,E,A)\) be the scale failure from the specified start in these
domains with these thresholds. With \(\mathcal D,\mathcal C\) fixed, define
\[
 B_i(P)=\sup_E\Pr_A(F_i(P,E,A)\mid P,E),
\]
where eligible sets must have the stated sizes within metric distance
\(R_i\) of the start; the supremum is zero if no such sets exist. This
defines a random variable depending only on the prospective positions.
The induction claim, uniform in the two deterministic domains, is
\begin{equation}
 \mathbb E_P B_i(P)\le\exp(-n^aR_i^\theta).
 \label{eq:source-H}
\end{equation}
The actual thresholds are stronger:
actual legal sets have size at least \(\lambda/3\), and every actual bad
site-level remains bad when the crowd threshold is lowered to
\(t_i n^b\). Hence the same upper bound holds for failures in the original
experiment on correct sizes.

\noindent\textbf{Step 2: the smallest scale.}\quad
A scale-zero failure must contain an up-step. Without one, reaching
distance \(R_0\) requires at least \(R_0\) downward steps and gives net
rise at most \(-R_0\). An up-step identifies a bad site-level in the
metric ball of the start. There are at most
\(\exp(O(R_0\log n))\) possible such points.

For any fixed legal eligible set, a hole has conditional probability at
most \(\exp(-s_0n^{b_0})\). The crowd test does not depend on eligibility.
Unconditionally its count is binomial, with mean at most
\(n^{b_0}O(1)\) in the linear-radius case and
\(n^{b_0}O(n^{D\rho})\) in the sublinear case, by successive Hamming-layer
ratios. The assumed gap below \(b\) gives a binomial upper tail with
polynomial slack. The same union bound is valid after taking the
eligibility supremum: the hole bound is uniform in the eligible set,
and the crowd bound is independent of it. Since \(b_0>a\), these tails
and the count of possible points prove the induction at scale zero.

\noindent\textbf{Step 3: separated child paths and ball intersections.}\quad
Put \(R'=R_{i-1}\). A scale-\(i\) failure contains at least
\(q=\lfloor c'M\rfloor\) starts of scale-\((i-1)\) failures separated
by \(KR'\), with all child paths still inside the parent's metric ball.
Here the child paths temporarily use the parent's bad statuses; \(K\)
is a large fixed constant and \(c'>0\) is sufficiently small.

To see this, take a maximal separated set of child-failure starts. If it
has fewer than \(q\) members, their \(KR'\)-balls cover every such start.
Follow the parent path. Whenever it enters the cover, skip to its last
visit to the currently hit ball, accounting separately for one outgoing
step if necessary. No ball is used twice. These skips are bookkeeping:
each has endpoint displacement, and hence possible upward displacement,
at most \(2KR'\). Outside the cover, partition the path into pieces
stopped on first reaching distance \(R'\), with one unfinished piece per
intervening stretch. Every full piece has rise less than
\(-\eta_{i-1}R'\), since its start is not a child-failure start. The parent
displacement forces at least \(M-O((q+1)K)\) full pieces. Its total rise
is consequently at most
\[
 -\eta_{i-1}MR'+O((q+1)KR'),
\]
which is less than \(-\eta_iMR'\) when \(c'\) is small relative to the
gap \(\eta_{i-1}-\eta_i\). This contradicts the parent failure.

There are at most \(\exp(O(qR_i\log n))\) choices of these starts.
A child's center domain has levels within \(R'\) of its start and spatial
radius at most \(r+DR'+D\). For two separated children, either their
level intervals are disjoint or their spatial centers have distance
\(s\) at least a large multiple of \(R'\). At each common level, the
intersection of their enlarged balls has volume
\(V\exp(-\Omega(R'))\).

For this last estimate, a uniform point of one enlarged ball lies within
\(s/10\) of its outer layer except with probability
\(\exp(-\Omega(s))\), by the binomial-layer ratios. If it also lies in
the other ball, it must then flip at least \(.44s\) of the \(s\)
coordinates on which the centers differ. The enlarged radius is at most
\((1/4+o(1))d\), so this is a hypergeometric upper tail of probability
\(\exp(-\Omega(s))\). For sublinear radius, the enlarged ball has
radius at most \(n^{1-c''}\) for some fixed \(c''>0\); layer ratios and
a subset union bound for the differing coordinates improve both
exponents to \(\Omega(s\log n)\). Enlarging the original ball costs a
factor \(\exp(O(R'))\), or \(\exp(O(R'\log n))\) in the sublinear case.
Taking \(K\) large makes the intersection bound valid relative to \(V\)
in either case.

\noindent\textbf{Step 4: removing shared centers.}\quad
For a fixed configuration of child starts, delete every pairwise overlap
from each child center domain. The remaining regions are deterministic
and disjoint. Choose a small fixed \(\varepsilon>0\) below all the gaps
\(s_i-s_{i-1}\) and \(t_i-t_{i-1}\). Except on an event of probability
\(\exp(-\Omega(n^bR'/q))\) per pair and level, an overlap contains at most
\(\varepsilon\lambda/q\) prospective centers and
\(\varepsilon n^b/q\) active centers. Indeed their means are at most
\(\lambda e^{-\Omega(R')}\) and \(n^{b_0}e^{-\Omega(R')}\), respectively,
so the claimed estimates follow from binomial upper tails.

If none of these count exceptions occurs, each child loses at most
\(\varepsilon\lambda\) eligible centers and \(\varepsilon n^b\) active
centers. Its eligible sets still have size at least
\(s_{i-1}\lambda\). A hole stays a hole, while a crowd above \(t_i n^b\)
remains above \(t_{i-1}n^b\). Thus all the child failures transfer to the
private regions with the child thresholds.

The probability calculation must not condition on successful overlap
counts. Let \(C\) be the event that the chosen child configuration occurs,
let \(B_{\rm pos},B_{\rm act}\) be the prospective and active overlap
exceptions, and let \(P_\ell\) be the positions in the private region of
child \(\ell\). For every fixed legal eligibility assignment \(E\),
\[
 \begin{aligned}
 \Pr_A(C\mid P,E)
 &\le\mathbf1_{B_{\rm pos}}+\Pr_A(B_{\rm act}\mid P)
          +\prod_\ell b_\ell(P_\ell),\\
 b_\ell(P_\ell)
 &=\sup_{E_\ell}\Pr_A(\text{private child failure}\mid P_\ell,E_\ell).
 \end{aligned}
\]
The transferred events depend on disjoint activations once \(P,E\) are
fixed. Their probabilities are bounded by the displayed private
suprema, even if \(E\) used positions outside those regions. After
paying for the overlap exceptions we have discarded their complements,
so no conditioning remains to destroy independence. The inequality is
uniform in \(E\); taking its supremum and averaging \(P\) factors the
last product, because the \(P_\ell\)'s are independent. Induction bounds
the product of their expectations by \(\exp(-q n^a(R')^\theta)\).

The exponent exceeds both the logarithm of the configuration count and
the desired parent exponent. In fact, using \(R_i=MR'\), \(R'\le n\),
and \(q\asymp M\),
\[
 \frac{n^a(R')^\theta}{R_i\log n}
 \ge\frac{n^{a-\sigma-(1-\theta)+o(1)}}{\log n}\longrightarrow\infty,
 \qquad \frac{q}{M^\theta}\longrightarrow\infty.
\]
The ratio of an overlap-error exponent to the child exponent is at least
\(\Omega(n^{b-a-2\sigma}(R')^{1-\theta})\), which also tends to infinity
because \(b>a+4\sigma\). The number of pair-level exceptions is
polynomial. The union over configurations therefore proves
\eqref{eq:source-H} and the position-averaged induction claim.

If one prospective center is forced present, erase its location-level
from the deterministic center domain. The remaining positions have their
original independent laws. Each eligible set and crowd loses at most one
center, and
\(\lambda/3-1\ge s_i\lambda\), \(n^b-1\ge t_i n^b\) for large \(n\).
Holes persist. Every original bad-path witness therefore remains a
failure at the relaxed thresholds, uniformly in the erased center's
activation. The same induction applies.

\noindent\textbf{Step 5: heights and local approximations.}\quad
At the top scale,
\(n^aH^\theta\ge n^{a+(1-\zeta)\theta}\), whose exponent is greater
than one. Thus \eqref{eq:source-H} permits a union over all sites with
error \(\exp(-n^{1+c})\). A path from level zero that first displaces by
\(H\) would be a scale-\(h\) failure, since its endpoint still has
nonnegative level. Outside the exceptional event no such path exists.
The spatially unrestricted path maximum is therefore below \(H\), and
all paths relevant to a queried maximum lie in its \(2DH\) consultation
tube. A maximizing site-level is good, since otherwise the path could
extend upward. If neighboring maxima differed by more than one, a
downward horizontal step from the higher one would contradict maximality
at the lower site. This proves (i).

For a fixed query, classify paths reaching it by their maximum metric
displacement from their level-zero start. Below \(R_0\), positive height
requires an up-step at one of \(\exp(O(R_0\log n))\) possible points,
so Step 2 applies. For displacements in \([R_i,R_{i+1})\), the first
prefix reaching distance \(R_i\) is a scale-\(i\) failure. There are at
most \(\exp(O(R_{i+1}\log n))\) possible starts near the query. Hence
these paths have total probability at most
\[
 \sum_{i\sigma+(1-\theta)>\sigma\theta\) and \(\theta>.9\).
This proves (iii).

Finally, ignore the height and crowd requirements when bounding the
probability of selecting a specified level-zero ID. For fixed \(P,E\),
independent activation and a uniform tie give each member of \(E(v,0)\)
the same probability of selection, at most \(1/|E(v,0)|\le3/\lambda\).
Reinstating the requirements only decreases the joint probability.
Couple the long and short constructions with the same positions,
activations, eligibilities and ties. Whenever their path maxima agree,
the selected ID and its validity agree as well, as required when a short
rule is used inside a hypothetical-candidate calculation.
\end{proof}

\subsection{Near-product injections}
\label{sec:near-product-injections}

The two samplers below use finite row sets and finite output spaces. Row
\(i\) has a full output \(o\in\Omega_i\), with a specified label
coordinate in a common finite label set. Write \(\widehat p_i(o)\) for
its full-output law and \(p_i(y)\) for the label marginal. When there is
no side data these are the same law. An assignment is injective when its
label coordinates are distinct. A pointwise upper bound for prescribed
outputs can be summed against any nonnegative function of those outputs;
this is the form of comparison used later.

Preserving individual marginals while choosing distinct representatives is
an established feature of bipartite dependent rounding; see Gandhi,
Khuller, Parthasarathy and Srinivasan~\cite[Properties~(P1)--(P3)]{gandhi-khuller-parthasarathy-srinivasan2006}.
Their negative-correlation guarantee concerns edges incident to a common
vertex. The next lemma additionally controls prescribed outputs on
arbitrary distinct rows, with a relative error even when their
probabilities are very small.

\begin{lemma}[Calibrated near-product injections]\label{lem:near-product-injection}
Let a finite set of rows have laws on \(d\) labels, with
\(p_i(y)\le d^{-.95}\) and \(\sum_i p_i(y)\le .4\) for every label
\(y\). For sufficiently large \(d\), there is an injective random
assignment \((O_i)_i\) with exact individual full-output marginals
\(\widehat p_i\) and, for every set \(J\) of \(l\le d^{.025}\) queried
rows and prescribed outputs \((o_i)_{i\in J}\),
\begin{equation}
 \Pr(O_i=o_i\text{ for all }i\in J)
 \le \exp(d^{-.04}l)\prod_{i\in J}\widehat p_i(o_i).
 \label{eq:source-17}
\end{equation}
Targets with repeated labels have probability zero. After sampling the
labels, side data can be drawn independently from their conditional laws
given those labels. We use this sampler for assignments within small bins.
\end{lemma}

\begin{proof}
It suffices to construct the labels: the independent conditional draws
then give both assertions for full outputs.

\noindent\textbf{Step 1: complete the columns and order the rows.}\quad
First allow label atoms \(O(d^{-.95})\) and column sums at most \(1/2\).
If there are \(m\) real rows, then \(m\le d/2\). Put
\(t=\lceil2d/3\rceil\) and write \(c_y=\sum_{i=1}^m p_i(y)\).
Add \(t-m\) identical dummy rows with law
\[
 p_{\rm dum}(y)=\frac{t/d-c_y}{t-m}.
\]
The numerator is nonnegative and sums to \(t-m\), so this is a probability
law. Its atoms are \(O(1/d)\), and every completed column sums to \(t/d\).

Choose an order of the \(t\) rows, then number them in that order, such
that every column prefix satisfies
\[
 \sum_{k1/20\); any undefined continuation
after a stop may be declared a failure. We claim that, with probability
\(1-\exp(-d^{\Omega(1)})\), there is no stop and
\(D_j^a=s_j\pm d^{-.1}\) for all \(a,j\).

Before stopping, all sampling denominators are bounded away from zero.
Conditional on the first \(j-1\) draws, the drift of \(D_j^a\) is
\[
 \mathbb E[D_{j+1}^a-D_j^a\mid Y_1,\ldots,Y_{j-1}]
  =\sum_{y\ \mathrm{free}}\frac{p_a(y)p_j(y)}{1-D_j^j}.
\]
Its martingale increments are \(O(d^{-.95})\). Bounded-increment
concentration gives cumulative errors \(O(d^{-1/8})\), simultaneously
for all rows and times, outside an event of probability
\(\exp(-d^{\Omega(1)})\).

When summing the drifts through step \(b-1\), replacing \(1-D_j^j\) by
\(1-s_j\) costs at most
\[
 O\left(\sum_y p_a(y)\sum_{jj,\ i\ \mathrm{queried}}p_j(y_i)}{1-D_j^j}
       \quad(j\text{ ordinary}).
\]
After extracting \(\prod_i p_i(y_i)\), the target-step denominators and
the ordinary-step factors cancel to small relative error. For each target,
the prefix estimate and summation by parts give
\[
 \sum_{j0\) with the following property. Suppose
\[
 \sum_a p_a(y)\le\theta_0,\qquad p_a(y)\le n^{-A_*}
\]
for every label and row. Let a finite list of failure predicates have
probability at most \(n^{-P_*}\) under independent row outputs. Assume
each predicate reads at most \(n^B\) rows and each row belongs to at most
\(n^B\) predicate scopes. Then there is a random assignment with distinct
labels avoiding all predicates, such that for every set \(J\) of at most
\(n^B\) queried rows,
\[
 \Pr(O_a=o_a\text{ for all }a\in J)
       \le(1+o(1))\prod_{a\in J}\widehat p_a(o_a).
\]
The error is uniform over the rows and targets for fixed \(B\), the chosen
constants, and a fixed bound in \(\log g=O(n)\). Noninjective targets
have probability zero. Unneeded predicates and an empty assignment may
be ignored.
\end{lemma}

\begin{proof}
Choose \(K_0\) sufficiently large in terms of \(B\), then choose
\(A_*,P_*\) sufficiently large in terms of \(K_0,B\). We first construct
a greedy matching from independent edge clocks and use finite backward
explorations to detect failures. The proof gives two estimates: a joint
product bound for prescribed outputs, and a small total probability for
bad exploration outcomes involving any fixed row or label. The first
controls the raw matching law. The second lets
Lemma~\ref{lem:conditional-avoidance} enforce a match at every real row
and avoidance of every predicate, at a multiplicative cost \(1+o(1)\)
on the queried outputs.

\noindent\textbf{Step 1: trim rare outputs and complete the columns.}\quad
For each row \(a\) and incident failure predicate \(F\), discard outputs
\(o\) for which
\[
 \Pr(F\mid O_a=o)>n^{-P_*/2}
\]
under the product law. Markov's inequality bounds the discarded mass
for each predicate by \(n^{-P_*/2}\), so the total loss per row is at
most \(\varepsilon=n^{B-P_*/2}\). Renormalize the retained laws. A test
or query involves at most \(n^B\) rows, so this changes its probability
by at most \((1-\varepsilon)^{-n^B}=1+o(1)\). Under the new laws, every
predicate has probability at most \(n^{-P_*/3}\), both unconditionally
and after any one row in its scope is pinned to a retained output. We
continue to denote these laws by \(\widehat p_a,p_a\).

Put \(\theta=\lceil10^{-6}g\rceil/g\), and take
\(\theta_0=10^{-8}\), for example. If there are \(m\) real rows and
\(c_y=\sum_a p_a(y)\), add \(\theta g-m\) identical dummy rows with
law \((\theta-c_y)/(\theta g-m)\). This is a probability law because
its numerator sums to the denominator. The denominator is a positive
integer of order \(g\), even after the small trimming loss. Every
completed column sums to \(\theta\), and the dummy atoms are \(O(1/g)\).
The nonempty case has \(g\ge n^{A_*}\), since an original real row is a
probability law with atoms at most \(n^{-A_*}\). Thus the largest edge
rate in the completed row-label graph is
\(\lambda_*=O(n^{-A_*})\).

\noindent\textbf{Step 2: matching and its backward explorations.}\quad
Run an independent Poisson process of rate \(p_a(y)\) on every positive
row-label edge \((a,y)\). Each arrival has an independent mark drawn
from the conditional law of the full output given label \(y\). Through
time \(T_0=K_0\log n\), greedily match an arriving edge if both endpoints
are free. Only its first arrival can matter: if that arrival is rejected,
an endpoint is already matched and never becomes free again.

There are two types of tests. A predicate test fails if all rows in its
scope are matched and their outputs violate the predicate. A real
singleton-row test fails if that row is unmatched. For each test we also
forbid an excessively large exploration of the clocks needed to determine
its outcome.

Start that exploration with the scope rows as roots, each requesting its
matching history through time \(T_0\). An endpoint's requested horizon
is the latest time up to which its status is needed. Process the pending
endpoint with largest horizon. In a fixed order, inspect its incident
edges for first arrivals by that horizon, reusing information already
revealed. A hit at time \(t\) requests the other endpoint through a time
strictly before \(t\); retain the largest request if it is requested
again. Horizons are processed in decreasing order, so a processed
endpoint can never receive a larger request. These inspections determine
the matching decisions at the roots by backward closure through all
earlier events they require.

The active endpoints are the roots and every endpoint reached by a hit,
including pending and processed endpoints. Stop with a \emph{giant}
failure as soon as their number reaches \(L=\lceil n^{.1K_0}\rceil\).
Register the endpoint of the last hit before stopping. Consequently every
inspected hit always has both endpoints active, even on a giant leaf.

\noindent\textbf{Step 3: exploration leaves and nonneighbor conditioning.}\quad
Eventually we discretize first-arrival times with a sufficiently fine
finite mesh and a fixed tie order. A leaf of an exploration then specifies
a product rectangle in the independent edge data. A hit pins an arrival
bin and mark on an edge whose two endpoints are active. A negative
inspection requires absence up to a specified cutoff on an edge with at
least one active endpoint. Every realization in this rectangle follows
the same inspections and reaches the same leaf.

Use the individual bad leaves as forbidden events, joining two leaves
when their active endpoint sets intersect. Leaves with disjoint active
sets can share an inspected edge only if both require absence on it.
To force a positive-probability leaf, condition its edges separately. On
absence edges couple the conditional first time to be no earlier than
the old time; on hit edges fix the required data; leave other edges
unchanged. Every already occurring nonneighbor leaf still occurs. This
holds simultaneously for any collection of nonneighbors, even if they
overlap with one another. If \(A\) is avoidance of such a collection
and \(E\) is the forced leaf, the coupling gives
\(\Pr(A\mid E)\le\Pr(A)\), hence
\(\Pr(E\mid A)\le\Pr(E)\) whenever defined.

It remains to show, uniformly in an endpoint \(u\), that
\[
 \sum_{\substack{E\ \mathrm{bad\ leaf}:\ u\ \mathrm{active\ in}\ E}}
       \Pr(E)\le n^{-.6K_0}.
\]
Equivalently, sum over tests the probability that the test has a bad
outcome and its exploration reaches \(u\). We prove this in continuous
time before choosing the mesh.

\noindent\textbf{Step 4: inserted paths bound the incidence sum.}\quad
Reaching \(u\) from a test's roots requires a path of time-decreasing
arrivals from one of its root rows to \(u\). Such a certificate uses
distinct edges, since the exploration inspects first arrivals; the empty
path is allowed. For a fixed edge path, count its possible distinguished
arrival tuples. Poisson insertion expresses their expected count,
with a specified bad outcome, as the integral of the product of edge
rates over ordered times in \([0,T_0]\), multiplied by the bad-outcome
probability in an ordinary realization with those arrivals inserted.
This identity follows directly by summing over the Poisson counts and
distinguishing one of their uniform-time points on each edge. Inserted
marks may be fixed anywhere in their support for uniform estimates.

To sum certificates, reverse them from \(u\) and allow all walks. Total
outgoing rates alternate between \(1\) at a row and \(\theta\) at a
label. The integrated rate sum for a start at a row is
\[
 \sum_{j\ge0}\theta^{\lfloor j/2\rfloor}\frac{T_0^j}{j!}
 =\cosh(\sqrt\theta T_0)+\theta^{-1/2}\sinh(\sqrt\theta T_0)
 =O(e^{\sqrt\theta T_0}/\sqrt\theta).
\]
Starting at a label only decreases this upper bound. Each root row
belongs to at most \(n^B+1\) tests. Lengths above
\(K_0^2\log n\) contribute less than \(n^{-K_0^2}\) before this
incidence factor, by the factorial tail of the series.

For shorter paths, first dispose of those meeting two distinct rows of
the same test, bounding the bad-outcome probability simply by one. Choose
their two positions on the path and a test incident to the earlier row.
In the normalized reversed walk, a subsequent label-to-row transition
enters that test's scope with probability at most
\(n^B\lambda_*/\theta\). Their total contribution is therefore at most
\[
 O(e^{\sqrt\theta T_0}/\sqrt\theta)(1+\log n)^{O(1)}
       (n^B+1)n^B\lambda_*/\theta.
\]
The remaining short insertions meet at most one row of the test. We now
bound bad outcomes uniformly under each such insertion.

\noindent\textbf{Step 5: the exploration rarely becomes giant.}\quad
Include the endpoints of all inserted arrivals as extra full-horizon
roots. Every reached endpoint is connected to one of these roots by
ordinary arrivals: take the part of its reaching path after the last
inserted hit. There are at most \(n^B+O(\log n)\) roots.

During largest-horizon processing, an edge from the current endpoint to
an unprocessed endpoint is fresh: neither of its endpoints could have
inspected it earlier. Superpose the fresh arrivals and, when necessary,
independent extra arrivals to reach total rate \(1\) at row endpoints
and \(\theta\) at label endpoints. They are dominated by a two-type
branching forest. A node with horizon \(t\) has Poisson children of the
opposite type at times in \([0,t]\), each child inheriting its arrival
time as horizon. To handle repeated requests for a graph endpoint,
attach its sole processing to the node making its highest request;
its offspring have not yet been generated. Unused tree nodes can be
filled with independent subtrees. This deferred construction dominates
the active endpoint count by the forest's total progeny.

For \(\delta=n^{-.01K_0}\), let \(H_{\rm row}(t)\) and
\(H_{\rm label}(t)\) be the exponential moments of single-root progeny,
including the root. They satisfy
\[
 \begin{aligned}
 H_{\rm row}(t)&=\exp\left(\delta+
                    \int_0^t(H_{\rm label}(s)-1)\,ds\right),\\
 H_{\rm label}(t)&=\exp\left(\delta+
                    \theta\int_0^t(H_{\rm row}(s)-1)\,ds\right).
 \end{aligned}
\]
Induction on truncated generations bounds their excesses above one by
\(4\delta e^{2\sqrt\theta t}/\sqrt\theta\) and
\(4\delta e^{2\sqrt\theta t}\), respectively. Substitution proves
these bounds using \(e^x-1\le2x\) for the resulting small positive
exponents. With \(R\le n^B+O(\log n)\) roots, exponential Markov gives
\[
 \Pr(\text{giant})\le
 \exp\left(-\delta L+
      O(R\delta e^{2\sqrt\theta T_0}/\sqrt\theta)\right).
\]
Here \(\delta L\ge n^{.09K_0}\), while the second term is
\(O(n^{B-(.01-2\sqrt\theta)K_0})\). Choosing
\((.1-2\sqrt\theta)K_0>B\) makes this tail superpolynomially small,
uniformly in the fixed short insertion.

\noindent\textbf{Step 6: track the free mass in a background process.}\quad
Fix a prescription removing at most \(2n^B\) endpoints and inserting
\(O(\log n)\) arrivals between the remaining endpoints. In the resulting
background matching define, even for original endpoints that were removed,
\[
 X_a(t)=\sum_{y\ \mathrm{free\ in\ background}}p_a(y),\qquad
 R_y(t)=\sum_{a\ \mathrm{free\ in\ background}}p_a(y).
\]
These are the available label mass of a row and the available row mass
at a label. The deterministic comparison functions solve
\[
 z'=-qz,\qquad q'=-\theta zq,\qquad z(0)=q(0)=1.
\]
In particular \(q=1-\theta+\theta z\) and \(02K_0+3B\), with slack, proves the claim and its stated
exception probability.

\noindent\textbf{Step 7: ordinary target matches have a product upper bound.}\quad
Fix \(k\le n^B\) full-output targets with distinct labels, also allowing
any fixed short insertion from Step 4. Count tuples of ordinary arrivals
that realize all the target matches. Insert their distinguished arrivals
at candidate times \(t_1,\ldots,t_k\). Their intensities factor out the
entire product \(\prod_a\widehat p_a(o_a)\), including all prescribed
marks, before any probability estimate is made.

If these are the target matches, none of their endpoints ever matches
to an outside endpoint. The outside process therefore agrees exactly
with the background obtained by removing the queried rows and target
labels, keeping the fixed inserted arrivals between remaining endpoints.
Given this background, an ordinary arrival from a target endpoint to a
free outside endpoint is forbidden before its candidate matching time.
These are disjoint clocks independent of the background. Ignoring other
necessary conditions gives the following upper bound for the remaining
time integrand:
\[
 \mathbb E\exp\left(-\sum_{(a,y_a)}
           \int_0^{t_a}(X_a(s)+R_{y_a}(s))\,ds\right).
\]
The ODE identity
\((\log(zq))'=-(q+\theta z)\) and Step 6 bound this, on the tracking
event, by \((1+o(1))\prod_a z(t_a)q(t_a)\): its logarithmic error is
at most \(kT_0\,o(n^{-3B})=o(1)\). After integrating the times, the
ordinary-target probability is at most
\[
 \left(\prod_a\widehat p_a(o_a)\right)
 \left[(1+o(1))\left(\int_0^{T_0}z(t)q(t)\,dt\right)^k
                 +T_0^k e^{-n^{A_*/3}}\right]
 \le(1+o(1))\prod_a\widehat p_a(o_a).
\]
Indeed \(\int_0^{T_0}zq=1-z(T_0)\le1\), and the second term is
\(o(1)\) for our choice of \(A_*\). In particular the tracking exception
still carries the full target product; the bound is relative even for
arbitrarily small positive atoms.

For an unmatched singleton, remove just its row. The same absence
calculation gives \(\mathbb E\exp(-\int_0^{T_0}X_a(s)\,ds)\) as an
upper bound. Since \(q\ge1-\theta\), its probability under the short
insertion is at most \(n^{-(1-\theta)K_0+o(1)}\).

\noindent\textbf{Step 8: bound bad leaves and impose avoidance.}\quad
For the remaining short path and predicate pairs, at most one row of the
predicate lies on the path. If all its matches are ordinary, sum Step 7
over its failing output tuples. Otherwise one match uses an inserted
arrival at that row. Pin its output, discard its match requirement, and
sum the ordinary-target bounds for the other rows using the one-pinned
failure estimate from Step 1. There are \(O(\log n)\) inserted arrivals
to consider. In either case the matched-failure probability is at most
\(O(1+\log n)n^{-P_*/3}\).

Multiply these estimates and the giant bound by the path and test factor
\(O((n^B+1)n^{\sqrt\theta K_0}/\sqrt\theta)\) from Step 4. The
unmatched contribution is at most
\(n^{B-(1-\theta-\sqrt\theta)K_0+o(1)}\). The two-row exception is
at most \(n^{2B+\sqrt\theta K_0-A_*+o(1)}\), and long paths cost
\(O(n^{B-K_0^2})\). Choose \(K_0\) so that
\(B<(.4-\theta-\sqrt\theta)K_0\), in addition to Step 5's condition;
then take \(A_*,P_*\) large enough for the other terms and tracking.
Every contribution has a fixed power of slack below \(n^{-.6K_0}\).
This proves the active-endpoint bound from Step 3.

Choose the time mesh sufficiently fine for this bound to persist.
Continuous arrival times are distinct almost surely; matching decisions
and truncated explorations therefore converge almost surely as the
mesh is refined. There are finitely many tests, endpoints and full-output
target products. We may also preserve the raw joint target bound, with
no path insertions, with negligible relative loss at every positive
product. The discretized exploration now has finitely many leaves.

Assign each bad leaf charge twice its raw probability. A leaf has at
most \(L\) active endpoints, so its total neighboring charge is at most
\(2L n^{-.6K_0}=O(n^{-.5K_0})\). Thus its probability is at most its
charge times the product of its neighbors' avoidance factors, and
Lemma~\ref{lem:conditional-avoidance} supplies simultaneous avoidance.
All real rows are then matched, all listed predicates are avoided, and
all the required explorations are nongiant.

Finally partition any joint target event by the non-giant singleton
leaves of its queried rows. Their intersections are product rectangles
with at most \(n^B L\) active endpoints. They have the same forcing
property against bad leaves with disjoint active sets. The total
neighboring charge is at most \(2n^B L n^{-.6K_0}\), so the avoidance
comparison costs
\(\exp(O(n^{B-.5K_0}))=1+o(1)\). Summing the rectangles gives the raw
joint target bound from Step 7. The initial trimming normalization costs
another \(1+o(1)\), proving the assertion for the original full-output
laws.
\end{proof}
==== END The-hypercube-Ramsey-number-has-linear-order//sections/03-general-conventions-and-probabilistic-tools.tex ====

==== BEGIN The-hypercube-Ramsey-number-has-linear-order//sections/04-bias-versus-purity-at-power-widths.tex ====
\section{Bias versus purity at power widths}
\label{sec:bias-versus-purity-at-power-widths}

At prescribed power widths, the next lemma combines an available density
surplus with the absence of nearly monochromatic patches at doubled width
budgets to construct a cube. Its contrapositive will be the first reduction
toward discrepancy.

\begin{lemma}[Bias versus purity]\label{lem:bias-purity}
Fix constants \(0<\beta\le\gamma<1\). For \(h=h(\beta,\gamma)>0\) chosen below, the following two hypotheses cannot both hold along a bad sequence:
\begin{enumerate}[label=\textup{(\roman*)}]
\item\label{it:bias-purity-available} Pairs of laws at widths \(\le n^\beta,n^\gamma\) on \(X,Y\) respectively with absolute bias \(\ge n^{-h}\) from half are available;
\item\label{it:bias-purity-excluded} On the current sets there is \textbf{no} pair at respective widths \(\le2n^\beta,2n^\gamma\) having defect \(\le\exp(-n^h)\) in either color. Defect for a color means density of its complement.
\end{enumerate}
Equivalently, their simultaneous validity yields a monochromatic cube.
\end{lemma}

\begin{proof}
We will first prepare pairs of laws \((\mu_i,\nu_i)\) with a density
surplus in one color \(G\), and distribute these pairs over the cube.
An even role will share a hidden tuple of \(X\)-labels with nearby even
roles. The odd roles receive laws on \(Y\) restricted to common neighbors
of the tuples they encounter. After assigning distinct odd labels, the
posterior law of an even role's tuple will show that those labels have a
large common neighborhood in \(X\). Masks on the patch laws will balance
the resulting label loads, allowing Hall's theorem to assign the even
roles distinctly as well.

\noindent\textbf{Step 1: a density plateau.}\quad
Set
\[
 \omega=\min(\beta,1-\gamma)/1000,\quad h=\omega/10^6,\quad
 k=\lceil n^{\omega/3}\rceil,\quad L=n^h,\quad a_*=n^{-h}.
\]
Here \(k\) will be the tuple length, \(e^{-L}\) the minimum acceptable
fraction retained by a single common-neighbor restriction, and \(a_*\)
the density surplus we must preserve.

Take residual label sets containing a witness in
hypothesis~\ref{it:bias-purity-available}. For each integer
\(0\le j\le\lfloor n^{\omega/2}/2\rfloor\), let \(P_j\) be the largest
density in either color among laws on those sets with width budgets
\[
 (s_X(j),s_Y(j))=(n^\beta,n^\gamma)
             +j(n^{\beta-\omega/2},n^{\gamma-\omega/2}).
\]
These maxima exist by compactness and form a nondecreasing sequence in
\([0,1]\), starting at least at \(1/2+a_*\). If every consecutive
increase were at least \(n^{-\omega/3}\), their sum would exceed one
for large \(n\). Choose a step with \(P_{j+1}-P_j0\), and the total
mean is bounded. Bounded-summand concentration therefore bounds a fixed
positive deviation from that mean by
\(\exp(-\Omega(\exp(c n^{\gamma+\omega})))\).
Since there are at most \(2N=\exp(O(n))\) label
coordinates, one assignment meets all the bounds. Fix it henceforth.

\subsection{Hidden tuples and height choices}
\label{sec:hidden-tuples-and-height-choices}

\noindent\textbf{Step 3: tuples and the masses retained by their filters.}\quad
The height device will let nearby even roles choose from a common set of
tuple indices. Use Lemma~\ref{lem:height-selection} on the even sites of
\(Q_n\), with
\[
 D=2,\quad b=\omega/30,\quad b_0=b/4,\quad \rho=b_0/10,
 \quad r=\lfloor n^{1-\rho}\rfloor,\quad \lambda=n^{10},
 \quad\zeta=b_0/20,\quad\sigma=\zeta/10.
\]
Choose \(\theta,a\) there to satisfy its inequalities, and use its height
bound \(H\). The logarithm of the volume of an \(O(r+H)\)-neighborhood
is \(o(a_*n)\). Set \(T=\lceil3n^b\rceil\); it bounds the number of
indices that an odd role's neighbors will collectively select.

A mask for a law is a subset of its support of mass at least \(1/2\);
the superscript \(M\) denotes conditioning on that subset. For now give
each mask an arbitrary distribution, independently of all other masks.
For every possible center ID \(c\) (a location and a level) and key \(g\),
choose a mask for \(\mu_{i_g}\) and draw a tuple \(W_{c,g}\) of \(k\)
independent labels from \(\mu_{i_g}^M\). Tuples and masks for different
pairs \((c,g)\) are independent. Each odd role \(u\) also has an
independent mask for \(\nu_{i_{g(u)}}\). We generate these data even for
IDs whose centers will be absent. They are independent of prospective
center positions, activations, and the ties used to choose active centers.

The same tuple \(W_{c,g}\) will be used in every odd filter that mentions
\((c,g)\). If an even role \(v\) selects \(c\), and its odd neighbors
eventually receive labels \(\mathbf y=(y_u:u\sim v)\), its available
label set is
\[
 S_{v,c}(\mathbf y)=
 \{x\in\operatorname{supp}\mu_{i_{g(v)}}^M:
                         xy_u\in G\text{ for every }u\sim v\},
\]
where the mask is the one belonging to \((c,g(v))\). We will bound the
posterior density of \(W_{c,g(v)}\), supported on this set's \(k\)th
power, to prove that the set is large. The next estimates quantify how
much an odd filter changes when this entire shared tuple is removed.

For an odd role \(u\) and an ID set \(\mathcal D\) with
\(1\le|\mathcal D|\le T\), define the retained mass
\[
 R_u(\mathcal D)=\sum_y\nu_{i_{g(u)}}^M(y)
       \prod_{c\in\mathcal D}\prod_{g'\in Z_u}
       \prod_{x\text{ an entry of }W_{c,g'}}1_{\{xy\in G\}}.
\]
Let \(R_u^{-(c,g')}(\mathcal D)\) be the same expression with all
requirements from the single indexed tuple \(W_{c,g'}\) omitted.
Other tuples with ID \(c\) remain in this expression. We call the set
\(\mathcal D\) valid at \(u\) if
\[
 R_u(\mathcal D)\ge\exp(-Lk|\mathcal D||Z_u|)
\]
and, for every \(c\in\mathcal D\) and \(g'\in Z_u\),
\[
 \frac{R_u(\mathcal D)}{R_u^{-(c,g')}(\mathcal D)}\ge
 \begin{cases}
 \exp(k(-\log2+c_1a_*)),&g'=g(u),\\
 \exp(-Lk),&g'\ne g(u),
 \end{cases}
\]
where \(c_1>0\) is a fixed small absolute constant. The first condition
ensures that every denominator in these ratios is positive. These
filters use the common-neighborhood sampling operation of dependent
random choice~\cite[Lemma~2.1]{fox-sudakov2009}. We also need their mass
ratios because deleting one tuple will later remove dependence on a
hypothetical even candidate.

For fixed masks, positions, and \(\mathcal D\), the probability that
\(\mathcal D\) is invalid is at most \(\exp(-n^{\omega/5})\). We prove
this by exposing the tuple entries successively, with any specified
tuple placed last. Call an exposed prefix successful if every hit
fraction in it is at least \(e^{-L}\); no condition is imposed on later
entries. After a successful prefix, let \(\eta\) be the law on \(Y\)
remaining after those hit requirements. Their total width cost is at most
\[
 O(kT|Z_u|L)=o(n^{\gamma-\omega/2}).
\]
For the next entry \(x\), drawn from its masked first law, put
\(q(x)=d_G(x,\eta)\). This is the fraction of current mass retained by
that entry. Its probability of being below \(e^{-L}\) is at most
\(\exp(-n^{\beta-\omega/2}/4)\). Otherwise conditioning the incoming
first law on these values of \(x\) would cost at most
\(n^{\beta-\omega/2}/4\) additional width. Together with \(\eta\), it
would give an opposite-color patch of defect below \(e^{-L}\), within
the doubled budgets, contrary to hypothesis~\ref{it:bias-purity-excluded}.

When this entry has key \(g(u)\), both laws lie in the same prepared
patch \(i=i_{g(u)}\). The intrinsic upper density bound from Step 1 also
gives
\[
 \Pr\{q(x)>p+n^{-\omega/3}\}
       \le\exp(-n^{\beta-\omega/2}/4).
\]
Indeed conditioning on a larger exceptional set would fit the first
width margin, and \(\eta\) fits the second margin. For the lower mean
bound, note that \(2\mu_i-\mu_i^M\) is a probability law of density at
most two relative to \(\mu_i\). Since \(\eta\) is supported on the
trimmed second support, the column lower bound and then the intrinsic
upper bound give
\[
 \begin{aligned}
 \mathbb E_{x\sim\mu_i^M}q(x)
 &=2d_G(\mu_i,\eta)-d_G(2\mu_i-\mu_i^M,\eta)\\
 &\ge2(p-n^{-\omega/5})-(p+n^{-\omega/3})
 \ge p-3n^{-\omega/5}.
 \end{aligned}
\]
These estimates hold conditional on each fixed successful prefix.
Comparing the mean with the upper bound for \(q\), and allowing the
exponentially small exceptional set, shows that
\[
 \Pr\{q0,\qquad M_c\ge e^{-c_2a_*kn/4}Q.
\]
The posterior \(F_z\,d\pi(z)/M_c\) then has density relative to the
uniform product law on the original \(N\)-label side \(X\), with current
laws extended by zero to discarded labels, at most
\[
 \exp((\log2-c_2a_*/2)kn).
\]
Indeed division by the displayed threshold uses \(c_2a_*kn/4\) of the
gain, and the masked first width is \(o(a_*n)\), leaving the stated
bound after multiplying the \(k\) prior density factors.
Writing \(S=S_{v,c}(\mathbf y)\), the posterior is supported on
\(S^k\), so
\[
 1\le\exp((\log2-c_2a_*/2)kn)(|S|/N)^k,
 \qquad |S|\ge N\exp(-(\log2-c_2a_*/2)n).
\]
Define \(p_v\) to be uniform on \(S\) if the selected reference meets
\(E\) and the predictive threshold, and zero otherwise. This even
subprobability uses only the local preparatory data and neighboring odd
labels. Whenever it is nonzero, its support is a common neighborhood in
the same color \(G\).

\subsection{Balance and load transfer}
\label{sec:balance-and-load-transfer}

\noindent\textbf{Step 6: choosing mask distributions to balance the rows.}\quad
For this step use the raw experiment with conditionally independent odd
draws given the preparatory data, including fallbacks where necessary,
and without conditioning on geometric success. We will choose the mask
distributions so that
\[
 \mathbb E p_u\le2\nu_{i_{g(u)}}\quad(u\in B),\qquad
 \sum_{v\in A}\mathbb E p_v
       \le K'\sum_{v\in A}\mu_{i_{g(v)}}
\]
coordinatewise, for a fixed \(K'\).

The player choosing the odd mask at \(u\) controls the output vector
\(\mathbb E p_u\). Given nonnegative label prices on \(Y\), retain the
labels with price at most twice the \(\nu_{i_{g(u)}}\)-mean price.
They have mass at least one half. Every nonzero \(p_u\) is supported
there and has mass at most one, so its expected price is at most twice
that mean, regardless of the other mask profiles. Separation therefore
gives a mixture of masks meeting this player's vector bound.

The player for \((c,g)\) instead controls the sum of outputs from even
rows with key \(g\) selecting ID \(c\). Let \(n_{c,g}\) be the number
of even roles with key \(g\) whose radius-\(r\) balls contain the
location of \(c\), regardless of its presence or selection. This count
is deterministic. Put
\[
 w_c=(\lambda/V)
 \begin{cases}
 3/\lambda,&\text{level zero},\\
 \exp(-n^{c_3}),&\text{otherwise},
 \end{cases}
\]
where \(V\) is the radius-\(r\) ball volume and \(c_3>0\) is small and
fixed. The probability that one such row selects \(c\) with event \(E\)
is at most \(w_c\). Presence of \(c\) costs \(\lambda/V\); given
presence, Lemma~\ref{lem:height-selection} bounds its level-zero choice
probability by \(3/\lambda\), and a positive height by
\(\exp(-n^{c_3})\). The local size condition in \(E\) is retained in
this application. The lemma's position-averaged bound is uniform over
the legal eligibility sets, so the bound remains valid for the masks
and tuple-dependent eligibility used here.

Given prices on \(X\), this player can likewise choose a mask whose
prices are at most twice their \(\mu_{i_g}\)-mean. Every even output
attributed to this player is supported in that mask. Multiplying its
price bound by the probability \(w_c\) of selecting \(c\) shows that
the player's expected output vector can be bounded by
\(2n_{c,g}w_c\mu_{i_g}\), again by separation. The output rules for
fixed masks do not depend on their profile probabilities: in particular,
the posterior computations condition on the realized masks. Thus
Lemma~\ref{lem:balanced-profiles} supplies simultaneous profiles for
all players.

For any fixed even role \(v\), summing \(w_c\) over IDs in its range
costs at most \(3\) at level zero and at most
\(H\lambda\exp(-n^{c_3})=o(1)\) over the other levels. Summing the
players' vector bounds proves the even inequality. The fixed patch-tag
assignment from Step 2 now shows that the parity averages of
\(N\mathbb E p_u(y)\) and \(N\mathbb E p_v(x)\) are bounded by
constants at every label.

\noindent\textbf{Step 7: assigning odd labels and controlling even loads.}\quad
First bound odd column sums in the preparatory experiment. The weights
\(Np_u(y)\) have cap \(\exp(O(n^\gamma))\), bounded average means by
Step 6, and independent local inputs for roles separated by more than
\(O(r+H)\). A near set has parity fraction at most
\(\exp(-n\log2+o(a_*n))\). Hence its contribution times \(n\) and
the cap tends to zero. Lemma~\ref{lem:scattered-moments}, followed by
Markov's inequality and the union over labels, bounds every normalized
average odd load by a constant with probability tending to one.
Since \(|B|/N=1/(2C_n)\to0\), the actual column sums are then at most
\(1/10\).

Write \(\mathcal H\) for the preparatory history and
\(S_{\rm pre}\) for geometric success together with the odd column
bound. On \(S_{\rm pre}\), all odd rows are probabilities and meet the hypotheses of
Lemma~\ref{lem:near-product-injection} with \(d=N\): their maximum atom
is \(N^{-1}\exp(O(n^\gamma))\le N^{-.95}\) eventually, the column
bound is less than \(.4\), and \(n^2\le N^{.025}\). Let
\(\mathsf J_{\mathcal H}\) be the resulting odd injection law, and
let \(\mathsf P_{\mathcal H}\) be the auxiliary product law of the odd
draws. For every nonnegative function \(\Phi\) of at most \(n^2\) odd
outputs, the joint target bound gives
\[
 \int\Phi(\mathcal H,\mathbf y)\,d\mathsf J_{\mathcal H}
 \le \exp(N^{-.04}n^2)
       \int\Phi(\mathcal H,\mathbf y)\,d\mathsf P_{\mathcal H}
       \qquad(\mathcal H\in S_{\rm pre}).
\]
The comparison factor is \(1+o(1)\), uniformly in the entering history.

We next show that all selected even references meet the predictive
threshold of Step 5 with probability tending to one. For a fixed even
role \(v\) and possible reference \(c\), let
\(\epsilon=e^{-c_2a_*kn/4}\) and let \(D_c\) be the set of neighboring
data with \(M_c=0\) or \(M_c<\epsilon Q\). Apply the comparison with
\(\Phi=1_E1_{D_c}\), then average the preparatory histories with
\(1_{S_{\rm pre}}\) retained. Removing this last indicator increases
the resulting product-draw integral. Its remaining indicator \(1_E\)
makes the neighboring likelihood exactly \(F_z\), because the odd
kernels are valid on \(E\). With the other preparatory data fixed,
integration over the original masked tuple prior therefore gives
\[
 \sum_{\mathbf y\in D_c}\int F_z(\mathbf y)\,d\pi(z)
   =\sum_{\mathbf y\in D_c}M_c(\mathbf y)
   \le\epsilon\sum_{\mathbf y\in D_c}Q(\mathbf y)
   \le\epsilon.
\]
There are at most \(|A|(H+1)V=\exp(O(n))\) role--ID pairs, whereas
\(a_*kn=n^{1+\omega/3-h+o(1)}\). Thus their total predictive-failure
probability is \(o(1)\). The probability here is under the experiment
that first draws the preparatory history and then, on \(S_{\rm pre}\),
draws the odd injection. Failure to reach \(S_{\rm pre}\) also has
probability \(o(1)\); earlier histories have not been reweighted by the
probability of later success.

Let \(S_{\rm good}\) be \(S_{\rm pre}\) intersected with the event
that every selected even reference passes its predictive requirement.
It remains to control the even column sums after this odd injection.
On \(S_{\rm good}\), the normalized even rows have cap
\(\exp((\log2-c_2a_*/2)n)\). With the same near fraction as above,
\[
 n\exp(-n\log2+o(a_*n))
       \exp((\log2-c_2a_*/2)n)=o(1).
\]
For the separated factors in an \(n\)th moment, their even kernels
consult at most \(n^2\) odd rows in total. The event \(S_{\rm good}\)
also tests references at other roles, so first use
\[
 1_{S_{\rm good}}\prod_{j=1}^{\ell}Np_{v_j}(x)
       \le 1_{S_{\rm pre}}\prod_{j=1}^{\ell}Np_{v_j}(x),
       \qquad \ell\le n.
\]
Each factor on the right still contains its own local validity and
predictive requirements. Conditional on the entering history, the product
of these factors is therefore a function of at most \(n^2\) odd outputs,
to which the displayed injection comparison applies. Only after that
comparison remove \(1_{S_{\rm pre}}\), which restricts the preparatory
history. In the resulting raw experiment the separated kernels depend on
disjoint center data, masks, and odd draw seeds. The patch tags are
already fixed. Their expectations thus factor, and their individual
means are those bounded in Step 6. Explicitly, for separated
\(v_1,\ldots,v_\ell\), \(\ell\le n\), and a fixed label \(x\),
\[
 \mathbb E\!\left[1_{S_{\rm good}}
                  \prod_{j=1}^{\ell}Np_{v_j}(x)\right]
       \le(1+o(1))\prod_{j=1}^{\ell}
                    \mathbb E_{\rm raw}[Np_{v_j}(x)].
\]
This is the separated-product hypothesis of
Lemma~\ref{lem:scattered-moments}; the displayed cap estimate handles
nearby factors.

It follows that, except for probability \(o(1)\) on \(S_{\rm good}\), every even
column sum is at most one. Intersect this event with the preceding
success events. All even rows are now probabilities supported on common
\(G\)-neighbors of the assigned odd labels, so Hall's
theorem~\cite{hall1935} assigns them distinct representatives. The even
images lie in \(X\) and the odd images in the disjoint side \(Y\);
every cube edge has color \(G\). This gives the required contradiction
and proves the assertion, including \(\beta=\gamma\).
\end{proof}
==== END The-hypercube-Ramsey-number-has-linear-order//sections/04-bias-versus-purity-at-power-widths.tex ====

==== BEGIN The-hypercube-Ramsey-number-has-linear-order//sections/05-a-constant-broad-high-neighborhood-case.tex ====
\section{A broad side of constant width}
\label{sec:a-constant-broad-high-neighborhood-case}

To turn Lemma~\ref{lem:bias-purity} into initial discrepancy, we need to
exclude available nearly pure patches with two small power widths. We
approach this through two broad-side constructions. The present
constant-width lemma handles an opposite-color alternative in the proof
of Lemma~\ref{lem:small-polynomial-broad-side}. The latter allows the
broad-side law to have a small polynomial density cap, or equivalently
logarithmic width. After stabilization, it supplies the lower bound on
both color densities in~\eqref{eq:source-1}, which the grid construction
of Section~\ref{sec:a-small-power-key-grid} uses to exclude these available
nearly pure patches.

\begin{lemma}[A broad side of constant width]
\label{lem:constant-broad-high-neighborhood}
Work in the counterexample sequence fixed above. Suppose for one color \(G\) there is a finite random tag \(I\) with laws \(\mu_I\) on \(X\) of width \(\le n^\gamma\) (\(0<\gamma<1\) fixed), \(\mathbb E\mu_I\le K'_0/N\) pointwise. For each \(I\), at least \(\chi N\) columns \(y\in Y\) have \(d_G(\mu_I,y)\ge .95\), with \(K'_0,\chi>0\) fixed. This yields a \(G\)-cube for large \(n\).
\end{lemma}

\begin{proof}
We construct probability rows on \(Y\) for the odd roles, assign them
injectively, and then construct rows on their common neighborhoods in
\(X\). The individual laws \(\mu_I\) may be too concentrated to serve a
constant fraction of the cube. Their balanced average will instead control
the mean loads of short random tuples in \(X\).

Each such tuple will be sampled to see several random columns. These
column requirements must vary across odd roles to spread their loads,
while only a small number of distinct requirements may occur around one
even role. We arrange this using counts and majority signs of disjoint
chunks of cube coordinates. Posterior distributions then relate three
objects: columns given streams of first-side labels, stream blocks given
those columns, and odd labels given the resulting blocks. All these
posteriors refer to specified raw experiments. We impose their numerical
bounds later, one sampling stage at a time.

\subsection{Parents, column indices and even types}
\label{sec:parents-macro-keys-and-even-types}

Call \(y\) good for \(I\) if \(d_G(\mu_I,y)\ge .95\), and define
\[
 (y,y')\in\mathcal H
 \quad\Longleftrightarrow\quad
 \Pr_I(y\text{ and }y'\text{ are good for }I)\ge\chi^2/2.
\]
The average of this probability over uniform \(y,y'\in Y\) is at least
\(\chi^2\), by squaring the size of each tag's good-column set. Hence
\(\mathcal H\) contains a positive constant fraction of all pairs.
Consequently a positive constant fraction of labels have a positive
constant fraction of partners in \(\mathcal H\). Draw \(V_0\) uniformly
from these labels. For each bin \(w\), to be defined below, independently
draw \(A_w\) uniformly from the partners of \(V_0\), conditional on
\(V_0\). Both the law of \(V_0\) and each conditional law of \(A_w\)
have atoms at most \(O(1)/N\). All draws use the retained labels under
consideration.

Fix constants
\[
 a_0=1/30\) sufficiently small relative to their gaps. Given
the parents, draw a stream \(W_w\) at each bin, independently across bins
and in independent segments of a fixed large length \(q_0\). To draw one
segment, first choose a fresh tag conditioned on both parents being good,
and then draw \(q_0\) independent labels from \(\mu_I\) conditioned on
adjacency to both parents. The labels in a segment are independent
conditional on its tag. Each has simultaneous-hit probability at least
\(.90\) before this last conditioning. Thus the segment law has density
at most
\[
 (2/\chi^2)(.90)^{-q_0}\le e^{a_0q_0}
\]
relative to \(R'_0=\mathbb E_I\mu_I^{\otimes q_0}\), upon increasing the
fixed \(q_0\). For a length \(u\) divisible by \(q_0\), write
\(R[u]\) for the product of \(u/q_0\) such reference segments. Each of
its coordinate marginals is at most \(K'_0/N\), and its joint density
relative to product uniform measure is at most \(e^{u n^\gamma}\).
Only finite streams are needed. All prefix and block lengths below are
rounded upward to multiples of \(q_0\).

\paragraph{Counts, signs, and column indices.}
Partition some cube coordinates into \(d_c=300\) coarse chunks, each of
length \(\lfloor n^{1/5}\rfloor\). In each chunk, partition the possible
counts of ones into consecutive intervals, or bins, of probability at
most \(2n^{-.04}\), with \(O(n^{.04})\) endpoints. The binomial atom
bound \(O(n^{-.1})\) permits this choice. Let \(P\) be the vector of
counts and \(w(P)\) its vector of bins. The coarse key \(i(P)\) records
\(w(P)\) and a flag: it is interior if no single bit flip changes a bin,
and boundary otherwise. An interior key uses parent \(A_w\) and the
list \(C_i=\{w\}\); a boundary key uses parent \(V_0\) and the list
consisting of \(w\) and its grid neighbors. In particular,
\(w(P)\in C_{i(P')}\) whenever \(P'=P\) or \(P'\) results from one
coarse bit flip.

Use \(m=\lceil n^\alpha\rceil\) further disjoint chunks, each of the
same odd length asymptotic to \(n^{.3}\), where \(\alpha>0\) is a small
fixed constant. Their majority signs give \(t\in Q_m\). Let \(F\) be
the set of chunks whose count is at distance \(1/2\) from mid-weight;
these are exactly the signs that one bit flip can change. Let \(j\)
count the chunks whose count is at distance at most \(R_f=5.5\) from
mid-weight. Thus \(j\) counts chunks, not coordinates within them, and
its cutoff is independent of the coarse boundary flag. A role is low if
\(j\le J=\lfloor m^{1/20}\rfloor\), and high otherwise. All remaining
cube coordinates are residual. On either actual cube parity the signs
are uniform. Binomial atom bounds and a union over subsets of chunks give
\[
 \Pr(j\ge h)\le n^{-.13h}\quad(1\le h\le m),\qquad
 \Pr(i(P)\text{ is boundary})\le n^{-.05}.
\]

The hidden columns are indexed by
\(\ell=(i,t,j)\), \(0\le j\le J\), and by \(\ell=(i,*)\) in the
high case. An odd role uses the index determined by its counts and signs.
Given the base data \((V_0,A,W)\), independently draw \(U_\ell\) for
all these indices. A low \(U_\ell\) is one column; a high \(U_\ell\)
is a tuple of \(s=\lceil K_sJ\log m\rceil\) independent columns.
Write \(s_\ell=1\) or \(s\) for its length. Its coordinate law
\(\pi_\ell\) is the following posterior in the raw parent-and-stream
experiment:
\begin{itemize}
\item at an interior key, the law of \(A_w\) given
\(V_0,W_w[1:b_j]\);
\item at a boundary key, the law of \(V_0\) given
\((A_{w'},W_{w'}[1:b_j])_{w'\in C_i}\).
\end{itemize}
Here
\[
 u_j=\lceil K_1(j+4)\log m\rceil,\qquad b_j=u_{j+1},
\]
with segment rounding, and high keys use \(j=J\). We draw these variables
also at indices that occur only in the padded lists defined next.

\paragraph{Even types and the lengths of their arrays.}
For a low even role, with coarse data \(P,w\), let \(S\) consist of the
distinct keys
\begin{itemize}
\item \((i(P'),t,j)\), where \(P'=P\) or is obtainable by one coarse
flip;
\item \((i(P),t^h,j)\), \(h\in F\), and
\((i(P),t,j\pm1)\) when in range, replacing severity \(J+1\) by the
high key. Here \(t^h\) is \(t\) with sign \(h\) reversed.
\end{itemize}
Its type is \(K=(w,S,j)\). At a high even role take
\(K=(w,S,*)\), where \(S\) contains the high keys at the same coarse
range of \(i(P')\)'s. If \(j=J+1\), there is also an optional low
neighbor key \((i(P),t,J)\). This optional key is excluded from both
\(S\) and the type \(K\). These lists cover the keys at all actual
neighbors, since a sign flip leaves \(j\) unchanged. Every key paired
with \(w\) has \(w\in C_i\).

We now fix the lengths and indices of the arrays; their block law
\(P_K\) will be defined in Step~2. At each possible center ID, arrays of
different types will be independent conditional on the base and hidden
columns. For a low type, blocks have length \(u=u_j\), and the array
has total length
\[
 k_j=u_j\left\lceil K_2\big((j+4)\log m+m^{.02}\big)/u_j\right\rceil.
\]
For a high type, put \(u=u_*=\lceil\eta\log m\rceil\), with segment
rounding, and \(k_*=u_*\lceil m^{.005}/u_*\rceil\). Its full pool has
\(\lceil e^{K_hu_*}k_*/u_*\rceil\) blocks, of total length \(M_*\).
If an optional low key is designated, the used tuple is formed from the
first \(k_*/u_*\) blocks all of whose entries hit that column. Without
an optional key it consists of the first \(k_*/u_*\) blocks. At fixed base, the full
pool law will use only the keys in the type \(K\), so it is independent
of the optional column's value before this extraction.

A tuple reference \(c\) specifies its ID and type, and in the high case
also the block index subset. Its length \(k_c\) is \(k_j\) or \(k_*\).
The constants \(K_h,K_1,K_2,K_s\) are fixed and large; after \(K_h\)
choose \(\eta\) so small that \(M_*=o(m^{.03})\). We give the remaining
order of choices below, taking \(\alpha\) sufficiently small last.
Undefined numerical formulas on unused or failure branches use fixed
fallback values depending only on their declared local inputs.

The raw sampling order is
\[
 V_0\ \longrightarrow\ (A_w,W_w)_w\ \longrightarrow\ (U_\ell)_\ell
 \ \longrightarrow\ \text{center arrays}.
\]
Prospective positions, activations and choice ties are sampled separately;
an array is generated even at an ID whose center is absent. Each posterior
uses this raw experiment and only the observations explicitly listed in
its definition. When a candidate value changes, every later raw kernel
depending on it is evaluated at that new value. In particular, unobserved
arrays are integrated under their new laws. Successful-history conditions
are included only when explicitly retained as local gates.

\subsection{Predictive estimates at the first two levels}
\label{sec:predictive-estimates-at-the-first-two-levels}

\paragraph{Step 1: deleting a stream prefix from a parent posterior.}
For a key \(\ell\), remove the observation \(W_w[1:u]\) from the
specified definition of \(\pi_\ell\), retaining its other observations,
and call the resulting posterior \(\pi_{\ell,-w,u}\). The shift
\(b_j=u_{j+1}\) ensures that each prefix needed for a listed or optional
key lies within the observed stream. Given the retained observations,
the incoming prefix has likelihood at most \(e^{a_0u}\) relative to
\(R[u]\), for every parent value in support: it comprises complete
segments, and the partner is among the retained data.

The marginal density of this prefix is smaller than \(e^{-\delta u}\)
on a set of raw probability at most \(e^{-\delta u}\). Off that set,
Bayes' formula and the gap \(a_1-a_0\) give the test
\[
 \pi_\ell(y)\le e^{a_1u}\pi_{\ell,-w,u}(y)
 \qquad\text{for every }y.
\]
We also require
\(N\max\pi_\ell\le\exp(K'b_j)\), for a sufficiently large fixed
\(K'\). Its raw exception is at most \(e^{-\delta b_j}\). At an
interior key this follows from the full stream likelihood conditional
on \(V_0\). At a boundary key use product uniform measure for the
bounded list \((A_{w'})_{w'\in C_i}\) and the segment references for
their streams. The likelihood for each candidate \(V_0\) is at most
\((O(1)e^{a_0b_j})^{|C_i|}\). The prior atom bound and the same
small-denominator estimate give the asserted cap.

\paragraph{Step 2: reconstructing a stream block from hidden columns.}
Fix a type \(K\) and all base data except \(W_w[1:u]\). Its conditional
raw law \(P_0\) is the product of the true-parent segment laws. Let
\(\mathcal G_K\) be the set of alternative blocks \(z\) for which the
Step~1 comparisons at \((w,u)\) hold for every key in \(S\). At a high
type, also require them for all potentially used optional keys. This
involves all coarse parts represented in \(S\), but not the signs:
the low \(j=J\) and high priors have the same coordinate law. In
particular, \(\mathcal G_K\) is defined without observing any \(U\).

Set \(\rho_\ell=\pi_{\ell,-w,u}^{\otimes s_\ell}\). Relative to
\(\rho_\ell\), let \(L_\ell(z;\theta_\ell)\) be the likelihood of
\(U_\ell=\theta_\ell\) when the base block is replaced by \(z\).
Off the support of \(\rho_\ell\) the gated likelihood can be set to
zero. Relative to the product reference \(\prod_{\ell\in S}\rho_\ell\),
the observations \(U_S\), with the event
\(W_w[1:u]\in\mathcal G_K\) retained, have subdensity
\[
 m_S(\theta)=\int1_{\mathcal G_K}(z)
       \prod_{\ell\in S}L_\ell(z;\theta_\ell)\,dP_0(z).
\]
Define \(P_K\) by normalizing this integrand in \(z\) at the observed
\(U_S\). Dropping the factor for \(\ell\), but retaining the same
gate, defines \(m_{S-\ell}\) and \(P_{K,-\ell}\).

We require positivity and the denominator bounds
\[
 m_S\ge e^{-\delta u\sum_Ss_\ell},\qquad
 m_S/m_{S-\ell}\ge e^{-\delta us_\ell}.
\]
On the true-block gate, each exception has raw probability at most its
threshold. For the ratio test, for example,
\[
 \int_{\{m_S<\varepsilon m_{S-\ell}\}}m_S
       \,d\Bigl(\prod_{\ell'\in S}\rho_{\ell'}\Bigr)
 \le\varepsilon\int m_{S-\ell}
       \,d\Bigl(\prod_{\ell'\in S}\rho_{\ell'}\Bigr)
 \le\varepsilon.
\]
The last integral is at most one, and all unlisted keys have simply been
integrated out. On the true-block gate \(m_S>0\) almost surely, which
also implies \(m_{S-\ell}>0\). For a high type, adding one optional low
key gives the analogous test
\(m_{S+\ell}/m_S\ge e^{-\delta u_*}\), with the same probability
bound.

Combining these lower bounds with Step~1 gives
\[
 \frac{dP_K}{dP_{K,-\ell}}\le e^{a_2us_\ell},\qquad
 \frac{dP_K}{dR[u]}\le A_K^u,\qquad
 A_K=\exp\bigl(K''(1+\sum_{\ell\in S}s_\ell)\bigr),
\]
where \(K''\) is a sufficiently large fixed constant. The first
comparison holds also at any replacement value of \(\theta_\ell\)
passing its ratio test. We can now generate each center array as
independent \(P_K\)-blocks of the lengths already specified.

The support of this posterior enforces the required adjacencies. Every
\(z\) in the support of \(P_0\) leaves the base data with positive raw
probability. If a listed column has positive posterior likelihood at
that base, the stream-generation rule says that it sees every entry of
\(z\). For an optional column the added likelihood is at most
\(e^{a_1u_*}\), whereas its expectation under \(P_K\) is
\(m_{S+\ell}/m_S\ge e^{-\delta u_*}\). Its positive-likelihood set
therefore has \(P_K\)-mass at least \(e^{-(a_1+\delta)u_*}\), and every
block in that set hits the optional column. Choosing \(K_h\) large
makes the probability of too few such blocks in a high pool \(o(1)\),
uniformly at histories passing these tests.

\subsection{State neighborhoods and odd predictive estimates}
\label{sec:state-neighborhoods-and-odd-predictive-estimates}

We group actual cube roles into states that retain their residual bits,
exact coarse counts, and the count in every majority-sign chunk, with one
exception: counts at distances \(5.5\) and \(6.5\) on the same side of
mid-weight are merged. A state also records the exact value of \(j\).
Encode each count field and the \(j\)-field by a one-hot vector. Together
with the residual bits this embeds the states in
\(Q_d\), \(d=(1+o(1))n\).

A state determines parity despite the merged counts. Give each merged
symbol its outer representative, at distance \(6.5\), as a baseline.
Replacing it by its inner representative changes the count by one and
reverses parity. The number of replacements is \(j\) minus the number
of unmerged counts within the cutoff. This determines the fine-coordinate
parity; the coarse counts and residual bits are exact. It also determines
the key, type and optional designation. The exact coarse counts here are
more information than will be retained in
Lemma~\ref{lem:small-polynomial-broad-side}.

Join an odd state to an even state when some actual cube edge realizes
that pair. Each state has degree \(O(n)\), and any two even states
adjacent to one odd state have ambient distance at most \(D=8\). Indeed,
one bit flip changes only boundedly many one-hot entries, including the
possible change of \(j\). A flip changing \(j\) passes between distances
\(5.5\) and \(6.5\). Thus all low neighbors of a high odd state, when
present, form one state; the same holds for the high neighbors of a low
state. The padded lists above cover all this incidence.

Use even states as height sites and choose one center ID at each, shared
by all actual roles represented there. An ID is a location-level pair in
the ambient cube. We aim to use at most \(T=\lceil m^{.001}\rceil\)
distinct IDs around each odd state. For the height device take
\(r=\lfloor\rho n\rfloor\), \(\lambda=n^{10}\), and parameters with
\(2n^b\le T\) and \(\theta>.9\). Its exponents are chosen after
\(\alpha\), with \(b>b_0>0\) much smaller than \(.001\alpha\), and
\(\sigma,\zeta,1-\theta\) small enough for its inequalities. These
height exponents are unrelated to the stream lengths \(b_j\). Choose
\(\rho>0\) so small that the binary ball entropy at \(2\rho\), in
natural logs, is less than \(\log2-\tau_1\). We will also use the short
height computation of radius \(D\lfloor\sqrt m\rfloor\).

\paragraph{Observation records and their counts.}
Fix an odd state \(b\) and a mapping of its neighboring even states to
at most \(T\) IDs. Its observation record lists distinct ID/type arrays,
so repeated uses of the same array are recorded only once. At a low state
we observe every used full low tuple and, if a high neighbor is present,
its full pool and the block subset selected to hit \(U_\ell\). Call
that subset the mask. At a high state we observe all used full high pools
and the possible one used low tuple. We also record which high
type/optional-key combinations are needed at each ID, including the
absence of an optional key. Their block subsets are computed from the
observed pools and optional columns. If there are too few hits, the test
uses the first blocks as a fallback; actual usable tuples will be ensured
separately. A tuple reference \(c\) is therefore a specified set of
primitive blocks in one of the observed arrays.

There are \(O(T+j)\) low tuples around a low state. To see this, low types
with unchanged \(t,F\) have boundedly many generic variants, determined
by coarse incidences and severity; each variant uses a subset of the ID
list. Every other variant changes a sign or \(F\), and hence comes from
a chunk at distance at most \(1.5\) from mid-weight. There are at most
\(j\) such chunks and constantly many relevant flips per chunk. Each
of their \(O(j)\) neighboring states uses one ID. Ambiguous merged
chunks do not change signs or \(F\), so they produce only generic
variants regardless of how many there are.

At a high state, there are \(O(T)\) full pools of boundedly many types.
Optional choices vary only near the interface, where \(j\le J+2\).
Their generic variants retain the sign, while the other variants arise
from \(O(J)\) relevant neighboring states. Thus there are only
\(O(T+J)\) needed high tuple references, even though several may use
subsets of the same pool.

The counts of actual records below assume that the \(r\)-ball of each
even state adjacent to \(b\) has at most \(2\lambda\) prospective centers
at every level, as will be required in the local validity event.
At fixed center presence, this leaves polynomially
many possible IDs. Choosing their lists and assigning the exceptional
states gives logarithmic record counts at most
\[
 \begin{array}{ll}
 O(T\log n+(j+1)\log T+k_*1_{j=J}),&b\text{ low},\\
 O(T\log n+(J+1)\log T),&b\text{ high}.
 \end{array}
\]
\Needspace{3\baselineskip}
The low mask contributes at most
\(\log\binom{M_*/u_*}{k_*/u_*}=O(k_*)\). At high states we count
optional-key assignments, then compute their subsets; we do not enumerate
all subset combinations. If only the full observation list is recorded,
its logarithmic count is \(O(T\log n)\).

For history tests, before positions have been sampled, use abstract
records with the IDs renamed in \([T]\). Group them by coarse bin,
central sign and severity. Their logarithmic counts are
\[
 \begin{array}{ll}
 O(T\log T+(j+1)\log m+k_*1_{j=J}),&b\text{ low},\\
 O(T\log T+(J+1)\log m),&b\text{ high}.
 \end{array}
\]
Besides generic variants, a low record specifies \(O(j+1)\) chunk
indices and their finitely many near-center statuses. A high record
needs such information only at the interface. Coarse data enter through
a bounded neighborhood of bins. In particular, regular Step~2 low-type
patterns number \(m^{O(j+1)}\); the small-prefix \(u_*\) tests have
boundedly many patterns per bin modulo the sign of their one optional
key. These counts distinguish the full arrays observed, the tuple
references extracted from them, and the records used to enumerate tests.

\paragraph{Step 3: reconstructing an odd label from center arrays.}
Fix the base and every hidden column except the target
\(\vartheta=U_\ell\) at \(b\). Its raw prior is
\(\pi_\ell^{\otimes s_\ell}\). At a low state, condition also on the
possible high pool, whose law does not use this optional low key. The
remaining observations are the low-array blocks. At a high state, the
observations instead comprise every full high pool and the possible one
low tuple. In either case these observed blocks are independent given
\(\vartheta\), with laws \(P_K(\cdot\mid\vartheta)\); their types
have \(\ell\in S\).

For each observed block use \(P_{K,-\ell}\) as a reference law. Let
\(g_e(\vartheta)\) be the likelihood of block \(e\) relative to this
law. The candidate gate \(\Theta(\vartheta)\) requires positive
\(m_{S-\ell}\) and the Step~2 lower ratio \(m_S/m_{S-\ell}\) for every
observed type. These conditions use no array entries. At a low state
with a high pool, also include the indicator that \(\vartheta\) selects
the specified successful mask from that fixed pool. There is no mask
indicator at a high state. Thus, with \(c\) a same-mode tuple reference,
\[
 M=\int\Theta(\vartheta)\prod_e g_e(\vartheta)
       \,d\pi_\ell^{\otimes s_\ell}(\vartheta),\qquad
 M_{-c}=\int\Theta(\vartheta)\prod_{e\notin c}g_e(\vartheta)
       \,d\pi_\ell^{\otimes s_\ell}(\vartheta).
\]
At low states the products use only low blocks; at high states they use
all the observed blocks, and deletion may remove a strict subset of one
pool. On the candidate gate each block density is at most
\(e^{a_2|e|s_\ell}\), where \(|e|\) is its length.

Let \(k'_j\) be the minimum \(k_l\) with \(|l-j|\le1\). Require
positivity and
\[
 M/M_{-c}\ge e^{-\delta k_cs_\ell},\qquad
 M\ge
 \begin{cases}
 e^{-\delta k'_j},&b\text{ low},\\
 e^{-\delta s},&b\text{ high}.
 \end{cases}
\]
For a fixed observation record and fixed subsets, each exception
intersected with the
true-target gate costs at most its threshold in the raw joint experiment.
This is the subdensity calculation of Step~2, now using
\(\int M_{-c}\le1\). At low states it includes occurrence of the
specified successful mask. At high states an individual ratio test can
be unioned over all subsets of one pool at cost \(\exp(O(k_*))\),
which is smaller than its \(\delta k_*s\) exponent. No union over all
joint choices of subsets is needed.

Let \(\mathcal P\) and \(\mathcal Q_c\) be the normalized full and
deleted target integrands. Their gates do not include the denominator
tests just imposed. At a low state, \(\mathcal P\) is supported on
labels adjacent to all needed tuples, including the high tuple specified
by the mask. The block likelihood and denominator bounds give
\(\mathcal P\le e^{a_3k_c}\mathcal Q_c\). We reserve a further
multiplier \(e^{\delta k'_j}\) for selection, still below
\(e^{a_4k_c}\). Even after that multiplier the normalized atom cap is
\(e^{D_L}\), where \(D_L=m^{.15}\): its logarithm costs only
\(O(b_j+(T+j)\max_{|l-j|\le1}k_l)\). The independent high pool is not
part of this likelihood cost.

At a high state the bounds are
\[
 \log(\mathcal P/\mathcal Q_c)\le a_3k_cs,\qquad
 \log(N^s\max\mathcal P)\le K_0sJ\log m.
\]
There are \(O(TM_*)=o(J)\) full high-pool entries and at most one low
tuple of length \(O(J\log m)\); together with the prior and denominator
bounds these give the second inequality. The fixed \(K_0\) may depend
on \(K_1,K_2\), but not on \(K_s\).

\paragraph{High rows: a common law for all deletion costs.}
For a high row we need one law on index--label pairs that has small
expected likelihood cost against every needed high deletion reference.
Fix the mapping and observed data in the true-target-gated raw model,
with the preceding denominator tests satisfied. The remaining target \(\vartheta\) has law \(\mathcal P\). The needed
block subsets are now fixed by the full pools and the other, optional
low keys; they do not depend on the remaining target draw. Let
\(r_{\rm ref}=O(T+J)\) be their number. If it is zero, the cost
constraints below are vacuous: restrict the index--label law to the
density-good set defined below and normalize, without using a grid.

For a supported true prefix \(\vartheta_{z)\le e^{-z}\): on that set
\(p(Y)e^{D_H}\) by a
small fixed constant \(\eta_D\).

Here is a finite set of directions sufficient for all the cost
constraints. Fix a small \(\varepsilon_g>0\), and for
\(\xi\) in the reference simplex set
\[
 a_c=\lceil r_{\rm ref}\xi_c/\varepsilon_g\rceil,\qquad
 A=\sum_c a_c,\qquad \widehat\xi_c=a_c/A.
\]
Then \(A\le(1+\varepsilon_g^{-1})r_{\rm ref}\) and
\(\xi_c\le(1+\varepsilon_g)\widehat\xi_c\) for every \(c\).
The number of nonnegative integer vectors with this bound on their sum
is \(\exp(O_{\varepsilon_g}(r_{\rm ref}))\), by the composition count
\(\binom{\lfloor(1+\varepsilon_g^{-1})r_{\rm ref}\rfloor+r_{\rm ref}}
{r_{\rm ref}}\). Thus all the predictable bounds hold on this grid,
with total failure \(e^{-c's}\) for a fixed \(c'>0\), since
\(T+J=o(s)\). This is a conditional bound at fixed data; integrating
against the gated data subdensity and adding the earlier denominator
exceptions gives the same form of bound for each mapping. The later
union over abstract mappings has a different count and will determine
how large \(K_s\) must be.

Now fix a path passing these tests, and define the probability law
\(\nu(h,y)=\mathcal P_h(y)/s\) and set
\(G_D=\{(h,y):N\mathcal P_h(y)\le e^{D_H}\}\). For each grid direction
restrict \(\nu\) to \(G_D\) and to
\(\sum_c\widehat\xi_cE_h^c(y)\le L_0\). The removed mass is at most
\[
 \beta=\eta_D+(a_3+\delta')/L_0.
\]
After normalization, the unclipped expected cost in that direction is
at most \((a_3+\delta')/(1-\beta)\). Choose the small constants and
\(L_0\) so that \((1-\beta)^{-1}\le1+\varepsilon'\), with
\(\varepsilon'>0\) small. All these restricted laws belong to the same
compact convex set
\[
 \mathfrak F=\left\{R\ge0:\ \sum_{h,y}R(h,y)=1,\quad
 R(h,y)\le(1+\varepsilon')\nu(h,y)1_{G_D}(h,y)\right\}.
\]
Nonnegative costs and the coordinatewise grid bound show that for every
convex direction \(\xi\), some member of \(\mathfrak F\) has weighted
expected cost at most \(a_3\) plus a chosen small error. If no member
satisfied all the individual bounds, separation of the compact convex
set of cost vectors from the region below these bounds would give a
nonnegative separating vector. After normalizing it, this would contradict
the directional conclusion. Hence one law \(\mathcal R\in\mathfrak F\)
satisfies all the cost bounds.

Its support hits every required tuple: a positive \(\mathcal P_h(y)\)
has a positive posterior continuation, all of whose coordinates hit the
observed blocks. Moreover,
\[
 \left[\log\frac{\mathcal R(h,y)}
   {\widetilde{\mathcal Q}_{c,h}(y)/s}\right]_+
 \le \log(1+\varepsilon')+k_c E_h^c(y).
\]
The gap from \(a_3\) to \(a_4\) therefore yields
\[
 \mathcal R(h,y)\le 2e^{D_H}/(sN),\qquad
 \mathbb E_{\mathcal R}\!\left(
  [\log(\mathcal R(h,y)/(\widetilde{\mathcal Q}_{c,h}(y)/s))]_+
                         \right)\le a_4k_c.
\]
Choose one such law deterministically from the local data. A deleted
reference uses only the full observation list with those primitive blocks
removed, together with the fixed history and true prefixes. It does not
use other optional subset assignments. True prefixes are legitimate fixed
data here because the hidden columns were sampled before the arrays.
The clip parameters can be chosen with a rate \(c'>0\) independent of
\(K_s\). The path tests include positivity and true support; these hold
almost surely in the true gated model.

\subsection{Making history tests simultaneous}
\label{sec:making-history-tests-simultaneous}

We next sample the base and hidden columns so that Steps~1 and~2 hold
throughout. At the resulting history, every abstract mapping must also
have Step~3 failure probability over independent center arrays at most
\[
 e^{-c_Lk'_j}\quad\text{at low states},\qquad
 e^{-c_Hs}\quad\text{at high states},
\]
for fixed small \(c_L,c_H>0\). We achieve this in five stages, restricting
only the newly drawn variables at each entering history. Later avoidance
probabilities never reweight earlier histories.

For Step~2 a failure always means the failed numerical test intersected
with its true-block gate \(W_w[1:u]\in\mathcal G_K\). For Step~3 it
means failure at the specified record intersected with its true-target
gate, at a base passing Step~1. In a low record with a specified high
mask, the event includes occurrence of that successful mask. The earlier
stages will enforce the block and key-ratio gates; usable hits for selected
centers are enforced below. These definitions keep raw subdensity bounds
as intersection bounds, rather than conditioning them on future success.

A regular Step~1 or~2 test has scale \(L=u_j\), including the prior cap
at severity \(j\), with the high prior cap assigned \(j=J\). A
small-prefix test has scale \(L=u_*\). Each raw failure probability is
at most \(e^{-\delta L}\). The regular pattern count per bin and
central sign is \(m^{O(j+1)}\), so a bound such as
\(e^{-\delta u_j/16}\) sums to \(o(1)\) over all regular patterns and
severities if \(K_1\) is large. Small-prefix tests have boundedly many
patterns modulo sign translation, and
\(e^{-\delta u_*/16}\to0\).

An alarm at an entering history \(H\) is an event
\[
 \left\{\Pr_{\rm raw\ future}(B\cap\text{local gate}\mid H)>q\right\}.
\]
If the expectation of this conditional probability is at most \(p\),
Markov bounds the alarm probability by \(p/q\). Its scope comprises the
current-stage variables occurring in the canonical record: base bins in
the relevant \(C_i\)-lists, hidden keys in the relevant type lists, and
any specified optional keys. Future array variables are integrated out.
This definition determines the scopes used in each local lemma below.

For these alarm families, the gated likelihoods are evaluated only where
their defining ratios have positive denominators. Auxiliary continuations
may still reach undefined branches. Fix their fallback rules invariant
under the bin, sign and ID renamings used in the abstract records: for
example, fix an order on retained host labels, use the first label and
repeated copies when a probability law is undefined, and fixed numerical
values for undefined scalar formulas. These choices depend on no
additional keys or arrays. Thus the symmetry assertions below hold also
for the completed experiments.

\paragraph{Conditioning stage 1: the global parent.}
For each abstract Step~1 or~2 pattern, the conditional failure probability
given \(V_0\) is a function of this one draw. Its mean is at most
\(e^{-\delta L}\). Restrict \(V_0\) so that every such function is at
most \(e^{-\delta L/2}\); the alarm probability per pattern is at most
\(e^{-\delta L/2}\).

The pattern unions just given apply globally here. Conditional on \(V_0\),
the bin variables are iid, every formula reads a bounded-radius bin
neighborhood, and only boundedly many coarse incidence shapes occur.
Likewise translating all signs does not change a raw failure probability:
the low keys being integrated have independent laws that do not depend
on their signs. No factor \(2^m\), or factor for all bin names, is
needed. The total excluded parent mass is \(o(1)\). The retained draw
does not change any of the posterior definitions.

\paragraph{Conditioning stage 2: the coarse base.}
Fix the selected \(V_0\) and start from the independent variables
\((A_w,W_w)\). Exclude Step~1 failures outright. Also exclude the
alarms that a Step~2 gated failure, averaged over its future hidden keys,
has probability greater than \(e^{-\delta L/4}\). Stage~1 bounds their
expectations by \(e^{-\delta L/2}\), so the Markov cost is at most
\(e^{-\delta L/4}\) per alarm.

Group the events at each bin. Their scopes are the base variables in the
bounded union of the record's \(C_i\)-lists. The dependency degree is
bounded, and the pattern sums are \(o(1)\). The conditional avoidance
lemma therefore applies with charges \(o(1)\). It gives a base passing
Step~1 and the stated conditional Step~2 bounds, separately at each
selected \(V_0\).

\paragraph{Conditioning stage 3: the high hidden keys.}
Given a successful base, the high \(U\)'s are initially independent.
The one-target calculations of Step~3 give, for any fixing of the other
keys, raw gated exceptions at most
\(e^{-c_{L0}k'_j}\) or \(e^{-c_{H0}s}\), with fixed small positive
constants \(c_{L0},c_{H0}\). These estimates integrate the target and
arrays. A high record specifies type/optional-key appearances and
computes their subsets from the pools; it does not condition on their
extraction in advance.

Restrict the high keys to pass high-only Step~2 tests. For tests involving
low keys, require their conditional raw failure probabilities to be at
most \(e^{-\delta L/8}\). Stage~2 and Markov give alarm probabilities
at most \(e^{-\delta L/8}\). Also require each high Step~3 failure,
still averaged over independent low keys and arrays, to have probability
at most \(e^{-c_{H0}s/2}\). Its alarm costs at most
\(e^{-c_{H0}s/2}\).

These events read only high keys in nearby coarse bins, hence have
bounded dependency degree after grouping by bin. The high Step~3
abstract count is \(\exp(O(T\log T+J\log m))\). Taking \(K_s\) large
makes its product with \(e^{-c_{H0}s/2}\) tend to zero. All grouped
probabilities are thus \(o(1)\), and another bounded-degree local lemma
provides the high-key history. The abstract alarms retain the sign and
ID symmetries; no later spatial selection is used in them.

\paragraph{Conditioning stage 4: separate optional pretrims.}
Given this base and high history, separately restrict each low \(U_\ell\)
to satisfy its optional small-prefix tests
\(m_{S+\ell}/m_S\ge e^{-\delta u_*}\). Only that low variable remains
random in such a test, and each is involved in boundedly many coarse
patterns. Their probabilities from Stage~3 are \(o(1)\), so the low
variables remain independent with a density multiplier \(1+o(1)\) per
variable.

A regular Step~2 pattern uses \(O(j+1)\) low keys, so its probability
multiplies by \((1+o(1))^{O(j+1)}\) and remains at most
\(e^{-\delta u_j/16}\). A high Step~3 pattern reads only \(O(J)\)
low keys: the possible low tuple's \(S\)-list and the optional keys
named in the record. Its bound remains \(e^{-c_{H0}s/3}\). For low
Step~3 the one-target bound holds at every fixing of the other low keys;
only the target's own distortion matters. Its bound remains
\(e^{-c_{L0}k'_j/2}\).

\paragraph{Conditioning stage 5: the low hidden keys.}
Start from the product of these trimmed low laws. Exclude all remaining
Step~2 failures. For Step~3 impose the conditional array-failure bounds
\(e^{-c_Lk'_j}\) and \(e^{-c_Hs}\), taking, for example,
\(c_L=c_{L0}/4\) and \(c_H=c_{H0}/6\). Markov applied to the Stage~4
bounds gives alarms of these same exponential orders.

Group by central sign, coarse bin and severity. The current variables
in a low group's scope are exactly the low keys in its listed types and
optional entries. They have bounded sign and severity distance and lie
in nearby bins. High groups involving low variables occur only near the
interface and read the optional keys and the possible low tuple's
\(S\)-list; high requirements with no low variables already hold.
Both the dependency degree and the number of groups touching one low
variable are polynomial in \(m\), with fixed exponents.

After the pattern unions, each group can have probability at most
\(m^{-K_{\rm deg}}\) for any prescribed fixed \(K_{\rm deg}\): choose
\(K_1\) large for the regular tests, then \(K_2\) large for the low
Step~3 logarithmic count
\(O(T\log T+(j+1)\log m+k_*1_{j=J})\), and \(K_s\) large for the
high count. Polynomially small charges with total \(o(1)\) at each
variable give the final local-lemma restriction. This completes the
construction of the key history and its uniform conditional bounds over
independent center arrays.

\paragraph{Order of constants.}
First fix \(q_0\), the gaps between the \(a_i\)'s, \(\delta\), and the
path clip parameters other than \(K_D\). Choose \(K_h\) for optional
block hits and then \(\eta\) so small that
\(K_h\eta+.005<.03\). The coefficients in the history pattern counts
are fixed before choosing \(K_1,K_2,K_s\). Next take \(K_1\) large for
regular history tests, then \(K_2\) large for low Step~3, then \(K_D\)
large relative to \(K_0\), and finally \(K_s\) large for the high
pattern unions. Increasing \(K_2\) or \(K_s\) need not decrease the
respective Step~3 exponential rates before counting patterns.

The scales give
\[
 TM_*=o(J),\qquad T\log n=o(k_*),\qquad
 T\log n=o(m^{.02}),\qquad T+J=o(s).
\]
Allow enough slack in the constants that each actual low configuration
count is smaller than its required fixed margin times \(k'_j\), and
that each high testing count is smaller than its required margin times
\(s\). These relations hold for every fixed \(\alpha>0\); choose
\(\alpha\) sufficiently small after all the likelihood constants,
including the following truncation constant.

\paragraph{Prior-heavy labels.}
For a block law \(P_K\), define its average coordinate marginal by
\(\bar P_K(x)=u^{-1}\sum_{i=1}^uP_K(z_i=x)\). Call a label
prior-heavy for \(K\) if \(N\bar P_K(x)>B_K\), where
\(B_K=A_K^{K_B}\). Fix a small \(\upsilon_0>0\) with
\(\upsilon_0+\tau_0/\tau_1<1\). At fixed successful key history and a
fixed tuple reference \(c\), the probability that more than
\(\upsilon_0k_c\) entries are prior-heavy is at most
\[
 2^{k_c}A_K^{k_c}
       \left(q_0K'_0/B_K\right)^{\upsilon_0k_c/q_0}.
\]
Indeed there are at most \(N/B_K\) heavy labels. A reference segment
hits this set with probability at most \(q_0K'_0/B_K\), and that many
heavy entries require at least \(\upsilon_0k_c/q_0\) segments to hit
it. The segments of \(R[k_c]\) are independent; the block domination
contributes \(A_K^{k_c}\), and the subset union contributes at most
\(2^{k_c}\). Choose \(K_B\) large enough that this is \(o(1)\), even
after the union over high subsets.

The following are instead deterministic averages over actual cube roles:
for sufficiently small \(\alpha\),
\[
 \mathbb E_{v\in A}B_{K(v)}\exp(O(k_*1_{j(v)>J}))=O(1),\qquad
 \Pr_{v\in B}(j(v)>J)e^{D_H}=o(1).
\]
At low severity \(\log B_K=O(j+1)\), except for an extra \(O(s)\)
at \(j=J\); at high severity it is \(O(s)\). The rarity bound
\(\Pr(j\ge h)\le n^{-.13h}\) outweighs these costs once \(\alpha\)
is small. The constants multiplying \(k_*\) are already fixed. Also
choose \(\alpha\) so that the Step~1 low-prior caps have logarithms
at most \(.02(j+1)\log n\).

\subsection{Height choices and the odd kernels}
\label{sec:height-choices-and-the-odd-kernels}

Fix a successful history through the hidden columns. Generate prospective
center presence and independent arrays according to their raw laws. At
an even site-level, first remove any center in its \(r\)-ball whose
tuple for that state fails the prior-heavy fraction bound or has too few
optional hits. Each candidate fails with probability \(o(1)\), and
these tests use independent arrays across centers.

For each odd state and each consecutive pair of levels, consider all
mappings of its neighbors into their prospective centers using at most
\(T\) IDs. Test Step~3 for each mapping, including the specified
successful-mask event when required at low states. Choose a maximal
family of failed ID sets that are pairwise disjoint, by a deterministic
local rule. Mark their union forbidden at all adjacent sites on those
levels. A site's eligible set is what remains of its prospective centers
after these marks and its singleton removals.

With conditional probability \(1-\exp(-\Omega(n))\), every site-level
ball has between \(\lambda/2\) and \(2\lambda\) prospective centers,
singleton losses are small, and every such maximal family has fewer than
\(n\) members. The first two claims follow from binomial tails.
For the third, fix presence within the count bounds. Disjoint ID sets
read disjoint arrays, which are independent given the key history.
The history's conditional failure bounds and the actual configuration
counts therefore bound the probability of \(n\) disjoint failures by
\(\exp(-\Omega(nk'_j))\) at a low star and
\(\exp(-\Omega(ns))\) at a high star, including the union over their
records. These bounds also sum over all stars and level pairs.
Since a site is incident to \(O(n)\) stars, the marks remove at most
\(O(n^2T)\) centers per site-level. The eligible sets thus have size
at least \(\lambda/3\) everywhere, with the stated exception.

Activations have not been used in defining eligibility. Apply the long
height rule and uniform eligible-active tie choices. With probability
\(1-o(1)\), neighboring even states around any odd state use at most
two consecutive levels. At either level all their choices lie in one
\((r+D)\)-ball, so the crowd bound limits their total number of IDs to
\(2n^b\le T\). Every actual mapping passes Step~3: otherwise its failed
ID set would be disjoint from the marked maximal family, contradicting
maximality. The singleton removals ensure its required hits.

\paragraph{Local validity under replacement.}
Use the same deterministic marking and singleton rules also at
hypothetical key and array values. Markings use only the displayed
likelihood tests and their records, not the history alarms or the odd
selection adjustment below. Long and short height computations use the
same pre-activation eligible sets and ties. Either returns no choice if
its maximum is \(H\) or if its resulting site-level is bad.

For either computation, call an odd state locally valid when all the
following hold at its star:
\begin{itemize}
\item every adjacent even state has a legitimate choice, and the
\(r\)-ball centered at each such state has at most \(2\lambda\)
prospective centers at every level \(0,\ldots,H\);
\item the mapping uses at most \(T\) IDs, and all required singleton
and hit tests pass;
\item the true-target gate, support conditions, and Step~3 numerical
and path tests for this mapping pass.
\end{itemize}
This is the same function of the local choices and star data for both
truncations. It does not require global path correctness or eligibility
sizes in a larger region. Thus equality of the adjacent path maxima,
with the common ties, gives equality of choices and validity. The long
calculation is valid everywhere on the global geometry event above.
Set odd kernels to zero on local invalidity, with the fixed local
fallbacks used only in auxiliary computations.

In particular, hypothetical computations do not retest global Step~1
or~2 success. The optional-prior comparisons in a high
\(\mathcal G_K\) do not read realized low-key values. Eligibility reads
optional values only in types or mappings at the consulted sites and
incident stars. Marks at a site-level do not test eligibility at other
sites. These facts ensure that the two height computations really use
the same eligible sets and that unconsulted keys remain unobserved.

\paragraph{Low rows: correcting for the selection event.}
The following rows are attached to actual odd roles, even when several
roles use one state computation. We continue to write \(b\) for the
role when taking loads, with its state understood. A high role uses the
law \(\mathcal R\) for its actual observation record. A low role
requires an adjustment because its observed arrays were selected using
the hidden column.

Fix the key history except for its target \(U_\ell\), and fix
prospective center presence. Use the original prior \(\pi_\ell\) for
the target, and simulate the raw center, activation and tie experiment
with the short height rule. Let \(\mathfrak d\) be a canonical
observation record, \(o\) its observed array data, and
\(Q_{\mathfrak d}\) the product of its Step~3 block reference laws.
When a high pool is present, include its target-independent law in this
reference. For target \(U_\ell=y\), its gated observation likelihood
is \(F_y(o)=\Theta(y)\prod_e g_e(y)\).

Let \(\mathbb P_y\) denote this raw experiment with the target replaced
by \(y\). Conditional on the recorded observations, the probability
that short selection validly presents exactly this record is a number
\(a_y(o)\in[0,1]\). More precisely,
\[
 \mathbb P_y\bigl(\text{valid proxy presentation of }\mathfrak d,
                  \ O_{\mathfrak d}\in do\bigr)
       =F_y(o)a_y(o)\,Q_{\mathfrak d}(do).
\]
The presentation event implies the required ratio gates and any successful
mask. Given these gates, the recorded low arrays have their product block
laws, independently of a recorded high pool. Integrating the remaining
selection event defines \(a_y\). In doing so, unrecorded arrays whose
laws depend on \(y\) are generated at that candidate value; they are
not fixed at their realized values. Mappings with the same record are
combined into one presentation event, and the events for different
records are disjoint. Values on zero-mass conditioning data can be fixed
arbitrarily. The resulting table \((a_y)_y\) is a function of the fixed
inputs and observed data, not a new observation of the actual target.

Set \(\varepsilon=e^{-\delta k'_j}\). At valid data define
\[
 \bar a=\frac{\sum_y\pi_\ell(y)F_ya_y}{\sum_y\pi_\ell(y)F_y}.
\]
If \(\bar a\ge\varepsilon\), use the adjusted posterior proportional
to \(\pi_\ell F a\); otherwise retain \(\mathcal P\), proportional
to \(\pi_\ell F\). For observations presented by the long rule use
this same short-rule table. In either case the row is at most
\(\varepsilon^{-1}\mathcal P\), preserving the deletion multiplier
\(e^{a_4k_c}\) and cap \(e^{D_L}/N\).

Let \(p_b^{\rm pr}\) be the proxy row, extended by zero on invalidity.
For each fixed output label \(x\), integrate the original target prior
and the raw center experiment. Cancellation of the adjusted normalizer
against the actual presentation density gives
\[
 \mathbb E[p_b^{\rm pr}(x)1_{\{\mathrm{adjusted}\}}]
 \le\pi_\ell(x)\sum_{\mathfrak d}
       \int F_x(o)a_x(o)\,dQ_{\mathfrak d}(o)
 \le\pi_\ell(x).
\]
The last step uses the disjoint presentation events. On fallback data,
its presentation density is at most \(\varepsilon\sum_y\pi_\ell(y)F_y\).
Hence
\[
 \mathbb E[p_b^{\rm pr}(x)1_{\{\mathrm{fallback}\}}]
 \le\varepsilon\pi_\ell(x)\sum_{\mathfrak d}
           \int F_x(o)\,dQ_{\mathfrak d}(o)
 \le\varepsilon(\#\mathrm{records})\pi_\ell(x).
\]
Each gated observation density integrates to at most one; their gates
need not be disjoint. The record count on the position gate is smaller
than \(\varepsilon^{-1}\), so the total mean is at most
\(2\pi_\ell(x)\).

For a fixed key history \(H\), define the normalized means
\[
 \bar p_b^{\rm pr}(y;H)=\mathbb E_{\rm raw\ centers\mid H}
                              [Np_b^{\rm pr}(y)],\qquad
 \bar p_b^{\rm long}(y;H)=\mathbb E_{\rm raw\ centers\mid H}
                              [Np_b^{\rm long}(y)].
\]
Here ``centers'' includes presence, arrays, activations and ties. Thus
presence is held fixed in the lookup calculation above and then averaged
in these means. The proxy mean uses low variables only at sign distance
\(O(\sqrt m)\) from the target, with the base and high history fixed.
Indeed the short rule reads statuses in its short tube, and the
incident-star marking rules add only bounded state distance. The one-hot
encoding bounds the corresponding sign distance. Although a consulted
center may be farther away, its array has one of these local types;
all arrays not read by the presentation event integrate out. The
validity and lookup calculations have this same locality.

At a successful key history, compare long and short calculations with
the same randomness. On correct eligibility sizes, the height lemma
bounds mismatch at any one of the \(O(n)\) neighboring states by
\(o(e^{-2m^{1/5}})\). Incorrect sizes have probability
\(e^{-\Omega(n)}\). Since \(D_L=m^{.15}\),
\[
 \bar p_b^{\rm long}(y;H)
 \le\bar p_b^{\rm pr}(y;H)
   +O(e^{D_L})\bigl[O(n)o(e^{-2m^{1/5}})+e^{-\Omega(n)}\bigr]
 =\bar p_b^{\rm pr}(y;H)+o(1).
\]
The height estimate bounds an intersection with correct sizes, not a
conditional law given size success. With either rule, the unaveraged row
and its lookup table use center randomness only within ambient radius
\(r+o(n)\) once the key history is fixed.

\paragraph{Odd column sums through the three histories.}
We now apply scattered moments three times, always averaging over actual
roles in \(B\) and setting weights to zero outside the specified class.
This distinction matters because many roles can use the same state.

First consider \(Z_b(y)=N\pi_{\ell(b)}(y)\) for low roles, under the
coarse-base law given the selected \(V_0\). The boundary roles and roles
with \(j\ge1\) contribute deterministically at most
\[
 O\left(n^{-.05+.02}+
       \sum_{h\ge1}n^{-.13h+.02(h+1)}\right)
\]
by their rarity and prior caps. For interior \(j=0\), the cap is
\(n^{.02}\). Before coarse avoidance, the mean posterior at a bin is
the bounded candidate prior, by integration of the raw conditional law.
Same-bin pairs have fraction at most \((2n^{-.04})^{d_c}\), so the
repeat cost \(n(2n^{-.04})^{d_c}n^{.02}\) tends to zero. For distinct
bins, drop the coarse constraints touching them at constant cost per
bin and integrate independent raw bin variables. The scattered-moment
bound, followed by Markov and the union over labels, shows that the
average of these weights is bounded at all labels with high probability
under the conditioned base law.

Next fix such a base and the high-key history. The weights are now
\(Z_b(y)=\bar p_b^{\rm pr}(y;H)\), viewed as functions of the low
keys. Their cap is \(e^{D_L}\). Their near relation is sign distance
\(O(\sqrt m)\), of fraction \(2^{-m+o(m)}\); hence the repeat term is
\(n2^{-m+o(m)}e^{D_L}=o(1)\). For separated rows, remove the final
low-key avoidance constraints touching their target variables. The
charge sum gives cost \(O(1)^n\). Conditional on all other low keys,
the targets are independent and no other retained row reads them, by
short locality. The one-target proxy bound gives comparison means
\(O(N\pi_{\ell(b)}(y))\); the optional pretrim adds only \(1+o(1)\)
per target. Their averages are bounded by the first calculation.
Scattered moments therefore bound all proxy-mean averages with high
probability under the low-key law. The additive comparison above gives
the same conclusion for the long means.

Finally fix one of these key histories and use weights
\(Z_b(y)=Np_b^{\rm long}(y)\), now random over raw centers. Low rows
again have cap \(e^{D_L}\). Rows separated in residual coordinates by
more than \(2r+o(n)\) have disjoint center scopes and comparison means
\(\bar p_b^{\rm long}(y;H)\). Residual-ball rarity is exponential in
\(-n\), so its product with \(ne^{D_L}\) tends to zero. High rows
contribute deterministically at most
\(2\Pr_B(j>J)e^{D_H}=o(1)\). Applying the moment and label-union
bound at this last history gives bounded normalized average loads,
while geometry success supplies valid probability rows. Since
\[
 \sum_{b\in B}p_b(y)=\frac{|B|}{N}
             \left(\frac1{|B|}\sum_{b\in B}Np_b(y)\right)
 \quad\text{and}\quad |B|/N=1/(2C_n)\longrightarrow0,
\]
all odd column sums are at most the clock threshold \(\theta_0\),
except on an event of probability \(o(1)\) intersected with the preceding
successes.

\subsection{Actual outputs and even placement}
\label{sec:actual-outputs-and-even-placement}

Fix a history and geometry with valid odd rows and the column bounds.
For each high even role \(v\), let \(c\) be its selected tuple reference.
Under the product of the odd row laws, the high neighbors' outputs
\((h_b,y_b)\) are independent. Their costs
\[
 \left[\log\frac{p_b(h_b,y_b)}
              {\widetilde{\mathcal Q}_{c,h_b}(y_b)/s}\right]_+
\]
have total mean at most \(a_4k_*n\), by the defining property of
\(\mathcal R\), and each is at most \(D_H+O(1)\) by smoothing and
the cap. Require their sum to be at most \(a_5k_*n\). Bounded-summand
concentration bounds each failure by an exponential with exponent of
order
\[
 \frac{nk_*^2}{(D_H+O(1))^2}=n^{1-.09\alpha+o(1)}.
\]
Each predicate reads at most \(n\) rows, and each row belongs to at most
\(n\) predicates. All label atoms are \(e^{o(n)}/N\), hence smaller
than any fixed inverse power of \(n\). Apply the clock lemma with
scope exponent \(B=2\). It yields an injective odd assignment, retaining
the high output indices, which satisfies all these budgets and has joint
upper bound \((1+o(1))\prod p_b\) on at most \(n^2\) queried rows.

\paragraph{Even rows: deletion of primitive block values.}
Fix an actual even role \(v\), a possible center ID there, and a tuple
reference \(c\), including its block index subset at high type. Fix the
successful key history and all primitive center data except the block
values \(z\) belonging to \(c\). Primitive data here are presence,
ties, activations and the sampled blocks themselves. In particular, do
not fix other extracted tuples that may be functions of these blocks.
The raw conditional law \(P_0'\) of \(z\) is a product of blocks of
total length \(k=k_c\), with density at most
\((A_Ke^{n^\gamma})^k\) relative to product uniform measure.

For neighboring odd outputs \(\mathbf y\), including their indices
at high rows, define the sublikelihood
\[
 F_z(\mathbf y)=1_E\prod_{b\sim v}p_b(y_b).
\]
Every choice, extracted subset and kernel is recomputed as \(z\) varies.
The local gate \(E\) requires:
\begin{itemize}
\item presence of the specified center and legitimate long-rule selection
of this \(c\) at \(v\), with its specified block subset;
\item valid neighboring rows with their count and mapping bounds, and
eligible sets of size at least \(\lambda/3\) throughout the long height
consultation domain of \(v\);
\item the prior-heavy fraction bound for \(c\), and the high log budget
at \(v\) when needed.
\end{itemize}
These conditions are local to ambient radius \(r+o(n)\), also at
hypothetical inputs. They hold for the actual selected reference on the
global success event. No success elsewhere is part of \(E\).

We construct a product reference on \(\mathbf y\) independent of
\(z\). For each same-mode neighbor \(b\), let \(\mathcal D_b(c)\) be
the finite list of possible observation configurations in its adjacent
balls under the fixed presence-count gate. Enumerate ID/type lists
without requiring that their selection is feasible for the present
array values. At a low neighbor include the possible mask; at a high
neighbor record only full pools and the possible low tuple. For each
record \(\mathfrak d\), let \(q_{b,\mathfrak d,-c}\) be the
corresponding deleted reference, namely \(\mathcal Q_c\) at low or
\(\widetilde{\mathcal Q}_{c,h}/s\) at high. Use its locally defined
fallback if its formula is undefined. Set
\[
 Q_b=\frac1{|\mathcal D_b(c)|}
          \sum_{\mathfrak d\in\mathcal D_b(c)}q_{b,\mathfrak d,-c},
 \qquad Q=\prod_{b\sim v}Q_b,
\]
using uniform \(Q_b\) at opposite-mode neighbors. If the count gate
fails, set \(E\) empty and take any fixed local reference instead.

Each deleted component uses only retained primitive data. At a low
neighbor, deletion of the full low tuple leaves any mask indicator on
a different, fixed high pool. At a high neighbor, every likelihood
factor involving a block in the fixed subset \(c\) is removed from
the one full-pool observation. The remaining target gate has no
successful-mask indicator. A pool used for several optional tuples is
still observed only once; those extracted tuples are recomputed with
\(z\), rather than held fixed. True hidden-column prefixes, sampled
before all arrays, do remain fixed. These facts prove that \(Q\) is
independent of \(z\), and that its mixture contains the actual deletion
component whenever \(E\) holds.

The likelihood costs now separate into three cases. At a low same-mode
neighbor, the adjusted row is at most \(e^{a_4k}\) times its actual
deleted component. The low record count, including a mask if needed,
fits the reserved margin because \(k'_j\le k\). At a high same-mode
neighbor use the imposed sum of positive-log costs, at most
\(a_5kn\) over these neighbors. Each full-observation-list mixture
costs only \(O(T\log n)=o(k_*)\) in the logarithm: the subset \(c\)
is fixed, and other optional subset decisions are not recorded in the
reference. Finally there are at most
\(O(mn^{.3})=o(n^{.4})\) opposite-mode neighbors, each costing
\(O(D_L+D_H)\) against uniform measure, including the high index when
present. Their total is \(o(kn)\). The reserved gaps therefore give
\[
 F_z(\mathbf y)\le e^{a_6kn}Q(\mathbf y).
\]

Let \(m_c(\mathbf y)=\int F_z(\mathbf y)\,dP_0'(z)\). For each fixed
\((v,c)\), the gated posterior lemma bounds the raw exception to
\[
 m_c(\mathbf y)>0,\qquad
 m_c(\mathbf y)\ge e^{-\delta kn}Q(\mathbf y)
\]
by \(e^{-\delta kn}\). To apply it to the actual assignment, first
retain its successful-prehistory indicator and compare the required
odd outputs to product rows using the clock bound. Only after this
comparison discard nonlocal center-success restrictions, retaining \(E\),
and integrate the raw centers at the successful key history. The bound
is thus \((1+o(1))e^{-\delta kn}\) per \((v,c)\) on the entering
success event. The union over roles, IDs and high subset indices costs
\(\exp(O(n)+O(k_*))\) and is \(o(1)\), since \(k\to\infty\).

On the complementary event use the posterior
\(F_z\,dP_0'/m_c\). Its density relative to product uniform is at most
\(e^{\tau_0kn}\): the prior contributes
\(k(\log A_K+n^\gamma)=o(kn)\), and the other exponents fit the gap
below \(\tau_0\). Let \(\bar\mu\) be its average coordinate marginal.
The support of each neighboring kernel implies that \(\bar\mu\) is
supported on common neighbors of the star.

Set \(H_1=\{x:N\bar\mu(x)>e^{\tau_1n}\}\), whose uniform mass is at
most \(e^{-\tau_1n}\). Choose
\(\upsilon_1>\tau_0/\tau_1\) with
\(\upsilon_1+\upsilon_0<1\). The joint density bound and a subset union
give
\[
 \Pr_{\rm post}\bigl(\#\{i:z_i\in H_1\}>\upsilon_1k\bigr)
 \le 2^k e^{\tau_0kn-\upsilon_1k\tau_1n}
 =e^{-\Omega(kn)}.
\]
It follows that
\[
 \bar\mu(H_1)
 =\mathbb E_{\rm post}\frac1k\sum_i1_{\{z_i\in H_1\}}
 \le\upsilon_1+e^{-\Omega(kn)}.
\]
The gate separately bounds the marginal mass on prior-heavy labels by
\(\upsilon_0\). Removing both sets leaves a mass bounded away from
zero. Normalize the restriction to obtain the even row, with normalized
cap \(O(e^{\tau_1n})\). Use only the actually selected reference, and
set the row to zero if its actual gate or its \(m_c\) test fails.

\paragraph{Even comparison means and the Hall assignment.}
We first estimate the row under product odd sampling and raw centers at
a successful key history. For a fixed potential ID and reference \(c\),
cancellation of the posterior denominator against the gated data
subdensity bounds its contribution at a prior-light label \(x\) by a
constant times
\[
 \mathbb E_{\rm centers}\!\left[
    \left(k^{-1}\sum_i1_{\{z_i=x\}}\right)
                  \sum_{\mathbf y}F_z(\mathbf y)\right].
\]
The constant accounts for the truncation normalization. The sum over
\(\mathbf y\) is at most the indicator that this center is present
and legitimately selected with the size gate. We now bound that selection
probability before averaging the tuple marginal.

Force this center present and fix its tuple values, but continue to
average all other prospective presence and activation variables. At
level zero, conditional on presence, the eligible-active tie bound is
\(3/\lambda\). At positive levels the forced-center height estimate
gives \(e^{-n^c}\) for some fixed \(c>0\). At each presence
configuration this estimate first takes the supremum over fixed
pre-activation eligible sets of the required sizes, then averages over
presence. Fixing the tuple may change these sets, but does not change
the position/activation product law, since arrays were generated
independently. Thus this is neither a bound at every fixed presence
configuration nor a posterior conditioned on selection.

The sum of presence probabilities over possible locations is
\(\lambda\) at each level. There are polynomially many levels, so
summing the selection bounds costs \(O(1)\) per fixed subset. A tuple
reference consists of whole iid blocks, and its unselected average
marginal is \(\bar P_K\), at most \(B_K/N\) on a prior-light label.
The number of possible high subsets is \(\exp(O(k_*))\). Consequently
the normalized comparison mean for the even row at \(v\) is at most
\[
 d_v=O\bigl(B_{K(v)}\exp(O(k_*1_{j(v)>J}))\bigr),
\]
whose deterministic average over actual even roles is bounded by the
cube-rarity calculation above.

For the final scattered-moment calculation set \(Z_v(x)=Np_v(x)\) for
the even rows and retain the actual success indicator. The cap is
\(O(e^{\tau_1n})\). A row's near set consists of residual-coordinate
distance at most \(2r+o(n)\). With
\(H_{\rm bin}(t)=-t\log t-(1-t)\log(1-t)\), its repeat cost is at most
\[
 n\exp\{-n(\log2-H_{\rm bin}(2\rho))+o(n)\}
                      O(e^{\tau_1n})=o(1).
\]
For up to \(n\) separated rows, at most \(n^2\) odd outputs are needed.
At a successful prehistory and fixed center data, apply the clock
comparison to these outputs. Then remove nonlocal success restrictions
but retain each local gate, and integrate the raw centers. The separated
rows have disjoint long-rule scopes, so their integrals factor and give
\[
 \mathbb E\!\left[1_{\rm success}\prod_{v\in U}Z_v(x)
                \,\middle|\,\text{successful key history}\right]
 \le (1+o(1))\prod_{v\in U}d_v
\]
for such a separated set \(U\), with harmless fixed factors included
in \(d_v\). Scattered moments and the label union give bounded normalized
average even loads. Since \(|A|/N\to0\), every even column sum is at
most one, except on an event of probability \(o(1)\) intersected with
the preceding successes.

The key-history, geometry, odd-load and predictive estimates together
have success probability tending to one under their successive stage
laws. Thus with positive probability the odd assignment is injective
and every even row is a probability law on its common neighborhood,
with all even column sums at most one. Hall's theorem gives distinct
even representatives. The two assignments form the required
\(G\)-cube.
\end{proof}
==== END The-hypercube-Ramsey-number-has-linear-order//sections/05-a-constant-broad-high-neighborhood-case.tex ====

==== BEGIN The-hypercube-Ramsey-number-has-linear-order//sections/06-very-small-polynomial-width-on-the-broad-side-polynomial-defect.tex ====
\section{A broad side with a small polynomial density cap}
\label{sec:very-small-polynomial-width-on-the-broad-side-polynomial-defect}

\begin{lemma}[A broad side with a small polynomial density cap]
\label{lem:small-polynomial-broad-side}
Work in the counterexample sequence fixed above. There is a universal \(D_*>0\) with the following property. Let \(0<\gamma<1,\ p_0>0\) be fixed. Suppose a finite random tag of law \(\Lambda\), with pairs \((\mu_i,\nu_i)\) on \(X,Y\), satisfies
\[
 N\mathbb E_\Lambda\mu_i,\ N\mathbb E_\Lambda\nu_i\le K,\qquad
 \operatorname{width}(\mu_i)\le n^\gamma,\qquad N\max\nu_i\le n^{D_*},
\]
where \(K\) is a constant and both average inequalities hold pointwise. In one color \(G\) assume on every support \(y\in\operatorname{supp}\nu_i\), \(d_G(\mu_i,y)\ge1-\epsilon,\ \epsilon=n^{-p_0}\). Then one of the colors contains the cube for large \(n\).
\end{lemma}

\begin{proof}
The preliminary reduction either produces a cube in the opposite color
or supplies pairs of parent labels that both see a common first-side law.
In the latter case we construct first-side tuples hitting those parents,
then use their observations to assign the odd roles. The posterior of a
whole tuple after its odd neighbors are assigned will supply the even
row for Hall's theorem. This follows the parent and height construction
of Lemma~\ref{lem:constant-broad-high-neighborhood}, with two changes:
each tuple carries a tag that must be deleted along with its entries,
and a high odd row redraws an actual parent rather than a hidden vector.
The constant \(D_*\) is universal; only subsequent auxiliary choices
and the sufficiently large dimension threshold may depend on the fixed
input parameters.

\subsection{Local base histories and hidden tags}
\label{sec:local-base-histories-and-hidden-tags}

The second-side mixture and its tag posterior are
\[
 \Pi(y)=\sum_i\Lambda(i)\nu_i(y),\qquad
 \eta_y(i)=\frac{\Lambda(i)\nu_i(y)}{\Pi(y)},\qquad
 B_y=\sum_i\eta_y(i)\mu_i
\]
when \(\Pi(y)>0\). Thus \(B_y\) is the first-side law obtained by
observing \(y\) in the second-side mixture. Restrict \(\Pi\) and normalize
to obtain \(\Pi'\) on \(\{y:N\Pi(y)\ge n^{-D_*}\}\). The discarded mass
is at most \(n^{-D_*}\), and \(\Pi'\le O(K)/N\).

Suppose first that two independent \(\Pi'\)-draws satisfy
\(d_G(B_y,y')