betaFeedback

WorksMathematics

Two-coloring the points of a projective plane

Abstract

Let us color the points of a projective plane of odd order nn with two colors, say red and blue. Erdős asked the question of determining the maximum number of balanced lines (that have the same number of red and blue points). The answer is n2n^2, and in the corresponding trivial coloring the unbalanced lines go through a point. In this paper, we consider the Galois plane PG(2,q)\mathrm{PG}(2,q) and determine the number of unbalanced lines for a non-trivial coloring. The problem can also be generalized to (r,b)(r,b)-colored lines (see Definition 1.1) and in many cases we extend the results to the generalized problem. Our strongest result for Galois planes of prime order pp describes all 2-colorings with at most max⁡{3p+1,4p−22}\max\{3p+1,4p-22\} not (r,b)(r,b)-colored lines (see Theorem 5.13). Finally, in case of the generalized problem, we allow even more not (r,b)(r,b)-colored lines if rr is small and the order is prime (for more details, see Theorem 5.18).

Introduction

Determining the chromatic number of a projective plane of order nn is an easy exercise. It is 3 for the Fano plane and 2 for n≥3n \ge3. In spite of this, there are several interesting problems for colorings of projective planes. For example, one can impose extra conditions on color classes (one may require that they are arcs, or blocking sets, see Csima, Füredi [9], or [6]), or can consider other variants of the chromatic number (such variants were introduced by Voloshin [19], and for projective planes the upper chromatic number was considered first by Bacsó and Tuza [4], then in [5]). One may also consider balanced colorings in which the size of color classes differs by at most one (the balanced upper chromatic number was introduced by Araujo-Pardo, Kiss, Montejano [2], and considered later in [7]). There are probably many other interesting problems for coloring; for example, Alon and Füredi [3] consider colorings in which the distribution of colors is unique for the lines.

We will mostly be interested in 2-colorings and the colors we call red and blue. The classical result by Spencer [14] about the discrepancy of projective planes gives a probabilistic proof of the existence of a 2-coloring so that for every line ℓ\ell the difference of the number of red and blue points on ℓ\ell is at most KnK\sqrt{n} (where KK is an absolute constant and nn is the order of the plane).

Probably motivated by the above result by Spencer, Erdős asked in the eighties the following problem: What is the maximum number of lines that have the same number of red and blue points? Let us call such a line balanced.

It is easy to see that there are at least q+1q+1 unbalanced lines in PG(2,q)(2,q). Indeed, as qq lines cannot cover all points, there exists a point through which only balanced lines pass. If this point is red, then the number of red points would be (q2+1)/2(q^2+1)/2. Similarly, on an unbalanced line there must be a point through which no other unbalanced line passes. Counting the number of red points on the lines through such a point yields a contradiction, showing that there are indeed at least q+1q+1 unbalanced lines. A slight refinement of this simple argument also shows that when there are exactly q+1q+1 unbalanced lines, then they must be concurrent. Moreover, half of these lines are entirely red, half are entirely blue (except the carrier of this pencil, which can be either color). This trivial coloring shows that the bound q+1q+1 for the number of unbalanced lines is sharp, and essentially this is the only coloring with q+1q+1 unbalanced lines.

We generalize the notion of balanced lines by introducing (r,b)(r,b)-colored lines.

Definition 1.1. Color the points of PG(2,q)(2,q) with red and blue and fix an integer 0≤r≤q+10 \le r \le q+1 and let b=q+1−rb=q+1-r. The line ℓ\ell in PG(2,q)(2,q) is (r,b)(r,b)-colored, if the number of red points on ℓ\ell is rr, while the number of blue points is bb.

For the remainder of this paper, we refer to (r,b)(r,b)-colored lines as balanced lines and all other lines as unbalanced lines. Note that when r=b=(q+1)/2r=b=(q+1)/2, this coincides with Erdős’ original notion of balance. Also note that the role of the colors is symmetric, and so we may assume that r≤br \le b.

Definition 1.2. We call the following coloring trivial: take a pencil, color rr lines of the pencil entirely red (except for their common carrier, which can be any color), and color the remaining lines entirely blue.

The question we consider is to find the maximum number of (r,b)(r,b)-colored (balanced) lines. Originally, as discussed above, Erdős asked this question for r=(q+1)/2r=(q+1)/2. The third author heard about the problem from Jenő Lehel [12]. Extending the argument above, one can see that there are exactly two exceptional cases when the number of unbalanced lines is smaller than q+1q+1: when r=0r=0, that is, all points are blue (no unbalanced lines), and when r=1r=1, that is, one line is completely red while all other points are blue (exactly one unbalanced line). In all other cases, there are at least q+1q+1 unbalanced lines.

The corresponding coloring in the case of equality is again the trivial coloring defined above.

We shall focus on a stability version of this generalized Erdős question: characterize the case(s) when the number of (r,b)(r,b)-colored lines is close to its maximum.

Note that the case r=0r=0 is trivial. If we color all points blue, then all lines are balanced. In this case, the stability version of the problem given above would ask for the number of lines intersecting a point set (see also [8]).

Note that a balanced line contains r mod pr \bmod p red points. Therefore, if we consider the set of red points RR, then only the unbalanced lines can be not (r mod p)(r \bmod p)-secants of it (though not necessarily). Hence, if there are δ\delta unbalanced lines, then the number of not (r mod p)(r \bmod p)-secants of RR is at most δ\delta. This allows us to apply the results of [16] for sets having few not (r mod p)(r \bmod p)-secants.

In the present paper we shall work in the Desarguesian plane PG(2,q)(2,q), q=phq=p^h, pp prime, so for the order of the plane we will use qq and not nn as above. The corresponding affine plane AG(2,q)(2,q) will occasionally be identified with Fq2\mathbb{F}_{q^2} (see [10], Section 2.2). Our goal is to determine and classify 2-colorings that admit only a small number of unbalanced lines — in particular, to describe all such colorings when their number is at most 2q+12q+1, and to analyze special cases when qq is prime.

Outline of results and motivating examples

Our main results provide complete classifications for colorings when there are few unbalanced lines. In § 3, we deal with the general case r<br < b in PG(2,q)(2,q), q=phq = p^h. Here we settle the problem under the additional assumption that there is a line for which the number of red points is not rr (mod pp) (Assumption 3.10). This condition is needed when the unbalanced lines (i.e. not (r,b)(r,b)-colored) do not form a dual blocking set (see Subsection 3.2). In this case we can describe the coloring completely if there are at most 2q+12q + 1 unbalanced lines and q>3q > 3 (Theorem 3.13). If, on the other hand, the unbalanced lines form a dual blocking set (see Subsection 3.1), then we describe the coloring completely if there are less than 2q+12q + 1 lines (Theorem 3.7).

§ 4 deals with the case of the original problem of Erdős (r=b=(q+1)/2r = b = (q + 1)/2). Using a counting argument (without Assumption 3.10), we prove that for a non-trivial coloring the number of unbalanced lines is at least 2q+12q + 1 when q>3q > 3 (Theorem 4.5). The argument also works for the nearby cases ∣r−(q+1)/2∣≤(p−3)/2\lvert r - (q + 1)/2\rvert\le(p - 3)/2: if 3≤r≤b3 \le r \le b and the unbalanced lines do not form a dual blocking set, then there are at least 2q+22q + 2 unbalanced lines (Corollary 4.4).

The next examples show that Assumption 3.10 cannot be omitted: there exist colorings with fewer than 2q+12q + 1 unbalanced lines which do not form a dual blocking set, and for which every line contains the same number of red points modulo pp. Also one might think that in the Erdős case, the only possible example with 2q+12q + 1 unbalanced lines is the trivial example with flipping the color of a point different from the carrier of the complete red lines. However, as Example 2.3 shows with t=(q−1)/2t = (q - 1)/2, this is not the case.

Example 2.1. Let qq be even, and consider a set of q+2q + 2 lines in PG(2,q)(2,q) such that no three of them are concurrent (a so-called dual hyperoval). Color all points on these q+2q + 2 lines blue and all other points red. Or color one of these q+2q + 2 lines blue, the remaining points on the other q+1q + 1 lines red, and all other points blue.

Since each point lies on either 0 or 2 of these q+2q + 2 lines, every line not belonging to the dual hyperoval contains exactly r=q/2r = q/2 red points. Thus these colorings have exactly q+2q + 2 unbalanced lines (namely, the lines of the dual hyperoval).

Example 2.2. In Example 2.1 change the color of a point on one of the lines of the dual hyperoval. This coloring will have exactly 2q+12q + 1 unbalanced lines.

Example 2.3. Let qq be a square, and let BB be a Baer subplane of PG(2,q)(2,q). Choose a point P∈BP \in B, and let tt lines through PP be tangent to BB (i.e. meeting BB in PP only), where 1≤t≤q−q1 \le t \le q - \sqrt{q}. Color all points of B∖{P}B \setminus\{P\} red, and also color red all points on these tt tangent lines except PP. The color of PP can be either red or blue. All remaining points are colored blue.

A line tangent to BB and not passing through PP contains exactly t+1t + 1 red points. Any other line not passing through PP contains q+1+t\sqrt{q} + 1 + t red points, while the lines through PP contain either 0, 1, q\sqrt{q}, q+1\sqrt{q} + 1, qq, q+1q + 1 red points.

Let r=t+1r = t + 1 and b=q−tb = q - t. Then:

  • if t=q−1t = \sqrt{q} - 1 and PP is blue, then the coloring has exactly 2q−q2q - \sqrt{q} unbalanced lines;

  • if t=qt = \sqrt{q} and PP is red, then the coloring has exactly 2q−q2q - \sqrt{q} unbalanced lines;

  • if t≠q−1,qt \ne\sqrt{q} - 1, \sqrt{q}, then the coloring has exactly 2q+12q + 1 unbalanced lines.

§ 5 is devoted to the case q=pq = p prime. The non-(r mod p)(r \bmod p) secants are typically just the unbalanced lines (except for r=1r = 1), so it is not surprising that we have stronger results for q=pq = p. First of all, there is an example due to Kiss and Somlai, who constructed a subset of size p(p−1)/2p(p - 1)/2 which intersects each line with slope not m=0,1m = 0, 1 in precisely (p−1)/2(p - 1)/2 points. If we color this set and the line at infinity red, then we get a non-trivial coloring in the Erdős case with 3p−23p - 2 unbalanced lines. In the prime case, q=p≥19q = p \ge19, we can describe colorings with at most max⁡{3p+1,4p−22}\max\{3p + 1, 4p - 22\} unbalanced lines completely, see Theorem 5.13 in Subsection 5.2. Finally, in Subsection 5.3, we consider the general problem when rr is small in PG⁡(2,p)\operatorname{PG}(2,p), pp prime. In this case the red points are the union of rr completely red lines (with some assumption on the number of points they intersect) and we may change the color of a small number of points (Theorem 5.18).

