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 (non-canonical) 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 real-valued.
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 -XDataKinds
>>>
chi = indexToChar 5 :: DirichletCharacter 45
>>>
chi2 = induced @135 chi :: 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.