Wednesday, September 08, 2010

The Rubik's Cube Conjecture PROVEN! (Do we care?)

In 1994 Fermat's last theorem was proven! In 2003 Poincare's conjecture was proven! In 2010 the Rubik Cube Conjecture was proven! That is, it was shown that the minimum number of moves needed to solve Rubik's Cube is 20 (it was known that there are starting configurations that require 20). Here is the pointer: Rubiks Cube has been solved. (Jeff Erickson also had a blog entry on Rubik's cube lately: here.)

(ADDED LATER. Clarification: From any starting position one can get to the solution in \le 20 moves. There exists a starting position where every solution takes \ge 20 moves. )

We all have a sense that the Rubik Cube result is not as important as the other two. What makes a math problem important?
  1. Would Martians work on it? I suspect Martians would work on FLT and Poincare but not Rubik's cube. One of the first things I would ask Space Aliens is what Math they have done.
  2. Does it connect to other parts of mathematics? This leads to a seemingly circular definition of importance: A topic in math is important if it connects to other topics that are interesting. FLT and Poincare's conjecture are connected to other parts of mathematics. One way to understand Rubik's cube is through group theory; however, this is not so much a connection as an application. Rubik's cube studies have not lead to advances in group theory.
  3. Does the problem have its origins in some real world phenomena? (This is not necessary but helps.)
  4. The problem should be hard but not so hard that you cannot make any progress on it.
  5. The proof must be interesting (hmmm- then we need to define interesting).
These criteria may be too strict. It would be interesting to discuss other branches of math that are considered important that do not quite fit these criteria and see what else makes them important. Or branches that do fit these criteria but are not considered important.

18 comments:

  1. minimum -> maximum?

    ReplyDelete
  2. That is, it was shown that the minimum number of moves needed to solve Rubik's Cube is 20 (it was known that there are starting configurations that require 20).

    You probably mean "maximum number of moves".

    ReplyDelete
  3. Objectively, FLT isn't that much more natural than Rubik's Cube. It's got the fact that it's a generalization of Pythagorean triples, but that's about it. That it's received so much attention seems like a sort of fluke of math history. It's created interesting math and even provided some applications, but only through a kind of sheer force-of-will. It wouldn't be that surprising if the Martians HADN'T studied it.

    ReplyDelete
  4. "Why are numbers beautiful? It's like asking why is Beethoven's Ninth Symphony beautiful. If you don't see why, someone can't tell you. I know numbers are beautiful. If they aren't beautiful, nothing is."
    - Paul Erdős

    ReplyDelete
  5. @1 and @2

    Minimum is correct.

    For example, if I gave you 21 moves, you could still always solve the cube. However, if I only gave you 19 moves, you could not always solve the cube. Thus, "the minimum number of moves needed to solve Rubik's Cube is 20".

    ReplyDelete
  6. This result can really show the power of math to a foreign world. Not many people know of the theoretical side of math, but lots know how much of a headache solving a Rubik's cube can be. Even if the proof is hard for a novice to understand, such a result can inspire conversation about how to prove similar things for simpler puzzles. And if this conversation helps more people to see the beauty of mathematics, then this is indeed an important result.

    ReplyDelete
  7. I think there's also a certain finiteness principle here: if a question can in principle be reduced to a finite calculation (even though in practice we can't do that calculation) then it's less likely to be interesting than a problem where any solution would have to be more conceptual.

    ReplyDelete
  8. I agree with David. In this case the "proof" is some sort of (clever, but still quite-brute-force) calculation.

    We can admire the nice exploitation of symmetries and the expertise in coding a lot of programming tricks in order to speed up the computation, but if the proof had been "on paper" probably it would have been more interesting.

    ReplyDelete
  9. As an utter layman, I'd suggest that "interesting" be defined as "holding the attention of provers long enough to prove it" when the amount of time it takes to prove something is not trivial. Rubik's cube is therefore surprisingly interesting, as this proof about essentially a toy took many person-years of effort to emerge, and yet the effort was made.

    At least, that's why it interests me!

    ReplyDelete
  10. As a counterpoint to David: 4 color theorem by a finite calculation.

    I suppose there is a question of how "obvious" it is that a finite calculation can solve the problem.

    ReplyDelete
  11. Carroll's Riddle:
    Why is God's Chess Number like a writing desk?

    Answer:
    Because both Turing and Shannon wrote upon it.

    ------------
    Note: white has 61 "only" moves.

    ReplyDelete
  12. In a sense not even Wiles believed FLT to be a problem important on its own. Only when a way to prove FLT that had connections to deep maths became apparent did he devote his complete attention to it.

    Many other mathematicians have commented on the utter irrelevance of the FLT question.

    The Rubik cube has connections to some really deep group theory, and when this is eventually re-proven for the n-sided cube it will likely be as relevant as FLT was.

    ReplyDelete
  13. Here's a question: does the Rubik's Cube count as "real world phenomena"? Somehow because it's a toy it seems the answer should be no, or at least this justification is much less strong than if, for instance, the conjecture was related to curing cancer.

    On the other hand, I think popular interest in this problem is actually more than for say the Poincare Conjecture.

    ReplyDelete
  14. This is epic result, much more important than 99.9% of the trash published in the so called TCS. That you are unable to understand that only highlights how overrated TCS people are.

    ReplyDelete
  15. @5

    "needed" means "required", so the "minimum needed" is 0, not 20.

    ReplyDelete
  16. The proof must be interesting (hmmm- then we need to define interesting).

    Yes, yes, please, please define "interesting" (or beautiful) in maths.
    You probably cannot do that using only mathematical statements, then what?

    ReplyDelete
  17. Yaaaay......

    Could someone please tell me what the 20 moves are so I can solve mine?

    ReplyDelete
  18. Could someone please tell me what the 20 moves are so I can solve mine?

    You can find these yourself. Feed them into the incredible Cube Explorer program (http://kociemba.org/cube.htm) and you get the solution in 20 moves.

    ReplyDelete