Bart Lamiroy
email: bart.lamiroy@loria.fr

Yassine Guebbas

Robust Circular Arc Detection

In this paper we present a method to robustly detect circular arcs in a line drawing image. The method is fast, robust and very reliable, and is capable of assessing the quality of its detection. It is based on Random Sample Consensus minimization, and uses techniques that are inspired from object tracking in image sequences. It is based on simple initial guesses, either based on connected line segments, or on elementary mainstream arc detection algorithms. Our method consists of gradually deforming these circular arc candidates as to precisely fit onto the image strokes, or to reject them if the fitting is not possible, this virtually eliminates spurious detections on the one hand, and avoiding non-detections on the other hand.

Introduction

Finding circular arcs is one the recurring problems in graphical document interpretation or symbol recognition. The main difficulty with the existing approaches is that they often are of considerable complexity (e.g. Houghlike [START_REF] Olson | Constrained Hough Transforms for Curve Detection[END_REF] or feature grouping approaches [START_REF] Chen | An Efficient Randomized Algorithm for Detecting Circles[END_REF]) sensitive to image quality, line thickness, or rely on a number of user defined parameters or thresholds that make them extremely difficult to apply to generic problems or on heterogeneous document sets.

The approach developed in this paper reduces the set of needed parameters to a minimal set of very elementary and visually significant values and can be applied without prior knowledge of the document set, regardless of line widths, connectedness or complexity. It relies on elementary [START_REF] Fischler | Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[END_REF][START_REF] Hilaire | Robust and Accurate Vectorization of Line Drawings[END_REF]-distance transform skeletonization [START_REF] Sanniti Di Baja | Well-Shaped, Stable, and Reversible Skeletons from the (3,4)-Distance Transform[END_REF] and segment detection [START_REF] Rosin | Segmentation of Edges into Lines and Arcs[END_REF]. Unlike extremely efficient methods like [START_REF] Hilaire | Robust and Accurate Vectorization of Line Drawings[END_REF], ours does not require reasonable segmentation of arcs. This work is tightly related to [START_REF] Lamiroy | Robust Circle Detection[END_REF].

The following section establishes how to determine if a single circular arc is present, provided we have a rough initial guess of its position, and how to robustly detect and locate it using RANSAC (Random Sample Consensus [START_REF] Fischler | Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[END_REF]). Section 3 then explains how to generalize to detecting and localizing any number of circles, without a priori knowledge of their position. The last two sections conclude by eliminating spurious detections and by establishing the limits of the approach.

Determining the Presence of a Circular Arc

In this section we address the problem of detecting a circular arc, given an initial estimate of its center (x c , y c ), its radius σ, and its two endpoints p l and p r1 . This estimate, as we shall see further, can be very approximate. The main goal, in this first stage, is to detect whether or not, an arc is present in the image, near the vicinity of the given parameters.

General Algorithm

We are mainly exploiting the algorithm described in [START_REF] Lamiroy | Robust Circle Detection[END_REF], with one major adjunction. The cited method has been developed to identify and locate full circles, and therefore only needs to consider adapting to two variables: the center (x c , y c ), and the radius σ. This is not the case anymore for detecting arcs, since two parameters are added: p l and p r , the left and right endpoints.

The general approach we develop consists of taking the set P = {p i } of all pixels p i lying on the discrete circular arc A 0 defined by (x c , y c ), σ, p l and p r . As in, [START_REF] Lamiroy | Robust Circle Detection[END_REF], we define, for each of these pixels p i , the discrete line ∆ i , starting at (x c , y c ), and passing through p i . Let q i be the pixel on ∆ i that is the closest black pixel to p i . Let Q 0 a = {q i }. Q 0 a therefore is the set of all black pixels closest to the initial estimate A 0 in the direction of the circle radius.

Figure 1 gives an illustration of this estimation. Initial guesses are drawn in blue. For each conjectured circle, green pixels are those found at the correct distance from the center, while red ones lie on the radius and are closest to the circle. Now, let C 1 be the best fitting circle over Q 0 a (any criterion can be used, but we are using the Least Median of Squarescf. section 2.2), and let us generalize the previous step, such that Q t c contains the set of all black pixels closest to the theoretical circle C t in the direction of the circle radius (and similarly for Q t a ). By construction, Q t a ⊂ Q t c , and while this new set of points allows for a re-estimation of (x c , y c ), σ, the other parameters p l and p r need to be re-evaluated as well. The approach is the following: Let τ t be the error measure between A t and Q t a . i.e. τ t represents the fitness between the model A t and its corresponding data Q t a . Let A t < ⊂ A t a smaller circular arc2 than A t such that τ t < > τ t and that

∀A t⋆ |A t < ⊂ A t⋆ ⊂ A t : τ t⋆ < τ t . (1)
In other terms, A t < is a smaller arc that fits the dataset better than A t and all intermediate arcs fit less. This means that A t < is the largest sub-arc fitting the data better than A t .

We do a similar search by increasing the arc size thus obtaining A t ⊂ A t > a larger circular arc than A t such that τ t > > τ t and that

∀A t⋆ |A t ⊂ A t⋆ ⊂ A t < : τ t⋆ < τ t , (2)
A t > thus being the smallest super-arc fitting the data better than A t . We can then define A t+1 as being the argmax τ A t < , A t , A t > . Continuing this iteration until A t = A t+1 will yield the best estimate of the arc (if any) closest to the initial A 0 .

In the following sections we detail the different steps of this general approach.

Using RANSAC and LMedS

Since there is no guarantee that any A t or Q t may effectively contain points that form a circle, it may be extremely hazardous to use global minimization approaches (like Least Squares, for instance) [START_REF] Rousseeuw | Robust Regression and Outlier Detection[END_REF]. It is known that these estimators are very sensitive to outliers or spurious data that does not conform to the required model [START_REF] Berman | Large Sample Bias in Least Squares Estimators of a Circular Arc Center and Its Radius[END_REF]. Using these functions would invariably lead to degenerate convergence. RANSAC [START_REF] Fischler | Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[END_REF] is much better suited for fitting very noisy data -especially data containing measures that do not belong to the model that is to be estimated -The approach consists of selecting the strict minimum of data points required for estimating an instance of the model (e.g. three points for estimating a circle) and then computing the residual error of the other data points to this model. This is done a number of times, and the final model is the one with the lowest residual error.

More formally: let Q t be the set of model points. Q t supposedly, and in the worst case, contains a ratio of τ outliers. Let q n , q ′ n and q ′′ n be three random points belonging to Q t , and let C n be the circle defined by and passing through q n , q ′ n and q ′′ n . Let δ (C, p) be the distance of a point p to a circle C, and let Med τ (S) be the τ -quantile median value of the set S. We then define the residual error of a set of model points

Q t to a circle C n as RsdErr Q t , C n = Med τ δ (C n , p) |p ∈ Q t . (3)
RsdErr gives the maximum distance of a set of points to a circle, discarding a proportion of τ outliers.

With RANSAC we choose R random subsets of 3 points within Q t , each giving rise to the computation of a circle C n . For each subset, we compute the corresponding RsdErr Q t , C n , thus obtaining

C t+1 = argmin Cn,n∈[1...R] RsdErr Q t , C n . ( 4
)
The number of required subsets can be formally deduced from both the quality of the data (expected rate of outliers τ ), the dimensionality of the problem (here 6, since we need three points for estimating a circle, each point having two dimensions) and the required confidence in the result [START_REF] Fischler | Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[END_REF].

Robust Arc Detection

The previously presented method does a very good job of robustly determining whether there is a circular arc close to a given center and radius (x c , y c ) and σ. However, it needs some initial guess on where to search. The method we are developing here proceeds in three main phases:

1. Generate a high number of possible arc candidates, without consideration of uniqueness, overlapping or exact localization.

2. Verify the quality of each candidate using the approach described in section 2. The output of this verification is a list A of genuine arcs, correctly fitted on the image data.

3. Detect and merge multiple and/or partial detections of the same curves as to obtain a set of unique, disjoint arcs.

Arc Candidate Generation

In order to obtain the largest possible set of arc candidates, we automatically segment the image using a basic Rosin & West line segment vectorization [START_REF] Rosin | Segmentation of Edges into Lines and Arcs[END_REF]. We then simply enumerate all connected pairs of segments. Each pair gives us three points, which is exactly the amount of data that allows for getting an initial guess for a circular arc: (p 1 , p 2 , p 3 ). These points define a unique circle on the one hand, and furthermore, since they are orderedp 2 being in the middle -they define the left and right extrema for the definition of an arc. This approach is combined with direct arc detection from [START_REF] Rosin | Segmentation of Edges into Lines and Arcs[END_REF] as to produce the largest possible set of arc candidates to bootstrap our localization method (cf. section 2).

Merging of multiple detections

Since the method is based on unfiltered hypothesis generation, it has a clear tendency toward over-segmentation, as shown in Figures 2 and3. The main idea behind being tolerant towards this over-segmentation is to be confident that (almost) all image pixels belonging to an arc are covered by at least one initial arc candidate. Merging arcs should therefore result in a full coverage of each arc of the image by one unique, genuine arc. The middle column of Figures 2 and3 show the results of the hypothesis generation. We can see that some of the arcs are covered by several arc estimates and that some others are covered by adjacent -but not necessarily overlapping -sectors. Merging arc candidates representing the same circular arc in the image requires two distinct operations: merging estimates covering the same pixels and merging arc candidates not sharing the same pixels but being partial estimates of a same wider arc. These two operations can be performed by first increasing the aperture of the arcs (cf. section 3.2.1), thus making hypothetical arcs share pixels, and, secondly, merging the arc candidates sharing pixels (cf. section 3.2.3). For merging arcs, we do not use the full circle image, but the image skeleton [START_REF] Lamiroy | Robust Circle Detection[END_REF].

Increasing Aperture

To increase the aperture of an arc, we first set a threshold to the maximum distance between a point from the discrete hypothetical arc and the closest pixel, as shown in Figure 4, where the distance is measured on the line going through the center of the hypothetical arc and a point on the hypothetical arc.

The increase of the aperture of an arc is done by starting from the endpoints of the candidate arc p l and p r and then increasing the aperture pixel-wise, as long as the distance to the closest pixel remains below the threshold.

Finding Which Arcs to Merge

Once the set of maximal arc candidates obtained, overlapping ones or those lying on the same image curve need to respond to the following criteria in order to be merged:

1. A non-empty intersection between two arcs means that these two arcs are likely part of a same covering arc. However two arcs having common closest pixels are not necessarily sub-arcs of a same arc as shown in Figure 5.

2. Arcs having comparable radii are merge candidates. This is checked through a radius ratio with the formula:

|r 1 -r 2 | max (r 1 , r 2 ) < RatioRadiusError. ( 5
)
Checking the center of the circle is less robust since small changes in curvature may be visually insignificant, but generate large differences in the center position. in Grey, image pixels; in green, distance between a point on the hypothetical arc and the closest pixel; in red, threshold 3. Arcs having opposed normal vectors (cf. Figure 5) are not eligible for merging, even though they may overlap. This criterion is verified by choosing a point I from the overlapping part of two arcs, and constructing a vector --→ IO 1 that originates from I and finishes at O 1 the center of the first arc, and defining similarly a vector --→ IO 2 . We then compute the scalar product of these vectors:

--→ IO 1 • --→ IO 2 = | --→ IO 1 || --→ IO 2 | cos θ (6)
If the sign of the product is positive, we consider that the two arcs stem from the same covering one.

O1 O2 I

Figure 5: Intersection of arcs with opposed curvature signs or with significantly different radii Once these criteria are verified, three different configurations may occur for merging. They are depicted in Figure 6. In configuration A the two arcs are "adjacent" sharing some pixels, in configuration B one arc includes another and in configuration C the two arcs are "explementary". The covering arc is formed by considering that the two arcs belong to the same circle. Therefore the resulting arc is the union of the two arcs as if they had the same center and the same radius, in other words, the computation of the arc's angle and aperture is based on the angles and apertures of the two arcs.

Merging Arcs

The last phase consists of creating the final, genuine arcs by merging the selected candidates corresponding to the previously described criteria. The method developed here tries to find the three points of the equilateral triangle which is circumscribed by the merged arc circle. This increases the odds of having the best fitting circle as with this method we avoid choosing either noisy or numerically instable points. This procedure begins by choosing either the arc 1 or 2, and then computes the edge length of the circumscribed equilateral triangle

edgeLength = 2r i sin π 3 , (7)
where r i is the radius of the circle.

C i R = {p ∈ Q|δ (C, p) < RsdErr (Q, C)} . (8)
We can then define a partitioning of the points (D 1 and D 2 ) belonging to the two arc candidates, as well as their intersection

I I = R 1 ∩ R 2 , D 1 = R 1 \R 2 , D 2 = R 2 \R 1 . (9)
We then define p 3 and p 1 such that

p 3 p 1 = min p i ∈I,p j ∈D 2 |edgeLength -p i p j | (10)
and find p 2 such that p 2 p 3 + p 2 p 1 = max

p i ∈D 2 (p i p 3 + p i p 1 ). (11)
If we consider that the initial arcs belong effectively to the same circle, this method constructs the equilateral triangle and gives three points of a same circle. The more the three points are distant from each other, the more accurate the construction of the new circle is.

In fact, we are likely to find a better distributed set of three points over a circle if instead of using D 1 and D 2 we use R 1 and R 2 .

Figures 2 and3 show results on the GREC 2007 contest images. The initial images are in black, while detected arcs are in Grey (right column). In most cases all the arcs are detected, however in some cases, we can see that the arc estimate might partially cover the image arc. We can overcome this by increasing the "actual" angle as far as filterCoverage holds for the arc. In one example, some arcs are not detected, as no corresponding hypotheses are supplied as shown in Figure 2, and some arcs get merged improperly. This can be avoided by tuning the likelyOnSameArc check, as described in the next section.

Parameters and their Influence

The parameter likelyOnSameArc verifies whether the two arcs are partial estimates of a same arc by checking the criteria defined in 3.2.2. To compare two arcs radii, the RatioRadiusError 64% makes the merge possible for most arcs having common black pixels and avoids merging arcs with significantly different radii as shown in Figure 7. For the image in Figure 7 65% was too high and resulted in a loss of precision as shown within the red rectangle. preFilterCoverage checks if the percentage of pixels of the discrete estimate of the given arc lying effectively on black pixels of the original image, oversteps a cover percentage and returns a boolean. This process uses the original image instead of the skeleton image. The cover percentage of preFilterCoverage can be lower than the cover percentage defined for filterCoverage, as some intermediate arcs that do not withstand the cover percentage of filterCoverage might be merged with another arc resulting in an arc that does withstand the cover percentage of filterCoverage. The percentage 89% proved to be a good value for the cover percentage of preFilterCoverage, while 90% removed some good circles as shown in The merging algorithm can be improved by increasing the aperture of the arcs "virtually'. In other words, each arc has two angles and two apertures. The "virtual" angle and aperture are those which are increased and used to check if two arcs have to be merged. The actual angle and aperture are not changed. In fact, while increasing the actual aperture, the discrete arc of an estimate might no longer withstand the preFilterCoverage processing, as it is likely to have more pixels that are not black. Thus by keeping the initial angle and aperture unchanged we maintain arcs that were not merged. Moreover when performing the merge, the points used to construct the new arc are from the closest points of the actual arc, which is more accurate especially if we choose the points from those who belong as well to the black pixels of the image. The "virtual" increase uses the threshold defined in 3.2.1, namely a value of 3.

Conclusion and Further Work

In this paper we have presented a highly efficient and complete arc detection algorithm that needs extremely few parameters or contextual knowledge to operate. We have validated it on quite difficult images, coming from the GREC 2007 contest. Further work will include stroke width integration in order to obtain a more precise localization of the arcs, as well as a more quantitative assessment of the positioning and localization of the detected arcs.

Figure 1 :

 1 Figure 1: Example of circle hypotheses: in blue, the initial guess; in green, points correctly lying on the conjectured circle; in red, point closest to the circle.

Figure 2 :Figure 3 :Figure 4 :

 234 Figure 2: GREC 2007 contest images: original image (left) -initial hypotheses (middle) -final segmentation (right)

Figure 6 :

 6 Figure 6: Intersection configurations (top) and corresponding covering arcs (bottom). Configurations are labeled from left to right: A,B and C.

Figure 7 :

 7 Figure 7: RatioRadiusError tuning;the original image;64% filter; 65% filterThe filterCoverage parameter is used to keep only those arc candidates that have a sufficient percentage of pixels effectively lying on pixels of the image. This process uses the original image instead of the skeleton image. The coverage percentage of filterCoverage is set to 89% to ensure keeping only accurate estimates.

Figure 8 :

 8 Figure 8: Cover percentage tuning;the original image; 89% filter; 90% filter

In this document we shall conveniently ignore the fact that there is a small ambiguity with defining an arc by the center of its corresponding circle, the radius and the endpoints: one also has at least the orientation of the arc to consider as to know what part of the circle between the two endpoints is belonging to the arc, and which part isn't.

"smaller" meaning having the same center and radius, but having a smaller aperture while being fully included in the "larger" one.

Acknowledgments

Authors acknowledge funding from the PROCORE-FRANCE/HONG KONG JOINT RESEARCH SCHEME (F-HK04/05T, 9050187): Knowledge representation issues for the performance evaluation of graphic symbol recognition methods. The author more particularly thanks Prof. Liu Wenyin for having received him at the City University of Hong Kong for finalizing this work.


Bruno Schapira

Robert Young
email: rjyoung@ihes.fr

WINDINGS OF PLANAR RANDOM WALKS AND AVERAGED DEHN FUNCTION

Keywords: 2000 Mathematics Subject Classification. 52C45; 60D05 simple random walk, winding number, averaged Dehn function

We prove sharp estimates on the expected number of windings of a simple random walk on the square or triangular lattice. This gives new lower bounds on the averaged Dehn function, which measures the expected area needed to fill a random curve with a disc.

Introduction

The winding numbers of random curves have received much study, going back to Lévy [START_REF] Lévy | Processus Stochastiques et Mouvement Brownien. Suivi d'une note de M. Loève[END_REF] and Spitzer [START_REF] Spitzer | Some theorems concerning 2-dimensional Brownian motion[END_REF]. Lévy, in particular, studied the Lévy area of a planar Brownian motion, which is based on adding, with sign, the winding number of the curve around different regions of the plane. In this paper, we will study the total winding number of a random closed curve, that is, the integral of the magnitude of the winding number over the plane. The total winding number of a curve is always non-negative, unlike the Lévy area, and it is connected to problems of filling curves by discs or cycles.

Let θ t (z) be the angular part of a Brownian motion with respect to z. Spitzer showed that (ln t) -1 θ t (z) converges to the Cauchy distribution, so the winding angle of a Brownian motion can be quite large. Further results on the winding number of Brownian motion suggest that the total winding number of a loop based on Brownian motion is infinite. Werner [START_REF] Werner | Sur les points autour desquels le mouvement brownien plan tourne beaucoup[END_REF] showed that if θ t (z) is the angular part of a Brownian motion with respect to z, then (1)

k 2 area{z ∈ C | θ t (z) -θ 0 (z) ∈ [2πk, 2π(k + 1))} → t/2π
in L 2 as k → +∞. Thus if γ is the loop formed by connecting the ends of a Brownian motion by a straight line and i γ (x) is the winding number of γ around x, then

E R 2 |i γ (x)| dx = ∞.
Similarly, Yor [START_REF] Yor | Loi de l'indice du lacet brownien, et distribution de Hartman-Watson[END_REF] explicitly computed the law of the index of a point z ∈ C with respect to a Brownian loop. Using this result, one can show that there is equality in (1) for all k = 0, so the expectation above is also infinite if γ is a Brownian loop. This infinite area, however, is due to the presence of small regions with arbitrarily large winding number, which are not present if γ is the curve formed by connecting the ends of a random walk by a straight line. In fact, since γ has finite length, its total winding number is finite. Let i n (z) be the random variable corresponding to the number of times that a random walk of n steps winds around z. Windings of random walks have been studied less than windings of Brownian curves, but one result is an analogue of Spitzer's theorem for the random walk, due to Bélisle [START_REF] Bélisle | Windings of random walks[END_REF], who proved that for any fixed z ∈ C, the distribution of i n (z)/ ln n converges to the hyperbolic secant distribution as n → +∞.

In this paper, we will prove Theorem 1.1. Let (S n , n ≥ 0) be the simple random walk on the unit square lattice in the complex plane. Let S n be the loop joining the points S 0 , S 1 , . . . , S n , S 0 in order by straight lines and for z ∈ C \ S n , let i n (z) be the index of z with respect to S n . Then

E C |i n (z)| dz ∼ 1 2π n ln ln n,
when n → +∞.

Note that the integral in the theorem is well defined since S n has Lebesgue measure 0.

The basic idea of the proof is to use strong approximation to relate windings of the random walk to windings of Brownian motion. The main effect of replacing a Brownian curve with a random walk is to eliminate points with very high winding numbers, and the replacement does not affect points which are far from the Brownian motion. We thus find a lower bound on the expected winding number by considering points which are far from the random walk (Prop. 3.2). We find an upper bound by bounding the number of points with high winding numbers (Prop. 3.3). Windings around a point can be broken into classes depending on their distance from the point, and we bound the number of windings in each class separately. We will give some notation and preliminaries in Sec. 2, and prove Thm. 1.1 in Sec. 3.

In Section 4, we describe an application to geometric group theory. The isoperimetric problem is a classical problem in geometry which asks for the largest area that can be bounded by a loop of a given length. This question can be asked for a variety of spaces, and is particularly important in geometric group theory, where the growth rate of this area as a function of the length of the loop is known as the Dehn function and carries information on the geometry of a group (see [START_REF] Bridson | The geometry of the word problem, Invitations to geometry and topology[END_REF] for a survey). Gromov [Gro93, 5.A ′ 6 ] proposed studying the distribution of areas of random curves as an alternative to studying the supremal area of a curve, and the total filling area of a curve in R 2 is bounded below by its total winding number.

Finally, in Section 5, we give some extensions of Thm. 1.1, including a version that holds for the triangular lattice and a lower bound for Brownian bridges in the plane.

We first describe some notation for the growth of functions. Recall that f (x) = O(g(x)) if and only if lim sup x→∞ |f (x)/g(x)| < ∞. We define a class of quicklydecaying functions:

G = {g : R + → R + | g(k) = O(k -c ) ∀c > 0}.
We next describe some notation for planar random walks and winding numbers. Throughout this paper, we will identify R 2 with C. Let (S i , i ≥ 0) be a random walk on R 2 with i.i.d. bounded increments, E[S i -S i-1 ] = 0, and cov(S i -S i-1 ) = κI. Except express mention of the contrary, we will assume that S is the simple random walk on the unit square lattice, for which κ = 1/2. For any n, consider the rescaled process (X t , 0 ≤ t ≤ 1) defined by:

X t := S ⌊nt⌋ + (t -⌊nt⌋ n )(S ⌊nt⌋+1 -S ⌊nt⌋ ) √ κn ,
for all t ≥ 0 (the dependence on n in the notation will often be implicit). Here, ⌊x⌋ represents the largest integer which does not exceed x. Denote by C n the loop made of the curve (X t , 0 ≤ t ≤ 1) and the segment joining X 0 and X 1 . This curve connects the points of the random walk in order and joins the endpoints. Note in comparison with the notation of Theorem 1.1 that C n = S n / n/2. We will primarily work with X t and C n rather than S i and S n .

If Y t is a continuous function of t ∈ [0, 1] and z is not in its image, let ψ z Y (t) be the unique continuous lift of Im(ln(Y t -z)) such that ψ z Y (0) ∈ [0, 2π). If T = i I i is a finite disjoint union of intervals I i with endpoints x i and y i , let w z Y (T ) = i [ψ z Y (y i ) -ψ z Y (x i )]. If z is in the image of Y , set w z Y (T ) = 0. For z not in the image of C n , let j n (z) := w z X ([0, 1]) 2π , (2)
where [x] represents the closest integer to x. Note that if w z X ([0, 1]) is an odd multiple of π, then z is on the line connecting X 0 and X 1 . So if z / ∈ C n , then j n (z) is well-defined, and this is the index of z with respect to C n . Actually it will be also convenient to define j n (z) when z is on the line connecting X 0 and X 1 . In this case we set by convention

j n (z) := w z X ([0, 1]) 2π - 1 2 . (3) Observe now that i n (z n/2) = j n (z) for all z ∈ C \ C n .
One of our main tools is the fact that a random walk can be approximated by a Brownian motion. A strong approximation theorem due to Zaitsev [START_REF] Yu | Multidimensional version of the results of Komlós, Major and Tusnády for vectors with finite exponential moments[END_REF], which improves bounds of Einmahl [START_REF] Einmahl | Extensions of results of Komlós, Major, and Tusnády to the multivariate case[END_REF] and generalizes results of Komlós, Major and Tusnády [START_REF] Komlós | An approximation of partial sums of independent RV's and the sample DF. I[END_REF], implies the following:

Theorem 2.1 ([Zai98]). If (X t , 0 ≤ t ≤ 1
) is defined as above, then there is a constant c > 0 such that for any n > 1, there exists a coupling of (X t , 0 ≤ t ≤ 1) with a Brownian motion (β t , 0 ≤ t ≤ 1) such that

P sup k≤n,k∈N |X k/n -β k/n | ≥ c ln n √ n ≤ 1 n 4 .
Standard properties of the Brownian motion imply that there is a constant c ′ > 0 such that

P sup t≤1 sup h≤1/n |β t -β t+h | ≥ ln n √ n ≤ c ′ n 4 ,
for all n > 1, so there are constants c 0 > 0 and c ′′ > 0 such that

P sup t≤1 |X t -β t | ≥ c 0 ln n √ n ≤ c ′′ n 4 ,
for all n ≥ 1. Let

ǫ n := c 0 ln n √ n
and let U be the event

U = U(n) := sup t≤1 |X t -β t | ≤ ǫ n .
Let (β t , t ≥ 0) be a complex Brownian motion starting from 0. As with the random walk, we can connect the endpoints of the Brownian motion by a line segment to form a closed curve C.

If z / ∈ C, let j(z) := w z β ([0, 1]) 2π ,
be its index with respect to C. We will need to consider the number of times β winds around a point, especially when this occurs outside a ball of radius ǫ. Let B(z, r) denote the closed disc with center z ∈ C and radius r. For r ≥ 0, let

T r (z) := inf{s ≥ 0 | β s ∈ B(z, r)} (4) t r (z) := inf{s ≥ 0 | β s ∈ B(z, r)}.
For any z = 0, we have the following skew-product representation (see for instance [START_REF] Gall | Some properties of planar Brownian motion[END_REF] or [START_REF] Revuz | Continuous martingales and Brownian motion[END_REF]):

β t -z = exp(ρ z A z t + iθ z A z t )
, where ((ρ z t , θ z t ), t ≥ 0) is a two-dimensional Brownian motion, and

A z t = t 0 1 |β s -z| 2 ds for all t ≥ 0.
Note the intuition behind this representation; when β t is far from z, then A z increases slowly, so that arg(β tz) also varies slowly. For ǫ > 0 and t ≥ 0, let

(5) Z ǫ (t) := t 0 1 {|βs-z|≥ǫ} |β s -z| 2 ds 1/2
, and let Z ǫ := Z ǫ (1). This Z ǫ controls the amount of winding around z which occurs while the Brownian motion is outside B(z, ǫ). The next lemma is essentially taken from [START_REF]Electrostatic capacity, heat flow, and Brownian motion, Z. Wahrscheinlichkeitstheorie und Verw[END_REF] and Lemma 2 and Corollary 3 (ii) of [START_REF] Werner | Sur les points autour desquels le mouvement brownien plan tourne beaucoup[END_REF]. It shows, among other things, that Z ǫ is not likely to be much larger than | ln ǫ|.

Lemma 2.2.

(i) There is a g ∈ G, such that for all ǫ ∈ (0, 1/2) and all k ≥ 1,

P[Z ǫ ≥ k] ≤ g(k/| ln ǫ|).
(ii) There exists a function φ ∈ L 1 , such that for all ǫ ∈ (0, 1/2) and all z = 0,

P[t ǫ (z) ≤ 1] ≤ φ(z) | ln ǫ| .
(iii) There exists a function φ ∈ L 1 , such that for all ǫ ∈ (0, 1/2), all z = 0 and all k ≥ 1,

P[Z ǫ ≥ k] ≤ φ(z) k .
Proof. We start with part (i). The proof is essentially contained in the proof of Lemma 2 in [START_REF] Werner | Sur les points autour desquels le mouvement brownien plan tourne beaucoup[END_REF]. Let M = e √ k . Consider first the case where |z| ≤ M/2. The skew-product decomposition shows that Z ǫ (T M (z)) 2 has the distribution of the exit time of [0, ln(M/ǫ)] by a reflected Brownian motion starting from ln |z|ln ǫ if |z| > ǫ, or from 0 if |z| ≤ ǫ. The Markov property implies that this exit time is dominated by the exit time σ ln(M/ǫ) of [0, ln(M/ǫ)] by a reflected Brownian motion starting from 0. Thus

P[Z ǫ (T M (z)) ≥ k] ≤ P[σ ln(M/ǫ) ≥ k 2 ] ≤ P σ 1 ≥ k 2 ( √ k + | ln ǫ|) 2 ≤ c exp -c ′ k 2 ( √ k + | ln ǫ|) 2 ,
where c and c ′ are positive constants. For the last inequality see for instance [START_REF] Port | Brownian motion and classical potential theory[END_REF] Proposition 8.4. If k/| ln ǫ| > 1,

P[Z ǫ (T M (z)) ≥ k] ≤ c exp -c ′ k/| ln ǫ| (| ln ǫ| -1/2 + | ln ǫ|/k) 2 ≤ c exp -c ′ k 10| ln ǫ| ≤ g(k/| ln ǫ|),
for some g ∈ G.

On the other hand, since |z| ≤ M/2, by the maximal inequality, there is a g ∈ G such that

P[T M (z) ≤ 1] ≤ P[T M/2 (0) ≤ 1] ≤ g(k). The case |z| ≤ M/2 now follows from the inequality P[Z ǫ ≥ k] ≤ P[T M (z) ≤ 1] + P[Z ǫ (T M (z)) ≥ k]. Next assume that |z| > M/2. Then P[Z ǫ ≥ k] ≤ P inf s≤1 |β s -z| ≤ k -1 ≤ P[T M/2 (0) ≤ 1] ≤ g ′ (k),
for some function g ′ ∈ G, which concludes the proof of (i).

Part (ii) is essentially due to Spitzer [START_REF]Electrostatic capacity, heat flow, and Brownian motion, Z. Wahrscheinlichkeitstheorie und Verw[END_REF] (see also [START_REF] Gall | Some properties of planar Brownian motion[END_REF] for a precise statement). Part (iii) is a special case of Corollary 3 (ii) in [START_REF] Werner | Sur les points autour desquels le mouvement brownien plan tourne beaucoup[END_REF].

Let ǫ n be as in the remarks after Thm. 2.1. The consequence of (ii) in the previous lemma for the random walk is the Corollary 2.3. For any c > 0, there exists a function φ ∈ L 1 , such that for all z = 0 and sufficiently large n,

P[inf{t ≥ 0 | X t ∈ B(z, cǫ n )} ≤ 1] ≤ φ(z) ln n .
Proof. By Lemma 2.2 (ii), there is a φ ∈ L 1 and a c ′ > 0 such that for sufficiently large n,

P[inf{t ≥ 0 | X t ∈ B(z, cǫ n )} ≤ 1] ≤ P[t (c+1)ǫn (z) ≤ 1, U] + P[U c ] ≤ φ(z) ln n + c ′ n -4 .
Since the length of a step of the random walk is bounded, if n is sufficiently large

and |z| > n + 1, then P[inf{t ≥ 0 | X t ∈ B(z, cǫ n )} ≤ 1] = 0.
We thus find

P[inf{t ≥ 0 | X t ∈ B(z, cǫ n )} ≤ 1] ≤ φ(z) ln n + c ′ min n -4 , |z| -3 n ≤ φ ′ (z) ln n ,
as desired.

Proof of Theorem 1.1

Let D ⊂ C be given by

D = {z 1 + iz 2 | z 1 n/2, z 2 n/2 ∈ Z for any n}.
This is the set of points which are not on any of the edges of the rescaled lattices for the random walk, and C \ D has measure 0.

