# Equivariant Perturbation in
Gomory and Johnson’s Infinite Group Problem
VII. Inverse Semigroup Theory, Closures, Decomposition of Perturbations

Robert Hildebrand  Robert Hildebrand: Grado Dept. of Industrial and Systems
Engineering, Virginia Tech<EMAIL_ADDRESS>,  Matthias Köppe  Matthias Köppe:
Dept. of Mathematics, University of California, Davis
<EMAIL_ADDRESS>and  Yuan Zhou  Yuan Zhou: Dept. of Mathematics,
University of Kentucky<EMAIL_ADDRESS>
(Date: Revision: 3403 $-\ $Date: 2020-01-03 11:25:49 -0500 (Fri, 03 Jan 2020)
)

###### Abstract.

In this self-contained paper, we present a theory of the piecewise linear
minimal valid functions for the 1-row Gomory–Johnson infinite group problem.
The non-extreme minimal valid functions are those that admit effective
perturbations. We give a precise description of the space of these
perturbations as a direct sum of certain finite- and infinite-dimensional
subspaces. The infinite-dimensional subspaces have partial symmetries; to
describe them, we develop a theory of inverse semigroups of partial
bijections, interacting with the functional equations satisfied by the
perturbations. Our paper provides the foundation for grid-free algorithms for
the Gomory–Johnson model, in particular for testing extremality of piecewise
linear functions whose breakpoints are rational numbers with huge
denominators.

An extended abstract of 13 pages titled _On perturbation spaces of minimal
valid functions: Inverse semigroup theory and equivariant decomposition
theorem_ appeared in: Integer Programming and Combinatorial Optimization. IPCO
2019 (A. Lodi and V. Nagarajan, eds.), Lecture Notes in Computer Science, vol.
11480, Springer, Cham, 2019, pp. 247–260,
https://doi.org/10.1007/978-3-030-17953-3_19, ISBN 978-3-030-17952-6 [15]. A
preliminary version of parts of the development in this paper appeared in the
third author’s 2017 Ph.D. thesis [23]. The authors gratefully acknowledge
partial support from the National Science Foundation through grants
DMS-0914873 (R. Hildebrand, M. Köppe) and DMS-1320051 (M. Köppe, Y. Zhou).
Part of this work was done while R. Hildebrand and M. Köppe were visiting the
Simons Institute for the Theory of Computing in Fall 2017. It was partially
supported by the DIMACS/Simons Collaboration on Bridging Continuous and
Discrete Optimization through NSF grant CCF-1740425.

##  1\. Introduction

###  1.1. Finite group relaxations $R_{f}(P,{\mathbb{Z}})$ of integer programs
and hierarchies of valid inequalities

A powerful method to derive cutting planes for unstructured integer linear
optimization problems is to study relaxations with more structure and
convenient properties. The pioneering relaxation in this line of research on
general-purpose cutting planes is Gomory’s _finite group relaxation_ [10],
whose convex hull is known as the _corner polyhedron_.

The relaxations are structured around the simplex method, applied to the
continuous relaxation, and are therefore suitable for generating cuts in a
linear-programming-based cutting-plane procedure. The group relaxation is
obtained by forgetting about the nonnegativity of all basic variables,
retaining only their integrality. Viewed in the space of nonbasic variables,
the equations of the simplex tableau are replaced by congruences modulo the
abelian group (${\mathbb{Z}}$-module) generated by the columns of the basis
matrix. Quotienting out by this group, one obtains a “group equation,” which
gives the relaxation its name. Further relaxations are obtained by picking
just one or a few rows of the system, or more generally by condensing the
system by means of group homomorphisms; see [10] for its remarks on the use of
(additive) group characters.

In the present paper, we restrict ourselves to 1-row (“cyclic”) group
relaxations, which after aggregation of non-basic variables with identical
coefficients can be brought to the form

(1.1) $\displaystyle\sum_{p\in P}y(p)\,p\in f+{\mathbb{Z}}$ $\displaystyle
y(p)\in{\mathbb{Z}}_{+}\ \ \textrm{for all $p\in P$}$

where $P$ is a finite subset of an additive group
$G=\frac{1}{q}{\mathbb{Z}}\supset{\mathbb{Z}}$ and $f\in
G\setminus{\mathbb{Z}}$, so $f+{\mathbb{Z}}$ is a coset of the subgroup
${\mathbb{Z}}$ in $G$. This is called Gomory’s _finite (cyclic) group
problem_. We denote the convex hull of $y$ by $R_{f}(P,{\mathbb{Z}})$; it is a
polyhedron of blocking type. Therefore every nontrivial valid linear
inequality can be written in the form $\langle\pi,y\rangle:=\sum_{p\in
P}\pi(p)y(p)\geq 1$; then we call $\pi$ a _valid function_. If
$\pi^{\prime}\leq\pi$ are two valid functions, then the valid inequality
$\langle\pi,y\rangle\geq 1$ is a conic combination of
$\langle\pi^{\prime},y\rangle\geq 1$ and nonnegativity inequalities $y(p)\geq
0$. Thus it suffices to consider the _minimal (valid) functions_ $\pi$,
defined by the property

(M) if $\pi^{\prime}$ is valid and $\pi^{\prime}\leq\pi$ then
$\pi^{\prime}=\pi$.

A stronger notion is that of _extreme functions_ $\pi$, defined by the
property

(E) if $\pi^{+}$ and $\pi^{-}$ are minimal and
$\pi=\tfrac{1}{2}(\pi^{+}+\pi^{-})$ $\displaystyle\text{then
$\pi=\pi^{+}=\pi^{-}$}.$

Extreme functions correspond to facet-defining inequalities for
$R_{f}(P,{\mathbb{Z}})$. Following the traditions of polyhedral combinatorics,
we are interested in describing families of extreme functions and making them
available for cutting-plane algorithms.

###  1.2. Master problems $R_{f}(G,{\mathbb{Z}})$ and the subadditive
characterization of minimal functions

Gomory’s approach was to consider _master problems_ for this purpose. The sets
of solutions $y$ to 1-row group relaxations $R_{f}(P)$ for subsets $P$ of the
same group $G$ inject into the _master group relaxation_

(1.2) $\displaystyle\sum_{p\in G}y(p)\,p\in f+{\mathbb{Z}}$ $\displaystyle
y\colon G\to{\mathbb{Z}}_{+}\textrm{ has finite support}$

by setting $y(p)=0$ for $p\notin P$. We denote its convex hull by
$R_{f}(G,{\mathbb{Z}})$. This is an infinite-dimensional set. By Gomory’s
master theorem [10, Theorem 13], every extreme function $\pi^{\prime}$ for
$R_{f}(P,{\mathbb{Z}})$ is obtained from some extreme function $\pi$ for a
master problem $R_{f}(G,{\mathbb{Z}})$ with $P\subseteq G$ by restricting the
function, $\pi^{\prime}=\pi|_{P}$. Moreover, Gomory [10] gave a
characterization of the minimal functions for the master problem
$R_{f}(G,{\mathbb{Z}})$ by the following functional inequalities and
equations:

(1.3a) $\displaystyle\pi(x)\geq 0$ $\displaystyle\text{for }x\in G,$ (1.3b)
$\displaystyle\pi(x+z)=\pi(x)$ for $x\in G$, $z\in{\mathbb{Z}}$ (periodicity)
(1.3c) $\displaystyle\pi(0)=0,\ \pi(f)=1,$ (1.3d)
$\displaystyle\Delta\pi(x,y)\geq 0$ $\displaystyle\text{for }x,y\in G$
(subadditivity), (1.3e) $\displaystyle\Delta\pi(x,f-x)=0$
$\displaystyle\text{for }x\in G$ (symmetry condition),

where $\Delta\pi(x,y)=\pi(x)+\pi(y)-\pi(x+y)$ is the _subadditivity slack_
function. By quotienting out by ${\mathbb{Z}}$, this system describes a
polyhedron in ${\mathbb{R}}^{G/{\mathbb{Z}}}$. Extreme functions are then
simply the vertices of this polyhedron; thus some of the subadditivity
inequalities $\Delta\pi(x,y)\geq 0$ are tight, i.e., additivity holds.

###  1.3. Continuous interpolations of extreme functions and the infinite
group problem $R_{f}({\mathbb{R}},{\mathbb{Z}})$

Gomory and Johnson, in their seminal papers [11, 12], noted that many extreme
functions for finite master group problems follow simple patterns that become
apparent in the piecewise linear interpolations of these functions. The
simplest pattern is that of the well-known two-slope function giving the
Gomory mixed integer cut (gmic ), which can be found in all finite group
problems; see Figure 1 (left).111A function name shown in sans serif font
refers to the software [21], which includes the Electronic Compendium of
Extreme Functions [17]. Gomory and Johnson initiated a program to study such
functions of a real variable systematically. The technical framework is that
of the _infinite group problem_ , in which the group $G$ in (1.2) is enlarged
from $\frac{1}{q}{\mathbb{Z}}$ to ${\mathbb{R}}$. Gomory and Johnson proved
that the characterization (1.3) of minimal functions still holds in this
setting.

|
---|---
|
|
Figure 1. Extreme functions for finite master group problems following simple
patterns that become apparent in the piecewise linear interpolations. _Left,_
the Gomory mixed-integer cut (gmic). _Right,_ another two-slope extreme
function.

For an extreme function $\pi|_{G}$ for a finite master problem
$R_{f}(G,{\mathbb{Z}})$, the piecewise linear interpolation $\pi=\href
https://github.com/mkoeppe/cutgeneratingfunctionology/search?q=%22def+interpolate_to_infinite_group(%22(\pi|_{G})$
is a minimal function, but not necessarily extreme. (A partial converse is
true; the restriction of a continuous piecewise linear extreme function $\pi$
for $R_{f}({\mathbb{R}},{\mathbb{Z}})$ to a group $G$ that includes all
breakpoints of $\pi$ is extreme for $R_{f}(G,{\mathbb{Z}})$.) There is a
possible viewpoint on the extreme functions for the infinite group problems as
“robust” cut-generating functions that ignore the specific number-theoretic
properties of a particular group problem
$R_{f}(\frac{1}{q}{\mathbb{Z}},{\mathbb{Z}})$. As a matter of fact, in a
numerical implementation, the value $q$ and exact rational value of $f$ would
not be readily available.

A natural algorithmic focus lies on piecewise linear valid functions, though a
part of the literature [1, 2] also studies more complicated functions. (When
we discuss piecewise linear functions in this paper, we include the
discontinuous case with possible jumps at breakpoints, which includes
important examples such as the Gomory fractional cut, gomory_fractional .)

For ${\mathbb{Z}}$-periodic piecewise linear functions, the characterization
(1.3) of minimal functions gives a simple algorithm for testing minimality,
based on enumerating the vertices of a certain polyhedral complex; see [3,
section 2.2] and [16, section 5]. For testing the extremality of a piecewise
linear minimal function, however, in contrast to the finite group case, we
cannot directly use polyhedral methods any more. Since the quotient
${\mathbb{R}}/{\mathbb{Z}}$ is not finite, we have to use infinite-dimensional
methods of functional equations and inequalities. The most important lemma
from this theory is the Gomory–Johnson interval lemma, variants of which has
been used in virtually all proofs of extremality in the literature.

###  1.4. The space $\tilde{\Pi}^{\pi}$ of effective perturbations
$\tilde{\pi}$ of a minimal valid function

Recall that by definition (E), a minimal valid function $\pi$ is extreme if it
cannot be written as a convex combination of two other minimal valid functions
$\pi^{+}$, $\pi^{-}$. A fruitful approach to extremality testing, introduced
by Basu et al. in Part I of the present series of papers [3], has been to
consider the difference function (_perturbation_) $\bar{\pi}=\pi^{+}-\pi$,
which allows us to write $\pi^{1}=\pi+\bar{\pi}$ and $\pi^{2}=\pi-\bar{\pi}$.
(Recently, Di Summa [9] obtained a breakthrough result on the question of
piecewise linearity of extreme functions using this approach.) It is
convenient to build a space from the notion of perturbation functions.
Following Part V [16, section 6], we define the space

(1.4)
$\tilde{\Pi}^{\pi}=\left\\{\,\tilde{\pi}\colon{\mathbb{R}}\to{\mathbb{R}}\mid\exists\,\epsilon>0\text{
s.t.\ }\pi^{\pm}=\pi\pm\epsilon\tilde{\pi}\text{ are minimal
valid}\,\right\\}$

of _effective perturbation functions_ for the minimal valid function $\pi$ .
This is a vector space (9.0), a subspace of the space of bounded functions.
The function $\pi$ is extreme if and only if the space $\tilde{\Pi}^{\pi}$ is
trivial.

If additivity ($\Delta\pi(x,y)=0$) holds for some $(x,y)$, then by convexity
also $\Delta\tilde{\pi}(x,y)=0$ holds for every effective perturbation
$\tilde{\pi}\in\tilde{\Pi}^{\pi}$. This is also true for additivity in the
limit [3, Lemma 2.7]; see also [16, Lemma 6.1]. Because $\pi$ is assumed to be
piecewise linear, the infinite system of functional equations describing
additivity and limit-additivity of $\tilde{\pi}$ can be structured
(“combinatorialized”) according to a certain polyhedral complex [3, 16].

###  1.5. Finite-dimensional and equivariant perturbations

In Part I of the present series, Basu et al. [3] gave the first algorithm to
decide extremality of a piecewise linear function with rational breakpoints in
some “grid” (group) $G=\frac{1}{q}{\mathbb{Z}}$.

In a first step, one tests whether there exists a nontrivial perturbation for
$\pi$ in the finite-dimensional subspace of $\tilde{\Pi}^{\pi}$ that consists
of the functions $\href
https://github.com/mkoeppe/cutgeneratingfunctionology/search?q=%22def+interpolate_to_infinite_group(%22(\tilde{\pi}|_{G})$,
where $\tilde{\pi}|_{G}$ is an effective perturbation function for the
restriction $\pi|_{G}$ to the finite group problem $R_{f}(G,{\mathbb{Z}})$.

Otherwise, one may assume that $\tilde{\pi}|_{G}=0$. Under this assumption,
the interval lemma forces $\tilde{\pi}|_{C}=0$ for certain _directly covered_
intervals $C$. Basu et al.’s crucial observation was that if there are any
remaining _uncovered_ intervals, then one-dimensional families of additivity
equations impose a type of symmetry of the perturbation function. By analyzing
the required symmetry, one can construct a perturbation function and prove
nonextremality of $\pi$.

Consider the additivity equations

(1.5)
$\Delta\tilde{\pi}(x,t)=\tilde{\pi}(x)+\tilde{\pi}(t)-\tilde{\pi}(x+t)=0,\quad\text{for
$x\in D$},$

where $D$ is an interval and $t\in\frac{1}{q}{\mathbb{Z}}$ is a grid point.
Because $\tilde{\pi}(t)=0$, this simplifies to

(1.6a) $\tilde{\pi}(x)=\tilde{\pi}(x+t)\quad\text{for $x\in D$}.$ We then say
that $\tilde{\pi}$ is _invariant_ under the action of the _translation_
$\tau_{t}\colon x\mapsto x+t$ (restricted to the interval $D$). Likewise, a
second type of one-dimensional families of additivity equations simplifies to
(1.6b) $\tilde{\pi}(x)=-\tilde{\pi}(r-x)\quad\text{for $x\in D$}.$

Here a negative sign comes in. We call $\rho_{r}\colon x\mapsto r-x$ a
_reflection_. By assigning a _character_ $\chi(\tau_{t})=+1$ and
$\chi(\rho_{r})=-1$ to the translations and reflections, we can unify
equations (1.6) as

(1.7) $\tilde{\pi}(x)=\chi(\gamma)\,\tilde{\pi}(\gamma(x))\quad\text{for $x\in
D$},$

where $\gamma$ is either a translation or a reflection. We then say that
$\tilde{\pi}$ is _equivariant_ under the action of $\gamma$.

By analyzing the group $\Gamma\subset\operatorname{Aff}({\mathbb{R}})$
generated by all relevant translations and reflections, Basu et al.
constructed a universal template function
$\psi\colon{\mathbb{R}}\to{\mathbb{R}}$, a continuous piecewise linear
function with breakpoints in $\frac{1}{4q}{\mathbb{Z}}$, which is equivariant
under the action of the group $\Gamma$. Taking

(1.8) $\tilde{\pi}(x)=\begin{cases}\psi(x)&\text{for $x$ in uncovered
intervals},\\\ 0&\text{for $x$ in covered intervals}\end{cases}$

then gives an effective perturbation function. (A revised construction in Basu
et al.’s survey [6, section 8.2] gives a continuous piecewise linear function
$\tilde{\pi}$ with breakpoints in $\frac{1}{3q}{\mathbb{Z}}$.)

###  1.6. Contributions of the present paper

It has been a long-term research project to develop a complete, _grid-free_
algorithmic theory and software implementation for piecewise linear minimal
valid functions, extending the reach of the grid-based extremality test
introduced in Part I of the series [3], which we described in subsection 1.5
above. While Parts II–IV develop a grid-based theory for 2-row relaxations,
Part V of our series [16] returned to the one-row case. It introduced our
software [21] and prepared the grid-free theory with several results. Part VI
of the series [20] discussed the case of piecewise linear functions that are
discontinuous on both sides of the origin and have irrational breakpoints. The
present paper, part VII of the series, and a computational companion paper,
part VIII of the series, are the culmination of the project for the case of
piecewise linear functions of one variable.

####  1.6.1. Method: Inverse semigroups as the language of partial symmetries

Group actions are the standard language to describe symmetries of mathematical
objects. The use of group actions was fruitful in Part I of our series to
obtain the first algorithm for testing extremality. However, group actions do
not provide a complete theory of the effective perturbations. This becomes
most apparent in [3, section 5], where Basu et al. introduce a family of
extreme functions with irrational breakpoints, bhk_irrational . Here the group
$\Gamma$ generated by the translations and reflections only gives the correct
result when a certain non-group-theoretic reachability condition [3,
Assumption 5.1, Lemma 5.2] is satisfied.

The underlying reason is that the restriction of the translations and
reflections to the interval domains $D$ in (1.6) is not considered in the
reflection group. Indeed, what the translations and reflections describe is
not a full symmetry of the perturbation function, but only a _partial
symmetry_ within the uncovered intervals.

$\begin{aligned} \vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-
algo-
paper/move_tau1+}}}\circ\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-
paper/move_tau2-}}}&=\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/move_tau1+_o_tau2-}}}\\\
\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-algo-
paper/move_rhoab+}}}\circ\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-
paper/move_tau2-}}}&=\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/move_rhoab+_o_tau2-}}}\\\
\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-algo-
paper/move_tau1+}}}\circ\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-
paper/move_rhoab-}}}&=\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/move_tau1+_o_rhoab-}}}\end{aligned}$

Figure 2. Operations of the inverse semigroup I: Composition

$\begin{aligned} \vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-
algo-
paper/move_tau1+}}}^{-1}&=\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/move_tau1-}}}\\\
\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-algo-
paper/move_rhoab+}}}^{-1}&=\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/move_rhoab-}}}\end{aligned}$

Figure 3. Operations of the inverse semigroup II: Inverse

$\begin{aligned} \vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-
algo-
paper/move_tau1-}}}\circ\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-
paper/move_tau1+}}}&=\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/move_tau1-_o_tau1+}}}\\\
\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-algo-
paper/move_tau1+}}}\circ\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-
paper/move_tau1-}}}&=\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/move_tau1+_o_tau1-}}}\end{aligned}$

Figure 4. Operations of the inverse semigroup III: Composition with inverse.
The partial identities $\tau_{0}|_{D}$ are the idempotents of the inverse
semigroup.

The correct language to describe partial symmetries is the less well-known
theory of inverse-semigroup actions. An _inverse semigroup_
$(\Gamma,\circ,\cdot^{-1})$, following [22, page 7], is a semigroup, i.e., a
set $\Gamma$ closed under an associative operation $\circ$, satisfying the
additional axiom that

($\exists!$ inverse) $\begin{gathered}\text{for every $\omega\in\Gamma$, there
exists a unique element $\omega^{-1}\in\Gamma$}\\\ \text{such that
$\omega=\omega\circ\omega^{-1}\circ\omega$ and
$\omega^{-1}=\omega^{-1}\circ\omega\circ\omega^{-1}$}.\end{gathered}$

The equations in the axiom describe the familiar properties of a
pseudoinverse, but due to the required uniqueness, we will simply refer to
$\omega^{-1}$ as the _inverse_ of $\omega$. In his monograph [22], Lawson
points out that

> the relationship between inverse semigroups and partial symmetries is a
> generalization of the relation between groups and symmetries.

Concretely, inverse semigroups arise as semigroups of partial bijections of a
set, where the operation $\circ$ is the composition and $\cdot^{-1}$ is the
inverse of a partial bijection. We define the restrictions of the previously
defined translations and reflections to open intervals $D$. We denote them by
$\tau_{t}|_{D}$ and $\rho_{r}|_{D}$ and consider them as partial bijections of
${\mathbb{R}}$ to itself, with domains
$\operatorname{dom}(\tau_{t}|_{D})=D=\operatorname{dom}(\rho_{r}|_{D})$ and
images $\operatorname{im}(\tau_{t}|_{D})=\tau_{t}(D)=D+t$ and
$\operatorname{im}(\rho_{r}|_{D})=\rho_{r}(D)=r-D$. We refer to these partial
bijections as _moves_. The composition of two moves $\gamma_{1}|_{D_{1}}$ and
$\gamma_{2}|_{D_{2}}$ is defined as

(1.9)
$\gamma_{2}|_{D_{2}}\circ\gamma_{1}|_{D_{1}}=\gamma_{2}\circ\gamma_{1}|_{D_{1}\cap\gamma_{1}^{-1}(D_{2})};$

see Figure 2. The domain of the composition is either an open interval or the
empty set. (By definition, there are exactly two empty moves: the empty
translation $\tau|_{\emptyset}$ and the empty reflection $\rho|_{\emptyset}$.)
Note that the inverse of a move $\gamma|_{D}$, given by
$(\gamma|_{D})^{-1}=\gamma^{-1}|_{\gamma(D)}$, is not an inverse in a group-
theoretic sense: The compositions

(1.10)
$\gamma|_{D}\circ(\gamma|_{D})^{-1}=\tau_{0}|_{\gamma(D)}\quad\text{and}\quad(\gamma|_{D})^{-1}\circ\gamma|_{D}=\tau_{0}|_{D}$

are only _partial identities_ (restrictions of the identity $\tau_{0}$ to
intervals) and therefore not neutral elements but merely idempotents (Figure
4).

We develop methods that center around inverse semigroups of moves and their
generating sets. We study the set of moves that are respected by the effective
perturbations of a given minimal function $\pi$. We analyze the closure
properties (axioms) that it satisfies: algebraically, it is an inverse
semigroup; but additional order-theoretic and analytic closure properties come
in. Starting from an initial set (_move ensemble_) $\Omega^{0}$, we can then
form the closure with respect to the axioms. We call it the _moves closure_ of
$\Omega^{0}$ (or _closed move semigroup_ generated by $\Omega^{0}$) and denote
it by $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$.

In the first part of the paper, we develop these methods in full generality,
without using any specific properties of the Gomory–Johnson model. Then we
turn to the study of piecewise linear functions; here we make the assumption
of continuity from at least one side of the origin.

For all piecewise linear functions with rational breakpoints, we will show
that $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ has a simple structure: Its
graph consists of a finite union of line segments and rectangles. (We say that
it is _finitely presented_.) It will become clear that we can compute
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ in finitely many steps using a
completion-type algorithm, using only the algebraic and order-theoretic
axioms, by manipulating finite presentations of generating systems. However,
this algorithm is not the focus of the present paper: We defer all
computational questions to the forthcoming companion paper [14].

Instead, an important point of our paper is that finitely presented closures
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ arise in a more general context,
through the interplay of the order-theoretic, algebraic, and analytic closure
properties. Move ensembles whose graphs are connected open sets extend to open
rectangles already in the joined semigroup (4.1). Our key theorem using the
analytic properties is Theorem 7.3: Rectangles appear in the closure whenever
there is a convergent sequence of moves. (In part I of our series, we have
observed a glimpse of this phenomenon already, in a specific arithmetic
context .) Empirically, for all families of piecewise linear minimal valid
functions in the literature (see [17] for an electronic compendium), even if
the breakpoints are irrational, the closure has a finite presentation. This
includes the function bhk_irrational , which we mentioned above. Again, we
defer questions regarding the computation of this closure, which then needs to
use the additional axioms, to our forthcoming paper [14].

####  1.6.2. Result: Precise description of the space of equivariant
perturbations

Under the above assumptions, the finite presentation of
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ allows us to read off a precise
description of the space of equivariant perturbations as a direct sum
decomposition of vector subspaces (Theorem 10.6).

One component in the decomposition is a finite-dimensional space, consisting
of (possibly discontinuous) piecewise linear functions. In contrast to the
grid-based algorithm, the set of breakpoints of these functions is not fixed,
but it is computed by our algorithm. The finite-dimensional space is then
described by a system of finitely many linear equations (10.3).

Then, for each of the finitely many _uncovered components_ (defined in section
10), there is a component that is an infinite-dimensional space isomorphic to
the space of Lipschitz functions on a compact interval that vanish on the
boundary. More specifically, our algorithm computes an open interval $D$, the
_fundamental domain_ , on which we take the space of Lipschitz functions
$\tilde{\pi}$ that vanish on the boundary $\partial D$. Additionally there are
finitely many moves $\gamma_{j}|_{D}$ with pairwise disjoint images
$\gamma_{j}(D)$ that together extend the functions equivariantly to the whole
uncovered component. Outside of the component, the functions in this space are
zero. This is Theorem 10.4.

This description of the space strengthens previous results. The method of Part
I [3], described in subsection 1.5, guarantees to construct a piecewise linear
effective perturbation if the space is nontrivial; but it does not provide a
complete description of the space. A theorem regarding direct sum
decomposition appeared in [5, Theorem 3.14], but it is limited to the grid
case.

We remark that the precise description of the perturbation space of a minimal
function $\pi$ enables us to strengthen (_lift_) it by constructing a
direction in the space of effective perturbations. By our theorem, the problem
of finding such a direction decomposes into subproblems; one finite-
dimensional, the others independent variational problems over Lipschitz
functions.

####  1.6.3. Computational implications: Grid-free algorithms, natural proofs

We only sketch the computational implications of the present paper because we
will elaborate on them in our companion paper. The inverse semigroup theory
lays the foundation for grid-free algorithms for minimal valid functions,
including automated extremality tests, which are detached from the finite
group problem. A grid-free test is faster for functions whose breakpoints are
rational numbers with huge denominators; and it enables computations for
functions with irrational breakpoints. More importantly, the grid-free
algorithms can give natural extremality proofs, similar to the general proof
pattern of extremality proofs in the published literature. In this way, the
grid-free algorithms enable automated extremality proofs for smoothly
parameterized families of extreme functions, as described in [18].

###  1.7. Structure of the paper

In sections 2–4, we introduce moves as partial bijections of ${\mathbb{R}}$.
We study _ensembles_ (sets) of such moves, which can be equipped with both an
order-theoretic structure (restriction and continuation) and an algebraic
structure (inverse semigroups). In section 5 we describe how move ensembles
and semigroups describe partial symmetries of a function by a system of
functional equations. Move ensembles for bounded functions have additional
properties, which we explore in section 6. Then, in section 7, we study
closure properties that capture the additional properties of move ensembles
for continuous functions. This development culminates in the notion of _closed
move semigroups_ in subsection 7.3.

We then apply this theory to compute the effective perturbation space of a
piecewise linear minimal valid function $\pi$. In section 8, we introduce the
_initial additive move ensemble_ $\Omega^{0}$, which describes functional
equations satisfied by every effective perturbation of $\pi$. For piecewise
linear functions $\pi$, it is related to the _additive faces_ of a polyhedral
complex (section 9). Finally, in section 10, working with a finite
presentation of the closed move semigroup
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ generated by $\Omega^{0}$, we prove
the main theorem of the paper, the decomposition theorem for the space of
effective perturbations of $\pi$.

We end the paper in section 11 with a discussion of the limitations of our
approach and an outlook on the computational companion paper [14]. See the
next pages for a detailed table of contents.

###### Contents

  1. 1 Introduction
    1. 1.1 Finite group relaxations $R_{f}(P,{\mathbb{Z}})$ of integer programs and hierarchies of valid inequalities
    2. 1.2 Master problems $R_{f}(G,{\mathbb{Z}})$ and the subadditive characterization of minimal functions
    3. 1.3 Continuous interpolations of extreme functions and the infinite group problem $R_{f}({\mathbb{R}},{\mathbb{Z}})$
    4. 1.4 The space $\tilde{\Pi}^{\pi}$ of effective perturbations $\tilde{\pi}$ of a minimal valid function
    5. 1.5 Finite-dimensional and equivariant perturbations
    6. 1.6 Contributions of the present paper
      1. 1.6.1 Method: Inverse semigroups as the language of partial symmetries
      2. 1.6.2 Result: Precise description of the space of equivariant perturbations
      3. 1.6.3 Computational implications: Grid-free algorithms, natural proofs
    7. 1.7 Structure of the paper
  2. 2 Translation and reflection moves. Their algebraic and order-theoretic structure
    1. 2.1 Group $\Gamma({\mathbb{R}})$ of unrestricted translations $\tau_{t}$ and reflections $\rho_{r}$, character $\chi$
    2. 2.2 Restricted moves $\gamma|_{D}\in{}\Gamma^{\subseteq}({\mathbb{R}})$ as partial bijections of ${\mathbb{R}}$
      1. 2.2.1 Remark on the relation to pseudogroups
    3. 2.3 Graphs of moves
    4. 2.4 Restriction partial order $\subseteq$ on moves
    5. 2.5 Inverse semigroup structure $(\Gamma^{\subseteq}({\mathbb{R}}),\circ,\cdot^{-1})$
  3. 3 Ensembles $\Omega$ of moves. Their order-theoretic structure
    1. 3.1 Order-theoretic structure
      1. 3.1.1 Restriction-closed move ensembles $\Omega^{\subseteq}$
      2. 3.1.2 Join-closed move ensembles ${\Omega}^{\vee}$
      3. 3.1.3 Presentation by the set $\operatorname{Max}(\Omega^{\vee})$ of maximal elements
    2. 3.2 Move ensembles as set-valued maps ${\mathbb{R}}{}\Rightarrow{}{\mathbb{R}}$. Domains, images, restrictions
    3. 3.3 Graphs $\operatorname{Gr}(\Omega),\operatorname{Gr}_{+}(\Omega),\operatorname{Gr}_{-}(\Omega)$ of move ensembles $\Omega$
  4. 4 Inverse semigroups generated by move ensembles
    1. 4.1 Move semigroups $\Gamma$; move semigroups $\mathop{\mathrm{i{}semi}}(\Omega)$ generated by ensembles $\Omega$
    2. 4.2 Move semigroups and joins; joined move semigroups $\mathop{\mathrm{jsemi}}(\Omega)$ generated by ensembles $\Omega$
    3. 4.3 Move semigroups $\mathop{\mathrm{moves}}\nolimits(O)$, $\mathop{\mathrm{moves}}\nolimits_{+}(O)$, $\mathop{\mathrm{moves}}\nolimits_{-}(O)$ generated by connected open ensembles
  5. 5 $\Omega$-equivariant functions
    1. 5.1 Spaces of $\Omega$-equivariant functions
    2. 5.2 Join-closed semigroup $\Gamma^{\mathrm{resp}}$ of moves respected by given functions
  6. 6 Kaleidoscopic joined ensembles and bounded functions. Finite presentations by moves and components
    1. 6.1 Cauchy–Pexider functional equation $f(x)+g(y)=h(x+y)$
    2. 6.2 Kaleidoscopic move ensembles
    3. 6.3 Covered intervals, connected covered components
    4. 6.4 Presentations by moves $\Omega^{\mathrm{fin}}$ and components ${\mathcal{C}}=\\{C_{1},\dots,C_{k}\\}$
    5. 6.5 Finite presentation in reduced form $(\Omega^{\mathrm{red}},{\mathcal{C}})$
    6. 6.6 Finite presentations of generating ensembles of move semigroups
  7. 7 Limit-closed ensembles and continuous functions. Closed move semigroups
    1. 7.1 Limit-closed move ensembles $\bar{\Omega}$; closures $\mathop{\mathrm{lim}}(\Omega)$, $\mathop{\mathrm{arblim}}(\Omega)$
      1. 7.1.1 Convergence of unrestricted moves
      2. 7.1.2 Limits closure
      3. 7.1.3 Respecting limits
      4. 7.1.4 Limit-closed move semigroups
    2. 7.2 Continuous domain extension $\mathop{\mathrm{extend}_{A}}(\Omega)$
      1. 7.2.1 Extended move ensembles $\overline{\Omega}{}{}^{\vee}$
      2. 7.2.2 Domain extension and semigroups
      3. 7.2.3 Respecting extensions
    3. 7.3 Closed move semigroups, the moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega)$
  8. 8 The initial additive move ensemble $\Omega^{0}$ of a subadditive function
    1. 8.1 The initial move ensemble $\Omega^{0}$
    2. 8.2 Moves from connected open sets of additivities
  9. 9 Piecewise linear functions, polyhedral complexes, effective perturbations
    1. 9.1 Continuous and discontinuous piecewise linear functions $\pi$, complex $\mathcal{P}_{B}$
    2. 9.2 Two-dimensional polyhedral complex $\Delta\mathcal{P}$ and additive faces
    3. 9.3 Effective perturbations $\tilde{\pi}$
    4. 9.4 Closed move semigroup generated by $\Omega^{0}$, rational case
  10. 10 Perturbation space
    1. 10.1 Assumptions: Piecewise linear $\pi$, one-sided continuous at $0$, finitely presented moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$
    2. 10.2 Properties of the finitely presented moves closure
    3. 10.3 Refined breakpoints $B^{\prime}$, complex ${\mathcal{T}}$
    4. 10.4 Connected uncovered components $U_{i}$
    5. 10.5 Finite-dimensional and equivariant perturbation subspaces
    6. 10.6 Finite-dimensional linear algebra for $\tilde{\Pi}^{\pi}_{\mathcal{T}}$
    7. 10.7 Equivariant perturbation space $\tilde{\Pi}^{\pi}_{\textrm{zero}({\mathcal{T}})}$
    8. 10.8 Decomposition theorem for effective perturbations
    9. 10.9 Relation of the moves closure to the semigroup $\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi})$ of respected moves
  11. 11 Conclusion
    1. 11.1 Forthcoming computational companion paper
    2. 11.2 Limits of the approach of this paper

###### List of Figures

  1. 1 Extreme functions for finite master group problems following simple patterns that become apparent in the piecewise linear interpolations
  2. 2 Operations of the inverse semigroup I: Composition
  3. 3 Operations of the inverse semigroup II: Inverse
  4. 4 Operations of the inverse semigroup III: Composition with inverse
  5. 5 Illustrations for Theorem 4.1 and 4.1
  6. 6 Move ensemble $\mathop{\mathrm{moves}}\nolimits(\mathcal{C})$ from connected covered components $\mathcal{C}$
  7. 7 Finite presentation in reduced form. _Left,_ finite presentations $(\Omega^{\mathrm{fin}},{\mathcal{C}})$ of kaleidoscopic joined ensembles $\Omega^{\boxtimes}$. _Right,_ finite presentations $(\Omega^{\mathrm{red}},{\mathcal{C}})$ in reduced form of the same ensembles
  8. 8 Extending components by moves, 6.0. _Left,_ reduced finite presentations of a kaleidoscopic joined ensemble $\Omega^{\boxtimes}$. _Right,_ reduced finite presentations of $\mathop{\mathrm{i{}semi}}(\Omega^{\boxtimes})$.
  9. 9 Extended move ensembles $\mathop{\mathrm{extend}_{A}}(\Omega)$ of ensembles $\Omega$
  10. 10 Additive edges in $\Delta\mathcal{P}_{B}$ and the corresponding initial moves (additive moves and their inverses) in $\Omega^{0}$
  11. 11 Additivities and initial moves. _Left,_ additivities sampled from two-dimensional additive faces of $\Delta\mathcal{P}$. _Right,_ the move semigroup $\mathop{\mathrm{jsemi}}(\Omega^{0})$ generated by the initial moves
  12. 12 Additivities in $E(\pi)$ and the corresponding connected covered components of moves
  13. 13 (Left) Two-dimensional polyhedral complex $\Delta\mathcal{P}$ of the one-sided discontinuous minimal valid function $\pi=\textsf{equiv7{\textunderscore}\allowbreak{}example{\textunderscore}\allowbreak{}1()}$ from 10.0. (Right) The graph of the moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ of $\pi$
  14. 14 The function $\pi=\textsf{equiv7{\textunderscore}\allowbreak example{\textunderscore}\allowbreak xyz{\textunderscore}\allowbreak 2()}$ from 10.0, its two-dimensional polyhedral complex $\Delta\mathcal{P}$, and the refined complex $\Delta{\mathcal{T}}$
  15. 15 The function $\pi=\textsf{equiv7{\textunderscore}\allowbreak example{\textunderscore}\allowbreak xyz{\textunderscore}\allowbreak 2()}$ from 10.0 and the graph of the moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ of $\pi$
  16. 16 Moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ for the function from 10.0, $\pi=\textsf{equiv7{\textunderscore}\allowbreak minimal{\textunderscore}\allowbreak 2{\textunderscore}\allowbreak covered{\textunderscore}\allowbreak 2{\textunderscore}\allowbreak uncovered()}$
  17. 17 (Left) Finite-dimensional perturbation $\tilde{\pi}_{\mathcal{T}}$ of $\pi=\textsf{equiv7{\textunderscore}\allowbreak{}example{\textunderscore}\allowbreak{}1()}$ from 10.0. (Middle–right) Examples of equivariant perturbations $\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}$ of $\pi$.
  18. 18 Decomposition of the space of effective perturbations for the function from 10.0/10.6, $\pi=\textsf{equiv7{\textunderscore}\allowbreak example{\textunderscore}\allowbreak xyz{\textunderscore}\allowbreak 2()}$. (a) The function $\pi_{2}$. (b–d) basis of the space $\tilde{\Pi}_{\mathcal{T}}$ of finite-dimensional perturbations. (e–h) representatives of the equivariant perturbation spaces $\tilde{\Pi}^{\pi}_{U_{i}}$ for the 4 connected uncovered components $U_{i}$.
  19. 19 Decomposition of the space of effective perturbations for the function from 10.0/10.6, $\pi=\textsf{equiv7{\textunderscore}\allowbreak minimal{\textunderscore}\allowbreak 2{\textunderscore}\allowbreak covered{\textunderscore}\allowbreak 2{\textunderscore}\allowbreak uncovered()}$. (a) The function $\pi$. (b) finite-dimensional perturbation $\tilde{\pi}_{\mathcal{T}}$. (c), (d) examples of equivariant perturbations $\tilde{\pi}_{1},\tilde{\pi}_{2}$ from the direct summands.
  20. 20 Function $\pi=\textsf{equiv7{\textunderscore}\allowbreak example{\textunderscore}\allowbreak post{\textunderscore}\allowbreak 3()}$ from 10.6.
  21. 21 (Left) Two-dimensional polyhedral complex $\Delta\mathcal{P}$ of a two-sided discontinuous minimal valid function $\pi=\textsf{minimal{\textunderscore}\allowbreak{}no{\textunderscore}\allowbreak{}covered{\textunderscore}\allowbreak{}interval()}$ from 11.0. (Right) The graph of the move ensemble $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ of $\pi$

Table 1. Notation for move ensembles and semigroups $\Gamma({\mathbb{R}})$ |  Group of unrestricted translations and reflections of ${\mathbb{R}}$ | 2.1
---|---|---
$\tau_{t}$, $\rho_{r}$ |  translation, reflection |
$\gamma$ |  some element |
$\Gamma^{\subseteq}({\mathbb{R}})$ |  Inverse semigroup of translations, reflections with domains | 2.0
$\tau_{t}|_{D}$ |  translation restricted to open interval $D$ |
$\rho_{r}|_{D}$ |  reflection restricted to open interval $D$ |
$\gamma|_{D}$ |  unrestricted move restricted to open interval $D$ |
$\Omega$ |  A move ensemble: a subset of $\Gamma^{\subseteq}({\mathbb{R}})$ | 3
$\Omega^{\mathrm{inv}}$ |  … satisfying (inv) | 4.1
$\Omega^{\boxtimes}$, $\Gamma$ |  A move semigroup: an inverse subsemigroup of $\Gamma^{\subseteq}({\mathbb{R}})$ | 4.1
$\Omega^{\subseteq}$,$\Omega^{\boxtimes}$, $\Gamma^{\subseteq}$ |  A move ensemble, or semigroup, satisfying (restrict) | 3.1.1
$\Omega^{\vee}$,$\Omega^{\boxtimes}$, $\Gamma^{\vee}$ |  … satisfying (restrict), (continuation) | 3.1.2
$\Omega^{\boxtimes}$, $\Gamma^{\boxtimes}$ |  … satisfying (restrict), (continuation), (kaleido) | 6.2
$\bar{\Omega}$,$\Omega^{\boxtimes}$, $\bar{\Gamma}$ |  … satisfying limit axiom (lim) or (arblim) | 7.1
$\overline{\Omega}{}{}^{\vee}$,$\Omega^{\boxtimes}$, $\overline{\Gamma}{}{}^{\vee}$ |  … satisying (extendA) |
$\Omega^{\mathrm{fin}}$ |  A finite move ensemble ponents }220pt[ finite presentation] | 6.4
$\mathcal{C}$ |  Connected covered components
$\Omega^{\mathrm{red}}$ |  A reduced finite move ensemble | 7
${\mathbb{L}}$, ${\mathbb{M}}$ |  Families of move ensembles | 7.3
Table 2. List of axioms for move ensembles (composition) |  }220pt[  _move semigroup_ $\Gamma=\mathop{\mathrm{i{}semi}}(\Omega)$ ] |  }420pt[  _joined semigroup_ $\Gamma^{\vee}=\mathop{\mathrm{jsemi}}(\Omega)$ ] |  }720pt[  _closed move semigroup_ $\overline{\Gamma}{}^{\vee}=\mathop{\mathrm{clsemi}_{A}}(\Omega)$ ] | composition
---|---|---|---|---
(inv) |  |  |  | inv
(restrict) |  }220pt[  _joined ensemble_ $\Omega^{\vee}=\mathop{\mathrm{join}}(\Omega)$ ] |  |  | restrict
(continuation) |  |  |  | continuation
(kaleido) | _kaleidoscopic ens._ |  $\Omega^{\boxtimes}$ |  | kaleido
(lim), (arblim) | _limits-closed ens._ |  $\bar{\Omega}=\mathop{\mathrm{arblim}}(\Omega)$ |  | lim
(extendA) | _extended ensemble_ | $\overline{\Omega}{}{}^{\vee}=\mathop{\mathrm{extend}_{A}}(\Omega)$ |  | extendA

##  2\. Translation and reflection moves. Their algebraic and order-theoretic
structure

###  2.1. Group $\Gamma({\mathbb{R}})$ of unrestricted translations $\tau_{t}$
and reflections $\rho_{r}$, character $\chi$

######  Definition 2.0.

For a point $r\in{\mathbb{R}}$, define the (unrestricted) _reflection_
$\rho_{r}\colon{\mathbb{R}}\to{\mathbb{R}}$, $x\mapsto r-x$. For a vector
$t\in{\mathbb{R}}$, define the (unrestricted) _translation_
$\tau_{t}\colon{\mathbb{R}}\to{\mathbb{R}}$, $x\mapsto x+t$.

The set $\Gamma({\mathbb{R}})=\\{\,\rho_{r},\tau_{t}\mid
r\in{\mathbb{R}},\;t\in{\mathbb{R}}\,\\}$ of all translations and reflections,
with the operations of function composition $\circ$ and inverse $\cdot^{-1}$,
has the structure of a group. It is a subgroup of the group
$\operatorname{Aff}({\mathbb{R}})$ of regular affine transformations of
${\mathbb{R}}$.

To denote an element that can be either a translation or a reflection, we will
usually use the letter $\gamma$. To recover whether an element $\gamma$ is a
translation or a reflection, we assign a _character_ $\chi(\rho_{r})=-1$ to
every reflection and $\chi(\tau_{t})=+1$ to every translation. The map
$\gamma\mapsto\chi(\gamma)$ is a group character, i.e., a homomorphism, so
compositions of elements follow the rule

(2.1) $\chi(\gamma_{1}\circ\gamma_{2})=\chi(\gamma_{1})\cdot\chi(\gamma_{2}).$

###  2.2. Restricted moves $\gamma|_{D}\in{}\Gamma^{\subseteq}({\mathbb{R}})$
as partial bijections of ${\mathbb{R}}$

As we mentioned in the introduction, compared to [3], where finitely generated
subgroups of $\Gamma({\mathbb{R}})$ were used for the grid-based extremality
test algorithm, in this paper we develop a more detailed theory using
restricted moves with domains. Our terminology is based on the monograph [22]
on inverse semigroups.

We begin by restricting translations and reflections
$\gamma\in\Gamma({\mathbb{R}})$ to open interval domains
$D\subseteq{\mathbb{R}}$.

######  Definition 2.0.

Let $\gamma\in\Gamma({\mathbb{R}})$ be a translation or reflection, and let
$D\subseteq{\mathbb{R}}$ be an open interval or the empty set.

  1. (a)

The _move_ $\gamma|_{D}$ is the partial function with domain $D$ and image
$\gamma(D)$, defined by $\gamma|_{D}(x)=\gamma(x)$ for $x\in D$.

  2. (b)

The _character_ of $\gamma|_{D}$ is the character of $\gamma$.

  3. (c)

Two moves $\gamma_{1}|_{D_{1}},\gamma_{2}|_{D_{2}}$ with open interval domains
$D_{1},D_{2}$ are _equal_ if $\gamma_{1}=\gamma_{2}$ and $D_{1}=D_{2}$. A move
with an open interval domain is not _equal_ to a move with an empty domain. We
identify all translations with empty domain and denote this object by
$\tau|_{\emptyset}$. Likewise, we identify all reflections with empty domain
and denote this object by $\rho|_{\emptyset}$. The empty translation and the
empty reflection are not _equal_ ; they are distinct objects with
$\chi(\tau|_{\emptyset})=+1$ and $\chi(\rho|_{\emptyset})=-1$.

  4. (d)

The set of all moves is denoted by $\Gamma^{\subseteq}({\mathbb{R}})$.

####  2.2.1. Remark on the relation to pseudogroups

Inverse semigroups of partial homeomorphisms between open subsets of a
topological space are known as _pseudogroups_ [22, section 1.2]. However, our
theory differs in the following ways: (1) We only allow open intervals (and
the empty set) as domains of the partial functions, rather than arbitrary open
subsets. The reason for our choice will become clear in section 5, where we
will use moves to describe systems of functional equations. (2) Less
importantly, we have two empty moves, one for each possible character, rather
than a unique empty move.

###  2.3. Graphs of moves

We find it convenient to describe the graphs of moves. The _graph_ of
$\gamma|_{D}$ is the set

$\operatorname{Gr}(\gamma|_{D})=\\{\,(x,y)\in{\mathbb{R}}\times{\mathbb{R}}\mid
x\in D,\;\gamma(x)=y\,\\}.$

Figures showing the graphs have already appeared in Figure 2 and Figure 3. To
emphasize that the domains of all nonempty moves are open intervals, we
decorate the endpoints of the moves by hollow circles, indicating that the
endpoints are not part of the graphs.

###  2.4. Restriction partial order $\subseteq$ on moves

The set of all moves comes with a natural partial order.

######  Definition 2.0.

$\gamma_{1}|_{D_{1}}$ is a _restriction_ of $\gamma_{2}|_{D_{2}}$, denoted
$\gamma_{1}|_{D_{1}}\subseteq\gamma_{2}|_{D_{2}}$, if $D_{1}\subseteq D_{2}$,
$\chi(\gamma_{1})=\chi(\gamma_{2})$, and $\gamma_{1}(x)=\gamma_{2}(x)$ for
$x\in D_{1}$.

Thus, in this partial order, translations and reflections are incomparable. We
have $\tau|_{\emptyset}\subseteq\tau_{t}|_{D}$ for all translations and
likewise $\rho|_{\emptyset}\subseteq\rho_{r}|_{D}$.

######  Definition 2.0.

Given $\gamma|_{D}$ and an open interval (or empty set) $D^{\prime}\subseteq
D$, the _restriction_ of $\gamma|_{D}$ to $D^{\prime}$ is the move
$(\gamma|_{D})\big{|}_{D^{\prime}}=\gamma|_{D^{\prime}}$. Given an open
interval (or empty set) $I^{\prime}\subseteq\gamma(D)$, the _corestriction_ of
$\gamma|_{D}$ to $I^{\prime}$ is the move
${}_{I^{\prime}}\big{|}(\gamma|_{D})=\gamma|_{D\cap\gamma^{-1}(I^{\prime})}$.

###  2.5. Inverse semigroup structure
$(\Gamma^{\subseteq}({\mathbb{R}}),\circ,\cdot^{-1})$

Let $\gamma_{1}|_{D_{1}}$ and $\gamma_{2}|_{D_{2}}$ be two moves. As noted in
the introduction, their composition
$\gamma_{2}|_{D_{2}}\circ\gamma_{1}|_{D_{1}}$ is defined as
$\gamma_{2}\circ\gamma_{1}|_{D_{1}\cap\gamma_{1}^{-1}(D_{2})}$ (Figure 2). The
domain of this partial bijection is either an open interval or the empty set;
so it is again a move. It is clear that the composition operation $\circ$ is
associative. Hence the moves form a semigroup
$(\Gamma^{\subseteq}({\mathbb{R}}),\circ)$.

As we have noted already, a move $\gamma|_{D}$ also has a (unique) inverse
given by $(\gamma|_{D})^{-1}=\gamma^{-1}|_{\gamma(D)}$ (Figure 3) satisfying
the laws (1.10) (Figure 4). Hence the moves form an inverse semigroup
$(\Gamma^{\subseteq}({\mathbb{R}}),\circ,\cdot^{-1})$. Its idempotent elements
are exactly the _partial identities_ , which are restrictions of the identity
translation $\tau_{0}$ to open intervals $D$ together with the empty
translation $\tau|_{\emptyset}$. (The empty reflection is not idempotent; we
have $\rho|_{\emptyset}\circ\rho|_{\emptyset}=\tau|_{\emptyset}$.)

The inverse semigroup structure interacts with the restriction partial order
(subsection 2.4) as follows [22, Proposition 1.1.4]. If
$\gamma|_{D^{\prime}}\subseteq\gamma|_{D}$, then
$\gamma|_{D^{\prime}}^{-1}\subseteq\gamma|_{D}^{-1}$; moreover, this
restriction can be expressed as a composition with an idempotent:
$\gamma|_{D^{\prime}}=(\gamma|_{D})\big{|}_{D^{\prime}}=\gamma|_{D}\circ\tau_{0}|_{D^{\prime}}$.
Finally, if $\gamma_{i}|_{D^{\prime}_{i}}\subseteq\gamma_{i}|_{D_{i}}$ for
$i=1,2$, then
$\gamma_{2}|_{D^{\prime}_{2}}\circ\gamma_{1}|_{D^{\prime}_{1}}\subseteq\gamma_{2}|_{D_{2}}\circ\gamma_{1}|_{D_{1}}$.

##  3\. Ensembles $\Omega$ of moves. Their order-theoretic structure

Now we consider _move ensembles_ $\Omega$, i.e., arbitrary subsets of the
inverse semigroup $\Gamma^{\subseteq}({\mathbb{R}})$. We denote elements by
$\gamma|_{D}$, where $\gamma\in\Gamma({\mathbb{R}})$ is an unrestricted move
and $D$ is the domain .

###  3.1. Order-theoretic structure

####  3.1.1. Restriction-closed move ensembles $\Omega^{\subseteq}$

######  Definition 3.0.

A move ensemble $\Omega^{\subseteq}$ is _restriction-closed_ if it satisfies
the following axiom.

(restrict) $\begin{gathered}\text{If $\gamma|_{D}\in\Omega^{\subseteq}$ and
$D^{\prime}\subseteq D$ is an open interval or the empty set,}\\\ \text{then
$\gamma|_{D^{\prime}}\in\Omega^{\subseteq}$.}\end{gathered}$

For a move ensemble $\Omega$, the restriction closure
$\mathop{\mathrm{restrict}}(\Omega)$ is the smallest restriction-closed move
ensemble containing $\Omega$. (It consists of all restrictions of moves of
$\Omega$.)

######  Remark 3.0.

Throughout the paper, a superscript like $\subseteq$ in $\Omega^{\subseteq}$
indicates an axiom that the set $\Omega^{\subseteq}$ satisfies. See Table 1
for an overview of notation used in the paper.

######  Example 3.0.

The inverse semigroup $\Gamma^{\subseteq}({\mathbb{R}})$ of all restricted
translations and reflections is a restriction-closed move ensemble.

####  3.1.2. Join-closed move ensembles ${\Omega}^{\vee}$

######  Definition 3.0.

A move ensemble ${\Omega}^{\vee}$ is _(completely) join-closed_ if it
satisfies (restrict) and the following condition.

(continuation) $\begin{gathered}\text{If there is a family
$\Omega_{\mathfrak{I}}=\\{\,\gamma|_{I}\mid
I\in\mathfrak{I}\,\\}\subseteq{\Omega}^{\vee}$}\\\ \text{such that
$D=\textstyle\bigcup_{I\in\mathfrak{I}}I$ is an interval,}\\\ \text{then
$\gamma|_{D}\in{\Omega}^{\vee}$.}\end{gathered}$

######  Definition 3.0.

We define the _joined ensemble_ $\mathop{\mathrm{join}}(\Omega)$ of $\Omega$
as the smallest set of moves containing $\Omega$ that satisfies (continuation)
and (restrict).

######  Lemma 3.0.

For a move ensemble $\Omega$, the joined ensemble
$\mathop{\mathrm{join}}(\Omega)$ consists of the following moves.

(3.1)
$\begin{gathered}\Bigl{\\{}\,\gamma|_{D}\mathrel{\Big{|}}\text{$D\subseteq\bigcup_{I\in\mathfrak{I}}I$,
where $\gamma|_{I}\in\Omega$ for $I\in\mathfrak{I}$, $D$ empty or open
interval}\,\Bigr{\\}}.\end{gathered}$

###### Proof.

This set clearly satisfies (continuation) and (restrict). On the other hand,
$\mathop{\mathrm{join}}(\Omega)$ needs to contain this set. ∎

####  3.1.3. Presentation by the set $\operatorname{Max}(\Omega^{\vee})$ of
maximal elements

######  Definition 3.0.

For a move ensemble $\Omega$, let $\operatorname{Max}(\Omega)$ denote the set
of maximal elements of $\Omega$ in the restriction partial order.

######  Lemma 3.0.

A join-closed move ensemble $\Omega^{\vee}$ is equal to the restriction
closure and to the joined ensemble of its maximal elements in the restriction
partial order:

(3.2)
$\Omega^{\vee}=\mathop{\mathrm{restrict}}(\operatorname{Max}(\Omega^{\vee}))=\mathop{\mathrm{join}}(\operatorname{Max}(\Omega^{\vee}))$

###### Proof.

Let $\gamma|_{D}\in\Omega^{\vee}$. Let $\mathfrak{D}=\\{\,D^{\prime}\supseteq
D\mid\gamma|_{D^{\prime}}\in\Omega^{\vee}\,\\}$. Let
$\bar{D}=\bigcup\mathfrak{D}$, an interval. Then $\bar{D}\in\Omega^{\vee}$
because $\Omega^{\vee}$ satisfies (continuation). Moreover,
$\gamma|_{D}\subseteq\gamma|_{\bar{D}}\in\operatorname{Max}(\Omega^{\vee})$
and thus
$\gamma|_{D}\in\mathop{\mathrm{restrict}}(\operatorname{Max}(\Omega^{\vee}))$.
The other inclusions are trivial. ∎

###  3.2. Move ensembles as set-valued maps
${\mathbb{R}}{}\Rightarrow{}{\mathbb{R}}$. Domains, images, restrictions

######  Definition 3.0.

Let $\Omega$ be a move ensemble and $R$ be a disjoint union of open intervals,
$R=\bigcup_{R^{\prime}\in\mathfrak{I}}R^{\prime}$. The _restriction_
$\Omega|_{R}$ is the move ensemble consisting of the restrictions
$\gamma|_{D\cap R^{\prime}}$ whenever $\gamma|_{D}\in\Omega$,
$R^{\prime}\in\mathfrak{I}$, and either $D=\emptyset$ or $D\cap
R^{\prime}\neq\emptyset$. Similarly, we define the _corestriction_
${}_{R}|\Omega$ and the _double restriction_ ${}_{R}|\Omega|_{R}$.

In the restrictions, domains of moves are restricted to subintervals of $R$.
Note that by our definition, the restrictions contain empty moves if and only
if $\Omega$ contains empty moves. Therefore we have the following two
convenient properties:

######  Lemma 3.0.

For a move ensemble $\Omega^{\subseteq}$ that satisfies (restrict), the
restrictions satisfy (restrict), and we have

$\displaystyle\Omega^{\subseteq}|_{R}$
$\displaystyle=\bigl{\\{}\,\gamma|_{D}\in\Omega^{\subseteq}\mathrel{\big{|}}D\subseteq
R\,\bigr{\\}},$ $\displaystyle{}_{R}|\Omega^{\subseteq}\hphantom{|_{R}}$
$\displaystyle=\bigl{\\{}\,\gamma|_{D}\in\Omega^{\subseteq}\mathrel{\big{|}}\gamma(D)\subseteq
R\,\bigr{\\}},$ $\displaystyle{}_{R}|\Omega^{\subseteq}|_{R}$
$\displaystyle=\bigl{\\{}\,\gamma|_{D}\in\Omega^{\subseteq}\mathrel{\big{|}}D,\gamma(D)\subseteq
R\,\,\bigr{\\}}.$

Likewise, restrictions also preserve (continuation).

######  Lemma 3.0.

Let $\Omega^{\max}=\operatorname{Max}(\Omega^{\vee})$, where $\Omega^{\vee}$
is a joined ensemble. Then each of the restrictions $\Omega^{\max}|_{R}$,
${}_{R}|\Omega^{\max}$, and ${}_{R}|\Omega^{\max}|_{R}$ consists of the
maximal elements of $\Omega^{\vee}|_{R}$, ${}_{R}|\Omega^{\vee}$, and
${}_{R}|\Omega^{\vee}|_{R}$, respectively.

We define the domain and image of a move ensemble $\Omega$, as well as the
image of a set under the ensemble.

######  Definition 3.0.

Let $\Omega$ be a move ensemble. The _domain_ of $\Omega$ is

$\operatorname{dom}(\Omega)=\bigcup\bigl{\\{}\,D\mathrel{\big{|}}\text{$\gamma|_{D}\in\Omega$
for some $\gamma$}\,\bigr{\\}};$

the _image_ of $\Omega$ is

$\operatorname{im}(\Omega)=\bigcup\bigl{\\{}\,\gamma(D)\mathrel{\big{|}}\text{$\gamma|_{D}\in\Omega$
for some $\gamma$}\,\bigr{\\}}.$

######  Definition 3.0.

Let $\Omega$ be a move ensemble and $X\subseteq{\mathbb{R}}$ be a set. Define

$\Omega(X)=\bigl{\\{}\,\gamma(x)\mathrel{\big{|}}\gamma|_{D}\in\Omega,\;x\in
X\cap D\,\bigr{\\}}.$

######  Remark 3.0.

In these notions, a move ensemble behaves like a set-valued map
$\Omega\colon{\mathbb{R}}\Rightarrow{\mathbb{R}}$.

###  3.3. Graphs
$\operatorname{Gr}(\Omega),\operatorname{Gr}_{+}(\Omega),\operatorname{Gr}_{-}(\Omega)$
of move ensembles $\Omega$

We introduced graphs of moves in subsection 2.3. For a move ensemble $\Omega$
we define the _translation moves graph_

$\displaystyle\operatorname{Gr}_{+}(\Omega)$
$\displaystyle=\bigcup\bigl{\\{}\,\operatorname{Gr}(\gamma|_{D})\mathrel{\big{|}}\gamma|_{D}\in\Omega\text{
and }\chi(\gamma)=1\,\bigr{\\}},$ consisting of line segments with slopes
$+1$, and the _reflection moves graph_
$\displaystyle\operatorname{Gr}_{-}(\Omega)$
$\displaystyle=\bigcup\bigl{\\{}\,\operatorname{Gr}(\gamma|_{D})\mathrel{\big{|}}\gamma|_{D}\in\Omega\text{
and }\chi(\gamma)=-1\,\bigr{\\}},$

consisting of line segments with slopes $-1$. The _graph_ of $\Omega$ is

$\operatorname{Gr}(\Omega)=\operatorname{Gr}_{+}(\Omega)\cup\operatorname{Gr}_{-}(\Omega).$

We also define the _character conflict graph_ ,

$\operatorname{Gr}_{\pm}(\Omega)=\operatorname{Gr}_{+}(\Omega)\cap\operatorname{Gr}_{-}(\Omega).$

The map
$\Omega\mapsto(\operatorname{Gr}_{+}(\Omega),\operatorname{Gr}_{-}(\Omega))$
becomes an injection if restricted to the join-closed move ensembles
$\Omega^{\vee}$. Hence these pairs of graphs faithfully represent all join-
closed move ensembles. (In our figures showing these graphs, we superimpose
the translation graph (blue) and reflection graph (red).)

We can go back from graphs to ensembles using the following notation.

######  Definition 3.0.

Let $O\subseteq{\mathbb{R}}^{2}$. We define the (join-closed) move ensembles

$\displaystyle\mathop{\mathrm{moves}}\nolimits_{+}(O)$
$\displaystyle=\bigl{\\{}\,\tau_{t}|_{D}\mathrel{\big{|}}\operatorname{Gr}(\tau_{t}|_{D})\subset
O,\;D\text{ an open interval or empty}\,\bigr{\\}},$
$\displaystyle\mathop{\mathrm{moves}}\nolimits_{-}(O)$
$\displaystyle=\bigl{\\{}\,\rho_{r}|_{D}\mathrel{\big{|}}\operatorname{Gr}(\rho_{r}|_{D})\subset
O,\;D\text{ an open interval or empty}\,\bigr{\\}},$
$\displaystyle\mathop{\mathrm{moves}}\nolimits(O)$
$\displaystyle=\bigl{\\{}\,\gamma|_{D}\mathrel{\big{|}}\operatorname{Gr}(\gamma|_{D})\subset
O,\;D\text{ an open interval or empty}\,\bigr{\\}}.$

Thus,
$\mathop{\mathrm{moves}}\nolimits(O)=\mathop{\mathrm{moves}}\nolimits_{+}(O)\cup\mathop{\mathrm{moves}}\nolimits_{-}(O)$.

##  4\. Inverse semigroups generated by move ensembles

Now we turn to the study of inverse semigroups generated by move ensembles.

###  4.1. Move semigroups $\Gamma$; move semigroups
$\mathop{\mathrm{i{}semi}}(\Omega)$ generated by ensembles $\Omega$

######  Definition 4.0.

A move ensemble $\Gamma$ is a _move semigroup_ (or, an _inverse subsemigroup_
of $\Gamma^{\subseteq}({\mathbb{R}})$) if it satisfies the following axioms:

(composition)
$\displaystyle\gamma^{\prime}|_{D^{\prime}}\circ\gamma|_{D}\in\Gamma\text{ for
all }\gamma|_{D},\gamma^{\prime}|_{D^{\prime}}\in\Gamma,$ (inv)
$\displaystyle(\gamma|_{D})^{-1}\in\Gamma\text{ for all
}\gamma|_{D}\in\Gamma.$

######  Definition 4.0.

For a move ensemble $\Omega$, the _move semigroup_
$\mathop{\mathrm{i{}semi}}(\Omega)$ generated by $\Omega$ is the smallest move
semigroup containing $\Omega$.

######  Definition 4.0.

A move semigroup $\Gamma$ is _finitely generated_ if there exists a finite set
$\Omega$ such that $\Gamma=\mathop{\mathrm{i{}semi}}(\Omega)$.

######  Lemma 4.0.

Let ${\Omega}^{\mathrm{inv}}$ be a move ensemble satisfying (inv). Then
$\mathop{\mathrm{i{}semi}}({\Omega}^{\mathrm{inv}})$ is the set of all finite
compositions $\gamma^{k}|_{D_{k}}\circ\dots\circ\gamma^{1}|_{D_{1}}$ of moves
$\gamma^{i}|_{D_{i}}\in{\Omega}^{\mathrm{inv}}$.

######  Remark 4.0.

Since the domains of moves in $\Omega$ are empty or open intervals, any move
$\gamma|_{D}\in\mathop{\mathrm{i{}semi}}(\Omega)$ also has a domain $D$ that
is empty or an open interval. If $\gamma|_{D}\in\Omega$, then the idempotent
$(\gamma|_{D})^{-1}\circ\gamma|_{D}=\tau_{0}|_{D}$ is an element of
$\mathop{\mathrm{i{}semi}}(\Omega)$. The inverse semigroup generated by the
empty set is the empty set.

###  4.2. Move semigroups and joins; joined move semigroups
$\mathop{\mathrm{jsemi}}(\Omega)$ generated by ensembles $\Omega$

Move semigroups generated by joined ensembles are not automatically join-
closed. On the other hand, joining does preserve the semigroup properties.

######  Lemma 4.0.

Let $\Gamma$ be a move semigroup. Then the joined ensemble
$\mathop{\mathrm{join}}(\Gamma)$ is a move semigroup. In particular, for a
move ensemble $\Omega$, we have

$\mathop{\mathrm{join}}(\mathop{\mathrm{i{}semi}}(\Omega))=\mathop{\mathrm{i{}semi}}(\mathop{\mathrm{join}}(\mathop{\mathrm{i{}semi}}(\Omega))).$

###### Proof.

Let
$\gamma|_{D},\gamma^{\prime}|_{D^{\prime}}\in\mathop{\mathrm{join}}(\Gamma)$.
We first show that $\mathop{\mathrm{join}}(\Gamma)$ satisfies the axiom
(composition). By equation (3.1), there exist collections $\mathfrak{I}$ and
$\mathfrak{I}^{\prime}$ of open intervals, such that
$D\subseteq\bigcup_{I\in\mathfrak{I}}I$,
$D^{\prime}\subseteq\bigcup_{I^{\prime}\in\mathfrak{I}^{\prime}}I^{\prime}$,
and $\gamma|_{I},\gamma^{\prime}|_{I^{\prime}}\in\Gamma$ for all
$I\in\mathfrak{I},I^{\prime}\in\mathfrak{I}^{\prime}$. We know that

$\gamma^{\prime}|_{I^{\prime}}\circ\gamma|_{I}=(\gamma^{\prime}\circ\gamma)|_{\gamma^{-1}(I^{\prime})\cap
I}\in\Gamma,\text{ for all }I\in\mathfrak{I}\text{ and
}I^{\prime}\in\mathfrak{I}^{\prime},$

since $\Gamma$ satisfies (composition), and that

$\gamma^{-1}(D^{\prime})\cap
D\subseteq\gamma^{-1}\bigl{(}\bigcup_{I^{\prime}\in\mathfrak{I}^{\prime}}I^{\prime}\bigr{)}\cap\bigl{(}\bigcup_{I\in\mathfrak{I}}I\bigr{)}=\bigcup_{I\in\mathfrak{I},\,I^{\prime}\in\mathfrak{I}^{\prime}}\bigl{(}\gamma^{-1}(I^{\prime})\cap
I\bigr{)}.$

Therefore, by equation (3.1),
$\gamma^{\prime}|_{D^{\prime}}\circ\gamma|_{D}=(\gamma^{\prime}\circ\gamma)|_{\gamma^{-1}(D^{\prime})\cap
D}\in\mathop{\mathrm{join}}(\Gamma)$.

We will now show that $\mathop{\mathrm{join}}(\Gamma)$ satisfies axiom (inv).
We know that $(\gamma|_{I})^{-1}=\gamma^{-1}|_{\gamma(I)}\in\Gamma\text{ for
all }I\in\mathfrak{I},$ since $\Gamma$ satisfies (inv), and that
$\gamma(D)\subseteq\gamma(\bigcup_{I\in\mathfrak{I}}I)=\bigcup_{I\in\mathfrak{I}}\gamma(I)$.
Therefore,
$(\gamma|_{D})^{-1}=\gamma^{-1}|_{\gamma(D)}\in\mathop{\mathrm{join}}(\Gamma)$.
We conclude that $\mathop{\mathrm{join}}(\Gamma)$ is a move semigroup, so
$\mathop{\mathrm{join}}(\Gamma)=\mathop{\mathrm{i{}semi}}(\mathop{\mathrm{join}}(\Gamma))$.
∎

######  Definition 4.0.

Let $\Omega$ be a move ensemble. Then the _joined move semigroup_ of $\Omega$
is defined as

$\mathop{\mathrm{jsemi}}(\Omega)=\mathop{\mathrm{join}}(\mathop{\mathrm{i{}semi}}(\Omega)).$

###  4.3. Move semigroups $\mathop{\mathrm{moves}}\nolimits(O)$,
$\mathop{\mathrm{moves}}\nolimits_{+}(O)$,
$\mathop{\mathrm{moves}}\nolimits_{-}(O)$ generated by connected open
ensembles

Finitely generated inverse semigroups, as defined in subsection 4.1, are not
general enough for our purposes. As we will see later, we need to consider
move ensembles $\Omega$ whose graphs are open connected sets. They generate
inverse semigroups $\mathop{\mathrm{i{}semi}}(\Omega)$ that are not finitely
generated. However, they have the following simple structure (see Figure 5).

######  Theorem 4.1.

Let $\Omega$ be an ensemble of moves. Let $O\subseteq{\mathbb{R}}^{2}$ be a
connected open set. Let
$D=\operatorname{dom}(O):=\operatorname{dom}(\mathop{\mathrm{moves}}\nolimits(O))$
and
$I=\operatorname{im}(O):=\operatorname{im}(\mathop{\mathrm{moves}}\nolimits(O))$.

  1. (1)

If $\operatorname{Gr}_{+}(\Omega)$ contains $O$, then
$\operatorname{Gr}_{+}(\mathop{\mathrm{i{}semi}}(\Omega))$ contains $(D\cup
I)\times(D\cup I)$.

  2. (2)

If $\operatorname{Gr}_{-}(\Omega)$ contains $O$, then
$\operatorname{Gr}_{-}(\mathop{\mathrm{i{}semi}}(\Omega))$ contains $(D\times
I)\cup(I\times D)$ and $\operatorname{Gr}_{+}(\Omega)$ contains $(D\times
D)\cup(I\times I)$.

  3. (3)

If $\operatorname{Gr}_{\pm}(\Omega)$ contains $O$, then
$\operatorname{Gr}_{\pm}(\mathop{\mathrm{i{}semi}}(\Omega))$ contains $(D\cup
I)\times(D\cup I)$.

$\vbox{\hbox{\includegraphics[height=143.09538pt]{graphics-for-algo-
paper/open_sets_of_tau_sampled-}}}\xmapsto{\mbox{\normalsize$\;\mathop{\mathrm{jsemi}}\;$}}\vbox{\hbox{\includegraphics[height=143.09538pt]{graphics-
for-algo-paper/open_sets_of_tau_sampled-completion-final}}}$
$\vbox{\hbox{\includegraphics[height=143.09538pt]{graphics-for-algo-
paper/open_sets_of_rho_sampled-}}}\xmapsto{\mbox{\normalsize$\;\mathop{\mathrm{jsemi}}\;$}}\vbox{\hbox{\includegraphics[height=143.09538pt]{graphics-
for-algo-paper/open_sets_of_rho_sampled-completion-final}}}$
$\vbox{\hbox{\includegraphics[height=143.09538pt]{graphics-for-algo-
paper/open_sets_of_rho2_sampled-}}}\xmapsto{\mbox{\normalsize$\;\mathop{\mathrm{jsemi}}\;$}}\vbox{\hbox{\includegraphics[height=143.09538pt]{graphics-
for-algo-paper/open_sets_of_rho2_sampled-completion-final}}}$
$\vbox{\hbox{\includegraphics[height=143.09538pt]{graphics-for-algo-
paper/open_sets_of_moves_sampled-}}}\xmapsto{\mbox{\normalsize$\;\mathop{\mathrm{jsemi}}\;$}}\vbox{\hbox{\includegraphics[height=143.09538pt]{graphics-
for-algo-paper/open_sets_of_moves_sampled-completion-final}}}$

Figure 5. Illustrations for Theorem 4.1 and 4.1. Here, only a finite set of
moves is considered. If, however, an infinite set is used by considering all
moves in the $O$-shaped set in the left plots, then the entire rectangles
would be filled in on the right plots.

###### Proof.

Part 2. We show that (2a)
$\operatorname{Gr}_{-}(\mathop{\mathrm{i{}semi}}(\Omega))$ contains $D\times
I$ and (2b) $\operatorname{Gr}_{+}(\mathop{\mathrm{i{}semi}}(\Omega))$
contains $D\times D$; the other two containments of $I\times D$ and $I\times
I$ follow from the fact that $\mathop{\mathrm{i{}semi}}(\Omega)$ is closed
under inverse.

Let $(x,y),(x^{\prime},y^{\prime})\in O$ be two arbitrary points in the
connected open set $O$. Since there is a path between $(x,y)$ and
$(x^{\prime},y^{\prime})$ contained in $O$, and the path is compact, it is
covered by finitely many open $\ell_{\infty}$-balls
$O_{1},\dots,O_{n}\subseteq O$ with $(x_{1},y_{1}):=(x,y)\in O_{1}$,
$(x_{2},y_{2})\in O_{1}\cap O_{2},\dots,(x_{n},y_{n})\in O_{n-1}\cap O_{n}$
and $(x_{n+1},y_{n+1}):=(x^{\prime},y^{\prime})\in O_{n}$. Since
$(x_{1},y_{1}),(x_{2},y_{1}),(x_{2},y_{2}),\allowbreak\dots,\allowbreak(x_{n},y_{n}),\allowbreak(x_{n+1},y_{n}),\allowbreak(x_{n+1},y_{n+1})\in
O$, there exist
$\rho_{r_{1}}|_{D_{1}},\,\rho_{r_{1}^{\prime}}|_{D_{1}^{\prime}},\,\rho_{r_{2}}|_{D_{2}},\allowbreak\dots,\allowbreak\rho_{r_{n}}|_{D_{n}},\,\allowbreak\rho_{r_{n}^{\prime}}|_{D_{n}^{\prime}}\allowbreak\text{
and }\allowbreak\rho_{r_{n+1}}|_{D_{n+1}}\in\Omega$ such that
$\rho_{r_{i}}|_{D_{i}}(x_{i})=y_{i}$ for $i=1,\dots,n+1$ and
$\rho_{r_{i}^{\prime}}|_{D_{i}^{\prime}}(x_{i+1})=y_{i}$ for $i=1,\dots,n$.
Notice that the inverse restricted reflections
${(\rho_{r_{i}^{\prime}}|_{D_{i}^{\prime}})}^{-1}\in\mathop{\mathrm{i{}semi}}(\Omega)$
with ${(\rho_{r_{i}^{\prime}}|_{D_{i}^{\prime}})}^{-1}(y_{i})=x_{i+1}$ for
$i=1,\dots,n$. We have

$x_{1}\xmapsto{\rho_{r_{1}}|_{D_{1}}}y_{1}\xmapsto{{(\rho_{r_{1}^{\prime}}|_{D_{1}^{\prime}})}^{-1}}x_{2}\mapsto\cdots\mapsto
y_{n}\xmapsto{{(\rho_{r_{n}^{\prime}}|_{D_{n}^{\prime}})}^{-1}}x_{n+1}\xmapsto{\rho_{r_{n+1}}|_{D_{n+1}}}y_{n+1}.$

The composition of the $2n+1$ reflections

$\rho_{r}|_{D_{r}}:=\rho_{r_{n+1}}|_{D_{n+1}}\circ{(\rho_{r_{n}^{\prime}}|_{D_{n}^{\prime}})}^{-1}\circ\rho_{r_{n}}|_{D_{n}}\circ\dots\circ(\rho_{r_{1}^{\prime}}|_{D_{1}^{\prime}})^{-1}\circ\rho_{r_{1}}|_{D_{1}}$

is a restricted reflection, satisfying that
$\rho_{r}|_{D_{r}}\in\mathop{\mathrm{i{}semi}}(\Omega)$ and
$\rho_{r}|_{D_{r}}(x)=y^{\prime}$. Therefore, (2a) holds. The composition of
the $2n$ reflections

$\tau_{t}|_{D_{t}}:={(\rho_{r_{n}^{\prime}}|_{D_{n}^{\prime}})}^{-1}\circ\rho_{r_{n}}|_{D_{n}}\circ\dots\circ(\rho_{r_{1}^{\prime}}|_{D_{1}^{\prime}})^{-1}\circ\rho_{r_{1}}|_{D_{1}}$

is a restricted translation, satisfying that
$\tau_{t}|_{D_{t}}\in\mathop{\mathrm{i{}semi}}(\Omega)$ and
$\tau_{t}|_{D_{t}}(x)=x^{\prime}$. Therefore, (2b) holds.

Part 1 follows exactly the same proof as part 2 using instead restricted
translations
$\tau_{t_{1}}|_{D_{1}},\,\tau_{t_{1}^{\prime}}|_{D_{1}^{\prime}},\,\tau_{t_{2}}|_{D_{2}},\dots,\tau_{t_{n}}|_{D_{n}},\,\tau_{t_{n}^{\prime}}|_{D_{n}^{\prime}},\,\tau_{t_{n+1}}|_{D_{n+1}}\in\Omega$.

