Тема 18

Симетрични полиноми над поле. Основна теорема за симетричните полиноми.

Едночлени

Нека $A$ е област на цялост.
Тогава $A[x]$ е множеството от полиноми над $A$ на една променлива.
$A[x][y]$ е множеството от полиноми на една променлива над $A[x]$, или алтернативно може да го разглеждаме като множеството от полиноми на две променливи над $A$. За удобство ще записваме $A[x, y]$.
Респективно $A[x_1, x_2, \cdots, x_n]$ е множеството от полиноми на $n$ променливи над $A$. Всеки от тях може да бъде записан като:

(1)
\begin{align} \sum_\alpha \underbrace{a_\alpha \prod_{i=1}^{n} x_i ^ {k_i}}_{t_\alpha} \end{align}

Където $t_\alpha$ e едночлен.
Степен на променлива на едночлен е … степента, с която променливата участва в едночлена: $\deg_{x_s} t = k_s$.
Степен на едночлен наричаме сумата от степените на всички променливи: $\deg t = k_1 + k_2 + \cdots + k_n$.
Степен на полином е най-голямата степен на едночлен в полинома: $\deg f = \max \{ \deg t \}$
Подобни едночлени наричаме едночлени, които се различават само по константата си. Нека $t = ax_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}$ и $l = b x_1^{s_1} x_2^{s_2}\cdots x_n^{s_n}$. Тогава $t \sim l \iff s_i = k_i \quad i = \overline{1,n} \And a \ne b$.

Лексикографска наредба

Ще трябва да въведем някаква подредба на едночлените, т.е когато записваме полинома първо да слагаме 'по-големите' едночлени после 'по-малките'.
Нека

(2)
\begin{eqnarray} t &=& ax_1^{k_1}x_2^{k_2}\cdots x_n^{k_n} \\ l &=& bx_1^{s_1}x_2^{s_2}\cdots x_n^{s_n} \\ \end{eqnarray}

Тогава $t \succ l$ ($t$ предшества $l$) ако:

  1. $t \nsim l$
  2. $\exists i : k_j = s_j\quad \forall j < i \And k_i > s_i$

Записваме полинома $f = t_1 + t_2 + \cdots + t_p$ по този начин, ако $t_1 \succ t_2 \succ t_3 \cdots \succ t_p$.

Дефиниция (Главен едночлен)

Нека $f = t_1 + t_2 + \cdots + t_p$ е полином. Тогава $t_1$ е неговият главен едночлен ако $t_1 \succ t_i \quad \forall i > 1$. (т.е ако го запишем както сме описали в предната точка - първия).

Лема

Нека $f, g \in F[x_1, x_2, \cdots, x_n]$. Тогава главният едночлен на $f.g$ е произведение на главните едночлени на $f$ и $g$.

Доказателство:

Нека $t$ и $l$ са главните едночлени на $f$ и $g$ и нека $u$ и $v$ са произволни едночлени от $f$ и $g$. Ще докажем, че $t.l \succ u.v$. Означаваме си $t, l, u, v$:

(3)
\begin{eqnarray} t = a \prod_{i=1}^{n} x_i^{k_i} & & l = b \prod_{i=1}^{n} x_i^{s_i} \\ u = c \prod_{i=1}^{n} x_i^{r_i} & & v = d \prod_{i=1}^{n} x_i^{q_i} \\ \end{eqnarray}
  1. $\exists p : k_j = r_j \quad \forall j < p \And k_p > r_p$
  2. $\exists w : s_j = q_j \quad \forall j < w \And s_w > q_w$

Нека $m = \min \{ p, w \}$. Следователно $x_i^{k_i + s_i} = x_i^{r_i + q_i} \quad \forall i < m$ и $x_m ^{k_m + s_m} > x_m ^{r_m + q_m}$, т.е $t.l \succ u.v$.

Симетрични полиноми

Нека $t = \prod x_i^{k_i}$ е едночлен и $\sigma \in S_n$ ( $\sigma$ е пермутация на $n$ променливи).
Тогава $\sigma(t) = \prod x_{\sigma(i)}^{k_i}$. (разместваме променливите на едночлена чрез пермутацията).
Сега може да дефинираме и действието на пермутацията върху полином:

(4)
\begin{eqnarray} f &=& t_1 + t_2 + \cdots + t_m \\ \sigma(f) &=& \sigma(t_1) + \sigma(t_2) + \cdots + \sigma(t_m) \\ \end{eqnarray}

