WorksMathematics
Extremal secant size distributions in projective planes
Abstract
Given a point set in a projective plane of order , each line determines a secant of size . 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 , 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 of the point set, one may study the multiset of intersection sizes
as 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 -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 -rich lines: lines with prescribed multiplicity . In fact, a well-known consequence of the famous Szemerédi–Trotter theorem claims that the number of lines with at least points in a planar -set of points is at most [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 -secants (). 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 be a projective plane of order , with point set and line set , and let denote the number of points, and also the number of lines, of . If the plane is Desarguesian, we denote it by .
Definition 1.1 (-secants). For a point set and a line , we define to be the intersection size of with . A line is called a -secant of a set if . In particular, for and , these lines are usually called skew lines and tangent lines of , respectively. For an integer , let
denote the set of -secant lines.
Definition 1.2. Let denote the maximum number of occurrences of any secant size, i.e.,
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 , determine
Equivalently, determine how concentrated the secant-size distribution of an -set of points can be.
It is convenient to measure the number of atypical lines instead. Accordingly, we define
Hence is the minimum possible number of non-most-common secants among all point sets of size in a fixed projective plane . For the Desarguesian plane, we write .
Our main observation is that the extremal behaviour depends primarily on the residue of modulo the order of the plane, . Writing
separates the cardinality into a multiple of and a centered remainder. The remainder turns out to be a useful parameter for the extremal problem. When is small, natural candidate configurations arise from unions of concurrent lines and small perturbations thereof. When is a square, additional families based on Baer subplanes become competitive for certain remainders on the -scale. Thus the behaviour of depends strongly on the arithmetic position of relative to multiples of .
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 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 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 -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 -arcs; in our case takes the role of being the size of the point set, while denotes the prescribed/maximum line-intersection number.
Finally, when , for small positive , 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 (-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, -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 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 . 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 , , where . Then
Similar statement hold for for complement symmetry reason (cf. Lemma 2.7). As a consequence, the Cauchy–Schwarz bound gives many values of for which the number of atypical lines is large.
Theorem 1.5. For every , there are values of such that
Theorem 1.4 need not be tight in general, as we will show another natural lower bound on , uniform in almost all .
Proposition 1.6. For , we have . Assume and . Then:
, if ;
, if .
In the Desarguesian case, we will use much stronger stability-type results, which will enable us to characterize as well the sets where 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 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 . 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 with . 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 denotes the set of -secants and denotes the maximum frequency of the secant sizes.
Definition 2.1 (Dominant lines and atypical lines). Let . Choose a secant size and call it a dominant secant size if , and call other secant sizes atypical. A line is called dominant if for the chosen dominant secant size , and atypical otherwise.
Note that the dominant secant size need not be unique in general, it is unique for every extremal point set when ; see Proposition 4.5.
We recall our main extremal quantity from the introduction: is the minimum possible number of atypical lines among -point sets. The investigation of the size of the set of atypical lines will capture better the dependence on and .
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 in is a covering line set if every point of lies on at least one line of . Dually, a point set is a blocking set if every line meets .
A point set is untouchable, or is a set without tangents if for every line .
An oval in a projective plane of order is a set of points no three of which are collinear. If is even, a hyperoval is a set of 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 be a blocking set in a projective plane of order . If does not contain a line, then . Moreover, equality implies that is a square and is a Baer subplane.
If is prime and the plane is Desarguesian, , then every blocking set not containing a line has size at least .
Theorem 2.4 (Blokhuis–Seress–Wilbrink). If is odd, then every nonempty set without tangents in has size at least .
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 be an Abelian group and let . A set is called a Sidon set (or set) if the equation () has at most one unordered solution for all .
More generally, a set is called a set (or -Sidon set) if every has at most unordered representations of the form with .
Finally, we call a -set (or -Sidon set) if every has at most unordered representations
Result 2.6. [7] Let be a finite Abelian group of order . If is a set, then
moreover, for . Moreover, for every fixed ,
The same holds for -sets, as
To distinguish between the general case and the classical setting, we denote by the minimum number of non--secants specifically when the projective plane is Desarguesian.
We start with the simple complement symmetry.
Lemma 2.7. .
Proof. Observe that , where is the complement of the set in the projective plane. The claim follows.
Next we record the standard equalities.
Lemma 2.8 (Standard equalities). Let with . Then
Lemma 2.9. The following values hold for in any projective plane.
If then ;
If or , then .
If then .
Proof. (1) and (2) follow immediately from the definition of . 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 iff . 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 .
Proposition 3.1. Suppose that with , , where . Then
i.e.,
Proof. Let us choose such that . Put
Thus exactly lines lie outside . Writing up the standard equations, cf. Lemma 2.8, we obtain that
The Cauchy-Schwarz inequality then implies
Note that in the last step, we used the fact that clearly holds. Hence,
that is,
The minimum of could be derived from here by minimizing the coefficient of
in . Since this is a quadratic inequality, the optimal choice can be derived studying the corresponding discriminant. Since and with , we have
Thus is the integer minimizing . In particular, for every dominant secant size . Substituting this into the preceding inequality yields the claim.
Remark 3.2. Equality in the upper bound of Proposition 3.1 on can occur only if all atypical lines have the same intersection size with . Thus equality in the resulting lower bound for requires, in particular, that the dominant secant size be the minimizing integer and that be constant over all . 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
where is a sufficiently small constant, and choose and and hence . Proposition 3.1 ensures that for we have
We estimate the numerator and denominator separately. Since and , we have , and therefore . On the other hand, . As , we have , while , and holds. Since , it follows that . Consequently,
It remains to count the number of admissible values of . There are admissible values for and possible choices for , hence pairs . Since and , distinct pairs yield distinct values of . Thus there are values of for which .
Stability results when the set has small size
Lemma 3.3. Suppose that -arcs exist in for all . (Note that for Desarguesian planes, this holds in a strong sense, for all ).
If , then , while if , then .
Proof. The transition point will be determined by comparing and . Suppose first that and is an arbitrary -element set. Then for all , while holds. Let be an -arc. Hence it is enough to show that holds. The inequality in turn follows from the upper bound on .
On the other hand, suppose next that and is an arbitrary -element set. Then for all , while holds. Let be a set of collinear points. Hence it is enough to show that holds. The inequality in turn follows from the upper bound on .
Lemma 3.4. If for a set , the set of lines does not cover all points of the projective plane then either or .
Proof. Let be a point incident only with -secants. If , then the lines through partition , whence .
If , then every line through contains further points of , and hence . Equivalently, .
Lemma 3.5. Let be a non-empty set in and assume that neither nor is a line. Suppose also that the non--secants do not cover all points of the plane. Then through each point there pass 0 or at least 2 non--secants of . In particular, has either 0 or at least non--secants.
Proof. By Lemma 3.4 and Lemma 2.7 we may suppose that (i.e., there exists a point outside with only -secants through it). If now is a point with exactly one non--secant line through it, then must be in . Counting the points of on the lines through , we get that and so . Since is non-empty with size , must be 1 and . Again looking around we see that is a line, which contradicts our assumption. Hence through each point there pass 0 or at least 2 non--secants of . If a non--secant exists then counting the non--secants through the points of this secant we see at least of them.
Lemma 3.6. Let be a set with less than lines not in . Assume also that among these lines there are through a point . Then is:
a pencil or a punctured pencil,
a point set of a line and a disjoint point
the complement of (2).
Proof. Note that on each line through there must exist a point such that is the unique non--secant through . Assume that and are such points so that the line is different from . If but , then counting the number of points of on the lines through and through , we get that
thus and ; and hence is a pencil or a punctured pencil. Otherwise we see the same number of points of on each line through . Write . The cases again give pencils or punctured pencils, so assume . By complementation, we may assume . Then . As mentioned before on each line through , there exists a point , through which is the only non--secant. Clearly, otherwise we get that and hence the lines through are in . Counting the points of on the lines through we get that .
Set . All lines through are now -secants, and fewer than other lines are not. In particular, is dominant for . These exceptional lines do not cover the plane. By Lemma 3.5 and Lemma 2.9, is a line, the complement of a line, the empty set, or the whole plane. Since and , only the complement of a line is possible. Thus is the complement of a line together with an external point. Undoing complementation gives the remaining possibility.
Lemma 3.7. Assume and , then:
, if ;
, if .
Proof. Let be a set of size . If its non--secants do not cover the plane, then Lemma 3.5, Lemma 2.9 and our assumption on give at least such lines. If they cover the plane, then by Theorem 2.3 there are at least of them, with equality only if they form a pencil. Thus .
If equality holds, the non--secants form a pencil, so Lemma 3.6 applies. A line plus an external point and its complement have non-dominant secants; hence is a pencil or a punctured pencil, and . If , we can choose a pencil or a punctured pencil of size with exactly non--secants.
Lemma 3.8. Assume that a set admits non--secants, forming a dual hyperoval. Then is one of the following
the set of all points lying on one of the lines , ;
the set of all points lying on one of the lines , , except those on a fixed line .
the complement of either (1) or (2).
Proof. For any point not lying on any of the lines , we see only -secants of through it and so either all points outside the lines are in or none. By taking the complement if necessary, we may assume that none of these points belongs to . Counting through any such point gives .
If no contains both a point of and a point outside , then each is either contained in or disjoint from it. Since the meet pairwise, they must all be of the same kind. They cannot all be disjoint, as then would be empty. Thus (1) holds. Now pick a line which is not a -secant of and assume that there exist points and . Let and be the other non--secants of through and through , we get that either and or and .
More generally, counting through the intersection of two distinct lines among the gives
Suppose first that and . Since is disjoint from , the displayed equality gives for every . In particular, . Thus every contains all its points outside in , giving (2).
In the other case, and . The point belongs to , so the displayed equality gives . For any , the point is not in , and hence . This contradicts the choice of the . Taking complements gives (3).
For , Lemmas 2.9 and 3.7 already determine all values of . For , the next corollary follows from the preceding lemmas and the dual form of Theorem 2.3.
Corollary 3.9. Suppose that and . Then , unless , , or admits a dual hyperoval and
Structural arguments relying on blocking sets
Proposition 3.10. Let , and let be a dominant secant size. If
then the non--secants form a covering line set.
Proof. If some point is not covered by a non--secant, Lemma 3.4 gives either or
In the first case , while in the second . This proves the claim.
Proposition 3.11. Let , let be a dominant secant size of , and suppose that
If is neither a pencil nor a punctured pencil, then
Proof. Put . By Proposition 3.10, is a covering line set. Suppose that . Choose an inclusion-minimal covering subset . By dual Bruen, either , contradiction, or contains a full pencil. But because is minimal, in the latter case it is exactly that pencil. Hence contains all lines through some point. Since , Lemma 3.6 applies and says that 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 and , so they are also excluded.
Proposition 3.12. Suppose that , then .
Proof. Choose an -point set attaining . A pencil has size , while a punctured pencil has size , so excludes both possibilities. Since also , Propositions 3.10 and 3.11 apply and yield the result.
Upper bounds on : constructions
In view of Lemma 2.9, we may assume throughout this section that .
Construction 4.1. We consider the following point sets:
a punctured pencil;
a pencil;
a punctured pencil together with points of an arc containing its carrier;
the union of lines through a common point and further lines, with all pairwise intersections distinct apart from the common point of the first lines, after deleting a subset of the intersection points;
a maximal -arc (a Denniston arc), when , the plane is Desarguesian, and [13];
the union of pairwise disjoint Baer subplanes and concurrent lines, as specified in Proposition 4.3;
a perturbation of a set in (vi), obtained by adding or deleting fewer than points;
the union of lines in general position, with a subset of their intersection points deleted.
In the level-two case, no line outside the original 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 ).
(i) For , .
(ii) For , .
(iii) If and , and a -arc exists in , then
(iv) Suppose that and that lines have the following incidence pattern: pass through a common point, and all their other pairwise intersections are distinct. Write , . For every integer satisfying , we have the bound
If, in addition, no line other than contains more than two points of , this improves to
(v) If , is Desarguesian, and , then
(vi) Under the hypotheses of Proposition 4.3, put . Then
Proof of Proposition 4.2(iii). Choose a -arc containing the carrier of a punctured pencil of lines, none of which contains another point of the arc; this is possible since . After adding the arc points, only the lines through and the lines through at least one of the other arc points can cease to be -secants. Among the lines not through , their number is
since no three of the added points are collinear. The claim follows.
Proof of Proposition 4.2(iv). The union of the lines has
points. Deleting
@page 12/21 starts_mid=0 ends_mid=1 points of gives a set with .
Every line avoiding meets the original lines in distinct points, none deleted from . Thus
To obtain a bound without further hypotheses, count the original lines, the at most further lines through their common point, and at most additional lines through each of the remaining points of . Hence
Under the additional hypothesis, the only lines containing at least three points of are the original . Counting the lines through by first summing the point-line incidences and then subtracting one for each pair of points of , we must restore for each line containing points of . The first original lines contain points of each, and the remaining lines contain such points each. Consequently,
as required.
We next turn to the construction involving Baer subplanes and concurrent lines.
Proposition 4.3. Suppose that is a square and are pairwise disjoint Baer subplanes of . Let be lines such that for every . If , assume that these lines are concurrent at a point . Put
Then
and
Proof. Since the Baer subplanes are disjoint,
Each of the lines adds exactly points outside the union of the subplanes; these added point sets are disjoint because the lines meet only at . This proves the cardinality formula (and is immediate when ).
Call a line fine if it meets each and each in exactly one point, with all these points distinct. Every fine line is a -secant of . If , every non-fine line is a Baer-subline of one of the , so there are at most such lines, which is stronger than the stated bound.
Suppose . A non-fine line must be a Baer-subline of some , pass through , or pass through for some and . There are at most lines of the first type. Apart from the Baer-sublines of , at most lines pass through . Similarly, for each of the points with , at most lines are not Baer-sublines of . By the union bound, the number of non-fine lines is therefore at most
This yields the asserted bound on .
In particular, if a set constructed above has size and at least -secants, adding or deleting points changes only lines through those points, giving
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 be lines in general position in , and put
Assume that no line outside contains three points of . Then the number of lines meeting is
Consequently, whenever
we have
Proof. The original lines meet . Each of its points lies on a further lines. Under the hypothesis, an additional line meets at most two points of ; hence the only repeated counts correspond to pairs of intersection points associated with four distinct original lines. There are such pairs, giving the formula for .
The union of the lines has points. Deleting any points of , with , gives a set of size , where
Every line avoiding remains an -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 be a projective plane of order . Then every extremal point set has a unique dominant secant size.
Proof. Put . The empty set and the full point set clearly have a unique dominant secant size. By complementation, it therefore suffices to consider . Write , where .
If , a punctured pencil of lines has -secants, and thus
Suppose . Fix a point and lines through , and put
Every line not through is an -secant of . Adding further points destroys at most of these secants. Therefore
Applying the same bound to the complementary cardinality yields
For even the right-hand side is at most . For odd , the same holds unless .
In the remaining case and . Since , we have , so at least two lines through lie outside the chosen pencil. Choose two of the added points on distinct such lines. The line joining them does not pass through and is counted twice among the affected non- lines. Hence at most of the former -secants are destroyed, and
Thus for every . If is extremal, then . Since distinct secant-size classes are disjoint, at most one of them can contain more than 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 . 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 . 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 that have the same number of red and blue points in two-colorings of the point set of ?
This problem has been studied and generalized recently by Blokhuis, Markó, Szőnyi and Weiner [2], who introduced the concept of -colored lines. A line is -colored in the two-coloring of the plane if the number of red points on is , while the number of blue points is . The natural question then is to determine the structure (and stability) of the two-colorings of point sets that attain the maximum number of -colored lines. If is the set of red points, the -colored lines are precisely the -secants of . In the coloring problem is fixed, whereas the size of need not be fixed.
Stability results that characterize colorings with not too many non--colored lines provide direct exact values and lower bounds for . Such characterizations identify the ”candidate” configurations for a fixed and hence is found by minimizing the number of non-typical secants over these specific structures. This also means that we get a lower bound on , when 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--colored lines is obtained by coloring lines entirely red and lines entirely blue through a common point , whose color may be either red or blue. Assuming that , the number of non--colored lines in such a coloring is either 0 (if and there were no red points), 1 (if and only the points of one line are red) or otherwise. This implies that, apart from a few special cases, is almost always at least .
The Desarguesian case for general order
Stability results yield exact values and lower bounds for . 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 be a set of points in . Suppose that the number of non--secants is less than and they form a dual blocking set. After replacing by its complement if necessary, put . Then (or its complement) is one of the following: a single point, a line plus a point, concurrent lines, concurrent lines minus their intersection, or a Baer subplane.
The difficulty in translating this into a result on lies in the specific assumptions involved.
Note that if the non--secants do not form a dual blocking set, then there exists a point such that all lines through it contain exactly points of and hence
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 , the values for are given in Lemma 2.9. For with , the following values and bounds hold for :
If , then .
If , then .
If is a square, then .
If and none of the preceding cases applies, then .
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 be prime, and let be a point set in . Suppose that the number of non--secants is at most . After replacing by its complement if necessary, put . Then one of the following holds:
Apart from a point , the set consists of the points on lines through . The point may or may not belong to .
The set is obtained from a set in (1) by adding or deleting at most two points different from .
, and consists of a line together with at most three points outside it.
or its complement is projectively equivalent to one the Kiss–Somlai configurations described in [2], obtained from or its affine complement by adding a subset of the three special directions at infinity. Here and are identified with their representatives in , and the three special directions are , and .
, and 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 .
Corollary 5.5. Let be prime, , and put . In PG, the following exceptional exact values hold:
| 0 | 0 |
| 1 | |
Table 1.
For all remaining values of , we have
while in every other case,
The next result characterizes point sets with small typical intersection numbers.
Result 5.6. [2] Let be a point set in PG, prime. Assume that the number of non--secants of is less than and suppose also that , where and hold. Then we can add and remove in total at most points so that we obtain lines. Furthermore, the size of the union of the set of added or removed points and the intersection points of the lines is at most .
The typical intersection is small, if the size of is small. Consequently, if is less than , the stability result in Result 5.6 yields exact values for when 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 for . By Lemma 2.7, these characterizations and lower bounds naturally extend to sets of large cardinality.
Result 5.7. [2] Consider the set of points of , and assume that the most frequent intersection size of , , is less than while the number of non--secants of is less than for some such that the condition is satisfied. If , then we can modify (add or delete) in total at most points, so that becomes the union of concurrent lines passing through .
This result and the pencil constructions in Proposition 4.2 imply the following corollary for .
Corollary 5.8. Let us take the Desarguesian plane of prime order . Suppose that the integers and satisfy , , where and . If , then
Line sets in general position on level 2
Construction 4.1(viii) and Lemma 4.4 suggest that efficient constructions for , with small, arise from unions of lines after deleting suitably chosen intersection points. In particular, the resulting upper bound on 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 lines are in general position on level two if they are in general position and, writing
no line other than contains more than two points of . Dually, we say that points are in general position on level two if they are in general position and, writing
no point other than is incident with more than two lines of .
Problem 6.2. Determine
Theorem 6.3. We have
To obtain lower bounds on , 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 in , and parameterize its affine points by
For distinct , the secant has equation
Consequently, a projective point lies on this secant if and only if
Moreover, lies on the conic precisely when .
For , put
Since 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 with
the equation
has at most two unordered solutions with . This motivates the following arithmetic problem.
Problem 6.4 (Projective Sidon sets). For an integer , call a projective -Sidon set if, for every satisfying , the equation
has at most unordered solutions with . Determine the maximum size of a projective -Sidon set.
Thus is in general position on level two if and only if is a projective 2-Sidon set. The condition unifies two familiar types of Sidon constraints. Indeed, if , the equation can be rewritten as
which is a translation-multiplicative condition. If , then and the equation becomes
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 . There exists a constant such that if is an -uniform hypergraph on vertices with maximum -degree
then
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 be in general position on level two. There are
unordered pairs of secants determined by four distinct points of . Their intersection points lie outside , and the level-two condition ensures that these intersection points are all distinct. Consequently,
which implies .
For the lower bound, consider the 6-uniform hypergraph with vertex set . A six-element subset of is an edge if its elements can be partitioned into three pairs such that the corresponding three secants of the conic are concurrent in .
We claim that
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 and bounded maximum 5-degree gives
for sufficiently large .
An independent set gives a point set 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 . Therefore
as required. □
Remark 6.7. The hypergraph above satisfies for . 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 in the Desarguesian case, for
References
- [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]Blokhuis, A., Markó, Á., Szőnyi, T., Weiner, Zs. Two-coloring the points of a projective plane, manuscript.
- [3]Blokhuis, A. (1994). On the size of a blocking set in PG (2, p). Combinatorica, 14(1), 111-114.DOI
- [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]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]Bruen, A. A. (1971). Blocking sets in finite projective planes. SIAM Journal on Applied Mathematics, 21(3), 380–392.DOI
- [7]Cilleruelo, J., Ruzsa, I., Vinuesa, C. (2010). Generalized Sidon sets. Advances in Mathematics, 225(5), 2786-2807.
- [8]Duke, R. A., Lefmann, H., Rödl, V. (1995). On uncrowded hypergraphs. Random Structures & Algorithms, 6(2-3), 209-212.DOI
- [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]Green, B., & Tao, T. (2013). On sets defining few ordinary lines. Discrete & Computational Geometry, 50(2), 409-468.
- [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]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]Kiss, Gy., Szőnyi, T. (2019). Finite geometries. Chapman and Hall/CRC.DOI
- [14]Kostochka, A., Mubayi, D., Verstraëte, J. (2014). On independent sets in hypergraphs. Random Structures & Algorithms, 44(2), 224-239.
- [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]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]Szemerédi, E., Trotter Jr, W. T. (1983). Extremal problems in discrete geometry. Combinatorica, 3(3), 381-392.DOI
- [18]Szőnyi, T., Weiner, Z. (2021). On the stability of Baer subplanes. European Journal of Combinatorics, 94, 103314.DOI
