Основа Грёбнера

В математике , а точнее в компьютерной алгебре , вычислительной алгебраической геометрии и вычислительной коммутативной алгебре , базис Грёбнера - это особый вид порождающего множества идеала в кольце многочленов K [ x ₁ ,…, x _n ] над полем K . Базис Грёбнера позволяет легко вывести многие важные свойства идеала и связанного с ним алгебраического многообразия , например размерностьи количество нулей, когда оно конечно. Вычисление базиса Грёбнера - один из основных практических инструментов для решения систем полиномиальных уравнений и вычисления образов алгебраических многообразий при проекциях или рациональных отображениях .

Вычисление базиса Грёбнера можно рассматривать как многомерное нелинейное обобщение как алгоритма Евклида для вычисления полиномиальных наибольших общих делителей , так и исключения Гаусса для линейных систем. ^[1]

Базы Грёбнера были введены в 1965 году вместе с алгоритмом их вычисления ( алгоритм Бухбергера ) Бруно Бухбергером в его докторской диссертации. Тезис. Он назвал их в честь своего советника Вольфганга Грёбнера . В 2007 году Buchberger получила Ассоциация вычислительной техники «s Париж Теория Kanellakis и премии практике для этой работы. Однако русский математик Николай Гюнтер ввел аналогичное понятие в 1913 году, опубликованное в различных российских математических журналах. Эти статьи в значительной степени игнорировались математическим сообществом до их повторного открытия в 1987 году Бодо Реншухом и др. ^[2] Аналогичная концепция для многомерногоСерия power была разработана независимо Хейсуке Хиронака в 1964 году, который назвал их стандартными базами . Этот термин использовался некоторыми авторами также для обозначения базисов Грёбнера.

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

Фон [ править ]

Кольцо многочленов [ править ]

Грёбнер основа, в первую очередь определяется для идеалов в кольце многочленов над полем K . Хотя теория работает для любого поля, большинство вычислений базиса Грёбнера выполняется либо когда K является полем рациональных чисел, либо целыми числами по модулю простого числа.${\ Displaystyle R = К [x_ {1}, \ ldots, x_ {n}]}$

Полином является суммой , где ненулевые элементы K и являются Мономы или «силовые продукты» переменных. Это означает, что моном M - это произведение, в котором неотрицательные целые числа. Вектор называется показатель степени вектор из М . Обозначения часто сокращаются как . Мономы однозначно определяются своими векторами показателей, поэтому компьютеры могут эффективно представлять мономы как векторы показателей, а полиномы - как списки векторов показателей и их коэффициентов.${\ displaystyle c_ {1} M_ {1} + \ cdots + c_ {m} M_ {m}}$${\ displaystyle c_ {i}}$${\ displaystyle M_ {i}}$${\ Displaystyle M = x_ {1} ^ {a_ {1}} \ cdots x_ {n} ^ {a_ {n}},}$${\ displaystyle a_ {i}}$${\ Displaystyle А = [а_ {1}, \ ldots, а_ {п}]}$${\ displaystyle x_ {1} ^ {a_ {1}} \ cdots x_ {n} ^ {a_ {n}} = X ^ {A}}$

Если - конечный набор многочленов в кольце многочленов R , идеал, порожденный F, - это набор линейных комбинаций элементов из F с коэффициентами во всем R :${\displaystyle F=\{f_{1},\ldots ,f_{k}\}}$

${\displaystyle \langle f_{1},\ldots ,f_{k}\rangle =\left\{\sum _{i=1}^{k}g_{i}f_{i}\mid g_{1},\ldots ,g_{k}\in K[x_{1},\ldots ,x_{n}]\right\}.}$

Мономиальный порядок [ править ]

Все операции, связанные с базисами Грёбнера, требуют выбора полного порядка на мономах со следующими свойствами совместимости с умножением. Для всех одночленов М , N , P ,

1. ${\displaystyle M\leq N\Longleftrightarrow MP\leq NP}$
2. ${\displaystyle M\leq MP}$.

Полный порядок, удовлетворяющий этим условиям, иногда называют допустимым порядком .

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

Хотя теория базиса Грёбнера не зависит от конкретного выбора допустимого мономиального порядка, три мономиальных порядка особенно важны для приложений:

• Лексикографическое упорядочение , обычно называемое lex или plex (для чистого лексического упорядочения).
• Полная степень обратного лексикографического упорядочения , обычно называемая дегревлексом .
• Ликвидация заказа , lexdeg .

Теория базиса Грёбнера была первоначально введена для лексикографического упорядочения. Вскоре стало понятно, что базис Грёбнера для degrevlex почти всегда намного проще вычислить, и что почти всегда легче вычислить базис lex-Гребнера, сначала вычислив базис degrevlex, а затем используя «алгоритм изменения порядка». Когда устранение необходимо, дегревлекс не удобен; могут использоваться как lex, так и lexdeg, но, опять же, многие вычисления относительно просты с lexdeg и почти невозможны с lex.

