Note on Quantifier Prefixes Over Diophantine Equations (Q3707986)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3933027
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Note on Quantifier Prefixes Over Diophantine Equations |
scientific article; zbMATH DE number 3933027 |
Statements
Note on Quantifier Prefixes Over Diophantine Equations (English)
0 references
1986
0 references
Hilbert irreducibility
0 references
residue classes
0 references
density
0 references
0.9047214388847352
0 references
0.7821672558784485
0 references
0.7792778015136719
0 references
0.771462619304657
0 references
0.7630325555801392
0 references
This paper gives a negative answer to 2 questions of \textit{J. P. Jones} [ibid. 27, 403-410 (1981; Zbl 0472.03034)]: For \(P_ 1,P_ 2,Q_ 1,Q_ 2\in {\mathbb{Z}}[x,y]\), do either of the following 2 conditions hold? \[ (1)\quad \forall P_ 1\exists Q_ 1: \{x\in {\mathbb{N}}| \forall y\in {\mathbb{N}},\quad P_ 1(x,y)>0\}=\{x\in {\mathbb{N}}| \exists z\in {\mathbb{N}},\quad Q_ 1(x,z)=0\}, \] \[ (2)\quad \forall P_ 2\exists Q_ 2: \{x\in {\mathbb{N}}| \forall y\in {\mathbb{N}},\quad P_ 2(x,y)\neq 0\}=\{x\in {\mathbb{N}}| \exists z\in {\mathbb{N}},\quad Q_ 2(x,z)=0\}. \] (1) implies (2), since, for \(P_ 1:=P^ 2_ 2\), \(P_ 2\neq 0\) if and only if \(P_ 1>0\). We refute (2), and hence (1), when \(P_ 2:=x-y^ 2\), that is, when the set \(\{\) \(x\in {\mathbb{N}}|\) \(\forall y\in {\mathbb{N}}\), \(P_ 2(x,y)\neq 0\}\) is the set of non-squares. We do this in 2 ways, first using a theorem of R. M. Robinson, then using Hilbert's irreducibility theorem. If the answer to either of Jones' questions had been positive, then Jones could have given an algorithm for deciding which binary Diophantine equations have integral solutions (for Diophantine equations in 9 or more variables, Matijasevič had shown that there is no such algorithm).
0 references