Chevie
Chevie
— ModuleThis is my effort to port to Julia the Chevie package from GAP3. I started this project at the end of 2018 and it is still in flux so the package is not yet registered. If you see anything that needs improving in this package, please contact me or make an issue or pull request in the GitHub repository.
Installing
To install this package, at the Julia command line:
- enter package mode with ]
- do the command
(@v1.7) pkg> add "https://github.com/jmichel7/Chevie.jl"
- exit package mode with backspace and then do
julia> using Chevie
and you are set up.
To update later to the latest version, do
(@v1.7) pkg> update Chevie
This package requires julia 1.6 or later.
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 reexported so that their functionality is automatically available when you use Chevie
. In other terms, Chevie
is a meta-package for the following packages:
- (univariate) LaurentPolynomials (and rational fractions)
- (multivariate) PuiseuxPolynomials (and rational fractions when there are no fractional exponents)
- CyclotomicNumbers
- ModuleElts (elements of a free module over some ring)
- Combinat (combinatorics and some basic number theory)
- PermGroups (permutations, groups, permutations groups. It contains the modules
Perms
andGroups
which could be separate packages) - SignedPerms (signed permutations)
- MatInt (Integer matrices and lattices)
- CycPols (cyclotomic polynomials)
- GenLinearAlgebra (linear algebra on any field/ring)
- FinitePosets (finite posets)
- FiniteFields (finite fields)
- UsingMerge (Automatically compose several packages)
- GroupPresentations (presentations of groups, and groups defined by generators and relations)
Look at the documentation of the above packages to see how to use the corresponding features. I have implemented some more infrastructure which sits currently in Chevie
but may become eventually 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 maybe not for your needs). Otherwise the infrastructure code is often competitive with GAP, despite being much shorter (often 100 lines of Julia replace 1000 lines of C); I am sure there are more optimisations possible. Any comments on the code and the design are welcome. For functions that are too inefficient or difficult to implement (such as character tables of arbitrary groups) Chevie
automatically calls GAP4 if you did using GAP
. Otherwise the code in this package is often 10 times faster than the equivalent GAP3 Chevie code (after the maddeningly long compilation time on first execution –- the TTFP problem of Julia).
The Chevie
package currently contains about 95% of the GAP3 Chevie functionality, ported from Gap3. The gap
function can help you to find the equivalent functionality 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
Then you can call on-line help on the discovered functions.
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
version and the Julia
version simultaneously subsides, I will do a proper translation of the data library, which should give an additional speed boost.
Extensions to Laurent and Puiseux polynomials
Chevie.FFfac
— ModuleFactoring polynomials over finite fields
Primes.factor
— Methodfactor(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³
Chevie.Fact
— ModuleFactoring polynomials over the rationals
Primes.factor
— Methodfactor(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)
Primes.factor
— Methodfactor(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
Extensions to groups
Chevie.Tools.abelian_gens
— Functionabelian_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)
Chevie.Tools.abelian_invariants
— Functionabelian_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
Combinat.blocks
— Methodblocks(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]
Extensions to linear algebra
Chevie.Tools2.eigmat
— Functioneigmat(m::Matrix)
eigenvalues of finite order of m
, as a Vector{Root1}
Utilities
Chevie.Util
— ModuleThis 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.
Chevie.Util.@forward
— Macro@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...)
...
Chevie.Util.showtable
— Functionshowtable(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 (defaultaxes(table,1)
)rows_label
label for first column (column of row labels)col_labels
labels for other columnsrowseps
line numbers after which to put a separatorrows
show only these rowscols
show only these columnsTeX
give LaTeX output (useful in Jupyter or Pluto)column_repartition
display in vertical pieces of sizes indicated (default if notTeX
: take in accountdisplaysize(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
─┴──────
Chevie.Util.cut
— Functioncut(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]