Volume 6 • Issue 1 • 2026
Reversibility of Circular Linear Cellular Automata over Finite Fields: An Exact Enumeration via the Unit Group of the Cyclic Group Algebra
Open Access & Copyright
© 2026 The Author(s). Published by ASPG. This article is licensed under the Creative Commons Attribution 4.0 International License (CC BY 4.0).
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
References
[1] G. A. Hedlund, “Endomorphisms and automorphisms of the shift dynamical system,” Mathematical Systems Theory, vol. 3, no. 4, pp. 320–375, 1969.
[2] O. Martin, A. M. Odlyzko, and S. Wolfram, “Algebraic properties of cellular automata,” Communications in Mathematical Physics, vol. 93, no. 2, pp. 219–258, 1984.
[3] G. Manzini and L. Margara, “Invertible linear cellular automata over Zm: Algorithmic and dynamical aspects,” Journal of Computer and System Sciences, vol. 56, no. 1, pp. 60–67, 1998.
[4] J. Kari, “Reversibility and surjectivity problems of cellular automata,” Journal of Computer and System Sciences, vol. 48, no. 1, pp. 149–182, 1994.
[5] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. Amsterdam: North-Holland, 1977.
[6] R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., ser. Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press, 1997, vol. 20.
[7] E. Czeizler and J. Kari, “A tight linear bound on the neighborhood of inverse cellular automata,” in Automata, Languages and Programming (ICALP 2005), ser. Lecture Notes in Computer Science, vol. 3580. Springer, 2005, pp. 410–420.
Cite This Article
Choose your preferred format
Publisher's Note
The statements, opinions, and data presented in this article are solely those of the author(s) and do not necessarily represent those of ASPG, the journal, or its editors. ASPG and the editors disclaim responsibility for any harm arising from the use of any ideas, methods, instructions, or products described in this article, to the fullest extent permitted by applicable law.