Information Technology Reference
In-Depth Information
when assuming only trivial linear dependencies. However, we thing that it is
easier to use Theorem 2 as one can plug in the numbers for a particular system
and do the simple arithmetic to get the expected number of linearly independent
equations. To find the same thing using Theorem 3, one needs to expand a com-
plicated series to find the coecient of a particular term. We start by computing
the
D
'th degree coecient in the series from Theorem 3
Proposition 1
[
t
D
]
p
(
t
)=[
t
D
]
1
n
1
m
−
t
2
−
t
k
1
1
−
t
1
−
t
1
−
t
2
k
1)
i
m
+
i
D−ik
n
j
.
=
k
i
=0
−
1
(
−
i
j
=0
=
l
=0
t
l
. The second
1
1
−t
Proof
The first fraction in
p
(
t
) can be written as
fraction can be expressed as
1
−t
2
1
n
=(1+
t
)
n
=
j
=0
j
t
j
.Thethirdfrac-
−t
tion can be expressed as
1
−t
k
1
−t
2
k
m
=(1
t
k
))
−m
. By [8], this is equal to
−
(
−
1)
i
m
+
i−
1
i
t
ik
. Since we are only interested in [
t
D
]
p
(
t
)where
D
i
=0
(
−
≤
n
,we
can cut away terms of degree higher than
D
in the three sums to get
[
t
D
]
p
(
t
)=[
t
D
]
D
t
l
⎛
t
j
⎞
⎛
t
ik
⎞
n
j
1)
i
m
+
i
D
k
D
−
1
⎝
⎠
⎝
⎠
=
(
−
i
l
=0
j
=0
i
=0
⎛
⎝
⎞
⎠
⎛
⎝
t
ik
⎞
n
j
1)
i
m
+
i
D
k
D
l
−
1
⎠
.
[
t
D
]
t
l
(
−
i
l
=0
j
=0
i
=0
We are looking for the coecient of the
D
'th degree term, so we need only
multiply the two sums together with the constraint
l
=
D
−
ik
.Takingawaythe
sum over
l
, substituting
D
ik
for
l
in the rest of the first sum and multiplying
together we get the desired expression for the
D
'th degree coecient.
−
The number
D
is the maximum degree of a monomial when running the XL
algorithm. Relating this to our notation we have
D
=
D
e
+
D
m
and
k
=
D
e
.We
then get the following result.
Corollary 1.
Let
D
=
D
e
+
D
m
and
k
=
D
e
,then
I
=[
t
D
]
1
n
1
m
−
t
2
−
t
k
1
T
−
1
−
t
1
−
t
1
−
t
2
k
is equivalent to
D
D
e
1)
i
m
+
i
i
+1
D
m
−ik
n
j
.
I
=
(
−
i
=0
j
=0
