2. GALOIS GEOMETRIES

The references between [ ] are listed in publications.html for typology.


The first area of study in this field was the spectrum of cardinalities and the geometrical properties of complete arcs and caps in Galois geometries PG(r,q). An n-arc is a set of n points such that no more than (r+1) are on a hyperplane. It is complete if it is not contained in an (n+1)-arc. Their coding theoretic equivalent are MDS-codes. A cap in PG(r,q) is a set of points no three of which are collinear. It is complete if every point in space is collinear with some two points of the cap. Complete caps are of particular interest in coding theory as they are equivalent to q-ary linear quasi-perfect codes of redundancy (r+1) and minimum distance 4. It was in fact the link between information theory and Galois geometries which stimulated the research, initiated by B. Segre in 1950s, into the possible cardinalities of caps.
In various cases this study has relied on intricate computer calculations. It is complicated to arrive at a satisfactory theoretical solution as the geometric, combinatorial and also group theoretic properties of finite planes vary considerably with the arithmetic properties of the order. This is a costumary phenomenon in number theory.
Not many general results are known. In the case of the maximum possible cardinality this is a special case of the packing problem as formulated in the Congress “R.C. Bose Memorial Conference on Statistical Design and related Combinatorics” – Fort-Collins, Colorado. The same is true of the problem of determining the smallest cardinality of complete arcs or caps. A complete theoretical determination of the maximum cardinality of complete caps is known only in dimensions two and three: if the dimension is two the maximum size is q+1 (a conic) if q is odd and q+2 (hyperovals) if q is even; if the dimension is three the maximum size is q^2 + 1 (elliptic quadric).
My research in this area has produced results in the following directions:


2.1. ARCS IN PROJECTIVE GALOIS PLANES

Each arc in PG(r,q) produces via a sequence of projections a plane arc. This leads to the situation that plane arcs are important in the general context of Galois geometries. My attack on the problems defined by B. Segre were based on algebraic geometry over finite fields and on combinatorial methods.
The study of the connections between finite geometries and the theory of algebraic curves initiated in the 1950s with the fundamental works by Segre himself. This theory received an important impulse in the late 1980s by the Stöhr-Voloch theory concerning the number of rational points of an algebraic curve over a finite field. The central idea behind this theory is that curves with many rational points must have certain non-classical characteristics. The study of non-classical curves is the main instrument used to obtain the recent results on the possible cardinalities of complete arcs in the plane. More specifically the second largest cardinality of complete arcs is not known in general. Certain limits on this number are due to B. Segre, J.F. Voloch, J.A. Thas, J.W.P. Hirschfeld and G. Korchmáros. The proofs of these results are all based on the original idea of Segre's to associate to an n-arc in PG(2,q) an algebraic curve defined over GF(q) whose number of rational points is at least n(q-n+2). This algebraic curve is called the envelope of the arc.
In [18] we study the components of the envelopes of sufficiently large arcs, in odd characteristic. In particular we concentrate on components that contain special points - rational points of the envelope which are neither singular nor flexes. The Stöhr -Voloch theory yields an estimate for the number of rational points which in turn allows to derive a limit for the cardinality of the complete arc. This limit depends only on q and on the last Frobenius order of the linear series intersected on this component by the conics of the plane. We also determine explicitly the classes of curves which can occur as irreducible components of large complete arcs. Those curves are classical with respect to the linear series determined by the lines but neither classical nor Frobenius classical with respect to the conics. Those results have motivated further studies into those classes of curves, among others in the works of A.Aguglia-G.Korchmáros and of M.Giulietti where new results concerning their number of rational points are obtained.
In [29] we construct highly symmetric arcs using the most symmetric curves of degrees 4 (the Klein quartic) and 6 (the Wiman sextic). More precisely it is shown that the sets of their flexes, of cardinality 24 and 72 respectively, in almost all characteristics form arcs admitting PSL(2,7) and A_6 as symmetry groups, respectively. Moreover those arcs turn out to be complete in all cases when complete arcs of that size are theoretically possible.
In [55], using the immersion of A_6 in PGL(3,k), arcs of projective planes which are invariant under the action of A_6 are studied, obtaining for some values of q complete plane arcs of size less then the size of known complete arcs.

