# Controlled quantum dot array segmentation via a highly tunable interdot
tunnel coupling

Martin Nurizzo  Univ. Grenoble Alpes, CNRS, Grenoble INP, Institut Néel,
F-38000 Grenoble, France  Baptiste Jadot  Univ. Grenoble Alpes, CEA, Leti,
F-38000 Grenoble, France  Pierre-André Mortemousque  Univ. Grenoble Alpes,
CEA, Leti, F-38000 Grenoble, France  Vivien Thiney  Univ. Grenoble Alpes, CEA,
Leti, F-38000 Grenoble, France  Emmanuel Chanrion  Univ. Grenoble Alpes, CNRS,
Grenoble INP, Institut Néel, F-38000 Grenoble, France  Matthieu Dartiailh
Univ. Grenoble Alpes, CNRS, Grenoble INP, Institut Néel, F-38000 Grenoble,
France  Arne Ludwig  Lehrstuhl für Angewandte Festkörperphysik, Ruhr-
Universität Bochum, Universitätsstraße 150, D-44780 Bochum, Germany  Andreas
D. Wieck  Lehrstuhl für Angewandte Festkörperphysik, Ruhr-Universität Bochum,
Universitätsstraße 150, D-44780 Bochum, Germany  Christopher Bäuerle  Univ.
Grenoble Alpes, CNRS, Grenoble INP, Institut Néel, F-38000 Grenoble, France
Matias Urdampilleta  Univ. Grenoble Alpes, CNRS, Grenoble INP, Institut Néel,
F-38000 Grenoble, France  Tristan Meunier  Univ. Grenoble Alpes, CNRS,
Grenoble INP, Institut Néel, F-38000 Grenoble, France

###### Abstract

Recent demonstrations using electron spins stored in quantum dots array as
qubits are promising for developing a scalable quantum computing platform. An
ongoing effort is therefore aiming at the precise control of the quantum dots
parameters in larger and larger arrays which represents a complex challenge.
Partitioning of the system with the help of the inter-dot tunnel barriers can
lead to a simplification for tuning and offers a protection against unwanted
charge displacement. In a triple quantum dot system, we demonstrate a
nanosecond control of the inter-dot tunnel rate permitting to reach the two
extreme regimes, large GHz tunnel coupling and sub-Hz isolation between
adjacent dots. We use this novel development to isolate a sub part of the
array while performing charge displacement and readout in the rest of the
system. The degree of control over the tunnel coupling achieved in a unit cell
should motivate future protocol development for tuning, manipulation and
readout including this capability.

Arrays of quantum dots (QDs) are identified as one possible road for scaling
up electron spin-based quantum processors Vinet  _et al._ (2018); Li  _et al._
(2018); Veldhorst  _et al._ (2017); Vandersypen  _et al._ (2017). In this
context, the ability to displace controllably individual electrons plays an
important role for realizing elementary operations within the array.
Displacement at the dot scale induces high fidelity coherent manipulation and
interaction Petta  _et al._ (2005); Brunner  _et al._ (2011); Watson  _et al._
(2018); Yoneda  _et al._ (2018). Displacement at multi-dot scale enables array
filling Mortemousque  _et al._ (2021); Volk  _et al._ (2019), and
functionalities for long distance quantum interconnection Mortemousque  _et
al._ (2021); Mills  _et al._ (2019a); Jadot  _et al._ (2021). These
displacement capabilities come with potential sources of errors such as
incorrect positioning and tunneling while operating the electron spin qubits.
It is therefore desirable to find protocols to minimize their impact on the
rest of the qubits. The tunnel barrier control over a large range offers
strategies to protect the electron spin information without losing quantum
manipulation capabilities Eenink  _et al._ (2019). In semiconductor devices,
this method is commonly used to isolate QD arrays from electron reservoirs,
thereby fixing the total number of charges in the system Bertrand  _et al._
(2015); Yang  _et al._ (2020).

Here we characterize the inter-dot tunnel rate from the sub-Hz to GHz regime
and achieve complete isolation both from the reservoirs and the neighbor QD of
up to three electrons. Then, we implement two functionalities demonstrating
the potential of the array partitioning process. First, an improvement of
metastable charge states lifetime and their readout at a fixed and optimized
position, and then charge displacement and readout in the partitioned array.

Figure 1:  Device, electron loading and isolation from the reservoirs. a,
Electron micrograph of a sample similar to the one measured. b, Stability
diagram of the leftmost QD. The derivative of the current (with respect to
$V_{\textrm{B1}}$) measured across the SET is plotted as a function of the
voltage applied on $\textrm{B}_{\textrm{1}}$ and $\textrm{B}_{\textrm{2}}$
gates controlling respectively the reservoir-QD tunnel barrier height and the
chemical potential of the QD. The electron occupation number is indicated for
the first four charge regions of the stability diagram. The indicated
positions $\textrm{L}_{1}$, $\textrm{L}_{2}$, $\textrm{L}_{3}$ and I are used
to respectively load 1, 2, 3 electrons in the left QD and to isolate the QD
array from the left electron reservoir. c, Schematic of the potential
landscape at position $\textrm{L}_{3}$ of the stability diagram. d, Schematic
of the potential landscape at position I of the stability diagram after the
loading procedure.

The device measured in this work is presented in Fig. 1a and is composed of a
linear triple QD array defined electrostatically by voltages applied to
metallic gates on a GaAs/AlGaAs heterostructure. The electrometer consists of
a single electron transistor (SET) set on the side of a Coulomb peak to be
sensitive to the charge configuration of the array. The QD array is tuned by
adjusting the voltage applied on the gates labelled as $\textrm{B}_{1-4}$. The
gate voltages applied for each experiment discussed are summarized in Sup.
Mat. I. We first focus on the protocol to isolate a quantum dot from the
reservoirs. The first step is to load electrons from the bottom left reservoir
(Fig. 1a) to the previously emptied QD nanostructure. We show in Fig. 1b, a
so-called stability diagram where we vary the voltages applied on
$\textrm{B}_{\textrm{1}}$ and $\textrm{B}_{\textrm{2}}$ while recording the
current $i_{\textrm{SET}}$ through the electrometer. In this diagram it is
possible to determine the absolute number of electrons in the dot by
identifying regions separated by charge degeneracy lines. The chemical
potential of L is controlled by the voltage applied on
$\textrm{B}_{\textrm{2}}$ while the reservoir to QD tunnel coupling is
controlled by the voltage applied to $\textrm{B}_{\textrm{1}}$, as indicated
by the disappearance of the charge degeneracy lines for $V_{\textrm{B1}}<-0.8\
\textrm{V}$. The interruption of the degeneracy lines is an indicator of the
isolated regime where the electron exchange rate with the reservoir is slower
than the measurement sweep rate (250 mV/s). We engineered a pulse sequence to
load the desired number of electrons in the QD structure and isolate them from
the reservoir. The system is first initialized at point I empty of any
electrons and the pulse sequence drawn on top of the stability diagram of Fig.
1b is applied. A voltage pulse on $\textrm{B}_{\textrm{1}}$ gate increases the
coupling between the array and the reservoir, allowing the exchange of
electrons with dot L. Then the chemical potential of the left QD is lowered by
applying a voltage pulse on gate $\textrm{B}_{\textrm{2}}$. By varying the
amplitude of this pulse to reach either the point $\textrm{L}_{1}$,
$\textrm{L}_{2}$ or $\textrm{L}_{3}$ it is possible to load respectively 1, 2
or 3 electrons in the dot. A sketch of the potential landscape at the position
$\textrm{L}_{3}$ is pictured in Fig. 1c. From the selected position, voltage
pulses are applied on gate $\textrm{B}_{\textrm{1}}$ and then
$\textrm{B}_{\textrm{2}}$ to reach the position I, where the electron
tunneling to the reservoir is suppressed (see Sup. Mat. II). In this
configuration, the high chemical potential of the left QD guarantees that all
loaded electrons should eventually tunnel back to the reservoir leaving the QD
empty. However, due to the low tunnel coupling to the reservoir this
metastable configuration can be held for several tens of seconds (see Sup.
Mat. II).

In this section, the isolation process is pushed one step further to perform
array partitioning by demonstrating QD-to-QD decoupling. We note the charge
configuration of the array $(l,m,r)$ with $l$, $m$ and $r$ the charge
occupation of the QDs L, M and R, respectively. After loading either 1, 2 or 3
electrons in L, we vary the voltages applied on $\textrm{B}_{\textrm{2}}$ and
$\textrm{B}_{\textrm{3}}$ to progressively transfer charges to dot M. The
corresponding stability diagrams are presented in Fig. 2a, b, c. For a system
of $n$ dots containing a total of $k$ electrons, we expect $\binom{n+k-1}{k}$
charge states, which we experimentally observe for $n=2$ and $k$ up to 3.
Analogous to the QD-reservoir decoupling, we observe the apparition of
stochastic events as $V_{\textrm{B2}}$ becomes increasingly more negative.
This phenomenon now corresponds to the L-M inter-dot tunnel rate becoming
comparable to the measurement sweep rate (250 mV/s).

Figure 2:  1, 2 and 3 electrons stability diagram of a DQD. a,b,c, Stability
diagram of the L-M DQD performed with a fixed number of charges respectively
1, 2 and 3 isolated from the reservoirs. The detuning and the tunnel coupling
of the L-M DQD are swept using relevant gates $\textrm{B}_{\textrm{3}}$ and
$\textrm{B}_{\textrm{2}}$. It is possible to access all charge states of the
DQD by sweeping $\textrm{B}_{\textrm{3}}$ gate voltage over around 200 mV. For
a negative enough voltage applied on $\textrm{B}_{\textrm{2}}$ the stability
diagram exhibits excited charge states of the DQD that are only observable in
the low tunnel coupling regime. Charge configurations of the array are
indicated in white.

In order to quantify the inter-dot tunnel rate dependence with the voltage
applied on gate $\textrm{B}_{\textrm{2}}$, we designed the pulse sequence
sketched on top of the stability diagrams in Fig. 2b. Two electrons are loaded
in L and the system is brought in the $(110)$ configuration at position S.
From this point, the tunnel coupling is lowered to the desired value
$V_{\textrm{B2}}^{\textrm{F}}$ using a voltage pulse on the gate
$\textrm{B}_{\textrm{2}}$. After 100 ns the detuning is set to reach the
$(020)$ charge region via a voltage pulse on gate $\textrm{B}_{\textrm{3}}$.
At this position the $(110)$ charge state becomes metastable. To track the
evolution of the charge state, we record the current $i_{\textrm{SET}}$ during
up to 1 s. The procedure is repeated 1000 times for
$V_{\textrm{B2}}^{\textrm{F}}$ between -0.72 V and -0.68 V. Selected records
of $i_{\textrm{SET}}$ for $V_{\textrm{B2}}^{\textrm{F}}=-0.69\ \textrm{V}$ are
shown in Fig. 3a and we observe sharp single jumps of $i_{\textrm{SET}}$ from
0.55 nA to 0.75 nA. These events are associated to an electron tunneling from
M to L. In Fig. 3b we compute the probability $P_{(110)}$ to observe the
$(110)$ charge state as a function of the waiting time at point F and observe
an exponential decay of the population. In Fig. 3c, we observe that the charge
state lifetime can be tuned over 4 orders of magnitude in few tens of mV. In
particular, for $V_{\textrm{B2}}^{\textrm{F}}\leqslant-0.72V$, no relaxation
events are visible in a thousand 1 s-long time-traces, setting a higher tunnel
rate bound at $10^{-2}$ Hz. This demonstrates that we are able to reduce the
inter-dot tunnel rate well below the Hz regime while keeping the initial QD
structure intact. Moreover, the high level of control in the low inter-dot
tunnel coupling regime did not prevent us to perform spin qubit operation
which requires a GHz tunnel coupling in the same sample with the same tuning
(data not shown here).

Figure 3:  Probing relaxation process of a metastable charge state in DQD. a,
Selected single shot measurements of $(110)$ to $(020)$ relaxation for
$V_{\textrm{B2}}^{\textrm{F}}=-0.69\ \textrm{V}$. The system is initialized to
point P in the $(110)$ charge configuration. The tunnel barrier height between
the dots is set by applying a pulse of varying amplitude
$V_{\textrm{B2}}^{\textrm{F}}$. The system is then brought back in the region
where the equilibrium charge state of the array is (020). The current
$i_{\textrm{SET}}$ displays single event relaxation. A moving average filter
is applied to the traces for clarity. b, Relaxation of the (110) to (020)
charge state observed for different tunnel barrier height. A threshold is
defined halfway between the two current levels represented by a dashed line in
a. For the $1000$ traces, a current above or below this threshold is
associated to respectively $(110)$ or $(020)$ charge state. The binarized
traces are averaged for each $V_{\textrm{B2}}^{\textrm{F}}$ value tested to
compute the $(110)$ population. Experimental data is represented as solid
points and the solid black line is an exponential decay fit. For
$V_{\textrm{B2}}^{\textrm{F}}=-0.72\ \textrm{V}$ we do not observe any
relaxation event in 1000 shots of 1 s. c, Relaxation rate of the (110) to the
(020) charge state as a function of the freeze point (F) coordinate.  Figure
4:  1, 2 and 3 electrons freeze map in a DQD. a,b,c, 1, 2 and 3 electrons
freeze map of the L-M DQD. The measurements are obtained by performing the
pulse sequence sketched on top of the stability diagram in Fig. 2a. The first
pulse probes the DQD at a certain value of detuning and tunnel coupling at a
varied point P. The second one brings back the system at point M by first
setting the tunnel coupling in the sub-Hz regime and then the detuning.
Finally, the current $i_{\textrm{SET}}$ is recorded during 5 ms.

The capability to operate over such a wide range the inter-dot tunnel coupling
enables novel functionalities for future prospects in spin qubit technology Li
_et al._ (2018). Indeed, freezing on a fast timescale the electron dynamics
results in a well separated and metastable charge configuration that can be
efficiently probed. Proof of principle experiment is performed in a tunnel
coupled double quantum dot (DQD) with up to three electrons. The protocol
consists in loading a specific charge configuration in the double dot,
decrease on fast timescale the tunnel barrier and then tune the system to a
working point at which the charge detection has been optimized while
preserving the charge configuration.

To do so we manipulate the inter-dot tunnel coupling and the detuning of the
L-M DQD at the nanosecond timescale. The initialization of metastable charge
configuration of the array is characterized using a freeze map protocol. It
consists in setting the system at a given detuning and tunnel coupling value
before pulsing the inter-dot tunnel rate to the sub-Hz regime to freeze the
charge configuration. Followed by a charge readout, this protocol allows us to
identify the detuning and tunnel coupling regions where a charge transfer is
possible.

In addition to the already described notation for labelling the charge states
we introduce a vertical bar $\lvert$ indicating a sub-Hz tunnel coupling rate
in between the QDs. The trajectory, visible in Fig. 2a, starts in the
$(0\lvert 10)$ charge state at point M and is used to realize the freeze map
protocol. Two 100 ns voltages pulses applied sequentially to
$\textrm{B}_{\textrm{2}}$ and $\textrm{B}_{\textrm{3}}$ set the system to
point P. Then, the inter-dot tunnel rate is lowered to the sub-$\mathrm{Hz}$
regime and the detuning is set back to position M. At this position the
electrometer signal $i_{\textrm{SET}}$ is averaged during 5 ms. Depending on
the coordinates of point
P($V_{\textrm{B2}}^{\textrm{P}}$,$V_{\textrm{B3}}^{\textrm{P}}$), we obtain
two possible values for $i_{\textrm{SET}}$ corresponding to either the
$(0\lvert 10)$ or $(1\lvert 00)$ charge state, as shown in Fig. 4a. Comparing
with the stability diagram in Fig. 2a, for $V_{\textrm{B2}}>-0.65\ \textrm{V}$
we observe the same charge transition at $V_{\textrm{B3}}=-1.07\ \textrm{V}$.
It indicates that the time spent at P is sufficient to observe charge
transfer. For $V_{\textrm{B2}}<-0.65\ \textrm{V}$, the tunnel coupling rate is
not strong enough to allow charge transfer in the ground state at
$V_{\textrm{B3}}=-1.07\ \textrm{V}$. Nevertheless, by increasing the detuning
($V_{\textrm{B3}}<-1.07\ \textrm{V}$) higher orbital states of M with higher
tunnel coupling are accessible and allow the charge transfer within the time
spent in P. The complete description of the charge dynamics to account for the
precise shape of the charge transition is beyond the scope of this work and
will be studied further in subsequent experiments. The agreement between the
freeze map and the stability diagram is also observed for 2 and 3 electrons
loaded in the array as shown in Fig. 4b,c. To conclude, we demonstrated the
capability to initialize metastable charge configuration for a duration long
enough to permit their readout at an optimized position in the voltage gate
space. This study is a first demonstration of the novel initialization and
readout protocols induced by the high level of control over the inter-dot
tunnel coupling.

Figure 5:  Isolating sub parts of the linear QD array. a, Schematic of the
potential landscape at the initialization point. b, Schematic of the potential
landscape at the beginning of the stability diagram of figure c. c, Stability
diagram performed while a a part of the array is segmented. For
$V^{\textrm{T}}_{\textrm{B2}}<-0.75\ \textrm{V}$ the electron in L is unable
to tunnel back to M and the only charge state seen on the stability diagram
are ($1|20$), ($1|11$) and ($1|02$). For higher values of
$V^{\textrm{T}}_{\textrm{B2}}$ the electron in L tunnels back to M and all
charge states of 3 electrons in a DQD are observed. d, Chronograph of the
voltages applied on gate $\textrm{B}_{\textrm{2}}$, $\textrm{B}_{\textrm{3}}$
and $\textrm{B}_{\textrm{4}}$. The pre-sequence is dedicated to create a
metastable charge state ($1|20$) using the pulse sequence described in Fig.
4c. Then the voltage applied on $\textrm{B}_{\textrm{2}}$ gate is pulsed
during 1 ms to $V^{\textrm{T}}_{\textrm{B2}}$ and finally the chemical
potential of the R QD is ramped while the current $i_{\textrm{SET}}$ is
recorded.

In addition to an improvement of the charge determination in QD arrays, the
inter-dot tunnel coupling control also grants us the possibility to isolate
subparts of a QD array to simplify the tuning and manipulation. In this
section we demonstrate the complete isolation of a sub part of the QD array
while keeping the complete control over the charge configuration in the rest
of the system. To do so we initialize a metastable charge state of the L-M DQD
in order to isolate an electron in L. Then we progressively transfer the
charges remaining in M to R to control the number of electrons present in the
M-R DQD subsystem.

The first step to implement this protocol consists in loading 3 electrons in M
to reach the (030) charge state. From there, a ($1|20$) metastable charge
configuration is initialized by pulsing the voltages applied on gate
$\textrm{B}_{\textrm{2}}$ and $\textrm{B}_{\textrm{3}}$, an equivalent of the
pulse sequence performed is sketched on top of the freeze map in Fig. 4c. The
next step consists in opening the tunneling between M and R by applying -0.65
V on gate $\textrm{B}_{\textrm{3}}$, and lowering the chemical potential of R
closer to the one of M by increasing the voltage applied on
$\textrm{B}_{\textrm{4}}$ to -1.15 V. In this voltage configuration the L-M
inter-dot tunnel coupling is pulsed during 1 ms using a voltage pulse of
amplitude $V^{\textrm{T}}_{\textrm{B2}}$. Following the pulse, the detuning of
L-R is ramped using the voltage applied on gate $\textrm{B}_{\textrm{4}}$
while $i_{\textrm{SET}}$ is recorded. The derivative $\partial
i_{\textrm{SET}}/\partial V_{\textrm{B4}}$ is plotted as a function of
$V_{\textrm{B4}}^{\textrm{R}}$ and $V_{\textrm{B2}}^{\textrm{T}}$ in Fig. 5c.
For $V_{\textrm{B2}}^{\textrm{T}}<-0.75\ \textrm{V}$ we observe two degeneracy
lines in the stability diagram indicating that the sub array composed of M and
R QDs contains only two electrons while the third one is isolated in L. Due to
the low L-M inter-dot tunnel coupling, the electron in L cannot tunnel back to
M during the whole 1.2 s ramp, in this configuration the only charge states
available by the array are $(1\lvert 02)$, $(1\lvert 11)$ and $(1\lvert 02)$
(see Sup. Mat. III). They are identified and labelled on top of the stability
diagram. For a pulse amplitude $V_{\textrm{B2}}^{\textrm{T}}>-0.75\
\textrm{V}$, we observe a third line, indicating that the electron stored in L
tunneled back to M during the $V_{\textrm{B2}}^{\textrm{T}}$ pulse. Indeed,
this configuration allows the relaxation of the (120) to the (030) charge
state and the resulting stability diagram corresponds to a classical one for
three electrons loaded in a DQD. To conclude, we are able to perform electron
manipulation in a partitioned DQD while preserving the charge state in the
adjacent QD. This study demonstrates the ability of the array partitioning to
lower the complexity of the stability diagrams by reducing the number of
charge states available for the electrons.

The control of the tunnel couplings and the chemical potential of each QD on
fast timescales allowed us to initialize arbitrary metastable charge state of
up to three electrons in a DQD. The freeze map protocol developed in this
article allowed us to enhance the lifetime and perform readout of these states
at a fixed and optimized position in the voltage gate space. This
demonstration is of particular interest in the context of the wide use of
Pauli spin blocked spin to charge conversion whose fidelity is limited by the
lifetime of such metastable charge states Barthel  _et al._ (2009). We finally
performed a segmentation of the array by decoupling a QD filled with one
electron while performing charge displacement and readout in the rest of the
structure. Doing so we observed a reduction of the charge states available for
the system and therefore a reduction of the complexity while tuning the QD
array. The partitioning protocol opens the door to more complex applications
such as the operation of larger 1D or 2D arrays of QDs while keeping the low
dimensionality of simple sub systems Mills  _et al._ (2019b).

See supplementary material for additional information of the array tuning and
the array partitioning protocol.

We acknowledge technical support from the Pole groups of the Institut Néel,
and in particular the NANOFAB team who helped with the sample realization, as
well as T. Crozes, E. Eyraud, D. Lepoittevin, C. Hoarau and C. Guttin. This
work is supported by the ERC QUCUBE. A.L. and A.D.W. acknowledge gratefully
support of DFG-TRR160 and DFH/UFA CDFA-05-06, DFG project 383065199, and BMBF
QR.X Project 16KISQ009.

The data that support the findings of this study are available from the
corresponding author upon reasonable request.

The authors have no conflicts to disclose.

M.N. and V.T. fabricated the sample. M.N. performed the experiment with the
help of B.J. M.N. interpreted the data with the help of B.J., P.-A.M., E.C.,
M.D. and T.M. A.L. and A.D.W. performed the design and molecular-beam-epitaxy
growth of the high-mobility heterostructure. All the authors discussed the
results extensively, as well as the manuscript.

## References

  * Vinet  _et al._ (2018) M. Vinet, L. Hutin, B. Bertrand, S. Barraud, J.-M. Hartmann, Y.-J. Kim, V. Mazzocchi, A. Amisse, H. Bohuslavskyi, L. Bourdet, A. Crippa, X. Jehl, R. Maurand, Y.-M. Niquet, M. Sanquer, B. Venitucci, B. Jadot, E. Chanrion, P.-A. Mortemousque, C. Spence, M. Urdampilleta, S. De Franceschi, and T. Meunier, “Towards scalable silicon quantum computing,” in  _2018 IEEE International Electron Devices Meeting (IEDM)_ (2018) pp. 6.5.1–6.5.4.
  * Li  _et al._ (2018) R. Li, L. Petit, D. P. Franke, J. P. Dehollain, J. Helsen, M. Steudtner, N. K. Thomas, Z. R. Yoscovits, K. J. Singh, S. Wehner, L. M. K. Vandersypen, J. S. Clarke, and M. Veldhorst, “A crossbar network for silicon quantum dot qubits,” Science Advances 4, eaar3960 (2018).
  * Veldhorst  _et al._ (2017) M. Veldhorst, H. G. J. Eenink, C. H. Yang, and A. S. Dzurak, “Silicon CMOS architecture for a spin-based quantum computer,” Nature Communications 8, 1766 (2017).
  * Vandersypen  _et al._ (2017) L. M. K. Vandersypen, H. Bluhm, J. S. Clarke, A. S. Dzurak, R. Ishihara, A. Morello, D. J. Reilly, L. R. Schreiber, and M. Veldhorst, “Interfacing spin qubits in quantum dots and donors—hot, dense, and coherent,” npj Quantum Information 3, 34 (2017).
  * Petta  _et al._ (2005) J. R. Petta, A. C. Johnson, J. M. Taylor, E. A. Laird, A. Yacoby, M. D. Lukin, C. M. Marcus, M. P. Hanson, and A. C. Gossard, “Coherent Manipulation of Coupled Electron Spins in Semiconductor Quantum Dots,” Science 309, 2180–2184 (2005).
  * Brunner  _et al._ (2011) R. Brunner, Y.-S. Shin, T. Obata, M. Pioro-Ladrière, T. Kubo, K. Yoshida, T. Taniyama, Y. Tokura, and S. Tarucha, “Two-Qubit Gate of Combined Single-Spin Rotation and Interdot Spin Exchange in a Double Quantum Dot,” Physical Review Letters 107, 146801 (2011).
  * Watson  _et al._ (2018) T. F. Watson, S. G. J. Philips, E. Kawakami, D. R. Ward, P. Scarlino, M. Veldhorst, D. E. Savage, M. G. Lagally, M. Friesen, S. N. Coppersmith, M. A. Eriksson, and L. M. K. Vandersypen, “A programmable two-qubit quantum processor in silicon,” Nature 555, 633–637 (2018).
  * Yoneda  _et al._ (2018) J. Yoneda, K. Takeda, T. Otsuka, T. Nakajima, M. R. Delbecq, G. Allison, T. Honda, T. Kodera, S. Oda, Y. Hoshi, N. Usami, K. M. Itoh, and S. Tarucha, “A quantum-dot spin qubit with coherence limited by charge noise and fidelity higher than 99.9%,” Nature Nanotechnology 13, 102–106 (2018).
  * Mortemousque  _et al._ (2021) P.-A. Mortemousque, E. Chanrion, B. Jadot, H. Flentje, A. Ludwig, A. D. Wieck, M. Urdampilleta, C. Bäuerle, and T. Meunier, “Coherent control of individual electron spins in a two-dimensional quantum dot array,” Nature Nanotechnology 16, 296–301 (2021).
  * Volk  _et al._ (2019) C. Volk, A. M. J. Zwerver, U. Mukhopadhyay, P. T. Eendebak, C. J. van Diepen, J. P. Dehollain, T. Hensgens, T. Fujita, C. Reichl, W. Wegscheider, and L. M. K. Vandersypen, “Loading a quantum-dot based “Qubyte” register,” npj Quantum Information 5, 1–8 (2019).
  * Mills  _et al._ (2019a) A. R. Mills, D. M. Zajac, M. J. Gullans, F. J. Schupp, T. M. Hazard, and J. R. Petta, “Shuttling a single charge across a one-dimensional array of silicon quantum dots,” Nature Communications 10, 1063 (2019a).
  * Jadot  _et al._ (2021) B. Jadot, P.-A. Mortemousque, E. Chanrion, V. Thiney, A. Ludwig, A. D. Wieck, M. Urdampilleta, C. Bäuerle, and T. Meunier, “Distant spin entanglement via fast and coherent electron shuttling,” Nature Nanotechnology 16, 570–575 (2021).
  * Eenink  _et al._ (2019) H. G. J. Eenink, L. Petit, W. I. L. Lawrie, J. S. Clarke, L. M. K. Vandersypen, and M. Veldhorst, “Tunable Coupling and Isolation of Single Electrons in Silicon Metal-Oxide-Semiconductor Quantum Dots,” Nano Letters 19, 8653–8657 (2019).
  * Bertrand  _et al._ (2015) B. Bertrand, H. Flentje, S. Takada, M. Yamamoto, S. Tarucha, A. Ludwig, A. D. Wieck, C. Bäuerle, and T. Meunier, “Quantum Manipulation of Two-Electron Spin States in Isolated Double Quantum Dots,” Physical Review Letters 115, 096801 (2015).
  * Yang  _et al._ (2020) C. H. Yang, R. C. C. Leon, J. C. C. Hwang, A. Saraiva, T. Tanttu, W. Huang, J. Camirand Lemyre, K. W. Chan, K. Y. Tan, F. E. Hudson, K. M. Itoh, A. Morello, M. Pioro-Ladrière, A. Laucht, and A. S. Dzurak, “Operation of a silicon quantum processor unit cell above one kelvin,” Nature 580, 350–354 (2020).
  * Barthel  _et al._ (2009) C. Barthel, D. J. Reilly, C. M. Marcus, M. P. Hanson, and A. C. Gossard, “Rapid Single-Shot Measurement of a Singlet-Triplet Qubit,” Physical Review Letters 103, 160503 (2009), arXiv:0902.0227 .
  * Mills  _et al._ (2019b) A. R. Mills, M. M. Feldman, C. Monical, P. J. Lewis, K. W. Larson, A. M. Mounce, and J. R. Petta, “Computer-automated tuning procedures for semiconductor quantum dot arrays,” Applied Physics Letters 115, 113501 (2019b).


$0\leq\pi^{\pm}\leq 1$, and so $\tilde{\pi}$ is a bounded function as well.

We note that the space $\tilde{\Pi}^{\pi}$ of effective perturbations,
introduced in subsection 1.4, is a vector space.

######  Lemma 9.0.

Let $\pi$ be a minimal valid function. The space $\tilde{\Pi}^{\pi}$ of
effective perturbation functions is a vector space, a subspace of the space
${\mathcal{B}({{\mathbb{R}}})}$ of bounded functions.

For the case of piecewise linear functions $\pi$ that are continuous from at
least one side of the origin, we have the following regularity theorem for
effective perturbations.

######  Lemma 9.0 ([16, Lemma 6.4]).

Let $\pi$ be a piecewise linear minimal valid function that is continuous from
the right at $0$ or continuous from the left at $1$. If $\pi$ is continuous on
a proper interval $I\subseteq[0,1]$, then for any
$\tilde{\pi}\in\tilde{\Pi}^{\pi}$ we have that $\tilde{\pi}$ is Lipschitz
continuous on the interval $I$.

(This is a strengthening of [8, Theorem 2].)

The purpose of the additive move ensemble is to infer properties of the
effective perturbation functions. For additive moves $\gamma|_{D}$, it follows
from convexity that every effective perturbation $\tilde{\pi}$ respects
$\gamma|_{D}$. In the case of piecewise linear functions, this extends to
limit-additive moves. The following lemma is shown by the proof of [16,
Theorem 6.3] , along with [16, Footnote 13] and also by [20, Theorem 3.3] in
the case where $\pi$ is two-sided discontinuous at the origin.

######  Lemma 9.0.

Let $\pi$ be a piecewise linear minimal valid function for
$R_{f}({\mathbb{R}},{\mathbb{Z}})$. Let $\gamma|_{D}\in\Omega^{0}$ be an
initial move, where $D\subseteq(0,1)$ is an open interval. Then $\pi$ respects
$\gamma|_{D}$, and every effective perturbation function
$\tilde{\pi}\in\tilde{\Pi}^{\pi}$ respects $\gamma|_{D}$.

######  Corollary 9.0.

Let $\pi$ be a piecewise linear minimal valid function for
$R_{f}({\mathbb{R}},{\mathbb{Z}})$. Then $\pi$ respects the moves closure
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$. If $\pi$ is is continuous from at
least one side of the origin, then every effective perturbation function
$\tilde{\pi}\in\tilde{\Pi}^{\pi}$ also respects the moves closure
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$.

###### Proof.

This follows from 9.0, 9.0, 9.0 and Theorem 7.4. ∎

###  9.4. Closed move semigroup generated by $\Omega^{0}$, rational case

We have the following theorem.

######  Theorem 9.1 (Finite presentation of the moves closure, rational case).

Let $\pi$ be a piecewise linear function whose breakpoints are rational, i.e.,
$B\subseteq G=\frac{1}{q}{\mathbb{Z}}$ for some $q\in{\mathbb{N}}$. Then the
moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ has a finite
presentation $(\Omega^{\mathrm{red}},{\mathcal{C}})$ in reduced form, where
(i) the endpoints of all domains and the values $t$ and $r$ of moves
$\tau_{t},\rho_{r}|_{D}\in\Omega^{\mathrm{red}}$ lie in $G\cap[0,1]$, (ii) the
endpoints of all maximal intervals of all $C_{i}\in{\mathcal{C}}$ lie in
$G\cap[0,1]$.

###### Proof sketch.

We can compute $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ in finitely many
steps using a completion-type algorithm that manipulates finite presentations,
maintaining properties (i) and (ii), using only the algebraic and order-
theoretic axioms and (extendA). The initialization is provided by 4.1, noting
that vertices of additive faces of $\Delta\mathcal{P}$ lie in $G\times G$.
There are only finitely many finite presentations satisfying (i) and (ii);
this implies the finiteness of the algorithm. ∎

We defer all details about such an algorithm, as well as its generalization to
non-rational input, to the forthcoming paper [14].

Instead, in the next section, we assume that a finite presentation
$(\Omega^{\mathrm{fin}},{\mathcal{C}})$ of the moves closure
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ is given. Using the finite
presentation, we can give a description of the space of effective
perturbations.

##  10\. Perturbation space

Let $\pi\colon{\mathbb{R}}\to{\mathbb{R}}$ be a minimal valid function. In
this section, we work with the following assumptions. (We will mention them
explicitly only in statements of main theorems.)

###  10.1. Assumptions: Piecewise linear $\pi$, one-sided continuous at $0$,
finitely presented moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$

######  Assumption 10.0.

The minimal valid function $\pi$ is piecewise linear (subsection 9.1) and
continuous from at least one side of the origin.

######  Assumption 10.0.

The set $B$ is minimal, i.e., $\mathcal{P}_{B}$ is the coarsest polyhedral
complex over which $\pi$ is piecewise linear.

Let $\Omega^{0}=\Omega^{0}(\pi)$ be the initial additive move ensemble
(section 8) of $\pi$.

######  Assumption 10.0.

The moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ has a finite
presentation $(\Omega,\mathcal{C})$ in reduced form (subsection 6.5).

Thus $\Omega$ has finitely many moves and $\mathcal{C}$ has finitely many
connected covered components $C_{1},C_{2},\dots,C_{k}$, each of which is a
finite union of open intervals. Each $\gamma|_{D}\in\Omega$ is maximal in the
restriction partial order of $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ and is
not contained in $\mathop{\mathrm{jmoves}}\nolimits(\mathcal{C})$. Figures 13
(right), 15, and 16 show examples of
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ satisfying 10.0.

###  10.2. Properties of the finitely presented moves closure

Let $C:=C_{1}\cup C_{2}\cup\dots\cup C_{k}$ denote the open set of points in
$(0,1)$ that are covered. We will refer to the open set
$U:=(0,1)\setminus\operatorname{cl}(C)$ as the set of points in $(0,1)$ that
are _uncovered_. Let

(10.1) $X:=\\{0\\}\cup\partial C\cup\\{1\\}=\\{0\\}\cup\partial U\cup\\{1\\}$

be the set of endpoints of all covered and uncovered intervals. Thus we have
the partition $[0,1]=C\cup X\cup U$.

######  Example 10.0.

Figure 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 (_blue graph at the left and top borders_), where the additive faces
are _colored in green_. (Right) The graph of the moves closure
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ of $\pi$. It has a finite
presentation by $\Omega=\\{\tau_{0}|_{(0,1/2)},\rho_{1/2}|_{(0,1/2)}\\}$
(_blue and red line segments of slopes $\pm 1$_) and one (maximal) connected
covered component $C=(\frac{1}{2},1)$ (the _brown square_ shows $C\times C$).
The set $C\cup X\cup Y\cup Z$ of covered points and refined breakpoints is
marked in _magenta on the left and top borders_.

Consider the discontinuous minimal valid function for $f=\tfrac{1}{2}$,
defined by

$\pi(x)=\begin{cases}0&\text{if }x=0\\\ \tfrac{1}{2}&\text{if
}0<x<\tfrac{1}{2}\\\ 2(1-x)&\text{if }\tfrac{1}{2}\leq x<1.\end{cases}$

It is provided by the software [21] as
$\pi=\textsf{equiv7{\textunderscore}\allowbreak{}example{\textunderscore}\allowbreak{}1()}$.
Figure 13 shows the two-dimensional polyhedral complex $\Delta\mathcal{P}$ and
the moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$. The interval
$C=(\tfrac{1}{2},1)$ is covered, $U=(0,\tfrac{1}{2})$ is uncovered. We have
$X=\\{0,\tfrac{1}{2},1\\}$.

######  Example 10.0.

Figure 14. The function $\pi=\textsf{equiv7{\textunderscore}\allowbreak
example{\textunderscore}\allowbreak xyz{\textunderscore}\allowbreak 2()}$ from
10.0 (_blue graph at the left and top borders_) and its two-dimensional
polyhedral complex $\Delta\mathcal{P}$ (_solid gray lines_), where the
additive faces are _colored in green_. The refined complex
$\Delta{\mathcal{T}}$ is shown with _dotted gray lines_.  Figure 15. The
function $\pi=\textsf{equiv7{\textunderscore}\allowbreak
example{\textunderscore}\allowbreak xyz{\textunderscore}\allowbreak 2()}$ from
10.0 (_colored graph at the left and top borders_) and the graph of the moves
closure $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ of $\pi$, as computed by
the command igp.equiv7_mode = True;
igp.extremality_test(igp.equiv7_example_xyz_2(), True,
show_all_perturbations=True). It has a finite presentation by
$\Omega=\\{\tau_{0}|_{(0,1)},\rho_{11/12}|_{(0,11/12)}\\}$ (_blue and red line
segments of slopes $\pm 1$_) and a set $\mathcal{C}=\\{C_{1},C_{2},C_{3}\\}$
of (maximal) connected covered components $C_{1}=(\frac{11}{12},1)$ (the
_lavender square_ shows $C_{1}\times C_{1}$),
$C_{2}=(0,\frac{1}{24})\cup(\frac{7}{8},\frac{11}{12})$ (_coral_), and
$C_{3}=(\frac{1}{24},\frac{1}{8})\cup(\frac{1}{6},\frac{1}{4})\cup(\frac{2}{3},\frac{3}{4})\cup(\frac{19}{24},\frac{7}{8})$
(_lime_). The set $C\cup B^{\prime}=C\cup X\cup Y\cup Z$ of covered points and
refined breakpoints is marked in _magenta on the left and top borders_.

Consider the continuous minimal valid function $\pi$ that is provided as
equiv7_example_xyz_2() by the software [21], shown in Figure 14. Figures 14
and 15 show the additive faces and the moves closure. We have
$X=\\{0,\frac{1}{24},\frac{1}{8},\frac{1}{6},\frac{1}{4},\frac{2}{3},\frac{3}{4},\frac{19}{24},\frac{7}{8},\frac{11}{12},1\\}$.

######  Example 10.0.

Figure 16. Moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ for the
function from 10.0,
$\pi=\textsf{equiv7{\textunderscore}\allowbreak}\allowbreak\textsf{minimal{\textunderscore}\allowbreak}\allowbreak\textsf{2{\textunderscore}\allowbreak
covered{\textunderscore}\allowbreak}\allowbreak\textsf{2{\textunderscore}\allowbreak
uncovered()}$. It has two connected covered components (_cyan, brown
rectangles_).

Consider the minimal valid function $\pi$ that is provided as
equiv7_minimal_2_covered_2_uncovered() by the software [21]; see Figure 16. It
has two connected covered components. The set of uncovered points is
$U=(\frac{12}{49},\frac{13}{49})\cup(\frac{14}{49},\frac{15}{49})\cup\dots\cup(\frac{20}{49},\frac{21}{49})$.
Thus we have
$X=\\{0,\frac{12}{49},\frac{13}{49},\dots,\frac{20}{49},\frac{21}{49},1\\}$.

Recall the two-dimensional polyhedral complex $\Delta\mathcal{P}_{B}$ and its
additive faces, introduced in subsection 9.2. Let

(10.2) $V:=\bigl{\\{}\,p_{i}(x,y)\mathrel{\big{|}}(x,y)\text{ additive vertex
of }\Delta\mathcal{P}_{B},\;i=1,2,3\,\bigr{\\}}\cap[0,1]$

be the set of $p_{1},p_{2}$ and $p_{3}$ projections (within the fundamental
domain) of the zero-dimensional additive faces (i.e., additive vertices).
Because $(x,0)$ is an additive vertex of $\Delta\mathcal{P}_{B}$ for every
$x\in B$, the set $V$ contains $B\cap[0,1]$. By 8.0, the initial move ensemble
$\Omega^{0}$ is join-closed . We consider the ensemble $\Omega^{0}|_{U}$ of
moves restricted to $U$, as defined in subsection 3.2. By 3.0 it is also join-
closed and therefore, by 3.0, has a presentation by its maximal elements. It
follows from 9.0 that its maximal elements have the following relation to the
set $V$.

######  Lemma 10.0.

If $\gamma|_{(a,b)}\in\operatorname{Max}(\Omega^{0}|_{U})$, then the endpoints
$a,b$ lie in $V\cap U$ or $\partial U$.

Next we define the set

(10.3) $Y:=\Omega(V\cap U)=\\{\,\gamma|_{D}(x)\mid x\in V\cap U,\;x\in D\text{
and }\gamma|_{D}\in\Omega\,\\},$

the orbit of $V\cap U$ under $\Omega$, which is a finite set by 10.0.

######  Remark 10.0.

In terms of graphs of ensembles, we have

(10.4) $Y=\\{\,y\mid\exists\,x\in V\cap U\text{ such that
}(x,y)\in\operatorname{Gr}(\Omega)\,\\}.$

######  Lemma 10.0.

We have (a) $V\cap U\subseteq Y$, and (b) $Y\subseteq U$.

###### Proof.

(a) Let $x\in V\cap U$. Since $\Delta\pi(x,y)=0$ for any $x\in{\mathbb{R}}$
when $y=0$, we know that there is open interval $D$ with $x\in D\subseteq U$
such that the idempotent $\tau_{0}|_{D}$ is in $\Omega^{0}$ and hence in
$\mathop{\mathrm{restrict}}(\Omega)$ as well. Since $x=\tau_{0}|_{D}(x)$, we
obtain that $x\in Y$.

(b) Suppose for the sake of contradiction that there is $y\in Y$ but
$y\in\operatorname{cl}(C)$. We can write $y$ as $y=\gamma|_{D}(x)$ where $x\in
V\cap U$, $x\in D$ and $\gamma|_{D}\in\Omega$. Under 10.0, by 6.0 applied to
$\mathcal{C}$ and $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$, we have that $C$
is invariant under the action of moves from
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$. Since the inverse move
$(\gamma|_{D})^{-1}\in\Omega\subseteq\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$,
we obtain that $x=(\gamma|_{D})^{-1}(y)\in\operatorname{cl}(C)$. This
contradicts $x\in U$. ∎

######  Example 10.0 (10.0, continued).

In the example shown in Figure 15, we have $V\cap
U=\\{\frac{1}{3},\frac{5}{12},\frac{1}{2},\frac{7}{12}\\}$. This set is
already closed under the action of $\Omega$, as
$\rho_{11/12}(\frac{1}{3})=\frac{7}{12}$ and
$\rho_{11/12}(\frac{5}{12})=\frac{1}{2}$. Thus $Y=V\cap U$ in the example.

We consider the ensembles $\Omega|_{U}$ and ${}_{U}|\Omega|_{U}$ of moves
restricted and double-restricted to $U$, as defined in subsection 3.2. We have
the following results.

######  Lemma 10.0.

The move ensemble $\Omega|_{U}$ satisfies:

  1. (a)

$\Omega|_{U}={}_{U}|\Omega|_{U}$.

  2. (b)

$\Omega|_{U}$ is a finite move ensemble.

###### Proof.

It follows directly from 10.0. ∎

######  Lemma 10.0 (Filtration of $\mathop{\mathrm{i{}semi}}(\Omega^{0}|_{U})$
by word length; maximal moves).

For $k\in{\mathbb{N}}$, let

$\displaystyle\Omega^{0}|_{U}{}^{k}=\bigl{\\{}\,\gamma^{k}|_{D^{k}}\circ\dots\circ\gamma^{1}|_{D^{1}}\mathrel{\big{|}}\,$
$\displaystyle\gamma^{i}|_{D^{i}}\in\Omega^{0}|_{U}\text{ for $1\leq i\leq
k$}\,\bigr{\\}}.$

Then $\Omega^{0}|_{U}{}^{1}\subseteq\Omega^{0}|_{U}{}^{2}\subseteq\dots$ and
$\mathop{\mathrm{i{}semi}}(\Omega^{0}|_{U})=\bigcup_{k\in{\mathbb{N}}}\Omega^{0}|_{U}{}^{k}$.
For each $k\in{\mathbb{N}}$, the ensemble $\Omega^{0}|_{U}{}^{k}$ satisfies
(restrict) and has a presentation by the set
$\operatorname{Max}(\Omega^{0}|_{U}{}^{k})$ of its maximal elements, which is
a finite set. For
$\gamma|_{(a,b)}\in\operatorname{Max}(\Omega^{0}|_{U}{}^{k})$, we have
$a,b,\gamma(a),\gamma(b)\in X\cup Y$.

###### Proof.

Because $\Omega^{0}$ satisfies (inv), (continuation), and (restrict) by 8.0,
so does its double restriction ${}_{U}|\Omega^{0}|_{U}$ to the uncovered set
$U$. By 10.0-(a), we have
$\operatorname{im}(\Omega^{0}|_{U})\subseteq\operatorname{im}(\Omega|_{U})=\operatorname{im}({}_{U}|\Omega|_{U})\subseteq
U$, hence $\Omega^{0}|_{U}={}_{U}|\Omega^{0}|_{U}$. Recall that
$\Omega^{0}|_{U}{}$ is join-closed and therefore has a presentation by its
maximal elements. It follows from the definition of $\Omega^{0}$, 10.0 with
9.0, and 8.0 that $\operatorname{Max}(\Omega^{0}|_{U}{})$ is finite.

Let
$\operatorname{Max}(\Omega^{0}|_{U}{})^{k}=\\{\,\gamma^{k}|_{\hat{D}^{k}}\circ\dots\circ\gamma^{1}|_{\hat{D}^{1}}\mid\gamma^{i}|_{\hat{D}^{i}}\in\operatorname{Max}(\Omega^{0}|_{U}{})\,\\}$,
a finite set. Then
$\operatorname{Max}(\Omega^{0}|_{U}{}^{k})\subseteq\operatorname{Max}(\Omega^{0}|_{U}{})^{k}$
is finite, and every element of $\Omega^{0}|_{U}{}^{k}$ is the restriction of
an element of $\operatorname{Max}(\Omega^{0}|_{U}{}^{k})$. The chain of
inclusions $\Omega^{0}|_{U}{}^{1}\subseteq\Omega^{0}|_{U}{}^{2}\subseteq\dots$
holds because the idempotents $\tau_{0}|_{D}$ for intervals $D\subseteq U$ are
elements of $\Omega^{0}|_{U}$.

Last, we prove the claim regarding the endpoints; we actually prove the
slightly stronger claim $a,b,\gamma(a),\gamma(b)\in\partial U\cup Y$ by
induction by word length $k$. Since each $\Omega^{0}|_{U}{}^{k}$ satisfies
(inv), it suffices to prove $a,b\in\partial U\cup Y$. For $k=1$, let
$\gamma|_{(a,b)}\in\operatorname{Max}(\Omega^{0}|_{U}{}^{1})=\operatorname{Max}(\Omega^{0}|_{U}{})$.
Then, by 10.0, each of the endpoints $a$, $b$ lies in $V\cap U\subseteq Y$, or
it lies in $\partial U$. Now we proceed by induction. Take
$\gamma^{1}|_{(a,b)}\in\operatorname{Max}(\Omega^{0}|_{U}{})$ and
$\gamma^{2}|_{(c,d)}\in\operatorname{Max}(\Omega^{0}|_{U}{}^{k-1})$, so
$a,b,c,d\in\partial U\cup Y$. Then, by (1.9),
$\gamma^{2}|_{(c,d)}\circ\gamma^{1}|_{(a,b)}$ has domain
$(a,b)\cap(\gamma^{1})^{-1}((c,d))$. If the domain is nonempty, let $x$ be an
endpoint of it. If $x=a,b$, nothing is to show, so assume $x\in(a,b)$ and
$x=(\gamma^{1})^{-1}(y)$, where $y=c$ or $y=d$, so $y\in\partial U\cup Y$. But
$y=\gamma^{1}|_{(a,b)}(x)\in U$, so $y\in Y$. Then it follows that also $x\in
Y$. ∎

By 10.0, all elements of $\Omega$ are maximal moves of the moves closure
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$. Therefore, by 3.0, all elements of
$\Omega|_{U}$ are maximal moves of
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})|_{U}$.

After these preliminaries, we are able to state the main theorem.

######  Theorem 10.1 (Structure and generation theorem for finitely presented
moves closures).

Under 10.0, we have

  1. (a)

$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})=\mathop{\mathrm{extend}_{A}}(\,\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{U})\cup\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{C})\,)$.

  2. (b)

$\Omega|_{U}=\operatorname{Max}(\mathop{\mathrm{extend}_{A}}(\mathop{\mathrm{i{}semi}}(\Omega^{0}|_{U})))$.

  3. (c)

$a,b,\gamma(a),\gamma(b)\in X\cup Y$ for any $\gamma|_{(a,b)}\in\Omega|_{U}$.

We emphasize that the theorem does _not_ depend on an algorithm to compute the
moves closure.

###### Proof.

_Part (a)._ Let $\Omega^{\prime}$ denote the right hand side of the equation
in part (a). Clearly,
$\Omega^{0}\subseteq\Omega^{\prime}\subseteq\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$.
We now show that $\Omega^{\prime}$ is a closed move semigroup. By 10.0-(a), we
have that

$\displaystyle\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{U})$
$\displaystyle\subseteq\mathop{\mathrm{restrict}}(\Omega|_{U})\subseteq\mathop{\mathrm{moves}}\nolimits(U\times
U);$ $\displaystyle\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{C})$
$\displaystyle=\mathop{\mathrm{moves}}\nolimits({\mathcal{C}})\subseteq\mathop{\mathrm{moves}}\nolimits(C\times
C),$

where the open sets $U$ and $C$ are disjoint. Thus, we have that
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{U})\cup\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{C})$
is a move semigroup, under 10.0. It follows from 7.3 that $\Omega^{\prime}$ is
a move semigroup that satisfies (extendA). Note that for any open intervals
$D$ and $I$ such that $\mathop{\mathrm{moves}}\nolimits(D\times
I)\subseteq\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$, we have
$\mathop{\mathrm{moves}}\nolimits(D\times
I)\subseteq\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{C})$. Therefore,
$\Omega^{\prime}$ also satisfies (kaleido). Moreover, (lim) holds by Theorem
7.3. We conclude that $\Omega^{\prime}$ is a closed move semigroup. Hence,
part (a) holds.

_Part (b)._ By restricting the moves ensembles on both sides of the equation
in part (a) to domain $U$, we obtain that

(10.5)
$\mathop{\mathrm{restrict}}(\Omega|_{U})=\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})|_{U}=\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{U})$

Next, we show that

(10.6)
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{U})=\mathop{\mathrm{extend}_{A}}(\mathop{\mathrm{i{}semi}}(\Omega^{0}|_{U})).$

It follows from 7.3 that
$\mathop{\mathrm{extend}_{A}}(\mathop{\mathrm{i{}semi}}(\Omega^{0}|_{U}))$ is
a move semigroup that satisfies (extendA) (and also (continuation) and
(restrict)). Since

(10.7)
$\mathop{\mathrm{extend}_{A}}(\mathop{\mathrm{i{}semi}}(\Omega^{0}|_{U}))\subseteq\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{U})=\mathop{\mathrm{restrict}}(\Omega|_{U}),$

where the equality follows from (10.5), and $\Omega|_{U}$ is a finite move
ensemble by 10.0-(b), we obtain that the move semigroup
$\mathop{\mathrm{extend}_{A}}(\mathop{\mathrm{i{}semi}}(\Omega^{0}|_{U}))$
also satisfies (kaleido) and (lim). Therefore,
$\mathop{\mathrm{extend}_{A}}(\mathop{\mathrm{i{}semi}}(\Omega^{0}|_{U}))$ is
a closed move semigroup which contains $\Omega^{0}|_{U}$. Since
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{U})$ is the smallest closed move
semigroup containing $\Omega^{0}|_{U}$, we have

$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0}|_{U})\subseteq\mathop{\mathrm{extend}_{A}}(\mathop{\mathrm{i{}semi}}(\Omega^{0}|_{U})).$

Together with (10.7), we conclude that (10.6) holds. Since $\Omega$ has only
maximal moves, (10.5) and (10.6) imply the equation in part (b).

_Part (c)._ Let $\gamma|_{(a,b)}\in\Omega|_{U}$. By symmetry, it suffices to
show that $a,b\in X\cup Y$. Consider $x=a$ or $x=b$. Part (b) implies that

$\Omega|_{U}=\operatorname{Max}(\mathop{\mathrm{extend}_{A}}(\mathop{\mathrm{jsemi}}(\Omega^{0}|_{U}))).$

Together with (7.2), we know that $x$ is the limit of a sequence
$\\{x^{j}\\}_{j\in{\mathbb{N}}}$, where $x^{j}$ is an endpoint of the domain
$D^{j}$ of a move
$\gamma|_{D^{j}}\in\operatorname{Max}(\mathop{\mathrm{jsemi}}(\Omega^{0}|_{U}))$.
By 10.0 and 3.0, for any $j\in{\mathbb{N}}$, we have that $D^{j}$ is a maximal
subinterval of
$\bigcup\\{\,D\mid\gamma|_{D}\in\bigcup_{k\in{\mathbb{N}}}\operatorname{Max}(\Omega^{0}|_{U}{}^{k})\,\\}$.
Thus for every $j\in{\mathbb{N}}$, there exists a sequence
$\\{x^{j}_{k}\\}_{k\in{\mathbb{N}}}$ such that each $x^{j}_{k}$ is an endpoint
of the domain of a move
$\gamma|_{D^{j}_{k}}\in\operatorname{Max}(\Omega^{0}|_{U}{}^{k})$, and
$x^{j}_{k}\to x^{j}$ as $k\to\infty$. We obtain that $x^{k}_{k}\to x$ as
$k\to\infty$, where each $x^{k}_{k}\in X\cup Y$ by 10.0. Since $X\cup Y$ is a
finite discrete set under 10.0, we obtain that $x\in X\cup Y$. ∎

###  10.3. Refined breakpoints $B^{\prime}$, complex ${\mathcal{T}}$

In addition to the finite sets $X$ and $Y$, we define

(10.8) $Z:=\\{\,x\mid x\in U,\;x=\rho|_{D}(x)\text{ for some reflection move
}\rho|_{D}\in\Omega\,\\},$

the set of _uncovered character conflicts_.

######  Remark 10.1.

In terms of $\operatorname{Gr}_{+}$ and $\operatorname{Gr}_{-}$ notations, the
set $Z$ is the set of projections of the intersection of the translation and
reflection moves graphs restricted to the uncovered intervals, $Z=\\{\,x\mid
x\in U,\;(x,x)\in\operatorname{Gr}_{\pm}(\Omega)\,\\}$.

######  Example 10.1 (10.0, continued).

In the example shown in Figure 15, we have $Z=\\{\frac{11}{24}\\}$.

######  Theorem 10.2.

Under 10.0, the sets $X$, $Y$, and $Z$ are closed under the action of all
moves from $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$.

###### Proof.

Let $\gamma|_{D}$ be a move in $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$.

Let $x\in X$ such that $x\in D$. Since $C$ is invariant under the action of
all moves from $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$, we have that
$\gamma|_{D}(x)\in X$.

Let $y\in Y$ such that $y\in D$. There exist $x\in V\cap U$ and
$\gamma^{\prime}|_{D^{\prime}}\in\Omega$ such that
$\gamma^{\prime}|_{D^{\prime}}(x)=y$. We have
$\gamma|_{D}(y)=\gamma|_{D}\circ\gamma^{\prime}|_{D^{\prime}}(x)$, where
$\gamma|_{D}\circ\gamma^{\prime}|_{D^{\prime}}\in\mathop{\mathrm{restrict}}(\Omega)$.
Therefore, $\gamma|_{D}(y)\in Y$.

Let $z\in Z$ such that $z\in D$. By definition, $z\in U$ and
$z=\rho|_{D^{\prime}}(z)$ for some reflection move
$\rho|_{D^{\prime}}\in\Omega$. Let $z^{\prime}=\gamma|_{D}(z)$. We have that
$z^{\prime}\in U$ and
$z^{\prime}=\gamma|_{D}\circ\rho|_{D^{\prime}}\circ(\gamma|_{D})^{-1}(z^{\prime})$,
where
$\gamma|_{D}\circ\rho|_{D^{\prime}}\circ(\gamma|_{D})^{-1}\in\mathop{\mathrm{restrict}}(\Omega)$.
Therefore, $z^{\prime}=\gamma|_{D}(z)\in Z$. ∎

Under 10.0, the sets $X$, $Y$, $Z$ are finite. We then define $B^{\prime}$,
which is a finite set of points under 10.0, a _refined set of breakpoints_ ,

(10.9) $B^{\prime}:=(X\cup Y\cup Z)+{\mathbb{Z}}.$

By 10.0, $B\cap C=\emptyset$ and thus $B\subseteq B^{\prime}$. Hence, the
polyhedral complex

(10.10) ${\mathcal{T}}:=\mathcal{P}_{B^{\prime}},$

is a refinement of $\mathcal{P}_{B}$, so our function $\pi$ is piecewise
linear over ${\mathcal{T}}$. The following result shows that each of the
$p_{1},p_{2}$ and $p_{3}$ projections of any additive vertex of the two-
dimensional polyhedral complex $\Delta{\mathcal{T}}$ is either in $B^{\prime}$
or covered by $C$.

######  Theorem 10.3 (Breakpoint stabilization theorem).

Let $(x,y)$ be an additive vertex of $\Delta{\mathcal{T}}$. Let $z=x+y$. Then,
$x,y,z\in B^{\prime}\cup(C+{\mathbb{Z}})$.

###### Proof.

Let $F$ be the unique face of $\Delta\mathcal{P}_{B}$ such that
$(x,y)\in\operatorname{rel\,int}(F)$. Since $(x,y)$ is an additive vertex of
$\Delta{\mathcal{T}}$, and $\Delta\pi$ is non-negative and affine linear over
$F$, we have that $F$ is an additive face of $\Delta\mathcal{P}_{B}$. Consider
$t=x,y$ or $z$. By ${\mathbb{Z}}$-periodicity, we can assume $t\in[0,1]$. To
show that $t\in(B^{\prime}\cap[0,1])\cup C$, we distinguish three cases, as
follows. We recall that $B^{\prime}\cap[0,1]=X\cup Y\cup Z$ and
$U=(0,1)\setminus\operatorname{cl}(C)$.

Assume that $F$ is a zero-dimensional additive face of
$\Delta\mathcal{P}_{B}$. Then, $(x,y)$ is an additive vertex of
$\Delta\mathcal{P}_{B}$, and thus $t\in V$. If $t\in\operatorname{cl}(C)$,
then $t\in X\cup C\subseteq B^{\prime}\cup C$. Otherwise, $t\in V\cap U$.
Since $V\cap U\subseteq Y$ by 10.0, we obtain that $t\in Y\subseteq
B^{\prime}$.

Assume that $F$ is a one-dimensional additive face (say, a horizontal additive
edge) of $\Delta\mathcal{P}_{B}$. Then, $y\in B\subseteq B^{\prime}$ and the
move $\tau_{y}|_{D}$ with $x\in D:=\operatorname{int}(p_{1}(F))$ is in
$\Omega^{0}$. Since $(x,y)$ is a vertex of $\Delta{\mathcal{T}}$, at least two
of $x,y,z$ are in $B^{\prime}$, and hence at least one of $x$ and $z$ is in
$B^{\prime}$. Without loss of generality, we assume that $x\in B^{\prime}$. By
Theorem 10.2, $z=\tau_{y}|_{D}(x)\in B^{\prime}$ as well. We showed that
$x,y,z\in B^{\prime}$ in this case. We omit the proof of the cases where $F$
is a vertical or diagonal additive edge of $\Delta\mathcal{P}_{B}$, which are
similar to the above proof.

Assume that $F$ is a two-dimensional additive face of $\Delta\mathcal{P}_{B}$.
Then, by 8.0, we have $t\in C$. ∎

######  Remark 10.3.

Theorem 10.3 is key to our grid-free theory. In the grid case of [3], where
$B=\tfrac{1}{q}{\mathbb{Z}}$, the projections $p_{1}\colon(x,y)\mapsto x$,
$p_{2}\colon(x,y)\mapsto y$, and $p_{3}\colon(x,y)\mapsto x+y$ map all
vertices of $\Delta\mathcal{P}_{B}$ back to the set $B$. We have stabilization
of breakpoints due to unimodularity. Going to higher dimension (minimal valid
functions of several variables), the piecewise linear functions defined on a
standard triangulation of ${\mathbb{R}}^{2}$ studied in [7, 4] also stabilize.
However, the non-existence of triangulations with stabilization for
${\mathbb{R}}^{k}$, $k\geq 3$ [13] blocks the path for further generalizations
of the approach of [3, 7, 4]. Our Theorem 10.3 depends on more detailed data
of the function than the group $G$ generated by $B$. This “dynamic”
stabilization result could pave the way to generalizations to higher
dimension.

###  10.4. Connected uncovered components $U_{i}$

Define

(10.11) $U^{\prime}:=U\setminus B^{\prime}.$

The interval $[0,1]$ is partitioned into the set $C$ of covered points, the
set $U^{\prime}$ of uncovered points and the set $B^{\prime}\cap[0,1]$ of
breakpoints of ${\mathcal{T}}$. We consider the ensemble
$\Omega|_{U^{\prime}}$ of maximal moves restricted to $U^{\prime}$ as defined
in subsection 3.2. 10.0 and Theorems 10.1 and 10.2 imply the following
corollary.

######  Corollary 10.3.

Under Assumptions 10.0 and 10.0, the move ensemble $\Omega|_{U^{\prime}}$
satisfies that:

  1. (a)

$\Omega|_{U^{\prime}}={}_{U^{\prime}}|\Omega|_{U^{\prime}}$.

  2. (b)

$\Omega|_{U^{\prime}}$ is a finite move ensemble.

  3. (c)

For any $\gamma|_{D}\in\Omega|_{U^{\prime}}$, $\operatorname{cl}(D)$ and
$\operatorname{cl}(\gamma(D))$ are faces of ${\mathcal{T}}$.

We partition the set of uncovered points $U^{\prime}$ into the (maximal)
_connected uncovered components_ $\\{U_{1},\dots,U_{l}\\}$, as follows.222This
extends the terminology of [3] where connected components are grid-based. A
connected uncovered component $U_{i}$ ($1\leq i\leq l$) is a maximal subset of
$U^{\prime}$ that is the disjoint union of all the uncovered intervals
$I_{1},I_{2},\dots,I_{p}\subseteq U^{\prime}$ such that any pair of intervals
$I_{j}$ and $I_{k}$ ($1\leq j,k\leq p$) are connected by a maximal move
$\gamma|_{I_{k}}\in\Omega|_{U^{\prime}}$ with domain $I_{k}$ and image
$I_{j}=\gamma(I_{k})$.

######  Remark 10.3.

The set $\Omega|_{U^{\prime}}$ only has moves $\gamma|_{D}$ whose domain $D$
and image $\gamma(D)$ are both contained in the same $U_{i}$, for
$i=1,2,\dots,l$.

Since the function $\pi$ is piecewise linear over ${\mathcal{T}}$ and it
respects $\Omega|_{U^{\prime}}$, we have that $\pi$ is affine linear with the
same slope on the maximal intervals $I_{1},I_{2},\dots,I_{p}$ of the same
connected uncovered component $U_{i}$. Since an effective perturbation
$\tilde{\pi}\in\tilde{\Pi}^{\pi}$ also respects $\Omega|_{U^{\prime}}$, it
takes the same shape on the uncovered intervals
$I_{1},I_{2},\dots,I_{p}\subseteq U_{i}$. We pick
$D\in\\{I_{1},I_{2},\dots,I_{p}\\}$ arbitrarily as the _fundamental domain_ ,
and write $I_{j}=\gamma_{j}(D)$ where $\gamma_{j}|_{D}\in\Omega|_{U^{\prime}}$
for $j=1,2,\dots,p$. Then, the connected uncovered component $U_{i}\subseteq
U^{\prime}$ can be written as $U_{i}=\bigcup\gamma_{j}(D)$.

###  10.5. Finite-dimensional and equivariant perturbation subspaces

Under 10.0, we define the following spaces.

######  Definition 10.3.

Define the _space of finite-dimensional perturbations_ that are piecewise
linear over ${\mathcal{T}}$:

(10.12)
$\tilde{\Pi}^{\pi}_{{\mathcal{T}}}:=\bigl{\\{}\,\tilde{\pi}\in\tilde{\Pi}^{\pi}\mathrel{\big{|}}\tilde{\pi}\text{
is piecewise linear over }{{\mathcal{T}}}\,\bigr{\\}}.$

Thus, functions in $\tilde{\Pi}^{\pi}_{{\mathcal{T}}}$ are allowed to be
discontinuous.

######  Definition 10.3.

Define the _space of equivariant perturbations_ that vanish on the vertices of
${\mathcal{T}}$:

$\tilde{\Pi}^{\pi}_{\mathrm{zero}({\mathcal{T}})}:=\biggl{\\{}\,\tilde{\pi}\in\tilde{\Pi}^{\pi}\mathrel{\bigg{|}}\tilde{\pi}(t)=\lim_{\begin{subarray}{c}x\to
t\\\ x<t\end{subarray}}\tilde{\pi}(t)=\lim_{\begin{subarray}{c}x\to t\\\
x>t\end{subarray}}\tilde{\pi}(t)=0,\;\forall
t\in\operatorname{vert}({\mathcal{T}})\,\biggr{\\}}.$

We will show in Theorem 10.4 that all functions in
$\tilde{\Pi}^{\pi}_{\mathrm{zero}({\mathcal{T}})}$ are Lipschitz continuous.
We will also show that the space is equivariant under the action of
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$, in the sense of subsection 5.1.
This will justify the name.

######  Remark 10.3.

In 9.0 we showed that the space $\tilde{\Pi}^{\pi}$ of effective perturbations
is a vector space. The space $\tilde{\Pi}^{\pi}_{{\mathcal{T}}}$ of finite-
dimensional perturbations and the space
$\tilde{\Pi}^{\pi}_{\mathrm{zero}({\mathcal{T}})}$ of equivariant
perturbations are vector subspaces of it.

######  Remark 10.3.

The vector spaces $\tilde{\Pi}^{\pi}_{{\mathcal{T}}}$ and
$\tilde{\Pi}^{\pi}_{\mathrm{zero}({\mathcal{T}})}$ should not be confounded
with the vector spaces $\bar{\Pi}^{E}_{{\mathcal{T}}}$ and
$\bar{\Pi}^{E}_{\mathrm{zero}({\mathcal{T}})}$ with prescribed additivities
$E=\\{\,(x,y)\mid\Delta\pi(x,y)=0\,\\}$, used in [5, Lemma 3.14], where the
function $\pi$ is assumed to be continuous piecewise linear over
${\mathcal{T}}$ with
$\operatorname{vert}({\mathcal{T}})=\frac{1}{q}{\mathbb{Z}}$,
$q\in{\mathbb{N}}$.

###  10.6. Finite-dimensional linear algebra for
$\tilde{\Pi}^{\pi}_{\mathcal{T}}$

Let $\tilde{\pi}_{\mathcal{T}}\in\tilde{\Pi}^{\pi}_{{\mathcal{T}}}$ be a
finite-dimensional perturbation. Note that $\tilde{\pi}_{\mathcal{T}}$ is a
piecewise linear function, and it is uniquely determined by its values
$\tilde{\pi}_{\mathcal{T}}(x)$ and limits
$\tilde{\pi}_{\mathcal{T}}(x^{-}):=\lim_{t\to
x,t<x}\tilde{\pi}_{\mathcal{T}}(t)$,
$\tilde{\pi}_{\mathcal{T}}(x^{+}):=\lim_{t\to
x,t>x}\tilde{\pi}_{\mathcal{T}}(t)$ at the breakpoints $x\in
B^{\prime}+{\mathbb{Z}}=\operatorname{vert}({\mathcal{T}})$.

######  Lemma 10.3.

A function $\tilde{\pi}_{\mathcal{T}}\colon{\mathbb{R}}\to{\mathbb{R}}$ is a
finite-dimensional perturbation,
$\tilde{\pi}_{\mathcal{T}}\in\tilde{\Pi}^{\pi}_{{\mathcal{T}}}$, if and only
if $\tilde{\pi}_{\mathcal{T}}$ is piecewise linear over ${\mathcal{T}}$ and
satisfies the following conditions.

  1. (i)

