872 is Minimal for Superpermutations on n=6

[Cole Fritsch]

A few weeks ago, I ran a computer search for superpermutations of length 871 that is based upon my lower bound and it found no results. I held off posting this since I seem to be quite prone to errors -- and indeed there were a few small errors in my code upon making it.

The search time is about 5 to 15 seconds -- I definitely overdid the optimizations. The Python code is attached and is given with the proof of my lower bound. The proof for the bounds used in the code are found in Appendix Section B.1. A summary of the proof is given in Section B.2.

A while back I also began overhauling the proof for the lower bound since I could not find a rigorous argument for an essential part of the proof -- I fixed this issue by reinterpreting what is being discovered.

The proof is in need of personal proof-reading: a lot of the proofs are dense and hard to follow. Being a college student, I simply do not have the time to proof-read the proof at the moment.

I am open to answer any questions you may have, but there may be a delay in my response since I will have exams scattered across the next few weeks.

~ Cole Fritsch

[Cole Fritsch]

The proof for Lemma 5.9 seems to be currently incorrect since it is a remnant of an earlier part of the proof, but I have already exhaustively tested these cases by hand, so I know that Lemma 5.9 holds anyway. I will update the proof when I find the time. 

Really, the proof for tau_6 edges ('132' 3-edges) involves considering two 3-cycle traversing paths together: one before the tau_6 edge, and one after the tau_6 edge. This means that Proposition 5.2 needs to be changed so that it can consider multiple 3-cycle traversing paths when I correct Lemma 5.9.

Additionally, there is a minor error in the python search code: line 138 should have an 'and' operator instead of an 'or' operator, however logic dictates that the search is still more than valid -- it even means that only one of those condition was necessary for the search.

That is all that I found in terms of errors as I proof-read part of the proof and the code. I know this is by no means an elegant proof, so if anyone doesn't understand a part of the proof, or has a suggestion, then let me know. I will try to answer it when I have the time.

- Cole Fritsch

[Tom S]

Hi Cole

At the top of page 8, how does V(x*) become E(x*)? I think V is bigger by 1?

Also, is there a good intuitive way to understand why the exitless loops can't self-intersect?

Tom

[Cole Fritsch]

Admittedly, I was a little vague in how I represented the Vertices and Edges in paths/path-segments. Basically, for all but the initial path segment, x*, the number of vertices and edges are the same. x* has one more vertex than edge since it contains the beginning and ends of the superpermutation path. Although I didn't make a note about that in the proof, I believe I did use the relation V(x*) = E(x*) + 1.

I don't quite understand what you mean by exitless loops and self-intersecting. In general, the superpermutation path cannot contain multiples of a permutations. Instead, we use what is called "improper edges" to skip over the repeated permutations -- these are the edges that can be "decomposed".

I'm not quite sure if that answers your questions. If not, then you can elaborate a little more on what you mean.

- Cole Fritsch

[Tom S]

OK cool

Since

| V(X_3) | = n! - V(X*) - E_1 |X_1| - E_2 |X_2| + nψ

 = n! - (E(X*) + 1)   - E_1 |X_1| - E_2 |X_2| + nψ

then I think we're missing a  -R_3 term in the first inequality on page 8. Which could affect the outcome of the paper unless it reappears somewhere and I've missed it.

Re: the self-intersecting exitless loops question:

When they've been defined we've been adding in permutations to the loops that already exist elsewhere, e.g. at the location of the early exit. So there are certainly duplicate permutations in the whole setup somewhere. My question was: can one of the loops intersect itself? Or is there some reason why the repeated permutations have to exist on separate loops? I think non-intersection might be being assumed in section 5 although I haven't scribbled through all the detail yet.

Regards

Tom

[Cole Fritsch]

I see. You are right about that equation and my derivation proof is wrong in that step based on how I defined E(x*) and V(x*), but it looks like I made up for it later in the w(x*) where I subtract the number of permutations from E(x*) rather than the number of edges in x*. Essentially, I just need to change E(x*) with V(x*) where it appears in this section of the proof and it will be right.

