CountingChambers

julia package for counting chambers of hyperplane arrangements

This package counts chambers of a hyperplane arrangement by computing its characteristic polynomial, or equivalently, its Betti numbers. It performs this computation via a modified deletion-restriction algorithm which takes advantage of the arrangement's symmetries, as detailed in the preprint Enumerating chambers of hyperplane arrangements with symmetry.

Further examples and explanation can be found here where you can also try the code via binder without installing julia.

Getting started

Our package can be loaded (after starting julia) by

]add CountingChambers
using CountingChambers

using Pkg; Pkg.add("CountingChambers")
using CountingChambers

]add https://github.com/tbrysiewicz/CountingChambers
using CountingChambers

Our main dependencies are the julia packages for GAP, Nemo, and Hecke.

Basic functionality

Inputting arrangements

Hyperplane arrangements may be defined over the integers, rationals, or an algebraic extension of the rationals.

When the arrangement A of n hyperplanes in d dimensional space is central (all hyperplanes go through the origin), it is represented as a d by n matrix whose columns are the normal vectors of those hyperplanes. These matrices may have entries which are julia integers, or alternatively, in any number field from Hecke/Nemo.

For non-central arrangements, the input to our functions require a vector c of constants for which the n equalities encoded as xA=c represent the hyperplanes. For example,

A = [-1 1 1 0; 1 0 1 1] # The four columns of A represent the normal vectors of the arrangement.
c = [1, 0, 1, 0] # To deal with non-central arrangements, constant terms can be given.
number_of_chambers(A; ConstantTerms=c)
   10

outputs 10 as the number of chambers of the arrangement xA=c of 4 hyperplanes in 2-dimensional space.

Inputting symmetry groups

To input a symmetry group of an arrangement, as a subgroup of the symmetric group on n elements, one provides a collection of permutations which generate it. These permutations may be written in one line notation or alternatively, a GAP permutation group may be provided.

In the above example, the symmetry group consists of permuting the first three columns and is generated by the permutations [2,3,1,4] and [2,1,3,4]. This information can be inputed as follows to allow the algorithm to take advantage of these symmetries.

G =  [[2,3,1,4],[2,1,3,4]]
betti_numbers(A; ConstantTerms=c, SymmetryGroup=G)
   [1, 4, 5]

Multiple threads

After calling julia with multiple threads via

julia --threads 4

one may also call our functions with the optional argument multi_threaded=true to execute the code in parallel.

Examples

This package can handle large arrangements. For example, the following evaluates in less than six seconds. It is a computation on an arrangement in 7-dimensional space consisting of 127 hyperplanes.

R7 = resonance_hyperplanes(7);
GR7 = symmetry_resonance(7)
@time b=betti_numbers(R7; SymmetryGroup=GR7)
   [1, 127, 7035, 215439, 3831835, 37769977, 169824305, 135677633]

The arrangements discussed in Enumerating chambers of hyperplane arrangements with symmetry and their symmetry groups are exported in this package:

n=6
R=(resonance_hyperplanes(n),symmetry_resonance(n))
T=(threshold_hyperplanes(n),symmetry_threshold(n))
P=(permutohedron_hyperplanes(n),symmetry_permutohedra(n))
D=(demicube_hyperplanes(n),symmetry_demicube(n))
C=(crosspolytope_hyperplanes(n),symmetry_crosspolytope(n))
Disc=(discriminantal_hyperplanes(n),symmetry_discriminantal(n)) 
# note that discriminantal_hyperplanes provdes both the matrix A and the vector c of constants