Universal theories of integers and the extended Bliznetsov hypothesis (Q1057849): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5534366 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4113824 / rank | |||
Normal rank |
Latest revision as of 17:37, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Universal theories of integers and the extended Bliznetsov hypothesis |
scientific article |
Statements
Universal theories of integers and the extended Bliznetsov hypothesis (English)
0 references
1983
0 references
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.
0 references
universal theories of integers
0 references
prime numbers
0 references