Lam's problem explained

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.^[1] 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.^[2]

Introduction

A finite projective plane of order

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 points on every line, and

• there are exactly

n +1 lines through every point.A consequence of this definition is that a projective plane of order n will contain n ^{2+n+1} points and 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 is equivalent to a (n ^{2+n+1) x (n} ^{2+n+1)} matrix with \{ 0 , 1 \} entries such that every row and column has n +1 onesand the inner product between any two rows or columns is exactly 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 x 111 matrix such that there are exactly eleven 1s in each row and column and any pair ofrows share a single 1 in the same column.^[3]

Clement W. H. 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.^[4] 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,^[5] 12,^[6] and 16^[7] —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.^[8] 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.^[9]

Notes and References

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