Monomial order

수학(mathematics)에서, 단항식 순서(monomial order) (때때로 항 순서(term order) 또는 허용 순서(admissible order)라고 불림움)는 주어진 다항식 링(polynomial ring)에서 모든 (일계수(monic)) 단항식(monomial)의 집합에 대한 전체 순서(total order)이며, 곱셈에 관련한 속성을 만족시킵니다. 즉,

만약 $u\leq v$ 이고 $w$ 가 임의의 다른 단항식이면, $uw\leq vw$ 입니다.

단항식 순서화는 단항식 순서는 그뢰브너 기저(Gröbner bases) 및 다변수 나눗셈(multivariate division)에서 가장 공통적으로 사용됩니다. 특히, 그뢰브너 기저(Gröbner basis)가 되는 것의 속성은 항상 특정 단항식 순서에 상대적입니다.

Definition, details and variations

곱셈에 관련된 것 외에도, 단항식 순서는 종종 바른-순서(well-orders)가 될 것을 요구하는데, 왜냐하면 이것은 다변수 나눗셈 절차가 종료될 것임을 보장하기 때문입니다. 어쨌든 바른-순서가 아닌 단항식의 집합에 대한 곱셈-관련되는 순서 관계에 대해 역시 실용적인 응용이 있습니다.

유한하게 많은 변수의 경우에서, 단항식 순서의 바른-순서화는 다음 두 조건의 논리곱과 동등합니다:

그 순서는 전체 순서(total order)입니다.
만약 u가 임의의 단항식이면, $1\leq u$ 입니다.

이들 조건이, 그것이 바른-순서화임을 직접 입증하는 것보다, 명시적 규칙을 통해 정의된 단항식 순서에 대해 확인하기가 더 쉬울 수 있기 때문에, 그것들은 때때로 단항식 순서의 정의에 선호됩니다.

Leading monomials, terms, and coefficients

단항식에 대한 전체 순서의 선택은 다항식의 항을 정렬하는 것을 허용합니다. 다항식의 선행 항(leading term)은 따라서 (선택된 단항식 순서화에 대해) 가장 큰 단항식의 항입니다.

구체적으로, $R$ 을 다항식의 임의의 링이라고 놓습니다. 그런-다음 $R$ 에서 (일계수) 단항식의 집합 $M$ 은 계수의 필드(field)에 걸쳐 벡터 공간(vector space)으로 고려된, $R$ 의 기저(basis)입니다. 따라서 $R$ 에서 임의의 비-영 다항식 $p$ 는 단항식의 선형 조합(linear combination)으로 고유한 표현 $p=\textstyle \sum _{u\in S}c_{u}u$ 을 가지며, 여기서 $S$ 는 $M$ 의 유한 부분집합이고 $c u$ 는 모두 비-영입니다. 단항식 순서가 선택될 때, 선행 단항식은 $S$ 에서 가장 큰 $u$ , 선행 계수는 해당하는 $c u$ 이고, 선행 항은 해당하는 $c u u$ 입니다. 머리 단항식/계수/항은 때때로 "선행"의 동의어로 사용됩니다. 일부 저자는 "항" 대신에 "단항식" 및 "단항식" 대신에 "거듭제곱 곱"을 사용합니다. 이 기사에서, 단항식은 계수를 포함하지 않는 것으로 가정됩니다.

단항식 순서화의 정의하는 속성은 다항식에 단항식을 곱할 때 항의 순서가 유지됨을 의미합니다. 역시, 다항식의 곱의 선행 항은 인수의 선행 항의 곱입니다.

Examples

임의의 한 변수 x의 거듭제곱의 집합 $\left\{x^{n}\mid n\in \mathbb {N} \right\}$ 위에, 오직 단항식 순서는 자연스러운 순서화 1 < x < x² < x³ < ... 및 그것의 역이며, 그것의 후자는 바른-순서화가 아닙니다. 그러므로, 단항식 순서의 개념은 여러 변수의 경우에서 오직 흥미롭게 됩니다.

단항식 순서는 개별적인 불확정에 대한 순서를 의미합니다. 우리는 불확정이, 항상 x₁ > x₂ > x₃ > …이 되도록, 고려된 단항식 순서에 대해 감소하는 순서에서 x₁, x₂, x₃, ...으로 이름지은 것으로 가정함으로써 단항식 순서의 분류를 단순화할 수 있습니다. (만약 무한하게 많은 불확정이 있어야 하면, 이 관례는 바른 순서화가 되는 것의 조건과 호환되지 않고, 우리는 반대 순서화를 사용하도록 강요될 것입니다; 어쨌든, 무한하게 많은 변수에서 다항식의 경우는 거의 고려되지 않습니다.) 아래 예제에서 우리는 x₁, x₂ 및 x₃ 대신에 x, y 및 z를 사용합니다. 이 관례와 함께, 여전히 다른 단항식 순서의 많은 예제가 있습니다.