Theorem 1.1 follows by dominated convergence from the following:

Proposition 3.1. Let (S n , n ≥ 0) be the simple random walk on the unit square lattice in the complex plane. For z ∈ D, let j n (z) be defined by (2) and (3). Then

lim n→+∞ E j n (z) ln ln n = 1 0 p s (0, z) ds π for all z ∈ D,
where p s (0, z) = (2πs) -1 exp(-|z| 2 /2s). Moreover there is a function φ ∈ L 1 such that for all sufficiently large n,

E j n (z) ln ln n ≤ φ(z) for all z ∈ D.
3.1. Sketch of proof. The main idea of our proof is that there are no small windings in the rescaled random walk because the granularity of the walk makes it impossible to approach a point more closely than roughly (κn) -1/2 . We thus expect the number of windings of C n to be roughly the number of windings of the Brownian motion which stay far from z (relative to (κn) -1/2 ). This has the effect of eliminating points with large winding numbers, since points with many windings generally have many close windings. We will show that the number of points with winding number ≤ ln n remains roughly the same, but there are many fewer points with winding number > ln n.

Accordingly, we will bound the total winding number from below by considering just the points with small winding number: Proposition 3.2 (Points with low index). Let (S i , i ≥ 0) be a random walk on R 2 with i.i.d. bounded increments, E[S i -S i-1 ] = 0, and cov(S i -S i-1 ) = κI. Let X t and j n (z) be as in Sec. 2. Then

lim n→+∞ 1 ln ln n ln n k=1 P[|j n (z)| ≥ k] = 1 π 1 0 p s (0, z) ds for all z ∈ D,
and there is a φ ∈ L 1 such that for all sufficiently large n,

1 ln ln n ln n k=1 P[|j n (z)| ≥ k] ≤ φ(z) for all z ∈ D.
Werner's [START_REF] Werner | Sur les points autour desquels le mouvement brownien plan tourne beaucoup[END_REF] results (see Lemma 3.4 in the next subsection) imply that the proposition also holds for the Brownian motion; that is, when j n (z) is replaced by j(z), the number of times that the Brownian motion winds around z. This gives the lower bound required by Prop. 3.1.

In Subsection 3.2, we prove this proposition through strong approximation. Since the random walk is usually close to the Brownian motion, j n (z) and j(z) can differ only if z is close to the Brownian motion. Using Spitzer's estimate of the area of the Wiener sausage, we will show that most of the points with winding numbers ≤ ln n lie far from the curve.

This proposition relies mainly on strong approximation and not on properties of the random walk, so we can prove it for random walks with arbitrary increments. Furthermore, it can be proved using a weaker embedding theorem, such as the Skorokhod embedding theorem.

We get an upper bound by showing that there are few points with winding number > ln n. In fact, we show that Proposition 3.3. Under the hypotheses of Proposition 3.1, there is a function φ ∈ L 1 such that for all k ≥ ln n,

P[|j n (z)| ≥ k] ≤ φ(z) k for all z ∈ D.
Furthermore, there is a φ ′ ∈ L 1 such that for any ǫ > 0, any k ≥ (ln n) 1+ǫ and n large enough,

P[|j n (z)| ≥ k] ≤ ln n k 2 φ(z) for all z ∈ D.
The proof of the proposition proceeds by decomposing the random walk into pieces that are close to and far from a given point z; this technique is similar to that used by Bélisle [START_REF] Bélisle | Windings of random walks[END_REF]. We bound the amount of winding accumulated by the faraway pieces using strong approximation and Lemma 2.2. We bound the winding of the nearby pieces by noting that the random walk usually spends little time near z, and so does not accumulate a large winding number while close to z. This is different from the case of the Brownian motion, in which most of the winding around a point with high winding number occurs very close to the point.

The proof of this proposition requires stronger machinery than the proof of the lower bound. In particular, it requires that S n be the simple random walk on the square grid. Furthermore, we need the full power of Thm. 2.1, since Thm. 2.1 allows us to choose ǫ n so that the ǫ n -neighborhood of z contains roughly (ln n) 2 grid points.

Assuming the two propositions, we can prove Prop. 3.1.

Proof of Proposition 3.1. Note that by summation by parts,

E j n (z) = +∞ k=-∞ |k|P[j n (z) = k] (6) = +∞ k=1 P[|j n (z)| ≥ k].
Moreover Proposition 3.3 implies that for n large enough,

1 ln ln n ∞ k=ln n P[|j n (z)| ≥ k] ≤ ǫφ ′ (z) + φ(z) ln ln n for all z ∈ D. (7)
Proposition 3.1 now immediately follows from (6), Proposition 3.2 and (7).

We will prove Proposition 3.2 in the next subsection and Proposition 3.3 in subsections 3.3-3.6.

Points with low index.

We concentrate here on Proposition 3.2. The proof combines strong approximation [Zai98], Spitzer's estimate on the area of the Wiener sausage [START_REF]Electrostatic capacity, heat flow, and Brownian motion, Z. Wahrscheinlichkeitstheorie und Verw[END_REF], and Werner's estimate of

P[ j(z) = k] [Wer94]. Recall that Werner showed that Lemma 3.4 ([Wer94], Lemma 5).
(1) For all t > 0 and all z = 0,

x 2 P[w z β ([0, t]) ∈ [x, x + 2π]] x→∞ → 2π t 0 p s (0, z) ds.
(2) For all t > 0, there is a function φ t ∈ L 1 such that for all z = 0 and all x large enough,

x 2 P[w z β ([0, t]) ∈ [x, x + 2π]] ≤ φ t (z).
Proof of Proposition 3.2: For ǫ > 0, let W ǫ be the ǫ-neighborhood of the loop C formed by connecting the endpoints of the Brownian motion. Since W ǫ is mostly made up of the Wiener sausage of β, Spitzer's estimate [START_REF]Electrostatic capacity, heat flow, and Brownian motion, Z. Wahrscheinlichkeitstheorie und Verw[END_REF] (see also [START_REF] Gall | Some properties of planar Brownian motion[END_REF]) shows that for all z,

(8) lim ǫ→0 | ln ǫ|P[z ∈ W ǫ ] = π 1 0 p s (0, z) ds,
and that there is a φ ∈ L 1 such that (9)

P[z ∈ W ǫ ] ≤ φ(z) | ln ǫ| .
Observe that on the set U, the straight-line homotopy between C and C n lies entirely in W ǫn . So if z ∈ W ǫn , then j n (z) = j(z). Thus

P[|j n (z)| ≥ k, U] -P[| j(z)| ≥ k, U] ≤ P[z ∈ W ǫ ].
On the other hand, if j n (z) = j(z), then one of them is non-zero, so |z| ≤

sup 0≤t≤1 |X t | or |z| ≤ sup 0≤t≤1 |β t |. Therefore P[|j n (z)| ≥ k, U c ] -P[| j(z)| ≥ k, U c ] ≤ P sup 0≤t≤1 |X t | > |z|, U c + P sup 0≤t≤1 |β t | > |z|, U c ≤ P[U c ]1 {|z|<n} + min P sup 0≤t≤1 |β t | > |z| , P[U c ] . Since P[U c ] = O(n -4 ), there is a φ ′ ∈ L 1 such that P[|j n (z)| ≥ k, U c ] -P[| j(z)| ≥ k, U c ] ≤ φ ′ (z) n .
Thus

P[|j n (z)| ≥ k] -P[| j(z)| ≥ k] ≤ P[z ∈ W ǫn ] + φ ′ (z) n , (10)
and by (8),

ln n k=1 P[|j n (z)| ≥ k] - ln n k=1 P[| j(z)| ≥ k] ≤ (ln n)P[z ∈ W ǫn ] + φ ′ (z) ln n n is bounded. Thus lim n→+∞ 1 ln ln n ln n k=1 P[|j n (z)| ≥ k] = lim n→∞ 1 ln ln n ln n k=1 P[| j(z)| ≥ k] = 1 π 1 0 p s (0, z) ds,
where the last equality follows from Lemma 3.4. Finally, by (10), (9) and Lemma 3.4, there is a φ ′′ ∈ L 1 such that

P[|j n (z)| ≥ k] ≤ φ ′′ (z) k + φ ′′ (z) ln n ,
and so

ln n k=1 P[|j n (z)| ≥ k] ≤ φ ′′ (z) ln ln n + φ ′′ (z).
This concludes the proof of Proposition 3.2.

3.3.

Decomposing the winding number. In the next subsections, we will prove Proposition 3.3.

To bound the probability that a point will have large index, we will introduce a decomposition of the winding number into small, medium, and large windings, depending on their distance from the point. We will then use different methods to bound the number of windings. During large windings, the random walk stays away from the point and is well-approximated by the Brownian motion. The number of medium and small windings is bounded by the fact that the random walk spends little time near the point, and while the bounds on the medium and large windings only use strong approximation, the bound on the small windings uses the full power of Thm. 2.1.

Define the stopping times (τ i , i ≥ 0) and (σ i , i ≥ 1) by τ 0 := 0,

σ i := inf{t ≥ τ i-1 | |β t -z| < 2ǫ n } ∀i ≥ 1, τ i := inf{t ≥ σ i | |β t -z| > 4ǫ n } ∀i ≥ 1.
These times divide the curve into pieces close to z and far from z.

If t ∈ [σ i , τ i ), then |β t -z| ≤ 4ǫ n ; if t ∈ [τ i , σ i+1 ), then |β t -z| ≥ 2ǫ n . Let T := i≥0 [τ i , σ i+1 ) ∩ [0, 1];
this is a.s. a finite union of intervals during which |β t -z| ≥ 2ǫ n .

We also break the random walk into excursions with winding number ±1/2; this decomposition relies on the assumption that (S i , i ≥ 0) is a nearest-neighbor walk on a square lattice, and this is the main step that requires this assumption. Let ẑ be the center of the square in the rescaled lattice containing z; since z ∈ D, this is unique. Let ∆ ± z := ẑ ± (1 + i)R + be the halves of the diagonal line through ẑ. If the random walk hits ∆ + z before ∆ - z , define

e 0 := inf{t ≥ 0 | X t ∈ ∆ + z } e 2i+1 := inf{t ≥ e 2i | X t ∈ ∆ - z } e 2i := inf{t ≥ e 2i-1 | X t ∈ ∆ +
z }; otherwise, define the e i 's with + andswitched. Note that e i ∈ Z/n for all i. We call intervals of the form [e i , e i+1 ] excursions with respect to z, and let E = E(z) be the set of all such excursions which are subsets of [0, 1]. If e = [t 1 , t 2 ] is an excursion, set w(e) := w z X ([t 1 , t 2 ])/2π = ±1/2. Then w z X ([0, 1]) 2π -e∈E w(e) ≤ 2.

We will classify these excursions as small, medium, or large. Let

E sm = E sm (z) := {[u, v] ∈ E | |X u -z| ≤ ǫ n },
be the set of excursions starting close to z; we call them small excursions. Let

E lg = E lg (z) := {[u, v] ∈ E | [u, v] ⊂ T }.
These large excursions stay far from z. On the set U, these two sets are disjoint. Let

E md = E md (z) := E \ (E sm ∪ E lg )
be the set of medium excursions, so that every excursion is either small, medium, or large. Proposition 3.3 is a consequence of the following lemmas.

Lemma 3.5. There exists a function φ ∈ L 1 , such that for all sufficiently large n, all k ≥ 1, and all z ∈ D,

(i) P e∈Esm w(e) ≥ k ≤ ln n k 2 φ(z). (ii) P e∈E md w(e) ≥ k ≤ ln n k 2 φ(z).
Lemma 3.6.

(i) There is a function φ ∈ L 1 , such that for any ǫ > 0, all sufficiently large n and k ≥ (ln n) 1+ǫ ,

P e∈E lg w(e) ≥ k ≤ ln n k 2 φ(z) for all z ∈ D.
(ii) There exists a function φ ∈ L 1 , such that for all sufficiently large n and all k ≥ 1,

P e∈E lg w(e) ≥ k ≤ φ(z) k for all z ∈ D.
We will prove these lemmas in the next three subsections.

3.4. Small excursions. In this subsection, we will prove Lemma 3.5 (i) by using results on the occupation times of points by a random walk on a lattice. We first show that the symmetry of the random walk implies that excursions are equally likely to go clockwise or counterclockwise. For the simple random walk, this follows from the fact that reflecting an excursion across the line ∆ + z ∪ ∆ - z results in an equally probable excursion which winds in the opposite direction, but there is also an argument which relies only on the random walk being symmetric. Let [e i , e i+1 ] be an excursion from ∆ + z to ∆ - z and let

t 0 = max{t ∈ [e i , e i+1 ] | X t ∈ ∆ + z }.
The portion of the excursion between t 0 and e i+1 travels between p 1 = X t0 and p 2 = X ei+1 . Its time reversal travels from p 2 to p 1 . Rotating this curve by 180 degrees and translating gives a curve going from p 1 to p 2 which winds around z in the opposite direction of the original. Replacing the section of the excursion between t 0 and e i+1 by this rotated curve is a measure-preserving map on the space of random walk paths. This map doesn't change E or E sm and changes the direction of the excursion from clockwise to counterclockwise or vice versa, so the variables w([e i , e i+1 ]) are independent and take values from {-1/2, 1/2} with equal probability. Furthermore,

