@comment -*-texinfo-*-
@comment this file contains the mathematical background of Singular

@c The following directives are necessary for proper compilation
@c with emacs (C-c C-e C-r).  Please keep it as it is.  Since it
@c is wrapped in `@ignore' and `@end ignore' it does not harm `tex' or
@c `makeinfo' but is a great help in editing this file (emacs
@c ignores the `@ignore').
@ignore
%**start
\input texinfo.tex
@setfilename math.info
@node Top, Mathematical background
@menu
* General concepts::
@end menu
@node Mathematical background, SINGULAR libraries, Examples, Top
@chapter Mathematical background
%**end
@end ignore

This chapter introduces some of the mathematical notions and definitions used
throughout the manual. It is mostly a collection of the
most prominent definitions and properties. For details, please, refer to
articles or text books (see @ref{References}).

@menu
* Standard bases::
* Hilbert function::
* Syzygies and resolutions::
* Characteristic sets::
* Gauss-Manin connection::
* Toric ideals and integer programming::
@ifset withplural
* Non-commutative algebra  ::
@end ifset
* Decoding codes with Groebner bases::
* References::
@end menu
@c ---------------------------------------------------------------------------
@node Standard bases, Hilbert function, ,Mathematical background
@section Standard bases
@cindex Standard bases

@subheading Definition
@tex
Let $R = \hbox{Loc}_< K[\underline{x}]$ and let $I$ be a submodule of $R^r$.
Note that for r=1 this means that $I$ is an ideal in $R$.
Denote by $L(I)$ the submodule of $R^r$ generated by the leading terms
of elements of $I$, i.e. by $\left\{L(f) \mid f \in I\right\}$.
Then $f_1, \ldots, f_s \in I$ is called a {\bf standard basis} of $I$
if $L(f_1), \ldots, L(f_s)$ generate $L(I)$.

A standard basis is {\bf minimal} if $\forall i: (f_1,..,f_{i-1},f_{i+1},..,f_s) \neq I$.

A minimal standard basis is {\bf completely reduced} if $\forall i: {\tt reduce}(f_i,(f_1,..,f_{i-1},f_{i+1},..,f_s))=f_i$
@end tex
@ifinfo
Let R = Loc K[x] and let I be a submodule of R^r.
Denote by L(I) the submodule of R^r generated by the leading terms
of elements in I, i.e. by @{ L(f) | f in I@}.
Then f_1, @dots{}, f_s in I is called a @strong{standard basis} of I
if L(f_1), @dots{}, L(f_s) generate L(I).

A standard basis is @strong{minimal} if for for all i: (f_1,..,f_(i-1),f_(i+1),..,f_s) != I.

A minimal standard basis is @strong{completely reduced} if for all i: @code{reduce(f_i,(f_1,..,f_(i-1),f_(i+1),..,f_s))=f_i}.
@end ifinfo

@subheading Properties
@table @asis
@item normal form:
@cindex normal form
@tex
A function $\hbox{NF} : R^r \times \{G \mid G\ \hbox{ a standard
basis}\} \to R^r, (p,G) \mapsto \hbox{NF}(p|G)$, is called a {\bf normal
form} if for any $p \in R^r$ and any standard basis $G$ the following
holds: if $\hbox{NF}(p|G) \not= 0$ then $L(g)$ does not divide
$L(\hbox{NF}(p|G))$ for all $g \in G$.
The function may also be applied to any generating set of an ideal:
the result is then not uniquely defined.

\noindent
$\hbox{NF}(p|G)$ is called a {\bf normal form of} $p$ {\bf with
respect to} $G$
@end tex
@ifinfo
A function NF : R^r x @{G | G a standard basis@} -> R^r, (p,G) ->
NF(p|G), is called a @strong{normal form} if for any p in R^r and any
standard basis G the following holds: if NF(p|G) <> 0 then L(g) does not
divide L(NF(p|G)) for all g in G.
The function may also be applied to any generating set of an ideal:
the result is then not uniquely defined.

@*NF(p|G) is called a @strong{normal form} of p with respect to G
@end ifinfo
@item ideal membership:
@cindex Ideal membership
@tex
For a standard basis $G$ of $I$ the following holds:
$f \in I$ if and only if $\hbox{NF}(f,G) = 0$.
@end tex
@ifinfo
For a standard basis G of I the following holds:
f in I if and only if NF(f,G) = 0.
@end ifinfo
@item Hilbert function:
@tex
Let \hbox{$I \subseteq K[\underline{x}]^r$} be a homogeneous module, then the Hilbert function
$H_I$ of $I$ (see below)
and the Hilbert function $H_{L(I)}$ of the leading module $L(I)$
coincide, i.e.,
$H_I=H_{L(I)}$.
@end tex
@ifinfo
Let I in K[x]^r be a homogeneous ideal, then the Hilbert function H_I of I
and the Hilbert function H_L(I) of the leading ideal L(I) coincide.
@end ifinfo
@end table

