Computer search in projective planes for the sizes of complete arcs

The spectrum of possible sizes k of complete k-arcs in finite projective planes PG(2, q) is investigated by computer search. Backtracking algorithms that try to construct complete arcs joining the orbits of some subgroup of collineation group PΓ L (3, q) and randomized greedy algorithms are applied. New upper bounds on the smallest size of a complete arc are given for q = 41, 43, 47, 49, 53, 59, 64, 71 ≤ q ≤ 809, q ≠ 529, 625, 729, and q = 821. New lower bounds on the second largest size of a complete arc are given for q = 31, 41, 43, 47, 53, 125. Also, many new sizes of complete arcs are obtained for 31 ≤ q ≤ 167.     

Cyclic caps in PG(3,q)

This article investigates cyclic completek-caps in PG(3,q). Namely, the different types of completek-capsK in PG(3,q) stabilized by a cyclic projective groupG of orderk, acting regularly on the points ofK, are determined. We show that in PG(3,q),q even, the elliptic quadric is the only cyclic completek-cap. Forq odd, it is shown that besides the elliptic quadric, there also exist cyclick-caps containingk/2 points of two disjoint elliptic quadrics or two disjoint hyperbolic quadrics and that there exist cyclick-caps stabilized by a transitive cyclic groupG fixing precisely one point and one plane of PG(3,q). Concrete examples of such caps, found using AXIOM and CAYLEY, are presented.     

New (k; r)-arcs in the projective plane of order thirteen

A (k;r)-arc $\cal K$ is a set of k points of a projective plane PG(2, q) such that some r, but no r +1 of them, are collinear. The maximum size of a (k; r)-arc in PG(2, q) is denoted by m _r (2, q). In this paper a (35; 4)-arc, seven (48; 5)-arcs, a (63; 6)-arc and two (117; 10)-arcs in PG(2, 13) are given. Some were found by means of computer search, whereas the example of a (63; 6)-arc was found by adding points to those of a sextic curve $\cal C$ that was not complete as a (54; 6)-arc. All these arcs are new and improve the lower bounds for m _r (2, 13) given in [10, Table 5.4]. The last section concerns the nonexistence of (40; 4)-arcs in PG(2, 13).     

Random constructions and density results

In this paper we outline a construction method which has been used for minimal blocking sets in PG(2, q) and maximal partial line spreads in PG(n, q) and which must have a lot of more applications. We also give a survey on what is known about the spectrum of sizes of maximal partial line spreads in PG(n, q). At the end we list some more elaborate random techniques used in finite geometry.      

Classification of maximal caps in PG(3,5) different from elliptic quadrics

Ak-cap in PG(3,q) is a set of k points, no three of which are collinear. A k-cap is calledcomplete if it is not contained in a (k+1)-cap. The maximum valuem ₂(3, q) ofk for which there exists a k-cap in PG(3,q) is q²+1. Letm ₂(3, q) denote the size of the second largest complete k-cap in PG(3,q). This number is only known for the smallest values of q, namely for q=2, 3,4 (cf. [2], pp. 96–97 and [3], p. 303). In this paper we show thatm ₂(3,5)=20. We also prove that there are, up to isomorphism, only two complete 20-caps in PG(3,5) and determine their collineation groups.In memoriam Giuseppe TalliniWork done within the activity of GNSAGA of CNR and supported by MURST.     

Linear k-blocking Sets

We point out the relationship between normal spreads and the linear k-blocking sets introduced in [9]. We give a characterisation of linear k-blocking sets proving that the projections and the embeddings of a PG(kt,q) in are linear k-blocking sets of . Finally, we construct some new examples. Received December 19, 1997/Revised September 19, 2000 RID="*" ID="*" Partially supported by Italian M.U.R.S.T.     

Note on the existence of large minimal blocking sets in galois planes

A subsetS of a finite projective plane of orderq is called a blocking set ifS meets every line but contains no line. For the size of an inclusion-minimal blocking setq+ +Sq +1 holds ([6]). Ifq is a square, then inPG(2,q) there are minimal blocking sets with cardinalityq +1. Ifq is not a square, then the various constructions known to the author yield minimal blocking sets with less than 3q points. In the present note we show that inPG(2,q),q1 (mod 4) there are minimal blocking sets having more thanqlog₂ q/2 points. The blocking sets constructed in this note contain the union ofk conics, whereklog₂ q/2. A slight modification of the construction works forq3 (mod 4) and gives the existence of minimal blocking sets of sizecqlog₂ q for some constantc.As a by-product we construct minimal blocking sets of cardinalityq +1, i.e. unitals, in Galois planes of square order. Since these unitals can be obtained as the union of parabolas, they are not classical.     

