arithmoi-0.11.0.0: Efficient basic number-theoretic functions.

Math.NumberTheory.DirichletCharacters

Description

Implementation and enumeration of Dirichlet characters.

Synopsis

An absorbing semigroup

type OrZero a = Ap Maybe a Source #

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

pattern Zero :: OrZero a Source #

Ap Nothing

pattern NonZero :: a -> OrZero a Source #

Ap (Just x)

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

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

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
 Source # Instance detailsDefined in Math.NumberTheory.DirichletCharacters Methods Source # We define succ and pred with more efficient implementations than toEnum . (+1) . fromEnum. Instance detailsDefined in Math.NumberTheory.DirichletCharacters Methods Source # Instance detailsDefined in Math.NumberTheory.DirichletCharacters Methods Source # This Semigroup is in fact a group, so stimes can be called with a negative first argument. Instance detailsDefined in Math.NumberTheory.DirichletCharacters Methodsstimes :: Integral b => b -> DirichletCharacter n -> DirichletCharacter n # Source # Instance detailsDefined in Math.NumberTheory.DirichletCharacters Methods

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.

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

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

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

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

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.

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
 Source # Instance detailsDefined in Math.NumberTheory.DirichletCharacters Methods(==) :: RealCharacter n -> RealCharacter n -> Bool #(/=) :: RealCharacter n -> RealCharacter n -> Bool #

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

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

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

Instances
 Source # Instance detailsDefined in Math.NumberTheory.DirichletCharacters Methods

Test if a Dirichlet character is primitive.

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)


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

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

Wrapper to hide an unknown type-level natural.

Constructors

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

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$$.

Constructors

 RootOfUnity FieldsfromRootOfUnity :: RationalEvery 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
 Source # Instance detailsDefined in Math.NumberTheory.RootsOfUnity Methods Source # Instance detailsDefined in Math.NumberTheory.RootsOfUnity MethodsshowList :: [RootOfUnity] -> ShowS # Source # This Semigroup is in fact a group, so stimes can be called with a negative first argument. Instance detailsDefined in Math.NumberTheory.RootsOfUnity Methodsstimes :: Integral b => b -> RootOfUnity -> RootOfUnity # Source # Instance detailsDefined in Math.NumberTheory.RootsOfUnity Methodsmconcat :: [RootOfUnity] -> RootOfUnity #

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

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 Source #

Test if the internal DirichletCharacter structure is valid.