Centre Vortex Structure of QCD-Vacuum Fields and Confinement

Derek Leinweber1$\star$, James Biddle1 and Waseem Kamleh1

1 Centre for the Subatomic Structure of Matter, Department of Physics,

University of Adelaide, SA 5005, Australia

*<EMAIL_ADDRESS>
XXXIII International (ONLINE) Workshop on High Energy Physics
“Hard Problems of Hadron Physics: Non-Perturbative QCD & Related Quests”
November 8-12, 2021 10.21468/SciPostPhysProc.?

## Abstract

The non-trivial ground-state vacuum fields of QCD form the foundation of
matter. Using modern visualisation techniques, this presentation examines the
microscopic structure of these fields. Of particular interest are the centre
vortices identified within the ground-state fields of lattice QCD. Our current
focus is on understanding the manner in which dynamical fermions in the QCD
vacuum alter the centre-vortex structure. The impact of dynamical fermions is
significant and provides new insights into the role of centre vortices in
underpinning both confinement and dynamical chiral symmetry breaking in QCD.

###### Contents

  1. 1 Introduction
  2. 2 Centre Vortex Identification
  3. 3 Centre Vortex Visualisation
  4. 4 Static Quark Potential
  5. 5 Conclusion

##  1 Introduction

Lattice QCD calculations have been instrumental in revealing the fundamental
role of centre vortices [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] in the ground-
state vacuum fields in governing the confinement of quarks.

By identifying centre vortices and then removing them from QCD ground-state
fields, a deep understanding of their contributions has been developed.
Removal of centre vortices from the ground-state fields results in a loss of
dynamical mass generation and restoration of chiral symmetry [13, 14], a loss
of the string tension [15, 16] and a suppression of the infrared enhancement
of the Landau-gauge gluon propagator [17, 16, 18].

One can also examine the role of the centre vortices alone. Remarkably centre
vortices produce both a linear static quark potential [15, 19, 20] and
infrared enhancement in the Landau-gauge gluon propagator. The planar vortex
density of centre-vortex degrees of freedom scales with the lattice spacing
providing an well defined continuum limit [15]. These results elucidate strong
connections between centre vortices and confinement.

A connection between centre vortices and instantons was identified through
gauge-field smoothing [20]. An understanding of the phenomena linking these
degrees of freedom was illustrated in Ref. [21]. In addition, centre vortices
have been shown to give rise to mass splitting in the low-lying hadron
spectrum [14, 13, 22].

Still, the picture is not perfect. The vortex-only string tension obtained
from pure Yang-Mills lattice studies has been consistently shown to be about
$\sim 62\%$ of the full string tension. Moreover, upon removal of centre
vortices the gluon propagator shows a remnant of infrared enhancement [18]. In
the pure gauge sector, the removal of long-distance non-perturbative effects
via centre-vortex removal is not perfect.

Here we turn our attention to understanding the impact of dynamical fermions
on the centre-vortex structure of QCD ground-state fields. We will illustrate
the differences in the microscopic structure and reveal how the change in
structure affects the static quark potential and the Landau-gauge gluon
propagator. We find the introduction of dynamical fermions brings the
phenomenology of centre vortices much closer to a perfect encapsulation of the
salient features of QCD.

##  2 Centre Vortex Identification

In identifying centre vortices one commences with a gauge fixing procedure
which brings the lattice link variables as close as possible to the identity
times a phase. Here, the original Monte-Carlo generated configurations are
considered. They are gauge transformed directly to Maximal Centre Gauge [23,
24, 15], without preconditioning [25]. The brings the lattice link variables
$U_{\mu}(x)$ close to the centre elements of $SU(3)$,

$Z=\exp\left(2\pi i\,\frac{m}{3}\right)\,\mathbf{I},\textrm{ with }m=-1,0,1.$
(1)

One considers gauge transformations $\Omega$ such that,

$\sum_{x,\mu}\,\left|\mathrm{tr}\,U_{\mu}^{\Omega}(x)\,\right|^{2}\stackrel{{\scriptstyle\Omega}}{{\to}}\mathrm{max}\,,$
(2)

and then projects the link variables to the centre

$U_{\mu}(x)\to Z_{\mu}(x)\textrm{ where }Z_{\mu}(x)=\exp\left(2\pi
i\,\frac{m_{\mu}(x)}{3}\right)\mathbf{I}\,,$ (3)

and $m_{\mu}(x)=-1,0,1.$

The product of these centre-projected links around an elementary $1\times 1$
square on the lattice reveals the centre charge associated with that
plaquette. The centre-line of an extended vortex in three dimensions is
identified by tracing the presence of nontrivial centre charge, $z$, through
the spatial lattice

$z=\prod_{\Box}Z_{\mu}(x)=\exp\left(2\pi i\,\frac{m}{3}\right)\,.$ (4)

A right-handed ordering of the dimensions is selected in calculating and
illustrating the centre charge. If $z=1$, no vortex pierces the plaquette. If
$z\neq 1$ a vortex with charge $z$ pierces the plaquette. We refer to the
centre charge of a vortex via the value of $m=\pm 1$.

##  3 Centre Vortex Visualisation

The centre lines of extended vortices are illustrated on the dual lattice by
rendering a jet piercing the plaquette producing the nontrivial centre charge.
The orientation of the jet follows the right-handed coordinate system. Figure
1 provides an illustration of this assignment. For example, with reference to
Eq. (4), an $m=+1$ vortex in the $x$-$y$ plane is plotted in the $+\hat{z}$
direction as a blue jet. Similarly, an $m=-1$ vortex in the $x$-$y$ plane is
plotted in the $-\hat{z}$ direction. As the centre charge transforms to its
complex conjugate under permutation of the two dimensions describing the
plaquette, the centre charge can be thought of as the directed flow of charge
$z=\exp(2\pi i/3)$.

$Z_{y}(n+\hat{x})\ $${}\ \
Z_{x}^{*}(n+\hat{y})$$Z_{y}^{*}(n)$$Z_{x}(n)$$x$$y$$z$

$Z_{y}(n+\hat{x})\ $$Z_{x}^{*}(n+\hat{y})$$Z_{y}^{*}(n)$$Z_{x}(n)$$x$$y$$z$

Figure 1: Illustrating nontrivial centre charge via a jet. (left) An $m=+1$
vortex with centre charge $z=\exp(2\pi i/3)$ is rendered as a jet pointing in
the $+\hat{z}$ direction. (right) An $m=-1$ vortex with centre charge
$z=\exp(-2\pi i/3)$ is rendered as a jet in the $-\hat{z}$ direction.

Our current focus is to understand the impact of dynamical-fermion degrees of
freedom on the centre-vortex structure of a gluon field. Here we consider the
PACS-CS $(2+1)$-flavour full-QCD ensembles [26], made available through the
ILDG [27]. These $32^{3}\times 64$ lattice ensembles employ a renormalisation-
group improved Iwasaki gauge action with $\beta=1.90$ and non-perturbatively
${\cal O}(a)$-improved Wilson quarks, with $C_{\rm SW}=1.715$. In this
section, their lightest $u$\- and $d$-quark-mass ensemble identified by a pion
mass of 156 MeV [26] is considered. The scale is set using the Sommer
parameter with $r_{0}=0.4921$ fm providing a lattice spacing of $a=0.0933$ fm
[26].

For comparison, a matched $32^{3}\times 64$ pure-gauge ensemble has been
generated using the same improved Iwasaki gauge action with $\beta=2.58$
providing a Sommer-scale spacing of $a=0.100$ fm. This spacing facilitates
comparisons with all the PACS-CS ensembles.

The centre-vortex structure of pure-gauge and dynamical-fermion ground-state
vacuum fields is illustrated in Figs. 3 and 3 respectively. The vortex flow
displays a rich structure. One observes the continuous flow of centre charge
and the presence of monopole or anti-monopole contributions, where three jets
emerge from or converge to a point. We refer to the latter as branching points
in general. Upon introducing dynamical fermions, the structure becomes more
complicated, both in the abundance of nontrivial centre charge and in the
increased abundance of branching points.

These figures provide interactive illustrations which can be activated in
Adobe Reader111Open this pdf document in Adobe Reader 9 or later. Linux users
can install Adobe acroread version 9.4.1, the last edition to have full 3D
support. From the “Edit” menu, select “Preferences…” and ensure “3D &
Multimedia” is enabled and “Enable double-sided rendering” is selected. by
clicking on the image. Once activated, click and drag to rotate, Ctrl-click to
translate, Shift-click or mouse wheel to zoom, and right click to access the
“Views” menu. Several views have been created to facilitate and inspection of
the centre-vortex structure.

Both Figs. 3 and 3 contain a percolating vortex cluster, a characteristic
feature of the confining phase [28]. These illustrations are representative of
the ensemble in that the vortex vacuum is typically dominated by a single
large percolating cluster. This single large cluster is accompanied by several
smaller loops or loop clusters. However, the most important observation is how
dynamical fermions significantly increase the number of vortices observed.

For an ensemble of 200 configurations with $32$ three-dimensional volume
slices each, the average number of vortices composing the primary cluster in
these $32^{2}\times 64$ spatial slices is $3,277\,\pm 156$ vortices in the
pure gauge theory, versus $5,924\,\pm 239$ vortices in full QCD. Since there
are $32^{2}\times 64\times 3=196,608$ spatial plaquettes on these lattices,
the presence of a vortex is a relatively rare occurrence.

[ noplaybutton, 3Dtoolbar, 3Dmenu, 3Dviews=U3D/Primary-Secondary-PG-28.vws,
3Dcoo = 16 16 32, 3Dc2c=0.245114266872406 0.8673180341720581
0.43321868777275085, 3Droo = 110.0, 3Droll =-98.1, 3Dlights=Default,
width=1.04]U3D/Primary-Secondary-PG-28.u3d

Figure 2:  The centre-vortex structure of a ground-state vacuum field
configuration in pure SU(3) gauge theory. (Click to activate.) The flow of
$+1$ centre charge through a gauge field is illustrated by the jets. Blue jets
are used to illustrate the single percolating vortex structure, while other
colours illustrate smaller structures.

[ noplaybutton, 3Dtoolbar, 3Dmenu, 3Dviews=U3D/Primary-Secondary-DF-18.vws,
3Dcoo = 16 16 32, 3Dc2c=0.245114266872406 0.8673180341720581
0.43321868777275085, 3Droo = 110.0, 3Droll =-98.1, 3Dlights=Default,
width=]U3D/Primary-Secondary-DF-18.u3d

