Universal theories of integers and the extended Bliznetsov hypothesis (Q1057849): Difference between revisions

It has been proved by \textit{A. P. Bel'tyukov} [Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova 60, 15-28 (1976; Zbl 0345.02035)] and \textit{L. Lipschitz} [The Diophantine Problem for \(+\), \(|\), - (Preprint 1975)] that the universal theory of the structure \(A_ 1=<{\mathbb{Z}};+,|,1>\), where \(|\) is the relation of divisibility (on the set \({\mathbb{Z}}\) of integers), is decidable. It has been proved by \textit{V. I. Mart'yanov} [Algebra Logika 16, 588-602 (1977; Zbl 0394.03038)] that the universal theory of the structure \(A_ 2=<{\mathbb{Z}};+,1,D>\), where D(x,y,z) denotes \(z=\pm GCD(x,y)\), is decidable. Yu. V. Matiyasevich remarked that the predicates D and \(\neg D\) are definable in \(A_ 1\) by universal formulas. In the present paper it is proved that the universal theory of the structure \(A_ 3=<{\mathbb{Z}};+,|,P,1>\), where P is the one-place predicate that selects the prime numbers, is decidable. This result is proved under the following assumption: Let \(g_ i(x)=a_ ix+b_ i\) \((i=1,...,n)\) be polynomials with relatively prime (integer) coefficients such that the numbers \(g_ i(t)\) are relatively prime to n! for a certain t. Then there exists an infinite sequence of integers \(t_ 1<...<t_ m<..\). such that all the numbers \(g_ i(t_ j)\) are prime. This assumption is satisfiable for \(n=1\) by virtue of the Dirichlet theorem. Therefore the following ''absolute'' result is true: The fragment of the universal theory of \(A_ 3\), in which each formula contains at most one occurrence of P, is decidable.