Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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:

  1. 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....)

  2. Any partial information in this vein?

share|improve this question

2 Answers 2

up vote 41 down vote accepted

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.

share|improve this answer
2  
This answer is awesome! –  Aaron Sterling Sep 14 '10 at 17:42

This is (very!) partial information. These may be the special cases of nonexistence you mention:

  1. Chihiro Suetake, "The nonexistence of projective planes of order 12 with a collineation group of order 16" Journal of Combinatorial Theory, Series A, Volume 107, Issue 1, July 2004, Pages 21-48.
  2. Kenzi Akiyama1, Chihiro Suetake,"The nonexistence of projective planes of order 12 with a collineation group of order 8", Journal of Combinatorial Designs, Volume 16, Issue 5, pages 411–430, September 2008.

I do not know whether these results reduces the search space substantially.

share|improve this answer
8  
I can't imagine these reducing the search space at all, let alone substantially because they are not properties that can be identified from a partially completed fragment of the putative plane. Basically you'd have to already have completed the entire structure before you could determine whether or not it had these collineation groups. –  Gordon Royle Sep 14 '10 at 6:37
    
Thanks, both of you. That sounds like the answer I need. I'll wait another day or two, see if anyone else stops by. –  Aaron Sterling Sep 14 '10 at 11:53
1  
I am not sure if these papers (there are many more of this kind) will be able to settle the existence of a projective plane of order 2. It seems to me that at best, they could end up one day proving that such a plane would have a trivial automorphism group... –  Max Horn Sep 14 '10 at 16:14
3  
Well, I can settle the existence of a projective plane of order 2... :) –  Mariano Suárez-Alvarez Sep 14 '10 at 16:26
    
Oops, indeed! :) Of course I meant 12, not 2... :) thanks for pointing this out! –  Max Horn Sep 14 '10 at 23:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.