Bounds on (n, r)-arcs and their application to linear codes

S. Ball^{∗} and J.W.P. Hirschfeld

3 April 2005

Abstract

This article reviews some of the principal and recently-discovered lower and upper bounds on the maximum size of (n, r)-arcs in PG(2, q), sets of n points with at most r points on a line. Some of the upper bounds are used to improve the Griesmer bound for linear codes in certain cases. Also, a table is included showing the current best upper and lower bounds for q ≤ 19, and a number of open problems are discussed.

1 Background

The weight of a vector v is the number of non-zero coordinates of v. Let V be the ndimensional vector space over F_{q}. A linear [n, k, d]-code C over F_{q} is a k-dimensional subspace of V all of whose non-zero vectors have weight at least d. Let v_{1}, v_{2}, …, v_{k} be a basis for C and for i = 1, 2, …, n define vectors u_{i} of V, by the rule

(u_{i})_{j} = (v_{j})_{i}.

In other words, the j-th co-ordinate of u_{i} is the i-th coordinate of v_{j}. For all a ∈ (F_{q})^{k} the vector ∑_{j=1}^{k} a_{j}v_{j} has at most n − d zero coordinates and so, for i = 1, 2, …, n,

∑_{j=1}^{k} a_{j}(v_{j})_{i} = 0

has at most n − d solutions. Hence

∑_{j=1}^{k} a_{j}(u_{i})_{j} = 0

has at most n − d solutions, or in other words there are at most n − d of the n vectors u_{i} on the hyperplane with equation

∑_{j=1}^{k} a_{j}X_{j} = 0.

∗The author acknowledges the support of the Ministerio de Ciencia y Tecnologia, España.

The matrix whose rows are the vectors v_{i}, or equivalently whose columns are the vectors u_{i}, is called a generator matrix of the code C. An (n, r)-arc in PG(k − 1, q) is a set of n points K with the property that every hyperplane is incident with at most r points of K and there is some hyperplane incident with exactly r points of K. Hence an (n, n − d)-arc in PG(k − 1, q) is equivalent to a linear [n, k, d]-code where ⟨u_{i}⟩ ≠ ⟨u_{m}⟩ for i ≠ m, that is, linear codes for which any two columns of the generator matrix are linearly independent.

The aim of this article is to formulate the bounds on (n, r)-arcs as bounds that will look more familiar to coding theorists, to survey recent improvements and list a number of open problems.

For further background to linear codes see [43] or [36], and for (n, r)-arcs in PG(2, q), see [32, Chapter 12]. In various articles and books, when r is large, the complement of a (n, r)-arc is considered; this is called a t-fold blocking set.

A t-fold blocking set with respect to hyperplanes is a set of points that is incident with at least t points of every hyperplane and there is some hyperplane incident with exactly t points of the set. In this article it is preferred to leave everything in the language of (n, r)-arcs. Note that an (n, r)-arc in PG(k − 1, q) is the complement of a (q + 1 − r)-fold blocking set of hyperplanes of size q^{k−1} + q^{k−2} + … + 1 − n. An alternative description used is that of an {n, m; N, q}-minihyper which is an m-fold blocking set with respect to hyperplanes of PG(N, q) of size n.

2 Bounds on (n, r)-arcs

In this section, attention is restricted to the case k = 3; that is, (n, r)-arcs in the plane PG(2, q) are considered.

Let K be an (n, r)-arc and P be a point of K. Each line incident with P contains at most r − 1 points of K \ P and the trivial upper bound is obtained:

n ≤ (r − 1)(q + 1) + 1 = (r − 1)q + r.

Cossu [21] noted that when the upper bound is attained every line is incident with either zero or r points of K and if r ≤ q, by counting points of K on lines incident with a point Q not in K, that r divides q. In the case when q is even, such arcs exist for every r dividing q. In the cases r = 2 and r = q/2, the arcs are called hyperovals and dual hyperovals respectively; the known examples are detailed in [34]. There are examples for all r dividing q, due to Denniston. Recently, Mathon [41], Mathon and Hamilton [29] and Hamilton [28] constructed many new examples. In the case that q is odd the upper bound can be realised only in the trivial cases r = 1, r = q and r = q + 1. This was shown in [7]; see [6] for an easier proof. The investigation of (n, r)-arcs was initiated by Barlotti [8] whose early work now implies that, if (r, q) ≠ (2^{t}, 2^{h}) and 2 < r < q, then

n ≤ (r − 1)q + r − 2.

An almost complete table of the known upper bounds can be found in [34, Table 5.2]. The only bound to have been published since then is in the case r | q and q odd, where Weiner [46] improved Szőnyi’s bound [42],

n ≤ (r − 1)q + r − \frac{1}{2} \sqrt[4]{q},

to

n ≤ (r − 1)q + r − \frac{1}{4} \sqrt{q}

for r ≤ \frac{1}{2} \sqrt{q}. There is one bound that appears in [34, Table 5.2] which is attributed to an unpublished manuscript of the first author. However, the bound is not quite correct as the strictly less than should be a less than or equal to. It is obtained as a corollary to the following theorem, to which a proof is provided since it has not appeared anywhere else.

Theorem 2.1. If there exists an ((r − 1)q + ϵ, r)-arc K with ϵ ≥ 1 in a projective plane π of order q which has no skew line, then

r^{2} − ϵq + ϵ(ϵ − r) − r ≥ 0.

Proof Let n = (r − 1)q + ϵ. Counting points of K on each line through a point P of K, it is seen that every line meets K in at least ϵ points. Bruen’s idea [17] is extended to look at the inequality,

∑_{i=ϵ}^{r}(r − i)(i − ϵ)τ_{i} ≥ 0,

where τ_{i} is the number of lines meeting K in i points. Standard counting arguments for a point set in a projective plane give

∑_{i=ϵ}^{r} τ_{i} = q^{2} + q + 1, ∑_{i=ϵ}^{r} iτ_{i} = n(q + 1), ∑_{i=ϵ}^{r} i(i − 1)τ_{i} = n(n − 1),

and, combining these with the inequality, implies that

−n(n − 1) + (ϵ + r − 1)n(q + 1) − ϵr(q^{2} + q + 1) ≥ 0.

By calculation this gives

r^{2} − ϵq + ϵ(ϵ − r) − r ≥ 0.
□

Corollary 2.2. An (n, r)-arc K in a projective plane π of order q which has no skew line satisfies

n ≤ (r − 1)q + ⌊\frac{r^{2}}{q} ⌋ ,

and if \sqrt{q} divides r then

n < (r − 1)q + ⌊\frac{r^{2}}{q} ⌋ .

Proof Theorem 2.1 provides a contradiction for ϵ ≥ r^{2}/q. □

Corollary 2.2 in combination with the following from [4] can always be used to provide an upper bound.

An (n, r)-arc K in a projective plane PG(2, q) which has a skew line satisfies

n ≤ (r − 1)q + p^{e},

where (r, q) = p^{e}.

Table A lists all r for which there is known to exist an (n, r)-arc withn > (r − 2)q + r and the maximum value of n known in that case. An (n, r)-arc in PG(2, q), with n > (r − 2)q + r, is equivalent to a code meeting the Griesmer bound, see Section 3.

In the table, the integer q = p^{h} is exceptional if h is odd, h ≥ 3 and p divides ⌊2\sqrt{q}⌋.

r  q  n
2  q odd  (r − 1)q + 1  [13]
2^{e}  2^{h}  (r − 1)q + r  [26]
r = 3  q non-exceptional  (r − 2)q + 1 + ⌊2\sqrt{q}⌋  [45]
r = 3  q exceptional  (r − 2)q + ⌊2\sqrt{q}⌋  [45]
r = \sqrt{q} + 1  q square  (r − 1)q + 1  [14]
r = (q + 1)/2  q odd  (r − 1)q + 1  [9]
r = (q + 3)/2  q odd  (r − 1)q + 1  [9]
r = q − \sqrt{q}  q square  (r − 1)q + \sqrt{q}  [39]
r = q − p^{e}  q = p^{h}  (r − 1)q + q − r  [40]
r ≥ q + 2 − \sqrt{q},  q square  (r − 1)q + r − \sqrt{q}(q + 1 − r) [31]
r = q − 2  q even  (r − 1)q + 2  [31]
r = q − 2  q odd  (r − 1)q + 1  [31]
r = q − 1  q  (r − 1)q + 1  [31]

Table A : The known families of (n, r)-arcs in PG(2, q) with n > (r − 2)q + r

Large arcs can also be constructed from the set of rational points of an algebraic curve, sometimes by adding extra points; see Daskalov and Jiménez Contreras [24], Giulietti et. al. [27] and Voloch [44].

3 Bounds on linear codes

In this section, some of the upper bounds on (n, r)-arcs are reformulated in terms of linear codes. This gives a Griesmer-like bound (3.1) for three-dimensional codes which is essentially nothing new but only novel in its formulation. Corollary 3.2 generalises the bound to higher-dimensional codes.

Recall that for a linear [n, k, d]-code the Griesmer bound, [43, Theorem 5.2.6], states that

n ≥ ∑_{i=0}^{k−1} ⌈\frac{d}{q^{i}} ⌉ .

An (n, r)-arc in PG(2, q) is equivalent to a linear [n, 3, n − r]-code and so the Griesmer bound tells us, assuming d ≤ q^{2},

n ≥ ∑_{i=0}^{2} ⌈\frac{n − r}{q^{i}}⌉ = n − r + ⌈\frac{n − r}{q}⌉ + 1.

Hence we have the upper bound

n ≤ (r − 1)q + r

and equality in the Griesmer bound if and only if n > (r − 2)q + r.

An (n, r)-arc in PG(2, q) satisfies the upper bound,

n ≤ (r − 1)q + 1,

in the cases when (i) (Blokhuis, see [2]) q is prime and r ≤ (q + 3)/2; (ii) (Section 2) (r, q) = 1 and r < \sqrt{2q} + 1; (iii) (Blokhuis [12]) (r, q) = 1 and there is a line skew from the (n, r)-arc; (iv) (Weiner [46]) q is odd, r | q and r < \frac{1}{4} \sqrt{q}.

The following theorem reformulates this bound in terms of linear codes. Put q = p^{h}, where p is prime. Theorem 3.1. Suppose that one of the following holds:

(i) q is prime and d ≤ (q − 1)(q + 3)/2; (ii) ⌈d/(q − 1)⌉ ≠ −1 (mod p) and d ≤ \sqrt{2q}(q − 1); (iii) ⌈d/(q − 1)⌉ ≠ −1 (mod p), d ≤ q^{2} and there is a codeword of weight n; (iv) q is odd, n = d + p^{e} for some e and d < (\frac{1}{4} \sqrt{q} − 1)(q − 1). Then a linear [n, 3, d] code over F_{q} satisfies

n ≥ d + ⌈\frac{d}{q − 1}⌉ + ⌈\frac{d}{q^{2}} ⌉ .  (3.1)

Proof Let C be a linear [n, 3, d]-code over F_{q}.

If C has repeated columns in its generator matrix, it may be assumed that the first two columns are (1, 0, 0)^{t}. The matrix obtained by deleting the first two columns and the first row generates an [n − 2, 2, d] linear code. Applying the Griesmer bound,

n − 2 ≥ d + ⌈\frac{d}{q}⌉ ,

from which the bound (3.1) follows since d ≤ q^{2}.

If C has no repeated columns, then an (n, n − d)-arc in PG(k − 1, q) is obtained. By assumption,

n ≤ (n − d − 1)q + 1,

and so

n(q − 1) ≥ d + d(q − 1) + q − 1.

Now, dividing by q − 1 gives the bound (3.1) for d ≤ q^{2}.

(i) The condition r ≤ (q + 3)/2 translates to n ≤ d + (q + 3)/2. Hence either the bound (3.1) holds or n ≥ d + (q + 5)/2, which is a better bound if d ≤ (q − 1)(q + 3)/2.

