הוכחות מתמטיות/שונות/π מספר טרנסצנדנטי/המשפט היסודי של הפולינומים הסימטריים

יהי $\mathbb {F}$ שדה, ויהי $F\in \mathbb {F} [{\vec {X}}{}^{n}]$ פולינום סימטרי.
אזי ניתן להציגו באופן יחיד כפולינום $G({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\in \mathbb {F} [{\vec {X}}{}^{n}]$, כאשר:

• מעלת $G$ אינה עולה על מעלת $F$.
• אם $F$ בעל מקדמים שלמים אזי גם $G$ בעל מקדמים שלמים.

הוכחה

ראשית, נתאר אלגוריתם למציאת הפולינום המבוקש $G$.

נגדיר תנאי התחלה $m=1$ וכן $F_{1}=F$.

1. מצאו את ${\text{L}}(F_{m})=c_{m}\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}$ כאשר $c_{m}\in \mathbb {F} ,c_{m}\neq 0$.
2. הגדירו $G_{m}({\vec {Y}}{}^{n})=c_{m}\,Y_{1}^{a_{1}-a_{2}}Y_{2}^{a_{2}-a_{3}}\!\cdots Y_{n-1}^{a_{n-1}-a_{n}}Y_{n}^{a_{n}}$.
3. הציבו $F_{m+1}({\vec {X}}{}^{n})=F_{m}({\vec {X}}{}^{n})-G_{m}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))$.
4. אם $F_{m+1}\neq 0$, שובו לסעיף 1 והתחילו את התהליך מחדש באינדקס $m+1$.
   אם $F_{m+1}=0$, עברו לסעיף 5.
5. הציבו $G=G_{1}\!+\cdots +G_{m}$.

להוכחת האלגוריתם אנו זקוקים לשתי למות.

למה 1: המונום המוביל ב־$F$ מקיים $a_{1}\geq a_{2}\geq \cdots \geq a_{n}$.

הוכחה: נניח בשלילה כי קיים אינדקס $k$ עבורו $a_{k}<a_{k+1}$. קיימת תמורה כלשהיא $\sigma \in S_{X}$ עבורה

$X_{\sigma (m)}={\begin{cases}X_{m}&:m\neq k,k+1\\X_{k+1}&:m=k\\X_{k}&:m=k+1\end{cases}}$

אך הפולינום $\sigma (F)=F$ מכיל את המונום $c\,X_{1}^{a_{1}}\!\cdots X_{k}^{a_{k+1}}X_{k+1}^{a_{k}}\!\cdots X_{n}^{a_{n}}$, שסדרו גדול מזה של $c\,X_{1}^{a_{1}}\!\cdots X_{k}^{a_{k}}X_{k+1}^{a_{k+1}}\cdots X_{n}^{a_{n}}$.
סתירה.

$\square$

למה 2: המונום המוביל בפיתוחו של הפולינום $G_{m}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))$ הוא $c_{m}\,X_{1}^{a_{1}}\!X_{2}^{a_{2}}\!\cdots X_{n}^{a_{n}}$.

הוכחה: מתקיים כי

${\begin{aligned}{\text{L}}(E_{k})=X_{1}\!\cdots X_{k},&\quad :\!1\leq k\leq n\\[5pt]{\text{L}}(c_{m}\,E_{1}^{b_{1}}E_{2}^{b_{2}}\!\cdots E_{n}^{b_{n}})&=c_{m}\,{\text{L}}(E_{1}^{b_{1}})\,{\text{L}}(E_{2}^{b_{2}})\cdots {\text{L}}(E_{n}^{b_{n}})\\[5pt]&=c_{m}\,{\text{L}}(E_{1})^{b_{1}}{\text{L}}(E_{2})^{b_{2}}\!\cdots {\text{L}}(E_{n})^{b_{n}}\\[5pt]&=c_{m}\,X_{1}^{b_{1}}(X_{1}X_{2})^{b_{2}}\!\cdots (X_{1}X_{2}\cdots X_{n})^{b_{n}}\\[5pt]&=c_{m}(X_{1})^{b_{1}\,+\,\cdots \,+\,b_{n}}(X_{2})^{b_{2}\,+\,\cdots \,+\,b_{n}}\!\cdots (X_{n-1})^{b_{n-1}+\,b_{n}}(X_{n})^{b_{n}}\\[5pt]&=c_{m}\,X_{1}^{a_{1}}X_{2}^{a_{2}}\!\cdots X_{n}^{a_{n}}\end{aligned}}$

