WorksMathematics
Two-coloring the points of a projective plane
Abstract
Let us color the points of a projective plane of odd order 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 , and in the corresponding trivial coloring the unbalanced lines go through a point. In this paper, we consider the Galois plane and determine the number of unbalanced lines for a non-trivial coloring. The problem can also be generalized to -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 describes all 2-colorings with at most not -colored lines (see Theorem 5.13). Finally, in case of the generalized problem, we allow even more not -colored lines if 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 is an easy exercise. It is 3 for the Fano plane and 2 for . 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 the difference of the number of red and blue points on is at most (where is an absolute constant and 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 unbalanced lines in PG. Indeed, as 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 . 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 unbalanced lines. A slight refinement of this simple argument also shows that when there are exactly 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 for the number of unbalanced lines is sharp, and essentially this is the only coloring with unbalanced lines.
We generalize the notion of balanced lines by introducing -colored lines.
Definition 1.1. Color the points of PG with red and blue and fix an integer and let . The line in PG is -colored, if the number of red points on is , while the number of blue points is .
For the remainder of this paper, we refer to -colored lines as balanced lines and all other lines as unbalanced lines. Note that when , 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 .
Definition 1.2. We call the following coloring trivial: take a pencil, color 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 -colored (balanced) lines. Originally, as discussed above, Erdős asked this question for . 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 : when , that is, all points are blue (no unbalanced lines), and when , 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 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 -colored lines is close to its maximum.
Note that the case 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 red points. Therefore, if we consider the set of red points , then only the unbalanced lines can be not -secants of it (though not necessarily). Hence, if there are unbalanced lines, then the number of not -secants of is at most . This allows us to apply the results of [16] for sets having few not -secants.
In the present paper we shall work in the Desarguesian plane PG, , prime, so for the order of the plane we will use and not as above. The corresponding affine plane AG will occasionally be identified with (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 , and to analyze special cases when 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 in PG, . Here we settle the problem under the additional assumption that there is a line for which the number of red points is not (mod ) (Assumption 3.10). This condition is needed when the unbalanced lines (i.e. not -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 unbalanced lines and (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 lines (Theorem 3.7).
§ 4 deals with the case of the original problem of Erdős (). Using a counting argument (without Assumption 3.10), we prove that for a non-trivial coloring the number of unbalanced lines is at least when (Theorem 4.5). The argument also works for the nearby cases : if and the unbalanced lines do not form a dual blocking set, then there are at least unbalanced lines (Corollary 4.4).
The next examples show that Assumption 3.10 cannot be omitted: there exist colorings with fewer than unbalanced lines which do not form a dual blocking set, and for which every line contains the same number of red points modulo . Also one might think that in the Erdős case, the only possible example with 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 , this is not the case.
Example 2.1. Let be even, and consider a set of lines in PG such that no three of them are concurrent (a so-called dual hyperoval). Color all points on these lines blue and all other points red. Or color one of these lines blue, the remaining points on the other lines red, and all other points blue.
Since each point lies on either 0 or 2 of these lines, every line not belonging to the dual hyperoval contains exactly red points. Thus these colorings have exactly 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 unbalanced lines.
Example 2.3. Let be a square, and let be a Baer subplane of PG. Choose a point , and let lines through be tangent to (i.e. meeting in only), where . Color all points of red, and also color red all points on these tangent lines except . The color of can be either red or blue. All remaining points are colored blue.
A line tangent to and not passing through contains exactly red points. Any other line not passing through contains red points, while the lines through contain either 0, 1, , , , red points.
Let and . Then:
if and is blue, then the coloring has exactly unbalanced lines;
if and is red, then the coloring has exactly unbalanced lines;
if , then the coloring has exactly unbalanced lines.
§ 5 is devoted to the case prime. The non- secants are typically just the unbalanced lines (except for ), so it is not surprising that we have stronger results for . First of all, there is an example due to Kiss and Somlai, who constructed a subset of size which intersects each line with slope not in precisely 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 unbalanced lines. In the prime case, , we can describe colorings with at most unbalanced lines completely, see Theorem 5.13 in Subsection 5.2. Finally, in Subsection 5.3, we consider the general problem when is small in , prime. In this case the red points are the union of 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 unbalanced lines in
In this section, we color the points of red and blue, and we denote the set of red points by , the set of blue points by , and the set of unbalanced lines by . Throughout this section, we will assume that , 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 and covers all points of , 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 is a power of a prime, then any point set in a projective plane of order intersecting each line in either or points, where and , 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 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 . 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 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 . Then, a line and a point disjoint from it are colored blue, and the rest of the points are red.
Proof. If 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 red points. Suppose that is an unbalanced line with red points. Since the unbalanced lines form a dual blocking set and have size less than , 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 , apart from itself, we observe at least one more unbalanced line with red points.
The fact that yields that if through a red point on there is another unbalanced line with red points, then there must be a third unbalanced line through that point. If there are no blue points on , then we already count at least unbalanced lines, which contradicts the assumption.
If every blue point on has at least three unbalanced lines passing through it, then again , a contradiction. Thus, there is a blue point on with only two unbalanced lines. Namely, and the other compulsory unbalanced line containing red points. Counting the total number of red points on the lines through , we obtain . However, we also know that there are red points in total. This implies that and or and . In the latter case, there can be at most one blue point (otherwise there was at least lines containing blue points, i.e. unbalanced), which is impossible since contains blue points. In the former case, all points not on or are red. Now, if we take another point on , then, as mentioned above, there is an unbalanced line through with red points. Since all points outside of and are red, this means that . However, a balanced line has exactly red points, so we must have , 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 and be two points of different colors. Assume that there is a unique unbalanced line through each of these points, then the line is balanced. Let and be the unique unbalanced lines through and respectively and . Then the points of are colored the same as , and similarly, the points of are colored the same as .
Proof. Assume that is colored red. If is unbalanced, counting the number of red points not on along the lines through would give while through would give which is a contradiction. Let the number of red points on be , and on be . By counting the number of red points on the lines through , we get . Similarly, by counting the red points on the lines through , we get . It follows that 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 . Then, there exists a point such that the points, excluding , on exactly lines through are colored red, and the points, excluding , on the remaining lines through are colored blue. The point itself can be either red or blue.
Proof. The assumption of the proposition and Lemma 3.5 imply that there exists a point colored red, a point colored blue, and a point such that the points of are red, and the points of are all blue. Without loss of generality, we may assume that is colored blue. Hence, the line is completely blue. Lemma 3.5 now shows that a unique unbalanced line through a blue point is completely blue and passes through . Assume that there are such completely blue lines through . Note that since all lines but through are balanced, .
First, assume that . Color every point on the line red. If was , then since through every line but was balanced, now the entire plane will be red and hence the proposition follows. If then in this new coloring, let us call lines with red points be balanced. The number of red points on every line but was increased by one, and so in this new coloring balanced lines are exactly those that were balanced earlier ( remains unbalanced since ). 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 ( and ). A contradiction follows from Lemma 3.3 and from Lemma 3.4 and hence if then .
Now suppose that . Note that this means that if a unique unbalanced line passes through a red point , then it must be the line and the points of this line are all red except . We show that each line through is unbalanced. On the contrary, suppose that there is a balanced line through . From above this means that there is no point on through which a unique unbalanced line passes, otherwise would be unbalanced. (Note that through there pass at least three unbalanced lines.) Since unbalanced lines cover all points, counting them through the points of we see at least unbalanced lines; a contradiction. Hence all lines through are unbalanced. Let be a line through . Now if through each point of , another unbalanced line passes different from , then again in total we count at least unbalanced lines. This means that each line through contains a point such that is the unique unbalanced line through and hence the proposition follows.
We summarize the results above in the following theorem.
Theorem 3.7. Color the points of the plane either red or blue. A line is balanced if it contains red and 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) concurrent lines,
(4) 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 , lead to cases (1), (2), and (5).
Unbalanced lines do not form a dual blocking set
Preliminaries for general
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 .
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 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 , we see that must be red. Let be the unique unbalanced line through with red points. Counting the red points on the lines through , we find that the total number of red points is , which is (by Assumption 3.8). Hence, we have , i.e., either and , or and . In the first case, looking around from , we see that all points outside must be blue. The second case is not possible, as it implies that balanced lines are completely blue, but 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 with the elements in and so three distinct points , , are collinear if and only if holds. This way the ideal points (directions) correspond to -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 (mod ).
The example coming from a dual hyperoval, mentioned in the Introduction, shows that the existence of lines with not mod secants is relevant. The second author showed in [13] that such examples only occur for even if the number of unbalanced lines is at most . 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 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 .
Identify the points of with the elements in , and hence the affine red points form a subset of . Let be the red points on the line at infinity, which can be viewed as the -th roots of unity. Write the following polynomial for the red points:
The polynomial is not identically zero, since its leading coefficient is non-zero (it corresponds to the number of affine red points). When is a blue point not covered by an unbalanced line (Assumption 3.8), is a root of . This is because all the lines through contain red points (including the point at infinity), so is times the sum of all -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 lines are disjoint from it. Such sets can be characterized if we impose a suitable bound on their size.
Lemma 3.12. Assume that is a set of size at most in , with no tangents and at most lines disjoint from . Then, is the symmetric difference of two lines, unless , , and is the complement of the union of three non-concurrent lines.
Proof. Pick any point not in . Since , there is a line through that is disjoint from . In other words, the points outside are covered by lines disjoint from . There are at most lines disjoint from , and they can cover at most points (equality holds only if there are passant lines and these lines are concurrent). Thus, must contain at least points, and for , the set is the symmetric difference of the two remaining lines passing through the common points of the passants.
Now assume that . Then its complement has points and is covered by at most passants. If , the complement has 2 points, whereas a passant has 3, which is impossible. If , 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 . Since lines cover at most points, there must be passants. Let be the maximum number of these passants through a point. They cannot all be concurrent, so ; the lines through this point cover points, and each remaining line adds at most new points. Hence their union has size at most
a contradiction. Thus is the only remaining case. Here three passants are necessary and they must be non-concurrent; their union is precisely the complement of .
Theorem 3.13. Color the points of the plane either red or blue. A line is balanced if it contains red and blue points, where . Assume that there are at most unbalanced lines, and they do not cover all the points of . Furthermore, suppose that there exists an unbalanced line with not red points on it. Assume moreover that . Then, the red points form one of the following structures: either a line with 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 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 and they are precisely the nine lines avoiding three non-collinear points , , .
We first exclude the latter case. Let be an unbalanced line whose number of red points is not congruent to modulo 2. Choose coordinates such that
Let satisfy . The six lines
form a dual hyperoval. Apart from , each passes through one of , , 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, contributes incidences and each of the other five lines contributes , since it is balanced. Hence,
Hence , a contradiction.
Thus there are two points, and , such that every unbalanced line passes through one of them. Moreover, the line joining them, , is balanced.
Assume there is a line through , different from , that contains both a red point and a blue point (different from ). Let us denote these points as and , respectively. Counting the red points through and immediately shows that the line must be completely red (except possibly at ), and similarly, the line must be entirely blue. Therefore, the points on the lines through , except for itself, must be monochromatic. If there is no such line through , we immediately can conclude the same for the lines through .
Thus, for one of , say , the lines through different from are monochromatic apart from . Let of them be red. Every line through neither nor is balanced and contains red points from these lines; hence all points of have the same color. They cannot be red, since for , so they are blue and . Since is balanced and , it follows that or , according to how many of 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 , and extend the argument to
where and 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, ).
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 . This means that
If and , Theorem 3.13, applied with the colors interchanged if necessary, implies that a coloring with at most unbalanced lines must have red points on every line. Indeed, , and the two exceptional structures have . If , our bounds on imply that every line with red points is balanced. Thus every line would be balanced, a contradiction. Hence .
Lemma 4.1. Let and assume that the unbalanced lines, , do not form a dual blocking set. Let be the set of red points and the set of blue points. Then
Proof. Let denote the number of red points on the line . The standard equations give
Since balanced lines contribute zero, we obtain
where we used and . Finally, .
We will call a line a blue (or red) majority line if it contains more than blue (or red) points.
Lemma 4.2. Let and . Assume that the unbalanced lines do not form a dual blocking set and that every line contains 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 , we count every other blue point once and itself times. Subtracting for each of the lines gives
Write , where . By the congruence assumption, every line contains at least red points, and hence at most blue points. Thus each positive summand is at most . Two positive summands cannot give a total of , and hence at least three blue majority lines pass through .
Proposition 4.3. Let and . Assume that the unbalanced lines do not form a dual blocking set and that every line contains red points. Then the number of unbalanced lines is at least .
Proof. Suppose, for a contradiction, that there are at most unbalanced lines. As noted at the beginning of the section, . By the preceding lemma, at least three blue majority lines pass through every blue point.
Put , where . Let be the line containing the maximum number of blue points, and suppose that has red points and blue points. The congruence assumption gives
Since is a blue majority line, is a positive multiple of , so .
We now show that every line contains at most red points. Counting through a red point gives
so a red point lies either on zero or on at least two unbalanced lines. Let be a red majority line. If a red point on lies on exactly two unbalanced lines, say and , then the deviations from on these two lines sum to zero. Since by the choice of , we obtain
If there is no such red point on , then through each red point on there must pass at least two unbalanced lines other than . Moreover, through every blue point on there are at least three blue majority lines, all different from . Thus every point of is on at least two unbalanced lines other than ; so we would see at least unbalanced lines, a contradiction. In particular, every term in is at most .
We now provide an upper bound on the sum from Lemma 4.1. To do so, we first show that the number of blue points on with exactly three unbalanced lines is at least . Assume, for a contradiction, that there are at least blue points on with more than three unbalanced lines. Each of the red points on lies on at least one further unbalanced line, of the blue points lie on at least three further unbalanced lines each, and the remaining blue points lie on at least two each. These lines are distinct, so, including , we obtain at least
which is again a contradiction.
Let be a blue point on with exactly three unbalanced lines: , , and . All three are blue majority lines. Since
and each summand is at most , their sum of squares is maximized when one equals and the other equals . Hence,
Choose such points ; they give disjoint pairs of terms in . The remaining terms can be estimated from above by . Thus, using the fact that there are at most unbalanced lines, we obtain
Put and . The congruence assumption gives . The three blue majority lines through also give , so . Using and multiplying the preceding inequality by four, we obtain , where
We show that . First,
since and so each term is negative. This settles the case , since then .
Now let . Since , we have
As , it follows that
Moreover,
since and . Therefore,
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 , where is odd, and let , , .
If the unbalanced lines do not form a dual blocking set, then there are at least unbalanced lines.
Applying the preceding corollary with 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 and . Then the number of unbalanced lines is at least 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 that is the points colored red. We have already noted that the case when is prime is special in the sense that, in this case most of the time, the set of non--secants of coincides with the set of unbalanced lines. Under the assumption , there are two exceptions, namely when a line with red points is unbalanced but contains red points, similarly when a line with red points is unbalanced but contains red points.
First, we will consider the case when the number of unbalanced lines () is relatively small (at most ). Subsequently, we will allow to be at most , while ensuring that the number of red points (or the number of blue points ) on a balanced line, remains small, at most . For more on the constants see Theorem 5.18
We will consider multisets of , , prime, these sets are related to codewords generated by lines of the dual plane of . Such codes are naturally considered over the prime field of and so the multiplicities of the points in a multiset will also be considered over . We mostly consider the multiplicities as integers between 0 and , 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 . A point set is said to admit a non-special direction () if every line with slope contains exactly points, for some fixed integer . A direction is special otherwise. They characterized point sets admitting at most three special directions.
Color the points of red and all other points in blue, and call a line balanced if it contains exactly 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 , we can interpret the elements of as the integers from 0 to . This naturally defines an ordering on the elements of . Kiss and Somlai proved the following results.
Example 5.1 (Kiss, Somlai). [11] Let be a prime. Then the set
has exactly three special directions, namely , and .
Result 5.2 (Kiss, Somlai). [11] Let be a point set in . Let be a non-special direction and assume that on each line with slope , we see points. If admits at most three special directions, then is either a union of parallel lines or, up to an affine transformation, it is equivalent to 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 , where , into red and blue. A line is called balanced if it contains exactly , where , red points. Suppose that there are at most unbalanced lines and assume that there is a line so that all unbalanced lines different from intersect in at most three different points, , . Then one of the following holds:
The red point set is the union of concurrent lines through one of the points , with their common point removed, together with a subset of ; and the blue point set has the analogous form with replaced by .
One of the two color classes is, up to an affine transformation, equivalent to or its complement in Example 5.1, together with a subset of the directions .
Proof. Let and be two points on a line through which all lines except are balanced. By counting the number of red points on the lines through and then through , we deduce that and must have the same color, say blue. Now, let be the line at infinity and consider the set of red points outside . If there were none, then 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 and a codeword of the code . The results will then follow from earlier results on small weight codewords.
Definition 5.4. Let denote the set of points of , is prime. We define the characteristic vector of a line in as the vector
where
The code is defined as the -span of the characteristic vectors of the lines of . Let be a codeword in . Then, the weight of the codeword, denoted by , is the number of non-zero coordinates in . The support, , of is the set of points corresponding to the non-zero coordinates of .
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 is a prime and that with . Then is either a linear combination of at most three lines or can be covered by three concurrent lines.
Notation 5.6. Coordinates of a point in will be denoted by while the coordinates of a line with .
Next we will establish the connection between the coloring of the points of and codewords.
Definition 5.7. Color the points of red and blue and consider the set of red points . Define
Note that the coordinate of corresponding to the point is the number of points of on the line modulo .
Lemma 5.8. Let be the all vector. The coordinate of the codeword corresponding to the point is non-zero if and only if the line intersects the point set in not mod points.
In our case, will be small and hence we will be able to apply Result 5.5.
Colorings with at most unbalanced lines
In this subsection, we will assume that prime. We color the points of red and blue. We call a line balanced if it contains exactly red points, where . Throughout this subsection, we will assume that the number of unbalanced lines is at most . As mentioned before, unbalanced lines which contain not mod red points will be handled by earlier results.
Definition 5.9. We call an unbalanced line containing not mod red points a regular unbalanced line.
Under the assumption , a non-regular unbalanced line can occur only when or : in the former case it is a -secant of , while in the latter case it is a completely red line. We first examine these two exceptional cases.
Lemma 5.10. Let be the set of red points and let denote the number of unbalanced lines. Then the following hold:
If , for every integer with , we have
Moreover, if there is a non-regular unbalanced line, then .
(2) If and is a completely red line, then for every integer with , we have
(3) If , then every unbalanced line is regular.
Proof. For any distinct points, the union of the pencils through them contains at least
lines: when the -th pencil is added, at most of its lines have occurred before. If , every line through a red point is unbalanced, which gives the first inequality in (1). A non-regular unbalanced line then contains exactly red points. The red points on such a line determine distinct lines different from it, all unbalanced, giving at least unbalanced lines.
If and is completely red, every line through a red point outside contains at least two red points and hence is unbalanced. The line itself is not among these pencils, which proves (2). Finally, (3) is immediate. □
Lemma 5.11. Color the points of , where is prime, red and blue, and call a line balanced if it contains exactly red points. Assume that the number of unbalanced lines is at most . 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, , , and , in order to block all regular unbalanced lines. Then there exist non-zero multiplicities so that the union of the points with multiplicity and the set of red-colored points forms a multiset in which every line contains exactly points (counted with multiplicities).
Proof. For the set of red points , construct the codeword (see Definition 5.7), and define
where is the all-ones vector. By Lemma 5.8 and by the assumption of the lemma, we have
Thus, by Result 5.5, the support of can be covered by at most three lines, which immediately implies (1).
Now, assume that exactly three lines are required to cover and that these lines are not concurrent. By Result 5.5, there exist non-zero multiplicities such that
Rearranging, we obtain
and hence (2) follows. □
Proposition 5.12. Suppose that and assume that there exist three non-collinear points , , , so that each regular unbalanced line contains at least one of them. Suppose that there are at most unbalanced lines. Suppose moreover that there exists a multiset which agrees with outside and in which every line contains exactly points (counted with multiplicities). Then is the union of lines, each passing through one of the points , with removed; or and consists of a completely red line together with a subset of outside this line.
Proof. Let . Let denote the multiplicity of in . First we get rid of the exceptional cases.
If , then by Lemma 5.10(1), there is no non-regular unbalanced line. If there were a red point , all lines through would be regular unbalanced, but at most three of them could contain one of the points , a contradiction. Thus , giving the first conclusion.
If and there is a completely red line , Lemma 5.10 shows that there are at most three red points outside . In particular, is the unique completely red line. If a red point outside were not one of the , then all lines through would be regular unbalanced and would have to contain one of the three points , again a contradiction. Hence the second conclusion holds.
We may therefore assume that and that every unbalanced line is regular.
First, we will show that through one of the points , , say through , there passes a line such that either all points of are in or none. Let be a point not in and not on the lines , for . Such a point exists, since otherwise a line avoiding would contain at least red points and hence would be a regular unbalanced line avoiding all three points. Also, let be a point of not on the lines . If no such point exists, then the lines through the points show that each side of the triangle without the vertices is either contained in or disjoint from . Thus is the union of sides without vertices. A line avoiding is balanced, so , and the first conclusion follows. Now, consider counting the points of once on the lines through and also on the lines through . Note that a line not passing through any is balanced and hence contains exactly points of and hence of too, and so we have
From this, we obtain:
The multiset intersects each line in points, and hence:
Since is a set, equation (2) can only be true if for some ,
which can only happen if one of or is and the other is . Hence, we have found the required line through the point .
:::
Without loss of generality, we may assume that through there passes a line , such that . Since intersects every line in mod points, and all these lines have the same contribution at in , this implies that any line through and not passing through or must contain either 0 or points from .
Assume that there are lines through containing points from . To complete the proof, we only need to show that on the line (and similarly on ), there are either 0 or points of .
Consider the lines through which do not pass through or . From above, such a line intersects in either or points, depending on whether the intersection with the line is in or not. However, since contains points modulo on each line, it follows that these lines intersect the set in the same number of points, namely in modulo points.
Therefore, all points of belong to simultaneously, or none of them do. By interchanging the roles of and , the same holds for . Thus is the union of lines through , with removed. Any line avoiding is balanced and meets in exactly points, so , 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 , where , with red and blue. A line is called balanced if it contains exactly red points. Suppose that there are at most unbalanced lines.
Then one of the following holds:
There is a point such that, apart from , the points on lines through are red and the points on the remaining lines are blue. The point can have either color.
A coloring obtained from (1) by switching the colors of at most two points different from .
, and the red points consist of a line together with at most three points outside it.
Either and the red point set is, up to an affine transformation, equivalent to from Example 5.1 together with a subset of the directions ; or and one of the two color classes is equivalent to the complement of in , together with a subset of these three directions.
, 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 . First suppose that . If , Lemma 5.10 gives
a contradiction. Hence , which is contained in cases (1) and (2).
Next suppose that and there is a completely red line . If there were at least four red points outside , Lemma 5.10 would give
Thus this gives case (3). We may therefore assume that 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 . Choose minimal with this property. If there is a line containing all points of , then Proposition 5.3 completes the proof. Its first case gives (1) or (2), while its second case, using , gives (4). Otherwise, 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 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 mod sets of [16], translated into the coloring terminology used above. The results below are for general . Throughout these preliminary results, 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 , red and blue, and assume that the number of regular unbalanced lines, , is smaller than . Then there exists a point set , of size , such that every regular unbalanced line contains at least one point of . Moreover, by [16 Remark 3.3], can be chosen so that each lies on at least
regular unbalanced lines.
From this result, we get the following:
Corollary 5.15. Let be a point of , . If , then at most regular unbalanced lines pass through . In particular, if every unbalanced line is regular, then the number of balanced lines through is at least .
Property 5.16 ([16 Property 3.5]). Color the points of red and blue. We say that the property holds if whenever more than regular unbalanced lines pass through a point, there exists an integer such that on more than of these lines the number of red points is congruent to mod .
Result 5.17 ([16 Theorem 3.6]). Color the points of , , red and blue. Assume
Assume furthermore that Property 5.16 holds. Then there exists a multiset such that every line intersects in mod points (counting with multiplicity) and the number of points of which have different multiplicities in than in is .
The number of unbalanced lines is when is either small or large
In this subsection, our aim is to prove the following theorem, showing that when 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 , prime, red and blue. We say that a line is balanced if it contains exactly red points. Suppose that and the number of unbalanced lines, , is less than , where and
hold. Then we can
change the color of at most points so that the coloring we obtain contains 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 red lines is at most .
Remark 5.19. Note that the assumption , and immediately implies that , also ; and hence Result 5.17 can be applied once Property 5.16 has been verified. Also note that . Furthermore, since , we also see that and so .
Remark 5.20. Note that and do not have to be constants. For example, when and and are constants and is large enough, we need that . In this case Theorem 5.18 says that there are almost completely red lines. If these lines are not concurrent, we see immediately at least intersection points. If now then Theorem 5.18 yields that these lines must be concurrent. Hence the coloring is the trivial coloring with changing the colors of at most points.
Assumption. In the lemmas below we assume, in addition to the hypotheses of Theorem 5.18, that 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, , such that each unbalanced line contains at least one point from and
Moreover, can be chosen so that every lies on at least
unbalanced lines.
Lemma 5.22. For the set of red points in we have
Proof. If every red point belongs to , the assertion is immediate. Otherwise, we count the number of red points on the lines through a red point not in . By Corollary 5.15, we count at most of them.
Lemma 5.23. Through any point of there are at least lines that contain the same number of red points.
Proof. Fix , and let be the numbers of red points on the lines through , excluding itself. Then
Let be the maximum number of the having the same value. Since each integer occurs at most times, the smallest possible sum is obtained by taking zeros, then ones, and so on. Hence
and therefore, by Lemma 5.22,
Lemma 5.24. There exists a multiset of points , such that the set of points whose multiplicity differs in and is exactly , and every line intersects in mod points.
Proof. By Remark 5.19, we have . Hence
so the numerical bound in Result 5.17 is satisfied. By Lemma 5.23, through each point in there are at least
lines containing the same number of red points. It remains to verify that Property 5.16 holds. A point outside lies on at most unbalanced lines, so it is enough to consider points of . For , put
By Lemma 5.21, at most balanced lines pass through .
This inequality follows from the assumption of Theorem 5.18. Moreover, gives
Thus the common number of red points above cannot be , and hence Property 5.16 holds.
Hence by Result 5.17 there is a multiset such that it intersects every line in mod points and the set consists of those points that have different multiplicity in than in , and has size . Clearly, every unbalanced line must contain a point of . If , then at most unbalanced lines through can meet , while Lemma 5.21 gives at least such lines. Thus , and since , we have .
Lemma 5.25. Let be a point of and let the multiplicity of in satisfy . Then or .
Proof. Assume to the contrary that there exists a point with multiplicity in . Through the point , there are at least lines that do not meet any point in . Each of these lines contains mod points from and contains exactly one point (namely ) at which the multiplicities in and may differ. Hence it contains exactly red points different from . Therefore,
We now show that
which is a contradiction to Lemma 5.22. We rearrange the previous inequality to obtain:
The right-hand side is a quadratic expression in , an upside down parabola. Indeed, since and ,
where the last inequality follows from the assumption of Theorem 5.18. This contradiction completes the proof since and .
Now we change the multiplicities so that their absolute values are minimized and hence we will allow negative values as well. The multiplicity of a point of in will be . The next lemma is straightforward.
Lemma 5.26. The total multiplicity of the points in in lies in the interval .
Lemma 5.27. Each line intersects in either or points.
Proof. Since every line intersects in points, we have for some integer . Also, and hence by Lemma 5.26 . It follows from Lemma 5.21 and Remark 5.19 that .
Lemma 5.28. There exists a blue point outside (i.e. has multiplicity in ) and no -secant of passes through it.
Proof. Let be a balanced line. Then contains at least blue points which are not in . By Remark 5.19, this number is larger than . Moreover,
where . Hence itself is not a -secant of .
Assume to the contrary that each of them is contained in a -secant of . These secants are distinct, since a line different from meets in only one point.
Since for every , a -secant of contains at least
red points. By Remark 5.19, and hence .
Counting the number of red points on the -secants through the blue points on which are not in , put . We may choose of these secants, each containing at least red points. The -th secant contributes at least new red points, and hence
By Lemma 5.22, the number of red points is less than
This yields a contradiction when and hence the lemma follows.
Proof of Theorem 5.18. Consider the points colored red; they form the set . Put . By Remark 5.19, , and hence
Since , Lemma 5.10, applied with , shows that if , then , while if and is a completely red line, then . Recoloring these points blue proves the theorem in these cases. Since , we may therefore assume that and that every unbalanced line is regular.
We construct the multiset using Lemma 5.24.
We will show that is the weighted sum of lines. Counting the points of with multiplicity on the lines through the point provided by Lemma 5.28 and using Lemma 5.27, we obtain . Now counting the points of with multiplicity on the lines through an arbitrary point , we get that the multiplicity of in must be the number of -secants through ; hence is the weighted sum of the not necessarily distinct lines .
Note that the multiplicities of the points in and differ only at points of . This means that any point whose color was flipped must be in . Also, points that lie on at least two of the lines must be in since their multiplicity in is larger than 1. Since , we see that the lines are all different and the intersection point of any two of these is in .
Now consider a point of which lies on at most one of the lines . Since is the weighted sum of lines, this means that its multiplicity is either 0 or 1 in . And so its multiplicity in is 1 in the first case and 0 in the second; hence it is a point whose color was flipped. Therefore, is exactly the union of the recolored points and the intersection points of the lines . 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 ; 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]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]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]N. Alon, Z. Füredi, Legitimate colorings of projective planes, Graphs and Combinatorics 5 (1989), 95-106.DOI
- [4]G. Bacsó, Zs. Tuza, Upper chromatic number of finite projective planes, Journal of Combin. Designs 7 (1999), 39-53.
- [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]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]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]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]J. Csima, Z. Füredi, Colouring finite incidence structures, Graphs and Combinatorics 2 (1986), 339-346.DOI
- [10]J. W. P. Hirschfeld, Projective Geometries over Finite Fields, 2nd ed., Clarendon Press Oxford, 1998.DOI
- [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]J. Lehel, private communication.
- [13]Á. Markó, Nonuniform lines on finite projective planes, The Art of Discrete and Applied Mathematics, available online.
- [14]J. Spencer, Coloring the projective plane, Discrete Math. 73 (1988-89), 213-220.DOI
- [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
- [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.
- [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.
- [19]V. Voloshin, Colouring mixed hypergraphs: Theory, algorithms and applications, Amer. Math. Soc., Providence, 2002.DOI