We focussed attention on the determination of complete arcs of small cardinaltity, the aim being to solve the problem of the smallest cardinality. In complete generality this problem appears to be untractable. This problem has received much attention: in the beginning of my research the knowledge of the minimal order in PG(2, q) was limited to cases q<=16 and general constructions were limited to cardinalities in the central part of the spectrum.
In [6], [19], [37], [AC16] the minimum order was determined in PG(2, q) for 17<=q<=32. In cases q<= 27 we also determined the spectrum of complete arcs and completed the classification up to automorphisms.

In order to obtain those results it has been necessary to use a sophisticated system of electronic calculations based on the geometric-group theoretic properties. In fact the difficulties increase exponentially with q: to this aim we developed algorithms which use the geometric symmetry properties of the ambient space in order to reduce the number of cases to be considered and in order to avoid the construction of isomorphic copies of the same solution. In particular a hybrid algorithm has been developed which combines a classification step with an exhaustive search step based on backtracking. The advantage of this approach is in the fact that the informations concerning symmetries of the objects obtained in the classification process are used in the subsequent step. This allows the exclusion of cases which are equivalent to cases already considered.
In [39] we develop a construction of arcs obtained by adding to a fixed highly saturating arc orbits of its stabilizer. This approach produces in particular in case q=37 complete arcs of cardinality smaller than previously known, case q=37 being the first open case in this respect. In [9] we present a geometric-group theoretic construction of an infinite family of small complete arcs which in certain cases yields the minimum cardinality.
In [30] a large number of small arcs in PG(2,q), q<1000, are obtained, using randomized and heuristic algorithms and by manipulating the orbits of symmetry groups acting on PG(2, q). The results suggest certain general conjectures concerning the behaviour of the cardinalities close to the minimal cardinality.
The refinement of a randomized greedy algorithm developed in [30] for the search of point sets with interesting extremal properties has led to search process for larger values of q (up to about 80,000). This led to the examples described in [AC19], [42], [52] [AC19], [AC22] and [56]: in many cases those examples produce new bounds on the minimum length of plane complete arcs. The bulk of the data produced by the heuristic algorithms has been analyzed in [AC24] where the asymptotic behaviour of the bound on the minimal length of complete plane arcs has been described.
In [41] we develop a procedure for the construction of arcs of cardinality 6( √q -1) in planes of order 2^{4h+2}. Those arcs turn out to be complete for q <=2^18.
General constructions for complete arcs sharing many points with a conic have been the objective of [AC17], [52] e [60]. In [AC17] and [60] we find complete arcs in PG(2, 17) and in PG(2, 59) which consist of (q + 3)/2 points on a conic and 4 and 3 points outside, respectively. Those are counterexamples to a result by G. Pellegrino from 1977 which states that for q=1 (mod 4) a complete arc with (q + 3)/2 points on a conic can have at most 2 points outside that conic.
The ovals - plane (q + 1)-arcs - have the property to admit precisely one tangent in each point. In [AC11] and [46] we consider point sets in the plane with this property, the so-called semiovals. Those structures are of intrinsic geometric interest and also possess cryptographic applications (Batten 2000). We obtain characterization results, constructions and non-existence results. We also construct new examples of semiovals of large cardinality.


2.2. PLANE (n, k)-ARCS

