Annotation of OpenXM/doc/compalg/effgr.tex, Revision 1.4
1.4 ! noro 1:
! 2: %$OpenXM: OpenXM/doc/compalg/effgr.tex,v 1.3 2000/03/28 02:02:29 noro Exp $
1.1 noro 3: \chapter{$B%0%l%V%J4pDl7W;;$N8zN(2=(B}
4:
5: $BBh(B \ref{chapgr} $B>O$G%0%l%V%J4pDl$r7W;;$9$k%"%k%4%j%:%`$G$"$k(B
6: Buchberger $B%"%k%4%j%:%`$N:G$b86;OE*$J7A$r<($7$?(B. $B$7$+$7(B, $B$=$3$G=R$Y$?(B
7: $B$h$&$K(B, $B%"%k%4%j%:%`(B \ref{buch}$B$r$=$N$^$^<B9T$9$k$3$H$O(B, $B8zN($NE@$+$i(B
8: $B$_$FLdBj$,$"$k(B. $B$3$l$O(B, $B%"%k%4%j%:%`$N?J9T$K$D$l$F(B, $B@55,2=$7$F(B 0 $B$K$J(B
9: $B$kBP$,A}2C$7$F$$$/$?$a$G$"$k(B. $B$^$?(B, $BBP$NA*$SJ}$K$bG$0U@-$,$"$k(B. $B$I$N$h(B
10: $B$&$JA*$SJ}$rMQ$$$F$b(B, $B:G=*7k2L$G$"$k%0%l%V%J4pDl$N0l0U@-$OJ]>Z$5$l$F$$(B
11: $B$k$,(B, $BA*$SJ}$K$h$j8zN($KBg$-$J:9$,$G$k$3$H$,B?$/$N<B83$K$h$j3N$+$a$i$l(B
12: $B$F$$$k(B. $BK\>O$G$O(B, $B%0%l%V%J4pDl$N7W;;$r8zN(2=$9$k$5$^$6$^$JJ}K!$r>R2p(B
13: $B$9$k(B.
14:
15: \begin{nt}
16: $B0J2<$G(B, $B<!$N$h$&$J5-K!$rMQ$$$k(B.
17:
18: \noi
19: $p$ : $BAG?t(B.\\
20: $GF(p)$ : $p$ $B85BN(B.\\
21: $\Z_{(p)}$ = $\{a/b \mid a \in \Z; b \in \Z \setminus p\Z\} \subset \Q$ :
22: $\Z$\, $B$N(B $p\Z$ $B$K$*$1$k6I=j2=(B.\\
23: $X = \{x_1,\cdots,x_n\}$ : $BITDj85(B.\\
24: $\phi_p$ : $\Z_{(p)}[X]$ $B$+$i(B $GF(p)[X]$ $B$X$NI8=`E*<M1F(B.
25: $\phi_p(a/b) = \phi_p(a)/\phi_p(b)$. ($a \in \Z$, $b\in \Z\setminus p\Z$.)\\
26: $<$, $<_0$, $<_1$, $<_i$ : term order.\\
27: $HT_<(f)$ : $f$ $B$N(B $<$ $B$K4X$9$kF,9`(B.\\
28: $HC_<(f)$ : $f$ $B$N(B $<$ $B$K4X$9$kF,78?t(B.\\
29: $T(f)$ : $f$ $B$K8=$l$k9`A4BN$N=89g(B.\\
30: $GB_<(S)$ : $S$ $B$N(B $<$ $B$K4X$9$kHoLs%0%l%V%J4pDl(B.\\
31: $f_1,\cdots,f_m$ : $\Z[X]$ $B$N85(B.\\
32: $NF_<(f,G)$ : $f$ $B$N(B $G$ $B$K4X$9$k@55,7A$N0l$D(B.\\
33: $Init_<(I)$ : \{$HT_<(f)\mid f\in I$\} $B$G@8@.$5$l$k%$%G%"%k(B.\\
34: $Useless\_Pairs(D)$ : $BITI,MWBP$N8!=P(B.\\
35: $Select\_Pair(D)$ : $BBP$NA*Br(B\\
36: $Sp(C)$ : $BB?9`<0BP$N(B S-$BB?9`<0$N7W;;(B
37: \end{nt}
38:
39: \section{$BITI,MWBP$N8!=P(B}
40: Buchberger $B%"%k%4%j%:%`$K$*$$$F(B, $B@55,2=$K$h$j(B 0 $B$K$J$kBP$rITI,MWBP$H8F(B
41: $B$V(B. $B$3$l$i$O(B, $B$"$kB?9`<0=89g$,(B $B%0%l%V%J4pDl$G$"$k$3$H$N3NG'$N$?$a$K$N$_0UL#$,(B
42: $B$"$j(B, $B$b$77W;;$;$:$K(B 0 $B$K@55,2=$5$l$k$3$H$,$o$+$l$P7W;;8zN($NE@$+$i$_(B
43: $B$F6K$a$F9%ET9g$G$"$k(B. $B$5$i$K(B, $B$3$N(B $B!V(B0 $B$X$N@55,2=!W$O(B, $B%"%k%4%j%:%`$N(B
44: $B$"$k;~E@$K$*$$$F$G$O$J$/(B, $B%0%l%V%J4pDl$N$9$Y$F$N85$,@8@.$5$l$?$N$A(B, 0 $B$K@55,2=(B
45: $B$5$l$k$N$G$"$C$F$b$h$$(B. $B<B:](B, $B$=$N$h$&$J>u67$O(B, $BL?Bj(B \ref{'thomo'} $B$K(B
46: $B$*$$$F8=$l$F$$$k(B. $B$3$NL?Bj$r(B, Taylor $B4pDl$KE,MQ$9$l$P(B, Taylor $B4pDl$N$&(B
47: $B$A(B, $B>iD9$J(B ($B$9$J$o$AB>$N4pDl$K$h$j@8@.$5$l$k(B) $B4pDl$r$H$j=|$$$?;D$j$K$D(B
48: $B$$$F(B 0 $B$K@55,2=$5$l$l$P$h$$$3$H$K$J$k(B. $B$3$3$G<h$j=|$+$l$k4pDl$KBP1~$9(B
49: $B$kB?9`<0BP$N$[$+(B, $BB>$NJ}K!$K$h$j(B 0 $B$K@55,2=$5$l$k$3$H$,$o$+$j(B, $B$H$j=|(B
50: $B$+$l$kBP$b$"$jF@$k(B. $B$3$l$i$K$D$$$F=R$Y$k(B.
51:
52: \subsection{$B>iD9$J4pDl$N=|5n(B}
53: Taylor $B4pDl$+$i>iD9$J4pDl$r<h$j=|$/$?$a$N4pK\E*$JF;6q$O(B, $B4pDl4V$N<!$N(B
54: $B<+L@$J91Ey<0$G$"$k(B.
55: $$ {T_{ijk}\over T_{ij}} S_{ij} + {T_{ijk}\over T_{jk}} S_{jk} +
56: {T_{ijk}\over T_{ki}} S_{ki} = 0 $$
57: $B$3$N91Ey<0$K$*$$$F(B, $B$$$:$l$+$N78?t$,(B 1 $B$G$"$l$P(B, $B$=$N9`$KBP1~$9$k4pDl(B
58: $B$O(B, $BB>$N4pDl$K$h$j@8@.$5$l$k(B. $B$3$l$r7+$jJV$7$F>iD9$J4pDl$r<h$j=|$$$F(B
59: $B9T$/$,(B, $B$3$N:](B, $BAj8_$K0MB8$79g$&4pDl$r8m$C$F<h$j=|$/$3$H$rHr$1$k$?$a(B,
60: $B4pDl4V$KA4=g=x$rF~$l(B, $B$"$k4pDl$,$=$l$h$j=g=x$NDc$$4pDl$K$h$j@8@.$5$l$F(B
61: $B$$$k>l9g$K$N$_(B, $B$=$N4pDl$r<h$j=|$/$3$H$H$9$k(B.
62:
63: \begin{df}
64: $\{S_{ij}\mid i < j\}$ $B$K$*$1$kA4=g=x$r<!$N$h$&$KDj5A$9$k(B.
65:
66: \noi
67: $S_{ij} < S_{kl} \Leftrightarrow$\\
68: $T_{ij} < T_{kl}$ $B$^$?$O(B\\
69: ($T_{ij} = T_{kl}$ $B$+$D(B ($j < l$ $B$^$?$O(B ($j = l$ $B$+$D(B $i < k$)))
70: \end{df}
71:
72: \begin{df}
73: $BBP(B $(i,j)$ $B$K4X$9$k;0$D$N@-<A$r<!$N$h$&$KDj5A$9$k(B.
74:
75: \noi
76: $M(i,j) \Leftrightarrow$ $B$"$k(B $k < j$ $B$,B8:_$7$F(B $T_{kj} \mid T_{ij}$ $B$+$D(B $T_{kj} \neq T_{ij}$
77:
78: \noi
79: $F(i,j) \Leftrightarrow$ $B$"$k(B $k < i$ $B$,B8:_$7$F(B $T_{kj} = T_{ij}$
80:
81: \noi
82: $B(i,j) \Leftrightarrow$ $B$"$k(B $k > j$ $B$,B8:_$7$F(B $T_{k} \mid T_{ij}$ $B$+$D(B $T_{jk} \neq T_{ij}$ $B$+$D(B $T_{ik} \neq T_{ij}$
83: \end{df}
84:
85: \noi
86: $B$3$l$i$O(B, $BA05-91Ey<0$K$*$$$F(B, $S_{ij}$ $B$N78?t$,(B 1 $B$+$D(B $S_{ij}$ $B$N=g=x(B
87: $B$,:GBg$K$J$k>r7o$r>l9gJ,$1$K$h$jI=$7$?$b$N$G$"$k(B. $B$$$:$l$N@-<A$K$*$$$F$b(B
88: $T_{k} | T_{ij}$ $B$h$j(B $S_{ij}$ $B$N78?t$O(B 1. $B$=$l$>$l$K$D$$$F3N$+$a$l$P(B,
89: $B<B:]$K(B $S_{ij}$ $B$,:GBg=g=x$H$J$C$F$$$k$3$H$,$o$+$k(B. $B$h$C$F(B, $B<!$NL?Bj$,(B
90: $B$J$jN)$D(B.
91:
92: \begin{pr}(Gebauer and M\"oller{\rm\cite{GEB}})
93: Taylor $B4pDl$O(B, $\{S_{ij} \mid \neg M(i,j), \neg F(i,j), \neg B(i,j)\}$
94: $B$G@8@.$5$l$k(B.
95: \end{pr}
96:
97: \begin{re}
98: $B<B:]$N%"%k%4%j%:%`$K$*$$$F$O(B, 0 $B$G$J$$@55,7A$,@8@.$5$l$F(B, $D$ $B$KBP$r(B
99: $BDI2C$9$k:]$K(B, $B>e5-$N@-<A$rK~$?$9BP$r:o=|$7$F$$$/$,(B, $B@-<A(B $M, F, B$ $B$N$&$A(B,
100: $M, F$ $B$O(B, $BB?9`<0=89g(B $G$ $B$KDI2C$9$k85$r4^$`BP$,BP>]$H$J$k$N$KBP$7(B,
101: $B$ $B$O4{$KB8:_$7$F$$$kBP$,BP>]$H$J$k(B. $B$3$N;v<B$O(B, $B@55,2=BP$NA*Br@oN,$H$N(B
102: $B4XO"$G(B, $B%"%k%4%j%:%`$N?J9T$K=EBg$J1F6A$r5Z$\$9>l9g$,$"$k(B.
103: \end{re}
104:
105: \subsection{0 $B$K@55,2=$5$l$kBP$N=|5n(B}
106: $BA0@a$G=R$Y$?$b$N0J30$K(B, $BF,9`$N$_$K$h$j(B, 0 $B$K@55,2=$G$-$k$HH=CG$G$-$kBP(B
107: $B$,$"$jF@$k(B.
108:
109: \begin{pr}(Buchberger)\\
110: $\GCD(HT(f),HT(g))=1$ $B$J$i$P(B $Sp(f,g) \tmred{\{f,g\}} 0$
111: \end{pr}
112: \proof
113: $f = \sum_i f_i$, $g = \sum_i g_i$ ($f_i, g_i \in M; f_1 > f_2 >
114: \cdots, g_1 > g_2 > \cdots$; $B$"$kE:;z0J9_$O(B 0 $B$H$7$F$*$/(B) $B$H$9$k(B.
115: $B2>Dj$K$h$j(B $\GCD(f_1,g_1) = 1$. $B$3$N$H$-(B, $Sp(f,g) = g_1\sum_{i\ge
116: 2}f_i - f_1\sum_{j\ge 2}g_j$$B$3$l$+$i(B, $BG$0U$N(B $m \ge 2$ $B$KBP$7$F$"$k(B
117: $k$ $B$,B8:_$7$F(B \\ $Sp(f,g) \tmred{\{f,g\}} R_m =
118: (g_1+\cdots+g_k)(f_{m-k+1}+\cdots)-(f_1+\cdots+f_{m-k})(g_{k+1}+\cdots)$\\
119: $B$H$J$k(B. $B<B:](B, $m = 2$ $B$K$D$$$F$O@5$7$$(B. $m$ $B$^$G@5$7$$$H$9$k(B.
120: $\GCD(f_1,g_1) = 1$ $B$h$j(B, $g_1f_{m-k+1} \neq f_1g_{k+1}$ $B$,8@$($k(B. $B$h$C(B
121: $B$F(B, $B$b$7(B $g_1f_{m-k+1} > f_1g_{k+1}$ $B$J$i$P(B, $HM(R_m) = g_1f_{m-k+1}$.
122: $B$9$k$H(B, \\
123: $R_m \mred{f} R_m - gf_{m-k+1} = (g_1+\cdots+g_k)(f_{m-k+2}+\cdots)-(f_1+\cdots+f_{m-k+1})(g_{k+1}+\cdots)$\\
124: $B$H$J$j(B, $m+1$ $B$N;~$b@5$7$$(B. $g_1f_{m-k+1} < f_1g_{k+1}$ $B$G$bF1MM$G$"$k(B.
125: $B$h$C$F(B, $B$3$NA`:n$r7+$jJV$7$F(B, $B7k6I(B $Sp(f,g) \tmred{\{f,g\}} 0$ $B$rF@$k(B. \qed
126:
127: \noi
128: $B$3$NL?Bj$K$h$j(B, $BA0@a$NA`:n$G;D$C$?4pDl$NCf$+$i$5$i$K(B 0 $B$K@55,2=$5$l$k(B
129: $BBP$r=|5n$9$k$3$H$,$G$-$k(B.
130:
131: \section{$B@55,2=BP$NA*Br@oN,(B}
132: $B%"%k%4%j%:%`(B \ref{buch} $B$N%k!<%W$K$*$1$k(B, $B@55,2=$NBP>]$H$J$kBP$NA*Br$O(B,
133: $B%"%k%4%j%:%`$N@5Ev@-$K$O$J$s$i1F6A$7$J$$$,(B, $B<B:]$N7W;;8zN($KBg$-$/1F6A(B
134: $B$rM?$($k(B. Buchberger $B$K$h$jDs0F$5$l$?@oN,$O<!$N$b$N$G$"$k(B.
135:
136: \begin{df}
137: {\bf normal strategy}\\
138: $T_{ij}$ $B$,:G>.$JBP$+$iA*Br$9$k@oN,$r$$$&(B.
139: \end{df}
140:
141: \noi
142: $B$3$N@oN,$O(B, $B=g=x$NDc$$F,9`$r$b$D4pDl$rAa$a$K@8@.$9$k$H$$$&<BMQE*$J0UL#(B
143: $B$r$b$DB>$K(B, $B$3$N@oN,$K$h$l$P(B S $BB?9`<0$O(B, $B4JLs$N;EJ}$K$h$i$:0l0UE*$J@5(B
144: $B5,7A$H$J$k$3$H$,<($5$l$F$$$k(B. $B$3$N@oN,$O(B, term order $B$K$h$C$F$O6K$a$F(B
145: $B0-$$7k2L$r$b$?$i$9>l9g$,B?$/(B, $BFC$K(B, $B<-=q<0=g=x$N$h$&$K(B, $BA4<!?t$K$h$k(B
146: $BHf3S$r9T$o$J$$=g=x$G?S$@$7$$(B.
147:
148: \begin{df}
149: {\bf $B@F<!2=(B}\\
150: $t$ $B$r@F<!2=JQ?t$H$7(B, $R = k[x_1,\cdots,x_n]$ and $R_h = k[x_1,\cdots,x_n,t]$
151: $B$H$9$k(B. $f \in R$ $B$N@F<!2=$r(B $f^*$, $g\in R_h$ $B$NHs@F<!2=$r(B $g_*$ $B$H=q$/(B.
152: $B0J2<(B, $f$ $B$NA4<!?t$r(B $\tdeg(f)$ $B$H=q$/(B.
153: $$f^* = t^{\tdeg(f)}f(x_1/t,\cdots,x_n/t)$$
154: $$g_* = g|_{t=1}$$$B$G$"$k(B. $BB?9`<0=89g(B $F \subset R$, $G \subset R_h$ $B$K(B
155: $BBP$7$F$b(B, $B3F85$r@F<!2=(B, $BHs@F<!2=$7$?$b$N$r$=$l$>$l(B $F^*$, $F_*$ $B$H=q$/(B.
156:
157: $B$3$N$H$-(B, $R$ $B$N(B order $<$ $B$KBP$7$F(B, $R_h$ $B$N(B order $<_h$ $B$,(B
158: \begin{center}
159: (H) $BG$0U$N@F<!B?9`<0(B $g \in R_h$ $B$KBP$7(B,
160: $HT(g)_* = HT(g_*)$
161: \end{center}
162: $B$rK~$?$9$H$-(B, $<_h$ $B$r(B $<$ $B$N@F<!2=$H8F$V$3$H$K$9$k(B.
163: \end{df}
164:
165: \begin{ex}
166: \label{horder}
167: $X \cup \{t\}$ ($X$ $B$K4X$7$F(B $<$) $B$K$h$k(B block order $B$O(B $<$ $B$N@F<!2=$N0l$D(B
168: $B$G$"$k$,(B, $BDj5A$K$h$j(B,
169:
170: \begin{center}
171: $ut^m <_h vt^n \Leftrightarrow \tdeg(ut^m) < \tdeg(vt^n)$ $B$^$?$O(B $\tdeg(ut^m) = \tdeg(vt^n)$ $B$+$D(B $u < v$
172: \end{center}
173: $B$J$k(B $<_h$ $B$b(B $<$ $B$N@F<!2=$G$"$k(B.
174: \end{ex}
175:
176: \begin{pr}
177: \label{hcomp}
178: $F \subset R$ $B$H$7(B, $<_h$ $B$r(B $<$ $B$N@F<!2=(B order $B$H$9$k(B. $B$3$N$H$-(B,
179: $B$b$7(B $G$ $B$,(B $Id(F^*)$ $B$N@F<!B?9`<0$+$i$J$k%0%l%V%J4pDl$J$i(B,
180: $G_*$ $B$O(B $Id(F)$ $B$N%0%l%V%J4pDl$H$J$k(B.
181: \end{pr}
182: $B@F<!2=$OA*Br@oN,$=$N$b$N$G$O$J$$$,(B, $BF~NO$r@F<!2=$7$?8e(B, $B>e$NNc$G=R$Y$?(B
183: $BA4<!?tHf3SF~$j$N(B $<_h$ $B$N$b$H$G(B normal strategy $B$G7W;;$7$?8eHs@F<!2=$9(B
184: $B$k$H$$$&<j=g$G%0%l%V%J4pDl$r5a$a$k$H(B, $BITI,MWBP$OA}2C$9$k$b$N$N(B, $B7W;;$,(B
185: $B%9%`!<%:$K?J9T$9$k$3$H$,7P83E*$KCN$i$l$F$$$?(B. $B78?tBN$,M-8BBN$N>l9g$K$O(B,
186: $B8e$G=R$Y$k(B, $BITI,MWBP$KBP$9$k@55,7A7W;;$G@8$8$k78?tKDD%$NLdBj$,@8$8$J$$(B
187: $B$?$a(B, $BM-8BBN>e$G$N%0%l%V%J4pDl7W;;$K$O@F<!2=$OM-MQ$G$"$k(B.
188:
189: \begin{df}
190: {\bf sugar strategy}\\
191: $B%0%l%V%J4pDl7W;;$NESCf$K8=$l$kB?9`<0(B $f$ $B$K(B, $B<!$N5,B'$K$h$j$"$k<+A3?t(B
192: $s_f$ (sugar) $B$rBP1~$5$;$k(B.
193:
194: \begin{enumerate}
195: \item $BF~NOB?9`<0(B $f$ $B$KBP$7$F$O(B, $s_f = \tdeg(f)$
196: \item $m$ $B$,(B monomial $B$N;~(B $s_{mf} = \tdeg(m)+s_f$
197: \item $s_{f+g} = \max(s_f,s_g)$
198: \end{enumerate}
199: sugar strategy $B$H$O(B, S $BB?9`<0$N(B sugar $B$N:G$b>.$5$$$b$N$N=89g$+$i(B normal
200: strategy $B$GBP$rA*Br$9$k@oN,$r$$$&(B.
201: \end{df}
202: Giovini $B$i(B{\rm\cite{SUGAR}}$B$K$h$jDs0F$5$l$?$3$N@oN,$O(B, $BF~NOB?9`<0=89g(B
203: $B$r@F<!2=$7$F$N%0%l%V%J4pDl7W;;$r(B{\bf $B2>A[E*(B}$B$K9T$J$&$b$N$G(B, sugar $B$O(B
204: $B@F<!2=8e$N<!?t$KBP1~$7$F$$$k(B.
205:
206: \section{Trace lifting}
207:
208: sugar strategy $B$K$h$j(B, $B>/$J$/$H$b78?tBN$,M-8BBN$N>l9g$K$O(B, $B==J,$J8zN((B
209: $B$,C#@.$G$-$k$h$&$K$J$C$?(B. $B$7$+$7(B, $B78?tBN$,M-M}?t$N>l9g(B, $BA0$K=R$Y$?8!(B
210: $B=P4p=`$K$+$+$i$J$$ITI,MWBP$N(B S $BB?9`<0$N@55,2=7W;;$K$+$+$k%3%9%H$,Bg$-(B
211: $B$$>l9g$,$7$P$7$P$"$k(B.
212: $B$=$N$?$a(B, $B<!$N$h$&$J%"%k%4%j%:%`(B ({\bf trace lifting})
213: $B$,Ds0F$5$l$?(B \cite{TRAV}.
214:
215: \begin{al}
216: \label{tl}
217: \begin{tabbing}
218: \\
219: trace\_lifting$(F,<)$\\
220: Input : $F \subset \Z[X]$; term order $<$\\
221: Output : $F$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J4pDl(B\\
222:
223: do \= \{\\
224: \> $p \leftarrow$ $BL$;HMQ$NAG?t(B\\
225: \> $G \leftarrow tl\_guess(F,<,p)$\\
226: \> if \= $G \neq$ {\bf nil} $B$+$D(B tl\_check$(F,G,<) =1$ \\
227: \> then return $G$\\
228: \}
229: \end{tabbing}
230: \end{al}
231:
232: \begin{al}
233: \label{tlguess}
234: \begin{tabbing}
235: \\
236: tl\_guess$(F,<,p)$\\
237: Input : $F \subset \Z[X]$; term order $<$; $BAG?t(B $p$\\
238: Output : $F$ $B$N%0%l%V%J4pDl8uJd$^$?$O(B {\bf nil}\\
239:
240: if \= $B$"$k(B $f \in F$ $B$,B8:_$7$F(B $\phi_p(HC(f))=0$ then return {\bf nil}\\
241: $G \leftarrow F$\\
242: $G_p \leftarrow \{\phi_p(f) \mid f \in G\}$\\
243: $D \leftarrow \{\{f,g\} \mid f,g \in G; f \neq g\}$\\
244: do \= \{\\
245: \> $D \leftarrow D \setminus Useless\_Pairs(D)$\\
246: \> if \= $D = \emptyset$ then return $G$\\
247: \> else \{ \= $C \leftarrow Select\_Pair(D)$\\
248: \> \> $D \leftarrow D \setminus \{C\}$\\
249: \> \}\\
250: \> $s \leftarrow Sp(C)$\\
251: \> $t_p = NF(\phi_p(s),G_p)$\\
252: \> if \= $t_p \neq 0$ then \{\\
253: \> \> $t \leftarrow NF(s,G)$\\
254: \> \> if $\phi_p(HC(f)) = 0$ then return {\bf nil}\\
255: \> \> $D \leftarrow D \cup \{\{f,t\} \mid f \in G\}$\\
256: \> \> $G \leftarrow G \cup \{t\}$\\
257: \> \> $G_p \leftarrow G_p \cup \{t_p\}$\\
258: \> \}\\
259: \}
260: \end{tabbing}
261: \end{al}
262:
263: \noi
264: $B%"%k%4%j%:%`(B \ref{tlguess} $B$O(B, $BM-M}?tBN>e$G$N@55,7A7W;;$r9T$J$&A0$KM-8BBN>e(B
265: $B$G@55,7A$r7W;;$7(B, $B$=$l$,(B 0 $B$H$J$k>l9g$K$O(B, $BM-M}?tBN>e$N@55,7A$b(B 0 $B$G$"(B
266: $B$k$H2>Dj$7$F$=$N7W;;$r>JN,$9$k(B. $B$3$N$h$&$JA`:n$r9T$J$C$F$b(B, $B@8@.$5$l$k(B
267: 0$B$G$J$$B?9`<0$K$D$$$F(B, $B$=$NF,9`$O(B, $BDL>o$N(B Buchberger $B%"%k%4%j%:%`$HF1(B
268: $BMM$N@-<A$r;}$D$?$a%"%k%4%j%:%`$ODd;_$9$k(B. $B$7$+$7(B, $p$ $B$NA*$SJ}$K$h$C$F(B
269: $B$O%0%l%V%J4pDl$r=PNO$7$J$$>l9g$,$"$k$?$a(B, $B<!$N$h$&$J%F%9%H$,I,MW$H$J$k(B.
270: \begin{al}
271: \label{tlcheck}
272: \begin{tabbing}
273: \\
274: tl\_check$(F,G,<)$\\
275: Input : $BB?9`<0=89g(B $F, G \subset \Z[X] \st G \subset Id(F)$; order $<$\\
276: Output :\= $B$b$7(B $G$ $B$,(B $<$ $B$K4X$9$k(B $F$ $B$N%0%l%V%J4pDl$J$i(B 1\\
277: \> $B$=$&$G$J$1$l$P(B 0\\
278: if \= $G$ $B$,(B $<$ $B$K4X$7$F%0%l%V%J4pDl$G$J$$(B then return 0\\
279: if $B$9$Y$F$N(B $f \in F$ $B$KBP$7(B $NF_<(f,G) = 0$ then return 1 else return 0
280: \end{tabbing}
281: \end{al}
282: $B<B:](B, $B%"%k%4%j%:%`(B \ref{tlguess} $B$N=PNO(B $G$ $B$KBP$7(B, $G \subset Id(F)$
283: $B$O9=@.K!$h$j>o$K@.$jN)$D$+$i(B, \ref{tlcheck} $B$,(B 1 $B$rJV$;$P(B $Id(G) =
284: Id(F)$ $B$G(B, $G$ $B$O(B $Id(F)$ $B$N%0%l%V%J4pDl$H$J$k(B. $B$3$N%F%9%H$rAH$_9g$o$;(B
285: $B$?$b$N$,(B, $B%"%k%4%j%:%`(B \ref{tl} $B$G$"$k(B. $B$3$N%F%9%H$rDL2a$G$-$k$h$&$J(B
286: $p$ $B$H$7$F$O(B, $BDL>o$N(B Buchberger $B%"%k%4%j%:%`$r<B9T$7$?>l9g$K8=$l$k$9$Y(B
287: $B$F$NB?9`<0$NF,78?t$r3d$i$J$$$h$&$JAG?t$r$H$l$P$h$$(B. $B$b$A$m$s$3$N$h$&$J(B
288: $BAG?t$O$"$i$+$8$a7hDj$9$k$3$H$O$G$-$J$$$,(B, $BITET9g$JAG?t$OM-8B8D$G$"$j(B,
289: $B%"%k%4%j%:%`A4BN$H$7$F$NDd;_@-$bJ]>Z$5$l$k(B. $B$3$N%"%k%4%j%:%`$K$*$$$F$O(B,
290: \begin{center}
291: $BITI,MWBP$KBP$9$k(B S $BB?9`<0$N7W;;%3%9%H(B\\
292: $\Downarrow$\\
293: $BM-8BBN>e$G$N%0%l%V%J4pDl7W;;(B + $B%0%l%V%J4pDl%F%9%H(B + $BF~NOB?9`<0$KBP$9$k(B
294: $B%a%s%P%7%C%W%F%9%H(B
295: \end{center}
296: $B$H$$$&CV$-49$($,9T$J$o$l$F$$$k(B. $B$h$C$F(B, $B$3$NCV$-49$($,8zN($r8~>e$5$;$k(B
297: $B$?$a$K$O(B, $B8e<T$,A0<T$h$j9bB.$K<B9T$G$-$J$1$l$P$J$i$J$$(B. $B$3$NHf3S$OF~NO(B
298: $BB?9`<0=89g(B $F$ $B$N@-<A(B, $B$"$k$$$OMQ$$$k(B order $B$N@-<A$K$h$C$F0[$J$k$,(B, $B0l(B
299: $BHLE*$K$O<!$N$h$&$J$3$H$,8@$($k(B.
300: \begin{itemize}
301: \item $V(Id(F))$ $B$NM><!85$,Bg$-$$>l9g(B
302:
303: $B%0%l%V%J4pDl7W;;$K8=$l$k78?t$,(B
304: $BD9Bg$K$J$k798~$,Bg$-$/(B, $BFC$K(B, $V(Id(F))$ $B$,M-8B=89g$K$J$k>l9g$K(B, $F$ $B$N(B
305: $B%0%l%V%J4pDl$r<-=q<0=g=x$G7W;;$9$k>l9g$K?S$@$7$$(B. $B$=$N$h$&$J>l9g$G$b(B,
306: $B:G=*E*$J%0%l%V%J4pDl$N78?t(B, $B85$N8D?t$O>.$5$$>l9g$,B?$/(B, 2 $B$D$N%F%9%H(B
307: $B$bHf3SE*MF0W$G$"$k(B.
308:
309: \item $V(Id(F))$ $B$NM><!85$,>.$5$$>l9g(B
310:
311: $BB?9`<0$N9`?t$,A}Bg$9$k>l9g$,B?$/(B, $B$=$N$h$&$J>l9g$K$O(B, $B8e<T$,$=$N$^$^M>(B
312: $BJ,$J%3%9%H$K$D$J$,$k(B.
313: \end{itemize}
314: $B$3$N$h$&$K(B, $B8z2L$,4|BT$G$-$J$$>l9g$b$"$jF@$k$,(B, $B$=$N$h$&$J>l9g$G$b(B
315: $B9b!9(B 2 $BG\DxEY$N;~4V$G7W;;$O=*N;$9$k$?$a(B, $B>o$K(B trace lifting $B$rMQ$$$k(B
316: $B$N$,0BA4$G$"$m$&(B.
317:
318: $B0J>e$N5DO@$K$*$$$F$O(B, $p$ $B$H$7$F$O7W;;5!$,Ds6!$9$k(B 1 $B%o!<%I0JFb$N@0?t(B
319: $B$rMQ$$$k$3$H$r2>Dj$7$F$$$k(B. $B$3$l$O(B, 1 $B%o!<%I0JFb$N@0?t$KBP$9$k2C8:>h=|(B
320: $B$,DL>o$O5!3#L?Na$H$7$FDs6!$5$l$F$$$F(B, $B9bB.$K<B9T$5$l$k$+$i$G$"$k(B. $B$^$?(B,
321: $B78?t$,K!(B $p$ $B$G0lMM$KJ,I[$7$F$$$k$H2>Dj$9$l$P(B, $p$ $B$,Bg$-$$Dx(B, $p$ $B$,(B
322: $BF,78?t$N$I$l$+$r3d$j@Z$k3NN($O>.$5$/$J$k$H4|BT$G$-$k(B. $B$h$C$F(B, $B<B:]$N7W(B
323: $B;;$G$O(B $p$ $B$H$7$F(B 1 $B%o!<%I$NHO0OFb$G$J$k$Y$/Bg$-$$@0?t$rA*$V$N$,$h$$(B.
324:
325: \section{$B@F<!2=(B $B$H(B trace lifting $B$NAH9g$;(B}
326:
327: trace lifting $B$K$h$j(B, $BITI,MWBP$KBP$9$k(B S $BB?9`<0$N7W;;%3%9%H$r(B, $BM-8BBN(B
328: $B>e$N%0%l%V%J4pDl7W;;$*$h$S(B, $B%0%l%V%J4pDl8uJd@8@.8e$N%0%l%V%J4pDl%F%9%H(B
329: $B$HF~NOB?9`<0$N%a%s%P%7%C%W%F%9%H$KCV$-49$($k$3$H$,$G$-$?(B. $B$7$+$7(B, $B<B:](B
330: $B$K@F<!2=$7$?>l9g$K$O@8$8$J$$$h$&$JCf4V78?tKDD%$,(B, sugar strategy $B$NE,(B
331: $BMQ$K$h$j@8$8$k>l9g$,$7$P$7$P8+$i$l$k(B. $BK\@a$G$O(B, $B$3$N:$Fq$r9nI~$9$k$?$a(B
332: $B$NJ}K!$K$D$$$F=R$Y$k(B.\\
333: $B$3$N$h$&$J78?tKDD%$r4JC1$JNc$G<($9(B.
334:
335: \begin{ex}
336: $I = Id(-3x_1-3x_2-5,-3x_1x_0^2-8x_0-6,4x_0^2+(-2x_1^3-7)x_0-3x_3x_1^2-2,-x_0^4-x_0^2+3x_1x_0-4x_1)$
337: \end{ex}
338: $I$ $B$N(B $x_0>x_1>x_2>x_3$ $B$J$k<-=q<0=g=x$N$b$H$G$N%0%l%V%J4pDl(B $GB(I)$ $B$O(B, \\
339: $GB(I) = \{f_3(x_3), f_2(x_2,x_3), f_1(x_1,x_3), f_0(x_0,x_3) \}$\\
340: $f_3=286978140000x_3^6-30735638450064x_3^5+139368108773718x_3^4-401122901874078x_3^3\\
341: +3813285736741284x_3^2-17712668879937657x_3+25309718023001309$\\
342: $f_2=-24359129516408255978429894458178435051554483918248x_2\\
343: -9117338725200447183121773483618146011417380000x_3^5\\
344: +945437242481668390348909147393962329546603617488x_3^4\\
345: -1215199713704678902273407299537086048391876350746x_3^3\\
346: +9203891427703221172499174842307408763060278519544x_3^2\\
347: -87128026603776953223695902278763008965980027109460x_3\\
348: +198072128718550346069760390022952204794356946307195$\\
349: $f_1=24359129516408255978429894458178435051554483918248x_1\\
350: -9117338725200447183121773483618146011417380000x_3^5\\
351: +945437242481668390348909147393962329546603617488x_3^4\\
352: -1215199713704678902273407299537086048391876350746x_3^3\\
353: +9203891427703221172499174842307408763060278519544x_3^2\\
354: -87128026603776953223695902278763008965980027109460x_3\\
355: +238670677912564106033810214119916263213614419504275$\\
356: $f_0=-9134673568653095991911210421816913144332931469343x_0\\
357: -334442494143970788481038492015748108482000000x_3^5\\
358: +37671432710327352302696037580172208903376423200x_3^4\\
359: -352356049164307536666247874973386638400872538040x_3^3\\
360: +499969270855985351160909518989653220917608771262x_3^2\\
361: -6841618915067057146509523126510725094238856771432x_3\\
362: +31588951614319486540726259755101613855437086625238$\\
363: $B$3$N7W;;$r(B, $B@F<!2=$r7PM3$7$F9T$C$?>l9g(B, $B8=$l$kCf4V4pDl$N78?t$N%S%C%HD9$NOB(B
364: $B$N:GBgCM$O(B 1489 $B%S%C%H$@$,(B, sugar strategy $B$N$_$rMQ$$$F9T$C$?>l9g$=$N(B
365: $B:GBgCM$O(B 10258121 $B%S%C%H$G$"$C$?(B. $B$3$N$h$&$J>.$5$$LdBj$KBP$7$F$b(B,
366: sugar strategy $B$,$&$^$/F/$+$J$$>l9g$K$OITI,MW$J78?tKDD%$,@8$8$F$7$^$&(B.
367: $B@F<!2=$O@8@.$5$l$k4pDl$N78?tKDD%$,5/$3$i$J$$$h$&$J(B strategy $B$rM?$($k>l(B
368: $B9g$,B?$$$,(B, $BHs@F<!$N>l9g$KHf$Y$FA0$K=R$Y$?ITI,MWBP$N8!=P$K$+$+$i$J$$IT(B
369: $BI,MWBP$rB?$/@8@.$7(B, $BLdBj$,Bg$-$/$J$k$H(B, $B$=$l$i$N(B 0 $B$X$N@55,2=$N%3%9%H(B
370: $B$,Hs>o$KBg$-$/$J$k(B. $B$3$l$i$r9nI~$9$kM-NO$JJ}K!$,(B, $B<!$N%"%k%4%j%:%`$G$"(B
371: $B$k(B.
372: \begin{al}
373: \label{htl}
374: \begin{tabbing}
375: \\
376: homogenized\_trace\_lifting$(F,<)$\\
377: Input : $F \subset \Z[X]$; term order $<$\\
378: Output : $F$ $B$N(B $<$ $B$K4X$9$k%0%l%V%J4pDl(B\\
379:
380: do \= \{\\
381: \> $p \leftarrow$ $BL$;HMQ$NAG?t(B\\
382: \> $G \leftarrow tl\_guess(F^*,<_h,p)$\\
383: \> if \= $G \neq$ nil\\
384: \> \>$B$+$D(B $G_*$ $B$,(B $<$ $B$K4X$9$k%0%l%V%J4pDl(B\\
385: \> \>$B$+$D$9$Y$F$N(B $f \in F$ $B$KBP$7(B $NF(f,G_*) = 0$\\
386: \> then return $G_*$\\
387: \}
388: \end{tabbing}
389: \end{al}
390: $<_h$ $B$O(B $BNc(B \ref{horder} $B$G=R$Y$?(B order $B$NA4<!?tIU@F<!2=$rMQ$$$F$$(B
391: $B$k(B. $B$3$NJ}K!$H(B, $BC1$KF~NO$r@F<!2=$7$?$b$N$KBP$7$F(Btrace lifting $B$K$h$j%0(B
392: $B%l%V%J4pDl$r5a$a$F$+$iHs@F<!2=$9$kJ}K!$rHf3S$9$k$H<!$N$h$&$K$J$k(B. $B$$$:(B
393: $B$l$b(B, $B@F<!2=$K$h$jA*Br@oN,$r0BDj$K$7(B, $B$+$D@F<!2=$K$h$jA}2C$7$?ITI,MWBP(B
394: $B$K4X$9$k%3%9%H$O(B trace lifting $B$K$h$j4KOB$5$l$k(B.
395:
396: \begin{itemize}
397: \item $B@F<!2=(B $\Rightarrow$ $B8uJd@8@.(B $\Rightarrow$ $BHs@F<!2=(B $\Rightarrow$ $B%F%9%H(B
398:
399: $BHs@F<!2=$r9T$J$C$?;~E@$G>iD9$J4pDl$r<h$j=|$/$?$a(B, $B%F%9%H$K$+$+$k%3(B
400: $B%9%H$O@F<!2=$r9T$J$o$J$$>l9g$HJQ$o$i$J$$(B.
401:
402: \item $B@F<!2=(B $\Rightarrow$ $B8uJd@8@.(B $\Rightarrow$ $B%F%9%H(B $\Rightarrow$ $BHs@F<!2=(B
403:
404: $B@F<!$J%0%l%V%J4pDl8uJd$N>l9g(B, $B>iD9$J4pDl$,$[$H$s$I$J$/(B, trace lifting $B$K(B
405: $B$h$j%+%C%H$5$l$?BgItJ,$NITI,MWBP$rM-M}?tBN>e$G2~$a$F@55,2=$9$kI,MW$,$"$k(B.
406: \end{itemize}
407: $B$9$J$o$A(B, $BF~NO$,4{$K@F<!$N>l9g$r=|$$$F(B, $BHs@F<!2=8e$K%F%9%H$r9T$J$&J}$,8zN((B
408: $B$,$h$$(B. $B$3$NJ}K!$K$h$j(B, trace lifting $B$N$_$G$O7W;;IT2DG=$@$C$?B?$/$NLdBj(B
409: $B$,7W;;2DG=$K$J$C$?(B.
410:
411: \section{$F_4$ $B%"%k%4%j%:%`(B}
412:
413: $BBe?tJ}Dx<05a2r$K8B$i$:(B, $BBe?t4v2?$K$*$1$kITJQNL$N7W;;$J$I$K$*$$$F$b(B
1.2 noro 414: $BG$0UF~NOB?9`<0=89g$+$i$N%0%l%V%J4pDl$N7W;;$O(B, $B7W;;NLE*$K$_$F(B dominant
1.1 noro 415: step $B$H$J$k$3$H$,B?$$(B. $B$3$N$h$&$J>l9g$N7W;;K!$H$7$F$O(B Buchberger
416: $B%"%k%4%j%:%`$,$[$\M#0l$NJ}K!$G$"$C$?$,(B, $B:G6a(B Faug\`ere $B$K$h$j(B
417: $F_4$ ($B$"$k$$$O(B $F_5$) $B%"%k%4%j%:%`$,Ds0F$5$l(B, $B$=$N9bB.@-$,(B
418: $BCmL\$5$l$F$$$k(B. $BK\@a$G$O(B, $B$3$N%"%k%4%j%:%`$K$D$$$F35@b$9$k(B.
419:
420: \subsection{Symbolic preprocessing}
421:
422: $B%"%k%4%j%:%`(B \ref{buch} $B$r<B9T$9$k>l9g(B, $D$ $B$+$i$I$N85$rA*$s$GMh$k$+(B
423: $B$G(B, $B$=$N8e$N7W;;$N?J9T$NMM;R$,A4$/$3$H$J$k(B, $B$H$$$&$3$H$,(B
424: $B5/$3$k(B. $B$^$?(B, $B:GA1$N85$rA*$s$@$D$b$j$G$b(B, $BFC$KM-M}?tBN>e(B
425: $B$J$I$K$*$$$F(B, $NF(Sp(f,g),G)$ $B$N78?t$,6KC<$KBg$-$/$J$j(B,
426: $B7W;;ITG=$K$J$k$3$H$b5/$3$k(B. $B$=$N$?$a(B, trace lifting,
427: homogenization $B$J$I$N<o!9$N%F%/%K%C%/$N$b$H$G7W;;$,;n$_$i$l$F(B
428: $BMh$?(B.
429: $B$3$3$G(B, Buchberger $B%"%k%4%j%:%`$N3K?4$G$"$k(B $NF(Sp(f,g),G)$
430: $B$K$D$$$F9M;!$9$k(B.
431: $NF(Sp(f,g),G)$ $B$O<!$N$h$&$J<j=g$G7W;;$5$l$k(B.
432:
433: \begin{tabbing}
434: $r \leftarrow af - bg$ ($a, b$ $B$OC19`<0(B) \\
435: while \= ( $r$ $B$N9`(B $t$ $B$r3d$j@Z$k(B $h \in G$ $B$,$"$k(B )\\
436: \> $ r \leftarrow r - ch $\\
437: \> ($r$ $B$K(B $t$ $B$N9`$O$J$$(B)
438: \end{tabbing}
439: $B$3$3$G(B, $r$ $B$r4JLs$9$k$N$KI,MW$J(B $h \in G$ $B$O0l8+<B:]$K4JLs(B
440: $BA`:n$r<B9T$7$J$1$l$PJ,$+$i$J$$$h$&$K8+$($k$,(B, $B>iD9$J85(B
441: ($B$9$J$o$A(B, $B<B:]$K$O4JLs$KMQ$$$i$l$J$$85(B) $B$b5v$;$P(B, $B<!$N$h$&$J(B
442: $BJ}K!$G;vA0$KF@$i$l$k(B.
443:
444: \begin{al} (Symbolic preprocessing)
445: \label{symred}
446: \begin{tabbing}
447: Input : $BB?9`<0(B $f$, $BB?9`<0=89g(B $G$\\
448: Output : $Red=\{ah \mid a :$ $BC19`<0(B, $h \in G \}$ \\
449:
450: $T \leftarrow T(f)$ \\
451: $Red \leftarrow \emptyset$\\
452: while \= $HT(g)|t$ $B$J$k(B $t\in T$, $g \in G$ $B$,B8:_$9$k(B do \{\\
453: \>$Red \leftarrow Red \cup \{t/HT(g)\cdot g\}$\\
454: \>$T \leftarrow (T \setminus \{t\}) \cup T(reductum(t/HT(g)\cdot g)$\\
455: \}\\
456: return $Red$
457: \end{tabbing}
458: \end{al}
459: $B$3$N%"%k%4%j%:%`$GF@$i$l$?(B $Red$ (Reducer) $B$O<!$N@-<A$r$b$D(B:
460:
461: \begin{itemize}
462: \item $\{f\} \cup Red$ $B$N85$N$"$k9`(B $t$ $B$,$"$k(B $g\in G$ $B$KBP$7(B $HT(g)$ $B$G3d$j@Z$l$k$J$i$P(B, $HT(x)=t$ $B$J$k(B $x \in Red$ $B$,$"$k(B.
463: \end{itemize}
464: $B$3$l$h$j(B, $B<!$,8@$($k(B.
465:
466: \begin{itemize}
467: \item $\{f\}$ $B$N(B, $Red$ $B$N85$K$h$k(B $K$ $B78?t$N4JLsA`:n$G$N@55,7A$O(B, $G$ $B$K(B
468: $B4X$9$k@55,7A$H$J$k(B.
469: \end{itemize}
470: $B$3$l$r(B, $B9TNs$N8@MU$G8@$$49$($k$?$a$K<!$N=`Hw$r$9$k(B.
471: $B$^$:(B, $\{f\} \cup Red$ $B$K8=$l$kA4$F$N9`$r(B $T$ $B$H$7(B, $T$ $B$N85$r=g=x$N9b$$(B
472: $B=g$KJB$Y$?$b$N$r(B $t_1 > t_2 > \cdots $ $B$H$9$k(B.
473: $T$ $B$G(B $K$ $B>eD%$i$l$k@~7A6u4V$N85(B $h$ $B$N(B,
474: $(t_1,t_2,\cdots)$ $B$r4pDl$H$9$k9T%Y%/%H%kI=8=$r(B $[h]$, $B9T%Y%/%H%k(B $v$
475: $B$KBP$9$kB?9`<0$r(B $poly(v)$ $B$H=q$/$3$H$K$9$k(B.
476: $$[f] = [f_1 f_2 \cdots]$$
477: $$r_i = [r_{i1} r_{i2} \cdots] \quad (r_i \in Red)$$
478: $B$H$9$k$H$-(B,
479: $$A=\left(
480: \begin{tabular}{ccc}
481: $f_1$ & $f_2$ & $\cdots$ \\
482: $r_{11}$ & $r_{12}$ & $\cdots$ \\
483: $r_{21}$ & $r_{22}$ & $\cdots$ \\
484: & $\cdots$ & \\
485: \end{tabular}
486: \right)$$
487: $B$H$J$i$Y(B, $B$3$l$r(B, $B9T$K4X$9$k4pK\JQ7A$K$h$j<!$N>r7o$rK~$?$99TNs(B
488: $B$ $B$KJQ7A$9$k(B.
489:
490: \begin{itemize}
491: \item $poly(B_i)$ $B$,(B 0 $B$G$J$$$H$-(B, $poly(B_k) (k\neq i)$ $B$O(B $HT(poly(B_i))$
492: $B$r4^$^$J$$(B.
493: \end{itemize}
494:
495: $$B=\left(
496: \begin{tabular}{ccccccc}
497: 1 & 0 & ? & ? & ? & 0 & $\cdots$ \\
498: 0 & 1 & ? & ? & ? & 0 & $\cdots$ \\
499: 0 & 0 & 0 & $\cdots$ & 0 & 1 & $\cdots$ \\
500: & & & $\cdots$ & & & \\
501: 0 & 0 & 0 & $\cdots$ & 0 & 0 & $\cdots$
502: \end{tabular}
503: \right)$$
504: $B$3$N$H$-(B,
505: $poly(B_i)$ $B$N$&$A(B, $HT(poly(B_i))$ $B$,(B $\{HT(r)\mid r\in Red\}$ $B$K(B
506: $B4^$^$l$J$$$b$N$,(B, $NF(f,G)$ $B$H$J$k(B.
507:
508: \subsection{$F_4$ $B%"%k%4%j%:%`(B}
509:
510: $BA0@a$G$N(B $B@55,7A7W;;$N8@$$BX$($O(B, $BB?9`<0>jM>1i;;7W;;$K$*$$$F$b$7$P$7$P(B
511: $BMQ$$$i$l(B, $BFC$KL\?7$7$$$b$N$G$b$J$$(B. $F_4$ $B%"%k%4%j%:%`$O(B, $BJ#?t$N(B
512: S-$BB?9`<0$r$^$H$a$F9TNs7A<0$G4JLs$9$k(B. $B$=$N$?$a$N(B symbolic preprocessing
513: $B$b(B, $B=PH/E@$,(B, S-$BB?9`<0$K8=$l$k9`$NOB=89g$H$J$k$@$1$G(B, $B4{$K(B
514: $B=R$Y$?%"%k%4%j%:%`$,$=$N$^$^E,MQ$5$l$k(B.
515:
516: \begin{al} (Symbolic preprocessing)
517: \label{multisymred}
518: \begin{tabbing}
519: Input : $BB?9`<0=89g(B $F$, $BB?9`<0=89g(B $G$\\
520: Output : $Red=\{ah \mid a :$ $BC19`<0(B, $h \in G \}$ \\
521:
522: $T \leftarrow \cup_{f\in F}T(f)$ \\
523: $Red \leftarrow \emptyset$\\
524: while \= $HT(g)|t$ $B$J$k(B $t \in T$, $g \in G$ $B$,B8:_$9$k(B do \{\\
525: \>$Red \leftarrow Red \cup \{t/HT(g)\cdot g\}$\\
526: \>$T \leftarrow (T \setminus \{t\}) \cup T(reductum(t/HT(g)\cdot g)$\\
527: \}\\
528: return $Red$
529: \end{tabbing}
530: \end{al}
531: $B9TNs(B $A$ $B$b(B, $BA4$F$N(B S-$BB?9`<0$KBP1~$9$k%Y%/%H%k$*$h$S(B symbolic preprocessing $B$G(B
532: $BF@$i$l$?(B $Red$ $B$KB0$9$kB?9`<0$KBP1~$9$k%Y%/%H%k$r9T$H$9$k9TNs$H$7$F(B
533: $B9=@.$5$l$k(B. $B$3$N9TNs$r(B, $B9T4pK\JQ7A$K$h$j(B, $B<!$N>r7o$rK~$?$99TNs(B $B$ $B$K(B
534: $BJQ7A$9$k(B.
535:
536: \begin{itemize}
537: \item $poly(B_i)$ $B$,(B 0 $B$G$J$$$H$-(B, $poly(B_k) (k\neq i)$ $B$O(B $HT(poly(B_i))$
538: $B$r4^$^$J$$(B.
539: \end{itemize}
540: $B$3$l$O(B, $t_1 > t_2 > \cdots$ $B$r?7$?$JJQ?t$H$_$F(B, $B$3$N=g=x$G(B reduced $B$J(B
1.2 noro 541: $B%0%l%V%J4pDl$r7W;;$7$?7k2L$KBP1~$9$k(B.
1.1 noro 542:
543: $$F' = \{h=poly(B_i) \mid h\neq 0, HT(h)\notin \{HT(r)\mid r\in Red\}\}$$
544: $$Red' = \{h=poly(B_i) \mid h\neq 0, HT(h)\in \{HT(r)\mid r\in Red\}\}$$
545: $B$H$*$/(B.
546: \begin{pr}
547: \begin{enumerate}
548: \item $h\in F'$ $B$O(B $G \cup (F'\setminus \{h\})$ $B$K4X$7$F@55,7A(B
549: \item $f\in F$ $B$J$i$P(B $f \tmred{G\cup F'} 0$
550: \end{enumerate}
551: \end{pr}
552: {\bf Proof}\\
553: 1: $h\in F'$ $B$J$i$P(B $T(h) \cap \{HT(r)\mid r\in Red\} = \emptyset$. $B$3$l$O(B,
554: $Red$ $B$N:n$jJ}$h$j(B $h$ $B$,(B $G$ $B$K4X$7$F@55,7A$G$"$k$3$H$r0UL#$9$k(B.
555: $B$b$A$m$s(B $h$ $B$O(B $F'\setminus \{h\}$ $B$K4X$7$F$b@55,7A$G$"$k(B. \\
556: 2: $f\in F$ $B$H$9$k(B. $$NF(f,G) = f-\sum_{r_i\in Red} c_i r_i\quad (c_i\in K)$$
557: $B$H=q$1$k(B. $B$h$C$F(B, $NF(f,G)$ $B$O(B $F \cup Red$ $B$G(B $K$ $B>e@8@.$5$l$k(B
558: $B@~7A6u4V$KB0$9$k(B. $B$3$3$G(B,
559: $F\cup Red$ $B$H(B $F' \cup Red'$ $B$,(B $K$ $B>eF10l$N@~7A6u4V$r@8@.$7(B,
560: $B$+$D(B $NF(f,G)$ $B$K$O(B $Red'$ $B$N85$NF,9`$O8=$l$J$$$+$i(B,
561: $$NF(f,G)=\sum_{f_i\in F'} d_i f_i\quad (d_i \in K)$$
562: $B$H=q$1$k(B.
563: $B$3$N@~7AOB$OD>$A$K(B $F'$ $B$K4X$9$k@55,7A7W;;$H$J$k(B. \qed\\
564: 2. $B$K$h$j(B $F$ $B$H$7$F(B, $B$$$/$D$+$N(B S-$BB?9`<0$N=89g$r$H$j(B,
565: $F'$ $B$r$^$H$a$F(B $G$ $B$KIU$12C$($k$3$H$K$h$j(B, $F$ $B$KB0$9$k(B S-$BB?9`<0(B
566: $B$,(B 0 $B$K4JLs$5$l$k$3$H$,J,$+$k(B. $B$^$?(B, 1. $B$K$h$j(B,
567: $B%"%k%4%j%:%`$NDd;_@-$b8@$($k(B.
568: $F$ $B$H$7$F0l$D$N(B S-$BB?9`<0$r$H$C$?>l9g$,DL>o$N(B Buchberger $B%"%k%4%j%:%`(B
569: $B$G$"$j(B, $B$=$N>l9g$K$O(B, $BA*$SJ}(B (selection strategy) $B$K$h$C$F8zN($K(B
570: $BBg$-$/:9$,$G$k$3$H$O4{$K=R$Y$?(B. $F_4$ $B$K$*$$$F$b(B $F$ $B$NA*$SJ}$,(B
571: $BLdBj$H$J$k$,(B, $BJ#?t85$rA*Br$G$-$k$3$H$G(B, selection strategy $B$N8zN($K(B
572: $BBP$9$k1F6A$,>/$J$/$J$k$3$H$,<B83$K$h$jCN$i$l$F$$$k(B.
573:
574: $BNc$($P(B, $B<!$N$h$&$J(B strategy $B$K$h$j(B, $BB?$/$NNc$,8zN($h$/7W;;$G$-$k(B.
575:
576: \begin{df}
577: S-$BB?9`<0$N(B sugar $B$N:G>.$N$b$N$rA4$FA*$V(B.
578: \end{df}
579: $B$3$3$G(B, $F_4$ $B$N>l9g(B, $B@55,7A7W;;$K$*$$$FDL>o$N(B sugar $B$O0UL#$r;}$?$J$$$N$G(B,
580: $B$"$k(B sugar $B$N(B S-$BB?9`<0$r=8$a$F7W;;$7$?>l9g(B, $B@8@.$5$l$?4pDl$N(B sugar $B$b(B
581: $B$=$NCM$G$"$k$H$7$F(B, $B:F5"E*$K(B sugar $B$NCM$rDj$a$k$3$H$H$9$k(B.
582: $BFC$K(B, $BF~NOB?9`<0=89g$,(B homogeneous $B$N>l9g(B, $B$3$N(B strategy $B$K$h$j(B,
1.2 noro 583: $B3F%9%F%C%W$G7W;;$5$l$k4pDl$O(B, $B<!?t$,(B $d$ $B$N>l9g(B, {\bf reduced} $B$J%0%l%V%J(B
1.1 noro 584: $B4pDl$N$&$A$N(B, $d$ $B<!$N85A4$F$H$J$k(B. $B$3$l$O(B, homogeneous ideal $B$N(B
1.2 noro 585: $B>l9g<!$,@.$jN)$D$3$H$+$iJ,$+$k(B.
1.1 noro 586:
587: \begin{enumerate}
588: \item $d$ $B<!$N4pDl$r@8@.$9$k$?$a$N(B S-$BB?9`<0$OA4$F(B $d-1$ $B<!0J2<$N(B
589: $B4pDl$+$i:n$i$l$k(B.
590: \item $d$ $B<!$N@F<!B?9`<0$O(B, $d+1$ $B<!0J>e$N4pDl$G$O4JLs$5$l$J$$(B.
591: \end{enumerate}
592:
593: \subsection{Modular $B7W;;$K$h$k@~7AJ}Dx<0$N5a2r(B}
594:
595: $F_4$ $B$K$*$$$F$O(B, selection strategy $B$K=>$C$F9=@.$5$l$?9TNs$r(B,
596: $B:84pK\JQ7A$9$k$H$$$&A`:n$N7+$jJV$7$G4pDl$r@8@.$7$F$$$/(B.
597: $B$3$3$G(B, $B:84pK\JQ7A$O(B, $B@~7AJ}Dx<05a2r$H$_$J$9$3$H$,$G$-$k(B.
598: $B$9$J$o$A(B,
599:
600: \begin{enumerate}
601: \item $B9TNs(B $A$ $B$+$i@~7AFHN)$J9T$rA4$FH4$-$@$7$F(B $A'$ $B$r:n$k(B.
602: \item $A'$ $B$NNs$r:8$+$i=g$K8+$F(B, $B$=$l$^$G<h$j=P$7$?Ns$H@~7AFHN)$J(B
603: $BNs$rH4$-=P$9(B, $B$H$$$&A`:n$r7+$jJV$7$F@5J}9TNs(B $A''$ $B$r:n$k(B.
604: \item $A'$ $B$G;D$C$?Ns$r=8$a$F(B $B''$ $B$H$9$k(B.
605: \item $A''X=B''$ $B$J$k@~7AJ}Dx<0$r2r$/(B.
606: \item $X$ $B$+$i(B, $A'$ $B$N9T4pK\JQ7A$N7k2L$r9=@.$9$k(B.
607: \end{enumerate}
608: $B85$NBN>e$G9M$($k8B$j(B, $B$3$l$OC1$J$k8@$$BX$($K2a$.$J$$$,(B, $BNc$($PM-M}?tBN(B
609: $B>e$N>l9g(B, $\det(A'')\neq 0$ $B$J$k(B $A''$ $B$r(B modular $B7W;;$K$h$j?dB,$7$FH4(B
610: $B$-$@$7(B, $A''X=B''$ $B$N2r8uJd$r(B modular $B7W;;$J$I$K$h$j9=@.$7(B,
611:
612: \begin{itemize}
613: \item $A$ $B$N3F9T$K(B, $BBh(B 5 $B9`$N7k2L$rBeF~$7$F(B 0 $B$K$J$k$3$H$r(B
614: $B3N$+$a$k(B.
615: \end{itemize}
616: $B$H$$$&%A%'%C%/$K$h$j(B modular $B7W;;$N7k2L$,(B, $BM-M}?tBN>e$G$N9T4pK\(B
617: $BJQ7A$N7k2L$HEy$7$$$3$H(B, $BFC$K(B $A$ $B$r9=@.$9$kB?9`<0(B
618: $B$GD%$i$l$F$$$k$3$H(B, $B@~7AJ}Dx<0$N2r$N0l0U@-$K$h$j8@$($k(B.
619: $B$3$N$h$&$J2r8uJd$rM?$($k$b$N$H$7$F(B, $BCf9q>jM>DjM}$*$h$S(B Hensel $B9=@.(B
620: $B$,$"$k(B. $BCf9q>jM>DjM}$rMQ$$$kJ}K!$O(B, $BK!(B $p$ $B$,M-M}?t>e$NA]$-=P$7$H(B
621: $B0[$J$k$b$N$rM?$($J$$8B$j(B, $B<+L@$JJ}K!$G@:EY$r$"$2$F$$$-(B, $B@0?t(B-$BM-M}?t(B
622: $BJQ49$N7k2L$,(B stable $B$K$J$C$?$i(B $A$ $B$KBeF~$7$F%A%'%C%/$H$$$&J}K!$G$"$k(B.
623: $B$^$?(B, Hensel $B9=@.$O(B $B%"%k%4%j%:%`(B \ref{lineq} $B$=$N$b$N$G$"$k(B.
624: Faug\`ere $B$K$h$l$P(B, $F_4$ $B$K$*$$$F$O(B $B$ $B$,Bg$-$/$J$k$?$a(B, $B$ $B$NNs?t(B
625: $B$,(B $A$ $B$N%5%$%:$r1[$($k>l9g$K$OCf9q>jM>DjM}$rMQ$$$?$[$&$,$h$$$H$N$3$H$G$"$k(B.
626: $B$$$:$l$K$;$h(B, modular $B7W;;$K$h$kJ}K!$,8zN($r>e$2$k>l9g$H$$$&$N$O(B,
627: $det(A'')$ $B$KHf$Y$F2r$N78?t$,>.$5$$>l9g$G$"$k(B. $B$3$l$O0lHL$K4|BT(B
628: $B$G$-$k$3$H$G$O$J$$$,(B, $BA0@a$G=R$Y$?$h$&$K(B, homogeneous $B$N>l9g$K(B $F_4$
1.2 noro 629: $B$,(B reduced $B$J%0%l%V%J4pDl$N0lIt$r@8@.$9$k(B, $B$H$$$&$3$H$+$i(B, reduced $B$K(B
1.1 noro 630: $B$7$?>l9g$K78?t$,>.$5$/$J$k$h$&$JLdBj$G$O(B modular $B7W;;$,8zN($r8~>e(B
631: $B$5$;$k$3$H$,4|BT$G$-$k(B.
632:
1.4 ! noro 633: \subsection{$BNc(B}
1.1 noro 634:
635: \cite{REP} $B$G$O(B, 4 $BJQ?t$NBe?tJ}Dx<07O(B (odd order $BJ}Dx<0(B) $B$N%0%l%V%J4pDl7W;;(B
636: $B$r(B Buchberger $B%"%k%4%j%:%`$K$h$j9T$C$?(B. $B$3$N7W;;$K8=$l$kCf4V4pDl$K$*$$(B
637: $B$F(B, 16 $B<!$N4pDl$r@~7A7A<0$H$_$F(B, inter reduction $B$7$F$_$?7k2L(B, $B78?t$,(B
638: $B6KC<$K>.$5$/$J$k$3$H$,$o$+$k(B. $B$b$H$b$H(B, Buchberger $B%"%k%4%j%:%`$G(B odd
639: order $BJ}Dx<0$r7W;;$9$k>l9g(B, $B:G8e$K78?t$,BgJQ>.$5$$4pDl$,2?K\$+=P$F=*N;(B
640: $B$9$k(B. $BFC$K(B, $B:G=i$K8=$l$k(B, $B78?t$N>.$5$$4pDl$,(B, 16 $B<!$N4pDl$N$&$A:G8e$N(B
641: $B$b$N$G$"$C$?$?$a(B, $B$=$N4pDl$rMQ$$$F0l$DA0$N4pDl$r4JLs$7$?$H$3$m(B, $B78?t$,(B
1.2 noro 642: $B>.$5$/$J$C$?(B. $B$=$NA`:n$r4pDlA4$F$KE,MQ$7$?$H$3$m(B, 16 $B<!$N4pDlA4$F$N78(B
643: $B?t$,(B, inter reduction $B$K$h$j>.$5$/$G$-$k$3$H$,J,$+$C$?$N$G$"$k(B. $B4{$K(B
644: $B=R$Y$?$h$&$K(B, $B$3$N$h$&$J>l9g$K$O(B, modular $B7W;;$K$h$k2r8uJd$N7W;;$,M-8z(B
645: $B$H$J$k(B. $B$7$+$7(B, 15 $B<!$N4pDl$r(B inter reduction $B$7$?$H$3$m(B, $B78?t$NBg$-$5(B
646: $B$O$[$H$s$IJQ$o$i$:(B, $BBg$-$$$^$^$G$"$C$?(B. $B0J>e$N$h$&$JGX7J$N$b$H$K(B, $B8=:_(B
647: $B$N<BAu$G$N(B odd order $BJ}Dx<0$KBP$9$k(B Buchberger$B%"%k%4%j%:%`7W;;(B
648: (homogenization+trace lifting) $B$*$h$S(B $F_4$ $B$NHf3S$r<($9(B. $BI=$G(B,
649: GaussElim, ChRem, IntRat, Check $B$O$=$l$>$l(B Gauss $B>C5n(B, $BCf9q>jM>DjM}(B,
650: $B@0?t(B-$BM-M}?tJQ49(B, $B7k2L$N%A%'%C%/$K$+$+$C$?;~4V$r<($9(B.
1.1 noro 651:
652: \begin{table}[hbtp]
653: \caption{$B7W;;;~4V$NHf3S(B}
654: \begin{center}
655: \begin{tabular}{|c||c|c|c|c|c|} \hline
656: & total & GaussElim & ChRem & IntRat& Check \\ \hline
657: Buchberger & 264710 & --- & --- & --- & --- \\ \hline
658: $F_4$ homo & 32880 & 6437 & 6300 & 5763 & 13340 \\ \hline
659: $F_4$ non homo & 39970 & 4832 & 6143 & 18240 & 9950 \\ \hline
660: \end{tabular}
661: \end{center}
662: \end{table}
663:
664: \begin{table}[hbtp]
665: \caption{$B3F<!?t$N9TNs$N%5%$%:(B}
666: \begin{center}
667: \begin{tabular}{|c||c|c|c|c|c|c|} \hline
668: & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
669: $F_4$ homo &(56,334) & (119,441) & (182,545) & (362,774) & (671,1009) & (1195,1359) \\ \hline
670: $F_4$ non homo &(62,339) & (128,448) & (137,461) & (227,571) & (307,621) & (955,1149) \\ \hline
671: \end{tabular}
672:
673: \begin{tabular}{|c||c|c|c|c|c|c|} \hline
674: & 16 & 17 & 18 & 19 & 20 & 21 \\ \hline
675: $F_4$ homo &(836,688) &(2323,1761) &(895,964) &(204,271) &(446,515) &(308,374) \\ \hline
676: $F_4$ non homo & (555,508) & (2022,1763) & --- & --- & --- & --- \\ \hline
677: \end{tabular}
678:
679: \begin{tabular}{|c||c|c|c|c|} \hline
680: & 22 & 23 & 24 & 25 \\ \hline
681: $F_4$ homo & --- & --- & --- & --- \\ \hline
682: $F_4$ non homo & (799,868)& (300,367) & (398,467) & (361,427) \\ \hline
683: \end{tabular}
684: \end{center}
685: \end{table}
686:
687: \begin{table}[hbtp]
688: \caption{$B3F<!?t$N4pDl$N7W;;;~4V(B}
689: \begin{center}
690: \begin{tabular}{|c||c|c|c|c|c|c|} \hline
691: & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
692: Buchberger & 2.3 & 11 & 43 & 164 & 1214 & 32512 \\ \hline
693: $F_4$ homo & 1.8 & 10 & 45 & 357 & 2574 & 26519\\ \hline
694: $F_4$ non homo & 2.2 & 12& 28 & 166& 1064 & 35906\\ \hline
695: \end{tabular}
696:
697: \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|} \hline
698: & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ \hline
699: Buchberger & 205234 & 10300 & 4530 & --- & 10700 & --- & --- & --- & --- & --- \\ \hline
700: $F_4$ homo & 1340 & 1097 & 359 & 45 & 208 & 150 & --- & --- & --- & --- \\ \hline
701: $F_4$ non homo & 937 & 902 & --- & --- & --- & --- & 341& 132 & 186 & 164 \\ \hline
702: \end{tabular}
703: \end{center}
704: \end{table}
705:
706: \begin{figure}[htbp]
707: \epsfxsize=15cm
708: \epsffile{ps/blenall.ps}
709: \caption{$BCf4V4pDl$N:GBg78?t$N%S%C%HD9(B}
710: \label{nftime}
711: \end{figure}
712:
713: $B$^$:(B, total $B;~4V$,(B 1/8 $BDxEY$K8:$C$F$$$k$3$H$KCmL\$7$?$$(B. $B$3$l$O(B, $B4pDl$N(B
714: $B7W;;;~4V$NFbLu$r$_$l$P$o$+$k$h$&$K(B, Buchberger $B%"%k%4%j%:%`$K$h$k7W;;$G(B
715: $BA4BN$N7W;;;~4V$NBgItJ,$r@j$a$F$$$?(B 16 $B<!$N7W;;$,(B 1/100 $BDxEY$N;~4V$G=*$C$F(B
716: $B$$$k$?$a$G$"$k(B. $B$3$l$O(B, $B:GBg78?t$N%S%C%HD9$,(B reduced $B$J4pDl$GHs>o$K>.$5$/(B
717: $B$J$k$3$H$KBP1~$7$F$$$k(B. $B$=$l0J>e$N<!?t$K$D$$$F$O(B, $B>.$5$$78?t$r;}$D(B
718: $BB?9`<0$K$h$k4JLs2=$G:Q$`$3$H$,9bB.2=$NM}M3$G$"$k(B.
719:
1.4 ! noro 720: \subsection{$B$^$H$a(B}
1.1 noro 721: $F_4$ $B$OK\<AE*$K$O(B Buchberger $B%"%k%4%j%:%`$N2~NI$H9M$($i$l$k$,(B, $B<!$N$h$&$J(B
722: $BD9=j$r;}$D(B.
723:
724: \begin{itemize}
725: \item $B9TNs$NA]$-=P$7Cf$O(B, $B9`$N=g=xHf3S$,C1$J$k(B index $B$NHf3S$K$J$k(B.
726: \item $BCf4V4pDl$r(B reduced $B$"$k$$$O$=$l$K6a$$7A$KJ]$D$?$a(B, $B$=$N8e$N(B
727: $BA]$-=P$77W;;$,8zN(2=$9$k(B. ($B!VBP3Q2=!W$5$l$?9TNs$K$h$k4JLs2=(B vs. $B!V;03Q2=!W(B
1.2 noro 728: $B$5$l$?9TNs$K$h$k4JLs2=(B)
1.1 noro 729: \item reduced $B$J4pDl$N78?t$,>.$5$/$J$k>l9g$K$O(B, modular $B7W;;$K$h$k(B
1.4 ! noro 730: $B8zN(2=$,4|BT$G$-$k(B.
! 731:
1.1 noro 732: \end{itemize}
1.4 ! noro 733: $B0lJ}$G(B,
1.1 noro 734:
1.4 ! noro 735: \begin{itemize}
! 736: \item $BB??t$N(B S-$BB?9`<0$*$h$S(B reducer $B$r0lEY$K9TNs$H$7$F07$&$?$a$K(B,
! 737: $B5pBg$J%a%b%j$rI,MW$H$9$k>l9g$,$7$P$7$P@8$:$k(B.
! 738: \item $B0lHL$K9TNs$OAB$H$J$k$?$a(B, $BBg5,LOAB9TNs$r8zN($h$/J];}$7(B, $BA]$-=P$9I,MW(B
! 739: $B$,$"$k(B.
! 740: \item modular $B7W;;$r9T$&>l9g(B, $B9TNs$N3F9T$N(B 0 $B4JLs%A%'%C%/(B
! 741: $B$K$h$k%*!<%P!<%X%C%I$,LdBj$H$J$k(B.
! 742: \end{itemize}
! 743: $B$J$I$N:$Fq$K$h$j(B, $B<BMQE*$J<BAu$r9T$&$K$O(B Buchberger $B%"%k%4%j%:%`$HF1MM(B
! 744: $B$5$^$6$^$J9)IW$,I,MW$H$J$k(B. $B$H$O$$$((B, $BA0@a$NNc$G8+$?$h$&$K(B, $B<B83E*$J<B(B
! 745: $BAu$G$b=>Mh$N(B Buchberger $B%"%k%4%j%:%`$h$j8zN($h$/7W;;$G$-$k>l9g$,$"$k$3(B
! 746: $B$H$O3N$+$G(B, Faug\`ere $B$K$h$k$b$N0J30$K$b$5$^$6$^$J<BAu<B83$,9T$o$l$k$3$H$,(B
! 747: $B4|BT$5$l$k(B.
1.1 noro 748:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to effgr.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / compalg