# Degenerate crossing number and signed reversal distance††thanks: This work
was partially supported by the ANR project SoS (ANR-17-CE40-0033). An extended
abstract appeared in the Proceedings of the 31st International Symposium on
Graph Drawing and Network Visualization (GD 2023)

Niloufar Fuladi Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée,
France Alfredo Hubard22footnotemark: 2 Arnaud de Mesmay22footnotemark: 2

###### Abstract

The degenerate crossing number of a graph is the minimum number of transverse
crossings among all its drawings, where edges are represented as simple arcs
and multiple edges passing through the same point are counted as a single
crossing. Interpreting each crossing as a cross-cap induces an embedding into
a non-orientable surface. In 2007, Mohar showed that the degenerate crossing
number of a graph is at most its non-orientable genus and he conjectured that
these quantities are equal for every graph. He also made the stronger
conjecture that this also holds for any loopless pseudotriangulation with a
fixed embedding scheme.

In this paper, we prove a structure theorem that almost completely classifies
the loopless 2-vertex embedding schemes for which the degenerate crossing
number equals the non-orientable genus. In particular, we provide a
counterexample to Mohar’s stronger conjecture, but show that in the vast
majority of the 2-vertex cases, the conjecture does hold.

The reversal distance between two signed permutations is the minimum number of
reversals that transform one permutation to the other one. If we represent the
trajectory of each element of a signed permutation under successive reversals
by a simple arc, we obtain a drawing of a 2-vertex embedding scheme with
degenerate crossings. Our main result is proved by leveraging this connection
and a classical result in genome rearrangement (the Hannenhali-Pevzner
algorithm) and can also be understood as an extension of this algorithm when
the reversals do not necessarily happen in a monotone order.

##  1 Introduction

A _cross-cap drawing_ of a graph $G$ is a drawing of $G$ on the sphere with
$g$ distinct points, called _cross-caps_ , such that the drawing is an
embedding except at the cross-caps, where multiple edges are allowed to cross
transversely, as pictured in Figure 1.

Figure 1: A degenerate crossing and a cross-cap placed at this crossing.

In [13], Pach and Toth introduced the _degenerate crossing number_ , denoted
by $Cr_{deg}(G)$ which in this language is the minimum number of cross-caps
for a cross-cap drawing of $G$ to exist, where edges are required to be drawn
as simple arcs. In [11], Mohar removed the constraint that edges be simple
arcs, leading to the _genus crossing number_ , which he proved to be equal to
the non-orientable genus of the graph, denoted by $g(G)$. He then made an
enticing conjecture claiming that these two crossing numbers are equal. We say
that a cross-cap drawing of graph $G$ is _perfect_ if there are $g(G)$ cross-
caps and every edge intersects each cross-cap at most once. Then this
conjecture can be restated as follows:

######  Conjecture 1.1.

[11, Conjecture 3.1, Proposition 3.3] Every simple graph has a perfect cross-
cap drawing.

Mohar went further and conjectured that for any loopless graph embedding,
there exists a perfect cross-cap drawing that is compatible with this
embedding, in a sense that we now describe. The terminology that we introduce
is equivalent to the PD1S in [11, Section 3]. A _pseudo-triangulation_ is a
cellularly embedded multi-graph $\phi\colon G\to S$ in which each face has
degree three. Denote by $S^{2}\setminus g\tiny{\bigotimes}$, the sphere minus
$g$ tiny disks, and by $(S^{2}\setminus g\tiny{\bigotimes})/\sim$ the space
obtained by quotienting the boundary of each disk with the antipodal map.
Topologically, this amounts gluing a Möbius band on each missing disk, thus
yielding the non-orientable surface of genus $g$, denoted by $N_{g}$. We say
that an embedded multi-graph $\phi\colon G\to N_{g}$ _admits a cross-cap
drawing_ $\phi^{\prime}\colon G\to(S^{2}\setminus g\tiny{\bigotimes})/\sim$,
if there is a homeomorphism $f\colon N_{g}\to(S^{2}\setminus
g\tiny{\bigotimes})/\sim$ such that $f(\phi(G))=\phi^{\prime}(G)$.

######  Conjecture 1.2.

[11, Conjecture 3.4] For any positive integer $g$, every loopless pseudo-
triangulation of $N_{g}$ admits a perfect cross-cap drawing.

An even stronger conjecture was hinted at in [11, Paragraph following
Conjecture 3.4], suggesting that one could possibly remove the loopless
assumption if one forbids separating loops. This strengthening was disproved
by Schaefer and Štefankovič [14, Theorem 7].

In addition to their motivation from crossing number theory, these conjectures
would also shed light on the difficult task of visualizing high genus embedded
graphs, providing an alternate approach to that of Duncan, Goodrich and
Kobourov [5], who rely on canonical polygonal schemes [10].

#### Our results.

A big step towards both these conjectures was achieved by Schaefer and
Štefankovič, who proved [14, Theorem 10] that any multi-graph embedded on a
non-orientable surface of genus $g$ admits a cross-cap drawing with $g$ cross-
caps, in which each edge enters each cross-cap at most _twice_. This theorem
applies in particular to one-vertex embedding schemes, and thus suggests a
natural approach towards proving Conjectures 1.1 and 1.2. First contract a
spanning tree to obtain a one-vertex graph and apply this theorem. Then, edges
might enter cross-caps twice, but since the initial graph is loopless, one
could hope to uncontract some edges so as to spread these two cross-caps on
two edges, thus obtaining a perfect cross-cap drawing. Our first result shows
that this approach cannot work, as some loopless $2$-vertex schemes do not
admit perfect cross-cap drawings.

Figure 2: Left: A loopless 2-vertex scheme made of a _positive block_ , in
red, consisting of only positive edges, and a _negative block_ , in blue,
consisting of negative edges. Middle: a cross-cap drawing showing that it has
non-orientable genus $5$. The bold red edge enters a cross-cap twice. Right: A
cross-cap drawing where each edge enters each cross-cap at most once requires
$6$ cross-caps.

######  Theorem 1.3.

A loopless $2$-vertex embedding scheme that consists of exactly one non-
trivial positive block and one non-trivial negative block admits no perfect
cross-cap drawing.

We refer to Figure 2 for an example that should provide an intuitive idea of
the notion of blocks, and to Section 2 for the precise definition. As a
corollary, we obtain a counter-example to Conjecture 1.2:

######  Corollary 1.4.

There exist a loopless pseudo-triangulation $G$ that admits no perfect cross-
cap drawing.

Our second contribution and main theorem is a converse to Theorem 1.3.

######  Theorem 1.5.

For any embedding $G$ of a loopless $2$-vertex graph on $N_{g}$, at least one
of the following is true.

  1. 1.

$G$ admits a perfect cross-cap drawing with $g$ cross-caps,

  2. 2.

or the reduced graph of $G$ is one of the two schemes pictured in Figure 3,

Figure 3: The only two possible exceptions to perfect cross-cap drawings.

We refer to Section 2 for the definition of blocks and reduced graphs.
Essentially, Theorem 1.5 shows that apart from two narrow families of
exceptional cases, all the loopless 2-vertex embeddings do satisfy Conjecture
1.2. As an illustration, Figure 4 shows that while the example in Figure 2
does not admit a perfect cross-cap drawing, surprisingly, it does after
_adding_ two edges to it. It directly follows from Theorem 1.5 that under
standard random models, any loopless 2-vertex embedding scheme admits a
perfect cross-cap drawing asymptotically almost surely.

Figure 4: A perfect cross-cap drawing of Figure 2 with two additional edges.

#### Techniques and connections to signed reversal distance.

Our focus on the 2-vertex case in Theorem 1.5 is further motivated by a
connection (introduced in [7]) to computational genomics. An important problem
in computational biology is to compute various notions of distance between two
genomes (see [4, 6]). Remarkably, one of the most biologically relevant
distances is also one of the few that can be calculated efficiently: a one
chromosome genome is encoded by a signed permutation (i.e., permutations of
integers in which each element has a sign) $\pi=(\pi_{1},\ldots,\pi_{n})$. The
_reversal_ of the interval $(i,j)$ acts on $\pi$ by reversing the order of the
elements $\pi_{i},\ldots,\pi_{j}$ as well as their signs, it maps

$(\pi_{1},\pi_{2},\ldots,\pi_{i-1},\pi_{i},\pi_{i+1}\ldots,\pi_{j-1},\pi_{j},\pi_{j+1}\ldots\pi_{n}),$

to

$(\pi_{1},\pi_{2},\ldots,\pi_{i-1},\overline{\pi_{j}},\overline{\pi_{j-1}}\ldots,\overline{\pi_{i+1}},\overline{\pi_{i}},\pi_{j+1}\ldots\pi_{n}).$

The _reversal distance_ between signed permutations $\pi,\pi^{\prime}$,
denoted by $d(\pi,\pi^{\prime})$ is the minimum number of reversals needed to
transform $\pi$ to $\pi^{\prime}$. A celebrated algorithm of Hannenhalli and
Pevzner [8] (see also [2, 3]) computes in polynomial time the reversal
distance between two signed permutations.

Now, a signed permutation is exactly the combinatorial data in the embedding
scheme of a 2-vertex loopless graph, and when tracing the action of each
element of a signed permutation under the action of reversals, one obtains a
cross-cap drawing of that embedding scheme, where each reversal corresponds to
a cross-cap and each edge is an x-monotone curve, and in particular no edge
enters twice the same cross-cap (see Figure 5 for an illustration).

This easily implies the inequalities: $g(\pi)\leq Cr_{deg}(\pi)\leq
d(\pi,id)$. It turns out that the inequality $g(\pi)\leq d(\pi,id)$ is central
to the reversal distance theory, and the cases of equality are well
understood. As we explain in Section 4 these arguments are natural from the
point of view of embedding schemes and our proof of Theorem 2 heavily relies
on them. Conversely, Theorem 1.5 can be reinterpreted in the setting of signed
permutations as providing an extension of the Hannenhalli-Pevzner theory.

The proof of Theorem 1.5 consists of two steps which can readily be made
algorithmic: we first _reduce_ a signed permutation $\pi$ to a simpler one
$\pi|$ for which we can prove that $g(\pi|)=d(\pi|,id)$ (Lemma 5.1), then we
devise a technique to _blow up_ (Lemma 5.3) the cross-cap drawing of the
reduced signed permutation $\pi|$, yielding a perfect cross-cap drawing of the
original signed permutation.

##  2 Preliminaries

#### Embedding schemes

Figure 5: From sorting permutations with reversals to monotone cross-cap
drawings.

In this article, we work with multi-graphs, possibly with loops and multiple
edges. An _embedding_ of a graph $G$ on a surface $S$ is an injective map
$\phi:G\rightarrow S$. We consider two embeddings equivalent if their images
are homeomorphic. The _faces_ of an embedded graph are the connected
components of $S\setminus\phi(G)$. An embedding is _cellular_ if its faces are
homeomorphic to topological disks. The Euler genus, $eg(G)$, of a cellular
embedding of a graph $G$ is the quantity $2-v+e-f$, where $v$, $e$ and $f$
denote respectively the number of vertices, edges and faces of the embedding
of $G$. If $S$ is orientable, an embedding can be described combinatorially by
a _rotation system_ , that is, the set of cyclic permutations encoding the
order of the edges around each vertex. When $S$ is non-orientable, which will
always be the case in this paper, some additional data is required to encode
an embedding, which is encompassed in the concept of an _embedding scheme_. We
introduce the main definitions and refer to Mohar and Thomassen [12, Section
3.3] for extensive background.

######  Definition 2.1 (Embedding scheme).

An _embedding scheme_ consists of a triple $(G,\rho,\lambda)$ where

  * •

$G$ is a graph,

  * •

$\rho=\\{\rho_{v},v\in V(G)\\}$, where each $\rho_{v}$ is a cyclic permutation
of the edges incident to $v$, and

  * •

$\lambda$ is a function that assigns a _signature_ $\\{+1,-1\\}$ to each edge
of $G$.

