Following the work of Jeremy Green and his table of virtual knots, this is a table of virtual links with two components. They were enumerated using a computer search based on the same techniques, extended to handle virtual links and to construct a virtual link database that allows additional analysis of Gauss codes. Details of the approach taken are given in the Algorithm Details section below.
The initial objective of this work was to create a list of virtual links similar to Jeremy Green's virtual knots by constructing Reidemeister equivalence classes within a set of diagrams represented by Gauss codes and using link invariants to prove that the resultant equivalence classes were distinct. Then, the possibility of recording the Reidemeister moves between pairs of diagrams presented itself, rather than discarding them and retaining only a preferred representative for each equivalence class as Green had done. That would enable the construction of a graph that could not only determine Reidemeister equivalence but provide a set of Reidemeister moves that demonstrated that equivalence explicitly.
The remainder of this page describes how these objectives have been achieved and the relationship between them.
Two canonical formats for the Gauss code of a diagram have been are used. The first is the "minimal cyclic" form used by Green, which is most naturally written in O,U format and is used here for enumerating unsigned Gauss codes; that is, permutations of the set {O1, U1, O2, U2, ..., On, Un} for some number of crossings. Commas are used to separate the terms corresponding to link components, as in O1U2U3,U1O2O4O3U4.
The minimal cyclic canonical form for a diagram is defined by considering all possible starting points and each choice of orientation, if appropriate, and numbering the crossings in the order in which they are are encountered. Each term of the Gauss code is converted to an integer:
6*<crossing_number> + <crossing_detail>, where <crossing_detail> = enum{O-, O, O+, U-, U, U+},
Here, enum is analogous to the C++ enumeration, so O- = 0, O = 1, O+ = 2, U- = 3, U = 4, U+ = 5. Only the O and U terms apply to unsigned Gauss codes, the other terms relate to the storage mechanism for signed Gauss codes used in Green's software. The conversion results in a representation of the Gauss code as a sequence of n integers, the minimal cyclic Gauss code being the one that corresponds to the lexicographically minimal such sequence. This canonical form for knots used by Green extends immediately to links if we fix the order of the components. Clearly, minimal cyclic Gauss codes always begin with the O1 term.
The other canonical form is the "over preferred" Gauss code, used here for signed Gauss codes. This format of Gauss code is more naturally written with the sign of the crossings separated from the sequence of crossing encounters and the over and under nature of each crossing encounter recorded as a signed crossing number. Thus we write 1 2 -3 4 -5 3 -1 -2 6 -4 5 -6-/+ - + - + - rather than O1+O2-U3+O4-U5+O3+U1+U2-O6-U4-O5+U6- and, again, separate link components with commas as in 1 2 -1 3 4 -5 -2 -6,-3 -4 6 5/+ + + - - -.
The over preferred form of a Gauss code is defined by analogy to the left preferred and un-oriented left preferred Gauss data for doodles (see [1]). We consider every possible re-numbering of the classical crossings, every possible starting point and each orientation, where appropriate. Amongst the resultant Gauss codes, the over preferred code is the one that contains 1,...,n (that is: over 1, ..., over n) as a subsequence and is lexicographically minimal amongst all such codes, where "over n" is considered to be smaller than "under n" and positive crossings considered smaller than negative crossings.
The over preferred canonical form extends to links by considering all possible orderings of the components and, if appropriate, all possible orientations of each component independently (that is 2k combinations of orientation for a k-component link). Components with fewer terms are preferred in the rare cases that two codes that differ only in the position of the component separator represent the same diagram, as in:
1 2 -3 -5 -1 3 4 -6,-2 -4 5 6/+ - + + - + and
1 2 -3 -5,-1 3 4 -6 -2 -4 5 6/+ - + + - +
The first of the above codes has component lengths 6 and 4, whereas the second has component lengths 4 and 6, so we prefer the second form.
The algorithm begins with the production of a set of files containing a complete set of minimal cyclic un-signed Gauss codes for some fixed number of crossings. The enumeration of the minimal cyclic codes is based on Green's approach of building unsigned Gauss codes recursively by considering all possible values for the next term and discarding those that result in a Reidemeister I configuration.
When enumerating the Gauss codes for links, multiple top-level calls to the recursive code generation function are made, each with a different, fixed, set of component boundaries. The algorithm does not permute components when looking for minimal cyclic codes. This has the effect of increasing the size of the list that is produced, since two codes may be equivalent if we consider the components in a different order, but results in a much faster enumeration than any other approach. Duplicates are removed at the second stage of the algorithm.
In Green's virtual knot enumeration, crossing signs are appended to the unsigned codes in all possible ways to produce a set of signed Gauss codes within which Reidemeister equivalence classes are determined. Note that these are "signed minimal-cyclic un-signed" codes and not "minimal-cyclic signed" codes. In this enumeration the set of signed Gauss codes is filtered to produce a set of distinct over preferred Gauss codes and equivalence classes are constructed within this reduced set. Whilst the calculation of the over preferred form is computationally more expensive than the minimal cyclic form, the number of codes rises so rapidly with the number of components and the number of crossings that the duplication within the set of signed minimal cyclic un-signed codes makes the additional overhead worthwhile. In Green's code the data structures used to store and manipulate codes and equivalence classes are binary encoded unsigned integers, so whilst restrictive in application, fast computationally. In such an environment the duplication within the underlying set of Gauss codes is manageable. Since the objective here is to store Reidemeister data, the data structures are necessarily more complex, so the list needs to be as small as possible.
A simple example of the duplication that arises with minimal cyclic codes may be seen by considering the unsigned code O1O2O3U1U2U3. Assigning crossing signs - + + and + + - results in the two signed codes O1-O2+O3+U1-U2+U3+ and O1+O2+O3-U1+U2+U3-. These both happen to represent the unknot but they also have the same unoriented over-preferred Gauss code O1+O2+O3-U1+U2+U3-.
The second stage of the algorithm constructs a directed graph whose vertex set is the set of distinct over preferred Gauss codes. Two vertices are joined by an edge of the graph if there is a Reidemeister move that takes us from one vertex to the other. More specifically, the algorithm considers each over preferred code, C, and check whether C contains any Reidemeister II configurations . If it does, recursively perform as many Reidemeister II moves as possible, taking out any Reidemeister I configurations that are produced in the process, recording details of each move along the way. Then, evaluate the over preferred form for the reduced diagram to identify the neighbouring vertex. Next, look for Reidemeister III configurations in C and for each one that exists, perform the Reidemeister III move and remove any Reidemeister I configurations that it produces, again recording the details of each move and evaluating the over preferred form of the final diagram.
The data structure in the software that represents a graph vertex is called a code_list_element and the data structure that represents an edge of the graph is called a list_target. Thus, a code_list_element contains a set of list_targets, each one pointing to another code_list_element and each list_target contains the record of a number of Reidemeister moves that relate the two diagrams represented by the code_list_elements.
In the case of a Reidemeister II move being found taking diagram D1 to D2, since D2 contains fewer crossings than D1, there is no detectable Reidemeister move in D2 taking us to D1. We therefore construct a "reverse" list target from D2 to D1 with no Reidemeister moves when we construct the list_target from D1 to D2 corresponding to the Reidemeister II move, ensuring we always have an edge of the graph from a vertex v2 to v1 when there is an edge from v1 to v2.
Once the directed graph is complete, we construct equivalence classes of graph vertices where two vertices are equivalent if there is a sequence of Reidemeister moves that takes the diagram corresponding to one of the vertices to the diagram corresponding to the other.
Since the unknot or unlink is represented by an empty Gauss code, there is no graph vertex corresponding to the unknot. Reidemeister moves that result in the unknot are indicated by a list_target that points to an invalid value (-1) for a code_list_element. One can think of this as a "virtual edge" of the graph. As a result, the set of equivalence classes produced at this stage includes multiple trivial classes that are Reidemeister equivalent to the unknot but not to each other, other than via the unknot.
In the case of links, a sequence of Reidemeister moves may take a connected link to the disjoint union of two simpler links. In such cases, no further attempt is made to relate the disjoint union to other classes via its components, rather the class is left as being represented by that disjoint union. Note that one of the simpler links may be the unknot in some cases.
The last step of the process is to identify reflection symmetries between the non-trivial equivalence classes we have constructed. Reflections in the plane or in a line within the plane are identified and recorded within the equivalence_class data structures used by the software. The equivalence_class objects are stored in a list that implicitly orders the classes. Reflection symmetry between classes is recorded by a forward reference from an equivalence class to the first subsequent class that is related by reflection symmetry, if such a subsequent class exists. If an equivalence class is referenced in this manner, it records a list of all those preceding classes that refer directly or transitively to it.
Finally, the equivalence_class, code_list_elements and list_targets are written to a compact, colon-delimited, data file that may be used by another programme for analysis.
Two analytical capabilities are currently provided by the software. The first simply identifies amongst the equivalence classes those that have no forward reference to another reflectively symmetric class. The representative diagrams from these classes provide the candidate set of distinct knots or links that may be checked by other invariant calculating software to ensure that they are indeed distinct. It is these diagrams for two-component virtual links up to four crossings that are presented above.
The second tool takes two Gauss codes as input from the user, identifies the graph vertex corresponding to each code and determines whether they belong to the same equivalence class or not.
If the two codes belong to the same equivalence class a maximal tree is constructed within the sub-graph corresponding to that class, with root the first code. The sequence of Reidemeister moves that corresponds to moving up the tree from the second code to the root is described.
If the codes belong to different equivalence classes that are related to each other by reflective symmetry then the symmetry between the two classes is described, as applied to one of the codes. The Reidemeister moves between the reflected code and the other code is then described, as in 1.
If the codes belong to different trivial equivalence classes. they are both Reidemeister equivalent via the unknot. The Reidemeister moves that take each code to the unknot are described.
In the case of links, if either of the two codes belongs to an equivalence class that is represented by the disjoint union of two simpler links, then the Reidemeister moves taking the connected code to the disjoint union of links is described.
The software used to generate the above table and the database files below is available here: glist-src-1-1-23.tar. There are three separate programmes glist, gprocess and ganalyse.
The glist programme produces lists of unsigned minimal cyclic Gauss codes in an output file called glist.out. A example use of the programme is: glist -u --num-cpts=1 --num-crossings=5, the full syntax is as follows:
Usage: glist [-<short-option>] [--<long-option>]
<short-option>:
#: debug, see #H! for details
b: show component boundaries only (requires debug)
h: show help
u: unoriented search
S: produce signed Gauss code output
W: produce standard Gauss code output rather than OU format
#H!: display debug help screen
<long-option>:
num-cpts=n: number of components
num-crossings=n: number of crossings in the Gauss codes
the short options other than 'u' are for development and debugging purposes only.
For the next stage of the process, one or more output files from glist are places into the same directory and re-named glist-k where k is the number of crossings in the Gauss codes within the file. Thus to create the table above, files glist-2, glist-3, glist-4, glist-5 and glist-6 were created and stored in the same directory. The gprocess programme is typically run as follows gprocess -ue --num-cpts=1 --max-crossings=6 --filepath=., indicating that the glist files are present in the current directory and that a database output file should be produced. The full syntax is:
Usage: gprocess [-<short-option>] [--<long-option>]
<short-option>:
#: debug, see #H! for details
e: write equivalence class data to output file
h: show normal help
u: unoriented code lists
H!: show this help
#H!: display debug help screen
p: write element pointer list to output file
<long-option>:
filepath=<relative filepath>: specifies the location of the code lists
hash_threshold=n: only hash codes if the code list is longer than hash threshold, default=100
num-cpts=n: number of components
max-crossings=n: maximum number of crossings to consider
shift-power=n: the code_list_length is 2^n, where n is the shift-power, default=23
Again the other options are for development and debugging. The database output file is named gprocess.out but it can be renamed afterwards for processing with the analysis programme.
The ganalyse programme will either produce a candidate list of distinct non-trivial equivalence class representatives, for example as in ganalyse -cu gprocess.out, or allow the user to enter a pair of Gauss codes to see an explicit Reidemeister equivalence, if one exists, for example as in ganalyse -u --moves gprocess.out. The full syntax is:
Usage: ganalyse [-<short-option>] [--<long-option>] <input-file>
<short-option>:
#: debug, see #H! for details
c: write non-trivial distinct equivalence classes
e: write full equivalence class detail
h: show normal help
u: unoriented code lists
H!: show this help
#H!: display debug help screen
<long-option>:
compare: compare Gauss codes
moves: evaluate a sequence of Reidemeister moves between two Gauss codes
<input-file>: relative path to a file containing the output from gprocess
In order to prove that the above tables of two-component virtual links do not contain duplicates we require to demonstrate distinct invariants, or invariant combinations for each of the 170 diagrams shown in the tables. The following links provide consolidated lists of codes and various polynomial invariants for each of the diagrams, listed in the order shown above, in ascending order of the number of crossings.
Any one of the above invariants is insufficient to distinguish all 170 knots as the following output shows:
[bart@localhost local]$ sort -u arrow.out | wc
152 152 6611
[bart@localhost local]$ sort -u burau.out | wc
128 128 5272
[bart@localhost local]$ sort -u sawollek.out | wc
129 129 24233
However, taken together, all 170 links may be distinguished. The following link provides a collated set of arrow, Burau and Sawollek polynomials, separated by commas:
[bart@localhost local]$ sort -u collated-files.txt | wc
170 850 39321
The following are links to colon-delimited databases produced by gprocess.
The virtual knots with four crossings in gprocess-1-6.out have been verified to agree with Green's list of four-crossing virtual knots. The unoriented over-preferred Gauss code for each of Green's four crossing knots appears in the list produced from gprocess-1-6.out using the command ganalyse -cu gprocess-1-6.out, with the exception of 1 2 -1 -4 3 -2 4 -3/- - - +. From the file gprocess-1-6.out it can be seen that this code is the representative of equivalence class 82, which is replaced by the line and plane reflected class 177, represented by 1 2 -1 -4 3 4 -2 -3/- + - - in the list produced from gprocess-1-6.out.
An example session using ganalyse to analyse Reidemeister moves is shown below. Note that the database may be unable to detect Reidemeister equivalence if two codes are related only via a diagram with more crossings than the codes in the database.
[bart@localhost]$ ~/source/glist/ganalyse -u --moves gprocess-1-6.out
gprocess-1-6.out contains 387741 equivalence classes
created code hash list
Enter first Gauss code: 1 2 -1 3 -4 -2 -3 4/- - - +
Enter second Gauss code: 1 2 -1 -3 -2 -4 3 4/+ + - +
Codes are not Reidemeister equivalent
1 2 -1 3 -4 -2 -3 4/- - - + is the line reflection of 1 2 -1 3 -4 -2 -3 4/+ + + -
Diagram 1 2 -1 3 -4 -2 -3 4/+ + + - may be obtained from 1 2 -1 -3 -2 -4 3 4/+ + - + by:
Reidemeister III move involving over-arc crossings 4 and 1 and crossing 2
Enter first Gauss code: 1 2 3 -5 -2 -6 4 -3 5 -1 6 -4/+ + - + - +
Enter second Gauss code: 1 2 3 -1 4 -5 -2 -3 5 -4/+ - + + -
Both codes are Reidemeister equivalent to the unlink.
Reidemeister moves for first code:
Diagram unknot may be obtained from 1 2 3 -1 -5 -6 4 -3 -2 5 6 -4/+ + - + - + by:
Reidemeister II move 2 3
Reidemeister II move 2 3
Reidemeister I move 1
Reidemeister I move 1
Diagram 1 2 3 -5 -2 -6 4 -3 5 -1 6 -4/+ + - + - + may be obtained from 1 2 3 -1 -5 -6 4 -3 -2 5 6 -4/+ + - + - + by:
Reidemeister III move involving over-arc crossings 1 and 2 and crossing 5
Reidemeister moves for second code:
Diagram unknot may be obtained from 1 2 3 -1 4 -5 -2 -3 5 -4/+ - + + - by:
Reidemeister II move 2 3
Reidemeister I move 1
Reidemeister I move 2
Reidemeister I move 1
Enter first Gauss code: q
[1] A. Bartholomew, R. Fenn, N. Kamada, S. Kamada, On Gauss codes of virtual doodles (Journal of Knot Theory and Its Ramifications Vol. 27, No. 11, 1843013 (2018), arXiv:1806.05885 ).