The n-Category Café

Here’s your picture. My method of displaying it here is inelegant, but the picture itself is very pretty! Thanks for creating it!

Why shorter than Fiore’s? Both have 18 moves, unless I miscounted, and Fiore’s has overall fewer terms.

For what it’s worth (not much), I don’t think this more symmetrical proof is due to George Bell. If I remember correctly, this is the same proof as appears in Pierre Ageron’s nice little book Logiques, ensembles, catégories : Le point de vue constructif. And to tap into an even more distant memory, I think I remember Marcelo coming up with it independently when we were working on this stuff. The point is that you can do all the expanding moves first, and all the contracting moves last. I believe we chose the one we did for the reason Todd stated: it has fewer terms.

Of course, it doesn’t matter who found the more symmetrical proof first. I just wanted to mention Pierre’s book, which is a gem. Unfortunately no part of it seems to be online, and I don’t have my copy here. And of course it’s in French (unfortunate for some, fortunate for others).

I don’t know of any proof shorter than 18 moves.

Some believe it is the shortest possible proof along these lines:

Sentences like that Ought Not To Be Allowed. It’s extremely irritating. Whilst suffering from jetlag, I came up with the following reasoning. Any errors should be blamed on the airline, but of course if it’s true then I claim all credit for myself (though I guess that to do that I ought to post it twice and only claim the credit in the second posting).

We start by observing that the very last move must be a fusion $B^6 + B^8 \to B^7$. That is the only way to end up with a single $B^7$. Thus at some point we must have, by fission, produced a $B^8$. To do this starting at $B^1$ we must have had fissions at $B^1$, $B^2$, …, $B^7$. A total of 7 fissions.

As was remarked elsewhere in this discussion, we can always arrange things so that all fissions happen first and all fusions last. Within the sequences of fissions and fusions we can rearrange providing cause-and-effect is maintained (that is, if one fission produces the particle that is involved in the next fission then we cannot swap the order of these two). Thus we can order things so that these 7 fissions happen first, in the obvious order.

Now let us consider the final moves. We have generated a $B^0$. We therefore have to fuse that into the final $B^7$. This involves fusions at $B^1$, $B^2$, …, $B^7$ (where I label a fusion by the position of the resulting particle). This produces 7 fusions. Again, we can assume that these fusions are the last moves to occur.

This yields a total of 14 moves. However, we cannot do a “cut and shut” with these 14. Not yet. They don’t fit together. The first seven moves yield

$$B^0 + B^1 + B^2 + B^3 + B^4 + B^5 + B^6 + B^8$$

whereas the last seven require the starting point

$$B^0 + B^2 + B^3 + B^4 + B^5 + B^6 + B^7 + B^8$$

It is clear what is needed. We need to exchange the $B^1$ in the first line for the $B^7$ in the second.

Ed: Err, hang on? Wasn’t that where we started? Isn’t the point of this to swap those two? What were we doing for those 14 moves then?

Now we use the factorisation

$$B^7 - B = (B^2 - B + 1)(B^5 + B^4 - B^2 - B)$$

to see that to swap the $B^1$ for a $B^7$ takes four moves: fissions on $B^6$ and $B^5$ and fusions on $B^3$ and $B^2$. This is the minimum number of moves providing they can be carried out.

In our original universe of a single solitary particle at $B^1$, these four moves could not be carried out. However, in our new fabulous universe they can. We can therefore swap $B^1$ for $B^7$ in just four moves.

Thus the total is 18. The middle four (in this arrangement) are the key moves in the swap. The first seven consist of creating a universe in which these four moves can be carried out, and the last consist of the “clean up” crew getting rid of the junk.

It might be tempting to think that if all we need are fissions at $B^5$ and $B^6$ and fusions at $B^3$ and $B^2$ then our minimum initial state for doing the swap should only reach to $B^6$ and not $B^8$. Whilst it is true that one can begin the swap earlier in the game, this does not shorten it. Essentially, if you start before you lay out all the pieces as I did above then you take longer to clean them up again afterwards. The two diagrams in John’s comment illustrate this: the first one begins the “key moves” at the earliest point possible whereas the second lays out all the preparations first before doing the key moves. They are, however, the same length because the first approach requires much more “cleaning up”.

However, rather than analysing each possible starting point separately and showing that shortening the initial stage merely lengthens the final stage, it’s simpler to reorder the moves and see that the minimum is 18.

Cool! It would actually make a fun game for the mathematically inclined, trying to get from one position to another in as few moves as possible. Line up a bunch of students with boards and have a ‘race’!