As for the self-intersecting exitless loop question, I see that it concerns the exitless cycle transformation. The transformation does indeed duplicate permutations: all of the permutations in the 1-cycle at which each early-exit exits from. The repeated permutations from the transformation are not actually repeated permutations in the superpermutation. To make sure that those permutations are not double counted we subtract nψ from the number of permutations.

We use the concept of "self-intersection" loosely through the proof. We of course do not consider all cases of self-intersection in the superpermutation-path (that would give the minimum-length superpermutation itself), instead we just try to minimize the chances of self-intersection as much as we can. In Section 5, we basically try to consider these intersection to the extent of bordering 3-cycle paths. Essentially, the more you account for self-intersections, the higher the lower bound. Does that cover what your asking?

- Cole Fritsch

[Cole Fritsch]

Okay, I fixed the E(x*) and V(x*) issue. Since I also referenced part of that proof in Proposition B.2, I changed it there as well. Originally, I used V(x*), but I changed it to E(x*) since it seemed to be more in line with E_1 and E_2 that I have already used. I must have used the incorrect relationship, " E(x*)=V(x*) ", making the equations wrong. I do expect there to be a few more small errors like that one scattered throughout the proof, but as I have mentioned previously, I don't have much free time to thoroughly proof-read this week/weekend.

- Cole Fritsch

[Tom S]

What does the exitless path transformation algorithm do to the (horrendous) example below?

n=5

123451543124512312543134512431251234...

There are 12 permutations in the above partial superpermutation. 10 are from the 1-cycles (12345) and (54312). There are loads of early exits.

I'm hoping the below comes out nicely typed in Google Groups! 

A 12345

B .23451

C  ...54312

D     ..31245

E       ...45123

F          ....31254

G              .12543

H               .25431

I                .....34512

J                     ..51243

K                     .....43125

L                          ....51234

The path segments as defined in step 1 are:

AB (early exit > I)

C (early exit > K)

D (early exit > elsewhere)

E (early exit > L)

FGH (early exit > C)

I (early exit > E)

J (early exit > elsewhere)

K (is this an early exit to F?)

L...

Step 2 asks us to add in edges to join early exits:

ABIEL... (path)

