F
{\displaystyle \mathbb {F} }
F
∈
F
[
X
→
n
]
{\displaystyle F\in \mathbb {F} [{\vec {X}}{}^{n}]}
F
{\displaystyle F}
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}
If
F
{\displaystyle F}
G
{\displaystyle G}
First, we shall describe an algorithm for finding the desired polynomial
G
{\displaystyle G}
Let us define initial conditions
m
=
1
{\displaystyle m=1}
F
1
=
F
{\displaystyle F_{1}=F}
Find
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}
Define
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}}}
Write
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}))}
If
F
m
+
1
≠
0
{\displaystyle F_{m+1}\neq 0}
m
+
1
{\displaystyle m+1}
F
m
+
1
=
0
{\displaystyle F_{m+1}=0}
Write
G
=
G
1
+
⋯
+
G
m
{\displaystyle G=G_{1}\!+\cdots +G_{m}}
lemmas .
Lemma 1: The leading monomial in
F
{\displaystyle F}
a
1
≥
a
2
≥
⋯
≥
a
n
{\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}
Proof: Let us assume there exists an index
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}}}
But the polynomial
σ
(
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}}}
A contradiction.
◻
{\displaystyle \square }
Lemma 2: The leading monomial in the expansion of
G
m
(
E
→
n
(
X
→
n
)
)
{\displaystyle G_{m}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))}
c
m
X
1
a
1
⋯
X
n
a
n
{\displaystyle c_{m}\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}}
Proof: We have
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}}}
The last equality holds if and only if
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 }
We shall now prove the theorem:
1. Let
F
≠
0
{\displaystyle F\neq 0}
X
1
,
…
,
X
n
{\displaystyle X_{1},\ldots ,X_{n}}
strong induction on
|
D
(
F
)
|
{\displaystyle |{\text{D}}(F)|}
definition ).
If
|
D
(
F
)
|
=
0
{\displaystyle |{\text{D}}(F)|=0}
F
{\displaystyle F}
Let us assume the algorithm holds for all symmetric polynomials
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}}}
By lemma 2, we get:
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}}}
The function
G
1
{\displaystyle G_{1}}
a
1
≥
a
2
≥
⋯
≥
a
n
{\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}
properties of symmetric polynomials
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})}
If
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. The properties of the theorem hold:
By definition, the degree of
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}}
If
F
1
{\displaystyle F_{1}}
c
1
≠
0
{\displaystyle c_{1}\neq 0}
G
1
{\displaystyle G_{1}}
◼
{\displaystyle \blacksquare }
Theorem. Let
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} }
Proof. By Vieta's formulae , we get
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}}}
By the fundamental theorem above,
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 }
Theorem. Let
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}}}
monic polynomial
F
k
∈
F
[
z
]
{\displaystyle F_{k}\in \mathbb {F} [z]}
m
{\displaystyle m}
β
1
,
…
,
β
m
{\displaystyle \beta _{1},\ldots ,\beta _{m}}
Proof. We will show that
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]}
By Vieta's formulae, its coefficients are all symmetric polynomials in
β
1
,
…
,
β
m
{\displaystyle \beta _{1},\ldots ,\beta _{m}}
Let
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})}
It is easy to see that by applying a permutation on
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)
