# P2696: Longest cycle of a nonlinear area-preserving map over F_1000003

- ID: `P2696`
- Reference: `kicked-map-million-prime-cycle`
- Page: https://theoremdb.org/statements/P2696
- Record maturity: Reviewed problem with recorded work

## Problem

Over \(\mathbb F_p\) with \(p=1000003\), let \(T(x,y)=(x+y+x^2,y+x^2)\), with both coordinates reduced modulo \(p\). Determine the length of the longest cycle of \(T\) on \(\mathbb F_p^2\).

### Remarks

- **Remark.** The map first applies the kick y'=y+x^2 and then the shear x'=x+y'.
- **Remark.** T is a permutation, with inverse x=x'-y' and y=y'-x^2.

### What counts as a solution

- Give a cycle of maximum length and a complete decomposition or certified exclusion showing that every remaining state lies on a no-longer cycle.

## Status

The state \((343233,119429)\) lies on a certified cycle of length 11,656,512, giving the current lower bound; the exact maximum cycle length over \(\mathbb F_{1000003}^2\) remains open. [2](#reference-2)

## Work

### Evidence for the current status

**Computation 1 (A certified cycle has length 11,656,512).** The state \((343233,119429)\) lies on a certified cycle of length 11,656,512, giving the current lower bound; the exact maximum cycle length over \(\mathbb F_{1000003}^2\) remains open.

For \(p=1{,}000{,}003\), direct iteration starting at
\[
(x_0,y_0)=(343233,119429)
\]
first returns to that state after
\[
\boxed{11{,}656{,}512}
\]
updates. The preceding state is \((223804,39277)\). It maps to the start, while no earlier positive iterate in the replay equals the start. The cycle begins
\[
(343233,119429)\mapsto(1524,658294)\mapsto(982388,980864).
\]
This improves the candidate record's lower bound of 2,732,283 by more than a factor of four.

The map is bijective because
\[
x=x'-y',\qquad y=y'-(x'-y')^2.
\]
Every starting state therefore lies on a cycle. A first return certifies the exact period of this witness without storing its 11,656,512 states. The ordered cycle trace, encoding each \((x,y)\) as two little-endian unsigned 64-bit integers, has FNV-1a digest `e1b26cc098a16596`.

This is a lower bound for the requested maximum. The phase space contains 1,000,006,000,009 states, and the 4,096-start search does not exclude a longer cycle elsewhere.

### Background and intake notes

Ten deterministic starting points already produce cycle lengths between 1 and 2732283, giving a reusable lower bound.

- Original intake status: Novelty remains unverified. No primary-source status audit was completed for this exact map and prime.
- The full permutation has 1000006000009 states. A segmented visited bitmap needs about 125 GB before compression, so cycle certificates should be sharded.
- Bijectivity rules out tails. Starting-point iteration must return to its start, which makes individual cycle lengths easy to certify.
- Linearizing the map or treating x^2 as a random kick gives heuristics, not orbit exclusions.

- Recorded example: The point (271828,161803) lies on a cycle of length 2732283.

### Other known results

- **Theorem 1** (established): An affine change of coordinates sends the kicked map to (a,b) -> (a^2+1-b,a). [2](#reference-2)

### Prior approaches

- **Route 1** (supported): Roberts and Vivaldi treat reversible Hénon reductions over finite fields; the focused search found no published decomposition at p=1000003. [2](#reference-2) [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): ISO C reproduces every sampled period, checks primality, verifies the record's first return, and hashes both the search records and cycle trace.
- **Artifact 2** (reproduced): Independent Python enumeration reproduces maximum periods 486 at p=101 and 6,724 at p=1009.

### Computational notes

- Exact full decompositions gave maximum cycle lengths 486 for p=101 and 6724 for p=1009. At p=1000003, direct return-to-start iteration gave lengths 1,2326224,1366428,1366428,1786139,1368770,184009,1039940,2732283,1849858 for the ten starts (0,0),(1,0),(0,1),(1,1),(2,3),(17,29),(12345,67890),(999983,314159),(271828,161803),(424242,777777).

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `kicked-map-million-prime-cycle`, 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. <a id="reference-1"></a>John A G Roberts and Franco Vivaldi, “A combinatorial model for reversible rational maps over finite fields”. Nonlinearity 22(8) (2009), 1965-1982. DOI 10.1088/0951-7715/22/8/011. Nonlinearity 22 (2009), 1965-1982 https://doi.org/10.1088/0951-7715/22/8/011
   - scholarly_publication; reference source; checked 2026-08-01
   - Source use: citation_only
   - For Longest cycle of a nonlinear area-preserving map over F_1000003, the reviewed source scope is Nonlinearity 22 (2009), 1965-1982. The packet makes no inference beyond that cited scope.
2. <a id="reference-2"></a>Signature of time-reversal symmetry in polynomial automorphisms over finite fields Nonlinearity 18 (2005), 2171-2192 https://doi.org/10.1088/0951-7715/18/5/015
   - Also cited at Exact 4096-start C search and full witness replay in kmmp-artifact-search-and-cycle-replay
   - Also cited at Direct affine conjugacy above; Roberts and Vivaldi, Signature of time-reversal symmetry in polynomial automorphisms over finite fields, Nonlinearity 18 (2005), 2171-2192
   - scholarly_publication; reference source
   - Source use: citation_only
   - Source named by the research packet.