Може да кажем, че $\sigma$ действа върху множеството от $F[x_1, \cdots, x_n]$.

Дефиниция (Симетричен полином)

$f \in F[x_1, \cdots, x_n]$ наричаме симетричен полином ако е изпълнено, че $\sigma(f) = f \quad \forall \sigma \in S_n$.

Примери

Елементарни симетрични полиноми:

(5)
\begin{eqnarray} \sigma_1 &=& x_1 + x_2 + \cdots + x_n = \sum_{i=1}^{n} x_i \\ \sigma_2 &=& x_1x_2 + x_1x_3 + \cdots + x_{n-1}x_n = \sum_{i < j} x_ix_j \\ &\vdots& \\ \sigma_n &=& x_1x_2 \cdots x_n = \prod_{i=1}^{n} x_i \\ \end{eqnarray}

Други интересни суми:

(6)
\begin{eqnarray} s_2 &=& \sum_{i=1}^{n} x_i^2 \\ s_3 &=& \sum_{i=1}^{n} x_i^3 \\ &\vdots & \\ \end{eqnarray}

Основна теорема за симетричните полиноми

Теорема: Нека $f(x_1, x_2, \cdots, x_n) \in F[x_1, x_2, \cdots, x_n]$ е симетричен полином.
Тогава съществува единствен полином $g \in F[x_1, x_2, \cdots, x_n]$ такъв, че:

(7)
\begin{align} g(\sigma_1, \sigma_2, \cdots, \sigma_n) = f(x_1, x_2, \cdots, x_n) \end{align}

С други думи всеки симетричен полином може да бъде изразен като полином на елементарните симетрични полиноми.

Доказателство:

$| \exists |$ Съществуване:
С $g_x$ ще бележим полином на елементарните симетрични полиноми, а с $f_x$ ще отбелязваме просто симетричен полином. На всяка стъпка ще отделяме по един g-полином като си осигуряваме, че отделяйки го с него си 'заминава' и главния едночлен от f-полинома. От $f$ отделяме $g_1$ и се получава $f_1$ ($f_1 = f - g_1$), като главният едночлен на $f_1$ е след главният едночлен на $f$.

(8)
\begin{eqnarray} f &=& g_1 + f_1 \\ f_1 &=& g_2 + f_2 \\ &\vdots& \\ f_{s-1} &=& g_s + f_s \\ f_s &=& 0 \\ f &=& g_1 + g_2 + g_3 + \cdots + g_s \\ \end{eqnarray}

Ако всеки път намаляваме главния едночлен ще стигнем до нула и като резултат получаваме $f$ като сума на g-полиноми, което очевидно е g-полином. Сега ще покажем как се отделя от произволен f-полином g-полином така че да махнем главния едночлен на f-полинома.

Нека $f$ е симетричен и има главен едночлен $t = ax_1^{k_1} x_2^{k_2} \cdots x_n^{k_n}$. Тогава със сигурност в $f$ са всички едночлени от вида $x_1^{k_{\sigma(1)}}x_2^{k_{\sigma(2)}}\cdots x_n^{k_{\sigma(n)}}$ за всяко $\sigma \in S_n$ (дали ще пермутираме буквите или степените е без значение). Това означава, че със сигурност за главният едночлен е изпълнено $k_1 \ge k_2 \ge \cdots \ge k_n$ (ако не са подредени по големина, то съществува пермутация която ги подрежда по големина; тъй като подреденият едночлен ще присъства в полинома, той би бил преди главния - противоречие).
Сега си конструираме $g_1 = a\sigma_1^{k_1 - k_2}\sigma_2^{k_2 - k_3} \cdots \sigma_{n-1}^{k_{n-1} - k_n}\sigma_n^{k_n}$. Ще проверим, че главният едночлен на $g_1$ е точно $t$. За целта трябва да видим кои са главните едночлени на $\sigma_1, \sigma_2, \cdots, \sigma_n$ (ползваме Лемата).
$t' = ax_1^{k_1 - k_2}(x_1x_2)^{k_2 - k_3} \cdots (x_1x_2\cdots x_{n-1})^{k_{n-1} - k_n}(x_1x_2\cdots x_n)^{k_n} = ax_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}$ - всичко точно.

