Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 16, 2009

Searching for a Video Proof of “Seven Trees in One”

Posted by John Baez

James Propp asks:

Can you steer me toward the YouTube video of someone using pebble-moves to prove that x 61x^6 - 1 is a multiple of x 2x+1x^2 - x + 1, by starting with a single pebble and managing to move it six spaces to the left (or maybe it was to the right?) with moves that replace a pebble at nn with pebble at each of n1n-1 and n+1n+1, and other moves that do the reverse?

The argument goes back to Andreas Blass’ paper Seven trees in one — he used it to give a nice bijection between the set of binary planar trees and the set of 7-tuples of such trees. The argument was generalized by Robbie Gates and later Marcelo Fiore and Tom Leinster. I discussed it in week202 of This Week’s Finds. But I don’t remember a video proof!

James Propp adds:

I’m pretty sure I learned about it from your This Week’s Finds series, but searching your site on the obvious keywords only led me to Week 202, which has some relevant stuff but doesn’t provide the link I was seeking.

I say pebbles, but I use the term generically to refer to counters, tokens, or chips of any sort.

Here’s a similar argument that proves

B1+B 2BB 7B \simeq 1 + B^2 \implies B \simeq B^7

This picture is taken from Fiore’s paper Isomorphisms of generic recursive polynomial types:

At each step he either replaces B nB^n by B n1+B n+1B^{n-1} + B^{n+1}, or the reverse. At each step he underlines the one or two terms that he’s about to replace.

But where’s the video?

Posted at July 16, 2009 9:59 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2015

25 Comments & 0 Trackbacks

Re: Searching for a Video Proof of “Seven Trees in One”

That’ll be me.

Posted by: Dan Piponi on July 16, 2009 3:43 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

I’ve put together a diagram (using xymatrix in Latex) illustrating the sequence of moves from Fiore’s paper, but I have no idea how to post it here. (None of the Text Filters seem to know what to do with it, unless I’m doing something wrong). I’ve put a version of it here which unfortunately isn’t very clear. If someone can help me post the original xymatrix diagram embedded in a comment here, I’ll do that.

Posted by: Stuart on July 16, 2009 4:42 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

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

Posted by: John Baez on July 16, 2009 7:01 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

Ah, that’s great, thanks for putting it up. I have a higher-resolution version of it if you’d prefer, and if there’s a convenient way for me to get it to you.

Posted by: Stuart on July 16, 2009 7:18 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

I made a jpg file of what I saw on your webpage, and linked to that. I just realized now that what you had on your webpage was a gif! So, you or I could have just included a link to that.

Anyway, if you can send me a jpg or gif or png with higher resolution, that would be nice. My email address, mutilated to avoid spam, is on my webpage.

Posted by: John Baez on July 16, 2009 8:27 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

Here is a (somewhat uglier) rendition of the alternative (more symmetric but more crowded) derivation due to George Bell here in the thread that Dan Piponi pointed to.

