Laplacian growth, sandpiles, and scaling limits

Levine, Lionel; Peres, Yuval

doi:10.1090/bull/1573

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