Link Tabulation Algorithm


It is time now to use all the theory already presented, in order to construct the "Link Tabulation Algorithm". This algorithm can then be converted to a computer program, that can be compiled and run, in order to yield specific results. Currently the computer program is "under construction": preliminary versions have already yielded the first few topologically distinct links (up to 9 crossings at this moment), but more work needs to be done, so that the program can be as "efficient" as possible.

In a manner similar to the case of knots, one starts by requesting for two input parameters: one of them, NF, indicates the maximum number of crossings to be considered, while the other, Nc, indicates the "maximum permutation group" that is going to be used for the "colorization" invariants.

Once we fix the input values, we initialize a variable N equal to 1. This variable indicates the number of crossings, and is going to be incremented until it exceeds NF. For each successive value of N, we consider all N-permutations (starting from p(i)=i and ending at p(i)=N+1-i). Each such permutation denotes a possible knot shadow notation, where 2i-1 is paired to 2p(i). Each such notation has to fulfill two properties, in order to be considered for further "study".

First, the notation must be ordered "ahead" of equivalent notations (i.e. the ones where every i is replaced either by i+c, or by i-c). Second, the notation must be "drawable" (consistent crossing signs, and number of areas equal to N+2).

Once a notation satisfies these conditions, we consider all possible combinations of "types" of crossings (i.e. some crossings are real, some are artificial). Each such combination yields a link "shadow". We discard shadows that have already appeared. In particular, we discard shadows where there are "too many" artificial crossings: ideally, if all crossings are real, the link consists of one component (is a knot), while for each artificial crossing the number of components should increase by 1. If this is not the case and the number of components is less than number of artificial components plus one, the emerging shadow has already appeared for a smaller number of crossings, and is thus discarded. Finally, we check for non-prime links. For N < NF - 1 such links must be kept only for "accounting purposes", while for N equal to NF or NF-1, they can be discarded.

Once a link shadow has been selected, we consider all possible combinations of "over/under" crossings, for each real crossing. We now continue working in a manner similar to the case of knots. On each such "link presentation" we perform equivalence moves that do not increase the crossing number. If these do not yield any presentation "ahead" of the one under consideration, then the link is stored into memory for "further use". If it does, then we continue performing moves until we reach notations that have already been stored into the memory. Such notations are going to be mapped to the one that is "ahead" of all the others.

When this part of the program has been completed (i.e. when N would start being equal to NF+1), we proceed to the second part. Here, only the notations that were passed into the memory and were mapped to themselves, are going to be considered.

We are now going to calculate the various invariants of these notations, until: either we show that they are all distinct, or exhaust the invariants that we are planning to use. We start with the first invariant, which is the number of components. We then proceed with the second invariant, which is the set of the absolute values of the linking numbers.

We now start calculating the various "colorization" invariants, that are determined through the conjugacy classes of the permutation groups. We thus consider the various permutation groups S(1), S(2), ..., S(Nc), where Nc is the second input parameter. As one may recall from the study of knots, each invariant corresponds to a distinct partition of n, where n takes values from 1 to Nc. In contrast to the case of knots, we do not use the HOMFLYPT (or the Kaufman) polynomial, since they may take different values for links that consist of the same points, but whose components may not have all the same orientation.

To view the preliminary results obtained up to this point, you may click here.

Charilaos Aneziris

Copyright 2001


Educational institutions are encouraged to reproduce and distribute these materials for educational use free of charge as long as credit and notification are provided. For any other purpose except educational, such as commercial etc, use of these materials is prohibited without prior written permission.