Е, сега вече очевидно $f_1 = f - g_1$ има главен едночлен по-малък от главния едночлен на $f$ и на $g_1$ (които съвпадат) т.е в частност е по-малък от $t$. $g_1$ е симетричен полином, следователно и разликата на симетрични полиноми $f - g_1 = f_1$ също е симетричен полином.
Повтаряме стъпката докато $f_s$ стане 0. Разложихме $f$ на $g_1 + g_2 + \cdots + g_n$, което е сума на полиноми на елементарни симетрични полиноми - т.е полином на елементарни симетрични полиноми.

$| ! |$ Единственост
Сега ще докажем, че съществува единствен полином $g(y_1, y_2, \cdots, y_n)$ над полето $F$, за който $g(\sigma_1, \cdots, \sigma_n) = f(x_1, x_2, \cdots, x_n)$.

Забележка: Обърнете внимание, че ние искаме полинома да е единствен по отношение на коефициентите си, а не по отношение на функционалните си стойности.

Да допуснем противното - че съществуват два полинома $g_1, g_2$ с коефициенти над $F$, за които

(9)
\begin{align} f(x_1, \cdots, x_n) = g_1(\sigma_1, \cdots, \sigma_n) = g_2(\sigma_1, \cdots, \sigma_n) \end{align}

Да си построим $h = g_1 - g_2$.
Ще докажем, че от $h(\sigma_1, \cdots, \sigma_n) = 0$ следва $h = 0$ (т.e следва че полинома $h$ е константата 0). Т.е, че ако в произволен полином над полето $F$ заместим неизвестните с $\sigma_1, \cdots, \sigma_n$ и получим 0, то полиномът е константата 0. Ще направим индукция по броя на неизвестните $n$.

База на индукцията: $n = 1$
Имаме, че $h \in F[x_1]$ и $h(\sigma_1) = 0$. Да обаче $\sigma_1 = x_1$ (когато имаме 1 променлива), затова $h(x_1) = 0$. И това е вярно за всяко $x_1$, следователно полинома $h$ е константата 0.

Индукционно предположение: Нека $h(y_1, y_2, \cdots, y_{n-1})$ е полином с коефициенти над $F$ и от $h(\sigma_1, \cdots, \sigma_{n-1}) = 0$, следва че $h = 0$.

Индукционна стъпка: Нека $h(y_1, y_2, \cdots, y_n)$ изпълнява $h(\sigma_1, \cdots, \sigma_n) = 0$. От всички полиноми, изпълняващи това условие да изберем този с най-малка степен. Ако полиномът е константата 0, тогава индукционната стъпка е направена. Допускаме, че $h$ е от степен поне 1.

Разписваме полинома $h$ по следния начин (разделяме $h$ на две части - частно и остатък при деление с $y_n$)

(10)
\begin{align} h(y_1, y_2, \cdots, y_n) = h_0(y_1, y_2, \cdots, y_{n-1}) + y_n h_1(y_1, y_2, \cdots, y_n) \quad (\star) \end{align}

Ще докажем, че $h_0 \ne 0$. Да допуснем противното - че $h_0 = 0$:
Тогава $y_n \mid h$, следователно може да запишем

(11)
\begin{align} h(y_1, \cdots, y_n) = y_n t(y_1, \cdots, y_n) \end{align}

където $t$ е частното при деление на $h$ с $y_1$. Да заместим неизвестните с $\sigma_1, \cdots, \sigma_n$:

(12)
\begin{eqnarray} h(\sigma_1, \cdots, \sigma_n) &=& \sigma_n t(\sigma_1, \cdots, \sigma_n) \\ 0 &=& \sigma_n t(\sigma_1, \cdots, \sigma_n) \end{eqnarray}

Сега очевидно $\sigma_n \ne 0$ (за произволни стойности на $x_1, \cdots, x_n$). Тогава излиза, че $t(\sigma_1, \cdots, \sigma_n) = 0$ (защото $F$ е област на цялост - т.е няма делители на нулата). Обаче $t$ е полином със степен по-малка от $\deg h$.1 Противоречие (от избора на $h$).
Следователно $h_0 \ne 0$.
Сега имаме, че $h_0 \ne 0$. Да заместим в $(\star)$ с $\sigma_1, \cdots, \sigma_n$

(13)
\begin{align} h(\sigma_1, \cdots, \sigma_n) = h_0(\sigma_1, \cdots, \sigma_{n-1}) + \sigma_n t(\sigma_1, \cdots, \sigma_n) \end{align}

