epsilon symbol=ϵ, nu symbol=ν,

# Fluctuations of Transverse Increments in Two-dimensional First Passage
Percolation

Ujan Gangopadhyay  Ujan Gangopadhyay, Department of Mathematics, University of
Southern California, Los Angeles, CA, USA<EMAIL_ADDRESS>
###### Abstract.

We consider finite geodesics for first passage percolation (FPP) on
$\mathbb{Z}^{2}$ with i.i.d. continuous passage times having exponential
moments. As has been common in the literature, we assume that the FPP model
satisfies certain basic properties conjectured to be true, and derive
consequences about transverse increments of passage times from these
properties. The assumed properties are approximately as follows: (i) the
standard deviation of the passage time on scale $r$ is of some order
$\sigma(r)$, with $\left\\{\sigma(r),r>0\right\\}$ growing approximately as a
power of $r$; (ii) the tails of the passage time distributions for distance
$r$ satisfy an exponential bound on scale $\sigma(r)$, uniformly over $r$; and
(iii) the limit shape boundary has curvature uniformly bounded away from $0$
and $\infty$ in a neighborhood of some fixed direction $\theta$. By transverse
increment we mean the difference between passage times from the origin to two
points $\boldsymbol{a}$ and $\boldsymbol{b}$ which are approximately in the
direction $\theta$ from origin and the direction between $\boldsymbol{a}$ and
$\boldsymbol{b}$ is the direction of the tangent to the limit shape at the
direction $\theta$. The main consequences derived is that, if $\sigma(r)$
varies as $r^{\chi}$ for some $\chi>0$, and $\xi$ is such that $\chi=2\xi-1$,
then magnitude of the transverse increment between two points situated at
distance $r$ from each other is of the order of $r^{\chi/\xi}$.

###### Key words and phrases:

first passage percolation, increments

###### 2010 Mathematics Subject Classification:

Primary 60K35; Secondary 82B43

###### Contents

  1. 1 Introduction
    1. 1.1 Brief description of the model
    2. 1.2 Heuristics of the Main Results
    3. 1.3 Advanced Assumptions
    4. 1.4 Main Results
  2. 2 Wandering of Geodesics
  3. 3 Preliminary Upper Bound of Transverse Increments
  4. 4 Refined Upper Bound on nonrandom Fluctuations
    1. 4.1 Proof of Theorem 4.1
      1. 4.1.1 Proof of Proposition
      2. 4.1.2 Proof of Proposition
    2. 4.2 Proof of Theorem 4.2
  5. 5 Upper Bound of Transverse Increments
  6. 6 Lower Bound of Variance of Transverse Increments
    1. 6.1 Proof of Proposition
    2. 6.2 Proof of Proposition
      1. 6.2.1 Proof of Proposition
      2. 6.2.2 Proof of Proposition 6.6
    3. 6.3 Proof of Proposition
  7. 7 Long-range Correlations

##  1\. Introduction

In this paper, we investigate transverse increments and long-range
correlations in first passage percolation (FPP) on $\mathbb{Z}^{2}$. Various
models of FPP have been considered in the literature, but we will consider the
classical model, as introduced by Hammersley and Welsh (1965), which places
i.i.d. weights on the edges of the integer lattice.

###  1.1. Brief description of the model

Let $\mathtt{E}(\mathbb{Z}^{2})$ be the set of nearest-neighbor edges in
$\mathbb{Z}^{2}$. Consider a collection
$\mathbb{T}:=\left\\{\tau_{e}:e\in\mathtt{E}(\mathbb{Z}^{2})\right\\}$ of
random variables which are called _edge-weights._ We will list our assumptions
in two categories: the “basic assumptions” described below will be used
throughout the paper. Later we will describe another set of more “technical
assumptions,” which we will use more selectively.

##### Basic Assumptions:

We assume that the edge-weights are _i.i.d., non-negative, continuous, with
$\operatorname{\mathbb{E}}\exp\left(C\tau_{e}\right)<\infty$ for some $C>0$._.

The _passage time_ of a self-avoiding lattice path $\gamma$ is defined as the
sum of the edge-weights of all the edges on the path $\gamma$, i.e.,

$T(\gamma):=\sum_{\gamma\mbox{ contains }e}\tau_{e}.$

We adopt the convention that paths are a continuous curve in $\mathbb{R}^{2}$
as opposed to a sequence of lattice points or sequence of nearest-neighbor
edges. The passage time between two points $\boldsymbol{u}$ and
$\boldsymbol{v}$ in $\mathbb{Z}^{2}$ is defined as

$T(\boldsymbol{u},\boldsymbol{v}):=\inf\left\\{T(\gamma)\middle|\gamma\;\mbox{is
a path joining $\boldsymbol{u}$ and $\boldsymbol{v}$}\right\\}.$

Then $T$ is a random pseudo-metric on $\mathbb{Z}^{2}$. It was shown by
Wierman and Reh (1978), under the i.i.d. and nonnegative assumptions on the
edge-weights, that the infimum above is attained for some paths; in our case
there can be only one such path because the edge-weights are also assumed to
be continuous, this path is called the _geodesic_ between $\boldsymbol{u}$ and
$\boldsymbol{v}$ and will be denoted by
$\Gamma(\boldsymbol{u},\boldsymbol{v})$. Since the edge-weights have finite
expectation, the passage times $T(\boldsymbol{u},\boldsymbol{v})$ also have
finite expectation for all $\boldsymbol{u}$, $\boldsymbol{v}$, and hence we
can define

$h(\boldsymbol{u}):=\operatorname{\mathbb{E}}T(\boldsymbol{0},\boldsymbol{u}).$

From the triangle inequality of $T$ it follows that $h$ is sub-additive, i.e.,
for any $\boldsymbol{u},\boldsymbol{v}\in\mathbb{Z}^{2}$ we have

$h(\boldsymbol{u}+\boldsymbol{v})\leq h(\boldsymbol{u})+h(\boldsymbol{v}).$

By the subadditive ergodic theorem of Kingman (1968), we get that for any
$\boldsymbol{u}\in\mathbb{Z}^{2}$ the following limits exist almost surely and
in $L^{1}$:

$g(\boldsymbol{u}):=\lim_{n\to\infty}\frac{T(\boldsymbol{0},n\boldsymbol{u})}{n}=\lim_{n\to\infty}\frac{h(n\boldsymbol{u})}{n}=\inf_{n>0}\frac{h(n\boldsymbol{u})}{n}.$

By taking appropriate subsequences the domain of $g$ can be extended to
$\mathbb{Q}^{2}$. Then $g$ becomes a norm, and therefore, the domain of $g$
can be further extended to $\mathbb{R}^{2}$. The unit ball in $g$-norm is
called the _limit shape_ and will be denoted by

$\mathcal{B}:=\left\\{\boldsymbol{x}\in\mathbb{R}^{2}:g(\boldsymbol{x})\leq
1\right\\}.$

The shape theorem of Cox and Durrett (1981) states, under conditions milder
than our our basic assumption, that the _wet region_ at time $t$, defined as

$\mathcal{B}(t):=\left\\{\boldsymbol{x}\in\mathbb{Z}^{2}:T(\boldsymbol{0},\boldsymbol{x})\leq
t\right\\},$

approaches $\mathcal{B}$ in an appropriate sense as $t\to\infty$, and further,
$\mathcal{B}$ is compact, convex, has a nonempty interior, and has all the
symmetries of the lattice.

######  Notation 1.1.

We extend the domain of $T$ and define passage times between points in
$\mathbb{R}^{2}$ as follows. For $\boldsymbol{x}\in\mathbb{R}^{2}$ let
$\lfloor\boldsymbol{x}\rfloor$ be the down-left corner of the unit square
containing $\boldsymbol{x}$ in the standard lattice of $\mathbb{Z}^{2}$. For
$\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{2}$, let

$T(\boldsymbol{x},\boldsymbol{y}):=T(\lfloor\boldsymbol{x}\rfloor,\lfloor\boldsymbol{y}\rfloor).$

Similarly, by $\Gamma(\boldsymbol{x},\boldsymbol{y})$ we will mean the
geodesic between $\lfloor\boldsymbol{x}\rfloor$ and
$\lfloor\boldsymbol{y}\rfloor$. Also for $\boldsymbol{x}\in\mathbb{R}^{2}$ let

$h(\boldsymbol{x}):=h(\lfloor\boldsymbol{x}\rfloor).$

######  Remark 1.1.

Throughout the paper, $C,C_{0},C_{1},C_{2},\dots$ will denote constants that
depend only on the distribution of the edge-weights. We will restart numbering
of $C_{i}$s in each proof with the exception that when we break the proof of a
theorem in smaller results, we keep a continuous numbering even in the proofs
of the smaller results. Also, when we need to use a result which has been
proved before, we use “tilde-version” of the variables and parameters.

######  Remark 1.2.

Extending definition of $T$ from $\mathbb{Z}^{2}$ to $\mathbb{R}^{2}$
introduces a minor technical issue. Although $g(\boldsymbol{x})\leq
h(\boldsymbol{x})$ for all $\boldsymbol{x}\in\mathbb{Z}^{2}$, this may not be
true for $\boldsymbol{x}\in\mathbb{R}^{2}$. Instead we have
$g(\boldsymbol{x})-\Cl{n1}\leq h(\boldsymbol{x})$ for some constant
$\Cr{n1}>0$. Similarly, for $\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{2}$
we have $h(\boldsymbol{x}+\boldsymbol{y})-\Cl{n2}\leq
h(\boldsymbol{x})+h(\boldsymbol{y})$ for some constant $\Cr{n2}>0$.

###  1.2. Heuristics of the Main Results

It is common in the literature, for example in the works Newman (1995), Newman
and Piza (1995), Licea and Newman (1996), Damron and Hanson (2014), Damron and
Hanson (2017), to take as assumption specific unproved properties of the
boundary of the limit shape such as differentiability, and curvature, either
locally or globally, which eliminates the possibility of facets or corners.
These properties are believed to be valid under our assumptions, but there is
no proof yet. We will also make similar assumptions.

Suppose the boundary of the limit shape is differentiable at a direction
$\theta$, and $\theta^{t}$ is the corresponding tangential direction. By
_transverse increments_ we mean differences of the form
$T(\boldsymbol{0},\boldsymbol{x})-T(\boldsymbol{0},\boldsymbol{y})$ where
$\boldsymbol{x}$ has direction $\theta$, $\boldsymbol{x}-\boldsymbol{y}$ has
direction ${\theta^{t}}$. Heuristically we can say what the order of the
fluctuations of transverse increments should be. For this, we need the scaling
exponents $\chi$ and $\xi$.

It is believed that for FPP on Euclidean lattices of any dimension, that there
exists an exponent $\chi$, called the _‘fluctuation exponent,’_ such that
$T(\boldsymbol{0},\boldsymbol{v})-h(\boldsymbol{v})$ is of the order of
$\lvert\boldsymbol{v}\rvert^{\chi}$ ($\lvert\cdot\rvert$ is the Euclidean
norm.) Also, it is believed that there exists an exponent $\xi$, called the
_‘wandering exponent,’_ such that the geodesic
$\Gamma(\boldsymbol{0},\boldsymbol{v})$ wanders
$\lvert\boldsymbol{v}\rvert^{\xi}$ distance on average from the line joining
$\boldsymbol{0}$ and $\boldsymbol{v}$. The two exponents are related by the
equation $\chi=2\xi-1$ which has been proved by Chatterjee (2013) assuming
$\chi$ and $\xi$ exist in a certain sense. In dimension $d=2$ it is believed
that $\chi=1/3$ and $\xi=2/3$. In $d=3$ it is believed that $\chi$ is
approximately $1/4$, and in higher dimensions there does not seem to be a
consensus even among physicists about values of $\chi$ and $\xi$, see for
example Marinari et al. (2002), Le Doussal and Wiese (2005), Fogedby (2008),
Kim and Kim (2013), Alves et al. (2014). In the closely related model of last
passage percolation it has been proved that in $d=2$ with exponential or
geometric edge-weights that $\chi=1/3$ and $\xi=2/3$ in $d=2$, see Johansson
(2000a), Johansson (2000b), Balázs et al. (2006).

If one assumes the existence of these exponents in some appropriate sense,
then fluctuations of the transverse increment
$T(\boldsymbol{0},\boldsymbol{x})-T(\boldsymbol{0},\boldsymbol{y})$ should be
of the order of $\lvert\boldsymbol{x}-\boldsymbol{y}\rvert^{\chi/\xi}$. The
heuristic of this is the following. We expect that the geodesics
$\Gamma(\boldsymbol{0},\boldsymbol{x})$ and
$\Gamma(\boldsymbol{0},\boldsymbol{y})$ stay disjoint after starting from
$\boldsymbol{x}$ and $\boldsymbol{y}$ respectively for a distance of the order
of $\lvert\boldsymbol{x}-\boldsymbol{y}\rvert^{1/\xi}$. Then these two
branches should contribute approximately independently
$\lvert\boldsymbol{x}-\boldsymbol{y}\rvert^{\chi/\xi}$ to the fluctuation. The
right scale of the coalescence time as above has been proved by Basu et al.
(2019a) in the exactly solvable model of two-dimensional last passage
percolation.

Figure 1. Illustration for the heuristic of the exponent $\chi/\xi$:
directions of $\boldsymbol{x}$ and $\boldsymbol{y}$ are approximately
${\theta_{0}}$; direction of $\boldsymbol{y}-\boldsymbol{x}$ is
${\theta_{0}^{t}}$; the two geodesics $\Gamma(\boldsymbol{0},\boldsymbol{x})$
and $\Gamma(\boldsymbol{0},\boldsymbol{y})$ are expected to coalesce
approximately at distance $\lvert\boldsymbol{x}-\boldsymbol{y}\rvert^{1/\xi}$
in $-{\theta_{0}}$ direction when traced starting from $\boldsymbol{x}$ and
$\boldsymbol{y}$ respectively.

One reason for studying the fluctuations of transverse increments is the
following. In $d=2$, it is believed that the transverse increments behave like
increments of Brownian motion, that is, the increments are approximately
uncorrelated. If this is true, then the exponent for fluctuation of transverse
increments should be $1/2$ so that $\chi/\xi=1/2$. This with $\chi=2\xi-1$
would imply $\chi=1/3$ and $\xi=2/3$.

As an application of the upper bound on fluctuations of transverse increments
we get an upper bound on long-range correlations. By long-range correlation we
mean the correlation between $T(\boldsymbol{0},\boldsymbol{a})$ and
$T(\boldsymbol{0},\boldsymbol{b})$ where $\boldsymbol{a}$ and $\boldsymbol{b}$
are points approximately in the same direction from the origin and distance
between $\boldsymbol{a}$ and $\boldsymbol{b}$ is large compared to typical
wanderings of the geodesics $\Gamma(\boldsymbol{0},\boldsymbol{a})$ and
$\Gamma(\boldsymbol{0},\boldsymbol{b})$. Heuristically we can say the
following about this correlation, see figure 2. Assuming $\chi$ and $\xi$
exist, typical wandering of the geodesics
$\Gamma(\boldsymbol{0},\boldsymbol{a})$ and
$\Gamma(\boldsymbol{0},\boldsymbol{b})$ is of the order of $n^{\xi}$ where $n$
is the distance of the points $\boldsymbol{a}$, $\boldsymbol{b}$ from the
origin. Suppose the distance between $\boldsymbol{a}$ and $\boldsymbol{b}$ is
$Jn^{\xi}$ for some large $J$. Then $\Gamma(\boldsymbol{0},\boldsymbol{a})$
and $\Gamma(\boldsymbol{0},\boldsymbol{b})$ are expected to branch apart at a
distance $m$ from the origin such that the distance between the rays joining
$\boldsymbol{0}$ to $\boldsymbol{a}$ and $\boldsymbol{0}$ to $\boldsymbol{b}$
at distance $m$ from the origin is of the order of the typical wandering of
the geodesics of at distance $m$ from origin. So we have approximately
$m^{\xi}/m=Jn^{\xi}/n$. Hence $m=nJ^{-(1-\xi)^{-1}}$. Then the covariance
between $T(\boldsymbol{0},\boldsymbol{a})$ and
$T(\boldsymbol{0},\boldsymbol{b})$ is expected to be of the order of
$m^{2\chi}$. So the correlation should be of the order of
$J^{-2\chi/(1-\xi)}$.

Figure 2. Illustration for the heuristic of the exponent $2\chi/(1-\xi)$:
directions of $\boldsymbol{a}$ and $\boldsymbol{b}$ are approximately
${\theta_{0}}$; direction of $\boldsymbol{a}-\boldsymbol{b}$ is
${\theta_{0}^{t}}$; distances of $\boldsymbol{a}$ and $\boldsymbol{b}$ from
origin are approximately $n$; distance between $\boldsymbol{a}$ and
$\boldsymbol{b}$ is $2Jn^{\xi}$; the two geodesics
$\Gamma(\boldsymbol{0},\boldsymbol{a})$ and
$\Gamma(\boldsymbol{0},\boldsymbol{b})$ are expected to branch apart at
approximately distance $m$ from the origin where $m^{\xi}/m=Jn^{\xi}/n$.

###  1.3. Advanced Assumptions

Along with our basic assumptions we make the following assumptions. Similar
assumptions have been used in Alexander (2020) and Ganguly and Hegde (2020).
We assume that there exists $\sigma:(0,\infty)\to(0,\infty)$ such that the
following hold.

######  Assumption 1.1.

There exist positive constants $\Cl{A11}$, $\Cl{A12}$, $\Cl{A13}$, such that
for all $\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{2}$ with
$\lvert\boldsymbol{x}-\boldsymbol{y}\rvert\geq\Cr{A11}$, and all $t>0$, we
have

$\operatorname{\mathbb{P}}\left(|T(\boldsymbol{x},\boldsymbol{y})-h(\boldsymbol{x}-\boldsymbol{y})|\geq
t\sigma(\lvert\boldsymbol{x}-\boldsymbol{y}\rvert)\right)\leq\Cr{A12}e^{-\Cr{A13}t}.$
(A1)

######  Assumption 1.2.

There exist constants $\mathfrak{p}>0$, $\mathfrak{q}>0$, $\alpha\in(0,1)$,
$\beta\in(0,1)$, $\alpha\leq\beta$, such that for all $x>y>0$ we have

$\mathfrak{p}\left(\frac{x}{y}\right)^{\alpha}\leq\frac{\sigma(x)}{\sigma(y)}\leq\mathfrak{q}\left(\frac{x}{y}\right)^{\beta}.$
(A2)

######  Assumption 1.3.

There exist positive constants $\epsilon$, $\Cl{A3}$, such that for
$\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{2}$ with
$\lvert\boldsymbol{x}-\boldsymbol{y}\rvert\geq\Cr{A3}$, we have

$\operatorname{\mathbb{P}}\left(T(\boldsymbol{x},\boldsymbol{y})\leq
h(\boldsymbol{x}-\boldsymbol{y})-\epsilon\sigma(\lvert\boldsymbol{x}-\boldsymbol{y}\rvert)\right)\geq\epsilon,\quad\mbox{and}\quad\operatorname{\mathbb{P}}\left(T(\boldsymbol{x},\boldsymbol{y})\geq
h(\boldsymbol{x}-\boldsymbol{y})+\epsilon\sigma(\lvert\boldsymbol{x}-\boldsymbol{y}\rvert)\right)\geq\epsilon.$
(A3)

######  Remark 1.3.

By Remark 1.1 of Alexander (2020), we assume without loss of generality that
$\sigma$ is monotonically increasing and continuous.

######  Remark 1.4.

Under Assumption A1, Assumption A3 is equivalent to saying that there exist
positive constants $\Cl{remark1.41}$, $\Cl{remark1.42}$, such that for all
$\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^{2}$ with
$\lvert\boldsymbol{x}-\boldsymbol{y}\rvert\geq\Cr{remark1.41}$, we have

$\operatorname{Var}(T(\boldsymbol{x},\boldsymbol{y}))\geq\Cr{remark1.42}\sigma^{2}(\lvert\boldsymbol{x}-\boldsymbol{y}\rvert).$

######  Remark 1.5.

The assumption $\beta<1$ is natural because, from results of Kesten (1993),
the passage times are known to satisfy exponential concentration with scaling
exponent $1/2$, which shows that under any reasonable definition of $\chi$ we
must have $\chi\leq 1/2$.

######  Remark 1.6.

The assumption $\alpha>0$ is natural because, for certain definition of $\chi$
and $\xi$ it was shown by Wehr and Aizenman (1990) that
$\chi\geq(1-(d-1)\xi)/2$ in $d$-dimensions, which in two dimensions coupled
with $\chi\geq 2\xi-1$ and $\chi\leq 1/2$ yields $\chi\geq 1/8$.

######  Definition 1.1.

We say that a direction ${\theta_{0}}$ is of _type I_ if there exist constants
$C>0$, $\delta_{1}>0$, $\delta_{2}>0$ as follows. The limit shape boundary
$\partial\mathcal{B}$ is differentiable in a neighborhood
$({\theta_{0}}-\delta_{1},{\theta_{0}}+\delta_{1})$ of the direction
${\theta_{0}}$, and for $|\delta|\leq\delta_{2}$,
${\theta}\in({\theta_{0}}-\delta_{1},{\theta_{0}}+\delta_{1})$, we have

$g({\boldsymbol{e}_{{\theta}}}+\delta{\boldsymbol{e}_{{\theta^{t}}}})-g({\boldsymbol{e}_{{\theta}}})\geq
C\delta^{2}$

where ${\theta^{t}}$ is the direction of the tangent to $\partial\mathcal{B}$
at the point in direction ${\theta}$.

######  Remark 1.7.

We take the direction of the tangents in counter-clockwise direction around
the limit shape boundary.

######  Remark 1.8.

An alternative formulation of type I direction is the following: there exist
constants $C>0$, $\delta_{1}>0$ such that $\partial\mathcal{B}$ is
differentiable in the sector
$({\theta_{0}}-\delta_{1},{\theta_{0}}+\delta_{1})$, and for
${\theta}\in({\theta_{0}}-\delta_{1},{\theta_{0}}+\delta_{1})$, we have

$g({\boldsymbol{e}_{{\theta}}}+\delta{\boldsymbol{e}_{{\theta^{t}}}})-g(n{\boldsymbol{e}_{{\theta}}})\geq
C\min\left\\{|\delta|,\delta^{2}\right\\}.$

######  Definition 1.2.

We say that a direction ${\theta_{0}}$ is of _type II_ if there exist
constants $C>0$, $\delta_{1}>0$, $\delta_{2}>0$ as follows. The limit shape
boundary $\partial\mathcal{B}$ is differentiable in a neighborhood
$({\theta_{0}}-\delta_{1},{\theta_{0}}+\delta_{1})$ of the direction
${\theta_{0}}$ and for $|\delta|\leq\delta_{2}$,
${\theta}\in({\theta_{0}}-\delta_{1},{\theta_{0}}+\delta_{1})$, we have

$g({\boldsymbol{e}_{{\theta}}}+\delta{\boldsymbol{e}_{{\theta^{t}}}})-g({\boldsymbol{e}_{{\theta}}})\leq
C\delta^{2},$ (1.1)

where ${\theta^{t}}$ is the direction of the tangent to $\partial\mathcal{B}$
at the point in direction ${\theta}$.

######  Remark 1.9.

In a neighborhood of a type I direction the limit shape boundary cannot have a
facet and in a neighborhood of a type II direction the limit shape boundary
cannot have a corner.

######  Remark 1.10.

As observed in Remark 1.2 of Alexander (2020), the condition in (1.1) can be
alternatively stated as follows. If $\boldsymbol{u}_{\theta}$ is the point on
$\partial\mathcal{B}$ in direction ${\theta}$, then in a neighborhood of
$\boldsymbol{u}_{\theta}$, the boundary is sandwiched between the tangent at
$\boldsymbol{u}_{\theta}$ and a parabola tangent to $\partial\mathcal{B}$ at
$\boldsymbol{u}_{\theta}$. This implies that the direction of the tangent
grows at most linearly in a neighborhood of ${\theta}$. So, if ${\theta_{0}}$
is a direction of type II, then there exist constants $C>0$, $\delta_{1}>0$,
$\delta_{2}>0$ such that $\partial\mathcal{B}$ is differentiable in the
directions $({\theta_{0}}-\delta_{1},{\theta_{0}}+\delta_{1})$, and for
${\theta}_{1},{\theta}_{2}\in({\theta_{0}}-\delta_{1},{\theta_{0}}+\delta_{1})$
with $|{\theta}_{1}-{\theta}_{2}|\leq\delta_{2}$ we have
$|{\theta}_{1}^{t}-{\theta}_{2}^{t}|\leq C|{\theta}_{1}-{\theta}_{2}|$.

###  1.4. Main Results

######  Notation 1.2.

For any direction ${\theta}$ the unit vector in direction ${\theta}$ is
denoted by ${\boldsymbol{e}_{{\theta}}}$. Given two distinct directions
${\theta}_{1}$, ${\theta}_{2}$ define the projections
$\pi^{1}_{{\theta}_{1},{\theta}_{2}}$ and
$\pi^{2}_{{\theta}_{1},{\theta}_{2}}$ so that for any $\boldsymbol{v}$ we have

$\boldsymbol{v}=\pi^{1}_{{\theta}_{1},{\theta}_{2}}(\boldsymbol{v})\boldsymbol{e}_{{\theta}_{1}}+\pi^{2}_{{\theta}_{1},{\theta}_{2}}(\boldsymbol{v})\boldsymbol{e}_{{\theta}_{2}}.$

We will denote standard unit vectors in $\mathbb{R}^{2}$ by
$\boldsymbol{e}_{1}$ and $\boldsymbol{e}_{2}$.

######  Notation 1.3.

For $n>0$ let $\Delta(n):=\left(n\sigma(n)\right)^{1/2}$.

Our first main result is the following.

######  Theorem 1.1.

Let ${\theta_{0}}$ be a direction of both type I and II. Define for $n>0$,
$L>0$,

$\mathcal{I}(n,L):=\left\\{\boldsymbol{x}\in\mathbb{R}^{2}:\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{x})=n,\;0\leq\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{x})\leq
L\right\\}$

and

$\mathcal{D}(n,L):=\max\left\\{|T(\boldsymbol{0},\boldsymbol{x})-T(\boldsymbol{0},\boldsymbol{y})|:\boldsymbol{x},\boldsymbol{y}\in\mathcal{I}(n,L)\right\\}.$

Fix $\eta\in(0,1]$. Then, under Assumptions A1 and A2, there exist positive
constants $C_{1}$, $C_{2}$, $L_{0}$, $n_{0}$, $t_{0}$, such that for $L\geq
L_{0}$, $n\geq n_{0}$, $t\geq t_{0}$, $L\leq\Delta(n)$, we have

$\operatorname{\mathbb{P}}\left(\mathcal{D}(n,L)\geq t(\log
L)^{\eta}\sigma\left(\Delta^{-1}(L)\right)\right)\leq
C_{1}\exp\left(-C_{2}t(\log L)^{\eta}\right).$

The following theorem is our lower bound on the fluctuations of transverse
increments. We show that standard deviation of transverse increment between
two points at a distance $L$ is at least of the order of
$\sigma\left(\Delta^{-1}(L)\right)$ with a correction factor smaller than any
power of $L$.

######  Theorem 1.2.

Let ${\theta_{0}}$ be a direction of both type I and II. Fix $\nu\in(1/2,1)$.
Then, under Assumptions A1, A2, and A3, there exist positive constants
$L_{0}$, $n_{0}$, such that for $L\geq L_{0}$, $n\geq n_{0}$,
$L\leq\Delta(n)$, we have

$\operatorname{Var}\left(T(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}})-T(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}+L{\boldsymbol{e}_{{\theta_{0}^{t}}}})\right)\geq
e^{-(\log L)^{\nu}}\sigma^{2}\left(\Delta^{-1}(L)\right).$

As a corollary of Theorems 1.1 and 1.2 we get the following result. It shows
if we assume $\chi$ and $\xi$ exist in a certain sense, then $\chi/\xi$ is the
correct scaling exponent for the fluctuations of transverse increments.

######  Corollary 1.3.

Suppose there exists $\chi>0$ such that

$\lim_{x\to\infty}\frac{\log\sigma(x)}{\log x}=\chi,$

and let

$\xi:=\frac{1+\chi}{2}=\lim_{x\to\infty}\frac{\log\Delta(x)}{\log x}.$

Let ${\theta_{0}}$ be a direction of both type I and II. Then, under
Assumptions A1, A2, and A3, there exist functions $f_{1}$, $f_{2}$, $f_{3}$,
which converge to $0$ at $\infty$, and positive constants $C_{1}$, $C_{2}$,
$C_{3}$, $n_{0}$, $L_{0}$, $t_{0}$, such that for $n\geq n_{0}$, $L\geq
L_{0}$, $t\geq t_{0}$, $L\leq n^{\xi+f_{1}(n)}$, we have

$\operatorname{\mathbb{P}}\left(|T(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}})-T(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}+L{\boldsymbol{e}_{{\theta_{0}^{t}}}})|\geq
tL^{\chi/\xi+f_{2}(L)}\right)\leq C_{1}\exp\left(-C_{2}t\right),$

and

$\operatorname{Var}\left(T(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}})-T(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}+L{\boldsymbol{e}_{{\theta_{0}^{t}}}})\right)\geq
C_{3}L^{2\chi/\xi+f_{3}(L)}.$

######  _Proof:_.

Fix $\eta\in(0,1)$ and $\nu\in(1/2,1)$. Define $f_{1}$, $f_{2}$, $f_{3}$ such
that for all $x>1$,

$\displaystyle x^{\xi+f_{1}(x)}=\Delta(x),$ $\displaystyle
x^{\chi/\xi+f_{2}(x)}=\sigma(\Delta^{-1}(x))(\log x)^{\eta},$ $\displaystyle
x^{2\chi/\xi+f_{3}(x)}=e^{-(\log x)^{\nu_{0}}}\sigma^{2}(x).$

Then $f_{1}$, $f_{2}$, $f_{3}$ converge to $0$ at $\infty$ and the result
readily follows from Theorems 1.1 and 1.2. ∎

######  Notation 1.4.

Let $f(n):=\Delta(n)(\log n)^{1/2}/n$ and $f^{-1}(y):=\sup\left\\{x:f(x)\geq
y\right\\}$.

######  Remark 1.11.

Since $\beta<1$ by (A2), and because we have assumed $\sigma$ is monotonically
increasing and continuous, we get that $f$ is continuous and goes to $0$ at
$\infty$. Therefore, $f^{-1}$ is continuous, monotonically decreasing, and
converges to $0$ at $\infty$.

Now we state the result on upper bound of long-range correlations.

######  Theorem 1.4.

Let ${\theta_{0}}$ be a direction of both type I and II. Recall $\beta$ and
$\mathfrak{q}$ from (A2). Fix $\delta\in(0,(1-\beta)/2)$. Then, under
Assumptions A1 and A2, there exist positive constants $C$, $J_{0}$, $n_{0}$,
such that for $n\geq n_{0}$, $J\in[\mathfrak{q}^{1/2}J_{0},n^{\delta}]$, we
have

$\operatorname{Cov}\left(T(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}-J\Delta(n)(\log
n)^{1/2}{\boldsymbol{e}_{{\theta_{0}^{t}}}}),T(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}+J\Delta(n)(\log
n)^{1/2}{\boldsymbol{e}_{{\theta_{0}^{t}}}})\right)\\\ \leq
C\sigma^{2}\left(f^{-1}\left(\frac{J}{J_{0}}f(n)\right)\right)\log n.$

The following corollary shows how we can get the exponent $2\chi/(1-\xi)$
under further regularity assumptions on $\sigma$.

######  Corollary 1.5.

Suppose $\sigma(n)=n^{\chi}L(n)$, where $L$ is a slowly varying function. Let
$\xi:=(1+\chi)/2$. Fix $\delta_{1}\in(0,(1-\beta)/2)$. Let ${\theta_{0}}$ be a
direction of both type I and II. Then, under Assumptions A1 and A2, there
exist positive constants $C$, $J_{0}$, such that the following holds. For any
$\delta_{2}>0$ there exists $n_{0}>0$ such that for $n\geq n_{0}$ and
$J\in[\mathfrak{q}^{1/2}J_{0},n^{\delta_{1}}]$, we have

$\operatorname{Corr}\left(T(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}-J\Delta(n)(\log
n)^{1/2}{\boldsymbol{e}_{{\theta_{0}^{t}}}}),T(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}+J\Delta(n)(\log
n)^{1/2}{\boldsymbol{e}_{{\theta_{0}^{t}}}})\right)\\\ \leq
CJ^{-2\chi/(1-\xi)+\delta_{2}}\log n.$

######  _Proof:_.

From Theorem 1.4 we get positive constants $\Cl{longcor1}$, $J_{0}$, $n_{0}$,
such that for $n\geq n_{0}$, $J\in[\mathfrak{q}^{1/2}J_{0},n^{\delta_{1}}]$,
we have

$\operatorname{Cov}\left(T(\boldsymbol{0},\boldsymbol{a}),T(\boldsymbol{0},\boldsymbol{b})\right)\leq\Cr{longcor1}\sigma^{2}(m)\log
n,$ (1.2)

where $\boldsymbol{a}:=n{\boldsymbol{e}_{{\theta_{0}}}}+J\Delta(n)(\log
n)^{1/2}{\boldsymbol{e}_{{\theta_{0}^{t}}}}$,
$\boldsymbol{b}:=n{\boldsymbol{e}_{{\theta_{0}}}}-J\Delta(n)(\log
n)^{1/2}{\boldsymbol{e}_{{\theta_{0}^{t}}}}$, $m:=f^{-1}(Jf(n)/J_{0})$. Using
$J\leq n^{\delta_{1}}$, $\delta_{1}<(1-\beta)/2$, and (A2), we get
$\lvert\boldsymbol{a}\rvert\leq\Cl{longcor3}n$,
$\lvert\boldsymbol{b}\rvert\leq\Cr{longcor3}$. Hence, using (1.2) and (A2), we
get

$\operatorname{Corr}\left(T(\boldsymbol{0},\boldsymbol{a}),T(\boldsymbol{0},\boldsymbol{b})\right)\leq\C\frac{\sigma^{2}(m)}{\sigma^{2}(n)}\log
n.$ (1.3)

From $m=f^{-1}(Jf(n)/J_{0})$ we get

$J_{0}\frac{\Delta(m)(\log m)^{1/2}}{m}=J\frac{\Delta(n)(\log n)^{1/2}}{n}.$

Therefore, using $J\in[\mathfrak{q}^{1/2}J_{0},n^{\delta}_{1}]$,
$\delta_{1}<(1-\beta)/2$, and (A2), we get $m\leq n$ and $\log
m\geq\Cl{longcor2}\log n$. Fix an $\delta_{2}>0$ and let $\delta_{3}>0$ be
such that

$\frac{2\chi}{1-\xi}-\delta_{2}\leq\frac{2\chi-2\delta_{3}}{1-\xi+\delta_{3}/2}.$
(1.4)

Since $L$ is slowly-varying, by possibly increasing $n_{0}$ based on
$\delta_{2}$, we get

$\frac{L(n)}{L(m)}\geq\left(\frac{n}{m}\right)^{-\delta_{3}}.$ (1.5)

Therefore, using $\Delta(n)(\log n)^{1/2}=n^{\xi}L(n)^{1/2}(\log n)^{1/2}$ we
get

$\left(\frac{n}{m}\right)^{1-\xi}=\frac{J}{J_{0}}\left(\frac{L(n)\log
n}{L(m)\log
m}\right)^{1/2}\geq\frac{J}{J_{0}}\left(\frac{n}{m}\right)^{-\delta_{3}/2}.$

Combining this with (1.5) and (1.4), we get

$\frac{\sigma^{2}(m)}{\sigma^{2}(n)}=\left(\frac{m}{n}\right)^{2\chi}\left(\frac{L(m)}{L(n)}\right)^{2}\leq\left(\frac{m}{n}\right)^{2\chi-2\delta_{3}}\leq\left(\frac{J_{0}}{J}\right)^{\frac{2\chi-2\delta_{3}}{1-\xi+\delta_{3}/2}}\leq
J_{0}^{\frac{2\chi}{1-\xi}}J^{-\frac{2\chi}{1-\xi}+\delta_{2}}.$

Combining this with (1.3) completes the proof of Corollary 1.5. ∎

##  2\. Wandering of Geodesics

In this section, our objective is to prove some results regarding upper bounds
of wandering of geodesics. We start with a preliminary bound.

######  Notation 2.1.

For any set $A\subset\mathbb{R}^{2}$ let

$\operatorname{Diam}(A):=\sup\left\\{\lvert\boldsymbol{x}-\boldsymbol{y}\rvert:\boldsymbol{x},\boldsymbol{y}\in
A\right\\}.$

######  Lemma 2.1.

There exist positive constants $C_{1}$, $C_{2}$, $C_{3}$, such that for all
$\boldsymbol{u},\boldsymbol{v}\in\mathbb{R}^{2}$ with
$\lvert\boldsymbol{u}-\boldsymbol{v}\rvert\geq C_{1}$ we have

$\operatorname{\mathbb{P}}\left(\operatorname{Diam}(\Gamma(\boldsymbol{u},\boldsymbol{v}))\geq
C_{2}\lvert\boldsymbol{u}-\boldsymbol{v}\rvert\right)\leq
e^{-C_{3}\lvert\boldsymbol{u}-\boldsymbol{v}\rvert}.$

Since our basic assumptions include that the edge-weights have finite
exponential moments, the proof of Lemma 2.1 follows readily from Proposition
5.8 of Kesten (1993). Moreover, the conclusion of Lemma 2.1 has been shown to
hold under milder assumptions in Theorem 6.2 of Auffinger et al. (2015).

In the $g$-norm, the shortest path between two points is, of course, the line
joining them. So when a geodesic wanders transversely from the line joining
the endpoints, the extra distance covered by the geodesic in $g$-norm can be
thought of as a cost for excessive wandering. The following lemma, which is
essentially same as Lemma 2.3 of Alexander (2020), provides a lower bound for
this cost. We state it without proof.

######  Lemma 2.2.

Let ${\theta_{0}}$ be a direction of type I. Then there exist positive
constants $C$, $\delta$ such that for $n>0$, $k$, $l$, $d$, satisfying
$|l|/n\leq\delta$, we have

$g(\boldsymbol{u})+g(\boldsymbol{a}-\boldsymbol{u})-g(\boldsymbol{a})\geq
C\min\left\\{|d|,\frac{d^{2}}{n}\right\\},$

where
$\boldsymbol{a}:=n{\boldsymbol{e}_{{\theta_{0}}}}+l{\boldsymbol{e}_{{\theta_{0}^{t}}}}$
and
$\boldsymbol{u}:=k{\boldsymbol{e}_{{\theta_{0}}}}+(l\frac{k}{n}+d){\boldsymbol{e}_{{\theta_{0}^{t}}}}$.

Geodesics cannot wander too much because the cost associated with the $g$-norm
becomes difficult to be compensated by the fluctuations of passage times.
Thus, bounds on the fluctuations
$T(\boldsymbol{0},\boldsymbol{x})-g(\boldsymbol{x})$, combined with Lemma 2.2
yields upper bounds on geodesic wanderings. By Assumption A1 we know
$T(\boldsymbol{0},\boldsymbol{x})-h(\boldsymbol{x})$ satisfies exponential
concentration in the scale $\sigma(\lvert\boldsymbol{x}\rvert)$ uniformly over
$\boldsymbol{x}$. So we need a bound on the differences
$h(\boldsymbol{x})-g(\boldsymbol{x})$. These differences are known as
nonrandom fluctuations in the literature. A general method of bounding the
nonrandom fluctuations was developed in Alexander (1993, 1997). There it was
shown, using exponential concentration of
$T(\boldsymbol{0},\boldsymbol{x})-h(\boldsymbol{x})$ on the scale of
$\lvert\boldsymbol{x}\rvert^{1/2}$ from Kesten (1993), that
$h(\boldsymbol{x})-g(\boldsymbol{x})$ is at most of the order of
$\lvert\boldsymbol{x}\rvert^{1/2}\log\lvert\boldsymbol{x}\rvert$. In our case,
Alexander’s method can be used with no significant alteration to yield a bound
of the order of
$\sigma(\lvert\boldsymbol{x}\rvert)\log\lvert\boldsymbol{x}\rvert$, which we
state below. Improvements to the logarithmic bound has been made by Tessera
(2018) and Damron and Wang (2016) in related models, which we will briefly
discuss in Section 4. We will also improve the logarithmic bound to
$\sigma(\lvert\boldsymbol{x}\rvert)(\log\lvert\boldsymbol{x}\rvert)^{\eta}$
for arbitrary small $\eta>0$ in Section 4. This improvement is necessary to
prove the lower bound result Theorem 1.2. To state the bound on the nonrandom
fluctuations we use the notion of ‘general approximation property’ from
Alexander (1997).

######  Notation 2.2.

Let $\Phi$ be the set of functions from $(0,\infty)$ to $[0,\infty)$ such that
for every $\phi$ there exists some $C\geq 0$ such that $\phi(x)>0$ for $x>C$
and $\inf_{x>y>C}\phi(x)/\phi(y)>0$. For $\eta\in(0,1]$, define
$\phi_{\eta}(k)=0$ for $k\leq 1$, and for $k>1$

$\phi_{\eta}(k):=k^{-\alpha}\sigma(k)(\log k)^{\eta}.$

Also define $\widehat{\phi}(k)=0$ for $k\leq 2$, and for $k>2$

$\widehat{\phi}(k):=k^{-\alpha}\sigma(k)\log\log k.$

So $\widehat{\phi}$ and $\phi_{\eta}$ for all $\eta\in(0,1]$ belong to $\Phi$.

######  Definition 2.1.

For $\nu\geq 0$ and $\phi\in\Phi$ we say that $h$ satisfies the _general
approximation property_ with exponent $\nu$ and correction factor $\phi$ in a
sector of directions $\mathcal{S}$ if there exist positive constants $C$ and
$M$ such that for all $\boldsymbol{x}\in\mathbb{R}^{2}$ with
$\lvert\boldsymbol{x}\rvert\geq M$ and having direction in $\mathcal{S}$ we
have

$h(\boldsymbol{x})\leq
g(\boldsymbol{x})+C\lvert\boldsymbol{x}\rvert^{\nu}\phi(\lvert\boldsymbol{x}\rvert).$

When we want to specify the relevant constants, we say $h$ satisfies
$\text{GAP}(\nu,\phi,M,C)$ in sector $\mathcal{S}$.

In Alexander (1997), the class of correction factors consisted of non-
decreasing functions and the general approximation property was not restricted
to any particular set of directions. These are some minor modifications we
need in our setup. As we mentioned before, we get the following result in our
context by following Alexander’s method.

######  Proposition 2.3.

Under Assumptions A1 and A2, there exist positive constants $C$, $M$, such
that $h$ satisfies $\text{GAP}(\alpha,\phi_{1},M,C)$ in all directions, i.e.,
for all $\lvert\boldsymbol{x}\rvert\geq M$, we have

$h(\boldsymbol{x})\leq
g(\boldsymbol{x})+C\sigma(\lvert\boldsymbol{x}\rvert)\log\lvert\boldsymbol{x}\rvert.$

Let us now introduce a notation to measure wandering of geodesics.

######  Notation 2.3.

Suppose ${\theta_{0}}$ is a direction where the boundary of the limit shape is
differentiable. Let ${\theta_{0}^{t}}$ be the direction of the tangent. Let
$\mathcal{W}(\boldsymbol{u},\boldsymbol{v},k,{\theta_{0}})$ denote the maximum
wandering of the geodesic $\Gamma(\boldsymbol{u},\boldsymbol{v})$, in
$\pm{\theta_{0}^{t}}$ directions, from the line joining $\boldsymbol{u}$ and
$\boldsymbol{v}$, when the geodesic is at a distance $k$ from $\boldsymbol{u}$
in ${\theta_{0}}$ direction. We allow $k$ to be negative also. More precisely

$\mathcal{W}(\boldsymbol{u},\boldsymbol{v},k,{\theta_{0}}):=\max\left\\{\left|\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{w}-\boldsymbol{u})-k\frac{\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{v}-\boldsymbol{u})}{\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{v}-\boldsymbol{u})}\right|:\boldsymbol{w}\in\Gamma(\boldsymbol{u},\boldsymbol{v}),\;\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{w}-\boldsymbol{u})=k\right\\}.$

In the next result, we show if distance between the endpoints is approximately
$n$, then wandering at a fixed but arbitrary distance $k$ from one of the end
points is at most of the order of $\Delta(n)$ with some logarithmic correction
factors. Thus, roughly speaking, this theorem deals with global wandering of a
geodesic. The tail bound in this result is sub-optimal for $k$ bigger than a
large multiple of $n$, because in that case we get a better bound using Lemma
2.1. In Theorem 2.6 we consider local wandering of geodesics. We show that at
a distance $k$ from an endpoint the wandering is of the order of $\Delta(k)$
with some logarithmic factors. In Theorem 3 of Basu et al. (2019a) and Theorem
4.4 of Basu et al. (2019b) similar bound has been proved for geodesics in the
integrable model of last passage percolation. Although, there the results are
sharper, i.e., there are no logarithmic correction factors involved, because
in the integrable model of last passage percolation exact asymptotics of the
distribution of the passage times are known.

######  Theorem 2.4.

Let ${\theta_{0}}$ be a direction of type I. Suppose $h$ satisfies GAP with
exponent $\alpha$ and correction factor $\phi_{\eta}$ for some $\eta\in(0,1]$
in a sector $({\theta_{0}}-\delta,{\theta_{0}}+\delta)$. Then, under
Assumptions A1 and A2, there exist positive constants $C_{1}$, $C_{2}$,
$\delta_{1}$, $\delta_{2}$, $n_{0}$, $t_{0}$, such that for $n\geq n_{0}$,
$t\geq t_{0}$, $t\Delta(n)(\log n)^{\eta/2}\leq n\delta_{1}$, $|l|\leq
n\delta_{2}$, we have

$\max_{k}\operatorname{\mathbb{P}}\left(\mathcal{W}\left(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}+l{\boldsymbol{e}_{{\theta_{0}^{t}}}},k,{\theta_{0}}\right)\geq
t\Delta(n)(\log n)^{\eta/2}\right)\leq C_{1}e^{-C_{2}t^{2}(\log n)^{\eta}}.$

######  _Proof:_.

Fix $\delta_{1}>0$, $\delta_{2}>0$, to be assumed appropriately small whenever
required. Fix $n_{0}>0$, $t_{0}>0$, to be assumed appropriately large whenever
required. Consider $n$, $t$, $l$ satisfying $n\geq n_{0}$, $t\geq t_{0}$,
$t\Delta(n)(\log n)^{\eta/2}\leq n\delta_{1}$, $|l|\leq n\delta_{2}$. Let
$\boldsymbol{a}:=n{\boldsymbol{e}_{{\theta_{0}}}}+l{\boldsymbol{e}_{{\theta_{0}^{t}}}}$.
Assuming $\delta_{2}<1$ we get $\lvert\boldsymbol{a}\rvert\leq 2n$, so that,
by Lemma 2.1, the geodesic $\Gamma(\boldsymbol{0},\boldsymbol{a})$ stays
inside a square of side length $\C n$ around $\boldsymbol{0}$ with probability
at least $1-e^{-\C n}$. Using $t\Delta(n)(\log n)^{\eta/2}\leq n\delta_{1}$,
assuming $\delta_{1}$ is small enough, and using (A2), we get $t^{2}(\log
n)^{\eta}\leq\C n/\sigma(n)\leq\C n^{1-\alpha}$. Hence, the probability bound
in the statement is trivial for $|k|\geq\Cl{244}n$. So let us consider $k$
satisfying $|k|\leq\Cr{244}n$.

We split the probability under consideration as

$\operatorname{\mathbb{P}}\left(\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\geq
t\Delta(n)(\log
n)^{\eta/2}\right)\leq\operatorname{\mathbb{P}}\left(\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\geq
n\right)\\\
+\operatorname{\mathbb{P}}\left(\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\in[t\Delta(n)(\log
n)^{\eta/2},n]\right)$ (2.1)

For any point $\boldsymbol{u}$ on $\Gamma(\boldsymbol{0},\boldsymbol{a})$ we
have

$\displaystyle 0=$ $\displaystyle
T(\boldsymbol{0},\boldsymbol{u})+T(\boldsymbol{u},\boldsymbol{a})-T(\boldsymbol{0},\boldsymbol{a})$
$\displaystyle=$
$\displaystyle\left(T(\boldsymbol{0},\boldsymbol{u})-h(\boldsymbol{u})\right)+\left(T(\boldsymbol{u},\boldsymbol{a})-h(\boldsymbol{a}-\boldsymbol{u})\right)-\left(T(\boldsymbol{0},\boldsymbol{a})-h(\boldsymbol{a})\right)$
$\displaystyle+\left(h(\boldsymbol{u})-g(\boldsymbol{u})\right)+\left(h(\boldsymbol{a}-\boldsymbol{u})-g(\boldsymbol{a}-\boldsymbol{u})\right)-\left(h(\boldsymbol{a})-g(\boldsymbol{a})\right)$
$\displaystyle+\left(g(\boldsymbol{u})+g(\boldsymbol{a}-\boldsymbol{u})-g(\boldsymbol{a})\right),$

so that

$\displaystyle|T(\boldsymbol{0},\boldsymbol{u})-h(\boldsymbol{u})|+|T(\boldsymbol{u},\boldsymbol{a})-h(\boldsymbol{a}-\boldsymbol{u})|+|T(\boldsymbol{0},\boldsymbol{a})-h(\boldsymbol{a})|$
$\displaystyle\geq$
$\displaystyle\left(h(\boldsymbol{u})-g(\boldsymbol{u})\right)+\left(h(\boldsymbol{a}-\boldsymbol{u})-g(\boldsymbol{a}-\boldsymbol{u})\right)-\left(h(\boldsymbol{a})-g(\boldsymbol{a})\right)+\left(g(\boldsymbol{u})+g(\boldsymbol{a}-\boldsymbol{u})-g(\boldsymbol{a})\right)$
$\displaystyle\geq$
$\displaystyle\left(g(\boldsymbol{u})+g(\boldsymbol{a}-\boldsymbol{u})-g(\boldsymbol{a})\right)-(h(\boldsymbol{a})-g(\boldsymbol{a})).$
(2.2)

Define a set of points $V$ in the $\mathbb{R}^{2}$ as follows. If
${\theta_{0}^{t}}$ is one of the axial directions, then let $V$ be the set of
lattice points $\boldsymbol{u}$ with
$\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{u})=k$. If ${\theta_{0}^{t}}$
is not an axial direction, then let $V$ be the set of intersection points of
the integer lattice-grid with the line
$\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{u})=k$. For
$\boldsymbol{u}\in V$ let

$d(\boldsymbol{u}):=\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{u})-\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{u})\frac{l}{n}.$

Let $V_{1}$ be the set of points $\boldsymbol{u}\in V$ with
$|d(\boldsymbol{u})|\geq n$. Let $V_{2}$ be the set of points
$\boldsymbol{u}\in V$ with $t\Delta(n)(\log
n)^{\eta/2}\leq|d(\boldsymbol{u})|\leq n$. Thus, if
$\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\geq n$,
then $\Gamma(\boldsymbol{0},\boldsymbol{a})$ goes through a point
$\boldsymbol{u}\in V_{1}$. Assuming $\delta_{2}$ is small enough and using
Lemma 2.2 we get

$g(\boldsymbol{u})+g(\boldsymbol{a}-\boldsymbol{u})-g(\boldsymbol{a})\geq\Cl{245}|d(\boldsymbol{u})|.$
(2.3)

Using $h$ satisfies GAP with exponent $\alpha$ and correction factor
$\phi_{\eta}$ in a neighborhood of ${\theta_{0}}$ and assuming $\delta_{2}$ is
small enough we get

$h(\boldsymbol{a})-g(\boldsymbol{a})\leq\Cl{246}\sigma(n)(\log n)^{\eta}.$
(2.4)

Using $|d(\boldsymbol{u})|\geq n$, $|l|/n\leq\delta_{2}<1$, and
$|k|\leq\Cr{244}n$, we get

$\max\left\\{\lvert\boldsymbol{u}-\boldsymbol{a}\rvert,\lvert\boldsymbol{u}\rvert,\lvert\boldsymbol{a}\rvert\right\\}\leq\C|d(\boldsymbol{u})|.$

Therefore, using (A1) and (A2), we get for all $t^{\prime}>0$

$\operatorname{\mathbb{P}}\left(\max\left\\{|T(\boldsymbol{0},\boldsymbol{u})-h(\boldsymbol{u})|,|T(\boldsymbol{u},\boldsymbol{a})-h(\boldsymbol{a}-\boldsymbol{u})|,|T(\boldsymbol{0},\boldsymbol{a})-h(\boldsymbol{a})|\right\\}\geq
t^{\prime}\sigma(|d(\boldsymbol{u})|)\right)\leq\C e^{-\C t^{\prime}}.$

Using this with (2.2)-(2.4), and (A2), we get

$\displaystyle\operatorname{\mathbb{P}}\left(\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\geq
n\right)$ $\displaystyle\leq$ $\displaystyle\sum_{\boldsymbol{u}\in
V_{1}}\C\exp\left(-\C\left(\Cr{245}|d(\boldsymbol{u})|-\Cr{246}\sigma(n)(\log(n))^{\eta}\right)/\sigma(|d(\boldsymbol{u})|)\right)$
$\displaystyle\leq$ $\displaystyle\sum_{u\in
V_{1}}\C\exp\left(-\C|d(\boldsymbol{u})|/\sigma(|d(\boldsymbol{u})|)\right)$
$\displaystyle\leq$ $\displaystyle\C\exp\left(-\C n/\sigma(n)\right).$ (2.5)

If
$\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\in[t\Delta(n)(\log
n)^{\eta/2},n]$, then $\Gamma(\boldsymbol{0},\boldsymbol{a})$ goes through a
point $\boldsymbol{u}\in V_{2}$. Assuming $\delta_{2}$ is small enough and
using Lemma 2.2 we get

$g(\boldsymbol{u})+g(\boldsymbol{a}-\boldsymbol{u})-g(\boldsymbol{a})\geq\Cl{2416}\frac{|d(\boldsymbol{u})|^{2}}{n}\geq\Cr{2416}t^{2}\sigma(n)(\log
n)^{\eta}.$ (2.6)

Since $|d(\boldsymbol{u})|\leq n$, we have

$\max\left\\{\lvert\boldsymbol{u}-\boldsymbol{a}\rvert,\lvert\boldsymbol{u}\rvert,\lvert\boldsymbol{a}\rvert\right\\}\leq\C
n.$

Hence, using Assumptions A1 and A2 we get, for all $t^{\prime}>0$

$\operatorname{\mathbb{P}}\left(\max\left\\{|T(\boldsymbol{0},\boldsymbol{u})-h(\boldsymbol{u})|,|T(\boldsymbol{u},\boldsymbol{a})-h(\boldsymbol{a}-\boldsymbol{u})|,|T(\boldsymbol{0},\boldsymbol{a})-h(\boldsymbol{a})|\right\\}\geq
t^{\prime}\sigma(n)\right)\leq\C e^{-\C t^{\prime}}.$

Using this with (2.2), (2.4), (2.6) we get

$\displaystyle\operatorname{\mathbb{P}}\left(\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\in[t\Delta(n)(\log
n)^{1/2},n]\right)$ $\displaystyle\leq$ $\displaystyle\sum_{\boldsymbol{u}\in
V_{2}}\C\exp\left(-\C\left(\Cr{2416}\frac{|d(\boldsymbol{u})|^{2}}{n}-\Cr{246}\sigma(n)(\log
n)^{\eta}\right)/\sigma(n)\right)$ $\displaystyle\leq$
$\displaystyle\C\exp\left(-\C t^{2}(\log n)^{\eta}\right).$ (2.7)

Assuming $\delta_{1}$ is small enough and combining (2.5), (2.7), (2.1) we get

$\operatorname{\mathbb{P}}\left(\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\geq
t\Delta(n)(\log n)^{\eta/2}\right)\leq\C e^{-\C t^{2}(\log n)^{\eta}}.$

This completes the proof of Theorem 2.4. ∎

######  Corollary 2.5.

Let ${\theta_{0}}$ be a direction of type I. Then, under Assumptions A1 and
A2, there exist positive constants $C_{1}$, $C_{2}$, $\delta_{1}$,
$\delta_{2}$, $n_{0}$, $t_{0}$, such that for $n\geq n_{0}$, $t\geq t_{0}$,
$t\Delta(n)(\log n)^{1/2}\leq n\delta_{1}$, $|l|\leq n\delta_{2}$, we have

$\operatorname{\mathbb{P}}\left(\max_{k}\mathcal{W}\left(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}+l{\boldsymbol{e}_{{\theta_{0}^{t}}}},k,{\theta_{0}}\right)\geq
t\Delta(n)(\log n)^{1/2}\right)\leq C_{1}e^{-C_{2}t^{2}\log n}.$

######  _Proof:_.

Fix $\delta_{1}>0$, $\delta_{2}>0$, to be assumed appropriately small whenever
required. Fix $n_{0}>0$, $t_{0}>0$, to be assumed appropriately large whenever
required. Consider $n$, $t$, and $l$, satisfying $n\geq n_{0}$, $t\geq t_{0}$,
$t\Delta(n)(\log n)^{1/2}\leq n\delta_{1}$, $|l|\leq n\delta_{2}$. Let
$\boldsymbol{a}:=n{\boldsymbol{e}_{{\theta_{0}}}}+l{\boldsymbol{e}_{{\theta_{0}^{t}}}}$.
Assuming $\delta_{2}<1$ we get $\lvert\boldsymbol{a}\rvert\leq 2n$, so that by
Lemma 2.1, the geodesic $\Gamma(\boldsymbol{0},\boldsymbol{a})$ stays inside a
square of side length $\C n$ around $\boldsymbol{0}$ with probability at least
$1-e^{-\Cl{252}n}$. On this event
$|\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{u})|\leq\Cl{251}n$ for all
$\boldsymbol{u}$ in $\Gamma(\boldsymbol{0},\boldsymbol{a})$. Assuming
$\delta_{1}<1$ and using (A2) we get $t^{2}\log n\leq n/\sigma(n)\leq\C
n^{1-\alpha}$. Thus

$\operatorname{\mathbb{P}}\left(\max_{|k|\geq\Cr{251}n}\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\geq
t\Delta(n)(\log n)^{1/2}\right)\leq e^{-\Cr{252}n}\leq\C e^{-\C t^{2}\log n}.$
(2.8)

Using Proposition 2.3 and Theorem 2.4 and taking a union bound we get

$\operatorname{\mathbb{P}}\left(\max_{|k|\leq\Cr{251}n}\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\geq
t\Delta(n)(\log n)^{1/2}\right)\leq\C e^{-\C t^{2}\log n}.$ (2.9)

Combining (2.8) and (2.9) completes the proof. ∎

Now we show that wandering of a geodesic at a distance $k$ from an endpoint is
at most of the order of $\Delta(k)$ with some logarithmic correction factor.

######  Theorem 2.6.

Let ${\theta_{0}}$ be a direction of type I. Suppose $h$ satisfies GAP with
exponent $\alpha$ and correction factor $\phi_{\eta}$ for some $\eta\in(0,1]$
in a neighborhood of ${\theta_{0}}$. Then, under Assumptions A1 and A2, there
exist positive constants $C_{1}$, $C_{2}$, $\delta_{1}$, $\delta_{2}$,
$k_{0}$, $n_{0}$, $t_{0}$, such that for $n\geq n_{0}$, $t\geq t_{0}$, $k\geq
k_{0}$, $k<n$, $t\Delta(k)(\log k)^{\eta/2}\leq k\delta_{1}$, $|l|\leq
n\delta_{2}$, we have

$\operatorname{\mathbb{P}}\left(\mathcal{W}\left(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}+l{\boldsymbol{e}_{{\theta_{0}^{t}}}},k,{\theta_{0}}\right)\geq
t\Delta(k)(\log k)^{\eta/2}\right)\leq C_{1}e^{-C_{2}t^{2}(\log k)^{\eta}}.$

######  _Proof:_.

Fix $\delta_{1}>0$, $\delta_{2}>0$, to be assumed appropriately small whenever
required. Fix $k_{0}>0$, $n_{0}>0$, $t_{0}>0$, to be assumed appropriately
large whenever required. Consider $k$, $n$, $l$, $t$ satisfying $n\geq n_{0}$,
$t\geq t_{0}$, $k\geq k_{0}$, $t\Delta(k)(\log k)^{\eta/2}\leq k\delta_{1}$,
$|l|\leq n\delta_{2}$. Let
$\boldsymbol{a}:=n{\boldsymbol{e}_{{\theta_{0}}}}+l{\boldsymbol{e}_{{\theta_{0}^{t}}}}$.

The strategy of the proof is as follows. We will define two sequences of
points $(\boldsymbol{a}_{p})_{p=0}^{m+1}$ and
$(\boldsymbol{b}_{p})_{p=0}^{m+1}$ in such a manner that, if for all $p$, the
geodesics $\Gamma(\boldsymbol{0},\boldsymbol{a}_{p})$ and
$\Gamma(\boldsymbol{0},\boldsymbol{b}_{p})$ do not wander “excessively” then
$\mathcal{W}(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}})\leq t\Delta(k)(\log
k)^{\eta/2}$ as we require. We will define events
$\left\\{\mathcal{E}_{p}^{i}:1\leq i\leq 4,0\leq p\leq m\right\\}$ in which
these geodesics do not wander excessively. We will then show that these events
have appropriately high probability.

Fix $1<\zeta<2/(1+\beta)$ and let $\epsilon:=1-\zeta(1+\beta)/2$. Fix
$\lambda>1$, $\lambda^{\prime}>0$. Later we choose $\lambda$ so that (2.12)
holds, and we choose $\lambda^{\prime}$ based on $\lambda$ so that (2.10)
holds. Let $m\geq 0$ be such that $\lambda^{m}k<n\leq\lambda^{m+1}k$. Let
$\boldsymbol{a}_{m+1}:=\boldsymbol{a}$,
$\boldsymbol{b}_{m+1}:=\boldsymbol{a}$, and for $0\leq p\leq m$, let
$\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{a}_{p})=\lambda^{p}k$,
$\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{b}_{p})=\lambda^{p}k$,

$\displaystyle\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{a}_{p})=\frac{\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{a}_{p})}{\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{a}_{p+1})}\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{a}_{p+1})+\lambda^{\prime}t\Delta(\lambda^{\zeta
p}k)(\log\lambda^{\zeta p}k)^{\eta/2},$
$\displaystyle\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{b}_{p})=\frac{\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{b}_{p})}{\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{b}_{p+1})}\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{b}_{p+1})-\lambda^{\prime}t\Delta(\lambda^{\zeta
p}k)(\log\lambda^{\zeta p}k)^{\eta/2}.$

For any $0\leq p\leq q\leq m$, using (A2) we get

$\frac{\lambda^{-q}\Delta(\lambda^{\zeta q}k)(\log(\lambda^{\zeta
q}k))^{\eta/2}}{\lambda^{-p}\Delta(\lambda^{\zeta p}k)(\log(\lambda^{\zeta
p}k))^{\eta/2}}\leq\C\lambda^{-\epsilon(q-p)}\left(\frac{q\zeta\log\lambda+\log
k}{p\zeta\log\lambda+\log k}\right)^{\eta/2}\\\
\leq\C\lambda^{-\epsilon(q-p)}\left(1+\frac{(q-p)\zeta\log\lambda}{p\zeta\log\lambda+\log
k}\right)^{\eta/2}\leq\C\lambda^{-\epsilon(q-p)}\left(1+(q-p)\log\lambda\right)^{\eta/2}.$

Therefore, we can choose $\lambda^{\prime}$, depending on $\lambda$, such that

$\sum_{q=p}^{m}\lambda^{-(q-p)}\Delta(\lambda^{\zeta q}k)(\log(\lambda^{\zeta
q}k))^{\eta/2}\leq\frac{1}{\lambda^{\prime}}\Delta(\lambda^{\zeta
p}k)(\log(\lambda^{\zeta p}k))^{\eta/2}.$ (2.10)

Therefore, for $0\leq p\leq m$

$\displaystyle\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{a}_{p})=\lambda^{p}k\frac{l}{n}+\lambda^{\prime}t\sum_{q=p}^{m}\lambda^{-(q-p)}\Delta(\lambda^{\zeta
q}k)(\log(\lambda^{\zeta
q}k))^{\eta/2}\leq\lambda^{p}k\frac{l}{n}+t\Delta(\lambda^{\zeta
p}k)(\log(\lambda^{\zeta p}k))^{\eta/2}$
$\displaystyle\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{b}_{p})=\lambda^{p}k\frac{l}{n}-\lambda^{\prime}t\sum_{q=p}^{m}\lambda^{-(q-p)}\Delta(\lambda^{\zeta
q}k)(\log(\lambda^{\zeta
q}k))^{\eta/2}\geq\lambda^{p}k\frac{l}{n}-t\Delta(\lambda^{\zeta
p}k)(\log(\lambda^{\zeta p}k))^{\eta/2}.$

For $0\leq p\leq m$, let

$\overline{\mathcal{I}}_{p}:=\left\\{\boldsymbol{x}\in\mathbb{R}^{2}:\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{x})=\lambda^{p}k\right\\}.$

So $\boldsymbol{a}_{p}$, $\boldsymbol{b}_{p}$ are on this line. Let
$\mathcal{I}_{p}$ be the segment joining $\boldsymbol{a}_{p}$ and
$\boldsymbol{b}_{p}$. Therefore,
$\mathcal{W}(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}})\leq t\Delta(k)(\log
k)^{\eta/2}$ if and only if, whenever $\Gamma(\boldsymbol{0},\boldsymbol{a})$
intersects $\overline{\mathcal{I}}_{0}$, it intersects $\mathcal{I}_{0}$. We
will define the events $\left\\{\mathcal{E}^{i}_{p}:1\leq i\leq 4,0\leq p\leq
m\right\\}$ in a way that, if
$\mathbb{T}\in\cap_{i=1}^{4}\cap_{p=0}^{m}\mathcal{E}^{i}_{p}$ then for all
$0\leq p\leq m$, whenever $\Gamma(\boldsymbol{0},\boldsymbol{a})$ intersects
$\overline{\mathcal{I}}_{p}$, it intersects $\mathcal{I}_{p}$, see Figure 3.

Figure 3. Rough sketch for $m=2$:
$\boldsymbol{a}_{m+1}=\boldsymbol{b}_{m+1}=\boldsymbol{a}$; for $0\leq p\leq
m$ the segment joining $\boldsymbol{a}_{p}$ and $\boldsymbol{b}_{p}$ is
$\mathcal{I}_{p}$, and extending $\mathcal{I}_{p}$ we get the line
$\overline{\mathcal{I}}_{p}$; for all $0\leq p\leq m$ if the geodesics
$\Gamma(\boldsymbol{0},\boldsymbol{a}_{p})$ and
$\Gamma(\boldsymbol{0},\boldsymbol{b}_{p})$ do not wander excessively then for
all $0\leq p\leq m$ the geodesic $\Gamma(\boldsymbol{0},\boldsymbol{a})$
intersects $\mathcal{I}_{p}$ whenever it intersects
$\overline{\mathcal{I}}_{p}$.

For $0\leq p\leq m$, define the events

$\displaystyle\mathcal{E}^{1}_{p}:=\left\\{\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a}_{p+1},\lambda^{p}k,{\theta_{0}}\right)\leq\lambda^{\prime}t\Delta(\lambda^{\zeta
p}k)(\log(\lambda^{\zeta p}k))^{\eta/2}\right\\},$
$\displaystyle\mathcal{E}^{2}_{p}:=\left\\{\mathcal{W}\left(\boldsymbol{0},\boldsymbol{b}_{p+1},\lambda^{p}k,{\theta_{0}}\right)\leq\lambda^{\prime}t\Delta(\lambda^{\zeta
p}k)(\log(\lambda^{\zeta p}k))^{\eta/2}\right\\}.$

By construction of the sequences $(\boldsymbol{a}_{p})_{p=0}^{m+1}$ and
$(\boldsymbol{b}_{p})_{p=0}^{m+1}$, we get that for $0\leq p\leq m$, if
$\mathbb{T}\in\mathcal{E}_{p}^{1}\cap\mathcal{E}_{p}^{2}$, then the geodesics
$\Gamma(\boldsymbol{0},\boldsymbol{a}_{p+1})$ and
$\Gamma(\boldsymbol{0},\boldsymbol{b}_{p+1})$ intersect $\mathcal{I}_{p}$
whenever they intersect $\overline{\mathcal{I}}_{p}$. We want the geodesic
$\Gamma(\boldsymbol{0},\boldsymbol{a})$ to intersect $\mathcal{I}_{p}$
whenever it intersects $\overline{\mathcal{I}_{p}}$, for all $0\leq p\leq m$;
Figure 3 shows the ideal situation. But
$\mathbb{T}\in\cap_{p=0}^{m}(\mathcal{E}_{p}^{1}\cap\mathcal{E}_{p}^{2})$ is
not sufficient for this because the geodesics can backtrack. So we will define
the events $\mathcal{E}_{p}^{3}$ and $\mathcal{E}_{p}^{4}$ for $0\leq p\leq m$
where the geodesics do not backtrack. Define the half-line

$\mathcal{I}:=\left\\{\boldsymbol{x}:\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{x})\geq
n,\frac{\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{x})}{\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{x})}=\frac{l}{n}\right\\}.$

If in addition to
$\mathbb{T}\in\cap_{p=0}^{m}(\mathcal{E}_{p}^{1}\cap\mathcal{E}_{p}^{2})$, we
also have that for all $0\leq p\leq m$, the geodesics
$\Gamma(\boldsymbol{0},\boldsymbol{a}_{p})$ and
$\Gamma(\boldsymbol{0},\boldsymbol{b}_{p})$ do not intersect $\mathcal{I}$,
then we get that for all $0\leq p\leq m$ the geodesic
$\Gamma(\boldsymbol{0},\boldsymbol{a})$ intersects $\mathcal{I}_{p}$ whenever
it intersects $\overline{\mathcal{I}}_{p}$. Therefore we define the events
$\mathcal{E}^{3}_{p}$, $\mathcal{E}^{4}_{p}$ for $0\leq p\leq m$ as follows.
Let

$\displaystyle\mathcal{E}^{3}_{m}:=\left\\{\max_{n^{\prime}\geq
n}\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a}_{m},n^{\prime},{\theta_{0}}\right)\leq\lambda^{\prime}t\Delta(\lambda^{\zeta
m}k)(\log(\lambda^{\zeta m}k))^{\eta/2}\right\\},$
$\displaystyle\mathcal{E}^{4}_{m}:=\left\\{\max_{n^{\prime}\geq
n}\mathcal{W}\left(\boldsymbol{0},\boldsymbol{b}_{m},n^{\prime},{\theta_{0}}\right)\leq\lambda^{\prime}t\Delta(\lambda^{\zeta
m}k)(\log(\lambda^{\zeta m}k))^{\eta/2}\right\\},$

and for $0\leq p<m$ let

$\mathcal{E}^{3}_{p}:=\left\\{\text{Diam}\left(\Gamma(\boldsymbol{0},\boldsymbol{a}_{p})\right)\leq
n\right\\},\quad\mathcal{E}^{4}_{p}:=\left\\{\text{Diam}\left(\Gamma(\boldsymbol{0},\boldsymbol{b}_{p})\right)\leq
n\right\\}.$

So, for $0\leq p\leq m$, if $\mathbb{T}\in\mathcal{E}^{3}_{p}$, then
$\Gamma(\boldsymbol{0},\boldsymbol{a}_{p})$ does not intersect $\mathcal{I}$,
and if $\mathbb{T}\in\mathcal{E}^{4}_{p}$, then
$\Gamma(\boldsymbol{0},\boldsymbol{b}_{p})$ does not intersect $\mathcal{I}$.
Thus, if $\mathbb{T}\in\cap_{i=1}^{4}\cap_{p=0}^{m}\mathcal{E}_{p}^{i}$, then
for all $0\leq p\leq m$, whenever $\Gamma(\boldsymbol{0},\boldsymbol{a})$
intersects $\overline{\mathcal{I}}_{p}$ it intersects $\mathcal{I}_{p}$. In
this event
$\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\leq
t\Delta(k)(\log k)^{\eta/2}$ as required. So now we will show these events
have appropriately high probability.

We use Theorem 2.4 to bound
$\operatorname{\mathbb{P}}((\mathcal{E}^{i}_{p})^{c})$ for $0\leq p\leq m$ and
$i=1,2$. For a fixed $p$ and $i=1$ we use the following parameters.

$\tilde{\eta}:=\eta,\quad\tilde{n}:=\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{a}_{p+1}),\quad\tilde{l}:=\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{a}_{p+1}),\quad\tilde{t}:=\lambda^{\prime}t\frac{\Delta(\lambda^{\zeta
p}k)(\log(\lambda^{\zeta
p}k))^{\eta/2}}{\Delta(\tilde{n})(\log\tilde{n})^{\eta/2}}.$

We need to verify $\tilde{n}\geq\tilde{n}_{0}$, $\tilde{t}\geq\tilde{t}_{0}$,
$\tilde{t}\Delta(\tilde{n})(\log\tilde{n})^{\tilde{\eta}/2}\leq\tilde{n}\delta_{1}$,
$|\tilde{l}|\leq\tilde{n}\tilde{\delta}_{2}$. The condition
$\tilde{n}\geq\tilde{n}_{0}$ holds by taking $k_{0}$ large enough because
$\tilde{n}\geq k\geq k_{0}$. Using $\tilde{n}\leq\lambda^{p+1}k$ and (A2) we
get $\tilde{t}\geq\C t$. So $\tilde{t}\geq\tilde{t}_{0}$ holds by choosing
$t_{0}$ large enough. Using $\tilde{n}\geq\lambda^{p}k$, (A2),
$t\Delta(k)(\log k)^{\eta/2}\leq k\delta_{1}$, and assuming $\delta_{1}$ is
small enough, we get

$\frac{1}{\tilde{n}}\tilde{t}\Delta(\tilde{n})(\log\tilde{n})^{\eta/2}\leq\C\frac{1}{\lambda^{p}k}t\Delta(\lambda^{p}k)(\log\lambda^{p}k)^{\eta/2}\leq\C\frac{1}{k}t\Delta(k)(\log
k)^{\eta/2}\leq\C\delta_{1}\leq\tilde{\delta_{1}}.$

If $p=m$, then
$|\tilde{l}|/\tilde{n}=|l|/n\leq\delta_{2}\leq\tilde{\delta}_{2}$. For $p<m$,
using $t\Delta(k)(\log k)^{\eta/2}\leq k\delta_{1}$, $|l|\leq n\delta_{2}$,
(A2), and assuming $\delta_{1}$, $\delta_{2}$ are small enough, we get

$\displaystyle\frac{|\tilde{l}|}{\tilde{n}}=\frac{|\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{a}_{p+1})|}{\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{a}_{p+1})}$
$\displaystyle\leq\frac{1}{\lambda^{p+1}k}\left(\lambda^{p+1}k\frac{|l|}{n}+t\Delta(\lambda^{\zeta(p+1)}k)(\log(\lambda^{\zeta(p+1)}k))^{\eta/2}\right)$
$\displaystyle\leq\delta_{2}+\delta_{1}\frac{\Delta(\lambda^{\zeta(p+1)}k)(\log(\lambda^{\zeta(p+1)}k))^{\eta/2}}{\lambda^{p}\Delta(k)(\log
k)^{\eta/2}}$
$\displaystyle\leq\delta_{2}+\C\delta_{1}\lambda^{-\epsilon(p+1)}\left(1+\frac{(p+1)\zeta\log\lambda}{\log
k}\right)^{\eta/2}$
$\displaystyle\leq\delta_{2}+\C\delta_{1}\leq\tilde{\delta_{2}}.$

So the conditions for applying Theorem 2.4 hold. Using
$\tilde{n}\leq\lambda^{p+1}k$ and (A2) we get

$\tilde{t}^{2}(\log\tilde{n})^{\eta}\geq\C t^{2}\lambda^{p\epsilon}(\log
k)^{\eta}.$

Therefore, applying Theorem 2.4 we get

$\operatorname{\mathbb{P}}((\mathcal{E}^{1}_{p})^{c})\leq\C\exp\left(-\C
t^{2}\lambda^{p\epsilon}(\log k)^{\eta}\right).$ (2.11)

Similar bounds hold for $\mathcal{E}^{2}_{p}$ for $0\leq p\leq m$,
$\mathcal{E}^{3}_{m}$, $\mathcal{E}^{4}_{m}$. For $0\leq p<m$,
$\lvert\boldsymbol{a}_{p}\rvert\leq 2\lambda^{p}k$. We have $n>\lambda^{m}k$.
Thus, assuming $\lambda$ large enough, we get for $i=3,4$ and $0\leq p<m$,
using Lemma 2.1,

$\operatorname{\mathbb{P}}((\mathcal{E}^{i}_{p})^{c})\leq\C\exp\left(-\C\lambda^{p}k\right).$
(2.12)

Combining (2.11) and (2.12) we get

$\operatorname{\mathbb{P}}\left(\mathcal{W}\left(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}}\right)\geq
t\Delta(k)(\log
k)^{\eta/2}\right)\leq\operatorname{\mathbb{P}}\left(\cup_{i=1}^{4}\cup_{p=0}^{m}(\mathcal{E}^{i}_{p})^{c}\right)\leq\C
e^{-\C t^{2}(\log k)^{\eta}}.$

This completes proof of Theorem 2.6. ∎

As a corollary we can deal with wandering of a geodesic within a fixed
distance from an endpoint.

######  Corollary 2.7.

Let ${\theta_{0}}$ be a direction of type I. Then, under Assumptions A1 and
A2, there exist positive constants $C_{1}$, $C_{2}$, $\delta_{1}$,
$\delta_{2}$, $k_{0}$, $n_{0}$, $t_{0}$, such that for $k\geq k_{0}$, $n\geq
n_{0}$, $t\geq t_{0}$, $t\Delta(k)(\log k)^{1/2}\leq k\delta_{1}$, $|l|\leq
n\delta_{2}$, we have

$\operatorname{\mathbb{P}}\left(\max_{k^{\prime}\leq
k}\mathcal{W}\left(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}+l{\boldsymbol{e}_{{\theta_{0}^{t}}}},k^{\prime},{\theta_{0}}\right)\geq
t\Delta(k)(\log k)^{1/2}\right)\leq C_{1}e^{-C_{2}t^{2}\log k}.$

######  _Proof:_.

Fix $\delta_{1}>0$, $\delta_{2}>0$, to be assumed appropriately small whenever
required. Fix $k_{0}>0$, $n_{0}>0$, $t_{0}>0$, to be assumed large enough
whenever required. Let
$\boldsymbol{a}:=n{\boldsymbol{e}_{{\theta_{0}}}}+l{\boldsymbol{e}_{{\theta_{0}^{t}}}}$.
Define

$L:=\left\\{\boldsymbol{v}\in\mathbb{R}^{2}:\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{v})=k,|\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{v})-k\frac{l}{n}|\leq\frac{t}{2}\Delta(k)(\log
k)^{1/2}\right\\}.$

If $\max_{k^{\prime}\leq
k}\mathcal{W}(\boldsymbol{0},\boldsymbol{a},k^{\prime},{\theta_{0}})\geq
t\Delta(k)(\log k)^{1/2}$, then either
$\mathcal{W}(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}})\geq(t/2)\Delta(k)(\log
k)^{1/2}$, or $\Gamma(\boldsymbol{0},\boldsymbol{a})$ passes through some
$\boldsymbol{v}\in L$ and
$\max_{k^{\prime}}\mathcal{W}\left(\boldsymbol{0},\boldsymbol{v},k^{\prime},{\theta_{0}^{t}}\right)\geq(t/2)\Delta(k)(\log
k)^{1/2}$. In the first case, by Theorem 2.6 and Proposition 2.3, we get

$\operatorname{\mathbb{P}}\left(\mathcal{W}(\boldsymbol{0},\boldsymbol{a},k,{\theta_{0}})\geq\frac{t}{2}\Delta(k)(\log
k)^{1/2}\right)\leq C_{1}e^{-C_{2}t^{2}\log k}.$ (2.13)

For the second case, consider $\boldsymbol{v}\in L$. We will apply Corollary
2.5 with $\tilde{{\theta_{0}}}={\theta_{0}}$, $\tilde{n}=k$,
$\tilde{l}=\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{v})$,
$\tilde{t}=t$. Then

$\frac{|\tilde{l}|}{\tilde{n}}\leq\frac{|l|}{n}+\frac{1}{k}\frac{t}{2}\Delta(k)(\log
k)^{1/2}\leq\delta_{1}+\frac{\delta_{2}}{2}.$

Also

$\frac{1}{\tilde{n}}\tilde{t}\Delta(\tilde{n})(\log\tilde{n})^{1/2}\leq\frac{1}{k}t\Delta(k)(\log
k)^{1/2}\leq\delta_{2}.$

Therefore, assuming $\delta_{1}$, $\delta_{2}$ are small enough, we get

$\operatorname{\mathbb{P}}\left(\max_{k^{\prime}\in[0,k]}\mathcal{W}\left(\boldsymbol{0},\boldsymbol{v},k^{\prime},{\theta_{0}}\right)\geq\frac{t}{2}\Delta(k)(\log
k)^{1/2}\right)\leq C_{3}e^{-C_{4}t^{2}\log k}.$

Taking a union bound over $2t\Delta(k)(\log k)^{1/2}$ many choices of
$\boldsymbol{v}$ we get

$\operatorname{\mathbb{P}}\left(\max_{k^{\prime}}\mathcal{W}\left(\boldsymbol{0},n{\boldsymbol{e}_{{\theta_{0}}}}+l{\boldsymbol{e}_{{\theta_{0}^{t}}}},k^{\prime},{\theta_{0}}\right)\geq
t\Delta(k)(\log k)^{1/2}\right)\leq C_{5}e^{-C_{6}t^{2}\log k}.$ (2.14)

Combining (2.13), (2.14) completes the proof of Corollary 2.7. ∎

######  Remark 2.1.

Recall from Notation 1.1 that geodesic between points $\boldsymbol{u}$,
$\boldsymbol{v}$ which are not necessarily lattice points is defined as the
geodesic between $\lfloor\boldsymbol{u}\rfloor$ and
$\lfloor\boldsymbol{v}\rfloor$. In Theorem 2.4, Corollary 2.5, Theorem 2.6,
and Corollary 2.7, we are dealing with geodesics having one endpoint
$\boldsymbol{0}$ and we are measuring the wandering at a distance from
$\boldsymbol{0}$. Later while applying these results we may have a point of
$\mathbb{R}^{2}$ in place of $\boldsymbol{0}$. This does not cause any major
complication, i.e., bounds that hold for wandering of
$\Gamma(\boldsymbol{0},\boldsymbol{u})$ also hold for wandering of
$\Gamma(\boldsymbol{v},\boldsymbol{u}+\boldsymbol{v})$, where $\boldsymbol{u}$
and $\boldsymbol{v}$ are not necessarily lattice points.

##  3\. Preliminary Upper Bound of Transverse Increments

In this section, our objective is to prove a weaker version of Theorem 1.1.
This weaker version will be used to improve the bound on nonrandom
fluctuations in Theorem 4.2. This improved bound on nonrandom fluctuations is
necessary for the proof of Theorem 1.1. To prove the weaker version of Theorem
1.1 we need the following result on curvature of the boundary of the limit
shape. We skip the proof as the result is essentially same as Lemma 2.7 of
Alexander (2020).

######  Lemma 3.1.

Let ${\theta_{0}}$ be a direction of type II. Then there exist positive
constants $C$, $\delta_{1}$, $\delta_{2}$, such that for $d$, $k>0$, $L$,
satisfying $|d|\leq k\delta_{1}$, $|L|\leq k\delta_{2}$, we have

$|g(k{\boldsymbol{e}_{{\theta_{0}}}}+(d+L){\boldsymbol{e}_{{\theta_{0}^{t}}}})-g(k{\boldsymbol{e}_{{\theta_{0}}}}+d{\boldsymbol{e}_{{\theta_{0}^{t}}}})|\leq
C\left(\frac{L^{2}}{k}+\frac{|d||L|}{k}\right).$

The preliminary upper bound of transverse increments is the following.

######  Theorem 3.2.

Let ${\theta_{0}}$ be a direction of both type I and II. For $n>0$, $L>0$, let
$\mathcal{I}(n,L)$ and $\mathcal{D}(n,L)$ be as defined in Theorem 1.1. Then,
under Assumptions A1 and A2, there exist positive constants $C_{1}$, $C_{2}$,
$L_{0}$, $n_{0}$, $t_{0}$, such that for $L\geq L_{0}$, $n\geq n_{0}$, $t\geq
t_{0}$, $L\leq\Delta(n)$, we have

$\operatorname{\mathbb{P}}\left(\mathcal{D}(n,L)\geq t\log
L\sigma(\Delta^{-1}(L))\right)\leq C_{1}e^{-C_{2}t\log L}.$

######  _Proof:_.

Let us assume without loss of generality that ${\theta_{0}}\in[0,\pi/4]$. Fix
$L_{0}>0$, $n_{0}>0$, $t_{0}>0$. We will assume $L_{0}$, $n_{0}$, $t_{0}$ are
large whenever required. Consider $L\geq L_{0}$, $n\geq n_{0}$, $t\geq t_{0}$,
$L\leq\Delta(n)$. Based on the values of $t$ we consider two cases because for
suitably large values of $t$ we are in a large deviation regime and the proof
is straightforward.

##### Case I:

Suppose $t\geq 4\mu L(\sigma(\Delta^{-1}(L))\log L)^{-1}$, where $\mu$ is the
expected passage edge-weight. Since $\mathcal{I}(n,L)$ has width $L$, the
lattice points corresponding to the points in $\mathcal{I}(n,L)$ can be joined
by a lattice path of at most $\lceil 2L\rceil$ edges. Hence
$\mathcal{D}(n,L)\leq X_{1}+\cdots+X_{\lceil 2L\rceil}$, where $X_{i}$’s are
i.i.d. random variables which have the same distribution as that of the edge-
weights. Therefore,

$\operatorname{\mathbb{P}}\left(\mathcal{D}(n,L)\geq t\log
L\sigma(\Delta^{-1}(L))\right)\leq\operatorname{\mathbb{P}}\left(X_{1}+\cdots+X_{\lceil
2L\rceil}\geq t\log L\sigma(\Delta^{-1}(L))\right)\\\ \leq\C\exp\left(-\C
t\log L\sigma(\Delta^{-1}(L))\right)\leq\C\exp\left(-\C t\log L\right).$

##### Case II:

Suppose

$t\leq 4\mu L(\sigma(\Delta^{-1}(L))\log L)^{-1}.$ (3.1)

Let

$\mathcal{I}^{\ast}:=\left\\{\boldsymbol{x}\in\mathbb{R}^{2}:\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{x})=n-\Delta^{-1}(L),\right.\\\
\left.\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{x})\in\left[-t^{1/2}L(\log\Delta^{-1}(L))^{1/2},\left(1-\frac{\Delta^{-1}(L)}{n}\right)L+t^{1/2}L\left(\log\Delta^{-1}(L)\right)^{1/2}\right]\vphantom{\boldsymbol{x}\in\mathbb{R}^{2}}\right\\}.$
(3.2)

Define the event

$\mathcal{E}:\mbox{$\Gamma(\boldsymbol{0},\boldsymbol{u})$ intersects
$\mathcal{I}^{\ast}$ for all $\boldsymbol{u}\in\mathcal{I}(n,L)$}.$

If $\mathbb{T}\not\in\mathcal{E}$, then for some
$\boldsymbol{u}\in\mathcal{I}(n,L)$ the geodesic
$\Gamma(\boldsymbol{0},\boldsymbol{u})$ wanders more than
$t^{1/2}L(\log\Delta^{-1}(L))^{1/2}$ in $\pm{\theta_{0}^{t}}$ directions when
it is at a distance $\Delta^{-1}(L)$ from $\boldsymbol{u}$ in direction
$-{\theta_{0}}$, i.e.,
$\mathcal{W}\left(\boldsymbol{u},\boldsymbol{0},\Delta^{-1}(L),-{\theta_{0}}\right)\geq
t^{1/2}L(\log\Delta^{-1}(L))^{1/2}$. Consider an
$\boldsymbol{u}\in\mathcal{I}(n,L)$. We will apply Theorem 2.6 with the
variables

$\tilde{k}:=\Delta^{-1}(L),\;\tilde{l}:=\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{u}),\;\tilde{n}:=\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{u})=n,\;\tilde{t}:=t^{1/2},\;\tilde{{\theta_{0}}}:=-{\theta_{0}},\;\tilde{\eta}:=1.$

The point $\boldsymbol{u}$ is not necessarily a lattice point, but this issue
has been addressed in Remark 2.1. The conditions on $\tilde{{\theta_{0}}}$
hold because by assumption ${\theta_{0}}$ is of type I, and by Proposition 2.3
$h$ satisfies GAP with correction factor $\phi_{1}$ in all directions. So we
need to verify the conditions $\tilde{k}\geq\tilde{k_{0}}$,
$\tilde{n}\geq\tilde{n_{0}}$, $\tilde{t}\geq\tilde{t_{0}}$,
$\tilde{t}\Delta(\tilde{k})(\log\tilde{k})^{1/2}\leq\tilde{k}\tilde{\delta_{1}}$,
$|\tilde{l}|\leq\tilde{n}\tilde{\delta_{2}}$. Assuming $n_{0}$, $L_{0}$,
$t_{0}$ are large enough we get $\tilde{k}\geq\tilde{k_{0}}$,
$\tilde{n}\geq\tilde{n_{0}}$, $\tilde{t}\geq\tilde{t_{0}}$. From
$\boldsymbol{u}\in\mathcal{I}(n,L)$ we get
$|\pi^{2}_{\theta_{0},\theta_{0}^{t}}(u)|\leq L$. Therefore, using
$L\leq\Delta(n)$, (A2), and assuming $n_{0}$ is large enough, we get

$\frac{|\tilde{l}|}{\tilde{n}}\leq\frac{L}{n}\leq\frac{\Delta(n)}{n}\leq
n_{0}^{-(1-\beta)/2}\leq\tilde{\delta_{2}}.$

Using (3.1), (A2), and assuming $L_{0}$ is large enough, we get

$\displaystyle\frac{1}{\tilde{k}}\tilde{t}\Delta(\tilde{k})(\log\tilde{k})^{1/2}=\frac{t^{1/2}L\left(\log\Delta^{-1}(L)\right)^{1/2}}{\Delta^{-1}(L)}$
$\displaystyle\leq\C\frac{L^{3/2}(\log\Delta^{-1}(L))^{1/2}}{\Delta^{-1}(L)(\sigma(\Delta^{-1}(L))^{1/2}(\log
L)^{1/2}}$ $\displaystyle\leq\C\frac{L^{1/2}}{(\Delta^{-1}(L))^{1/2}}\leq\C
L^{-\frac{(1-\beta)}{2(1+\beta)}}\leq\C
L_{0}^{-\frac{(1-\beta)}{2(1+\beta)}}\leq\tilde{\delta_{1}}.$

Therefore, all the conditions for applying Theorem 2.6 are satisfied, and we
get

$\operatorname{\mathbb{P}}\left(\mathcal{W}\left(\boldsymbol{u},\boldsymbol{0},\Delta^{-1}(L),-{\theta_{0}}\right)\geq
t^{1/2}L(\log\Delta^{-1}(L))^{1/2}\right)\leq\C e^{-\C t\log L}.$

Therefore, taking a union bound over all $\boldsymbol{u}\in\mathcal{I}(n,L)$
we get

$\operatorname{\mathbb{P}}\left(\mathcal{E}^{c}\right)\leq\C e^{-\C t\log L}.$
(3.3)

So in order to complete the proof we consider $\mathbb{T}\in\mathcal{E}$.

Figure 4. Illustration for Theorem 3.2 under case II: distance of
$\mathcal{I}(n,L)$ from $\boldsymbol{0}$ in ${\theta_{0}}$ direction is $n$,
width of $\mathcal{I}(n,L)$ in ${\theta_{0}^{t}}$ direction is $L$, distance
of $\mathcal{I}^{\ast}$ from $\boldsymbol{0}$ is $n-\Delta^{-1}L$, if
$\mathbb{T}\in\mathcal{E}$ then geodesics from $\boldsymbol{0}$ to points in
$\mathcal{I}(n,L)$ passes through $\mathcal{I}^{\ast}$.

Consider two points $\boldsymbol{u}$ and $\boldsymbol{v}$ on
$\mathcal{I}(n,L)$. Since $\mathbb{T}\in\mathcal{E}$, there exist points
$\boldsymbol{y}$ and $\boldsymbol{z}$ on $\mathcal{I}^{\ast}$ such that the
geodesic $\Gamma(\boldsymbol{0},\boldsymbol{u})$ passes through
$\boldsymbol{y}$ and the geodesic $\Gamma(\boldsymbol{0},\boldsymbol{v})$
passes through $\boldsymbol{z}$. Then

$T(\boldsymbol{0},\boldsymbol{u})-T(\boldsymbol{0},\boldsymbol{v})\leq(T(\boldsymbol{0},\boldsymbol{z})+T(\boldsymbol{z},\boldsymbol{u}))-(T(\boldsymbol{0},\boldsymbol{z})+T(\boldsymbol{z},\boldsymbol{v}))=T(\boldsymbol{z},\boldsymbol{u})-T(\boldsymbol{z},\boldsymbol{v}).$

Similarly, we get the opposite inequality with $\boldsymbol{y}$ in place of
$\boldsymbol{z}$. Therefore,

$|T(\boldsymbol{0},\boldsymbol{u})-T(\boldsymbol{0},\boldsymbol{v})|\leq\max_{\boldsymbol{x}\in\mathcal{I}^{\ast}}|T(\boldsymbol{x},\boldsymbol{u})-T(\boldsymbol{x},\boldsymbol{v})|.$
(3.4)

Fix an $\boldsymbol{x}\in\mathcal{I}^{\ast}$. Then

$|T(\boldsymbol{x},\boldsymbol{u})-T(\boldsymbol{x},\boldsymbol{v})|\leq|T(\boldsymbol{x},\boldsymbol{u})-h(\boldsymbol{u}-\boldsymbol{x})|+|T(\boldsymbol{x},\boldsymbol{v})-h(\boldsymbol{v}-\boldsymbol{x})|\\\
+|h(\boldsymbol{u}-\boldsymbol{x})-g(\boldsymbol{v}-\boldsymbol{x})|+|h(\boldsymbol{v}-\boldsymbol{x})-g(\boldsymbol{v}-\boldsymbol{x})|+|g(\boldsymbol{u}-\boldsymbol{x})-g(\boldsymbol{v}-\boldsymbol{x})|.$
(3.5)

Since $\boldsymbol{u}$, $\boldsymbol{v}$ are in $\mathcal{I}(n,L)$, we have

$\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{u}-\boldsymbol{v})\leq L.$
(3.6)

From (3.2) we get

$\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{u}-\boldsymbol{x})=\Delta^{-1}(L),$
(3.7)

and

$|\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{u}-\boldsymbol{x})|\leq\C
t^{1/2}L(\log\Delta^{-1}(L))^{1/2}.$ (3.8)

Combining (3.6), (3.7), (3.1) we get

$\lvert\boldsymbol{u}-\boldsymbol{x}\rvert\leq\C\Delta^{-1}(L).$ (3.9)

Hence, by Proposition 2.3, and using $\log L$ and $\log\Delta^{-1}(L)$ are of
the same order, we get

$|h(\boldsymbol{u}-\boldsymbol{x})-g(\boldsymbol{u}-\boldsymbol{x})|\leq\C\sigma(\Delta^{-1}(L))\log
L.$ (3.10)

Similarly, (3.7)-(3.10) hold for $\boldsymbol{u}$ replaced with
$\boldsymbol{v}$. By Lemma 3.1 and using (3.6), (3.7), (3.8), we get

$|g(\boldsymbol{u}-\boldsymbol{x})-g(\boldsymbol{v}-\boldsymbol{x})|\leq\C
t^{1/2}\frac{L^{2}}{\Delta^{-1}(L)}\log\Delta^{-1}(L)\leq\C
t^{1/2}\sigma(\Delta^{-1}(L))\log L.$ (3.11)

Using (3.10) and the same for $\boldsymbol{u}$ replaced with $\boldsymbol{v}$,
(3.11), and (3.5), we get

$\operatorname{\mathbb{P}}\left(|T(\boldsymbol{x},\boldsymbol{u})-T(\boldsymbol{x},\boldsymbol{v})|\geq
t\sigma(\Delta^{-1}(L))\log
L\right)\leq\operatorname{\mathbb{P}}\left(|T(\boldsymbol{x},\boldsymbol{u})-h(\boldsymbol{u}-\boldsymbol{x})|\geq\Cl{321}t\sigma(\Delta^{-1}(L))\log
L\right)\\\
+\operatorname{\mathbb{P}}\left(|T(\boldsymbol{x},\boldsymbol{v})-h(\boldsymbol{v}-\boldsymbol{x})|\geq\Cr{321}t\sigma(\Delta^{-1}(L))\log
L\right).$

Therefore, using (3.9) and the same for $\boldsymbol{u}$ replaced by
$\boldsymbol{v}$, and using (A1) we get

$\operatorname{\mathbb{P}}\left(|T(\boldsymbol{x},\boldsymbol{u})-T(\boldsymbol{x},\boldsymbol{v})|\geq
t\sigma(\Delta^{-1}(L))\log L\right)\leq\C e^{-\C t\log L}.$ (3.12)

The number of choices of lattice points corresponding to $\boldsymbol{x}$,
$\boldsymbol{u}$, $\boldsymbol{v}$ is $\C tL^{3}(\log L)^{1/2}$. Using (3.4),
(3.12), and a union bound, we get

$\operatorname{\mathbb{P}}\left(\mathcal{D}(n,L)\geq
t\sigma(\Delta^{-1}(L))\log L,\;\mathbb{T}\in\mathcal{E}\right)\leq\C e^{-\C
t\log L}.$

This concludes the proof because we already found in (3.3) that
$\mathcal{E}^{c}$ has appropriately small probability. ∎

We shall need the following variation of the last result. In the last result
we took a direction ${\theta_{0}}$ of both type I and type II and considered
transverse increment over a segment with one endpoint having direction
${\theta_{0}}$. In the next result, we look at transverse increment over a
segment whose endpoints have direction in a neighborhood of ${\theta_{0}}$ but
may not have direction exactly ${\theta_{0}}$.

######  Corollary 3.3.

Let ${\theta_{0}}$ be a direction of both type I and II. For $n>0$, $L>0$,
$d$, let

$\mathcal{I}(n,L,d):=\left\\{\boldsymbol{x}\in\mathbb{R}^{2}:\pi^{1}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{x})=n,\;d\leq\pi^{2}_{\theta_{0},\theta_{0}^{t}}(\boldsymbol{x})\leq
d+L\right\\},$

and

$\mathcal{D}(n,L,d):=\max\left\\{|T(\boldsymbol{0},\boldsymbol{x})-T(\boldsymbol{0},\boldsymbol{y})|:\boldsymbol{x},\boldsymbol{y}\in\mathcal{I}(n,L,d)\right\\}.$

Then, under Assumptions A1 and A2, there exist positive constants
$\delta_{1}$, $\delta_{2}$ $C_{1}$, $C_{2}$, $C_{3}$, $L_{0}$, $n_{0}$,
$t_{0}$ such that for $L\geq L_{0}$, $n\geq n_{0}$, $t\geq t_{0}$, $|d|\leq
n\delta_{1}$, $L\leq\delta_{2}\Delta(n)$, we have

$\operatorname{\mathbb{P}}\left(\mathcal{D}(n,L,d)\geq
C_{3}L\frac{|d|}{n}+t\sigma(\Delta^{-1}(L))\log L\right)\leq
C_{1}e^{-C_{2}t\log L}.$

######  _Proof:_.

Fix $\delta_{1}>0$, $\delta_{2}>0$, to be assumed appropriately small whenever
required. Fix $n_{0}>0$, $L_{0}>0$, $t_{0}>0$, to be assumed appropriately
large whenever required. Consider $n$, $L$, $t$, $d$ such that $L\geq L_{0}$,
$n\geq n_{0}$, $|d|\leq n\delta_{1}$, $L\leq\delta_{2}\Delta(n)$. Let
$\boldsymbol{u}:=n{\boldsymbol{e}_{{\theta_{0}}}}+d{\boldsymbol{e}_{{\theta_{0}^{t}}}}$,
$\boldsymbol{v}:=n{\boldsymbol{e}_{{\theta_{0}}}}+(d+L){\boldsymbol{e}_{{\theta_{0}^{t}}}}$.
Let ${\theta}_{1}$, ${\theta}_{2}$ be the directions of $\boldsymbol{u}$ and
$\boldsymbol{v}$ respectively. Let $\boldsymbol{w}$ be the projection of
$\boldsymbol{u}$ on the line joining $\boldsymbol{0}$ and $\boldsymbol{v}$ in
direction ${\theta}_{1}^{t}$ which exists assuming $\delta_{1}$ is small
enough. Let $\mathcal{I}^{\ast}$ be segment joining $\boldsymbol{u}$ and
$\boldsymbol{w}$.

Figure 5. Illustration for Corollary 3.3. The segment joining $\boldsymbol{u}$
and $\boldsymbol{v}$ is $\mathcal{I}(n,L,d)$. The segment joining
$\boldsymbol{u}$ and $\boldsymbol{w}$ is $\mathcal{I}^{\ast}$.

Let

$\mathcal{D}^{\ast}:=\max\left\\{|T(\boldsymbol{0},\boldsymbol{x})-T(\boldsymbol{0},\boldsymbol{y})|:\boldsymbol{x},\boldsymbol{y}\in\mathcal{I}^{\ast}\right\\}.$

Let $|\mathcal{I}^{\ast}|$ be the length of $\mathcal{I}^{\ast}$. To bound
$\mathcal{D}^{\ast}$ we will use Theorem 3.2 with the following variables

$\tilde{{\theta_{0}}}={\theta}_{1},\quad\tilde{n}:=\lvert\boldsymbol{u}\rvert,\quad\tilde{L}:=|\mathcal{I}^{\ast}|,\quad\tilde{t}=\frac{t}{2},\quad\tilde{\eta}=1.$

Since ${\theta_{0}}$ is of both type I and type II, assuming $\delta_{1}$ is
small enough, we get all possible values of ${\theta}_{1}$ are uniformly of
both type I and type II i.e., they satisfy the curvature conditions with same
constants. Thus the condition on ${\theta}_{1}$ for applying Theorem 3.2
holds. Assuming $\delta_{1}$ and $\delta_{2}$ are small enough, we get $\C
L\leq|\mathcal{I}^{\ast}|\leq\Cl{logupinc1}L$, $\C n\leq\tilde{n}\leq\C n$.
Therefore, $\tilde{L}\geq\tilde{L_{0}}$, $\tilde{n}\geq\tilde{n_{0}}$ hold
assuming $L_{0}$ and $n_{0}$ are large enough. Also from
$L\leq\delta_{2}\Delta(n)$ we get $\tilde{L}\leq\Delta(\tilde{n})$. Hence all
the conditions for applying Theorem 3.2 hold and we get

$\operatorname{\mathbb{P}}\left(\mathcal{D}^{\ast}\geq\frac{t}{2}\sigma(\Delta^{-1}(L))\log
L\right)\leq\C e^{-\C t\log L}.$ (3.13)

Now let us consider the difference $|\mathcal{D}^{\ast}-\mathcal{D}(n,L,d)|$.
Considering the triangle with vertices $\boldsymbol{u}$, $\boldsymbol{v}$,
$\boldsymbol{w}$, we get

$\lvert\boldsymbol{v}-\boldsymbol{w}\rvert=L\frac{|\sin({\theta}_{1}^{t}-{\theta_{0}^{t}})|}{|\sin({\theta}_{1}^{t}-{\theta}_{2})|}.$
(3.14)

Assuming $\delta_{1}$ and $\delta_{2}$ are small enough, we get

$|\sin({\theta}_{1}^{t}-{\theta}_{2})|\geq\C|\sin({\theta_{0}^{t}}-{\theta_{0}})|,$
(3.15)

and

$|\sin({\theta^{t}}-{\theta_{0}^{t}})|\leq\C|{\theta}_{1}^{t}-{\theta_{0}^{t}}|\leq\C|{\theta}_{1}-{\theta_{0}}|\\\
\leq\C|\sin({\theta}_{1}-{\theta_{0}})|\leq\C\frac{|d|}{n}|\sin({\theta_{0}^{t}}-{\theta})|\leq\C\frac{|d|}{n}|\sin({\theta_{0}^{t}}-{\theta_{0}})|,$
(3.16)

where the second inequality holds by Remark 1.10. Combining (3.14)-(3.16) we
get

$\lvert\boldsymbol{v}-\boldsymbol{w}\rvert\leq\Cl{curvup1}L\frac{|d|}{n}.$

Therefore, if $\boldsymbol{x}$ is a point on $\mathcal{I}(n,L,d)$ and
$\boldsymbol{y}$ is its projection on $\mathcal{I}^{\ast}$ in direction
${\theta}_{2}$, then $\lvert\boldsymbol{x}-\boldsymbol{y}\rvert\leq\C L|d|/n$.
Since $h$ is subadditive and therefore sublinear, we get
$h(\boldsymbol{x}-\boldsymbol{y})\leq\Cl{317}L|d|/n$. Assuming $\delta_{1}<1$,
taking $L_{0}$ large enough, and using (A2), we get
$|d|/n\leq\delta_{1}<1\leq\Delta^{-1}(L)/L$, so that
$L|d|/n\leq\Delta^{-1}(L)$. Therefore, using (A1) we get for all
$t^{\prime}>0$

$\operatorname{\mathbb{P}}\left(T(\boldsymbol{x},\boldsymbol{y})\geq\Cr{317}L\frac{|d|}{n}+t^{\prime}\sigma(\Delta^{-1}(L))\right)\leq\C
e^{-\C t^{\prime}}.$

Using $|\mathcal{I}^{\ast}|\leq\Cr{logupinc1}L$, $|\mathcal{I}(n,L,d)|=L$, and
using a union bound, we get

$\operatorname{\mathbb{P}}\left(|\mathcal{D}^{\ast}-\mathcal{D}(n,L)|\geq\Cr{317}L\frac{|d|}{n}+t^{\prime}\sigma(\Delta^{-1}(L))\right)\leq\C
L^{2}\exp\left(-\C t^{\prime}\right).$

Therefore taking $t^{\prime}=(t/2)\log L$ and assuming $t_{0}$ and $L_{0}$ are
large enough we get

$\operatorname{\mathbb{P}}\left(|\mathcal{D}^{\ast}-\mathcal{D}(n,L)|\geq\Cr{317}L\frac{|d|}{n}+\frac{t}{2}\sigma(\Delta^{-1}(L))\log
L\right)\leq\C\exp\left(-\C t\log L\right).$ (3.17)

Combining (3.13) and (3.17) completes the proof. ∎

##  4\. Refined Upper Bound on nonrandom Fluctuations

In the previous section, we proved a preliminary upper bound of fluctuations
of transverse increments. To prove the more refined bound of Theorem 1.1, we
need to improve the correction factor in Proposition 2.3 from $\log$ to small
power of $\log$. Related results are known in the literature, for example,
Tessera (2018) has shown that $(\log x)^{1/2}$ is a valid correction factor in
FPP on Cayley Graphs on integer lattices, and Damron and Wang (2016) have
shown in a spherically symmetric model of FPP that any iterate of $\log$ is a
valid correction factor. In Section 2 we briefly discussed the method from
Alexander (1997), we will now discuss it in more detail.

######  Notation 4.1.

Let $\mathcal{S}_{0}$ be the set of directions where the boundary of
$\mathcal{B}$ is differentiable. Consider $\boldsymbol{x}$ with direction in
$\mathcal{S}_{0}$. Let $H_{\boldsymbol{x}}$ be the tangent to $\partial
g(\boldsymbol{x})\mathcal{B}$ at $\boldsymbol{x}$. Let
$H_{\boldsymbol{x}}^{0}$ be the line through $\boldsymbol{0}$ parallel to
$H_{\boldsymbol{x}}$. Let $g_{\boldsymbol{x}}$ be the unique linear functional
on $\mathbb{R}^{2}$ satisfying $g_{\boldsymbol{x}}(\boldsymbol{y})=0$ for all
$y\in H_{\boldsymbol{x}}^{0}$, and
$g_{\boldsymbol{x}}(\boldsymbol{x})=g(\boldsymbol{x})$. Recall $\Phi$ from
Notation 2.2. Define for $\phi\in\Phi$, $\nu\geq 0$, $C>0$, $K>0$,

$Q_{\boldsymbol{x}}(\nu,\phi,C,K):=\left\\{\boldsymbol{y}\in\mathbb{Z}^{2}:\lvert\boldsymbol{y}\rvert\leq
K\lvert\boldsymbol{x}\rvert,g_{\boldsymbol{x}}(\boldsymbol{y})\leq
g(\boldsymbol{x}),h(\boldsymbol{y})\leq
g_{\boldsymbol{x}}(\boldsymbol{y})+C\lvert\boldsymbol{x}\rvert^{\nu}\phi\left(\lvert\boldsymbol{x}\rvert\right)\right\\}.$

######  Definition 4.1.

We say that $h$ satisfies the convex hull approximation property (CHAP) with
exponent $\nu\geq 0$ and correction factor $\phi\in\Phi$ in a set of
directions $\mathcal{S}\subset\mathcal{S}_{0}$, if there exist constants
$M>0$, $C>0$, $K>0$, $a>1$ such that
$x/\alpha\in\textsf{Co}(Q_{\boldsymbol{x}}(\nu,\phi,C,K))$ for some
$\alpha\in[1,a]$, for all $\boldsymbol{x}\in\mathbb{Q}^{2}$ with
$\lvert\boldsymbol{x}\rvert\geq M$ and direction of $\boldsymbol{x}$ in
$\mathcal{S}$, where Co denotes the convex hull. When we want to specify the
specific constants, we say $h$ satisfies $\text{CHAP}(\nu,\phi,M,C,K,a)$ in
sector $\mathcal{S}$.