(ii) The condition r < \sqrt{2q} + 1 translates to n < \sqrt{2q} + 1 + d. Hence either the bound (3.1) holds or n ≥ \sqrt{2q} +1+d which is a better bound if d ≤ (q −1)\sqrt{2q}. If equality in the bound violates the condition (n − d, q) = 1, then ⌈d/(q − 1)⌉ ≡ −1 (mod p).

(iii) The condition that there is a line skew from the (n, r)-arc translates to the condition that there is a codeword of weight n.

(iv) The condition r | q translates to n = d + p^{e} for some e. The bound (3.1) holds or n ≥ d + \frac{1}{4} \sqrt{q}, which is a better bound if d ≤ (q − 1)(\frac{1}{4} \sqrt{q} − 1).

□

Corollary 3.2. Suppose one of the following holds:

(i) q is prime and d ≤ q^{k−3}(q − 1)(q + 3)/2;

(ii) ⌈d/\{(q − 1)q^{k−3}\}⌉ ≢ q − 1 (mod p) and d ≤ \sqrt{2q}(q − 1)q^{k−3};

(iii) ⌈d/{(q − 1)q^{k−3}}⌉ ≢ q − 1 (mod p), d ≤ q^{k−1} and there is a codeword of weight n;

(iv) q is odd, n = ∑_{i=0}^{k−3} ⌈d/q^{i}⌉ + p^{e} for some e and d < (\frac{1}{4} \sqrt{q} − 1)(q − 1)q^{k−3}.

Then a linear [n, k, d] code over F_{q} satisfies

n ≥ ∑_{i=0}^{k−3} ⌈\frac{d}{q^{i}} ⌉ + ⌈\frac{d}{(q − 1)q^{k−3}} ⌉ + ⌈\frac{d}{q^{k−1}} ⌉ .  (3.2)

Proof Let k ≥ 4 and let C be a linear [n, k, d]-code over F_{q}.

If C has repeated columns in its generator matrix, assume that the first two columns are (1, 0, …, 0)^{t}. The matrix obtained by deleting the first two columns and the first row generates an [n − 2, k − 1, d] linear code. Applying the Griesmer bound,

n − 2 ≥ ∑_{i=0}^{k−2} ⌈\frac{d}{q^{i}} ⌉ ,

from which the bound (3.1) follows since d ≤ q^{k−1}.

If C has no repeated columns in its generator matrix, then let K be the corresponding (n, n − d) arc in PG(k − 1, q). There is a hyperplane H meeting K in n − d points or else C would have minimum distance more than d. Let e be the minimum such that H ∩ K is an (n − d, n − d − e)-arc in PG(k − 2, q) and let L be a hyperplane meeting H ∩ K in n − d − e points. Then counting points of K on hyperplanes containing L gives

n ≤ eq + n − d,

and hence e ≥ ⌈d/q⌉. Thus H ∩ K gives us an [n − d, k − 1, ⌈d/q⌉] linear code.

By iteration an [n − d − ⌈d/q⌉ − … − ⌈d/q^{k−4}⌉ , 3, ⌈d/q^{k−3}⌉] linear code is obtained. Now, according to the conditions, Theorem 3.1 can be applied. □

4 Large (n, r)-arcs in small planes

Table B is an update of [34, Table 5.4] including results of Daskalov and Medotieva [22, 25] and the many new constructions of Braun et al. [16].

The new (n, r)-arcs from [16] were found in the following way. Let M be the point-line incidence matrix of PG(2, q). Then an (n, r)-arc is given by a vector x ∈ {0, 1}^{q^{2}+q+1} with the property that x has n coordinates equal to 1 and the coordinates of Mx are at most r. Even for small q the computation involved in solving these equations is unfeasible. For this reason the authors of [16] choose a subgroup G of the automorphism group of PG(2, q) and consider the reduced incidence matrix M^{G} whose columns are the G-orbits on the points and whose rows are the G-orbits on the lines. If t is the number of orbits and w_{j} is the size of orbit of points corresponding to the j-th column of M^{G}, an (n, r)-arc is given by a vector x ∈ {0, 1}^{t} with the property that ∑_{j=1}^{t} x_{j}w_{j} = n and the coordinates of M^{G}x are at most r. Various small subgroups G are used, the corresponding systems of diophantine equations are solved exhaustively by computer using lattice-point enumeration.

Table C provides all the references for the lower and upper bounds in Table B. The reference [∗] means that the bound can be deduced from the bounds in Section 2. In the case of a (98, 7)-arc in PG(2, 16), a (165, 11)-arc in PG(2, 16), a (182, 12)-arc in PG(2, 16), there is equality in the bound of Theorem 2.1. This implies that such arcs, if they have no skew line, have only ϵ-secants and r-secants. Easy counting arguments give a contradiction. If they have a skew line the bound from [4] can be used.

The reference [∗∗] refers to the following slight improvement of [2, Theorem 4.2]. If there is equality in the bound and r ≥ (q + 1)/2 then the number of r-secants can be counted, following the same arguments as used for the small planes in [5], and is (q − 1)(2q + 3 − 2r)(q + 1)/2(q + 1 − r). If this number is not an integer then the bound can be improved to

n ≤ (r − 1)q + r − (q + 3)/2.

q 3 4 5 7 8 9  11  13  16  17  19

r

2  4 6 6 8 10 10  12  14  18  18  20
3  9 11 15 15 17  21  23  28...33 28...35 31...39
4  16 22 28 28 32...34 38...40  52  48...52 52...58
5  29 33 37 43...45 49...53  65  61...69 68...77
6  36 42 48  56  64...66 78...82 78...86 86...96
7  49 55  67  79  93...97 94...103 105...115
8  65 77...78  92  120  114...120 124...134
9  89...90  105  128...131  137  147...153
10  100...102 118...119 142...148  154  172
11  132...133 159...164 166...171  191
12  145...147 180...181 182...189 204...210
13  195...199 204...207 225...230
14  210...214 221...225 242...250
15 231 239...243 262...270
16  256...261 285...290
17  305...310
18  324...330

Table B : The size of the largest (n, r)-arc in PG(2, q) for small q

q 3  4  5  7  8  9  11  13  16  17  19

r

2 [13] [13] [13] [13] [13] [13] [13] [13] [13] [13] [13]
3  [35] [35] [15] [11] [10] [33]...[37] [2]...[38] [16]...[8] [16]...[8] [16]...[8]
4 [35] [35] [21] [35] [16]...[35] [16]...[35] [26] [16]...[35] [16]...[35]
5  [20] [39] [39] [2]...[2] [16]...[2] [14]...[∗] [16]...[2] [16]...[2]
6  [20] [31] [39] [9]...[2] [16]...[2] [16]...[∗] [16]...[2] [16]...[2]
7  [11] [3] [9]...[2]  [9]...[2] [16]...[∗] [16]...[2] [16]...[2]
8  [5] [2]...[2]  [9]...[2]  [26]  [16]...[2] [16]...[2]
9  [31]...[5] [2]...[2] [16]...[∗] [9]...[2] [16]...[2]
10 [31]...[5] [16]...[2] [16]...[∗] [9]...[2] [9]...[2]
11  [16]...[3] [16]...[∗] [16]...[22] [9]...[2]
12  [16]...[5] [16]...[∗] [22]...[22] [16]...[∗∗]
13  [16]...[30] [16]...[22] [16]...[∗∗]
14  [31]...[3] [25]...[22] [16]...[∗∗]
15 [5] [31]...[22] [16]...[23]
16  [31]...[5] [16]...[∗∗]
17  [31]...[23]
18  [31]...[5]

Table C : References for the size of the largest (n, r)-arc in PG(2, q) for small q

5 Open problems

1. In most cases no example is known of an (n, r)-arc with n/q large, say n/q > r−2. The best that can be done in general is to take (a) for r < q/2 the union of ⌊r/2⌋ conics, which gives n/q > r/2 and (b) for r > q/2 large the complement of the union of 2(q − r) + 1 lines of a dual (2(q − r) + 1, 2)-arc, which gives n/q > q − 2r + (2r^{2} − r)/q.

2. In the case r = 3 there is a construction of size q + ⌊2\sqrt{q}⌋ for all q and an upper bound of n ≤ 2q + 1. Any progress on determining a constant c such that the upper bound n/q < c < 2 for q large enough, or a construction where n/q > c > 1 for infinitely many q will be rewarded by a cheque for 10,000 Hungarian florins from Prof. A. Blokhuis.

3. In the case r = q − 1 Braun et al.’s [16] discovery of a (145,12)-arc in PG(2, 13) ends speculation that an (n, q − 1)-arc in PG(2, q), q prime, satisfies n ≤ (q − 2)q + 1; the so-called 3p conjecture for double blocking sets, see [5]. It is known from [5] that n ≤ (q − 2)q + \frac{q−3}{2} but in general there is no better construction than the complement of three non-concurrent lines, which provides an example with n = (q − 2)q + 1. Any construction of a family of (n, q − 1)-arcs in PG(2, q), for infinitely many q prime, with n ≥ (q − 2)q + 2 would be of interest.

4. For q prime, there are upper bounds on n due to Blokhuis which appear in [2]. For q non-prime and r > \sqrt{q} + 1, there are few upper bounds on n that use the fact that the projective plane is Desarguesian; in other words only counting arguments are used. The only exceptions are when r > q − q^{1/6} and q is square.

References

[1] S. Ball, On sets of points in finite planes, D.Phil. thesis, University of Sussex, 1994.

[2] S. Ball, Multiple blocking sets and arcs in finite planes, J. London Math. Soc. 54 (1996), 581–593.

[3] S. Ball, On the size of a triple blocking set in P G(2, q), European J. Combin. 17 (1996), 427–435.

[4] S. Ball, On nuclei and blocking sets in Desarguesian spaces, J. Combin. Theory Ser. A 85 (1999), 232–236.

[5] S. Ball and A. Blokhuis, On the size of a double blocking set in P G(2, q), Finite Fields Appl. 2 (1996), 125–137.

[6] S. Ball and A. Blokhuis, An easier proof of the maximal arcs conjecture, Trans. Amer. Math. Soc. 126 (1998), 3377–3380.

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

[8] A. Barlotti, Su {k; n}-archi di un piano lineare finito, Boll. Un. Mat. Ital. 11 (1956), 553–556.

[9] A. Barlotti, Some topics in finite geometrical structures, Institute of Statistics Mimeo Series 439, Univ. of North Carolina, 1965.

[10] M. Barnabei, D. Searby and C. Zucchini, On small (k, q)-arcs in planes of order q^{2}, J. Combin. Theory Ser. A 24 (1978), 241–246.

[11] J. Bierbrauer, (k, n)-arcs of maximal size in the plane of order 8, unpublished manuscript (1988).

[12] A. Blokhuis, On multiple nucei and a conjecture of Lunelli and Sce, Bull. Belg. Math. Soc. 3 (1994), 349–353.

[13] R.C. Bose, Mathematical theory of the symmetrical factorial design, Sankhyā 8 (1947), 107–166.

[14] R.C. Bose, On the application of finite projective geometry for deriving a certain series of balanced Kirkman arrangements, Golden Jubilee Commemoration Volume (1958–1959) Calcutta Math. Soc., (1959), 341–354.

[15] D.L. Bramwell, Ph.D. thesis, University of London, 1973.

[16] M. Braun, A. Kohnert and A. Wassermann, Construction of (n, r)-arcs in P G(2, q), preprint.

[17] A.A. Bruen, Blocking sets in finite projective planes, SIAM J. Appl. Math. 21 (1971), 380–392.

[18] J.M. Chao and H. Kaneta, Classical arcs in P G(r, q) for 11 ≤ q ≤ 19, Discrete Math. 174 (1997), 87–94.

[19] J.M. Chao and H. Kaneta, Classical arcs in P G(r, q) for 23 ≤ q ≤ 27, Discrete Math. 226 (2001), 377–385.

[20] Z. Ciechanowicz, Ph.D. thesis, University of London, 1980.

[21] 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.

[22] R.N. Daskalov, On the existence and the nonexistence of some (k, r)-arcs in P G(2, 17), in: Proceedings of Ninth International Workshop on Algebraic and Combinatorial Coding Theory, Kranevo, Bulgaria (2004), 95-100.

[23] R.N. Daskalov, On the nonexistence of (271, 15)-arcs and (311, 17)-arcs in P G(2, 19), unpublished manuscript.

[24] R.N. Daskalov and M.E. Jimenéz Contreras, New (k; r)-arcs in the projective plane of order thirteen, J. Geom. 80 (2004) 10-22.

[25] R.N. Daskalov amd E. Metodieva, New (k, r)-arcs in P G(2, 17) and the related optimal linear codes, Math. Balkanica 18 (2004), 121-127.

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

[27] M. Giulietti, F. Pambianco, F. Torres and E. Ughi, On complete arcs arising from plane curves, Des. Codes Cryptogr., 25 (2002) 237–246.

[28] N. Hamilton, Degree 8 maximal arcs in PG(2, 2^{h}), h odd, J. Combin. Theory Ser. A 100 (2002), 265–276.

[29] N. Hamilton and R. Mathon, More maximal arcs in Desarguesian projective planes and their geometric structure, Adv. Geom. 3 (2003), 251–261.

[30] R. Hill, Some problems concerning (k, n)-arcs in finite projective planes, Rend. Sem. Mat. Brescia 7 (1984), 367–383.

[31] R. Hill and J.R.M. Mason, On (k, n)-arcs and the falsity of the Lunelli–Sce conjecture, Finite Geometries and Designs, London Math. Soc. Lecture Note Series 49, Cambridge University Press, Cambridge, 1981, 153–168.

[32] J.W.P. Hirschfeld, Projective Geometries over Finite Fields, Second edition, Oxford University Press, Oxford, 1998.

[33] J.W.P. Hirschfeld and A. Sadeh, The projective plane over the field of eleven elements, Mitt. Math. Sem. Giessen 164 (1984), 245–257.

[34] J.W.P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces: update 2001, in: Finite Geometries, Developments in Mathematics 3, Kluwer, 2001, 201–246.

[35] L. Lunelli and M. Sce, Considerazioni arithmetiche e resultati sperimentali sui {K; n}_{q} archi, Ist. Lombardo Accad. Sci. Rend. A 98 (1964), 3–52.

[36] F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.

[37] S. Marcugini, A. Milani and F. Pambianco, Maximal (n, 3)-arcs in P G(2, 11), Discrete Math. 208/209 (1999), 421–426.

[38] S. Marcugini, A. Milani and F. Pambianco, Maximal (n, 3)-arcs in P G(2, 13), Discrete Math., to appear.

[39] J.R.M. Mason, On the maximum sizes of certain (k, n)-arcs in finite projective geometries, Math. Proc. Cambridge Philos. Soc. 91 (1982), 153–170.

[40] J.R.M. Mason, A class of ((p^{n} − p^{m})(p^{n} − 1), p^{n} − p^{m})-arcs in P G(2, p^{n}), Geom. Dedicata 15 (1984), 355–361.

[41] R. Mathon, New maximal arcs in Desarguesian planes, J. Combin. Theory Ser. A 97 (2002), 353–368.

[42] T. Szőnyi, On the embedding of (k, p)-arcs, Des. Codes Cryptogr. 18 (1999), 235–246.

[43] J.H. van Lint, An Introduction to Coding Theory, Third edition, Springer-Verlag, 1998.

[44] J.F. Voloch, A note on (k, n)-arcs, Discrete Math., to appear.

[45] W.C. Waterhouse, Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. 2 (1969), 521–560.

[46] Z. Weiner, On (k, p^{e})-arcs in Desarguesian planes, Finite Fields Appl. 10 (2004), 390–404.

S. Ball Departament de Matemàtica Aplicada IV Universitat Politècnica de Catalunya Jordi Girona 1-3 Mòdul C3, Campus Nord 08034 Barcelona Spain

simeon@mat.upc.es
http://www-ma4.upc.es/∼simeon/

J.W.P. Hirschfeld Department of Mathematics University of Sussex Brighton BN1 9RF United Kingdom

jwph@sussex.ac.uk
http://www.maths.susx.ac.uk/Staff/JWPH/