The universal constant λ, the growth constant
of polyominoes (think Tetris pieces), is
rigorously proved to be greater than 4.
BY GILL BAREQUET, GÜNTER ROTE, AND MIRA SHALAH
What is λ The universal constant λ arises in the study
of three completely unrelated fields: combinatorics,
percolation, and branched polymers. In combinatorics,
analysis of self-avoiding walks (SAWs, or non-self-
intersecting lattice paths starting at the origin, counted
by lattice units), simple polygons or self-avoiding
polygons (SAPs, or closed SAWs, counted by either
perimeter or area), and “polyominoes” (SAPs possibly
with holes, or edge-connected sets of lattice squares,
counted by area) are all related. In statistical physics,
SAWs and SAPs play a significant role in percolation
processes and in the collapse transition that branched
polymers undergo when being heated. A collection
edited by Guttmann15 gives an excellent review of all
these topics and the connections be-
tween them. In this article, we describe
our effort to prove that the growth con-
stant (or asymptotic growth rate, also
called the “connective constant”) of
polyominoes is strictly greater than 4.
To this aim, we exploited to the maxi-
mum possible computer resources
λ > 4
on the Growth
˽ Direct access to large shared RAM is
useful for scientific computations, as well
as for big-data applications.
˽ The growth constant of polyominoes is
provably strictly greater than 4.
˽ The “proof” of this bound is an
eigenvector of a giant matrix Q that
can be verified as corresponding to the
claimed bound—an eigenvalue of Q.