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

A mathematical schematic of Longest cycle of a nonlinear area-preserving map over F_1000003. — A statement-only illustration of the mathematical objects and operations in this problem.

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\).

1Context

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

2Definitions

Definition 1 (The map first applies the kick y'=y+x^2 and then the shear x'=x+y'). The map first applies the kick y'=y+x^2 and then the shear x'=x+y'.

Definition 2 (T). T is a permutation, with inverse x=x'-y' and y=y'-x^2.

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

1Status

Current status (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.^[1]

1Records

Record	Kind	Assessment
	Result	Reproduced
claim · Computation 1 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.^[1] Relevance to this problem For Longest cycle of a nonlinear area-preserving map over F_1000003, record kmmp-claim-certified-cycle-11656512 (“A certified cycle has length 11,656,512”) records a bound, answer, status fact, or structural consequence. The record states: 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. Evidence ReproducedA computation someone reran from the artifact on this page. Record state established Scope the permutation T(x,y)=(x+y+x^2,y+x^2) on the full state space F_p squared at p=1000003 Sources Reference 1 Details 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. Open full record →
	Result	Established
claim · Theorem 1 An affine change of coordinates sends the kicked map to (a,b) -> (a^2+1-b,a).^[1] Relevance to this problem For Longest cycle of a nonlinear area-preserving map over F_1000003, record kmmp-claim-henon-conjugacy (“The map is a reversible area-preserving Hénon map”) records a bound, answer, status fact, or structural consequence. The record states: An affine change of coordinates sends the kicked map to (a,b) -> (a^2+1-b,a). Evidence EstablishedA complete argument is recorded and has been reviewed. Scope the kicked map over any field of odd characteristic Sources Reference 1 Argument Set \[ a=x+1,\qquad b=x-y+1. \] Then the kicked map becomes \[ H(a,b)=(a^2+1-b,a), \] the quadratic area-preserving Hénon form. Its Jacobian determinant is one. The coordinate swap \(R(a,b)=(b,a)\) is a reversing involution because \[ RHR=H^{-1},\qquad H^{-1}(a,b)=(b,b^2+1-a). \] Equivalently, \(H=(HR)R\) is a product of two involutions. Each involution has \(p\) fixed points over \(\mathbb F_p\) when \(p\) is odd. Roberts and Vivaldi study finite-field reductions of this reversible Hénon class and the resulting cycle statistics. Their asymptotic random-involution model has natural period scale \(p\) in this case. The certified period here is about \(11.656477p\). That model supplies context and no finite upper bound for this particular prime. Related: Route 1 Open full record →
	Trace	Supported
attempt · Route 1 Roberts and Vivaldi treat reversible Hénon reductions over finite fields; the focused search found no published decomposition at p=1000003.^[1][2] Relevance to this problem For Longest cycle of a nonlinear area-preserving map over F_1000003, record kmmp-attempt-literature-audit (“The literature supplies a cycle-statistics model rather than this finite maximum”) documents a concrete method, search boundary, or failed route. The record states: Roberts and Vivaldi treat reversible Hénon reductions over finite fields; the focused search found no published decomposition at p=1000003. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope published finite-field cycle results relevant to the exact Hénon-form map and the modulus p=1000003 Sources Reference 1, Reference 2 What happened Roberts and Vivaldi's 2005 paper studies reductions of polynomial automorphisms of the plane over finite fields, with detailed experiments for the area-preserving Hénon map. Their 2009 paper proves a universal cycle-length distribution for the corresponding random-involution model and explains why reversible maps differ from random permutations. The affine conjugacy in this fixture places the present map directly in that setting. The papers give asymptotic statistics and experiments at other primes. The focused title, formula, and citation search found no decomposition or longest-cycle value for this exact map at \(p=1{,}000{,}003\). The global maximum therefore remains open in this entry. Related: Computation 1 Open full record →
	Artifact	Reproduced
artifact · Artifact 1 ISO C reproduces every sampled period, checks primality, verifies the record's first return, and hashes both the search records and cycle trace. Relevance to this problem For Longest cycle of a nonlinear area-preserving map over F_1000003, record kmmp-artifact-search-and-cycle-replay (“Exact 4,096-start search and record-cycle replay”) supplies evidence or a replay used to check the packet. The record states: ISO C reproduces every sampled period, checks primality, verifies the record's first return, and hashes both the search records and cycle trace. Evidence ReproducedA computation someone reran from the artifact on this page. Record state available Scope all 4096 SplitMix64-generated starting states with indices 0 through 4095 at p=1000003, followed by every state in the record cycle Run `cc -O3 -std=c11 -Wall -Wextra -pedantic search.c -o search && ./search` Runtime ISO C11; reproduced with Apple clang at -O3 Details Starting with the 64-bit seed `6b69636b65646d61`, two consecutive SplitMix64 outputs reduced modulo \(p\) give each sampled \((x,y)\). The program computes the first return for every index 0 through 4095. It hashes each four-tuple \((i,x,y,\ell)\), with all fields encoded as little-endian unsigned 64-bit integers. The final search digest is `f6dd5727b5ac0b50`. The record advances at indices 0, 6, 66, and 234, with periods 4,135,917; 4,897,828; 8,743,054; and 11,656,512. The search was reproduced in four consecutive 1,024-index batches. Carrying the FNV state across the batch boundaries gave cumulative digests `f2906540ab7a26e8`, `b69b9b82a87dbe89`, `d042bfc2f97c70da`, and `f6dd5727b5ac0b50`. The witness replay checks every intermediate state against the start. Selected states are \((6790,451908)\) at time 100, \((693931,696803)\) at time 1,000, \((494671,78205)\) at time 1,000,000, \((385219,565829)\) at time 5,000,000, and \((42331,466469)\) at time 10,000,000. Time 11,656,511 gives the predecessor \((223804,39277)\), and the next update returns to the start. The six canonical stdout lines, including their terminating line feeds, have SHA-256 digest `8eeeee9564e2e5badd30d7d6825dc6e6ba5784592362b457ca464197b2b68180`. Related: Computation 1 Open full record →
	Artifact	Reproduced
artifact · Artifact 2 Independent Python enumeration reproduces maximum periods 486 at p=101 and 6,724 at p=1009. Relevance to this problem For Longest cycle of a nonlinear area-preserving map over F_1000003, record kmmp-artifact-small-prime-decompositions (“Complete small-prime cycle decompositions”) supplies evidence or a replay used to check the packet. The record states: Independent Python enumeration reproduces maximum periods 486 at p=101 and 6,724 at p=1009. Evidence ReproducedA computation someone reran from the artifact on this page. Record state available Scope the complete state spaces for the same map at p=101 and p=1009 Entry point `Execute code with python3` Runtime CPython 3.9 or newer, standard library only Details A visited bitmap decomposes every state into disjoint cycles. At \(p=101\), the map has 101 cycles and maximum period 486, first encountered at \((0,9)\). At \(p=1009\), it has 1,011 cycles and maximum period 6,724, first encountered at \((0,134)\). These reproduce both calibration values in the candidate record. For each prime, the program hashes the sorted `period:multiplicity` histogram with SHA-256. The digests are `c9ced7c56ae551bbc25d3be50b00610336cef8b561c9ffb5ff00a0ba57e2aeb6` and `404eaecab6ff5302910b9986568d2362856415376fcb3b49c4b30efe972f50f3`. Related: Artifact 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. OPEN as of 2026-08-01. 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.

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.
Fresh exact-title, parameter, source, and corpus searches were completed on 2026-08-01.

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

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

How the 5 records connectTyped relations and evidence flow

ProblemLongest cycle of a nonlinear area-preserving map over F_1000003

Computation 1A certified cycle has length 11,656,512in this packetReproduced
Artifact 1Exact 4,096-start search and record-cycle replayverifiesReproduced
Artifact 2Complete small-prime cycle decompositionstestsReproduced
Route 1The literature supplies a cycle-statistics model rather than this finite maximuminformsSupported
Theorem 1The map is a reversible area-preserving Hénon mapinformsEstablished

2See also

A half-edge transient bound for majority dynamics on the square torusfinite dynamical systems
Power-of-two solution counts for a finite-field functional equationfinite dynamical systems
Rank log-concavity for symmetric binary matrices through order fiftyfinite fields

How to cite

TheoremDB contributors, “Longest cycle of a nonlinear area-preserving map over F_1000003,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/kicked-map-million-prime-cycle

This page as plain text: kicked-map-million-prime-cycle.md

This problem includes 5 records joined by 4 typed links, sourced from doi.org^[1], current as of July 25, 2026.

1References

Packet source. John A. G. Roberts and Franco Vivaldi, Signature of time-reversal symmetry in polynomial automorphisms over finite fields, Nonlinearity 18 (2005), 2171-2192. Finite-field reversible Hénon dynamics. ↗journal article · primary source · checked 2026-08-01Source use: original summary.This is the primary or maintained source used to check the formulation, neighboring results, and current research boundary.Also cited at Nonlinearity 18 (2005), 2171-2192.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.Source named by the research packet.
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. ↗scholarly publication · reference source · checked 2026-08-01Source 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.

Original CC0 finite nonlinear-map cycle problem.

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

1Context

2Definitions

3What counts as a solution

1Status

1Records

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Definitions

3What counts as a solution

1Status

1Records

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance