Открыть главное меню

ОпределениеПравить

Пусть для поля   и коммутирующих переменных   заданы: некоторый идеал   кольца многочленов   коммутирующих переменных   и некоторый полный порядок « » на мономах  , где  , т.е.   для  . При этом порядок   обязан дополнительно удовлетворять двум условиям:

  1. мультипликативность:   влечёт   для  ;
  2. минимальность единицы:   для  , т.е.  .

Член   называется старшимleading») членом (относительно упорядочения  ) многочлена  , если   для всех  .

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

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

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

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

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

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

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

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

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

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

Алгоритмы построенияПравить

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

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

ПримененияПравить

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

ИсторияПравить

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

 

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

 

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

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

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

ПримечанияПравить

  1. W. Gröbner. Über die Eliminationstheorie (англ.) // Monatshefte für Mathematik (англ.) : journal. — 1950. — Vol. 54. — P. 71—78.
  2. СМЖ, 1962, т. 3, №2, с. 292-296.

ЛитератураПравить

СсылкиПравить