[#P2812] Positive cycle entropy for finite cyclic Rule 30
Problem. For \(n\ge1\), let \(F_n:\{0,1\}^n\to\{0,1\}^n\) be cyclic Rule 30, \((F_n(x))_i=x_{i-1}\mathbin{\mathsf{xor}}(x_i\mathbin{\mathsf{or}}x_{i+1})\), with indices modulo \(n\). Let \(M_n\) be the largest eventual period of an orbit of \(F_n\). Is \(\limsup_{n\to\infty} n^{-1}\log_2 M_n>0\)?
1Context
Finite Rule 30 tables contain large and highly irregular periods. A construction relating widths, a transfer description of cycles, or certified lower bounds on an infinite subsequence would turn those isolated computations into reusable dynamics.
2Problem setup
Definition 1 (The eventual period of \(x\). The eventual period of \(x\) is the least positive \(p\) for which \(F_n^{t+p}(x)=F_n^t(x)\) for some \(t\ge0\).
Definition 2 (The limsup inequality). The limsup inequality is equivalent to the existence of constants \(c>0\) and infinitely many \(n\) with \(M_n\ge2^{cn}\).
Definition 3 (The displayed Boolean formula fixes the Rule 30 convention and the orientation of the neighborhood). The displayed Boolean formula fixes the Rule 30 convention and the orientation of the neighborhood.
Remark 1. Finite Rule 30 tables contain large and highly irregular periods. A construction relating widths, a transfer description of cycles, or certified lower bounds on an infinite subsequence would turn those isolated computations into reusable dynamics.
3What counts as a solution
- Prove that \(M_n\ge2^{cn}\) for some explicit \(c>0\) and infinitely many \(n\), or prove \(\log M_n=o(n)\).
- A disproof may also establish \(\limsup n^{-1}\log_2M_n=0\); finite tables alone do not settle either side.
1Status
Current status (Current status and unresolved remainder). UNKNOWN as of 2026-07-31. Exact maximum-period tables exist for small widths, and the checked structural results for Rule 30 do not prove an exponential subsequence of finite-ring periods. Prove that \(M_n\ge2^{cn}\) for some explicit \(c>0\) and infinitely many \(n\), or prove \(\log M_n=o(n)\).[1]
1Records
Notes and companion material
Original intake status. UNKNOWN as of 2026-07-31. Exact maximum-period tables exist for small widths, and the checked structural results for Rule 30 do not prove an exponential subsequence of finite-ring periods.
- 2026-07-27 prior-art search checked finite-width Rule 30 maximum periods, Rule 30 expansivity, periodic configurations, and cellular-automaton cycle growth; no asymptotic lower bound matching the statement was found.
- A single record cycle at one width gives no asymptotic conclusion. Useful progress should identify a construction that embeds or combines cycles across widths.
- Left permutivity controls preimages in one direction, while long temporal cycles on a ring also require the wraparound constraints to close.
Recorded example 1. The exact maxima at widths 4, 7, 14, 16, and 17 are respectively 8, 63, 1428, 6016, and 10846.
Computational notes
- Complete functional-graph enumeration for widths 1 through 18 gave \(M_n=1,1,1,8,5,1,63,40,171,15,154,102,832,1428,1455,6016,10846,2844\). Every transition and cycle length was computed with integer bit operations.
How the 2 records connect
ProblemPositive cycle entropy for finite cyclic Rule 30
2See also
How to cite
TheoremDB contributors, “Positive cycle entropy for finite cyclic Rule 30,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/rule-30-positive-cycle-entropyThis page as plain text: rule-30-positive-cycle-entropy.md
This problem includes 2 records joined by 1 typed links, sourced from doi.org[1], current as of July 31, 2026.
1References
- Packet source. Rapid left expansivity, a commonality between Wolfram's Rule 30 and powers of p/q, source checked for the TheoremDB status review (2026-07-31). The paper supplies current structural context for Rule 30; the finite-ring cycle-entropy target and prose were generated in a TheoremDB agent session on 2026-07-27. ↗journal article · primary sourceSource use: original summary.UNKNOWN as of 2026-07-27. Exact maximum-period tables exist for small widths, and the checked structural results for Rule 30 do not prove an exponential subsequence of finite-ring periods.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.Source used to assess the problem's recorded status.Source named by the research packet.
- Rapid left expansivity, a commonality between Wolfram's Rule 30 and powers of p/q. OEIS entry A334497, checked 2026-08-01. Status evidence identified in the source record and checked at the linked publication. ↗website · primary source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. Exact maximum-period tables exist for small widths, and the checked structural results for Rule 30 do not prove an exponential subsequence of finite-ring periods.Also cited at Entry definition, data, comments, and linked references relevant to Positive cycle entropy for finite cyclic Rule 30; checked 2026-08-01.Source used to assess the problem's recorded status.For Positive cycle entropy for finite cyclic Rule 30: UNKNOWN as of 2026-07-27. Exact maximum-period tables exist for small widths, and the checked structural results for Rule 30 do not prove an exponential subsequence of finite-ring periods.
Original CC0 asymptotic question extracted from exact finite-ring cycle data.