От допускането имаме, че:

(14)
\begin{align} 0 = h_0(\sigma_1, \cdots, \sigma_{n-1}) + \sigma_n t(\sigma_1, \cdots, \sigma_n) \end{align}

И горното равенство е вярно за произволни $x_1, x_2, \cdots, x_n$ (те изграждат $\sigma_1, \cdots, \sigma_n$). Това означава, че равенството пак ще е изпълнено, ако си фиксираме $x_n = 0$. Да разгледаме какво се случва със $\sigma_1, \cdots, \sigma_n$ в този случай:

(15)
\begin{eqnarray} \sigma_1^{(n)} = &x_1 + x_2 + \cdots + x_{n-1} + 0& = \sigma_1^{(n-1)} \\ \sigma_2^{(n)} = &x_1x_2 + x_1x_3 + \cdots + x_1x_{n-1} + 0 + \cdots x_{n-2}x_{n-1}& = \sigma_2^{(n-1)} \\ &\vdots& \\ \sigma_{n-1}^{(n)} = &x_1x_2\cdots x_{n-1}& = \sigma_{n-1}^{(n-1)} \\ \sigma_n = &\sigma_1\sigma_2\cdots \sigma_{n-1} 0& = 0 \end{eqnarray}

Забележка: С горен индекс $(n)$ отбелязваме на колко променливи сме разгледали елементарните симетрични полиноми.
Както ясно се вижда, ако $x_n = 0$, елементарните симетрични полиноми на $n$ променливи се превръщат елементарни симетрични полиноми на $n-1$ променливи, с изключение на $\sigma_n$, което става равно на 0. Ако се върнем към равенството и заместим с новите $\sigma_i^{(n-1)}$ получаваме:

(16)
\begin{align} 0 = h_0(\sigma_1^{(n-1)}, \sigma_2^{(n-1)}, \cdots, \sigma_{n-1}^{(n-1)}) + 0 t (\sigma_1^{(n-1)}, \cdots, \sigma_{n-1}^{(n-1)}, 0) \end{align}

От индукционното предположение имаме, че ако $h_0$ е такъв полоном, че заместен с елементарните симетрични полиноми се получава 0, то и самия $h_0$ трябва да е нулевият полином, т.е получихме че $h_0 = 0$. Противоречие (доказахме, че $h_0 \ne 0$).

Следователно $h = 0$, с което индукцията (и теоремата) са доказани!

Следствие

Нека $f(x) \in F[x]$ и $\deg f = n$. Нека $K \supset F$ е разширението на $F$, в което попадат корените на $f$ - $\alpha_1, \alpha_2, \cdots, \alpha_n \in K$.
Ако $t(x_1, \cdots, x_n)$ e произволна симетрична функция на $n$ променливи над $F$, то $t(\alpha_1, \alpha_2, \cdots, \alpha_n) \in F$.
Доказателство: Прилагаме основната теорема за $t$ и получаваме, че съществува полином $h(y_1, \cdots, y_n) \in F[x_1, \cdots, x_n]$, за който $h(\sigma_1, \cdots, \sigma_n) = t(x_1, \cdots, x_n)$.
От формулите на Виет получаваме, че:

(17)
\begin{eqnarray} \sigma_1(\alpha_1, \cdots, \alpha_n) &=& - \frac{a_1}{a_0} \\ \sigma_2(\alpha_1, \cdots, \alpha_n) &=& \frac{a_2}{a_0} \\ &\vdots& \\ \sigma_n(\alpha_1, \cdots, \alpha_n) &=& (-1)^n \frac{a_n}{a_0} \end{eqnarray}

Следователно:

(18)
\begin{eqnarray} t(\alpha_1, \cdots, \alpha_n) &=& h(\sigma_1(\alpha_1, \cdots, \alpha_n), \cdots, \sigma_n(\alpha_1,\cdots,\alpha_n)) \\ &=& h(\underbrace{-\frac{a_1}{a_0}}_{\in F}, \underbrace{\frac{a_2}{a_0}}_{\in F}, \cdots, \underbrace{(-1)^n \frac{a_n}{a_0}}_{\in F}) \in F \end{eqnarray}

Т.е получихме, че произволна симетрична функция над $F$, заместена с корените на произволен полином над $F$ дава елемент на полето $F$ (независимо, че корените могат и да не са от полето $F$).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License