# Antisymmetry, Corners of the 3x3x3 Cube, quarter turn metric

Distance Positions Positions Positions from reduced reduced Start by by Symmetry Symmetry and Anti-Symmetry 0 1 1 1 1 12 1 1 2 114 5 5 3 924 24 17 4 6539 149 96 5 39528 850 469 6 199926 4257 2289 7 806136 16937 8768 8 2761740 57848 29603 9 8656152 180787 91688 10 22334112 466220 235710 11 32420448 676786 342593 12 18780864 392342 199610 13 2166720 45600 23818 14 6624 163 110 Total 88179840 1841970 934778

As I have written before, my programs have seldom worked with positions. They have nearly always worked with representative elements of M-conjugate classes. In the table above, the summary of representative elements is labeled "Positions Reduced by Symmetry". The goal of this approach is to obtain a 48 times speedup in processing time, and also to obtain a 48 times reduction in storage requirements.

Four or five years ago I did write a little program that dealt with all 88179840 positions of the corners of the 3x3x3 cube instead of just dealing with representative elements. The program was intended as a proof of concept, using a bijection to map between the positions of the corners and a table of lengths for each position. The table contained 88179840 cells to store the lengths. This is an old, old concept and has been done many times before. I do note that the running time was about 15 minutes, whereas when the problem was first solved back in the 1980's the running time was over 24 hours. That's a reflection of the improvements in computer hardware rather than a reflection of improvements in algorithm.

The next step in the "proof of concept" was to reduce the problem by symmetry, working only with representatives of M-conjugate classes. This time, there were only 1841970 positions to deal with. But I stored the length information for those 1841970 positions in the same table of lengths as before (the table containing 88179840 cells). Using the same table worked because the representative elements are positions. So I continued to use the same bijection to map between the representative elements and the table as I had used when I was using all 88179840 positions. I suppose that strictly speaking, we should now call the bijection a function because it's no longer a bijection, but it's still exactly the same computer code.

This approach is a very inefficient use of space, with only about 1/48 of the table cells being used. That means that 47/48 of the table is wasted. However, there was a tremendous speedup in running time. The whole thing ran in just over 20 seconds. It's not quite a 48 times speedup, but it's close. You can't get the full 48 times speedup because of the extra processing associated with calculating symmetry.

I don't think it's ever possible to achieve a complete 48 times reduction in storage by using symmetry. When you don't reduce the problem by symmetry, you don't have to store any positions at all, you just have to store lengths. But when you do reduce the problem by symmetry, you either have to store the representative elements plus their lengths, or else you have to use a hashing technique such as symmetry coordinates. In the case of representative elements, you have to store additional information about each position. In the case of symmetry coordinates, the hash table is not 100% efficient (if I understand correctly how it works). So either way, you don't get quite the complete 48 times reduction in storage.

In any case, my next step was to move from storing the lengths of the representatives sparsely within the table of 88179840 lengths to storing the representatives themselves plus their lengths in a variety of data structures, mostly binary trees of various kinds. I sort of ran out of interest at that point.

I recently resurrected the same program to calculate the corners of the 3x3x3 reduced by both symmetry and antisymmetry. In a perfect world, I think you should strive for both a 96 times speed up and also a 96 times reduction in storage. In this case, I just did a quick and dirty hack of the program and there was no speedup over the speedup I had already obtained from symmetry, and there was no storage reduction over the storage reduction I had already obtained from symmetry. I just added a counting routine for antisymmetry.

The quick and dirty counting routine works as follows. It is assumed that if I did a proper program taking full advantage of antisymmetry, I would work with antisymmetry representatives. Namely, if I had a position x, I would calculate the symmetry representatives y=Rep(x) and z=Rep(x^{-1}). The antisymmetry representative would then be the minimum of y and z. For most positions, this approach will reduce the size of the search space by 2 because y and z will not be equal. But occasionally y and z will be equal. In these cases, there is no reduction. Therefore, in order to count antisymmetry representatives, as symmetry representatives were being identified a counter for the antisymmetry case was incremented any time Rep(x) was less than or equal Rep(x^{-1}). It only took five or six extra lines of code to include this calculation.

I've been thinking about what would be required to take full advantage of antisymmetry, rather than just accounting for it in a quick and dirty fashion. With respect to storage, I would store antisymmetry representatives as described above, yielding about a 2 times storage reduction on top of the storage reduction from symmetry. But I can't convince myself that antisymmetry would provide any processing speedup at all. Here's what I think the problem is.

For each symmetry representative x, I calculate all the neighboring positions as y=Rep(xq) for all q in Q (the set of quarter turns), and similarly for the face turn metric. Each x has 12 neighboring positions (or 18 in the face turn metric). But if I were working with antisymmetry representatives, it seems to me that it would be necessary to calculate for each representative x not only y=Rep(xq) for all q in Q, but also y=Rep(x^{-1}q) for all q in Q. So the number of representatives would be cut in half, but the number of neighbors that would have to calculated would have to be doubled from 12 to 24 (and from 18 to 36 in the face turn metric). Therefore, there would be no speed up at all. Am I missing something?