# Random Groups are not n-cubulated

Zachary Munro

###### Abstract.

A group $G$ has $F\mathcal{C}_{n}$ if every action on a $n$-dimensional
$\mathrm{CAT}(0)$ cube complex has a global fixed point. This provides a
natural stratification between Serre’s $FA$ and Kazhdan’s $(T)$. For every
$n$, we show that random groups in the plain words density model have
$F\mathcal{C}_{n}$ with overwhelming probability. The same result holds for
random groups in the reduced words density model assuming there are
sufficiently many generators. These are the first examples of cubulated
hyperbolic groups with $F\mathcal{C}_{n}$ for $n$ arbitrarily large.

##  1\. Introduction

The density model of random groups, defined by Gromov in [Gro91], gives
credence to the claim that “most” groups are $\delta$-hyperbolic. The model
depends upon a parameter $d\in(0,1)$, the _density_ , and a parameter
$L\in\mathbf{N}$, the _length_. One typically fixes $d$ and studies properties
of a random group as $L\to\infty$. A random group at density $d$ is said to
satisfy a property $Q$ _with overwhelming probability_ if the probability that
$Q$ holds goes to $1$ as $L\to\infty$. This is analogous to the study of
random graphs in the Erdős–Renyi model $G(n,p)$, in which one typically fixes
$p$, the probability of adding an edge, and takes the number of vertices
$n\to\infty$. More precise definitions are given in Section 5.

A random group is defined by a presentation, and the relators are randomly
selected from a set of words of length $L$. We work mainly in the _plain words
model_ , in which the relators of the defining presentation are selected from
all words of length $L$. In the _reduced words model_ , the relators are
selected from the reduced words of length $L$.

Random groups in the reduced words model behave vastly differently above and
below the critical density $d=\frac{1}{2}$. Random groups at densities
$d<\frac{1}{2}$ are infinite hyperbolic, but random groups at densities
$d>\frac{1}{2}$ are either trivial or $\mathbf{Z}/2\mathbf{Z}$ [Gro91, Oll04].
Ollivier proved that a similar phase transition takes place in the plain words
model, but with critical density $d=1-\theta$, where $\theta>\frac{1}{2}$
depends on the number of generators [Oll04, Theorem 4], and
$\theta\to\frac{1}{2}$ as $k\to\infty$. The density model of random groups has
proven to be both a fruitful testing ground for conjectures and an important
source of examples in group theory. For example, Calegari and Walker were able
to give a positive answer to Gromov’s surface subgroup question for reduced
word random groups [CW15]. And both the reduced and plain word models provide
many examples of non-left-orderable and property (T) groups [Orl17],[KK13,
Ż03].

We study the actions of random groups on $\mathrm{CAT}(0)$ cube complexes.
Despite the increasing popularity of $\mathrm{CAT}(0)$ cube complexes in the
past few decades, the study of fixed-point properties for actions on
$\mathrm{CAT}(0)$ cube complexes has been relatively neglected. We will take
particular interest in the following fixed-point property for actions on
finite-dimensional $\mathrm{CAT}(0)$ cube complexes.

######  Definition 1.1.

A group $G$ has property $F\mathcal{C}_{n}$ if for every action of $G$ on an
$n$-dimensional $\mathrm{CAT}(0)$ cube complex, the fixed-point set of $G$ is
nonempty. We let $F\mathcal{C}_{\infty}\vcentcolon=\cap F\mathcal{C}_{n}$, and
we say $G$ has $F\mathcal{C}$ if for every action on a $\mathrm{CAT}(0)$ the
fixed-point set is nonempty. Note that property $F\mathcal{C}_{1}$ is exactly
Serre’s property $FA$, and property $(T)$ is stronger than any of the above
fixed-point properties. For a recent discussion on known results regarding
$F\mathcal{C}_{n}$ along with many open questions, see [Gen23].

The properties $F\mathcal{C}_{n}$ can be thought of as a stratification
between the well-studied properties $FA$ and $(T)$. That is, one has the
following inclusions

$FA=F\mathcal{C}_{1}\supset F\mathcal{C}_{2}\supset\cdots\supset
F\mathcal{C}_{\infty}\supset F\mathcal{C}\supset(T).$

At density $d>1/3$, random groups with either plain or reduced words have
property (T) [KK13, Ż03], and thus, every action on a finite-dimensional
$\mathrm{CAT}(0)$ cube complex has a global fixed-point [NR97]. However, at
lower densities this changes. Ashcroft proved that random groups in the
reduced words model at density $d<1/4$ act without global fixed-point on
finite-dimensional $\mathrm{CAT}(0)$ cube complexes [Ash22]. Even more
strongly, random groups with reduced words at density $d<1/12$ satisfy the
$C^{\prime}(1/6)$ small-cancellation condition [Gro91, §9.B], and Wise proved
that $C^{\prime}(1/6)$ groups act properly and cocompactly on
$\mathrm{CAT}(0)$ cube complexes [Wis04]. Ollivier and Wise strengthened this
result to include random groups in the reduced words model at density $d<1/6$
[OW11]. The above results contrast sharply with the main theorem of the
article, stated below.

######  Theorem 1.2.

For any $d\in(0,1)$ and $n\in\mathbf{N}$, a random group in the plain words
density model at density $d$ has property $F\mathcal{C}_{n}$ with overwhelming
probability.

In a sense, this is the strongest result one could hope for, since it holds
for any density $d\in(0,1)$ and any dimension $n\in\mathbf{N}$. As mentioned
above, the statement was previously known to hold for $d>\frac{1}{3}$ and any
$n\in\mathbf{N}$ by invoking property (T). However, our result circumvents the
use of property (T). For statements concerning all densities $d\in(0,1)$, the
theorem was only known to hold in the cases $n=1$ [DGP11] and $n=2$ [Mun22].
In the context of small-cancellation, Jankiewicz constructed, for each $p\geq
6$ and $n\in\mathbf{N}$, examples of $C^{\prime}(1/p)$ groups which do not act
properly on any $n$-dimensional $\mathrm{CAT}(0)$ cube complex [Jan20].

The proof of Theorem 1.2 is inspired by [Jah11, DGP11]. In particular, for
each $n\in\mathbf{N}$, we construct a finite family of automata such that the
following holds: for any action of a free group on an $n$-dimensional
$\mathrm{CAT}(0)$ cube complex, there exists an automaton in our family whose
accepted language consists entirely of words which act nontrivially on the
cube complex. Moreover, the accepted languages of the automata in our family
are, in a suitable sense, “dense”. By modifying our automata to accept only
reduced words, we can prove Theorem 1.2 in the reduced words density model,
supposing there are sufficiently many generators.

######  Theorem 1.3.

For every $n\in\mathbf{N}$, there exists $k(n)>0$ such that the following
holds: For any $d\in(0,1)$, a random group in the reduced words model with
density $d$ and $k\geq k(n)$ generators has property $F\mathcal{C}_{n}$ with
overwhelming probability.

As a corollary of Theorem 1.3, we are able to strengthen the main theorem of
[Jan20], mentioned above. In fact, for $p\geq 6$, we are able to show that a
strong version of the theorem holds for generic $C^{\prime}(1/p)$ groups as
relator length tends to infinity. Recall the following definition from
[Jan20]: The _cubical dimension_ of $G$ is the minimal $n$ such that $G$ acts
properly on an $n$-dimensional $\mathrm{CAT}(0)$ cube complex. Note the
cubical dimension of a group with $F\mathcal{C}_{n}$ must be greater than $n$.

######  Corollary 1.4.

Fix $n\in\mathbf{N}$ and $0<d<\frac{1}{2p}$ with $p\geq 6$. Let $k(n)$ be as
in Theorem 1.3. Let $G$ be a random group in the reduced words density model
at density $d$ with $k\geq k(n)$ generators. Then with overwhelming
probability, $G$ is $C^{\prime}(1/p)$ and has $F\mathcal{C}_{n}$. In
particular, there exist $C^{\prime}(1/p)$ groups with arbitrarily high cubical
dimension.

###### Proof.

It is a theorem of Gromov that $G$ is $C^{\prime}(1/p)$ with overwhelming
probability [Gro91, §9.B]. See also [OW11, Proposition 1.8]. By Theorem 1.3,
$G$ has property $F\mathcal{C}_{n}$ with overwhelming probability. ∎

Genevois constructs cubulated groups with $F\mathcal{C}_{n}$ for arbitrarily
large $n$ [Gen23]. However, the groups he constructs are virtually free
abelian. Corollary 1.4 provides the first examples of cubulated hyperbolic
groups with $F\mathcal{C}_{n}$ for arbitrarily large $n$.

Theorem 1.2 and Theorem 1.3 produce many examples of groups with
$F\mathcal{C}_{n}$ but not $F\mathcal{C}_{\infty}$. To produce a group with
$F\mathcal{C}_{\infty}$, Corollary 1.4 can be utilized in a construction
similar to that in [JW21] to form an infinite $C^{\prime}(1/6)$ complex $Z$
with $F\mathcal{C}_{\infty}$ fundamental group. Thus $\pi_{1}Z$ acts freely on
a locally-finite $\mathrm{CAT}(0)$ cube complex, but every action of
$\pi_{1}Z$ on a finite-dimensional $\mathrm{CAT}(0)$ cube complex has a global
fixed point. Previously, it was known that Thompson’s group $V$ has
$F\mathcal{C}_{\infty}$ [Gen19] yet acts freely on a locally-finite
$\mathrm{CAT}(0)$ cube complex [Far05]. However, the example below is the
first with cohomological dimension $2$.

######  Theorem 1.5.

There exists a finitely generated $F\mathcal{C}_{\infty}$ group with
cohomological dimension $2$ acting freely on a locally-finite
$\mathrm{CAT}(0)$ cube complex.

Given a finitely presented group $G=\langle S\mid R\rangle$, the _Rips
construction_ produces another finitely presented group $\Gamma=\langle
S\cup\\{x,y\\}\mid R^{\prime}\rangle$ satisfying $C^{\prime}(1/p)$ so that
there exists a short exact sequence $1\to\langle x,y\rangle\to\Gamma\to G\to
1$ [Rip82]. If $G$ has $F\mathcal{C}_{n}$, then Theorem 1.3 can be used to
perform a variation of the Rips construction so that $\Gamma$ is
$C^{\prime}(1/p)$ and has $F\mathcal{C}_{n}$. More precisely, we have the
following.

######  Corollary 1.6 ($F\mathcal{C}_{n}$ Rips Construction).

Let $G$ be a finitely presented group with property $F\mathcal{C}_{n}$. For
any $p\geq 6$ and $n\in\mathbf{N}$, $G$ fits into a short exact sequence of
the form

$1\to F\to\Gamma\to G\to 1,$

where $F$ is a finitely generated nonabelian free group and $\Gamma$ is
$C^{\prime}(1/p)$ and has property $F\mathcal{C}_{n}$. In fact, if $G=\langle
a_{1},\ldots a_{m}\mid r_{1},\ldots r_{l}\rangle$, then with overwhelming
probability the statement holds for $\Gamma=\langle
a_{1},\ldots,a_{m},b_{1}\ldots,b_{k(n)}\mid
r_{1}B_{1},\ldots,r_{l}B_{l},a_{i}b_{j}a_{i}^{-1}=B_{i,j},\mathcal{B}\rangle$
where $\mathcal{B}\cup\\{B_{1},\ldots,B_{l}\\}\cup\\{B_{i,j}\\}_{1\leq i\leq
m,1\leq j\leq k(n)}$ is a random set of reduced words of length $L$ and
density $d<\frac{1}{2p}$ in the free group $F=\langle
b_{1}\ldots,b_{k(n)}\rangle$.

To prove Corollary 1.6, we establish a a combination result for short exact
sequences of $F\mathcal{C}_{n}$ groups which may be of independent interest.

######  Lemma 1.7.

If $K$ and $N$ have property $F\mathcal{C}_{n}$, and $G$ fits into a short
exact sequence of the form

$1\to K\to G\to N\to 1,$

then $G$ has property $F\mathcal{C}_{n}$.

In Section 2, we define and establish notation for words and $\mathrm{CAT}(0)$
cube complexes. In Section 3, we define progressing automata, a main tool in
our proofs. These were originally defined by the author in [Mun22] to settle
the $n=2$ case of the above theorems, but our treatment here differs slightly
from the original. Given a $\mathrm{CAT}(0)$ cube complex $X$ and a finite set
of isometries $S=\\{s_{1},\ldots,s_{k}\\}$ of $X$, we would like to construct
an automaton accepting only words over $S$ which act nontrivially on $X$.
Nontriviality would follow if there existed a point $x\in X$ translated by
every accepted word, and this observation motivates the definition of a
progressing automaton. Roughly, the defining feature of a progressing
automaton is this: For a fixed point $x\in X$, if a word $w$ is accepted and
$wx\neq x$, then $ws$ is accepted only if $wsx$ is at least as far from $x$ as
$wx$. This ensures $wsx\neq x$. The main theorems follow easily from the
existence of a suitably rich family of progressing automaton, and thus, the
main difficulty rests in constructing such a family. Section 4 is the
technical heart of the paper. We perform a case analysis, ensuring that for
any set of isometries $S=\\{s_{1},\ldots,s_{k}\\}$ there always exists a
progressing automaton. In a $\mathrm{CAT}(0)$ cube complex, if $wx\neq x$ then
there exists a hyperplane separating $wx$ and $x$. Suppose $H$ is such a
hyperplane closest to $wx$. The case analysis is done by partitioning $S$: The
isometries which move $wx$ off the carrier $N(H)$ away from $x$, advancing the
progression, are denoted $\mathcal{A}(H)$; the isometries which keep $wx$ on
the carrier $N(H)$, moving it to a parallel position, are denoted
$\mathcal{P}(H)$; and the isometries which move $wx$ off $N(H)$ towards $x$,
backtracking the progression, are denoted $\mathcal{B}(H)$. It should be
intuitively clear that progression is easy when there are many ways to
advance, i.e., $\mathcal{A}(H)$ is large, and the most difficult cases are
occur without many ways to advance, i.e., $\mathcal{A}(H)$ is small. When this
happens, either $\mathcal{B}(H)$ or $\mathcal{P}(H)$ must be large, and these
difficult cases are handled by Lemma 4.11 and Lemma 4.15, respectively. In
Section 5, we use the existence of a bounded size progressing automaton to
prove Theorem 1.2. We then sketch how to modify the automata to prove Theorem
1.3 using methods in [DGP11, Mun22].

Acknowledgements. Thank you Piotr Przytycki for asking me if random groups
have a cubical fixed-point property years ago. Also, thank you for the many
conversations we shared over those years. You were an important source of
knowledge and motivation. Thanks to Dani Wise for sharing his knowledge and
passion for cubes. And thank you Harry Petyt for encouraging me to get off our
couch and to work on this article.

##  2\. Preliminaries

###  2.1. Words and subwords

Let $S=\\{s_{1},\ldots,s_{k}\\}$ be a set of formal letters,
$S^{-1}=\\{s_{1}^{-1},\ldots,s_{k}^{-1}\\}$ the set of formal inverses, and
$S^{\pm}=S\cup S^{-1}$. Let $F_{S}$ be the free group over $S$. Then elements
of $S^{\pm}$ can be viewed both as formal symbols or as group elements.

A _word $w$ over $S^{\pm}$_ is a string of elements from $S^{\pm}$. This can
be formalized as a function $w:[i,j]\subset\mathbf{Z}\to S^{\pm}$, in which
case $w$ is a word of _length_ $|w|\vcentcolon=j-i+1$. In this setting, words
are defined up to translations of the domain $[i,j]$. A _subword_ $w^{\prime}$
of $w$ is a restriction of $w$ to some subinterval
$[i^{\prime},j^{\prime}]\subset[i,j]$, which we denote by writing
$w^{\prime}\subset w$. A subword $w^{\prime}\subset w$ is a _prefix_ if
$i^{\prime}=i$ and a _suffix_ if $j^{\prime}=j$. A subword is _proper_ if
$[i^{\prime},j^{\prime}]\subset[i,j]$ is a proper subset. We allow empty
intervals, and the word $w:\emptyset\to S^{\pm}$ is the _empty word_.

If $w$ and $w^{\prime}$ are words of length $l$ and $l^{\prime}$, then their
_concatenation_ $ww^{\prime}$ is the word of length $l+l^{\prime}$
characterised by having $w$ as prefix and $w^{\prime}$ as a suffix. A
_language_ $\mathcal{L}$ is a set of words. For a word $r$ and language
$\mathcal{L}$, we define $r\mathcal{L}=\\{rw:w\in\mathcal{L}\\}$. Similarly,
$\mathcal{L}r=\\{wr:w\in\mathcal{L}\\}$.

###  2.2. $\mathrm{CAT}(0)$ cube complexes

A _$n$ -cube_ is $[-1,1]^{n}$, endowed with the $\ell^{2}$-metric. A _face_ of
a cube is a subspace defined by restricting some coordinates to $1$ or $-1$. A
face naturally has the structure of a cube. For example, the $2$-cube
$[-1,1]^{2}$ has four $1$-cube faces: $\\{-1\\}\times[-1,1]$,
$\\{1\\}\times[-1,1]$, $[-1,1]\times\\{-1\\}$, and $[-1,1]\times\\{1\\}$. A
_cube complex_ is constructed from a collection of cubes by identifying some
faces via isometries. The _dimension_ of a cube complex is the maximal
dimension of a cube in the collection. For example, a 1-dimensional cube
complex is a graph. Similarly, a _simplex complex_ is a complex built from
simplicies by identifying faces via isometries. Simplicial complexes are
exactly those simplex complexes such that simplicies are uniquely identified
by their 0-cells. A simplicial complex is _flag_ if each set of pairwise
adjacent 0-simplicies spans a simplex.

A corner of an $n$-cube can be naturally associated to an $(n-1)$-simplex,
where the ends of $1$-cubes at the corner correspond to the 0-cells of the
simplex. Under this correspondence, codimension-$k$ faces of the simplex are
in bijection with the codimension-$k$ faces of the cube at the corner. A
similar construction exists for general cube complexes. Let $X$ be a cube
complex. The _link_ of a $0$-cube $x\in X$ is the simplex complex
$\operatorname{Link}(x)$ with an $(n-1)$-simplex for each corner of an
$n$-cube containing $x$, and faces of simplicies are identified if the
corresponding corners of faces of cubes are identified.

A cube complex $X$ is _nonpositively curved_ if $\operatorname{Link}(x)$ is a
flag simplicial complex for each $0$-cube $x$ of $X$. A $\mathrm{CAT(0)}$
_cube complex_ is a simply-connected nonpositively curved cube complex. A
_midcube_ of a cube is the subspace defined by restricting one of the
coordinates to 0, e.g. the $2$-cube has two midcubes $\\{0\\}\times[-1,1]$ and
$[-1,1]\times\\{0\\}$. Midcubes naturally have the structure of a cube. Let
$\Upsilon(X)$ be the cube complex formed from copies of midcubes of $X$ glued
along common midcubes. There is a natural immersion
$\Upsilon(X)\looparrowright X$. A _hyperplane_ $H\looparrowright X$ is a
connected component of $\Upsilon(X)$. The inclusion of a midcube in a cube
$m\hookrightarrow C$ can be extended to an isomorphism $m\times[-1,1]\to C$.
Extending midcube inclusions in this fashion yields an immersion
$N(H)\looparrowright X$ of the _carrier_ $N(H)\vcentcolon=H\times[-1,1]$ of
the hyperplane $H$.

The following theorem is standard in the study of $\mathrm{CAT}(0)$ cube
complexes. For proofs see [Sag14, Theorem 1.1], [Wis21, Lemma 2.14].

######  Theorem 2.1.

Let $X$ be a $\mathrm{CAT}(0)$ cube complex, and let $H$ be a hyperplane of
$X$.

  1. (1)

The map $N(H)\looparrowright X$ is an embedding.

  2. (2)

The image $N(H)\subset X$ is a convex subcomplex.

  3. (3)

$H$ and $N(H)$ are $\mathrm{CAT}(0)$ cube complexes.

  4. (4)

Every collection of pairwise intersecting hyperplanes has nonempty
intersection.

This theorem has several important consequences. For one, since a midcube is
two-sided, i.e., a neighborhood of $m\subset C$ is homeomorphic to
$m\times(-\epsilon,\epsilon)$, hyperplanes in a $\mathrm{CAT}(0)$ cube complex
are two-sided. Thus the complemenent of a hyperplane $X-H$ has two components.
The two components of $X-H$ are the _halfspaces_ of $H$. Additionally, if a
$0$-cube $x$ lies in a cube intersecting $H$, then $x\in N(H)$ and there is a
unique _opposite_ $y\in N(H)$ given by the product structure
$N(H)=H\times[-1,1]$. Finally, if $k$ hyperplanes pairwise intersect, then
there exists a $k$-cube whose midcubes correspond to each of the $k$
hyperplanes. Thus, in an $n$-dimensional $\mathrm{CAT}(0)$ cube complex no
more than $n$ hyperplanes can pairwise intersect.

The $\ell^{p}$-metric on $X$ is the path metric where each cube of $X$ has
been given the $\ell^{p}$-metric. We will work mainly with the
$\ell^{1}$-metric of a $\mathrm{CAT}(0)$ cube complex, denoted
$(X,\mathsf{d})$. The $\ell^{1}$-metric restricted to the $0$-cubes $X^{0}$
agrees with the graph metric on $X^{1}$. That is, the $\ell^{1}$-distance
between $0$-cubes is equal to the number of $1$-cubes in a shortest chain of
$1$-cubes joining them. In general, the $\ell^{1}$-metric is not
$\mathrm{CAT}(0)$ — the $\ell^{2}$-metric is $\mathrm{CAT}(0)$. We say a
subcomplex $A\subset X$ is _convex_ if every $\ell^{1}$-geodesic joining
$0$-cubes of $A$ lies in $A$. We define $\mathsf{d}(A,B)\vcentcolon=\inf_{a\in
A,b\in B}\mathsf{d}(a,b)$ for convex subcomplexes $A,B\subset X$. The
$\ell^{1}$-metric is determined by the hyperplanes of $X$ in a way we now
precise. A hyperplane $H$ _separates_ subsets $A,B\subset X$ if $A$ and $B$
lie in distinct halfspaces of $H$. For subsets $A,B\subset X$, we let
$\\#(A,B)$ denote the number of hyperplanes separating $A$ and $B$. The
following lemma follows from [Wis21, Corollary 2.15] and [Wis21, Lemma 2.18].

######  Lemma 2.2.

For convex subcomplexes $A,B\subset X$, $\mathsf{d}(A,B)=\\#(A,B)$.

In particular, $\mathsf{d}(x,y)=\\#(x,y)$ for $0$-cubes $x,y\in X$. And for
some a hyperplane $H$ and $0$-cube, $x\not\in N(H)$ if and only if there
exists a hyperplane $H^{\prime}$ separating $x$ and $N(H)$.

We conclude this section with some definitions regarding the arrangement of
hyperplanes. Two hyperplanes $H\neq H^{\prime}$ of $X$ _cross_ if and $H\cap
H^{\prime}\neq\emptyset$. This is denoted $H\pitchfork H^{\prime}$. Two
hyperplanes $H\neq H^{\prime}$ are _parallel_ if $H\cap H^{\prime}=\emptyset$.
This is denoted $H\parallel H^{\prime}$. Note if $H$ and $H^{\prime}$ are
noncrossing, it is possible that $H=H^{\prime}$.

##  3\. Progressing Automata

Let $S$, $S^{-}$, $S^{\pm}$ and $F_{S}$ be as in Section 2. An action of
$F_{S}$ on a $\mathrm{CAT}(0)$ cube complex $X$ amounts to a map
$S\to\operatorname{Isom}(X)$ extending to a map
$S^{\pm}\to\operatorname{Isom}(X):s\to\hat{s}$. When an action of $F_{S}$ has
been fixed, we use $\hat{s}$ to denote the isometry of $X$ associated to $s\in
S^{\pm}$, and we let $\hat{s}^{-1}\vcentcolon=\widehat{s^{-1}}$. More
generally, for a word $w\in F_{S}$, $\hat{w}$ denotes the image of $w$ under
the map $F_{S}\to\operatorname{Isom}(X)$. As a convention, if $w$ is the empty
word, then $\hat{w}$ is the identity transformation on $X$.

######  Definition 3.1.

A _graph_ $\Sigma$ is a 1-complex whose 0-cells we call _vertices_ and whose
1-cells we call _edges_. A _directed edge_ is an edge with a fixed
orientation. A graph is _directed_ if each edge is directed. If $\Sigma$ is
directed, then a path $P\to\Sigma$ is _directed_ if it traverses each edge in
an orientation-respecting manner. A _vertex/edge labeling_ associates to each
vertex/edge of a graph an element of some label set. An edge labeling of a
directed graph is _deterministic_ if the outgoing edges at each vertex have
distinct labels. Our label set will most often be $S^{\pm}$. An edge labeling
of $\Sigma$ induces an edge labeling of any path $P\to\Sigma$. A _tree_ is a
graph $\Sigma$ with $\pi_{1}\Sigma$ trivial. A _leaf_ of a tree is a vertex
belonging to only one edge. A _rooted tree_ $\Sigma$ is a tree with a
distinguished vertex, the _root_. A path $P\to\Sigma$ is _rooted_ if the
initial vertex of $P$ is the root of $\Sigma$. As a convention, we orient
edges of a rooted tree away from the root. Let $\Sigma$ be a rooted tree. A
vertex $v$ is a _descendant_ of $u$ if there exists a nontrivial directed path
$P\to\Sigma$ with initial vertex $u$ and terminal vertex $v$. If $P$ has
length one, then $v$ is a _child_ of $u$. If $v$ is a descendant of $u$, then
$u$ is an _ancestor_ of $v$. Suppose $T$ is a labeled, rooted tree with label
set $S^{\pm}$. We define an operation $\tilde{\cdot}$ interchanging between
vertices of $T$ and words over $S^{\pm}$: For a vertex $v\in T$, $\tilde{v}$
is the label of the unique rooted, directed path $P\to T$ terminating on $v$.
If $w$ is a word over $S^{\pm}$, then $\tilde{w}$ denotes the set of terminal
vertices of rooted, directed paths $P\to T$ with label $w$. For a vertex $v\in
T$, we let $c(v)$ be the set of children of $v$ and $\tilde{c}(v)$ be the set
of labels on edges joining $v$ to its children.

The following is a result of a procedure commonly referred to as _folding_
[Sta83]. Any combinatorial map $\Gamma\to\Sigma$ between graphs factors
through a series of quotient maps
$\Gamma=\Gamma_{0}\to\cdots\to\Gamma_{n}\to\Sigma$ so that the final map is an
immersion $\Gamma_{n}\looparrowright\Sigma$. Each $\Gamma_{i}\to\Gamma_{i+1}$
identifies two edges of $\Gamma_{i}$ and the following diagram commutes:

${\Gamma_{i}}$${\Gamma_{i+1}}$${\Sigma}$

A _finite state automaton (FSA) over $S$_, or simply, an _automaton over $S$_,
is a finite directed graph $\Sigma$ with an edge labeling over $S^{\pm}$ and a
distinguished _start vertex_ $\mathfrak{s}$. A word $w$ is _accepted_ by
$\Sigma$ if it is the label of a directed path $P\to\Sigma$ beginning at
$\mathfrak{s}$. The _accepted language_ $\mathcal{L}_{\Sigma}$ is the set of
all accepted words.

######  Definition 3.2.

A vertex $v$ of a FSA has _$\lambda$ -large growth_ if there are at least
$\lambda|S^{\pm}|$ outgoing edges at $v$. A FSA has _$\lambda$ -large growth_
if there exists some $K>0$ so that each directed path $P\to\Sigma$ of length
at least $K$ ends on a vertex with $\lambda$-large growth.

######  Definition 3.3.

