\input amssym.def
\input cyracc.def
\newfam\cyrfam
\font\tencyr=wncyr10
\font\sevencyr=wncyr7
\font\fivecyr=wncyr5
\def\cyr{\fam\cyrfam\tencyr\cyracc}
\textfont\cyrfam=\tencyr \scriptfont\cyrfam=\sevencyr
  \scriptscriptfont\cyrfam=\sevencyr
\font\twcyr=wncysc10 scaled \magstep1
\font\tencyr=wncyr10
\font\tencyrb=wncyb10
\font\tencyri=wncyi10
\font\eightcyr=wncyr8
\font\tencyss=wncyss10
\font\twcyss=wncyss10 scaled \magstep1
\def\K{{\Bbb K}}
\def\lm{\mathop{\rm lm}\nolimits}
\def\lc{\mathop{\rm lc}\nolimits}
\def\NOD{\mathop{\cyr NOD}\nolimits}
\hyphenation{mno-go-ob-ra-ziya}
{\cyr
\centerline{\twcyss FORMULA  GA\u IDARA DLYA NAIBOL\Cprime SHEGO
OBSHCHEGO}
\centerline{\twcyss DELITELYA NESKOL\Cprime KIKH POLINOMOV}
\medskip
\centerline{\tencyri S.~V.~Duzhin, S.~V.~Chmutov}
\bigskip

     V  zametke  privodit\cydot sya  dokazatel\cprime stvo  izyashchno\u i
formuly E.~A.~Ga\u idara, vyrazhayushche\u i naibol\cprime shi\u i obshchi\u i
delitel\cprime\  nabora  polinomov
ot mnogikh pe\-re\-mennykh cherez bazis Grebnera porozhdennogo imi  ideala.
\`Eta formula byla opublikovana avtorom [3] nezadolgo do ego smerti v
avtomobil\cprime no\u i katastrofe. Preprint [3] trudnodostupen, pri
\`etom on napisan chereschur dlinno i ne slishkom  akkuratno.  Sama  zhe
formula Ga\u idara nastol\cprime ko krasiva i  prosta,  chto  my  sochli
svoim dolgom sdelat\cprime\ ee dostoyaniem shiroko\u i matematichesko\u i
obshchestvennosti.

     Ideya privodimogo nizhe  dokazatel\cprime stva  teoremy  1  prinadlezhit
A.~I.~Ka\-ishevu [4]; v vyvode teoremy 2 my sleduem original\cprime nomu
rassuzhdeniyu avtora. Svetlo\u i pamyati nashego druga Zheni Ga\u idara my
posvyashchaem \`etu publikatsiyu.
\bigskip

     Pust\cprime\ $A$ ---  kol\cprime tso  polinomov  ot  konechnogo  chisla
peremennykh $x_1,...,x_n$  nad proizvol\cprime nym polem $\K$:
$$
           A = \K[x_1,...,x_n].
$$
Predpolozhim, chto zadan nekotory\u i poryadok na monomakh v $A$,
sovmestimy\u i s umnozheniem (sm. [1]).
V dal\cprime ne\u ishem  pod  starshimi  monomami  polinomov
podrazumevayut\cydot sya starshie  monomy  otnositel\cprime no \`etogo
vy\-bran\-no\-go  poryadka.  Sistema obrazuyushchikh ideala $I\subset A$
nazyvaet\cydot sya  {\tencyri bazisom  Grebnera\/},  esli starshie monomy
ee \`elementov porozhdayut tot zhe ideal v $A$, chto i starshie monomy vsekh
polinomov ideala $I$. Ponyatie bazisa Grebnera dopuskaet mnozhestvo 
\`ekvivalentnykh pereformulirovok i sluzhit osnovaniem vse\u i
konstruktivno\u i kommutativno\u i algebry [1,5].
\medskip
{\tencyrb Teorema 1.}
{\tencyri Esli $f_1,...,f_m$  ---  polinomy,  obrazuyushchie  bazis
Grebnera, to
$$
        \lm(\NOD(f_1,...,f_m)) = \NOD(\lm(f_1),...,\lm(f_m)),
$$
gde $\lm(f)$ oboznachaet starshi\u i monom $f$.}
\smallskip
{\tencyri  Dokazatel\cprime stvo\/}.  Snachala  svedem  zadachu  k
sluchayu  vzaimno prostykh   polinomov $f_1,...,f_m$.  Dlya  \`etogo
predpolozhim,   chto  $\NOD(f_1,...,f_m) = q$ i $f_i=q\cdot g_i$
dlya vsekh $i=1,...,m$. Togda  $\lm(f_i) = \lm(q)\cdot\lm(g_i)$
i ostaet\cydot sya dokazat\cprime, chto
$$
       \NOD(\lm(g_1),...,\lm(g_m)) = 1,
$$
gde  $g_1,...,g_m$ --- nabor vzaimno prostykh polinomov,
obrazuyushchi\u i bazis Grebnera.

     Predpolozhim protivnoe: $\NOD(\lm(g_1),...,\lm(g_m))\ne 1$,  t.e.
sushchestvuet peremennaya $x_k$, vkho\-dya\-shchaya vo vse monomy
$\lm(g_1),...,\lm(g_m)$.
Rassmotrim polinomy  $g_1,...,g_m$   kak \`elementy kol\cprime tsa
$B = \K(x_1,...,\widehat{x_k},...,x_n)[x_k]$.
Zametim, chto  v  kol\cprime tse  $B$ \`eti polinomy takzhe vzaimno prosty.
(Dokazatel\cprime stvo \`etogo prostogo utverzhdeniya my opuskaem).
Poskol\cprime ku $B$ --- kol\cprime tso polinomov ot odno\u i peremenno\u i,
to  sushchestvuyut  takie $h_1,...,h_m \in B$, chto
$$
           h_1\cdot g_1 + ... + h_m\cdot g_m = 1.
$$
Pust\cprime\ $v\in \K[x_1,...,\widehat{x_k},...,x_n]$ --- naimen\cprime shee
obshchee kratnoe znamenatele\u i vsekh ko\`effitsientov
$h_1,...,h_m$.
Umnozhaya obe chasti poslednego ravenstva na $v$, poluchim:
$$
        \widetilde{h}_1\cdot g_1 + ... + \widetilde{h}_m\cdot g_m = v,
$$
gde $\widetilde{h}_i\in A$.

     Togda  $v$ prinadlezhit idealu, porozhdennomu  $g_1,...,g_m$ v $A$.
Poskol\cprime ku  $g_1,...,g_m$ --- bazis Grebnera, starshi\u i monom
$\lm(v)$ polinoma $v$ dolzhen prinadlezhat\cprime\
idealu, porozhdennomu starshimi monomami $\lm(g_1)$,...$\lm(g_m)$.
\`Eto, odnako, nevozmozhno, ibo starshie monomy  $\lm(g_i)$  soderzhat  $x_k$,
a  $v$ --- net. Poluchennoe protivorechie dokazyvaet teoremu.
\smallskip

{\tencyri Zamechanie\/}. Teorema 1 yavlyaet\cydot sya chastnym sluchaem teoremy
Kredelya i Ve\u ispfenninga [2], utverzhdayushche\u i, chto  razmernost\cprime\
algebraicheskogo mnogoobraziya $V$ ravna  razmernosti  mnogoobraziya  $V'$
nule\u i  starshikh monomov \`elementov bazisa Grebnera $F$ ideala $V$.
V  chastnosti,  esli \`elementy $F$ vzaimno prosty, to  $\dim V < n-1$
i, sledovatel\cprime no,  $\dim V'< n-1$.   A  \`eto  oznachaet,  chto
monomy iz $\lm(F)$  vzaimno  prosty.  \`Etot  fakt \`ekvivalenten  teoreme 1.
Odnako,   dokazatel\cprime stvo  Kredelya i Ve\u ispfenninga  ikh  teoremy
gorazdo   slozhnee   privedennogo   vyshe
dokazatel\cprime stva ee chastnogo sluchaya.
\smallskip

     V sluchae leksikograficheskogo poryadka na monomakh iz teoremy  1
vytekaet formula, vy\-ra\-zha\-yu\-shchaya NOD cherez bazis Grebnera.
\medskip
{\tencyrb  Teorema 2 (formula Ga\u idara).}
$$
\NOD(P) = {\lc_{x_{1},\ldots
,x_{n}}(f_{1})\cdot \ldots
\cdot \lc_{x_{n-1},x_{n}}(f_{n-1})\cdot \lc_{x_n}(f_n)
\over\lc_{x_2,\ldots,x_{n}}(f_{1})\cdot \ldots
\cdot \lc_{x_{n}}(f_{n-1})}.
$$

{\tencyri Poyasnenie\/}. Zdes\cprime\ $P$ --- proizvol\cprime noe mnozhestvo
polinomov iz $A$, $f_{1},...,f_{n}$  --- nekotorye (vozmozhno, ne vse)
\`elementy bazisa Grebnera $F$ ideala, porozhdennogo $P$, otnositel\cprime no
leksikograficheskogo poryadka, pri kotorom $x_{1}>x_{2}>\ldots>x_{n}$.
\`Eti  \`elementy  vybrany iz $F$ tak, chto $\lm(f_{i})/\NOD(\lm(F))$
ne zavisit ot $x_{i}$  dlya  kazhdogo $i=1,\ldots,n$. (Tako\u i
vybor vozmozhen v silu teoremy 1; razumeet\cydot sya, on ne odnoznachen).
Cherez $\lc_{x_{i+1},\ldots,x_{n}}(f)$  oboznachen polinomial\cprime ny\u i
koefficient  pri starshem monome $f$  ,  rassmatrivaemom  kak  polinom ot
peremennyh $x_{1},x_{2},\ldots,x_{i}$  nad  kol\cprime com
$\K[x_{i+1},\ldots,x_{n}]$.  Po\-skol\cprime\-ku  NOD  nabora
polinomov  opredelen s tochnost\cprime yu  do  umnozheniya na konstantu,
starshie ko\`efficienty (v obychnom  smysle)  vseh  voznikayushchih
polinomov mozhno schitat\cprime\ edinichnymi.
\smallskip
{\tencyri Dokazatel\cprime stvo\/}. Pust\cprime\ $q= \NOD(P)$. Togda
sushchestvuyut takie polinomy $g_{i}$,  chto $f_i=g_i\cdot q$. Budem
posledovatel\cprime no vychislyat\cprime\ polinomy
$\lc_{x_{n}}(q)$, $\lc_{x_{n-1},x_{n}}(q)$,...,
$\lc_{x_{1},x_{2},\ldots,x_{n}}(q)= q$.
Poskol\cprime ku
$\lc_{x_{n}}(f_{n}) = \lc_{x_{n}}(g_{n})\cdot \lc_{x_{n}}(q)$ i
$\lc_{x_{n}}(g_{n})=1$ (soglasno   vyboru $g_n$),   to
$\lc_{x_{n}}(q)=\lc_{x_{n}}(f_{n})$. Predpolozhim, chto
$\lc_{x_{i+1},\ldots,x_{n}}(q)$  uzhe  na\u ideno
i vychislim $\lc_{x_{i},\ldots,x_{n}}(q)$. Imeem:
$$\eqalign{
\lc_{x_{i},\ldots,x_{n}}(f_{i})
&= \lc_{x_{i},\ldots,x_{n}}(g_{i})\cdot \lc_{x_i,\ldots,x_n}(q), \cr
\lc_{x_{i+1},\ldots,x_{n}}(f_{i})
&= \lc_{x_{i+1},\ldots,x_n}(g_i)\cdot \lc_{x_{i+1},\ldots,x_n}(q).\cr}
$$
\noindent
Po postroeniyu, starshi\u i monom $\lm(g_{i})$ ne zavisit ot $x_{i}$,
znachit,
$$\lc_{x_{i},\ldots
,x_{n}}(g_{i}) = \lc_{x_{i+1},\ldots
,x_{n}}(g_{i}),
$$
i, sledovatel\cprime no,
$$
\lc_{x_{i},\ldots,x_{n}}(q)
= {\lc_{x_{i},\ldots,x_{n}}(f_{i})\over \lc_{x_{i+1},
\ldots,x_{n}}(f_{i})}\cdot \lc_{x_{i+1},\ldots,x_{n}}(q).
$$
Spustivshis\cprime\ takim obrazom do $i=1$, my poluchim nuzhnuyu formulu 
dlya $\NOD(P)$.
}
\bigskip
[1]  L.~Robbiano.  Gr\"obner  Bases:  a  Foundation  for   Commutative
     Algebra. -- Preprint, 1989.
[2]  H.~Kredel, V.~Weispfenning.  Computing Dimension and Independent
     Sets for Polynomial Ideals. --  J. of Symb. Comp., v.~6,  p.~231---248,
     1988.
[3]  E.~A.~Gaydar.  The calculation of  polynomial  GCD  by  Gr\"obner
     basis. -- Utrecht University, preprint no.~678, September 1991.
{\cyr
[4]  A.~I.~Kaishev. Chastnoe soobshchenie, 1990.
[5]  Komp\cprime yuternaya algebra. Simvol\cprime nye i algebraicheskie
     vychisleniya. -- M.: Mir, 1986.

\bigskip
\leftline{Institut programmnykh sistem}
\leftline{Rossi\u isko\u i Akademii Nauk}
\leftline{Pereslavl\cprime-Zalesski\u i}
}
\end
