Базисы Гребнера

9.11. ОПРЕДЕЛЕНИЕ. правильным если из условия $$\smu{1} \ord\theta_1< \textrm{ord}\theta_2$$ $$(\theta_1,\theta_2\in T)$$ следует $$\smu{1} \theta_1 b_i<\theta_2 b_j$$ для всех $$1\smu{1} \leq i,j\leq n$$.

9.12. ПРИМЕР. Пусть задан ранжир на множестве мономов $$T$$. Будем сравнивать термы вида $$(\theta, i)$$ по их последней координате $$i$$ и только в случае равенства ее для двух термов переходить к сравнению мономов. Полученный таким образом ранжир на $$T_F$$ не является правильным.

9.13. ПРИМЕР. Пусть $$\phi_1,\phi_2\in T_F$$. Будем считать, что $$\phi_1=(j_1,\theta_1)<\phi_2=(j_2,\theta_2)$$ тогда и только тогда, когда

либо $$\textrm{ord}\theta_1<\textrm{ord}\theta_2$$ ;

либо $$\textrm{ord}\theta_1=\textrm{ord}\theta_2$$ и $$j_1<j_2$$ ;

либо $$\textrm{ord}\theta_1=\textrm{ord}\theta_2$$, $$j_1=j_2$$ и $$\theta_1<\theta_2$$ относительно лексикографического порядка при фиксированной нумерации переменных.

Этот ранжир является правильным. Мы будем называть его стандартным.

Отметим, что по определению ранжира множество термов $$T_F$$ вполне упорядочено относительно каждого ранжира.

9.14. ОПРЕДЕЛЕНИЕ. Пусть задан ранжир на множестве термов $$T_F$$, и пусть $$\phi_1,\phi_2\in T_F$$. Будем говорить, что терм $$\phi_1$$ ниже(выше) рангом, чем $$\phi_2$$, если $$\phi_1<\phi_2$$ $$(\phi_1>\phi_2)$$.

Кроме отношения порядка $$<$$ на $$T_F$$, определим отношение частичного порядка $$\ll$$ следующим образом:$$\begin{equation} \phi_1\ll\phi_2\iff \exists \theta\in T \mid \theta\phi_1=\phi_2. \end{equation}$$ В этом случае будем говорить, что терм $$\phi_1$$ делит $$\phi_2$$. Из (1) следует, что < совместно с $$\ll$$, т.е.$$\begin{equation} \phi_1\ll\phi_2\implies \phi_1\le\phi_2. \end{equation}$$

9.15. ОПРЕДЕЛЕНИЕ. Любой элемент $$f \in F\setminus \{ 0\}$$ допускает единственное представление в виде конечной суммы:$$f=\smash[b]{\sum_{i=1}^r} c(f,\phi_i )\phi_i,\quad 0 \ne c(f,\phi_i)\in K,\ \phi_i\in T_F,\label{4.1.7}\\ \phi_r<\phi_{r-1}<\dots<\phi_1.\notag$$ Определим лидер элемента $$f$$ как $$\textbf{u}_f= \phi_1$$ и старший коэффициент как $$\textrm{Hcoeff}(f)= c(f,\phi_1 )$$. Определим $$\textbf{u}_{0}= 0$$, $$\textrm{Hcoeff}(0)=0$$. Аналогично, $$\textbf{u}_B=\{ \textbf{u}_f\mid f\in B\}$$ для любого конечного множества $$B \subseteq F$$, $$\textbf{u}_M$$ для любого подмодуля $$M \subseteq F$$ обозначает подмодуль, порожденный множеством $$\{ \textbf{u}_f\mid f \in M\}$$.

Пусть $$F$$ - свободный $$D$$ -модуль и $$f,g\in F$$. Будем говорить, что элемент $$f$$ ниже рангом, чем $$g$$, и писать $$\textrm{rk} f< \textrm{rk} g$$, если $$\textbf{u}_f<\textbf{u}_g$$. Будем говорить, что элемент $$f$$ выше рангом, чем $$g$$, и писать $$\textrm{rk} f>\textrm{rk} g$$, если $$\textbf{u}_f>\textbf{u}_g$$. Если $$\textbf{u}_f=\textbf{u}_g$$, то будем говорить, что элементы $$f$$ и $$g$$ имеют одинаковый ранг. Ясно, что различные элементы могут иметь одинаковый ранг.

9.16. ОПРЕДЕЛЕНИЕ. Пусть $$B \subset F\setminus \{ 0\}$$ - конечное множество образующих некоторого $$D$$ -модуля $$M \subseteq F$$ (без потери общности можно предположить, что $$\textrm{Hcoeff}(g) = 1$$ для любого $$g \in B$$ ). Определим процесс редукции следующим образом: $$f \underset B\to f'$$, если $$f,f' \in F$$ и существуют терм $$t \in T_F$$, $$\zeta \in T(X)$$ и $$g \in B$$, такие, что $$c = c(f,t) \ne0$$, $$t = \zeta \textbf{u}_g$$, $$f' = f - c\zeta g$$.

9.17. ЛЕММА. Пусть $$f,f'\in F$$ и $$f\underset B\to f'$$. Тогда $$\rk f\geq\rk f'$$.

ДОКАЗАТЕЛЬСТВО. Утверждение леммы следует из того, что отношение > является линейным порядком на множестве термов $$T_F$$ и свойства (2).

В дальнейшем будем опускать указание на множество $$B$$, если это не приведет к двусмысленности или если выбор множества $$B$$ несуществен. Символ $$\overset+{\underset B\to}$$ обозначает транзитивное, а $$\overset*{\underset B\to}$$ - рефлексивноранзитивное замыкание отношения $$\underset B\to$$. Элемент $$f$$ называется нередуцируемым, если не существует элемента $$f' \neq f$$, такого, что $$f\underset B\to f'$$, в противном случае $$f$$ называется редуцируемым.

9.18. ПРИМЕРЫ.

Пусть $$m=0$$, т.е. $$F$$ - векторное пространство над полем $$K$$. Рассмотрим стандартный ранжир на $$T_F$$. Если $$\boldsymbol v$$ - вектор, у которого первая ненулевая координата стоит на $$i$$ -м месте, то редукция вектора $$\boldsymbol w$$ относительно $$\boldsymbol v$$ приводит к обнулению $$i$$ -й координаты вектора $$\boldsymbol w$$ путем вычитания соответствующего кратного вектора $$\boldsymbol v$$.

Пусть $$K$$ - поле, $$n=1$$ и $$m=1$$, т.е. $$F$$ - кольцо многочленов от одной переменной. Рассмотрим стандартный ранжир на $$T_F$$. Пусть $$B=\{x^3-1;x^2-1\}$$. Тогда $$x^4\smash[b]{\underset B\to} x$$ и $$x^4\underset B\to x^2\underset B\to 1$$.

9.19. ОПРЕДЕЛЕНИЕ. Пусть на свободном $$D$$ -модуле $$F$$ дано отношение редукции $$\underset B\to$$ и вычислимая функция $$\textrm{Sel:} F\to F$$ такая, что $$f\underset B\to \textrm{Sel}(f)$$ для любого редуцируемого элемента $$f\in F$$. Рассмотрим вычислимую функцию $$S$$, определяемую рекурсивно формулой$$S(f):=\begin{cases} f, \text{ если f нередуцируем;}\\ S(\Sel(f)), \text{ если f редуцируем.} \end{cases}$$ Функцию $$S$$ такого вида назовем нормальной редукцией или алгоритмом нормальной формы для $$\overset * {\underset B \to}$$. Например, редуцируемые термы выбираются в порядке убывания относительно полного упорядочения термов, а при фиксированном терме соотношения выбираются в том порядке, как они располагаются в множестве $$B$$.

9.20. ОПРЕДЕЛЕНИЕ. Частичную редукцию определим как нормальную редукцию, осуществляемую только до тех пор, пока редуцируется лидер.

9.21. ЛЕММА. Если $$f\overset *{\underset B\to}f'$$, то элементы $$f$$ и $$f'$$ принадлежат одному и тому же смежному классу модуля $$F/M$$, где $$M$$ - подмодуль, порожденный множеством $$B$$.

ДОКАЗАТЕЛЬСТВО. $$g \in B$$, следовательно, $$c\zeta g \in M$$.

9.22. ЛЕММА. Пусть $$F$$ - свободный $$D$$ -модуль и $$B$$ - конечное подмножество модуля $$F$$. Тогда отношение редукции $$\underset B\to$$ является нетеровым, т.е. не существует бесконечных цепочек вида $$f \underset B\to f_1 \underset B\to \dots \underset B\to f_k\dots$$. Следовательно, для любого элемента $$f$$ существует (не обязательно единственный) нередуцируемый элемент $$f'$$ , такой, что $$f\overset*{\underset B\to}f'$$.

ДОКАЗАТЕЛЬСТВО. Предположим противное. Всякий ранжир, по определению, вполне упорядочивает множество термов $$T_F$$. Поэтому мы можем выбрать среди всех бесконечных цепочек редукций цепочку, начинающуюся с элемента $$g$$ с минимальным относительно ранжира лидером $$t$$. Возможны две ситуации: либо на некотором шаге редукции терм $$t$$ редуцируется и оставшаяся часть цепочки начинается с элемента, все слагаемые которого меньше, чем $$t$$ ; либо $$t$$ не редуцируется ни на каком шаге редукции. В обоих случаях получается противоречие с минимальностью выбранной цепочки: в первом случае можно выбрать хвост исходной цепочки, остающийся после редуцирования $$t$$ ; во втором - вычесть из всех элементов цепочки терм $$t$$.

9.23. ПРЕДЛОЖЕНИЕ. Множество нередуцируемых относительно отношения $$\smash[b]{\underset B\to}$$ элементов является векторным $$K$$ -пространством.

ДОКАЗАТЕЛЬСТВО. Нужно проверить, что если $$f$$ и $$g$$ - нередуцируемые элементы и $$c \in K$$, то элементы $$f + g$$ и $$cf$$ также нередуцируемы. Это немедленно следует из того, что в $$f + g$$ и $$cf$$ присутствуют с ненулевыми коэффициентами только те слагаемые, которые присутствуют в $$f$$ и $$g$$.

9.24. ЛЕММА. Если множество $$G$$ порождает подмодуль $$\smu{1} M \subset F$$ и $$f - f' \in M$$, то существует целое $$s \geq 0$$ и элементы $$f=f_0 ,f_1 ,\dots\dots , f_s =f'$$, такие, что для всех $$i$$ от 1 до $$s$$ либо $$f_{i-1} \to f_i$$, либо $$f_i\to f_{i-1}$$.

ДОКАЗАТЕЛЬСТВО. Поскольку $$G$$ порождает модуль $$M$$, элемент $$f-f'$$ можно представить в виде суммы$$\sum_{i=1}^rc_i\cdot\eta_i\cdot g_i,$$ где $$c_i$$ - коэффициенты, $$\eta_i \in T(X)$$, $$g_i \in G$$ (могут совпадать при различных значениях $$i$$ ). Доказательство леммы будем вести индукцией по минимальной длине $$r$$ такого представления. Если $$r=0$$, то $$f=f'$$, и утверждение леммы выполнено. Для произвольного $$r$$ мы можем предполагать, что $$\phi =\textbf{u}_{\eta_r \cdot g_r } \geq \textbf{u}_{\eta_i \cdot g_i }$$ для всех $$i$$. Положим $$f_1 =f-c(f,\phi)\cdot \eta_r \cdot g_r$$, $$f_2 =f_1 -(c_r -c(f,\phi))\cdot \eta_r \cdot g_r$$. Тогда $$f \to f_1 \leftarrow f_2$$ и $$f_2 - f' = f - f' - c_r \cdot \eta _r \cdot g_r = \sum\limits_{i=1}^{r-1} c_i \cdot \eta _i \cdot g_i$$, так что можно применить предположение индукции.

9.25. ОПРЕДЕЛЕНИЕ. На прямом произведении $$F\times F$$ определим функцию $$S$$, такую, что $$S(f,f')= 0$$, если $$f = 0$$, или $$f' = 0$$, или $$НОД(\textbf{u}_f,\textbf{u}_{f'})$$ не определен; в остальных случаях $$S(f,f')=\textrm{Hcoeff}(f') \varphi f - \textrm{Hcoeff}(f) \zeta f'$$, где $$\varphi ,\zeta \in T(X)$$ и $$\varphi \textbf{u}_f = НОД(\textbf{u}_f, \textbf{u}_{f'}) = \zeta \textbf{u}_{f'}$$.

9.26. ОПРЕДЕЛЕНИЕ. Пусть $$D$$ - кольцо обобщенных многочленов от переменных $$X=\{x_1,\dots,x_m\}$$ над полем $$K$$, $$F$$ - свободный $$D$$ -модуль. Предположим, что $$M \subseteq F$$ - подмодуль свободного модуля $$F$$, $$G \subset M$$ - конечное множество и < - ранжир на множестве термов $$T_F$$. Множество $$G$$ называется базисом Гребнера ( $$G$$ -базисом) подмодуля $$M$$, если для любого ненулевого элемента $$f\in M$$ имеется представление Гребнера ( $$G$$ -представление):$$f=\sum_{i=1}^r c_i\theta_ig_i,\quad 0\ne c_i\in K,\ \theta_i \in T(X),\ g_i \in G,\label{4.1.8}\\ \theta_i\textbf{u}_{g_i}>\theta_{i+1}\textbf{u}_{g_{i+1}},\notag$$ откуда, в частности, следует, что $$\textbf{u}_f = \theta _1 \textbf{u}_{g_1}$$.

Недостатком введенного определения является то, что для одного и того же элемента могут существовать различные $$G$$ -представления. Например, если $$g_1 = t^2 - 1$$, $$g_2=t^3-1$$, то $$(t^2-1)(t^3-1)== t^3\cdot g_1-g_1=t^2\cdot g_2-g_2$$ - два различных $$G$$ -представления одного и того же многочлена. С другой стороны, достаточно сложно проверить, что некоторый элемент не допускает $$G$$ -представления. От этих недостатков можно избавиться, если потребовать, чтобы любой одночлен мог появляться в $$G$$ -представлении в качестве лидера слагаемого $$\theta_i g_i$$ не более чем для одного элемента $$g_i \in G$$. В частности, можно предполагать, что элементы множества $$G$$ упорядочены, и при выборе линейно независимых элементов вида $$\theta_i g_i$$ мы руководствуемся правилами, сформулированными в определении нормальной редукции 9.19. Представление такого вида мы будем называть нормальным $$G$$ - представлением.

Для формулировки основного результата настоящего параграфа введем некоторые обозначения и докажем две леммы.

9.27. ОПРЕДЕЛЕНИЕ. Для элементов $$f,f' \in F$$ будем писать $$f \nabla f'$$, если существует элемент $$f''\in F$$, такой, что $$f \overset*\to f''$$ и $$f' \overset*\to f''$$.

9.28. ЛЕММА. Пусть $$f,f',f'' \in F$$ и $$f\overset*\to f'$$. Тогда $$f+f'' \nabla f'+f''$$.

ДОКАЗАТЕЛЬСТВО. Пусть $$f = f'+c\cdot \eta \cdot g$$, где $$\textbf{u}_{\eta \cdot g} = \phi$$ и $$c == c(f,\phi)\neq 0$$, $$c(f',\phi)=0$$. Если $$c'' = c(f'',\phi)$$, то $$f''= c''\cdot \eta \cdot g+h$$, где $$c(h,\phi)=0$$, тогда$$f+f'' = f'+c\cdot \eta \cdot g+c''\cdot \eta \cdot g+h = f'+h+(c+c'')\cdot \eta \cdot g \overset*\to f'+h$$ и$$f'+f''=f'+h+c''\cdot \eta\cdot g \overset*\to f'+h.$$

9.29. ОПРЕДЕЛЕНИЕ. Будем говорить, что отношение редукции $$\to$$ удовлетворяет условию слияния }, если для любого элемента $$f$$ из условий $$f \overset*\to f'$$ и $$f \overset*\to f''$$ следует, что $$f' \nabla f''$$.

9.30. ОПРЕДЕЛЕНИЕ. Будем говорить, что отношение редукции $$\to$$ удовлетворяет локальному условию слияния, если для любого элемента $$f$$ из $$f \to f'$$ и $$f\to f''$$ следует, что $$f' \nabla f''$$.

9.31. ОПРЕДЕЛЕНИЕ. Будем говорить, что отношение редукции $$\to$$ удовлетворяет псевдолокальному условию слияния, если для всех $$f,f',f'' \in F$$, таких, что $$f \to f'$$ и $$f\to f''$$, существует целое $$s \geq 0$$ и элементы $$f'=f_0 ,f_1 ,\dots, f_s =f''$$, такие, что $$f\overset*\to f_i$$ и $$f_{i-1}\nabla f_i$$ для всех $$i = 1,\dots,s$$.

9.32. ЛЕММА. Если нетерово отношение $$\to$$ удовлетворяет псевдолокальному условию слияния, то отношение $$\to$$ удовлетворяет условию слияния.

ДОКАЗАТЕЛЬСТВО. Применим "нетерову" индукцию, т.е. покажем, что если утверждение леммы верно для всех $$g$$ таких, что $$f\to g$$, то оно верно и для $$f$$. Такой индукции достаточно для доказательства леммы, поскольку в противном случае некоторый элемент $$f$$, для которого утверждение леммы не выполняется, мог бы быть выбран в качестве первого элемента бесконечной цепочки $$f \to f_1 \to\dots\to f_n \to \dots,$$ для всех элементов которой утверждение леммы также не выполняется.

Итак, фиксируем $$f$$ и предположим, что для всех элементов $$f^\#$$ таких, что $$f \overset+\to f^\#$$, утверждение леммы выполняется. Покажем, что оно выполняется и для $$f$$. Без потери общности мы можем предполагать, что данные элементы $$f'$$ и $$f"$$ отличны от $$f$$, т.е. имеют место редукции $$f\to g_1 \overset*\to f'$$ и $$f \to g_2 \overset*\to f"$$. Элементы $$g_1$$ и $$g_2$$ удовлетворяют псевдолокальному условию слияния при некотором~ $$s$$.

Доказательство будем вести индукцией по $$s$$. Основание индукции по $$s$$ предполагает $$s=1$$, т.е. $$g_1$$ и $$g_2$$ удовлетворяют локальному условию слияния. Из условия локального слияния следует, что существует $$g_3$$, такой, что $$g_2 \overset*\to g_3$$ и $$g_1 \overset*\to g_3.$$ По предположению внешней индукции для элементов $$f'$$ и $$g_3$$ существует элемент $$g_4$$, такой, что $$f' \overset*\to g_4$$ и $$g_3 \overset*\to g_4$$, а также элемент $$g_5$$, такой, что $$f" \overset*\to g_5$$ и $$g_4 \overset*\to g_5$$. Этот элемент удовлетворяет условию леммы (см. рис 6.1).

(рис 6.2) (рис 6.1)

Переход от $$s$$ к $$s+1$$ иллюстрируется следующей диаграммой (рис 6.2). Пусть $$g_1$$ и $$g_2$$ удовлетворяют псевдолокальному условию слияния с цепочкой из $$s+2$$ элементов: $$\smu{1} g_1 =f_0 , f_1 , \dots, f_s , f_{s+1}=g_2$$. По предположению индукции элементы $$f_1$$ и $$g_2$$ удовлетворяют условию слияния (элемент $$g_4$$ ). Существование элементов $$g_5$$, $$g_6$$ и $$g_7$$ в приведенной диаграмме следует из предположения о том, что элементы, которые получены редукцией элементов, следующих за $$f$$, в частности, $$g_1 ,f_1 ,g_2$$, удовлетворяют условию слияния.

Следующая теорема перечисляет ряд условий, которые равносильны определению базиса Гребнера. Следует отметить, что среди них содержатся условия (6') и (7') и , позволяющие за конечное число шагов проверить, является ли выписанная система образующих подмодуля $$M$$ его базисом Гребнера.

9.33. ТЕОРЕМА. Пусть $$F$$ - свободный $$D$$ -модуль, $$M\subseteq F$$ - его $$D$$ -подмодуль, $$G \subset M$$ - конечное множество, - ранжир на множестве термов $$T_F$$. Предположим, что множество $$G$$ нормализовано таким образом, что $$\textrm{Hcoeff}(g_i) = 1$$ для всех $$g_i\in G$$. Тогда эквивалентны следующие условия:

(1) $$G$$ является $$G$$ -базисом модуля $$M$$ ;

(1') любой элемент модуля $$M$$ допускает нормальное $$G$$ -представление;

(2) $$\textbf{u}_G$$ порождает $$\textbf{u}_M$$ ;

(3) для любого $$f \in M$$ имеет место $$f\overset *{\underset G\to} 0$$ ;

(3') для любого $$f \in M$$ имеет место $$f\overset *{\underset G\Longrightarrow} 0$$ ;

(4) если $$f - f' \in M$$ и $$f, f'$$ нередуцируемы, то $$f = f'$$ ;

(5) если $$f \in M$$ и $$f$$ нередуцируем, то $$f = 0$$.

Следующие условия являются необходимыми для выполнения предыдущих, и, если множество $$G$$ порождает $$M$$, то они являются и достаточными:

(6) если $$f, f' \in G$$ и $$S(f,f') \neq 0$$, то $$S(f,f')$$ допускает $$G$$ -представление;

(6') если $$f,f' \in G$$ и $$S(f,f') \neq 0$$, то $$S(f,f')$$ допускает нормальное $$G$$ -представление;

(7) если $$f,f' \in G$$ и $$НОД(\textbf{u}_f,\textbf{u}_{f'})$$ определен, то в $$G$$ существуют элементы $$f=f_0,\dots,f_i,\dots,f_s = f'$$, такие, что$$\begin{equation} НОД \{\textbf{u}_{f_i}: i=0,\dots,s\}=НОД (\textbf{u}_f,\textbf{u}_{f'}) \qquad \qquad \ecno(9.7) \end{equation}$$ и каждый $$S$$ -элемент $$S(f_{i-1}, f_i )$$, $$i=1,\dots,s$$, допускает $$G$$ -представление;

(7') если $$f,f' \in G$$ и $$НОК(\textbf{u}_f, \textbf{u}_{f')$$ определен, то в $$G$$ существуют элементы $$f=f_1,\dots,f_i,\dots,f_s = f'$$, удовлетворяющие условию (9.7), такие, что каждый $$S$$ -элемент $$S(f_{i-1}, f_i )$$, $$i=1,\dots, s$$, допускает нормальное $$G$$ -представление;

(8) если $$f\overset*{\underset G\to}f'$$, $$f\overset*{\underset G\to}f"$$ и $$f'$$ и $$f"$$ нередуцируемы, то $$f'=f"$$ ;

(9) если $$f\overset*{\underset G\to}f'$$, $$f\overset*{\underset G\to}f"$$, то существует элемент $$h \in F$$, такой, что $$f'\overset*{\underset G\to}h$$, $$f"\overset*{\underset G\to}h$$, т.е. $$\overset*{\underset G\to}$$ удовлетворяет условию слияния;

(10) $$S(f,f')\overset*{\underset G\to}0$$ для любых $$f,f'\in G$$ ;

(10') $$S(f,f')\overset*{\underset G\Longrightarrow}0$$ для любых $$f,f'\in G$$ ;

(11) если $$f,f' \in G$$ и $$НОК(\textbf{u}_f, \textbf{u}_{f'})$$ определен, то в $$G$$ существуют элементы $$f=f_0,\dots,f_i,\dots,f_r=f'$$, удовлетворяющие условию (9.7) и такие, что $$S(f_{i-1}, f_i)\overset*{\underset G\to}0$$ для всех $$i = 1,\dots,r$$ ;

(11') если $$f,f' \in G$$ и $$НОК(\textbf{u}_f, \textbf{u}_{f')$$ определен, то в $$G$$ существуют элементы $$f=f_0,\dots,f_i,\dots,f_r=f'$$, удовлетворяющие условию и такие, что $$S(f_{i-1}, f_i)\overset*{\underset G\Longrightarrow}0$$ для всех $$i = 1,\dots,r$$.

ДОКАЗАТЕЛЬСТВО. Докажем следующие импликации:$$\begin{align*} \quad(3) \to (10) \to (11) \\ (3') \to (10') \to (11') \to (11) \\ (3) \to (4) \to (5) \to (3') \to (3) \\ (3) \to (2) \to (1') \to (1) \to (6) \to (7) \to (11) \to (9) \to (3) \\ (1') \to (6') \to (7') \to (7) \\ (4) \to (8) \to (9) \end{align*}$$

$$(3) \to (10)$$. Тривиально, поскольку $$S(f,f') \in M$$.

$$(3') \to (10')$$. Аналогично.

$$(10) \to (11)$$. Достаточно положить $$r=1$$.

$$(10') \to (11')$$. Аналогично.

$$(11') \to (11)$$. Тривиально.

$$(3) \to (4)$$. По предложению (9.23) множество нередуцируемых элементов является векторным пространством, значит, если $$f$$ и $$f'$$ нередуцируемы, то и их разность нередуцируема. Поскольку $$f - f' \in M$$, из 3 и предыдущего замечания следует, что $$f - f' = 0$$, т.е. (4)

$$(4) \to (5)$$. Полагаем $$f' = 0$$.

$$(5) \to (3')$$. Достаточно применить леммы 9.21 и 9.22.

$$(3') \to (3)$$. Очевидно.

$$(3) \to (2)$$. Пусть $$u \in M$$ и $$\textbf{u}_u \notin(\textbf{u}_G)$$. Тогда элемент $$u$$ не может редуцироваться к 0, что противоречит (3).

$$(2) \to (1')$$. Пусть существуют $$0 \neq u \in M$$, для которых нет нормального $$G$$ -представления. Среди таких элементов выберем элемент с минимальным $$\textbf{u}_u$$. По условию (2) можно применить шаг редукции, сокращающий $$\textbf{u}_u$$. Полученное противоречие с минимальностью $$\textbf{u}_u$$ доказывает (1')).

$$(1')\to (1)$$. Очевидно.

$$(1) \to (6)$$. Достаточно заметить, что если $$f \in G$$, $$f' \in G$$, то $$S(f,f') \in M$$.

$$(1')\to (6')$$. Аналогично.

$$(6) \to (7)$$. Очевидно.

$$(6') \to (7')$$. Также очевидно.

$$(7') \to (7)$$. Очевидно.

$$(7) \to (11)$$. Пусть $$1\le i\le r$$, $$u=S(f_{i-1},f_i)$$ и $$u=\sum\limits_{j=1}^rc_j\theta_jg_j$$, $$0\ne c_j\in K$$, $$\theta_j \in T(X)$$, $$g_j\in G$$, $$\theta_i\textbf{u}_{g_i}>\theta_{i+1}\textbf{u}_{g_{i+1}}$$ - $$G$$ -представление элемента $$u$$. Положим $$u_k =\sum\limits_{j=k}^r c_j \theta_j g_j$$. Тогда$$u=u_1 \xrightarrow[G]{} u_2 \xrightarrow[G]{}\dots \xrightarrow[G]{} u_r \xrightarrow[G]{}0.$$

$$(11) \to (9)$$. Ввиду леммы 9.32, достаточно доказать, что отношение редукции удовлетворяет псевдолокальному условию слияния. Пусть $$f \to f'$$, $$f\to f"$$. Это означает существование элементов $$g', g'' \in G$$, $$\eta ', \eta''\in T(X)$$, $$\varphi '=\eta '\textbf{u}_{g'}$$, $$\varphi''=\eta''\textbf{u}_{g''}$$, таких, что $$f' = f-c'\eta 'g'$$, $$f'' = f-c''\eta''g''$$, где $$c'=c(f,\varphi ')\neq 0$$, $$c''=c(f,\varphi'')\neq 0$$, но $$c(f',\varphi ')= c(f'',\varphi'')=0$$. Можно предполагать, что $$\varphi'' \leq \varphi'$$. Обозначим $$R(\xi ) = \xi - \textrm{Hcoeff}(\xi )\textbf{u}_\xi$$ для любого $$\xi \in F$$.

Выделим в $$f$$ слагаемое $$c'\varphi'$$, т.е. $$f = f_1 +c'\varphi '+f_2$$, где $$f_1$$ состоит из слагаемых, которые больше, чем $$c'\varphi'$$, а $$f_2$$ - из слагаемых, меньших $$c'\varphi'$$. Нужно рассмотреть два случая: $$\varphi'' <\varphi'$$ и $$\varphi''=\varphi'$$. В первом из них, полагая $$f_2''= f_2 - c''\eta''g''$$ и $$f_0 =f_1 -c'\eta 'R(g')+f_2''$$, по лемме 9.28 получаем $$f'=(f_1 -c'\eta 'R(g'))+f_2 \nabla (f_1 -c'\eta 'R(g'))+f_2''=f_0$$, откуда $$f' \nabla f''$$.

В случае, когда $$\varphi '=\varphi''$$, одновременно выполняются условия $$\textbf{u}_{g'} \ll \varphi '$$ и $$\textbf{u}_{g''} \ll \varphi''$$. Поэтому определен $$НОД(\textbf{u}_{g'}, \textbf{u}_{g''})$$. По условию 11 доказываемой теоремы в $$G$$ существует последовательность $$g' = g_0 ,\dots, g_i,\dots, g_t =g''$$, удовлетворяющая условию (9.7) и такая, что $$S(g_{i-1},g_i ) \xrightarrow{*} 0$$ для любого $$i$$. Значит, $$\textbf{u}_{g_i}\ll \varphi'$$ для любого $$i$$, поэтому существуют $$\eta _i \in T$$, такие, что $$\eta _i \textbf{u}_{g_i}= \varphi '$$, $$c'\varphi'\to -c'\eta_i R(g_i)$$ и $$f \to f_1 -c'\eta_i R(g_i)+f_2 =h_i$$, $$i=1,\dots,t$$. Покажем, что $$h_{i-1} \nabla h_i$$. Это следует из того, что$$h_i -h_{i-1} = c'\eta _{i-1}R(g_{i-1})-c'\eta _i R(g_i ) = c'\theta S(g_i,g_{i-1}) \xrightarrow{*} 0,$$ где $$\theta \in T(X)$$ и удовлетворяет условию $$\theta \cdot НОД(\textbf{u}_{g_i}, \textbf{u}_{g_{i-1}}) = \varphi'$$. Следовательно, отношение $$\to$$ удовлетворяет псевдолокальному условию слияния.

$$(9) \to (3)$$. Если множество $$G$$ порождает $$M$$, то по лемме 9.24 существуют элементы $$f=f_0,\dots, f_i,\dots, f_s =0$$, такие, что для любого $$i$$ либо $$f_{i-1}\to f_i$$, либо $$f_i\to f_{i-1}$$. Пусть $$k$$ обозначает наибольший индекс, для которого не выполняется условие $$f_i \xrightarrow{*} 0$$. Тогда $$f_{k+1}\xrightarrow{*} 0$$ и $$f_{k+1}\to f_k$$. По условию 9 $$0 \nabla f_k$$, и получаем противоречие с выбором $$k$$, поскольку $$0$$ редуцируется только в самого себя.

$$(4) \to (8)$$. $$f'-f'' = (f'-f)-(f''-f) \in M$$, следовательно, $$f'=f''$$.

$$(8) \to (9)$$. Пусть $$f \xrightarrow{*} f'$$ и $$f \xrightarrow{*} f''$$. Выберем нередуцируемые $$f_1'$$ и $$f_1''$$ такие, что $$f' \xrightarrow{*} f_1'$$, $$f''\xrightarrow{*} f''_1$$. Из (8) следует, что $$f'_1 = f_1''$$, т.е. отношение $$\to$$ удовлетворяет условию слияния.

Поскольку вопрос о $$G$$ -представимости элемента может быть решен алгоритмически, пункт (6') дает нам возможность сформулировать алгоритм проверки, является ли данная система образующих подмoдуля его базисом Гребнера. Пункт (7') этой же теоремы позволяет нам оптимизировать полученный алгоритм, проверяя $$G$$ -представимость не всего множества $$S$$ -элементов, а только некоторого его подмножества.

9.34. УПРАЖНЕНИЕ. Показать, что многочлены$$\begin{align*} f_1=x^3yz-xz^2,\\ f_2=xy^2z-xyz,\\ f_3=x^2y^2-z^2 \end{align*}$$ не составляют базис Гребнера порождаемого ими идеала (упорядочение по степени, затем обратное лексикографическое, $$x > y > z$$ ).

9.35. УПРАЖНЕНИЕ. Показать, что многочлены$$\begin{align*} f_1=x^3yz-xz^2, \quad f_6=yz^3-z^3,\\ f_2=xy^2z-xyz, \quad f_7=xyz^2-xz^2,\\ f_3=x^2y^2-z^2, \quad f_8=z^4-x^2z^2,\\ f_4=x^2yz-z^3, \quad f_9=x^3z^2-xz^2\\ f_5=xz^3-xz^2, \end{align*}$$ образуют базис Гребнера идеала, введенного в предыдущем упражнении.

9.36. УПРАЖНЕНИЕ. Показать, что, используя теорему 9.33.11, в предыдущем упражнении достаточно рассмотреть $$S$$ -элементы для пар (2,3), (2,4), (5,6), (4,7), (2,7), (5,7), (5,8), (6,8), (4,9), (5,9).

9.37. УПРАЖНЕНИЕ. Пусть $$D$$ - кольцо обобщенных многочленов над полем от конечного числа неизвестных, $$F$$ - свободный $$D$$ -модуль и ранжир на множестве термов $$T_F$$ правильный. Пусть $$H$$ - подмодуль модуля $$F$$ и $$G$$ - базис Гребнера подмодуля $$H$$. Показать, что для каждого элемента $$f\in H$$ существует представление $$f=\sum\limits_{j=1}^r\lambda_j g_j$$, где $$\lambda_j\in D,\ g_j\in G$$, такое, что $$\deg f\geq \deg\lambda_j g_j$$ для всех $$j=1,\dots,r$$.

Если данная система элементов не является базисом Гребнера порождаемого ею подмодуля, то ее можно расширить, присоединяя поочередно элементы, получающиеся редуцированием $$S$$ -элементов.

9.38. УПРАЖНЕНИЕ. Доказать конечность следующего рекурсивного алгоритма построения базиса Гребнера полиномиального идеала (алгоритм пополнения).

Алгоритм $$\textrm{Groebner}$$ ( $$\EuScript A$$ )

$$\begin{align*} \text{Дано: $\EuScript A$—конечное множество образующих идеала $I$,}\\ \text{\qquad $\Rightarrow $ — алгоритм нормальной формы.}\\ \text{Надо: $\EuScript A$ — базис Гребнера идеала $I$.}\\ \text{Начало}\\ \text{если $\exists g_1, g_2 \in \EuScript A$, такие, что $S(g_1,g_2) \overset*{\underset{\EuScript A}\implies} g'$,}\\ \text{\qquad где $g' \neq 0$ — нередуцируемый относительно $\EuScript A$ многочлен,}\\ \text{\qquad то $\textrm{Groebner}(\EuScript A \cup {g'})$}\\ \text{конец если}\\ \text{Конец} \end{align*}$$

Очевидно, что сформулированный алгоритм не является оптимальным. Учитывая роль, которую базисы Гребнера играют в компьютерной алгебре, и высокую сложность алгоритмов их построения, оптимизация этих алгоритмов приобретает особое значение. Вопросы оптимизации будут рассмотрены несколько позже.

Базис Гребнера для любого подмодуля $$M$$ определен неоднозначно. В частности, после присоединения к базису Гребнера модуля $$M$$ любого элемента $$h \in M$$ снова получаем базис Гребнера модуля $$M$$. Естественно возникает вопрос о минимальных базисах Гребнера.

Следующая терминология пришла из дифференциальной алгебры.

9.39. ОПРЕДЕЛЕНИЕ. Подмножество $$G = \{ g_i: i \in I\}$$ свободного модуля $$F$$ называется авторедуцированным множеством, если любой элемент $$g_i \in G$$ нередуцируем относительно $$G\setminus\{g_i \}$$.

Из определения немедленно следует, что лидеры всех элементов, принадлежащих авторедуцированному множеству, различны.

9.40. ПРЕДЛОЖЕНИЕ. Пусть $$D$$ - кольцо обобщенных многочленов от переменных $$X=\{x_1,\dots,x_m\}$$ над полем $$K$$ и $$F$$ - свободный $$D$$ -модуль с базисом $$E=\{e_1,\dots,e_n\}$$. Любое авторедуцированное множество в $$F$$ состоит из конечного числа элементов, следовательно, его элементы можно упорядочить по возрастанию лидеров.

ДОКАЗАТЕЛЬСТВО. Доказательство немедленно следует из леммы 12.1.

Зафиксировав ранжир < на множестве термов $$T_F$$, можно ввести отношение частичного порядка на множестве авторедуцированных множеств.

Пусть $$\A=\{a_1,\dots,a_p\}$$ и $$\B=\{b_1,\dots,b_q\}$$ - авторедуцированные множества, элементы которых упорядочены по возрастанию лидеров. Будем считать, что $$\EuScript A < \EuScript B $$, если,

либо существует $$i$$, $$1 \leq i \leq min(p,q)$$, такое, что $$\textbf{u}_{a_i}<\textbf{u}_{b_i}$$ и $$\textbf{u}_{a_j}=\textbf{u}_{b_j}$$ для всех $$j<i$$,

либо $$p >q$$ и $$\textbf{u}_{a_j} =\textbf{u}_{b_j}$$ для $$1 \leq j \leq q$$.

9.41. ЛЕММА. Любое множество $$\mathbb A=\{ \EuScript A_i,\ i\in I\}$$ авторедуцированных подмножеств содержит минимальный элемент относительно введенного частичного порядка. Минимальный элемент в множестве всех авторедуцированных подмножеств некоторого подмодуля $$M$$ свободного $$D$$ -модуля является базисом Гребнера модуля $$M$$.

ДОКАЗАТЕЛЬСТВО. По предложению 9.40 мы можем предполагать, что элементы в наших авторедуцированных множествах упорядочены по возрастанию старших термов. Зафиксируем минимальное значение лидера для первых элементов рассматриваемых авторедуцированных множеств (это значение определено однозначно, поскольку множество термов вполне упорядочено). Обозначим этот лидер $$\phi_1$$. В системе авторедуцированных множеств $$\mathbb A = \{ \EuScript A _i \mid i\in I\}$$ рассмотрим подсистему $$\mathbb A '= \{ \EuScript A_i \mid i\in I'\}$$ множеств $$\EuScript A_i=\{a^i_1,\dots,a^i_{k_i}\}$$, таких, что $$\textbf{u}_{a^i_1} = \phi_1$$. В $$\mathbb A'$$ найдем минимальное значение лидера вторых элементов, обозначим его $$\phi_2$$. Продолжая подобным образом, получим авторедуцированную систему термов, упорядоченную по возрастанию ранга их лидеров. По предложению 9.40 эта система должна обрываться на конечном шаге. Выбор системы лидеров осуществлялся таким образом, чтобы всегда существовало авторедуцированное множество, лидеры элементов которого имели вид $$\phi_1,\dots, \phi_i$$. Авторедуцированное множество, соответствующее полной системе $$\phi_1,\dots, \phi_n$$, является минимальным.

Для доказательства того, что $$A$$ - базис Гребнера модуля $$M$$, воспользуемся условием 2 теоремы 9.33 Предположим противное, тогда существует элемент $$g \in M$$, старший терм $$g$$ которого редуцирован относительно $$\EuScript A$$. Можно предполагать, что он сам также редуцирован относительно $$\EuScript A$$. Рассмотрим множество$$\EuScript A'=\{a_i\in \EuScript A\mid a_i < g\}\cup\{g\}.$$ Это множество авторедуцировано и его ранг меньше ранга $$\EuScript A$$, что противоречит предположению о минимальности $$\EuScript A$$.

9.42. СЛЕДСТВИЕ. Пусть $$D$$ - кольцо обобщенных многочленов над полем, $$F$$ - свободный конечнопорожденный $$D$$ -модуль. Тогда для каждого подмодуля $$M$$ модуля $$F$$ существует базис Гребнера.

9.43. СЛЕДСТВИЕ. Всякое кольцо обобщенных многочленов над полем является (слева) нетеровым.

ДОКАЗАТЕЛЬСТВО. Как следует из следствия 9.42, во всяком левом идеале такого кольца существует базис Гребнера. Как видно из определения 9.26, базис Гребнера конечен и порождает этот идеал.

9.44. ОПРЕДЕЛЕНИЕ. Базис Гребнера $$G$$ модуля $$M \subseteq F$$ назовем авторедуцированным, если множество $$G$$ авторедуцировано.

9.45. ПРЕДЛОЖЕНИЕ. Авторедуцированный базис Гребнера модуля $$M$$ определен однозначно с точностью до умножения его элементов на константы из поля $$K$$.

ДОКАЗАТЕЛЬСТВО. Среди всех авторедуцированных подмножеств модуля $$M$$ выберем минимальное. Обозначим его $$\EuScript A$$ и предположим, что его элементы нормированы так, что все их старшие коэффициенты равны 1. Покажем, что этим условием множество $$\EuScript A$$ определено однозначно и что оно является базисом Гребнера модуля $$M$$.

Предположим, что $$\EuScript A = \{a_1,\dots, a_r \}$$ и $$\EuScript B = \{b_1,\dots,b_s\}$$ - два множества, удовлетворяющих сформулированным выше условиям. Из условия минимальности следует, что $$r=s$$ и $$\textbf{u}_{a_i} =\textbf{u}_{b_i}$$ для любого $$i$$. Предположим, что существует $$i$$, для которого $$a_i \neq b_i$$. Ненулевой элемент $$a_i -b_i\in M$$ редуцирован относительно $$a_j$$ для $$j < i$$, поскольку нередуцируемость зависит только от множеств лидеров для $$\EuScript A$$ и $$\EuScript B$$, а эти множества лидеров совпадают. По лемме 9.41 $$\EuScript A$$ - базис Гребнера модуля $$M$$, что противоречит нетривиальности элемента $$a_i-b_i$$.

9.46. ОПРЕДЕЛЕНИЕ. Пусть $$\EuScript B=\{b_1,\dots,b_s\}$$ - $$G$$ -базис модуля $$M \subseteq F$$, относительно некоторого упорядочения термов из $$T_F$$. Назовем базис $$\EuScript B$$ редуцируемым, если для некоторого $$i$$, $$1\leq i\leq s$$, существует $$G$$ -представление $$b_i = \smash[b]{\sum\limits_{j\neq i}} c_j b_j$$, в противном случае $$\EuScript B$$ называем нередуцируемым.

9.47. ОПРЕДЕЛЕНИЕ. $$G$$ -базис $$\EuScript B$$ модуля $$M$$, содержащий $$s$$ элементов, назовем минимальным, если не существует $$G$$ -базиса $$\EuScript B'$$ модуля $$M$$, содержащего менее $$s$$ элементов.

9.48. ПРЕДЛОЖЕНИЕ. Понятия минимальности и нередуцируемости $$G$$ -базисов совпадают. Каждый авторедуцированный $$G$$ -базис минимален, и каждый минимальный $$G$$ -базис квазиавторедуцирован, т.е. множество его лидеров авторедуцировано (это множество определяется модулем $$M$$ однозначно).

ДОКАЗАТЕЛЬСТВО. Очевидно, что редуцируемый $$G$$ -базис не является минимальным. Таким образом для доказательства предложения достаточно показать, что лидеры элементов нередуцируемого базиса определены однозначно. Доказательство проходит во многом аналогично доказательству предложения 9.45 и оставляется читателю в качестве самостоятельного упражнения.

9.49. ПРИМЕРЫ.

Пусть $$K$$ - поле и $$m=0$$. Если матрица системы линейных многочленов приведена к ступенчатому виду, т.е. нет строк, которые начинаются с одного и того же столбца, то эта система представляет собой базис Гребнера порождаемого ею модуля. Показать, что обратное, в общем случае, неверно, т.е. могут существовать базисы Гребнера векторного подпространства, первые ненулевые элементы различных векторов которых стоят в одном и том же столбце.

Пусть $$K$$ - поле, $$n=m=1$$. Множество $$\EuScript B $$ является базисом Гребнера порождаемого им идеала тогда и только тогда, когда оно содержит НОД всех своих элементов. Минимальный базис Гребнера в этом случае состоит из одного элемента.

Базис Гребнера в упражнении 9.35 не является минимальным. После удаления из него первого элемента он становится минимальным и даже авторедуцированным.

9.50. УПРАЖНЕНИЕ. Показать, что система алгебраических уравнений не имеет решений в алгебраическом замыкании поля коэффициентов тогда и только тогда, когда базис Гребнера идеала, порожденного этой системой, содержит константу.

9.51. УПРАЖНЕНИЕ. Показать, что система алгебраических уравнений из $$K[x_1,\dots,x_n ]$$ имеет конечное множество решений в алгебраическом замыкании поля коэффициентов тогда и только тогда, когда базис Гребнера идеала, порожденного этой системой, содержит для любого $$i=1,\dots,n$$ многочлен со старшим мономом, являющимся степенью $$x_i$$.

9.52. УПРАЖНЕНИЕ. Построить теорию базисов Гребнера для идеалов в кольце многочленов с коэффициентами из кольца $$\mathbb Z $$.

Инволютивные базисы

Напомним основные определения и результаты теории базисов Гребнера в простейшей постановке, т. е. для полиномиальных идеалов.

Пусть $$K$$ - поле, $$R=K[x_1,\dots,x_n]$$ - кольцо многочленов над полем $$K$$, $$I$$ - идеал кольца $$R$$. Как идеал $$I$$, так и фактор-кольцо $$R/I$$ являются линейными $$K$$ -пространствами, в общем случае бесконечномерными. Как найти базисы этих пространств? В кольце $$R$$, рассматриваемом как $$K$$ -пространство, имеется базис, состоящий из множества $$T$$ всех мономов. Естественно попытаться разбить множество $$T$$ на две части $$T=T_1\cup T_2$$ так, что образы элементов из $$T_1$$ в фактор-кольце $$R/I$$ образуют базис $$K$$ -пространства $$R/I$$, а элементы базиса $$K$$ -пространства $$I$$ находятся во взаимно-однозначном соответствии с элементами множества $$T_2$$.

Предположим, что на множестве мономов задан допустимый порядок, т.е. отношение $$<$$, удовлетворяющее условиям:

$$1<m$$ для любого нетривиального монома $$m$$ ;

если мономы $$t_1$$ и $$t_2$$ удовлетворяют соотношению $$t_1<t_2$$, то $$t_1m<t_2m$$ для любого монома $$m$$.

Таким образом для любого многочлена $$f$$ можно определить его старший моном $$\textrm{lm}(f)$$ и старший коэффициент $$\textrm{lcoef}(f)$$, и множество мономов $$T$$ разбивается на два подмножества: $$T_1$$ состоит из мономов, которые не являются старшими мономами ни для одного элемента $$f\in I$$, и $$T_2$$ состоит из мономов, которые являются старшими мономами для элементов из $$I$$.

Теперь возникает вопрос: как описать множества $$T_1$$ и $$T_2$$ конструктивно?

Ответ на него, а также на многие другие вопросы конструктивной теории полиномиальных идеалов, дает теория базисов Гребнера. Имеется несколько эквивалентных определений базисов Гребнера (см., или , в стр.40] эти определения рассматриваются с учетом выбора алгоритма нормальной формы). Например, множество $$G\subset I$$ называется базисом Гребнера идеала $$I$$, если любой элемент $$f\in I$$ допускает представление вида $$f=\sum\limits_{i=1}^N c_im_ig_i$$, где $$c_i\in K$$, $$m_i\in T$$, $$g_i\in G$$ и выполнено условие $$\lm(m_ig_i)>\lm(m_jg_j)$$ при $$j>i$$ (представление такого вида называется $$G$$ -представлением). Это определение, во-первых, не является конструктивным, во-вторых, определяет базис Гребнера неоднозначно. Конструктивный метод построения базиса Гребнера дает алгоритм пополнения (см.упражнение 9.38). Для того, чтобы выделить из всех базисов Гребнера некоторый однозначно определенный, введем понятие авторедуцированного множества.

Множество многочленов $$G=\{g_\alpha:\alpha\in \mathbb I \}$$ называется авторедуцированным, если для любого $$\alpha\in \mathbb I $$ ни один из одночленов, входящих в $$g_\alpha$$ с ненулевым коэффициентом, не делится ни на один из мономов $$\lm(g_\beta)$$ для $$\beta\ne\alpha$$. Базис Гребнера, который является авторедуцированным множеством и старшие коэффициенты элементов которого равны 1, определен однозначно для любого идеала $$I$$. Назовем такой базис авторедуцированным базисом Гребнера.

Предположим, что мы знаем авторедуцированный базис Гребнера $$G$$ идеала $$I$$. Чтобы получить базис $$I$$ как линейного пространства, нам достаточно указать процедуру, которая каждому моному $$m\in T_2$$ ставит в соответствие некоторый элемент $$g(m)\in G$$, старший моном которого делит $$m$$, т.е. $$m=t(m)\cdot \textrm{lm}(g(m))$$ для некоторого монома $$t(m)$$. Тогда множество многочленов $$t(m)\cdot g(m)\ |\ m\in T_2$$ образует базис линейного пространства $$I$$. Любую такую процедуру назовем алгоритмом нормальной формы.

10.1. ПРИМЕР. Простейший алгоритм нормальной формы состоит в том, что элементы авторедуцированного базиса Гребнера нумеруются в каком-либо порядке индексами от 1 до $$k$$ и каждому моному $$m\in T_2$$ ставится в соответствие элемент $$g_i$$ с минимальным индексом, такой, что $$\textrm{lm}(g_i)|m$$. Существуют, однако, и более сложные алгоритмы нормальной формы.

Рассмотрим этот пример подробнее. Пусть авторедуцированный базис Гребнера идеала $$I$$ состоит из многочленов $$g_1,\dots,g_k$$. Тогда базис линейного пространства $$I$$ получается объединением следующих множеств множества $$\EuScript B_1$$ всех произведений $$m\cdot g_1$$, где $$m\in T$$ ; множества $$\EuScript B_2$$ произведений $$m\cdot g_2$$, таких, что $$\textrm{lm}(m\cdot g_2)\notin \textrm{lm}(\EuScript B_1)$$ ; множества $$\EuScript B_3$$ произведений $$m\cdot g_3$$, таких, что $$\textrm{lm}(m\cdot g_3)\notin \textrm{lm}(\EuScript B_1)\cup\textrm{lm}(\EuScript B_2)$$ ; $$\ldots$$ множества $$\EuScript B_k$$ произведений $$m\cdot g_k$$, таких, что $$\textrm{lm}(m\cdot g_k)\notin \bigcup\limits_{i=1}^{k-1}\textrm{lm}(\EuScript B_i)$$.

Этот же базис можно описать несколько по-другому.

Для каждого $$g_i$$ выделим максимальное подмножество переменных $$x_{i_1},\dots,x_{i_s}$$ такое, что произведение $$g_i$$ на любой моном, включающий только эти переменные (обозначим множество таких мономов $$S(g_i)$$ ), принадлежит $$\EuScript B_i$$. Назовем эти переменные мультипликативными для монома $$\textrm{lm}(g_i)$$, остальные переменные назовем немультипликативными. Исключим из $$\EuScript B_i$$ моном $$g_i$$ и все его произведения на мономы из $$S(g_i)$$. Если полученное множество непусто, то возьмем в нем младший моном $$g'_i$$ и повторим процесс для него. Таким образом мы можем представить базис линейного пространства $$I$$ в виде объединения конечного набора множеств, каждое из которых описывается некоторым многочленом и набором мультипликативных переменных для этого многочлена. Полученный базис представляет собой пример инволютивного базиса. В коммутативную алгебру понятие инволютивного базиса было введено Жарковым и Блинковым , .

Итак, для построения инволютивного базиса мы воспользовались базисом Гребнера, алгоритмом нормальной формы и процедурой разделения переменных на мультипликативные и немультипликативные для некоторого набора мономов.

Напомним алгоритмы проверки того, что заданное множество является базисом Гребнера порождаемого им идеала и построения базиса Гребнера по заданной системе образующих идеала $$I$$ (этот алгоритм называется алгоритмом пополнения ).

Пусть дано множество многочленов $$G$$ и отношение порядка на множестве мономов $$<$$. Для проверки того, что $$G$$ является базисом Гребнера идеала $$I=(G)$$ относительно порядка <, используется некоторый алгоритм нормальной формы, от выбора которого результат не зависит. Алгоритм состоит в том, что формируется множество $$S$$ -полиномов и проверяется, что каждый из этих полиномов редуцируется к нулю. Для повышения эффективности алгоритма используются различные критерии, позволяющие сузить круг рассматриваемых $$S$$ -полиномов, например, "правило треугольника".

Как сказано выше, множество многочленов $$G=\{g_1,\dots,g_k\}$$ и алгоритм нормальной формы позволяют сформировать множества $$\EuScript B_i$$, каждое из которых получается путем умножения многочлена $$g_i$$ на некоторое множество мономов. $$S$$ -полиномы соответствуют многочленам $$g_i$$ и мономам $$m_i$$, таким, что $$m_i$$ является минимальным (относительно деления мономов) мономом, для которого $$m_i\cdot g_i\notin \EuScript B_i$$. В действительности, проверять редуцируемость к нулю нужно только для таких многочленов (заметим, что при этом рассматриваются не все $$S$$ -полиномы, автоматически используется "правило треугольника"). Естественно потребовать, чтобы множество $$G$$ было авторедуцированным.

Алгоритм пополнения основан на описанном выше методе $$S$$ -полиномов и отличается от приведенного выше алгоритма тем, что в случае нередуцируемости $$S$$ -полинома его нормальная форма добавляется к множеству $$G$$. При этом, как правило, меняется алгоритм нормальной формы, т.е. множества $$\EuScript B_i$$, описанные выше.

Как правило, для повышения эффективности алгоритмов построения базисов Гребнера совершенствуются методы перебора $$S$$ -полиномов, но мало внимания уделяется рассмотрению возможных алгоритмов нормальной формы.

До настоящего момента мы никак не ограничивали выбор алгоритма нормальной формы, т.е. формирование множеств $$\EuScript B_i$$ для заданной системы многочленов $$G=\{g_i\}$$. Теперь предположим, что на множестве мономов задано некоторое отношение "делимости" $$|_L$$, удовлетворяющее следующим аксиомам (аксиомы глобального инволютивного деления, см., например, :

$$u|_L v\implies u|v$$ (в смысле обычного деления);

$$1|_L u$$ ;

$$u|_L w\wedge v|_L w\implies u|_L v\vee v|_L u$$ ;

$$u|_L uvw\iff u|_L uv\wedge u|_L uw$$ ;

$$u|_L v\wedge v|_L w\implies u|_L w$$ (транзитивность).

В случае, если имеет место отношение $$u\bigr|_Lv$$, мы будем говорить, что $$u$$ инволютивно делит $$v$$.

Аксиомы 3 и 4 для случая двух переменных можно наглядно представить следующим образом.

Изобразим мономы вида $$x^iy^j$$ на плоскости точками с координатами $$(i,j)$$. Тогда

множества инволютивных кратных для любых двух мономов либо не пересекаются, либо одно из них содержится в другом;

множество кратных монома $$x^iy^j$$ представляется либо одной точкой $$(i,j)$$, либо вертикальным или горизонтальным лучом, выходящим из этой точки, либо углом между вертикальным и горизонтальным лучами, выходящими из этой точки.

Обобщение на случай нескольких переменных очевидно.

10.2. УПРАЖНЕНИЕ. Показать, что глобальное инволютивное деление определяет для каждого монома $$u$$ множество $$M(u)$$ его мультипликативных переменных как множество таких переменных, что $$u$$ инволютивно делит любое произведение $$u$$ на моном, включающий только мультипликативные переменные. Остальные переменные назовем немультипликативными для монома $$u$$ (обозначение $$NM(u)$$ ).

Примеры глобальных инволютивных делений:

$$M(x_1^{i_1}\dots x_k^{i_k})=\{x_k,\dots,x_n\}$$ - правое деление Поммаре.

$$M(x_k^{i_k}\dots x_n^{i_n})=\{x_1,\dots,x_k\}$$ - левое деление Поммаре.

$$M(x_1^{i_1}\dots x_n^{i_n})=\{x_k\ :\ i_k=\max_{m=1}^n i_m\}$$.

Для двух переменных правое и левое деление Поммаре можно проиллюстрировать следующим образом:

$$\begin{picture}(120,120) \multiput(0,0)(20,0){7}% {\multiput(0,0)(0,20){7}{\put(0,0){\circle*{2}}}} \multiput(0,0)(20,0){6}{\put(0,0){\vector(1,0){18}}} \multiput(0,0)(20,0){7}% {\multiput(0,0)(0,20){6}{\put(0,0){\vector(0,1){18}}}} \end{picture}$$ $$\begin{picture}(120,120) \multiput(0,0)(20,0){7}% {\multiput(0,0)(0,20){7}{\put(0,0){\circle*{2}}}} \multiput(0,0)(0,20){6}{\put(0,0){\vector(0,1){18}}} \multiput(0,0)(0,20){7}% {\multiput(0,0)(20,0){6}{\put(0,0){\vector(1,0){18}}}} \end{picture}$$

Для третьего примера геометрическая интерпретация выглядит следующим образом:

$$\begin{picture}(120,120) \multiput(0,0)(20,0){7}% {\multiput(0,0)(0,20){7}{\put(0,0){\circle*{3}}}} \multiput(0,0)(20,0){6}{\put(0,0){\vector(1,0){18}}} \multiput(0,0)(0,20){6}{\put(0,0){\vector(0,1){18}}} \multiput(20,20)(20,0){5}{\put(0,0){\vector(1,0){18}}} \multiput(20,20)(0,20){5}{\put(0,0){\vector(0,1){18}}} \multiput(40,40)(20,0){4}{\put(0,0){\vector(1,0){18}}} \multiput(40,40)(0,20){4}{\put(0,0){\vector(0,1){18}}} \multiput(60,60)(20,0){3}{\put(0,0){\vector(1,0){18}}} \multiput(60,60)(0,20){3}{\put(0,0){\vector(0,1){18}}} \multiput(80,80)(20,0){2}{\put(0,0){\vector(1,0){18}}} \multiput(80,80)(0,20){2}{\put(0,0){\vector(0,1){18}}} \put(100,100){\vector(1,0){18}} \put(100,100){\vector(0,1){18}} \end{picture}$$

10.4. УПРАЖНЕНИЕ. В кольце многочленов $$K[x,y,z]$$ найти мультипликативные и немультипликативные переменные для мономов $$x^5$$, $$x^3y^2$$, $$xyz$$ для каждого из глобальных инволютивных делений, рассмотренных в примерах 10.3.

Можно рассмотреть более общую ситуацию, когда фиксировано некоторое конечное множество $$U$$ мономов, а инволютивное деление зависит от этого множества. При этом в левой части отношения $$u|_{L^V}$$ могут стоять только мономы из множества $$U$$.

10.5. ОПРЕДЕЛЕНИЕ. Согласно , на моноиде $$M$$ задано инволютивное деление $$L$$, если для каждого конечного подмножества $$U\subset M$$ и для каждого монома $$u\in U$$ определен подмоноид $$L(u,U)$$ моноида $$M$$, удовлетворяющий следующим условиям:

Если $$w\in L(u,U)$$ и $$v|w$$, то $$v\in L(u,U)$$ ;

Если $$u,v\in U$$ и $$uL(u,U)\cap vL(v,U)\ne\emptyset$$, то $$u\in vL(v,U)$$ или $$v\in uL(u,U)$$ ;

Если $$v\in U$$ и $$v\in uL(u,U)$$, то $$L(v,U)\subseteq L(u,U)$$ ;

Если $$V\subseteq U$$, то $$\forall\;u\in V$$ $$L(u,U)\subseteq L(u,V)$$.

Образующие моноида $$L(u,U)$$ называются мультипликативными переменными для $$u$$. Если $$w\in uL(u,U)$$, то пишут $$u|_{L^V}$$, и моном $$u$$ называется ( $$L$$ )- инволютивным делителем монома $$w$$ а моном $$w$$ называется ( $$L$$ )- инволютивным кратным монома $$u$$. В этом случае равенство $$w=uv$$ мы будем записывать в виде $$w=u\times v$$, в противном случае - в виде $$w=u\cdot v$$, и моном $$v$$ будем называть немультипликативным для $$u$$.

10.6. УПРАЖНЕНИЕ. Показать, что глобальное инволютивное деление является инволютивным делением в смысле определения 10.5.

10.7. ОПРЕДЕЛЕНИЕ. Мы говорим, что многочлен $$f$$ инволютивно редуцируется к многочлену $$g$$ с помощью многочлена $$h$$ по моному m и пишем, опуская упоминание о мономе $$m$$, $$f\xrightarrow[\text{inv}h]{}g$$, если $$f$$ редуцируется к $$g$$ в обычном смысле, и $$\textrm{lm}(h)|_Lm$$. Естественным образом определяется отношение $$\xrightarrow[\text{inv }G]{}$$ для произвольного множества $$G$$ многочленов и его транзитивное $$\smash[b]{\xrightarrow[\text{inv }G]+}$$ и рефлексивно-транзитивное $$\xrightarrow[\text{inv }G]*$$ замыкания.

Если задано отношение редукции, то определена нормальная форма, которая в данном случае называется инволютивной.

Немультипликативным продолжением многочлена будем называть его произведение на некоторую немультипликативную для его старшего монома переменную.

10.8. ПРИМЕР. Пусть $$U\subset M$$ - конечное подмножество. Для каждого $$1\le i\le n$$ разделим множество $$U$$ на группы, помеченные неотрицательными целыми числами $$d_1,\ldots,d_i$$:$$[d_1,\ldots,d_i]=\{u\in U\sep d_j=\deg_j(u),\;1\le j\le i\}.$$ Переменная $$x_i$$ мультипликативна для $$u\in U$$, если $$i=1$$ и $$\deg_1(u)= \max\{\deg_1(v)\sep v\in U\}$$, или $$i>1$$, $$u\in[d_1,\ldots,d_{i-1}]$$ и $$\deg_i(u)= \max\{\deg_i(v)\sep v\in[d_1,\ldots,d_{i-1}]\}$$. (Здесь $$\deg_j$$ обозначает степень по переменной $$x_j$$.)

10.9. ОПРЕДЕЛЕНИЕ. Пусть $$R=K[x_1,\dots,x_m]$$ - кольцо многочленов от переменных $$X=\{x_1,\dots,x_m\}$$, $$I$$ - идеал кольца $$R$$, $$G \subset I$$ - конечное множество и $$|_L$$ - инволютивное деление на множестве мономов $$T$$. Множество $$G$$ называется инволютивным базисом идеала $$I$$, если для любого ненулевого элемента $$f\in I$$ имеется инволютивное представление$$\begin{equation} f=\sum_{i=1}^r c_i\theta_ig_i,\quad 0\ne c_i\in K,\ \theta_i \in T(M(\textrm{lm}(g_i))),\ g_i \in G.\label{e:inv8} % \theta_i\u_{g_i}>\theta_{i+1}\u_{g_{i+1}},\notag \end{equation}$$

10.10. ТЕОРЕМА. Пусть $$R=K[x_1,\dots,x_m]$$ - кольцо многочленов от переменных $$X=\{x_1,\dots,x_m\}$$, $$I$$ - идеал кольца $$R$$, $$G \subset I$$ - конечное множество и $$|_L$$ - инволютивное деление на множестве мономов $$T$$. Предположим, что множество $$G$$ нормализовано таким образом, что $$\textrm{Hcoeff}(g_i) = 1$$ для всех $$g_i\in G$$. Тогда эквивалентны следующие условия:

$$G$$ является инволютивным базисом идеала $$I$$ ;

$$\textbf{u}_G$$ инволютивно порождает $$\textbf{u}_I$$ ;

для любого $$f \in I$$ имеет место $$f\xrightarrow[\text{inv }G]* 0$$ ;

если $$f-f'\in I$$ и $$f,f'$$ инволютивно нередуцируемы, то $$f=f'$$ ;

если $$f\in I$$ и $$f$$ инволютивно нередуцируем, то $$f=0$$. Следующие условия являются необходимыми для выполнения предыдущих, и если множество $$G$$ порождает $$I$$, то они являются и достаточными:

Если $$f\in G$$ и $$x_i\in NM(\textrm{lm}(f))$$, то $$x_if$$ допускает инволютивное представление;

$$x_if\xrightarrow[\text{inv }G]*0$$ для любых $$f\in G$$ и $$x_i\in NM(\textrm{lm}(f))$$.

Доказательство оставляется читателю в качестве упражнения.

Инволютивный базис может быть легко построен, если мы знаем авторедуцированный базис Гребнера соответствующего идеала и инволютивное деление. Это построение сводится к домножению элементов базиса Гребнера на немультипликативные переменные.

Имея инволютивный базис $$G=\{g_i\}$$ и инволютивное деление, можно построить алгоритм нормальной формы следующим образом: для каждого многочлена $$g_i$$ образуем множество его инволютивных кратных $$\EuScript B_i$$ ; множество $$\bigcup_i \EuScript B_i$$ является базисом линейного пространства $$I$$, причем любой моном может присутствовать не более, чем в одном элементе этого базиса. Для любого многочлена $$f$$ мы можем исключать те его слагаемые, которые присутствуют в качестве старших мономов в множестве инволютивных кратных. Легко показать, что нередуцируемый многочлен, получающийся после таких исключений, не зависит от порядка этих исключений. Однако, чтобы избежать повторных исключений одного и того же монома (сразными коэффициентами), естественно проводить эти действия в порядке убывания мономов. Таким образом мы получаем алгоритм нормальной формы.

Естественно, не всякий алгоритм нормальной формы может быть получен таким образом. Возникает задача описания тех алгоритмов нормальной формы, которые определяются с помощью инволютивных базисов.

10.11. ПРЕДЛОЖЕНИЕ. Если множество старших мономов многочленов из идеала разбивается на непересекающиеся конусы так, что элементы одного конуса редуцируются по одному многочлену из базиса, то соответствующее инволютивное деление выглядит следующим образом: для вершины конуса мультипликативными являются переменные, соответствующие образующим, а внутри конуса деление задается произвольным образом.

ДОКАЗАТЕЛЬСТВО. Формально указанное инволютивное деление $$\mid_L$$ задается так: пусть $$\mid_{l_s}$$ - произвольное инволютивное деление, соответствующее конусу $$C_s$$ с вершиной в мономе $$s$$. Положим$$\forall u,v\in C_s\;u\l v\;\Leftrightarrow\; u\l_sv.$$ Если же $$\not\exists s:\; u,v\in C_s$$, то положим $$u\not\l v$$. Положим $$\forall u\;1\l u$$. Аксиомы инволютивного деления выполнены:

$$u|_L v\;\Rightarrow\;\exists s:\; u\in C_s,\,u|_{L_s}v\; \Rightarrow\;u|v$$ ;

$$1|_L u$$ - по определению $$|_L$$ ;

$$u|_{L}w ,v|_L w\;\Rightarrow\;\exists s_1,s_2:\;u,w\in C_{s_1},\, v,w\in C_{s_2}$$, но тогда $$C_{s_1}\cap C_{s_2}\ne\emptyset$$, значит, $$s_1=s_2=:s$$. Отсюда $$u|_{L_s} w,\,v\l_s w\;\Rightarrow\; u|_{L_s}w\lor v|{L_s}u\;\Rightarrow\;u|_{L} v\lor v|_L u$$ ;

$$u|_L uvw\;\Rightarrow\;\exists s:\; u|_{L_s}uvw\; \Rightarrow\;u|_{L_s}uv\land u|_{L_s}uw\;\Rightarrow\; u|_{L} uv\land u|_L uw\;\Rightarrow\; \exists s:\;u,uv,uw\in C_s,\,u|_{L_s} uv\land u|_{L_s} uw\;\Rightarrow\; u|_{L_s} uvw\;\Rightarrow\;u|_l uvw$$

$$u|_L v,\,v|_L w\;\Rightarrow\;\exists s:\;u,v,w\in C_s,\, u|_{L_s}v,\,v|_{L_s}w\;\Rightarrow\;u|_{L_s} w\;\Rightarrow\;u|_{L}w$$.

По определению $$\l$$, любой старший моном многочлена идеала инволютивно редуцируется к вершине соответствующего конуса, кроме того, инволютивная нормальная форма всегда единственна. Алгоритм нормальной формы, заданный этими конусами, устроен так же. Поэтому соответствие алгоритма нормальной формы и инволютивного деления установлено.