λ > 4       (Klarner's constant)

Polyominoes are edge-connected sets of cells on the planar square lattice. A(n) denotes the number of polyominoes of size n, where the size of a polyomino is simply the number of squares it contains. An important combinatorial problem is determining the asymptotic growth constant of polyominoes, that is, the limit of A(n+1)/A(n), when n tends to infinity. This limit is known as "Klarner's constant" (after the mathematician who coined this term) and is usually denoted by λ. In fact, the study of polyominoes originated in statistical physics (where they are called "lattice animals") in the contexts of percolation processes (Broadbent and Hammersley, 1957) and (later) the collapse of branched polymers (Peard and Gaunt, 1995). The relevant mathematical literature began by the pioneering book of Golomb (1965) and seminal papers by Klarner (1967) and others. So far, not even a single decimal digit of λ has been known. It was only known that 3.98 < λ < 4.65.

On Sunday, May 19, 2013, 18:25 GMT (21:25 Israel time), our program, which was run on the supercomputer DL980-1 of the "HPI (Hasso Plattner Institut) Future SOC Lab" in Potsdam, Germany, computed the new lower bound 4.00064... on λ. Specifically, the number we computed was a lower bound on λ₂₇, the growth constant of polyominoes on a twisted cylinder of width 27, which is by itself a lower bound on λ. Our program continued to run for a few more days, resulting in the final lower bound 4.002537727. The computation was peformed on 64 cores (128 virtual cores) with a total of 2 TB of main memory (RAM).

The fact that we performed the computations with 32-digit floating-point numbers does not imply that numerical errors can be too large so as to nullify our result. Our computed number is an eigenvalue of a huge integer matrix, for which we have a witness vector that is a good approximation of the eigenvector corresponding to λ₂₇. This vector proves rigorous bounds on the true eigenvalue with numerical errors whose magnitude is comparable with the accuracy of floating-point numbers, much smaller than the gap we opened above 4. (Specifically, the certified lower bound on λ is 4.00253176.) Thus, we now know the leading digit of λ: it is 4.

This project was awarded HPI Project of the Month of July 2013; see here.

Joint project with Günter Rote from Freie Universität Berlin and my M.Sc. student Mira Shalah.