WikiSort.ru - Не сортированное

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

Определение

Пусть для поля ${\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})\geq 0}$ , т.е. ${\displaystyle a_{j}\geq 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\geq 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}}$ называется старшим («leading») членом (относительно упорядочения ${\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)}$ .

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

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

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

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

Применения

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

История

Австрийский математик Вольфганг Грёбнер (англ.) разработал теорию стандартных базисов для свободного коммутативного случая в начале 1930-х годов, а опубликовал её в статье 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» («алмазная лемма»). Строгое доказательство в работе отсутствовало, а была обозначена только мнемоническая схема «слияния», необходимая для понимания идеи Ширшова о композиции. После публикации Бергмана «алмазная лемма» стала популярна среди алгебраистов и геометров, она также привлекла внимание к «базису Грёбнера» Бухбергера. В середине 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?

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