Pattern in the "negative space"

[Randy Olsen]

I would like to share an OEIS sequence that grows quite similarly to the minimal superpermutation length pattern (which you can see even from the known bounds, so independent of the prediction scheme I posted), and how I encountered this sequence, meaning how I think it relates to the minimal superpermutation problem.

1)  Here is the sequence: https://oeis.org/A288780

2) I found this by searching on "2,9,36,165" which I will presently show are the "negative space" totals in constructions of the respective n = 2, n = 3, n = 4, and n = 5 minimal superpermutations such that all the individual permutations "stick around" in the process.  It is like saying the individual permutations can extend orthogonal to the superpermutation or bend away from the superpermutation, but they don't just "get absorbed" by it.  Here, I will just type out the cases for n = 2, n = 3, and n = 4 and I will link to my spreadsheet work for n = 5.  You will be able to read the minimal superpermutations as the continuous vertical columns and you will see the individual permutations branching or bending off of the superpermutations:

n = 2:

_1

_2

21

The underscores represent what I call the "negative space" and the total is 2 for n = 2.

n = 3:

123

231

3__

12_

213

132

3__

2__

1__

Again, the underscores are the "negative space" and appear in a section of 3 and a section of 6, for a total of 9.

n = 4:

1234

2341

3412

4___

123_

2314

3142

1423

4___

231_

3124

1243

2431

4___

3___

12__

2134

1342

3421

4___

213_

1324

3241

2413

4___

132_

3214

2143

1432

4___

3___

2___

1___

The total negative space in the n = 4 case is 36, given four sections of 4, one center section of 8, and a final section of 12.

3) Here is my Microsoft One Drive Excel spreadsheet work for n = 5 "negative space": https://1drv.ms/x/s!Ap4I-rXcEKcQjUbvgvwM8fQTz9PN?e=LceDR9

4) On the message chain about my prediction scheme for minimal superpermutation length values I mentioned at one point no longer being able to see the cell formulas as an outside viewer, but I've been able to see the formulas when viewing through the Microsoft Edge browser.

5) Separately, in case not everyone here saw it, the online Quanta magazine published an article recently about progress a few researchers made on the Traveling Salesperson Problem. https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/

[Jelmer Firet]

Dear Randy,

I don't fully understand how you define the negative space, but based on the spreadsheet this seems like the number of wasted characters in disguise.

From the site superpermutations.net:
"By a “wasted” digit, we mean one that, when added to the string, did not add a (new) permutation. We don’t count the first 5 [=k-1 for a superperm with k symbols] digits as wasted."

If you call the number of wasted digits in the minimal superpermutation over k symbols wasted(k) then your negative space can be calculated as follows:
negative space(k) = k*(wasted(k)+k)=k*(minlen(k)-k!+1)

It seems to match https://oeis.org/A288780 until k=6; for k=7 an upper bound on the negative space then is 7*(5906-7!+1)=7*867=6069, which is less than the 6111 given in that OEIS sequence. So the negative space probably won't give us more insight than the wasted characters.

I wasn't aware of the improvement to the TSP. The improvement they managed is quite small, but it provides new techniques. Since the superpermutation problem is a special case of TSP this new technique might help, but I don't really have time at the moment to look into it.

Kind Regards,

Jelmer Firet

[phil.and...@gmail.com]

I see differences in the TSP examples given: 1) that the endpoints are far vs close, and 2) how many cities that are passed by on the last stretch to make a "round" trip that are close to the rest of the paths. But isn't mathematically visualizing it just simplex?

Interestingly, I think the amazing superpermutations work here might be able to contribute to TSP round trips using the original improvement with the coordinate system that spawned all of this - perhaps by "superpermutating" into fuzziness how many endpoints are considered rather than just 1. Maybe up to 6 or 7 instead since that's computationally not too hard any longer. (So complete the shortest one way path, then delete the last ~6 links, and either do coordinates or brute force it like they did with sudoku14).

[Randy Olsen]

Fun, and possibly even meaningful (or hopefully at least thought-provoking), correspondence to another sequence in OEIS: https://oeis.org/A294400

To show this, I have another spreadsheet linked at bottom, but first I should address what Jelmer Firet pointed out and attempt to explain better how I define the negative space.

