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

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

===הוכחה===
ראשית, נתאר [[w:אלגוריתם|אלגוריתם]] למציאת הפולינום המבוקש <math>G</math>.

נגדיר תנאי התחלה <math>m=1</math> וכן <math>F_1=F</math>.
#מצאו את <math>\text{L}(F_m)=c_m\,X_1^{a_1}\!\cdots X_n^{a_n}</math> כאשר <math>c_m\in\mathbb F,c_m\ne0</math>.
#הגדירו <math>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}</math>.
#הציבו <math>F_{m+1}(\vec{X}{}^n)=F_m(\vec{X}{}^n)-G_m(\vec{E}{}^n(\vec{X}{}^n))</math>.
#אם <math>F_{m+1}\ne0</math>, שובו לסעיף 1 והתחילו את התהליך מחדש באינדקס <math>m+1</math>.{{ש}}אם <math>F_{m+1}=0</math>, עברו לסעיף 5.
#הציבו <math>G=G_1\!+\cdots+G_m</math>.


להוכחת האלגוריתם אנו זקוקים לשתי [[w:למה (מתמטיקה)|למות]].

'''למה 1:''' המונום המוביל ב־<math>F</math> מקיים <math>a_1\ge a_2\ge\cdots\ge a_n</math>.

'''הוכחה:''' [[w:הוכחה בדרך השלילה|נניח בשלילה]] כי קיים אינדקס <math>k</math> עבורו <math>a_k<a_{k+1}</math>. קיימת תמורה כלשהיא <math>\sigma\in S_X</math> עבורה
:<math>X_{\sigma(m)}=\begin{cases}X_m&:m\ne k,k+1\\X_{k+1}&:m=k\\X_k&:m=k+1\end{cases}</math>
אך הפולינום <math>\sigma(F)=F</math> מכיל את המונום <math>c\,X_1^{a_1}\!\cdots X_k^{a_{k+1}}X_{k+1}^{a_k}\!\cdots X_n^{a_n}</math>, שסדרו גדול מזה של <math>c\,X_1^{a_1}\!\cdots X_k^{a_k}X_{k+1}^{a_{k+1}}\cdots X_n^{a_n}</math>.{{ש}}
'''סתירה.'''

<math>\square</math>

'''למה 2:''' המונום המוביל בפיתוחו של הפולינום <math>G_m(\vec{E}{}^n(\vec{X}{}^n))</math> הוא <math>c_m\,X_1^{a_1}\!X_2^{a_2}\!\cdots X_n^{a_n}</math>.

'''הוכחה:''' מתקיים כי
:<math>\begin{align}\text{L}(E_k)=X_1\!\cdots X_k,&\quad:\!1\le k\le 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_1X_2)^{b_2}\!\cdots(X_1X_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{align}</math>
השוויון האחרון מתקיים [[w:אם ורק אם|אם ורק אם]]
:<math>\begin{align}a_k&=\sum_{i\,=\,k}^nb_i,\quad:\!1\le k\le n\\[5pt]b_k&=\begin{cases}a_k\!-a_{k+1}&:\!1\le k\le n-1\\[5pt]a_k&:\!k=n\end{cases}\end{align}</math>

<math>\square</math>

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

1. יהי <math>F\ne0</math> פולינום סימטרי במשתנים <math>X_1,\ldots,X_n</math>.{{ש}}
ההוכחה ב[[w:אינדוקציה מתמטית|אינדוקציה שלמה]] על <math>|\text{D}(F)|</math> (ראו [[הוכחות מתמטיות/שונות/π מספר טרנסצנדנטי/סידור מונומי#הגדרה 5|הגדרה]]).

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

נניח כי האלגוריתם מתקיים לכל הפולינומים הסימטריים <math>F</math> בעלי <math>0\le|\text{D}(F)|\le k</math>, עבור <math>k\in\N</math> כלשהוא.{{ש}}
נראה כי האלגוריתם מתקיים גם עבור פולינום סימטרי <math>F_1</math> בעל <math>|\text{D}(F_1)|=k+1</math>, כאשר <math>\text{L}(F_1)=c_1\,X_1^{a_1}\!\cdots X_n^{a_n}</math>.

על־פי למה 2, מתקיים כי:
:<math>\begin{align}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{align}</math>
הפונקציה <math>G_1</math> היא פולינום, שכן <math>a_1\ge a_2\ge\cdots\ge a_n</math>.{{ש}}
בנוסף, על־פי [[הוכחות מתמטיות/שונות/π מספר טרנסצנדנטי/פולינומים סימטריים#תכונות|תכונות הפולינומים הסימטריים]] <math>G_1(\vec{E}{}^n(\vec{X}{}^n))</math> פולינום סימטרי במשתנים <math>X_1,\ldots,X_n</math>, ולכן גם <math>F_2</math> פולינום סימטרי.{{ש}}
הפולינומים <math>F_1(\vec{X}{}^n),G_1(\vec{E}{}^n(\vec{X}{}^n))</math> מכילים שניהם את <math>\text{L}(F_1)</math>, ולכן הוא מתקזז בהפרשם.{{ש}}

אם <math>F_2=0</math> אזי <math>G=G_1</math>.{{ש}}
אם <math>F_2\ne0</math> אזי <math>\text{L}(F_2)\prec\text{L}(F_1)</math>, כלומר <math>|\text{D}(F_2)|<|\text{D}(F_1)|=k+1</math>.{{ש}}
הנחת האינדוקציה מתקיימת עבור <math>F_2</math>, ועל כן האלגוריתם מניב פולינום <math>G^*</math> עבורו
:<math>\begin{align}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{align}</math>

2. תכונות המשפט מתקיימות:
*על־פי ההגדרה, מעלת <math>G_1(\vec{Y}{}^n)</math> היא <math>a_1</math> ומעלת <math>F_1</math> היא לפחות <math>a_1\!+\cdots+a_n</math>.
*אם <math>F_1</math> בעל מקדמים שלמים אזי <math>c_1\ne0</math> הנ"ל מספר שלם. לכן גם <math>G_1</math> בעל מקדמים שלמים.
<math>\blacksquare</math>

==תוצאות חשובות==
'''משפט.''' יהי <math>\mathbb{F}\sube\mathbb{E}</math> שדה, ויהי <math>P\in\mathbb{F}[z]</math> פולינום ממעלה <math>n</math> בעל השורשים <math>\alpha_1,\ldots,\alpha_n\in\mathbb{E}</math> (עם ריבוי).{{ש}}
יהי <math>G\in\mathbb{F}[\vec{X}{}^n]</math> פולינום סימטרי. אזי <math>G(\vec{\alpha}{}^n)\in\mathbb{F}</math>.

'''הוכחה.''' על־פי [[w:נוסחאות ויאטה|נוסחאות ויאטה]] מתקיים כי:
:<math>\begin{align}P(z)&=\sum_{k\,=\,0}^na_kz^k\in\mathbb{F}[z]\\[5pt]E_k(\vec{\alpha}{}^n)&=(-1)^k\frac{a_{n-k}}{a_n}\in\mathbb{F},\quad(1\le k\le n)\end{align}</math>
על־פי המשפט היסודי, <math>G</math> ניתן להצגה כפולינום
:<math>\begin{align}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{align}</math>

<math>\square</math>

'''משפט.''' יהי <math>\mathbb{F}\sube\mathbb{E}</math> שדה, ויהי <math>P\in\mathbb{F}[z]</math> פולינום ממעלה <math>n</math> בעל השורשים <math>\alpha_1,\ldots,\alpha_n\in\mathbb{E}</math> (עם ריבוי).{{ש}}
אזי לכל <math>1\le k\le n</math> קיים [[w:פולינום מתוקן|פולינום מתוקן]] <math>P_k\in\mathbb{F}[z]</math> אשר שורשיו הם סכומי/מכפלות כל <math>k</math> מבין שורשי <math>P</math>.

'''הוכחה.''' יהיו <math>\beta_1,\ldots,\beta_m</math> סכומי/מכפלות כל <math>k</math> מבין שורשי <math>P</math> (לאמר <math>m=\tbinom{n}{k}</math>).{{ש}}
עלינו להראות כי מתקיים
:<math>P_k(z)=\prod_{i\,=\,1}^m(z-\beta_i)\in\mathbb{F}[z]</math>
על־פי נוסחאות ויאטה, מקדמי הפולינום כולם פולינומים סימטריים לפי <math>\beta_1,\ldots,\beta_m</math>.

יהי <math>G\in\mathbb{F}[\vec{Y}{}^m]</math> פולינום סימטרי, ויהיו <math>Y_1,\ldots,Y_m</math> סכומי/מכפלות כל <math>k</math> מבין המשתנים  <math>X_1,\ldots,X_n</math>.{{ש}}
אזי <math>G</math> ניתן להצגה כפולינום
:<math>G(\vec{Y}{}^m)=H(\vec{X}{}^n)</math>
קל לראות כי בהפעלת תמורה על <math>X_1,\ldots,X_n</math> מתקיימת גם תמורה על <math>Y_1,\ldots,Y_m</math>.{{ש}}
לכן <math>H\in\mathbb{F}[\vec{X}{}^n]</math> פולינום סימטרי, ועל־פי המשפט הקודם מתקיים כי
:<math>G(\vec{\beta}{}^m)=H(\vec{\alpha}{}^n)\in\mathbb{F}</math>
<math>\square</math>

{{תוכן|
|הפרק הקודם=[[../פולינומים סימטריים אלמנטריים/]]
|הפרק הנוכחי=המשפט היסודי של הפולינומים הסימטריים 
|הפרק הבא=[[../הוכחה/]]
}}

[[קטגוריה:הוכחות מתמטיות]]