E e∈Esm w(e) 2 = 1 4 E[#E sm ].
Many points have no small excursions; if the random walk never comes close to z, then

E sm = ∅. Let τ = inf{t ≥ 0 | X t ∈ B(z, 2ǫ n )}. Then by Corollary 2.3, P[τ ≤ 1] ≤ φ(z) ln n ,
for some φ ∈ L 1 . Applying the Markov property, this gives

P e∈Esm w(e) ≥ k ≤ 1 4 E[#E sm ] k 2 φ(z) ln n ,
where the expectation on the right hand side is taken conditionally on the past before time τ . Since each small excursion starts at a point in (∆

+ z ∪ ∆ - z ) ∩ B(z, ǫ n ),
the number #E sm of small excursions is bounded by the number of visits to such points; it is well known that the mean number of visits to each site is bounded by c ln n for some constant c. Since the number of lattice points in (∆ + z ∪∆ - z )∩B(z, ǫ n ) is of order ln n, we get E[#E sm ] ≤ c(ln n) 2 , for some constant c > 0, which establishes Lemma 3.5 (i).

3.5. Medium excursions. On the set U, medium excursions start outside of B(z, ǫ n ) and enter B(z, 5ǫ n ) at some point. We will divide the medium excursions into two classes, depending on whether they start inside or outside the ball B(z, 8ǫ n ), and bound the number in each class.

Let

E ′ md = E ′ md (z) := {[t 1 , t 2 ] ∈ E md | |X t1 -z| > 8ǫ n }
, be the set of medium excursions starting outside B(z, 8ǫ n ) and

E ′′ md = E ′′ md (z) := {[t 1 , t 2 ] ∈ E md | |X t1 -z| ≤ 8ǫ n }, be its complement. Given 0 < a < b, define the sequences of stopping times τ a,b 0 := 0, σ a,b i = σ a,b i (z) := inf{t ≥ τ a,b i-1 | |β t -z| < aǫ n } ∀i ≥ 1, τ a,b i = τ a,b i (z) := inf{t ≥ σ a,b i | |β t -z| > bǫ n } ∀i ≥ 1.
These stopping times record the number of times the Brownian motion crosses the annulus B(z, bǫ n )\B(z, aǫ n ). Using the skew-product decomposition, we can bound the number of such crossings that occur before time 1:

Lemma 3.7. For any 0 < a < b, there are a constant c > 0 and functions φ ∈ L 1 and g ∈ G, such that for sufficiently large n and all z ∈ C,

P[σ a,b i < 1] ≤ φ(z) ln n 1 - c ln n i + g(n) ≤ φ(z)
ln n e -ci/ ln n + g(n).

Proof. Recall the definitions of T r (z) and t r (z) from (4). By the skew-product decomposition, there is a constant c > 0 (depending on a and b) such that a Brownian motion starting on the circle of radius bǫ n around z has probability p ≤ 1c/ ln n of entering B(z, aǫ n ) before escaping B(z, n). Thus, if σ a,b i < T n (z), then a.s. τ a,b i < T n (z) and

P[σ a,b i+1 < T n (z) | σ a,b i < T n (z)] = p. Thus P[σ a,b i < T n (z) | σ a,b 1 < T n (z)] = p i . Furthermore it is well known that P[T n (z) < 1] ≤ g(n),
for some g ∈ G. Now σ a,b 1 = t aǫn (z) and by Lemma 2.2 (ii), there is a φ ∈ L 1 such that for all sufficiently large n,

P[σ a,b 1 < 1] = P[t aǫn (z) < 1] ≤ φ(z) ln n .
We conclude that

P[σ a,b i < 1] ≤ P[σ a,b i < T n (z), σ a,b 1 < 1] + g(n) ≤ φ(z) ln n p i + g(n),
as desired.

On U, the Brownian motion crosses the annulus B(z, 7ǫ n )\ B(z, 6ǫ n ) during each excursion in E ′ md . Thus, there are φ, φ ′ ∈ L 1 such that for all sufficiently large n,

P[#E ′ md > k] ≤ P[σ 6,7 k < 1] + P[U c ] (11) ≤ φ(z) ln n e -ck/ ln n + O(n -4 ) ≤ φ ′ (z) ln n k 2 + O(n -4
). for all k.

To bound the cardinality of E ′′ md , we will show that if E ′′ md is large, then the rescaled random walk likely crosses the annulus

B(z, 11ǫ n ) \ B(z, 8ǫ n ) many times before time 1. First note that, on U, E ′′ md ⊂ Ē := {[t 1 , t 2 ] ∈ E | ǫ n ≤ |X t1 -z| ≤ 8ǫ n }.
Using strong approximation and the skew-product decomposition, one can show that the probability that a random walk started in

(B(z, 8ǫ n ) \ B(z, ǫ n )) ∩ ∆ + z leaves B(z, 11ǫ n ) before hitting ∆ -
z is bounded away from zero, say by p > 0. Let η be the number of times the random walk crosses from inside B(z, 8ǫ n ) to outside B(z, 11ǫ n ). Let {x i } be a sequence of independent random variables with P[x i = 1] = p, P[x i = 0] = 1p. Since the starting times of excursions in Ē form a sequence of stopping times,

P[# Ē ≥ 2k/p, η ≤ k] ≤ P 2k/p i=1 x i ≤ k ≤ e -ck ,
for some c > 0. So by reproducing the steps of (11), we get

P[# Ē ≥ 2k/p] ≤ φ(z) ln n k 2 + O(n -4 ), for some φ ∈ L 1 .
Combining the bounds on #E ′ md and #E ′′ md , we see that there is some φ ∈ L 1 such that

P e∈E md w(e) ≥ 1 + 2 p k ≤ P #E md ≥ 1 + 2 p k ≤ φ(z) ln n k 2 + O(n -4 ).
We can eliminate the O(n -4 ) term using an argument like the one in the proof of Corollary 2.3. That is, the number of medium excursions is at most n, and if |z| > n/κ, then the random walk does not come near z. So

P e∈E md w(e) ≥ 1 + 2 p k ≤ φ(z) ln n k 2 + cn -4 1 {|z|≤ √ n/κ} 1 {(1+2/p)k≤n} ≤ φ ′ (z)
ln n k 2 , for some c > 0 and φ ′ ∈ L 1 , as desired. This proves Lemma 3.5 (ii).

3.6. Large excursions. In this subsection, we will prove Lemma 3.6 using strong approximation.

Note first that on the set U, the winding of the Brownian motion during T is approximated by the winding number of the large excursions. The difference between the two arises from excursions which intersect the beginning or end of an interval of T ; each such interval can thus increase the difference by at most 1. Thus on the set U,

e∈E lg w(e) ≤ w z β (T ) 2π + #{i | τ i ≤ 1} + 1, and (12)
P e∈E lg w(e) > 2k + 1 ≤ P w z β (T ) 2π ≥ k + P [#{i | τ i ≤ 1} > k] + P[U c ].
By Lemma 3.7, we have

(13) P[#{i | τ i ≤ 1} > k] ≤ ln n k 2 φ(z) + g(n),
for some φ ∈ L 1 and g ∈ G. To prove Lemma 3.6, it thus suffices to bound

P w z β (T ) 2π ≥ k . Let Z := T ds |β s -z| 2 1/2 .
Since T is a finite union of intervals whose endpoints are stopping times for the Brownian motion, w z β (T ∩ [0, t]) is a continuous local martingale whose quadratic variation at time 1 is Z 2 . Thus w z β (T ) is equal in law to γ Z, with γ a standard normal variable. If Z ǫn is given by (5), then Z ≤ Z ǫn , and we get

P |w z β (T )| ≥ k ≤ P [|γ|Z ǫn ≥ k] .
We first show part (i) of the lemma. Let δ > 0 be such that (1δ)(1 + ǫ) > 1. Then by Lemma 2.2 (i), for n sufficiently large depending on ǫ and k ≥ (ln n) 1+ǫ , there are c > 0 , c ′ > 0, ǫ ′ > 0 and g ′ , g ′′ ∈ G such that

P [|γ|Z ǫn ≥ k] ≤ P |γ| ≥ k δ + P Z ǫn ≥ k 1-δ ≤ c ′ e -k 2δ /2 + g(k 1-δ /| ln ǫ n |) ≤ c ′ e -k 2δ /2 + g ′ (ck ǫ ′ ) ≤ g ′′ (k).
Thus for sufficiently large n and k ≥ (ln n) 1+ǫ ,

P[|w z β (T )| ≥ k] ≤ k -4 .
Moreover, if |w z β (T )| ≥ π, then we must have T |z|/2 (0) ≤ 1; this has probability less than e -d|z| 2 for some constant d > 0. By interpolation this gives (14)

P |w z β (T )| ≥ k ≤ k -2 e -d|z| 2 /2 .
Thus by ( 12), (13), and ( 14) there is a φ ∈ L 1 , independent of ǫ, such that for all sufficiently large n and k ≥ (ln n) 1+ǫ ,

P e∈E lg w(e) ≥ k ≤ ln n k 2 φ(z) + O(n -4 ).
As in the previous subsection, we can eliminate the O(n -4 ) term by changing φ. This proves part (i) of Lemma 3.6. For part (ii), we use Lemma 2.2 (iii). If n is sufficiently large, we have

P [|γ|Z ǫn ≥ k] = ∞ 0 2 √ 2π e -x 2 /2 P Z ǫn ≥ k x dx ≤ ∞ 0 2 √ 2π e -x 2 /2 φ(z)x k dx = 2 √ 2π φ(z) k ,
for some φ ∈ L 1 . Thus

P e∈E lg w(e) > k ≤ φ ′ (z) k + O(n -4 ),
for some φ ′ ∈ L 1 , and as above, the O(n -4 ) term can be absorbed into φ ′ .

Application to the study of Dehn functions

One motivation for studying the winding numbers of random walks comes from geometric group theory, namely the study of Dehn functions. For an introduction to Dehn functions with rigorous definitions, see [START_REF] Bridson | The geometry of the word problem, Invitations to geometry and topology[END_REF]; we will only sketch the definitions. Given a closed curve γ in a space X, one can ask for the infimal area of a disc with boundary γ. We call this the filling area of γ, denoted δ(γ), and define a function δ so that δ(n) is the supremal filling area of curves in X with length at most n; this is the Dehn function of X.

Gromov noted that when a group G acts properly discontinuously and cocompactly on a connected, simply connected space X, the filling area of curves can be described in terms of G [START_REF] Gromov | Asymptotic invariants of infinite groups, Geometric group theory[END_REF]. Roughly, formal products of generators of G (words) correspond to curves in X and conversely, curves in X can be approximated by words. For example, if X is the universal cover of a compact space M and G = π 1 (M ), generators of G correspond to closed curves in M . A formal product w of generators corresponds to a concatenation of these curves, and if w represents the identity in G, this concatenation lifts to a closed curve in X. A disc whose boundary is this curve corresponds to a way of using the relators of G to show that w represents the identity. We define the Dehn function of a group similarly to that of a space; if w is a word, let w be the element of G represented by w, and if w is the identity, let the filling area δ(w) of w be the minimal number of applications of relators necessary to reduce w to the identity. Define the Dehn function δ of G so that δ(n) is the maximal filling area of words with length at most n. The Dehn function of a group depends a priori on the presentation of the group, but one can show that the growth rate of δ is a group invariant and that the Dehn function of G grows at the same rate as that of X.

The Dehn function measures maximal filling area; Gromov [Gro93, 5.A ′ 6 ] also proposed studying the distribution of δ(w) when w is a random word of length n. This has led to multiple versions of an averaged Dehn function or mean Dehn function; see [START_REF] Bogopolski | The mean Dehn functions of abelian groups[END_REF] for some alternatives to our definition. We will give definitions based on random walks. Given a random walk on G supported on the generators, paths of the random walk correspond to words; in particular, the random walk induces a measure on the set of words of length n. We can thus define the averaged Dehn function δ avg (n) to be the expectation of δ(w) with respect to this measure, conditioned on the event that w represents the identity in G. If the random walk has a nonzero probability of not moving at each step, this is defined for all n. The averaged Dehn function is not known to be a group invariant and it is possible that its growth depends on the transition probabilities of the random walk.

The averaged Dehn function often behaves differently than the Dehn function. For example, in Z 2 , the Dehn function is quadratic, corresponding to the fact that a curve of length n in R 2 encloses an area at most quadratic in n. On the other hand, random walks in Z 2 enclose much less area, and the averaged Dehn function is at most O(n ln n) for a wide variety of random walks. A similar phenomenon occurs in nilpotent groups; if δ(n) = O(n k ) for some k > 2, then δ avg (n) = O(n k/2 ) for many random walks [START_REF] Young | Averaged Dehn functions for nilpotent groups[END_REF].

Since the averaged Dehn function involves bridges of random walks on groups, it is often difficult to work with. M. Sapir has proposed an alternative, the random Dehn function [START_REF] Bogopolski | The mean Dehn functions of abelian groups[END_REF], which depends on a choice of a random walk and a choice of a word v x for every element x ∈ G so that v x represents x -1 . If w is a word, wv w is a word representing the identity; essentially, the v x give a way to close up any path. One can then define

δ rnd (n) = E[δ(wv w )]
where w is chosen from the set of words of length n with measure corresponding to the random walk. This function depends on the choice of v x , but if the v x are short enough, the choice may not affect the function. In particular, Proposition 3.2 implies the following: Winding numbers provide a lower bound on the filling area of curves in the plane; if γ : S 1 → R 2 , and f : D 2 → R 2 is a PL or smooth map with boundary γ, then #f -1 (x) ≥ |i n (x)| away from a set of measure zero and thus

area f ≥ R 2 |i γ (x)| dx.
Indeed, R 2 |i γ (x)| dx is the abelianized area of wv w , a function defined in [START_REF] Baumslag | Isoperimetric inequalities and the homology of groups[END_REF] as a lower bound for the filling area. As in the 2-dimensional case, we can define a random closed curve S in R d which consists of a random walk and a line connecting the endpoints. Let p : R d → R 2 be the projection onto the first two coordinates; since this map is area-decreasing,

δ(S) ≥ R 2 |i p(S) (x)| dx.
The curve S can be obtained from wv w by replacing v w with a straight line. For every x ∈ Z d , let f x : D 2 → R d be a disc whose boundary consists of v x and a straight line connecting 0 and x and such that area(f for sufficiently large n, as desired.

x ) ≤ 4ℓ(v x ) 2 . If h : D 2 → R d is a disc

Extensions to bridges and other random walks

We can prove a similar result to Proposition 4.1 for the averaged Dehn function of Z 2 by extending Proposition 3.2 to the random walk bridge. To prove Proposition 3.2, it suffices to have strong approximation of the random walk bridge by a Brownian bridge, estimates of E[ j(z)], and estimates of the probability of lying near the loop; all of these results exist in the literature. Borisov [START_REF] Borisov | On the rate of convergence in the "conditional" invariance principle[END_REF] has proven a strong approximation theorem which applies to the simple random walk bridge in Z 2 , and the analogue of Werner's result for the Brownian loop is a consequence of Yor [START_REF] Yor | Loi de l'indice du lacet brownien, et distribution de Hartman-Watson[END_REF]. Note that for Brownian loop, the result is more precise since [START_REF] Yor | Loi de l'indice du lacet brownien, et distribution de Hartman-Watson[END_REF] gives an exact formula for the expected area of points with index k = 0. The case k = 0 has even been computed recently by Garban and Trujillo Ferreras [GTF06]. Finally the upper bound on the probability of being close to the Brownian loop is a consequence of the fact that the law of the Brownian loop for t ∈ [0, 1/2] or t ∈ [1/2, 1] is absolutely continuous with respect to the law of the Brownian motion. More precisely, for ǫ > 0, denote by W ′ ǫ the Wiener sausage associated to the Brownian loop. Denote by P or E the law of the Brownian motion and by P ′ the law of the Brownian loop. Now if p t (x, y) is the heat kernel, then one has

P ′ [z ∈ W ′ ǫ ] ≤ 2E
p 1/2 (0, β 1/2 ) p 1 (0, 0) 1 {z∈Wǫ} , for all ǫ > 0. Since p 1/2 (0, x) is bounded, (8) implies that

P ′ [z ∈ W ′ ǫ ]
≤ φ(z)/| ln ǫ| for some φ ∈ L 1 as desired. Thus there is a c > 0 such that δ avg (n) ≥ cn ln ln n for sufficiently large n. We suspect that neither of these lower bounds is sharp and conjecture that in fact δ avg (n) and δ rnd (n) grow like n ln n. The integral R 2 |i γ (x)| dx is the area necessary to fill γ with a chain or an arbitrary manifold with boundary, and requiring that the filling be a disc should increase the necessary area.

Extending Theorem 1.1 to more general situations seems difficult, because of the use of E, but it can be extended to walks with certain symmetries. For instance, E can be defined for the simple random walk on the triangular lattice. If z is a point in the plane and X t is the rescaled triangular random walk, let s be an edge of the triangle containing z, let ∆ + and ∆ -be opposite sides of the straight line containing s and define e i and E as before. If e ∈ E, define w(e) to be 0 if X t traverses s during e. If this does not happen, then X t goes around s in either the positive or negative direction; let w(e) = ±1/2 depending on the direction. Note that each direction is equally likely, just as in the case of the square lattice.

Then

j n (z) - e∈E w(e) ≤ 2 + g n (s) 2
where g n (s) is the number of times that X t traverses s. We can bound e∈E w(e) exactly as before, by breaking E into small, medium, and large excursions, so it remains only to bound g n (s). This is straightforward; since the random walk is n steps long, s g n (s) = n, and there is a φ ∈ L 1 such that E[g n (s)] ≤ φ(z)/n. A similar proof holds for the simple random walk on the honeycomb lattice.

Proposition 4. 1 .

 1 For every x ∈ Z d , d ≥ 2, let v x be a word of minimal length representing x -1 . Then there is a c > 0 such that the random Dehn function of Z d with respect to the v x and any random walk on Z d with i.i.d. bounded increments, E[S i -S i-1 ] = 0, and whose support generates Z d satisfies δ rnd (n) ≥ cn ln ln n for sufficiently large n. Proof. To use Proposition 3.2, we need to use the correspondence between words in Z d and curves in R d . If w = w 1 . . . w n is a word in some generating set for Z d , let w be the curve in R d connecting w 1 , w 1 w 2 , . . . , w 1 . . . w n ∈ Z d ⊂ R d by straight lines. It suffices to show that E[δ( wv w )] ≥ cn ln ln n.

  with boundary wv w , we can construct a disc with boundary S by adjoining f w to h, and soδ( wv w ) ≥ R 2 |i p(S) (x)| dx -4ℓ(v w ) 2 . Then Proposition 3.2 implies that E[δ( wv w )] ≥ cn ln ln n -4E[ℓ(v w ) 2 ] ≥ c 2 n ln ln n

Acknowledgments: We would like to thank Anna Erschler, Jean-François Le Gall, David Mason, Pierre Pansu, Christophe Pittet, Oded Schramm, and Wendelin Werner for useful discussions and suggestions.

Preliminaries and notation

We start by laying out some of the background and notation for the rest of the paper. We will recall some standard notation and describe results of Zaitsev on approximating random walks by Brownian motion and of Werner on winding numbers of Brownian motion.