Math.NumberTheory.DirichletCharacters

Implementation and enumeration of Dirichlet characters.

An absorbing semigroup

type OrZero a = Ap Maybe a

Similar to Maybe, but with different Semigroup and Monoid instances.

pattern Zero :: OrZero a

Ap Nothing

pattern NonZero :: a -> OrZero a

Ap (Just x)

orZeroToNum :: Num a => (b -> a) -> OrZero b -> a

Interpret an OrZero as a number, taking the Zero case to be 0.

Dirichlet characters

data DirichletCharacter (n :: Nat)

A Dirichlet character mod \(n\) is a group homomorphism from \((\mathbb{Z}/n\mathbb{Z})^*\) to \(\mathbb{C}^*\), represented abstractly by DirichletCharacter. In particular, they take values at roots of unity and can be evaluated using eval. A Dirichlet character can be extended to a completely multiplicative function on \(\mathbb{Z}\) by assigning the value 0 for \(a\) sharing a common factor with \(n\), using evalGeneral.

There are finitely many possible Dirichlet characters for a given modulus, in particular there are \(\phi(n)\) characters modulo \(n\), where \(\phi\) refers to Euler's totient function. This gives rise to Enum and Bounded instances.

Instances

KnownNat n => Bounded (DirichletCharacter n)

Defined in Math.NumberTheory.DirichletCharacters

Methods

minBound :: DirichletCharacter n

maxBound :: DirichletCharacter n

KnownNat n => Enum (DirichletCharacter n)

We define succ and pred with more efficient implementations than toEnum . (+1) . fromEnum.

Defined in Math.NumberTheory.DirichletCharacters

Methods

succ :: DirichletCharacter n -> DirichletCharacter n

pred :: DirichletCharacter n -> DirichletCharacter n

toEnum :: Int -> DirichletCharacter n

fromEnum :: DirichletCharacter n -> Int

enumFrom :: DirichletCharacter n -> [DirichletCharacter n]

enumFromThen :: DirichletCharacter n -> DirichletCharacter n -> [DirichletCharacter n]

enumFromTo :: DirichletCharacter n -> DirichletCharacter n -> [DirichletCharacter n]

enumFromThenTo :: DirichletCharacter n -> DirichletCharacter n -> DirichletCharacter n -> [DirichletCharacter n]

Eq (DirichletCharacter n)

Defined in Math.NumberTheory.DirichletCharacters

Methods

(==) :: DirichletCharacter n -> DirichletCharacter n -> Bool

(/=) :: DirichletCharacter n -> DirichletCharacter n -> Bool

Semigroup (DirichletCharacter n)

This Semigroup is in fact a group, so stimes can be called with a negative first argument.

Defined in Math.NumberTheory.DirichletCharacters

Methods

(<>) :: DirichletCharacter n -> DirichletCharacter n -> DirichletCharacter n

sconcat :: NonEmpty (DirichletCharacter n) -> DirichletCharacter n

stimes :: Integral b => b -> DirichletCharacter n -> DirichletCharacter n

KnownNat n => Monoid (DirichletCharacter n)

Defined in Math.NumberTheory.DirichletCharacters

Methods

mempty :: DirichletCharacter n

mappend :: DirichletCharacter n -> DirichletCharacter n -> DirichletCharacter n

mconcat :: [DirichletCharacter n] -> DirichletCharacter n

Construction

indexToChar :: forall n. KnownNat n => Natural -> DirichletCharacter n

Give the dirichlet character from its number. Inverse of characterNumber.

indicesToChars :: forall n f. (KnownNat n, Functor f) => f Natural -> f (DirichletCharacter n)

Give a collection of dirichlet characters from their numbers. This may be more efficient than indexToChar for multiple characters, as it prevents some internal recalculations.

characterNumber :: DirichletCharacter n -> Integer

We have a (non-canonical) enumeration of dirichlet characters.

allChars :: forall n. KnownNat n => [DirichletCharacter n]

List all characters for the modulus. This is preferred to using [minBound..maxBound].

fromTable :: forall n. KnownNat n => Vector (OrZero RootOfUnity) -> Maybe (DirichletCharacter n)

Attempt to construct a character from its table of values. An inverse to evalAll, defined only on its image.

Evaluation

eval :: DirichletCharacter n -> MultMod n -> RootOfUnity

For elements of the multiplicative group \((\mathbb{Z}/n\mathbb{Z})^*\), a Dirichlet character evaluates to a root of unity.

evalGeneral :: KnownNat n => DirichletCharacter n -> Mod n -> OrZero RootOfUnity

A character can evaluate to a root of unity or zero: represented by Nothing.

evalAll :: forall n. KnownNat n => DirichletCharacter n -> Vector (OrZero RootOfUnity)

In general, evaluating a DirichletCharacter at a point involves solving the discrete logarithm problem, which can be hard: the implementations here are around O(sqrt n). However, evaluating a dirichlet character at every point amounts to solving the discrete logarithm problem at every point also, which can be done together in O(n) time, better than using a complex algorithm at each point separately. Thus, if a large number of evaluations of a dirichlet character are required, evalAll will be better than evalGeneral, since computations can be shared.

Special Dirichlet characters

principalChar :: KnownNat n => DirichletCharacter n

