A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
A counterexample to Ryser's covering conjecture
expertly designed by an internal OpenAI model · released 2026-09-23
· original PDF
IntroductionA vertex cover of a finite hypergraph \(H\) is a set of vertices meeting every edge. Its covering number \(\tau(H)\) is the minimum size of such a set, and its matching number \(\nu(H)\) is the maximum number of pairwise disjoint edges. For an integer \(r\ge2\), an \(r\)-partite \(r\)-uniform hypergraph has disjoint vertex parts \(V_1,\ldots,V_r\), with every edge containing exactly one vertex from each part. Ryser’s covering conjecture asserts that every such hypergraph satisfies \[ \tau(H)\le(r-1)\nu(H). \tag{1}\] A nonempty hypergraph is intersecting when every two distinct edges meet; equivalently, its matching number is one. In this case the conjecture asks for a cover of size at most \(r-1\). The vertices of a cover may lie in several different parts, which is the central obstacle in constructing a counterexample. For \(r=2\), inequality (1) is Kőnig’s matching theorem. An equivalent formulation appears in Henderson’s 1971 thesis (Henderson 1971); Best and Wanless discuss the history of its attribution to Ryser (Best and Wanless 2018). Aharoni proved the full tripartite case (Aharoni 2001). In the intersecting case, the results through rank four are due to Gyárfás, and the rank-five result to Tuza, as recorded by Király and Tóthmérész (Király and Tóthmérész 2017); see also Tuza’s early study of the covering conjecture (Tuza 1983). Haxell and Scott proved \(\tau(H)\le(r-\epsilon)\nu(H)\) for some \(\epsilon>0\) when \(r=4\) or \(5\), without assuming intersection (Haxell and Scott 2012). White proved the particular rank-four case \(\nu(H)=2\), obtaining \(\tau(H)\le6\) (White 2026).1 Under the additional assumption that any two distinct edges meet in exactly one vertex, Francetić, Herke, McKay, and Wanless established the intersecting case through rank nine (Francetić et al. 2017). Bishnoi, Das, Morris, and Szabó obtained bounds when every pair of edges has a larger prescribed intersection (Bishnoi et al. 2021). Finite planes supply the classical equality examples. Delete a point and all lines through it from a projective plane of order \(q\). Partition the remaining points according to the deleted line through them, and take the remaining lines as hyperedges. The result is intersecting, has \(q+1\) parts and covering number \(q\). Thus equality in the proposed bound occurs whenever \(r-1\) is a prime power. Work of Mansour, Song, and Yuster (Mansour et al. 2009) and Aharoni, Barát, and Wanless (Aharoni et al. 2016) studies the structure and sparsity of equality examples. Abu-Khazneh, Barát, Pokrovskiy, and Szabó exploit the rigidity of minimum covers in a truncated plane and add exceptional edges to obtain further equality examples (Abu-Khazneh et al. 2019). In that construction, the number of parts and the covering number both increase by one. Haxell and Scott combine affine planes with intersecting configurations to obtain covering number at least \(r-4\) for every sufficiently large \(r\), improved to \(r-3\) when \(r\) is even (Haxell and Scott 2017). Our construction also starts from a finite plane and inserts exceptional edges, but keeps one part for each ambient direction. It changes the line labels within these parts to raise the covering number beyond \(q\). The following theorem gives the precise field orders for which this can be done. Theorem 1. There exists \(s_0\) such that, for every prime \(s\ge s_0\) with \(s\equiv2\pmod3\), there is an integer \(n_0(s)\ge3\) with the following property. For every odd integer \(n\ge n_0(s)\), put \(q=s^n\). There is a finite intersecting \((q+1)\)-partite \((q+1)\)-uniform hypergraph \(H\) satisfying \[\tau(H)=q+1.\] In particular, the intersecting case of (1) is false. Every edge of a nonempty intersecting hypergraph is itself a cover, so the assertion \(\tau(H)\le q+1\) is automatic. The proof must construct an intersecting hypergraph and exclude every cover of size at most \(q\). We first fix any sufficiently large eligible prime \(s\), construct a configuration in \(\mathbb F_s^2\), and then take \(n\) sufficiently large among the odd integers. All subsequent thresholds may depend on that fixed configuration. The result is asymptotic; the proof does not give a numerical threshold. A companion paper (OpenAI 2026) proves a different theorem: for every sufficiently large prime \(q\), it constructs such a hypergraph with exactly \(q+1\) vertices in every part and with every vertex nonisolated. Its construction modifies line partitions directly in the prime plane. Here the field order is a proper odd power, and the proof uses a small-field configuration with a nonlinear change of coordinates. The two constructions give distinct ranges of ranks. The only results imported from the companion are its three elementary estimates in Appendix A: the affine second-moment identity (Lemma A.1), bounded-drift concentration (Lemma A.2), and the exposure bound for independent trials (Lemma A.3). Lovász proposed the stronger assertion that deleting \(r-1\) vertices can always reduce the matching number. Clow, Haxell, and Mohar disproved that assertion at \(r=3\) (Clow et al. 2026); Abiad, Garbe, Povill, and Spiegel subsequently gave an infinite family at \(r=3\) and examples at \(r=4\) (Abiad et al. 2025). These examples are consistent with (1). They exclude a prescribed matching-reduction procedure, whereas Theorem 1 violates the covering inequality itself. Monochromatic tree coversAn \(r\)-edge-coloring here assigns exactly one of \(r\) colors to each edge. A monochromatic tree cover is a family of monochromatic trees whose vertex sets cover the graph; the trees may overlap, and singleton trees are allowed. Gyárfás’s conjecture asks whether \(r-1\) such trees suffice for every \(r\)-edge-colored complete graph; see (Milićević 2017, Conjecture 1). This is the covering formulation recorded after Theorem 2 in (Erdős et al. 1991, sec. 3), not the distinct vertex-disjoint tree-partition conjecture numbered Conjecture 2 there. Corollary 2. Let \(s_0\) and \(n_0(s)\) be as in Theorem 1. For every prime \(s\ge s_0\) with \(s\equiv2\pmod3\) and every odd integer \(n\ge n_0(s)\), put \(r=s^n+1\). There is a finite simple complete graph with an \(r\)-edge-coloring for which the minimum number of monochromatic trees needed to cover its vertices is exactly \(r\). The same minimum holds with connected monochromatic subgraphs or maximal monochromatic components in place of trees. Proof. Take the hypergraph \(H\) from Theorem 1, with parts \(V_1,\ldots,V_r\). For \(e\in E(H)\), let \(x_i(e)\) be the unique vertex in \(e\cap V_i\). Form the complete graph \(K\) with vertex set \(E(H)\). For each pair of distinct hyperedges \(e,f\), choose one index \(i\) with \(x_i(e)=x_i(f)\) and color the edge \(ef\) by \(i\). Such an index exists because \(H\) is intersecting. Only one color is chosen even when the two hyperedges meet in several parts. Along a color-\(i\) path, the value of \(x_i\) is constant. Thus every connected color-\(i\) subgraph determines a vertex of \(V_i\) belonging to every hyperedge indexed by that subgraph. For a singleton, choose any color and the corresponding vertex of its hyperedge. If \(t\) connected monochromatic subgraphs cover the vertices of \(K\), the at most \(t\) hypergraph vertices so chosen meet every edge of \(H\). Hence \(t\ge\tau(H)=r\). Conversely, fix a vertex of \(K\). The \(r\) monochromatic stars centered there, one for each color and allowing singleton stars, cover all vertices of \(K\). They give a tree cover of size at most \(r\). The lower bound applies to trees and to maximal monochromatic components as well, and the stars can be enlarged to maximal components. This proves all three stated minima. ◻ Thus Gyárfás’s cover conjecture fails at these extension-field ranks. The examples admit no cover by \(r-1\) connected monochromatic subgraphs even without a diameter restriction. They therefore also refute Milićević’s bounded-diameter strengthening (Milićević 2017, Conjecture 6), whose diameter bound may depend on \(r\), and the \(\alpha=1\) case of the conjecture of DeBiasio, Kamel, McCourt, and Sheats (DeBiasio et al. 2021, Conjecture 2.8), whose diameter bound depends only on the independence number \(\alpha\). Indeed, \(\alpha(K)=1\), so the latter conjecture also demands a cover by at most \(r-1\) such subgraphs. Proof strategyIn the affine-plane model, the parts are indexed by the \(q+1\) directions in \(\mathbb F_q^2\), and the vertices of a part are the \(q\) lines of that direction. A point \(x\) defines an edge consisting of its incident line in each direction. The edges of two points intersect at their join, but a full parallel class always gives a cover of size \(q\). We retain many of these point edges and add exceptional edges whose labels are changed in some directions. The construction has three tasks: preserve intersection, restrict small covers of the retained point edges, and make the exceptional edges too costly for those covers. Restricting the ordinary cover.Delete a bounded number of translated shapes in each of \(O(q)\) independent trials. The shapes are lines or curves that meet every line in boundedly many points. Thus a shape has bounded intersection with a line unless it is that line itself. Section 3 proves that, under explicit uniform survival assumptions, every cover of almost all surviving points by at most \(q\) lines contains almost a pencil. Here a pencil is a family of lines through one projective point, including a parallel class when that point is at infinity. Surviving points on each nondeleted line then force every nondeleted member of this pencil into the cover. To obtain the pencil statement over the required extension fields, Section 2 first proves an incidence saving by the sum–product method of Bourgain, Katz, and Tao (Bourgain et al. 2004). Its constants are uniform over fields whose proper subfields all have order at most \(q^{1/3}\). One configuration in two coordinates.In a fixed prime plane \(\mathbb F_s^2\), remove one line in each finite nonzero direction and call the remaining set \(Y\). The change of coordinates \(f(x,y)=(x^3,y)\) is bijective when \(s\equiv2\pmod3\). Original line labels determine which ambient point edges must be deleted to intersect the exceptional edges. The labels for altered directions are instead read from the lines through \(f(w)\), for \(w\in Y\). The map \(f\) preserves the horizontal and vertical parallel classes; this ensures intersection within the exceptional configuration. Its nonlinear action on the other lines makes their images curves with at most three intersections with any line. Applying the deletion lemma in these new coordinates yields the crucial obstruction: covering \(f(Y)\) by \(a\) lines and \(b\) individual points with \(a+b/2\le s\) requires exactly one full parallel class and no point resources. Section 5 proves this statement together with the ordinary-coordinate occupancy needed later. Placing the configurations and spending the cover budget.Embed linearly transformed copies of \(Y\) in \(\mathbb F_q^2\) so that every ambient direction is altered in one or two copies. Arbitrary translates could create disjoint exceptional edges. We therefore sample a fixed number of independent candidate translates for each copy. Section 4 proves that one can choose compatible representatives from these pools, using an independent-transversal argument in the tradition of Haxell (Haxell 1995, 2001). Section 6 proves the deletion estimates for the entire independent pool before making this selection. Keeping only the selected deletions restores ordinary points, so the needed estimates transfer by deterministic inclusion. Section 7 gives the labels of every edge, proves intersection, and excludes a cover of size at most \(q\). After the ordinary edges force a pencil, its center determines the remaining argument. At infinity, the uncovered exceptional configurations require more vertices than the missing parallel lines release. Inside an embedded configuration, the remaining budget would cover \(f(Y)\) by at most \(s\) lines including two nonparallel axis lines. Outside every configuration, each deleted pencil line supplies five uncovered exceptional edges, while every additional vertex covers at most five. In all three cases the available budget is too small. Conventions.A direction is a one-dimensional linear subspace of \(\mathbb F_q^2\); as a subspace it includes zero. The projective completion adds one point at infinity per direction. A pencil consists of the affine lines through a projective point: it has \(q+1\) members for a finite center and \(q\) members for a center at infinity. Thus concurrence always includes parallel lines. For a positive integer \(j\), write \((a)_j=a(a-1)\cdots(a-j+1)\). All asymptotic constants may depend on the parameters explicitly held fixed. An event holds with high probability if its probability tends to one along the specified sequence of fields. The small field is fixed before the ambient field tends to infinity. A uniform incidence boundFor a set \(P\) of points and a set \(\mathcal L\) of lines in \(\mathbb P^2(\mathbb F_q)\), write \[ I(P,\mathcal L) =\bigl|\{(p,\ell)\in P\times\mathcal L:p\in\ell\}\bigr|. \tag{2}\] Our aim is a power saving with constants independent of the field and its characteristic. In Section 3, this estimate will control intersections of a proposed line cover when no projective point lies on many of its lines. This is the incidence input to the conclusion that a small cover must contain almost a full pencil. Theorem 3 (Uniform incidence saving). There exist absolute constants \(\kappa\in(0,1/10)\) and \(Q\) with the following property. Suppose that \(q\ge Q\) is a prime power and every proper subfield of \(\mathbb F_q\) has order at most \(q^{1/3}\). If \(P\) and \(\mathcal L\) are sets of projective points and projective lines over \(\mathbb F_q\) satisfying \[ |P|,|\mathcal L|\le q^{1+\kappa}, \tag{3}\] then \[ I(P,\mathcal L)\le q^{3/2-\kappa}. \tag{4}\] The proof follows the incidence and sum–product strategy of Bourgain, Katz, and Tao (Bourgain et al. 2004, secs. 3–4 and 6). Its geometric step turns an incidence configuration with too many incidences into a dense set of pairs whose differences and quotients range over small sets. A graph argument then extracts one subset with both a small difference set and a small quotient set. Finally, scalar coverings show that such a subset cannot have size near the square root of the field order under the proper-subfield hypothesis. We develop the two algebraic ingredients first, then return to the incidence configuration. The proofs include the simultaneous extraction of additive and multiplicative control and the bounds on scalar expressions that make the argument uniform over fields of nonprime order. Finite-set estimatesThe first task is to pass from control of differences and quotients along the edges of a dense bipartite graph to control on all pairs in one subset. We begin with the sumset estimates needed to use the resulting additive control. For subsets of an abelian group, \(X+Y\) and \(X-Y\) denote the usual sumset and difference set. For a nonnegative integer \(j\), the notation \(jY\) in this subsection means a sum of \(j\) copies of \(Y\), with \(0Y=\{0\}\). Later, a field element multiplying a set will always mean field scaling; we will specify explicitly when an integer denotes an iterated sumset. The first two estimates below are Ruzsa’s triangle inequality and covering lemma; the maximal-translates proof of the latter appears in (Ruzsa 1999, 324). The multiple-sum bound is a Plünnecke–Ruzsa estimate, for which we use Petridis’s minimizing-subset proof (Petridis 2012, Proposition 2.1 and Section 3). Lemma 4 (Triangle, covering, and multiple-sum estimates). Let the sets below be finite subsets of an abelian group.
Proof. For the triangle inequality, choose one representation \(d=x_d-y_d\) for each \(d\in X-Y\). The map \[(d,z)\longmapsto (x_d-z,z-y_d)\] from \((X-Y)\times Z\) into \((X-Z)\times(Z-Y)\) is injective: summing the two coordinates recovers \(d\), after which the chosen representation recovers \(z\). This proves (5). For the covering statement, take a maximal set \(T\subseteq X\) for which the translates \(t-Y\), \(t\in T\), are pairwise disjoint. Their union is contained in \(X-Y\), so \(|T|\le M\). Maximality implies that for every \(x\in X\) some \(x-Y\) intersects \(t-Y\) with \(t\in T\), whence \(x\in t+(Y-Y)\). For the multiple-sum bound, the minimizing-subset argument of Petridis (Petridis 2012) lets us iterate a one-step growth estimate. Put \(Q_0=-Y\) and choose a nonempty \(W\subseteq Y\) minimizing \[\mu=\frac{|W+Q_0|}{|W|}.\] Then \(\mu\le M\), and every \(W'\subseteq W\), including the empty set, satisfies \(|W'+Q_0|\ge\mu|W'|\). We claim that for every finite set \(E_0\), \[ |W+Q_0+E_0|\le\mu|W+E_0|. \tag{7}\] The assertion is immediate if \(E_0\) is empty. Otherwise order its elements as \(e_1,\ldots,e_k\). When the translate \(W+e_i\) is added to the preceding translates, let \[W_i'=\{w\in W:w+e_i\in\bigcup_{j<i}(W+e_j)\}.\] It contributes exactly \(|W|-|W_i'|\) new elements. Moreover, \(W_i'+Q_0+e_i\) is contained in the union of the preceding enlarged translates \(W+Q_0+e_j\). Thus the contribution of \(W+Q_0+e_i\) is at most \[|W+Q_0|-|W_i'+Q_0| \le\mu\bigl(|W|-|W_i'|\bigr).\] Summing proves (7). Iterating this estimate gives \(|W+jQ_0|\le\mu^j|W|\) for every nonnegative integer \(j\). We now remove the auxiliary set \(W\) by applying (5) to \(uQ_0,vQ_0\) with intermediate set \(-W\): \[|uQ_0-vQ_0|\,|W| \le |W+uQ_0|\,|W+vQ_0| \le\mu^{u+v}|W|^2.\] Negation preserves cardinality, so \(|uQ_0-vQ_0|=|uY-vY|\). Since \(|W|\le|Y|\) and \(\mu\le M\), this is (6). ◻ We next carry out the extraction from a dense graph. The argument uses the common-neighborhood method in Gowers’s quantitative refinement (Gowers 1998, sec. 4, Lemma 11 and Proposition 12) of the Balog–Szemerédi theorem (Balog and Szemerédi 1994); see also (Fox and Sudakov 2011, sec. 5, Lemmas 5.1–5.2). The point is to use the same walks for both additive and multiplicative edge labels. We can therefore obtain both bounds on one subset, which is what the subsequent subfield argument requires. In the geometric application, the edge labels will come from the four pencils through four chosen points. Lemma 5 (Simultaneous difference and quotient extraction). Let \(F\) be a field, let \(A,B\subseteq F^*\) be finite, and let \(G\subseteq A\times B\). Define \[D=\{a-b:(a,b)\in G\},\qquad J=\{a/b:(a,b)\in G\}.\] Suppose that, for real numbers \(n>0\) and \(V\ge2\), \[ |A|,|B|,|D|,|J|\le Vn, \qquad |G|\ge n^2/V. \tag{8}\] Then there is \(S\subseteq A\) such that \[ \frac{3n}{8V^2}\le |S|\le Vn \tag{9}\] and \[ |S-S|,|S/S|\le 2^{20}V^{22}n. \tag{10}\] Here \(S/S=\{a/a':a,a'\in S\}\). Proof. We first find a large set of vertices such that every ordered pair is joined by many walks of length four. Counting the possible edge labels of these walks will then bound both differences and quotients of the endpoints. Regard \(G\) as a bipartite graph, and put \(\tau=(512V^8)^{-1}\). Call an ordered pair \((a,a_2)\in A^2\) bad if it has fewer than \(\tau n\) common neighbors in \(B\). To find a neighborhood with few bad pairs, first note that vertices of \(B\) with fewer than \(n/(2V^2)\) neighbors account for at most \(|B|n/(2V^2)\le n^2/(2V)\) edges. Since every vertex of \(B\) has at most \(Vn\) neighbors, the set of vertices with at least \(n/(2V^2)\) neighbors has size at least \(n/(2V^2)\). Summed over all \(b\in B\), the number of bad ordered pairs in the neighborhood of \(b\) is at most \[|A|^2\tau n\le V^2\tau n^3.\] Averaging over the large neighborhoods just identified, one obtains a neighborhood \(A_0\) of size at least \(n/(2V^2)\) in which the number of bad ordered pairs is at most \[2V^4\tau n^2=\frac{n^2}{256V^4} \le \frac{|A_0|^2}{64} \le \frac{|A_0|^2}{16}.\] Let \(S\) consist of those \(a\in A_0\) having at most \(|A_0|/4\) bad partners in \(A_0\). At most \(|A_0|/4\) elements are discarded, so \(|S|\ge3|A_0|/4\), proving (9). The choice of \(S\) ensures that, for every \(a,a'\in S\), at least \(|A_0|/2\) elements \(a_2\in A_0\) form nonbad pairs with both endpoints. Each such \(a_2\) gives at least \((\tau n)^2\) ordered walks \[a,b_1,a_2,b_2,a'\] whose four edges belong to \(G\). Repeated vertices are allowed. Consequently each ordered endpoint pair in \(S^2\) has at least \[ \frac{|A_0|}{2}(\tau n)^2 \ge\frac{n^3}{2^{20}V^{18}} \tag{11}\] such walks. This lower bound now converts the limited number of edge labels into a bound on endpoint differences. For one of these walks, write its edge differences, always taking the \(A\) coordinate minus the \(B\) coordinate, as \[d_1=a-b_1,\quad d_2=a_2-b_1,\quad d_3=a_2-b_2,\quad d_4=a'-b_2.\] They satisfy \(a-a'=d_1-d_2+d_3-d_4\). For a fixed endpoint pair, the four differences determine the walk uniquely: starting from \(a\), one recovers successively \(b_1,a_2,b_2,a'\). Choose one ordered endpoint pair for each element of \(S-S\). The resulting collections of difference quadruples are disjoint for different differences, because their alternating sums differ. Counting in \(D^4\) and using (11) gives \[|S-S|\le \frac{|D|^4}{n^3/(2^{20}V^{18})} \le 2^{20}V^{22}n.\] The same walks give the quotient bound on the same set \(S\). Put \[j_1=a/b_1,\quad j_2=a_2/b_1,\quad j_3=a_2/b_2,\quad j_4=a'/b_2.\] All are nonzero, and \(a/a'=j_1j_3/(j_2j_4)\). From a fixed initial \(a\) and these four quotients one recovers \(b_1=a/j_1\), \(a_2=j_2b_1\), \(b_2=a_2/j_3\), and \(a'=j_4b_2\). Choosing one endpoint pair for each element of \(S/S\) and counting in \(J^4\) therefore proves the other bound in (10). ◻ Bounded scalar expressions and subfieldsWe now turn to the algebraic obstruction: a set near the square-root field scale cannot have both the small difference set and the small quotient set supplied by the extraction lemma. The first step is to bound sums involving scalars formed using a bounded number of field operations. We use the scalar-covering method of Bourgain, Katz, and Tao (Bourgain et al. 2004, Lemma 3.2 and Proposition 3.3), keeping the dependence on the number of operations explicit. An expression in a set \(E\subseteq F\) is built from members of \(E\cup\{0,1\}\) using binary addition, subtraction, and multiplication, and unary negation and inversion. Each of these operations counts as one operation. Inversion is allowed only when its argument is nonzero. Lemma 6 (Uniform scalar coverings). Let \(B\) be a nonempty finite subset of a field \(F\), let \(E\subseteq B\), and let \(K\ge2\). Suppose that \[ |B-B|\le K|B|, \qquad |B-eB|\le 2K^3|B|\quad(e\in E). \tag{12}\] Define \[ C_0=4,\qquad C_{m+1}=3C_m+5, \qquad\text{so that }C_m=\frac{13\cdot3^m-5}{2}. \tag{13}\] If \(\lambda\in F\) has an expression in \(E\) using at most \(m\) operations, then \(\lambda B\) is contained in at most \(K^{C_m}\) translates of \(B-B\). In particular, \[ |E+\lambda E|\le |B+\lambda B| \le K^{C_m+3}|B|. \tag{14}\] These bounds are uniform over all such expressions and all choices of their entries from \(E\). Proof. Put \(H=B-B\), so \(H=-H\) and \(0\in H\). In the remainder of this proof, integer multiples of \(B\) or \(H\) inside sumsets denote iterated sums. We prove the covering assertion by induction on expression length. To combine coverings at an induction step, we will need a fixed covering of \(2H\) by translates of \(H\). By Lemma 4, \[|2H-B|=|2B-3B|\le K^5|B|.\] The covering statement of that lemma consequently supplies a set \(T_*\subseteq F\) with \(|T_*|\le K^5\) such that \[ 2H\subseteq T_*+H. \tag{15}\] Every \(e\in E\) has a covering \(eB\subseteq T_e+H\) with \(|T_e|\le2K^3\le K^4\), by (12) and the covering lemma. The scalars \(0\) and \(1\) also have coverings by one translate of \(H\): use \(\{0\}\subseteq H\) and \(B\subseteq b_0+H\) for any \(b_0\in B\). This proves the case \(m=0\). We now check how the number of translates changes under each allowed operation. Suppose that \[\lambda B\subseteq T+H,\qquad \mu B\subseteq U+H,\qquad |T|\le K^a,\quad |U|\le K^b.\] Negation replaces \(T\) by \(-T\). For addition and subtraction, \[(\lambda\pm\mu)B \subseteq \lambda B\pm\mu B \subseteq T\pm U+2H \subseteq T\pm U+T_*+H,\] so the number of translates is at most \(K^{a+b+5}\). For a product, \[\lambda\mu B \subseteq \lambda U+\lambda H =\lambda U+(\lambda B-\lambda B) \subseteq\lambda U+T-T+T_*+H.\] This uses at most \(K^{b+2a+5}\) translates and is valid even if \(\lambda=0\). Finally, if \(\lambda\ne0\), then \[|\lambda B-B| \le |T|\,|H-B| =|T|\,|B-2B| \le K^{a+3}|B|.\] Scaling by \(\lambda^{-1}\) and then negating gives \(|\lambda^{-1}B-B|\le K^{a+3}|B|\). The covering lemma now covers \(\lambda^{-1}B\) by at most \(K^{a+3}\) translates of \(H\). These bounds give the claimed uniform induction: in an expression with at most \(m+1\) operations, each immediate subexpression has at most \(m\) operations, so every resulting covering uses at most \(K^{3C_m+5}\) translates. This proves the covering assertion with (13). To deduce the sumset bound from the covering, let \(\lambda B\subseteq T+H\) be the covering just obtained. Then \[|B+\lambda B| \le |T|\,|B+H| =|T|\,|2B-B| \le K^{C_m+3}|B|,\] again by Lemma 4. Since \(E\subseteq B\), this also bounds \(|E+\lambda E|\). ◻ When working along a sequence \(q\to\infty\), a positive quantity \(K=q^{o(1)}\) means that \(\log K/\log q\to0\). Likewise, \(|S|=q^{1/2+o(1)}\) means that \(\log|S|/\log q\to1/2\). In particular, every fixed power of a subpower factor is still a subpower factor. This is why a uniform bound for expressions of fixed length suffices for the next lemma. Lemma 7 (Exclusion of an intermediate approximate subfield). There is no sequence of prime powers \(q\to\infty\), each satisfying the proper-subfield hypothesis of Theorem 3, together with sets \(S\subseteq\mathbb F_q^*\) and numbers \(K\ge2\) such that \[ |S|=q^{1/2+o(1)},\qquad K=q^{o(1)},\qquad |S-S|,|S/S|\le K|S|. \tag{16}\] Proof. Suppose that such a sequence exists. We first use multiplicative overlaps to obtain sets satisfying the scalar-covering hypotheses. Ratios of differences in a large subset will then form a subfield. The proper-subfield hypothesis will force that subfield to be the whole field, where averaging will contradict the scalar-covering bound. Extracting scalar-covering hypotheses.Put \(s=|S|\). The \(s\) sets \(S/a\), \(a\in S\), each have size \(s\), and their union is contained in \(S/S\). Cauchy–Schwarz gives \[ \sum_{a,b\in S}|S/a\cap S/b| \ge\frac{s^4}{|S/S|}\ge\frac{s^3}{K}. \tag{17}\] Thus some \(b\in S\) satisfies \(\sum_{a\in S}|S/a\cap S/b|\ge s^2/K\). Since every summand is at most \(s\), at least \(s/(2K)\) values \(a\in S\) have \(|S/a\cap S/b|\ge s/(2K)\): otherwise the sum of the large summands would be less than \(s^2/(2K)\) and that of all the other summands at most \(s^2/(2K)\). Let \(E\) be the set of \(e=a/b\) for these values of \(a\), and put \(B=S/b\). Then \[ E\subseteq B,\qquad |B|=s,\qquad |E|\ge\frac{s}{2K},\qquad |S\cap eS|\ge\frac{s}{2K}\quad(e\in E). \tag{18}\] The last inequality follows by multiplying \(S/a\cap S/b\) by \(a\). For \(Z=S\cap eS\), the triangle inequality and the containments \(Z\subseteq S,eS\) imply \[|S-eS| \le\frac{|S-Z|\,|Z-eS|}{|Z|} \le\frac{(Ks)^2}{s/(2K)}=2K^3s.\] After scaling by \(1/b\), we have \[|B-B|\le Ks,\qquad |B-eB|\le2K^3s\quad(e\in E).\] Thus Lemma 6 applies to \(B\) and \(E\). We have obtained uniform control for every scalar expressible using a bounded number of operations on elements of \(E\). Ratios of differences form a subfield.Write \(t=|E|\). By (18) and (16), \(t=q^{1/2+o(1)}\). In particular, \(t\ge2\) for all sufficiently large fields in the sequence. Define \[ R_0=\left\{\frac{x-x'}{y-y'}: x,x',y,y'\in E,\ y\ne y'\right\}. \tag{19}\] To prove closure under addition and multiplication, we apply the scalar-covering bound to the result of either operation. Every member of \(R_0\) has an expression in \(E\) with at most four operations. Consequently, for \(r,r'\in R_0\), each of \(r+r'\) and \(rr'\) has an expression with at most nine operations. For either candidate \(\lambda\), Lemma 6 gives \[|E+\lambda E|\le K^{C_9+3}s<t^2\] for all sufficiently large \(q\), uniformly over \(r,r'\). Indeed, the ratio of this upper bound to \(t^2\) is at most \(4K^{C_9+5}/s\), which tends to zero. Therefore the map \((x,y)\mapsto x+\lambda y\) from \(E^2\) is not injective. A collision between distinct pairs satisfies \(y\ne y'\), since otherwise also \(x=x'\), and gives \[\lambda=\frac{x'-x}{y-y'}\in R_0.\] It follows that \(R_0\) is closed under addition and multiplication. It contains \(0\) and \(1\) and, directly from its definition, is closed under negation and reciprocals of nonzero elements. Thus \(R_0\) is a subfield of \(\mathbb F_q\). The size of \(E\) now prevents this subfield from being proper. Choose distinct \(e_0,e_1\in E\). The map \[e\longmapsto\frac{e-e_0}{e_1-e_0}\] injects \(E\) into \(R_0\), so \(|R_0|\ge t>q^{1/3}\) for large \(q\). The proper-subfield hypothesis forces \(R_0=\mathbb F_q\). A scalar with a large sumset.Every field element consequently has a four-operation representation using elements of \(E\). The scalar-covering estimate therefore bounds \(|E+\lambda E|\) for every scalar. To reach a contradiction, we average over the field and find a scalar for which this sumset is too large. For \(\lambda\in\mathbb F_q\), let \(N_\lambda\) be the number of ordered quadruples \((x,y,x',y')\in E^4\) satisfying \(x+\lambda y=x'+\lambda y'\). There are \(t^2\) identical pairs, which give a collision for every \(\lambda\). If \(y\ne y'\), exactly one value of \(\lambda\) gives a collision; if \(y=y'\) but \(x\ne x'\), none does. Hence \[ \frac1q\sum_{\lambda\in\mathbb F_q}N_\lambda =t^2+\frac{t^4-t^3}{q} \le t^2+\frac{t^4}{q}. \tag{20}\] For some \(\lambda\), Cauchy–Schwarz applied to the fibers of \((x,y)\mapsto x+\lambda y\) therefore yields \[ |E+\lambda E| \ge\frac{t^4}{t^2+t^4/q} \ge\frac12\min(t^2,q) =q^{1-o(1)}. \tag{21}\] But \(R_0=\mathbb F_q\), so this particular \(\lambda\) itself has a four-operation representation in (19). Lemma 6 bounds its sumset by \(K^{C_4+3}s=q^{1/2+o(1)}\), contradicting (21). The expression length here remains bounded; no iteration of field generation is being used. ◻ Proof of the incidence theoremThe algebraic ingredients are now in place. It remains to obtain the hypotheses of Lemma 5 from a configuration with too many incidences. We use the projective-coordinate reduction in the incidence strategy of Bourgain, Katz, and Tao (Bourgain et al. 2004, sec. 6): after controlling degrees, we choose four points whose pencils encode the two coordinates, their difference, and their quotient. Proof of Theorem 3. We argue by contradiction, allowing all quantitative losses to be subpower factors along a sequence of fields. Suppose the theorem is false. For a sequence of positive exponents \(\kappa_j\to0\) in \((0,1/10)\), choose admissible counterexamples with \(q_j\to\infty\). Such choices are possible because the failure of the theorem says that for each fixed exponent there are arbitrarily large counterexamples. Along this sequence, put \(U=\max(2,q_j^{\kappa_j})\) and suppress the index \(j\). We have \[ |P|,|\mathcal L|\le Uq,\qquad I(P,\mathcal L)\ge\frac{q^{3/2}}{U},\qquad U\ge2,\qquad U=q^{o(1)}. \tag{22}\] All bounds below use absolute constants. Every assertion made for sufficiently large \(q\) is along this sequence. Our goal is to construct from these counterexamples sets of the size and small-expansion form excluded by Lemma 7. Pruning the incidence graph.We first retain many incidences while putting both an upper and a lower bound on every remaining degree. Consider the bipartite graph on \(P\) and \(\mathcal L\) whose edges are incidences. If \(d(v)\) denotes a degree on either side, then counting ordered pairs on the opposite side and using the unique join of two distinct projective points, or the unique intersection of two distinct projective lines, gives \[ \sum_v d(v)^2\le2U^2q^2 \quad\text{on each side}. \tag{23}\] Here \(\sum_vd(v)(d(v)-1)\le U^2q^2\), and \(\sum_vd(v)=I(P,\mathcal L)\le U^2q^2\). Set \[ H=16U^3q^{1/2},\qquad d=\frac{q^{1/2}}{8U^2}. \tag{24}\] Delete every vertex whose initial degree exceeds \(H\). By (23), the total number of incidences lost, counting both sides, is at most \[\frac{4U^2q^2}{H}=\frac{q^{3/2}}{4U}.\] Next, iteratively delete vertices whose current degree is less than \(d\). Each of the at most \(2Uq\) original vertices is deleted at most once, so this stage loses at most \(2Uq\,d=q^{3/2}/(4U)\) incidences. Denote the surviving sets again by \(P,\mathcal L\). They satisfy \[ I(P,\mathcal L)\ge\frac{q^{3/2}}{2U},\qquad \frac{q}{32U^4}\le |P|,|\mathcal L|\le Uq, \qquad d\le d(v)\le H. \tag{25}\] The size lower bounds follow by dividing the surviving incidence count by the maximum degree \(H\). The pruning also controls the intersection of \(P\) with every projective line, including lines not in \(\mathcal L\). We will need this stronger form of control when discarding points on a few lines chosen later. Fix a projective line \(\ell\). Each point of \(P\cap\ell\) is incident with at least \(d-1\) lines of \(\mathcal L\) different from \(\ell\). These lines are distinct for different points of \(P\cap\ell\). Since \(d\to\infty\), for large \(q\) we obtain \[ |P\cap\ell| \le\frac{|\mathcal L|}{d-1} \le16U^3q^{1/2}=H \qquad\text{for every projective line }\ell. \tag{26}\] Four anchors with many common witnesses.We seek four points, three collinear and the fourth off their line, together with many points joined to each of them by lines of \(\mathcal L\). We obtain the four points by first counting such configurations around each possible common point and then averaging. For \(x\in P\), let \(N(x)\) consist of the points in \(P\setminus\{x\}\) joined to \(x\) by a line of \(\mathcal L\). Distinct lines through \(x\) have disjoint point sets away from \(x\), so \[ |N(x)|\ge d(d-1)\ge\frac{q}{128U^4} \tag{27}\] for large \(q\). Put \(t_\ell=|N(x)\cap\ell|\). Summing degrees of the points of \(N(x)\) gives \[\sum_{\ell\in\mathcal L}t_\ell \ge d|N(x)|\ge\frac{q^{3/2}}{1024U^6}.\] Lines with \(t_\ell\le2\) contribute at most \(2Uq\). Because \(U=q^{o(1)}\), for sufficiently large \(q\) this is at most half of the displayed lower bound. Consequently \[\sum_{\ell:t_\ell\ge3}t_\ell \ge\frac{q^{3/2}}{2048U^6}.\] For every integer \(t\ge3\), one has \(t(t-1)(t-2)\ge(2/9)t^3\). Hölder’s inequality therefore shows that the number of ordered triples of distinct points of \(N(x)\) lying on a line of \(\mathcal L\) is at least \[ \begin{split} \sum_{\ell\in\mathcal L}t_\ell(t_\ell-1)(t_\ell-2) &\ge\frac{2}{9|\mathcal L|^2} \left(\sum_{\ell:t_\ell\ge3}t_\ell\right)^3\\ &\ge\frac{q^{5/2}}{9\cdot2^{32}U^{20}}. \end{split} \tag{28}\] By (26) and (27), each such triple admits at least \[\frac{q}{128U^4}-H\ge\frac{q}{256U^4}\] choices of a fourth point in \(N(x)\) outside its line, once \(q\) is large enough. Summing over \(x\) and using (25), we obtain at least \[ \frac{q^{9/2}}{9\cdot2^{45}U^{28}} \tag{29}\] ordered choices \((x,p_1,p_2,p_3,p_4)\) with \(p_1,p_2,p_3\) distinct and collinear on a line of \(\mathcal L\), with \(p_4\) outside that line, and with all four \(p_i\) in \(N(x)\). We now reverse the count to fix the four anchor points while retaining many choices of the common point \(x\). The number of possible ordered quadruples \((p_1,p_2,p_3,p_4)\) in this count is at most \[ |\mathcal L|H^3|P| \le2^{12}U^{11}q^{7/2}. \tag{30}\] Some quadruple thus has at least \[ c_0\frac{q}{U^{39}} \quad\text{witnesses }x,\qquad c_0=\frac1{9\cdot2^{57}}. \tag{31}\] Discard the witnesses on the common line of \(p_1,p_2,p_3\) and on the joins of \(p_1,p_4\) and of \(p_2,p_4\). The cap (26) discards at most \(3H\) witnesses. Since \(U=q^{o(1)}\), this is eventually less than \(c_0q/(2U^{39})\). At least that many witnesses remain. Their joins to the four anchors will supply the graph and the four small sets required by Lemma 5. The four pencils as coordinates.Choose projective coordinates in which \[p_1=(1:0:0),\qquad p_2=(0:1:0),\qquad p_3=(1:1:0),\qquad p_4=(0:0:1).\] This is possible over \(\mathbb F_q\): representatives of \(p_1,p_2\) span their line, the representative of the distinct third point has both coefficients nonzero and permits rescaling of the first two, and a representative of \(p_4\) completes a basis. The discarded lines are precisely the coordinate line at infinity and the two coordinate axes through \(p_4\). Hence every remaining witness has coordinates \((a:b:1)\) with \(a,b\ne0\). Let \(G\) be the set of these pairs \((a,b)\), and let \(A,B\) be its coordinate projections. Define \(D\) and \(J\) from \(G\) as in Lemma 5. The chosen coordinates make the roles of the four pencils explicit: for a witness \((a:b:1)\), the joins to \(p_2,p_1,p_3,p_4\), respectively, have equations \[X=aZ,\qquad Y=bZ,\qquad X-Y=(a-b)Z,\qquad X=(a/b)Y.\] Each join is a member of \(\mathcal L\), by the witness property. Each anchor belongs to \(P\) and has degree at most \(H\). Distinct values of the corresponding parameter give distinct lines in its pencil. Thus \[|A|,|B|,|D|,|J|\le H, \qquad |G|\ge\frac{c_0q}{2U^{39}}.\] With \[ n=q^{1/2},\qquad V=\frac{2}{c_0}U^{39}, \tag{32}\] we have \(V\ge2\), \(V=q^{o(1)}\), and all the hypotheses (8) hold. The incidence configuration now meets the extraction hypotheses. Lemma 5 gives \(S\subseteq\mathbb F_q^*\) satisfying \[\frac{3q^{1/2}}{8V^2}\le |S|\le Vq^{1/2},\qquad |S-S|,|S/S|\le2^{20}V^{22}q^{1/2}.\] In particular \(|S|=q^{1/2+o(1)}\), and, on setting \(K=2^{23}V^{24}\), we have \(K\ge2\), \(K=q^{o(1)}\), and \(|S-S|,|S/S|\le K|S|\). This contradicts Lemma 7. We have excluded every sequence of counterexamples of the form (22). The negation of the theorem would have produced such a sequence, so some absolute \(\kappa\in(0,1/10)\) and \(Q\) satisfy the stated conclusion. ◻ Line covers after random deletionsWe regard the affine plane \(\mathbb F_q^2\) as a subset of its projective completion \(\mathbb P^2(\mathbb F_q)\). Thus a pencil with centre at infinity is a parallel class of affine lines. The purpose of this section is to show that a set of at most \(q\) lines covering almost all survivors of a suitable random deletion process must contain almost a full pencil. The deletions within a single trial may be dependent; independence is required only between trials. Classical covering results for finite planes are closely related by duality to blocking sets. Jamison and Brouwer–Schrijver established the affine blocking-set lower bound \(2q-1\) (Jamison 1977; Brouwer and Schrijver 1978), and Blokhuis, Brouwer, and Szőnyi studied partial projective covers and bounds depending on their uncovered points (Blokhuis et al. 2010, sec. 1.1, Proposition 1.5). Here the covered set instead consists of the positive-density survivors of structured random deletions. We prove the pencil statement needed in this setting directly. There are two different concentration tasks. The total number of surviving points and the number on a fixed line have bounded changes under one trial; for these we use the elementary estimates in (OpenAI 2026, Lemmas A.2–A.3). The more delicate task is to retain many intersections of a short list of lines, simultaneously for every such list. A deletion trial rarely hits this small set, and we must use that rarity in the variance estimate. We prove the needed Bernstein-type martingale bound here, following the method of Freedman (Freedman 1975, Theorem (1.6) and Proposition (2.1)). Lemma 8 (Martingale concentration). Let \(Z_i\), \(1\leq i\leq n\), be martingale differences for a filtration \((\mathcal A_i)_{i=0}^n\). Suppose that \(M,V>0\) and deterministic numbers \(v_i\geq0\) satisfy, almost surely, \[|Z_i|\leq M,\qquad \mathbb E(Z_i^2\mid\mathcal A_{i-1})\leq v_i,\qquad \sum_{i=1}^n v_i\leq V.\] Then, for every \(u>0\), \[ \Pr\left(\left|\sum_{i=1}^n Z_i\right|\geq u\right) \leq 2\exp\left[-\frac14 \min\left\{\frac{u^2}{V},\frac{u}{M}\right\}\right]. \tag{33}\] Proof. For \(|z|\leq1\) we have \(e^z\leq1+z+z^2\). Consequently, if \(|\theta|\leq M^{-1}\), the conditional mean-zero property gives \[\mathbb E(e^{\theta Z_i}\mid\mathcal A_{i-1}) \leq 1+\theta^2v_i\leq e^{\theta^2v_i}.\] Iteration and Markov’s inequality bound the upper tail by \(\exp(\theta^2V-\theta u)\) for \(0<\theta\leq M^{-1}\). Take \(\theta=\min\{u/(2V),1/M\}\). If \(u\leq2V/M\), the exponent is \(-u^2/(4V)\); otherwise it is at most \(-u/(2M)\). Applying the same argument to \(-Z_i\) proves (33). ◻ Lemma 9 (Line covers after random deletions). Let \(q\to\infty\) through prime powers for which every proper subfield of \(\mathbb F_q\) has order at most \(q^{1/3}\). Fix a positive integer \(D\) and constants \(\delta>0\) and \(0<\rho<1\). For each \(q\), let \(\mathcal F\) be a family of at most \(Dq^D\) subsets of \(\mathbb F_q^2\), called shapes, such that
There are at most \(Dq\) independent trials, each producing a random list of at most \(D\) shapes from \(\mathcal F\). Delete every point on any listed shape, and denote the surviving set by \(X\). Assume that
Write \(X^\ell\) for the surviving set when all exact occurrences of the shape \(\ell\) are ignored, with every other listed shape still deleted. With probability tending to one, both of the following statements hold:
Proof. We first establish a simultaneous lower bound on surviving cross-intersections for every admissible pair of short line lists, ignoring any deletion shape equal to one of those lines. After fixing such a realization, we show that any cover lacking an almost full pencil contains an admissible pair with too few surviving cross-intersections. This second step samples only within the fixed cover, with separate arguments according to its maximum concurrency. Fix the absolute constant \(\kappa\in(0,1/10)\) of Theorem 3, and put \(\epsilon=\kappa/10\). All constants below may depend on the fixed parameters, but not on \(q\), the particular deletion distributions, or a subsequently chosen cover. Uniform point and line counts.Expose the independent trials one at a time. Changing one trial changes \(|X|\) by at most \(2D^2q\), because the old and new lists contain at most \(2D\) shapes in total and each has at most \(Dq\) points. The exposure observation in (OpenAI 2026, Lemma A.3) therefore bounds the absolute martingale increment by \(L=2D^2q\). There are \(T\le Dq\) trials, and \(\mathbb E|X|=\delta_q q^2\). The fixed-time concentration estimate in (OpenAI 2026, Lemma A.2), with \(u=q^{3/2+\epsilon}\), gives \[\Pr\bigl(\bigl||X|-\delta_q q^2\bigr|\ge q^{3/2+\epsilon}\bigr) \le2\exp\left(-\frac{q^{2\epsilon}}{32D^5}\right).\] If there are no trials, the count is deterministic and this bound holds as well. Equivalently, we may add a dummy trial of zero change. For the line count \(|X^\ell\cap\ell|\), the rule ignoring exact copies of \(\ell\) is applied separately to each trial. Changing one trial then changes the count by at most \(2D^2\): each of its at most \(2D\) old or new shapes meets \(\ell\) in at most \(D\) points. With \(L=2D^2\) and \(u=q^{1/2+\epsilon}\), the same two elementary estimates and \(T\le Dq\) give \[\Pr\bigl(\bigl||X^\ell\cap\ell|-\mathbb E|X^\ell\cap\ell|\bigr| \ge q^{1/2+\epsilon}\bigr) \le2\exp\left(-\frac{q^{2\epsilon}}{32D^5}\right).\] Moreover, a point restored by ignoring \(\ell\) can be restored only if some trial lists \(\ell\) exactly. The probability of this event is at most \(D/q\), by the third deletion hypothesis. Therefore \[\delta_q q\leq \mathbb E|X^\ell\cap\ell|\leq\delta_q q+D.\] There are \(q(q+1)\) affine lines. The superpolynomial tails and a union bound consequently show that, with probability tending to one, \[ \begin{split} |X|&=\delta_q q^2+O_D(q^{3/2+\epsilon}),\\ |X^\ell\cap\ell|&=\delta_q q+O_D(q^{1/2+\epsilon}) \qquad\text{for every affine line }\ell. \end{split} \tag{34}\] The lower line estimate proves the first conclusion of the lemma. For the pencil conclusion we will also need to bound overlaps in an alleged cover. The same estimates give the uniform upper bound \[ |X\cap\ell|\leq\delta_q q+O_D(q^{1/2+\epsilon}), \tag{35}\] because \(X\subseteq X^\ell\). A simultaneous event for small line samples.The counts just proved control a single line but do not yet restrict how a cover’s lines meet. We now obtain a stronger test on short lists of lines: provided their intersections are distinct and not concentrated on a deletion shape, many of those intersections survive. The list length will be logarithmic in \(q\), so that the variance-sensitive tail can pay for a union bound over all lists. Set \[h=10(D+1),\qquad H_0=2Dh,\qquad t=\lceil A\log q\rceil,\] where the fixed constant \(A\) will be chosen below. Consider any ordered tuple of \(2t\) distinct affine lines, separated into two lists of length \(t\). Call the tuple admissible if its cross-list intersections form a set \(P_0\) of \(t^2\) distinct finite points, and \[ |F\cap P_0|\leq H_0 \quad\text{for every }F\in\mathcal F \text{ which is not one of the tuple lines}. \tag{36}\] For this tuple, ignore deletions by every shape equal to a tuple line, and let \(Y_0\) count the survivors in \(P_0\) after the remaining deletions. We claim that, with probability tending to one, \[ Y_0\geq\frac{\delta t^2}{2} \qquad\text{for every admissible tuple}. \tag{37}\] To prove the claim, fix a tuple in advance. Omitting shapes is a deterministic operation on each trial, so the trials remain independent. Omission can only restore points, and hence \(\mathbb EY_0\geq\delta t^2\). By (36), each trial’s contribution to the deletion set within \(P_0\) has size at most \(C_0=DH_0\). The probability that this contribution is nonempty is at most \(Dt^2/q\), by a union bound over \(P_0\) and the per-point deletion hypothesis. For completeness, the rarity of a nonempty contribution also controls the conditional variance of the exposure martingale. Fix the past, and let \(g_i(w)\) be the conditional expected final value of \(Y_0\) when the current trial has outcome \(w\). Let \(g_i(\varnothing)\) denote the hypothetical value obtained by making this trial delete nothing on \(P_0\). Independence leaves the law of the future trials unchanged, so \[|g_i(w)-g_i(\varnothing)|\leq C_0,\] with equality to zero whenever the trial’s contribution is empty. The current trial also retains its original law conditional on the past. Thus the martingale increment has absolute value at most \(2C_0\), and its conditional variance is at most \[\mathbb E\bigl((g_i(w)-g_i(\varnothing))^2\mid\text{past}\bigr) \leq C_0^2\frac{Dt^2}{q}.\] The sum of conditional variances is at most \(D^2C_0^2t^2\), since there are at most \(Dq\) trials. Applying Lemma 8 at deviation \(\delta t^2/2\) yields \[ \Pr\left(Y_0<\frac{\delta t^2}{2}\right) \leq2e^{-c_0t^2},\qquad c_0=\min\left\{\frac{\delta^2}{16D^2C_0^2}, \frac{\delta}{16C_0}\right\}>0. \tag{38}\] In particular, \(c_0\) is independent of \(A\). There are at most \((q(q+1))^{2t}\) ordered tuples. The logarithm of the union bound in (38) is \[-c_0t^2+4t\log q+O(t/q)+O(1) =\bigl(-c_0A^2+4A+o(1)\bigr)(\log q)^2.\] Choose, for example, any fixed \(A>5/c_0\). This proves (37) simultaneously for all admissible tuples. Consequences of an alleged cover.The random part of the argument is complete. We now keep the deletion outcome fixed and show deterministically that the simultaneous events exclude any cover without an almost full pencil. Random sampling below is only a way to find a short witness inside a fixed cover. Fix a realization satisfying both (34) and (37). Suppose that the second conclusion of the lemma fails. From an offending cover remove every line which actually occurred as a listed deletion shape. Such a line contains no point of \(X\), so the remaining line set \(L\) still covers all but at most \(2q\) points of \(X\). Put \(m=|L|\), and for any projective point \(p\) write \(n_p=|\{\ell\in L:p\in\ell\}|\). Define \[E_L=\sum_{x\in X}(n_x-1)_+, \qquad (a)_+=\max\{a,0\}.\] The count of covered survivors and (35) give \[m\bigl(\delta_q q+O_D(q^{1/2+\epsilon})\bigr) \geq\delta_q q^2-O_D(q^{3/2+\epsilon})-2q.\] Since \(\delta_q\geq\delta\) and \(m\leq q\), this implies \[ m=q-O_{D,\delta}(q^{1/2+\epsilon}),\qquad E_L=O_D(q^{3/2+\epsilon}). \tag{39}\] For the second estimate, subtract the number of covered survivors from \(\sum_{\ell\in L}|X\cap\ell|\) and use \(m\leq q\). Finally, put \[R=\max_{p\in\mathbb P^2(\mathbb F_q)}n_p.\] The failure of the pencil conclusion implies \(R\leq(1-\rho)q\). We will find an admissible tuple of lines from \(L\) with fewer than \(\delta t^2/2\) survivors in its cross-intersection set. Low concurrency: \(R\leq q^{1/2+\kappa/4}\).Let \(T=q^{1/2-\kappa/3}\). The number of ordered pairs of distinct lines of \(L\) meeting at a point \(x\in X\) is \(\sum_{x\in X}n_x(n_x-1)\). Points with \(n_x<T\) contribute at most \[ T E_L=O(q^{2-7\kappa/30}). \tag{40}\] The set \(P=\{x\in X:n_x\geq T\}\) has size \[|P|\leq\frac{E_L}{T-1} =O(q^{1+13\kappa/30})\leq q^{1+\kappa}\] for sufficiently large \(q\). Theorem 3, applied to \(P\) and \(L\), therefore gives \(\sum_{x\in P}n_x\leq q^{3/2-\kappa}\). The contribution of these points to the ordered-pair count is at most \[ R\sum_{x\in P}n_x\leq q^{2-3\kappa/4}. \tag{41}\] Together, (40) and (41) show that the fraction of ordered distinct line pairs meeting in \(X\) is \[ O\bigl(q^{-7\kappa/30}+q^{-3\kappa/4}\bigr)=o(1). \tag{42}\] Sample an ordered tuple of \(2t\) distinct lines uniformly from \(L\). The expected number of its cross pairs meeting in \(X\) is \(t^2\) times the fraction in (42). Markov’s inequality shows that this number is less than \(\delta t^2/2\) with probability tending to one. We next check the two admissibility conditions. A given sampled pair is parallel with probability at most \(R/(m-1)\). Once two distinct lines have been sampled, at most \(R\) population lines pass through their projective intersection, so the probability of concurrency for any specified three sampled positions is at most \(R/(m-2)\). The probability of any parallel pair or concurrent triple in the tuple is consequently \[ O\left(\frac{(t^2+t^3)R}{m}\right) =O\bigl((\log q)^3q^{-1/2+\kappa/4}\bigr)=o(1). \tag{43}\] If neither event occurs, every cross intersection is finite and the cross intersections are distinct: equality of two different cross intersections would make at least three of the tuple lines concurrent. To verify (36), fix \(F\in\mathcal F\). Consider the event that \(F\) is not a tuple line but contains more than \(H_0\) distinct finite cross intersections. Each tuple line then contains at most \(D\) points of \(F\). Greedily choose a cross intersection on \(F\) and its two representing positions, and discard all cross intersections on either of those lines. Each step discards at most \(2D\) points. Since \(H_0=2Dh\), this produces \(h\) cross pairs whose \(2h\) positions are distinct. Among the population \(L\), there are at most \(mDR\) ordered distinct line pairs, neither line equal to \(F\), whose intersection lies in \(F\). Indeed, the first line meets \(F\) in at most \(D\) points, and at each such point there are at most \(R\) choices of the second line. There are at most \(t^{2h}\) ordered choices of the \(h\) cross pairs of positions. For each choice, the sampled lines at those \(2h\) distinct positions are uniform among \((m)_{2h}\) assignments, where \((z)_a=z(z-1)\cdots(z-a+1)\). The probability of the event for this fixed shape is therefore at most \[ \frac{t^{2h}(mDR)^h}{(m)_{2h}} =O_{D,h}\left(\left(\frac{t^2R}{m}\right)^h\right). \tag{44}\] The numerator may count assignments with repeated population lines; this only enlarges the upper bound. Summing (44) over all shapes gives \[O\bigl((\log q)^{2h}q^{D-h(1/2-\kappa/4)}\bigr)=o(1),\] because \(\kappa<1/10\) and \(h=10(D+1)\) imply \[D-h(1/2-\kappa/4) <D-\frac{19}{4}(D+1)<0.\] Thus, with probability tending to one, the sampled tuple is admissible and has fewer than \(\delta t^2/2\) cross pairs meeting in \(X\). High concurrency: \(R>q^{1/2+\kappa/4}\).Choose a projective point \(p\) with \(n_p=R\), and take all \(R\) lines of \(L\) through \(p\) as the pencil. Its complement has size \[N=m-R\geq\rho q/2\] for sufficiently large \(q\), by (39); no complement line passes through \(p\). Sample the first list of \(t\) lines uniformly without replacement from the pencil, and independently sample the second list in the same way from the complement. Any cross intersection lies off \(p\). At a cross intersection \(x\in X\), exactly one pencil line passes through \(x\), and the number of cross pairs meeting there is the number of complement lines through \(x\), namely \(n_x-1\). Thus at most \(E_L\) of all \(RN\) population cross pairs meet in \(X\). Their fraction is at most \[ \frac{E_L}{RN} =O\bigl(q^{\epsilon-\kappa/4}\bigr) =O(q^{-3\kappa/20})=o(1). \tag{45}\] As before, expectation and Markov’s inequality show that fewer than \(\delta t^2/2\) sampled cross pairs meet in \(X\), with probability tending to one. For a fixed complement line, at most one pencil line meets it at infinity when \(p\) is finite. When \(p\) is at infinity, the pencil lines have direction \(p\) and every complement line has a different direction, so all cross intersections are finite. The probability of any infinite cross intersection is therefore at most \(t^2/R\). Two equal cross intersections must use the same pencil line, since distinct pencil lines meet only at \(p\), which lies on no complement line. Given two complement lines, their projective intersection determines at most one affine pencil line, namely its join with \(p\). If this join is the line at infinity, there is no affine candidate. Conditioning on the second list and taking a union bound over its pairs shows that the probability of a collision is \(O(t^3/R)\). The total probability of a failure of finiteness or distinctness is therefore \[ O\left(\frac{t^2+t^3}{R}\right) =O\bigl((\log q)^3q^{-1/2-\kappa/4}\bigr)=o(1). \tag{46}\] Fix \(F\in\mathcal F\), and consider the event that \(F\) is not a tuple line but contains more than \(H_0\) distinct finite cross intersections. The same greedy argument gives \(h\) cross pairs with disjoint positions. There are at most \(DN\) population cross pairs, with neither line equal to \(F\), whose intersection lies in \(F\): a complement line distinct from \(F\) meets \(F\) in at most \(D\) points, all off \(p\), and each such point determines at most one pencil line. The two lists are sampled independently, so the probability of this occupancy violation for a fixed shape is at most \[ \frac{t^{2h}(DN)^h}{(R)_h(N)_h} =O_{D,h}\left(\left(\frac{t^2}{R}\right)^h\right). \tag{47}\] After summing over \(\mathcal F\), the bound becomes \[O\bigl((\log q)^{2h}q^{D-h(1/2+\kappa/4)}\bigr)=o(1),\] since \[D-h(1/2+\kappa/4)<D-5(D+1)<0.\] The sampled tuple is consequently admissible and has fewer than \(\delta t^2/2\) cross pairs meeting in \(X\), with probability tending to one in this regime as well. The contradiction and the order of choices.All sampling estimates above are uniform over line sets satisfying (39) and the appropriate bound on \(R\). In either regime, for every sufficiently large \(q\) there is therefore an admissible tuple from the fixed line set \(L\) with \[|X\cap P_0|<\delta t^2/2.\] No line of \(L\) actually occurred as a listed deletion shape. Hence ignoring exact occurrences of its tuple lines changes none of the deletions in the fixed realization, and the tuple’s count \(Y_0\) is exactly \(|X\cap P_0|\). This contradicts (37). In particular, the cover and the tuple are allowed to depend on the realized deletions: the event (37) was established simultaneously for every admissible tuple before fixing the realization. Sampling from \(L\) is used only to prove the existence of a tuple inside that fixed realization. No concentration estimate is conditioned on the choice of the cover. The contradiction proves the second conclusion, and finishes the proof. ◻ Selecting compatible translatesThe deletion estimates require independent random choices, while intersection of the exceptional edges requires geometric compatibility. We separate these tasks by sampling several independent translates of each bounded configuration and then selecting one from each pool. The theorem below supplies the selection step. Its input consists of finite point sets \(W_i\) and sets \(D_i\) of forbidden join directions; its output avoids every forbidden join between different selected sets. Because a direction is a linear subspace containing zero, the condition also rules out a common point between two selected configurations whenever at least one of their direction sets is nonempty. Theorem 10 (Compatible translates from independent pools). For every positive integer \(D\) there is a positive integer \(K=K(D)\) with the following property. Let \(q\) tend to infinity through prime powers. For each \(q\), let \(n\le Dq\), and for \(1\le i\le n\) let \(W_i\subseteq\mathbb F_q^2\) and let \(D_i\) be a set of directions, with \[|W_i|\le D,\qquad |D_i|\le D.\] Assume that each direction belongs to \(D_i\) for at most \(D\) indices \(i\). For distinct indices \(i,j\), declare the translates \(b+W_i\) and \(b'+W_j\) to conflict if there are \(u\in W_i\), \(v\in W_j\), and \(d\in D_i\cup D_j\) such that \[(b+u)-(b'+v)\in d.\] For each \(i\), draw \(K\) independent uniform shifts \(b_{i,1},\ldots,b_{i,K}\in\mathbb F_q^2\), independently for all indices. With probability tending to one, one can choose \(k_i\in\{1,\ldots,K\}\) for every \(i\) so that the translates \(b_{i,k_i}+W_i\) have no conflicts. The convergence is uniform over all data satisfying the stated bounds. To prove the theorem, make each candidate a vertex of a graph and join candidates from different pools when they conflict. We seek an independent set containing one vertex from each pool, called an independent transversal. Its nonexistence has a small domination certificate. We first prove the form of that assertion we need, then show that the independent shifts make every such certificate unlikely. The certificate argument is a weaker form of Haxell’s independent-transversal domination theorem (Haxell 2001), whose method originates in (Haxell 1995). We include its proof. Haxell’s theorem uses total domination, which also requires neighbors for the vertices of the dominating set. Here we use the following weaker convention. For a graph \(G\) and a set \(S\) of its vertices, we say that \(T\subseteq S\) dominates \(S\) if every vertex of \(S\setminus T\) has a neighbor in \(T\). No condition is imposed on the vertices of \(T\) themselves. Lemma 11 (A domination certificate). Let a finite simple graph have a vertex partition into nonempty parts \(A_1,\ldots,A_n\). If there is no independent set containing one vertex from each part, then there are a nonempty index set \(I\) and a set \[T\subseteq\bigcup_{i\in I}A_i, \qquad |T|\le 2(|I|-1),\] such that \(T\) dominates \(\bigcup_{i\in I}A_i\). Proof. We grow a set of vertices with small size compared with the number of parts it reaches. Whenever it does not yet dominate those parts, we use an undominated vertex to reach another part. A minimality condition on the transversals prevents this growth from stopping without the required domination certificate. Choose an inclusion-minimal nonempty subfamily of parts with no independent transversal, and distinguish one part \(A_*\) of this subfamily. Let \(\mathcal U\) be the family of independent transversals of all its other parts. Minimality makes \(\mathcal U\) nonempty. The deficient subfamily has at least two parts, since every part is nonempty. Choose any \(x_1\in A_*\). Among \(U\in\mathcal U\), minimize \(|N(x_1)\cap U|\), where \(N(x)\) denotes the neighborhood of \(x\) in \(G\). Fix a minimizer and write \(Y_1=N(x_1)\cap U\). This set is nonempty: otherwise adjoining \(x_1\) would give an independent transversal of the deficient subfamily. Inductively, suppose that vertices \(x_1,\ldots,x_j\) and sets \(Y_1,\ldots,Y_j\) have been fixed with the following properties:
Let \(Y=\bigcup_{a=1}^jY_a\), let \(I\) consist of the distinguished part and all parts represented in \(Y\), and put \[T=\{x_1,\ldots,x_j\}\cup Y.\] By joint realization, the vertices of \(Y\) occupy distinct parts, none of them \(A_*\). Thus \(|I|=|Y|+1\), while nonemptiness of the \(Y_a\) gives \(j\le |Y|\). The third invariant shows that \(T\) lies in the union of the parts indexed by \(I\), and \[|T|\le j+|Y|\le 2|Y|=2(|I|-1).\] If \(T\) dominates this union, we have the required certificate. Otherwise, choose a vertex \(x_{j+1}\) in that union, outside \(T\), with no neighbor in \(T\). Among the transversals realizing all the current equalities, choose \(U\) minimizing \(|N(x_{j+1})\cap U|\), and set \[Y_{j+1}=N(x_{j+1})\cap U.\] This set avoids all the previous \(Y_a\), because \(x_{j+1}\) has no neighbor in \(T\). We claim it is nonempty. If it were empty and \(x_{j+1}\in A_*\), then \(U\cup\{x_{j+1}\}\) would be an independent transversal of the deficient subfamily. Otherwise, the part of \(x_{j+1}\) contains a unique vertex \(y\) of \(Y\), say \(y\in Y_b\). The transversal \(U\) uses \(y\) in that part, so \(x_{j+1}\notin U\). Replace \(y\) by \(x_{j+1}\) to form \[U'=(U\setminus\{y\})\cup\{x_{j+1}\}.\] Since \(N(x_{j+1})\cap U=\varnothing\), this is again an independent transversal of the nondistinguished parts. For every \(a<b\), the vertex \(y\) does not belong to \(Y_a\), and the new vertex is not adjacent to \(x_a\). Consequently the exact earlier equalities are preserved: \[N(x_a)\cap U'=Y_a\qquad(a<b).\] For \(a=b\), the replacement removes the neighbor \(y\) and adds no neighbor, so \[|N(x_b)\cap U'|=|Y_b|-1.\] This contradicts the minimum imposed at stage \(b\). Notice that the contradiction uses only the equalities preceding stage \(b\); preservation of later equalities is not required. Thus \(Y_{j+1}\) is nonempty and all the induction invariants continue to hold. Each continuation adds vertices in previously unrepresented parts to \(Y\), whereas all of \(Y\) lies in one transversal of the fixed nondistinguished subfamily. There can be only finitely many continuations. The process must therefore stop with a dominating set \(T\), proving the lemma. ◻ Proof of Theorem 10. The case \(n=0\) is immediate, so suppose \(n\ge1\). Fix \(D\) and, for the moment, a constant integer \(K\ge6\). We will choose \(K\) sufficiently large in terms of \(D\) at the end. Form a graph whose vertices are the candidate positions \((i,k)\), partitioned into the \(n\) pools. Put an edge between candidates in different pools precisely when their translates conflict. Candidate positions are distinct vertices even when their sampled shifts happen to coincide. An independent transversal in this graph is exactly a selection as in the theorem. By Lemma 11, it suffices to show that, with probability tending to one, there are no nonempty index sets \(I\), with \(|I|=m\), and sets \(T\) of at most \(2m\) candidate positions in those pools that dominate their union. We use the slightly weaker bound \(2m\) to simplify the counting. Throughout the probability estimates, \(I\) and \(T\) are fixed sets of indices before any shifts are exposed. The proof splits according to \(m\), the number of pools in the certificate. When \(m\) is small, the forbidden lines associated with \(T\) occupy only a small part of each candidate’s possible shifts. When \(m\) is proportional to \(q\), that direct bound is insufficient. Instead, we expose \(T\) in a bounded number of chunks and prove that a positive average proportion of shifts remains feasible. Crucially, this proportion will depend only on \(D\), so we may subsequently choose \(K\) large enough that the unused candidates defeat all certificates. Forbidden equations and counting possible certificates.For every direction \(d\) in use, fix a nonzero linear functional \(\pi_d:\mathbb F_q^2\to\mathbb F_q\) whose kernel is \(d\). After exposing the shifts of the candidates \(e\in T\), call a shift \(b\in\mathbb F_q^2\) feasible for target \(i\) if, for every such \(e\), with source-pool index \(j\), it avoids every equation \[ \pi_d(b)=\pi_d(b_e)+\pi_d(v-u), \qquad u\in W_i,\quad v\in W_j,\quad d\in D_i\cup D_j. \tag{48}\] We impose these prohibitions even when \(i=j\). This only makes feasibility more restrictive. A feasible candidate outside \(T\) has no neighbor in \(T\), so its existence prevents domination. Set \[ C=2D^3,\qquad c_1=\frac1{4C},\qquad \alpha=\frac1{2C}. \tag{49}\] For one target \(i\) and one exposed candidate \(e\), there are at most \(C\) equations in (48). This remains true if the two lists \(D_i\) and \(D_j\) are counted separately, retaining duplicate directions. Each equation excludes one affine line, containing exactly \(q\) shifts. The number of choices of \(I\) is at most \[\binom{n}{m}\le\left(\frac{eDq}{m}\right)^m.\] There is an absolute constant \(C_*>0\) such that, for \(K\ge6\), the number of candidate-index sets \(T\) in these pools with \(|T|\le2m\) is at most \[ \sum_{t=0}^{2m}\binom{Km}{t}\le (C_*K^2)^m. \tag{50}\] For example, the usual bound \(\sum_{t=0}^{r}\binom Nt\le(eN/r)^r\) for \(1\le r\le N/2\) applies with \(N=Km\) and \(r=2m\). The range \(1\le m\le c_1q\).Condition on all the exposed shifts in \(T\). A fresh uniform shift for any target \(i\in I\) is infeasible with probability at most \[\frac{C|T|}{q}\le\frac{2Cm}{q}\le\frac12.\] At least \((K-2)m\) candidate positions in the target pools remain unexposed. Their shifts are conditionally independent and uniform. Thus the probability that \(T\) dominates, for this fixed \(I,T\), is at most \[ \left(\frac{2Cm}{q}\right)^{(K-2)m}. \tag{51}\] Combining this with the counts of \(I\) and \(T\), the probability of a dominating certificate of size parameter \(m\) is at most \[ \left[ 2CeD C_*K^2 \left(\frac{2Cm}{q}\right)^{K-3} \right]^m. \tag{52}\] Choose \(K\) large enough that \[ 2CeD C_*K^2\,2^{-(K-3)}\le\frac12. \tag{53}\] Then the bracket in (52) is at most \(1/2\) throughout this range, and tends to zero for every fixed positive \(m\). Summing over \(m\) gives \(o(1)\): for a fixed cutoff, the finite initial sum tends to zero, while the remaining terms are bounded by a geometric tail. A feasible-density estimate for \(m>c_1q\).We prove that there is a constant \(\delta_1>0\), depending only on \(D\) and not on \(K\), such that for every fixed \(I,T\) in this range, \[ \Pr\!\left[ \sum_{i\in I}|U_i^{\mathrm{fin}}|<\delta_1mq^2 \right] \le \exp\bigl(-\Omega_D(q\log q)\bigr). \tag{54}\] Here \(U_i^{\mathrm{fin}}\) is the set of shifts feasible for target \(i\) after all candidates in \(T\) have been exposed. The estimate is uniform in \(I,T\) and the configuration data. The lower cutoff on \(q\) may depend on the fixed value of \(K\). Expose the candidate positions of \(T\) in a fixed order, divided into consecutive chunks of size at most \(\lfloor\alpha q\rfloor\), with all but the last having that size. For sufficiently large \(q\), \(\lfloor\alpha q\rfloor\ge\alpha q/2\). Since \(|T|\le2m\le2Dq\), the number of chunks is at most \[ J_0=\left\lceil\frac{4D}{\alpha}+1\right\rceil. \tag{55}\] In particular, this bound does not involve \(K\). If \(T\) is empty, the desired feasible-density estimate holds deterministically; otherwise there is at least one chunk. At the start of a chunk, condition on all shifts previously exposed. Let \(U_i\) be the set of shifts still feasible for target \(i\), and write \[M=\sum_{i\in I}|U_i|.\] For the analysis of this chunk we keep all these sets frozen at their start values. They are now deterministic, while the shifts belonging to the new chunk are independent uniform vectors. For an entry \(e\) of the chunk, with source-pool index \(j\), define \(Z_e\) by summing, over all equations (48) associated with \(i\in I\) and \(e\), the number of shifts \(b\in U_i\) satisfying that equation. Count the \(D_i\) and \(D_j\) lists separately, including duplicates. A shift deleted more than once is therefore counted more than once, which is harmless for an upper bound on loss. Each line contains at most \(q\) shifts, and each of its right-hand sides is uniform in \(\mathbb F_q\). Consequently, \[ 0\le Z_e\le Cmq, \qquad \mathbb EZ_e\le \frac{CM}{q}. \tag{56}\] All expectations and variances in the following chunk calculation are conditional on the fixed past. The terms whose directions belong to the target.The expectation bound alone does not control the loss in a chunk. We estimate its fluctuations by separating the two direction lists in each forbidden equation. Bounded reuse of target directions handles one list; the affine second moment will handle the source list. Write \[Z_e=Z_e^{(1)}+Z_e^{(2)},\] where \(Z_e^{(1)}\) uses the list \(D_i\) in each target, and \(Z_e^{(2)}\) uses the list \(D_j\) of the source. Group the terms of \(Z_e^{(1)}\) by direction. The group for \(d\) is a function only of \(\pi_d(b_e)\). For distinct directions \(d,d'\), the functionals \(\pi_d,\pi_{d'}\) are linearly independent, so \[b_e\longmapsto\bigl(\pi_d(b_e),\pi_{d'}(b_e)\bigr)\] is a bijection from \(\mathbb F_q^2\) to itself. The two coordinates are therefore independent and uniform. The direction groups are pairwise independent, which suffices for adding their variances. There are at most \(Dm\) such groups. Each direction belongs to at most \(D\) target direction sets; for each associated target-source pair there are at most \(D^2\) choices of \((u,v)\). Thus every group is bounded by \(D^3q\), and \[ \operatorname{Var}(Z_e^{(1)})\le D^7mq^2. \tag{57}\] The terms whose directions belong to the source.For each target \(i\) and each direction \(d\), define the variance of its parallel line slices by \[ V_{i,d}=\frac1q\sum_{\ell\parallel d} \left(|U_i\cap\ell|-\frac{|U_i|}{q}\right)^2, \tag{58}\] where the sum is over the \(q\) affine lines of direction \(d\). These variances obey the exact identity \[ \sum_d V_{i,d} =|U_i|-\frac{|U_i|^2}{q^2} \le |U_i|\le q^2, \tag{59}\] where the sum runs over all \(q+1\) directions. This is precisely the normalized affine second-moment identity in (OpenAI 2026, Lemma A.1), applied to \(U_i\subseteq\mathbb F_q^2\). That identity holds for every subset of every finite affine plane; it has no randomness, characteristic, or subfield hypothesis. Thus it applies after conditioning on any history of earlier chunks. This is the reason we can control all source directions even when the feasible sets \(U_i\) have complicated shapes. Every individual summand of \(Z_e^{(2)}\) associated with \(i,d,u,v\) is a uniformly sampled line-slice count, with its slice index translated by a fixed offset. Its variance is therefore \(V_{i,d}\). There are at most \(D^3m\) summands, and each pair \((i,d)\) is repeated at most \(D^2\) times. Cauchy–Schwarz applied to their centered sum, without any independence assumption, gives \[ \operatorname{Var}(Z_e^{(2)}) \le D^5m A_e, \qquad A_e:=\sum_{i\in I}\sum_{d\in D_j}V_{i,d}. \tag{60}\] Each source pool contributes at most \(K\) entries to the chunk, and each direction belongs to at most \(D\) source direction sets. Consequently, by (59), \[ \sum_{e\text{ in the chunk}} A_e \le KD\sum_{i\in I}\sum_d V_{i,d} \le KDmq^2. \tag{61}\] Call an entry regular if \(A_e\le mq^{3/2}\). There are at most \(KD\sqrt q\) irregular entries. For a regular entry, (57), (60), and \(\operatorname{Var}(X+Y)\le2\operatorname{Var}(X)+2\operatorname{Var}(Y)\) give \[ \operatorname{Var}(Z_e) \le 2D^7mq^2+2D^5m^2q^{3/2}. \tag{62}\] For a fixed constant \(\gamma>0\), Chebyshev’s inequality and (56) therefore imply \[\begin{align*} \Pr\!\left[Z_e>\frac{CM}{q}+\gamma mq\right] &\le \frac{2D^7}{\gamma^2m} +\frac{2D^5}{\gamma^2\sqrt q} \\ &\le B_{D,\gamma}q^{-1/2} \qquad\text{for regular }e, \tag{63}\end{align*}\] where \(B_{D,\gamma}\) is independent of \(K\). In the last step we used \(m>c_1q\). Conditional independence and loss over one chunk.The preceding variance bounds show that each regular entry has a small chance of removing far more than its expected share. We now use independence within the chunk to show that few entries do so, and convert that statement into a deterministic bound on the total remaining feasible set. The regularity of an entry is determined by the frozen sets \(U_i\) and its fixed source-pool index. In particular, it does not depend on its fresh shift \(b_e\). After conditioning on the past, the collection of regular entries is fixed, and their variables \(Z_e\) are independent functions of independent shifts. Their common threshold in (63) is also fixed under this conditioning. A union bound over subsets of regular entries, using the chunk size bound and (63), shows that the probability of at least \(\gamma q\) threshold exceedances is at most \[ 2^{\lceil\alpha q\rceil} \left(B_{D,\gamma}q^{-1/2}\right)^{\lceil\gamma q\rceil} \le \exp(-c_{D,\gamma}q\log q) \tag{64}\] for all sufficiently large \(q\), with \(c_{D,\gamma}>0\) independent of \(K\). If there are fewer than \(\lceil\gamma q\rceil\) regular entries, the event in question is empty and the bound remains valid. For each fixed \(K\), we may also take \(q\) sufficiently large that \[ KD\sqrt q\le\gamma q. \tag{65}\] Except on the event in (64), all but at most \(2\gamma q\) entries are regular and below the threshold: the exceptions include all irregular entries. The actual loss of feasible shifts within the chunk is at most \(\sum_eZ_e\), because these counts used the larger feasible sets at the start of the chunk. Bounding each exceptional entry by \(Cmq\) and all other entries by the threshold gives, for the end-of-chunk value \(M'\), the deterministic inequality \[\begin{align*} M' &\ge M-C\alpha M-\alpha\gamma mq^2-2C\gamma mq^2 \\ &=(1-C\alpha)M-(\alpha+2C)\gamma mq^2 \\ &=\frac12M-(\alpha+2C)\gamma mq^2. \tag{66}\end{align*}\] Choose \(\gamma>0\), depending only on \(D\), so small that \[ 2(\alpha+2C)\gamma\le 2^{-J_0-1}, \qquad \delta_1:=2^{-J_0-1}. \tag{67}\] At the beginning, before exposing \(T\), every shift is feasible, so \(M=mq^2\). If all \(J\le J_0\) chunks satisfy (66), iteration gives \[\begin{align*} \frac{M_{\mathrm{fin}}}{mq^2} &\ge 2^{-J}-(\alpha+2C)\gamma \sum_{a=0}^{J-1}2^{-a}\\ &\ge 2^{-J_0}-2(\alpha+2C)\gamma \ge\delta_1. \end{align*}\] The conditional probability bound (64) holds for every possible past. Averaging over the past and taking a union bound over the at most \(J_0\) chunks proves (54). The constants \(J_0\), \(\gamma\), and \(\delta_1\) depend only on \(D\). The dependence on \(K\) in (65) affects only how large \(q\) must be, not these constants. Unused candidates and the large-range union bound.We have established the required positive average feasible density with a failure probability of order \(\exp(-\Omega_D(q\log q))\). There are only exponentially many candidate certificates, so this error can be summed over all of them. On the successful event, the unused candidates now supply the further exponential saving needed to rule out domination. Condition now on all the shifts belonging to \(T\), and suppose the feasible-density event in (54) succeeds. Let \(t_i\) be the number of exposed candidate positions from pool \(i\). Every unused candidate from that pool remains independent and uniform, and is feasible with probability \(|U_i^{\mathrm{fin}}|/q^2\). The probability that none of the unused candidates in the target pools is feasible is therefore at most \[\begin{align*} \prod_{i\in I} \left(1-\frac{|U_i^{\mathrm{fin}}|}{q^2}\right)^{K-t_i} &\le \exp\!\left(-\sum_{i\in I} (K-t_i)\frac{|U_i^{\mathrm{fin}}|}{q^2}\right) \\ &\le \exp\bigl(-(K\delta_1-2)m\bigr). \tag{68}\end{align*}\] To obtain the last inequality, use \[\sum_{i\in I}\frac{|U_i^{\mathrm{fin}}|}{q^2}\ge\delta_1m, \qquad 0\le\frac{|U_i^{\mathrm{fin}}|}{q^2}\le1, \qquad \sum_{i\in I}t_i=|T|\le2m.\] This argument also covers pools for which every candidate belongs to \(T\); it does not assume \(K-t_i\) is positive in every target pool. For \(m>c_1q\), the number of pairs \(I,T\) is at most \(A_K^m\), where \[ A_K=\frac{eD}{c_1}C_*K^2. \tag{69}\] For each fixed pair, domination can occur only if the feasible-density estimate fails or all unused candidates are infeasible despite its success. The sum of the first failure probabilities over all \(m,I,T\) in the large range is bounded by \[\exp\bigl(O_{D,K}(q)\bigr) \exp\bigl(-\Omega_D(q\log q)\bigr)=o(1).\] Here the number of choices is at most \(\sum_{m\le Dq}A_K^m=\exp(O_{D,K}(q))\), with \(K\) fixed. Finally choose \(K\) sufficiently large, still depending only on \(D\), so that both (53) and \[ A_K\exp(2-K\delta_1)<\frac12 \tag{70}\] hold. Such a choice exists because \(\delta_1>0\) does not depend on \(K\), whereas \(A_K\) grows only quadratically in \(K\). By (68), the sum of the remaining failure probabilities is then at most \[\sum_{m>c_1q} \left(A_K\exp(2-K\delta_1)\right)^m \le\sum_{m>c_1q}2^{-m}=o(1).\] Together with the small-range estimate, this excludes all dominating certificates with probability tending to one. Lemma 11 therefore supplies an independent transversal, proving the theorem. The choices have been made in the order \[D\ ;\quad C,c_1,\alpha,J_0,\gamma,\delta_1\ ;\quad K\ ;\quad q.\] In particular, \(K\) is fixed before taking \(q\) to infinity, and all sufficiently-large-\(q\) conditions may depend on that fixed \(K\). Every estimate above is uniform over the configurations and direction sets subject to the bounds in the theorem. ◻ A configuration with two coordinatizationsWe now use the deletion lemma to construct the exceptional configuration. We need two properties of the same set: many points on each undeleted line, and rigidity of its small line covers. A change of coordinates lets us obtain both. In the original coordinates we delete one line in every finite nonzero direction. After the change of coordinates, the deleted sets become curves, so the line-survival conclusion of Lemma 9 applies to every line. It will force every small mixed cover by lines and individual points to be a parallel class. Lemma 12. For every sufficiently large prime \(s\equiv2\pmod3\), there is a set \(Y\subseteq\mathbb F_s^2\) with the following properties. For each \(d\in\mathbb F_s^*\), there is an affine line \(\ell_d\) of slope \(d\), and \[Y=\mathbb F_s^2\setminus\bigcup_{d\in\mathbb F_s^*}\ell_d.\] For each \(d\in\mathbb F_s^*\), every line of slope \(d\) other than \(\ell_d\) contains at least five points of \(Y\). The map \[f:\mathbb F_s^2\longrightarrow\mathbb F_s^2, \qquad f(x,y)=(x^3,y),\] is a bijection, and every affine line contains at least \(s/8\) points of \(f(Y)\). Moreover, if \(a\) affine lines and \(b\) individual points cover \(f(Y)\), and \[ a+\frac b2\le s, \tag{71}\] then \(a=s\), \(b=0\), and the lines form a full parallel class. Consequently every such mixed cover has weighted cost at least \(s\), and no cover of \(f(Y)\) by at most \(s\) lines contains two nonparallel lines. Proof. Let \(s\) tend to infinity through primes congruent to \(2\pmod3\). Since \(\gcd(3,s-1)=1\), cubing permutes \(\mathbb F_s^*\) and fixes zero. Thus \(f\) is bijective. It maps horizontal lines to horizontal lines and vertical lines to vertical lines. We first prove the two survival properties simultaneously with high probability, then use them to classify mixed covers satisfying (71). Survivors in the original coordinates.Choose the lines \(\ell_d\), independently for the \(s-1\) values of \(d\), uniformly within their parallel classes. Fix a line \(\ell\) of finite nonzero slope \(d\), and temporarily ignore the choice \(\ell_d\). Each of the other \(s-2\) choices deletes a uniformly distributed point of \(\ell\). Let \(Z_\ell\) count the surviving points on \(\ell\). Its expectation is \[\mu:=\mathbb EZ_\ell=s(1-1/s)^{s-2}.\] Changing one of these choices changes the survivor count by at most two. Apply the independent-trial jump bound and bounded-drift concentration estimate of (OpenAI 2026, Lemmas A.2–A.3) to the exposure martingale, with \(T=s-2\), \(L=2\), and \(u=\mu/2\). The martingale has zero drift, and hence \[\Pr(Z_\ell<\mu/2) \le 2\exp\left(-\frac{\mu^2}{128(s-2)}\right) =\exp(-\Omega(s)).\] There are fewer than \(s^2\) lines under consideration. A union bound, together with \(\mu/2\ge5\) for sufficiently large \(s\), shows that all these counts are at least five with probability tending to one. If \(\ell\ne\ell_d\), reinstating the deletion by \(\ell_d\) changes no point on \(\ell\), since the two lines are parallel. Thus every required line in the original coordinates has at least five points of \(Y\). Survivors and almost-pencil covers in the new coordinates.In the new coordinates, the possible deletion shapes are \[F_{d,z}=\{(x^3,dx+z):x\in\mathbb F_s\}, \qquad d\in\mathbb F_s^*,\quad z\in\mathbb F_s.\] There are \(s(s-1)\) such shapes, each of size \(s\), and each of the \(s-1\) independent trials chooses one of them. Every point is deleted by a specified trial with probability \(1/s\), so its overall survival probability is the uniform value \[\delta_s=(1-1/s)^{s-1}\ge\frac14\] for all sufficiently large \(s\). Each shape meets every affine line in at most three points. For a vertical line this follows from bijectivity of cubing; for a horizontal line it follows from \(d\ne0\). For a line of finite nonzero slope \(m\), the intersection is determined by \[dx+z=mx^3+u,\] a nonzero polynomial equation of degree three. In particular, no shape is itself a line when \(s>5\). All the hypotheses of Lemma 9 hold with field size \(s\), a fixed integer constant, for example \(D=3\), survival lower bound \(\delta=1/4\), and \(\rho_0=1/100\). The exact-line occurrence probabilities are zero, and the subfield restriction is automatic for a prime field. With probability tending to one, every line consequently contains at least \(s/8\) points of \(f(Y)\), and its almost-cover conclusion holds for \(f(Y)\) as well. We now combine that conclusion with the lower bound on every line to replace an almost pencil by a complete one. From an almost pencil to a full parallel class.Assume these events hold, and consider a cover satisfying (71). Repeated resources can be removed; alternatively, one may keep their original counts, since removal only reduces the budget. The line portion has at most \(s\) distinct lines and leaves at most \(b\le2s\) points of \(f(Y)\) uncovered. Lemma 9 supplies at least \((1-\rho_0)s\) distinct lines in this portion through a common projective point \(p\). There are at most \(\rho_0s\) other lines, and \[b\le2(s-a)\le2\rho_0s.\] If an affine line through \(p\) were absent from the cover, all the chosen lines through \(p\) would cover at most one of its affine points. The other lines would cover at most \(\rho_0s\) further points, and the individual point resources at most \(2\rho_0s\). Thus at most \(1+3\rho_0s\) points of this missing line would be covered. For sufficiently large \(s\), this contradicts \[\frac s8>1+3\rho_0s.\] Every affine line through \(p\) must therefore be present. A finite \(p\) requires \(s+1\) lines, which is impossible. An infinite \(p\) requires all \(s\) lines in its parallel class, and then (71) forces \(a=s\) and \(b=0\). This also rules out repetitions in a cover attaining the budget. The events used in the two coordinate systems hold simultaneously with probability tending to one. Consequently every sufficiently large prime \(s\equiv2\pmod3\) admits a successful configuration \(Y\). A mixed cover of cost less than \(s\) would satisfy (71) but not its necessary equality conclusion. The two stated consequences follow. ◻ There are arbitrarily large primes congruent to \(2\pmod3\). Indeed, if the list were finite and its product were \(P\), the integer \(3P-1\equiv2\pmod3\) would have a prime factor congruent to \(2\pmod3\), and none of the primes dividing \(P\) could divide it. Fix any sufficiently large prime \(s\equiv2\pmod3\), and choose \(Y\) and the omitted lines from Lemma 12. These data remain fixed for the rest of the proof. Ambient placementWe will place copies of \(Y\) in a larger affine plane, assign each copy the directions in which its labels will change, and delete the ambient lines of those directions that meet it. The placement must meet two requirements. Joins between different copies must avoid their changed directions, while the undeleted points must retain the pencil and line-survival properties of Lemma 9. We first specify the copies and direction sets, then prove the deletion estimates for independent pools of translates, and finally select one compatible translate from each pool. Fields, copies, and direction setsLet \(n\ge3\) be odd, and put \(q=s^n\). We identify \(\mathbb F_s\) with the prime subfield of \(\mathbb F_q\). If \(E\) is a subfield, then \(|E|=s^a\), where \(a=[E:\mathbb F_s]\), and multiplication of vector-space bases gives \[n=a[\mathbb F_q:E].\] For a proper subfield, the index \([\mathbb F_q:E]\) is an odd integer larger than one, so it is at least three. Consequently \[|E|=s^a\le s^{n/3}=q^{1/3} \qquad\text{for every proper subfield }E.\] Thus Theorem 3 and Lemma 9 apply along this sequence of ambient fields. In this section all constants may depend on the already fixed \(s\) and \(Y\), but not on \(n\). The odd-degree condition has now supplied the required subfield bound. It remains to assign every ambient direction to at least one copy, with bounded overlap between assignments. Identify the ambient directions with \(\mathbb P^1(\mathbb F_q)=\mathbb F_q\cup\{\infty\}\), using slope. Choose a set \(\Lambda\) of representatives of \(\mathbb F_q^*/\mathbb F_s^*\), with \(1\in\Lambda\). There will be one configuration group for each \(\lambda\in\Lambda\), together with one further group denoted by \(*\). Write \[\mathcal I=\Lambda\sqcup\{*\}, \qquad N_q=|\mathcal I|=\frac{q-1}{s-1}+1.\] Each index \(i\in\mathcal I\) will specify a pool of translates of one configuration. We call this pool a group and will choose one translate from each group. For \(\lambda\in\Lambda\), define \[M_\lambda(x,y)=(x,\lambda y), \qquad S_\lambda=\lambda\mathbb F_s^*, \qquad A_\lambda=\{0,\infty\}.\] Choose distinct \(u,v\in\mathbb F_s^*\) and define \[M_*= \begin{pmatrix}1&1\\u&v\end{pmatrix}, \qquad S_*=(\mathbb F_s\cup\{\infty\})\setminus\{u,v\}, \qquad A_*=\{u,v\}.\] All these linear maps are invertible. For \(M_*\), the image of a finite slope \(t\) is \[\frac{u+vt}{1+t},\] where a zero denominator gives the infinite direction. Its images of the horizontal and vertical directions are \(u\) and \(v\). The induced projective bijection therefore maps the \(s-1\) finite nonzero subfield slopes precisely to \(S_*\). The same statement for \(M_\lambda\) follows from the slope map \(t\mapsto\lambda t\). For each \(i\in\mathcal I\), put \[W_i=M_i(\mathbb F_s^2).\] The directions of joins of distinct points of \(W_i\) form exactly \(S_i\cup A_i\). Each set \(S_i\) has size \(s-1\), and \(A_i\) consists of the two images of the coordinate axes. The cosets \(S_\lambda\) partition all nonzero finite ambient slopes. The extra set \(S_*\) contains \(0\) and \(\infty\). Hence every ambient direction belongs to at least one and at most two sets \(S_i\). More precisely, the directions belonging to two sets are \[ S_1\cap S_* = \mathbb F_s^*\setminus\{u,v\}, \tag{72}\] and the two groups involved are always \(1\) and \(*\). The sets \(S_i\) are the directions whose labels will change, and \(A_i\) are the images of the two axis directions preserved by \(f\). For compatibility between copies we use the slightly larger direction sets \[D_i= \begin{cases} S_i\cup A_i,&i\in\{1,*\},\\ S_i,&i\notin\{1,*\}. \end{cases}\] In particular, \[ D_1=D_*=\mathbb P^1(\mathbb F_s), \tag{73}\] whereas the remaining \(D_i\) are the nonidentity multiplicative cosets of \(\mathbb F_s^*\). Every direction occurs in at most two sets \(D_i\). Since \(|W_i|=s^2\), \(|D_i|\le s+1\), and \(N_q=O_s(q)\), a fixed constant depending only on \(s\) satisfies all size and multiplicity assumptions of Theorem 10. In a conflict-free selection, including the axes in both \(D_1\) and \(D_*\) ensures that an axis line meeting one of these two selected copies cannot also meet the other. This will enter the weighted cover argument for the two groups sharing a direction in (72). Independent candidate poolsLet \(K\) be a fixed pool size supplied by Theorem 10. For each \(i\in\mathcal I\), choose independent uniform shifts \(b_{i,1},\ldots,b_{i,K}\in\mathbb F_q^2\), independently between groups, and write \[P_{i,k}=b_{i,k}+W_i, \qquad Y_{i,k}=b_{i,k}+M_iY.\] Associate to this candidate the following set of ambient deletion lines: \[\mathcal B_{i,k} =\{\ell:\operatorname{dir}(\ell)\in S_i, \ \ell\cap Y_{i,k}\ne\varnothing\}.\] Lemma 13. For every candidate and every \(d\in S_i\), exactly \(s-1\) lines of \(\mathcal B_{i,k}\) have direction \(d\). Each of these lines contains at least five points of \(Y_{i,k}\). Consequently \(|\mathcal B_{i,k}|=(s-1)^2\). Proof. Undo the translation and apply \(M_i^{-1}\). An ambient line in the given direction meeting \(P_{i,k}\) becomes a line through a point of \(\mathbb F_s^2\) in a finite nonzero subfield direction. Its intersection with \(\mathbb F_s^2\) is the corresponding subfield line. The \(s\) lines in that subfield parallel class extend to distinct parallel ambient lines. Exactly one is the omitted line in the definition of \(Y\); the other \(s-1\) each contain at least five points of \(Y\), by Lemma 12. These are precisely the lines meeting the candidate’s retained configuration. ◻ Each candidate therefore prescribes a bounded list of deletion lines. We next apply the deletion lemma to all these independent lists at once. Besides the almost-pencil and line-survival conclusions, we need one bound on how many groups a line can meet along joins from an external point. All three properties will survive the subsequent selection of one candidate per group. Lemma 14. There are constants \(\delta\in(0,1)\) and \(\rho=\delta/10\), independent of \(n\), with the following properties with probability tending to one as \(n\) tends to infinity through odd integers. Let \[X_{\rm pool} =\mathbb F_q^2\setminus \bigcup_{i\in\mathcal I}\bigcup_{k=1}^K \bigcup_{\ell\in\mathcal B_{i,k}}\ell.\]
Proof. We verify the hypotheses of Lemma 9 for the full pool, which gives the first two assertions. The third follows from a separate union bound over finite points and lines. Treat each candidate shift as one independent deletion trial, listing the lines of \(\mathcal B_{i,k}\). There are \(KN_q=O_{s,K}(q)\) trials, each listing \(m=(s-1)^2\) lines. We may take the shape family to be all \(q(q+1)\) ambient affine lines. Each shape has size \(q\), and two distinct line shapes intersect in at most one point. Thus the shape and trial bounds in Lemma 9 hold with a sufficiently large fixed integer \(D\) depending only on \(s,K\). A candidate’s deleting set is a uniform translate of a fixed union of \(m\) lines. Its deletion probability at a fixed point is independent of the point and is at most \(m/q\). Independence of the shifts makes the overall survival probability \(\delta_q\) uniform on \(\mathbb F_q^2\). For sufficiently large \(q\), \(m/q\le1/2\) and \(N_q\le2q/(s-1)\). Using \(\log(1-t)\ge-2t\) for \(0\le t\le1/2\), we obtain \[\delta_q\ge (1-m/q)^{KN_q} \ge \exp\bigl(-2KN_qm/q\bigr) \ge \exp\bigl(-4K(s-1)\bigr).\] Fix \(\delta=\exp(-4K(s-1))\) and \(\rho=\delta/10\). For completeness, the exact-line hypothesis also has a uniform bound. A fixed line \(\ell\) of direction \(d\) can occur only in candidates of groups with \(d\in S_i\), of which there are at most two. In each such candidate, there are \(s-1\) translated lines in this direction. Each fixed line has probability \(1/q\) of becoming \(\ell\) under the uniform shift. Therefore the sum, over all trials, of the probabilities of listing \(\ell\) is at most \[ \frac{2K(s-1)}q. \tag{74}\] Increasing the fixed \(D\) if necessary verifies every hypothesis of Lemma 9. Its conclusions give the first two properties. To prove the third, fix \(p\notin\ell\). For one candidate in group \(i\), there are at most \(s-1\) possible points \(y\in\ell\) whose join to \(p\) has a direction in \(S_i\): each such direction contributes at most one intersection with \(\ell\). A fixed point belongs to a uniform translate of \(W_i\) with probability \(s^2/q^2\). The probability for this candidate is thus at most \[\frac{(s-1)s^2}{q^2}.\] If six distinct groups meet the condition, choose one witnessing candidate from each. There are at most \((KN_q)^6=O_{s,K}(q^6)\) choices, and their shifts are independent. For the fixed pair \((p,\ell)\), the probability of six such groups is therefore \(O_{s,K}(q^{-6})\). There are at most \(q^2q(q+1)=O(q^4)\) pairs \((p,\ell)\). The union bound gives a total failure probability \(O_{s,K}(q^{-2})\), proving the claim. ◻ Selection and transfer of the deletion estimatesThe estimates just proved concern independent candidates. We can now select compatible copies, using only inclusions to transfer the estimates to the selected deletion set. By Theorem 10, with probability tending to one the same pool admits one candidate per group with no conflicts. Intersect this event with those of Lemma 14. No independence between these events is needed. For every sufficiently large odd integer \(n\), their intersection has positive probability, so fix a pool in the intersection and a conflict-free selection. Denote the selected sets and shifts by \[P_i=b_i+M_i(\mathbb F_s^2),\qquad Y_i=b_i+M_iY.\] Conflict avoidance gives the useful implication \[ i\ne j,\quad \operatorname{dir}(\ell)\in D_i,\quad \ell\cap P_i\ne\varnothing \quad\Longrightarrow\quad \ell\cap P_j=\varnothing. \tag{75}\] In particular the \(P_i\) are pairwise disjoint: a common point would give a zero difference, which belongs to every conflict direction, and each \(D_i\) is nonempty. Let \(B\) be the union, as a set of lines, of the deletion lines of the selected candidates, and put \[ X=\mathbb F_q^2\setminus\bigcup_{\ell\in B}\ell. \tag{76}\] Then \(X\supseteq X_{\rm pool}\). Moreover, if \(\ell\notin B\), every selected deletion line belongs to the pool list after all exact occurrences of \(\ell\) have been omitted. Hence \(X\) contains the survivor set of that modified pool process. This inclusion is deterministic: it holds even if \(\ell\) occurs in an unselected candidate and even though the selected shifts depend on the whole pool. In particular, \[ \ell\notin B \quad\Longrightarrow\quad |X\cap\ell|\ge\frac{\delta q}{2}. \tag{77}\] The third property of Lemma 14 also remains available for the selection, since it was established for all candidates in the pool. This completes the placement: the copies are separated, covers of the ordinary survivors by at most \(q\) lines contain an almost pencil, every undeleted line contains at least \(\delta q/2\) survivors, and the bound of five groups remains valid. The order of choices is \(s,Y\), then the selection constant and \(K\), then the deletion constants \(D,\delta,\rho\), and finally \(q=s^n\). Only after fixing these constants do we require \(q=s^n\) to be sufficiently large. All further numerical inequalities below involve these fixed constants and can be imposed by enlarging this final threshold. Thus the construction is available for every sufficiently large odd integer \(n\), with the same \(s,Y\); its pools and selected shifts may depend on \(n\). The constant used for the ambient deletion lemma may depend on \(K\), but it changes no hypothesis of the already applied selection theorem. A small value of \(\delta\) only increases the final lower threshold on \(q\). The hypergraph and its covering numberThe placement supplies the ordinary points \(X\) and the exceptional copies \(Y_i\). We now turn them into edges. Ordinary edges retain all their affine-line labels. In an exceptional copy, the directions \(S_i\) instead use line labels read from \(f(Y)\); all remaining directions retain their ordinary labels. We will first check that every pair of edges still meets, then use the rigidity of \(f(Y)\) to rule out covers of size \(q\). Vertices, edges, and intersectionSet \(r=q+1\). There is one vertex part \(V_d\) for each \(d\in\mathbb P^1(\mathbb F_q)\). For every ambient affine line \(\ell\) of direction \(d\), place an ordinary vertex \(o_\ell\) in \(V_d\). If \(d\in S_i\), let \(t_i(d)\in\mathbb F_s^*\) be the unique subfield direction whose image under \(M_i\) is \(d\). For each of the \(s\) subfield affine lines \(L\) of direction \(t_i(d)\), place a special vertex \(v_{i,d,L}\) in \(V_d\). These subfield lines are read in the new coordinates used for \(f(Y)\). All vertices are formal labels, tagged to be distinct between parts, between ordinary and special types, and between different groups. In particular each \(V_d\) is finite, and the parts are pairwise disjoint. Write \(\ell_d(z)\) for the ambient line of direction \(d\) through \(z\), and \(L_t(w)\) for the subfield line of direction \(t\) through \(w\in\mathbb F_s^2\). Each \(x\in X\) defines the ordinary edge \[e_x=\{o_{\ell_d(x)}:d\in\mathbb P^1(\mathbb F_q)\}.\] For each \(i\in\mathcal I\) and \(w\in Y\), put \(y_{i,w}=b_i+M_iw\) and define an exceptional edge by selecting, in part \(V_d\), the vertex \[ \begin{cases} v_{i,d,L_{t_i(d)}(f(w))},& d\in S_i,\\ o_{\ell_d(y_{i,w})},&d\notin S_i. \end{cases} \tag{78}\] Denote this edge by \(e_{i,w}\), and let \[H=\{e_x:x\in X\}\cup \{e_{i,w}:i\in\mathcal I,\ w\in Y\}.\] Thus an exceptional edge changes labels in the assigned directions, without introducing any new part. Every edge contains exactly one vertex from every part, so \(H\) is \((q+1)\)-partite and \((q+1)\)-uniform. It is nonempty, because \(Y\ne\varnothing\). Figure 1 shows how to read an exceptional edge from its parameter \(w\). The deletion lines were defined from its ordinary base point \(y_{i,w}\), while its special labels use \(f(w)\). The two axis parallel classes are preserved by \(f\), which joins these descriptions in the intersection proof. Proposition 15. The hypergraph \(H\) is intersecting. Furthermore, all the edges in its displayed parametrization are distinct. Proof. There are four types of pairs, according to whether their edges are ordinary or exceptional and, in the latter case, whether their group indices agree. Two ordinary edges with distinct base points share the ordinary label of their join. Next, an exceptional base point \(y\in Y_i\) lies on a deletion line in every direction of the nonempty set \(S_i\), so \(y\notin X\). Its join with \(x\in X\) cannot have direction in \(S_i\): otherwise that join would be a selected deletion line containing \(x\). Its ordinary label therefore belongs to both the exceptional edge and \(e_x\). For exceptional edges from distinct groups \(i,j\), the base points are distinct by (75). That same separation condition ensures that their join has direction outside both \(D_i\) and \(D_j\), and hence outside \(S_i\cup S_j\). The two edges share its ordinary label. Finally, consider \(e_{i,w}\) and \(e_{i,w'}\) with \(w\ne w'\). The transformed points \(f(w),f(w')\) are distinct. If their join has finite nonzero slope \(t\), the exceptional edges share the special label of this subfield line in the part of direction \(M_i(t)\). If their join is horizontal or vertical, the relevant original coordinates are equal as well, because \(f\) preserves these two parallel classes bijectively. The original base points then share an ordinary axis-direction label, in a direction of \(A_i\). This completes the intersection proof. We also check that the parameters count distinct edges, as required when we count exceptional edges below. Two ordinary labels in nonparallel directions determine the ordinary base point, so ordinary edges are distinct. An exceptional edge has special labels and cannot equal an ordinary edge. Within one group, the special labels in any two distinct directions of \(S_i\) determine \(f(w)\), since the corresponding subfield lines are nonparallel. As \(|S_i|=s-1\ge2\), equal exceptional edges within a group would imply \(w=w'\). Finally, any special label tagged by group \(i\) is absent from every edge of a different group. Exceptional edges in distinct groups are therefore distinct too. ◻ Covering vertices in the small-plane coordinatesWe identify the positions of the exceptional edges of group \(i\) with \(f(Y)\), via \(e_{i,w}\leftrightarrow f(w)\). The action of a covering vertex means the subset of these positions whose edges contain that vertex. The next lemma translates every such action into one of the two resources in Lemma 12: a subfield line or an individual point. Lemma 16. Fix a group \(i\).
In particular, the positions covered by any one vertex are contained in a subfield affine line. Proof. The assertions for special vertices and altered ordinary directions follow directly from (78). For an axis direction, undoing \(b_i,M_i\) fixes one original coordinate, so applying \(f\) gives the corresponding horizontal or vertical line. A line in a direction outside \(S_i\cup A_i\) cannot contain two points of \(P_i\), since the join directions of that embedded subplane are exactly \(S_i\cup A_i\). It therefore covers at most one exceptional position. A singleton can be included in an arbitrary subfield line through it, and an empty set requires no covering resource. ◻ The final cover argumentCompletion of the proof of Theorem 1. We prove that \(H\) has no vertex cover of size at most \(q\). Suppose to the contrary that \(C\) is such a cover. Its ordinary vertices, regarded as affine lines, must cover \(X\): special vertices belong to no ordinary edge. These lines also cover \(X_{\rm pool}\). Lemma 14 therefore gives a projective point \(p\) such that at least \((1-\rho)q\) ordinary vertices of \(C\) are lines through \(p\). The line-survival bound will force every undeleted member of this pencil into \(C\). We then count the vertices left for exceptional edges, separating centers at infinity, centers inside one of the sets \(P_i\), and finite centers outside them all. Every undeleted line in this pencil is forced.We claim that \[ p\in\ell,\quad\ell\notin B \quad\Longrightarrow\quad o_\ell\in C, \tag{79}\] where incidence with an infinite \(p\) means that \(\ell\) has the corresponding direction. If \(o_\ell\) were missing, all other lines of \(C\) through \(p\) would cover at most one affine point of \(\ell\). There are at most \(\rho q\) vertices outside the large pencil subcollection. Each of their ordinary lines covers at most one point of \(\ell\), and their special vertices cover no ordinary edge. Consequently \[|X\cap\ell|\le1+\rho q.\] This contradicts (77), since \(\delta q/2>1+\rho q\) for sufficiently large \(q\) and \(\rho=\delta/10\). At infinity the pencil lines are parallel, so the possible contribution of one central point is absent; the same upper bound still applies. Let \(F_p\) be the set of ordinary vertices forced by (79), and call the vertices of \(C\setminus F_p\) the additional vertices. The deleted pencil lines determine how many additional vertices the assumed budget \(|C|\le q\) permits. An infinite center.Suppose \(p\) is the point at infinity in direction \(d\). Put \[I_d=\{i\in\mathcal I:d\in S_i\}, \qquad z=|I_d|\in\{1,2\}.\] Only these groups contribute deletion lines in direction \(d\), and each contributes \(s-1\), by Lemma 13. At most \(z(s-1)\) of the \(q\) lines in this parallel class belong to \(B\). Thus \[|C\setminus F_p|\le z(s-1).\] None of the forced vertices covers any exceptional edge of a group in \(I_d\), because those groups use special vertices in direction \(d\). If \(z=1\), all positions of this group’s \(f(Y)\) must therefore be covered by at most \(s-1\) additional vertices. By Lemma 16, their effects can be included in at most \(s-1\) subfield lines. This contradicts Lemma 12. If \(z=2\), the two groups are \(1,*\), by (72). An additional vertex can now meet both groups, so we use the weighted line-and-point budget instead of counting one line per vertex. For each of these groups let \(a_i\) count the additional vertices that cover at least one of its positions and are either special vertices of this group or ordinary vertices in its axis directions \(A_i\). Let \(b_i'\) count the other additional vertices covering a position of the group. By Lemma 16, the latter vertices each cover only a singleton. The former supply subfield lines. The weighted conclusion of Lemma 12 gives \[ a_i+\frac{b_i'}2\ge s \qquad (i=1,*). \tag{80}\] Each additional vertex contributes at most one to the sum of the two left sides. A special vertex is confined to its tagged group. An ordinary axis-direction vertex counted in \(a_i\) is a line meeting \(P_i\) with direction in \(A_i\subseteq D_i\); by (75) it cannot meet the other group’s \(P_j\). It therefore contributes nothing to that other group, even as a singleton. Any vertex of neither exclusive type contributes at most \(1/2\) to each group. This accounts for every type of additional vertex, including those covering neither group. Summing (80), we obtain \[2s\le a_1+\frac{b_1'}2+a_*+\frac{b_*'}2 \le |C\setminus F_p|\le2(s-1),\] a contradiction. A finite center inside an embedded configuration.Now let \(p\) be finite, and write \[h_p=|\{\ell\in B:p\in\ell\}|.\] There are \(q+1\) affine lines through \(p\), so \[ |F_p|=q+1-h_p, \qquad |C\setminus F_p|\le h_p-1. \tag{81}\] The loss of one in the second inequality comes from the \(q+1\) members of a finite pencil and the assumed cover size \(q\). If \(h_p=0\), the forced vertices already exceed the permitted size of \(C\). We may therefore assume \(h_p\ge1\) in both finite-center cases. Suppose \(p\in P_i\), for the necessarily unique such group. Every deletion line through \(p\) comes from this group: a line from another group would contradict (75), since its direction belongs to that other group’s conflict set. There is at most one such line in each direction of \(S_i\), and hence \[ h_p\le s-1. \tag{82}\] Let \(w_p=M_i^{-1}(p-b_i)\in\mathbb F_s^2\), whether or not \(w_p\in Y\). We account for the exceptional positions of this group covered by \(F_p\): they will all lie on two nonparallel lines in the new coordinates. For a position with base point \(y\ne p\), its join with \(p\) has a direction in \(S_i\cup A_i\). A direction in \(S_i\) cannot cover this edge by an ordinary vertex. Any actual forced coverage must therefore lie along one of the two axis-direction lines through \(p\). A position based at \(p\) itself, if present, lies on both these axes as well. Since \(f\) preserves the two coordinate parallel classes, all these covered positions are contained, in the new coordinates, in the horizontal and vertical lines through \(f(w_p)\). The remaining positions are covered by the additional vertices; each can be included in one subfield line by Lemma 16. Equations (81) and (82) would thus give a cover of \(f(Y)\) by at most \[2+(h_p-1)\le s\] lines containing the two nonparallel coordinate lines. These are legitimate covering resources whether or not their ordinary labels belong to \(F_p\): their union contains every position covered by \(F_p\). Removing any duplicate replacement lines preserves these two distinct lines and can only decrease the count. This contradicts Lemma 12. A finite center outside all embedded configurations.It remains to consider \(p\notin\bigcup_{i\in\mathcal I}P_i\). Here we use the five points on each deletion line, rather than the small-plane cover obstruction. We will find \(5h_p\) exceptional edges missed by \(F_p\), while each additional vertex covers at most five of them. Each group contributes at most one deletion line through \(p\). Indeed, two distinct such lines cannot be parallel. After undoing \(b_i,M_i\), their subfield affine equations have distinct subfield directions. Solving these two equations uses a nonsingular linear system over \(\mathbb F_s\), so their intersection lies in \(\mathbb F_s^2\). This would place \(p\) in \(P_i\), a contradiction. Also, deletion lines from different groups cannot coincide, by (75). The \(h_p\) deletion lines through \(p\) therefore come from \(h_p\) distinct groups. From each such group \(i\), choose five distinct points of \(Y_i\) on its contributing line, possible by Lemma 13. These give \(5h_p\) distinct exceptional edges, by Proposition 15. None is covered by a forced ordinary vertex: its unique join line to \(p\) is precisely its contributing deletion line, whose direction is altered for that group. Any one additional vertex covers at most five of these selected edges. For a special vertex this follows because it belongs to only one group. An ordinary line through \(p\) covers none, by the same unique-join and altered-direction argument. Finally, let an ordinary vertex \(o_\ell\), with \(\ell\) not through \(p\), cover some selected edges. The line \(\ell\) meets each contributing line in at most one point, so \(o_\ell\) covers at most one selected edge from each contributing group. Every such group has a selected point \(y\in Y_i\cap\ell\) whose join to \(p\) has direction in \(S_i\). The third part of Lemma 14, which applies to all candidates and hence to the selection, bounds the number of these groups by five. This proves the asserted bound for every additional vertex. By (81), at most \(h_p-1\) additional vertices are available. They can cover at most \(5(h_p-1)\) of the \(5h_p\) selected edges, a final contradiction. We have ruled out every possible projective center \(p\), and hence every vertex cover of size at most \(q\). Therefore \(\tau(H)\ge q+1\). Conversely, any edge of the nonempty intersecting hypergraph \(H\) is itself a vertex cover and has size \(q+1\). It follows that \[\tau(H)=q+1.\] The parameter choices in Section 6 give this hypergraph for every sufficiently large odd integer \(n\), with \(q=s^n\), after fixing any sufficiently large prime \(s\equiv2\pmod3\) and a successful \(Y\). Choose one such \(Y\) for each eligible \(s\), and let \(n_0(s)\ge3\) exceed all the resulting degree thresholds. This proves Theorem 1. Since there are arbitrarily large odd integers, it also gives infinitely many ranks \(r=q+1\). ◻
Abiad, Aida, Frederik Garbe, Xavier Povill, and Christoph Spiegel. 2025. Infinitely Many Counterexamples to a Conjecture of Lovász. arXiv:2506.21286v2. https://arxiv.org/abs/2506.21286v2.
Abu-Khazneh, Ahmad, János Barát, Alexey Pokrovskiy, and Tibor Szabó. 2019. “A Family of Extremal Hypergraphs for Ryser’s Conjecture.” Journal of Combinatorial Theory, Series A 161: 164–77. https://doi.org/10.1016/j.jcta.2018.07.011.
Aharoni, Ron. 2001. “Ryser’s Conjecture for Tripartite 3-Graphs.” Combinatorica 21 (1): 1–4. https://doi.org/10.1007/s004930170001.
Aharoni, Ron, János Barát, and Ian M. Wanless. 2016. “Multipartite Hypergraphs Achieving Equality in Ryser’s Conjecture.” Graphs and Combinatorics 32 (1): 1–15. https://doi.org/10.1007/s00373-015-1575-9.
Balog, Antal, and Endre Szemerédi. 1994. “A Statistical Theorem of Set Addition.” Combinatorica 14 (3): 263–68. https://doi.org/10.1007/BF01212974.
Best, Darcy, and Ian M. Wanless. 2018. What Did Ryser Conjecture? https://arxiv.org/abs/1801.02893.
Bishnoi, Anurag, Shagnik Das, Patrick Morris, and Tibor Szabó. 2021. “Ryser’s Conjecture for \(t\)-Intersecting Hypergraphs.” Journal of Combinatorial Theory, Series A 179: 105366. https://doi.org/10.1016/j.jcta.2020.105366.
Blokhuis, A., A. E. Brouwer, and T. Szőnyi. 2010. “Covering All Points Except One.” Journal of Algebraic Combinatorics 32: 59–66. https://doi.org/10.1007/s10801-009-0204-1.
Bourgain, Jean, Nets Katz, and Terence Tao. 2004. “A Sum-Product Estimate in Finite Fields, and Applications.” Geometric and Functional Analysis 14 (1): 27–57. https://doi.org/10.1007/s00039-004-0451-1.
Brouwer, A. E., and A. Schrijver. 1978. “The Blocking Number of an Affine Space.” Journal of Combinatorial Theory, Series A 24 (2): 251–53. https://doi.org/10.1016/0097-3165(78)90013-4.
Clow, Alexander, Penny Haxell, and Bojan Mohar. 2026. “A Counterexample to a Conjecture of Lovász.” Combinatorica 46: 26. https://doi.org/10.1007/s00493-026-00220-3.
DeBiasio, Louis, Yigal Kamel, Grace McCourt, and Hannah Sheats. 2021. Generalizations and Strengthenings of Ryser’s Conjecture. arXiv:2009.07239v3. https://arxiv.org/abs/2009.07239v3.
Erdős, P., A. Gyárfás, and L. Pyber. 1991. “Vertex Coverings by Monochromatic Cycles and Trees.” Journal of Combinatorial Theory, Series B 51 (1): 90–95. https://doi.org/10.1016/0095-8956(91)90007-7.
Fox, Jacob, and Benny Sudakov. 2011. “Dependent Random Choice.” Random Structures & Algorithms 38 (1–2): 68–99. https://doi.org/10.1002/rsa.20344.
Francetić, Nevena, Sarada Herke, Brendan D. McKay, and Ian M. Wanless. 2017. “On Ryser’s Conjecture for Linear Intersecting Multipartite Hypergraphs.” European Journal of Combinatorics 61: 91–105. https://doi.org/10.1016/j.ejc.2016.10.004.
Freedman, David A. 1975. “On Tail Probabilities for Martingales.” The Annals of Probability 3 (1): 100–118. https://doi.org/10.1214/aop/1176996452.
Gowers, W. T. 1998. “A New Proof of Szemerédi’s Theorem for Arithmetic Progressions of Length Four.” Geometric and Functional Analysis 8 (3): 529–51. https://doi.org/10.1007/s000390050065.
Haxell, P. E. 1995. “A Condition for Matchability in Hypergraphs.” Graphs and Combinatorics 11 (3): 245–48. https://doi.org/10.1007/BF01793010.
Haxell, P. E. 2001. “A Note on Vertex List Colouring.” Combinatorics, Probability and Computing 10 (4): 345–47. https://doi.org/10.1017/S0963548301004758.
Haxell, P. E., and A. D. Scott. 2012. “On Ryser’s Conjecture.” The Electronic Journal of Combinatorics 19 (1): P23. https://doi.org/10.37236/1175.
Haxell, P. E., and A. D. Scott. 2017. “A Note on Intersecting Hypergraphs with Large Cover Number.” The Electronic Journal of Combinatorics 24 (3): P3.26. https://doi.org/10.37236/6460.
Henderson, John Robert. 1971. “Permutation Decompositions of (0,1)-Matrices and Decomposition Transversals.” PhD thesis, California Institute of Technology. https://doi.org/10.7907/J1Z1-SK19.
Jamison, Robert E. 1977. “Covering Finite Fields with Cosets of Subspaces.” Journal of Combinatorial Theory, Series A 22 (3): 253–66. https://doi.org/10.1016/0097-3165(77)90001-2.
Király, Zoltán, and Lilla Tóthmérész. 2017. “On Ryser’s Conjecture for \(t\)-Intersecting and Degree-Bounded Hypergraphs.” The Electronic Journal of Combinatorics 24 (4): P4.40. https://doi.org/10.37236/6448.
Mansour, Toufik, Chunwei Song, and Raphael Yuster. 2009. “A Comment on Ryser’s Conjecture for Intersecting Hypergraphs.” Graphs and Combinatorics 25 (1): 101–9. https://doi.org/10.1007/s00373-008-0821-9.
Milićević, Luka. 2017. Covering Complete Graphs by Monochromatically Bounded Sets. arXiv:1705.09370v1. https://arxiv.org/abs/1705.09370v1.
OpenAI. 2026. Balanced counterexamples to Ryser’s conjecture at prime orders. OpenAI Math Release preprint OAI:Balanced-Counterexamples-to-Rysers-Conjecture-at-Prime-Orders-September-27-2026.
Petridis, Giorgis. 2012. “New Proofs of Plünnecke-Type Estimates for Product Sets in Groups.” Combinatorica 32 (6): 721–33. https://doi.org/10.1007/s00493-012-2818-5.
Ruzsa, Imre Z. 1999. “An Analog of Freiman’s Theorem in Groups.” In Structure Theory of Set Addition, vol. 258. Astérisque. Société Mathématique de France. https://www.numdam.org/item/AST_1999__258__323_0/.
Tuza, Zsolt. 1983. “Ryser’s Conjecture on Transversals of \(r\)-Partite Hypergraphs.” Ars Combinatoria 16B: 201–9. https://combinatorialpress.com/ars/vol16b/.
White, Patrick. 2026. Tuza’s Ryser-Conjecture Claim for Four-Partite Hypergraphs with Matching Number Two. arXiv:2609.14281v1. https://arxiv.org/abs/2609.14281v1.
|
| ||||||||
|