I asked this question on the new Theoretical Computer Science "overflow" site, and commenters suggested I ask it here. That question is here, and it contains additional links, which I doubt I can embed here because I don't have enough reputation. Anyway, here goes:
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. 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:
-
There have been special cases of nonexistence shown (again, by computer search). Does anyone know, if we remove those and exhaustively (cleverly?) search the rest, if the problem size is on the order of the Cube search? (Maybe too much to hope for that someone knows this….)
-
Any partial information in this vein?
Best Answer
I am actually not aware of many results on planes of order 12 in the vein of what Lam et. al. did (I list the few I know of below). There seems to be a plethora of papers proving restrictions on the collineation group of a hypothetical such plane, but I am not aware of how any of these could be used to settle the existence problem.
Moreover, I am quite skeptical that disproving the existence of planes of order 12 by a computer search would help for the general theory much. Though it certainly would be nice to know, and if one actually found a plane of order 12, that would be quite exciting; but it's hard to gain deep insights from these combinatorial brute force searches.
Extending the approach by Lam et. al. to planes of order 12 is in principle possible. But probably still not feasible with today's computers, as the search space is a lot bigger than for order 10. Anyway, here are some reasons why I think that, and at the same time a sketch of things that would have to be done. But my personal belief is that one will need some substantially new ideas to make progress on this. Then again, only by actually trying to do it can one be sure... :)
From here on, I'll assume you are familiar with Lam's "The Search for a Finite Projective Plane of Order 10" and the notation used within.
A crucial point was the reduction of the (non-)existence to the value of certain weight enumerator coefficients $w_0$ to $w_{n^2+n+1}$ (a good exposition can be found in "On the existence of a projective plane of order 10" by MacWilliams, Sloane and Thompson). But the real breakthrough was when Assmus and Mattson proved that one only needs to know $w_{12},w_{15},w_{16}$ to determine all others. I'll refer to these as essential weight enumerator coefficients.
Some steps towards this for order 12 have been executed in "Ternary and binary codes for a plane of order $12$" by Hall and Wilkinson. Yet many nice properties and theorems will be hard to recover for order 12. E.g. for orders of the form $8m+2$, one knows the $\mathbb{F}_2$-rank of the incidence matrix. Not so for order 12, where working with a ternary code is in some ways more "natural." In particular, the $\mathbb{F}_3$-rank of the incidence matrix is known, but, alas, working with a ternary code means losing the natural identification of codewords with point sets, so tons of new machinery would be needed to exploit the ternary code. Thus I'll focus on the binary code case here.
Anyway, let's assume we reduced the number of essential weight enumerator coefficients as much as we can (Hall and Wilkinson pushed it down to 16; remember, for $n=10$ we had only 3). We must compute the essential coefficients.
According to Lam, for $n=10$ and the case $w_{12}$, they estimated, using a Monte-Carlo method (before doing it) that $4\times 10^{11}$ configuration had to be checked. I don't have a good means to compute a good estimate for $n=12$, but for that there are 16 coefficients to determine, and I'd hazard to guess that some of them are much, much harder than the three cases for $n=10$ put together. Several orders of magnitude. However, this is just gut feeling.
So let's assume we had somehow managed to overcome this and had computed all essential weight enumerator coefficients. We then would have the full weight enumerator at hand (and no projective plane arose as a byproduct of our search). Now, the hard part starts (corresponding roughly to the second half of Lam's paper), the one that took them 2 years for $n=10$: We have to somehow derive a contradiction (or construct a plane). A lot of ground work needs to be done (extending stuff from $n=10$), before one can even start writing code...
Ah well. To anybody who wants to try out this strategy on $n=12$, I would recommend to first try reproducing the $n=10$ result -- with modern computers it should be possible to do this much, much quicker than it took Lam et. al. originally (this verification might already interest some people on its own). Actually, at the very start, try it with even smaller examples ($n=6,8$), then go up.