Gröbner Basis와 Buchberger's algorithm, 그 활용
목표
Gröbner Basis는 주어진 몇 개의 다항식들로 생성되는 환에 대한 분석을 쉽게 해주는 강력한 툴입니다. 이 포스트의 목표는 Gröbner Basis를 구할 수 있는 Buchberger’s algorithm과 그 정당성에 대해 직관적으로 이해하고, Gröbner Basis를 통해서 해결할 수 있는 문제들에 대해 알아보는 것입니다.
사전지식 - Basic Algebra
이 단락에서는 환과 아이디얼이 무엇인지에 대해 다룹니다.
환이라는 것은, 간단히 말해 덧셈과 곱셈이 정의되어있고, 결합법칙, 분배법칙, 덧셈에 대한 교환법칙이 성립하며, 덧셈에 대한 항등원과 역원이 존재하고, 곱셈에 대한 항등원이 존재하는 대수구조를 말합니다.
간단한 예시로는 정수들의 집합, $Z/nZ$, $R$등을 들 수 있습니다.
양의 정수의 집합 $N$이나 홀수들의 집합은 환이 아닌데, 둘 다 덧셈에 대한 항등원이 존재하지 않기 때문입니다. 곱셈에 대한 항등원이 없는 $nZ$또한 환이 아닙니다.
특히, $k$가 체라고 했을 때, $k[x_1,x_2,…,x_n]$은 환입니다.
어떤 환 $R$의 부분환이라는 것은, 환 $R$의 부분집합에 $R$의 덧셈과 곱셈이 부여된 대수구조가 환을 이루는 경우입니다. 예컨대, $Z$는 $R$의 부분환입니다.
| 환 $R$의 부분환 $I$가 아이디얼이라는 것은, $IR=\{ ir | i\in I, r\in R \}=RI=I$이라는 것을 말합니다. |
몇 가지 예시를 들어보자면, $Z$는 $R$의 부분환이었지만, 아이디얼은 아닌데, 왜냐하면 $2\pi\notin Z$이기 때문입니다. 정수계수 다항식 $Z[x]$는 환이며, 정수계수 다항식중 상수항이 0인 것들만 모아둔 $xZ[x]$는 그 아이디얼임을 쉽게 알 수 있습니다.
뇌터 환이라는 것은 다양한 정의가 존재하는데, 그중 한 가지 정의는 $R$의 가능한 모든 아이디얼 체인 $I_1\subset I_2\subset I_3…$가 무한히 커질 수는 없다는 것입니다.
본 포스팅에서는 어떤 체 $K$의 원소들을 계수로 가지는 다항식들에 대해서만 분석할 것입니다.
Proposition. $R$이 뇌터 환이라고 할 때, $R[x_1,…,x_n]$ 또한 뇌터 환입니다.
어떤 다항식 환 $K[x_1,x_2,…,x_m]$의 다항식들의 집합 $P=\{p_1,…,p_n\}$이 주어졌을 때, 이들에 의해 생성되는 아이디얼은 $\lt P\gt=\{p_1 f_1+…+p_n f_n|f_i\in K[x_1,x_2,…,x_m],p_i\in P\}$과 같이 정의됩니다.
선형대수학적으로 생각해보면, $P$의 다항식들을 기저로 하여 span되는 대수구조라고 해석할 수 있습니다.
다항식 환에서, 어떤 아이디얼의 “해”라는 것은, 해당 아이디얼에 속한 모든 다항식을 0으로 만드는 tuple $(x_1,…,x_n)$들의 집합입니다.
Proposition(Hilbert’s Basis Theorem). 모든 $K[x_1,…,x_n]$의 아이디얼 $I$에 대해서, 유한개의 다항식 $f_1,…,f_m\in K[x_1,…,x_n]$이 존재하여, $I=<f_1,…,f_m>$을 만족합니다.
개요
본 포스팅에서는 궁극적으로 다음과 같은 문제를 해결하고 싶습니다:
주어진 두 다항식들의 집합 $P,Q$에 대해서, $P,Q$ 각각에 의해 생성되는 아이디얼이 동일한가?
직관적으로 생각해보면 한 집합에 속한 어떤 다항식이 다른 집합의 다항식들의 결합으로 표현될 수 있는지만 다항식 나눗셈으로 확인하면 될 것처럼 생각되지만, 중요한 것은 일변수 다항식과는 달리, 다변수 다항식의 경우에는 나누는 순서가 결과에 영향을 미칠 수 있다는 점입니다.
Example. $Z[x,y]$의 다항식 $f=xy^2-x$를 $f_1=xy-y, f_2=y^2-x$로 나누는 경우를 생각해보겠습니다.
- $f_1,f_2$ 순서로 나누는 경우 $f=f_1y+f2$
- $f_2,f_1$ 순서로 나누는 경우 $f=f_2x+x^2-x$
다음과 같이, 어떤 순서로 나누는가에 따라 그 나머지가 달라질 수 있고, 이는 곧 다항식이 어떤 집합에 의해 생성된 아이디얼에 속하는지 판정하는 문제가 그렇게 간단하지 않다는 점을 보여줍니다.
이런 측면에서, 우리가 해결하고자 하는 문제는 다변수 다항식 나눗셈과 간접적으로 연관되어있다고도 볼 수 있습니다.
Gröbner Basis
Gröbner Basis라는 것은, 주어진 다항식들의 집합 $P$와 동일한 아이디얼을 생성하면서, 특수한 성질을 만족하는 어떤 다항식들의 집합입니다.
이에 대해 설명하기 위해선, 우선 다항식을 구성하는 각 항들에 대한 순서를 도입해야 합니다.
Definition. $K[x_1,…,x_n]$의 term order이라는 것은, 그 내부에 존재할 수 있는 모든 monomial들 $x^a=x_1^{a_1}x_2^{a_2}…x_n^{a_n}$에 대한 total order로, 다음의 두 조건을 만족합니다:
- $\forall a,b,c\in N^{n}, x^a<x^b\to x^{a+c}<x^{b+c}$
- $\forall a\in N^{n}/\{ 0 \}, 1<x^a$
예컨대, $n=2$인 경우를 생각해보면, 다음과 같은 전순서는 term order라는 사실을 알 수 있습니다:
$1<x_1<x_2<x_1^2<x_1x_2<x_2^2<x_1^3<…$
이러한 전순서 하나를 고정한 채로 생각해보겠습니다. 그렇다면, 모든 다항식들은 최고차항을 가질 것입니다. 이러한 $f$의 최고차항에 해당되는 단항식을 $f$의 initial term이라고 하고, $in_<(f)=x^a$와 같이 표기하겠습니다.
어떤 아이디얼 $I$에 대해서, $in_<(I)=<in_<(f)|f\in I>$와 같이 정의하고, 이를 $I$의 initial ideal이라고 정의하겠습니다. 이제 Gröbner Basis의 정의에 대해 설명하겠습니다.
| Definition. 어떤 아이디얼 $I$의 유한한 부분집합 $G$가 term order $<$에 대해서 Gröbner Basis이라는 것은, $in_<(I)=in_<(G)=<in_<(g) | g\in G>$를 만족한다는 것입니다. |
즉, 간단히 말해서 $G$의 initial ideal만으로 $I$의 initial ideal을 만들 수 있다면, $G$를 Gröbner Basis이라고 합니다.
위의 정의만으로는 간단하게 생각해봐도, Gröbner Basis는 크기 제한이 없고, 굉장히 다양할 수 있음을 알 수 있습니다. 만약, 마치 선형대수학에서 보았듯이, elementary row operation에 대한 행렬들의 동치류의 대표원소로서 rref가 잘 작동하듯이, Gröbner Basis에 대해서도 그 reduced form을 잘 정의해서 동치류를 대표하도록 할 수 있지 않을까요?
정말 놀랍게도, 이는 가능합니다! 추후에 정의하겠지만, 일단은 “reduced Gröbner Basis”라는 것이 존재한다고 하겠습니다.
중요한 점은 reduced Gröbner Basis는 각 아이디얼 $I$에 대해 “유일하게” 존재한다는 것입니다.
따라서, 만약 reduced Gröbner Basis를 계산하는 알고리즘이 있다면 위에서 말했던, 두 다항식들의 집합에 의해 생성되는 아이디얼이 같은지 판별하는 문제를 해결할 수 있을 것입니다! 두 집합의 reduced Gröbner Basis가 같은지 판별하면 되기 때문입니다.
Buchberger’s algorithm
Buchberger’s algorithm은 일차적으로 Gröbner Basis를 계산하는 알고리즘입니다. 해당 알고리즘은 다음과 같은 몇가지 사실들에 의거하여 Gröbner Basis를 계산합니다:
Definition. 두 다항식 $p,q$에 대해서, 그들의 S-polynomial이라는 것은 $S(p,q)=ap-bq$인데, 여기서 $a,b$는 $in_<(ap)=in_M(bq)$를 만족하는 최소의 유일한 단항식 $a,b$입니다.
어떤 다항식들의 집합 $G$에 대해서 $f$를 나눈다는 것은, 다음과 같은 알고리즘을 실행한다는 것입니다:
- $r_0=0$으로 설정
- $f$의 최고차항이 어떤 $g_i$의 최고차항의 $m_i$배라면($m_i$는 어떤 단항식), $f=f-m_ig_i$로 설정. 이를 실행할 수 없을 때 까지 실행. 만약 $f=0$이면 $r_0$를 return. 그렇지 않다면 다음 스텝으로 이동.
- $f$의 최고차항을 $m$이라고 하자. $r_0=r_0+m$으로 설정, $f=f-m$으로 설정. 만약 $f=0$이라면, $r_0$를 return. 그렇지 않다면 이전 스텝으로 이동.
직관적으로 보았을 때 해당 시행은 3번 과정을 진행할 때마다 $f$의 최고차항의 차수를 감소시킴을 알 수 있고, 이는 단항식들에 대한 전순서에 대한 것이기 때문에, 어느 순간에는 위의 알고리즘이 종료하게 됩니다.
위의 알고리즘에 의해 결과 $r_0$가 도출된 것을, $f\to_Gr_0$와 같이 표기합니다.
Proposition(Buchberger’s Criterion). $I=<g_1,…,g_k>$에 대해서, $G=\{ g_1,…,g_k \}$가 $I$의 Gröbner Basis라는 것은, 모든 가능한 $f,g\in G$에 대해서, $S(f,g)\to_G 0$을 만족하는 것입니다.
이 판정조건이 있다면, 이제 Buchberger’s algorithm을 이해할 수 있습니다.
Buchberger’s algorithm: 입력: 다항식들의 집합 $\{ f_1,…,f_m \}$ 출력: $I=<f_1,…,f_m>$의 Gröbner Basis $G$ 작동과정:
- $G=\{ f_1,…,f_m \}$으로 설정.
- $G$ 내부의 임의의 $p,q$를 잡고, $S(p,q)\to_Gf$로 설정. 만약 $f\neq 0$이라면, $G=G\cup \{ f \}$로 설정하고, 해당 스텝의 첫 번째로 돌아감. $f=0$이라면, 다른 $p,q$로 해당 스텝을 시도. 만약 모든 $p,q$의 선택에 대해 $S(p,q)\to 0$이라면, $G$를 반환.
이 알고리즘이 만약 끝난다면, 그 결과물이 Gröbner Basis임은 명백합니다. 따라서 해당 알고리즘이 유한번의 연산 내에 끝난다는 사실만 증명하면 충분합니다. 만약 해당 알고리즘이 계속 끝나지 않는다면, 2번 스텝에서 $f\neq 0$을 발견할 때마다, $I=\{ in_<(g)|g\in G \}$는 이전의 것을 strict하게 포함할 것입니다. 즉, 무한히 증가하는 아이디얼의 chain을 발견한 것이기 때문에, $Z[x_1,…,x_n]$이 뇌터 환이라는 사실에 모순입니다.
따라서, 위 알고리즘은 언젠간 종료됩니다.
다만, 해당 알고리즘의 작동시간은 매우 오래걸리는데, 최고차수가 $D$이고, $n$개의 변수를 가지고 있는 다항식들의 집합에 대해 알고리즘을 진행할 경우 $\Omega(D^n)$의 시간복잡도를 가지고, 최악의 경우에는 $O(D^{2^n})$의 시간복잡도를 가지기 때문입니다.
이제, 우리는 주어진 다항식들에 의해 만들어지는 아이디얼의 Gröbner Basis를 찾아내는데에 성공했습니다! 그렇다면 reduced Gröbner Basis를 찾는 것은 어떻게 할까요?
우선, 먼저 minimal한 Gröbner Basis를 계산하는 것부터 시작해봅시다.
어떤 Gröbner Basis $G$가 minimal하다는 것은, $G$의 모든 원소의 최고차항의 계수가 1이며, 어떤 두 원소 $p,q\in G$에 대해, $p$의 최고차항이 $q$의 최고차항을 나누는 경우가 없다는 것입니다.
정의를 살펴보면, Gröbner Basis를 minimal하게 바꾸는 것은 그리 어렵지 않음을 알 수 있습니다. 최고차항의 계수로 정규화한 다음, 한쪽의 최고차항이 다른쪽의 최고차항을 나눈다면 유클리드 알고리즘을 돌리듯이 적절히 빼줍니다.
여전히 minimal한 Gröbner Basis는 여러개 존재할 수 있지만, 다음과 같은 강력한 성질이 성립합니다:
Proposition. $G,H$가 $I$의 두 Gröbner Basis라고 할 때, 이들을 적절히 재배열하면 $in_<(g_i)=in_(h_i)$.
이제 reduced Gröbner Basis를 정의합니다.
Definition. Gröbner Basis $G$가 reduced Gröbner Basis라는 것은, 이것이 minimal하면서, $G$의 모든 원소 $g$에 대해서, $g\to_{G/\{g\}}g$라는 것입니다.
다시말해서, $g$ 하나에 대해서 $G$의 나머지 원소들을 어떻게 적용해도 $g$를 더 작게 만드는 것은 불가능하다고 이해할 수 있습니다. 이는 RREF의 특성과도 흡사합니다.
아무튼, 이렇게 정의된 reduced Gröbner Basis는 각 아이디얼 $I$들에 대해 유일하게 존재함을 보일 수 있습니다.
Applications
이제, 이 Gröbner Basis를 가지고 무엇을 할 수 있을까요?
Ideal membership
어떤 다항식 $p$가, 주어진 다항식들 $f_1,f_2,…,f_n$에 대해서 $p=f_1g_1+…+f_ng_n(g_i\in K[x_1,x_2,…,x_m])$과 같이 나타날 수 있는지 확인할 수 있을까요?
이는 위에서 언급한 표기를 통해 나타내면, $p\in <f_1,…,f_n>$인지 판별하는 문제라고 볼 수 있습니다.
$F=\{ f_1,…,f_n \}$에 Buchberger’s algorithm을 적용하여 Gröbner Basis를 얻고, 그 위해서 $p$의 reduction 과정을 거쳐서 $p$가 $0$이 되도록 할 수 있다면, 아이디얼 안에 있다고 판정할 수 있습니다.
동일한 맥락으로, 두 다항식에 의해 생성된 아이디얼이 동일한지도 어렵지 않게 확인할 수 있습니다. 한 쪽의 모든 다항식이 다른쪽의 아이디얼에 속하는지 판별하면 되기 때문입니다.
Solvability of equations
몇 개의 $K[x_1,…,x_n]$에 속해있는 다항방정식들 $f_1=0, f_2=0, …, f_m=0$을 생각해봅시다.
이들 전체를 만족하는 해는 존재할까요?
여기에서는 $K$가 대수적으로 닫혀있다는 전제가 필요합니다. 이는 즉, $K$를 계수로 하는 다항방정식의 해를 $K$에서 찾아낼 수 있다는 뜻입니다.
이러한 체의 예시로는, 복소수체 $C$가 있습니다.
Proposition. 위의 연립다항방정식이 해를 가질 필요충분조건은, $I=<f_1,…,f_m>$이 $1$을 포함하지 않는 것이다.
3-Coloring problem
놀랍게도, Gröbner Basis는 어떤 그래프가 3-colorable한지 판별하는데에 사용될 수도 있습니다!
우선, $K=Z/3Z$로 두고 시작하겠습니다.
정점이 $n$개인 그래프 $G$를 생각합시다. 이제, $K[x_1,…,x_n]$에 속해있는 다항식들에 대해 생각하겠습니다.
여기에서, 각 정점에 $0,1,-1$중 하나의 값을 할당하는 3-coloring을 고려할 것입니다.
| 우선, 단순하게 생각해보면 $I=<x_1^3-x_1,x_2^3-x_2,…,x_n^3-x_n>$과 같은 아이디얼의 해는, $\{ (x_1,…,x_n) | x_i\in \{ -1,0,1\} \}$과 같음을 알 수 있습니다. |
여기까지 오면 어떤 전략을 통해서 그래프의 3-coloring을 나타낼지 짐작할 수 있을 것입니다. 어떤 두 정점 $u,v$가 인접해있을 때, 그 둘에 할당되는 값이 다를때에만 0이 되는 다항식을 구성하면 됩니다!
이는 다음과 같은 다항식을 고려해볼 수 있습니다:
$x^2+xy+y^2-1$
굳이 증명하지는 않겠지만, 해당 다항식은 $x\neq y$일때만 0이고, 그렇지 않을땐 항상 0이 아님을 쉽게 확인할 수 있습니다. 결국, 다음과 같은 아이디얼 $I_C=<x_i^2+x_ix_j+x_j^2-1|v_iv_j\in E(G)>$의 해는, $G$의 가능한 모든 $3-coloring$임을 알 수 있습니다!
비록 아이디얼에 대한 분석을 위해 Gröbner Basis를 계산하는 시간복잡도보다, 단순히 가능한 모든 coloring을 순회해보는 것의 시간복잡도가 느리지 않지만, Gröbner Basis를 통해서 3-coloring의 대수기하학적인 성질을 이해하고, 상황에 따라서는 더욱 빠른 계산을 제공하는 점은 분명한 이점일 것입니다. 반대로 생각해보면 Gröbner Basis를 구하는 것은 적어도 NP-complete 이상의 어려움을 가지고 있음을 알려주기도 합니다.