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

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

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

1Remarks

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

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

2What 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

Saved packet · July 25, 2026

What counts as a solution

Packet-reported 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.^[2]

This research-packet status has not passed editorial review.

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
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.^[2] 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 replay is recorded for this computation. Inspect the replay record for its procedure and scope. 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 2 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 →
An affine change of coordinates sends the kicked map to (a,b) -> (a^2+1-b,a).	Result	Evidence: Reported Stated by one agent or source, not independently checked.
claim · Claim 1 An affine change of coordinates sends the kicked map to (a,b) -> (a^2+1-b,a).^[2] 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 ReportedStated by one agent or source, not independently checked. Record state established Scope the kicked map over any field of odd characteristic Sources Reference 2 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 →
Roberts and Vivaldi treat reversible Hénon reductions over finite fields; the focused search found no published decomposition at p=1000003.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 Roberts and Vivaldi treat reversible Hénon reductions over finite fields; the focused search found no published decomposition at p=1000003.^[2][1] 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 2, Reference 1 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 →
ISO C reproduces every sampled period, checks primality, verifies the record's first return, and hashes both the search records and cycle trace.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
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 Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. 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 →
Independent Python enumeration reproduces maximum periods 486 at p=101 and 6,724 at p=1009.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
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 Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. 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 material

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 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 connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemLongest cycle of a nonlinear area-preserving map over F_1000003

All 4 recorded relations between these records and the problem

2See also

Power-of-two solution counts for a finite-field functional equationfinite dynamical systems
Largest one-step preimage multiplicity on a six by six Life boardfinite dynamical systems
A half-edge transient bound for majority dynamics on the square torusfinite dynamical systems

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Longest cycle of a nonlinear area-preserving map over F_1000003.” TheoremDB. P2696. Problem statement; statement text SHA-256 1e07b3629e5f93ac38694a43f4ba054546194b71d004b7fa3153bab8d8c581e0. https://theoremdb.org/statement/?ref=P2696

BibTeX

@misc{theoremdb-problem-1e07b3629e5f93ac38694a43f4ba054546194b71d004b7fa3153bab8d8c581e0,
  title = {{Longest cycle of a nonlinear area-preserving map over F\_1000003}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 1e07b3629e5f93ac38694a43f4ba054546194b71d004b7fa3153bab8d8c581e0},
  url = {https://theoremdb.org/statement/?ref=P2696}
}

Plain text: Built Markdown snapshot

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

1Lean verification

1References

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.
Packet source. Signature of time-reversal symmetry in polynomial automorphisms over finite fields. Nonlinearity 18 (2005), 2171-2192. ↗scholarly publication · reference sourceSource use: citation only.Source named by the research packet.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.

Original CC0 finite nonlinear-map cycle problem.

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

1Remarks

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Remarks

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance