On the incompleteness of (k, n)-arcs in Desarguesian planes of order q where n divides q

Simeon Ball Aart Blokhuis Technische Universiteit Eindhoven, Postbox 513, 5600 MB Eindhoven, The Netherlands

simeon@win.tue.nl aartb@win.tue.nl

Abstract

We investigate the completeness of an (nq − q + n − ε, n)-arc in the Desarguesian plane of order q where n divides q. It is shown that such arcs are incomplete for 0 < ε ≤ n/2 if q/n > 3. For q = 2n they are incomplete for 0 < ε < .381n and for q = 3n they are incomplete for 0 < ε < .476n. For q odd it is known that such arcs do not exist for ε = 0 and hence we improve the upper bound on the maximum size of such a (k, n)-arc.

Mathematics Subject Classification numbers 05B25 51E15 51E21

Key words Maximal arcs, arcs, finite Desarguesian planes.

1. Introduction

A (k, n)−arc in a projective plane is a set of k points, at most n on every line. A (k, n)-arc is called complete if it cannot be extended to a (k + 1, n)-arc. If the order of the plane is q, then k ≤ 1 + (q + 1)(n − 1) = qn − q + n with equality if and only if every line intersects the arc in 0 or n points. Arcs realizing the upper bound are called maximal arcs. Equality in the bound implies that n | q or n = q + 1. If 1 < n < q, then the maximal arc is called nontrivial. The only known examples of non-trivial maximal arcs in Desarguesian projective planes, are the hyperovals (n = 2), and, for n > 2 the Denniston arcs [4] and an infinite family constructed by Thas [8, 10]. The Denniston arcs exist for all pairs (n, q) = (2^{a}, 2^{b}), 0 < a < b.

Maximal arcs do not exist in Desarguesian planes of odd order, The case (n, q) = (3, 9) was proved by Cossu [3] and Thas [9] proved the cases (n, q) = (3, 3^{h}). A general proof first appeared in [1] although a more accessible version of the proof appears in [2] and [5]. The techniques used in [1, 2] depend strongly on the properties of certain polynomials over finite fields. We shall again be using such techniques.

BALL & BLOKHUIS : INCOMPLETENESS OF ARCS

In this paper we show that a (nq − q + n − ε, n)-arc in P G(2, q), n < q/3 is incomplete for 0 < ε ≤ n/2 and any such arc can therefore be completed to a maximal arc. For q odd this implies immediately that the maximal size of a (k, n)-arc, denoted m_{n}(2, q) in other literature (see [6]), for n|q is less than nq − q + n/2.

At this point we compare our result to the work of Szőnyi [7]. Although his work is still in progress it is interesting to note the different bounds achieved using different techniques. His algebraic geometric approach gives a bound on epsilon of cq^{1/4}. In other words, a (nq − q + n − ε, n)-arc is incomplete for ε < cq^{1/4}. It follows that for n/2 < cq^{1/4} his bound is better, since we would like ε as large as possible. However, reversing the inequality clearly implies the opposite.

2. Some counting and some conclusions

Let B be a (nq − q + n − ε, n)-arc in P G(2, q) where n/2 > ε > 0. Counting the number of points of B on the lines passing through a point of B we immediately get that a line with at least one point of B in fact has at least n − ε points. Using this, the standard counting arguments involving incident (point, line) pairs and (point, point, line) triples gives that there will be lines missing B (if l_{i} denotes the number of lines containing precisely i points, then we can compute ∑ l_{i}, ∑ il_{i} and ∑ i(i − 1)l_{i} and it turns out that ∑(i − n)(i − (n − ε))l_{i} > 0, hence l_{0} > 0), so we can, and will, consider our point set B in the affine plane AG(2, q).

Define a good point to be a point not in B which lies on exactly q/n external lines. Let G be the set of good points. Let H be the set of points not in B which are not good, we shall call such points bad. Our aim is to show that bad points are on no external lines. First however we wish to get some kind of lower bound on the number of good points. Using this we then apply some polynomial techniques, which imply the incompleteness property.

Define s_{i} to be the number of lines containing n − i points of B, and let s_{i}(P) be the number of lines through the point P containing n − i points of B. Let S be the set of lines containing some points of B but less than n points of B. For every point P ∈ B

∑_{i=1}^{ε} is_{i}(P) = ε

and summing this over all points P ∈ B gives

∑_{i=1}^{ε} i(n − i)s_{i} = ε(nq − q + n − ε) ≥ (n − ε) ∑_{i=1}^{ε} is_{i}.

For all bad points P ∈ H

∑_{i=1}^{ε} is_{i}(P) ≥ n + ε