Figure 3:  The centre-vortex structure of a ground-state vacuum field
configuration in dynamical 2+1 flavour QCD. (Click to activate.) The flow of
$+1$ centre charge through a gauge field is illustrated by the jets. Symbols
are as described in Fig. 3.

Similarly, Figs. 5 and 5 illustrate the secondary loop structures left behind
as one removes the single large percolating structure. Again, the introduction
of dynamical fermions increases the complexity of the structure through a
proliferation of branching points (or monopoles [29]). Figure 5 contains many
views in the drop-down menu to facilitate the observation of this complexity.

[ noplaybutton, 3Dtoolbar, 3Dmenu, 3Dviews=U3D/Secondary-PG-28.vws, 3Dcoo = 16
16 32, 3Dc2c=0.245114266872406 0.8673180341720581 0.43321868777275085, 3Droo =
110.0, 3Droll =-98.1, 3Dlights=Default, width=1.04]U3D/Secondary-PG-28.u3d

Figure 4:  The centre-vortex structure of secondary loops in a ground-state
vacuum field configuration of pure SU(3) gauge theory. (Click to activate.)
The flow of $+1$ centre charge in the secondary loops – left behind as the
single percolating structure is removed – is illustrated.

[ noplaybutton, 3Dtoolbar, 3Dmenu, 3Dviews=U3D/Secondary-DF-18.vws, 3Dcoo = 16
16 32, 3Dc2c=0.245114266872406 0.8673180341720581 0.43321868777275085, 3Droo =
110.0, 3Droll =-98.1, 3Dlights=Default, width=1.05]U3D/Secondary-DF-18.u3d

Figure 5:  The centre-vortex structure of secondary loops in a ground-state
vacuum field configuration of dynamical 2+1 flavour QCD. (Click to activate.)
The flow of $+1$ centre charge in the secondary loops is illustrated.

##  4 Static Quark Potential

With an understanding the impact of dynamical-fermion degrees of freedom on
the centre-vortex structure of ground-state vacuum fields, we turn our
attention to confinement as realised in the static quark potential. The
results presented here are supported by complimentary studies of the
nonperturbative gluon propagator.

The static quark potential is accessed via consideration of the expectation
value of Wilson loops, $\left\langle W(r,t)\right\rangle$, with spatial
separation $r$ and temporal extent $t$,

$\langle
W(r,\,t)\rangle=\sum_{\alpha}\lambda^{\alpha}\\!(r)\,\exp\left(-V^{\alpha}\\!(r)\,t\right)\,.$
(5)

The relevant static quark potential is given by the lowest $\alpha=0$ state.
We use a variational analysis of several spatially-smeared sources to isolate
this state.

With knowledge of the vortex content of a configuration, contained in
$Z_{\mu}(x)$ of Eq. (3), we can analyse two vortex-modified ensembles in
addition to the original untouched configuration, $U_{\mu}(x)$. We refer to
these as the vortex-only, $Z_{\mu}(x)$, and vortex-removed,
$Z_{\mu}^{\dagger}(x)\,U_{\mu}(x)$, ensembles.

The static quark potential for the original untouched configurations is
expected to follow a Cornell potential

$V(r)=V_{0}-\frac{\alpha}{r}+\sigma\,r\,,$ (6)

composed of a Coulomb term, dominant at short distances, and a linear term,
dominant at large distances. As centre vortices are anticipated to encapsulate
the non-perturbative long-range physics, the vortex-only results should give
rise to a linear potential [12, 5, 30]. On the other hand, the vortex-removed
results are expected to capture the short-range behaviour. To analyse the
linearity of the potential at large distances we plot a sliding local linear
fit to the potential with extent $r\pm\frac{3}{2}a$.

Figure 6:  The static quark potential as calculated on the original untouched
and vortex-modified pure-gauge ensembles. The lower plot shows the local slope
of the potentials at position $r$ obtained from a linear fit with extent
$r\pm\frac{3}{2}a$.  Figure 7:  The static quark potential as calculated on
the vortex-modified dynamical-fermion ensembles, corresponding to a pion mass
of $701$ MeV. Details are as in Fig. 6.

We commence with preliminary results for the pure-gauge ensemble illustrated
in Fig. 6. Qualitatively, centre vortices account for the long-distance
physics. The lower plot illustrates how removal of centre vortices completely
removes the long-range potential. However, the phenomenology is not perfect.
The value of the string tension produced in the vortex-only analysis is once
again only $~{}60$ % of the original string tension.

Upon introducing dynamical fermions with light quark masses corresponding to a
pion mass of $m_{\pi}=701$ MeV, the preliminary results shown in Fig. 7 are
observed. Comparing with the pure-gauge sector of Fig. 6, we observe a
screening of the original string tension with the introduction of dynamical
fermions, in accord with expectations. Again, the effect of vortex removal is
to remove confinement. The sliding average lies in excellent agreement with 0
at large distances.

While the centre-vortex phenomenology is similar to the pure gauge sector,
this time the vortex-only string tension is in excellent agreement with the
original untouched ensemble. This is illustrated in Fig. 7, in the lower plot
where the local slopes of the untouched and vortex-only ensembles agree at
large distances. This new agreement arises from significant modifications in
the centre-vortex structure of ground state fields induced by dynamical
fermions, even at relatively large quark masses.

##  5 Conclusion

In summary, centre-vortex structure is complex. Each ground-state
configuration is dominated by a long-distance percolating centre-vortex
structure. In $SU(3)$ gauge field theory, a proliferation of branching points
is observed, with further enhancement as light dynamical fermion degrees of
freedom are introduced in simulating QCD. There is an approximate doubling in
the number of nontrivial centre charges in the percolating vortex structure as
one goes from the pure-gauge theory to full QCD. An enhancement in the number
of small vortex paths is also observed upon introducing dynamical fermions.
Increased complexity in the vortex paths is also observed as the number of
monopole-antimonopole pairs is significantly increased with the introduction
of dynamical fermions. In short, dynamical-fermion degrees of freedom
radically alter the centre-vortex structure of the ground-state vacuum fields.

With regard to the static quark potential and confinement, we find that centre
vortices now quantitatively capture the string tension in full QCD, unlike the
pure-gauge sector. This represents a significant advance in centre-vortex
phenomenology. Moreover, vortex removal continues to eliminate the long
distance potential. These encouraging results are also reflected in more
recent studies of the gluon propagator in full QCD. In summary, the results
presented here show a significant advance in the ability of centre vortices to
capture the salient nonperturbative features of QCD.

## Acknowledgements

We thank the PACS-CS Collaboration for making their 2 +1 flavour
configurations available via the International Lattice Data Grid (ILDG).

### Funding information

This research was undertaken with the assistance of resources from the
National Computational Infrastructure (NCI), provided through the National
Computational Merit Allocation Scheme and supported by the Australian
Government through Grant No. LE190100021 via the University of Adelaide
Partner Share. This research is supported by Australian Research Council
through Grants No. DP190102215 and DP210103706. WK is supported by the Pawsey
Supercomputing Centre through the Pawsey Centre for Extreme Scale Readiness
(PaCER) program.

## References

  * [1] G. ’t Hooft,  _On the Phase Transition Towards Permanent Quark Confinement_ ,  Nucl. Phys. B 138, 1 (1978),  10.1016/0550-3213(78)90153-0.
  * [2] G. ’t Hooft,  _A Property of Electric and Magnetic Flux in Nonabelian Gauge Theories_ ,  Nucl. Phys. B 153, 141 (1979),  10.1016/0550-3213(79)90595-9.
  * [3] L. Del Debbio, M. Faber, J. Greensite and S. Olejnik,  _Center dominance and Z(2) vortices in SU(2) lattice gauge theory_ ,  Phys. Rev. D 55, 2298 (1997),  10.1103/PhysRevD.55.2298,  hep-lat/9610005.
  * [4] M. Faber, J. Greensite and S. Olejnik,  _Casimir scaling from center vortices: Towards an understanding of the adjoint string tension_ ,  Phys. Rev. D 57, 2603 (1998),  10.1103/PhysRevD.57.2603,  hep-lat/9710039.
  * [5] L. Del Debbio, M. Faber, J. Giedt, J. Greensite and S. Olejnik,  _Detection of center vortices in the lattice Yang-Mills vacuum_ ,  Phys. Rev. D 58, 094501 (1998),  10.1103/PhysRevD.58.094501,  hep-lat/9801027.
  * [6] R. Bertle, M. Faber, J. Greensite and S. Olejnik,  _The Structure of projected center vortices in lattice gauge theory_ ,  JHEP 03, 019 (1999),  10.1088/1126-6708/1999/03/019,  hep-lat/9903023.
  * [7] M. Faber, J. Greensite, S. Olejnik and D. Yamada,  _The Vortex finding property of maximal center (and other) gauges_ ,  JHEP 12, 012 (1999),  10.1088/1126-6708/1999/12/012,  hep-lat/9910033.
  * [8] M. Engelhardt and H. Reinhardt,  _Center projection vortices in continuum Yang-Mills theory_ ,  Nucl. Phys. B 567, 249 (2000),  10.1016/S0550-3213(99)00727-0,  hep-th/9907139.
  * [9] R. Bertle, M. Faber, J. Greensite and S. Olejnik,  _P vortices, gauge copies, and lattice size_ ,  JHEP 10, 007 (2000),  10.1088/1126-6708/2000/10/007,  hep-lat/0007043.
  * [10] J. Greensite,  _The Confinement problem in lattice gauge theory_ ,  Prog. Part. Nucl. Phys. 51, 1 (2003),  10.1016/S0146-6410(03)90012-3,  hep-lat/0301023.
  * [11] M. Engelhardt, M. Quandt and H. Reinhardt,  _Center vortex model for the infrared sector of SU(3) Yang-Mills theory: Confinement and deconfinement_ ,  Nucl. Phys. B 685, 227 (2004),  10.1016/j.nuclphysb.2004.02.036,  hep-lat/0311029.
  * [12] J. Greensite,  _Confinement from Center Vortices: A review of old and new results_ ,  EPJ Web Conf. 137, 01009 (2017),  10.1051/epjconf/201713701009,  1610.06221.
  * [13] D. Trewartha, W. Kamleh and D. Leinweber,  _Evidence that centre vortices underpin dynamical chiral symmetry breaking in SU(3) gauge theory_ ,  Phys. Lett. B747, 373 (2015),  10.1016/j.physletb.2015.06.025,  1502.06753.
  * [14] D. Trewartha, W. Kamleh and D. Leinweber,  _Centre vortex removal restores chiral symmetry_ ,  J. Phys. G44(12), 125002 (2017),  10.1088/1361-6471/aa9443,  1708.06789.
  * [15] K. Langfeld,  _Vortex structures in pure SU(3) lattice gauge theory_ ,  Phys. Rev. D69, 014503 (2004),  10.1103/PhysRevD.69.014503,  hep-lat/0307030.
  * [16] P. O. Bowman, K. Langfeld, D. B. Leinweber, A. Sternbeck, L. von Smekal and A. G. Williams,  _Role of center vortices in chiral symmetry breaking in SU(3) gauge theory_ ,  Phys. Rev. D 84, 034501 (2011),  10.1103/PhysRevD.84.034501,  1010.4624.
  * [17] K. Langfeld, H. Reinhardt and J. Gattnar,  _Gluon propagators and quark confinement_ ,  Nucl. Phys. B 621, 131 (2002),  10.1016/S0550-3213(01)00574-0,  hep-ph/0107141.
  * [18] J. C. Biddle, W. Kamleh and D. B. Leinweber,  _Gluon propagator on a center-vortex background_ ,  Phys. Rev. D98(9), 094504 (2018),  10.1103/PhysRevD.98.094504,  1806.04305.
  * [19] A. O’Cais, W. Kamleh, K. Langfeld, B. Lasscock, D. Leinweber, P. Moran, A. Sternbeck and L. von Smekal,  _Preconditioning Maximal Center Gauge with Stout Link Smearing in SU(3)_ ,  Phys. Rev. D 82, 114512 (2010),  10.1103/PhysRevD.82.114512,  0807.0264.
  * [20] D. Trewartha, W. Kamleh and D. Leinweber,  _Connection between center vortices and instantons through gauge-field smoothing_ ,  Phys. Rev. D92(7), 074507 (2015),  10.1103/PhysRevD.92.074507,  1509.05518.
  * [21] J. C. Biddle, W. Kamleh and D. B. Leinweber,  _Visualization of center vortex structure_ ,  Phys. Rev. D 102(3), 034504 (2020),  10.1103/PhysRevD.102.034504,  1912.09531.
  * [22] E.-A. O’Malley, W. Kamleh, D. Leinweber and P. Moran,  _SU(3) centre vortices underpin confinement and dynamical chiral symmetry breaking_ ,  Phys. Rev. D 86, 054503 (2012),  10.1103/PhysRevD.86.054503,  1112.2490.
  * [23] L. Del Debbio, M. Faber, J. Greensite and S. Olejnik,  _Center dominance and Z(2) vortices in SU(2) lattice gauge theory_ ,  Phys. Rev. D55, 2298 (1997),  hep-lat/9610005.
  * [24] K. Langfeld, H. Reinhardt and O. Tennert,  _Confinement and scaling of the vortex vacuum of SU(2) lattice gauge theory_ ,  Phys. Lett. B419, 317 (1998),  10.1016/S0370-2693(97)01435-4,  hep-lat/9710068.
  * [25] A. O’Cais, W. Kamleh, K. Langfeld, B. Lasscock, D. Leinweber _et al._ ,  _Preconditioning Maximal Center Gauge with Stout Link Smearing in SU(3)_ ,  Phys.Rev. D82, 114512 (2010),  10.1103/PhysRevD.82.114512,  0807.0264.
  * [26] S. Aoki _et al._ ,  _2+1 Flavor Lattice QCD toward the Physical Point_ ,  Phys. Rev. D 79, 034503 (2009),  10.1103/PhysRevD.79.034503,  0807.1661.
  * [27] M. G. Beckett, B. Joo, C. M. Maynard, D. Pleiter, O. Tatebe and T. Yoshie,  _Building the International Lattice Data Grid_ ,  Comput. Phys. Commun. 182, 1208 (2011),  10.1016/j.cpc.2011.01.027,  0910.1692.
  * [28] M. Engelhardt, K. Langfeld, H. Reinhardt and O. Tennert,  _Deconfinement in SU(2) Yang-Mills theory as a center vortex percolation transition_ ,  Phys. Rev. D 61, 054504 (2000),  10.1103/PhysRevD.61.054504,  hep-lat/9904004.
  * [29] F. Spengler, M. Quandt and H. Reinhardt,  _Branching of Center Vortices in SU(3) Lattice Gauge Theory_ ,  Phys. Rev. D98(9), 094508 (2018),  10.1103/PhysRevD.98.094508,  1810.04072.
  * [30] H. G. Dosch and Y. A. Simonov,  _The Area Law of the Wilson Loop and Vacuum Field Correlators_ ,  Phys. Lett. B205, 339 (1988),  10.1016/0370-2693(88)91675-9.


# Sim2Real Docs: Domain Randomization for Documents in Natural Scenes using
Ray-traced Rendering

Nikhil Maddikunta, Huijun Zhao, Sumit Keswani, Alfy Samuel,
Fu-Ming Guo, Nishan Srishankar, Vishwa Pardeshi, Austin Huang
Fidelity Investments, Artificial Intelligence Center of Excellence
Correspondence<EMAIL_ADDRESS>
###### Abstract

In the past, computer vision systems for digitized documents could rely on
systematically captured, high-quality scans. Today, transactions involving
digital documents are more likely to start as mobile phone photo uploads taken
by non-professionals. As such, computer vision for document automation must
now account for documents captured in natural scene contexts. An additional
challenge is that task objectives for document processing can be highly use-
case specific, which makes publicly-available datasets limited in their
utility, while manual data labeling is also costly and poorly translates
between use cases.

To address these issues we created Sim2Real Docs
111https://github.com/fidelity/sim2real-docs \- a framework for synthesizing
datasets and performing domain randomization of documents in natural scenes.
Sim2Real Docs enables programmatic 3D rendering of documents using Blender, an
open source tool for 3D modeling and ray-traced rendering. By using rendering
that simulates physical interactions of light, geometry, camera, and
background, we synthesize datasets of documents in a natural scene context.
Each render is paired with use-case specific ground truth data specifying
latent characteristics of interest, producing unlimited fit-for-task training
data. The role of machine learning models is then to solve the inverse problem
posed by the rendering pipeline. Such models can be further iterated upon with
real-world data by either fine tuning or making adjustments to domain
randomization parameters.

_Keywords_ computer vision $\cdot$ synthetic data $\cdot$ data centric ai
$\cdot$ document processing $\cdot$ text detection $\cdot$ text recognition
$\cdot$ data augmentation $\cdot$ natural scenes

##  1 Introduction

While computer vision models for extracting text from images have existed for
decades (LeCun et al. (1989); Tang et al. (1994, 1996); Sinha and Bansal
(1995)), the development of new, robust neural networks for text layout,
detection and recognition is still an active area of research (Xu et al.
(2020); Li et al. (2021)), particularly in the context of text in natural
scenes (Bartz et al. (2018)).

At the same time, transactions requiring document processing in commercial
applications have mostly transitioned to taking place online. Whereas
previously, computer vision for document processing could rely on systematic
scans, today documents are more likely to be photographed by customers
themselves on a mobile phone camera under natural scene conditions.

In light of this, computer vision objectives for document processing that were
once considered solved (Bartz et al. (2018)) need to be re-examined. Classical
document processing systems remain fragile - working under narrow acquisition
conditions and often producing noisy data (Chiron et al. (2017); Mokhtar et
al. (2018)). Documents in natural scene photographs violate the fragile
operating parameters of these traditional document processing pipelines.

Recent advances in neural networks for text recognition in natural scenes
(Mishra et al. (2019); Hu et al. (2020); Lyu et al. (2018)) as well as layout
analysis and recognition using transformer architectures (Xu et al. (2020); Li
et al. (2021)) suggest a promising direction which robustly unifies text and
vision in natural scenes.

However, a major impediment to taking full advantage of neural networks in
this context is the availability of training data. An additional challenge is
that document processing use cases can have highly specialized task
objectives, rendering shared public datasets of limited use for creating
neural networks with a specific end-to-end task objective. Recent tools for
synthetic document data such as Gupte et al. (2021) are limited to applying
compositions of basic image augmentations - blur, bleed-through, morphological
operations - which are insufficient to represent the physical interactions
(e.g. light and shadow, geometry, camera) underlying image variation in a
natural scene contexts.

