Rings of quadratic integers

[Bodigrim]

It would be nice to implement a basic support for quadratic integers in arithmoi. There is a proof of concept in Math.NumberTheory.Quadratic.GaussianIntegers and Math.NumberTheory.Quadratic.EisensteinIntegers modules.

1. Implement quadratic integers as a data type with two Integer fields and discriminant of the field D on the type level. One can copy the kind of discriminants from Numeric.QuadraticIrrational.SquareFree into arithmoi tree.

{-# LANGUAGE DataKinds      #-}
{-# LANGUAGE KindSignatures #-}

import GHC.TypeNats.Compat
import Numeric.QuadraticIrrational.SquareFree

data QuadraticInteger (d :: SquareFree)
  = QuadraticInteger { a :: Integer, b :: Integer }

2. Define Num (QuadraticInteger d) instance. This will require definitions of conjugation and norm as well.

3. For principal rings (D = −1, −2, −3, −7, −11, −19, −43, −67, −163) define a function primes, generating an infinite sequence of prime elements, ordered by norm. Use solveQuadratic to solve norm x = p and norm x = p^2 as described in this comment.

4. Define UniqueFactorisation instance for principal rings.

5. Define Euclidean instance for Euclidean rings.

[blperez01]

Currently have most of the functionality for this finished - just need to implement the unique factorization bit.

[Bodigrim]

A prototype can be found in #82.

[b-mehta]

Additionally, quadratic integers have periodic continued fractions so it would be nice to have this too - and then Pell equation solutions can be added. I have prototype code for continued fractions so I'm happy to help with that when appropriate.

[Bodigrim]

There are packages quadratic-irrational and pell already. However, the first one seems abandoned and I'd prefer to parametrise quadratic irrationals on type level, to avoid partial functions and allow Num instance.

[b-mehta]

Fair enough!

[Bodigrim]

Just for reference, I pushed some commits, reflecting my vision of quadratic rings, to https://github.com/ion1/quadratic-irrational/blob/c58c0fba08272c7e9fdff9fe8e338cff4d766ced/src/Numeric/QuadraticIrrational/Ring.hs

[rockbmb]

@Bodigrim I understand why you opened the issues you did over the past few months, things have been nicely progressing towards this issue. Point 2 seems the hardest, I agree. Plus for some values of D the quadratic integer ring won't be a Euclidean domain, or a Unique factorization domain. Tricky. I'll give it some more thought.

[Bodigrim]

Updated description to confirm with recent directions of development.

[Bodigrim]

@Multramate this is the issue I mentioned today.

[Multramate]

Thank you. It seems from reading the description above that this issue is meant to implement imaginary quadratic rings, as the real case would probably be harder to do e.g. there are probably infinitely many with unique factorisation. Would you reckon I should contribute by continuing from one of the prototypes, or think it over? I foresee unique factorisation to be done on a case-by-case basis, since there are only finitely many cases to consider:

instance UniqueFactorisation (ImQuadRing (-4)) where
  ...
instance UniqueFactorisation (ImQuadRing (-8)) where
  ...

Moreover, could you clarify the difficulty in doing (2)?

[Multramate]

Right - the discriminant as mentioned above refers to the d in Q(√d) and not the usual term used in number theory (at least in English), so it should be something like

instance UniqueFactorisation (ImQuadRing (-1)) where
  ...
instance UniqueFactorisation (ImQuadRing (-2)) where
  ...

Was worried for a bit since the quadratic ring is not unique given a fixed discriminant.

[Bodigrim]

It seems from reading the description above that this issue is meant to implement imaginary quadratic rings, as the real case would probably be harder to do e.g. there are probably infinitely many with unique factorisation.

I'd prefer to support both imaginary and real rings, under the same umbrella type, stratified by Nat on type-level. At least we can have a uniform Num instance for both, even if everything else will prove to be too difficult for real extensions.

Writing Num instance should be pretty straight-forward, I do not foresee any particular difficulties.

Would you reckon I should contribute by continuing from one of the prototypes, or think it over?

I would like to make it at least vaguely compatible with Math.NumberTheory.Quadratic.GaussianIntegers and Math.NumberTheory.Quadratic.EisensteinIntegers modules.

Not only feel free, but I encourage you to think over other aspects :)

Right - the discriminant as mentioned above refers to the d in Q(√d) and not the usual term used in number theory

You are right, sorry for confusion. I meant D as in wiki article.

Was worried for a bit since the quadratic ring is not unique given a fixed discriminant.

Yep, that is exactly the reason to stratify not by discriminant, but by its square-free part.