FGHCK (is this a loop to F? We can't continue to L because E does that...?)

Note in particular that H is now definitely joined to C via a 1 edge.

Step 3 asks us to put back in the edges we removed in step 1.

For the very first early exit at B we need to put back in the edge HI, then go the long way round via 1 edges to B, then add back in BC.

But H is already joined directly to C from step 2...?

[Cole Fritsch]

I am beginning to settle down for the day so I might have to continue this conversation tomorrow. The issue here is that the the exitless path transformation can only be used when all of the paths return back to the initial exitless path. In the sense of an arbitrary path of a defined permutation cover, this criteria can only be assumed true when V(p) = n! (i.e. it is a complete superpermutation path).

It is quite a hard concept to pick up so I totally understand the confusion. I will have to make a diagram of what is essentially going on when I find the time. I don't know if it will help, but Zach Hunter was the one who gets full credit for this concept so it may be helpful to read his procedure in his proof.

[Cole Fritsch]

Okay, I have made a sketch of what is happening with the exitless path transformation. I colored each of the parts of the path. Single, straight lines represent one or multiple 1-edges, double lines represent a 2-edge, triple lines represent a 3-edge, etc. I give dashed lines to give context as to what edges are where before and after the exitless path transformation. The "..." just means that the path may arbitrarily continue.

The left-most sketch is the superpermutation path and the right-most sketch is the what the graph would look like after the transformation. The direction of this path is irrelevant since it is symmetric This specific example is a peripheral cycle in X_1 -- given in light blue -- coming off of some arbitrary part of the path -- given in red -- on n=6 symbols.

Key:

Red = arbitrary part of an exitless path/cycle

Light Blue = arbitrary peripheral cycle off of the exitless path/cycle

Green = Edges that are shared due to the intersecting 1-cycle

Pink = the 1-edge that is in the intersecting 1-cycle that is not used in the Light Blue path

Dark Blue = the 1-edge that is in the intersecting 1-cycle that is not used in the red path

Yellow = the early-exit and early-return edges

We can actually show that each early-exit and early-return pair adds a weight of 'n' in the process of the transformation. The green edges are the edges that in the 1-cycle that are shared by both the red and light blue paths/cycles. There are 'n-2' green edges, each being double counted after the transformation. The only other change is the addition of the dark blue and pink edges which adds another '2' 1-edges. This makes the total additional weight after the transition 'n' per early-exit and early-return pair.

The concept of early-exits/returns allows us to think about peripheral cycles as appendages to the initial (kernel) path. The model is a little more difficult to figure out when you consider multiple early-exits between two peripheral cycles. I will need to look into it more, but the exitless path transformation appears to hold up in that case anyway so it is of low priority right now.

I have a physics exam tomorrow so this is the most I can help at the moment, unfortunately.

- Cole Fritsch

[Tom S]

Hi Cole

I hope your exam went well!

I've been looking through Zach's draft paper that you've linked.

His construction X does not seem to include the exitless loops you have in your X. It contains only paths.

Quote: "Lemma 5.7. Comps(X) is a set of paths."

To shore up your proof we'd need an algorithm to show how to turn Zach's X into your X.

This might be technically challenging.

One issue is that Zach has defined "early exit" based on the order that the first permutation in each 1 cycle appeared in the original superpermutation.

But when following your construction we will need to change this order around as we deal with each early exit in turn, which will get very messy.

e.g. If I add 2 permutations M ....43512 and N .35124 to the end of my (horrendous) example above

The initial exitless path from your paper must here begin ABIEL MNJ--    where ABIEL is a 1-cycle and MNJ is the start of another

But you'll notice that J occurred in the original superpermutation before M. In Zach's X we therefore have ABIEL be one exitless path, with J--MN in some separate path.

So your described general structure for X is not compatible with Zach's original definition of X.

Another issue is that we are potentially adding a lot of repeat 1-loops when building your X.

As you can see in my (horrendous) example, it is possible for a superpermutation to exit early from a 1-loop multiple times. Each time, your construction adds another copy of that 1-loop.

As I mentioned in my first reply, I'm not sure that it's obvious that an element of X_3 won't end up containing more than one of these copies, in which case it would self-intersect.

A lot of the discussion of X_3 in your paper assumes no self-intersection.

So I think that assuming the algebra in your paper contains no errors, you've only shown this lower bound for superpermutations with certain kinds of good behaviour - which need fleshing out in a bit more detail.

Regards

Tom

[Cole Fritsch]

My definition of early exit in this proof is quite poor at the moment and I may change it eventually. It is also definitely true that I need to discuss some topics like the ones you've mentioned more in the proof, but at the moment I am just trying to make it readable. I definitely did not base my concepts of early-exit and exitless path are not directly from his proof, I am just using the names since the ideas are more-or-less the same. I discovered the concept of early-exit independently of Zach Hunter (similarly to how Zach Hunter likely discovered early-exits/exitless paths independently of the kernel and extension approach), however, it was after reading his proof that I thought of it as a transformation.

You are right in that multiple early-exits can appear with in the same 1-cycle. This shouldn't matter since we subtract off the 'n' repeated permutations and the 'n' weight that comes with it every time we use an early-exit. Additionally, there can be multiple early-exits between two exitless paths/cycles and it does only occur with 'X_3', which was the case I said I needed to look into more before. However, these additional early-exits are accounted for in the 'zeta' variable. The multi-exit case has a strange consequence of two paths/cycles being the peripherals of each other.

-- Cole Fritsch

[Cole Fritsch]

In trying to fix Lemma 5.9, I realized that the current way I am proving Proposition 4.1 gets very complicated. Recently, I have discovered a new proof for Proposition 4.1 as a whole that will be more rigorous and easier to follow than the current one. I will be redoing almost the entirety of Section 5 for a while. Next, I will look into my description of exitless paths and early-exits.

I want to make it clear that this proof is not entirely complete yet. I am very much aware that there is some specific scenarios or details that I have left out of the proof at the moment. The proof as it is now is mostly to show the concept of the proof as I find ways to fit in those details I left out.