History and contribution

Erdős and Szekeres proved the classical bound \(r(s,t)\le\binom{s+t-2}{s-1}\) (Erdős and Szekeres 1935). Ajtai, Komlós and Szemerédi improved its fixed-\(s\) order to \(O(t^{s-1}/(\log t)^{s-2})\) (Ajtai et al. 1980). Li, Rousseau and Zang subsequently obtained leading upper constant \(1+o(1)\) for fixed \(s\) (Li et al. 2001). We include an elementary proof of the upper bound with an absolute constant for \(s=5\), using uniform independent sets and random sampling.

The lower-bound problem has followed a different course. Kim proved that \(r(3,t)\) has order \(t^2/\log t\), matching the classical upper bound in order (Kim 1995). For \(s=5\), Spencer’s local-lemma method gave a lower bound of order \((t/\log t)^3\) (Spencer 1977); the analysis of the random clique-free process by Bohman and Keevash improved this to \(t^3/(\log t)^{8/3}\), up to a constant factor (Bohman and Keevash 2010, Theorem 1.2). Thus even the power of \(t\) in the upper bound remained out of reach by these methods. Finite geometry supplied a different route: Mattheus and Verstraëte proved \(r(4,t)\ge c t^3/(\log t)^4\) using a construction based on Hermitian unitals (Mattheus and Verstraëte 2024).

Bradač’s projective construction gives \[r(s,t)\ge c_s\frac{t^{s-1}}{(\log t)^{2s-4}} \qquad(s\ge3,\ t\ge2)\] (Bradač 2026, Theorem 1.1). For \(s=5\), its logarithmic exponent is \(6\). We use the ordered projective-flag graph and adapt the marking argument from Section 2.5 of that paper. The improvement here is in the analysis of long independent sequences, closing the remaining gap from exponent \(6\) to exponent \(3+o(1)\). Earlier graphs on ordered incidence pairs appear in the work of Codenotti, Pudlák and Resta and of Kostochka, Pudlák and Rödl (Codenotti et al. 2000; Kostochka et al. 2010). The distinction between steps with few choices and steps which substantially reduce the remaining choices is also central to Alon and Rödl’s independent-set counting method (Alon and Rödl 2005). Our compression must account for the extra bias created by choosing an independent sequence from a random stream.

The principal additional ingredient is a description theorem for sparse point–hyperplane pairs. If two large sets have much fewer incidences than the ambient density \(1/q\), a short message describes a moderately larger set containing a constant fraction of the smaller set. The message consists of samples selected from public random tables, together with geometric data. A score formed from several independent Poisson samples distinguishes most training points from most ambient points. Polynomial bounds for rich lines and planes control the dependencies in its high moments.

This description theorem is used inside an entropy argument. The consistent sequence selected from a random stream has a possibly highly biased law. We retain that law throughout, using conditional entropy to choose representatives and to pay for every message. A balanced tree of incidence tests successively reduces the sets available to the decoder. This separates the geometric description problem from the question of how to use its output under adaptive conditioning.

Proof overview

Fix a small \(\eta>0\) and a large prime \(q\). We construct a \(K_5\)-free graph on roughly \(q^4\log q\) positions whose independent sets have fewer than \(q(\log q)^{1+\eta}\) positions. A position receives a random incident pair \((a,b)\), where \(a\) is a point of \(\mathop{\mathrm{PG}}(4,q)\) and \(b\) is a hyperplane containing it. For positions \(i<j\), place an edge when \(a_i\) lies on \(b_j\) but \(a_j\) does not lie on \(b_i\). A five-clique would give five linearly independent points in one hyperplane.

Suppose every stream contained a long independent sequence, and select one. We call its ordered flag tuple consistent. Even after auxiliary choices and conditioning on an event of probability bounded below, each possible selected tuple is unlikely: it must occur at some set of positions in the original stream. This gives an entropy lower bound exceeding \(4\log q\) per flag by a term of order \(\eta\log\log q\).

Two marking scans give almost every flag a set of at most \(Cq^4\) joint possibilities. They also give separate bounds for its two endpoints. Revealing a small number of representative flags lowers the remaining mutual information. Consistency then has a geometric consequence: most nearly independent pairs of endpoint laws have very few incidences, except for collisions inside specific subspace rectangles. A uniform occupancy bound on the original stream controls those collisions.

The sparse-pair description theorem now applies to suitable nearly uniform parts of the endpoint laws. Its output supplies samples for fresh incidence tests. A balanced tree arranges these tests so that the total description length is small. The tests retain a constant fraction of the sequence while reducing the decoder’s available domains. A bounded number of repetitions makes the marking description shorter than the entropy lower bound, a contradiction.

Sections 2 and 3 establish the upper bound and the flag-stream framework. The sparse-pair theorem is stated in Section 4; the following compression argument proves the stream construction from it. Its proof is then given in Sections 7–10, including the finite-field geometry and the score estimates. Section 11 converts the stream parameters to Theorem 1.

Incidence estimates

For a prime power \(q\), let \(\mathcal P_d=\mathop{\mathrm{PG}}(d,q)\) be the one-dimensional subspaces of \(\mathbb F_q^{d+1}\), and let \(\mathcal P_d^*\) be its dual point space. A dual point \(b\) represents the hyperplane \(b^\perp\). We write \(a\perp b\) for incidence. In both spaces, a projective \(j\)-flat corresponds to a vector subspace of dimension \(j+1\). Put \(Q_j=1+q+\cdots+q^j\).

This projective incidence calculation is the bipartite form of the orthogonality-graph spectral calculation of Alon and Krivelevich (Alon and Krivelevich 1997, sec. 2); it also underlies Bradač’s polarity-graph estimates (Bradač 2026, Lemma 2.1). We shall use both its unweighted and weighted forms.

The ordered graph

Fix \(0<\eta<1/10\). Throughout the lower-bound proof let \(q\) be a sufficiently large prime, and put \[\beta=\eta/10^7,\qquad \sigma=\log q,\qquad N=\lfloor q^4\sigma\rfloor,\qquad k=\lfloor q\sigma^{1+\eta}\rfloor.\] The small parameter \(\beta\) is unrelated to the independence number \(\alpha(G)\). Constants may depend on \(\eta\); they never depend on \(q\). Each \(o(1)\) is uniform in the stated parameter ranges. Only a bounded number of stages, depending on \(\eta\), will be used.

A flag is a pair \((a,b)\in\mathcal P_4\times\mathcal P_4^*\) with \(a\perp b\). There are \(M=Q_4Q_3\) flags. Choose a stream \(X_1,\ldots,X_N\) of independent uniform flags. Its graph has vertex set \(\{1,\ldots,N\}\); writing \(X_i=(a_i,b_i)\), its edge rule for \(i<j\) is \[i\sim j \quad\Longleftrightarrow\quad a_i\perp b_j\ \hbox{ and }\ a_j\not\perp b_i.\] Repeated flags are permitted: the vertices are stream positions. This is the ordered version of Bradač’s \(D^*\) construction (Bradač 2026, sec. 2.5). Related earlier constructions use ordered edges of a bipartite incidence graph (Codenotti et al. 2000; Kostochka et al. 2010); the reverse nonincidence in our displayed edge rule is part of the specific construction used here.

An ordered tuple of flags is consistent if \[i<j,\ a_i\perp b_j \quad\Longrightarrow\quad a_j\perp b_i.\] Independent vertex sets give consistent tuples in stream order. Reversing the tuple and interchanging its two endpoint systems preserves consistency.

Laws of selected tuples

Entropy always means Shannon entropy with natural logarithms. For a finite-valued variable \(Y\) with masses \(p_y\), write \(H(Y)=-\sum_y p_y\log p_y\), with \(0\log0=0\). Conditional entropy \(H(Y\mid Z)\) averages this quantity over \(Z\); \(H_\theta(Y)\) denotes the entropy of the particular conditional law given \(Z=\theta\). Mutual information and total correlation are \[I(Y;Z)=H(Y)+H(Z)-H(Y,Z),\qquad \mathop{\mathrm{TC}}(Y_1,\ldots,Y_m)=\sum_iH(Y_i)-H(Y_1,\ldots,Y_m).\] We use their conditional versions with the same convention.

For probability masses \(P,Q\) on a finite set, their relative entropy is \[\mathop{\mathrm{D}}(P\Vert Q)=\sum_xP(x)\log\frac{P(x)}{Q(x)},\] with value infinity if \(P\) charges a zero of \(Q\). Direct expansion gives \[I(Y;Z)=\mathop{\mathrm{D}}(P_{Y,Z}\Vert P_Y\otimes P_Z).\] For every real function \(f\), Jensen’s inequality gives \[ \mathop{\mathrm{D}}(P\Vert Q)\ge \mathbb E_P f-\log\mathbb E_Q e^f. \tag{4}\] Indeed, apply concavity of the logarithm under \(P\) to \(e^fQ/P\); its expectation is at most \(\mathbb E_Q e^f\). In particular relative entropy is nonnegative. If \(P(E)=0\), use \(f=-s1_E\) and let \(s\to\infty\) to obtain \(\mathop{\mathrm{D}}(P\Vert Q)\ge-\log(1-Q(E))\ge Q(E)\).

We also use the following elementary concentration estimates. For a binomial or Poisson variable of mean \(\mu\), halving or doubling its mean has tail probability at most \(e^{-c\mu}\); more generally, its upper tail at \(h\ge e\mu\) is at most \((e\mu/h)^h\). For independent centered variables bounded in absolute value by one and with total variance \(V\), the two-sided tail of their sum at \(z\) is at most \[2\exp\{-c\min(z,z^2/V)\}.\] These follow from the exponential Markov inequality. For the first two bounds use \(\log\mathbb Ee^{t(X-\mu)}\le\mu(e^t-1-t)\). For the last, the Taylor expansion gives \(\mathbb Ee^{tX}\le\exp(Ct^2\mathbb EX^2)\) for centered \(|X|\le1\) and \(|t|\le1\); multiply these bounds and choose \(|t|=\min(cz/V,c)\). The zero-variance case is deterministic.

Say a stream law has density at most \(C_0\) if its probability of every stream event is at most \(C_0\) times the iid uniform stream probability. Auxiliary random choices can have arbitrary dependence on the stream; only this marginal bound is required.

Conditioning on an event of probability at least a fixed positive constant preserves stream domination, with a different constant. Fixing independent public random tables by averaging will be done before such conditioning. A fixed finite number of these operations therefore leaves Lemma 8 applicable.

To prove the lower bound, suppose every stream has a consistent \(k\)-tuple, select one deterministically, and condition on the event of Lemma 7. The compression argument starts from this law. Every subsequent retained tuple will have deterministic length \(\Theta(k)\), satisfy the same rectangle bound, and have a stream law with bounded density. Its entropy must consequently retain the excess \(\eta\ell\log\sigma\).

Two marking scans