In our terminology, the procedure in Alexander (1997) is as follows. There the
objective is to prove GAP with exponent $\alpha$ and correction factor
$\phi_{1}$. To achieve this, first, it is shown that CHAP with exponent
$\alpha$ and correction factor $\phi_{1}$ holds. Since $h$ is sublinear, GAP
with exponent $1$ and correction factor $\phi_{1}$ holds trivially. Then the
exponent of GAP is reduced from $1$ to $\alpha$ iteratively using CHAP. Here
we are not concerned about the exponent $\alpha$. We want to change the
correction factor of GAP from $\phi_{1}$ to $\phi_{\eta}$ for small $\eta>0$
while keeping the exponent $\alpha$ fixed. We will prove this in two steps. In
the first step, we will prove that CHAP holds with exponent $\alpha$ and
correction factor $\widehat{\phi}$. From Proposition 2.3 we get $h$ satisfies
GAP with exponent $\alpha$ and correction factor $\phi_{1}$. Using this, we
will reduce the correction factor of GAP from $\phi_{1}$ to $\phi_{\eta}$,
which will be the second step. The result about CHAP with exponent $\alpha$
and correction factor $\widehat{\phi}$ is the following.

######  Theorem 4.1.

Let ${\theta_{0}}$ be a direction of both type I and type II. Then, under
Assumptions A1 and A2, there exists $\delta>0$ such that CHAP holds for $h$
with exponent $\alpha$ and correction factor $\widehat{\phi}$ in the sector
$({\theta_{0}}-\delta,{\theta_{0}}+\delta)$.

After carrying out the second step we get the refined upper bound on the
nonrandom fluctuations stated below.

######  Theorem 4.2.

Let ${\theta_{0}}$ be a direction of both type I and type II. Fix
$\eta\in(0,1]$. Then, under Assumptions A1 and A2, there exist constants
$C>0$, $M>0$, $\delta>0$ such that for all $\lvert\boldsymbol{x}\rvert\geq M$
with direction of $\boldsymbol{x}$ in
$({\theta_{0}}-\delta,{\theta_{0}}+\delta)$, we have

$h(\boldsymbol{x})\leq
g(\boldsymbol{x})+C\sigma(\lvert\boldsymbol{x}\rvert)(\log\lvert\boldsymbol{x}\rvert)^{\eta},$

i.e., $\text{GAP}(\alpha,\phi_{\eta},C,M)$ holds in the sector
$({\theta_{0}}-\delta,{\theta_{0}}+\delta)$.

In the first subsection below we prove Theorem 4.1, then in the second
subsection we prove Theorem 4.2 using Theorem 4.1.

###  4.1. Proof of Theorem 4.1

First, we fix $\delta>0$ which will be used throughout the proof of Theorem
4.1. Since ${\theta_{0}}$ is of both type I and II, we can choose $\delta>0$
such that $\partial\mathcal{B}$ is differentiable in
$({\theta_{0}}-2\delta,{\theta_{0}}+2\delta)$ and there exists $\delta_{1}>0$
such that for all ${\theta}\in({\theta_{0}}-2\delta,{\theta_{0}}+2\delta)$ and
$|\delta_{2}|\leq\delta_{1}$

$\C\delta_{2}^{2}\leq
g({\boldsymbol{e}_{{\theta}}}+\delta_{2}{\boldsymbol{e}_{{\theta^{t}}}})-g({\boldsymbol{e}_{{\theta}}})\leq\C\delta_{2}^{2}.$
(4.1)

So all ${\theta}\in({\theta_{0}}-\delta,{\theta_{0}}+\delta)$ are of both type
I and type II with same constants. This allows us to use results which hold in
type I or type II directions with same constants for all
${\theta}\in({\theta_{0}}-\delta,{\theta_{0}}+\delta)$.

We extract a sufficient condition from Alexander (1997) for the Theorem 4.1 to
hold. We state the condition as Proposition 4.3. Since it is essentially
proved in Alexander (1997), we will not prove it here. To state the condition
we need the concept of skeletons of paths defined below.

##### Construction of fine skeletons:

For $\boldsymbol{x}\in\mathbb{R}^{2}$, $n>0$, $\lambda>0$, $K>0$, the fine
$Q_{\boldsymbol{x}}(\alpha,\widehat{\phi},\lambda,K)$-skeleton of a self-
avoiding path $\gamma$ from $\boldsymbol{0}$ to $n\boldsymbol{x}$ is the
sequence of marked points $\boldsymbol{v}_{0},\dots,\boldsymbol{v}_{m}$ on
$\gamma$ constructed as follows. Let $\boldsymbol{v}_{0}:=\boldsymbol{0}$, and
given $\boldsymbol{v}_{i}$, let $\boldsymbol{v}^{\prime}_{i+1}$ be the first
point (if any) in $\gamma$ such that
$\boldsymbol{v}^{\prime}_{i+1}-\boldsymbol{v}_{i}\not\in
Q_{\boldsymbol{x}}(\alpha,\widehat{\phi},\lambda,K)$; then let
$\boldsymbol{v}_{i+1}$ be the last lattice point in $\gamma$ before
$\boldsymbol{v}^{\prime}_{i+1}$ if $\boldsymbol{v}^{\prime}_{i+1}$ exists;
otherwise let $\boldsymbol{v}_{i+1}=\lfloor n\boldsymbol{x}\rfloor$ and end
the construction.

######  Proposition 4.3.

Consider an infinite sequence of i.i.d. copies of the passage-time
configuration $(\hat{T}^{i})_{i=0}^{\infty}$ on the lattice. If for some
positive constants $\lambda_{1}$, $\lambda_{2}$, $\lambda_{3}$, we have

$\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}\left[h(\boldsymbol{v}_{i}-\boldsymbol{v}_{i+1})-\hat{T}^{i}(\boldsymbol{v}_{i},\boldsymbol{v}_{i+1})\right]\geq\frac{\lambda_{1}}{16}m\sigma(\lvert\boldsymbol{x}\rvert)\log\log\lvert\boldsymbol{x}\rvert\right.\\\
\left.\text{for some $m\geq 1$ and some
$Q_{\boldsymbol{x}}(\alpha,\widehat{\phi},\lambda_{1},5)$-skeleton
$(\boldsymbol{v}_{j})_{j=0}^{m}$ of a
path}\vphantom{\sum_{i=0}^{m-1}}\right)\leq
e^{-\lambda_{2}\log\log\lvert\boldsymbol{x}\rvert}$ (4.2)

for all $\boldsymbol{x}$ with $\lvert\boldsymbol{x}\rvert\geq\lambda_{3}$ and
direction of $\boldsymbol{x}\in({\theta_{0}}-\delta,{\theta_{0}}+\delta)$,
then $h$ satisfies $\text{CHAP}(\alpha,\widehat{\phi},M,\lambda_{1},4,2)$ for
some $M$ in the sector $({\theta_{0}}-\delta,{\theta_{0}}+\delta)$.

In order to verify (4.2) we need the concept of ‘coarse skeletons.’

##### Construction of coarse skeletons:

Consider $\boldsymbol{x}\in\mathbb{R}^{2}$ with direction
${\theta}\in({\theta_{0}}-\delta,{\theta_{0}}+\delta)$. Let

$\displaystyle\ell_{\boldsymbol{x}}:=\lvert\boldsymbol{x}\rvert(\log\lvert\boldsymbol{x}\rvert)^{-2/\alpha},$
$\displaystyle
B_{ij}:=\left\\{\boldsymbol{y}\in\mathbb{R}^{2}:\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y})\in[i\ell_{\boldsymbol{x}},(i+1)\ell_{\boldsymbol{x}}),\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})\in[j\Delta(\ell_{\boldsymbol{x}}),(j+1)\Delta(\ell_{\boldsymbol{x}}))\right\\},$
(4.3)

where $i,j\in\mathbb{Z}$, and, $\alpha$ is defined in Assumption A2. So
$B_{ij}$ is a parallelogram with side lengths $\ell_{\boldsymbol{x}}$ and
$\Delta(\ell_{\boldsymbol{x}})$, and these parallelograms cover the whole
plane. Given $\boldsymbol{v}\in B_{ij}$, let

$F_{\boldsymbol{x}}(\boldsymbol{v}):=\lfloor
i\ell_{\boldsymbol{x}}{\boldsymbol{e}_{{\theta}}}+j\Delta(\ell_{\boldsymbol{x}}){\boldsymbol{e}_{{\theta^{t}}}}\rfloor,\quad
G_{\boldsymbol{x}}(\boldsymbol{v}):=\lfloor(i+1)\ell_{\boldsymbol{x}}{\boldsymbol{e}_{{\theta}}}+j\Delta(\ell_{\boldsymbol{x}}){\boldsymbol{e}_{{\theta^{t}}}}\rfloor.$

So, $F_{\boldsymbol{x}}(\boldsymbol{v})$ is the lattice point corresponding to
down-left corner of the parallelogram $B_{ij}$ containing $\boldsymbol{v}$ and
$G_{\boldsymbol{x}}(\boldsymbol{v})$ is the down-right corner, see Figure 6.
Suppose $(\boldsymbol{v}_{i})_{i=0}^{m}$ is a fine
$Q_{\boldsymbol{x}}(\alpha,\widehat{\phi},\lambda,5)$-skeleton of some path
for some $\lambda>0$. Then its coarse skeleton
$(\boldsymbol{w}_{j})_{j=0}^{2m}$ is defined as follows. For $0\leq i\leq
m-1$, let $\boldsymbol{w}_{2i}:=F_{\boldsymbol{x}}(\boldsymbol{v}_{i})$ and
$\boldsymbol{w}_{2i+1}:=G_{\boldsymbol{x}}(\boldsymbol{v}_{i+1})$.

Figure 6. Construction of coarse skeletons: for every pair of consecutive
points $\boldsymbol{v}$, $\boldsymbol{v}^{\prime}$ in a fine skeleton of a
path, we have $F_{\boldsymbol{x}}(\boldsymbol{v})$ and
$G_{\boldsymbol{x}}(\boldsymbol{v}^{\prime})$ as consecutive points in the
coarse skeleton of the path.

######  Remark 4.1.

If $(\boldsymbol{v}_{i})_{i=0}^{m}$ is a fine
$Q_{\boldsymbol{x}}(\alpha,\widehat{\phi},\lambda,5)$ skeleton of some path
and $(\boldsymbol{w}_{j})_{j=0}^{2m}$ the corresponding coarse skeleton, then
$\lvert\boldsymbol{v}_{i}-\boldsymbol{v}_{i+1}\rvert\leq
5\lvert\boldsymbol{x}\rvert$ and
$\lvert\boldsymbol{w}_{2i-1}-\boldsymbol{w}_{2i}\rvert\leq
6\lvert\boldsymbol{x}\rvert$ for large enough $\lvert\boldsymbol{x}\rvert$.

We will state two propositions which, when combined, establishes (4.2). We
need to define few constants first. Let $\Cl{1}$, $\Cl{2}$, $\Cl{0}$ be
positive constants such that for all $|\boldsymbol{u}-\boldsymbol{v}|\leq
6\lvert\boldsymbol{x}\rvert$

$\operatorname{\mathbb{P}}\left(|T(\boldsymbol{u},\boldsymbol{v})-h(\boldsymbol{u}-\boldsymbol{v})|\geq
t\sigma(\lvert\boldsymbol{x}\rvert)\right)\leq\Cr{1}e^{-\Cr{2}t},$ (4.4)

and

$\Cr{0}:=256\alpha^{-1}(1+\Cr{1})/\Cr{2}.$ (4.5)

For any $\boldsymbol{x}$ let us use the shorthand notation

$Q_{\boldsymbol{x}}:=Q_{\boldsymbol{x}}(\alpha,\widehat{\phi},\Cr{0},5).$

######  Proposition 4.4.

Under the assumptions of Theorem 4.1, there exist positive constants $\Cl{3}$,
$\Cl{4}$ such that for $\boldsymbol{x}$ with direction in
$({\theta_{0}}-\delta,{\theta_{0}}+\delta)$ and
$\lvert\boldsymbol{x}\rvert\geq\Cr{3}$, and for all $m\geq 1$, we have

$\displaystyle\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}\left[h(\boldsymbol{w}_{2i}-\boldsymbol{w}_{2i+1})-\hat{T}^{i}(\boldsymbol{w}_{2i},\boldsymbol{w}_{2i+1})\right]>\frac{\Cr{0}}{32}m\sigma\left(\lvert\boldsymbol{x}\rvert\right)\log\log\lvert\boldsymbol{x}\rvert\right.$
$\displaystyle\left.\quad\text{for some coarse $Q_{\boldsymbol{x}}$-skeleton
$(\boldsymbol{w}_{j})_{j=0}^{2m}$ of a
path}\vphantom{\sum_{i=0}^{m-1}}\right)$ $\displaystyle\leq$
$\displaystyle\exp\left(-m\Cr{4}\log\log\lvert\boldsymbol{x}\rvert\right).$

######  Proposition 4.5.

Under assumptions of Theorem 4.1, there exist positive constants $\Cl{5}$,
$\Cl{6}$ such that for $\boldsymbol{x}$ with direction in
$({\theta_{0}}-\delta,{\theta_{0}}+\delta)$ and
$\lvert\boldsymbol{x}\rvert\geq\Cr{5}$, and for all $m\geq 1$, we have

$\displaystyle\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}\left[h(\boldsymbol{v}_{i}-\boldsymbol{v}_{i+1})-\hat{T}^{i}(\boldsymbol{v}_{i},\boldsymbol{v}_{i+1})-h(\boldsymbol{w}_{2i}-\boldsymbol{w}_{2i+1})+\hat{T}^{i}(\boldsymbol{w}_{2i},\boldsymbol{w}_{2i+1})\right]\geq\frac{\Cr{0}}{32}m\sigma(\lvert\boldsymbol{x}\rvert)\log\log\lvert\boldsymbol{x}\rvert\right.$
$\displaystyle\left.\quad\text{for some fine $Q_{\boldsymbol{x}}$-skeleton
$(\boldsymbol{v}_{j})_{j=0}^{m}$ and corresponding coarse skeleton
$(\boldsymbol{w}_{j})_{j=0}^{2m}$}\vphantom{\sum_{i=0}^{m-1}}\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(-m\Cr{6}\log\log\lvert\boldsymbol{x}\rvert\right).$

So (4.2) holds by Propositions 4.5 and 4.4. Hence, to complete the proof of
Theorem 4.1, we only need to prove these two propositions. We need the
following lemma first.

######  Lemma 4.6.

Under assumptions of Theorem 4.1, there exist positive constants $\Cl{61}$,
$\Cl{7}$ such that for $\boldsymbol{x}$ with direction in
$({\theta_{0}}-\delta,{\theta_{0}}+\delta)$ and
$\lvert\boldsymbol{x}\rvert\geq\Cr{61}$ we have the following.

  1. (i)

For all $\boldsymbol{y}\in Q_{\boldsymbol{x}}$,
$|\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})|\leq\Cr{7}\Delta(\lvert\boldsymbol{x}\rvert)(\log\log\lvert\boldsymbol{x}\rvert)^{1/2}$,
where ${\theta}$ is the direction of $\boldsymbol{x}$.

  2. (ii)

The number of coarse $Q_{\boldsymbol{x}}$-skeletons of length $2m+1$ is at
most $(\log\lvert\boldsymbol{x}\rvert)^{4m/\alpha}$, where $\alpha$ is defined
in (A2).

######  _Proof:_.

Fix $\boldsymbol{x}$ with direction ${\theta}$ in
$({\theta_{0}}-\delta,{\theta_{0}}+\delta)$. We will assume that
$\lvert\boldsymbol{x}\rvert$ is large enough whenever required.

  1. (i)

Consider $\boldsymbol{y}\in Q_{\boldsymbol{x}}$. Then

$g(\boldsymbol{y})\leq h(\boldsymbol{y})\leq
g_{\boldsymbol{x}}(\boldsymbol{y})+\Cr{0}\sigma(\lvert\boldsymbol{x}\rvert)\log\log\lvert\boldsymbol{x}\rvert,$

so

$g(\boldsymbol{y})-g_{\boldsymbol{x}}(\boldsymbol{y})\leq\Cr{0}\sigma(\lvert\boldsymbol{x}\rvert)\log\log\lvert\boldsymbol{x}\rvert.$
(4.6)

Consider three cases.

Case I: Suppose $\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y})>0$ and
$|\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})|\leq\delta_{1}\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y})$,
where $\delta_{1}$ is defined in (4.1). From (4.1) we get

$g(\boldsymbol{y})-g_{\boldsymbol{x}}(\boldsymbol{y})=g(\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y}){\boldsymbol{e}_{{\theta}}}+\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y}){\boldsymbol{e}_{{\theta^{t}}}})-g(\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y}){\boldsymbol{e}_{{\theta}}})\geq\C\frac{\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})^{2}}{\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y})}.$
(4.7)

Since $\boldsymbol{y}\in Q_{\boldsymbol{x}}$, we have

$\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y})\leq\C\lvert\boldsymbol{y}\rvert\leq\C\lvert\boldsymbol{x}\rvert.$

This with (4.7) and (4.6) implies

$|\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})|\leq\C\Delta(\lvert\boldsymbol{x}\rvert)(\log\log\lvert\boldsymbol{x}\rvert)^{1/2}.$

Case II: Now suppose $\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y})>0$ and
$|\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})|\geq\delta_{1}\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y})$.
Let us consider $\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})>0$, the case
$\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})<0$ is similar. Using convexity of
$g$ and (4.1) we get

$\displaystyle g(\boldsymbol{y})-g_{\boldsymbol{x}}(\boldsymbol{y})$
$\displaystyle=$ $\displaystyle
g(\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y}){\boldsymbol{e}_{{\theta}}}+\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y}){\boldsymbol{e}_{{\theta^{t}}}})-g(\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y}){\boldsymbol{e}_{{\theta}}})$
$\displaystyle\geq$
$\displaystyle\frac{g(\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y}){\boldsymbol{e}_{{\theta}}}+\delta_{1}\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y}){\boldsymbol{e}_{{\theta^{t}}}})-g(\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y}){\boldsymbol{e}_{{\theta}}})}{\delta_{1}\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y})/\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})}$
$\displaystyle=$
$\displaystyle\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})\delta_{1}^{-1}(g({\boldsymbol{e}_{{\theta}}}+\delta_{1}{\boldsymbol{e}_{{\theta^{t}}}})-g({\boldsymbol{e}_{{\theta}}}))$
$\displaystyle\geq$
$\displaystyle\C\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y}).$

Hence using (4.6) and (A2) we get

$\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})\leq\C\sigma(\lvert\boldsymbol{x}\rvert)\log\log\lvert\boldsymbol{x}\rvert\leq\C\Delta(\lvert\boldsymbol{x}\rvert)(\log\log\lvert\boldsymbol{x}\rvert)^{1/2}.$

Case III: Suppose $\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y})<0$. Then
$g_{\boldsymbol{x}}(\boldsymbol{y})<0$. Using $\boldsymbol{y}\in
Q_{\boldsymbol{x}}$, (4.6), and (A2) we get

$\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})\leq\C\lvert\boldsymbol{y}\rvert\leq\C
g(\boldsymbol{y})\leq\C\sigma(\lvert\boldsymbol{x}\rvert)\log\log\lvert\boldsymbol{x}\rvert\leq\C\Delta(\lvert\boldsymbol{x}\rvert)(\log\log\lvert\boldsymbol{x}\rvert)^{1/2}.$

  2. (ii)

Given any $\boldsymbol{v}$ let $Q_{\boldsymbol{x}}(\boldsymbol{v})$ denote the
translate of $Q_{\boldsymbol{x}}$ by $\boldsymbol{v}$. Suppose part of a
coarse skeleton is given as $(\boldsymbol{w}_{0},\dots,\boldsymbol{w}_{2i})$.
We will find an upper bound on number of possibilities of
$(\boldsymbol{w}_{2i+1},\boldsymbol{w}_{2i+2})$. Consider a fine skeleton
$(\boldsymbol{v}_{0},\dots,\boldsymbol{v}_{i})$ corresponding to
$(\boldsymbol{w}_{0},\dots,\boldsymbol{w}_{2i})$. Since
$(\boldsymbol{w}_{2i-1},\boldsymbol{w}_{2i})$ is fixed, all choices of
$\boldsymbol{v}_{i}$ lie in the same $B_{i_{0}j_{0}}$. Consider the union of
$Q_{\boldsymbol{x}}(\boldsymbol{v})$ over all $\boldsymbol{v}\in
B_{i_{0}j_{0}}$. Each $Q_{\boldsymbol{x}}(\boldsymbol{v})$ is contained in a
parallelogram of length $\C\lvert\boldsymbol{x}\rvert$ in ${\theta}$ direction
and length
$\C\Delta(\lvert\boldsymbol{x}\rvert)(\log\log\lvert\boldsymbol{x}\rvert)^{1/2}$
in ${\theta^{t}}$ direction. Hence the union of all such
$Q_{\boldsymbol{x}}(\boldsymbol{v})$ as $\boldsymbol{v}$ varies in a
parallelogram $B_{i_{0}j_{0}}$ is contained in a parallelogram of length
$\C\lvert\boldsymbol{x}\rvert$ in ${\theta}$ direction and length
$\C\Delta(\lvert\boldsymbol{x}\rvert)(\log\log\lvert\boldsymbol{x}\rvert)^{1/2}$
in ${\theta^{t}}$ direction (using (i)). From (4.3) we have

$\frac{\Delta(\lvert\boldsymbol{x}\rvert)(\log\log\lvert\boldsymbol{x}\rvert)^{1/2}}{\Delta(\ell_{\boldsymbol{x}})}\leq\C(\log\lvert\boldsymbol{x}\rvert)^{(1+\beta)/\alpha}(\log\log\lvert\boldsymbol{x}\rvert)^{1/2},$

and,

$\frac{\lvert\boldsymbol{x}\rvert}{\ell_{\boldsymbol{x}}}=(\log\lvert\boldsymbol{x}\rvert)^{2/\alpha}.$

Using $\beta<1$, the number of parallelograms $B_{ij}$ that cover the
aforementioned union is at most $(\log\lvert\boldsymbol{x}\rvert)^{4/\alpha}$.
Hence number of choices of $(\boldsymbol{w}_{2i+1},\boldsymbol{w}_{2i+2})$ is
at most $(\log\lvert\boldsymbol{x}\rvert)^{4/\alpha}$. Iterating this from
$i=0$ to $m$, we get the result.

∎

