The Blog of Scott Aaronson

*Quantum computers are not known to be able*

to solve NP-complete problems in polynomial time,

and can be simulated classically with exponential slowdown.

to solve NP-complete problems in polynomial time,

and can be simulated classically with exponential slowdown.

Comment #1 October 19th, 2007 at 10:17 am

It’s a great video and I am really glad that they made it. I own a copy. But it is evil to say that

everymath talk should be like this. Some people really believe that, or half-believe it. When they have their way, a lot of math never gets discussed.There is a related, long-known phenomenon in physics classes. Everyone remembers the cool demonstrations as the best part of physics classes. The demonstrations are a great motivator and if I taught physics, I would have them too. But it turns out that the more demonstrations you have, the less the students learn. The students drink them in without thinking for themselves.

Comment #2 October 19th, 2007 at 10:37 am

Ah, Greg my friend … who else can I count on to use the word “evil” unironically when discussing mathematical pedagogy?

Comment #3 October 19th, 2007 at 10:58 am

What can I say? I am paid to care about this.

Comment #4 October 19th, 2007 at 1:09 pm

“The turning number is the number of smiles minus the number of frowns”

That makes me happy

Comment #5 October 19th, 2007 at 1:18 pm

And yes Greg, the best part about physics lectures are the cool demonstrations. The memory of my Prof. solving the two-body Problem still almost makes me pee my pants.

Comment #6 October 19th, 2007 at 2:05 pm

What is more amazing is that it describes a series of moves developed by Bernard Morin, a French mathematician (now retired) who is blind.

Comment #7 October 19th, 2007 at 4:37 pm

Can someone motivate the rules for the transformation? Were they picked because they made the problem difficult but not impossible?

Comment #8 October 19th, 2007 at 4:48 pm

anonymous: Yes. As the video points out, if you allow neither self-intersections nor tearings then it’s trivially impossible, while if you allow tearings (or self-intersections plus creasings) then it’s trivially possible. Out of eight possible problems, that leaves only one nontrivial one: that of self-intersections but no tearings or creasings. And mathematicians gravitate toward nontrivial problems, for the anthropic reason that if they didn’t they wouldn’t be mathematicians.

Comment #9 October 19th, 2007 at 5:00 pm

The “with no cuts or creases” part only sounds intriguing when one conveniently does not mention that the material can pass through itself..

What a sham.

Comment #10 October 19th, 2007 at 5:08 pm

Eelis: Well, would

youhave guessed it was possible under those assumptions? Could you have figured out how to do it?Comment #11 October 19th, 2007 at 6:59 pm

Scott: The moment they announced in the video that the material could pass through itself, I could not help but think “Oh, sure, if you give yourself that kind of freedom, it does not surprise me in the least that it is possible”. But that does not necessarily mean that I would have been able to convince myself of the possibility of turning a sphere inside out under these assumptions, or that I would have been able to come up with the procedure myself; not being surprised by a result does not mean one would have been able to arrive at it oneself.

Comment #12 October 19th, 2007 at 8:10 pm

Although Scott, replying to anonymous, is mathematically correct, he is historically inaccurate. Mathematicians did not set out to prove this fact. Steve Smale (look him up on Wikipedia) proved a general theorem on immersions of manifolds in his PhD thesis. During the defense, some older topologist (Eilenberg?) expressed doubt that the theorem was correct. When asked why, he replied “because you can’t turn a sphere inside out”. Eventually he and others were convinced that the result was correct but a visual way of seeing this only came later, with the work of Morin (as Deja vu pointed out).

Comment #13 October 19th, 2007 at 10:27 pm

Kinda like how, even though I doubt I could prove it myself, I would not be surprised in the least if P were, in fact, not NP?

Comment #14 October 19th, 2007 at 11:06 pm

This video got me thinking in the same direction as anonymous and Eelis. It is a well made video but the rules are too “pure math”, so the “turning inside out” comes across as false advertising. Also, for what it’s worth, I really doubt the audience they’re targeting this at would understand the transformation, or the constraints.

Comment #15 October 19th, 2007 at 11:10 pm

is it odd that i want to guess that you cannot turn a torus inside out with the same rules? also, who started thinking about this? they mention that it was first proved in 1957, how long had it been considered before that, and why?

Comment #16 October 19th, 2007 at 11:35 pm

Scott,

Thanks for a wonderful link! I believe lots of fundamental math can be visualized and taught to general public this way, but it requires diligent team work to produce such a video. The problem is how to motivate mathematicians and programmers to get together and work in this direction, and, of course, who would pay for this work :).

BTW, it’s somewhat off-topic but let me advertise my own math prize problem. It’s on my website

http://www.stasbusygin.org

The prize amount is $1000.

Comment #17 October 19th, 2007 at 11:47 pm

Ninguem: The (not much) older mathematician was Bott,

who was Smale’s advisor (and I believe he made this comment

before the defense..) Also the first construction was due not to Morin but to Arnold Shapiro (see Tony Phillips’ great Scientific

American article on this) – Morin’s is I think more beautiful but came later. There are also great illustrations of sphere eversions in the amazing “Topological Picturebook” by George Francis.

Comment #18 October 20th, 2007 at 12:50 am

When I read the your post, my first thought was,

“What every math talk should be like”: On research 40 years old Smale’s paradox (wikipedia) .

But I guess you aren’t being entirely serious (and neither am I).

Comment #19 October 20th, 2007 at 2:13 am

What is more amazing is that it describes a series of moves developed by Bernard Morin, a French mathematician (now retired) who is blind.Morin’s role in this is definitely amazing, but I think the eversion actually shown in the movie is a later one due to Thurston rather than Morin.

Comment #20 October 20th, 2007 at 1:17 pm

Among the funders of this excellent video was the Dept. of Energy. How it fits into a coherent energy strategy escapes me.

Comment #21 October 20th, 2007 at 1:55 pm

Any idea why they went with sixteen sections? It looks like three, or maybe even two, should work just fine.

Comment #22 October 21st, 2007 at 4:04 am

John Sullivan also has a nice sphere eversion called the “optiverse”. It uses the Boy surface (immersion of RP^2) as a half-way point for the eversion, but he runs the whole eversion through a process that minimizes the bending-energy through the eversion. If you have a chance to watch it, do. John is at TU Berlin.

Regarding “why sixteen sections”, I never sat down to think through how few you could get by with. Maybe 2 would work. The reason so many were used was to get the corrugation idea across — that this idea could in principle be used to prove the general Smale-Hirsch theorem. I don’t think they say that in the video.

The homotopy-classes of eversions of the sphere turn out to be in natural bijective correspondence with Z + Z/2 (a free abelian group direct sum 2-element cyclic group). I’ve wonder if this corrugation technique would be of aid in explicitly generating the whole family of eversions.

And to motivate the rules for turning the sphere inside-out: the rule is that at every stage you have to have an immersion, that is a smooth function from the 2-sphere to R^3 so that the derivative has full rank. It’s a ‘basic concept’ from the point of view of multi-variable calculus in that it is a map which is locally an embedding. But outside the confines of calculus it’ll probably seem artificial.

Comment #23 October 21st, 2007 at 4:12 am

PS: if you’re lazy and want to try 2 corrugations, go to Google and type in “sphere eversion thurston” and you’ll find either the original software to compute that animation in Minnesota, or some variant of it at a U. Toronto webpage. Compile it and tell it to use 2 corrugations — the code lets you choose whichever number you want. It was written largely by Nathanial Thurston, if I remember correctly.

Comment #24 October 21st, 2007 at 5:00 am

I think I spelled Nathaniel wrong.

cody: I think the torus can be turned inside-out, if what you mean is “is there a 1-parameter family of immersions that starts at the ‘standard’ immersion of the torus in R^3 and ends at some mirror-reflection of it?” In this case, Smale-Hirsch says there’s 4 components to the space of immersions, and mirror reflection preserves each component. Now that I think about it, Smale-Hirsch seems to have the same answer for every surface in R^3 — they can all be turned inside-out. Off the top of my head I don’t `see’ an eversion of the torus.

Comment #25 October 21st, 2007 at 5:17 am

Ah, there is a ‘cheap’ inversion of the torus. It uses two main ingredients: 1) any inversion of the sphere and 2) the observation that the standard torus in the 3-sphere separates the 3-sphere into two solid tori. The ideas piggy-back on each other.

The idea can be souped-up to give an inversion of any closed orientable surface in R^3. I’m getting sleepy. I could whip out a bunch of formalism but it doesn’t seem like the place. The proof just needs a couple pictures.

Comment #26 October 21st, 2007 at 5:46 am

Regarding Scott’s original comment: computers (and mathematicians) are too slow to make all math talks like outside-in.

Here’s some `on the cheap’ videos demonstrating a theorem about quadrisecants on a knot and the geometry of the convex hull:

http://math.rybu.org/makeknot.2-3.mpeg

http://math.rybu.org/pqqp.2-3.fat.mpeg

That’s the best I’ve been able to do, so far.

Comment #27 October 21st, 2007 at 7:34 am

“who else can I count on to use the word “evil” unironically when discussing mathematical pedagogy?”

Well, Fields Medalist Laurent Lafforgue got fired from the High Committee on Education for comparing the education experts of the french ministry of education to Red Khmers, without the slightest hint of irony, as far as I understand the text in French.

http://www.ihes.fr/~lafforgue/dem/courriel.html

Comment #28 October 21st, 2007 at 11:05 am

Ryan,

Thanks for the comments!

I think I was cocredited with Nathaniel for the program

for the eversion, can’t remember what they wrote in the official description. (Of course 16 was an arbitrary choice, just seemed to look best around that width.)

Outside In was started as an idea of Bill Thurston and Silvio Levy. They got me and Matt Headrick (as college freshmen – it was supposed to be our “work-study”) to start developing animations for the eversion at the Geometry Center. For a while it was just the two of us working under Silvio’s supervision. After a while Nathaniel realized we were hopeless as programmers (though we had

the formulas for the eversion, we wrote it in a pretty amazingly slow Mathematica program) and rewrote the code. Meanwhile we worked on the script (at some point Matt wanted to concentrate on physics work and stopped coming to the geometry center). Eventually the project gathered momentum and lots of the geometry center experts – especially Tamara Munzner (and Delle Maxwell, and all the others you can see on the credits) – took over and I was designated “sphere movie evangelist”, mainly going around and getting people enthusiastic about the project. (For the credits Nathaniel and Matt and I first thought I think to have the sphere everting back and forth between Smale and Bill Thurston’s faces..)

Anyway it was a wonderful experience.. the geometry center was a pretty magical place to me, and I was very sad to see it go.

Comment #29 October 21st, 2007 at 11:18 am

Would it still work using only two sections of very different sizes, such as one nearly full section and a tiny one? What about a single section split by a single guide?

Comment #30 October 21st, 2007 at 2:05 pm

What motivated this kind of research? I guess as Scott pointed out: mathematicians have to sometimes manufacture problems for themselves or else they would be out of a job =p.

But really, is there a practical application?

Comment #31 October 21st, 2007 at 2:16 pm

“What every math talk should be like”

Yeah, can’ t you just imagine how much more fun talks in complexity theory would be with animation.

“Here’s a Turing machine. It’s like an automatic mechanical typewriter. Look, it has written a 1 on the tape. Exciting, can we see that again?”

Comment #32 October 21st, 2007 at 2:26 pm

Here’s a brief history of the motivation which I take as “pretty much” accurate:

1) Hassler Whitney unified the various competing notions of “manifold” and proved that all n-dimensional manifolds embed in Euclidean 2n-dimensional space. His proof (called the “hard whitney embedding theorem”) used a technique for removing opposite pairs of double points from an immersion — a map that is locally an embedding, but globally maybe not. This, I think is the main motivation — that all manifolds embed in some Euclidean space in a sense solves a mental riddle that goes back to “the earth is flat”/”the earth is round” debate.

2) People began to notice that the study of immersions was significantly “easier” than studying embeddings, yet non-trivial enough to still require some work, and frequently immersions are close-enough to embeddings to give you useful information. Early theorems of this type were the Whitney-Graustein theorem that classified immersions of the circle in the plane.

3) Steve Smale, in his dissertation souped-up the Whitney-Graustein theorem to the point where he could “classify” immersions of the circle in any 2-dimensional manifold.

Shortly after graduating, he got on a tremendous “roll” and proved a landslide of beautiful theorems, one being that the sphere could be turned inside-out.

On a more personal note, until I had seen the sphere turned inside-out I was not convinced mathematicians had anything non-trivial to say. It helped to convinced me to take mathematics seriously. I was a microbiology student at the time.

Comment #33 October 21st, 2007 at 2:50 pm

“Here’s a Turing machine. It’s like an automatic mechanical typewriter. Look, it has written a 1 on the tape….”

That could be gripping video, if the Australian actresses are pretty enough and scantily clad, and the background music is cool.

As to people that assume to be dumb saying something smart, and vice versa, here’s a snippet from an obituary today:

Former Green Bay receiver Max McGee dies in fall from roof

By STEVE KARNOWSKI,

Associated Press Writer

October 21, 2007

MINNEAPOLIS (AP) — Max McGee, the unexpected hero of the first Super Bowl and a long-time challenge for Hall of Fame coach Vince Lombardi, died Saturday after falling from the roof of his home, police confirmed. He was 75….

“He had a delightful sense of humor and had a knack for coming up with big plays when you least expected it to happen,” Packers historian Lee Remmel said. “He had a great sense of timing.”

Remmel said McGee once teased Lombardi when the coach showed the team a football on their first meeting and said, “Gentlemen, this is a football.”

“McGee said, ‘Not so fast, not so fast,”‘ Remmel said….

[Then he turned the football inside-out, while sexy Australian cheerleaders discussed the quantum computing implications of hot tub immersion]

Comment #34 October 22nd, 2007 at 7:43 am

Hehe. They show this every year at the Hampshire College Summer Studies in Mathematics (a high-school math program), which I attended. Twice. And yeah, it’s one of the coolest things we get to see all summer.

Comment #35 October 22nd, 2007 at 6:06 pm

Heh. And every CS talk should be like this.

Comment #36 October 23rd, 2007 at 8:07 pm

I am currently working on a series of illustrations (very old school) that improve upon Tony Phillips’s version and the version in my old book. Here we will have the projection, a movie of each projection, the “double decker set,” and the pre-image of the fold and cusp set of a generic perturbation of the Froissart-Morin eversion which was used in Banchoff’s movie of the Chicken wire models made by Charlie Pugh. Each movie will be easily obtained from the previous by means of the movie-moves.

From this series, we’ll be able to calculate explicitly all the multiple point set invariants, see that when it is capped off, it represents a generator of the third stable stem (zee mod 24) when considered upto cobordism, and look for other invariants of the fold set OF THE PROJECTION ONTO THE PAPER. It, of course, has no folds or creases in the same way that my trousers don’t have creases even though they were just ironed.

The apparent creases (in the trousers) as artifacts of the projection onto the ironing board.

I am pretty sure that the example I work with is very minimal, and it will contain a belt trick in it. But it does not contain the corregations that the ThTh eversion has.

If I got off the blogosphere, finished grading these tests, and finished a mathematica program to rotate a bunch of polyhedra in 4-space, I would be finished in a jiffy.

Comment #37 October 24th, 2007 at 3:02 pm

I remember I used to do/try to do this with wiffle balls when I was a boy.

Comment #38 October 25th, 2007 at 2:58 am

Um, so why is this post marked “nerd interest”? Shouldn’t all posts on this blogs be in that category? Just asking.

Comment #39 October 25th, 2007 at 4:28 am

Yeah, “Nerd Interest” is a pretty meaningless label on this blog; I should really get rid of it. (Right now it functions as my Miscellaneous/Other category.)

Comment #40 October 29th, 2007 at 4:39 pm

I love finding this blog

I think I’m the right audiance for the video. I’m pretty new in maths, but it fascinates me.