Computable finite factorization domains

Abstract

In the ring of integers Z we can obtain the set of all the divisors of a given number using the Division Algorithm. Moreover, since there are finitely many divisors for each element, the Kronecker Method allows us to construct an algorithm to find the set of all divisors for polynomials in Z[x]. In both cases, the existence of these algorithms implies that the set of irreducible elements is computable relative to the copy of the structure. Other integral domains, like the quadratic extensions of Z, also have this property. In general, these domains are examples of Strongly Computable Strong Finite Factorization Domains (SCSFFD). In 2017, these structures were used to prove the existence of an integral domain where the set of irreducible elements is computable while the set of prime elements is not. Although differences are known between irreducible and prime elements in the algebraic context, this result shows how different they can be in computability context. Also, the authors provided conditions for which a Unique Factorization Domain (UFD) is a SCSFFD. However, being an UFD is not sufficient because there exists integral domains like Z[\sqrt{-5}] that are SCSFFD but not UFD. Our work completely classifies SCSFFD's in general by showing the existence of a computable norm that possess among other properties, being able to solve norm-form equations computably. This classification provides the intuition to extend further the notion of strongly computability to Computable Finite Factorization Domains in general.

En el anillo de los enteros Z podemos obtener el conjunto de todos los divisores de un número dado utilizando el algoritmo de la división. Más aún, dado que hay una cantidad finita de divisores para cada número, el método de Kronecker nos permite construir un algoritmo para encontrar el conjunto de todos los divisores de cualquier polinomio en Z[x]. En ambos casos, la existencia de estos algoritmos implica que el conjunto de los elementos irreducibles es computable relativo a la copia de la estructura. Otros dominios enteros, como las extensiones cuadráticas de Z, también tienen esta propiedad. En general, estos dominios son ejemplos de Dominios Enteros Fuertemente Computables de Factorización Finita Fuerte (SCSFFD). En el 2017, estas estructuras se utilizaron para demostrar la existencia de un dominio entero computable donde el conjunto de los irreducibles es computable mientras, que el conjunto de los elementos primos no lo es. Aunque se conocen diferencias entre estos conjuntos desde el contexto algebraico, este resultado muestra cuán diferentes también pueden ser desde el contexto de computabilidad. También, los autores proporcionaron condiciones para que un Dominio de Factorización Única (UFD) sea un SCSFFD. Sin embargo, ser un UFD no es una condición, pues dominios enteros como Z[\sqrt{-5}] son SCSFFD pero, no UFD. Nuestro trabajo clasifica completamente los SCSFFD's en general demostrando la existencia de una norma computable que una de sus propiedades es el poder resolver ecuaciones con normas computablemente. Esta clasificación provee la intuición de como extender la noción de ser fuertemente computable para los CFFD's.