Counting ordered independent sets by steps with few options or a large reduction in the remaining domain goes back to Alon and Rödl (Alon and Rödl 2005, Theorem 2.1 and Lemma 2.2). The following scan adapts the marking argument of Bradač (Bradač 2026, Claim 2.13), freezing its state between expensive steps and recording its joint option counts for later entropy estimates.

The masks also give useful separate endpoint bounds. At a slot that is poor-cheap in at least one orientation, fix such an orientation by a priority rule and put \(u=\max(\sigma,\min(4\sigma,\log|Z_l|))\). Its endpoint supports have sizes at most \[ A_{\max}=Ce^{5\sigma-u},\qquad B_{\max}=Ce^u. \tag{10}\] The clamping uses the trivial ambient bound \(Q_4=O(q^4)\) at the two endpoints. If the slot is popular-cheap in both scans, with forward and reversed ranks \(r,r'\), its endpoint caps and partner caps are as follows. Here \(|B\mid A|\) is the largest number of permitted second endpoints for a fixed first endpoint, and \(|A\mid B|\) is defined symmetrically: \[ |A|\le Cq^{r'},\quad |B|\le Cq^r,\qquad |B\mid A|\le2q^{4-r'},\quad |A\mid B|\le2q^{4-r}. \tag{11}\] In a high class we use \(A_{\max}=Cq^{r'}\) and \(B_{\max}=Cq^r\). For \(r+r'\le5\), these imply (10) with \(u=r\sigma\). Rank zero cannot be popular.

We divide the remaining positions into a fixed number of classes. Reciprocal classes specify their orientation and either an integer band \(|u-r\sigma|\le K_*\), with \(r\in\{1,2,3,4\}\), or an open band \[(r-1)\sigma+K_*<u<r\sigma-K_*.\] For open bands \(r\in\{2,3,4\}\). The remaining, high classes specify \((r,r')\) with \(r+r'>5\); whenever a rank is four, orient the class so that \(r=4\). By pigeonholing, an event determined by \(\theta_0\) and of probability bounded below has a fixed class containing at least \(c k\) positions. Condition on that event and retain the first \(\lfloor c k\rfloor\) positions. Conditional laws at a fixed \(\theta_0\) have not changed, and (9) changes only by a constant factor. The deterministic parameters \(D,K,K_*\) remain those chosen at the start of the stage. Conditioning here multiplies the expected deficit bound by at most the reciprocal of a fixed positive probability, which is absorbed in its stage constant. It does not redefine \(D\) from the entropy of the conditioned old context. The next stage will instead use the deterministic message-length bound for its newly constructed context. If the orientation is swapped, reverse the retained order as well. All subsequent lengths are deterministic.

Split this class into equal windows, discarding the final remainder. Let \(w\) be the resulting deterministic number of complete windows, before any subsequent deletions. Take window length, rounded to a multiple of four, of order \[ m\asymp \begin{cases} qD\sigma^{\eta/2},&\text{open bands},\\ q\sigma^{1+\eta/2},&\text{integer bands}. \end{cases} \tag{12}\] A high class uses one window of length \(\Theta(k)\). The early and late quarters of each window are representative blocks; the middle half consists of targets. In every case \(\Theta(k)\) positions remain.

Choosing a round before exposing its values

Conditioning to reduce correlations is a standard entropy method; compare (Raghavendra and Tan 2011, Lemma 4.5). We need the following version with one representative per block.

In the following estimates, conditional entropies and mutual information are evaluated at the indicated history. The outer expectation averages over that history and all fresh representative indices.

Low-conflict pairs and collision rectangles

All conditional probabilities in this subsection are given a fixed pre-round history \(\theta\). For a flag \((a,b)\) at slot \(i\), denote its joint and endpoint marginal probabilities by \(p_i(a,b)\), \(p_i^A(a)\), and \(p_i^B(b)\). Call a first endpoint \(a\) good if \[p_i^A(a)\ge e^{-K}/A_{\max}\quad\text{and}\quad \Pr\bigl(p_i(a,b)>q^{-4}e^K\mid a\bigr)\le .02;\] define good second endpoints symmetrically. In a high class impose also the upper cutoffs \[p_i^A(a)\le e^Kq^{-r'},\qquad p_i^B(b)\le e^Kq^{-r}.\] The mass of bad endpoints at slot \(i\) is \[ O\bigl(e^{-K}+(\delta_i+1)/K\bigr). \tag{15}\] Indeed, the negative part of \(\log(p_i(F_i)q^4)\) has bounded expectation by the support cap \(C_1q^4\), so its positive part has expectation at most \(\delta_i+O(1)\). Markov’s inequality proves the light-atom condition. The lower cutoff loses at most \(e^{-K}\). For the high upper cutoff, the partner cap gives \(H_\theta(A_i)\ge r'\sigma-\delta_i-O(1)\), and the same negative-part argument with the marginal cap \(Cq^{r'}\) applies; similarly for \(B_i\).

Fix \(\rho=.005\). For a first endpoint \(a\) define a vector subspace in the second system by \[\mathcal K_i(a)= \bigcap_{\Pr(b\not\perp z\mid a)\le\rho} z^\perp.\] Define \(\mathcal L_j(y)\) in the first system by the analogous construction from the conditional first endpoint at second endpoint \(y\). A basis of the span of the tests has at most five members; hence \[ \Pr(b\in\mathcal K_i(a)\mid a)\ge1-5\rho, \qquad a\perp\mathcal K_i(a), \tag{16}\] with the analogous assertions for \(\mathcal L_j(y)\). At a good \(a\), a captured light conditional atom is at most \(q^{-4}e^{2K}A_{\max}\), and these atoms have total mass at least \(.955\). Counting points in a vector subspace therefore gives \[ \dim\mathcal K_i(a)\ge \left\lceil5-\frac{\log A_{\max}+3K}{\sigma}\right\rceil, \tag{17}\] and the corresponding bound using \(B_{\max}\) for \(\mathcal L_j(y)\).

Extend \(c_{ij}\) symmetrically, setting it to zero in the other high classes. For a fresh target \(i\), put \[g_i=\max_{j\in\mathcal J_i}(I_{ij}+c_{ij}).\] Call the index good if \[ \delta_i\le D\sigma^\beta,\qquad g_i\le\sigma^{-2000\beta}/q. \tag{20}\] The expected fractions of bad indices and bad representatives are \(o(1)\). For mutual information use Lemma 11 and \(\mathcal B/k=O(D\sigma^{-\beta})\). For collisions, uniform block sampling and (18) give expected total at most \(C\sigma k/m\); collision windows have \(m\ge cq\sigma^{1+\eta/2}\), so Markov loses at most \(C\sigma^{2000\beta-\eta/2}=o(1)\). Selection in a target’s own block is independent of its other-block sum, giving the representative estimate as before. At every good index, (15) is \(o(1)\).

Eliminating high classes

Nearly uniform endpoint supports

Only reciprocal classes remain. Their endpoint caps are (10), with a history-known number \(u_i\) at each slot.

Discard windows with a bad representative. In an open band discard also windows with \(u_{\rm early}-u_{\rm late}>K_*\). Along the remaining ordered representative list before this last deletion, the sum of downward changes is at most \(C\sigma+CKw\), by (21). Thus these extra deletions cost at most \(C(\sigma+Kw)/K_*=o(w)\) windows, since \(w\asymp\sigma^{1+\eta/2}/D\). In an integer band the variation is already at most \(2K_*\).

At every surviving window independently choose a permissible first support \(A\) from its early representative and a permissible second support \(B\) from its late representative. Then \[ |A||B|\ge q^5e^{-CK_*}. \tag{22}\] For the same window and every ordered cross pair, expected incidence density is at most \(C\sigma^{-2000\beta}/q\). The same bound holds against the corresponding good endpoint mass of every good middle target on the appropriate temporal side. These are averaged statements over the independent support choices; no pointwise sparsity of every chosen pair is being assumed. They are precisely the inputs for the tree construction in the next section.

A fresh incidence test

For points \(x,y\) in opposite systems write \(x\in N(y)\) when \(x\perp y\). Given a row \(x_1,\ldots,x_h\) in one system, its fresh ambient test is \[ \mathcal T(x_1,\ldots,x_h) =\left\{y:\sum_{j=1}^h1_{\{x_j\perp y\}}<\frac{.2h}{q}\right\}. \tag{23}\] The word “ambient” means that this set is defined on the entire opposite point system, before intersection with an inherited domain.

The tree construction and loss accounting

The surviving window list is determined by the pre-round history and the fresh representative indices: all its deletions use only the numbers \(\delta_i,g_i,u_i\). Fix this list before making the independent level choices. Build a balanced binary tree on it from Section 5: its root is the middle window, and recurse on the earlier and later halves. Each node has its original supports \(A,B\) from Lemma 14. Its inherited sets \(U_A,U_B\) initially equal the two full point systems. At a successful node, the left child inherits the new first-endpoint cap and the old second-endpoint cap; the right child inherits the old first-endpoint cap and the new second-endpoint cap. Middle targets of the pivot window use both new caps. Figure 1 records these different roles.

At a node, trim \(A\) and \(B\) to their inherited sets. Drop its entire subtree if either trim keeps fewer than \(.9\) of its original support, or if the untrimmed same-node density exceeds \(\sigma^{-1000\beta}/q\). Otherwise, the trimmed supports satisfy Theorem 9 in dimension four, with \(b=O(K_*)\). Apply the predictor in the orientation of the smaller support and then Lemma 15, exchanging the two systems if necessary. Drop the subtree on failure. Use independent tables for each tree address, stage, predictor call and validation test.

The new decoder and its message length

The encoder transmits the tree size and node statuses, successful node constructions, and the retained slot count at each node in tree order. The parameters \(q,\eta,D,L,R,P\) and the deterministic stage budgets are part of the common protocol. At each successful node the message also specifies its orientation, trimmed support sizes, row lengths and row indices, together with the predictor’s diagnostics. These integers cost \(O(\sigma)\) per node apart from the already charged row indices. No failed construction is transmitted. Starting with the two ambient point systems, the decoder reconstructs every successful ancestor’s caps and therefore the inherited sets for each successful child. The predictor’s message supplies its set \(W\); row sizes and row indices supply the two validation tests. A proposal row is regenerated using public uniforms ranked in the decoder’s reconstructed finite domain. The hidden supports determine acceptance, but are not needed to regenerate an accepted row. Concatenating the prescribed number of copies of the pivot domains in the windows’ original order specifies all new slot domains. The decoder never needs the old context, the old slot labels, or the identities of the omitted targets.

We can now state the full compression step established by the two sections.

The finite iteration

Small sets and greedy removal of flats

Orient the input so that \(n=|S|\le|T|\), and put \(n=q^{1+v}\). Lemma 5 gives \(n\le Cq^{(d+1)/2}\). If \(n\le100qP\), send \(n\) and the rank of \(S\) among the \(n\)-element subsets of the known set \(U_S\). The elementary inequality \(\binom{|U_S|}{n}\le(e|U_S|/n)^n\) bounds the message length by \[O\bigl(\sigma+n(d_S+1)\bigr) \le CqP(d_S+P).\] The decoder takes \(W=S\). Henceforth \(n>100qP\), so \(v>0\).

Define \[g_0=(v-\tfrac12)\sigma,\qquad g_1=(v-1)\sigma,\qquad \xi=L/100,\qquad \chi=P/100,\qquad \chi_0=P/10000.\] The following two greedy procedures refer to the original value of \(n\), including in their thresholds.

1. If \(d=4\) and \(g_1>\chi_0\), repeatedly choose a hyperplane containing the largest number of remaining points of \(S\). Remove its remaining points whenever this number is at least \(q^2\). Stop as soon as at least \(n/2\) points have been removed, or when the maximum is below \(q^2\). In the first case retain the removed points and their ordered list of hyperplanes. In the second retain the residual and no list. If the procedure is not used, retain all of \(S\). Call the retained set \(S_1\).

2. If \(d\ge3\) and \(g_0>\chi_0\), apply the same rule to planes and the points of \(S_1\), now with threshold \[K_p=n^{4/3}q^{-1}\exp(-g_0/5).\] Stop on removing at least \(|S_1|/2\), or when the largest remaining plane count is below \(K_p\). Retain the removed points and the ordered plane list in the first case, and the residual with no plane list in the second. If this procedure is not used, retain \(S_1\). Write \(S'\) for the final training set and \(n'=|S'|\).

Ties are resolved by a fixed ordering of flats. Each retained list partitions the training points by earliest membership: a point belongs to the first listed flat containing it. The hyperplane partition, if present, is restricted to \(S'\) after the second procedure. The sizes of the original hyperplane cells, before that restriction, will also be used in the geometric analysis; they are not needed by the decoder.

A large cell reduces the dimension

Suppose a training cell has at least \(.04n'\) points. Its listed flat \(K_0\), of projective dimension \(2\le j<d\), satisfies \[S_0=S\cap K_0,\qquad |S_0|\ge .01n.\] The encoder sends \(K_0\), with a canonical coordinate system. The average incidence proportion from \(T\) into \(S_0\) is at most \(100\tau/q\). Delete members whose proportion exceeds \(\sqrt\tau/q\). This loses at most \(100\sqrt\tau\,|T|\) members, so leaves at least \(|T|/2\) for large \(q\). Each remaining covector restricts nontrivially to \(K_0\).

Normalize each nonzero projective restriction. Each restriction has at most \(q^{d-j}\) projective lifts: after fixing one nonzero restricted coordinate to be \(1\), the remaining \(d-j\) coordinates are free. Among the dyads \([l,2l)\) of lift multiplicity, choose one carrying at least \(|T|/(C\sigma)\) of the retained lift mass. Let \(T_0\) be its set of distinct restrictions. Then \[ |S_0||T_0|\ge q^{j+1}\exp\{-b-O(\log\sigma)\}, \qquad \frac{e(S_0,T_0)}{|S_0||T_0|}\le\frac{\sqrt\tau}{q}. \tag{30}\] Indeed, the number of restrictions is at least the retained mass divided by \(2l\), and \(l\le q^{d-j}\). The density assertion holds for each restriction separately, so forgetting its multiplicity causes no problem.

The decoder’s enclosures are \[U_{S_0}=U_S\cap K_0,\qquad U_{T_0}=\{\text{nonzero projective restrictions with at least \(l\) lifts in \(U_T\)}\}.\] Their logarithmic gaps are bounded by \(d_S+O(1)\) and \(d_T+O(\log\sigma)\). The extra term in \(b\) in (30) is absorbed in \(O(D\sigma^{6\beta})\). Moreover, \[\sqrt\tau\le \sigma^{-200\cdot2^{j-2}\beta}\qquad(j<d).\] Thus the induction hypothesis applies after orienting the reduced pair so that its smaller side is first. The dimension decreases, and its initial value is at most four.

If the recursive output captures \(S_0\), it already captures a constant fraction of \(S\) in a set of size at most \(ne^{CP}\). Intersect it with \(U_S\), if necessary. If instead it captures \(T_0\), let \(W_0\) be the decoded set and \(C_0=W_0\cap T_0\) its hidden capture, with \(|C_0|\ge c|T_0|\) and \(|W_0|/|C_0|\le e^{CP}\). We convert this to a capture on the original side.

Take \(h=\lceil Cq(d_S+1)\rceil\) independent uniform samples from \(C_0\), temporarily using the true hidden-set law. On \(U_S\cap K_0\) define the cap \[W=\{x:\text{fewer than } .2h/q \text{ of the sampled restrictions annihilate }x\}.\] By Lemma 5, at most \(C'q^{j+1}/|T_0|\) points in the whole \(j\)-space have incidence proportion less than \(.5/q\) into \(C_0\). Every other point belongs to \(W\) with probability at most \(\exp(-ch/q)\). The bounds \[|U_S\cap K_0|\le e^{d_S}n,\qquad n\le Cq^{j+1}/|T_0|\] therefore imply, by increasing \(C\) and applying Markov’s inequality, that \[|W|\le C''q^{j+1}/|T_0| \le n\exp\{O(b+\log\sigma+1)\}\] with probability at least \(.9\). The second displayed inequality for \(n\) follows by applying mixing to \(S_0,T_0\) and using \(|S_0|\ge .01n\).

Every member of \(T_0\) has incidence proportion at most \(\sqrt\tau/q\) into \(S_0\). Consequently every all-in-\(C_0\) sample row, regardless of its bias, loses at most \(5\sqrt\tau\,|S_0|\) points of \(S_0\) under this test: sum the hit counts and divide by the rejection threshold. Thus a row satisfying the size test also captures at least \(.9|S_0|\) for large \(q\).

To implement this sampling with a message, send the integer \(h\) and use a fresh table indexed by this row length. Its \(O(\sigma)\)-bit cost is absorbed in the bounds below. Propose independent rows uniform in the known \(W_0\). A row falls entirely in \(C_0\) and passes the size test with probability at least \(.9e^{-ChP}\). Searching at most \(\exp(C'hP)\) rows gives failure probability \(O(e^{-cq})\), and its row index takes \(O(hP)\) bits. Conditional on being all in \(C_0\), a proposed row is exactly iid uniform in \(C_0\); the comparison is made before searching. After search, no unbiased-sampling assertion is used.

The flat, dyad, recursive message, row length and optional conversion have total length \(O(qP(d_S+d_T+P))\). Here the recursive increases of \(O(\log\sigma)\) in the gaps are absorbed because \(\log\sigma=o(P)\). There are at most two dimension reductions, and each uses fresh tables. The constants and failure probabilities can therefore be absorbed in those of Theorem 9.

We have reduced the proof to training data satisfying the small-cell case of Lemma 20. The next section bounds the rich radial configurations that can correlate incidence tests at one query point. Those bounds will be applied separately to validation on \(S'\) and to output size in the ambient space.

A polynomial bound for rich lines

We first prove the only algebraic ingredient. Its characteristic restriction will enter through a polynomial whose degree is less than \(q\).

The overlap estimate

We now return to the training set. To keep the geometric statement independent of the score, the hyperplanes below can be any family of bounded training density.

Empty exceptional hyperplanes

The incidence variance identity gives \[ \sum_H(\lambda_{H,C}-f_C)^2\le CqBf_C, \qquad \sum_H(\lambda_H-1)^2\le CqB. \tag{48}\] Replacing the exact means by \(f_C\) and one changes only a negligible term, since \(qp_d=1-1/Q_d\). Summing the first estimate over the three partition systems, then using the thresholds in (44), gives \[ |\mathcal E|\le CqB,\qquad \sum_{H\in\mathcal E}\lambda_H\le CqB. \tag{49}\] For the second assertion, use Cauchy–Schwarz and the full-set variance in (48).

We call a pencil regular if it contains at most \(Be^\xi\) members of \(\mathcal E\), and if the pencil sum of each clipped squared deviation in (48) is at most \(Be^\xi\). Here clipping replaces a squared deviation \(u^2\) by \(\min\{1,u^2\}\). Only \(o(n)\) centers have an irregular pencil. Indeed, a clipped weight \(w_H\in[0,1]\) has \(\sum_Hw_H\le CqBf_C\) and \(\sum_Hw_H^2\le\sum_Hw_H\). Applying incidence variance in the opposite direction gives a total pencil variance at most \(Cq^dBf_C\), with mean \(O(Bf_C)\). Chebyshev’s inequality bounds its exceptional centers by \(Cn'e^{-2\xi}f_C\). Sum this bound using \(\sum_Cf_C\le3\); the full-set and exceptional-set indicator estimates have the same proof. This argument pays for the number of cells through their total mass, not their cardinality.

Poisson splitting makes the sample counts at different point–batch pairs independent. The average of \(\lambda_H\) over \(H\in T\) is at most \(4\tau\). Thus there is a fixed \(T_0\subseteq T\) with \(|T_0|\ge|T|/2\) and \(\lambda_H\le8\tau\) for every \(H\in T_0\). For large \(q\), these hyperplanes lie in \(\mathcal E\), and the product-size assumption gives \(|T_0|\ge cqBe^{-b}\). If \(Y\) counts the members of \(T_0\) empty in all batches, then \[\mathbb EY\ge |T_0|e^{-8P\tau},\qquad 0\le Y\le |T_0|.\] The second bound, rather than independence of empty-hyperplane events, yields \[ \mathbb P\{z\ge z_{\min}\}\ge\tfrac12e^{-8P\tau}, \qquad z_{\min}=cqB e^{-b-8P\tau}. \tag{50}\] Here and below decrease the absolute constant \(c\) if necessary.

We may require at the same time \[ \sum_{H\in Z}\lambda_H\le .001z. \tag{51}\] The terms with \(\lambda_H\le10^{-4}\) contribute at most \(10^{-4}z\). For the others, (49) gives expected contribution at most \(CqBe^{-10^{-4}P}\). Markov’s inequality at \(.0009z_{\min}\) fails with probability at most \(Ce^{b+8P\tau-10^{-4}P}=o(e^{-8P\tau})\), by (47).

For each resulting \(Z\), incidence variance shows that \[ z_x\ge .8z/q \quad\hbox{outside at most }Cq^{d+1}/z\hbox{ ambient points}. \tag{52}\] On the training set, \[\sum_{x\in S'}z_x=\frac{n'}q\sum_{H\in Z}\lambda_H\le .001n'z/q.\] Consequently at least \(.99n'\) training points satisfy \(z_x\le .1z/q\).

The exceptional part of the score equals \((1-b_0)^Rz_x\), with error in absolute value at most \(b_0|\mathcal E\cap\{H:H\ni x\}|\). For a member of \(Z\) every factor is \(1-b_0\). For any other exceptional hyperplane, either an own hit makes its product zero or an outside-own hit supplies a factor \(-b_0\); every other factor has magnitude at most one. At a regular pencil the error is at most \(Be^{-.91L}=o(z_{\min}/q)\), and \((1-b_0)^R=1-o(1)\). It remains to control the sum \(T_x\) over the nonexceptional hyperplanes. This is the only probabilistic issue left in separating the two bounds on \(z_x\).

The second moment on training points

Fix \(x\). The schedule of a point or direction is the vector of its sample counts in the \(R\) batches. Condition first on \(x\) being unsampled and then on the schedules of all points of \(O_x\setminus\{x\}\). The own-empty multipliers in (45) are now fixed zeros or ones. All remaining point counts are still independent Poisson variables. Group them by their radial lines \(\ell\) through \(x\), with strengths \[a_\ell=\frac q{n'}|\ell\cap(S'\setminus(O_x\cup\{x\}))|.\] A line has a hit in a specified batch with probability \(1-e^{-La_\ell}\). For a typical hyperplane put \[\lambda'_H=\sum_{\ell\subset H}a_\ell,\qquad \delta'_H=\lambda'_H-(1-f),\qquad \theta_{HH'}=\sum_{\ell\subset H\cap H'}a_\ell.\] The union defining \(O_x\) uses two cells minus their intersection. The exceptional thresholds therefore give \[ \lambda'_H\ge .75,\qquad |\delta'_H|\le .17,\qquad D_x:=\sum_{H\text{ typical}}(\delta'_H)^2\le CBe^\xi \tag{53}\] at a regular pencil. The last bound follows by summing the relevant clipped squares. Removing \(x\) contributes at most \(O(q^{d-1}(q/n')^2)=O(B)\), since \(n'\ge n/4>25qP\). Also \(\lambda'_H\le\lambda_H\le1.1\), so the geometric input applies.

Temporarily omit the fixed own multiplier and write the one-batch term as \[X_H=\mathbf1\{H\text{ is outside-own empty}\}-b_0.\] Then \[u_H:=\mathbb EX_H=e^{-L\lambda'_H}-b_0, \qquad |u_H|\le Le^{-.75L}|\delta'_H|,\] and for distinct \(H,H'\), \[\mathbb EX_HX_{H'}=u_Hu_{H'}+ e^{-L(\lambda'_H+\lambda'_{H'})}(e^{L\theta_{HH'}}-1).\] Since \(\lambda'_H+\lambda'_{H'}-\theta_{HH'}\ge .75\), \[ |\mathbb EX_HX_{H'}|\le L^2e^{-.75L} (|\delta'_H\delta'_{H'}|+\theta_{HH'}), \qquad \mathbb EX_H^2\le2e^{-.75L}. \tag{54}\] The fixed multipliers can only reduce the absolute bounds. More precisely, after the own schedules are fixed, the full product for a hyperplane is either identically zero or has all its own-empty multipliers equal to one. Thus they do not alter the signed cancellation used below.

In dimension two the overlaps vanish. In higher dimensions, (46) and dyadic summation give \[\sum_{H\ne H'}\theta_{HH'}^R \le B^2\exp(2\chi+O(R+\log\sigma)).\] For the deviation terms, \(R\ge2\) and \(|\delta'_H|<1\) give \(\sum_{H,H'}|\delta'_H\delta'_{H'}|^R\le D_x^2\). Finally \(Q_{d-1}=O(B^2)\), because \(n'\le n\le Cq^{(d+1)/2}\). Summing (54) to the \(R\)-th power and using (47) proves \[ \mathbb ET_x^2\le B^2e^{-.6P}. \tag{55}\] This estimate is uniform in the conditioned own schedules. It holds at all centers except the \(o(n)\) pencil and geometric exceptions; it uses none of the additional ambient exclusions.

In dimension two, different pencil lines have disjoint outside-\(x\) samples. Thus their score terms are independent under the same conditioning. Their variance sum is at most \(Cqe^{-.6P}\), and their mean is at most \(Be^{-cP}\), by the one-batch mean bound and \(D_x\). Bernstein’s inequality gives \[ \mathbb P\{|T_x|>z_{\min}/(10q)\}\le q^{-50}. \tag{56}\] Indeed \(B\ge c\sqrt q\), \(P=o(\sigma)\), and \(e^{cP}\gg\sigma\). This settles the ambient tail in dimension two. The next subsection treats dimensions three and four, where pencil tests share radial lines.

An ambient moment bound

Choose the even moment order \(p\) above, and put \(K_c=200\), \(J=5000\). If \(g_1>\chi_0\), let \(\mathcal G_x\) be the event that every outside-own radial line hits in fewer than \(J\) batches. Otherwise \(\mathcal G_x\) is the whole sample space. In the high case a line of strength \(a\) violates the condition with probability at most \((2Pa)^J\). The global geometric line bound and the maximum strength \(Ce^{-g_1}\) give, after summing the dyads above \(e^{-.05g_0}\), \[\sum_x\mathbb P(\mathcal G_x^c) \le Cq^2P^J e^{-(J-2)g_1+O(J)+O(\log\sigma)}+o(n)\le n.\] For the lower dyads, the elementary bound of \(Cq^7\) center–line pairs in dimensions at most four contributes at most \(Cq^7(CPe^{-.05g_0})^J=o(n)\); here \(g_0>.5\sigma\). These are probabilities under the fixed-point conditioning, uniformly in the own schedules.

We prove, at every remaining ambient center, \[ \mathbb E\bigl[T_x^p\mathbf1_{\mathcal G_x}\bigr] \le B^p e^{-.1pP}. \tag{57}\] Expand the power into ordered \(p\)-tuples of typical hyperplanes. Join two distinct tuple hyperplanes when their overlap exceeds \(t=1/(100p)\). A component is a connected component of this graph. A simple singleton is an isolated hyperplane occurring in exactly one tuple position. A positive-strength radial direction is external if it is contained in hyperplanes from two different components. A batch touches a hyperplane when it has a hit on an external direction contained in that hyperplane. Thus sharing a direction always means containing that radial line, not merely intersecting it at \(x\). The total external mass in any tuple hyperplane is at most \((p-1)t<.01\): sum its overlap with tuple hyperplanes in other components.

Condition on all external schedules. Internal schedules belonging to different components are independent. Directions contained in no tuple hyperplane contribute an independent truncation probability at most one, which can be omitted from the absolute expectation bound. The remaining truncation condition splits into its external condition and one internal condition per component. The internal mass in every hyperplane is at least \(.74\). In a batch with no external hit the expected absolute value of its factor is at most \(2e^{-.74L}\). If there is an external hit the factor has magnitude \(b_0\le e^{-.92L}\). A component containing two distinct hyperplanes, or a singleton repeated in the tuple, consequently costs at most \[ e^{-.7P}. \tag{58}\] To see this, keep only the absolute factors of one of its hyperplanes; all other absolute factors are at most one. Drop its internal truncation and multiply the one-batch bounds. This bound is uniform in the external schedules.

For a simple singleton \(H\), let \(\theta_{\max}\) be its largest overlap with another tuple hyperplane, or zero if there is none. The external mass is at most \(p\theta_{\max}\le .01\). In an untouched batch its signed mean has magnitude at most \(Le^{-.74L}(|\delta'_H|+p\theta_{\max})\); a touched batch has factor \(-b_0\). If fewer than half the batches are touched, the product of means is therefore bounded in absolute value by \[ e^{-.68P}\bigl(|\delta'_H|^{R/2}+ (p\theta_{\max})^{K_c}\bigr). \tag{59}\] Here \((CL)^R=e^{o(P)}\), and \(R/2\ge K_c\). If at least half are touched, the bound is instead \(e^{-.68P}\mathbf1_{\mathrm{BAD}(H)}\), where \(\mathrm{BAD}(H)\) denotes this condition on the external schedules.

Internal truncation adds to (59) at most \[ e^{-.68P}\sum_{\ell\subset H}(Pa_\ell)^J. \tag{60}\] For a direct verification, union over a line with hits in \(J\) specified batches. Each forced batch has score factor \(-b_0\) and probability at most \(La_\ell\). Every remaining batch has absolute expectation at most \(2e^{-.74L}\). Summing the choices of forced batches gives \((Pa_\ell)^J\) while retaining the displayed attenuation. Thus no independence conditional on the truncation event is being asserted.

We can now designate each simple singleton as a deviation, shift, truncation-error or BAD term according to these bounds. The first three have respective weights \[|\delta'_H|^{R/2},\qquad (p\theta_{\max})^{K_c},\qquad \sum_{\ell\subset H}(Pa_\ell)^J;\] the last has its BAD indicator. The truncation-error designation is absent when \(g_1\le\chi_0\), since \(\mathcal G_x\) is then the whole space. Every simple position retains \(e^{-.68P}\), including positions whose additional weight will be dropped in the counting below.

Simultaneous capture and size

We finish the proof of Lemma 24 under the original sampling law. All fixed-point estimates above were conditional on the point being unsampled and uniform in its own schedules. Multiplying by the probability that it is unsampled and then averaging the own schedules makes them unconditional upper bounds for failures at unsampled points. Sampled points are included automatically.

The deterministic pencil and local geometry exceptions contain \(o(n)\) points. On the training set, the second moment (55) gives expected typical-score failures at most \(n'e^{-cP}\). Markov’s inequality shows that more than \(.01n'\) such failures has probability \(e^{-c'P}\), which is negligible relative to \(e^{-8P\tau}\). This validation estimate does not discard the additional \(ne^{O(P)}\) ambient centers.

For the ambient size estimate, those additional centers may all be included. Beyond all static exceptions, (65), (56), and the bound on \(\sum_x\mathbb P(\mathcal G_x^c)\) show that the expected number of dynamic failures is \(O(n+1)\). Markov’s inequality permits at most \(ne^{CP}\) of them, except with probability \(e^{-cP}\), again negligible relative to (50). The total Poisson sample count has mean \(qP\) and exceeds \(2qP\) with probability \(e^{-cqP}\).

Intersect these events with (50) and (51). Their probability is at least \(ce^{-8P\tau}\). At least \(.99n'\) training points have \(z_x\le .1z/q\); after the \(o(n)\) static exceptions and the validation failures, a fixed positive fraction have score below \(.5z/q\) or are sampled. They belong to \(W\). Outside the ambient exceptions, \(z_x\ge .8z/q\), the exceptional-score error is \(o(z/q)\), and the typical score has magnitude at most \(z/(10q)\). Such unsampled points have score above \(.5z/q\) and are excluded.

Finally, the \(Z\)-dependent ambient exception in (52) has size \[Cq^{d+1}/z\le Cn'e^{b+8P\tau}\le ne^{CP}.\] The at most \(2qP\) sampled points, all other ambient exceptions and dynamic failures satisfy the same size allowance. Thus \(|W|\le ne^{CP}\) and \(|W\cap S'|\ge cn'\) simultaneously on a set of rows of probability at least \(\exp[-C(P\tau+1)]\), proving the lemma.