[nd]Ines Klimann, Matthieu Picantin, and Dmytro Savchuk Billy Editor, Bill
Editors2Conference title on which this volume is based on111
10.4230/LIPIcs.xxx.yyy.p

# A connected 3-state reversible Mealy automaton cannot generate an infinite
Burnside group 111This work was partially supported by the french _Agence
Nationale pour la Recherche_ , through the Project MealyM ANR-
JCJC-12-JS02-012-01. The third author was partially supported by the New
Researcher Grant from USF Internal Awards Program.

Ines Klimann  Univ Paris Diderot, Sorbonne Paris Cité, LIAFA, UMR 7089 CNRS,
F-75013 Paris, France<EMAIL_ADDRESS>Matthieu
Picantin  Univ Paris Diderot, Sorbonne Paris Cité, LIAFA, UMR 7089 CNRS,
F-75013 Paris, France<EMAIL_ADDRESS>Dmytro
Savchuk  Department of Mathematics and Statistics, University of South
Florida,
4202 E Fowler Ave – Tampa, FL 33620-5700, USA<EMAIL_ADDRESS>
###### Abstract.

The class of automaton groups is a rich source of the simplest examples of
infinite Burnside groups. However, there are some classes of automata that do
not contain such examples. For instance, all infinite Burnside automaton
groups in the literature are generated by non reversible Mealy automata and it
was recently shown that 2-state invertible-reversible Mealy automata cannot
generate infinite Burnside groups. Here we extend this result to connected
3-state invertible-reversible Mealy automata, using new original techniques.
The results provide the first uniform method to construct elements of infinite
order in each infinite group in this class.

###### Key words and phrases:

Burnside groups, reversible Mealy automata, automaton groups

##  1\. Mealy automata and the General Burnside problem

In 1902, Burnside has introduced a question which would become highly
influential in group theory [6]:

_Is a finitely generated group whose all elements have finite order
necessarily finite?_

This problem is now known as the _General Burnside Problem_. A group is
commonly called a _Burnside_ group if it is finitely generated and all its
elements have finite order.

In 1964, Golod and Shafarevich [12, 13] were the first ones to give a negative
answer to the general Burnside problem and around the same time Glushkov
suggested that groups generated by automata could serve as a different source
of counterexamples [11]. In 1972, Aleshin gave an answer as a subgroup of an
automaton group [2], and then in 1980, Grigorchuk exhibited the first and the
simplest by now example of an infinite Burnside automaton group [14]. Since
then many infinite Burnside automaton groups have been constructed [4, 15, 16,
22]. Even by now, the simplest examples of infinite Burnside groups are still
automaton groups.

All the examples of infinite Burnside automaton groups in the literature
happen to be generated by non-reversible invertible Mealy automata, that is,
invertible Mealy automata where all the letters do not act as permutations on
the stateset.

It was proved in [17] that a 2-state invertible-reversible Mealy automaton
cannot generate an infinite Burnside group, but the techniques were strongly
based on the fact that the stateset has size 2. Here we address this problem
for a larger class, namely the 3-state invertible-reversible automata, and
prove the following theorem.

######  Theorem 1.1.

A connected 3-state invertible-reversible Mealy automaton cannot generate an
infinite Burnside group.

For the proof of this theorem we develop new techniques, centered on the orbit
tree of the dual of the Mealy automaton. We hope that these techniques could
be further extended to attack similar problem for automata with bigger
statesets.

The class of groups generated by automata is very interesting from algorithmic
point of view. Even thought the word problem (given a word in generators
decide if it represents the trivial element of the group) is decidable, most
of other basic algorithmic questions, including finiteness problem, order
problem, conjugacy problem, are either known to be undecidable, or their
decidability is unknown. For example, it was proved recently that the order
problem is undecidable for automaton semigroups [10] and for groups generated
by, so called, asynchronous Mealy automata [5]. However, this problem still
remains open for the class of all groups generated by Mealy automata. There
are many partial methods to find elements of infinite order in such groups,
but the class of reversible automata is known as the class for which most of
these algorithms do not work or perform poorly. The proof of Theorem 1.1 gives
a uniform algorithm to produce many elements of infinite order in infinite
groups generated by 3-state invertible-reversible automata. Unfortunately, it
does not provide an algorithm that can determine if the group itself is
infinite, however, it is known that each invertible-reversible but not
bireversible automaton generates an infinite group [1].

The paper is organized as follows. In Section 2, we set up notation, provide
well-known definitions and facts concerning automaton groups and rooted trees.
Certain results concerning connected components of reversible Mealy automata
are given in Section 3. In Section 4 we introduce a crucial construction for
our proofs: the labeled orbit tree of a Mealy automaton. Finally, Section 5
contains the proof of our main results, including Theorem 1.1.

##  2\. Basic notions

###  2.1. Groups generated by Mealy automata

We first recall the formal definition of an automaton. A (finite,
deterministic, and complete) automaton is a triple
$\bigl{(}Q,\Sigma,\delta=(\delta_{i}\colon Q\rightarrow
Q)_{i\in\Sigma}\bigr{)}$, where the _stateset_ $Q$ and the _alphabet_ $\Sigma$
are non-empty finite sets, and where the $\delta_{i}$ are functions.

A _Mealy automaton_ is a quadruple $\bigl{(}Q,\Sigma,\delta=(\delta_{i}\colon
Q\rightarrow
Q)_{i\in\Sigma},\rho=(\rho_{x}\colon\Sigma\rightarrow\Sigma)_{x\in
Q}\bigr{)}$, such that both $(Q,\Sigma,\delta)$ and $(\Sigma,Q,\rho)$ are
automata. In other terms, a Mealy automaton is a complete, deterministic,
letter-to-letter transducer with the same input and output alphabet.

The graphical representation of a Mealy automaton is standard, see Figures 2
and 2.

$x$$y$$z$$\begin{array}[]{c}1|2\\\ 2|1\\\
3|4\end{array}$$4|3$$\begin{array}[]{c}4|1\\\
2|3\end{array}$$2|1$$4|3$$\begin{array}[]{c}1|2\\\
3|4\end{array}$$\begin{array}[]{c}1|2\\\ 3|4\end{array}$ Figure 1. An example
of a 4-letter 3-state
connected Mealy automaton.

$x$$y$$z$$\begin{array}[]{c}1|1\\\ 2|3\\\
3|2\end{array}$$3|3$$3|3$$\begin{array}[]{c}1|1\\\
2|2\end{array}$$\begin{array}[]{c}1|2\\\ 2|1\end{array}$ Figure 2. An example
of a 3-letter 3-state
disconnected Mealy automaton.

A Mealy automaton $(Q,\Sigma,\delta,\rho)$ is _invertible_ if the functions
$\rho_{x}$ are permutations of $\Sigma$ and _reversible_ if the functions
$\delta_{i}$ are permutations of $Q$.

In a Mealy automaton ${\mathcal{A}}=(Q,\Sigma,\delta,\rho)$, the sets $Q$ and
$\Sigma$ play dual roles. So we may consider the _dual (Mealy) automaton_
defined by ${\mathfrak{d}}({{\mathcal{A}}})=(\Sigma,Q,\rho,\delta)$.
Obviously, a Mealy automaton is reversible if and only if its dual is
invertible.

Let ${\mathcal{A}}=(Q,\Sigma,\delta,\rho)$ be a Mealy automaton. We view
${\mathcal{A}}$ as an automaton with an input and an output tape, thus
defining mappings from input words over $\Sigma$ to output words over
$\Sigma$. Formally, for $x\in Q$, the map
$\rho_{x}\colon\Sigma^{*}\rightarrow\Sigma^{*}$, extending
$\rho_{x}\colon\Sigma\rightarrow\Sigma$, is defined recursively by:

$\forall i\in\Sigma,\
\forall{\mathbf{s}}\in\Sigma^{*},\qquad\rho_{x}(i{\mathbf{s}})=\rho_{x}(i)\rho_{\delta_{i}(x)}({\mathbf{s}})\>.$

By convention, the image of the empty word is itself. The mapping $\rho_{x}$
for each $x\in Q$ is length-preserving and prefix-preserving. We say that
$\rho_{x}$ is the _production function_ associated with $({\mathcal{A}},x)$.
For ${\mathbf{x}}=x_{1}\cdots x_{n}\in Q^{n}$ with $n>0$, set
$\rho_{\mathbf{x}}\colon\Sigma^{*}\rightarrow\Sigma^{*},\rho_{\mathbf{x}}=\rho_{x_{n}}\circ\cdots\circ\rho_{x_{1}}\>$.

Denote dually by $\delta_{i}\colon Q^{*}\rightarrow Q^{*},i\in\Sigma$, the
production functions associated with the dual automaton
$\mathfrak{d}({\mathcal{A}})$. For ${\mathbf{s}}=s_{1}\cdots
s_{n}\in\Sigma^{n}$ with $n>0$, set $\delta_{\mathbf{s}}\colon
Q^{*}\rightarrow Q^{*},\
\delta_{\mathbf{s}}=\delta_{s_{n}}\circ\cdots\circ\delta_{s_{1}}$.

The semigroup of mappings from $\Sigma^{*}$ to $\Sigma^{*}$ generated by
$\\{\rho_{x},x\in Q\\}$ is called the _semigroup generated by ${\mathcal{A}}$_
and is denoted by $\langle{{{\mathcal{A}}}}\rangle_{+}$. When ${\mathcal{A}}$
is invertible, its production functions are permutations on words of the same
length and thus we may consider the group of mappings from $\Sigma^{*}$ to
$\Sigma^{*}$ generated by $\\{\rho_{x},x\in Q\\}$. This group is called the
_group generated by ${\mathcal{A}}$_ and is denoted by
$\langle{{\mathcal{A}}}\rangle$.

Let us recall some known results that will be used in our proofs.

######  Proposition 2.1 (see, for example, [1]).

An invertible Mealy automaton generates a finite group if and only if it
generates a finite semigroup.

######  Proposition 2.2 ([1, 20, 21]).

A Mealy automaton generates a finite (semi)group if and only if so does its
dual.

As in the case of automata, there is a notion of minimization for Mealy
automata: if several states have the same action, it consists of keeping only
one of them. More formally, for a Mealy automaton
${\mathcal{A}}=(Q,\Sigma,\delta,\rho)$, the _Nerode equivalence $\equiv$ on
$Q$_ is the limit of the sequence of increasingly finer equivalences
$(\equiv_{k})$ recursively defined by:

