Reversibility of Circular Linear Cellular Automata over Finite

Fields: An Exact Enumeration via the Unit Group of the Cyclic

Group Algebra

Lee Xu1,* Olalekan Joosati2

1 Mathematics Department, University of Chinese Academy of Sciences (CAS), Beijing, China

2 Faculty of Applied Science, Cape Peninsula University of Technology, South Africa

Received: August 07, 2025 Revised: November 03, 2025 Accepted: December 30, 2025 ⋆ Corresponding author

ABSTRACT

We study the reversibility of one-dimensional linear cellular automata (CA) with periodic boundary conditions over a

finite field Fq, identifying the global transition map with multiplication by a rule polynomial f (x) in the cyclic group

algebra Rn = Fq[x]/(xn−1). We prove that reversibility is exactly equivalent to f (x) being a unit of Rn, and, when

gcd(n,q) = 1, we use the classical correspondence between irreducible factors of xn−1 and q-cyclotomic cosets

modulo n to derive a closed-form count of the reversible rules of a given neighborhood size: |R×n

| = Πi(qdi −1),

where the di are the sizes of the q-cyclotomic cosets modulo n. We then resolve the complementary case gcd(n,q)>1:

writing n = pam with p = char(Fq) and gcd(m, p) = 1, we show xn−1 = (xm−1)pa , determine the local structure

of each factor ring Fq[x]/(g(x)pa

) for g irreducible, and obtain the fully general count |R×n

| = Πi qdi(pa−1)(qdi −1),

valid for every n and every finite field Fq. We give an explicit closed form for the case where m is prime and q is

a primitive root modulo m, a density lower bound, an explicit description of the group of reversible rules under

composition together with a formula for the exact dynamical period of any reversible rule via its coordinates under

the Chinese Remainder Theorem, and a remark on explicit inverse-rule construction. All results are stated and proved

in full; numerical instances used to validate the formulas were checked by direct and brute-force computation and

are reported without tabulation.

Keywords: Linear cellular automata Reversibility Finite fields Cyclotomic cosets Group algebras Cyclic codes

1. INTRODUCTION

The global transition function of a one-dimensional cellular

automaton is a shift-commuting continuous self-map of a

symbolic sequence space, and every such map is generated

by a local rule applied uniformly across cells [1]. When the

local rule is linear and the alphabet is a finite field, the global

map of a periodic (circular) automaton coincides exactly

with multiplication in the group algebra of the cyclic group

of cell indices, a fact underlying the algebraic analysis of

additive cellular automata [2] and the algorithmic study of

invertibility for linear automata over general residue rings

Zm [3, 4]. This note isolates the finite-field case and answers a

purely enumerative question left implicit in that literature: not

merely how to decide whether a single given rule is reversible,

but exactly how many reversible rules of a fixed neighborhood

size exist. The answer follows from the classical structure

theory of the ring Fq[x]/(xn−1), which is also the ambient

ring of cyclic error-correcting codes [5, 6].