next up previous
Next: Computing the adjunction divisor Up: Computational Aspects Previous: Computational Aspects

Computing the places of $ C$

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

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:

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

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

    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$,

    Finally, the closed affine singular points are given by the set of ideals

    \begin{displaymath}\hspace*{0.2cm} SING_{aff}:= \left\{ \langle \phi_{i,j},
...,, \: k=1,\dots,s_i\,,\\

    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]$,

    $\displaystyle \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

    $\displaystyle 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:

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.

next up previous
Next: Computing the adjunction divisor Up: Computational Aspects Previous: Computational Aspects
Christoph Lossen