@c ---------------------------------------------------------------------------
@node Hilbert function, Syzygies and resolutions, Standard bases, Mathematical background
@section Hilbert function
@cindex Hilbert function
@cindex Hilbert series
@tex
Let M $=\bigoplus_{i\in Z} M_i$ be a graded module over $K[x_1,..,x_n]$ with
respect to weights $(w_1,..w_n)$.
The {\bf Hilbert function} of $M$, $H_M$, is defined (on the integers) by
$$H_M(k) :=dim_K M_k.$$
The {\bf Hilbert-Poincare series}  of $M$ is the power series
$$\hbox{HP}_M(t) :=\sum_{i=-\infty}^\infty
H_M(i)t^i=\sum_{i=-\infty}^\infty dim_K M_i \cdot t^i.$$
It turns out that $\hbox{HP}_M(t)$ can be written in two useful ways
for weights $(1,..,1)$:
$$\hbox{HP}_M(t)={Q(t)\over (1-t)^n}={P(t)\over (1-t)^{dim(M)}}$$
where $Q(t)$ and $P(t)$ are polynomials in ${\bf Z}[t]$.
$Q(t)$ is called the {\bf first Hilbert series},
and $P(t)$ the {\bf second Hilbert series}.
If \hbox{$P(t)=\sum_{k=0}^N a_k t^k$}, and \hbox{$d = dim(M)$},
then \hbox{$H_M(s)=\sum_{k=0}^N a_k$ ${d+s-k-1}\choose{d-1}$}
(the {\bf Hilbert polynomial}) for $s \ge N$.
@end tex
@ifinfo
Let M =(+) M_i be a graded module over K[x_1,...,x_n] with
respect to weights (w_1,..w_n).
The Hilbert function of M H_M is defined by
@display
H_M(k)=dim_K M_k.
@end display
The Hilbert-Poincare series  of M is the power series
@display
HP_M(t)=sum_i dim_K (M_i)*t^i.
@end display
It turns out that HP_M(t) can be written in two useful ways
for weights $(1,..,1)$:
@display
H_M(t)=Q(t)/(1-t)^n=P(t)/(1-t)^dim(M).
@end display
where Q(t) and P(t) are polynomials in Z[t].
Q(t) is called the first Hilbert series, and P(t) the second Hilbert series.
If P(t)=sum_(k=0)^N a_k t^k, and d=dim(M),
then
@display
H_M(s)=sum_(k=0)^N a_k binomial(d+s-k-1,d-1) (the Hilbert polynomial)
@end display
for s >= N.
@end ifinfo
@*
@*
@tex
Generalizing this to quasihomogeneous modules we get
$$\hbox{HP}_M(t)={Q(t)\over {\Pi_{i=1}^n(1-t^{w_i})}}$$
where $Q(t)$ is a polynomial in ${\bf Z}[t]$.
$Q(t)$ is called the {\bf first (weighted) Hilbert series} of M.
@end tex
@ifinfo
Generalizing these to quasihomogeneous modules we get
@display
H_M(t)=Q(t)/Prod((1-t)^(w_i)).
@end display
where Q(t) is a polynomial in Z[t].
Q(t) is called the first (weighted) Hilbert series of M.
@end ifinfo

@c ---------------------------------------------------------------------------
@node Syzygies and resolutions, Characteristic sets, Hilbert function, Mathematical background
@section Syzygies and resolutions
@cindex Syzygies and resolutions

@subheading Syzygies
@tex
Let $R$ be a quotient of $\hbox{Loc}_< K[\underline{x}]$ and let \hbox{$I=(g_1, ..., g_s)$} be a submodule of $R^r$.
Then the {\bf module of syzygies} (or {\bf 1st syzygy module}, {\bf module of relations}) of $I$, syz($I$), is defined to be the kernel of the map \hbox{$R^s \rightarrow R^r,\; \sum_{i=1}^s w_ie_i \mapsto \sum_{i=1}^s w_ig_i$.}
@end tex
@ifinfo
Let R be a quotient of Loc K[x] and let I=(g_1, ..., g_s) be a submodule
of R^r.
Then the @strong{module of syzygies} (or @strong{1st syzygy module}, @strong{module of relations}) of I, syz(I), is defined to be the kernel of the map
@display
R^s --> R^r,
w_1*e_1 + ... + w_s*e_s -> w_1*g_1 + ... + w_s*g_s.
@end display
@end ifinfo

The @strong{k-th syzygy module} is defined inductively to be the module
of syzygies of the
@tex
$(k-1)$-st
@end tex
@ifinfo
(k-1)-st
@end ifinfo
syzygy module.

@tex
Note, that the syzygy modules of $I$ depend on a choice of generators $g_1, ..., g_s$.
But one can show that they depend on $I$ uniquely up to direct summands.
@end tex
@ifinfo
Note, that the syzygy modules of I depend on a choice of generators g_1, ..., g_s.
But one can show that they depend on I uniquely up to direct summands.
@end ifinfo

@table @code
@item @strong{Example:}
@smallexample
@c example
  ring R= 0,(u,v,x,y,z),dp;
  ideal i=ux, vx, uy, vy;
  print(syz(i));
@c example
@end smallexample
@end table

@subheading Free resolutions
@tex
Let $I=(g_1,...,g_s)\subseteq R^r$ and $M= R^r/I$.
A {\bf free resolution of $M$} is a long exact sequence
$$...\longrightarrow F_2 \buildrel{A_2}\over{\longrightarrow} F_1
\buildrel{A_1}\over{\longrightarrow} F_0\longrightarrow M\longrightarrow
0,$$
@end tex
@ifinfo
Let I=(g_1,...,g_s) in R^r and M=R^r/I.  A free resolution of M is a
long exact sequence
@display
...--> F2 --A2-> F1 --A1-> F0-->M-->0,
@end display
@end ifinfo
@*where the columns of the matrix
@tex
$A_1$
@end tex
@ifinfo
A_1
@end ifinfo
generate @math{I}. Note that resolutions need not to be finite (i.e., of
finite length). The Hilbert Syzygy Theorem states that for
@tex
$R=\hbox{Loc}_< K[\underline{x}]$
@end tex
@ifinfo
R=Loc K[x]
@end ifinfo
there exists a ("minimal") resolution of length not exceeding the number of
variables.

@table @code
@item @strong{Example:}
@smallexample
@c example
  ring R= 0,(u,v,x,y,z),dp;
  ideal I = ux, vx, uy, vy;
  resolution resI = mres(I,0); resI;
  // The matrix A_1 is given by
  print(matrix(resI[1]));
  // We see that the columns of A_1 generate I.
  // The matrix A_2 is given by
  print(matrix(resI[3]));
@c example
@end smallexample
@end table

@subheading Betti numbers and regularity
@cindex Betti number
@cindex regularity
@tex
Let $R$ be a graded ring (e.g., $R = \hbox{Loc}_< K[\underline{x}]$) and
let $I \subset R^r$ be a graded submodule. Let
$$
  R^r = \bigoplus_a R\cdot e_{a,0} \buildrel A_1 \over \longleftarrow
        \bigoplus_a R\cdot e_{a,1} \longleftarrow \ldots \longleftarrow
        \bigoplus_a R\cdot e_{a,n} \longleftarrow 0
$$
be a minimal free resolution of $R^r/I$ considered with homogeneous maps
of degree 0. Then the {\bf graded Betti number} $b_{i,j}$ of $R^r/I$ is
the minimal number of generators $e_{a,j}$ in degree $i+j$ of the $j$-th
syzygy module of $R^r/I$ (i.e., the $(j-1)$-st syzygy module of
$I$). Note that, by definition, the $0$-th syzygy module of $R^r/I$ is $R^r$
and the 1st syzygy module of $R^r/I$ is $I$.
@end tex
@ifinfo
Let R be a graded ring (e.g., R = K[x]) and let I in R^r be a graded
submodule. Let
@display
R^r = (+) K[x]e(a,0) <--- (+) K[x]e(a,1)
            <--- @dots{} <--- (+) K[x]e(a,n) <--- 0
@end display
be a minimal free resolution of R^n/I considered with homogeneous maps
of degree 0. Then the @strong{graded Betti number} b_i,j of R^r/I is the
minimal number of generators e_a,j in degree i+j of the j-th syzygy
module of R^r/I (i.e., the (j-1)-st syzygy module of I). Note, that by
definition the 0th syzygy module of R^r/I is R^r and the 1st syzygy module
of R^r/I is I.
@end ifinfo

The @strong{regularity} of @math{I} is the smallest integer @math{s} such that
@tex
$$
    \hbox{deg}(e_{a,j}) \le s+j-1 \quad \hbox{for all $j$.}
$$
@end tex
@ifinfo
@display
deg(e(a,j)) <= s+j-1    for all j.
@end display
@end ifinfo

@table @code
@item @strong{Example:}
@smallexample
@c example
  ring R= 0,(u,v,x,y,z),dp;
  ideal I = ux, vx, uy, vy;
  resolution resI = mres(I,0); resI;
  // the betti number:
  print(betti(resI), "betti");
  // the regularity:
  regularity(resI);
@c example
@end smallexample
@end table
@c ---------------------------------------------------------------------------
@node Characteristic sets, Gauss-Manin connection, Syzygies and resolutions, Mathematical background
@section Characteristic sets
@cindex Characteristic sets

@tex
Let $<$ be the lexicographical ordering on $R=K[x_1,...,x_n]$ with $x_1
< ... < x_n$.
For $f \in R$ let lvar($f$) (the leading variable of $f$) be the largest
variable in $f$,
i.e., if $f=a_s(x_1,...,x_{k-1})x_k^s+...+a_0(x_1,...,x_{k-1})$ for some
$k \leq n$ then lvar$(f)=x_k$.

Moreover, let
\hbox{ini}$(f):=a_s(x_1,...,x_{k-1})$. The pseudoremainder
$r=\hbox{prem}(g,f)$ of $g$ with respect to $f$ is
defined by the equality $\hbox{ini}(f)^a\cdot g = qf+r$ with
$\hbox{deg}_{lvar(f)}(r)<\hbox{deg}_{lvar(f)}(f)$ and $a$
minimal.

A set $T=\{f_1,...,f_r\} \subset R$ is called triangular if
$\hbox{lvar}(f_1)<...<\hbox{lvar}(f_r)$. Moreover, let $ U \subset T $,
then $(T,U)$ is called a triangular system, if $T$ is a triangular set
such that $\hbox{ini}(T)$ does not vanish on $V(T) \setminus V(U)
(=:V(T\setminus U))$.

$T$ is called irreducible if for every $i$ there are no
$d_i$,$f_i'$,$f_i''$ such that
$$   \hbox{lvar}(d_i)<\hbox{lvar}(f_i) =
\hbox{lvar}(f_i')=\hbox{lvar}(f_i''),$$
$$   0 \not\in \hbox{prem}(\{ d_i, \hbox{ini}(f_i'),
\hbox{ini}(f_i'')\},\{ f_1,...,f_{i-1}\}),$$
$$\hbox{prem}(d_if_i-f_i'f_i'',\{f_1,...,f_{i-1}\})=0.$$
Furthermore, $(T,U)$ is called irreducible if $T$ is irreducible.

The main result on triangular sets is the following: Let
$G=\{g_1,...,g_s\} \subset R$, then there are irreducible triangular sets $T_1,...,T_l$
such that $V(G)=\bigcup_{i=1}^{l}(V(T_i\setminus I_i))$
where $I_i=\{\hbox{ini}(f) \mid f \in T_i \}$. Such a set
$\{T_1,...,T_l\}$ is called an {\bf irreducible characteristic series} of
the ideal $(G)$.
@end tex
@ifinfo
Let > be the lexicographical ordering on R=K[x_1,...,x_n] with x_1<...<x_n .
For f in R let lvar(f) (the leading variable of f) be the largest
variable in lead(f) (the leading term of f with respect to >),
i.e., if f=a_s(x_1,...,x_(k-1))x_k^s+...+a_0(x_1,...,x_(k-1)) for some
k<=n then lvar(f)=x_k.

Moreover, let ini(f):=a_s(x_1,...,x_(k-1)). The pseudoremainder
r=prem(g,f) of g with respect to f is defined by ini(f)^a*g=q*f+r with
the property deg_(lvar(f))(r)<deg_(lvar(f))(f), @code{a} minimal.

A set T=@{f_1,...,f_r@} in R is called triangular if lvar(f_1)<...<lvar(f_r).

(T,U) is called a triangular system, if U is a subset of T and
if T is a triangular set such that ini(T)
does not vanish on the zero-set of T \ zero-set of U
( =:Zero(T\U)).

T is called irreducible if for every i there are no d_i,f_i',f_i'' with
the property:
@display
lvar(d_i)<lvar(f_i)
lvar(f_i')=lvar(f_i'')=lvar(f_i)
0 not in prem(@{ d_i, ini(f_i'), ini(f_i'')@},@{ f_1,...,f_(i-1)@})
@end display
such that prem(d_i*f_i-f_i'*f_i'',@{f_1,...,f_(i-1)@})=0.

(T,U) is called irreducible if T is irreducible.

The main result on triangular sets is the following: let
G=@{g_1,...,g_s@} then there are irreducible triangular sets T_1,...,T_l
such that Zero(G)=Union(i=1,...,l: Zero(T_i\I_i)) where I_i=@{ini(f), f
in T_i @}.  Such a set @{T_1,...,T_l@} is called an @strong{irreducibel
characteristic series} of the ideal (G).
@end ifinfo

@table @code
@item @strong{Example:}
@smallexample
@c example
  ring R= 0,(x,y,z,u),dp;
  ideal i=-3zu+y2-2x+2,
          -3x2u-4yz-6xz+2y2+3xy,
          -3z2u-xu+y2z+y;
  print(char_series(i));
@c example
@end smallexample
@end table
@c ---------------------------------------------------------------------------
@node Gauss-Manin connection, Toric ideals and integer programming, Characteristic sets, Mathematical background
@section Gauss-Manin connection
@cindex Gauss-Manin connection

@c the following text contain too much math code, so there are
@c tex and info versions of it. It end just before the introducing text
@c to the first example.

@tex
Let $f\colon(C^{n+1},0)\rightarrow(C,0)$ be a complex isolated hypersurface singularity given by a polynomial with algebraic coefficients which we also denote by $f$.
Let $O=C[x_0,\ldots,x_n]_{(x_0,\ldots,x_n)}$ be the local ring at the origin and $J_f$ the Jacobian ideal of $f$.

A {\bf Milnor representative} of $f$ defines a differentiable fibre bundle over the punctured disc with fibres of homotopy type of $\mu$ $n$-spheres.
The $n$-th cohomology bundle is a flat vector bundle of dimension $n$ and carries a natural flat connection with covariant derivative $\partial_t$.
The {\bf monodromy operator} is the action of a positively oriented generator of the fundamental group of the punctured disc on the Milnor fibre.
Sections in the cohomology bundle of {\bf moderate growth} at $0$ form a regular $D=C\{t\}[\partial_t]$-module $G$, the {\bf Gauss-Manin connection}.

By integrating along flat multivalued families of cycles, one can consider fibrewise global holomorphic differential forms as elements of $G$.
This factors through an inclusion of the {\bf Brieskorn lattice} $H'':=\Omega^{n+1}_{C^{n+1},0}/df\wedge d\Omega^{n-1}_{C^{n+1},0}$ in $G$.

The $D$-module structure defines the {\bf V-filtration} $V$ on $G$ by $V^\alpha:=\sum_{\beta\ge\alpha}C\{t\}ker(t\partial_t-\beta)^{n+1}$.
The Brieskorn lattice defines the {\bf Hodge filtration} $F$ on $G$ by $F_k=\partial_t^kH''$ which comes from the {\bf mixed Hodge structure} on the Milnor fibre.
Note that $F_{-1}=H'$.

The induced V-filtration on the Brieskorn lattice determines the {\bf singularity spectrum} $Sp$ by $Sp(\alpha):=\dim_CGr_V^\alpha Gr^F_0G$.
The spectrum consists of $\mu$ rational numbers $\alpha_1,\dots,\alpha_\mu$ such that $e^{2\pi i\alpha_1},\dots,e^{2\pi i\alpha_\mu}$ are the eigenvalues of the monodromy.
These {\bf spectral numbers} lie in the open interval $(-1,n)$, symmetric about the midpoint $(n-1)/2$.

The spectrum is constant under $\mu$-constant deformations and has the following semicontinuity property:
The number of spectral numbers in an interval $(a,a+1]$ of all singularities of a small deformation of $f$ is greater than or equal to that of f in this interval.
For semiquasihomogeneous singularities, this also holds for intervals of the form $(a,a+1)$.

Two given isolated singularities $f$ and $g$ determine two spectra and from these spectra we get an integer.
This integer is the maximal positive integer $k$ such that the semicontinuity holds for the spectrum of $f$ and $k$ times the spectrum of $g$.
These numbers give bounds for the maximal number of isolated singularities of a specific type on a hypersurface $X\subset{P}^n$ of degree $d$:
such a hypersurface has a smooth hyperplane section, and the complement is a small deformation of a cone over this hyperplane section.
The cone itself being a $\mu$-constant deformation of $x_0^d+\dots+x_n^d=0$, the singularities are bounded by the spectrum of $x_0^d+\dots+x_n^d$.

Using the library {\tt gmssing.lib} one can compute the {\bf monodromy}, the V-fitration on $H''/H'$, and the spectrum.
@end tex

@ifinfo
Let f:(C^(n+1),0)--->(C,0) be a complex isolated hypersurface singularity given by a polynomial with algebraic coefficients which we also denote by f.
Let O=C[x_0,...,x_n]_(x_0,...,x_n) be the local ring at the origin and J_f the Jacobian ideal of f.

A @strong{Milnor representative} of f defines a differentiable fibre bundle over the punctured disc with fibres of homotopy type of mu n-spheres.
The n-th cohomology bundle is a flat vector bundle of dimension n and carries a natural flat connection with covariant derivative d_t.
The @strong{monodromy operator} is the action of a positively oriented generator of the fundamental group of the puctured disc on the Milnor fibre.
Sections in the cohomology bundle of @strong{moderate growth} at 0 form a regular D=C@{t@}[d_t]-module G, the @strong{Gauss-Manin connection}.

By integrating along flat multivalued families of cycles, one can consider fibrewise global holomorphic differential forms as elements of G.
This factors through an inclusion of the @strong{Brieskorn lattice} H'':=Omega^(n+1)_(C^(n+1),0)/df*dOmega^(n-1)_(C^(n+1),0) in G.

The D-module structure defines the @strong{V-filtration} V on G by V^a:=sum_(b>=a)C@{t@}ker(t*d_t-b)^(n+1).
The Brieskorn lattice defines the @strong{Hodge filtration} F on G by F_k=d_t^kH'' which comes from the @strong{mixed Hodge structure} on the Milnor fibre.
Note that F_(-1)=H'.

The induced V-filtration on the Brieskorn lattice determines the @strong{singularity spectrum} Sp by Sp(a):=dim_CGr_V^a Gr^F_0G.
The spectrum consists of mu rational numbers a_1,...,a_mu such that exp(2*pi*i*a_1),...,exp(2*pi*i*a_mu) are the eigenvalues of the monodromy.
These @strong{spectral numbers} lie in the open interval (-1,n), symmetric about the midpoint (n-1)/2.

The spectrum is constant under mu-constant deformations and has the following semicontinuity property:
The number of spectral numbers in an interval (a,a+1] of all singularities of a small deformation of f is greater or equal to that of f in this interval.
For semiquasihomogeneous singularities, this also holds for intervals of the form (a,a+1).

Two given isolated singularities f and g determine two spectra and from these spectra we get an integer.
This integer is the maximal positive integer k such that the semicontinuity holds for the spectrum of f and k times the spectrum of g.
These numbers give bounds for the maximal number of isolated singularities of a specific type on a hypersurface X in P^n of degree d:
Such a hypersurface has a smooth hyperplane section, and the complement is a small deformation of a cone over this hyperplane section.
The cone itself being a mu-constant deformation of x_0^d+...+x_n^d=0, the singularities are bounded by the spectrum of x_0^d+...+x_n^d.

Using the library @code{gmssing.lib} one can compute the @strong{monodromy}, the V-fitration on H''/H', and the spectrum.
@end ifinfo

Let us consider as an example @math{f=x^5+x^2y^2+y^5}.
First, we compute a matrix @math{M} such that
@tex
$\exp(2\pi iM)$
@end tex
@ifinfo
exp(-2*pi*i*M)
@end ifinfo
is a monodromy matrix of @math{f} and the Jordan normal form of @math{M}:
@smallexample
@c example
  LIB "mondromy.lib";
  ring R=0,(x,y),ds;
  poly f=x5+x2y2+y5;
  matrix M=monodromyB(f);
  print(M);
@c example
@end smallexample

Now, we compute the V-fitration on @math{H''/H'} and the spectrum:
@smallexample
@c example
  LIB "gmssing.lib";
  ring R=0,(x,y),ds;
  poly f=x5+x2y2+y5;
  list l=vfilt(f);
  print(l[1]); // spectral numbers
  print(l[2]); // corresponding multiplicities
  print(l[3]); // vector space of i-th graded part
  print(l[4]); // monomial vector space basis of H''/s*H''
  print(l[5]); // standard basis of Jacobian ideal
@c example
@end smallexample
Here @code{l[1]} contains the spectral numbers, @code{l[2]} the corresponding multiplicities, @code{l[3]} a @math{C}-basis of the V-filtration on @math{H''/H'} in terms of the monomial basis of
@tex
$O/J_f\cong H''/H'$
@end tex
@ifinfo
O/J_f~=H''/H'
@end ifinfo
in @code{l[4]} (separated by degree).

@tex
If the principal part of $f$ is $C$-nondegenerate, one can compute the spectrum using the library {\tt spectrum.lib}.
In this case, the V-filtration on $H''$ coincides with the Newton-filtration on $H''$ which allows to compute the spectrum more efficiently.
@end tex

@ifinfo
If the principal part of f is C-nondegenerate, one can compute the spectrum using the library @code{spectrum.lib}.
In this case, the V-filtration on H'' coincides with the Newton-filtration on H'' which allows to compute the spectrum more efficiently.
@end ifinfo

Let us calculate one specific example, the maximal number
of triple points of type
@tex
$\tilde{E}_6$ on a surface $X\subset{P}^3$
@end tex
@ifinfo
E~_6 on a surface X in P^3
@end ifinfo
of degree seven.
This calculation can be done over the rationals.
We choose a local ordering on @math{Q[x,y,z]}. Here we take the
negative degree lexicographical ordering, in @sc{Singular} denoted by @code{ds}:

@smallexample
@c example
ring r=0,(x,y,z),ds;
LIB "spectrum.lib";
poly f=x^7+y^7+z^7;
list s1=spectrumnd( f );
s1;
@c example
@end smallexample

The command @code{spectrumnd(f)} computes the spectrum of @math{f} and
returns a list with six entries:
The Milnor number
@tex
$\mu(f)$, the geometric genus $p_g(f)$
@end tex
@ifinfo
mu(f), the geometric genus p_g(f)
@end ifinfo
and the number of different spectrum numbers.
The other three entries are of type @code{intvec}.
They contain the numerators, denominators and
multiplicities of the spectrum numbers. So
@tex
$x^7+y^7+z^7=0$
@end tex
@ifinfo
x^7+y^7+z^7=0
@end ifinfo
has Milnor number 216 and geometrical
genus 35. Its spectrum consists of the 16 different rationals
@*
@tex
${3 \over 7}, {4 \over 7}, {5 \over 7}, {6 \over 7}, {1 \over 1},
{8 \over 7}, {9 \over 7}, {10 \over 7}, {11 \over 7}, {12 \over 7},
{13 \over 7}, {2 \over 1}, {15 \over 7}, {16 \over 7}, {17 \over 7},
{18 \over 7}$
@end tex
@ifinfo
3/7, 4/7, 5/7, 6/7, 1, 8/7, 9/7, 10/7, 11/7, 12/7, 13/7, 2, 15/7, 16/7, 17/7,
18/7
@end ifinfo
@*appearing with multiplicities
@*1,3,6,10,15,21,25,27,27,25,21,15,10,6,3,1.

@tex
The singularities of type $\tilde{E}_6$ form a
$\mu$-constant one parameter family given by
$x^3+y^3+z^3+\lambda xyz=0,\quad \lambda^3\neq-27$.
@end tex
@ifinfo
The singularities of type E~_6 form a
mu-constant one parameter family given by
x^3+y^3+z^3+lambda xyz=0, lambda^3 <> -27.
@end ifinfo
Therefore they have all the same spectrum, which we compute
for
@tex
$x^3+y^3+z^3$.
@end tex
@ifinfo
@math{x^3+y^3+z^3}.
@end ifinfo

@smallexample
poly g=x^3+y^3+z^3;
list s2=spectrumnd(g);
s2;
@expansion{} [1]:
@expansion{}    8
@expansion{} [2]:
@expansion{}    1
@expansion{} [3]:
@expansion{}    4
@expansion{} [4]:
@expansion{}    1,4,5,2
@expansion{} [5]:
@expansion{}    1,3,3,1
@expansion{} [6]:
@expansion{}    1,3,3,1
@end smallexample
Evaluating semicontinuity is very easy:
@smallexample
semicont(s1,s2);
@expansion{} 18
@end smallexample

This tells us that there are at most 18 singularities of type
@tex
$\tilde{E}_6$ on a septic in $P^3$. But $x^7+y^7+z^7$
@end tex
@ifinfo
E~_6 on a septic in P^3. But x^7+y^7+z^7
@end ifinfo
is semiquasihomogeneous (sqh), so we can also apply the stronger
form of semicontinuity:

@smallexample
semicontsqh(s1,s2);
@expansion{} 17
@end smallexample

So in fact a septic has at most 17 triple points of type
@tex
$\tilde{E}_6$.
@end tex
@ifinfo
E~_6.
@end ifinfo

Note that @code{spectrumnd(f)} works only if @math{f} has a nondegenerate
principal part. In fact @code{spectrumnd} will detect a degenerate
principal part in many cases and print out an error message.
However if it is known in advance that @math{f} has nondegenerate
principal part, then the spectrum may be computed much faster
using @code{spectrumnd(f,1)}.

@c ---------------------------------------------------------------------------
@ifclear withplural
@node Toric ideals and integer programming, Decoding codes with Groebner bases, Gauss-Manin connection, Mathematical background
@end ifclear

@ifset withplural
@node Toric ideals and integer programming, Non-commutative algebra , Gauss-Manin connection, Mathematical background
@end ifset

@section Toric ideals and integer programming
@cindex Toric ideals and integer programming
@include ti_ip.tex



@ifset withplural

@c ---------------------------------------------------------------------------
@node Non-commutative algebra, Decoding codes with Groebner bases, Toric ideals and integer programming, Mathematical background

@section Non-commutative algebra
@cindex  Non-commutative algebra

See @ref{Mathematical background (plural)}, @ref{Mathematical background (letterplace)}.
@end ifset

@c ---------------------------------------------------------------------------

@ifclear withplural
@node Decoding codes with Groebner bases, References, Toric ideals and integer programming, Mathematical background
@end ifclear

@ifset withplural
@c ---------------------------------------------------------------------------
@node Decoding codes with Groebner bases, References, Non-commutative algebra, Mathematical background
@end ifset

@section Decoding codes with Groebner bases
@cindex  Decoding codes with Groebner bases
@include decodegb.tex

@node References, ,Decoding codes with Groebner bases, Mathematical background



@section References
@cindex References



The Centre for Computer Algebra Kaiserslautern publishes a series of preprints
which are electronically available at
@code{https://www.singular.uni-kl.de/reports}.
Other sources to check are @code{http://symbolicnet.org/},
@code{http://www-sop.inria.fr/galaad/},... and the following list of books.

@ifset withplural
For references on non-commutative algebras and algorithms, see @ref{References (plural)}.
@end ifset

@subheading Text books on computational algebraic geometry
@itemize @bullet

@item
Adams, W.; Loustaunau, P.: An Introduction to Gr@"obner Bases. Providence, RI,
AMS, 1996

@item
Becker, T.; Weisspfenning, V.:
Gr@"obner Bases - A Computational Approach to Commutative Algebra. Springer, 1993

@item
Cohen, H.:
A Course in Computational Algebraic Number Theory,
Springer, 1995

@item
Cox, D.; Little, J.; O'Shea, D.:
Ideals, Varieties and Algorithms. Springer, 1996

@item
Cox, D.; Little, J.; O'Shea, D.:
Using Algebraic Geometry. Springer, 1998

@item
Eisenbud, D.: Commutative Algebra with a View Toward Algebraic Geometry.
Springer, 1995

@item
Greuel, G.-M.; Pfister, G.:
A Singular Introduction to Commutative Algebra. Springer, 2002

@item
Mishra, B.: Algorithmic Algebra, Texts and Monographs in Computer Science.
Springer, 1993
@item
Sturmfels, B.: Algorithms in Invariant Theory. Springer 1993

@item
Vasconcelos, W.: Computational Methods in Commutative Algebra and Algebraic
Geometry. Springer, 1998
@end itemize

@subheading Descriptions of algorithms
@itemize @bullet
@item
Bareiss, E.:
Sylvester's identity and multistep integer-preserving Gaussian elimination.
Math. Comp. 22 (1968), 565-578

@item
Campillo, A.: Algebroid curves in positive characteristic. SLN 813, 1980

@item
Chou, S.:
Mechanical Geometry Theorem Proving.
D.Reidel Publishing Company, 1988

@item
Decker, W.; Greuel, G.-M.; Pfister, G.:
Primary decomposition: algorithms and
comparisons.  Preprint, Univ. Kaiserslautern, 1998.
To appear in: Greuel, G.-M.; Matzat, B. H.; Hiss, G. (Eds.),
Algorithmic Algebra and Number Theory. Springer Verlag, Heidelberg, 1998

@item
Decker, W.; Greuel, G.-M.; de Jong, T.; Pfister, G.:
The normalisation: a new algorithm,
implementation and comparisons. Preprint, Univ. Kaiserslautern, 1998

@item
Decker, W.; Heydtmann, A.; Schreyer, F. O.: Generating a Noetherian Normalization of
the Invariant Ring of a Finite Group, 1997, to appear in Journal of
Symbolic Computation

@item
@tex
Faug\`ere,
@end tex
@ifinfo
Faugere,
@end ifinfo
J. C.; Gianni, P.; Lazard, D.; Mora, T.: Efficient computation
of zero-dimensional
Gr@"obner bases by change of ordering. Journal of Symbolic Computation, 1989

@item
Gr@"abe, H.-G.: On factorized Gr@"obner bases, Univ. Leipzig, Inst. f@"ur
Informatik, 1994

@item
Grassmann, H.; Greuel, G.-M.; Martin, B.; Neumann,
W.; Pfister, G.; Pohl, W.; Sch@"onemann, H.; Siebert, T.:  On an
implementation of standard bases and syzygies in  @sc{Singular}.
Proceedings of the Workshop  Computational Methods in Lie theory in AAECC (1995)

@item
Greuel, G.-M.; Pfister, G.:
Advances and improvements in the theory of standard bases and
syzygies. Arch. d. Math. 63(1995)

@item
Kemper; Generating Invariant Rings of Finite Groups over Arbitrary
Fields. 1996, to appear in Journal of Symbolic Computation

@item
Kemper and Steel: Some Algorithms in Invariant Theory of Finite Groups. 1997

@item
Lee, H.R.; Saunders, B.D.: Fraction Free Gaussian Elimination for
Sparse Matrices. Journal of Symbolic Computation (1995) 19, 393-402

@item
Sch@"onemann, H.:
Algorithms in @sc{Singular},
Reports on Computer Algebra 2(1996), Kaiserslautern

@item
Siebert, T.:
On strategies and implementations for computations of free resolutions.
Reports on Computer Algebra 8(1996), Kaiserslautern

@item
Wang, D.:
Characteristic Sets and Zero Structure of Polynomial Sets.
Lecture Notes, RISC Linz, 1989
@end itemize