# Chevie

`Chevie`

— ModuleThis 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:

- (univariate) LaurentPolynomials (and rational fractions)
- (multivariate) PuiseuxPolynomials (and rational fractions when there are no fractional exponents)
- CyclotomicNumbers(elements of cyclotomic fields)
- 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`

and`Groups`

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)
- GroupPresentations (presentations of groups, and groups defined by generators and relations)
- UsingMerge (Automatically compose several 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 `GAP`

to implement these functions.

Functions in the `Chevie.jl`

package are often 10 times faster than the equivalent functions in GAP3/Chevie (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. 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.

**Installing**

This is a registered package that can be installed/upgraded in the standard way. For Julia newbies, we will remind you what this is. To install, do this at the REPL command line:

- enter package mode with ]
- do the command

`(@v1.10) pkg> add Chevie`

- exit package mode with backspace and then do

`julia> using Chevie`

and you are set up. For first help, type "?Chevie".

To update later to the latest version, do

`(@v1.10) pkg> update`

`Chevie.jl`

requires julia 1.10 or later.

Chevie uses its rich total infrastructure to provide extensions to several of its infrastructure packages.

#### Extensions to Laurent and Puiseux polynomials

`Primes.factor`

— Method`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³
```

`Primes.factor`

— Method`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)
```

`Primes.factor`

— Method`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
```

#### Arithmetic and finite fields

`LaurentPolynomials.valuation`

— Method`valuation(c::Union{Integer,Rational{<:Integer},p::Integer)`

`p`

-adic valuation of `c`

(largest power of `p`

which divides `c`

; for a `Rational`

, valuation of the numerator minus that of the denominator).

```
julia> valuation.(24,(2,3,5))
(3, 1, 0)
```

`FiniteFields.FFE`

— Method`FFE{p}(z::Cyc)`

where `z`

is a `p`

-integral cyclotomic number (that is, `z`

times some number prime to `p`

is a cyclotomic integer), returns the reduction of `z`

mod. `p`

, an element of some extension `𝔽_{pʳ}`

of the prime field `𝔽ₚ`

.

```
julia> FFE{3}(E(7))
Z₇₂₉¹⁰⁴
```

#### Extensions to groups

`Chevie.Tools.abelian_gens`

— Function`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)
```

`Chevie.Tools.abelian_invariants`

— Function`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
```

`Combinat.blocks`

— Method`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]
```

#### Extensions to linear algebra

`Chevie.Tools2.eigmat`

— Function`eigmat(m::Matrix)`

eigenvalues of finite order of `m`

, as a `Vector{Root1}`

#### Useful macros

`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...)
...
```