Let
(
A
1
,
…
,
A
n
)
{\displaystyle (A_{1},\ldots ,A_{n})}
be an N-tuple . Let us define:
A
→
n
=
(
A
1
,
…
,
A
n
)
{\displaystyle {\vec {A}}{}^{n}=(A_{1},\ldots ,A_{n})}
For functions
F
→
m
,
G
→
n
{\displaystyle {\vec {F}}{}^{m},{\vec {G}}{}^{n}}
let us define:
F
→
m
(
G
→
n
)
=
(
F
1
(
G
1
,
…
,
G
n
)
,
…
,
F
m
(
G
1
,
…
,
G
n
)
)
{\displaystyle {\vec {F}}{}^{m}({\vec {G}}{}^{n})={\bigl (}F_{1}(G_{1},\ldots ,G_{n}),\ldots ,F_{m}(G_{1},\ldots ,G_{n}){\bigr )}}
This abbreviated notation will be of great use to us in the following pages and in the proof.
Let
F
{\displaystyle \mathbb {F} }
be a field. Then
F
[
X
→
n
]
{\displaystyle \mathbb {F} [{\vec {X}}{}^{n}]}
is the polynomial space in variables
X
1
,
…
,
X
n
{\displaystyle X_{1},\ldots ,X_{n}}
with coefficients in
F
{\displaystyle \mathbb {F} }
.
A monomial is a polynomial of the form
c
X
1
a
1
⋯
X
n
a
n
{\displaystyle c\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}}
, such that
c
∈
F
{\displaystyle c\in \mathbb {F} }
and
a
1
,
…
,
a
n
∈
N
{\displaystyle a_{1},\ldots ,a_{n}\in \mathbb {N} }
.
Let
X
a
,
X
b
{\displaystyle X^{a},X^{b}}
be monomials.
We say that
X
a
{\displaystyle X^{a}}
is of lower order than
X
b
{\displaystyle X^{b}}
(and denote it by
X
a
≺
X
b
{\displaystyle X^{a}\!\prec X^{b}}
) if there exists an index
1
≤
k
≤
n
{\displaystyle 1\leq k\leq n}
such that
{
a
i
=
b
i
:
1
≤
i
≤
k
−
1
a
i
<
b
i
:
i
=
k
{\displaystyle {\begin{cases}a_{i}=b_{i}&:\!1\leq i\leq k-1\\[3pt]a_{i}<b_{i}&:i=k\end{cases}}}
In other words, the vectors
(
a
1
,
…
,
a
n
)
,
(
b
1
,
…
,
b
n
)
{\displaystyle (a_{1},\ldots ,a_{n}),(b_{1},\ldots ,b_{n})}
have a lexicographic ordering .
In a polynomial
F
{\displaystyle F}
, the monomial of maximal order is called the leading monomial , and is denoted by
L
(
F
)
{\displaystyle {\text{L}}(F)}
.
x
1
7
x
2
3
x
3
10
≺
x
1
7
x
2
31
x
3
⟺
(
7
,
3
,
10
)
≺
(
7
,
31
,
1
)
{\displaystyle x_{1}^{7}x_{2}^{3}x_{3}^{10}\!\prec x_{1}^{7}x_{2}^{31}x_{3}\iff (7,3,10)\prec (7,31,1)}
Let
F
,
G
∈
F
[
X
→
n
]
{\displaystyle F,G\in \mathbb {F} [{\vec {X}}{}^{n}]}
be polynomials. Then
L
(
F
⋅
G
)
=
L
(
F
)
⋅
L
(
G
)
{\displaystyle {\text{L}}(F\cdot G)={\text{L}}(F)\cdot {\text{L}}(G)}
.
Let
X
a
,
X
b
,
X
f
,
X
g
{\displaystyle X^{a},X^{b},X^{f},X^{g}}
be monomials, with
X
f
=
L
(
F
)
,
X
g
=
L
(
G
)
{\displaystyle X^{f}={\text{L}}(F),\,X^{g}={\text{L}}(G)}
.
1. Let us assume that
X
a
≺
X
f
{\displaystyle X^{a}\!\prec X^{f}}
. We will show that
X
a
+
c
≺
X
f
+
c
{\displaystyle X^{a+c}\!\prec X^{f+c}}
for all
X
c
{\displaystyle X^{c}}
.
By definition, there exists an index
1
≤
k
≤
n
{\displaystyle 1\leq k\leq n}
such that
{
a
i
(
+
c
i
)
=
f
i
(
+
c
i
)
:
1
≤
i
≤
k
−
1
a
i
(
+
c
i
)
<
f
i
(
+
c
i
)
:
i
=
k
{\displaystyle {\begin{cases}a_{i}(+\,c_{i})=f_{i}(+\,c_{i})&:\!1\leq i\leq k-1\\[3pt]a_{i}(+\,c_{i})<f_{i}(+\,c_{i})&:i=k\end{cases}}}
2. Let us assume also that
X
b
≺
X
g
{\displaystyle X^{b}\!\prec X^{g}}
. We will show that
X
a
+
b
≺
X
f
+
g
{\displaystyle X^{a+b}\!\prec X^{f+g}}
.
By definition, there exist indexes
k
1
,
k
2
∈
{
1
,
…
,
n
}
{\displaystyle k_{1},k_{2}\in \{1,\ldots ,n\}}
such that respectively
{
a
i
=
f
i
:
1
≤
i
≤
k
1
−
1
a
i
<
f
i
:
i
=
k
1
,
{
b
i
=
g
i
:
1
≤
i
≤
k
2
−
1
b
i
<
g
i
:
i
=
k
2
{
1
≤
k
1
≤
k
2
≤
n
:
(
a
k
1
<
f
k
1
)
∧
(
b
k
1
≤
g
k
1
)
⟹
a
k
1
+
b
k
1
<
f
k
1
+
g
k
1
1
≤
k
2
<
k
1
≤
n
:
(
a
k
2
=
f
k
2
)
∧
(
b
k
2
<
g
k
2
)
⟹
a
k
2
+
b
k
2
<
f
k
2
+
g
k
2
}
⟹
X
a
+
b
≺
X
f
+
g
{\displaystyle {\begin{aligned}&{\begin{cases}a_{i}=f_{i}&:\!1\leq i\leq k_{1}-1\\[3pt]a_{i}<f_{i}&:i=k_{1}\end{cases}},\quad {\begin{cases}b_{i}=g_{i}&:\!1\leq i\leq k_{2}-1\\[3pt]b_{i}<g_{i}&:i=k_{2}\end{cases}}\\[8pt]&{\begin{cases}1\leq k_{1}\leq k_{2}\leq n\!:&(a_{k_{1}}\!<f_{k_{1}}\!)\land (b_{k_{1}}\!\leq g_{k_{1}}\!)\,\implies \,a_{k_{1}}\!+b_{k_{1}}\!<f_{k_{1}}\!+g_{k_{1}}\\[5pt]1\leq k_{2}<k_{1}\leq n\!:&(a_{k_{2}}\!=f_{k_{2}}\!)\land (b_{k_{2}}\!<g_{k_{2}}\!)\,\implies \,a_{k_{2}}\!+b_{k_{2}}\!<f_{k_{2}}\!+g_{k_{2}}\end{cases}}\!{\Bigg \}}\,\implies \,X^{a+b}\!\prec X^{f+g}\end{aligned}}}
hence:
L
(
F
⋅
G
)
=
X
f
+
g
=
X
f
⋅
X
g
=
L
(
F
)
⋅
L
(
G
)
{\displaystyle {\text{L}}(F\cdot G)=X^{f+g}=X^{f}\cdot X^{g}={\text{L}}(F)\cdot {\text{L}}(G)}
◻
{\displaystyle \square }
Let
F
∈
F
[
X
→
n
]
{\displaystyle F\in \mathbb {F} [{\vec {X}}{}^{n}]}
be a polynomial. Let us define:
D
(
F
)
=
{
X
a
∈
F
[
X
→
n
]
:
deg
(
X
a
)
≤
deg
(
L
(
F
)
)
,
X
a
≺
L
(
F
)
}
{\displaystyle {\text{D}}(F)={\Big \{}X^{a}\!\in \mathbb {F} [{\vec {X}}{}^{n}]:\deg(X^{a})\leq \deg({\text{L}}(F)),X^{a}\!\prec {\text{L}}(F){\Big \}}}
Meaning, the set of all monic monomials of degree
≤
deg
(
L
(
F
)
)
{\displaystyle \leq \deg({\text{L}}(F))}
which are of lower order than
L
(
F
)
{\displaystyle {\text{L}}(F)}
.
F
(
x
1
,
x
2
)
=
4
+
3
x
1
+
2
x
1
2
x
2
+
x
2
4
L
(
F
)
=
2
x
1
2
x
2
D
(
F
)
=
{
x
1
x
2
2
,
x
1
2
,
x
1
x
2
,
x
2
2
,
x
1
,
x
2
,
1
}
{\displaystyle {\begin{aligned}&F(x_{1},x_{2})=4+3x_{1}+2x_{1}^{2}x_{2}+x_{2}^{4}\\[3pt]&{\text{L}}(F)=2x_{1}^{2}x_{2}\\[3pt]&{\text{D}}(F)={\Big \{}x_{1}x_{2}^{2},x_{1}^{2},x_{1}x_{2},x_{2}^{2},x_{1},x_{2},1{\Big \}}\end{aligned}}}