[#P2840] A two-variable polynomial whose integer image is exactly the nonnegative integers

A flat mathematical diagram showing integer lattice points mapped to a nonnegative number line. — A schematic view of integer lattice points mapped to a nonnegative number line.

Problem. Does there exist a polynomial \(F\in\mathbb Q[X,Y]\) whose image on the full integer lattice is exactly \(\mathbb Z_{\ge 0}\)? Thus \(F(x,y)\) must be a nonnegative integer for every \((x,y)\in\mathbb Z^2\), and every nonnegative integer must equal \(F(x,y)\) for at least one integer pair.

1Context

The question asks whether two unrestricted integer parameters admit a single polynomial coding of the nonnegative integers without stray values. Degree bounds, positivity certificates, and exhaustive searches through normalized low-degree families can be retained as intermediate artifacts.

2Problem setup

Definition 1 (The image \(F(\mathbb Z^2)\). The image \(F(\mathbb Z^2)\) is the set \(\{F(x,y):x,y\in\mathbb Z\}\).

Definition 2 (A rational-coefficient polynomial may be integer-valued on \(\mathbb Z^2\) even when some coefficients are not integers). A rational-coefficient polynomial may be integer-valued on \(\mathbb Z^2\) even when some coefficients are not integers.

Definition 3 (Exact image). Exact image means both containment \(F(\mathbb Z^2)\subseteq\mathbb Z_{\ge0}\) and surjectivity onto every member of \(\mathbb Z_{\ge0}\).

Remark 1. The question asks whether two unrestricted integer parameters admit a single polynomial coding of the nonnegative integers without stray values. Degree bounds, positivity certificates, and exhaustive searches through normalized low-degree families can be retained as intermediate artifacts.

3What counts as a solution

Give an explicit \(F\in\mathbb Q[X,Y]\) and prove the equality \(F(\mathbb Z^2)=\mathbb Z_{\ge0}\), including integrality and nonnegativity on every integer pair.
Alternatively, prove unconditionally that no such polynomial exists. A conclusion conditional on Vojta's conjecture does not meet acceptance.

1Status

Current status (Current status and unresolved remainder). UNKNOWN as of 2026-07-31. The MathOverflow thread has no accepted construction. Rawson gives a conditional negative result using Vojta's conjecture, and the dated search found no unconditional existence or nonexistence theorem. Give an explicit \(F\in\mathbb Q[X,Y]\) and prove the equality \(F(\mathbb Z^2)=\mathbb Z_{\ge0}\), including integrality and nonnegativity on every integer pair.^[1]

1Packet records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 UNKNOWN as of 2026-07-31. The MathOverflow thread has no accepted construction. Rawson gives a conditional negative result using Vojta's conjecture, and the dated search found no unconditional existence or nonexistence theorem. Give an explicit \(F\in\mathbb Q[X,Y]\) and prove the equality \(F(\mathbb Z^2)=\mathbb Z_{\ge0}\), including integrality and nonnegativity on every integer pair.^[1] Relevance to this problem For polynomial image z2 nonnegative integers, pins the dated research frontier: UNKNOWN as of 2026-07-31. The MathOverflow thread has no accepted construction. Rawson gives a conditional negative result using Vojta's conjecture, and the dated search found no unconditional existence or nonexistence theorem. Give an explicit \(F\in\mathbb Q[X,Y]\) and prove the equality. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1 Details UNKNOWN as of 2026-07-31. The MathOverflow thread has no accepted construction. Rawson gives a conditional negative result using Vojta's conjecture, and the dated search found no unconditional existence or nonexistence theorem. A complete resolution must satisfy this condition: Give an explicit \(F\in\mathbb Q[X,Y]\) and prove the equality \(F(\mathbb Z^2)=\mathbb Z_{\ge0}\), including integrality and nonnegativity on every integer pair. Open full record →
	Trace	Reported
attempt · Route 1 Give an explicit \(F\in\mathbb Q[X,Y]\) and prove the equality \(F(\mathbb Z^2)=\mathbb Z_{\ge0}\), including integrality and nonnegativity on every integer pair.^[1] Relevance to this problem For A two-variable polynomial whose integer image is exactly the nonnegative integers, record polynomial-image-z2-nonnegative-integers-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: Give an explicit \(F\in\mathbb Q[X,Y]\) and prove the equality \(F(\mathbb Z^2)=\mathbb Z_{\ge0}\), including integrality and nonnegativity on every integer pair. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. Give an explicit \(F\in\mathbb Q[X,Y]\) and prove the equality \(F(\mathbb Z^2)=\mathbb Z_{\ge0}\), including integrality and nonnegativity on every integer pair. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. UNKNOWN as of 2026-07-31. The MathOverflow thread has no accepted construction. Rawson gives a conditional negative result using Vojta's conjecture, and the dated search found no unconditional existence or nonexistence theorem.

On 2026-07-27 the full MathOverflow thread, its eight answers, and answer comments were checked. Proposed expressions either use restricted domains, extra variables, nonpolynomial operations, or leave one of the two image inclusions unproved.
Rawson, arXiv:2403.09440, gives a negative answer conditional on Vojta's conjecture. The conjectural hypothesis prevents that paper from settling this record.
Classical pairing polynomials cover \(\mathbb Z_{\ge0}^2\), while this problem uses all of \(\mathbb Z^2\). Extending the domain can introduce negative or nonintegral values.
Trap: representing each nonnegative integer is only half of the target. Every integer input pair must also produce a nonnegative integer, and no positive surjectivity argument may silently restrict the signs of \(x\) and \(y\).

Recorded example 1. The Cantor polynomial \((X+Y)(X+Y+1)/2+Y\) pairs nonnegative integer inputs, but it takes unwanted values when \(X\) and \(Y\) range over all integers.

Recorded example 2. The polynomial \(X^2+Y^2\) is always nonnegative on integer pairs, but its image omits many nonnegative integers.

How the 2 records connectTyped relations and evidence flow

ProblemA two-variable polynomial whose integer image is exactly the nonnegative integers

Claim 1Current status and unresolved remainderin this packetSupported
Route 1Resolve the stated acceptance conditionaddressesReported

2See also

All nonnegative limits of normalized consecutive-prime gapsnumber theory
Decidability of positivity for linear recurrence sequencesnumber theory
Erdős Problem 152: isolated sums in Sidon setsnumber theory

How to cite

TheoremDB contributors, “A two-variable polynomial whose integer image is exactly the nonnegative integers,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/polynomial-image-z2-nonnegative-integers

This page as plain text: polynomial-image-z2-nonnegative-integers.md

This problem includes 2 records joined by 1 typed links, sourced from mathoverflow.net^[1], current as of July 31, 2026.

1References

Packet source. Polynomial representing all nonnegative integers, MathOverflow question 9731. Original CC0 restatement written after reviewing the question, all eight answers, their comments, and later conditional work. mathoverflow.net checked 2026-08-01. Original CC0 restatement written after reviewing the question, all eight answers, their comments, and later conditional work. ↗forum · discovery source · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow thread has no accepted construction. Rawson gives a conditional negative result using Vojta's conjecture, and the dated search found no unconditional existence or nonexistence theorem.Also cited at See dataset.references[0] for the exact external source and locator.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For A two-variable polynomial whose integer image is exactly the nonnegative integers: UNKNOWN as of 2026-07-27. The MathOverflow thread has no accepted construction. Rawson gives a conditional negative result using Vojta's conjecture, and the dated search found no unconditional existence or nonexistence theorem.Source named by the research packet.
Polynomial representing all nonnegative integers, MathOverflow question 9731, source checked for the TheoremDB status review (2026-07-31). Status evidence identified in the source record and checked at the linked publication. ↗preprint · primary source · arXiv:2403.09440, checked 2026-07-31 · checked 2026-07-31Source use: original summary.UNKNOWN as of 2026-07-27. The MathOverflow thread has no accepted construction. Rawson gives a conditional negative result using Vojta's conjecture, and the dated search found no unconditional existence or nonexistence theorem.Also cited at Full preprint relevant to A two-variable polynomial whose integer image is exactly the nonnegative integers.Source used to assess the problem's recorded status.For A two-variable polynomial whose integer image is exactly the nonnegative integers: UNKNOWN as of 2026-07-27. The MathOverflow thread has no accepted construction. Rawson gives a conditional negative result using Vojta's conjecture, and the dated search found no unconditional existence or nonexistence theorem.

Original CC0 textbook restatement.

[#P2840] A two-variable polynomial whose integer image is exactly the nonnegative integers

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

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

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance