## A.2 Construction of the path $\pi$ for the modification in the unbounded case

Recall that, here, $u^\Lambda$ and $v^\Lambda$ are the vertices defined at the beginning of Section 2.3. The aim is to prove that we can construct a path $\pi$ in a deterministic way such that:

(i) $\pi$ goes from $u$ to $u^\Lambda$ without visiting a vertex of $B_\infty(sN, \ell^\Lambda)$, then going from $u^\Lambda$ to $v^\Lambda$ in a shortest way for the norm $\|\cdot\|_1$ (and thus being contained in $B_\infty(sN, \ell^\Lambda)$) and then goes from $v^\Lambda$ to $v$ without visiting a vertex of $B_\infty(sN, \ell^\Lambda)$,

(ii) $\pi$ is entirely contained in $B_{2,s,N}$ and does not have vertices on the boundary of $B_{2,s,N}$ except $u$ and $v$,

(iii) $\pi$ is self-avoiding,

(iv) the length of $\pi_{u,u^\Lambda} \cup \pi_{v^\Lambda, v}$ is bounded from above by $2r_2N + K$, where $K$ is the number of edges in $B_\infty(0, \ell^\Lambda + 3)$.

As it is said in Section 2.3, we want to construct a path from $u$ to $sN$ and a path from $sN$ to $v$ which have no vertex in common except $sN$ and such that their lengths are bounded from above by $r_2N$. To get them, we use the following lemma whose proof is left to the reader.

**Lemma A.2.** Let $m \in \mathbb{N}^*$ and $x, y$ two vertices of $\mathbb{Z}^d$ such that $\|x\|_1 = \|y\|_1 = m$ and $x \neq y$. Then we can build in a deterministic way two paths $\pi_x$ and $\pi_y$ linking respectively $x$ and $y$ to 0 and such that their length is equal to $m$, they have only 0 as a common vertex and they have respectively only $x$ and $y$ as vertices whose norm $\|\cdot\|_1$ is greater than or equal to $m$.

Using this lemma and replacing 0 by $sN$ using a translation, we get two paths linking $u$ to $sN$ and $v$ to $sN$ with the stated properties. Recall that $B_\infty(sN, \ell^\Lambda + 3) \subset B_{2,s,N}$ and let $u_0$ (resp. $v_0$) denote the first vertex in $B_\infty(sN, \ell^\Lambda + 3)$ visited by the path going from $u$ to $sN$ (resp. the one going from $v$ to $sN$). Then we get two paths $\pi_{u,u_0}$ and $\pi_{v_0,v}$ respectively from $u$ to $u_0$ and from $v_0$ to $v$ both constructed in a deterministic way such that $\pi_{u,u_0}$ and $\pi_{v_0,v}$ do not have any vertex in common, are entirely contained in $B_{2,s,N}$, have only $u$ or $v$ as points on the boundary of $B_{2,s,N}$, and their lengths are bounded from above by $r_2N - (\ell^\Lambda + 3)$.