Maximal partial spreads in PG (3, q)

We transfer the whole geometry of PG(3, q) over a non-singular quadric Q_4,q of PG(4, q) mapping suitably PG(3, q) over Q_4,q. More precisely the points of PG(3, q) are the lines of Q_4,q; the lines of PG(3, q) are the tangent cones of Q_4,q and the reguli of the hyperbolic quadrics hyperplane section of Q_4,q. A plane of PG(3, q) is the set of lines of Q_4,q meeting a fixed line of Q_4,q. We remark that this representation is valid also for a projective space over any field K and we apply the above representation to construct maximal partial spreads in PG(3, q). For q even we get new cardinalities for For q odd the cardinalities are partially known.     

On the sharpness of a theorem of B. segre

The theorem of B. Segre mentioned in the title states that a complete arc of PG(2,q),q even which is not a hyperoval consists of at mostq−√q+1 points. In the first part of our paper we prove this theorem to be sharp forq=s ² by constructing completeq−√q+1-arcs. Our construction is based on the cyclic partition of PG(2,q) into disjoint Baer-subplanes. (See Bruck [1]). In his paper [5] Kestenband constructed a class of (q−√q+1)-arcs but he did not prove their completeness. In the second part of our paper we discuss the connections between Kestenband’s and our constructions. We prove that these constructions result in isomorphic (q−√q+1)-arcs. The proof of this isomorphism is based on the existence of a traceorthogonal normal basis in GF(q ³) over GF(q), and on a representation of GF(q)³ in GF(q ³)³ indicated in Jamison [4].     

Flocks and ovals

An infinite family of q-clans, called the Subiaco q-clans, is constructed for q=2^e. Associated with these q-clans are flocks of quadratic cones, elation generalized quadrangles of order (q ², q), ovals of PG(2, q) and translation planes of order q ² with kernel GF(q). It is also shown that a q-clan, for q=2^e, is equivalent to a certain configuration of q+1 ovals of PG(2, q), called a herd.W. Cherowitzo gratefully acknowledges the support of the Australian Research Council and has the deepest gratitude and warmest regards for the Combinatorial Computing Research Group at the University of Western Australia for their congenial hospitality and moral support. I. Pinneri gratefully acknowledges the support of a University of Western Australia Research Scholarship.     

Classification of triply-retractive semifields of order q 4

A complete classification of the semifield spreads of order q⁴ that triply-retract to mixed partitions of PG (3, q²) is given.     

Some families of complete caps of quadrics and symplectic polarities over GF(8)

A cap on a quadric is a set of its points whose pairwise joins are all chords. A cap is complete if it is not part of a larger one. The only field for which all complete quadric caps are known is GF(2). Those caps are small; the biggest for each quadric is of order the dimension of the ambient space. Apart from information about ovoids in dimensions at most 7, little else is known. Here, the evidence is increased by providing caps over GF(2), odd, which, if >1, have size of order the dimension cubed. In particular, complete caps are obtained for the quadrics Q _2m (8), Q ₊ ^8k+7 (8), Q _- ^8k+3 (8), Q ₊ ^8k+1 (8) and Q _- ^8k+5 (8). These caps on Q ₊ ^8k+7 (8) and Q _- ^8k+3 (8) are complete on any Q _n(8) of which their quadrics are sections; so is that that of Q ₄₊₂(8) for any Q _2n (8) of which Q ₄₊₂(8) is a section with the same kernel. From the correspondence with Q _2n (8) complete caps are obtained for symplectic polarities over GF(8).     

A characterisation of spreads ovally-derived from Desarguesian spreads

We characterise all spreads that are obtainable from Desarguesian spreads by replacing a partial spread consisting of translation ovals; the corresponding ovally-derived planes are generalised André planes, of order 2 ^N , although not all generalised André planes are ovallyderived from Desarguesian planes. Our analysis allows us to obtain a complete classification of all nearfield planes that are ovally-derived from Desarguesian planes. It turns out that whether or not a nearfield plane is ovally-derived from a Desarguesian plane depends solely on the parametersq andr, where GF (q) is the kern, andr is the dimension of the plane. Our results also imply that a Hall plane of even orderq ² can be ovally-derived from a Desarguesian spread if and only ifq is a square.     

Extending MDS Codes

A q-ary (n, k)-MDS code, linear or not, satisfies n ≤ q + k − 1. A code meeting this bound is said to have maximum length. Using purely combinatorial methods we show that an MDS code with n = q + k − 2 can be uniquely extended to a maximum length code if and only if q is even. This result is best possible in the sense that there is, for example, a non-extendable 4-ary (5, 4)-MDS code. It may be that the proof of our result is as interesting as the result itself. We provide a simple necessary and sufficient condition for code extendability. In future work, this condition might be suitably modified to give an extendability condition for arbitrary (shorter) MDS codes.Received December 1, 2003     

Spreads and ovoids in finite generalized quadrangles

This paper is a survey on the existence and non-existence of ovoids and spreads in the known finite generalized quadrangles. It also contains the following new results. We prove that translation generalized quadrangles of order (s,s ²), satisfying certain properties, have a spread. This applies to three known infinite classes of translation generalized quadrangles. Further a new class of ovoids in the classical generalized quadranglesQ(4, 3 ^e ),e3, is constructed. Then, by the duality betweenQ(4, 3 ^e ) and the classical generalized quadrangleW (3 ^e ), we get line spreads of PG(3, 3 ^e ) and hence translation planes of order 3^2e . These planes appear to be new. Note also that only a few classes of ovoids ofQ(4,q) are known. Next we prove that each generalized quadrangle of order (q ²,q) arising from a flock of a quadratic cone has an ovoid. Finally, we give the following characterization of the classical generalized quadranglesQ(5,q): IfS is a generalized quadrangle of order (q,q ²),q even, having a subquadrangleS isomorphic toQ(4,q) and if inS each ovoid consisting of all points collinear with a given pointx ofS\S is an elliptic quadric, thenS is isomorphic toQ(5,q).     

The classification of spreads in PG(3, q) admitting linear groups of order q(q+1), I. odd order

A classification is given of all spreads in PG(3, q), q = p^r, p odd, whose associated translation planes admit linear collineation groups of order q(q +1) such that a Sylow p-subgroup fixes a line and acts non-trivially on it.The authors are indebted to T. Penttila for pointing out the special examples of conical flock translation planes of order q² that admit groups of order q(q+1), when q = 23 or 47.     

Classes of optical orthogonal codes from arcs in root subspaces

We present new constructions for (n,w,λ) optical orthogonal codes (OOC) using techniques from finite projective geometry. In one case codewords correspond to (q-1)-arcs contained in Baer subspaces (and, in general, kth-root subspaces) of a projective space. In the other construction, we use sublines isomorphic to PG(2,q) lying in a projective plane isomorphic to PG(2,q^k), k>1. Our construction yields for each λ>1 an infinite family of OOCs which, in many cases, are asymptotically optimal with respect to the Johnson bound.     

Characterizations of Buekenhout-Metz unitals

We give a characterization of the Buekenhout-Metz unitals in PG(2, q ²), in the cases that q is even or q=3, in terms of the secant lines through a single point of the unital. With the addition of extra conditions, we obtain further characterizations of Buekenhout-Metz unitals in PG(2, q ²), for all q. As an application, we show that the dual of a Buekenhout-Metz unital in PG(2, q ²) is a Buekenhout-Metz unital.     

How many s-subspaces must miss a point set in PG(d, q)

The following result is well-known for finite projective spaces. The smallest cardinality of a set of points of PG(n, q) with the property that every s-subspace has a point in the set is (q ^n+1-s - 1)/(q - 1). We solve in finite projective spaces PG(n, q) the following problem. Given integers s and b with 0 ≤ s ≤ n - 1 and 1 ≤ b ≤ (q ^n+1-s - 1)/(q - 1), what is the smallest number of s-subspaces that must miss a set of b points. If d is the smallest integer such that b ≤ (q ^d+1 - 1)/(q - 1), then we shall see that the smallest number is obtained only when the b points generate a subspace of dimension d. We then also determine the smallest number of s-subspaces that must miss a set of b points of PG(n, q) which do not lie together in a subspace of dimension d. The results are obtained by geometrical and combinatorial arguments that rely on a strong algebraic result for projective planes by T. Szőnyi and Z. Weiner.     

Spreads,ovoids andS 5

We consider translation planes of orderq ² (whereq andq ² - 1 are coprime to 30) such thatS ₅ acts on the line at infinity. It turns out that the Klein correspondence is in particular useful for the investigation of these planes. Representations of the planes, automorphisms and examples of low order are studied in detail. In view of a problem of Ostrom (Math. Z. 156 (1977), 59–71), series of translation planes are constructed with the following property: the translation complement is nonsolvable and has an order coprime to the characteristic of the plane.