Fix an action of $F_{S}$ on a $\mathrm{CAT}(0)$ cube complex $X$ and a
_basepoint_ $0$-cube $x\in X$. For $s\in S^{\pm}$, let $\mathcal{H}_{s}$ be
the set of hyperplanes $H$ separating $x$ and $sx$ such that no hyperplane
separates $x$ and $H$. Equivalently, by Lemma 2.2, $\mathcal{H}_{s}$ is the
set of hyperplanes $H$ separating $x$ and $sx$ such that $x\in N(H)$. The
_visible_ hyperplanes are $\mathcal{H}=\cup_{s\in S^{\pm}}\mathcal{H}_{s}$.
Evidently, $\mathcal{H}$ highly depends on the action of $F_{S}$ on $X$ and
the choice of basepoint. A FSA $\Sigma=(V,E)$ is _progressing_ if there exists
a nonempty set of _checkpoint_ vertices $C\subset V-\\{\mathfrak{s}\\}$ and a
labeling $H:C\to\mathcal{H}$ such that the following hold:

  1. (1)

Let $P\to\Sigma$ be a directed path beginning at $\mathfrak{s}$ with label $w$
such that either $P$ does not meet $C$ or $P$ meets $C$ only at its terminal
vertex. Then $\hat{w}x\neq x$. If the terminal vertex of $P$ is $c\in C$, then
$\hat{w}H(c)$ separates $x$ and $\hat{w}x$.

  2. (2)

Let $P\to\Sigma$ be a directed path with label $w$ such that $P$ meets $C$
only at its initial vertex or only at its initial and terminal vertices.
Suppose in the first case that the initial vertex of $P$ is $c_{1}\in C$. Then
$\hat{w}x$ lies in the same halfspace of $H(c_{1})$ as $x$. If the intial and
terminal vertices of $P$ are $c_{1}\in C$ and $c_{2}\in C$, then either
$\hat{w}H(c_{2})=H(c_{1})$, or $\hat{w}H(c_{2})$ is parallel to $H(c_{1})$ and
separates $x$ and $\hat{w}x$.

Observe that a progressing automaton $\Sigma$ has the following associated
data: an action of $F_{S}$ on $X$, a set of checkpoints $C\subset
V-\\{\mathfrak{s}\\}$, a labeling $H:C\to\mathcal{H}$, and a basepoint $x\in
X$.

######  Lemma 3.4.

Let $\Sigma$ be a progressing automaton, and let $P\to\Sigma$ be a directed
path with label $w$ beginning on $\mathfrak{s}$. Then $\hat{w}x\neq x$.

###### Proof.

If $P$ does not meet any checkpoint vertices, then the lemma follows from
Definition 3.3.(1). Otherwise, let $c_{1},\ldots,c_{n}$ be the checkpoint
vertices that $P$ meets, in order. Let $w_{1}$ be the label of the initial
subpath $P_{1}$ joining $\mathfrak{s}$ to $c_{1}$, let $w_{i}$ be the label of
the subpath $P_{i}$ joining $c_{i-1}$ to $c_{i}$ for $i=2,\ldots,n$, and let
$w_{n+1}$ be the label of the terminal subpath $P_{n+1}$ meeting $C$ only at
its initial vertex. We begin by inductively proving that
$\hat{w}_{1}\cdots\hat{w}_{i}H(c_{i})$ separates $x$ and
$\hat{w}_{1}\cdots\hat{w}_{i}x$.

Definition 3.3.(1) applied to $P_{1}$ implies that $\hat{w}_{1}H(c_{1})$
separates $x$ and $\hat{w}_{1}x$. Suppose now that $\hat{w}^{\prime}H(c_{i})$
separates $x$ and $\hat{w}^{\prime}x$ where
$w^{\prime}=\hat{w}_{1}\cdots\hat{w}_{i}$. Definition 3.3.(2) applied to
$P_{i+1}$ implies $\hat{w}_{i+1}H(c_{i+1})$ separates $x$ and
$\hat{w}_{i+1}x$. Additionally, $\hat{w}_{i+1}H(c_{i+1})$ is either equal or
parallel to $H(c_{i})$. Multiplying with $\hat{w}^{\prime}$ shows
$\hat{w}^{\prime}\hat{w}_{i+1}H(c_{i+1})$ separates $\hat{w}^{\prime}x$ and
$\hat{w}^{\prime}\hat{w}_{i+1}x$, and
$\hat{w}^{\prime}\hat{w}_{i+1}H(c_{i+1})$ is either equal or parallel to
$\hat{w}^{\prime}H(c_{i})$. Since $\hat{w}^{\prime}H(c_{i})$ separates $x$ and
$\hat{w}^{\prime}x$, we get that $\hat{w}^{\prime}\hat{w}_{i+1}H(c_{i+1})$
separates $x$ and $\hat{w}^{\prime}\hat{w}_{i+1}x$.

The path $P$ decomposes as $P_{1}\cdots P_{n+1}$, and we have shown that
$\hat{w}_{1}\cdots\hat{w}_{n}H(c_{n})$ separates $x$ and
$\hat{w}_{1}\cdots\hat{w}_{n}x$. Definition 3.3.(2) applied to $P_{n+1}$
implies $x$ and $w_{n+1}x$ lie in the same halfspace of $H(c_{n})$.
Multiplying by $\hat{w}_{1}\cdots\hat{w}_{n}$, we get that
$\hat{w}_{1}\cdots\hat{w}_{n}x$ and $\hat{w}x$ lie in the same halfspace of
$\hat{w}_{1}\cdots\hat{w}_{n}H(c_{n})$. Thus $\hat{w}x\neq x$. ∎

######  Corollary 3.5.

Suppose $\Sigma$ is progressing with respect to a basepoint $x$. Then
$\hat{w}x\neq x$ for each accepted word $w\in\mathcal{L}_{\Sigma}$.

###### Proof.

The accepted language $\mathcal{L}_{\Sigma}$ is exactly the set of labels of
directed paths $P\to\Sigma$ beginning at $\mathfrak{s}$. Thus the corollary
follows from Lemma 3.4. ∎

##  4\. Partitioning $\mathcal{H}$ and Progressing

######  Definition 4.1.

Let $S^{\pm}\to\operatorname{Isom}(X)$ be the map associated to an action of
$F_{S}$ on $X$, $\mathrm{CAT}(0)$ cube complex, and let $x\in X$ be a
basepoint $0$-cube. Let $\mathcal{H}$ be the set of visible hyperplanes. Let
$w$ be a reduced word over $S^{\pm}$, and let $\mathfrak{s}$ be a formal
letter not in $S^{\pm}$. A pair $(w,\mathfrak{s})$ is _progressing_ if
$\hat{w}^{\prime}x\neq x$ for each prefix $w^{\prime}\subset w$, and
$\hat{w}H^{\prime}$ separates $x$ and $\hat{w}x$ for some
$H^{\prime}\in\mathcal{H}$. Let $H\in\mathcal{H}$. A pair $(w,H)$ is
_progressing_ if for each prefix $w^{\prime}\subset w$, $H$ does not separate
$x$ and $\hat{w}^{\prime}x$, and for some $H^{\prime}\in\mathcal{H}$ either
$\hat{w}H^{\prime}=H$, or $\hat{w}H^{\prime}$ is parallel to $H$ and separates
$x$ and $\hat{w}x$. In each of the above cases, we say $H^{\prime}$
_witnesses_ the progression of $(w,H)$.

Let $H\in\mathcal{H}\cup\\{\mathfrak{s}\\}$, and consider a collection of
progressing pairs $\\{(w_{i},H)\\}_{i\in I}$. For each $i\in I$, let $H_{i}$
be a witness for the progression of $(w_{i},H)$. Let $B_{S}$ be a bouquet of
directed circles labeled bijectively by $S$, and for each $i$, let
$P_{i}\looparrowright B_{S}$ be an immersed path with label $w_{i}$. Let
$\Gamma\looparrowright B_{S}$ be the immersed graph produced by folding
$\bigvee_{i\in I}P_{i}\to B_{S}$, where $\bigvee_{i\in I}P_{i}$ is the wedge
sum of the $P_{i}$ along their initial vertices. Each edge of $\Gamma$ has a
label from $S^{\pm}$ induced by the immersion $\Gamma\looparrowright B_{S}$.
The wedge sum $\bigvee_{i\in I}P_{i}$ has the structure of a rooted tree,
where the root is the common initial vertex of the $P_{i}$, and since folding
does not introduce any cycles, $\Gamma$ is also a rooted tree. The _realized
tree_ of $\\{(w_{i},H)\\}_{i\in I}$ is $\Gamma$ with a partial vertex
labeling: the root is labeled $H$ and each leaf of $\Gamma$, which corresponds
to a terminal vertex of some $P_{i}\subset\Gamma$, is labeled $H_{i}$. Recall
that, as a convention, the edges of a rooted tree are directed away from the
root. A tree $T_{H}$ which is the realized tree of a collection of progressing
pairs $\\{(w_{i},H)\\}_{i\in I}$ is a _checkpoint tree at $H$_.

######  Definition 4.2.

A nontrivial checkpoint tree $T_{H}$ has _$\lambda$ -large growth_ if either
$H=\mathfrak{s}$ or, in the case that $H\in\mathcal{H}$, each nonleaf vertex
has $\lambda|S^{\pm}|$ outgoing edges. The _realized automaton_ of a set of
checkpoint trees $\\{T_{H}\\}_{H\in\mathcal{H}\cup\\{\mathfrak{s}\\}}$ is the
union of the $T_{H}$ with vertices of the same label identified. The following
lemma relates the various definitions of progressing and $\lambda$-large
growth.

######  Lemma 4.3.

Suppose $\\{T_{H}\\}_{H\in\mathcal{H}\cup\\{\mathfrak{s}\\}}$ is a collection
of checkpoint trees with $\lambda$-large growth. Then the realized automaton
$\Sigma$ is progressing and has $\lambda$-large growth.

###### Proof.

The automaton $\Sigma$ is built from checkpoint trees $T_{\mathfrak{s}}$ and
$T_{H}$ for $H\in\mathcal{H}$. We let the checkpoint vertices $C$ of $\Sigma$
be the roots and leaves of the $T_{H}$, $H\in\mathcal{H}$. The labeling
$H:C\to\mathcal{H}$ comes from the labeling on the $T_{H}$.

Let $P\to\Sigma$ be a directed path with label $w^{\prime}$ and initial vertex
$\mathfrak{s}$, and suppose $P$ either does not meet $C$ or only meets $C$ at
its terminal vertex. Thus $P$ is contained in the tree $T_{\mathfrak{s}}$, so
there exists a progressing pair $(w,\mathfrak{s})$ where $w^{\prime}\subset w$
is a prefix. Because $(w,\mathfrak{s})$ is progressing,
$\hat{w}^{\prime\prime}x\neq x$ for each prefix $w^{\prime\prime}\subset
w^{\prime}$. If the terminal vertex of $P$ is some $c\in C$, then
$w^{\prime}=w$. In this case $\hat{w}H(c)$ separates $x$ and $\hat{w}x$ since
$H(c)$ witnesses the progression of $(w,\mathfrak{s})$.

Let $P\to\Sigma$ be a directed path with label $w^{\prime}$ such that $P$
meets $C$ only at its initial vertex or only at its initial and terminal
vertices. Thus $P$ is contained in a tree $T_{H}$ for some $H\in\mathcal{H}$,
and there exists a progressing pair $(w,H)$ such that $w^{\prime}\subset w$ is
a prefix. The initial vertex of $P$ is the root of $T_{H}$, which is also a
checkpoint vertex $c_{1}\in C$. We have $H(c_{1})=H$. Because $(w,H)$ is
progressing, $\hat{w}^{\prime\prime}x$ lies in the same halfspace of
$H(c_{1})$ as $x$ for each prefix $w^{\prime\prime}\subset w^{\prime}$. If the
terminal vertex of $P$ is $c_{2}\in C$, then $w^{\prime}=w$. In this case,
either $\hat{w}H(c_{2})=H(c_{1})$ or $\hat{w}H(c_{2})$ is parallel to
$H(c_{1})$ and separates $x$, $\hat{w}x$, since $H(c_{2})$ witnesses the
progression of $(w,H)$.

Any directed path $P\to\Sigma$ beginning at $\mathfrak{s}$ of length at least
$K=|T_{\mathfrak{s}}|$ terminates on some nonleaf vertex $v\in T_{H}$,
$H\in\mathcal{H}$. More precisely, $\Sigma$ is built by identifying roots and
leaves of $\\{T_{H}\\}_{H\in H\cup\\{\mathfrak{s}\\}}$, and there exists some
nonleaf vertex $v$ of some $T_{H}$, $H\in\mathcal{H}$ whose image is the
terminal vertex of $P$. $T_{H}$ has $\lambda$-large growth, so $v$ has at
least $\lambda|S^{\pm}|$ outgoing edges, hence so does the terminal vertex of
$P$. ∎

######  Definition 4.4.

Let $x\in X$ be a basepoint. The _fixing elements_
$\operatorname{Fix}(x)\subset S^{\pm}$ of some action of $F_{S}$ on $X$ are
those $s$ such that $sx=x$.

If for some basepoint $x\in X$ the set $\operatorname{Fix}(x)$ is sufficiently
large, then it is straightforward to construct an automaton whose accepted
language acts nontrivially on $x$. Note the automaton does not necessarily
have the structure of a progressing automaton. It is an ad hoc construction.

######  Lemma 4.5.

Fix an action of $F_{S}$ on a $\mathrm{CAT}(0)$ cube complex $X$ without a
global fixed-point, and let $x\in X$ be a $0$-cube such that
$|\operatorname{Fix}(x)|\geq\lambda|S^{\pm}|$. Then there exists an automaton
$\Sigma$ with $\lambda$-large growth such that $\hat{w}x\neq x$ for each
$w\in\mathcal{L}_{\Sigma}$.

###### Proof.

By assumption, there exists some $s\in S^{\pm}$ such that $sx\neq x$. Let
$\\{\mathfrak{s},v\\}$ be the vertex set of $\Sigma$. Add a directed edge
joining $\mathfrak{s}$ to $v$ with label $s$, and for each
$s^{\prime}\in\operatorname{Fix}(x)$ add a directed loop at $v$ labeled with
$s^{\prime}$. Any directed path $P\to\Sigma$ of length at least $1$ terminates
on $v$, which has $|\operatorname{Fix}(x)|\geq\lambda|S^{\pm}|$ outgoing
edges. Thus $\Sigma$ has $\lambda$-large growth. By construction, any word
$w\in\mathcal{L}_{\Sigma}$ is of the form $w=sw^{\prime}$, where $s$ is as
above and $w^{\prime}$ is a word over $\operatorname{Fix}(x)$. So we have
$\hat{w}x=\hat{s}\hat{w}^{\prime}x=\hat{s}x\neq x$. ∎

Moving forward, we concern ourselves with constructing a progressing automaton
using only elements of $S^{\pm}-\operatorname{Fix}(x)$. To this end, it will
simplify notation if we assume $\operatorname{Fix}(x)$ is empty. For the
remainder of this section until Section 5, we assume $\operatorname{Fix}(x)$
is empty.

######  Definition 4.6.

Let $H\in\mathcal{H}$, and let $w$ be a word over $S^{\pm}$ such that
$x,\hat{w}x\in N(H)$ lie in the same halfspace of $H$. We define a partition
of $S^{\pm}$ relative to $H$ and $w$ as follows:

  * •

The _forward_ elements $\mathcal{A}_{w}(H)$ are those $s\in S^{\pm}$ such that
$\hat{w}x$ and $\hat{w}\hat{s}x$ lie in the same halfspace of $H$ and
$\mathsf{d}(\hat{w}\hat{s}x,N(H))>0$.

  * •

The _backward_ elements $\mathcal{B}_{w}(H)$ are those $s\in S^{\pm}$ such
that $\hat{w}x$ and $\hat{w}\hat{s}x$ lie in different halfspaces of $H$.

  * •

The _parallel_ elements $\mathcal{P}_{w}(H)$ are those $s\in S^{\pm}$ such
that $\hat{w}x,\hat{w}\hat{s}x\in N(H)$ lie in the same halfspace of $H$.

The elements of $\mathcal{P}_{w}(H)$ further partitions into three sets:

  * •

The _visible parallel_ elements $\mathcal{P}^{|}_{w}(H)$ are those
$s\in\mathcal{P}_{w}(H)$ such that $(\hat{w}\hat{s})^{-1}H\in\mathcal{H}$.

  * •

The _crossing parallel_ elements $\mathcal{P}^{\pitchfork}_{w}(H)$ are the
nonvisible $s\in\mathcal{P}_{w}(H)$ such that $\hat{w}\hat{s}H\pitchfork H$.

  * •

The _disjoint parallel_ elements $\mathcal{P}^{\parallel}_{w}(H)$ are the
nonvisible $s\in\mathcal{P}_{w}(H)$ such that $\hat{w}\hat{s}H\parallel~{}H$.

When $w$ is the empty word, for simplicity we write $\mathcal{A}(H)$,
$\mathcal{B}(H)$, and $\mathcal{P}(H)$ instead of $\mathcal{A}_{w}(H)$,
$\mathcal{B}_{w}(H)$, and $\mathcal{P}_{w}(H)$. Similarly,
$\mathcal{P}^{|}_{w}(H)$, $\mathcal{P}^{\pitchfork}_{w}(H)$, and
$\mathcal{P}^{\parallel}_{w}(H)$ become $\mathcal{P}^{|}(H)$,
$\mathcal{P}^{\pitchfork}(H)$, and $\mathcal{P}^{\parallel}(H)$ when $w$
empty.

###  4.1. Easy progressions

######  Lemma 4.7.

Fix a visible hyperplane $H\in\mathcal{H}$ and a word $w$ such that
$x,\hat{w}\in N(H)$ lie in the same halfspace of $H$. The following hold:

  1. (1)

For each $s\in\mathcal{A}_{w}(H)$ the pair $(ws,H)$ is progressing. The
progression is witnessed by some $H^{\prime}\in\mathcal{H}_{s^{-1}}$.

  2. (2)

For each $s\in\mathcal{P}^{\parallel}_{w}(H)$ and $t\in\mathcal{B}(H)$, the
pair $(wst,H)$ is progressing. The progression is witnessed by some
$H^{\prime}\in\mathcal{H}_{t^{-1}}$.

  3. (3)

For $s\in\mathcal{P}^{|}(H)$, the pair $(ws,H)$ is progressing. The
progression is witnessed by $(ws)^{-1}H\in\mathcal{H}$.

###### Proof.

$(1)$ By definition of $\mathcal{A}_{w}(H)$,
$\mathsf{d}(\hat{w}\hat{s}x,N(H))>0$. By Lemma 2.2, the set of hyperplanes
separating $\hat{w}\hat{s}x$ and $H$ is nonempty. There exists a hyperplane
$H^{\prime\prime}$ in this set such that no hyperplane separates
$\hat{w}\hat{s}x$ and $H^{\prime\prime}$. The hyperplane
$H^{\prime}=(\hat{w}\hat{s})^{-1}H^{\prime\prime}$ separates $x$ and
$\hat{s}^{-1}x$ and no hyperplane separates $x$ and $H^{\prime}$. Thus
$H^{\prime}\in\mathcal{H}_{s^{-1}}$, and $H^{\prime}$ witnesses the
progression of $(ws,H)$.

$(2)$ Since $t\in\mathcal{B}(H)$, the hyperplane $H$ separates $x$ and
$\hat{t}x$. By definition of $\mathcal{P}^{\parallel}_{w}(H)$, $H$ does not
separate $\hat{w}\hat{s}x$ and $\hat{w}x$. Additionally,
$\hat{w}\hat{s}H\parallel H$, and $\hat{w}\hat{s}H$ lies on the same side of
$H$ as $\hat{w}x$ and $\hat{w}\hat{s}x$ because $\hat{w}x,\hat{w}\hat{s}x\in
N(H)\cap N(\hat{w}\hat{s}H)$. Since $H$ separates $x$ and $\hat{t}x$,
$\hat{w}\hat{s}H$ separates $\hat{w}\hat{s}x$ and $\hat{w}\hat{s}\hat{t}x$.
Let $H^{\prime\prime}$ be a hyperplane closest to $\hat{w}\hat{s}\hat{t}x$
parallel or equal to $\hat{w}\hat{s}H$. We have that $H^{\prime\prime}$
separates $\hat{w}\hat{s}\hat{t}x$ and $\hat{w}\hat{s}x$. Consequently,
$H^{\prime}=(\hat{w}\hat{s}\hat{t})^{-1}H^{\prime\prime}$ separates $x$ and
$\hat{t}^{-1}x$ and is not separated from $x$ by another hyperplane. Thus
$H^{\prime}\in\mathcal{H}_{t^{-1}}$, and $H^{\prime}$ is a witness to the
progression of $(wst,H)$.

$(3)$ By definition of $\mathcal{P}^{|}_{w}(H)$, $H$ does not separate
$\hat{w}x$ and $\hat{w}\hat{s}x$ and $(\hat{w}\hat{s})^{-1}H\in\mathcal{H}$.
Setting $H^{\prime}=(\hat{w}\hat{s})^{-1}H$, we have
$\hat{w}\hat{s}H^{\prime}=H$, so the pair $(s,H)$ is progressing. The
progression is witnessed by $H^{\prime}$. ∎

######  Corollary 4.8.

Let $T$ be a tree with a root labeled by $H\in\mathcal{H}$ and
$\lambda|S^{\pm}|$ children at each nonleaf vertex. If for each leaf $v\in T$
one of $|\mathcal{A}(H)_{\tilde{v}}|\geq\lambda|F|$,
$|\mathcal{P}^{|}(H)_{\tilde{v}}|\geq\lambda|F|$, or
$|\mathcal{P}^{\parallel}(H)_{\tilde{v}}|\geq\lambda|F|$ and
$|\mathcal{B}(H)_{\tilde{v}}|\geq\lambda|S^{\pm}|$ holds, then $T$ can be
extended to a checkpoint tree $T_{H}$ with $\lambda$-large growth by adding
children to its leaves.

The special case of the corollary for $T$ a trivial tree says if
$|\mathcal{A}(H)|\geq\lambda|S^{\pm}|$,
$|\mathcal{P}^{|}(H)|\geq\lambda|S^{\pm}|$, or
$|\mathcal{P}^{\parallel}(H)|\geq\lambda|S^{\pm}|$ and
$|\mathcal{B}(H)|\geq\lambda|S^{\pm}|$ for some $H\in\mathcal{H}$ holds, then
there exists a checkpoint tree at $H$ with $\lambda$-large growth.

###### Proof.

A tree $T_{H}$ is a checkpoint tree at $H$ if $(\tilde{v},H)$ is a progressing
pair for each leaf $v$ of $T_{H}$. By Lemma 4.7, each leaf of $T$ can be given
at least $\lambda|S^{\pm}|$ children so that this condition is satisfied on
the new leaves. The $\lambda$-large growth is automatically satisfied. ∎

###  4.2. Progressing with $\mathcal{P}$ and $\mathcal{B}$

The following property will aid in building checkpoint trees.

######  Definition 4.9.

Let $T$ be a labeled, rooted tree. We say that a rooted, directed path $P\to
T$ is a _rooted lift_ of a directed path $P^{\prime}\to T$ if $P$ and
$P^{\prime}$ have the same label $w$. We say $P\to T$ is a _rooted partial
lift_ if $P$ has label a prefix of $w$. $T$ has _property $(\star)$_ if every
rooted partial lift of a directed path extends to a rooted lift. In
particular, each directed path $P\to T$ has a rooted lift, since the trivial
path is a rooted partial lift.

######  Lemma 4.10.

Let $T$ be a labeled, rooted tree. Let $T_{0}\subset T$ be the subtree spanned
on all nonleaf vertices. Assume $T_{0}$ has property $(\star)$. Then $T$ has
property $(\star)$ if and only if for every leaf $v\in T_{0}$ we have
$\tilde{c}(v)\subset\bigcap_{\text{suffixes
}u\subset\tilde{v}}\tilde{c}(\tilde{u})$. Here we let $c(v)$ denote the set of
children of $v$ in $T$.

###### Proof.

Let $P^{\prime}\to T$ be a directed path, and let $P^{\prime}_{0}\to T_{0}$ be
the restriction of $P^{\prime}$ to $T_{0}$ terminating on a vertex $v$. Note
that $P^{\prime}_{0}$ is labeled by some suffix $u\subset\tilde{v}$. By
property $(\star)$ for $T_{0}$, every rooted partial lift of
$P^{\prime}_{0}\to T_{0}$ extends to a rooted lift $P_{0}\to T$. If
$P^{\prime\prime}=P^{\prime\prime}_{0}$, then $P_{0}\to T$ is a rooted lift of
$P^{\prime}$. Otherwise, $P^{\prime}_{0}=P^{\prime}-e$ where $e$ is an edge
joining $v$ to one of its children. Suppose $P_{0}$ terminates on a vertex
$v_{0}$, and $e$ has label $s$. Then $P_{0}\to T$ extends to a rooted lift
$P\to T$ of $P^{\prime}$ if and only if $s\in\tilde{c}(v_{0})$. Letting
$P^{\prime}$ range over all paths terminating in $c(v)$ and considering all
rooted partial lifts of $P^{\prime}_{0}$, we recover the inclusion
$\tilde{c}(v)\subset\bigcap_{\text{suffixes
}u\subset\tilde{v}}\tilde{c}(\tilde{u})$. ∎

######  Lemma 4.11.

Fix an action of $F_{S}$ on a $\mathrm{CAT}(0)$ cube complex $X$ with
$\operatorname{Fix}(x)$ empty, and fix a basepoint $x\in X$. There exists a
decreasing function $\epsilon(n)>0$ and a function
$\alpha(\epsilon_{0},\epsilon_{1},n)>0$ defined for
$0<\epsilon_{0}\leq\epsilon(n)\leq\epsilon_{1}<1$ such that the following
holds: If no more than $n$ hyperplanes in $\mathcal{H}$ pairwise intersect and
$\epsilon_{0}|S^{\pm}|\leq|\mathcal{B}(H)|\leq\epsilon_{1}|S^{\pm}|$ for some
$H\in\mathcal{H}$, then there exists a progressing checkpoint tree at $H$ with
$\alpha(\epsilon_{0},\epsilon_{1},n)$-large growth.

For $\epsilon_{0}>0$, define a diagonal array of real numbers $D_{i}(j)$,
$i\in\mathbf{N}$, $0\leq j<i$, by:

  * •

For $j<i-1$, $D_{i}(j)=(1-\epsilon_{0})D_{i-1}(j)-\sum_{0\leq
k<j}(1-D_{i}(k))$.

  * •

For $j=i-1$, $D_{i}(j)=1-3\epsilon_{0}-\sum_{0\leq k<j}(1-D_{i}(k))$.

Note that each $D_{i}(j)$ is defined only in terms of those
$D_{i^{\prime}}(j^{\prime})$ with $i^{\prime}+j^{\prime}<i+j$. Also note for
$i^{\prime}+j^{\prime}<i+j$ that $D_{i}(j)\leq D_{i^{\prime}}(j^{\prime})$.

######  Lemma 4.12.

For any $i\in\mathbf{N}$ and $0\leq j\leq i$, we have $D_{i}(j)\to 1$ as
$\epsilon_{0}\to 0$.

###### Proof.

$D_{1}(0)=1-3\epsilon_{0}$ by the second equation, so $D_{1}(0)\to 1$ as
$\epsilon_{0}\to 0$. If the lemma holds for all $D_{i^{\prime}}(j^{\prime})$
with $i^{\prime}+j^{\prime}<i+j$, then the lemma holds for $D_{i}(j)$ by
definition of $D_{i}(j)$, so the lemma follows from induction. ∎

###### Proof of Lemma 4.11.

Since we only consider the partition of $\mathcal{H}$ defined relative to $H$,
we use $\mathcal{A}_{w}$, $\mathcal{B}_{w}$, and $\mathcal{P}_{w}$ in place of
$\mathcal{A}_{w}(H)$, $\mathcal{B}_{w}(H)$, and $\mathcal{P}_{w}(H)$ for the
duration of this proof.

Let $F=S^{\pm}-\mathcal{B}$, and note $|F|\geq(1-\epsilon_{1})|S^{\pm}|$ since
$|\mathcal{B}|\leq\epsilon_{1}|S^{\pm}|$. If
$|\mathcal{A}|\geq\epsilon_{0}|F|$, $|\mathcal{P}^{|}|\geq\epsilon_{0}|F|$, or
$|\mathcal{P}^{\parallel}|\geq\epsilon_{0}|F|$, then by Corollary 4.8 there is
a progressing tree at $H$ with $\epsilon_{0}(1-\epsilon_{1})$-large growth.
Otherwise, we have $|\mathcal{P}^{\pitchfork}|\geq(1-3\epsilon_{0})|F|$, since
$\mathcal{P}^{\pitchfork}\subset F$ and $F$ is partitioned between
$\mathcal{A}$, $\mathcal{P}^{|}$, $\mathcal{P}^{\parallel}$, and
$\mathcal{P}^{\pitchfork}$. Supposing
$|\mathcal{P}^{\pitchfork}|\geq(1-3\epsilon_{0})|F|$, we will construct a
progressing checkpoint tree $T$ with
$\epsilon_{0}(1-\epsilon_{1})D_{n}(n-1)$-large growth.

We construct $T$ as the limit of a finite sequence of deterministically
labeled trees $T_{1},T_{2},\ldots,T_{m}=T$. For $i<m$, every leaf of $T_{i}$
has depth $i$, and $T_{i+1}$ is constructed by first deleting edges from
$T_{i}$ and then adding children to the leaves. For $i<m$, each $T_{i}$ will
satisfy the following:

  1. (1)

$T_{i}$ has property $(\star)$.

  2. (2)

For any vertex $v\in T_{i}$,
$\tilde{c}(v)\subset\mathcal{P}^{\pitchfork}_{\tilde{v}}\cap F$.

  3. (3)

A vertex of depth $j<i$ in $T_{i}$ has at least $D_{i}(j)|F|$ children.

Let $T_{1}$ be the rooted, depth-one tree with an edge for each element of
$\mathcal{P}^{\pitchfork}$, and label each edge by its corresponding element
in $\mathcal{P}^{\pitchfork}$. $T_{1}$ satisfies conditions (1) and (2)
trivially. Condition (3) holds by the assumption that
$|\mathcal{P}^{\pitchfork}|\geq(1-3\epsilon_{0})|F|$.

We now describe how to construct $T_{i+1}$ from $T_{i}$. Let $v$ be a leaf of
$T_{i}$. Applying condition (2) to the ancestor of $v$, it follows that
$\mathcal{B}_{\tilde{v}}$ is empty. Thus the set $F$ is partitioned between
$\mathcal{A}_{\tilde{v}}$, $\mathcal{P}^{|}_{\tilde{v}}$,
$\mathcal{P}^{\pitchfork}_{\tilde{v}}$, and
$\mathcal{P}^{\parallel}_{\tilde{v}}$. One of the following must hold: either
(i) at least one of $|\mathcal{A}_{\tilde{v}}|>\epsilon_{0}|F|$,
$|\mathcal{P}^{|}_{\tilde{v}}|>\epsilon_{0}|F|$, or
$|\mathcal{P}^{\parallel}_{\tilde{v}}|>\epsilon_{0}|F|$ holds; or (ii)
$|\mathcal{P}^{\pitchfork}_{\tilde{v}}\cap F|\geq(1-3\epsilon_{0})|F|$. We
define a partition of the vertices of $T_{i}$ into sets $\mathcal{C}$ and
$\mathcal{D}$. The partition is defined inductively from larger depth vertices
to lower depth vertices, beginning with the leaves of $T_{i}$.

  * •

If $v$ is a leaf of $T_{i}$ such that (i) holds, then $v\in\mathcal{C}$.
Otherwise (ii) holds and $v\in\mathcal{D}$.

  * •

Let $u$ be a vertex whose children $c(u)$ have been partitioned between
$\mathcal{C}$ and $\mathcal{D}$. If
$|c(u)\cap\mathcal{C}|\geq\epsilon_{0}|c(u)|$, then $u\in\mathcal{C}$.
Otherwise $|c(u)\cap\mathcal{D}|>(1-\epsilon_{0})|c(u)|$ and
$u\in\mathcal{D}$.

Our construction now splits into two cases, depending on whether the root of
$T_{i}$ is in $\mathcal{C}$ or $\mathcal{D}$. If the root is in $\mathcal{C}$,
then $T_{i+1}$ will be the final tree in the sequence, i.e., $m=i+1$.
Supposing the root is in $\mathcal{C}$, begin by deleting all vertices in
$\mathcal{D}$ from $T_{i}$. Note that $T_{i}-\mathcal{D}$ may be disconnected.
Let $T^{\prime}_{i}$ be the connected component of $T_{i}-\mathcal{D}$
containing the root. By condition (3) and construction of $T^{\prime}_{i}$, a
depth $j<i$ vertex of $T^{\prime}_{i}$ has at least $\epsilon_{0}D_{i}(j)|F|$
children, and
$\epsilon_{0}D_{i}(j)|F|\geq\epsilon_{0}(1-\epsilon_{1})D_{n}(n-1)|S^{\pm}|$.
Thus depth $j<i$ vertices of $T^{\prime}_{i}$ have
$\epsilon_{0}(1-\epsilon_{1})D_{n}(n-1)$-growth. For each leaf $v\in
T^{\prime}_{i}$, one of $|\mathcal{A}_{\tilde{v}}|>\epsilon_{0}|F|$,
$|\mathcal{P}^{|}_{\tilde{v}}|>\epsilon_{0}|F|$, or
$|\mathcal{P}^{\parallel}_{\tilde{v}}|>\epsilon_{0}|F|$ holds. Since
$\epsilon_{0}|F|\geq\epsilon_{0}(1-\epsilon_{1})D_{n}(n-1)|S^{\pm}|$,
Corollary 4.8 implies the leaves of $T^{\prime}_{i}$ can be given children so
that the resulting tree $T_{i+1}$ is progressing and has
$\epsilon_{0}(1-\epsilon_{1})D_{n}(n-1)|S^{\pm}|$-large growth.

Suppose now that the root of $T_{i}$ is in $\mathcal{D}$. Let $T^{\prime}_{i}$
be the connected component of $T_{i}-\mathcal{C}$ containing the root, and let
$\mathcal{T}$ be the maximal subtree of $T^{\prime}_{i}$ satisfying property
$(\star)$. There is a filtration
$\mathcal{T}_{1}\subset\cdots\subset\mathcal{T}_{i}=\mathcal{T}$ where
$\mathcal{T}_{j}$ is the maximal rooted subtree of $T^{\prime}_{i}$ of depth
$j$ satisyfing property $(\star)$. Note that unions of rooted subtrees of
$T^{\prime}_{i}$ satisfying $(\star)$ also satisfy $(\star)$, so the
$\mathcal{T}_{j}$ are well-defined. Additionally, for each $j$, the subtree
spanned on the depth at most $j-1$ vertices in $\mathcal{T}_{j}$ is exactly
$\mathcal{T}_{j-1}$.

We now focus our attention on the tree $T^{\prime}_{i}$, so that the functions
$\tilde{\cdot}$ and $c(\cdot)$ are defined relative to $T^{\prime}_{i}$. Let
$v$ be a depth $j<i$ vertex in $\mathcal{T}_{j}\subset T^{\prime}_{i}$. By
Lemma 4.10, $\mathcal{T}_{j+1}$ contains the outgoing edges at $v\in
T^{\prime}_{i}$ with labels in $\tilde{c}(v)\bigcap_{\text{suffixes
}u\subset\tilde{v}}(\tilde{c}(\tilde{u})\cap\mathcal{T}_{j})$. We will
inductively show that a depth $j$ vertex $v\in\mathcal{T}_{j+1}$ has
$D_{i+1}(j)|F|$ children. Since the trees are deterministically labeled, this
is equivalent to showing $|\tilde{c}(v)\cap\mathcal{T}_{j+1}|\geq
D_{i+1}(j)|F|$. We have the following bound:

$\displaystyle\bigg{|}\tilde{c}(v)\bigcap_{u\subset\tilde{v}\text{ a proper
suffix}}(\tilde{c}(\tilde{u})\cap\mathcal{T}_{j})\bigg{|}$
$\displaystyle\geq|\tilde{c}(v)|-\sum_{u\subset\tilde{v}\text{ a proper
suffix}}|F-(\tilde{c}(\tilde{u})\cap\mathcal{T}_{j})|$
$\displaystyle=(1-\epsilon_{0})D_{i}(j)|F|-\sum_{0\leq k<j}(1-D_{i+1}(k))|F|$
$\displaystyle=D_{i+1}(j)|F|.$

For each $j$, $\mathcal{T}_{j+1}$ is formed by adding children to the leaves
of $\mathcal{T}_{j}$ for each, so we have succeeded in showing that a depth
$j<i$ vertex of $\mathcal{T}_{i}=\mathcal{T}$ has $D_{i+1}(j)|F|$ children.

We now examine the tree $\mathcal{T}$, so that the functions $\tilde{\cdot}$
and $c(\cdot)$ are defined relative to $\mathcal{T}$. To finish the
construction of $T_{i+1}$, we add children to the leaves of $\mathcal{T}$. Let
$v\in\mathcal{T}$ be a leaf (recall the leaves are exactly the depth $i$
vertices). By definition of $\mathcal{D}$,
$|\mathcal{P}^{\pitchfork}_{\tilde{v}}\cap F|\geq(1-3\epsilon_{0})|F|$, so we
have the following bound:

$\displaystyle\bigg{|}\mathcal{P}^{\pitchfork}_{\tilde{v}}\cap
F\cap\big{(}\bigcap_{u\subset\tilde{v}\text{ a proper
suffix}}\tilde{c}(\tilde{u})\big{)}\bigg{|}$
$\displaystyle\geq|\mathcal{P}^{\pitchfork}_{\tilde{v}}\cap
F|-\sum_{u\subset\tilde{v}\text{ a proper suffix}}|F-\tilde{c}(\tilde{u})|$
$\displaystyle=(1-3\epsilon_{0})|F|-\sum_{0\leq k<i}(1-D_{i+1}(k))|F|$
$\displaystyle=D_{i+1}(i)|F|$

For each element of $s\in\mathcal{P}^{\pitchfork}_{\tilde{v}}\cap
F\cap\big{(}\bigcap_{u\subset\tilde{v}\text{ a proper
suffix}}\tilde{c}(\tilde{u}))$, we add an edge incident to $v$ with label $s$.
Thus $v$ has at least $D_{i+1}(i)|F|$ children. The tree $T_{i+1}$ is formed
by adding children to each leaf $v\in\mathcal{T}$ as above. By construction,
$T_{i+1}$ has property $(\star)$, and thus satisfies condition (1). All new
edges have labels from the relevant $\mathcal{P}^{\pitchfork}_{\tilde{v}}\cap
F$ sets, so $T_{i+1}$ also satisfies condition (2). Finally, the inequalities
above show that $T_{i+1}$ satisfies condition (3).

Conditions (1) and (2) have the following consequence: For any vertex $v\in
T_{i}$, the set of hyperplanes $\\{\hat{u}H:u\subset\tilde{v}\text{ a
prefix}\\}$ pairwise cross. We first show that
$\hat{\tilde{v}}H\pitchfork\hat{u}H$ for each prefix $u\subset\tilde{v}$.
Fixing a prefix $u\subset\tilde{v}$, we can write $\tilde{v}$ in the form
$\tilde{v}=uws$, where $s$ is the final letter of $u$. The subword $w$ may be
empty. By conditions (1) and (2), $s\in\mathcal{P}^{\pitchfork}_{w}$. By
definition of $\mathcal{P}^{\pitchfork}_{w}$, we have
$\hat{w}\hat{s}H\pitchfork H$. Multiplying by $\hat{u}$ and using
$\hat{u}\hat{w}\hat{s}=\hat{\tilde{v}}$, we get
$\hat{\tilde{v}}H\pitchfork\hat{u}H$ as desired. For any prefix
$u\subset\tilde{v}$ repeating the above argument with $\tilde{u}$ in the place
of $v$, we get that $\hat{u}H\pitchfork\hat{w}H$ for any prefix $w\subset u$.
This suffices to show the collection $\\{\hat{u}H:u\subset\tilde{v}\text{ a
prefix}\\}$ is pairwise crossing.

The above analysis allows us to bound the number of trees in our sequence. By
assumption, no more than $n$ hyperplanes in $\mathcal{H}$ can pairwise
intersect. The argument above shows that a depth $k$ vertex $v\in T_{i}$
yields a set of $k+1$ pairwise crossing hyperplanes. Thus the $T_{i}$ can have
depth at most $n-1$, and our sequence must terminate in at most $n-1$ steps,
i.e., $m\leq n-1$.

Since the sequence $T_{1},\ldots,T_{m}=T$ terminates in at most $n-1$ steps,
$T$ has at least $\epsilon_{0}(1-\epsilon_{1})D_{n}(n-1)$-growth. The value of
$\epsilon_{0}(1-\epsilon_{1})D_{n}(n-1)$ is positive for $\epsilon_{0}>0$
sufficiently small. Let $\epsilon(n)>0$ be a constant such that
$\alpha(\epsilon_{0},\epsilon_{1},n)\vcentcolon=\epsilon_{0}(1-\epsilon_{1})D_{n}(n-1)$
is positive for all $\epsilon_{0}\leq\epsilon(n)$, and choose $\epsilon(n)$ be
be decreasing in $n$. ∎

###  4.3. Inductive progression

######  Definition 4.13.

A group $G$ acts on a $\mathrm{CAT}(0)$ cube complex _without hyperplane
inversions_ if there do not exist $g\in G$ and a hyperplane $H\subset X$ such
that $gH=H$ and $g$ interchanges the halfspaces of $H$.

Group actions can always be arranged to be without hyperplane inversions by
passing to the first cubical subdivision. That is, for any action of $G$ on a
$\mathrm{CAT}(0)$ cube complex $X$, there is an induced action of $G$ on the
first cubical subdivision of $X$, and this latter action is always without
hyperplane inversions. Note the induced action has bounded orbits if and only
if the original action did too. Thus when studying the existence of global
fixed-points, there is no cost to assuming an action is without hyperplane
inversions.

######  Lemma 4.14.

Fix an action of $F_{S}$ on a $\mathrm{CAT}(0)$ cube complex $X$ without
hyperplane inversions. Fix a basepoint $0$-cube $x\in X$ which minimizes
$\sum_{s\in S^{\pm}}\mathsf{d}(x,sx)$. Then
$\mathcal{B}(H)\leq\frac{1}{2}|S^{\pm}|$ for any $H\in\mathcal{H}$.

###### Proof.

Suppose $\mathcal{B}_{H}>\frac{1}{2}|S^{\pm}|$ for some $H\in\mathcal{H}$. Let
$y$ be the $0$-cube opposite $x$ in $N(H)$. We will show $\sum_{s\in
S^{\pm}}\mathsf{d}(y,sy)<\sum_{s\in S^{\pm}}\mathsf{d}(x,sx)$, contradicting
our choice of $x$. For each $s$ and its inverse $s^{-1}$, we have the
following three possibilities.

  1. (1)

Both $s,s^{-1}\in\mathcal{B}(H)$. We show that $d(y,sy)=d(x,sx)-2$. Let
$x_{0},\ldots,x_{n}$ be the 0-cells of a geodesic $P\to X$ joining
$s^{-1}x=x_{0}$ to $x=x_{n}$. If $s^{-1}H=H$, then $s$ stabilizes $H$ and
interchanges its halfspaces, contradicting that there are no hyperplane
inversions. Thus $s^{-1}H\neq H$. Note that $s^{-1}H$ is a closest hyperplane
to $x_{0}$ separating $x_{0}$, $x_{n}$, and $H$ is a closest hyperplane to
$x_{n}$ separating $x_{0}$, $x_{n}$. Thus we can choose $P\to X$ so that it
crosses the hyperplane $s^{-1}H$ first and crosses $H$ last. Since $H$ is the
last hyperplane crossed, we have $x_{n-1}=y$. And since $s$ takes $s^{-1}H$ to
$H$, we get that $sx_{1}=x_{n-1}$, i.e., $x_{1}=s^{-1}y$. Hence
$d(y,sy)=d(s^{-1}y,y)=d(x_{1},x_{n-1})=d(x_{0},x_{n})-2=d(s^{-1}x,x)-2=d(x,sx)-2$.

  2. (2)

Exactly one of $s\in\mathcal{B}(H)$ or $s^{-1}\in\mathcal{B}(H)$. We show that
$\mathsf{d}(y,sy)=\mathsf{d}(x,sx)$. Suppose $s\in\mathcal{B}(H)$. Consider
the 0-cells $x_{0},\ldots,x_{n}$ of a geodesic $P$ joining $x=x_{0}$ to
$sx=x_{n}$ with $x_{1}=y$. Then $s^{-1}P$ is a geodesic joining $s^{-1}x$ to
$x$. The hyperplane $H$ does not intersect $s^{-1}P$, otherwise $H$ would
separate $s^{-1}x$ and $x$. Thus, the edge $yx$ followed by the subpath
$P^{\prime}\subset s^{-1}P$ of length $|P|-1$ is a geodesic of length $|P|$
joining $y$ to $s^{-1}y$.

  3. (3)

Both $s,s^{-1}\not\in\mathcal{B}(H)$. We have
$\mathsf{d}(y,sy)\leq\mathsf{d}(x,sx)+2$, since $\mathsf{d}(x,y)=1$.

Let the partition $S^{\pm}=D_{1}\sqcup D_{2}\sqcup D_{3}$ correspond to the
three cases above. Since $|\mathcal{B}(H)|>\frac{1}{2}|S^{\pm}|$, we have
$|D_{1}|>|D_{3}|$. This yields

$\sum_{s\in S^{\pm}}\mathsf{d}(x,sx)\geq\sum_{s\in
D_{1}}\big{(}\mathsf{d}(y,sy)+2\big{)}+\sum_{s\in
D_{2}}\mathsf{d}(y,sy)+\sum_{s\in
D_{3}}\big{(}\mathsf{d}(y,sy)-2\big{)}>\sum_{s\in S^{\pm}}\mathsf{d}(y,sy).$

∎

Some new notation is necessary to state the next result. Let
$\mathsf{P}\subset S^{\pm}$. Then $\mathcal{H}_{\mathsf{P}}\subset\mathcal{H}$
are those hyperplanes which separate $x$ and $sx$ for some $s\in\mathsf{P}$.
Equivalently,
$\mathcal{H}_{\mathsf{P}}\vcentcolon=\bigcup_{s\in\mathsf{P}}\mathcal{H}_{s}$.

######  Lemma 4.15.

Fix an action of $F_{S}$ on a $\mathrm{CAT}(0)$ cube complex. Suppose that no
more than $n$ hyperplanes in $\mathcal{H}$ pairwise intersect. If
$\mathcal{P}(H)\geq\lambda|S^{\pm}|$ for some $H\in\mathcal{H}$, then there
exists a symmetric $\mathsf{S}^{\pm}\subseteq S^{\pm}$ such that
$|\mathsf{S}^{\pm}|\geq(2\lambda-1)|S^{\pm}|$ and no more than $n-1$
hyperplanes of $\mathcal{H}_{\mathsf{S}^{\pm}}$ pairwise cross.

###### Proof.

Suppose $H\in\mathcal{H}$ is such that $\mathcal{P}(H)\geq\lambda|S^{\pm}|$.
Each hyperplane in $\mathcal{H}_{\mathcal{P}(H)}$ intersects $H$, so at most
$n-1$ hyperplanes in $\mathcal{H}_{\mathcal{P}(H)}$ pairwise intersect. The
intersection $\mathcal{P}(H)\cap\mathcal{P}(H)^{-1}$ is clearly symmetric, and
thus can be written as $\mathsf{S}^{\pm}=\mathsf{S}\cup\mathsf{S}^{-1}$. It is
also immediate that $|\mathsf{S}^{\pm}|\geq(2\lambda-1)|S^{\pm}|$, and no more
than $n-1$ hyperplanes in $\mathcal{H}_{\mathsf{S}^{\pm}}$ pairwise intersect,
since $\mathcal{H}_{\mathsf{S}^{\pm}}\subset\mathcal{H}_{\mathcal{P}(H)}$. ∎

The above lemma will allow us to induct on the number of pairwise intersecting
hyperplanes in $\mathcal{H}$. To do this, we need the following bound.

######  Lemma 4.16.

Let $S$ and $\mathsf{S}$ be as in Lemma 4.15. If
$\mathcal{B}(H)\leq\beta|S^{\pm}|$ for each $H\in\mathcal{H}$, then
$\mathcal{B}(\mathsf{H})\leq\frac{\beta}{2\lambda-1}|\mathsf{S}^{\pm}|$ for
each $\mathsf{H}\in\mathcal{H}_{\mathsf{S}^{\pm}}$.

###### Proof.

Use $|\mathsf{S}^{\pm}|/(2\lambda-1)\geq|S^{\pm}|$ from Lemma 4.15 to
substitute $|S^{\pm}|$ in $\mathcal{B}(H)\leq\beta|S^{\pm}|$. ∎

######  Theorem 4.17.

Fix an action of $F_{S}$ on an $n$-dimensional $\mathrm{CAT}(0)$ cube complex
$X$. Let $x\in X$ be a $0$-cube such that $\operatorname{Fix}(x)$ is trivial
and $|\mathcal{B}(H)|\leq\epsilon_{1}<1$. Then there exists a progressing
automaton with at most $(|S^{\pm}|n+1)^{n}$ vertices and
$\theta(n,\epsilon_{1})$-large growth, where $\theta(n,\epsilon_{1})>0$
depends only on $n$ and $\epsilon_{1}$.

###### Proof.

Let $\epsilon$ be the function from Lemma 4.11, and take
$\epsilon_{0}=\epsilon(n)$. Let $\lambda=1-2\epsilon_{0}$.

Define a positive, decreasing sequence $\\{\gamma(i)\\}_{1\leq i\leq n}$ as
follows:

  * •

Let $\gamma(1)=1-\frac{\epsilon_{1}}{(2\lambda-1)^{n-1}}$.

  * •

For $1<i\leq n$, let
$\gamma(i)=\min\\{\epsilon_{0},\alpha(\epsilon(n),\frac{\epsilon_{1}}{(2\lambda-1)^{n-i}},i),(2\lambda-1)\gamma(i-1)\\}$.

We will prove the following claim by induction on $i$ for $1\leq i\leq n$.

Claim. Suppose that no more than $i$ hyperplanes of $\mathcal{H}$ pairwise
cross and
$|\mathcal{B}(H)|\leq\frac{\epsilon_{1}}{(2\lambda-1)^{n-i}}|S^{\pm}|$ for
each $H\in\mathcal{H}$. Then there exists a progressing automaton with
$\gamma(i)$-large growth.

The theorem follows by taking $\theta(n)=\gamma(n)$ and applying the claim for
the case $i=n$.

Proof of Claim. If no two hyperplanes in $\mathcal{H}$ cross, i.e., $i=1$,
then $\mathcal{P}(H)$ is empty for all $H\in\mathcal{H}$. Since
$\mathcal{B}(H)\leq\frac{\epsilon_{1}}{(2\lambda-1)^{n-1}}|S^{\pm}|$, we have
$\mathcal{A}(H)\geq(1-\frac{\epsilon_{1}}{(2\lambda-1)^{n-1}})|S^{\pm}|$ for
each $H\in\mathcal{H}$. By Lemma 4.7.(1), we can build a progressing
checkpoint tree with $(1-\frac{\epsilon_{1}}{(2\lambda-1)^{n-1}})$-large
growth, i.e., $\gamma(1)$-large growth. By Lemma 4.3, we can construct a
progressing automaton with the same growth. We now suppose the claim holds for
$i-1$ and try to prove it for $i$.

By Lemma 4.7.(1) and Lemma 4.11, if
$|\mathcal{A}(H)|\geq\epsilon_{0}|S^{\pm}|$ or
$|\mathcal{B}(H)|\geq\epsilon_{0}|S^{\pm}|$, then there exists a progressing
checkpoint tree at $H$ with $\epsilon_{0}$-large growth or
$\alpha(\epsilon_{0},\frac{\epsilon_{1}}{(2\lambda-1)^{n-i}},i)$-large growth,
respectively. Thus, by Lemma 4.3, if
$|\mathcal{A}(H)|\geq\epsilon_{0}|S^{\pm}|$ or
$|\mathcal{B}(H)|\geq\epsilon_{0}|S^{\pm}|$ for every $H\in\mathcal{H}$, then
there exists a progressing automaton with
$\min\\{\epsilon_{0},\alpha(\epsilon(n),\\\
\frac{\epsilon_{1}}{(2\lambda-1)^{n-i}},i)\\}$-large growth, hence
$\gamma(i)$-large growth.

Suppose then that $|\mathcal{A}(H)|<\epsilon_{0}|S^{\pm}|$ and
$|\mathcal{B}(H)|<\epsilon_{0}|S^{\pm}|$ for some $H\in\mathcal{H}$. Then
$|\mathcal{P}(H)|\geq(1-2\epsilon_{0})|S^{\pm}|=\lambda|S^{\pm}|$. By Lemma
4.15, there exists $\mathsf{S}\subset S$ with
$|\mathsf{S}^{\pm}|\geq(2\lambda-1)|S^{\pm}|$ so that no more than $i-1$
hyperplanes of $\mathcal{H}_{\mathsf{S}^{\pm}}$ pairwise cross. By Lemma 4.16,
$|\mathcal{B}(\mathsf{H})|\leq\frac{\epsilon_{1}}{(2\lambda-1)^{n-(i-1)}}|\mathsf{S}^{\pm}|$
for each $\mathsf{H}\in\mathcal{H}_{\mathsf{S}^{\pm}}$. Restricting our action
to the subgroup $F_{\mathsf{S}}\subset F_{S}$, we may apply the $i-1$ version
of the claim to obtain an progressing automaton over $\mathsf{S}$ with
$\gamma(i-1)$-large growth. This automaton can be considered as an automaton
over $S$ with $(2\lambda-1)\gamma(i-1)$-large growth, hence $\gamma(i)$-large
growth. ∎

Lemma 4.14 and Lemma 4.17 have the following corollary, which may be of
independent interest for constructing groups with $F\mathcal{C}_{n}$.

######  Corollary 4.18.

For any $k,n>0$, there exist regular languages
$\mathcal{L}_{1},\ldots,\mathcal{L}_{i(n,k)}$ so that the following holds: If
a group $G$ has presentation $\langle S\mid R\rangle$ with $|S|\leq k$, and
$R$ contains at least one word from each $\mathcal{L}_{j}$, $1\leq j\leq
i(n,k)$, then $G$ has $F\mathcal{C}_{n}$. Moreover, there is some $c>0$,
independent of $k$, so that for each $1\leq j\leq i(n,k)$, $\mathcal{L}_{j}$
contains $\epsilon(c|S|)^{L}$ words of length $L$ for some $\epsilon>0$. Thus,
if $|S|$ is sufficiently large, then one can choose words
$w_{j}\in\mathcal{L}_{j}$ so that the chosen words $\\{w_{j}\\}$ satisfy the
$C^{\prime}(\lambda)$ condition for any $\lambda>0$.

###### Proof.

Let $c=\frac{1}{2}\min\\{\theta(m,\frac{1}{2})\\}_{m\leq n}$. Let
$\mathcal{L}_{1},\ldots,\mathcal{L}_{i(n,k)}$ be the set of accepted languages
for all automata with at most $(kn+1)^{n}$ vertices and $c$-large growth.

Let $G$ be a group with a presentation $\langle S\mid R\rangle$ satisfying the
hypotheses in the theorem. Suppose for sake of contradiction that $G$ acts on
an $n$-dimensional $\mathrm{CAT}(0)$ cube complex $X$ without global fixed
point. The action of $G$ on $X$ lifts to an action of $F_{S}$ on $X$. By Lemma
4.14, there exists a $0$-cube $x\in X$ ∎

##  5\. Random Groups and Cubical fixed-points

###  5.1. Random group preliminaries

######  Definition 5.1.

If $S=\\{s_{1},\ldots,s_{k}\\}$ and
$S^{-1}=\\{s_{1}^{-1},\ldots,s_{k}^{-1}\\}$ are a set of formal letters and
their formal inverses, then the set $\mathcal{R}$ of length $L$ words over
$S^{\pm}$ has cardinality $(2k)^{L}$. A _random set of relators
$\mathcal{R}_{d,L}$ at density $d\in(0,1)$ and length $L$_ is formed by taking
$(2k)^{dL}$ uniformly random samples from $\mathcal{R}_{L}$. A _random group
at density $d\in(0,1)$, length $L$, and generators $S$_ is given by a
presentation $G_{S,d,L}=\langle S\mid R_{d,L}\rangle$. A random group at
density $d$ has a property $Q$ _with overwhelming probability (w.o.p.)_ if
$\mathbf{P}\\{G_{S,d,L}\text{ has }Q\\}\to 1$ as $L\to\infty$.

######  Definition 5.2.

Let $A\subset\mathbf{N}$ be infinite. A set of words $\mathcal{L}$ over
$S^{\pm}$ has $A$-_density $d\in(0,1)$_ if for some constant $c>0$, the set
$\mathcal{L}$ contains at least $c|S^{\pm}|^{dL}$ words of length $L$ for each
$L\in A$. If an automaton $\Sigma$ has $\lambda$-large growth for
$\lambda\geq|S^{\pm}|^{d-1}$, then its accepted language
$\mathcal{L}_{\Sigma}$ has $A$-density $d$ for every $A\subset\mathbf{N}$.
Note for a fixed $\lambda>0$, the inequality $\lambda\geq|S^{\pm}|^{d-1}$ is
satisfied for all $|S^{\pm}|$ sufficiently large.

The following lemma follows from an application of Chebyshev’s theorem. For
more details see [Gro91, Orl17].

######  Lemma 5.3.

Fix densities $d,d^{\prime}\in(0,1)$ so that $d+d^{\prime}>1$. If
$\mathcal{L}$ is a set of words with $A$-density $d^{\prime}$, then for $L\in
A$, $\mathbf{P}\\{R_{d,L}\cap\mathcal{L}\neq\emptyset\\}\to 1$ as
$L\to\infty$. Consequently, if $\Sigma$ is an automaton with $\lambda$-large
growth where $|S^{\pm}|^{d-1}$, then
$\mathbf{P}\\{R_{d,L}\cap\mathcal{L}_{\Sigma}\neq\emptyset\\}\to 1$ as
$L\to\infty$.

######  Definition 5.4.

The subgroup $H_{m}<G_{S,d,L}$ is the subgroup generated by length $m$ words
over $S^{\pm}$. It is clear that $H_{m}$ has finite-index in $G_{S,d,L}$.
Inversion induces a fixed-point free involution on the set of length $m$
words, so this set can naturally be partitioned into
$\widehat{S}\cup\widehat{S}^{-1}$ for some $\widehat{S}$. We have
$|\widehat{S}^{\pm}|=|S^{\pm}|^{m}$.

A benefit of the plain words model is that the subgroups $H_{m}$ are quotients
of random groups in the same model. Importantly, these quotients also have the
same density of relators.

######  Definition 5.5.

Fix $m>0$, and consider a random group $G_{S,d,L}$. There exists a unique
$0\leq r<m$ such that $L=\widehat{L}m+r$. For each $0\leq r<m$, we let
$A_{r}\subset\mathbf{N}$ denote the set of $L$ such that $L=\widehat{L}m+r$.
If two relators of $G_{S,d,L}$ have the form $R_{1}w^{-1}$ and $wR_{2}$ for a
word $w$ of length $r$, then $R_{1}R_{2}$ can be viewed as a word of length
$2\widehat{L}$ over $\widehat{S}^{\pm}$. Let $\widehat{R}$ be the set of all
$R_{1}R_{2}$ for relators $R_{1}w^{-1}$ and $wR_{2}$ of $G_{S,d,L}$ as above
(for all possible $w$ as well). The group
$\widehat{G}_{m}=\langle\widehat{S}\mid\widehat{R}\rangle$ is the _$m$
-associated group_ of $G_{S,d,L}$. Interpreting elements of $\widehat{S}$ as
length $m$ words over $S^{\pm}$ defines a natural quotient map
$\widehat{G}_{m}\twoheadrightarrow H_{m}$.

###  5.2. Cubical fixed-points

######  Lemma 5.6.

Let $H<G$ be a finite-index subgroup. If $H$ has property $F\mathcal{C}_{n}$,
then $G$ has property $F\mathcal{C}_{n}$.

###### Proof.

Fix an action of $G$ on an $n$-dimensional $\mathrm{CAT}(0)$ cube complex $X$,
and consider a global fixed-point of $H$, i.e., a point $x\in X$ such that
$Hx=x$. The orbit $Gx$ is finite, since $H$ is finite-index. By [BH99,
Corollary 2.8], the fixed-point set of $G$ is nonempty. ∎

The converse of the above lemma does not hold in general. For example, the
333-triangle group has $F\mathcal{C}_{1}$ but is virtually $\mathbf{Z}^{2}$.

######  Lemma 5.7.

If $G$ has property $F\mathcal{C}_{n}$, then any quotient of $G$ has property
$F\mathcal{C}_{n}$.

###### Proof.

Let $G\twoheadrightarrow H$ be a group epimorphism. Any action
$H\to\operatorname{Isom}(X)$ of $H$ on a $\mathrm{CAT}(0)$ cube complex $X$
can be turned into an action $G\twoheadrightarrow H\to\operatorname{Isom}(X)$
of $G$ on $X$. A global fixed-point of $G\to\operatorname{Isom}(X)$ is also a
global fixed-point of $H\to\operatorname{Isom}(X)$. ∎

###### Proof of Lemma 1.7.

Let $X$ be a $\mathrm{CAT}(0)$ cube complex. For $0$-cubes $x$, $y$, and $z$,
the _median_ $\mu(x,y,z)$ is the unique $0$-cube contained in the intersection
of halfspaces containing a majority of $x$, $y$, and $z$. A collection of
$0$-cubes $Y\subset X$ closed under taking medians is a _median subalgebra_.
Any median subalgebra $Y\subset X$ be realized as the $0$-cubes of their own
$\mathrm{CAT}(0)$ cube complex $X_{Y}$ in such a way that the medians of $X$
and $X_{Y}$ agree on $Y$. For more information, see [Nic04].

Let $G$ act on an $n$-dimensional $\mathrm{CAT}(0)$ cube complex $X$. After
passing to the cubical subdivision of $X$, we can assume $K$ fixes a $0$-cube
of $X$. Let $Y$ denote the set of $0$-cubes fixed by $K$, and observe that $Y$
is a median subalgebra. The action of $N=G/K$ on $Y$ has a finite orbit, since
$Y$ can be realized as the $0$-skeleton of a $\mathrm{CAT}(0)$ cube complex.
Consequently, the action of $G$ on $X$ has a finite orbit, so there exists a
global fixed-point. ∎

###  5.3. Main Theorem

######  Definition 5.8.

Let $\Sigma$ be an automaton over $S$, and let $v\in\Sigma$ be a vertex. We
define $\mathcal{L}_{\Sigma}^{v}=\\{w:w\text{ labels a directed path
}P\to\Sigma\text{ with initial vertex }v\\}$. Note that
$\mathcal{L}_{\Sigma}=\mathcal{L}_{\Sigma}^{\mathfrak{s}}$ where
$\mathfrak{s}\in\Sigma$ is the start vertex. If $\Sigma$ has $\lambda$-large
growth, then for a constant $c>0$, $\mathcal{L}_{\Sigma}^{v}$ contains at
least $c(\lambda|S^{\pm}|)^{L}$ words of length $L$. Consequently, if
$\lambda>|S^{\pm}|^{d-1}$, then
$\mathbf{P}\\{R_{d,L}\cap\mathcal{L}_{\Sigma}^{v}\neq\emptyset\\}\to 1$ as
$L\to\infty$ by Lemma 5.3.

Suppose for $m>0$ we have $\lambda>|S^{\pm}|^{m(d-1)}$. We define
$\widehat{\mathcal{L}}_{\Sigma}^{v}\subset\mathcal{L}_{\Sigma}^{v}$ to be the
sublanguage whose word lengths are a multiple of $m$. We can view
$\widehat{\mathcal{L}}_{\Sigma}^{v}$ as a language over $\widehat{S}$ or a
language over $S$. As a language over $\widehat{S}$,
$\widehat{\mathcal{L}}_{\Sigma}^{v}$ has density $d^{\prime}>1-d$. And as a
language over $S$, $\widehat{\mathcal{L}}_{\Sigma}^{v}$ has $A_{0}$-density
$d^{\prime}$.

###### Proof of Theorem 1.2.

Set $\lambda=\min\\{\frac{1}{3},\frac{2}{3}\theta(n,\frac{3}{4})\\}$, where
$\theta(n,\epsilon_{1})$ is the function from Theorem 4.17. Fix $d\in(0,1)$,
and take $m$ sufficiently large so that $\lambda>1/|S^{\pm}|^{md}$. Let
$\widehat{S}\cup\widehat{S}^{-1}$ be a partition of $(S^{\pm})^{m}$ as in
Definition 5.4. Let $\\{\Sigma_{i}\\}$ be the set of all automata over
$\widehat{S}$ with $\lambda$-large growth and at most
$(|\widehat{S}^{\pm}|n+1)^{n}$ vertices.

We focus our attention on $A_{r}\subset\mathbf{N}$ for some $0\leq r<m$. Since
$\lambda>|S^{\pm}|^{m(1-d)}$, the language
$\widehat{\mathcal{L}}_{\Sigma}^{v}$ from Definition 5.8 has density
$d^{\prime}>1-d$ for any $v\in\Sigma\in\\{\Sigma_{i}\\}$. Viewed as a language
over $S$, $\widehat{\mathcal{L}}_{\Sigma}^{v}$ has $A_{0}$-density
$d^{\prime}$. Thus fixing an arbitrary word $w$ of length $r$ over $S$, the
language $w\widehat{\mathcal{L}}_{\Sigma}^{v}$ has $A_{r}$-density
$d^{\prime}$. Similarly, $\widehat{\mathcal{L}}_{\Sigma}w^{-1}$ has
$A_{r}$-density $d^{\prime}$. Hence for $L\in A_{r}$, $\mathbf{P}\\{\forall
v\in\Sigma\in\\{\Sigma_{i}\\}(R_{d,L}\cap
w\widehat{\mathcal{L}}_{\Sigma}^{v}\neq\emptyset)\text{ and
}R_{d,L}\cap\widehat{\mathcal{L}}_{\Sigma}w^{-1}\neq\emptyset\\}\to 1$ as
$L\to\infty$. Supposing all intersections are nonempty, let $R_{1}w^{-1}\in
R_{d,L}\cap\widehat{\mathcal{L}}_{\Sigma}w^{-1}$, and let $wR_{2}\in
R_{d,L}\cap w\widehat{\mathcal{L}}_{\Sigma}^{v}$, were $v$ is the terminal
vertex of the path $P\to\Sigma$ labeled by $R_{1}$. By construction, the
concatenation $R_{1}R_{2}$ labels a directed path $P\to\Sigma$ beginning at
the start vertex. Also, if
$\widehat{G}_{m}=\langle\widehat{S}\mid\widehat{R}\rangle$ is the
$m$-associated group of $G=\langle S\mid R\rangle$, then
$R_{1}R_{2}\in\widehat{R}$. Since $r$ was arbitrary and finite, we have shown
that
$\mathbf{P}\\{\forall\Sigma\in\\{\Sigma_{i}\\}(\widehat{R}\cap\mathcal{L}_{\Sigma}\neq\emptyset)\\}\to
1$ as $L\to\infty$, where $\widehat{R}$ is the set of relators for the
$m$-associated group $\widehat{G}_{m}$ to $G$.

The above argument implies $\widehat{G}_{m}$ has property $F\mathcal{C}_{n}$
w.o.p. Indeed, if $\widehat{G}_{m}$ acted without global fixed-point on an
$n$-dimensional $\mathrm{CAT}(0)$ cube complex, then there would be an action
$F_{\widehat{S}}\to\operatorname{Isom}(X)$ without global fixed-point. Fix a
$0$-cube $x\in X$ minimizing $\sum_{s\in\widehat{S}^{\pm}}\mathsf{d}(x,sx)$.
If $|\operatorname{Fix}(x)|\geq\frac{1}{3}|\widehat{S}^{\pm}|$, then there
exists an automaton $\Sigma\in\\{\Sigma_{i}\\}$ such that $\hat{w}x\neq x$ for
all $w\in\mathcal{L}_{\Sigma}$ by Lemma 4.5. But since
$\mathcal{L}_{\Sigma}\cap\widehat{R}\neq\emptyset$ with overwhelming
probability, this is a contradiction. So suppose
$|\operatorname{Fix}(x)|<\frac{1}{3}|\widehat{S}^{\pm}|$. We can pass to a
subset $\mathsf{S}\subset\widehat{S}$ disjoint from $\operatorname{Fix}(x)$
with $|\mathsf{S}^{\pm}|\geq\frac{2}{3}|\widehat{S}^{\pm}|$. With the previous
generating set $\widehat{S}$, we had
$|\mathcal{B}(H)|\leq\frac{1}{2}|\widehat{S}^{\pm}|$ for each
$H\in\mathcal{H}$ by Lemma 4.14, so
$|\mathcal{B}(H)|\leq\frac{3}{4}|\mathsf{S}^{\pm}|$. By Theorem 4.17, there
exists a progressing automaton $\Sigma$ over $\mathsf{S}$ with at most
$(|\mathsf{S}^{\pm}|+1)^{n}$ vertices and $\theta(n,\frac{3}{4})$-large
growth. Considered as an automaton over $S$, $\Sigma$ has
$\frac{2}{3}\theta(n,\frac{3}{4})$-large growth, thus
$\Sigma\in\\{\Sigma_{i}\\}$. Since $\Sigma$ is progressing, $\hat{w}x\neq x$
for each $w\in\mathcal{L}_{\Sigma}$. As before, this leads to a contradiction.

