search

Bodigrim / arithmoi

Number theory: primes, arithmetic functions, modular computations, special sequences
http://hackage.haskell.org/package/arithmoi
MIT License
148 stars 40 forks source link

Cubic reciprocity law #155

Open Bodigrim opened 5 years ago

Bodigrim commented 5 years ago

It may be fun to extend Math.NumberTheory.Moduli.Jacobi to cover not only quadratic reciprocity, but cubic as well.

Quadratic reciprocity symbol or Jacobi symbol answers the question whether an equation x^2 = n (mod m) has any solutions. Similarly, cubic residue symbol answers whether x^3 = n (mod m) has solutions.

The values of Jacobi symbol are units of real integers (+ zero), while the values of cubic symbol are units of Eisenstein integers.

When this will be implemented, we can proceed to modular cubic roots (similar to Math.NumberTheory.Moduli.Sqrt) and eventually solve cubic and quartic modular equations in Math.NumberTheory.Moduli.Equations.

Steps to implement:

  1. Define data CubicSymbol = Zero | Omega | OmegaSquare | One and define cubicSymbol :: EisensteinInteger -> EisensteinInteger -> CubicSymbol in accordance to the definition of cubic residue character.

  2. Define the modular cube root in accordance to one of the algorithms in New Cube Root Algorithm. The API should be designed similar to Math.NumberTheory.Moduli.Sqrt.

  3. Develop an algorithm to solve cubic modular equations (similar to the real case) and implement it as Math.NumberTheory.Moduli.Equations.solveCubic.

  4. Develop an algorithm to solve quartic modular equations (similar to the real case) and implement it as Math.NumberTheory.Moduli.Equations.solveCubic.

hgsipiere commented 4 years ago

I was looking into this issue out of curiosity and noticed that with cubic/quartic residue characters the values are roots of unity. Would it make sense to move roots of unity out of Dirichlet characters or to just reference the Dirichlet character module if implementing this?

Edit: Ignore this, can just use EisensteinIntegers module

Bodigrim commented 4 years ago

Moving them out is a good idea, I think.

b-mehta commented 4 years ago

I agree roots of unity probably belong somewhere other than in Dirichlet characters, but cubic/quartic symbols should have a more specific type than root of unity. It would be nice to include a conversion function CubicResidueSymbol -> RootOfUnity or something similar instead.

hgsipiere commented 4 years ago

I completely agree, representing them as Eisenstein Integers looks nice with stuff like CubicResidueSymbol ω (or anything else more specific). It was an oversight, I think they are seperate issues.

Edit: I think you can only do CubicResidueSymbol -> Maybe RootOfUnity because of the 0 case.

Bodigrim commented 4 years ago

CubicSymbol is also fine from my perspective. But representing cubic symbols directly as EisensteinInteger is probably painful because of the lack of exhausting pattern matching.

IMO we can iron out precise API details later, having more stuff at hand.