We bridge this data gap by creating Sim2Real Docs
(https://github.com/fidelity/sim2real-docs) - a Python framework which
integrates with the open source Blender project. Blender is a 3D tool for
modeling and rendering that is often used in movies, animations, and game
development (Community (2021)).

##  2 Synthesis Pipeline: Target Specification, Content and Scene
Randomization, Rendering

Building datasets and models using Sim2Real Docs takes an "inverse problem"
view (De Vito et al. (2005)) of document processing. The objective of the
inverse problem is to infer a latent state corresponding to a computable
representation (classification, segmentation, orientation, detection,
recognition, content extraction etc.) from raw images of documents in natural
scenes.

Figure 1: Render (left), depth map (middle), and in-camera document locations
for fields of interest (right).

Simulation via rendering implements the "forward" computation of the inverse
problem - synthesis starts from the latent state value to produce a rendered
image, with domain randomized scene parameters to generate variation
reflecting class invariants (for example, document classification should be
invariant to lighting or camera angles). The role of the neural network is to
learn a program which solves the end-to-end inverse problem posed by the
simulated scene and rendering process.

By using a data synthesis approach with a photorealistic ray-traced rendering
engine embedded in the domain randomization process, the ground truth is
always available as part of the generated scene specification. Furthermore,
the physics embedded in the rendering engine enables a layer of learned
invariants that would be difficult to specify directly using standard data
augmentation techniques.

With this in mind, specifying a model task with Sim2Real Docs consists of the
following steps:

  1. 1.

Define and randomly sample base document images (e.g. clean pdfs) for the
model supervision task. Some examples of task objectives are described in the
following section ("Example Use Cases").

  2. 2.

Content randomization (optional). To ensure vision models learn to be content-
invariant, documents can be randomly populated with fake content (e.g.
Faraglia and Other Contributors (2021)), either using typed text or
handwritten content from a Generative Adversarial Network (GAN) such as Kang
et al. (2020).

  3. 3.

Style noise (optional). When it’s necessary to capture texture quality of
documents such as faxes, photocopies, scanning, etc., style transfer can be
randomly applied to a subset of documents Gatys et al. (2015). Alternatively
classical noise models such as Gaussian noise and morphological operations as
in (Gupte et al. (2021)) can also be applied.

  4. 4.

Scene randomization. Domain randomization is performed with respect to the
scene contents, which include a document image with optional modifications
from steps (2) and (3) applied as a texture to a 3D document object. Domain
randomization of the scene teaches invariants to the model such as camera
position and orientation relative to documents, camera lens properties such as
focus and depth of field, scene background (e.g. table surface, other pages,
incidental objects), document geometry (folds, bends, creases in the paper),
lighting (sources, intensity, shadows), occlusions and cropping.

  5. 5.

Rendering engine invocation. For each generated scene, Sim2Real Docs invokes
the path-traced rendering process of the Cycles engine to produce a final
image (2).

Figure 2: Sample images from a synthesized classification dataset.

##  3 Example Use Cases

Here we describe several example use cases and illustrate some approaches to
address them.

Camera Rotation. A common issue with document images is for the orientation to
be flipped, sideways, or rotated at an angle. The Nvidia OCRRot library
(Nvidia (2018)) implements a neural network to rotate pages to their correct
orientation, but only for multiples of 90 degrees.

Using Sim2RealDocs, ground truth data is produced by randomizing camera
rotation, while domain randomization is applied to other parameters such as
camera translation, lighting, shadows, and other variables. In contrast to
using rotation data augmentation (such as in torchvision), boundary artifacts
are absent because an actual simulated camera is undergoing rotation. For
estimating a rotation angles, boundary artifacts would constitute a form of
data leakage. Using the synthesized data, any standard vision backbone (He et
al. (2016)) can be used to fine tune output with a periodic loss:

$\mathcal{L}=[sin(\hat{\theta})-sin(\theta)]^{2}+[cos(\hat{\theta})-cos(\theta)]^{2}$
(1)

$\theta$ is the ground truth camera rotation and the model outputs the
$sin(\hat{\theta})$ and $cos(\hat{\theta})$ predictions.

Document Classification. Documents often need to be sorted into one of a set
of known document types, with allowances for an "unknown/other" category. This
determination must be invariant to variations in content, orientation,
lighting, placement, and background (Figure 2). This can be approached as a
standard classification problem with some caveats. If document classes are
similar in appearance, the image classifier may need to incorporate
information that captures fine detail. If documents consist of more than one
page, each document-page pair is its own class. One advantage of performing
document classification upstream of OCR is that inference latency can be
realtime and classification is not subject to OCR errors.

Logo Detection. It’s common to identify brands in documents by detecting their
logos/imagery. For base images, one can either obtain documents with example
logos or insert logos as a form of content augmentation (step 2 of "Synthesis
Pipeline"). Ground truth data is produced by localizing the logo position in
the document and performing a projective transformation to obtain ground truth
bounding box in the camera space projection (Figure 1, right, illustrates the
use of projective transformations to convert content bounding boxes to in-
camera coordinates). Rendered images are then used to train a standard
detection model.

OCR Readability. Image quality issues such as camera focus, grain/noise, low
lighting conditions, fonts, poor camera angles, can cause downstream OCR
systems to fail. Being able to diagnose potential issues in realtime prior to
batch OCR processes allows alerting users that an image may need to be re-
taken. We can use self-supervision to derive such models by defining a loss
that compares the difference between OCR of the base document against OCR of
the rendered image for a distribution of documents.

Segmentation. It’s common to use simple heuristics such as thresholding for
segmenting documents in the foreground from their background. However, such
heuristics can fail if there are textures in the background or other pages
beneath the foreground document. By generating a ground truth per-pixel
segmentation, segmentation models can be taught to be invariant to background
contexts that would otherwise cause heuristic methods to fail.

View Synthesis / Document Coordinate Transforms. There is a frequent need to
transform from the camera coordinate space to the document coordinate space in
order to contextualize and extract content. For example, content of interest
(such as an account ID or signature) may occur at a known fixed location on
the page. This transformation of a document image from the camera coordinate
system to a document-space projection is a simplified instance of view
synthesis. For this, the camera position and orientation relative to the
document within the 3D scene provides a ground truth projective transformation
(Figure 1 middle) that can be used for model training. A more challenging
variant of this task is to apply distortions such as folds, creases, and bends
to the document geometry as part of the domain randomization.

Detection and Recognition. Text detection and recognition models can be
trained using rendered images since the base image text and any augmented
document content are known and provide ground truth data. Projective
transformations can be used to transform text locations within a document to
camera-space bounding boxes (Figure 1 right).

Figure 3: Specification file excerpt defining parameter ranges for domain
randomization.

##  4 Usage

From the user specification for a dataset (Figure 3) , Sim2Real Docs
randomizes a 3D scene for each image in the input location, creating random
scene variations according to ranges (for continuous parameters) and user-
weighted distributions (for categorical parameters). Running the Sim2Real Docs
process creates a scene per base image, renders it, and produces accompanying
metadata reflecting the scene conditions. Sim2Real Docs can also return a
tuple of Blender object models for each render describing the camera,
lighting, and scene for further scripting or customization.

##  5 Conclusion

Sim2Real Docs enables synthetic data and domain randomization for documents in
natural scenes using ray-traced rendering. Synthetic data provides a direct
approach to data-centric model development - a task is defined by creating
data where the model target variable is a parameter of the simulation’s
specification. With photorealism becoming increasingly accessible using tools
such as Blender (Community (2021)), Unreal Engine (Epic Games (2021)), as well
as machine learning methods such as GANs (Richter et al. (2021)), we expect
simulation approaches for data-centric AI to become increasingly common.

In the past, text in natural scenes was considered a distinct domain from text
in documents. Beyond the immediate applications of Sim2Real Docs, our broader
goal is to eliminate this distinction and unify content extraction and
comprehension for documents and natural scenes with multimodal models that are
more general and robust.

##  6 Acknowledgements

The authors would like to thank Qian Yang for comments and edits to this
manuscript.

## References

  * LeCun et al. [1989] Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel.  Backpropagation applied to handwritten zip code recognition.  _Neural computation_ , 1(4):541–551, 1989.
  * Tang et al. [1994] Yuan Yan Tang, Chang De Yan, and Ching Y. Suen.  Document processing for automatic knowledge acquisition.  _IEEE transactions on Knowledge and Data Engineering_ , 6(1):3–21, 1994.
  * Tang et al. [1996] Yuan Y Tang, Seong-Whan Lee, and Ching Y Suen.  Automatic document processing: a survey.  _Pattern recognition_ , 29(12):1931–1952, 1996\.
  * Sinha and Bansal [1995] RMK Sinha and Veena Bansal.  On devanagari document processing.  In _1995 IEEE International Conference on Systems, Man and Cybernetics. Intelligent Systems for the 21st Century_ , volume 2, pages 1621–1626. IEEE, 1995.
  * Xu et al. [2020] Yiheng Xu, Minghao Li, Lei Cui, Shaohan Huang, Furu Wei, and Ming Zhou.  Layoutlm: Pre-training of text and layout for document image understanding.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 1192–1200, 2020.
  * Li et al. [2021] Minghao Li, Tengchao Lv, Lei Cui, Yijuan Lu, Dinei Florencio, Cha Zhang, Zhoujun Li, and Furu Wei.  Trocr: Transformer-based optical character recognition with pre-trained models.  _arXiv preprint arXiv:2109.10282_ , 2021.
  * Bartz et al. [2018] Christian Bartz, Haojin Yang, and Christoph Meinel.  See: towards semi-supervised end-to-end scene text recognition.  In _Thirty-second aaai conference on artificial intelligence_ , 2018\.
  * Chiron et al. [2017] Guillaume Chiron, Antoine Doucet, Mickaël Coustaty, Muriel Visani, and Jean-Philippe Moreux.  Impact of ocr errors on the use of digital libraries: towards a better access to information.  In _2017 ACM/IEEE Joint Conference on Digital Libraries (JCDL)_ , pages 1–4. IEEE, 2017.
  * Mokhtar et al. [2018] Kareem Mokhtar, Syed Saqib Bukhari, and Andreas Dengel.  Ocr error correction: State-of-the-art vs an nmt-based approach.  In _2018 13th IAPR International Workshop on Document Analysis Systems (DAS)_ , pages 429–434. IEEE, 2018.
  * Mishra et al. [2019] Anand Mishra, Shashank Shekhar, Ajeet Kumar Singh, and Anirban Chakraborty.  Ocr-vqa: Visual question answering by reading text in images.  In _ICDAR_ , 2019.
  * Hu et al. [2020] Ronghang Hu, Amanpreet Singh, Trevor Darrell, and Marcus Rohrbach.  Iterative answer prediction with pointer-augmented multimodal transformers for textvqa.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 9992–10002, 2020.
  * Lyu et al. [2018] Pengyuan Lyu, Minghui Liao, Cong Yao, Wenhao Wu, and Xiang Bai.  Mask textspotter: An end-to-end trainable neural network for spotting text with arbitrary shapes.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 67–83, 2018.
  * Gupte et al. [2021] Amit Gupte, Alexey Romanov, Sahitya Mantravadi, Dalitso Banda, Jianjie Liu, Raza Khan, Lakshmanan Ramu Meenal, Benjamin Han, and Soundar Srinivasan.  Lights, camera, action! A framework to improve NLP accuracy over OCR documents.  _CoRR_ , abs/2108.02899, 2021.  URL https://arxiv.org/abs/2108.02899.
  * Community [2021] Blender Online Community.  _Blender - a 3D modelling and rendering package_.  Blender Foundation, Stichting Blender Foundation, Amsterdam, 2021.  URL http://www.blender.org.
  * De Vito et al. [2005] Ernesto De Vito, Lorenzo Rosasco, Andrea Caponnetto, Umberto De Giovannini, Francesca Odone, and Peter Bartlett.  Learning from examples as an inverse problem.  _Journal of Machine Learning Research_ , 6(5), 2005.
  * Faraglia and Other Contributors [2021] Daniele Faraglia and Other Contributors.  Faker, 2021.  URL https://github.com/joke2k/faker.
  * Kang et al. [2020] Lei Kang, Pau Riba, Yaxing Wang, Marçal Rusiñol, Alicia Fornés, and Mauricio Villegas.  Ganwriting: Content-conditioned generation of styled handwritten word images.  In _European Conference on Computer Vision_ , pages 273–289. Springer, 2020.
  * Gatys et al. [2015] Leon A Gatys, Alexander S Ecker, and Matthias Bethge.  A neural algorithm of artistic style.  _arXiv preprint arXiv:1508.06576_ , 2015.
  * Nvidia [2018] Nvidia.  ocrrot, 2018.  URL https://github.com/NVlabs/ocropus3-ocrorot.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Epic Games [2021] Epic Games.  Unreal engine, 2021.  URL https://www.unrealengine.com.
  * Richter et al. [2021] Stephan R Richter, Hassan Abu AlHaija, and Vladlen Koltun.  Enhancing photorealism enhancement.  _arXiv preprint arXiv:2105.04619_ , 2021.


then reaches $r^j$. The largest priority on this path is $\pp(6,i,1,j,0)$ on the
vertex $h^j_i$. Hence we have $\maxdiff^{\sigma}(r^j, o^j_i) \le \pp(6, i, 1, j,
0)$, and since this priority is even, we have that $\val^{\sigma}(r^j)
\sqsubset \val^{\sigma}(o^j_i)$. Hence, we have shown both of the required
properties for this case.

Now that we have shown the two versions of the inductive hypothesis, we have
completed the proof.

§ OR GATES

The following pair of lemmas show that the states $o^j_i$ in the gate
gadgets correctly switch to the outgoing edge specified by
$\chi^{B,\C,j}_{m+1}$. The first lemma considers the case where $1 \le m <
\delay(j, \C) - 1$, and the second lemma considers the case where $m = \delay(j,
\C) - 1$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $1 \le m <
\delay(j, \C) - 1$. For each -gate $i$, greedy all-switches strategy
improvement will switch $o^j_i$ to $\chi^{B,\C,j}_{m+1}(o^j_i)$.

In this proof we will show the that the most appealing edge is the one that is
specified in Equation (<ref>). This boils down to a case analysis.

First suppose that $m < d(i)+2$. We must prove that the edge to $r^j$ is the
most appealing edge at $o^j_i$. By Lemma <ref>, we have that
$\val^{\sigma}(s^j) \sqsubset \val^{\sigma}(r^j)$. Furthermore, since
$d(\inp_1(i)) = d(\inp_2(i)) = d(i) - 1$, part <ref> of Lemma <ref> implies
that $\val^{\sigma}(\inputstate(i,j,l)) \sqsubset \val^{\sigma}(r^j)$ for
$l \in \{1, 2\}$. Hence, we have that $r^j$ is the most appealing edge at
$o^j_i$, as required.

Now suppose that $d(i) + 2 \le  m \le \delay(j, \C) -1$. There are three cases to

* If both input gates are false, then Lemma <ref> and
part <ref>  of
Lemma <ref> imply that $r^j$ will continue to be the most appealing
edge at $o^j_i$, as required.

* If $\inp_l(i)$ is true and $\inp_{1-l}(i)$ is false, for some $l \in \{1,
2\}$, then part <ref>  of Lemma <ref> implies that
$\val^{\sigma}(r^j) \sqsubset \val^{\sigma}(\inputstate(i,j,l))$, and
$\val^{\sigma}(\inputstate(i,j,1-l)) \sqsubset \val^{\sigma}(r^j)$.
Therefore, the most appealing edge at $o^j_i$ is the one to
$\inputstate(i,j,l)$, as required.

* Finally,  if both input gates are true, then Lemma <ref> implies
that the highest appeal edge at $o^j_i$ is either $\inputstate(i,j,1)$ or
$\inputstate(i,j,2)$. Since $\ornext(i)$ is defined to be the successor
with highest appeal, we have that the highest appeal edge at $o^j_i$ is the one
to $o^j_{I_{\ornext(i)}(i)}$, as required.

This completes the proof that greedy all-switches strategy improvement will
switch $o^j_i$ to $\chi^{B,\C,j}_{m+1}(o^j_i)$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and for $m = \delay(j, \C)-1$. For
each -gate $i$, greedy all-switches strategy improvement will switch
to $\chi^{B,\C,j}_{m+1}(o^{1-j}_i)$.

We must show that the edge to $s^{1-j}$ is the most appealing edge at
$o^{1-j}_i$. It can be verified that all paths starting at
$\inputstate(i,j,1)$ and $\inputstate(i,j,2)$ either reach
$r^{1-j}$, $s^{1-j}$, or $r^j$. Furthermore, the largest possible priority on
these paths is strictly smaller than $\pp(7, 0, 0, 0, 0)$. Hence, we can apply
part <ref> of Lemma <ref> and part <ref> of
Lemma <ref> to conclude that the edge to $s^{1-j}$ is the most
appealing outgoing edge at $o^{1-j}_i$.

§ THE STATES $T^J_{I,L}$ IN GATES

In this section we show that the states $t^j_{i,l}$ in the gate gadgets
correctly switch to the outgoing edge specified by $\chi^{B,\C,j}_{m+1}$. The
first two lemmas consider the case where $1 \le m < \delay(j, \C) - 1$, and the
third lemma considers the case where $m = \delay(j, \C) - 1$. The first lemma
deals with the case where $l < d(i)$, while the second lemma deals with the case
where $l > d(i)$. Observe that there is no need to deal with the case where $l =
d(i)$, because $t^j_{i, d(i)}$ only has one outgoing edge.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $1 \le m <
\delay(j, \C)-1$. For each -gate $i$, and each $l$ int the range $1 \le l <
d(i)$, greedy all-switches strategy improvement will switch $t^j_{i,l}$ to

Lemma <ref> implies that the state $t^j_{i,l}$ will not switch to
$s^j$. In the rest of this proof we consider the two remaining outgoing edges at
this state. We have two cases to consider.

We first deal with the case where $m < l + 1$, where we must show that
the edge to $r^j$ is the highest appeal edge at $t^j_{i,l}$. Let $v =
\sigma(t^j_{i,l})$ be the successor of $t^j_{i,l}$ according to $\sigma$ (if $m
= 1$ then $v = s^j$, and otherwise $v = r^j$). Since $m \le l$, the definition in
Equation (<ref>) we have that $\sigma(t^j_{i,l-1}) = v$. Since the
priority assigned to $t^j_{i,l-1}$ is odd, we therefore have that
$\val^{\sigma}(t^j_{i,l-1}) \sqsubset \val^{\sigma}(v)$. Since we already know
from Lemma <ref> that $\val^{\sigma}(s^j) \sqsubset
\val^{\sigma}(r^j)$, we have therefore proved that the edge to $r^j$ is the most
appealing edge at $t^j_{i,l}$.

Now we deal with the case where $m \ge l + 1$, where we must show that the most
appealing edge at $t^j_{i,l}$ is the one to $t^j_{i,l-1}$. Since $m > l$, the
definition in Equation (<ref>) implies that the path that starts at
$t^j_{i,l-1}$ and follows $\sigma$ will pass through $t^j_{i,l'}$ for all $l'$
in the range $0 \le l' < l$ before arriving at $r^j$. The highest priority on
this path is $\pp(5, i, 2k + 4n + 4, j, 0)$ on the vertex $t^j_{i,0}$. Since
this priority is even we have that $\val^{\sigma}(r^j) \sqsubset
\val^{\sigma}(t^j_{i,l-1})$, and therefore the edge to $t^j_{i,l-1}$ is the most
appealing edge at $t^j_{i,l}$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $1 \le m <
\delay(j,\C) - 1$. For each -gate $i$, and each $l > d(i)$, greedy
all-switches strategy improvement will switch $t^j_{i,l}$ to

Lemma <ref> implies that the state $t^j_{i,l}$ will not switch to
$s^j$. In the rest of this proof we consider the two remaining outgoing edges at
this state.

* First we deal with the case where $m < l + 1$, where we must show that the edge
to $r^j$ is the most appealing edge at $t^j_{i,l}$. When $l > d(i) + 1$, the
proof of this fact is identical to Item <ref> in the proof of
Lemma <ref>. For $l = d(i) + 1$, we invoke Lemma <ref> to
argue that, since $m < l + 1 = d(i) + 2$, we have that $\val^{\sigma}(o^j_i)
\sqsubset \val^{\sigma}(r^j)$. Since the priority assigned to $t^j_{i, d(i)}$ is
odd, we therefore also have that $\val^{\sigma}(t^j_{i,d(i)}) \sqsubset
\val^{\sigma}(r^j)$. Therefore, the edge to $r^j$ is the most appealing edge at
$t^j_{i, d(i) + 1}$.

* Now we deal with the case where $m \ge l + 1$, and where $\eval(B, \inp(i)) =
0$. Here we must show that the edge to $r^j$ is the most appealing edge at
$t^j_{i, l}$. For each $l > d(i) + 1$, the proof is identical to the proof of
the first case in the proof of this lemma. For $l = d(i) + 1$, we invoke
Lemma <ref> to argue that, since $\eval(B, \inp(i)) = 0$ we must
have $\val^{\sigma}(o^j_{\inp(i)}) \sqsubset \val^{\sigma}(r^j)$, and therefore
the edge to $r^j$ is the most appealing edge at $t^j_{i, l}$.

* Finally, we deal with the case where $m \ge l + 1$ and where $\eval(B,
\inp(i)) = 1$. Here we must show that edge to $t^{j}_{i,l-1}$ is the most
appealing edge at $t^j_{i,l}$. From the definition given in
Equation (<ref>), we have that the path that starts at
$t^{j}_{i,l-1}$ and follows $\sigma$ will pass through $t^{j}_{i,l'}$ for each
$l'$ in the range $d(i) \le l' < l$ before moving to $o^j_{\inp(i)}$. Since $m
\ge l + 1 > d(i)$, we have that $m \ge d(i) + 2$, and therefore
Lemma <ref> implies that $\val^{\sigma}(r^j)  \sqsubset
\val^{\sigma}(o^j_{\inp(i)})$ and that $\maxdiff^{\sigma}(r^j, o^j_{\inp(i)})
\ge \pp(6,0,0,0,0)$. All priorities on the path from $t^j_{i,l-1}$ to
$o^j_{\inp(i)}$ are smaller than $\pp(6,0,0,0,0)$, so we can conclude that
$\val^{\sigma}(r^j)  \sqsubset \val^{\sigma}(t^j_{i,l-1})$, as required.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and for $m = \delay(j, \C)-1$. For
each -gate $i$, and each $l$ int the range $1 \le l < \lale$, greedy
all-switches strategy improvement will switch $t^{1-j}_{i,l}$ to

We must show that the edge to $s^{1-j}$ is the most appealing edge at
$t^{1-j}_{i,l}$. It can be verified that all paths starting at $t^{1-j}_{i,l-1}$
reach one of $r^{1-j}$, $s^{1-j}$, or $r^j$. Furthermore, the largest possible
priority on these paths is strictly smaller than $\pp(7, 0, 0, 0, 0)$. Hence, we
can apply part <ref> of Lemma <ref> and
part <ref> of Lemma <ref> to conclude that the edge to
$s^{1-j}$ is the most appealing outgoing edge at $t^{1-j}_{i,l}$.

§ THE STATE $D^J_I$ IN GATES

In this section we show that the states $d^j_{i}$ in the gate gadgets
correctly switch to the outgoing edge specified by $\chi^{B,\C,j}_{m+1}$. The
first lemma considers the case where $m = 1$, the second lemma considers the
case where $m = 2$, the third lemma considers the case where $3 \le m < d(i) +
2$, the fourth lemma considers the case where $d(i) + 2 \le m < \delay(j, \C) -
1$ and the gate outputs 0, the fifth lemma considers the case where $d(i) + 2
\le m < \delay(j, \C)$ and the gate outputs 1, and the final lemma considers the
case where $m = \delay(j, \C) - 1$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and where $m=1$. For each
-gate $i$, greedy all-switches strategy improvement will switch $d^j_i$ to

According to the definition given in Equation (<ref>), we must show
that the edge to $r^j$ is the most appealing edge at $d^j_i$. We do so by a case

* First we consider the vertex $s^j$. Here we can apply part <ref>
of Lemma <ref> to argue that $\val^{\sigma}(s^j) \sqsubset
\val^{\sigma}(r^j)$.

* Next we consider a vertex $a^j_{i, l}$ with $l \ne d(i)$. Here the definition given in
Equation (<ref>) implies that the path that starts at $a^j_{i,l}$
and follows $\sigma$ passes through $t^j_{i,l}$ and then arrives at $s^j$.
The largest priority on this path is $\pp(5, i, l+1, j, 0)$ on the vertex
$a^j_{i,l}$. However, since this priority is smaller than $\pp(7, 0, 0, 0, 0)$,
we can apply part <ref> of Lemma <ref> to prove that
$\val^{\sigma}(a^j_{i,l}) \sqsubset \val^{\sigma}(r^j)$.

* Next we consider a vertex $a^j_{i, l}$ with $l = d(i)$. Here we can apply
Lemma <ref> to argue that $\val^{\sigma}(o^j_{\inp(i)}) \sqsubset
\val^{\sigma}(r^j)$. Furthermore, the largest priority on the path from $a^j_{i,
l}$ to $o^j_i$ is the odd priority on $t^j_{i, d(i)}$. Hence, we can conclude
that $\val^{\sigma}(a^j_{i, d(i)}) \sqsubset \val^{\sigma}(r^j)$.

* Finally, we consider the vertex $e^j_i$. Lemma <ref> implies that
$\br(\sigma)(e^j_i) = d^j_i$. Hence, the path that starts at $e^j_i$ moves to
$d^j_i$ and then to $s^j$. The highest priority on this path is $\pp(4, i ,1, j,
0) < \pp(7, 0, 0, 0, 0)$. Therefore, we can apply Lemma <ref> to
show that $\val^{\sigma}(e^j_i) \sqsubset \val^{\sigma}(r^j)$.

Hence, we have shown that the edge to $r^j$ is the most appealing outgoing edge
at $d^j_i$, so greedy all-switches strategy improvement will switch $d^j_i$ to

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and where $m=2$. For each
-gate $i$, greedy all-switches strategy improvement will switch $d^j_i$ to

According to the definition given in Equation (<ref>), we must show
that the edge to $a^j_{i, \lale}$ is the most appealing edge at $d^j_i$. We do
so by a case analysis.

* First we consider the vertex $r^j$. Observe that the path that starts at
$a^j_{i, \lale}$ and follows $\sigma$ visits $t^j_{i, \lale}$ and then arrives
at $r^j$. The highest priority on this path is the even priority assigned to
$a^j_{i, \lale}$, so therefore we can conclude that $\val^{\sigma}(r^j)
\sqsubset \val^{\sigma}(a^j_{i, \lale})$.

* Next we consider the vertex $s^j$. Here we can apply
Lemma <ref> to argue that $\val^{\sigma}(s^j) \sqsubset
\val^{\sigma}(r^j)$, and we have already shown that
$\val^{\sigma}(r^j) \sqsubset \val^{\sigma}(a^j_{i, \lale})$.

* Next we consider a vertex $a^j_{i, l}$ with $l \ne d(i)$ and $l \ne
a^j_{i, \lale}$. The path that starts at $a^j_{i,l}$
and follows $\sigma$ passes through $t^j_{i,l}$ and then arrives at $r^j$.
The largest priority on this path is
the even priority assigned to $a^j_{i, l}$. However, since $l < \lale$, we have
that this priority is smaller than the even priority assigned to $a^j_{i,
\lale}$. Therefore, we have
$\val^{\sigma}(a^j_{i, l}) \sqsubset \val^{\sigma}(a^j_{i, \lale})$.

* Next we consider the vertex $a^j_{i, d(i)}$. Here we can apply
Lemma <ref> to argue that $\val^{\sigma}(o^j_{\inp(i)}) \sqsubset
\val^{\sigma}(r^j)$. Furthermore, the largest priority on the path from $a^j_{i,
l}$ to $o^j_i$ is the odd priority on $t^j_{i, d(i)}$. Since the highest
priority on the path from $a^j_{i, \lale}$ to $r^j$ is even, we we can conclude
that $\val^{\sigma}(a^j_{i, d(i)}) \sqsubset \val^{\sigma}(a^j_{i, \lale})$.

* Finally, we consider the vertex $e^j_i$. Lemma <ref> implies that
$\br(\sigma)(e^j_i) = d^j_i$. Hence, the path that starts at $e^j_i$ moves to
$d^j_i$ and then to $r^j$. The highest priority on this path is $\pp(4, i ,1, j,
0)$ on the vertex $e^j_i$. However, this is smaller than the largest priority on
the path from $a^j_{i, \lale}$ to $r^j$, so we can conclude that
$\val^{\sigma}(e^j_i) \sqsubset \val^{\sigma}(a^j_{i, \lale})$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $3 \le m <
d(i) + 2$. For each -gate $i$, greedy all-switches strategy improvement
will switch $d^j_i$ to $\chi^{B,\C,j}_{m+1}(d^j_i)$.

Lemma <ref> implies that the state $d^j_i$ will not switch to
$s^j$. In the rest of this proof we consider the other outgoing edges at
this state.

Since we are in the case where $m < d(i) + 2$ the definition from
Equation (<ref>) specifies that greedy all-switches strategy
improvement must switch to $a^j_{i,m-2}$. Hence must argue that the edge to
$a^j_{i,m-2}$ is the most appealing edge at $d^j_i$, and we will start by
considering the appeal of this edge. The definition in
Equation (<ref>) implies that the path that starts at $a^j_{i,m-2}$
passes through $t^j_{i,l}$ for all $l \le m-2$ before arriving at $r^j$. The
highest priority on this path is $\pp(5, i, 2k+4n+4, j, 0)$ on the vertex
$t^j_0$, and the second highest priority on this path is $\pp(5, i , m-1, j, 0)$
on the vertex $a^j_{i,m-2}$. We will now show that all other edges are less

* First we consider the vertex $r^j$. Since $\pp(5, i, 2k+4n+4, j, 0)$ is
even, we immediately get that $\val^{\sigma}(r^j) \sqsubset
\val^{\sigma}(a^j_{i,m-2})$.

Next we consider a vertex $a^j_{i,l}$ with $l < m-2$. The path that
starts at this vertex and follows $\sigma$ passes through $t^j_{i,l'}$  for all
$l' \le l$ before arriving at $r^j$. The highest priority on this path is
$\pp(5, i, 2k+4n+4, j, 0)$ on the vertex $t^j_0$, and the second highest
priority on this path is $\pp(5, i , l+1, j, 0)$ on the vertex $a^j_{i,l}$.
Hence, we have that $\maxdiff^{\sigma}(a^j_{i,m-2}, a^j_{i, l})$ is $\pp(5, i ,
m-1, j, 0)$, and since this is even, we can conclude that
$\val^{\sigma}(a^j_{i,l}) \sqsubset \val^{\sigma}(a^j_{i,m-2})$.

Next we consider a vertex $a^j_{i,l}$ with $l > m-2$  and with $l \ne
d(i)$. The path that starts at this vertex and follows $\sigma$ passes through
$t^j_{i,l}$ and then moves immediately to $r^j$. The highest priority on this
path is is $\pp(5, i , l+1, j, 0)$ on the vertex $a^j_{i,l}$. Since $l+1 < 2k +
4n + 4$ we have that $\maxdiff^{\sigma}(a^j_{i,m-2}, a^j_{i, l})$ is $\pp(5, i ,
2k+4n+4, j, 0)$, and since this priority is even, we can conclude that
$\val^{\sigma}(a^j_{i,l}) \sqsubset \val^{\sigma}(a^j_{i,m-2})$.

Next we consider the vertex $a^j_{i, d(i)}$. The path that starts at this
vertex passes through $t^j_{i, d(i)}$, and then moves to $\inputstate(i, j)$.
Since $m < d(i) + 2$, we have that $m \le d(\inp(i)) + 2$, and therefore the
first case of Lemma <ref> tells us that
$\val^{\sigma}(\inputstate(i,j)) \sqsubset \val^{\sigma}(r^j)$. Hence we can
conclude that $\val^{\sigma}(a^j_{i, d(i)}) \sqsubset
\val^{\sigma}(a^j_{i,m-2})$.

Finally, we consider the vertex $e^j_i$. By Lemma <ref>, the path
that starts at $e^j_i$ and follows $\sigma$ passes through $d^j_i$. If $m=3$, it
then moves to $a^j_{i, \lale}$, and if $m >3$ it then moves to $a^j_{i, m-3}$.
In either case, since the priority assigned to $e^j_i$ is smaller than the
priorities assigned to the vertices $a^j_l$ and $t^j_l$, we can reuse the
arguments made above to conclude that $\val^{\sigma}(e^j_i) \sqsubset
\val^{\sigma}(a^j_{i,m-2})$.

Therefore, we have shown that the edge to $a^j_{i,m-2}$ is the most appealing
outgoing edge at
$d^j_i$, and so this edge will be switched by greedy all-switches strategy

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $d(i) + 2
\le m < \delay(j, \C) - 1$. For each -gate $\eval(B, \inp(i)) = 1$
then greedy all-switches strategy improvement will switch $d^j_i$ to

Lemma <ref> implies that the state $d^j_i$ will not switch to
$s^j$. In the rest of this proof we consider the other outgoing edges at
this state.

Since we are in the case where $m \ge d(i) + 2$ and $\eval(B, \inp(i)) = 1$,
the definition from Equation (<ref>) specifies that greedy all-switches
strategy improvement must switch to $a^j_{i,m-2}$. Hence must argue that the
edge to $a^j_{i,m-2}$ is the most appealing edge at $d^j_i$, and we will start
by considering the appeal of this edge. The definition in
Equation (<ref>) implies that the path that starts at $a^j_{i,m-2}$
passes through $t^j_{i,l}$ for all $l$ in the range $d(i) \le l \le m-2$ before
arriving at $\inputstate(i, j)$. Since $m \ge d(i) + 2$ we have $m > d(\inp(i) +
2$, and so Lemma <ref> implies that $\maxdiff^{\sigma}(r^j,
\inputstate(i, j)) \ge \pp(6, 0, 0, 0, 0)$. We now consider the other outgoing
edges from $d^j_i$.

* First we consider $r^j$, where Lemma <ref> immediately gives
that $\val^{\sigma}(r^j) \sqsubset \val^{\sigma}(a^j_{i,m-2})$.

* Next we consider a vertex $a^j_{i, l}$ with $l < d(i)$. Using the same
reasoning as Item <ref> in the proof of Lemma <ref>, we can
conclude that the highest priority on the path from $a^j_{i, l}$ to $r^j$ is
$\pp(5, i, 2k+4n+4, j, 0) < \pp(6, 0, 0, 0, 0)$ and so therefore
$\val^{\sigma}(a^j_{i,l}) \sqsubset \val^{\sigma}(a^j_{i,m-2})$.

* Next we consider a vertex $a^j_{i, l}$ with $l$ in the range $d(i) \le l <
m -2$. The path that starts at $a^j_{i, l}$ and follows $\sigma$ passes through
$t^j_{i, l'}$ for all $l'$ in the range $d(i) \le l' \le l$ and then arrives at
$\inputstate(i,j)$. The highest
priority on this path is $\pp(5, i, l+1, j, 0)$. On the other hand, the largest
priority on the path from $a^j_{i, m-2}$ to $\inputstate(i,j)$ is
$\pp(5, i, m-1, j, 0)$. Since this priority is even, we can conclude that
$\val^{\sigma}(a^j_{i,l}) \sqsubset \val^{\sigma}(a^j_{i,m-2})$.

* Next we consider a vertex $a^j_{i, l}$ with $l > m - 2$. Using the same
reasoning as Item <ref> in the proof of Lemma <ref> we can
conclude that the highest priority on the path from $a^j_{i, l}$ to $r^j$ is
$\pp(5, i , l+1, j, 0) < \pp(6, 0, 0, 0, 0)$ and so therefore
$\val^{\sigma}(a^j_{i,l}) \sqsubset \val^{\sigma}(a^j_{i,m-2})$.

* Finally, we consider the vertex $e^j_i$, where we can use the same
reasoning as Item <ref> in the proof of Lemma <ref> to conclude
that $\val^{\sigma}(e^j_{i}) \sqsubset \val^{\sigma}(a^j_{i,m-2})$.

Therefore, we have shown that the edge to $a^j_{i,m-2}$ is the most appealing
outgoing edge at $d^j_i$, and so this edge will be switched by greedy
all-switches strategy improvement.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $d(i) + 2
\le m < \delay(j, \C) - 1$. For each -gate $\eval(B, \inp(i)) = 0$
then greedy all-switches strategy improvement will switch $d^j_i$ to

Lemma <ref> implies that the state $d^j_i$ will not switch to
$s^j$. In the rest of this proof we consider the other outgoing edges at
this state.

Since $m \ge d(i) + 2$ and $\eval(B, \inp(i) = 0)$, the definition in
Equation (<ref>) specifies that the edge to $e^j_i$ is the most
appealing edge at $d^j_i$. To prove this, we first show that all other edges are
less appealing than $a^j_{i, d(i) -1}$, and we will then later show that $e^j_i$
is more appealing than $a^j_{i, d(i) -1}$. The definition in
Equation (<ref>) implies that the path that starts at
$a^j_{i,d(i)-1}$ passes through $t^j_{i,l}$ for all $l$ in the range $0 \le l
\le d(i) - 1$ before arriving at $r^j$. The largest priority on this path is
$\pp(5, i, d(i), j 0)$ on the state $a^j_{i, d(i)-1}$. We now consider the other
outgoing edges.

* First we consider the vertex $r^j$. Since $\pp(5, i, 2k+4n+4, j, 0)$ is
even, we immediately get that $\val^{\sigma}(r^j) \sqsubset
\val^{\sigma}(a^j_{i,m-2})$.

* Next we consider a vertex $a^j_{i, l}$ with $l < d(i) -1$. Here we can use
the same reasoning as we used in Item <ref> in the proof of
Lemma <ref> to argue that $\val^{\sigma}(a^j_{i,l}) \sqsubset
\val^{\sigma}(a^j_{i,d(i)-1})$.

* Next we consider a vertex $a^j_{i, l}$ with $l > d(i)$. Here we can use
the same reasoning as we used in Item <ref> in the proof of
Lemma <ref> to argue that $\val^{\sigma}(a^j_{i,l}) \sqsubset
\val^{\sigma}(a^j_{i,d(i)-1})$.

* Finally, we consider the vertex $a^j_{i,d(i)}$. Here we can use the
same reasoning as we used in Item <ref> in the proof of
Lemma <ref> to argue that $\val^{\sigma}(a^j_{i,d(i)}) \sqsubset
\val^{\sigma}(a^j_{i,d(i)-1})$, although this time we will use case two of
Lemma <ref>.

So, we have shown that every edge other than the one to $e^j_i$ is less
appealing than the edge to $a^j_{i, d(i)-1}$.

Now we will show that the edge to $e^j_i$ is more appealing than the edge to
$a^j_{i, d(i)-1}$. There are two cases to consider.

* If $m = d(i) + 2$, then $\sigma(d^j_i) = a^j_{i, d(i)-1}$. Since
Lemma <ref> implies that $\br(\sigma)(e^j_i) = d^j_i$, we have that the
path that starts at $e^j_i$ and follows $\sigma$ passes through $d^j_i$ and then
arrives at $a^j_{i, d(i)-1}$. The largest priority on this path is $\pp(4, i, 1,
j, 0)$, and since this is even, we can conclude that $\val^{\sigma}(a^j_{i, d(i)
- 1})
\sqsubset \val^{\sigma}(e^j_i)$.

* If $m > d(i) + 2$, then $\sigma(d^j_i) = e^j_i$. In this case
Lemma <ref> implies that $\br(\sigma)(e^j_i) = h^j_i$. The path that
starts at $e^j_i$ and follows $\sigma$ passes through $h^j_i$ and then moves
directly to $r^j_i$. The largest priority on this path is $\pp(6, i, 1, j 0)$,
which is bigger than $\pp(5, i, d(i), j 0)$. Therefore,
$\maxdiff^{\sigma}(e^j_i, a^j_{i, d(i) - 1} = \pp(6, i, 1, j 0)$, and since this
is even, we can conclude that $\val^{\sigma}(a^j_{i, d(i) - 1}) \sqsubset
\val^{\sigma}(e^j_i)$.

Hence, we have shown that the edge to $e^j_i$ is the most appealing edge at

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and for $m = \delay(j, \C)-1$. For
each -gate $i$ greedy
all-switches strategy improvement will switch $d^{1-j}_{i}$ to

We must show that the edge to $s^{1-j}$ is the most appealing edge at
$d^{1-j}_{i}$. It can be verified that all paths starting at the vertices
$a^{1-j}_{i,l}$ and $e^j_i$ reach one of $r^{1-j}$, $s^{1-j}$, or $r^j$.
Furthermore, the largest possible priority on all of these paths is strictly
smaller than $\pp(7, 0, 0, 0, 0)$. Hence, we can apply part <ref> of
Lemma <ref> and part <ref> of Lemma <ref>
to conclude that the edge to $s^{1-j}$ is the most appealing outgoing edge at

§ THE VERTICES $Z^L$

In this section we show that the states $z^l$ correctly switch to the outgoing
edge specified by $\chi^{B,\C,j}_{m+1}$. The first lemma considers the case
where $l = j$, while the second lemma considers the case where $l = 1-j$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and $m$ in the range $1 \le m \le
\delay(j, \C) - 1$. The greedy all-switches strategy improvement algorithm will switch
$z^{j}$ to $\chi^{B,\C,j}_{m+1}(z^{j})$.

We must show that the edge to $r^j$ is the most appealing edge at $z^j$. This
follows immediately from part <ref> of Lemma <ref>.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $1 \le m \le
\delay(j, \C) - 1$. The greedy all-switches strategy improvement algorithm will switch
$z^{1-j}$ to $\chi^{B,\C,j}_{m+1}(z^{1-j})$.

There are two cases to consider.

* If $m < \delay(j, \C) - 1$, then we must show that the edge to $r^{1-j}$
is the most appealing edge at $z^{1-j}$. This follows immediately by applying
part <ref> of Lemma <ref>.

* If $m = \delay(j, \C) - 1$, then since $\delay(j, \C) + \delay(1-j, \C) =
\length(\C)$, we must show that the edge to $s^{1-j}$ is the most appealing edge
at $z^{1-j}$. This follows immediately from part <ref> of
Lemma <ref>.

§ THE VERTICES $Y^L$

In this section we show that the states $y^l$ correctly switch to the outgoing
edge specified by $\chi^{B,\C,j}_{m+1}$. The first lemma considers the case
where $l = j$, while the second lemma considers the case where $l = 1-j$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $1 \le m \le
\delay(j, \C) - 1$. The greedy all-switches strategy improvement algorithm will switch
$y^j$ to $\chi^{B,\C,j}_{m+1}(y^j)$.

The definition of $\chi^{B,\C,j}_{m+1}(y^{j}_i)$ specifies that the edge chosen
at $y^{j}$ is defined by $\sigma_{m+\delay(j, \C)}(y^{j})$, which is given in
Equation (<ref>).  According to this definition, we must show that the
edge to $r^j$ is the most appealing outgoing edge at $y^j$. This follows
immediately from parts <ref> and <ref> of
Lemma <ref>.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $1 \le m \le
\delay(j, \C) - 1$. The greedy all-switches strategy improvement algorithm will
switch $y^{1-j}$ to $\chi^{B,\C,j}_{m+1}(y^{1-j})$.

According to Equation (<ref>), we must show that the edge to $r^j$ is the
most appealing edge at $y^{1-j}$. This follows immediately  from
Lemma <ref>.

§ THE VERTICES $P^L_I$

In this section we show that the vertices $p^l_i$ correctly switch to the
outgoing edge specified by $\chi^{B,\C,j}_{m+1}$. The first lemma considers the
case where $l = j$, while the second lemma considers the case where $l = 1-j$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $1 \le m \le
\delay(j, \C) - 1$. For each $i \in \inputg$, the greedy all-switches strategy
improvement algorithm will switch $p^j_{i}$ to $\chi^{B,\C,j}_{m+1}(p^j_i)$.

Since $m$ is in the range $1 \le m \le \delay(j, \C) - 1$, the definition given
in Equation (<ref>) specifies that $o^j_{\inp(i)}$ should be the most
appealing outgoing edge at $p^j_i$. There are two cases to consider.

* If $m = 1$, then observe that the path that starts at $o^j_{\inp(i)}$ and
follows $\sigma$ will eventually reach $s^j$, no matter whether $\inp(i)$ is a
-gate or an -gate. Furthermore, the largest priority on this path is
strictly smaller than $\pp(7, 0, 0, 0, 0)$. On the other hand, the path that
starts at $p^j_{i,1}$ moves immediately to $r^{1-j}$, and the largest priority
on this path is strictly smaller than $\pp(7, 0, 0, 0, 0)$. Hence, we can apply
part <ref> of Lemma <ref> to argue that
$\val^{\sigma}(p^{j}_{i,1}) \sqsubset \val^{\sigma}(o^j_{\inp(i)})$, as

* If $m \ge 1$, then then observe that the path that starts at
$o^j_{\inp(i)}$ and follows $\sigma$ will eventually reach $r^j$, and again the
largest priority on this path is strictly smaller than $\pp(7, 0, 0, 0, 0)$.
Hence, we can apply part <ref> of Lemma <ref> to argue
that $\val^{\sigma}(p^{j}_{i,1}) \sqsubset \val^{\sigma}(o^j_{\inp(i)})$, as

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $1 \le m \le
\delay(j, \C) - 1$. For each $i \in \inputg$, the greedy all-switches strategy
improvement algorithm will switch $p^{1-j}_{i}$ to

The definition given in Equation (<ref>) specifies that the edge to
$p^{1-j}_{i}$ should be the most appealing edge at $p^{1-j}_i$. The path that
starts at $o^{1-j}_{\inp(i)}$ and follows $\sigma$ must eventually arrive at
either $s^{1-j}$ or $r^{1-j}$. In particular, observe that $r^j$ cannot be
reached due to the vertices $q^j_{i, 0}$, which by Lemma <ref> selects
the edge towards $q^j_{i, 1}$. On the other hand, the path that starts at
$p^{1-j}_{i,1}$ moves directly to $r^j$. Moreover the largest priorities on both
of these paths are strictly smaller than $\pp(7, 0, 0, 0, 0)$. Hence, we can
apply Lemmas <ref> and <ref> to argue that
$\val^{\sigma}(o^j_{\inp(i)}) \sqsubset \val^{\sigma}(r^j)$.

§ THE VERTICES $H^L_{I,0}$

In this section we show that the vertices $h^l_{i,0}$ correctly switch to the
outgoing edge specified by $\chi^{B,\C,j}_{m+1}$. The first lemma considers the
case where $l = j$, while the second lemma considers the case where $l = 1-j$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $1 \le m \le
\delay(j, \C) - 1$. For each $i \in \inputg$, the greedy all-switches strategy
improvement algorithm will switch $h^j_{i, 0}$ to $\chi^{B,\C,j}_{m+1}(h^j_{i,

We must show that the most appealing edge at $h^{j}_{i,0}$ should be
$h^j_{i,1}$. Observe that both $h^j_{i,1}$ and $h^j_{i,2}$ move directly to
$r^j$ and $r^{1-j}$, respectively. Moreover, the priorities assigned to these
vertices are strictly smaller than $\pp(7, 0, 0, 0, 0)$. Since $h^j_{i,1}$ moves
to $r^{j}$, we can apply part <ref> of Lemma <ref> to
prove that $h^j_{i,1}$ is the most appealing edge at $h^j_{i, 0}$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and some $m$ in the range $1 \le m \le
\delay(j, \C) - 1$. The greedy all-switches strategy improvement algorithm will switch
$h^{1-j}_{i, 0}$ to $\chi^{B,\C,j}_{m+1}(h^{1-j}_{i,0})$.

We must show that the most appealing edge at $h^{j}_{i,0}$ should be
$h^j_{i,1}$. Observe that both $h^{1-j}_{i,1}$ and $h^{1-j}_{i,2}$ move directly
to $r^{1-j}$ and $r^{j}$, respectively. Moreover, the priorities assigned to
these vertices are strictly smaller than $\pp(7, 0, 0, 0, 0)$. We will use these
fact in order to apply Lemma <ref> in the following case
analysis. According to Equation (<ref>), there are two cases to consider.
Since $h^j_{i,1}$ moves to $r^{j}$, we can apply part <ref> of
Lemma <ref> to prove that $h^j_{i,1}$ is the most appealing edge
at $h^j_{i, 0}$.

§ INPUT/OUTPUT GATES

In this section we show that the vertices in the input/output gadgets  correctly
switch to the outgoing edge specified by $\chi^{B,\C,j}_{m+1}$. The first two
lemmas deal with the case where the input/output gadget for circuit $j$ resets.
Note that this occurs one iteration later than the rest of the vertices in
circuit $j$, which is why we prove separate lemmas for this case. Otherwise, the
input/output gadgets behave as if they are gates, so the proofs that we have
already given for the gates can be applied with only minor changes. These is
formalized in the final two lemmas of this section. The first of these lemmas
considers the input/output gadgets in circuit $j$ and the second considers the
input/output gadgets in circuit $1-j$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and for $m = 1$. For
each -gate $i$, and each $l$ int the range $1 \le l < \lale$, greedy
all-switches strategy improvement will switch $t^{j}_{i,l}$ to

We must show that the edge to $z^j$ is the most appealing edge at $t^j_{i, l}$.
All paths that start at $t^j_{i, l}$ and follow $\sigma$ will eventually arrive
at $r^{1-j}$, either via $y^j$, or via $p^j_i$. On the other hand, the path that
starts at $z^j$ moves directly to $s^j$. Therefore, part <ref> of
Lemma <ref> implies that the edge to $z^j$ is the most appealing
edge at $t^j_{i, l}$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and for $m = 1$. For
each -gate $i$ greedy
all-switches strategy improvement will switch $d^{j}_{i}$ to

This proof uses the same argument as the proof of Lemma <ref>,
because all paths that start at $d^j_i$ will eventually arrive at $r^{1-j}$.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and for $m$ in the range $2 \le m \le
\delay(j, \C) - 1$. For each -gate $i$, and each $l$ int the range $1 \le
l < \lale$, greedy all-switches strategy improvement will switch $t^{j}_{i,l}$
to $\chi^{B,\C,j}_{m+1}(t^{j}_{i,l})$ and $d^{j}_{i}$ to

Since $m \ge 2$, we have that $\sigma(y^j) = r^j$ and $\sigma(z^j) = s^j$.
Hence, both  $t^{j}_{i,l}$ and $d^j_i$ behave in exactly the same way as the
states $t^{j}_{i',l}$ and $d^j_{i',l}$ for $i' \in \notg$, with the exception
that these states one step behind the -gate vertices, due to the delay
introduced by $y^j$. Note, however, that this is account for by placing the edge
to $p^j_i$ on $t^j_{i, d(C)}$, rather than $t^j_{i, d(C)+1}$, as would be
expected for a -gate with depth $d(C) + 1$. Therefore, to prove this lemma,
we can use exactly the reasoning as gave for
Lemmas <ref>, <ref>, <ref>, <ref>, <ref>, <ref>,
and <ref>. This is because all of the reasoning used there is done
relative to $r^j$ and $s^j$, and since $y^j$ and $z^j$ have insignificant
priorities, none of this reasoning changes.

Let $\sigma$ be a strategy that agrees with $\chi^{B, \C, j}_m$ for some $\C, B
\in \{0, 1\}^n$, some $j \in \{0, 1\}^n$, and for $m$ in the range $2 \le m <
\delay(j, \C) - 1$. For each -gate $i$, and each $l$ int the range $1 \le
l < \lale$, greedy all-switches strategy improvement will switch $t^{1-j}_{i,l}$
to $\chi^{B,\C,j}_{m+1}(t^{1-j}_{i,l})$ and $d^{1-j}_{i}$ to

Much like the proof of Lemma <ref>, this claim can be proved using
essentially the same reasoning given as was given for
Lemmas <ref>, <ref>, <ref>, <ref>, <ref>, <ref>,
and <ref>, because an -gate behaves exactly like a -gate.

In particular, note that since we have defined $\chi^{B, \C, 0}_{\delay(0,\C)} =
\chi^{B, \C, 1}_1$ and $\chi^{B, \C, 1}_{\delay(1,\C)} = \chi^{B, \C+1,
0}_1$, the gate gadgets in circuit $1-j$ continue to have well-defined
strategies, so the $d^{1-j}_i$ will continue to act like a -gate between
iterations $1$ and $2$.

The one point that we must pay attention to is that, in the transition between
$\chi^{B,\C,j}_{1}$ and $\chi^{B,\C,j}_{2}$, the state $y^{1-j}$ switches from
$r^{1-j}$ to $r^{j}$. Note, however, that both $h^j_{i, 0}$ and $p^j_i$ both
switch to vertex that eventually leads to $r^j$ at exactly the same time, so all
paths that exit the gadget will switch from $r^{1-j}$ to $r^j$. Since almost all
of the reasoning in the above lemmas is done relative to $r^j$, the relative
orders over the edge appeals cannot change.

The only arguments that must be changed are the ones that depend on
Lemma <ref>. Here, the fact that the priority $\pp(5, i, 2k+4n+5, j,
0)$ is assigned to $p^{1-j}_{i,1}$ is sufficient to ensure that
$\val^{\sigma}(r^j) \sqsubset \val^{\sigma}(t^{1-j}_{i, d(C)})$, so the
deceleration lane will continue switching. On the other hand, since $\pp(5, i,
2k+4n+5, j, 0) < \pp(7, 0, 0, 0, 0)$, this priority is not large enough to cause
$d^j_i$ to switch away from $e^j_i$, if $B_i = 1$.