From an embedding scheme $(G,\rho,\lambda)$, one can naturally recover the set
of _facial cycles_ by following the edges and switching sides according to
their signatures. Then, pasting a topological disk on each facial cycle yields
a cellular embedding of $G$. Given an embedding scheme $(G,\rho,\lambda)$, a
_flip_ at a vertex $v$ yields another embedding scheme of the same graph, in
which we reverse the order of the edges incident to $v$ and invert the
signature of those edges incident to $v$ that are not loops. We say that two
embedding schemes $(G,\rho,\lambda)$ and $(G,\rho^{\prime},\lambda^{\prime})$
are _equivalent_ if one can go from one to the other one by a sequence of
flips. Two embedding schemes are equivalent if and only if they induce
equivalent cellular embeddings [12, Theorem 3.3.1]. This justifies that
equivalence classes of embedding schemes and embedded graphs can be considered
as being two representations of the same objects, and we switch freely between
the two points of view in this article, sometimes using the shorthand $G$ to
denote $(G,\rho,\lambda)$.

A closed curve in an embedding scheme is one-sided (resp. two-sided) if and
only if the signatures of its edges multiply to $-1$ (resp. $+1$). An
embedding scheme is called _orientable_ if it only contains two-sided closed
curves; otherwise it is called _non-orientable_. A closed curve in a non-
orientable embedding scheme is _separating_ if cutting along $\gamma$ yields
two connected components. A closed curve in a non-orientable embedding scheme
is _orienting_ [7, 14] if by cutting along $\gamma$, we obtain a connected
orientable surface.

For two edges $a$ and $b$ in a 2-vertex embedding scheme, we denote by $a\cdot
b$ the concatenation of $a$ and $b$ which we will interpret as a cycle.
Denoting the vertices of the scheme by $v_{1}$ and $v_{2}$, we define a
_wedge_ between $a$ and $b$, $\omega_{a,b}$:

  * •

If both $a$ and $b$ are negative, then $\omega_{a,b}$ contains all the half-
edges in the interval $(a,b)$ in both $\rho_{v_{1}}$ and $\rho_{v_{2}}$.

  * •

If at least one of them is positive, then $\omega_{a,b}$ contains all the
half-edges in the interval $(a,b)$ in $\rho_{v_{1}}$ and $(b,a)$ in
$\rho_{v_{2}}$.

We say that a wedge _encloses_ an edge if it contains both its half-edges or
none of them. For example $w_{1,4}$ in Figure 6 encloses all the edges of the
graph. We can recognize orienting and separating curves in an embedding scheme
with the following lemmas. See Figure 6 for an example of separating and
orienting cycle in a 2-vertex scheme.

Figure 6: The wedges $\omega_{1,4}$ and $\omega_{3,5}$ depicted in orange and
green respectively.

######  Lemma 2.2.

For two edges $a$ and $b$ in a non-orientable loopless 2-vertex embedding
scheme, the cycle $a.b$ is orienting,

  * •

if at least one of $a$ and $b$ is positive and $\omega_{a,b}$ contains exactly
one end of all negative edges and encloses all the positive edges, or

  * •

if both $a$ and $b$ are negative and their wedge contains exactly one end of
all positive edges and encloses all the negative edges.

###### Proof.

We prove the lemma by contracting the edge $a$ in order to obtain a one-vertex
embedding scheme $G^{\prime}$. Note that the topological type of the cycle
formed by the edges $a$ and $b$ is the same as the loop $b$ in $G^{\prime}$.
Denote the vertices of $G$ by $v_{1}$ and $v_{2}$. When we contract a positive
edge $e$ in $G$, we obtain an embedding scheme $G^{\prime}$ with a single
vertex $w$ such that the cyclic permutation of the edges around $w$ after
contraction is $\rho_{w}=\rho_{v_{1}}\rho_{v_{2}}$ where the edge $e$ has been
removed from both cyclic permutations and the notation means that have been
concatenated at $e$. On the other hand, when we contract a negative edge $e$
in $G$, $\rho_{w}=\rho_{v_{1}}\overline{\rho_{v_{2}}}$, where the edge $e$ has
been removed from both permutations, the signature of all the edges are
reversed and the notation means that they have been concatenated at $e$. The
ends of the loop $b$ subdivide the half-edges around $w$ into two sets. We can
see that the half-edges in $\omega_{a,b}$ in $G$ correspond to one of the sets
of half-edges divided by $b$ in $\rho_{w}$.

By [7, Lemma 2.3], a loop $o$ in a 1-vertex non-orientable embedding scheme is
orienting if and only if its ends _alternate_ with the ends of all negative
loops in the cyclic permutation around the vertex and _enclose_ the ends of
any positive loop; i.e. the ends of $o$ does not alternate with the ends of
any positive loop.

To prove the first case, without loss of generality we can assume that $a$ is
positive. We contract the edge $a$ in $G$. Since the wedge $\omega_{a,b}$ in
$G$ contains exactly one end of each negative edge, the ends of the loop $b$
alternate with the ends of negative loops in $\rho_{w}$. Similarly, since
$\omega_{a,b}$ encloses all the positive edges, the ends of $b$ enclose the
ends of any positive loop in $\rho_{w}$. Therefore $b$ is orienting in
$G^{\prime}$ and this implies that the cycle formed by $a$ and $b$ is
orienting in $G$. For the proof of the second case in 1 we proceed identically
by contracting the negative edge $a$. This finishes the proof. ∎

######  Lemma 2.3.

For two edges $a$ and $b$ in a loopless 2-vertex embedding scheme, the cycle
$a.b$ is separating if $a$ and $b$ have the same signature and $\omega_{a,b}$
encloses all the edges.

###### Proof.

We contract $a$. The loop $b$ has positive signature in $G^{\prime}$ and since
$\omega_{a,b}$ contains both ends of any edge inside it then the ends of $b$
separate the ends of the other loops in $G^{\prime}$, i.e. the ends of no loop
alternates with those of $b$. Such a loop is separating the surface, and
therefore $a$ and $b$ form a separating cycle in $G$. ∎

#### 2-vertex embedding schemes and signed permutations

This paper almost exclusively deals with loopless graphs with two vertices,
and in that setting embedding schemes take a particularly simple form. Without
loss of generality, one can number the edges so that the cyclic permutation
around one of the vertices is the identity. Then the data of the embedding
scheme just consists of the cyclic permutation around the other vertex, and
the signature of the edges, and thus this amounts to a _signed cyclic
permutation_ : a cyclic permutation where each number is additionally endowed
with a $+$ or $-$ sign. We also use an overline notation $\overline{i}$ to
depict negative signs. Therefore, in what follows we freely identify a signed
permutation and a 2-vertex embedding scheme. Two edges in a 2-vertex embedding
scheme are _homotopic_ if either they are both positive and appear
consecutively in increasing order (e.g., $(i,i+1)$) or they are both negative
and they appear in the reverse order (e.g., $(\overline{i+1},\overline{i})$).

A _positive block_ in a signed permutation is an interval
$I=(\pi_{i},\ldots,\pi_{j})$ where all the elements are positive,
$\pi_{i}<\pi_{j}$, all the integers in $[\pi_{i},\pi_{j}]$ are contained in
$I$. A _negative block_ in a signed permutation is an interval
$I=(\overline{\pi_{i}},\ldots\overline{\pi_{j}})$ where all the elements are
negative, $\pi_{i}>\pi_{j}$, and all the integers in $[\pi_{j},\pi_{i}]$ are
contained in $I$. A block is _non-trivial_ if it is not already sorted, i.e.,
it is not equal to $(\pi_{i},\pi_{i}+1,\ldots\pi_{j}-1,\pi_{j})$ or to
$(\overline{\pi_{i}},\overline{\pi_{i}-1},\ldots,\overline{\pi_{j}+1},\overline{\pi_{j}})$.
Our concept of blocks is similar to the notion of hurdles of [8], or more
accurately, to the notion of unoriented components in [3]. In both cases, we
call $\pi_{i}$ and $\pi_{j}$ the frames of the block. A block is called
_minimal_ if it does not contain any block except itself.

We say that a signed permutation is _reduced_ if it has no blocks. Given a
signed permutation $\pi$, its reduced permutation $\pi|$ is a permutation in
which we replace every minimal block with a single element of the same sign,
and we iterate this process until we arrive at a reduced permutation.

#### Cross-cap drawings

A cross-cap drawing of an embedding scheme $(G,\rho,\lambda$) is a cross-cap
drawing of $(G,\rho,\lambda)$ or of an equivalent scheme (under flips), that
respects the cyclic permutations and signatures on the edges, i.e., if an edge
has signature $+1$ (resp. $-1$) then it enters an even (resp. odd) number of
cross-caps. This definition is equivalent to the cross-cap drawings of
embeddings defined in the introduction. For non-orientable embedding schemes,
by Euler’s formula, the minimum number of cross-caps for a drawing coincides
with the Euler genus. For orientable embedding schemes of non-zero Euler
genus, one needs exactly one additional cross-cap:

######  Lemma 2.4 ([14, Lemma 6]).

Let $(G,\rho,\lambda)$ be an orientable embedding scheme with non-zero Euler
genus. Then any cross-cap drawing of $G$ requires $eg(G)+1$ cross-caps, in
particular $eg(G)+1$ is odd.

The next lemma allows us to recognize types of curves in a cross-cap drawing.

######  Lemma 2.5.

For any cross-cap drawing of a non-orientable embedding scheme:

  1. 1.

A closed curve is one-sided (two-sided) if and only if it enters an odd (even)
number of cross-caps.

  2. 2.

A closed curve is orienting (separating) if and only if it enters each cross-
cap an odd (even) number of times.

We refer to [14, Lemma 3] and [14, Lemma 4] for proofs.

#### Reversal distance and monotone cross-cap drawings

Signed permutations model genomes with a single chromosome in computational
biology where they come endowed with the reversal distance. The reversal
distance $d(\pi,id)$ is the smallest number $d$ such that there exists a
sequence $\\{\pi=\pi^{1},\pi^{2},\ldots\pi^{d}=id\\}$ such that $(\pi^{i})$
and $(\pi^{i+1})$ differ by a signed reversal. We call such a (not necessarily
minimizing) sequence, a _path_ of signed permutations.

To any path of signed permutations $\\{\pi^{1},\pi^{2},\ldots\pi^{d}\\}$ we
can associate a cross-cap drawing. We place a source vertex at $(-1,n/2)$ and
a terminal vertex at $(d+1,n/2)$. Edges will be $x$-monotone piece-wise linear
curves between these two vertices, and at each crossing between two such
curves we introduce a cross-cap. The edge $j$ emanates from $(-1,n/2)$ to
$(0,\pi_{j}^{1})$, for each $k\leq d$ it passes through
$(k,\pi_{k}^{j})\in\mathbb{R}^{2}$, and finally it connects $(d,\pi_{j}^{d})$
to the terminal vertex at $(d+1,n/2)$. In the remaining of this article, we
often forget about the vertices $(-1,n/2)$ and $(d+1,n/2)$ in our
illustrations as they play no role, and we always assume that $\pi^{d}$ is the
identity (see Figure 5).

##  3 The counterexample

In this section, we provide a family of 2-vertex embedding schemes that do not
admit a perfect cross-cap drawing. Then we provide an explicit pseudo-
triangulation of $N_{5}$ (depicted in Figure 7) , disproving Conjecture 1.2.

Figure 7: A pseudo-triangulation of $N_{5}$ admitting no perfect cross-cap
drawing.

######  Remark 3.1.

If an embedding scheme $G$ has one positive and one negative block, then so
does its flipped version, therefore we do not need to account for the possible
flip in the proof of Theorem 1.3.

In order to prove Theorem 1.3, we rely on Lemmas 3.1 and 3.2.

######  Lemma 3.2.

Let $G$ be an embedding scheme that consists of a non-trivial positive block
$A$ and a non-trivial negative block $B$, then $g(G)=g(A)+g(B)-1$.

The proof follows directly from the Euler characteristic.

###### Proof.

Assume that the positive block has edges labelled $A=\\{e_{1},\ldots e_{k}\\}$
and the edges of the negative block are
$B=\\{\overline{e}_{k+1},\overline{e}_{k+2},\ldots\overline{e}_{k+l}\\}$.
Notice that $f(G)=f(A)+f(B)-1$, indeed the face $e_{1},e_{k}$ and the face
$\overline{e}_{k+1},\hat{e}_{k+l}$ are the outer faces of $A$ and $B$, and
they merge to become the face
$e_{1},\overline{e}_{k+1},e_{k},\overline{e}_{k+l}$. Hence by Euler’s formula
$eg(G)=eg(A)+eg(B)+1$. We know that $g_{A}=eg(A)+1$ and $g_{B}=eg(B)+1$. On
the other hand, a cycle in $G$ that contains one edge from $A$ and one edge
from $B$ is one-sided, therefore $G$ is a non-orientable, hence $eg(G)=g_{G}$.
All in all we can conclude

$g_{G}=eg(G)=eg(A)+eg(B)+1=g_{A}-1+g_{B}-1+1=g_{A}+g_{B}-1$

as claimed. ∎

We now have all the tools to prove Theorem 1.3, and refer to Figure 2 for an
example to help follow the proof.

###### Proof of Theorem 1.3.

Let $G$ be a concatenation of a positive block $A$ with frames $a_{1}$ and
$a_{2}$ and a negative block $B$ with frames $b_{1}$ and $b_{2}$. Let us
assume that $\phi$ is a perfect cross-cap drawing of $G$. From Lemma 2.2 we
derive that $a_{1}\cdot b_{1}$ and $a_{1}\cdot b_{2}$ are orienting curves,
hence by Lemma 2.5 each of them enters each cross-cap once. Lemma 2.3 implies
that $b_{1}\cdot b_{2}$ is separating. Therefore by Lemma 2.5, $b_{1}$ and
$b_{2}$ enter the same cross-caps and do not enter any cross-cap that $a_{1}$
enters. Similarly, $a_{1}\cdot a_{2}$ is separating and hence they enter the
same cross-caps and no cross-cap that $b_{1}$ and $b_{2}$ enter. Then $A$ is
drawn with $g_{A}$ cross-caps and $B$ is drawn with $g_{B}$ cross-caps that
are disjoint from the cross-caps that $A$ entered. But by Lemma 3.2 the non-
orientable genus of $G$ is $g_{A}+g_{B}-1$. Therefore, there are not enough
cross-caps available to draw both $A$ and $B$. This concludes. ∎

Corollary 1.4 follows at once as we can always add edges and vertices to a
scheme to triangulate it without adding loops nor changing its genus, and any
perfect cross-cap drawing of the triangulation restricts to a cross-cap
drawing of the scheme. We provide in Figure 7 an example of such a pseudo-
triangulation.

##  4 Topology of the reversal distance

In this section, we recall some well-known results from the genomics
rearrangements literature111The literature primarily deals with sorting
standard permutations, while here we are sorting cyclic permutations. In our
description, we directly translate their techniques to this cyclic setting.,
which we interpret in the language of embedding schemes (see also [9] for an
alternate topological interpretation of these arguments).

###  4.1 The Bafna-Pevzner inequality from Euler’s formula.

Let $\pi$ be a signed cyclic permutation, which, as explained in Section 2, we
think of as a 2-vertex embedding scheme, which requires $g(\pi)$ cross-caps to
be drawn. We can compute its number of faces, which we denote by $f(\pi)$ and
the number of elements in the permutation corresponds to the number of edges
in the scheme, which we denote by $e(\pi)$. Then Euler’s formula reads
$2-eg(\pi)=2-e(\pi)+f(\pi)$ which simplifies to $eg(\pi)=e(\pi)-f(\pi)$. By
Lemma 2.4, we thus have $d(\pi,id)\geq e(\pi)-f(\pi)$.

A very similar inequality was first discovered by Bafna and Pevzner [1,
Theorem 2] without reference to embeddings. Figure 8 shows an example where
the inequality is strict: the embedding scheme has Euler genus two, non-
orientable genus three and one can show that the signed permutation requires
four reversals to be sorted. However, as pictured on the right, it does admit
a perfect cross-cap drawing with three cross-caps. Necessarily, in that
example, the cross-caps can not be interpreted as reversals: this is apparent
here as they do not occur in a monotone order.

Figure 8: The embedding scheme depicted in this picture has non-orientable
genus 3 but requires four reversals (left). However, it admits a perfect
cross-cap drawing with three cross-caps (right).

The starting idea of the Hannenhalli-Pevzner (HP) algorithm is to identify
intervals in a signed permutation where applying a reversal is clearly making
progress. Given a signed cyclic permutation $\pi$, we call a pair of
consecutive integers $i$ and $i+1$ _reversible_ if they have opposite signs in
$\pi$ (this is called an _oriented pair_ in [3]). For a given reversible pair
there exist two reversals $\sigma,\sigma^{\prime}$ such that $i$ and $i+1$ are
homotopic in $\pi\cdot\sigma$ and in $\pi\cdot\sigma^{\prime}$. These two
reversals are equivalent in the sense that the two permutations that they
yield are flipped versions of each other. The following lemma follows from an
Euler characteristic argument.

######  Lemma 4.1.

If $i,i+1$ are a reversible pair in $\pi$ and $\sigma$ is a reversal that
turns them into homotopic curves in $\pi\cdot\sigma$, then
$eg(\pi\cdot\sigma)=eg(\pi)-1$.

###### Proof.

Since $e(\pi)=e(\pi\cdot\sigma)$, we need to show that
$f(\pi\cdot\sigma)=f(\pi)+1$. The edges $i$ and $i+1$ appear in some face $a$
in $\pi$. We claim that the faces of $\pi\cdot\sigma$ are the same as the
faces of $\pi$ except that $a$ is subdivided into the bigon $(i,i+1)$ and
another face which contains the edges of $a$ minus $i$ and $i+1$. Indeed every
other face is not disrupted by the reversal. This finishes the proof. ∎

###  4.2 The HP algorithm for reduced signed permutations

It is immediate to see that blocks do not contain reversible pairs of edges,
and thus non-trivial blocks form a natural obstruction to applying the
reversals described above. Given a reversible pair $(i,i+1)$ in the signed
permutation $\pi$, let $\sigma$ be a reversal that turns $i$ and $i+1$ into
homotopic edges. The _score_ of $(i,i+1)$ is the number of reversible pairs in
$\pi\cdot\sigma$.

#### HP algorithm:

While there is a reversible pair, reverse a pair of maximal score [2].

######  Theorem 4.2.

If a signed permutation $\pi$ is non-orientable and has no non-trivial blocks
then $d(\pi,id)=eg(\pi)$, and the HP algorithm gives a sequence of reversals
of this optimal length.

This theorem follows at once from the following lemma.

######  Lemma 4.3.

Let $\pi$ be a non-orientable signed permutation without non-trivial blocks,
$(i,i+1)$ be a reversible pair of maximal score, and $\sigma$ be a reversal
that makes $i$ and $i+1$ homotopic such that $\pi\cdot\sigma$ is not the
identity. Then $\pi\cdot\sigma$ is non-orientable and has no non-trivial
blocks.

###### Proof of Theorem 4.2.

By the previous lemma, if $\pi$ is non-orientable has no non-trivial block and
$\sigma$ is a reversal of maximum score, then $\pi\cdot\sigma$ is also non-
orientable and also has no non-trivial block. By induction,
$d(\pi\cdot\sigma,id)=e(\pi\cdot\sigma)-f(\pi\cdot\sigma)=eg(\pi\cdot\sigma)$.
Therefore, by Lemma 4.1, $eg(\pi)\leq d(\pi,id)$, and $d(\pi,id)\leq
d(\pi\cdot\sigma,id)+1=eg(\pi\cdot\sigma)+1=e(\pi)-f(\pi)=eg(\pi)$.∎

The proof of Lemma 4.3 is almost identical to that of [2, Theorem 10] but
first requires some additional definitions.

Two intervals $(i,j)$ and $(k,l)$ are called _interleaving_ in a cyclic
permutation, if we either have $\pi^{-1}(i)<\pi^{-1}(k)<\pi^{-1}(i+1)$ or
$\pi^{-1}(i)<\pi^{-1}(l)<\pi^{-1}(i+1)$.

#### Interleaving graph.

Given a permutation $\pi$ on $\\{1,\dots,n\\}$, Let $\pi^{*}$ be the
permutation of size $2n$ on elements $\\{i^{l},i^{r}\text{ for }1\leq i\leq
n\\}$ in which $\pi^{*}_{2k-1}=\pi_{i}^{l}$ and $\pi^{*}_{2k}=\pi_{i}^{r}$
when $\pi_{i}$ is positive and $\pi^{*}_{2k-1}=\pi_{i}^{r}$ and
$\pi^{*}_{2k}=\pi_{i}^{l}$ when $\pi_{i}$ is negative. We build the
_interleaving_ graph $I_{\pi}$ as follows:

  * •

The graph has $n$ vertices labelled by $(i,i+1)$ for $i$ modulo $n$. A vertex
$(i,i+1)$ is called _reversible_ if $(i,i+1)$ is a reversible pair, otherwise
it is called _non-reversible_. We denote a reversible pair by a white vertex
and a non-reversible pair by a black one.

  * •

Two vertices $(i,i+1)$ and $(j,j+1)$ are connected if the intervals
$(i^{r},i+1^{l})$ and $(j^{r},j+1^{l})$ are interleaving in $\pi^{*}$.

See Figure 9 for an example. A connected component in $I_{\pi}$ is _non-
trivial_ if it has more than one vertex and it is called _orientable_ if it
only contains non-reversible vertices.

######  Remark 4.4.

If $(i,i+1)$ are a homotopic pair in $\pi$ then the vertex $(i,i+1)$ is an
isolated vertex. A non-trivial block and the vertices in $I_{\pi}$ associated
to the pair of edges that belong to the block correspond to a non-trivial
orientable connected component in $I_{\pi}$. Note that the reverse is not true
and an orientable connected component does not always correspond to a non-
trivial block in the permutation.

######  Lemma 4.5.

Let $\pi$ be a signed permutation for which $I_{\pi}$ has a non-trivial
orientable connected component $U$. Then either $U$ corresponds to a non-
trivial block or $\pi$ is orientable.

###### Proof.

We say that an element $i$ belongs to $U$ if $(i,i+1)\in U$ or $(i-1,i)\in U$.
By orientability, all the elements belonging to $U$ have the same signature,
let us first assume that it is positive. Let us furthermore assume, for the
sake of contradiction, that $\pi$ is not orientable and that $U$ does not
correspond to a block. Since $\pi$ is not orientable, not every element has
positive signature, so there is at least one element that does not belong to
$U$. Let $a$ be an element belonging to $U$ such that $a-1$ does not belong to
$U$. Without loss of generality, we can fix an origin to the signed
permutation $\pi$ at $a-1$. Now let $b$ be an element that belongs to $U$ and
such that for any element $j$ that belongs to $U$, $a,j$ and $b$ appear in
this cyclic order in $\pi$. We claim that either $a-2=b$, or $a-2$ does not
appear between $a$ and $b$ in $\pi$. Indeed, if $a-2$ appears between $a$ and
$b$, then $(a-2^{r},a-1^{l})$ would interleave with one pair on a path between
$(a,a+1)$ and $(b,b\pm 1)$ in $U$, and thus $a-1$ would belong to $U$.
Therefore, either $a-2=b$ or $a-2$ does not belong to $U$. Inductively, none
of the elements that are not in $[a,b]$ lie between $[a,b]$ in $\pi$.
Similarly, all the elements within $[a,b]$ lie between $a$ and $b$ in $\pi$,
as otherwise the smallest one that does not, call it $k$, does not belong to
$U$, yet $(k-1^{r},k^{l})$ interleaves with a pair on a path between $(a,a+1)$
and $(b,b\pm 1)$ in $U$, contradicting the fact that $k$ is not in $U$. We
conclude that $a$ and $b$ are the frames of a block, which is non-trivial
since there is at least one pair in $U$. This is a contradiction. The case
where all the signatures in $U$ are negative follows from the fact that
flipping $\pi$ does not change its interleaving graph nor the orientability of
its components. ∎

When we apply a reversal on a reversible pair $(i,i+1)$, the effect on
$I_{\pi}$ is to complement the subgraph induced by the vertex $(i,i+1)$ and
its neighbors in $I_{\pi}$. Also if a vertex in this subgraph was reversible,
it gets non-reversible and vice versa. Indeed, let $(j,j+1)$ be a reversible
vertex connected to $(i,i+1)$. This means that the intervals $(j^{r},j+1^{l})$
and $(i^{r},i+1^{l})$ are interleaving. Without loss of generality let us
assume that $j^{r}$ is the element that belongs to the interval
$(i^{r},i+1^{l})$ and it is positive. Reversing the elements between
$(i,\pi_{\pi^{-1}(i+1)-1})$ makes $i$ and $i+1$ homotopic and isolates
$(i,i+1)$. Also it makes $j$ negative and therefore the pair $(j,j+1)$ is not
reversible anymore. Similarly it can be seen that if $(j,j+1)$ and $(k,k+1)$
are two neighbors of $(i,i+1)$ in $I_{\pi}$ and the intervals
$(j^{r},j+1^{l})$ and $(k^{r},k+1^{l})$ interleave, after applying the
reversal they stop being interleaved and therefore vertices $(j,j+1)$ and
$(k,k+1)$ are not connected anymore in the interleaving graph. This explains
the complementing of the induced subgraph. Figure 9 depicts the effect of
applying the reversal on the pair $(4,5)$.

Figure 9: Figure depicts a permutation $\pi$, its associated doubled
permutation $\pi^{*}$ and its interleaving graph $I_{\pi}$. At the bottom we
can see the effect of reversing elements $1,3,5$ on the interleaving graph;
this reversal makes $4$ and $5$ homotopic.

###### Proof of Lemma 4.3.

To prove the lemma, we first show that the number of non-trivial orientable
connected components in $I_{\pi\cdot\sigma}$ cannot be more than $I_{\pi}$.
Let us assume that this is the case and that by applying $\sigma$ we create
such a component $C$. In this case, we claim that the score of any pair
$(j,j+1)$ for which the corresponding vertex is in $C$, is higher than the
score of the pair $(i,i+1)$.

Denote by $\\#^{+}(i,i+1)$ (resp. $\\#^{-}(i,i+1)$) the number of reversible
(resp. non-reversible) pairs of edges adjacent edges to $(i,i+1)$ in
$I_{\pi}$. If $\pi$ has $k$ reversible pairs of edges, then the
score$(i,i+1)=k-\\#^{+}(i,i+1)+\\#^{-}(i,i+1)$.
Before applying the reversal, every non-reversible vertex that is connected to
$(i,i+1)$ has to be connected to $(j,j+1)$. This is because otherwise after
applying the reversal this vertex will be a reversible vertex connected to
$(j,j+1)$ and therefore belonging to $C$ which is not possible. This implies
that $\\#^{-}(i,i+1)\leq\\#^{-}(j,j+1)$.
Before applying the reversal, every reversible vertex $(t,t+1)$ that is
connected to $(j,j+1)$ has to be connected to $(i,i+1)$. This is because if
$(t,t+1)$ is not connected to $(i,i+1)$, after applying the reversal this
vertex remains connected to $(j,j+1)$ without changing its reversibility. This
means that $(t,t+1)$ is a reversible pair that belongs to $C$ which is not
possible. This implies that $\\#^{+}(j,j+1)\leq\\#^{+}(i,i+1)$. The equality
does not happen since the component $C$ has more than one vertex and a vertex
in $C$ to which $(j,j+1)$ is connected after the reversal, is a reversible
vertex that used to be connected to $(i,i+1)$ but not to $(j,j+1)$. Therefore
$\\#^{+}(j,j+1)<\\#^{+}(i,i+1)$

We have that
$\text{score}(i,i+1)=k-\\#^{+}(i,i+1)+\\#^{-}(i,i+1)<k-\\#^{+}(j,j+1)+\\#^{-}(j,j+1)=\text{score}(j,j+1)$
which contradicts our assumption. This finishes the proof of the claim.

Now, the assumptions of Lemma 4.3 imply that there are no non-trivial
orientable connected components in $I_{\pi}$. Thus there are also none in
$I_{\pi\cdot\sigma}$. A non-trivial block or the entire scheme being
orientable but not the identity would induce such a non-trivial orientable
connected component. This concludes the proof.∎

##  5 Perfect drawings for most 2-vertex graph embeddings

We say that a cross-cap drawing is _fantastic_ if it is perfect and every edge
enters at least one cross-cap.

######  Lemma 5.1.

Every reduced loopless 2-vertex graph embedding scheme that is different from
$(1)$, $(1,\overline{2})$ or $(1,\overline{3},\overline{4},2)$ admits a
fantastic cross-cap drawing.

The proof is based on an induction and an exhaustive analysis of all the
loopless $2$-vertex embedding schemes of genus $2$ and $3$, as pictured in
Figure 10. We first prove the following lemma.

######  Lemma 5.2.

Let $G$ be an orientable scheme of non-orientable genus $g(G)$ that has no
non-trivial block. We can add an edge to this embedding scheme such that we
obtain a non-orientable scheme of genus $g(G)$ without any block.

###### Proof.

Let us assume that the signatures of the edges are positive. Choose an edge
$f$. Add a negative edge $e$ consecutive to $f$, such that in the cyclic
permutation of one vertex we see $ef$ and in the other vertex we see $fe$. Let
us call the new embedding scheme by $G^{\prime}$. The scheme $G^{\prime}$ is
non-orientable. Since $G$ is orientable, we know that $g(G)=eg(G)+1$. Since
$e(G^{\prime})=e(G)+1$, it is enough to show that $f(G^{\prime})=f(G)$. By
looking at the face cycles of both schemes, we can see that all face cycles
are intact except a face $(i,f,j,\dots)$ in $G$ that is turned to a face cycle
$(i,e,f,e,j,\dots)$ ($i$ and $j$ are two adjacent edges to $f$ in the cyclic
permutation of the vertices). Since the edge $e$ has an opposite signature
compared to the edges of $G$, $e$ cannot create a block in $G^{\prime}$. The
proof for the case where all the edges of $G$ are negative can be obtained by
flipping. This finishes the proof. ∎

###### Proof of Lemma 5.1.

Let $\pi$ be the signed permutation associated to the embedding scheme. If the
embedding scheme is orientable, we first add one edge without changing its
genus to make it non-orientable while keeping it reduced (this is possible by
Lemma 5.2). Now, since it is reduced and non-orientable, by Theorem 4.2, the
HP algorithm provides a path in the reversal graph
$\\{\pi=\pi^{1},\pi^{2},\ldots\pi^{g}=id\\}$, where $g$ is the non-orientable
genus of $\pi$. We distinguish cases depending on the value of $g$.

If $g\geq 3$, we consider the sub-path $\\{\pi^{1},\pi^{2},\ldots,\pi^{k}\\}$,
with $g-k=3$ and realize this sub-path as a cross-cap drawing $\phi$ as
described in Section 2. Notice that if there exists a fantastic cross-cap
drawing $\phi^{\prime}$ for $\pi^{k}$, we can concatenate $\phi$ with
$\phi^{\prime}$ to obtain a fantastic cross-cap drawing for $\pi$. Now
$\pi^{k}$ is a reduced signed permutation of non-orientable genus $3$. The
proof then proceeds via an exhaustive case analysis. Without loss of
generality, we can assume that

  * •

There is no non-trivial block in $\pi^{k}$ since that is preserved by the HP
algorithm.

  * •

There are no homotopic edges since, for any collection of homotopic edges, one
can remove all but one and add them in the end identical to the remaining one.

  * •

There is at least one edge of signature $-1$ and one edge of signature $+1$ in
$\pi^{k}$. Otherwise, $\pi^{k}$ is orientable, which is impossible since by
Theorem 4.2, the HP algorithm preserves non-orientability.

  * •

$\pi^{k}$ is maximal while preserving these three properties. Indeed,
otherwise, we can add edges, draw the resulting scheme and remove these
superfluous edges at the end.

With these simplifying assumptions at our disposal, we can exhaustively
enumerate all the genus $3$ embedding schemes matching these assumptions. The
numbers are small enough that this can be done by hand, we ran a computer
search for safety. One obtains that all the maximal schemes have their all
faces of degree $4$, and thus have six edges: for all reduced schemes with
some faces of degree higher than four, one can always add an edge within a
face while keeping the fact that it is reduced. Then, there are exactly eight
loopless $2$-vertex embedding schemes matching our assumptions, their signed
permutations are: $(1,\overline{6},5,\overline{4},3,\overline{2})$,
$(1,\overline{6},\overline{3},5,4,\overline{2})$,
$(1,\overline{3},\overline{6},5,\overline{4},2)$,
$(1,5,\overline{3},\overline{6},4,2)$, $(1,\overline{4},6,3,\overline{5},2)$,
$(1,\overline{6},3,\overline{4},5,\overline{2})$,
$(1,\overline{4},6,\overline{2},5,\overline{3})$, and
$(1,\overline{4},\overline{6},\overline{2},5,3)$. Fantastic drawings of each
of them are provided in Figure 10.

If $g=2$, there are exactly three reduced schemes:
$(1,\overline{3},\overline{4},2)$, $(1,\overline{2},3,\overline{4})$ and
$(1,3,\overline{2})$. Fantastic drawings of the second and third case (or
rather its flipped version) are provided in Figure 10.

If $g=1$, there is a single reduced scheme: $(1,\overline{2})$.

If $g=0$, there is a single reduced scheme: $(1)$. ∎

Figure 10: Fantastic drawings of genus-$2$ and genus-$3$ embedding schemes
(these are cylindrical drawings: the top is identified to the bottom).

In order to prove Theorem 1.5, our strategy is to first look for a fantastic
cross-cap drawing for the reduced graph of an embedding scheme. Then, to
obtain a drawing for the initial graph, we need to bring back the blocks that
we replaced and extend the drawing to the edges of the block. This is achieved
via the following blowing-up operation.

#### Blowing up a cross-cap.

Let $\phi$ be a fantastic drawing for $G$. By the definition of fantastic
drawing, any reduced edge enters at least one cross-cap. Let $e$ be a reduced
edge that corresponded to a block $X$ with frames $a$ and $b$ and let
$\mathfrak{c}$ be a cross-cap in $\phi$ that $e$ enters. By Lemma 2.4, $X$
needs an odd number of cross-caps to be drawn, exactly $eg(X)+1$. We replace
$\mathfrak{c}$ by $eg(X)+1$ cross-caps and we draw the frames of $X$, $a$ and
$b$ as follows. We draw $a$ following $e$ thoroughly. To draw $b$ we follow
$e$ except that we make $b$ enter the new $eg(X)+1$ cross-caps in the reversed
order that $a$ enters. All the other edges outside of $X$ that were entering
$e$ are now drawn in the same way as $a$ or $b$ depending on how they were
crossing $e$ at $\mathfrak{c}$. Finally we remove $e$ (see Figure 11).

Figure 11: Blowing up a cross-cap to draw the frames of a block

Repeatedly blowing up a drawing of a reduced permutation $\pi|$ yields a
drawing for all edges of $\pi$ except for the edges inside the blocks. The
following lemma shows that these edges can be added in this cross-cap drawing.

######  Lemma 5.3.

Let $\pi$ be a signed permutation on $n$ elements such that all the elements
form a non-trivial minimal negative block. The associated embedding scheme
admits a perfect cross-cap drawing in which the frames of $\pi$, i.e. elements
$1$ and $n$, enter all the cross-caps but in opposite order.

###### Proof.

Let us denote by $g(\pi)=eg(\pi)+1$ the non-orientable genus of the associated
embedding scheme. We know that $\pi_{1}=\overline{n}$ and
$\pi_{n}=\overline{1}$. Let us define $\pi^{\prime}$ from $\pi$ by replacing
$\overline{1}$ by $n+1$. The following lemma is proved using the HP algorithm
and Theorem 4.2.

######  Lemma 5.4.

The optimal number of reversals to go from $\pi^{\prime}$ to the permutation
$(2,3,\dots,n+1)$ is $g(\pi^{\prime})=g(\pi)$. There exists a sequence of such
reversals such that no reversal is applied on the element $n+1$.

###### Proof.

Note that the associated embedding scheme to $\pi^{\prime}$ is a non-
orientable scheme and therefore $g(\pi^{\prime})=eg(\pi^{\prime})$. The number
of edges in $\pi$ and $\pi^{\prime}$ are equal therefore to show that
$eg(\pi^{\prime})=g(\pi)=eg(\pi)+1$, it is enough to show that
$f(\pi^{\prime})=f(\pi)-1$. Let
$\pi=(\overline{n},\dots,\overline{2},\dots,\overline{j},\overline{1})$. Then
$\pi^{\prime}=(\overline{n},\dots,\overline{2},\dots,\overline{j},n+1)$. $\pi$
has a face $f_{1}=(0,n)$ and $f_{2}=(2,n,j,\dots)$. Replacing $-1$ with $n+1$,
the faces $f_{1}$ and $f_{2}$ merge to a single face $f=(2,n+1,n,n+1,j,\dots)$
in $\pi^{\prime}$ (see Figure 12). The other faces in $\pi^{\prime}$ are the
same as the faces in $\pi$ other than $f_{1}$ and $f_{2}$. This implies that
$\pi^{\prime}$ has one face less than $\pi$.

Figure 12: Faces of $\pi^{\prime}$ (left) and $\pi$ (right).

Furthermore, $\pi^{\prime}$ does not contain any block and therefore it is
reduced. It is non-orientable by construction. Having a reversible pair
$(i,i+1)$, there are two reversals that make $i$ and $i+1$ homotopic. By
running the HP-algorithm on $\pi^{\prime}$ and choosing the reversal at each
step that does not reverse $n+1$ we obtain a desired sequence of reversals.
This finishes the proof of the lemma. ∎

Now, the sequence of reversals of Lemma 5.4 gives us a cross-cap drawing for
$\pi$. By Lemma 2.2, the edges $n$ and $n+1$ form an orienting cycle, and thus
together they have to enter all the $g(\pi^{\prime})$ cross-caps exactly once.
We know that the edge $n+1$ does not enter any cross-cap in this drawing which
implies that $n$ enters all the cross-caps exactly once. We can obtain a
cross-cap drawing for $\pi$ from this drawing for $\pi^{\prime}$ by drawing
$1$ entering the cross-caps that $n$ enters with the opposite order as
depicted in Figure 13. ∎

Figure 13: From a cross-cap drawing of $\pi^{\prime}$ to a cross-cap drawing
of $\pi$.

We are now finally ready to prove Theorem 1.5.

###### Proof of Theorem 1.5.

Let $G$ denote an embedding scheme for a loopless 2-vertex graph of non-
orientable genus $g$. We denote by $G^{\prime}$ the reduced scheme, i.e., the
scheme obtained after recursively replacing minimal blocks with a curve of the
corresponding sidedness. If $G^{\prime}$ is exactly one of the two graphs
depicted in Figure 3, the conclusion of the theorem holds. If $G^{\prime}$
consists of a single edge, up to flipping $G$ we can assume that this edge has
negative signature. Then this edge can be drawn in the natural way with a
single cross-cap. In all the other cases, by Lemma 5.1, $G^{\prime}$ admits a
fantastic cross-cap drawing.

In order to finish the proof, we explain how to inductively put back minimal
blocks of $G$ in the place of the corresponding reduced edge in $G^{\prime}$.
If $A$ is such a minimal block and is negative and we denote by $e$ the
corresponding reduced edge, $e$ is one-sided and thus goes through at least
one cross-cap. We blow up this cross-cap, replacing it by exactly the odd
number of cross-caps required to draw $A$. By Lemma 5.3, since $A$ is minimal,
it is reduced and thus it can be drawn using these blown-up cross-caps, in
such a way that the frames of the block enter the blown-up cross-caps in
opposite orders. This process is pictured in Figure 13. If $A$ is a positive
minimal block and $e$ is the corresponding reduced edge, since the drawing of
$G^{\prime}$ is fantastic, we know that $e$ enters at least two cross-caps. We
first make the entirety of $A$ enter the first of these cross-caps. Thus,
there remains to draw the flipped version of $A$, which is now a negative
block. This is achieved as before by blowing-up the second cross-cap, and
appealing to Lemma 5.3 to draw the negative block within the space bordered by
the two frames.

This process shows how to obtain a perfect cross-cap drawing of $G$ from a
fantastic cross-cap drawing of the reduced graph $G^{\prime}$, concluding the
proof. ∎

#### Acknowledgements.

We are very grateful to anonymous reviewers for helpful comments.

