The lower bound n! + (n-1)! + (n-2)! + (n-3)

[Robin Houston]

I’ve attempted to write up the proof of this lower bound in a more or less coherent way: https://bosker.wordpress.com/2018/10/20/superpermutations-lower-bound/

I also thought it would be useful to start iterating towards a common language to use for talking about these cycle structures, since I think Greg Egan’s work involves the same structures.

Unfortunately my proof is currently incomplete: it doesn’t account for the case of a Hamiltonian tour that uses only edges of weight 1 and 2. Since that is the case Greg Egan has been thinking about, I wonder if his work can fill this hole. I’ll keep thinking about it too, and edit the linked post if I work it out!

Robin

[Robin Houston]

Further on having ways to talk about things: the structures I’ve called 2-cycles seem to be important, so it might be useful to be able to identify them. In the permutation graph for n symbols, there is a 2-cycle for each necklace of (n-1) symbols, which seems a reasonable way to label them. The nodes of this 2-cycle are precisely those in which those (n-1) symbols appear in a particular cyclic order.

For example the 2-cycle on n=4 labelled [123] is:

1234

2341

3412

4123

.

2314

3142

1423

4231

.

3124

1243

2431

4312

.

A pair of 2-cycles may be disjoint – e.g. [123] and [132].

Or they might overlap on a single 1-cycle, e.g. [123] and [142] overlap on the 1-cycle [1423].

Or they might have two 1-cycles in common, e.g. [123] and [124] have the 1-cycles [1234] and [1243] in common.

[Robin Houston]

Okay! I believe I have filled in the missing case, completing the proof. Please say if anything’s unclear, even if it’s just “I got lost at this point”.

Robin

On Sat, 20 Oct 2018 at 14:42 Robin Houston <robin....@gmail.com> wrote:

[Niles Johnson]

Thanks!  I haven't had the concentration to think through it carefully, but it looks reasonable.

I also found the argument you linked hard to follow (importantly, I think there are some typos where the indexing of the Ni is off by one).  But I did think the auxiliary parameters, X1, X2, were clever and interesting.  They can be thought of as functions which assign numbers to paths.  I didn't see an analogous notion in your argument, but maybe it's implicitly there?  Or do you just have a completely independent line of reasoning? (I'm partly just curious, and partly hoping your answer will help me understand your lower bound better :)

-Niles

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAD9Xfq2VTniqBQR2KntK3_%3DO67%3D0ZfvRRejRAD4y6Q%2B%2B%2Bvh64w%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Robin Houston]

Interesting! Yes, you’re right that mine is mostly an independent proof that I wrote after failing to understand the other one.

Of course, now I’ve thought about the problem hard enough to be able to write a proof, the other one suddenly seems very simple and natural. The idea of the non-decreasing measures is elegant, and seems to avoid the need to treat the case where all edges have weight 1 or 2 separately, which is a bit annoying. (Though it *is* interesting that one gets a better bound in that case, in the light of Greg Egan’s results.)

Robin

[Greg Egan]

On your blog, you write:

In a path where all edges have weights 1 or 2, we can never have n(n-1)-1 consecutive edges that all belong to the same 2-cycle, except right at the end of the path, because if they did the next edge (of weight 1 or 2) would visit a node in the same 2-cycle, which must have already been visited.

I can see why this is true if the section of the path starts with a run of (n-1) 1s, e.g. for n=3 if we have the n(n-1)-1 = 5 weights 1 1 2 1 1 , then that is enough to paint you into a corner where choosing 1 next closes a 1-cycle, and choosing 2 next closes the 2-cycle.

But suppose you begin at a different point on the 2-cycle, so you have the 5 weights 1 2 1 1 2. Another edge of weight 1 would close the 2-cycle, but you could choose a 2 after this and leave the 2-cycle. Similarly, the 5 weights 2 1 1 2 1 could be followed by a 2 that leaves the 2-cycle.

[Greg Egan]

My choice of counterexamples wasn’t very good, because for n=3 the edge sequence 2 2 is itself a cycle, and there is only a single 2-cycle covering the whole group.  But hopefully the general idea is still clear.  For n=4, an edge sequence like:

1 2 1 1 1 2 1 1 1 2 1

contains n(n-1)-1 = 11 edges all on the same 2-cycle, and you can follow it with a 2 without closing the cycle.

[Robin Houston]

Thank you so much for checking this carefully! You are right, of course. Clearly I was far too hasty with the 1/2 case.

The wikia proof is starting to look better and better…

Robin

--

You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/e197889e-223e-456c-bd19-7545ad03b6de%40googlegroups.com.

[Robin Houston]

So… if the wikia proof looks like our best bet for proving this bound, we ought to check that we can make it rigorous.

I’ll reformulate the method in terms of paths in the permutation graph, and explain where I think some additional rigour is needed. I feel somewhat optimistic that this is possible, but I don’t think I’ve quite got there. (I hope it is possible, because if this proof falls apart too then we’re back to square one.) Comments, as always, are very welcome.

Define the permutation graph on n symbols G_n to be a weighted directed graph whose nodes are all the permutations of the symbols. It has n! nodes, labelled by the permutations of the n symbols regarded as strings. It is a complete graph, i.e. for any two nodes A and B there is an edge e: A→B, and the weight w(e) of this edge is the length of the shortest string that has A as a prefix and B as a suffix, minus n.

Let’s say a path of length n is a sequence alternating between nodes and edges, x_0, e_0, x_1, e_1, ..., x_n, where each x_i is a different node and each e_i is an edge from x_i to x_{i+1}. The weight w(p) of a path p is the sum of the weights of its edges. A cycle is like a path except that x_0 = x_n.

An edge e: A→B of the permutation graph is improper if there is a path p: A→B of length > 1 with w(p) ≤ w(e).

The edges of weight 1 form a cycle cover consisting of disjoint cycles of n nodes, which we call 1-cycles. Two nodes belong to the same 1-cycle iff their labels are cyclically equivalent, e.g. 1234 and 3412 belong to the same 1-cycle in G_4.

Define a 2-cycle to be a cycle of n(n-1) edges, alternating between runs of (n-1) weight-1 edges and single proper weight-2 edges. Note that distinct 2-cycles may overlap.

The idea of the wikia proof is to define three functions on paths in the graph, x0, x1 and x2, and to argue by induction on the path that

  w(p) ≥ x0(p) + x1(p) + x2(p) - 3

for all paths p.

The functions are:

• x0(p) is the number of nodes in the path p, i.e. one more than the length of p;
  
• x1(p) is the number of complete 1-cycles in p, plus 1 if the last node of p belongs to a 1-cycle that is not completely in p.
• x2(p) is the “number of 2-cycles visited”, noting that “The tricky thing about 2-[cycles] is that which 2-[cycle] you're in depends on the point at which you entered the current 1-[cycle].”

The intention is that x1 depends only on the nodes (not the edges) in the path p: the path p contains a complete 1-cycle just when every node of the 1-cycle is a node of p. So the only one of these definitions that presents any real difficulty is x2.

Next let’s recap the proof, as a reminder of what properties the function x2 needs.

If e is an empty path (on any node), then w(e) = 0, x0(e) = 1, x1(e) = 1 and x2(e) = 1, hence the base case holds.

Now let p be a path, and let e be an edge whose source is the last node of p and whose target is x. We’re extending p to the longer path p' = p + (e, x). For the induction it suffices to show that:

  w(p') - x0(p') - x1(p') - x2(p') ≥ w(p) - x0(p) - x1(p) - x2(p)

or, equivalently, since w(p') - w(p) = w(e) and x0(p') - x0(p) = 1,

  w(e) ≥ 1  +  x1(p') - x1(p)  +  x2(p') - x2(p).                   (*)

If w(e) = 1 then x1(p') = x1(p) and x2(p) = x2(p'), which satisfies (*).

