On surjectivity and dynamical properties of dill maps

Firas Ben Ramdhane

REVIEW 1 major objections 5 minor 12 references

On surjectivity and dynamical properties of dill maps

T0 review · 1 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Surjective uniform dill maps are exactly cellular automata

desk verdict A correct but modest surjectivity theorem for uniform dill maps, with one genuine gap: the proof needs |A| ≥ 2, and the singleton alphabet breaks the precise statement. read the letter →

arxiv 2506.00960 v1 pith:GDYNHLXJ submitted 2025-06-01 math.DS cs.DM

Firas Ben Ramdhane This is my paper

classification math.DScs.DM MSC 37B1037B15

keywords dillmapscellularautomatasubstitutionssurjectivityequicontinuitysymbolicdynamicsexpansivitypreimagecounting

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Uniform dill maps generalise cellular automata and substitutions by reading a sliding window and writing a block of possibly several symbols per step. The paper's central claim is that the only surjective uniform dill maps are the surjective cellular automata: as soon as such a map is onto, every window must produce exactly one symbol, so variable-length writing is impossible. This matters because it draws a sharp structural line inside symbolic dynamics, showing that block-writing maps cannot fill the whole configuration space unless they are already classical cellular automata. The paper also establishes a sufficient condition for equicontinuity and exhibits an expansive dill map that is not surjective, in contrast to cellular automata.

What carries the argument

The central object is the extended local rule $f^*$, which slides a window of diameter $\theta$ along a finite word and concatenates the output blocks. The argument fixes the upper norm $\ell$ and defines $p$ as the minimum number of preimages under $f^*$ among words of length $k\ell$; surjectivity gives $p>0$, and a double-counting identity shows $p=|A|^{(\theta-1)\ell}$. Comparing $|A|^\theta = |A|^{\theta\ell}$ then yields $\ell=1$, which reduces the map to a cellular automaton. Preimage-balance counting is the mechanism that carries the theorem.

What would settle it

Take $A=\{a\}$ and any uniform dill rule $f$ of constant length $r>1$; then $F(a^{\mathbb{N}})=a^{\mathbb{N}}$ is the same surjective map as a cellular automaton, so the theorem's literal claim fails unless $|A|\ge 2$ is added. The theorem could also be tested by searching for any binary uniform dill map with constant output length greater than 1 that is surjective.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is Theorem 2: a uniform dill map $F$ with diameter $\theta$ and local rule $f$ is surjective if and only if it is a surjective cellular automaton, meaning $|f(u)|=1$ for every $u\in A^\theta$ and every nonempty word $v$ has exactly $|A|^{\theta-1}$ preimages under $f^*$. The proof adapts the classical balanced-counting argument for cellular automata to block outputs; once uniform preimage balance is established, comparing $|A|^\theta$ with $|A|^{\theta\ell}$ forces $\ell=1$, so the output length collapses to one. A direct consequence is that uniform dill maps with constant block length greater than one, or with variable block lengths, are never onto.

Load-bearing premise

The proof silently assumes the alphabet has at least two symbols; the step concluding $\ell=1$ by comparing exponents in $|A|^\theta = |A|^{\theta\ell}$ is invalid when $|A|=1$, and a one-letter uniform dill rule of constant length $r>1$ defines the same surjective map as a cellular automaton.

Editorial extensions

If this is right

Theorem 2 implies that no uniform dill map with a variable-length local rule can be surjective; onto maps must write single symbols at every window position.
Surjective uniform dill maps inherit the uniform preimage balance of cellular automata: every nonempty word has exactly $|A|^{\theta-1}$ preimages under $f^*$.
Corollary 2 transfers cellular automaton rigidity: a surjective uniform dill map is expansive, transitive, open, or closing exactly when the corresponding cellular automaton is.
The condition $\theta \le |f|$ guarantees equicontinuity, so such dill maps cannot be expansive (Remark 1).
Example 2 shows a dill map can be expansive but not surjective, a behaviour impossible for cellular automata.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A testable boundary case is to allow local rules with non-constant output lengths whose average length is 1; if such a dill map over a binary alphabet can be onto, then uniformity, not constant length alone, is the true obstruction.
The theorem makes surjectivity of uniform dill maps checkable from finite data: verify $|f(u)|=1$ on all $\theta$-blocks and count preimages of finitely many words, with no search over infinite configurations.
A natural next step the paper leaves open is whether equicontinuity of non-uniform dill maps admits a blocking-word characterisation analogous to the cellular automaton case; Proposition 1 looks like one sufficient condition inside that larger question.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper proves a clean, modest theorem: among uniform dill maps, surjectivity forces the local rule to output single letters, so the map is actually a cellular automaton. The balance-counting proof is a faithful adaptation of Hedlund and Kůrka, and I think it is correct for alphabets of size at least two. That is the main result, and it is a genuine extension to a class that had only been defined and characterized before, not analyzed for surjectivity. The equicontinuity sufficient condition (Proposition 1) is also correct, though not deep.

