Sharp logarithmic exponents for fixed off-diagonal Ramsey numbers

Proof. Let M be the point-hyperplane incidence matrix. Every point lies in Q_{j-1} hyperplanes, and two distinct points lie in Q_{j-2} hyperplanes. Hence, writing J for the all-ones matrix,

The same identity holds with the two projective spaces interchanged. Subtract the mean of w and apply this identity to obtain Equation (2.2). Applying the resulting operator norm bound to the centered indicators of S and T proves Equation (2.3). Finally, p_j=(1+o(1))/q, so the sparsity assumption and Equation (2.3) give

for large q, proving the last assertion.□

Proof. Consider a clique with flags (a_1,b_1),\ldots,(a_m,b_m) in its increasing position order. For r<m, the covector b_r annihilates a_1,\ldots,a_r but not a_{r+1}. The first assertion follows from the earlier clique edges and the flag condition; the second follows from the edge between positions r and r+1. Thus a_{r+1} lies outside the vector span of its predecessors. The m lines are independent, while the nonzero covector b_m annihilates all of them. Its kernel has dimension d, so m\le d. Negating Equation (2.4) gives Equation (2.5). Reversal and dual interchange turn that same implication into itself.□

Proof. If \dim U=r with 1\le r\le d, then

The rectangles for r=0,d+1 are empty. Thus the occupancy of any fixed rectangle is binomial with mean at most 4\sigma. There are at most (d+2)q^{(d+1)^2} subspaces, by counting possible ordered bases. For A>4e, the exponential-moment bound for a binomial variable gives

with an immaterial adjustment for rounding the threshold. Choose A large enough in terms of d and sum over the subspaces. Under dual interchange, \mathcal R(U) becomes the rectangle defined by U^\perp, so no further event is needed.□

Proof. For any prescribed tuple f, the event F=f implies that f occurs on some increasing set of \ell stream positions, in one of the two allowed orientations. For each such set and orientation its iid probability is (Q_dQ_{d-1})^{-\ell}. The stream domination and a union bound therefore give

This containment of events uses no assumption about the selector’s conditional distribution. Shannon entropy is at least minus the logarithm of the largest atom. Now

Use \binom N\ell\le(eN/\ell)^\ell and \ell=\Theta(k) to conclude.□

Proof. The assertion is immediate when the relative entropy is infinite. Otherwise Jensen’s inequality gives, for bounded f,

Apply this with f=-1_E. Since -\log(1-u)\ge u for 0\le u<1,

which proves the claim.□

Proof. For a Bernoulli variable of mean p, its exponential moment is 1+p(e^t-1)\le e^{p(e^t-1)}; multiply over independent trials. For a Poisson variable the moment formula is an equality, by summing its series. Exponential Markov with t=\log(1+\delta) or t=\log(1-\delta) gives the two proportional tails. For the final bound use t=\log(h/\mu) and discard the factor e^{-\mu}.□

Proof. The last bounds follow from the interval for R. Also K_*/L=\sigma^{-2\beta} and L/P=1/R\le\sigma^{-\beta}. Since 9\beta<\eta/2,

Finally L\ge\sigma^{9\beta}, P\ge\sigma^{10\beta}, and \log L=O(\log\sigma), so

□

Proof. Put X=W\cap S, so |X|\geq c|S|, and first consider an ideal row of h=\lceil C_0q(d_T+1)\rceil independent uniform points of X. For an opposite point y, write p_X(y)=|X\cap N(y)|/|X|, where N(y) is its incident neighborhood. The variance identity in Lemma 2.1 yields

Since qp_j=1-Q_j^{-1}, there are at most Cq^{j+1}/|X|\leq Cq^{j+1}/|S| ambient points with p_X(y)<1/(2q). Every other point passes the row test with probability at most e^{-c_0h/q}, by a lower binomial tail. The expected number of such passing points in U_T is at most

Choosing C_0 large and then the cap-size constant large makes the probability of violating the first size bound less than .04, by Markov’s inequality and |T|\leq Cq^{j+1}/|S|.

For capture, if H_y denotes the row’s hit count at y, then

Averaging over y\in T gives expected excluded fraction at most

Thus the probability of losing more than .01|T| is O(\tau)=o(1). For large q, both desired properties hold for an ideal row with probability at least .9.

To implement the ideal experiment, propose independent rows from the known set W. Accept only rows whose entries all lie in X and whose ambient test has the two properties just proved. Conditional on all entries lying in X, a proposal has exactly the ideal law. Moreover,

A proposal is therefore accepted with probability at least .9e^{-C_1hP}. Search at most \lceil e^{C_2hP}\rceil rows, with C_2>C_1 sufficiently large. The failure probability is at most e^{-cq}, and the index costs O(hP)=O(qP(d_T+1)) bits. The decoder intersects the resulting ambient test with U_T, obtaining U_T'.

For the second test, the hidden source is X_T=U_T'\cap T and its proposal domain is U_T'. At readiness, the first successful test gives

Repeat the argument with h=\lceil C_0q(d_S+1)\rceil and a fresh table. The tested domain on the other side is the original U_S, not W. Conditional on the first cap, its source is fixed, has at least .99|T| points, and satisfies e(S,X_T)/(|S||X_T|)\leq\tau/(.99q). Thus the same ideal-row acceptance bound holds uniformly over every successful first cap. Consequently this second test captures .99 of the original S. The two costs and failure bounds give the conclusion; all finite diagnostics cost O(\sigma) and fit within the stated budget.□

Proof. Let \nu be one proposal’s law and A its acceptance event. For independent proposals and any deterministic cutoff m, the first accepted row, conditional on there being one among the first m, has law \nu(\,\cdot\mid A). Indeed, the contribution of acceptance at index i is (1-\nu(A))^{i-1}\nu(A) times that same conditional law. Given that all entries lie in X_0, the proposal is an independent uniform row on X_0, and the further acceptance probability is at least .9. The claimed domination follows. Apply (3.5) and use

Multiplication by the probability of production can only decrease the bound. No later success, including production of the other validation test, has been conditioned on.□

Proof. For a point z represented by a vector line \langle z\rangle, the quotient vector space has dimension j and hence projectivization \PG(j-1,q). Projection maps a point different from z to its image in this quotient; its fibers are the q noncentral points of lines through z. The dual operation retains hyperplanes containing z, identified with hyperplanes of the quotient. Write S_0,T_0 for the projected S\setminus\{z\} and the cut T\cap z^\perp. Apply the same operations to the decoder domains.

Lifting a quotient cap can enlarge it by a factor q, the size of a projection fiber. We remove that enlargement by intersecting caps from eight projections, always using the original S,T. At a given call let A\subseteq U_S be the intersection of all caps lifted so far, initially A=U_S. The next center will preserve almost all of S and limit collisions among the points of this current set A; the latter property makes successive intersections contract. There exists a center, chosen before that call’s fresh tables, satisfying

Here \operatorname{coll}_z(A) counts unordered distinct pairs of A\setminus\{z\} with the same projection.

To prove existence, choose z uniformly in the ambient point space. The variance identity gives

Here |T|\geq q^{(j+1)/2}e^{-b/2}\gg q, and replacing the constant 1/3 by any other fixed positive constant is harmless. Markov’s inequality gives the stated cut-domain bound with arbitrarily high fixed probability. A distinct pair projects together only if z lies on its joining line, an event of probability at most (q+1)/Q_j=O(q^{1-j}). Thus

The latter implies projection loss o(n) with probability 1-o(1): each nonempty fiber loses at most its number of unordered pairs, and omitting z loses at most one more point. Finally, an original incidence survives the dual cut with probability p_j\leq C/q. Its expected count before collapsing fibers is at most C\tau n|T|/q^2, and collapsing cannot increase it. A union bound, using large fixed constants in the three Markov bounds, proves (3.7). This reasoning is valid for every realized current A: fix that set and all earlier data, then combine the two events of probability 1-o(1) with the three Markov bounds. Their constants can be chosen so that the simultaneous event has positive probability. Choose a center in that event before exposing any of the fresh tables used by this call.

Transmit z in O(\sigma) bits and use a fixed coordinate convention on the quotient. The new product is at least q^je^{-b-O(1)} and the density at most C\tau/q. The projected S domain has size at most |U_S|, whereas |S_0|=(1-o(1))n; on the other side both domain and support shrink by comparable factors q. Hence both logarithmic gaps increase by O(1). These are the induction hypotheses, with changed fixed constants. Reorient if necessary, apply induction, and then Lemma 3.2, which returns caps on both quotient sides. In particular, the projected S cap captures .99|S_0| and has size at most

