Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is deciding if a ring is a UFD always possible ?

Is there a simple proof of that ?

share|improve this question
1  
This makes no sense as it stands. A ring is an infinitary object; it can't be the input to a decision problem. You need to fix a specific way of describing rings with finite strings before you can ask about decidability. –  Chris Eagle Feb 10 '13 at 15:02
add comment

1 Answer 1

up vote 8 down vote accepted

A ring is always either a UFD or not.

How easily it is to determine whether it is or not depends entirely on which definition of the ring we have available. For example, consider the ring structure on $\mathbb Z^2$ defined by

$$ \langle a,b\rangle + \langle c,d\rangle = \langle a+c, b+d\rangle $$

$$ \langle a,b \rangle \times \langle c,d\rangle = \begin{cases} \langle ac-bd, bc+ad\rangle & \text{if the Riemann hypothesis is true} \\ \langle ac-5bd, bc+ad \rangle & \text{otherwise} \end{cases} $$

This ring is either isomorphic to $\mathbb Z[i]$ (which is UFD) or to $\mathbb Z[\sqrt{-5}]$ (which is not), but it is extremely difficult to determine which of these is the case.

There are families of definitions of rings where it is provably impossible for any procedure to correctly determine whether each of them defines a UFD. (In the above construction, replace "the Riemann hypothesis is true" with "Turing machine $n$ halts on the empty tape").

share|improve this answer
    
I think that $(\mathbb{Z},+_R,\times_R)$ is always a UFD. whether the riemann hypothesis is true or not –  Amr Feb 10 '13 at 15:10
    
$\mathbb{Z}[{\sqrt{-5}}]$ is not a UFD –  Amr Feb 10 '13 at 15:14
    
No its just my fault. At the beginning I thought that $f$ is a bijection between $\mathbb{Z}$ and itself, thus $(\mathbb{Z},+_R,\times_R)$ is isomorphic to $\mathbb{Z}$, hence a UFD –  Amr Feb 10 '13 at 15:16
    
Now I understand +1 –  Amr Feb 10 '13 at 15:17
1  
Unique factorization does not depend on any norm. And the point is exactly that the hardness deciding whether a ring is UFD depends intrinsically on how that ring is given to you. –  Henning Makholm Feb 10 '13 at 18:35
show 7 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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