Integrals, partitions, and cellular automata
Authors:
Alexander E. Holroyd, Thomas M. Liggett and Dan Romik
Translated by:
Journal:
Trans. Amer. Math. Soc. 356 (2004), 33493368
MSC (2000):
Primary 26A06; Secondary 05A17, 60C05, 60K35
Published electronically:
December 15, 2003
MathSciNet review:
2052953
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We prove that
where is the decreasing function that satisfies , for . When is an integer and we deduce several combinatorial results. These include an asymptotic formula for the number of integer partitions not having consecutive parts, and a formula for the metastability thresholds of a class of threshold growth cellular automaton models related to bootstrap percolation.
 1.
Michael
Aizenman and Geoffrey
Grimmett, Strict monotonicity for critical points in percolation
and ferromagnetic models, J. Statist. Phys. 63
(1991), no. 56, 817–835. MR 1116036
(92i:82060), http://dx.doi.org/10.1007/BF01029985
 2.
M.
Aizenman and J.
L. Lebowitz, Metastability effects in bootstrap percolation,
J. Phys. A 21 (1988), no. 19, 3801–3813. MR 968311
(90e:82047)
 3.
George
E. Andrews, The theory of partitions, AddisonWesley
Publishing Co., Reading, Mass.LondonAmsterdam, 1976. Encyclopedia of
Mathematics and its Applications, Vol. 2. MR 0557013
(58 #27738)
 4.
George
E. Andrews, The reasonable and unreasonable effectiveness of number
theory in statistical mechanics, The unreasonable effectiveness of
number theory (Orono, ME, 1991) Proc. Sympos. Appl. Math., vol. 46,
Amer. Math. Soc., Providence, RI, 1992, pp. 21–34. MR 1195840
(94c:82021), http://dx.doi.org/10.1090/psapm/046/1195840
 5.
J.
Baik, P.
Deift, and K.
Johansson, On the distribution of the length of the second row of a
Young diagram under Plancherel measure, Geom. Funct. Anal.
10 (2000), no. 4, 702–731. MR 1791137
(2001m:05258a), http://dx.doi.org/10.1007/PL00001635
 6.
Charles
H. Brenner, Asymptotic analogs of the RogersRamanujan
identities, J. Combin. Theory Ser. A 43 (1986),
no. 2, 303–319. MR 867654
(88e:05008), http://dx.doi.org/10.1016/00973165(86)900695
 7.
I.
S. Gradshteyn and I.
M. Ryzhik, Table of integrals, series, and products, Academic
Press [Harcourt Brace Jovanovich, Publishers], New YorkLondonToronto,
Ont., 1980. Corrected and enlarged edition edited by Alan Jeffrey;
Incorporating the fourth edition edited by Yu. V. Geronimus [Yu. V.
Geronimus]\ and M. Yu. Tseytlin [M. Yu. Tseĭtlin]; Translated from
the Russian. MR
582453 (81g:33001)
 8.
Janko
Gravner and David
Griffeath, First passage times for threshold growth dynamics on
𝑍², Ann. Probab. 24 (1996), no. 4,
1752–1778. MR 1415228
(98c:60140), http://dx.doi.org/10.1214/aop/1041903205
 9.
Janko
Gravner and David
Griffeath, Scaling laws for a class of critical cellular automaton
growth rules, Random walks (Budapest, 1998) Bolyai Soc. Math. Stud.,
vol. 9, János Bolyai Math. Soc., Budapest, 1999,
pp. 167–186. MR 1752894
(2001a:60113)
 10.
G. H. Hardy and S. Ramanujan.
Asymptotic formulae for the distribution of integers of various types. Proc. London Math. Soc., Ser. 2, 16:112132, 1918. Reprinted in The Collected Papers of G. H. Hardy, vol. 1, 277293.
 11.
Paul
G. Hoel, Sidney
C. Port, and Charles
J. Stone, Introduction to probability theory, Houghton Mifflin
Co., Boston, Mass., 1971. The Houghton Mifflin Series in Statistics. MR 0358880
(50 #11337c)
 12.
A. E. Holroyd.
Sharp metastability threshold for twodimensional bootstrap percolation. Probability and Related Fields, 125:195224, 2003.
 13.
Kurt
Johansson, Shape fluctuations and random matrices, Comm. Math.
Phys. 209 (2000), no. 2, 437–476. MR 1737991
(2001h:60177), http://dx.doi.org/10.1007/s002200050027
 14.
Donald
J. Newman, Analytic number theory, Graduate Texts in
Mathematics, vol. 177, SpringerVerlag, New York, 1998. MR 1488421
(98m:11001)
 1.
 M. Aizenman and G. Grimmett.
Strict monotonicity for critical points in percolation and ferromagnetic models. Journal of Statistical Physics, 63:817835, 1991. MR 92i:82060
 2.
 M. Aizenman and J. L. Lebowitz.
Metastability effects in bootstrap percolation. J. Phys. A, 21(19):38013813, 1988. MR 90e:82047
 3.
 G. E. Andrews.
The Theory of Partitions, volume 2 of Encyclopedia of Mathematics and its Applications. AddisonWesley, 1976. MR 58:27738
 4.
 G. E. Andrews.
The reasonable and unreasonable effectiveness of number theory in statistical mechanics. Proceedings of Symposia in Applied Mathematics, 46:2134, 1992. MR 94c:82021
 5.
 J. Baik, P. Deift, and K. Johansson.
On the distribution of the length of the second row of a Young diagram under Plancherel measure. Geom. Funct. Anal., 10(4):702731, 2000. MR 2001m:05258a
 6.
 C. H. Brenner.
Asymptotic analogs of the RogersRamanujan identities. J. Comb. Theory Ser. A, 43:303319, 1986. MR 88e:05008
 7.
 I. S. Gradshteyn and I. M. Ryzhik.
Table of integrals, series, and products. Academic Press, New York, 1965. MR 81g:33001
 8.
 J. Gravner and D. Griffeath.
First passage times for threshold growth dynamics on . Ann. Probab., 24(4):17521778, 1996. MR 98c:60140
 9.
 J. Gravner and D. Griffeath.
Scaling laws for a class of critical cellular automaton growth rules. In Random walks (Budapest, 1998), pages 167186. János Bolyai Math. Soc., Budapest, 1999. MR 2001a:60113
 10.
 G. H. Hardy and S. Ramanujan.
Asymptotic formulae for the distribution of integers of various types. Proc. London Math. Soc., Ser. 2, 16:112132, 1918. Reprinted in The Collected Papers of G. H. Hardy, vol. 1, 277293.
 11.
 P. G. Hoel, S. C. Port, and C. J. Stone.
Introduction to probability theory. Houghton Mifflin Co., Boston, Mass., 1971. The Houghton Mifflin Series in Statistics. MR 50:11337c
 12.
 A. E. Holroyd.
Sharp metastability threshold for twodimensional bootstrap percolation. Probability and Related Fields, 125:195224, 2003.
 13.
 K. Johansson.
Shape fluctuations and random matrices. Comm. Math. Phys., 209(2):437476, 2000. MR 2001h:60177
 14.
 D. J. Newman.
Analytic Number Theory. Number 177 in Graduate Texts in Mathematics. SpringerVerlag, 1998. MR 98m:11001
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (2000):
26A06,
05A17,
60C05,
60K35
Retrieve articles in all journals
with MSC (2000):
26A06,
05A17,
60C05,
60K35
Additional Information
Alexander E. Holroyd
Affiliation:
Department of Mathematics, University of British Columbia, Vancouver, British Columbia, Canada V6T 1Z2
Email:
holroyd@math.ubc.ca
Thomas M. Liggett
Affiliation:
Department of Mathematics, University of California Los Angeles, Los Angeles, Califonia 900951555
Email:
tml@math.ucla.edu
Dan Romik
Affiliation:
Department of Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel
Email:
romik@wisdom.weizmann.ac.il
DOI:
http://dx.doi.org/10.1090/S0002994703034172
PII:
S 00029947(03)034172
Keywords:
Definite integral,
partition asymptotics,
partition identity,
combinatorial probability,
threshold growth model,
bootstrap percolation,
cellular automaton
Received by editor(s):
February 17, 2003
Received by editor(s) in revised form:
May 6, 2003
Published electronically:
December 15, 2003
Additional Notes:
The first author’s research was funded in part by NSF Grant DMS–0072398.
The second author’s research was funded in part by NSF Grant DMS0070465.
Article copyright:
© Copyright 2003
American Mathematical Society
