Chevie

ChevieModule

This is my attempt to port the Chevie package from GAP3 to Julia. I started this project at the end of 2018 and it is still in flux so some function names or interfaces may still change. Pull requests and issues are welcome.

I have implemented the GAP functionality (infrastructure) needed to make Chevie work. I have already registered most of this infrastructure as separate packages; the following packages are loaded and re-exported so that their functionality is automatically available when you use Chevie. In other words, Chevie is a meta-package for the following packages:

Have a look at the documentation of the above packages to see how to use their features. I have implemented some other infrastructure which currently resides in Chevie but may eventually become separate packages:

  • factorizing polynomials over finite fields (module FFfac)
  • factorizing polynomials over the rationals (module Fact)
  • Number fields which are subfields of the Cyclotomics (module Nf)

For permutation groups I have often replaced GAP's sophisticated algorithms with naive but easy-to-write methods suitable only for small groups (sufficient for the rest of the package but perhaps not for your needs). Otherwise the infrastructure code is often competitive with GAP, despite using much less code (often 100 lines of Julia replace 1000 lines of C); and I am sure it could be optimised better than I did. Comments on code and design are welcome. For functions that are too inefficient or difficult to implement (such as character tables of arbitrary groups), Chevie uses the GAP package as an extension. This means that if you have the GAP package installed, Chevie will automatically call GAP4 to implement these functions. The code in this package is often 10 times faster than the equivalent GAP3 Chevie code (after the maddeningly long compilation time on the first run –- Julia's TTFP).

The Chevie package currently contains about 95% of the GAP3/Chevie functionality, ported from Gap3. If you are a user of GAP3/Chevie, the gap function can help you to find the equivalent functionality in Chevie.jl to a Gap3 function: it takes a string and gives you Julia translations of functions in Gap3 that match that string.

julia> gap("words")
CharRepresentationWords  =>  traces_words_mats
CoxeterWords(W[,l])      =>  word.(Ref(W),elements(W[,l]))
GarsideWords             =>  elements

You can then access online help for the functions you have found.

The port to Julia is not complete in the sense that 80% of the code is the data library from Chevie, which was automatically ported by a transpiler so its code is "strange". When the need to maintain the GAP3 and Julia versions simultaneously subsides, I will do a proper translation of the data library, which should give an additional speed boost.

This package requires julia 1.8 or later.

source

Extensions to Laurent and Puiseux polynomials

Primes.factorMethod

factor(f::Pol{FFE{p}}[, F])

Given f a polynomial over a finite field of characteristic p, factor f, by default over the field of its coefficients, or if specified over the field F. The result is a Primes.Factorization{Pol{FFE{p}}}.

julia> @Pol q
Pol{Int64}: q

julia> f=q^3*(q^4-1)^2*Z(3)^0
Pol{FFE{3}}: q¹¹+q⁷+q³

julia> factor(f)
(q²+1)² * (q+1)² * (q-1)² * q³

julia> factor(f,GF(9))
(q+1)² * (q-1)² * (q+Z₉²)² * (q+Z₉⁶)² * q³
source
Primes.factorMethod

factor(f::Pol{<:Union{Integer,Rational{<:Integer}}})

Factor f over the rationals. The result is a Primes.Factorization{typeof(f)}.

julia> factor(Pol(:q)^24-1)
(q-1) * (q²-q+1) * (q⁴-q²+1) * (q⁸-q⁴+1) * (q⁴+1) * (q²+1) * (q+1) * (q²+q+1)
source
Primes.factorMethod

factor(p::Mvp)

p should be of degree <=2 thus represent a quadratic form. The function returns a list of two linear forms of which p is the product if such forms exist, otherwise it returns [p].

julia> @Mvp x,y

julia> factor(x^2-y^2+x+3y-2)
2-element Vector{Mvp{Int64, Int64}}:
 x-y+2
 x+y-1

julia> factor(x^2+x+1)
2-element Vector{Mvp{Cyc{Int64}, Int64}}:
 x-ζ₃
 x-ζ₃²

julia> factor(x*y-1)
1-element Vector{Mvp{Int64, Int64}}:
 xy-1
source

Extensions to groups

Chevie.Tools.abelian_gensFunction

abelian_gens(A)

A should be an abelian group or the list of its generators. Such a group has a unique decomposition up to isomorphism as a product of cyclic groups C(n₁)×…×C(nₖ) where C(nᵢ) is a cyclic group of order nᵢ and nᵢ divides nᵢ₊₁. The function returns a list of generators for each of the C(nᵢ).

julia> abelian_gens([Perm(1,2),Perm(3,4,5),Perm(6,7)])
2-element Vector{Perm{Int16}}:
 (6,7)
 (1,2)(3,5,4)(6,7)
source
Chevie.Tools.abelian_invariantsFunction

abelian_invariants(G::Group )

G should be an abelian group. Such a group has a unique decomposition up to isomorphism as a product of cyclic groups C(n₁)×…×C(nₖ) where C(nᵢ) is a cyclic group of order nᵢ and nᵢ divides nᵢ₊₁. The function returns the list n₁,…,nₖ.

julia> abelian_invariants(Group(Perm(1,2),Perm(3,4,5),Perm(6,7)))
2-element Vector{Int64}:
 2
 6
source
Combinat.blocksMethod

blocks(G::Group,p::Integer)

Let p be a prime. This function returns the partition of the irreducible characters of G in p-blocks, represented by the list of indices of irreducibles characters in each block.

julia> W=coxsym(5)
𝔖 ₅

julia> blocks(W,2)
2-element Vector{Vector{Int64}}:
 [1, 3, 4, 5, 7]
 [2, 6]

julia> blocks(W,3)
3-element Vector{Vector{Int64}}:
 [1, 5, 6]
 [2, 3, 7]
 [4]

julia> blocks(W,7)
7-element Vector{Vector{Int64}}:
 [1]
 [2]
 [3]
 [4]
 [5]
 [6]
 [7]
source

Extensions to linear algebra

Utilities

Chevie.UtilModule

This module contains various utility functions used in the rest of the code. Maybe some of them exist in some Julia module I am not aware of; please tell me.

source
Chevie.Util.@forwardMacro

@forward T.f f1,f2,...

is a macro which delegates definitions. The above generates

f1(a::T,args...)=f1(a.f,args...)
f2(a::T,args...)=f2(a.f,args...)
...
source
Chevie.Util.showtableFunction

showtable(io, table::AbstractMatrix; options )

General routine to format a table. The following options can be passed as properties of the io or as keywords.

  • row_labels labels for rows (default axes(table,1))
  • rows_label label for first column (column of row labels)
  • col_labels labels for other columns
  • rowseps line numbers after which to put a separator
  • rows show only these rows
  • cols show only these columns
  • TeX give LaTeX output (useful in Jupyter or Pluto)
  • column_repartition display in vertical pieces of sizes indicated (default if not TeX: take in account displaysize(io,2))
  • align alignment of column (default 'c':centered)
julia> m=[1 2 3 4;5 6 7 8;9 1 2 3;4 5 6 7];

julia> showtable(stdout,m)
1│1 2 3 4
2│5 6 7 8
3│9 1 2 3
4│4 5 6 7

julia> labels=["x","y","z","t"];

julia> showtable(stdout,m;cols=2:4,col_labels=labels,rowseps=[0,2,4])
 │y z t
─┼──────
1│2 3 4
2│6 7 8
─┼──────
3│1 2 3
4│5 6 7
─┴──────
source
Chevie.Util.cutFunction

cut(io::IO=stdout,string;width=displaysize(io)[2]-2,after=",",before="")

This function prints to io the string argument cut across several lines for improved display. It can take the following keyword arguments:

  • width: the cutting width
  • after: cut after these chars
  • before: cut before these chars
julia> cut(string(collect(1:50)))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
 41, 42, 43, 44, 45, 46, 47, 48, 49, 50]
source