Finally, since $\widehat{G}_{m}$ has $F\mathcal{C}_{n}$, its quotient $H_{m}$
has $F\mathcal{C}_{n}$ w.o.p. by Lemma 5.7. And since $H_{m}<G$ is finite
index, $G$ has $F\mathcal{C}_{n}$ w.o.p. by Lemma 5.6. ∎

###  5.4. Reduced words, the Rips construction, and an $F\mathcal{C}_{\infty}$
cubulated group

Here we provide the proofs of Theorem 1.3, Corollary 1.6, and Theorem 1.5, all
stated in the introdution. The proof of Theorem 1.3 is similar the proofs of
[DGP11, Lemma 3.4] and [Mun22, Lemma 5.5]. We sketch the argument below.

###### Proof Sketch for Theorem 1.3..

One would like to repeat the proof of Theorem 1.2. When $F_{\widehat{S}}$ acts
without global fixed-point on an $n$-dimensional $\mathrm{CAT}(0)$ cube
complex and $x\in X^{0}$ minimizes
$\sum_{s\in\widehat{S}^{\pm}}\mathsf{d}(x,sx)$, Lemma 4.5 and Theorem 4.17
guarantee the existence of a progressing automaton with $\lambda$-large
growth, where $\lambda$ is the same as in the proof of Theorem 1.2. Moreover,
the automaton is one of a finite collection $\\{\Sigma_{i}\\}$.

The issue is that the accepted language $\mathcal{L}(\Sigma)$ of an automaton
$\Sigma\in\\{\Sigma_{i}\\}$ may contain unreduced words when interpreted as a
language over $S$. This can be remedied by adjusting the automata in
$\\{\Sigma_{i}\\}$, at the cost of increasing the number of vertices by a
factor of $|S^{\pm}|$ and reducing the growth to
$\lambda-\frac{1}{|S^{\pm}|}$. We illustrate this adjustment below.

Let $\Sigma=(V,E)\in\\{\Sigma_{i}\\}$, and let $v\in V-\\{\mathfrak{s}\\}$ be
a vertex with incoming edges $E_{+}$ and outgoing edges $E_{-}$. For $s\in
S^{\pm}$, let $E_{+}(s)$ denote the incoming edges whose label is a word
ending with $s$, and let $E_{-}(s)$ denote the outgoing edges whose label is a
word not beginning with $s^{-1}$. The sets of edges $\\{E_{+}(s)\\}_{s\in
S^{\pm}}$ partition $E_{+}$, but the $E_{-}(s)$ may intersect for distinct
$s$. We replace $v$ with a collection of vertices $\\{(v,s)\\}_{s\in S^{\pm}}$
and adjust the edges as follows. For each $s\in S^{\pm}$, the edges of
$E_{+}(s)$ are redirected to be incoming at $(v,s)$. And for each $s\in
S^{\pm}$, we make a copy of $E_{-}(s)$ outgoing at $(v,s)$ with the same
terminal vertices as the original collection $E_{-}(s)$. The result is that if
$w$ and $w^{\prime}$ are reduced words labeling incoming and outgoing edges at
some $(v,s)$, then $ww^{\prime}$ is also reduced. Also, if
$|E_{-}|\geq\lambda|\widehat{S}^{\pm}|$, then
$|E_{-}(s)|\geq(\lambda-\frac{1}{|S^{\pm}|})|\widehat{S}^{\pm}|$. Performing
this procedure at each vertex $v\in V-\\{\mathfrak{s}\\}$, we get an automaton
$\Sigma^{\prime}$ with at most $|S^{\pm}||V|$ vertices, at least
$(\lambda-\frac{1}{|S^{\pm}|})$-large growth, and whose accepted language
$\mathcal{L}(\Sigma^{\prime})\subset\mathcal{L}(\Sigma)$ consists only of
reduced words.

Finally, if $|S^{\pm}|$ is sufficiently large so that
$\lambda-\frac{1}{|S^{\pm}|}>0$, then the proof of Theorem 1.2 can be repeated
with the adjusted family $\\{\Sigma_{i}^{\prime}\\}$. ∎

###### Proof of Theorem 1.5.

By Corollary 1.4, there exists a sequence $\\{\langle S_{i}\mid
R_{i}\rangle\\}_{i\in\mathbf{N}}$ of $C^{\prime}(1/6)$ presentations so that
the group defined by $\langle S_{i}\mid R_{i}\rangle$ has $F\mathcal{C}_{i}$.
Choose the presentations so that $|S_{i}|=k(i)$ for each $i$, where $k(i)$ is
as in Theorem 1.3. Additionally, choose $\langle S_{i}\mid R_{i}\rangle$ so
that there exists a partition $R_{i}=R^{1}_{i}\sqcup R^{2}_{i}$ such that
$G_{i}\vcentcolon=\langle S_{i}\mid R^{1}_{i}\rangle$ has $F\mathcal{C}_{i}$
and $|R^{2}_{i}|=k(i-1)+k(i+1)$. This is possible since removing a fixed
finite number of relators from a random presentation does not affect that it
has $F\mathcal{C}_{i}$ with overwhelming probability.

Let $B$ denote $\mathbf{N}$ with its natural cell structure and a copy of the
presentation complex of $G_{i}$ wedge summed at $i\in\mathbf{N}$ for each $i$.
Let $\\{s_{i,1},\ldots,s_{i,k(i)}\\}$ be the $k(i)$ 1-cell loops wedge summed
at $i$, corresponding to the generators of $G_{i}$, and let $t_{i}$ denote the
1-cell $[i,i+1]$ of $B$.

Note that $\pi_{1}B=\ast_{i}G_{i}$. To obtain our desired group, we modify $B$
to obtain a $C^{\prime}(1/6)$ complex $Z$ so that $\pi_{1}Z$ is a quotient of
$G_{i}$ for each $i$. To do this, we add 2-cells so that each generator of
$G_{i}$ at $i\in B$ becomes equal to a word in the generators of $G_{i-1}$ and
also equal to a word in the generators of $G_{i+1}$. For each 1-cell loop
$s_{i,j}$ at $i$, pick a 2-cell $l(i,j)$ in $R^{2}_{i-1}$ and a 2-cell
$r(i,j)$ in $R^{2}_{i+1}$. Since $|R^{2}_{i}|=k(i-1)+k(i+1)$ for all $i$, this
can be done so that the $l(i,j)$ and $r(i,j)$ are distinct for all
$i\in\mathbf{N}$ and $j\in\\{1,\ldots,k(i)\\}$. Let $\bar{l}(i,j)$ and
$\bar{r}(i,j)$ denote the boundary paths of $l(i,j)$ and $r(i,j)$. The complex
$Z$ is obtained from $B$ by attaching 2-cells along the paths
$s_{i,j}t_{i-1}^{-1}\bar{l}(i,j)t_{i-1}$ and
$s_{i,j}t_{i}\bar{r}(i,j)t_{i}^{-1}$ for each $i\in\mathbf{N}$,
$j\in\\{1,\ldots,k(i)\\}$.

The paths $\bar{l}(i,j)$ and $\bar{r}(i,j)$ define elements of $G_{i-1}$ and
$G_{i+1}$. Thus the 2-cells added to $B$ to obtain $Z$ give us
$\pi_{1}Z=\ast_{i}G_{i}/\llangle s_{i,j}=\bar{l}(i,j)=\bar{r}(i,j)\rrangle$.
For any $i\in\mathbf{N}$, $\\{s_{i,1},\ldots,s_{i,k(i)}\\}$ generate
$\pi_{1}Z$ and are subject to all the relations in $G_{i}$. Consequently
$\pi_{1}Z$ is finitely generated and has $F\mathcal{C}_{n}$ for all $n$. Since
$Z$ is $C^{\prime}(1/6)$ and no attaching map of a 2-cell is a proper power,
$Z$ is aspherical. In particular $\pi_{1}Z$ has geometric (and cohmological)
dimension 2 [LS77]. Since $Z$ is a locally finite aspherical $C^{\prime}(1/6)$
complex, $\pi_{1}Z$ acts freely on a locally finite $\mathrm{CAT}(0)$ cube
complex [Wis04]. ∎

###### Proof of Corollary 1.6.

Recall $\mathcal{B}\cup\\{B_{1},\ldots,B_{l}\\}\cup\\{B_{i,j}\\}_{1\leq i\leq
m,1\leq j\leq k(n)}$ is a random set of reduced words of length $L$ and
density $d$. The proof of Theorem 1.3 can be applied to the group $\langle
b_{1},\ldots,b_{k(n)}\mid\mathcal{B}\rangle$, since $\mathcal{B}$ differs only
by a finite set $\\{B_{1},\ldots,B_{l}\\}\cup\\{B_{i,j}\\}_{1\leq i\leq
m,1\leq j\leq k(n)}$ from a random set of words. Thus $\langle
b_{1},\ldots,b_{k(n)}\mid\mathcal{B}\rangle$ has $F\mathcal{C}_{n}$ with
overwhelming probability.

The subgroup $F$ of $\Gamma$ is a quotient of $\langle
b_{1},\ldots,b_{k(n)}\mid\mathcal{B}\rangle$, so $F$ has $F\mathcal{C}_{n}$
with overwhelming probability by Lemma 5.7. By construction, $F$ is a normal
subgroup of $\Gamma$ and $\Gamma/F=G$. Thus, by Lemma 1.7, $\Gamma$ has
property $F\mathcal{C}_{n}$ with overwhelming probability. The usual argument
that reduced word random groups are $C^{\prime}(1/p)$ at densities
$d<\frac{1}{2p}$ applies to show $\Gamma$ is $C^{\prime}(1/p)$ with
overwhelming probability [Gro91, §9.B]. ∎

## References

  * [Ash22] Calum J Ashcroft.  Random groups do not have Property $\mathrm{(T)}$ at densities below 1/4.  arXiv e-prints, page arXiv:2206.14616, June 2022.
  * [BH99] Martin R. Bridson and André Haefliger.  Metric spaces of non-positive curvature, volume 319 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer-Verlag, Berlin, 1999.
  * [CW15] Danny Calegari and Alden Walker.  Random groups contain surface subgroups.  J. Amer. Math. Soc., 28(2):383–419, 2015.
  * [DGP11] François Dahmani, Vincent Guirardel, and Piotr Przytycki.  Random groups do not split.  Math. Ann., 349(3):657–673, 2011.
  * [Far05] Daniel S. Farley.  Actions of picture groups on CAT(0) cubical complexes.  Geom. Dedicata, 110:221–242, 2005.
  * [Gen19] Anthony Genevois.  Hyperbolic and cubical rigidities of Thompson’s group $V$.  J. Group Theory, 22(2):313–345, 2019.
  * [Gen23] Anthony Genevois.  Examples of cubulable groups with fixed-point properties, 2023.
  * [Gro91] Mikhail Gromov.  Asymptotic invariants of infinite groups.  In Geometric Group Theory, volume 2 of London Mathematical Society Lecture Note Series, pages 1–295, Sussex, 1991. Cambridge University Press.
  * [Jah11] Giso Jahncke.  Zufallsgruppen und die Eigenschaft $\mathrm{F}\mathbb{R}$, (German) Random Groups and the Property $\mathrm{F}\mathbb{R}$.  Bachelor’s thesis, University of Kiel, 2011.
  * [Jan20] Kasia Jankiewicz.  Lower bounds on cubical dimension of $C^{\prime}(1/6)$ groups.  Proc. Amer. Math. Soc., 148(8):3293–3306, 2020.
  * [JW21] Kasia Jankiewicz and Daniel T. Wise.  A curiously cubulated group.  Geom. Dedicata, 212:17–19, 2021.
  * [KK13] Marcin Kotowski and Michał Kotowski.  Random groups and property $\mathrm{(T)}$: Żuk’s theorem revisited.  J. Lond. Math. Soc. (2), 88(2):396–416, 2013.
  * [LS77] Roger C. Lyndon and Paul E. Schupp.  Combinatorial group theory, volume Band 89 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas].  Springer-Verlag, Berlin-New York, 1977.
  * [Mun22] Zachary Munro.  Random group actions on $\mathrm{CAT}(0)$ square complexes, 2022.
  * [Nic04] Bogdan Nica.  Cubulating spaces with walls.  Algebr. Geom. Topol., 4:297–309, 2004.
  * [NR97] Graham Niblo and Lawrence Reeves.  Groups acting on $\mathrm{CAT(0)}$ cube complexes.  Geometry and Topology Monographs: The Epstein Birthday Schrift, 1:1–7, 1997.
  * [Oll04] Y. Ollivier.  Sharp phase transition theorems for hyperbolicity of random groups.  Geom. Funct. Anal., 14(3):595–679, 2004.
  * [Orl17] Damian Orlef.  Random groups are not left-orderable.  Colloq. Math., 150(2):175–185, 2017.
  * [OW11] Yann Ollivier and Daniel Wise.  Cubulating random groups at density less than 1/6.  Transactions of the American Mathematical Society, 363(9):4701–4733, 2011.
  * [Rip82] E. Rips.  Subgroups of small Cancellation Groups.  Bulletin of the London Mathematical Society, 14(1):45–47, 01 1982\.
  * [Sag14] Michah Sageev.  $\mathrm{CAT(0)}$ cube complexes and groups.  In Geometric group theory, volume 21 of IAS/Park City Math. Ser., pages 7–54. Amer. Math. Soc., Providence, RI, 2014.
  * [Sta83] John R. Stallings.  Topology of finite graphs.  Invent. Math., 71(3):551–565, 1983.
  * [Wis04] D. T. Wise.  Cubulating small cancellation groups.  Geom. Funct. Anal., 14(1):150–214, 2004.
  * [Wis21] Daniel T. Wise.  The structure of groups with a quasiconvex hierarchy, volume 209 of Annals of Mathematics Studies.  Princeton University Press, Princeton, NJ, [2021] ©2021.
  * [Ż03] Andrzej Żuk.  Property $\mathrm{(T)}$ and Kazhdan constants for discrete groups.  Geometric and Functional Analysis, 13(3):643–670, 2003.