####  4.1.1. Proof of Proposition 4.4

Fix $\boldsymbol{x}$ with direction
$\theta\in({\theta_{0}}-\delta,{\theta_{0}}+\delta)$. We will assume
$\lvert\boldsymbol{x}\rvert$ is large whenever required. Fix a coarse
$Q_{\boldsymbol{x}}$-skeleton $(\boldsymbol{w}_{j})_{j=0}^{2m}$ for some
$m\geq 1$. By Remark 4.1 and (4.4) we get

$\operatorname{\mathbb{P}}\left(h(\boldsymbol{w}_{2i}-\boldsymbol{w}_{2i+1})-\hat{T}^{i}(\boldsymbol{w}_{2i},\boldsymbol{w}_{2i+1})\geq
t\sigma\lvert\boldsymbol{x}\rvert\right)\leq\Cr{1}e^{-\Cr{2}t}.$

For $\Cl{sp}:=\Cr{2}/(1+\Cr{1})$ we get

$\operatorname{\mathbb{E}}\exp\left(\Cr{sp}\left(h(\boldsymbol{w}_{2i}-\boldsymbol{w}_{2i+1})-\hat{T}^{i}(\boldsymbol{w}_{2i},\boldsymbol{w}_{2i+1})\right)^{+}/\sigma\left(\lvert\boldsymbol{x}\rvert\right)\right)\leq
2.$

Using independence of $\hat{T}^{i}$s we get

$\operatorname{\mathbb{E}}\exp\left(\Cr{sp}\sum_{i=0}^{m-1}\left(h(\boldsymbol{w}_{2i}-\boldsymbol{w}_{2i+1})-\hat{T}^{i}(\boldsymbol{w}_{2i},\boldsymbol{w}_{2i+1})\right)^{+}/\sigma\left(\lvert\boldsymbol{x}\rvert\right)\right)\leq
2^{m}.$

Hence, for all $t>0$ we have

$\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}h(\boldsymbol{w}_{2i}-\boldsymbol{w}_{2i+1})-\hat{T}^{i}(\boldsymbol{w}_{2i},\boldsymbol{w}_{2i+1})>tm\sigma\left(\lvert\boldsymbol{x}\rvert\right)\log\log\lvert\boldsymbol{x}\rvert\right)\\\
\leq 2^{m}e^{-\Cr{sp}mt\log\log\lvert\boldsymbol{x}\rvert}.$

By Lemma 4.6, the number of coarse skeletons of length $2m+1$ is at most
$(\log\lvert\boldsymbol{x}\rvert)^{m(4/\alpha)}$. So by (4.5)

$\displaystyle\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}\left[h(\boldsymbol{w}_{2i}-\boldsymbol{w}_{2i+1})-\hat{T}^{i}(\boldsymbol{w}_{2i},\boldsymbol{w}_{2i+1})\right]>\frac{\Cr{0}}{32}m\sigma\left(\lvert\boldsymbol{x}\rvert\right)\log\log\lvert\boldsymbol{x}\rvert\right.$
$\displaystyle\left.\quad\text{for some coarse $Q_{\boldsymbol{x}}$-skeleton
$(\boldsymbol{w}_{j})_{j=0}^{2m}$ of a
path}\vphantom{\sum_{i=0}^{m-1}}\right)$ $\displaystyle\leq$ $\displaystyle
2^{m}(\log\lvert\boldsymbol{x}\rvert)^{m(4/\alpha)}\exp\left(-\Cr{sp}\frac{\Cr{0}}{32}m\log\log\lvert\boldsymbol{x}\rvert\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(-m\C\log\log\lvert\boldsymbol{x}\rvert\right).$

This completes the proof of Proposition 4.4.

####  4.1.2. Proof of Proposition 4.5

Fix $\boldsymbol{x}$ with direction
$\theta\in({\theta_{0}}-\delta,{\theta_{0}}+\delta)$. We will assume
$\lvert\boldsymbol{x}\rvert$ is large whenever required. Fix a coarse
$Q_{\boldsymbol{x}}$-skeleton $(\boldsymbol{w}_{j})_{j=0}^{2m}$ for some
$m\geq 1$. For $0\leq i\leq m-1$, let

$V_{i}:=\left\\{(\boldsymbol{v},\boldsymbol{v}^{\prime})\in\mathbb{Z}^{2}\times\mathbb{Z}^{2}:F_{\boldsymbol{x}}(\boldsymbol{v})=\boldsymbol{w}_{2i},G_{\boldsymbol{x}}(\boldsymbol{v}^{\prime})=\boldsymbol{w}_{2i+1},\boldsymbol{v}^{\prime}-\boldsymbol{v}\in
Q_{\boldsymbol{x}}\right\\},$

and

$X_{i}:=\sup\left\\{\left(h(\boldsymbol{v}-\boldsymbol{v}^{\prime})-\hat{T}^{i}(\boldsymbol{v},\boldsymbol{v}^{\prime})-h(\boldsymbol{w}_{2i}-\boldsymbol{w}_{2i+1})+\hat{T}^{i}(\boldsymbol{w}_{2i},\boldsymbol{w}_{2i+1})\right)/\sigma(\lvert\boldsymbol{x}\rvert):(\boldsymbol{v},\boldsymbol{v}^{\prime})\in
V_{i}\right\\}.$

For any $0\leq i\leq m-1$ and $(\boldsymbol{v},\boldsymbol{v}^{\prime})\in
V_{i}$ we have $\lvert\boldsymbol{v}-\boldsymbol{v}^{\prime}\rvert\leq
5\lvert\boldsymbol{x}\rvert$ by definition of $Q_{\boldsymbol{x}}$. So the
number of elements in $V_{i}$ is at most
$\Cl{p440}\lvert\boldsymbol{x}\rvert^{4}$. Hence, for all $t>0$ we have

$\operatorname{\mathbb{P}}\left(X_{i}\geq
t\right)\leq\Cl{p441}\lvert\boldsymbol{x}\rvert^{4}e^{-\Cl{p442}t}.$ (4.8)

If we can show that for some constant $\Cl{p443}>0$

$\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}X_{i}\geq\frac{\Cr{0}}{32}m\log\log\lvert\boldsymbol{x}\rvert\right)\leq
e^{-\Cr{p443}m\log\lvert\boldsymbol{x}\rvert},$ (4.9)

then the Proposition 4.5 follows using Lemma 4.6. So we will verify the
condition in (4.9). Let $N_{0}$, $N_{1}$ be positive integers such that

$2^{N_{0}}<\frac{\Cr{0}}{96}\log\log\lvert\boldsymbol{x}\rvert\leq
2^{N_{0}+1},\mbox{ and
}2^{N_{1}-1}<\Cl{p444}\log\lvert\boldsymbol{x}\rvert\leq 2^{N_{1}},$ (4.10)

where $\Cr{p444}:=8/\Cr{p442}$. Then

$\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}X_{i}\geq\frac{\Cr{0}}{32}m\log\log\lvert\boldsymbol{x}\rvert\right)\leq\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}X_{i}\mathbf{1}(2^{N_{0}}\leq
X_{i}<2^{N_{1}})\geq\frac{\Cr{0}}{96}m\log\log\lvert\boldsymbol{x}\rvert\right)\\\
+\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}X_{i}\mathbf{1}(X_{i}\geq
2^{N_{1}})\geq\frac{\Cr{0}}{96}m\log\log\lvert\boldsymbol{x}\rvert\right).$
(4.11)

For the second term in the right-hand side of (4.11) we have

$\displaystyle\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}X_{i}\mathbf{1}(X_{i}\geq
2^{N_{1}})\geq\frac{\Cr{0}}{96}m\log\log\lvert\boldsymbol{x}\rvert\right)$
$\displaystyle\leq$
$\displaystyle\operatorname{\mathbb{P}}\left(\sum_{q=N_{1}}^{\infty}\sum_{i=0}^{m-1}2^{q+1}\mathbf{1}(2^{q+1}>X_{i}\geq
2^{q})\geq\frac{\Cr{0}}{96}m\log\log\lvert\boldsymbol{x}\rvert\sum_{q=N_{1}}^{\infty}2^{-(q-N_{1}+1)}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{q=N_{1}}^{\infty}\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}\mathbf{1}(X_{i}\geq
2^{q})\geq\frac{\Cr{0}}{96}m\log\log\lvert\boldsymbol{x}\rvert
2^{N_{1}-2(q+1)}\right)$ $\displaystyle\leq$
$\displaystyle\sum_{q=N_{1}}^{\infty}e^{-mI(a_{1}(q)|b_{1}(q))},$ (4.12)

where

$a_{1}(q):=\frac{\Cr{0}}{96}m\log\log\lvert\boldsymbol{x}\rvert
2^{N_{1}-2(q+1)},\quad b_{1}(q):=\max_{0\leq i\leq
m-1}\operatorname{\mathbb{P}}(X_{i}\geq 2^{q}),$

and $I$ is the large deviation rate function for Bernoulli random variables
given by

$I(x|y):=x\log\frac{x}{y}+(1-x)\log\frac{1-x}{1-y}.$ (4.13)

Using (4.8), $\Cr{p444}=8/\Cr{p442}$, and
$2^{N_{1}}\geq\Cr{p444}\log\lvert\boldsymbol{x}\rvert$, we get for $q\geq
N_{1}$

$b_{1}(q)\leq\Cr{p441}\lvert\boldsymbol{x}\rvert^{4}e^{-\Cr{p442}2^{q}}\leq
e^{-\C 2^{q}}.$

So $b_{1}(q)$ is much smaller than $a_{1}(q)$. Therefore, using (4.13) for
$I(a_{1}(q)|b_{1}(q))$ and expanding the log terms we see that the term
$a_{1}(q)\log(b_{1}(q)^{-1})$ dominates the others. Hence

$I(a_{1}(q)|b_{1}(q))\geq\C
a_{1}(q)\log(b_{1}(q)^{-1})\geq\C\log\log\lvert\boldsymbol{x}\rvert\log\lvert\boldsymbol{x}\rvert
2^{-q}.$

Therefore, continuing from (4.12) and using (4.8) we get

$\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}X_{i}\mathbf{1}(X_{i}\geq
2^{N_{1}})\geq\frac{\Cr{0}}{96}m\log\log\lvert\boldsymbol{x}\rvert\right)\leq
e^{-\C m\log\lvert\boldsymbol{x}\rvert}.$ (4.14)

For the first term in the right-hand side of (4.11) we have

$\displaystyle\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}X_{i}\mathbf{1}(2^{N_{0}}\leq
X_{i}<2^{N_{1}})\geq\frac{\Cr{0}}{96}m\log\log\lvert\boldsymbol{x}\rvert\right)$
$\displaystyle\leq$
$\displaystyle\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}\sum_{q=N_{0}}^{N_{1}-1}2^{q+1}\mathbf{1}(X_{i}\geq
2^{q})\geq\frac{\Cr{0}}{96}m\log\log\lvert\boldsymbol{x}\rvert\right)$
$\displaystyle\leq$
$\displaystyle\sum_{q=N_{0}}^{N_{1}-1}\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}\mathbf{1}(X_{i}\geq
2^{q})\geq\frac{\Cr{0}}{96}m(\log\log\lvert\boldsymbol{x}\rvert)2^{-(q+1)}(N_{1}-N_{0})^{-1}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{q=N_{0}}^{N_{1}-1}e^{-mI(a_{2}(q)|b_{2}(q))},$ (4.15)

where

$a_{2}(q):=\frac{\Cr{0}}{96}(\log\log\lvert\boldsymbol{x}\rvert)2^{-(q+1)}(N_{1}-N_{0})^{-1},\quad
b_{2}(q):=\max_{0\leq i\leq m-1}\operatorname{\mathbb{P}}(X_{i}\geq 2^{q}).$

We will use the following claim to derive a bound of $b_{2}(q)$. The proof of
the claim is presented later.

######  Claim 4.1.1.

For $0\leq i\leq m-1$, $(\boldsymbol{v},\boldsymbol{v}^{\prime})\in V_{i}$,
and $t\in[2^{N_{0}},2^{N_{1}-1}]$ we have

$\operatorname{\mathbb{P}}\left(h(\boldsymbol{v}-\boldsymbol{v}^{\prime})-\hat{T}^{i}(\boldsymbol{v},\boldsymbol{v}^{\prime})-h(\boldsymbol{w}_{2i}-\boldsymbol{w}_{2i+1})+\hat{T}^{i}(\boldsymbol{w}_{2i},\boldsymbol{w}_{2i+1}))\geq
t\sigma(\lvert\boldsymbol{x}\rvert)\right)\leq
e^{-C_{9}t\log\lvert\boldsymbol{x}\rvert}.$

By this claim and using that size of $V_{i}$ is at most
$\Cr{p440}\lvert\boldsymbol{x}\rvert^{4}$ we get, for $N_{0}\leq q\leq
N_{1}-1$

$b_{2}(q)=\max_{0\leq i\leq m-1}\operatorname{\mathbb{P}}\left(X_{i}\geq
2^{q}\right)\leq\C\lvert\boldsymbol{x}\rvert^{4}e^{-\C
2^{q}\log\lvert\boldsymbol{x}\rvert}\leq e^{-\C
2^{q}\log\lvert\boldsymbol{x}\rvert}.$

From (4.10) we get $\C 2^{-q}\leq a_{2}(q)\leq\C 2^{-q}$. Therefore, using
(4.13) for $I(a_{2}(q)|b_{2}(q))$ and expanding the log terms we see that the
term $a_{2}(q)\log(b_{2}(q)^{-1})$ dominates the others. Hence

$I(a_{2}(q)|b_{2}(q))\geq\C
a_{2}(q)\log(b_{2}(q)^{-1})\geq\C\log\lvert\boldsymbol{x}\rvert.$

So continuing from (4.15) we get

$\operatorname{\mathbb{P}}\left(\sum_{i=0}^{m-1}X_{i}\mathbf{1}(2^{N_{0}}\leq
X_{i}<2^{N_{1}})\geq\frac{\Cr{0}}{96}m\log\log\lvert\boldsymbol{x}\rvert\right)\leq
e^{-m\C\log\lvert\boldsymbol{x}\rvert}.$

Combining this with (4.14) we get (4.9). So to complete the proof of
Proposition 4.5 we only need to prove Claim 4.1.1.

##### Proof of Claim 4.1.1:

Fix $0\leq i\leq m-1$ and $(\boldsymbol{v},\boldsymbol{v}^{\prime})\in V_{i}$.
Let

$\mathcal{D}(\boldsymbol{v},\boldsymbol{v}^{\prime}):=h(\boldsymbol{v}-\boldsymbol{v}^{\prime})-\hat{T}^{i}(\boldsymbol{v},\boldsymbol{v}^{\prime})-h(\boldsymbol{w}_{2i}-\boldsymbol{w}_{2i+1})+\hat{T}^{i}(\boldsymbol{w}_{2i},\boldsymbol{w}_{2i+1})).$

Let
$\ell_{0}:=\lvert\boldsymbol{x}\rvert(\log\lvert\boldsymbol{x}\rvert)^{-1/\alpha}$.
We consider two cases, either
$\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{v}^{\prime}-\boldsymbol{v})\leq\ell_{0}$,
or
$\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{v}^{\prime}-\boldsymbol{v})\geq\ell_{0}$.

##### Case I:

Suppose
$\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{v}^{\prime}-\boldsymbol{v})\leq\ell_{0}$.
Using Lemma 4.6,
$\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{v}-\boldsymbol{w}_{2i})$ and
$\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{v}^{\prime}-\boldsymbol{w}_{2i+1})$
are at most $\C\Delta(\boldsymbol{x})\log\log\lvert x\rvert$, which is smaller
than $\ell_{0}$. Hence $\lvert\boldsymbol{v}-\boldsymbol{w}_{2i}\rvert$ and
$\lvert\boldsymbol{v}^{\prime}-\boldsymbol{w}_{2i+1}\rvert$ are at most
$\C\ell_{0}$. Therefore, using (A1) and (A2), we get

$\operatorname{\mathbb{P}}\left(\mathcal{D}(\boldsymbol{v},\boldsymbol{v}^{\prime})\geq
t\sigma(\lvert\boldsymbol{x}\rvert)\right)\leq\C e^{-\C
t\sigma(\lvert\boldsymbol{x}\rvert)/\sigma(\lvert\ell_{0}\rvert)}\leq e^{-\C
t\log\lvert\boldsymbol{x}\rvert}.$

So the claim is proved in this case.

##### Case II:

Suppose
$\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{v}^{\prime}-\boldsymbol{v})\geq\ell_{0}$.
Let

$\displaystyle\mathcal{D}_{1}(\boldsymbol{v},\boldsymbol{v}^{\prime}):=h(\boldsymbol{v}-\boldsymbol{v}^{\prime})-T(\boldsymbol{v},\boldsymbol{v}^{\prime})-h(\boldsymbol{v}-\boldsymbol{w}_{2i+1})+T(\boldsymbol{v},\boldsymbol{w}_{2i+1}),$
$\displaystyle\mathcal{D}_{2}(\boldsymbol{v},\boldsymbol{v}^{\prime}):=h(\boldsymbol{v}-\boldsymbol{w}_{2i+1})-T(\boldsymbol{v},\boldsymbol{w}_{2i+1})-h(\boldsymbol{w}_{2i}-\boldsymbol{w}_{2i+1})+T(\boldsymbol{w}_{2i},\boldsymbol{w}_{2i+1}).$

So
$\mathcal{D}(\boldsymbol{v},\boldsymbol{v}^{\prime})=\mathcal{D}_{1}(\boldsymbol{v},\boldsymbol{v}^{\prime})+\mathcal{D}_{2}(\boldsymbol{v},\boldsymbol{v}^{\prime})$,
and hence

$\operatorname{\mathbb{P}}\left(\mathcal{D}(\boldsymbol{v},\boldsymbol{v}^{\prime})\geq
t\sigma(\lvert\boldsymbol{x}\rvert)\right)\leq\operatorname{\mathbb{P}}\left(\mathcal{D}_{1}(\boldsymbol{v},\boldsymbol{v}^{\prime})\geq\frac{t}{2}\sigma(\lvert\boldsymbol{x}\rvert)\right)+\operatorname{\mathbb{P}}\left(\mathcal{D}_{2}(\boldsymbol{v},\boldsymbol{v}^{\prime})\geq\frac{t}{2}\sigma(\lvert\boldsymbol{x}\rvert)\right).$
(4.16)

We will only consider the first term on the right-hand side, the second term
can be dealt with similarly.

Suppose $i_{0}$ and $j_{0}$ are such that $\boldsymbol{v}^{\prime}\in
B_{i_{0}j_{0}}$, where recall that $B_{ij}$ is defined in (4.3). Let

$R(t):=\left\\{\boldsymbol{y}\in\mathbb{R}^{2}:\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y})=i_{0}\ell_{\boldsymbol{x}},\right.\\\
\left.j_{0}\Delta(\ell_{\boldsymbol{x}})-t^{1/2}\Delta(\ell_{\boldsymbol{x}})(\log\ell_{\boldsymbol{x}})^{1/2}\leq\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y})\leq(j_{0}+1)\Delta(\ell_{\boldsymbol{x}})+t^{1/2}\Delta(\ell_{\boldsymbol{x}})(\log\ell_{\boldsymbol{x}})^{1/2}\vphantom{\boldsymbol{y}\in\mathbb{R}^{2}}\right\\}.$

So $R(t)$ is an extension of a side of the parallelogram $B_{i_{0}j_{0}}$.
Define the event

$\mbox{$\mathcal{E}(t)$: $\Gamma(\boldsymbol{v},\boldsymbol{v}^{\prime})$
intersects $R(t)$}.$

Since $\boldsymbol{v}^{\prime}\in B_{i_{0}j_{0}}$, distance of the segment
$R(t)$ from $\boldsymbol{v}^{\prime}$ in $-{\theta}$ direction is less than
$\ell_{\boldsymbol{x}}$. So, if $\mathbb{T}\not\in\mathcal{E}(t)$, then
$\mathcal{W}(\boldsymbol{v}^{\prime},\boldsymbol{v},k,-{\theta})\geq
t^{1/2}\Delta(\ell_{\boldsymbol{x}})(\log\ell_{\boldsymbol{x}})^{1/2}$ for
some $k\leq\ell_{\boldsymbol{x}}$. So to bound the probability of
$\mathbb{T}\not\in\mathcal{E}(t)$ we use Corollary 2.7 with

$\tilde{{\theta_{0}}}:=-{\theta},\quad\tilde{n}:=\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{v}^{\prime}-\boldsymbol{v}),\quad\tilde{l}:=\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{v}-\boldsymbol{v}^{\prime}),\quad\tilde{k}:=\ell_{\boldsymbol{x}},\quad\tilde{t}:=t^{1/2}.$

We will now verify the conditions of Corollary 2.7. Recall that by our choice
of $\delta$ from (4.1) ${\theta}$ is a direction of type I, equivalently so is
$-{\theta}$. Using the assumption of case II we get
$\tilde{n}\geq\ell_{0}\geq\tilde{n_{0}}$. By Lemma 4.6 we have
$|\tilde{l}|\leq\C\Delta(\lvert x\rvert)\log\log\lvert\boldsymbol{x}\rvert$.
Hence, $|\tilde{l}|\leq\tilde{n}\tilde{\delta_{2}}$, as required. Recall from
the statement of the claim that $t\leq 2^{N_{1}-1}$, and from (4.10) we have
$2^{N_{1}-1}\leq\Cr{p444}\log\lvert\boldsymbol{x}\rvert$. Therefore,
$t^{1/2}\Delta(\tilde{k})(\log\tilde{k})\leq\tilde{k}\tilde{\delta_{3}}$, as
required. Thus, all the conditions for applying Corollary 2.7 hold, and we get

$\operatorname{\mathbb{P}}\left(\mathcal{E}(t)^{c}\right)\leq e^{-\C
t\log\ell_{\boldsymbol{x}}}\leq e^{-\C t\log\lvert\boldsymbol{x}\rvert}.$
(4.17)

Let $R:=R(2^{N_{1}-1})$. For any $\boldsymbol{y}$ in $R$ let

