ASPG Menu
search

American Scientific Publishing Group

verified Journal

Pure Mathematics for Theoretical Computer Science

ISSN
Online: 2995-3162
Frequency

Continuous publication

Publication Model

Open access journal. All articles are freely available online with no APC.

Pure Mathematics for Theoretical Computer Science
Full Length Article

Volume 6Issue 1 • 2026

Reversibility of Circular Linear Cellular Automata over Finite Fields: An Exact Enumeration via the Unit Group of the Cyclic Group Algebra

Lee Xu 1* ,
Olalekan Joosati 2
1Mathematics Department, University of Chinese Academy of Sciences (CAS), Beijing, China
2Faculty of Applied Science, Cape Peninsula University of Technology, South Africa
* Corresponding Author.
verified

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

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

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

format_quote
Xu, Lee, Joosati, Olalekan. "Reversibility of Circular Linear Cellular Automata over Finite Fields: An Exact Enumeration via the Unit Group of the Cyclic Group Algebra." Pure Mathematics for Theoretical Computer Science, vol. Volume 6, no. Issue 1, 2026, pp. . DOI:
Xu, L., Joosati, O. (2026). Reversibility of Circular Linear Cellular Automata over Finite Fields: An Exact Enumeration via the Unit Group of the Cyclic Group Algebra. Pure Mathematics for Theoretical Computer Science, Volume 6(Issue 1), . DOI:
Xu, Lee, Joosati, Olalekan. "Reversibility of Circular Linear Cellular Automata over Finite Fields: An Exact Enumeration via the Unit Group of the Cyclic Group Algebra." Pure Mathematics for Theoretical Computer Science Volume 6, no. Issue 1 (2026): . DOI:
Xu, L., Joosati, O. (2026) 'Reversibility of Circular Linear Cellular Automata over Finite Fields: An Exact Enumeration via the Unit Group of the Cyclic Group Algebra', Pure Mathematics for Theoretical Computer Science, Volume 6(Issue 1), pp. . DOI:
Xu L, Joosati O. Reversibility of Circular Linear Cellular Automata over Finite Fields: An Exact Enumeration via the Unit Group of the Cyclic Group Algebra. Pure Mathematics for Theoretical Computer Science. 2026;Volume 6(Issue 1):. DOI:
L. Xu, O. Joosati, "Reversibility of Circular Linear Cellular Automata over Finite Fields: An Exact Enumeration via the Unit Group of the Cyclic Group Algebra," Pure Mathematics for Theoretical Computer Science, vol. Volume 6, no. Issue 1, pp. , 2026. DOI:
policy

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.

Digital Archive Ready