השוויון האחרון מתקיים אם ורק אם

${\begin{aligned}a_{k}&=\sum _{i\,=\,k}^{n}b_{i},\quad :\!1\leq k\leq n\\[5pt]b_{k}&={\begin{cases}a_{k}\!-a_{k+1}&:\!1\leq k\leq n-1\\[5pt]a_{k}&:\!k=n\end{cases}}\end{aligned}}$

$\square$

עתה ניגש להוכחת המשפט:

1. יהי $F\neq 0$ פולינום סימטרי במשתנים $X_{1},\ldots ,X_{n}$.
ההוכחה באינדוקציה שלמה על $|{\text{D}}(F)|$ (ראו הגדרה).

אם $|{\text{D}}(F)|=0$ אזי $F$ פולינום קבוע, וקל להראות כי האלגוריתם מתקיים עבורו.

נניח כי האלגוריתם מתקיים לכל הפולינומים הסימטריים $F$ בעלי $0\leq |{\text{D}}(F)|\leq k$, עבור $k\in \mathbb {N}$ כלשהוא.
נראה כי האלגוריתם מתקיים גם עבור פולינום סימטרי $F_{1}$ בעל $|{\text{D}}(F_{1})|=k+1$, כאשר ${\text{L}}(F_{1})=c_{1}\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}$.

על־פי למה 2, מתקיים כי:

${\begin{aligned}G_{1}({\vec {Y}}{}^{n})&=c_{1}\,Y_{1}^{a_{1}-a_{2}}Y_{2}^{a_{2}-a_{3}}\!\cdots Y_{n-1}^{a_{n-1}-a_{n}}Y_{n}^{a_{n}}\\[5pt]F_{2}({\vec {X}}{}^{n})&=F_{1}({\vec {X}}{}^{n})-G_{1}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\end{aligned}}$

הפונקציה $G_{1}$ היא פולינום, שכן $a_{1}\geq a_{2}\geq \cdots \geq a_{n}$.
בנוסף, על־פי תכונות הפולינומים הסימטריים $G_{1}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))$ פולינום סימטרי במשתנים $X_{1},\ldots ,X_{n}$, ולכן גם $F_{2}$ פולינום סימטרי.
הפולינומים $F_{1}({\vec {X}}{}^{n}),G_{1}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))$ מכילים שניהם את ${\text{L}}(F_{1})$, ולכן הוא מתקזז בהפרשם.

אם $F_{2}=0$ אזי $G=G_{1}$.
אם $F_{2}\neq 0$ אזי ${\text{L}}(F_{2})\prec {\text{L}}(F_{1})$, כלומר $|{\text{D}}(F_{2})|<|{\text{D}}(F_{1})|=k+1$.
הנחת האינדוקציה מתקיימת עבור $F_{2}$, ועל כן האלגוריתם מניב פולינום $G^{*}$ עבורו

