ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Fix an effective encoding of polynomials with integer coefficients in finitely many unknowns by finite strings over a finite alphabet (so that, for each n≥1n\ge 1, every P∈Z[x1,…,xn]P\in\mathbb{Z}[x_1,\dots,x_n] has a code, and the coefficients and the number of unknowns can be read off from the code). Let

D={ P∈⋃n≥1Z[x1,…,xn] : ∃ (a1,…,an)∈Zn  P(a1,…,an)=0 },D=\{\,P\in\textstyle\bigcup_{n\ge 1}\mathbb{Z}[x_1,\dots,x_n]\ :\ \exists\,(a_1,\dots,a_n)\in\mathbb{Z}^n\ \ P(a_1,\dots,a_n)=0\,\},

the set of polynomial Diophantine equations P=0P=0 that are solvable in rational integers.

Call a set SS of codes decidable if there is a Turing machine that halts on every input string and outputs 11 on inputs in SS and 00 on inputs not in SS.

Then the set of codes of members of DD is not decidable: there exists no algorithm which, given as input an arbitrary Diophantine equation with any number of unknowns and with rational integral coefficients, determines in a finite number of operations whether the equation is solvable in rational integers.

The same holds with Zn\mathbb{Z}^n replaced by Nn\mathbb{N}^n, i.e. for solvability in non-negative integers. Moreover, undecidability persists in a fixed one-parameter family: there is a polynomial p(a,x1,…,xk)p(a,x_1,\dots,x_k) with integer coefficients such that the set

{ a∈N : ∃ (x1,…,xk)∈Nk  p(a,x1,…,xk)=0 }\{\,a\in\mathbb{N}\ :\ \exists\,(x_1,\dots,x_k)\in\mathbb{N}^k\ \ p(a,x_1,\dots,x_k)=0\,\}

is not computable.

Equivalently, in terms of Diophantine sets: a set S⊆NmS\subseteq\mathbb{N}^m is called Diophantine if there are k≥0k\ge 0 and a polynomial PP with integer coefficients such that

S={ (a1,…,am)∈Nm : ∃ (x1,…,xk)∈Nk  P(a1,…,am,x1,…,xk)=0 };S=\{\,(a_1,\dots,a_m)\in\mathbb{N}^m\ :\ \exists\,(x_1,\dots,x_k)\in\mathbb{N}^k\ \ P(a_1,\dots,a_m,x_1,\dots,x_k)=0\,\};

every recursively enumerable subset of Nm\mathbb{N}^m is Diophantine.

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.