betaFeedback

WorksMathematics

Extremal secant size distributions in projective planes

Abstract

Given a point set SS in a projective plane of order qq, each line ℓ\ell determines a secant of size ∣S∩ℓ∣|S\cap \ell|. We study how concentrated this secant-size distribution can be. We develop a general framework for estimating and, in several cases, determining the extremal number. We point out how the extremal constructions vary depending on the remainder of the size of the set modulo qq, and classify several extremal families of point sets, building from concurrent lines, Baer {subplanes} and lines in general position. On the lower bound side, we rely on stability results in the Desarguesian case and applications of the standard equalities in general. Finally, we connect the problem to a novel concept, called general position on level 2 for point and line sets, which then leads to a Sidon-type problem over finite fields called projective Sidon sets, providing an additional arithmetic model for highly concentrated secant-size distributions.

Introduction

A recurring theme in combinatorics and incidence geometry is to understand how a set is distributed with respect to a family of test objects, such as lines, subspaces or, more generally, hyperedges of a hypergraph defined on the ground set. Given an incidence structure—for instance a block design, a finite geometry, or a family of lines or hyperplanes—and a subset SS of the point set, one may study the multiset of intersection sizes

∣S∩B∣|S \cap B|

as BB ranges over the blocks of the structure. A basic question is how concentrated this distribution can be: can one intersection size occur on almost all blocks, or must several different intersection sizes appear with comparable frequency?

Questions of this type arise naturally in many settings. In Euclidean incidence geometry, or after projective completion in the real projective plane, a prime example is the orchard problem due to Jackson [12], which studies the maximum number of 3-rich lines determined by an nn-point set. For the state-of-the-art result on this problem, see the beautiful paper of Green and Tao [10]. A related problem concerns kk-rich lines: lines with prescribed multiplicity kk. In fact, a well-known consequence of the famous Szemerédi–Trotter theorem claims that the number of lines with at least k≥2k \ge2 points in a planar nn-set of points is at most O(n2/k3+n/k)O(n^2/k^3+n/k) [16, 17]. This provides indirect control on large secant classes via incidence limits or collinearity avoidance, and forces the number of short secants to be large in every non-collinear point set, with respect to the number of all kk-secants (k>1k>1). We mention that this phenomenon is far from true in the finite projective setting, see the recent paper of the authors [15].

In this paper we investigate this question in finite projective planes. Let Πq\Pi_q be a projective plane of order qq, with point set P\mathcal{P} and line set L\mathcal{L}, and let N:=q2+q+1N := q^2 + q + 1 denote the number of points, and also the number of lines, of Πq\Pi_q. If the plane is Desarguesian, we denote it by PG⁡(2,q)\operatorname{PG}(2,q).

Definition 1.1 (kk-secants). For a point set S⊆PS \subseteq\mathcal{P} and a line ℓ\ell, we define nℓ:=∣S∩ℓ∣n_\ell:= |S \cap\ell| to be the intersection size of ℓ\ell with SS. A line is called a kk-secant of a set SS if nℓ=kn_\ell= k. In particular, for k=0k = 0 and k=1k = 1, these lines are usually called skew lines and tangent lines of SS, respectively. For an integer kk, let

Lk(S):={ℓ∈L:nℓ=k}L_k(S) := \{\ell\in\mathcal{L} : n_\ell= k\}

denote the set of kk-secant lines.

Definition 1.2. Let sm(S)s_m(S) denote the maximum number of occurrences of any secant size, i.e.,

sm(S):=max⁡k{∣Lk(S)∣}.s_m(S) := \max_k \{|L_k(S)|\}.

Rather than prescribing a particular secant size, we ask a more global extremal question concerning the distribution of the secant sizes.

Problem 1.3. Given a positive integer nn, determine

max⁡{sm(S):∣S∣=n,S⊆P}.\max\{s_m(S) : |S| = n, S \subseteq\mathcal{P}\}.

Equivalently, determine how concentrated the secant-size distribution of an nn-set of points can be.

It is convenient to measure the number of atypical lines instead. Accordingly, we define

M(n,Πq):=N−max⁡{sm(S):S⊆P,∣S∣=n}.M(n,\Pi_q) := N - \max\{s_m(S) : S \subseteq\mathcal{P}, |S| = n\}.

Hence M(n,Πq)M(n,\Pi_q) is the minimum possible number of non-most-common secants among all point sets of size nn in a fixed projective plane Πq\Pi_q. For the Desarguesian plane, we write MD(n,q):=M(n,PG⁡(2,q))M^D(n,q) := M(n,\operatorname{PG}(2,q)).

Our main observation is that the extremal behaviour depends primarily on the residue of nn modulo the order of the plane, qq. Writing

n=qr+t,−q/2<t≤q/2,n = qr + t,\qquad-q/2 < t \le q/2,

separates the cardinality into a multiple of qq and a centered remainder. The remainder tt turns out to be a useful parameter for the extremal problem. When ∣t∣|t| is small, natural candidate configurations arise from unions of concurrent lines and small perturbations thereof. When qq is a square, additional families based on Baer subplanes become competitive for certain remainders on the q\sqrt{q}-scale. Thus the behaviour of M(n,Πq)M(n,\Pi_q) depends strongly on the arithmetic position of nn relative to multiples of qq.

The extremal constructions appearing throughout the paper arise from three geometric mechanisms. First, unions of concurrent lines, i.e., pencils and their small perturbations yield the extremal examples in several ranges where tt is small. In the Desarguesian case, recent stability results imply that these constructions are essentially unique whenever the number of atypical secants is sufficiently small.

Second, when qq is a square, Baer subplanes provide examples with substantially fewer atypical secants than pencils for certain residue classes. These constructions explain the appearance of the q\sqrt{q}-scale in our results and show that the general lower bound obtained from counting cannot be asymptotically improved in several parameter ranges. Further special point-line arrangements also emerge, in connection with so-called (K;N)(K;N)-arcs; in our case nn takes the role of KK being the size of the point set, while NN denotes the prescribed/maximum line-intersection number.

Finally, when n=qr−tn= q^{r}-t, for small positive tt, optimal constructions appear to arise from unions of lines after deleting suitably chosen intersection points. This naturally leads to a new geometric extremal problem concerning line arrangements whose intersection points are themselves in general position. We formulate this notion as general position on level 2. Somewhat unexpectedly, a natural restricted version of the problem leads to a Sidon-type problem over finite fields, thereby providing an arithmetic model for highly concentrated secant-size distributions.

The problem above and our approach to it are closely related to various themes in combinatorial geometry and finite geometry. The characterization of sets with no skew lines or tangents, and, more generally, sets without small secants is the subject of the study of covering and (kk-fold) blocking sets, see for instance Bruen [6], Blokhuis [3], the survey of Ball [1], and the book of Kiss and Szőnyi [13]. Point sets having only a few line-intersection numbers form an active topic in finite geometry [9] which is closely related to block designs, and notable examples are subplanes, complete arcs, (k;n)(k;n)-arcs and Korchmáros-Mazzocca arcs [13]. These are rigid configurations, the line-intersection pattern is supported on very few values. These examples suggest that a very small value of M(n,Πq)M(n,\Pi_q) should usually come from a highly organized geometric construction. One of the themes of the present paper is that this expectation is correct in several ranges of the size of SS. In particular, such conditions often invoke stability-type arguments, see the work of Szőnyi and Weiner [18]. Avoiding a prescribed secant size can also be challenging. We refer to the theory of untouchable (or tangent-free) sets [4, 5] or the recent paper of Héger and Nagy [11] for the general case.

Our first general result is a universal lower bound obtained by the standard equation method, relying on double countings in the projective plane, and a refined application of the Cauchy–Schwarz inequality. Although this estimate is generally not asymptotically sharp, it has the correct order of magnitude for a broad parameter range and closely reflects the behaviour exhibited by the geometric constructions.

Theorem 1.4. Let n=qr+tn=q^{r}+t, 0<n≤(q2+q+1)/20<n\le(q^{2}+q+1)/2, where −q/2<t≤q/2-q/2<t\le q/2. Then

(t(q+1)−r)2qn−qr2+(r−t)2≤M(n,Πq).\frac{(t(q+1)-r)^2}{qn-qr^2+(r-t)^2}\le M(n,\Pi_q).

Similar statement hold for n>(q2+q+1)/2n>(q^{2}+q+1)/2 for complement symmetry reason (cf. Lemma 2.7). As a consequence, the Cauchy–Schwarz bound gives many values of nn for which the number of atypical lines is large.

Theorem 1.5. For every α∈[1,2]\alpha\in[1,2], there are Ω(qα)\Omega(q^\alpha) values of nn such that

M(n,Πq)=Ω(q3−α).M(n,\Pi_q)=\Omega(q^{3-\alpha}).

Theorem 1.4 need not be tight in general, as we will show another natural lower bound on M(n,Πq)M(n,\Pi_q), uniform in almost all nn.

Proposition 1.6. For n∈{0,q+1,q2,q2+q+1}n\in\{0,q+1,q^2,q^2+q+1\}, we have M(n,Πq)∈{0,1}M(n,\Pi_q)\in\{0,1\}. Assume 1≤n≤q2+q1\le n\le q^2+q and n≠q+1,q2n\ne q+1,q^2. Then:

  1. M(n,Πq)=q+1M(n,\Pi_q)=q+1, if n≡0,1(modq)n\equiv0,1\pmod q;

  2. M(n,Πq)>q+1M(n,\Pi_q)>q+1, if n≢0,1(modq)n\not\equiv0,1\pmod q.

In the Desarguesian case, we will use much stronger stability-type results, which will enable us to characterize as well the sets where M(n,Πq)M(n,\Pi_q) is small.

The paper is organized as follows. In § 2, we collect notation, basic identities, and the external geometric results used later as black boxes. In § 3, we discuss how small M(n,Πq)M(n,\Pi_q) can be and prove general lower bounds by counting and structural arguments, including the Cauchy–Schwarz bound and the blocking-set method. Then in § 4, we examine which constructions yield matching or competitive upper bounds, and present explicit constructions and the resulting upper bounds on M(n,Πq)M(n,\Pi_q). We continue by studying under what conditions these constructions are the only extremal configurations in § 5. We examine the Desarguesian case in detail, where earlier stability theorems allow stronger conclusions. Finally, § 6 revisits the constructions for point sets with n=qr+tn=qr+t with −q/2<t<0-q/2<t<0. Here a natural candidate construction, taking unions of lines and deleting suitably arranged intersection points, leads naturally to the concept of the so-called general position on level 2 and to an additive combinatorial problem related to Sidon sets, which might be of independent interest.

Definitions and basic observations

Recall (Definition 1.1 and Definition 1.2) that Lk={ℓ∈L:nℓ=k}L_k=\{\ell\in\mathcal{L}:n_\ell=k\} denotes the set of kk-secants and sm(S)=max⁡k{∣Lk(S)∣}s_m(S)=\max_k\{|L_k(S)|\} denotes the maximum frequency of the secant sizes.

Definition 2.1 (Dominant lines and atypical lines). Let S⊆PS\subseteq\mathcal{P}. Choose a secant size κ\kappa and call it a dominant secant size if ∣Lκ(S)∣=sm(S)|L_\kappa(S)|=s_m(S), and call other secant sizes atypical. A line ℓ\ell is called dominant if nℓ=κn_\ell=\kappa for the chosen dominant secant size κ\kappa, and atypical otherwise.

Note that the dominant secant size need not be unique in general, it is unique for every extremal point set when q≥4q\geq4; see Proposition 4.5.

We recall our main extremal quantity from the introduction: M(n,Πq)M(n,\Pi_q) is the minimum possible number of atypical lines among nn-point sets. The investigation of the size of the set of atypical lines will capture better the dependence on nn and qq.

Definition 2.2.

  • A pencil is a set of concurrent lines (often identified with their point set). A punctured pencil is obtained from the point set of a pencil by removing the intersection point of its lines. A carrier is the intersection point of the lines of the pencil.

  • A set of lines BB in Πq\Pi_q is a covering line set if every point of Πq\Pi_q lies on at least one line of BB. Dually, a point set BB is a blocking set if every line meets BB.

  • A point set UU is untouchable, or is a set without tangents if ∣ℓ∩U∣≠1|\ell\cap U| \ne1 for every line ℓ\ell.

  • An oval in a projective plane of order qq is a set of q+1q+1 points no three of which are collinear. If qq is even, a hyperoval is a set of q+2q+2 points no three of which are collinear.

Theorem 2.3 (Lower bounding the size of minimal blocking sets, Bruen-Pelikán, Blokhuis, [6, 3]). Let BB be a blocking set in a projective plane of order qq. If BB does not contain a line, then ∣B∣≥q+q+1|B| \ge q+\sqrt{q}+1. Moreover, equality implies that qq is a square and BB is a Baer subplane.

If qq is prime and the plane is Desarguesian, Πq=PG⁡(2,q)\Pi_q = \operatorname{PG}(2,q), then every blocking set not containing a line has size at least 3(q+1)2\frac{3(q+1)}{2}.

Theorem 2.4 (Blokhuis–Seress–Wilbrink). If qq is odd, then every nonempty set without tangents in PG⁡(2,q)\operatorname{PG}(2,q) has size at least q+2q4+2q+\frac{\sqrt{2q}}{4}+2.

As we indicated in the first section, the problem turns out to be connected to additive combinatorial concepts, most notably to Sidon sets.

Definition 2.5. Let GG be an Abelian group and let A⊆GA \subseteq G. A set AA is called a Sidon set (or B2B_2 set) if the equation a+b=xa+b=x (a,b∈Aa,b \in A) has at most one unordered solution (a,b)(a,b) for all x∈Gx \in G.

More generally, a set AA is called a B2(h)B_2(h) set (or hh-Sidon set) if every x∈Gx \in G has at most hh unordered representations of the form x=a+bx=a+b with a,b∈Aa,b \in A.

Finally, we call AA a B2∗(h)B_2^*(h)-set (or h∗h^*-Sidon set) if every x∈Gx \in G has at most hh unordered representations

x=a+b,a,b∈A,a≠b.x=a+b,\qquad a,b \in A,\qquad a \ne b.

Result 2.6. [7] Let GG be a finite Abelian group of order NN. If A⊆GA \subseteq G is a B2(h)B_2(h) set, then

∣A∣≤2hN+O(1),|A| \le\sqrt{2hN}+O(1),

moreover, ∣A∣≤N+1|A| \le\sqrt{N}+1 for h=1h=1. Moreover, for every fixed hh,

max⁡{∣A∣:A⊆ZN is B2(h)}=Ω(hN).\max\{|A|: A \subseteq\mathbb{Z}_N\text{ is }B_2(h)\}=\Omega(\sqrt{hN}).

The same holds for B2∗(h)B_2^*(h)-sets, as

max⁡{∣A∣:A⊆ZN is B2∗(h)}=Ω(hN).\max\{|A|: A \subseteq\mathbb{Z}_N\text{ is }B_2^*(h)\}=\Omega(\sqrt{hN}).

To distinguish between the general case and the classical setting, we denote by MD(n,q)M^D(n,q) the minimum number of non-κ\kappa-secants specifically when the projective plane is Desarguesian.

We start with the simple complement symmetry.

Lemma 2.7. M(n,Πq)=M(q2+q+1−n,Πq)M(n,\Pi_q)=M(q^2+q+1-n,\Pi_q).

Proof. Observe that Lk(S)=Lq+1−k(Sc)L_k(S)=L_{q+1-k}(S^c), where ScS^c is the complement of the set SS in the projective plane. The claim follows.

Next we record the standard equalities.

Lemma 2.8 (Standard equalities). Let S⊆ΠqS\subseteq\Pi_q with ∣S∣=n|S|=n. Then

∑k∣Lk(S)∣=N,(1)\sum_k |L_k(S)|=N, \tag*{(1)}
∑kk∣Lk(S)∣=n(q+1),(2)\sum_k k|L_k(S)|=n(q+1), \tag*{(2)}
∑kk(k−1)∣Lk(S)∣=n(n−1),(3)\sum_k k(k-1)|L_k(S)|=n(n-1), \tag*{(3)}
∑kk2∣Lk(S)∣=n(n+q).(4)\sum_k k^2|L_k(S)|=n(n+q). \tag*{(4)}

Lemma 2.9. The following values hold for M(n,Πq)M(n,\Pi_q) in any projective plane.

  1. If n=0,q2+q+1n=0,q^2+q+1 then M(n,Πq)=0M(n,\Pi_q)=0;

  2. If n=1n=1 or n=q2+qn=q^2+q, then M(n,Πq)=q+1M(n,\Pi_q)=q+1.

  3. If n∈{q+1,q2}n\in\{q+1,q^2\} then M(n,Πq)=1M(n,\Pi_q)=1.

Proof. (1) and (2) follow immediately from the definition of M(n,Πq)M(n,\Pi_q). Counting the number of points in a set on the lines through a point in the set and a point not in the set shows that M(n,Πq)=0M(n,\Pi_q)=0 iff n=0,q2+q+1n=0,q^2+q+1. The number of non-1-secants of the set of points of a line is 1 (the line itself), which then proves (3).

General results and lower bounds for Problem 1.3

A general Cauchy-Schwarz bound

Now we turn to the main general counting inequality. Recall that N=(q2+q+1)N=(q^2+q+1).

Proposition 3.1. Suppose that S⊆PS\subseteq\mathcal{P} with ∣S∣=n=qr+t|S|=n=qr+t, 0<n≤(q2+q+1)/20<n\le(q^2+q+1)/2, where −q/2<t≤q/2-q/2<t\le q/2. Then

sm(S)≤n(n+q)N−n2(q+1)2Nr2+n(q+n)−2n(q+1)rs_m(S)\le\frac{n(n+q)N-n^2(q+1)^2}{Nr^2+n(q+n)-2n(q+1)r}

i.e.,

M(n,Πq)≥(t(q+1)−r)2qn−qr2+(r−t)2.M(n,\Pi_q)\ge\frac{(t(q+1)-r)^2}{qn-qr^2+(r-t)^2}.

Proof. Let us choose κ\kappa such that ∣Lκ(S)∣=sm(S)|L_\kappa(S)|=s_m(S). Put

m:=N−∣Lκ(S)∣=N−sm(S).m:=N-|L_\kappa(S)|=N-s_m(S).

Thus exactly mm lines lie outside Lκ(S)L_\kappa(S). Writing up the standard equations, cf. Lemma 2.8, we obtain that

∑ℓ∉Lκnℓ=n(q+1)−(N−m)κ,∑ℓ∉Lκnℓ(nℓ−1)=n(n−1)−(N−m)κ(κ−1).(5)\sum_{\ell\notin L_{\kappa}} n_{\ell}=n(q+1)-(N-m)\kappa,\qquad\sum_{\ell\notin L_{\kappa}}n_{\ell}(n_{\ell}-1)=n(n-1)-(N-m)\kappa(\kappa-1). \tag*{(5)}

The Cauchy-Schwarz inequality then implies

(∑ℓ∉Lκnℓ)2≤∑ℓ∉Lκnℓ2⋅m=[(n(q+1)−(N−m)κ)+(n(n−1)−(N−m)κ(κ−1))]⋅m=[n(q+n)−(N−m)κ2]⋅m.(6)\begin{aligned} \left(\sum_{\ell\notin L_{\kappa}}n_{\ell}\right)^2\leq\sum_{\ell\notin L_{\kappa}}n_{\ell}^2\cdot m \\ &= \left[(n(q+1)-(N-m)\kappa)+(n(n-1)-(N-m)\kappa(\kappa-1))\right]\cdot m \\ &= \left[n(q+n)-(N-m)\kappa^2\right]\cdot m. \tag*{(6)} \end{aligned}

Note that in the last step, we used the fact that ∑ℓ∉Lκnℓ2=∑ℓ∉Lκnℓ(nℓ−1)+∑ℓ∉Lκnℓ\sum_{\ell\notin L_{\kappa}}n_{\ell}^2=\sum_{\ell\notin L_{\kappa}}n_{\ell}(n_{\ell}-1)+\sum_{\ell\notin L_{\kappa}}n_{\ell} clearly holds. Hence,

(n(q+1)−(N−m)κ)2≤[n(q+n)−(N−m)κ2]⋅m,(n(q+1)-(N-m)\kappa)^2\leq[n(q+n)-(N-m)\kappa^2]\cdot m,

that is,

(N−m)(Nκ2+n(q+n)−2n(q+1)κ)≤(−n2(q+1)2+n(n+q)N).(N-m)(N\kappa^2+n(q+n)-2n(q+1)\kappa)\leq(-n^2(q+1)^2+n(n+q)N).

The minimum of mm could be derived from here by minimizing the coefficient of (N−m)(N-m)

Nκ2+n(q+n)−2n(q+1)κN\kappa^2+n(q+n)-2n(q+1)\kappa

in κ\kappa. Since this is a quadratic inequality, the optimal choice can be derived studying the corresponding discriminant. Since n<N/2n<N/2 and n=qr+tn=qr+t with −q/2<t≤q/2-q/2<t\leq q/2, we have

∣n(q+1)N−r∣<12.\left|\frac{n(q+1)}{N}-r\right|<\frac{1}{2}.

Thus rr is the integer minimizing A(k):=Nk2+n(n+q)−2n(q+1)kA(k):=Nk^2+n(n+q)-2n(q+1)k. In particular, A(κ)≥A(r)A(\kappa)\geq A(r) for every dominant secant size κ\kappa. Substituting this into the preceding inequality yields the claim. □\square

Remark 3.2. Equality in the upper bound of Proposition 3.1 on sms_m can occur only if all atypical lines have the same intersection size with SS. Thus equality in the resulting lower bound for M(n,Πq)M(n,\Pi_q) requires, in particular, that the dominant secant size be the minimizing integer rr and that nℓn_{\ell} be constant over all ℓ∉Lr(S)\ell\notin L_r(S). Such an equality case therefore gives rise to a highly regular incidence structure, closely related to a block design.

Proof of Theorem 1.5. Let

R:=max⁡{1,⌊cqα−1⌋},R:=\max\{1,\lfloor cq^{\alpha-1}\rfloor\},

where c>0c>0 is a sufficiently small constant, and choose 1≤r≤R1\leq r\leq R and ⌈q/8⌉≤t≤⌊q/4⌋\lceil q/8\rceil\leq t\leq\lfloor q/4\rfloor and hence t=Ω(q)t=\Omega(q). Proposition 3.1 ensures that for n=qr+tn=qr+t we have

M(n,Πq)≥(t(q+1)−r)2qn−qr2+(r−t)2.M(n,\Pi_q)\geq\frac{(t(q+1)-r)^2}{qn-qr^2+(r-t)^2}.

We estimate the numerator and denominator separately. Since t≥q/8t\geq q/8 and r≤R=O(qα−1)r\leq R=O(q^{\alpha-1}), we have t(q+1)−r≫q2t(q+1)-r\gg q^2, and therefore (t(q+1)−r)2≫q4(t(q+1)-r)^2\gg q^4. On the other hand, qn−qr2+(r−t)2=qr(q−r)+qt+(r−t)2qn-qr^2+(r-t)^2=qr(q-r)+qt+(r-t)^2. As r≤Rr\le R, we have qr(q−r)≤q2r≪qα+1qr(q-r)\le q^2r\ll q^{\alpha+1}, while qt≪q2qt\ll q^2, and (r−t)2≪q2(r-t)^2\ll q^2 holds. Since α≥1\alpha\ge1, it follows that qn−qr2+(r−t)2≪qα+1qn-qr^2+(r-t)^2\ll q^{\alpha+1}. Consequently,

M(n,Πq)≫q4qα+1=q3−α.M(n,\Pi_q)\gg\frac{q^4}{q^{\alpha+1}}=q^{3-\alpha}.

It remains to count the number of admissible values of nn. There are R=Ω(qα−1)R=\Omega(q^{\alpha-1}) admissible values for rr and Ω(q)\Omega(q) possible choices for tt, hence Ω(qα)\Omega(q^\alpha) pairs (r,t)(r,t). Since n=qr+tn=qr+t and 0<t<q0<t<q, distinct pairs (r,t)(r,t) yield distinct values of nn. Thus there are Ω(qα)\Omega(q^\alpha) values of nn for which M(n,Πq)≫q3−αM(n,\Pi_q)\gg q^{3-\alpha}.

Stability results when the set has small size

Lemma 3.3. Suppose that tt-arcs exist in Πq\Pi_q for all t≤(2−2)q+1t\le(2-\sqrt{2})q+1. (Note that for Desarguesian planes, this holds in a strong sense, for all t≤q+1t\le q+1).

If n≤⌊2q+32−2q2+4q+14⌋≈(2−2)qn\le\left\lfloor2q+\frac{3}{2}-\sqrt{2q^2+4q+\frac{1}{4}}\right\rfloor\approx(2-\sqrt{2})q, then M(n,Πq)=M(q2+q+1−n,Πq)=n(q+1)−(n2)M(n,\Pi_q)=M(q^2+q+1-n,\Pi_q)=n(q+1)-\binom{n}{2}, while if q≥n>⌊2q+32−2q2+4q+14⌋q\ge n>\left\lfloor2q+\frac{3}{2}-\sqrt{2q^2+4q+\frac{1}{4}}\right\rfloor, then M(n,Πq)=M(q2+q+1−n,Πq)=q2+q+1−qnM(n,\Pi_q)=M(q^2+q+1-n,\Pi_q)=q^2+q+1-qn.

Proof. The transition point will be determined by comparing ∣L0∣|L_0| and ∣L1∣|L_1|. Suppose first that 1<n≤⌊2q+32−2q2+4q+14⌋1<n\le\left\lfloor2q+\frac{3}{2}-\sqrt{2q^2+4q+\frac{1}{4}}\right\rfloor and SS is an arbitrary nn-element set. Then ∣Lk(S)∣≤(n2)|L_k(S)|\le\binom{n}{2} for all k≥2k\ge2, while ∣L1(S)∣≤nq|L_1(S)|\le nq holds. Let S0S_0 be an nn-arc. Hence it is enough to show that ∣L0(S0)∣=q2+q+1−(q+1)n+(n2)≥max⁡{nq,(n2)}|L_0(S_0)|=q^2+q+1-(q+1)n+\binom{n}{2}\ge\max\{nq,\binom{n}{2}\} holds. The inequality in turn follows from the upper bound on nn.

On the other hand, suppose next that q≥n>⌊2q+32−2q2+4q+14⌋q\ge n>\left\lfloor2q+\frac{3}{2}-\sqrt{2q^2+4q+\frac{1}{4}}\right\rfloor and SS is an arbitrary nn-element set. Then ∣Lk(S)∣≤(n2)|L_k(S)|\le\binom{n}{2} for all k≥2k\ge2, while ∣L0(S)∣≤q2+q+1−(q+1)n+(n2)|L_0(S)|\le q^2+q+1-(q+1)n+\binom{n}{2} holds. Let S1S_1 be a set of collinear points. Hence it is enough to show that ∣L1(S1)∣=qn≥max⁡{q2+q+1−(q+1)n+(n2),(n2)}|L_1(S_1)|=qn\ge\max\{q^2+q+1-(q+1)n+\binom{n}{2},\binom{n}{2}\} holds. The inequality in turn follows from the upper bound on nn.

Lemma 3.4. If for a set SS, the set of lines L(Πq)∖Lκ(S)\mathcal{L}(\Pi_q)\setminus L_{\kappa}(S) does not cover all points of the projective plane then either ∣S∣=(q+1)κ(S)|S|=(q+1)\kappa(S) or ∣Sc∣=(q+1)(q+1−κ(S))|S^c|=(q+1)(q+1-\kappa(S)).

Proof. Let PP be a point incident only with κ(S)\kappa(S)-secants. If P∉SP\notin S, then the q+1q+1 lines through PP partition SS, whence ∣S∣=(q+1)κ(S)|S|=(q+1)\kappa(S).

If P∈SP\in S, then every line through PP contains κ(S)−1\kappa(S)-1 further points of SS, and hence ∣S∣=1+(q+1)(κ(S)−1)|S|=1+(q+1)(\kappa(S)-1). Equivalently, ∣Sc∣=(q+1)(q+1−κ(S))|S^c|=(q+1)(q+1-\kappa(S)).

Lemma 3.5. Let SS be a non-empty set in Πq\Pi_q and assume that neither SS nor ScS^c is a line. Suppose also that the non-κ(S)\kappa(S)-secants do not cover all points of the plane. Then through each point there pass 0 or at least 2 non-κ(S)\kappa(S)-secants of SS. In particular, SS has either 0 or at least q+2q+2 non-κ(S)\kappa(S)-secants.

Proof. By Lemma 3.4 and Lemma 2.7 we may suppose that ∣S∣=κ(S)(q+1)|S|=\kappa(S)(q+1) (i.e., there exists a point outside SS with only κ(S)\kappa(S)-secants through it). If now QQ is a point with exactly one non-κ(S)\kappa(S)-secant line ℓ\ell through it, then QQ must be in SS. Counting the points of SS on the lines through QQ, we get that ∣ℓ∩S∣=q+κ(S)|\ell\cap S|=q+\kappa(S) and so κ(S)=0,1\kappa(S)=0,1. Since SS is non-empty with size ∣S∣=κ(S)(q+1)|S|=\kappa(S)(q+1), κ(S)\kappa(S) must be 1 and ∣S∣=q+1|S|=q+1. Again looking around QQ we see that SS is a line, which contradicts our assumption. Hence through each point there pass 0 or at least 2 non-κ(S)\kappa(S)-secants of SS. If a non-κ(S)\kappa(S)-secant exists then counting the non-κ(S)\kappa(S)-secants through the points of this secant we see at least q+2q+2 of them.

Lemma 3.6. Let SS be a set with less than 2q+12q+1 lines not in Lκ(S)L_{\kappa(S)}. Assume also that among these lines there are q+1q+1 through a point PP. Then SS is:

  1. a pencil or a punctured pencil,

  1. a point set of a line and a disjoint point

  1. the complement of (2).

Proof. Note that on each line through PP there must exist a point Q≠PQ \ne P such that PQPQ is the unique non-κ(S)\kappa(S)-secant through QQ. Assume that Q1Q_1 and Q2Q_2 are such points so that the line PQ1PQ_1 is different from PQ2PQ_2. If Q1∈SQ_1 \in S but Q2∉SQ_2 \notin S, then counting the number of points of SS on the lines through Q1Q_1 and through Q2Q_2, we get that

∣S∣=κq+∣PQ2∩S∣=(κ−1)q+∣PQ1∩S∣,|S| = \kappa q + |PQ_2 \cap S| = (\kappa- 1)q + |PQ_1 \cap S|,

thus ∣S∩{PQ1∖{P}}∣=q|S \cap\{PQ_1 \setminus\{P\}\}| = q and ∣S∩{PQ2∖{P}}∣=0|S \cap\{PQ_2 \setminus\{P\}\}| = 0; and hence SS is a pencil or a punctured pencil. Otherwise we see the same number of points of SS on each line through PP. Write a=∣(ℓ∖{P})∩S∣a = |(\ell\setminus\{P\}) \cap S|. The cases a=0,qa = 0,q again give pencils or punctured pencils, so assume 0<a<q0 < a < q. By complementation, we may assume P∉SP \notin S. Then n=a(q+1)n = a(q+1). As mentioned before on each line through PP, there exists a point RR, through which RPRP is the only non-κ\kappa-secant. Clearly, R∈SR \in S otherwise we get that κ(S)=a\kappa(S) = a and hence the lines through PP are in Lκ(S)L_{\kappa(S)}. Counting the points of SS on the lines through RR we get that κ(S)−1=a\kappa(S) - 1 = a.

Set S′=S∪{P}S' = S \cup\{P\}. All lines through PP are now κ\kappa-secants, and fewer than qq other lines are not. In particular, κ\kappa is dominant for S′S'. These exceptional lines do not cover the plane. By Lemma 3.5 and Lemma 2.9, S′S' is a line, the complement of a line, the empty set, or the whole plane. Since ∣S′∣=a(q+1)+1|S'| = a(q+1)+1 and 0<a<q0 < a < q, only the complement of a line is possible. Thus SS is the complement of a line together with an external point. Undoing complementation gives the remaining possibility.

Lemma 3.7. Assume 1<n<q2+q1 < n < q^2 + q and n≠q+1,q2n \ne q+1,q^2, then:

  1. M(n,Πq)=q+1M(n,\Pi_q) = q+1, if n≡0,1(modq)n \equiv0,1 \pmod q;

  1. M(n,Πq)>q+1M(n,\Pi_q) > q+1, if n≢0,1(modq)n \not\equiv0,1 \pmod q.

Proof. Let SS be a set of size nn. If its non-κ(S)\kappa(S)-secants do not cover the plane, then Lemma 3.5, Lemma 2.9 and our assumption on nn give at least q+2q+2 such lines. If they cover the plane, then by Theorem 2.3 there are at least q+1q+1 of them, with equality only if they form a pencil. Thus M(n,Πq)≥q+1M(n,\Pi_q) \ge q+1.

If equality holds, the non-κ(S)\kappa(S)-secants form a pencil, so Lemma 3.6 applies. A line plus an external point and its complement have q+2q+2 non-dominant secants; hence SS is a pencil or a punctured pencil, and n≡0,1(modq)n \equiv0,1 \pmod q. If n≡0,1(modq)n \equiv0,1 \pmod q, we can choose a pencil or a punctured pencil of size nn with exactly q+1q+1 non-κ(S)\kappa(S)-secants.

Lemma 3.8. Assume that a set SS admits q+2q+2 non-κ(S)\kappa(S)-secants, l1,l2,…lq+2l_1,l_2,\ldots l_{q+2} forming a dual hyperoval. Then SS is one of the following

  1. the set of all points lying on one of the lines lil_i, 1≤i≤q+21 \le i \le q + 2;

  1. the set of all points lying on one of the lines lil_i, 1≤i≤q+21 \le i \le q + 2, except those on a fixed line ljl_j.

  1. the complement of either (1) or (2).

Proof. For any point not lying on any of the lines lil_i, we see only κ(S)\kappa(S)-secants of SS through it and so either all points outside the lines lil_i are in SS or none. By taking the complement if necessary, we may assume that none of these points belongs to SS. Counting through any such point gives ∣S∣=(q+1)κ(S)|S| = (q + 1)\kappa(S).

If no lil_i contains both a point of SS and a point outside SS, then each lil_i is either contained in SS or disjoint from it. Since the lil_i meet pairwise, they must all be of the same kind. They cannot all be disjoint, as then SS would be empty. Thus (1) holds. Now pick a line lil_i which is not a κ(S)\kappa(S)-secant of SS and assume that there exist points Q∈li∩SQ \in l_i \cap S and R∈{li∖S}R \in\{l_i \setminus S\}. Let lQl_Q and lRl_R be the other non-κ(S)\kappa(S)-secants of SS through QQ and through RR, we get that either ∣lQ∩S∣=q+1|l_Q \cap S| = q + 1 and ∣lR∩S∣=1|l_R \cap S| = 1 or ∣lQ∩S∣=q|l_Q \cap S| = q and ∣lR∩S∣=0|l_R \cap S| = 0.

More generally, counting through the intersection of two distinct lines la,lbl_a,l_b among the lil_i gives

