# Cyclotomics.jl

Cyclotomics package implements cyclotomic numbers which are sums of roots of unity. The coefficients of the sum are in general taken from a ring. E.g. the imaginary unit is represented by `E(4)`

, the fourth root of `1`

, while algebraic number `(1 + √5)/2`

can be written exactly as `E(5) + E(5)^4`

.

In summary the package implements

- Cyclotomic numbers as structs based on
`SparseVector`

s, - basic arithmetic on those: module and ring structures that take advantage of (lazy) normalization,
- a few predicates (e.g.
`isreal`

) and conversions to`float`

/`Rational`

/`Complex`

numbers, - Zumbroich basis (by three different methods), thread-safe and memoized.

## Example uses

```
julia> using Cyclotomics
julia> e = E(45) # 45-th root of unity
ζ₄₅
julia> isone(E(5)^5) # 5-th root of unity to power 5 gives the unit
true
```

### Normal forms

Consider the following element

```
julia> w = e + e^2 + e^8 + e^11 + e^17 + e^26 + e^29 + e^38 + e^44
ζ₄₅ + ζ₄₅² + ζ₄₅⁸ + ζ₄₅¹¹ + ζ₄₅¹⁷ + ζ₄₅²⁶ + ζ₄₅²⁹ + ζ₄₅³⁸ + ζ₄₅⁴⁴
```

Since the vector space spanned by `45`

-th roots of unity is of dimension less than `45`

not all roots are needed to express a cyclotomic number of degree `45`

. For example the following is a different way to write `w`

:

```
julia> x = E(45) + E(45)^5 # or E(45) + E(9)
ζ₄₅ + ζ₄₅² + ζ₄₅⁸ + ζ₄₅¹¹ + ζ₄₅¹⁷ + ζ₄₅²⁶ + ζ₄₅²⁹ + ζ₄₅³⁸ + ζ₄₅⁴⁴
julia> x == w
true
```

And that's 9-th root of unity in its normal form (i.e. written in the canonical basis):

```
julia> E(45, 5) # == E(45)^5 == E(9)
-ζ₉⁴-ζ₉⁷
```

### Computing with cyclotomics

We define module structures with different coefficients

```
julia> E(45, 5)
-ζ₉⁴-ζ₉⁷
julia> 3E(45, 5)
-3*ζ₉⁴ -3*ζ₉⁷
julia> 2.0E(45, 5) - E(9)
-1.0*ζ₉⁴ -1.0*ζ₉⁷
```

as well as conversions to standard julia types

```
julia> complex(2.0x)
3.5126250237210965 + 1.5639214212932075im
julia> float(E(3))
ERROR: InexactError: float(Float64, 1*E(3)^1)
Stacktrace:
[1] float(#unused#::Type{Float64}, α::Cyclotomic{Int64, SparseArrays.SparseVector{Int64, Int64}})
@ Cyclotomics ~/.julia/dev/Cyclotomics/src/cycl.jl:168
[2] float(α::Cyclotomic{Int64, SparseArrays.SparseVector{Int64, Int64}})
@ Cyclotomics ~/.julia/dev/Cyclotomics/src/cycl.jl:171
[3] top-level scope
@ REPL[15]:1
julia> complex(E(3))
-0.4999999999999998 + 0.8660254037844387im
julia> float(E(3) + E(3)^2)
-1.0
julia> Rational(E(3) + E(3)^2)
-1//1
```

When possible we try to promote to Cyclotomics

```
julia> E(5) + im
-ζ₂₀ + ζ₂₀⁴-ζ₂₀⁹-ζ₂₀¹³-ζ₂₀¹⁷
julia> (1.0+2im) + E(5)
-2.0*ζ₂₀ -1.0*ζ₂₀⁸ -2.0*ζ₂₀⁹ -1.0*ζ₂₀¹² -2.0*ζ₂₀¹³ -1.0*ζ₂₀¹⁶ -2.0*ζ₂₀¹⁷
julia> (1.0+2.0im) - 2E(4)
1.0
julia> typeof(ans)
Cyclotomic{Float64, SparseArrays.SparseVector{Float64, Int64}}
julia> isreal((1.0+2.0im) - 2E(4))
true
```

However cyclotomic numbers can store non-rational algebraic numbers:

```
julia> z = E(5)^2+E(5)^3
ζ₅² + ζ₅³
julia> isreal(z)
true
julia> Rational(z)
ERROR: InexactError: Rational( 1*E(5)^2 + 1*E(5)^3)
Stacktrace:
[1] Rational{Int64}(α::Cyclotomic{Int64, SparseArrays.SparseVector{Int64, Int64}})
@ Cyclotomics ~/.julia/dev/Cyclotomics/src/cycl.jl:192
[2] Rational(α::Cyclotomic{Int64, SparseArrays.SparseVector{Int64, Int64}})
@ Cyclotomics ~/.julia/dev/Cyclotomics/src/cycl.jl:195
[3] top-level scope
@ none:1
julia> z ≈ (-1-sqrt(5))/2
true
```

### Low level constructors

One can also construct `Cyclotomic`

directly from a vector, which is then used as the underlying vector of coefficients. Here these are dense, while by default `Cyclotomic`

uses sparse storage.

```
julia> Cyclotomic([0,1,0,0,0])
ζ₅
julia> Cyclotomic([0,0,1,0,0])
ζ₅²
julia> Cyclotomic([1,1,1,1,1]) # the sum of all roots == 0
0
```

`Cyclotomic`

s: constructors and low level access

`Cyclotomics.Cyclotomic`

— Type`Cyclotomic(coeffs::AbstractVector)`

Element of `length(coeffs)`

-th cyclotomic field with coefficients stored as `coeffs`

.

To access the internals of a cyclotomic use API functions:

`conductor`

- the conductor of a cyclotomic, i.e. the`n`

used currently for storage. This might not be the minimal embeding field of a cyclotomic.`coeffs`

- returns a reference to the underlying vector containing the coefficients.`getindex`

/`setindex!`

- use`α[i]`

to access the coefficient at`i`

-th power of the root of unity (in a circular fashion).`values`

/`exponents`

- paired iterators over*non zero*coefficients/exponents corresponding to*non-zero*coefficients`normalform!`

- bring a cyclotomic to its unique representation as given by Zumbroich basis (also available in non-modifying form).

Iteration over non-zero coefficients in `Cyclotomic`

is provided by `exps_coeffs`

which produces pairs `(exp, coeff)`

of exponent and corresponding coefficient.

`Cyclotomics.E`

— Function`E(n[, i=1])`

Return the `i`

-th power of `n`

-th root of unity with sparse vector as storage.

`Cyclotomics.conductor`

— Function`conductor(α::Cyclotomic)`

Return the conductor, i.e. the degree of cyclotomic field `α`

belongs to.

`Cyclotomics.exponents`

— Function`exponents(α::Cyclotomic)`

Return an iterator over non-zero exponents of `α`

, beginning at `0`

-th one. Matched iterator over coefficients is provided by @ref(values).

`Cyclotomics.coeffs`

— Function`coeffs(α::Cyclotomic)`

Return the coefficients of `α`

as stored.

`Base.values`

— Function`values(α::Cyclotomic)`

Return an iterator over non-zero coefficients of `α`

, beginning at `0`

-th one. Matched iterator over exponents is provided by @ref(exponents).

`Base.conj`

— Function`conj(α::Cyclotomic[, n::Integer=1])`

Return the `n`

-th conjugate of `α`

, i.e. the image of `α`

under the `n`

-th Frobenious homomorphism.

If `n`

is co-prime to the conductor of `α`

the map defines Galois automorphism. Note that the default choice for `n=-1`

corresponds to the standard complex conjugation.

`Cyclotomics.dense`

— Function`dense(α::Cyclotomic)`

Return a copy of `α`

with coefficients stored in dense `Vector`

.

`SparseArrays.sparse`

— Function`sparse(α::Cyclotomic)`

Return a copy of `α`

with coefficients stored in `SparseVector`

.

## Embeddings and normal forms

`Cyclotomics.reduced_embedding`

— Function`reduced_embedding(α::Cyclotomic{T,V}[, m::Integer=1])`

Return the reduced embedding of `α`

into `m`

-th cyclotomic field.

When `m=1`

, the embedding into possibly smallest degree is returned.

`Cyclotomics.embed`

— Function`embed(α::Cyclotomic, m::Integer)`

Embed `α`

into the `m`

-th cyclotomic field. `m`

can be either larger, or smaller than the conductor of `α`

, however either `conductor(α)`

must divide `m`

, or the other way around.

`Cyclotomics.isnormalized`

— Function`isnormalized(α::Cyclotomic, basis)`

Check if `α`

is already in normal form with respect to the given basis.

`Cyclotomics.normalform!`

— Function`normalform!(α::Cyclotomic[, tmp=dense(α)]; basis_forbidden=...)`

Reduces `α`

to the Zumbroich basis in-place. Note that unless `α`

has dense storage the operation will need at least one dense `tmp::Cyclotomic`

.

`Cyclotomics.normalform`

— Function`normalform(α::Cyclotomic)`

Reduces `α`

to the Zumbroich basis.

### Internals

`Base.hash`

— Function`hash(α::Cyclotomic[, h::UInt])`

A basic hashing function for cyclotomic elements; Note that unlike the `Base`

types hashing of `Cyclotomic`

s is expensive as it necessitates reducing to minimal embeding. This is to keep `hash`

ing consistent and reliable with respect to `==`

, i.e. that the equality of elements implies the equality of `hash`

es.

## Technicalities: Zumbroich basis

One can naively represent cyclotomic number as a vector of `n`

coefficients, corresponding to `n`

-th root of identity. However since there are relations among them (e.g. the sum of all is equal to `0`

), the actual dimension of the vector space is usually much smaller than `n`

. Zumbroich basis is the set of `n`

-th roots of unity which are linearly independent as vectors in the subspace (i.e. allow to express any cyclotomic number as sum of them).

There are three implementations provided by the package:

`zumbroich_plain`

following the description in the documentation of GAP system`zumbroich_direct`

which attempts to compute the basis directly`zumbroich_viacomplement`

which computes the complement of the basis (the default).

My understanding and the implementation are based on the wonderful documenting comments at the top of cyclotom.c from GAP project. Check them out!

!!! note The package uses function `zumbroich_basis`

(which defaults to `zumbroich_viacomplement`

) in its source code. To avoid recomputation the basis over and over the function is memoized for `Int`

arguments.