## References

  * [1] Vineet Bafna and Pavel A Pevzner.  Genome rearrangements and sorting by reversals.  SIAM Journal on computing, 25(2):272–289, 1996.  doi:10.1109/SFCS.1993.366872.
  * [2] Anne Bergeron.  A very elementary presentation of the Hannenhalli-Pevzner theory.  In Annual Symposium on Combinatorial Pattern Matching, pages 106–117. Springer, 2001.  doi:10.1016/j.dam.2004.04.010.
  * [3] Anne Bergeron, Julia Mixtacki, and Jens Stoye.  Reversal distance without hurdles and fortresses.  In Combinatorial Pattern Matching: 15th Annual Symposium, CPM 2004, Istanbul, Turkey, July 5-7, 2004. Proceedings 15, pages 388–399. Springer, 2004.  doi:10.1007/978-3-540-27801-6_29.
  * [4] Phillip Compeau and Pavel Pevzner.  Bioinformatics algorithms: an active learning approach.  Active Learning Publishers La Jolla, California, 2015.
  * [5] Christian A Duncan, Michael T Goodrich, and Stephen G Kobourov.  Planar drawings of higher-genus graphs.  Journal of Graph Algorithms and Applications, 15(1):7–32, 2011\.  doi:10.1007/978-3-642-11805-0_7.
  * [6] Guillaume Fertin, Anthony Labarre, Irena Rusu, Stéphane Vialette, and Eric Tannier.  Combinatorics of genome rearrangements.  MIT press, 2009.
  * [7] Niloufar Fuladi, Alfredo Hubard, and Arnaud de Mesmay.  Short topological decompositions of non-orientable surfaces.  In 38th International Symposium on Computational Geometry (SoCG 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.SoCG.2022.41.
  * [8] Sridhar Hannenhalli and Pavel A Pevzner.  Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals.  Journal of the ACM (JACM), 46(1):1–27, 1999.  doi:10.1145/300515.300516.
  * [9] Fenix WD Huang and Christian M Reidys.  A topological framework for signed permutations.  Discrete Mathematics, 340(9):2161–2182, 2017.  doi:10.1016/j.disc.2017.03.019.
  * [10] Francis Lazarus, Michel Pocchiola, Gert Vegter, and Anne Verroust.  Computing a canonical polygonal schema of an orientable triangulated surface.  In Proceedings of the seventeenth annual symposium on Computational geometry, pages 80–89, 2001.  doi:10.1145/378583.378630.
  * [11] Bojan Mohar.  The genus crossing number.  ARS Mathematica Contemporanea, 2(2):157–162, 2009.  doi:10.26493/1855-3974.21.157.
  * [12] Bojan Mohar and Carsten Thomassen.  Graphs on surfaces, volume 10.  JHU press, 2001.
  * [13] János Pach and Géza Tóth.  Degenerate crossing numbers.  Discrete & Computational Geometry, 41(3):376–384, 2009.  doi:10.1007/s00454-009-9141-y.
  * [14] Marcus Schaefer and Daniel Štefankovič.  The degenerate crossing number and higher-genus embeddings.  Journal of Graph Algorithms and Applications, 26(1):35–58, 2022\.  doi:10.7155/jgaa.00580.


# Computable Model Discovery and High-Level-Programming Approximations to
Algorithmic Complexity

Vladimir Lemus111The authors were supported by conacyt scholarships while
working on this project. They also want to thank Luis Felipe Benítez Lluis for
his help with the project. Eduardo Acuña222The authors were supported by
conacyt scholarships while working on this project. They also want to thank
Luis Felipe Benítez Lluis for his help with the project. Víctor Zamora333The
authors were supported by conacyt scholarships while working on this project.
They also want to thank Luis Felipe Benítez Lluis for his help with the
project. Francisco Hernandez-Quiroz444The author was supported by a sabbatical
grant (dgapa-unam) while working on this project. Hector Zenil555Corresponding
author<EMAIL_ADDRESS>Posgrado en Ciencia e Ingenieria de la
Computacion, UNAM, C.U., 04510, CDMX, Mexico  Facultad de Ciencias, UNAM,
C.U., 04510, CDMX, Mexico  Oxford Immune Algorithmics, RG1 3EU, Reading, UK
Algorithmic Dynamics Lab, Karolinska Institute, 171 77, Stockholm, Sweden
Alan Turing Institute, British Library, NW1 2DB, London, UK  Algorithmic
Nature Group, LABORES, 76005, Paris, France

###### Abstract

Motivated by algorithmic information theory, the problem of program discovery
can help find candidates of underlying generative mechanisms of natural and
artificial phenomena. The uncomputability of such inverse problem, however,
significantly restricts a wider application of exhaustive methods. Here we
present a proof of concept of an approach based on IMP, a high-level
imperative programming language. Its main advantage is that conceptually
complex computational routines are more succinctly expressed, unlike lower-
level models such as Turing machines or cellular automata. We investigate if a
more expressive higher-level programming language can be more efficient at
generating approximations to algorithmic complexity of recursive functions,
often of mathematical interest.

###### keywords:

Kolmogorov-Chaitin complexity, Algorithmic Information Theory, algorithmic
randomness, generative model generation, IMP.

##  1 Introduction

Since first proposed as a measure of complexity [12], approximations to, or
measures inspired by, Kolmogorov-Chaitin or algorithmic complexity, have found
many applications [13]. But at its core, as an semi-computable measure, it can
only be applied by indirect methods such as computable weaker versions based
on statistical lossless compressibility [13, 7] or computationally expensive
approximations [18, 19]. Statistical compressibility is limited to what
entropic measures can find not beyond trivial regularities and redundancies
without resort to uncomputability [22]. Alternative approximations by means of
exhaustive searches are also very expensive [15, 20] and are limited to small
programs. For very small Turing machines this can be avoided through clever
tricks that cannot be expanded to larger machines [15] and often produce the
kind of programs that humans would not find very interesting such as the ones
generating highly recursive objects such as arithmetic or geometric
progressions that mathematicians find of high interest [8]. This kind of
approach has inspired a whole line of research into computable models [24] for
causal and knowledge discovery [20, 21].

In a seminal paper [1], Calude and Stay explored non-terminating programs from
a probabilistic viewpoint. In further papers [2, 3], they also proposed
techniques that can be applied to estimate the probability that a program will
not halt after certain execution time.

This paper builds on Calude’s and other people’s work in order to combine
exhaustive exploration of programs with an estimation of their non-halting
probability to produce approximations of Kolmogorov-Chaitin complexity. We do
this using a high-level programming language. IMP [17] is used to investigate
if a more expressive and efficient higher-level programming language can
generate faster approximations to the algorithmic complexity of recursive
functions, often of mathematical interest (e.g. short descriptions for
arithmetic sequences).

Assuming optimality, we systematically generated all programs in the language
IMP up to certain length and execute them in a controlled environment. We
registered their output to find the smallest program to produce a given
string, establishing its Kolmogorov-Chaitin complexity under this model. In
order to deal with non-halting programs we estimated their halting probability
and used it to execute those programs to ascertain whether they would stop
within an acceptable threshold.

##  2 A Simple Imperative Programming Language

For our programming language we decided on IMP, a simple textbook example of
an imperative programming language [17] that is Turing-complete. The syntax of
IMP is given by the grammar in figure 1.

$\displaystyle P$ $\displaystyle\Coloneqq\mathop{\mathtt{skip}}\mid
X\mathop{\mbox{\tt:=}}A\mid\mbox{\tt(}P\mathop{\mbox{\tt;}}P\mbox{\tt)}\mid\mbox{\tt(}\mathop{\mathtt{if}}B\mathop{\mathtt{then}}P\mathop{\mathtt{else}}P\mbox{\tt)}\mid\mbox{\tt(}\mathop{\mathtt{while}}B\mathop{\mathtt{do}}P\mbox{\tt)}$
$\displaystyle A$ $\displaystyle\Coloneqq N\mid
X\mid\mbox{\tt(}A\mathrel{\mbox{\tt+}}A\mbox{\tt)}\mid\mbox{\tt(}A\mathrel{\mbox{\tt-}}A\mbox{\tt)}\mid\mbox{\tt(}A\mathrel{\mbox{\tt*}}A\mbox{\tt)}$
$\displaystyle B$
$\displaystyle\Coloneqq\mathtt{true}\mid\mathtt{false}\mid\mbox{\tt(}A\mathrel{\mbox{\tt=}}A\mbox{\tt)}\mid\mbox{\tt(}A\mathrel{\mbox{\tt<}}A\mbox{\tt)}\mid\neg
B\mid\mbox{\tt(}B\vee B\mbox{\tt)}\mid\mbox{\tt(}B\wedge B\mbox{\tt)}$
$\displaystyle X$ $\displaystyle\Coloneqq\mathtt{x}\mbox{\tt[}N\mbox{\tt]}$
$\displaystyle N$ $\displaystyle\Coloneqq\mathtt{0}\mid C$ $\displaystyle C$
$\displaystyle\Coloneqq\mathtt{1}S\mid\mathtt{2}S\mid\dots\mid\mathtt{9}S$
$\displaystyle S$
$\displaystyle\Coloneqq\mathtt{0}S\mid\mathtt{1}S\mid\mathtt{2}S\mid\dots\mid\mathtt{9}S\mid\epsilon$
Figure 1: IMP language grammar in Backus-Naur form

One can assume IMP has a straightforward structural operational semantics
[14]. Registers of the type $x[N]$ hold natural numbers as possible values.
But we are interested instead in single binary strings as the output of
programs. We adopt the following convention to convert the values in the
registers used by a program into binary strings by a two-step mapping:

  1. 1.

For each register, we map its contents to a binary string according to the
canonical ordering of strings (strings are first sorted by length and then
ordered lexicographically).

  2. 2.

We take the concatenation of all the registers’ strings to be the program’s
output. In other words, a program’s output is computed by:

$\operatorname*{\scalerel*{+}{\sum}}_{n=0}^{\infty}f(x[n])$

where $f(x[n])$ is the function that transforms $x[n]$ into a binary string.

For step 1, we can use the very efficient algorithm 1. This algorithm can be
derived from the simple observation that strings of $0$s always correspond to
numbers of the form $2^{n}-1$ and vice versa. This is because the first string
of $0$s corresponds to the number $1$ and there are always $2^{n}$ strings of
size $n$. So, if the string corresponding to the number $2^{n}-1$ is the
string of $n$ $0$s, then the string of $n+1$ $0$s must correspond to
$2^{n}-1+2^{n}=2^{n+1}-1$.

Input: A natural number $n$

Output: The $n$th string in canonical order

$l\leftarrow\lfloor\log_{2}(n+1)\rfloor$;

$c\leftarrow n-(2^{l}-1)$;

return _$c$ in $l$ bits_

Algorithm 1 Algorithm for obtaining the $n$-th string in canonical order.

Step 2 involves concatenating the strings in all registers. Since registers
are initialised as $0$ and $0$ is mapped to the empty string, the
concatenation will be finite, and will only involve those registers which were
modified by a given program.

For a small example of how we compute a program’s output, consider the
following program:

(x[0] | := | 2;
---|---|---
(x[1] | := | 1;
x[2] | := | 3))

At the end of the program’s execution, register $0$ contains $2$, register $1$
contains $1$, register $2$ contains $3$, and the rest of the registers all
contain $0$.

To compute the program’s output, each register is converted to a string. So
register $0$’s $2$ is converted to $1$, register $1$ is converted to $0$ and
register $2$ is converted to $00$. The rest of the registers are converted to
$\epsilon$. Therefore the program’s output is:

$1+0+00+\operatorname*{\scalerel*{+}{\sum}}_{i=3}^{\infty}\epsilon\ =1000$

As Kolmogorov-Chaitin complexity is concerned with the smallest program
producing a certain output, we need a length metric. We will use the terminal
symbols of the language such as skip, while, etc., the decimal digits, and so
on to measure the length of a program.

A quick glance at our grammar shows that the insertion of parentheses after
each construct guarantees the unicity of the syntax trees. It also yields
prefix-free programs, which will be useful in a future extension of this
project.

##  3 Taming the Halting Problem

###  3.1 Workarounds for the Halting problem

The Halting problem is the main reason why Kolmogorov-Chaitin’s complexity is
semi-computable. In order to know whether a certain program will output a
given string at the end of its execution, we need to know whether the program
will halt at all. But this is the paradoxical nature of an uncomputable
problem [16].

In [15], the authors applied reduction techniques for Turing machines with 5
states and 2 symbols, including setting a time limit to run the machines, and
were able to analyse the Kolmogorov-Chaitin complexity of a relatively large
set of strings.

A small programming language, known as Brainfuck (BF), has also been used to
show an empirical approximation [6] to Kolmogorov-Chaitin complexity, as well
as in a first attempt to estimate a theoretical error measure for such
approximations [11].

The main idea behind the theoretical model of [11] is to trade strict
algorithmic solutions for approximate solutions. In other words, a value is
considered to yield a solution within a particular range of confidence. The
central idea is to pass from the worst case scenario of non-halting to an
average case. As a program either halts or loops forever, there is no such
thing as average halting in the strict sense, but hard instances of the
halting problem are rarely encountered in practice, according to empirical
observations provided by Köhler, Schindelhauer and Ziegler (although this
depends on the particular encoding of the problem).

Here we are using a completely different method based on the theoretical
results of Calude and Stay [1]. Their results hold for any universal Turing
machine and posit an _a priori_ probability distribution over all running
times. The probability space in this case is extended to both program lengths
and runtimes, with time and programs uniformly distributed, in contrast to a
previous approach by Chaitin based upon a probability space just over program
length [5].

The central hypothesis is that long runtimes are in effect rare, and as such
they tend to zero in all probability distributions. A method to decide when to
stop a running program could be implemented by using an auxiliary Turing
machine running a probabilistic _anytime_ algorithm [9]. Runtimes for halting
programs are algorithmically non-random, which means they can be generated by
a machine with a small input, in this case the auxiliary Turing machine.

Calude and Dumitrescu [2] have further proved that it is possible to apply the
above method to approximate a runtime limit for the overwhelming majority of
halting programs. This limit depends solely on the machine codification and it
is independent of size and number of programs analysed. Their method produces
two intrinsically connected viewpoints, one probabilistic and the other
statistical [3].

Instead of proposing an _a priori_ probability distribution, given that (a)
long runtimes imply that the halting probability tends to zero and that (2)
halting time values are algorithmically non-random, we are able to build a
model for the halting probability based on running times of a finite set of
programs executed on a universal Turing machine. In its turn, an upper bound
for halting times can be estimated.

To calculate a limit for running times, the cumulative distribution function
(CDF) and a $(1-\epsilon)$-quantile is used. Beyond the
$(1-\epsilon)$-quantile value there is the upper $\epsilon$-tail in which the
halting probability is negligible, so these values can be used as a first
qualitative measure for our approximation. For a program $x$ running on the
machine $U$, if the execution has not halted after the above-mentioned
quantile value, we declare that the program will not halt, even if there are a
few programs that still halt beyond this limit.

###  3.2 Decision error, precision and confidence parameters

Thus far we have a probabilistic device proposing that some programs under a
certain optimal machine $U$ may not halt according to a value
$\epsilon\in(0,1)$, the decision error. Achieving this result requires a
probability distribution, indirectly based on the CDF and the quantile, and a
random variable over time [3]

$RT=RT_{U}:dom(U)\rightarrow T_{U},$ (1)

where $dom(U)$ is the set of all the halting programs under $U$.

Now the idea is to approximate the distribution by a long sequence of times.
For this reason an Empirical Cumulative Distribution Function is defined as:

$ECDF_{RT,N}((RT_{1}(\mathbf{x}),...,RT(\mathbf{x}));t)=\frac{\\#\\{1\leq
i\leq N:RT_{i}(\mathbf{x})\leq t\\}}{N},$ (2)

with an $N$-dimensional _time sampling space_ [3]. Working with these values
and using Hoeffding’s inequality [10], two parameters are given: (a) the
precision parameter $\lambda$, with $0<\lambda<\epsilon$, and (b) the
confidence parameter $\delta$, with $1-\delta\in(0,1)$. The first one is a
bound for the approximation to the CDF by the ECDF; the second one is a
confidence level, an index of how good our sampling is.

Having in hand three rational values that can be fine-tuned according to
whatever levels of error, precision and confidence are desired in an
approximation, a sampling size $N$ can be calculated [3]:

$N\geq N(\lambda,\delta)=\left\lceil\frac{1}{2\lambda^{2}}\cdot
ln\frac{1}{\delta}\right\rceil,$ (3)

Sampling $N$ independent halting programs in this manner and obtaining their
running times are the first steps. Thereafter the times can be sorted in
increasing order. The maximum time the sampled programs run until halting will
be the threshold $\mathbf{T}$. Any program that has not stopped by time $t\geq
T$ will be considered to never halt, with an error equal to $\epsilon$.

Two more approaches exist to provide a threshold time $\mathbf{T}$. When it is
too hard to sample exactly $N(\lambda,\delta)$ halting programs, it is easier
to find an affordable sample of size $\tilde{N}$. Two values can be given,
$\epsilon,\lambda\in(0,1)$ with $\lambda<\epsilon$, and the third one can be
obtained by:

$\delta(\tilde{N},\lambda)\geq exp(-2\tilde{N}\cdot\lambda^{2}).$ (4)

The second approach is as follows: if neither a dynamic nor an affordable
sample size is possible, an upper bound for time $\mathbf{T}$ can be set as an
initial parameter, adding $\epsilon$ and $\lambda$ with similar properties as
in the last case. A bigger sample of programs is used to obtain
$dom(\mathbf{U})$, that is, all the programs halting in a time $t<\mathbf{T}$.
Afterwards the size of the set $N(T)$ is calculated using the values
$\epsilon$, $\lambda$ and $\tilde{N}=N(T)$ as input for the second approach.
Both ways may entail a decrease in the confidence level.

$\epsilon$ | $\lambda<\epsilon$ | $\delta$ | $N(\lambda,\delta)$
---|---|---|---
$0.01$ | $0.009$ | $0.01$ | $28\,427$
$0.01$ | $0.001$ | $0.01$ | $2\,302\,586$
$0.01$ | $0.001$ | $0.001$ | $3\,453\,878$
$0.001$ | $0.0005$ | $0.001$ | $13\,815\,511$
Table 1: Sampling set size $N(\lambda,\delta)$ calculated for different
$\epsilon$, $\lambda$ and $\delta$ values.

The sampling size may not be directly dependent on $\epsilon$, our main error
value, but it is a bound for the precision parameter $\lambda$. Very
optimistic values can be proposed for $\epsilon$, $\lambda$ and $\delta$ to
obtain the size of the sampling set. The table 1 shows some values obtained
with equation 3.

###  3.3 Generating programs sorted by length

Once we calculated a time limit for the execution of programs of length 9 or
less, we executed _all_ of them and observed their output (or gave up on them
if the execution took longer than the estimated threshold for halting). But
the systematic _generation_ of all programs up to a certain length is not an
easy task. In a future paper, we will cover all the technicalities involved,
which have to do mainly with the combinatorial explosion of programs produced
by the grammar. Here we simply present an overview.

