Experimental Mathematics Approach to Gauss Diagrams Realizability

Gauss words and Gauss diagrams are natural combinatorial encodings of generic smooth closed planar curves. For a closed planar curve its Gauss code (word) can be obtained by first assigning different symbols to all intersection points and then by writing down the symbols of intersection points passed over during traversal of the curve, starting and finishing at the chosen non-intersection point, see (Fig 1, a). The Gauss code of a closed curve with $n$ intersection points has a length $2n$ and it is a double occurrence word, that is in which each symbol occurs twice. With any double occurrence word one can further associate its chord (or Gauss) diagram which consists of a circle with all symbols of the word placed at the points of the circle following its clockwise traversal. The chords of the diagram link the points labelled by the same symbol, (Fig.1,b). Not every double occurrence word and its Gauss diagram correspond to (can be obtained from) a closed planar curve; if they do, they are called realizable.

A classical question of computational topology asked by Gauss [Gau00] is which of the chords diagrams are realizable. Gauss himself gave a partial answer in terms of a necessary condition - in a realizable diagram any chord intersects even number of other chords Additional necessary condition was provided by Nagy [Nag27] and a full answer to Gauss’ question was discovered in the 1930s by Dehn [Deh36]. Since then many efficient criteria and algorithms for checking the realizability of Gauss diagrams have been developed [Mar69, Fra69, de 81, LM76, Ros76, RR76, RT84, dFOdM97, DT83, Ven18, CE96, CW94]. As computational complexity concerned recognition of realizability of Gauss diagrams or words can be done in polynomial time and even in linear time [RT84]. Furthermore as it is shown in [LPS11] it can be done with logarithmic space complexity. All realizability criteria and detection algorithms in the papers cited above can be expressed in terms of a diagram graph $(V,E,H)$ with two types of edges representing a chord diagram. Vertices of the graph are points of the diagrams, one type $E$ of edges corresponds to chords, the edges of another type $H$ form a cycle covering all vertices in $V$, see Fig. 2.

With every Gauss diagram one may further associate an interlacement graph whose vertices are the chords of the diagram and two vertices are adjacent if an only if the corresponding chords intersect, see (Fig. 1, c). The interlacement graph of a diagram embodies an essential information about its realiziability. Furthermore, as it was shown in [Ros76, dFOdM97, STZ09] the realizability of Gauss diagrams can be decided based on their interlacement graphs only. The criteria are more abstract then those defined in terms of diagram graphs, as different (non-isomorphic) diagram graphs may have isomorphic corresponding interlacement graphs. At the same time criteria from [Ros76, dFOdM97, STZ09] appear to be computationally more costly. Some account of this can be given in terms of definability and descriptiive complexity [Imm99]. The formal definition of these conditions can be presented in first-order logic (FO) extended by a parity quantifier (${\rm MOD_{2}}$) [Nur00] and monadic second-order quantification (MSO). While parity quantifier evaluation can be implemented very efficiently, second-order quantification goes over all subsets of vertices. Hence checking these conditions by a straightforward algorithm requires exponential time. More recent studies [GL18, GL20, Bir19] formulated even simpler realizability conditions expressible in terms of the interlacement graphs. In particular [GL18, GL20] proposed a criteria based on parity conditions and reduction operation on the graph, while [Bir19] reformulated it in a simple form, expressed in ${\rm FO+MOD_{2}}$. Further simple analysis shows that the original conditions from [GL18] can be expressed in ${\rm FO+MOD_{2}}$ too. Hence both variants of criteria can be tested in polynomial time and logarithmic space. Furthermore the simple and declarative form of these conditions opens an opportunity for experimental investigation of Gauss diagrams using constraint satisfaction [Tsa93, RBW06] and related computational techniques. We took this opportunity as a starting point of our research in experimental mathematics with the primary aim to enumerate various classes of Gauss diagrams. We have implemented the declarative realizability conditions and algorithms from [Bir19], [GL20] and [STZ09] alongside with the classical algorithm from [Deh36] (for the latter see detailed exposition in e.g. [Kau99]). We have enumerated several interesting classes of Gauss diagrams up to sizes 10-12 (number of chords), confirming and expanding on known enumerations (for the latter see e.g. [CZ16] and references therein). The detailed presentation of this will be given in an extended version of this paper. In the present note we confine ourselves with the presentation of the most surprising discovery, that is the realiziability conditions in [Bir19], [GL20] are not completely correct. We present a minimal counterexample to both conditions of size 9 and enumerate all countexamples of sizes 10 and 11. We further confirm experimentally up to the size 11 that criteria from [Bir19] and [GL20] are equivalent, and the condition from [STZ09] is correct, i.e equivalent to that from [Deh36].

In this section we formally discuss the definitions used in our paper.

In this paper we are only concerned with the curves immersed into plane $R^{2}$ or sphere $S^{2}$.