Lift this cap, excluding z, and intersect it with A. The original support loss is at most .01n, plus the o(n) total fiber excess, plus one possible center: among the lost images there are at most .01|S_0| first preimages, and all additional preimages are charged to n-|S_0|-\boldsymbol 1_{\{z\in S\}}=o(n). This bound concerns the original S, not merely the points retained by earlier calls. Thus each call loses fewer than .02n of its original points, and losses from intersecting the lifted caps add.

The first call gives |A_1|\leq qm_0. For any later call let k_i be the retained nonzero fiber sizes; there are at most m_0 of them. Cauchy–Schwarz and (3.7) give

By (3.3), the last coefficient is

After seven further calls, |A_8|\leq m_0(1+\rho+\cdots+\rho^6)+qm_0\rho^7=O(m_0), while more than half of the original S remains. Eight calls multiply the cost and failure bounds by fixed constants. The center at each stage depends only on data available before its fresh tables, so all conditional failure bounds apply. The set W=A_8 proves the result.□

Proof. If n\leq100qP, transmit n and the index of S among the n-subsets of U_S. The cost is at most

which is within the description budget. It gives W=S without failure. Assume henceforth n>100qP, so v>0.

When j=3 and g>\chi_0, greedily choose a plane richest in the remaining points of S, provided it contains at least K_p of them, and remove those points. Stop as soon as at least n/2 points have been removed or no qualifying plane remains. In the first case retain the captured prefix, with its list and cells; in the second retain the residual without a list. Otherwise retain all of S without a list. The asserted size and cap properties follow directly from the stopping rule. Greedy maximality makes the removed cell sizes nonincreasing. Since each removal has size at least K_p, the list has length at most n/K_p=q^{1/2}e^{-2g/15}\leq q^{1/2}. Plane identifiers and cell sizes each cost O(\sigma) bits, so the list costs O(q).

Suppose now that a retained list has a cell of size at least .04n', and let \Pi be its containing plane. Then S_1=S\cap\Pi has size at least .02n. The original sparsity and Markov’s inequality imply that at least half of T consists of hyperplanes having incidence proportion at most C\tau/q into S_1. For large q this is less than one, so their restrictions to \Pi are nonzero projective covectors. Each nonzero projective restriction has exactly q projective lifts: normalize its restriction to a fixed representative and choose the coefficient on a complement of the vector space underlying \Pi.

Group the retained lifts by their restriction multiplicities. One dyadic class [h,2h), with 1\leq h\leq q, carries at least c|T|/\sigma lifts. If T_1 is its set of distinct restrictions, then

Every member of T_1 has incidence proportion at most C\tau/q into S_1, since all its lifts have identical incidences there. Transmit \Pi and h. Use decoder domains U_S\cap\Pi and the nonzero restrictions having at least h lifts in U_T. The latter has size at most |U_T|/h, so its logarithmic gap increases by O(\log\sigma); the former gap increases by O(1).

Apply the dimension-two description, with reorientation if needed, and then Lemma 3.2. The resulting cap on S_1 has size at most

and captures .99|S_1|\geq cn points of S. Its cost is within the required budget because \log\sigma=o(P); its failure probability has the required order. This deals with every large cell. All other cases have the stated small-cell preparation. Notice that O_x is a subset of the training support: even when x\notin S', the earliest containing plane still specifies the same whole cell.□

Proof. Work over the algebraic closure \mathbb K of \mathbb F_q. Choose an affine chart containing all points of \mathcal S, which is possible because \mathbb K is infinite. The plane cap remains valid for planes over \mathbb K: rational points on such a plane have rational vector-span dimension at most three. Otherwise four linearly independent rational representatives would remain independent over \mathbb K. The points therefore lie in an \mathbb F_q-plane and obey the same cap.

Independently sample each point with probability A\sqrt{n/M^3}=o(1), where A is a sufficiently large fixed constant. The expected sample count on any M-rich line is at least A\sqrt{n/M}\geq cA\sqrt q. There are at most n^2 lines to test, since M\to\infty and two distinct points determine a line. Binomial tails and a union bound show that, simultaneously with positive probability, every rich line contains more than (A/2)\sqrt{n/M} sampled points, and the total sample has size at most 2A(n/M)^{3/2}. The latter assertion follows from an upper binomial tail, or from stochastic domination if |\mathcal S|<n.

There are \binom{D+3}{3} monomials of degree at most D in three variables. Solving the homogeneous linear system requiring vanishing at the sample therefore gives a nonzero polynomial of degree at most CA^{1/3}\sqrt{n/M}. Choose A large enough that this degree is smaller than the guaranteed number of sampled points on each rich line. Restriction to a line is a univariate polynomial, so it vanishes identically there. Replace the polynomial by its squarefree part. Its degree D_0 satisfies

We now count three groups of rich lines. Plane factors are controlled by the plane cap. Among the other lines, those with few points incident to three lines are controlled by the total point count. The remaining lines will lie in the common zero set of the nonplane surface and an auxiliary polynomial coprime to it, whose degrees bound their number.

First count rich lines lying in plane factors. There are at most \binom{D_0}{2} lines lying in two distinct such planes. For one plane let u be the number of remaining rich lines it contains. Select M'=\lfloor M\rfloor points of \mathcal S on each. If r_a is the number of selected occurrences at point a, then

The second inequality uses the fact that two distinct lines meet in at most one point. Cauchy–Schwarz and the plane cap give

For u>0 this implies u\leq K_pM'/((M')^2-K_p)=o(M'). Remove from each selected line its intersections with all other plane factors, losing at most D_0 points. The remaining union in this plane has size at least

Such unions for different planes are disjoint. Thus the plane factors account for O(n/M+D_0^2)=O(n/M) rich lines.

Let F_0 be the squarefree product of the nonplane irreducible factors. Every as yet uncounted rich line lies on F_0: the coordinate ring of a line is an integral domain, so vanishing of a product on the line implies vanishing of one factor. If there are no such factors we are done. For coordinate vectors e_1,e_2,e_3, form

At a point on at least three of the remaining lines, all Q_{ij} vanish. At a singular point this follows from the gradient factors. At a nonsingular point, the three distinct line directions lie in the two-dimensional tangent vector space. Restricting F_0 to each line shows that its Hessian quadratic form vanishes on each direction. A binary quadratic vanishing on three distinct projective directions is zero; since the characteristic is odd, its associated bilinear form is also zero. The vectors e_i\times\nabla F_0 span that tangent space, proving the assertion.

Among incidences with points of \mathcal S, points on at most two remaining lines account for at most 2n incidences. Hence all but O(n/M) remaining rich lines have at least M/2 points incident with three or more remaining lines. Since \deg Q_{ij}<3D_0=o(M), every such line lies on every Q_{ij}.

To obtain a polynomial coprime to F_0, we must show that the Q_{ij} do not all vanish identically on any of its irreducible components. The reason is local: their vanishing makes all second derivatives of a smooth formal graph zero, while the degree bound below the prime characteristic forces a plane factor.

We claim that no irreducible factor F of F_0 divides all these polynomials. Its degree is less than the prime characteristic q, so a nonconstant F has a nonzero partial derivative. Rename its variable z, and write the other variables as x_1,x_2. By squarefreeness, F and (F_0)_z are coprime in \mathbb K(x_1,x_2)[z]. Indeed, modulo F the derivative is F_z(F_0/F), and neither factor is divisible by F. Clearing a univariate Bezout identity gives

with polynomial coefficients. Choose x_1,x_2 so that a and the leading coefficient of F in z are nonzero. A root in z then gives a point on F where (F_0)_z\ne0.

Translate this point to the origin. The invertible coefficient of z in F_0 determines, recursively by total degree, a unique formal series z=h(x_1,x_2) with F_0(x_1,x_2,h)=0. The other factors are units on this branch. If F divided every Q_{ij}, those polynomials would vanish after this substitution. To see the tangent space statement over the formal series ring explicitly, write g=\nabla F_0(x_1,x_2,h). Its third coordinate g_3 is a unit, and the kernel of the row vector g has basis

Moreover e_2\times g=g_3t_1 and e_1\times g=-g_3t_2. The vanishing Q_{ij} therefore makes the Hessian bilinear form zero on this entire formal tangent module. Twice differentiating F_0(x_1,x_2,h)=0 gives

so all second partial derivatives of h vanish. For a monomial x_1^u x_2^v of total degree less than q, these conditions require

Only the constant and linear monomials satisfy these conditions. Writing h_1 for the affine-linear part, we obtain h-h_1\in(x_1,x_2)^q. Thus the polynomial F_0(x_1,x_2,h_1) vanishes to order at least q. Its degree is less than q, so it is identically zero. The plane z=h_1 would be a factor of F_0, a contradiction. This proves the claim.

Because \mathbb K is infinite, a constant linear combination Q of the Q_{ij} can be chosen coprime to F_0: for each of its finitely many irreducible factors, combinations divisible by that factor form a proper linear subspace of the coefficient space. We finish by justifying the elementary common-line bound used here.

If coprime polynomials in three variables have degrees D_1,D_2, they contain at most 2D_1D_2 common lines. To see this, take any finite collection of such lines and choose coordinates (t,u,v) with t nonconstant on each. Over the fraction fields in the other two variables, univariate coprimality gives cleared identities

For a generic c\in\mathbb K, both right-hand sides remain nonzero polynomials after t=c. Any common factor of the sliced polynomials would divide both a polynomial in u alone and one in v alone, and hence would be constant. Choose the slice also to meet the selected lines in distinct points; only finitely many values are forbidden by pairwise intersections of lines. Choose coordinates on this slice so that these points have distinct first coordinates. The resultant eliminating the second coordinate is nonzero by coprimality and has degree at most 2D_1D_2 in the first coordinate. Indeed its Sylvester determinant has at most D_2 columns with coefficients of degree at most D_1, and at most D_1 columns with coefficients of degree at most D_2. It vanishes at each of the distinct first coordinates, bounding the collection. If both sliced polynomials omit the second coordinate, their univariate coprimality gives no common point. If just one omits it, say it is f(u) and the other has degree m>0 in the second coordinate, the resultant is f(u)^m; it is again nonzero and vanishes at every common point. As this bounds every finite collection, it bounds all common lines.

Apply the bound to F_0,Q, whose degrees are at most D_0 and 3D_0. The remaining lines number O(D_0^2)=O(n/M). Together with the earlier exceptional lines this proves the lemma.□

Proof. The radial lines partition X_x, so their total strength is at most q. Thus there are at most q/a qualifying lines through any center. Comparing this with (3.14) reduces to

This holds for g\leq\chi_0 and large q, since a\leq2 and 2\chi_0<\chi. It also holds when g>\chi_0 but a\leq e^{-g/20}.

In the remaining regime put M=n'a/q. Since n'\geq n/2 and n=q^{3/2}e^g,

Also cq\leq n/M\leq Cqe^{g/20}, and (3.3) gives g\leq\sigma/2+O(1). Hence all hypotheses of Lemma 3.6 hold uniformly. In the capped residual case, that lemma gives Cn/M\leq Cq/a rich lines; each has q+1 rational centers. This yields at most Cq^2/a\leq Cq^2/a^2 relevant pairs.

Suppose instead that the plane list is retained. Here own-cell removal will force the center of a surviving rich line into a plane earlier than the first listed plane containing that line. This gives a bound on its possible centers. First, the list length satisfies

A relevant line must be contained in a listed plane, since otherwise it meets the union of the list in at most J<M points. Let i be its first containing plane. Earlier planes contribute at most J points to this line and later cells contribute none, so |C_i\cap\ell|\geq M-J\geq M/2. Its center must be in an earlier plane: otherwise O_x=C_i, leaving at most J<M points on this line in X_x. Since the line is not contained in any earlier plane, there are at most i-1 possible centers for it.

Put f_i=|C_i|/n'. Fix a sufficiently large constant C_0. If a>C_0f_i, the mean number of C_i points on a line of \Pi_i is at most 2f_i n'/q, much less than M/2. The projective-plane incidence variance bounds the number of lines with at least M/2 points by

Multiplying by at most i centers and summing gives

because \sum_i f_i=1 and J\leq q^v. In the other case a\leq C_0f_i, nonincreasing cell fractions and their unit sum imply i\leq C_0/a; there are at most C_0/a such indices. Each corresponding plane has O(q^2) lines and each line at most i possible centers. Their total is again O(q^2/a^2). This proves the center–line bound in all remaining cases.

For a fixed dyadic threshold, divide that bound by the right-hand side of (3.14). The number of centers where the latter fails, divided by n=q^{1+v}, is at most

Since v\leq1+O(1/\sigma) and the sum of a^{98} over all dyadic a\leq2 is bounded, the union of these exceptional sets has size o(n), as asserted.□

Proof. In dimension two, two distinct hyperplanes in the pencil are lines intersecting only at x. Because x\notin X_x, all overlaps are zero and all claims follow. Consider dimension three. The intersection of two distinct planes through x is a radial line; each radial line belongs to q+1 planes and therefore accounts for at most Cq^2 ordered pairs. Lemma 3.7 gives

The last inequality uses B=q^3/n'\asymp q^{2-v} and a\leq2; the factor e^\chi absorbs fixed constants. Within one plane, the radial lines partition its points other than x, so the sum of their strengths is at most 2. There are at most 2/a qualifying lines, each giving at most q other planes. Thus

Since B\geq cq, this implies the second bound in (3.15).

For the stronger assertion, \log(1/t_*)=O(\log\sigma)=o(P). If (v-1)\sigma<-4P, then

for large q, so (3.17) suffices at every center. Otherwise n\geq q^2e^{-4P} and g\geq\sigma/2-4P>\chi_0. Moreover t_*\gg e^{-g/20}. The center–line estimate of Lemma 3.7, which does not require a dyadic threshold, bounds the number of centers lying on even one radial line of strength at least t_* by

Remove these centers. At every remaining center \Delta_{t_*}=0, proving (3.16).□

Proof. Weighted incidence variance gives

The exact means differ from 1 and f_C by the factors qp_j=1-1/Q_j, whose squared contributions satisfy the same bounds. Summing over cells and using \sum_C f_C\le1 proves

For the second assertion use Cauchy–Schwarz on \sum_{H\in\mathcal E}(\lambda_H-1).

For the clipped squared-deviation weight of a cell, the total weight is at most CqBf_C and each weight is at most one. Its pencil sums have mean O(Bf_C) and total squared deviation at most Cq^jBf_C, by Lemma 2.1. For sufficiently large q, exceeding Be^\xi therefore excludes at most

centers. Sum this estimate over cells, rather than multiplying by their number. The full-deviation weight and the exceptional-indicator weight have the same proof with fraction one. Their union is D_2.

For a typical hyperplane, removing O_x subtracts a quantity within .02 of f_x, when a cell is present. Removing x subtracts at most q/n'. Thus \lambda'_H\ge .9-.04-.02-q/n'>.75 and |\delta'_H|\le .1+.02+q/n'<.18. The upper bound by 2 follows as well. On typical hyperplanes the relevant squared deviations are already below one. The inequality (u+v+w)^2\le3(u^2+v^2+w^2) and regularity give the last bound in (4.11); the removed center adds at most O(q^{j-1}(q/n')^2)=O(B) by (4.7).□

Proof. The average of \lambda_H over T is at most 2\tau. At least half of T consequently has \lambda_H\le8\tau. These hyperplanes are exceptional, and their number m is at least c qB e^{-b} by (4.3) and n'\ge n/2. Each is empty with probability at least a=e^{-8P\tau}. If Y counts the empty members of this particular set, then 0\le Y\le m and \E Y\ge ma. Therefore \Prob(Y\ge ma/2)\ge a/2, without any independence assumption among the hyperplanes. Choose c_0 small enough to obtain the first inequality of (4.14) on this event.

By (4.13), the expected contribution from \lambda_H\ge10^{-4} to \sum_{H\in Z}\lambda_H is at most CqB e^{-10^{-4}P}. Markov’s inequality at .0009z_{\min} bounds the probability of a larger contribution by

The remaining contribution is at most .0001z. Subtracting this failure probability proves the asserted simultaneous event.

For fixed Z, incidence variance has mean p_jz=(1-o(1))z/q and total squared deviation at most q^{j-1}z. This gives the ambient exception bound. On the hidden support, exact double counting gives

which proves the .99n' assertion by Markov’s inequality.

An exceptional hyperplane in Z contributes (1-b_x)^R to the score. For any other exceptional member of the pencil, an own-cell hit makes its product zero; otherwise an outside hit gives a factor -b_x, and all other factors have absolute value at most one. Its contribution has absolute value at most b_x. Regularity proves the error bound. Finally b_x\le e^{-.96L}, so b_xBe^\xi\le Be^{-.95L}=o(z_{\min}/q) and Rb_x=o(1) by (4.2).□

Proof. Batch independence raises the bounds in (4.17) to the Rth power. Fixed zero-one multipliers cannot increase their absolute values. By (4.11),

For the overlap terms, (4.5) and dyadic summation give, for R>200,

Every positive overlap is at least q/n' and at most 2, so it falls within the available dyadic range. There are O(\sigma) dyads. The inequality (u+v)^R\le2^{R-1}(u^R+v^R) handles their sum with the deviation terms. The diagonal contributes at most Q_{j-1}(2e^{-.75L})^R. Now use Q_{j-1}=O(B^2), 2\chi=.02P, and R\log L=o(P) to obtain the claimed exponent.□

