Computing the places of $C$

A place $Q$ of $C$ is represented by a triple, consisting of

• the closed point $[P]\in C$ corresponding to $Q$,
• the degree $k_Q$ of the place (that is, the minimal degree of a field extension defining $Q$) and
• a symbolic Hamburger-Noether expression HN for the local branch corresponding to $Q$ (defined over a primitive algebraic field extension $\mathbf{F}\subset \mathbf{F}(a)$ of degree $k_Q$).

Recall that $[P]\in C$ denotes the formal sum of a point $P\in C$ with its conjugates. Affine closed points will be represented by a defining (triangular) ideal $I=\langle \phi,\psi\rangle\subset \mathbf{F}[x,y]$, while closed points at infinity are usually stored in form of a homogeneous polynomial $\Phi\in \mathbf{F}[X,Y]$ (the defining prime factor of $F(X,Y,0)$).

Note that the conjugates of a place $Q$ are given by the triples $([P],k_Q,$ HN$')$, where HN$'$ runs through the conjugates of HN. Hence, when computing the closed places of $C$, we can restrict ourselves to computing one representing place for each. We apply the following algorithm:

Input

Squarefree homogeneous polynomial $F\in \mathbf{F}[X,Y,Z]_d$,
degree bound $k\in \mathbf{N}$.

Output

List $L$ of all closed singular places and all closed non-singular places up to degree $k$ of the plane curve $C$ defined by $F$.

1. Affine singular points. Let $f(x,y):=F(x,y,1)$ and $I:=\langle f,f_x,f_y \rangle$ the Tjurina ideal of $f$. Compute a triangular system for $I$, that is, a system of triangular bases $T_i$ such that $V(I) = V(T_1) \cup \ldots \cup V(T_s)$.

   Here, by a triangular basis one denotes a reduced lexicographical Gröbner basis of the form $T= \left\{ \phi, \psi\right\}$ with $\phi\in \mathbf{F}[y]$ a monic polynomial in $y$ and $\psi=y^b+\sum_{i<b} \psi_i(x)y^i\in \mathbf{F}[x,y]$. Triangular systems can be computed effectively, basically by two different methods, one due to Lazard [27,7], the other due to Möller [31]. Choose any of these methods to compute a triangular system for $I$, $T_i=\bigl\{\phi_i,\psi_i\bigr\}$, $i=1,\dots,s$. For each $i$,

   • compute a prime factorization of $\phi_i$ in $\mathbf{F}[y]$,
     $$\phi_i =\phi_{i,1}\cdot \ldots\cdot \phi_{i,r_i} \in \mathbf{F}[y]\,;$$

   • for $j=1,\dots,r_i$, let $\mathbf{F}(a_{i,j})=\mathbf{F}[y]/\langle \phi_{i,j}\rangle$ be the primitive field extension defined by the irreducible polynomial $\phi_{i,j}$. Compute a prime factorization of $\psi_i$ in $\mathbf{F}(a_{i,j})[x,y]$,
     $$\psi_i =\psi_{i,1}\cdot \ldots\cdot \psi_{i,s_i}\in \mathbf{F}(a_{i,j})[x,y]\,.$$

   Finally, the closed affine singular points are given by the set of ideals
   $$\hspace*{0.2cm} SING_{aff}:= \left\{ \langle \phi_{i,j}, \ov... ...,, \: k=1,\dots,s_i\,,\\ i=1,\dots,s \end{array}\right\}\!,$$
   where $\overline{\psi}_{i,j}$ is the image of $\psi_{i,j}$ when substituting the parameter $a_{i,j}$ by $y$.

   
   

2. Points at infinity. Let $f_{\infty}(x):=F(x,1,0)$ and compute a prime factorization of the polynomial $f_{\infty}\in \mathbf{F}[x]$,

   $$\hspace*{1.2cm} f_\infty=f_{\infty,1}\cdot \ldots \cdot f_{\infty,d'}\in \mathbf{F}[x]\,, \qquad d'\!\leq d\,.$$ (4)

   
   
   Let $a_j\in \overline{\mathbf{F}}$ be a root of $f_{\infty,j}$ and define
   $$PTS_{\infty}:= \left\{\, \big[(a_j\!:\!\!\:1\!\!\::\!\!\:0)\big] \;\big\vert\; j=1,\dots, d' \,\right\},$$
   where $\big[(a_j\!:\!\!\:1\!\!\::\!\!\:0)\big]$ denotes the formal sum of the point $(a_j\!:\!\!\:1\!\!\::\!\!\:0)$ (defined over $\overline{\mathbf{F}}$) with its conjugates. (It is represented by $f_{\infty,j}$.)

   We denote by $SING_{\infty}\!\subset PTS_{\infty}$ the subset of closed singular points. To check whether a point $\big[(a_j\!:\!\!\:1\!\!\::\!\!\:0)\big]$ is singular or not, one has to check whether $F_X(a_j,1,0)=F_Z(a_j,1,0)=0$ (these computations can be performed over the finite field extension $F(a_j)=F[x]/\langle f_{\infty,j}\rangle$).

   Finally, consider the (closed) point $P=(1\!\!\::\!\!\:0\!\!\::\!\!\:0)$: if $F(1,0,0)=0$ then $P$ has to be added to $PTS_{\infty}$; if, additionally, $F_Y(1,0,0)$ and $F_Z(1,0,0)$ vanish then it has to be added to $SING_{\infty}$, too.

   The sets $PTS_{\infty}$ (resp. $SING_{\infty}$) are the sets of closed (singular) points at infinity.

   
   

3. Affine singular places. To each closed affine singular point $\left[P\right]$ given by a (triangular) ideal $\langle \phi,\psi\rangle\in SING_{aff}$ we compute the corresponding places in form of a system of symbolic Hamburger-Noether expressions for the respective germ $(C,P)$ (defined over $\overline{\mathbf{F}}$). More precisely, a closed place over $\left[P\right]$ is the formal sum of a place $Q$ described by one of the computed sHNE with its conjugates.

   The computation of the symbolic Hamburger-Noether expressions has to be performed in the local ring $\mathbf{F}(a)[x,y]_P$ where $\mathbf{F}\subset \mathbf{F}(a)$ is a primitive field extension (of degree $k_P\!=\deg_y(\phi)\deg_x(\psi)$) such that $\phi,\psi$ decompose into linear factors. Note that during the computation of a sHNE further field extensions might be necessary.

   
   

4. Singular places at infinity. To each closed singular point $\left[P\right]$ in $SING_{\infty}$ we compute a system of sHNE for the local germ $(C,P)$ (defined over $\overline{\mathbf{F}}$). To be precise, if $P=(a_j\!:\!\!\:1\!\!\::\!\!\:0)$ then we compute a system of sHNE for $F(x\!\!\:+\!\!\:a_j,1,z)$ in $\mathbf{F}(a_j)[x,z]_{\langle x,z\rangle}$; if $P=(1\!\!\::\!\!\:0\!\!\::\!\!\:0)$ then the system of sHNE is computed for $F(1,y,z)$ in $\mathbf{F}[y,z]_{\langle y,z\rangle}$.

   
   

5. Non-singular affine closed points up to degree $k$. For each $1\leq \ell \leq k$ do the following:
   • let $Q:=p^{\ell}$ and set $I:=\langle f,\,x^Q\!-x,\,y^Q\!-y \rangle$.
   • Proceed as in Step 1 to obtain a set of (triangular) ideals $PTS_{aff}$ corresponding to the set of closed points defined over $\mathbf{F}_Q$.
   • For all non-singular $[P]\in PTS_{aff}$ (given by $\langle \phi,\psi\rangle\subset \mathbf{F}[x,y]$) compute the degree $k_P\!=\deg_y(\phi)\deg_x(\psi)$). If $k_P=\ell$ then compute the corresponding closed place (that is, a sHNE for the germ $(C,P)$) and add it to the list $L$ of closed places.

Remark 2.10   It is interesting to notice that triangular sets have mainly been used for numerical purpose, since they allow a fast and stable numerical solving of polynomial systems (cf. [27,31,13]), and this has been the reason for implementing it in SINGULAR. Several experiments have shown that they behave also superior against other methods to represent closed points over finite fields.