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.

Any Euclidean domain satisfies the division "algorithm":

For any $x,d$ there exists $q,r$ such that $x = qd+r$ with $\sigma(r)<\sigma(d)$ or $\sigma(r)=0$

With $\sigma$ a "size function."

I'm wondering if what I would call an algorithm (i.e. a discrete series of steps to get to an answer) exists for division. Specifically:

Suppose +, -, and * are defined in some Euclidean Domain. Is there a mechanism to find $x/y$ (beyond brute force)?

Repeated subtraction works in the integers, but not the polynomials, and this was my first thought. (I realize that I'm ignoring the problem of how to do subtraction in the ring, which is quite similar.)

share|improve this question
4  
Asking algorithmic questions about set-theoretically general structures like rings brings with it some difficulties. For instance, as you point out, $R = \mathbb{C}[t]$ is a Euclidean Domain. In order to have a division "algorithm", first we need to input a polynomial with complex coefficients, so we need to be able to input complex numbers. But there are uncountably many complex numbers, most of which are "uncomputable" by anyone's definition, so already this is somewhat problematic. (I'm not saying these problems are insurmountable, which is why this is a comment not an answer...) –  Pete L. Clark Sep 29 '11 at 15:54

1 Answer 1

up vote 6 down vote accepted

Various complexity results are known about Euclidean domains. For example, Downey and Kach: Euclidean functions of computable Euclidean domains shows that there is a computable Euclidean domain having no (finite or transfinitely-valued) computable Euclidean function. Further there is a computable Euclidean domain with a computable Euclidean function but whose units are noncomputable, and there is a computable Euclidean domain with neither computable units nor a computable Euclidean function. See the paper and its references for much more.

share|improve this answer

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.