יהי
שדה, ויהי
פולינום סימטרי.
אזי ניתן להציגו באופן יחיד כפולינום
, כאשר:
- מעלת
אינה עולה על מעלת
.
- אם
בעל מקדמים שלמים אזי גם
בעל מקדמים שלמים.
ראשית, נתאר אלגוריתם למציאת הפולינום המבוקש
.
נגדיר תנאי התחלה
וכן
.
- מצאו את
כאשר
.
- הגדירו
.
- הציבו
.
- אם
, שובו לסעיף 1 והתחילו את התהליך מחדש באינדקס
.
אם
, עברו לסעיף 5.
- הציבו
.
להוכחת האלגוריתם אנו זקוקים לשתי למות.
למה 1: המונום המוביל ב־
מקיים
.
הוכחה: נניח בשלילה כי קיים אינדקס
עבורו
. קיימת תמורה כלשהיא
עבורה
![{\displaystyle X_{\sigma (m)}={\begin{cases}X_{m}&:m\neq k,k+1\\X_{k+1}&:m=k\\X_{k}&:m=k+1\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce6d8ab9c826ef312f00617e270a941c67a3d176)
אך הפולינום
מכיל את המונום
, שסדרו גדול מזה של
.
סתירה.
למה 2: המונום המוביל בפיתוחו של הפולינום
הוא
.
הוכחה: מתקיים כי
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce2b66fd0cf8add3eb8282aba09af2011b1c3f66)
השוויון האחרון מתקיים אם ורק אם
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b87c36c38cf642c72c3559ca2a45a85a1d97ebb)
עתה ניגש להוכחת המשפט:
1. יהי
פולינום סימטרי במשתנים
.
ההוכחה באינדוקציה שלמה על
(ראו הגדרה).
אם
אזי
פולינום קבוע, וקל להראות כי האלגוריתם מתקיים עבורו.
נניח כי האלגוריתם מתקיים לכל הפולינומים הסימטריים
בעלי
, עבור
כלשהוא.
נראה כי האלגוריתם מתקיים גם עבור פולינום סימטרי
בעל
, כאשר
.
על־פי למה 2, מתקיים כי:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/787bcfcde4331e9369369d99996455b156e2968f)
הפונקציה
היא פולינום, שכן
.
בנוסף, על־פי תכונות הפולינומים הסימטריים
פולינום סימטרי במשתנים
, ולכן גם
פולינום סימטרי.
הפולינומים
מכילים שניהם את
, ולכן הוא מתקזז בהפרשם.
אם
אזי
.
אם
אזי
, כלומר
.
הנחת האינדוקציה מתקיימת עבור
, ועל כן האלגוריתם מניב פולינום
עבורו
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/896b6186a10dc077cb10de29bcb3960ee30b06a6)
2. תכונות המשפט מתקיימות:
- על־פי ההגדרה, מעלת
היא
ומעלת
היא לפחות
.
- אם
בעל מקדמים שלמים אזי
הנ"ל מספר שלם. לכן גם
בעל מקדמים שלמים.
משפט. יהי
שדה, ויהי
פולינום ממעלה
בעל השורשים
.
יהי
פולינום סימטרי. אזי
.
הוכחה. על־פי נוסחאות ויאטה מתקיים כי:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbdb68078e53453e76acf3bfac21f987203a4224)
על־פי המשפט היסודי,
ניתן להצגה כפולינום
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bda1da23c3bf6cff1fa21fa77cc05109dba6c0a2)
משפט. יהי
שדה, ויהי
פולינום ממעלה
בעל השורשים
.
יהי
כלשהוא, ויהיו
סכומי כל
מבין השורשים
(כלומר
).
אזי קיים פולינום מתוקן
ממעלה
בעל השורשים
.
הוכחה. עלינו להראות כי מתקיים
![{\displaystyle F_{k}(z)=(z-\beta _{1})(z-\beta _{2})\cdots (z-\beta _{m})\in \mathbb {F} [z]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d534130372ee6bf97d58da6c1281ed7d783e03db)
על־פי נוסחאות ויאטה, מקדמי הפולינום כולם פולינומים סימטריים לפי
.
יהי
פולינום סימטרי, ויהיו
סכומי כל
מבין המשתנים
.
אזי
ניתן להצגה כפולינום
![{\displaystyle G({\vec {Y}}{}^{m})=H({\vec {X}}{}^{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee1d14a6a7a3f923005f36475b8d97721c5c4e1f)
קל לראות כי בהפעלת תמורה על
מתקיימת גם תמורה על
.
לכן
פולינום סימטרי, ועל־פי המשפט הקודם מתקיים כי
![{\displaystyle G({\vec {\beta }}{}^{m})=H({\vec {\alpha }}{}^{n})\in \mathbb {F} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/7415d60f50473067a72f91c55fe70c69f935d0e9)