One shared random coloring and a small exceptional set

This chapter studies Lemma 6.3 of H, in Section 6.2, pages 41–43. It supplies a fixed successful color realization for the historical ball masks in the following Section 6.3. The source is the fixed October 5, 2026 version of An $L^3$ bound for the trilinear Hilbert transform.

We prove two statements. For every realization of the delay arrays, each vertex changes color only a controlled number of times. Moreover, one global realization can be chosen so that the first cells with failed markings have any prescribed small fixed total length relative to the root. This second statement uses one realization for the whole tree, rather than a separate choice of random numbers for each spatial path.

The inputs are fixed original vertex lists and graph distances that do not increase with depth. The main columns, helper columns, and linearized modes constructed later do not add graph vertices, as stated explicitly on page 39 of the source.

Back to the guide to H

1. Fix the finite tree, vertices, and graphs before sampling

Fix a finite dyadic tree below a root interval $R$. At each cell $I$, write $\mathcal V(I)$ for the original vertex list, consisting of the occurrences of original columns in all relevant slots. A child inherits its parent's list and may append new vertices. The admission order, including the order of simultaneous births, is fixed in advance. Different branches may admit different vertices. Two vertices with the same curvature tag are still distinct occurrences of original columns, and their delays are sampled independently.

Assume that the total number of vertices ever admitted on each downward path from the root is at most the integer $D\ge2$. The total number of vertices in the whole tree need not be at most $D$. It is finite because the tree is finite, but it will not enter the final error bound.

The graph is defined on all hypothetical curvature tags satisfying the basic bounds. At absolute depth $s$, write $d_s$ for its distance, which may equal $+\infty$. Equal tags have distance zero, and

These distances depend on the curvature tags and absolute depth. They do not depend on spatial location, whether a vertex is currently present, colors, or delay arrays. Distances are defined even for tags whose vertices have not yet been born.

The order of quantifiers is therefore as follows: first fix the lists, admission data, and entire graph family; then sample the arrays. The conclusions are uniform over all such fixed graph families. They do not require one array to work simultaneously for every possible graph family or every edge threshold.

2. The parameters and two shared arrays

Fix the integer scale parameter $P\ge1$ from the source, and put

An unqualified $\log$ denotes the natural logarithm. The final probability bound does not depend on the particular sizes of $b_1,b_2$. Their special ratio is used later in the historical ball masks.

For each vertex $z$ born anywhere in the tree, sample two families of delays

The variables are independent across all births, rounds, and the two families. Each delay is a truncated geometric variable:

The symbol $D_{\mathrm{one}}$ above describes the distribution of a single delay only. Below we use the indexed variables $D_z^{\mathrm{pri},q},D_z^{\mathrm{hi},q}$, keeping them distinct from the vertex-count bound $D$.

A vertex's delay in a given round is sampled only once and is then used throughout the inherited lists. The high-round arrays are shared by all frozen contexts. Resampling whenever the center or group changes would invalidate the later arguments for finitely many stages and one common realization.

3. Primary scores, successful markings, and fixed prefixes

At the current depth $s$ and a currently present vertex $v$, primary round $q$ assigns competitor $z\in\mathcal V(I)$ the score

An infinite distance gives score $-\infty$. The vertex $v$ itself is a competitor at distance zero, so the top score is always an integer in $\{0,\ldots,d_0\}$.

A round is successfully marked if it has a unique winner whose score exceeds every other score by at least $5$. Choose the first successful primary round, and denote its round number, top score, and winner by $q,g,z$, respectively. If no round succeeds, use fixed failure placeholders.

Let $i$ be the winner's admission index and $j\ge i$ the current list size. If $j=i$, use the equality cohort and the prefix through $i$. Otherwise, in the fixed dyadic decomposition of the positive integer indices, take the unique smallest block with $i$ in its lower half and $j$ in its upper half. Throughout this upper-half cohort, freeze $W$ to be the prefix through the end of the lower half. In particular, $z\in W$, and all vertices in $W$ are currently present.

For a fixed winner, the list size only increases. The total number of equality and dyadic cohorts it encounters is therefore at most

After leaving an upper half, the next block containing the same winner's index must be larger. A smaller block that has already been left cannot be revisited.

4. The high rounds use pseudometrics frozen over all depths

