# Efficient computations with counting functions
on free groups and free monoids

Tobias Hartnick, Alexey Talambutsa

###### Abstract

We present efficient algorithms to decide whether two given counting functions
on non-abelian free groups or monoids are at bounded distance from each other
and to decide whether two given counting quasimorphisms on non-abelian free
groups are cohomologous. We work in the multi-tape Turing machine model with
non-constant time arithmetic operations. In the case of integer coefficients
we construct an algorithm of linear space and time complexity (assuming that
the rank is at least $3$ in the monoid case). In the case of rational
coefficients we prove that the time complexity is $O(N\log N)$, where $N$
denotes the size of the input, i.e. it is as fast as addition of rational
numbers (implemented using the Harvey–van der Hoeven algorithm for integer
multiplication). These algorithms are based on our previous work which
characterizes bounded counting functions.

##  1 Introduction

###  1.1 From combinatorics of words to quasimorphisms

The study of words over a finite alphabet $S$ is a central topic in many areas
of mathematics and computer science, including algebra, combinatorics,
dynamical systems, decision problems and many others. In particular, the
combinatorics of such words have been studied intensively during the last 50
years in algebra and computer science – see e.g. [17] and [15] for two very
different perspectives. Of fundamental importance for the combinatorics of
words is the _subword relation_ : A word $v=s_{1}\cdots s_{l}$ with
$s_{1},\dots,s_{l}\in S$ is called a _subword_ of a word $w=r_{1}\cdots r_{m}$
with $r_{1},\dots,r_{m}\in S$ provided there is some $j\in\\{1,\dots,m-l+1\\}$
such that $s_{i}=r_{j+i}\text{ for all }i\in\\{1,\dots,l\\}$; we then call
$\\{j+1,\dots,j+l\\}$ an _occurence_ of $v$ in $w$. Many famous problems
concerning the combinatorics of words are related to this subword relation.
For example, the question whether a word of length $N$ can be reconstructed
from the set of its subwords of length up to $f(N)$ was solved in [15] and
independently by V.I. Levenstein in [14], and the corresponding length was
shown to be $f(N)=\lceil\frac{N+1}{2}\rceil$. If one replaces the set of
subwords by the _multiset_ of subwords, then the currently best known lower
bound is $f(N)\leq\lfloor\frac{16}{7}\sqrt{N}\rfloor+5$, due to Krasikov and
Roditty [13].

The present article is concerned with a quantitative refinement of the subword
relation: Given two words $v,w$ over $S$ we denote by $\rho_{v}(w)$ the number
of (possibly overlapping) occurences of $v$ in $w$; thus by definition we have
$\rho_{v}(w)>0$ if and only if $v$ is a subword of $w$. The collection $S^{*}$
of all words over $S$ is a free monoid, and we can consider $\rho_{v}$ as a
function $\rho_{v}:S^{*}\to\mathbb{N}_{0}$, called the _$v$ -counting
functions_. If $v$ happens to be a single letter, then this counting function
is actually a monoid homomorphism; in general it will only be a
_quasimorphism_ in the sense that

$\sup_{w_{1},w_{2}\in
S^{*}}|\rho_{v}(w_{1}w_{2})-\rho_{v}(w_{1})-\rho_{v}(w_{2})|<\infty.$

To summarize, the counting of subwords is a natural source of quasimorphisms
on free monoids.

###  1.2 Computations in bounded cohomology of free groups

While not much is known about general quasimorphisms on monoids, there is a
well-developed theory of quasimorphisms on groups, since these are closely
related to bounded cohomology [5] and stable commutator length [2]. Note that
if $F_{n}$ is a free group of rank $n\geq 2$ with basis
$S=\\{a_{1},\dots,a_{n}\\}$, then we can identify elements of $F_{n}$ with
reduced words over the extended alphabet
$S^{\pm}=\\{a_{1},\dots,a_{n},a_{1}^{-1},\dots,a_{n}^{-1}\\}$. This then
allows us to define, for every $v\in F_{n}$, a corresponding $v$-counting
function $\rho_{v}:F_{n}\to\mathbb{N}_{0}$. It was pointed out by Brooks [1]
that the symmetrizations

$\varphi_{v}:F_{n}\to\mathbb{Z},\quad w\mapsto\rho_{v}(w)-\rho_{v}(w^{-1})$

of these counting functions are quasimorphism on the free group;
symmetrization is needed to deal with the effects of cancellations in free
groups. In the sequel we refer to $\varphi_{v}$ as the _$v$ -counting
quasimorphism_. Finite linear combinations of these quasimorphisms are known
as _counting quasimorphisms_ or sometimes _quasimorphisms of finite type_.
Similarly, finite linear combinations of $v$-counting functions are simply
known as _counting functions_.

Every quasimorphism $\varphi:F_{n}\to\mathbb{R}$ gives rise to a bounded
$2$-cocycle $d\varphi$ on $F_{n}$ given by
$d\varphi(x,y):=\varphi(y)-\varphi(xy)+\varphi(x)$ and hence defines a class
in the second bounded cohomology $H^{2}_{b}(F_{n};\mathbb{R})$ (see [5]). We
say that two quasimorphisms are _cohomologous_ if they define the same bounded
cohomology class. In particular, this is the case if they are at bounded
distance from each other with respect to the $\ell^{\infty}$-norm.

It follows from our previous results of [9] that the question whether two
given counting quasimorphisms (say, with coefficients in $\mathbb{Z}$ or
$\mathbb{Q}$) are cohomologous is decidable; in fact, one can extract from [9]
an explicit algorithm which decides this question. This algorithm is actually
sufficient for many applications, see e.g. the work of Hase [10] for an
application concerning the $\mathrm{Out}(F_{n})$-action on
$H^{2}_{b}(F_{n};\mathbb{R})$. However, while the algorithm sketched in [9] is
effective, it is certainly not efficient. On the contrary, the purpose of the
present article is to provide an _efficient_ algorithm and to analyze its
complexity. Our main result then reads as follows:

######  Theorem 1.1.

Let $n\geq 2$ and $\mathfrak{N}\in\\{\mathbb{Z},\mathbb{Q}\\}$. Then there
exists an algorithm which, given two counting quasimorphisms on $F_{n}$ with
coefficients in $\mathfrak{N}$, decides whether they are cohomologous.
Moreover, this algorithm can be implemented in such a way that its runtime is
at most $O(N)$ if $\mathfrak{N}=\mathbb{Z}$ and at most $O(N\log N)$ if
$\mathfrak{N}=\mathbb{Q}$, where $N$ denotes the size of the input data and
the implied constants depend on $n$.

We will provide a more precise formulation of Theorem 1.1 in Corollary 5.9
below after clarifying the data structures which will be used to encode
counting quasimorphisms. In particular, we will specify precisely what we mean
by the “size” of the input data. As far as our model of computation is
concerned, we will be working in the multi-tape Turing machine model
throughout. There are a couple of variants of Theorem 1.1 worth mentioning

  * •

Instead of deciding whether two given counting quasimorphisms are cohomologous
we also decide with essentially the same runtime whether they are at bounded
distance from each other (see Corollary 5.9).

  * •

Instead of considering counting quasimorphisms we can also consider counting
functions, i.e. linear combinations of $v$-counting functions. Our algorithms
still applies, essentially with the same runtime (see Corollary 5.9).

  * •

Instead of considering counting functions over the free group $F_{n}$ we can
also consider counting functions over the free monoid $M_{n}$. The same
runtime estimates as above also hold in this case, provided $n\geq 3$ (see
Corollary 3.3).

The fact that the runtime is linear in the case of $\mathbb{Z}$-coefficients
is connected to the fact that addition of integers can be implemented in
linear time. On the contrary, it is currently not known whether addition of
large rational numbers can be implemented in linear time. In view of the
recent work of Harvey and van der Hoeven [11], $T(N):=N\log N$ is currently
the best known time complexity for addition of rational numbers of size at
most $N$, if rational numbers are encoded as (possibly unreduced) mixed
fractions (see the discussion in Appendix A), and this is how this function
enters into the proof of the theorem. The reader is invited to check that our
results also holds for more general coefficient groups
$\mathfrak{N}\subset\mathbb{R}$ instead of $\mathbb{Z}$ or $\mathbb{Q}$, as
long as addition, subtraction and comparison in $\mathfrak{N}$ can be carried
out efficiently by a multi-tape Turing machine.

###  1.3 Towards applications

Theorem 1.1 can be seen as a starting point for efficient computations in the
bounded cohomology of the free group or more precisely, for efficient
computations in its subspace $H^{2}_{b,{\rm fin}}(F_{2},\mathbb{Q})\subset
H^{2}_{b}(F_{2},\mathbb{R})$ generated by counting quasimorphisms with
rational coefficients. This subspace is actually quite remarkable: As pointed
out by Grigorchuk [6] it is dense in $H^{2}_{b}(F_{2},\mathbb{R})$ for a
suitable topology (namely the topology of pointwise convergence of homogeneous
representatives, cf. [7]) and by a result of Schweitzer and the first author
it is moreover invariant under the natural action of $\mathrm{Out}(F_{n})$ and
hence independent of the chosen basis [7]. Nevertheless we have to admit that
there are many explicit examples of classes in $H^{2}_{b}(F_{2},\mathbb{R})$
which are of _infinite type_ (i.e. not representable by counting
quasimorphisms), and it is still a major open problem how to decide whether
two such quasimorphisms are cohomologous.

This latter question is actually relevant beyond the theory of free groups.
Namely, if $G$ is an arbitrary group and $F\subset G$ is a finitely-generated
free subgroup, then every bounded cohomology class in $G$ restricts to a
bounded cohomology class of $F$. It turns out that for a large class of groups
with weak negative curvature properties (namely, _acylindrically hyperbolic
groups_ in the sense of [16]), every $2$nd bounded cohomology class is
uniquely determined by its restrictions to (hyperbolically embedded) free
subgroups [8]. This provides a strong motivation to look for algorithms which
decide whether two given quasimorphisms on a free group are cohomologous.
Theorem 1.1 solves this problem for quasimorphisms of finite type, whereas the
case of quasimorphisms of infinite type remains open for the moment.

###  1.4 Organization of the article

The goal of this article is to establish Theorem 1.1 and all of the variants
mentioned thereafter. It turns out that the case of counting functions over
free monoids is notationally simpler to handle than the case of counting
quasimorphisms over free groups, but uses essentially the same idea. In the
body of this text we will thus first discuss algorithms which are concerned
with counting functions over free monoids. An informal discussion will be
given in Section 2, and after formalizing the relevant concepts in Section 3,
the monoid version of Theorem 1.1 (i.e. Corollary 3.3) will be established in
Section 4 by constructing and analyzing the desired algorithm. In the final
section (Section 5) we will then explain, how this algorithm has to be
modified in the group case - this requires a lot of additional notation, but
very few additional ideas. In the appendix we discuss in detail the
implementations of the arithmetic operations for our coefficient groups, since
these crucially influence the runtime of our algorithm.

Notation: In the sequel we denote by $\mathbb{N}=\\{1,2,\dots\\}$ the set of
natural numbers (starting from $1$) and by $\mathbb{N}_{0}=\\{0,1,2,\dots\\}$
its union with $\\{0\\}$. The letters $\mathbb{Z}$ and $\mathbb{Q}$ denote the
ring of integers and the field of rational numbers respectively. For real-
valued functions $f,g:\mathbb{N}\to[0,\infty)$ we are going to use the
standard Bachmann-Landau notation

$g(x)=O(f(x))\quad:\Leftrightarrow\quad\limsup(g(x)/f(x))<\infty.$

By a slight abuse of notation we use the same notation also for functions
which are only defined on a cofinite subset of $\mathbb{N}$.

Acknowledgments: T.H. is grateful to Simons Foundation for supporting his
visit to Steklov International Mathematical Center. A.T. is grateful to the
Mathematics Department of Technion for supporting his visits. The work of A.T.
was performed in Steklov International Mathematical Center and partially
supported by the Ministry of Science and Higher Education of the Russian
Federation (agreement no. 075-15-2019-1614). A.T. also would like to thank
M.N. Vyalyi for valuable discussions concerning rational arithmetic
algorithms.

##  2 Counting functions on monoids

Throughout this section let $n\geq 2$ be a fixed integer. We will discuss the
equivalence problem for counting functions over the free monoid $M_{n}$ with
coefficients in either $\mathbb{Z}$ or $\mathbb{Q}$ and describe an algorithm
for its solution in an informal way.

###  2.1 Representing counting functions

Let $\mathtt{A}=\\{\mathtt{a_{1}},\dots,\mathtt{a_{n}}\\}$ be a finite set of
cardinality $n\geq 2$. We identify elements of the free monoid $M_{n}$ with
finite words over $\mathtt{A}$ (including the empty word $\varepsilon$) and
given $w\in M_{n}$ denote by $|w|$ the _word length_ of $w$, i.e. the number
of letters of the word $w$. We also fix a coefficient group
$\mathfrak{N}\in\\{\mathbb{Z},\mathbb{Q}\\}$.

Given two words $v=s_{1}\cdots s_{l}$ and $w=r_{1}\cdots r_{m}$ over
$\mathtt{A}$ with $m\geq l\geq 0$ we denote by $\rho_{v}(w)$ the number of
(possibly overlapping) occurrences of $v$ in $w$, i.e.

$\rho_{v}(w)=|\\{j\in\\{1,\dots,m-l+1\\}\mid s_{i}=r_{j+i}\text{ for all
}i\in\\{1,\dots,l\\}\\}|.$

If $m<l$, we set $\rho_{v}(w):=0$ by convention. The function
$\rho_{v}:M_{n}\to\mathbb{N}$ is then called the _$v$ -counting function_ on
$M_{n}$. With this definition we have $\rho_{\varepsilon}(w)=|w|$. By a
_counting function_ with coefficients in $\mathfrak{N}$ we mean a function of
the form

$f=\sum_{i=1}^{N}x_{i}\rho_{w_{i}}:M_{n}\to\mathfrak{N}$

where $N\in\mathbb{N}_{0}$, $w_{1},\dots w_{n}\in M_{n}$ are words and
$x_{1},\dots,x_{N}\in\mathfrak{N}$ are coefficients. We say that two counting
functions $f_{1}$ and $f_{2}$ are _equivalent_ , denoted $f_{1}\sim f_{2}$
provided

$\|f_{1}-f_{2}\|_{\infty}<\infty.$

In this section we are going to use two different encodings of counting
functions over $M_{n}$ with coefficients in $\mathfrak{N}$, namely word-
number-lists and weighted trees. While weighted trees are useful for
visualizations purposes, we will mostly describe our algorithms in terms of
word-number-lists, since these are more closely related to the data structures
that we will use in the actual implementations of our algorithms below.

####  2.1.1 Word-number-lists

By a _word-number-list_ we mean a list of the form
$L=((w_{1},x_{1}),\dots,(w_{N},x_{N}))$, where $N\in\mathbb{N}_{0}$ and
$w_{j}\in M_{n}$ and $x_{j}\in\mathfrak{N}$ for all $j\in\\{1,\dots,N\\}$. The
_associated counting function_ is

$\rho_{L}=\sum_{i=1}^{N}x_{i}\rho_{w_{i}}.$ (2.1)

Thus every word-number-list encodes a counting function, and by definition
every counting function is encoded by a word-number-list. However, this word-
number-list is not unique, since it may e.g. happen that some words repeat in
the list.

####  2.1.2 Weighted trees

Following [9] we visualize every word-number-list by a finite weighted tree as
follows: Denote by $T_{n}$ the right-Cayley tree of $M_{n}$ with respect to
the free generating set $\mathtt{A}$. Thus, by definition, the vertex set of
$T_{n}$ is given by $V(T_{n})=M_{n}$, and two vertices $x$ and $y$ are joined
by an edge if and only if there exists $i\in\\{1,\dots,n\\}$ such that
$x=y\mathtt{a}_{i}$ or $y=x\mathtt{a}_{i}$. We consider $T_{n}$ as a rooted
tree with root given by the empty word $\varepsilon$. Given a word-number-list
$L=((w_{1},x_{1}),\dots,(w_{N},x_{N})$ we denote by $T_{L}$ the subtree of
$T_{n}$ given by the convex hull of the vertex set

$V(T_{L}):=\\{w\in
M_{n}\mid\exists\,j\in\\{1,\dots,N\\}:w=w_{j}\\}\cup\\{\varepsilon\\}.$

We then define a _weight function_ $\alpha_{L}:V(T_{L})\to\mathfrak{N}$ by

$\alpha_{L}(w)=\sum_{w_{j}=w}x_{j}.$

For example, the weighted tree $(T_{L},\alpha_{L})$ associated with the list

$L=((\varepsilon,-1),(\mathtt{a}_{2},6),(\mathtt{a}_{3},-1),(\mathtt{a}_{1}^{2},4),(\mathtt{a}_{1}\mathtt{a}_{2},4),(\mathtt{a}_{1}\mathtt{a}_{3},4),(\mathtt{a}_{3}\mathtt{a}_{1},1),(\mathtt{a}_{3}\mathtt{a}_{2},1),(\mathtt{a}_{3}^{2},1))$

is given by the following picture:

$-1$$0$$-6$$-1$$4$$4$$4$$1$$1$$1$

Different word-number-lists may give rise to the same tree, but all of these
lists correspond to the same counting function, since

$f_{L}=\sum_{w\in V(T_{L})}\alpha_{L}(w)\rho_{w}.$

In the sequel we will prefer to work with word-number-lists rather than
weighted trees, but we will occasionally use weighted trees to visualize some
of our algorithms.

###  2.2 The equivalence problem

####  2.2.1 Equivalent counting functions and equivalent word-number-lists

Recall that counting functions $f_{1}$ and $f_{2}$ are called _equivalent_
(denoted $f_{1}\sim f_{2}$) if $f_{1}-f_{2}$ is a bounded function. For every
$w\in M_{n}$ we have the obvious equivalences (see [9])

$\rho_{w}\sim\sum_{i=1}^{n}\rho_{\mathtt{a}_{i}w}\quad\text{and}\quad\rho_{w}\sim\sum_{i=1}^{n}\rho_{w\mathtt{a}_{i}}.$
(2.2)

We refer to the two kind of basic equivalences in (2.2) as _left-extension
equivalences_ and _right-extension equivalences_ respectively. It was
established in [9] that these basic equivalences span the space of all linear
relations between equivalence classes of counting functions as $w$ ranges over
all elements of $M_{n}$, but we will not need this fact here. Using left- and
right-extensions relations we can transform counting functions into equivalent
counting functions. We extend our notion of equivalence to word-number-lists
in the obvious way:

######  Definition 2.1.

Let $L_{1},L_{2}$ be two word-number-lists. We say that $L_{1}$ and $L_{2}$
are

  * •

_strictly equivalent_ , denoted $L_{1}\approx L_{2}$, if
$f_{L_{1}}=f_{L_{2}}$;

  * •

_equivalent_ , denoted $L_{1}\sim L_{2}$, if $f_{L_{1}}-f_{L_{2}}$ is bounded.

We apply the same definitions also to finite weighted trees.

####  2.2.2 Formulation of the main problem

The main algorithmic problem concerning counting functions on free monoids
that we want to solve in this article is as follows:

######  Problem 2.2 (Equivalence problem).

Given two word-number-lists $L_{1},L_{2}$, decide whether $L_{1}\sim L_{2}$.

Note that, given word-number-lists $L_{1},L_{2}$ it is easy to construct a
word-number-list $L_{3}$ with $f_{L_{3}}=f_{L_{1}}-f_{L_{2}}$. We may thus
assume in Problem 2.2 that $L_{2}=()$ is the empty word-number-list. To solve
Problem 2.2, we need the notion of a minimal word-number-list.

######  Definition 2.3.

Let $N\in\mathbb{N}_{0}$ and let $L=((w_{1},x_{1}),\dots,(w_{N},x_{N}))$ be a
word-number-list.

  1. (i)

If $N\geq 1$, then the _maximal depth_ of $L$ is defined as

$\mathtt{depth}(L):=\max\\{|w_{j}|\mid j=1,\dots,N\\};$

if $N=0$ we set $\mathtt{depth}(L):=-1$. We say that $L$ is of _constant
depth_ if $|w_{j}|=\mathtt{depth}(L)$ for all $j=1,\dots,N$. (With this
definition, the empty list is of constant depth $-1$.)

  2. (ii)

$L$ is called _minimal_ if
$\mathtt{depth}(L)=\min\\{\mathtt{depth}(L^{\prime})\mid L^{\prime}\sim L\\}$.

We employ similar terminology also for weighted trees.

######  Remark 2.4.

The following useful fact is immediate from the definition: If $L$ is a word-
number-list of maximal depth $\ell$ and $L^{\prime}$ is a word-number-list of
maximal depth $<\ell$, then the concatenation $L\cup L^{\prime}$ is minimal if
and only if $L$ is minimal. In that sense, minimality of a word-number-list
depends only on the “bottom level”.

######  Remark 2.5.

By definition, every word-number-list $L$ is equivalent to some minimal word-
number-list $L^{\prime}$, and we observe that

$L\sim()\iff\mathtt{depth}(L^{\prime})=-1$

In order to solve Problem 2.2 it thus suffices to solve the following problem.

######  Problem 2.6 (Minimality problem).

Given a word-number-list $L$, find a minimal word-number-list $L^{\prime}$
which is equivalent to $L$.

For the remainder of this section we will thus focus on Problem 2.6.

######  Remark 2.7.

We say that a word-number-list $L=((w_{1},x_{1}),\dots,(w_{N},x_{N}))$ is
_normalized_ if the words $w_{i}$ are all distinct, ordered by length and
ordered lexicographically within words of the same length, and if $x_{j}\neq
0$ for all $j\in\\{1,\dots,N\\}$. Clearly every word-number-list is strictly
equivalent to a normalized word-number-list, and hence we will mainly study
Problem 2.6 for _normalized_ lists. We will see later that (for our chosen
encoding) there is an efficient algorithm to normalize any given word-number-
list.

###  2.3 Related brotherhoods and minimality

In order to discuss our algorithms we introduce the following terminology. We
recall that $T_{n}$ denotes the right-Cayley tree of $M_{n}$ with respect to
$\mathtt{A}$; we identify elements of $M_{n}$ with vertices of $T_{n}$.

####  2.3.1 Brotherhoods

Let $w\in M_{n}=V(T_{n})$. The _depth_ of $w$ is defined as its distance from
the root. The vertices on the geodesic between $w$ and the root (including $w$
and the root) are called the _ancestors_ of $w$.

From now on assume that $w$ is not the root. Then $w$ admits a unique ancestor
$v={\rm Fa}(w)$ of distance $1$, which is called its _father_. The vertices
with the same father as $w$ are called its _brothers_ and their collection,
the _brotherhood_ of $w$, is denoted by $\\{\mathrm{Fa}(w)\ast\\}$. Thus, by
definition each brotherhood contains exactly $n$ elements.

The _depth_ of a brotherhood is defined as the depth of any of its $n$
elements. We say that two element $u,v$ of $M_{n}$ are _related_ , denoted
$u\smile v$, if they differ at most by their first letter. In this case we
also say that the brotherhoods $\\{\mathrm{Fa}(u)\ast\\}$ and
$\\{\mathrm{Fa}(v)\ast\\}$ are _related_.

If $w=\mathtt{a}_{1}\cdots\mathtt{a}_{\ell}\in M_{n}$ is of length $\ell\geq
2$, then the (possibly empty) subword
$\mathtt{a_{2}}\cdots\mathtt{a_{\ell-1}}$ is called the _stem_ of $w$. If $B$
is a brotherhood then all elements of $B$ have the same stem
$\mathrm{stem}(B)$, and two brotherhoods $B_{1}$ and $B_{2}$ of depth $\geq 2$
are related if and only if $\mathrm{stem}(B_{1})=\mathrm{stem}(B_{2})$. Given
$u\in M_{n}$, there are precisely $n$ (pairwise related) brotherhoods
$B_{1},\dots,B_{n}$ with stem $u$, and up to reordering these are given by
$B_{i}=\\{\mathtt{a}_{i}\mathtt{u}\ast\\}$.

####  2.3.2 Weighted brotherhoods

If $B$ is a brotherhood, then a normalized word-number-list
$\mathcal{B}=((w_{1},x_{1}),\dots,(w_{m},x_{m}))$ with $m\leq n$ is called a
_weighted brotherhood_ of type $B$ if the words $w_{1},\dots,w_{m}$ all belong
to $B$. Thus, we explicitly allow a weighted brotherhood to contain less than
$n$ pairs and even to be empty; if $\mathcal{B}$ is a non-empty weighted
brotherhood, then its type is uniquely determined and denoted by
$\mathrm{type}(\mathcal{B})$. By definition, every weighted brotherhood is a
list of constant depth.

We say that two non-empty weighted brotherhoods $\mathcal{B}$ and
$\mathcal{B}^{\prime}$ are _related_ if their types are related; by convention
we declare the empty weighted brotherhood to be related to every weighted
brotherhood. A weighted brotherhood
$\mathcal{B}=((w_{1},x_{1}),\dots,(w_{m},x_{m}))$ is called _constant_ if it
is either empty or if $m=n$ and ${x}_{1}=\dots={x}_{m}$. Otherwise it is
called _non-constant_.

If $L=((w_{1},x_{1}),\dots,(w_{N},x_{N}))$ is a normalized word-number-list
and $w\in M_{n}$, then we denote by $L_{\\{w\ast\\}}$ the normalized sublist
of $L$ consisting of all pairs $(w_{j},x_{j})$ from $L$ with
$w_{j}\in\\{w\ast\\}$. By definition this is a (possibly empty) weighted
brotherhood, and we refer to it as the _weighted sub-brotherhood of $L$ of
type $\\{w\ast\\}$_.

####  2.3.3 Unbalanced word-number-lists and minimality

######  Definition 2.8.

A normalized word-number-list $L$ of maximal depth $\ell$ is called
_unbalanced_ if there exist two related weighted sub-brotherhoods
$\mathcal{B}_{1}$ and $\mathcal{B}_{2}$ of $L$ of depth $\ell$ such that
$\mathcal{B}_{1}$ is non-constant and $\mathcal{B}_{2}$ is empty, otherwise it
is called _balanced_.

The following result was established in [9, Theorem 4.2] (in the language of
weighted trees):

######  Theorem 2.9.

Every unbalanced normalized word-number-list is minimal.∎

Note that one can see immediately from the associated weighted tree whether a
given normalized word-number-list is unbalanced by only looking at its bottom
level. For example, the following weighted tree (over $M_{3}$) represents an
unbalanced list, since the non-constant weighted brotherhood labeled $(4,2,1)$
is related to the empty weighted sub-brotherhood whose father is the vertex
labelled $-6$.

$17$$0$$-6$$-1$$4$$2$$1$$5$$3$$7$

###  2.4 Basic moves

We now single out to basic moves which allow one to transform a given
(normalized) word-number-list into an equivalent one; these correspond to the
two types of basic equivalences from (2.2).

####  2.4.1 Pruning

Let $L$ be a normalized word-number-list of maximal depth $\ell\geq 1$ and let
$B=\\{w\ast\\}$ for some $w\in M_{n}$ of length $|w|=\ell-1$. We then say that
$L_{B}$ is _prunable_ if it is constant and non-empty. This means that $L_{B}$
is of the form $L_{B}=((w\mathtt{a}_{1},x_{1}),\dots,(w\mathtt{a}_{n},x_{n}))$
with $x_{1}=\dots=x_{n}=:x$.

######  Definition 2.10.

If $L_{B}$ is prunable, then the word-number-list $\mathrm{Pr}_{w\ast}(L)$
obtained from $L$ by deleting $L_{B}$, appending the pair $(w,x)$ and
normalizing the resulting list, is said to be obtained from $L$ by _pruning_
at $B$.

It is immediate from the right-extension equivalence, that pruning transforms
$L$ into an equivalent word-number-list $\mathrm{Pr}_{w\ast}(L)$. We say that
a normalized word-number-list is _pruned_ if it does not contain admit any
prunable sub-brotherhood. Since pruning strictly reduces the number of entries
in a given word-number-list, every word-number-list can be transformed into an
equivalent _pruned_ word-number-list by a finite number of pruning moves, as
illustrated in the following example:

$-1$$0$$-6$$-1$$4$$4$$4$$1$$1$$1$$-1$$4$$-6$

In this example the pruned word-number-list is already unbalanced and hence
minimal by Theorem 2.9, i.e. we have reached a minimal equivalent word-number-
list using only pruning moves. However, in general we will also need to apply
moves related to left-extension-equivalences.

####  2.4.2 Transfer

We now consider the case where $L$ is a _pruned_ normalized balanced word-
number-list of maximal depth $\ell\geq 2$. Given a stem $u\in M_{n}$ we
consider the $n$ related brotherhoods
$\\{\mathtt{a}_{1}\mathtt{u}\ast\\},\dots,\\{\mathtt{a}_{n}\mathtt{u}\ast\\}$
of depth $\ell$. Since $L$ has maximal depth $\ell$, there exists some $u\in
M_{n}$ with $|u|=\ell-2$ such that $L_{\\{\ast
u\ast\\}}:=L_{\\{\mathtt{a}_{1}\mathtt{u}\ast\\}}\cup\dots\cup
L_{\\{\mathtt{a}_{n}\mathtt{u}\ast\\}}$ is non-empty, and we fix such an
element $u$.

We now form a $(n\times n)$-matrix $T(L,u)$ over $\mathfrak{N}$ whose entry
$t_{ij}$ at position $(i,j)$ is given by $t_{ij}:=x_{ij}$ if there is a pair
of the form $(\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j},x_{ij})$ in
$L_{\\{\mathtt{a}_{i}\mathtt{u}\ast\\}}$ and by $t_{ij}:=0$ otherwise. This
matrix is called the _transfer matrix_ for the pair $(L,u)$. Note that
$T(L,u)$ is non-zero by our choice of $u$. By definition we have

$\rho_{L_{\ast
u\ast}}=\sum_{i=1}^{n}\sum_{j=1}^{n}t_{ij}\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}.$

If we fix some $i^{\prime}\in\\{1,\dots,n\\}$, then we can use the left-
extension equivalence (2.2) to rewrite this as

$\displaystyle\rho_{L_{\ast u\ast}}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}(t_{ij}-t_{i^{\prime}j})\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}+\sum_{i=1}^{n}\sum_{j=1}^{n}t_{i^{\prime}j}\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}$
$\displaystyle=$ $\displaystyle\sum_{i\neq
i^{\prime}}\sum_{j=1}^{n}(t_{ij}-t_{i^{\prime}j})\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}+\sum_{j=1}^{n}t_{i^{\prime}j}\sum_{i=1}^{n}\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}$
$\displaystyle\sim$ $\displaystyle\sum_{i\neq
i^{\prime}}\sum_{j=1}^{n}(t_{ij}-t_{i^{\prime}j})\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}+\sum_{j=1}^{n}t_{i^{\prime}j}\rho_{\mathtt{u}\mathtt{a}_{j}}.$

######  Definition 2.11.

If $i^{\prime}\in\\{1,\dots,n\\}$, then the list
$\mathrm{Tr}_{i^{\prime},u}(L)$ which is obtained from $L$ by deleting
$L_{\ast u\ast}$, appending the pair
$(\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j},t_{ij}-t_{i^{\prime}j})$ for every
$i\in\\{1,\dots,n\\}\setminus\\{i^{\prime}\\}$ and $j\in\\{1,\dots,n\\}$,
appending the pair $(\mathtt{u}\mathtt{a}_{j},t_{i^{\prime}j})$ for every
$j\in\\{1,\dots,n\\}$ and normalizing the resulting list is said to be
obtained from $L$ by _transfer_ of the brotherhood
$L_{\\{\mathtt{a}_{i^{\prime}}u\ast\\}}$.

By the previous computation, $\mathrm{Tr}_{i^{\prime},u}(L)$ is equivalent to
$L$. The following picture shows the effect of a transfer move (applied to the
weighted brotherhood labelled $(1,2,3)$) on the associated tree:

$6$$4$$5$$4$$1$$2$$3$$4$$5$$4$$5$$4$$5$$6$$4+1$$5+2$$4+3$$4-1$$5-2$$4-3$$5-1$$4-2$$5-3$

######  Definition 2.12.

A matrix $M=(m_{ij})\in\mathfrak{N}^{n\times n}$ is called a _column-row-sum_
of a column vector $c=(c_{1},\ldots,c_{n})^{\top}\in\mathfrak{N}^{n}$ and a
row vector $r=(r_{1},\ldots,r_{n})\in(\mathfrak{N}^{n})^{*}$, denoted
$M=c\boxplus r$, if $m_{ij}=c_{i}+r_{j}$ for any $i,j\in\\{1,2,\ldots,n\\}$.

Note that if $M=r\boxplus c$ is a column-row-sum, then for any two of its
rows, say $m_{i}$ and $m_{k}$, the difference $m_{i}-m_{k}$ satisfies

$m_{i}-m_{k}=(c_{i}-c_{k},\dots,c_{i}-c_{k}),$

hence is a constant vector. Conversely, if $M$ is a matrix with rows
$m_{1},\dots,m_{k}$, such that for all $i,k\in\\{1,\dots,n\\}$ the difference
$m_{i}-m_{k}$ is a constant vector with all entries equal to a constant
$c_{ik}$, then $M$ is a column-row sum with

$M=(c_{1k},\dots,c_{nk})\boxplus m_{k}.$

######  Proposition 2.13.

If the transfer matrix $T(L,u)\in\mathfrak{N}^{n\times n}$ is not a column-
row-sum, then $L$ is minimal.

###### Proof.

If $L^{\prime}:=\mathrm{Tr}_{i^{\prime},u}(L)$, then
$L^{\prime}_{B_{i}^{\prime}(u)}$ is empty. Now there are two cases: If all of
the brotherhoods $L^{\prime}_{B_{i}(u)}$ with $i\in\\{1,\dots,n\\}$ are
constant, then for every $i\in\\{1,\dots,n\\}$ the difference
$t_{ij}-t_{i^{\prime}j}:=c_{j}$ is independent of $j$ so the matrix is a
column-row-sum. If at least one of the weighted brotherhoods
$L^{\prime}_{B_{i}(u)}$ is non-constant (and in particular non-empty), then
$L^{\prime}$ has depth $\ell$ and is unbalanced, hence minimal by Theorem 2.9.
Since $L$ and $L^{\prime}$ are equivalent and of the same depth $\ell$, we
deduce that $L$ is also minimal. ∎

####  2.4.3 Transfer and prune

We keep the previous notation; in particular, $L$ is a pruned normalized
balanced word-number-list of maximal depth $\ell\geq 2$ and $u\in M_{n}$ is
chosen such that $|u|=\ell-2$ and $L_{\\{\ast u\ast\\}}$ is non-empty.

If the transfer matrix $T(L,u)$ is non a column-row-sum, then we already known
from Proposition 2.13 that $L$ is minimal. We thus consider the case where
$T(L,u)$ is a column-row-sum and fix $i^{\prime}\in\\{1,\dots,n\\}$. We then
consider the list $L^{\prime}:=\mathrm{Tr}_{i^{\prime},u}(L)$ obtained from
$L$ by transferring the weighted brotherhood
$L_{\\{\mathtt{a}_{i^{\prime}}\mathtt{u}\ast\\}}$.

Since $T(L,u)$ is a column-row-sum, all of the weighted sub-brotherhoods
$L^{\prime}_{\\{\mathtt{a}_{i^{\prime}}\mathtt{u}\ast\\}}$ for
$i\in\\{1,\dots,n\\}\setminus\\{i^{\prime}\\}$ are constant (by the proof of
Proposition 2.13), hence we can prune them to obtain a new equivalent list,
which we denote by $\mathrm{TrP}_{i^{\prime},u}(L)$ (for “transfer and
prune”).

Our next goal is to provide an explicit formula for the coefficients in
$\mathrm{TrP}_{i^{\prime},u}(L)$. By assumption, $T(L,u)$ can be written as a
column-row sum $T(L,u)=c\boxplus r$, and we want to compute such a
decomposition explicitly. For this it will be convenient to fix some
$j^{\prime}\in\\{1,\dots,n\\}$; since $T(L,u)$ is a column-row-sum we then
have

${t}_{ij}-{t}_{i^{\prime}j}={t}_{ij^{\prime}}-{t}_{i^{\prime}j^{\prime}}\quad\text{for
all }i,j\in\\{1,\dots,n\\}.$ (2.3)

Given $i,j\in\\{1,\dots,n\\}$ we now set

$y_{i}:=t_{ij^{\prime}}-t_{i^{\prime}j^{\prime}}\quad\text{ and }\quad
z_{j}:=t_{i^{\prime}j}$ (2.4)

so that

$T(L,u)=(y_{1},\dots,y_{n})^{\top}\boxplus(z_{1},\dots,z_{n}).$

We have thus found the desired decomposition of $T(L,u)$. Note that $y_{i}$ is
independent of the choice of $j^{\prime}$ by (2.3). We then obtain

$\displaystyle\rho_{L_{\ast u\ast}}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}t_{ij}\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}(t_{ij}-t_{i^{\prime}j})\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}+\sum_{i=1}^{n}\sum_{j=1}^{n}t_{i^{\prime}j}\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}(t_{ij^{\prime}}-t_{i^{\prime}j^{\prime}})\sum_{j=0}^{n}\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}+\sum_{j=1}^{n}t_{i^{\prime}j}\sum_{i=0}^{n}\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}$
$\displaystyle\sim$
$\displaystyle\sum_{i=1}^{n}y_{i}\rho_{\mathtt{a}_{i}\mathtt{u}}+\sum_{j=1}^{n}z_{j}\rho_{\mathtt{u}\mathtt{a}_{j}},$

and one can check that this rewriting corresponds precisely to applying
transfer followed by pruning the resulting constant brotherhoods. This shows:

######  Proposition 2.14.

The list $\mathrm{TrP}_{i^{\prime},u}(L)$ is obtained from $L$ by removing
$L_{\\{\ast u\ast\\}}$, appending the elements
$(\texttt{a}_{i}\texttt{u},y_{i})$ and $(\texttt{u}\texttt{a}_{j},z_{j})$ for
$i,j\in\\{1,\dots,n\\}$ and normalizing the resulting list.∎

####  2.4.4 The case of maximal depth $\leq 1$

Using the above moves we can reduce any given word-number-list to a minimal
word-number-list or a normalized word-number-list of maximal depth $\leq 1$.
Thus assume from now on that $L$ is a normalized word-number-list of maximal
depth $\leq 1$; we are going to construct a minimal list $L^{\prime}$
equivalent to $L$.

If $L$ is empty, then $L^{\prime}:=L$ is minimal by definition. Now assume $L$
has depth $0$; we claim that $L^{\prime}:=L$ is then minimal as well. Indeed,
since $L$ is assumed normalized we have $\rho_{L}=x\rho_{\varepsilon}$ for
some $x\neq 0$. Since $\rho_{\varepsilon}(w)=|w|$ for all $w\in M_{n}$, the
function $\rho_{L}$ is unbounded, hence not equivalent to the $0$ function,
and thus $L$ is not equivalent to the empty list, which is the unique list of
depth $<0$.

Finally, consider the case that $L$ has maximal depth $1$; then

$\rho_{L}=x\rho_{\varepsilon}+\sum_{i=1}^{n}x_{i}\rho_{\mathtt{a}_{i}}.$ (2.5)

If $L$ is prunable, i..e. $x_{1}=\dots=x_{n}$, then applying a pruning move to
the unique brotherhood of depth $1$ and normalizing yields either the empty
list $L^{\prime}$ (which is minimal by definition) or a list $L^{\prime}$ of
maximal depth $1$, which is minimal as seen above. We claim that, on the other
hand, if a normalized word-number-list $L$ of maximal depth $1$ is not
prunable, then it is already minimal. Otherwise, with $\rho_{L}$ as in (2.5),
the function $\sum_{i=1}^{n}x_{i}\rho_{\mathtt{a}_{i}}$ would be equivalent to
$y\rho_{\varepsilon}$ for some coefficient $y$, and hence the function
$\sum_{i=1}^{n}(x_{i}-y)\rho_{a_{i}}$ would be bounded. Since at least one of
the coefficients $x_{i}-y$ is non-zero, this is impossible as can be seen by
evaluating at words of the form $a_{j}^{N}$ for large $N$.

###  2.5 Informal description of the algorithm

Assume now that we are given a word-number-list $L$. Then we can proceed as
follows to find a minimal word-number-list in the equivalence class of $L$:

  * •

Normalize the word-number-list $L$ and prune all constant brotherhoods in the
bottom level to obtain a pruned word-number-list $L^{\prime}$. It $L^{\prime}$
is unbalanced (or empty), then we have found our minimal word-number-list.

  * •

Assume now that $L^{\prime}$ is balanced and of maximal depth $\ell\geq 2$. We
can then find some $u\in M_{n}$ with $|u|=\ell-2$ such that
$L^{\prime}_{\\{\ast u\ast\\}}$ is non-empty. If the transfer matrix
$T(L^{\prime},u)$ is not a column-row-sum, then $L^{\prime}$ is minimal and we
are done. Otherwise we can apply a transfer and prune move. Repeat this as
often as possible; if $L^{\prime}$ is not minimal, then we ultimately obtain a
list $L^{\prime\prime}$ of smaller depth.

  * •

We can now iterate the previous step until we obtain either a minimal list
$L^{\prime\prime\prime}$ equivalent to $L$ or a list $L^{\prime\prime\prime}$
of depth $\leq 1$. In the latter case we can find an equivalent minimal list
as described in Section 2.4.4.

######  Remark 2.15.

Unfortunately, this algorithm, if implemented naively, will not be efficient
in all cases. Generally speaking, there are two things we want to avoid when
applying a transfer-and-prune move. We do not want to create too many new
entries in our list, and at the same time we do not want to transfer
brotherhoods with large coefficients. We can easily avoid one of the two
problems (by transferring the brotherhood with the minimal number of non-zero
entries, respectively by transferring the brotherhood with “smallest”
coefficients), but in general not both of them. In order to optimize the
runtime of our algorithm we will apply a _mixed strategy_ :

  1. (1)

It the word-number-list $L_{\\{\ast u\ast\\}}$ contains only few entries
(compared to the maximal possible number of $n^{2}$ entries), then we transfer
one of the weighted brotherhoods $L_{\\{\mathtt{a}_{i}u\ast\\}}$ which
contains the fewest number of entries. (This will be referred to as the sparse
case.)

  2. (2)

If the word-number-list $L_{\\{\ast u\ast\\}}$ contains many entries, then we
transfer one of the brotherhoods $L_{\\{\mathtt{a}_{i}u\ast\\}}$ whose
coefficients are as small as possible. (This will be referred to as the non-
sparse case.)

Using this strategy, we can ensure that the algorithm operates efficiently in
all cases.

##  3 Formalization of the problem

We now turn to the problem of formalizing the algorithms described in the
previous section. Throughout this article we will use the multi-tape Turing
machine model (see [12, Section 8.4.1]) as our computational model. We
emphasize the fact that our algorithms are designed to work with coefficients
that can be large, therefore we do not assume that the arithmetic operations
with them are performed in constant time.

###  3.1 Encoding the coefficients

In order to formalize our algorithm we need to discuss how our data is stored
inside a multi-tape Turing machine. In particular, we have to choose an
encoding for our coefficients. The following result is established in Appendix
A. Here the function $T$ can be chosen as $T(N):=N\log N$ or any other
function satisfying the assumptions of Convention A.3.

######  Theorem 3.1.

For $\mathfrak{N}\in\\{\mathbb{Z},\mathbb{Q}\\}$ there exist alphabets
$\Sigma_{\mathfrak{N}}$, encoding subsets
$\mathtt{Num}_{\mathfrak{N}}\subset\Sigma^{*}$ and surjective encoding maps

$\mathtt{Num}_{\mathfrak{N}}\to\mathfrak{N},\quad\mathtt{x}\mapsto\langle\mathtt{x}\rangle$

and maps
$\oplus,\ominus:\mathtt{Num}_{\mathfrak{N}}\times\mathtt{Num}_{\mathfrak{N}}\to\mathtt{Num}_{\mathfrak{N}}$
and $\|\cdot\|:\mathtt{Num}_{\mathfrak{N}}\to\mathbb{N}_{0}$ with the
following properties:

  1. (i)

$\langle\mathtt{x}_{1}\oplus\mathtt{x}_{2}\rangle=\langle\mathtt{x}_{1}\rangle+\langle\mathtt{x}_{2}\rangle$
and
$\langle\mathtt{x}_{1}\ominus\mathtt{x}_{2}\rangle=\langle\mathtt{x}_{1}\rangle-\langle\mathtt{x}_{2}\rangle$.

  2. (ii)

If $|\mathtt{x}|$ denotes the word length of
$\mathtt{x}\in\mathtt{Num}_{\mathfrak{N}}$ as a word over
$\Sigma_{\mathfrak{N}}$, then $|x|\leq\|x\|\leq 2|x|$.

  3. (iii)

$\mathtt{x}_{1}\oplus\mathtt{x}_{2}$ and $\mathtt{x}_{1}\ominus\mathtt{x}_{2}$
are of size at most $\max\\{\|\mathtt{x}_{1}\|,\|\mathtt{x}_{2}\|\\}$ and can
be computed in time $O(\max\\{\|\mathtt{x}_{1}\|,\|\mathtt{x}_{2}\|\\}+1)$ if
$\mathfrak{N}=\mathbb{Z}$ and are of size at most $\|x_{1}\|+\|x_{2}\|$ and
can be computed in time at most $O(T(\|\mathtt{x}_{1}\|+\|\mathtt{x}_{2}\|))$
if $\mathfrak{N}=\mathbb{Q}$.

  4. (iv)

Given $\mathtt{x}_{1},\mathtt{x}_{2}\in\mathtt{Num}_{\mathfrak{N}}$ it can be
decided whether $\langle\mathtt{x}_{1}\rangle=\langle\mathtt{x}_{2}\rangle$ or
not in time at most $O(\max\\{\|\mathtt{x}_{1}\|,\|\mathtt{x}_{1}\|\\})$ if
$\mathfrak{N}=\mathbb{Z}$ and at most
$O(T(\|\mathtt{x}_{1}\|+\|\mathtt{x}_{2}\|))$ if $\mathfrak{N}=\mathbb{Q}$.

In order to obtain the estimates in Theorem 3.1 in the case
$\mathfrak{N}=\mathbb{Q}$ we had to chose an encoding that is not injective
(namely an encoding by possibly non-reduced mixed fractions). We do not know
whether similar bounds can be achieved using an injective encoding. Given
$\mathtt{x}_{1},\mathtt{x}_{2}\in\mathtt{Num}_{\mathfrak{N}}$ we will write
$\mathtt{x}_{1}\equiv\mathtt{x}_{2}$ provided
$\langle\mathtt{x}_{1}\rangle=\langle\mathtt{x}_{2}\rangle$.

From now on we assume that our coefficients and their arithmetic operations
between them are encoded as in Theorem 3.1. Given
$x\in\mathtt{Num}_{\mathfrak{N}}$ we refer to $\|x\|$ as the _size_ of $x$,
since it is proportional to the amount of memory needed in order to store
$\mathtt{x}$.

###  3.2 Encoding counting functions

From now on we fix an integer $n\geq 2$. We want to encode counting functions
over the free monoid $M_{n}$ with coefficients in either $\mathbb{Z}$ or
$\mathbb{Q}$. In our informal discussion in Section 2 we have described
counting functions by word-number-lists, i.e. lists of the form
$L=((w_{1},x_{1}),\dots,(w_{N},x_{N}))$, where $w_{1},\dots,w_{N}$ are
elements of $M_{n}$ and $x_{1},\dots,x_{N}$ are elements of the coefficient
group $\mathfrak{N}\in\\{\mathbb{Z},\mathbb{Q}\\}$. In our formal discussion
we will speak of the standard data structure of a _doubly linked list_ (see
[4, Section 10.2]), which in multi-tape model can be presented as a long word
written as on a separate tape with its list elements $(w_{i},x_{i})$ separated
by commas, but we yet have to specify our encoding of the elements of $M_{n}$
and $\mathfrak{N}$ respectively. Since in most algorithms we deal with at most
$n+1$ lists, this constant can serve as an estimate for a number of tapes one
needs.

####  3.2.1 Word-coefficient pairs

To encode elements of $M_{n}$ we choose a set
$\mathtt{A}:=\\{\mathtt{a}_{1},\dots,\mathtt{a}_{n}\\}$ of cardinality $n$ and
identify $M_{n}$ with the set $\mathtt{A}^{*}$ of words over $\mathtt{A}$.
This gives an encoding of $M_{n}$ over the alphabet $\mathtt{A}$, and given
$w\in M_{n}$ we denote by $|w|$ the word length of $w$ with respect to the
alphabet $\mathtt{A}$ and call it the _size_ of $w$. In reality, the amount of
memory needed to encode $w$ is proportional to the canonical binary size
$b(w)=\log_{2}(n)\cdot|w|$. However, we will primarily be interested in the
case where the rank $n$ of our monoid is small compared to the size of the
list and/or the size of the coefficients, hence we will treat $n$ as a
constant throughout and thus consider $|w|$ to be proportional to the memory
used by $w$.

For the coefficients we use the encoding
$\mathtt{Num}_{\mathfrak{N}}\to\mathfrak{N}$ discussed in the previous section
and in more details in Appendix A. Given
$\mathtt{x}\in\mathtt{Num}_{\mathfrak{N}}$ we use the size $\|\mathtt{x}\|$ as
defined in Appendix A as a measure for the memory needed to store
$\mathtt{x}$.

By a _word-coefficient-pair_ (or simply a _pair_) we shall always mean a pair
of the form
$(w,\mathtt{x})\in\mathtt{A}^{*}\times\mathtt{Num}_{\mathfrak{N}}$. Here the
first component $w$ is interpreted as an element of the monoid
$M_{n}\cong\mathtt{A}^{*}$ and the second component $\mathtt{x}$ encodes a
coefficient $x=\langle\mathtt{x}\rangle$. Given a pair $(w,\mathtt{x})$ we
define its _total size_ as

$|(w,\mathtt{x})|_{\rm tot}:=|w|+\|\mathtt{x}\|.$

By the discussion above, this quantity is proportional to the memory needed to
store such a pair.

####  3.2.2 Encoded lists

A finite list
$\mathcal{L}=((w_{1},\mathtt{x}_{1}),\dots,(w_{N},\mathtt{x}_{N}))$ of pairs
will be referred to as an _encoded list_ , and the word-number-list

$\langle\mathcal{L}\rangle:=((w_{1},\langle\mathtt{x}_{1}\rangle),\dots,(w_{N},\langle\mathtt{x}_{N}\rangle))$

is called its _interpretation_. Note that, due to the fact that our encoding
of coefficients is not injective, different encoded lists may share the same
interpretation. We say that encoded lists are _normalized, minimal, pruned,
equivalent etc._ if their interpretations have the corresponding property.
Given an encoded list
$\mathcal{L}=((w_{1},\mathtt{x}_{1}),\dots,(w_{N},\mathtt{x}_{N}))$, we set

$|\mathcal{L}|:=\sum_{i=1}^{N}|w_{i}|,\quad\|\mathcal{L}\|:=\sum_{i=1}^{N}\|\mathtt{x}_{i}\|\quad\text{and}\quad|\mathcal{L}|_{\rm
tot}:=|\mathcal{L}|+\|\mathcal{L}\|,$

and refer to these at the _word size_ , _coefficient size_ and _total size_ of
$\mathcal{L}$ respectively. Up to a constant (depending on $n$) the total size
of $\mathcal{L}$ is the amount of memory used to store this list in our
encoding.

Given an encoded list $\mathcal{L}$, the _associated counting function_ is
defined as $\rho_{\mathcal{L}}:=\rho_{\langle\mathcal{L}\rangle}$. For
example, for $\mathfrak{N}=\mathbb{Z}$ the encoded list
$\mathcal{L}:=(\mathtt{(a_{1},+11),(a_{2}a_{1},-100),(a_{2},-101)})$
represents the counting function
$3\rho_{a_{1}}-4\rho_{a_{2}a_{1}}-5\rho_{a_{2}}$. Our choice of a doubly
linked list as the underlying data structure (rather than, e.g. a structure
similar to the weighted trees used for our visualizations above) is motivated
by the fact that we do not want to allocate redundant memory for many zero
coefficients. We will see the efficiency of this data structure in the
analysis of our main algorithm.

###  3.3 Statement of the main result

Having fixed the notion of an encoded list as our encoding for a counting
function we can now formulate the main results of the present article, at
least in the case of monoids.

######  Theorem 3.2.

For every $n\geq 2$, there exists an algorithm FindMinimalList which takes as
input an encoded list $\mathcal{L}$ over $M_{n}$ and gives as output a minimal
encoded list $\mathcal{M}$ equivalent to $\mathcal{L}$. Moreover, if $n\geq 3$
the algorithm can be implemented in such a way that its time complexity is
given as follows:

  * (a)

If $\mathfrak{N}=\mathbb{Z}$, then $\mathcal{M}$ is constructed from
$\mathcal{L}$ in linear time, i.e. in time $O(|\mathcal{L}|)$.

  * (b)

If $\mathfrak{N}=\mathbb{Q}$, then $\mathcal{M}$ is constructed from
$\mathcal{L}$ in time $O(T(|\mathcal{L}|))$, where $T(N):=N\log N$.

In view of Remark 2.5 we have the following immediate consequence:

######  Corollary 3.3.

For every $n\geq 2$ and $\mathfrak{N}\in\\{\mathbb{Z},\mathbb{Q}\\}$ there
exist algorithms to decide whether two counting functions over $M_{n}$ with
coefficients in $\mathfrak{N}$ (given as encoded lists) are equivalent.
Moreover, for $n\geq 3$ these algorithm can be implemented in such a way that
their respective time complexities are as decribed in Parts (a)–(b) of Theorem
3.2.∎

The raison d’être for the appearance of the non-linear function $T$ in Theorem
3.2(b) (and consequently Corollary 3.3) is the non-linear complexity of the
arithmetic operations over $\mathbb{Q}$, i.e. the currently best known
implementation of addition in $\mathbb{Q}$ has time complexity $T(n)$. If
addition of rational numbers could be implemented more efficiently, then this
complexity bound could be improved; see Appendix A for a more detailed
discussion. While our algorithm works for all $n\geq 2$, our runtime estimate
requires the more restrictive condition $n\geq 3$. This condition is only used
once in Lemma 4.8 to show that in the main processing step the sizes of the
coefficients under consideration is decreased by some fixed factor which is
strictly less than $1$.

###  3.4 Implementing basic moves

Three of the main subalgorithms in the informal algorithm from Subsection 2.5
are given by pruning, computation of transfer matrices and the “transfer and
prune” move. We now discuss how these algorithms can be implemented on the
level of encoded lists.

Concerning encoded lists we will use similar terminology as for word-number-
lists. In particular, if
$\mathcal{L}=((w_{1},\mathtt{x}_{1}),\dots,(w_{N},\mathtt{x_{N}}))$ is a
normalized encoded list and $w\in M_{n}$, then we define the _weighted sub-
brotherhood of $\mathcal{L}$ of type $\\{w\ast\\}$_ as the normalized encoded
list $\mathcal{L}_{\\{w\ast\\}}$ consisting of all pairs
$(w_{j},\mathtt{x}_{j})$ from $\mathcal{L}$ with $w_{j}\in\\{w\ast\\}$.
Similarly, given a word $u\in M_{n}$ we denote by $\mathcal{L}_{\\{\ast
u\ast\\}}$ the normalized encoded list given as the concatenation of the
encoded lists $\mathcal{L}_{\\{\mathtt{a}_{1}\mathtt{u}\ast\\}}$, …,
$\mathcal{L}_{\\{\mathtt{a}_{n}\mathtt{u}\ast\\}}$.

####  3.4.1 Pruning

Let $\mathcal{L}$ be a normalized encoded list with interpretation
$L=\langle\mathcal{L}\rangle$ of maximal depth $\ell\geq 1$. If $w\in M_{n}$
is of length $\ell-1$ and $L_{\\{w\ast\\}}$ is prunable we would like to find
an encoded list which represents $\mathrm{Pr}_{w\ast}(L)$. For this we remove
the sublist $\mathcal{L}_{\\{w\ast\\}}$ from $\mathcal{L}$ and append a pair
of the form $(w,\mathtt{x})$ with
$\mathtt{x}\equiv\mathtt{x}_{1}\equiv\dots\equiv\mathtt{x}_{n}$.

Note that in performing such a pruning map to $\mathcal{L}$ we have the
freedom of chosing $\mathtt{x}$. We could always choose
$\mathtt{x}:=\mathtt{x}_{1}$, but in order to get an efficient algorithm it
will be better to chose $\mathtt{x}$ to be one of the $\mathtt{x}_{j}$ of
smallest size $\|\mathtt{x}_{j}\|$.

####  3.4.2 Computation of transfer matrices

Let $\mathcal{L}$ be a normalized encoded list with interpretation
$L=\langle\mathcal{L}\rangle$ of maximal depth $\ell$ and let $u\in M_{n}$
with $|u|=\ell-2$. We will be interested in computing the transfer matrix
$T:=T(L,u)=(t_{ij})$. We say that a matrix
$\mathtt{T}=(\mathtt{t}_{ij})\in\mathtt{Num}_{\mathfrak{N}}^{n\times n}$
represents $T$ if $t_{ij}=\langle\mathtt{t}_{ij}\rangle$. In this case we also
call $\mathtt{T}$ an _encoded transfer matrix_ and write
$\mathtt{T}(\mathcal{L},u)$ for $\mathtt{T}$.

In order to compute such a transfer matrix we first compute
$\mathcal{L}_{\\{\ast u\ast\\}}$. We then read through the words in this list,
and whenever we find a word starting in $\mathtt{a}_{i}$ and ending in
$\mathtt{a}_{j}$, then we read out the corresponding coefficient
$\mathtt{x}_{ij}$ and set $\mathtt{t}_{ij}:=\mathtt{x}_{ij}$. All the other
entries of $\mathtt{T}$ are set to be $\varepsilon$. We will see that this can
be carried out in linear time in the total size of $\mathcal{L}_{\\{\ast
u\ast\\}}$.

####  3.4.3 Transfer and prune

Let $\mathcal{L}$ be a normalized encoded list with interpretation
$L=\langle\mathcal{L}\rangle$ of maximal depth $\ell\geq 2$. We assume that
there is $u\in M_{n}$ with $|u|=\ell-2$ such that the transfer matrix $T(L,u)$
is a column-row-sum. We then want to find an encoded list
$\mathcal{L}^{\prime}$ which represents the word-number-list
$\mathrm{TrP}_{i^{\prime},u}(L)$ for some $i^{\prime}\in\\{1,\dots,n\\}$.

For this we first form the encoded transfer matrix
$\mathtt{T}(\mathcal{L},u)=(\mathtt{t}_{ij})$. For every $i\in\\{1,\dots,n\\}$
we then choose $\mathtt{y}_{i}\in\mathtt{Num}_{\mathfrak{N}}$ such that
$\mathtt{y}_{i}\equiv\mathtt{t}_{ij}\ominus\mathtt{t}_{i^{\prime}j}$ for some
$j\in\\{1,\dots,n\\}$. For every $j\in\\{1,\dots,n\\}$ we then choose elements
$\mathtt{z}_{j}\in\mathtt{Num}_{\mathfrak{N}}$ such that $\mathtt{z}_{j}\equiv
t_{i^{\prime}j}$. One possible choice is
$\mathtt{z}_{j}:=\mathtt{t}_{i^{\prime}j}$ and
$\mathtt{y}_{i}:=\mathtt{t}_{ij^{\prime}}\ominus\mathtt{t}_{i^{\prime}j^{\prime}}$
for some fixed $j^{\prime}\in\\{1,\dots,n\\}$, but in general this choice may
not be efficient. In any case, we can then modify $\mathcal{L}$ by removing
$\mathcal{L}_{\\{\ast u\ast\\}}$ and appending the elements
$(\texttt{a}_{i}\texttt{u},\mathtt{y}_{i})$ and
$(\texttt{u}\texttt{a}_{j},\mathtt{z}_{j})$ for $i,j\in\\{1,\dots,n\\}$ (where
we may omit those with coefficient representing $0$). By Proposition 2.14 the
resulting list will then represent $\mathrm{TrP}_{i^{\prime},u}(L)$.

##  4 Description of the algorithm in the monoid case

We now formalize the algorithm sketched in Section 2.5. We then analyze its
complexity and establish Theorem 3.2. Our algorithm will work with encoded
lists of word-coefficient pairs. For brevity’s sake we will refer to a word-
coefficient pair simply as a _pair_ and to an encoded list simply as a _list_.
We are going to deal with the integer and the rational case simultaneously. We
set $T(N):=N$ if the coefficient group is given by $\mathfrak{N}=\mathbb{Z}$
and $T(N):=N\log N$ if the coefficient group is given by
$\mathfrak{N}=\mathbb{Q}$ so that addition, subtraction and comparison of
coefficients $\mathtt{x}_{1},\mathtt{x}_{2}\in\mathtt{Num}_{\mathfrak{N}}$ can
be carried out in $T(\|\mathtt{x}_{1}\|+\|\mathtt{x}_{2}\|)$ by Theorem 3.1,
and $T$ satisfies Properties (T1)-(T3) from Convention A.3.

######  Remark 4.1.

During out main algorithm we will of often encounter algorithms of the
following form: We are given an encoded list $\mathcal{L}$, which we split
into finitely many non-empty sublists $\mathcal{L}_{1},\dots,\mathcal{L}_{k}$
by a procedure of linear time complexity $O(|\mathcal{L}|_{\rm tot})$. We then
run the same procedure Proc over each of the lists $\mathcal{L}_{i}$.

Fortunately, we will always be in the situation where the time complexity of
the procedure is either linear or of the form $O(T(N))$, where $N$ is the size
of the input. In this specific situation it follows from Lemma A.4 that the
time complexity of the whole algorithm is also of the form
$O(|\mathcal{L}|_{\rm tot})$ (in the linear case) or of the form
$O(T(|\mathcal{L}|_{\rm tot}))$ respectively.

###  4.1 Normalizing lists and detaching brotherhoods

We start the description of our algorithm by discussing some auxiliary
procedures. We first consider a procedure to transform a given list into a
normalized one.

######  Lemma 4.2.

There exists a procedure NormalizeList with the following properties:

  1. (i)

The input of NormalizeList is a list $\mathcal{L}$ and the output is a a
normalized list $\mathcal{N}$ equivalent to $\mathcal{L}$ with
$|\mathcal{N}|_{\rm tot}\leq|\mathcal{L}|_{\rm tot}$.

  2. (ii)

The runtime of the procedure is $O(T(|\mathcal{L}|_{\rm tot}))$.

###### Proof.

Recall from [4, Section 8.3] that it is possible to sort a given list in
linear time under assumption that the size of the alphabet is constant using
the famous RadixSort sorting algorithm. (It is quite clear that this algorithm
can be realized on a multi-tape Turing machine with $n+1$ tapes, where $n$ is
the number of symbols in the alphabet of the words to be sorted.) In order to
normalize the input list $\mathcal{L}$ we apply RadixSort, using the
respective words as sorting keys. The result is a new list
$\mathcal{L}^{\prime}$ with entries being ordered in such a way that shorter
words $w_{i}$ go first, and within words of the same length, words are ordered
lexicographically. Obviously, such reordering does not change the total size
of the list. We then go through the sorted list $\mathcal{L^{\prime}}$, and if
we find several consecutive pairs with the same word $w$ and coefficients
$x_{1},\dots,x_{m}$, then we replace these entries by a pair
$(w,x_{1}\oplus\dots\oplus x_{m})$ unless $x_{1}\oplus\dots\oplus x_{m}\equiv
0$ in which case we simply eliminate them. The result is a normalized list
$\mathcal{L}$; the runtime of RadixSort is linear, hence (ii) follows from the
Totalizing Lemma A.4 applied to the estimates for addition and comparison of
numbers from Theorem 3.1.

The inequality $|\mathcal{N}|_{\rm tot}\leq|\mathcal{L}|_{\rm tot}$ follows
from the fact that in the course of the algorithm adjacent number-word pairs
of the form $(w,\mathtt{x})$ and $(w,\mathtt{y})$ are replaced by the single
pair $(w,\mathtt{x}\oplus\mathtt{y})$, and that we have

$|(w,\mathtt{x}\oplus\mathtt{y})|_{\rm
tot}=|w|+||\mathtt{x}\oplus\mathtt{y}||<2|w|+||\mathtt{x}||+||\mathtt{y}||=|(w,\mathtt{x})|_{\rm
tot}+|(w,\mathtt{y})|_{\rm tot}.\qed$

One of the advantages of normalized lists is that it is easy to find sub-
brotherhoods.

######  Lemma 4.3.

There exists a procedure DetachBrotherhood with the following properties:

  1. (i)

The input of DetachBrotherhood is a normalized list $\mathcal{N}$ and the
procedure returns the first (in lexicographic order) sub-brotherhood
$\mathcal{B}$ of $\mathcal{N}$ and deletes the sublist $\mathcal{B}$ from
$\mathcal{N}$.

  2. (ii)

The runtime of the procedure is $O(|\mathcal{B}|)$.

###### Proof.

Just move the first pair
$(\mathtt{a}_{i_{1}}\cdots\mathtt{a}_{i_{l}},\mathtt{x})$ of $\mathcal{N}$
into a separate list $\mathcal{B}$; then read the word $w^{\prime}$ of the
next pair, and move the pair into $\mathcal{B}$ if
$w^{\prime}=\mathtt{a}_{i_{1}}\cdots\mathtt{a}_{i_{l}-1}\mathtt{a}$ for some
$\mathtt{a}\in\mathtt{A}$. Continue until you find a pair whose word is not of
this form. Since we run through the list $\mathcal{N}$ until we find all
entries of a non-empty list $\mathcal{B}$ plus we view at most the first $l+1$
letter of one more word, the runtime is $O(|\mathcal{B}|)$. ∎

###  4.2 The Procedure “PruneList”

We now describe a procedure which takes a normalized list $\mathcal{N}$ of
constant depth $\ell\geq 1$ and prunes all constant brotherhoods of
$\mathcal{N}$. The result will be stored in two separate normalized lists: The
remaining pairs of depth $\ell$ will be stored in a list
$\mathcal{N}^{\prime}$ and the newly produced pairs of depth $\ell-1$ will be
stored in a list $\mathcal{L}$. The list $\mathcal{L}$ will be of much smaller
size than $\mathcal{N}$, whereas the list $\mathcal{N}^{\prime}$, which will
be later be handled using a series of transfer-and-prune moves, may be of
comparable size to $\mathcal{N}$ (and even equal to $\mathcal{N}$ if the
latter is pruned to begin with).

######  Lemma 4.4.

There exists a procedure PruneList with the following properties:

  1. (i)

The input is a normalized list $\mathcal{N}$ of constant depth $\ell\geq 1$.

  2. (ii)

The output is a normalized sublist $\mathcal{N}^{\prime}$ of $\mathcal{N}$ and
another normalized list $\mathcal{L}$, which is either empty or of constant
depth $\ell-1$.

  3. (iii)

The list $\mathcal{N}^{\prime}$ is pruned, and
$\mathcal{N}^{\prime}\cup\mathcal{L}$ is equivalent to $\mathcal{N}$.

  4. (iv)

The size of the list $\mathcal{L}$ satisfies the inequality
$|\mathcal{L}|_{\rm tot}\leq\frac{1}{n}(|\mathcal{N}|_{\rm
tot}-|\mathcal{N}^{\prime}|_{\rm tot})$

  5. (v)

The runtime of the procedure is $O(T(|\mathcal{N}|_{\rm tot}))$.

Explicitly, such a procedure can be described as follows:

Procedure PruneList

Input: A normalized list $\mathcal{N}$ of constant depth $\ell\geq 1$.

Output: A normalized list $\mathcal{N}^{\prime}$ of constant depth $\ell$ and
a normalized list $\mathcal{L}$ of constant depth $\ell-1$ such that
$\mathcal{L}$ is equivalent to the concatenation
$\mathcal{N}^{\prime}\cup\mathcal{L}$.

  1. 1.

Set $\mathcal{L}$ and $\mathcal{N}^{\prime}$ to be empty lists.

  2. 2.

While $\mathcal{N}$ is not empty do

    1. (a)

Apply the procedure DetachBrotherhood to $\mathcal{L}$,
call the resulting sub-brotherhood $\mathcal{B}$ and its coefficients
$\mathtt{x}_{1},\dots,\mathtt{x}_{k}$
and let the first word in $\mathcal{B}$ be of the form $w\mathtt{a}$ for some
$\mathtt{a}\in\mathtt{A}$.

    2. (b)

If $k\neq n$ or if $c_{1}\equiv\dots\equiv c_{n}$ does not hold,
then append $\mathcal{B}$ to $\mathcal{N}^{\prime}$,
else find the minimal $i_{0}\in\\{1,\ldots,n\\}$ such that
$||\mathtt{x}_{i_{0}}||=\min_{i=1,\ldots,n}||\mathtt{x}_{i}||$
else and append $(w,\mathtt{x}_{i_{0}})$ to the list $\mathcal{L}$.

  3. 3.

Return the lists $\mathcal{N}^{\prime}$ and $\mathcal{L}$.

###### Proof.

It is clear that (ii) and (iii) hold, since
$\mathcal{N}^{\prime}\cup\mathcal{L}$ is obtained from $\mathcal{N}$ by
pruning all prunable sub-brotherhoods of depth $\ell$. (Note that
$\mathcal{N}^{\prime}$ is normalized as a sublist of $\mathcal{N}$ and
$\mathcal{L}$ is normalized by construction.) The list $\mathcal{N}^{\prime}$
is obtained from $\mathcal{N}$ by deleting several sublists of the form

$\mathcal{C}=((w\mathtt{a}_{1},\mathtt{x}_{1}),(w\mathtt{a}_{2},\mathtt{x}_{2}),\ldots,(w\mathtt{a}_{n},\mathtt{c}_{n})),$

and each time we delete such a sublist, we add the corresponding pair
$(w,\mathtt{x}_{i_{0}})$ to $\mathcal{L}$. Since $|{w}|<|w\mathtt{a}_{i}|$ and
$\|\mathtt{x}_{i_{0}}\|<\|\mathtt{x}_{i}\|$ for all $i\in\\{1,\dots,n\\}$, we
have
$|\\{(w,\mathtt{x}_{i_{0}})\\}|_{\mathrm{tot}}<\frac{1}{n}|\mathcal{C}|_{\mathrm{tot}}$,
and thus we obtain (iv).

It remains to estimate the runtime of the procedure. To detach each
brotherhood $\mathcal{B}$ we spend time $O(|\mathcal{B}|)$ according to Lemma
4.3. The comparison of $c_{i}$ and $c_{i-1}$ in Step 2 takes
$O(T(||c_{i}||+||c_{i-1}||))$ by Theorem 3.1, and we have to apply this
$(n-1)$ times (for $i=2,\ldots,n$). Since $n$ is considered as a constant we
need time
$O(|\mathcal{B}|)+O(T(||\mathcal{B}||)=O(T(|\mathcal{B}|_{\mathrm{tot}})))$ to
deal with the brotherhood $\mathcal{B}$. It thus follows from Lemma A.4 that
the total time complexity is $O(T(|\mathcal{N}|_{\rm tot}))$. ∎

###  4.3 The procedure “TransferAndPrune”

We now turn to the main step of our algorithm, in which we want to either show
that a given pruned word-number-list $L$ is minimal or otherwise apply a
transfer-and-prune move. We will consider one family of related brotherhoods
at a time, and hence our input will be a single collection of related non-
constant weighted brotherhoods $(\mathcal{B}_{1},\dots,\mathcal{B}_{n})$. We
may assume that the concatenation
$\mathcal{B}=\mathcal{B}_{1}\cup\dots\cup\mathcal{B}_{n}$ is normalized. This
means that if ${u}$ denotes the common stem of the underlying brotherhoods,
then the elements of $\mathcal{B}_{i}$ are of the form
$(\mathtt{a}_{i}{u}\mathtt{a}_{j},\mathtt{x}_{ij})$ with
$\mathtt{x}_{ij}\not\equiv 0$. We recall that the encoded transfer matrix
$\mathtt{T}=\mathtt{T}(\mathcal{B},u)$ is given by
$\mathtt{T}=(\mathtt{t}_{ij})$, where $\mathtt{t}_{ij}:=\mathtt{x}_{ij}$ if
$\mathcal{B}_{i}$ contains a pair with word $\mathtt{a}_{i}u\mathtt{a}_{j}$
and $\mathtt{t}_{ij}:=\varepsilon$ otherwise. In particular, the total size of
its entries is given by $\|\mathtt{T}\|=\|\mathcal{B}\|$ and we refer to the
entries $\mathtt{t}_{ij}$ of $\mathtt{T}$ with
$\mathtt{t}_{ij}\neq\varepsilon$ as the _non-trivial_ entries.

######  Definition 4.5.

We say that the encoded transfer matrix $\mathtt{T}$ is _sparse_ if either
$n\geq 4$ and $\mathtt{T}$ has less than $3n$ non-trivial entries or if $n=3$
and $\mathtt{T}$ has less than $2n$ non-trivial entries.

The goal of this subsection is to describe and analyze a procedure
TransferAndPrune with the following properties:

  1. (i)

The input is an family $(\mathcal{B}_{1},\dots,\mathcal{B}_{n})$ of non-
constant related brotherhoods of depth $\ell\geq 2$ such that
$\mathcal{B}:=\mathcal{B}_{1}\cup\dots\cup\mathcal{B}_{n}$ is normalized.

  2. (ii)

The output is a Boolean variable minimal and a list $\mathcal{L}$.

  3. (iii)

If $\textsc{minimal}=\texttt{true}$, then $\mathcal{B}$ is minimal (i.e. not
equivalent to any list of depth $\leq\ell-1$) and $\mathcal{L}=\mathcal{B}$.

  4. (iv)

If $\textsc{minimal}=\texttt{false}$, then $\mathcal{L}$ is equivalent to
$\mathcal{B}$ and of constant depth $\ell-1$.

We will compute $\mathcal{L}$ from $\mathcal{B}$ by applying a single
transfer-and-prune move if possible. The precise implementation of this move
will very much depend on whether the transfer matrix is sparse or not. In the
non-sparse case, a naive implementation of the transfer-and-prune move works
fine, but in the sparse case we need to take extra care in order not to create
too many new word-coefficient pairs. Explicitly our procedure will look as
follows:

Procedure TransferAndPrune

Input: A family of non-constant weighted brotherhoods
$(\mathcal{B}_{1},\dots,\mathcal{B}_{n})$ of depth $\ell\geq 2$
Input:* such that $\mathcal{B}:=\mathcal{B}_{1}\cup\dots\cup\mathcal{B}_{n}$
is normalized.

Output: A Boolean variable minimal and a list $\mathcal{L}$.

  1. 1.

Compute the stem $u$ of $(\mathcal{B}_{1},\dots,\mathcal{B}_{n})$ and the
transfer matrix $\mathtt{T}:=\mathtt{T}(\mathcal{B},u)$.

  2. 2.

Find the first row of minimal size in the matrix $\mathtt{T}$,
i.e. find the smallest element $i_{0}$ in the set $\\{1,\dots,n\\}$ such that

$\sum_{j=1}^{n}||\mathtt{t}_{i_{0}j}||=\min_{i=1,\dots,n}\sum_{j=1}^{n}||\mathtt{t}_{ij}||.$

  3. 3.

For each $i\in\\{1,\dots,n\\}\setminus\\{i_{0}\\}$ do the following:

    1. (a)

If
$(\mathtt{t}_{i1}\ominus\mathtt{t}_{i_{0}1})\equiv(\mathtt{t}_{i2}\ominus\mathtt{t}_{i_{0}2})\equiv\dots\equiv(\mathtt{t}_{in}\ominus\mathtt{t}_{i_{0}n})$
does not hold, then
return $\textsc{Minimal}:=\texttt{true}$ and
$\mathcal{L}:=\mathcal{B}_{1}\cup\dots\cup\mathcal{B}_{n}$ and terminate the
procedure.

  4. 4.

Set $\mathcal{L}:=()$ and compute the number $K$ of non-trivial elements in
the matrix $\mathtt{T}$.
If ($n>3$ and $K<3n$) or ($n=3$ and $K<2n$) then set Sparse:=True
else set Sparse:=False.

  5. 5.

If (Sparse=False) do the following:

    1. (a)

For each $j\in\\{1,\dots,n\\}$, if $\mathtt{t}_{i_{0}j}\not\equiv 0$, append
the pair $(u\mathtt{a}_{j},\mathtt{t}_{i_{0}j})$ to $\mathcal{L}$.

    2. (b)

Find the smallest element $j_{0}$ in the set $\\{1,\dots,n\\}$ such that

$(n-2)\cdot||\mathtt{t}_{i_{0}j_{0}}||+\sum_{i=1}^{n}||\mathtt{t}_{ij_{0}}||=\min_{j=1,\dots,n}\left((n-2)\cdot||\mathtt{t}_{i_{0}j}||+\sum_{i=1}^{n}||\mathtt{t}_{ij}||\right).$

    3. (c)

For each $i\in\\{1,\dots,n\\}\setminus\\{i_{0}\\}$, if
$\mathtt{t}_{ij_{0}}\not\equiv 0$, append
$(a_{i}u,\mathtt{t}_{ij_{0}}\ominus\mathtt{t}_{i_{0}j_{0}})$ to $\mathcal{L}$.

  6. 6.

If (Sparse=True) do the following:

    1. (a)

Find the smallest element $i_{1}$ in $\\{1,\dots,n\\}$ with the property that
the row $(\mathtt{t}_{i_{1}1},\dots,\mathtt{t}_{i_{1}n})$ of $\mathtt{T}$ has
the minimal number of non-trivial entries and set111The letters $Z$ and $S$
stand for “zero set” and “support” respectively.

$Z:=\\{j\in\\{1,\dots,n\\}\mid\mathtt{t}_{i_{1}j}=\varepsilon\\}\quad\text{and}\quad
S:=\\{1,\dots,n\\}\setminus Z.$

    2. (b)

For each $i\in\\{1,\dots,n\\}\setminus\\{i_{1}\\}$ do the following:

      1. (i)

Find the smallest element $j_{1}$ in $Z$ such that

$|\mathtt{t}_{ij_{1}}|=\min\\{||\mathtt{t}_{ij}||\,\mid j\in Z\\}.$

      2. (ii)

If $\mathtt{t}_{ij_{1}}\neq\varepsilon$, append $(a_{i}u,\mathtt{t}_{ij_{1}})$
to $\mathcal{L}$.

    3. (c)

If $i_{0}=i_{1}$, then for each $j\in S$, if
$\mathtt{t}_{i_{1}j}\neq\varepsilon$, append
$(ua_{i_{1}},\mathtt{t}_{i_{1}j})$ to $\mathcal{L}$.

    4. (d)

If $i_{0}\neq i_{1}$ do the following:

      1. (i)

Find the smallest element $j_{0}$ in $Z$ such that

$||\mathtt{t}_{i_{0}j_{0}}||=\min\\{||\mathtt{t}_{i_{0}j}||\,\mid j\ \in
Z\\}.$

      2. (ii)

For each $j\in S$, if $\mathtt{t}_{i_{0}j}\not\equiv\mathtt{t}_{i_{0}j_{0}}$
append $(ua_{j},\mathtt{t}_{i_{0}j}\ominus\mathtt{t}_{i_{0}j_{0}})$ to
$\mathcal{L}$.

  7. 7.

Return $\textsc{Minimal}=\texttt{false}$ and $\mathcal{L}$.

Let us first check correctness of the procedure:

######  Proposition 4.6.

The procedure TransferAndPrune satisfies Properties (i) - (iv).

###### Proof.

If the procedure stops during the execution of Step 3, then the encoded
transfer matrix is not a column-row-sum and hence $\mathcal{B}$ is minimal by
Proposition 2.13, hence the output is correct. Assume now that the transfer
matrix is a column-row-sum; we then want to perform a transfer-and-prune move.
For this we have to choose some $i^{\prime}\in\\{1,\dots,n\\}$ and then choose
elements $\mathtt{y}_{i},\mathtt{z}_{j}\in\mathtt{Num}_{\mathfrak{N}}$ with

