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

Ба́зис Грёбнера — множество, которое порождает идеал заданного кольца многочленов, обладающее специальными свойствами.

Определение

Пусть для поля $F$ и коммутирующих переменных $(x_{1},\ldots ,x_{n})$ заданы: некоторый идеал $I$ кольца многочленов $F[x_{1},\ldots ,x_{n}]$ от переменных $(x_{1},\ldots ,x_{n})$ и некоторый полный порядок «$\prec$» на мономах $x^{a}=x_{1}^{a_{1}}\cdot \ldots \cdot x_{n}^{a_{n}}$, где $a=(a_{1},\ldots ,a_{n})\geqslant 0$, то есть $a_{j}\geqslant 0$ для $j=1,\ldots ,n$. При этом порядок $\prec$ обязан дополнительно удовлетворять двум условиям:

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

Член $l_{\prec }(p)=\varphi _{l}\cdot x^{l}$ называется старшим членом (относительно упорядочения $\prec$) многочлена $p=\sum _{a\in A(p)}\varphi _{a}\cdot x^{a}\in F[x_{1},\ldots ,x_{n}]$, если $x^{a}\prec x^{l}$ для всех $a\in A(p)\setminus \{l\}$.

Базисом Грёбнера идеала $I$ кольца $F[x_{1},\ldots ,x_{n}]$ называется конечное множество $G=\{g_{1},\ldots ,g_{m}\}$ многочленов из $F[x_{1},\ldots ,x_{n}]$, порождающее идеал $I$ и обладающее свойством: для любого многочлена $p\in I$ найдётся многочлен $g\in G$ такой, что $l_{\prec }(p)$ делится на $l_{\prec }(g)$.

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

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

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

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

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

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

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

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

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

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

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

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

Применения

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

История

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

Я начал использовать этот метод 17 лет назад для различных примеров, в том числе и очень сложных.

Оригинальный текст (нем.)

Ich habe diese Methode seit etwa 17 Jahren in den verschiedensten, auch kompliziersten Fällen verwendet.

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

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

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

Литература

• Аржанцев И. В. Базисы Грёбнера и системы алгебраических уравнений. — М.: МЦНМО, 2003. — 68 с. — ISBN 5-94057-095-X.
• Бухбергер Б. и другие. Компьютерная алгебра: Символьные и алгебраические вычисления. — М.: Мир, 1986. — 392 с.
• Кокс Д., Литтл Дж., О'Ши Д. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры. — М.: Мир, 2000. — 687 с. — ISBN 5-03-003320-3.
• Панкратьев Е. В. Введение в компьютерную алгебру. — Интуит. — ISBN 978-5-9556-0099-4.

Ссылки

• Чуркин В. А. Системы полиномиальных уравнений, идеалы и их базисы-делители.
• Bernd Sturmfels. What is a Gröbner basis?