This post highlights recent work which constitutes only the third rigorous result about planar diffusion-limited aggregation (DLA), a paradigmatic model of random, dendritic growth.

The definition of DLA 🔗

DLA is a random process which grows a connected subset, or cluster, of the two-dimensional Euclidean lattice $\mathbb{Z}^2$, one element at a time.¹ It was introduced by Witten and Sander in 1981 and serves to model a variety of physical phenomena, such as electrodeposition and Hele-Shaw flow.² Start with a set $A_0 = \{o\}$ consisting of the origin $o$. One step of the dynamics is given by $$ A_{t+1} = A_t \cup \{X\},$$ where $X$ is the first site in the boundary of $A_t$ visited by a simple random walk “from infinity.” In other words, DLA is a Markov chain with transition probabilities (known in this context as growth probabilities) given by $$ P (A_{t+1} = A_t \cup \{x\} \bigm\vert A_t) = H_{\partial A_t} (x), $$

where $H_{\partial A_t}$ is the harmonic measure of $\partial A_t$,³ and where $\partial A_t$ denotes the boundary of $A_t$, i.e., elements $y$ which do not belong to $A_t$, but are at distance $| y - x| = 1$ from some element $x$ which does.

State-of-the-art simulations show that large DLA clusters have a cross-shaped backbone with many smaller scales of branching, the confluence of which forms narrow channels, called “fjords” (Figure 1).⁴ Since the “tips” of the cluster are exposed, their boundaries have greater growth probabilities than those at the bottom of the fjords. The multifractal conjecture concerns the way these growth probabilities scale with the linear size (i.e., the diameter) of the cluster.

There are few rigorous results about DLA 🔗

Before discussing the multifractal conjecture in greater detail, it is worth highlighting the extent to which DLA has evaded rigorous study. Despite being introduced more than 40 years ago, there are only two non-trivial, rigorous results about DLA on $\mathbb{Z}^2$. The first, due to Kesten,⁵ states that there is a number $C < \infty$ such that, almost surely, for all sufficiently large $t$, the diameter of the cluster at time $t$ satisfies $$ \mathrm{diam} (A_t) \leq C t^{\frac{2}{3}}. $$ This result is a consequence of an upper bound on the harmonic measure of a connected set. The second, due to Eberz-Wagner,⁶ states that, almost surely, the DLA cluster will have infinitely-many holes.

The third rigorous result about DLA comes from a harmonic measure lower bound I recently proved with Shirshendu Ganguly and Alan Hammond. This result is related to the conjectural multifractality of DLA.

The multifractal conjecture 🔗

Informally, the assertion that DLA is multifractal means that the growth probabilities on the boundary of a typical cluster exhibit power-law scaling with the linear size of such a cluster.⁷ In particular, concerning the least positive growth probability, $p_{min}$, we can make “typical” precise via expectation, by defining $$ \log p_{min} (t) = E \big[ \log \min \{ H_{\partial A_t} (x): H_{\partial A_t} (x) > 0 \} \big]. $$ Note that, in the absence of the expectation, $p_{min} (t)$ would simply be the random quantity $$ \min \{ H_{\partial A_t} (x): H_{\partial A_t} (x) > 0 \}. $$ In terms of the expected linear size $L(t) = E [\mathrm{diam} (A_t)]$ of a DLA cluster at time $t$, multifractality asserts that there is a positive number $\alpha < \infty$ such that $$ p_{min} (t) \approx L(t)^{-\alpha}, $$ where we write $f(t) \approx g(t)$ to mean that there are positive real numbers $c$ and $C$ such that $$ c g(t) \leq f(t) \leq C g(t) $$ for all sufficiently large $t$.

A rigorous result concerning the failure of multifractality 🔗

It is unclear if $\alpha$ exists. Indeed, while a pair of studies⁸ claimed to have definitively established a finite value of $\alpha$, they were based on simulations of DLA clusters over only tens of thousands of steps, whereas the later simulations of Grebenkov and Beliaev suggest that the cluster’s shape changes dramatically over 100 times as many steps. Additionally, many earlier studies (at least nine by my count) predicted that $p_{min} (t)$ decays faster than any inverse power of $L(t)$, and it is unclear how the concerns raised by these studies are addressed by the simulations which claim a finite $\alpha$.⁹ If multifractality fails for $p_{min} (t)$, meaning that no finite $\alpha$ satisfies $$ p_{min} (t) \approx L(t)^{-\alpha}, $$ then it is natural to wonder: How rapidly can $p_{min} (t)$ decrease, as a function of $L(t)$?

My recent work with Shirshendu Ganguly and Alan Hammond includes a harmonic measure lower bound, which partly addresses this question.¹⁰ Specifically, our result states that there is a positive number $C_1$ such that, if $B$ is a connected, $n$-element subset of $\mathbb{Z}^2$, then $$ \log \min \{ H_B (x): H_B (x) > 0 \} \geq -C_1 n. $$ In the context of DLA, this implies that there is a positive number $C_2$ such that, for $t \geq 1$, $$ \log p_{min} (t) \geq -C_2 t. $$

Hence, the smallest growth probability can be no smaller than exponential in $t$.

Compare this to the prediction made by Lee and Stanley¹¹ that the smallest positive growth probability $\widetilde p$ among DLA clusters with linear size $\widetilde L$ satisfies $$ \log \widetilde p \approx - \widetilde L^2, $$ which agrees with our result because the linear size at least scales as $t^{\frac{1}{2}}$. Additionally, consider the form assumed by Blumenfeld and Aharony,¹² $$ \log p_{min} (t) \approx - t^\beta, $$ which our result constrains to $\beta < 1$.

Takeaway: A result about harmonic measure leads to the third rigorous result about DLA, which is a lower bound on the smallest growth probability.