The stress-test note is right. Theorem 2 as stated quantifies over all finite alphabets, and the proof jumps from (♯A)^θ = (♯A)^θℓ to ℓ = 1. That implication requires ♯A ≥ 2. For A = {0}, every dill map is the identity on the singleton Cantor space, hence surjective, but the local rule can have constant length ℓ > 1. So the precise characterization '|f(u)| = 1 for all u' is false as stated. The abstract's looser phrasing—surjective uniform dill maps are surjective CAs—survives in the sense that the map itself is a CA, but the theorem's internal characterization and the corollary about variable-length uniform dill maps need a separate singleton case or an explicit |A| ≥ 2 hypothesis. This is a genuine formulation gap, though easily fixable.

Other issues are minor. Example 2's expansivity proof is a sketch rather than a complete argument, and there are typos and notational slips, such as the definition of q1 in Proposition 1 and the bound on q_t. The citation pattern is fine: the main theorem is not in the cited papers, and the only self-citation (Theorem 1, characterizing dill maps) is not used circularly.

Overall, the central claim holds up for non-trivial alphabets, and the gap is small enough that a referee can ask for a patch rather than a rethink. I would send this to a serious referee, with a request to state |A| ≥ 2, handle the singleton case, and tighten the expansivity example.

Referee Report

1 major / 5 minor

Summary. The paper studies dill maps over the one-sided full shift A^N, which generalize both cellular automata and substitutions by allowing the local rule to output words of variable length. The main result (Theorem 2) claims that a uniform dill map is surjective if and only if it is a surjective cellular automaton, i.e., its local rule outputs single letters and satisfies a balanced preimage condition. The paper also proves a sufficient condition for equicontinuity (Proposition 1 and Corollary 1) and gives an example of an expansive non-surjective dill map, contrasting with the known behavior of cellular automata.

Significance. If the main theorem is correct, it is a strong rigidity result: among uniform dill maps, surjectivity forces the local rule to have length one, so variable-length uniform dill maps cannot be onto. The proof is self-contained and adapts classical balance-counting arguments from Hedlund and Kůrka; no parameters are fitted. Proposition 1 is a clean sufficient condition for equicontinuity. The paper is clearly written in structure, though with several presentation defects. The central theorem as stated, however, fails for one-letter alphabets, so the main claim needs a small but essential correction before the paper can be accepted.

major comments (1)

[3, Theorem 2] Theorem 2 is false as stated when the alphabet has exactly one symbol. The proof concludes ℓ=1 from the equation (♯A)^θ = (♯A)^ℓ(♯A)^((θ−1)ℓ) = (♯A)^(θℓ), but this exponent comparison is only valid when ♯A≥2. If A={0}, a uniform dill rule of constant length ℓ>1, e.g., f(0^θ)=0^ℓ, defines the identity map on the one-point Cantor space. That map is surjective and is a cellular automaton (with a different local rule), yet |f(u)|=ℓ>1, contradicting the stated characterization. The paper should either state explicitly the standing assumption |A|≥2, or give a separate one-sentence treatment of the singleton case.

minor comments (5)

[3, proof of Theorem 2] The counting argument is correct in substance for |A|≥2, but the display 'p×(♯A)^k = ... = ... > p(♯A)^(kℓ)' uses the symbol k both for the length of the input suffix in A^k and for the index of the output word length kℓ in A^(kℓ). This makes the proof hard to follow. Please clarify by using two different indices, and justify explicitly why the set {u'v : u'∈(f*)^{-1}(u), v∈A^k} equals the union over w∈A^(kℓ) of (f*)^{-1}(uw).
[3, Example 2] The notation 'a≠b≠c' should be defined as 'a,b,c pairwise distinct'; as written it is ambiguous. The proof of non-surjectivity contains several typos and unclear equalities (e.g., 'f*(u0u1u2u3) = w0w1w2 = 01' and 'f(u2u3u4)=2=w3' followed by 'f(012)=22'), which should be corrected. The proof of positive expansivity is only a sketch: the quantities pt and Δt are not defined cleanly, and the key assertion that applying f* cannot create a factor a≠b≠c unless such a pattern already existed is stated without proof. Since this example is used to exhibit an expansive non-surjective dill map, it deserves a rigorous write-up.
[3, Corollary 2] The term 'opening' should be 'open' (open maps). Also, 'transitive ... cellular automata are surjective' is stated with citation [3]; make sure the citation is to the correct result for one-sided cellular automata.
[Throughout] There are numerous typographical and grammatical errors, e.g., 'Comminucations' in the affiliation, 'defintions' in Section 2, 'let us start by given', and missing spaces before 'A'. A careful proofreading pass is recommended.
[2, Example 1] The displayed local rule 'τ ◦ f : aa, bb7→ ab ba, ab7→ a' is ambiguous; please present the values of τ∘f on all length-2 words in a table or with clear spacing.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 2 is proved by a self-contained counting argument on the local rule, independent of the paper's own Theorem 1.

full rationale

The only self-citation, Theorem 1 (from the author's thesis), is presented as background characterization and is never invoked in the proof of the main results. The proof of Theorem 2 follows Kůrka's Theorem 5.21, an external result, and is a finite counting argument: surjectivity gives a positive minimal preimage count p, the count is shown constant over words of length kℓ, and the contradiction argument forces p = (♯A)^((θ−1)ℓ) and then ℓ = 1 from (♯A)^θ = (♯A)^(θℓ). No fitted parameter is introduced, no conclusion is assumed, and no known result is merely renamed. The corollaries on equicontinuity, expansivity, transitivity, openness, and closing all rest on Theorem 2/Proposition 1 plus standard external theorems (Hedlund, Kůrka, Fagnani–Margara, Codenotti–Margara). The singleton-alphabet edge case, where comparing exponents does not force ℓ = 1, is a genuine correctness gap but not a circularity, and it does not change the circularity verdict.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

Theorem 2 relies on finite-word counting over an alphabet of size at least 2, on the assumption that every local block is non-empty so that F maps into A^N, and on Hedlund's balance criterion for surjective cellular automata. No free parameters or invented entities appear in the paper.

assumptions (3)

domain assumption Alphabet A has at least two symbols.
The counting step (♯A)^θ=(♯A)^(θℓ) in Theorem 2 concludes ℓ=1 by comparing exponents. With |A|=1 that comparison is void and the theorem as stated fails, so |A|≥2 is load-bearing and unstated.
domain assumption Dill map local rules are non-erasing: every output block f(u) is a nonempty word.
Definition 2 writes f:A^θ→A* without requiring f(u) to be nonempty. The proofs use the lower norm |f| and the length formula |f*(u)|=|f|(|u|-θ+1), which require |f|≥1 for a map A^N→A^N.
standard math Hedlund's balance condition characterizes surjective cellular automata.
The equivalence in Theorem 2 uses the classical fact that a cellular automaton is surjective exactly when every nonempty word has |A|^(θ−1) preimages; the proof re-derives the condition and leans on this external theorem for the converse direction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On surjectivity and dynamical properties of dill maps." pith.science (2026). https://pith.science/paper/GDYNHLXJ

@misc{pith2026250600960,
  author       = {Pith},
  title        = {Pith review of: On surjectivity and dynamical properties of dill maps},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GDYNHLXJ}},
  note         = {Machine review of arXiv:2506.00960}
}

read the original abstract

In this paper, we study certain dynamical properties of dill maps, a class of functions introduced in~\cite{salo2015block} that generalizes both cellular automata and substitutions. In particular, we prove that surjective uniform dill maps are precisely the surjective cellular automata. We also establish a sufficient condition for a dill map to be equicontinuous.

Figures

Figures reproduced from arXiv: 2506.00960 by the authors.

**Figure 1.** Space-time diagrams of two configurations sharing a common prefix. The two space-time diagrams illustrate the evolution of configurations over {0, 1, 2} N under the local rule f. Both configurations share a long common prefix, but differ in their suffixes. In the first configuration, patterns where three consecutive symbols are all distinct are present, causing some symbols to duplicate during the evolution. In co… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

12 extracted references · 9 canonical work pages

[1]

Ben Ramdhane, F.: Symbolic dynamical systems in topological spaces defined via edit distances. Ph.D. thesis, Aix Marseille Universit \'e (AMU), Marseille, FRA.; University of Sfax, Tunisia (2023)

work page 2023
[2]

(eds.): Combinatorics, automata, and number theory., Encyclopedia of Mathematics and Its Applications, vol

Berth \'e , V., Rigo, M. (eds.): Combinatorics, automata, and number theory., Encyclopedia of Mathematics and Its Applications, vol. 135. Cambridge: Cambridge University Press (2010)

work page 2010
[3]

The American Mathematical Monthly 103(1), 58--62 (1996)

Codenotti, B., Margara, L.: Transitive cellular automata are sensitive. The American Mathematical Monthly 103(1), 58--62 (1996)

work page 1996
[4]

Theory of Computing Systems 31(6), 663--677 (1998)

Fagnani, F., Margara, L.: Expansivity, permutivity, and chaos for cellular automata. Theory of Computing Systems 31(6), 663--677 (1998)

work page 1998
[5]

(eds.): Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol

Fogg, N.P., Berth \'e , V., Ferenczi, S., Mauduit, C., Siegel, A. (eds.): Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794. Berlin: Springer (2002). doi:10.1007/b13861, link.springer.de/link/service/series/0304/tocs/t1794.htm

doi:10.1007/b13861 2002
[6]

Mathematical systems theory 3(4), 320--375 (1969)

Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical system. Mathematical systems theory 3(4), 320--375 (1969)

work page 1969
[7]

Ergodic theory and dynamical systems 17(2), 417--433 (1997)

K u rka, P.: Languages, equicontinuity and attractors in cellular automata. Ergodic theory and dynamical systems 17(2), 417--433 (1997)

work page 1997
[8]

Soci \'e t \'e math \'e matique de France Paris, France (2003)

K u rka, P.: Topological and symbolic dynamics. Soci \'e t \'e math \'e matique de France Paris, France (2003)

work page 2003

Show all 12 references

[9]

Ergodic Theory and Dynamical Systems 35(7), 2292--2310 (2015)

Salo, V., T \"o rm \"a , I.: Block maps between primitive uniform and pisot substitutions. Ergodic Theory and Dynamical Systems 35(7), 2292--2310 (2015)

2015
[10]

IEEE Transactions on Neural Networks 5(1), 3--14 (1966)

Von Neumann, J., Burks, A.W., et al.: Theory of self-reproducing automata. IEEE Transactions on Neural Networks 5(1), 3--14 (1966)

1966
[11]

, " * write output.state after.block = add.period write

ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION in...
[12]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Ben Ramdhane, F.: Symbolic dynamical systems in topological spaces defined via edit distances. Ph.D. thesis, Aix Marseille Universit \'e (AMU), Marseille, FRA.; University of Sfax, Tunisia (2023)

work page 2023

[2] [2]

(eds.): Combinatorics, automata, and number theory., Encyclopedia of Mathematics and Its Applications, vol

Berth \'e , V., Rigo, M. (eds.): Combinatorics, automata, and number theory., Encyclopedia of Mathematics and Its Applications, vol. 135. Cambridge: Cambridge University Press (2010)

work page 2010

[3] [3]

The American Mathematical Monthly 103(1), 58--62 (1996)

Codenotti, B., Margara, L.: Transitive cellular automata are sensitive. The American Mathematical Monthly 103(1), 58--62 (1996)

work page 1996

[4] [4]

Theory of Computing Systems 31(6), 663--677 (1998)

Fagnani, F., Margara, L.: Expansivity, permutivity, and chaos for cellular automata. Theory of Computing Systems 31(6), 663--677 (1998)

work page 1998

[5] [5]

(eds.): Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol

Fogg, N.P., Berth \'e , V., Ferenczi, S., Mauduit, C., Siegel, A. (eds.): Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794. Berlin: Springer (2002). doi:10.1007/b13861, link.springer.de/link/service/series/0304/tocs/t1794.htm

doi:10.1007/b13861 2002

[6] [6]

Mathematical systems theory 3(4), 320--375 (1969)

Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical system. Mathematical systems theory 3(4), 320--375 (1969)

work page 1969

[7] [7]

Ergodic theory and dynamical systems 17(2), 417--433 (1997)

K u rka, P.: Languages, equicontinuity and attractors in cellular automata. Ergodic theory and dynamical systems 17(2), 417--433 (1997)

work page 1997

[8] [8]

Soci \'e t \'e math \'e matique de France Paris, France (2003)

K u rka, P.: Topological and symbolic dynamics. Soci \'e t \'e math \'e matique de France Paris, France (2003)

work page 2003