14
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Daniel Apon
    Sep 11, 2010 at 15:43
  • 2
    $\begingroup$ 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?) $\endgroup$
    – Jeffε
    Sep 11, 2010 at 16:04
  • $\begingroup$ @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. $\endgroup$
    – Aaron Sterling
    Sep 11, 2010 at 17:53
  • $\begingroup$ I like Jeff's reformulation. Maybe that's worth posting as another question :) $\endgroup$
    – Suresh Venkat
    Sep 11, 2010 at 19:21
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Jeffε
    Sep 11, 2010 at 20:27

2 Answers 2

Reset to default
9
$\begingroup$

(More a comment than answer:)

Finite projective planes exist for values of n which are powers of a prime, and there are infinitely many values of n which are ruled out by a theorem of R.H. Bruck and H. Ryser, which was generalized to block designs by Chowla:

http://en.wikipedia.org/wiki/Bruck%E2%80%93Chowla%E2%80%93Ryser_theorem

n = 10, as was stated, was solved (no plane exists) by a computer search so the first value of n not ruled out by Bruck-Ryser is n = 12. However, the computer work did not seem to give new insights as to whether or not there are only the prime power planes. What seems to be needed are new mathematical methods for insight into the commonly made conjecture that only the prime power planes exist.

Improve this answer
$\endgroup$
3
$\begingroup$

There is a conjecture saying that, if sigma(n)>2n, then there is neiether a finite projective plane (FPP) of order n, nor a complete set of mutually orthogonal Latin square (CMOLS) that corresponds to it. Where sigma(n) denotes the sum of positive divisors of n including n itself. In fact, when sigma(n)>2n means that n is an abundant number. and 12 is the smallest abundant number exist. The following is all the abundant numbers for 1 > n > 500: 12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 100, 102, 104, 108, 112, 114, 120, 126, 132, 138, 140, 144, 150, 156, 160, 162, 168, 174, 176, 180, 186, 190, 196, 198, 200, 204, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264, 270, 272, 276, 280, 282, 294, 300, 304, 306, 308, 312, 318, 320, 324, 330, 336, 340, 342, 348, 350, 352, 354, 360, 364, 366, 368, 372, 378, 380, 384, 390, 392, 396, 400, 402, 408, 414, 416, 420, 426, 432, 438, 440, 444, 448, 450, 456, 460, 462, 464, 468, 474, 476, 480, 486, 490, 492, 498, 500.

from On Projective Planes of Order 12 by Muatazz Abdolhadi Bashir and Andrew Rajah

Improve this answer
$\endgroup$
0

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.