@comment -*-texinfo-*- @comment $Id: math.doc,v 1.44 1999-07-23 12:32:38 obachman Exp $ @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 some articles or text books (see @ref{References}). @menu * Standard bases:: * Hilbert function:: * Syzygies and resolutions:: * Characteristic sets:: * References:: @end menu @c --------------------------------------------------------------------------- @node Standard bases, Hilbert function, ,Mathematical background @section Standard bases @cindex Standard bases @subheading Definition @tex Let \hbox{$I \subseteq \hbox{Loc}_< K[\underline{x}]$} be an ideal and let $L(I)$ denote the ideal of $\hbox{Loc}_< K[\underline{x}]$ generated by the leading terms, i.e., by $\{L(f) \mid f \in I\}$. 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 the ideal \hbox{$L(I) \subset \hbox{Loc}_< K[\underline{x}]$}. @end tex @ifinfo Let I in Loc K[x] be an ideal and let L(I) denote the ideal of Loc K[x] generated by the leading terms, 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 the ideal L(I) in Loc K[x]. @end ifinfo @subheading Properties @table @asis @item normal form: @cindex Normal form @tex A function $\hbox{NF} : K[\underline{x}]^r \times \{G \mid G\ \hbox{ a standard basis}\} \to K[\underline{x}]^r, (p,G) \mapsto \hbox{NF}(p|G)$, is called a {\bf normal form} if for any $p \in K[\underline{x}]^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$. \noindent $\hbox{NF}(p|G)$ is called a {\bf normal form of} $p$ {\bf with respect to} $G$ (note that such a function is not unique). @end tex @ifinfo A function NF : K[x]^r x @{G | G a standard basis@} -> K[x]^r, (p,G) -> NF(p|G), is called a @strong{normal form} if for any p in K[x]^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. NF(p|G) is called a @strong{normal form} of p with respect to G (note that such a function is not unique). @end ifinfo @item ideal membership: @cindex Ideal membership @tex $f \in I$ if and only if $\hbox{NF}(f,\hbox{std}(I)) = 0$ (for $I \subseteq R$, resp.\ $I \subseteq R^r$). @end tex @ifinfo f in I if and only if NF(f,std(I)) = 0 (for I in R, resp.@: I in R^r). @end ifinfo @item Hilbert function: @tex Let \hbox{$I \subseteq K[\underline{x}]^r$} be a homogeneous ideal, then the Hilbert function $H_I$ of $I$ (see below) and the Hilbert function $H_{L(I)}$ of the leading ideal $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 M_i$ be a graded module over $K[x_1,..,x_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: $$\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]. The Hilbert function of M H_M is defined by H_M(k)=dim_K M_k.@* The Hilbert-Poincare series of M is the power series HP_M(t)=sum_i dim_K (M_i)*t^i.@* It turns out that HP_M(t) can be written in two useful ways: H_M(t)=Q(t)/(1-t)^n=P(t)/(1-t)^dim(M). 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 H_M(s)=sum_(k=0)^N a_k binomial(d+s-k-1,d-1) (the Hilbert polynomial) for s >= N. @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 \hbox{$I=(g_1, ..., g_s) \subseteq K[\underline{x}]^r$}. Then, the {\bf module of syzygies} of $I$, syz($I$), is defined to be the kernel of the map \hbox{$K[\underline{x}]^s \rightarrow K[\underline{x}]^r, \sum_{i=1}^s w_ie_i \mapsto \sum_{i=1}^s w_ig_i$.} @end tex @ifinfo Let I=(g_1, ..., g_s) in K[x]^r.@* Then, the @strong{module of syzygies} of I, syz(I), is defined to be the kernel of K[x]^s @expansion{} K[x]^r, sum w_i*e_i @expansion{} sum w_i*g_i. @end ifinfo @subheading Free resolutions @tex Let $I=(g_1,...,g_s)\subseteq K[\underline{x}]^r$ and $M= K[\underline{x}]^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 K[x]^r and M=K[x]^r/I. A free resolution of M is a long exact sequence is a long exact sequence @*...--> F2 --A2-> F1 --A1-> F0-->M-->0, @end ifinfo @*where the columns of the matrix @tex $A_1$ generate $I$. The length of the sequence is at most $n$, where $n$ is the number of variables in the polynomial ring, resp. power series ring. Note that free resolutions over other rings may be infinite. Considered as modules, $A_1$ @end tex @ifinfo A1 generate I. The length of the sequence is at most n, where n is the number of variables in the polynomial ring, resp.@: power series ring. Note that free resolutions over other rings may be infinite. Considered as modules, A1 @end ifinfo is a set of generators of the input, @tex $A_2$ @end tex @ifinfo A2 @end ifinfo consists of a set of generators of the first syzygy module of @tex $A_1$, @end tex @ifinfo A1, @end ifinfo etc. @subheading Betti numbers @cindex Betti number @tex The graded {\bf Betti number} $b_{i,j}$ of $R^n/M$ ($M$ a homogeneous submodule of $R^n$) is the minimal number of generators in degree $i+j$ of the $j$th syzygy module (= module of relations) of $R^n/M$ (the 0th resp.\ 1st syzygy module of $R^n/M$ is $R^n$ resp.\ $M$). @end tex @ifinfo The graded @strong{Betti number} b_(i,j) of R^n/M (M a homogeneous submodule of R^n) is the minimal number of generators in degree i+j of the j-th syzygy module (= module of relations) of R^n/M (the 0-th (resp.1-st) syzygy module of R^n/M is R^n (resp.@: M)). @end ifinfo @subheading Regularity @cindex Regularity @ifinfo Let (+) K[x]e(a,n) -> @dots{} -> (+) K[x]e(a,0) -> I -> 0 @* be a minimal resolution with homogeneous maps of degree 0. Then, the regularity of I is the smallest number s with the property deg(e(a,i)) <= s+i for all i. @end ifinfo @tex \noindent Let $0 \rightarrow\ \bigoplus_a K[\underline{x}]e_{a,n}\ \rightarrow\ \dots \rightarrow\ \bigoplus_a K[\underline{x}]e_{a,0}\ \rightarrow\ I\ \rightarrow\ 0$ be a minimal resolution of $I$ considered with homogeneous maps of degree 0. Then, the {\bf regularity} of $I$ is the smallest number $s$ with the property \hbox{deg($e_{a,i}$)$ \leq s+i$} for all $i$. @end tex @c --------------------------------------------------------------------------- @node Characteristic sets, References, 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<...), 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)