Line complexity asymptotics of polynomial cellular automata
Cellular automata are discrete dynamical systems that consist of patterns of symbols on a grid, which change according to a locally determined transition rule. In this paper, we will consider cellular automata that arise from polynomial transition rules, where the symbols are integers modulo some pr...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2018
|
| Online Access: | http://hdl.handle.net/1721.1/119219 |
| _version_ | 1826217561919848448 |
|---|---|
| author | Stone, Bertrand Stone, Bertrand A. |
| author2 | Massachusetts Institute of Technology. Department of Humanities. Music and Theater Arts Section |
| author_facet | Massachusetts Institute of Technology. Department of Humanities. Music and Theater Arts Section Stone, Bertrand Stone, Bertrand A. |
| author_sort | Stone, Bertrand |
| collection | MIT |
| description | Cellular automata are discrete dynamical systems that consist of patterns of symbols on a grid, which change according to a locally determined transition rule. In this paper, we will consider cellular automata that arise from polynomial transition rules, where the symbols are integers modulo some prime p. We consider the asymptotic behavior of the line complexity sequence a[subscript T](k), which counts, for each k, the number of coefficient strings of length k that occur in the automaton. We begin with the modulo 2 case. For a polynomial T(x)=c[subscript0] + c[subscript 1]x+...+c[subscript n]x[superscript n] with c[subscript 0],c[subscript n] ≠ 0, we construct odd and even parts of the polynomial from the strings0[subscript c[subscript 1]c[subscript 3]c[subscript 5] ... c[subscript 1+2 |_(n-1)/2_|] and c[subscript 0]c[subscript 2]c[susscript 4] .... c[subscript 2[_ n/2_|] respectively. We prove that a[subscript T][superscript (k)] satisfies recursions of a specific form if the odd and even parts of T are relatively prime. We also define the order of such a recursion and show that the property of “having a recursion of some order” is preserved when the transition rule is raised to a positive integer power. Extending to a more general setting, we consider an abstract generating function ϕ(z = ∑[subscript k=1][superscript ∞] α(k)z[superscript k] which satisfies a functional equation relating ϕ(z) and (z[superscript p]) . We show that there is a continuous, piecewise quadratic function f on [1 / p, 1] for which lim[subscript k→ ∞] (α(k)/k[superscript 2] - f(p[superscript -⟨log[subscript p]k))) = 0 (here ⟨y⟩ = y - ⌊y⌋). We use this result to show that for certain positive integer sequences s[subscript k] (x)→ ∞ with a parameter x ∈ [1/p,1], the ratio α(s[subscript k](x))/s[subscript k](x)[superscript 2] tends to f(x), and that the limit superior and inferior of α(k)/k[superscript 2] are given by the extremal values of f. Keywords: Cellular automata, Line complexity, Additive transition rules, Asymptotic estimates |
| first_indexed | 2024-09-23T17:05:38Z |
| format | Article |
| id | mit-1721.1/119219 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T17:05:38Z |
| publishDate | 2018 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1192192022-09-29T23:38:52Z Line complexity asymptotics of polynomial cellular automata Stone, Bertrand Stone, Bertrand A. Massachusetts Institute of Technology. Department of Humanities. Music and Theater Arts Section Massachusetts Institute of Technology. Department of Mathematics Stone, Bertrand A. Cellular automata are discrete dynamical systems that consist of patterns of symbols on a grid, which change according to a locally determined transition rule. In this paper, we will consider cellular automata that arise from polynomial transition rules, where the symbols are integers modulo some prime p. We consider the asymptotic behavior of the line complexity sequence a[subscript T](k), which counts, for each k, the number of coefficient strings of length k that occur in the automaton. We begin with the modulo 2 case. For a polynomial T(x)=c[subscript0] + c[subscript 1]x+...+c[subscript n]x[superscript n] with c[subscript 0],c[subscript n] ≠ 0, we construct odd and even parts of the polynomial from the strings0[subscript c[subscript 1]c[subscript 3]c[subscript 5] ... c[subscript 1+2 |_(n-1)/2_|] and c[subscript 0]c[subscript 2]c[susscript 4] .... c[subscript 2[_ n/2_|] respectively. We prove that a[subscript T][superscript (k)] satisfies recursions of a specific form if the odd and even parts of T are relatively prime. We also define the order of such a recursion and show that the property of “having a recursion of some order” is preserved when the transition rule is raised to a positive integer power. Extending to a more general setting, we consider an abstract generating function ϕ(z = ∑[subscript k=1][superscript ∞] α(k)z[superscript k] which satisfies a functional equation relating ϕ(z) and (z[superscript p]) . We show that there is a continuous, piecewise quadratic function f on [1 / p, 1] for which lim[subscript k→ ∞] (α(k)/k[superscript 2] - f(p[superscript -⟨log[subscript p]k))) = 0 (here ⟨y⟩ = y - ⌊y⌋). We use this result to show that for certain positive integer sequences s[subscript k] (x)→ ∞ with a parameter x ∈ [1/p,1], the ratio α(s[subscript k](x))/s[subscript k](x)[superscript 2] tends to f(x), and that the limit superior and inferior of α(k)/k[superscript 2] are given by the extremal values of f. Keywords: Cellular automata, Line complexity, Additive transition rules, Asymptotic estimates 2018-11-20T14:59:58Z 2018-11 2018-10-12T03:38:15Z Article http://purl.org/eprint/type/JournalArticle 1382-4090 1572-9303 http://hdl.handle.net/1721.1/119219 Stone, Bertrand. “Line Complexity Asymptotics of Polynomial Cellular Automata.” The Ramanujan Journal, vol. 47, no. 2, Nov. 2018, pp. 383–416. en https://doi.org/10.1007/s11139-017-9957-7 The Ramanujan Journal Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer Science+Business Media, LLC application/pdf Springer US Springer US |
| spellingShingle | Stone, Bertrand Stone, Bertrand A. Line complexity asymptotics of polynomial cellular automata |
| title | Line complexity asymptotics of polynomial cellular automata |
| title_full | Line complexity asymptotics of polynomial cellular automata |
| title_fullStr | Line complexity asymptotics of polynomial cellular automata |
| title_full_unstemmed | Line complexity asymptotics of polynomial cellular automata |
| title_short | Line complexity asymptotics of polynomial cellular automata |
| title_sort | line complexity asymptotics of polynomial cellular automata |
| url | http://hdl.handle.net/1721.1/119219 |
| work_keys_str_mv | AT stonebertrand linecomplexityasymptoticsofpolynomialcellularautomata AT stonebertranda linecomplexityasymptoticsofpolynomialcellularautomata |