with equality if and only if P is on exactly q/n − 1 external lines. In fact if a point P is on (exactly) q/n − l external lines then

∑_{i=1}^{ε} is_{i}(P) = ln + ε.

It is clear that

∑_{P ∈H} ∑_{i=1}^{ε} is_{i}(P) ≥ |H|(n + ε)

and we can manipulate the sum on the left as follows:

∑_{P ∈H} ∑_{i=1}^{ε} is_{i}(P) = ∑_{l∈S}(n − |l ∩ B|)(|l ∩ H|)

≤ ∑_{l∈S}(n − |l ∩ B|)(q − n + ε) = (∑_{i=1}^{ε} is_{i})(q − n + ε).

Combining various inequalities we get

|H| ≤ (q − n + ε)(nq − q + n − ε)ε/(n − ε)(n + ε).

Now |G| + |H| + |B| = q^{2} and so

|G| + |B| ≥ q^{2} − (q − n + ε)(nq − q + n − ε)ε/(n − ε)(n + ε).

In the initial stage we will require the number of good points together with the number of points in the arc to be more than (n + ε)(q − 1). This will occur when

q^{2} − (q − n + ε)(nq − q + n − ε)ε/(n − ε)(n + ε) > (n + ε)(q − 1),

and ignoring some positive terms on the right-hand side and some negative terms on the left-hand side when

q^{2} − (q − n + ε)nqε/(n − ε)(n + ε) > (n + ε)q.

Writing ε = cn and m = q/n this will hold for 0 ≤ c ≤ c_{m}, where c_{m} is the unique zero in the interval (0, 1) of the cubic c^{3}/m − c^{2} − c − 1/m + 1. For m = 2 we get c_{m} > .381, for m = 3 we get c_{m} > .476 and for m ≥ 4 we have c_{m} > 1/2.

3. A technical lemma

At several points in the rest of the paper we will make use of the following lemma; it will be referred to simply as the lemma. Here q, n and ε are as before.

Lemma 3.1 Let R ∈ F_{q^{2}}[t, x], be of the form

R(t, x) = ∑_{j=0}^{q+ε} ρ_{j}(x)t^{j}

with ρ_{0} = 1, and ρ_{j} a polynomial of degree at most j(q − 1). Suppose R(t, x_{0}) is fully reducible in F_{q^{2}}[t] for all x_{0} ∈ F_{q^{2}}. Let S ∈ F_{q^{2}} be the set of points x_{0} for which we have a factorization

R(t, x_{0}) = ∑_{i=0}^{q/n} ρ_{in}(x_{0})t^{in} ∑_{j=0}^{ε} ρ_{j}(x_{0})t^{j},

Suppose for some x_{1} ∈ F_{q^{2}} we have the factorization

R(t, x_{1}) = ∑_{i=0}^{q/n−l} γ_{in}t^{in} ∑_{j=0}^{ln+ε} δ_{j}t^{j},

for some l > 0, with ln + ε < |S|/(q − 1). Then x_{1} ∈ S.

Proof : For x_{0} ∈ S and 0 ≤ j < n we have ρ_{in+j}(x_{0}) = ρ_{in}(x_{0})ρ_{j}(x_{0}) and ρ_{j}(x_{0}) = 0 for ε < j < n. Since ρ_{in+j} has degree at most (in + j)(q − 1) these equations hold identically for in + j ≤ ln + ε < |S|/(q − 1). It follows that δ_{j} = 0 for in + ε < j < (i + 1)n, where i = 0, 1, …, l − 1, and we may write

∑_{j=0}^{ln+ε} δ_{j}t^{j} = ∑_{i=0}^{l} Δ_{i}(t)t^{in},

where Δ_{i} has degree at most ε in t. Let R_{0} = ∑_{j=0}^{ε} ρ_{j}(x_{1})t^{j}. Then we can successively solve Δ_{0} = R_{0}, Δ_{1} + γ_{n}Δ_{0} = R_{0}ρ_{n}(x_{1}), …, Δ_{l} + γ_{n}Δ_{l−1} + … + γ_{nl}Δ_{0} = R_{0}ρ_{ln}(x_{1}) so we get that all Δ’s are constant multiples (depending on x_{1} of course) of R_{0} and it follows that x_{1} ∈ S.

4. Some useful polynomials and their consequences

The points of AG(2, q) can be identified with the elements of GF (q^{2}) in a suitable way, so that in fact all point sets can be considered as subsets of this field. Note that three points a, b, c are collinear, precisely when (a − b)^{q−1} = (a − c)^{q−1}. If the direction of the line joining a and b is identified with the number (a − b)^{q−1}, then a one-to-one correspondence between the q + 1 directions (or parallel classes) and the different (q + 1)-st roots of unity in GF (q^{2}) is obtained. Let B, G and H be as they were in the last section but view them now as subsets of GF (q^{2}).

Let B^{[−1]} = {1/b | b ∈ B \ {0}} and define G^{[−1]} and H^{[−1]} similarly.

Define the polynomials F in two variables and σ_{k} in one variable by

F (t, x) := ∏_{b∈B}(1 − (1 − bx)^{q−1}t) = ∑_{k=0}^{∞}(−1)^{k}σ_{k}t^{k}

where σ_{k} is the k-th elementary symmetric function of the set of polynomials {(1 − bx)^{q−1} | b ∈ B}, a polynomial of degree at most k(q − 1) in x.

Define the formal inverse to F, when viewed as a polynomial in t to be

F^{−1}(t, x) := ∑_{k=0}^{∞} α_{k}t^{k}

such that F F^{−1} ≡ 1. It is clear that α_{k} is a polynomial in x. Moreover it is a sum of certain terms of the form σ_{i_{1}}σ_{i_{2}}....σ_{i_{m}} where ∑_{j=1}^{m} i_{j} = k and therefore has degree at most k(q − 1) in x.

For x_{0} ∈ B^{[−1]} we get that F (t, x_{0})|(1−t^{q+1})^{n−1}, for in this case every line passing through the point 1/x_{0} contains at most n−1 other points of B, so that the multiset {(1/x_{0}−b)^{q−1}} consists of every (q + 1)-st root of unity repeated at most n − 1 times, together with the element 0. The quotient of this divisibility has degree ε and since this is assumed to be less than n (in fact we need only less than q here) we have that the quotient is ∑_{j=0}^{ε} α_{j}(x_{0})t^{j}. Consider the equality

F (t, x_{0}) (∑_{j=0}^{ε} α_{j}(x_{0})t^{j}) = (1 − t^{q+1})^{n−1}.

The right-hand side has no non-constant term until q + 1. If we look at the terms of degree greater than ε yet less than q + 1 we find that

α_{j}(x_{0}) = 0

for ε < j < q + 1 whenever x_{0} ∈ B^{[−1]}.

For x_{0} ∈ G^{[−1]} ∪ H^{[−1]} we get that F (t, x_{0})|(1 − t^{q+1})^{n}, for in this case every line passing through the point 1/x_{0} contains at most n points of B, so that the multiset {(1/x_{0} − b)^{q−1}|b ∈ B} consists of various (q + 1)-st root of unity repeated at most n times. Define the quotient of this divisibility to be Q(t, x_{0}) where Q has degree q + ε in t and

F (t, x_{0})Q(t, x_{0}) = (1 − t^{q+1})^{n} = 1 − t^{nq+n}.

We can write down an expression for Q(t, x_{0}), it is simply

Q(t, x_{0}) = ∑_{j=0}^{q+ε} α_{j}t^{j}.

By definition Q(t, x_{0}) splits into linear factors in t whose (inverse) roots correspond to the directions of lines through 1/x_{0} that have less than n points of B, counted with multiplicity. For example, consider a line through 1/x_{0} that has direction γ yet contains no points of B. It follows that (1 − γt)^{n}|Q(t, x_{0}). Moreover consider x_{0} ∈ G^{[−1]}. The corresponding point to 1/x_{0} lies on q/n external lines and hence

Q(t, x_{0}) = (∑_{i=0}^{q/n} α_{in}t^{in}) (∑_{j=0}^{ε} α_{j}t^{j}) .

Note that this equation also holds for x_{0} ∈ B^{[−1]} since for these points the first factor reduces to the constant term α_{0} = 1.

Consider x_{1} ∈ H^{[−1]} such that 1/x_{1} corresponds to a point on exactly q/n − 1 external lines. It follows that

Q(t, x_{1}) = ( ∑_{i=0}^{q/n−1} γ_{in}t^{in}) (∑_{j=0}^{n+ε} δ_{j}t^{j})

for some γ_{in} and δ_{j}. We are now in the position to apply our lemma, with l = 1 and R = Q. We have B^{[−1]} ∪ G^{[−1]} ⊂ S, so |S| > (n + ε)(q − 1), (here we assume that ε < .381n if q/n = 2, that ε < .476n if q/n = 3 and ε < n/2 if q/n > 2) and we conclude that x_{1} ∈ S. This would imply however that 1/x_{1} corresponds to a point on q/n external lines since Q(t, x_{1}) has q/n factors repeated n times. In other words, 1/x_{1} is a good point. Therefore, all elements of H lie on less than q/n − 1 external lines. In particular if q/n = 2 bad points are on no external lines. In the remaining part we will therefore take q/n > 2.

In the next section we go back to our counting argument from an earlier section with the added knowledge that H contains no points on exactly q/n − 1 external lines.

5. More counting and more polynomials

All points in H are on at most q/n − 2 external lines so we have now that for P ∈ H

∑_{i=1}^{ε} is_{i}(P) ≥ 2n + ε.

Continuing the same argument as before with this new bound implies

|G| + |B| ≥ q^{2} − \frac{(q − n + ε)(nq − q + n − ε)ε}{(n − ε)(2n + ε)} ≥ 0.6q^{2},

where we just use ε ≤ .476n.

Consider again x_{0} ∈ G^{[−1]} ∪ B^{[−1]}. As before,

Q(t, x_{0}) = (∑_{i=0}^{q/n} α_{in}t^{in}) (∑_{j=0}^{ε} α_{j}t^{j})

Consider x_{1} ∈ H^{[−1]} such that 1/x_{1} corresponds to a point on exactly q/n − l external lines, with l < 0.6q/n. It follows that

Q(t, x_{1}) = ( ∑_{i=0}^{q/n−l} γ_{in}t^{in}) ( ∑_{j=0}^{ln+ε} δ_{j}t^{j})

for some γ_{in} and δ_{j}. We may apply our technical lemma again and conclude as before that x_{1} is in fact a good point. Now we have that all points in H are on less than 0.4q/n external lines. For q/n = 3 it pays to be a bit more precise in our bookkeeping, and in fact we get that in this case bad points are on no external lines. So from here on we assume q/n > 3. We return to our counting argument and conclude that for P ∈ H

∑_{i=1}^{ε} is_{i}(P) ≥ 0.6(q/n)n + ε = 0.6q + ε.

Continuing as before we get that |H| < 2nq and hence at least q^{2} − 2nq points are either good or in B. Applying the lemma, now with l = q/n − 3 we get that all points in H are now on at most 2 external lines, and doing it once more on no external lines.

We have now proven that all points on external lines are good points and, since good points lie on exactly q/n external lines, the external lines form a dual maximal arc of degree q/n. The lines in the dual plane that are external to this dual maximal arc are simply the points B ∪ H in the original plane. The external lines to a maximal arc form a dual maximal arc and hence B ∪ H is a maximal arc. Note that this implies that the extension of B to a maximal arc is unique. We have, therefore, proved the following theorem:

Theorem 5.1 Let B be a (nq − q + n − ε, n)-arc in P G(2, q) where n divides q.

1. (q even.) For ε < n/2 and q/n > 2 or ε < .381n and q/n = 2, B can be extended uniquely to some maximal arc containing nq − q + n points.

2. (q odd.) If q/n > 3 then ε > n/2 and if q/n = 3 then ε > .476n.

References

[1] S. Ball, A. Blokhuis and F. Mazzocca, Maximal arcs in Desarguesian planes of odd order do not exist, Combinatorica, 17, (1997), 31–41.

[2] S. Ball and A. Blokhuis, An easier proof of the maximal arcs conjecture, Proc. Amer. Math. Soc., to appear.

[3] A. Cossu, Su alcune proprietà dei {k; n}-archi di un piano proiettivo sopra un corpo finito, Rend. Mat. e Appl., 20, (1961), 271–277.

[4] R. H. F. Denniston, Some maximal arcs in finite projective planes, J. Combin. Theory, 6, (1969), 317–319.

[5] J. W. P. Hirschfeld, Projective Geometries over Finite Fields, Second Edition, Clarendon Press, Oxford (1997).

[6] J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces, Journal of Statistical Planning and Inference, Proceedings of the Bose Memorial Conference (Colorado, June 7–11 1995).

[7] T. Szőnyi, On the embeddability of (k, p)-arcs, manuscript.

[8] J. A. Thas, Construction of maximal arcs and partial geometries, Geom. Dedicata, 3, (1974), 61–64.

[9] J. A. Thas, Some results concerning {(q + 1)(n − 1); n}−arcs and {(q + 1)(n − 1) + 1; n}−arcs in finite projective planes of order q, J. Combin. Theory Ser. A, 19, (1975), 228–232.

[10] J. A. Thas, Construction of maximal arcs and dual ovals in translation planes, Europ. J. Combinatorics, 1, (1980), 189–192.

[11] B. J. Wilson, Incompleteness of (nq + n − q − 2, n)-arcs in finite projective planes of even order, Math. Proc. Cambridge Philos. Soc., 91, (1982), 1–8.