Dirichlet characters

[Bodigrim]

https://en.wikipedia.org/wiki/Dirichlet_character

Despite of rather complicated applications, Dirichlet characters itself are a simple algebraic concept. It would be nice to have a data type, representing them, annotated by modulo on type level:

data DirichletCharacter (mod :: Nat) = TBD

Since Dirichlet characters of given modulo form a group by multiplication, we should be able to define correspondent Semigroup and Monoid instances. Moreover, it is useful to be able to enumerate all Dirichlet characters, which can be reflected in Haskell by Enum and Bounded instances. Finally, each character is a multiplicative function, so there is a mapping between DirichletCharacter and ArithmeticFunction from Math.NumberTheory.ArithmeticFunctions.

[b-mehta]

I'm happy to take this on. My current idea is to store a DirichletCharacter mod n as follows: A Dirichlet Character is determined by its values on generators of the group of units mod n. So for a given n we factorise it and find generators of its unit group using Moduli.PrimitiveRoot and the chinese remainder theorem. On these generators we can freely define the values of the Dirichlet character (using cyclotomic numbers to represent roots of unity).

data DirichletCharacter (mod :: Nat) = Generated (Map (Mod mod) Cyclotomic)

(with the data constructor hidden). Does this sound sensible?

I'd also like to make a change in Moduli.PrimitiveRoot: the function isPrimitiveRoot' can be optimised for large prime powers, determining primitive roots mod p^k (and 2p^k) for k > 1 should take roughly the same amount of time compared to determining primitive roots mod p^2.

[Bodigrim]

Since cyclotomic utilizes arithmoi for factorisation, we cannot reuse Cyclotomic type. Because otherwise it would cause a circular dependency between packages. This is not a big deal, we can represent a root of unity exp(2pim/n) as RootOfUnit { m :: Natural, n :: Natural } or something similar.

It would be desirable to have a unique representation for each Dirichlet character. From this point of view the ability to choose any primitive root looks like a redundant degree of freedom. IMHO we can assume that the smallest primitive root is always used and represent Dirichlet character just by a Map Natural Natural, where each key-value pair (m, n) means that the value of a character on the smallest primitive root modulo n is exp(2pim/n).

As a bonus level, one can represent moduli on type level, possibly include some proof that their product matches the order of a character, etc. Not sure which degree of type-foo is reasonable here.

---

It seems that there is no way to evaluate a Dirichlet character without computing discreet logarithms (#88). There is an unfinished PR #110. @b-mehta are you be interested to take it over, if @Taneb would not mind?

---

W.r.t. isPrimitiveRoot': sure, go ahead, possibly as a separate PR.

[b-mehta]

The root of unity representation sounds fine to me.

The choice of primitive roots is not necessarily as simple as you describe, since the modulus may not form a cyclic group of units. For instance, mod 35 the group of units is isomorphic (under CRT) to (Z/5Z) x (Z/7Z) and thus is generated by the pairs (2,1) and (1,3) since 2 generates (Z/5Z) and 3 generates (Z/7Z) (and are the smallest such). Using the CRT isomorphism, this gives that 22 and 31 together generate (Z/35Z)*. But, if the generator of (Z/5Z)* was chosen to be 3 instead, then CRT would give 8 as the corresponding generator of (Z/35Z)*. That said, we still have a canonical choice which should work fine. The map would represent something slightly different, but that idea would work well.

I'm not comfortable enough with type magic to work that out myself, but it does sound promising. We could possibly extend CyclicGroup to represent general multiplicative groups mod n for any n instead of just for certain n as well.

I'll have a look at that PR, I may implement a naive method for now in the meantime. I'm unsure about some of the difficulties described there, the Pollard algorithm should to my knowledge work just as well if the base is not a primitive root and the target value is a power of the base.

[b-mehta]

Once #130 is merged, I plan to work on this in parallel with #136.

[b-mehta]

This is implemented in #180, except for

there is a mapping between DirichletCharacter and ArithmeticFunction from Math.NumberTheory.ArithmeticFunctions

which I'll create an issue for, once #180 is merged.

[b-mehta]

I believe this issue can be closed by #180 now.