One natural generalization of the concept of an arc in the plane is the notion of an (n, k)-arc (or arc of species k): a set of n points no k + 1 of which are collinear. A natural class of examples of an (n, k)-arc in PG(2, q) is constituted by the GF(q)-rational points of a plane algebraic curve defined over GF(q) without linear components. Here n is the number of such points and k is the degree of the curve. In general such an (n, k)-arc is incomplete. In [17] the interesting problem is addressed when those (n, k)-arcs will in fact be complete. This problem has initially been posed by Hirschfeld and Voloch. They gave a partial answer in case k = 3: apart from conics and cubics only a small number of examples were known, the Hermitian curves among them. The Hermitian curve is non-singular and not Frobenius classic with respect to the linear system determined by the lines of the plane. It was then natural to ask if the rational points of every non Frobenius classical curve form a complete (n, k)-arc. In [17] we give an affirmative answer under the additional hypothesis that the degree of the dual curve is less than q +1: this condition turns out to be satisfied by a certain sporadic curve defined over GF(8): it follows from a recent result due to J.Top that the curve mentioned above and the Fermat quartic over GF(9) are the only curves of genus 3 over GF(q) with more than 2q +6 rational points. In [17] we also present various examples of complete (n, k)-arcs derived from algebraic curves: we emphasize that in many of those cases geometrical structures with those parameters had not been known before.
To each plane (n, k)-arc is canonically associated a linear code of length n and dimension 3: its error-correcting capability increases with the difference n-k (the redundancy). For fixed k one is therefore interested in the largest value of n for an (n, k)-arc (packing problem). Species 3 is particularly interesting as the (n, 3)-arcs in the plane correspond to linear NMDS-codes of dimension 3 (while an MDS code [n, k, d] has minimum distance meeting the bound n-k+1 an NMDS code has minimum distance n-k and its dual has minimum distance k) In [10], [26] the packing problem for arcs of species 3 in PG(2, 11) and PG(2, 13) is resolved. The largest maximal length of an (n, 3)-arc is 21 and 23, respectively. Also the classification of the examples of maximal order is given. This result is proved by an exhaustive search method which utilizes geometric relationships between arcs of species 2 and 3 ([AC7]) and which uses projective equivalence relationships of certain configurations. In [AC7] we obtain a lower bound on the maximal cardinality of an (m, r-1)-arc in the plane contained in an (n, r)-arc and determine the arcs of species 3 of large cardinality for q>=16. Some of those have maximal length under the additional hypothesis to contain arcs of fixed cardinality. Recently the packing problem for (n, k)-arcs has been resolved in PG(2, 16) as well ([AC23], [59]). As the difficulty of the problem is exponential in q we reached the solution by utilizing further geometric constraints concerning the structure of the solutions. This allows to prune the search tree in places which can be proved not to lead to a solution.
Those definitive results concerning the packing problem yield new bounds on the existence of NMDS codes in PG(2, q), q = 11,13,16 and have allowed us via extension methods to prove the non-existence of other related NMDS codes ([15],[59]). In particular new examples of NMDS-codes of maximal length have been obtained in [15]. Further new results concerning existence and classification of NMDS-codes have been obtained in [33] and [AC1] starting from classification results of (n, 3)-arcs. As special cases the classifications are obtained of all arcs of species 3 in PG(2, q); q = 7,8,9 in [14]. If we increase the dimension and make use of extension methods alone for the classification of NMDS-codes, the calculation times become unmanageable: as a first step to reduce the time we used the method to alternate between extension and classification methods. In order to reduce the computational complexity of the classification problem we introduced a preclassification step based on a readily computable invariant of the code [AC2]: this method allows us to obtain a partition of the search space in parts each of which contains just one or a small number of equivalence classes. The subsequent step of the classification turns out to have a linear cost in the applications. Moreover it has turned out to be advantageous for classification purposes to use a characterization of AMDS codes (those are more general than NMDS-codes in the sense that there are no restrictions on the dual code) as given in [AC4]. This has enabled us to determine the maximal of an NMDS-code in GF(q), q=7,8,9 for each dimension ([33]). Those results have resolved numerous cases which had been open in the specialized databases http://www.win.tue.nl/~aeb/voorlincod.html (not more updated), http://mint.sbg.ac.at and http://www-ma4.upc.es/~simeon/codebounds.html.
A code is called optimal with respect to the Griesmer bound if n>(k-2)q+k. In [41] we give a detailed analysis of the (n, k)-arcs consisting of point orbits under the action of a power of the Singer cycle in PG(2, q): in certain cases the Griesmer bound is reached.


2.3. CAPS IN PG(r,q), r>2

As indicated earlier, Segre had emphasized the importance of the determination of the spectrum of the cardinalities of complete caps in PG(r,q) and in particular of the extreme values, from the point of view of the applications. For example the complete caps of minimal sizes give rise to quasi-perfect codes which for fixed redundancy have density as close as possible to the perfect codes.
Before the mid-1990s only two infinite families of complete caps had been constructed, both in projective 4-spaces: one by B. Segre (1959) and the second by G. Tallini (1964). In 1996 in [4] we described an inductive construction of complete caps in projective spaces of arbitrary dimension over fields of characteristic 2. These caps have size q^{r/2} in even dimension and 3q^{(r-1)/2} in odd dimension. In particular in dimension 4 those cardinalities are smaller than the cardinalities that had been known before (of order 2q^2).
What definitive results on the minimal cardinality of complete caps are concerned, my research concentrated on dimensions 3 and 4; in 1998 the problem was resolved for q=5 and q=3 which had been the first open cases. In order to solve the problem in PG(3,7) and in PG(4,4) detailed theoretical considerations were necessary in order to reduce the calculation times for an exhaustive search. In particolar the result in PG(3,7), including the classification of the minimal examples has been possible only by using group-theoretical considerations as well as graph-theoretic Ramsey theory concerning the relation between the existence question of certain linear codes and of the arcs in question. In fact the classification of the arcs has made possible to exclude those linear codes. In [49] the non-existence of certain linear codes has been particularly useful for the introduction of certain constraints on the hyperplane sections of complete caps in PG(4,4).
In [3], [11] e [12] geometric mechanisms are used for the construction of small complete arcs in PG(3,q), q odd, which in certain cases yield arcs of minimal cardinality.
In [5], [7], [8], [24], [AC12], [42] e [49] we address the problem of the spectra of complete caps in various dimensions.

In [47] we improve upon the inductive method of [4] by broadening the class of plane caps which can be used as a basis of the inductive construction: the main result is the determination for q>8 and for each dimension r>2 of a new upper bound for the minimal cardinality of complete caps. In the same paper the notion of a sum-point of a complete plane curve is introduced. This notion was helpful in the establishment of the new upper bound for q<= 2^15.

What the maximum cardinality of complete caps is concerned, new upper bounds are obtained [42]. In dimension 3 the maximum cardinality is known, so the emphasis is on the second largest cardinality: in [44] e [AC8] we construct a new infinite family of complete caps of size (q^{2}+q+8)/2, q odd prime, q=2(mod 3), q>=11. This yields a new lower bound on the second cardinality. A slight variant of this construction method yields in case q=5 one of the two complete 20-caps of the second largest cardinality.


2.4. SATURATING SETS

The r-saturating sets of a projective space generalize the concept of a complete cap. Technically speaking a subset S of PG(r, q) is called s-saturating if s is the minimum integer such that for every point P of PG(r, q) there exists a subspace generated by some s + 1 points of S which contains P. In case s=1 this is equivalent to the fact that the bisecants of S cover the ambient space. Of particular interest is the construction of minimal saturating sets (not containing proper subsets which are saturating) of small cardinality, in view of the links to covering codes and to other area of Combinatorics like the design of experiments and the degree/diameter- problem in graph theory.
The problem of determining the minimal cardinality of saturating sets turns out to be more complex than the case of complete caps due to the fact that there are less geometric constraints.
The best known general upper bound on the minimal cardinality concerns 1-saturating sets in the plane and is derived from statistical estimations: this bound is however quite far from a lower bound which is obtained by a simple counting argument. What exact values of the minimal cardinality in the plane is concerned, in [20] and [AC21] the problem has been resolved for q<=23, including the classification of the examples. The complete spectrum of examples has been determined for q<=13: in [22] estimations are obtained for certain extremal parameters pertaining to minimal saturating sets in  PG(n, q). A concept of saturating density is introduced which allows to obtain new lower bounds on the smallest minimal saturating sets. In the same paper we also determine the largest cardinality of a minimal 1-saturating set. Constructions of minimal 1-saturating sets in PG(r, 2) are described in [AC3] and [36]. Some of these constructions yield sets of a particularly symmetric structure in terms of internal lines, polygons and orbits of the symmetry groups. As an example we studied an 11-set in PG(4, 2) named central pentagon. Starting from examples of those constructions infinite families of 1-saturating sets in spaces of growing dimension are obtained. In small dimensions the complete classification of the 1-saturating minimal sets is given.
To an s-saturating n-set in PG(r, q) is canonically associated an [n,n-(r+1)]_R covering code of covering radius R = s+1: In [23] new constructions are given for infinite families of covering codes with R = 2; 3 and growing dimension. The basis for those inductive constructions consists of the saturating sets constructed in the previous articles. The interest of those constructions stems from the fact that codes with low covering density are obtained. In [AC6] and [31] the concept of a locally optimal covering code is introduced. It corresponds to the minimality property of saturating sets. Constructions of infinite families of such codes are given. Classification results are derived for those codes in ”small geometries” (for small values of the codimension and of q), using algorithms written in Magma which perform a search in width, utilizing projective equivalence and preclassification steps based on invariants like for example the minimum distance. New upper and lower bounds on the minimal and maximal lengths are obtained. In [AC13], [AC14] and [50] we continue the study of r-saturating sets in spaces of dimension exceeding 3. A new instrument has been the utilization of the notion of a strong blocking set which is a specialization of the classical notion of a blocking set of species n. In particular we obtain, by use of a concatenation construction, new infinite families of saturating sets of small cardinality in arbitrary dimension which yield q-ary covering codes of asymptotic covering density higher than had been known before.
In [AC25] a concept of a multiple s-saturating set is introduced. It has been proved that in the linear case those are the geometric counterpart of the multiply covering codes with MCF. One application of those codes is in the football pool problem where the aim is to reduce the previsions needed to multiply a victory. For such MCF codes we introduce a concept of multiple saturating density as a quality characteristic: in order to save resources one aims at those with lowest possible density. In geometric language this comes down to multiple saturating sets of minimum length.
In the same work constructions are obtained of multiple 1-saturating sets of small cardinality which improve on an upper bound which can be derived via probabilistic results on classical 1-saturating sets. This paper belongs in the context of current research where recently general construction procedures of saturating multiple sets have been obtained using concatenation and translation caps.


