\documentclass[centertags,12pt]{amsart}
\usepackage{latexsym}
\usepackage{amssymb}
%
% page layout
%
\textwidth = 15.50cm
\textheight = 22.00cm
\oddsidemargin = 0.12in
\evensidemargin = 0.12in
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 2pt minus 1pt} 
\renewcommand{\baselinestretch}{1.1}
\numberwithin{equation}{section}
\makeatletter
\renewcommand{\subsection}{\@startsection
{subsection}{2}{0mm}{\baselineskip}{-0.25cm}
{\normalfont\normalsize\bf}}
\makeatother
%
% theoremlike environments
%
\newtheorem{theorem}{Theorem}[section]
\newtheorem{deff}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{scholium}[theorem]{Scholium}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{claim}[theorem]{Claim}
%
% definitions
%
\def\F{\mathbb F}
\def\P{\mathbb P}
\def\N{\mathbb N}
\def\Z{\mathbb Z}
\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cD{\mathcal D}
\def\cE{\mathcal E}
\def\cF{\mathcal F}
\def\cK{\mathcal K}
\def\cL{\mathcal L}
\def\cM{\mathcal M}
\def\cV{\mathcal V}
\def\cW{\mathcal W}
\def\cX{\mathcal X}
\def\l{\ell}
\def\aut{{\rm Aut}}
\def\deg{{\rm deg}}
\def\det{{\rm det}}
\def\div{{\rm div}}
\def\Div{{\rm Div}}
\def\dim{{\rm dim}}
\def\supp{{\rm Supp}}
%\def\fq1{\mathbb F_q}
\def\fq13{\mathbb F_{q^3}}
\def\frx{{\rm Fr}_{\mathcal X}}
%
\sloppy
%
\begin{document}
\author[Massimo Giulietti]{Massimo Giulietti}\thanks{The research was
supported 
by Italian MURST progetto 40\% {\em Strutture Geometriche, Combinatoria e 
loro applicazioni}, by CNR Progetto strategico {\em Applicazioni della
matematica per la tecnologia e la societ\'a} sottoprogetto 
{\em Calcolo Simbolico} and by GNSAGA}
\title{\bf Computational Solutions of Some Problems about Algebraic
Curves}

\maketitle
\begin{abstract}
We report some MAGMA instructions about 
algebraic curves defined over a finite field.
The sections below are logically independent; in the former
we treat some global properties, while the latter is about local 
properties.
\end{abstract}
\section{Singular Rational Points}                                         
Let $K$ be the finite field of order $q=p^r$ and let $F$ be its algebraic closure.
A plane algebraic curve $C$ of $PG(2,F)$ defined over $K$ is the projective algebraic 
set defined by the principal ideal generated by a homogeneous polynomial $f$ of
$K[x_{0}, x_{1} , x_{2}]$ (briefly $C=V(f)$). 
Let $C(K)$ be the set of the $K$-rational points of $C$, $\mathcal{S}$ the set of
its singular points and ${\mathcal S}(K)$ the set of its singular $K$-rational points.
The following instructions define the environment.
\begin{verbatim}
  K:=GF(q);
  P,V,L:=ProjectivePlane(q);
  W:=VectorSpace(K,3);  
  R<x0,x1,x2>:=PolynomialRing(K,3,"lex");
\end{verbatim}
Suppose that \begin{tt} f \end{tt} is defined as a homogeneous element of
\begin{tt} R \end{tt}.

\subsection{How many $K$-rational points?}

We count the number of $K$-rational points of $C$ and we call it 
\begin{tt} NRatPts \end{tt}.

\begin{verbatim} 
  NRatPts:=0;
  for pt in V do
    if (Evaluate(f,[pt[1],pt[2],pt[3]]) eq 0) then
      NRatPts:=NRatPts+1;
    end if;
  end for;
\end{verbatim}

\subsection{What are the singular $K$-rational points?}

We find the set of the singular $K$-rational points of $C$ and we call it 
\begin{tt} RatSgPt \end{tt}; we put these points in a sequence called
\begin{tt} RSP \end{tt}.

\begin{verbatim}
  f0:=Derivative(f,x0);
  f1:=Derivative(f,x1);
  f2:=Derivative(f,x2);
  RatSgPt:={};
  for pt in V do
    if (Evaluate(f0,[pt[1],pt[2],pt[3]]) eq 0) and
                 (Evaluate(f1,[pt[1],pt[2],pt[3]]) eq 0) and
                 (Evaluate(f2,[pt[1],pt[2],pt[3]]) eq 0) then
       RatSgPt:=RatSgPt join {pt};
    end if;
  end for;
  RSP:=SetToSequence(RatSgPt);
\end{verbatim}

\subsection{Do there exist singular non-$K$-rational points?}

The boolean variable \begin{tt} AreAllSg \end{tt} will indicate whether 
all the singular points are $K$-rational or not.
\subsubsection{Case 1: ${\mathcal S}(K)= \emptyset $}
We establish whether  ${\mathcal S}= \emptyset$ or not, i. e. whether
$V(M)= \emptyset$ or not, where
$M$ is the ideal of $F[x_{0},x_{1},x_{2}]$ generated by the derivatives of $f$.
We use Hilbert's Nullstellensatz.

\begin{verbatim}
  M:=ideal<R|f0,f1,f2>;
  if #RSP eq 0 then
     BasM:=GroebnerBasis(M);
     B1:=false;
     for g in BasM do
       B1:=B1 or (Evaluate(LeadingTerm(g),[1,0,0]) ne 0);
     end for;
     B2:=false;
     for g in BasM do
       B2:=B2 or (Evaluate(LeadingTerm(g),[0,1,0]) ne 0);
     end for;
     B3:=false;
     for g in BasM do
       B3:=B3 or (Evaluate(LeadingTerm(g),[0,0,1]) ne 0);
     end for;
     AreAllSg:=B1 and B2 and B3;
   end if;  
\end{verbatim}
\subsubsection{Case 2: ${\mathcal S}(K)\neq \emptyset $}
We establish whether ${\mathcal S} \subseteq {\mathcal S}(K)$ or not. 
Observe that ${\mathcal S}(K)= V(J)$ and $I({\mathcal S}(K))=J$, where
$J:=\bigcap_{P \in {\mathcal S}(K)} J_{P}$ and
\[ 
J_{P}:=
\left\{ \begin{array}{ll}
 <a_{0}x_{1}-a_{1}x_{0}, a_{0}x_{2}-a_{2}x_{0}> ,&  se\:\:a_{0}\neq 0 \\
 <a_{1}x_{0}-a_{0}x_{1}, a_{1}x_{2}-a_{2}x_{1}> ,&  se\:\:a_{1}\neq 0
,\: a_{0}=0 \\
 <a_{2}x_{0}-a_{0}x_{2}, a_{2}x_{1}-a_{1}x_{2}> ,&  se\:\:a_{2}\neq 0 
,\:a_{0}=0 ,\: a_{1}=0 \end{array} \right. ,
\]
($P=[a_{0}, a_{1}, a_{2}]$). 
So ${\mathcal S} \subseteq {\mathcal S}(K) \Leftrightarrow
V(M) \subseteq V(J) \Leftrightarrow I(V(J))\subseteq I(V(M))
\Leftrightarrow J \subseteq \sqrt{M} $ by Hilbert's Nullstellensatz.
The following instructions determine $J$; we construct a procedure 
\begin{tt} Intersect \end{tt} which compute the intersection between two 
ideals by using Groebner Basis (see \cite{CO}).

\begin{verbatim}
   T<t,y0,y1,y2>:=PolynomialRing(K,4,"lex");
   im:=hom<R->T|y0,y1,y2>; 
   imin:=hom<T->R|1,x0,x1,x2>;

   procedure Intersect(J1,J2,~J1meetJ2);
    Jt:={T|};
    for a in J1 do
      Jt:=Jt join {t*im(a)};
    end for;
    for a in J2 do
      Jt:=Jt join {(1-t)*im(a)};
    end for;
    Jtt:=SetToSequence(Jt);  
    JJ:=ideal<T|Jtt>;
    G:=GroebnerBasis(JJ);
    J1meetJ2:={R|};
    for g in G do
      if Evaluate(LeadingTerm(g),[0,1,1,1]) ne 0 then
        J1meetJ2:=J1meetJ2 join {R!imin(g)};
      end if;
    end for;
   end procedure;

  if #RSP gt 0 then
    J:=[R|1];
    JmeetL:={R|}
    for P in RSP do
      if P[1] ne 0 then
        l1:=(P[1]*x1-P[2]*x0); 
        l2:=(P[1]*x2-P[3]*x0); 
      end if;
      if (P[1] eq 0) and (P[2] ne 0) then
        l1:=(P[2]*x0-P[1]*x1); 
        l2:=(P[2]*x2-P[3]*x1); 
      end if;
      if (P[1] eq 0) and (P[2] eq 0) then
        l1:=(P[3]*x0-P[1]*x2); 
        l2:=(P[3]*x1-P[2]*x2); 
      end if;
      L:=[R|l1,l2];
      Intersect(J,L,~JmeetL);
      J:=SetToSequence(JmeetL);
    end for;
\end{verbatim}

We finally establish whether $J \subseteq \sqrt{M}$.

\begin{verbatim}
    B4:=true;
    for h in J  do
      if not IsInRadical(h,M) then
        B4:=false;
        break;
      end if;
    end for;
    AreAllSg:=B4;
  end if;
\end{verbatim}

\section{Local Properties}
Let $K$ be the finite field of order $q=p^r$ and let $F$ be its algebraic closure.
A plane algebraic curve $C$ of $PG(2,F)$ defined over $K$ is the projective algebraic 
set defined by the principal ideal generated by a homogeneous polynomial $f$ of
$K[x_{0}, x_{1} , x_{2}]$ (briefly $C=V(f)$). 
Let $C(K)$ be the set of the $K$-rational points of $C$, $\mathcal{S}$ the set of
its singular points and ${\mathcal S}(K)$ the set of its singular $K$-rational points.
The following instructions define the environment.
\begin{verbatim}
  K:=GF(q);
  P,V,L:=ProjectivePlane(q);
  W:=VectorSpace(K,3);   
  R<x0,x1,x2>:=PolynomialRing(K,3,"lex");
\end{verbatim}
Suppose that \begin{tt} f \end{tt} is defined as a homogeneous element of
\begin{tt} R \end{tt}.

\subsection{What are the singular $K$-rational points?}

We find the set of the singular $K$-rational points of $C$ and we call it 
\begin{tt} RatSgPt \end{tt}; we put these points in a sequence called
\begin{tt} RSP \end{tt}.

\begin{verbatim}
  f0:=Derivative(f,x0);
  f1:=Derivative(f,x1);
  f2:=Derivative(f,x2);
  RatSgPt:={};
  for pt in V do
    if (Evaluate(f0,[pt[1],pt[2],pt[3]]) eq 0) and
                 (Evaluate(f1,[pt[1],pt[2],pt[3]]) eq 0) and
                 (Evaluate(f2,[pt[1],pt[2],pt[3]]) eq 0) then
       RatSgPt:=RatSgPt join {pt};
    end if;
  end for;
  RSP:=SetToSequence(RatSgPt);
\end{verbatim}

\subsection{The singular $K$-rational points are ordinary singularities or not?}

We will construct a procedure \begin{tt} Ordinary \end{tt}
which establish whether a singular $K$-rational point is an ordinary singularity or not.
Then we can easily say if all the $K$-rational points are ordinary:

\begin{verbatim}
  AreAllOrd:=true; 
  for sp in RSP do
    IsOrdSg:=false;
    Ordinary(sp,~IsOrdSg);
    if not IsOrdSg then 
      AreAllOrd:=false;
      break;
    end if;
  end for;
\end{verbatim}

\subsubsection{A singular $K$-rational poiont is an ordinary singularity or not?}

We write the procedure we promised:

 \begin{verbatim}
  procedure Ordinary(sp,~IsOrdSg);
 \end{verbatim}

First of all, we change the frame of reference bringing the point {\tt sp} to the origin
$[0,0,1]$; the new polynomial of $C$ will be called {\tt ff}.

 \begin{verbatim}
    if sp[1] ne 0 then
      ff:=Evaluate(f,[sp[1]*x0,x1+sp[2]*x0,x2+sp[3]*x0]);
    end if;
    if (sp[1] eq 0) and (sp[2] ne 0) then
      ff:=Evaluate(f,[x1,sp[2]*x0,x2+sp[3]*x0]);
    end if;
    if (sp[1] eq 0) and (sp[2] eq 0) then
      ff:=Evaluate(f,[x1,x2,sp[3]*x0]);
    end if;
 \end{verbatim}


We now find the monomials of {\tt ff} that have {\tt x0} to the highest power.
Their sum will be called {\tt ProdTg}.

 \begin{verbatim}
    ProdTg:=LeadingTerm(ff); 
    comolt:=Degree(prodtg,x0);
    fftemp:=ff-prodtg;
    B5:=true;
    while B5 do
      if Degree(LeadingTerm(fftemp),x0) eq comolt then
        ProdTg:=ProdTg+LeadingTerm(fftemp);
        fftemp:=fftemp-LeadingTerm(fftemp);
                                            else
        B7:=false; 
      end if;
    end while;
 \end{verbatim}

We finally write {\tt ProdTg} in an affine form and we check whether it has multiple 
factors or not.

\begin{verbatim}
    ProdTgAff:=Evaluate(ProdTg,[1,x1,x2]);
    B6:=false;
    d1:=Discriminant(ProdTgAff,x1);
    d2:=Discriminant(ProdTgAff,x2);
    if (d1 ne 0) and (d2 ne 0) then
      B6:=true;
    end if;
    IsOrdSg:=B6;
  end procedure;
\end{verbatim} 

   
\begin{thebibliography}{9999}
\bibitem{BC} W.BOSMA, S.CANNON,
             {\em Handbook of MAGMA Functions},
             University of Sydney, 1996. 
\bibitem{MA} W.BOSMA, S.CANNON, C.PLAYOUST, A.STEEL,
             {\em Solving problems with MAGMA},
             University of Sydney, 1996. 
\bibitem{CO} D. COX - J. LITTLE - D. O`SHEA, {\em Ideals, Varieties, and
Algorithms}, Springer-Verlag, 1991.
\bibitem{FU} W. FULTON, {\em Algebraic Curves}, Addison-Wesley, 1969.
\bibitem{HI} J.W.P. HIRSCHFELD, {\em Projective Geometries over Finite Fields}, Oxford, Clarendon Press, 1979.
\bibitem{SE} A. SEIDENBERG,
             {\em Elements of the theory of Algebraic Curves},
             Addison-Wesley, 1968.
\bibitem{ST} H. STICHTENOTH,
             {\em Algebraic Function Fields and Codes},
             Springer-Verlag, 1993.
\bibitem{WA} R.J. WALKER, {\em Algebraic curves}, Springer-Verlag, 1978. 
\end{thebibliography}
%\tableofcontents
\end{document}
\end{document}