$\mathtt{z}_{j}\equiv t_{i^{\prime}j}\quad\text{ and
}\quad\mathtt{y}_{i}\equiv\mathtt{t}_{ij^{\prime}}-\mathtt{t}_{i^{\prime}j^{\prime}}\quad\text{for
some }j^{\prime}\in\\{1,\dots,n\\}.$ (4.1)

The list $\mathcal{L}$ should then consist of those pairs
$(\texttt{a}_{i}\texttt{u},\mathtt{y}_{i})$ and
$(\texttt{u}\texttt{a}_{j},\mathtt{z}_{j})$ with $\mathtt{y}_{i}\not\equiv
0\not\equiv\mathtt{z}_{j}$. We distinguish two cases:

Case 1. If the matrix $\mathtt{T}$ is non-sparse, then in Step 5 we perform
transfer with $i^{\prime}:=i_{0}$. The coefficients in our list $\mathcal{L}$
are then given by $\mathtt{z}_{j}:=\mathtt{t}_{i_{0}j}$ and
$y_{i}:=\mathtt{t}_{ij_{0}}-\mathtt{t}_{i_{0}j_{0}}$, where $j_{0}$ is chosen
in Step 5(b). (The reason for this specific choice will become clear in Lemma
4.8.) Then (4.1) holds by definition, hence the algorithm performs correctly.

Case 2. If $\mathtt{T}$ is sparse, then in Step 6 we perform transfer with
$i^{\prime}:=i_{1}$. For every $i$ we choose
$\mathtt{y}_{i}:=\mathtt{t}_{ij_{1}}$, where $j_{1}$ is chosen in Step
6(b)(i). Since $j_{1}\in Z$ we have $\mathtt{t}_{i_{1}j_{1}}\equiv 0$ and
hence
$\mathtt{y}_{i}=\mathtt{t}_{ij_{1}}\equiv\mathtt{t}_{ij_{1}}-\mathtt{t}_{i_{1}j_{1}}$
satisfies (4.1).

For reasons of efficiency, the coefficients $\mathtt{z}_{j}$ will be chosen
differently depending on whether $i_{0}=i_{1}$ or not. If $i_{0}=i_{1}$, then
we choose $\mathtt{z}_{j}:=\mathtt{t}_{i_{1}j}$, which is obviously correct.
If $i_{0}\neq i_{1}$ then we choose
$\mathtt{z}_{j}:=\mathtt{t}_{i_{0}j}\ominus\mathtt{t}_{i_{0}j_{0}}$, where
$j_{0}$ is chosen as in Step 6(d)(i). Since $j_{0}\in Z$ we have
$\mathtt{t}_{i_{1}j_{0}}\equiv 0$, and since $\mathtt{T}$ is a row-colum-sum
we have

$\mathtt{t}_{i_{1}j_{0}}\ominus\mathtt{t}_{i_{0}j_{0}}\equiv\mathtt{t}_{i_{1}j}\ominus\mathtt{t}_{i_{0}j}\implies\mathtt{z}_{j}=\mathtt{t}_{i_{0}j}\ominus\mathtt{t}_{i_{0}j_{0}}\equiv\mathtt{t}_{i_{1}j}\ominus\mathtt{t}_{i_{1}j_{0}}\equiv\mathtt{t}_{i_{1}j}$

hence (4.1) is satisfied also in this case and the algorithm is correct. ∎

Concerning the run-time of the procedure TransferAndPrune we observe:

######  Proposition 4.7.

The procedure TransferAndPrune terminates in time $O(T(|\mathcal{B}|_{\rm
tot}))$.

###### Proof.

We recall that the rank $n$ is considered as a constant throughout our
estimates, hence all implied constants will be allowed to depend on $n$.

Step 1 can be perforemd in linear time $O(|\mathcal{B}|_{\rm tot})$. The stem
can be computed from any pair $(w,\mathtt{x})$ in time $O(|w|)\leq
O(|\mathcal{B}|_{\rm tot})$. The transfer matrix can also be computed in time
$O(|\mathcal{B}|_{\rm tot})$ by running through the pairs and copying the
required data.

Step 2 can be done by a subsequent summation of the length of the coefficients
from $\mathcal{B}_{i}$ and the update of the minimum, so it takes time at most
$O(||\mathcal{B}_{i}||)$ for each row, hence at most $O(||\mathcal{B}||)$
altogether. (Note that we are adding integers, not rational numbers, here,
even in the case $\mathfrak{N}=\mathbb{Q}$.)

In Step 3 we need time at most
$O(T(||\mathtt{t}_{ij}||+||\mathtt{t}_{i_{0}j}||+||\mathtt{t}_{i{j-1}}||+||\mathtt{t}_{i_{0}{j-1}}||))$
to decide whether
$\mathtt{t}_{ij}\ominus\mathtt{t}_{i_{0}j}\equiv\mathtt{t}_{i{j-1}}\ominus\mathtt{t}_{i_{0}{j-1}}$
by Theorem 3.1. Then all of the comparisons in the $i$th iteration of Step 3
take time at most $O(T(2(||\mathcal{B}_{i}||+||\mathcal{B}_{i_{0}}||)))$. By
our choice of $i_{0}$ and Property (T3) of the function $T$ (cf. Convention
A.3) we have
$O(T(2(||\mathcal{B}_{i}||+||\mathcal{B}_{i_{0}}||)))=O(T(||\mathcal{B}_{i}||)$,
and hence by Lemma A.4 Step 3 takes time at most $O(T(|\mathcal{B}|_{\rm
tot}))$. Step 4 can be carried out in time $O(1)$.

In the non-sparse case we execute Step 5. Here Part (a) takes time at most
$|\mathcal{B}_{i_{0}}|_{\rm tot}$, Part (b) takes time at most
$O(||\mathcal{B}||)$ similarly to Step 2, and Part (c) takes time at most
$O(T(|\mathcal{B}|_{\rm tot}))$ since each operation of subtraction
$x_{ij_{0}}\ominus x_{i_{0}j_{0}}$ takes time at most
$O(T(||\mathcal{B}_{i}||+||\mathcal{B}_{i_{0}}||)$. We can thus apply the
Totalling Lemma A.4 as in Step 3 to get the estimate of
$O(T(||\mathcal{B}||))$ for the coefficients processing and $O(|\mathcal{B}|)$
for the words processing, obtaining at most $O(T(|\mathcal{B}|_{\rm tot}))$ in
total. In the sparse case we execute Step 6, whose time complexity can be
analyzed similarly to Step 5. Step 7 has again time complexity $O(1)$. Thus
every step of the algorithm takes time at most $O(T(|\mathcal{B}|_{\rm
tot}))$, hence this bound also serves as a time estimate for the whole
procedure. ∎

The crucial point about the procedure TransferAndPrune is that it reduces the
size of the output by a fixed constant $<1$, unless the input was already
minimal:

######  Lemma 4.8.

Assume that TransferAndPrune returns $\textsc{minimal}=\texttt{false}$ when
applied to $(\mathcal{B}_{1},\dots,\mathcal{B}_{n})$. If $n\geq 3$, then the
sizes of the output list $\mathcal{L}$ and the input list
$\mathcal{B}:=\mathcal{B}_{1}\cup\dots\cup\mathcal{B}_{n}$ are related by the
inequality

$|\mathcal{L}|_{\rm tot}\quad\leq\quad\frac{8}{9}\cdot|\mathcal{B}|_{\rm
tot}.$

###### Proof.

Since $|\mathcal{L}|_{\rm tot}=|\mathcal{L}|+||\mathcal{L}||$ and
$|\mathcal{B}|_{\rm tot}=|\mathcal{B}|_{\texttt{A}}+||\mathcal{B}||$ it will
suffice to estimate the word lengths and coefficient size separately, i.e. to
show that

$|\mathcal{L}|\leq\frac{8}{9}\cdot|\mathcal{B}|\quad\text{and}\quad||\mathcal{L}||\leq\frac{8}{9}\cdot||\mathcal{B}||.$

For this we will use the fact that if $m_{1},\dots,m_{n}$ are rational numbers
and $m_{i_{0}}$ is minimal among those, then

$m_{i_{0}}\leq\frac{1}{n}\sum_{i=1}^{n}m_{i}$ (4.2)

Let $\mathtt{T}$ be the coeffcient matrix constructed in Step 1. We will
distinguish two cases:

Case 1: The matrix $\mathtt{T}$ is non-sparse.

Assume first that $n\geq 4$. so that in our input we had at least $3n$ words
if lenght $\ell$ and hence $|\mathcal{B}|\geq 3n\ell$. The maximal number of
words in our output is $n+(n-1)=2n-1$ (since in Step 5(a) we create at most
$n$ words and in Step 5(c) we create at most $(n-1)$ words), and each of them
has length $\ell-1$, hence

$|\mathcal{L}|\leq(2n-1)(\ell-1)<(2n-1)\cdot\ell\leq\frac{2n-1}{3n}|\mathcal{B}|\leq\frac{2}{3}|\mathcal{B}|\leq\frac{8}{9}{|\mathcal{B}|}.$

For $n=3$ the same bound follows by a similar argument from

${|\mathcal{L}|}\leq\frac{(2n-1)(\ell-1)}{2n\ell}|\mathcal{B}|\leq\frac{2n-1}{2n}|\mathcal{B}|=\frac{5}{6}|\mathcal{B}|\leq\frac{8}{9}{|\mathcal{B}|}.$

On the other hand, $||\mathcal{B}||$ is precisely the total size of the
entries in the matrix $\mathtt{T}$, i.e.

$||\mathcal{B}||=\sum_{i=1}^{n}\sum_{j=1}^{n}||\mathtt{t}_{ij}||,$ (4.3)

whereas in view of Step 5(a) and Step 5(c) the coefficient size of the output
is

$||\mathcal{L}||=\sum_{j=1}^{n}||\mathtt{t}_{i_{0}j}||+\sum_{i\neq
i_{0}}||\mathtt{t}_{ij_{0}}\ominus\mathtt{t}_{i_{0}j_{0}}||.$

In view of our choice of $i_{0}$ in Step 2 we can apply (4.2) to estimate

$\sum_{j=1}^{n}||\mathtt{t}_{i_{0}j}||\leq\frac{1}{n}\cdot\sum_{i=1}^{n}\left(\sum_{j=1}^{n}||\mathtt{t}_{ij}||\right)=\frac{||\mathcal{B}||}{n}.$
(4.4)

Similarly, in view of our choice of $j_{0}$ in Step 5(b) we have the estimate

$(n-2)\cdot||\mathtt{t}_{i_{0}j_{0}}||+\sum_{i=1}^{n}||\mathtt{t}_{ij_{0}}||\leq\frac{1}{n}\cdot\sum_{j=1}^{n}\left((n-2)\cdot||\mathtt{t}_{i_{0}j}||+\sum_{i=1}^{n}||\mathtt{t}_{ij}||\right).$

Combining these two estimates and using Lemma A.4 we obtain

$\displaystyle||\mathcal{L}||$ $\displaystyle\leq$
$\displaystyle\frac{||\mathcal{B}||}{n}+\sum_{i\neq
i_{0}}\left(||\mathtt{t}_{ij_{0}}||+||\mathtt{t}_{i_{0}j_{0}}||\right)\quad=\quad\frac{||\mathcal{B}||}{n}+(n-2)\cdot||\mathtt{t}_{i_{0}j_{0}}||+\sum_{i=1}^{n}||\mathtt{t}_{ij_{0}}||$
$\displaystyle\leq$
$\displaystyle\frac{||\mathcal{B}||}{n}+\frac{1}{n}\cdot\sum_{j=1}^{n}\left((n-2)\cdot||\mathtt{t}_{i_{0}j}||+\sum_{i=1}^{n}||\mathtt{t}_{ij}||\right)$
$\displaystyle=$
$\displaystyle\frac{||\mathcal{B}||}{n}+\frac{n-2}{n}\sum_{j=1}^{n}||\mathtt{t}_{i_{0}j}||+\frac{1}{n}\cdot\sum_{i=1}^{n}\sum_{j=1}^{n}||\mathtt{t}_{ij}||$
$\displaystyle\leq$
$\displaystyle\frac{||\mathcal{B}||}{n}+\frac{n-2}{n}\cdot\frac{||\mathcal{B}||}{n}+\frac{1}{n}\cdot||\mathcal{B}||\quad=\quad\frac{3n-2}{n^{2}}\cdot||\mathcal{B}||,$

hence for $n\geq 3$ we obtain

$||\mathcal{L}||\leq\frac{7}{9}\cdot||\mathcal{B}||\leq\frac{8}{9}\cdot||\mathcal{B}||,$

which finishes Case 1.

Case 2: The matrix $\mathtt{T}$ is sparse.

Let $\lambda$ be the minimal number of non-zero entries in a row of
$\mathtt{T}$, i.e. the size of the set $S$ constructed in Step 6(a). Since the
weighted brotherhoods $\mathcal{B}_{1},\dots\mathcal{B}_{n}$ are non-constant
we have $\lambda\geq 1$, and since $\mathtt{T}$ is sparse we have either
$\lambda\leq 2$ and $n\geq 4$ or $\lambda\leq 1$ and $n=3$. In either case we
have $|Z|\geq 2$ and $\lambda\in\\{1,2\\}$. If $\lambda=1$, then $S$ is
actually a singleton, say $S=\\{j_{s}\\}$. In this case we define

$A:=\\{i\in\\{1,\dots,n\\}\setminus\\{i_{1}\\}\mid\mathtt{t}_{ij_{s}}\equiv\mathtt{t}_{i_{1}j_{s}}\\}\quad\text{and}\quad
A^{c}:=\\{i\in\\{1,\dots,n\\}\setminus\\{i_{1}\\}\mid\mathtt{t}_{ij_{s}}\not\equiv\mathtt{t}_{i_{1}j_{s}}\\}.$

We then set $|A|:=r$ so that $|A^{c}|=n-r-1$.

Assume first $\lambda=2$. Then $\mathcal{B}$ contains at least $2n$ words and
hence $|\mathcal{B}|\geq 2\ell$. In Step 6(b)(ii) we create at most $(n-1)$
words of length $(\ell-1)$ and in Step 6(c) or (d) we create at most $|S|=2$
words. Thus for $\lambda=2$ and $n\geq 3$ we obtain

$|\mathcal{L}|\leq(n+1)(\ell-1)<(n+1)\ell\leq\frac{n+1}{2n}|\mathcal{B}|\leq\frac{4}{6}|\mathcal{B}|\leq\frac{8}{9}|\mathcal{B}|.$

Now consider the case $\lambda=1$. Since the matrix $\mathtt{T}$ is a column-
row-sum, the $i$-th row of $X$ becomes constant after subtracting
$\mathtt{t}_{i_{1}j_{s}}$ from $\mathtt{t}_{ij_{s}}$. Thus if $i\in A$, then
$\mathcal{B}_{i}$ has a single entry, whereas if $i\in A^{c}$, then
$\mathcal{B}_{i}$ has at least $(n-1)$-entries. We thus obtain

$|\mathcal{B}|\geq(1+|A|+|A^{c}|\cdot(n-1))\cdot\ell\geq(1+r+2(n-r-1))\cdot\ell\geq(2n-r-1)\ell.$

In Step 6(b)(ii) we create $(n-r-1)$ words and in Step 6(c) or 6(d) we create
at most $1$ word, all of length $\leq\ell-1$, hence

$|\mathcal{L}|\leq((n-r-1)+1)\cdot(\ell-1)\leq(n-r)\cdot\ell\leq\frac{n-r}{2n-r-1}\cdot|\mathcal{B}|.$

If $r=0$, then ${(n-r)}/{(2n-r-1)}=n/(2n-1)\leq 3/5$, and if $r\geq 1$, then
$2n-r-1\leq 2(n-r)$, hence ${(n-r)}/{(2n-r-1)}\leq 1/2$, thus in any case

$|\mathcal{L}|\leq\frac{8}{9}\cdot|\mathcal{B}|.$

We now turn to the coefficient sizes. Consider first the coefficients created
in Step 6(b)(ii). For each $i\in\\{1,2,\ldots,n\\}\setminus\\{i_{1}\\}$ two
cases are possible. Either no pair is created (if the $i$-th and $i_{1}$-th
rows encode equal vectors) or a there are at least two non-trivial entries
$\mathtt{t}_{ij_{2}}$ and $\mathtt{t}_{ij_{3}}$ in the $i$-the row with
$\\{j_{2},j_{3}\\}\subset Z$ (since $|Z|\geq 2$), and the smallest of these
coefficients is copied to $\mathcal{N}$. Either way the coefficients created
in the $i$th iteration of Step 6(b)(ii) are of total size at most
$||\mathcal{B}_{i}||/2$ and consequently the total size of all coefficients
created in Step 6(b)(ii) are of size at most $||\mathcal{B}||/2$.

We now consider the coefficients created in Parts (c) and (d) of Step 6. If
$i_{0}\neq i_{1}$, then their total size is given by

$\displaystyle\sum_{j\in
S}||\mathtt{t}_{i_{0}j}\ominus\mathtt{t}_{i_{0}j_{0}}||$ $\displaystyle\leq$
$\displaystyle\sum_{j\in
S}\left(||\mathtt{t}_{i_{0}j}||+||\mathtt{t}_{i_{0}j_{0}}||\right)\quad\leq\quad|S|||\mathtt{t}_{i_{0}j_{0}}||+\sum_{j\in
S}||\mathtt{t}_{i_{0}j}||$ $\displaystyle=$
$\displaystyle|S|\min_{j\in\\{1,\dots,n\\}}||\mathtt{t}_{i_{0}j}||+\sum_{j\in
S}||\mathtt{t}_{i_{0}j}||\quad\leq\quad|Z|\min_{j\in\\{1,\dots,n\\}}||\mathtt{t}_{i_{0}j}||+\sum_{j\in
S}||\mathtt{t}_{i_{0}j}||$ $\displaystyle\leq$ $\displaystyle\sum_{j\in
Z}||\mathtt{t}_{i_{0}j}||+\sum_{j\in
S}||\mathtt{t}_{i_{0}j}||\quad\leq\quad\sum_{j=1}^{n}||\mathtt{t}_{i_{0}j}||\quad\leq\quad\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}||\mathtt{t}_{ij}||$
$\displaystyle=$ $\displaystyle\frac{1}{n}\cdot||\mathcal{B}||,$

where in the second line we have used that $|S|\leq 2\leq|Z|$ and in the third
line we have used (4.2). If $i_{0}=i_{1}$ then the choice for $i_{0}$ we made
in the Step 2 and the estimation (4.4) immediately shows that the coefficients
created in Step 6(c) are bounded by $\frac{1}{n}\cdot||\mathcal{B}||$. Either
way, we see that for all $n\geq 3$,

$||\mathcal{L}||\leq\frac{||\mathcal{B}||}{2}+\frac{||\mathcal{B}||}{n}=\frac{n+2}{2n}\cdot||\mathcal{B}||\leq\frac{5}{6}\cdot||\mathcal{B}||\leq\frac{8}{9}\cdot||\mathcal{B}||.$

This finishes Case 2. ∎

###  4.4 The main processing step

In this section we describe the algorithm MainProcessingStep and then prove
the Lemma 4.9 which is used afterwards to prove our main Theorem 3.2.

######  Lemma 4.9.

For every $n\geq 2$, there exists an algorithm MainProcessingStep with the
following properties:

  1. (i)

The input is a normalized list $\mathcal{L}$ of constant depth $\ell\geq 2$.

  2. (ii)

The output is a boolean parameter minimal and a normalized list
$\mathcal{L}^{\prime}$ equivalent to $\mathcal{L}$.

  3. (iii)

It $\textsc{minimal}=\mathtt{true}$, then $\mathcal{L}^{\prime}$ is minimal.

  4. (iv)

If $\textsc{minimal}=\mathtt{false}$, then $\mathcal{L}^{\prime}$ is of
constants depth $\ell-1$. If $n\geq 3$, then

$|\mathcal{L}^{\prime}|_{\mathrm{tot}}\leq\frac{8}{9}|\mathcal{L}|_{\rm tot}.$
(4.5)

  5. (v)

The runtime of the algorithm is $O(T(|\mathcal{L}|))$.

Explicitly we can describe such an algorithm as follows:

Procedure MainProcessingStep

Input A normalized list $\mathcal{N}$ of constant depth $\ell\geq 2$.

Output: A Boolean variable minimal and a normalized list of pairs
$\mathcal{L}$.

  1. 1.

Set $\textsc{minimal}:=\texttt{false}$.

  2. 2.

Apply the procedure PruneList to $\mathcal{N}$ to create a sublist
$\mathcal{N}^{\prime}$ of $\mathcal{N}$ and a list $\mathcal{L}$ of pairs of
depth $\ell-1$.

  3. 3.

Decompose the list $\mathcal{N}$ into lists
$\mathcal{A}_{1},\dots,\mathcal{A}_{n}$ by moving all the pairs $(w,x)$ in
$\mathcal{N}$ such that $w$ starts with $a_{i}$ into $\mathcal{A}_{i}$.

  4. 4.

While minimal = false and the lists $\mathcal{A}_{1}$, …, $\mathcal{A}_{n}$
are not all empty, do the following.

    1. (a)

For $i=1,\dots,n$, apply the procedure DetachBrotherhood to $\mathcal{A}_{i}$,
call the resulting brotherhood $\mathcal{B}_{i}$.

    2. (b)

If the brotherhoods $\mathcal{B}_{1},\dots,\mathcal{B}_{n}$ are not related,
set $\textsc{minimal}:=\texttt{true}$, else apply the procedure
TransferAndPrune to $(\mathcal{B}_{1},\dots,\mathcal{B}_{n})$. Set its Boolean
output as the new value of minimal and append the resulting list to
$\mathcal{L}$.

  5. 5.

Append $\mathcal{A}_{1},\dots,\mathcal{A}_{n}$ to $\mathcal{L}$ and return
$\textsc{NormalizeList}(\mathcal{L})$.

###### Proof of Lemma 4.9.

Correctness of the procedure follows from the facts that the procedure
PruneList correctly prunes all constant brotherhoods of maximal depth in
$\mathcal{N}$ and that the procedure TransferAndPrune correctly applies a
transfer-and-prune move if possible and otherwise sets the boolean variable
minimal to true.

By Lemma 4.4, Step 2 takes time $O(T(|\mathcal{N}|_{\rm tot}))$ to turn the
initial list $\mathcal{N}$ turns into an equivalent list
$\mathcal{L}\cup\mathcal{N}^{\prime}$ such that

$0\leq|\mathcal{L}|_{\rm tot}\leq\frac{1}{n}(|\mathcal{N}|_{\rm
tot}-|\mathcal{N}^{\prime}|_{\rm tot})$

In Step 3 the list $\mathcal{N}^{\prime}$ is split into the lists
$\mathcal{A}_{1},\mathcal{A}_{2},\ldots,\mathcal{A}_{n}$ whose union is equal
to $\mathcal{N}^{\prime}$, and this takes time at most
$O(|\mathcal{N}^{\prime}|_{\rm tot})$.

Now we consider the iterations of Step 4. After each iteration the length of
the list $\mathcal{A}_{1}\cup\mathcal{A}_{2}\cup\ldots\cup\mathcal{A}_{n}$
gets decreased by some integer value $|\mathcal{B}|_{\rm tot}$, where
$\mathcal{B}$ is a union $\mathcal{B}_{1}\cup\ldots\cup B_{k}$, that was
produced in the part (a). Each such step takes time $|\mathcal{B}|_{\rm tot}$
due to Lemma 4.3 and its output has size at most
$\frac{8}{9}|\mathcal{B}|_{\rm tot}$ if $\textsc{minimal}=\texttt{False}$
after its execution. Using Lemma A.4 we see that the time complexity of step
$4$ is at most

$O(T(|\mathcal{A}_{1}\cup\dots\cup\mathcal{A}_{n}|_{\mathrm{tot}}))\leq
O(T(|\mathcal{N}^{\prime}|_{\mathrm{tot}}))\leq
O(T(|\mathcal{N}|_{\mathrm{tot}})).$

If $n\geq 3$ and $\textsc{minimal}=\texttt{False}$ at the end of Step $4$,
then the original list $\mathcal{L}$ is increased into a list
$\mathcal{L}^{\prime}$ of total size at most

$|\mathcal{L}^{\prime}|_{\mathrm{tot}}\leq|\mathcal{L}|_{\mathrm{tot}}+\frac{8}{9}|\mathcal{N}^{\prime}|_{\mathrm{tot}}\leq\frac{1}{n}(|\mathcal{N}|_{\mathrm{tot}}-|\mathcal{N}^{\prime}|_{\mathrm{tot}})+\frac{8}{9}|\mathcal{N}^{\prime}|_{\mathrm{tot}}\leq\max\left\\{\frac{1}{n},\frac{8}{9}\right\\}|\mathcal{N}^{\prime}|_{\mathrm{tot}}\leq\frac{8}{9}|\mathcal{N}|_{\mathrm{tot}}.$

In any case, the list $\mathcal{L}^{\prime}$ obtained by appending
$\mathcal{A}_{1},\dots,\mathcal{A}_{n}$ to the list obtained after Step $4$
always satisfies
$|\mathcal{L}^{\prime}|_{\mathrm{tot}}\leq|\mathcal{N}|_{\mathrm{t}ot}$ (even
if $n=2$ and/or $\textsc{minimal}=\texttt{true}$), and hence the final step
can also be carried out in time at most $O(T(|\mathcal{N}|_{\mathrm{tot}}))$
and does not increase the size of the output. In the case, where $n=3$ and
$\textsc{minimal}=\texttt{false}$ the size of the output is thus smaller than
the input by a factor of at least $\frac{8}{9}$. ∎

###  4.5 The final algorithm

Using all of the procedures described above we are now finally ready to
describe an algorithm FindMinimalList which, given an arbitrary encoded list,
finds an equivalent minimal list. This algorithm will then be used to prove
Theorem 3.2.

Algorithm FindMinimalList

Input An encoded list $\mathcal{L}$.

Output: A normalized encoded list $\mathcal{M}$ which is equivalent to
$\mathcal{L}$.

  1. 1.

Set $\mathcal{N}:=\textsc{NormalizeList}(\mathcal{L})$.

  2. 2.

If $\mathcal{N}$ is empty, return $\mathcal{M}:=\mathcal{N}$, otherwise set
$\textsc{Minimal}:=\texttt{false}$.

  3. 3.

Set $d$ to be the maximal depth of $\mathcal{N}$.

  4. 4.

Decompose the list $\mathcal{N}$ into lists
$\mathcal{N}_{d},\dots,\mathcal{N}_{1},\mathcal{N}_{0}$ by moving all pairs
$(w,\mathtt{x})$ in $\mathcal{N}$ with $|w|=i$ into $\mathcal{N}_{i}$.

  5. 5.

Set $\mathcal{M}_{d}:=\mathcal{N}_{d}$.

  6. 6.

For $i:=d$ downto 2 do

    1. (a)

If $\mathcal{M}_{i}$ is empty, then set $\mathcal{N}^{\prime}$ to be the empty
list,
else apply MainProcessingStep to $\mathcal{M}_{i}$,
and put the resulting list into $\mathcal{N}^{\prime}$ and the boolean value
into Minimal.

    2. (b)

If $\textsc{Minimal}=\texttt{false}$ then
$\mathcal{M}_{i-1}:=\textsc{NormalizeList}(\mathcal{N}^{\prime}\cup\mathcal{N}_{i-1})$
else break.

  7. 7.

If minimal = true return
$\mathcal{M}:=\mathcal{M}_{i}\cup\mathcal{N}_{i-1}\cup\ldots\cup\mathcal{N}_{0}$
else do the following.

    1. (a)

Apply PruneList to $\mathcal{M}_{1}$ to get a list $\mathcal{N}^{\prime}$ of
constant depth $1$ and a list $\mathcal{K}$ of constant depth $0$.

    2. (b)

If $\mathcal{N}^{\prime}$ is empty then return
$\mathcal{M}:=\textsc{NormalizeList}(\mathcal{K}\cup\mathcal{N}_{0})$
else return $\mathcal{M}:=\mathcal{M}_{1}\cup\mathcal{N}_{0}$.

###### Proof of Theorem 3.2.

Basically we just have to combine all of the previous lemmas.

First, we show that the algorithm FindMinimalList gives a correct result. If
$\mathcal{N}_{0},\dots,\mathcal{N}_{d}$ denotes the lists created in Step 4,
then the list
$\mathcal{N}_{d}\cup\mathcal{N}_{d-1}\cup\ldots\cup\mathcal{N}_{1}\cup\mathcal{N}_{0}=\mathcal{N}$
us equivalent to $\mathcal{L}$. Now during Step 6 one of two cases occurs:
Either the iteration never breaks and we obtains lists
$\mathcal{M}_{d},\dots,\mathcal{M}_{1}$ (in which case we set $t:=1$) or the
algorithm produces lists $\mathcal{M}_{d},\dots,\mathcal{M}_{t}$ for some
$t\geq 2$ and breaks in the following iteration. In either case, one shows by
a descending induction on $i$ that for all $i\in\\{d,d-1,\dots,t\\}$ the list
$\mathcal{M}_{i}$ is a list of constant depth $\ell=i$ and equivalent to the
union $\mathcal{N}_{d}\cup\ldots\cup\mathcal{N}_{i}$. Indeed, for $i:=d$ there
is nothing to show, and if the claim holds for $i$ and the algorithm does not
break in the following step, then correctness of the MainProcessingStep
ensures that $\mathcal{M}_{i-1}$ is of constant depth $i-1$ and satisfies

$\mathcal{M}_{i-1}\sim\mathcal{N}^{\prime}\cup\mathcal{N}_{i-1}\sim\mathcal{N}_{d}\cup\dots\cup\mathcal{N}_{i}\cup\mathcal{N}_{i-1},$

which finishes the induction. Now, in Step 7 two cases are possible.

_Case I._ If the execution of Step 6 a break occurs after computing
$\mathcal{M}_{d},\dots,\mathcal{M}_{t}$ for some $t\geq 2$, then correctness
of the MainProcessingStep ensures that $\mathcal{M}_{t}$ is minimal and in
fact unbalanced. This implies that also
$\mathcal{M}:=\mathcal{M}_{t}\cup\mathcal{N}_{t-1}\cup\ldots\cup\mathcal{N}_{0}$
is unbalanced, hence minimal. Moreover, by the previous induction we have

$\mathcal{M}\sim\mathcal{M}_{t}\cup\mathcal{N}_{t-1}\cup\ldots\cup\mathcal{N}_{0}\sim\mathcal{N}_{d}\cup\dots\cup\mathcal{N}_{t}\cup\mathcal{N}_{t-1}\cup\ldots\cup\mathcal{N}_{0}\sim\mathcal{L}$

Thus $\mathcal{M}$ is a minimal list, which is equivalent to $\mathcal{L}$ in
this case.

_Case II._ If all iterations of Step 6 were carried out without breaking, then
we obtain a list $\mathcal{M}_{1}$ of constant depth $1$ which by the above
induction is equivalent to $\mathcal{N}_{d}\cup\ldots\cup\mathcal{N}_{1}$, and
hence satisfies $\mathcal{M}_{1}\cup\mathcal{N}_{0}\sim\mathcal{L}$. If the
list $\mathcal{N}^{\prime}$ produced in Step 7(a) is non-empty, then
$\mathcal{M}_{1}$ is a non-constant brotherhood of depth $1$, and by the
argument in Section 2.4.4 we deduce that
$\mathcal{M}:=\mathcal{M}_{1}\cup\mathcal{N}_{0}$ is minimal, and thus a
minimal list equivalent to $\mathcal{L}$. If, on the other hand,
$\mathcal{N}^{\prime}$ is empty, then $\mathcal{M}_{1}$ is equivalent to
$\mathcal{K}$, and hence
$\mathcal{L}\sim\mathcal{M}_{1}\cup\mathcal{N}_{0}\sim\mathcal{K}\cup\mathcal{N}_{0}$,
i.e. $\mathcal{L}$ is equivalent to
$\mathcal{M}:=\textsc{NormalizeList}(\mathcal{K}\cup\mathcal{N}_{0})$.
Moreover, $\mathcal{M}$ is a normalized list of maximal depth $\leq 0$, hence
minimal. This finishes the proof of correctness in Case II.

It remains to estimate the time complexity of the algorithm; we proceed
similarly to the complexity analysis in Lemma 4.9. It suffices to show that
each of the 7 steps of the algorithm is executed in time at most
$O(T(|\mathcal{N}|))_{\rm tot}$. This is obvious for Step 2. By Lemma 4.2,
Step 1 takes time $O(T(|\mathcal{L}|_{\rm tot}))$ and produces a list
$\mathcal{N}$ with $|\mathcal{N}|_{\rm tot}\leq|\mathcal{L}|_{\rm tot}$. The
latter implies in particular that Step 3 can be performed in time
$O(|\mathcal{N}|_{\rm tot})\leq O(|\mathcal{L}|_{\rm tot})$. Similarly, the
split in Step 4 takes time $O(|\mathcal{N}|_{\rm tot})\leq
O(|\mathcal{L}|_{\rm tot})$ since it can be done by a single run over the list
$\mathcal{N}$. The complexity of Step 5 is also linear.

Now we consider the iterations of Step 6. Let us assume that these iterations
produce lists $\mathcal{M}_{d},\dots,\mathcal{M}_{t}$ before an iteration
breaks. We claim that

$|\mathcal{M}_{i}|_{\rm tot}\leq\frac{8}{9}|\mathcal{M}_{i+1}|_{\rm
tot}+|\mathcal{N}_{i}|_{\rm tot}\quad\text{for all }t\leq i\leq d-1.$

Indeed, this inequality holds for trivial reasons if $\mathcal{M}_{i+1}$ is
empty, and otherwise follows from Lemma 4.9(iv). If we denote by
$\mathcal{M}_{d+1}$ the empty list, then it also holds for $i=d$, since
$|\mathcal{M}_{d}|_{\rm tot}=|\mathcal{N}_{d}|_{\rm tot}$. By descending
induction on $i$ we then find that

$|\mathcal{M}_{i}|_{\rm
tot}\leq\sum_{k=i}^{d}\left(\frac{8}{9}\right)^{k-i}|\mathcal{N}_{i}|_{\rm
tot}\quad(i\in\\{t,\dots,d\\}).$

Summing up the left and right parts over $i=t,\ldots,d$, we obtain, that

$\sum_{i=t}^{d}|\mathcal{M}_{i}|_{\rm
tot}\leq\sum_{i=t}^{d}\left(\sum_{k=i}^{d}\left(\frac{8}{9}\right)^{k-i}|\mathcal{N}_{i}|_{\rm
tot}\right)\leq\sum_{i=t}^{d}\left(\sum_{j=0}^{\infty}\left(\frac{8}{9}\right)^{j}\right)|\mathcal{N}_{i}|_{\rm
tot}=9\sum_{i=t}^{d}|\mathcal{N}_{i}|_{\rm tot}.$

Thus, if $\mathcal{M}_{d},\dots,\mathcal{M}_{t}$ are produced before an
iteration breaks, then

$\sum_{i=t}^{d}|\mathcal{M}_{i}|_{\rm tot}\leq
9\sum_{i=t}^{d}|\mathcal{N}_{i}|_{\rm tot}\leq 9|\mathcal{N}|_{\rm tot}.$
(4.6)

Given $i\in\\{t,\dots,d\\}$, the $(d-i+1)$th iteration of Step 6(a) takes time
$O(T(|\mathcal{M}_{i}|_{\rm tot})))$ by Lemma 4.9(v). It thus follows from
Lemma A.4 that all of the iterations of Step 6(a) taken together take time at
most $O(|\mathcal{M}_{t}|+\dots+O(|\mathcal{M}_{d}|))$, and thus times at most
$O(T(|\mathcal{N}|_{\rm tot})))$ due to Inequality (4.6) and the fact that the
function $T$ satisfies Property (T3) from Convention A.3.