2.5. CYCLIC MODEL of PG(r,q) and ARCS

Studying the additive inverse of lines in the cyclic model of PG(r,q), in [16] we generalized a result of M.Hall which states that in the cyclic model of the projective Galois plane the additive inverse of a line is a conic; in particular we showed that for the additive inverse of a line there are two possibilities: either it is a (q + 1)-arc or it is contained in a hyperplane. In dimension 3 the result is stronger as for the second possibility we obtain a line. This result has then been generalized to spaces of dimension larger than 3.


2.6. SPREADS E BLOCKING SETS

The problem of the determination of maximal partial spreads in PG(3, q) (families of mutually skew lines such that any line in the space PG(3, q) intersects at least one line of the family non-trivially) has been considered. Originally this problem has been studied by Dale Mesner in 1967. The currently best known upper bound is due to Aart Blokhuis as a consequence of his results on blocking sets. In his study of the case PG(3, 7) O. Heden proved that this upper bound cannot be improved upon in general. The first open case for odd q was q = 9 with possible cardinalities 75 and 76. In [40] the second possibility has been ruled out: in a preliminary paper [38] the corresponding blocking sets in PG(2, 9) have been determined and classified. This has been used as point of departure for the geometric study of the possible holes (points in the ambient space not covered by a line of the spread). The result has been obtained invoking a theorem by Blokhuis-Metsch concerning the weights of affine subspaces. In [L1] with analogous approach, also the first possibility has been ruled out, solving definitively the problem.

In the line of research concerning blocking sets we studied partitions of PG(2, q); specifically we aimed at determining the maximal number of disjoint minimal blocking sets. In particular it has been shown in [35] that a recent conjecture of M. Kriesell according which planes of non-square order q contain q/2 disjoint blocking sets may not be best possible. In fact we found 5 disjoint minimal blocking sets for q = 8.

In parallel we studied blocking sets in Mobius planes. There are no general constructions and only a small number of known bounds: L. Lovasz has proved that each Mobius plane of order q contains a blocking set of order less than 3qlogq whereas Bruen and Rothschild proved that for q>=9 the cardinalities are greater than 2q-1. In [P27] we determined the spectrum of the cardinalities for small values of q and showed that for each natural number C there is a constant q(C) for each Mobius plane of order q>q(C) the cardinality of a blocking set has at least 2q + C points.