Copyright  (c) 2018 Bhavik Mehta 

License  MIT 
Maintainer  Bhavik Mehta <bhavikmehta8@gmail.com> 
Safe Haskell  None 
Language  Haskell2010 
Implementation and enumeration of Dirichlet characters.
Synopsis
 type OrZero a = Ap Maybe a
 pattern Zero :: OrZero a
 pattern NonZero :: a > OrZero a
 orZeroToNum :: Num a => (b > a) > OrZero b > a
 data DirichletCharacter (n :: Nat)
 indexToChar :: forall n. KnownNat n => Natural > DirichletCharacter n
 indicesToChars :: forall n f. (KnownNat n, Functor f) => f Natural > f (DirichletCharacter n)
 characterNumber :: DirichletCharacter n > Integer
 allChars :: forall n. KnownNat n => [DirichletCharacter n]
 fromTable :: forall n. KnownNat n => Vector (OrZero RootOfUnity) > Maybe (DirichletCharacter n)
 eval :: DirichletCharacter n > MultMod n > RootOfUnity
 evalGeneral :: KnownNat n => DirichletCharacter n > Mod n > OrZero RootOfUnity
 evalAll :: forall n. KnownNat n => DirichletCharacter n > Vector (OrZero RootOfUnity)
 principalChar :: KnownNat n => DirichletCharacter n
 isPrincipal :: DirichletCharacter n > Bool
 orderChar :: DirichletCharacter n > Integer
 data RealCharacter n
 isRealCharacter :: DirichletCharacter n > Maybe (RealCharacter n)
 getRealChar :: RealCharacter n > DirichletCharacter n
 toRealFunction :: KnownNat n => RealCharacter n > Mod n > Int
 jacobiCharacter :: forall n. KnownNat n => Maybe (RealCharacter n)
 data PrimitiveCharacter n
 isPrimitive :: DirichletCharacter n > Maybe (PrimitiveCharacter n)
 getPrimitiveChar :: PrimitiveCharacter n > DirichletCharacter n
 induced :: forall n d. (KnownNat d, KnownNat n) => DirichletCharacter d > Maybe (DirichletCharacter n)
 makePrimitive :: DirichletCharacter n > WithNat PrimitiveCharacter
 data WithNat (a :: Nat > Type) where
 newtype RootOfUnity = RootOfUnity {}
 toRootOfUnity :: Rational > RootOfUnity
 toComplex :: Floating a => RootOfUnity > Complex a
 validChar :: forall n. KnownNat n => DirichletCharacter n > Bool
An absorbing semigroup
type OrZero a = Ap Maybe a Source #
Similar to Maybe, but with different Semigroup and Monoid instances.
orZeroToNum :: Num a => (b > a) > OrZero b > a Source #
Dirichlet characters
data DirichletCharacter (n :: Nat) Source #
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
Construction
indexToChar :: forall n. KnownNat n => Natural > DirichletCharacter n Source #
Give the dirichlet character from its number.
Inverse of characterNumber
.
indicesToChars :: forall n f. (KnownNat n, Functor f) => f Natural > f (DirichletCharacter n) Source #
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 Source #
We have a (noncanonical) enumeration of dirichlet characters.
allChars :: forall n. KnownNat n => [DirichletCharacter n] Source #
List all characters for the modulus. This is preferred to using [minBound..maxBound]
.
fromTable :: forall n. KnownNat n => Vector (OrZero RootOfUnity) > Maybe (DirichletCharacter n) Source #
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 Source #
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 Source #
A character can evaluate to a root of unity or zero: represented by Nothing
.
evalAll :: forall n. KnownNat n => DirichletCharacter n > Vector (OrZero RootOfUnity) Source #
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 Source #
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 Source #
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 Source #
Get the order of the Dirichlet Character.
Real Dirichlet characters
data RealCharacter n Source #
A Dirichlet character is real if it is realvalued.
Instances
Eq (RealCharacter n) Source #  
Defined in Math.NumberTheory.DirichletCharacters (==) :: RealCharacter n > RealCharacter n > Bool # (/=) :: RealCharacter n > RealCharacter n > Bool # 
isRealCharacter :: DirichletCharacter n > Maybe (RealCharacter n) Source #
Test if a given DirichletCharacter
is real, and if so give a RealCharacter
.
getRealChar :: RealCharacter n > DirichletCharacter n Source #
Extract the character itself from a RealCharacter
.
toRealFunction :: KnownNat n => RealCharacter n > Mod n > Int Source #
Evaluate a real Dirichlet character, which can only take values \(1,0,1\).
jacobiCharacter :: forall n. KnownNat n => Maybe (RealCharacter n) Source #
The Jacobi symbol gives a real Dirichlet character for odd moduli.
Primitive characters
data PrimitiveCharacter n Source #
A Dirichlet character is primitive if cannot be induced
from any character with
strictly smaller modulus.
Instances
Eq (PrimitiveCharacter n) Source #  
Defined in Math.NumberTheory.DirichletCharacters (==) :: PrimitiveCharacter n > PrimitiveCharacter n > Bool # (/=) :: PrimitiveCharacter n > PrimitiveCharacter n > Bool # 
isPrimitive :: DirichletCharacter n > Maybe (PrimitiveCharacter n) Source #
Test if a Dirichlet character is primitive.
getPrimitiveChar :: PrimitiveCharacter n > DirichletCharacter n Source #
Extract the character itself from a PrimitiveCharacter
.
induced :: forall n d. (KnownNat d, KnownNat n) => DirichletCharacter d > Maybe (DirichletCharacter n) Source #
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
>>>
chi = indexToChar 5 :: DirichletCharacter 45
>>>
chi2 = induced @135 chi
>>>
:t chi2
Maybe (DirichletCharacter 135)
makePrimitive :: DirichletCharacter n > WithNat PrimitiveCharacter Source #
This function also provides access to the new modulus on type level, with a KnownNat instance
Roots of unity
newtype RootOfUnity Source #
A representation of roots of unity: complex numbers \(z\) for which there is \(n\) such that \(z^n=1\).
RootOfUnity  

Instances
Eq RootOfUnity Source #  
Defined in Math.NumberTheory.RootsOfUnity (==) :: RootOfUnity > RootOfUnity > Bool # (/=) :: RootOfUnity > RootOfUnity > Bool #  
Show RootOfUnity Source #  
Defined in Math.NumberTheory.RootsOfUnity showsPrec :: Int > RootOfUnity > ShowS # show :: RootOfUnity > String # showList :: [RootOfUnity] > ShowS #  
Semigroup RootOfUnity Source #  This Semigroup is in fact a group, so 
Defined in Math.NumberTheory.RootsOfUnity (<>) :: RootOfUnity > RootOfUnity > RootOfUnity # sconcat :: NonEmpty RootOfUnity > RootOfUnity # stimes :: Integral b => b > RootOfUnity > RootOfUnity #  
Monoid RootOfUnity Source #  
Defined in Math.NumberTheory.RootsOfUnity mempty :: RootOfUnity # mappend :: RootOfUnity > RootOfUnity > RootOfUnity # mconcat :: [RootOfUnity] > RootOfUnity # 
toRootOfUnity :: Rational > RootOfUnity Source #
Given a rational \(q\), produce the root of unity \(e^{2 \pi i q}\).
toComplex :: Floating a => RootOfUnity > Complex a Source #
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.