9
$\begingroup$

Let $R$ be a ring such that all of its elements have a finite number of divisors, ie $\forall r\in R\, |\{x\in R: x|r\}|<\infty$. Then we can decide whether a polynomial in $R[t]$ is reducible through Kronecker's method.

Even in the ring $\mathbb{Q}[x,\sqrt{x},\sqrt[4]{x},...]$, where $x$ has an infinite number of divisors, it is easy to list any polynomial's possible factors, and reducibility is decidable.

Is there a ring for which the reducibility of a polynomial is undecidable?

Is there a countable ring with computable ring operations and decidable equality for which the reducibility of a polynomial is undecidable?

$\endgroup$
  • 5
    $\begingroup$ I would ask for a countable ring with computable ring operations and decidable equality but undecidable reducibility. $\endgroup$ – Matt F. Jan 21 at 16:02
  • $\begingroup$ Yes that is a good suggestion @Matt F.. Btw, where could I find an examplu of ring with uncomputable operations? $\endgroup$ – Lucio Tanzini Jan 21 at 16:10
  • 1
    $\begingroup$ Consider $R=\mathbb{Z}[\{x_i\}]/\{x_i^2-f(i)\}$, where $f$ is a total function that grows uncomputably fast. In the presentation where the elements of $R$ are listed as elements of $\mathbb{Z}[\{x_i\}]$, the ring operations are computable but equality is not decidable. In the presentation where the elements of $R$ are listed as elements of $\mathbb{Z}+\mathbb{Z}x_1+\mathbb{Z}x_2+\cdots$ (allowing only linear powers of the $x$'s), the equality is decidable but the ring operations (esp multiplication) are not computable. For a genuinely computable presentation of a ring you want both. $\endgroup$ – Matt F. Jan 21 at 19:25
15
$\begingroup$

Yes, but the answer is a bit unsatisfying. This answer is a summary of the very nice paper Computable Fields and Galois Theory, Russel Miller, Notices of the AMS, 2008.

First of all, if one could not even compute with the elements of the ring $R$ at all, it would be unclear what it would mean for factorization to be computable. The usual solution is to talk about "computable rings", meaning a countable (or finite) ring $R$ where the elements are indexed by integers and the operations of addition and multiplication are given by computable functions.

The following is an example of a computable field in which factorization is not decidable: Let $p_n$ be the $n$-th prime and let $T_n$ be the $n$-th Turing machine and let $K = \mathbb{Q}(\sqrt{p_n} \ : \ T_n \ \mbox{halts})$. Given any element $\theta$ of $K$, there is a finite expression which witnesses that $\theta$ is in $K$: namely, the algebraic expression for $\theta$ in terms of finitely many $p_n$'s and a transcript of the ruunning of the corresponding Turing machines. This can be made into a proof that $K$ is computable, in particular (in response to Matt F.'s comment) there is no issue with testing equality. However, $x^2 - p_n$ is reducible iff $T_n$ halts, so we cannot test reducibility.

The fields one normally meets in life do not have this issue. Reducibility is computable over $\mathbb{Q}$, $\mathbb{R}$ and over finite fields. If reducibility is computable over $k$, then it is computable over $k(t)$ and over $k[t]/f(t)$ for $f$ irreducible. That already covers the most obvious fields you know.

Searching for "computable fields" turns up a fair bit of recent research.

$\endgroup$
  • 2
    $\begingroup$ +1. Let me add to this that there's a surprising (to me at least) computable algebra fact here: while this undecidability result prevents the usual construction of the algebraic closure from being computable in the appropriate sense it is still the case that every computable field has a computable algebraic closure (Frolich-Shepherdson if I recall correctly). The subtlety here is around the phrase "algebraic closure:" for every computable field $F$ there is a computable field $G$ such that $G$ is isomorphic to the algebraic closure of $F$, but no embedding $F\rightarrow G$ need be computable! $\endgroup$ – Noah Schweber Jan 21 at 16:29
  • $\begingroup$ Your ring $K$ is not computable? Why? $\endgroup$ – Mark Sapir Jan 21 at 16:54
  • 1
    $\begingroup$ @MarkSapir It is computable, but factorization is not decidable. I think that is what I wrote? $\endgroup$ – David E Speyer Jan 21 at 17:36
  • 1
    $\begingroup$ I do not understand steps 2 and on. You said it is all written in some published paper? $\endgroup$ – Mark Sapir Jan 21 at 20:13
  • 2
    $\begingroup$ I see. The problem is that the definitions of "computable ring" used by Miller and you are very weak. The ring $K$ is not recursive because there is no way to tell if $\sqrt{p}$ is in $K$. Of course if one uses recursively enumerable sets instead of recursive, it is easy to build all sorts of examples. $\endgroup$ – Mark Sapir Jan 21 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.