\documentstyle[12pt,fleqn]{article}
\language0 
\title{Caps and Arcs in $PG(n,q)$, $n \geq 3$}

\author{Stefano Marcugini, Alfredo Milani, Fernanda Pambianco
\thanks{%
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\`{a}`` sottoprogetto ``Calcolo simbolico`` and by GNSAGA.}}

\date{Dipartimento di Matematica,  Universit\`a di Perugia,\\
      06123 Perugia, Italy}
                 

\begin{document}
\maketitle

\section{Definition of the environment}

\smallskip 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.

\smallskip

F:=GF(q);

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

npoints := 1;

for i in [1..n] do

\quad npoints := npoints + q\symbol{94}i;

end for; \ \ \ \ \ \ \ \ \ \ \ \ 

// npoints represents the number of points of PG(n,q)

\smallskip

\section{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.

\subsection{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.

\smallskip

LineThrough := function (p1,p2);

\quad p1 := Normalise(V!p1);

\quad p2 := Normalise(V!p2);

\quad if p1 eq p2 then

\quad \quad return \{\};

\quad else

\quad \quad line1 := \{\};

\quad \quad for elf in F do

\quad \quad \quad p3 := Normalize(p1+elf * p2);

\quad \quad \quad line1 := line1 join \{p3\};

\quad \quad end for;

\quad \quad line1 := line1 join \{p2\};

\quad \quad return line1;

\quad end if;

end function;

\subsection{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.

\smallskip

The function uses the function \textit{LineThrough} previously defined.

\medskip

EdIsCap := function (pointsset)

// returns: \ 0 if pointsset is not a cap

//\quad \quad \quad \quad 1 if pointsset is an incomplete cap

//\quad \quad \quad \quad 2 if pointsset is a complete cap

\quad pointsset := \{V!pp : pp in pointsset\};

\quad SP := \{\};

\quad lp := \{@ pp : pp in pointsset@\};

\quad cardcap := \#pointsset;

\quad for p1 in [1..cardcap] do

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

\quad \quad \quad r := LineThrough(lp[p1],lp[p2]);

\quad \quad \quad if r eq \{\} then

\quad \quad \quad \quad return 0;

\quad \quad \quad else

\quad \quad \quad \quad tan := \#(r meet pointsset);

\quad \quad \quad \quad if tan gt 2 then

\quad \quad \quad \quad \quad return 0;

\quad \quad \quad \quad else

\quad \quad \quad \quad \quad if tan eq 2 then

\quad \quad \quad \quad \quad \quad SP :=SP join r;

\quad \quad \quad \quad \quad end if;

\quad \quad \quad \quad end if;

\quad \quad \quad end if;

\quad \quad end for;

\quad end for;

\quad if \#SP eq npoints then

\quad \quad return 2;

\quad else

\quad \quad return 1;

\quad end if;

end function;

\section{Arcs in PG(3,q)\protect\smallskip }

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.

\smallskip

\subsection{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.

\smallskip The function uses the function \textit{LineThrough} previously
defined.

\smallskip

PlaneThrough := function (p1,p2,p3);

\quad p1 := Normalise(V!p1);

\quad p2 := Normalise(V!p2);

\quad \quad if p1 eq p2 then

\ \quad \quad \quad return \{\};

\quad \quad else

\quad \quad \quad p3 := Normalise(V!p3);

\quad \quad \quad line1 := LineThrough(p1,p2);

\quad \quad \quad if p3 in line1 then

\quad \quad \quad \quad return \{\};

\quad \quad \quad else

\quad \quad \quad \quad plane1 := \{\};

\quad \quad \quad \quad for pr in line1 do

\quad \quad \quad \quad \quad rr := LineThrough(p3,pr);

\quad \quad \quad \quad \quad plane1 := plane1 join rr;

\quad \quad \quad \quad end for;

\quad \quad \quad \quad plane1 := plane1 join line1;

\quad \quad \quad \quad return plane1;

\quad \quad \quad end if;

\quad \quad end if;

end function;

\smallskip

\smallskip

\subsection{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.

\smallskip

The function uses the functions \textit{LineThrough} and \textit{PlaneThrough%
} previously defined.

\smallskip

D3IsArc := function (pointsset)

// returns: \ 0 if pointsset is not a arc

//\quad \quad \quad \quad 1 if pointsset is an incomplete arc

//\quad \quad \quad \quad 2 if pointsset is a complete arc

\quad pointsset := \{V!pp : pp in pointsset\};

\quad SP := \{\};

\quad lp := \{@ pp : pp in pointsset@\};

\quad cardcap := \#pointsset;

\quad for p1 in [1..cardcap] do

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

\quad \quad \quad for p3 in [p2+1..cardcap] do

\quad \quad \quad \quad pp := PlaneThrough(lp[p1],lp[p2],lp[p3]);

\quad \quad \quad \quad if pp eq \{\} then

\quad \quad \quad \quad \quad return 0;

\quad \quad \quad \quad else

\quad \quad \quad \quad \quad tan := \#(pp meet pointsset);

\quad \quad \quad \quad \quad if tan gt 3 then

\quad \quad \quad \quad \quad \quad return 0;

\quad \quad \quad \quad \quad else

\quad \quad \quad \quad \quad \quad if tan eq 3 then

\quad \quad \quad \quad \quad \quad \quad SP :=SP join pp;

\quad \quad \quad \quad \quad \quad end if;

\quad \quad \quad \quad \quad end if;

\quad \quad \quad \quad end if;

\quad \quad \quad end for;

\quad \quad end for;

\quad end for;

\quad if \#SP eq npoints then

\quad \quad return 2;

\quad else

\quad \quad return 1;

\quad end if;

end function;

\smallskip

\smallskip

\section{Projective equivalence of sets of points of PG(n,q)\protect%
\smallskip}

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 $\geq 2$ and q is a prime power and let P$\Gamma $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.

\smallskip

if IsPrime(q) then

\quad Pgl,Pts:= PGL(V);

else

\quad Pgl,Pts:= PGammaL(V);

end if;

\smallskip

\smallskip Pgl is the group PGL(n,q)\ if q is prime, P$\Gamma $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).

\bigskip \bigskip

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

\smallskip

IndicesToVectors := function (indicesset)

\quad return \{Pts[i] : i in indicesset\};

end function;

\bigskip \bigskip

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

VectorsToIndices := function (setvectors)

\quad setvectors := \{Normalise(V!vector) : vector in setvectors\};

\quad return \{i : i in [1..\#Pts] $\mid$ Pts[i] in setvectors\};

end function;

\bigskip \bigskip

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

\smallskip

IsConjugate(Pgl,VectorsToIndices(S1), VectorsToIndices(S2));

\smallskip

The funcion returns true if the sets S1 and S2 are equivalent, false
otherwise. 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.


\begin{thebibliography}{9}
\bibitem{1}  W. Bosma, S. Cannon, Handbook of MAGMA\ Functions, University
of Sydney, 1996.\smallskip 

\bibitem{2}  W. Bosma, S. Cannon, C. Playoust, A. Steel, Solving problems
with MAGMA, University of Sydney, 1996.

\bibitem{5}  G. Faina, F. Pambianco, On the spectrum of the values k for
which a complete k-cap exists, J. Geom. 62 (1998) 84-98

\bibitem{3}  J.W.P. Hirschfeld, Projective geometries over finite fields
(Claredon Press, Oxford, 1979).

\bibitem{4}  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.
\end{thebibliography}

\end{document}
