В математике порядок монома (иногда называемый порядком термов или допустимым порядком ) — это полный порядок на множестве всех ( монических ) мономов в заданном кольце полиномов , удовлетворяющий свойству соблюдения умножения, т. е.
Мономиальные упорядочения чаще всего используются с базисами Грёбнера и многомерным делением . В частности, свойство быть базисом Грёбнера всегда относится к конкретному мономиальному порядку.
Помимо соблюдения умножения, часто требуется, чтобы порядки мономов были хорошо упорядоченными , поскольку это гарантирует завершение процедуры многомерного деления. Однако существуют также практические приложения для уважительных к умножению отношений порядка на множестве мономов, которые не являются хорошо упорядоченными.
В случае конечного числа переменных хорошее упорядочение мономиального порядка эквивалентно конъюнкции следующих двух условий:
Поскольку эти условия может быть проще проверить для порядка мономов, определенного с помощью явного правила, чем напрямую доказать, что он является вполне упорядоченным, им иногда отдают предпочтение в определениях порядка мономов.
Выбор общего порядка мономов позволяет сортировать члены многочлена. Таким образом, старший член многочлена — это член наибольшего монома (для выбранного порядка мономов).
Конкретно, пусть R — любое кольцо многочленов. Тогда множество M (монических) мономов в R является базисом R , рассматриваемым как векторное пространство над полем коэффициентов. Таким образом, любой ненулевой полином p в R имеет единственное выражение в виде линейной комбинации мономов, где S — конечное подмножество M , а c u все ненулевые. Когда выбран порядок монома, ведущий моном — это наибольший u в S , ведущий коэффициент — это соответствующий c u , а ведущий член — это соответствующий c u u . Головной моном/коэффициент/член иногда используется как синоним «ведущего». Некоторые авторы используют «моном» вместо «терма» и «степенное произведение» вместо «монома». В этой статье предполагается, что моном не включает коэффициент.
Определяющее свойство упорядочения мономов подразумевает, что порядок членов сохраняется при умножении многочлена на моном. Кроме того, старший член произведения многочленов является произведением старших членов множителей.
На множестве степеней любой одной переменной x единственными мономиальными порядками являются естественный порядок 1 < x < x 2 < x 3 < ... и его обратный порядок, последний из которых не является полным порядком. Поэтому понятие мономиального порядка становится интересным только в случае нескольких переменных.
Порядок монома подразумевает порядок отдельных неопределенных. Можно упростить классификацию порядков мономов, предположив, что неопределенные называются x 1 , x 2 , x 3 , ... в порядке убывания для рассматриваемого порядка монома, так что всегда x 1 > x 2 > x 3 > ... . (Если должно быть бесконечно много неопределенных, это соглашение несовместимо с условием быть хорошим порядком, и пришлось бы использовать противоположный порядок; однако случай полиномов от бесконечного числа переменных редко рассматривается.) В примере ниже мы используем x , y и z вместо x 1 , x 2 и x 3 . С этим соглашением все еще есть много примеров различных порядков мономов.
Лексикографический порядок (lex) сначала сравнивает показатели степеней x 1 в одночленах, а в случае равенства сравнивает показатели степеней x 2 и т. д. Название происходит от сходства с обычным алфавитным порядком, используемым в лексикографии для словарей, если одночлены представлены последовательностью показателей степеней неопределенных. Если число неопределенных фиксировано (как это обычно и бывает), лексикографический порядок является вполне упорядоченным , хотя это не относится к лексикографическому порядку, применяемому к последовательностям различной длины (см. Лексикографический порядок § Упорядочение последовательностей различной длины ).
Для мономов степени не более двух от двух неизвестных лексикографический порядок (с ) имеет вид
Для вычислений на основе базиса Грёбнера лексикографическое упорядочение, как правило, является наиболее затратным; поэтому его следует избегать, насколько это возможно, за исключением очень простых вычислений.
Градуированный лексикографический порядок (grlex или deglex для degree lexicographic order ) сначала сравнивает общую степень (сумму всех показателей), а в случае равенства применяет лексикографический порядок. Этот порядок не только является хорошим порядком, он также обладает тем свойством, что любому моному предшествует только конечное число других мономов; это не относится к лексикографическому порядку, где все (бесконечно много) степеней y меньше x (то, что лексикографический порядок тем не менее является хорошим порядком, связано с невозможностью построения бесконечной убывающей цепочки мономов).
Для мономов степени не более двух от двух неизвестных градуированный лексикографический порядок (с ) имеет вид
Хотя это и вполне естественно, такой порядок используется редко: базис Грёбнера для градуированного обратного лексикографического порядка, который следует ниже, вычислить проще, и он предоставляет ту же информацию о входном наборе многочленов.
Градуированный обратный лексикографический порядок (grevlex или degrevlex для degree reverse lexicographic order ) сначала сравнивает общую степень, затем использует лексикографический порядок в качестве решающего, но он меняет результат лексикографического сравнения так, что лексикографически большие мономы той же степени считаются degrevlex меньшими. Для того чтобы окончательный порядок демонстрировал обычный порядок x 1 > x 2 > ... > x n неопределенных, необходимо, чтобы решающий лексикографический порядок перед обратным считал последний неопределенный x n наибольшим, что означает, что он должен начинаться с этого неопределенного. Конкретный рецепт для градуированного обратного лексикографического порядка, таким образом, заключается в том, чтобы сначала сравнить по общей степени, затем сравнить показатели последней неопределенной величины x n , но поменять местами результат (так, чтобы моном с меньшим показателем был больше в порядке), а затем (как всегда, только в случае равенства) провести аналогичное сравнение x n −1 и так далее, заканчивая x 1 .
Различия между градуированным лексикографическим и градуированным обратным лексикографическим порядками тонкие, поскольку они фактически совпадают для 1 и 2 неопределенных. Первое различие возникает для одночленов степени 2 в 3 неопределенных, которые градуированы лексикографически как , но градуированы обратно лексикографически как . Общая тенденция заключается в том, что обратный порядок показывает все переменные среди малых одночленов любой заданной степени, тогда как при необратном порядке интервалы наименьших одночленов любой заданной степени будут образованы только из наименьших переменных.
Порядок блоков или порядок исключения (lexdeg) может быть определен для любого числа блоков, но для простоты мы рассмотрим только случай двух блоков (однако, если число блоков равно числу переменных, этот порядок является просто лексикографическим порядком). Для этого порядка переменные делятся на два блока x 1 ,..., x h и y 1 ,..., y k , и для каждого блока выбирается мономиальный порядок, обычно градуированный обратный лексикографический порядок. Два монома сравниваются путем сравнения их x- частей, а в случае равенства — путем сравнения их y- частей. Этот порядок важен, поскольку он допускает исключение — операцию, которая соответствует проекции в алгебраической геометрии.
Порядок веса зависит от вектора, называемого вектором веса. Сначала он сравнивает скалярное произведение последовательностей экспонент мономов с этим вектором веса, а в случае равенства использует другой фиксированный порядок мономов. Например, градуированные порядки выше являются порядками веса для вектора веса «полной степени» (1,1,...,1). Если a i являются рационально независимыми числами (в частности, ни одно из них не равно нулю, а все дроби иррациональны), то равенство никогда не может возникнуть, а сам вектор веса определяет порядок мономов. В противном случае можно использовать другой вектор веса для разрыва равенств и т. д.; после использования 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) для grevlex.
Например, рассмотрим мономы , , , и ; приведенные выше порядки мономов упорядочат эти четыре монома следующим образом:
При использовании мономиальных порядков для вычисления базисов Грёбнера разные порядки могут приводить к разным результатам, а сложность вычислений может существенно различаться. Например, градуированный обратный лексикографический порядок имеет репутацию почти всегда производящего самые простые для вычисления базисы Грёбнера (это подкрепляется тем фактом, что при довольно общих условиях на идеал полиномы в базисе Грёбнера имеют степень, которая не более чем экспоненциальна по числу переменных; такого результата по сложности не существует ни для какого другого упорядочения). С другой стороны, порядки исключения требуются для проблем исключения и относительных проблем.
