Discrete & Computational Geometry (2023) 70:1356–1377
https://doi.org/10.1007/s00454-023-00557-2
Computing Characteristic Polynomials of Hyperplane
Arrangements with Symmetries
Taylor Brysiewicz1·Holger Eble2·Lukas Kühne3
Received: 25 June 2021 / Revised: 23 February 2023 / Accepted: 25 March 2023 /
Published online: 7 November 2023
© The Author(s) 2023
Abstract
We introduce a new algorithm computing the characteristic polynomials of hyper-
plane arrangements which exploits their underlying symmetry groups. Our algorithm
counts the chambers of an arrangement as a byproduct of computing its characteristic
polynomial. We showcase our julia implementation, based on OSCAR, on exam-
ples coming from hyperplane arrangements with applications to physics and computer
science.
Keywords Hyperplane arrangement ·Chambers ·Algorithm ·Symmetry ·
Resonance arrangement ·Separability
Mathematics Subject Classification 52C35 ·52B15
1 Introduction
The problem of enumerating chambers of hyperplane arrangements is a challenge in
computational discrete geometry [20,29,34,42]. A well-known approach to this prob-
lem is through the computation of characteristic polynomials [1,21,30,38,43,47].
Editor in Charge: János Pach
Taylor Brysiewicz
tbrysie[email protected]
Holger Eble
Lukas Kühne
1Department of Mathematics, Western University, London, Canada
2Chair of Discrete Mathematics/Geometry, Technische Universität Berlin, Berlin, Germany
3Fakultät für Mathematik, Universität Bielefeld, Bielefeld, Germany
123
Discrete & Computational Geometry (2023) 70:1356–1377 1357
Table 1 Our timings on examples from Sect. 6
A|Aut(A)|d=3 (s) 4 (s) 5 (s) 6 7 (s) 8 9
Td(d+1)!2d0.005 0.013 0.041 0.28s 33.17 8.16h
Rd(d+1)!0.004 0.011 0.035 0.12s 2.89 19.8 min ∼10 day+
C2d(2d)!22d0.015 0.039 0.085 0.183s 0.42 1.158 s 4.50s
Pdd!0.003 0.013 6.398 ∼8day+
Dd(d)!2d−10.002 0.005 0.018 0.049s 0.54 1.9 min ∼8day+
Disc4,nn!– 0.0003 0.0047 0.055 0.71 s 7.62 41.14s
Computations ran on a single thread (Intel Core i7-8700) except for R9which ran on 42 threads
(Intel Xeon E7-8867)
We develop a novel for computing characteristic polynomials which takes advantage
of the combinatorial symmetries of an arrangement. While most arrangements admit
few combinatorial symmetries [39], most arrangements of interest do [19,40,48].
We implemented our algorithm in julia [3] and published it as the package
CountingChambers.jl.1Our implementation relies heavily on the cornerstones
of the new computer algebra system OSCAR [51] for group theory computations (GAP
[50]) and the ability to work over number fields (Hecke and Nemo [17]).
While other algorithms and pieces of software exist for studying hyperplane
arrangements (see, for instance, [10,15,29,33,44]), either their chamber-enumeration
computations appear as byproducts of more difficult calculations, the code does not use
symmetry, or it only pertains to very specific types of arrangements. For example, ref-
erence [29] computes the associated zonotope, whose vertices are in bijection with the
chambers of the arrangement, containing much more information than the character-
istic polynomial. A similar approach is suggested in [15] involving a search algorithm
relying upon linear programming. An example of an approach which computes the
number of chambers via a much more difficult computation is via the computation of
the so-called broken circuit complex of the arrangement (see [7]): a simplicial complex
which has the same number of faces as the number of chambers of the arrangement.
As demonstrated in Table 1, the fastest algorithms we know of for counting cham-
bers in hyperplane arrangements (including the one discussed in this article) also
compute the characteristic polynomial of the arrangement as a byproduct. In this
sense, we do not know of an algorithm which illustrates that counting the chambers
of an arrangement is an easier computation than computing its characteristic polyno-
mial. To the best of our knowledge, our implementation is the first publicly available
software for counting chambers which uses symmetry.
We showcase our algorithm and its implementation on a number of well-known
examples, such as the resonance and discriminantal arrangements. Additionally, we
study sequences of hyperplane arrangements which come from the problem of linearly
separating vertices of regular polytopes. In particular, we investigate one correspond-
ing to the hypercube [0,1]dwhose chambers are in bijection with linearly separable
Boolean functions.
1Available at https://mathrepo.mis.mpg.de/CountingChambers.
123
1358 Discrete & Computational Geometry (2023) 70:1356–1377
In the presence of symmetry, our implementation outperforms the existing software
by several orders of magnitude (cf. Table 1). Moreover, its output is guaranteed to be
correct since we compute symbolically over the integers or exact number fields and
avoid overflow errors thanks to the package SaferIntegers.jl [41].
The ninth resonance arrangement (511 hyperplanes in R9) approaches the limit
of what is possible with our implementation: the computation of its characteristic
polynomial took ten days on 42 processors. Our computation confirms that its chamber-
count is 1955230985997140 as independently and concurrently computed by Chroman
and Singhar with different methods [10].
We first give background on hyperplane arrangements in Sect. 2. The ideas outlined
in Sect. 3, regarding deletion and restriction algorithms, form the basic structure of
our algorithm. We explain the relevant results regarding symmetries of arrangements
in Sect. 4. The algorithm and its implementation details reside in Sect. 5. In Sect. 6we
construct and discuss examples of arrangements exhibiting large symmetry groups.
We conclude in Sect. 7with timings and comparisons to other software.
2 Hyperplane Arrangements
We begin by discussing background on the theory of hyperplane arrangements related
to the problem of enumerating chambers: the main goal of this article and the associated
software. Our notation will mostly follow the textbook by Orlik and Terao [38].
For any field K,ahyperplane in Kdis an affine linear space of codimension one.
Throughout this article, we denote by A={H1,...,Hn}a(hyperplane)arrangement
where Hiis a hyperplane in Kd.
Definition 2.1 Suppose Ais an arrangement in Rd. The connected components of the
complement Rd\H∈AHare called chambers of Aand the set of chambers of Ais
denoted by ch(A).
Example 2.2 We use the arrangement
{y−x=1}
H1
,{x=0}
H2
,{x+y=1}
H3
,{y=0}
H4
in R2as a running example. This arrangement is depicted in Fig. 1. It has ten chambers:
two bounded and eight unbounded.
Given a subset I⊆[n]:={1,...,n}, we write the set {Hi}i∈Ias HIand its
intersection as LI=i∈IHi. The collection of these intersections form the set
L(A)={LI|I⊆[n],LI=∅}, a combinatorial shadow of Aknown as its
intersection poset. This poset is ordered by reverse inclusion and graded by the rank
function,r:L(A)→Z≥0, where r(LI)=codim(LI). As a notational convention,
we set r(I)=r(LI)for I⊆[n]whenever LI=∅.
123
Discrete & Computational Geometry (2023) 70:1356–1377 1359
H1
H2
H3
H4
Fig. 1 The arrangement introduced in Example 2.2
2.1 The Characteristic Polynomial
Our algorithm counts chambers of an arrangement by computing a more refined count,
namely the characteristic polynomial. The coefficients of this polynomial are known
as the unsigned Whitney numbers of the first kind of the intersection poset L(A),
which we simply refer to as the Whitney numbers of the arrangement.
Definition 2.3 The characteristic polynomial of an arrangement Ain Kdis the poly-
nomial
χA(t)=
I⊆[n]
LI=∅
(−1)|I|td−r(I)=
d
i=0
(−1)ibi(A)td−i.(1)
The integers bi(A), defined via (1), are non-negative and are called the Whitney num-
bers of A. We denote the vector of Whitney numbers by b(A).
The characteristic polynomial and Whitney numbers of an arrangement Adepend
only on the intersection poset L(A)and have various interpretations depending on the
field Kas detailed below.
Real: For an arrangement Ain Rd, Zaslavsky [47] proved that
|ch(A)|=(−1)dχA(−1)=
d
i=0
bi(A).
Thus, the Whitney numbers are a refined count of the chambers of A.Theyhave
the following geometric interpretation. Given a generic flag F•:F0⊂F1⊂
... ⊂Fd=Rdof affine linear subspaces Fi[where dim(Fi)=i] the number
of chambers of Awhich meet Fibut do not meet Fi−1is equal to bi(A)[45,
Proposition 2.3.2].
Complex: If Ais an arrangement in Cdwhere all hyperplanes contain the origin,
then bi(A)is the ith topological Betti number of the complement Cd\H∈AH
with rational coefficients [37]. Because of this, some papers refer to the Whitney
numbers bi(A)as the Betti numbers of the arrangement A[46].
Finite: When Ais an arrangement over a finite field Fq, Crapo and Rota proved
that χA(q)=
Fd
q\H∈AH
[12]. Moreover, if Ais a hyperplane arrangement in
123
1360 Discrete & Computational Geometry (2023) 70:1356–1377
F0
F1
F2
Fig. 2 The intersections of a generic flag (purple) in R2with the chambers of A. The point F0intersects
one chamber, F1intersects four others, and F2intersects the remaining five, and so b(A)=(1,4,5)
Qdone may consider its reduction modulo q:A⊗Fq={H1⊗Fq,...,Hn⊗Fq}.
When qis sufficiently large, we have that L(A)=L(A⊗Fq)and thus computing
χA(t)for rational arrangements also yields the number of points in the complement
after reducing modulo large primes.
Example 2.4 Let Abe the arrangement introduced in Example 2.2. Its characteristic
polynomial is χA(t)=t2−4t+5. Figure 2shows a generic flag F•intersecting this
arrangement verifying that b(A)=(1,4,5).
3 A Deletion–Restriction Algorithm
To compute the Whitney numbers of an arrangement Ain Kd, we take advantage of the
behavior of χA(t)under the operations of deletion and restriction. These operations
reduce computations about Ato computations about two smaller arrangements. Thus
at its core, our main algorithm is a divide-and-conquer algorithm.
Given a hyperplane H∈A,thedeletion of Hin Ais the arrangement A\{H}.The
restriction of Hin Ais the arrangement in H∼
=Kd−1defined by AH={K∩H|
K∈A\{H}}. The following lemma provides the basic foundation of our algorithm.
Lemma 3.1 [38, Cor. 2.57] Given a hyperplane H ∈A,we have that χA(t)=
χA\{H}(t)−χAH(t). In particular,b(A)=b(A\{H})+0|b(AH)where 0|b means
prepending the vector b with a zero.
3.1 A Simple Deletion–Restriction Algorithm
Lemma 3.1 along with the fact that the empty arrangement in Kdhas the vector of
Whitney numbers (1,0,...,0)∈Nd+1suggests the following well-known recursive
algorithm for computing b(A).
123
Discrete & Computational Geometry (2023) 70:1356–1377 1361
Algorithm 1: Whitney numbers via simple deletion and restriction
Input: A hyperplane arrangement Ain Kd
Output: The vector of Whitney numbers b(A)
WhitneyNumbers (A)
1if ∅ = Athen
2choose H∈A
3return WhitneyNumbers(A\{H})+0|WhitneyNumbers(AH)
4else
5return (1,0,...,0)
Structurally, Algorithm 1is a depth-first binary tree algorithm on arrangements,
rooted at the initial input: one child represents a deletion and the other a restriction, as
shown in Fig. 3. The implementation of Algorithm 1is already nontrivial as it is often
the case that some hyperplanes become the same after a restriction. Thus, its proper
implementation requires care in representing an arrangement on a computer.
3.2 Computationally Representing Deletions and Restrictions
An arrangement Bcoming from Avia deletions and restrictions may be represented
by an encoding of the restricted hyperplanes. To be precise, the pair
(1, 4, 5)
123
4
(1,3,3) (1, 2)
(1, 1)(1, 2, 1) (1, 2) (1)
(1, 1, 0) (1, 1) (1, 1) (1) (1, 0) (1)
(1, 0, 0) (1, 0) (1, 0) (1) (1, 0) (1)
Fig. 3 The tree structure of Algorithm 1on the hyperplane arrangement from Example 2.2. Hyperplanes
are chosen (line 3) according to the ordering {1,2,3,4}. In each box, the ambient space of the arrangement
is shaded green. Deletions are marked with red edges (left children) and restrictions with blue edges (right
children). Each arrangement box has the Whitney numbers above its upper right corner
123
1362 Discrete & Computational Geometry (2023) 70:1356–1377
B=({Hi1,...,Hik},{Hj1,...,Hj})=: (HI,HJ)
represents the hyperplane arrangement Bin LI∼
=Kd−r(LI)given by the hyperplanes
in {Hj∩LI}j∈J. Note that Hj∩LImaybeemptyforsome j∈J, in which case this
intersection does not correspond to any hyperplane. We extend notation regarding B
to its representation B(i.e., χB(t):= χB(t)and b(B):= b(B)).
If Hj1∩LIis a hyperplane which occurs uniquely with respect to the tuple (Hj1∩
LI,...,Hj∩LI), then BHj1∩LIand B\{Hj1∩LI}are represented by
BHj1:= ({Hi1,...,Hik,Hj1},{Hj2,...,Hj}),
B\{Hj1}:=({Hi1,...,Hik},{Hj2,...,Hj}),
respectively. Whereas if Hj1∩LIis either empty or does not occur uniquely, then
B\{Hj1}trivially represents the same arrangement as B, namely B. The following
computational analogue of Lemma 3.1 establishes how such representations behave
under deletion and restriction.
Lemma 3.2 Let B =(HI,HJ)represent an arrangement Band fix H ∈HJ.If
H∩LIis a hyperplane which occurs uniquely in the tuple (Hj∩LI)j∈Jthen χB(t)=
χB\{H}(t)−χBH(t)and b(B)=b(B\{H})+0|b(BH). Otherwise,we have χB(t)=
χB\{H}(t)and b(B)=b(B\{H}).
Proof The first case follows from Lemma 3.1. In the second case, Band B\{H}
represent the same hyperplane arrangement and the result is trivial.
The following algorithm is equivalent to Algorithm 1.
Algorithm 2: Whitney numbers via extended deletion and restriction
Input: A representation B=(HI,HJ)of an arrangement in Kd
Output: The vector of Whitney numbers b(B)
WhitneyNumbers B=(HI,HJ)
1if ∅ = HJthen
2choose H∈HJ
3if H∩LI=∅occurs uniquely in (Hj∩LI)j∈Jthen
4return WhitneyNumbers(B\{H})+0|WhitneyNumbers(BH)
5else
6return WhitneyNumbers(B\{H})
7else
8return (1,0,...,0)
Given a hyperplane arrangement A={H1,...,Hn}in Kd, Algorithm 2computes
the Whitney numbers bi(A)when given A=(∅,{H1,...,Hn})as input. This algo-
rithm traverses a binary tree which is essentially the same as the one from Algorithm 1.
The only difference is that some edges are extended with nodes that have only one child
and so we say it computes the Whitney numbers via extended deletion and restriction.
123
Discrete & Computational Geometry (2023) 70:1356–1377 1363
, {1, 2, 3, 4} (1,4,5)
123
4
1
,{2,3,4} (1, 3, 3)
1
{1}, {2, 3, 4} (1, 2)
2
{1}, {3, 4} (1, 2)
2
, {3, 4} (1,2,1)
2
{2}, {3, 4} (1, 2)
3
,{4} (1,1,0)
3
{3}, {4} (1, 1)
3
{2}, {4} (1, 1)
3
{2, 3}, {4} (1)
3
{1}, {4} (1, 1)
3
{1, 3}, {4} (1)
4
,(1, 0, 0)
4
{4}, (1, 0)
4
{3}, (1, 0)
4
{3, 4}, (1)
4
{2}, (1, 0)
4
{2, 4}, (1)
4
{2, 3}, (1)
4
{1}, (1, 0)
4
{1, 4}, (1)
4
{1, 3}, (1)
Fig. 4 The tree structure of Algorithm 2on the hyperplane arrangement from Example 2.2. Its nodes are
represented by pairs of subsets I,J⊂{1,2,3,4}(top-left) and the Whitney numbers are given (top-right).
Grey edges indicate that the condition in line 3 has been violated
Algorithm 2has the advantage that the representations of the original hyperplanes
in Aneed not be updated upon restriction, and that representations of hyperplanes
in AHneed not be unique. As a consequence, structural aspects of Asuch as its
symmetries extend trivially to the representations of the restricted arrangements, as
we explain in Sect. 4. Figure 4displays the tree structure underlying Algorithm 2on
our running example. Note that Jis constant amongst nodes in the same depth.
4 Automorphisms of Hyperplane Arrangements
Our main contribution is the inclusion of symmetry-reduction in the deletion-
restriction algorithm. Many other algorithms in discrete geometry have also been
adapted to take advantage of symmetry [5,6,25,26]. For us, the relevant symmetries
for an arrangement are the rank-preserving permutations of its hyperplanes.
Let Snbe the permutation group on [n]. Elements of a subgroup G≤Snact on
subsets of [n].Giveng∈Gand I⊆[n], we fix the notation:
–gI ={g(i)}i∈Ifor the image of Iunder g,
–IG={g∈G|gI =I}for the stabilizer of Iin G,
–G·I={gI |g∈G}for the orbit of Iunder G.
123
1364 Discrete & Computational Geometry (2023) 70:1356–1377
Definition 4.1 The automorphism group of A={H1,...,Hn}is
Aut(A)={g∈Sn|r(HI)=r(HgI)for all I⊆[n]}.
Given a representation B=(HI,HJ)of an arrangement coming from A, the auto-
morphism group Aut(A)acts as gB =(HgI,HgJ).
Remark 4.2 Our definition of the automorphism group of an arrangement is combi-
natorial, not geometric. This difference can be quite large. For example, a generic
hyperplane arrangement A={H1,...,Hn}has no geometric symmetries but
Aut(A)=Sn.
Lemma 4.3 Let A={H1,...,Hn}be an arrangement in Kdand let B1and B2
represent arrangements coming from deletions and restrictions. If B1and B2are in
the same orbit under Aut(A)then b(B1)=b(B2).
Proof The conclusion of the lemma is equivalent to showing that the characteristic
polynomials of B1and B2are the same. This follows directly from the fact that the
characteristic polynomial depends only on the intersection poset (graded by rank) and
that B1and B2are in the same orbit under Aut(A)if and only if they are related by a
rank-preserving permutation.
Our algorithm relies upon the following corollary of Lemma 4.3.
Corollary 4.4 Let B =(HI,HJ)represent a hyperplane arrangement coming from
A={H1,...,Hn}.Forg∈JAut(A)we have that gB =(HgI,HJ)and B have the
same Whitney numbers.
5 Enumeration Algorithm with Symmetry
Our main algorithm augments Algorithm 2, making particular use of Corollary 4.4.
It is essentially a breadth-first tree algorithm except that at each level, nodes may be
identified up to symmetry and so the algorithmic structure is no longer that of a tree.
The output is the vector of Whitney numbers b(A)of an arrangement A, refining its
chamber count. We remark that despite the fact that our algorithm takes advantage
of symmetry and counts the number of chambers, it does not reveal any information
about the sizes of orbits of chambers under this symmetry group.
Given an arrangement A={H1,...,Hn}in Kd, we represent the nodes of the
algorithm at depth kby a dictionary Tk. The keys of Tkare orbits Gk·Ifor I⊆[k]
where Gkis a subgroup of the stabilizer of {k+1,...,n}in Aut(A).Thevalueof
Gk·Iin this dictionary is a pair (BI,ω(BI)) where BIrepresents the hyperplane
arrangement (HI,H{k+1,...,n})and ω(BI)is some multiplicity, tracking how many
arrangements indexed by elements of the orbit Gk·Ihave appeared. We refer to Tk
as a k-th orbit-node dictionary.
Algorithm 3presents the breadth-first structure of the algorithm.
123
Discrete & Computational Geometry (2023) 70:1356–1377 1365
Algorithm 3: Whitney numbers using symmetry
Input: A hyperplane arrangement A={H1,...,Hn}in Kd
A subgroup G≤Aut(A)
Output: The vector of Whitney numbers b(A)
WhitneyNumbers (A)
// compute the stabilizers of G
1compute {Gi}n
i=0where Gi={i+1,...,n}Gand Gn=G
// initialize orbit-node dictionaries
2initialize {Ti}n
i=0and set T0={G0·∅⇒((∅,A), 1)}
3for k=1,...,ndo
4set Tk=NextGeneration(A,Gk,Tk−1)
5initialize b=(0,0,...,0)
6for (BI,ω(BI)) ∈Tndo
7increment the entry b|I|by ω(BI)
8return b
Moving from depth k−1tokis performed by Algorithm 4.
Algorithm 4: NextGeneration
Input: A hyperplane arrangement A={H1,...,Hn}in Kd
A subgroup Gk≤{k+1,...,n}Aut(A)
An orbit-node dictionary Tk−1
Output: An orbit-node dictionary Tk
NextGeneration (A,Gk,Tk−1)
1set J={k+1,...,n}
2for (BI,ω(BI)) ∈
values
(Tk−1)do
3if Hk∩LIis a unique hyperplane amongst (Hj∩LI)n
j=kthen
// produce the restriction as the right child
4set I=I∪{k}
5compute the orbit O=Gk·I
6if O∈
keys
(Tk)then
7increment the multiplicity of Tk[O]by ω(BI)
8else
9Tk[O]=((HI,HJ), ω(BI))
// produce the deletion as the left child
10 compute the orbit O=Gk·I
11 if O∈
keys
(Tk)then
12 increment the multiplicity of Tk(O)by ω(BI)
13 else
14 Tk[O]=((HI,HJ), ω(BI))
return Tk
Example 5.1 The structure underlying Algorithm 3applied to the arrangement in
Example 2.2 is shown in Fig.5. It is no longer a tree but may be obtained from
thetreeinFig.4by identifying nodes under the stabilizers of Aut(A). Each identifi-
123
1366 Discrete & Computational Geometry (2023) 70:1356–1377
, {1, 2, 3, 4} (1, 4, 5)
123
4
1
, {2, 3, 4} (1, 3, 3)
1
{1}, {2, 3, 4} (1, 2)
2
,{3,4} (1, 2, 1)
22
{1}, {3, 4} (1, 2)
3
,{4} (1, 1, 0) {2}, {4} (1, 1)
3
{1, 3}, {4} (1)
4
,(1,0,0)
4
{4}, (1, 0)
4
{1, 3}, (1)
4
{2}, (1, 0)
4
{2, 4}, (1)
Fig. 5 The algorithmic structure underlying Algorithm 3. Starting at the top node, each call of Algorithm 4
produces the next depth of this graph
cation accumulates multiplicity in the node and that multiplicity is passed down to its
children.
5.1 Representing Orbits
The computations of orbits in lines 5and 10 require elaboration; specifically in regards
to representing an orbit G·Ion a computer. One option is to use a canonical element
of G·I, which can be computed using the MinimalImage or CanonicalImage
functions from GAP [23,24]. An alternative approach is to provide any function
ϕ:2[n]→Staking values in an arbitrary set Ssuch that ϕ(I)=ϕ(J)only if
G·I=G·J. Equivalently, ϕis any factor of the projection π:2[n]→2[n]/Gas a
map of sets where 2[n]/Gis the set of orbits. In this case, the value of ϕ(I)may be
used to represent the orbit G·Ias a key in the orbit–node dictionaries. While this
approach may fail to identify all nodes in the same orbit, nodes in distinct orbits are
never identified and so the algorithm remains correct. The benefit is that it may be
significantly more efficient to evaluate ϕthan it is to compute minimal or canonical
images.
Our default option for identifying orbits is called pseudo_minimal_image.
Given a subset I⊆[n]and a collection of elements g1,...,gm∈G≤Sn,
this function sequentially computes giIand recursively calls itself on giIwhenever
123
Discrete & Computational Geometry (2023) 70:1356–1377 1367
(a)
0
0
2
4
Pseudo minimal image
Minimal image
No identifications
log(number of nodes)
6
20 40 60
Depth
80 100 120
Leaves at depth.
(b) Time per depth.
0
–4
–3
–2
–1
0
Pseudo minimal image
Minimal image
No identifications
log(seconds)
1
20 40 60
Depth 80 100 120
Fig. 6 The leaves per depth and time per depth of Algorithm 3on the arrangement R7using pseudo_
minimal_image,MinimalImage, and no identifications
giI<Ilexicographically. If no such giproduces a smaller subset, Iitself is returned.
Options are implemented for choosing mto be a proportion of |G|subject to maxi-
mum and minimum values. For our computations, we take m=nrandom elements
of G. Although this greedy procedure does not make all possible identifications in
the algorithm, we have found that it is quicker than MinimalImage to evaluate and
produces a comparably small algorithmic structure.
Example 5.2 We compare the effect of three choices of identifications in Algorithm 3
(either pseudo_minimal_image,theMinimalImage function in GAP,orno
identifications at all) on the resonance arrangement R7(see Definition 6.3) consisting
of 127 hyperplanes in R7. We compare the number of leaves of the algorithm at some
depth, as well as the time per depth of the algorithm and display the results in Fig. 6.
As depicted, the cost (in number of leaves) of using pseudo_minimal_image
compared to MinimalImage is negligible, while the benefits in terms of speed
are significant. Similarly, while the timing of our algorithm with MinimalImage is
comparable to the timing without any identifications (Algorithm 2), the memory usage
is significantly reduced as conveyed by the number of leaves (a reasonable proxy for
memory usage). This difference becomes even more dramatic for larger arrangements.
5.2 Accumulating the Whitney Numbers and Skipping Levels
Much of the computational burden occurs in line 3of Algorithm 4and involves pro-
jecting the normal vectors of the hyperplanes in Aalong those hyperplanes which
123
1368 Discrete & Computational Geometry (2023) 70:1356–1377
have been restricted. When implementing Algorithm 4, one may choose whether to
save such computations at the cost of memory, or to perform redundant computations
throughout the algorithm. We found that, for our benchmark examples, recomputation
held the most benefit.
Nonetheless, from the linear algebra involved in the evaluation of line 3, one can
read off jmin, the smallest j∈Jfor which this uniqueness condition is true. Hence,
one may immediately place the left child of the corresponding node in level jmin rather
than kto avoid redundancy in line 3later on. This comes at the cost of missing some
identifications between the layers kand jmin.
Another implementation choice we made was to keep a running count of the Whit-
ney numbers of the arrangement throughout the algorithm. Whenever jmin =nwhile
computing the children of (BI,ω(BI)), we increment b|I|by ω(BI)and delete the
node altogether since no other deletions or restrictions are possible. Similarly, if Ais
a hyperplane arrangement where each hyperplane contains the origin, b|I|and b|I|+1
are incremented by ω(BI)whenever jmin =n−1 by a similar reasoning. In this way,
we can free memory occupied by nodes throughout the algorithm.
5.3 Relation to OSCAR
The new computer algebra system OSCAR in julia combines the existing systems
GAP [50], Singular [14], Polymake [18,27], and Antic (Hecke,Nemo)[51].
Our software is written in julia and builds heavily on these cornerstones. Specif-
ically, we use the number theory components Nemo [17] and Hecke to work with
arrangements defined over algebraic field extensions of Q. For example the separa-
bility arrangement of the vertices of the 600-cell is defined over Q(√5). Secondly,
we use GAP [50] for group theoretic computations in Algorithm 4. Concretely, we
compute stabilizers and minimal images using the GAP packages ferret [22] and
images [24], respectively.
5.4 Functionality of CountingChambers.jl
The julia package titled CountingChambers.jl contains our implementation
and is available at https://mathrepo.mis.mpg.de/CountingChambers. The following
code snippet shows some standard functions of our package applied to the arrangement
introduced in Example 2.2. A collection of hyperplanes defined by the equations
i(x1,...,xd)=cifor 1 ≤i≤nis encoded by a d×nmatrix Ahaving the
coefficients of ias columns and a vector c.
julia>A=[-1110;1011];
julia> c = [1, 0, 1, 0];
julia> whitney_numbers(A; ConstantTerms=c)
3-element Vector{Int64}:
145
julia> characteristic_polynomial(A; ConstantTerms=c)
t^2 - 4*t + 5
julia> number_of_chambers(A; ConstantTerms=c)
10
123
Discrete & Computational Geometry (2023) 70:1356–1377 1369
Note that the automorphism group of this arrangement is S3→S4consisting of
permutations of the first three hyperplanes. This group can be passed to our algorithm
via a list of generators in one-line notation:
julia> G = [[2,3,1,4],[2,1,3,4]];
julia> whitney_numbers(A; ConstantTerms=c, SymmetryGroup=G)
3-element Vector{Int64}:
145
As it is easy to run julia on multiple threads, we also implemented our algorithm
to take advantage of this. By starting julia via the command julia –threads
NUM_THREADS and passing the optional parameter multi_threaded=true to
our methods, the for loop in Algorithm 4is executed in parallel. Table 2shows how
the multithreading scales.
6 Examples and Integer Sequences
We apply our algorithm to a number of examples. Many of these arise from the
following construction of separability arrangements.
6.1 Separability Arrangements
Fix a finite set V⊂Rd. We associate to every v∈Vthe hyperplane Hv⊂(Rd+1)∗
comprised of linear forms which vanish on (1,v). Equivalently, Hvrepresents the affine
hyperplanes in Rdwhich contain v. We call the arrangement HV:= {Hv|v∈V}the
separability arrangement of V. We point out that by increasing the dimension dby one,
this construction is distinct from the one which defines real reflection arrangements
from root systems. In particular, translating Vdoes not change the combinatorics of
HV.
A hyperplane Hvpartitions the points in (Rd+1)∗\Hvinto the sets H+
vof linear
forms which are positive on vand H−
vwhich are negative on v. Consequently, all affine
hyperplanes corresponding to points in a chamber of HVare positive on some subset
V1⊂Vand negative on its complement V2=V\V1. Such a partition V1V2=V
is called linearly separable. Hence, chambers of HVare in bijection with linearly
separable partitions of V, motivating the terminology for HV. This point of view, which
connects linear separability and hyperplane arrangements, appears in [2, Sect. 2].
One purpose for introducing separability arrangements is that it immediately pro-
vides us with a zoo of arrangements admitting considerable symmetry; for example,
those Vwhich are the vertices of regular polytopes.
6.2 The Threshold Arrangement
The following arrangement appears in the study of neural networks [35,36,49] and
algebraic statistics [13].
123
1370 Discrete & Computational Geometry (2023) 70:1356–1377
Definition 6.1 The threshold arrangement2,Tdis the separability arrangement asso-
ciated to the vertices of the hypercube [0,1]d. That is,
Td:={{x0+c1x1+···+cdxd=0}with ci∈{0,1}for all ci}.
As a consequence of the definition of Td, the linear automorphisms of the hypercube
[0,1]d, namely the hyperoctahedral group of order d!2d, is a subgroup of Aut(Td).
ThetruesizeofAut(Td)is (d+1)!2d.
We computed the Whitney numbers of Tdfor 1 ≤d≤8, and thus their number
of chambers. The results are collected in Table 3and the timings appear in Table 1.
The values of |ch(Td)|for 1 ≤d≤9 are listed in entry https://oeis.org/A000609 of
the Online-Encyclopedia of Integer Sequences (OEIS), whereas the Whitney numbers
of Td, to the best of our knowledge, have not been published before. Zuev showed that
asymptotically |ch(Td)|∼2d2[48].
Remark 6.2 Using similar proof techniques as in [32] one can show that the values of
bi(Td)for 1 ≤d≤2idetermine a formula for bi(Td)for all d. Applying this to the case
of b2(Td)and b3(Td)and using the results in Table 3we obtain b2(Td)=(4d−2d)/2
and b3(Td)=(4·8d−3·6d−6·4d+5·2d)/24. For i≥4 this technique requires
knowledge of bi(Td)foratleast1≤d≤16.
6.3 The Resonance Arrangement
The next arrangement we consider appears as a restriction of the threshold arrange-
ment.
Definition 6.3 The resonance arrangement is the restriction of Tdto the hyperplane
H(0,...,0). Equivalently, for d≥1 the resonance arrangement is
Rd:= {{c1x1+c2x2+···+cdxd=0}with ci∈{0,1}and not all ciare zero}.
The chambers of the resonance arrangements are in bijection with generalized
retarded functions in quantum field theory [16]. An overview of the applications of
the resonance arrangement is given in [32, Sect. 1]. A formula for their number of
chambers remains elusive, let alone one for their Whitney numbers. Nonetheless,
partial formulas and bounds exist [4,19,32,48].
The numbers of chambers of the resonance arrangements are listed in the sequence
https://oeis.org/A034997 intheOEISuptod=9. The Whitney numbers are published
in [28]uptod=7. Our software was able to determine the Whitney numbers of R8
and R9confirming the concurrent computations in [10]. The computation for R9took
ten days, running multithreaded on 42 Intel Xeon E7-8867 v3 CPUs. All Whitney
numbers of Rdup to d=9 are given in Table 4and the timings are listed in Table 1.
2The arrangement {xi+xj}1≤i<j≤din Rdis also referred to as a threshold arrangement in the literature.
We discuss the arrangement Tdonly as in Definition 6.1.
123
Discrete & Computational Geometry (2023) 70:1356–1377 1371
6.4 Separability Arrangements of the Cross-Polytopes
The cross-polytope of dimension dis the polytope with the 2dvertices {±ei}d
i=1.Its
symmetry group is the hyperoctahedral group of order d!2d. We define the arrange-
ment Cdin Rd+1to be the separability arrangement of its vertices. Our computations
show that |ch(Cd)|=2·3d−2dfor d≤20, suggesting that |ch(Cd)|agrees with
this sequence (https://oeis.org/A027649 in the OEIS). This can indeed be proven by
applying Athanasiadis’ finite field method [1] and seems to be a new result obtained
through experiments with our algorithm.
6.5 Separability Arrangements of Permutohedra
The permutohedron of dimension d−1 is the convex hull of the d!points σ(1,...,d)
for all σ∈Sd. The separability arrangements Pdof these points in Rd+1consist of
d!hyperplanes. We record their Whitney numbers in Table 6for 1 ≤d≤6.
6.6 Separability Arrangements of Demicubes
The d-demicube is the convex hull of those vertices of the hypercube [0,1]dwhich have
an odd number of 1’s. For instance, the 3-demicube is a regular tetrahedron. We denote
by Ddthe corresponding separability arrangement consisting of 2d−1hyperplanes
in Rd+1. Table 5contains the Whitney numbers of Ddup to d=9.
6.7 Separability Arrangements of Some Regular Polytopes
In Table 7, we provide the Whitney numbers for the separability arrangements corre-
sponding to the remaining two Platonic solids: the icosahedron and the dodecahedron.
This table also contains the Whitney numbers of the separability arrangements of the
vertices of the regular 24-cell, 600-cell, and 120-cell. Except for the 24-cell, each of
these computations uses irrational realizations.
6.8 Discriminantal Arrangements
Given npoints in Rdin general position, the discriminantal arrangement Discd,nis the
hyperplane arrangement in Rdconsisting of the n
dhyperplanes spanned by d-subsets
of such points. This arrangement, originally called the “geometry of circuits” was
introduced by Crapo [11]. We verify the Whitney numbers of Disc4,nfor 5 ≤n≤16
given in [31, Sect. 4.4]. From this data, we recover their formula for the characteristic
polynomial of Disc4,nfor all n. A deformation of this arrangement appears in physics
[8,9] and we were able to confirm the chamber counts given in these papers.
123
1372 Discrete & Computational Geometry (2023) 70:1356–1377
7 Timings
While other pieces of software for counting chambers of arrangements exist, they
do not take advantage of symmetry and some compute significantly more data than
our algorithm does. Consequently, our software outperforms them with respect to the
calculation of Whitney numbers as shown below.
The implementation [29]inpolymake computes much more information than the
Whitney numbers, namely a chamber decomposition of the arrangement. The sage
implementation, on the other hand, uses basic deletion and restriction as in Algorithm 2.
Similarly, the GAP package alcove [33] computes the Tutte polynomial by simple
deletion and restriction and then specializes this to the characteristic polynomial.
To illustrate the performance of our software on the arrangements from Sect. 6,
we collect our timings in Table 1. This table also shows the growth in complexity for
computing the number of chambers of these arrangements. Based on our profiling, the
main bottleneck in our implementation is the identifications of orbits. Thus, improving
pseudo_minimal_image would be the most direct method for making our code
faster.
Acknowledgements This research was completed while the first and third author were at the Max Planck
Institute for Mathematics in the Sciences. The third author was funded by the Deutsche Forschungsgemein-
schaft (DFG, German Research Foundation)—SFB-TRR 358/1 2023—491392403. We are very grateful
to Tommy Hofmann, Christopher Jefferson, and Marek Kaluba for their support regarding the implemen-
tation, and to Michael Cuntz for initial verifications of our computations. We would also like to thank
Michael Joswig for his helpful comments throughout the project and Bernd Sturmfels for suggesting the
discriminantal arrangement. Lastly, we thank the referees for their careful reading and helpful comments.
Funding Open Access funding enabled and organized by Projekt DEAL.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which
permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give
appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence,
and indicate if changes were made. The images or other third party material in this article are included
in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If
material is not included in the article’s Creative Commons licence and your intended use is not permitted
by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the
copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Appendix: Tables of Whitney Numbers
Table 2 Comparison of the effect of number of threads on run times (Intel Core i7-8700)
A#Threads = 1 2 4 8 12
R8(min) 19.8 10.56.35.95.1
T8(h) 8.16 3.92.41.81.6
123
Discrete & Computational Geometry (2023) 70:1356–1377 1373
Table 3 The values of bi(Td)and |ch(Td)|of the threshold arrangement for 1 ≤d≤9and0≤i≤d
d12 3 4 5 6 7 8
b0(Td)11 1 1 1 1 1 1
b1(Td)=|Td|2 4 8 16 32 64 128 256
b2(Td)1 6 28 120 496 2016 8128 32640
b3(Td)3 44 460 4240 36848 310464 2569920
b4(Td)23 820 19660 400400 7493808 133492800
b5(Td)465 43014 2453248 112965776 4626016752
b6(Td)27129 7111650 987779688 103818315888
b7(Td)5023907 4075759064 1382897843304
b8(Td)3193753807 8676817935144
b9(Td)7393243346241
|ch(Td)|2 14 104 1882 94572 15028134 8378070864 17561539552946
Table 4 The values of bi(Rd)and |ch(Rd)|of the resonance arrangement for 1 ≤d≤9and0≤i≤d
d123 4 5 6 7 8 9
b0(Rd)11 1 1 1 1 1 1 1
b1(Rd)=|Rd|1 3 7 15 31 63 127 255 511
b2(Rd)2 15 80 375 1652 7035 29360 120975
b3(Rd)9 170 2130 22435 215439 1957200 17153460
b4(Rd)104 5270 159460 3831835 81029004 1582492380
b5(Rd)3485 510524 37769977 2076831708 96834110730
b6(Rd)371909 169824305 30623870732 3829831100340
b7(Rd)135677633 207507589302 89702833260450
b8(Rd)178881449368 973784079284874
b9(Rd)887815808473419
|ch(Rd)|2 6 32 370 11292 1066044 347326352 419172756930 1955230985997140
We submitted these Whitney numbers to the OEIS as the sequence https://oeis.org/A344494
123
1374 Discrete & Computational Geometry (2023) 70:1356–1377
Table 5 The values of bi(Dd)and |ch(Dd)|of the demicube arrangement for 2 ≤d≤9and0≤i≤d+1
d23 4 5 6 7 8 9
b0(Dd)11 1 1 1 1 1 1
b1(Dd)=|Dd|2 4 8 16 32 64 128 256
b2(Dd)1 6 28 120 496 2016 8128 32640
b3(Dd)0 4 50 500 4480 38304 319200 2622400
b4(Dd)1 44 1160 24340 461496 8283744 143504320
b5(Dd)15 1362 76364 3486448 143595816 5483536464
b6(Dd)597 120942 15440376 1615624080 145378334304
b7(Dd)64903 33803416 10878083096 2574289938400
b8(Dd)21424343 35828091880 27816202212040
b9(Dd)26430009593 146101801794362
b10(Dd)120719853808577
|ch(Dd)|4 16 146 3756 291558 74656464 74904015666 297363155783764
123
Discrete & Computational Geometry (2023) 70:1356–1377 1375
Table 6 The values of bi(Pd)and |ch(Pd)|of the permutohedron arrangement for 1 ≤d≤6and0 ≤i≤d
d123 4 5 6
b0(Pd)11 1 1 1 1
b1(Pd)=|Pd|1 2 6 24 120 720
b2(Pd)1 15 276 7140 258840
b3(Pd)10 1423 246605 59577390
b4(Pd)1170 4290610 9271534305
b5(Pd)4051026 834595018036
b6(Pd)825382803000
|ch(Pd)|2 4 32 2894 8595502 1669309192292
Table 7 The values of bi(A)and |ch(A)|of the icosahedral and dodecahedral arrangements as well as
arrangements stemming from regular 4-polytopes for 0 ≤i≤5
Polytope Icosahedron Dodecahedron 24-Cell 600-Cell 120-Cell
b0(A)11 11 1
b1(A)=|A|12 20 24 120 600
b2(A)66 166 276 7140 179700
b3(A)157 577 1630 225782 31972550
b4(A)102 430 4308 3118740 2979870540
b5(A)– – 2931 2899979 2948077091
|ch(A)|338 1194 9170 6251762 5960100482
References
1. Athanasiadis, Ch.A.: Characteristic polynomials of subspace arrangements and finite fields. Adv. Math.
122(2), 193–233 (1996)
2. Baldi, P., Vershynin, R.: Polynomial threshold functions, hyperplane arrangements, and random tensors.
SIAM J. Math. Data Sci. 1(4), 699–729 (2019)
3. Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing.
SIAM Rev. 59(1), 65–98 (2017)
4. Billera, L.J., Moore, J.T., Moraites, C.D., Wang, Y., Williams, K.: Maximal unbalanced families (2012).
arXiv:1209.2309
5. Bremner, D., Dutour Sikiri´c, M., Pasechnik, D.V., Rehn, Th., Schürmann, A.: Computing symmetry
groups of polyhedra. LMS J. Comput. Math. 17(1), 565–581 (2014)
6. Bremner, D., Dutour Sikiri´c, M., Schürmann, A.: Polyhedral representation conversion up to symme-
tries. In: Polyhedral Computation (Montréal 2006). CRM Proc. Lecture Notes, vol. 48, pp. 45–71.
American Mathematical Society, Providence (2009)
7. Brylawski, T.: The broken-circuit complex. Trans. Am. Math. Soc. 234(2), 417–433 (1977)
8. Cachazo, F., Early, N., Guevara, A., Mizera, S.: Scattering equations: from projective spaces to tropical
Grassmannians. J. High Energy Phys. 2019(6), # 39 (2019)
9. Cachazo, F., Umbert, B., Zhang, Y.: Singular solutions in soft limits. J. High Energy Phys. 2020(5),
# 148 (2020)
10. Chroman, Z., Singhal, M.: Computations associated with the resonance arrangement (2021).
arXiv:2106.09940
123
1376 Discrete & Computational Geometry (2023) 70:1356–1377
11. Crapo, H.: The combinatorial theory of structures. In: Matroid Theory (Szeged 1982). Colloquia
Mathematica Societatis János Bolyai, vol. 40, pp. 107–213. North-Holland, Amsterdam (1985)
12. Crapo, H.H., Rota, G.-C.: On the Foundations of Combinatorial Theory: Combinatorial Geometries.
MIT Press, Cambridge (1970)
13. Cueto, M.A., Morton, J., Sturmfels, B.: Geometry of the restricted Boltzmann machine. In: Algebraic
Methods in Statistics and Probability II (Urbana-Champaign 2009). Contemporary Mathematics, vol.
516, pp. 135–153. American Mathematical Society, Providence (2010)
14. Decker, W., Greuel, G.-M., Pfister, G., Schönemann, H.: Singular 4-2-0—A computer algebra system
for polynomial computations (2020). http://www.singular.uni-kl.de
15. Deza, A., Pournin, L.: A linear optimization oracle for zonotope computation. Comput. Geom. 100,
# 101809 (2022)
16. Evans, T.: What is being calculated with thermal field theory? In: Particle Physics and Cosmology
(Lake Louise 1994), pp. 343–352. World Scientific, Singapore (1995)
17. Fieker, C., Hart, W., Hofmann, T., Johansson, F.: Nemo/Hecke: computer algebra and number theory
packages for the Julia programming language. In: 42nd International Symposium on Symbolic and
Algebraic Computation (Kaiserslautern 2017), pp. 157–164. ACM, New York (2017)
18. Gawrilow, E., Joswig, M.: polymake: a framework for analyzing convex polytopes. In: Polytopes—
Combinatorics and Computation (Oberwolfach 1997). DMV Seminar, vol. 29, pp. 43–73. Birkhäuser,
Basel (2000)
19. Gutekunst, S.C., Mészáros, K., Petersen, T.K.: Root cones and the resonance arrangement. Electron.
J. Comb. 28(1), # P1.12 (2021)
20. Halperin, D., Sharir, M.: Arrangements. In: Handbook of Discrete and Computational Geometry, 3rd
edn, pp. 723–762 (chapter 28). Chapman & Hall/CRC, Boca Raton (2018)
21. Huh, J., Katz, E.: Log-concavity of characteristic polynomials and the Bergman fan of matroids. Math.
Ann. 354(3), 1103–1116 (2012)
22. Jefferson, Ch.: ferret—GAP package, v. 1.0.2 (2019). https://gap-packages.github.io/ferret/
23. Jefferson, Ch., Jonauskyte, E., Pfeiffer, M., Waldecker, R.: Minimal and canonical images. J. Algebra
521, 481–506 (2019)
24. Jefferson, Ch., Pfeiffer, M., Waldecker, R., Jonauskyte, E.: images—GAP package, v. 1.3.0 (2019).
https://gap-packages.github.io/images/
25. Jensen, A.N.: Traversing symmetric polyhedral fans. In: 3rd International Congress on Mathematical
Software (Kobe 2010). Lecture Notes in Computer Science, vol. 6327, pp. 282–294. Springer, Berlin
(2010)
26. Jordan, Ch., Joswig, M., Kastner, L.: Parallel enumeration of triangulations. Electron. J. Comb. 25(3),
# P3.6 (2018)
27. Kaluba, M., Lorenz, B., Timme, S.: Polymake.jl: a new interface to polymake. In: 7th International
Conference on Mathematical Software (Braunschweig 2020). Lecture Notes in Computer Science, vol.
12097, pp. 377–385. Springer, Cham (2020)
28. Kamiya, H., Takemura, A., Terao, H.: Ranking patterns of unfolding models of codimension one. Adv.
Appl. Math. 47(2), 379–400 (2011)
29. Kastner, L., Panizzut, M.: Hyperplane arrangements in polymake. In: 7th International Conference
on Mathematical Software (Braunschweig 2020). Lecture Notes in Computer Science, vol. 12097, pp.
232–240. Springer, Cham (2020)
30. Klivans, C.J., Swartz, E.: Projection volumes of hyperplane arrangements. Discrete Comput. Geom.
46(3), 417–426 (2011)
31. Koizumi, H., Numata, Y., Takemura, A.: On intersection lattices of hyperplane arrangements generated
by generic points. Ann. Comb. 16(4), 789–813 (2012)
32. Kühne, L.: The universality of the resonance arrangement and its Betti numbers. Sém. Lothar. Comb.
85B, # 75 (2021)
33. Leuner, M.: alcove—GAP package (2019). https://github.com/martin-leuner/alcove
34. Möller, T., Röhrle, G.: Counting chambers in restricted Coxeter arrangements. Arch. Math. (Basel)
112(4), 347–359 (2019)
35. Montúfar, G., Ay, N., Ghazi-Zahedi, K.: Geometry and expressive power of conditional restricted
Boltzmann machines. J. Mach. Learn. Res. 16, 2405–2436 (2015)
36. Montúfar, G.F., Morton, J.: When does a mixture of products contain a product of mixtures? SIAM J.
Discrete Math. 29(1), 321–347 (2015)
123
Discrete & Computational Geometry (2023) 70:1356–1377 1377
37. Orlik, P., Solomon, L.: Combinatorics and topology of complements of hyperplanes. Invent. Math.
56(2), 167–189 (1980)
38. Orlik, P., Terao, H.: Arrangements of Hyperplanes. Grundlehren der Mathematischen Wissenschaften,
vol. 300. Springer, Berlin (1992)
39. Pendavingh, R., van der Pol, J.: Asymptotics of symmetry in matroids. J. Comb. Theory B 135, 349–365
(2019)
40. Postnikov, A., Stanley, R.P.: Deformations of Coxeter hyperplane arrangements. J. Comb. Theory A
91(1–2), 544–597 (2000)
41. Sarnoff, J.: SaferIntegers—julia package, v. 2.5.3 (2021). https://github.com/JeffreySarnoff/Safer
Integers.jl
42. Sleumer, N.H.: Output-sensitive cell enumeration in hyperplane arrangements. Nord. J. Comput. 6(2),
137–147 (1999)
43. Solomon, L., Terao, H.: A formula for the characteristic polynomial of an arrangement. Adv. Math.
64(3), 305–325 (1987)
44. Stein, W.A.: Sage Mathematics Software, version x.y.z. The Sage Development Team (2021). http://
www.sagemath.org
45. Yoshinaga, M.: Hyperplane arrangements and Lefschetz’s hyperplane section theorem. Kodai
Math. J. 30(2), 157–194 (2007)
46. Yoshinaga, M.: Freeness of hyperplane arrangements and related topics. Ann. Fac. Sci. Toulouse Math.
23(2), 483–512 (2014)
47. Zaslavsky, Th.: Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyper-
planes. Memoirs of the American Mathematical Society, vol. 154. American Mathematical Society,
Providence (1975)
48. Zuev, Yu.A.: Methods of geometry and probabilistic combinatorics in threshold logic. Discrete Math.
Appl. 2(4), 427–438 (1992)
49. Zunic, J.: On encoding and enumerating threshold functions. IEEE Trans. Neural Netw. 15(2), 261–267
(2004)
50. GAP—Groups, Algorithms, and Programming, v. 4.10.2 (2019). http://www.gap-system.org
51. OSCAR—Computer Algebra System, v. 0.5.2 (2021). https://oscar.computeralgebra.de
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps
and institutional affiliations.
123
