# P2812: Positive cycle entropy for finite cyclic Rule 30

- ID: `P2812`
- Reference: `rule-30-positive-cycle-entropy`
- Page: https://theoremdb.org/statements/P2812
- Record maturity: Reviewed problem with recorded work

## 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\)?

### Problem setup

- **Definition.** 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\).
- **Remark.** The limsup inequality is equivalent to the existence of constants \(c>0\) and infinitely many \(n\) with \(M_n\ge2^{cn}\).
- **Remark.** The displayed Boolean formula fixes the Rule 30 convention and the orientation of the neighborhood.

### What 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.

## 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. Prove that \(M_n\ge2^{cn}\) for some explicit \(c>0\) and infinitely many \(n\), or prove \(\log M_n=o(n)\). [1](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (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)\).

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.

A complete resolution must satisfy this condition: Prove that \(M_n\ge2^{cn}\) for some explicit \(c>0\) and infinitely many \(n\), or prove \(\log M_n=o(n)\).

### Background and intake notes

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.

- Original intake status: 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.
- 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: The exact maxima at widths 4, 7, 14, 16, and 17 are respectively 8, 63, 1428, 6016, and 10846.

### Open directions

- **Route 1** (reported): Prove that \(M_n\ge2^{cn}\) for some explicit \(c>0\) and infinitely many \(n\), or prove \(\log M_n=o(n)\). [1](#reference-1)

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `rule-30-positive-cycle-entropy`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1 entry has incomplete source metadata. Each affected row names the fields that still need editorial review.

1. <a id="reference-1"></a>Status assessment source See dataset.references[0] for the exact external source and locator. https://doi.org/10.1016/j.tcs.2022.12.018
   - Also cited at Editorial research route recorded 2026-07-31
   - scholarly_publication; reference source
   - Source metadata incomplete: publication-style citation.
   - Source use: citation_only
   - Source used to assess the problem's recorded status.
   - Source named by the research packet.
2. <a id="reference-2"></a>Rapid left expansivity, a commonality between Wolfram's Rule 30 and powers of p/q. OEIS entry A334497, checked 2026-08-01. Entry definition, data, comments, and linked references relevant to Positive cycle entropy for finite cyclic Rule 30; checked 2026-08-01. https://oeis.org/A334497
   - reference_database; reference source; checked 2026-07-31
   - Source use: citation_only
   - 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.