The Dimension of the Brownian Frontier is Greater Than 1.

Christopher J. Bishop^{1}, Peter W. Jones^{2}, Robin Pemantle^{3} and Yuval Peres^{4}

State University of New York, Yale University, University of Wisconsin, and University of California.

Abstract

Consider a planar Brownian motion run for finite time. The frontier or “outer boundary” of the path is the boundary of the unbounded component of the complement. Burdzy (1989) showed that the frontier has infinite length. We improve this by showing that the Hausdorff dimension of the frontier is strictly greater than 1. (It has been conjectured that the Brownian frontier has dimension 4/3, but this is still open.) The proof uses Jones’s Traveling Salesman Theorem and a self-similar tiling of the plane by fractal tiles known as Gosper Islands.

Keywords: Brownian motion, frontier, outer boundary, Hausdorff dimension, self-similar tiling, traveling salesman

1Supported in part by NSF grant # DMS 9204092 and by an Alfred P. Sloan Foundation Fellowship.

2Research partially supported by NSF grant # DMS 9213595.

3Research supported in part by National Science Foundation grant # DMS 9300191, by a Sloan Foundation Fellowship, and by a Presidential Faculty Fellowship.

4Research partially supported by NSF grant # DMS-9404391.

Figure 1: A Brownian path and its frontier

1 Introduction

Let K be any compact, connected set in the plane. The complement of K has one unbounded component and its topological boundary is called the frontier of K, denoted frontier(K). The example we are most interested in is when K is the range of a planar Brownian motion run for a finite time (see Figure 1). In this case, Mandelbrot (1982) conjectured that the Hausdorff dimension dim(frontier(K)) is 4/3. (See Falconer (1985) for the definition of Hausdorff dimension in any metric space.) Rigorously, the best proven upper bound on the dimension is 3/2 − 1/(4π^{2}) ≈ 1.475 by Burdzy and Lawler (1990). Burdzy (1989) proved that frontier(K) has infinite length; our main result improves this to a strict dimension inequality:

Theorem 1.1 Let B[0, t] denote the range of a planar Brownian motion, run until time t > 0. There is an ϵ > 0 such that with probability 1, the Hausdorff dimension dim(frontier(B[0, 1])) is at least 1 + ϵ. Moreover, with probability 1,

inf_{t>0} inf_{V} dim (frontier(B[0, t]) ∩ V ) ≥ 1 + ϵ ,

where the inner infimum is over all open sets V that intersect frontier(B[0, t]).

Remarks: The uniformity in t implies that dim(frontier(B[0, τ])) ≥ 1 + ϵ almost surely for any positive random variable τ (which may depend on the Brownian motion). We also note that our proof shows that the frontier can be replaced in the statement of the theorem by the boundary of any connected component of the complement B[0, t]^{c}. (One can also infer this from the statement of the theorem by using conformal invariance of Brownian motion). As explained at the end of Section 6, The result also extends to the frontier of the planar Brownian bridge (which is a closed Jordan curve by Burdzy and Lawler (1990)).

Bishop and Jones (1994) proved that if a compact, connected set is “uniformly wiggly at all scales”, then it has dimension strictly greater than 1. Here we adapt this to a stochastic setting in which the set is likely to be wiggly at each scale, given the behavior at previous scales. The difficulty is in handling statistical dependence.

Definitions: Let G be a compact set in the plane with complement G^{c}, and let η > 0. Denote by core(G, η) the set {z ∈ G : dist(z, G^{c}) > η · diam(G)}. Say that the compact set K η-surrounds G if core(G, η) is disjoint from the unbounded component of (K ∩ G)^{c}.

Figure 2: The Gosper island

The collection of compact planar sets equipped with the Hausdorff metric is a metric space (see Falconer (1985)). A random compact set is a measurable mapping F from a probability

Figure 3: A Brownian motion which surrounds the core and one which misses it.

space to this metric space with its Borel σ-field. The preimage of the Borel σ-field under F is denoted σ(F).

Theorem 1.2 Let G_{0} be the Gosper Island, defined in the next section and illustrated in Figure 2. There exists an absolute constant η_{0} > 0 with the following property. Suppose that c_{0} > 0, and K is a random compact connected subset of the plane such that for all images G = z + rG_{0} of G_{0} with r complex and 0 < |r| < 1 and z in the plane:

P[K η_{0}-surrounds G \underline{or} K ∩ core(G, η_{0}) = ∅ | σ(K \ G^{∘})] > c_{0},  (1)

where the conditioning is on the σ-field generated by the random set K \ G^{∘} and G^{∘} is the interior of G. Then there is an ϵ > 0, depending only on c_{0}, such that

dim(frontier(K)) ≥ 1 + ϵ

with probability 1. More generally, dim(frontier(K) ∩ V) ≥ 1 + ϵ for any open V intersecting frontier(K).

Remarks: 1. In fact, the proof in Section 3 shows that with probability 1, for any connected component Ω of K^{c} and any open V intersecting ∂Ω, there is a John domain Ω_{J} ⊂ Ω with closure \overline{Ω_{J}} contained in V, such that dim(∂Ω ∩ ∂Ω_{J}) ≥ 1 + ϵ.

2. The constant η_{0} will be chosen in the next section to ensure that no “macroscopic” line segment can be wholly contained within a 2η_{0}-neighborhood of the Gosper Island’s boundary ∂G_{0}.

The appearance of the Gosper Island might seem strange at this point, but is explained as follows. The hypothesis on K that guarantees “wiggliness” should be local to handle dependence (thus it must hold inside each G conditioned on K ∩ G^{c}). If K η_{0}-surrounds G, \underline{or} K ∩ core(G, η_{0}) = ∅, then frontier(K) cannot intersect core(G, η_{0}) . Having thus controlled frontier(K) inside G, away from the boundary of G, we must worry about how frontier(K) behaves near boundaries of cells G, as these run over a partition of the plane. If a small neighborhood of the union of the boundaries of cells G of a fixed size contains no straight line segments of length comparable to diam (G) , then no significant flatness can be introduced near cell boundaries. To apply the argument with the same constants on every scale, we need a self-similar tiling where tile boundaries have no straight portions; the Gosper Island yields such a tiling.

Proving Theorem 1.2 is the main effort of the paper and is organized as follows. Section 2 summarizes notation and useful facts about the Gosper Island. We also discuss the notion of a Whitney decomposition with respect to these tiles. Section 3 constructs a random tree of Whitney tiles for K and reduces Theorem 1.2 to a lower bound on the expected growth rate of the tree, via some general propositions on random trees. In Section 4 we state a variant of Jones’s Traveling Salesman Theorem adapted to the current setting. In Section 5 this theorem is used to derive the required lower bound on the expected growth rate of the “Whitney tree” mentioned above, which then finishes the proof of Theorem 1.2. In Section 6 we verify that the range of planar Brownian motion, killed at an independent exponential time, satisfies the hypothesis of Theorem 1.2; this easily yields Theorem 1.1.

We thank the referee for detailed and very helpful comments.

Figure 4: Substitution defining Gosper island

Figure 5: First four generation of the construction

2 Gosper Islands and Whitney tiles

The standard hexagonal tiling of the plane is not self-similar, but can be modified to obtain a self-similar tiling. Replacing each hexagon by the union of seven smaller hexagons (of area 1/7 that of the original – see Figure 4) yields a new tiling of the plane by 18-sided polygons; denote by d_{1} the Hausdorff distance between each of these polygons and the hexagon it approximates. Applying the above operation to each of the seven smaller hexagons yields a 54-sided polygon with Hausdorff distance 7^{−1/2} · d_{1} from the 18-sided polygon, which also has translates that tile the plane. Repeating this operation (properly scaled) ad infinitum, we get a sequence of polygonal tilings of the plane, that converge in the Hausdorff metric to a tiling of the plane by translates of a compact connected set G_{0} called the “Gosper Island” (see Gardner (1976) and Mandelbrot (1982)).

