יהי
F
{\displaystyle \mathbb {F} }
F
∈
F
[
X
→
n
]
{\displaystyle F\in \mathbb {F} [{\vec {X}}{}^{n}]}
G
(
E
→
n
(
X
→
n
)
)
∈
F
[
X
→
n
]
{\displaystyle G({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\in \mathbb {F} [{\vec {X}}{}^{n}]}
מעלת
G
{\displaystyle G}
F
{\displaystyle F}
אם
F
{\displaystyle F}
G
{\displaystyle G}
ראשית, נתאר אלגוריתם למציאת הפולינום המבוקש
G
{\displaystyle G}
נגדיר תנאי התחלה
m
=
1
{\displaystyle m=1}
F
1
=
F
{\displaystyle F_{1}=F}
מצאו את
L
(
F
m
)
=
c
m
X
1
a
1
⋯
X
n
a
n
{\displaystyle {\text{L}}(F_{m})=c_{m}\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}}
c
m
∈
F
,
c
m
≠
0
{\displaystyle c_{m}\in \mathbb {F} ,c_{m}\neq 0}
הגדירו
G
m
(
Y
→
n
)
=
c
m
Y
1
a
1
−
a
2
Y
2
a
2
−
a
3
⋯
Y
n
−
1
a
n
−
1
−
a
n
Y
n
a
n
{\displaystyle 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}}}
הציבו
F
m
+
1
(
X
→
n
)
=
F
m
(
X
→
n
)
−
G
m
(
E
→
n
(
X
→
n
)
)
{\displaystyle F_{m+1}({\vec {X}}{}^{n})=F_{m}({\vec {X}}{}^{n})-G_{m}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))}
אם
F
m
+
1
≠
0
{\displaystyle F_{m+1}\neq 0}
m
+
1
{\displaystyle m+1}
F
m
+
1
=
0
{\displaystyle F_{m+1}=0}
הציבו
G
=
G
1
+
⋯
+
G
m
{\displaystyle G=G_{1}\!+\cdots +G_{m}}
למות .
למה 1: המונום המוביל ב־
F
{\displaystyle F}
a
1
≥
a
2
≥
⋯
≥
a
n
{\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}
הוכחה: נניח בשלילה כי קיים אינדקס
k
{\displaystyle k}
a
k
<
a
k
+
1
{\displaystyle a_{k}<a_{k+1}}
σ
∈
S
X
{\displaystyle \sigma \in S_{X}}
X
σ
(
m
)
=
{
X
m
:
m
≠
k
,
k
+
1
X
k
+
1
:
m
=
k
X
k
:
m
=
k
+
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}}}
אך הפולינום
σ
(
F
)
=
F
{\displaystyle \sigma (F)=F}
c
X
1
a
1
⋯
X
k
a
k
+
1
X
k
+
1
a
k
⋯
X
n
a
n
{\displaystyle 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
⋯
X
k
a
k
X
k
+
1
a
k
+
1
⋯
X
n
a
n
{\displaystyle c\,X_{1}^{a_{1}}\!\cdots X_{k}^{a_{k}}X_{k+1}^{a_{k+1}}\cdots X_{n}^{a_{n}}}
סתירה.
◻
{\displaystyle \square }
למה 2: המונום המוביל בפיתוחו של הפולינום
G
m
(
E
→
n
(
X
→
n
)
)
{\displaystyle G_{m}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))}
c
m
X
1
a
1
X
2
a
2
⋯
X
n
a
n
{\displaystyle c_{m}\,X_{1}^{a_{1}}\!X_{2}^{a_{2}}\!\cdots X_{n}^{a_{n}}}
הוכחה: מתקיים כי
L
(
E
k
)
=
X
1
⋯
X
k
,
:
1
≤
k
≤
n
L
(
c
m
E
1
b
1
E
2
b
2
⋯
E
n
b
n
)
=
c
m
L
(
E
1
b
1
)
L
(
E
2
b
2
)
⋯
L
(
E
n
b
n
)
=
c
m
L
(
E
1
)
b
1
L
(
E
2
)
b
2
⋯
L
(
E
n
)
b
n
=
c
m
X
1
b
1
(
X
1
X
2
)
b
2
⋯
(
X
1
X
2
⋯
X
n
)
b
n
=
c
m
(
X
1
)
b
1
+
⋯
+
b
n
(
X
2
)
b
2
+
⋯
+
b
n
⋯
(
X
n
−
1
)
b
n
−
1
+
b
n
(
X
n
)
b
n
=
c
m
X
1
a
1
X
2
a
2
⋯
X
n
a
n
{\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}}}
השוויון האחרון מתקיים אם ורק אם
a
k
=
∑
i
=
k
n
b
i
,
:
1
≤
k
≤
n
b
k
=
{
a
k
−
a
k
+
1
:
1
≤
k
≤
n
−
1
a
k
:
k
=
n
{\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}}}
◻
{\displaystyle \square }
עתה ניגש להוכחת המשפט:
1. יהי
F
≠
0
{\displaystyle F\neq 0}
X
1
,
…
,
X
n
{\displaystyle X_{1},\ldots ,X_{n}}
אינדוקציה שלמה על
|
D
(
F
)
|
{\displaystyle |{\text{D}}(F)|}
הגדרה ).
אם
|
D
(
F
)
|
=
0
{\displaystyle |{\text{D}}(F)|=0}
F
{\displaystyle F}
נניח כי האלגוריתם מתקיים לכל הפולינומים הסימטריים
F
{\displaystyle F}
0
≤
|
D
(
F
)
|
≤
k
{\displaystyle 0\leq |{\text{D}}(F)|\leq k}
k
∈
N
{\displaystyle k\in \mathbb {N} }
F
1
{\displaystyle F_{1}}
|
D
(
F
1
)
|
=
k
+
1
{\displaystyle |{\text{D}}(F_{1})|=k+1}
L
(
F
1
)
=
c
1
X
1
a
1
⋯
X
n
a
n
{\displaystyle {\text{L}}(F_{1})=c_{1}\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}}
על־פי למה 2, מתקיים כי:
G
1
(
Y
→
n
)
=
c
1
Y
1
a
1
−
a
2
Y
2
a
2
−
a
3
⋯
Y
n
−
1
a
n
−
1
−
a
n
Y
n
a
n
F
2
(
X
→
n
)
=
F
1
(
X
→
n
)
−
G
1
(
E
→
n
(
X
→
n
)
)
{\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}}}
הפונקציה
G
1
{\displaystyle G_{1}}
a
1
≥
a
2
≥
⋯
≥
a
n
{\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}
תכונות הפולינומים הסימטריים
G
1
(
E
→
n
(
X
→
n
)
)
{\displaystyle G_{1}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))}
X
1
,
…
,
X
n
{\displaystyle X_{1},\ldots ,X_{n}}
F
2
{\displaystyle F_{2}}
F
1
(
X
→
n
)
,
G
1
(
E
→
n
(
X
→
n
)
)
{\displaystyle F_{1}({\vec {X}}{}^{n}),G_{1}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))}
L
(
F
1
)
{\displaystyle {\text{L}}(F_{1})}
אם
F
2
=
0
{\displaystyle F_{2}=0}
G
=
G
1
{\displaystyle G=G_{1}}
F
2
≠
0
{\displaystyle F_{2}\neq 0}
L
(
F
2
)
≺
L
(
F
1
)
{\displaystyle {\text{L}}(F_{2})\prec {\text{L}}(F_{1})}
|
D
(
F
2
)
|
<
|
D
(
F
1
)
|
=
k
+
1
{\displaystyle |{\text{D}}(F_{2})|<|{\text{D}}(F_{1})|=k+1}
F
2
{\displaystyle F_{2}}
G
∗
{\displaystyle G^{*}}
F
2
(
X
→
n
)
=
G
∗
(
E
→
n
(
X
→
n
)
)
F
1
(
X
→
n
)
=
G
1
(
E
→
n
(
X
→
n
)
)
+
G
∗
(
E
→
n
(
X
→
n
)
)
{\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}}}
2. תכונות המשפט מתקיימות:
על־פי ההגדרה, מעלת
G
1
(
Y
→
n
)
{\displaystyle G_{1}({\vec {Y}}{}^{n})}
a
1
{\displaystyle a_{1}}
F
1
{\displaystyle F_{1}}
a
1
+
⋯
+
a
n
{\displaystyle a_{1}\!+\cdots +a_{n}}
אם
F
1
{\displaystyle F_{1}}
c
1
≠
0
{\displaystyle c_{1}\neq 0}
G
1
{\displaystyle G_{1}}
◼
{\displaystyle \blacksquare }
משפט. יהי
F
⊆
E
{\displaystyle \mathbb {F} \subseteq \mathbb {E} }
F
∈
F
[
z
]
{\displaystyle F\in \mathbb {F} [z]}
n
{\displaystyle n}
α
1
,
…
,
α
n
∈
E
{\displaystyle \alpha _{1},\ldots ,\alpha _{n}\in \mathbb {E} }
G
∈
F
[
X
→
n
]
{\displaystyle G\in \mathbb {F} [{\vec {X}}{}^{n}]}
G
(
α
→
n
)
∈
F
{\displaystyle G({\vec {\alpha }}{}^{n})\in \mathbb {F} }
הוכחה. על־פי נוסחאות ויאטה מתקיים כי:
F
(
z
)
=
a
0
+
a
1
z
+
⋯
+
a
n
−
1
z
n
−
1
+
a
n
z
n
∈
F
[
z
]
E
k
(
α
→
n
)
=
(
−
1
)
k
a
n
−
k
a
n
∈
F
,
(
1
≤
k
≤
n
)
{\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}}}
על־פי המשפט היסודי,
G
{\displaystyle G}
G
(
X
→
n
)
=
H
(
E
→
n
(
X
→
n
)
)
∈
F
[
X
→
n
]
G
(
α
→
n
)
=
H
(
E
→
n
(
α
→
n
)
)
∈
F
{\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}}}
◻
{\displaystyle \square }
משפט. יהי
F
⊆
E
{\displaystyle \mathbb {F} \subseteq \mathbb {E} }
F
∈
F
[
z
]
{\displaystyle F\in \mathbb {F} [z]}
n
{\displaystyle n}
α
1
,
…
,
α
n
∈
E
{\displaystyle \alpha _{1},\ldots ,\alpha _{n}\in \mathbb {E} }
1
≤
k
≤
n
{\displaystyle 1\leq k\leq n}
β
1
,
…
,
β
m
{\displaystyle \beta _{1},\ldots ,\beta _{m}}
k
{\displaystyle k}
α
1
,
…
,
α
n
{\displaystyle \alpha _{1},\ldots ,\alpha _{n}}
m
=
(
n
k
)
{\displaystyle m={\tbinom {n}{k}}}
פולינום מתוקן
F
k
∈
F
[
z
]
{\displaystyle F_{k}\in \mathbb {F} [z]}
m
{\displaystyle m}
β
1
,
…
,
β
m
{\displaystyle \beta _{1},\ldots ,\beta _{m}}
הוכחה. עלינו להראות כי מתקיים
F
k
(
z
)
=
(
z
−
β
1
)
(
z
−
β
2
)
⋯
(
z
−
β
m
)
∈
F
[
z
]
{\displaystyle F_{k}(z)=(z-\beta _{1})(z-\beta _{2})\cdots (z-\beta _{m})\in \mathbb {F} [z]}
על־פי נוסחאות ויאטה, מקדמי הפולינום כולם פולינומים סימטריים לפי
β
1
,
…
,
β
m
{\displaystyle \beta _{1},\ldots ,\beta _{m}}
יהי
G
∈
F
[
Y
→
m
]
{\displaystyle G\in \mathbb {F} [{\vec {Y}}{}^{m}]}
Y
1
,
…
,
Y
m
{\displaystyle Y_{1},\ldots ,Y_{m}}
k
{\displaystyle k}
X
1
,
…
,
X
n
{\displaystyle X_{1},\ldots ,X_{n}}
G
{\displaystyle G}
G
(
Y
→
m
)
=
H
(
X
→
n
)
{\displaystyle G({\vec {Y}}{}^{m})=H({\vec {X}}{}^{n})}
קל לראות כי בהפעלת תמורה על
X
1
,
…
,
X
n
{\displaystyle X_{1},\ldots ,X_{n}}
Y
1
,
…
,
Y
m
{\displaystyle Y_{1},\ldots ,Y_{m}}
H
∈
F
[
X
→
n
]
{\displaystyle H\in \mathbb {F} [{\vec {X}}{}^{n}]}
G
(
β
→
m
)
=
H
(
α
→
n
)
∈
F
{\displaystyle G({\vec {\beta }}{}^{m})=H({\vec {\alpha }}{}^{n})\in \mathbb {F} }
◻
{\displaystyle \square }
![{\displaystyle F\in \mathbb {F} [{\vec {X}}{}^{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3cdb9c0c218275f5806755dc5747bcb62f40093d)
![{\displaystyle G({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\in \mathbb {F} [{\vec {X}}{}^{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab3a983844d8f075e8d168caa7a35ccbe2cf0c1b)
![{\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)
![{\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)
![{\displaystyle F\in \mathbb {F} [z]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48ce21a913b6f2462f3216e3816a04bf705074fb)
![{\displaystyle G\in \mathbb {F} [{\vec {X}}{}^{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ce9a5854f495f3d783d13e80bfc2e38db49d3f0)
![{\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}\in \mathbb {F} [z]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fcca686f35269c0672fc56f08e70c325fe182c4)
![{\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\in \mathbb {F} [{\vec {Y}}{}^{m}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11ce3fad45b8483a113634d281c8772ad7085126)
![{\displaystyle H\in \mathbb {F} [{\vec {X}}{}^{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30db03bc6c4b9b150e8a8a04767aa09127d27371)
