## Laplacian growth, sandpiles, and scaling limits

HTML articles powered by AMS MathViewer

- by Lionel Levine and Yuval Peres PDF
- Bull. Amer. Math. Soc.
**54**(2017), 355-382

## Abstract:

Laplacian growth is the study of interfaces that move in proportion to harmonic measure. Physically, it arises in fluid flow and electrical problems involving a moving boundary. We survey progress over the last decade on discrete models of (internal) Laplacian growth, including the abelian sandpile, internal DLA, rotor aggregation, and the scaling limits of these models on the lattice $\epsilon {\mathbb {Z}}^d$ as the mesh size $\epsilon$ goes to zero. These models provide a window into the tools of discrete potential theory, including harmonic functions, martingales, obstacle problems, quadrature domains, Green functions, smoothing. We also present one new result: rotor aggregation in ${\mathbb {Z}}^d$ has $O(\log r)$ fluctuations around a Euclidean ball, improving a previous power-law bound. We highlight several open questions, including whether these fluctuations are $O(1)$.## References

- Dov Aharonov and Harold S. Shapiro,
*Domains on which analytic functions satisfy quadrature identities*, J. Analyse Math.**30**(1976), 39–73. MR**447589**, DOI 10.1007/BF02786704 - Amine Asselah and Alexandre Gaudillière,
*From logarithmic to subdiffusive polynomial fluctuations for internal DLA and related growth models*, Ann. Probab.**41**(2013), no. 3A, 1115–1159. MR**3098673**, DOI 10.1214/12-AOP762 - Amine Asselah and Alexandre Gaudillière,
*Sublogarithmic fluctuations for internal DLA*, Ann. Probab.**41**(2013), no. 3A, 1160–1179. MR**3098674**, DOI 10.1214/11-AOP735 - Amine Asselah and Alexandre Gaudillière,
*Lower bounds on fluctuations for internal DLA*, Probab. Theory Related Fields**158**(2014), no. 1-2, 39–53. MR**3152779**, DOI 10.1007/s00440-012-0476-6 - Siva R. Athreya and Antal A. Járai,
*Infinite volume limit for the stationary distribution of abelian sandpile models*, Comm. Math. Phys.**249**(2004), no. 1, 197–213. MR**2077255**, DOI 10.1007/s00220-004-1080-0 - László Babai,
*Lecture notes on the sandpile model*. http://people.cs.uchicago.edu/~laci/REU05/#problem - Per Bak, Chao Tang, and Kurt Wiesenfeld,
*Self-organized criticality*, Phys. Rev. A (3)**38**(1988), no. 1, 364–374. MR**949160**, DOI 10.1103/PhysRevA.38.364 - Matthew Baker and Serguei Norine,
*Riemann-Roch and Abel-Jacobi theory on a finite graph*, Adv. Math.**215**(2007), no. 2, 766–788. MR**2355607**, DOI 10.1016/j.aim.2007.04.012 - Itai Benjamini, Russell Lyons, Yuval Peres, and Oded Schramm,
*Uniform spanning forests*, Ann. Probab.**29**(2001), no. 1, 1–65. MR**1825141**, DOI 10.1214/aop/1008956321 - Anders Björner, László Lovász, and Peter W. Shor,
*Chip-firing games on graphs*, European J. Combin.**12**(1991), no. 4, 283–291. MR**1120415**, DOI 10.1016/S0195-6698(13)80111-4 - L. A. Caffarelli,
*The obstacle problem revisited*, J. Fourier Anal. Appl.**4**(1998), no. 4-5, 383–402. MR**1658612**, DOI 10.1007/BF02498216 - Hannah Cairns,
*Some halting problems for abelian sandpiles are undecidable in dimension three*. arXiv:1508.00161 - Sergio Caracciolo, Guglielmo Paoletti, and Andrea Sportiello,
*Explicit characterization of the identity configuration in an abelian sandpile model*, J. Phys. A**41**(2008), no. 49, 495003, 17. MR**2515893**, DOI 10.1088/1751-8113/41/49/495003 - Sergio Caracciolo and Andrea Sportiello,
*Exact integration of height probabilities in the Abelian Sandpile model*, J. Stat. Mech. Theory Exp.**9**(2012), P09013, 14. MR**2994907**, DOI 10.1088/1742-5468/2012/09/p09013 - Joshua N. Cooper and Joel Spencer,
*Simulating a random walk with constant error*, Combin. Probab. Comput.**15**(2006), no. 6, 815–822. MR**2271828**, DOI 10.1017/S0963548306007565 - Deepak Dhar,
*Self-organized critical state of sandpile automaton models*, Phys. Rev. Lett.**64**(1990), no. 14, 1613–1616. MR**1044086**, DOI 10.1103/PhysRevLett.64.1613 - Deepak Dhar,
*Theoretical studies of self-organized criticality*, Phys. A**369**(2006), no. 1, 29–70. MR**2246566**, DOI 10.1016/j.physa.2006.04.004 - Deepak Dhar, Tridib Sadhu and Samarth Chandra,
*Pattern formation in growing sandpiles*, Europhys. Lett.**85**(2009), 48002. arXiv:0808.1732 - Persi Diaconis and William Fulton,
*A growth model, a game, an algebra, Lagrange inversion, and characteristic classes*, Rend. Sem. Mat. Univ. Pol. Torino**49**(1991), no. 1, 95–119. - Anne Fey, Ronald Meester, and Frank Redig,
*Stabilizability and percolation in the infinite volume sandpile model*, Ann. Probab.**37**(2009), no. 2, 654–675. MR**2510019**, DOI 10.1214/08-AOP415 - Laura Florescu, Lionel Levine and Yuval Peres,
*The range of a rotor walk*, 2014. arXiv:1408.5533 - Yasunari Fukai and Kôhei Uchiyama,
*Potential kernel for two-dimensional random walk*, Ann. Probab.**24**(1996), no. 4, 1979–1992. MR**1415236**, DOI 10.1214/aop/1041903213 - Geoffrey Grimmett,
*The random-cluster model*, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 333, Springer-Verlag, Berlin, 2006. MR**2243761**, DOI 10.1007/978-3-540-32891-9 - Björn Gustafsson,
*Quadrature identities and the Schottky double*, Acta Appl. Math.**1**(1983), no. 3, 209–240. MR**726725**, DOI 10.1007/BF00046600 - Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp and David B. Wilson,
*Chip-firing and rotor-routing on directed graphs*,*In and out of equilibrium $2$*, 331–364, Progr. Probab.**60**, Birkhäuser, 2008. arXiv:0801.3306 - Alexander E. Holroyd and James Propp,
*Rotor walks and Markov chains*, Algorithmic probability and combinatorics, Contemp. Math., vol. 520, Amer. Math. Soc., Providence, RI, 2010, pp. 105–126. MR**2681857**, DOI 10.1090/conm/520/10256 - Antal A. Járai, Sandpile models,
*Cornell probability summer school lecture notes*, 2014. arXiv:1401.0354 - Monwhea Jeng, Geoqffroy Piroux and Philippe Ruelle,
*Height variables in the Abelian sandpile model: scaling fields and correlations*, J. Stat. Mech.**61**(2006), 15. - David Jerison, Lionel Levine, and Scott Sheffield,
*Logarithmic fluctuations for internal DLA*, J. Amer. Math. Soc.**25**(2012), no. 1, 271–301. MR**2833484**, DOI 10.1090/S0894-0347-2011-00716-9 - David Jerison, Lionel Levine, and Scott Sheffield,
*Internal DLA in higher dimensions*, Electron. J. Probab.**18**(2013), No. 98, 14. MR**3141799**, DOI 10.1214/EJP.v18-3137 - David Jerison, Lionel Levine, and Scott Sheffield,
*Internal DLA and the Gaussian free field*, Duke Math. J.**163**(2014), no. 2, 267–308. MR**3161315**, DOI 10.1215/00127094-2430259 - Adrien Kassel,
*Learning about critical phenomena from scribbles and sandpiles*, Modélisation Aléatoire et Statistique—Journées MAS 2014, ESAIM Proc. Surveys, vol. 51, EDP Sci., Les Ulis, 2015, pp. 60–73 (English, with English and French summaries). MR**3440791**, DOI 10.1051/proc/201551004 - Adrien Kassel and David B. Wilson,
*Looping rate and sandpile density of planar graphs*, 2014. arXiv:1402.4169 - Richard Kenyon,
*Spanning forests and the vector bundle Laplacian*, Ann. Probab.**39**(2011), no. 5, 1983–2017. MR**2884879**, DOI 10.1214/10-AOP596 - Richard W. Kenyon and David B. Wilson,
*Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs*, J. Amer. Math. Soc.**28**(2015), no. 4, 985–1030. MR**3369907**, DOI 10.1090/S0894-0347-2014-00819-5 - Gady Kozma and Ehud Schreiber,
*An asymptotic expansion for the discrete harmonic potential*, Electron. J. Probab.**9**(2004), no. 1, 1–17. MR**2041826**, DOI 10.1214/EJP.v9-170 - Gregory F. Lawler,
*A self-avoiding random walk*, Duke Math. J.**47**(1980), no. 3, 655–693. MR**587173** - Gregory F. Lawler,
*Subdiffusive fluctuations for internal diffusion limited aggregation*, Ann. Probab.**23**(1995), no. 1, 71–86. MR**1330761** - Gregory F. Lawler,
*Intersections of random walks*, Modern Birkhäuser Classics, Birkhäuser/Springer, New York, 2013. Reprint of the 1996 edition. MR**2985195**, DOI 10.1007/978-1-4614-5972-9 - Gregory F. Lawler, Maury Bramson, and David Griffeath,
*Internal diffusion limited aggregation*, Ann. Probab.**20**(1992), no. 4, 2117–2140. MR**1188055** - Lionel Levine, Mathav Murugan, Yuval Peres, and Baris Evren Ugurcan,
*The divisible sandpile at critical density*, Ann. Henri Poincaré**17**(2016), no. 7, 1677–1711. MR**3510467**, DOI 10.1007/s00023-015-0433-x - Lionel Levine, Wesley Pegden, and Charles K. Smart,
*Apollonian structure in the Abelian sandpile*, Geom. Funct. Anal.**26**(2016), no. 1, 306–336. MR**3494492**, DOI 10.1007/s00039-016-0358-7 - Lionel Levine, Wesley Pegden and Charles K. Smart,
*The Apollonian structure of integer superharmonic matrices*, 2013. arXiv:1309.3267 - Lionel Levine and Yuval Peres,
*Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile*, Potential Anal.**30**(2009), no. 1, 1–27. MR**2465710**, DOI 10.1007/s11118-008-9104-6 - Lionel Levine and Yuval Peres,
*Scaling limits for internal aggregation models with multiple sources*, J. Anal. Math.**111**(2010), 151–219. MR**2747064**, DOI 10.1007/s11854-010-0015-2 - Lionel Levine and Yuval Peres,
*The looping constant of $\Bbb Z^d$*, Random Structures Algorithms**45**(2014), no. 1, 1–13. MR**3231081**, DOI 10.1002/rsa.20478 - Dino J. Lorenzini,
*Arithmetical graphs*, Math. Ann.**285**(1989), no. 3, 481–501. MR**1019714**, DOI 10.1007/BF01455069 - S. N. Majumdar and Deepak Dhar,
*Height correlations in the Abelian sandpile model*, J. Phys. A: Math. Gen.**24**(1991), no. 7, L357. - Madhusudan Manjunath and Bernd Sturmfels,
*Monomials, binomials and Riemann-Roch*, J. Algebraic Combin.**37**(2013), no. 4, 737–756. MR**3047017**, DOI 10.1007/s10801-012-0386-9 - Fatemeh Mohammadi and Farbod Shokrieh,
*Divisors on graphs, connected flags, and syzygies*, Int. Math. Res. Not. IMRN**24**(2014), 6839–6905. MR**3291642**, DOI 10.1093/imrn/rnt186 - Paul Meakin and J. M. Deutch,
*The formation of surfaces by diffusion-limited annihilation*, J. Chem. Phys.**85**(1986), 2320. - Cristopher Moore and Martin Nilsson,
*The computational complexity of sandpiles*, J. Statist. Phys.**96**(1999), no. 1-2, 205–224. MR**1706761**, DOI 10.1023/A:1004524500416 - Robin Pemantle,
*Choosing a spanning tree for the integer lattice uniformly*, Ann. Probab.**19**(1991), no. 4, 1559–1574. MR**1127715** - Wesley Pegden and Charles K. Smart,
*Convergence of the Abelian sandpile*, Duke Math. J.**162**(2013), no. 4, 627–642. MR**3039676**, DOI 10.1215/00127094-2079677 - Wesley Pegden,
*Sandpile galleries*. http://www.math.cmu.edu/~wes/sandgallery.html - David Perkinson, Jacob Perlman, and John Wilmes,
*Primer for the algebraic geometry of sandpiles*, Tropical and non-Archimedean geometry, Contemp. Math., vol. 605, Amer. Math. Soc., Providence, RI, 2013, pp. 211–256. MR**3204273**, DOI 10.1090/conm/605/12117 - David Perkinson and Bryan Head,
*SandpilesApp*. http://people.reed.edu/~davidp/sand/program/program.html - V. S. Poghosyan and V. B. Priezzhev,
*The problem of predecessors on spanning trees*, Acta Polytechnica,**51**(2011), 1, arXiv:1010.5415 - A. M. Povolotsky, V. B. Priezzhev, and R. R. Shcherbakov,
*Dynamics of Eulerian walkers*, Physical Review E**58**(1998), no. 5, 5449. - V. B. Priezzhev,
*Structure of two dimensional sandpile. I. Height probabilities*, J. Stat. Phys.,**74**(1994), 955-979. - V. B. Priezzhev, Deepak Dhar, Abhishek Dhar and Supriya Krishnamurthy,
*Eulerian walkers as a model of self-organised criticality*, Phys. Rev. Lett.**77**(1996), 5079–5082. arXiv:cond-mat/9611019 - V. S. Poghosyan, V. B. Priezzhev and P. Ruelle,
*Return probability for the loop-erased random walk and mean height in the Abelian sandpile model: a proof*. Journal of Statistical Mechanics: Theory and Experiment**10**(2011), P10004. - James Propp,
*Random walk and random aggregation, derandomized*, 2003. http://research.microsoft.com/apps/video/default.aspx?id=104906. - Makoto Sakai,
*Quadrature domains*, Lecture Notes in Mathematics, vol. 934, Springer-Verlag, Berlin-New York, 1982. MR**663007** - Makoto Sakai,
*Solutions to the obstacle problem as Green potentials*, J. Analyse Math.**44**(1984/85), 97–116. MR**801289**, DOI 10.1007/BF02790192 - Frank Spitzer,
*Principles of random walk*, 2nd ed., Graduate Texts in Mathematics, Vol. 34, Springer-Verlag, New York-Heidelberg, 1976. MR**0388547** - Kôhei Uchiyama,
*Green’s functions for random walks on $\textbf {Z}^N$*, Proc. London Math. Soc. (3)**77**(1998), no. 1, 215–240. MR**1625467**, DOI 10.1112/S0024611598000458 - Israel A. Wagner, Michael Lindenbaum, and Alfred M. Bruckstein,
*Smell as a computational resource—a lesson we can learn from the ant*, Israel Symposium on Theory of Computing and Systems (Jerusalem, 1996) IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 219–230. MR**1436463**

## Additional Information

**Lionel Levine**- Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
- MR Author ID: 654666
**Yuval Peres**- Affiliation: Microsoft Research, Redmond, Washington 98052
- MR Author ID: 137920
- Received by editor(s): September 23, 2016
- Published electronically: April 13, 2017
- Additional Notes: The first author was supported by NSF grant DMS-1455272 and a Sloan Fellowship.
- © Copyright 2017 by Lionel Levine and Yuval Peres
- Journal: Bull. Amer. Math. Soc.
**54**(2017), 355-382 - MSC (2010): Primary 31C20, 35R35, 60G50, 60K35, 82C24
- DOI: https://doi.org/10.1090/bull/1573
- MathSciNet review: 3662912