$\tilde{\pi}_{\mathcal{T}}(0)=0$ and $\tilde{\pi}_{\mathcal{T}}(f)=0$;

  2. (ii)

$\tilde{\pi}_{\mathcal{T}}(x)=\tilde{\pi}_{\mathcal{T}}(x+t)$ for all
$x\in{\mathbb{R}},\,t\in{\mathbb{Z}}$;

  3. (iii)

For any additive vertex $(x,y)$ of $\Delta{\mathcal{T}}$ and any face
$F\in\Delta{\mathcal{T}}$ such that $(x,y)\in F$, $\Delta\pi_{F}(x,y)=0$
implies $\Delta(\tilde{\pi}_{\mathcal{T}})_{F}(x,y)=0$.

Before we give the proof, we define another space
$\bar{\Pi}^{E_{\bullet}(\pi,{\mathcal{T}})}$, following [19]. Recall from
subsection 9.2 the family of sets $E_{F}(\pi)$, indexed by faces $F$ of a
polyhedral complex, which capture the set of additivities and limit-
additivities of $\pi$. Here we use this family with the refined polyhedral
complex $\Delta{\mathcal{T}}$, considering $\pi$ as a piecewise linear
function on ${\mathcal{T}}$.

######  Definition 10.3.

For a family $E_{\bullet}=\\{E_{F}\\}_{F\in\Delta{\mathcal{T}}}$, define the
_space of perturbation functions with prescribed additivities and limit-
additivities_ $E_{\bullet}$,

$\bar{\Pi}^{E_{\bullet}}=\left\\{\bar{\pi}\colon{\mathbb{R}}\to{\mathbb{R}}\,\Bigg{|}\;\begin{array}[]{@{}r@{\;}c@{\;}l@{\quad}l@{}}\bar{\pi}(0)=\bar{\pi}(f)&=&0\\\
\Delta\bar{\pi}_{F}(x,y)&=&0&\text{ for }(x,y)\in E_{F},\
F\in\Delta{\mathcal{T}}\\\ \bar{\pi}(x+t)&=&\bar{\pi}(x)&\text{ for
}x\in{\mathbb{R}},\,t\in{\mathbb{Z}}\end{array}\;\right\\}.$

###### Proof of 10.3.

We consider $\pi$ as piecewise linear over ${\mathcal{T}}$, which is a
refinement of $\mathcal{P}_{B}$. Let
$\tilde{\pi}_{\mathcal{T}}\in\tilde{\Pi}^{\pi}_{{\mathcal{T}}}$. Then by
definition, $\tilde{\pi}_{\mathcal{T}}$ is also piecewise linear over
${\mathcal{T}}$. Since $\tilde{\pi}_{\mathcal{T}}\in\tilde{\Pi}^{\pi}$, we
have that $\tilde{\pi}_{\mathcal{T}}\in\bar{\Pi}^{E_{\bullet}}$, where
$E_{\bullet}=E_{\bullet}(\pi,{\mathcal{T}})$ is the family of sets
$E_{F}(\pi)$, indexed by $F\in\Delta{\mathcal{T}}$. Namely,
$\tilde{\pi}_{\mathcal{T}}$ satisfies the conditions (i), (ii) and

  1. (iii’)

For any face $F\in\Delta{\mathcal{T}}$ and any $(x,y)\in F$, if
$\Delta\pi_{F}(x,y)=0$ then $\Delta(\tilde{\pi}_{\mathcal{T}})_{F}(x,y)=0$.

The condition (iii’) clearly implies (iii). Thus, we proved the “only if”
direction. Now let $\tilde{\pi}_{\mathcal{T}}$ be a piecewise linear function
over ${\mathcal{T}}$ that satisfies (i)–(iii). Notice that function $\pi$ is
subadditive and also piecewise linear over ${\mathcal{T}}$. Hence, the
condition (iii) implies (iii’). We obtain that
$\tilde{\pi}_{\mathcal{T}}\in\bar{\Pi}^{E_{\bullet}}$, where
$E_{\bullet}=E_{\bullet}(\pi,{\mathcal{T}})$. It then follows from [19,
Theorem 3.1] that $\tilde{\pi}_{\mathcal{T}}\in\tilde{\Pi}^{\pi}$. Therefore,
$\tilde{\pi}_{\mathcal{T}}\in\tilde{\Pi}^{\pi}_{{\mathcal{T}}}$, we proved the
“if” direction. ∎

Assume that
$B^{\prime}=\\{x^{\prime}_{0}=0,x^{\prime}_{1},\dots,x^{\prime}_{n^{\prime}-1},x^{\prime}_{n}=1\\}$
and we identify $\tilde{\pi}_{\mathcal{T}}(x)$ and
$\tilde{\pi}_{\mathcal{T}}(x+t)$ for all $t\in{\mathbb{Z}}$. 10.3 shows that
$\bigl{(}\tilde{\pi}_{\mathcal{T}}(x^{\prime}_{0}\mbox{}^{-}),\,\tilde{\pi}_{\mathcal{T}}(x^{\prime}_{0}),\,\allowbreak\tilde{\pi}_{\mathcal{T}}(x^{\prime}_{0}\mbox{}^{+}),\,\allowbreak\tilde{\pi}_{\mathcal{T}}(x^{\prime}_{1}\mbox{}^{-}),\,\allowbreak\dots,\allowbreak\,\tilde{\pi}_{\mathcal{T}}(x^{\prime}_{n^{\prime}-1}\mbox{}^{-}),\,\allowbreak\tilde{\pi}_{\mathcal{T}}(x^{\prime}_{n^{\prime}-1}),\,\allowbreak\tilde{\pi}_{\mathcal{T}}(x^{\prime}_{n^{\prime}-1}\mbox{}^{+})\bigr{)}$
is a solution to the finite-dimensional linear system defined by (i) and
(iii). The interpolation of such a solution gives an effective perturbation
function $\tilde{\pi}_{\mathcal{T}}\in\tilde{\Pi}^{\pi}_{\mathcal{T}}$. We
know that $(0,0,\dots,0)$ is a trivial solution. If a nontrivial solution
exists, then its interpolation $\tilde{\pi}_{\mathcal{T}}\not\equiv 0$,
implying that the function $\pi$ is not extreme.

######  Remark 10.3.

In fact, one can reduce the number of variables in the above linear system of
equations to solve, by considering the connected components, as follows. 9.0
and (10.12) imply that $\tilde{\pi}_{\mathcal{T}}$ is affine linear with the
same slope over all the intervals from a connected covered component $C_{i}$
($i=1,2,\dots,k$) or from a connected uncovered component $U_{i}$
($i=1,2,\dots,l$). Let $\tilde{s}_{1}^{c},\dots,\tilde{s}_{k}^{c}$ and
$\tilde{s}_{1}^{u},\dots,\tilde{s}_{l}^{u}$ denote the corresponding slope
variables.

In the discontinuous case, by 9.0, using 10.0, the perturbation
$\tilde{\pi}_{\mathcal{T}}$ can only be discontinuous at the points where
$\pi$ is discontinuous. Let the variables $\tilde{d}_{i}$ ($i=1,2,\dots,m)$
denote the changes of the value of $\tilde{\pi}_{\mathcal{T}}$ at the $m$
discontinuity points of $\pi$. In other words, the variables $\tilde{d}_{i}$
denote jumps $\tilde{\pi}_{\mathcal{T}}(x)-\tilde{\pi}_{\mathcal{T}}(x^{-})$
when $\pi$ is discontinuous at $x$ on the left, or
$\tilde{\pi}_{\mathcal{T}}(x^{+})-\tilde{\pi}_{\mathcal{T}}(x)$ when $\pi$ is
discontinuous at $x$ on the right.

Then, for any fixed $x\in{\mathbb{R}}$, the value
$\tilde{\pi}_{\mathcal{T}}(x)$ is uniquely determined by the slope variables
$\tilde{s}_{i}^{c}$ ($i=1,2,\dots,k$), $\tilde{s}_{i}^{u}$ ($i=1,2,\dots,l$)
and the jump variables $\tilde{d}_{i}$ ($i=1,2,\dots,m$). These $k+l+m\leq
3n^{\prime}$ variables satisfy the system of linear equations given by 10.3,
where $(0,0,\dots,0)$ is a trivial solution. See [16, Example 7.2] for a
concrete example.

###  10.7. Equivariant perturbation space
$\tilde{\Pi}^{\pi}_{\textrm{zero}({\mathcal{T}})}$

Let
$\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}\in\tilde{\Pi}^{\pi}_{\textrm{zero}({\mathcal{T}})}$
be an equivariant perturbation of $\pi$. By 6.0 (or 6.0) and 9.0,
$\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}$ is affine linear on all covered
intervals. By definition,
$\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}(t)=\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}(t^{-})=\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}(t^{+})=0$
for every $t\in\operatorname{vert}({\mathcal{T}})$, and $\partial
C\subseteq\operatorname{vert}({\mathcal{T}})$. Therefore,
$\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}$ is zero on
$\operatorname{cl}(C)$. If the set of uncovered points $U^{\prime}=\emptyset$,
then $\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}\equiv 0$. Otherwise, recall
from subsection 10.4 that $U^{\prime}$ is partitioned into connected uncovered
components $U_{1},U_{2},\dots,U_{l}$. The following theorem gives the
characterization of the projection of a perturbation
$\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}$ onto the space of functions with
support contained in a connected uncovered component $U_{i}$.

######  Theorem 10.4 (Characterization of the equivariant perturbations
supported on an uncovered component).

Suppose that Assumptions 10.0,10.0 and 10.0 hold. Let
$U_{i}=\bigcup\gamma_{j}(D)$ be a connected uncovered component, where $D$ is
the fundamental domain for $U_{i}$ and
$\gamma_{j}|_{D}\in\Omega|_{U^{\prime}}$ ($j=1,\dots,p$). Let
$\tilde{\pi}_{i}\colon{\mathbb{R}}\to{\mathbb{R}}$ be a
${\mathbb{Z}}$-periodic function such that $\tilde{\pi}_{i}(x)=0$ for
$x\not\in U_{i}$. Then
$\tilde{\pi}_{i}\in\tilde{\Pi}^{\pi}_{\mathrm{zero}({\mathcal{T}})}$ if and
only if

  1. (i)

$\tilde{\pi}_{i}$ is Lipschitz continuous on $D$;

  2. (ii)

$\tilde{\pi}_{i}(x)=\tilde{\pi}_{i}(x^{-})=\tilde{\pi}_{i}(x^{+})=0$ for
$x\in\partial D$;

  3. (iii)

$\tilde{\pi}_{i}(x)=\chi(\gamma_{j})\tilde{\pi}_{i}(\gamma_{j}(x))$ for $x\in
D$, $j=1,\dots,p$.

###### Proof.

Let $\tilde{\pi}_{i}\in\tilde{\Pi}^{\pi}_{\textrm{zero}({\mathcal{T}})}$.
Since $\pi$ is continuous on $D$, by 9.0, $\tilde{\pi}_{i}$ is Lipschitz
continuous on ${\mathbb{R}}$. Hence, the condition (i) holds. The condition
(ii) is clearly satisfied, as
$\tilde{\pi}_{i}(x)=\tilde{\pi}_{i}(x^{-})=\tilde{\pi}_{i}(x^{+})=0$ for each
$x\in\operatorname{vert}({\mathcal{T}})$. Since $\tilde{\pi}_{i}$ respects
$\Omega|_{U^{\prime}}$, the condition (iii) also holds.

Conversely, let $\tilde{\pi}_{i}\colon{\mathbb{R}}\to{\mathbb{R}}$ be a
${\mathbb{Z}}$-periodic function such that $\tilde{\pi}_{i}(x)=0$ for
$x\not\in U_{i}$ and the conditions (i)–(iii) hold. It follows from (ii) that
$\tilde{\pi}_{i}(x)=\tilde{\pi}_{i}(x^{-})=\tilde{\pi}_{i}(x^{+})=0$ for
$x\in\partial U_{i}$. Since $\tilde{\pi}_{i}(x)=0$ for $x\not\in U_{i}$, we
have

(10.13)
$\tilde{\pi}_{i}(x)=\tilde{\pi}_{i}(x^{-})=\tilde{\pi}_{i}(x^{+})=0\text{ for
}x\in[0,1]\setminus U_{i}\supseteq B^{\prime}\cup C.$

We claim that $\tilde{\pi}_{i}$ satisfies all the additivities (including the
limits) that $\pi$ has. Indeed, let $F$ be a face of $\Delta{\mathcal{T}}$ and
let $(x,y)\in F$ such that $\Delta\pi_{F}(x,y)=0$. We show that
$(\Delta\tilde{\pi}_{i})_{F}(x,y)=0$ by distinguishing the following three
cases.

(a) If $(x,y)$ is an additive vertex of $\Delta{\mathcal{T}}$, then by Theorem
10.3 and (10.13), we have $(\Delta\tilde{\pi}_{i})_{F}(x,y)=0$.

(b) If $(x,y)$ is contained in the relative interior of an edge $F^{\prime}$
of $\Delta{\mathcal{T}}$, then $F^{\prime}\subseteq F$ and $F^{\prime}$ is an
additive face of $\Delta{\mathcal{T}}$. Consider the move
$\gamma|_{D^{\prime}}$ associated with $F^{\prime}$. We have either
$D^{\prime}$ and $\gamma(D^{\prime})\subseteq(0,1)\setminus U_{i}$, or
$D^{\prime}$ and $\gamma(D^{\prime})\subseteq U_{i}$. In the former case, the
claim holds because of (10.13); and in the latter case, the structure of
$\Delta{\mathcal{T}}$ (Theorem 10.3) implies that
$\gamma|_{D^{\prime}}\in\Omega|_{U^{\prime}}$, and thus
$(\Delta\tilde{\pi}_{i})_{F}(x,y)=0$ by the condition (iii).

(c) If $(x,y)$ is contained in the relative interior of a two-dimensional face
$F^{\prime}$ of $\Delta{\mathcal{T}}$, then $F^{\prime}=F$ is a two-
dimensional additive face of $\Delta{\mathcal{T}}$. We have $x,y,(x+y)\bmod
1\in C$, hence the claim follows from (10.13).

We showed that $\tilde{\pi}_{i}\in\bar{\Pi}^{E_{\bullet}}$, where
$E_{\bullet}=E_{\bullet}(\pi,{\mathcal{T}})$ is the family from the proof of
10.3. Then, [19, Theorem 3.1] implies that
$\tilde{\pi}_{i}\in\tilde{\Pi}^{\pi}$. Therefore,
$\tilde{\pi}_{i}\in\tilde{\Pi}^{\pi}_{\textrm{zero}({\mathcal{T}})}$. ∎

For $i=1,\dots,l$, denote the space of functions $\tilde{\pi}_{i}$ as in the
theorem by $\tilde{\Pi}^{\pi}_{U_{i}}$. It is independent of the choice of
fundamental domain.

######  Theorem 10.5 (Direct sum decomposition of equivariant perturbations by
uncovered components).

We have the direct sum decomposition
$\tilde{\Pi}^{\pi}_{\mathrm{zero}({\mathcal{T}})}=\tilde{\Pi}^{\pi}_{U_{1}}\oplus\dots\oplus\tilde{\Pi}^{\pi}_{U_{l}}$,
i.e., if $\tilde{\pi}\in\tilde{\Pi}^{\pi}_{\mathrm{zero}({\mathcal{T}})}$,
then it has a unique decomposition
$\tilde{\pi}=\tilde{\pi}_{1}+\tilde{\pi}_{2}+\dots+\tilde{\pi}_{l}$ such that
$\tilde{\pi}_{i}\in\tilde{\Pi}^{\pi}_{U_{i}}$ for $i=1,\dots,l$.

###### Proof.

Let $\tilde{\pi}\in\tilde{\Pi}^{\pi}_{\textrm{zero}({\mathcal{T}})}$. For
$i=1,2,\dots,l$, define $\tilde{\pi}_{i}:{\mathbb{R}}\to{\mathbb{R}}$,
$\tilde{\pi}_{i}(x)=\tilde{\pi}(x)$ if $x\in U_{i}$ and $\tilde{\pi}_{i}(x)=0$
otherwise. Then

(10.14) $\tilde{\pi}=\tilde{\pi}_{1}+\tilde{\pi}_{2}+\dots+\tilde{\pi}_{l},$

where each $\tilde{\pi}_{i}$ ($i=1,2,\dots,l$) satisfies the conditions in
Theorem 10.4. ∎

Each of the component functions $\tilde{\pi}_{i}$ ($i=1,2,\dots,l$) is
supported on the connected uncovered component $U_{i}$ and is obtained by
choosing an arbitrary Lipschitz continuous template on the fundamental domain
$D_{i}$, then by extending equivariantly to the other intervals through the
moves in $\Omega|_{U^{\prime}}$.

###  10.8. Decomposition theorem for effective perturbations

The following perturbation decomposition theorem, a generalization of [5,
Lemma 3.14] without assuming $\pi$ is continuous and
$\operatorname{vert}({\mathcal{T}})=\frac{1}{q}{\mathbb{Z}}$, shows that the
effective perturbation space $\tilde{\Pi}^{\pi}$ is the direct sum of the
finite-dimensional perturbation space $\tilde{\Pi}^{\pi}_{{\mathcal{T}}}$ and
the equivariant perturbation space
$\tilde{\Pi}^{\pi}_{\mathrm{zero}({\mathcal{T}})}$.

######  Theorem 10.6 (Perturbation decomposition theorem).

Under Assumptions 10.0,10.0 and 10.0, for every effective perturbation
$\tilde{\pi}\in\tilde{\Pi}^{\pi}$, there exist a unique finite-dimensional
perturbation $\tilde{\pi}_{\mathcal{T}}\in\tilde{\Pi}^{\pi}_{\mathcal{T}}$ and
a unique equivariant perturbation
$\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}\in\tilde{\Pi}^{\pi}_{\mathrm{zero}({\mathcal{T}})}$
such that

$\tilde{\pi}=\tilde{\pi}_{\mathcal{T}}+\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}.$

###### Proof.

Let $\tilde{\pi}\in\tilde{\Pi}^{\pi}$ be an effective perturbation. By [16,
Corollary 6.5] , the limits $\tilde{\pi}(t^{-})$ and $\tilde{\pi}(t^{+})$
exist for every $t\in\operatorname{vert}({\mathcal{T}})$. Let
$\tilde{\pi}_{\mathcal{T}}$ be the unique piecewise linear function over
${\mathcal{T}}$ such that $\tilde{\pi}_{\mathcal{T}}(t)=\tilde{\pi}(t)$,
$\tilde{\pi}_{\mathcal{T}}(t^{-})=\tilde{\pi}(t^{-})$ and
$\tilde{\pi}_{\mathcal{T}}(t^{+})=\tilde{\pi}(t^{+})$ for every
$t\in\operatorname{vert}({\mathcal{T}})$. Define
$\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}=\tilde{\pi}-\tilde{\pi}_{\mathcal{T}}$.
Note that $\tilde{\pi}_{\mathcal{T}}$ is the unique piecewise linear function
over ${\mathcal{T}}$ such that
$\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}(t)=\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}(t^{-})=\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}(t^{+})=0$
for every $t\in\operatorname{vert}({\mathcal{T}})$. It is left to show that
$\tilde{\pi}_{\mathcal{T}},\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}\in\tilde{\Pi}^{\pi}$.

We first show that $\tilde{\pi}_{\mathcal{T}}\in\tilde{\Pi}^{\pi}$, by
applying 10.3. It suffices to show that $\tilde{\pi}_{\mathcal{T}}$ satisfies
condition (iii) of 10.3. Let $(x,y)$ be an additive vertex of a face
$F\in\Delta{\mathcal{T}}$ with $\Delta\pi_{F}(x,y)=0$. By [16, Lemma 6.1] ,
$\Delta\pi_{F}(x,y)=0$ implies that $\Delta\tilde{\pi}_{F}(x,y)=0$. Since
$(x,y)$ is an additive vertex of $\Delta{\mathcal{T}}$, Theorem 10.3 implies
that $x,y,z\in B^{\prime}\cup C$, where $z=(x+y)\bmod 1$. We have
$\tilde{\pi}_{\mathcal{T}}(t)=\tilde{\pi}(t)$,
$\tilde{\pi}_{\mathcal{T}}(t^{-})=\tilde{\pi}(t^{-})$ and
$\tilde{\pi}_{\mathcal{T}}(t^{+})=\tilde{\pi}(t^{+})$ for $t=x,y$ or $z$, and
hence
$\Delta(\tilde{\pi}_{\mathcal{T}})_{F}(x,y)=\Delta\tilde{\pi}_{F}(x,y)=0$.
Therefore, $\tilde{\pi}_{\mathcal{T}}\in\tilde{\Pi}^{\pi}$.

Since the vector space $\tilde{\Pi}^{\pi}$ contains both $\tilde{\pi}$ and
$\tilde{\pi}_{\mathcal{T}}$, we obtain that
$\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}=\tilde{\pi}-\tilde{\pi}_{\mathcal{T}}\in\tilde{\Pi}^{\pi}$.
∎

######  Example 10.6 (10.0, continued).

Figure 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$.

For the function in Figure 13,
$\pi=\textsf{equiv7{\textunderscore}\allowbreak{}example{\textunderscore}\allowbreak{}1()}$,
the refined polyhedral complex ${\mathcal{T}}$ has vertices
$B^{\prime}=\\{0,\tfrac{1}{4},\tfrac{1}{2},1\\}$. The finite-dimensional
perturbation space $\tilde{\Pi}^{\pi}_{\mathcal{T}}$ has dimension $1$ and is
spanned by the basic perturbation

$\tilde{\pi}_{\mathcal{T}}(x)=\begin{cases}0&\text{if }x=0\\\
x-\tfrac{1}{4}&\text{if }0<x<\tfrac{1}{2}\\\ 0&\text{if }\tfrac{1}{2}\leq
x<1,\end{cases}$

see Figure 17 (left). The two intervals $I_{1}=(0,\tfrac{1}{4})$ and
$I_{2}=(\tfrac{1}{4},\tfrac{1}{2})$ are uncovered, and they are connected
through the move $\rho_{f}|_{(0,1/2)}$ in $\Omega$. Because there is only one
connected uncovered component, the equivariant perturbation space
$\tilde{\Pi}^{\pi}_{\textrm{zero}({\mathcal{T}})}$ consists of all Lipschitz
continuous functions $\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}$ satisfying
that $\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}(x)=0$ for $x\in C\cup
B^{\prime}$ and that
$\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}(x)=-\tilde{\pi}_{\mathrm{zero}({\mathcal{T}})}(f-x)$
for $x\in U^{\prime}$. See Figure 17 (middle, right) for examples of such
functions.

######  Example 10.6 (10.0, continued).

Figure 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}$.

Figure 18 illustrates the decomposition of the space of effective
perturbations.

######  Example 10.6 (10.0, continued).

Figure 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.

Figure 19 illustrates the decomposition of the space of effective
perturbations.

###  10.9. Relation of the moves closure to the semigroup
$\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi})$ of respected moves

In this section, still under the assumptions from subsection 10.1, we
establish the relation between $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ and
two other move semigroups:

  1. (a)

the semigroup $\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi})$ of moves respected
by all effective perturbation functions $\tilde{\pi}$,

  2. (b)

the semigroup
$\Gamma^{\mathrm{resp}}(\\{\pi\\}\cup\tilde{\Pi}^{\pi})=\Gamma^{\mathrm{resp}}(\pi+\tilde{\Pi}^{\pi})$
of moves respected by $\pi$ and its perturbations.

We already know from 9.0 that

(10.15)
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})\subseteq\Gamma^{\mathrm{resp}}(\pi+\tilde{\Pi}^{\pi})\subseteq\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi}).$

In the case of an extreme function $\pi$, the space $\tilde{\Pi}^{\pi}$ of
effective perturbations is trivial; and thus,
$\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi})=\Gamma^{\subseteq}({\mathbb{R}})$.

More generally, whenever a function $\theta$ is affine on intervals
$D_{1},D_{2},\dots,D_{k}$ with the same slope, then
$\mathop{\mathrm{moves}}\nolimits((D_{1}\cup\dots\cup
D_{k})\times(D_{1}\cup\dots\cup
D_{k}))\subseteq\Gamma^{\mathrm{resp}}(\theta)$. Thus, we have the following:

######  Lemma 10.6.

Suppose the space $\tilde{\Pi}^{\pi}_{{\mathcal{T}}}$ of finite-dimensional
perturbations is trivial.

  1. (a)

Let $C$ be the set of covered points. Then
$\mathop{\mathrm{moves}}\nolimits(C\times
C)\subseteq\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi})$.

  2. (b)

Let $D_{1},\dots,D_{k}\subseteq C$ be covered intervals on which $\pi$ is
affine with the same slope. Then
$\mathop{\mathrm{moves}}\nolimits((D_{1}\cup\dots\cup
D_{k})\times(D_{1}\cup\dots\cup
D_{k}))\subseteq\Gamma^{\mathrm{resp}}(\pi+\tilde{\Pi}^{\pi})$.

######  Example 10.6.

Figure 20. Function $\pi=\textsf{equiv7{\textunderscore}\allowbreak
example{\textunderscore}\allowbreak post{\textunderscore}\allowbreak 3()}$
from 10.6.

Consider the function $\pi=\textsf{equiv7{\textunderscore}\allowbreak
example{\textunderscore}\allowbreak post{\textunderscore}\allowbreak 3()}$,
shown in Figure 20. It has 4 connected covered components (colored slopes in
the figure) and 2 connected uncovered components
$U_{1}=(\frac{2}{9},\frac{5}{18})\cup(\frac{4}{9},\frac{1}{2})$ and
$U_{2}=(\frac{5}{6},\frac{31}{36})\cup(\frac{31}{36},\frac{8}{9})$. Its
finite-dimensional perturbation space is trivial.

  1. (a)

From 10.6 (a) we see that $\mathop{\mathrm{moves}}\nolimits(C\times
C)\subseteq\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi})$.

  2. (b)

For the smaller semigroup $\Gamma^{\mathrm{resp}}(\pi+\tilde{\Pi}^{\pi})$, we
observe that the function $\pi$ is affine with slope $0$ on the intervals
$D_{1}=(\frac{1}{18},\frac{2}{18})$ and $D_{2}=(\frac{2}{18},\frac{3}{18})$,
which belong to separate connected covered components (_cyan_ and _lavender_).
Because the finite-dimensional perturbation space is trivial, all functions in
$\pi+\tilde{\Pi}^{\pi}$ take the same slope on $D_{1}$ and $D_{2}$, and hence
from 10.6 (b) we have $\mathop{\mathrm{moves}}\nolimits((D_{1}\cup
D_{2})\times(D_{1}\cup
D_{2}))\subseteq\Gamma^{\mathrm{resp}}(\pi+\tilde{\Pi}^{\pi})$. By continuity,
we also have
$\mathop{\mathrm{moves}}\nolimits((\frac{1}{18},\frac{3}{18})\times(\frac{1}{18},\frac{3}{18}))\subseteq\Gamma^{\mathrm{resp}}(\pi+\tilde{\Pi}^{\pi})$.

######  Remark 10.6.

Suppose the finite-dimensional perturbation space has a positive dimension.
Recall its description using slope variables $\tilde{s}_{i}^{c}$ (for the
connected covered components $C_{i}$) and $\tilde{s}_{i}^{u}$ (for the
connected uncovered components $U_{i}$) from 10.3. Whenever for some $i$, $j$,
we have that $\tilde{s}_{i}^{c}=\tilde{s}_{j}^{c}$ holds for all solutions,
then $\mathop{\mathrm{moves}}\nolimits((C_{i}\cup C_{j})\times(C_{i}\cup
C_{j}))\subseteq\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi})$. A similar
statement holds for $\Gamma^{\mathrm{resp}}(\pi+\tilde{\Pi}^{\pi})$.

