Мономиальный порядок

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

Если $u\leq v$ и $w$ — любой другой моном, то $uw\leq vw$ .

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

Определение, детали и варианты

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

В случае конечного числа переменных хорошее упорядочение мономиального порядка эквивалентно сочетанию следующих двух условий:

Порядок - это полный порядок .
Если u — любой моном, то $1\leq u$ .

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

Ведущие мономы, члены и коэффициенты

Выбор полного порядка мономов позволяет сортировать члены многочлена. Таким образом, главный член полинома является членом наибольшего монома (для выбранного мономиального порядка).

Конкретно, пусть $R$ — любое кольцо многочленов. Тогда множество $M$ (монических) мономов из $R$ является базисом R $,$ рассматриваемым как векторное пространство над полем коэффициентов. Таким образом, любой ненулевой полином $p$ из $R$ имеет единственное выражение $p=\textstyle \sum _{u\in S}c_{u}u$ как линейная комбинация мономов, где $S$ — конечное подмножество $M$ , а $все c u$ ненулевые. Когда выбран порядок мономиа, ведущим мономом является наибольшее значение $u$ в $S$ , старшим коэффициентом является соответствующий $c u$ , а ведущим членом является соответствующий $c u u$ . Головной моном/коэффициент/термин иногда используется как синоним слова «ведущий». Некоторые авторы используют слово «моном» вместо «термин» и «степенное произведение» вместо «моном». В этой статье предполагается, что одночлен не содержит коэффициента.

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

Примеры

На съемочной площадке $\left\{x^{n}\mid n\in \mathbb {N} \right\}$ степеней любой одной переменной x единственными мономиальными порядками являются естественный порядок 1 < x < x ² < х ³ <... и обратное, последнее из которых не является упорядоченным. Следовательно, понятие мономиального порядка становится интересным только в случае нескольких переменных.

Мономиальный порядок подразумевает порядок отдельных неопределенных. Можно упростить классификацию мономиальных порядков, предположив, что неопределенные называются x ₁ , x ₂ , x ₃ , ... в порядке убывания рассматриваемого мономиального порядка, так что всегда x ₁ > x ₂ > x ₃ > .. . (Если должно быть бесконечно много неопределенных, это соглашение несовместимо с условием хорошего упорядочения, и придется использовать противоположный порядок; однако случай полиномов от бесконечного числа переменных рассматривается редко.) В примере ниже мы используем x , y и z вместо x ₁ , x ₂ и x ₃ . При таком соглашении существует еще множество примеров мономиальных порядков разного порядка.

Лексикографический порядок

Лексикографический порядок (lex) сначала сравнивает показатели x ₁ в мономах, а в случае равенства сравнивает показатели x ₂ и так далее. Название происходит от сходства с обычным алфавитным порядком, используемым в лексикографии для словарей, если мономы представляются последовательностью показателей степени неопределенности. Если число неопределенных фиксировано (как это обычно бывает), лексикографический порядок является вполне упорядоченным , хотя это не относится к лексикографическому порядку, применяемому к последовательностям различной длины (см. Лексикографический порядок § Упорядочение последовательностей разная длина ).

Для мономов степени не выше двух из двух неопределенных $x_{1},x_{2}$ , лексикографический порядок (с $x_{1}>x_{2}$ ) является

$x_{1}^{2}>x_{1}x_{2}>x_{1}>x_{2}^{2}>x_{2}>1.$

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

Градуированный лексикографический порядок

Градуированный лексикографический порядок (grlex или deglex для степени лексикографического порядка ) сначала сравнивает общую степень (сумму всех показателей), а в случае равенства применяет лексикографический порядок. Этот порядок не только является хорошим упорядочением, он также обладает тем свойством, что любому моному предшествует только конечное число других мономов; это не относится к лексикографическому порядку, где все (бесконечно многие) степени y меньше x (тот факт, что лексикографический порядок, тем не менее, является хорошим упорядочением, связан с невозможностью построения бесконечной убывающей цепочки мономов).

Для мономов степени не выше двух из двух неопределенных $x_{1},x_{2}$ , градуированный лексикографический порядок (с $x_{1}>x_{2}$ ) является

$x_{1}^{2}>x_{1}x_{2}>x_{2}^{2}>x_{1}>x_{2}>1.$

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

Градуированный обратный лексикографический порядок

Градуированный обратный лексикографический порядок (grevlex или degrevlex для степени обратного лексикографического порядка ) сначала сравнивает общую степень, затем использует лексикографический порядок в качестве разрешения тай-брейка, но меняет результат лексикографического сравнения, так что лексикографически более крупные мономы одной и той же степени считается, что дегревлекс меньше. Для того, чтобы окончательный порядок демонстрировал традиционный порядок x ₁ > x ₂ > ... > x _n неопределенных значений, кроме того, необходимо, чтобы лексикографический порядок разрешения конфликтов перед обращением считал последний неопределенный x _n самым большим, что означает, что оно должно начинаться с этого неопределенного. Таким образом, конкретный рецепт градуированного обратного лексикографического порядка состоит в том, чтобы сначала сравнить по общей степени, затем сравнить показатели последней неопределенной величины x _n, но обратив результат (так что моном с меньшим показателем будет больше в порядке), а затем (как всегда) только в случае ничьей) путем аналогичного сравнения x _{n −1} и т. д., заканчивая x ₁ .