Lexicographic order

사전식 순서(Lexicographic order 줄여서 lex)는 먼저 단항식에서 x₁의 지수를 비교하고, 상등의 경우에서 x₂의 지수를 비교하고, 이런 식입니다. 그 이름은, 만약 단항식이 불확정의 지수의 수열에 의해 표현되면, 사전에 대해 사전-편집(lexicography)에서 사용되는 보통의 알파벳 순서(alphabetical order)와 유사성에서 파생됩니다. 만약 불확정의 숫자가 고정되면 (보통의 경우에서 처럼), 사전식 순서는, 비록 이것이 다양한 길이의 수열에 적용된 사전식 순서(lexicographical order)에 대한 경우가 아닐지라도, 바른-순서(well-order)입니다 (Lexicographic order § 다양한 길이의 수열의 순서화를 참조하십시오). 그뢰브너 기저(Gröbner basis) 계산에 대해, 이 순서화는 가장 비용이 많이 드는 경향이 있습니다; 따라서 그것은 매우 간단한 계산을 제외하고는 가능한 한 피해져야 합니다.

Graded lexicographic order

등급화된 사전식 순서(Graded lexicographic order, 줄여서 grlex, 또는 차수 사전식 순서(degree lexicographic order)에 대해 deglex)는 먼저 전체 차수 (모든 지수의 합)을 비교하고, 동점의 경우에서 사전식 순서를 적용합니다. 이 순서화는 바른 순서화일뿐만 아니라, 그것은 임의의 단항식이 다른 단항식의 유한 숫자에 의해 오직 선행된다는 속성을 가집니다; 이것은 x의 모든 (무한하게 많은) 거듭제곱이 y보다 작은, 사전식 순서에 대해 경우가 아닙니다 (사전식 순서는 그럼에도 불구하고 무한히 감소하는 단항식의 사슬을 구성하는 것이 불가능한 것과 관련이 있습니다). 비록 매우 자연스럽지만, 이 순서화는 거의 사용되지 않습니다: 그것이 따르는, 등급화된 역 사전식 순서에 대한 그뢰브너 기저(Gröbner basis)는 계산하기가 더 쉽고 입력 다항식의 집합에 대한 같은 정보를 제공합니다.

Graded reverse lexicographic order

등급화된 역 사전식 순서(Graded reverse lexicographic order, 줄여서 grevlex 또는 차수 역 사전식 순서(degree reverse lexicographic order)에 대해 degrevlex)는 먼저 전체 차수를 비교하고, 그런-다음 역 사전 사전 순서를 동점-깨기로 사용하지만, 그것은 같은 차수의 사전식으로 더 큰 단항식이 더 작은 degrevlex인 것으로 고려되도록 사전식 비교의 결과를 거꾸로 합니다. 불확정의 전통적인 순서화 x₁ > x₂ > … > x_n를 표시하기 위한 최종 순서에 대해, 거꾸로 하기 전에 동점-깨기 사전식 순서는 마지막 불확정 x_n을 가장 큰 것으로 여기는 것이 더욱 필요하며, 이것은 그것이 해당 불확정으로 시작해야 함을 의미합니다. 등급화된 역 사전식 순서에 대해 구체적인 방법은 따라서 먼저 전체 차수로 비교하는 것이며, 그런-다음 마지막 불확정 x_n의 지수를 비교하지만 그 결과를 거꾸로 하며 (따라서 더 작은 지수를 갖는 단항식은 순서화에서 더 큽니다), x_n−1의 유사한 비교가 (오직 동점의 경우에서 항상 그런 것처럼) 뒤따르고, 이런 식으로 해서 x₁에서 끝납니다.

등급화된 사전식 순서와 등급화된 역 사전식 순서 사이의 차이는 미묘한데, 왜냐하면 그것들은 사실 1과 2 불확정에 대해 일치하기 때문입니다. 첫 번째 차이는 3 불확정에서 차수 2 단항식에 대해 오며, 이것은 $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}$ 으로 등급화된 역 사전식 순서입니다. 일반적인 경향은 역 순서가 임의의 주어진 차수의 작은 단항식 중에서 모든 변수를 나타내지만, 비-역 순서와 함께 임의의 주어진 차수의 가장 작은 단항식의 구간이 가장 작은 변수로부터 오직 형성될 것입니다.

Elimination order