Fix a primary round, winner, top score, and prefix context. For every hypothetical tag $a$ and every absolute depth $s'\in\mathbb Z$, define

An empty maximum is $-\infty$. The profiles include all depths before and after the births of their arguments and are nondecreasing in depth.

Put

where $1\le l\le d_0$, with the convention $C_l(-\infty)=T_l$. Define

This is always a finite pseudometric. Since $C_{l+1}\circ C_l=C_{l+1}$ and the clipping maps are $1$-Lipschitz,

Once the context is fixed, none of the $d^{(l)}$ vary with the current depth, current vertex list, or high-round arrays. They may depend on the primary arrays; the probability argument handles this by conditioning on those arrays first. For the finitely many pairs of admitted vertices actually tested in this chapter, the supremum ranges over integer depths and depends on only finitely many primary delays. Thus no additional measurable choice is needed. This does not treat the set of all hypothetical curvature tags as finite.

5. Two adjacent balls always have the same size class

Put

and let

Each ball contains the current center $v$, so its size is positive. The pseudometrics are nonincreasing in $l$, while the radii increase with $l$. Hence

Thus $N_1\le\cdots\le N_{d_0}$, and all these values lie in the range

If every adjacent pair increased strictly, we would have $N_{d_0}-N_1\ge d_0-1$, a contradiction.

We may therefore choose the least $l<d_0$ such that $N_l=N_{l+1}$, and denote the common integer by $n$. The high rounds use the pseudometric $d^{(l+1)}$. In round $q'$, the competitor score is

Choose the first successful high round, with round number, top score, and winner denoted by $q',g_2,a$. Use fixed placeholders on failure. The center is again a competitor at distance zero, so $0\le g_2\le d_0$.

6. Monotone scores allow only finitely many successful stages

We first isolate the counting argument. Fix one target vertex and one round. Competitors are added over time, every existing competitor's score is nondecreasing, and the top score always belongs to $\{0,\ldots,d_0\}$.

Consider a consecutive time interval with constant top score $g$. Suppose a successful marking occurs within it, with winner $z$. At each earlier time in the same interval, some competitor already has score $g$. Its score cannot decrease and is still $g$ at the successful marking, so it must be the unique winner $z$. Every other competitor's earlier score is no greater than its score at the successful marking, and is therefore at most $g-5$.

It follows that, within an interval of constant top score, the successful times form an initial consecutive interval with a fixed winner. Once a rival destroys the gap, success cannot return while the top score remains unchanged. Each round has at most $d_0+1$ successful stages.

Describe the state of a round as either failure or success with its top score and winner. This state changes at at most $2(d_0+1)$ boundaries. Taking all boundaries from $d_0$ rounds, the number of stages for the first successful round and its top score and winner is at most

No independence of the states over time is assumed. This is a deterministic count for every fixed realization of the delays.

The primary rounds satisfy these assumptions because graph distances are nonincreasing with depth and births only add competitors. Within a fixed context and an interval with fixed $l$, the high rounds satisfy them as well: existing scores are constant, and only new competitors are added.

7. Counting ball stages without counting depths

Fix a vertex $v$ and follow a spatial path after its birth. The selected primary data have at most $5d_0^2$ stages. Each successful stage splits into at most $d_0$ prefix cohorts.

Within one prefix cohort, all pseudometrics are fixed. A ball grows only when original vertices are added to the list. Consequently,

is coordinatewise nondecreasing, and each coordinate has at most $m_D+1\le d_0$ integer values. The number of changes of the whole vector is bounded by the sum of the total increments of its coordinates. Its number of constant stages is therefore at most

Within each stage, the selected $l,n$ and the high-round pseudometric are fixed. By Section 6, the selected high-round data have at most $5d_0^2$ stages.

Multiplying the bounds, the number of stages of the complete selected data for each vertex is at most

A failed primary stage requires no prefix or ball construction. Treating it as one fixed failure state only reduces the actual count. The bound is independent of the total depth of the tree.

8. Finitely many colors and a decreasing counter

The color contains seven coordinates:

Each coordinate, including failure placeholders, has at most $d_0+2$ possible values. A successful group additionally specifies $z,a,W$ and the exact dyadic cohort block. The winners' identities are not themselves color coordinates.

