Intro Soup Recipe Shelf Sink Chef
Take me higher...

Threshold and Monotone Growth (continued)

Let's see how the formalism works for our Basic Example. In this case it turns out that K is a nonconvex 16-gon (Fig. 2), with vertices (1,0), (2,1), (1,1), and 13 more dictated by the symmetries of the lattice. For instance, the diagram reflects the fact that while horizontal and vertical half-spaces advance with speed 1, a half-space with slope 2 only advances at speed 5-1/2. Despite the nonconvexity, one gets K* = O (the small dark octagon in Fig. 2), which we have already shown to be the asymptotic shape L. For polygonal K one can obtain the shape (but not the size) of L geometrically by forming the intersection of half-spaces containing the origin and normal to vectors which end at a vertex of the convex hull of K. This intersection is the white octagon in Fig. 1. The size is then determined by a half-space velocity corresponding to one of the polygonal sides.

Fig. 2. K for Range 1 Box

Evidently the polar formula is valid for our Basic Example even though the boundary of O is not smooth so that the heuristics leading to the polar representation break down. In fact, formula (2.3) is always valid for Threshold Growth, and establishes Theorem 1 in full generality. A careful analysis relies on conjugate dynamics on R2, with which one can mimic the technology of Euclidean Threshold Growth; [GG1] and [GG2] provide the details, including an argument that L is always a polygon. See [Wil] for another proof of the shape theorem for discrete Threshold Growth.

There are 10 supercritical polygonal limit shapes for range 2, corresponding to thresholds 1 through 10. Fig.2 of [GG2] shows them all as overlays when the successive dynamics are run from a suitable small initial seed. Clearly, smaller polygons correspond to larger thresholds, but the number of sides varies irregularly: 4, 8, 8, 12, 8, 12, 4, 4, 8, 8. Curiously, the limits are identical for 7 and 8. Under a suitable threshold-range scaling, the asymptotic shapes for increasing threshold t and range r converge to a convex Euclidean limit with piecewise smooth boundary which is described in [GG1]. But in spite of the polar formula, we do not know how the number of polygonal sides grows with r. Thus, let us pose

Problem 1. As r increases, determine the asymptotic growth rate for the maximal number of sides in Lr,t for any supercritical t.

Another approach to asymptotic shape for monotone dynamics exploits subadditivity : the fact that growth accelerates as additional sites become occupied. More precisely, for any initial seed A0 which fills Z2 eventually, and any site x, let T(x) denote the time until An occupies x starting from A0. Suppose that once a sufficiently distant x is occupied, it must be the case that x+A0 is totally covered after s additional updates, where s is independent of x. Then for any sites x and y

T(x+y) < T(x) + T(y) + s ,

since by monotonicity it can take no longer than T(y) additional updates for the configuration covering x+A0 at time T(x) + s to reach site x+y. Extend T(x) to Euclidean vectors by identifying each site of the lattice with the unit cell centered at that site. Introduce v(x) = inf T(nx)/n. It follows easily from the above subadditivity that T(nx)/n converges to v(x), that v defines a norm, and that shape result (#) holds with the convex limit shape given implicitly as the unit ball

L = { x : v(x) < 1 }.

One uses monotonicity to show uniqueness of the limit starting from sufficiently large seeds, just as in our recursive proof of Theorem 1 for the Basic Example. This line of argument was first applied about 25 years ago in the context of random spatial interactions by D. Richardson [Ric]; Section 7 will discuss the method in more detail. Note, however, that the subadditivity approach does not show that L is a polygon, nor does it give any geometric information other than convexity and lattice symmetry.

For now, let us discuss the method's applicability to Threshold Growth models, in which case we need only manufacture a suitable A0 and s leading to the subadditivity inequality. For our Basic Example it turns out that one can take A0 = B1 and s = 4 as long as x does not belong to B2. To see this, first observe that the crystal started from B1 covers B2 after two updates. By monotonicity, A2t covers Bt , and so the process fills Z2. We formalize the choice of s as a lemma, since it will be used again in Section 7 for an extension to random dynamics.

Lemma. Let x be any occupied site at time n separated from A0 by B1-distance at least 2. Restrict the occupied set and the dynamics to x+B2 from time n on. Such dynamics will cover x + B1 at time n + 4.

Proof.Clearly An -1 must contain 3 neighbors of x. Unless those 3 occupied sites comprise a corner cell and its two adjacent neighbors (other than x), it is straighforward to check that An+3 covers x + B1 using only the dynamics restricted to that neighborhood. If the 3 sites lie in a corner, and x does not belong to A1, then a neighbor of one of the 3 sites (other than x) must have been occupied at time n - 2. In that case one can check that An+4 covers x + B1 using only the dynamics restricted to x + B2.

Of course, carrying out such explicit case checking for larger ranges and thresholds rapidly becomes unmanageable, even with the aid of a computer. In order to describe the subadditivity approach for general supercritical Threshold Growth, we digress briefly and consider some delicate combinatorial questions connected with nucleation - Which A0 manage to grow, and what is the mechanism for initial stages of growth? Say that A0 generates persistent growth if at least one new cell is occupied at every update. Call the dynamics omnivorous if for every A0 which generates persistent growth, An covers all of Z2 eventually. T. Bohman has recently proved

Theorem 2. [Boh] Threshold Growth with neighborhood Br is omnivorous for any (supercritical) r.

Bohman's proof uses clever "energy" estimates, taking about 2 journal pages for the case where t is at most r2, and much longer for general t. The latter part of his analysis depends on the geometry of squares, so it is unclear to which other neighborhoods the result generalizes. However, for Br at least, the details of the construction show that for any A0 which generates persistent growth, the subadditivity approach to shape theorem (#) applies. Note that Theorem 2 also strengthens Theorem 1, showing that the growth started from any finite seed either stops eventually or attains asymptotic shape L.



Gravner and Griffeath

Take me higher...

Intro Soup Recipe Shelf Sink Chef