The complexity of primes in computable unique factorization domains

DOI10.1215/00294527-2017-0024zbMATH Open1400.03061arXiv1407.2626OpenAlexW1937825932MaRDI QIDQ1750293FDOQ1750293

Authors: Damir D. Dzhafarov, Joseph R. Mileti 

Publication date: 18 May 2018

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Abstract: In many simple integral domains, such as $mathbbZ$ or $mathbbZ[i]$, there is a straightforward procedure to determine if an element is prime by simply reducing to a direct check of finitely many potential divisors. Despite the fact that such a naive approach does not immediately translate to integral domains like $mathbbZ[x]$ or the ring of integers in an algebraic number field, there still exist computational procedures that work to determine the prime elements in these cases. In contrast, we will show how to computably extend $mathbbZ$ in such a way that we can control the ordinary integer primes in any $P{i}_2^0$ way, all while maintaining unique factorization. As a corollary, we establish the existence of a computable UFD such that the set of primes is $P{i}_2^0$-complete in every computable presentation.

Full work available at URL: https://arxiv.org/abs/1407.2626

Recommendations

• Irreducibles and Primes in Computable Integral Domains
• Proper divisibility in computable rings
• Methods of prime factorization of elements in a Euclidean ring
• Factorization of prime ideal extensions in Dedekind domains
• How do elements really factor in \(\mathbb{Z}[\sqrt{-5}]\)?

zbMATH Keywords

primescomputability theorycomputable unique factorization domains

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Commutative rings defined by factorization properties (e.g., atomic, factorial, half-factorial) (13F15) Applications of logic to commutative algebra (13L05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Effective content of field theory
• Advanced Topics in Computional Number Theory
• Effective procedures in field theory
• Computable Algebra, General Theory and Theory of Computable Fields
• Countable algebra and set existence axioms
• Ideals in computable rings
• On the complexity of radicals in noncommutative rings
• Computable fields and Galois theory
• Rekursive Algebren mit Kettenbedingungen
• Title not available (Why is that?)
• Euclidean functions of computable Euclidean domains
• Basic algorithms for rational function fields
• Algorithms for Function Fields

Cited In (2)

• Irreducibles and Primes in Computable Integral Domains
• Proper divisibility in computable rings

This page was built for publication: The complexity of primes in computable unique factorization domains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1750293)