A sequential dynamical system consists of the following data; a finite graph Y with vertex set <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$v_1,\ldots ,v_n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>v</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>v</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, a state set, local update functions, and an update ordering <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>σ</mi> </math></EquationSource> </InlineEquation>. We study period-3 orbits of SDSs on the complete graph <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$K_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> with identical local functions. We prove that the maximum number <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\theta _{n+1}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>θ</mi> <mrow> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> of 3-cycles in the phase space equals <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$A_3(n,4)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>A</mi> <mn>3</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mn>4</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, the largest size of a ternary code of length n with minimum Hamming distance at least 4. Our approach reduces the problem to a clique number computation in an explicit graph and yields a direct correspondence with optimal ternary (n, 4)-codes. We also give field-agnostic necessary conditions for prime period-p orbits and discuss extensions over <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\mathbb {F}_p$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">F</mi> <mi>p</mi> </msub> </math></EquationSource> </InlineEquation>.

Period-3 Orbits of Sequential Dynamical Systems and Their Relationship to Error-Correcting Codes over Finite Fields

期刊论文
发表日期：

2026年1月5日

查看全文

Tuğçe Ulutaş,
Mehmet Emin Köroğlu

摘要

A sequential dynamical system consists of the following data; a finite graph Y with vertex set $v_1,\ldots ,v_n$ $v_{1}, \dots, v_{n}$ , a state set, local update functions, and an update ordering $\sigma $ $σ$ . We study period-3 orbits of SDSs on the complete graph $K_n$ $K_{n}$ with identical local functions. We prove that the maximum number $\theta _{n+1}$ $θ_{n + 1}$ of 3-cycles in the phase space equals $A_3(n,4)$ $A_{3} (n, 4)$ , the largest size of a ternary code of length n with minimum Hamming distance at least 4. Our approach reduces the problem to a clique number computation in an explicit graph and yields a direct correspondence with optimal ternary (n, 4)-codes. We also give field-agnostic necessary conditions for prime period-p orbits and discuss extensions over $\mathbb {F}_p$ $F_{p}$ .