ПРОГРАММИРОВАНИЕ, 2009, № 2, с. 28-42
— КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
ПЕРЕЧИСЛЕНИЕ КОНЕЧНЫХ МОНОМИАЛЬНЫХ УПОРЯДОЧЕНИЙ И КОМБИНАТОРИКА УНИВЕРСАЛЬНЫХ БАЗИСОВ ГРЕБНЕРА
© 2009 г. Н. Н. Васильев1, Д. А. Павлов2
1 Санкт-Петербургское отделение Математического института им. В.А. Стеклова РАН 191011 Санкт-Петербург, Набережная Фонтанки, 27 2 Санкт-Петербургский государственный политехнический университет 195251 Санкт-Петербург, Политехническая ул, 29 E-mail: dmitry.pavlov@gmail. com Поступила в редакцию 31.05.2008 г.
Целью настоящей работы является анализ различных классов конечных и бесконечных мономи-альных упорядочений. Понятие мономиального упорядочения играет ключевую роль в теории базисов Гребнера: каждый базис определяется некоторым допустимым упорядочением. В то же время, для того, чтобы определить базис Гребнера, не обязательно знать упорядочение всех мономов - достаточно знать только конечный отрезок данного упорядочения. Мы рассматриваем комбинаторику конечных мономиальных упорядочений и ее связь с ячейками универсального базиса Гребнера.
Для каждого рассмотренного класса упорядочений (слабодопустимых, выпуклых и допустимых) представлен алгоритм перебора конечных упорядочений и получены комбинаторные числовые последовательности .
Представлен алгоритм, позволяющий для произвольного базиса Гребнера вычислить все минимальные конечные упорядочения, которые полностью определяют этот базис.
Представлен алгоритм, вычисляющий расширенный универсальный базис Гребнера произвольного нульмерного идеала.
1. ВВЕДЕНИЕ
Классическая теория базисов Гребнера основана на рассмотрении допустимых упорядочений мономов. Однако, она может быть обобщена различными способами на другие упорядочения, не являющиеся допустимыми [1, 2]. Кроме того, для однозначного задания базиса Гребнера упорядочение не обязательно должно быть полным; достаточно некоторой конечной подпоследовательности мономов.
Для каждого конкретного базиса Гребнера мы изучаем минимальные конечные упорядочения мономов, которые полностью определяют этот базис. В некотором смысле, набор таких конечных мономиальных упорядочений определяет ячейку веера Гребнера.
Кроме допустимых упорядочений, мы рассматриваем так называемые слабодопустимые упорядочения, согласованные только с делением мономов. Конечные слабодопустимые упорядочения в точности соответствуют многомерным таблицам Юнга, а бесконечные - некоторым путям в графе Юнга. Таким образом, комбинаторика мономиальных упорядочений тесно связана с комбинаторикой таблиц и диаграмм Юнга [3, 4].
2. ОБОЗНАЧЕНИЯ
Обозначим за М множество мономов от с1 переменных. Множество переменных обозначим V: V = {ж1,..., х^]. М стандартным образом
Рис. 1. Конечное слабодопустимое упорядочение 1 < х < у < у2 < ху < х2 < ху2 < х2у < х3 и соответствующая ему таблица Юнга. Жирным обведена форма таблицы Юнга, т.е. диаграмма Юнга.
отождествляется с октантом в целочисленной решетке .
Мы будем рассматривать упорядочения на множестве М, как полные (например, лексикографический порядок), так и конечные (например: 1 <х<у<х2<ху< у2).
Определение 1. Полное упорядочение < называется слабодопустимым, когда оно удовлетворяет условию:
V ГП\, ТО2 € М ТО1|ТО2 => ГП\ < ТТ12 • (1)
Определение 2. Полное упорядочение < называется выпуклым, когда оно удовлетворяет условию:
V тем ЩМ\М<т) П М<т = 0. (2)
% обозначает выпуклую оболочку в а
М<т - множество мономов, которые не больше то.
Определение 3. Полное упорядочение < называется допустимым, когда оно удовлетворяет условию:
V ТО, ТП\, ТО2 € М ТП\ < ТО2 => ТОТО1 < ТОТО-2. (3)
Определение 4. Конечным слабодопустимым (выпуклым, допустимым) упорядочением степени п называется цепочка М' = (то1, ..., тп), удовлетворяющая условию слабодопустимого (выпуклого, допустимого) упорядочения и содержащая с каждым мономом все его делители:
V тем Зт' е М' : то|то' то € М'. (4)
Определение 5. Конечное упорядочение называется строгодопустимым, если оно является началом некоторого бесконечного допустимого упорядочения.
Каждое конечное слабодопустимое упорядочение задает некоторую (многомерную) таблицу Юнга размерности с1 (и задается такой таблицей), а множество элементов определяет форму таблицы Юнга, т.е. диаграмму Юнга.
Утверждение 1. Каждое допустимое упорядочение является выпуклым. Каждое выпуклое упорядочение является слабодопустимым. Это верно как для полных, так и для конечных упорядочений.
Нетрудно показать, что каждое конечное выпуклое упорядочение является начальным отрезком некоторого бесконечного выпуклого упорядочения. Для слабодопустимых упорядочений аналогичный факт очевиден.
Замечание 1. Не каждое конечное допустимое упорядочение является строгодопустимым, что показывает следующий пример:
1 < х < х2 < у < у2.
Предположим, что это строгодопустимое упорядочение. Моном ху не входит в цепочку, следовательно, у2 < ху, что невозможно по условию (3), поскольку х < у.
Замечание 2. Существуют также непро-должаемые конечные допустимые упорядочения, например,
1 < х < у < х2 < ху < х2у.
Рис. 2. Один шаг алгоритма перебора конечных слабодопустимых упорядочений. М& = = (1, ж, х2, у, ху, у2, х2у). Ск = {у3,ху2, х3}.
По условию (4) данная цепочка может быть продолжена одним из двух мономов: х3 или у2. Однако, оба продолжения нарушают условия допустимости (3).
Четыре последующих раздела будут посвящены перечислительной комбинаторике указанных классов упорядочений.
3. ПЕРЕБОР КОНЕЧНЫХ СЛАБОДОПУСТИМЫХ УПОРЯДОЧЕНИЙ
Рассмотрим задачу перебора всех слабодопустимых конечных упорядочений фиксированной степени п. Ввиду того, что первые к элементов (к < п) любого из них также составляют конечное упорядочение, перебор мы сделаем рекурсивной процедурой. Начнем с упорядочения (1), оно очевидно является слабодопустимым. Его можно продолжить (в случае V = {х,у}) двумя способами: (1,ж) и (1 ,у). (1,ж) дает начало упорядочениям (1 ,х,у) и (1,ж,ж2), и т.д.
Предположим, у нас есть Мк - цепочка мономов, упорядоченных в соответствии с критерием "слабой допустимости". Из условия (1) видно, что моном продолжающий эту це-
почку, может быть выбран из М\Мк с тем единственным условием, что он не делится никаким
другим мономом из М\Мь- Полный набор таких мономов конечен согласно лемме Диксона. Обозначим его С к-
Очевидно, что Со = {1}, так как М\Мо = М. Из Ск и то^_1-1 не составит труда получить Ск+1 удалением самого то^_|_1 и добавлением мономов вида {тк-ци | V £ V}, за исключением тех мономов, которые имеют делители в СДт^-ц.
4. ПЕРЕБОР КОНЕЧНЫХ ВЫПУКЛЫХ УПОРЯДОЧЕНИЙ
Поскольку любое конечное выпуклое упорядочение является конечным слабодопустимым упорядочением, к задаче перебора конечных выпуклых упорядочений степени п применимы все рассуждения и выводы предыдущего раздела. Модификация заключается в том, что на выбор тк-1-1 € Ск накладывается дополнительное ограничение, связанное с условием (2) на множество М\Мк+1-
Vто е Мк+1 т £ ЩМ\Мк+1). (5)
Множество М\Мк+1 бесконечно; его выпуклая оболочка - это часть октанта, ограниченная гиперплоскостями. Назовем множество этих гиперплоскостей Нормаль п(К) ка-
ждой гиперплоскости К 6 Нк+\ направлена в сторону отрицательного октанта:
У/г. € Нк+1 V 0 < г < (I щ(к) < 0. (6)
Пусть в1дп{к, т) - расстояние от точки , соответствующей моному то, до гиперплоскости /г, со знаком "—", если точка находится под гиперплоскостью. Преобразуем условие (5) к эквивалентному:
Vто 6 Мк+1 3/г 6 Нк~ы : в1дп(к, то) > 0. (7)
Любой моном из М\Мк~|-1 делится хотя бы на один с 6 С к-ы • Исходя из геометрических свойств этих множеств, можно заключить, что каждая гиперплоскость /г 6 Нк+\ построена на А точках, соответствующих мономам из Ск+1-
УИ е Нк+1 3{сь ..., с^} С Ск+1 :
||С1, - - -, с^П Ф 0, (8)
V 0 < ! < (I вгдп^к, сг) = 0.
procedure BuildNextC(Cfc, mk+i)
C'k+i Ck\mk+1
for all v £ V do
if /Эс G Cfc : c|mjt+iu then
Cfc+i Cfc+i u
end if end for return Ck+i
procedure EnumerateWeakAdmissibleOrders(Mfc, Ck) if к = n then
yield Mk else
for all с G Ck Мк+1 <r-Mk + c Ck+1 BuildNextC(Cfc,c)
Enumerate Weak AdmissibleOrders Cjt+i)
end for end if
Рис. 3. Алгоритм перебора конечных слабодопустимых упорядлчений.
Рис. 4. Один шаг алгоритма перебора конечных выпуклых упорядочений. Мк = (1, х, у, х2,х3,ху,у2). Бк = {у2,ху, х3}. Ск = {у3,ху2,х2у,х4}. Нк = {-х - у = 3, -х - 2у = 4}. Штриховкой отмечено внутреннее пространство %{М\Мк).
вляют все возможные гиперплоскости, удовлетворяющие условиям (6), (8) и (9).
Утверждение 3. Если условие (7) выполняется для множества -0^+1 неделителей Мк+\, то оно верно и для всего множества Мк+\.
Таким образом, условие (7) принимает окончательный вид
Мт С 3/г 6 Нк+1 : в1дп(к, т) > 0. (10)
Кроме того, очевидно, что точки, соответствующие мономам из Ск+\, не могут лежать над плоскостями из Нк+\, так как принадлежат множеству М\Мк+1Ф.
Vк е Нк+1 ¿5с е Ск+1 : згдп(с, к) > 0. (9)
Утверждение 2. Множество Нк+\ гиперплоскостей, ограничивающих М\Мк+\, соста-
procedure EnumerateConvexOrders(Mfc, Ck, Dk, Нк) if к = n then
yield Mk else
for all с G Ck do
Мк+1 <r-Mk + c Ck+1 BuildNextC(Cfc,c) Dk+1 ^ {deDk : d/c} U с Hk+1 <r- 0
for all S С Dk : \S\ = d do
h гиперплоскость, проходящая через S
if h не вырождена и удовлетворяет условию (9) для Ck+i then
нк+1 Нк+1 и h
end if end for
if Dk+1 удовлетворяет условию (10) для Hk+1 then
EnumerateConvexOrders(Mfc+i, Ck+1, Dk+1, iifc+i) end if end for end if
Рис. 5. Алгоритм перебора конечных выпуклых упорядочений.
Очевидно, _Оо = 0- Е>к+1 получается из Ок добавлением тк+\ и исключением всех делителей тк.|_1. Чтобы вычислить Нк+1} достаточно перебрать все ¿-элементные подмножества Ск+г и на каждом построить гиперплоскость, развернув при необходимости нормаль в противоположную сторону, чтобы она удовлетворяла условию (6). Гиперплоскости, удовлетворяющие условию (9), включаются в Нк+
5. ПЕРЕБОР КОНЕЧНЫХ ДОПУСТИМЫХ УПОРЯДОЧЕНИЙ
Мы будем использовать свойство конечных упорядочений, следующее из теоремы Роббиано [5]:
Утверждение 4. Конечное упорядочение т1 < т2 < ■ ■ ■ < тк является допустимым тогда и только тогд
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.