Colorings with at most 2q+12q + 1 unbalanced lines in PG⁡(2,q)\operatorname{PG}(2,q)

In this section, we color the points of PG⁡(2,q)\operatorname{PG}(2,q) red and blue, and we denote the set of red points by RR, the set of blue points by BB, and the set of unbalanced lines by UU. Throughout this section, we will assume that ∣U∣≤2q+1|U| \le2q + 1, unless stated otherwise and we will characterize the possible such colorings. We will distinguish between two cases: first, we consider the case where the unbalanced lines form a dual blocking set, and then we examine the case where there exists a point not covered by any of the unbalanced lines.

Unbalanced lines form a dual blocking set

Lemma 3.1. If 0<∣U∣≤2q+10 < |U| \le2q + 1 and UU covers all points of PG⁡(2,q)\operatorname{PG}(2,q), then every balanced line contains a point through which there is a unique unbalanced line.

First, we consider the case when the points through which a unique unbalanced line passes are all the same color. We will need the following result.

Result 3.2 (Tallini Scafati [17], [18]). If qq is a power of a prime, then any point set in a projective plane of order qq intersecting each line in either 11 or nn points, where 0≤n≤q+10 \le n \le q + 1 and n≠1n \ne1, is one of the following: a unique point, a line, a Baer subplane, or a unital.

Lemma 3.3. Assume that unbalanced lines cover all points of PG⁡(2,q)\operatorname{PG}(2,q) and the points through which a unique unbalanced line passes are all the same color, say red. Suppose also that all unbalanced lines contain the same number of red points and the total number of unbalanced lines is less than q+1\sqrt{q} + 1. Then either there is a unique blue point or the blue points form a Baer subplane.

Proof. By assumption, the number of red points on a line can take on two possible values. Hence, the number of unbalanced lines through any two points of the same color must be the same. Since the points through which a unique unbalanced line passes are red, we conclude that exactly one unbalanced line passes through each red point. By Result 3.2, this means there is either only one unbalanced line, or q+1q + 1 concurrent ones, or they form a dual Baer subplane. Unbalanced lines form a dual blocking set and hence the first case cannot happen. The lemma now follows from the fact that the points through which there passes a unique unbalanced line are exactly the red points.

Lemma 3.4. Assume that all points through which a unique unbalanced line passes are the same color, say red. Suppose also that the unbalanced lines form a dual blocking set and there exist two unbalanced lines with different number of red points on them. Assume that ∣U∣≤2q+1|U| \le2q + 1. Then, a line and a point disjoint from it are colored blue, and the rest of the points are red.

Proof. If RR denotes the set of red points, then on an unbalanced line containing a red point through which that line is the only unbalanced line, we see r0:=∣R∣−q(r−1)r_0 := |R| - q(r - 1) red points. Suppose that uu is an unbalanced line with r1≠r0r_1 \ne r_0 red points. Since the unbalanced lines form a dual blocking set and have size less than 2q+12q+1, by Szőnyi ([15], Proposition 3.1), the essential lines (i.e., the lines containing a point through which that line is the only unbalanced line) form a minimal dual blocking set. This implies that, through the points of a line uu, apart from uu itself, we observe at least one more unbalanced line with r0r_0 red points.

The fact that r0=∣R∣−q(r−1)r_0=|R|-q(r-1) yields that if through a red point on uu there is another unbalanced line with r0r_0 red points, then there must be a third unbalanced line through that point. If there are no blue points on uu, then we already count at least 2(q+1)+12(q+1)+1 unbalanced lines, which contradicts the assumption.

If every blue point on uu has at least three unbalanced lines passing through it, then again ∣U∣≥2(q+1)+1|U|\ge2(q+1)+1, a contradiction. Thus, there is a blue point PP on uu with only two unbalanced lines. Namely, uu and the other compulsory unbalanced line ee containing r0r_0 red points. Counting the total number of red points on the lines through PP, we obtain (q−1)r+r0+r1(q-1)r+r_0+r_1. However, we also know that there are q(r−1)+r0q(r-1)+r_0 red points in total. This implies that r1=0r_1=0 and r=qr=q or r1=1r_1=1 and r=q+1r=q+1. In the latter case, there can be at most one blue point (otherwise there was at least 2q+12q+1 lines containing blue points, i.e. unbalanced), which is impossible since uu contains qq blue points. In the former case, all points not on uu or ee are red. Now, if we take another point P′P' on uu, then, as mentioned above, there is an unbalanced line through P′P' with r0r_0 red points. Since all points outside of uu and ee are red, this means that q−1≤r0≤qq-1\le r_0\le q. However, a balanced line has exactly qq red points, so we must have r0=q−1r_0=q-1, from which the proof follows. □

Next, we will consider the case where there are two points of different colors, each having a unique unbalanced line passing through it.

Lemma 3.5. Let PP and QQ be two points of different colors. Assume that there is a unique unbalanced line through each of these points, then the line PQPQ is balanced. Let ℓP\ell_P and ℓQ\ell_Q be the unique unbalanced lines through PP and QQ respectively and T:=ℓP∩ℓQT:=\ell_P\cap\ell_Q. Then the points of ℓP∖{T}\ell_P\setminus\{T\} are colored the same as PP, and similarly, the points of ℓQ∖{T}\ell_Q\setminus\{T\} are colored the same as QQ.

Proof. Assume that PP is colored red. If PQPQ is unbalanced, counting the number of red points not on PQPQ along the lines through PP would give (r−1)q(r-1)q while through QQ would give rqrq which is a contradiction. Let the number of red points on ℓP\ell_P be r1r_1, and on ℓQ\ell_Q be r2r_2. By counting the number of red points on the lines through PP, we get q(r−1)+r1q(r-1)+r_1. Similarly, by counting the red points on the lines through QQ, we get qr+r2qr+r_2. It follows that r1−r2=qr_1-r_2=q and hence we are done. □

Proposition 3.6. Assume that the points through which there is a unique unbalanced line are not all of the same color. Assume also that ∣U∣<2q+1|U|<2q+1. Then, there exists a point TT such that the points, excluding TT, on exactly rr lines through TT are colored red, and the points, excluding TT, on the remaining q+1−rq+1-r lines through TT are colored blue. The point TT itself can be either red or blue.

Proof. The assumption of the proposition and Lemma 3.5 imply that there exists a point PP colored red, a point QQ colored blue, and a point TT such that the points of TP∖{T}TP\setminus\{T\} are red, and the points of TQ∖{T}TQ\setminus\{T\} are all blue. Without loss of generality, we may assume that TT is colored blue. Hence, the line TQTQ is completely blue. Lemma 3.5 now shows that a unique unbalanced line through a blue point is completely blue and passes through TT. Assume that there are kk such completely blue lines through TT. Note that since all lines but TPTP through PP are balanced, r≠q+1r\ne q+1.

First, assume that k=1k=1. Color every point on the line TQTQ red. If rr was qq, then since through QQ every line but TQTQ was balanced, now the entire plane will be red and hence the proposition follows. If r<qr<q then in this new coloring, let us call lines with r+1r+1 red points be balanced. The number of red points on every line but TQTQ was increased by one, and so in this new coloring balanced lines are exactly those that were balanced earlier (TQTQ remains unbalanced since q+1≠r+1q + 1 \ne r + 1). But now, the points with a unique unbalanced line through them are all red, the unique unbalanced line is completely red, and there are at least two such lines (TQTQ and TPTP). A contradiction follows from Lemma 3.3 and from Lemma 3.4 and hence if k=1k = 1 then r=qr = q.

Now suppose that k>1k > 1. Note that this means that if a unique unbalanced line passes through a red point P′P', then it must be the line P′TP'T and the points of this line are all red except TT. We show that each line through TT is unbalanced. On the contrary, suppose that there is a balanced line ℓ\ell through TT. From above this means that there is no point on ℓ\ell through which a unique unbalanced line passes, otherwise ℓ\ell would be unbalanced. (Note that through TT there pass at least three unbalanced lines.) Since unbalanced lines cover all points, counting them through the points of ℓ\ell we see at least 2(q+1)2(q + 1) unbalanced lines; a contradiction. Hence all lines through TT are unbalanced. Let ee be a line through TT. Now if through each point of e∖{T}e \setminus\{T\}, another unbalanced line passes different from ee, then again in total we count at least 2q+12q + 1 unbalanced lines. This means that each line through TT contains a point SS such that STST is the unique unbalanced line through SS and hence the proposition follows.

We summarize the results above in the following theorem.

Theorem 3.7. Color the points of the plane PG⁡(2,q)\operatorname{PG}(2,q) either red or blue. A line is balanced if it contains rr red and bb blue points, where $0 \le r \le b \le q + 1. Assume unbalanced lines form a dual blocking set and there are less than $2q+1. Then, the red points form one of the following structures:

(1) a point,

(2) a line and a point not on the line,

(3) rr concurrent lines,

(4) rr concurrent lines minus their intersection,

(5) a Baer subplane.

Proof. By Lemma 3.1, there are points uniquely covered by unbalanced lines. If these points are of different colors, then by Proposition 3.6, we are in cases (3), (4). If they are of the same color, then Lemmas 3.3 and 3.4, along with the assumption that r≤br \le b, lead to cases (1), (2), and (5).

Unbalanced lines do not form a dual blocking set

Preliminaries for general qq

In this subsection, we assume that the unbalanced lines do not cover all points. By counting the red points through such a non-covered point, we immediately see that all such points must have the same color. Hence, we make the following assumption.

Assumption 3.8. Points that are not covered by unbalanced lines are blue, and thus the total number of red points is (q+1)r(q + 1)r.

Proposition 3.9. Assume that points not covered by unbalanced lines are blue. Then, either a line is completely red with the points outside being blue, or no point is covered by exactly one unbalanced line.

Proof. Assume that PP is a point through which exactly one unbalanced line passes. Since points not covered by an unbalanced line are blue, by counting the red points on the unbalanced line through PP, we see that PP must be red. Let ll be the unique unbalanced line through PP with r0r_0 red points. Counting the red points on the lines through PP, we find that the total number of red points is q(r−1)+r0q(r-1)+r_0, which is (q+1)r(q+1)r (by Assumption 3.8). Hence, we have r0−r=qr_0-r=q, i.e., either r0=q+1r_0=q+1 and r=1r=1, or r0=qr_0=q and r=0r=0. In the first case, looking around from PP, we see that all points outside ll must be blue. The second case is not possible, as it implies that balanced lines are completely blue, but PP is red.

Next, we will use the famous nuclei polynomial to show that there cannot be too many points not covered by the unbalanced lines. To that we identify the points of AG⁡(2,q)\operatorname{AG}(2,q) with the elements in Fq2\mathbb{F}_q^2 and so three distinct points aa, bb, cc are collinear if and only if (a−c)q−1=(b−c)q−1(a-c)^{q-1}=(b-c)^{q-1} holds. This way the ideal points (directions) correspond to (q+1)(q+1)-th roots of unity. (For more details see [10], Section 2.2.) We will need the following assumption.

Assumption 3.10. There is a line for which the number of red points is not rr (mod pp).

The example coming from a dual hyperoval, mentioned in the Introduction, shows that the existence of lines with not rr mod pp secants is relevant. The second author showed in [13] that such examples only occur for qq even if the number of unbalanced lines is at most 4q/34q/3. He also described the two non-trivial examples.

Proposition 3.11. Assume that the unbalanced lines do not cover all points. Under Assumption 3.10, there are at most q−1q-1 points not covered by an unbalanced line.

Proof. Let us choose the line at infinity as the line guaranteed by Assumption 3.10. Then, the number of red points on the remaining affine plane is non-zero modulo pp.

Identify the points of AG⁡(2,q)\operatorname{AG}(2,q) with the elements in Fq2\mathbb{F}_q^2, and hence the affine red points R′R' form a subset of Fq2\mathbb{F}_q^2. Let a1,…,aka_1,\ldots,a_k be the red points on the line at infinity, which can be viewed as the (q+1)(q+1)-th roots of unity. Write the following polynomial for the red points:

F(X)=∑a∈R′(X−a)q−1+a1+…+ak,F(X)=\sum_{a\in R'}(X-a)^{q-1}+a_1+\ldots+a_k,

The polynomial is not identically zero, since its leading coefficient is non-zero (it corresponds to the number of affine red points). When X=x0X=x_0 is a blue point not covered by an unbalanced line (Assumption 3.8), x0x_0 is a root of F(X)F(X). This is because all the lines through x0x_0 contain rr red points (including the point at infinity), so F(x0)F(x_0) is rr times the sum of all (q+1)(q+1)-th roots of unity, which equals zero. This proves the proposition.

By Proposition 3.9, if we are not in the case where a line is completely red with the points outside being blue, then the unbalanced line in the dual plane forms a set with no tangents, and at most q−1q-1 lines are disjoint from it. Such sets can be characterized if we impose a suitable bound on their size.

Lemma 3.12. Assume that SS is a set of size at most 2q+12q+1 in PG⁡(2,q)\operatorname{PG}(2,q), with no tangents and at most q−1q-1 lines disjoint from SS. Then, SS is the symmetric difference of two lines, unless q=4q=4, ∣S∣=9|S|=9, and SS is the complement of the union of three non-concurrent lines.

Proof. Pick any point PP not in SS. Since ∣S∣≤2q+1|S|\leq2q+1, there is a line through PP that is disjoint from SS. In other words, the points outside SS are covered by lines disjoint from SS. There are at most q−1q-1 lines disjoint from SS, and they can cover at most (q−1)q+1(q-1)q+1 points (equality holds only if there are q−1q-1 passant lines and these lines are concurrent). Thus, SS must contain at least 2q2q points, and for ∣S∣=2q|S|=2q, the set SS is the symmetric difference of the two remaining lines passing through the common points of the q−1q-1 passants.

Now assume that ∣S∣=2q+1|S|=2q+1. Then its complement has q2−qq^2-q points and is covered by at most q−1q-1 passants. If q=2q=2, the complement has 2 points, whereas a passant has 3, which is impossible. If q=3q=3, the complement has 6 points; one passant covers only 4 points, while two distinct passants have union of size 7, so this case is also impossible.

Now let q>4q>4. Since q−2q-2 lines cover at most (q−2)(q+1)<q2−q(q-2)(q+1)<q^2-q points, there must be q−1q-1 passants. Let mm be the maximum number of these passants through a point. They cannot all be concurrent, so 2≤m≤q−22\leq m\leq q-2; the mm lines through this point cover 1+mq1+mq points, and each remaining line adds at most q+1−mq+1-m new points. Hence their union has size at most

1+mq+(q−1−m)(q+1−m)=q2−m(q−m)≤q2−2q+4<q2−q,1+mq+(q-1-m)(q+1-m)=q^2-m(q-m)\leq q^2-2q+4<q^2-q,

a contradiction. Thus q=4q=4 is the only remaining case. Here three passants are necessary and they must be non-concurrent; their union is precisely the complement of SS.

Theorem 3.13. Color the points of the plane PG⁡(2,q)\operatorname{PG}(2,q) either red or blue. A line is balanced if it contains rr red and bb blue points, where 0<r≤b<q+10<r\leq b<q+1. Assume that there are at most 2q+12q+1 unbalanced lines, and they do not cover all the points of PG⁡(2,q)\operatorname{PG}(2,q). Furthermore, suppose that there exists an unbalanced line with not r mod pr\bmod p red points on it. Assume moreover that q>3q>3. Then, the red points form one of the following structures: either a line with qq red points and a point outside the line; or two completely red lines and a point outside these lines.

Proof. We may assume that we are not in the case where a line is completely red with the points outside being blue, since in this case all lines contain 1 mod pp red points. By Proposition 3.11, Proposition 3.9, and Lemma 3.12, applied in the dual plane, either the unbalanced lines form the symmetric difference of two pencils, or q=4q=4 and they are precisely the nine lines avoiding three non-collinear points AA, BB, CC.

We first exclude the latter case. Let ℓ\ell be an unbalanced line whose number of red points is not congruent to rr modulo 2. Choose coordinates such that

A=(1:0:0),B=(0:1:0),C=(0:0:1),ℓ:x+y+z=0.A=(1:0:0),\qquad B=(0:1:0),\qquad C=(0:0:1),\qquad\ell:x+y+z=0.

Let ω∈F4\omega\in\mathbb{F}_4 satisfy ω2+ω+1=0\omega^2+\omega+1=0. The six lines

x+y+z=0,z=0,y+z=0,x+z=0,x+ωy=0,x+ω2y=0x+y+z=0,\qquad z=0,\qquad y+z=0,\qquad x+z=0,\qquad x+\omega y=0,\qquad x+\omega^2y=0

form a dual hyperoval. Apart from ℓ\ell, each passes through one of AA, BB, CC and is therefore balanced. Counting incidences between red points and the six lines of the dual hyperoval, each red point is counted either zero or twice. On the other hand, ℓ\ell contributes ∣ℓ∩R∣|\ell\cap R| incidences and each of the other five lines contributes rr, since it is balanced. Hence,

∣ℓ∩R∣+5r≡0(mod2).|\ell\cap R|+5r\equiv0\pmod{2}.

Hence ∣ℓ∩R∣≡r(mod2)|\ell\cap R|\equiv r\pmod{2}, a contradiction.

Thus there are two points, P1P_1 and P2P_2, such that every unbalanced line passes through one of them. Moreover, the line joining them, P1P2P_1P_2, is balanced.

Assume there is a line through P1P_1, different from P1P2P_1P_2, that contains both a red point and a blue point (different from P1P_1). Let us denote these points as R1R_1 and B1B_1, respectively. Counting the red points through R1R_1 and B1B_1 immediately shows that the line R1P2R_1P_2 must be completely red (except possibly at P2P_2), and similarly, the line B1P2B_1P_2 must be entirely blue. Therefore, the points on the lines through P2P_2, except for P2P_2 itself, must be monochromatic. If there is no such line through P1P_1, we immediately can conclude the same for the lines through P1P_1.

Thus, for one of P1,P2P_1, P_2, say P2P_2, the qq lines through P2P_2 different from P1P2P_1P_2 are monochromatic apart from P2P_2. Let kk of them be red. Every line through neither P1P_1 nor P2P_2 is balanced and contains kk red points from these lines; hence all points of P1P2∖{P1,P2}P_1P_2 \setminus\{P_1, P_2\} have the same color. They cannot be red, since r≤(q+1)/2<q−1r \le(q + 1)/2 < q - 1 for q>3q > 3, so they are blue and k=rk = r. Since P1P2P_1P_2 is balanced and r>0r > 0, it follows that r=1r = 1 or 22, according to how many of P1,P2P_1, P_2 are red. These two cases give the two structures in the statement (the completely red line case having been excluded at the beginning).

The original Erdős problem in PG(2, q) and nearby cases

In this section, we consider the original problem of Erdős, that is r=b=(q+1)/2r = b = (q + 1)/2, and extend the argument to

r+b=q+1,∣r−q+12∣≤p−32,r + b = q + 1,\qquad\left|r - \frac{q + 1}{2}\right| \le\frac{p - 3}{2},

where q=phq = p^h and pp is odd. Theorem 3.7 settles this problem when the unbalanced lines cover all points of the plane. Hence we will assume that the unbalanced lines do not cover all points of PG(2, qq).

For the lemmas and proposition below, we may interchange the colors and suppose that a point not covered by unbalanced lines is red; we do not assume r≤br \le b. This means that

∣R∣=(q+1)(r−1)+1,∣B∣=(q+1)b.|R| = (q + 1)(r - 1) + 1,\qquad|B| = (q + 1)b.

If q>3q > 3 and min⁡{r,b}≥3\min\{r, b\} \ge3, Theorem 3.13, applied with the colors interchanged if necessary, implies that a coloring with at most 2q+12q + 1 unbalanced lines must have r mod pr \bmod p red points on every line. Indeed, q>4q > 4, and the two exceptional structures have min⁡{r,b}≤2\min\{r, b\} \le2. If q=pq = p, our bounds on rr imply that every line with r mod pr \bmod p red points is balanced. Thus every line would be balanced, a contradiction. Hence q≥p2q \ge p^2.

Lemma 4.1. Let r+b=q+1r + b = q + 1 and assume that the unbalanced lines, UU, do not form a dual blocking set. Let RR be the set of red points and BB the set of blue points. Then

D:=∑ℓ∈U(∣ℓ∩R∣−r)2=∑ℓ∈U(∣ℓ∩B∣−b)2=qrb.D := \sum_{\ell\in U} (|\ell\cap R| - r)^2 = \sum_{\ell\in U} (|\ell\cap B| - b)^2 = qrb.

Proof. Let rir_i denote the number of red points on the line ℓi\ell_i. The standard equations give

∑iri=∣R∣(q+1),∑iri2=∣R∣(∣R∣+q).\sum_i r_i = |R|(q + 1),\qquad\sum_i r_i^2 = |R|(|R| + q).

Since balanced lines contribute zero, we obtain

D=∑i(ri−r)2=∣R∣(∣R∣+q)−2r∣R∣(q+1)+(q2+q+1)r2=qrb,\begin{aligned} D &= \sum_i (r_i - r)^2\\ &= |R|(|R| + q) - 2r|R|(q + 1) + (q^2 + q + 1)r^2\\ &= qrb, \end{aligned}

where we used ∣R∣=(q+1)r−q|R| = (q + 1)r - q and r+b=q+1r + b = q + 1. Finally, ∣ℓ∩R∣−r=−(∣ℓ∩B∣−b)|\ell\cap R| - r = -(|\ell\cap B| - b).

We will call a line a blue (or red) majority line if it contains more than bb blue (or rr red) points.

Lemma 4.2. Let r+b=q+1r+b=q+1 and ∣r−(q+1)/2∣≤(p−3)/2\lvert r-(q+1)/2\rvert\le(p-3)/2. Assume that the unbalanced lines do not form a dual blocking set and that every line contains r mod pr\bmod p red points. Then at least three blue majority lines pass through every blue point.

Proof. Counting the blue points on the lines through a blue point PP, we count every other blue point once and PP itself q+1q+1 times. Subtracting bb for each of the q+1q+1 lines gives

∑ℓ∋P(∣ℓ∩B∣−b)=∣B∣+q−(q+1)b=q.\sum_{\ell\ni P}(\lvert\ell\cap B\rvert-b)=\lvert B\rvert+q-(q+1)b=q.

Write r=(q+1)/2+er=(q+1)/2+e, where ∣e∣≤(p−3)/2\lvert e\rvert\le(p-3)/2. By the congruence assumption, every line contains at least (p+1)/2+e(p+1)/2+e red points, and hence at most q+1−(p+1)/2−eq+1-(p+1)/2-e blue points. Thus each positive summand is at most (q−p)/2(q-p)/2. Two positive summands cannot give a total of qq, and hence at least three blue majority lines pass through PP.

Proposition 4.3. Let r+b=q+1r+b=q+1 and ∣r−(q+1)/2∣≤(p−3)/2\lvert r-(q+1)/2\rvert\le(p-3)/2. Assume that the unbalanced lines do not form a dual blocking set and that every line contains r mod pr\bmod p red points. Then the number of unbalanced lines is at least 2q+22q+2.

Proof. Suppose, for a contradiction, that there are at most 2q+12q+1 unbalanced lines. As noted at the beginning of the section, q≥p2q\ge p^2. By the preceding lemma, at least three blue majority lines pass through every blue point.

Put r=(q+1)/2+er=(q+1)/2+e, where ∣e∣≤(p−3)/2\lvert e\rvert\le(p-3)/2. Let ℓ\ell be the line containing the maximum number of blue points, and suppose that ℓ\ell has dd red points and q+1−dq+1-d blue points. The congruence assumption gives

d≥p+12+e≥2.d\ge\frac{p+1}{2}+e\ge2.

Since ℓ\ell is a blue majority line, r−dr-d is a positive multiple of pp, so d≤r−p<(q+1)/2d\le r-p<(q+1)/2.

We now show that every line contains at most 2r−d2r-d red points. Counting through a red point PP gives

∑m∋P(∣m∩B∣−b)=0,\sum_{m\ni P}(\lvert m\cap B\rvert-b)=0,

so a red point lies either on zero or on at least two unbalanced lines. Let ℓ′\ell' be a red majority line. If a red point on ℓ\ell lies on exactly two unbalanced lines, say ℓ′\ell' and ℓ′′\ell'', then the deviations from rr on these two lines sum to zero. Since ∣ℓ′′∩B∣≤q+1−d\lvert\ell''\cap B\rvert\le q+1-d by the choice of ℓ\ell, we obtain

∣ℓ′∩R∣−r=r−∣ℓ′′∩R∣=∣ℓ′′∩B∣−b≤r−d.\lvert\ell'\cap R\rvert-r=r-\lvert\ell''\cap R\rvert=\lvert\ell''\cap B\rvert-b\le r-d.

If there is no such red point on ℓ\ell, then through each red point on ℓ\ell there must pass at least two unbalanced lines other than ℓ\ell. Moreover, through every blue point on ℓ\ell there are at least three blue majority lines, all different from ℓ\ell. Thus every point of ℓ\ell is on at least two unbalanced lines other than ℓ\ell; so we would see at least 2(q+1)+12(q+1)+1 unbalanced lines, a contradiction. In particular, every term in DD is at most (r−d)2(r-d)^2.

We now provide an upper bound on the sum DD from Lemma 4.1. To do so, we first show that the number of blue points on ℓ\ell with exactly three unbalanced lines is at least q+2−2dq+2-2d. Assume, for a contradiction, that there are at least dd blue points on ℓ\ell with more than three unbalanced lines. Each of the dd red points on ℓ\ell lies on at least one further unbalanced line, dd of the blue points lie on at least three further unbalanced lines each, and the remaining q+1−2dq + 1 - 2d blue points lie on at least two each. These lines are distinct, so, including ℓ\ell, we obtain at least

1+d⋅1+d⋅3+(q+1−2d)⋅2=2q+3,1 + d \cdot1 + d \cdot3 + (q + 1 - 2d) \cdot2 = 2q + 3,

which is again a contradiction.

Let TT be a blue point on ℓ\ell with exactly three unbalanced lines: ℓ\ell, ℓ1\ell_1, and ℓ2\ell_2. All three are blue majority lines. Since

(∣ℓ1∩B∣−b)+(∣ℓ2∩B∣−b)=q−r+d(\lvert\ell_1 \cap B \rvert- b) + (\lvert\ell_2 \cap B \rvert- b) = q - r + d

and each summand is at most r−dr - d, their sum of squares is maximized when one equals r−dr - d and the other equals q−2r+2dq - 2r + 2d. Hence,

(∣ℓ1∩B∣−b)2+(∣ℓ2∩B∣−b)2≤(r−d)2+(q−2r+2d)2.(\lvert\ell_1 \cap B \rvert- b)^2 + (\lvert\ell_2 \cap B \rvert- b)^2 \le(r - d)^2 + (q - 2r + 2d)^2.

Choose q+2−2dq + 2 - 2d such points TT; they give disjoint pairs of terms in DD. The remaining terms can be estimated from above by (r−d)2(r - d)^2. Thus, using the fact that there are at most 2q+12q + 1 unbalanced lines, we obtain

D≤(q+2−2d)(q−2r+2d)2+(q−1+2d)(r−d)2.D \le(q + 2 - 2d)(q - 2r + 2d)^2 + (q - 1 + 2d)(r - d)^2.

Put t=d−et = d - e and K=(p−3)/2K = (p - 3)/2. The congruence assumption gives t≥(p+1)/2t \ge(p + 1)/2. The three blue majority lines through TT also give q≤3(r−d)q \le3(r - d), so 6t≤q+36t \le q + 3. Using D=qrbD = qrb and multiplying the preceding inequality by four, we obtain 0≤fe(t)0 \le f_e(t), where

fe(t)=4(q+2−2t−2e)(2t−1)2+(q−1+2t+2e)(q+1−2t)2−q((q+1)2−4e2).f_e(t) = 4(q + 2 - 2t - 2e)(2t - 1)^2 + (q - 1 + 2t + 2e)(q + 1 - 2t)^2 - q((q + 1)^2 - 4e^2).

We show that fe(t)<0f_e(t) < 0. First,

f0(t)=−2t(q−3t+3)2−(q−1)2−2(t−2)(3t2−2t+4)−8<0,f_0(t) = -2t(q - 3t + 3)^2 - (q - 1)^2 - 2(t - 2)(3t^2 - 2t + 4) - 8 < 0,

since t≥(p+1)/2≥2t \ge(p + 1)/2 \ge2 and so each term is negative. This settles the case p=3p = 3, since then e=0e = 0.

Now let p≥5p \ge5. Since 6t≤q+36t \le q + 3, we have

A:=(q+1−2t)2−4(2t−1)2≥0.A := (q + 1 - 2t)^2 - 4(2t - 1)^2 \ge0.

As ∣e∣≤K\lvert e \rvert\le K, it follows that

fe(t)=f0(t)+2eA+4qe2≤f0(t)+2KA+4qK2=fK(t).f_e(t) = f_0(t) + 2eA + 4qe^2 \le f_0(t) + 2KA + 4qK^2 = f_K(t).

Moreover,

fK(t+1)−fK(t)=−72(t−3q+4−6K18)2+16(13−K)q+8(K−23)2−6<0,f_K(t + 1) - f_K(t) = -72\left(t - \frac{3q + 4 - 6K}{18}\right)^2 + 16\left(\frac{1}{3} - K\right)q + 8\left(K - \frac{2}{3}\right)^2 - 6 < 0,

since K≥1K \ge1 and q≥p2=(2K+3)2q \ge p^2 = (2K + 3)^2. Therefore,

fe(t)≤fK(p+12)=−5q2+(2p2+8)q−6p3+13p2=−5(q−p2)2−8(p2−1)(q−p2)−3p2(p2+2p−7)<0.\begin{aligned} f_e(t) &\le f_K\left(\frac{p + 1}{2}\right) \\ &= -5q^2 + (2p^2 + 8)q - 6p^3 + 13p^2 \\ &= -5(q - p^2)^2 - 8(p^2 - 1)(q - p^2) - 3p^2(p^2 + 2p - 7) < 0. \end{aligned}

This is a contradiction.

Theorem 3.13 together with the preceding proposition yield immediately the following corollary. Its assumptions do not prescribe the color of the points not covered by unbalanced lines.

Corollary 4.4. Let q=ph>3q=p^h>3, where pp is odd, and let r+b=q+1r+b=q+1, 3≤r≤b3\le r\le b, r≥q−p+42r\ge\frac{q-p+4}{2}.

If the unbalanced lines do not form a dual blocking set, then there are at least 2q+22q+2 unbalanced lines.

Applying the preceding corollary with r=b=(q+1)/2r=b=(q+1)/2 and combining it with Theorem 3.7, noting that in the latter only cases (3) and (4) are possible, immediately gives the following theorem.

Theorem 4.5. Let r=b=q+12r=b=\frac{q+1}{2} and q>3q>3. Then the number of unbalanced lines is at least 2q+12q+1 unless the coloring is the trivial coloring defined in Definition 1.2.

The case of the Desarguesian plane of prime order

Let us consider the pointset RR that is the points colored red. We have already noted that the case when q=pq=p is prime is special in the sense that, in this case most of the time, the set of non-(r mod p)(r\bmod p)-secants of RR coincides with the set of unbalanced lines. Under the assumption r≤br\le b, there are two exceptions, namely when r=0r=0 a line with pp red points is unbalanced but contains r mod pr\bmod p red points, similarly when r=1r=1 a line with p+1p+1 red points is unbalanced but contains r mod pr\bmod p red points.

First, we will consider the case when the number of unbalanced lines (δ\delta) is relatively small (at most max⁡{3p+1,4p−22}\max\{3p+1,4p-22\}). Subsequently, we will allow δ\delta to be at most dp(p+1)d\sqrt{p}(p+1), while ensuring that the number of red points rr (or the number of blue points bb) on a balanced line, remains small, at most cpc\sqrt{p}. For more on the constants c,dc,d see Theorem 5.18

We will consider multisets of PG⁡(2,q)\operatorname{PG}(2,q), q=phq=p^h, pp prime, these sets are related to codewords generated by lines of the dual plane of PG⁡(2,q)\operatorname{PG}(2,q). Such codes are naturally considered over the prime field of Fp\mathbb{F}_p and so the multiplicities of the points in a multiset will also be considered over Fp\mathbb{F}_p. We mostly consider the multiplicities as integers between 0 and p−1p-1, but there will be cases when we want to minimize their absolute values and so we will allow negative multiplicities. We will say that a point is not in a given multiset if it has multiplicity 0. The size of a multiset is the sum of the multiplicities and the intersection number of a line and a multiset is the sum of the multiplicities of the points on that line.

Not too many unbalanced lines

A very special case

From another aspect, the very special case of the Erdős problem in question has already been studied by Kiss and Somlai. They investigated point sets in AG⁡(2,p)\operatorname{AG}(2,p). A point set M⊂AG⁡(2,p)M\subset\operatorname{AG}(2,p) is said to admit a non-special direction (dd) if every line with slope dd contains exactly rr points, for some fixed integer 1≤r≤p1\le r\le p. A direction is special otherwise. They characterized point sets admitting at most three special directions.

Color the points of MM red and all other points in PG⁡(2,p)\operatorname{PG}(2,p) blue, and call a line balanced if it contains exactly rr red points. Then, all lines in a non-special direction are balanced, and hence a point set with few special directions results in a coloring with few unbalanced lines.

Given a prime number pp, we can interpret the elements of Fp\mathbb{F}_p as the integers from 0 to p−1p-1. This naturally defines an ordering << on the elements of Fp\mathbb{F}_p. Kiss and Somlai proved the following results.

Example 5.1 (Kiss, Somlai). [11] Let p>2p>2 be a prime. Then the set

S={(x,y)∈Fp2∣y<x}S=\{(x,y)\in\mathbb{F}_p^2\mid y<x\}

has exactly three special directions, namely (0)(0), (1)(1) and (∞)(\infty).

Result 5.2 (Kiss, Somlai). [11] Let MM be a point set in AG⁡(2,p)\operatorname{AG}(2,p). Let (d)(d) be a non-special direction and assume that on each line with slope dd, we see 1≤r≤p1\le r\le p points. If MM admits at most three special directions, then MM is either a union of rr parallel lines or, up to an affine transformation, it is equivalent to SS or its complement in Example 5.1.

The above result can be translated into the following very special case of our Erdős problem. Although it may seem extreme, we will see later that it will be very useful.

Proposition 5.3. Color the points of PG⁡(2,p)\operatorname{PG}(2,p), where p≥19p\ge19, into red and blue. A line is called balanced if it contains exactly rr, where 0<r<p+10<r<p+1, red points. Suppose that there are at most max⁡{3p+1,4p−22}\max\{3p+1,4p-22\} unbalanced lines and assume that there is a line ℓ\ell so that all unbalanced lines different from ℓ\ell intersect ℓ\ell in at most three different points, P1,…,PkP_1,\ldots,P_k, 1≤k≤31\le k\le3. Then one of the following holds:

  1. The red point set is the union of rr concurrent lines through one of the points PiP_i, with their common point removed, together with a subset of {P1,…,Pk}\{P_1,\ldots,P_k\}; and the blue point set has the analogous form with rr replaced by b=p+1−rb=p+1-r.

  1. One of the two color classes is, up to an affine transformation, equivalent to SS or its complement in Example 5.1, together with a subset of the directions {(0),(1),(∞)}\{(0),(1),(\infty)\}.

Proof. Let PP and QQ be two points on a line ℓ\ell through which all lines except ℓ\ell are balanced. By counting the number of red points on the lines through PP and then through QQ, we deduce that PP and QQ must have the same color, say blue. Now, let ℓ\ell be the line at infinity and consider the set of red points outside ℓ\ell. If there were none, then rr must have been 0, which is not possible. Otherwise the result follows from Result 5.2.

Preliminary results on codewords and special pointsets

In this subsection, similarly to [1], we will establish a connection between the set of red points of PG⁡(2,p)\operatorname{PG}(2,p) and a codeword of the code C1(2,p)C_1(2,p). The results will then follow from earlier results on small weight codewords.

Definition 5.4. Let P={P1,P2,…,Pp2+p+1}\mathcal{P}=\{P_1,P_2,\ldots,P_{p^2+p+1}\} denote the set of points of PG⁡(2,p)\operatorname{PG}(2,p), pp is prime. We define the characteristic vector of a line ℓ\ell in PG⁡(2,p)\operatorname{PG}(2,p) as the vector

χℓ=(χℓ,1,χℓ,2,…,χℓ,p2+p+1)∈Fpp2+p+1,\chi_\ell=(\chi_{\ell,1},\chi_{\ell,2},\ldots,\chi_{\ell,p^2+p+1})\in\mathbb{F}_p^{p^2+p+1},

where

χℓ,i={1if Pi∈ℓ,0otherwise.\chi_{\ell,i}= \begin{cases} 1 & \text{if }P_i\in\ell,\\ 0 & \text{otherwise.} \end{cases}

The code C1(2,p)C_1(2,p) is defined as the Fp\mathbb{F}_p-span of the characteristic vectors of the lines of PG⁡(2,p)\operatorname{PG}(2,p). Let c=(c1,c2,…,cp2+p+1)c=(c_1,c_2,\ldots,c_{p^2+p+1}) be a codeword in C1(2,p)C_1(2,p). Then, the weight of the codeword, denoted by w(c)w(c), is the number of non-zero coordinates in cc. The support, supp⁡(c)\operatorname{supp}(c), of cc is the set of points PiP_i corresponding to the non-zero coordinates of cc.

We will use the following result from the last two authors. For the exact statement, see [16 Theorem 4.8, Corollary 4.10]; here, we only require a simplified version.

Result 5.5 (Szőnyi, Weiner). [16] Suppose that p≥19p\ge19 is a prime and that c∈C1(2,p)c\in C_1(2,p) with w(c)≤max⁡{3p+1,4p−22}w(c)\le\max\{3p+1,4p-22\}. Then cc is either a linear combination of at most three lines or supp⁡(c)\operatorname{supp}(c) can be covered by three concurrent lines.

Notation 5.6. Coordinates of a point in PG⁡(2,p)\operatorname{PG}(2,p) will be denoted by (a,b,c)(a,b,c) while the coordinates of a line with [a,b,c][a,b,c].

Next we will establish the connection between the coloring of the points of PG⁡(2,p)\operatorname{PG}(2,p) and codewords.

Definition 5.7. Color the points of PG⁡(2,p)\operatorname{PG}(2,p) red and blue and consider the set of red points RR. Define

cR=∑(x,y,z)∈Rχ[x,y,z]c_R=\sum_{(x,y,z)\in R}\chi_{[x,y,z]}

Note that the coordinate of cRc_R corresponding to the point (a,b,c)(a,b,c) is the number of points of RR on the line [a,b,c][a,b,c] modulo pp.

Lemma 5.8. Let jj be the all 11 vector. The coordinate of the codeword cR−rjc_R-rj corresponding to the point (a,b,c)(a,b,c) is non-zero if and only if the line [a,b,c][a,b,c] intersects the point set RR in not rr mod pp points.

In our case, w(cR−rj)w(c_R-rj) will be small and hence we will be able to apply Result 5.5.

Colorings with at most max⁡{3p+1,4p−22}\max\{3p+1,4p-22\} unbalanced lines

In this subsection, we will assume that p≥19p\ge19 prime. We color the points of PG⁡(2,p)\operatorname{PG}(2,p) red and blue. We call a line balanced if it contains exactly rr red points, where 0≤r≤b=p+1−r0\le r\le b=p+1-r. Throughout this subsection, we will assume that the number of unbalanced lines is at most max⁡{3p+1,4p−22}\max\{3p+1,4p-22\}. As mentioned before, unbalanced lines which contain not rr mod pp red points will be handled by earlier results.

Definition 5.9. We call an unbalanced line containing not rr mod pp red points a regular unbalanced line.

Under the assumption 0≤r≤b0\le r\le b, a non-regular unbalanced line can occur only when r=0r=0 or r=1r=1: in the former case it is a pp-secant of RR, while in the latter case it is a completely red line. We first examine these two exceptional cases.

Lemma 5.10. Let RR be the set of red points and let δ\delta denote the number of unbalanced lines. Then the following hold:

  1. If r=0r=0, for every integer kk with 1≤k≤min⁡{∣R∣,p+1}1\le k\le\min\{|R|,p+1\}, we have

δ≥k(p+1)−(k2).\delta\ge k(p+1)-\binom{k}{2}.

Moreover, if there is a non-regular unbalanced line, then δ≥p2+1\delta\ge p^2+1.

(2) If r=1r=1 and ℓ\ell is a completely red line, then for every integer kk with 1≤k≤min⁡{∣R∖ℓ∣,p+1}1 \le k \le\min\{|R\setminus\ell|,p+1\}, we have

δ≥1+k(p+1)−(k2)\delta\ge1+k(p+1)-\binom{k}{2}

(3) If 2≤r≤b2 \le r \le b, then every unbalanced line is regular.

Proof. For any k≤p+1k \le p+1 distinct points, the union of the pencils through them contains at least

k(p+1)−(k2)k(p+1)-\binom{k}{2}

lines: when the ii-th pencil is added, at most i−1i-1 of its lines have occurred before. If r=0r=0, every line through a red point is unbalanced, which gives the first inequality in (1). A non-regular unbalanced line then contains exactly pp red points. The pp red points on such a line determine p2p^2 distinct lines different from it, all unbalanced, giving at least p2+1p^2+1 unbalanced lines.

If r=1r=1 and ℓ\ell is completely red, every line through a red point outside ℓ\ell contains at least two red points and hence is unbalanced. The line ℓ\ell itself is not among these pencils, which proves (2). Finally, (3) is immediate. □

Lemma 5.11. Color the points of PG⁡(2,p)\operatorname{PG}(2,p), where p≥19p \ge19 is prime, red and blue, and call a line balanced if it contains exactly 0≤r≤b=p+1−r0 \le r \le b=p+1-r red points. Assume that the number of unbalanced lines is at most max⁡{3p+1,4p−22}\max\{3p+1,4p-22\}. Then, the following holds:

(1) There exist at most three points with the property that every regular unbalanced line contains at least one of them.

(2) Suppose that we need three non-collinear points, P1P_1, P2P_2, and P3P_3, in order to block all regular unbalanced lines. Then there exist non-zero multiplicities m1,m2,m3∈Fp∗m_1,m_2,m_3 \in\mathbb{F}_p^* so that the union of the points PiP_i with multiplicity mim_i and the set of red-colored points forms a multiset in which every line contains exactly r mod pr \bmod p points (counted with multiplicities).

Proof. For the set of red points RR, construct the codeword cRc_R (see Definition 5.7), and define

cR∗=cR−rj.c_R^*=c_R-rj.

where jj is the all-ones vector. By Lemma 5.8 and by the assumption of the lemma, we have

w(cR∗)≤max⁡{3p+1,4p−22}.w(c_R^*)\le\max\{3p+1,4p-22\}.

Thus, by Result 5.5, the support of cR∗c_R^* can be covered by at most three lines, which immediately implies (1).

Now, assume that exactly three lines ℓ1,ℓ2,ℓ3\ell_1,\ell_2,\ell_3 are required to cover supp⁡(cR∗)\operatorname{supp}(c_R^*) and that these lines are not concurrent. By Result 5.5, there exist non-zero multiplicities m1∗,m2∗,m3∗∈Fp∗m_1^*,m_2^*,m_3^*\in\mathbb{F}_p^* such that

cR∗=∑i=13mi∗χℓi.c_R^*=\sum_{i=1}^{3}m_i^*\chi_{\ell_i}.

Rearranging, we obtain

rj=cR−∑i=13mi∗χℓi=cR+∑i=13(p−mi∗)χℓi.rj=c_R-\sum_{i=1}^{3}m_i^*\chi_{\ell_i} =c_R+\sum_{i=1}^{3}(p-m_i^*)\chi_{\ell_i}.

and hence (2) follows. □

Proposition 5.12. Suppose that p>5p > 5 and assume that there exist three non-collinear points P1P_1, P2P_2, P3P_3, so that each regular unbalanced line contains at least one of them. Suppose that there are at most max⁡{3p+1,4p−22}\max\{3p+1,4p-22\} unbalanced lines. Suppose moreover that there exists a multiset MM which agrees with RR outside {P1,P2,P3}\{P_1,P_2,P_3\} and in which every line contains exactly r(modp)r \pmod p points (counted with multiplicities). Then R∖{P1,P2,P3}R \setminus\{P_1,P_2,P_3\} is the union of rr lines, each passing through one of the points PiP_i, with P1,P2,P3P_1,P_2,P_3 removed; or r=1r=1 and RR consists of a completely red line together with a subset of {P1,P2,P3}\{P_1,P_2,P_3\} outside this line.

Proof. Let R∗=R∖{P1,P2,P3}R^* = R \setminus\{P_1,P_2,P_3\}. Let mim_i denote the multiplicity of PiP_i in MM. First we get rid of the exceptional cases.

If r=0r=0, then by Lemma 5.10(1), there is no non-regular unbalanced line. If there were a red point P∉{P1,P2,P3}P \notin\{P_1,P_2,P_3\}, all p+1p+1 lines through PP would be regular unbalanced, but at most three of them could contain one of the points PiP_i, a contradiction. Thus R∗=∅R^*=\varnothing, giving the first conclusion.

If r=1r=1 and there is a completely red line ℓ\ell, Lemma 5.10 shows that there are at most three red points outside ℓ\ell. In particular, ℓ\ell is the unique completely red line. If a red point PP outside ℓ\ell were not one of the PiP_i, then all p+1p+1 lines through PP would be regular unbalanced and would have to contain one of the three points PiP_i, again a contradiction. Hence the second conclusion holds.

We may therefore assume that r>0r>0 and that every unbalanced line is regular.

First, we will show that through one of the points PiP_i, 1≤i≤31 \le i \le3, say through PjP_j, there passes a line ℓ\ell such that either all points of ℓ∖{Pj}\ell\setminus\{P_j\} are in R∗R^* or none. Let PP be a point not in R∗R^* and not on the lines PiPjP_iP_j, for 1≤i≠j≤31 \le i \ne j \le3. Such a point exists, since otherwise a line avoiding P1,P2,P3P_1,P_2,P_3 would contain at least p−2>(p+1)/2≥rp-2 > (p+1)/2 \ge r red points and hence would be a regular unbalanced line avoiding all three points. Also, let QQ be a point of R∗R^* not on the lines PiPjP_iP_j. If no such point exists, then the lines through the points PiP_i show that each side of the triangle without the vertices is either contained in R∗R^* or disjoint from R∗R^*. Thus R∗R^* is the union of tt sides without vertices. A line avoiding P1,P2,P3P_1,P_2,P_3 is balanced, so t=rt=r, and the first conclusion follows. Now, consider counting the points of R∗R^* once on the lines through PP and also on the lines through QQ. Note that a line not passing through any PiP_i is balanced and hence contains exactly rr points of RR and hence of R∗R^* too, and so we have

(p−2)r+∣PP1∩R∗∣+∣PP2∩R∗∣+∣PP3∩R∗∣=1+(p−2)(r−1)+∣QP1∩R∗∣−1+∣QP2∩R∗∣−1+∣QP3∩R∗∣−1.(1)(p-2)r+\lvert PP_1\cap R^*\rvert+\lvert PP_2\cap R^*\rvert+\lvert PP_3\cap R^*\rvert =1+(p-2)(r-1)+\lvert QP_1\cap R^*\rvert-1+\lvert QP_2\cap R^*\rvert-1+\lvert QP_3\cap R^*\rvert-1. \tag*{(1)}

From this, we obtain:

p+∣PP1∩R∗∣+∣PP2∩R∗∣+∣PP3∩R∗∣=∣QP1∩R∗∣+∣QP2∩R∗∣+∣QP3∩R∗∣.(2)p+\lvert PP_1\cap R^*\rvert+\lvert PP_2\cap R^*\rvert+\lvert PP_3\cap R^*\rvert =\lvert QP_1\cap R^*\rvert+\lvert QP_2\cap R^*\rvert+\lvert QP_3\cap R^*\rvert. \tag*{(2)}

The multiset MM intersects each line in r(modp)r \pmod p points, and hence:

∣PPi∩R∗∣≡∣QPi∩R∗∣(modp).\lvert PP_i\cap R^*\rvert\equiv\lvert QP_i\cap R^*\rvert\pmod p.

Since R∗R^* is a set, equation (2) can only be true if for some 1≤j≤31 \le j \le3,

∣∣PPj∩R∗∣−∣QPj∩R∗∣∣=p,\bigl\lvert\lvert PP_j\cap R^*\rvert-\lvert QP_j\cap R^*\rvert\bigr\rvert=p,

which can only happen if one of ∣PPj∩R∗∣\lvert PP_j\cap R^*\rvert or ∣QPj∩R∗∣\lvert QP_j\cap R^*\rvert is 00 and the other is pp. Hence, we have found the required line ℓ\ell through the point PjP_j.

:::

Without loss of generality, we may assume that through P1P_1 there passes a line ℓ\ell, such that ∣ℓ∩R∗∣=p|\ell\cap R^*| = p. Since MM intersects every line in rr mod pp points, and all these lines have the same contribution at P1P_1 in MM, this implies that any line through P1P_1 and not passing through P2P_2 or P3P_3 must contain either 0 or pp points from R∗R^*.

Assume that there are kk lines through P1P_1 containing pp points from R∗R^*. To complete the proof, we only need to show that on the line P1P2P_1P_2 (and similarly on P1P3P_1P_3), there are either 0 or p−1p-1 points of R∗R^*.

Consider the lines through P3P_3 which do not pass through P2P_2 or P1P_1. From above, such a line intersects R∗R^* in either k+1k+1 or kk points, depending on whether the intersection with the line P1P2P_1P_2 is in R∗R^* or not. However, since MM contains rr points modulo pp on each line, it follows that these lines intersect the set R∗R^* in the same number of points, namely in (r−m3)(r-m_3) modulo pp points.

Therefore, all points of P1P2∖{P1,P2}P_1P_2 \setminus\{P_1,P_2\} belong to R∗R^* simultaneously, or none of them do. By interchanging the roles of P2P_2 and P3P_3, the same holds for P1P3P_1P_3. Thus R∗R^* is the union of tt lines through P1P_1, with P1,P2,P3P_1,P_2,P_3 removed. Any line avoiding P1,P2,P3P_1,P_2,P_3 is balanced and meets R∗R^* in exactly tt points, so t=rt=r, and the proof follows.

Finally, we are ready to state our main theorem of this section.

Theorem 5.13. Consider a coloring of the points of PG⁡(2,p)\operatorname{PG}(2,p), where p≥19p \ge19, with red and blue. A line is called balanced if it contains exactly 0≤r≤b=p+1−r0 \le r \le b = p+1-r red points. Suppose that there are at most max⁡{3p+1,4p−22}\max\{3p+1,4p-22\} unbalanced lines.

Then one of the following holds:

  1. There is a point PP such that, apart from PP, the points on rr lines through PP are red and the points on the remaining b=p+1−rb=p+1-r lines are blue. The point PP can have either color.

  2. A coloring obtained from (1) by switching the colors of at most two points different from PP.

  3. r=1r=1, and the red points consist of a line together with at most three points outside it.

  4. Either r=(p−1)/2r=(p-1)/2 and the red point set is, up to an affine transformation, equivalent to SS from Example 5.1 together with a subset of the directions {(0),(1),(∞)}\{(0),(1),(\infty)\}; or r=b=(p+1)/2r=b=(p+1)/2 and one of the two color classes is equivalent to the complement of SS in AG⁡(2,p)\operatorname{AG}(2,p), together with a subset of these three directions.

  5. r=3r=3, and the red point set is obtained from the union of the three sides of a triangle by possibly switching the colors of its three vertices.

Proof. Consider the set of red points RR. First suppose that r=0r=0. If ∣R∣≥4|R| \ge4, Lemma 5.10 gives

δ≥4(p+1)−(42)=4p−2>max⁡{3p+1,4p−22},\delta\ge4(p+1)-\binom{4}{2}=4p-2>\max\{3p+1,4p-22\},

a contradiction. Hence ∣R∣≤3|R| \le3, which is contained in cases (1) and (2).

Next suppose that r=1r=1 and there is a completely red line ℓ\ell. If there were at least four red points outside ℓ\ell, Lemma 5.10 would give

δ≥1+4(p+1)−(42)=4p−1>max⁡{3p+1,4p−22}.\delta\ge1+4(p+1)-\binom{4}{2}=4p-1>\max\{3p+1,4p-22\}.

Thus this gives case (3). We may therefore assume that r>0r>0 and that every unbalanced line is regular.

::: By Lemma 5.11 (1), the regular unbalanced lines can be covered by at most three points, say by the set of points BB. Choose BB minimal with this property. If there is a line containing all points of BB, then Proposition 5.3 completes the proof. Its first case gives (1) or (2), while its second case, using r≤br \le b, gives (4). Otherwise, BB consists of three non-collinear points, in which case Proposition 5.12, together with Lemma 5.11 (2) completes the proof. The proof of Proposition 5.12 shows that its first conclusion gives (1) or (2), except when r=3r = 3 and the three lines are the sides of a triangle, which gives (5). Its second conclusion gives (3).

More unbalanced lines with some additional restrictions

Preliminaries

We recall the stability result of kk mod pp sets of [16], translated into the coloring terminology used above. The results below are for general qq. Throughout these preliminary results, δ\delta denotes the number of regular unbalanced lines; this number is at most the total number of unbalanced lines.

Result 5.14 ([16 Theorem 1.1]). Color the points of PG⁡(2,q)\operatorname{PG}(2,q), q=phq = p^{h} red and blue, q>17q > 17 and assume that the number of regular unbalanced lines, δ\delta, is smaller than (q+1)q2(q+1)\sqrt{\frac{q}{2}}. Then there exists a point set LL, of size ⌈δq+1⌉\left\lceil\frac{\delta}{q+1}\right\rceil, such that every regular unbalanced line contains at least one point of LL. Moreover, by [16 Remark 3.3], LL can be chosen so that each P∈LP \in L lies on at least

q+1−(δq+1+2δ2(q+1)3)q+1-\left(\frac{\delta}{q+1}+\frac{2\delta^{2}}{(q+1)^{3}}\right)

regular unbalanced lines.

From this result, we get the following:

Corollary 5.15. Let PP be a point of PG⁡(2,q)\operatorname{PG}(2,q), q>17q > 17. If P∉LP \notin L, then at most ∣L∣|L| regular unbalanced lines pass through PP. In particular, if every unbalanced line is regular, then the number of balanced lines through PP is at least q+1−∣L∣q+1-|L|.

Property 5.16 ([16 Property 3.5]). Color the points of PG⁡(2,q)\operatorname{PG}(2,q) red and blue. We say that the property holds if whenever more than q/2q/2 regular unbalanced lines pass through a point, there exists an integer mm such that on more than 2δq+1+52\frac{\delta}{q+1}+5 of these lines the number of red points is congruent to mm mod pp.

Result 5.17 ([16 Theorem 3.6]). Color the points of PG⁡(2,q)\operatorname{PG}(2,q), q>17q > 17, red and blue. Assume

δ<(⌊q⌋+1)(q+1−⌊q⌋).\delta< (\lfloor\sqrt{q}\rfloor+1)(q+1-\lfloor\sqrt{q}\rfloor).

Assume furthermore that Property 5.16 holds. Then there exists a multiset R∗R^{*} such that every line intersects R∗R^{*} in rr mod pp points (counting with multiplicity) and the number of points of PG⁡(2,q)\operatorname{PG}(2,q) which have different multiplicities in RR than in R∗R^{*} is ⌈δq+1⌉\left\lceil\frac{\delta}{q+1}\right\rceil.

The number of unbalanced lines is O(pp)O(p\sqrt{p}) when rr is either small or large

In this subsection, our aim is to prove the following theorem, showing that when rr is small (or large) and the number of unbalanced lines is moderately bounded, the coloring is close to a trivial one.

Theorem 5.18. Color the points of PG⁡(2,p)\operatorname{PG}(2,p), pp prime, red and blue. We say that a line is balanced if it contains exactly rr red points. Suppose that 0≤r<cp0 \le r < c\sqrt{p} and the number of unbalanced lines, δ\delta, is less than dp(p+1)d\sqrt{p}(p+1), where c,d>0c,d > 0 and

δ(c+d)+20c+28dp+19p<1\delta(c+d)+\frac{20c+28d}{\sqrt{p}}+\frac{19}{p}<1

hold. Then we can

change the color of at most ⌈dp⌉\lceil d\sqrt{p}\rceil points so that the coloring we obtain contains rr completely red lines and all other points are blue. Furthermore, the size of the union of the set of recolored points and the intersection points of the rr red lines is at most ⌈dp⌉\lceil d\sqrt{p}\rceil.

Remark 5.19. Note that the assumption c,d>0c,d>0, and 8d(c+d)+20c+28dp+19p<18d(c+d)+\frac{20c+28d}{\sqrt{p}}+\frac{19}{p}<1 immediately implies that 8d2<18d^{2}<1, also p>19p>19; and hence Result 5.17 can be applied once Property 5.16 has been verified. Also note that 8cd<18cd<1. Furthermore, since 20c+28dp<1\frac{20c+28d}{\sqrt{p}}<1, we also see that 20c+20dp<1\frac{20c+20d}{\sqrt{p}}<1 and so 20(c+d)<p20(c+d)<\sqrt{p}.

Remark 5.20. Note that cc and dd do not have to be constants. For example, when c=Cpc=C\sqrt{p} and d=D/pd=D/\sqrt{p} and C,DC,D are constants and pp is large enough, we need that 8CD+20C<18CD+20C<1. In this case Theorem 5.18 says that there are rr almost completely red lines. If these lines are not concurrent, we see immediately at least rr intersection points. If now r>⌈D⌉r>\lceil D\rceil then Theorem 5.18 yields that these rr lines must be concurrent. Hence the coloring is the trivial coloring with changing the colors of at most ⌈D⌉\lceil D\rceil points.

Assumption. In the lemmas below we assume, in addition to the hypotheses of Theorem 5.18, that r>0r>0 and every unbalanced line is regular. The excluded cases will be handled separately in the proof of the theorem.

Lemma 5.21. There exists a set of points, LL, such that each unbalanced line contains at least one point from LL and

∣L∣=⌈δp+1⌉≤⌈dp⌉.|L|=\left\lceil\frac{\delta}{p+1}\right\rceil\leq\lceil d\sqrt{p}\rceil.

Moreover, LL can be chosen so that every P∈LP\in L lies on at least

p+1−(δp+1+2δ2(p+1)3)p+1-\left(\frac{\delta}{p+1}+\frac{2\delta^{2}}{(p+1)^{3}}\right)

unbalanced lines.

Lemma 5.22. For the set of red points RR in PG⁡(2,p)\operatorname{PG}(2,p) we have

∣R∣≤(r+∣L∣)(p+1)≤(r+⌈dp⌉)(p+1).|R|\leq(r+|L|)(p+1)\leq(r+\lceil d\sqrt{p}\rceil)(p+1).

Proof. If every red point belongs to LL, the assertion is immediate. Otherwise, we count the number of red points on the lines through a red point not in LL. By Corollary 5.15, we count at most 1+(r−1)(p+1−∣L∣)+∣L∣p1+(r-1)(p+1-|L|)+|L|p of them.

Lemma 5.23. Through any point of LL there are at least p+14(cp+∣dp∣)\frac{p+1}{4(c\sqrt{p}+|d\sqrt{p}|)} lines that contain the same number of red points.

Proof. Fix P∈LP\in L, and let x1,…,xp+1x_1,\ldots,x_{p+1} be the numbers of red points on the lines through PP, excluding PP itself. Then

∑xi≤∣R∣.\sum x_i\leq|R|.

Let MM be the maximum number of the xix_i having the same value. Since each integer occurs at most MM times, the smallest possible sum is obtained by taking MM zeros, then MM ones, and so on. Hence

∣R∣≥∑xi≥(p+1)(p+1−M)2M,|R|\geq\sum x_i\geq\frac{(p+1)(p+1-M)}{2M},

and therefore, by Lemma 5.22,

M≥(p+1)22∣R∣+p+1≥p+12(r+∣L∣)+1>p+14(cp+⌈dp⌉).M \ge\frac{(p+1)^2}{2|R|+p+1} \ge\frac{p+1}{2(r+|L|)+1} > \frac{p+1}{4(c\sqrt{p}+\lceil d\sqrt{p}\rceil)}.

Lemma 5.24. There exists a multiset of points R∗R^*, such that the set of points whose multiplicity differs in R∗R^* and RR is exactly LL, and every line intersects R∗R^* in rr mod pp points.

Proof. By Remark 5.19, we have d<122d < \frac{1}{2\sqrt{2}}. Hence

δ<p(p+1)2<(⌊p⌋+1)(p+1−⌊p⌋),\delta< \frac{\sqrt{p}(p+1)}{2} < (\lfloor\sqrt{p}\rfloor+1)(p+1-\lfloor\sqrt{p}\rfloor),

so the numerical bound in Result 5.17 is satisfied. By Lemma 5.23, through each point in LL there are at least

p+14(cp+⌈dp⌉)\frac{p+1}{4(c\sqrt{p}+\lceil d\sqrt{p}\rceil)}

lines containing the same number of red points. It remains to verify that Property 5.16 holds. A point outside LL lies on at most ∣L∣<p/2|L|<p/2 unbalanced lines, so it is enough to consider points of LL. For P∈LP\in L, put

A=δp+1+2δ2(p+1)3.A=\frac{\delta}{p+1}+\frac{2\delta^2}{(p+1)^3}.

By Lemma 5.21, at most AA balanced lines pass through PP.

p+14(cp+⌈dp⌉)>p+14(cp+dp+1)>2δp+1+5.\frac{p+1}{4(c\sqrt{p}+\lceil d\sqrt{p}\rceil)}>\frac{p+1}{4(c\sqrt{p}+d\sqrt{p}+1)}>\frac{2\delta}{p+1}+5.

This inequality follows from the assumption of Theorem 5.18. Moreover, 8δ2<18\delta^2<1 gives

A<δp+1+14<p2.A<\frac{\delta}{p+1}+\frac{1}{4}<\frac{p}{2}.

Thus the common number of red points above cannot be rr, and hence Property 5.16 holds.

Hence by Result 5.17 there is a multiset R∗R^* such that it intersects every line in rr mod pp points and the set SS consists of those points that have different multiplicity in RR than in R∗R^*, and SS has size ⌈δp+1⌉\lceil\frac{\delta}{p+1}\rceil. Clearly, every unbalanced line must contain a point of SS. If P∈L∖SP\in L\setminus S, then at most ∣S∣|S| unbalanced lines through PP can meet SS, while Lemma 5.21 gives at least p+1−A>∣S∣p+1-A>|S| such lines. Thus L⊆SL\subseteq S, and since ∣L∣=∣S∣|L|=|S|, we have L=SL=S.

Lemma 5.25. Let PP be a point of LL and let the multiplicity mPm_P of PP in R∗R^* satisfy 0≤mP<p0\le m_P<p. Then mP≤rm_P\le r or p−∣L∣≤mPp-|L|\le m_P.

Proof. Assume to the contrary that there exists a point P∈LP\in L with multiplicity r<mP<p−∣L∣r<m_P<p-|L| in R∗R^*. Through the point PP, there are at least p+2−∣L∣p+2-|L| lines that do not meet any point in L∖{P}L\setminus\{P\}. Each of these lines contains rr mod pp points from R∗R^* and contains exactly one point (namely PP) at which the multiplicities in RR and R∗R^* may differ. Hence it contains exactly p+r−mP>∣L∣+rp+r-m_P>|L|+r red points different from PP. Therefore,

∣R∣≥(p+2−∣L∣)(∣L∣+r+1).|R|\ge(p+2-|L|)(|L|+r+1).

We now show that

(p+2−∣L∣)(∣L∣+r+1)>(r+∣L∣)(p+1),(p+2-|L|)(|L|+r+1)>(r+|L|)(p+1),

which is a contradiction to Lemma 5.22. We rearrange the previous inequality to obtain:

0<p+r+2−∣L∣2−r∣L∣.0<p+r+2-|L|^2-r|L|.

The right-hand side is a quadratic expression in ∣L∣|L|, an upside down parabola. Indeed, since ∣L∣≤⌈dp⌉<dp+1|L|\leq\lceil d\sqrt{p}\rceil<d\sqrt{p}+1 and r<cpr<c\sqrt{p},

∣L∣2+r∣L∣<d(c+d)p+(c+2d)p+1<p,|L|^2+r|L|<d(c+d)p+(c+2d)\sqrt{p}+1<p,

where the last inequality follows from the assumption of Theorem 5.18. This contradiction completes the proof since 0<r0<r and 0≤∣L∣≤⌈dp⌉0\leq|L|\leq\lceil d\sqrt{p}\rceil.

Now we change the multiplicities so that their absolute values are minimized and hence we will allow negative values as well. The multiplicity mPm_P of a point of LL in R∗R^* will be −∣L∣≤mP≤r-|L|\leq m_P\leq r. The next lemma is straightforward.

Lemma 5.26. The total multiplicity of the points in LL in R∗R^* lies in the interval [−∣L∣2,r∣L∣][-|L|^2,r|L|].

Lemma 5.27. Each line intersects R∗R^* in either rr or p+rp+r points.

Proof. Since every line intersects R∗R^* in r(modp)r\pmod{p} points, we have ∣ℓ∩R∗∣=kp+r|\ell\cap R^*|=kp+r for some integer kk. Also, 0≤∣ℓ∩R∣≤p+10\leq|\ell\cap R|\leq p+1 and hence by Lemma 5.26 −∣L∣2≤∣ℓ∩R∗∣≤p+1+r∣L∣-|L|^2\leq|\ell\cap R^*|\leq p+1+r|L|. It follows from Lemma 5.21 and Remark 5.19 that k=0,1k=0,1.

Lemma 5.28. There exists a blue point outside R∗R^* (i.e. has multiplicity 00 in R∗R^*) and no (p+r)(p+r)-secant of R∗R^* passes through it.

Proof. Let ℓ\ell be a balanced line. Then ℓ\ell contains at least p+1−r−∣L∣>p−(c+d)pp+1-r-|L|>p-(c+d)\sqrt{p} blue points which are not in R∗R^*. By Remark 5.19, this number is larger than 19p/2019p/20. Moreover,

∣ℓ∩R∗∣≤r+r∣L∣<p+r,|\ell\cap R^*|\leq r+r|L|<p+r,

where r∣L∣<cp(dp+1)<pr|L|<c\sqrt{p}(d\sqrt{p}+1)<p. Hence ℓ\ell itself is not a (p+r)(p+r)-secant of R∗R^*.

Assume to the contrary that each of them is contained in a (p+r)(p+r)-secant of R∗R^*. These secants are distinct, since a line different from ℓ\ell meets ℓ\ell in only one point.

Since mP≤rm_P\leq r for every P∈LP\in L, a (p+r)(p+r)-secant of R∗R^* contains at least

p+r−r∣L∣=p−r(∣L∣−1)>p−cdp=p(1−cd)p+r-r|L|=p-r(|L|-1)>p-cdp=p(1-cd)

red points. By Remark 5.19, cd<1/8cd<1/8 and hence p(1−cd)>7p/8p(1-cd)>7p/8.

Counting the number of red points on the (p+r)(p+r)-secants through the blue points on ℓ\ell which are not in R∗R^*, put s=⌊7p/8⌋s=\lfloor7p/8\rfloor. We may choose s+1s+1 of these secants, each containing at least s+1s+1 red points. The jj-th secant contributes at least s+2−js+2-j new red points, and hence

∣R∣≥(s+1)(s+2)2.|R|\geq\frac{(s+1)(s+2)}{2}.

By Lemma 5.22, the number of red points is less than

((c+d)p+1)(p+1)<(p/20+1)(p+1).((c+d)\sqrt{p}+1)(p+1)<(p/20+1)(p+1).

This yields a contradiction when p>19p>19 and hence the lemma follows.

Proof of Theorem 5.18. Consider the points colored red; they form the set RR. Put m=⌈dp⌉m = \lceil d\sqrt{p}\rceil. By Remark 5.19, m+1<pm+1<\sqrt{p}, and hence

(m+12)<p+1.\binom{m+1}{2}<p+1.

Since m+1−dp≥1m+1-d\sqrt{p}\geq1, Lemma 5.10, applied with k=m+1k=m+1, shows that if r=0r=0, then ∣R∣≤m|R|\leq m, while if r=1r=1 and ℓ\ell is a completely red line, then ∣R∖ℓ∣≤m|R\setminus\ell|\leq m. Recoloring these points blue proves the theorem in these cases. Since r<cp<pr<c\sqrt{p}<p, we may therefore assume that r>0r>0 and that every unbalanced line is regular.

We construct the multiset R∗R^* using Lemma 5.24.

We will show that R∗R^* is the weighted sum of rr lines. Counting the points of R∗R^* with multiplicity on the p+1p+1 lines through the point provided by Lemma 5.28 and using Lemma 5.27, we obtain ∣R∗∣=(p+1)r|R^*|=(p+1)r. Now counting the points of R∗R^* with multiplicity on the lines through an arbitrary point PP, we get that the multiplicity of PP in R∗R^* must be the number of (p+r)(p+r)-secants through PP; hence R∗R^* is the weighted sum of the not necessarily distinct rr lines e1,e2,…,ere_1,e_2,\ldots,e_r.

Note that the multiplicities of the points in RR and R∗R^* differ only at points of LL. This means that any point whose color was flipped must be in LL. Also, points that lie on at least two of the lines eie_i must be in LL since their multiplicity in R∗R^* is larger than 1. Since ∣L∣<p+1|L|<p+1, we see that the lines eie_i are all different and the intersection point of any two of these is in LL.

Now consider a point of LL which lies on at most one of the lines eie_i. Since R∗R^* is the weighted sum of lines, this means that its multiplicity is either 0 or 1 in R∗R^*. And so its multiplicity in RR is 1 in the first case and 0 in the second; hence it is a point whose color was flipped. Therefore, LL is exactly the union of the recolored points and the intersection points of the lines eie_i. The result follows from Lemma 5.21.

Acknowledgement

Project no. 153080 has been implemented with the support provided by the Ministry of Culture and Innovation of Hungary from the National Research, Development and Innovation Fund, financed under the ADVANCED 25 funding scheme.

The third author was partially supported by the Slovenian Research Agency, research project N1-0429 and by Dynasnet European Research Council Synergy project ERC-2018-SYG 810115.

The research presented in this paper was carried out by the authors several years ago, without the use of any AI tool; essentially all of the mathematical content is their own work. The present version was proofread with the help of ChatGPT. During this proofreading, ChatGPT pointed out that the original statement of Lemma 3.12 fails for q=4q=4; the lemma and its proof were corrected accordingly. The details of the extension to nearby cases in § 4 were also adjusted at this stage.

References

  1. [1]S. Adriaensen, T. Szőnyi, Zs. Weiner, Multisets with few special directions and small weight codewords in Desarguesian planes, Designs, Codes and Cryptography, 94 (2026), Article 35.arxiv.org/abs/2411.19201
  2. [2]G. Araujo-Pardo, Gy. Kiss, A. Montejano, On the balanced upper chromatic number of cyclic projective planes and projective spaces, Discrete Math. 338 (2015), 2562-2571.
  3. [3]N. Alon, Z. Füredi, Legitimate colorings of projective planes, Graphs and Combinatorics 5 (1989), 95-106.DOI
  4. [4]G. Bacsó, Zs. Tuza, Upper chromatic number of finite projective planes, Journal of Combin. Designs 7 (1999), 39-53.
  5. [5]G. Bacsó, T. Héger, T. Szőnyi, The 2-blocking number and the upper chromatic number of PG(2,q), Journal of Combin. Designs 21 (2013), 585-602.DOI
  6. [6]J. Barát, S. Marcugini, F. Pambianco, T. Szőnyi, Note on disjoint blocking sets in Galois planes, Journal of Combin. Designs 14 (2006), 149-158.DOI
  7. [7]Z. L. Blázsik, A. Blokhuis, Š. Miklavič, Z. L. Nagy, T. Szőnyi, On the balanced upper chromatic number of finite projective planes, Discrete Math. 344 (2021), 112266.
  8. [8]A. Blokhuis, A.A. Bruen, The minimal number of lines intersected by a set of q + 2 points, blocking sets, and intersecting circles, Journal of Combin. Theory, Series A, 50 (1989) 308-315.DOI
  9. [9]J. Csima, Z. Füredi, Colouring finite incidence structures, Graphs and Combinatorics 2 (1986), 339-346.DOI
  10. [10]J. W. P. Hirschfeld, Projective Geometries over Finite Fields, 2nd ed., Clarendon Press Oxford, 1998.DOI
  11. [11]G. Kiss, G. Somlai, Special directions on the finite affine plane, Designs, Codes and Cryptography 92 (2024), 2587-2597.arxiv.org/abs/2109.13992
  12. [12]J. Lehel, private communication.
  13. [13]Á. Markó, Nonuniform lines on finite projective planes, The Art of Discrete and Applied Mathematics, available online.
  14. [14]J. Spencer, Coloring the projective plane, Discrete Math. 73 (1988-89), 213-220.DOI
  15. [16]T. Szőnyi, Zs. Weiner, Stability of k mod p multisets and small weight codewords of the code generated by the lines of PG(2,q), J. Combin. Theory Ser. A 157 (2018), 321–333.arxiv.org/abs/1901.09649
  16. [17]M. Tallini Scafati, (k, n)-archi in un piano grafico finito, con particolare riguardo a quelli con due caratteri, I. Rend. Accad. Naz. Lincei, 40:812–818, 1966.
  17. [18]M. Tallini Scafati, (k, n)-archi in un piano grafico finito, con particolare riguardo a quelli con due caratteri, II. Rend. Accad. Naz. Lincei, 40:1020–1025, 1966.
  18. [19]V. Voloshin, Colouring mixed hypergraphs: Theory, algorithms and applications, Amer. Math. Soc., Providence, 2002.DOI

Paper details

vlnc:W_vw8ubk3r
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

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

  • Mathematics

ChatGPT

View statement
Looking for related papers…
Contents