Proof. We expand into ordered p-tuples of typical hyperplanes and bound the absolute expectation of every summand. The evenness of p will permit the final tail estimate. A tuple may contain repeated hyperplanes. Among its distinct hyperplanes, join H,H' when \theta_{HH'}>t_*, and take the connected components of this graph. A component consisting of one hyperplane appearing once in the tuple is a simple singleton. All other components are nonsimple.

Component expectations. A positive-strength radial line is external to the tuple if it is contained in hyperplanes in different components. The sum of the strengths of the external lines in any fixed tuple hyperplane is at most pt_*=.01: assign each such line to one other tuple hyperplane containing it, whose overlap is at most t_*. Condition further on all external line-batch schedules. The remaining schedules affecting different components are independent, and each hyperplane has internal mass at least .75-.01=.74. Call a hyperplane touched in a batch if one of its external lines has a hit in that batch.

For a nonsimple component, all factor magnitudes are at most one. Keeping just the factors of one of its hyperplanes bounds its absolute product expectation. In an untouched batch the expected absolute factor is at most 2e^{-.74L}; in a touched batch it is at most b_x\le e^{-.96L}. Independence between batches consequently bounds the entire component by

For a simple singleton keep its signed expectation. Let \theta_{\max} be the largest overlap \theta_{HH'} over the other distinct hyperplanes H' of the current tuple, taking zero if there are none. It is not a maximum over the whole pencil. In an untouched batch the mean has absolute value at most

in every batch it has absolute value at most 2e^{-.74L}. Let \mathcal B_H be the event that H is touched in at least R/2 batches. If it is not, at least R/2 factors have the sharper bound. Since p\theta_{\max}\le .01, R/2\ge200, and R\log(2L)=o(P), the resulting bound for a simple singleton is

The fixed own multipliers do not change either estimate.

We now sum these fixed-tuple bounds over the possible hyperplanes. For each valid tuple, retain e^{-.7P} per nonsimple component and e^{-.68P} per simple position, and expand the three terms in (4.19) at each simple position. The resulting bounds are nonnegative. After averaging the external schedules, the only remaining probabilistic factor in each term is the conditional probability of the selected events \mathcal B_H occurring together. We will bound the sum of these terms after dividing by B^p.

The geometric choices have three forms. Nonsimple components are counted either from a strong pair and a spanning tree or from repetitions of one hyperplane; deviation and overlap terms use the corresponding pencil bounds; the remaining hit events are covered by static certificates. Each such certificate charges any independent direction-batch hit event at most once. We construct these certificates below and then verify the probability union bound. These descriptions count moment terms and are not part of the public-table message.

The combinatorial descriptions use only p^{O(p)} choices of names, partitions, and orders. Record the partition of positions into equal hyperplane names, the partition of distinct names into their strong components, and spanning trees and traversal orders inside those components. Do not record the full strong graph. For any geometric assignment its true graph determines whether these recorded components are valid; an invalid assignment initially contributes zero. Dropping such validity restrictions later only enlarges a positive sum after the attenuation bounds have been assigned.

Nonsimple and deviation choices. For a component with at least two distinct hyperplanes, start with a strong pair. By (4.5), its normalized count is at most

Each later distinct vertex along its tree costs at most e^{-3P} by (4.6); a repeated position costs 1/B. For a component consisting of one hyperplane repeated, its first two positions cost Q_{j-1}/B^2=O(1), and further positions again cost 1/B. These counts are combined with (4.18) once per component.

A deviation choice has weighted normalized sum at most Ce^\xi by (4.11). Encode these and all nonsimple components first. The remaining choices are overlap shifts and events \mathcal B_H; their attenuation e^{-.68P} has already been retained.

Overlap shifts. For an unencoded shift vertex, choose the name of a neighbor attaining its largest positive overlap and a dyad a\le\theta<2a. Zero weights need not be encoded. If the neighbor is encoded, the weighted normalized count is at most

If it is not, encode the ordered pair with count (2pa)^{200}E_a/B^2, dropping the neighbor’s extra shift weight or event requirement, each bounded by one. Both vertices retain their attenuation. Equation (4.5) cancels a^{200} in either case and gives at most e^{2\chi} times polynomial overhead. Summing dyads has the same type of overhead. Continue until all unencoded vertices carry the event requirement \mathcal B_H.

Hit certificates and their probability weights. Fix a tuple and external schedules for which these remaining requirements hold. We describe certificates witnessing enough of the hits to count the tuple. Maintain two objects: a dictionary of radial directions whose geometry is already recorded, and a set of charged direction-batch events. On first introduction of a direction, charge one positive hit event, except in the pair operation below, which charges 200 distinct batches at once. Once that direction enters the dictionary, any later reference to it imposes no new hit requirement. In particular, no direction-batch event is charged twice.

For a fixed tuple all charged events are external events, independent under the conditional law given \mathcal O_x. Thus their joint probability is at most the product of their La_\ell weights. Keeping \min(1,La_\ell) would also be valid, but is unnecessary. From an encoded hyperplane H_0, the weighted sum of choices of a new line and a witnessing batch is at most

An old direction is specified by its dictionary index and requires no new probability factor. If the current dictionary has m directions, these references have at most m choices, each of incremental weight one. A direction choice, allowing either a new charge or an old reference, therefore has total weight at most 2P+m. The construction below keeps m=O(p), so these extra choices enter only the polynomial overhead.

Anchors and pairs. If an unencoded vertex has a touched direction shared with an encoded hyperplane, encode it using that direction as an anchor. A new direction is paid for by (4.20); an old one is referenced. Given the direction, there are at most Cq^{j-2} hyperplanes through it. The normalized geometric cost is therefore

This uses n'\asymp n and (4.7). In dimension two there are no positive external directions, and no such event requirements occur.

If no anchor is available but two unencoded vertices share external hits in at least 200 distinct batches on directions in no encoded hyperplane, encode this pair. Choose an overlap dyad, 200 witnessing batches and one shared hit direction in each. These events are new and distinct, outside the direction dictionary. For a fixed pair their total probability weights, summed over the witness choices, are at most (2Pa)^{200}. The normalized pair count in (4.5) then gives a cost at most e^{2\chi}(2P)^{200}. Add the vertices and witness directions to the encoded data. In dimension three the intersection direction of a pair is unique; repeated use of that direction in distinct batches still charges distinct independent events. Repeat the anchor and pair operations whenever either applies.

The residual root set. Suppose h vertices remain. Each has at least R/2 touched batches, whose witnessing external directions are shared with residual vertices only; otherwise an anchor would be available. Select one witness per such batch. A fixed neighbor appears fewer than 200 times, and a fixed direction appears fewer than 200 times. Either violation would permit the pair operation. Greedily keeping one witness and discarding others with its neighbor or its direction removes fewer than 400 witnesses. Thus each residual vertex has at least \lfloor R/800\rfloor witnesses with distinct neighbors and distinct directions.

There exists a set of at most h/10 roots such that every nonroot has two of these witnesses to roots. To prove this, select each vertex independently with probability 1/20. For any one witness list, the probability of fewer than two selected neighbors is at most CR e^{-cR}. Union over at most p lists is o(1) because R\gg\log(p+2). Markov’s inequality bounds the probability of more than h/10 selected vertices by 1/2. The two conditions therefore hold simultaneously with positive probability. If a residual set is too small to have the displayed number of distinct neighbors, it could not have reached this case in the first place.

Record the root names and choose their hyperplanes freely, dropping their extra event requirements. A root has normalized cost Q_2/B=O(q^v). Encode each nonroot by two distinct directions in its two chosen root neighbors, using (4.20) for new directions and dictionary references for old ones. Two distinct radial lines determine at most one projective plane, so the nonroot’s normalized geometric cost is 1/B=O(q^{v-2}). Restrict to distinct directions for this uniqueness statement. Each pair operation introduces at most 200 dictionary directions, each anchor at most one, and each nonroot at most two. There are at most p tuple vertices, so the dictionary always has at most Cp entries. Conditional on previously recorded geometry, each of the two direction choices thus has total weight at most 2P+Cp, including old references with unit incremental weight. After counting the unique plane, their positive weighted sum is bounded by (2P+Cp)^2; this is a polynomial overhead factor. If there are r\le h/10 roots, the aggregate geometric cost, apart from C^{O(h)}, is at most

This is favorable, and absorbs no attenuation assigned earlier.

Justification of the enumeration. The operations above are a way to choose a certificate from a realization, not an assertion of independence under adaptive choices. Take the union bound over all resulting static descriptions. More formally, for a fixed valid tuple, let I be the set of its remaining event requirements and let \mathfrak C be the family of certificates just described. Write \mathcal L(c) for the charged direction-batch ledger of c, and E_{\ell,r}=\{N_r(\ell\cap X_x)>0\}. The construction proves the pointwise inequality

Every ledger consists of distinct external events, so integration gives

Different certificates may overlap, which is harmless in this union bound. Exchange the nonnegative sums over tuples and certificates, and sum their numerical weights by the encoding order. Equations (4.5) and (4.20) give uniform bounds after previously encoded geometry is fixed. Every encoded hyperplane remains in the fixed typical pencil; in particular \lambda'_H<2 is retained wherever (4.20) is used. The local overlap constraints used in degree bounds are retained as well. For a residual nonroot, the two directions remain distinct until its unique plane has been counted; only their positive weighted sum is then bounded by the product of the two new-or-old choice bounds 2P+Cp. Old dictionary references add multiplicity without adding a hit probability factor. Discarding other compatibility restrictions can only increase these weighted sums. This occurs after the component attenuations have been justified for valid tuples, and never treats an adaptive hit as a fresh event.

There are O(p) dictionary directions and charged events: a pair uses the fixed number 200, an anchor uses one, and a residual nonroot uses at most two. Names, traversal orders, component partitions, root choices, batches, dyads, dictionary references and all polynomial factors in p,\sigma,P,R contribute at most \exp(O(p\log(\sigma+2)))=\exp(o(pP)).

Finally, a nonsimple component pays for its first two positions by e^{-.7P+2\chi}=e^{-.68P}, and for each additional position by at most e^{-P}. A simple position retains e^{-.68P}; its normalized weighted choice costs at most e^{2\chi} per position apart from the overhead, or less in (4.21). The deviation factor e^\xi is also at most e^{2\chi}. The weakest per-position saving comes from sharing e^{-.68P} between the first two positions of a nonsimple component. It is e^{-.34P} before negligible overhead. Summing the expansion proves the asserted B^p e^{-.1pP} bound.□

Proof. Use the deterministic threshold z_{\min}/(10q). By Lemma 4.5, the probability that |T_x^*| exceeds it, conditional on \mathcal O_x, is at most

outside D_0\cup D_1\cup D_2. By Lemma 4.4, the corresponding bound outside D_0\cup D_2 is e^{-cP}. Multiply each conditional estimate by the probability that x is unsampled and average its own schedules. These bounds therefore hold for the event that x is unsampled and its typical contribution exceeds the threshold.

For training points, the expected number of these failures is at most n'e^{-cP}. With failure probability O(e^{-cP})=o(e^{-8P\tau}), there are fewer than .01n' failures outside D_0\cup D_2. For ambient points, the expected number is at most Q_jq^{-50}, so Markov gives at most n e^{CP} failures with a further o(e^{-8P\tau}) exceptional probability. Here j\le3 and P\tau=o(\sigma). The static ambient exceptions D_1 are included by increasing C; D_0\cup D_2 has size o(n).

Intersect these events with (4.14). Their failure probabilities are subtracted from that event’s probability, not conditioned on its occurrence. The total sample count is Poisson with mean qP, and its exceeding 2qP costs e^{-cqP} by Lemma 2.6, again negligible. The remaining probability is at least c e^{-8P\tau}.

On this joint event, at least .99n' training points satisfy z_x\le .1z/q. Apart from o(n) static exceptions and .01n' unsampled failures, their exceptional and typical score contributions give A_x<z/(2q), by Lemma 4.3 and z\ge z_{\min}. Sampled points are included automatically. This retains a fixed fraction of S' and hence of S.

Conversely, an unsampled point with z_x\ge .8z/q, a regular pencil, and typical contribution of magnitude at most z_{\min}/(10q) has A_x>z/(2q) for sufficiently large q. The further exception depending on Z has size

Together with the static exceptions, ambient failures, and at most 2qP sampled points, this proves the size bound after enlarging C.□

Proof. Transmit the prepared plane list and cell sizes, the integers n,n', and the choice of the present mode. These cost O(q+\sigma) bits. The decoder can now generate a public-table proposal consisting of R independent Poisson batch sizes of mean qL, with entries uniform in its known domain U_S. The table supplies independent repetitions of this entire proposal. It is fresh relative to the data used to prepare S'.

The encoder accepts a proposal precisely if every entry belongs to S' and the conclusion of Lemma 4.6 holds for that row. The encoder knows the hidden data, so this is a well-defined finite test. For a specified ordered row with total count m and all entries in S', the proposal-to-true-law probability ratio is

The Poisson probabilities of the batch sizes cancel exactly. On successful true-law rows m\le2qP and n'\ge n/2, so summing these ratios over the successful rows proves proposal success probability at least

Choose a fixed C_2>C_1 and search at most

independent proposals, taking the first success and declaring failure if none exists. The failure probability is at most

The successful index has a self-delimiting description of O(qP(d_S+1)) bits. The encoder also sends z\le Q_j, costing O(\sigma) bits. The decoder reconstructs that proposal, computes the score from its samples and the transmitted list data, includes the sampled points, and intersects the resulting set with U_S. This intersection preserves all captured points of S'.

The decoder neither repeats the acceptance test nor needs the hidden supports to evaluate the resulting score. The guarantee concerns the first accepted row within a finite cutoff; it does not assert that this accepted row has an unbiased true-law distribution. Any later validation procedure uses its own fresh table. Finally, conditional on arbitrary earlier readiness data, the fixed-input calculation above is unchanged. This proves the uniformity, length, and failure claims.□

Completion of Proposition 4.1. Lemmas 4.6 and 4.7 give the stated set, message bound, and failure probability.□

Completion of the description lemma. The only unresolved branch in the proof of Lemma 3.1 was the prepared small-cell case in projective dimension two or three. Its inputs satisfy exactly the hypotheses of Proposition 4.1, which supplies that branch at a cost bounded by the lemma’s stated budget. Dimension two has no plane-list reduction and no external radial overlaps. The dimension-three large-cell reduction of Proposition 3.5 invokes the now established dimension-two result. The bounded higher-dimensional projection induction of Proposition 3.4 then applies successively. Its validation calls use fresh tables, as stipulated in the preceding section. Hence all branches of Lemma 3.1 are proved, with the specified one-sided capture, message length, and exponentially small failure.□

Proof. At a known state and rank r, a possible second endpoint b has at most 2q^{d-r} first partners annihilating V(b). For l\ge1, counting the incidences b\subseteq V(y) over y\in Z_l gives at most 2|Z_l|q^{l-1} memberships. Hence (5.3) allows at most 32q^l second endpoints, and its joint domain has size O(q^d) since l\le r. For l=0 there are no popular endpoints.

For a poor-cheap position, the variance estimate in Lemma 2.1 bounds the number of first endpoints in (5.4) by Cq^{d+1}/|Z_l|. Indeed their incidence count deviates by at least c|Z_l|/q from its mean for large q. The second endpoint belongs to Z_r, and |Z_r|\le|Z_l|. The product of these two marginal domain sizes is therefore at most Cq^{d+1}. Incidence mixing bounds the number of flags between them by

At an expensive step, more than |Z_l|/(8q) points of Z_l are hit by a, and fewer than |Z_l|/(16q) already have b\subseteq V(y). Thus at least |Z_l|/(16q) points increase their rank from l to l+1. The cumulative set U_l=\{y:\dim V(y)\le l\} has size at most (d+1)|Z_l| at this step, and loses a fraction at least 1/(16(d+1)q). Each U_l is nonincreasing throughout the scan. Starting with O(q^d) points, a nonempty integer-sized set can undergo only O(q\sigma) such multiplicative decreases. Charge a step to its chosen l and sum over 0\le l\le d. This proves the expensive-position bound in each scan.

The constant-alphabet masks specify the ranks, types, and positions of all transmitted flags. Their cost is O(k); there is no separate cost for the expensive positions. Conditional on the old context and masks, the transmitted values range over a product of h old domains. Its logarithmic size is at most h(d\sigma+\Delta+O(1)), without any independence assumption. This proves (5.5). The decoder reconstructs each scan by updating only at that scan’s expensive positions, ignoring values sent solely for the other scan. Given the reconstructed state and the encoded rank r, the fixed tie-breaking rule determines l; it need not be transmitted separately. The decoder therefore recovers all cheap restrictions. Choose J_0=d\sigma+O(1) to bound their joint domains uniformly.

All values outside U are known at \theta_0, so

Lemma 2.4 and (5.5) consequently give

The terms d\sigma\E h cancel. Dropping the last, nonpositive term gives (5.6) for U. For any specified history, the chain rule and the coordinate caps imply

Thus the deficit of S is pointwise nonnegative and no larger than that of U, proving the full assertion. Finally, the upper estimate H(F\mid\theta_0)\le(\ell-\E h)J_0 combined with (5.5) proves (5.7).□

Proof. At a history h=\theta_t, put

Both are nonnegative. The initial subset bound gives \E\mathcal D_0\le\mathcal B, and \mathcal T_0\le\mathcal D_0 since each marginal entropy is at most J_0. For a fixed fresh index set E_t, the entropy chain rule gives

Consequently \E\mathcal D_t\le\mathcal B at every round. Also \sum_i\delta_i\le\mathcal D_t, proving the first bound at every round, not just at the one eventually selected.

Expansion of the entropies gives the exact total-correlation identity

Here \operatorname{TC}_h(F_{E_t}) is the sum of the selected marginal entropies minus their joint entropy, at history h. For each unselected i, data processing gives M_i\le I_h(F_i;F_{E_t}). To include the selected positions, observe that for an i in a representative block, M_i is a function of the draws in the other blocks only. Its own block’s draw is uniform on n_t indices and independent of those draws. Hence, conditional on h and averaging only over the fresh indices,

Combining this with (5.13) yields

Now average and sum over t<T_1. The right-hand side telescopes and is at most \E\mathcal T_0\le\mathcal B, while n_t\to\infty uniformly. Some deterministic t therefore has \E\sum_iM_i\le C\mathcal B/T_1. Finally, uniform sampling gives \E\sum_{i\in E_t}\delta_i\le n_t^{-1}\E\sum_i\delta_i; (5.14) gives the identical factor for M_i. Since n_t=\Theta(m), both sampled bounds hold at that same round.□

Proof. If a distribution p is supported on at most Ce^L atoms and Z=\log(p(X)e^L), then \Prob(-Z>t)\le\min\{1,Ce^{-t}\}. Integrating this bound gives \E Z_-\le\log C+1, after enlarging C\ge1. Thus \E Z_+=L-H(X)+O(1). Apply this with L=d\sigma to the joint law at slot i. The cheap-domain cap yields

The mass of joint atoms exceeding e^Kq^{-d} is at most C(\delta_i+1)/K. By Markov’s inequality, the marginal mass of endpoints for which their conditional heavy-atom probability exceeds .02 is at most fifty times this. The lower marginal cutoff excludes mass at most e^{-K} by the support-size cap.

For a high class, (5.9) also implies

The same negative-part calculation, now using the support cap Cq^{r'}, bounds the mass of p_i^A(A_i)>e^Kq^{-r'} by C(\delta_i+1)/K. The second marginal uses r instead of r'.□

Proof. Under the actual conditional joint law, the event \{a\perp y,\ c\not\perp b\} has probability zero by consistency. The relative entropy of this law to the product law is I_{ij}. Lemma 2.5 therefore bounds the product probability of this reverse-conflict event by CI_{ij}. For given endpoints a,y, let

Except for good-incidence mass at most CI_{ij}/\rho^2, we have e(a,y)\le\rho^2. For such endpoints, Markov’s inequality says that at least 1-\rho of the conditional c-mass satisfies \Prob_\theta(B_i\not\perp c\mid A_i=a)\le\rho. These c are tests defining V_i(a). Every projective point of V_i(a) consequently annihilates at least 1-\rho of the law of c given y, and is a test defining U_j(y). Hence

To check the rounding even when u_i\ne u_j, take a common constant C\ge1 in (5.8) and put e_K=\log C+3K. Then (5.18) reads

For large q, e_K<K_* and K_*+e_K<\sigma. In an open band indexed by r, we have (u_i-e_K)/\sigma>r-1 and d+1-(u_j+e_K)/\sigma>d+1-r. Consequently the dimensions are at least r and d+2-r. These dimensions rule out (5.20) in ambient vector dimension d+1. All good-incidence mass is therefore exceptional, proving the claim with c_{ij}=0.

In an integer band indexed by r, the two expressions inside the ceilings are greater than r-1 and d-r, respectively, since u_i\ge r\sigma-K_* and u_j\le r\sigma+K_*. The lower bounds are therefore r and d+1-r. Containment forces

Let \Gamma_{ij} be the endpoint event that a,y are good and incident and satisfy (5.20). Define G_{ij} by additionally requiring b\subseteq V_i(a) and c\subseteq U_j(y), and put c_{ij}=\Prob_\theta(G_{ij}) in the actual joint law. Given a,y under the product law, b and c are independent with their respective conditional endpoint laws. Therefore

Applying Lemma 2.5 to G_{ij} gives an upper bound C(I_{ij}+c_{ij}) for its product probability. Add the CI_{ij}/\rho^2 exceptional mass to obtain the first assertion of (5.19).

It remains to bound the sum of charges without treating the history-dependent rectangles as fixed in advance. On G_{ij}, (5.17) and (5.21) imply

Both flags thus belong to \mathcal R(V_i(a)). Fix the history and an actual realized tuple. For each fixed earlier slot i, all later slots charged to it lie in the single rectangle determined by that history and its actual first endpoint. The simultaneous occupancy bound holds for every rectangle, including this adaptively chosen one, on every stream in the support of the current law. No conditional stream-domination estimate is needed. There are at most C\sigma charged later slots for each i, and hence at most C\sigma k charged pairs, pointwise. Conditional expectation proves the second assertion of (5.19).□

Proof. There are \Theta(k) unexposed positions, because T_1=o(m). By (5.10) and Lemma 5.2, the expected proportion violating the deficit bound is at most

Using half the second threshold for mutual information, the corresponding proportion is at most

Only integer bands have nonzero collision charges. At a fixed history, uniform sampling in blocks with n_t=\Theta(m) gives

The expected proportion exceeding half the collision threshold is therefore at most

The maximum of I_{ij}+c_{ij} is bounded by the sum of the two separate maxima, proving the first assertion.

For fresh representatives, the expected deficit sum has an additional factor C/m by (5.12). Each maximum over the other blocks is independent of its own block’s draw, so the same selected-index identity (5.14) applies to both mutual information and collision charges. Their expected sums also gain a factor C/m. The number of fresh representatives is 2w=\Theta(k/m), so their bad proportion obeys the same three vanishing bounds. This is an average statement and does not require that every representative be good simultaneously.

Finally, at a good index,

Lemma 5.3 proves the uniform endpoint assertion.□

Proof. If X or \mathcal V is empty, the result is immediate. Suppose otherwise, and put n=d+1. Denote by \widetilde X the set of all nonzero vector lifts of points of X, and by \widetilde Y the nonzero vector points of the union of the spaces in \mathcal V.

We use the Schwartz–Zippel zero bound [24, 27]: a nonzero polynomial of total degree at most h on \F_q^r has at most hq^{r-1} zeros. To see this, induct on r, writing the polynomial as a polynomial of degree t in the last coordinate. Its nonzero leading coefficient has degree at most h-t in the other coordinates. There are at most (h-t)q^{r-2} choices at which that coefficient vanishes; for every other choice there are at most t roots in the last coordinate. The asserted bound follows, with the univariate case starting the induction.

Fix a sufficiently small constant c>0, and put h=\lfloor c\delta q\rfloor. If V has vector dimension r, at least \delta(q^r-1) of its vector points belong to \widetilde X. This is greater than hq^{r-1}. Thus every polynomial of degree at most h vanishing on \widetilde X vanishes identically on each such V, and hence on \widetilde Y. Writing \mathrm{ev}_Z for evaluation on a set Z, restricted to these low-degree polynomials, gives

Here is a lower bound for this evaluation rank on an arbitrary nonempty set Z\subseteq\F_q^n. The monomials with individual exponents less than q span all functions on \F_q^n, by coordinatewise Lagrange interpolation, so their evaluations on Z have rank |Z|. If h\ge2n, partition their exponent box into boxes of side a=\lfloor h/n\rfloor+1. Every box consists of a fixed monomial times monomials of total degree at most n(a-1)\le h. Multiplication by that fixed monomial is a diagonal map on evaluations, and therefore cannot increase rank. The number of boxes is at most C_d\delta^{-n}, giving

Apply this to Z=\widetilde Y, combine with (6.2), and divide by q-1. If h<2n, then \delta q is bounded in terms of d. The result instead follows directly from |X|\ge1 and the ambient bound |\PG(d,q)|\le2q^d, after increasing C_d.□

Proof. Fix the history and fresh indices, and first suppose the early representative is good. Draw two independent rows, each of

full flags from its conditional marginal conditioned on both endpoints being good. Write their entries (a_t^{(1)},b_t^{(1)}) and (a_t^{(2)},b_t^{(2)}). These are auxiliary samples, independent of the actual unexposed tuple given the history and indices. By (5.9) and Lemma 5.3, their first and second marginal atom sizes are at most Ce^K/q^{r'} and Ce^K/q^r, respectively, and their support sizes are at most Cq^{r'} and Cq^r.

For every second-system projective point y, form the vector space

The decoded domain consists of all flags (c,y) satisfying

Here and below, dimensions of the spaces V_y are vector dimensions. Because y\subseteq V_y, every pair allowed by (6.3) is indeed an incident flag.

Coverage. Consider an actual target at a good middle index, and write it (c,y). The weighted variance estimate of Lemma 2.1 shows that, except for at most O(q^{d+1-r'}e^K) values of y, a source sample satisfies a\perp y with probability at least .4/q. The mass of these exceptions at a good target endpoint is at most

For a nonexceptional y, while the first-row span has dimension less than r, it contains at most Cq^{r-2} second points. The probability that a sample second endpoint belongs to that span is at most Ce^K/q^2=o(1/q). A sample therefore increases the span with probability at least .3/q while its rank is too small. Dividing the row into a fixed number of pieces proves that the first-row span reaches rank r with failure probability o(1). Independently, the second row has at least .1h/q first-endpoint hits on y, again with failure probability o(1).

Consistency of the actual early representative and target, Lemma 2.5, and (5.22) bound the product-law conflict probability \Prob(a\perp y,\ c\not\perp b) by C\sigma^{-2000\beta}/q. Conditioning the auxiliary source on good endpoints changes this by only a constant factor. Across both rows, the probability of any conflict is at most O(\sigma^{-1999\beta})=o(1). In the absence of a conflict, c annihilates the span generated by y and the second endpoints of all first-endpoint hits in both rows.

Write W_y for that combined span. We next bound the joint event \{\dim W_y>r,\ c\perp W_y\}, without conditioning on the absence of conflicts or on successful span growth. Fixing both auxiliary rows leaves the actual target law equal to its original conditional law p_i: the conditioning on good endpoints was applied only to the auxiliary source. Thus the target still has at most Cq^r possible second endpoints; for each such y, a combined span of dimension at least r+1 has at most 2q^{d-r-1} annihilating first points. Excluding joint atoms larger than e^Kq^{-d}, their total target probability is at most Ce^K/q=o(1). The excluded atom mass is O((\delta_i+1)/K)=o(1), by the proof of Lemma 5.3. If r=d, an excessive span is the whole vector space and has no projective annihilator. In particular,

Thus the first-row and combined spans both have dimension exactly r, outside an o(1) exceptional probability. Every second-row first-endpoint hit then has its second endpoint in V_y, proving (6.3).

The expected number of bad middle indices is o(k), as is the loss from bad target endpoints. A bad early representative can be declared a failure at cost o(1). We have therefore proved coverage of the middle targets with expected loss o(k).

Size. Fix the first row. For every y with \dim V_y=r, set

where (a,b) is a further independent sample from the same source law. Let X be the source’s second-endpoint support. If a_y\ge u>0, the atom bound implies

For 0<u\le u_0, with u_0>0 fixed and small, this is relative density at least c u e^{-K} in \PG(V_y). Since y\in\PG(V_y), Lemma 6.2 gives

The same bound at u=u_0 accounts for every candidate above that threshold. On a dyad u\le a_y<2u below u_0, the second-row count in (6.3) is binomial with mean at most 2hu/q. Its probability of reaching .1h/q is at most

For completeness, put t=h/(10q) and u_j=u_0\,2^{-j-1}, j\ge0. If C_0 is the constant in the binomial bound, the contribution of all these dyads is at most

For large q, t\ge d+2. Choose u_0 so that C_0u_0\le1/2. The displayed fraction is then bounded uniformly in t, so no factor exponential in h/q remains. Together with the count for a_y\ge u_0, the expected total number of admitted second points is at most q^r e^{O(K)}. These dyads cover every arbitrarily small positive a_y; candidates with a_y=0 never pass. Markov’s inequality gives the same bound, with an enlarged constant, with high constant probability. Each admitted point has at most 2q^{d-r} first-point partners, giving the claimed flag-domain bound.

The decoder receives the two raw rows and r, so the message length is O(h\sigma)=O(q\sigma^{1+\beta}). Definition (6.3) uses neither X, the probabilities a_y, nor any other hidden marginal data. The size event and the event of retaining a prescribed positive fraction of the middle targets have intersection of probability bounded below. On that event retain the first prescribed number in order.□

Proof. Partition each positive marginal support into levels according to \lfloor-\log p\rfloor. This nonnegative integer has mean at most the marginal entropy, which is O(\sigma). Comparison with a geometric distribution of comparable mean, using nonnegativity of relative entropy, bounds its entropy by O(\log\sigma).

For a pair of level sets A_0,B_0, put

These numbers are nonnegative. The reciprocal caps (5.8) and incidence mixing give

Apply the entropy chain rule to the two level indices and then bound the conditional flag entropy by the logarithm of this count. Since H_\theta(F_i)=J_0-\delta_i, this gives

At a good index, \delta_i/K\le\sigma^{-2\beta}, and \log\sigma=o(K). Levels whose loss exceeds K therefore carry o(1) marginal mass.

Within each level the positive weights differ by at most a factor e. If more than half its points are bad, its bad points carry at least 1/(2e) of the level’s mass. Equation (5.15) consequently shows that such levels also carry only o(1) mass. Keep the levels with loss at most K and at least half of their points good. Choose one with probability proportional to its original marginal mass, and take its subset of good points. The size assertion follows immediately. The retained levels have total mass at least 1/2 for large q. For a point in a retained level, its level mass divided by the number of good points in that level is at most 2e times its own mass. The renormalization costs at most another factor 2, proving the pointwise bound. The same construction applies to the other endpoint and uses independent auxiliary randomness when desired.□

Proof. The pre-tree deletions have already been bounded, and all windows have equal size. It remains to analyze the tests without conditioning on the later retention of a window.

Fix the history, indices, all original support choices, and any earlier auxiliary data making a validation test ready. In the first validation test the hidden source is the intersection of the described set with one trimmed support. Description capture and the .9 trim make it a fixed positive fraction of the corresponding original support. If this test succeeds, the second test’s hidden source is also a fixed positive fraction of its original support, by the .99 capture assertion of Lemma 3.2. For either test and every fixed opposite point y, let E_y be the event that the test is produced and excludes y by its ambient test. Lemma 3.3 gives

where X is that test’s original pivot support. The right side no longer depends on the readiness data. The contribution is zero if the node is not reached or the test is not ready. We may consequently average over all earlier auxiliary data with no additional conditioning.

More explicitly, fix one ancestor test and a descendant’s corresponding original support Y. Let L be the fraction of Y excluded by that test, set to zero when the test is not produced. If \mathcal H denotes the history and indices, and \mathcal S all original support choices, averaging over readiness data gives

This bound is not conditioned on reaching the test. Now average the original support choices under their original independent law. The chronological inheritance rule ensures that the pair is always an earlier first support against a later second support. Equation (6.6) bounds the expected lost fraction by C\varepsilon per ancestor test. This remains true when readiness data or the prescribed acceptance predicates depend on other original support sets: those sets were fixed before (6.10) was applied.

At a node of depth j, failure of a trim after all previous successes requires loss of at least one tenth of an original support to its ancestor tests. The joint probability of this event and reaching the node is therefore at most Cj\varepsilon. By (6.6) and Markov’s inequality, the unconditional same-node density rejection probability is at most C\sigma^{-1000\beta}. Conditional on reaching a ready node, a description or validation failure costs Ce^{-cq}, uniformly in its input data. Hence, if H=C\log(w+2), a fixed window’s probability of deletion somewhere along its path is at most

For an actual good middle target, instead integrate (6.10) against its unnormalized good endpoint mass. Independence of the auxiliary construction from actual unexposed flags and (6.7) give an exclusion probability at most C\varepsilon per relevant ancestor test. Both tests are relevant at the target’s own pivot. This count includes a first test as soon as it is produced, even if the second test subsequently fails. Neither this estimate nor (6.11) conditions on eventual survival of a descendant or target.

The expected bad-index fraction tends to zero by Proposition 5.5, and the bad-endpoint mass at every good index tends uniformly to zero by Lemma 5.3. Combining these losses with (6.11) and the O(H) relevant tests gives expected total loss o(k). The original middle-target population is a fixed positive multiple of k. With probability tending to one, at least a prescribed smaller positive multiple remains; retain the first prescribed number in order.□

Proof of Lemma 6.1. Apply the preparation of Section 5. Its class selection conditions on an event of probability bounded below; its choices and orientation are determined by the revealed history. In a high-rank class use Lemma 6.3, with w=1. Its cost O(q\sigma^{1+\beta}) is bounded by (6.1), and its exponent O(K) is O(K_*). In a reciprocal class use the support construction, tree, and Lemma 6.5. Equations (6.12) and (6.15) give the required output budgets. The window sizes in (5.11) imply

in both reciprocal cases, and this bound also holds for w=1 under the admissible range of D.

Initially average over the fresh public tables as well as the auxiliary support choices and other randomness. The preceding arguments give a probability bounded below of having the required number of targets and all asserted output properties. Hence some fixed choice of the entire public table family retains a bounded-below probability of this event. Fix that family first, then condition on successful extraction of the prescribed deterministic length. The fresh table family was independent of the input stream, so fixing it does not change the input stream’s marginal law. For any stream event, the subsequent success conditioning increases its probability by at most the reciprocal of the fixed success probability. Thus constant domination persists, while the occupancy property persists pointwise. The retained tuple is an ordered subtuple in the selected orientation and remains consistent.

The message-length and domain bounds hold for every successful history and every fixed table realization, not merely on average over histories. They therefore remain valid under this possibly biased conditioning. The new context is precisely its standalone message, not that message together with the old history. Consequently its entropy and slot domains satisfy (6.1), with fixed constants, as asserted.□

Proof of Theorem 1.2. Fix d\ge5 and 0<\eta<1/10, with all the parameters of Equation (2.1). Suppose, for a contradiction, that every stream has a consistent k-tuple. Select one by a fixed rule, and condition on the simultaneous rectangle event of Lemma 2.3. For large q this event has probability at least 1/2, so the new stream law is dominated by twice the iid law. The selected tuple has deterministic length k.

Initially the context is empty. Its entropy budget is \Lambda_0=0, and the full flag domain has size

Thus we may take \Delta_0=(d-1)\sigma. The stage parameter defined in Equation (5.2) is initially

which lies in the admissible interval [\sigma^\beta,\sigma^{1-\eta/2}] for sufficiently large q.

Consider any admissible stage with budgets \Lambda,\Delta and parameter D. By Lemma 6.1, its replacement context has budgets satisfying

The high-rank case is included with w=1. The constants may depend on d,\eta, a fixed lower bound for \ell/k, and fixed upper bounds for the stream domination factor and the domain prefactor. They are uniform over all input laws, contexts, conditional histories, and class choices satisfying those numerical bounds, as in Lemma 6.1. Using k\asymp q\sigma^{1+\eta} and P\le4D\sigma^{9\beta}, the three terms to estimate satisfy

Also \log(w+2)=O(\log(\sigma+2)). We obtain

Indeed, w\sigma/k\le Cq^{-1}\sigma^{1-\eta/2}/D is exponentially small in \sigma, uniformly for admissible D. The other two terms have exponents strictly below -\eta/3, because \beta=\eta/10^7; their fixed constants and logarithmic factor are absorbed for large q.

Recompute the stage parameter from the new budgets, without retaining the old context. Equations (5.2) and (7.2) give

The last inequality follows from \beta-\eta/3<-\eta/4 and 7\beta-\eta<-\eta/4. This recurrence preserves admissibility: its lower bound D_{\rm new}\ge\sigma^\beta follows from the definition, while

for large q.

Choose the number of stages in advance, for example T=\lceil8/\eta\rceil. Iterating Equation (7.3), and using D_0\le\sigma for large q, gives

One further compression stage produces budgets \Lambda_*,\Delta_* with

We justify explicitly the probabilistic invariants throughout this iteration. At each stage Lemma 6.1 first averages over fresh public tables and fixes a table family with an extraction event of probability bounded below. It then conditions on that event and retains a prescribed deterministic number of slots in one of the two allowed orientations. The new decoder uses only its new context and its fixed tables. In particular, its entropy budget is \Lambda', not the sum of earlier context entropies. Every retained tuple is consistent, remains in the original stream in an allowed orientation, and still satisfies the simultaneous rectangle bound.

The constants and thresholds can be fixed without knowing the actual conditional laws. Start with the numerical bounds \ell/k=1, domain prefactor 4, and domination factor 2. The uniform statement of Lemma 6.1 supplies a positive lower bound on the next retained proportion and on the conditioning probability, and an upper bound on the next domain prefactor. Use these to prescribe the next stage’s numerical bounds, including the old domination bound divided by the success-probability lower bound. Recursively do this for the already fixed T+1 stages, taking maxima over the finitely many class types if necessary. All resulting constants are independent of q; choose q above their finitely many uniform thresholds and the arithmetic thresholds used above. No enumeration of conditional histories, or history-dependent limiting argument, is involved.

Consequently the final length is deterministic and satisfies \ell_*=\Theta(k), and the final stream law still has a constant domination factor. Lemma 2.4 therefore applies to the final tuple F_*. Only the marking scans are now performed: no further class selection, tuple extraction, or conditioning is used. The marking message specifies the expensive flag values and a cheap domain for each remaining slot. Conditional on that message, the entropy of the remaining values is bounded by the logarithm of the product of those domains. Thus Equation (5.7) bounds the entropy of the entire tuple under its present law.

Therefore, Equation (5.7) from the final marking scan and Equation (7.4) give

Lemma 2.4 gives instead

These inequalities contradict each other, since \ell_*\ge c k for a fixed c>0 and \log\sigma\to\infty. Consequently some stream has no consistent k-tuple. Its flag graph has independence number less than k and is K_{d+1}-free by Lemma 2.2, as required.□

Proof. Define

where p ranges over primes. Every prime in (m,2m] divides \binom{2m}{m}, so

Summing at powers of two and then using monotonicity proves \vartheta(x)\le Cx.

The exponent of p in the central binomial coefficient is

Each summand is zero or one, and therefore

The last inequality follows because the largest of the 2m+1 binomial coefficients is at least their average 4^m/(2m+1). For proper prime powers the rough estimate

suffices: there are O(\log x) exponents h\ge2, at most \sqrt{x} possible bases for each, and each weight is at most \log x. It follows first for even integers, and then by monotonicity for all large real x, that \vartheta(x)\ge cx. Choose c_0<c/(2C). For sufficiently large x, \vartheta(x)>\vartheta(c_0x), proving that the stated interval contains a prime.□

Proof. Choose an independent set I uniformly from all independent sets of H, including the empty set, and write \mu=\E|I|/n. At a vertex x, expose I outside the closed neighborhood of x. Let Z_x be the number of neighbors that have no neighbor in this exposed part of I. These available neighbors are mutually nonadjacent because H is triangle-free. The remaining independent-set choices are therefore \{x\} or an arbitrary subset of the Z_x available neighbors, all with equal conditional probability. Hence

The last inequality includes Z_x=0. Averaging also over a uniform vertex x, the degree bound gives

Since (1+2^z)^{-1}\ge2^{-z}/2 for z\ge0, Jensen’s inequality now gives

If \mu<\log(D_0+1)/(8(D_0+1)), then Equation (7.6) implies \mu>1/(2\sqrt{D_0+1}), using \log2<1. This is impossible: \log u\le2\sqrt u for u\ge1 implies \log u/(8u)<1/(2\sqrt u). Thus \mu has the claimed lower bound, and \alpha(H)\ge\E|I|=n\mu completes the proof.□

Proof. Induct on s. The case s=2 follows from r(2,t)=t. If a triangle-free graph has no independent set of size t, then all its degrees are below t, because every neighborhood is independent. Lemma 7.2, with D_0=t, bounds its order by 8t(t+1)/\log(t+1). This proves the case s=3.

Now let s\ge4 and suppose the estimate holds for smaller clique parameters. Let G have n>0 vertices, maximum degree h, no K_s, and no independent set of size t. Every neighborhood avoids K_{s-1} and an independent t-set. Likewise the common neighborhood of the two endpoints of an edge avoids K_{s-2} and an independent t-set. Therefore

Summing these common-neighborhood sizes over edges counts each triangle three times, so G has at most nhm/6 triangles.

If h\le t^{s-5/2}, the greedy bound \alpha(G)\ge n/(h+1) gives

Assume henceforth that h>t^{s-5/2}, and set \lambda=(hm)^{-1/2}\le1. By the induction bound on m,

for sufficiently large t.

Retain each vertex independently with probability \lambda. Delete all retained vertices whose degree in the sampled graph exceeds 12\lambda h, and then delete one vertex from each triangle still present until none remains. If E_0,T_0 are the initial sampled edge and triangle counts, respectively, the first deletion removes at most 2E_0/(12\lambda h) vertices, and the second at most T_0. Their expected numbers are at most

Some realization therefore leaves a triangle-free induced subgraph H with

Deleting further vertices cannot increase degrees, so both conclusions hold simultaneously. Lemma 7.2 and Equation (7.7) imply

Finally substitute h<r(s-1,t) and its induction bound to obtain n\le C_s t^{s-1}/(\log t)^{s-2}. Increasing C_s absorbs the additive one in passing from the order of an avoiding graph to its Ramsey number.□

Proof of Theorem 1.1. The lower bound follows from Equation (7.5) and the choice of \eta made there. Proposition 7.3 gives the asserted upper estimate. For every fixed \varepsilon>0, its constant is eventually bounded by (\log t)^\varepsilon; hence

for all sufficiently large integer t. Taking logarithms and dividing by \log\log t>0 bounds the expression in the theorem between s-2-\varepsilon and s-2+\varepsilon. Since \varepsilon is arbitrary, its limit is s-2.□