Enumerating chambers in symmetric arrangements

using CountingChambers

┌ Info: Precompiling CountingChambers [23b3ee6f-a072-41d8-ada8-267420d58637]
└ @ Base loading.jl:1317

 ┌───────┐   GAP 4.11.1 of 2021-03-02
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-apple-darwin14-julia64-kv7
 Configuration:  gmp 6.2.0, Julia GC, Julia 1.6.0, readline
 Loading the library and packages ...
 Packages:   AClib 1.3.2, Alnuth 3.1.2, AtlasRep 2.1.0, AutoDoc 2019.09.04,
             AutPGrp 1.10.2, CRISP 1.4.5, Cryst 4.1.23, CrystCat 1.1.9,
             CTblLib 1.2.2, FactInt 1.6.3, FGA 1.4.0, Forms 1.2.5,
             GAPDoc 1.6.3, genss 1.6.6, IO 4.7.0, IRREDSOL 1.4,
             JuliaInterface 0.5.2, LAGUNA 3.9.3, orb 4.8.3, Polenta 1.3.9,
             Polycyclic 2.15.1, PrimGrp 3.4.0, RadiRoot 2.8, recog 1.3.2,
             ResClasses 4.7.2, SmallGrp 1.4.1, Sophus 1.24, SpinSym 1.5.2,
             TomLib 1.2.9, TransGrp 2.0.5, utils 0.69
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
─────────────────────────────────────────────────────────────────────────────
Loading  ferret 1.0.3 (Backtrack Search in Permutation Groups)
by Christopher Jefferson (http://caj.host.cs.st-andrews.ac.uk/).
Homepage: https://gap-packages.github.io/ferret/
Report issues at https://github.com/gap-packages/ferret/issues
─────────────────────────────────────────────────────────────────────────────
─────────────────────────────────────────────────────────────────────────────
Loading  images 1.3.0 (Minimal and Canonical images)
by Christopher Jefferson (http://caj.host.cs.st-andrews.ac.uk/),
   Markus Pfeiffer (http://www.morphism.de/~markusp/),
   Rebecca Waldecker (http://conway1.mathematik.uni-halle.de/~waldecker/), and
   Eliza Jonauskyte (ej31@st-andrews.ac.uk).
maintained by:
   Christopher Jefferson (http://caj.host.cs.st-andrews.ac.uk/).
Homepage: https://gap-packages.github.io/images/
Report issues at https://github.com/gap-packages/images/issues
─────────────────────────────────────────────────────────────────────────────

Example 2 from our article:

We start by computing the characteristic polynomial \(\chi_{\mathcal{A}}(t)\) of the arrangement \(\mathcal{A}\) depicted above.

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 c_i for l(x1,...,x_n)=c_i can be given.
number_of_chambers(A; ConstantTerms=c)

$10$

print(betti_numbers(A; ConstantTerms=c))
chiA = characteristic_polynomial(A; ConstantTerms=c)

[1, 4, 5]

$t^{2} - 4t + 5$

Zaslavasky proved that for a general arrangement \(\mathcal{A}\) in \(\mathbb{R}^d\) the number of chambers equals \((-1)^d\chi_{\mathcal{A}}(-1)\) and the number of bounded chambers equals \((-1)^d\chi_{\mathcal{A}}(1)\):

using Nemo
println("The number of chambers is:")
println(evaluate(chiA, -1))
println("The number of bounded chambers is:")
println(evaluate(chiA, 1))

The number of chambers is:
10
The number of bounded chambers is:
2

The symmetry group of this arrangements permutes the first three hyperplanes. This group can be passed as a list of generators in one-line notation:

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

[$1$, $4$, $5$]

The threshold arrangement

The \(d\)- threshold arrangement \(\mathcal{T}_d\) is an arrangement in \(\mathbb{R}^{d+1}\) consisting of the hyperplanes \(1+c_1x_1+...+c_dx_d=0\) for all \(c_i=0,1\). Its chambers correspond to threshold functions which are linearly separabale Boolean functions on \(d+1\) inputs. We first compute the number of chambers of \(\mathcal{T_6}\) without symmetry:

T6 = threshold_hyperplanes(6)
@time number_of_chambers(T6)

  9.949601 seconds (22.93 M allocations: 1.059 GiB, 7.73% gc time)

$15028134$

Computing the number of chambers of T_6 with symmetry:

GT6 = symmetry_threshold(6); # This is the symmetry group of the 6-dimensional cube.
@time number_of_chambers(T6; SymmetryGroup=GT6)

  0.386299 seconds (938.90 k allocations: 53.837 MiB)

$15028134$

The demicube arrangement is a subarrangement of the threshold arrangement defined by the equations \(1+c_1x_1+...+c_dx_d=0\) with \(c_i=0,1\) such that the number of \(1\)’s is even.

D5 = demicube_hyperplanes(5)
GD5 = symmetry_demicube(5)
characteristic_polynomial(D5; SymmetryGroup=GD5)

$t^{6} - 16t^{5} + 120t^{4} - 500t^{3} + 1160t^{2} - 1362t + 597$

The resonance arrangement

A related arrangement is the so-called resonance arrangement \(\mathcal{R}_d\). It is the restriction of \(\mathcal{T}_d\) to the hyperplane \(x_0+...+x_d=0\) and appears in various applications such as physics, computer science and ecconomics. We compute the Betti numbers of \(\mathcal{R}_7\) with symmetry. They add up to the total of 347326352 chambers.

R7 = resonance_hyperplanes(7);
GR7 = symmetry_resonance(7)
@time b=betti_numbers(R7; SymmetryGroup=GR7)

  5.072711 seconds (3.85 M allocations: 215.251 MiB, 0.10% compilation time)

[$1$, $127$, $7035$, $215439$, $3831835$, $37769977$, $169824305$, $135677633$]

sum(b) # The sum of the Betti numbers equals the number of chambers.

$347326352$

The discriminantal arrangement

The discriminantal arrangement \(Disc_{d,n}\) is a non-central hyperplane arrangement. Given \(n\) points in general position in \(\mathbb{R}^d\) is consists of the \(\binom{n}{d}\) many hyperplane spanned by \(d\)-subset of such points.

D46= discriminantal_hyperplanes(4,6)
GD46 = symmetry_discriminantal(4,6)
number_of_chambers(D46[1]; ConstantTerms=D46[2], SymmetryGroup=GD46)

$600$