${\begin{aligned}F_{2}({\vec {X}}{}^{n})&=G^{*}\!({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\\[5pt]F_{1}({\vec {X}}{}^{n})&=G_{1}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))+G^{*}\!({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\end{aligned}}$

2. תכונות המשפט מתקיימות:

• על־פי ההגדרה, מעלת $G_{1}({\vec {Y}}{}^{n})$ היא $a_{1}$ ומעלת $F_{1}$ היא לפחות $a_{1}\!+\cdots +a_{n}$.
• אם $F_{1}$ בעל מקדמים שלמים אזי $c_{1}\neq 0$ הנ"ל מספר שלם. לכן גם $G_{1}$ בעל מקדמים שלמים.

$\blacksquare$

תוצאות חשובות

משפט. יהי $\mathbb {F} \subseteq \mathbb {E}$ שדה, ויהי $F\in \mathbb {F} [z]$ פולינום ממעלה $n$ בעל השורשים $\alpha _{1},\ldots ,\alpha _{n}\in \mathbb {E}$.
יהי $G\in \mathbb {F} [{\vec {X}}{}^{n}]$ פולינום סימטרי. אזי $G({\vec {\alpha }}{}^{n})\in \mathbb {F}$.

הוכחה. על־פי נוסחאות ויאטה מתקיים כי:

${\begin{aligned}F(z)&=a_{0}+a_{1}z+\cdots +a_{n-1}z^{n-1}+a_{n}z^{n}\in \mathbb {F} [z]\\[5pt]E_{k}({\vec {\alpha }}{}^{n})&=(-1)^{k}{\frac {a_{n-k}}{a_{n}}}\in \mathbb {F} ,\quad (1\leq k\leq n)\end{aligned}}$

על־פי המשפט היסודי, $G$ ניתן להצגה כפולינום

${\begin{aligned}G({\vec {X}}{}^{n})&=H({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\in \mathbb {F} [{\vec {X}}{}^{n}]\\[5pt]G({\vec {\alpha }}{}^{n})&=H({\vec {E}}{}^{n}({\vec {\alpha }}{}^{n}))\in \mathbb {F} \end{aligned}}$

$\square$

משפט. יהי $\mathbb {F} \subseteq \mathbb {E}$ שדה, ויהי $F\in \mathbb {F} [z]$ פולינום ממעלה $n$ בעל השורשים $\alpha _{1},\ldots ,\alpha _{n}\in \mathbb {E}$.
יהי $1\leq k\leq n$ כלשהוא, ויהיו $\beta _{1},\ldots ,\beta _{m}$ סכומי כל $k$ מבין השורשים $\alpha _{1},\ldots ,\alpha _{n}$ (כלומר $m={\tbinom {n}{k}}$).
אזי קיים פולינום מתוקן $F_{k}\in \mathbb {F} [z]$ ממעלה $m$ בעל השורשים $\beta _{1},\ldots ,\beta _{m}$.

הוכחה. עלינו להראות כי מתקיים

$F_{k}(z)=(z-\beta _{1})(z-\beta _{2})\cdots (z-\beta _{m})\in \mathbb {F} [z]$

על־פי נוסחאות ויאטה, מקדמי הפולינום כולם פולינומים סימטריים לפי $\beta _{1},\ldots ,\beta _{m}$.

יהי $G\in \mathbb {F} [{\vec {Y}}{}^{m}]$ פולינום סימטרי, ויהיו $Y_{1},\ldots ,Y_{m}$ סכומי כל $k$ מבין המשתנים $X_{1},\ldots ,X_{n}$.
אזי $G$ ניתן להצגה כפולינום

$G({\vec {Y}}{}^{m})=H({\vec {X}}{}^{n})$

קל לראות כי בהפעלת תמורה על $X_{1},\ldots ,X_{n}$ מתקיימת גם תמורה על $Y_{1},\ldots ,Y_{m}$.
לכן $H\in \mathbb {F} [{\vec {X}}{}^{n}]$ פולינום סימטרי, ועל־פי המשפט הקודם מתקיים כי

$G({\vec {\beta }}{}^{m})=H({\vec {\alpha }}{}^{n})\in \mathbb {F}$

$\square$

הפרק הקודם: פולינומים סימטריים אלמנטריים

המשפט היסודי של הפולינומים הסימטריים תרגילים

הפרק הבא: הוכחה