The hypercube Ramsey number has linear order

Proof. Each fixed dimension has finite Ramsey number by the finite Ramsey theorem [30]. 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

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.□

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.□

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

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 [24]. At that point every player’s expected-vector bound holds.□

Proof. The local lemma and its conditional induction go back to Erdős and Lovász [9, Section 2]. Erdős and Spencer introduced the lopsided nonneighbor condition [10, Section 1]; see Lu and Székely [27, Lemma 3] 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,

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.□

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.□

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,

with the left integrand set to zero where m=0. This is the asserted cancellation.□

Proof. Step 1: the path event to be estimated. Use the metric

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

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

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.

Step 2: the smallest scale. 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.

Step 3: separated child paths and ball intersections. 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

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.

Step 4: removing shared centers. 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,

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,

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 (3.1) 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.

Step 5: heights and local approximations. At the top scale, n^aH^\theta\ge n^{a+(1-\zeta)\theta}, whose exponent is greater than one. Thus (3.1) 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

Displacements at least H contribute at most \exp(O(n)-n^aH^\theta). The exponent comparisons in Step 4 show that the sum, together with the base-scale contribution, is at most \exp(-n^c). All arguments hold in deterministic restricted path domains and for position-averaged eligibility suprema. This proves (ii) with the stated local and forced-center uniformity.

A path reaching the query but leaving its D\lfloor\sqrt m\rfloor-tube has displacement from its start at least \sqrt m/3. Only scales with R_i\ge\sqrt m/(3M), or a top-scale failure, need be counted. The previous sum now has exponent much larger than m^{1/5}, since

Here a>\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.□

Proof. It suffices to construct the labels: the independent conditional draws then give both assertions for full outputs.

Step 1: complete the columns and order the rows. 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

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

A uniform random order has this property with positive probability. Indeed the expectation is s_j, and exposure without replacement has martingale increments bounded by the column atom range. Bounded-difference concentration [23, 1], followed by a union over j,y, gives the asserted error. Fix one such order.

Step 2: track the mass already used. At step j, sample row j’s law conditional on its label still being free. For each row a, let

Thus D_j^a is the mass that row a assigns to labels used before step j. Stop at the first e_j>1/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

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

For the equality, use summation by parts on the column-prefix error against the bounded nondecreasing sequence e_j. A second summation by parts replaces p_j(y) by 1/d in the remaining drift sum: the sequence \mathbf1_{\{y\ \mathrm{free\ before}\ j\}}/(1-s_j) has bounded variation. The resulting sum is

Subtracting s_b now gives, even at a potential stopping index,

Iteration bounds e_b by O(d^{-1/8}). This is smaller than both 1/20 and d^{-.1} for large d, proving the claim. Call this successful tracking event G, and condition the sampler on G.

Step 3: compare specified targets multiplicatively. Fix l distinct positive-probability target labels y_i on queried rows. Define a second sampler that forces Y_i=y_i at each queried step and, at every ordinary step, excludes all target labels whose queried steps are still pending. On a path realizing the targets and satisfying G, the likelihood of the original unconditioned sampler divided by that of the forcing sampler is the product of

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

Tracking permits replacement of s_j by D_j^j at error O(d^{-.1}); omitting queried steps costs O(l d^{-.95}) per target. Thus the linear terms in the ordinary-step logarithms cancel -\log(1-D_i^i). The quadratic terms have total size O(l^2d^{-.95}), because each subtracted fraction is O(l d^{-.95}) and their sum is O(l). The total log-error per target is O(d^{-.1}+l d^{-.95}).

Integrating this ratio under the forcing law, and dividing by \Pr(G)=1-\exp(-d^{\Omega(1)}), gives the joint upper comparison \exp(O(d^{-.09}l))\prod_i p_i(y_i). For a single target the same ratio also gives a lower comparison (1-O(d^{-.09}))p_i(y_i): the forcing sampler itself tracks with exponentially small failure probability. Indeed, before a constant-error stop, excluding the one pending label changes a step’s distribution in total variation by O(p_j(y_i)). Since the tracked increment is O(d^{-.95}), the cumulative drift change is O(d^{-.95}\sum_jp_j(y_i))=O(d^{-.95}); the forced step contributes another O(d^{-.95}). The proof of Step 2 therefore still applies. The target mass was extracted before this tracking exception was bounded; no absolute error is divided by a tiny atom.

Step 4: calibrate the individual marginals exactly. Return to the original .4 column bound. For arbitrary real prices c_i(y) on the real row-label pairs, put \bar c_i=\sum_y p_i(y)c_i(y) and \delta=d^{-.05}. Perturb row i by multiplying its probabilities by 1+\delta\operatorname{sign}(c_i(y)-\bar c_i), then normalize. Writing p'_i for the result, its gain in centered expected price is

The perturbed rows satisfy the relaxed hypotheses of Step 1. The tracking sampler’s two-sided singleton error is O(d^{-.09}) relative to p'_i, so its error in this centered price is at most O(d^{-.09})\sum_y p_i(y)|c_i(y)-\bar c_i|, smaller than the gain. Its joint upper bound, measured against the original inputs, costs \exp(O(d^{-.05}l+d^{-.09}l)), which fits (3.2) for large d.

Let \mathcal C be the set of all laws on injections of the real rows satisfying the joint upper inequalities relative to those original inputs. These are linear inequalities on a finite probability simplex, so \mathcal C is compact and convex. Every price-dependent construction just made belongs to this same set, and its marginal vector has price at least that of the original marginal vector. If the original vector were outside the marginal image of \mathcal C, a separating linear functional would contradict that property. It therefore belongs to the image, giving exact marginals while preserving all joint bounds.□

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 3.5 enforce a match at every real row and avoidance of every predicate, at a multiplicative cost 1+o(1) on the queried outputs.

Step 1: trim rare outputs and complete the columns. For each row a and incident failure predicate F, discard outputs o for which

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_*}).

Step 2: matching and its backward explorations. 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 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.

Step 3: exploration leaves and nonneighbor conditioning. 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

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.

Step 4: inserted paths bound the incidence sum. 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

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

The remaining short insertions meet at most one row of the test. We now bound bad outcomes uniformly under each such insertion.

Step 5: the exploration rarely becomes giant. 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

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

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.

Step 6: track the free mass in a background process. 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,

These are the available label mass of a row and the available row mass at a label. The deterministic comparison functions solve

In particular q=1-\theta+\theta z and 0<q,z\le1. We claim, with error probability at most \exp(-n^{A_*/3}), that throughout [0,T_0], uniformly over original endpoints,

The estimate is uniform for each fixed removal and insertion prescription; we do not take a union over all such prescriptions.

A free label y is matched at ordinary rate R_y, and a free row a at rate X_a. Hence the ordinary drifts of these masses are -\sum_{y\ \mathrm{free}}p_a(y)R_y and -\sum_{a\ \mathrm{free}}p_a(y)X_a. If E(t) is the maximum of the claimed approximation errors, each drift differs from its ODE drift by at most 2E(t). Removals cause initial error O(n^B\lambda_*), and inserted matches cause total jumps O(\log n\,\lambda_*).

The drift-compensated ordinary-jump martingales have jumps at most \lambda_* and predictable variance at most T_0\lambda_*. Their running absolute maxima exceed n^{-A_*/4} with probability at most \exp(-n^{A_*/2-o(1)}) per endpoint. For completeness, compensating e^{vM_t} costs log-rate at most v^2 times the variance rate when |v|\lambda_* is small; this follows from the exponential series for each jump. Use both signs of v=n^{-A_*/4}/(2T_0\lambda_*) and stop at the first crossing. This is the bounded-jump exponential estimate used here; compare [15]. A union over O(g) endpoints is permitted by \log g=O(n). Finally drift iteration yields

Taking A_*/4>2K_0+3B, with slack, proves the claim and its stated exception probability.

Step 7: ordinary target matches have a product upper bound. 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:

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

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)}.

Step 8: bound bad leaves and impose avoidance. 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 3.5 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.□

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.

Step 1: a density plateau. Set

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 (i). 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

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_j<n^{-\omega/3}, and a maximizing pair at its smaller budgets. Write these budgets as s_X,s_Y, its color as G, its first law as \mu_i, and its density as p=1/2+a_i, where a_i\ge a_*.

We can trim the second law to a law \nu_i such that

To see this, first consider the columns with degree greater than p+n^{-\omega/3}. If their mass exceeded \eta=\exp(-n^{\gamma-\omega/2}/2), conditioning on them would increase width by less than n^{\gamma-\omega/2}/2 and produce a density larger than P_{j+1}. Their mass is therefore at most \eta. If t is the mass of columns below p-n^{-\omega/5}, the original mean p gives

Thus t=o(1), so retaining the other columns costs less than one unit of width. We also retain the following upper density bound: any laws supported in this patch with respective widths at most

have G-density at most p+n^{-\omega/3}. Both laws fit the next budget pair, which proves this bound independently of the trimming. The index i records the laws, budgets, and density just obtained.

This construction works after every removal allowed by hypothesis (i), so the resulting patches are available. Lemmas 3.2 and 3.3 allow us to pass to a subsequence, fix one available color G, and use a finite balanced mixture of its patches.

Step 2: a coordinate key distributing the patches. We need a function g on cube roles whose values are spread over many keys, while only a small number of keys occur among the neighbors of any one role. It will use \lfloor n^{\gamma-\omega}\rfloor disjoint coordinate gadgets. In each gadget take s' chunks of (s')^6 bits, where S=s'+1 is a power of two and s'\asymp n^{2\omega}. The number of bits used by all the gadgets is

For one gadget, clip each chunk’s count of ones to a central interval consisting of S^2 integer unit steps, and translate that interval to [0,S^2]. Denote the clipped values by t_1,\ldots,t_{s'}, with chunk labels retained. Each endpoint has probability at least 1/3: the counts are symmetric, and their maximum binomial atom is O((s')^{-3}), so the unclipped central interval has probability O(S^2(s')^{-3})=o(1).

Sort these values by rank and add sentinel ranks 0,S with values 0,S^2. A binary search starts from the rank interval [0,S]. At every step its rank endpoints a,b have values enclosing [aS,bS]. At the middle rank, compare its count with the fixed value (a+b)S/2. If the count is at least this value, continue in the left half; otherwise continue in the right half. The invariant is preserved. At a leaf, two consecutive ranks enclose one elementary interval of length S. The gadget outputs the index of that interval and the labeled subset of chunks above its midpoint.

There are two useful properties of this output. First, all one-bit changes to a fixed input produce only O(\log n) possible outputs. If the search path is unchanged, membership above the leaf midpoint is unchanged. Otherwise consider the first comparison that changes on the original path. One clipped count must move between a multiple of S and the integer immediately below it. Once that comparison and the direction of the move are specified, the new multiset of counts is fixed. The identity of a tied chunk making the move does not affect the output: its count stays on the same side of every elementary midpoint. There are only O(\log n) comparisons on the original path and two directions. Second, for any fixed output, each chunk is required to lie on a specified side of a fixed midpoint. Either requirement has probability at most 2/3, because the opposite clipped endpoint has probability at least 1/3. Independence of the chunks bounds the probability of that output by (2/3)^{s'}.

Let g be the joint output of all gadgets, and for odd u let Z_u=\{g(v):v\sim u\}. Flipping one bit changes at most one gadget, so

In the second estimate, v is a uniform role on either fixed cube parity. The unused coordinates allow the special bits to remain uniform after parity is fixed.

Assign a patch index i_g to each key so that the averages of \mu_{i_{g(v)}} over v\in A, and of \nu_{i_{g(u)}} over u\in B, are pointwise at most K/N for a fixed K. Such an assignment follows by drawing the tags independently from the balanced mixture. For example, if \alpha_g is the fraction of even roles with key g, each summand in the normalized mean at a fixed label is bounded by

The same bound holds on the odd side. The summand bound is at most \exp(-c n^{\gamma+\omega}) for some fixed c>0, 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.

4.1 Hidden tuples and height choices

Step 3: tuples and the masses retained by their filters. The height device will let nearby even roles choose from a common set of tuple indices. Use Lemma 3.8 on the even sites of Q_n, with

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

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 kth 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

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

and, for every c\in\mathcal D and g'\in Z_u,

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 [14, Lemma 2.1]. 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

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 (ii).

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

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

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

Call such an entry a dip. Its indicator is set to zero once an earlier entry has had q<e^{-L}. This stopped sequence is adapted to the successive exposures, and its conditional expectation bound remains valid throughout; we do not condition on eventual validity. The bounded-increment inequality [1] shows that an own-key last tuple has at most a_*k/(20L) dips, except with probability \exp(-\Omega(ka_*^2/L^2)). On a path with no step below e^{-L}, each dip costs at most L in the negative logarithm of the retained fraction; at every other own-key entry, \log q\ge-\log2+.7a_i. Multiplying the k fractions gives the own-key ratio above, for sufficiently small c_1. For a cross-key tuple the lower bound q\ge e^{-L} already gives its ratio. The same bound on all entries gives the lower bound for R_u(\mathcal D). There are only polynomially many entries and choices of the last tuple, and ka_*^2/L^2=n^{\omega/3-4h+o(1)}. A union bound therefore gives the claimed \exp(-n^{\omega/5}) failure estimate.

Step 4: excluding failed sets and selecting heights. We now define eligibility before activating centers. For each odd role u and consecutive pair of levels, consider all ID sets of size at most T from the prospective centers in the balls of its incident even sites at these levels. Among the sets invalid at u, take a maximal disjoint family, using a fixed local rule, and mark every ID in its union forbidden for those even sites, at that ID’s own level. Every invalid set intersects this union; otherwise it could be added to the family. Consequently every set consisting entirely of the remaining eligible IDs is valid.

Binomial tails show that, with probability tending to one, every site-level ball contains between \lambda/2 and 2\lambda prospective centers. Fix such positions and all masks. For a given odd role and level pair, a prospective list of at most T IDs can be chosen in \exp(O(T\log n)) ways. Invalidity events for disjoint ID sets depend on disjoint tuples, hence are independent under this conditioning. The probability of a disjoint family of n invalid sets is therefore at most

Since T=O(n^{\omega/30}), this bound still tends to zero after the union over all odd roles and level pairs.

Thus each such family has fewer than n members, each with at most T IDs. An even site has n neighboring odd roles, so at most O(n^2T) IDs are forbidden in any one of its level balls. This is o(\lambda), leaving at least \lambda/3 eligible centers. Activate the centers and apply the long local height rule of Lemma 3.8, with uniform eligible active choices. With probability 1-o(1), the stated counts hold and the rule gives correct heights everywhere. Around an odd role, these heights occupy at most two consecutive levels because its even neighbors are at distance two from one another. At each occupied level the crowd bound in a representative site’s (r+2)-ball allows at most n^b selected IDs. The actual set therefore has size at most 2n^b<T and, by the marking argument, is valid. Call this global count, eligibility, and height outcome geometric success.

At an odd role u with valid incident choices, let p_u be \nu_{i_{g(u)}}^M restricted to the corresponding tuple hits and normalized. If the choices fail, or their ID set is too large or invalid, define p_u=0. Thus it is always a subprobability. Auxiliary product experiments may use fixed fallback samples for these zero rows; the fallbacks do not replace the zero output in a load estimate. Every rule uses only data within distance O(r+H): height choices consult their long tubes, and marks consult the nearby balls, tuples, and odd masks. No rule consults geometric success itself. On that success all odd rows are probabilities, and the retained-mass bound always gives

Step 5: the posterior tuple and even common neighbors. Fix an even role v and a possible reference ID c in its ball at some level. Let E be the following local event: c is present and is legitimately selected at v by the long path rule and its tie, at a good height below H; eligibility sizes are correct throughout v’s height tube; all neighboring odd kernels are valid; and the prospective counts in every neighboring-filter ball at all levels are at most 2\lambda. These conditions hold for the selected ID on geometric success.

Hold all preparatory data except z=W_{c,g(v)} fixed, including its mask. Its prior \pi remains the original product of k masked first laws. For the vector \mathbf y=(y_u:u\sim v) of odd-neighbor labels, define

Selection, validity, and all other local rules in this formula are recomputed for each replacement of z. Thus F_z is the likelihood including the event of selecting this tuple, not the likelihood conditional on its actual selection.

To remove dependence on z from the reference law, form a mixture at each neighbor u. Its terms range uniformly over ID sets of size at most T containing c, drawn from the present IDs in the incident balls at all levels. If the prospective count condition fails or this family is empty (in particular, if c is absent), E is impossible and we use a fixed reference probability instead of the whole mixture. Otherwise the count condition makes the logarithm of the number of terms O(T\log n). In each term omit every requirement from the indexed tuple W_{c,g(v)}, then normalize the remaining filtered law; use a fixed default if undefined or empty. These terms do not depend on z. In particular, they do not require the proposed set to pass its tests or to be selected. Let Q be the product of these mixtures over the neighbors of v.

On E, each actual odd kernel compares to its corresponding mixture term by the mass ratio from Step 3. All but at most m neighbors have g(u)=g(v), since only flips in special coordinates can change the key. The comparison cost for the product is consequently at most

Here T\log n=o(ka_*) and mL=o(a_*n). For a fixed 0<c_2<c_1, these two error terms fit within (c_1-c_2)a_*kn, giving

The entire tuple has been deleted in Q, while true selection and validity remain in F_z. This is precisely the distinction needed for Lemma 3.7.

Require, for the selected reference, that

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

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

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.

4.2 Balance and load transfer

Step 6: choosing mask distributions to balance the rows. 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

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

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 3.8 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 3.3 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.

Step 7: assigning odd labels and controlling even loads. 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 3.6, 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 3.9 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

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

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,

For the separated factors in an nth 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

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,

This is the separated-product hypothesis of Lemma 3.6; 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 [20] 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.□

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.

5.1 Parents, column indices and even types

Call y good for I if d_G(\mu_I,y)\ge .95, and define

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

and take \delta>0 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

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.

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

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:

• •

  at an interior key, the law of A_w given V_0,W_w[1:b_j];

• •

  at a boundary key, the law of V_0 given (A_{w'},W_{w'}[1:b_j])_{w'\in C_i}.

Here

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.

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

• •

  (i(P'),t,j), where P'=P or is obtainable by one coarse flip;

• •

  (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.

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

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

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.

5.2 Predictive estimates at the first two levels

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

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.

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

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

On the true-block gate, each exception has raw probability at most its threshold. For the ratio test, for example,

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

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.

5.3 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 6.1.

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.

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

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

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.

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,

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

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

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.

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_{<h}, let \mathcal P_h and \mathcal Q_{c,h} be the next-coordinate conditionals. They are functions of this prefix. Joint domination ensures that the deletion conditional is defined there. Smooth it with a small fixed uniform component to obtain \widetilde{\mathcal Q}_{c,h}, and put

If Y has law p, then \Pr_p(\log(q(Y)/p(Y))>z)\le e^{-z}: on that set p(Y)<e^{-z}q(Y). The positive part of this negative log has exponential moment at parameter 1/2 at most 2. Applying this conditionally at successive true prefixes shows that the sum of negative parts is O(s), except with probability e^{-\Omega(s)} per reference. By the chain rule, the sum of the full unsmoothed logs is at most a_3k_cs. Smoothing increases a positive log by at most a fixed constant. Consequently

The same argument against uniform measure gives

We choose K_D large enough to make this last bound a small fixed constant.

These are averages at the labels actually drawn. To control the averages of the conditional laws, fix a convex weight vector \xi on the references and a large fixed L_0. For the filtration \mathcal F_h=\sigma(\vartheta_1,\ldots,\vartheta_h), conditional on the fixed observations, set

The D_h^\xi are martingale differences bounded in absolute value by L_0. On the preceding actual-path bounds, failure of

forces \sum_hD_h^\xi<-\delta's/2, for large n. Its probability is at most \exp(-\Omega_{\delta',L_0}(s)). This concentration is applied before conditioning on any successful path. Applying it also to \min\{1,[\log(N\mathcal P_h(y))]_+/D_H\} bounds the average conditional mass of labels with N\mathcal P_h(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

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

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

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,

The gap from a_3 to a_4 therefore yields

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.

5.4 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

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

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.

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.

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.

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.

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}.

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.

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

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.

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

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,

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.

5.5 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.

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:

• •

  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;

• •

  the mapping uses at most T IDs, and all required singleton and hit tests pass;

• •

  the true-target gate, support conditions, and Step 3 numerical and path tests for this mapping pass.

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.

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,

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

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

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

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

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},

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.

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

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

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.

5.6 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

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

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.

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

Every choice, extracted subset and kernel is recomputed as z varies. The local gate E requires:

• •

  presence of the specified center and legitimate long-rule selection of this c at v, with its specified block subset;

• •

  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;

• •

  the prior-heavy fraction bound for c, and the high log budget at v when needed.

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

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

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

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

It follows that

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.

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

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

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

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

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.□

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 5.1, 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.

6.1 Local base histories and hidden tags

The second-side mixture and its tag posterior are

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')<c_0=.01 with probability at least .1. A set of first draws of positive \Pi'-mass then has a positive \Pi'-mass of such partners. Each partner set contains \Omega(N) labels because \Pi'\le O(K)/N. The laws B_y have width at most n^\gamma, and their average over these first draws is at most O(1)/N: indeed \mathbb E_{y\sim\Pi}\eta_y=\Lambda. Their degrees to the partners in the other color exceed .99. Lemma 5.1 therefore gives a cube in that color.

In the remaining case the directed bad-pair probability is less than .1. A union bound for the two directions shows that the relation

has (\Pi'\otimes\Pi')-mass greater than .8. In particular a positive \Pi'-mass of labels has partner mass at least .1. Draw V_0 from \Pi' restricted to those labels. Given V_0, draw the candidates A_w independently from \Pi'|_{\{y:y\asymp V_0\}}, with bins w defined below. Both the initial prior and every conditional candidate prior are bounded by constant multiples of \Pi.

Use the coarse and fine chunks of Lemma 5.1: there are d_c=300 coarse chunks of length \lfloor n^{1/5}\rfloor, and m=\lceil n^\alpha\rceil fine chunks of odd length asymptotic to n^{.3}. Their majority signs, exactly flippable coordinates, and number of counts within R_f=5.5 of mid-weight are denoted by t,F,j. Here use J=\lfloor m^{.04}\rfloor, and call j\le J low. The signs remain uniform on either cube parity, while \Pr(j\ge q)\le n^{-.13q} and the coarse boundary fraction is at most n^{-.05}.

The coarse key of a site x is h_x=(w,\mathrm{int/bdy}). Define its named primary variable by

and let P_h^* be the other member of \{A_w,V_0\}. Two keys have matching primaries when these are the same random variable, not merely when their realized labels agree. Give the coarse keys a symmetric relation connecting each key to itself, the two keys at a bin, and boundary keys at adjacent bins; let C(h) include all these neighbors and h itself. A coarse flip stays in this relation: if it changes the bin, both endpoints are boundary keys. Within C(h), only the opposite key at the same bin can have a nonmatching primary.

Given the parents, draw independent base tags I_h from \eta_{P_h} restricted to d_G(\mu_i,P_h^*)\ge c_1=c_0/2. The mean of this degree under \eta_{P_h} is at least c_0, so the restriction has mass bounded below by a positive constant. On the parent support,

Thus the conditional base-tag law is at most O(n^{2D_*})\Lambda.

Next, given the base (V_0,A,I), draw independent hidden scalars Z_\ell, indexed by \ell=(h,t). Their laws \pi_\ell=\pi_h are parent posteriors in this base model:

• •

  at h=(w,\mathrm{int}), redraw A_w given V_0 and the tags I_s,\ s\in C(h);

• •

  at h=(w,\mathrm{bdy}), redraw V_0 given the candidates A_u at bins of C(h), and the tags I_s,\ s\in C(h).

Only low odd positions will use a hidden scalar Z_\ell as their target label. A high position will instead use its actual named primary. Thus there are no high hidden vectors or stream pools in this construction.

An even position x of coarse key h=h_x uses a type \beta carrying h, low/high and the following observation list S (also retain j for low types):

• •

  low: all (s,t),\ s\in C(h), and (h,t^a),\ a\in F with t^a the one-sign flip;

• •

  high: just (h,t) when j=J+1, and an empty list otherwise.

Write u_\beta=j+1 for low, 1 for high. All adjacent low odd keys are covered (the high-to-low transition can only be at the paired fringe with sign unchanged).

For every potential center ID we will generate one tuple per type \beta, independent across ID/type pairs given history through Z, consisting of one new tag i and k=\lceil\kappa J\log n\rceil labels on X. The tag has a restricted posterior law T_\beta defined below. Given this tag, draw iid from \mu_i conditioned individually to hit:

• •

  P_h and all Z_S for low;

• •

  P_h,P_h^* and all Z_S for high.

These requirements include the actual primaries needed by adjacent high odd roles. At a low-to-high transition the coarse key is unchanged. Step 2 will prove that the common-hit mass is at least c_1/2, so the sampler is defined on its success gates.

The raw generation order is

Given V_0, the bin variables in the second stage are independent; given the base, so are the hidden scalars; given both, so are the tuples at distinct ID/type pairs. Generate tuples also for IDs whose centers are not present, independently of center positions, activations and ties. On undefined branches use fixed local fallbacks respecting the bin, sign and ID symmetries. Whenever a defining sampling formula is valid, use it without checking numerical tests elsewhere. Later avoidance changes the stage law, but does not redefine any raw posterior formula.

A tuple observation is the entire primitive pair consisting of the new center tag and its k label entries. Deleting a tuple will remove that whole observation. When the pair is varied in the even reconstruction, all choices and observations derived from it are recomputed. The old base tag I_h remains in the history: the fresh tag sampled from T_\beta does not replace it. Likewise equal realized values of two primary or hidden variables do not identify their roles in a conditioning formula.

Parameters can be chosen as follows. Take the small fixed \kappa>0 so small that \kappa(1+\log(4/c_1))<.001. Use very small successive constants d_2,\delta_2,d_1,\delta_1,d_0,D_*>0, each sufficiently small in terms of previous ones and the absolute coarse dimension (in particular d_2\ll\kappa). Choose 2D_*<d_0, so the fixed multiplier in the base-tag bound is absorbed and that bound is n^{d_0}\Lambda for large n. If C is an absolute constant with |S|\le C u_\beta, require C d_1+\delta_2+d_0<d_2, with slack; also take d_0,\delta_1\ll d_1. Finally \alpha>0 is sufficiently small in terms of all these constants and p_0. The target fan is T=\lceil m^{.001}\rceil. Constants hidden in pattern counts below are absolute for the fixed coarse dimension; in particular choosing D_* does not require K,\gamma,p_0. We detail the needed predictive tests.

Step 1: deleting one base tag from a hidden-key posterior. For \ell=(h,t), let \pi_{\ell,-s} be the defining parent posterior for \pi_\ell with the observation I_s omitted and all its other listed observations retained. We require

To estimate a deletion failure, fix the retained observations of this parent posterior. Given any supported candidate parent value, the incoming tag has likelihood at most n^{d_0}\Lambda(i), by conditional independence of the base tags and their uniform domination. Its predictive density relative to \Lambda is smaller than n^{-\delta_1} with probability at most n^{-\delta_1}. Outside that event Bayes’ formula bounds the posterior multiplier by n^{d_0+\delta_1}\le n^{d_1}, simultaneously at every parent label.

For the absolute cap, use all observations in the parent posterior. In the boundary case reference the bounded list of candidate labels to uniform laws; reference all incoming tags to \Lambda. The parent and conditional candidate priors have normalized caps O(1), and only boundedly many tag factors occur. The same predictive-denominator calculation, with d_0,\delta_1\ll d_1, proves the absolute test. Each Step 1 failure has probability O(n^{-\delta_1}) in its raw parent experiment.

Step 2: reconstructing the tag of a center tuple. For a type \beta at h, fix the base except I_h. Let T_0 be the original conditional law used to generate that base tag from its two parents. We first replace I_h by a hypothetical value i to define a posterior law on tags. Given the resulting Z_S, a center later samples a fresh tag from this law. The posterior formula itself does not consult the actual value of I_h again. Restrict alternative tags i to G_\beta requiring the step-1 pointwise ratio comparisons for deletion of I_h at the keys in S, computed with its value i (laws compared on all labels, so G_\beta does not read realized Z’s). Write

Notation m_{S-\ell} drops one factor with the same gate. Use their normalized integrands (against T_0) as T_\beta,T_{\beta,-\ell}. Enforce positivity where needed and m_S,\ m_S/m_{S-\ell}\ge n^{-\delta_2 u_\beta}. Conditional on the base with I_h omitted, the reference law of Z_S is \prod_{\ell\in S}\pi_{\ell,-h}. The true-event data subdensity relative to this reference is m_S. Both m_S and m_{S-\ell} integrate to at most one, so for a=n^{-\delta_2u_\beta},

These are bounds on the joint event with true I_h\in G_\beta. Reference atoms of mass zero may be omitted on that gate. Division of the normalized integrands now gives

Indeed the absolute ratio to \Lambda is at most n^{d_0+d_1|S|+\delta_2u_\beta}, and the ratio to the deleted posterior is at most n^{d_1+\delta_2u_\beta}. The stated order of constants places both below n^{d_2u_\beta}. The same bounds hold at alternative observations satisfying the gates. Also every tag in T_\beta’s support sees P_h with degree \ge1-\epsilon, P_h^* with degree \ge c_1, and each Z_S with degree \ge1-\epsilon if its primary matches, or \ge c_1 if not (degree here into \mu_i). Indeed positive likelihood for Z_{(h',t')} entails a positive case in the base model of P_{h'} having that value with I_h=i, since h\in C(h'). In that case the base tag at h was drawn to see that value with degree \ge1-\epsilon if its primary is the same named variable P_h=P_{h'}, or degree at least c_1 in the crossing case P_{h'}=P_h^*. For a low tuple, the only required column that can have degree merely c_1 is the single Z-key with nonmatching primary. For a high tuple it is P_h^*; its optional Z-key has matching primary. Every other required column has defect at most \epsilon. Consequently their common neighborhood has \mu_i-mass at least c_1-O(m\epsilon)\ge c_1/2. This proves that the tuple sampler is defined on all the stated gates.

6.2 Odd observation configurations and deletions

A state retains the residual bits and the fine count fields and total j of the preceding lemma, with counts at distances R_f,R_f+1 merged on each side of mid-weight. On the coarse chunks it retains only the bin vector, encoded by one-hot fields, and the interior/boundary flag. The ambient encoded cube still has dimension (1+o(1))n. Unlike the earlier state, this one need not determine parity, because it omits exact coarse counts.

Let q_{\rm st} be this quotient map, and set \mathcal S_A=q_{\rm st}(A), \mathcal S_B=q_{\rm st}(B). Use \mathcal S_A as the height sites. For an odd state b\in\mathcal S_B, define its even neighborhood by actual-edge existence:

This definition remains valid when \mathcal S_A\cap\mathcal S_B\ne\varnothing. The random choice at each even image is shared by all its actual even representatives, and every actual odd role reads the entire neighborhood of its odd image. A coarse flip changes at most one bin field and the flag; a fine flip changes one count field and possibly the field for j; a residual flip changes one bit. Thus the encoded distance of each edge is bounded, and two even neighbors of one odd image are within D_0=10. There are constantly many coarse possibilities and boundedly many possibilities per fine chunk, giving degree O(n). The sets \mathcal S_A,\mathcal S_B retain their even and odd roles even when they contain the same encoded point. All neighbors across a low/high transition form one state at the paired fine-count fringe. All nonmatching-primary neighbors also form one state, differing only in the coarse flag. These two facts limit the exceptional tuples below.

An observation descriptor records the distinct ID/type pairs used by the neighboring even states, together with the coarse and fine keys defining their laws. Repeated use of one ID/type pair observes the same tuple once; it does not create another tuple or another hidden scalar. The number of distinct observations is bounded as follows.

• •

  At low center severity j, adjacent types observed with at most T distinct IDs altogether give O(T+j+1) tuples; as before generic variants are constantly many (same t,F, coarse choices and severity variants), while exceptional adjacent states changing F or t number O(j+1).

• •

  At high, high observations have constant generic variants; exceptional sign-changing optional variants only matter at j\le J+2, with O(J) exceptional states. There is at most one adjacent low tuple and at most one nonmatching-primary tuple.

Let \mathcal D_b be the set of descriptors at a fixed odd state when the allowed IDs form a polynomial-size set. To specify one, list its at most T IDs, choose a subset of that list for each of the constantly many generic types, and give one ID for each exceptional neighboring state. Therefore

For unions over histories, use abstract descriptors obtained by renaming these IDs in [T] and translating the central sign. Their remaining fine data specify the O(j+1) coordinates at low states where a flip can change F, the sign, or the near-fringe status, with constantly many possible statuses per coordinate. At high states the same description uses O(J) coordinates near the interface; away from it the types have no fine-key data. Consequently their log count per coarse bin and central sign is

Multiplicities of generic neighboring states do not change the observed tuple list or its law. The Step 2 type patterns alone have count \exp(O(u_\beta\log m)) per low severity and constant count at high.

Step 3: deleting a complete tagged tuple. For an odd state b fix such an observation configuration for its neighboring even states, and observe the full tuples of the indicated (ID,type) pairs. We form a posterior L_b of a target single label. We require for good configurations

for each tuple c here in the same low/high mode and matching primary, where Q_{-c} is a reference posterior not using any entries or tag of that tuple. Absolute caps will be N\max L_b\le e^{m^{.15}/2} at low, and N\max L_b\le n^{.05 J} at high. Here and below n is sufficiently large.

Low targets: a hidden scalar. Fix the base and all hidden scalars other than \xi=Z_\ell, where \ell=(h_b,t). Its prior is \pi_\ell. The observed data are the complete tagged tuples in the descriptor. For a candidate \xi, let \Theta_b(\xi) require the positive support cases and the following Step 2 tests for each observed type, evaluated with this candidate: every defining denominator is positive, m_S\ge n^{-\delta_2u_\beta}, and m_S/m_{S-\ell^{\prime}}\ge n^{-\delta_2u_\beta} for every \ell^{\prime}\in S. Include the Step 1 cap on the target prior. These conditions use the preceding base and hidden data and the type list, not any tuple tag or entry. The support and likelihood bounds proved in Steps 1–2 then hold on this gate over the whole support of each tuple law.

For a tuple of type \beta, use as reference its tag law T_{\beta,-\ell}, followed by its label sampler with the required hit to the named variable Z_\ell omitted. The omitted normalizer and integrand do not read Z_\ell, so this reference is independent of the candidate. Other required hits remain, even if their labels happen to equal the realized value of Z_\ell. Undefined reference cases use fixed candidate-independent fallbacks. The tuple likelihood ratio is bounded by

The first factor is the tag comparison from Step 2. In the matching case, adding the omitted hit removes at most \epsilon mass from a set of mass at least c_1/2; this gives the first label factor. The second case uses only the common-hit mass c_1/2.

Write g_e(o_e\mid\xi) for these tagged-tuple likelihood ratios and Q^{\rm data} for the product of their reference laws. Define

Normalize the respective integrands to obtain L_b and Q_{-c}. The latter omits the complete tagged tuple c. Impose the data tests

for the needed deletions. These tests are not added to the candidate gate of either posterior. Because M is the true-gated subdensity and \int M_{-c}\,dQ^{\rm data}\le1, each exception has joint mass at most e^{-.02k}, integrating the target and tuples in the raw model.

For a matching tuple in the same mode, normalization gives

Here u_\beta\le J+1 and d_2\ll\kappa. For the absolute cap, there are O(T+J) observed tuples, of which at most one has nonmatching primary. Adding all tag costs, that possible label cost, the prior cap and the denominator cost gives O(J^2\log n)=o(m^{.15}). Thus N\max L_b\le e^{m^{.15}/2}. Every supported candidate hits all observed tuple entries.

High targets: the actual primary in a local joint model. Now the target is the named primary \xi=P_{h_b}, so replacing it also changes some preceding base and hidden laws. Its prior \pi^0 is the original conditional candidate law given V_0 if it is A_w, and the original initial law if it is V_0. Only in the first case is V_0 fixed from the outset.

Define the preceding observation list H_{\rm loc} from the fixed tuple descriptor as follows. Include every hidden scalar in the union of the observed types’ S-lists. Include the parent pair for each observed type, omitting the target itself. For each included Z_{(h',t')}, include the base tags indexed by C(h') and all parents needed to generate those tags and to define its posterior, again omitting the target variable itself. Take the union, counting each primitive variable once. A deterministic bounded grid neighborhood may pad this list. There are O(1) coarse bins and O(J) hidden scalars: all high types have at most one hidden key, and only one neighboring low tuple can contribute its larger list.

Given \xi, generate this list by the original local base and hidden kernels. Unused exterior variables are marginalized. Let g_*(H_{\rm loc}\mid\xi) be its density relative to uniform laws for observed candidate labels and hidden scalars, and \Lambda for base tags. Let \Theta(\xi,H_{\rm loc}) require positive support, all Step 1 cap and deletion tests for the included hidden keys, and the full Step 2 conjunction just specified for each observed type. This is a finite conjunction determined before tuple outcomes are observed. Replacing \xi recomputes every affected base-tag law, hidden prior, type law and gate from these inputs. The hidden data are fixed when the posterior is evaluated, but are integrated when its raw exception probability is estimated.

For a tuple use reference tag law \Lambda and the label sampler omitting the hit to the named variable \xi, with other required variables held at their observed values. Every tuple imposes that hit; undefined omission samplers use candidate-independent fallbacks. Hits to different variable names remain even if their realized values coincide with \xi. Write g_e(o_e\mid\xi,H_{\rm loc}) for the conditional tagged-tuple likelihood relative to this reference. The absolute tag bound in Step 2 gives the same tuple comparisons as in the low calculation. In particular the possible low tuple has a matching primary for this hit.

The unnormalized target measure is

Let M be its mass and L_b its normalization. Omitting the factor e=c gives M_{-c} and Q_{-c}. The hidden likelihood and gate read no part of tuple c, so this deletion removes its tag and all its entries. After integrating the kept tuple factors against their conditional references, the deleted density has mass at most one: the remaining integral is a gated sublaw of H_{\rm loc}. Hence the tests M>0, M\ge e^{-.02k}, and M/M_{-c}\ge e^{-.02k} have raw true-gated exception mass at most e^{-.02k} each. This probability integrates H_{\rm loc} as well as the target and tuples. As at low targets, the denominator tests are data tests, not additional candidate gates.

For a matching high tuple u_\beta=1, so the previous deletion budget gives L_b\le e^{.16k}Q_{-c}. The absolute-width budget has four contributions:

There is only one possible low tuple, so its u_\beta=O(J) cost is included in the third line. Matching label costs total O((T+J)k\epsilon/c_1)=o(k), and at most one tuple needs the weaker label factor. The coefficient contributed by the last line to J\log n is at most \kappa(\log(2/c_1)+.02)+o(1)<.002. Choosing d_2 and the smaller constants with the stated slack makes the total less than .05J\log n, proving N\max L_b\le n^{.05J}. Its support again gives common adjacency.

6.3 Conditioning, center choices, and load estimates

We now sample histories on which the preceding local tests hold simultaneously. At each stage the new avoidance law is normalized at the fixed entering history; its success probability does not reweight any earlier draw. All posterior formulas remain those of the raw experiments. For a raw failure event E and an exposed history H, the alarm variable is a_E(H)=\Pr_{\rm raw}(E\mid H). Its expectation is the raw failure probability. Thus Markov’s inequality changes a bound p into \Pr(a_E>\sqrt p)\le\sqrt p. The events E below include their stated local true gates. After the union over deletions, each Step 3 configuration fails with raw joint mass at most e^{-.018k} for large n. After its local factor union, Step 2 failure costs at most n^{-\delta_2u_\beta/2}. We seek all Step 1 and Step 2 tests, and, at the final hidden history, a Step 3 failure probability over independent hypothetical center tuples at most e^{-c_2k} for each abstract descriptor. The deterministic posterior inequalities then follow from their gates.

Global parent. Restrict V_0 to values for which every conditional raw failure probability loses at most half its exponent. Conditional on V_0, the bin variables are iid and the hidden laws are invariant under central-sign translation. Only finitely many coarse shapes and the abstract descriptors above need be tested. Markov’s inequality and the unions over severities give costs bounded by

for Step 2 and Step 3 respectively. Both tend to zero for sufficiently small \alpha; Step 1 has only constantly many shapes. The tests that hypothetically redraw V_0 still use its original prior inside their formulas.

Coarse base. At a retained V_0, start with the product of candidate-and-two-tag variables over bins. At each bin forbid failure of Step 1, or an alarm that the future Step 2 or Step 3 probability exceeds its next threshold. Conditional future probabilities have the same sign symmetry and use only a bounded bin neighborhood. The grouped bad-event probabilities are o(1) and their dependency degree is bounded, so Lemma 3.5 supplies the desired law. The future bounds after this stage are n^{-\delta_2u_\beta/8} and e^{-.0045k}.

Hidden scalars. At a retained base, start with the product law of the Z’s. Forbid Step 2 failure and the alarm that a future Step 3 failure exceeds the next threshold, halving exponents by Markov once more. Group by bin and central sign, including all allowed severities in one group. Every group uses signs within bounded distance and nearby bins, so the dependency degree is m^{O(1)}. Even after the pattern unions these probabilities are at most n^{-c_3} for some c_3>0 fixed before \alpha. High tests away from the interface have no hidden-key input and already satisfy the coarse-stage bound. We may take c_2=.001, independently of the later choice of \alpha.

For clarity, the hidden-stage pattern union has probability at most n^{-c_3}, and each group meets at most m^C=n^{C\alpha+o(1)} other groups, for an absolute C. Choose \alpha so that C\alpha<c_3/4. Charges x=n^{-c_3/2} then satisfy

The coarse stage has bounded degree and the same inequality with charges tending to zero. These checks give both avoidance and the later cost of deleting constraints touching a fixed local set. On the admitted entering histories, the gated exceptions are exactly the failures that need to be excluded. In particular the high-target formula may redraw V_0 under its original prior, while its alarm after V_0 has been sampled is simply a function of the true local data.

Local height selection.

The tuple sampler already imposes every required hit on valid inputs. There is no optional pool search in this construction, and the even mean will be controlled by the tag-mixture estimate below. Thus no singleton removals from Lemma 5.1 are needed. Use its center and height mechanism with linear radius r=\lfloor\rho n\rfloor, \lambda=n^{10}, and small fixed \rho>0. Choose the other height parameters to give crowd at most T/2 and short-truncation error o(e^{-2m^{1/5}}). Given admitted hidden history, generate the independent tuple arrays. At each odd state and each pair of consecutive levels, take a maximal family of disjoint ID sets whose Step 3 descriptors fail. Mark their union forbidden at the adjacent even sites.

On the polynomial ball-count bounds let D_n bound the number of descriptors at that state and level pair. The preceding count gives \log D_n=O(T\log n+(J+1)\log T)<c_2k/2, after taking \alpha small. Disjoint ID sets use independent arrays, and hence

This beats the \exp(O(n)) union over states and levels. After forcing one center present with a fixed tuple, at most one member of a disjoint family contains it; the other n-1 failures give the same negligible bound. Ball counts change by at most one.

There are therefore fewer than n marked sets per star and level pair. Their total loss at an even site-level is O(n^2T), leaving at least \lambda/3 eligible centers. Activate centers and make the uniform eligible-active choice at the long height. The height lemma implies global success with probability 1-o(1); each odd state sees at most T IDs across at most two levels. A failed actual descriptor would be disjoint from the marked union, contradicting maximality.

One even state makes one shared choice. Each actual odd role uses the entire neighborhood of its odd state, not only the states represented by its own actual neighbors. This convention also defines the calculations under hypothetical replacements. A mark reads only the incident-star Step 3 tests, their base and hidden inputs, the listed center tuples and position counts. Eligibility does not consult future alarms, selection adjustments or global success. The long or short path rule then reads these eligibility sets and local activations and ties. Invalid choices produce zero rows, with fixed local fillers where a continued sampling experiment requires them.

Selected odd posteriors. From here on rows are indexed by actual odd roles b; write L_b for the posterior at their state q_{\rm st}(b). At a high role use p_b=L_b for the selected tuple descriptor. At a low role, selection itself carries information about the hidden scalar, so we use the short-height correction from Lemma 5.1. Fix the base, all hidden scalars except Z_\ell, and the prospective center positions. In the raw experiment let Z_\ell\sim\pi_\ell, regenerate every consulted tuple whose law depends on it, and compute the short-height selections with their activation and tie randomness.

For a canonical descriptor \mathfrak d, let o be its complete tagged-tuple data and Q_{\mathfrak d}^{\rm data} their product reference from Step 3. If F_\xi(o) is the gated tuple likelihood, then for the raw experiment \mathbb P_\xi with target fixed at \xi,

Here a_\xi integrates the remaining local selection event after these data are specified. Candidate-dependent unobserved tuples are regenerated under their changed laws; they are not fixed at their actual values. Mappings with the same distinct ID/type observations are combined into one descriptor, so their presentation events are disjoint. Validity requires legitimate choices, the descriptor size bound, the true candidate gate, the Step 3 data tests, and position counts at most 2\lambda in the adjacent balls at all levels. These are the validity conditions of the previous lemma with its singleton and optional-pool conditions removed.

Write M=\int F_\xi\,d\pi_\ell and M^a=\int F_\xi a_\xi\,d\pi_\ell. If M^a\ge e^{-.02k}M, use the posterior proportional to F_\xi a_\xi\,d\pi_\ell; otherwise use L_b. The adjustment table depends on the fixed inputs and presented data, not on a separate read of the actual Z_\ell. Use this same table also for descriptors presented by the long selection. Invalid outcomes give zero rows. The possible multiplier e^{.02k} leaves the bounds

All valid rows remain supported on common neighbors of the tuple entries.

In the raw proxy experiment, the expected mass assigned to a label y is at most 2\pi_\ell(y). To see the two contributions separately, the adjusted normalizer cancels against the actual presentation density, and disjointness gives

On fallback data, M^a<e^{-.02k}M, while each gated observation likelihood has integral at most one. Hence

The descriptor bound here uses the polynomial position-count gate and O(T\log n+(J+1)\log T)<.01k. This expectation uses the original prior \pi_\ell, before avoidance of hidden-scalar alarms.

Let \bar p_b^{\rm pr} and \bar p_b^{\rm long} be the rows averaged over their raw center experiments at a fixed good hidden history. The proxy computation consults hidden keys at signs within O(\sqrt m) of the role’s sign: eligibility is determined by incident stars, and the short tube contains only that many sign changes. Couple the two rules by the same positions, activations and ties. On equality of their adjacent path maxima, choices, validity and kernels agree. Use the short-truncation estimate in its intersection form, take a union over the O(n) adjacent even sites, and multiply by the common cap. This gives

The last error also includes the exponentially small eligible-size exceptions. Both long and short rows, before center averaging, use center inputs only within spatial radius r+o(n) at fixed history.

Odd loads. Three different averages enter the load estimate. We take all averages over actual odd roles, using zero outside the indicated low or high subset.

First expose the base. For a fixed label y, use the summand 1_{\{b\text{ low}\}}N\pi_{\ell(b)}(y), multiplied on raw inputs by its Step 1 validity indicator. Its cap is n^{d_1}. Boundary rows contribute at most n^{-.05+d_1}=o(1). At an interior key, before coarse avoidance and conditional on V_0, posterior cancellation bounds the mean by the candidate prior, hence by O(1) after normalization. In an n-th moment, rows with bins within a fixed grid distance have fraction O((2n^{-.04})^{d_c}). Their cap cost is negligible. For separated bins, remove the coarse constraints touching their local base variables. Lemma 3.5 costs O(1)^l for l\le n terms and then their raw means multiply. Lemma 3.6, Markov’s inequality and a union over labels give a bounded base average simultaneously for all y, with probability 1-o(1) in the admitted base law.

Next fix such a base and average the low proxy means over the avoided hidden-scalar law. Sign neighborhoods of radius O(\sqrt m) have fraction 2^{-m+o(m)}, giving repeat cost n2^{-m+o(m)}e^{m^{.15}}=o(1). For separated signs, remove the hidden-stage constraints touching each target scalar. With the other keys fixed, integrate those distinct targets under their original independent priors. The preceding proxy calculation bounds each mean by 2N\pi_{\ell(b)}(y), and no other retained function reads that target. Scattered moments give a bounded average of the proxy means, and the additive comparison gives the same for long means. High rows contribute deterministically at most n^{-.13J}n^{.05J}=o(1).

Finally fix a typical admitted hidden history and take moments over centers, activations and ties. Long computations at residual distance more than 2r+o(n) use disjoint primitive randomness. Their comparison means are the long means just bounded; the absolute row caps handle close repeats. Thus the normalized average of Np_b(y) is bounded for every y, with probability 1-o(1) on center success. In actual column sums this is

so all odd columns are at most 1/10 for large n.

The additional even history mean. For the even reconstruction we need a separate bound on the tag mixtures: with probability 1-o(1) in the admitted hidden history,

The contribution outside interior low rows with j=0 is bounded deterministically. Use T_\beta\le n^{d_2u_\beta}\Lambda, tag balance and the rarity bounds. For example the low rows with j\ge1 contribute at most O(\sum_{j\ge1}n^{-.13j+d_2(j+1)}); boundary and high rows are handled by their corresponding rarity bounds.

For an interior j=0 row define

where the indicator requires true I_h\in G_\beta, positivity, and the Step 2 tests, with value zero on undefined inputs. Then f_x\le K n^{d_2}, and \phi_x depends only on a bounded bin neighborhood. Hold the base except I_h fixed. The true-gated subdensity of Z_S is the normalizer defining T_\beta, so its cancellation gives

This uses the fact established in Step 2 that the posterior formula does not read the actual I_h a second time. Now P_h=A_w, and T_0\le O(\eta_{A_w}). Only after this cancellation average A_w under its prior dominated by \Pi. Since \mathbb E_\Pi\eta_{A_w}=\Lambda,

Apply scattered moments first to the \phi_x’s under the coarse stage. The near-bin fraction is the one in the preceding odd base estimate, and the cap here is K n^{d_2}; at separated bins remove the touching coarse constraints before using the raw expectation. This bounds their cube average. Given such a base, apply scattered moments to the f_x’s under the hidden stage. Each uses boundedly many keys at signs within bounded distance of the row’s sign. The same near-sign count applies; removing the constraints touching separated key lists lets their means integrate to the \phi_x’s. Thus the cube average of the tag mixtures is bounded, although an individual mixture need not have a constant pointwise cap.

Odd injection and even posterior reconstruction.

On entering histories with odd columns at most 1/10, apply Lemma 3.9 with d=N. The atom caps satisfy N^{-1+o(1)}\le N^{-.95}, the column bound is below .4, and n^2\le N^{.025}. We obtain an odd injection whose outputs on at most n^2 queried roles are dominated by 1+o(1) times their product law.

Fix an actual even role v and a possible center ID c, with the type required at its state. Hold the admitted history through Z and all other relevant primitive center randomness fixed. The remaining primitive variable is the complete tagged tuple z=(i,x_1,\ldots,x_k) at this ID/type, with raw law P_c. For odd-neighbor data \mathbf y define

All choices and kernel evaluations in this formula are recomputed at z. The gate E requires presence and legitimate long selection of c at v, valid kernel presentations on the entire odd-state stars of its actual neighbors, and correct eligible sizes throughout v’s height consultation domain. Thus it includes the descriptor size and position-count bounds. At a fixed hidden history these checks use center positions, tuples, activations and ties within radius r+o(n), also after a hypothetical replacement of z.

For a neighbor b with matching mode and primary, let \mathcal D_{b,c} be the possible descriptors containing this ID/type among the locally permitted IDs. The lists need not be selected validly; including all of them makes the index set independent of z. For each list use its posterior Q_{-c}, which deletes the tag and all entries of tuple c. Let q_b be the uniform average of these reference laws. On undefined cases choose fixed laws independent of z; if the prerequisite position-count gate fails, E is empty. For nonmatching neighbors use the uniform law on Y. The product Q=\prod_{b\sim v}q_b is independent of z. On E, for each matching neighbor,

The deleted law uses only other tuple observations and the preceding hidden data. In particular its type-list gate never reads the removed tag or entries. Only coarse or fine chunk flips can produce the other neighbors, so their number is o(n^{.4}). Their absolute caps cost o(kn) in total. We have proved

Retain the successful-prehistory indicator while applying the near-product inequality to the actual odd labels. After their joint law has been replaced by the product law, remove nonlocal center-success restrictions and retain E. Under this raw experiment the marginal data subdensity is m_c. Lemma 3.7 therefore bounds the joint mass of E and m_c=0 or m_c<e^{-.02kn}Q by (1+o(1))e^{-.02kn} for each fixed v,c. There are \exp(O(n)) such choices, and \exp(O(n)-.02kn)=o(1). Thus the probability of a successful entering history together with any failed requirement for an actually selected tuple is o(1).

The posterior proportional to F_z now has joint density on the k labels (marginalizing the tag) relative to uniform product at most e^{.4kn}, since the prior width per coordinate given a support tag costs \le n^\gamma+\log(2/c_1)=o(n). Its average-coordinate marginal is supported on common neighbors: on every positive-mass input the same tuple reference is selected at v and each valid neighboring output hits all its label entries by the posterior supports at that star. Let \mathcal H be the labels at which its average marginal exceeds e^{.55n}/N, so |\mathcal H|/N\le e^{-.55n}. The joint cap gives

because .8\cdot.55>.4. The heavy marginal mass is the expected fraction of tuple entries in \mathcal H, hence at most .8+o(1). Restricting the average marginal to \mathcal H^c and renormalizing therefore costs a constant factor. Use these row weights at v with the selected reference only, zero on local failures. Under auxiliary product odd sampling (with any fillers on invalid rows not used on E), their expected normalized mass at a, given good history and integrating centers as well, is bounded by

Before truncation the cancellation, as a measure in z, is

The last integral retains the selection indicator. After averaging the other raw center inputs it is bounded by the probability of selecting this fixed tuple on the stated gates. Coordinate averaging therefore gives the expected empirical mass of a in the selected tuple. With one forced present center in the ball and its tuple fixed, the probability with local size gates of its valid selection is O(1/\lambda) on level 0 by uniform eligible active choice, and \exp(-n^{\Omega(1)}) on higher levels by the height bound. Here the tuple is fixed but the other prospective-center positions remain averaged. The positive-height bound is the position-averaged supremum over legal pre-activation eligibilities from Lemma 3.8, not a bound for each fixed position configuration. Summing presence probabilities thus costs a constant. The unconditional tuple marginal given history costs at most 2/c_1 times the indicated tag mixture.

Even loads and completion.

Let w_v(a) be the final even row at label a, extended by zero on local failure. Fix an admitted history through Z for which the additional even mean is bounded. For at most n even roles separated in residual bits by more than 2r+o(n), keep the successful entering history while applying the joint odd-output comparison. Their actual odd-neighbor sets are disjoint, so this comparison replaces all queried outputs by their product law at cost 1+o(1). Then remove nonlocal center-success restrictions, retaining each local gate E. The raw center integrals now factor, and the preceding cancellation gives comparison means O(N\sum_iT_{\beta(v)}(i)\mu_i(a)) for the normalized rows Nw_v(a). Their cube average is bounded by the additional history estimate.

For close repeats choose \rho so that binary entropy in natural logs satisfies H_{\rm bin}(2\rho)<\log2-.55. The near fraction then obeys

Lemma 3.6, Markov’s inequality and the column union bound show that the probability of a retained success together with any normalized even load above a sufficiently large fixed constant is o(1). Since |A|/N\to0, a bounded normalized average gives actual even column sums at most one for large n. The total exceptional joint mass through the stagewise laws is o(1), so these events have a common successful outcome. Hall’s theorem supplies distinct even representatives adjacent to the already distinct odd labels, completing the embedding.□

Proof. Step 1: the grid and its raw anchor laws. Suppose such a family exists. A finite menu retains availability by choosing a representative for each successful discard pair. Denote its given color by G.

Partition some cube coordinates into s=\lceil n^d\rceil chunks of \lfloor n^d\rfloor special bits each, with total length m=\Theta(n^{2d}), and set aside q=\lceil n^{4d}\rceil further auxiliary bits. Bin each special chunk’s count into consecutive intervals of probability at most 2n^{-b}; this is possible since each binomial atom is O(n^{-d/2}). The vector of bin indices is a grid key g, and the auxiliary word is a second key t\in Q_q. Write E(g) for the distinct grid keys obtained by moving one bin in one coordinate, so |E(g)|\le2s. Grid distance means the number of such one-bin moves. An actual cube position reads the cell indexed by its pair (g,t); many positions can read the same cell. A fixed g occurs with fraction at most (2n^{-b})^s. Since m+q=o(n), unused residual bits remain, and t is uniform on either parity of the cube, also when g is fixed.

For each grid key independently sample a patch tag i_g. Conditional on these tags, sample independent anchors W_{g,t}\sim\mu_{i_g}, one for every cell. The distributions of the tags will be chosen below. For odd positions of key (g,t), restrict \nu_{i_g} to labels adjacent to all anchors in the two lists

Call these the cross list and the own list, respectively. They cover all incident even anchors: a special-bit flip either leaves g unchanged or moves it to E(g), an auxiliary-bit flip changes only t, and a residual-bit flip changes neither key.

We need to be able to omit any specified cross hit later. For this reason, process the cross list once with each possible element last, using a fixed order of the other elements independent of t. In every such order require each successive restriction to retain a fraction at least n^{-c}. The empty cross list is allowed. After the full cross restriction, require the own list, taken together, to retain a fraction at least 1-n^{-2}. Call the cell valid when all these requirements hold. On validity let p_{g,t} be the normalized fully restricted law; otherwise let it be zero. Thus it is a subprobability supported on hits of all incident even anchors, and

For an anchor variable w in the lists, let p_{g,t}^{(-w)} be \nu_{i_g} restricted to all listed hits except the hit of w, then normalized. If the restriction has zero mass, use a fixed fallback independent of w. Deletion is by the variable’s name, even if two anchors happen to take the same label. On validity,

The second comparison uses the order in which that cross hit is last, followed by the restriction to the own list. Each deletion law is normalized without consulting the deleted variable’s value.

Choose product profiles for the tags so that, for a constant K',

1. (i)

   \mathbb E N\mu_{i_g}\le K' pointwise for every grid key g;

2. (ii)

   for each g, the expectation of Np_{g,t}, averaged over odd sites with this grid key, is pointwise \le K'.

Both expectations refer to the raw independent tag and anchor model. To obtain these profiles, use one player per grid key in Lemma 3.3. Fix the other players’ profiles and assign nonnegative prices to the two output vectors of this player. Availability permits a patch avoiding, on each side, all labels whose price exceeds a sufficiently large constant times total price divided by N. Its first output \mu_{i_g} is supported on its first support; every possible second output p_{g,t} is a subprobability on its second support. Both price contributions therefore have the required bound. Separation gives a mixture satisfying the two coordinatewise bounds, and the simultaneous-profile part of the lemma gives profiles for all players. Its hypothesis on the output rule holds because the filter and validity rules do not use the profile probabilities.

Step 2: filter tails and tag conditioning. Consider one step in one prescribed cross order, conditional on the starting tag and the preceding cross anchors, all of whose tests have passed. The current filtered law \tau has width at most \log L<n^{1/4}. The next anchor comes from a distinct grid key, so its raw marginal law \alpha is independent of this history and satisfies N\alpha\le K' pointwise. Put

If \alpha(H_\tau)\ge K'n^{-D_0}, the normalized restriction \sigma=\alpha|_{H_\tau} satisfies N\max\sigma\le n^{D_0}, but d_G(\sigma,\tau)<n^{-c}, contrary to (7.1). Thus each cross step fails with probability O(n^{-D_0}). There are at most O(s^2) order–step pairs, giving total cross-failure probability

For the own test, condition on all tags and the cross anchors, with the cross tests passed. Each label in the support of the resulting law has degree at least 1-e^{-n^p} into \mu_{i_g}. The own anchors are still independent draws from \mu_{i_g}. The expected mass removed by their q+1 constraints is at most (q+1)e^{-n^p}, so Markov’s inequality bounds own-test failure by n^2(q+1)e^{-n^p}.

We first impose a condition on the tags alone. Let B_g be the event that, conditional on all tags, the cross-failure probability for cell (g,t), including all orders and steps, exceeds n^{-D_0/2}. This probability is independent of t by auxiliary-key symmetry. The event B_g reads just the tags at g and E(g), and

The overlap graph of these tag events has degree O(s^2). Lemma 3.5 therefore gives a tag law avoiding all B_g, with charges n^{-D_0/4}, since O(s^2)n^{-D_0/4}=o(1).

This tag law also has bounded average anchor loads with probability 1-o(1). Here is the moment calculation. For a fixed x\in X, use even roles v\in A and weights Z_v=N\mu_{i_{g(v)}}(x), of cap L_\mu=e^{n^{d/2}}. Declare roles near when their grid keys are within a fixed sufficiently large distance. Each near set has fraction f\le n^{O(1)}(2n^{-b})^s, and nfL_\mu=o(1). For l\le n separated roles, remove the tag-avoidance constraints touching their tag variables. There are O(ls) such constraints, so the comparison cost is

The remaining integral uses independent raw tags, each with mean weight at most K' by (i). Lemma 3.6, followed by Markov’s inequality and a union over x, bounds |A|^{-1}\sum_{v\in A}N\mu_{i_{g(v)}}(x) by a constant simultaneously for all x. Call such tags typical.

Step 3: predictive alarms before anchor conditioning. We next ensure that the eventual odd labels give a sufficiently large predictive denominator at every even role. Fix an even position v of key (g,t), all tags, and all anchors except z=W_{g,t}. For a vector \mathbf y=(y_u:u\sim v) of odd labels put

where \mathcal V requires validity of all the neighboring filters. Both validity and the kernels are recomputed as z varies. Let Q_v be the product of their deletion laws for the named variable W_{g,t}, with the fallbacks above when necessary. This is a probability law on \mathbf y independent of z. At most m actual neighbors impose a cross hit of z, so the deletion bounds give

Declare predictive failure when M_v=0 or M_v<e^{-.04q}Q_v.

For fixed realized anchors \mathbf W, let r_v(\mathbf W) be the probability of this failure under independent neighbor draws, multiplied by 1_{\mathcal V}; set it to zero if a neighboring filter is invalid. Invalid rows may use arbitrary local fallback probabilities in this auxiliary draw. Before any anchor conditioning, the data subdensity on \mathcal V is exactly M_v. Hence, even with the tags and all other anchors fixed,

These estimates retain \mathcal V as an indicator; they do not condition the raw law on validity.

At a given key (g,t) we must impose the inequality r_v\le e^{-.02q} for all neighbor multiplicities that can occur at an even position with that key. Each auxiliary flip contributes once. The special-bit neighbors are described by at most 2s+1 counts: one for each possible adjacent grid bin and one for the unchanged key. The number of residual-bit neighbors is fixed. Thus there are at most (n+1)^{2s+1}=\exp(O(s\log n)) distinct formulas, up to reordering the neighbor labels. A union over these formulas, rather than over cube positions, bounds the probability that a key violates an alarm by

uniformly in the tags.

Step 4: anchor conditioning and odd loads. Fix tags admitted by Step 2. Group, for each (g,t), its filter failure and all its predictive alarms into one bad event on the raw independent anchors. Give the grid-times-auxiliary graph edges for one grid-bin move or one auxiliary-bit flip. Each grouped event reads anchors within distance two of its key: the filter reads distance one, and an alarm reads the filters at neighboring keys. The event graph therefore has degree O((s+q)^4). Its failure probability is at most

Charges n^{-D_0/4} again satisfy Lemma 3.5, since 16d<D_0/4. Use the resulting anchor law at each fixed admitted tag history. Sampling in these two stages leaves the tag law unchanged; the anchor avoidance probability is not used to reweight it.

We show that the odd kernels have small column sums under this law. Fix y\in Y, and for an odd role u put

The cap is L. Take the near relation to mean that the grid keys are within a fixed distance large enough to contain the local scopes just described. Its fraction is again f\le n^{O(1)}(2n^{-b})^s, and

because b>2c.

For l\le n separated roles first integrate the anchors, keeping the tags fixed. To recover the independent raw anchor means, remove all avoidance constraints touching their anchor lists. A list has radius one and a constraint has radius two, so at most O((s+q)^3) constraints touch each list. The lists are disjoint, and the resulting integral factors as \prod_j a_{u_j}(\mathbf i). Each factor uses only tags within grid distance one of its role. Next remove the tag-avoidance constraints touching these tag lists, at most O(s^2) per role, and integrate the independent raw tags. Consequently the full two-stage law satisfies

for a constant C independent of n. The exponent is o(l), since 12d<D_0/4. Profile constraint (ii) gives |B|^{-1}\sum_{u\in B}d_u\le K'.

Lemma 3.6 now bounds the normalized average |B|^{-1}\sum_u Z_u by a constant, simultaneously for all labels, with probability 1-o(1). Here and in Step 2 the union is legitimate because N\le n2^n: a sufficiently large fixed threshold in the n-th moment bound beats all N columns. The actual column sum is

since C_n=N/2^n\to\infty. It is therefore at most the clock-lemma constant \theta_0 for large n. This property and typicality of the tags hold simultaneously with probability 1-o(1).

Step 5: injective odd labels and posterior even rows. On a prehistory with the odd column bound, apply Lemma 3.10, for example with B=3, to the actual odd-position kernels. Use predictive failure at each even position as a forbidden predicate. Each predicate reads its n odd neighbors, and each odd row belongs to n such scopes. Its product-law probability is at most e^{-.02q} by the anchor alarms. The maximum label atom is at most L/N, with \log L=o(q)=o(n). These bounds meet the lemma’s polynomial requirements. We obtain an odd injection avoiding all predictive failures, with joint upper comparison 1+o(1) on at most n^2 queried rows.

For each even role v, evaluated at its assigned neighbor data, use the probability row

It is supported on common neighbors of those odd labels. Predictive success and the bound for F_x/Q_v give Np_v^X\le e^{.04q+o(q)}, including the prior cap N\mu_{i_g}\le e^{n^{d/2}}. In auxiliary experiments set the row to zero unless \mathcal V and predictive success hold.

Step 6: posterior cancellation and Hall. Fix typical tags and a label x\in X. For the even load moments use Z_v=Np_v^X(x), cap L_{\rm even}=e^{.04q+o(q)}, and declare roles near when their auxiliary words are within Hamming distance five. Then

For l\le n separated roles their odd-neighbor sets are disjoint. Keep the successful-prehistory indicator while applying the clock lemma’s joint comparison to these at most n^2 odd labels. This replaces their injection law by independent odd draws. We may now remove nonlocal success restrictions, retaining each local gate \mathcal V in its star likelihood.

Next remove the anchor-avoidance constraints touching the l target variables W_{g(v),t(v)}. There are at most O(l(s+q)^2) such constraints, and their total comparison cost is \exp(O(l(s+q)^2n^{-D_0/4}))=e^{o(l)}, in particular O(1)^n. The calculation at any other retained role does not consult a target being integrated: its anchor inputs have auxiliary words within distance two of its own word, whereas retained words are separated by more than five.

With all other anchors fixed, integrating one target and its product neighbor data gives the marginal data subdensity M_v. Thus, with zero terms where M_v=0,

The last inequality uses the local validity gate; retaining predictive success can only decrease the integral. We can perform this cancellation successively at all separated roles. If \mathcal S denotes the successful prehistory and assignment, the resulting comparison is

The comparison means have bounded average because the tags are typical. Lemma 3.6 and the same Markov and column union therefore bound the probability of \mathcal S together with any normalized even load exceeding a sufficiently large fixed constant by o(1), uniformly over typical tags. Average this estimate over the tag law. Step 4 gives typical tags and the odd column bound with probability 1-o(1), and the clock sampler avoids all predictive failures on those prehistories. There is therefore a realization with both odd and even column bounds. The even column sums are O(2^n/N)=o(1), hence at most 1. Its rows are probability laws, so Hall’s theorem gives distinct even labels. Together with the odd injection they form a monochromatic cube, proving the lemma.□

Proof. Take \beta=\gamma=d/4 in Lemma 4.1, with its corresponding h>0. Stabilize its bias property at widths n^\gamma and its purity property at doubled width budgets. If purity were available at widths 2n^\gamma and defect \le e^{-n^h}, first retain an available color on a subsequence. Restrict its second law to columns of defect at most e^{-n^{h/2}}; Markov’s inequality loses only o(1) mass. The restricted family is still available and has both widths at most 2n^{d/4}+O(1)\le n^{d/2}. It would satisfy Lemma 7.1 with p=h/2, a contradiction. Stabilization therefore makes this purity property absent.

With purity absent, Lemma 4.1 rules out availability of absolute bias \ge n^{-h} at widths n^\gamma. Stabilization makes that property absent as well. Choosing a fixed 0<\eta_0\le\min(\gamma,h) therefore gives (7.2) for all laws on the retained sets and either color, after a subsequence and a total of o(N) discards.□

Proof. We construct probability rows for the odd vertices and posterior rows for the even vertices. The required edges will follow from their supports. To obtain injective assignments, we must also keep both sets of column sums bounded.

Step 1: the key grid and trimming. Take s=\lceil n^\tau\rceil chunks of length \lfloor n^{.2}\rfloor, using m bits altogether. Bin each chunk count into consecutive intervals of mass at most 2n^{-.04}, as in the preceding grid construction. Write g for the vector of bins and E(g) for its distinct one-bin-step neighbors, so |E(g)|\le2s. Keep the full residual word a\in Q_{n-m}. We use both an even and an odd task at every cell (g,a). The padded even neighbors of an odd task are

Call the first set ordinary neighbors and the second set cross neighbors. These lists contain every actual cube edge. For locality statements, B_{\rm grid}(g,k) denotes the radius-k ball in the grid graph, and B_Q(a,R) a residual Hamming ball.

Fix \delta=10^{-4}. We will choose a sufficiently large integer h, independent of n; the list counts below have exponents independent of h. We first trim the mixture so that the survival probability of a first-side label under one independent h-tuple is nearly constant:

To see this, let

For a fixed i, (7.2), applied to uniform laws on either exceptional set, bounds their total size by 2Ne^{-n^\eta}. Hence

Balance gives \mathbb E_\Lambda\mu_i(D)\le2K e^{-n^\eta/2}. Discard tags with \mu_i(D)>1/2, whose total mass is at most 4K e^{-n^\eta/2}, normalize the remaining tag law, and replace each \mu_i by its restriction to D^c. Continue to use the same symbols for these laws. Balance changes only by constant factors, first-side widths increase by O(1), and each own-color defect is at most 2\epsilon. The remaining tag law differs from the original one by e^{-\Omega(n^\eta)} in total variation. Thus, uniformly over retained x,

because h is fixed and \tau<\eta.

Step 2: hidden tuples, center laws, and base gates. At each grid key sample an independent hidden tuple

Let \eta_g be the posterior law of its mixture tag. For the following quantities the key g is fixed. Define two unnormalized masses under \mu_i:

Here and below a hit means adjacency in the chosen color. Tilt the tag law by the mass of cross hits, retaining tags for which adding the own tuple costs at most a \Delta-fraction:

The normalizer is Z_g. These laws are used where their denominators are positive; local fallbacks will be specified below. For a retained tag, the corresponding single-anchor law is

We next establish the bounds on hidden tuples that will be used throughout this construction. At a fixed key their combined exception probability is at most e^{-n^{c'}}, for some fixed c'>0:

We also require each of \int d_i^-\,d\eta_g(i) and \int d_i^-\,d\Lambda(i) to be within a factor 1.1 of A_g. With any one cross key omitted, the analogous requirement is within a factor 1.1 of 2^hA_g. We call these the base gates.

For the posterior bound, the event R'(\Theta_g)<N^{-h}e^{-n^{\tau/2}} has probability at most e^{-n^{\tau/2}}. Outside it,

The aggregate first laws \overline\mu_\eta=\int\mu_i\,d\eta_g(i) and \overline\mu_\Lambda=\int\mu_i\,d\Lambda(i) consequently satisfy

Their widths are therefore less than n^\eta/2 for large n, even though individual \mu_i’s may have much greater width.

Filter either aggregate successively by the independent cross tuples. Conditional on a cross tuple’s latent tag, its coordinates are independent with law \nu_i. On preceding regular hits, the aggregate width has increased by only O(hs), and remains less than n^\eta. A next hit fraction outside 1/2\pm2n^{-\eta} has probability at most 2e^{-n^\eta}: restricting the next \nu_i to a larger exceptional mass would produce, together with the current aggregate, a pair contradicting (7.2). Thus

The same calculation omitting one cross key gives 2^hA_g(1+o(1)). A union over both aggregates and all these deletions costs at most O(hs^2)e^{-n^\eta}.

It remains to control the cutoffs in S_g. Put L_g=\int(d_i^--d_i^+)\,d\eta_g(i). Given \Theta_g, every tag in the support of \eta_g has own-miss mass at most 2h\epsilon. A fixed retained x survives the independent cross tuples with probability \alpha_x^{|E(g)|}=A_g(1+o(1)). Hence

The weight removed by d_i^+<(1-\Delta)d_i^- is at most L_g/\Delta, so

The other cutoff removes at most e^{-n^{2\tau}}=o(A_g), since \log A_g^{-1}=O(hs). Together with the cross-normalizer bounds these give .8A_g\le Z_g\le1.2A_g. This calculation uses no ordering between p and \tau.

Step 3: local centers and the future anchors. In each grid slice use the height device on Q_{n-m}, independently sampling prospective positions and activations across slices. Each prospective center in slice g receives an independent tag with law S_g, conditional on the hidden tuples. Take step length D=2, radius r=\lfloor\rho n\rfloor, and \lambda=n^{10}. The choices

are suitable; the height parameters \zeta,\sigma,1-\theta can be chosen sufficiently small in terms of b_0 to meet Lemma 3.8. At good Lipschitz heights, the ordinary neighbors of an odd cell occupy at most two levels. The crowd bound at one cell of each level then limits their distinct center IDs to 2n^b, which is at most T=\lceil n^{\tau/8}\rceil for large n.

We specify eligibility below before drawing activations or actual anchors. Once a center has been selected at every even cell, write i(g,a) for its tag and draw W_{g,a}\sim U_{g,i(g,a)}, independently between cells at this stage. Cells choosing the same center share its tag, but receive independent anchor samples. This distinction permits the subsequent product likelihoods at odd cells.

8.1 Presentations at odd cells

Step 4: a fixed-presentation reference experiment. Consider an odd cell (g,a) with a prescribed list of at most T distinct own-slice IDs and one ID in each cross slice. The observations are the tags at the own-slice IDs and the pairs (i,W_{u,a}) at the cross IDs. Ordinary anchors are not observed. For now these are independent hypothetical observations: conditional on hidden tuples, their laws are S_g internally and S_u(i)U_{u,i} externally.

Replace the target tuple \Theta_g by a candidate \xi with prior R', holding all other hidden tuples fixed. Retain the base gates at g and its grid neighbors; these gates depend on the candidate but not on the hypothetical tag and anchor outcomes. Use the following candidate-independent probability references for the data:

• •

  For an internal tag, use \Lambda(i)d_i^-, normalized. Here the cross-hit mass d_i^- does not involve \xi. The density of S_g against this reference is at most \exp(hn^\beta+n^{\tau/2}+O(1)).

• •

  For a cross pair at u\in E(g), use \eta_u(i)\mu_i(x) restricted to hits of the cross tuples of u other than g, and normalize. Its normalizer is at most 1.1\cdot2^hA_u. On the base gate,

  S_u(i)U_{u,i}(x) \le\frac{\eta_u(i)\mu_i(x)} {(1-\Delta)Z_u} 1[x\text{ hits }\Theta_w,\ w\in E(u)\cup\{u\}],

  because d_i^-/d_i^+\le(1-\Delta)^{-1}. Dividing by the indicated reference therefore costs at most 2^{h+2}.

The second calculation is the reason for tilting center tags by d_i^-. At undefined reference normalizers use fixed fallbacks independent of the omitted tuple; validity will require the legitimate positive cases.

Let Q be the product of these references, and let F_\xi be the product observation density against Q, multiplied by the candidate’s base-gate indicator. Define

The true-gated data have subdensity M against Q, so the joint probability of M<\varepsilon_0, including M=0, is at most \varepsilon_0. Require M\ge\varepsilon_0 on a valid presentation. The posterior F_\xi\,dR'(\xi)/M then has log density against the uniform law on Y^h at most

Here T=n^{\tau/8+o(1)}, \beta<\tau/4, and h is fixed.

Every candidate in this posterior’s support hits all observed cross anchors, coordinate by coordinate. Each observed ordinary tag i has a positive S_g(i) factor in F_\xi. Its defining cutoff d_i^+\ge(1-\Delta)d_i^- therefore gives

The conditioning set on the left does not change as \xi varies. These two support properties will provide the required edges.

Step 5: hidden-history conditioning and local selection. We now arrange that the fixed-list denominator test remains likely after selecting centers. There are two successive conditional probabilities. For fixed hidden tuples, let q_{g,k} be the true-gated probability of M<\varepsilon_0 over the hypothetical tags and cross anchors, with k\le T distinct internal IDs. The preceding estimate and Markov’s inequality give

Only k matters here, not positions or residual words. Use a local lemma on the independent hidden tuples to impose the base gates and q_{g,k}\le\varepsilon_0^{1/2} for every k\le T. One combined event per grid key suffices. It uses hidden keys in B_{\rm grid}(g,2), has probability

for some c_H>0, and dependency degree O((1+2s)^4). Thus charges x_H=2q_H suffice for large n. All posterior formulas continue to use the raw references of Step 4, rather than references conditioned on this avoidance event.

Fix such a hidden history and generate prospective positions and tags. For a candidate ID list at an odd cell, let q_L be the denominator-failure probability over hypothetical cross anchors after fixing its tags. The hidden-history bound gives

Call precisely these lists bad. At each odd cell consider all lists using present IDs in the balls of its incident even cells, at all levels, with at most T internal IDs and one per cross key. No assignment of internal IDs to particular ordinary neighbors is needed. On prospective ball counts between \lambda/2 and 2\lambda, their number is at most

where C is independent of h. Lists with disjoint ID sets have independent tag outcomes, conditional on the hidden tuples and positions. Therefore

Choose the fixed integer h so that \delta h/4>2C. Since T=o(s), the exponent is negative of order ns\log n, which dominates the logarithm O(n+s\log n) of the number of cells.

Choose a maximal disjoint family of bad lists at each odd cell, using a fixed ordering of its local lists, and mark their IDs forbidden at the incident even sites whose corresponding balls contain them. On the event just proved, each family contains fewer than n lists. An even site has O(n+s) incident odd cells, so the total number of forbidden IDs per site-level is at most

Prospective ball counts lie in the required range simultaneously with high probability by binomial tails. At least \lambda/3 choices therefore remain eligible at every site-level. Any used list whose IDs are all eligible cannot be bad: it would be disjoint from the marked maximal family.

Only now activate centers and select them by the long height rule. Eligibility is independent of every slice’s activations. Lemma 3.8 gives good Lipschitz heights simultaneously in all slices with probability 1-o(1): its failure exponent exceeds n by a power, whereas there are only \exp(O(s\log n)) grid keys. In particular every used list passes the conditional bound q_L\le\varepsilon_0^{1/4}, and ordinary fans have at most T IDs.

We record the inputs of this selection rule. Eligibility at (t,b) examines only the bad-list families at its incident odd cells. Their lists read center positions and tags in

and hidden tuples in B_{\rm grid}(t,3). The conditional list test uses the fixed-presentation experiment, not any selected IDs or adjusted label kernels. The height rule stays within slice t and consults statuses at residual distance at most 4H. Consequently selection at (t,b) uses center positions, tags, activations and ties within

All levels are included. This is a finite sequence of consultations: a list test never asks for another selection. Define the same local rules off successful histories, using local fallbacks when a law or test is undefined and independently randomized uniform choices among eligible active IDs when usable. Such fallbacks do not inspect success elsewhere.

Step 6: selection adjustment under candidate replacement. Fix positions and all hidden tuples except \Theta_g. In a raw experiment draw \Theta_g\sim R', generate the center tags and selections needed at the incident even cells under their resulting laws, and then draw their cross anchors. There is no further conditioning. A valid presentation requires the true base gate of Step 4, legitimate local selections with at most T internal IDs, incident-ball position counts at all levels at most 2\lambda, and M\ge\varepsilon_0. Ordinary anchor values are still absent.

Group presentations by their distinct internal IDs and their one cross ID at each key; call this list L. Its observed tags and cross pairs have product reference Q_L from Step 4. Given a candidate \xi, the subevent of validly presenting L has density

Indeed the listed centers must first have the observed independent tag outcomes. Selection and validity can only reduce their probability. After selection, the cross anchors have the indicated independent laws conditional on the selected tags. Thus the unselected product density F_\xi dominates the valid-presentation subdensity.

The factor a_\xi is obtained by disintegrating this raw experiment. In particular, when \Theta_g changes, every affected center law S_u changes with it. The unobserved center tags and the local selections are integrated under those new laws, rather than held at their realized values. The cross-key reference deletes the entire dependence on \Theta_g. The different lists are disjoint outcomes of this same candidate-dependent experiment, so

Step 7: posterior truncation and mean recovery. For the realized presentation put M^a=\int F_\xi a_\xi\,dR'(\xi). Use the selected-presentation posterior F_\xi a_\xi\,dR'/M^a when M^a\ge\varepsilon_0 M; otherwise use the base posterior F_\xi\,dR'/M. In either case its log density against uniform tuples is bounded by

The second denominator costs at most one further factor \varepsilon_0^{-1}.

Let q be the average coordinate marginal of this tuple posterior and \mathcal H=\{y:Nq(y)>e^{.01s\log n}\}. Then |\mathcal H|/N\le e^{-.01s\log n}, and the joint density cap implies

It follows that q(\mathcal H)\le1/2+o(1). Delete \mathcal H and normalize; the normalization factor is bounded by a constant. Denote this law by p^0_{g,a}, setting it to zero on invalid presentations.

For later loads, the important conclusion is its raw mean bound

Here the expectation is in the experiment of Step 6, at fixed positions and non-target hidden tuples. To verify it, valid data for list L have subdensity M_L^a against Q_L. On the selected-posterior cases, cancellation gives the following inequality of measures on the candidate tuple:

On the other cases, M_L^a<\varepsilon_0M_L bounds their contribution by

The list count follows from the local position gate, and h was chosen large enough that \varepsilon_0L_n=o(1). Taking average coordinate marginals and paying the bounded truncation factor proves the claim.

The input scope of this whole computation will matter when its means are multiplied. The incident even selections are at grid and residual distance at most one from (g,a). By Step 5, their raw center inputs lie in

The only realized anchors read by p^0_{g,a} are W_{u,a}, u\in E(g). Its evaluation of a_\xi integrates unobserved tags and selection randomness inside the displayed region, at the fixed positions there. Candidate replacement changes these local laws and tests but does not enlarge their scope. Thus, after cross-anchor integration, the composite raw experiment has grid radius 4 and residual radius r+4H+3=r+o(n), and reads no realized anchors. Neither its validity gate nor a_\xi uses the later anchor-avoidance tests. We use this raw-computed posterior rule on the constrained histories as well.

Step 8: the ordinary-anchor hit test. The support of p^0_{g,a} already hits every cross anchor. Now restrict it to labels hitting the realized anchors at all padded ordinary even neighbors, and require the retained mass to be at least .98. Call the resulting normalized law p_{g,a}.

To bound this test’s failure probability, fix valid presentation data and cross anchors before conditioning the anchors. A support label of p^0_{g,a} belongs to a coordinate of a supported candidate tuple. For any observed internal tag i, Step 4 bounds its miss probability under \mu_i conditioned on cross hits by \Delta. Conditioning additionally on the true own tuple increases this by at most (1-\Delta)^{-1}. Thus its miss probability under U_{g,i} is at most \Delta/(1-\Delta). Summing over the O(n) ordinary anchors and applying Markov’s inequality gives failure probability O(n\Delta). On validity,

and this law hits every incident actual even anchor. The reference p^0_{g,a} still omits all ordinary anchor values.

8.2 Taking the assignment

Step 9: selected-anchor load bounds. Before sampling actual anchors we need, with high probability on successful hidden and selection histories,

There are two successive averages to control: over center selection at fixed hidden tuples, and over the hidden tuples themselves.

For the first, retain local validity, including the eligibility-size bounds on the height consultation domain. Given hidden tuples, force a specified center present and fix its tag. The height lemma bounds its gated selection probability, averaged over positions, by O(1/\lambda) at level zero and e^{-n^c} at a positive level. The sum over possible centers has weight

On the base gate the tag and anchor laws satisfy

Choose a fixed constant C_1 large enough for the preceding selection bound, and define, on the base gate,

Set B_g(x)=0 off that gate. The conditional mean of the gated normalized selected law is at most B_g(x), whose cap is

Under the raw hidden law, averaging \Theta_g returns the posterior tag law to its prior, \mathbb E\eta_g=\Lambda. Independently averaging the cross tuples gives \alpha_x^{|E(g)|}=O(A_g). Therefore

Apply Lemma 3.6 first to these comparison means on the hidden-history avoidance law. Declare rows near when their grid keys are within distance eight. Their fraction is at most f_{\rm grid}=n^{O(1)}(2n^{-.04})^s, and nf_{\rm grid}L_B=o(1). For separated rows the relevant hidden neighborhoods are disjoint. Removing hidden constraints touching one such neighborhood costs \exp(O((1+2s)^3x_H))=1+o(1); the remaining raw expectations are bounded by O(K). The scattered-moment estimate and a union over x show that the row average of B_g(x) is bounded simultaneously for all x, with high probability.

Fix a hidden history with these bounds and now average the selected laws over center randomness. Their cap is

by the lower cutoff on d_i^- and d_i^+\ge(1-\Delta)d_i^-. Two selections have disjoint center inputs when their residual words are more than 2r+8H+4 apart, by Step 5. Up to a constant parity factor, the fraction of nearer words is at most

Here r=.01n+O(1), H=o(n), and the binomial-sum exponent is strictly less than n\log2. Since \log L_U=o(n), we have nf_{\rm res}L_U=o(1). Conditional independence at separated words and the comparison means B_g(x) now give the asserted selected-anchor load bound by a second application of the scattered-moment lemma. Both applications keep successful histories as indicators until the raw comparisons have been made.

Step 10: anchor avoidance and predictive alarms. Fix a successful hidden and selection history with the selected-law load bound. Failures of these earlier stages may be treated as aborts; their laws will not be reweighted by later avoidance probabilities. Start with independent anchors W_{g,a}\sim U_{g,i(g,a)}. At each odd cell the denominator test fails with probability at most \varepsilon_0^{1/4}, by its selected list’s bound, and the ordinary-hit test has the O(n\Delta) bound of Step 8. We will avoid these events together with the following predictive alarms.

At an actual even position v, write U_v for its selected anchor law and let its anchor z vary, holding all other anchors fixed. For the vector \boldsymbol y of labels at its actual odd neighbors set

Here \mathcal V requires those neighboring presentations and ordinary-hit tests to be valid; it contains no predictive alarms. All these gates and kernels, including the p^0 lookups at observed cross anchors, are reevaluated when z varies. Center histories remain fixed.

Choose a product reference Q_v independent of z. At a neighbor of the same grid key use p^0, or a fixed independent fallback if necessary: z is an ordinary anchor there and hence was omitted in the definition of p^0. At all other neighbors use the uniform law. There are at most m such cross neighbors, so

Define predictive failure by M_v=0 or M_v<e^{-.04n}Q_v. The joint probability of this failure on \mathcal V, under the raw target anchor and product neighbor sampling, is at most e^{-.04n}, since the data subdensity is M_v. Markov’s inequality therefore bounds by e^{-.02n} the probability over anchors that its conditional product-sampling probability exceeds e^{-.02n}.

At a fixed cell only \exp(O(s\log n)) actual multiplicity profiles occur: the numbers of special-bit neighbors in each cross bin or the own bin determine the formula up to a permutation of the sampled coordinates. Combine their alarm failures into one event per cell. Its probability is at most \exp(O(s\log n)-.02n). In the cell graph with grid or residual one-step moves, denominator and hit events have anchor radius one and predictive events have anchor radius two. The maximum degree of this graph is O(n), so the grouped events have dependency degree O(n^4). A uniform event bound is

for some c_A>0. The conditional local lemma applies with charges x_A=2q_A, at each fixed entering history. Sample the anchors from its avoidance law.

Step 11: odd loads by successive removal of constraints. We show that the odd kernel column sums are at most \theta_0, as required by the clock lemma, with high probability on success. Let \mathcal S denote successful earlier histories and selections, and consider l\le n odd rows b_j=(g_j,a_j) with pairwise grid distance greater than eight.

First use p_{b_j}\le p^0_{b_j}/.98. One anchor variable is touched by O(n^2) of the grouped events from Step 10. Removing all events touching the at most 2s cross anchors of a row costs \exp(O(sn^2x_A))=1+o(1). The cross anchors can then be integrated independently under their selected raw laws. No ordinary anchor remains in the integrand.

Next discard global selection success while retaining each local valid-presentation indicator in p^0. Finally remove the hidden-history constraints touching the target tuples \Theta_{g_j}. At most O((1+2s)^2) hidden events touch one target, so this costs \exp(O((1+2s)^2x_H))=1+o(1) per row. The radius-four scopes of Step 7 are disjoint. Conditional on positions and the other hidden tuples, the target tuples have their independent priors and the local center experiments use disjoint primitive inputs. Each experiment regenerates its center laws and selections when its candidate tuple changes, exactly as in Step 6. The raw mean bound of Step 7 therefore gives

Both charge sums are o(1), even after multiplication by n.

For the remaining, grid-near rows, the cap is L=e^{.02s\log n} and

Lemma 3.6, followed by Markov and a union over labels, now bounds every normalized average odd load by a constant with high probability. The actual column sums are O(2^n/N)=o(1), because C_n\to\infty, and are therefore at most \theta_0. This is a joint estimate with earlier successes, rather than a claim that conditioning on those successes preserves independence.

Step 12: injection, even loads, and Hall. On a successful prehistory with the odd column bound, apply Lemma 3.10 with B=3 to the actual odd rows. The predictive-failure predicate at an even position involves its at most n odd neighbors, each odd row occurs in at most n such predicates, and their product-law failure probabilities are at most e^{-.02n}. The atom cap from Step 8 is more than sufficient for the lemma’s polynomial requirement. We obtain an odd injection avoiding all predictive failures and retaining the joint upper comparison on at most n^2 queries.

At an even position use the posterior row

Its support consists of common neighbors of the assigned odd labels. In auxiliary experiments set it to zero unless local validity and predictive success hold. Since

the likelihood comparison F_x\le e^{.03n}Q_v and predictive lower bound M_v\ge e^{-.04n}Q_v give N\max w_v\le e^{.1n} for large n.

For its load estimate fix the entire center history, including the selected-law bound of Step 9; only anchors and odd outputs are varied. Select at most n even rows whose residual words have pairwise distance greater than four. Their odd-neighbor sets are disjoint, and their anchor calculations have residual radius at most two. Transfer their neighbor outputs jointly to product odd sampling, keeping the successful-prehistory indicator for this comparison. Then discard nonlocal requirements on the anchors and odd outputs and remove the anchor constraints touching each target anchor. Each removal costs \exp(O(n^2x_A))=1+o(1), and another retained row’s calculation does not consult that target.

Fix all other anchors. After integrating the target anchor, the product neighbor data with the local validity indicator have subdensity M_v. Thus posterior cancellation gives, for each label x,

The same identity multiplies over the separated rows. Their comparison means are thus the selected laws whose average was bounded in Step 9. Residual-near rows have fraction at most n^{O(1)}2^{-(n-m)}, and

The scattered-moment estimate shows that the joint probability of prior success and any normalized even load exceeding a fixed constant is o(1). Intersecting its complement with the earlier high-probability events gives a successful history and odd injection for which all even loads are bounded. Their actual column sums are O(2^n/N)=o(1), hence at most one for large n. Hall’s theorem supplies distinct even representatives. Together with the odd injection and the common-neighbor support of every even row, this gives the monochromatic cube.□

Proof. We may replace \gamma by \max(\beta,\gamma), so assume \beta\le\gamma. Apply Lemma 4.1 at the budgets n^\beta,n^\gamma, and write h_*>0 for its bias and purity exponent. Choose \beta<\beta^+<\tau/4 and \gamma<\gamma^+<1. For large n, the doubled budgets 2n^\beta,2n^\gamma, including an O(1) trimming cost, fit within n^{\beta^+},n^{\gamma^+}. Stabilize the bias property with threshold n^{-h_*} and the purity property with defect e^{-n^{h_*}} at the doubled budgets.

If that purity is available, pass to one available color and trim the small-budget side for minimum degree with defect e^{-n^{h_*/2}}. A balanced mixture then meets Lemma 8.1 with the enlarged exponents \beta^+,\gamma^+, placing the small-budget side on its odd side. That lemma gives a cube, so the purity alternative is absent. An available bias of at least n^{-h_*} at the original budgets would now give a cube by Lemma 4.1. Stabilization excludes that alternative too. Applying this to each rational budget pair, and to the reversed orientation, gives the stated discrepancy; the exponent is allowed to depend on the pair.□

Proof.

Parameter selection. Here are parameter choices and what is then available, using the orientation in question. We arrange 0<x_s<x_d<.1,\ u=x_s/2, exponents 0<h_-<h_+<1, x_d<(1-h_+)/10, and small \sigma,\chi>0 with

Write a_*=\tfrac12 n^{-h_+},\ b_*=n^{-h_-}. At shallow budgets n^{x_s},S_s absolute bias \ge2a_* is available; at deep budgets n^{x_d},S_d all densities are 1/2\pm b_* (meaning within the indicated error). Further choices:

Sublinear case. S_s=n^{y_s}, S_d=n^{y_d}, with y_s<1-\sigma<y_d, \chi<\sigma/10; use m=\lfloor n^{y_m}\rfloor special bits with y_s<y_m<1-\sigma;

Linear case. S_s=\alpha_s n,\ S_d=\alpha_d n, with 100\alpha_s<\alpha_d<.01,\ \sigma<\chi/10; use m=\lfloor\alpha_d n/10\rfloor. Also densities against any law of width O(1) on Y, for all first laws up to width n^{x_d}, are 1/2\pm o(a_*).

The two cases use different orders of parameter selection: the inequalities specific to either case are imposed only in that case.

For the sublinear case, the thresholds we need are

Choose a small rational interval [x_1,x_2] within the first-budget range of Corollary 8.2, also small relative to the margin between H^\dagger and 1. Choose a rational y-interval near, but bounded away from, 1. We may arrange that H is bounded above by a fixed number below 1 throughout the resulting rectangle, that x_2 is less than a small constant times this margin, and that 1-y\ll x_1. The value at the deep corner is positive by the asymmetric discrepancy corollary; monotonicity gives a positive lower bound throughout the rectangle.

Fix \chi using these positive margins, including \chi<(1-y)/10 throughout the rectangle. Subdivide its ascending diagonal into sufficiently many equal intervals. The total decrease of H is bounded, so one adjacent pair has decrease less than \chi/20. Use its endpoints as the shallow and deep budgets, and place h_-,h_+ strictly below and above their respective H-values, with h_+-h_-<\chi/10. We can then choose 1-\sigma strictly between y_s,y_d, and choose y_m between y_s and 1-\sigma. These strict choices provide the required width slack.

In the linear case, first choose fixed positive margins around H_L^\dagger\in(0,1). The nonincreasing function x\mapsto\lim_{\alpha\downarrow0}H_L(x,\alpha) tends to H_L^\dagger as x\downarrow0. Choose a small x-interval on which these values stay within the fixed margins. Since H^\dagger\ge1, the interval can also be chosen so that a sublinear discrepancy bound with exponent h_{\rm broad}>h_+ holds there. In particular, tests against laws of width O(1) have error n^{-h_{\rm broad}}=o(a_*).

Fix \chi using this interval and the margins. As above, monotonicity gives x_s<x_d for which the decrease of the limiting linear exponent is less than \chi/30. Choose \alpha_d sufficiently small, and then \alpha_s<\alpha_d/100 sufficiently small, to obtain

Here \sigma may be chosen arbitrarily small after \chi, so the linear-case conditions on it are compatible.

In either case, availability at the shallow threshold permits one color to be fixed along a subsequence. Restrict each first law to labels of degree at least 1/2+a_* into its second law. Since the original surplus is at least 2a_*, the retained mass is at least a constant times a_*; this costs O(\log n) width. Lemma 3.3 now gives a balanced finite mixture of patches (\mu_i,\nu_i). Each first support has the stated minimum degree, the shallow widths have only this logarithmic extra cost, and the deep discrepancy bounds hold on all retained labels.

9.1 Core and read bound for center IDs

Write a cube word as a special word z\in Q_m and a residual word in Q_{n-m}. A center ID records a slice z, a residual location and a level. We first construct and then fix a coloring-independent map from every cube site, of either parity, to an ID in its own slice at residual distance at most r=\lfloor n^\sigma\rfloor. Randomness is used here only to prove existence of this map. The anchor variables introduced later are fresh, independent draws.

The map will have the following properties:

• •

  At an odd row, the adjacent even sites use at most T+m distinct IDs, where T=O(n^{1-\sigma+\varepsilon}) and \varepsilon>0 can be arbitrarily small.

• •

  At an even row v=(z,v'), the IDs observed in all neighboring odd stars have a common core of size at most n^\chi, including the ID of v. Every other ID occurs in at most r+3 of these stars.

The adapted height construction. Let V_j be the volume of a radius-j ball in the residual cube, and put V=V_r. Independently at every slice/location/level, put a prospective center with probability n^{10}/V, and activate it with probability n^{b_0-10}. Here b_0>0 will be small. All prospective centers in the same-slice radius-r ball are eligible. Besides the event that this ball contains no active center, use the following crowd tests:

Require these bounds at the levels within 2 of the level being tested, clipping that window at its endpoints. The mean estimates use V_{r-1}/V=O(r/n) and V_{r+1}/V=O(n/r). Choose 0<\varepsilon<\sigma within the filter-budget slack below, and then b_0<\varepsilon sufficiently small in terms of \chi. In the linear case also require b_0+\sigma<\chi/2; in the sublinear case y_m+\sigma<1 provides the corresponding slack. Thus each crowd threshold exceeds its mean by a fixed power of n.

We adapt Steps 2–4 of the proof of Lemma 3.8, using paths with step bound 2 in the full cube. The position counts in all eligibility balls are at least n^{10}/2 with high probability. The hole and crowd probabilities, including the bounded level windows, have the same base estimates as in that proof. The following overlap check permits the paths to cross slices.

A child domain of metric radius R' consults slices within O(R') special-coordinate distance and residual locations within r+O(R'). For starts separated by KR', whose level ranges overlap, either the consulted slice ranges are disjoint or the residual separation is \Omega(KR'). If the residual balls also intersect, their centers are at distance at most 2r+O(R'), so R'=O(r) for large fixed K. The shell and hypergeometric estimates from the height proof then bound their residual overlap fraction by \exp(-\Omega(KR'\log n)). Enlarging the residual balls and enumerating the consulted slices costs only \exp(O(R'\log n)). Taking K large therefore leaves pair-level overlap volume at most Ve^{-\Omega(R')}.

Use degraded thresholds at successive scales for every crowd count in the table and for the eligible-size count. Delete overlaps to obtain private child regions. Deletion preserves holes; its loss from each size or crowd count fits the corresponding threshold gap unless an overlap contains too many prospective or active centers. With q separated child domains, the binomial bound for each such exception is at most

The minimum crowd exponent is \chi/2. Denote the height proof’s scale-spacing exponent by \sigma_h, to distinguish it from the present radius exponent. Choose its a,\zeta,1-\theta,\sigma_h small enough that

The base bound, the overlap bound and independence on private regions now give the same scale induction as in Lemma 3.8. This argument uses the three displayed crowd tests; it does not require the original lemma’s full-cube radius-(r+2) crowd test. It gives good heights differing by at most one at full-cube distance at most 2. Choose a covered active center at every such height and fix the resulting map.

The core and its read multiplicity. At an odd star, the residual-flip neighbors use at most O(n^{1-\sigma+\varepsilon}) IDs by the radius-(r+1) crowd bound and the bounded level window. Its special-flip neighbors use at most m more. At v, put in the core every observed ID in the same-slice radius-r ball or in an adjacent-slice radius-(r-1) ball, at the relevant heights within 1. The two smaller crowd bounds make the core size at most n^\chi.

To verify the read bound, let \Delta(c,v') be the set of residual coordinates where a center c differs from v'. Suppose a same-slice ID outside the core is seen at the residual-flip neighbor b_i through an even neighbor v'^{\,i,j}. The case j=i returns to v' and would put the ID in the core. Otherwise

The left side is at most r, while d_H(c,v')>r. Hence i\in\Delta(c,v'), and d_H(c,v')\le r+2. Such an ID is therefore seen at no more than r+2 residual-flip neighbors. For an adjacent-slice ID outside the core, the one-flip identity gives i\in\Delta(c,v') and d_H(c,v')\le r+1. At special-flip neighbors, same-slice IDs are already in the core, an adjacent slice contributes only at its own special flip, and a distance-two slice contributes at most twice. These bounds give r+3.

Finally choose \varepsilon so that

In the sublinear case both T and m have exponent below y_d; in the linear case T=o(n) and m=\lfloor\alpha_dn/10\rfloor, while 100\alpha_s<\alpha_d. Thus this choice is possible.

Tags and masks. Assign independent tags i_z from the balanced mixture, one per special word. Their averaged first and second laws have pointwise normalized loads O(1) with high probability. In the n-th moment, a repeated word costs a fraction at most n2^{-m}, multiplied by its normalized atom cap. This product tends to zero: m\gg S_s in the sublinear case, and m\log2> S_s with linear slack in the linear case. The first-law cap is smaller still.

In the linear case we also choose the tags so that, for every z, except on \mu_{i_z}-mass \exp(-\Omega(n^u)),

Here z^j is obtained by flipping bit j. To justify this choice, first use the raw product law of the tags and draw w\sim\mu_{i_z}. The broad-test bound gives degree 1/2\pm o(a_*) into the tag-average second law outside \exp(-\Omega(n^u)) first-law mass. Indeed, conditioning on a larger exceptional set would stay inside the first deep budget. Deep discrepancy also gives individual degrees 1/2\pm2b_* except with the same exponential scale of joint (w,i_{z^j})-probability. By Markov, outside an exponentially small set of w’s, the conditional probability of such an irregular neighboring tag is exponentially small.

Clip every summand to [-2b_*,2b_*]. Conditional on w, these clipped summands depend on independent adjacent tags. Their downward deviation of order na_* has probability \exp(-\Omega(na_*^2/b_*^2)). Adding the clipping exceptions proves a joint tail \exp(-\Omega(n^u)). If E_z(w) denotes failure of the displayed sum, choose a small fixed c>0 and put

Markov gives \Pr(B_z)=\exp(-\Omega(n^u)). The event B_z reads only the tag at z and its neighbors, so the dependency degree is polynomial. Lemma 3.5 allows all B_z’s to be avoided with exponentially small charges. The preceding tag-load moment still applies: removing constraints touching at most n separated tag neighborhoods has charge sum \operatorname{poly}(n)e^{-c' n^u}=o(1). Fix tags satisfying these conditions and the load bounds.

Each ID c in slice z now carries an independent anchor W_c\sim\mu_{i_z}. At an odd row b, let \nu=\nu_{i_{z(b)}}. Choose a mask of \nu-mass at least \tfrac12e^{-n^u}, normalize its restriction, and require hits of the anchors at every distinct neighboring ID. On a nonempty filter let p_b be the normalized result; otherwise use the initial masked law as an auxiliary fallback.

Choose the mask distribution separately at each row by convex separation, before drawing the anchors. For any nonnegative price, the labels costing at most 1+e^{-n^u} times its \nu-mean have mass at least \tfrac12e^{-n^u}, and hence form an allowed mask. Every output from that mask has the same price bound, including the fallback. Separation therefore supplies a distribution of masks for which

The expectation here averages all anchors used at b and its mask, before any further conditioning. Masks are drawn independently across rows. Since R_b and \nu are probability laws, their total-variation distance is exponentially small. This is an unconditional mean identity; it is not asserted after a core has been fixed.

9.2 Gains after conditioning the core

All probabilities in this subsection use independent anchors and masks, with the tags and ID map fixed. For an even role v, write W_*=W_{c(v)}. At each b\sim v, let q_b be the fraction retained by imposing the hit of W_* after all other hits in that filter. We will prove, with failure probability \exp(-\Omega(n^u)) per even star, that all these filters have width less than S_d and

where c_4>0 is a small absolute constant.

The required regularity tests. Fix an ordering of all ID names. For each b\sim v, order its IDs outside the core first, then its core IDs other than c(v), and finally c(v), keeping the fixed order inside the first two blocks. We use this order with the masked starting law and with the unmasked starting law. We also use the order of the core IDs other than c(v), starting from the unmasked law. Include all prefixes of these three orders. The masked prefixes give the outer filter, the deletion filter and the target-last fraction; the unmasked core prefixes are the laws used in the covariance telescoping argument below. There are O(n(T+m)) such prefix tests per star. The degree and signed-density tests below are applied at these same prefixes, so their number is polynomial as well. No assertion over all permutations or all subsets of IDs is needed.

At a fixed prefix whose preceding hits each retain at least .49, the current second-law width is at most

with room for the further O(n^u) restrictions below. If the next hit fraction differs from 1/2 by more than 2b_* on anchor mass at least e^{-O(n^u)}, condition its first law on one signed exceptional set. Its width is at most

and its density against the current second law contradicts deep discrepancy. Thus each next hit fraction is 1/2\pm2b_*, except with probability \exp(-\Omega(n^u)). Conditional application at each prefix and a union over the stated family prove all required sequential tests. We enlarge the constant implicit in T if necessary.

We will also use the reverse form of this reasoning: for any first law within the deep budget, an exceptional set of second labels of mass at least e^{-n^u} on which its degree differs by more than 2b_* could be normalized and used as a second test law. The available width room excludes this. In particular, each actual q_b=1/2\pm2b_* except with the stated tail. The remaining issue is a positive sum of their surpluses.

For the fixed even role v, let C_v be the core specified above, common to all its neighboring stars. If I_b is the ID set observed at b\sim v, put

Condition on the entire anchor vector W_{C_v}=(W_c)_{c\in C_v}, keeping the tags and the deterministic ID map fixed. At a given b, write D=D_b, O=O_b, and k=|D|\le n^\chi; the target ID c(v) belongs to D. Let J_-,J_D be the sets of second labels hitting D except the target, or all of D, respectively. Let P_O be the masked law filtered just by outer hits, with a width-preserving fallback (initial masked law) if their retained mass is below .49^{|O|}. Write Q=\mathbb E P_O, averaging the outer anchors and this row’s independent mask; thus Q is independent of W_{C_v}. Core coordinates outside I_b do not enter this filter. Clip q_b to [1/2-2b_*,1/2+2b_*], with a fixed local handling of invalidity there (using only this filter’s inputs), calling it \widehat q_b.

Conditional Markov applied to the outer-then-core tests shows that, outside a set of core histories of mass \exp(-\Omega(n^u)), their conditional failure probability is also \exp(-\Omega(n^u)). On these histories, outside that conditional exception,

Consequently

The fraction is a weighted mean of \widehat q_b. Its weight differs from the constant 2^{1-k} by relative O(kb_*), while \widehat q_b has oscillation O(b_*). Removing this weight therefore costs O(kb_*^2), rather than O(kb_*). Since k\le n^\chi=o(n^u), the exceptional error remains exponentially small. We obtain

Here d_G(w;\lambda) is the degree of one label into a probability law, and every restriction bar denotes normalization.

Erasing the core from the mean filter. The law Q averages only the outer anchors and the mask. To compare it with \nu, temporarily average the core as well, returning to the unconditional law R_b above. Independence of distinct core anchors gives the exact identity

On regular histories the full filter is P_O|_{J_D}, and its normalizing multiplier is 2^k(1+O(kb_*)). Averaging this bounded multiplier pointwise yields a function \theta with |\theta|\le Ckb_* such that

To see the error estimate, extend the good-history multiplier divided by 2^k by 1 on bad histories. Replacing the actual kernel there costs at most their probability times 1+2^k, which preserves the exponential scale.

The fallback in P_O gives it, and therefore Q, width at most S_s+O(n^u)+\log(1/.49)|O|. The reverse degree tests just proved apply to Q. Outside a Q-set of mass \exp(-\Omega(n^u)), every doubled degree factor 2d_G(\mu_{i_{z(c)}},y) is 1+O(b_*), so a_D=1+O(kb_*). On the exceptional set use a_D\le2^k. Since kb_*=o(1), we can invert the resulting multiplier and use the exponentially small distance between R_b and \nu. This gives

All measures and multipliers in this identity are independent of the core data.

Now fix the core except for W_*. The unmasked regularity tests give \nu(J_-)\ge.49^k outside an exponentially small exception. Restricting the last identity to J_- magnifies its total-mass error by at most O(.49^{-k}), still negligible. Put \lambda=\nu|_{J_-}. The normalized multiplier changes \lambda by a signed density

Thus \tau=(1+s/(Ckb_*))\lambda is a probability law whose width exceeds that of \lambda by at most \log2. The target anchor W_* is independent of these two laws. The individual-degree test gives d_G(W_*;\tau)-d_G(W_*;\lambda)=O(b_*), except with the stated exponential tail. Rescaling back to the actual modulation gives

Therefore replacing Q|_{J_-} by \nu|_{J_-} in the conditional mean costs O(kb_*^2).

The effect of each core hit. It remains to compare d_G(W_*;\nu|_{J_-}) with d_G(W_*;\nu). At a prefix of the unmasked core order, let \lambda be the current law, let w be the next anchor, and write x=W_*. These two anchors are independent of \lambda and each other. With g_w(y)=1[w\sim_Gy], the degree change on imposing the next hit is

The denominator is at least .49 on regularity. We claim that the covariance has magnitude at most a_*n^{-2\chi}, except with probability \exp(-\Omega(n^u)).

Suppose instead that its bad-pair probability is at least e^{-n^u}. Choose one sign and an x-set X_0 of mass at least \rho=e^{-O(n^u)} such that, for every x\in X_0, the w-set B_x with that signed violation has mass at least \rho. Draw t=\lceil n^{8\chi}\rceil independent w_j’s from the anchor law conditioned on B_x. This conditioned law still fits the first deep budget. Its mean adjacency indicator is 1/2\pm2b_* outside a \lambda-set of exponentially small mass, by the reverse degree test. Hence, for

independence gives

since tb_*^2=o(1). For an absolute K, the tuple event \mathcal G=\{\|S\|_{L^1(\lambda)}\le K\sqrt t\} thus has conditional probability at least a fixed c>0.

The event \mathcal G depends on the tuple and the fixed law \lambda, not on x. Returning to the raw independent tuple law gives

Here \mu denotes the target anchor law. Fubini therefore supplies one fixed norm-good tuple whose simultaneous signed-violation set of x’s has mass at least c\rho^{t+1}=e^{-O(tn^u)}. Restricting \mu to that set costs O(n^{u+8\chi}) width, which fits the first deep budget because u+8\chi<x_s.

For this fixed tuple, \mathbb E_\lambda S=0, so the laws

have equal normalizers. Here S_\pm=\max(\pm S,0). Their multipliers are O(\sqrt t), costing only O(\log n) second width. Deep discrepancy, with the target law restricted to the simultaneous violation set, bounds the average over that law of \mathbb E_\lambda(g_xS) in magnitude by O(b_*\sqrt t). The simultaneous violations force it to exceed ta_*n^{-2\chi} in the chosen sign. This is impossible, since

This proves the covariance tail.

There are at most k\le n^\chi core hits. Their total degree shift is O(ka_*n^{-2\chi})=o(a_*). Also kb_*^2=o(a_*). Combining this with the erasure comparison, and taking the union over b\sim v, gives outside exponentially rare core data

Concentration with the core fixed. The comparisons above hold for the fixed tags. Every ordinary neighbor uses the same slice as v, so its conditional mean surplus is at least a_*+o(a_*). Their sum is at least (1-o(1))(n-m)a_*. In the linear case the additional tag condition bounds the sum over special neighbors below by -.06na_*. In the sublinear case the bound mb_*=o(na_*) gives the required estimate without that condition.

After fixing W_{C_v}, the remaining inputs are independent outside-core anchors and independent row masks. Each clipped fraction reads one row mask, and each remaining anchor is read at most r+3 times. Exponential Markov and the product-space Hölder inequality [11] therefore bound a downward deviation of .1na_* by

Here the product-space inequality bounds the expectation of a product of nonnegative functions by the product of their d-norms when each independent input is read at most d times. We apply it with d=r+3 in this raw conditional experiment, before avoidance is imposed. The parameter choices give

Thus the tail has the required strength. On individual regularity, the clipped fractions equal the actual q_b’s. Finally

The quadratic loss is O(nb_*^2)=o(na_*), so the positive surplus proves (9.1).

9.3 Taking the assignment

Anchor avoidance and the predictive tests. At every even star require the neighboring filter tests just enumerated and the log-gain bound (9.1). For a target v, fix all anchors except W_* and all masks. For candidate W_*=x, define the data sublikelihood

where \mathcal V is this star’s filter-validity and log-gain event, recomputed with x. Let P^- be the product of the deletion kernels, each obtained by normalizing the same filter without the target ID. A zero deletion denominator uses a fixed fallback independent of x. On \mathcal V, (9.1) gives

Put M_v=\int F_x\,d\mu_{i_z}(x), where z=z(v). Define predictive failure by M_v=0 or M_v<e^{-c_4na_*/4}P^-. Lemma 3.7 bounds its true-gated probability in the raw anchor-and-product-data experiment by e^{-c_4na_*/4}. Markov then shows that the anchor event

has probability at most e^{-c_4na_*/8}.

Each star event reads IDs within residual distance r+O(1) and bounded special-coordinate distance. Its dependency degree, and the number of events touching any one local list, are at most \operatorname{poly}(n)e^{O(r\log n)}. Since \sigma<u, charges e^{-c n^u}, with small fixed c>0, meet Lemma 3.5 for the star and predictive events. Moreover,

so removing the touching constraints for any polynomial number of queried local lists costs 1+o(1).

Odd column loads and injection. Fix a second label y and use normalized weights Np_b(y) in Lemma 3.6. A row has cap e^{S_d} on success. Declare rows near when their special words are at bounded distance and their residual words at distance O(r), with constants large enough to contain the declared input lists. The near fraction is at most 2^{-n}\exp(O(r\log n)), and

For separated rows remove the avoidance constraints touching their independent local anchor and mask inputs. Their raw means are R_b\le(1+e^{-n^u})\nu_{i_{z(b)}}, whose normalized average is bounded by the fixed tag balance. The charge sum just estimated supplies the separated-product comparison. Scattered moments therefore give column sums O(2^n/N)=o(1), simultaneously, with high probability.

At such a prehistory apply Lemma 3.10 to the odd rows, with the predictive failures as predicates. Each predicate reads at most n rows and each row occurs in at most n predicates; the atoms and failure probabilities are smaller than any required inverse power. This gives an odd injection avoiding every predictive failure and satisfying the required joint product comparisons.

Even posterior rows and Hall. At v, use the posterior F_x\,d\mu_{i_z}(x)/M_v as a row on its common neighbors. Set this row to zero off its local gate or predictive success when estimating moments. The likelihood and denominator bounds, together with n^{x_s}=o(na_*), give normalized cap

The same near relation has repeat cost \exp(O(r\log n)-c_4na_*/2)=o(1), since r\log n=o(na_*).

For separated even rows, retain the successful entering-history indicator while using the clock comparison on their disjoint odd neighbor sets. Only after replacing those outputs by their product laws do we remove nonlocal success indicators. Keep every true local star gate. Remove the anchor-avoidance constraints touching the target IDs, hold the other anchors and masks fixed, and integrate a target and its data. The cancellation is

with zero terms where M_v=0. The fixed-map locality ensures that no other retained calculation consults this target ID. These integrations consequently multiply. The avoidance cost is 1+o(1), and the normalized comparison means have bounded average by tag balance. Scattered moments now give even column sums O(2^n/N)=o(1), hence at most 1, with high probability on success. All even rows have mass 1 there and are supported on common neighbors of the odd injection. Hall’s theorem finishes the cube and excludes both stated intermediate situations.□

Proof.

The finite patch menu. In proving this we can limit patch tags i to a finite menu still available with fixed discard fraction (retain, for each allowed discard set, a witness off it). Use X,Y for first and second sides. Take

We split off m bits, writing z for their exact word. Tags i_z will be independently sampled from product profiles to be fixed later.

10.1 Projections and lists

Write d=n-m as a sum of distinct powers of two and split the residual coordinates into chunks of those sizes H'. Index the bits in one chunk by the elementary binary group of order H'. For a word s, its syndrome is u(s)=\sum_l l\,s_l. Define its projection to be s\oplus e_{u(s)}. The projected syndrome is u(s)+u(s)=0. Conversely, a zero-syndrome word has exactly the H' preimages obtained by flipping one of its bits. This uses the binary syndrome correction rule of Hamming’s parity-check construction [21, Sections 3–4]. The index 0 is also a bit position, so exactly one bit is always flipped.

Use the product projection \psi on residual words of both parities. It toggles parity by the number of chunks modulo two. In a fixed slice z, call the actual odd roles with the same projected state a group. The projected even states are the sites where centers will be selected. Across a residual edge only one projected chunk changes, in at most three coordinates; a special-coordinate flip leaves the projected residual word fixed. Thus the even projected sites incident to one odd group have pairwise residual distance at most 6 in its own slice, and there is one incident site in each adjacent slice.

A changed chunk admits at most O(H'^3) neighboring projected states. Hence each even projected site belongs to at most O(\sum H'^3)=O(n^3) group neighborhoods. The size of a projection fiber is \prod H'\le n^{O(\log n)}, since there are O(\log n) chunks. In particular the group sizes have this bound.

At a single actual even role v, partition its ordinary neighbors by odd group. Different chunks of the flip give different groups (the changed projected chunk has opposite parity to that at v). Within one chunk the neighbor projections are s\oplus e_l\oplus e_{u(s)+l}. If the syndrome u(s)\ne0, multiplicities are 2; if zero, the single multiplicity is H'. Thus these ordinary incidences have multiplicities j\ge2, with at most one singleton (possible unit chunk). Special incidences are all singleton groups.

Use Lemma 3.8 independently in each slice, with step bound 6 among even projected sites and parameters

For the height lemma’s parameters \zeta,\sigma,1-\theta,a, unrelated to the cluster parameters here, take 8\delta,\sigma_g,\delta,20\delta, with 0<\sigma_g\ll\delta. The sublinear-radius condition is satisfied, and the height horizon H obeys r+H=O(n^{1-7\delta}). An ID c consists of a slice, a residual location and a level. Independently pre-generate W_c\sim\mu_{i_z}^{\otimes k} at every possible ID in slice z, including IDs that will be absent from the position field.

At each odd group in slice z, choose a mask of the cluster prior. The finite menu of permitted masks is defined as follows. Choose a subset of second labels, retain clusters assigning it mass at least 1/2, provided their total prior probability is at least 1/2, and condition each retained cluster on that subset. Normalize the mixture weights as well. The resulting aggregate is at most 4\nu_{i_z}; codegrees on the retained supports are unchanged, and cluster atoms increase by at most a factor 2. The trivial mask is permitted. The distribution over masks will be specified below. It depends only on the tags at z and its adjacent slices; conditional on tags, masks are independent across groups and independent of the positions and tuple arrays.

The randomization order is now fixed. After the tags, generate prospective positions and the independent tuple arrays, then the group masks. The eligibility rule below uses these data but no activations. Afterwards generate independent activations and site-level selection ties. Only after the centers have been selected do we draw clusters and then labels. Uniform ties are pre-randomized separately at every site-level.

On successful heights, own-slice IDs in a group neighborhood number at most T. Indeed the incident projected sites have heights differing by at most one, and a crowd ball about one representative at each occupied height contains all choices at that height. There is one further ID per special neighboring slice. Every group therefore sees at most T+m distinct IDs.

Tests for hypothetical lists. Consider at a group a hypothetical list \mathcal D of distinct involved IDs, at most T of its own slice and exactly one from each adjacent slice. Write F for the set of labels hitting (in G) all tuple entries there; use F_{-c} on deleting one of the tuples. For the masked cluster mixture put

Test the following bounds:

We claim that, conditional on positions, masks and tags, a fixed list fails these tests with probability at most \exp(-c_5a^2k), for an absolute c_5>0. Only its independent tuple entries remain random. Fix one order of its tuples, and for each tuple also use the order obtained by putting it last. Thus at most |\mathcal D|+1 orders suffice for the absolute bound and all deletion bounds.

After a set J of second labels has survived the preceding hits, exposing the next first label x multiplies A(J) by

The aggregate law of D|_J under this tilt is

Jensen’s inequality gives q(x)\ge d_G(x;\overline D_J)^2. As long as preceding ratios are at least .24, the width of \overline D_J is at most

The initial discrepancy bound (7.2) therefore implies q(x)\ge1/4-O(n^{-\eta_0}), except with probability at most e^{-n^{\eta_0}/2}. Indeed, conditioning an incoming first law on a larger exceptional set would still fit that discrepancy bound and contradict the corresponding degree estimate.

For an own-slice entry, the codegree hypothesis additionally gives, at every such prefix,

Clip the logarithmic increment below at \log(.24). Its typical lower bound is -\log4-O(n^{-\eta_0}). Its expected surplus is at least .7a for large n: use the last mean bound and \log v-\log u\ge v-u for 0<u\le v\le1, with the rare exceptional values charged separately. Thus the conditional mean increment for an own tuple is at least -\log4+.7a.

Expose the k independent entries of the tuple placed last. The clipped log increments are bounded, so their deviation below ( -\log4+.4a)k has probability \exp(-\Omega(a^2k)). Stop this calculation if a preceding regularity bound fails and continue with fixed good increments after the stop; the stopped-prefix failures are bounded by the discrepancy exceptions already estimated. For an external last tuple the typical lower bound gives the weaker threshold -2k; processing a whole list gives the absolute threshold -2k|\mathcal D|. A union over the stated orders proves the fixed-list claim.

Eligibility and local validity. For each group, enumerate the hypothetical lists of the prescribed form using present IDs in its incident even-site balls, at any levels. A failed list is one that violates (10.1). Choose a maximal pairwise disjoint family of failed lists and mark every ID in that family as forbidden at each incident even site where it could be selected. The enumeration and maximal-family rule can be fixed deterministically. Every failed list meets the marked family by maximality; thus a list consisting entirely of eligible IDs passes the tests.

With probability 1-o(1), all radius-r position counts at all site-levels are within relative error .002 of \lambda. On these position bounds, the number of lists per group is at most L_n=\exp(O((m+T)\log n)). After fixing masks and tags, failures on disjoint lists use disjoint tuple entries and are independent. If p_n=e^{-c_5a^2k}, the chance of n disjoint failures at one group is at most

This bound also permits the union over all groups. A site lies in O(n^3) group neighborhoods. Fewer than n failed lists, each of size at most T+m, at every such group remove at most O(n^4(T+m))=o(\lambda) IDs from its ball. Hence at least .99\lambda choices remain at every site-level, with high probability.

Now activate prospective centers independently and apply the height rule. Its largest-scale estimate gives simultaneous success in all slices on these eligibility sizes. Eligibility may depend on other slices; the height bound is uniform over all fixed eligible sets of the required sizes. The actual lists then consist of eligible IDs and pass (10.1).

Let \mathcal V_g be the following local event for a group g: its incident position counts obey the stated bounds at every level; all eligibility sets consulted by the needed height rules have size at least .99\lambda; the long-truncated rules select legitimate active IDs at levels less than H, at sites and heights that are not bad; the own-slice fan is at most T; and its realized list passes (10.1). We have proved that all \mathcal V_g’s hold simultaneously with probability 1-o(1). On a local failure the later kernels use zero subprobabilities or the specified local fallback.

We record an input domain for these events and their later recomputations. Relative to the projected state of g, its queried even sites are within residual distance 3 and special-coordinate distance 1. A height calculation remains in its queried slice and consults sites within residual distance 12H. Eligibility at one of those sites reads only the failed-list tests at incident groups, whose projected states are at distance at most 3 and whose slices differ by at most one special coordinate. Such a test reads tuples and positions in the radius-r balls of that group’s incident sites, and its mask. A mask uses tags one additional special step away. Thus a group calculation reads only tags, tuple and position fields, masks, activations and ties within special-coordinate distance 3 and residual distance r+12H+9.

An even star combines groups at projected distance at most 3 and special-coordinate distance at most 1 from it. For all group and star calculations below, including every candidate-tuple replacement, we may therefore use the common domain

All levels are included. The final term covers passage between actual and projected words. Replacing a tuple only reevaluates the same list, marking, height and kernel functions on this fixed primitive domain; it does not initiate a recursive search through other eligibility rules. In particular heights remain slice-local. This domain will justify the independence of sufficiently separated calculations.

10.2 Squared tilt, masks and presentations

On validity, sample at each group independently (given all preceding data) a masked cluster D tilted by D(F)^2, further restricted to

Let h_F be the probability retained by these restrictions under the squared tilt. For any ratio threshold t_c,

Substitution from (10.1) bounds this by e^{-.24ak} for an own tuple and e^{-.4k} for an external tuple. The absolute-mass restriction fails with probability at most e^{-k|\mathcal D|}. Their union is o(1), so h_F\ge1/2.

Conditional on the chosen cluster, every odd role in the group has row law D|_F. The reference labels are independent given the clusters. For a prescribed list \mathcal D, let p_{\mathcal D} be the marginal law obtained by averaging this row over the restricted cluster draw, and set it to zero when (10.1) fails. The restriction costs at most 2; cancelling one factor D(F) in the squared tilt and using its aggregate bound gives

Call all data through the actual center selections the pre-cluster history. It includes tags, positions, tuple arrays, masks, activations and ties. For an odd role b, write p_b^W for the cluster-averaged row at its realized list, multiplied by 1_{\mathcal V_g} for its group. The superscript does not condition only on W; it denotes this full pre-cluster history. The same cap holds for p_b^W.

We also define a reference sampling law at every pre-cluster history, without requiring global success. Draw clusters independently at the locally valid groups by the stated rule, then draw role labels independently conditional on those clusters. Invalid groups use independent local defaults. Later sublikelihoods retain \mathcal V_g for every group they query.

We now specify masks and bound tag-conditional means. For fixed neighboring tags and a deterministic configuration (the \mathcal D inputs with iid respective tuples), the mean of p_{\mathcal D} depends only on the number t\le T of own IDs in addition to the tag/mask laws. Choose a distribution of masks so these hypothetical means, for all t, are each bounded by O(T+1)\nu_{i_z} pointwise. Indeed for nonnegative prices c_t(y) put S=\sum_{t,y}c_t(y)\nu_{i_z}(y) and discard labels with \sum_t c_t(y)>10S. One can mask as specified to retain only cheap labels (they have \nu_{i_z}-mass at least .9, also when S=0, so at most .2 of the prior on clusters has cheap mass below half); summed cost is \le 10(T+1)S. Separation in the finite menu proves feasibility. Fix such strategies as lookups, independent of the choices of tag profiles.

From a prescribed list to the actual selection. Let \widehat p_b=\mathbb E[p_b^W\mid(i_z)_z], averaging the pre-cluster randomness at fixed tags. We claim N\max\widehat p_b\le e^{.1m}. Condition first on the own-slice positions of the group of b. On its position gate there are at most n^{O(T)} possible own lists: enumerate all subsets of at most T names in its incident balls. This enumeration depends only on positions. In each adjacent slice enumerate one external ID, requiring it to be present.

Fix the tuple and mask arrays. For an external queried slice z', a specified present ID c at level \ell, and its position field P_{z'}, let w_{\ell,c}(P_{z'}) be the supremum, over fixed legal eligibility sets, of the conditional activation-and-tie probability that this ID is selected on the queried slice’s size and height gates. In this upper bound discard all other components of the group event \mathcal V_g. This supremum removes dependence on the particular tuple and mask values used to form eligibility. At level 0 uniform eligible-active selection gives the pointwise bound w_{0,c}\le1/(.99\lambda). At a higher level selection requires positive height, so the forced-center estimate in Lemma 3.8 gives

for some fixed c_0>0.

Conditional on all positions, the activation and tie fields for the external queries are independent because they lie in distinct slices. Their bounds w_{\ell,c} depend only on the respective position fields. Those fields are independent, also with one center forced present in each slice. Hence the expectations of the bounds multiply, although the original eligibility rule uses cross-slice data. Summing named choices in one external slice, with their presence probabilities, gives

We have ignored any requirement to present the enumerated own list, which only enlarges the probability.

The resulting weights are independent of tuple and mask values. For each deterministic list, we may now average p_{\mathcal D} using its hypothetical mean bound. Summing the own lists and external vectors gives

Its normalized logarithm is

This proves the claim and explains why eligibility had to be fixed before activation.

10.3 Internal weights and load transfer

Fix an actual even role v in slice z and a specified present candidate ID c in its center ball. Hold fixed the tags, positions, masks, activations and choice randomizers, and all tuples other than W_c. The candidate tuple w=W_c has prior \mu_{i_z}^{\otimes k}.

Define L_w to be the sublikelihood of the ordered odd-neighbor labels: require the position-count gate at v, the selection of c there, and every neighboring group event \mathcal V_g, all recomputed with w. On this gate use the reference law that draws one newly tilted cluster in each group and then independent queried labels within that cluster. Thus L_w integrates the clusters; it does not fix any realized cluster or impose later injectivity constraints. We claim that

for a reference probability Q independent of w.

To prove this comparison, first prescribe the ID list at one neighboring group. Delete c from that list and keep the other tuples and the mask fixed. Reference its j queried labels by the masked cluster prior tilted by D(F_{-c})^2, without the extra restrictions, followed by independent samples from D|_{F_{-c}}.

Before integrating the cluster, the likelihood ratio on actual support is

The three factors come from the retained tilt mass, the two tilt normalizers, and the j conditional label densities. For an ordinary group with j\ge2, the deletion bound in (10.1) and the lower ratio gate give

For a singleton use D(F)/D(F_{-c})\le1, giving at most 2e^{2k}. There are at most m+1 singleton groups.

The realized lists may change with w. At each group average the deletion references uniformly over all possible name lists containing c. This probability law is independent of w, and dominates any one such reference at a cost at most \exp(O((m+T)\log n)) on the position gate. Nonexistent or undefined references use fixed independent fallbacks. Taking the product over groups yields a reference Q for which

The last inequality uses m=o(an) and (m+T)\log n=o(ak), proving (10.2).

On the true local gates with c actually selected, test

at the observed star data \boldsymbol y. Under reference odd sampling the unconditional probability of such a true-gated failure is \le e^{-.01 a k n} per candidate test with the conditioning just described, by predictive mass. On passing, use the resulting posterior proportional to L_w\,d\mu_{i_z}^{\otimes k}. It is supported on tuples of common neighbors, and has normalized joint atom cap (relative to uniform k-fold sampling on original X)

using n^\delta=o(an). Let \overline p be the average coordinate marginal of this posterior and put

Then |B|/N\le e^{-(\log2-.02a)n}. If q=\lceil(1-.01a)k\rceil, the joint tuple cap and a union over coordinate subsets give

Indeed the coefficient gained in the exponent is at least .02-.01\log2+.0002a>0, while k\log2=o(akn). Thus the expected light-coordinate fraction is at least .01a(1-o(1)). For an absolute c_6>0, the light part of \overline p has mass at least c_6a.

Normalize this light part to obtain the even row p_v^X. In estimates set it to zero off the true local gates or predictive success. It is supported on common neighbors, and

since normalizing costs 1/(c_6a) and \log(1/a)=o(an).

Conditional means and tag balance. Let \widehat p_v^X be the mean of this row over the raw local randomizations and reference neighbor draws, with tags fixed. Its normalized cap is at most e^{.1m}. For a specified candidate c, the subdensity L_w includes exactly the event that c is selected and the neighboring groups are locally valid. Its data marginal is Z. Consequently, as measures in the candidate tuple,

with zero terms at Z=0. The last integral is a gate probability. Coordinate averaging and light-part normalization cost at most 1/(c_6a). On the position gate there are only polynomially many possible candidates at v. Summing their bounds and using N\max\mu_i\le e^{n^\delta} proves the claimed cap.

Both \widehat p_v^X and \widehat p_b depend only on the tags in the declared bounded special-coordinate neighborhood. Each row is supported on labels in its own patch.

Choose independent tag profiles, one per slice, so that the expected odd and even mean rows, averaged over their respective roles within that slice, are bounded coordinatewise by O(1)/N. For fixed profiles elsewhere, price separation makes these bounds feasible for one slice: availability supplies a tag whose two supports avoid expensive labels, regardless of the remaining draws. The mask lookups and all other rules conditional on realized tags have already been fixed, independently of profile probabilities. The response sets are therefore nonempty, convex and have closed graph on the finite profile simplices. Lemma 3.3 gives simultaneous profiles.

Under these product profiles, apply Lemma 3.6 to the normalized tag-conditional means. Their cap is e^{.1m}. Two roles are near for this calculation when their special words lie within a sufficiently large fixed distance, so the near fraction is at most n^{O(1)}2^{-m}. At separated words their mean functions use disjoint tags. The product comparison is thus independence, and n\,n^{O(1)}2^{-m}e^{.1m}=o(1). With high probability their averaged normalized means are bounded simultaneously for all labels. Fix such typical tags.

Next expose the pre-cluster history at these tags. Declare actual parity roles residual-near when their projected words are within 2R_{\rm loc}, enlarging the fixed constant if necessary. The primitive domains for separated roles are disjoint. Since R_{\rm loc}=O(n^{1-7\delta}), its ball volume is \exp(o(an)); the m special bits and the O(\log n) projection changes also cost only this amount. Thus the near fraction is

For a fixed second label, the normalized row Np_b^W(y) has cap 8e^{2k(T+m)+n^\delta}, which is e^{o(n)}. Its mean is N\widehat p_b(y). At separated roles the raw local experiments are independent given tags, even when events elsewhere fail, because all rules were extended locally. Scattered moments and the bounded average of these comparison means give odd column sums o(1) with high probability. Intersect this event with the already proved simultaneous pre-cluster validity.

On these good prehistories, draw the independent group clusters. The conditional individual laws D|_F then have column sums \le\theta_0 with high probability, where \theta_0 is as in the clock lemma. Indeed their sums have the preceding small expectations; the maximum contribution from a group is

even including its entire group size. This is \exp(-\Omega(n^\zeta)) by 500\delta<\zeta. Bounded-summand exponential concentration for independent groups beats the union over columns: if L_* is the displayed summand bound, a column sum with conditional mean \bar s=o(1) exceeds \theta_0 with probability at most \exp(((e-1)\bar s-\theta_0)/L_*), by exponential Markov (use e^x\le1+(e-1)x on [0,1]). On this success use a clock-lemma injection of all odd labels with joint upper domination through n^2 queries (no additional predicates needed).

Transfer to even rows. At a successful cluster history the clock law compares each queried star, and any collection of at most n separated stars, to independent odd-row sampling conditional on those realized clusters. Retain the prehistory and cluster-column success indicators while applying this comparison; it queries at most n^2 odd rows. Once the comparison is made, remove the nonlocal cluster-column indicator and integrate the independent group clusters. This gives exactly the product-by-groups reference law used to define L_w, with the local gates still present.

For one star, this order of integration permits the true-gated predictive bound above to be used. Summing it over all 2^{n-1} even roles and their polynomially many possible candidates gives o(1), because its exponent is .01akn\gg n. Thus predictive failures occur with total probability o(1) on the entering successes.

For the even column estimate, use normalized weights Np_v^X(x) with these success indicators. Their cap is e^{(\log2-.01a)n}, and

At retained separated rows, first make the same clock comparison and integrate clusters in the same order. Then remove nonlocal prehistory restrictions. The true local gates remain in each likelihood, and the declared primitive domains are disjoint. Integrating those local fields therefore gives the product of the fixed-tag comparison means N\widehat p_v^X(x). Their average is bounded by the chosen tags. Lemma 3.6 yields even column sums O(2^n/N)=o(1), hence at most 1, with high probability on the successes.

On their joint success every even row has mass 1 and consists of common neighbors of the odd injection. Hall’s theorem supplies distinct even representatives, completing the cube and the proposition.□

Proof. We may stabilize (for countably many fixed choices of these parameters) and hence assume no such cluster witnesses at all on the retained sets, either orientation or color, since availability gives the just-proved contradiction. More precisely we take in particular all fixed rational choices meeting the parameter conditions, and for each such choice we have eventual absence. Further o(N) discards do not affect previous availability conclusions.□

Proof.

The slice experiment. Suppose both orientations have H^\dagger\ge1, but one has H_L^\dagger=0; denote that orientation by X,Y. We will use a biased patch inside a small cube slice to leave large first-side common-neighbor sets. Independent labels from the other slices will then pay for the remaining cube edges. The compatibility argument below ensures that those outer labels do not consume almost all of an internal set.

Fix cluster-exclusion parameters \zeta=1/100 and rational \delta as in Proposition 10.1, and put s_c=\lceil e^{n^\zeta}\rceil, \upsilon=\delta/4. In the reversed orientation, H^\dagger\ge1 permits a rational x_0>0 with H_{\rm rev}(x_0,1-\upsilon/4)>.95. Indeed the near-1 second-budget limit exceeds .95 for a sufficiently small first argument, and monotonicity gives the same lower bound at 1-\upsilon/4. Stabilized absence at exponent .95, followed by reversing the sides, gives

on X,Y, in either color.

Set g=n^{-.01}. Since H_L^\dagger=0, monotonicity and nonnegativity give H_L(.01,.01)=0. Choose an available exponent h_0<.01. Its surplus n^{-h_0} is much larger than g. After fixing a color along a subsequence, the columns of degree at least 1/2+2g have second-law mass at least c n^{-h_0}. Conditioning on them costs only h_0\log n+O(1) width. Lemma 3.2 therefore supplies an available finite menu of tags i, all of one color G, such that

All supports lie in the retained sets.

One slice and its odd rows. Split the cube into inner slices Q_h, where h=\lfloor n^{.1}\rfloor, indexed by outer words s\in Q_{n-h}. Put k=\lceil n^{.2}\rceil, and first consider one slice with fixed tag i. Define the hit-conditioned first law

Provisionally draw Y_0\sim\nu_i. Given Y_0, draw the tuples W_v\sim\rho_{Y_0}^{\otimes k} independently at its even roles. At an odd role b, the observed data are the tuples at its h internal even neighbors. Their likelihood density, relative to independent \mu_i-entries, is

Let Z_b=\int L_b\,d\nu_i, and let Z_{b,-v} be the corresponding predictive density with one neighboring tuple omitted. Require positivity and

On passing, set p_b^W=\nu_iL_b/Z_b; otherwise set p_b^W=\nu_i.

Lemma 3.7 applies first to all kh entries, using reference \mu_i^{\otimes kh}. For a deletion test, fix the other entries and use their posterior on Y_0 as the prior; the next tuple has reference \mu_i^{\otimes k}, and predictive density Z_b/Z_{b,-v}. Hence

The row laws always have width at most .02n. On a passing row,

and the fallback has the smaller width .011n.

For each fixed y_0, the conditional test-failure probability is the same at every odd role by translation symmetry of the slice. Averaging over Y_0 therefore selects one deterministic y_0 for this tag for which the per-row bound holds. Fix it from now on and sample independent W_v\sim\rho_{y_0}^{\otimes k}. The likelihood rule L_b is unchanged. This selection gives the same bound for each row, not simultaneous success of all rows at this stage. Conditional on W, the slice reference law draws the odd labels independently from the rows p_b^W.

The first-side common-neighbor set. At an even v, let \sigma_v be uniform on the labels of \operatorname{supp}\mu_i hitting all its actual internal odd neighbors, if this set has size at least N\exp(- (\log2-.5g)h); otherwise let \sigma_v=0. We claim that \sigma_v has mass 1 except with probability \exp(-\Omega(gk)) in the slice reference law.

Fix every tuple except W_v, and vary w=W_v under prior \rho_{y_0}^{\otimes k}. For a vector t of internal odd outputs, let F_w(t) be the product of their row masses, multiplied by the indicator that all their tuple tests pass. Recompute both rows and tests at (W_{-v},w). Let Q(t) be the product of the deletion-posterior rows, with fixed w-independent fallbacks if a deletion denominator is zero. Each neighboring row costs at most (1/2+2g)^{-k}e^{.2gk}, so on the gate

Put m(t)=\int F_w(t)\,d\rho_{y_0}^{\otimes k}(w). The true-gated event m=0 or m<e^{-.5gkh}Q has probability at most e^{-.5gkh}. Outside it, the posterior on w has atom cap

where n^{.01}=o(gh).

If the common-neighbor set has size T_0, this posterior is supported on at most T_0^k tuples. Its total mass 1 forces

which exceeds the cutoff defining \sigma_v. Adding the h possible neighboring row-test failures proves the claim.

11.1 Compatibility

Define the tag’s two mean rows by

Here N_{\rm in}(v) is the set of internal odd neighbors of v. Their outputs in the second expectation are independent with rows p_b^W. Thus \pi_i is a probability law, whereas \alpha_i can be a subprobability. Translation symmetry makes these means independent of the chosen role of the indicated parity, also when the outer word reverses the slice’s internal parity. They are supported on the two sides of the tag, and \pi_i has width at most .02n.

The next two auxiliary lemmas use the slice experiment, patch menu, and parameter choices fixed in this proof.

11.2 Outer moment

11.3 Taking the assignment

Reference failure probability. Choose the slice tags i(s) independently from the compatible profile p, draw the independent tuples at each tag’s fixed y_0, and use independent odd-row sampling conditional on those tuples. Denote the odd outputs by Y_b. At an even v, define the unnormalized row

where v^j is obtained from v by flipping outer bit j; the row is zero off the indicated first support. Its mass is at least 1/2 except with arbitrarily strong polynomially small probability in this raw reference law. The internal failure probability for \sigma_v is already exponentially small. Given internal data with \sigma_v of mass 1, the outer neighbors lie in distinct slices. Their unconditional laws are independent copies of \pi, so Lemma 11.3 applies.

Avoidance at the tag stage. Fix a large constant P, exceeding all needed polynomial dependency exponents and the requirements of Lemma 3.10 with B=4. At each outer word s, impose two conditions on the product tag law:

• •

  the conditional raw probability that \|M_v\|_1<1/2, for a given even role in this slice, is at most n^{-2P};

• •

  for every x on the first support of its tag, at least half the outer neighboring tags satisfy d_G(x;\pi_{i(s^j)})\le.8.

The first conditional probability is identical for all even roles of the slice by inner translation. It reads the tags in the radius-one outer neighborhood. Markov applied to a stronger raw bound from the preceding paragraph makes its failure probability at most n^{-2P}. For the second condition, compatibility gives exceptional tag probability at most \eta for every such x. Independence of adjacent tags and a binomial union bound give total failure probability at most

The tag events have dependency degree O(n^2). Lemma 3.5, with charges of order n^{-2P}, therefore supplies a law avoiding both kinds of failure.

We next choose a typical outcome of this tag-avoidance law. Write d=n-h, and for a fixed host label define the normalized comparison means

The second expression is zero where its first-side row vanishes. These weights have cap at most 2^ne^{-cn} on the tag gates for a fixed c>0. For A_s use the width .02n. For B_s, use N\alpha_i\le e^{h\log2}, D_x^{-d}\le2^de^{O(n^{.05})}, and the second gate, which contributes at most .8^{d/2} in the numerator.

Apply scattered moments on the outer words, with words at bounded distance declared near. Their near fraction is n^{O(1)}2^{-d}, and the product of this fraction, n, and the cap tends to zero. At up to n separated neighborhoods remove the touching tag constraints; there are O(n^3) of them, with total charge o(1). In the restored product law,

For the second inequality, condition on i(s); each independent neighboring tag integrates its ratio to 1 on the compatible support, and then (11.2) bounds \mathbb E_iN\alpha_i. Thus, with high probability, both comparison means have bounded averages simultaneously for all labels. Fix tags having these bounds and all tag gates.

Avoidance at the tuple stage. At these fixed tags, the raw W-law is a product of the laws \rho_{y_0}^{\otimes k} at the even roles. Require at every even star that its conditional mass-failure probability under independent odd-row sampling be at most n^{-P}. The tag gate and Markov make each tuple-stage bad event have probability at most n^{-P}. It reads W-variables within full-cube distance 2, so the dependency degree is O(n^4). The conditional avoidance lemma applies again, now with charges of order n^{-P}.

For a fixed second label y, apply scattered moments to Z_b(y)=Np_b^W(y) under this tuple-avoidance law. The cap is e^{.02n}, and a sufficiently large fixed full-cube neighborhood has fraction n^{O(1)}2^{-n}. Their repeat cost is o(1). At separated rows remove the touching tuple constraints; at most O(n^5) constraints are removed for n queried neighborhoods, with charge sum o(1). Their raw means are A_{s(b)}(y), whose average is bounded by the selected tags. The resulting actual column sums are O(2^n/N)=o(1), simultaneously with high probability.

The odd injection. At a tuple history with these column bounds, apply the clock lemma, retaining this entering success indicator in subsequent comparisons. Its label count is N, with \log N=O(n); column sums are eventually below \theta_0; and row atoms are at most e^{.02n}/N<n^{-A_*}. A mass-failure predicate reads the n odd neighbors of one even role, and each odd row occurs in n such predicates. Their product-law probabilities are at most n^{-P}, as required by the chosen P. The clock law therefore gives an odd injection avoiding every mass failure and joint upper comparison with the independent odd-row law.

Even loads and normalization. The normalized weights NM_v(x) have cap

A fixed-radius full-cube near relation again has fraction n^{O(1)}2^{-n}, so its repeat cost is o(1), because gh=n^{.09+o(1)}.

For up to n separated even stars, retain the successful tuple-history indicator and apply the clock comparison to their at most n^2 distinct odd neighbors. This replaces the injection outputs by independent odd-row draws at fixed W. We may then discard the nonlocal column-load indicator for an upper bound. Each remaining local row and weight reads only the radius-two W-scope of its star. Removing the avoidance constraints touching those scopes costs 1+o(1) and restores independent raw tuple fields in the separated domains.

The resulting product means are exactly B_{s(v)}(x): the internal weight integrates to \alpha_{i(s(v))}, and each outer label contributes its degree into the corresponding \pi_{i(s^j)}. Their bounded averages give, by scattered moments, simultaneous column sums

hence at most 1/2 with high probability on the entering successes. This uses only N/2^n\to\infty, with no rate assumption. Clock avoidance has ensured that every row has mass at least 1/2. Normalizing each row thus increases column sums by at most 2. The resulting probability rows lie on common neighbors of the odd injection and have column sums at most 1, so Hall’s theorem completes the cube. This excludes the linear-budget jump.□

Proof. Proposition 9.2 leaves both H^\dagger\ge1 and excludes 0<H_L^\dagger<1. Proposition 11.1 also excludes H_L^\dagger=0; since these exponents are nonnegative, both linear limits are at least 1. Given 0<\epsilon<1, choose a rational h_0 with 1-\epsilon<h_0<1, and then positive rational budgets with H_L(x,\alpha)>h_0 in each orientation. Stabilized absence at h_0 gives discrepancy less than n^{-h_0}\le n^{-1+\epsilon}. Larger error slacks follow by weakening such a bound.□

Proof. Apply Corollary 11.4 with the chosen positive error slack, and shrink the two budget constants to work simultaneously in both orientations.□

Proof. Expand the centered power, introduce independent copies of the first label for its factors, and integrate the independent second labels one coordinate at a time. The alternating sum is exactly (12.2); the individual centered factors have zero mean, so singleton interactions vanish.□

Proof.

One free coordinate. Fix the column l and the other coordinates. The interaction is the projection of a_{l,x} onto a fixed bounded function of the second label. Equation (12.1) applies to bounded signed tests: add a fixed positive offset, normalize to a probability law, apply discrepancy, and subtract the offset term. If a one-sign exceptional set of first labels had \tau-mass at least \tfrac12e^{-\alpha n/3}, conditioning on it would have width

The signed-test estimate would then bound the alleged exceptional projection by O_u(b_*), a contradiction. This also proves the gated assertion: condition on the signed exception intersected with the degree gate, and never divide by the probability of the gate alone.

Two free coordinates. Write the interaction as \langle a_{l,x},H a_{l,z}\rangle_{\pi_l}, with H a fixed bounded function supplied by the other coordinates. Suppose its magnitude exceeds n^{-1-.03} on a set of \tau^2-mass greater than e^{-n^{.4}}. Splitting signs and then the conditional masses gives a set A of first coordinates, of mass at least e^{-O(n^{.4})}, such that for every x\in A the same signed violation holds on a set E_x of z’s with \tau(E_x)\ge e^{-O(n^{.4})}.

Let \rho_x=\tau(\cdot\mid E_x). Its width is O(n^{.4})<\alpha n. Applying (12.1) to this first law shows that \mathbb E_{\rho_x}f_z(y)=O(b_*) outside a \pi_l-set of mass e^{-\Omega(n^{x_*})}. The degree bounds change f_z to a_{l,z} by O(b_*), and boundedness on the exceptional set therefore gives \|\mathbb E_{\rho_x}a_{l,z}\|_{L^2(\pi_l)}=O(b_*). Take t=\lceil n^{.25}\rceil independent z_j\sim\rho_x. For S=H\sum_{j\le t}a_{l,z_j}, independence gives

A fixed positive fraction of these tuples consequently satisfy \|S\|_2=O_u(\sqrt t).

Return now to the original product law \tau^{\otimes t}. For each x\in A, the tuples just obtained have raw mass at least e^{-O(tn^{.4})}, and all their coordinates lie in E_x. Fubini therefore supplies one fixed norm-good tuple for which the set of x’s satisfying all the signed violations has mass at least e^{-O(tn^{.4})}. Conditioning \tau on that set costs width O(n^{.65})<\alpha n. Its mean a_{l,x} has L^2(\pi_l)-norm O(b_*) by the preceding argument. Its projection onto this fixed S is thus at most

whereas the simultaneous violations make that projection at least t n^{-1-.03}=n^{-.78+o(1)} with one sign. This contradiction proves the two-free estimate. For the raw correlation K_{\pi_l}(x,z)=\langle f_x,f_z\rangle_{\pi_l}, the same proof uses f in place of a and requires no degree gate.

Mean interaction size. Independence of the tuple coordinates yields

For fixed y, the inner expression is a bounded signed test on the first side applied to f_x(y'), with an O(b_*) error from the centering and denominators. Deep discrepancy bounds it by O(b_*) outside a \pi_l-set of y'’s of mass e^{-\Omega(n^{x_*})}. Boundedness elsewhere gives

Cauchy–Schwarz now gives \mathbb E|M_{l,J}|\le n^{-.4|J|}, since .96/2>.4.□

Proof. Every positive product term is at most \exp(2^u n w). The union over the O_u(n) interactions and Lemma 12.3 bound its integral on the two ranges above n^{-1-.03} by

In the second range the lower endpoint exceeds the one-free threshold O_u(b_*). Both bounds decay faster than any fixed inverse power of n; the second uses the stipulated smallness of \xi.

On w\le n^{-1-.03}, expand each column factor into interactions and then sum over I. A term with chosen interactions whose union is S\subseteq[u] has coefficient \sum_{I\supseteq S}(-1)^{u-|I|}. It vanishes unless S=[u]. Thus every surviving term covers all u coordinates, and its interactions come from distinct columns. Terms choosing more than L interactions have a geometric tail bounded by powers of 2^u n^{-.03}, which is smaller than the required n^{-3R}. Among at most L interactions covering [u], one has at least u/L coordinates. Its mean absolute size is at most n^{-.4u/L}; the remaining factors are bounded on this set. The column and interaction choices cost O_u(n^L), giving O_u(n^{L-.4u/L}), again smaller than n^{-3R} because u>10L^2.

Without the alternating sum, the small range has weight \exp(O_u(n^{-.03})), and the two displayed tail bounds still apply. This proves the uncentered assertion, including for subtuples.□

Proof. After the other coordinates are fixed, a large extension gives a projection of f_z onto a bounded fixed direction whose magnitude is bounded below by a positive constant depending only on \xi,u. Split the candidates by projection sign. If t vectors in one sign class have all mutual inner products at most 3\theta, their average has squared norm at most 1/t+3\theta, while its projection has that fixed positive lower bound. For sufficiently small \theta, this forces t<t_0 for a fixed t_0=t_0(\xi,u). The graph joining pairs with K_\pi>3\theta has neither an independent set of size t_0 nor a clique of size \lceil e^Q\rceil. The elementary Ramsey binomial bound gives

Increase the fixed C_*, chosen after u,\xi,\theta, to include the two signs and the finitely many interactions. The same projection argument gives the stated count for |K_\pi(x,z)|>\xi.

For a tuple with a large interaction, choose a maximal retained index set whose subtuple has every interaction at most \xi. Sum over the finitely many possible retained index sets. Once its labels are fixed, each excluded coordinate must create a large interaction when added to them; otherwise maximality fails. Its possible labels therefore lie in a set of size at most \exp(C_*Q), determined by the retained labels alone.

In a positive product term of (12.2), deleting an excluded coordinate costs at most D_\pi(x)^{-d}. Under the original product measure, each excluded coordinate consequently contributes at most

These necessary extension conditions can be integrated independently; no independence after conditioning on maximality is asserted. The remaining positive product has bounded integral by Lemma 12.4. Every tuple under consideration excludes at least one coordinate, so summing the finitely many retained sets and positive terms gives C_u\Gamma.

In particular, for the homogeneous mass Z defined in Lemma 12.2, the moderate bound and even centered-power Markov give the explicit consequence

The peeling bound on the set with an interaction above \xi covers the complement of the moderate set. In heterogeneous applications the large-interaction part will be controlled separately.□

Proof. Let x,z be independent uniform labels in the original first set. The raw two-free estimate gives \Pr(|K_\pi(x,z)|>n^{-1-.03})\le e^{-n^{.4}}. For the weighted expression, split at n^{-1+.06}. The two-free and one-free bounds respectively give

for a fixed c>0 and large n. Markov, applied to each conditional expectation over z at threshold e^{-n^{.2}}, removes at most e^{-c n^{.4}+n^{.2}} of the first labels per test. The union over \exp(o(n^{.2})) laws still removes an o(1) fraction.

For interpolation, choose simplex diameters at most n^{-3} in \ell^1. Then |K_\pi-K_{\pi'}|\le\|\pi-\pi'\|_1\le n^{-3}. The realized event with thresholds n^{-1-.02},2\xi is contained in the corner event with thresholds n^{-1-.03},4\xi. Its exponential weight is at most the old weight times e^{100n^{-2}}. The relaxation from e^{-n^{.2}} to e^{-n^{.19}} pays for this factor. A finer mesh can simultaneously preserve any other finitely many strict margins needed later.□

Proof. A nontrivial bias witness has g\le n, so its two uniform laws have widths at most n^{a_B}. The discrepancy estimate chosen with slack \iota/2 gives

which proves the first bound. For the cluster-scale bound, if not, pass to maxima with \log_n q\to\gamma'\in[\gamma,1] on a subsequence (q\le\log N when nontrivial). Remove column degree outliers into the stated first set using (7.2); this costs negligible mass even relative to the union size (exception count at most 2Ne^{-n^{\eta_0}}, testing their uniform laws). Here we can take deviation 2n^{-\eta_0}=o(1), since the first width exponent is at most \gamma' a_C+o(1). Keep the bins retaining at least half their mass, restricted to the survivors.

For distinct retained labels, their codegree in the red color is

where the means and inner product are under the first law. Here |m(y)|,|m(y')|\le4n^{-\eta_0} and K(y,y')>\theta; blue changes the signs of the two means and keeps K. Thus both codegrees exceed 1/4+\theta/8 eventually. A diagonal codegree is the degree itself, close to 1/2. All pairs therefore have codegree \ge1/4+n^{-\delta}, where one can fix rational numbers \zeta,\delta with 0<\zeta<\gamma' and \gamma'a_C<\delta<\min(\eta_0,\zeta,1)/2000. Uniform bin clusters with weights proportional to retained sizes now give a full-dimensional cluster witness with atom cap \exp(-n^\zeta) and both widths \le n^\delta, contradicting Corollary 10.2.□

Proof.

At every pass, work on the labels left after removing both supports of the earlier patches from the working sides, and recompute g,q on the current residual pair. A new pass is started only while the extracted equal sizes sum to less than .1N. Thus each residual side then has size at least

for a fixed c>0, as needed by the bounded branch.

Extracting one patch. If \max(g,q)<M_1 Q_0 during extraction, take the bounded case right away on those residual sets, still of sizes \ge cN; this uses just one equal-side-size patch, by truncating to arbitrary sets of the smaller size, with uniform laws, either orientation and color, and low direct mode below. Otherwise proceed as follows (later g,q for an extracted patch refer to the values here at its own extraction):

• •

  If g>M_1 q, use direct bias mode. Extract first and second sets X_i,Y_i of equal size M_i\ge c N e^{-g^{a_B}}, with the second law uniform and every first label having degree at least 1/2+g/(4n) into it in some fixed color of that patch. To see this, let U,V witness g and choose their denser color. The top eighth U_1 of rows by degree has size at least Ne^{-(2g)^{a_B}}, since the fixed threshold makes (2g)^{a_B}-g^{a_B}>\log8+O(1). The absent 2g budget therefore gives d_G(U_1,V)<1/2+2g/n. If fewer than an eighth of all rows had degree at least 1/2+g/(2n), the remaining seven eighths would be below that threshold, and

  d_G(U,V)<\tfrac18(1/2+2g/n)+\tfrac78(1/2+g/(2n)) =1/2+11g/(16n),

  contrary to the witness. Let U^+ be the rows meeting this degree threshold and take M_i=\min(|U^+|,|V|). Keep any M_i of the good first labels, and choose an M_i-subset of V. A uniform such choice preserves all their degrees to o(1/n) simultaneously: M_i=e^{\Omega(n)}, so sampling concentration permits a union over at most N rows. One realization gives the asserted g/(4n) surplus.

• •

  Otherwise use the cluster mode (q\ge Q_0), with orientation from its witness and, say, red color. Extract X_i,Y_i of equal size M_i\ge cN e^{-q^{a_C}}, where Y_i is partitioned into bins of the prescribed size d_i. Every within-bin pair (including diagonals) has codegree \ge1/4+3a under uniform X_i. First remove the degree outliers as in Lemma 13.2. Retain original bins losing at most half their mass, restrict them to the survivors, and partition them into bins of the stated size, discarding the final remainders. This loses only a negligible or fixed small fraction. Choose a common size that is a multiple of d_i, no larger than either the surviving first set or the whole-bin union, and maximal with these properties. It remains at least cNe^{-q^{a_C}}. Keep that many whole-bin labels on the second side and sample the same number of first labels. Since this number is e^{\Omega(n)}, concentration followed by a union over the at most N^2 within-bin pairs preserves every codegree with the displayed slack.

The chosen cluster parameters satisfy

For high-small-bin mode, \log d_i=\min(q/2,\sqrt{\log n})+O(1); the bound q\le(\log n)^2 and the choice of \omega give the second comparison also at the cutoff. Likewise h_i is smaller than any fixed positive power of d_i needed below, uniformly after increasing Q_0. The inequalities c_qM_{\rm lo}<1/20 and c_qM_{\rm hi}>5 give, respectively, h_i\le(\log n)^{.1} in low mode and h_i>(\log n)^5 in high mode eventually. After either nonbounded extraction, remove its two supports before the next pass and retain its measured g,q values with that patch.

Repeating extraction and selecting one type. Continue until the sum of the equal sizes first reaches .1N, or until the immediate bounded branch fires. In the former case, select one of the finite mode/orientation/color possibilities, distinguishing also high-small-bin and high-large-bin. Let I be its patch indices and put \sum_{i\in I}M_i=S\ge c'N. In the immediate bounded case, ignore earlier extractions and take I to contain only the bounded patch, with S=M_i and s_i=h_i=0. From now on all patches used are of this one type, orienting notation accordingly. The color is selected together with the mode and orientation, before any cube allocation; thus every edge required by the subsequent construction is tested in this single selected color.

Dyadic prefix allocation. For i\in I, put p_i=M_i/S and round it up to a dyadic weight r_i=2^{-\ell_i}. Then

Order the r_i decreasingly, and let J be the first segment whose sum reaches 1. Both 1 and all preceding terms are integer multiples of the last term in this segment. The preceding partial sum is below 1, so adding that last term reaches 1 exactly. Hence \sum_{i\in J}r_i=1. We retain only these patches for the allocation, but S continues to mean the total over I before this restriction. In particular \sum_{i\in J}M_i>S/2.

The allocation uses subcubes obtained by fixing initial coordinates, as in the cube tilings of Conlon, Fox, Lee and Sudakov [6, Section 2.2] and their adaptation by Fiz Pontiveros, Griffiths, Morris, Saxton and Skokan [13, Section 2]. Here the sizes are chosen from the patch masses, and the later embedding uses the patch laws. Use the weights r_i, i\in J, as disjoint complete prefix leaves in the first cube coordinates. Positions in leaf i belong to patch i for both parities. The leaf has exactly 2^{n-\ell_i-1}=\Theta(2^nM_i/N) roles of each parity eventually. Leading flips, called crossings, number \ell_i per star of patch i, visiting distinct other leaves: the first prefix mismatch identifies the flipped coordinate.

Internal and bulk coordinates. In the tail, beyond all leading coordinates, dedicate nested coordinate sets of sizes h_i as internal for patch i; by a slice in that patch we mean exactly fixing their complementary coordinates. Other nonleading, noninternal flips there are called bulk. Here nonleading is relative to the current leaf: a coordinate beyond its prefix may still belong to a longer leaf’s prefix. The size bounds and dyadic rounding give

Together with g\le n^{\iota/2}, and Lemma 13.2 used with a fixed \gamma<\iota/(2M_{\rm hi}), these show that the maximum of the h_i over I and the \ell_i over J is <n^\iota eventually. In particular all asserted dimension allocations fit. Except in the bounded case we can ensure

because g^{a_B}=o(g) and q^{a_C}=o(q^M) as their arguments grow; choose the fixed threshold so these inequalities hold with the displayed constants for every argument above it. In the bounded case these quantities are O(1) (actually \ell_i=0).□

Proof.

Approximating a capped law by a uniform set. The measured budgets concern uniform sets, so first fix a law \pi on the residual labels of width W=\log(N\max\pi), and a larger powered width budget B. Set

independently over labels. Then t\max\pi=e^{-(B-W)/2}<1 and \mathbb E|V|=t\gg Ne^{-B}. In the applications B,W=o(n), so t=e^{\Omega(n)}. Concentration of the cardinality and all bounded degree and pair sums, followed by a union over O(N^2) tests, gives one realization whose uniform law approximates every such test against \pi to o(1/n), and whose size is at least Ne^{-B}.

Own-patch degrees. At the residual pair used to extract a cluster patch, choose a dyadic bias budget in [q^{C_b},4q^{C_b}], larger than the measured g\le M_1q. Its powered width exceeds the input width with ample slack:

Use the uniform approximant just constructed for the second law. If the rows of X_i exceeding 8q^{C_b}/n in either bias direction numbered at least the higher budget’s size threshold, they and this approximant would form a rectangle witnessing that absent budget. Each exceptional row set is therefore smaller than its threshold, a tiny fraction of M_i. In direct mode \pi_i is already uniform and fits the absent 2g budget; the same rectangle test gives the upper degree trimming while preserving the lower bound. In bounded mode choose fixed dyadic budgets above M_1Q_0, large enough that their size thresholds are less than aM_i/10. They give a fixed degree constant K.

Own-patch clique exclusion. For cluster mode choose a dyadic Q_i\in[q^2,2q^2]; for direct mode choose one in (g/(2\sqrt{M_1}),2g/\sqrt{M_1}]. Both exceed the measured cluster maximum. Their powered widths exceed the input widths because

above the fixed threshold. Approximate \pi_i by a uniform law at this budget. Greedily remove disjoint cliques of size \lceil e^{Q_i}\rceil in X_i, with pair inner products under \pi_i greater than 2\theta. If their union had size at least Ne^{-Q_i^{a_C}}, it would, together with the approximating first law in the reverse orientation, witness the absent cluster budget Q_i: the approximation retains pair inner products greater than \theta. The removed union is thus smaller than that threshold. Its fraction is tiny, and \Delta_i=e^{C_*Q_i}\le e^{s_i} by the powers of q and the choice of M_1,Q_0. In bounded mode a sufficiently large fixed Q_i gives the same small-loss conclusion and a fixed \Delta_i.

Other-patch degrees and row tails. In cluster mode the input widths satisfy

For direct and bounded modes omit the term 10k_iT_i; their input laws are uniform. For each j\ne i, conditioning uniform X_i on a putative outlier fraction e^{-cn}, with fixed c<\alpha/2, still fits the linear width in (12.1). Thus the fraction with deviation greater than 2b_* against \pi_j is e^{-\Omega(n)}. Lemma 12.6 supplies the row-tail removal for the whole collection. Their unions have vanishing relative mass. Choose the fixed thresholds so own-degree and clique removals together cost less than, say, a/2; the other two removals together cost less than a/2 eventually. If a total fraction r<a is removed, each original within-bin codegree of at least 1/4+3a becomes at least

Finally hold this cleaned support fixed while varying the inputs. Degrees and pair inner products are Lipschitz in the \ell^1 distance of the comparison laws. A sufficiently fine mesh, of diameter at most n^{-3}, preserves the degree margins 8 to 10, 2b_* to 3b_*, the clique threshold 2\theta to 3\theta, and the relaxed row-tail bounds proved in Lemma 12.6. Cleaning is performed separately at each corner; it requires no union over mesh corners. The later union of corner supports inherits only the bounds that hold label by label.□

Proof.

14.1 Primitive data and selection geometry

Fix an h_i-slice and abbreviate h=h_i,k=k_i,T=T_i. Conditional on the common parameter point, different slices have independent copies of the following experiment. At every potential center c, indexed by an internal location and a level, draw a mesh vertex, use its cleaned law \mu_c, and draw W_c\sim\mu_c^{\otimes k}. These variables are generated even when the center is absent. Each odd group independently draws its mask vertex. Prospective positions, the orders used in searches, activations, and site-level choice ties are further independent primitive variables. Eligibility is computed before using activations or choice ties. We write W for this whole pre-bin history, including the selections derived from the primitives. Its derived fields need not be independent. Before success conditioning, the records at distinct centers and groups and the remaining randomizers are independent; each tuple is sampled conditional on its own corner.

Here is the projection defining groups and sites. Index the h internal coordinates by the binary group of order h, and for a word z set

The map has syndrome-zero image and fibers of size h, and always flips one bit. An odd group is a fiber on the odd roles of the slice; a selection site is \psi(v) for an even role. The parity convention includes the shift from the slice’s fixed complementary word. A group’s site neighborhood consists of the projected even roles adjacent to one of its odd roles. As in Section 10.1, these sites have mutual distances at most 6, and each site lies in O(h^3) such neighborhoods.

For a fixed even role,

If s(v)\ne0, the flips l and l+s(v) form pairs with the same image; if s(v)=0, all h flips have the same image. Thus each group queried by this star has multiplicity j\ge2, and the multiplicities sum to h. This is the incidence property used in the posterior calculation.

For each group and mesh vertex, form a mask from that vertex’s price vector on Y_i. Take the uniform prior on bins with uniform in-bin laws; retain bins having at least half their labels of price \le10/M_i, then restrict to those cheap labels in each bin, normalizing both stages. At most a tenth of labels overall exceed the cut, so most bins have enough cheap mass; aggregate is bounded by 4 times uniform on Y_i. A physical bin is a member of the fixed partition of Y_i. Write D for its masked uniform probability law when it occurs inside a formula such as D(F), and r_g(D) for the masked prior probability of choosing that bin at group g. Thus a bin identity determines a group-dependent masked law. All these prior lookups and draws up to the actual assignment of clusters are local. In particular different centers can have different cleaned first laws, all still giving codegrees \ge1/4+a.

We give details of the template, including its gates used later. Use the geometric height device on Q_h with step bound 6, radius \lfloor\rho h\rfloor, \lambda=h^{10}, activation and crowd exponents b_0=\omega/8,\ b=\omega/2, height-proof exponents a_g=\omega/12,\ \zeta_g=1-\theta_g=\omega/30,\ 0<\sigma_g\ll\omega (subscripts refer here to geometric parameters only). Positions and activations are independent of tuples, masks and tie randomizers. The consultation distance for paths is o(h) in this geometric estimate, in particular tiny compared to \rho h by the large threshold. Throughout, asymptotic slack in powers of h itself need only hold for q\ge Q_0, choosing that fixed threshold sufficiently large.

14.2 List tests and odd bin laws

Fix corners, the group’s mask, prospective positions, and a hypothetical set \mathcal D of 1 through T distinct candidate IDs in its neighborhood. Let F be the set hitting all entries of their tuples and let F_{-c} omit tuple c. Set A(J)=\mathbb E_{D\sim r_g}D(J)^2. The list must satisfy the absolute and deletion bounds from (10.1), with every ID treated as an own-slice ID:

To bound failure, expose tuple coordinates successively; for each deletion test choose an order in which the indicated tuple is last. If the entries already exposed impose the hit set J, the next ratio is

The next x has its center’s cleaned first law. All-pairs codegrees give conditional mean ratio at least 1/4+a, even though different centers can use different corner laws. While preceding ratios are at least .24, the second aggregate law has width at most \log(N/M_i)+O(1)+2kT<n^{\eta_0}/2. Jensen and (7.2) then bound the probability of a ratio below 1/4-O(n^{-\eta_0}) by e^{-\Omega(n^{\eta_0})}.

As in the proof of (10.1), clip log ratios below at \log(.24). Their conditional means are at least -\log4+.7a. The deletion inequality asks the last k increments to sum to at least (-\log4+.4a)k, leaving a deviation margin .3ak. Bounded-increment concentration gives failure e^{-\Omega(a^2k)}. For the absolute inequality, sum all k|\mathcal D| increments and use its still larger margin above -2k|\mathcal D|. Stop on an earlier invalid ratio, continue the clipped process with good values, and separately add the negligible probability of an unclipped catastrophe. The finite collection of orders gives the stated failure bound for one list.

In each group neighborhood search failed lists using present IDs in range of incident even sites, at any levels, and mark a maximal disjoint family’s union forbidden for choices by those incident sites. On polynomial position bounds there are at most \exp(O(T\log h)) lists per search and disjoint tests in one search are independent conditional on positions, masks and corner realizations. Here disjoint lists have disjoint ID sets. A union bound for h disjoint failures, using T\log h=o(a^2k), shows that each search has fewer than h of them except with probability \exp(-h^{1+\Omega(1)}) per slice. Such a search marks fewer than hT IDs. Since a site participates in O(h^3) searches, it loses at most O(h^4T)=o(\lambda) choices. Binomial position concentration puts the original counts close to \lambda; hence the remaining eligible count is at least \lambda/2, while the original count is at most 2\lambda, with the same slice failure bound. Now apply the activation/path mechanism with these eligibilities. Choose one ID per site at the obtained height by a uniform active eligible tie (that same choice used everywhere it is queried). The largest scale proof gives heights and non-bad-layer choices everywhere there except with probability \exp(-h^{1+\Omega(1)}) on size success. Realized lists at each group then have size \le T by the crowd bound at the (at most two) levels used, and pass (10.1): a failed realized list uses no marked ID and would enlarge the maximal disjoint family.

At each group on validity, given W, sample independently a masked D tilted by D(F)^2, conditional further on

The extra restrictions retain probability at least 1/2 by (10.1). Thus the first stage selects a physical bin by a restricted squared-mass tilt of r_g. Conditional on that bin, the internal reference law draws all queried role labels independently from its uniform law D|_F. Write q_g^W(D) for the induced bin probabilities at group g, U_g^W(D) for the resulting individual conditional uniform-subset law given bin, p_g^W=\sum_D q_g^W(D) U_g^W(D). On needed fallbacks just draw from the group’s masked prior and laws. The label-marginal cap uses cancellation of one hit-mass factor:

The masked bin prior is at most 2d_i/M_i, so its squared tilt and extra restrictions give the first cap below. The absolute mass restriction and the masked support size give the third. These bounds also hold for the prescribed fallbacks:

for used bins. In this notation g as subscript is a group, not bias budget.

Local validity and fallback rules. The local rules are defined even when some tests fail. At a site, use the height rule restricted to its long consultation domain. Choose no ID if that height reaches the horizon or its site-level is bad; otherwise choose a uniform active eligible ID, with the pre-randomized tie for that level.

A group is valid when all its incident sites make choices, every candidate ball at those sites and levels has at most 2\lambda positions, and the resulting list has size between 1 and T and passes (10.1). An invalid group uses the masked-prior fallback above.

For an even star at v, let \mathcal V_v require validity of its neighboring groups and the position upper bound 2\lambda and eligibility lower bound \lambda/2 at every site-level in its projected site’s long consultation domain. This event depends on W, before bins or labels are drawn. It ensures a genuine selection at the projected site. A positive selected level then requires a path reaching positive height, and selection uses the actual independent uniform active tie. All these events hold simultaneously on the slice success already proved.

Fallback/mark/choice tie rules can use separate independent order permutations per queried group or site-level, as needed (on ID lists or on IDs, respectively) to be translation-invariant in law under syndrome-zero shifts, including shifts interchanging the two local parity conventions. Choice ties themselves are independent of eligibility and activation data. All validity and comparison rules may and will use this symmetry. The height lemma with ambient parameter h gives 2DH+O(\rho h+1)<10\rho h after increasing the threshold. Thus the rules consult only this slice within 10\rho h of the inner queried state, including in the counterfactual calculations below (eligibility calculations themselves just use incident group tests in range, not their selections).

14.3 Even posteriors and predictive tests

Fix a present candidate ID c for v’s projected site. Hold all other primitive data fixed, including the corner selecting its prior \mu_c, and vary w=W_c. For ordered internal neighbor labels \boldsymbol y, define

The bin at each group is integrated out in this probability. Selections, validity, and all bin laws are recomputed at w.

We construct a reference independent of w. For each queried group g, let \mathcal L_g be the family of all lists of at most T present IDs in its candidate ranges that contain c. This family uses only the frozen positions. For \mathcal D\in\mathcal L_g, delete c, tilt the masked bin prior by D(F_{-c})^2, and draw its j_g queried labels independently from D|_{F_{-c}}. Denote this probability by Q_{g,\mathcal D}, using a fixed symmetric fallback if its normalization is zero. Average uniformly over the family, with a fallback also for an empty family, and set

This notation uses the fallback convention when the family is empty. In particular the actual list may depend on w, but the reference mixture does not.

For one fixed list, the likelihood ratio before integrating its bin is at most

The factor 2 pays for the extra bin restrictions; the other factors are the squared-tilt normalizer and the j_g conditional label densities. The inequality uses j_g\ge2 and the tested ratio bounds. Passing to the fixed mixture costs |\mathcal L_g|, with logarithm O(T\log h)=o(ak) on the position gate. Since \sum_g j_g=h and there are no singleton incidences,

If a required position bound fails, the sublikelihood is zero.

With c actually selected on \mathcal V_v, require

The posterior P_{c,\boldsymbol y}(dw)=L_w(\boldsymbol y)d\mu_c^{\otimes k}(w)/Z(\boldsymbol y) has density at most e^{(\log2-.05a)kh} relative to its prior. Since \max\mu_c\le2/M_i and the allocation gives \log(2N/M_i)\le .01ah, its joint atom cap relative to N^{-k} is e^{(\log2-.04a)kh}.

Let \bar P be its average coordinate marginal, and let B=\{x:N\bar P(x)>2^he^{-.02ah}\}. Then |B|/N\le2^{-h}e^{.02ah}. For any specified r=\lceil(1-.01a)k\rceil coordinates, the joint cap bounds the probability that all lie in B by

The union over at most 2^k coordinate subsets is negligible. Hence the expected fraction of coordinates outside B, namely \bar P(B^c), is at least c a for a fixed c>0. Define \sigma_v by restricting \bar P to B^c and normalizing; this costs O(1/a), which the fixed threshold absorbs in the cap below.

On failures of the gates let \sigma_v=0; otherwise it is supported in a single cleaned corner law’s support and on common neighbors of all internal labels. We have

where expectation is for unrestricted W and internal reference sampling and K a fixed constant. To prove the mean bound, first fix the data other than W_c. If \bar P_{c,\boldsymbol y} is the posterior coordinate marginal, cancellation of its denominator gives

The inner sum is the probability of selecting c and passing \mathcal V_v in this candidate experiment. Thus, after the O(1/a) restriction cost, the contribution is bounded by the actual tuple-coordinate incidence with that selection gate.

An entry equals x with prior probability at most 2/M_i; conditioning on this equality leaves positions and activations with their original laws. Given presence of c, the gated selection probability at level zero is O(1/\lambda) by the uniform active tie bound. At higher levels the position-averaged, eligibility-uniform positive-height bound is e^{-h^{\Omega(1)}}, with the one specified center forced present. These are precisely the bounds of Lemma 3.8; they do not condition on global success. The sum of candidate presence probabilities is \lambda per level. Summing over the polynomial number of levels proves \mathbb E\sigma_v(x)\le K/M_i.

Let E_v^{\rm in} denote failure (\sigma_v=0). For each candidate, Lemma 3.7 bounds failure of the displayed predictive inequality, on its selection and validity gate, by e^{-.01akh}. The position-count gate permits only polynomially many candidates. Consequently the nonnegative function of primitive data

has raw mean at most h^{O(1)}e^{-.01akh}. For \epsilon_i=e^{-.001a k_i h_i},

holds simultaneously per slice except with probability \exp(-h_i^{1+\Omega(1)}): apply Markov to B_v at threshold \epsilon_i, union over the 2^{h-1} even roles, and add the separate slice-wide validity failure. The exponent akh, with k=h^{3\omega}+O(1), pays for this union. The individual tests (14.3) are local as well. All these estimates are uniform in the corner probabilities.□

Proof. The output means are continuous in the parameters. Barycentric probabilities are continuous and piecewise affine; varying them changes the weights of the finite primitive experiments but leaves every corner lookup, recomputed validity gate and posterior rule for a fixed realization unchanged. In particular, each posterior retains its realized corner law as prior. The slice-conditioning denominators are bounded below, as are the pretrim normalizers just estimated. Equation (14.1) puts the outputs in the capped input domain: the bounded conditioning and trim factors fit the gap from 2k_iT_i to 10k_iT_i.

Apply Kakutani to the response

This response is nonempty, convex and has closed graph, so it has a fixed point. There z_i\cdot\pi_i=\max_y\pi_i(y). Every label in the output support is cheap at some mesh vertex used by the point, whose price differs coordinatewise from z_i by o(1/M_i). Hence z_i(y)\le11/M_i on that support. Integrating against \pi_i=\pi_i^{\rm out} proves (14.4).

The mesh was chosen for the stability conclusion of Lemma 13.4. Each used corner support therefore has the cleaned properties at the fixed-point laws. Degree and row-tail bounds hold label by label and pass to the envelope; the no-clique condition remains a property of each corner support separately.

In low mode, conditioning on all slice gates changes the raw history law in total variation by at most their failure probability, \exp(-h_i^{1+\Omega(1)}). For each conditioned history, the bin pretrim changes the label marginal by at most h_i^2\sqrt{\epsilon_i}. Averaging and the triangle inequality give the stated comparison with \pi_i^0. These bounds are uniform above the fixed threshold Q_0; they do not require a low-mode scale to tend to infinity.□

Proof. Encode W by its finite categorical outcomes, not by continuous random seeds. A parameter point uses at most dimension plus one active vertices, hence O(N) possibilities for each corner draw. In low mode h\le(\log n)^{.1}, so the number h^{O(1)}2^h of position, group, and level records is n^{o(1)}. Each tuple and vertex record costs at most O(k\log N)=n^{1+o(1)} in log cardinality, using N\le n2^n.

The order universes for IDs and lists have sizes U=\exp(O(T(h+\log h)))=n^{o(1)}. An order contributes at most \log(U!)\le U\log U=n^{o(1)}. Multiplying by the number of records, and including the binary presence and activation variables, gives total log cardinality n^{1+o(1)}.□

Proof.

Mass estimate. In high direct mode define the unnormalized even row

First sample the odd labels independently from their \pi_{i(b)}. We claim that \sum_xZ_v(x)<1/2 has probability at most n^{-R}.

Expose crossings first. After successful earlier filters, their normalized first law is at most 4^{\ell_i}\sigma_v, hence still has small width. Deep discrepancy (12.1), applied after conditioning the next second law on a putative exceptional set, puts its hit mass at 1/2\pm O(b_*) except with probability exponentially small in a power of n. The cleaned crossing denominators have the same bounds. Each normalized ratio filter therefore changes total mass by 1+O(b_*), and the product is 1+o(1), since \ell_i b_*=o(1).

Let \tau be the normalized first law after these filters. Its remaining bulk draws all have law \pi_i. Its support retains the own-patch degree and clique conditions from Lemma 13.4. The degree error is O(b_*), because g\le n^{\iota/2}, and the positive surplus gives

Here |L_v|=n-o(n). The support and crossing losses from allocation, together with N\ge2^n and s_i=10^{-3}g, yield

Apply Lemmas 12.4 and 12.5 to this homogeneous bulk mass. Their even centered-moment bound also controls any fixed lower-tail threshold near 1/2. Since s_i>10^{-3}K_B\log n, the peeling term and the crossing failures give the asserted n^{-R} bound.

Injection and column loads. Apply the clock lemma with B=5, using these mass failures as predicates. Disjoint patches and the allocation counts give odd column sums o(1); atoms are exponentially small, each predicate reads n rows, and each row belongs to at most n predicates. The sampler therefore enforces every even-row mass bound.

Column loads require a separate estimate under this sampler. For fixed x\in X_i, expand the n-th moment of the average of M_iZ_v(x) over even roles in patch i. Its cap is 2^ne^{-200s_i}. Stars can intersect only at positions within distance 2, a fraction O(n^2)2^{-n+\ell_i}; their cap contribution tends to zero because the high gain exceeds the polynomial and prefix losses. For the remaining positions the stars are disjoint. The clock comparison on their at most n^2 queried rows restores independent labels, under which each row has mean M_i\sigma_v(x)=O(1). Lemma 3.6 gives a moment bound K^n.

If this normalized average is A_x, the actual column sum is O(2^nM_i/N)A_x/M_i=O(A_x/C_n). Markov and the union over at most N\le n2^n first labels bound the probability of any column sum above 1/2 by N(K'/C_n)^n=o(1). Thus one injection has both the enforced mass bounds and these column bounds. Normalize the hit-supported rows, increasing columns by at most a factor two, and apply Hall.□

Proof. By (14.3), the internal row \sigma_v is a probability except with probability \epsilon_i. When it is nonzero, its mass removed by J_v is at most

using the first test, the deterministic crossing-removal bound, and h_i<n^\iota. Now expose crossings. At each step the current normalized first law has small width, the new conditional law p_{g(b)}^W has small width, and its denominator is .5\pm2b_* on J_v. The deep-discrepancy calculation from the direct case therefore makes each ratio filter change mass by 1+O(b_*), outside exponentially small exceptions. At the end the retained mass is 1+o(1), and its normalized law satisfies \tau\le5^{\ell_i+1}\sigma_v on J_v.

The remaining bulk inputs are independent, each in a distinct group and slice. Apply (12.2) with their laws p_{g(b)}^W and denominators D_b^W. Lemma 12.4 bounds the small and moderate part of the centered moment by n^{-3R}. For the large-interaction part, the domination of \tau and the bulk product-ratio gates give, after averaging the internal and crossing data with their preceding success indicators,

The factor 2^u changes the conditional denominators to the nominal D_i’s in \Phi_v^W. Since \ell_i\le s_i/(1000u), the alarm bounds this expression by n^{-3R}. Even centered-power Markov, adding the preceding exceptions, gives (15.2).□

Proof.

Bin predicates. Given such prehistory, start the bin stage with independent group choices by q_g^W (bin identities below refer to physical bins, with their particular further masked/filtered laws as in each group). Require per v that conditional on bins its independent-role label probability of failure in (15.2) is \le n^{-R/2}; exception costs \le n^{-R/2} by Markov. In small-bin mode also require no bin chosen twice by distinct groups in its star, with exponentially small exception by (14.1). These are star constraints on bin choices. Finally require given-bin label column sums \le\theta_0.

Capacity certificates. Fix a physical bin D of size d=d_i, a label y\in D, and the entering history W. If group g chooses this bin, its h_i roles contribute

to the column, by (14.1) and the scale choices. Put groups with a_g(y)\in(\lambda_j/2,\lambda_j] in bucket j, where \lambda_j=d^{-1/2}2^{-j}. Its expected load under independent bin choices is m_j=\sum_{g\text{ in bucket }j}q_g^W(D)a_g(y). For

forbid every event that a specified l_j-subset of this bucket all choose D. Avoidance leaves at most l_j-1 chosen groups in the bucket, so its load is at most K'm_j+c'2^{-j/2}. First choose K' large, then c',\theta_* sufficiently small. Since \sum_jm_j<\theta_*, the sum of these allowed loads is at most \theta_0.

Give such a certificate charge 2^{l_j} times its product probability. To sum charges touching a fixed group, first pin its bin choice to D. For each y\in D, that group belongs to only one bucket. In that bucket put z=\sum_gq_g^W(D)\le2m_j/\lambda_j. The chosen constants and the additive allowance ensure

Summing over subsets containing the pinned group costs at most

The union over at most d columns still has this negligible bound; averaging the pinned target gives the unconditional touching bound. Here q>(\log n)^{c_q}, so these errors are smaller than every inverse polynomial in n.

Use charge n^{-5P} for each star constraint. At most O(nh_i) of them touch one group, and their raw probabilities have much stronger decay. Thus the total charge touching any group is \delta_n=o(n^{-4P}). For a certificate involving l groups, the reciprocal neighbor product is at most \exp(O(l\delta_n))\le2^l, which is paid by its chosen charge inflation. The polynomial scopes of star constraints likewise have reciprocal neighbor product 1+o(1). Lemma 3.5 now supplies all bin requirements. Dropping constraints touching O(n^3) queried groups costs 1+o(1), giving the asserted comparison with independent bin choices.

Conditional label assignment. In high-large-bin mode individual laws conditional on successful bins now meet the clock lemma (atoms \le2\exp(1.5k_iT_i)/d_i uniformly superpolynomially small). Draw an odd injection avoiding every mass failure. In high-small-bin mode instead start independently per assigned bin with (3.2) for its individual laws (maximum atom \le d_i^{-.95} by (14.1)). Here d_i\le n^{o(1)} and h_i=o(d_i^{.025}) uniformly. In each star a queried bin belongs to just one participating group by bin-stage success; multi-observations in it are possible only for internal incidences. Using exact singleton comparisons and (3.2) their overall joint upper-error factor is \le\exp(d_i^{-.04}h_i), so failure still costs \le2n^{-R/2}. Each bin serves at most d_i roles by the column-sum requirement, hence bin-variable dependence degrees are n^{2+o(1)} or less. Condition to avoid all these failures by the local lemma (charges e.g. n^{-5P}), retaining upper comparison to the preconditioning bin-wise sampling at 1+o(1) cost on O(n^2) queried bins. Thus either procedure gives an odd injection with the mass gates, without further reweighting earlier histories.□

Proof.

Caps and geometric separation. Fix x in patch i’s cleaned envelope; only its even patch positions can use it. We bound n-th moments of the patch average of M_i Z_v(x), with indicator of the prerequisite W-load success. On successes use both

Indeed off J_v the weight is zero; on it the bulk ratio gate and crossing degree bounds for both kernels (\ell_i b_*=o(1)) give the product comparison. Its individual factors are \le3 on this envelope. Also use (13.1), (14.2) with 10q^{C_b}\le s_i/(100u) for the cap.

There are three possible sources of repeated information in this moment: intersecting geometric core scopes, crossing scopes shared by different stars, and, for small bins, distinct groups choosing the same physical bin. We handle them in that order.

Expand by independent uniform even patch indices (positions, ordered by draw number). Call a position’s core scopes those for \sigma_v and its internal and bulk samples/kernels: the needed own-slice and nearby own-patch W consultations, groups and odd roles. Its core bin-choice variables are just the groups actually sampled for its internal and bulk labels; even the counterfactual calculations for \sigma_v use the observed internal labels and W, not bin draws elsewhere. Remove by the cap each index core-near an earlier index (earlier removals included), using proximity of complementary-word distance \le4 and inner distance \le100\rho h_i. This covers core intersections, and partner fraction per fixed index is at most 2^{-n}e^{.01s_i} by the inner volume, prefix and high slacks. On retained indices form a graph by full distance \le n^{2\iota}, partner fraction \le2^{-n+o(n)}. It covers any crossing-scope intersections between them (all internal dimensions <n^\iota); crossing consultations themselves are never in patch i, and within a star are in different patches. When using the second bound in (15.3) below, drop all crossing factors at nonisolated indices of this graph. If this graph has rank j, meaning its number of vertices minus its number of connected components, at most 2j vertices are nonisolated. Deleting their crossing factors therefore costs at most 3^{2j\ell_i}.

Label and bin transfers. For large bins transfer the retained indices’ needed data in that product bound to independent labels given bins by the clock bound (at most n^2 distinct queries), then use independent-bin upper comparison on the involved groups.

For small bins we need the following extra splice before these transfers. Given the bin choices, remove by the cap each geometrically retained index whose core groups’ bin choices intersect the core choices of an earlier geometrically retained index (even one that these bin repeats remove). In using (15.3) thus take the cap on all indicated removals, using the product bound and crossing-graph drops only on the remaining indices. For a core-bin removal keep its necessary repeat condition; against fixed earlier choices under independent bin sampling given W this costs per index

by distinctness of group variables across the geometrically retained cores and the high scale bounds. Among the remaining indices’ crossing queries not excised by the graph, use a fixed order and drop by factor 3 each hit factor whose bin repeats an earlier bin of these queries. Their group variables are all distinct and outside patch i; the necessary repeat condition costs \le2^{-n+o(n)} per drop against earlier choices under independent bins.

Small-bin removal patterns. Fix the position tuple and then one outcome of the ordered removal procedure just described: core-near rows are capped first; among the remaining rows, later core-bin repeats are capped; among crossing queries still allowed by the crossing graph, later bin repeats lose only their hit factor. Fix the resulting removal masks before comparing probability laws.

Let \mathcal R be the rows whose factors remain, and \mathcal B_v their remaining bulk and crossing queries. After paying the row caps and the factors 3, the nonnegative integrand has the form

Here \mathbf1_{\mathrm{rep}} retains the necessary earlier-bin repeat for every removal. Initially one also retains the mask-consistency and successful-history indicators. The rule for \sigma_v uses its observed internal labels and local W; its candidate calculations integrate hypothetical bins and never consult other actual bin choices. Consequently the displayed product reads actual bins only through its remaining label queries.