# P2548: Power-of-two solution counts for a finite-field functional equation

- ID: `P2548`
- Reference: `fibonacci-functional-equation-prime-count`
- Page: https://theoremdb.org/statements/P2548
- Record maturity: Reviewed problem with recorded work

## Problem

For a prime p, let \(N(p)\) be the number of functions \(f:\mathbb F_p\to\mathbb F_p\) satisfying \(f(f(x))=f(x)+x\) for every x. Whenever \(N(p)>0\), must \(N(p)\) be a power of two?

### Remarks

- **Remark.** Function composition is on the left side, while addition is field addition.
- **Remark.** Every solution is automatically injective, hence a permutation, because equal f-values force equal inputs in the equation.

### What counts as a solution

- Prove that every positive N(p) is a power of two, or give a prime p with a certified solution count having an odd factor.

## Status

All 46 positive counts among the 95 primes below 500 are powers of two; the orbit-cover model gives no general parity-factor proof yet. [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (The power-of-two claim is verified below 500 and unresolved in general).** All 46 positive counts among the 95 primes below 500 are powers of two; the orbit-cover model gives no general parity-factor proof yet.

For each prime \(p<500\), the exact orbit-cover computation determines \(N(p)\). Forty-six counts are positive and forty-nine vanish. Every positive count in this range is a power of two. The observed positive values have distribution
\[
1^1,\quad2^{30},\quad4^7,\quad8^3,\quad32^3,\quad512^1,\quad1024^1,
\]
where exponents record the number of primes attaining each value. The largest is \(N(461)=1024\).

The structural reduction in `ffe-claim-exact-orbit-cover` turns \(N(p)\) into a finite exact-cover count. Exact-cover counts can have odd factors in general. This audit found no additional involution or component theorem forcing the present counts to be powers of two for every prime. The universal question therefore remains unresolved in this entry.

### Background and intake notes

An exact-cover instance is canonical for each prime. Eligible orbit lists, forced orbits, and residual cover components are compact research records.

- Original intake status: Status not established. No literature search was performed. Iterative polynomial and permutation functional equations are established subjects.
- The attractive route assumes f is linear and solves \(a^2=a+1\).
- The obstruction appears at p=29, where two nonlinear solutions join the two linear ones. Iteration gives Fibonacci pairs, and the correct finite object is an exact cover by cycles of \((x,y)\mapsto(y,x+y)\).

- Recorded example: \(N(5)=1\), \(N(11)=2\), \(N(29)=4\), \(N(139)=8\), and \(N(199)=512\).

### Other known results

- **Theorem 1** (established): The graph of a solution is an invariant union of cycles of T(x,y)=(y,x+y), and the first-coordinate projections partition the field. [2](#reference-2)
- **Theorem 2** (established): The scalar map f(x)=a x works exactly when a^2-a-1=0; p=29 has two further nonlinear solutions. [2](#reference-2)
- **Computation 1** (reproduced): The census reproduces all candidate examples and finds powers of two at every prime with a solution. [2](#reference-2)

### Prior approaches

- **Route 1** (inconclusive): The located papers discuss continuous or analytic iterative equations; no finite-field orbit-cover count was found. [2](#reference-2) [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python enumerates every pair orbit, filters eligible cycles, and counts every exact cover. [2](#reference-2)

### Computational notes

- Exact enumeration of cycles of the Fibonacci map on \(\mathbb F_p^2\), followed by exact-cover counting on first coordinates, checked every prime p below 500. Every positive count was a power of two. The largest observed count was \(N(461)=1024\). The first nonlinear solutions occurred at p=29, and the positive counts at p=211 and p=281 were both 32. The search used integer residue arithmetic only.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `fibonacci-functional-equation-prime-count`, 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>Xiao Tang and Weinian Zhang, “Continuous solutions of a second order iterative equation”. arXiv:1803.03770 (2018). Xiao Tang and Weinian Zhang, Continuous solutions of a second order iterative equation, 2018, abstract and Introduction https://arxiv.org/abs/1803.03770
   - preprint; reference source; arXiv:1803.03770, version checked 2026-07-24; checked 2026-07-24
   - Source use: citation_only
   - For Power-of-two solution counts for a finite-field functional equation: Fibonacci iterative equations are studied over the reals. The located papers discuss continuous or analytic iterative equations; no finite-field orbit-cover count was found.
2. <a id="reference-2"></a>Stephen J. Greenfield and Roger D. Nussbaum, Dynamics of a Quadratic Map in Two Complex Variables, Journal of Differential Equations 169 (2001), 57-141, DOI 10.1006/jdeq.2000.3895, pages 80-81; search performed 2026-07-24. Stephen J. Greenfield and Roger D. Nussbaum, Dynamics of a Quadratic Map in Two Complex Variables, Journal of Differential Equations 169 (2001), 57-141, DOI 10.1006/jdeq.2000.3895, pages 80-81; search performed 2026-07-24 https://sites.math.rutgers.edu/~nussbaum/Pubs/dynamicsJDE.pdf
   - Also cited at Exact census in ffe-artifact-primes-below-500 and structural analysis performed 2026-07-24
   - Also cited at Independent graph-invariance and converse proof, 2026-07-24
   - Also cited at Direct substitution, quadratic reciprocity for 5, and the exact p=29 census
   - Also cited at Independent exact enumeration in ffe-artifact-primes-below-500, executed 2026-07-24
   - Also cited at Inline CPython standard-library computation executed on 2026-07-24
   - journal_article; primary source; PDF checked 2026-07-24; checked 2026-08-01
   - Source use: original_summary
   - For Power-of-two solution counts for a finite-field functional equation: The located papers discuss continuous or analytic iterative equations; no finite-field orbit-cover count was found.
   - Source named by the research packet.