Cyclotomics.jl

A package for working with cyclotomic numbers
Author kalmarek
Popularity
1 Star
Updated Last
2 Years Ago
Started In
July 2020

Cyclotomics.jl

CI codecov Stable Dev

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 SparseVectors,
  • 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