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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править код]

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

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

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

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

Виды базисов Грёбнера[править | править код]

Минимальный базис Грёбнера[править | править код]

Минимальным базисом Грёбнера полиномиального идеала 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 (1950). «Über die Eliminationstheorie». Monatshefte für Mathematik 54: 71-78.
  2. СМЖ, 1962, т. 3, №2, с. 292-296.

Литература[править | править код]

Ссылки[править | править код]