The equivalence of immersed curves with prime Gauss diagrams is captured by isomorphism of Gauss words and Gauss diagrams. Two double occurrences words over the same alphabet are isomorphic if one can be obtained from the other by any combination of cyclic shifts and reversing the word [Car91]. For immersed curves $\gamma_{1}$ and $\gamma_{2}$, such that their Gauss diagrams are prime, both corresponding Gauss words and Gauss diagrams are isomorphic if and only if $\gamma_{1}$ and $\gamma_{2}$ are equivalent, see e.g. [CHLR06].

A double occurrence word $w$ is called realizable iff there exists an immersed in a plane (or sphere $S^{2}$¹¹1when presenting criteria for realizability of Gauss words and diagrams, various authors refer to immersions either to plane, or sphere $S^{2}$. It is easy to see, by considering the stereographic projection of $S^{2}$ to $R^{2}$, that it does not make a difference ) curve $\gamma$, such that $w$ is associated with $\gamma$. A Gauss diagram $g$ is realizable iff there is a realizable word $w$ such that $g$ is isomorphic to $g(w)$.

Not all double occurrences words and Gauss diagram are realizable. In this paper we mainly focus on investigation of the realizability criteria of prime Gauss diagrams expressed solely in terms of their interlacement graphs.

One necessary realizability condition proposed by Gauss himself can be formulated in terms of interlacement graphs as follows:

C1: If a Gauss diagram $g$ is realizable then in its interlacement graphs $I_{g}$ every node has an even degree.

In this section we overview known realiziability criteria for Gauss diagrams, which are defined in terms of the interlacement graphs.

We aim to implement efficient algorithms for generating Gauss diagrams, checking their (non-)equivalence, listing all non-equivalent diagrams, satisfying combinations of criteria and checking the realiziability criteria. As a starting point we take Definition 2, and consider the generation of Gauss diagrams with a sets of vertices $V=\{i\mid 0\leq i\leq 2n-1\}$ for some $n\geq 2$ satisfying an additional constraint, corresponding to the condition C1. For that we introduce a concept of lintel, and useful algorithms working on lintels.

Let $n$ be a positive integer. A lintel is an $n$-tuple of pairs of numbers $((a^{1}_{1},a^{2}_{1}),\dots,$ $(a^{1}_{n},a^{2}_{n}))$ such that 1) the set of numbers in the lintel $\{a^{1}_{i},a^{2}_{i},\dots,a^{1}_{n},a^{2}_{n}\}$ is equal to the set $\{0,1,\dots,2n-1\}$, and 2) in each pair $(a^{1}_{i},a^{2}_{i})$ the difference $a^{1}_{i}-a^{2}_{i}$ is odd. The number $n$ will be called the size of the lintel. Each pair $(a^{1}_{i},a^{2}_{i})$ will be called a chord of the lintel.

For example, $L=((4,7),(8,1),(5,0),(2,9),(6,3))$ is a lintel of size $5$. For better readability, below we will write the two numbers in each chord under one another; therefore, the lintel $L$ can be written as $\begin{pmatrix}4&8&5&2&6\\ 7&1&0&9&3\end{pmatrix}$.

Let us say that two lintels are strongly equivalent if they can be transformed into one another by steps of the following two types:

1. 1.

   Swapping the positions of two numbers in a chord; for example, the lintel $L$ in the example above is strongly equivalent to $\begin{pmatrix}4&8&0&2&6\\ 7&1&5&9&3\end{pmatrix}$;

2. 2.

   Swapping the positions of chords in the list; for example, the lintel $L$ in the example above is strongly equivalent to $\begin{pmatrix}2&8&5&4&6\\ 9&1&0&7&3\end{pmatrix}$.

Among the lintels that are strongly equivalent to each other, one can point at one which can serve as the canonical lintel of this class of lintels. To define it, let us introduce a kind of lexicographic order on lintels. Consider two lintels of size $n$, $L=\begin{pmatrix}a^{1}_{1}&\dots&a^{1}_{n}\\ a^{2}_{1}&\dots&a^{2}_{n}\end{pmatrix}$ and $M=\begin{pmatrix}b^{1}_{1}&\dots&b^{1}_{n}\\ b^{2}_{1}&\dots&b^{2}_{n}\end{pmatrix}$. We will say that $L$ is less than $M$ if there is a position $i$ such that $a^{1}_{j}=b^{1}_{j}$ and $a^{2}_{j}=b^{2}_{j}$ for all $j<i$, and either $a^{1}_{i}<b^{1}_{i}$, or $a^{1}_{i}=b^{1}_{i}$ and $a^{2}_{i}<b^{2}_{i}$. We will call this order the L-order. The lintel which is the least one relative to the L-order among the lintels that are strongly equivalent to each other will be treated as the canonical representative of this class of lintels. There is also another way to define this lintel. Let us say that a lintel is a sorted lintel if each pair in it is sorted, and first elements of pairs are sorted, that is, for each $i$ we have $a^{1}_{i}<a^{2}_{i}$, and for all $i<j$ we have $a^{1}_{i}<a^{1}_{j}$. In each class of lintels that are strongly equivalent to each other, there is exactly one sorted lintel, and it is the one that is the least one relative to the L-order. For a given lintel $L$, one can produce the sorted lintel corresponding to $L$ using the following simple algorithm.

Let us say that two lintels are equivalent if they can be transformed into one another by steps of the following types:

1. 1.

   the two types of steps defining strongly equivalent lintels

2. 2.

   shifting the value of each entry of the lintel cyclically modulo $2n$, that is, replacing a lintel $\begin{pmatrix}a^{1}_{1}&\dots&a^{1}_{n}\\ a^{2}_{1}&\dots&a^{2}_{n}\end{pmatrix}$ by a lintel $\begin{pmatrix}a^{1}_{1}+s&\dots&a^{1}_{n}+s\\ a^{2}_{1}+s&\dots&a^{2}_{n}+s\end{pmatrix}$ for some value $s$, with operations performed in the arithmetic modulo $2n$;

3. 3.

   inverting the value of each entry of the lintel modulo $2n$, that is, replacing a lintel $\begin{pmatrix}a^{1}_{1}&\dots&a^{1}_{n}\\ a^{2}_{1}&\dots&a^{2}_{n}\end{pmatrix}$ by the lintel $\begin{pmatrix}-a^{1}_{1}&\dots&-a^{1}_{n}\\ -a^{2}_{1}&\dots&-a^{2}_{n}\end{pmatrix}$, with operations performed in the arithmetic modulo $2n$;

Now we are ready to define a canonical lintel. Namely, the lintel which is the least one relative to the L-order among the lintels that are equivalent to each other will be treated as the canonical representative of this class of lintels We shall call such lintels Lyndon lintels. This construction is similar in certain aspects to Lyndon words in algebra, hence the name Obviously, a Lyndon lintel is a sorted lintel, but not every sorted lintel is a Lyndon lintel. For a given lintel $L$, one can produce the sorted lintel corresponding to $L$ using the following algorithm.

Proof Let $I_{2n}=\{0,\ldots,2n-1\}$. Denoted by $P_{2n}$ the set of all even-odd matchings of $I_{2n}$, that is partitions of $I_{2n}$ into subsets of size 2, each containing one even and one odd number. The obvious consequence of definitions is that elements of $P_{2n}$ are in bijective correspondence with the set of all equivalence classes for strong equivalence relation on lintels of size $n$. Now for symmetric group $S_{n}$ we define a mapping $\beta:S_{n}\rightarrow P_{2n}$ as follows. For $\sigma\in S_{n}$, $\sigma:[1..n]\rightarrow[1..n]$ $\beta(\sigma)=\{\{2*i-1,2*\sigma(i)-2\}|i\in[1..n]\}$. Straightforward check shows that $\beta$ is a bijection between $S_{n}$ and $P_{2n}$.

We have implemented the algorithms suite Gauss-Lint for Gauss diagram generation, equivalence checking, canonization, and realizability conditions using the concept of lintels. The prototype implementation in logic programming language SWI-Prolog [WSTL12] is available at [KLV21].

Here we give a short overview of the implementation while more detailed presentation is deferred to the extended version of this paper.

Using our implementation we have conducted various experiments and enumerated the classes of non-equivalent Gauss diagrams, satisfying various combinations of properties.

Table 1 shows the numbers of non-equivalent Gauss diagrams of sizes $3\ldots 11$ satisfying different realizability conditions, generated by our program. The first two lines, found also in OEIS article A264759 [oeib], together with the fact that generated corresponding lists of Gauss diagrams are the same, verify that indeed, STZ are correct realizability conditions up to the size 11.

The last two lines show an interesting phenomenon. Up to the size 8 B and GL conditions are satisfied by the same diagrams, as CA and STZ are. For the size 9, however, there is one (= $102-101$) up to equivalence Gauss diagram such that it satisfies both B and GL conditions, but still is not realizable. For sizes 10 and 11 the numbers of such diagrams are 6 and 36²²2 For size 12, the number of such diagrams is $235=7437-7202$. The analysis of size 12 required an additional, more efficient method of generating Gauss diagrams, which will be described in the extended version of this paper , respectively.

In summary, CA and STZ, respectively B and GL, are pairwise equivalent conditions up to the size 11. B and GL, however are not equivalent to CA or STZ, starting from size 9. Hence B and GL are not correct realizability criteria despite the claims in [Bir19] and [GL18, GL20], respectively.

We have presented an approach to experimental investigation of Gauss realizability conditions based on the concept of lintel. We have implemented the algorithms for Gauss diagrams generation, canonization and checking recently proposed declarative criteria for Gauss realizability. We reported on the experiments with our implementations and presented counterexamples for the recently published simple realizability criteria. Based on that we conjecture that realizability of Gauss diagrams can not be defined in first-order logic with parity quantifier over their interlacement graphs.

This work was supported by the Leverhulme Trust Research Project Grant RPG-2019-313.