Give the principal character for this modulus: a principal character mod \(n\) is 1 for \(a\) coprime to \(n\), and 0 otherwise.

isPrincipal :: DirichletCharacter n -> Bool

Test if a given Dirichlet character is prinicpal for its modulus: a principal character mod \(n\) is 1 for \(a\) coprime to \(n\), and 0 otherwise.

orderChar :: DirichletCharacter n -> Integer

Get the order of the Dirichlet Character.

Real Dirichlet characters

data RealCharacter n

A Dirichlet character is real if it is real-valued.

Instances

Eq (RealCharacter n)

Defined in Math.NumberTheory.DirichletCharacters

Methods

(==) :: RealCharacter n -> RealCharacter n -> Bool

(/=) :: RealCharacter n -> RealCharacter n -> Bool

isRealCharacter :: DirichletCharacter n -> Maybe (RealCharacter n)

Test if a given DirichletCharacter is real, and if so give a RealCharacter.

getRealChar :: RealCharacter n -> DirichletCharacter n

Extract the character itself from a RealCharacter.

toRealFunction :: KnownNat n => RealCharacter n -> Mod n -> Int

Evaluate a real Dirichlet character, which can only take values \(-1,0,1\).

jacobiCharacter :: forall n. KnownNat n => Maybe (RealCharacter n)

The Jacobi symbol gives a real Dirichlet character for odd moduli.

Primitive characters

data PrimitiveCharacter n

A Dirichlet character is primitive if cannot be induced from any character with strictly smaller modulus.

Instances

Eq (PrimitiveCharacter n)

Defined in Math.NumberTheory.DirichletCharacters

Methods

(==) :: PrimitiveCharacter n -> PrimitiveCharacter n -> Bool

(/=) :: PrimitiveCharacter n -> PrimitiveCharacter n -> Bool

isPrimitive :: DirichletCharacter n -> Maybe (PrimitiveCharacter n)

Test if a Dirichlet character is primitive.

getPrimitiveChar :: PrimitiveCharacter n -> DirichletCharacter n

Extract the character itself from a PrimitiveCharacter.

induced :: forall n d. (KnownNat d, KnownNat n) => DirichletCharacter d -> Maybe (DirichletCharacter n)

Induce a Dirichlet character to a higher modulus. If \(d \mid n\), then \(a \bmod{n}\) can be reduced to \(a \bmod{d}\). Thus, the multiplicative function on \(\mathbb{Z}/d\mathbb{Z}\) induces a multiplicative function on \(\mathbb{Z}/n\mathbb{Z}\).

>>> :set -XTypeApplications -XDataKinds
>>> chi = indexToChar 5 :: DirichletCharacter 45
>>> chi2 = induced @135 chi :: Maybe (DirichletCharacter 135)

makePrimitive :: DirichletCharacter n -> WithNat PrimitiveCharacter

This function also provides access to the new modulus on type level, with a KnownNat instance

data WithNat (a :: Nat -> Type) where

Wrapper to hide an unknown type-level natural.

Constructors

WithNat :: KnownNat m => a m -> WithNat a

Roots of unity

newtype RootOfUnity

A representation of roots of unity: complex numbers \(z\) for which there is \(n\) such that \(z^n=1\).

Constructors

RootOfUnity

Fields

• fromRootOfUnity :: Rational

  Every root of unity can be expressed as \(e^{2 \pi i q}\) for some rational \(q\) satisfying \(0 \leq q < 1\), this function extracts it.

Instances

Eq RootOfUnity

Defined in Math.NumberTheory.RootsOfUnity

Methods

(==) :: RootOfUnity -> RootOfUnity -> Bool

(/=) :: RootOfUnity -> RootOfUnity -> Bool

Show RootOfUnity

Defined in Math.NumberTheory.RootsOfUnity

Methods

showsPrec :: Int -> RootOfUnity -> ShowS

show :: RootOfUnity -> String

showList :: [RootOfUnity] -> ShowS

Semigroup RootOfUnity

This Semigroup is in fact a group, so stimes can be called with a negative first argument.

Defined in Math.NumberTheory.RootsOfUnity

Methods

(<>) :: RootOfUnity -> RootOfUnity -> RootOfUnity

sconcat :: NonEmpty RootOfUnity -> RootOfUnity

stimes :: Integral b => b -> RootOfUnity -> RootOfUnity

Monoid RootOfUnity

Defined in Math.NumberTheory.RootsOfUnity

Methods

mempty :: RootOfUnity

mappend :: RootOfUnity -> RootOfUnity -> RootOfUnity

mconcat :: [RootOfUnity] -> RootOfUnity

toRootOfUnity :: Rational -> RootOfUnity

Given a rational \(q\), produce the root of unity \(e^{2 \pi i q}\).

toComplex :: Floating a => RootOfUnity -> Complex a

Convert a root of unity into an inexact complex number. Due to floating point inaccuracies, it is recommended to avoid use of this until the end of a calculation. Alternatively, with the cyclotomic package, one can use polarRat 1 . fromRootOfUnity to convert to a cyclotomic number.

Debugging

validChar :: forall n. KnownNat n => DirichletCharacter n -> Bool

Test if the internal DirichletCharacter structure is valid.