Различия между градуированными лексикографическими и градуированными обратными лексикографическими порядками невелики, поскольку они фактически совпадают для 1 и 2 неопределенных. Первое отличие касается мономов 2-й степени из 3-х неопределенных, которые классифицируются в лексикографическом порядке как $x_{1}^{2}>x_{1}x_{2}>x_{1}x_{3}>x_{2}^{2}>x_{2}x_{3}>x_{3}^{2}$ но градуированные обратные лексикографические упорядочены как $x_{1}^{2}>x_{1}x_{2}>x_{2}^{2}>x_{1}x_{3}>x_{2}x_{3}>x_{3}^{2}$ . Общая тенденция такова, что в обратном порядке проявляются все переменные среди малых мономов любой заданной степени, тогда как при необратном порядке интервалы наименьших мономов любой заданной степени будут образовываться только из наименьших переменных.

Порядок исключения

Порядок блоков или порядок исключения (lexdeg) может быть определен для любого количества блоков, но для простоты мы рассматриваем только случай двух блоков (однако, если количество блоков равно количеству переменных, этот порядок является просто лексикографический порядок). Для этого упорядочения переменные делятся на два блока x ₁ ,..., x _h и y ₁ ,..., y _k , и для каждого блока выбирается мономиальный порядок, обычно градуированный обратный лексикографический порядок. Два монома сравниваются путем сравнения их части x , а в случае равенства — путем сравнения их части y . Этот порядок важен, поскольку он позволяет исключить операцию, которая соответствует проектированию в алгебраической геометрии.

Порядок веса

Порядок весов зависит от вектора $(a_{1},\ldots ,a_{n})\in \mathbb {R} _{\geq 0}^{n}$ называется весовым вектором. Сначала он сравнивает скалярное произведение последовательностей показателей мономов с этим весовым вектором, а в случае равенства использует какой-либо другой фиксированный порядок мономов. Например, приведенные выше градуированные порядки представляют собой весовые порядки для весового вектора «общая степень» (1,1,...,1). Если a _i являются рационально независимыми числами (в частности, ни одно из них не равно нулю, а все дроби ${\tfrac {a_{i}}{a_{j}}}$ иррациональны), то ничья никогда не может возникнуть, а сам весовой вектор определяет мономиальный порядок. В противном случае можно было бы использовать другой весовой вектор, чтобы разорвать связи, и так далее; после использования n линейно независимых весовых векторов не может оставаться никаких связей. Фактически можно определить любой мономиальный порядок с помощью последовательности весовых векторов ( Кокс и др., стр. 72–73), например (1,0,0,...,0), (0,1,0,. ..,0), ... (0,0,...,1) для lex или (1,1,1,...,1), (1,1,..., 1,0 ), ... (1,0,...,0) для гревлекса.

Например, рассмотрим мономы $xy^{2}z$ , $z^{2}$ , $x^{3}$ , и $x^{2}z^{2}$ ; приведенные выше порядки мономов упорядочили бы эти четыре монома следующим образом:

Лекс: $x^{3}>x^{2}z^{2}>xy^{2}z>z^{2}$ (сила $x$ доминирует).
Грлекс: $x^{2}z^{2}>xy^{2}z>x^{3}>z^{2}$ (доминирует суммарная степень; высшая степень $x$ сломал ничью среди первых двух).
Гревлекс: $xy^{2}z>x^{2}z^{2}>x^{3}>z^{2}$ (доминирует общая степень; меньшая мощность $z$ сломал ничью среди первых двух).
Порядок веса с вектором веса (1,2,4): $x^{2}z^{2}>xy^{2}z>z^{2}>x^{3}$ (скалярные произведения 10>9>8>3 не оставляют здесь никаких связей, которые можно было бы разорвать).

Связанные понятия

Порядок исключения гарантирует, что моном, включающий любую из множества неопределённых, всегда будет больше монома, не включающего ни одну из них.
Заказ на продукт — это более простой пример заказа на исключение. Он состоит в объединении мономиальных порядков по непересекающимся множествам неопределенных в мономиальный порядок по их объединению. Он просто сравнивает показатели неопределённостей в первом наборе, используя первый мономиальный порядок, затем разрывает связи, используя другой мономиальный порядок, для неопределённых чисел второго набора. Этот метод, очевидно, обобщается на любое непересекающееся объединение множеств неопределенных величин; таким образом лексикографический порядок может быть получен из одноэлементных наборов { x ₁ }, { x ₂ }, { x ₃ }, ... (с уникальным мономиальным порядком для каждого одноэлементного элемента).

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

Ссылки

Дэвид Кокс; Джон Литтл; Донал О'Ши (2007). Идеалы, разновидности и алгоритмы: введение в вычислительную алгебраическую геометрию и коммутативную алгебру . Спрингер. ISBN 978-0-387-35650-1 .