**
λ > 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
λ_{27}, 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 λ_{27}.
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**.