B 1 B 2 1 B B 3 1 B B 2 B 4 1 B B 2 B 3 B 5 1 B B 2 B 3 B 4 B 6 1 B B 2 B 3 B 4 B 5 B 7 1 B B 2 B 3 B 4 B 5 B 6 B 8 1 B B 2 B 3 B 4 2B 5 B 7 B 8 1 B B 2 B 3 2B 4 B 5 B 6 B 7 B 8 1 B 2B 3 B 4 B 5 B 6 B 7 B 8 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8 B B 3 B 4 B 5 B 6 B 7 B 8 B 2 B 4 B 5 B 6 B 7 B 8 B 3 B 5 B 6 B 7 B 8 B 4 B 6 B 7 B 8 B 5 B 7 B 8 B 6 B 8 B 7 \array{ &&B\\ &\swarrow&&\searrow\\ 1&&&&B^2\\ \downarrow&&&\swarrow&&\searrow\\ 1&&B&&&&B^3\\ \downarrow&&\downarrow&&&\swarrow&&\searrow\\ 1&&B&&B^2&&&&B^4\\ \downarrow&&\downarrow&&\downarrow&&&\swarrow&&\searrow\\ 1&&B&&B^2&&B^3&&&&B^5\\ \downarrow&&\downarrow&&\downarrow&&\downarrow&&&\swarrow&&\searrow\\ 1&&B&&B^2&&B^3&&B^4&&&&B^6\\ \downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow&&&\swarrow&&\searrow\\ 1&&B&&B^2&&B^3&&B^4&&B^5&&&&B^7\\ \downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow&&&\swarrow&&\searrow\\ 1&&B&&B^2&&B^3&&B^4&&B^5&&B^6&&&&B^8\\ \downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow&\swarrow&&\searrow&&&\downarrow\\ 1&&B&&B^2&&B^3&&B^4&&2B^5&&&&B^7&&B^8\\ \downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow&\swarrow&\downarrow&\searrow&&&\downarrow&&\downarrow\\ 1&&B&&B^2&&B^3&&2B^4&&B^5&&B^6&&B^7&&B^8\\ \downarrow&&\downarrow&&&\searrow&\downarrow&\swarrow&\downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow\\ 1&&B&&&&2B^3&&B^4&&B^5&&B^6&&B^7&&B^8\\ \downarrow&&&\searrow&&\swarrow&\downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow\\ 1&&&&B^2&&B^3&&B^4&&B^5&&B^6&&B^7&&B^8\\ &\searrow&&\swarrow&&&\downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow\\ &&B&&&&B^3&&B^4&&B^5&&B^6&&B^7&&B^8\\ &&&\searrow&&\swarrow&&&\downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow\\ &&&&B^2&&&&B^4&&B^5&&B^6&&B^7&&B^8\\ &&&&&\searrow&&\swarrow&&&\downarrow&&\downarrow&&\downarrow&&\downarrow\\ &&&&&&B^3&&&&B^5&&B^6&&B^7&&B^8\\ &&&&&&&\searrow&&\swarrow&&&\downarrow&&\downarrow&&\downarrow\\ &&&&&&&&B^4&&&&B^6&&B^7&&B^8\\ &&&&&&&&&\searrow&&\swarrow&&&\downarrow&&\downarrow\\ &&&&&&&&&&B^5&&&&B^7&&B^8\\ &&&&&&&&&&&\searrow&&\swarrow&&&\downarrow\\ &&&&&&&&&&&&B^6&&&&B^8\\ &&&&&&&&&&&&&\searrow&&\swarrow\\ &&&&&&&&&&&&&&B^7\\ }

Posted by: Tim Silverman on July 16, 2009 9:56 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

Hmm, not actually more symmetric. But maybe less twiddly.

Posted by: Tim Silverman on July 17, 2009 12:15 AM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

However, these aren’t precisely the moves in Dan’s YouTube video, which has twenty moves. His demonstration is, if I’m not mistaken,

000000010
000000101
000001011
000010111
000101111
001011111
010111111
010020111
010011011
010010101
010010010
101010010
110110010
111020010
111111010
111110100
111101000
111010000
110100000
101000000
010000000

which is nicely symmetric about the pivot point in the middle, involving first, fourth, and seventh powers of a placeholder x.

Posted by: Todd Trimble on July 17, 2009 4:30 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

Symmetry seems quite general in these solutions, perhaps not surprisingly (why do twice the work!)

Posted by: Tim Silverman on July 17, 2009 4:58 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

There’s yet another way of thinking about seven trees in one, in terms of walks.

Let W nW_n be the ‘space’ of all walks on the natural numbers starting at position nn, where with each tick of the clock, you take either one step left or one step right. Then the sequence (W n) n=1 (W_n)_{n = 1}^\infty of spaces has period 66. See here for explanation.

Posted by: Tom Leinster on July 16, 2009 6:15 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

I know this hasn’t the same effectiveness as a video, but one can always look at frames…

* 0 * * * 0 0
0 * 0 * * 0 0
0 0 * 0 * 0 0
0 0 * * 0 * 0
0 0 * * * 0 *
Posted by: some guy on the street on July 16, 2009 6:32 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

Here are two picture proofs that

BB 2+1 B \simeq B^2 + 1

implies

BB 7 B \simeq B^7

They were created by Stuart Presnell.

The first, which we’ve already seen in lower resolution, shows Marcelo Fiore’s proof:

The second proof, which Tim Silverman already drew for us, is due to George Bell. Some believe it is the shortest possible proof along these lines:

Posted by: John Baez on July 17, 2009 9:36 AM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

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

Posted by: Todd Trimble on July 17, 2009 4:11 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

Okay, I guess it’s not shorter than Fiore’s. I guess it could be ‘as short as possible’. And I think we all have to agree with Tim Silverman: it’s definitely less twiddly.

Posted by: John Baez on July 17, 2009 4:26 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

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.

