Is the `IntegralDomain` in `numeric-prelude` really an Integral domain?

3
votes

I am trying to model linear feedback shift registers in haskell. These can be modeled by polynomials over finite fields, so I am using numeric-prelude to get type classes that resemble mathematical algebraic structures more closely than those in the normal prelude.

I am by no means an expert in abstract algebra, so I have become a little confused about the IntegralDomain type class. The problem is that my book on abstract algebra (A book of abstract algebra by Charles C. Pinter) and the type classes seem to be conflicting with each other.

According to the book, the ring of polynomials over an integral domain, is itself an integral domain. Also, a ring of polynomials over a field is only an integral domain, but with the special(the fact that it is special is mentioned) property that the division algorithm holds.

That is, if F[x] is a polynomial over a field, then for a in F[x] and b!=0 in F[x], there exists q,r in F[x] such that b*q+r=a, and the degree of r is less than that of b.

The fact that this property is special to polynomials over a field, to me implies that it does not hold over any integral domain.

On the other hand, according to the type classes of numeric prelude, a polynomial over a field (that is zeroTestable) is also an IntegraldDomain. But according to the documentation, there are several laws of integralDomains, one of the being:

(a `div` b) * b + (a `mod` b) === a

http://hackage.haskell.org/packages/archive/numeric-prelude/0.4.0.1/doc/html/Algebra-IntegralDomain.html#t:C

This to me looks like the division algorithm, but then the division algorithm is true in any integral domain, including a polynomial over an integral domain contradiction my book. It is also worth noting that a polynomail over an integral domain does not have an instance for IntegralDomain in numeric-prelude(not that I can see at least, the fact that every type class is simply called C, make the documentation a little hard to read). So maybe the IntegralDomain in numeric prelude is an integral domain with the extra property that the division algorithm holds?

So is the IntegralDomain in numeric-prelude really an integral domain?

rubber duck debugging post script: While writing this question I got an idea for part of a possible explanation. Is it the requirement that "the degree of r is less than that of b." which makes the whole difference? That requirement is not in the numeric-prelude IntegralDomain. Then again, some of the other laws might imply this fact...

1
mathhaskell

1 Answers

3
votes

According to the book, a polynomial over an integral domain, is itself an integral domain.

That's not correctly phrased. The ring of polynomials over an integral domain is again an integral domain.

The ring of polynomials in one indeterminate over a field is even a principal ideal domain, as witnessed by the division algorithm, since every polynomial of degree 0 is a unit then.

In a general integral domain R, you have nonzero non-units, and if a is one, then you cannot write

X = q*a + r

with the degree of r smaller than that of a (which is 0).

Is it the requirement that "the degree of r is less than that of b." which makes the whole difference?

Precisely. That requirement guarantees that the division algorithm terminates. In a general integral domain, you can have a "canonical" choice of remainders modulo any fixed ring element, but the canonical remainder need not be "smaller" in any meaningful way, so an attempt to use the division algorithm need not terminate.

Then again, some of the other laws might imply this fact

None of the laws in Algebra.IntegralDomain imply that.

The law

(a+k*b) `mod` b === a `mod` b

is, I believe, hard to implement for a completely general integral domain, which could somewhat restrict the actual instances, but for something like Z[X] or R[X,Y] which are not PIDs, an instance is possible.