At a vertex's birth, initialize its change counter to $d_0^8$. Decrease it by $1$ whenever any of the seven color data or either winner's identity changes. By the preceding section and $d_0\ge50$, the number of changes is at most $50d_0^7\le d_0^8$, so the counter never becomes negative.

Order the counter and seven coordinates lexicographically, with the counter first. Embed this ordered set into the integer color set by one order-preserving encoding shared by all vertices. The total number of possible states is at most

Whenever the data or a winner changes, the first coordinate strictly decreases, regardless of changes in the other coordinates. Thus each vertex's color is nonincreasing along a path and changes at most $d_0^8$ times.

Vertices of the same color have identical values of the seven metadata coordinates, but need not have the same winners. The group data distinguish winners and frozen prefixes. These are precisely the color and group data used by the historical ball masks.

9. A fixed score situation has a uniform success probability

A fixed score situation consists of a finite set of at most $D$ competitors and a fixed penalty $c_z\in[0,\infty]$ for each competitor. At least one penalty is zero. The scores are $X_z-c_z$, where the $X_z$ are independent untruncated geometric variables. In the primary and high rounds, the penalties are the integer parts of the corresponding distance quotients.

For each outcome of the geometric variables, use a fixed order to choose one top-score winner $z$, and increase only $X_z$ by $5$. In the resulting outcome, this winner is unique and leads every other competitor by at least $5$.

This map is injective: the unique winner in the image identifies the coordinate that was increased, and subtracting $5$ recovers the original outcome. Since

the probability of each image outcome is exactly $2^{-5}$ times the probability of its preimage. Summing over all original outcomes yields

A competitor with infinite penalty cannot win. A competitor with zero penalty ensures that a winner exists.

Truncate each variable at $d_0$. The outcome can change only if $X_z>d_0$ for some competitor. Hence

The last inequality follows from $d_0=\lceil1000\log(2D)\rceil$ and $D\ge2$. For this one fixed situation, the rounds are independent, so the probability that all $d_0$ rounds fail is at most

This bound cannot be applied directly to a situation selected using the same random variables that are about to be revealed. We next construct a deterministic list of primary situations and a conditional list of high situations.

10. Polynomially many deterministic primary situations suffice

Fix a spatial path, or equivalently a point $x\in R$ away from dyadic boundaries. At most $D$ vertices are born along this path. Their admission order and all graph distances are fixed before the primary arrays are sampled.

For each ordered pair of vertices on this path, define the capped penalty

with infinity also capped at $d_0+5$. This is a nonincreasing integer sequence and changes at most $d_0+5$ times per pair. All ordered pairs, together with at most $D$ changes of the list, produce at most

stages on which both the list and the whole capped penalty matrix are constant.

Capping does not change whether a round succeeds or who wins. A competitor whose penalty was capped has score at most $d_0-(d_0+5)=-5$, whereas the top score is at least zero. It can neither win nor violate the requirement of a lead of at least $5$. Here the source's non-strict gap condition, at least $5$, is essential.

Each stage requires tests at at most $D$ present vertices. Thus the number of fixed primary situations is at most

This list is independent of all delays. Applying the all-round failure bound to each situation and then the union bound gives

Different situations may be highly dependent. The union bound does not require independence.

11. Condition on the primary arrays before listing high situations

Now fix an arbitrary realization of all primary arrays, without revealing any high-round delays. For each vertex on the path, the primary stages, prefix cohorts, and ball-count stages together number at most

Within every such stage with a successful primary round, the primary context, selected $l,n$, and entire pseudometric $d^{(l+1)}$ are fixed.

The high-round competitors still form the current prefix. Within a stage there are at most $D$ such prefixes. Across all of the at most $D$ target vertices, the number of high situations is therefore at most

Each situation consists of a target vertex, a fixed frozen pseudometric, and a fixed current prefix. It is a function of the primary arrays and does not depend on the high arrays. Even if a later high-round failure stops the construction, the list is formed in advance to include every situation that could be needed before stopping.

Conditional on the primary arrays, the high-round variables retain their original independent distributions. For each fixed situation, the probability that all rounds fail is still at most $e^{-d_0/64}$. Hence

This conditional bound is uniform over all realizations of the primary arrays, so it remains valid after taking expectation.

We use independence between distinct born vertices in the same high round and between different high rounds. Different frozen contexts share the same high arrays; no independence between contexts is assumed or available. Sharing is precisely what later allows the same high-round delay to cancel when two historical centers are compared.

12. The explicit bad-path probability and a small fixed proportion

Call the fixed path bad if some currently present vertex has no successful primary marking, or has no successful high marking after a successful primary marking. The preceding two sections imply

where

This bound contains neither the total depth of the path nor the number of spatial branches in the whole tree.

Since $d_0\ge1000\log(2D)$,

Also, $d_0=O(\log(2D))$, so

There is no need to optimize the exponent. It is used only to reach any small fixed proportion specified in advance.

The exact order of choice is to prescribe $\varepsilon_{\mathrm{bad}}\in(0,1)$ first, then choose the allowed vertex-count bound $D$ or starting accuracy $k$ sufficiently large that $q(D)\le\varepsilon_{\mathrm{bad}}/2$, and only then fix the chapter's parameters and sample the arrays. Increasing the allowed bound $D$ adds no actual vertices. The proof of Proposition 5.8 on page 38 of the source already uses $D_{\mathrm{base}}\ge e^k$, and page 39 sets $D=D_{\mathrm{base}}$ while allowing this bound to be enlarged. Thus, after fixing the error proportion, increasing the starting $k$ does make $D$ tend to infinity, while still preserving $\log D\le k^{O(1)}$.

This does not assert that, for an already fixed small $D$, the same $d_0$ can achieve every prescribed error proportion.

13. Integrate over space to select one global realization

There are finitely many births in the whole tree, and each truncated delay has finitely many values. The entire sample space is therefore finite. All colors and failure events can be defined simultaneously on every original cell. The suprema over integer depths in the frozen profiles are also well-defined measurable functions.

Let $\mathcal B(\omega)\subset R$ be the set of points for which some ancestor cell has the specified failure under delay realization $\omega$. This is a finite union of dyadic cells. Interchanging expectation and spatial integration for a nonnegative function yields

Markov's inequality then implies

Hence there is at least one global realization $\omega_*$ such that

The color-count conclusions of Sections 6–8 hold for every realization. This same realization therefore also has nonincreasing colors, at most $L$ colors, and at most $d_0^8$ changes per vertex.

We have not required every path to succeed simultaneously, or applied a union bound with a cost proportional to the number of spatial branches. Bad paths are allowed; their Lebesgue measure is controlled.

14. Why use the first failure cells?

Under $\omega_*$, send the first cell on each path where a required marking fails to a fresh attempt. Let $\mathcal F$ be the collection of these first failure cells. Include each cell only once. A cell with an already failed ancestor is not included as a first failure cell.

Two intersecting dyadic cells are nested, whereas no first failure cell can be a strict ancestor of another. The first failure cells are therefore pairwise disjoint. Each also lies in $\mathcal B(\omega_*)$, so

With half-open dyadic cells, disjointness holds literally. Using closed intervals changes only a null set of boundary points.

If the construction requires markings only at some cells or vertices, its first required failure cells correspond to a subset of the failure events already counted and satisfy the same bound. On the retained paths, every actual use of a color or historical mask has successful primary and high markings.

This chapter controls this source of failure only. Combining it with the other catalog, size, and maximal-function stopping rules into the full restart argument of Section 10 of H still requires the respective error and root-length bounds.

15. What is supplied to the historical masks, and what remains

We can now fix the chosen $\omega_*$. Each vertex's primary delays remain unchanged along inherited lists; the high arrays are shared by all frozen contexts; colors are nonincreasing; and each successful group has fixed primary-round, score, cohort, ball-level, count, high-round, and winner data. After removing the first failure roots, this chapter supplies the successful marking realization assumed in the chapter on historical ball masks.

This conclusion relies on the data being fixed in advance as in Section 1. The original lists and graph family cannot be altered arbitrarily after observing the delays. New main columns, helper columns, and modes cannot be admitted as new graph vertices. Allowing such adaptive changes would invalidate the deterministic situation list in Section 10 and the situation list depending only on the primary arrays in Section 11.

This chapter does not develop the same-tag template tests, catalog closure for changing projection histories, or the full two-sided estimate. Those arguments may use the color realization constructed here, but they do not follow automatically from the small probabilistic exceptional set.