OctoInformBeta

OpenAI preprint, September 2026 ยท ยง2. The construction and the rank obstruction

Lemma 2.2: Punctured lines in ๐”ฝq20\mathbb{F}_q^{20} with 4r24r^2 incidences at points off an exceptional set, obtained by deleting the marks on short cycles

Marked line data with girth above twelve exist.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The constructed complex KK has vertices OO, VV, WW, and for a natural number rr its edges xiuvx_{iuv} from VV to WW carry a label ii, a line of the data described below, and two indices u,vu, v running over 0,โ€ฆ,rโˆ’10, \dots, r-1. The labels are lines of the affine space P=๐”ฝq20P = \mathbb{F}_q^{20}, for a prime qq, each with a marked point on it, and a label is incident to the points of its line other than its mark. The question is how to choose the lines so that the incidence graph between points and labels has no short cycles while almost every point lies on many lines.

Punctured Lines and Marked Line Data

Let XX be a finite-dimensional vector space over a finite field ๐”ฝ\mathbb{F}, and let โ„™(X)\mathbb{P}(X) be its projective space, whose points, the directions, are the one-dimensional subspaces of XX; a nonzero vector vv spans the direction [v][v]. The line โ„“(a,d)\ell(a,d) through a point aโˆˆXa \in X in a direction d=[v]d = [v] is the set of points โ„“(a,d)={a+tv:tโˆˆ๐”ฝ}.\ell(a,d) = \{\, a + tv : t \in \mathbb{F} \,\}.(1)โœฆ A point zโˆˆXz \in X is incident to the mark aa in direction dd when it lies on the punctured line, the line with its mark removed: zโˆˆโ„“(a,d)\{a}.z \in \ell(a,d) \setminus \{a\}.(2)โœฆ The incidence graph of a relation between two sets AA and BB is the simple graph on the disjoint union AโŠ”BA \sqcup B in which xโˆˆAx \in A and yโˆˆBy \in B are adjacent when they are related, and no two vertices of the same set are adjacent.โœฆ

Let qq be a prime and rr a natural number. Given labels ii with marks aiโˆˆPa_i \in P and directions diโˆˆโ„™(P)d_i \in \mathbb{P}(P), write โ„“i=โ„“(ai,di)\ell_i = \ell(a_i, d_i) and let I(z)I(z) be the set of labels incident to a point zz, those with zโˆˆโ„“i\{ai}z \in \ell_i \setminus \{a_i\}. Marked line data for qq and rr consist of a set SโŠ‚๐”ฝqS \subset \mathbb{F}_q of โŒŠq/100โŒ‹\lfloor q/100 \rfloor scalars, a finite set II of labels whose marks aia_i are distinct points of the grid S20S^{20} of points of PP with all coordinates in SS, a direction diโˆˆโ„™(P)d_i \in \mathbb{P}(P) for each label, and a set EโŠ‚PE \subset P of exceptional points, such that |I(z)|โ‰ฅ4r2for every zโˆˆP\E,|I(z)| \geq 4r^2 \quad \text{for every } z \in P \setminus E,(3) every cycle of the incidence graph of the relation iโˆˆI(z)i \in I(z) between points of PP and labels has length greater than 1212, and, with N=|I|N = |I| the number of labels, 4(2q20+r|E|)<Nr.4\bigl(2q^{20} + r\,|E|\bigr) < N r.(4)โœฆ

Directions and Deletion

Fix a set MโŠ‚XM \subset X of marks and a choice of directions ฯ‰:Mโ†’โ„™(X)\omega \colon M \to \mathbb{P}(X). The degree deg⁡ฯ‰(z)\deg_\omega(z) of a point zโˆˆXz \in X is the number of marks aโˆˆMa \in M to which zz is incident in direction ฯ‰(a)\omega(a).โœฆ The mean degree ฮผM(z)\mu_M(z) of a point zโˆˆXz \in X with respect to MM is the number ฮผM(z)=|M\{z}||โ„™(X)|.\mu_M(z) = \frac{|M \setminus \{z\}|}{|\mathbb{P}(X)|}.(5)โœฆ

Let sโ‰ฅ2s \geq 2. A cycle candidate of length ss is a sequence of distinct points p1,โ€ฆ,psp_1, \dots, p_s of XX, indexed cyclically, together with scalars t1,โ€ฆ,tsโˆˆ๐”ฝt_1, \dots, t_s \in \mathbb{F}, such that the points mk=pk+tk(pk+1โˆ’pk),1โ‰คkโ‰คs,m_k = p_k + t_k\,(p_{k+1} - p_k), \qquad 1 \leq k \leq s,(6)โœฆ on the lines joining consecutive points are distinct marks in MM. The direction of a cycle candidate at kk is [pk+1โˆ’pk][p_{k+1} - p_k], and a cycle candidate occurs under a choice of directions ฯ‰\omega when ฯ‰(mk)=[pk+1โˆ’pk]\omega(m_k) = [p_{k+1} - p_k] for every kk.

