Misplaced Pages

Lam's problem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

In finite geometry, Lam's problem is the problem of determining if a finite projective plane of order ten exists. The order ten case is the first theoretically uncertain case, as all smaller orders can be resolved by purely theoretical means. Lam's problem is named after Clement W. H. Lam who experimentally determined that projective planes of order ten do not exist via exhaustive computational searches.

Introduction

A finite projective plane of order n {\displaystyle n} is a collection of points and lines such that

  • any two points define a unique line,
  • any two lines meet at a unique point,
  • there are exactly n + 1 {\displaystyle n+1} points on every line, and
  • there are exactly n + 1 {\displaystyle n+1} lines through every point.

A consequence of this definition is that a projective plane of order n {\displaystyle n} will contain n 2 + n + 1 {\displaystyle n^{2}+n+1} points and n 2 + n + 1 {\displaystyle n^{2}+n+1} lines. The incidence relation between points and lines may equivalently be described using an incidence matrix. In this context a projective plane of order n {\displaystyle n} is equivalent to a ( n 2 + n + 1 ) × ( n 2 + n + 1 ) {\displaystyle (n^{2}+n+1)\times (n^{2}+n+1)} matrix with { 0 , 1 } {\displaystyle \{0,1\}} entries such that every row and column has n + 1 {\displaystyle n+1} ones and the inner product between any two rows or columns is exactly 1 {\displaystyle 1} .

Using the incidence matrix representation, Lam's problem is equivalent to determining if there is a way of placing 0s and 1s in a 111 × 111 {\displaystyle 111\times 111} matrix such that there are exactly eleven 1s in each row and column and any pair of rows share a single 1 in the same column.

Lam considered studying the existence of a projective plane of order ten in his PhD thesis but was dissuaded by his thesis advisor H. J. Ryser who believed the problem was too difficult.

Resolution

Edward Assmus presented a connection between projective planes and coding theory at the conference Combinatorial Aspects of Finite Geometries in 1970. He studied the code generated by the rows of the incidence matrix of a hypothetical projective plane of order ten and derived a number of restrictive properties that such a code must satisfy. In particular, the enumerator polynomial of the code is completely determined by the number of words of weights 12, 15, and 16 in the code.

Over the next two decades a number of computer searches showed that the hypothetical code associated with the projective plane of order ten does not contain words of weights 15, 12, and 16—which implied that it must contain words of weight 19. Finally, Clement Lam, Larry Thiel and Stanley Swiercz used about three months of time on a Cray-1A supercomputer to show that words of weight 19 are also not present in the code. This resolved Lam's problem in the negative. Their result was independently verified in 2021 by using a SAT solver to generate computer-verifiable certificates for the correctness of the exhaustive searches.

References

  1. Hall, Marshall Jr. (1955). "Finite Projective Planes". American Mathematical Monthly. 62 (7P2): 18–24. doi:10.2307/2308176. JSTOR 2308176. MR 0073214. The first critical value of n {\displaystyle n} is n = 10 {\displaystyle n=10} . A thorough investigation of this case is currently beyond the facilities of computing machines.
  2. ^ Lam, Clement W. H. (1991). "The Search for a Finite Projective Plane of Order 10". American Mathematical Monthly. 98 (4): 305–318. doi:10.1080/00029890.1991.12000759. MR 1103185.
  3. Weisstein, Eric W. (2005). "Lam's Problem". CRC Concise Encyclopedia of Mathematics (3rd ed.). CRC Press. ISBN 9780849319464.
  4. Assmus, Edward F. Jr.; Mattson, Harold F. Jr. (15 October 1970). "On the Possibility of a Projective Plane of Order Ten". Algebraic Theory of Codes II (Report). Air Force Cambridge Research Laboratories.
  5. MacWilliams, F. J.; Sloane, N. J. A.; Thompson, J. G. (1973). "On the Existence of a Projective Plane of Order 10". Journal of Combinatorial Theory, Series A. 14: 66–78. doi:10.1016/0097-3165(73)90064-2. MR 0313089.
  6. Lam, C. W. H.; Thiel, L.; Swiercz, S.; McKay, J. (1983). "The Nonexistence of Ovals in a Projective Plane of Order 10". Discrete Mathematics. 45: 319–321. doi:10.1016/0012-365X(83)90049-3. MR 0704249.
  7. Lam, C. W. H.; Thiel, L.; Swiercz, S. (1986). "The Nonexistence of Code Words of Weight 16 in a Projective Plane of Order 10". Journal of Combinatorial Theory, Series A. 42: 207–214. doi:10.1016/0097-3165(86)90091-9. MR 0847551.
  8. Lam, C. W. H.; Thiel, L.; Swiercz, S. (1989). "The Non-existence of Finite Projective Planes of Order 10". Canadian Journal of Mathematics. 41 (6): 1117–1123. doi:10.4153/CJM-1989-049-4. MR 1018454.
  9. Bright, C.; Cheung, K. K. H.; Stevens, B.; Kotsireas, I.; Ganesh, V. (2021). A SAT-based Resolution of Lam's Problem. AAAI Conference on Artificial Intelligence. pp. 3669–3676.
Categories: