# Projective Plane of Order 12

Objective: Settle the conjecture that there is no projective plane of order 12.

In 1989, using computer search on a Cray, Lam proved that no projective plane of order 10 exists. Now that God's Number for Rubik's Cube has been determined after just a few weeks of massive brute force search (plus clever math of symmetry), it seems to me that this longstanding open problem might be within reach. (Plus maybe we could use such techniques to solve something mathematically fundamental.) I'm hoping this question can serve as a sanity check.

The Cube was solved by reducing the total problem size to "only" 2,217,093,120 distinct tests, which could be run in parallel.

Questions:

1. There have been several special cases of nonexistence shown. Does anyone know, if we remove those and exhaustively search the rest, if the problem size is on the order of the Cube search? (Maybe to much to hope for that someone knows this....)

2. Any partial information in this vein?

Edited to add: I asked this question on MathOverflow here. So far it seems as though no search space reduction is achieved from the known partial results. I still don't know the size of the total search space.

• do you know any good references for the special cases of nonexistence that you mentioned? Or perhaps, just a general reference/set of references for the order 12 case? Sep 11, 2010 at 15:43
• This looks better suited for MathOverflow. Is there a strong connection to theoretical computer science? (On the other hand: How hard is it to decide, given an integer n, whether a projective plane of order n exists? Polynomial time? NP-hard? Worse?) Sep 11, 2010 at 16:04
• @JeffE, thanks, I was wondering if I should ask it there instead. I think it could be an application of TCS to combinatorics, but I'm not seeing it as an "important" result, just a high-hanging fruit that may now be low-hanging due to processor speeds and the cloud. I don't know the answer to your decision problem. So... I'll wait a few days, then post to MO, linking here. Sep 11, 2010 at 17:53
• I like Jeff's reformulation. Maybe that's worth posting as another question :) Sep 11, 2010 at 19:21
• I see the potential application of computer science to combinatorics, just not theoretical computer science, which is (according to my own biases) about the limiting behavior of computation as the input size grows to infinity. Finding God's number was an impressive technical achievement, but it's not clear that it required any algorithmic insight, or that it will have any algorithmic impact. (I'd love to be corrected on this point.) Sep 11, 2010 at 20:27