$\displaystyle\forall x,y\in Q\colon\qquad\qquad x\equiv_{0}y$ $\displaystyle\
\Longleftrightarrow\ \forall i\in\Sigma\colon\rho_{x}(i)=\rho_{y}(i)\>,$
$\displaystyle\forall k\geqslant 0\colon x\equiv_{k+1}y$ $\displaystyle\
\Longleftrightarrow\ \bigl{(}x\equiv_{k}y\quad\wedge\quad\forall
i\in\Sigma\colon\delta_{i}(x)\equiv_{k}\delta_{i}(y)\bigr{)}\>.$

Since the set $Q$ is finite, this sequence is ultimately constant. The
_minimization_ of ${\mathcal{A}}$ is then the Mealy automaton
$\mathfrak{m}({\mathcal{A}})=(Q/\mathord{\equiv},\Sigma,\tilde{\delta},\tilde{\rho})$,
where for every $(x,i)$ in $Q\times\Sigma$, we have
$\tilde{\delta}_{i}([x])=[\delta_{i}(x)]$ and $\tilde{\rho}_{[x]}=\rho_{x}$.

If the minimizations of two invertible Mealy automata are structurally
isomorphic, these automata generate two isomorphic groups. Moreover, the
following lemma is straightforward:

######  Lemma 2.3.

Let ${\mathcal{A}}$ be an invertible Mealy automaton. If there exist $p<q$
such that $\mathfrak{m}({\mathcal{A}}^{p})$ and
$\mathfrak{m}({\mathcal{A}}^{q})$ are isomorphic, then ${\mathcal{A}}$
generates a finite group.

###  2.2. Terminology on trees

Throughout this paper, we will use different sorts of labeled trees. Here we
set up some terminology that are common for all of them.

All our trees are rooted, _i.e._ with a selected vertex called the _root_. We
will visualize the trees traditionally as growing down from the root. Hence,
the “top” and “bottom” directions in the tree are defined as “to” and “from”
the root respectively. It will be convenient to orient all edges in the tree
in the direction from the root. The initial vertex of an edge $e$ is denoted
by $\top(e)$ and its terminal vertex by $\bot(e)$. A _path_ is a (possibly
infinite) sequence of adjacent edges without backtracking from top to bottom.
A path is said to be  _initial_ if it starts at the root of the tree. A
_branch_ is an infinite initial path. The initial vertex of a non-empty path
${\mathbf{e}}$ is denoted by $\top({\mathbf{e}})$ and its terminal vertex by
$\bot({\mathbf{e}})$

The _level of a vertex_ is its distance to the root and the _level of an edge_
or _a path_ is the level of its initial vertex. For $V$ a vertex in a tree
${\mathcal{T}}$, by _section of ${\mathcal{T}}$ at $V$_ (denoted by
${\mathcal{T}}_{|V}$) we mean the subtree of ${\mathcal{T}}$ with root $V$
consisting of all those vertices of ${\mathcal{T}}$ that are descendant of
$V$. Additionally, for ${\mathbf{e}}$ an initial finite path of
${\mathcal{T}}$, we also call ${\mathcal{T}}_{|\bot({\mathbf{e}})}$ the
_section of ${\mathcal{T}}$ at ${\mathbf{e}}$_ and denote it by
${\mathcal{T}}_{|{\mathbf{e}}}$.

Whenever one considers a rooted tree whose edges are labeled by elements of a
finite set, the _label_ of a (possibly infinite) path is the ordered sequence
of labels of the edges of this path.

##  3\. Powers of a Mealy automaton and their connected components

In this section we detail the basic properties of the connected components of
the powers of a reversible Mealy automaton. The link between these components
is central in our construction.

Note that some of the notions below may be defined in a more general
framework, but as in this paper we work only with reversible automata, we
restrict our attention to this case in order to make the explanations easier.

Let ${\mathcal{A}}=(Q,\Sigma,\delta,\rho)$ be a reversible Mealy automaton. We
will consider the connected components of the underlying graph of
${\mathcal{A}}$. By reversibility, all the connected components are strongly
connected. One can also view the connected components of ${\mathcal{A}}$ as
the orbits of the action of the group
$\langle{{\mathfrak{d}}({{\mathcal{A}}})}\rangle$ generated by the dual
automaton on $Q$.

Now, in order to construct the orbit tree of
${\mathfrak{d}}({{\mathcal{A}}})$, we will consider the connected components
of the powers of ${\mathcal{A}}$: for $n>0$, its _$n$ -th power_
${\mathcal{A}}^{n}$ is the Mealy automaton

${\mathcal{A}}^{n}=\bigl{(}\ Q^{n},\Sigma,(\delta_{i}\colon Q^{n}\rightarrow
Q^{n})_{i\in\Sigma},(\rho_{{\mathbf{x}}}\colon\Sigma\rightarrow\Sigma)_{{\mathbf{x}}\in
Q^{n}}\ \bigr{)}\enspace.$

By convention, ${\mathcal{A}}^{0}$ is the trivial automaton on a singleton
stateset and the alphabet $\Sigma$.

The powers of the reversible Mealy automaton ${\mathcal{A}}$ are reversible
and the connected components of ${\mathcal{A}}^{n}$ coincide with the orbits
of the action of $\langle{{\mathfrak{d}}({{\mathcal{A}}})}\rangle$ on $Q^{n}$.

######  Definition 3.1.

The _connection degree_ of a Mealy automaton ${\mathcal{A}}$, denoted by
$\curlywedge({{\mathcal{A}}})$, is the largest $n$ such that
${\mathcal{A}}^{n}$ is connected. If ${\mathcal{A}}$ is not connected, its
connection degree is 0; if all the powers of ${\mathcal{A}}$ are connected,
its connection degree is infinite.

Note that a connection degree of ${\mathcal{A}}$ is infinite if and only if
the group $\langle{{\mathfrak{d}}({{\mathcal{A}}})}\rangle$ acts level-
transitively on the tree $Q^{*}$ (_i.e._ the action of
$\langle{{\mathfrak{d}}({{\mathcal{A}}})}\rangle$ on each level $Q^{n}$ of
$Q^{*}$ is transitive).

Since ${\mathcal{A}}$ is reversible, there is a very particular connection
between the connected components of ${\mathcal{A}}^{n}$ and the connected
components of ${\mathcal{A}}^{n+1}$ as highlighted in [17]. More precisely,
suppose that ${\mathcal{C}}$ is a connected component of ${\mathcal{A}}^{n}$
for some $n$ and that ${\mathbf{u}}\in Q^{n}$ is a state of ${\mathcal{C}}$.
Let also $x\in Q$ be a state of ${\mathcal{A}}$ and ${\mathcal{D}}$ be a
connected component of ${\mathcal{A}}^{n+1}$ containing the state
${\mathbf{u}}x$. Then, for any state ${\mathbf{v}}$ of ${\mathcal{C}}$, there
exists a state of ${\mathcal{D}}$ prefixed with ${\mathbf{v}}$:

$\exists{\mathbf{s}}\in\Sigma^{*}\mid\delta_{{\mathbf{s}}}({\mathbf{u}})={\mathbf{v}}\quad\text{and
so}\quad\delta_{{\mathbf{s}}}({\mathbf{u}}x)={\mathbf{v}}\delta_{\rho_{{\mathbf{u}}}({\mathbf{s}})}(x)\enspace.$

Furthermore, if ${\mathbf{u}}y$ is a state of ${\mathcal{D}}$, for some state
$y\in Q$ different from $x$, then $\delta_{{\mathbf{s}}}({\mathbf{u}}x)$ and
$\delta_{{\mathbf{s}}}({\mathbf{u}}y)$ are two different states of
${\mathcal{D}}$ prefixed with ${\mathbf{v}}$, because of the reversibility of
${\mathcal{A}}^{n+1}$: the transition function
$\delta_{\rho_{{\mathbf{u}}}({\mathbf{s}})}$ is a permutation.

Hence ${\mathcal{D}}$ can be seen as consisting of several full copies of
${\mathcal{C}}$ and $\\#{\mathcal{C}}$ divides $\\#{\mathcal{D}}$. They have
the same size if and only if, once fixed some state ${\mathbf{u}}$ of
${\mathcal{C}}$, for any different states $x,y\in Q$, ${\mathbf{u}}x$ and
${\mathbf{u}}y$ cannot both belong to ${\mathcal{D}}$.

If from a connected component ${\mathcal{C}}$ of ${\mathcal{A}}^{n}$, we
obtain several connected components of ${\mathcal{A}}^{n+1}$, we say that
${\mathcal{C}}$ _splits up_.

The connected components of the powers of a Mealy automaton and the questions
of the finiteness of the generated group or the existence of a monogenic
subgroup are closely related, as shown in the following propositions (obtained
also independently in [7]).

######  Proposition 3.2.

An invertible-reversible Mealy automaton generates a finite group if and only
if the connected components of its powers have bounded size.

######  Proof 3.3.

Let ${\mathcal{A}}$ be an invertible-reversible Mealy automaton.

Let ${\mathcal{C}}$ be a connected component of some ${\mathcal{A}}^{n}$, and
${\mathbf{u}},{\mathbf{v}}$ two states of ${\mathcal{C}}$: because of the
reversibility of ${\mathcal{A}}^{n}$, ${\mathbf{v}}$ is the image of
${\mathbf{u}}$ by the action of an element of
$\langle{{\mathfrak{d}}({{\mathcal{A}}})}\rangle$. If ${\mathcal{A}}$
generates a finite group, so does ${\mathfrak{d}}({{\mathcal{A}}})$ by
Proposition 2.2, and hence $\\#{\mathcal{C}}$ is bounded by
$\\#\langle{{\mathfrak{d}}({{\mathcal{A}}})}\rangle$.

Conversely, if the connected components of the powers of ${\mathcal{A}}$ have
bounded size, as there is only a finite number of Mealy automata of bounded
size, there exist $p<q$ such that $\mathfrak{m}({\mathcal{A}}^{p})$ and
$\mathfrak{m}({\mathcal{A}}^{q})$ are isomorphic, and therefore
${\mathcal{A}}$ generates a finite group from Lemma 2.3.

######  Proposition 3.4.

Let ${\mathcal{A}}=(Q,\Sigma,\delta,\rho)$ be an invertible-reversible Mealy
automaton and let ${\mathbf{u}}\in Q^{+}$ be a non-empty word. The following
conditions are equivalent:

  1. (i)

$\rho_{{\mathbf{u}}}$ has finite order,

  2. (ii)

the sizes of the connected components of
$({\mathbf{u}}^{n})_{n\in{\mathbb{N}}}$ are bounded,

  3. (iii)

there exists a word ${\mathbf{v}}$ such that the sizes of the connected
components of $({\mathbf{vu}}^{n})_{n\in{\mathbb{N}}}$ are bounded,

  4. (iv)

for any word ${\mathbf{v}}$, the sizes of the connected components of
$({\mathbf{vu}}^{n})_{n\in{\mathbb{N}}}$ are bounded.

######  Proof 3.5.

(ii)$\Rightarrow$(iii), (iv)$\Rightarrow$(ii), and (iv)$\Rightarrow$(iii) are
immediate.

(i)$\Rightarrow$(ii) is a direct consequence of Proposition 3.2: let $k$ be
the order of $\rho_{{\mathbf{u}}}$; it means that ${\mathbf{u}}^{k}$ acts as
the identity, and so do all the states of its connected component. By
Proposition 3.2, the connected components of the $({\mathbf{u}}^{kn})_{n}$
have bounded size, which leads to (ii).

(iii)$\Rightarrow$(i): for each $n$, denote by ${\mathcal{C}}_{n}$ the
connected component of ${\mathbf{vu}}^{n}$. As the sizes of these components
are bounded, the sequence $({\mathcal{C}}_{n})_{n}$ admits a subsequence which
all elements are the same, up to state numbering. Within this subsequence,
there are two elements such that two different words ${\mathbf{vu}}^{*}$ name
the same state, say ${\mathbf{vu}}^{p}$ and ${\mathbf{vu}}^{q}$, which means
that $\rho_{{\mathbf{vu}}^{p}}=\rho_{{\mathbf{vu}}^{q}}$, and
$\rho_{{\mathbf{u}}}$ has finite order.

(ii)$\Rightarrow$(iv): the size of the connected component of
${\mathbf{vu}}^{n}$ is at most $\\#\Sigma^{|{\mathbf{v}}|}$ times the size of
the connected component of ${\mathbf{u}}^{n}$.

##  4\. The Labeled Orbit Tree

In this section, we build a tree capturing the links between the connected
components of consecutive powers of a Mealy automaton. An example of the first
levels of such a tree is given in Figure 3.

Let ${\mathcal{A}}=(Q,\Sigma,\delta,\rho)$ be an invertible-reversible Mealy
automaton. Consider the tree with vertices the connected components of the
powers of ${\mathcal{A}}$, and the incidence relation built by adding an
element of $Q$: for any $n\geq 0$, the connected component of ${\mathbf{u}}\in
Q^{n}$ is linked to the connected component(s) of ${\mathbf{u}}x$, for any
$x\in Q$. This tree is called the _orbit tree_ of
${\mathfrak{d}}({{\mathcal{A}}})$ [9]. It can be seen as the quotient of the
tree $Q^{*}$ under the action of the group
$\langle{{\mathfrak{d}}({{\mathcal{A}}})}\rangle$.

We label any edge ${\mathcal{C}}\to{\mathcal{D}}$ of the orbit tree by the
ratio $\frac{\\#{\mathcal{D}}}{\\#{\mathcal{C}}}$, which is always an integer
by the reversibility of ${\mathcal{A}}$. We call this labeled tree the
_labeled orbit tree_ of ${\mathfrak{d}}({{\mathcal{A}}})$. In [9], in the
definition of the labeled orbit tree, each vertex is labeled by the size of
the associated connected component, which encodes exactly the same information
as our relative labeling, as the root has size one. We denote by
$\mathfrak{t}{({\mathcal{A}})}$ the labeled orbit tree of
${\mathfrak{d}}({{\mathcal{A}}})$. Note that for each vertex of
$\mathfrak{t}{({\mathcal{A}})}$ the sum of the labels of all edges going down
from this vertex always equals to the number of states in ${\mathcal{A}}$.

vertex ${\Lambda}$vertex ${\mathcal{O}}_{2}$edge
$e_{2}$$\curlywedge\leavevmode\nobreak\
$11111112222221111111211211121112111111222111112211121212211112121221211211212221112222111222212111212122211221221111211211132221111111311111121112111

Figure 3. The labeled orbit tree of the Mealy automaton of Figure 2 (up to
level 7).

From now on we will assume that all the orbit trees are labeled.

Let ${\mathbf{u}}$ be a (possibly infinite) word over $Q$. The _path of_
${\mathbf{u}}$ in the orbit tree $\mathfrak{t}{({\mathcal{A}})}$ is the unique
initial path going from the root through the connected components of the
prefixes of ${\mathbf{u}}$; ${\mathbf{u}}$ can be called _a representative_ of
this initial path (or of the orbit of ${\mathbf{u}}$ under
$\langle\mathfrak{d}({\mathcal{A}})\rangle$ representing the endpoint of this
path); we can say equivalently that this path is _represented_ by
${\mathbf{u}}$.

######  Definition 4.1.

Let $e$ and $f$ be two edges in the orbit tree
$\mathfrak{t}{({\mathcal{A}})}$. We say that $e$ _is liftable to_ $f$ if each
word of $\bot(e)$ admits some word of $\bot(f)$ as a suffix.

Obviously if $e$ is liftable to $f$, then $f$ is closer to the root of the
orbit tree. The fact that an edge is liftable to another one reflects a deeper
relation stated below. The following lemma is one of the key observations that
we use many times later in the paper.

######  Lemma 4.2.

Let $e$ and $f$ be two edges in the orbit tree
$\mathfrak{t}{({\mathcal{A}})}$. If $e$ is liftable to $f$, then the label of
$e$ is less than or equal to the label of $f$.

######  Proof 4.3.

Since $e$ is liftable to $f$, each word in $\bot(e)$ has a form
${\mathbf{vu}}x$ for some ${\mathbf{u}}x\in\bot(f)$. Suppose that
${\mathbf{vu}}x$ and ${\mathbf{vu}}y$ are in the same connected component:
there exists ${\mathbf{s}}\in\Sigma^{*}$ such that $\delta_{{\mathbf{s}}}$
moves ${\mathbf{vu}}x$ to ${\mathbf{vu}}y$. In this case,
$\rho_{{\mathbf{v}}}({\mathbf{s}})$ moves ${\mathbf{u}}x$ to ${\mathbf{u}}y$.
Thus, the number of children of ${\mathbf{vu}}$ in the connected component of
${\mathbf{vu}}x$ (which is equal to the label of $e$) is less than or equal to
the number of children of ${\mathbf{u}}$ in the connected component of
${\mathbf{u}}x$ (which is equal to the label of $f$).

This notion can be generalized to paths:

######  Definition 4.4.

Let ${\mathbf{e}}=(e_{i})_{i\in I}$ and ${\mathbf{f}}=(f_{i})_{i\in I}$ be two
paths of the same (possibly infinite) length in the orbit tree
$\mathfrak{t}{({\mathcal{A}})}$. The path ${\mathbf{e}}$ _is liftable to_ the
path ${\mathbf{f}}$ if, for any $i\in I$, the edge $e_{i}$ is liftable to the
edge $f_{i}$.

As each word ${\mathbf{u}}\in Q^{*}$ is a state in a connected component of
${\mathcal{A}}^{|{\mathbf{u}}|}$, we can notice the following fact which is
crucial for all our forthcoming proofs.

######  Lemma 4.5.

Let ${\mathbf{e}}$ be a path at level $k$ in the orbit tree
$\mathfrak{t}{({\mathcal{A}})}$. Then, for any $\ell<k$, ${\mathbf{e}}$ is
liftable to some path at level $\ell$. In particular, ${\mathbf{e}}$ is
liftable to some initial path.

##  5\. Main result

We study here the case where ${\mathcal{A}}$ is a connected invertible-
reversible 3-state Mealy automaton, which means that the orbit tree of its
dual has a unique edge adjacent to the root, labeled by 3. We prove that if
${\mathcal{A}}$ generates an infinite group, then the orbit tree
$\mathfrak{t}{({\mathcal{A}})}$ admits a (necessarily unique) branch without
edges labeled by 1, more precisely a branch of label either $3^{\omega}$ or
$3^{n}2^{\omega}$, where $i^{\omega}$ denotes an infinite word whose each
letter is $i$. An element of infinite order will then be constructed using
this branch.

The restriction to connected Mealy automata is discussed in Remark 5.27.

###  5.1. General structure of the orbit tree

From Lemma 4.5, we obtain the following result on the connection degree of a
Mealy automaton (note that it does not depend on the number of states in the
Mealy automaton):

######  Proposition 5.1.

If for some $n$, a connected component of ${\mathcal{A}}^{n}$ does not split
up, then the connection degree of ${\mathcal{A}}$ is at least $n+1$.

######  Proof 5.2.

Suppose that ${\mathcal{A}}$ has $m$ states. If an edge at level $n$ in the
orbit tree $\mathfrak{t}{({\mathcal{A}})}$ has label $m$, by Lemma 4.5, it is
liftable to some edge at any level above $n$, and by Lemma 4.2 this edge is
labeled by $m$. Now, by going from top to bottom, we can conclude that there
is only one edge at each level above $n+1$ in the orbit tree.

Now we restrict our attention again on the case of 3-state automata, unless
specified otherwise. If the connection degree of such an automaton
${\mathcal{A}}$ is infinite, it has been proved in [17, Proposition 14] that
the generated semigroup is free, freely generated by the states of the Mealy
automaton. As a consequence ${\mathcal{A}}$ cannot generate an infinite
Burnside group in this case. So from now on, we assume
$0<\curlywedge({{\mathcal{A}}})<\infty$.

We know now that the orbit tree $\mathfrak{t}{({\mathcal{A}})}$ has a prefix
linear part until level $\curlywedge({{\mathcal{A}}})$ and that below this
level, all the vertices split up. We denote by ${\Lambda}({{\mathcal{A}}})$
the highest vertex to split up (_i.e._ the only vertex at level
$\curlywedge({{\mathcal{A}}})$).

######  Definition 5.3.

Let ${\mathbf{i}}$ be a (possibly infinite) word over an alphabet $F$ and let
$j\in F$. A $j$-block ${\mathbf{j}}$ of ${\mathbf{i}}$ is a maximal factor of
${\mathbf{i}}$ in $j^{*}\cup\\{j^{\omega}\\}$, that is,
${\mathbf{i}}={\mathbf{k}}{\mathbf{j}}{\mathbf{l}}$ holds, where the last
letter of ${\mathbf{k}}$ and the first letter of ${\mathbf{l}}$, if not empty,
are not $j$.

######  Lemma 5.4.

If the lengths of the 2-blocks in the orbit tree
$\mathfrak{t}{({\mathcal{A}})}$ are not bounded, then
$\mathfrak{t}{({\mathcal{A}})}$ admits a branch labeled by
$3^{\curlywedge({{\mathcal{A}}})}2^{\omega}$. If the lengths of the 2-blocks
are bounded with supremum $N$, then $\mathfrak{t}{({\mathcal{A}})}$ admits an
initial path labeled by $3^{\curlywedge({{\mathcal{A}}})}2^{N}$ (and none
labeled by $3^{\curlywedge({{\mathcal{A}}})}2^{N+1}$).

######  Proof 5.5.

As there is at most one path starting at ${\Lambda}({{\mathcal{A}}})$ with a
maximal prefix in $2^{\omega}$ because the stateset has size 3, Lemma 4.5
leads to the conclusion.

By Proposition 5.1, below the connection degree of ${\mathcal{A}}$, no edge
can be labeled by 3. On the other hand, the case when all edges are labeled by
1 turns out to be irrelevant for generating infinite Burnside groups,according
to the following proposition (that holds for automata with arbitrary number of
states).

######  Proposition 5.6.

If all edges coming down from the only connected component at vertex
${\Lambda}({{\mathcal{A}}})$ are labeled by 1, the group generated by
${\mathcal{A}}$ is finite.

######  Proof 5.7.

By Lemmas 4.2 and 4.5, below level $\curlywedge({{\mathcal{A}}})$, all edges
are then labeled by $1$, which means that the connected components of the
powers of ${\mathcal{A}}$ have bounded size, and the group
$\langle{{\mathcal{A}}}\rangle$ is finite according to Proposition 3.2.

From now on, we assume that the only connected component at vertex
${\Lambda}({{\mathcal{A}}})$ splits up in two connected components.

###  5.2. Reduction edge and orbital words

Let us recall our framework: ${\mathcal{A}}$ is a connected 3-state
invertible-reversible Mealy automaton with
$0<\curlywedge({{\mathcal{A}}})<\infty$, such that the only connected
component at vertex ${\Lambda}({{\mathcal{A}}})$ splits up in two connected
components. The point is now to put the emphasize on the larger of the two.

######  Definition 5.8.

At level $\curlywedge({{\mathcal{A}}})$ there are two edges, one labeled by 1
and a second one labeled by 2. We call by the _reduction edge_ this last edge
and denote it by $e_{2}$, and denote by ${\cal O}_{2}$ its terminal vertex,
and call it the _reduction orbit_.

######  Lemma 5.9.

Each vertex below the level $\curlywedge({{\mathcal{A}}})+1$ is the initial
vertex of either one edge which is liftable to the reduction edge and one edge
which is not, or two edges which are liftable to the reduction edge and one
which is not.

######  Definition 5.10.

An _$e_{2}$ -liftable path_ is an initial (possibly infinite) path in the
orbit tree whose edges below the level $\curlywedge({{\mathcal{A}}})$ are all
liftable to the reduction edge $e_{2}$ of $\mathfrak{t}{({\mathcal{A}})}$.

######  Definition 5.11.

A word over $Q$ is said to be  _orbital_ if it is a representative of an
$e_{2}$-liftable path or, equivalently, if all its length
$\curlywedge({{\mathcal{A}}})$ factors belong to the reduction orbit ${\cal
O}_{2}$. Denote then by $T_{{\cal O}_{2}}$ the set of all finite orbital
words. Being prefix-closed, $T_{{\cal O}_{2}}$ can be seen either as a set of
words, or as a tree.

Note that $T_{{\cal O}_{2}}$ is a strictly
($\curlywedge({{\mathcal{A}}})$+1)-testable language [18]. In particular, for
any word ${\mathbf{u}}\in T_{{\cal O}_{2}}$ of length at least
$\curlywedge({{\mathcal{A}}})$, the set of words ${\mathbf{v}}$ such that
${\mathbf{uv}}$ belongs to $T_{{\cal O}_{2}}$ depends only on the length
$\curlywedge({{\mathcal{A}}})$ suffix of ${\mathbf{u}}$. A simple consequence
is that $T_{{\cal O}_{2}}$ viewed as a set of infinite words is factor-closed.
Further, up to level $\curlywedge({{\mathcal{A}}})$, the tree $T_{{\cal
O}_{2}}$ coincides with $Q^{*}$ and each word of length at least
$\curlywedge({{\mathcal{A}}})$ is a prefix of exactly two other words in
$T_{{\cal O}_{2}}$.

We now state several technical results about the tree $T_{{\cal O}_{2}}$ of
orbital words which will be of use in the final subsection.

######  Lemma 5.12.

For any two words ${\mathbf{u}},{\mathbf{v}}$ in $T_{{\cal O}_{2}}$ and any
integer $n$, there exists a word ${\mathbf{r}}\in Q^{n}$ satisfying
${\mathbf{u}}{\mathbf{r}}\in T_{{\cal O}_{2}}$ and
${\mathbf{v}}{\mathbf{r}}\in T_{{\cal O}_{2}}$.

######  Proof 5.13.

For any word ${\mathbf{w}}\in T_{{\cal O}_{2}}$, there exist (at least) two
different states $q_{1},q_{2}\in{Q}$ satisfying
${\mathbf{w}}q_{1},{\mathbf{w}}q_{2}\in T_{{\cal O}_{2}}$. As the stateset $Q$
has size 3, there is at least one common state $r_{1}\in Q$ satisfying
${\mathbf{u}}r_{1}\in T_{{\cal O}_{2}}$ and ${\mathbf{v}}r_{1}\in T_{{\cal
O}_{2}}$. The result is then obtained by recursion.

######  Lemma 5.14.

Let $x\in Q$ and ${\mathbf{u}}\in Q^{\curlywedge({{\mathcal{A}}})}$. The set
of length $\curlywedge({{\mathcal{A}}})$ suffixes of all words in the
connected component of $x{\mathbf{u}}$ is the whole
$Q^{\curlywedge({{\mathcal{A}}})}$.

######  Proof 5.15.

Since ${\mathcal{A}}$ is reversible and
${\mathcal{A}}^{\curlywedge({{\mathcal{A}}})}$ connected, for each
${\mathbf{v}}\in{Q}^{\curlywedge({{\mathcal{A}}})}$, there exists
${\mathbf{s}}\in\Sigma^{*}$ such that
$\delta_{{\mathbf{s}}}({\mathbf{u}})={\mathbf{v}}$. By the invertibility of
${\mathcal{A}}$, ${\mathbf{t}}=\rho_{x}^{-1}({\mathbf{s}})$ is well defined
and we have

$\delta_{{\mathbf{t}}}(x{\mathbf{u}})=\delta_{{\mathbf{t}}}(x)\delta_{\rho_{x}({\mathbf{t}})}({\mathbf{u}})=\delta_{{\mathbf{t}}}(x)\delta_{{\mathbf{s}}}({\mathbf{u}})=\delta_{{\mathbf{t}}}(x){\mathbf{v}}\>.$

######  Proposition 5.16.

For any orbital word ${\mathbf{u}}$, there are infinitely many edges in
${T_{{\cal O}_{2}}}_{|{{\mathbf{u}}}}$ labeled by each state.

######  Proof 5.17.

By contradiction. Denote the stateset $Q=\\{x,y,z\\}$ and let ${\mathbf{u}}$
be an orbital word (of length at least $\curlywedge({{\mathcal{A}}})$) such
that no edge of ${T_{{\cal O}_{2}}}_{|{{\mathbf{u}}}}$ is labeled by $z$.

As each word of $T_{{\cal O}_{2}}$ can be extended in $T_{{\cal O}_{2}}$ by
two different states, $x$ and $y$ are in ${T_{{\cal
O}_{2}}}_{|{{\mathbf{u}}}}$. By recursion, $\\{x,y\\}^{*}$ is a subset of
${T_{{\cal O}_{2}}}_{|{{\mathbf{u}}}}$ and, as $T_{{\cal O}_{2}}$ is suffix-
closed, $\\{x,y\\}^{*}\subseteq T_{{\cal O}_{2}}$. Let
${\mathbf{v}}\in\\{x,y\\}^{\curlywedge({{\mathcal{A}}})-1}$: $x{\mathbf{v}}$
and $y{\mathbf{v}}$ are elements of $T_{{\cal O}_{2}}$ and $x{\mathbf{v}}x$,
$x{\mathbf{v}}y$, $y{\mathbf{v}}x$, and $y{\mathbf{v}}y$ are in ${\cal
O}_{2}$. Hence $x{\mathbf{v}}z$ and $y{\mathbf{v}}z$ have length
$\curlywedge({{\mathcal{A}}})+1$ and are not in ${\cal O}_{2}$. In this case
both these words must belong to the other connected component of size
$3^{\curlywedge({{\mathcal{A}}})}$.

By Lemma 5.14, the connected component of $x{\mathbf{v}}z$ will have at least
$3^{\curlywedge({{\mathcal{A}}})}$ words with different suffixes starting from
position $2$. Therefore, if we assume that $y{\mathbf{v}}z$ is also in this
component, we must have at least $3^{\curlywedge({{\mathcal{A}}})}+1$ words in
there. Contradiction.

###  5.3. Cyclically orbital words and elements of infinite order

In this subsection, in the case when the lengths of the 2-blocks in the orbit
tree are bounded, we exhibit a family of words whose induced actions have
finite bounded orders. Then we prove that each word admits a bounded power
which induces the same action as some word in this family.

######  Definition 5.18.

A word over $Q$ is said to be  _cyclically orbital_ if each of its powers is
orbital. In other words, a word is cyclically orbital if viewed as a cyclic
word it is orbital.

Note that the existence of such cyclically orbital words is ensured by the
straightforward fact that any orbital word of length
$\curlywedge({{\mathcal{A}}})\times(1+\\#Q^{\curlywedge({{\mathcal{A}}})})$
admits a cyclically orbital factor.

To prove the first result about cyclically orbital words we will need the
following proposition.

######  Proposition 5.19.

If the lengths of the 2-blocks in $\mathfrak{t}{({\mathcal{A}})}$ are bounded
with supremum $N$, then each edge from level $\curlywedge({{\mathcal{A}}})+N$
or below in an $e_{2}$-liftable path is followed by three edges.

######  Proof 5.20.

From Lemma 5.4, there is an initial path labeled by
$3^{\curlywedge({{\mathcal{A}}})}2^{N}$ (and none labeled by
$3^{\curlywedge({{\mathcal{A}}})}2^{N+1}$). As the stateset has size 3, this
path is unique, call it ${\mathbf{e}}$: $\bot({\mathbf{e}})$ is the initial
vertex of 3 edges, two of which are liftable to the reduction edge by Lemma
5.9.

We now consider the subtree ${\mathfrak{s}}$ of
$\mathfrak{t}{({\mathcal{A}})}$ consisting of all $e_{2}$-liftable paths. By
Lemma 5.9, each path of ${\mathfrak{s}}$ is either a prefix of ${\mathbf{e}}$
or prefixed with ${\mathbf{e}}$. Suppose that one of the edges of
${\mathfrak{s}}$ below level $|{\mathbf{e}}|+1$ is labeled by 2 and consider
an initial branch ${\mathbf{f}}$ in ${\mathfrak{s}}$ which minimizes the
length of the 1-block from $\bot({\mathbf{e}})$: its label has prefix
$3^{\curlywedge({{\mathcal{A}}})}2^{N}1^{k}2$ for some $k>0$. Consider the
(non-initial) path in $\mathfrak{t}{({\mathcal{A}})}$ obtained from
${\mathbf{f}}$ by erasing the first edge: by Lemma 4.5, it is liftable to an
initial path, say ${\mathbf{g}}$. As ${\mathbf{f}}$ is an $e_{2}$-liftable
path, so is ${\mathbf{g}}$, hence ${\mathbf{g}}$ coincides necessarily with
${\mathbf{e}}$ until level $\curlywedge({{\mathcal{A}}})+N$; so the label of
${\mathbf{g}}$ has prefix $3^{\curlywedge({{\mathcal{A}}})}2^{N}$. By Lemmas
4.2 and 4.5, it has also a prefix whose label is greater than or equal to
(coordinatewise) $3^{\curlywedge({{\mathcal{A}}})-1}2^{N}1^{k}2$. Hence the
label of ${\mathbf{g}}$ has a prefix greater than or equal to
$3^{\curlywedge({{\mathcal{A}}})}2^{N}1^{k-1}2$, which is in contradiction
with the choice of ${\mathbf{f}}$.

######  Proposition 5.21.

If the lengths of the 2-blocks in $\mathfrak{t}{({\mathcal{A}})}$ are bounded,
any cyclically orbital word induces an action of finite order, bounded by a
constant not depending on the word.

######  Proof 5.22.

Let ${\mathbf{u}}$ be a cyclically orbital word and $n$ be an integer such
that $|{\mathbf{u}}^{n}|>\curlywedge({{\mathcal{A}}})$. By the definition,
${\mathbf{u}}^{n}$ is a representative of some $e_{2}$-liftable path. So, by
Lemma 5.4, the label of the path of ${\mathbf{u}}^{\omega}$ is ultimately 1
and, by Proposition 3.2, the action induced by ${\mathbf{u}}$ has finite
order, bounded by a constant which depends on $\curlywedge({{\mathcal{A}}})$
(more precisely on how many ways one can choose the outputs for a Mealy
automaton with the same structure as $\bot({\mathbf{e}})$ where ${\mathbf{e}}$
is the path of $\mathfrak{t}{({\mathcal{A}})}$ defined in the proof of
Proposition 5.19).

######  Proposition 5.23.

If the lengths of the 2-blocks in $\mathfrak{t}{({\mathcal{A}})}$ are bounded,
any non-empty word over $Q$ admits a non-empty bounded power which is
equivalent to a cyclically orbital word.

######  Proof 5.24.

Let $\curlywedge=\curlywedge({{\mathcal{A}}})$ be the connection degree of
${\mathcal{A}}$. For a (possibly infinite) word ${\mathbf{w}}\in T_{{\cal
O}_{2}}$, let denote the (finite) set of its length $\curlywedge$ factors.

Consider an infinite word ${\mathbf{u}}\in T_{{\cal O}_{2}}$, that we assume
to be _maximal_ in the sense that there is no other infinite word
${\mathbf{u^{\prime}}}\in T_{{\cal O}_{2}}$ satisfying . Let fix a finite
prefix ${\mathbf{v}}$ of ${\mathbf{u}}$ satisfying . From the maximality
assumption on ${\mathbf{u}}$, we deduce that each ${\mathbf{w}}\in{T_{{\cal
O}_{2}}}_{|{{\mathbf{v}}}}$ (where ${T_{{\cal O}_{2}}}_{|{{\mathbf{v}}}}$,
viewed as a set of words, consists of words ${\mathbf{w}}$ over $Q$ such that
${\mathbf{vw}}\in T_{{\cal O}_{2}}$) satisfies . We will refer to this
property as Property (${\natural}$).

Let $a_{1}a_{2}\dots a_{n}\in Q^{+}$. By Proposition 5.16, $a_{1}$ appears
infinitely many often in the tree ${T_{{\cal O}_{2}}}_{|{{\mathbf{v}}}}$.
Therefore there is some word ${\mathbf{u_{0}}}$ satisfying
${\mathbf{u_{0}}}a_{1}\in{T_{{\cal O}_{2}}}_{|{{\mathbf{v}}}}$. The goal is to
build a word ${\mathbf{u_{1}}}$ satisfying
${\mathbf{u_{0}}}a_{1}{\mathbf{u_{1}}}a_{2}\in{T_{{\cal
O}_{2}}}_{|{{\mathbf{v}}}}$. As in Figure 4, choose some word
${\mathbf{v_{0}}}$ satisfying ${\mathbf{v_{0}}}a_{2}\in{T_{{\cal
O}_{2}}}_{|{{\mathbf{v}}}}$. By Lemma 5.12 and Property ($\natural$), there
exists a word ${\mathbf{r}}\in$ such that both
${\mathbf{u_{0}}}a_{1}{\mathbf{r}}\in{T_{{\cal O}_{2}}}_{|{{\mathbf{v}}}}$ and
${\mathbf{v_{0}}}{\mathbf{r}}\in{T_{{\cal O}_{2}}}_{|{{\mathbf{v}}}}$ hold.
Let ${\mathbf{v}}_{{\mathbf{r}}}$ be the shortest word such that
${\mathbf{v}}_{{\mathbf{r}}}{\mathbf{r}}$ is a prefix of ${\mathbf{v}}$ and
let ${\mathbf{u_{1}^{\prime}}}$ be the word satisfying
${\mathbf{v}}_{{\mathbf{r}}}{\mathbf{u_{1}^{\prime}}}={\mathbf{v}}{\mathbf{v_{0}}}$.
Then ${\mathbf{u_{1}^{\prime}}}$ is a cyclically orbital word, since its
length $\curlywedge$ prefix ${\mathbf{r}}$ satisfies
${\mathbf{v}}_{{\mathbf{r}}}{\mathbf{u_{1}^{\prime}}}{\mathbf{r}}\in T_{{\cal
O}_{2}}$.

${\mathbf{u_{1}^{\prime}}}$${\mathbf{u_{1}^{\prime}}}$${\mathbf{r}}$${\mathbf{v}}_{\mathbf{r}}$${\mathbf{v_{0}}}$${\mathbf{u_{0}}}$$a_{1}$${\mathbf{r}}$$a_{2}$$a_{2}$${\mathbf{r}}$$\leavevmode\nobreak\
{\mathbf{v}}$${T_{{\cal O}_{2}}}_{|{{\mathbf{v}}}}$

Figure 4. Proof of Proposition 5.23: building a word
${\mathbf{u_{1}^{\prime}}}$ satisfying
${\mathbf{u_{0}}}a_{1}{\mathbf{u_{1}^{\prime}}}a_{2}\in{T_{{\cal
O}_{2}}}_{|{{\mathbf{{\mathbf{v}}}}}}$.

By Proposition 5.21, ${\mathbf{u_{1}^{\prime}}}$ has finite order $q$. So we
set ${\mathbf{u_{1}}}={\mathbf{u_{1}^{\prime}}}^{q}$ and keep
$a_{1}{\mathbf{u_{1}}}a_{2}\in{T_{{\cal
O}_{2}}}_{|{{\mathbf{{\mathbf{v}}{\mathbf{u_{0}}}}}}}$.

The same method produces words $({\mathbf{u_{i}}})_{1\leq{\mathbf{i}}\leq n}$
of length at least $\curlywedge$ that induce the trivial action and such that
the word ${\mathbf{w^{(0)}}}=a_{1}{\mathbf{u_{1}}}a_{2}\cdots
a_{n-1}{\mathbf{u_{n-1}}}a_{n}{\mathbf{u_{n}}}$ satisfies
${\mathbf{w^{(0)}}}a_{1}\in{T_{{\cal
O}_{2}}}_{|{{\mathbf{{\mathbf{v}}{\mathbf{u_{0}}}}}}}$ and induces the same
action as $a_{1}\cdots a_{n}$. For $i\geq 0$, we analogously define a word
${\mathbf{w^{(i+1)}}}$ inducing the same action as $a_{1}\cdots a_{n}$ such
that ${\mathbf{w^{(i+1)}}}a_{1}\in{T_{{\cal
O}_{2}}}_{|{{\mathbf{{\mathbf{v}}{\mathbf{u_{0}}}{\mathbf{w^{(0)}}}\cdots{\mathbf{w^{(i)}}}}}}}$.
Eventually, there exist ${\mathbf{i}}<{\mathbf{j}}$ such that
${\mathbf{u_{1}^{(i)}}}$ and ${\mathbf{u_{1}^{(j+1)}}}$ have the same prefix
of length $\curlywedge$, hence ${\mathbf{w^{(i)}}}\cdots{\mathbf{w^{(j)}}}$ is
cyclically orbital and induces the same action as $(a_{1}\cdots
a_{n})^{{\mathbf{j}}-{\mathbf{i}}}$. Note that ${\mathbf{j}}-{\mathbf{i}}$ is
bounded by a constant depending on $\curlywedge({{\mathcal{A}}})$ and $\\#Q$.

######  Corollary 5.25.

If ${\mathcal{A}}$ generates an infinite group, the orbit tree of its dual
admits an $e_{2}$-liftable branch labeled either by $3^{\omega}$ or by
$3^{n}2^{\omega}$ for some $n$.

######  Proof 5.26.

If the lengths of the 2-blocks are bounded, any non-empty word has a non-empty
bounded power which is equivalent to a cyclically orbital word by Proposition
5.23, so the order of the action it induces is finite and bounded by a
constant from Propositions 5.21 and 5.23.

It follows from Zelmanov’s solution to the restricted Burnside problem [23,
24, 25] that the group $\langle{{\mathcal{A}}}\rangle$ is finite, which
contradicts the hypothesis. Proposition 5.19 leads to the conclusion.

######  Remark 5.27.

A disconnected 3-state invertible-reversible Mealy automaton have either three
connected components – each of size 1 – and the generated group is finite (see
Proposition 5.6), or two connected components – of size 1 and 2 – and the
situation is then more subtle because both connected components can generate
separately finite groups, but together an infinite group. Such a disconnected
Mealy automaton might not satisfy Corollary 5.25. For example, the Mealy
automaton in Figure 2 illustrates this situation. The group that it generates
is infinite since the product of two components of this automaton generates an
infinite subgroup $\langle{xy,xz}\rangle$ [1, 17]. However, if there is an
initial branch labeled by $2^{\omega}$ and the analogue of Corollary 5.25
holds, it would imply that both $y$ and $z$ have infinite order, which is not
the case as $\langle y,z\rangle$ is finite.

######  Theorem 5.28.

Any infinite group generated by a connected 3-state invertible-reversible
Mealy automaton admits an element of infinite order.

######  Proof 5.29.

All cyclically orbital words induce actions of infinite order from Proposition
3.4 and Corollary 5.25.

Finally we can emphasize that the proof of existence of elements of infinite
order is constructive and that the effective detection of such elements
becomes computable in this framework. For instance, in the group generated by
the Mealy automaton in Figure 2, the cyclically orbital word $xyz$ has
infinite order. At least in this case, neither one of the existing two
packages $\mathtt{FR}$ [3] and $\mathtt{automgrp}$ [19] for $\mathtt{GAP}$ [8]
system, dedicated to Mealy automata and groups they generate, is able to
detect such an element of infinite order.

## References

  * [1] A. Akhavi, I. Klimann, S. Lombardy, J. Mairesse, and M. Picantin, _On the finiteness problem for automaton (semi)groups_ , Int. J. Algebra Comput. 22 (2012), no. 6, 26p.
  * [2] S.V. Alešin, _Finite automata and the Burnside problem for periodic groups_ , Mat. Zametki 11 (1972), 319–328.
  * [3] L. Bartholdi, _$\mathtt{FR}$ functionally recursive groups, self-similar groups — a gap package, version 2.1.1_, 2014.
  * [4] L. Bartholdi and Z. Šuniḱ, _On the word and period growth of some groups of tree automorphisms_ , Comm. Algebra 29 (2001), no. 11, 4923–4964.
  * [5] James Belk and Collin Bleak, _Some undecidability results for asynchronous transducers and the Brin-Thompson group $2{V}$_, Preprint: arxiv:1405.0982, 2014.
  * [6] W. Burnside, _On an unsettled question in the theory of discontinuous groups_ , Quart.J.Math. 33 (1902), 230–238.
  * [7] D. D’Angeli and E. Rodaro, _A geometric approach to (semi)-groups defined by automata via dual transducers_ , Preprint: arxiv:1403.1722, 2014.
  * [8] The GAP Group, _$\mathtt{GAP}$ – Groups, Algorithms, and Programming, Version 4.7.5_, 2014.
  * [9] P.W. Gawron, V.V. Nekrashevych, and V.I. Sushchansky, _Conjugation in tree automorphism groups_ , Internat. J. Algebra Comput. 11 (2001), no. 5, 529–547.
  * [10] P. Gillibert, _The finiteness problem for automaton semigroups is undecidable_ , Internat. J. Algebra Comput. 24 (2014), no. 1, 1–9.
  * [11] V.M. Gluškov, _Abstract theory of automata_ , Uspehi Mat. Nauk 16 (1961), no. 5 (101), 3–62.
  * [12] E.S. Golod, _On nil-algebras and finitely residual groups_ , Izv. Akad. Nauk SSSR. Ser. Mat. 28 (1964), 273–276.
  * [13] E.S. Golod and I. Shafarevich, _On the class field tower_ , Izv. Akad. Nauk SSSR Ser. Mat. 28 (1964), 261–272.
  * [14] R.I. Grigorchuk, _On Burnside’s problem on periodic groups_ , Funktsional. Anal. i Prilozhen. 14 (1980), no. 1, 53–54.
  * [15] by same author, _Degrees of growth of finitely generated groups and the theory of invariant means_ , Izv. Akad. Nauk SSSR Ser. Mat. 48 (1984), no. 5, 939–985.
  * [16] N. Gupta and S. Sidki, _On the Burnside problem for periodic groups_ , Math. Z. 182 (1983), no. 3, 385–388.
  * [17] I. Klimann, _The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable_ , Proc. 30th STACS, LIPIcs, vol. 20, 2013, pp. 502–513.
  * [18] R. Mac Naughton and S. Papert, _Counter free automata_ , The MIT Press, 1971\.
  * [19] Y. Muntyan and D. Savchuk, _$\mathtt{automgrp}$ automata groups — a gap package, version 1.2.4_, 2014.
  * [20] V. Nekrashevych, _Self-similar groups_ , Mathematical Surveys and Monographs, vol. 117, American Mathematical Society, Providence, RI, 2005.
  * [21] D.M. Savchuk and Y. Vorobets, _Automata generating free products of groups of order 2_ , J. Algebra 336 (2011), no. 1, 53–66.
  * [22] V.I. Sushchansky, _Periodic permutation $p$-groups and the unrestricted Burnside problem_, DAN SSSR. 247 (1979), no. 3, 557–562, (in Russian).
  * [23] M. Vaughan-Lee, _The restricted Burnside problem_ , London Mathematical Society Monographs. New Series, vol. 8, Oxford University Press, 1993.
  * [24] E.I. Zel′manov, _Solution of the restricted Burnside problem for groups of odd exponent_ , Izv. AN SSSR Math+ 54 (1990), no. 1, 42–59, 221.
  * [25] by same author, _Solution of the restricted Burnside problem for $2$-groups_, Mat. Sb. 182 (1991), no. 4, 568–592.


# MobileStyleGAN: A Lightweight Convolutional Neural Network for High-Fidelity
Image Synthesis

Sergei Belousov
<EMAIL_ADDRESS>
###### Abstract

In recent years, the use of Generative Adversarial Networks (GANs) has become
very popular in generative image modeling. While style-based GAN architectures
yield state-of-the-art results in high-fidelity image synthesis,
computationally, they are highly complex. In our work, we focus on the
performance optimization of style-based generative models. We analyze the most
computationally hard parts of StyleGAN2, and propose changes in the generator
network to make it possible to deploy style-based generative networks in the
edge devices. We introduce MobileStyleGAN architecture, which has x3.5 fewer
parameters and is x9.5 less computationally complex than StyleGAN2, while
providing comparable quality.

##  1 Introduction

Figure 1: (top) Images generated by StyleGAN2. (bottom) Images generated by
MobileStyleGAN.

In recent years, high-fidelity image synthesis has significantly improved by
through the use of Generative Adversarial Networks (GANs) [9]. Whereas early
work such as DCGAN [27] could generate images having a resolution up to 64x64
pixels, modern networks such as BigGAN [3] and StyleGAN [20, 21, 19] allow the
generation of photorealistic images with up to 512x512 and even 1024x1024
pixels. Although the quality of generative models has significantly improved,
image generation still requires many computation resources. The high
computational complexity makes it difficult to deploy state-of-the-art
generative models to edge devices.

For example, the StyleGAN2 [21] network allows realistic face images 1024x1024
pixels in size with FID=2.84 for the FFHQ dataset. It, however, contains
28.27M parameters and has a computational complexity of 143.15GMAC.

We propose a new lightweight architecture, MobileStyleGAN, a high-resolution
generative model for high-quality image generation. Taking as a baseline the
original StyleGAN2 architecture, we revisit computationally hard parts of this
network to create our own lightweight model that provides comparable quality
(Figure 1). The whole network contains 8.01M parameters, has a computational
complexity of 15.09 GMAC, and provides quality with FID=7.75 for the FFHQ
dataset.

Our main contributions are:

  * •

We introduce an end-to-end wavelet-based convolutional neural network for
high-fidelity image synthesis.

  * •

We introduce Depthwise Separable Modulated Convolution as a lightweight
version of Modulated Convolution to decrease computational complexity.

  * •

We introduce a revisited version of the demodulation mechanism applicable to
graph optimizations such as operation fusion.

  * •

We propose a pipeline based on knowledge distillation to train our network.

##  2 Related Work

###  2.1 StyleGAN

StyleGAN [20] is a modern generative model for high-resolution image
generation. The key aspects of the StyleGAN network are:

  * •

It uses progressive growing to increase the resolution gradually.

  * •

It generates images from a fixed value tensor, as opposed to generating images
from stochastically generated latent variables as in conventional GANs.

  * •

The stochastically generated latent variables are used as style vectors
through AdaIN [16] at each resolution after being nonlinearly transformed by
an 8-layer neural network.

StyleGAN2 [21] improves upon StyleGAN by:

  * •

Eliminating droplet modes by normalizing with estimated statistics instead of
normalizing with actual statistics such as AdaIN.

  * •

Reducing eye and tooth stagnation by using a hierarchical generator with skip
connections instead of progressive growing.

  * •

Improving image quality by reducing PPL and smoothing the latent space.

StyleGAN2-ADA [19] makes StyleGAN applicable to tasks with limited data by
using adaptive discriminator augmentations.

###  2.2 Model acceleration

A prominent research directions in deep learning focuses on accelerating to
convolution neural networks (CNNs) using manual and automatic design of
lightweight architectures.

Some works focused on designing efficient neural classification networks that
can be used as a backbone for other tasks. Howard et al. [15, 14, 28] proposed
efficient models called MobileNets for mobile and embedded vision
applications. These ideas have been improved in many articles [29, 17, 8, 32,
26].

Other works focused on the design models of efficient generative models. Li et
al. [23] proposed a generic framework for automatic optimization of the
conditional GANs based on a distillation and neural architecture search [4].
Chang and Lu [5] proposed a distillation pipeline for compression of BigGAN.
Liu et al. [24] proposed a lightweight GAN based on the attention mechanism.

###  2.3 Knowledge distillation

Hinton et al. [13] proposed the knowledge distillation method to train a small
student network using a large teacher network. The main idea of the
distillation is that the student network is trained to mimic the teacher
network’s behavior. Aguinaldo et al. [2] adopted knowledge distillation to
accelerate unconditional GANs. Some other works related to GANs [30, 6, 23, 5]
also used knowledge distillation as part of their pipeline.

###  2.4 Wavelet transform

Using wavelet-based methods with deep learning is not novel. Wavelets [10]
have been applied to many computer vision tasks such as texture classification
[7], image restoration [25],and super-resolution [31].

Han et al. [11] proposed Not-So-Big-GAN architecture based on two sub-
networks: a generative network in low resolution and a super-resolution
network for upsampling. The authors showed that wavelet-based sub-networks
outperform pixel-based methods.

In comparison to previous works, we present an end-to-end wavelet-based CNN
architecture for generative networks. We show that integrating wavelet-based
methods into GANs allows more lightweight networks to be designed and provides
more smoothed latent space.

##  3 MobileStyleGAN Architecture

Our proposed architecture, MobileStyleGAN, is based on previous works related
to style-based generative models. MobileStyleGAN includes a mapping network
and synthesis network, as in StyleGAN2. We adopt the mapping network from
StyleGAN2, focusing on the design of a computationally efficient synthesis
network.

We now first describe the key differences between our proposed architecture
and the basic StyleGAN2. We then describe the distillation-based training
procedure for the MobileStyleGAN network.

###  3.1 Image representation revisited

While StyleGAN2 works with pixel-based image representation and aims to
directly predict the pixel values of the output image, in our work, we use a
frequency-based representation of images. In this way, MobileStyleGAN seeks to
predict the discrete wavelet transform (DWT) of the output image.

When applied to a 2d image, the DWT transforms the channel into four equally-
sized channels having a lower spatial resolution and different frequency
bands. The inverse discrete wavelet transform (IDWT) then reconstructs the
pixel-based representation from the wavelet-domain (Figure 2).

This type of representation of images has several advantages, such as:

  * •

Since wavelet-based image representation contains more structural information
than pixel-based approaches, we can generate high-resolution images using low-
resolution feature maps without losing accuracy:

$\begin{array}[]{l}|I-IDWT(DWT(I))|_{l1}<\epsilon\\\ \epsilon\approx
1e-7\end{array}$ (1)

  * •

In our work, we use Haar wavelets [10] as a bank of filters for the DWT and
IDWT. IDWT using Haar wavelets can be implemented efficiently without
multiplication operations (Figure 2):

$\begin{array}[]{l}\left\\{\begin{matrix}A=LL+HL+LH+HH\\\ B=LL-HL+LH-HH\\\
C=LL+HL-LH-HH\\\ D=LL-HL-LH+HH\end{matrix}\right.\end{array}$ (2)

  * •

The generation of the high-frequency details of the image is a complex
problem. While the latent space of StyleGAN is smoothed in low frequencies, it
is rough in high frequencies. In contrast to pixel-based approaches, using
frequency-based image representation, we can add regularization to the high-
frequency components of the signal directly, which makes latent space smooth
at both low and high frequencies.

Figure 2: (left) The original RGB image. (right) DWT decomposition of the
image. A, B, C, D are four pixels located in the top-left grid 2x2 of the HR
image.

###  3.2 Progressive growing revisited

StyleGAN2 uses a skip-generator to form the output image by explicitly summing
RGB values from multiple resolutions of the same image. We found that when we
predict images in the wavelet domain, the prediction head based on skip
connections does not make an essential contribution to the quality of the
generated image. Accordingly, to decrease computational complexity, we replace
the skip-generator with a single prediction head from the network’s last
block. Predicting the target image from the intermediate blocks, however, is
important in stabilizing image synthesis. We, therefore, add an auxiliary
prediction head for each intermediate block to predict the target image
according to its spatial resolution.

The difference between the StyleGAN2 and MobileStyleGAN prediction heads is
shown in Figure 3.

Figure 3: (left) Prediction head of StyleGAN2. (right) Prediction head of
MobileStyleGAN.

###  3.3 Depthwise separable modulated convolution

Figure 4: (left) Modulated convolution. (middle) Depthwise separable modulated
convolution. (right) Depthwise separable modulated convolution with a
trainable demodulation.

Inspired by MobileNet [15], MobileStyleGAN is based on depthwise separable
convolutions, a form of factorized convolutions that factorize a standard
convolution into a 3x3 depthwise convolution and a 1x1 convolution called a
pointwise convolution.

As described in [21], a modulated convolution consists of modulation,
convolution, and normalization (left panel of Figure 4). Depthwise separable
modulated convolution also comprises these parts (middle panel of Figure 4).
We note, however, that while StyleGAN2 describes modulation/demodulation
applied to weights, we apply them to input/output activations, respectively.
This order of operations makes it easy to describe depthwise separable
modulated convolution. Let us start by considering the effect of a modulation
followed by a convolution. The modulation scales each input feature map of the
convolution based on the incoming style:

$x^{\prime}=s*x$ (3)

where $x$ and $x^{\prime}$ are the original and modulated input activations,
respectively, and $s$ is the scale corresponding to the input feature maps.
Then we apply 3x3 depthwise convolution and 1x1 pointwise convolution
sequentially without any nonlinearity between them:

$\begin{array}[]{l}x^{\prime\prime}=w_{dw}*x^{\prime}\\\
x^{\prime\prime\prime}=w_{pw}*x^{\prime\prime}\end{array}$ (4)

Now we apply demodulation to remove the effect of $s$ from the statistics of
the output feature maps. Due to the linearity of the convolution operator, the
result of the sequentially applied depthwise and pixelwise convolutions are
equal to the result of the applied dense convolution:

$\begin{array}[]{l}w_{dense}=w_{dw}*w_{pw}\\\
w_{pw}*(w_{dw}*x^{\prime})=(w_{pw}*w_{dw})*x^{\prime}=w_{dense}*x^{\prime}\end{array}$
(5)

In this way, demodulation coefficients can be calculated as:

$\begin{array}[]{l}w^{\prime}=w_{pw}*w_{dw}\\\
demod_{j}=\frac{1}{\sqrt{\sum_{i,k}{(s_{i}*w^{\prime}_{i,j,k})^{2}}+\epsilon}}\end{array}$
(6)

where $i$ and $j$ and $k$ enumerate the input/output feature maps and spatial
footprint of the convolution, respectively. To demodulate the output feature
maps, we apply:

$x_{out}=demod*x^{\prime\prime\prime}$ (7)

###  3.4 Demodulation fusion

Batch normalization fusion is a popular technique to decrease the
computational complexity of convolutional networks at the inference time. This
technique relies on the fact that we can merge two linear operations into one.
The demodulation mechanism is similar to batch normalization, but it is not a
linear operation at the inference time. Following Equation 6, where weights
are fixed, the demodulation is the function of style. To make the demodulation
constant, we replace style coefficients with trainable parameters (right panel
of Figure 4):

$\begin{array}[]{l}w^{\prime}=w_{pw}*w_{dw}\\\
demod_{j}=\frac{1}{\sqrt{\sum_{i,k}{(p_{demod}*w^{\prime}_{i,j,k})^{2}}+\epsilon}}\end{array}$
(8)

Thus, demodulation becomes the constant at the inference time and can be
merged into the pixelwise convolution weights. We found that this technique
does not adversely affect the quality of the generated image.

###  3.5 Upscale revisited

Figure 5: (left) StyleGAN2 upscale block. (right) MobileStyleGAN upscale
block. Yellow rectangles on arrows show the number of channels in related
feature maps.

While the StyleGAN2 building block uses ConvTranspose (left panel of Figure 5)
to upscale input feature maps, following Section 3.1, we use IDWT as an
upscale function in the building block of MobileStyleGAN (right panel of
Figure 5). Since IDWT does not include trainable parameters, we add extra
depthwise separable modulated convolution after the IDWT layer.

Figure 6: (left) StyleGAN2 building block. (right) MobileStyleGAN building
block.

The complete building block structures for StyleGAN2 and MobileStyleGAN are
shown in Figure 6.

##  4 Training framework

Figure 7: Training framework.

As in previous works [5, 23], our training framework is based on the knowledge
distillation technique [13]. Given StyleGAN2 [21] as the teacher network, we
train MobileStyleGAN to mimic its functionality. The overall framework is
illustrated in Figure 7. In this section, we discuss the main parts of our
training framework.

###  4.1 Data preparation

Given the original StyleGAN2 generator, we can transform unpaired learning
into the paired setting. To do so, we prepare triplet data $\\{style,\ noise,\
I_{teacher}\\}$, where $style$ is the output of the mapping network for given
noise vector z, $noise$ is the noise shared between the teacher and student
networks, and $I_{teacher}$ is the output of the teacher network for the given
style.

As described in Section 3.2, each block of MobileStyleGAN predicts the output
image for its spatial size. Therefore, instead of $I_{teacher}$, we use
$I^{pyramid}_{teacher}$ as a ground-truth. $I^{pyramid}_{teacher}$ is the
image pyramid built from $I_{teacher}$. Accordingly, our trained data are
represented as the triplet data $\\{style,\ noise,\ I^{pyramid}_{teacher}\\}$.

To prevent overfitting, we do not use a preprocessed dataset. Instead, we
generate data on the fly during a learning procedure.

To decrease memory consumption during the learning procedure, we use only
artificial samples generated by StyleGAN2 and no real data.

###  4.2 Training objective

We now elaborate on the proposed objectives of the knowledge distillation.

Figure 8: Pixel-Level Distillation Loss.

Pixel-Level Distillation Loss (Figure 8). Since MobileStyleGAN aims to predict
the target image in the wavelet domain, the naive method to mimic the
functionality of StyleGAN2 minimizes the pixel-level distance between the
wavelet transform of the image generated by StyleGAN2 and the output of
MobileStyleGAN. Also, we added a regularization term that minimizes the pixel-
level distance between our ground truth and the predicted image in the pixel-
based domain. We found that this term allows us to train different frequencies
in concert with each other. As described in Section 3.2, our network predicts
output images at each spatial size. Accordingly, pixel-based distillation loss
was applied at each scale.

Formally, let

$\begin{array}[]{l}L_{pix}(F_{s},I_{t})=\sum_{i}{(||F^{i}_{s}-DWT(I^{i}_{t})||_{1}+||IDWT(F^{i}_{s})-I^{i}_{t}||_{1})}\end{array}$
(9)

where $F^{i}_{s}$ is the image in the wavelet domain predicted by the i-th
block of the student network, $I^{i}_{t}$ is the ground-truth image in the
pixel-based domain in the corresponding spatial size.

Perceptual Loss. The pixel-level loss described previously does not capture
perceptual differences between output and ground-truth images. To solve this
problem, we use perceptual loss as an objective. Our perceptual loss is based
on VGG16 features and implemented as described in [18]. We applied perceptual
loss only to the output image generated by MobileStyleGAN.

Formally, let

$\begin{array}[]{l}L_{perc}(I_{s},I_{t})=\sum_{l}{||VGG16(I^{256\mathbf{x}256}_{s})_{l}-VGG16(I^{256\mathbf{x}256}_{t})_{l}||_{2}}\end{array}$
(10)

where $VGG16(...)_{l}$ are intermediate features from the corresponding layer
$l\in[relu1\\_2,\ relu2\\_2,\ relu3\\_3,\ relu4\\_3]$ of the VGG16,
$I^{256\mathbf{x}256}_{s}$ is the output image predicted by the student
network (resized to 256x256), where $I^{256\mathbf{x}256}_{t}$ is the output
image predicted by the teacher network (resized to 256x256).

GAN Loss. Using only pixel-level and perceptual losses leads to generation of
blurred images. To sharpen the generated images, we incorporate a
discriminator network in our pipeline. We adopt the GAN loss for the
generator:

$\begin{array}[]{l}L_{g}(style,noise)=f(-D_{T}(G_{student}(style,noise)))\end{array}$
(11)

and for the discriminator network:

$\begin{array}[]{l}\begin{aligned}
L_{d}(style,noise)={}&f(-D_{T}(G_{teacher}(style,noise)))\\\
&+f(D_{T}(G_{student}(style,noise)))\\\ &+\frac{\gamma}{2}\mu(||\nabla
D_{T}(G_{teacher}(...)||^{2})\end{aligned}\end{array}$ (12)

where $f(t)=-\log(1+\exp(-t))$ is the softplus function, $D_{T}(...)$ is the
discriminator network with differentiable augmentations,
$G_{student}(...)$/$G_{teacher}(...)$ is the student/teacher network, and
(style, noise) is the input paired data. The discriminator has the same
topology as in [20].

We found that it is hard to balance capacity between generator and
discriminator networks when we compress the generator network. So, R1
regularization is an important part of GAN Loss for distillation pipelines,
that allow for recouping capacity disbalance between generator and
discriminator.

Full objective. Finally, we define the full objective as:

$\begin{array}[]{l}L_{student}=\lambda_{1}*L_{pix}+\lambda_{2}*L_{perc}+\lambda_{3}*L_{g}\\\
L_{discriminator}=L_{d}\end{array}$ (13)

where hyperparameters $\lambda_{1},\ \lambda_{2},\ \lambda_{3}$ control the
importance of each term.

##  5 Experiments

To train our MobileStyleGAN network we use the StyleGAN2 teacher network
trained on the FFHQ [20] dataset.

###  5.1 Training

MobileStyleGAN is trained using the Adam algorithm [22] with $\beta 1=0.9,\
\beta 2=0.999$. The generator and discriminator learning rates are both set to
constant 5e-4. We use affine transforms and cutout as differentiable
augmentations at the input of the discriminator. Hyperparameters of the
objective function set are fixed at $\lambda_{1}=1.0,\ \lambda_{2}=1.0,\
\lambda_{3}=0.1$. We update the generator and discriminator at each
optimization step. Training takes about three days on 4 x NVIDIA 2080Ti GPU
with batch_size=8.

###  5.2 Results

Table 1 shows the result of our evaluation of MobileStyleGAN on the FFHQ
datase. We compare the number of parameters, the computational cost and the
Frechet inception distance (FID) [12] of MobileStyleGAN and the teacher
network (StyleGAN2).

Network | MParams | GMACs | FID
---|---|---|---
StyleGAN2 | 28.27 | 143.15 | 2.84
MobileStyleGAN | 8.01 | 15.09 | 7.75
Table 1: Main results. Comparison between StyleGAN and MobileStyleGAN for the
FFHQ dataset, 1024x1024.

Also, we evaluate inference time for StyleGAN2 and MobileStyleGAN on CPU. We
use a laptop with Intel(R) Core(TM) i5-8279U CPU for our experiments. Table 2
shows the result of inference time evaluation. As we noticed previously, some
architectural tricks that we used in MobileStyleGAN make available graph
optimizations such as constant folding, etc. We get better performance when we
use special inference engines such as OpenVINO [1] that automatically apply
graph optimization.

Network | Engine | Time (sec.)
---|---|---
StyleGAN2 | PyTorch | 4.3
MobileStyleGAN | PyTorch | 1.2
MobileStyleGAN | OpenVINO | 0.16
Table 2: Inference time on CPU (Intel(R) Core(TM) i5-8279U).

##  6 Conclusion

In this work, we approached the problem of high-fidelity image synthesis,
suitable for deployment on edge devices. We proposed the new style-based
lightweight generative network and training pipeline based on knowledge
distillation. We have made our training code publicly available
(https://github.com/bes-dev/MobileStyleGAN.pytorch), along with a simple
python library for fast random face synthesis on the CPU
(https://github.com/bes-dev/random_face). The accompanying videos can be found
on YouTube
(https://www.youtube.com/playlist?list=PLstKhmdpWBtwsvq_27ALmPbf_mBLmk0uI).

Some techniques may further improve performance and accuracy, such as
quantization and pruning. We left them for future research.

## References

  * [1] Openvino toolkit.  https://software.intel.com/content/www/us/en/develop/tools/openvino-toolkit.html.
  * [2] Angeline Aguinaldo, Ping-Yeh Chiang, Alex Gain, Ameya Patil, Kolten Pearson, and Soheil Feizi.  Compressing gans using knowledge distillation, 2019.
  * [3] Andrew Brock, Jeff Donahue, and Karen Simonyan.  Large scale gan training for high fidelity natural image synthesis, 2019\.
  * [4] Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han.  Once-for-all: Train one network and specialize it for efficient deployment, 2020.
  * [5] Ting-Yun Chang and Chi-Jen Lu.  Tinygan: Distilling biggan for conditional image generation, 2020.
  * [6] Yonggan Fu, Wuyang Chen, Haotao Wang, Haoran Li, Yingyan Lin, and Zhangyang Wang.  Autogan-distiller: Searching to compress generative adversarial networks, 2020.
  * [7] Shin Fujieda, Kohei Takayama, and Toshiya Hachisuka.  Wavelet convolutional neural networks for texture classification, 2017\.
  * [8] Amir Gholami, Kiseok Kwon, Bichen Wu, Zizheng Tai, Xiangyu Yue, Peter Jin, Sicheng Zhao, and Kurt Keutzer.  Squeezenext: Hardware-aware neural network design, 2018.
  * [9] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks, 2014.
  * [10] A. Haar.  On the theory of orthogonal function systems. * ) * * ) (first communication.).  1909\.
  * [11] Seungwook Han, Akash Srivastava, Cole Hurwitz, Prasanna Sattigeri, and David D. Cox.  not-so-biggan: Generating high-fidelity images on small compute with wavelet-based super-resolution, 2020.
  * [12] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium, 2018.
  * [13] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network, 2015.
  * [14] Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, Quoc V. Le, and Hartwig Adam.  Searching for mobilenetv3, 2019.
  * [15] Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications, 2017.
  * [16] Xun Huang and Serge Belongie.  Arbitrary style transfer in real-time with adaptive instance normalization, 2017.
  * [17] Forrest N. Iandola, Song Han, Matthew W. Moskewicz, Khalid Ashraf, William J. Dally, and Kurt Keutzer.  Squeezenet: Alexnet-level accuracy with 50x fewer parameters and ¡0.5mb model size, 2016.
  * [18] Justin Johnson, Alexandre Alahi, and Li Fei-Fei.  Perceptual losses for real-time style transfer and super-resolution, 2016\.
  * [19] Tero Karras, Miika Aittala, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila.  Training generative adversarial networks with limited data.  In Proc. NeurIPS, 2020.
  * [20] Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks, 2019.
  * [21] Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila.  Analyzing and improving the image quality of StyleGAN.  In Proc. CVPR, 2020.
  * [22] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization, 2017.
  * [23] Muyang Li, Ji Lin, Yaoyao Ding, Zhijian Liu, Jun-Yan Zhu, and Song Han.  Gan compression: Efficient architectures for interactive conditional gans, 2020.
  * [24] Bingchen Liu, Yizhe Zhu, Kunpeng Song, and Ahmed Elgammal.  Towards faster and stabilized gan training for high-fidelity few-shot image synthesis, 2021.
  * [25] Pengju Liu, Hongzhi Zhang, Kai Zhang, Liang Lin, and Wangmeng Zuo.  Multi-level wavelet-cnn for image restoration, 2018.
  * [26] Ningning Ma, Xiangyu Zhang, Hai-Tao Zheng, and Jian Sun.  Shufflenet v2: Practical guidelines for efficient cnn architecture design, 2018.
  * [27] Alec Radford, Luke Metz, and Soumith Chintala.  Unsupervised representation learning with deep convolutional generative adversarial networks, 2016.
  * [28] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks, 2019.
  * [29] Mingxing Tan and Quoc V. Le.  Efficientnet: Rethinking model scaling for convolutional neural networks, 2020.
  * [30] Haotao Wang, Shupeng Gui, Haichuan Yang, Ji Liu, and Zhangyang Wang.  Gan slimming: All-in-one gan compression by a unified optimization framework, 2020.
  * [31] Qi Zhang, Huafeng Wang, and Sichen Yang.  Image super-resolution using a wavelet-based generative adversarial network, 2019.
  * [32] Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun.  Shufflenet: An extremely efficient convolutional neural network for mobile devices, 2017.