Как только мономиальный порядок фиксирован, члены многочлена (произведение одночлена с его ненулевым коэффициентом) естественным образом упорядочиваются по убыванию одночленов (для этого порядка). Это делает представление полинома в виде упорядоченного списка пар коэффициент-экспонента вектор каноническим представлением полиномов. Первый (наибольший) член полинома p для этого порядка и соответствующие моном и коэффициент называются соответственно главным членом , старшим мономом и старшим коэффициентом и обозначаются в этой статье lt ( p ), lm ( p ) и lc ( р ).

Сокращение [ править ]

Концепция редукции , также называемая многомерным делением или вычислением нормальной формы , занимает центральное место в теории базиса Гребнера. Это многомерное обобщение евклидова деления одномерных многочленов .

В этом разделе мы предполагаем фиксированный мономиальный порядок, который не будет определяться явно.

При наличии двух многочленов е и г , один говорит , что е является приводимым по г , если некоторый одночлен т в е кратна ведущего мономиального лм ( г ) в г . Если т случается ведущий одночлен й то один говорит , что е является свинцово-приводимым от г . Если c - коэффициент при m в f и m = q lm ( g ), одношаговое сокращениеиз F по г является операцией , которая сопоставляет е многочлена

${\displaystyle \operatorname {red} _{1}(f,g)=f-{\frac {c}{\operatorname {lc} (g)}}\,q\,g.}$

Основные свойства этой операции заключаются в том, что полученный многочлен не содержит одночлена m и что одночлены больше m (для мономиального порядка) остаются неизменными. Эта операция, как правило, не определяется однозначно; если несколько одночленов в f кратны lm ( g ), то можно произвольно выбрать, какой из них уменьшить. На практике для мономиального упорядочения лучше выбрать наибольший, потому что в противном случае последующие редукции могут повторно ввести только что удаленный моном.

Учитывая конечное множество G многочленов, то говорит , что F является приводимым или свинцово-приводимое с помощью G , если она является приводимой или свинцом-приводим, соответственно, с помощью элемента г G . Если это так, то можно определить . (Полное) уменьшение F на G состоит в применении не итеративен этот оператора до получения многочлена , который является неприводимым с помощью G . Это называется нормальной формой из F по G . В общем, эта форма не определена однозначно (это не каноническая форма${\displaystyle \operatorname {red} _{1}(f,G)=\operatorname {red} _{1}(f,g)}$${\displaystyle \operatorname {red} _{1}}$${\displaystyle \operatorname {red} (f,G)}$); эта неединственность является отправной точкой теории базисов Грёбнера.

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

Определение редукции сразу показывает, что если h - нормальная форма f по G , то имеем

${\displaystyle f=h+\sum _{g\in G}q_{g}\,g,}$

где - многочлены. В случае одномерных многочленов, если G состоит из одного элемента g , то h - это остаток от евклидова деления f на g , q _g - частное, а алгоритм деления - это в точности процесс уменьшения опережения. По этой причине некоторые авторы используют термин многомерное деление вместо сокращения.${\displaystyle q_{g}}$

Примеры сокращения [ править ]

В примерах данного раздела, многочлены имеют три неизвестных х , у и г , а мономиальная порядок , который используется является мономиальным порядком с , который, для сравнения двух одночленов, один сравнивают первые экспоненты х ; только когда экспоненты x равны, сравнивают показатели y ; и показатели z сравниваются только тогда, когда другие показатели равны.${\displaystyle x\succ y\succ z;}$

Чтобы иметь четкое представление о процессе редукции, нужно переписать многочлены с их членами в порядке убывания. Например, если

${\displaystyle P=xy^{3}z^{5}+x^{2}y^{6}+x^{4}yz+y^{2}z^{5}+yz^{4}+y^{3}+z^{3}+xy+xz+z^{2}+z,}$

это должно быть переписано

${\displaystyle P=x^{4}yz+x^{2}y^{6}+xy^{3}z^{5}+xy+xz+y^{3}+y^{2}z^{5}+yz^{4}+z^{3}+z^{2}+z.}$

Это позволяет иметь первым (в выбранном порядке) ведущий моном; здесь${\displaystyle \operatorname {lm} (P)=x^{4}yz.}$

Рассмотрим уменьшение на с и${\displaystyle f=2x^{3}-x^{2}y+y^{3}+3y\;}$${\displaystyle \;G=\{g_{1},g_{2}\},}$${\displaystyle g_{1}=x^{2}+y^{2}-1}$${\displaystyle g_{2}=xy-2.}$

Для первого шага сокращения может быть уменьшен либо первый член второго члена. Однако сокращение срока означает удаление этого члена за счет добавления новых более низких членов, и, если это не первый сокращаемый член, который сокращается, возможно, что дальнейшее сокращение добавляет аналогичный член, который должен быть снова уменьшился. Поэтому всегда лучше сначала уменьшить наибольший (для мономиального порядка) приводимый член.

Главный член из F приводит согласно Таким образом, первая стадия восстановления состоит из умножения на -2 х и добавляя результат к F :${\displaystyle 2x^{3}}$${\displaystyle g_{1}.}$${\displaystyle g_{1}}$

${\displaystyle f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}=f-2xg_{1}=-x^{2}y-2xy^{2}+2x+y^{3}+3y.}$

В качестве ведущего члена из кратна ведущих одночленов как и один имеет два варианта для второй стадии восстановления. Если выбрать, получится многочлен, который можно снова уменьшить на${\displaystyle -x^{2}y}$${\displaystyle f_{1}}$${\displaystyle g_{1}}$${\displaystyle g_{2},}$${\displaystyle g_{2},}$${\displaystyle g_{2}\colon }$

${\displaystyle f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}\;{\overset {xg_{2}}{\longrightarrow }}\;-2xy^{2}+y^{3}+3y\;{\overset {2yg_{2}}{\longrightarrow }}\;f_{2}=+y^{3}-y.}$

Дальнейшее уменьшение невозможно, поэтому его можно выбрать для полного уменьшения f . Однако при другом выборе второго шага получается другой результат:${\displaystyle f_{2}}$

${\displaystyle f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}\;{\overset {yg_{1}}{\longrightarrow }}\;-2xy^{2}+2x+2y^{3}+2y\;{\overset {2yg_{2}}{\longrightarrow }}\;f_{3}=+2x+2y^{3}-2y.}$

Таким образом, полное восстановление F может привести либо или${\displaystyle f_{2}}$${\displaystyle f_{3}.}$

Алгоритм Бухбергера был введен для решения трудностей, вызванных этой неединственностью. Грубо говоря , он состоит , чтобы добавить к G многочленов, которые необходимы для однозначности редукции G .

Здесь алгоритм Бухбергера начнется с добавления к G полинома

${\displaystyle g_{3}=yg_{1}-xg_{2}=2x+y^{3}-y.}$

В самом деле, можно еще больше уменьшить, и это снова производит . Однако это не завершает алгоритм Бухбергера, поскольку xy дает разные результаты при уменьшении на или${\displaystyle f_{3}}$${\displaystyle g_{3},}$${\displaystyle f_{2}}$${\displaystyle g_{2}}$${\displaystyle g_{3}.}$

Формальное определение [ править ]

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

• идеал, порожденный старшими членами многочленов от I, равен идеалу, порожденному старшими членами многочлена G ;
• главный член любого полинома из I делится на главный член некоторого полинома из G ;
• многофакторное деление любого многочлена в кольце многочленов R с помощью G дает уникальный остаток;
• многомерное деление на G любого многочлена из идеала I дает остаток 0 .

Все эти свойства эквивалентны; разные авторы используют разные определения в зависимости от выбранной темы. Последние два свойства позволяют производить вычисления в фактор-кольце R / I с той же функциональностью, что и модульная арифметика. Важным фактом коммутативной алгебры является то, что базисы Грёбнера всегда существуют и могут быть эффективно вычислены для любого идеала, заданного конечным порождающим подмножеством.

Многовариантное деление требует мономиального упорядочения, базис зависит от выбранного мономиального упорядочения, и разные упорядочения могут привести к радикально различным базисам Гребнера. Два наиболее часто используемых порядка - это лексикографический порядок и обратный лексикографический порядок степеней (также называемый градуированным обратным лексикографическим порядком или просто полным порядком степеней.). Лексикографический порядок исключает переменные, однако результирующие базы Грёбнера часто очень велики и дороги для вычисления. Обратный лексикографический порядок степеней обычно обеспечивает самые быстрые вычисления базиса Гребнера. В этом порядке мономы сначала сравниваются по общей степени, а связи разрываются путем взятия наименьшего монома относительно лексикографического упорядочения с измененными переменными.

В большинстве случаев (например, многочлены от конечного числа переменных с комплексными коэффициентами или, в более общем смысле, коэффициенты над любым полем), базисы Грёбнера существуют для любого мономиального порядка. Алгоритм Бухбергера - самый старый и самый известный метод их вычисления. Другие методы - это алгоритмы F4 и F5 Фогера , основанные на той же математике, что и алгоритм Бухбергера, и инволютивные подходы, основанные на идеях дифференциальной алгебры . ^[3] Также существует три алгоритма преобразования базиса Грёбнера относительно одного мономиального порядка в базис Грёбнера относительно другого мономиального порядка: алгоритм FGLM, алгоритм , управляемый Гильбертом иАлгоритм ходьбы Гребнера . Эти алгоритмы часто используются для вычисления (сложных) лексикографических базисов Грёбнера из (более простых) базисов Грёбнера полной степени.

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

Концепция и алгоритмы Грёбнера были обобщены на подмодули из свободных модулей над кольцом многочленов. Фактически, если L - свободный модуль над кольцом R , то можно рассматривать R ⊕ L как кольцо, определяя произведение двух элементов L равным 0. Это кольцо можно отождествить с , где - базис L . Это позволяет идентифицировать подмодуль L , генерируемый с идеалом , порожденными и продуктами , . Если R${\displaystyle R[e_{1},\ldots ,e_{l}]/\left\langle \{e_{i}e_{j}|1\leq i\leq j\leq l\}\right\rangle }$${\displaystyle e_{1},\ldots ,e_{l}}$${\displaystyle g_{1},\ldots ,g_{k}}$${\displaystyle R[e_{1},\ldots ,e_{l}]}$${\displaystyle g_{1},\ldots ,g_{k}}$${\displaystyle e_{i}e_{j}}$${\displaystyle 1\leq i\leq j\leq l}$ является кольцом многочленов, это сводит теорию и алгоритмы базисов Грёбнера модулей к теории и алгоритмам базисов Грёбнера идеалов.

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

Пример и контрпример [ править ]

Пусть R = Q [ x , y ] - кольцо двумерных многочленов с рациональными коэффициентами, и рассмотрим идеал I = < f , g >, порожденный многочленами

е ( х , у ) = х ² - у

g ( х , у ) = х ³ - х

Два других элемента I - многочлены

k ( x , y ) = - xf ( x , y ) + g ( x , y ) = xy - x

h ( x , y ) = xk ( x , y ) - ( y - 1) f ( x , y ) = y ² - y

При лексикографическом порядке с x > y имеем

lt ( f ) = х ²

lt ( г ) = х ³

lt ( h ) = y ²

Идеал, порожденный {lt ( f ), lt ( g )}, содержит только многочлены, которые делятся на x ^2, что исключает lt ( h ) = y ² ; отсюда следует, что { f , g } не является базисом Грёбнера для I.

С другой стороны, мы можем показать, что { f , k , h } действительно является базисом Грёбнера для I.

Во-первых, f и g и, следовательно, также h, k и все другие многочлены в идеале I имеют следующие три общих нуля в плоскости ( x , y ), как показано на рисунке: {(1,1), (-1,1), (0,0)}. Эти три точки не коллинеарны, поэтому I не содержит полиномов первой степени. Я также не могу содержать многочлены специального вида

м ( х , у ) = сх + р ( у )

где c - ненулевое рациональное число, а p - многочлен только от переменной y ; причина в том, что у такого m никогда не может быть двух различных нулей с одинаковым значением y (в данном случае точки (1,1) и (−1,1)).

Из вышесказанного следует, что I, помимо нулевого многочлена, содержит только многочлены, старший член которых имеет степень больше или равную 2; поэтому их главные члены делятся хотя бы на один из трех мономов

{ x ² , xy , y ² } = {lt ( f ), lt ( k ), lt ( h )}.

Это означает, что { f , k , h } является базисом Грёбнера для I относительно лексикографического упорядочения с x > y.

Свойства и приложения баз Грёбнера [ править ]

Если явно не указано иное , все результаты, следующие за ^[4] , верны для любого мономиального порядка (см. В этой статье определения различных порядков, которые упомянуты ниже).

Распространенное заблуждение, что лексикографический порядок необходим для некоторых из этих результатов. Напротив, лексикографический порядок почти всегда труднее всего вычислить, и его использование делает непрактичным многие вычисления, которые относительно просты с градуированным обратным лексикографическим порядком (grevlex) или, когда необходимо исключение, порядком исключения (lexdeg ), который ограничивается grevlex для каждого блока переменных.

Равенство идеалов [ править ]

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

Членство и включение идеалов [ править ]

Уменьшение полинома F на основе Гребнера G идеала I дает 0 тогда и только тогда , когда F в I . Это позволяет проверить принадлежность элемента к идеалу. Другой метод состоит в проверке , что Гребнер основа G ∪ { ф } равно G .

Для тестирования , если идеал I , порожденный е ₁ , ...,  е _к содержится в идеале J , достаточно теста , что каждый е _I в J . Можно также проверить равенство редуцированных базисов Гребнера J и J  ∪ { f ₁ , ..., f _k }.

Решения системы алгебраических уравнений [ править ]

Любой набор полиномов можно рассматривать как систему полиномиальных уравнений , приравнивая полиномы к нулю. Множество решений такой системы зависит только от сгенерированного идеала и, следовательно, не меняется при замене данного порождающего набора базисом Гребнера при любом упорядочении сгенерированного идеала. Такое решение с координатами в алгебраически замкнутом поле, содержащем коэффициенты многочленов, называется нулем идеала . В обычном случае рациональных коэффициентов это алгебраически замкнутое поле выбирается в качестве комплексного поля .

У идеала нет нуля (система уравнений несовместна ) тогда и только тогда, когда 1 принадлежит идеалу (это гильбертовский Nullstellensatz ), или, что то же самое, если его базис Грёбнера (для любого мономиального порядка) содержит 1, или, также, если соответствующий приведенный базис Грёбнера равен [1].

Учитывая Гребнер базис G идеала I , он имеет лишь конечное число нулей, тогда и только тогда, когда для каждой переменной х , G содержит многочлен с ведущим одночлена , что является степенью х (без какой - либо другой переменной , появляясь в ведущий термин). Если это случай число нулей, с учетом кратности, равно числу одночленов, которые не кратны любого ведущего мономе G . Это число называется степенью идеала.

Когда число нулей конечно, базис Грёбнера для лексикографического мономиального упорядочения теоретически обеспечивает решение: первые координаты решения являются корнем наибольшего общего делителя многочленов базиса, который зависит только от первой переменной. После подстановки этого корня в базис вторые координаты этого решения являются корнем наибольшего общего делителя полученных многочленов, который зависит только от этой второй переменной, и так далее. Этот процесс решения является только теоретическим, поскольку он подразумевает вычисление НОД и нахождение корня многочленов с приближенными коэффициентами, что невозможно из-за числовой нестабильности. Поэтому были разработаны другие методы решения систем полиномов через базисы Грёбнера (см.Подробнее о системе полиномиальных уравнений ).

Размерность, степень и ряд Гильберта [ править ]

Измерение идеального I в кольце полиномов R является размерностью Крулля кольца R / I и равно размерности алгебраического множества нулей I . Это также равно числу гиперплоскостей в общем положении , которые необходимы , чтобы иметь пересечение с алгебраическим множеством, который представляет собой конечное число точек. Степень идеала и связанного с ней алгебраического множества является число точек пересечения этой конечной, с учетом кратности. В частности, степень гиперповерхности равна степени его полинома определения.

И степень, и размерность зависят только от набора главных мономов базиса Грёбнера идеала для любого мономиального упорядочения.

Измерение размера максимальных подмножеств S переменных таким образом, что не существует ведущего мономиальный в зависимости только от переменных в S . Таким образом, если идеал имеет размерность 0, то для каждой переменной x существует старший моном в базисе Грёбнера, являющийся степенью x .

Как размерность, так и степень могут быть выведены из ряда Гильберта идеала, который представляет собой ряд , где - число одночленов степени i , не кратных любому старшему одночлену в базисе Грёбнера. Ряд Гильберта можно суммировать в рациональную дробь${\textstyle \sum _{i=0}^{\infty }d_{i}t^{i}}$${\displaystyle d_{i}}$

${\displaystyle \sum _{i=0}^{\infty }d_{i}t^{i}={\frac {P(t)}{(1-t)^{d}}},}$

где d - размерность идеала, а - такой многочлен, который является степенью идеала.${\displaystyle P(t)}$${\displaystyle P(1)}$

Хотя размерность и степень не зависят от выбора мономиального порядка, ряд Гильберта и полином меняются при изменении мономиального порядка.${\displaystyle P(t)}$

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

Устранение [ править ]

Вычисление Грёбнера для элиминации мономиального упорядочения позволяет вычислительную теорию исключения . Это основано на следующей теореме.

Рассмотрим полиномиальное кольцо , в котором переменные разбиты на два подмножества X и Y . Давайте также выберем устраняющий мономиальный порядок, «исключающий» X , то есть мономиальный порядок, для которого два монома сравниваются путем сравнения сначала X -частей и, в случае только равенства, рассмотрения Y -частей. Это означает , что одночлен , содержащий X -переменный больше , чем каждый мономиальные независимо от X . Если G является базисом Гребнера идеала I для этого мономиального упорядочения, то является базисом Гребнера (этот идеал часто называют идеалом исключения${\displaystyle K[x_{1},\ldots ,x_{n},y_{1},\ldots ,y_{m}]=K[X,Y],}$${\displaystyle G\cap K[Y]}$${\displaystyle I\cap K[Y]}$). Более того, он состоит в точности из многочленов группы G , главные члены которых принадлежат K [ Y ] (это очень упрощает вычисление , поскольку нужно проверять только старшие одночлены).${\displaystyle G\cap K[Y]}$${\displaystyle G\cap K[Y]}$

Это свойство исключения имеет множество применений, некоторые из них описаны в следующих разделах.

Другое применением в алгебраической геометрии , является то , что устранение реализует геометрическую операцию проекции в качестве аффинного алгебраического множества в подпространство окружающего пространства: с выше обозначениями ( Зарискому замыканием в) проекция алгебраического множества определяется идеальным I в Y -подпространство определяется идеалом${\displaystyle I\cap K[Y].}$

Лексикографический порядок, который является порядком исключения для каждого раздела. Таким образом, базис Грёбнера для этого порядка несет гораздо больше информации, чем обычно необходимо. Это может объяснить, почему основы Грёбнера для лексикографического упорядочения обычно труднее всего вычислить.${\displaystyle x_{1}>\cdots >x_{n}}$${\displaystyle \{x_{1},\ldots ,x_{k}\},\{x_{k+1},\ldots ,x_{n}\}.}$

Пересекающиеся идеалы [ править ]

Если I и J - два идеала, порожденные соответственно { f ₁ , ..., f _m } и { g ₁ , ..., g _k }, то одно вычисление базиса Гребнера дает базис Гребнера их пересечения I  ∩  J . Для этого вводится новый неопределенный t и используется порядок исключения, так что первый блок содержит только t, а другой блок содержит все другие переменные (это означает, что одночлен, содержащий t , больше, чем любой одночлен, не содержащий т). При таком мономиальном порядке базис Грёбнера в I  ∩  J состоит из многочленов, не содержащих t , в базисе Грёбнера идеала

${\displaystyle K=\langle tf_{1},\ldots ,tf_{m},(1-t)g_{1},\ldots ,(1-t)g_{k}\rangle .}$

Другими словами, я  ∩  J получается путем устранения т в K . Это можно доказать, заметив, что идеал K состоит из таких многочленов , что и . Такой многочлен не зависит от t тогда и только тогда, когда a = b , что означает, что${\displaystyle (a-b)t+b}$${\displaystyle a\in I}$${\displaystyle b\in J}$${\displaystyle b\in I\cap J.}$

Неявное построение рациональной кривой [ править ]

Рациональной кривой представляет собой алгебраическую кривую , которая имеет параметрическое уравнение вида

${\displaystyle {\begin{aligned}x_{1}&={\frac {f_{1}(t)}{g_{1}(t)}}\\&\;\;\vdots \\x_{n}&={\frac {f_{n}(t)}{g_{n}(t)}},\end{aligned}}}$

где и - одномерные многочлены для 1 ≤ i ≤ n . Один может (и будет) Предположим , что и являются взаимно простыми (они не имеют непостоянные факторы , общие).${\displaystyle f_{i}(t)}$${\displaystyle g_{i}(t)}$${\displaystyle f_{i}(t)}$${\displaystyle g_{i}(t)}$

Неявность заключается в вычислении неявных уравнений такой кривой. В случае n = 2, то есть для плоских кривых, это можно вычислить с помощью полученного результата . Неявное уравнение имеет следующий результат:

${\displaystyle {\text{Res}}_{t}(g_{1}x_{1}-f_{1},g_{2}x_{2}-f_{2}).}$

Исключение с базисами Грёбнера позволяет неявно выполнять для любого значения n , просто исключив t в идеале. Если n = 2, результат будет таким же, как и с результирующим, если отображение инъективно для почти каждого t . В другом случае результат - это степень результата исключения.${\displaystyle \langle g_{1}x_{1}-f_{1},\ldots ,g_{n}x_{n}-f_{n}\rangle .}$${\displaystyle t\mapsto (x_{1},x_{2})}$

Насыщенность [ править ]

При моделировании проблемы с помощью полиномиальных уравнений очень часто предполагается, что некоторые величины не равны нулю, потому что, если они равны нулю, проблема становится совсем другой. Например, при работе с треугольниками многие свойства становятся ложными, если треугольник вырожден, то есть если длина одной стороны равна сумме длин других сторон. В таких ситуациях нет никакой надежды получить релевантную информацию из полиномиальной системы, если вырожденные решения не выпадут. Точнее, система уравнений определяет алгебраическое множество, которое может иметь несколько неприводимых компонентов , и нужно удалить компоненты, на которых условия вырождения всюду равны нулю.

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

Определение насыщенности [ править ]

Локализация кольца состоит в прилегающем к нему формальным инверсиям некоторых элементов. Этот раздел касается только случая одного элемента или, что то же самое, конечного числа элементов (соединение обратных элементов нескольких элементов эквивалентно соединению обратных элементов их произведения). Локализации кольцевого R элемента F является кольцом , где т представляет собой новый неопределенный , представляющие обратные е . Локализации идеального I из R является идеальной из Когда R является полиномом кольца, вычисления в${\displaystyle R_{f}=R[t]/(1-ft),}$${\displaystyle R_{f}I}$${\displaystyle R_{f}.}$${\displaystyle R_{f}}$неэффективен из-за необходимости управлять знаменателями. Поэтому операцию локализации обычно заменяют операцией насыщения .

Насыщения относительно F идеала I в R является прообразом при канонической карте от R до Это идеальное , состоящий во всех элементах R , чья продукция по некоторой степени е принадлежит к I .${\displaystyle R_{f}I}$${\displaystyle R_{f}.}$${\displaystyle I:f^{\infty }=\{g\in R|(\exists k\in \mathbb {N} )f^{k}g\in I\}}$

Если J - идеал, порожденный I и 1- ft в R [ t ], то отсюда следует, что, если R - кольцо многочленов, вычисление базиса Грёбнера, исключающее t, позволяет вычислить базис Гребнера насыщения идеала элементом полином.${\displaystyle I:f^{\infty }=J\cap R.}$

