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

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

Пусть для поля ${\displaystyle F}$ и

${\displaystyle (x_{1},\ldots ,x_{n})}$

${\displaystyle I}$

${\displaystyle F[x_{1},\ldots ,x_{n}]}$

${\displaystyle (x_{1},\ldots ,x_{n})}$

${\displaystyle \prec }$

${\displaystyle x^{a}=x_{1}^{a_{1}}\cdot \ldots \cdot x_{n}^{a_{n}}}$

${\displaystyle a=(a_{1},\ldots ,a_{n})\geqslant 0}$

${\displaystyle a_{j}\geqslant 0}$

${\displaystyle j=1,\ldots ,n}$

${\displaystyle \prec }$

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

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

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

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

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

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

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

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

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

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

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

Базис Грёбнера является важнейшим понятием

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

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

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

Существование стандартного базиса идеала опирается на «лемму о композиции», которая впервые была доказана для самого сложного из известных случаев (свободных

• Аржанцев И. В. Базисы Грёбнера и системы алгебраических уравнений. — М.:
  МЦНМО, 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?

Для улучшения этой статьи желательно: Проставить сноски, внести более точные указания на источники. Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.