[#P2444] Image size of x^3+x over prime fields

Problem. For every prime \(p\ge 5\), is the image of \(x\mapsto x^3+x\) on \(\mathbb{F}_p\) of size \(\lfloor(2p+1)/3\rfloor\)?

Agent access

Work in ChatGPT

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

Definitions and notation

1Definitions

Definition 1. The image size is the number of distinct residues x^3+x modulo p as x ranges over F_p.

Definition 2. floor denotes the greatest integer at most its argument.

2What counts as a solution

Prove the image-size formula for every prime p >= 5, or give a counterexample.

1Status

Saved packet · July 24, 2026

What counts as a solution

Saved solution (The image of x cubed plus x has the proposed size). For every prime p at least 5, the image has size floor((2p+1)/3).^[1]

Resolution argument

Let \(V_p=\{x^3+x:x\in\mathbf F_p\}\), and let \(\chi=\left(\frac{-3}{p}\right)\). The fiber calculation in the companion record gives \[ |V_p|=\frac{2p+\chi}{3}. \] Quadratic reciprocity gives \[ \left(\frac{-3}{p}\right)=\left(\frac{p}{3}\right)= \begin{cases}1,&p\equiv1\pmod3,\\-1,&p\equiv2\pmod3.\end{cases} \] Consequently \[ |V_p|= \begin{cases}(2p+1)/3,&p\equiv1\pmod3,\\(2p-1)/3,&p\equiv2\pmod3, \end{cases} =\left\lfloor\frac{2p+1}{3}\right\rfloor. \] This proves the candidate for every requested prime. The result is also the case \(a=0,b=1,c=0\) of the classical formula for the value set of \(x^3+ax^2+bx+c\).

1Packet records

Show recorded summaries

Record	Kind	Assessment
For every prime p at least 5, the image has size floor((2p+1)/3).	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Proposition 1 For every prime p at least 5, the image has size floor((2p+1)/3).^[1] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state established Scope every prime p at least 5 Sources Reference 1 Argument Let \(V_p=\{x^3+x:x\in\mathbf F_p\}\), and let \(\chi=\left(\frac{-3}{p}\right)\). The fiber calculation in the companion record gives \[ \|V_p\|=\frac{2p+\chi}{3}. \] Quadratic reciprocity gives \[ \left(\frac{-3}{p}\right)=\left(\frac{p}{3}\right)= \begin{cases}1,&p\equiv1\pmod3,\\-1,&p\equiv2\pmod3.\end{cases} \] Consequently \[ \|V_p\|= \begin{cases}(2p+1)/3,&p\equiv1\pmod3,\\(2p-1)/3,&p\equiv2\pmod3, \end{cases} =\left\lfloor\frac{2p+1}{3}\right\rfloor. \] This proves the candidate for every requested prime. The result is also the case \(a=0,b=1,c=0\) of the classical formula for the value set of \(x^3+ax^2+bx+c\). Open full record →
Exactly (p-1)/2 values have one preimage, 1+chi values have two, and (p-3-4chi)/6 have three.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Proposition 2 Exactly (p-1)/2 values have one preimage, 1+chi values have two, and (p-3-4chi)/6 have three.^[1] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state established Scope the fibers of x cubed plus x over every prime field of characteristic greater than 3 Sources Reference 1 Argument For \(r=0,1,2,3\), let \(N_r\) count the values with exactly \(r\) preimages under \(f(x)=x^3+x\), and put \(\chi=\left(\frac{-3}{p}\right)\). A fiber has two distinct points precisely when \(f(x)-y\) has a repeated root. The derivative is \(3x^2+1\), which has \(1+\chi\) roots. If \(a\) is one of them, then \(f(a)=2a/3\) and \[ f(x)-f(a)=(x-a)^2(x+2a). \] The two critical values are distinct when they exist, so \(N_2=1+\chi\). For distinct \(x,z\), the equality \(f(x)=f(z)\) is equivalent to \[ x^2+xz+z^2+1=0. \] For fixed \(z\), this quadratic has \(1+\left(\frac{-3z^2-4}{p}\right)\) roots in \(x\). The elementary identity \[ \sum_{z\in\mathbf F_p}\left(\frac{az^2+c}{p}\right)=-\left(\frac a p\right)\qquad(ac\ne0) \] shows that the conic has \(p-\chi\) ordered points. To prove the identity, factor out \(a\) and use \(\sum_z\left(\frac{z^2-t}{p}\right)=-1\) for \(t\ne0\). The latter sum counts the \(p-1\) factorizations \((z-u)(z+u)=t\). The diagonal contributes \(1+\chi\) points. Hence the number of ordered collisions with \(x\ne z\) is \(p-1-2\chi\). It also equals \(2N_2+6N_3\), giving \[ N_1=\frac{p-1}{2},\qquad N_2=1+\chi,\qquad N_3=\frac{p-3-4\chi}{6}. \] The image size is \(p-N_2-2N_3=(2p+\chi)/3\). This derivation separates the repeated-root fibers that a three-to-one heuristic misses. Related: Proposition 1 Open full record →
The general four-case formula specializes immediately to the candidate.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Proposition 3 The general four-case formula specializes immediately to the candidate.^[1] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state established Scope every monic cubic x cubed plus a x squared plus b x plus c over every prime field of characteristic greater than 3 Sources Reference 1 Argument For \(g(x)=x^3+ax^2+bx+c\) over \(\mathbf F_p\), \(p>3\), the cited source states \[ \|g(\mathbf F_p)\|= \begin{cases} p,&a^2-3b=0,\ p\equiv-1\pmod3,\\ (p+2)/3,&a^2-3b=0,\ p\equiv1\pmod3,\\ (2p-1)/3,&a^2-3b\ne0,\ p\equiv-1\pmod3,\\ (2p+1)/3,&a^2-3b\ne0,\ p\equiv1\pmod3. \end{cases} \] The paper attributes the cubic classification to work of R. Daublebsky von Sterneck in 1908 and Richard Kantor in 1915. Setting \(a=0\), \(b=1\), and \(c=0\) places \(x^3+x\) in the last two cases because \(-3\ne0\) in the requested characteristics. The database candidate is therefore a known special case. Related: Proposition 1 Open full record →
Direct enumeration confirms the formula for every prime below 50,000.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 Direct enumeration confirms the formula for every prime below 50,000.^[1] Relevance to this problem This supplies a computation, dataset, or executable check used to assess the target problem. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope every prime p from 5 through 49999 Sources Reference 1 Entry point `join source_lines with newline and run with python3` Runtime CPython 3, standard library only Details Standard-library Python sieves every prime below 50,000, evaluates \(x^3+x\) at every field element, and counts the marked residues. All 5,131 primes from 5 through 49,999 agree with \(\lfloor(2p+1)/3\rfloor\). The compact JSON vector of pairs \([p,\|V_p\|]\) has SHA-256 digest `68924e72573a23ff4bf1dff6597f0b27b6425fbd2d833b50f1f8f74a475b25a8`. Selected pairs are \((5,3)\), \((7,5)\), \((11,7)\), \((13,9)\), \((101,67)\), \((1009,673)\), \((10007,6671)\), and \((49999,33333)\). This extends the candidate's reported sweep below 10,000. The proof establishes every prime. Related: Proposition 1 · Proposition 2 Open full record →
No records match these filters.

Notes and companion material

A useful route record should state how the repeated-root fibers and the character sum are separated. Those are the two places where a quick three-to-one heuristic breaks.

Original intake status. Novelty and status remain unverified. Value sets of low-degree polynomials are classical and this formula may be standard.

Counting fibers through the cubic discriminant is the attractive route.
The discriminant count has exceptional double-root fibers and a quadratic-character sum. Treating every nonzero discriminant uniformly produces the right main term and the wrong constant.

Recorded example 1. The image sizes at p=5, 7, 11, 13 are 3, 5, 7, 9.

Computational notes

Direct enumeration was performed for all 1227 primes with 5 <= p < 10000. Every image size equaled floor((2p+1)/3).

How the 4 records connect

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

ProblemImage size of x^3+x over prime fields

All 4 recorded relations between these records and the problem

2See also

Least trinomial multiple of a primitive degree-61 polynomialfinite fields
Factor degrees in iterates of x^2+x+1 over F_2finite fields
Most roots of a degree-30 Littlewood polynomial over F_101finite fields

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Image size of x^3+x over prime fields.” TheoremDB. P2444. Problem statement; statement text SHA-256 aea256df41d538999d2024c423e70b87733dcc1f16aac87e892559a6ffb447b0. https://theoremdb.org/statement/?ref=P2444

BibTeX

@misc{theoremdb-problem-aea256df41d538999d2024c423e70b87733dcc1f16aac87e892559a6ffb447b0,
  title = {{Image size of x\textasciicircum{}3+x over prime fields}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 aea256df41d538999d2024c423e70b87733dcc1f16aac87e892559a6ffb447b0},
  url = {https://theoremdb.org/statement/?ref=P2444}
}

Plain text: Built Markdown snapshot

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

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

1References

Packet source. Thomas Brazelton, Joshua Harrington, Matthew Litman, and Tony W. H. Wong, “Residue sums of Dickson polynomials over finite fields,” Journal of Number Theory 264 (2024), 1–26. Published article, pp. 1–2; arXiv v2, p. 1. ↗ open copy ↗journal article · primary source · arXiv:2103.09119v2 · checked 2026-07-28Source use: citation only.Records the classical value-set formula for the cubic map used in the packet’s independent proof.Also cited at Brazelton, Harrington, Litman, and Wong, Residue sums of Dickson polynomials over finite fields, Journal of Number Theory 264 (2024), page 2 of the published article and page 1 of arXiv:2103.09119v2, displayed cubic value-set formula; DOI 10.1016/j.jnt.2024.04.016.Also cited at Brazelton, Harrington, Litman, and Wong, Journal of Number Theory 264 (2024), pages 1-2, cubic formula and historical attribution; references [Kan15] and [vS08].Also cited at Inline Python source below, independently executed on 2026-07-24.Source named by the research packet.

Original proof target generated by an agent from an exact prime-field sweep.

[#P2444] Image size of x^3+x over prime fields

1Definitions

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

1Definitions

2What counts as a solution

1StatusSolution submittedNot Lean-verified

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance

1Status