Part 3. Let $(x,y),(x^{\prime},y^{\prime})\in O$. By part 1 and 2, there exist
restricted translation and reflection
$\tau_{t}|_{D_{t}},\rho_{r}|_{D_{r}}\in\mathop{\mathrm{i{}semi}}(\Omega)$ such
that $x\xmapsto{\tau_{t}|_{D_{t}}}y\xmapsto{\rho_{r}|_{D_{r}}}x^{\prime}$. The
composition $\rho_{r}|_{D_{r}}\circ\tau_{t}|_{D_{t}}$ is a restricted
reflection in $\mathop{\mathrm{i{}semi}}(\Omega)$. Therefore,
$\operatorname{Gr}_{-}(\mathop{\mathrm{i{}semi}}(\Omega))$ contains $D\times
D$. By part 1, part 2 and the fact that $\mathop{\mathrm{i{}semi}}(\Omega)$ is
closed under inverse, we obtain that part 3 holds. ∎

The following corollary sharpens the result.

######  Corollary 4.1.

Let $O\subseteq{\mathbb{R}}^{2}$ be a connected open set, with
$D=\operatorname{dom}(O)=\operatorname{dom}(\mathop{\mathrm{moves}}\nolimits(O))$
and
$I=\operatorname{im}(O)=\operatorname{im}(\mathop{\mathrm{moves}}\nolimits(O))$.

$\begin{array}[]{rr@{\:}ll}$(1)$&\mathop{\mathrm{jsemi}}(\mathop{\mathrm{moves}}\nolimits_{+}(O))=\>&\mathop{\mathrm{moves}}\nolimits_{+}\left((D\cup
I)\times(D\cup I)\right).&\\\
$(2a)$&\mathop{\mathrm{jsemi}}(\mathop{\mathrm{moves}}\nolimits_{-}(O))=\>&\mathop{\mathrm{moves}}\nolimits_{-}((D\times
I)\cup(I\times D))\cup{}\\\ &\>&\mathop{\mathrm{moves}}\nolimits_{+}((D\times
D)\cup(I\times I)),&\text{ if }D\cap I=\emptyset.\\\
$(2b)$&\mathop{\mathrm{jsemi}}(\mathop{\mathrm{moves}}\nolimits_{-}(O))=\>&\mathop{\mathrm{moves}}\nolimits\left((D\cup
I)\times(D\cup I)\right),&\text{ if }D\cap I\neq\emptyset.\\\
$(3)$&\mathop{\mathrm{jsemi}}(\mathop{\mathrm{moves}}\nolimits(O))=\>&\mathop{\mathrm{moves}}\nolimits\left((D\cup
I)\times(D\cup I)\right).&\end{array}$

###### Proof.

By applying Theorem 4.1-(1), (2) and (3) to
$\Omega=\mathop{\mathrm{moves}}\nolimits_{+}(O)$,
$\Omega=\mathop{\mathrm{moves}}\nolimits_{-}(O)$ and
$\Omega=\mathop{\mathrm{moves}}\nolimits(O)$, we obtain that
$\mathop{\mathrm{jsemi}}(\Omega)$ on the left-hand side of the equation in
(1), (2a) and (3) contains the move ensemble on the right-hand side,
respectively. In case (2b) where $D\cap I\neq\emptyset$, by applying Theorem
4.1-(2) to $\Omega=\mathop{\mathrm{moves}}\nolimits_{-}(O)$, we have that
$\mathop{\mathrm{jsemi}}(\Omega)$ contains
$\mathop{\mathrm{moves}}\nolimits\left((D\cup I)\times(D\cap I)\right)$. It
then follows from Theorem 4.1-(3) that $\mathop{\mathrm{jsemi}}(\Omega)$
contains the right-hand side of (2b). Conversely, the right-hand side of the
equation in each case is a joined move semigroup that contains $\Omega$.
Hence, the equality holds. ∎

######  Remark 4.1.

Theorem 4.1 suggests to consider the following class of generating ensembles
for inverse semigroups. Take a finite ensemble
$\Omega^{\mathrm{fin}}=\\{\gamma^{1}|_{D_{1}},\dots,\gamma^{n}|_{D_{n}}\\}$
together with a finite list of infinite ensembles of the form
$\mathop{\mathrm{moves}}\nolimits_{+}(D_{i}\times I_{i})$, $i=n+1,\dots,n+m$
and $\mathop{\mathrm{moves}}\nolimits_{-}(D_{i}\times I_{i})$,
$i=n+m+1,\dots,n+m+\ell$, where $D_{i}$ and $I_{i}$ are open intervals.
However, we suppress the details of this. In section 6, an additional
assumption will allow us to use a more convenient class of generating
ensembles.

##  5\. $\Omega$-equivariant functions

###  5.1. Spaces of $\Omega$-equivariant functions

Move ensembles encode a system of functional equations as follows.

######  Definition 5.0.

Let $\Omega$ be a move ensemble and let
$\theta\colon{\mathbb{R}}\to{\mathbb{R}}$ be a function.

  1. (a)

We say that $\theta$ is _affinely $\Omega$-equivariant_ (in short, $\theta$
_respects_ $\Omega$) provided that for every $\gamma|_{D}\in\Omega$ there
exists a constant $c_{\gamma|_{D}}^{\theta}$ such that

(5.1)
$\theta(\gamma|_{D}(x))=\chi(\gamma)\theta(x)+c^{\theta}_{\gamma|_{D}}\quad\text{
for }x\in D,$

where $\chi(\gamma)=\pm 1$ is the character of $\gamma$.

  2. (b)

If all constants $c_{\gamma|_{D}}^{\theta}$ can be chosen to be zero, then we
say that $\theta$ is _$\Omega$ -equivariant_ (or, _equivariant under the
action of $\Omega$_).

Throughout the paper, we will be working with affinely $\Omega$-equivariant
functions. At the very end, in section 10, an important space of
$\Omega$-equivariant functions will appear.

######  Remark 5.0.

It now becomes clear why singletons $\\{x\\}$ are not allowed as the domain
$D$ of a move. The functional equation (5.1) would degenerate to a single
equation with an independent constant $c^{\theta}_{\gamma|_{\\{x\\}}}$. The
equation and the constant can be eliminated from the system.

Some trivial relations between the constants $c^{\theta}_{\gamma|_{D}}$ are
induced by the restriction partial order on moves (subsection 2.4). If
$\emptyset\neq D\subset D^{\prime}$, thus
$\gamma|_{D}\subseteq\gamma|_{D^{\prime}}$ and $D\neq\emptyset$, then
necessarily $c^{\theta}_{\gamma|_{D}}=c^{\theta}_{\gamma|_{D^{\prime}}}$.

Thus it is natural to work with restriction-closed ensembles, as defined in
subsubsection 3.1.1.

######  Lemma 5.0.

For a space $\Theta$ of functions, we denote by $\Theta^{\Omega}$ the set of
affinely $\Omega$-equivariant functions in $\Theta$. If $\Theta$ is a vector
space, then so is $\Theta^{\Omega}$.

###### Proof.

Let $\theta_{1},\theta_{2}\in\Theta$ and $a_{1},a_{2}\in{\mathbb{R}}$. Let
$\theta=a_{1}\theta_{1}+a_{2}\theta_{2}$. Then $\theta\in\Theta$. Moreover,
let $c^{\theta_{1}}_{\gamma|_{D}}$ for $\gamma|_{D}\in\Omega$ and
$c^{\theta_{2}}_{\gamma|_{D}}$ for $\gamma|_{D}\in\Omega$ be the families of
constants that satisfy (5.1) for $\theta_{1}$ and $\theta_{2}$, respectively.
Then
$c^{\theta}_{\gamma|_{D}}=a_{1}c^{\theta_{1}}_{\gamma|_{D}}+a_{2}c^{\theta_{2}}_{\gamma|_{D}}$
for $\gamma|_{D}\in\Omega$ is a family of constants that satisfy (5.1) for
$\theta$. ∎

###  5.2. Join-closed semigroup $\Gamma^{\mathrm{resp}}$ of moves respected by
given functions

######  Definition 5.0.

For a function $\theta\colon\operatorname{dom}(\theta)\to{\mathbb{R}}$, we
denote the ensemble of moves respected by $\theta$ as

$\Gamma^{\mathrm{resp}}(\theta)=\bigl{\\{}\,\gamma|_{D}\in\Gamma^{\subseteq}({\mathbb{R}})\mathrel{\big{|}}D,\gamma(D)\subseteq\operatorname{dom}(\theta),\;\text{$\exists
c^{\theta}_{\gamma|_{D}}\in{\mathbb{R}}$ s.t.\leavevmode\nobreak\
\eqref{eq:additivity-equation-for-move} holds}\,\bigr{\\}}.$

(Clearly $\Gamma^{\mathrm{resp}}(\theta)$ is the largest move ensemble that
$\theta$ respects.) For a space $\Theta^{\prime}$ of functions, we denote
$\Gamma^{\mathrm{resp}}(\Theta^{\prime})=\bigcap_{\theta\in\Theta^{\prime}}\Gamma^{\mathrm{resp}}(\theta)$.

######  Theorem 5.1.

Let $\Omega$ be a move ensemble. If a function $\theta$ respects $\Omega$,
then $\theta$ respects the joined semigroup $\mathop{\mathrm{jsemi}}(\Omega)$.

To prove this, we use the following lemma.

######  Lemma 5.1.

Let $\mathfrak{I}$ be a collection of open intervals that cover the open
interval $(l,u)$. If a function $g$ is constant over each interval $I$ from
the collection $\mathfrak{I}$, then $g$ is constant over $(l,u)$.

###### Proof.

Let $m=\frac{l+u}{2}$ and $a=g(m)$. Consider the interval
$J=\\{\,y\in(l,m)\mid g(x)=a\text{ for all }x\in[y,m]\,\\}$. Since $m$ is
contained in some open interval $I\in\mathfrak{I}$ and $g(x)=a$ for $x\in I$,
we know that $J$ is non-empty. Let $l^{\prime}=\inf J$. We now show that
$l=l^{\prime}$. Suppose that $l\neq l^{\prime}$. Then there exists an open
interval $I\in\mathfrak{I}$ such that $l^{\prime}\in I$, and $g$ is constant
over $I$. Since $I\cap J\neq\emptyset$ and $g(x)=a$ for $x\in J$, we have that
$g(x)=a$ for $x\in I$, a contradiction to $l^{\prime}=\inf J$. Hence $g(x)=a$
for all $l<x\leq m$. Similarly, one shows that $g(x)=a$ for all $m\leq x<u$.
Therefore, $g$ is constant over $(l,u)$. ∎

###### Proof of Theorem 5.1.

Let $\gamma|_{D}\in\mathop{\mathrm{jsemi}}(\Omega)$. Thus, there exists a
collection $\mathfrak{I}$ of open intervals, such that
$D=\bigcup_{I\in\mathfrak{I}}I$ and
$\gamma|_{I}\in\mathop{\mathrm{i{}semi}}(\Omega)$ for each $I\in\mathfrak{I}$.

Define $g(x)=\theta(\gamma(x))-\chi(\gamma)\theta(x)$ for $x\in D$. We first
show that $g$ is constant over each interval $I\in\mathfrak{I}$. Let
$I\in\mathfrak{I}$. Since $\gamma|_{I}\in\mathop{\mathrm{i{}semi}}(\Omega)$,
we can write it in the form
$\gamma|_{I}=\gamma_{k}|_{D_{k}}\circ\gamma_{k-1}|_{D_{k-1}}\circ\dots\circ\gamma_{1}|_{D_{1}}$,
where
$\gamma_{1}|_{D_{1}},\gamma_{2}|_{D_{2}},\dots,\gamma_{k}|_{D_{k}}\in\Omega$.
Let $x_{0}\in I$ and denote $x_{i}=\gamma_{i}(x_{i-1})$ for $i=1,2,\dots,k$.
Then, $x_{i}\in D_{i+1}$ for $i=0,1,\dots,k-1$, and
$x_{k}=\gamma|_{I}(x_{0})=\gamma(x_{0})$. Since $\theta$ respects $\Omega$,
for $i=1,2,\dots,k$, we have that

$\theta(x_{i})=\chi(\gamma_{i})\theta(x_{i-1})+c^{\theta}_{i},$

where the constants $c^{\theta}_{i}$ are independent of the choice of
$x_{0}\in I$. We also know that
$\chi(\gamma)=\chi(\gamma_{1})\chi(\gamma_{2})\dots\chi(\gamma_{k})$.
Therefore,

$\displaystyle g(x_{0})$
$\displaystyle=\theta(\gamma(x_{0}))-\chi(\gamma)\theta(x_{0})$
$\displaystyle=\theta(x_{k})-\chi(\gamma_{k})\chi(\gamma_{k-1})\dots\chi(\gamma_{1})\theta(x_{0})=\sum_{j=1}^{k}{\left(\prod_{i=j+1}^{k}{\chi(\gamma_{i})}\right)c_{j}^{\theta}}$

is constant for $x_{0}\in I$.

Then, it follows from 5.1 that $g$ is constant over $D$. ∎

######  Corollary 5.1.

For a function $\theta$, the ensemble $\Gamma^{\mathrm{resp}}(\theta)$ defined
in 5.0 is a join-closed move semigroup. The same holds for the ensemble
$\Gamma^{\mathrm{resp}}(\Theta^{\prime})$, where $\Theta^{\prime}$ is a space
of functions.

##  6\. Kaleidoscopic joined ensembles and bounded functions. Finite
presentations by moves and components

###  6.1. Cauchy–Pexider functional equation $f(x)+g(y)=h(x+y)$

Recall from subsection 5.1 that move ensembles encode systems of functional
equations. We now bring a first result on functional equations to use. The
following result on the Cauchy–Pexider functional equation on bounded domains
appeared in [5, Theorem 4.3]. Here we state it for functions of a single real
variable. It is a variant of the Gomory–Johnson interval lemma, which has been
used throughout the extreme functions literature. Note that it requires a weak
assumption regarding the function space. Boundedness is sufficient; see [5]
for a more detailed discussion.

######  Lemma 6.0 (Convex additivity domain lemma).

Let $f,g,h\colon{\mathbb{R}}\to{\mathbb{R}}$ be bounded functions and let
$E\subseteq{\mathbb{R}}^{2}$ be open, convex, and bounded. Suppose that

$f(x)+g(y)=h(x+y)\quad\text{ for all }(x,y)\in E.$

Define the projections

$p_{1}(x,y)=x,\quad p_{2}(x,y)=y,\quad p_{3}(x,y)=x+y$

as functions from ${\mathbb{R}}^{2}$ to ${\mathbb{R}}$. Then $f,g,h$ are
affine with the same slopes on the domains $p_{1}(E),p_{2}(E),p_{3}(E)$,
respectively.

###  6.2. Kaleidoscopic move ensembles

When we are only interested in _bounded_ functions that respect a move
ensemble $\Omega$, then it follows from 6.0 that we can replace $\Omega$ by a
move ensemble $\Omega^{\boxtimes}$ with more convenient properties.

######  Lemma 6.0.

Let $\theta\colon{\mathbb{R}}\to{\mathbb{R}}$ be a bounded function. Let
$D,I\subseteq{\mathbb{R}}$ be open intervals. The following are equivalent:

  1. (1)

$\theta$ respects $\mathop{\mathrm{moves}}\nolimits_{+}(D\times I)$,

  2. (2)

$\theta$ respects $\mathop{\mathrm{moves}}\nolimits_{-}(D\times I)$,

  3. (3)

$\theta$ respects $\mathop{\mathrm{moves}}\nolimits(D\times I)$,

  4. (4)

$\theta$ is affine on $D$ and $I$ with the same slope.

###### Proof.

We first show that (1) implies (4). By assumption, the function $\theta$
satisfies equation (5.1) for all $\tau_{t}|_{D_{t}}$, where $t\in\\{\,y-x\mid
x\in D,\;y\in I\,\\}$ and $D_{t}=\\{\,x\in D\mid x+t\in I\,\\}$. Thus, there
exists a function $c\colon I+(-D)\to{\mathbb{R}}$ such that

$\theta(x+t)=\theta(x)+c(t)\qquad\text{for all $(x,x+t)\in D\times I$}.$

The function $c$ is bounded because $\theta$ is. Then, by Lemma 6.0 with
$f=h=\theta$ and $g=c$, we have that $\theta$ affine on $D$ and $I$ with the
same slope. The proofs that each of (2) and (3) implies (4) are similar; we
omit them.

Now we show that (4) implies (1). Fix $t=y-x$ for some $x\in D,y\in I$. Since
$\theta$ is affine on $D$ and $I$ with the same slope, there exist scalars
$a,b,b^{\prime}$ such that $\theta(x)=a\cdot x+b$ for all $x\in D$ and
$\theta(x)=a\cdot x+b^{\prime}$ for all $x\in I$. But then for all $x\in D$
such that $x+t\in I$, we have that $\theta(x+t)-\theta(x)=a\cdot t$, which is
constant. Therefore, $\theta$ respects $\tau_{t}|_{D_{t}}$. Again the proofs
that (4) also implies (2) and (3) is similar and we omit them. ∎

Motivated by these results, we make the following definitions.

######  Definition 6.0.

A move ensemble $\Omega^{\boxtimes}$ is a _kaleidoscopic joined ensemble_ if
it satisfies (restrict), (continuation), and the following axiom:

(kaleido) $\begin{gathered}\text{ for open intervals
}D,I\subseteq{\mathbb{R}}\\\ \mathop{\mathrm{moves}}\nolimits_{+}(D\times
I)\subseteq\Omega^{\boxtimes}\text{ if and only if
}\mathop{\mathrm{moves}}\nolimits_{-}(D\times
I)\subseteq\Omega^{\boxtimes}.\end{gathered}$

###  6.3. Covered intervals, connected covered components

######  Definition 6.0.

For a kaleidoscopic joined ensemble $\Omega^{\boxtimes}$ and an open interval
$D$ such that $\mathop{\mathrm{moves}}\nolimits(D\times
D)\subseteq\Omega^{\boxtimes}$, we say that $D$ is a _covered interval_ in
$\Omega^{\boxtimes}$.

Let $\Gamma^{\boxtimes}$ be a kaleidoscopic joined move semigroup. For two
open intervals $D_{1},D_{2}$, if

$\mathop{\mathrm{moves}}\nolimits\bigl{(}(D_{1}\cup D_{2})\times(D_{1}\cup
D_{2})\bigr{)}\subseteq\Gamma^{\boxtimes},$

then we say that both $D_{1}$ and $D_{2}$ are covered intervals in the same
_connected covered component_ of $\Gamma^{\boxtimes}$. (Here the word
“connected” does not refer to the topology of ${\mathbb{R}}$, in contrast to
subsection 4.3.) It follows from 4.1 that this is an equivalence relation.
However, we want to define the notion of a _connected covered component_ also
for kaleidoscopic joined ensembles $\Omega^{\boxtimes}$ that are not
semigroups. In this case there is no equivalence relation (transitivity
fails), but we still use the word “components” in the following definition.

######  Definition 6.0.

Let $\Omega^{\boxtimes}$ be a kaleidoscopic joined ensemble. Let $C$ be an
open set such that $\mathop{\mathrm{moves}}\nolimits(C\times
C)\subseteq\Omega^{\boxtimes}$. Then $C$ is called a _connected covered
component_ of $\Omega^{\boxtimes}$. Any two covered intervals
$D_{1},D_{2}\subseteq C$ are said to be _connected_ by the component $C$.

The connected covered components of $\Omega^{\boxtimes}$ are partially ordered
by set inclusion. The maximal elements in this partial order suffice to
describe all covered intervals.

######  Corollary 6.0.

Let $\theta$ be a bounded function. Suppose $\theta$ respects a kaleidoscopic
joined ensemble $\Omega^{\boxtimes}$. Let $C$ be a connected covered component
of $\Omega^{\boxtimes}$. Then $\theta$ is affine on all open intervals in $C$
with a common slope.

###### Proof.

Let $D,I\subseteq C$ be open intervals. Then $D\times I\subseteq C\times C$,
and hence $\theta$ respects $\mathop{\mathrm{moves}}\nolimits(D\times I)$. By
6.0 (4), $\theta$ is affine on $D$ and $I$ with the same slope. ∎

(Later in section 10, we will also consider so-called connected uncovered
components.)

###  6.4. Presentations by moves $\Omega^{\mathrm{fin}}$ and components
${\mathcal{C}}=\\{C_{1},\dots,C_{k}\\}$

Now we are prepared to define a convenient finite presentation for a large
class of kaleidoscopic joined ensembles, which we announced in 4.1.

######  Definition 6.0.

Take a finite list of connected covered components
${\mathcal{C}}=\\{C_{1},\dots,C_{k}\\}$, where each $C_{i}$ is a finite union
of disjoint open intervals. Define

$\displaystyle\mathop{\mathrm{moves}}\nolimits({\mathcal{C}})$
$\displaystyle=\bigcup_{i=1}^{k}\mathop{\mathrm{moves}}\nolimits(C_{i}\times
C_{i})$
$\displaystyle=\bigl{\\{}\,\gamma|_{D}\in\Gamma^{\subseteq}({\mathbb{R}})\mathrel{\big{|}}D,\gamma(D)\subseteq
C_{i}\text{ for some }i=1,\dots,k\,\bigr{\\}}.$

The graph $\operatorname{Gr}(\mathop{\mathrm{moves}}\nolimits({\mathcal{C}}))$
is a union of open rectangles. See Figure 6 for a visualization. We plot the
components with different colors.

Figure 6. Move ensemble $\mathop{\mathrm{moves}}\nolimits(\mathcal{C})$ from
connected covered components $\mathcal{C}$. _Left,_ $\mathcal{C}=\\{C_{1}\\}$
(one component), where
$C_{1}=(\frac{1}{19},\frac{2}{19})\cup(\frac{3}{19},\frac{6}{19})$, shown in
_red_. _Right,_ $\mathcal{C}=\\{C_{1},C_{2}\\}$ (two components), where
$C_{1}=(\frac{2}{19},\frac{3}{19})\cup(\frac{6}{19},\frac{7}{19})\cup(\frac{8}{19},\frac{9}{19})$
is shown in _red_ and
$C_{2}=(\frac{4}{19},\frac{5}{19})\cup(\frac{11}{19},\frac{12}{19})\cup(\frac{16}{19},\frac{17}{19})$
is shown in _cyan_.

Note that any ensemble of the form
$\mathop{\mathrm{moves}}\nolimits({\mathcal{C}})$ or
$\Omega^{\mathrm{fin}}\cup\mathop{\mathrm{moves}}\nolimits({\mathcal{C}})$,
where $\Omega^{\mathrm{fin}}$ is a finite move ensemble, satisfies (restrict)
and (kaleido), but is not necessarily join-closed. To make a kaleidoscopic
joined ensemble, we use the following.

######  Definition 6.0.

For any finite move ensemble $\Omega^{\mathrm{fin}}$ and a finite list
$\mathcal{C}$ of connected covered components, define

$\mathop{\mathrm{jmoves}}\nolimits(\Omega^{\mathrm{fin}},{\mathcal{C}})=\mathop{\mathrm{join}}(\Omega^{\mathrm{fin}}\cup\mathop{\mathrm{moves}}\nolimits({\mathcal{C}})).$

If $\Omega^{\mathrm{fin}}=\emptyset$, we simply write
$\mathop{\mathrm{jmoves}}\nolimits({\mathcal{C}})$.

######  Definition 6.0.

The ordered pair $(\Omega^{\mathrm{fin}},{\mathcal{C}})$ is said to be a
_finite presentation_ (by moves $\Omega^{\mathrm{fin}}$ and components
${\mathcal{C}}$) of the kaleidoscopic joined ensemble
$\mathop{\mathrm{jmoves}}\nolimits(\Omega^{\mathrm{fin}},{\mathcal{C}})$.

######  Corollary 6.0.

Let $\theta$ be a bounded function. Suppose $\theta$ respects a move ensemble
$\Omega^{\boxtimes}$ that has the finite presentation
$(\Omega^{\mathrm{fin}},{\mathcal{C}})$. Then $\theta$ is affine on all
intervals in $\mathcal{C}$ and shares a common slope on all intervals of each
component $C_{i}$ of $\mathcal{C}$.

###### Proof.

This is a restatement of 6.0. ∎

It is clear that these presentations are not unique, which motivates the next
subsection.

###  6.5. Finite presentation in reduced form
$(\Omega^{\mathrm{red}},{\mathcal{C}})$

$\begin{aligned} \vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-
algo-paper/reduce_moves_by_components_ex1a-completion-
unreduced}}}&\mapsto\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/reduce_moves_by_components_ex1a-completion-initial}}}\\\
\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-algo-
paper/reduce_moves_by_components_ex1b-completion-
unreduced}}}&\mapsto\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/reduce_moves_by_components_ex1b-completion-initial}}}\\\
\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-algo-
paper/reduce_moves_by_components_ex1c-completion-
unreduced}}}&\mapsto\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/reduce_moves_by_components_ex1c-completion-
initial}}}\end{aligned}$

Figure 7. Finite presentation in reduced form. _Left,_ finite presentations
$(\Omega^{\mathrm{fin}},{\mathcal{C}})$ of kaleidoscopic joined ensembles
$\Omega^{\boxtimes}$. _Right,_ finite presentations
$(\Omega^{\mathrm{red}},{\mathcal{C}})$ in reduced form of the same ensembles.
(a) A move poking into a component is extended to become a maximal move of
$\Omega^{\boxtimes}$. (b) Two restrictions of the same move are extended to
become a maximal move of $\Omega^{\boxtimes}$. (c) A move that lies completely
in a component is removed.

######  Definition 6.0.

A finite presentation $(\Omega^{\mathrm{red}},{\mathcal{C}})$ of a
kaleidoscopic joined ensemble $\Omega^{\boxtimes}$ is said to be in _(long)
reduced form_ if the following holds:

(reduce)
$\Omega^{\mathrm{red}}\subseteq\operatorname{Max}(\Omega^{\boxtimes})\setminus\mathop{\mathrm{jmoves}}\nolimits({\mathcal{C}}),$

that is, each move $\gamma|_{D}\in\Omega^{\mathrm{red}}$ is maximal in
$\Omega^{\boxtimes}$ with respect to the restriction partial order
$\subseteq$, and the graph $\operatorname{Gr}(\gamma|_{D})$ is not covered by
the union of open rectangles $C_{i}\times C_{i}$, $C_{i}\in\mathcal{C}$.

######  Lemma 6.0.

If a kaleidoscopic joined ensemble $\Omega^{\boxtimes}$ has a finite
presentation $(\Omega^{\mathrm{fin}},{\mathcal{C}})$, then there is a unique
finite ensemble $\Omega^{\mathrm{red}}$ such that
$(\Omega^{\mathrm{red}},{\mathcal{C}})$ is in reduced form and
$\Omega^{\boxtimes}=\mathop{\mathrm{jmoves}}\nolimits(\Omega^{\mathrm{red}},{\mathcal{C}})$.

Figure 7 illustrates the operation of going from a finite presentation to a
reduced presentation of the same ensemble.

######  Remark 6.0.

As the examples in Figure 7 illustrate, the domains of moves in
$\Omega^{\mathrm{fin}}$ may be extended.

###  6.6. Finite presentations of generating ensembles of move semigroups

Move ensembles have a crucial rôle as generating sets of move semigroups. We
now describe an operation that changes the generating ensemble, but preserves
the move semigroup that is generated by it.

######  Lemma 6.0 (Extend component by move).

Let ${\mathcal{C}}$ be a list of connected components and let $\Omega$ be a
move ensemble such that
$\mathop{\mathrm{moves}}\nolimits({\mathcal{C}})\subseteq\Omega$. If
$\gamma|_{D}\in\Omega$ and $D\subseteq C_{i}$ for some
$C_{i}\in{\mathcal{C}}$, then
$\mathop{\mathrm{moves}}\nolimits({\mathcal{C}}^{\prime})\subseteq\mathop{\mathrm{i{}semi}}(\Omega)$,
where $C_{i}^{\prime}=C_{i}\cup\gamma(D)$ and all other components of
${\mathcal{C}}^{\prime}$ are the same as ${\mathcal{C}}$.

See Figure 8 for an illustration.

###### Proof.

Let $x\in C_{i}$, $z\in\gamma(D)$, and $y=\gamma^{-1}(z)\in D$. Since $x\in
C_{i}$, $x$ is in the domain of moves $\tau_{0}$ and $\rho_{0}$ in $\Omega$.
Thus, we can both translate and reflect $x$ to $z$ by

$x\xmapsto{\tau_{t_{y-x}}}y\xmapsto{\gamma}z,$

and

$x\xmapsto{\rho_{r_{0}}}x\xmapsto{\tau_{t_{y-x}}}y\xmapsto{\gamma}z.$

Note that which one above is a translation or reflection depends on the
character $\chi(\gamma)$. ∎

$\begin{aligned} \vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-
algo-
paper/extend_components_by_moves_ex1-completion-0}}}&\xmapsto{\mbox{\normalsize$\;\mathop{\mathrm{i{}semi}}\;$}}\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/extend_components_by_moves_ex1-completion-final}}}\\\
\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-algo-
paper/extend_components_by_moves_ex2-completion-0}}}&\xmapsto{\mbox{\normalsize$\;\mathop{\mathrm{i{}semi}}\;$}}\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/extend_components_by_moves_ex2-completion-final}}}\\\
\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-algo-
paper/extend_components_by_moves_ex4-completion-0}}}&\xmapsto{\mbox{\normalsize$\;\mathop{\mathrm{i{}semi}}\;$}}\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/extend_components_by_moves_ex4-completion-final}}}\\\
\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-algo-
paper/extend_components_by_moves_ex5-completion-0}}}&\xmapsto{\mbox{\normalsize$\;\mathop{\mathrm{i{}semi}}\;$}}\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/extend_components_by_moves_ex5-completion-
final}}}\end{aligned}$

Figure 8.  Extending components by moves, 6.0. _Left,_ reduced finite
presentations of a kaleidoscopic joined ensemble $\Omega^{\boxtimes}$.
_Right,_ reduced finite presentations of
$\mathop{\mathrm{i{}semi}}(\Omega^{\boxtimes})$.

##  7\. Limit-closed ensembles and continuous functions. Closed move
semigroups

Let $A\subseteq{\mathbb{R}}$ be an open set. We now consider the space
${\mathcal{C}_{\mathrm{b}}({A})}$ of bounded continuous functions on $A$. For
${\mathcal{C}_{\mathrm{b}}({A})}$, some notions of convergence of moves are
natural to study.

###  7.1. Limit-closed move ensembles $\bar{\Omega}$; closures
$\mathop{\mathrm{lim}}(\Omega)$, $\mathop{\mathrm{arblim}}(\Omega)$

####  7.1.1. Convergence of unrestricted moves

######  Definition 7.0.

A sequence $\\{\gamma^{i}\\}_{i\in{\mathbb{N}}}\subseteq\Gamma({\mathbb{R}})$
of unrestricted moves _converges_

  1. (a)

to an unrestricted translation $\tau_{t}\in\Gamma({\mathbb{R}})$ if all but
finitely many $\gamma^{i}$ are translations $\tau_{t^{i}}$ and $t^{i}\to t$.

  2. (b)

to an unrestricted reflection $\rho_{r}\in\Gamma({\mathbb{R}})$ if all but
finitely many $\gamma^{i}$ are reflections $\rho_{r^{i}}$ and $r^{i}\to r$.

####  7.1.2. Limits closure

######  Definition 7.0.

We define the _limits closure_ $\mathop{\mathrm{lim}}(\Omega)$ of a moves
ensemble $\Omega$ to be the smallest (by set inclusion) moves ensemble
$\bar{\Omega}$ containing $\Omega$ that satisfies the following axiom.

(lim) $\begin{gathered}\text{Let $D$ be an open interval.}\\\ \text{If
$\gamma^{i}\to\gamma$ and $\gamma^{i}|_{D}\in\bar{\Omega}$ for all $i$,}\
\text{then $\gamma|_{D}\in\bar{\Omega}$.}\end{gathered}$

We note that the domain $D$ is fixed for all moves in the sequence. Thus, the
limits closure will in general not satisfy (continuation) and (inv). Instead
we can consider the following axiom.

######  Definition 7.0.

Define $\mathop{\mathrm{arblim}}(\Omega)$ to be the smallest moves ensemble
$\bar{\Omega}$ containing $\Omega$ that satisfies the following axiom.

(arblim) $\begin{gathered}\text{If $\gamma^{i}\to\gamma$, $l^{i}\to l$,
$u^{i}\to u$ and $\gamma^{i}|_{(l^{i},u^{i})}\in\bar{\Omega}$ for all $i$,}\\\
\text{then $\gamma|_{(l,u)}\in\bar{\Omega}$.}\end{gathered}$

For our purposes, when considered together with (continuation), the notions
turn out to be equivalent.

######  Theorem 7.1.

Let $\Omega^{\vee}$ be a join-closed move ensemble. Then

$\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Omega^{\vee}))=\mathop{\mathrm{join}}(\mathop{\mathrm{arblim}}(\Omega^{\vee})).$

###### Proof.

It is clear that
$\mathop{\mathrm{lim}}(\Omega^{\vee})\subseteq\mathop{\mathrm{arblim}}(\Omega^{\vee})$,
so it suffices to show that

(7.1)
$\mathop{\mathrm{arblim}}(\Omega^{\vee})\subseteq\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Omega^{\vee})).$

Let $\tau_{t}|_{(l,u)}\in\mathop{\mathrm{arblim}}(\Omega^{\vee})$. By
(arblim), there is a convergent sequence
$\\{\tau_{t^{i}}|_{(l^{i},u^{i})}\\}_{i\in{\mathbb{N}}}$ of moves in
$\Omega^{\vee}$ such that $l^{i}\to l$, $u^{i}\to u$ and $t^{i}\to t$. For
every integer $j>\frac{2}{u-l}$, there exists a large integer $n_{j}$ such
that for any $i\geq n_{j}$, we have $l_{i}<l+\frac{1}{j}$ and
$u-\frac{1}{j}<u_{i}$. Since $\Omega^{\vee}$ satisfies (continuation),
$\tau_{t^{i}}|_{D_{j}}\in\Omega^{\vee}$ for any $i\geq n_{j}$, where
$D_{j}:=(l+\frac{1}{j},u-\frac{1}{j})$. Since $t_{i}\to t$, we have
$\tau_{t}|_{D_{j}}\in\mathop{\mathrm{lim}}(\Omega^{\vee})$ for every $j$,
hence
$\tau_{t}|_{(l,u)}\in\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Omega^{\vee}))$.
We showed that (7.1) holds for translations. The proof for reflections is
similar. ∎

######  Theorem 7.2.

Let $\Omega^{\vee}$ be a join-closed move ensemble. The following are
equivalent.

  1. (1)

$\Omega^{\vee}$ satisfies (lim).

  2. (2)

$\Omega^{\vee}$ satisfies (arblim).

The proof is essentially the same and we omit it.

####  7.1.3. Respecting limits

######  Lemma 7.2 (Limits).

Let $D$ be an open interval and let $\theta$ be continuous on $D$. If there
exists a sequence $\gamma^{i}\to\gamma$ such that $\theta$ respects
$\gamma^{i}|_{D}$ for all $i$, then $\theta$ also respects $\gamma|_{D}$.

###### Proof.

We prove the lemma for a sequence $t_{i}\to t$ such that $\theta$ respects the
translations $\tau_{t_{i}}|_{D}$ for all $i$. We will show that $\theta$ also
respects $\tau_{t}|_{D}$.

Since $\theta$ is continuous on $D$, $\theta$ is also continuous on
$\tau_{t_{i}}(D)$ for all $i$. Fix $\bar{x}\in D$. Since $t_{i}\to t$, and
$\bar{x}\in\operatorname{int}(D)$ since $D$ is open, there exists an $\hat{i}$
such that for all $i\geq\hat{i}$, we have $\bar{x}+t\in D+t_{i}$. Hence, for a
neighborhood $N_{\bar{x}}$ of $\bar{x}$, $\theta$ is continuous in
$N_{\bar{x}}+t$. Now, for all $x\in N_{\bar{x}}$,

$\theta(x+t)-\theta(x)=\lim_{t_{i}\to
t}\theta(x+t_{i})-\theta(x)=\lim_{i\to\infty}c^{\theta}_{\tau_{t_{i}}|_{D}}.$

Since the limit on the right-hand side is independent of $x$, we define
$c^{\theta}_{\tau_{t}|_{N_{\bar{x}}}}$ to be this limit. Thus, $\theta$
respects $\tau_{t}|_{N_{\bar{x}}}$.

Now the connected open set $D$ is covered by the open neighborhoods
$N_{\bar{x}}$ of each $\bar{x}\in D$. It follows that
$c^{\theta}_{\tau_{t}|_{N_{\bar{x}}}}=c^{\theta}_{\tau_{t}|_{N_{\bar{x}^{\prime}}}}$
for all $\bar{x},\bar{x}^{\prime}\in D$. Therefore, $\theta$ respects
$\tau_{t}|_{D}$. Moreover, $\theta$ is continuous on $\tau_{t}|_{D}$.

The proof for a sequence of reflections is the same. ∎

####  7.1.4. Limit-closed move semigroups

######  Lemma 7.2.

Let $\Gamma$ be a move semigroup. Then $\mathop{\mathrm{arblim}}(\Gamma)$ is
also a move semigroup.

###### Proof.

It is clear that $\mathop{\mathrm{arblim}}(\Gamma)$ satisfies (inv), as
$\Gamma$ satisfies (inv). We now show that $\mathop{\mathrm{arblim}}(\Gamma)$
satisfies (composition). Let
$\gamma_{1}|_{D_{1}},\gamma_{2}|_{D_{2}}\in\mathop{\mathrm{arblim}}(\Gamma)$
such that $\gamma_{1}|_{D_{1}}\circ\gamma_{2}|_{D_{2}}$ is not an empty move.
$\gamma_{1}|_{D_{1}}$ and $\gamma_{2}|_{D_{2}}$ are the (arblim) of sequences
of moves $\\{\gamma_{1}^{i}|_{D_{1}^{i}}\\}_{i\in{\mathbb{N}}}$ and
$\\{\gamma_{2}^{i}|_{D_{2}^{i}}\\}_{i\in{\mathbb{N}}}$ in $\Gamma$. Since
$\Gamma$ satisfies (composition),
$\gamma^{i}|_{D^{i}}:=(\gamma_{1}^{i}|_{D_{1}^{i}})\circ(\gamma_{2}^{i}|_{D_{2}^{i}})\in\Gamma$
for every $i$. The (arblim) of the sequence
$\\{\gamma^{i}|_{D^{i}}\\}_{i\in{\mathbb{N}}}$ is
$\gamma_{1}|_{D_{1}}\circ\gamma_{2}|_{D_{2}}$. Thus, we obtain that
$\gamma_{1}|_{D_{1}}\circ\gamma_{2}|_{D_{2}}\in\mathop{\mathrm{arblim}}(\Gamma)$.
This show that $\mathop{\mathrm{arblim}}(\Gamma)$ is a semigroup. ∎

######  Lemma 7.2.

Let $\Gamma^{\vee}$ be a join-closed semigroup. Then
$\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Gamma^{\vee}))=\mathop{\mathrm{join}}(\mathop{\mathrm{arblim}}(\Gamma^{\vee}))$
is a semigroup.

###### Proof.

It follows from 7.2, 4.0 and Theorem 7.1. ∎

######  Theorem 7.3 (Limits imply components).

Let $\Gamma^{\vee}$ be a join-closed move semigroup. Assume that $\gamma|_{D}$
is the limit move (in the sense of $\mathop{\mathrm{lim}}$ or
$\mathop{\mathrm{arblim}}$) of a sequence
$\\{\gamma^{i}|_{D^{i}}\\}_{i\in{\mathbb{N}}}$ of moves in $\Gamma^{\vee}$
with $\gamma^{i}\neq\gamma$ for every $i$. Let $I=\gamma(D)$. Then the
following holds.

  1. (1)

If $\gamma$ is a translation, then
$\mathop{\mathrm{moves}}\nolimits_{+}((D\cup I)\times(D\cup
I))\subseteq\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Gamma^{\vee}))$.

  2. (2)

If $\gamma$ is a reflection, then

$\mathop{\mathrm{moves}}\nolimits_{-}((D\times I)\cup(I\times
D)),\mathop{\mathrm{moves}}\nolimits_{+}((D\times D)\cup(I\times
I))\subseteq\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Gamma^{\vee})).$

###### Proof.

Let $D=(l,u)$. If a sequence $\\{\gamma^{i}|_{D^{i}}\\}_{i\in{\mathbb{N}}}$ of
moves in $\Gamma^{\vee}$ with $\gamma^{i}\neq\gamma$ converges to
$\gamma|_{D}$ in the sense of $\mathop{\mathrm{arblim}}$, then
$\gamma^{i}|_{D^{i}\cap(l+\epsilon,u-\epsilon)}\to\gamma|_{(l+\epsilon,u-\epsilon)}$
in the sense of $\mathop{\mathrm{lim}}$ for any small $\epsilon>0$. Thus, it
suffices to prove the statement for a limit move $\gamma|_{D}$ in the sense of
$\mathop{\mathrm{lim}}$; the statement for $\mathop{\mathrm{arblim}}$ follows
from 7.2 and continuation.

We first show that $\mathop{\mathrm{moves}}\nolimits_{+}(D\times
D)\subseteq\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Gamma^{\vee}))$. Let
$\epsilon>0$ be an arbitrary small number. Since $\gamma|_{D}$ is a limit
move, there exist $\gamma^{i}|_{D},\gamma^{j}|_{D}\in\Gamma^{\vee}$ in the
convergent sequence such that the constants $\gamma-\gamma^{i}$ and
$\gamma-\gamma^{j}$ have the same sign, and
$0<\gamma^{j}-\gamma^{i}<\epsilon$. Let $\delta=\gamma^{j}-\gamma^{i}$ and
$D^{1}=(l,u)\cap(l-\delta,u-\delta)$. We notice that
$(\gamma^{i}|_{D})^{-1}\circ\gamma^{j}|_{D}=\tau_{\delta}|_{D^{1}}$ when
$\gamma$ is a translation, and
$(\gamma^{j}|_{D})^{-1}\circ\gamma^{i}|_{D}=\tau_{\delta}|_{D^{1}}$ when
$\gamma$ is a reflection. Therefore, $\tau_{\delta}|_{D^{1}}\in\Gamma^{\vee}$.
Let $D^{k}:=(l,u)\cap(l-k\delta,u-k\delta)$ for $k\in{\mathbb{Z}}$. For $k\geq
1$, $\tau_{k\delta}|_{D^{k}}$ is the $k$ times composition of
$\tau_{\delta}|_{D^{1}}$, hence it is in $\Gamma^{\vee}$. For $k=-1$,
$\tau_{-\delta}|_{D^{-1}}=(\tau_{\delta}|_{D^{1}})^{-1}\in\Gamma^{\vee}$. For
$k\leq-2$, $\tau_{k\delta}|_{D^{k}}$ is the $-k$ times composition of
$\tau_{-\delta}|_{D^{-1}}$, and hence is in $\Gamma^{\vee}$. Finally, for
$k=0$, we have
$(\tau_{\delta}|_{D^{1}})\circ(\tau_{-\delta}|_{D^{-1}}),(\tau_{-\delta}|_{D^{-1}})\circ(\tau_{\delta}|_{D^{1}})\in\Gamma^{\vee}$,
so their join $\tau_{0}|_{D^{0}}$ is also in $\Gamma^{\vee}$. Therefore, for
every $k\in{\mathbb{Z}}$ such that $D^{k}$ is not empty, we have
$\tau_{k\delta}|_{D^{k}}\in\Gamma^{\vee}$. By letting $\epsilon\to 0$, we
obtain that $\mathop{\mathrm{moves}}\nolimits_{+}(D\times
D)\subseteq\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Gamma^{\vee}))$.

Since
$\gamma|_{D}\in\mathop{\mathrm{lim}}(\Gamma^{\vee})\subseteq\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Gamma^{\vee}))$
and $\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Gamma^{\vee}))$ is a
semigroup by 7.2, we have that $\mathop{\mathrm{moves}}\nolimits_{+}(D\times
I)\subseteq\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Gamma^{\vee}))$ when
$\gamma$ is a translation, and $\mathop{\mathrm{moves}}\nolimits_{-}(D\times
I)\subseteq\mathop{\mathrm{join}}(\mathop{\mathrm{lim}}(\Gamma^{\vee}))$ when
$\gamma$ is a reflection.

The other two subsets follow from applying the above argument to
$(\gamma|_{D})^{-1}$ instead of $\gamma|_{D}$. ∎

###  7.2. Continuous domain extension $\mathop{\mathrm{extend}_{A}}(\Omega)$

Next we introduce a topological version of axiom (continuation).

####  7.2.1. Extended move ensembles $\overline{\Omega}{}{}^{\vee}$

######  Definition 7.3.

Let $\Omega$ be a move ensemble with
$\operatorname{dom}(\Omega),\operatorname{im}(\Omega)\subseteq A$, where
$A\subseteq{\mathbb{R}}$ is an open set. Then the _extended move ensemble_
$\mathop{\mathrm{extend}_{A}}(\Omega)$ of $\Omega$ is defined to be the
smallest set $\overline{\Omega}{}{}^{\vee}$ containing $\Omega$ that satisfies
the following axiom

(extendA) $\begin{gathered}\text{Let $\gamma\in\Gamma({\mathbb{R}})$ and $D$
empty or an open interval.}\\\ \text{If there is an ensemble
$\\{\gamma|_{D^{i}}\\}_{i\in\mathfrak{I}}\subseteq\overline{\Omega}{}{}^{\vee}$
such that}\\\ \text{
$D\subseteq\operatorname{cl}(\textstyle\bigcup_{i\in\mathfrak{I}}D^{i})\cap
A\cap\gamma^{-1}(A)$, then
$\gamma|_{D}\in\overline{\Omega}{}{}^{\vee}$.}\end{gathered}$

######  Remark 7.3.

An ensemble satisfying (extendA) is join-closed.

The most simple application of (extendA) allows us to join two adjacent moves
across a point of continuity; see Figure 9.

######  Lemma 7.3.

Let $\overline{\Omega}{}{}^{\vee}$ be a move ensemble that satisfies
(extendA). Then we have:

(2-extendA) $\begin{gathered}\text{If
$\gamma|_{(l,m)},\gamma|_{(m,u)}\in\overline{\Omega}{}{}^{\vee}$, where
$l<m<u$, and $m,\gamma(m)\in A$,}\\\ \text{then
$\gamma|_{(l,u)}\in\overline{\Omega}{}{}^{\vee}.$}\end{gathered}$

$\begin{aligned} \vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-
algo-paper/extend_moves_ex1a-completion-
unreduced}}}&\xmapsto{\mbox{\normalsize$\;\mathop{\mathrm{extend}_{A}}\;$}}\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/extend_moves_ex1a-completion-initial}}}\\\
\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-algo-
paper/extend_moves_ex1b-completion-
unreduced}}}&\xmapsto{\mbox{\normalsize$\;\mathop{\mathrm{extend}_{A}}\;$}}\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/extend_moves_ex1b-completion-initial}}}\\\
\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-for-algo-
paper/reduce_moves_by_components_ex2b-completion-
unreduced}}}&\xmapsto{\mbox{\normalsize$\;\mathop{\mathrm{extend}_{A}}\;$}}\vbox{\hbox{\includegraphics[height=108.405pt]{graphics-
for-algo-paper/reduce_moves_by_components_ex2b-completion-initial}}}\\\
\end{aligned}$

Figure 9. Extended move ensembles $\mathop{\mathrm{extend}_{A}}(\Omega)$ of
ensembles $\Omega$. Points not in the continuity set $A$ are indicated by
_black circles at the top and left border_.

The following is clear from the definition.

######  Lemma 7.3.

Let $\Omega$ be a move ensemble with
$\operatorname{dom}(\Omega)=\operatorname{im}(\Omega)\subseteq A$. Let
$\overline{\Omega}{}{}^{\vee}=\mathop{\mathrm{extend}_{A}}(\Omega)$. Then
$\operatorname{dom}(\overline{\Omega}{}{}^{\vee})=\operatorname{im}(\overline{\Omega}{}{}^{\vee})\subseteq
A$.

######  Remark 7.3.

If $\Omega^{\vee}$ is a joined ensemble with finite
$\operatorname{Max}(\Omega^{\vee})$, then repeated application of (2-extendA),
followed by applying (continuation), suffices to obtain
$\mathop{\mathrm{extend}_{A}}(\Omega^{\vee})$.

However, this is not true for arbitrary joined ensembles $\Omega^{\vee}$. As
an example, let $A={\mathbb{R}}$ and consider $\Omega^{\vee}$ consisting of
the restrictions of a move $\gamma$ to all subintervals of $(-1,0)$ and
$(\frac{1}{n+1},\frac{1}{n})$ for $n\in{\mathbb{N}}$. (These maximal intervals
are disjoint.) Domains of moves of
$\mathop{\mathrm{extend}_{A}}(\Omega^{\vee})$ are all subintervals of
$(-1,1)$. The domains of moves of
$\mathop{\mathrm{\text{2-}extend}_{A}}(\Omega^{\vee})$ are $(-1,0)$ and its
subintervals and the infinite chain $(\frac{1}{m},1)$ for $m\in{\mathbb{N}}$
and some of its subintervals; the supremum of the chain, $(0,1)$ is not an
element. Then the domains of maximal moves of
$\mathop{\mathrm{join}}(\mathop{\mathrm{\text{2-}extend}_{A}}(\Omega^{\vee}))$
are $(-1,0)$ and $(0,1)$. It takes _another round_ of
$\mathop{\mathrm{\text{2-}extend}_{A}}$ to arrive at
$\mathop{\mathrm{extend}_{A}}(\Omega^{\vee})$.

We have an explicit description of the moves in the extended move ensemble
$\mathop{\mathrm{extend}_{A}}(\Omega)$, similar to 3.0 for
$\mathop{\mathrm{join}}(\Omega)$.

######  Remark 7.3.

For a move ensemble $\Omega$ with
$\operatorname{dom}(\Omega),\operatorname{im}(\Omega)\subseteq A$, where
$A\subseteq{\mathbb{R}}$ is an open set, we have

(7.2)
$\displaystyle\mathop{\mathrm{extend}_{A}}(\Omega)=\bigl{\\{}\,\gamma|_{D}\mathrel{\big{|}}$
$\displaystyle\gamma\in\Gamma({\mathbb{R}}),\;\text{$D$ empty or open
interval},$ $\displaystyle D\subseteq\operatorname{cl}(C_{\gamma})\cap
A\cap\gamma^{-1}(A)\,\bigr{\\}},$

where $C_{\gamma}:=\bigcup\\{\,I\mid\gamma|_{I}\in\Omega\,\\}$, which is a
subset of $A\cap\gamma^{-1}(A)$.

####  7.2.2. Domain extension and semigroups

######  Lemma 7.3.

Let $\Gamma$ be a move semigroup with
$\operatorname{dom}(\Gamma),\operatorname{im}(\Gamma)\subseteq A$, where
$A\subseteq{\mathbb{R}}$ is an open set. Then
$\mathop{\mathrm{extend}_{A}}(\Gamma)$ is a move semigroup that satisfies
(extendA).

###### Proof.

Since $\Gamma$ satisfies (inv), it is clear that
$\mathop{\mathrm{extend}_{A}}(\Gamma)$ satisfies (inv). We now show that
$\mathop{\mathrm{extend}_{A}}(\Gamma)$ satisfies (composition), too.

Let
$\gamma_{1}|_{D_{1}},\gamma_{2}|_{D_{2}}\in\mathop{\mathrm{extend}_{A}}(\Gamma)$.
Let

$C_{1}=C_{\gamma_{1}}=\bigcup\\{\,I\mid\gamma_{1}|_{I}\in\Gamma\,\\}\;\text{
and }\;C_{2}=C_{\gamma_{2}}=\bigcup\\{\,I\mid\gamma_{2}|_{I}\in\Gamma\,\\}.$

By equation (7.2), the open set $D_{1}$ and $D_{2}$ satisfy that

$D_{1}\subseteq\operatorname{cl}(C_{1})\cap A\cap\gamma_{1}^{-1}(A)\;\text{
and }\;D_{2}\subseteq\operatorname{cl}(C_{2})\cap A\cap\gamma_{2}^{-1}(A).$

Let $\gamma=\gamma^{2}\circ\gamma^{1}$,
$C=C_{\gamma}=\bigcup\\{\,I\mid\gamma|_{I}\in\Gamma\,\\}$ and let
$D=\gamma_{1}^{-1}(D_{2})\cap D_{1}$ be a non-empty open set. We will show
that

(7.3) $D\subseteq\operatorname{cl}(C)\cap A\cap\gamma^{-1}(A).$

It then follows again from (7.2) that
$\gamma_{2}|_{D_{2}}\circ\gamma_{1}|_{D_{1}}=\gamma|_{D}\in\mathop{\mathrm{extend}_{A}}(\Gamma)$,
and hence $\mathop{\mathrm{extend}_{A}}(\Gamma)$ is a move semigroup. It
suffices to show (7.3) for

$D_{1}=\operatorname{int}\bigl{(}\operatorname{cl}(C_{1})\cap
A\cap\gamma_{1}^{-1}(A)\bigr{)}\;\text{ and
}\;D_{2}=\operatorname{int}\bigl{(}\operatorname{cl}(C_{2})\cap
A\cap\gamma_{2}^{-1}(A)\bigr{)}.$

We have on the left hand side of (7.3)

$\displaystyle D$ $\displaystyle=\gamma_{1}^{-1}(D_{2})\cap D_{1}$
$\displaystyle=\operatorname{int}\bigl{(}\gamma_{1}^{-1}\bigl{(}\operatorname{cl}(C_{2})\bigr{)}\cap\gamma_{1}^{-1}(A)\cap\gamma^{-1}(A)\bigr{)}\cap\operatorname{int}\bigl{(}\operatorname{cl}(C_{1})\cap
A\cap\gamma_{1}^{-1}(A)\bigr{)}$
$\displaystyle=\operatorname{int}\bigl{(}\operatorname{cl}(C_{1})\bigr{)}\cap\gamma_{1}^{-1}\bigl{(}\operatorname{int}\bigl{(}\operatorname{cl}(C_{2})\bigr{)}\bigr{)}\cap
A\cap\gamma_{1}^{-1}(A)\cap\gamma^{-1}(A),$

and on the right hand side of (7.3) $\operatorname{cl}(C)\cap
A\cap\gamma^{-1}(A)$. Thus, it suffices to prove that if
$x\in\operatorname{int}\bigl{(}\operatorname{cl}(C_{1})\bigr{)}$ such that
$\gamma_{1}(x)\in\operatorname{int}\bigl{(}\operatorname{cl}(C_{2})\bigr{)}$,
then $x\in\operatorname{int}\bigl{(}\operatorname{cl}(C)\bigr{)}$. This holds
since $\Gamma$ satisfies (composition). ∎

####  7.2.3. Respecting extensions

######  Lemma 7.3 (Extend moves by continuity).

Let $\theta$ be a function that respects a move ensemble $\Omega$ with
$\operatorname{dom}(\Omega),\operatorname{im}(\Omega)\subseteq A$. Then it
respects the extended move ensemble $\mathop{\mathrm{extend}_{A}}(\Omega)$.

###### Proof.

We use the characterization of $\mathop{\mathrm{extend}_{A}}(\Omega)$ from
7.3. Let $\gamma\in\Gamma({\mathbb{R}})$ and let $C_{\gamma}\subseteq
A\cap\gamma^{-1}(A)$ be as in 7.3. The function
$x\mapsto\theta(\gamma(x))-\chi(\gamma)\theta(x)$ is constant on the connected
components of $C_{\gamma}$ and it is continuous on $A\cap\gamma^{-1}(A)$. Then
it is constant on the connected components of
$\operatorname{cl}(C_{\gamma})\cap A\cap\gamma^{-1}(A)$. ∎

Applied to the simple case of 7.3, we have the following.

######  Corollary 7.3.

Suppose $\theta$ respects the moves $\gamma|_{(l,m)},\gamma|_{(m,u)}$ with
$l<m<u$ and suppose $\theta$ is continuous at $m$, $\gamma(m)$. Then $\theta$
respects $\gamma|_{(l,u)}$.

######  Remark 7.3.

The assumption regarding continuity at both $m$ and $\gamma(m)$ cannot be
removed, which explains why we use $A\cap\gamma^{-1}(A)$ in (extendA). We
illustrate this by the following example. Let $A=(0,2)\cup(2,3)$. Let
$\gamma=\tau_{1}$ and $\Omega=\\{\gamma|_{(0,1)},\gamma|_{(1,2)}\\}$, so
$\operatorname{dom}(\Omega)=(0,1)\cup(1,2)\subseteq A$ and
$\operatorname{im}(\Omega)=(1,2)\cup(2,3)\subseteq A$. Then $1\in A$, but
$\gamma(1)=2\notin A$. Define $\theta=0$ on $A$ and $\theta(2)=1$, so it is
continuous at $1$ but not at $\gamma(1)=2.$ Then $\theta$ respects $\Omega$,
but it does not respect the move $\gamma|_{(0,2)}$.

###  7.3. Closed move semigroups, the moves closure
$\mathop{\mathrm{clsemi}_{A}}(\Omega)$

Now all axioms that we have introduced above come together.

######  Definition 7.3.

A _closed move semigroup_ is a limits-closed extension-closed kaleidoscopic
joined move semigroup, i.e., a move ensemble that satisfies all the following
axioms: (composition), (inv), (continuation), (restrict), (extendA), (lim),
and (kaleido).

######  Definition 7.3.

Let $\Omega$ be a move ensemble with
$\operatorname{dom}(\Omega),\operatorname{im}(\Omega)\subseteq A$. We define
the _closed move semigroup_ $\mathop{\mathrm{clsemi}_{A}}(\Omega)$ generated
by $\Omega$ (or just _moves closure_ of $\Omega$) to be the smallest (by set
inclusion) closed move semigroup containing $\Omega$.

######  Lemma 7.3.

Let ${\mathbb{L}}$ be the family of closed move semigroups containing
$\Omega$. Then
$\mathop{\mathrm{clsemi}_{A}}(\Omega)=\bigcap{\mathbb{L}}=\bigcap_{\Omega^{\prime}\in{\mathbb{L}}}\Omega^{\prime}$.

###### Proof.

First of all, $\bigcap{\mathbb{L}}$ contains $\Omega$. We show that
$\bigcap{\mathbb{L}}$ is a closed move semigroup. Note that each axiom is a
closure property of a set $\Omega^{\prime}$ of the form: For all
$(\Omega_{1},\Omega_{2})\in\mathbb{X}$, if
$\Omega_{1}\subseteq\Omega^{\prime}$, then
$\Omega_{2}\subseteq\Omega^{\prime}$. Now if
$\Omega_{1}\subseteq\bigcap{\mathbb{L}}$, then
$\Omega_{1}\subseteq\Omega^{\prime}$ for all $\Omega^{\prime}\in{\mathbb{L}}$,
and thus $\Omega_{2}\subseteq\Omega^{\prime}$ for all
$\Omega^{\prime}\in{\mathbb{L}}$. This implies
$\Omega_{2}\subseteq\bigcap{\mathbb{L}}$.

On the other hand, $\bigcap{\mathbb{L}}$ is contained in each of the ensembles
$\Omega^{\prime}\in{\mathbb{L}}$ and is therefore the smallest closed move
semigroup containing $\Omega$. ∎

######  Remark 7.3.

In contrast to 4.0 (regarding (continuation) and (restrict) and the axioms of
an inverse semigroup), we do not know whether
$\mathop{\mathrm{clsemi}_{A}}(\Omega)$ can be obtained by applying a finite
sequence of closures with respect to the individual axioms.

######  Theorem 7.4 (Main theorem on the moves closure).

Suppose $\theta$ is bounded and continuous on $A$. If $\theta$ respects a move
ensemble $\Omega$ with
$\operatorname{dom}(\Omega),\operatorname{im}(\Omega)\subseteq A$, then
$\theta$ respects the moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega)$.

###### Proof of Theorem 7.4.

Let $\theta|_{A}$ denote the restriction of $\theta$ to $A$. We consider the
ensemble $\Gamma=\Gamma^{\mathrm{resp}}(\theta|_{A})$ of moves that
$\theta|_{A}$ respects, introduced in subsection 5.2. By definition,
$\operatorname{dom}(\Gamma),\operatorname{im}(\Gamma)\subseteq A$. Since, by
assumption, $\theta$ respects $\Omega$, we have $\Gamma\supseteq\Omega$. By
Theorem 5.1, $\Gamma$ is a join-closed move semigroup. By 6.0, because
$\theta|_{A}$ is bounded, $\Gamma$ satisfies the axiom (kaleido). Because
$\theta|_{A}$ is continuous, we can apply 7.2 to all convergent sequences
$\\{\gamma^{i}|_{D}\\}_{i\in{\mathbb{N}}}\subseteq\Gamma$, and thus $\Gamma$
satisfies the axiom (lim). Finally, by 7.3, it satisfies the axiom (extendA).
Hence, $\Gamma^{\mathrm{resp}}(\theta)$ is a closed move semigroup. By 7.3, we
conclude that $\theta$ respects $\mathop{\mathrm{clsemi}_{A}}(\Omega)$. ∎

##  8\. The initial additive move ensemble $\Omega^{0}$ of a subadditive
function

We will now apply the theory of the previous sections to compute the effective
perturbation spaces of minimal valid functions. Let
$\pi\colon{\mathbb{R}}\to{\mathbb{R}}$ be a minimal valid function. Recall
from the introduction that $\pi$ is nonnegative, ${\mathbb{Z}}$-periodic, and
satisfies $\pi(0)=0$, $\pi(f)=1$. Its key property is subadditivity, which we
express using the _subadditivity slack_ function

(8.1) $\Delta\pi(x,y)=\pi(x)+\pi(y)-\pi(x+y)$

as $\Delta\pi(x,y)\geq 0$. Moreover, the symmetry condition
$\Delta\pi(x,f-x)=0$ holds for all $x$. This is the characterization that
appeared in the introduction as (1.3).

Since $\pi$ is ${\mathbb{Z}}$-periodic, we will work with its fundamental
domain $[0,1]$. Let $A=A(\pi)$ be the maximal open subset of $(0,1)$ on which
$\pi$ is continuous.

###  8.1. The initial move ensemble $\Omega^{0}$

We begin by defining an ensemble of _initial moves_
$\Omega^{0}=\Omega^{0}(\pi)$ that consists of _additive moves_ and _limit
additive moves_ , together with their inverses and the empty moves. We define
these moves $\gamma|_{D}$ on domains $D$ that are open intervals such that the
domain $D$ and the image $\gamma(D)$ are subsets of $A$ .

######  Definition 8.0.

  1. (i)

An _additive move_ is any translation $\tau_{t}|_{D}$, where $t\in(-1,1)$ and
$D\subseteq A$ is an open interval such that $\tau_{t}(D)\subseteq A$ and

$\displaystyle\Delta\pi(x,t)$ $\displaystyle=\pi(x)+\pi(t)-\pi(x+t)=0$
$\displaystyle\forall x\in D$ or any reflection $\rho_{r}|_{D}$, where
$r\in(0,2)$, and $D\subseteq A$ is an open interval such that
$\rho_{r}(D)\subseteq A$ such that $\displaystyle\Delta\pi(x,r-x)$
$\displaystyle=\pi(x)+\pi(r-x)-\pi(r)=0$ $\displaystyle\forall x\in D.$

  2. (ii)

A _limit-additive move_ is any translation $\tau_{\bar{t}}|_{D}$, where
$\bar{t}\in(-1,1)$ and $D\subseteq A$ is an open interval such that
$\tau_{\bar{t}}(D)\subseteq A$ and

$\displaystyle\lim_{t\to\bar{t}^{+}}\Delta\pi(x,t)=0$
$\displaystyle\quad\text{or}\quad\lim_{t\to\bar{t}^{-}}\Delta\pi(x,t)=0$
$\displaystyle\forall x\in D$ or any reflection $\rho_{\bar{r}}|_{D}$, where
$\bar{r}\in(0,2)$, and $\rho_{\bar{r}}(D)\subseteq A$ such that
$\displaystyle\lim_{r\to\bar{r}^{+}}\Delta\pi(x,r-x)=0$
$\displaystyle\quad\text{or}\quad\lim_{r\to\bar{r}^{-}}\Delta\pi(x,r-x)=0$
$\displaystyle\forall x\in D.$

  3. (iii)

An _initial move_ in $\Omega^{0}(\pi)$ is a move that is either additive or
limit-additive, or an inverse of such a move, or an empty move.

######  Remark 8.0.

The property of the moves $\gamma|_{D}\in\Omega^{0}$ that the function $\pi$
is continuous on the domain $D$ and image $\gamma(D)$ will be preserved
throughout.

######  Remark 8.0.

The initial move ensemble $\Omega^{0}$ is join-closed. Therefore, by 3.0, it
is equal to the restriction closure of its maximal elements. Moreover, by
definition, $\Omega^{0}$ satisfies (inv). However, $\Omega^{0}$ in general is
not a semigroup.

The function $\pi$ is affinely $\Omega^{0}$-equivariant (subsection 5.1),
i.e., it respects all moves in $\Omega^{0}$.

###  8.2. Moves from connected open sets of additivities

We now specialize our results from subsection 4.3 regarding connected open
ensembles to the initial moves. We have the following corollary. Recall from
subsection 6.1 the projections $p_{1}(x,y)=x$, $p_{2}(x,y)=y$, and
$p_{3}(x,y)=x+y$ as functions from ${\mathbb{R}}^{2}$ to ${\mathbb{R}}$.

######  Corollary 8.0.

Suppose $E\subseteq{\mathbb{R}}^{2}$ be a connected open set on which $\pi$ is
additive, i.e., $\Delta\pi(x,y)=0$ for $(x,y)\in E$. Let $C=p_{1}(E)\cup
p_{2}(E)\cup p_{3}(E)$ and assume that $C\subseteq A$. Then

$\mathop{\mathrm{moves}}\nolimits(C\times
C)\subseteq\mathop{\mathrm{jsemi}}(\Omega^{0}),$

so $C$ is a connected covered component of
$\mathop{\mathrm{jsemi}}(\Omega^{0})$.

See Figure 12 for an illustration.

######  Remark 8.0.

In [16], the intervals $p_{1}(E),p_{2}(E),p_{3}(E)$ are referred to as
_directly covered intervals_.

###### Proof of 8.0.

Denote $\Gamma^{\vee}=\mathop{\mathrm{jsemi}}(\Omega^{0})$. By 4.0,
$\Gamma^{\vee}=\mathop{\mathrm{i{}semi}}(\Gamma^{\vee})$. We first show that
$\operatorname{Gr}_{\pm}(\Gamma^{\vee})$ contains $E$. Let $(x,y)\in E$. Since
$E$ is open, there exists an open interval $D\ni x$ such that the diagonal
segment $\\{\,(x^{\prime},r-x^{\prime})\mid x^{\prime}\in D\,\\}\subseteq E$,
where $r=x+y$. By 8.0, we have $\rho_{r}|_{D}\in\Omega^{0}$, with
$\rho_{r}|_{D}(x)=y$. Thus, $(x,y)\in\operatorname{Gr}_{-}(\Gamma^{\vee})$.
There exist open intervals $D_{y}\ni y$ and $D_{x}\ni x$ such that the
vertical segment $\\{x\\}\times D_{y}$ and the horizontal segment
$D_{x}\times\\{y\\}$ are contained in $E$. Again by 8.0, we have
$\tau_{y}|_{D_{x}},\tau_{x}|_{D_{y}}\in\Omega^{0}$. Notice that

$x\xmapsto{\tau_{y}|_{D_{x}}}(x+y)\xmapsto{(\tau_{x}|_{D_{y}})^{-1}}y.$

Thus, $(x,y)\in\operatorname{Gr}_{+}(\Gamma^{\vee})$. We showed that
$\operatorname{Gr}_{\pm}(\Gamma^{\vee})$ contains $E$. By Theorem 4.1-(3),
$\mathop{\mathrm{moves}}\nolimits((p_{1}(E)\cup p_{2}(E))\times(p_{1}(E)\cup
p_{2}(E)))\subseteq\Gamma^{\vee}$.

For any point $x+y\in p_{3}(E)$, where $x\in p_{1}(E)$ and $y\in p_{2}(E)$,
the above translation move $\tau_{y}|_{D_{x}}$ satisfies that
$\tau_{y}|_{D_{x}}\in\Omega^{0}$ and $\tau_{y}|_{D_{x}}(x)=x+y$. By applying
6.0 to $\mathcal{C}=\\{p_{1}(E)\cup p_{2}(E)\\}$ and all such moves
$\tau_{y}|_{D_{x}}$, we obtain that
$\mathop{\mathrm{moves}}\nolimits((p_{1}(E)\cup p_{2}(E)\cup
p_{3}(E))\times(p_{1}(E)\cup p_{2}(E)\cup p_{3}(E)))\subseteq\Gamma^{\vee}$. ∎

##  9\. Piecewise linear functions, polyhedral complexes, effective
perturbations

We now specialize our theory to the important case of piecewise linear
functions. We begin with the basic definitions and review some tools that were
developed in the previous papers of the present series.

###  9.1. Continuous and discontinuous piecewise linear functions $\pi$,
complex $\mathcal{P}_{B}$

We begin by giving a definition of ${\mathbb{Z}}$-periodic piecewise linear
functions $\pi\colon{\mathbb{R}}\to{\mathbb{R}}$ that are allowed to be
discontinuous, following [20]. [16] discusses how these functions are
represented in the software [21].

Let $0=x_{0}<x_{1}<\dots<x_{n-1}<x_{n}=1$. Denote by

(9.1) $B=\\{\,x_{0}+t,\,x_{1}+t,\,\dots,\,x_{n-1}+t\mid t\in{\mathbb{Z}}\,\\}$

the set of all breakpoints. The 0-dimensional faces are defined to be the
singletons, $\\{x\\}$, $x\in B$, and the 1-dimensional faces are the closed
intervals, $[x_{i}+t,x_{i+1}+t]$, $i=0,\dots,{n-1}$, $t\in{\mathbb{Z}}$. The
empty face, the 0-dimensional and the 1-dimensional faces form
$\mathcal{P}=\mathcal{P}_{B}$, a locally finite polyhedral complex, periodic
modulo ${\mathbb{Z}}$.

######  Definition 9.0.

We call a function $\pi\colon{\mathbb{R}}\to{\mathbb{R}}$ _piecewise linear_
over $\mathcal{P}_{B}$ if for each face $I\in\mathcal{P}_{B}$, there is an
affine linear function $\pi_{I}\colon{\mathbb{R}}\to{\mathbb{R}}$,
$\pi_{I}(x)=c_{I}x+d_{I}$ such that $\pi(x)=\pi_{I}(x)$ for all
$x\in\operatorname{rel\,int}(I)$.

Under this definition, piecewise linear functions can be discontinuous . Let
$I=[a,b]\in\mathcal{P}_{B}$ be a 1-dimensional face. The function $\pi$ can be
determined on $\operatorname{int}(I)=(a,b)$ by linear interpolation of the
limits $\pi(a^{+})=\lim_{x\to a,x>a}\pi(x)=\pi_{I}(a)$ and
$\pi(b^{-})=\lim_{x\to b,x<b}\pi(x)=\pi_{I}(b)$.

###  9.2. Two-dimensional polyhedral complex $\Delta\mathcal{P}$ and additive
faces

Figure 10. Additive edges in $\Delta\mathcal{P}_{B}$ and the corresponding
initial moves (additive moves and their inverses) in $\Omega^{0}$

Figure 11. Additivities and initial moves. _Left,_ additivities sampled from
two-dimensional additive faces of $\Delta\mathcal{P}$. _Right,_ the move
semigroup $\mathop{\mathrm{jsemi}}(\Omega^{0})$ generated by the initial
moves. The graphs $\operatorname{Gr}_{+}(\Omega)$ (_blue_) and
$\operatorname{Gr}_{-}(\Omega)$ (_red_) are plotted on top of each other. For
illustration purposes, only a finite set of additive moves is considered.

Figure 12.  Additivities in $E(\pi)$ and the corresponding connected covered
components of moves

For a piecewise linear function (see subsection 9.1 for our notation), we now
explain the structure of the initial moves. We will use the notion of the
polyhedral complex $\Delta\mathcal{P}$ and its _additive faces_ from [16,
section 4]. $\Delta\mathcal{P}$ is a two-dimensional polyhedral complex, which
expresses the domains of linearity of the subadditivity slack $\Delta\pi(x,y)$
introduced in subsection 1.2.

######  Definition 9.0.

The polyhedral complex $\Delta\mathcal{P}$ of ${\mathbb{R}}\times{\mathbb{R}}$
consists of the faces

$F(I,J,K)=\left\\{\,(x,y)\in{\mathbb{R}}\times{\mathbb{R}}\mid x\in I,\,y\in
J,\,x+y\in K\,\right\\},$

where $I,J,K\in\mathcal{P}$, so each of $I,J,K$ is either empty, a breakpoint
of $\pi$, or a closed interval delimited by two consecutive breakpoints.

In the continuous case, since the function $\pi$ is piecewise linear over
$\mathcal{P}$, we have that $\Delta\pi$ is affine linear over each (closed)
face $F\in\Delta P$. We say that a face $F\in\Delta\mathcal{P}$ is _additive_
if $\Delta\pi=0$ over all $F$. If $\pi$ is subadditive, then the _set of
additivities_

(9.2) $E(\pi)=\\{\,(x,y)\mid\Delta\pi(x,y)=0\,\\}$

is the union of all additive faces $F\in\Delta\mathcal{P}$; see [7, section
3.4].

For a discontinuous function $\pi$, the subadditivity slack $\Delta\pi$ is
affine linear only over the relative interior of each face $F$. For
additivity, beside the subadditivity slack $\Delta\pi(x,y)$ at a point
$(x,y)$, we also consider its limits.

######  Definition 9.0.

The limit value of $\Delta\pi$ at the point $(x,y)$ approaching from the
relative interior of a face $F\in\Delta\mathcal{P}$ containing $(x,y)$ is
denoted by

$\Delta\pi_{F}(x,y)=\lim_{\begin{subarray}{c}(u,v)\to(x,y)\\\
(u,v)\in\operatorname{rel\,int}(F)\end{subarray}}\Delta\pi(u,v).$

######  Definition 9.0.

Let $F\in\Delta\mathcal{P}$. Define the _set of additivities and limit-
additivities approaching from the relative interior of $F$_ as

(9.3) $E_{F}(\pi)=\bigl{\\{}\,(x,y)\in
F\mathrel{\big{|}}\Delta\pi_{F}(x,y)\text{ exists, and
}\Delta\pi_{F}(x,y)=0\,\bigr{\\}}.$

######  Remark 9.0.

The points $(x,y)\in E_{F}(\pi)$ that lie in $\operatorname{rel\,int}(F)$
capture all additivities of $\pi$, whereas those that lie on the relative
boundary capture all limit-additivities. The set $E(\pi)$ that we introduced
in the continuous case can be partitioned as

$E(\pi)=\bigcup_{F\in\Delta\mathcal{P}}(E_{F}(\pi)\cap\operatorname{rel\,int}(F)).$

######  Lemma 9.0.

Let $\pi$ be a subadditive function that is piecewise linear over
$\mathcal{P}$. Let $F\in\Delta\mathcal{P}$. Let $(x_{0},y_{0})\in
E_{F}(\pi)\subseteq F$ and let $E$ be the unique face of $F$ containing
$(x_{0},y_{0})$ in its relative interior. Then $E\subseteq E_{F}(\pi)$.

We make the following general definition, which is equivalent to the one found
in [16, 20].

######  Definition 9.0.

In the situation of 9.0, we say that the face $E$ is _additive_.

Now the following lemma is clear from the definition. [16] only states this
fact for the case of continuous $\pi$.

######  Lemma 9.0.

Let $\pi$ be a subadditive function that is piecewise linear over
$\mathcal{P}$. Then the set of additive faces of $\pi$ is a polyhedral
subcomplex of $\Delta\mathcal{P}$, i.e., it is closed under taking subfaces.
In particular, each additive face is the convex hull of some additive vertices
(zero-dimensional additive faces).

For a piecewise linear function $\pi$, a finite presentation of the initial
moves is easy to compute using the additive faces of the complex
$\Delta\mathcal{P}$. For a detailed explanation of diagrams visualizing the
additivities and limit-additivities, we refer to [16, sections 4.2–4.3]. See
Figure 10 for the moves from one-dimensional additive faces (edges) and Figure
11 and Figure 12 for the moves from two-dimensional additive faces. In the
forthcoming paper [14], we will give a more detailed description how to
compute the finite presentation of the initial moves.

######  Remark 9.0.

The zero-dimensional additive faces (i.e., additive vertices) of
$\Delta\mathcal{P}_{B}$ do not give rise to moves (cf. 5.0). Instead they will
be considered in section 10 to determine a refinement of $\mathcal{P}_{B}$ for
the decomposition of perturbations.

###  9.3. Effective perturbations $\tilde{\pi}$

We recall the notion of effective perturbations from subsection 1.4. An
effective perturbation is a function
$\tilde{\pi}\colon{\mathbb{R}}\to{\mathbb{R}}$ for which there exists an
$\epsilon>0$ such that $\pi^{\pm}=\pi\pm\epsilon\tilde{\pi}$ are minimal valid
functions.

######  Remark 9.0.

Let $\pi$ be a minimal valid function for $R_{f}({\mathbb{R}},{\mathbb{Z}})$.
From (1.3a), (1.3c), and (1.3e) it follows that $0\leq\pi\leq 1$, so $\pi$ is
a bounded function. Now if $\tilde{\pi}$ is an effective perturbation, then
$\pi^{\pm}=\pi\pm\epsilon\tilde{\pi}$ for some $\epsilon>0$, where also