Constructing fields of fractions using Haskell

This time I will write about a way to construct fields from integral domains using Haskell. It will use the structures from my previous post. But first a comment on that post. When discussing integral domains I said that it was hard to test the property that there should be no zero divisors. A friend of mine asked me why I did not test the contrapositive instead. That is, I should use \phi \rightarrow \psi \equiv \neg \psi \rightarrow \neg \phi to convert xy = 0 \rightarrow x = 0 \lor y = 0 into x \neq 0 \land y \neq 0 \rightarrow xy \neq 0 which should be easier to test…

Now let’s consider how to turn integral domains into fields. This construction is called field of fractions and is denoted by Quot(A) where A is an integral domain. It is a generalization of the construction of \mathbb{Q} from \mathbb{Z} . An element of Quot(A) is a pair (a,b) with a,b \in A and b \neq 0 . This pair should be interpreted as a \over b . This could be represented straight forwardly in Haskell as a pair. But I want to work with reduced expressions, that is I want the extra constraint that gcd(a,b)=1 . To guarantee this I need to consider a more specialised structure than integral domains called GCD domains. This is a structure in which any pair of nonzero elements has a greatest common divisor. This is represented as:

class IntegralDomain a => GCDDomain a where
  gcd' :: a -> a -> (a,a,a)

Here gcd’ take nonzero a and b and compute (g,x,y) such that g=gcd(a,b) , a = gx and b = gy . That is, it computes the greatest common divisor of a and b plus witnesses that it actually divides both a and b . This can be specified as:

propGCD :: (GCDDomain a, Eq a) => a -> a -> Property
propGCD a b = a /= zero && b /= zero ==> a == g <*> x && b == g <*> y
  where
  (g,x,y) = gcd' a b

Now we are ready to represent the field of fractions over a GCD domain:

newtype GCDDomain a => FieldOfFractions a = F (a,a)

Now A can be embedded in Quot(A) by

toFieldOfFractions :: GCDDomain a => a -> FieldOfFractions a
toFieldOfFractions a = F (a,one)

Since we are working over a GCD domain we can compute reduced expressions:

reduce :: (GCDDomain a, Eq a) 
       => FieldOfFractions a -> FieldOfFractions a
reduce (F (a,b)) | b == zero = error "reduce: Division by 0"
                 | a == zero = F (zero,one)
                 | otherwise = F (x,y)
  where
  (g,x,y) = gcd' a b

Using this we can define a function from Quot(A) to A.

fromFieldOfFractions :: (GCDDomain a, Eq a) => FieldOfFractions a -> a
fromFieldOfFractions x 
  | b' == one = a'
  | otherwise = error "fromFieldOfFractions: Denominator is not 1"
    where F (a',b') = reduce x 

To test equality the underlying ring need to have decidable equality (i.e. it should be discrete). {a \over b} \in Quot(A) and {c \over d} \in Quot(A) are equal iff ad = bc which give:

instance (GCDDomain a, Eq a) => Eq (FieldOfFractions a) where
  (F (a,b)) == (F (c,d)) = a <*> d == b <*> c

We can also implement all the operations needed for showing that the constructed field of fractions is in fact a field.

instance (GCDDomain a, Eq a) => Ring (FieldOfFractions a) where
  (F (a,b)) <+> (F (c,d)) = reduce (F (a <*> d <+> c <*> b,b <*> d))
  (F (a,b)) <*> (F (c,d)) = reduce (F (a <*> c,b <*> d))
  neg (F (a,b))           = reduce (F (neg a,b))
  one                     = toFieldOfFractions one
  zero                    = toFieldOfFractions zero

instance (GCDDomain a, Eq a) => CommutativeRing (FieldOfFractions a)
instance (GCDDomain a, Eq a) => IntegralDomain (FieldOfFractions a)

instance (GCDDomain a, Eq a) => Field (FieldOfFractions a) where
  inv (F (a,b)) | a == zero = error "inv: Can't invert 0"
                | b == zero = error "inv: Division by 0"
                | otherwise = reduce $ F (b,a)

Finally we can construct \mathbb{Q} from \mathbb{Z} by just writing:

type Q = FieldOfFractions Z

*Algebra.Q> quickCheck (propField :: Q -> Q -> Q -> Property)
+++ OK, passed 100 tests.

*Algebra.Q> 3*(1/2)^3 :: Q
3/8

Where the last computation is possible by adding suitable Num, Fractional and Show instances. I really like this way of constructing fields. For instance I used this to implement the field of rational functions using my implementation of polynomials.

Of course I don’t need the GCDDomain constraint for any function except fromFieldOfFractions, so it would be very easy to generalize this for any integral domain. But it proved useful when implementing a proof for constructing interesting Prüfer domains, so I added the constraint everywhere. It also look more appealing with reduced expressions and I have only had to consider \mathbb{Q} and the field of rational functions so far.

Finally I would like to write a little about GCD domains. It is possible to prove that they are non-Noetherian analogues of unique factorization domains (UFDs), that is, one gets UFDs by taking GCD domains and adding the ascending chain condition on ideals. The reason for not having Noetheriannity is that it gives constructive versions of classical notions. So instead of UFDs we get GCD domains and instead of PIDs we get Bézout domains in constructive mathematics. The problem with Noetheriannity is quite intricate and I have not fully grasped it yet. As far as I know there is no consensus about what a constructive version should be. I plan to write more about this in some upcoming posts.

About these ads

2 Responses to Constructing fields of fractions using Haskell

  1. Jan Christiansen says:

    I have to admit that I do not know any of the structures that you have presented here. But out of curiosity would it be possible to use a kind of continued fractions instead of reduced fractions?

    • mortberg says:

      No, I don’t think continued fractions are relevant in this setting. But they seem to have applications in other parts of abstract algebra, namely algebraic number theory, but I don’t know much about this… :(

      Anyway, I want to find the smallest field that an integral domain can be embedded in. So I need to add inverse elements for all elements that don’t already have that. To do this I construct the pairs and consider the equivalence classes under the equality I have given here. So this means that 2/4 and 1/2 belong to the same equivalence class. In a gcd domain I can simplify things a little bit by collapsing the equivalence classes into only one representative value for each class and I don’t see any way that continued fractions could be relevant for this construction.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: