Caps and Arcs in P G(n, q), n ≥ 3

Stefano Marcugini, Alfredo Milani, Fernanda Pambianco ^{∗}

Dipartimento di Matematica, Università di Perugia, 06123 Perugia, Italy

1 Definition of the environment

Let F be the finite field of order q = p^{r}, let V be the vector space of dimension n+1 over the field F, let npoints be the number of points of PG(n,q), the Galois projective space of dimension n over the finite field of order q. The following instructions define the environment.

F:=GF(q);

V:=VectorSpace(F,n+1);

npoints := 1;

for i in [1..n] do

npoints := npoints + qˆ i; end for; // npoints represents the number of points of PG(n,q)

2 Caps in PG(n,q)

A cap of PG(n,q) is a set of points of PG(n,q) such that no three points are collinear. First we define a function to compute the line joining two points, then we use it to verify if a set of points of PG(n,q) is a cap.

∗This research is supported by Italian MURST progetto 40% “Efficienza di algoritmi e progetto di strutture informative“ and progetto 40% “Strutture Geometriche, Combinatoria e loro applicazioni“ and by CNR Progetto strategico “Applicazioni della matematica per la tecnologia e la società“ sottoprogetto “Calcolo simbolico“ and by GNSAGA.

2.1 What is the line joininig two points of PG(n,q)?

The following function returns the set of points belonging to the line joining two given points p1 and p2. The points p1 and p2 are represented as lists of n+1 coordinates. The function returns the empty set if p1 and p2 coincide.

LineThrough := function (p1,p2); p1 := Normalise(V!p1); p2 := Normalise(V!p2); if p1 eq p2 then

return {}; else

line1 := {}; for elf in F do

p3 := Normalize(p1+elf * p2); line1 := line1 join {p3};

end for;

line1 := line1 join {p2}; return line1;

end if; end function;

2.2 Is a set of points a cap of PG(n,q)?

The following function verifies if a set of points of PG(n,q) is a cap. Each point of the set is represented as a list of n+1 coordinates. The function returns:

0 if the set is not a cap;

1 if the set is an incomplete cap; 2 if the set is a complete cap.

The function uses the function LineThrough previously defined.

EdIsCap := function (pointsset) // returns: 0 if pointsset is not a cap // 1 if pointsset is an incomplete cap // 2 if pointsset is a complete cap

pointsset := {V!pp : pp in pointsset}; SP := {}; lp := {@ pp : pp in pointsset@}; cardcap := #pointsset; for p1 in [1..cardcap] do

for p2 in [p1+1..cardcap] do r := LineThrough(lp[p1],lp[p2]); if r eq {} then return 0;

else tan := #(r meet pointsset); if tan gt 2 then return 0;

else

if tan eq 2 then SP :=SP join r;

end if; end if; end if;

end for; end for; if #SP eq npoints then

return 2; else

return 1; end if;

end function;

3 Arcs in PG(3,q)

An arc of PG(3,q) is a set of points of PG(3,q) such that no three points belong to the same plane. First we define a function to compute the plane defined by tree points, then we use it to verify if a set of points of PG(3,q) is an arc.

3.1 What is the plane defined by three points of PG(n,q)?

The following function returns the set of points belonging to the plane defined by three given points p1, p2, p3. The points p1, p2, p3 are represented as lists of n+1 coordinates. If p1, p2, p3 are collinear the function returns the empty set.

The function uses the function LineThrough previously defined.

PlaneThrough := function (p1,p2,p3); p1 := Normalise(V!p1); p2 := Normalise(V!p2); if p1 eq p2 then return {};

else p3 := Normalise(V!p3); line1 := LineThrough(p1,p2); if p3 in line1 then return {};

else plane1 := {}; for pr in line1 do

rr := LineThrough(p3,pr); plane1 := plane1 join rr;

end for;

plane1 := plane1 join line1; return plane1;

end if; end if;

end function;

3.2 Is a set of points an arc of PG(3,q)?

The following function verifies if a set of points of PG(3,q) is an arc. Each point of the set is represented as a list of n+1 coordinates. The function returns:

0 if the set is not an arc;

1 if the set is an incomplete arc;

2 if the set is a complete arc. The function uses the functions LineThrough and PlaneThrough previ-

ously defined. D3IsArc := function (pointsset) // returns: 0 if pointsset is not a arc // 1 if pointsset is an incomplete arc // 2 if pointsset is a complete arc

pointsset := {V!pp : pp in pointsset}; SP := {}; lp := {@ pp : pp in pointsset@}; cardcap := #pointsset; for p1 in [1..cardcap] do

for p2 in [p1+1..cardcap] do

for p3 in [p2+1..cardcap] do pp := PlaneThrough(lp[p1],lp[p2],lp[p3]); if pp eq {} then return 0;

else tan := #(pp meet pointsset); if tan gt 3 then return 0;

else

if tan eq 3 then

SP :=SP join pp; end if; end if; end if; end for;

end for; end for; if #SP eq npoints then

return 2; else

return 1; end if;

end function;

4 Projective equivalence of sets of points of PG(n,q)

Let PGL(n, q) be the group corresponding to the action of GL(n,q) on the projective points of the n-dimensional vector space V over K = GF(q), where n ≥ 2 and q is a prime power and let PΓL(n,q) be the automorphism group of the projective general linear group PGL(n,q) where q is a prime power.

The following instructions define the environment. if IsPrime(q) then

Pgl,Pts:= PGL(V); else

Pgl,Pts:= PGammaL(V); end if;

Pgl is the group PGL(n,q) if q is prime, PΓL(n, q) otherwise, represented as a permutation group acting on the set of indices I = [1 .. npoints].

Pts is an indexed set giving the correspondence between the indeces of I and the points of PG(n,q).

The following function returns the set of points of PG(n,q) corresponding to a given set of indices in [1 .. npoints].

IndicesToVectors := function (indicesset)

return {Pts[i] : i in indicesset}; end function;

The following function returns the set of indices in [1 .. npoints] corresponding to a given set of points of PG(n,q).

VectorsToIndices := function (setvectors)

setvectors := {Normalise(V!vector) : vector in setvectors}; return {i : i in [1..#Pts] | Pts[i] in setvectors};

end function;

The following instruction verifies if two sets S1 and S2 of points of PG(n,q) are equivalent up to Pgl.

IsConjugate(Pgl,VectorsToIndices(S1), VectorsToIndices(S2)); The funcion returns true if the sets S1 and S2 are equivalent, false other-

wise. If the two sets are equivalent the function returns a second value: an element P of Pgl such that the image of S1 under P is equal to S2.

References

[1] W. Bosma, S. Cannon, Handbook of MAGMA Functions, University of Sydney, 1996.

[2] W. Bosma, S. Cannon, C. Playoust, A. Steel, Solving problems with MAGMA, University of Sydney, 1996.

[3] G. Faina, F. Pambianco, On the spectrum of the values k for which a complete k-cap exists, J. Geom. 62 (1998) 84-98

[4] J.W.P. Hirschfeld, Projective geometries over finite fields (Claredon Press, Oxford, 1979).

[5] J.W.P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces, J. Stat. Plann. Infer., to appear in the Proceedings of the Bose Memorial Conference, Colorado, June 7-11, 1995.