For the negative space values as I calculate them, the formula from Jelmer needs a "minus k" at the end, so

negative space(k) = k*(minlen(k)-k!+1) - k

This works up to n = 5 (I will now use 'n' instead of 'k'), and also for the best-known results for n =6 and n = 7.  I concur the connection was a good observation by you Jelmer, so thanks for that, and I also concur we start getting divergence from A288780.  However, I wonder if the particular manner of divergence might be a clue for us.  At n = 6 the difference is 6 (from 918 minus 912) and at n = 7 the difference is 49 (from 6111 minus 6062).  For n = 8 could the difference then be 512 (that is, 8^3)?  I have run with this idea in my current spreadsheet.

To find visually the negative space, here is the procedure (other than n = 2 which is 2 by inspection):

Write a minimal superpermutation down vertically.  Then, start out with each row as a transpose of length n.  Many of the rows will be individual permutations, but not all rows.

Start reading the rows left to right.  When you get to a row that is not an individual permutation, it will have some repeated digit from earlier in the row.  Look ahead to see if the immediate next row or rows also have that problem, and jump to the last one in the set.  Start carving out the "negative space" by deleting the repeated digit and anything to the right of it on that row.  Then, as what is still left on that row can be read as an individual permutation when combined with the leftmost digit in a previous row or rows, retroactively delete out all but the left column in the applicable preceding row(s).  For example, if I see

4123

1231

2314

then my procedure leaves me with

4___

123_

2314

and the individual permutation 4123 ends up "recorded" as a bent permutation in the n = 4 minimal superpermutation.

Similarly, the permutation 4312 gets "recorded" as bent in a different place from taking

4312

3121

1213

2134

to

4___

3___

12__

2134

The exception to this procedure is just at the very end of the superpermutation, when you end up with a clean rectangle of "negative space" because you can just write the last permutation vertically, and you don't keep rows of length less than n, so the last two individual permutations for n = 4 show up as:

1432

4

3

2

1

I hope this suffices for explanation.  Given its visible nature, I continue using the "negative space" rather than converting to the "wasted digit" terminology in my new spreadsheet, which again demonstrates a correspondence to a different sequence in OEIS.  I am showing a surprising (at least to me) correspondence with OEIS A294400 through n = 8 and also maintain "near agreement" through n = 11:

https://1drv.ms/x/s!Ap4I-rXcEKcQjWyzrq_OZ28Tk6lC?e=WztXPr

[Randy Olsen]

Important update: Persisting correspondences with (n-1)^2 - 2 (see A008865 in OEIS as a reference, as it is just n^2 - 2) from n = 4 and through n = 15 (as far as I have taken the calculations thus far.)  I altered my extrapolation of difference between A288780 and the minimal superpermutation negative space from n^(n-5) to n*(minlen(n-4) - 2) which has made things just as interesting if not more so!

https://1drv.ms/x/s!Ap4I-rXcEKcQjW52YTX3ByWOlyLC?e=4LDmv9

[Randy Olsen]

A second round of the minimal superpermutation negative space stepping away from A288780 starts at n =10.  For the first round, n = 6 to n = 9, the length of the n-4 minimal superpermutation is key and the adjustment from A288780 as I wrote in the last message is n*(minlen(n-4) - 2).  In the second round starting at n = 10, the adjustment should become n*(minlen(n-4) - 2) + n*(minlen(n-8) - 2), so there is a second term.  Then at n = 14 a third round would start and give the offset from A288780 as n*(minlen(n-4) - 2) + n*(minlen(n-8) - 2) + n*(min(n-12) - 2).  Although I have not yet made another version of my latest spreadsheet, one can see this pattern as what would be needed to reconcile the two different predictions for minimal superpermutation negative space.  The upshot of all this for minimal superpermutation lengths is that we would continue seeing linear gains with respect to beating the upper bound.  I'm still pretty happy then with my original minimal superpermutation length predictions up to n = 11 (as 43948802 is 6 below the upper bound for n = 11), but I might need to revisit n = 12 and larger.  It is possible the "snap to the upper bound" I predicted after n = 11 is an artifact of the n^(n-5) trend that I was using in one part of my scheme just not tolerating the constraints of the minimal superpermutation problem anymore, is one guess.