Then we build two paths $\pi_{u_0,u^\Lambda}$ and $\pi_{v^\Lambda,v_0}$ respectively from $u_0$ to $u^\Lambda$ and from $v^\Lambda$ to $v_0$ contained in $B_\infty(sN, \ell^\Lambda+3) \setminus B_\infty(sN, \ell^\Lambda)$ except for $u^\Lambda$ and $v^\Lambda$, such that they do not have any vertex in common. By the definition of $K$, this implies that the sum of their lengths is bounded from above by $K$ (recall that $K$ is the number of edges in $B_\infty(0, \ell^\Lambda+3)$). To get these paths, assume first that $\|u_0-v^\Lambda\|_1 > 3$ or $\|v_0-u^\Lambda\|_1 > 3$. Assume that we have $\|v_0 - u^\Lambda\|_1 > 3$, the other case being the same. We begin by considering a path $\tilde{\pi}$ going in a shortest way from $v_0$ to a vertex of the boundary of $B_\infty(sN, \ell^\Lambda + 2)$, denoted by $v'_0$. This path has at most $d$ edges. Then, let $u^{\Lambda,0}$ be a vertex on the boundary of $B_\infty(sN, \ell^\Lambda + 3)$ such that $\|u^\Lambda - u^{\Lambda,0}\|_1 = 3$. We get $\pi_{u_0,u^\Lambda}$ by going from $u_0$ to $u^{\Lambda,0}$ in a shortest way on the boundary of $B_\infty(sN, \ell^\Lambda + 3)$ avoiding all vertices of $\tilde{\pi}$, and then by going from $u^{\Lambda,0}$ to $u^\Lambda$ by three steps. This is possible since $\|v_0 - u^\Lambda\|_1 > 3$. To get $\pi_{v_0,v^\Lambda}$, we begin by following $\tilde{\pi}$. Let $v^{\Lambda,0}$ be a vertex on the boundary of $B_\infty(sN, \ell^\Lambda + 2)$ such that $\|v^\Lambda - v^{\Lambda,0}\|_1 = 2$. Then, $\pi_{v_0,v^\Lambda}$ goes from $v'_0$ to $v^{\Lambda,0}$ in a shortest way on the boundary of $B_\infty(sN, \ell^\Lambda + 2)$ avoiding the unique vertex of $\pi_{u_0,v^\Lambda}$ belonging to $B_\infty(sN, \ell^\Lambda + 2)$. Finally, $\pi_{v_0,v^\Lambda}$ goes from $v^{\Lambda,0}$ to $v^\Lambda$ by two steps (see the left side of Figure 6 for an example of this construction in dimension 2).

Now, if $\|u_0 - v^\Lambda\|_1 = 3$ and $\|v_0 - u^\Lambda\|_1 = 3$, the construction has to be slightly different. From $u_0$, $\pi_{u_0,u^\Lambda}$ goes to a vertex $u_0''$ belonging to the boundary of $B_\infty(sN, \ell^\Lambda + 3)$ and such that $\|u_0'' - v_0\|_1 = 1$ in a shortest way on the boundary of $B_\infty(sN, \ell^\Lambda + 3)$. After, it makes one step to go to the boundary of $B_\infty(sN, \ell^\Lambda + 2)$ and goes to $u^\Lambda$ in a shortest way by taking only one vertex in $B_\infty(sN, \ell^\Lambda + 1)$. Then, $\pi_{v_0,v^\Lambda}$ goes on the boundary of $B_\infty(sN, \ell^\Lambda + 3)$ to a vertex $v_0''$ belonging to the boundary of $B_\infty(sN, \ell^\Lambda + 3)$ and such that $\|v_0'' - u_0\|_1 = 1$ by avoiding every vertex which belongs to $\pi_{u_0,u^\Lambda}$, and then makes two steps to go to the boundary of $B_\infty(sN, \ell^\Lambda + 1)$ and goes to $v^\Lambda$ in a shortest way (see the right side of Figure 6 for an example of this construction in dimension 2). In this case, we also have that the sum of their lengths is bounded from above by $K$.

Finally, $\pi$ is the path obtained by concatenating $\pi_{u,u_0}$, $\pi_{u_0,u^\Lambda}$, a path going from $u^\Lambda$ to $v^\Lambda$ in a shortest way for the norm $\|\cdot\|_1$, $\pi_{v^\Lambda,v_0}$ and $\pi_{v_0,v}$ in this order. We have that $\pi$ is a self-avoiding path contained in $B_{2,s,N}$ and has only $u$ and $v$ on the boundary of $B_{2,s,N}$.
<figure><img src="image_9.png" /><figcaption>Figure 6: Example of the construction of the portion of $\pi$ which is contained in $B_{\infty}(sN, \ell^{\Lambda} + 3) \setminus B_{\infty}(sN, \ell^{\Lambda})$ in dimension 2. On the left, this is an example of the case where $\|u_0 - v^{\Lambda}\|_1 > 3$ or $\|v_0 - u^{\Lambda}\|_1 > 3$ and on the left the other case.</figcaption></figure>

## B Overlapping pattern in the bounded case

*Proof of Lemma 3.1.* Recall that $\nu$ is fixed at the beginning of Section 3 and that $\delta' = \min\left(\frac{\delta}{8}, \frac{\delta}{1+d}\right)$. Then, we fix a positive real $\nu_0$ such that:

* $t_{\min} + \delta \le \nu_0 \le \nu \le t_{\max}$,

* the event $A^{\Lambda} \cap \{\forall e \in \Lambda, t_e \le \nu_0\}$ has a positive probability,

* $F([\nu_0, \nu]) > 0$.

Notice that, if $F$ has an atom, one could have $\nu_0 = \nu$, or even $\nu_0 = \nu = t_{\max}$. Then, fix

$$ \ell^{\Lambda} = \max(L_1, \dots, L_d), \qquad (B.1) $$

$$ \ell_1 > \frac{4d\ell^{\Lambda} \left( \nu_0 - t_{\min} - \frac{\delta'}{2} \right)}{\nu_0 - t_{\min} - \delta'}, \qquad (B.2) $$

$$ \text{and } \ell_0 > \frac{\ell^{\Lambda}((2d+1)\nu_0 + (2d-1)t_{\min} + 2d\delta') + \ell_1(\nu_0 + 3t_{\min} + 4\delta')}{\nu_0 - t_{\min} - 2\delta'} \qquad (B.3) $$

Fix also

$$ \delta'' < \min \left( \delta', \frac{\nu_0 - t_{\min}}{2d\ell_0} \right). \qquad (B.4) $$

Let $j \in \{1, \dots, d\}$. Let us construct the overlapping pattern in $\Lambda_0 = \{-\ell_0, \dots, \ell_0\}^d$ with endpoints $\ell_0\varepsilon_j$ and $-\ell_0\varepsilon_j$. We denote by $u_3$ and $v_3$ the endpoints of the original pattern. The first step is the construction of an oriented path going from the face of $\Lambda_0$ containing $\ell_0\varepsilon_j$ to the face containing $-\ell_0\varepsilon_j$ and visiting $u_3$ and $v_3$. We denote by $\Lambda_1$ the set $\prod_{i=1}^d \{-\ell_1, \dots, L_i + \ell_1\}$. Then we define $u_2$ (resp. $v_2$) the
<figure><img src="image_10.png" /><figcaption>Figure 7: Example of the construction of $\tilde{\pi}$ in an overlapping pattern in dimension 2.</figcaption></figure>

vertex of $\partial\Lambda_1$ which can be linked to $u_3$ (resp. $v_3$) by a path using exactly $\ell_1$ edges in only one direction (the direction of the external normal vector associated to $u_3$ (resp. $v_3$)). If $u_3$ or $v_3$ are associated to several external normal unit vectors, then the choice of the direction is not unique. We choose one external normal unit vector in an arbitrary way but we ensure that the two normal unit vectors chosen to build $u_2$ and $v_2$ are different. Note that this is possible since the pattern is valid (recall Definition 1.2). For a vertex $z \in \mathbb{Z}^d$, denote by $z(j)$ its $j$-th coordinate. Even if it means exchanging the roles of $u_3$ and $v_3$, we can assume that $u_2(j) \ge v_2(j)$. Then, we define $u_1 = u_2 + (\ell_0 - u_2(j))\varepsilon_j$ and $v_1 = v_2 - (\ell_0 + v_2(j))\varepsilon_j$. Note that $u_1$ (resp. $v_1$) belongs to the face of $\Lambda_0$ containing $\ell_0\varepsilon_j$ (resp. $-\ell_0\varepsilon_j$). We define a path $\tilde{\pi}$ going from $\ell_0\varepsilon_j$ to $u_1$ in a shortest way, then to $u_2$ in the shortest way, then to $u_3$ in the shortest way, then to $v_3$ in a shortest way, then to $v_2$ in the shortest way, then to $v_1$ in the shortest way and to $v_0$ in a shortest way. Note that $\tilde{\pi}_{u_1,v_1}$ is an oriented path. Indeed, $\tilde{\pi}_{u_3,v_3}$ is an oriented path. Extending it outside $\Lambda$ following the direction of an external normal unit vector preserves the fact that it is oriented. Thus $\tilde{\pi}_{u_2,v_2}$ is an oriented path. Then, we assume that $u_2(j) \ge v_2(j)$ on purpose to guarantee that, with the definitions of $u_1$ and $v_1$, the path $\tilde{\pi}_{u_1,v_1}$ remains an oriented path.

The event (whose probability is positive) of the overlapping pattern, denoted by $A_j^{\Lambda_0}$ is the following:

* for all $e \in \tilde{\pi}_{\ell_0\varepsilon_j, u_3}$ and $e \in \tilde{\pi}_{v_3, -\ell_0\varepsilon_j}$, $T(e) < t_{\min} + \delta''$,

* the event $A^{\Lambda} \cap \{\forall e \in \Lambda, T(e) \le \nu_0\}$ is realized,

* for all $e$ in $\Lambda_0 \setminus (\tilde{\pi} \cup \Lambda)$, $\nu_0 \le T(e) \le \nu$.

On this event, let $\bar{\gamma}$ be one of the fastest path from $\ell_0\varepsilon_j$ to $-\ell_0\varepsilon_j$ among the path entirely contained in $\Lambda_0$ and let us show that $\bar{\gamma}$ visits $u_3$ and $v_3$ and that $\bar{\gamma}_{u_3,v_3}$ is entirely contained in $\Lambda$. We proceed by proving successive properties.

* There exist one vertex $a_0$ of $\tilde{\pi}_{u_1,u_2}$ and one vertex $b_0$ of $\tilde{\pi}_{v_2,v_1}$ visited by $\bar{\gamma}$. Further, $\bar{\gamma}_{\ell_0\varepsilon_j,a_0} = \tilde{\pi}_{\ell_0\varepsilon_j,a_0}$ and $\bar{\gamma}_{b_0,-\ell_0\varepsilon_j} = \tilde{\pi}_{b_0,-\ell_0\varepsilon_j}$.

Let us assume that $\bar{\gamma}$ does not visit any vertex of $\tilde{\pi}_{u_1,u_2}$, the other case being the same. The path $\bar{\gamma}$ has to take at least $\ell_0 - \ell^{\Lambda} - \ell_1$ edges connecting vertices such that at least one of them has its
j-th coordinate strictly between $\ell^\Lambda + \ell_1$ and $\ell_0$. The only edges in this set whose passage time is smaller than $\nu_0$ are those of $\tilde{\pi}_{u_1,u_2}$. Hence

$$T(\bar{\gamma}) \geq (\ell_0 - \ell^\Lambda - \ell_1)\nu_0 + (\ell_0 + \ell^\Lambda + \ell_1)t_{\min}.$$

But, thanks to our construction, we have

$$T(\tilde{\pi}) \leq \underbrace{T(\tilde{\pi}_{\ell_0\varepsilon_j, u_1}) + T(\tilde{\pi}_{v_1, -\ell_0\varepsilon_j})}_{\leq 2d\ell^\Lambda + 2\ell_1}(t_{\min} + \delta'') + \underbrace{T(\tilde{\pi}_{u_1, u_2}) + T(\tilde{\pi}_{v_2, v_1})}_{\leq 2\ell_0}(t_{\min} + \delta'') + \underbrace{T(\tilde{\pi}_{u_2, u_3}) + T(\tilde{\pi}_{v_3, v_2})}_{\leq 2\ell_1}(t_{\min} + \delta'') + \underbrace{T(\tilde{\pi}_{u_3, v_3})}_{\leq 2d\ell^\Lambda\nu_0} \\ \leq 2(d\ell^\Lambda + 2\ell_1 + \ell_0)(t_{\min} + \delta') + 2d\ell^\Lambda\nu_0 \quad \text{since } \delta'' < \delta'$$

So, (B.3) leads to $T(\tilde{\pi}) < T(\bar{\gamma})$, which is impossible.

To prove that $\bar{\gamma}_{\ell_0\varepsilon_j, a_0} = \tilde{\pi}_{\ell_0\varepsilon_j, a_0}$, we use the fact that by the construction, if $\bar{\gamma}_{\ell_0\varepsilon_j, a_0} \neq \tilde{\pi}_{\ell_0\varepsilon_j, a_0}$, $\bar{\gamma}_{\ell_0\varepsilon_j, a_0}$ has to take at least one edge whose time is greater than or equal to $\nu_0$. Hence,

$$T(\bar{\gamma}_{\ell_0\varepsilon_j, a_0}) \geq \nu_0 + (\|\ell_0\varepsilon_j - a_0\|_1 - 1)t_{\min},$$

although

$$T(\tilde{\pi}_{\ell_0\varepsilon_j, a_0}) \leq \|\ell_0\varepsilon_j - a_0\|_1(t_{\min} + \delta'').$$

Since $\|\ell_0\varepsilon_j - a_0\|_1 \leq 2d\ell_0$, (B.4) leads to $T(\tilde{\pi}_{\ell_0\varepsilon_j, a_0}) < T(\bar{\gamma}_{\ell_0\varepsilon_j, a_0})$, which is impossible since $\bar{\gamma}$ is an optimal path.

* If $a_1$ (resp. $b_1$) is a vertex of $\tilde{\pi}_{u_2,u_3}$ (resp. $\tilde{\pi}_{v_3,v_2}$) visited by $\bar{\gamma}$, then $\bar{\gamma}_{\ell_0\varepsilon_j, a_1} = \tilde{\pi}_{\ell_0\varepsilon_j, a_1}$ (resp. $\bar{\gamma}_{b_1, -\ell_0\varepsilon_j} = \tilde{\pi}_{b_1, -\ell_0\varepsilon_j}$).

Indeed, let $a_1$ be such a vertex and let $a_0$ be the vertex of the preceding property. We only have to prove that $\bar{\gamma}_{a_0, a_1} = \tilde{\pi}_{a_0, a_1}$ and the proof is the same as the one for $\bar{\gamma}_{\ell_0\varepsilon_j, a_0} = \tilde{\pi}_{\ell_0\varepsilon_j, a_0}$.

Among the vertices visited by $\bar{\gamma}$, we denote by $a$ (resp. $b$) the last vertex of $\tilde{\pi}_{\ell_0\varepsilon_j, u_3}$ (resp. the first vertex of $\tilde{\pi}_{v_3, -\ell_0\varepsilon_j}$). Then, $\bar{\gamma}_{a,b}$ does not visit any vertex of $\tilde{\pi}_{\ell_0\varepsilon_j, u_3} \cup \tilde{\pi}_{v_3, -\ell_0\varepsilon_j}$ (except $a$ and $b$). Indeed, by the two properties above, we have that $\bar{\gamma}_{\ell_0\varepsilon_j, a} = \tilde{\pi}_{\ell_0\varepsilon_j, a}$ and $\bar{\gamma}_{b, -\ell_0\varepsilon_j} = \tilde{\pi}_{b, -\ell_0\varepsilon_j}$ and $\bar{\gamma}_{a,b}$ can not visit a vertex of $\tilde{\pi}_{a,u_3} \cup \tilde{\pi}_{v_3,b}$ thanks to the definition of $a$ and $b$.

* The vertex $a$ (resp. $b$) belongs to $\tilde{\pi}_{u_2,u_3}$ (resp. $\tilde{\pi}_{v_3,v_2}$).

Assume that $a$ or $b$ does not satisfy this property. Then $\|a - u_3\|_1 \geq \ell_1$ or $\|b - v_3\|_1 \geq \ell_1$. Since $\tilde{\pi}_{a,b}$ is oriented and since $\|u_3 - v_3\|_1 \leq 2d\ell^\Lambda$,

$$T(\tilde{\pi}_{a,b}) \leq (\|a - b\|_1 - 2d\ell^\Lambda)(t_{\min} + \delta'') + 2d\ell^\Lambda\nu_0 \leq (\|a - b\|_1 - 2d\ell^\Lambda)(t_{\min} + \delta') + 2d\ell^\Lambda\nu_0.$$

Then, since the edges whose time is smaller than $\nu_0$ taken by $\bar{\gamma}_{a,b}$ are those in $\Lambda$,

$$T(\bar{\gamma}_{a,b}) \geq (\|a - b\|_1 - 2d\ell^\Lambda)\nu_0 + 2d\ell^\Lambda t_{\min}.$$

Using (B.2), we get $T(\bar{\gamma}_{a,b}) > T(\tilde{\pi}_{a,b})$, which is impossible.

* We have that $a = u_3$ and $b = v_3$.

Assume that $a \neq u_3$, the other case being the same. We have

$$T(\tilde{\pi}_{a,b}) \leq (\|a - b\|_1 - \|u_3 - v_3\|_1)(t_{\min} + \delta') + \|u_3 - v_3\|_1\nu_0,$$

and thus $\bar{\gamma}_{a,b}$ takes at least one edge of $\Lambda$ otherwise $T(\bar{\gamma}_{a,b}) \geq \|a - b\|_1\nu_0 > T(\tilde{\pi}_{a,b})$ since $\|a - b\|_1 - \|u_3 - v_3\|_1 > 0$. Let $u_0$ be the first entry point of $\bar{\gamma}_{a,b}$ in $\Lambda$ and let us consider the path $\pi$ following $\tilde{\pi}_{a,u_3}$, then going from $u_3$ to $u_0$ in a shortest way and then following $\bar{\gamma}_{u_0,b}$. Then, the number of edges of $\pi_{a,u_0}$ is lower than or equal to the number of edges of $\bar{\gamma}_{a,u_0}$, for all $e \in \pi_{a,u_0}$, $T(e) \leq \nu_0$, there exists $e' \in \pi_{a,u_0}$ such that $T(e') \leq t_{\min} + \delta'$ and for all $e \in \bar{\gamma}_{a,u_0}$, $T(e) \geq \nu_0$. So, we have $T(\pi) < T(\bar{\gamma}_{a,b})$ which is impossible since $\bar{\gamma}$ is an optimal path among paths entirely contained in $\Lambda_0$.
• $\bar{\gamma}_{a,b}$ takes the original pattern.

Assume that $\bar{\gamma}_{a,b}$ is not entirely contained in $\Lambda$. Let $v_0$ be the first exit point from $\Lambda$ of $\bar{\gamma}_{a,b}$ and $u_0$ the first entry point after $v_0$. Let us consider the shortcut $\pi$ going from $v_0$ to $u_0$ in a shortest way. Then, using the same argument as in the proof of Lemma 3.21, we have that $\bar{\gamma}_{v_0,u_0}$ has strictly more edges than $\pi$. Furthermore, all edges of $\bar{\gamma}_{v_0,u_0}$ have a time greater than or equal to $v_0$ although all edges of $\pi$ have a time lower than or equal to $v_0$. So, $T(\pi) < T(\bar{\gamma}_{v_0,u_0})$, which is impossible since $\bar{\gamma}$ is an optimal path among paths entirely contained in $\Lambda_0$. Since $\bar{\gamma}_{a,b}$ is a path entirely contained in $\Lambda$, going from $u_3$ to $v_3$ and with an optimal time, so we have the result.

□

## References

[1] Enrique D. Andjel and Maria E. Vares. First passage percolation and escape strategies. *Random Structures and Algorithms*, 47(3):414–423, October 2015.

[2] A. Auffinger, M. Damron, and J. Hanson. *50 years of first-passage percolation*. American Mathematical Society, 2017.

[3] S. Boucheron, G. Lugosi, and P. Massart. *Concentration Inequalities: A Nonasymptotic Theory of Independence*. OUP Oxford, 2013.

[4] Geoffrey Grimmett. *Percolation*, volume 321 of *Grundlehren der Mathematischen Wissenschaften* [*Fundamental Principles of Mathematical Sciences*]. Springer-Verlag, Berlin, second edition, 1999.

[5] Arjun Krishnan, Firas Rassoul-Agha, and Timo Seppäläinen. Geodesic length and shifted weights in first-passage percolation. *arXiv preprint arXiv:2101.12324*, 2021.

[6] T. M. Liggett, R. H. Schonmann, and A. M. Stacey. Domination by product measures. *The Annals of Probability*, 25(1):71–95, 1997.

[7] Shuta Nakajima. On properties of optimal paths in first-passage percolation. *Journal of Statistical Physics*, 174(2):259–275, Oct 2018.

[8] J. van den Berg and H. Kesten. Inequalities for the Time Constant in First-Passage Percolation. *The Annals of Applied Probability*, 3(1):56–80, 1993.