Важным свойством насыщения, которое гарантирует , что она удаляет из алгебраического множества , определенного идеала I на неприводимые компоненты , на которых многочлен F равен нулю, состоит в следующем: примарное из состоит в компонентах первичного разложения I которые не содержат степени f . ${\displaystyle I:f^{\infty }}$

Вычисление насыщенности [ править ]

Базис Грёбнера насыщения f полиномиального идеала, порожденного конечным набором многочленов F , может быть получен путем исключения t в том смысле, что полиномы не зависят от t в базисе Грёбнера для упорядочения исключения, исключающего t .${\displaystyle F\cup \{1-tf\},}$${\displaystyle F\cup \{1-tf\}}$

Вместо того чтобы использовать F , можно также начинать с базиса Гребнера F . Какой метод наиболее эффективен, зависит от проблемы. Однако, если насыщение не удаляет какой-либо компонент, то есть если идеал равен своему насыщенному идеалу, вычисление сначала базиса Гребнера F обычно происходит быстрее. С другой стороны, если насыщение удаляет некоторые компоненты, прямое вычисление может быть значительно быстрее.

Если кто-то хочет получить насыщение по отношению к нескольким многочленам или по отношению к одному многочлену, который является произведением, есть три способа действовать, которые дают тот же результат, но могут иметь очень разное время вычисления (это зависит от задачи, которая является наиболее эффективной. ).${\displaystyle f_{1},\ldots ,f_{k}}$${\displaystyle f=f_{1}\cdots f_{k},}$

• Насыщение с помощью одного вычисления базиса Грёбнера.${\displaystyle f=f_{1}\cdots f_{k}}$
• Насыщение, затем насыщение результата и так далее.${\displaystyle f_{1},}$${\displaystyle f_{2},}$
• Добавление к F или к его базису Грёбнера полиномы и исключение полиномов за одно вычисление базиса Грёбнера.${\displaystyle 1-t_{1}f_{1},\ldots ,1-t_{k}f_{k},}$${\displaystyle t_{i}}$

Эффективный Nullstellensatz [ править ]

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

Вторая версия утверждает, что множество общих нулей (в алгебраическом замыкании поля коэффициентов) идеала содержится в гиперповерхности нулей многочлена f тогда и только тогда, когда степень f принадлежит идеалу . Это может быть проверено насыщением идеала функцией f ; на самом деле степень f принадлежит идеалу тогда и только тогда, когда насыщение f дает базис Грёбнера, содержащий 1.

Неявное выражение в более высоком измерении [ править ]

По определению аффинное рациональное многообразие размерности k может быть описано параметрическими уравнениями вида

${\displaystyle {\begin{aligned}x_{1}&={\frac {p_{1}}{p_{0}}}\\&\;\;\vdots \\x_{n}&={\frac {p_{n}}{p_{0}}},\end{aligned}}}$

где есть п +1 многочленов от K переменных (параметры параметризации) Таким образом, параметры и координаты точек многообразия являются нули идеала${\displaystyle p_{0},\ldots ,p_{n}}$${\displaystyle t_{1},\ldots ,t_{k}.}$${\displaystyle t_{1},\ldots ,t_{k}}$${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle I=\left\langle p_{0}x_{1}-p_{1},\ldots ,p_{0}x_{n}-p_{n}\right\rangle .}$

Можно было догадаться, что достаточно исключить параметры, чтобы получить неявные уравнения многообразия, как это было сделано в случае кривых. К сожалению, это не всегда так. Если имеют общий нуль (иногда называемая базовая точка ), каждый неприводимую компоненту из непустого алгебраического множества , определяемой неприводимая компонента алгебраического множества , определенного I . Следовательно, в этом случае прямое исключение дает пустой набор многочленов.${\displaystyle p_{i}}$${\displaystyle p_{i}}$${\displaystyle t_{i}}$

Следовательно, если k > 1, необходимы два вычисления базиса Грёбнера для неявного определения:

1. Пропитайте , чтобы получить основу Грёбнера${\displaystyle I}$${\displaystyle p_{0}}$${\displaystyle G}$
2. Исключите из, чтобы получить базис Грёбнера идеала (неявных уравнений) многообразия.${\displaystyle t_{i}}$${\displaystyle G}$

Реализации [ править ]

