|
Articles Cellular Automata Algebraic Properties of Cellular Automata (1984)
Algebraic Properties of Cellular Automata (1984) |
|
Detailed discussion of the material in this appendix may be found in [8].
A. Basic Notations
denotes 
reduced modulo 
, or the remainder of after division by .
or 
denotes the greatest common divisor of and . When and are polynomials, the result is taken to be a polynomial with unit leading coefficient (monic).
represents the statement that divides (with no remainder).
indicates that 
is the highest power of which divides .
Exponentiation is assumed right associative, so that 
denotes 
not 
.
usually denotes a prime integer.
denotes an arbitrary commutative ring of 
elements.
denotes the ring of integers modulo .
denotes the highest power of 
which appears in 
.
B. Finite Fields
There exists a finite field unique up to isomorphism with any size 
( prime), denoted 
. is termed the characteristic of the field.
The ring of integers modulo forms a field only when is prime, since only in this case do unique inverses under multiplication modulo exist for all nonzero elements. (For example, in 
, 2 has no inverse.) 
is therefore isomorphic to 
.
The field is conveniently represented by the set of polynomials of degree less than 
with coefficients in , with all polynomial operations performed modulo a fixed irreducible polynomial of degree over . For example, 
may be represented by elements 
, 
, 
, 
with operations performed modulo 2 and modulo 
. In this case for example 
. Notice that, as mentioned in Sect. A.C below, polynomials over a field form a unique factorization domain.
Any field of size 
yields a group of size 
under multiplication if the zero element is removed. Thus for any element of 
,
and 
for 
. Notice that if 
and 
, then 
.
C. Polynomials over Finite Fields
Polynomials in any number of variables with coefficients in form a unique factorization domain. For such polynomials, therefore, 
implies 
if 
, 
.
For any polynomials 
and 
with coefficients in , there exist polynomials 
and 
such that
There are exactly 
univariate polynomials over with degree less than 
. With a polynomial 
of degree 
, the number of polynomials with degree not exceeding for which 
is 
for 
.
For any prime , and for elements 
of 
,
Thus for example,
a result used extensively in Sect. 3.
If 
, then every root of 
must be a root of 
. If 
and
then
where 
is the formal derivative of 
, obtained by differentiation of each term in the polynomial. [Note that integration is not defined for polynomials over .]
The number of roots (not necessarily distinct) of a polynomial over is equal to the degree of the polynomial. The roots may lie in an extension of .
Over the field ,
where 
, with 
defined in Sects. 3 and 4 as the maximum power of which divides 
. The polynomial 
with not a multiple of then factorizes over according to
where the 
are irreducible cyclotomic polynomials of degree 
. Note that the multiplicity of any irreducible factor of 
is exactly , and that
D. Dipolynomials over Finite Fields
A dipolynomial is taken to divide a dipolynomial if there exists a dipolynomial 
such that 
. Hence if and are polynomials, with 
, and if 
are dipolynomials, then are polynomials.
Congruence in the ring of dipolynomials is defined as follows: 
for dipolynomials , 
, and if 
.
The greatest common divisor of two nonzero dipolynomials 
and 
is defined as the ordinary polynomial 
, where 
and 
is chosen to make 
a polynomial with nonzero constant term. Note that by analogy with Eq. (A.2), for any dipolynomials and , there exist dipolynomials 
and 
such that