Similarly, for every $i\in\\{t,\dots,d\\}$, the call of the procedure
NormalizeList in the $(d-i+1)$-th iteration of Step 6(b) takes time at most
$O\left(T\left(\frac{8}{9}|\mathcal{M}_{i}|_{\rm tot}+|\mathcal{N}_{i-1}|_{\rm
tot}\right)\right)$. Summing over $i$ and using the Totalling Lemma A.4 we
obtain that together all these calls take time at most
$O(T(\frac{8}{9}|\mathcal{M}_{t}|_{\rm
tot}+\dots+\frac{8}{9}|\mathcal{M}_{d}|_{\rm tot}+|\mathcal{N}|_{\rm tot}))$,
which is again $O(T(|\mathcal{N}|_{\rm tot})$ by Inequality (4.6) and Property
(T3). We have thus established that the whole Step 6 can be carried out in
time $O((|\mathcal{N}|_{\rm tot})$.

Now assume that $\mathcal{M}_{d},\dots,\mathcal{M}_{t}$ have been produced in
Step 6 before a break. If $t\geq 2$, i.e. a break occured, then in Step 7 the
algorithm just returns a minimal list
$\mathcal{M}:=\mathcal{M}_{t}\cup\mathcal{N}_{t-1}\cup\ldots\cup\mathcal{N}_{0}$
of size at most

$|\mathcal{M}|_{\rm tot}=|\mathcal{M}_{t}|_{\rm
tot}+\sum_{i=0}^{t-1}|\mathcal{N}_{i}|_{\rm tot}\leq
9\sum_{i=t}^{d}|\mathcal{N}_{i}|_{\rm
tot}+9\sum_{i=0}^{t-1}|\mathcal{N}_{i}|_{\rm tot}=9|\mathcal{N}|_{\rm tot}.$

If $t=1$, i.e. no break occurs, then Step 7 initially operates with the list
$\mathcal{M}_{1}$, which has size at most $m:=9(|\mathcal{N}|_{\rm
tot}-|\mathcal{N}_{0}|_{\rm tot})$ according to (4.6). The pruning in Step
7(a) then takes time $O(T(|\mathcal{M}_{1}|_{\rm
tot}))=O(T(m))=O((|\mathcal{N}|_{\rm tot})$ to produce a list
$\mathcal{N}^{\prime}\cup\mathcal{K}$ of size at most $m$ by Lemma 4.4. The
potentially necessary normalization in Step 7(b) then takes time
$O(T(m))=O((|\mathcal{N}|_{\rm tot})$ as well, and hence the whole Step 7 can
be accomplished in time $O((|\mathcal{N}|_{\rm tot})$ and produces a list
$\mathcal{M}$ of total size at most $9|\mathcal{N}|_{\rm tot}$. ∎

##  5 The group case

In this section we explain how the techniques of the previous sections have to
be modified to deal with counting functions on a free group rather than on a
few monoid. We will see, that only at very few places some modifications will
be necessary, although the notation gets more involved.

###  5.1 Encoding counting functions on free groups

In this section, we consider again a finite alphabet
$\mathtt{A}=\\{\mathtt{a}_{1},\dots,\mathtt{a}_{n}\\}$ of size $n\geq 2$. We
then define the _extended alphabet_
$\mathtt{A}^{\pm}:=\\{\mathtt{a}_{1},\dots,\mathtt{a}_{n},\mathtt{a}^{-1}_{1},\dots,\mathtt{a}^{-1}_{n}\\}$,
where $\mathtt{a}^{-1}_{1},\dots,\mathtt{a}^{-1}_{n}$ are further symbols
chosen such that $|\mathtt{A}^{\pm}|=2n$. We then identify $F_{n}$ with the
subset $\mathtt{A}^{\pm\ast}\subset(\mathtt{A}^{\pm})^{*}$ consisting of words
which are reduced, i.e. which do not contain any subword of the form
$\mathtt{a}_{j}\mathtt{a}^{-1}_{j}$ or $\mathtt{a}^{-1}_{j}\mathtt{a}_{j}$ for
some $j\in\\{1,\dots,n\\}$. Given a word $w\in\mathtt{A}^{\pm\ast}$ we denote
by $w_{\mathrm{in}}\in\mathtt{A}^{\pm}$ and
$w_{\mathrm{fin}}\in\mathtt{A}^{\pm}$ its initial and final letter
respectively.

From now on let $\mathfrak{N}\in\\{\mathbb{Z},\mathbb{Q}\\}$. By a _word-
coefficient pair_ (or _pair_ for short) we shall mean a pair $(w,\mathtt{x})$,
where $w\in\mathtt{A}^{\pm\ast}$ and $x\in\mathrm{Num}_{\mathfrak{N}}$, and by
an encoded list (or _list_ for short) we shall mean a doubly linked list of
word-coefficient pairs. Any such list then represents a counting function over
$F_{n}$. Explicitly, if $\mathcal{L}=((w_{1},x_{1}),\dots,(w_{N},x_{N}))$,
then the _associated counting function_ is

$\rho_{\mathcal{L}}=\sum_{i=1}^{N}\langle x_{i}\rangle\rho_{w_{i}}.$

As in the monoid case we say that a list
$\mathcal{L}=((w_{1},\mathtt{x}_{1}),\dots,(w_{N},\mathtt{x}_{N}))$ has
_maximal depth_

$\ell:=\sup\\{|w_{j}|\mid\mathtt{x}_{j}\not\equiv 0\\}$

and we say that $\mathcal{L}$ is _minimal_ if it is not equivalent to a list
of smaller maximal depth. We also say that $\mathcal{L}$ is _normalized_ if
the words $w_{j}$ are all distinct, ordered by length and ordered
lexicographically within words of the same length (with respect to some fixed
total order on $\mathtt{A}^{\pm}$), and if $\mathtt{x}_{j}\not\equiv 0$ for
all $j\in\\{1,\dots,N\\}$.

######  Remark 5.1.

As in the monoid case there is a procedure NormalizeList which replaces a
given list $\mathcal{L}$ by an equivalent normalized list $\mathcal{N}$ of
total size $|\mathcal{N}|_{\mathrm{tot}}\leq|\mathcal{L}|_{\mathrm{tot}}$ in
time at most $O(T(|\mathcal{L}|_{\mathrm{tot}}))$.

Similarly to the monoid case we have two kinds of basic equivalences between
counting functions on $F_{n}$ (see [9]), but these are now given by the
slightly different formulas

$\rho_{w}\sim\sum_{\mathtt{a}\in\mathtt{A}^{\pm}\setminus\\{w_{\mathrm{in}}^{-1}\\}}\rho_{\mathtt{a}w}\quad\text{and}\quad\rho_{w}\sim\sum_{\mathtt{a}\in\mathtt{A}^{\pm}\setminus\\{w_{\mathrm{fin}}^{-1}\\}}\rho_{w\mathtt{a}}.$
(5.1)

To take this into account, we will need to slightly modify our pruning and
transfer moves.

We will in particular be interested in counting functions $f$ which are
_antisymmetric_ (i.e. $f(g^{-1})=-f(g)$), since these represent classes in
bounded cohomology of $F_{n}$ (see [5]). We then also call the corresponding
lists antisymmetric.

As before, two lists are called _equivalent_ if the corresponding counting
functions are equivalent, i.e. at bounded distance from each other, and this
equivalence is denoted by $\sim$. We also say that two symmetric counting
functions $f_{1},f_{2}$, and by extension any two lists representing them, are
_cohomologous_ , denoted $f_{1}\equiv f_{2}$, provided $f_{1}-f_{2}$ is at
bounded distance from a homomorphism and hence $f_{1}$ and $f_{2}$ define the
same class in bounded cohomology. We want to solve the following two problems
algorithmically:

######  Problem 5.2 (Equivalence problem).

Given two lists $\mathcal{L}_{1},\mathcal{L}_{2}$, decide whether
$\mathcal{L}_{1}\sim\mathcal{L}_{2}$.

######  Problem 5.3 (Cohomological problem).

Given two antisymmetric lists $\mathcal{L}_{1},\mathcal{L}_{2}$, decide
whether $\mathcal{L}_{1}\equiv\mathcal{L}_{2}$.

As in the monoid case, both problems can be reduced to the following problem -
note that a list which is equivalent to an antisymmetric list is cohomologous
to the empty list if and only if it is equivalent to a list of maximal depth
$\leq 1$.

######  Problem 5.4 (Minimality problem).

Given a list $\mathcal{L}$, find a minimal list $\mathcal{L}^{\prime}$ which
is equivalent to $\mathcal{L}$.

###  5.2 Brotherhoods and basic moves

Let $T_{n}$ denote the right-Cayley tree of $F_{n}$ with respect to the
extended generating set $\mathtt{A}^{\pm}$, considered as an oriented rooted
tree with root $\varepsilon$ and edges oriented away from $\varepsilon$. We
identify elements of $F_{n}$ with vertices of $T_{n}$. Within $T_{n}$ we can
talk about fathers, brothers, brotherhoods and related brotherhoods as in the
monoid case and we use the same notation. Note, however, that
$|\\{\varepsilon\ast\\}|=2n$ whereas $|\\{w\ast\\}|=2n-1$ for all
$w\neq\varepsilon$, i.e. the unique brotherhood of depth $1$ is different in
size from all the other brotherhoods. Given a normalized list $\mathcal{L}$
and a brotherhood $B$ we define the weighted brotherhood $\mathcal{L}_{B}$
exactly as in the monoid case. We can then define a Procedure
DetachBrotherhood with the same properties and runtime as in Lemma 4.3 also in
the group case.

####  5.2.1 Pruning

Let $\mathcal{L}$ be a normalized list of maximal depth $\ell\geq 1$. As in
the monoid case, if $B=\\{w\ast\\}$ is a brotherhood and the weighted
brotherhood
$\mathcal{L}_{B}=((w\mathtt{a}_{1},\mathtt{x_{1}}),\dots,(w\mathtt{a_{n}}^{-1},\mathtt{x}_{2n}))$
is non-empty and constant with
$\mathtt{x}_{1}\equiv\dots\equiv\mathtt{x}_{2n}\equiv\mathtt{x}_{n}\equiv\mathtt{x}$
for some $\mathtt{x}\in\mathtt{Num}_{\mathfrak{N}}$, then we can remove
$\mathcal{L}_{B}$ from $\mathcal{L}$, append $\\{\mathtt{w},\mathtt{x}\\}$ and
normalize the resulting list. This is called a _pruning move_ , and a
normalized list is called _pruned_ if it does not allow for any pruning moves.

We can now extend the procedure PruneList from the monoid case to the group
case. Our new procedure carries out exactly the same steps as in the monoid
case. This procedure will have the same properties listed in Lemma 4.4 except
that the estimate in Part (iv) becomes

$|\mathcal{L}|_{\rm tot}\leq\frac{1}{h(n)}(|\mathcal{N}|_{\rm
tot}-|\mathcal{N}^{\prime}|_{\rm tot})$

where $h(n)$ is the size of a non-empty constant brotherhood of depth $\ell$,
i.e. $h(n)=2n-1$ if $\ell\geq 2$ and $h(n)=2n$ if $\ell=1$.

####  5.2.2 Generic transfer-and-prune moves

As in the monoid case we also have the notion of a transfer move in the group
case. In fact we have two slightly different transfer moves, depending on
whether the brotherhood, which is transferred, has depth $\geq 3$ (the
_generic_ case) or depth $2$ (the _special_ case). In this subsection we
discuss exclusively the generic case, leaving the special case to the next
subsection. Thus let $u\in F_{n}\setminus\\{\varepsilon\\}$ and let
$\mathcal{L}$ be a normalized list of depth $\ell\geq 3$, where
$|u|=\ell-2\geq 1$. We set

$\mathtt{A}^{\pm}_{\mathrm{in}}:=\mathtt{A}^{\pm}\setminus\\{u_{\mathrm{in}}^{-1}\\}\quad\text{and}\quad\mathtt{A}^{\pm}_{\mathrm{fin}}:=\mathtt{A}^{\pm}\setminus\\{u_{\mathrm{fin}}^{-1}\\}.$

As in the monoid case we write $\mathcal{L}_{\\{\ast u\ast\\}}$ for the
concatenation of the weighted brotherhoods
$\mathcal{L}_{\\{\mathtt{a}\mathtt{u}\ast\\}}$ with
$\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}}$. Entries of
$\mathcal{L}_{\\{\ast u\ast\\}}$ are then of the form

$(\mathtt{a}\mathtt{u}\mathtt{a^{\prime}},\mathtt{x}_{\mathtt{a}\mathtt{a^{\prime}}})\quad\text{with}\quad
a\in\mathtt{A}^{\pm}_{\mathrm{in}}\text{ and
}\mathtt{a}^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{fin}}.$ (5.2)

We many thus define the encoded transfer matric $\mathtt{T}(\mathcal{L},u)$ as
the matrix of size $(2\ell-1)\times(2\ell-1)$ whose rows and columns are
indexed by $\mathtt{A}^{\pm}_{\mathrm{in}}$ and
$\mathtt{A}^{\pm}_{\mathrm{fin}}$ respectively and whose entry
$\mathtt{t}_{\mathtt{a}\mathtt{a^{\prime}}}$ with index
$(\mathtt{a},\mathtt{a^{\prime}})\in\mathtt{A}^{\pm}_{\mathrm{in}}\times\mathtt{A}^{\pm}_{\mathrm{fin}}$
is given by $\mathtt{x}_{\mathtt{a}\mathtt{a^{\prime}}}$ if
$\mathcal{L}_{\\{\ast u\ast\\}}$ contains an entry of the form (5.2) and by
$t_{\mathrm{a}\mathrm{a^{\prime}}}:=\varepsilon$ otherwise. If we fix
$\mathtt{b}\in\mathtt{A}^{\pm}_{\mathrm{in}}$. then we have

$\displaystyle\rho_{\mathcal{L}_{\\{\ast u\ast\\}}}$ $\displaystyle=$
$\displaystyle\sum_{\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}}}\sum_{\mathtt{a}^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{fin}}}\mathtt{t}_{\mathtt{a}\mathtt{a}^{\prime}}\rho_{\mathtt{a}u\mathtt{a}^{\prime}}\;=\;\sum_{\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}}}\sum_{\mathtt{a}^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{fin}}}(\mathtt{t}_{\mathtt{a}\mathtt{a}^{\prime}}-\mathtt{t}_{\mathtt{b}\mathtt{a}^{\prime}})\rho_{\mathtt{a}u\mathtt{a}^{\prime}}\rho_{\mathtt{a}_{i}\mathtt{u}\mathtt{a}_{j}}+\sum_{\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}}}\sum_{\mathtt{a}^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{fin}}}\mathtt{t}_{\mathtt{b}\mathtt{a}^{\prime}}\rho_{\mathtt{a}u\mathtt{a}^{\prime}}$
$\displaystyle\sim$
$\displaystyle\sum_{\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}}\setminus\\{\mathtt{b}\\}}\sum_{\mathtt{a}^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{fin}}}(\mathtt{t}_{\mathtt{a}\mathtt{a}^{\prime}}-\mathtt{t}_{\mathtt{b}\mathtt{a}^{\prime}})\rho_{\mathtt{a}u\mathtt{a}^{\prime}}+\sum_{\mathtt{a}^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{fin}}}\mathtt{t}_{\mathtt{b}\mathtt{a}^{\prime}}\rho_{u\mathtt{a}^{\prime}}$

The list $\mathcal{L}$ is thus equivalent to any list $\mathcal{L}^{\prime}$
which is obtained from $\mathcal{L}$ by deleting $\mathcal{L}_{\\{\ast
u\ast\\}}$, appending a pair of the form
$(\mathtt{a}\mathtt{u}\mathtt{a}^{\prime},\mathtt{y}_{\mathtt{a}\mathtt{a^{\prime}}})$
with
$\mathtt{y}_{\mathtt{a}\mathtt{a^{\prime}}}\equiv\mathtt{t}_{\mathtt{a}\mathtt{a}^{\prime}}-\mathtt{t}_{\mathtt{b}\mathtt{a}^{\prime}}$
for all $\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}}\setminus\\{\mathtt{b}\\}$
and $\mathtt{a}^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{fin}}$ with
$\mathtt{t}_{\mathtt{a}\mathtt{a}^{\prime}}\not\equiv\mathtt{t}_{\mathtt{b}\mathtt{a}^{\prime}}$,
appending a pair of the form
$(\mathtt{u}\mathtt{a}^{\prime},\mathtt{z}_{\mathtt{a^{\prime}}})$ with
$\mathtt{z}_{\mathtt{a^{\prime}}}\equiv\mathtt{t}_{\mathtt{b}\mathtt{a}^{\prime}}$
for every $\mathtt{a^{\prime}}\in\mathtt{A}^{\pm}_{\mathrm{fin}}$with
$\mathtt{t}_{\mathtt{b}\mathtt{a}^{\prime}}\neq\varepsilon$ and normalizing
the resulting list. We say that any such list $\mathcal{L}^{\prime}$ is
obtained from $\mathcal{L}$ by a _transfer move_ with stem $u$ and special
letter $\mathtt{b}$.

According to [9, Theorem 4.2], Theorem 2.9 holds mutatis mutandis also in the
group case, i.e. a list of maximal depth $\ell$ is minimal if it admits two
related weighted brotherhoods one of which is empty and the other of which is
non-constant. If $\mathcal{L}^{\prime}$ is obtained from $\mathcal{L}$ by a
transfer move with stem $u$ and special letter $\mathtt{b}$, then
$\mathcal{L}^{\prime}_{\mathtt{b}u*}$ is empty and hence
$\mathcal{L}^{\prime}$ is minimal unless all of the weighted brotherhoods of
the form $\mathcal{L}^{\prime}_{\mathtt{a}u*}$ with
$\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}}\setminus\\{\mathtt{b}\\}$ are
constant. As in the monoid case, this implies that $\mathcal{L}^{\prime}$ is
minimal unless $\mathtt{T}(\mathcal{L},u)$ is a column-row sum.

Now assume that
$\mathtt{T}(\mathcal{L},u)=(\mathtt{t}_{\mathtt{a}\mathtt{a^{\prime}}})$ is a
column-row sum. This means that for every
$\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}}$ the the number
$\langle\mathtt{t_{aa^{\prime}}}\ominus\mathtt{t}_{\mathtt{ba^{\prime}}}\rangle$
is independent of $\mathtt{a^{\prime}}\in\mathtt{A}^{\pm}_{\mathrm{fin}}$.
Consequently, if we choose elements
$y_{\mathtt{a}},z_{\mathtt{a^{\prime}}}\in\mathtt{Num}_{\mathfrak{N}}$ such
that

$\mathtt{y}_{\mathtt{a}}\equiv\mathtt{t_{aa^{\prime}}}\ominus\mathtt{t}_{\mathtt{ba^{\prime}}}\quad\text{and}\quad\mathtt{z}_{\mathtt{a}^{\prime}}\equiv\mathtt{t}_{\mathtt{b}\mathtt{a}^{\prime}}\quad(\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}},\mathtt{a^{\prime}}\in\mathtt{A}^{\pm}_{\mathrm{fin}}),$
(5.3)

then from the above formula for $\rho_{\mathcal{L}_{\ast u\ast}}$ we obtain

$\rho_{\mathcal{L}_{\ast
u\ast}}\sim\sum_{\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}}\setminus\\{\mathtt{b}\\}}\sum_{\mathtt{a}^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{fin}}}(\mathtt{t}_{\mathtt{a}\mathtt{a}^{\prime}}-\mathtt{t}_{\mathtt{b}\mathtt{a}^{\prime}})\rho_{\mathtt{a}u\mathtt{a}^{\prime}}+\sum_{\mathtt{a}^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{fin}}}\mathtt{t}_{\mathtt{b}\mathtt{a}^{\prime}}\rho_{u\mathtt{a}^{\prime}}=\sum_{\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}}\setminus\\{\mathtt{b}\\}}\mathtt{y_{a}}\rho_{\mathtt{a}u}+\sum_{\mathtt{a}^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{fin}}}\mathtt{z}_{\mathtt{a^{\prime}}}\rho_{u\mathtt{a}^{\prime}}$

Thus if $\mathtt{T}(\mathcal{L},u)$ is a column-row-sum and
$\mathcal{L}^{\prime}$ is obtained from $\mathcal{L}$ by deleting
$\mathcal{L}_{\ast u\ast}$, appending pairs $(\mathtt{a}u,\mathtt{y_{a}})$ and
$(u\mathtt{a^{\prime}},\mathtt{z_{a^{\prime}}})$ subject to (5.3) and
normalizing, then $\mathcal{L}^{\prime}$ is equivalent to $\mathcal{L}$. We
say that $\mathcal{L}^{\prime}$ is obtained from $\mathcal{L}$ by a _transfer-
and-prune move_ with stem $u$ and special letter $\mathtt{b}$. Using this move
we can now generalize the results of Section 4.3:

######  Lemma 5.5.

There exists a procedure TransferAndPrune with the following properties:

  1. (i)

The input is a family $(\mathcal{B}_{1},\dots,\mathcal{B}_{n})$ of non-
constant related brotherhoods of depth $\ell\geq 3$ such that
$\mathcal{B}:=\mathcal{B}_{1}\cup\dots\cup\mathcal{B}_{n}$ is normalized.

  2. (ii)

The output is a Boolean variable minimal and a list $\mathcal{L}$.

  3. (iii)

If $\textsc{minimal}=\texttt{true}$, then $\mathcal{B}$ is not equivalent to
any list of depth $\leq\ell-1$ and $\mathcal{L}=\mathcal{B}$.

  4. (iv)

If $\textsc{minimal}=\texttt{false}$, then $\mathcal{L}$ is of constant depth
$\ell-1$, equivalent to $\mathcal{B}$ and of total size

$|\mathcal{L}|_{\rm tot}\quad\leq\quad\frac{8}{9}\cdot|\mathcal{B}|_{\rm
tot}.$

  5. (v)

The runtime of the procedure is $O(T(|\mathcal{B}|_{\rm tot}))$

There are two main differences to the results from Section 4.3: Firstly, we
allow $n=2$, whereas in the monoid case the condition $n\geq 3$ was needed to
ensure the estimate in (iv). On the other hand, we have to assume here that
$\ell\geq 3$; however, we will deal with the case $\ell=2$ (which corresponds
to an empty stem) separately.

###### Proof.

We follow as close as possible the algorithm of the same name described in
Section 4.3, in particular we will perform $7$ steps which correspond one-to-
one to the $7$ steps in the monoid case.

In the first step we compute the stem and the transfer matrix just as in the
monoid case. The transfer matrix has size $m\times m$, where $m:=(2n-1)$ and
since $n\geq 2$ we have $m\geq 3$. The transfer matrix is now indexed by
$\mathtt{A}^{\pm}_{\mathrm{in}}\times\mathtt{A}^{\pm}_{\mathrm{fin}}$ rather
than $\\{1,\dots,m\\}\times\\{1,\dots,m\\}$, but except for this change in
indexing we can carry out Steps 2 and 3 as in the monoid case.

In Step 4, the sparseness condition has to be chosen relatively to the size
$m$ of the matrix rather than relative to $n$. Thus we set Sparse to be true
if and only if $m\geq 4$ (i.e. $n\geq 3$) and the transfer matrix $\mathtt{T}$
has less than $3m=6n-3$ non-trivial entries or if $m=3$ (i.e. $n=2$) and
$\mathtt{T}$ has less than $2m=4n-2=6$ non-trivial entries.

The remaining Steps 5-7 are then carried out precisely as in the monoid case,
except for the difference in indexing. For example, in Step 5 (a) we append
the pairs of the form
$(u\mathtt{a^{\prime}},\mathtt{t}_{\mathtt{b}\mathtt{a^{\prime}}})$ for
$\mathtt{a^{\prime}}\in A^{\pm}_{\mathrm{fin}}$, where
$\mathtt{b}\in\mathtt{A}^{\pm}_{\mathrm{in}}$ is chosen such that

$\sum_{\mathtt{a^{\prime}}\in
A^{\pm}_{\mathrm{fin}}}||\mathtt{t}_{\mathtt{ba^{\prime}}}||=\min_{\mathtt{a}\in\mathtt{A}^{\pm}_{\mathrm{in}}}\sum_{\mathtt{a^{\prime}}\in
A^{\pm}_{\mathrm{fin}}}||\mathtt{t}_{\mathtt{aa^{\prime}}}||,$

and similarly for the other steps. It is clear that this change in indexing
does not affect the runtime, nor the size of the output. The latter always
satisfies (iv), since for all $n\geq 2$ we have $m\geq 3$ and hence the proof
of Lemma 4.8 applies to the $(m\times m)$-matrix $\mathtt{T}$. ∎

####  5.2.3 Special transfer-and-prune moves

The transfer-and-prune move discussed in the previous section works for all
$n\geq 2$ under the condition that the brotherhood, which is transferred, is
of depth at least $3$. For brotherhoods of depth $\ell=2$ there also exists a
transfer and prune move, but this one is more complicated to describe.
Nevertheless we can establish the following lemma:

######  Lemma 5.6.

The statement of Lemma 5.5 remains true also for $\ell=2$ except that (iv) has
to be replaced by

  * (iv′)

If $\textsc{minimal}=\texttt{false}$, then $\mathcal{L}$ is of constant depth
$\ell-1=1$, equivalent to $\mathcal{B}$ and of total size

$|\mathcal{L}|_{\rm tot}\quad\leq\quad\|\mathcal{B}\|+2n,$

and hence in particular $|\mathcal{L}|_{\rm tot}\leq 2n\cdot|\mathcal{B}|_{\rm
tot}$.

In fact, this estimate is far from optimal, but it is easily established and
sufficient for our purposes. For the proof of the lemma, let $\mathcal{L}$ be
a normalized list of constant depth $2$. We fix a letter
$\mathtt{b}\in\mathtt{A}^{\pm}$ (which we won’t even bother to choose
optimally) and set
$\mathtt{A}^{\pm}_{\mathrm{in}}:=\mathtt{A}^{\pm}\setminus\\{\mathtt{b}^{-1}\\}$.
We want to define a move which clears out the sub-brotherhood of type
$\\{\mathtt{b}\ast\\}$ in $\mathcal{L}$. We first define a _transfer matrix_
$\mathtt{T}=(\mathtt{t_{\mathtt{a}\mathtt{a^{\prime}}}})$ over
$\mathtt{A}^{\pm}\times\mathtt{A}^{\pm}$ by setting $\mathtt{t_{aa^{\prime}}}$
to be the coefficient of $\mathtt{aa^{\prime}}$ in $\mathcal{L}$ if such a
word exists in $\mathcal{L}$ and setting
$\mathtt{t_{aa^{\prime}}}:=\varepsilon$ otherwise. (In particular we then have
$\mathtt{t}_{\mathtt{a}\mathtt{a}^{-1}}=\varepsilon$ for all
$\mathtt{a}\in\mathtt{A}^{\pm}$.) Using the fact that for
$a^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{in}}$ we have

$\langle\mathtt{t}_{\mathtt{ba^{\prime}}}\rangle\rho_{\mathtt{ba^{\prime}}}\sim\langle\mathtt{t}_{\mathtt{ba^{\prime}}}\rangle\rho_{\mathtt{a^{\prime}}}-\sum_{\mathtt{a}\neq(\mathtt{a^{\prime}})^{-1}}\langle\mathtt{t}_{\mathtt{ba^{\prime}}}\rangle\rho_{\mathtt{aa^{\prime}}},$

we obtain

$\displaystyle\rho_{\mathcal{L}}$ $\displaystyle=$
$\displaystyle\sum_{\mathtt{a}\in\mathtt{A}^{\pm}}\sum_{\mathtt{a}^{\prime}\neq\mathtt{a}^{-1}}\langle\mathtt{t_{aa^{\prime}}}\rangle\rho_{\mathtt{aa^{\prime}}}$
$\displaystyle\sim$
$\displaystyle\sum_{a^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{in}}}\langle\mathtt{t}_{\mathtt{ba^{\prime}}}\rangle\rho_{\mathtt{a^{\prime}}}+\sum_{a\in\mathtt{A}^{\pm}\setminus\\{b\\}}\langle\mathtt{t}_{\mathtt{ab^{-1}}}\rangle\rho_{\mathtt{ab^{-1}}}+\sum_{\mathtt{a}\in\mathtt{A}^{\pm}\setminus\\{\mathtt{b}\\}}\sum_{\mathtt{a^{\prime}}\in\mathtt{A}^{\pm}_{\mathrm{in}}\setminus\\{\mathtt{a}^{-1}\\}}\langle\mathtt{t}_{\mathtt{aa^{\prime}}}\ominus\mathtt{t}_{\mathtt{ba^{\prime}}}\rangle\rho_{\mathtt{aa^{\prime}}}.$

We deduce that $\mathcal{L}$ is minimal unless for all
$\mathtt{a}\in\mathtt{A}^{\pm}\setminus\\{\mathtt{b}\\}$

$\mathtt{t}_{\mathtt{ab}^{-1}}\equiv\mathtt{t}_{\mathtt{aa^{\prime}}}\ominus\mathtt{t}_{\mathtt{ba^{\prime}}}\quad\text{for
all }\mathtt{a}\in\mathtt{A}^{\pm}\setminus\\{\mathtt{b}\\}\text{ and
}\mathtt{a^{\prime}}\in\mathtt{A}_{\mathrm{in}}^{\pm}\setminus\\{\mathtt{a}^{-1}\\}.$
(5.4)

On the other hand, if (5.4) holds, then we can apply pruning moves to obtain

$\rho_{\mathcal{L}}\sim\sum_{a^{\prime}\in\mathtt{A}^{\pm}_{\mathrm{in}}}\langle\mathtt{t}_{\mathtt{ba^{\prime}}}\rangle\rho_{\mathtt{a^{\prime}}}+\sum_{a\in\mathtt{A}^{\pm}\setminus\\{b\\}}\langle\mathtt{t}_{\mathtt{ab^{-1}}}\rangle\rho_{\mathtt{a}}=\langle\mathtt{t}_{\mathtt{bb}}\rangle\rho_{\mathtt{b}}+\langle\mathtt{t}_{\mathtt{b}^{-1}\mathtt{b}^{-1}}\rangle\rho_{\mathtt{b}^{-1}}\sum_{a\in\mathtt{A}^{\pm}\setminus\\{b,b^{-1}\\}}\langle\mathtt{t}_{\mathtt{ba}}\oplus\mathtt{t}_{\mathtt{ab}^{-1}}\rangle\rho_{\mathtt{a}}.$

This shows that the following procedure works correctly:

Procedure SpecialTransferAndPrune

Input: An family of non-constant related brotherhoods
$(\mathcal{B}_{1},\dots,\mathcal{B}_{n})$ of depth $\ell=2$
Input:* such that $\mathcal{B}:=\mathcal{B}_{1}\cup\dots\cup\mathcal{B}_{n}$
is normalized.

Output: A Boolean variable minimal and a list $\mathcal{L}$.

  1. 1.

Compute the transfer matrix $\mathtt{T}=(\mathtt{t_{aa^{\prime}}})$ and choose
$\mathtt{b}:=\mathtt{a}_{1}$.

  2. 2.

For each $\mathtt{a}\in\mathtt{A}^{\pm}\setminus\\{\mathtt{b}\\}$ do
for each
$\mathtt{a^{\prime}}\in\mathtt{A}_{\mathrm{in}}^{\pm}\setminus\\{\mathtt{a}^{-1}\\}$
do the following:

    1. (a)

If
$\mathtt{t}_{\mathtt{ab}^{-1}}\not\equiv\mathtt{t}_{\mathtt{aa^{\prime}}}\ominus\mathtt{t}_{\mathtt{ba^{\prime}}}$,
then
return $\textsc{Minimal}:=\texttt{true}$ and
$\mathcal{L}:=\mathcal{B}_{1}\cup\dots\cup\mathcal{B}_{n}$ and terminate the
procedure

  3. 3.

Set
$\mathcal{L}:=((\mathtt{b},\mathtt{t}_{\mathtt{bb}}),(\mathtt{b}^{-1},\mathtt{t}_{\mathtt{b^{-1}b^{-1}}}))$
and for $\mathtt{a}\in\mathtt{A}^{\pm}\setminus\\{b,b^{-1}\\}$ do the
following:

    1. (a)

Append
$(\mathtt{a},\mathtt{t}_{\mathtt{ba}}\oplus\mathtt{t}_{\mathtt{ab}^{-1}})$ to
$\mathcal{L}$.

  4. 4.

Return $\textsc{Minimal}:=\texttt{false}$ and $\mathcal{L}$.

It is easy to see that the runtime of the procedure is given by
$O(T(|\mathcal{B}|_{\mathrm{tot}}))$. As for (iv′), in the non-minimal case we
have $\|\mathcal{L}\|\leq\|\mathtt{T}\|=\|\mathcal{B}\|$ since each non-
trivial coefficient of $\mathtt{T}$ is copied at most once into $\mathcal{L}$,
and clearly $|\mathcal{L}|\leq|\mathtt{A}^{\pm}|=2n$, hence (iv′) holds.

###  5.3 The algorithm in the group case

####  5.3.1 The main processing step

At this point we have extended the procedures NormalizeList,
DetachBrotherhood, PruneList and TransferAndPrune from the monoid case to the
group case. The latter works only for lists of depth $\ell\geq 3$, but the
case $\ell=2$ can be dealt with by the additional procedure
SpecialTransferAndPrune from Section 5.2.3. Using these procedures we can now
define a procedure MainProcessingStep almost literally as in the monoid case
(see p.4.4), except that in Step 4(b) we replace the procedure
TransferAndPrune by the procedure SpecialTransferAndPrune if $\ell=2$. The
same analysis as in the monoid case then shows:

######  Lemma 5.7.

For every non-abelian free group $F_{n}$ with $n\geq 2$, there exists an
algorithm MainProcessingStep with the following properties:

  1. (i)

The input is a normalized list $\mathcal{L}$ of constant depth $\ell\geq 2$.

  2. (ii)

The output is a boolean parameter minimal and a normalized list
$\mathcal{L}^{\prime}$ equivalent to $\mathcal{L}$.

  3. (iii)

It $\textsc{minimal}=\mathtt{true}$, then $\mathcal{L}^{\prime}$ is minimal.

  4. (iv)

If $\textsc{minimal}=\mathtt{false}$, then $\mathcal{L}^{\prime}$ is of
constants depth $\ell-1$ and

$|\mathcal{L}^{\prime}|_{\mathrm{tot}}\leq\left\\{\begin{array}[]{rl}\frac{8}{9}|\mathcal{L}|_{\rm
tot},&\text{if }\ell\geq 3,\\\ \ 2n|\mathcal{L}|_{\rm tot},&\text{if
}\ell=2.\end{array}\right.$ (5.5)

  5. (v)

The runtime of the algorithm is $O(T(|\mathcal{L}|))$.

Here the difference in (iv) (compared to Lemma 4.9) comes from the use of the
procedure SpecialTransferAndPrune.

####  5.3.2 The final algorithm

We are now ready to establish the main result of the present article; as
before we set $T(N):=N$ if $\mathfrak{N}=\mathbb{Z}$ and $T(N):=N\log N$ if
$\mathfrak{N}=\mathbb{Q}$.

######  Theorem 5.8.

For every $n\geq 2$ and $\mathfrak{N}\in\\{\mathbb{Z},\mathbb{Q}\\}$ there
exists an algorithm FindMinimalList which takes as input an encoded list
$\mathcal{L}$ over $F_{n}$ with coefficients in $\mathfrak{N}$, terminates
within time $O(T(|\mathcal{L}|_{\rm tot}))$ and gives as output a minimal
encoded list $\mathcal{M}$ equivalent to $\mathcal{L}$.

This implies the following more precise version of of Theorem 1.1 from the
introduction:

######  Corollary 5.9.

For every $n\geq 2$ and $\mathfrak{N}\in\\{\mathbb{Z},\mathbb{Q}\\}$ there
exist algorithms of time complexity $O(T(N))$ (where $N$ denotes the size of
the input) to decide whether two counting functions (respectively counting
quasimorphisms) over $F_{n}$ with coefficients in $\mathfrak{N}$ (encoded as
encoded lists) are equivalent (respectively cohomologous).∎

The proof of Theorem 5.8 is analogous to the proof of Theorem 3.2 in the
monoid case. In fact, if we use the group versions of the procedures
NormalizeList, PruneList and MainProcessingStep instead of the monoid
versions, then we can define the algorithm FindMinimalList literally as in the
monoid case. The proof for correctness of this algorithm is then as in the
monoid case.

As for the runtime analysis of the algorithm in the group case, there is only
one difference compared to the monoid case, which is caused by the difference
between Lemma 4.9 and Lemma 5.7. Namely, in Step 6 we apply the procedure
MainProcessingStep to generate lists $\mathcal{M}_{d},\dots,\mathcal{M}_{t}$;
here either $t=1$ or $t\geq 2$ and a break happens before $\mathcal{M}_{t-1}$
was computed. As long as $i\in\\{t,\dots,d\\}$ satisfies $i\geq 2$ we have

$|\mathcal{M}_{i}|_{\rm tot}\leq\frac{8}{9}|\mathcal{M}_{i+1}|_{\rm
tot}+|\mathcal{N}_{i}|_{\rm tot},$

just as in the monoid case, but in view of the difference between Lemma 4.9
and Lemma 5.7 we only obtain the weaker estimate

$|\mathcal{M}_{1}|_{\rm tot}\leq 2n|\mathcal{M}_{2}|_{\rm
tot}+|\mathcal{N}_{1}|_{\rm tot}.$

Of course, this difference only occurs if $t=1$, i.e. if no break occurs in
Step 6. Assume this from now on. In this case we have, as in the monoid case,
the estimates

$|\mathcal{M}_{2}|_{\rm tot}\leq\sum_{i=2}^{d}|\mathcal{M}_{i}|_{\rm tot}\leq
9\sum_{i=2}^{d}|\mathcal{N}_{i}|_{\rm tot},$

and hence

$\sum_{i=1}^{d}|\mathcal{M}_{i}|_{\rm tot}\leq|\mathcal{M}_{1}|_{\rm
tot}+9\sum_{i=2}^{d}|\mathcal{N}_{i}|_{\rm tot}\leq 2n|\mathcal{M}_{2}|_{\rm
tot}+9\sum_{i=1}^{d}|\mathcal{N}_{i}|_{\rm
tot}\leq(18n+9)\cdot\sum_{i=1}^{d}|\mathcal{N}_{i}|_{\rm tot},$

i.e. for all $i\in\\{1,\dots,d\\}$ we obtain

$|\mathcal{M}_{i}|\leq\sum_{i=1}^{d}|\mathcal{M}_{i}|_{\rm
tot}\leq(18n+9)\left(|\mathcal{N}|_{\rm tot}-|\mathcal{N}_{0}|_{\rm
tot}\right).$

This inequality can now be used to replace Inequality (4.6) for the remainder
of the runtime analysis. The rest of the proof of Theorem 5.8 is then
identical with the proof of Theorem 3.2, except for the slightly worse
constant $(18n+9)$ instead of $9$. Of course, for this argument to be valid it
is important for $n$ to be so small as to be considered as a constant.

##  Appendix A Encoding of arithmetic operations

In this appendix we discuss the encodings of arithmetic for integer and
rational numbers which are used in the body of the text. For each of two cases
$\mathfrak{N}\in\\{\mathbb{Z},\mathbb{Q}\\}$ we will choose an alphabet
$\Sigma_{\mathfrak{N}}$, an encoding subset
$\mathtt{Num}_{\mathfrak{N}}\subset\Sigma^{*}$ of the set $\Sigma^{*}$ of
words over $\Sigma$ and a surjective map

$\mathtt{Num}_{\mathfrak{N}}\to\mathfrak{N},\quad\mathtt{x}\mapsto\langle\mathtt{x}\rangle.$

Given $\mathtt{x},\mathtt{y}\in\mathtt{Num}_{\mathfrak{N}}$ we will write
$\mathtt{x}\equiv\mathtt{y}$ provided
$\langle\mathtt{x}\rangle=\langle\mathtt{y}\rangle$.

###  A.1 Encoding integer arithmetic

To encode the semiring $\mathbb{N}_{0}$ of non-negative integers we choose an
auxiliary alphabet $\Sigma_{\mathbb{N}_{0}}:=\\{\mathtt{0},\mathtt{1}\\}$. We
then define $\mathtt{Num}_{\mathbb{N}_{0}}$ as the union of the singleton
$\\{\mathtt{0}\\}$ and the set of all finite words over
$\Sigma_{\mathbb{N}_{0}}$ which start with $\mathtt{1}$. We then obtain a
bijective encoding

$\mathtt{Num}_{\mathbb{N}_{0}}\to\mathbb{N}_{0},\quad\mathtt{x}\mapsto\langle\mathtt{x}\rangle$

by interpreting each word in $\mathtt{Num}_{\mathbb{N}_{0}}$ as a binary
expansion of a natural number, so that e.g. $\mathtt{111}$ represents $7$. To
encode the ring $\mathbb{Z}$ of integers we use the alphabet
$\Sigma_{\mathbb{Z}}:=\\{\mathtt{0},\mathtt{1},\mathtt{+},\mathtt{-}\\}$ and
define

$\mathtt{Num}_{\mathfrak{\mathbb{Z}}}:=\\{\varepsilon\\}\cup\\{\mathtt{+}\mathtt{x}\mid\mathtt{x}\in\mathtt{Num}_{\mathbb{N}_{0}}\\}\cup\\{\mathtt{-}\mathtt{x}\mid\mathtt{x}\in\mathtt{Num}_{\mathbb{N}_{0}}\\},$

where $\varepsilon$ denotes the empty word. We then have an encoding

$\mathtt{Num}_{\mathbb{Z}}\to\mathbb{Z},\quad\mathtt{x}\mapsto\langle\mathtt{x}\rangle$

as follows: The empty word is interpreted as $0$, and for non-empty words we
interpret the first letter as the sign and the rest of the word as the binary
expansion of the absolute value, e.g. $\mathtt{-111}$ represents $-7$. This
encoding is almost injective except that
$\varepsilon\equiv\mathtt{+0}\equiv\mathtt{-0}$. This non-uniqueness will
sometimes be convenient for us. If
$\mathtt{x}\in\mathtt{Num}_{\mathbb{Z}}\setminus\\{\varepsilon\\}$, then the
amount of memory used to store $\mathtt{x}$, i.e. its word length in the
alphabet $\Sigma_{\mathbb{Z}}$ is given by

$|\mathtt{x}|_{\Sigma_{\mathbb{Z}}}:=\lceil\log_{2}(|\langle\mathtt{x}\rangle|+1)\rceil+1,$

whereas $|\varepsilon|_{\Sigma_{\mathbb{Z}}}=0$. Given
$\mathtt{x}\in\Sigma_{\mathbb{Z}}$ we also write
$\|x\|:=|\mathtt{x}|_{\Sigma_{\mathbb{Z}}}$ and refer to $\|\mathtt{x}\|$ as
the _size_ of $\mathtt{x}$. The following is a standard elementary exercise in
the theory of computing.

######  Lemma A.1.

Let $\mathtt{x}_{1},\mathtt{x}_{2}\in\mathtt{Num}_{\mathbb{Z}}$. Then there
exist elements
$\mathtt{x}_{3}=:\mathtt{x}_{1}\oplus\mathtt{x}_{2}\in\mathtt{Num}_{\mathbb{Z}}$
and
$\mathtt{x}_{4}=:\mathtt{x}_{1}\ominus\mathtt{x}_{2}\in\mathtt{Num}_{\mathbb{Z}}$
of size
$\|\mathtt{x}_{3}\|,\|\mathtt{x}_{4}\|\leq\max\\{\|\mathtt{x}_{1}\|,\|\mathtt{x}_{2}\|\\}$
which can be computed in time
$O(\max\\{\|\mathtt{x}_{1}\|,\|\mathtt{x}_{2}\|\\}+1)$ and satisfy
$\langle\mathtt{x}_{3}\rangle=\langle\mathtt{x}_{1}\rangle+\langle\mathtt{x}_{2}\rangle$
and
$\langle\mathtt{x}_{4}\rangle=\langle\mathtt{x}_{1}\rangle-\langle\mathtt{x}_{2}\rangle$.
∎

######  Remark A.2.

Besides adding and subtracting integers, we also need to be able to decide
whether to given words in $\mathtt{Num}_{\mathbb{Z}}$ represent the same
integer. It turns out that equality can be checked in linear time. Indeed, for
words of length $\geq 3$ one just has to compare the words over
$\Sigma_{\mathbb{Z}}$. For shorter words the only relation one has to account
is the fact that $\mathtt{+0}\equiv\mathtt{-0}\equiv\varepsilon$, but this can
be checked in bounded time as well.