Posted by: Tom Leinster on July 18, 2009 2:10 AM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

You’re right. It’s on page 29 of Pierre Ageron’s book.

Posted by: Gonšalo Marques on July 18, 2009 10:09 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

I finally used Tom’s information to update the Addenda to week202.

I didn’t realize saying a proof was ‘due to’ somebody meant that they were the first to come up with it. I thought it just meant they came up with it on their own. I guess I need a more unambiguous phrase, when I say this sort of thing. Maybe something like “I saw George Bell give this proof on that blog…” (I had the feeling he independently invented it, instead of finding it in a book.)

Posted by: John Baez on July 25, 2009 6:55 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

I didn’t realize saying a proof was ‘due to’ somebody meant that they were the first to come up with it.

Well, I thought that was how people used the phrase. Let’s say, for instance, that as a precocious schoolboy I figured out the equation e iθ=cosθ+isinθ e^{i\theta} = \cos \theta + i \sin \theta all on my own. I don’t think I’d be very popular if I made a habit of writing “we now use the equation e iθ=cosθ+isinθe^{i\theta} = \cos\theta + i\sin\theta, due to Leinster.”

(I did no such thing, incidentally.)

Posted by: Tom Leinster on July 26, 2009 12:49 AM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

Unless it is an alternate proof
in which case perhaps: THIS proof is due to…
but still for the first person to provide a full proof

Arnol’d once (or more) commented that Theorems are often named for the second person to discover them. ;-)

Posted by: jim stasheff on July 26, 2009 3:40 AM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

Arnol’d once (or more) commented that Theorems are often named for the second person to discover them.

Well, John knows this. In fact, it's been called ‘Baez's Law’, because Arnolʹd said it first.

Posted by: Toby Bartels on July 26, 2009 7:16 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

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 8B 7B^6 + B^8 \to B^7. That is the only way to end up with a single B 7B^7. Thus at some point we must have, by fission, produced a B 8B^8. To do this starting at B 1B^1 we must have had fissions at B 1B^1, B 2B^2, …, B 7B^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 0B^0. We therefore have to fuse that into the final B 7B^7. This involves fusions at B 1B^1, B 2B^2, …, B 7B^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 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 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 1B^1 in the first line for the B 7B^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 7B=(B 2B+1)(B 5+B 4B 2B) B^7 - B = (B^2 - B + 1)(B^5 + B^4 - B^2 - B)

to see that to swap the B 1B^1 for a B 7B^7 takes four moves: fissions on B 6B^6 and B 5B^5 and fusions on B 3B^3 and B 2B^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 1B^1, these four moves could not be carried out. However, in our new fabulous universe they can. We can therefore swap B 1B^1 for B 7B^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 5B^5 and B 6B^6 and fusions at B 3B^3 and B 2B^2 then our minimum initial state for doing the swap should only reach to B 6B^6 and not B 8B^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.

Posted by: Andrew Stacey on August 10, 2009 12:45 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

James Propp points us towards yet another blog entry on this puzzle:

Posted by: John Baez on July 17, 2009 10:52 AM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

He he! This is fun!

Bother. The filters won’t let me post either my fantastic perl script which generates these diagrams, nor the SVG that it results in.

Anyway, I’ve written a Perl script that allows one to play with this by specifying moves. Anyone who wants a copy can email me and ask for it, or wait until I stick it up on my own webpage (sometime next year).

The script generates the xymatrix syntax for producing the diagrams. That can then be converted to SVG using PHPLaTeX, though the SVG that it produces doesn’t get through the sanitiser here (memo to self: bug Jacques about that).

Anyway, fun game! Thanks, everyone.

Posted by: Andrew Stacey on July 17, 2009 9:47 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

Hey all,

Excellent timing! I’m currently running the research portion of the summer math institute at Cornell, and one of the groups is working on a generalization of the 7-trees theorem (actually an extension of the Objects of Categories as Complex Numbers paper). They put together a video last night showing the process with dot diagrams:

SMI 7-Trees

I’m hoping that they can make a couple of “special features” on Monday that demonstrate some of the more interesting algebraic structures that appear in these computations…

Posted by: Matt Noonan on July 18, 2009 1:37 PM | Permalink | Reply to this

Re: Searching for a Video Proof of “Seven Trees in One”

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’!

Posted by: John Baez on July 27, 2009 11:09 AM | Permalink | Reply to this

Post a New Comment