|
Articles Cellular Automata Algebraic Properties of Cellular Automata (1984)
Algebraic Properties of Cellular Automata (1984) |
|
A. Euler Totient Function 
is defined as the number of integers less than 
which are relatively prime to [7]. is a multiplicative function, so that
For 
prime,
Hence
providing a formula by which may be computed. Some values of are given in Table 4.
is bounded (for 
) by
where 
is some positive constant, and the upper bound is achieved if and only if is prime. For large , 
tends on average to a constant value.
satisfies the Euler-Fermat theorem
and suborder 
functions defined in Eqs. (B.6) and (B.10), respectively, together with values of the Euler totient function . Each column gives values of the pair 
, 
.B. Multiplicative Order Function 
The multiplicative order function is defined as the minimum positive integer 
for which [8]
This condition can only be satisfied if 
.
By the Euler-Fermat theorem (B.5),
In addition, 
, 
, 
. Some special cases are
A rigorous bound on is
where the upper bound is attained only if is prime. It can be shown that on average, for large , 
; the actual average is presumably closer to . Nevertheless, for large , 
tends to zero on average.
Some values of the multiplicative order function are given in Table 4.
The multidimensional generalization 
of the multiplicative order function is defined as the minimum positive integer for which 
simultaneously modulo 
, 
and 
. It is clear that
C. Multiplicative Suborder Function 
The multiplicative suborder function is defined as the minimum for which
again assuming 
. Comparison with (B.6) yields
or
The second case becomes comparatively rare for large ; the fraction of integers less than 
for which it is realised may be shown to be asymptotic to 
[16], where and 
are constants determined by 
.
In general,
the upper limit again being achieved only if is prime. For large , 
on average.
The multidimensional generalization 
of the multiplicative suborder function is defined as the minimum positive integer for which 
simultaneously modulo 
, with 
and 
perhaps taken variously for the different 
. The analogue of Eq. (B.9) for this function is
and
or
Acknowledgement. We are grateful to O. E. Lanford for several suggestions.
