Понкратьев Е. В. - Элементы КА

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

Как сказано выше, множество многочленов G = {g1, . . . , gk} и алгоритм нормальной формы позволяют сформировать множества Bi, каждое из которых получается путем умножения многочлена gi на некоторое множество мономов. S-полиномы соответствуют многочленам gi и мономам mi, таким, что mi является минимальным (относительно деления мономов) мономом, для которого mi · gi / Bi. В действительности, проверять редуцируемость к нулю нужно только для таких многочленов (заметим, что при этом рассматриваются не все S-полиномы, автоматически используется “правило треугольника”). Естественно потребовать, чтобы множество G было авторедуцированным.

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

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

До настоящего момента мы никак не ограничивали выбор алгоритма нормальной формы, т. е. формирование множеств Bi для заданной системы многочленов G = {gi}. Теперь предположим, что на множестве мономов задано некоторое отношение “делимости” |L, удовлетворяющее следующим аксиомам (аксиомы глобального инволютивного деления, см., например, [22]):

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

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

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

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

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

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

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

N M (u)).

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

10.3. ПРИМЕРЫ.

(1)M (xi11 . . . xikk ) = {xk , . . . , xn} — правое деление Поммаре.

(2)M (xikk . . . xinn ) = {x1, . . . , xk} — левое деление Поммаре.

(3)M (xi11 . . . xinn ) = {xk : ik = maxnm=1 im}.

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

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

6

r - r - r - r - r - r - r

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

Можно рассмотреть более общую ситуацию, когда фиксировано некоторое конечное множество U мономов, а инволютивное деление

зависит от этого множества. При этом в левой части отношения u Lv могут стоять только мономы из множества U .

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

(3)Если v U и v uL(u, U ), то L(v, U ) L(u, U );

(4)Если V U , то u V L(u, U ) L(u, V ).

Образующие моноида L(u, U ) называются мультипликативными

монома

w называется (L-)инволютивным кратным монома u. В этом случае равенство w = uv мы будем записывать в виде w = u × v, в противном случае — в виде w = u · v, и моном v будем называть

немультипликативным для u.

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

10.7. ОПРЕДЕЛЕНИЕ. Мы говорим, что многочлен f инволютивно редуцируется к многочлену g с помощью многочлена h по моному m, входящему в f , и пишем, опуская упоминание о мо-

номе m, f −−−→ g, если f редуцируется к g в обычном смысле, и

inv h

lm(h)|Lm. Естественным образом определяется отношение −−−→ для

inv G

+

произвольного множества G многочленов и его транзитивное −−−→

и рефлексивно-транзитивное замыкания.

−−−→

inv G

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

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

10.8. ПРИМЕР. Пусть U M — конечное подмножество. Для каждого 1 6 i 6 n разделим множество U на группы, помеченные неотрицательными целыми числами d1, . . . , di:

[d1, . . . , di] = {u U | dj = degj (u), 1 6 j 6 i}.

Переменная xi мультипликативна для u U , если i = 1 и deg1(u) =

= max{deg1(v) | v U }, или i > 1, u [d1, . . . , di−1] и degi(u) = = max{degi(v) | v [d1, . . . , di−1]}. (Здесь degj обозначает степень

по переменной xj .)

10.9. ОПРЕДЕЛЕНИЕ. Пусть R = K[x1, . . . , xm] — кольцо многочленов от переменных X = {x1, . . . , xm}, I — идеал кольца R, G I — конечное множество и |L — инволютивное деление на множестве мономов T . Множество G называется инволютивным базисом идеала I, если для любого ненулевого элемента f I имеется

инволютивное представление:

r

X

f = ciθigi, 0 6= ci K, θi T (M (lm(gi))), gi G. (10.1)

i=1

10.10. ТЕОРЕМА. Пусть R = K[x1, . . . , xm] — кольцо многочленов от переменных X = {x1, . . . , xm}, I — идеал кольца R,

G I — конечное множество и |L — инволютивное деление на множестве мономов T . Предположим, что множество G нормализовано таким образом, что Hcoe (gi) = 1 для всех gi G. Тогда эквивалентны следующие условия:

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

(2)uG инволютивно порождает uI ;

ритм нормальной формы, заданный этими конусами, устроен так же. Поэтому соответствие алгоритма нормальной формы и инволютивного деления установлено.

11.2. ПРЕДЛОЖЕНИЕ. Следующие соотношения выполняются для всех n, p, r N:

ДОКАЗАТЕЛЬСТВО. Справедливость равенств (11.4) и (11.5) может быть легко выведена из (11.3) индукцией по n.

Прежде чем доказывать (11.6)–(11.8), заметим, что если значения целозначных многочленов f (t) и g(t) совпадают для всех достаточно больших целых значений t, то f (t) ≡ g(t). Поэтому при доказательстве (11.6)–(11.8) мы можем (и будем) предполагать, что t Z, t > n.

Сравнивая коэффициенты при xn в тождестве (1 + x)t+k = = (1 + x)t(1 + x)k, мы получим (11.6). Для того, чтобы получить (11.7), сначала докажем, что

Теперь для завершения доказательства (11.7) достаточно воспользоваться (11.6) и (11.9):

11.3. ПРЕДЛОЖЕНИЕ. Пусть f (t) — целозначный многочлен степени m. Тогда f (t) можно представить в виде

где a0, a1, . . . , am — целые числа, однозначно определенные многочленом f (t).

где рациональные числа a0, a1, . . . , am однозначно определены мно-

гочленом f (t). Нам нужно показать, что ai Z (i = 0, 1, . . . , m). Будем это делать индукцией по m = deg f (t).

Если m = 0, то из целозначности многочлена f (t) следует, что f (t) = a0 Z. Предположим, что m > 0 и существование

иоднозначность представления (11.11) (с целыми коэффициентами

a0, a1, . . . , am) доказана для всех целозначных многочленов степени меньшей m. Рассматривая конечные разности обеих частей (11.12)

ииспользуя (11.10), мы получаем

Многочлен kf (t) является целозначным, следовательно, mf (t) = = am Z. Применяя предположение индукции к многочлену f (t) −