The space of programs is modelled as an enumeration, mapping non-negative
integers called positions to abstract syntax trees corresponding to valid
programs, such that every position is mapped to only one program and every
valid program is mapped to only one position.

The enumeration used for this paper consists of all IMP programs sorted first
by their length and then lexicographically. This enumeration is built in
stages.

Starting from the context-free grammar of the language, a base enumeration is
constructed where positions are mapped to programs based solely on the
production rules of the grammar. This is done by breaking apart a position $k$
as the syntax tree of a program is built from top to bottom. The position
determines what kind of tree must be constructed and in turn the kind of tree
determines how the position must be broken apart into the positions
corresponding to each of its children. This enumeration satisfies the property
that given programs $p$ and $q$ at positions $i$ and $j$ respectively, if $q$
is a subprogram of $p$, then $j<i$.

For any reasonable measure for the length of programs, the length of a program
is strictly greater than the length of any of its subprograms, however the
aforementioned property isn’t strong enough to guarantee that if $q$ is
smaller than $p$ and $q$ isn’t a subprogram of $p$ then $j<i$, which is one of
main goals in constructing an enumeration sorted by length.

A simple metric to measure the length of programs is defined. The chosen
metric counts the number of nodes in the syntax tree, and considers numbers
with $d$ digits as constructs of length $d$.

Using the base enumeration and the length metric, a counting function is
defined which maps non-negative integers $\ell$ to the number of programs of
length $\ell$. The metric informs the way a particular length can be
partitioned for different kinds of programs, while the base enumeration works
as a blueprint for how to navigate the program space. Table 2 shows the
relationship between program length and number of programs in the IMP
language, along with the cumulative sum of these counts.

| Count
---|---
Length | Individual | Accumulated
$0$ | $0$ | $0$
$1$ | $1$ | $1$
$2$ | $0$ | $1$
$3$ | $3$ | $4$
$4$ | $104$ | $108$
$5$ | $2124$ | $2232$
$6$ | $35\,770$ | $38\,002$
$7$ | $546\,611$ | $584\,613$
$8$ | $7\,991\,176$ | $8\,575\,789$
$9$ | $114\,513\,832$ | $123\,089\,621$
$10$ | $1\,631\,934\,090$ | $1\,755\,023\,711$
$11$ | $23\,318\,957\,744$ | $25\,073\,981\,455$
$12$ | $335\,696\,750\,370$ | $360\,770\,731\,825$
Table 2: Number of IMP programs by length.

The base enumeration and the counting function are used to build enumerations
of programs for a given length, called fixed-length enumerations. If $c$ is
the number of programs of length $\ell$, the corresponding fixed-length
enumeration, or $\ell$-length enumeration, maps positions smaller than $c$ to
all programs of length $\ell$. Fixed-length enumerations are finite, given
that the number of programs of a fixed length is finite.

Finally, the canonically sorted enumeration is built by considering the fixed-
length enumeration from smallest to largest length. This is achieved by
keeping track of the program counts. Let $k$ be any position, and let $\ell$
be the greatest length such that the cumulative sum of program counts
$\overline{c}$ is less than $k$. Then the corresponding program is at position
$k-\overline{c}$ of the $\ell$-length enumeration.

The canonically sorted enumeration has the advantage of sorting programs in a
predictable order. However, in contexts where the order is not as relevant,
the base enumeration has a couple of advantages:

  * •

The algorithm to build a program for a given position is simpler and more
efficient both in time and space.

  * •

The current implementation includes the inverse process of calculating the
position for a given program efficiently.

  * •

Enumerations with different orderings or for subsets of the language can be
easily derived.

[By the way, the techniques used to build the sorted enumeration can be
applied to any other programming languages and metrics. The base enumeration
is constructed in a declarative way by means of a combinator language based on
Euclidean division and an $n$-tuple pairing function akin to Cantor’s pairing
function for pairs of natural numbers [4]. The rest of the stages follow a
manual process once a metric has been defined, and as long as the metric
computes its value from a program’s constituent parts and the mechanism for
combining them, then this manual process can be adapted in a straightforward
way.]

###  3.4 Sampling the program space

The sorted enumeration is used to navigate the space of programs. Starting
from position zero, programs are generated and executed successively, with the
guarantee that any programs generated afterwards will be of the same length or
longer, which is convenient if the goal is to approximate their Kolmogorov-
Chaitin complexity.

The results obtained from this process are collected and analysed after
exploring all programs of each length. The space of programs of length at most
$\ell$ is denoted by $\mathcal{S}_{\ell}$. In this project we focus our
attention on $\mathcal{S}_{9}$, which consists of
$|\mathcal{S}_{9}|=$123\,089\,621$$ programs.

Following the statistical approach of Calude et al for estimating running
time, we used a sampling size of $N=$13\,815\,511$$ corresponding to the last
row of table 1.

The sample must consist of programs that halt. In order to achieve this, a
random number generator is used to sample uniformly distributed integers in
the interval $[0,|\mathcal{S}_{9}|)$. Interpreted as positions in the sorted
enumeration, these integers are effectively encodings of IMP programs in
$\mathcal{S}_{9}$. After generating a program, it is executed with a large
running time threshold $\mathbf{T}$ in order to determine if it can be
considered part of the sample.

When choosing a threshold we must be careful to not set it too low, which
would potentially exclude many halting programs from the sample. On the other
hand, setting the threshold too high will affect the performance of the
sampling process when executing non-halting programs. We decided to accept the
performance loss by fixing $T=10^{4}$, as this value is quite large in
comparison to the lengths of programs being executed. We believe it is a
reasonable threshold to use during the sampling process.

For all sampled programs we recorded their position in the sorted enumeration,
their length, their output strings, and their running time. Table 3 shows how
the sample is distributed by program length and the percentage corresponding
to the total number of programs.

| Count
---|---
Length | Sampled | Percentage
$1$ | $0$ | $$0$\%$
$3$ | $0$ | $$0$\%$
$4$ | $12$ | $$11.54$\%$
$5$ | $245$ | $$11.53$\%$
$6$ | $4091$ | $$11.44$\%$
$7$ | $62\,258$ | $$11.39$\%$
$8$ | $902\,471$ | $$11.29$\%$
$9$ | $12\,846\,434$ | $$11.22$\%$
Table 3: Number of sampled programs by length.

The largest running time obtained from the sampled programs was $9$ steps,
which means that there were no sampled programs that halted between $10$ and
$10^{4}$ steps, and indicates that the chosen running time threshold was high
enough for our purposes. Figure 2 shows the distribution of the sample by the
running time, where no programs ran in zero or one steps, and less than a
hundred ran in $9$ steps.

Figure 2: Running time distribution across the sample.

Figure 3 shows how the lengths of the outputs in the sample are distributed.
Almost a third of the output strings obtained were the empty string, and the
largest outputs consist of $19$ bits.

Figure 3: Output length distribution across the sample.

Given the results described above and the statistical estimation of Calude et
al, we should run all programs in the sample space using a running time
threshold of $\mathbf{T}=9$, which significantly reduces the evaluation time
of non-halting programs, compared to the threshold $T=10^{4}$ used for the
programs in the sample.

##  4 Some results of the execution of programs

###  4.1 Systematic execution of programs in $\mathcal{S}_{9}$

In order to empirically verify the quality of the chosen running time
threshold estimate, we generated and executed all programs in
$\mathcal{S}_{9}$ with threshold $\mathbf{T}$ to see if the statistically
estimated $T$ is good enough.

Table 4 classifies the number of programs by length into halting and non-
halting, along with the percentage of the total count. The results show a
slight decreasing trend for the percentage of programs that halt as program
length increases, and correspondingly the trend is inverted for non-halting
programs.

Length | Halt | (%) | Non-halt | (%)
---|---|---|---|---
$1$ | $1$ | $($100.0$\%)$ | $0$ | $($0.0$\%)$
$3$ | $2$ | $($66.7$\%)$ | $1$ | $($33.3$\%)$
$4$ | $103$ | $($99.0$\%)$ | $1$ | $($1.0$\%)$
$5$ | $2059$ | $($96.9$\%)$ | $65$ | $($3.1$\%)$
$6$ | $34\,491$ | $($96.4$\%)$ | $1279$ | $($3.6$\%)$
$7$ | $522\,060$ | $($95.5$\%)$ | $24\,551$ | $($4.5$\%)$
$8$ | $7\,578\,748$ | $($94.8$\%)$ | $412\,428$ | $($5.2$\%)$
$9$ | $107\,800\,381$ | $($94.1$\%)$ | $6\,713\,451$ | $($5.9$\%)$
Table 4: Halting and non-halting programs by length.

The table shows a sudden drop to $$66.7$\%$, which interrupts the trend
mentioned above. This is because there are only three programs of length 3,
and one of them is the first non-halting program: (skip; skip), (while false
do skip), and (while true do skip).

The largest running time obtained from the sampling space was in fact $9$
steps, which confirms that the estimate $\mathbf{T}$ given by Calude’s method
would have given us the same results.

For the purpose of approximating the algorithmic complexity of a bit string,
we are interested in finding non-trivial programs that produce an output
longer that the programs’ length. However, for the purpose of finding
generating computable models, any program of any length will provide, and the
number of programs found for the same object, is an indication of the data’s
nature and its algorithmic probability determining a likelihood as a
generating mechanism.

Figure 4 shows the distribution of halting-programs by length and running
time, and we expect non-trivial programs to appear in the upper-left triangle,
where the running times are large relative to the length of the programs.
Figure 5 shows the distribution of halting-programs by output length and
program length. We also expect non-trivial programs to appear in the lower-
right triangle of figure 5, where the lengths of the output strings are large
relative to the length of the programs.

Figure 4: Distribution of $\mathcal{S}_{9}$ program length and running time.
Figure 5: Distribution of sample space by output length and program length.

In these figures, a darker shade means that there are more programs in the
configuration–the intensity of the colouring is log-scaled in order to
visualise clearly the distinction between zero programs and just a small
number of programs.

In order to specify which programs are trivial in the context of Kolmogorov
complexity, we use a standard process to calculate an upper bound for the
complexity of a binary string $b$. First we compute the position $n$ of $b$ in
the lexicographical enumeration of all binary strings. Then we build the
program $p$ as $x[0]:=n$. Finally the length $\ell$ of $p$ sets an upper bound
on $K_{\mathrm{IMP}}(b)$. As a base case, we include the program $skip$ with
length 1 as the upper bound for the empty binary string.

One future goal in exploring the program space is to improve upon this bound.
Even though we explored around 123 million programs, and retrieved a million
different output strings, the first smallest program found for every output
string corresponded to the trivial program described above consistent with the
theoretical expectation.

We found that the shortest programs produced a considerable number of strings.
A table showing strings and a sample of the shortest programs producing them
can be found at the the following URL:

https://kolm-complexity.gitlab.io/approx-
kolmogorov/approximating_kolmogorov.html

###  4.2 Program space beyond $\mathcal{S}_{9}$

While the systematic exploration of programs up to length 9 has allowed us to
find the simplest programs producing some small strings, we are still at the
level of trivial programs in the sense that their length is on the same order
of magnitude than the strings they output. We need to go farther than
$\mathcal{S}_{9}$ in order to find programs whose output is much bigger and
therefore more interesting. In Figures 6, 7, 8, 9 we present four families of
programs producing an output clearly bigger than the length of the programs:

( | x[0] := 1;
---|---
| (while (x[1] < n) do
| ( | x[1] := (x[1] + 1);
|  | x[0] := (x[0] * 2))))
Figure 6: Family of programs that calculate $2^{n}$. ( | x[0] := 1;
---|---
| (while (x[1] < n) do
| ( | x[1] := (x[1] + 1);
|  | x[0] := (x[0] * x[1]))))
Figure 7: Family of programs that calculate $n!$. ( | x[0] := 1;
---|---
| (while (x[1] < n) do
| ( | x[1] := (x[1] + 1);
|  | x[0] := (x[0] * n))))
Figure 8: Family of programs that calculate $n^{n}$. ( | x[0] := n;
---|---
| (while (x[1] < n) do
| ( | x[1] := (x[1] + 1);
|  | x[0] := (x[0] * x[0]))))
Figure 9: Family of programs that calculate $n^{2^{n}}$.