If w(e) ≥ 3 then (*) is also satisfied, since x1(p') - x1(p) ≤ 1 and x2(p') - x2(p) ≤ 1 necessarily for any edge e.

The interesting case is where w(e) = 2. The key lemma that makes this work is: if x1(p') - x1(p) = 1 then x2(p') = x2(p). If e is an improper edge then x1(p') = x1(p) necessarily, so the interesting case is where e is a proper edge. The condition x1(p') - x1(p) = 1 holds just when the nodes of p consist of complete 1-cycles.

The final step is to argue that when p is a Hamiltonian path, we have x0(p) = n!; x1(p) = (n-1)! and x2(p) = (n-2)!. This last equation assumes that the 2-cycles considered to have been “visited by” p are disjoint from one another.

So we need to define a notion of which 2-cycles a path p has “visited” that has the following properties:

• adding a single edge to the path visits at most 1 additional 2-cycle;
• adding a weight-1 edge to the path visits no additional 2-cycles;
• if the nodes of p consist of complete 1-cycles, adding a proper weight-2 edge to the end of p visits no additional 2-cycles.
• the 2-cycles visited by p are pairwise disjoint.

I have to stop for now. I’ll send this as is in the hope that someone will say “Oh, that’s easy!” and explain how to do it.

Robin

[Robin Houston]

I think I have it!

Although different 2-cycles may have some of the same nodes (and weight-1 edges), they have disjoint sets of weight-2 edges. (And every proper weight-2 edge belongs to some 2-cycle.) Let’s say that the 2-cycle determined by a node y is the unique 2-cycle that contains the (unique) proper weight-2 edge → y.

Now define the set of 2-cycles visited by a path p as follows: for every edge e: x→y in p with w(e) > 1, include the 2-cycle determined by y. Also include the 2-cycle determined by the initial node of the path p, so that x2(e) = 1 for a zero-length path e as required by the base case.

This satisfies the first three of the four conditions above. The fourth is not actually necessary: the requirement that the 2-cycles visited by a path be pairwise disjoint is bogus, since if x2(p) > (n-2)! for a Hamiltonian path p, that strengthens the bound rather than weakening it. All that we need is that x2(p) ≥ (n-2)! for a Hamiltonian path p, which this definition does satisfy.