Consider these move ensembles restricted to the set $U$ of uncovered points in
$(0,1)$. We have the following theorem.

######  Theorem 10.7.

Under Assumptions 10.0, 10.0, and 10.0, we have that

(10.16)
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})|_{U}=\Gamma^{\mathrm{resp}}(\pi+\tilde{\Pi}^{\pi})|_{U}=\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi})|_{U}.$

where $U$ is the set of uncovered points in $(0,1)$.

###### Proof.

We use the notations of the present section. By (10.15), it suffices to show
that if the domain of a move
$\gamma|_{D}\in\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi})$ is contained in $U$,
then $\gamma|_{D}\in\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$.

Recall that we can write an arbitrary connected uncovered component $U_{i}$ in
the form of $U_{i}=\bigcup_{j=1}^{p}\gamma_{j}(I)$, where $I$ is the
fundamental domain for $U_{i}$,
$\gamma_{j}|_{I}\in\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$, and the open
intervals $\gamma_{j}(I)$ are disjoint. As
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ is join-closed and extension-
closed, by taking sub-moves, it suffices to show that if a move $\gamma|_{D}$
satisfies that $D\subseteq I$ and the unrestricted move $\gamma\neq\gamma_{j}$
for all $j=1,\dots,p$, then
$\gamma|_{D}\not\in\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi})$.

Consider a move $\gamma|_{D}$ where $D\subseteq I$ and $\gamma\neq\gamma_{j}$
for all $j=1,\dots,p$. There exists an open interval $D^{\prime}\subseteq D$
such that $\gamma(D^{\prime})\cap\gamma_{j}(D^{\prime})=\emptyset$ for all
$j=1,\dots,p$. We can construct a perturbation $\tilde{\pi}$ such that

  1. (i)

$\tilde{\pi}$ is non-zero and Lipschitz continuous on $D^{\prime}$;

  2. (ii)

$\tilde{\pi}(x)=\tilde{\pi}(x^{-})=\tilde{\pi}(x^{+})=0$ for $x\in\partial
D^{\prime}$;

  3. (iii)

$\tilde{\pi}(x)=\chi(\gamma_{j})\tilde{\pi}(\gamma_{j}(x))$ for $x\in
D^{\prime}$, $j=1,\dots,p$; and

  4. (iv)

$\tilde{\pi}(x)=0$ for $x\not\in\bigcup_{j=1}^{p}\gamma_{j}(D^{\prime})$.

Since $\tilde{\pi}|_{D^{\prime}}\not\equiv 0$ but
$\tilde{\pi}|_{\gamma(D^{\prime})}\equiv 0$, we have that
$\gamma|_{D^{\prime}}\not\in\Gamma^{\mathrm{resp}}(\tilde{\pi})$, and hence
$\gamma|_{D}\not\in\Gamma^{\mathrm{resp}}(\tilde{\pi})$. By Theorem 10.4,
$\tilde{\pi}\in\tilde{\Pi}^{\pi}_{\mathrm{zero}({\mathcal{T}})}\subseteq\tilde{\Pi}^{\pi}$.
Therefore, $\gamma|_{D}\not\in\Gamma^{\mathrm{resp}}(\tilde{\Pi}^{\pi})$. We
conclude that (10.16) holds. ∎

##  11\. Conclusion

###  11.1. Forthcoming computational companion paper

In the forthcoming paper [14], part VIII of the series, we will describe a
method to compute the moves closure $\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$
for a large class of piecewise linear minimal valid functions, including all
functions with rational breakpoints, for which the moves closure has a finite
presentation. The decomposition of the perturbation space in section 10 is
already algorithmic. Thus we will obtain a grid-free extremality test.

###  11.2. Limits of the approach of this paper

We now discuss the limitations to the equivariant perturbation theorydeveloped
in our series of papers.

For two-sided discontinuous functions, the decomposition of the perturbation
spaces breaks down. Theorem 10.4 and Theorem 10.6 do not hold when the
function $\pi$ is discontinuous from both sides of the origin, as the
following example shows.

######  Example 11.0.

Figure 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()}$
(_blue graph at the left and top borders_) from 11.0, where the additive faces
are colored in _green_. (Right) The graph of the move ensemble
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$ of $\pi$, where the set $C\cup
B^{\prime}=[0,1)\setminus U^{\prime}$ of covered points and breakpoints are
marked in _magenta on the left and top borders_.

Consider the minimal valid function $\pi=$ minimal_no_covered_interval() with
$f=\tfrac{1}{2}$, defined by

$\pi(x)=\begin{cases}0&\text{if }x=0\\\ \tfrac{1}{2}&\text{if
}0<x<\tfrac{1}{2}\text{ or }\tfrac{1}{2}<x<1\\\ 1&\text{if
}x=\tfrac{1}{2},\end{cases}$

which is discontinuous from both sides of the origin.

Observe from Figure 21 that $C=\emptyset$,
$B^{\prime}=\\{0,\tfrac{1}{4},\tfrac{1}{2},\tfrac{3}{4},1\\}$ and the
connected uncovered components are
$U_{1}=(0,\tfrac{1}{4})\cup(\tfrac{1}{4},\tfrac{1}{2})$ and
$U_{2}=(\tfrac{1}{2},\tfrac{3}{4})\cup(\tfrac{3}{4},1)$, where the two
intervals in either $U_{1}$ or $U_{2}$ are connected through the move
$\rho_{f}|_{(0,f)}$ or $\rho_{f}|_{(f,1)}$ in
$\mathop{\mathrm{clsemi}_{A}}(\Omega^{0})$. Any bounded
${\mathbb{Z}}$-periodic function $\tilde{\pi}$ satisfying that
$\tilde{\pi}(x)=0$ for $x\in B^{\prime}$ and
$\tilde{\pi}(x)=\tilde{\pi}(\rho_{f}(x))$ for $x\in[0,1)$ is an effective
perturbation of $\pi$. For example, define a ${\mathbb{Z}}$-periodic function
$\tilde{\pi}=$ equiv7_example_2_crazy_perturbation() by

$\tilde{\pi}(x)=\begin{cases}1&\text{if }x\in(0,\frac{1}{4})\text{ such that
}x\in G\text{, or}\\\ &\text{if }x\in(\frac{1}{4},\frac{1}{2})\text{ such that
}x-\frac{1}{4}\in G;\\\ -1&\text{if }x\in(0,\frac{1}{4})\text{ such that
}x-\frac{1}{4}\in G\text{, or}\\\ &\text{if
}x\in(\frac{1}{4},\frac{1}{2})\text{ such that }x-\frac{1}{2}\in G;\\\
0&\text{otherwise},\end{cases}$

where the group $G=\langle 1,\sqrt{2}\rangle_{{\mathbb{Z}}}$ is dense in
${\mathbb{R}}$. Then $\tilde{\pi}$ is an effective perturbation of $\pi$,
since both $\pi\pm\epsilon\tilde{\pi}$ are minimal valid functions for
$0<\epsilon\leq\frac{1}{6}$.333This positive $\epsilon$ is verified by calling
find_epsilon_for_crazy_perturbation($\pi$, $\tilde{\pi}$) Observe that
$\tilde{\pi}$ is a highly discontinuous function, which does not have a limit
at any point in $(0,\frac{1}{2})$. Thus, without 10.0, an equivariant
perturbation is not necessarily Lipschitz continuous; and the limits of an
effective perturbation at the breakpoints might not exist. For this reason,
the decomposition of perturbations does not make sense when the function $\pi$
is discontinuous from both sides of the origin.

Note that in [20], though an algorithm was presented that checks the
effectiveness of a given perturbation function $\tilde{\pi}$, and a
perturbation was constructed for an example function, it was left as an open
question how to construct perturbations in general. This is still open.

We conjecture that the equivariant perturbation theory also breaks down for
the case of non–piecewise linear functions, such as the fractal functions
presented in [1] and [2]. In particular we note that (1) the finite system of
equations describing the space of finite-dimensional perturbations would be
replaced by a system of functional equations, for which we have no lemmas
available; (2) we expect that the decomposition theorem no longer holds.

## Acknowledgments

The authors wish to thank Chun Yu Hong, who worked on a first implementation
of a grid-free procedure as an undergraduate researcher at UC Davis in 2013;
experiments based on his code have helped the authors to develop the full
theory described in the present paper. The authors also wish to thank Quentin
Louveaux and Reuben La Haye for valuable discussions.

## References

  * [1] A. Basu, M. Conforti, G. Cornuéjols, and G. Zambelli, _A counterexample to a conjecture of Gomory and Johnson_ , Mathematical Programming Ser. A 133 (2012), no. 1–2, 25–38, https://doi.org/10.1007/s10107-010-0407-1.
  * [2] A. Basu, M. Conforti, M. Di Summa, and J. Paat, _Extreme functions with an arbitrary number of slopes_ , Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Liège, Belgium, June 1–3, 2016, Proceedings (Q. Louveaux and M. Skutella, eds.), Springer International Publishing, Cham, 2016, pp. 190–201, https://doi.org/10.1007/978-3-319-33461-5_16, ISBN 978-3-319-33461-5.
  * [3] A. Basu, R. Hildebrand, and M. Köppe, _Equivariant perturbation in Gomory and Johnson’s infinite group problem. I. The one-dimensional case_ , Mathematics of Operations Research 40 (2014), no. 1, 105–129, https://doi.org/10.1287/moor.2014.0660.
  * [4] by same author, _Equivariant perturbation in Gomory and Johnson’s infinite group problem. IV. The general unimodular two-dimensional case_ , Manuscript, 2016.
  * [5] by same author, _Light on the infinite group relaxation I: foundations and taxonomy_ , 4OR 14 (2016), no. 1, 1–40, https://doi.org/10.1007/s10288-015-0292-9.
  * [6] by same author, _Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms_ , 4OR 14 (2016), no. 2, 107–131, https://doi.org/10.1007/s10288-015-0293-8.
  * [7] by same author, _Equivariant perturbation in Gomory and Johnson’s infinite group problem—III: Foundations for the $k$-dimensional case with applications to $k=2$_, Mathematical Programming 163 (2017), no. 1, 301–358, https://doi.org/10.1007/s10107-016-1064-9.
  * [8] S. S. Dey, J.-P. P. Richard, Y. Li, and L. A. Miller, _On the extreme inequalities of infinite group problems_ , Mathematical Programming 121 (2010), no. 1, 145–170, https://doi.org/10.1007/s10107-008-0229-6.
  * [9] M. Di Summa, _Piecewise smooth extreme functions are piecewise linear_ , Mathematical Programming (2018), 1–29, https://doi.org/10.1007/s10107-018-1330-0.
  * [10] R. E. Gomory, _Some polyhedra related to combinatorial problems_ , Linear Algebra and its Applications 2 (1969), 451–558, https://doi.org/10.1016/0024-3795(69)90017-2.
  * [11] R. E. Gomory and E. L. Johnson, _Some continuous functions related to corner polyhedra, I_ , Mathematical Programming 3 (1972), 23–85, https://doi.org/10.1007/BF01584976.
  * [12] by same author, _Some continuous functions related to corner polyhedra, II_ , Mathematical Programming 3 (1972), 359–389, https://doi.org/10.1007/BF01585008.
  * [13] R. Hildebrand, _On polyhedral subdivisions closed under group operations_ , Manuscript, 2013.
  * [14] R. Hildebrand, M. Köppe, and Y. Zhou, _Equivariant perturbation in Gomory and Johnson’s infinite group problem. VIII. Grid-free extremality test—general algorithm and implementation_ , manuscript, 2019.
  * [15] by same author, _On perturbation spaces of minimal valid functions: Inverse semigroup theory and equivariant decomposition theorem_ , 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.
  * [16] C. Y. Hong, M. Köppe, and Y. Zhou, _Equivariant perturbation in Gomory and Johnson’s infinite group problem (V). Software for the continuous and discontinuous 1-row case_ , Optimization Methods and Software 33 (2018), no. 3, 475–498, https://doi.org/10.1080/10556788.2017.1366486.
  * [17] M. Köppe and Y. Zhou, _An electronic compendium of extreme functions for the Gomory–Johnson infinite group problem_ , Operations Research Letters 43 (2015), no. 4, 438–444, https://doi.org/10.1016/j.orl.2015.06.004.
  * [18] by same author, _Toward computer-assisted discovery and automated proofs of cutting plane theorems_ , Combinatorial Optimization: 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16–18, 2016, Revised Selected Papers (R. Cerulli, S. Fujishige, and A. R. Mahjoub, eds.), Springer International Publishing, Cham, 2016, pp. 332–344, https://doi.org/10.1007/978-3-319-45587-7_29, ISBN 978-3-319-45587-7.
  * [19] by same author, _On the notions of facets, weak facets, and extreme functions of the Gomory–Johnson infinite group problem_ , Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26–28, 2017, Proceedings (F. Eisenbrand and J. Koenemann, eds.), Springer International Publishing, Cham, 2017, pp. 330–342, https://doi.org/10.1007/978-3-319-59250-3_27, ISBN 978-3-319-59250-3.
  * [20] by same author, _Equivariant perturbation in Gomory and Johnson’s infinite group problem. VI. The curious case of two-sided discontinuous minimal valid functions_ , Discrete Optimization 30 (2018), 51–72, https://doi.org/10.1016/j.disopt.2018.05.003.
  * [21] M. Köppe, Y. Zhou, C. Y. Hong, and J. Wang, _cutgeneratingfunctionology: Python code for computation and experimentation with cut-generating functions_ , https://github.com/mkoeppe/cutgeneratingfunctionology, November 2019, (Version 1.4.1).
  * [22] M. V. Lawson, _Inverse semigroups: The theory of partial symmetries_ , World Scientific, 1998.
  * [23] Y. Zhou, _Infinite-dimensional relaxations of mixed-integer optimization problems_ , Ph.D. thesis, University of California, Davis, Graduate Group in Applied Mathematics, May 2017, available from https://search.proquest.com/docview/1950269648.