41
$\begingroup$

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?

$\endgroup$
1

2 Answers 2

70
$\begingroup$

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.

UPDATE 2023-08-10: I just learned that the $n=10$ result has been reproduced not once but twice in the meantime:

  1. in 2010/2011 by Dominique J. Roy in their master thesis "Confirmation of the non-existence of a projective plane of order 10" at Carleton University, using special purpose code. They also give a more detailed overview of what is involved in the whole endeavour.
  2. And then again more recently with help of a standard SAT solver (!), in an effort culminating in: Bright, C., Cheung, K. K. H., Stevens, B., Kotsireas, I., & Ganesh, V. (2021). A SAT-based Resolution of Lam’s Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 3669-3676. DOI.
$\endgroup$
7
  • 3
    $\begingroup$ This answer is awesome! $\endgroup$ Sep 14, 2010 at 17:42
  • $\begingroup$ The link to www.dtic.mil is broken. I'm also unable to find any snapshot saved on the Wayback Machine. $\endgroup$ May 12, 2023 at 6:04
  • 1
    $\begingroup$ Hmm, that's bad. The text in question is the one describe here: apps.dtic.mil/sti/citations/AD0698813 but the full text link given there (apps.dtic.mil/sti/pdfs/AD0698813.pdf) is also broken (it links to a page saying "This document is not available in digital form"). They give a US phone number to contact if there are still issues. I am not in the US, but if someone from there would like to call... $\endgroup$
    – Max Horn
    May 12, 2023 at 15:50
  • 3
    $\begingroup$ BTW I do have that PDF archived on my computer, email me if you would like a copy. Also if someone phones them and they say they don't have a digital version, well, I'll send 'em a copy, too, if they want one ;-) $\endgroup$
    – Max Horn
    May 12, 2023 at 15:50
  • 2
    $\begingroup$ Not a lot for $n=12$ at this point because they still crucially rely on all the purely theoretical reductions that are available for $n=10$ but missing (and way out of reach) for $n=12$, as I explain with some more detail above. $\endgroup$
    – Max Horn
    Aug 10, 2023 at 9:25
11
$\begingroup$

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.

$\endgroup$
5
  • 14
    $\begingroup$ 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. $\endgroup$ Sep 14, 2010 at 6:37
  • $\begingroup$ Thanks, both of you. That sounds like the answer I need. I'll wait another day or two, see if anyone else stops by. $\endgroup$ Sep 14, 2010 at 11:53
  • 2
    $\begingroup$ 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... $\endgroup$
    – Max Horn
    Sep 14, 2010 at 16:14
  • 5
    $\begingroup$ Well, I can settle the existence of a projective plane of order 2... :) $\endgroup$ Sep 14, 2010 at 16:26
  • 2
    $\begingroup$ Oops, indeed! :) Of course I meant 12, not 2... :) thanks for pointing this out! $\endgroup$
    – Max Horn
    Sep 14, 2010 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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