Finally we should check that the “key lemma” holds for this definition. Let p be a path whose nodes consist of complete 1-cycles, with final node x. There is a unique weight-1 edge from x, say e: x→y, where y is already in p and e is not. Therefore y must either be the initial node of p, or the target of a different edge (with weight > 1). In either case the 2-cycle determined by y is counted by x2(p). And the proper weight-2 edge from x is included in this 2-cycle, so x2(p') = x2(p) where p' is p followed by the proper weight-2 edge from x. Which is the conclusion we needed.

Robin

[Niles Johnson]

excellent!!  (still haven't read carefully, but I like the direction this is going :)

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/CAD9Xfq3WKaV2Jvb2hSoQCJj-cJnHL9XvWpbYFOzMcrnouMvwjg%40mail.gmail.com.

[Greg Egan]

I’ve gone through this as carefully as I can, and I’m pretty sure it’s right.  It’s really hard to pick correct definitions here and to be sure about all possible cases, but I think you’ve done it — I certainly can’t see any flaws.  Well done!

[Robin Houston]

Thank you! I was worried no one would have the time or energy to check it carefully. It’s very kind of you.

So this together with your improved upper bound brings the gap between the two down to (n - 3)!

I’m in awe of the anonymous anime fan who came up with this beautiful, subtle proof. I’ll see if there’s any way to get in touch with him/her.

--

You received this message because you are subscribed to the Google Groups "Superpermutators" group.
To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee5f4514-f376-4d00-b7a3-a54bcc76f3d0%40googlegroups.com.

[Jay Pantone]

Thanks for your proof Robin! I also happened to spend a long time yesterday understanding the lower bound, and I think we are mostly in agreement. If I'm understanding your proof correctly, I think there is a small gap. You claim:

The key lemma that makes this work is: if x1(p') - x1(p) = 1 then x2(p') = x2(p).

but I'm not sure this is true. It seems to me that you could take a 2-step in the middle of a 2-loop, and if the cycle you're leaving has already been completed. then x0, x1, and x2 all increase by 1. (You can rule this out if you prove that a permutation is never re-visited in a superpermutation, but to my knowledge we haven't proved that yet. As a side note, I think that will be an important step to making the upper and lower bounds meet.)

I wrote a short note explaining how I read the proof, using the easier lower bounds as a warmup. I handle the gap I mentioned above in the long, tedious paragraph in the middle of page 3. My notation is a little hand-wavy, but I didn't think it was worth rewriting just yet. Let me know if any parts don't make sense!

And thanks for gathering so much interest around this problem. 

On Tuesday, October 23, 2018 at 3:16:02 AM UTC-5, Robin Houston wrote:

Thank you! I was worried no one would have the time or energy to check it carefully. It’s very kind of you.

So this together with your improved upper bound brings the gap between the two down to (n - 3)!

I’m in awe of the anonymous anime fan who came up with this beautiful, subtle proof. I’ll see if there’s any way to get in touch with him/her.

On Tue, 23 Oct 2018 at 08:44, Greg Egan wrote:

I’ve gone through this as carefully as I can, and I’m pretty sure it’s right.  It’s really hard to pick correct definitions here and to be sure about all possible cases, but I think you’ve done it — I certainly can’t see any flaws.  Well done!

On Tuesday, October 23, 2018 at 3:48:33 AM UTC+8, Robin Houston wrote:

I think I have it!

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

[Robin Houston]

Ah, interesting! What a convenient coincidence. I haven’t read your document yet, but I shall read it later today.

From what you say here, it sounds as though you and I are using different definitions of the relationship between superpermutations and walks in the graph. Since I’ve never actually explained the way I’m thinking about it, it’s not surprising there’s some confusion!

In my formulation, the relationship between superpermutations and paths in the graph is one-to-many in general (in the case where some permutation occurs more than once in a superpermutation). To convert a superpermutation to a path in the graph, you have to *choose* an occurrence in the superpermutation of each permutation; the path visits the chosen occurrences in the order they appear in the superpermutation.

An edge in the graph that “skips over” one or more unchosen permutations is what I call an improper edge.

So, although a superpermutation may contain the same permutation several times, the corresponding path in the graph nevertheless visits each node only once.

The only superpermutations that cannot be represented in this way are those in which there is a run of > n consecutive symbols that complete no chosen permutation – and these are clearly not minimal.

Does that make it clearer?

Thanks,

Robin

On Tue, 23 Oct 2018 at 14:56 Jay Pantone <jay.p...@gmail.com> wrote:

Thanks for your proof Robin! I also happened to spend a long time yesterday understanding the lower bound, and I think we are mostly in agreement. If I'm understanding your proof correctly, I think there is a small gap. You claim:

The key lemma that makes this work is: if x1(p') - x1(p) = 1 then x2(p') = x2(p).

but I'm not sure this is true. It seems to me that you could take a 2-step in the middle of a 2-loop, and if the cycle you're leaving has already been completed. then x0, x1, and x2 all increase by 1. (You can rule this out if you prove that a permutation is never re-visited in a superpermutation, but to my knowledge we haven't proved that yet. As a side note, I think that will be an important step to making the upper and lower bounds meet.)

I wrote a short note explaining how I read the proof, using the easier lower bounds as a warmup. I handle the gap I mentioned above in the long, tedious paragraph in the middle of page 3. My notation is a little hand-wavy, but I didn't think it was worth rewriting just yet. Let me know if any parts don't make sense!

And thanks for gathering so much interest around this problem. 

On Tuesday, October 23, 2018 at 3:16:02 AM UTC-5, Robin Houston wrote:

Thank you! I was worried no one would have the time or energy to check it carefully. It’s very kind of you.

So this together with your improved upper bound brings the gap between the two down to (n - 3)!

I’m in awe of the anonymous anime fan who came up with this beautiful, subtle proof. I’ll see if there’s any way to get in touch with him/her.

On Tue, 23 Oct 2018 at 08:44, Greg Egan wrote:

I’ve gone through this as carefully as I can, and I’m pretty sure it’s right.  It’s really hard to pick correct definitions here and to be sure about all possible cases, but I think you’ve done it — I certainly can’t see any flaws.  Well done!

On Tuesday, October 23, 2018 at 3:48:33 AM UTC+8, Robin Houston wrote:

I think I have it!

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee5f4514-f376-4d00-b7a3-a54bcc76f3d0%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

You received this message because you are subscribed to the Google Groups "Superpermutators" group.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/e29c1b87-0a52-417c-8201-e38178c56102%40googlegroups.com.

[Robin Houston]

I’ve read your document now. Looks good to me!

It seems my guess was right: you exclude “improper edges” from your directed graph, and represent a superpermutation as a walk that may visit the same node more than once. As you say, this necessitates a more complicated argument to establish the “key lemma”.

(But the way I did it necessitates a more complicated description of the relationship between superpermutations and paths in the graph, and an argument that the superpermutations that cannot be represented by such a path cannot possibly be minimal. So maybe overall it’s a wash.)

Best wishes,

Robin

[Jay Pantone]

Here's the one place where I'm still confused about your proof: In the end, you make the same claim that I do, that x0(p) = n!, x1(p) = (n-1)!, and x2(p) >= (n-2)!, where p is the path for any superpermutation. In your model, every path must pass through all n! nodes in the graph. It seems to me like there are superpermutations that can be formed without actually visiting all the nodes! If a permutation appears in the "middle" of an improper edge somewhere, we then we might never need to actually visit its nodes. In these superpermutations, it might be that x0(p) < n!.

Am I missing an argument that shows that this isn't really a problem?

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee5f4514-f376-4d00-b7a3-a54bcc76f3d0%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

[Robin Houston]

Dear Jay,

I think I haven’t described my argument very well, and you are objecting to a different argument that I didn’t make.

To make sure I understand: you believe my argument establishes that every Hamiltonian path in the graph has weight at least n! + (n-1)! + (n-2)! - 3, but you doubt this implies that every superpermutation has length at least n! + (n-1)! + (n-2)! + (n - 3)?

My idea is to start with a superpermutation S of length |S|, and from it to derive a Hamiltonian path H(S) in the graph whose weight is at most (|S| - n). Then n! + (n-1)! + (n-2)! - 3 ≤ w(H(S)) ≤ |S| - n, hence |S| ≥ n! + (n-1)! + (n-2)! + (n - 3).

Take a superpermutation S, which is to say a word over the alphabet N = {1, …, n} that has each permutation of N as a factor of length n. For each permutation p of N, choose a factorisation S = ApB and let i_p = |A|. (If p occurs more than once in S then there is more than one factorisation to choose from. Choose any one.) Sort the set of permutations of N by index, so that p precedes q iff i_p < i_q. Let the sorted list of permutations be s_1, s_2, …, s_{n!}, so i_{s_j} < i_{s_k} iff j < k.

The corresponding Hamiltonian path H(S) visits the nodes s_1, s_2, …, s_{n!} in order. If e_k is the edge s_k → s_{k+1} then w(e_k) ≤ i_{k+1} - i_k, since the substring S[i_k, i_{k+1} + n] has s_k as a prefix and s_{k+1} as a suffix, hence

    w(H(S)) ≤ \sum_{k=1}^{n-1} i_{k+1} - i_k = i_n - i_1 ≤ |S| - n.

Does this make any more sense?

Best,

Robin

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee5f4514-f376-4d00-b7a3-a54bcc76f3d0%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/e29c1b87-0a52-417c-8201-e38178c56102%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

You received this message because you are subscribed to the Google Groups "Superpermutators" group.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutato...@googlegroups.com.
To post to this group, send email to superper...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee95265a-c969-48a0-840d-89f33d3b6ac4%40googlegroups.com.

[Jay Pantone]

Ah, now I understand where your walk comes from. Clever argument!

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/ee5f4514-f376-4d00-b7a3-a54bcc76f3d0%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/superpermutators/e29c1b87-0a52-417c-8201-e38178c56102%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Superpermutators" group.

To unsubscribe from this group and stop receiving emails from it, send an email to superpermutators+unsubscribe@googlegroups.com.
To post to this group, send email to superpermutators@googlegroups.com.

[Vince Vatter]

Thanks for the clarifications, Robin.

Jay's first proof was just his attempt to explain the 4chan proof with as few modifications as possible. Since he posted that, I've been working with him to try to write a cleaner proof. The result of this attempt is attached. It follows the general outline of the 4chan proof, but also incorporates a couple clever ideas from your proof, Robin.

Comments and requests for clarification are of course most welcome.

[Roberto Colombari]

Hi Everyone!
I wasn’t aware of the Haruhi problem up to these days, when someone on 4chan gave a kind of solution.

I had a look on it and I’d like to post here my approach.

The shortest string containing all the permutations of n digits occurs when you are able to take advantage of the maximum overlap between each permutation, obviously.

Given a permutation of n digits, I can find at maximum (n – 1) different permutations that grant the maximum overlap (n – 1) with an overall length of (2n – 1) digits.

Than I have to lower down to an overlap of (n – 2) for finding a new different permutation that grants other (n – 1) different ones with maximum overlap (n – 1); this new series has length equal to 2n – 1 – (n – 2) (I’m subtracting n – 2 because of the overlap with the previous permutation series).

Lets call L a string of n permutations with overlap (n – 1) between them.

I can put in a row (n – 1) L strings with overlap between them equal to (n – 2) than I have to lower down to (n – 3) for being able to create a new block.

Here it follows the L string lengths for n = 5:

L1 => length 9 (2n – 1)

L2 => length 6 (2n – 1 – (n – 2) for the overlap with L1)

L3 => length 6

L4 => length 6

_______________________________________

L5 => length 7 (2n – 1 – (n – 3) for the overlap with L4)

L6 => length 6

L7 => length 6

L8 => length 6

_______________________________________

L9 => length 7 (2n – 1 – (n – 3) for the overlap with L8)

L10 => length 6

L11 => length 6

L12 => length 6

_______________________________________

L13 => length 7 (2n – 1 – (n – 3) for the overlap with L12)

L14 => length 6

L15 => length 6

L16 => length 6

_______________________________________

L17 => length 7 (2n – 1 – (n – 3) for the overlap with L16)

L18 => length 6

L19 => length 6

L20 => length 6

_______________________________________

L21 => length 7 (2n – 1 – (n – 3) for the overlap with L20)

L22 => length 6

L23 => length 6

L24 => length 6

Total = 152

Lower bound formula = n^2(n – 2)! + n – 3

Hope my post could be of interest.

Best regards.

[Greg Egan]

Hi Roberto

What you describe here doesn't give a strict lower bound that we can be sure applies in all generality, because it is tied to a particular way of structuring the superpermutation.  That way of structuring things, recursively, with uniform blocks of maximum overlap of n-1, then n-2, and so on, has been treated as the standard way of building a superpermutation for 20 years, but we now know (since discoveries by Ben Chaffin and Robin Houston) that it is not unique, and not always the most efficient way.

To get a strict lower bound, we need to consider  every possible way of structuring the superpermutation, not just that particular approach.

Best wishes

Greg

[Roberto Colombari]

Hi Greg,

I'm not too much inside this topic, maybe it's really not the best way.

By the way, if you look at my lower bound formula it seems to be the same as n! + (n-1)! + (n-2)! + n - 3.

n! + (n-1)! + (n-2)! + n-3 = (n-2)!(n^2 - n + n - 1 + 1) + n - 3 = n^2(n - 2)! + n - 3

Bests