• Бесплатная система компьютерной алгебры CoCoA для вычисления базисов Гребнера.
• Система компьютерной алгебры без GAP, которая может выполнять вычисления базиса Грёбнера.
• FGb, собственная реализация Фогера его алгоритма F4 , доступная в виде библиотеки Maple . ^[5] На сегодняшний день, по состоянию на 2014 год, с Magma это самая быстрая реализация рациональных коэффициентов и коэффициентов в конечном поле простого порядка.
• Бесплатная программа Macaulay 2 для выполнения полиномиальных вычислений, в частности, вычислений базиса Грёбнера.
• Magma имеет очень быструю реализацию алгоритма F4 Фожера. ^[6]
• В Maple есть реализации алгоритмов Бухбергера и Фогера F4, а также трассировки Грёбнера.
• Mathematica включает реализацию алгоритма Бухбергера с такими методами повышения производительности, как обход Грёбнера, след Грёбнера и усовершенствование торических базисов.
• SINGULAR бесплатное программное обеспечение для вычисления коммутативных и некоммутативных базисов Гребнера.
• SageMath предоставляет унифицированный интерфейс для нескольких систем компьютерной алгебры (включая SINGULAR и Macaulay) и включает несколько собственных базовых алгоритмов Гребнера.
• Система компьютерной алгебры SymPy Python использует базисы Грёбнера для решения полиномиальных систем.

Области применения [ править ]

Коды исправления ошибок [ править ]

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

См. Также [ править ]

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

Дальнейшее чтение [ править ]

• Адамс, Уильям У .; Лустаунау, Филипп (1994). Введение в основы Грёбнера . Аспирантура по математике . 3 . Американское математическое общество . ISBN 0-8218-3804-0.
• Ли, Хуиши (2011). Основы Грёбнера в теории колец . World Scientific. ISBN 978-981-4365-13-0.
• Беккер, Томас; Вайспфеннинг, Фолькер (1998). Базы Грёбнера . Тексты для выпускников по математике. 141 . Springer. ISBN 0-387-97971-9.
• Бухбергер, Бруно (1965). Алгоритм поиска базисных элементов кольца классов остатков нульмерного полиномиального идеала (PDF) (PhD). Университет Инсбрука. - (2006). Перевод М. Абрамсона "Кандидатская диссертация Бруно Бухбергера 1965: Алгоритм нахождения базисных элементов кольца классов вычетов нульмерного полиномиального идеала" . Журнал символических вычислений . 41 (3–4): 471–511. DOI : 10.1016 / j.jsc.2005.09.007 . [Это тезис Бухбергера об изобретении основ Грёбнера.]
• Бухбергер, Бруно (1970). «Алгоритмический критерий разрешимости системы алгебраических уравнений» (PDF) . Aequationes Mathematicae . 4 : 374–383. DOI : 10.1007 / BF01844169 . S2CID  189834323 . (Это журнальная публикация диссертации Бухбергера.) Burchberger, B .; Винклер, Ф., ред. (26 февраля 1998 г.). «Алгоритмический критерий разрешимости системы алгебраических уравнений» . Основы Грёбнера и приложения . Серия лекций Лондонского математического общества. 251 . Издательство Кембриджского университета. С. 535–545. ISBN 978-0-521-63298-0.
• Бухбергер, Бруно; Кауэрс, Мануэль (2010). «Базы Грёбнера» . Scholarpedia . 5 (10): 7763. DOI : 10,4249 / scholarpedia.7763 .
• Фрёберг, Ральф (1997). Введение в основы Грёбнера . Вайли. ISBN 0-471-97442-0.
• Штурмфельс, Бернд (ноябрь 2005 г.). "Что такое ... Основа Грёбнера?" (PDF) . Уведомления Американского математического общества . 52 (10): 1199–1200, краткое введениеCS1 maint: postscript (link)
• Ширшов, Анатолий И. (1999). «Некоторые алгоритмические проблемы для алгебр Ли» (PDF) . Бюллетень ACM SIGSAM . 33 (2): 3–6. DOI : 10.1145 / 334714.334715 . S2CID  37070503 .(пер. из Сиб. мат. ж. Сибирский математический журнал 3 (1962), 292–296).
• Ашенбреннер, Матиас ; Хиллар, Кристофер (2007). «Конечное поколение симметричных идеалов» . Труды Американского математического общества . 359 (11): 5171–92. DOI : 10.1090 / S0002-9947-07-04116-5 . S2CID  5656701 . (о бесконечномерных базисах Грёбнера для колец многочленов от бесконечного числа неопределенных).

Внешние ссылки [ править ]

• Собственная реализация Фогером его алгоритма F4
• «Базис Грёбнера» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Бухбергер, Б. (2003). «Основы Грёбнера: краткое введение для теоретиков систем» (PDF) . In Moreno-Diaz, R .; Buchberger, B .; Фрейре, Дж. (Ред.). Теория компьютерных систем - EUROCAST 2001: Подборка статей 8-го Международного семинара по теории автоматизированных систем . Springer. С. 1–19. ISBN 978-3-540-45654-4.
• Buchberger, B .; Заплетал, А. "Библиография основ Грёбнера" .
• Страница сравнительного времени для программного обеспечения Gröbner Bases
• Проф. Бруно Бухбергер Бруно Бухбергер
• Вайсштейн, Эрик В. «Основа Грёбнера» . MathWorld .
• Введение в основы Грёбнера в Scholarpedia