Examples of the output of these programs are shown in Tables 5, 6, 7 and 8.
The changing parameter is $n$. As it can see, for each family there is a lower
bound on the value of $n$ when the output starts being clearly bigger than the
length of the program itself.

| Length |
---|---|---
$n$ | Program | Output | Output String
$0$ | $25$ | $1$ | 0
$1$ | $25$ | $2$ | 10
$2$ | $25$ | $3$ | 011
$3$ | $25$ | $5$ | 00100
$4$ | $25$ | $6$ | 000101
$5$ | $25$ | $7$ | 0000110
$6$ | $25$ | $8$ | 00000111
$7$ | $25$ | $10$ | 0000001000
$8$ | $25$ | $11$ | 00000001001
$9$ | $25$ | $12$ | 000000001010
$10$ | $26$ | $13$ | 0000000001011
$11$ | $26$ | $14$ | 00000000001100
$12$ | $26$ | $15$ | 000000000001101
$13$ | $26$ | $16$ | 0000000000001110
$14$ | $26$ | $17$ | 00000000000001111
$15$ | $26$ | $19$ | 0000000000000010000
$16$ | $26$ | $20$ | 00000000000000010001
$17$ | $26$ | $21$ | 000000000000000010010
$18$ | $26$ | $22$ | 0000000000000000010011
$19$ | $26$ | $23$ | 00000000000000000010100
$20$ | $26$ | $24$ | 000000000000000000010101
$21$ | $26$ | $25$ | 0000000000000000000010110
$22$ | $26$ | $26$ | 00000000000000000000010111
$23$ | $26$ | $27$ | 000000000000000000000011000
Table 5: IMP programs computing $2^{n}$ | Length |
---|---|---
$n$ | Program | Output | Output String
$0$ | $26$ | $1$ | 0
$1$ | $26$ | $2$ | 00
$2$ | $26$ | $2$ | 11
$3$ | $26$ | $4$ | 1100
$4$ | $26$ | $6$ | 100101
$5$ | $26$ | $8$ | 11100110
$6$ | $26$ | $11$ | 01101000111
$7$ | $26$ | $15$ | 001110110001000
$8$ | $26$ | $18$ | 001110110000001001
$9$ | $26$ | $21$ | 011000100110000001010
$10$ | $27$ | $24$ | 101110101111100000001011
$11$ | $27$ | $28$ | 0011000010001010100000001100
Table 6: IMP programs computing $n!$ | Length |
---|---|---
$n$ | Program | Output | Output String
$0$ | $25$ | $1$ | 0
$1$ | $25$ | $2$ | 00
$2$ | $25$ | $3$ | 011
$3$ | $25$ | $6$ | 110000
$4$ | $25$ | $10$ | 0000000101
$5$ | $25$ | $13$ | 1000011011010
$6$ | $25$ | $17$ | 01101100100000111
$7$ | $25$ | $22$ | 1001001000011111000000
$8$ | $25$ | $27$ | 000000000000000000000001001
Table 7: IMP programs computing $n^{n}$ | Length |
---|---|---
$n$ | Program | Output | Output String
$0$ | $26$ | $0$ | $\varepsilon$
$1$ | $26$ | $2$ | 00
$2$ | $26$ | $5$ | 00011
$3$ | $26$ | $14$ | 10011010001000
$4$ | $26$ | $34$ | 0000000000000000000000000000000101
Table 8: IMP programs computing $n^{2^{n}}$

Given that the shortest examples that show interesting results live in
$\mathcal{S}_{25}$, it will take an enormous amount of computational work to
generate and execute the programs in this class. In order to get the results
in the tables we did not follow the canonical enumeration but the base
enumeration mentioned in section 3.3. Generating programs according to the
base enumeration does not guarantee that we will find first the shortest
program producing an output, but it can give us _upper bounds_ for the
Kolmogorov complexity that are definitely smaller than the trivial programs.
As this enumeration is also bijective and exhaustive it will eventually
produce the shortest program too. In the meantime it has already given us
useful information about the Kolmogorov complexity of strings representing the
functions $2^{n}$, factorial, $n^{n}$ and $n^{2^{n}}$. The base enumeration
can be regarded as a kind of _look ahead_ exploration.

##  5 Conclusions and Future Work

We started this project as a proof of concept for approximating Kolmogorov
complexity using a very different computational model from those used in
previous work. We managed to overcome some very serious technical impediments
to efficiently generating vast amounts of programs, and we are confident the
project can be scaled up for longer programs. But before discussing how this
may be done, we want to draw some conclusions about the already explored space
of programs.

First of all, we saw that Calude’s method for estimating probable halting
times can be applied to our chosen computational model without much trouble.
Better still, estimating halting times for bigger program spaces is feasible
(we have done this for programs of length 11 already, without need of
considerably greater computational resources).

Secondly, all the programs found in $\mathcal{S}_{9}$ so far are still
trivial, in the sense that their length is greater than that of the output
strings. This was to be expected, as short strings can be described very
succinctly by just presenting them. Yet this approach represents an
opportunity to rank them even when short. Other approaches, including lossless
statistical compression algorithms, present the same challenges and
limitations, and are actually unable to rank short strings for more basic
reasons. But there are indications that this could change for programs in
$\mathcal{S}_{11}$. As this space is considerably larger than
$\mathcal{S}_{9}$, we could not collect the outputs produced by all programs
in $\mathcal{S}_{11}$ that will be calculated in the future. Nevertheless,
Figure 10 shows the distribution of $\mathcal{S}_{11}$ by program length and
running time. In contrast to figure 4, we are starting to get programs in the
upper-left region above the identity line. Specifically, there are some
programs of length 10 with a running time of 11 steps, and programs of length
11 with a running time of 13 steps, which means (quite significantly) that we
are starting to see programs whose execution times exceed their length, and we
think this region will grow faster in larger spaces. Longer execution times
are needed to produce larger outputs.

Figure 10: Distribution of $\mathcal{S}_{11}$ by program length and running
time.

Thirdly, using a different enumeration of programs we managed to explore much
bigger spaces than $\mathcal{S}_{9}$ showing how the method can generate non-
trivial programs and can find highly recursive ones quickly without many
resources even at the beginning of the enumeration by choosing a high-level
computer language. This is key for the causal discovery program in [20, 24]
with applications to, for example, areas of Artificial Intelligence [23].

On the other hand, it is naive to think that such a vast and ever growing
enterprise as calculating Kolmogorov complexity can be undertaken by a small
team with limited resources. Currently, our workflow looks like this: we read
a list of programs, run them, and save the outputs in a text file. After
receiving the outputs, we check that the file is accurate through two
mechanisms: an integrity check using hashes and a correctness check through
the execution of a random sample of programs.

This process can easily be made to work within a collaborative framework.
Among others, one option is to use the framework of the Automacoin[25]
cryptocurrency tocken. A user of Automacoin will get a reward for running
millions of programs and submitting their output. This method of collaboration
is sustainable and useful for both parties.

Collaborative frameworks need portable and efficient ways of setting and
running partial tasks for collaborators. A portable, light-weight interpreter
for IMP will be part of this effort. We are working on this and we already
have a nice prototype implemented in Haskell [26].

## References

  * [1] C. Calude and M. Stay, “Most programs stop quickly or never halt”, _Advances in Applied Mathematics_ , 40, pp. 295–308, 2008.
  * [2] C. Calude and M. Dumitrescu, “A probabilistic anytime algorithm for the halting problem.”, _Computability_ , 7, 259–271, 2018. doi: 10.3233/COM-170073.
  * [3] C. Calude and M. Dumitrescu, “A statistical anytime algorithm for the Halting Problem”, _Computability_ , 9, 155–166, 2020. doi: 10.3233/COM-190250.
  * [4] G. Cantor, “Ein Beitrag zur Mannigfaltigkeitslehre”, Journal für die reine und angewandte Mathematik, vol. 84, pp. 242–258, 1877.
  * [5] G.J. Chaitin, “A theory of program size formally identical to information theory”, _J. ACM_ , 22, 329–340, 1975.
  * [6] U. Čibej, B. Robič and J. Mihelič, “Empirical estimation of the halting probabilities”, Computability in Europe, 2014.
  * [7] R.L. Cilibrasi and P. Vitányi, “Clustering by compression”, _IEEE Trans. Inf. Theory_ , 51, 1523–1545, 2005.
  * [8] N. Gauvrit, J.-P. Delahaye and H. Zenil, “Sloane’s Gap: Do Mathematical and Social Factors Explain the Distribution of Numbers in the OEIS?” _Journal of Humanistic Mathematics_ , vol. 3, no. 1, pp. 3-19, 2013. doi:10.5642/jhummath.201301.03
  * [9] J. Grass, “Reasoning about computational resource allocation. An introduction to anytime algorithms”, _Magazine Crossroads_ , 3(1), 16–20, 1996. doi:10.1145/332148.332154.
  * [10] W. Hoeffding, “Probability inequalities for sums of bounded random variables”, _Journal of the American Statistical Association_ , 58(301), 13–30, 1963. doi:10.1080/01621459.1963.10500830.
  * [11] S. Köhler, C. Schindelhauer and M. Ziegler, “On Approximating Real-World Halting Problems”, in: M. Liśkiewicz, R. Reischuk (Eds.), Proc. FCT 2005, Lectures Notes in Comput. Sci., vol. 3623, Springer, 454–466, 2005.
  * [12] A.N. Kolmogorov, “Three approaches to the quantitative definition of information”, _Problems of Information and Transmission_ , 1(1), 1–7, 1965.
  * [13] M. Li and P. Vitányi, _An Introduction to Kolmogorov Complexity and Its Applications_ , Springer, 2008.
  * [14] G.D. Plotkin, “Structural operational semantics”, Lecture Notes, DAIMI FN-19, Aarhus University, 1981.
  * [15] F. Soler-Toscano F, H. Zenil, J.-P. Delahaye and N. Gauvrit, “Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines”, _PLoS ONE_ , 9(5): e96223, 2014. doi:10.1371/journal.pone.0096223
  * [16] A.M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem.” _Proceedings of the London Mathematical Society_ , s2-42 (1), 230–265, 1937.
  * [17] G. Winskel, _The Formal Semantics of Programming Languages_ , The MIT Press, 1993.
  * [18] H. Zenil, S. Hernández-Orozco, N.A. Kiani, F. Soler-Toscano and A. Rueda-Toicen, “A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity”, _Entropy_ , 20, 2018.
  * [19] H. Zenil, L. Badillo, S. Hernández-Orozco, F. Hernández-Quiroz, “Coding-theorem Like Behaviour and Emergence of the Universal Distribution from Resource-bounded Algorithmic Probability”, _Int. J. Parallel Emerg. Distrib. Syst._ , 2018.
  * [20] H. Zenil, N.A. Kiani, A. Zea, J. Tegnér, “Causal Deconvolution by Algorithmic Generative Models”, _Nat. Mach. Intell._ , 1, 58–66, 2019.
  * [21] H. Zenil, N.A. Kiani, F. Marabita, Y. Deng, S. Elias, A. Schmidt, G. Ball, J. Tegnér, “An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems”, _iScience_ , S2589-0042(19)30270-6, 2019 DOI:10.1016/j.isci.2019.07.043
  * [22] H. Zenil, “A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions”, _Entropy_ , 22(6), 2020.
  * [23] S. Hernández-Orozco, H. Zenil, J. Riedel, A. Uccello , N.A. Kiani, and J. Tegnér, “Algorithmic Probability-guided Machine Learning On Non-differentiable Spaces”, _Frontiers in Artificial Intelligence_ , 25, 2021.
  * [24] H. Zenil, N.A. Kiani, F.S. Abrahao and J. Tegnér, “Algorithmic Information Dynamics”, _Scholarpedia_ , 15(7):53143, 2020. doi:10.4249/scholarpedia.53143
  * [25] AUTOMACOIN.
URL https://www.automacoin.com/

  * [26] Haskell Language.
URL https://www.haskell.org/