∣la∩S∣+∣lb∩S∣={2κ(S)+q,la∩lb∈S,2κ(S),la∩lb∉S.|l_a \cap S| + |l_b \cap S| = \begin{cases} 2\kappa(S) + q, & l_a \cap l_b \in S,\\ 2\kappa(S), & l_a \cap l_b \notin S. \end{cases}

Suppose first that ∣lQ∩S∣=q|l_Q \cap S| = q and ∣lR∩S∣=0|l_R \cap S| = 0. Since lRl_R is disjoint from SS, the displayed equality gives ∣lj∩S∣=2κ(S)|l_j \cap S| = 2\kappa(S) for every lj≠lRl_j \ne l_R. In particular, 2κ(S)=∣lQ∩S∣=q2\kappa(S) = |l_Q \cap S| = q. Thus every lj≠lRl_j \ne l_R contains all its points outside lRl_R in SS, giving (2).

In the other case, ∣lQ∩S∣=q+1|l_Q \cap S| = q + 1 and ∣lR∩S∣=1|l_R \cap S| = 1. The point lQ∩lRl_Q \cap l_R belongs to SS, so the displayed equality gives κ(S)=1\kappa(S) = 1. For any lj≠lQ,lRl_j \ne l_Q,l_R, the point lj∩lRl_j \cap l_R is not in SS, and hence ∣lj∩S∣=1=κ(S)|l_j \cap S| = 1 = \kappa(S). This contradicts the choice of the ljl_j. Taking complements gives (3).

For q=2q = 2, Lemmas 2.9 and 3.7 already determine all values of M(n,Π2)M(n,\Pi_2). For q≥3q \ge3, the next corollary follows from the preceding lemmas and the dual form of Theorem 2.3.

Corollary 3.9. Suppose that q≥3q \ge3 and 0<n<q2+q+10 < n < q^2 + q + 1. Then M(n,Πq)>q+2M(n,\Pi_q) > q + 2, unless n≡0,1(modq)n \equiv0, 1 \pmod q, n∈{q+2,q2−1}n \in\{q + 2, q^2 - 1\}, or Πq\Pi_q admits a dual hyperoval and

n∈{(q+1)(q+2)2,q(q+1)2,q(q−1)2,q2+q+22}.n \in\left\{ \frac{(q + 1)(q + 2)}{2}, \frac{q(q + 1)}{2}, \frac{q(q - 1)}{2}, \frac{q^2 + q + 2}{2} \right\}.

Structural arguments relying on blocking sets

Proposition 3.10. Let S⊆ΠqS \subseteq\Pi_q, and let κ\kappa be a dominant secant size. If

∣S∣≢0,1(modq+1),|S| \not\equiv0,1 \pmod{q+1},

then the non-κ\kappa-secants form a covering line set.

Proof. If some point is not covered by a non-κ\kappa-secant, Lemma 3.4 gives either ∣S∣=(q+1)κ|S| = (q + 1)\kappa or

∣Sc∣=(q+1)(q+1−κ(S)).|S^c| = (q + 1)(q + 1 - \kappa(S)).

In the first case ∣S∣≡0(modq+1)|S| \equiv0 \pmod{q + 1}, while in the second ∣S∣=q2+q+1−(q+1)(q+1−κ(S))≡1(modq+1)|S| = q^2 + q + 1 - (q + 1)(q + 1 - \kappa(S)) \equiv1 \pmod{q + 1}. This proves the claim.

Proposition 3.11. Let S⊆ΠqS \subseteq\Pi_q, let κ\kappa be a dominant secant size of SS, and suppose that

∣S∣≢0,1(modq+1).|S| \not\equiv0,1 \pmod{q+1}.

If SS is neither a pencil nor a punctured pencil, then

N−∣Lκ(S)∣≥q+q+1.N-|\mathcal{L}_{\kappa}(S)| \ge q+\sqrt{q}+1.

Proof. Put B=L\Lκ(S)\mathcal{B}=\mathcal{L}\backslash\mathcal{L}_{\kappa}(S). By Proposition 3.10, B\mathcal{B} is a covering line set. Suppose that ∣B∣<q+q+1|\mathcal{B}|<q+\sqrt{q}+1. Choose an inclusion-minimal covering subset B0⊆B\mathcal{B}_0\subseteq\mathcal{B}. By dual Bruen, either ∣B0∣≥q+q+1|\mathcal{B}_0|\ge q+\sqrt{q}+1, contradiction, or B0\mathcal{B}_0 contains a full pencil. But because B0\mathcal{B}_0 is minimal, in the latter case it is exactly that pencil. Hence B\mathcal{B} contains all q+1q+1 lines through some point. Since ∣B∣<q+q+1<2q+1|\mathcal{B}|<q+\sqrt{q}+1<2q+1, Lemma 3.6 applies and says that SS is a pencil, a punctured pencil, a line plus an external point, or the complement of the latter. The first two are excluded; the last two have cardinalities q+2≡1(modq+1)q+2\equiv1\pmod{q+1} and q2−1≡0(modq+1)q^2-1\equiv0\pmod{q+1}, so they are also excluded. □\square

Proposition 3.12. Suppose that n≢0,1(modq)n\not\equiv0,1\pmod q, n≢0,1(modq+1)n\not\equiv0,1\pmod{q+1} then M(n,Πq)≥q+q+1M(n,\Pi_q)\ge q+\sqrt{q}+1.

Proof. Choose an nn-point set SS attaining M(n,Πq)M(n,\Pi_q). A pencil has size rq+1rq+1, while a punctured pencil has size rqrq, so n≢0,1(modq)n\not\equiv0,1\pmod q excludes both possibilities. Since also n≢0,1(modq+1)n\not\equiv0,1\pmod{q+1}, Propositions 3.10 and 3.11 apply and yield the result. □\square

Upper bounds on M(n,q)M(n,q): constructions

In view of Lemma 2.9, we may assume throughout this section that n∉{0,q+1,q2,q2+q+1}n\notin\{0,q+1,q^2,q^2+q+1\}.

Construction 4.1. We consider the following point sets:

  1. a punctured pencil;

  2. a pencil;

  3. a punctured pencil together with t>0t>0 points of an arc containing its carrier;

  4. the union of r0≥2r_0\ge2 lines through a common point and r1=r−r0≥1r_1=r-r_0\ge1 further lines, with all pairwise intersections distinct apart from the common point of the first r0r_0 lines, after deleting a subset of the intersection points;

  5. a maximal ((q+1)k−q;k)((q+1)k-q;k)-arc (a Denniston arc), when q=2hq=2^h, the plane is Desarguesian, and k∣qk\mid q [13];

  6. the union of kk pairwise disjoint Baer subplanes and ss concurrent lines, as specified in Proposition 4.3;

  7. a perturbation of a set in (vi), obtained by adding or deleting fewer than q\sqrt q points;

  8. the union of r>1r>1 lines in general position, with a subset of their intersection points deleted.

In the level-two case, no line outside the original rr lines contains three of their pairwise intersection points.

The first three constructions, together with maximal arcs, yield the standard bounds below. The partial-pencil construction in (iv) is treated explicitly after Proposition 4.2; the Baer-subplane construction in (vi) is analyzed in Proposition 4.3. Construction 4.1(viii) will lead to Lemma 4.4 and the level-two problem of § 6.

Proposition 4.2 (Upper bounds on M(n,Πq)M(n,\Pi_q)).

(i) For 1≤r≤q+11 \le r \le q+1, M(qr,Πq)≤q+1M(qr,\Pi_q) \le q+1.

(ii) For 0≤r≤q0 \le r \le q, M(qr+1,Πq)≤q+1M(qr+1,\Pi_q) \le q+1.

(iii) If 2≤t≤q/22 \le t \le q/2 and 1≤r≤q+2−t1 \le r \le q+2-t, and a tt-arc exists in Πq\Pi_q, then

M(qr+t,Πq)≤tq+1−(t−12).M(qr+t,\Pi_q) \le tq+1-\binom{t-1}{2}.

(iv) Suppose that 1≤m≤r−21 \le m \le r-2 and that rr lines ℓ1,…,ℓr\ell_1,\ldots,\ell_r have the following incidence pattern: ℓ1,…,ℓr−m\ell_1,\ldots,\ell_{r-m} pass through a common point, and all their other pairwise intersections are distinct. Write X={ℓi∩ℓj:1≤i<j≤r}X=\{\ell_i\cap\ell_j:1\le i<j\le r\}, xm=∣X∣=1+m(2r−m−1)/2x_m=|X|=1+m(2r-m-1)/2. For every integer tt satisfying xm−m−2≤t≤2xm−m−2x_m-m-2\le t\le2x_m-m-2, we have the bound

M(rq−t,Πq)≤xm(q−1)+m+2.M(rq-t,\Pi_q) \le x_m(q-1)+m+2.

If, in addition, no line other than ℓ1,…,ℓr\ell_1,\ldots,\ell_r contains more than two points of XX, this improves to

M(rq−t,Πq)≤xm(q+1)−(xm2)+(r−m)(m2)+m(r−22).M(rq-t,\Pi_q) \le x_m(q+1)-\binom{x_m}{2}+(r-m)\binom{m}{2}+m\binom{r-2}{2}.

(v) If q=2hq=2^h, Πq\Pi_q is Desarguesian, and r+1∣qr+1\mid q, then

M(qr+r+1,Πq)≤q(q+1r+1−1).M(qr+r+1,\Pi_q) \le q\left(\frac{q+1}{r+1}-1\right).

(vi) Under the hypotheses of Proposition 4.3, put n=(k+s)q+k(q−s)+(k+s)n=(k+s)q+k(\sqrt{q}-s)+(k+s). Then

M(n,Πq)≤((k−1)(s+1)+2)q−(k−1)(s−1)q+k.M(n,\Pi_q) \le((k-1)(s+1)+2)q-(k-1)(s-1)\sqrt{q}+k.

Proof of Proposition 4.2(iii). Choose a tt-arc containing the carrier PP of a punctured pencil of rr lines, none of which contains another point of the arc; this is possible since r≤q+2−tr\le q+2-t. After adding the tt arc points, only the q+1q+1 lines through PP and the lines through at least one of the other t−1t-1 arc points can cease to be rr-secants. Among the lines not through PP, their number is

(t−1)q−(t−12),(t-1)q-\binom{t-1}{2},

since no three of the added points are collinear. The claim follows.

Proof of Proposition 4.2(iv). The union of the rr lines has

r(q+1)−(r−m−1)−(xm−1)=rq+m+2−xmr(q+1)-(r-m-1)-(x_m-1)=rq+m+2-x_m

points. Deleting

d=t−(xm−m−2),0≤d≤xm,d=t-(x_m-m-2),\qquad0\le d\le x_m,

@page 12/21 starts_mid=0 ends_mid=1 points of XX gives a set SS with ∣S∣=rq−t|S|=rq-t.

Every line avoiding XX meets the rr original lines in rr distinct points, none deleted from SS. Thus

M(rq−t,Πq)≤∣{ℓ:ℓ∩X≠∅}∣.M(rq-t,\Pi_q)\leq\left|\{\ell:\ell\cap X\ne\varnothing\}\right|.

To obtain a bound without further hypotheses, count the rr original lines, the at most q+1−(r−m)q+1-(r-m) further lines through their common point, and at most q−1q-1 additional lines through each of the remaining xm−1x_m-1 points of XX. Hence

∣{ℓ:ℓ∩X≠∅}∣≤r+q+1−(r−m)+(xm−1)(q−1)=xm(q−1)+m+2.\left|\{\ell:\ell\cap X\ne\varnothing\}\right|\leq r+q+1-(r-m)+(x_m-1)(q-1)=x_m(q-1)+m+2.

Under the additional hypothesis, the only lines containing at least three points of XX are the original ℓi\ell_i. Counting the lines through XX by first summing the xm(q+1)x_m(q+1) point-line incidences and then subtracting one for each pair of points of XX, we must restore (j−12)\binom{j-1}{2} for each line containing j≥3j\geq3 points of XX. The first r−mr-m original lines contain m+1m+1 points of XX each, and the remaining mm lines contain r−1r-1 such points each. Consequently,

∣{ℓ:ℓ∩X≠∅}∣=xm(q+1)−(xm2)+(r−m)(m2)+m(r−22),\left|\{\ell:\ell\cap X\ne\varnothing\}\right|=x_m(q+1)-\binom{x_m}{2}+(r-m)\binom{m}{2}+m\binom{r-2}{2},

as required.

We next turn to the construction involving Baer subplanes and concurrent lines.

Proposition 4.3. Suppose that qq is a square and B1,…,Bk\mathcal{B}_1,\ldots,\mathcal{B}_k are k>0k>0 pairwise disjoint Baer subplanes of PG⁡(2,q)\operatorname{PG}(2,q). Let ℓ1,…,ℓs\ell_1,\ldots,\ell_s be s≥0s\geq0 lines such that ∣ℓi∩Bj∣=1|\ell_i\cap\mathcal{B}_j|=1 for every i,ji,j. If s≥1s\geq1, assume that these lines are concurrent at a point P∈B1P\in\mathcal{B}_1. Put

S=⋃j=1kBj∪⋃i=1sℓi.S=\bigcup_{j=1}^{k}\mathcal{B}_j\cup\bigcup_{i=1}^{s}\ell_i.

Then

∣S∣=(k+s)q+k(q−s)+(k+s),|S|=(k+s)q+k(\sqrt{q}-s)+(k+s),

and

∣Lk+s(S)∣≥N−[((k−1)(s+1)+2)q−(k−1)(s−1)q+k].|L_{k+s}(S)|\geq N-\left[((k-1)(s+1)+2)q-(k-1)(s-1)\sqrt{q}+k\right].

Proof. Since the Baer subplanes are disjoint,

∣⋃j=1kBj∣=k(q+q+1).\left|\bigcup_{j=1}^{k}\mathcal{B}_j\right|=k(q+\sqrt{q}+1).

Each of the ss lines adds exactly q+1−kq+1-k points outside the union of the subplanes; these added point sets are disjoint because the lines meet only at P∈B1P\in\mathcal{B}_1. This proves the cardinality formula (and is immediate when s=0s=0).

Call a line fine if it meets each Bj\mathcal{B}_j and each ℓi\ell_i in exactly one point, with all these points distinct. Every fine line is a (k+s)(k+s)-secant of SS. If s=0s=0, every non-fine line is a Baer-subline of one of the Bj\mathcal{B}_j, so there are at most k(q+q+1)k(q+\sqrt{q}+1) such lines, which is stronger than the stated bound.

Suppose s≥1s\geq1. A non-fine line must be a Baer-subline of some Bj\mathcal{B}_j, pass through PP, or pass through ℓi∩Bj\ell_i\cap\mathcal{B}_j for some ii and j≥2j\geq2. There are at most k(q+q+1)k(q+\sqrt{q}+1) lines of the first type. Apart from the Baer-sublines of B1\mathcal{B}_1, at most q−qq-\sqrt{q} lines pass through PP. Similarly, for each of the (k−1)s(k-1)s points ℓi∩Bj\ell_i \cap B_j with j≥2j \ge2, at most q−qq-\sqrt{q} lines are not Baer-sublines of BjB_j. By the union bound, the number of non-fine lines is therefore at most

k(q+q+1)+(q−q)+(k−1)s(q−q)=((k−1)(s+1)+2)q−(k−1)(s−1)q+k.k(q+\sqrt{q}+1)+(q-\sqrt{q})+(k-1)s(q-\sqrt{q})=((k-1)(s+1)+2)q-(k-1)(s-1)\sqrt{q}+k.

This yields the asserted bound on ∣Lk+s(S)∣|L_{k+s}(S)|.

In particular, if a set S0S_0 constructed above has size n0n_0 and at least N−BN-B (k+s)(k+s)-secants, adding or deleting dd points changes only lines through those points, giving

M(n0±d,Πq)≤B+d(q+1)M(n_0 \pm d,\Pi_q) \le B+d(q+1)

whenever the indicated addition or deletion is possible. This is the perturbation principle in Construction 4.1(vii).

The next lemma concerns Construction 4.1(viii). Its hypothesis is precisely general position on level two, as defined in § 6.

Lemma 4.4. Let ℓ1,…,ℓr\ell_1,\ldots,\ell_r be r≥3r \ge3 lines in general position in PG⁡(2,q)\operatorname{PG}(2,q), and put

X={ℓi∩ℓj:1≤i<j≤r}.X=\{\ell_i\cap\ell_j:1\le i<j\le r\}.

Assume that no line outside {ℓ1,…,ℓr}\{\ell_1,\ldots,\ell_r\} contains three points of XX. Then the number b(X)b(X) of lines meeting XX is

b(X)=r+(r2)(q−1)−3(r4)=r+(r2)(q−1)−12(r−2)(r2).b(X)=r+\binom{r}{2}(q-1)-3\binom{r}{4}=r+\binom{r}{2}(q-1)-\frac{1}{2}(r-2)\binom{r}{2}.

Consequently, whenever

(r2)−r≤t≤r(r−2),\binom{r}{2}-r\le t\le r(r-2),

we have

M(rq−t,Πq)≤b(X).M(rq-t,\Pi_q)\le b(X).

Proof. The original rr lines meet XX. Each of its (r2)\binom{r}{2} points lies on a further q−1q-1 lines. Under the hypothesis, an additional line meets at most two points of XX; hence the only repeated counts correspond to pairs of intersection points associated with four distinct original lines. There are 3(r4)3\binom{r}{4} such pairs, giving the formula for b(X)b(X).

The union of the rr lines has r(q+1)−(r2)r(q+1)-\binom{r}{2} points. Deleting any dd points of XX, with 0≤d≤(r2)0\le d\le\binom{r}{2}, gives a set of size rq−trq-t, where

t=(r2)−r+d.t=\binom{r}{2}-r+d.

Every line avoiding XX remains an rr-secant, and the claimed bound follows.

Finally, a simple pencil perturbation shows that extremal sets have a unique dominant secant size.

Proposition 4.5. Let Πq\Pi_q be a projective plane of order q≥4q\ge4. Then every extremal point set has a unique dominant secant size.

Proof. Put N=q2+q+1N=q^2+q+1. The empty set and the full point set clearly have a unique dominant secant size. By complementation, it therefore suffices to consider 0<n≤N/20<n\le N/2. Write n=rq+tn=rq+t, where 0≤t<q0\le t<q.

If t=0t=0, a punctured pencil of rr lines has q2q^2 rr-secants, and thus

M(n,Πq)≤q+1<N2.M(n,\Pi_q)\le q+1<\frac{N}{2}.

Suppose t≥1t\ge1. Fix a point PP and rr lines through PP, and put

S0={P}∪⋃i=1r(ℓi∖{P}),∣S0∣=rq+1.S_0=\{P\}\cup\bigcup_{i=1}^{r}(\ell_i\setminus\{P\}),\qquad|S_0|=rq+1.

Every line not through PP is an rr-secant of S0S_0. Adding t−1t-1 further points destroys at most q(t−1)q(t-1) of these q2q^2 secants. Therefore

M(n,Πq)≤qt+1.M(n,\Pi_q)\le qt+1.

Applying the same bound to the complementary cardinality yields

M(n,Πq)≤qmin⁡{t,q+1−t}+1.(7)M(n,\Pi_q)\le q\min\{t,q+1-t\}+1. \tag*{(7)}

For even qq the right-hand side is at most q2/2+1<N/2q^2/2+1<N/2. For odd qq, the same holds unless t=(q+1)/2t=(q+1)/2.

In the remaining case q≥5q\ge5 and t−1≥2t-1\ge2. Since n≤N/2n\le N/2, we have r≤(q−1)/2r\le(q-1)/2, so at least two lines through PP lie outside the chosen pencil. Choose two of the added points on distinct such lines. The line joining them does not pass through PP and is counted twice among the affected non-PP lines. Hence at most q(t−1)−1q(t-1)-1 of the former rr-secants are destroyed, and

M(n,Πq)≤qt=q(q+1)2=N−12<N2.M(n,\Pi_q)\le qt=\frac{q(q+1)}{2}=\frac{N-1}{2}<\frac{N}{2}.

Thus M(n,Πq)<N/2M(n,\Pi_q)<N/2 for every nn. If SS is extremal, then sm(S)=N−M(n,Πq)>N/2s_m(S)=N-M(n,\Pi_q)>N/2. Since distinct secant-size classes are disjoint, at most one of them can contain more than N/2N/2 lines. □

Erdős's two-coloring problem and bounds on M(n,q) and MD(n, q)

In arbitrary projective planes the counting arguments of the previous sections already imply nontrivial lower bounds on M(n,Πq)M(n,\Pi_q). In Desarguesian planes, however, considerably stronger conclusions become possible. Recent stability theorems classify point sets with few atypical secants, and therefore translate almost immediately into exact values and sharp lower bounds for M(n,Πq)M(n,\Pi_q). These results originated from the coloring problem of Erdős.

Problem 5.1 (Erdős). What is the maximum number of lines in the projective plane Πq\Pi_q that have the same number of red and blue points in two-colorings of the point set of Πq\Pi_q?

This problem has been studied and generalized recently by Blokhuis, Markó, Szőnyi and Weiner [2], who introduced the concept of (r,b)(r,b)-colored lines. A line ℓ\ell is (r,b)(r,b)-colored in the two-coloring of the plane if the number of red points on ℓ\ell is rr, while the number of blue points is bb. The natural question then is to determine the structure (and stability) of the two-colorings of point sets that attain the maximum number of (r,b)(r,b)-colored lines. If SS is the set of red points, the (r,b)(r,b)-colored lines are precisely the rr-secants of SS. In the coloring problem rr is fixed, whereas the size of SS need not be fixed.

Stability results that characterize colorings with not too many non-(r,b)(r,b)-colored lines provide direct exact values and lower bounds for M(n,Πq)M(n,\Pi_q). Such characterizations identify the ”candidate” configurations for a fixed nn and hence M(n,Πq)M(n,\Pi_q) is found by minimizing the number of non-typical secants over these specific structures. This also means that we get a lower bound on M(n,Πq)M(n,\Pi_q), when nn is not the size of any of the candidates.

In the next subsections, we recall the stability results from [2]. While these results apply to Desarguesian planes, in the introduction, the authors sketch a simple combinatorial proof showing that the minimum number of non-(r,b)(r,b)-colored lines is obtained by coloring rr lines entirely red and bb lines entirely blue through a common point PP, whose color may be either red or blue. Assuming that r≤br \le b, the number of non-(r,b)(r,b)-colored lines in such a coloring is either 0 (if r=0r=0 and there were no red points), 1 (if r=1r=1 and only the points of one line are red) or q+1q+1 otherwise. This implies that, apart from a few special cases, M(n,Πq)M(n,\Pi_q) is almost always at least q+1q+1.

The Desarguesian case for general order

Stability results yield exact values and lower bounds for MD(n,q)M^D(n,q). We do not aim to list all such consequences here, but give a few examples. Here we recall a stability result from [2] but we reformulate it by using our terminology.

Result 5.2. [2] Let SS be a set of points in PG⁡(2,q)\operatorname{PG}(2,q). Suppose that the number of non-κ(S)\kappa(S)-secants is less than 2q+12q+1 and they form a dual blocking set. After replacing SS by its complement if necessary, put r=κ(S)≤(q+1)/2r=\kappa(S)\le(q+1)/2. Then SS (or its complement) is one of the following: a single point, a line plus a point, κ(S)\kappa(S) concurrent lines, κ(S)\kappa(S) concurrent lines minus their intersection, or a Baer subplane.

The difficulty in translating this into a result on MD(n,q)M^D(n,q) lies in the specific assumptions involved.

Note that if the non-κ(S)\kappa(S)-secants do not form a dual blocking set, then there exists a point such that all lines through it contain exactly κ(S)\kappa(S) points of SS and hence

∣S∣∈{(q+1)κ(S), 1+(q+1)(κ(S)−1)}.|S| \in\{(q+1)\kappa(S),\ 1+(q+1)(\kappa(S)-1)\}.

The next result follows from the above result and from Lemma 2.7 and from Lemma 3.7.

Theorem 5.3. In the Desarguesian plane PG⁡(2,q)\operatorname{PG}(2,q), the values for n∈{0,q+1,q2,q2+q+1}n\in\{0,q+1,q^2,q^2+q+1\} are given in Lemma 2.9. For 0<n<q2+q+10<n<q^2+q+1 with n∉{q+1,q2}n\notin\{q+1,q^2\}, the following values and bounds hold for MD(n,q)M^D(n,q):

  • If n≡0,1(modq)n\equiv0,1\pmod q, then MD(n,q)=q+1M^D(n,q)=q+1.

  • If q≥3q\ge3, then MD(q+2,q)=MD(q2−1,q)=q+2M^D(q+2,q)=M^D(q^2-1,q)=q+2.

  • If qq is a square, then MD(q+q+1,q)=MD(q2−q,q)=q+q+1M^D(q+\sqrt{q}+1,q)=M^D(q^2-\sqrt{q},q)=q+\sqrt{q}+1.

  • If n≢0,1(modq+1)n\not\equiv0,1\pmod{q+1} and none of the preceding cases applies, then MD(n,q)≥2q+1M^D(n,q)\ge2q+1.

The Desarguesian case when the order is a prime

When the order is a prime, there are stronger results which we recall here using our terminology.

Result 5.4. [2] Let p≥19p\ge19 be prime, and let SS be a point set in PG⁡(2,p)\operatorname{PG}(2,p). Suppose that the number of non-κ(S)\kappa(S)-secants is at most max⁡{3p+1,4p−22}\max\{3p+1,4p-22\}. After replacing SS by its complement if necessary, put r=κ(S)≤(p+1)/2r=\kappa(S)\le(p+1)/2. Then one of the following holds:

  1. Apart from a point PP, the set SS consists of the points on rr lines through PP. The point PP may or may not belong to SS.

  1. The set SS is obtained from a set in (1) by adding or deleting at most two points different from PP.

  1. r=1r=1, and SS consists of a line together with at most three points outside it.

  1. SS or its complement is projectively equivalent to one the Kiss–Somlai configurations described in [2], obtained from {(x,y)∈Fp2:y<x}\{(x,y)\in\mathbb{F}_p^2:y<x\} or its affine complement by adding a subset of the three special directions at infinity. Here xx and yy are identified with their representatives in {0,…,p−1}\{0,\ldots,p-1\}, and the three special directions are 00, 11 and ∞\infty.

  1. r=3r=3, and SS is obtained from the union of the three sides of a triangle by possibly deleting some of its vertices.

As before, from this and from Lemma 2.7 and 3.3, and the constructions above, we get the following corollary for MD(n,p)M^D(n,p).

Corollary 5.5. Let p≥19p\ge19 be prime, N=p2+p+1N=p^2+p+1, and put m=min⁡{n,N−n}m=\min\{n,N-n\}. In PG(2,p)(2,p), the following exceptional exact values hold:

MD(n,p)M^D(n,p)mm
00
1p+1p+1
p+2p+2p+2p+2
2p2p2p+22p+2
2p+22p+2p+3p+3
3p−23p-22p+3, p(p−1)2+3, p(p+1)2−22p+3,\ \frac{p(p-1)}{2}+3,\ \frac{p(p+1)}{2}-2
3p3p3p−33p-3
3p+13p+1p−2, p+4p-2,\ p+4

Table 1.

For all remaining values of mm, we have

MD(n,p)={p+1,m≡0,1(modp),2p+1,m≡−1,2(modp),3p,m≡−2,3(modp),M^D(n,p)= \begin{cases} p+1, & m\equiv0,1\pmod p,\\ 2p+1, & m\equiv-1,2\pmod p,\\ 3p, & m\equiv-2,3\pmod p, \end{cases}

while in every other case,

MD(n,p)>max⁡{3p+1,4p−22}.M^D(n,p)>\max\{3p+1,4p-22\}.

The next result characterizes point sets with small typical intersection numbers.

Result 5.6. [2] Let SS be a point set in PG(2,p)(2,p), pp prime. Assume that the number of non-κ(S)\kappa(S)-secants of SS is less than dp(p+1)d\sqrt{p}(p+1) and suppose also that κ(S)<cp\kappa(S)<c\sqrt{p}, where c,d>0c,d>0 and 8d(c+d)+2c+28dp+19p<18d(c+d)+\frac{2c+28d}{\sqrt{p}}+\frac{19}{p}<1 hold. Then we can add and remove in total at most ⌈dp⌉\lceil d\sqrt{p}\rceil points so that we obtain κ(S)\kappa(S) lines. Furthermore, the size of the union of the set of added or removed points and the intersection points of the κ(S)\kappa(S) lines is at most ⌈dp⌉\lceil d\sqrt{p}\rceil.

The typical intersection is small, if the size of SS is small. Consequently, if nn is less than O(pp)O(\sqrt{p}p), the stability result in Result 5.6 yields exact values for MD(n,p)M^D(n,p) when nn matches the size of one of the rigid configurations described above. In particular, it shows the optimality of the construction detailed in Proposition 4.2 (iii). In all other cases within this range, the result provides a lower bound of Ω(p3/2)\Omega(p^{3/2}) for MD(n,p)M^D(n,p). By Lemma 2.7, these characterizations and lower bounds naturally extend to sets of large cardinality.

Result 5.7. [2] Consider the set SS of points of PG⁡(2,p)\operatorname{PG}(2,p), and assume that the most frequent intersection size of SS, κ(S)\kappa(S), is less than cpc\sqrt{p} while the number of non-κ(S)\kappa(S)-secants of SS is less than dp(p+1)d\sqrt{p}(p+1) for some c,d>0c,d>0 such that the condition 8d(c+d)+20c+28dp+19p<18d(c+d)+\frac{20c+28d}{\sqrt{p}}+\frac{19}{p}<1 is satisfied. If κ(S)>⌈dp⌉\kappa(S)>\lceil d\sqrt{p}\rceil, then we can modify (add or delete) in total at most ⌈dp⌉\lceil d\sqrt{p}\rceil points, so that SS becomes the union of κ(S)\kappa(S) concurrent lines passing through PP.

This result and the pencil constructions in Proposition 4.2 imply the following corollary for MD(n,p)M^D(n,p).

Corollary 5.8. Let us take the Desarguesian plane PG⁡(2,p)\operatorname{PG}(2,p) of prime order pp. Suppose that the integers rr and tt satisfy r<cpr<c\sqrt{p}, 1≤t<dp1\leq t<d\sqrt{p}, where c,d>0c,d>0 and 8d(c+d)+20c+28dp+19p<18d(c+d)+\frac{20c+28d}{\sqrt{p}}+\frac{19}{p}<1. If r>⌈dp⌉r>\lceil d\sqrt{p}\rceil, then

MD(rp+t,p)=tp+1−(t−12).M^D(rp+t,p)=tp+1-\binom{t-1}{2}.

Line sets in general position on level 2

Construction 4.1(viii) and Lemma 4.4 suggest that efficient constructions for n=qr−tn=qr-t, with t>0t>0 small, arise from unions of lines after deleting suitably chosen intersection points. In particular, the resulting upper bound on M(n,Πq)M(n,\Pi_q) depends on the number of lines meeting the set of pairwise intersections. Additional collinear triples among these intersection points weaken this bound. This motivates the following strengthening of general position.

Definition 6.1 (Lines or points in general position on level 2). We say that rr lines ℓ1,…,ℓr\ell_1,\ldots,\ell_r are in general position on level two if they are in general position and, writing

X:={ℓi∩ℓj:1≤i<j≤r},X:=\{\ell_i\cap\ell_j:1\leq i<j\leq r\},

no line other than ℓ1,…,ℓr\ell_1,\ldots,\ell_r contains more than two points of XX. Dually, we say that rr points P1,…,PrP_1,\ldots,P_r are in general position on level two if they are in general position and, writing

Y:={⟨Pi,Pj⟩:1≤i<j≤r},Y:=\{\langle P_i,P_j\rangle:1\leq i<j\leq r\},

no point other than P1,…,PrP_1,\ldots,P_r is incident with more than two lines of YY.

Problem 6.2. Determine

gen⁡2(q):=max⁡{∣P∣:P⊆PG⁡(2,q) is in general position on level two}.\operatorname{gen}_2(q):=\max\{|P|:P\subseteq\operatorname{PG}(2,q)\text{ is in general position on level two}\}.

Theorem 6.3. We have

gen⁡2(q)=O(q1/2)andgen⁡2(q)=Ω((qlog⁡q)1/5).\operatorname{gen}_2(q)=O(q^{1/2})\quad\text{and}\quad\operatorname{gen}_2(q)=\Omega((q\log q)^{1/5}).

To obtain lower bounds on gen⁡2(q)\operatorname{gen}_2(q), it is natural to restrict the point set to a conic. This leads to a projective Sidon-type condition over finite fields.

Consider the conic X2=YZX^2=YZ in PG(2,q)\mathrm{PG}(2,q), and parameterize its affine points by

P(u)=[u:u2:1],u∈Fq.P(u)=[u:u^2:1],\qquad u\in\mathbb{F}_q.

For distinct u,v∈Fqu,v\in\mathbb{F}_q, the secant P(u)P(v)P(u)P(v) has equation

(u+v)X−Y−uvZ=0.(u+v)X-Y-uvZ=0.

Consequently, a projective point Q=[x:y:z]Q=[x:y:z] lies on this secant if and only if

zuv−x(u+v)+y=0.zuv-x(u+v)+y=0.

Moreover, QQ lies on the conic precisely when x2−yz=0x^2-yz=0.

For A⊆FqA\subseteq\mathbb{F}_q, put

HA:={P(u):u∈A}.H_A:=\{P(u):u\in A\}.

Since HAH_A is contained in a conic, it is automatically in general position. It is in general position on level two if and only if, for every [a:b:c]∈PG(2,q)[a:b:c]\in\mathrm{PG}(2,q) with

b2−ac≠0,b^2-ac\ne0,

the equation

auv+b(u+v)+c=0auv+b(u+v)+c=0

has at most two unordered solutions {u,v}⊆A\{u,v\}\subseteq A with u≠vu\ne v. This motivates the following arithmetic problem.

Problem 6.4 (Projective Sidon sets). For an integer h≥1h\ge1, call A⊆FqA\subseteq\mathbb{F}_q a projective hh-Sidon set if, for every [a:b:c]∈PG(2,q)[a:b:c]\in\mathrm{PG}(2,q) satisfying b2−ac≠0b^2-ac\ne0, the equation

auv+b(u+v)+c=0auv+b(u+v)+c=0

has at most hh unordered solutions {u,v}⊆A\{u,v\}\subseteq A with u≠vu\ne v. Determine the maximum size of a projective hh-Sidon set.

Thus HAH_A is in general position on level two if and only if AA is a projective 2-Sidon set. The condition unifies two familiar types of Sidon constraints. Indeed, if a≠0a\ne0, the equation can be rewritten as

(u+ba)(v+ba)=b2−aca2,\left(u+\frac{b}{a}\right)\left(v+\frac{b}{a}\right)=\frac{b^2-ac}{a^2},

which is a translation-multiplicative condition. If a=0a=0, then b≠0b\ne0 and the equation becomes

u+v=−cb,u+v=-\frac{c}{b},

an additive Sidon-type condition. The latter case corresponds to concurrency at infinity. Hence the two conditions are simply coordinate charts of a single projective formulation.

We now turn to the proof of Theorem 6.3. For the lower bound we use the following result.

Theorem 6.5 (Kostochka–Mubayi–Verstraëte [14]). Fix r≥2r \ge2. There exists a constant cr>0c_r > 0 such that if HH is an (r+1)(r+1)-uniform hypergraph on nn vertices with maximum rr-degree

0<d<n(log⁡n)3r2,0 < d < \frac{n}{(\log n)^{3r^2}},

then

α(H)≥cr(ndlog⁡nd)1/r.\alpha(H) \ge c_r\left(\frac{n}{d}\log\frac{n}{d}\right)^{1/r}.

Remark 6.6. An earlier result of Duke, Lefmann, and Rödl [8] also yields the same order of magnitude.

Proof of Theorem 6.3. For the upper bound, let P={P1,…,Pr}\mathcal{P}=\{P_1,\ldots,P_r\} be in general position on level two. There are

12(r2)(r−22)=3(r4)\frac{1}{2}\binom{r}{2}\binom{r-2}{2}=3\binom{r}{4}

unordered pairs of secants determined by four distinct points of P\mathcal{P}. Their intersection points lie outside P\mathcal{P}, and the level-two condition ensures that these intersection points are all distinct. Consequently,

3(r4)≤q2+q+1−r,3\binom{r}{4}\le q^2+q+1-r,

which implies r=O(q1/2)r=O(q^{1/2}).

For the lower bound, consider the 6-uniform hypergraph H\mathcal{H} with vertex set V=FqV=\mathbb{F}_q. A six-element subset of VV is an edge if its elements can be partitioned into three pairs such that the corresponding three secants of the conic are concurrent in PG(2,q)\mathrm{PG}(2,q).

We claim that

Δ5(H)≤15.\Delta_5(\mathcal{H})\le15.

Indeed, given five vertices, there are five choices for the vertex belonging to the pair containing the sixth vertex, and three ways to partition the remaining four vertices into two pairs. These two pairs determine two secants and hence their intersection point. The line joining this point to the fifth vertex meets the conic in at most one additional point. Thus each choice yields at most one possible sixth vertex, proving the claim.

Applying Theorem 6.5 with r=5r=5 and bounded maximum 5-degree gives

α(H)=Ω((qlog⁡q)1/5)\alpha(\mathcal{H})=\Omega((q\log q)^{1/5})

for sufficiently large qq.

An independent set A⊆VA\subseteq V gives a point set HAH_A in general position on level two: three concurrent secants at an external point would necessarily have disjoint pairs of endpoints and hence determine an edge of H\mathcal{H}. Therefore

gen⁡2(q)≥α(H)=Ω((qlog⁡q)1/5),\operatorname{gen}_2(q)\ge\alpha(\mathcal{H})=\Omega((q\log q)^{1/5}),

as required. □

Remark 6.7. The hypergraph above satisfies Δk(H)=O(q5−k)\Delta_k(\mathcal{H})=O(q^{5-k}) for 1≤k≤51\le k\le5. These codegree bounds are consistent with the scaling of a sparse random 6-uniform hypergraph, but do not by themselves yield a matching upper bound on its independence number. Determining whether the lower bound in Theorem 6.3 is sharp remains an interesting question.

AI declaration. The authors used ChatGPT during drafting and checking of parts of the exposition, and for creating Figure 1.

Figure 1. Lower and upper bounds for q=16q = 16 in the Desarguesian case, for n<(q2+q+1)/2n < (q^2 + q + 1)/2

References

  1. [1]Ball, S. (2003). The number of directions determined by a function over a finite field. Journal of Combinatorial Theory, Series A, 104(2), 341–350.DOI
  2. [2]Blokhuis, A., Markó, Á., Szőnyi, T., Weiner, Zs. Two-coloring the points of a projective plane, manuscript.
  3. [3]Blokhuis, A. (1994). On the size of a blocking set in PG (2, p). Combinatorica, 14(1), 111-114.DOI
  4. [4]Blokhuis, A., Seress, A., Wilbrink, H. A. (1991). On sets of points in PG(2, q) without tangents. Mitt. Math. Sem. Giessen, 201, 39–44.
  5. [5]Blokhuis, A., Szőnyi, T., Weiner, Zs. (2003). On sets without tangents in Galois planes of even order. Designs, Codes and Cryptography, 29, 91–98.DOI
  6. [6]Bruen, A. A. (1971). Blocking sets in finite projective planes. SIAM Journal on Applied Mathematics, 21(3), 380–392.DOI
  7. [7]Cilleruelo, J., Ruzsa, I., Vinuesa, C. (2010). Generalized Sidon sets. Advances in Mathematics, 225(5), 2786-2807.
  8. [8]Duke, R. A., Lefmann, H., Rödl, V. (1995). On uncrowded hypergraphs. Random Structures & Algorithms, 6(2-3), 209-212.DOI
  9. [9]Durante, N. (2014). On sets with few intersection numbers in finite projective and affine spaces. The Electronic Journal of Combinatorics, 21(4), P4.13.DOI
  10. [10]Green, B., & Tao, T. (2013). On sets defining few ordinary lines. Discrete & Computational Geometry, 50(2), 409-468.
  11. [11]Héger, T., & Nagy, Z. L. (2025). Avoiding secants of given size in finite projective planes. Journal of Combinatorial Designs, 33(3), 83-93.arxiv.org/abs/2409.14213
  12. [12]Jackson, J. (1821). Rational Amusement for Winter Evenings, Or, A Collection of Above 200 Curious and Interesting Puzzles and Paradoxes Relating to Arithmetic, Geometry, Geography: With Their Solutions, and Four Plates, Designed Chiefly for Young Persons. Longman, Hurst, Rees, Orme, and Brown.
  13. [13]Kiss, Gy., Szőnyi, T. (2019). Finite geometries. Chapman and Hall/CRC.DOI
  14. [14]Kostochka, A., Mubayi, D., Verstraëte, J. (2014). On independent sets in hypergraphs. Random Structures & Algorithms, 44(2), 224-239.
  15. [15]Nagy, Z. L., Weiner, Zs. (2026). Balanced intersection size distributions in finite geometries and vector spaces. ArXiv preprint, arxiv.org/abs/2605.23644.arxiv.org/abs/2605.23644
  16. [16]Pach, J., Radoičić, R., Tardos, G., Tóth, G. (2004, June). Improving the crossing lemma by finding more crossings in sparse graphs. In Proceedings of the twentieth annual symposium on Computational geometry (pp. 68-75).
  17. [17]Szemerédi, E., Trotter Jr, W. T. (1983). Extremal problems in discrete geometry. Combinatorica, 3(3), 381-392.DOI
  18. [18]Szőnyi, T., Weiner, Z. (2021). On the stability of Baer subplanes. European Journal of Combinatorics, 94, 103314.DOI

Paper details

vlnc:W_asxyq7sp
Version
v1 · latest
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents