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

Ба́зис Грёбнера некоторого идеала I алгебры многочленов $K[x_1,\ldots,x_n]$ относительно порядка «$\prec$» на мономах — это конечное множество G многочленов из $K[x_1,\ldots,x_n]$ такое, что старший (относительно $\prec$) член каждого многочлена из I делится на старший член хотя бы одного многочлена из G. При этом порядок $\prec$ обязан быть полным и дополнительно удовлетворять двум условиям:

1. Мультипликативность: $x^a\prec x^b$ влечёт $x^{a+c}\prec x^{b+c}$.
2. Минимальность единицы: $1\prec x^a$, для $a>0$.

Виды базисов Грёбнера

Минимальный базис Грёбнера

Минимальным базисом Грёбнера полиномиального идеала I называется его базис Грёбнера G, такой, что:

1. Коэффициент при старшем мономе каждого $p \in G$ равен единице.
2. Старший моном каждого $p \in G$ не является старшим мономом ни одного другого $q \in \{G\setminus{p}\}$

Редуцированный базис Грёбнера

Редуцированным базисом Грёбнера полиномиального идеала I называется его базис Грёбнера G, такой, что:

1. Коэффициент при старшем мономе каждого $p \in G$ равен единице.
2. Старший моном каждого $p \in G$ не делится ни на один старший моном других элементов базиса.

Для редуцированного базиса Грёбнера идеала верно следующее утверждение:

Пусть I — полиномиальный идеал, и задано некоторое мономиальное упорядочение. Тогда существует единственный редуцированный базис Грёбнера идеала I.

Алгоритмы построения

Самым первым алгоритмом построения редуцированного базиса Грёбнера идеала считается алгоритм Бухбергера. Интересно, что известный метод Гаусса решения систем линейных уравнений является частным случаем алгоритма Бухбергера.

Кроме того, французским математиком Жаном-Шарлем Фожером были предложены алгоритмы F4 и F5 нахождения базиса Грёбнера.

Применения

Базис Грёбнера является важнейшим понятием компьютерной алгебры, алгебраической геометрии и вычислительной коммутативной алгебры.

История

Австрийский математик Вольфганг Грёбнер разработал теорию стандартных базисов для свободного коммутативного случая в начале 30-х годов и опубликовал её в 1950 году,^[1] где он написал:

Я начал использовать этот метод 17 лет назад для различных примеров, в том числе и очень сложных. Оригинальный текст  (нем.)   Ich habe diese Methode seit etwa 17 Jahren in den verschiedensten, auch kompliziersten Fällen verwendet.

В 1964 году аналогичная концепция для локальных колец была разработана Хейсуки Хиронакой, получившим Филдовскую премию в 1970 году. Он назвал введённые системы полиномов стандартным базисом.

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

Существование стандартного базиса идеала опирается на «лемму о композиции», которая впервые была доказана для самого сложного из известных случаев (свободных алгебр Ли) А. И. Ширшовым.^[2] При этом правильность аналогичного утверждения для свободного ассоциативного и коммутативного случая считалась очевидной и не привлекала особого внимания вплоть до более поздних работ Л. И. Бокутя по теории вложений ассоциативных колец в тела и кольца с заданными свойствами. В 1972 году Л. И. Бокуть опубликовал «лемму Ширшова о композиции» для свободного ассоциативного случая в записках курса по ассоциативным алгебрам Новосибирского университета. Отсюда и из устного общения она стала известна американскому алгебраисту Дж. Бергману, который опубликовал её в 1979 году под названием «Diamond Lemma» (Алмазная Лемма), впрочем, строгое доказательство в работе отсутствовало, и была обозначена только мнемоническая схема «слияния», необходимая для понимания идеи Ширшова о композиции. После публикации Бергмана «Алмазная Лемма» стала популярна среди алгебраистов и геометров, она также привлекла внимание к «базису Грёбнера» Бухбергера. В середине 80-х годов стандартный базис для супералгебр и цветных алгебр Ли был построен московским алгебраистом А. А. Михалёвым.

Примечания

1. ↑ W. Gröbner (1950). «Über die Eliminationstheorie». Monatshefte für Mathematik 54: 71-78.
2. ↑ СМЖ, 1962, т. 3, №2, с. 292-296.

Ссылки

• Панкратьев Е. В. Введение в компьютерную алгебру.
• Аржанцев И. В. Базисы Грёбнера и системы алгебраических уравнений. — М.: МЦНМО, 2003. — 68 с. — ISBN 5-94057-095-X
• Чуркин В. А. Cистемы полиномиальных уравнений, идеалы и их базисы-делители.
• Кокс Д., Литтл Дж., О'Ши Д. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры.
• Bernd Sturmfels. What is a Gröbner basis?