대칭다항식의 기본 정리와 $\text{Waring's method}$

 
오늘은 대칭다항식과 $s_1, s_2, \dots, s_n$의 관계에 대해 다루어 보려고 합니다. 일단 오늘의 주제를 얘기하기에 앞서, 정의부터 하고 넘어가겠습니다.

---

대칭다항식

다항식 $P(x_1,\ldots,x_n)$이 모든 순열 $\sigma$에 대해,
\[ P(x_{\sigma(1)},\ldots,x_{\sigma(n)}) = P(x_1,\ldots,x_n). \]
을 만족하면 대칭다항식이라고 한다. 
 
쉽게 말해서, 다항식의 변수를 서로 바꾸어도 같은 다항식이 나오는 것을 대칭다항식이라고 합니다.
 

기본 대칭다항식

기본 대칭다항식 $s_1, s_2, \ldots, s_n$을 다음과 같이 정의한다:

\begin{gather*} s_1 = \sum_{i=1}^n x_i, \quad s_2 = \sum_{i<j}^n x_i x_j, \quad  s_3 = \sum_{i<j<k}^n x_i x_j x_k, \quad \\ \cdots, \\ s_n = x_1 x_2 \cdots x_n.\end{gather*}
 
그럼 정의를 다 했으니, 메인 주제로 넘어갑시다.

---

대칭 다항식의 기본 정리

 
다항식 $P(x_1,\ldots,x_n)$을 $n$개의 변수 $x_1,\ldots,x_n$에 대한 대칭 다항식이라고 하자. 그렇다면 $P(x_1,\ldots,x_n)$은 $s_1,\ldots,s_n$으로 표현될 수 있다. 또한, 그 역도 성립한다.

---

여기서는 따로 증명을 하진 않겠습니다. 그렇다면, 주어진 대칭 다항식을 $s_1,\ldots,s_n$으로 바꾸는 알고리즘이 있을까요? 바로 $\text{Waring's method}$가 있습니다. 이 알고리즘을 살펴보기 전에, Notation을 하나 정의하겠습니다.
$$\sum x_1^{i_1}x_2^{i_2} \dots x_n^{i_n} := \sum_{k_1>k_2> \cdots > k_n}^n x_{k_1}^{i_1}x_{k_2}^{i_2} \dots x_{k_n}^{i_n}$$
우리가 대칭식을 합으로 나타낼 때, 기호 주변에 복잡한 조건을 계속 적긴 귀찮으니 앞으로는 이 Notation을 통해 간단하게 나타내겠습니다. 예를 들어, 변수가 2개인 대칭 다항식의 경우는 $$\sum x_1^2x_2 = x_1^2x_2 + x_1x_2^2$$ 로 나타낼 수 있겠습니다. 또한
\begin{gather*}
    s_1 = \sum x_1, \quad s_2 = \sum x_1x_2, \quad \\ \dots, \\ \quad s_{n-1} = \sum x_1 \dots x_{n-1}, \quad s_n = \sum x_1 \dots x_n \quad (=x_1\dots x_n).
\end{gather*}
기본 대칭 다항식도 간단하게 나타낼 수 있습니다.
 
대칭 다항식에 대해, 차수에 대해서도 생각해볼 수 있을 것입니다. $n$개의 변수가 있는 경우, 차수를 $n$-튜플로 정의할 수 있습니다. 예를 들어, $$deg(\sum x_1^{i_1}x_2^{i_2}\dots x_n^{i_n}) = (i_1,\ldots,i_n)$$ 처럼 말이죠. 여기에서 사전식 순서(lexicographic order)를 주면, 다항식 사이의 차수도 비교할 수 있습니다. 또한, 기본 대칭 다항식의 차수는
 
\[ \begin{aligned} deg\ s_1 &= (1,0,0,\ldots,0), \\ deg\ s_2 &= (1,1,0,\ldots,0), \\ &\vdots \\ deg\ s_n &= (1,1,\ldots,1,1) \end{aligned} \]
 
가 되겠습니다.
 
자, 그럼 준비가 끝났으니 주어진 대칭 다항식을 $s_1,\dots,s_n$들로 바꾸는 방법을 살펴봅시다. $\text{Waring's method}$는 유클리드 알고리즘과 유사하게, 차수를 잰 뒤 최대한 $s_1,\dots,s_n$으로 바꾸고 남은 차수에 대해 같은 방법으로 $s_1,\dots,s_n$으로 바꾸며, 이를 반복하여 결국 차수를 $(0,0,\ldots,0)$으로 만드는 것입니다. 이 과정을 수학적으로 표현하면 다음과 같습니다.

---

Steps:

1. 차수 $deg \ P = (i_1,i_2,\ldots,i_n)$ 인 대칭 다항식 $P$ 가 있다고 합시다. 일단, 우리는 $i_1 \geq i_2 \geq \dots \geq i_n$ 임을 알 수 있습니다. 그러므로 다음과 같은 다항식$f$를 생각할 수 있습니다: $$ f = s_1^{i_1-i_2}s_2^{i_2-i_3}\dots s_{n-1}^{i_{n-1}-i_n}s_n^{i_n}$$ $f$의 차수를 구해보면, $deg \ f = (i_1,i_2,\ldots,i_n)$ 입니다. 즉, $$f = x_1^{i_1}x_2^{i_2}\dots x_n^{i_n} + \text{(낮은 차수의 항들)}$$ 으로 나타낼 수 있습니다. $P$의 최고차항 계수를 $a(\neq0)$로 두면, $P$도 $$P = ax_1^{i_1}x_2^{i_2}\dots x_n^{i_n} + \text{(낮은 차수의 항들)}$$ 으로 나타낼 수 있습니다. 이제 $P_1 = P-af$ 를 정의하면, $deg \ P_1 < deg \ P$ 이고 $P_1$은 여전히 대칭 다항식입니다.
2. Step 1에서 구한 다항식의 차수를 재었을 때, 만약 차수가 $(0,0,\ldots,0)$이 아니라면 Step 1로 돌아가 똑같은 방법을 $P_1$에 적용하여 차수가 더 작은 대칭 다항식 $P_2$를 구합니다. 차수가 $(0,0,\ldots,0)$이 되면 Step을 중지합니다.

 
마지막으로 예제를 통해 $\text{Waring's method}$를 사용하여 대칭 다항식을 $s_1,\dots,s_n$으로 바꿔볼까요?

---

Example.
$$S = \sum x_1^4x_2x_3 + \sum x_1^3x_2^3$$
차수 $deg \ S = (4,1,1)$ 이므로, $f_1=s_1^{4-1}s_2^{1-1}s_3^1 = s_1^3s_3$ 입니다.
$$s_1^3 s_3 = (\sum x_1)^3(x_1 x_2 x_3) = \sum x_1^4 x_2 x_3 + 3\sum x_1^3 x_2^2 x_3 + 6x_1^2 x_2^2 x_3^2$$
따라서
$$ S = \sum x_1^3x_2^3 -3\sum x_1^3 x_2^2 x_3 - 6x_1^2 x_2^2 x_3^2 + s_1^3 s_3.$$
이제 차수 $deg \ S = (3,3,0)$ 이므로, $f_2 = s_2^3$ 을 계산해줍니다.
$$s_2^3 = (\sum x_1 x_2)^3 = \sum x_1^3x_2^3 + 3\sum x_1^3 x_2^2 x_3 + 6x_1^2 x_2^2 x_3^2$$
따라서 다음과 같은 결과를 얻습니다.
$$S = -6\sum x_1^3 x_2^2 x_3 - 12x_1^2 x_2^2 x_3^2 + s_1^3 s_3 + s_2^3.$$
다음으로, 차수 $deg \ S = (3,2,1)$ 이므로 $f_3 = s_1 s_2 s_3$ 을 계산합시다.
$$s_1 s_2 s_3 = (\sum x_1)(\sum x_1 x_2)(\sum x_1 x_2 x_3) = \sum x_1^3 x_2^2 x_3 + 3x_1^2 x_2^2 x_3^2,$$
따라서
$$ S = 6x_1^2 x_2^2 x_3^2 + s_1^3 s_3 + s_2^3 - 6s_1 s_2 s_3.$$
$x_1^2 x_2^2 x_3^2=s_3^2$이므로, 최종적으로 다음과 같은 결과를 얻게 됩니다.
$$S = s_1^3 s_3 + s_2^3 - 6s_1 s_2 s_3 + 6s_3^2.$$
간단한 예제를 살펴봤는데, 아마 $\text{Waring's method}$로 대칭 다항식을 $s_1,\dots,s_n$으로 표현하는 것이 쉽지 않다는 것을 느끼셨을 것입니다. 오늘은 여기까지입니다. 감사합니다.