$\mathcal{D}^{\prime}_{1}(\boldsymbol{y}):=h(\boldsymbol{v}-\boldsymbol{y})-T(\boldsymbol{v},\boldsymbol{y})-h(\boldsymbol{v}-\boldsymbol{w}_{2i+1})+T(\boldsymbol{v},\boldsymbol{w}_{2i+1}),\quad\mathcal{D}^{\prime}_{2}(\boldsymbol{y}):=h(\boldsymbol{y}-\boldsymbol{v}^{\prime})-T(\boldsymbol{y},\boldsymbol{v}^{\prime}).$

If $\Gamma(\boldsymbol{v},\boldsymbol{v}^{\prime})$ passes through
$\boldsymbol{y}$ then
$\mathcal{D}_{1}(\boldsymbol{v},\boldsymbol{v}^{\prime})\leq\mathcal{D}^{\prime}_{1}(\boldsymbol{y})+\mathcal{D}^{\prime}_{2}(\boldsymbol{y})$.
Hence

$\operatorname{\mathbb{P}}\left(\mathcal{D}_{1}(\boldsymbol{v},\boldsymbol{v}^{\prime})\geq\frac{t}{2}\sigma(\lvert\boldsymbol{x}\rvert)\right)\leq\operatorname{\mathbb{P}}\left(\max_{\boldsymbol{y}\in
R}\mathcal{D}^{\prime}_{1}(\boldsymbol{y})\geq\frac{t}{4}\sigma(\lvert\boldsymbol{x}\rvert)\right)+\operatorname{\mathbb{P}}\left(\max_{\boldsymbol{y}\in
R}\mathcal{D}^{\prime}_{2}(\boldsymbol{y})\geq\frac{t}{4}\sigma(\lvert\boldsymbol{x}\rvert)\right)+\operatorname{\mathbb{P}}(\mathcal{E}(t)^{c}).$
(4.18)

Let us consider the first term in the right-hand side first. We will use
Corollary 3.3 with

$\displaystyle\tilde{{\theta_{0}}}:={\theta},\quad\tilde{n}:=i_{0}\ell_{\boldsymbol{x}}-\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{v}),\quad\tilde{L}:=\Delta(\ell_{\boldsymbol{x}})(1+2^{(N_{1}-1)/2+1}(\log\ell_{\boldsymbol{x}})^{1/2}),$
$\displaystyle\tilde{d}:=\Delta(\ell_{\boldsymbol{x}})(j_{0}-2^{(N_{1}-1)/2}(\log\ell_{\boldsymbol{x}})^{1/2})-\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{v}).$

We will now verify the conditions of Corollary 3.3. By our choice of $\delta$
in (4.1), ${\theta}$ is of both type I and type II. Since $\tilde{n}$ is the
distance of $R$ from $\boldsymbol{v}$ in direction $-{\theta}$, we have

$\tilde{n}\geq\ell_{0}-\ell_{\boldsymbol{x}}\geq\Cl{331}\ell_{0}\geq\tilde{n_{0}}.$

Using $2^{N_{1}-1}<\Cr{p444}\log\lvert\boldsymbol{x}\rvert$, (A2), and
$\tilde{n}\geq\Cr{331}\ell_{0}$, we get

$\tilde{L}\leq\Cl{332}\Delta(\ell_{\boldsymbol{x}})\log\lvert\boldsymbol{x}\rvert\leq\C\Delta(\ell_{0})(\log\lvert\boldsymbol{x}\rvert)^{1-(1+\beta)/(2\alpha)}\leq\tilde{\delta_{2}}\Delta(\tilde{n}).$
(4.19)

By Lemma 4.6 we have
$|\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{v}^{\prime}-\boldsymbol{v})|\leq\C\Delta(\boldsymbol{x})(\log\log\lvert\boldsymbol{x}\rvert)^{1/2}$.
Since $\boldsymbol{v}^{\prime}\in B_{i_{0}j_{0}}$, we have
$|\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{v}^{\prime})-j_{0}\Delta(\ell_{\boldsymbol{x}})|\leq\Delta(\ell_{\boldsymbol{x}})$.
Therefore, using (A2) and $\tilde{n}\geq\Cr{331}\ell_{0}$, we get

$|\tilde{d}|\leq\C\Delta(\lvert\boldsymbol{x}\rvert)(\log\log\lvert\boldsymbol{x}\rvert)^{1/2}+2^{N_{1}/2}\Delta(\ell_{\boldsymbol{x}})(\log\ell_{\boldsymbol{x}})^{1/2}\leq\C\Delta(\lvert\boldsymbol{x}\rvert)(\log\log\lvert\boldsymbol{x}\rvert)^{1/2}\leq\tilde{\delta_{1}}\tilde{n}.$
(4.20)

By Corollary 3.3 we get for $\tilde{t}\geq\tilde{t_{0}}$

$\operatorname{\mathbb{P}}\left(\max_{\boldsymbol{y}\in
R}\mathcal{D}^{\prime}_{1}(\boldsymbol{y})\geq\C\tilde{L}\frac{|\tilde{d}|}{\tilde{n}}+\tilde{t}\sigma(\Delta^{-1}(\tilde{L}))\log\Delta^{-1}(\tilde{L})\right)\leq\C
e^{-\C\tilde{t}\log\tilde{L}}.$ (4.21)

Let $\tilde{t}$ be such that

$\C\tilde{L}\frac{|\tilde{d}|}{\tilde{n}}+\tilde{t}\sigma(\Delta^{-1}(\tilde{L}))\log\Delta^{-1}(\tilde{L})=\frac{t}{4}\sigma(\lvert\boldsymbol{x}\rvert).$
(4.22)

We need to verify $\tilde{t}\geq\tilde{t_{0}}$. Using (4.19) and (A2), we have

$\tilde{L}\leq\Cr{332}\Delta(\ell_{\boldsymbol{x}})\log\lvert\boldsymbol{x}\rvert\leq\C\Delta(\lvert\boldsymbol{x}\rvert)(\log\lvert\boldsymbol{x}\rvert)^{-1/\alpha}.$
(4.23)

Using this with (4.20) we get

$\tilde{L}\frac{|\tilde{d}|}{\tilde{n}}\leq\C\sigma(\lvert\boldsymbol{x}\rvert)(\log\log\lvert\boldsymbol{x}\rvert)^{1/2}(\log\lvert\boldsymbol{x}\rvert)^{-1/\alpha}.$
(4.24)

Using $t\geq 2^{N_{0}}\geq(\Cr{0}/96)\log\log\lvert\boldsymbol{x}\rvert$,
(4.22), (4.24), and (4.23), we get

$\tilde{t}\geq\C
t\frac{\sigma(\lvert\boldsymbol{x}\rvert)}{\sigma(\Delta^{-1}(\tilde{L}))\log\Delta^{-1}(\tilde{L})}\geq\C
t\left(\frac{\lvert\boldsymbol{x}\rvert}{\Delta^{-1}(\tilde{L})}\right)^{\alpha}(\log\lvert\boldsymbol{x}\rvert)^{-1}\\\
\geq\C
t\left(\frac{\Delta(\lvert\boldsymbol{x}\rvert)}{\tilde{L}}\right)^{2\alpha/(1+\beta)}(\log\lvert\boldsymbol{x}\rvert)^{-1}\geq\C
t(\log\lvert\boldsymbol{x}\rvert)^{(1-\beta)/(1+\beta)}\geq\tilde{t_{0}}.$

Therefore, from (4.21), (4.22) we get

$\operatorname{\mathbb{P}}\left(\max_{\boldsymbol{y}\in
R}\mathcal{D}^{\prime}_{1}(\boldsymbol{y})\geq\frac{t}{4}\sigma(\lvert\boldsymbol{x}\rvert)\right)\leq\C
e^{-\C t(\log\lvert\boldsymbol{x}\rvert)^{2/(1+\beta)}}\leq\C e^{-\C
t(\log\lvert\boldsymbol{x}\rvert)}.$ (4.25)

Now we will consider the second term in the right-hand side of (4.18). By
(4.23) width of $R$ is less than $\Delta(\boldsymbol{x})$. Distance of $R$
from $\boldsymbol{v}^{\prime}$ in ${\theta}$ direction is less than
$\ell_{\boldsymbol{x}}$. So
$\lvert\boldsymbol{y}-\boldsymbol{v}^{\prime}\rvert\leq\C\ell_{\boldsymbol{x}}$
for all $\boldsymbol{y}\in R$. Thus, using (A1), (A2), and a union bound, we
get

$\operatorname{\mathbb{P}}\left(\max_{\boldsymbol{y}\in
R}\mathcal{D}^{\prime}_{2}(\boldsymbol{y})\geq\frac{t}{4}\sigma(\lvert\boldsymbol{x}\rvert)\right)\leq\C\lvert\boldsymbol{x}\rvert
e^{-\C
t\sigma(\lvert\boldsymbol{x}\rvert)/\sigma(\ell_{\boldsymbol{x}})}\leq\C
e^{-\C t(\log\lvert\boldsymbol{x}\rvert)^{2}}$

Using this in (4.18) together with (4.17) and (4.25) we get appropriate bound
for the first term in the right-hand side of (4.16). The second term can be
dealt with similarly. This completes the proof of Claim 4.1.1. This also
completes the proof of Proposition 4.5.

###  4.2. Proof of Theorem 4.2

We assume that $\eta<1$ because for $\eta=1$ the result is same as Proposition
2.3. Let $n$ be a positive integer such that $(1-\alpha)^{n}\leq\eta/2$.
Define for $0\leq m\leq n$ and $k\geq 3$

$\psi_{m}(k):=k^{-\alpha}\sigma(k)(\log k)^{(1-\alpha)^{m}}(\log\log
k)^{1-(1-\alpha)^{m}}.$

Because $\psi_{n}(k)\leq\phi_{\eta}(k)$ for large enough $k$, to prove Theorem
4.2 it is enough to show that $h$ satisfies GAP with exponent $\alpha$ and
correction factor $\psi_{n}$.

By assumptions of Theorem 4.2 ${\theta_{0}}$ is a direction of both type I and
II. Therefore, by Theorem 4.1, there exist positive constants $\delta$,
$C_{c}$, $M_{c}$, $K$, $a$, such that $h$ satisfies
$\text{CHAP}(\alpha,\widehat{\phi},M_{c},C_{c},K,a)$ in the sector of
directions $({\theta_{0}}-\delta,{\theta_{0}}+\delta)$. Define
$\mathcal{S}_{0}:=[0,2\pi]$, and for $1\leq m\leq n$ define

$\mathcal{S}_{m}:=\left[{\theta_{0}}-\delta\frac{n-m+1}{n},{\theta_{0}}+\delta\frac{n-m+1}{n}\right].$

We will show that $h$ satisfies GAP with exponent $\alpha$ and correction
factor $\psi_{n}$ in $\mathcal{S}_{n}$.

By Proposition 2.3, $h$ satisfies GAP with exponent $\alpha$ and correction
factor $\phi_{1}=\psi_{0}$ in all directions. Hence, there exist constants
$C_{g}>0$ and $M_{g}>0$ such that for $\lvert\boldsymbol{x}\rvert\geq M_{g}$
we have

$h(\boldsymbol{x})\leq
g(\boldsymbol{x})+C_{g}\sigma\left(\lvert\boldsymbol{x}\rvert\right)\log\lvert\boldsymbol{x}\rvert.$
(4.26)

We will use an inductive argument. Fix $0\leq m<n$. Suppose $h$ satisfies GAP
with exponent $\alpha$, correction factor $\psi_{m}$, in the sector
$\mathcal{S}_{m}$, with constants $C$ and $M$. We will show that $h$ satisfies
GAP with exponent $\alpha$, correction factor $\psi_{m+1}$, in the sector
$\mathcal{S}_{m+1}$, with constant $C$ and $M$. This will prove that $h$
satisfies GAP with exponent $\alpha$, correction factor $\psi_{n}$ in the
sector $\mathcal{S}_{n}$. The constants $C$ and $M$ need to remain unchanged.
We will see that if $C$ and $M$ are chosen large enough then the inductive
step works.

We assume without loss of generality $K>1$, $M>3$, $M>M_{c}$, $M>M_{g}$. Also
we assume $M$ is large enough, independent of $m$, so that
$\psi_{m+1}(\lvert\boldsymbol{x}\rvert)\geq 1$ for all
$\lvert\boldsymbol{x}\rvert\geq M$, which is possible by (A2). Since $h$ has
sublinear growth, there exists constant $r>0$ such that for all
$\boldsymbol{x}$ we have $h(\boldsymbol{x})\leq r\lvert\boldsymbol{x}\rvert$.
Let $\nu:=(1-\beta)/4$, $c_{0}:=3C_{c}$, $c_{1}:=C_{c}a$, $c_{2}:=3K$,
$c_{3}:=(c_{1}+c_{0}+C_{g}c_{2}(\alpha\nu)^{-1})\mathfrak{p}^{-1}$,
$c_{4}:=c_{2}^{\alpha}\mathfrak{p}^{-1}$,

$c_{5}:=c_{3}^{\alpha}c_{4}^{1-\alpha}\left(\left(\frac{\alpha}{1-\alpha}\right)^{1-\alpha}+\left(\frac{1-\alpha}{\alpha}\right)^{\alpha}\right),$

and $c_{6}:=(1-\alpha)c_{3}(\alpha c_{4})^{-1}$. We start the inductive step
now. Consider $\boldsymbol{x}$ with direction ${\theta}\in\mathcal{S}_{m+1}$
and $\lvert\boldsymbol{x}\rvert\geq M$. We need to show

$h(\boldsymbol{x})\leq
g(\boldsymbol{x})+C\lvert\boldsymbol{x}\rvert^{\alpha}\psi_{m+1}(\lvert\boldsymbol{x}\rvert).$
(4.27)

We are free to choose $C$ and $M$ large enough, independent of $m$. In various
steps we will assume $C$ is large enough depending on $M$, and $M$ will be
chosen to be large enough without depending on $C$.

##### Bounding $h(\boldsymbol{x})$ when $\lvert\boldsymbol{x}\rvert$ is small:

Suppose $\lvert\boldsymbol{x}\rvert\leq c_{2}M$. Assuming $C\geq rc_{2}M$, we
get

$h(\boldsymbol{x})\leq r\lvert\boldsymbol{x}\rvert\leq rc_{2}M\leq C\leq
C\lvert\boldsymbol{x}\rvert^{\alpha}\psi_{m+1}(\boldsymbol{x})\leq
g(\boldsymbol{x})+C\lvert\boldsymbol{x}\rvert^{\alpha}\psi^{m}(\lvert\boldsymbol{x}\rvert).$

Thus (4.27) is verified.

##### Defining $\boldsymbol{x}^{\ast}$, $\boldsymbol{x}_{\sf L}$ and
$\boldsymbol{x}_{\sf S}$ when $\lvert\boldsymbol{x}\rvert$ is large:

Suppose $\lvert\boldsymbol{x}\rvert\geq c_{2}M$. Take
$q\in[c_{2},\lvert\boldsymbol{x}\rvert/M]\cap\mathbb{Q}$. Then
$\lvert\boldsymbol{x}/q\rvert\geq M\geq M_{c}$. Applying
$\text{CHAP}(\alpha,\widehat{\phi},M_{c},C_{c},K,a)$ to $\boldsymbol{x}/q$ we
get

$\boldsymbol{x}/q=\sum_{i=1}^{3}\alpha_{qi}\boldsymbol{y}_{qi}\mbox{ with
}\alpha_{qi}\geq 0,\;\sum_{i=1}^{3}\alpha_{qi}\in[1,a]\mbox{ and
}\boldsymbol{y}_{qi}\in Q_{\boldsymbol{x}/q}(\alpha,\widehat{\phi},C_{c},K).$
(4.28)

Let

$L(q):=\left\\{1\leq i\leq
3:\lvert\boldsymbol{y}_{qi}\rvert\geq\lvert\boldsymbol{x}/q\rvert^{1-\nu}\right\\}$

and

$\boldsymbol{x}^{\ast}:=\sum_{i=1}^{3}\lfloor
q\alpha_{qi}\rfloor\boldsymbol{y}_{qi},\;\boldsymbol{x}_{\sf L}:=\sum_{i\in
L(q)}\gamma_{qi}\boldsymbol{y}_{qi},\;\boldsymbol{x}_{\sf S}:=\sum_{i\not\in
L(q)}\gamma_{qi}\boldsymbol{y}_{qi},$ (4.29)

where

$\gamma_{qi}:=q\alpha_{qi}-\lfloor q\alpha_{qi}\rfloor\in[0,1).$

Therefore,

$\boldsymbol{x}=\boldsymbol{x}^{\ast}+\boldsymbol{x}_{\sf
L}+\boldsymbol{x}_{\sf S}.$

##### Direction of $\boldsymbol{x}_{\sf L}$:

Consider $i\in L(q)$. Then

$\lvert\boldsymbol{y}_{qi}\rvert\geq\lvert\boldsymbol{x}/q\rvert^{1-\nu}.$
(4.30)

Using Lemma 4.6, $\boldsymbol{y}_{qi}\in
Q_{\boldsymbol{x}/q}(\alpha,\widehat{\phi},C_{c},K)$,
$\lvert\boldsymbol{x}/q\rvert\geq M$, assuming $M$ is large enough, and (A2),
we get

$\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y}_{qi})\leq\C\Delta(\boldsymbol{x}/q)(\log\log\lvert\boldsymbol{x}/q\rvert)^{1/2}\leq\C\lvert\boldsymbol{x}/q\rvert^{(1+\beta)/2}(\log\log\lvert\boldsymbol{x}/q\rvert)^{1/2}.$

Therefore, using (4.30), (A2), and $1-\nu=1-(1-\beta)/4>(1+\beta)/2$, we get

$\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y}_{qi})\geq\lvert\boldsymbol{y}_{qi}\rvert-\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y}_{qi})\geq\C\lvert\boldsymbol{x}/q\rvert^{1-\nu},$

and, further, using $1-\nu-(1+\beta)/2=(1-\beta)/4$ we get

$\frac{\pi^{2}_{\theta,\theta^{t}}(\boldsymbol{y}_{qi})}{\pi^{1}_{\theta,\theta^{t}}(\boldsymbol{y}_{qi})}\leq\C\frac{\lvert\boldsymbol{x}/q\rvert^{(1+\beta)/2}(\log\log\lvert\boldsymbol{x}/q\rvert)^{1/2}}{\lvert\boldsymbol{x}/q\rvert^{1-\nu}}\leq\C\frac{(\log\log
M)^{1/2}}{M^{(1-\beta)/4}}.$

Since ${\theta}\in\mathcal{S}_{m+1}$, assuming $M$ is large enough, we get
direction of $\boldsymbol{y}_{qi}$ is in $\mathcal{S}_{m}$. This implies
$\boldsymbol{x}_{\sf L}$ has direction in $\mathcal{S}_{m}$.

##### Bounding $h(\boldsymbol{x}^{\ast})$:

Using subadditivity of $h$, (4.29), (4.28), and (A2), we get

$h(\boldsymbol{x}^{\ast})\leq\sum_{i=1}^{3}\lfloor q\alpha_{qi}\rfloor
h(\boldsymbol{y}_{qi})\leq\sum_{i=1}^{3}\lfloor
q\alpha_{qi}\rfloor\left[g_{\boldsymbol{x}}(\boldsymbol{y}_{qi})+C_{c}\lvert\boldsymbol{x}/q\rvert^{\alpha}\widehat{\phi}(\lvert\boldsymbol{x}/q\rvert)\right]\\\
\leq
g_{\boldsymbol{x}}(\boldsymbol{x}^{\ast})+c_{1}\mathfrak{p}^{-1}q^{1-\alpha}\lvert\boldsymbol{x}\rvert^{\alpha}\widehat{\phi}(\lvert\boldsymbol{x}\rvert).$
(4.31)

##### Bounding $h(\boldsymbol{x}_{\sf S})$ when $\lvert\boldsymbol{x}_{\sf
S}\rvert$ is large:

Suppose $\lvert\boldsymbol{x}_{\sf S}\rvert\geq M_{g}$. Using $q\geq
c_{2}=3K>3$, $\lvert\boldsymbol{x}/q\rvert\geq M\geq 1$, and (4.29) we get

$\lvert\boldsymbol{x}_{\sf S}\rvert=\lvert\sum_{i\not\in
L(q)}\gamma_{qi}\boldsymbol{y}_{qi}\rvert\leq\sum_{i\not\in
L(q)}\gamma_{qi}\lvert\boldsymbol{y}_{qi}\rvert\leq
3\lvert\boldsymbol{x}/q\rvert^{1-\nu}\leq
3\lvert\boldsymbol{x}/q\rvert\leq\lvert\boldsymbol{x}\rvert.$

Using this and
$\log\lvert\boldsymbol{x}\rvert\leq\lvert\boldsymbol{x}\rvert^{\alpha\nu}(\alpha\nu)^{-1}$
we get

$\frac{\sigma(\lvert\boldsymbol{x}_{\sf S}\rvert)\log\lvert\boldsymbol{x}_{\sf
S}\rvert}{\sigma(\lvert\boldsymbol{x}\rvert)\log\log\lvert\boldsymbol{x}\rvert}\leq\mathfrak{p}^{-1}\left(\frac{\lvert\boldsymbol{x}_{\sf
S}\rvert}{\lvert\boldsymbol{x}\rvert}\right)^{\alpha}\frac{\log\lvert\boldsymbol{x}\rvert}{\log\log\lvert\boldsymbol{x}\rvert}\leq\mathfrak{p}^{-1}\frac{c_{2}^{\alpha}q^{\alpha\nu}\log\lvert\boldsymbol{x}\rvert}{q^{\alpha}\lvert\boldsymbol{x}\rvert^{\alpha\nu}\log\log\lvert\boldsymbol{x}\rvert}\leq\mathfrak{p}^{-1}c_{2}^{\alpha}(\alpha\nu)^{-1}q^{-\alpha(1-\nu)}.$

Since $\lvert\boldsymbol{x}_{\sf S}\rvert\geq M_{g}$, using (4.26) we get

$\displaystyle h(\boldsymbol{x}_{\sf S})$ $\displaystyle\leq
g(\boldsymbol{x}_{\sf S})+C_{g}\lvert\boldsymbol{x}_{\sf
S}\rvert^{\alpha}\phi_{1}(\lvert\boldsymbol{x}_{\sf S}\rvert)$
$\displaystyle\leq\sum_{i\not\in
L(q)}\gamma_{qi}g(\boldsymbol{y}_{qi})+C_{g}\sigma(\lvert\boldsymbol{x}_{\sf