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, \[MM^{\mathsf T}=q^{j-1}I+Q_{j-2}J.\] The same identity holds with the two projective spaces interchanged. Subtract the mean of \(w\) and apply this identity to obtain Equation (2). Applying the resulting operator norm bound to the centered indicators of \(S\) and \(T\) proves Equation (3). Finally, \(p_j=(1+o(1))/q\), so the sparsity assumption and Equation (3) give \[\frac{|S||T|}{2q} \le q^{(j-1)/2}\sqrt{|S||T|}\] 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 (4) gives Equation (5). Reversal and dual interchange turn that same implication into itself. ◻

Proof. If \(\dim U=r\) with \(1\le r\le d\), then \[|\mathcal R(U)|=Q_{r-1}Q_{d-r}\le4q^{d-1}.\] 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 \[\mathbb P\{\text{occupancy}>A\sigma\} \le (4e/A)^{A\sigma} =q^{-A\log(A/(4e))},\] 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 \[\mathbb P(F=f)\le2C_0\binom N\ell(Q_dQ_{d-1})^{-\ell}.\] 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 \[\log(Q_dQ_{d-1})=(2d-1)\sigma+O(1/q), \qquad \log(eN/\ell)=(d-1)\sigma-\eta\log\sigma+O(1).\] 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\), \[\mathop{\mathrm{KL}}(P\Vert Q)\ge \mathbb E_P f-\log\mathbb E_Q e^f.\] Apply this with \(f=-1_E\). Since \(-\log(1-u)\ge u\) for \(0\le u<1\), \[\mathop{\mathrm{KL}}(P\Vert Q) \ge-P(E)-\log\bigl(1-(1-e^{-1})Q(E)\bigr) \ge-P(E)+(1-e^{-1})Q(E),\] 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\), \[P\le4\sigma^{1-\eta/2+9\beta}=o(\sigma).\] Finally \(L\ge\sigma^{9\beta}\), \(P\ge\sigma^{10\beta}\), and \(\log L=O(\log\sigma)\), so \[\frac{R\log L}{P}=\frac{\log L}{L}=o(1), \qquad \frac{\log\sigma}{P}=o(1).\] ◻

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 3 yields \[\sum_y\bigl(p_X(y)-p_j\bigr)^2 \leq \frac{q^{j-1}}{|X|}, \qquad p_j=\frac{Q_{j-1}}{Q_j}.\] 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 \[|U_T|e^{-c_0h/q} =|T|e^{d_T-c_0h/q}.\] 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 \[ \mathbb P\{H_y\geq h/(5q)\} \leq 5q p_X(y). \tag{13}\] Averaging over \(y\in T\) gives expected excluded fraction at most \[\frac{5q e(X,T)}{|X||T|} \leq C\tau.\] 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, \[\frac{|W|}{|X|}\leq e^{C_1P}.\] 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 \[\frac{|U_T'|}{|X_T|} \leq \frac{Cq^{j+1}}{|S||T|} \leq Ce^b\leq e^{CP}.\] 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 (13) and use \[\frac{|X_0\cap N(y)|}{|X_0|} \leq c^{-1}\frac{|X\cap N(y)|}{|X|}.\] 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 \(\mathop{\mathrm{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 \[ \begin{aligned} |T_0|&\asymp |T|/q,& |U_T\cap z^\perp|&\leq C|U_T|/q,\\ |S_0|&\geq(1-o(1))n,& e(S_0,T_0)&\leq C\tau |S_0||T_0|/q,\\ \operatorname{coll}_z(A)&\leq C|A|^2/q^{j-1}.&& \end{aligned} \tag{15}\] 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 \[\mathbb P\left\{\left||T\cap z^\perp|-p_j|T|\right| >\frac{|T|}{3q}\right\} \leq Cq/|T|=o(1).\] 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 \[\mathbb E\operatorname{coll}_z(A)\leq C|A|^2/q^{j-1},\qquad \frac{\mathbb E\operatorname{coll}_z(S)}{n} \leq Cq^{(3-j)/2}=o(1).\] 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 (15). 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 11, which returns caps on both quotient sides. In particular, the projected \(S\) cap captures \(.99|S_0|\) and has size at most \[\frac{Cq^j}{|T_0|}\leq \frac{Cq^{j+1}}{|T|} \leq m_0:=ne^{C_3P}.\] 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 (15) give \[\begin{split} |A_{\mathrm{new}}| &\leq m_0+\sum_i(k_i-1) \leq m_0+\sqrt{m_0\sum_i k_i(k_i-1)}\\ &\leq m_0+C|A|\sqrt{m_0/q^{j-1}}. \end{split}\] By (11), the last coefficient is \[\rho\leq e^{C_4P}q^{(3-j)/4}\leq q^{-1/4+o(1)}.\] 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 \[O(\sigma)+\log_2\binom{|U_S|}{n} \leq C\bigl(\sigma+n(d_S+1)\bigr),\] 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 \[|T_1|\geq c|T|/(h\sigma),\qquad |S_1||T_1|\geq q^3e^{-b-O(\log\sigma)}.\] 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 11. The resulting cap on \(S_1\) has size at most \[\frac{Cq^3}{|T_1|} \leq\frac{Cq^4\sigma}{|T|} \leq Cn\sigma e^b\leq ne^{CP}\] 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 \[ D_0=O(\sqrt{n/M})=o(M),\qquad D_0\leq Cq^{41/80}<q. \tag{20}\]

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 \[\sum_a r_a=uM',\qquad \sum_a r_a^2\leq uM'+u(u-1).\] The second inequality uses the fact that two distinct lines meet in at most one point. Cauchy–Schwarz and the plane cap give \[(uM')^2\leq K_p\bigl(uM'+u(u-1)\bigr).\] 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 \[u(M'-D_0)-\binom u2\geq uM'/2.\] 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 \[ Q_{ij}=(e_i\times\nabla F_0)^{\mathsf T} \operatorname{Hess}(F_0)(e_j\times\nabla F_0), \qquad 1\leq i,j\leq3. \tag{21}\] 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 \[A F+B(F_0)_z=a(x_1,x_2)\ne0\] 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 \[t_1=(1,0,-g_1/g_3),\qquad t_2=(0,1,-g_2/g_3).\] 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 \[(F_0)_z h_{ab}=0\quad (a,b\in\{1,2\}),\] 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 \[u(u-1)=uv=v(v-1)=0\pmod q.\] 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 \[A F+B G=a(t,u)\ne0,\qquad C F+D G=b(t,v)\ne0.\] 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 (22) reduces to \[e^{2g}a^{99}\leq e^\chi.\] 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\), \[\frac M{n^{1/3}}\geq c e^{(2/3-1/20)g},\qquad \frac{M^2}{K_p}\geq c e^{(2/3+1/10)g}.\] Also \(cq\leq n/M\leq Cqe^{g/20}\), and (11) gives \(g\leq\sigma/2+O(1)\). Hence all hypotheses of Lemma 15 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 \[\frac JM\leq C e^{-(1+2/15-1/20)g}=o(1).\] 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 \[\frac{Cq|C_i|}{M^2} \leq Cq^{2-v}f_i/a^2.\] Multiplying by at most \(i\) centers and summing gives \[Cq^{2-v}a^{-2}\sum_i i f_i \leq Cq^{2-v}J/a^2\leq Cq^2/a^2,\] 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 (22). The number of centers where the latter fails, divided by \(n=q^{1+v}\), is at most \[Cq^{v-1}e^{-\chi}a^{98}.\] 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 16 gives \[E_a\leq Cq^{4-2v}e^\chi a^{-100} \leq B^2e^{2\chi}a^{-200}.\] 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 \[ \Delta_a\leq Cq/a. \tag{25}\] Since \(B\geq cq\), this implies the second bound in (23).

For the stronger assertion, \(\log(1/t_*)=O(\log\sigma)=o(P)\). If \((v-1)\sigma<-4P\), then \[Be^{-3P}\geq cq e^P\geq Cq/t_*\] for large \(q\), so (25) 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 16, which does not require a dyadic threshold, bounds the number of centers lying on even one radial line of strength at least \(t_*\) by \[Cq^2/t_*^2\leq ne^{CP}.\] Remove these centers. At every remaining center \(\Delta_{t_*}=0\), proving (24). ◻

Proof. Weighted incidence variance gives \[ \sum_H(\lambda_H-1)^2\le CqB,\qquad \sum_H(\lambda_{H,C}-f_C)^2\le CqBf_C. \tag{37}\] 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 \[ |\mathcal E|\le CqB,\qquad \sum_{H\in\mathcal E}\lambda_H\le CqB. \tag{38}\] 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 3. For sufficiently large \(q\), exceeding \(Be^\xi\) therefore excludes at most \[C\frac{q^jBf_C}{B^2e^{2\xi}}=Cn'f_Ce^{-2\xi}\] 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 (36); the removed center adds at most \(O(q^{j-1}(q/n')^2)=O(B)\) by (32). ◻

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 (28) 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 \(\mathbb EY\ge ma\). Therefore \(\mathbb P(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 (39) on this event.

By (38), 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 \[C\exp\{b+8P\tau-10^{-4}P\}=o(e^{-8P\tau}).\] 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 \[\sum_{x\in S'}z_x=\frac{n'}q\sum_{H\in Z}\lambda_H \le .001n'z/q,\] 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 (27). ◻

Proof. Batch independence raises the bounds in (42) to the \(R\)th power. Fixed zero-one multipliers cannot increase their absolute values. By (36), \[\sum_H|\delta'_H|^R\le CBe^\xi.\] For the overlap terms, (30) and dyadic summation give, for \(R>200\), \[\sum_{H\ne H'}\theta_{HH'}^R \le B^2\exp\{2\chi+O(R+\log\sigma)\}.\] 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.

Proof. Use the deterministic threshold \(z_{\min}/(10q)\). By Lemma 22, the probability that \(|T_x^*|\) exceeds it, conditional on \(\mathcal O_x\), is at most \[\exp\{-.1pP+p(b+8P\tau+O(1))\} \le e^{-.09pP}\le q^{-50}\] outside \(D_0\cup D_1\cup D_2\). By Lemma 21, 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 (39). 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 8, 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 20 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 \[O(q^{j+1}/z)\le Cn'e^{b+8P\tau}\le n e^{CP}.\] 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 23 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 \[\left(\frac{n'}{|U_S|}\right)^m.\] 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 \[c e^{-8P\tau}e^{-2qP(d_S+\log2)} \ge e^{-C_1qP(d_S+1)}.\] Choose a fixed \(C_2>C_1\) and search at most \[M=\left\lceil e^{C_2qP(d_S+1)}\right\rceil\] independent proposals, taking the first success and declaring failure if none exists. The failure probability is at most \[\exp\{-M e^{-C_1qP(d_S+1)}\} \le \exp\{-e^{(C_2-C_1)qP(d_S+1)}\} \le C e^{-cq}.\] 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 18. Lemmas 23 and 24 give the stated set, message bound, and failure probability. ◻

Completion of the description lemma. The only unresolved branch in the proof of Lemma 10 was the prepared small-cell case in projective dimension two or three. Its inputs satisfy exactly the hypotheses of Proposition 18, 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 14 invokes the now established dimension-two result. The bounded higher-dimensional projection induction of Proposition 13 then applies successively. Its validation calls use fresh tables, as stipulated in the preceding section. Hence all branches of Lemma 10 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 (49) 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 3 bounds the number of first endpoints in (50) 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 \[Cq^{-1}q^{d+1} +q^{(d-1)/2}(Cq^{d+1})^{1/2}=O(q^d).\]

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 (51). 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 \[\mathbb EH_{\theta_0}(F_U)=H(F\mid\theta_0) \ge H(F)-H(\theta_0).\] Lemma 6 and (51) consequently give \[\begin{align*} \mathbb E\bigl[(\ell-h)J_0-H_{\theta_0}(F_U)\bigr] &\le (\ell-\mathbb Eh)J_0-H(F)+H(\theta_0)\\ &\le \Lambda+O(k)+\Delta\mathbb Eh-\eta\ell\log\sigma. \end{align*}\] The terms \(d\sigma\mathbb Eh\) cancel. Dropping the last, nonpositive term gives (52) for \(U\). For any specified history, the chain rule and the coordinate caps imply \[H_{\theta_0}(F_U) \le H_{\theta_0}(F_S)+|U\setminus S|J_0.\] 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-\mathbb Eh)J_0\) combined with (51) proves (53). ◻

Proof. At a history \(h=\theta_t\), put \[\mathcal D_t(h)=|U_t|J_0-H_h(F_{U_t}),\qquad \mathcal T_t(h)=\sum_{i\in U_t}H_h(F_i)-H_h(F_{U_t}).\] Both are nonnegative. The initial subset bound gives \(\mathbb 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 \[\mathcal D_t(h) -\mathbb E[\mathcal D_{t+1}\mid h,E_t] =|E_t|J_0-H_h(F_{E_t})\ge0.\] Consequently \(\mathbb 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 \[ \mathcal T_t(h)-\mathbb E[\mathcal T_{t+1}\mid h,E_t] =\operatorname{TC}_h(F_{E_t})+ \sum_{i\in U_t\setminus E_t}I_h(F_i;F_{E_t}). \tag{59}\] 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, \[ \mathbb E\left[\sum_{i\in E_t}M_i\,\middle|\,h\right] =\frac1{n_t}\mathbb E\left[ \sum_{\substack{i\in U_t\\i\text{ in a representative block}}} M_i\,\middle|\,h\right] \le\frac1{n_t}\mathbb E\left[\sum_{i\in U_t}M_i\,\middle|\,h\right]. \tag{60}\] Combining this with (59) yields \[(1-n_t^{-1})\mathbb E\left[\sum_{i\in U_t}M_i\,\middle|\,h\right] \le \mathcal T_t(h)-\mathbb E[\mathcal T_{t+1}\mid h].\] Now average and sum over \(t<T_1\). The right-hand side telescopes and is at most \(\mathbb E\mathcal T_0\le\mathcal B\), while \(n_t\to\infty\) uniformly. Some deterministic \(t\) therefore has \(\mathbb E\sum_iM_i\le C\mathcal B/T_1\). Finally, uniform sampling gives \(\mathbb E\sum_{i\in E_t}\delta_i\le n_t^{-1}\mathbb E\sum_i\delta_i\); (60) 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 \(\mathbb P(-Z>t)\le\min\{1,Ce^{-t}\}\). Integrating this bound gives \(\mathbb EZ_-\le\log C+1\), after enlarging \(C\ge1\). Thus \(\mathbb EZ_+=L-H(X)+O(1)\). Apply this with \(L=d\sigma\) to the joint law at slot \(i\). The cheap-domain cap yields \[\mathbb E_\theta[\log(p_i(F_i)q^d)]_+\le\delta_i+O(1).\] 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, (55) also implies \[H_\theta(A_i)\ge H_\theta(F_i)-(d-r')\sigma-O(1) \ge r'\sigma-\delta_i-O(1).\] 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 7 therefore bounds the product probability of this reverse-conflict event by \(CI_{ij}\). For given endpoints \(a,y\), let \[e(a,y)=\mathbb P_{\mathrm{prod}}(c\not\perp b\mid a,y).\] 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 \(\mathbb P_\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 \[ U_j(y)\subseteq V_i(a)^\perp. \tag{66}\]

To check the rounding even when \(u_i\ne u_j\), take a common constant \(C\ge1\) in (54) and put \(e_K=\log C+3K\). Then (64) reads \[\dim V_i(a)\ge\left\lceil\frac{u_i-e_K}{\sigma}\right\rceil, \qquad \dim U_j(y)\ge\left\lceil d+1-\frac{u_j+e_K}{\sigma}\right\rceil.\] 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 (66) 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 \[ \dim V_i(a)=r,\qquad U_j(y)=V_i(a)^\perp. \tag{67}\] Let \(\Gamma_{ij}\) be the endpoint event that \(a,y\) are good and incident and satisfy (66). Define \(G_{ij}\) by additionally requiring \(b\subseteq V_i(a)\) and \(c\subseteq U_j(y)\), and put \(c_{ij}=\mathbb P_\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 \[\mathbb P_{\mathrm{prod}}(G_{ij})\ge .99^2 \mathbb P_{\mathrm{prod}}(\Gamma_{ij}).\] Applying Lemma 7 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 (65).

It remains to bound the sum of charges without treating the history-dependent rectangles as fixed in advance. On \(G_{ij}\), (63) and (67) imply \[b\subseteq V_i(a),\quad a\subseteq V_i(a)^\perp, \quad c\subseteq V_i(a)^\perp,\quad y\subseteq V_i(a).\] 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 (65). ◻

Proof. There are \(\Theta(k)\) unexposed positions, because \(T_1=o(m)\). By (56) and Lemma 26, the expected proportion violating the deficit bound is at most \[C\frac{\mathcal B/k}{D\sigma^\beta}=O(\sigma^{-2\beta}).\] Using half the second threshold for mutual information, the corresponding proportion is at most \[C\frac{q\sigma^{2000\beta}\mathcal B}{kT_1} =O(\sigma^{-1001\beta}).\] Only integer bands have nonzero collision charges. At a fixed history, uniform sampling in blocks with \(n_t=\Theta(m)\) gives \[\mathbb E\left[\sum_{i\in U}\max_{j\in\mathcal J_i}c_{ij} \,\middle|\,\theta\right] \le\frac{C}{m}\sum_{i,j\in U}c_{ij} \le\frac{C\sigma k}{m}.\] The expected proportion exceeding half the collision threshold is therefore at most \[Cq\sigma^{2000\beta}\frac{\sigma}{m} =O(\sigma^{2000\beta-\eta/2})=o(1).\] 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 (58). Each maximum over the other blocks is independent of its own block’s draw, so the same selected-index identity (60) 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, \[\frac{\delta_i+1}{K} \le \sigma^{-2\beta}+(D\sigma^{3\beta})^{-1}=o(1).\] Lemma 27 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 (Schwartz 1980; Zippel 1979): a nonzero polynomial of total degree at most \(h\) on \(\mathbb 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 \[ \ker(\mathrm{ev}_{\widetilde X}) \subseteq\ker(\mathrm{ev}_{\widetilde Y}), \qquad \operatorname{rank}(\mathrm{ev}_{\widetilde Y}) \le|\widetilde X|. \tag{70}\]

Here is a lower bound for this evaluation rank on an arbitrary nonempty set \(Z\subseteq\mathbb F_q^n\). The monomials with individual exponents less than \(q\) span all functions on \(\mathbb 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 \[\operatorname{rank}(\mathrm{ev}_Z) \ge c_d\delta^n|Z|.\] Apply this to \(Z=\widetilde Y\), combine with (70), 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 \(|\mathop{\mathrm{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 \[h=\lceil q\sigma^\beta\rceil\] 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 (55) and Lemma 27, 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 \[V_y=\mathop{\mathrm{span}}\bigl(y,\ b_t^{(1)}: a_t^{(1)}\perp y,\ 1\le t\le h\bigr).\] The decoded domain consists of all flags \((c,y)\) satisfying \[ \dim V_y=r,\qquad c\perp V_y,\qquad \#\{t:b_t^{(2)}\subseteq V_y\}\ge .1h/q. \tag{71}\] Here and below, dimensions of the spaces \(V_y\) are vector dimensions. Because \(y\subseteq V_y\), every pair allowed by (71) is indeed an incident flag.

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 \[x=\log(A_{\max,i}/|A_0|),\qquad y=\log(B_{\max,i}/|B_0|).\] These numbers are nonnegative. The reciprocal caps (54) and incidence mixing give \[e(A_0,B_0) \le Cq^d\bigl(e^{-x-y}+e^{-(x+y)/2}\bigr) \le C'q^d e^{-(x+y)/2}.\] 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 \[\mathbb E(x+y)\le C(\delta_i+\log\sigma+1).\] 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 (61) 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 11. 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 12 gives \[ \mathbb P(E_y\mid\text{readiness data}) \le Cq\frac{|X\cap N(y)|}{|X|}, \tag{78}\] 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 \[\mathbb E(L\mid\mathcal H,\mathcal S) \le Cq\frac{e(X,Y)}{|X||Y|}.\] 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 (74) 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 (78) 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 (74) 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 \[ C\varepsilon H^2+ C\sigma^{-1000\beta}H+Ce^{-cq}H=o(1). \tag{79}\]

For an actual good middle target, instead integrate (78) against its unnormalized good endpoint mass. Independence of the auxiliary construction from actual unexposed flags and (75) 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 (79) conditions on eventual survival of a descendant or target.

The expected bad-index fraction tends to zero by Proposition 29, and the bad-endpoint mass at every good index tends uniformly to zero by Lemma 27. Combining these losses with (79) 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 30. 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 32, with \(w=1\). Its cost \(O(q\sigma^{1+\beta})\) is bounded by (69), and its exponent \(O(K)\) is \(O(K_*)\). In a reciprocal class use the support construction, tree, and Lemma 34. Equations (80) and (83) give the required output budgets. The window sizes in (57) imply \[w\le C\sigma^{1+\eta/2}/D\] 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 (69), with fixed constants, as asserted. ◻

Proof of Theorem 2. Fix \(d\ge5\) and \(0<\eta<1/10\), with all the parameters of Equation (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 5. 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 \[Q_dQ_{d-1}\le4q^d\exp((d-1)\sigma).\] Thus we may take \(\Delta_0=(d-1)\sigma\). The stage parameter defined in Equation (48) is initially \[D_0=\sigma^\beta\bigl(1+(d-1)\sigma^{1-\eta}\bigr) =O(\sigma^{1-\eta+\beta}),\] 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 30, its replacement context has budgets satisfying \[ \Lambda'\le CqP\log(w+2)(\sigma+wP)+Cw\sigma, \qquad \Delta'\le CK_*, \qquad 1\le w\le C\sigma^{1+\eta/2}/D. \tag{84}\] 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 30. Using \(k\asymp q\sigma^{1+\eta}\) and \(P\le4D\sigma^{9\beta}\), the three terms to estimate satisfy \[\frac{qP\sigma}{k}\le CD\sigma^{9\beta-\eta},\qquad \frac{qP^2w}{k}\le CD\sigma^{18\beta-\eta/2},\qquad \frac{w\sigma}{k}\le\frac{Cq^{-1}\sigma^{1-\eta/2}}{D}.\] Also \(\log(w+2)=O(\log(\sigma+2))\). We obtain \[\begin{align*} \frac{\Lambda'}{k} &\le CD\log(\sigma+2) \bigl(\sigma^{9\beta-\eta} +\sigma^{18\beta-\eta/2}\bigr) +\frac{Cw\sigma}{k}\\ &\le D\sigma^{-\eta/3}. \tag{85}\end{align*}\] 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 (48) and (85) give \[\begin{align*} D_{\rm new} &=\sigma^\beta\bigl(1+\Lambda'/k+\Delta'\sigma^{-\eta}\bigr) \\ &\le\sigma^\beta +D\sigma^{\beta-\eta/3}+CD\sigma^{7\beta-\eta} \\ &\le\sigma^{2\beta}+D\sigma^{-\eta/4}. \tag{86}\end{align*}\] 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 \[\sigma^{2\beta}+\sigma^{1-3\eta/4} \le\sigma^{1-\eta/2}\] for large \(q\).

Choose the number of stages in advance, for example \(T=\lceil8/\eta\rceil\). Iterating Equation (86), and using \(D_0\le\sigma\) for large \(q\), gives \[D_T\le\sigma^{1-T\eta/4} +\frac{\sigma^{2\beta}}{1-\sigma^{-\eta/4}} \le2\sigma^{2\beta}.\] One further compression stage produces budgets \(\Lambda_*,\Delta_*\) with \[ \frac{\Lambda_*}{k} \le2\sigma^{2\beta-\eta/3}=o(1), \qquad \frac{\Delta_*q\sigma}{k} \le C\sigma^{8\beta-\eta}=o(1). \tag{87}\]

We justify explicitly the probabilistic invariants throughout this iteration. At each stage Lemma 30 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 30 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 6 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 (53) bounds the entropy of the entire tuple under its present law.

Therefore, Equation (53) from the final marking scan and Equation (87) give \[H(F_*)\le d\sigma\ell_*+\Lambda_*+O(k)+O(\Delta_*q\sigma) =d\sigma\ell_*+O(k).\] Lemma 6 gives instead \[H(F_*)\ge d\sigma\ell_*+\eta\ell_*\log\sigma-O(k).\] 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 4, as required. ◻

Proof. Define \[\vartheta(x)=\sum_{p\le x}\log p, \qquad \psi(x)=\sum_{\substack{p^h\le x\\h\ge1}}\log p,\] where \(p\) ranges over primes. Every prime in \((m,2m]\) divides \(\binom{2m}{m}\), so \[\vartheta(2m)-\vartheta(m) \le\log\binom{2m}{m}\le2m\log2.\] Summing at powers of two and then using monotonicity proves \(\vartheta(x)\le Cx\).

The exponent of \(p\) in the central binomial coefficient is \[\sum_{h\ge1} \left(\left\lfloor\frac{2m}{p^h}\right\rfloor -2\left\lfloor\frac{m}{p^h}\right\rfloor\right).\] Each summand is zero or one, and therefore \[\psi(2m)\ge\log\binom{2m}{m} \ge2m\log2-\log(2m+1).\] 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 \[0\le\psi(x)-\vartheta(x) \le C\sqrt{x}\log^2(x+2)=o(x)\] 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=\mathbb 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 \[\mathbb P(x\in I\mid\text{exposure})=\frac1{1+2^{Z_x}}, \qquad \mathbb E(|I\cap N(x)|\mid\text{exposure}) =\frac{Z_x2^{Z_x-1}}{1+2^{Z_x}}\ge\frac{Z_x}{4}.\] The last inequality includes \(Z_x=0\). Averaging also over a uniform vertex \(x\), the degree bound gives \[\frac{\mathbb EZ_x}{4} \le\frac1n\mathbb E\sum_{v\in I}\deg(v)\le D_0\mu.\] Since \((1+2^z)^{-1}\ge2^{-z}/2\) for \(z\ge0\), Jensen’s inequality now gives \[ \mu\ge\tfrac12\mathbb E2^{-Z_x} \ge\tfrac12 2^{-\mathbb EZ_x} \ge\tfrac12 2^{-4D_0\mu}. \tag{89}\] If \(\mu<\log(D_0+1)/(8(D_0+1))\), then Equation (89) 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\mathbb 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 36, 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 \[h<r(s-1,t),\qquad |N(u)\cap N(v)|\le m:=r(s-2,t)\quad(uv\in E(G)).\] 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 \[n<t(h+1)=O(t^{s-3/2}) =o\!\left(\frac{t^{s-1}}{(\log t)^{s-2}}\right).\] Assume henceforth that \(h>t^{s-5/2}\), and set \(\lambda=(hm)^{-1/2}\le1\). By the induction bound on \(m\), \[ \lambda h=\sqrt{h/m} \ge c_s t^{1/4}(\log t)^{(s-4)/2}\ge t^{1/5} \tag{90}\] 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 \[\frac{\lambda^2nh}{12\lambda h}=\frac{n\lambda}{12}, \qquad \frac{\lambda^3nhm}{6}=\frac{n\lambda}{6}.\] Some realization therefore leaves a triangle-free induced subgraph \(H\) with \[|V(H)|\ge\tfrac34n\lambda, \qquad \Delta(H)\le12\lambda h.\] Deleting further vertices cannot increase degrees, so both conclusions hold simultaneously. Lemma 36 and Equation (90) imply \[t>\alpha(H) \ge\frac{(3/4)n\lambda\log(12\lambda h+1)}{8(12\lambda h+1)} \ge c\frac{n\log t}{h}.\] 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. The lower bound follows from Equation (88) and the choice of \(\eta\) made there. Proposition 37 gives the asserted upper estimate. For every fixed \(\varepsilon>0\), its constant is eventually bounded by \((\log t)^\varepsilon\); hence \[\frac{t^{s-1}}{(\log t)^{s-2+\varepsilon}} \le r(s,t)\le \frac{t^{s-1}}{(\log t)^{s-2-\varepsilon}}\] 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\). ◻