블록 순서(Block order) 또는 제거 순서(elimination order) (lexdeg)는 임의의 숫자의 블록에 대해 정의될 수 있지만, 간단하게 하기 위해, 우리는 두 블록의 경우를 오직 고려합니다 (어쨌든, 만약 블록의 숫자가 변수의 숫자와 같으면, 이 순서는 간단히 사전식 순서입니다). 이 순서화에 대해, 변수는 두 블록 x₁,..., x_h 및 y₁,...,y_k로 나뉘고 단항식 순서화는 각 블록에 대해, 보통 등급화된 역 사전식 순서가 선택됩니다. 두 단항식은 그들의 x 부분을 비교하고, 동점의 경우에서, 그들의 y 부분을 비교함으로써 비교됩니다. 이 순서화는 중요한데, 왜냐하면 그것이 제거, 대수 기하학에서 투영에 해당하는 연산을 허용하기 때문입니다.

Weight order

가중 순서(Weight order)는 가중 벡터로 불리는 벡터 $(a_{1},\ldots ,a_{n})\in \mathbb {R} _{\geq 0}^{n}$ 에 의존합니다. 그것은 먼저 이 가중 벡터를 갖는 단항식의 지수 수열의 점 곱(dot product)을 비교하고, 동점의 경우에서 어떤 다른 고정된 단항식 순서를 사용합니다. 예를 들어, 위의 등급화된 순서는 "전체 순서" 가중 벡터 (1,1,...,1)에 대해 가중 순서입니다. 만약 a_i가 유리적으로 독립(rationally independent) 숫자이면 (따라서 특히 그들 중 어떤 것도 영이 아니고 모든 분수 ${\tfrac {a_{i}}{a_{j}}}$ 가 무리적이면), 동점이 절대 발생할 수 없고, 가중 벡터 자체는 단항식 순서화를 지정합니다. 반대 경우에서, 우리는 동점을 깨기 위해 또 다른 가중 벡터를 사용할 수 있고, 계속 이런 식입니다; n 선형적으로 독립 가중 벡터를 사용한 후에, 임의의 남아있는 동점이 절대 있을 수 없습니다. 우리는 실제로 가중 벡터 수열 (Cox et al. pp. 72–73), 예를 들어 lex에 대해 (1,0,0,...,0), (0,1,0,...,0), ... (0,0,...,1), 또는 grevlex에 대해 (1,1,1,...,1), (1,1,..., 1,0), ... (1,0,...,0)에 의해 임의의 단항 순서화를 정의할 수 있습니다.

예를 들어, 단항식 $xy^{2}z$ , $z^{2}$ , $x^{3}$ , 및 $x^{2}z^{2}$ 를 생각해 보십시오; 위의 단항식 순서는 다음처럼 이들 네 단항식을 순서화합니다:

Lex: $x^{3}>x^{2}z^{2}>xy^{2}z>z^{2}$ ( $x$ 의 거듭제곱이 지배합니다).
Grlex: $x^{2}z^{2}>xy^{2}z>x^{3}>z^{2}$ (전체 차수가 지배합니다; $x$ 의 더 높은 거듭제곱이 처음 둘 사이의 동점을 깹니다).
Grevlex: $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은 여기서 깨지게 되어 임의의 동점을 남기지 않습니다).

Related notions

제거 순서는 불확정의 집합의 임의의 것을 포함하는 단항식이 항상 그들 중 어느 것도 포함하지 않는 단항식보다 더 크다는 것을 보장합니다.
곱 순서는 제거 순서의 더 쉬운 예제입니다. 그것은 불확정의 서로소 집합에 대한 단항식 순서를 그들의 합집합에 대한 단항식 순서를 결합하는 것으로 구성됩니다. 그것은 첫 번째 단항식 순서를 사용하여 첫 번째 집합에서 불확정의 지수를 비교하며, 그런-다음 두 번째 집합의 불확정에 대한 다른 단항식 순서화를 사용하여 동점을 깹니다. 이 방법은 명확하게 불확정의 집합의 임의의 서로소 합집합으로 일반화됩니다; 사전식 순서는 (각 한원소에 대해 고유한 단항식 순서와 함께) 한원소 집합 {x₁}, {x₂}, {x₃}, ...에서 따라서 얻어질 수 있습니다.

그뢰브너 기저(Gröbner bases)를 계산하기 위해 단항식 순서화를 사용할 때, 다른 순서는 다른 결과로 이어질 수 있고, 계산의 어려움이 극적으로 변할 수 있습니다. 예를 들어, 등급화된 역 사전식 순서는, 거의 항상, 계산하기 가장 쉬운 것으로 그뢰브너 기저를 생성하는 것으로 유명합니다 (이것은 아이디얼에 대한 꽤 공통적인 조건 아래에서, 그뢰브너 기저에서 다항식은 변수의 숫자에서 많아야 지수인 차수를 가진다는 사실에 의해 강력히 주장됩니다; 그러한 복잡한 결과는 임의의 다른 순서에 대해 존재하지 않습니다). 다른 한편으로, 제거 순서는 제거(elimination) 및 관련 문제에 대해 요구됩니다.

References

David Cox; John Little; Donal O'Shea (2007). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer. ISBN 0-387-35650-9.