Notation: We normalize G_{0} to be centered at the origin and have diameter 1. Denote by D_{0} the set of translates of G_{0} that form a tiling of the plane (depicted in Figure 6). This tiling is

Figure 6: A self-similar tiling of the plane

self-similar, i.e., there is a complex number λ with |λ| > 1 such that for each tile G ∈ D_{0}, the homothetic image λ·G is the union of tiles in D_{0}. (For the tiling by Gosper Islands, |λ| = 7^{1/2}.) For each integer n, we denote by D_{n} the scaled tiling {λ^{−n} ·G : G ∈ D_{0}}, and let D = ∪_{n=0}^{∞}D_{n}. If G ∈ D_{n} we say that G is a tile of index n and write ||G|| = n. Every tile G ∈ D_{n} is contained in a unique tile of D_{n−1}, denoted parent(G). Each tile G is centrally symmetric about a “center point” z; for any non-zero, complex θ, denote by θ ⊙ G = z + θ · (G − z) the expansion of G by a factor θ around z.

We record several simple properties of the tiling by Gosper Islands, which will be useful later.

1. There is some minimal distance d_{0} between any two nonadjacent tiles of D_{0}.

2. There is an η_{0} > 0 such that any line segment of length d_{0} must intersect core(G, 2η_{0}) for some G ∈ D_{0}. (The existence of η_{0} follows by a compactness argument from the fact that ∂G_{0} contains no straight line segments.)

3. The Gosper Island G_{0} contains an open disk centered at the origin which in turn contains λ^{−1}G_{0}.

4. The blow-up λ^{3} ⊙ G contains λ ⊙ parent(G) for any G ∈ D (see Figure 7).

5. If ||G|| = ||G′|| − 1 for neighboring tiles G and G′, then λ ⊙ G contains λ ⊙ G′. (See Figure 7.)

6. The blow-up λ ⊙ G is contained in ⋃(λ ⊙ G′′) where the union is over all neighbors G′′ of G of index ||G||.

7. The boundary of G_{0} is a Jordan curve. To see this note that when we replace each segment or length r by the three segments of the next generation, they remain within distance r\sqrt{3}/14 of the segment. Thus the limiting arc is within

r \frac{\sqrt{3}}{14} ∑_{n=0}^{∞}(\frac{1}{\sqrt{7}})^{n} = \frac{r\sqrt{21}}{14(\sqrt{7} − 1)} ≈ r(0.198892),

of the segment. If I_{1}, I_{2}, I_{3} are consecutive segments of length r then dist(I_{1}, I_{3}) = r, so this shows the limiting arcs corresponding to them are at least distance r/2 apart. Thus the boundary of the Gosper Island is a Jordan curve, indeed, is the image of the unit circle under a map f satisfying

\frac{1}{C} ≤ \frac{|f(x) − f(y)|}{|x − y|^{α}} ≤ C,

where α = \frac{1}{2} log 7/ log 3.

8. For any η > 0, there is a topological annulus with a rectifiable boundary, which separates core(G_{0}, η) from the boundary ∂G_{0} of the Gosper island. (By the previous property, the interior G_{0}^{∘} of G_{0} is simply connected, so this annulus can be obtained, for instance, by applying the Riemann mapping theorem.)

Definitions: Let K be a compact connected subset of the plane. We say that G ∈ D is a Whitney tile for K if λ ⊙ G is disjoint from K, but λ ⊙ parent(G) intersects K. (See Figure 7.) Let W_{K} denote the set of Whitney tiles for K. This collection is called a Whitney decomposition of K^{c}, since it decomposes K^{c} into a countable union of tiles (disjoint except for their boundaries) each with diameter comparable to its distance from K. See Figure 8.

Figure 7: G is a Whitney tile if K misses λ ⊙ G, but hits λ ⊙ parent(G).

A chain of adjacent tiles {G_{1}, G_{2}, …, G_{j}} in W_{K} such that G_{i} ⊂ λ^{5} ⊙ G_{1} and ||G_{i}|| ≥ ||G_{i−1}|| for all i ∈ {2, …, j} is called a Whitney chain (see Figure 8). Given G ∈ W_{K}, define W_{K}^{G} ⊂ W_{K} to be the set of tiles G′ such that there is a Whitney chain {G_{1}, G_{2}, …, G_{j}} with G_{1} = G and G_{j} = G′.

Note the following property of the Whitney decomposition, which holds for any connected component Ω of K^{c}:

For any open V intersecting ∂Ω , there is a tile G_{∗} ∈ W_{K} with λ^{5} ⊙ G_{∗} ⊂ V.  (2)

Lemma 2.1 If G_{1}, G_{2} ∈ W_{K} are adjacent then ||G_{1}|| − ||G_{2}|| is 0 or ±1.

Proof: Suppose ||G_{1}|| − ||G_{2}|| ≥ 2. Let G be the tile of index ||G_{2}|| + 1 that contains G_{1}, and observe that G is adjacent to G_{2}. Then by Property 5 of the Gosper tiling, λ ⊙ parent(G_{1}) ⊂ λ ⊙ G ⊂ λ ⊙ G_{2} and maximality of G_{1} is violated.

Lemma 2.2 Suppose C ⊂ W_{K} ∩ D_{n} is a collection of tiles whose union topologically surrounds a smaller Whitney tile G ∈ W_{K} ∩ D_{n+k} where k > 0. Then C surrounds a point of K.

Figure 8: Whitney decomposition and a chain of tiles

Proof: The k-fold parent of G is a tile D ∈ D_{n} which is surrounded by C. Applying Property 6 inductively shows that the union of λ ⊙ G′ for G′ ∈ C surrounds whatever part of λ ⊙ D it does not contain. Thus maximality of G implies that λ ⊙ D intersects K, and any point of intersection is surrounded by C.

Lemma 2.3 Suppose that G ∈ W_{K} and that there is a Whitney chain from some larger tile outside λ^{5} ⊙ G to G. For any n > ||G|| define Wall(G, n) to be the set W_{K}^{G} ∩ D_{n}. (See Figure 9.) Let

E_{n} = ⋃{D : D ∈ Wall(G, n)} ∪ ∂(λ^{5} ⊙ G) .

Then E_{n} is a connected set which topologically separates G from K. Furthermore, if Γ is a Jordan curve separating G from the complement of λ^{5} ⊙ G, then every connected component of ⋃{D : D ∈ Wall(G, n)} intersecting the domain bounded by Γ also intersects Γ.

Proof: By Lemma 2.1 any path which connects G to K must hit Whitney tiles of every index larger than ||G||. Thus any such path either hits Wall(G, n) or must leave λ^{5} ⊙ G, proving that E_{n} separates G from K. Connectedness follows from the last assertion of the lemma for Γ = ∂(λ^{5} ⊙ G), so it remains only to prove the last assertion.

Figure 9: The sets Wall(G,n) and U(G,h).

Suppose to the contrary that there is a component U of ⋃{D : D ∈ Wall(G, n)} which intersects the domain bounded by Γ but is disjoint from Γ itself. The union of all Whitney tiles which are in the unbounded component of U^{c} and are adjacent to U is a connected set. By Lemma 2.1 all of these tiles have index n − 1 or n + 1. By connectedness and Lemma 2.1, they must all have a single index. Suppose they all have index n + 1. Since tiles in U can be connected to G by Whitney chains which don’t cross any tile of index n + 1, this means G is in a bounded component of the complement of U, which contradicts our assumption that G could be connected by a Whitney chain to a larger tile outside λ^{5} ⊙ G. Thus the adjacent tiles must all have index n − 1. But then by Lemma 2.2 these adjacent tiles must also surround a point of K, which implies that K is not connected, another contradiction.

Lemma 2.4 For any Whitney tile G there is a Whitney chain of tiles starting at G, staying inside λ ⊙ parent(G) and containing tiles of all generations larger than ||G||. In particular, Wall(G,n) hits λ ⊙ parent(G) for all n ≥ ||G||.

Proof: We claim it is enough to show that given a Whitney tile G there is another Whitney tile G′ such that 1. ||G′|| = ||G|| + 1.

2. G′ ⊂ λ ⊙ parent(G).

3. G′ is connected to G by a chain of tiles in λ ⊙ parent(G), all of generation ||G||.

4. λ ⊙ parent(G′) ⊂ λ ⊙ parent(G).

Given these conditions we easily construct the desired chain by induction.

So suppose G is a Whitney tile for K. By definition, K intersects λ ⊙ parent(G) and hence it must intersect one of the children of λ ⊙ parent(G). Let Ĝ denote one such child and let G̃ denote the center tile of Ĝ (i.e., the unique child which does not hit ∂Ĝ). Note that ||G̃|| = ||G||, and that G̃ cannot be a Whitney tile (since K hits Ĝ = λ ⊙ G̃). By checking a small number of cases, we see that there is a chain G = G_{0}, … G_{s} = G̃, of adjacent tiles in generation ||G|| which are disjoint from ∂(λ ⊙ parent(G)).

Let G_{j} be the first tile in the chain which is not a Whitney tile (there is one since G is Whitney but G̃ is not). Let G′ be a Whitney subtile of G_{j} which is adjacent to G_{j−1}. Since G_{j−1} is a Whitney tile of generation ||G|| Lemma 2.1 implies ||G′|| = ||G||+1. This is condition (1). Conditions (2) and (3) are obvious by construction. Finally, condition (4) holds because G_{j} is not adjacent to ∂(λ ⊙ parent(G)), so

λ ⊙ parent(G′) = λ ⊙ G_{j} ⊂ λ ⊙ parent(G).

This proves the lemma.

The next two lemmas are needed in order to show that if “major portions” of a wall of Whitney tiles can be covered by a thin strip, then K must intersect the core of an appropriate tile G′′ without η-surrounding it; the latter event is controlled by the hypothesis of Theorem 1.2.

Lemma 2.5 Fix G′ ∈ D and β ∈ (0, η_{0}). Let Û be any connected set intersecting both ∂(λ^{5} ⊙ G′) and λ^{3} ⊙ G′. Suppose that Û ∩ (λ^{5} ⊙ G′) is contained in an infinite open strip of width 2βdiam(G′). Then there is a tile G′′ contained in λ^{5} ⊙ G′ and of the same index as G′, such that Û intersects core(G′′, 2η_{0} − 2β).

Proof: Pick a point x ∈ Û ∩ (λ^{3} ⊙ G′) and choose y ∈ Û ∩ ∂(λ^{4} ⊙ G′) connected to x inside Û ∩ (λ^{4} ⊙ G′). By Property 1 of the tiling, the segment \overline{xy} has length at least d_{0} · diam(G′), so by Property 2 of the tiling, there is a tile G′′ of the same index as G′, such that \overline{xy} contains some point z ∈ core(G′′, 2η_{0}). By Property 3 and convexity of disks, z ∈ λ^{5} ⊙ G′, and therefore G′′ ⊂ λ^{5} ⊙ G′. Observe that dist(z, Û) < 2βdiam(G′), for if not, removing the open disk centered at z of radius 2βdiam(G′) from the infinite strip would contradict the connectedness of Û. This observation implies the assertion of the lemma.

Let G be any Whitney tile with λ^{5} ⊙ G not containing all of K. We will also assume (as in Lemma 2.3) that there is a Whitney chain from some larger tile outside λ^{5} ⊙ G to G. Let γ be a circle centered at center(G) which separates λ^{4} ⊙ G from ∂(λ^{5} ⊙ G). (Such a circle exists by Property 3 of the tiling.) For any positive integer h, let U(G, h) be the union of all tiles D ∈ W_{K}^{G} of index ||G|| + h such that D intersects the disk bounded by γ (see Figure 9).

Lemma 2.6 Choose a_{2} so that λ^{3−a_{2}} ≤ η_{0}/2. With G as above, let G′ be a tile in W_{K}^{G} with ||G|| < ||G′|| < ||G|| + h − a_{2} such that λ^{5} ⊙ G′ is contained in the disk bounded by γ. Suppose that U(G, h) ∩ (λ^{5} ⊙ G′) is covered by an open strip of width 2βdiamG′ with β < η_{0}/4. Then there is a tile G′′ ⊂ λ^{5} ⊙G′ of the same index as G′, such that K intersects core(G′′, η_{0}) without η_{0}-surrounding G′′.

Proof: By Lemma 2.4 G′ can be connected by a Whitney chain in λ^{3} ⊙ G′ to at least one tile G̃ of generation | G | + h. Since G′ is (by assumption) connected by a Whitney chain to G, so is G̃, and hence this tile is in U(G, h). Thus U(G, h) hits λ^{3} ⊙ G′. Now Lemma 2.3 implies that there is a connected component of U(G, h) which hits λ^{3} ⊙ G′ and also hits ∂(λ^{5} ⊙ G′). Let Û be a connected component of U(G, h) ∩ λ^{5} ⊙ G′ which hits λ^{3} ⊙ G′. Now apply Lemma 2.5 with G′ and Û and let G′′ be the tile given by the conclusion of the lemma.

Since 2η_{0} − 2β > 3η_{0}/2, we can pick a point u in U(G, h) ∩ core(G′′, 3η_{0}/2). This clearly prevents K from η_{0}-surrounding G′′. For any Whitney tile D of index ||G|| + h, the blow-up λ^{3} ⊙ D intersects K (by Property 4 of the tiling). Since U(G, h) ∩ (λ^{5} ⊙ G′) is a union of tiles of index ||G|| + h, it follows that

dist(u, K) < |λ|^{3−||G||−h} ≤ |λ|^{3−a_{2}−||G′||} ≤ \frac{η_{0}}{2} diam(G′′) ,

by the choice of a_{2}. Therefore K intersects core(G′′, η_{0}).

3 A tree of Whitney tiles

Fix a compact, connected K ⊂ C^{|}, a tile G_{∗}, and a positive integer, h. We construct a tree T̂ = T (K, G_{∗}, h) of Whitney tiles. If G_{∗} ∉ W_{K} then T̂ is empty. If G_{∗} ∈ W_{K} then we take The root of T̂ to be G_{∗}, and the remaining generations of T̂ are defined recursively as follows.

Assume T̂ has been defined up to generation n and for each G in T̂_{n}, the n^{th} generation of T̂, define T̃_{n+1}(G) to be the set of tiles D with the following properties:

1. ||D|| = ||G_{∗}|| + (n + 1)h;
2. D ∈ W_{K}^{G};
3. λ^{5} ⊙ D ⊂ λ^{5} ⊙ G.

Let T_{n+1}(G) be a subcollection of T̃_{n+1}(G) which has maximal cardinality among all subcollections C for which the expanded tiles {λ^{6} ⊙ D : D ∈ C} are disjoint. By maximality, ⋃{λ^{7} ⊙ D : D ∈ T_{n+1}(G)} contains all tiles in T̃_{n+1}(G) and therefore

|T̃_{n+1}(G)| ≤ |λ|^{14}|T_{n+1}(G)| .  (3)

The children of G in T̂ are defined to be the collection T_{n+1}(G). Some trivial inductive observations are that T̂_{n} ⊂ D_{nh+||G_{∗}||}, that each G ∈ D_{n} is connected to G_{∗} by a Whitney chain, and that the sets λ^{5} ⊙ G are disjoint as G runs over any T̂_{n}.

Some tree terminology: Let V be a countable set.

(i) A mapping T from a measure space S to the set of trees on the vertex set V is measurable with respect to a σ-field F on S, if for any pair {v, v′} ⊂ V, the event [{v, v′}is an edge of T ] is in F.

(ii) For any tree T with vertex set contained in V, and any element v ∈ V, define trunc_{v}(T) to be null if v is not a vertex of T, and otherwise let trunc_{v}(T) be T with the part below v removed; more precisely, the vertices of trunc_{v}(T) are the vertices of T not separated from the root by v, and the edges are the edges of T spanning pairs of vertices in this smaller vertex set.

For any G ∈ D, let F_{G} denote the σ-field generated by the events {D ∩ K ≠ ∅} for all tiles D for which either ||D|| ≤ ||G|| or the interior of D is disjoint from λ^{5} ⊙ G.

Lemma 3.1 Let G_{∗} and G be fixed tiles with ||G|| = nh + ||G_{∗}||. the mapping trunc_{G} ∘ T̂ from the underlying probability space to the space of trees on D, is measurable with respect to F_{G}.

Recall trunc_{G} ∘ T̂ is the

Proof: Consider an event of the form {{D, D′} is in the edge set of trunc_{G}(T̂)}, where D and D′ are tiles of index mh + ||G_{∗}|| and (m + 1)h + ||G_{∗}|| respectively, with λ^{5} ⊙ D′ ⊂ λ^{5} ⊙ D. If m ≥ n and λ^{5} ⊙ D is not disjoint from λ^{5} ⊙ G, then the edge {D, D′} cannot be in trunc_{G}(T̂). If m < n or λ^{5} ⊙ D is disjoint from λ^{5} ⊙ G then the event that {D, D′} is an edge of T̂ is the union of events witnessed by particular Whitney chains of tiles, all tiles being either disjoint from λ^{5} ⊙ G or of index at most ||G||, so the event is measurable with respect to F_{G}.

The next lemma requires the traveling salesman theorem described in the next section, so its proof is delayed until Section 5.

Lemma 3.2 Assume the random set K satisfies the hypotheses of Theorem 1.2. Fix any tile G_{∗} and h > 0 and let T̂ be the random tree T (K, G_{∗}, h). There are constants c_{1}, c_{2} > 0 such that for any tile G ∈ D_{nh+||G_{∗}||},

E[#T̂_{n+1}(G) | F_{G}] ≥ c_{1}h|λ|^{h} − c_{2}|λ|^{h}  (4)

on the event that G_{∗} ∈ W_{K}, the tile G is in T̂_{n}, and λ^{5} ⊙G_{∗} does not contain K. The constants c_{1} and c_{2} depend only on c_{0}.

To prove Theorem 1.2, we also need two general lemmas concerning trees. Define the boundary ∂T of the infinite rooted tree T to be the set of infinite self-avoiding paths from the root. The next lemma is implicit in Hawkes (1981) and can be found in a stronger form in Lyons (1990). For convenience, we include the short proof.

Lemma 3.3 Let T be an infinite rooted tree. Given constants C > 0 and θ > 1, define a metric on ∂T by

dist(ξ, ξ′) = Cθ^{−n} if ξ and ξ′ share exactly n edges.  (5)

Suppose that independent percolation with parameter p ∈ (0, 1) is performed on T, i.e., each edge of T is erased with probability 1 − p and retained with probability p, independently of all other edges. If

dim(∂T) < α = \frac{log(1/p)}{log θ}

then with probability 1, all the connected components of retained edges in T are finite.

Proof: It suffices to show that the connected component of the root is finite almost surely. For any vertex v of T, denote by |v| the number of edges between v and the root. By the dimension hypothesis and the definition of the metric on ∂T, there must exist cut-sets Π in T for which the α-dimensional cut-set sum

∑_{v∈Π} θ^{−|v|α} = ∑_{v∈Π} p^{|v|}

is arbitrarily small. But for any cutset Π, the right-hand side is the expected number of vertices in Π which are connected to the root after percolation; this expectation bounds the probability that the connected component of the root is infinite.

The next lemma formalizes the notion of a random tree which “stochastically dominates” the family tree of a branching process. We require the analogue of a filtration in our setting.

Definition: Let V be a countable set and let T be a random tree with vertex set contained in V, i.e., T is a measurable mapping from some probability space ⟨S, A, P⟩ to the set of trees on the vertex set V. Say that σ-fields {F_{v} : v ∈ V } on S form a tree-filtration if for any v, w ∈ V and any A ∈ F_{v}, the event A ∩ {w is a descendant of v in T } is F_{w}-measurable.

Lemma 3.4 Let V be a countable set and let T be a random tree with vertex set contained in V. We assume that T is rooted at a fixed v_{∗} ∈ V. Assume that b > 1 and a tree-filtration {F_{v} : v ∈ V } exists such that trunc_{v}(T) (defined before Lemma 3.1) is F_{v}-measurable for each v ∈ V, and the conditional expectation

E(number of children of v in T | F_{v}) ≥ b.

If every vertex of T has at most M children and at least m children, m ≥ 0, then

1. The probability that T is infinite is at least 1 − q > 0, where q is the unique fixed point in

[0, 1) of the polynomial

ψ(s) = s^{m} + \frac{b − m}{M − m}(s^{M} − s^{m}) .

(Observe that q = 0 when m > 0.)

2. P(T is infinite | F_{v_{∗}}) ≥ 1 − q.

3. If ∂T is endowed with the metric (5), then dim(∂T) ≥ log b/ log θ with probability at least 1 − q (θ is as in (5)).

Proof: 1. Let |T_{n}| be the size of the n^{th} generation T_{n} of T and let ψ_{n}(s) denote the n-fold iterate of ψ. We claim that for s ∈ [0, 1],

Es^{|T_{n}|} ≤ ψ_{n}(s).  (6)

When n = 1, convexity of x ↦ s^{x} implies that

s^{|T_{1}|} ≤ s^{m} + \frac{|T_{1}| − m}{M − m}(s^{M} − s^{m})

and the claim follows by taking expectations:

Es^{|T_{1}|} ≤ s^{m} + \frac{E|T_{1}| − m}{M − m}(s^{M} − s^{m}) ≤ ψ_{1}(s)

since s^{M} − s^{m} ≤ 0. For n > 1 proceed by induction. Let |T_{n+1}(v)| be the number of children of v if v ∈ T_{n} and zero otherwise, and use the argument from the n = 1 case to see that E(s^{|T_{n+1}(v)|} | F_{v}) ≤ ψ(s) on the event v ∈ T_{n} (which is an event in F_{v}). Giving V an arbitrary linear order (denoted “<”), we have in particular

E(s^{|T_{n+1}(v)|} | T_{n}and T_{n+1}(w) for w < v in T_{n}) ≤ ψ(s)

for v ∈ T_{n}. Since

s^{|T_{n+1}|} = ∏_{v∈T_{n}} s^{|T_{n+1}(v)|} , this yields E(s^{|T_{n+1}|} | T_{n}) ≤ ψ(s)^{|T_{n}|} .

Taking expectations and applying the induction hypothesis with ψ(s) in place of s gives

Es^{|T_{n+1}|} ≤ E(ψ(s)^{|T_{n}|}) ≤ ψ_{n}(ψ(s)) = ψ_{n+1}(s) ,

proving the claim (6).

From (6) we see that P(|T_{n}| = 0) ≤ Eq^{|T_{n}|} ≤ ψ(q) = q, establishing the first conclusion of the lemma.

2. By copying the derivation of (6), inserting an extra conditioning on F_{v_{∗}}, one easily verifies that E(s^{|T_{n}|} | F_{v_{∗}}) ≤ ψ_{n}(s), and the rest of the argument is the same as in the first part.

3. Let T′(v) be the connected component of the subtree of T below v after removing each vertex of T below v independently with probability 1 − p. For p > 1/b, let q_{p} ∈ (0, 1) solve q_{p} = 1 + (bp/M)(q_{p}^{M} − 1). We apply the second part of the lemma to T′(v) conditioned on F_{v} to see that

P(T′(v) is infinite | F_{v}) ≥ 1 − q_{p}

for v ∈ T. By Lemma 3.3, the event {dim(∂T) < | log p|/ log θ} is contained up to null sets in the event {T′(v) is finite for all v ∈ T_{n}}. Thus

P( dim(∂T) < | log p|/ log θ | T_{n}) ≤ P( ∩_{v∈T_{n}} T′(v) finite | T_{n})
= ∏_{v∈T_{n}} P(T′(v) finite | T_{n} , T′(w) finite for all w < v in T_{n})
≤ q_{p}^{|T_{n}|}

since each event conditioned on is in the corresponding F_{v}. Taking expectations yields

P( dim(∂T) < \frac{| log p|}{log θ}) ≤ ψ_{n}(q_{p}).

Since q_{p} < 1 for each p > 1/b, this goes to q as n → ∞, proving the last conclusion of the lemma.

Proof of Theorem 1.2: Let G_{∗} be a fixed tile and let h be a positive integer (to be specified later in the proof). Denote by A the event that G_{∗} ∈ W_{K} and λ^{5} ⊙ G_{∗} does not contain K. On the event A, let T̂ = T (K, G_{∗}, h) and let Ω_{∗} be the connected component of K^{c} that contains G_{∗}. Define a metric on ∂T̂ by

dist(ξ, ξ′) = |λ|^{−(n+1)h−||G_{∗}||} if ξ and ξ′ share exactly n edges.

Each ξ = (G_{1}, G_{2}, …) ∈ ∂T̂ defines a unique limiting point ϕ(ξ) ∈ ∂Ω_{∗} which is the decreasing limit of the set λ^{5} ⊙ G_{n}. If ξ = (G_{1}, G_{2}, …) and ξ′ = (G′_{1}, G′_{2}, …) share exactly n edges, then by definition of T̂_{n+1}, the expanded tiles λ^{6} ⊙ G_{n+1} and λ^{6} ⊙ G′_{n+1} are disjoint. Since ϕ(ξ) ∈ λ^{5} ⊙ G_{n+1} and ϕ(ξ′) ∈ λ^{5} ⊙ G′_{n+1}, it follows from Property 1 of the tiling that

|ϕ(ξ) − ϕ(ξ′)| ≥ d_{0}|λ|^{−(n+1)h−||G_{∗}||}.

Thus

|ϕ(ξ) − ϕ(ξ′)| ≥ d_{0} · dist(ξ, ξ′)

and since the range of ϕ is included in ∂Ω ∩ λ^{5} ⊙ G_{∗}, it follows that

dim(∂Ω ∩ λ^{5} ⊙ G_{∗}) ≥ dim(∂T̂).  (7)

From Lemma 3.4 and the conclusion of Lemma 3.2, we see that

dim(∂T (K, G_{∗}, h)) ≥ \frac{log(c_{1}h|λ|^{h} − c_{2}|λ|^{h})}{h log |λ|}  (8)

with probability 1, on the event that G_{∗} ∈ W_{K} and λ^{5} ⊙ G_{∗} does not contain K. Choose h to maximize the RHS of (8). Since the maximum is greater than 1, there is an ϵ > 0 for which

dim(∂T̂(K, G_{∗}, h)) ≥ 1 + ϵ

with probability 1 on this event. Finally, let Ω be any connected component of K^{c}. By property (2) of the Whitney decomposition, for any open V intersecting ∂Ω, there is a tile G_{∗} ∈ W_{K} with λ^{5} ⊙ G_{∗} ⊂ V, and the theorem follows from (7).

Remark: A planar domain Ω is called a John domain if there is a base point z_{0} ∈ Ω and a constant C > 0 so that any point x ∈ Ω can be joined to z_{0} by a curve γ_{x} ⊂ Ω so that dist(z, ∂Ω) ≥ C|x − z| for any z ∈ γ_{x}. John domains were introduced by Fritz John in 1961, and some basic facts about them can be found in Näkki and Väisälä (1994).

With the notation of the above proof, if G_{∗} ∈ W_{K} is contained in a component Ω of K^{c}, choose for every tile G ≠ G_{∗} in the tree T (K, G_{∗}, h), a Whitney chain leading to G from its unique ancestor in the previous generation of the tree. For each tile G′ in this chain, there is an open disk containing it which is contained in λ ⊙ G′ (by Property 3 of the tiling). The union of all these open disks as G′ runs over the chosen Whitney chain for G and G runs over T (K, G_{∗}, h), is a John domain Ω_{J} satisfying dim(∂Ω ∩ ∂Ω_{J}) ≥ 1 + ϵ.

4 The traveling salesman theorem

Given a set E in the plane and another bounded plane set S, we define

β_{E}(S) = (diam(S))^{−1} inf_{L∈L} sup_{z∈E∩S} dist(z, L),

where L is the set of all lines L intersecting S.

Theorem 4.1 (Jones 1990) If E ⊂C^{|} then the length of the shortest connected curve Γ containing E is bounded between (universal) constant multiples of

diam(E) + ∑_{Q} β_{E}(3 ⊙ Q)^{2}diam(Q),

where the sum is over all dyadic squares in the plane and 3 ⊙ Q is the union of a 3 by 3 grid of congruent squares with Q as the central square.

A simpler proof of this Theorem, and an extension to higher dimensions, are given in Okikiolu (1992). The theorem easily implies that the length |Γ| of any curve Γ which passes within r of every point of E satisfies

diam(E) + ∑_{diam(Q)≥r} β_{E}(3 ⊙ Q)^{2}diam(Q) ≤ c_{3}|Γ|,  (9)

where the sum is over all dyadic squares in the plane with diameter at least r. For every set S, there is a dyadic square Q of side length at most 2diam(S) for which S ⊂ 3 ⊙ Q. Picking S = λ^{5} ⊙ G for some tile G and Q accordingly, we get

β_{E}(λ^{5} ⊙ G)^{2}diam(G) ≤ 9|λ|^{−10}β_{E}(3 ⊙ Q)^{2}diam(Q)

and since each expanded square 3 ⊙ Q contains a bounded number of expanded tiles λ^{5} ⊙ G for tiles G with \sqrt{2}|λ|^{5}diam(G) ≥ diam(Q), it follows that the length of any curve passing within r of every point of E satisfies

|Γ| ≥ c_{4} (diam(E) + ∑_{diam(G)≥r} β_{E}(λ^{5} ⊙ G)^{2}diam(G)) .  (10)

We require the following corollary, which uses an idea from Bishop and Jones (1994).

Corollary 4.2 Let γ be a Jordan curve with length denoted |γ| and let C be a collection of Whitney tiles of index n. Let U denote ⋃_{D∈C} D and suppose that γ ∪ U is connected. Then there is a constant c_{5} such that the cardinality of C is at least

c_{5}|λ|^{n} (−|γ| + ∑_{G′∈Ξ(C)} β_{U}(λ^{5} ⊙ G′)^{2}diam(G′)) ,

where Ξ(C) is the collection of tiles G′ of index at most n for which λ^{5} ⊙ G′ intersects U.

Proof: Let C_{∘} be the collection of circles of radius r := |λ|^{−n} centered at points center(D) for D ∈ C. Since neighboring tiles in C give rise to intersecting circles in C_{∘}, we see that Γ := γ ∪ ⋃_{Θ∈C_{∘}} Θ is connected and passes within r of every point of γ ∪ U. Furthermore, any connected finite union of closed curves is a closed curve, and hence Γ is a curve of length at most |γ| + 2π#(C)|λ|^{−n}. Combining this with (10) shows that

#(C) ≥ \frac{|λ|^{n}}{2π} (c_{4} ∑_{diam(G′)≥r} β_{U}(λ^{5} ⊙ G′)^{2}diam(G′) − |γ|).

Since all tiles in Ξ(C) have diameter at least r, this proves the lemma.

5 Expected offspring in the Whitney tree

Proof of Lemma 3.2: Fix G_{∗} and h as in the statement of the lemma and let G be any tile in T̂_{n}. Let γ be the circle separating |λ|^{4} ⊙ G from ∂(|λ|^{5} ⊙ G), which was defined before the statement of Lemma 2.6. Let C be the collection of tiles D ∈ W_{K}^{G} of index ||G|| + h intersecting the disk bounded by γ. The union of all tiles in C is the set U = U(G, h) defined before Lemma 2.6. We want to show that the expected cardinality of T̂_{n+1}(G) is large. Since the cardinality of T̂_{n+1}(G) is at least |λ|^{−14} times the cardinality of T̃_{n+1}(G) by (3), and T̃_{n+1}(G) is a superset of C, it suffices to show that

E(#C | F_{G}) ≥ c′_{1}h|λ|^{h} − c′_{2}|λ|^{h} .

To do this, we will apply Corollary 4.2 to C, so that the set U defined in that corollary is the same as U(G, h) defined above.

We will be able to bound from below the summands in Corollary 4.2 for most, but not all, “intermediate-sized” tiles G′. Pick an integer a_{3} > 1 so that |λ|^{3−a_{3}} < d_{0}, where d_{0} is the minimal distance between nonadjacent tiles in D_{0}. Let γ̃ be a circle concentric with γ, with a smaller radius: rad(γ̃) = rad(γ) − |λ|^{5−a_{3}} (see Figure 10).

Figure 10: The circles γ and γ̃

For a_{3} < j < h, let W_{K}^{G}(j) be the set of tiles G′ ∈ W_{K}^{G} such that ||G′|| = ||G|| + j and λ^{5} ⊙ G′ intersects the disk bounded by γ̃ . For any such tile G′ the blow-up λ^{5} ⊙ G′ is contained in the disk bounded by γ.

Fix any tile G′ ∈ W_{K}^{G}(j) with a_{3} < j ≤ ||G|| + h − a_{2}, where a_{2} was specified in Lemma 2.6. That lemma implies

P (β_{U}(λ^{5} ⊙ G′) ≥ \frac{η_{0}}{4} | F_{G} and W_{K}^{G}(j))  (11)
≥ P[ ⋂_{G′′} (K η_{0}-surrounds G′′ \underline{or} K ∩core(G′′, η_{0}) = ∅) | F_{G} and W_{K}^{G}(j)] ,

where the intersection is over all tiles G′′ ⊂ λ^{5} ⊙ G′ such that ||G′′|| = ||G′||. The set of such tiles G′′ for a fixed G′ has cardinality |λ|^{10}. Enumerating these and multiplying conditional probabilities using the hypotheses of Lemma 3.2 (since the σ-fields F_{G} and σ(W_{K}^{G}(j)) are contained in σ(K \ G^{′′∘}) ) gives a lower bound of c_{0}^{|λ|^{10}} for (11), and implies that

E(β_{U}(λ^{5} ⊙ G′)^{2} | F_{G}and W_{G}^{K}(j)) ≥ (\frac{η_{0}}{4} )^{2} c_{0}^{|λ|^{10}} = c_{6} > 0 .

(This is the definition of c_{6}). Since γ is outside λ^{4} ⊙ G, the distance from γ to λ^{3} ⊙ G is at least |λ|^{3}d_{0} · diam(G), by Property 1 of the tiling. Therefore the distance from γ̃ to λ^{3} ⊙ G is at least (|λ|^{3}d_{0} − |λ|^{5−a_{3}}) · diam(G), which is greater than d_{0} · diam(G) by the choice of a_{3}. (Recall that for Gosper islands, |λ| = \sqrt{7}.)

By applying Lemma 2.3 to each of the connected components of of W_{K}^{G}(j), we see that the union of γ̃ with all the tiles in W_{K}^{G}(j) is a connected set (note that a component of W_{K}^{G}(j) not hitting γ̃ is the same as a component of Wall(G, | G | + j) missing γ̃, but hitting its interior). By Lemma 2.4, W_{K}^{G}(j) must intersect λ ⊙ parent(G) and hence λ^{3} ⊙ G. Since W_{K}^{G}(j) intersects both λ^{3} ⊙G and γ̃, it follows that its cardinality is at least d_{0}|λ|^{j}. Thus for each j ∈ (a_{3}, h−a_{2}] we have

E( ∑_{G′∈W_{K}^{G}(j)} β_{U}(λ^{5} ⊙ G′)^{2} | F_{G} and W_{G}^{K}(j)) ≥ c_{6}d_{0}|λ|^{j}.

By Corollary 4.2,

E(#C | F_{G}) ≥ c_{5}|λ|^{(n+1)h+||G_{∗}||} (−|γ| + ∑_{j=a_{3}+1}^{h−a_{2}} |λ|^{−nh−||G_{∗}||−j}c_{6}d_{0}|λ|^{j}) .

Summing gives

E(#C | F_{G}) ≥ c_{5} (c_{6}d_{0}(h − a_{2} − a_{3})|λ|^{h} − |γ| · |λ|^{(n+1)h+||G_{∗}||})

which proves the lemma since |γ| ≥ 2π|λ|^{4−nh−||G_{∗}||}.

6 The Brownian frontier: Proof of Theorem 1.1

Let P_{x} denote the law of a planar Brownian motion {B(t)}_{t≥0} started at x. We use P_{0} unless indicated explicitly otherwise. Let τ_{exp} be a positive random variable, independent of the Brownian motion, which is exponential of mean 1 (i.e., its density is e^{−t}). We will verify (1) for K = B[0, τ_{exp}]. By Brownian scaling, this will imply the first assertion of Theorem 1.1.

Notation: for any compact planar set S, denote by τ_{S} = min{t ≥ 0 : B(t) ∈ S} the first hitting time of S, which is almost surely finite if S has positive logarithmic capacity. Given η ∈ (0, 1/10), let J_{0} be a rectifiable closed Jordan curve, which is the exterior boundary of a topological annulus separating core(G_{0}, η) from ∂G_{0}. (Here the constant 1/10 can be replaced by any constant smaller than the inradius of G_{0}, and the existence of J_{0} is guaranteed by Property 8 of the tiling.) For the rest of this section, consider a homothetic image G = z_{cen}+rG_{0} of the Gosper Island G_{0}, with r ∈ (0, 1) and z_{cen} in the plane. Also, denote by J = z_{cen} + rJ_{0} the image of J_{0} in G. We must obtain estimates which are uniform in the location and scale of G, as well as in the structure of the Brownian range outside G.

Lemma 6.1 For every x ∈ core(G, η) ,

P_{x}(B[0, τ_{J}] η-surrounds G) ≥ c_{7}(η) > 0 .  (12)

Furthermore, there exists c_{8}(η) > 0 such that

P_{x}(B[0, τ_{J}] η-surrounds G and τ_{J} < τ_{exp} < τ_{∂G}) ≥ c_{8}(η)P_{x}(τ_{exp} < τ_{∂G}) .  (13)

Proof: The first estimate is immediate for G_{0}, and the general case follows by scaling. For the second, observe that by Brownian scaling, inf_{y∈J} P_{y}(τ_{∂G} > diam(G)^{2}) is a positive constant depending only on J_{0}, hence only on η. Also, clearly P(τ_{J} < 1) > 1/2 and therefore

P(τ_{J} < τ_{exp} < τ_{J} + diam(G)^{2}) > \frac{e^{−2}}{2} diam(G)^{2} , since diam(G) < 1.

Applying (12), lack of memory of exponential variables, and the strong Markov property of Brownian motion at the stopping time τ_{J}, then shows that the left-hand side of (13) is at least a constant multiple of diam(G)^{2}. On the other hand, for any x ∈ G we have P_{x}(τ_{exp} < τ_{∂G}) ≤ E_{x}(τ_{∂G}) ≤ diam(G)^{2}. This completes the proof.

Lemma 6.2 There exists c_{9}(η) > 0 such that for any tile G, for any x ∈ core(G, η) and any A ⊂ ∂G,

P_{x}(B[0, τ_{∂G}] η-surrounds G and B(τ_{∂G}) ∈ A) ≥ c_{9}(η)P_{x}(B(τ_{∂G}) ∈ A).

Proof: Recall that J is a Jordan curve of finite length separating core(G, η) from ∂G. The Harnack principle (see, e.g., Bass (1995, Theorem 1.20)) implies that there is a constant c_{10} = c_{10}(J_{0}) such that for any y, z ∈ J and for any A ⊂ ∂G,

P_{y}(B(τ_{∂G}) ∈ A) ≥ c_{10}P_{z}(B(τ_{∂G}) ∈ A).  (14)

Therefore for any x ∈ core(G, η) ,

P_{x}(B[0, τ_{J}] η-surrounds G and B(τ_{∂G}) ∈ A)
= E_{x}(1_{{B[0,τ_{J}] η-surrounds G}} · P_{B(τ_{J})}[B(τ_{∂G}) ∈ A])  (15)

Applying the Harnack inequality (14) with y = B(τ_{J}) and then invoking the estimate (12) from the previous lemma, we find that the expression (15) is at least c_{7}(η)c_{10}P_{z}(B(τ_{∂G}) ∈ A), for any z ∈ J. Finally, taking z = B(τ_{J}) and averaging with respect to P_{x} using the strong Markov property gives

P_{x}(B[0, τ_{J}] η-surrounds Gand B(τ_{∂G}) ∈ A) ≥ c_{7}(η)c_{10}P_{x}(B(τ_{∂G}) ∈ A) ,

for any Borel set A ⊂ ∂G. This proves the lemma.

Given η > 0, we abbreviate τ_{C} = τ_{core(G,η)} and partition the Brownian trajectory into three pieces:

1. Until the first time τ_{C} that the path visits core(G, η).

Formally, define B^{(1)}(t) = B(t ∧ τ_{C}) for t ≥ 0, where t ∧ s is shorthand for min{t, s}.

2. From time τ_{C} until the next visit to ∂G, denoted τ_{C,∂G} = min{t ≥ τ_{C} : B(t) ∈ ∂G}. Define B^{(2)}(t) = B((t + τ_{C}) ∧ τ_{C,∂G}) for t ≥ 0.

3. After time τ_{C,∂G}.

Denote B^{(3)}(t) = B(t + τ_{C,∂G}) for t ≥ 0.

Figure 11: The partition of the Brownian trajectory

The idea now is that B^{(1)} and B^{(3)} determine the Brownian range outside G^{∘}, and B^{(2)} has a substantial chance of η-surrounding G, even when we condition on its endpoints. However, we still have to take the exponential killing into account. Define the random variable

I = \{ \begin{matrix}1 & if & τ_{exp} < τ_{C} \\ 2 & if & τ_{C} ≤ τ_{exp} < τ_{C,∂G} \\ 3 & if & τ_{C,∂G} ≤ τ_{exp} \end{matrix}

that indicates in which part of the motion the exponential killing occurred. Finally, define

τ̃_{exp} = \{ \begin{matrix}τ_{exp} & if & I = 1 \\ τ_{C} & if & I = 2 \\ τ_{exp} − τ_{C,∂G} & if & I = 3 \end{matrix}

Proposition 6.3 For any η ∈ (0, 1/10) there is a constant c_{0} = c_{0}(η) > 0 such that for all homothetic images G = z_{cen} + rG_{0} of G_{0} with r ∈ (0, 1) and z_{cen} in the plane:

P(B[0, τ_{exp}] η-surrounds G \underline{or} B[0, τ_{exp}] ∩ core(G, η) = ∅ | A_{G}) > c_{0}  (16)

where the conditioning is on the σ-field A_{G} generated by I, B^{(1)}, B^{(3)}1_{{I=3}} and τ̃_{exp}.

Proof: On the event {I = 1}, the set B[0, τ_{exp}] is disjoint from core(G, η) . To handle the case {I = 2}, we use the strong Markov property at time τ_{C} and apply the estimate (13) to B^{(2)}. Denoting τ_{C,J} = min{t ≥ τ_{C} : B(t) ∈ ∂G}, this gives

P_{0}(B[τ_{C}, τ_{C,J}] η-surrounds G and τ_{C,J} < τ_{exp} < τ_{C,∂G} | I ≥ 2; B^{(1)})
≥ c_{8}(η)P_{0}(τ_{C} < τ_{exp} < τ_{C,∂G} | I ≥ 2; B^{(1)}) .

This proves (16) on the event I = 2.

Only the case I = 3 remains. By using the strong Markov property at time τ_{C} and applying Lemma 6.2 to B^{(2)}, we see that for any A ⊂ ∂G,

P_{0}(B[τ_{C}, τ_{C,∂G}] η-surrounds G and B(τ_{C,∂G}) ∈ A | B^{(1)}) ≥ c_{9}(η)P_{0}(B(τ_{C,∂G}) ∈ A | B^{(1)}) .

In other words,

P_{x}(B[τ_{C}, τ_{C,∂G}] η-surrounds G | B^{(1)}, B(τ_{C,∂G})) ≥ c_{9}(η) .

An application of the strong Markov property at time τ_{C,∂G} shows that this lower bound is still valid if we insert an additional conditioning on I ≥ 2 and on B^{(3)}. Finally, since P_{0}(I = 3 | I ≥ 2) ≥ e^{−1}/2 and τ̃_{exp} is conditionally independent of B[0, τ_{C,∂G}] given I = 3, this completes the proof of the proposition.

To obtain the uniformity in Theorem 1.1, we will need the following general observation.

Lemma 6.4 Let Γ : [0, ∞) → C^{|} be any continuous path and let t > 0. For any open disk U intersecting frontier(Γ[0, t]) such that Γ(t) ∉ \overline{U}, there is a δ > 0 such that for any s ∈ [t, t + δ], we have

U ∩ frontier(Γ[0, t]) ⊃ U ∩ frontier(Γ[0, s]) ≠ ∅ .  (17)

Proof: By hypothesis U intersects the unbounded component, Ω of Γ[0, t]^{c}, so there is a point u ∈ U and an unbounded curve starting from u and contained in Ω. Using the convexity of U, we can append to this curve a line-segment connecting u to a nearest point x on Γ[0, t], and thus obtain an unbounded curve ψ starting at x and contained in Ω ∪ {x}. Choose δ > 0 small enough so that Γ[t, t + δ] is disjoint from the curve ψ. This gives the right-hand side of (17) for s ∈ [t, t + δ]. If we also require that Γ[t, t + δ] is disjoint from U, then the left-hand side of (17) follows from the general fact that

frontier(Γ[0, s]) ⊂ frontier(Γ[0, t]) ∪ Γ[t, s] .

As noted by the referee the containment in (17) is actually an equality for small enough δ. However, we won’t need this fact so we omit the proof.

Proof of Theorem 1.1: The random set B[0, τ_{exp}] \ G^{∘} is completely determined by the variables generating the σ-field A_{G} defined in Proposition 6.3, so the proposition implies that K = B[0, τ_{exp}] satisfies the hypothesis (1) of Theorem 1.2.

Since B[0, τ_{exp}] has the same distribution as \sqrt{τ_{exp}}·B[0, 1], this establishes the first assertion of Theorem 1.1.

For t > 0, Let A_{t} be the event that dim(frontier(B[0, s]) ∩ V) ≥ 1 + ϵ simultaneously for all open disks V that intersect frontier(B[0, t]) and have rational centers and radii. Theorem 1.2 and Proposition 6.3 give P_{0}(A_{1}) > 0, and we must show that P_{0}(∩_{t>0}A_{t}) = 1. Denote by A_{I Q} = ∩_{s∈I Q_{+}}A_{s} the intersection over all positive rational times. Now Brownian scaling and countable additivity imply that P_{0}(A_{I Q}) = 1, so it suffices to prove that A_{I Q} ⊂ A_{t} for all t > 0. Fix t > 0 and an open disk V that intersects frontier(B[0, t]). Since frontier(B[0, t]) is connected, it must intersect some (random) open disk U = U(V, t) with rational center and radius such that U ⊂ V and B(t) ∉ \overline{U}. By the previous lemma, there is a rational s such that

frontier(B[0, t]) ∩ U ⊃ frontier(B[0, s]) ∩ U ≠ ∅ .

This implies that A_{I Q} ⊂ A_{t}, and completes the proof of the theorem.

Finally, we consider the planar Brownian bridge B_{br}, which may be defined either by conditioning the Brownian path to return to the origin, or by B_{br}(t) = B(t)−tB(1) for t ∈ [0, 1].

For every t < 1, the restrictions B_{br}|_{[0,t]} and B|_{[0,t]} have mutually absolutely continuous laws (these laws are measures on the space of continuous maps from [0, t] to the plane.) Therefore by Theorem 1.1, for every fixed t ∈ (0, 1),

dim (frontier(B_{br}[0, t])) ≥ 1 + ϵ a.s.  (18)

Consider a sequence of annuli {A_{n}} of modulus 2^{−n} around the origin. The probability that B_{br} surrounds the origin in A_{n} is bounded away from 0, so the Blumenthal 0–1 law implies that with probability 1, there is some rational t < 1 such that frontier(B_{br}[0, 1]) = frontier(B_{br}[0, t]) (see Burdzy and Lawler (1990)). Thus by (18), with probability 1,

dim (frontier(B_{br}[0, 1])) ≥ inf_{t∈I Q∩(0,1)} dim (frontier(B_{br}[0, t])) ≥ 1 + ϵ .

7 Concluding remarks

It can be shown (Krzysztof Burdzy, personal communication) that dim(frontier(B[0, 1])) is almost surely constant; this fact is not required for the arguments in this paper. The conjecture that the Brownian frontier has dimension 4/3 is related to well-known conjectures concerning self-avoiding random walks, which in turn are a model for long polymer chains. In that context, the exponent 4/3 first appeared in the non-rigorous considerations of Flory (1949); see also de Gennes (1991).

Theorem 1.2 is stated for general random sets, rather than just Brownian motion, in view of potential applications to the ranges and level-sets of other stochastic processes. Besides the range of Brownian motion, another natural random set that satisfies the hypothesis of Theorem 1.2 is the support of super-Brownian motion, i.e. the intersection of all closed sets that are assigned full measure by this measure-valued diffusion throughout its lifetime. (For the definitions see, e.g., Dawson, Iscoe, and Perkins (1989).) Equivalently, this random set may be characterized as the set of points ever visited by the path-valued process constructed by Le-Gall (1993). (This process is often referred to as “The Brownian snake”.). We are grateful to Steve Evans for enlightening discussions of super-Brownian motion.

For the special case when K is the range of planar Brownian motion, it seems likely that methods directly adapted to this case will yield better estimates for dim(frontier(K)) than those obtainable by our methods. Indeed, Gregory Lawler has informed us that immediately after he learned of our Theorem 1.1 (but without seeing its proof), he proved (using completely different methods) that the dimension of the Brownian frontier can be expressed in terms of the “double disconnection exponent” of Brownian motion. This allowed Lawler to deduce that dim(frontier(B[0, 1])) > 1.01 a.s., by invoking recent estimates of Werner (1994) on disconnection exponents. We refer the reader to Lawler’s forthcoming paper for this and several other striking results on the Brownian frontier.

Finally, we note an application to simple random walk on the square lattice ZZ^{2}. Given a finite subset S of ZZ^{2}, say that a lattice point x ∈ S is on the outer boundary of S if x is adjacent to some point in the unbounded component of ZZ^{2}\S. We remark that using the strong approximation results of Auer (1990) and our construction of the Whitney tree in Section 3, it is easy to derive the following.

Corollary 7.1 Let {S(k)} denote simple random walk on ZZ^{2}, and let ϵ > 0 be as in Theorem 1.1. Then for every ϵ_{1} < ϵ we have

lim_{n→∞} P{There are more than n^{(1+ϵ_{1})/2} points on the outer boundary of S[0, n]} = 1.

References

[1] Auer, P. (1990). Some hitting probabilities of random walks on ZZ^{2}. In: Berkes, L. Csáki, E. and Révész, P. (eds.) Limit Theorems in Probability and Statistics, North-Holland, 9–25.

[2] Bass, R. (1995). Probabilistic techniques in analysis. Springer-Verlag, New York.

[3] Bishop, C.J. and Jones. P.W. (1994). Wiggly sets and limit sets. preprint (Earlier version appeared in Hausdorff dimension and Kleinian groups, SUNY Stony Brook IMS Preprint 1994/5.

[4] Burdzy, K. (1989). Geometric properties of 2-dimensional Brownian paths. Probab. Th. Rel. Fields 81, 485–505.

[5] Burdzy, K. and Lawler, G.F. (1990). Non-intersection exponents for Brownian paths. Part II: Estimates and applications to a random fractal. Ann. Probab. 18, 981–1009.

[6] Dawson, D.A., Iscoe, I. and Perkins, E.A. (1989). Super-Brownian motion: Path properties and hitting probabilities. Probab. Th. Rel. Fields 83, 135–205.

[7] Falconer, K.J. (1985). The geometry of fractal sets . Cambridge University Press.

[8] Flory, P. (1949). The configuration of real polymer chains. J. Chem. Phys. 17, 303-310.

[9] Gardner, M. (1976). Mathematical games: In which “monster” curves force redefinition of the word “curve”. Scientific American 235, December, 124–134.

[10] de Gennes, P.-G. (1991). Scaling concepts in polymer physics. Cornell University Press.

[11] Hawkes, J. (1981). Trees generated by a simple branching process. J. London Math. Soc. 24, 373–384.

[12] John, F. (1961). Rotation and Strain. Comm. Pure Appl. Math 14, 391–413.

[13] Jones, P.W. (1990). Rectifiable sets and the travelling salesman problem. Invent. Math. 102, 1–15.

[14] Le-Gall, J.F. (1993). A calss of path-valued Markov processes and its application to superprocesses. Probab. Th. Rel. Fields 95, 25–46.

[15] Lyons, R. (1990). Random walks and percolation on trees. Ann Probab. 18, 931–958.

[16] Mandlebrot, B.B. (1982). The Fractal geometry of nature. W. H. Freeman & Co.: New York.

[17] Näkki, R. and Väisälä, J. (1991). John disks. Expositiones Math. 9, 3–43.

[18] Okikiolu, K. (1992). Characterizations of rectifiable sets in R^{n}. J. London Math. Soc. 46, 336–348.

[19] Pemantle, R. (1994). The probability that Brownian motion almost contains a line segment. Preprint.

[20] Werner, W. (1994). Some upper bounds of disconnection exponents for two-dimensional Brownian motion. Preprint.

Christopher J. Bishop Department of Mathematics, SUNY at Stony Brook, Stony Brook, NY 11794-3651.

Peter W. Jones Department of Mathematics, 10 Hillhouse Ave., Yale University, New Haven, CT 06520 .

Robin Pemantle Department of Mathematics, University of Wisconsin-Madison, Van Vleck Hall, 480 Lincoln Drive, Madison, WI 53706 .

Yuval Peres Department of Statistics, 367 Evans Hall University of California, Berkeley, CA 94720-3860 and Institute of Mathematics, Hebrew University, Jerusalem.