A mark aโˆˆMa \in M is deleted under ฯ‰\omega when it is one of the marks mkm_k of a candidate of length at most 66 that occurs under ฯ‰\omega, and retained otherwise. The number of retained marks is written Nฯ‰N_\omega. For a natural number TT, the exceptional set Eฯ‰(T)E_\omega(T) is the set of points of degree less than TT together with the points of the lines through deleted marks: Eฯ‰(T)={zโˆˆX:deg⁡ฯ‰(z)<T}โˆชโ‹ƒa deletedโ„“(a,ฯ‰(a)).E_\omega(T) = \{\, z \in X : \deg_\omega(z) < T \,\} \;\cup \bigcup_{a \text{ deleted}} \ell\bigl(a, \omega(a)\bigr).(7)โœฆ The retained incidence graph ฮ“ฯ‰\Gamma_\omega is the incidence graph between points of XX and retained marks in which zz is adjacent to aa when zโˆˆโ„“(a,ฯ‰(a))\{a}z \in \ell(a, \omega(a)) \setminus \{a\}. The set Iฯ‰(z)I_\omega(z) of retained incidences of a point zz is the set of retained marks adjacent to zz in ฮ“ฯ‰\Gamma_\omega.โœฆ

The Claim

Theorem 1. (a) There are a prime qq and a natural number rr that admit marked line data (S,I,(ai)iโˆˆI,(di)iโˆˆI,E).\bigl(S,\ I,\ (a_i)_{i \in I},\ (d_i)_{i \in I},\ E\bigr).(8)โœฆ

(b) Let r=200โ‹…20020r = 200 \cdot 200^{20}, let qq be a prime with qโ‰ฅ200q \geq 200 and qโ‰ฅ1000โ‹…20020r2q \geq 1000 \cdot 200^{20}\, r^2, and let SโŠ‚๐”ฝqS \subset \mathbb{F}_q be a set of โŒŠq/100โŒ‹\lfloor q/100 \rfloor scalars. Then the grid M=S20M = S^{20} in PP has a choice of directions ฯ‰\omega with 4(2q20+r|Eฯ‰(4r2)|)<Nฯ‰r.4\bigl(2q^{20} + r\,|E_\omega(4r^2)|\bigr) < N_\omega\, r.(9)โœฆ

Let XX be a finite-dimensional vector space over a finite field ๐”ฝ\mathbb{F}, MโŠ‚XM \subset X a set of marks and TT a natural number.

(c) For every choice of directions ฯ‰\omega, every cycle ฮณ\gamma of the retained incidence graph ฮ“ฯ‰\Gamma_\omega has length |ฮณ|>12.|\gamma| > 12.(10)โœฆ

(d) For every choice of directions ฯ‰\omega, every point zโˆ‰Eฯ‰(T)z \notin E_\omega(T) has |Iฯ‰(z)|โ‰ฅT.|I_\omega(z)| \geq T.(11)โœฆ

(e) Let rr be a natural number and ฮผ\mu and BB real numbers with ฮผ>0\mu > 0 and 2Tโ‰คฮผ2T \leq \mu, such that ฮผโ‰คฮผM(z)\mu \leq \mu_M(z) for every zโˆˆXz \in X, the number of deleted marks averaged over all choices of directions ฯ‰:Mโ†’โ„™(X)\omega \colon M \to \mathbb{P}(X) is at most BB, and 8|X|+16r|X|ฮผ+r(4|๐”ฝ|+1)B<|M|r.8|X| + \frac{16\, r\, |X|}{\mu} + r\bigl(4|\mathbb{F}| + 1\bigr)B < |M|\, r.(12) Then some choice of directions ฯ‰\omega satisfies 4(2|X|+r|Eฯ‰(T)|)<Nฯ‰r.4\bigl(2|X| + r\,|E_\omega(T)|\bigr) < N_\omega\, r.(13)โœฆ

In the paper, the result reads: with h=20h = 20, c=100โˆ’20c = 100^{-20}, a natural number rr with crโ‰ฅ100cr \geq 100, P=๐”ฝqhP = \mathbb{F}_q^{h}, m=qhm = q^{h} and SโŠ‚๐”ฝqS \subset \mathbb{F}_q of size โŒŠq/100โŒ‹\lfloor q/100 \rfloor, for all sufficiently large primes qq there are N=(c+o(1))mN = (c + o(1))m affine lines โ„“iโŠ‚P\ell_i \subset P, indexed by a set II, with distinct marked points aiโˆˆShโˆฉโ„“ia_i \in S^{h} \cap \ell_i, and a set EโŠ‚PE \subset P such that (i) the bipartite graph on PโŠ”IP \sqcup I with zโˆผiz \sim i when zโˆˆโ„“i\{ai}z \in \ell_i \setminus \{a_i\} has no cycle of length at most 1212, (ii) |I(z)|โ‰ฅ4r2|I(z)| \geq 4r^2 for zโˆ‰Ez \notin E, and (iii) |E|=o(m)|E| = o(m), so that in particular such data can be fixed with q>rq > r and Nr/4>2m+r|E|Nr/4 > 2m + r|E|.

What Is Checked

The claim is stated over marked line data, with incidence on punctured lines (2) and the incidence graph of points and labels, and, for a set of marks in a finite vector space or the grid S20S^{20} in PP, over the degree and the mean degree (5) of a point, the cycle candidates (6) that occur under a choice of directions, the deleted and retained marks, the exceptional sets (7) and the retained incidences.