The surjectivity characterization conjecture for LR-separated cellular automata

Let FF be a LRLR-separated cellular automaton over the finite field Zp\mathbb Z_{p}, where p3p\geq 3 is prime, and let \ell (respectively, rr) be the leftmost (respectively, rightmost) position of FF.

Surjectivity characterization conjecture. FF is surjective if and only if either

gcd(q,p1)=1\gcd(q_{\ell},p-1)=1

or

gcd(qr,p1)=1.\gcd(q_r,p-1)=1.

The conjecture proposes a complete characterization of surjective LRLR-separated cellular automata over finite fields, extending the one-sided sufficient criterion established for finite rings. The converse fails over general finite rings, so the finite-field hypothesis is essential to the proposed statement; its resolution is not given here.

Sources & referencesView supporting material

Primary source

Firas Ben Ramdhane, Alberto Dennunzio, Luciano Margara and Giuliamaria Menara, “Structural Properties of Non-Linear Cellular Automata: Permutivity, Surjectivity and Reversibility”, arXiv:2504.15949 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.