<figure><img src="image_1.png" /></figure>

HAL
open science

# Enumeration of walks in multidimensional orthants and reflection groups

Léa Gohier, Emmanuel Humbert, Kilian Raschel

<figure><img src="image_2.png" /></figure>

## To cite this version:

Léa Gohier, Emmanuel Humbert, Kilian Raschel. Enumeration of walks in multidimensional orthants and reflection groups. 2025. hal-04881884

HAL Id: hal-04881884

https://hal.science/hal-04881884v1

Preprint submitted on 13 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# ENUMERATION OF WALKS IN MULTIDIMENSIONAL ORTHANTS AND REFLECTION GROUPS

LÉA GOHIER, EMMANUEL HUMBERT, AND KILIAN RASCHEL

**ABSTRACT.** We consider (random) walks in a multidimensional orthant. Using the idea of universality in probability theory, one can associate a unique polyhedral domain to any given walk model. We use this connection to prove two sets of new results. First, we are interested in a group of transformations naturally associated with any small step model; as it turns out, this group is central to the classification of walk models. We show a strong connection between this group and the reflection group through the walls of the polyhedral domain. As a consequence, we can derive various conditions for the combinatorial group to be infinite. Secondly, we consider the asymptotics of the number of excursions, whose critical exponent is known to be computable in terms of the eigenvalue of the above polyhedral domain. We prove new results from spectral theory on the eigenvalues of polyhedral nodal domains. We believe that these results are interesting in their own right; they can also be used to find new exact asymptotic results for walk models corresponding to these nodal polyhedral domains.

## 1. INTRODUCTION AND MAIN RESULTS

**Lattice walks in multidimensional orthants.** A lattice walk is a sequence of points $P_0, P_1, \dots, P_n$ of $\mathbb{Z}^d, d \ge 1$. The points $P_0$ and $P_n$ are its starting and end points, respectively, the consecutive differences $P_{i+1} - P_i$ its steps, and $n$ is its length. Given a set $S \subset \mathbb{Z}^d$, called the step set, a set $C \subset \mathbb{Z}^d$ called the domain (which in this paper will systematically be the cone $\mathbb{R}_+^d$, called the $d$-dimensional orthant), and elements $P$ and $Q$ of $C$, we are interested in the number

$$e_C(P, Q; n)$$

of (possibly weighted) walks (or excursions) of length $n$ that start at $P = P_0$, have all their steps in $S$, have all their points in $C$, and end at $Q = P_n$. See Figure 1. Normalising the weights with the condition that they sum to one, we obtain transition probabilities, and the number $e_C(P, Q; n)$ can be interpreted as the probability that a random walk starting at $P$ will reach the point $Q$ at time $n$ while remaining in the domain $C$.

In the last twenty years, there has been a dense research activity in the mathematical community on the enumerative aspects of walks confined to cones, in particular to the $d$-dimensional orthant. To summarise, three main questions have attracted most attention: the first is to determine, if possible, a closed-form formula for the number of walks $e_C(P, Q; n)$. Of course, such an explicit formula is not expected to exist in general, and in most cases can be explained by bijections with other combinatorial objects. The second question concerns the asymptotic behaviour, e.g. of the number of excursions $e_C(P, Q; n)$, in the regime where the length $n \to \infty$, while the start and end

<footnote>Date: January 10, 2025.</footnote>

<footnote n="2020">2020 Mathematics Subject Classification. 05A15; 05A16; 20F55; 47A75; 60F05.</footnote>

<footnote>Key words and phrases. Enumeration of walks in multidimensional orthants; Asymptotic enumeration; Reflection groups; Coxeter groups; Dirichlet eigenvalue; Nodal domain.</footnote>
<figure><img src="image_4.png" /><figcaption>FIGURE 1. Walks in orthants $\mathbb{R}_+^d$ in small dimensions $d = 1, 2, 3$</figcaption></figure>

points remain fixed: as we will see later, in general one has

$$e_C(P, Q; n) \sim c(P, Q) \frac{\rho^n}{n^\alpha}, \qquad (1)$$

for some quantities $c, \rho, \alpha$ depending on the model; $\rho$ is called the structural constant, it describes the exponential growth of the number of excursions, while $\alpha$ is called the critical exponent. The last question would focus more on the complexity of generating functions associated with these models, such as the excursion series

$$\sum_{n \ge 0} e_C(P, Q; n) t^n. \qquad (2)$$

One would then ask whether the last power series satisfies any algebraic or differential equation. The answer to the last problem may allow us to classify the models according to the complexity of their generating function, and is further related to the first two questions.

Historically, these questions were first addressed for one-dimensional models. In this case, the model is that of walks on the positive half-line, which has a long tradition in the probabilistic community [6] and also in the combinatorial community [2]. Note that in dimension one, walks with bounded jumps admit algebraic generating functions [2]; we can thus systematically solve the three questions mentioned above. The case of dimension two gives rise to the model of walks in the quarter plane, which has been studied intensively, see [11, 9, 20] and references therein. The variety of possible behaviours and answers to the three questions is much richer than in dimension one; however, a combination of techniques from different fields (probability [9, 17], complex analysis [23], analytic combinatorics in several variables [11, 35, 36], Galois theory of difference equations [20], etc.) eventually lead to a deep understanding of this class of models, at least in the case of small steps (this hypothesis means that the walk can only go to neighbours at $\ell^\infty$-distance one). Walk models in higher dimension $d \ge 3$ have been less studied. The variety of behaviours seems to increase dramatically with dimension, and exactly solvable models become an exception. See the recent papers [8, 21, 28, 7, 26] for properties of three-dimensional models and [12] for an approach in dimension four. In higher dimensions, some models are equivalent to non-intersecting paths [19, 32, 24, 25], which are well understood and studied in both the combinatorial and physics literature.

**Focus on two important tools.** In order to present the main results of this paper, we recall two different tools that are of crucial interest in obtaining some of the previous results in the literature. The first is a group introduced in dimension two in the combinatorial context in [11], following the idea of Fayolle, Iasnogorodski and Malyshev in [23], see also [33]. This group will be properly defined
<figure><img src="image_5.png" /><figcaption>FIGURE 2. The orthant $\mathbb{R}_+$ is mapped into the polyhedral domain (or pyramid) (4), which depends on the model (illustration in dimension two and three). In the new domain, the model has a covariance matrix equal to the identity.</figcaption></figure>

later in the paper (see Section 2, in particular (6)), but can be presented informally as follows. It is a symmetry group of involutions defined by the steps of the model $\mathcal{S}$. The main application is that, if it is finite, its action on a functional equation naturally associated with the model can lead to explicit expressions for the generating functions (2) (with some further information on the asymptotics (1) and algebraic complexity). In principle, this method works in dimension two [23, 11] and higher [8, 40, 12]. However, there is no criterion to decide whether the group is finite (even in dimension two), nor any interpretation of the group using more classical groups.

The second tool comes from probability theory and is the asymptotics written in (1), originally derived in [17, Eq. (12)], where the prefactor $c(P, Q)$ depends on the start and end points (and can be interpreted as a discrete harmonic function), the structural constant $\rho$ is easily computed in terms of the parameters, see (12), and the critical exponent is computed by Denisov and Wachtel in [17]:

$$ \alpha = 1 + \sqrt{\lambda_1 + \left(\frac{d}{2} - 1\right)^2}, \qquad (3) $$

where $\lambda_1$ is the principal eigenvalue for a Dirichlet problem on a subdomain of the sphere $\mathbb{S}^{d-1}$, see our Theorem 1 for a more precise statement. See [15, 3] for probabilistic references where the exponent (3) appears in the context of Brownian motion in cones; see also [39]. While the formula (3) characterises the critical exponent in (1), it is not clear a priori for which walk models $\lambda_1$ can be computed in closed form.

**A polyhedral domain depending on the walk model.** In this paper we introduce a new idea, based on reflection groups and more generally Coxeter groups, to study at once the combinatorial group and the critical exponent mentioned above. The main tool is to transform the orthant $\mathbb{R}_+$, which is the natural confinement domain of the walk (see again Figure 1), into another polyhedral domain obtained as a linear transformation of the orthant, see Figure 2. More precisely, the new domain is

$$ \Delta^{-\frac{1}{2}} \mathbb{R}_+^d, \qquad (4) $$

where the linear map $\Delta$ allowing this transformation is canonical and given by the idea of universality in probability theory, as we now explain.

For a given model $\mathcal{S}$, if $w(s)$ denotes the weight of the step $s = (s_1, \dots, s_d) \in \mathcal{S}$, the drift is defined as the vector $\sum_{s \in \mathcal{S}} w(s)s$ and the covariance matrix is the $d \times d$ matrix with coefficients $\sum_{s \in \mathcal{S}} w(s)s_i s_j$. A generic walk model will have a non-zero drift and a covariance different from
the identity. It is then natural to perform an exponential transformation of the weights to remove
the drift and transform the covariance matrix into the identity matrix. This change of measure is
classical in probability theory and is known as the Cramér transformation (it will be recalled in
Section 2, see (13)). In this way, the new random walk is in the region of attraction of a standard
Brownian motion, and various universal limit theorems can be applied, in particular the results of
Denisov and Wachtel [17].

If we denote by $\Delta$ the covariance matrix of the new random walk $(Y_n)_{n\ge0}$ after changing the transition probabilities, the modified random walk $(\Delta^{-\frac{1}{2}}Y_n)_{n\ge0}$ has identity covariance matrix. The counterpart is that the confinement domain of the process is no longer the orthant $\mathbb{R}_+^d$ but the polyhedral domain (4), which appears naturally in this way. See Section 2, in particular equation (13), for mode details of this construction.

**Main results.** Given the polyhedral domain (4) it is natural to ask two main questions. First, one
can define the reflection group $H$ spanned by the reflections through the sides of the domain, and
ask how this group compares to the natural combinatorial group $G$ mentioned above. This question
is at the origin of our first set of results (Part 1 of the paper).

In Theorem **5** and Corollary **6** we construct a surjective morphism $G \to H$ which sends the set of generators of $G$ to the set of generators of $H$. This clarifies the connection between the group $G$ and $H$, and also between $G$ and Coxeter groups. A direct consequence (Corollary **7**) is that if $H$ is infinite, then $G$ should also be infinite. More generally, our results extend and simplify the strategy developed in [11, 21, 28] to prove that some models $S$ admit an infinite group $G$ in dimension two and three (which is based on showing that the order of the composition of two generators of $G$ is infinite). In our case, since the composition of two reflections is simply a rotation of the angle twice the angle between two boundary hyperplanes of the polyhedral domain, its order can be read directly from the covariance matrix. Another relevant remark is that $H$ is a reflection group and thus a Coxeter group. If it is finite, it must belong to a short list of known examples (see e.g. [27]), and thus it suffices to exclude these cases to prove that $H$ (and thus $G$) is infinite. See Section **4** for more details and various examples.

The second set of results (Part 2 of this paper) concerns the critical exponent $\alpha$ in (1), or equivalently the principal eigenvalue $\lambda_1$. There are basically two ways to compute $\alpha$. In some cases there is an explicit expression for the number $e_C(P, Q; n)$ (or for the associated generating function (2)), which can be analysed asymptotically. See for example [11, 8] for such calculations. However, this is very rare and is related to bijections with other combinatorial models or obtained by delicate combinatorial manipulations. Forgetting any combinatorial interpretation of the numbers $e_C(P, Q; n)$, the second approach would be to study the quantity $\lambda_1$ directly from a geometric perspective. In dimension two one can fully compute the eigenvalue $\lambda_1$, which is given by $(\frac{\pi}{\arccos(-a)})^2$, where $a$ is a correlation coefficient, which can be computed starting from the parameters. See Example 2 in [17] and [9] for detailed computations in dimension two. In dimension $d \ge 3$ there is no hope of finding such a general formula for $\lambda_1$. This is illustrated in [7] in dimension three, where $\lambda_1$ is characterised as the first eigenvalue of spherical triangles, which is generally not computable in closed form. The only exceptions are triangles belonging to a small list of examples given in [4] and [5, Sec. 3], which correspond to certain crystallographic groups. In these cases it is possible to calculate the principal eigenvalue and in fact the whole spectrum.
Surprisingly, Bérard and Besson's works [4, 5] have not been extended to the case of arbitrary dimension (although a list of relevant domains is proposed in [14] in dimension four). This is the main result of our second part, see Theorem 14. More precisely:

* We compute the Dirichlet eigenvalue $\lambda_1$ of polyhedral domains (in the sense of (4)) which are also nodal domains of $\mathbb{S}^{d-1}$, i.e. for which there exists $\phi \in C^\infty(\mathbb{S}^{d-1})$ such that $\phi$ is an eigenfunction of the Laplacian satisfying $\phi > 0$ on the domain and $\phi = 0$ on the boundary. This part of the statement in Theorem 14 is exactly the $d$-dimensional generalisation of [4, 5]. The main technical novelty is that we find an expression for the eigenfunction which makes possible the computation of $\lambda_1$ in all dimensions.

* We classify all such domains. We show that they must be the intersection of a chamber of a finite Coxeter group with $\mathbb{S}^{d-1}$.

This provides new examples of walk models, in any dimension, for which one can compute the asymptotics (1).

## Part 1. The combinatorial group as a reflection group

The first part consists of three sections. First, in Section 2, we introduce our notation and recall some details about the connection between the asymptotics of the excursion and the eigenvalue $\lambda_1$. Section 3 contains our main theoretical results, in particular Theorem 5 and Corollary 6 on the surjective morphism $G \to H$. Finally, in Section 4 we propose various applications of our results, giving several examples and techniques to prove that $G$ is infinite or to show that $G$ and $H$ are isomorphic.

## 2. PRELIMINARY NOTATIONS AND RESULTS

### 2.1. Assumptions on the step set.
Define the inventory of the model $\mathcal{S}$ as follows:

$$ \chi_S(x_1, \dots, x_d) = \sum_{(i_1, \dots, i_d) \in \mathcal{S}} w(i_1, \dots, i_d) x_1^{i_1} \dots x_d^{i_d}, \qquad (5) $$

where $w(i_1, \dots, i_d) > 0$ is the weight of the step $(i_1, \dots, i_d) \in \mathcal{S}$. We will normalize the weights in such a way that $\chi_S(1, \dots, 1) = 1$, so that they are also transition probabilities. Most of the time we shall assume that the step set satisfies the following irreducibility assumption:

(H1) For any two points $P, Q$ in the domain $C$, the set $\{n \in \mathbb{N} : e_C(P, Q; n) \neq 0\}$ is non-empty, with $\mathbb{N} = \{1, 2, \dots\}$.

As a consequence of (H1), the walk can visit any point in the domain $C$, independent of its starting point.

### 2.2. The group of the model.
This group was first introduced in the context of two-dimensional walks [33, 23, 11] and turns out to be very useful. Let $\chi_S$ be the inventory (5). Introduce the notation

$$ \begin{aligned} \chi_S(x_1, \dots, x_d) &= x_1 A_1(x_2, \dots, x_d) + B_1(x_2, \dots, x_d) + \bar{x}_1 C_1(x_2, \dots, x_d) \\ &= x_2 A_2(x_1, x_3, \dots, x_d) + B_2(x_1, x_3, \dots, x_d) + \bar{x}_2 C_2(x_1, x_3, \dots, x_d) \\ &= \dots \\ &= x_d A_d(x_1, \dots, x_{d-1}) + B_d(x_1, \dots, x_{d-1}) + \bar{x}_d C_d(x_1, \dots, x_{d-1}), \end{aligned} $$
where $\bar{x}_i = \frac{1}{x_i}$. Under the assumption (H1), the step set has a positive step in each direction and $A_1, \dots, A_d$ are all non-zero. By definition, the group of $S$ is the group

$$G = \langle \varphi_1, \dots, \varphi_d \rangle \qquad (6)$$

of birational transformations of the variables $[x_1, \dots, x_d]$ generated by the following involutions:

$$ \left\{ \begin{array}{l} \varphi_1([x_1, \dots, x_d]) = \left[ \bar{x}_1 \frac{C_1(x_2, \dots, x_d)}{A_1(x_2, \dots, x_d)}, x_2, \dots, x_d \right], \\ \varphi_2([x_1, \dots, x_d]) = \left[ x_1, \bar{x}_2 \frac{C_2(x_1, x_3, \dots, x_d)}{A_2(x_1, x_3, \dots, x_d)}, x_3, \dots, x_d \right], \\ \dots \\ \varphi_d([x_1, \dots, x_d]) = \left[ x_1, \dots, x_{d-1}, \bar{x}_d \frac{C_d(x_1, \dots, x_{d-1})}{A_d(x_1, \dots, x_{d-1})} \right]. \end{array} \right. \qquad (7) $$

The generators of the group $G$ therefore satisfy the relations $\varphi_1^2 = \dots = \varphi_d^2 = \text{Id}$, plus possible other relations, depending on the model.

**2.3. Probabilistic estimates.** We need to introduce the following quantity. Given a cone $T$ in $\mathbb{R}^d$ (which in our case will be a polytope, or pyramid, defined by an intersection of $d$ linear half-spaces, see for example (11)), we define $\lambda_1$ as the smallest eigenvalue $\Lambda$ of the Dirichlet problem for the Laplace-Beltrami operator $\Delta_{S^{d-1}}$ on the sphere $S^{d-1} \subset \mathbb{R}^d$

$$ \left\{ \begin{array}{ll} -\Delta_{S^{d-1}} m = \Lambda m & \text{in } T \cap S^{d-1}, \\ m = 0 & \text{in } \partial(T \cap S^{d-1}). \end{array} \right. \qquad (8) $$

See the book [13] for general properties of the eigenvalues of the above Dirichlet problem.

**Theorem 1 ([17, 18]).** Let $S$ be a step set satisfying (H1), and let $\chi_S$ be its inventory (5). The system of equations

$$ \frac{\partial \chi_S}{\partial x_1} = \dots = \frac{\partial \chi_S}{\partial x_d} = 0 \qquad (9) $$

admits a unique solution in $(0, \infty)^d$, denoted by $\mathbf{x}_0$. Define the covariance matrix

$$ \Delta = (a_{i,j})_{1 \le i,j \le d}, \quad \text{with } a_{i,j} = \frac{\frac{\partial^2 \chi_S}{\partial x_i \partial x_j}(\mathbf{x}_0)}{\sqrt{\frac{\partial^2 \chi_S}{\partial x_i^2}(\mathbf{x}_0) \cdot \frac{\partial^2 \chi_S}{\partial x_j^2}(\mathbf{x}_0)}}. \qquad (10) $$

Let $\Delta^{-\frac{1}{2}}$ denote the inverse of the symmetric, positive definite square root of the covariance matrix $\Delta$, see (14). Consider the $d$-dimensional polytope

$$ T = \Delta^{-\frac{1}{2}} \mathbb{R}_+^d. \qquad (11) $$

Let $\lambda_1$ be the smallest eigenvalue of the Dirichlet problem (8). Then for all $P, Q \in \mathbb{N}_0^d$ and $n$ such that $e_C(P, Q; n) \neq 0$, the asymptotics (1) of the number of excursions going from $P$ to $Q$ holds, where

$$ \rho = \min_{(0,\infty)^d} \chi_S \qquad (12) $$

and the critical exponent $\alpha$ in (1) is given by (3), namely $\alpha = 1 + \sqrt{\lambda_1 + \left(\frac{d}{2} - 1\right)^2}$.

The condition $e_C(P, Q; n) \neq 0$ can be easily understood by thinking about periodic random walks, for example the simple walk

$$ \chi_S(x_1, \dots, x_d) = x_1 + \bar{x}_1 + \dots + x_d + \bar{x}_d, $$
see our Examples 11 and 12, which can only return to its starting point in an even number of steps. Theorem 1 was actually first proved under the following stronger aperiodicity property:

(H2) For any two points P, Q in the domain C, the gcd of the set {$n \in \mathbb{N} : e_C(P, Q; n) \neq 0$} is 1. However, it was later proved [18] that the same asymptotic results hold only under (H1).

2.4. **Four random walks.** To be complete and to interpret the above Theorem 1, let us define four random walks that are naturally associated with any walk model $\mathcal{S}$. A similar discussion is proposed in dimension 2 in [9, Sec. 2.3]. First, the main random walk associated with the step set $\mathcal{S}$ and weight $w(s)$ is denoted by $(W_n)_{n \ge 0}$. By definition, for all $s \in \mathcal{S}$ and $n \ge 0$, $\mathbb{P}(W_{n+1} - W_n = s) = w(s)$. With $\chi_{\mathcal{S}}$ as in (5), it has a (possibly non-zero) drift given by $\nabla \chi_{\mathcal{S}}(\mathbf{1}) = \sum_{s \in \mathcal{S}} w(s)s$ and a covariance matrix given by

$$ \left( \frac{\partial^2 \chi_{\mathcal{S}}}{\partial x_i \partial x_j}(\mathbf{1}) \right)_{1 \le i,j \le d} . $$

The second random walk model appears when the drift of the model is removed; it is the Cramér transformation, as mentioned in the introduction. It is denoted by $(X_n)_{n \ge 0}$, has jumps in $\mathcal{S}$ and transitions

$$ \mathbb{P}(X_{n+1} - X_n = s) = \frac{w(s)\mathbf{x}_0^s}{\chi_{\mathcal{S}}(\mathbf{x}_0)}, \quad (13) $$

with the multi-index notation $s = (s_1, \dots, s_d) \in \mathbb{Z}^d$ and $\mathbf{x}_0$ solving the system (9). It has zero drift and covariance matrix given by

$$ \left( \frac{\frac{\partial^2 \chi_{\mathcal{S}}}{\partial x_i \partial x_j}(\mathbf{x}_0)}{\chi_{\mathcal{S}}(\mathbf{x}_0)} \right)_{1 \le i,j \le d} . $$

If the initial random walk $(W_n)_{n \ge 0}$ has zero drift, then $\mathbf{x}_0 = \mathbf{1}$ and the first step becomes unnecessary: $X_n = W_n$.

The third model, denoted $(Y_n)_{n \ge 0}$, is a normalised version of $(X_n)_{n \ge 0} = (X_n^1, \dots, X_n^d)_{n \ge 0}$ so as to have a covariance matrix with unit diagonal coefficients; it is defined by

$$ Y_n = \left( \frac{X_n^1}{\sqrt{\mathbb{E}((X_n^1)^2)}}, \dots, \frac{X_n^d}{\sqrt{\mathbb{E}((X_n^d)^2)}} \right). $$

It has zero drift and, by construction, a covariance matrix given by $\Delta$ in (10).

Finally, the random walk $(Z_n)_{n \ge 0} = (\Delta^{-\frac{1}{2}} Y_n)_{n \ge 0}$ has zero drift and an identity covariance matrix. Unlike the random walks $(W_n)_{n \ge 0}$, $(X_n)_{n \ge 0}$ and $(Y_n)_{n \ge 0}$, which all evolve in the orthant $\mathbb{R}_+^d$, the domain of definition of $(Z_n)_{n \ge 0}$ is $\Delta^{-\frac{1}{2}} \mathbb{R}_+^d$ as in (4).

### 3. A SURJECTIVE MORPHISM FROM THE COMBINATORIAL GROUP TO A REFLECTION GROUP

3.1. **Preliminary results.** Our first result (Proposition 3) is a reformulation of the covariance matrix given by (10) in terms of the cosine of certain angles. Our result is general and holds with general matrices; however, in our application we will systematically take the covariance matrix $\Delta$ as in (10).

In the whole paper, we denote the canonical basis of $\mathbb{R}^d$ by $(e_i)_{1 \le i \le d}$ and $\langle \cdot, \cdot \rangle$ will stand to the scalar product on $\mathbb{R}^d$. We consider a matrix $\Delta = (a_{i,j})_{1 \le i,j \le d}$ which is symmetric, positive definite and has diagonal coefficients equal to 1. The matrix $\Delta$ is diagonalisable in an orthonormal basis.
We denote by $P \in O(d)$ and $D = \text{diag}(\alpha_1, \dots, \alpha_d)$, where for all $i$, $\alpha_i > 0$, the matrices such that
$\Delta = PDP^{-1}$. We can then define, for any $s \in \mathbb{R}$, the matrix

$$
\Delta^s = P \operatorname{diag}(\alpha_1^s, \dots, \alpha_d^s) P^{-1}. \tag{14}
$$

In particular, the matrix $\Delta^{-1/2}$ appearing in Theorem 1 is computed thanks to (14) at $s = -1/2$.
The orthant $\mathbb{R}_+^d$ is bounded by the hyperplanes

$$
G_i = \operatorname{Span}\{e_1, \dots, e_{i-1}, e_{i+1}, \dots, e_d\}, \quad i \in \{1, \dots, d\}, \qquad (15)
$$

and thus $T$ in (11) is bounded by the hyperplanes $H_i = \Delta^{-1/2} G_i$. We set

$$
u_i = \Delta^{\frac{1}{2}} e_i, \tag{16}
$$

A first observation is:

**Lemma 2.** Let $u_i$ be defined in (16). It holds that

$$
H_i = \langle u_i \rangle^{\perp}. \tag{17}
$$

*Proof.* Indeed, using that $\Delta^{-1/2}$ is a symmetric matrix, we have

$$
\begin{align*}
u \in \langle H_i \rangle^{\perp} &\Leftrightarrow \forall v \in H_i, \langle v, u \rangle = 0 \Leftrightarrow \forall v \in \Delta^{-1/2} G_i, \langle v, u \rangle = 0 \\
&\Leftrightarrow \forall j \neq i, \langle \Delta^{-1/2} e_j, u \rangle = 0 \Leftrightarrow \forall j \neq i, \langle e_j, \Delta^{-1/2} u \rangle = 0 \\
&\Leftrightarrow \Delta^{-1/2} u = \lambda e_i, \quad \lambda \in \mathbb{R} \Leftrightarrow u = \lambda \Delta^{1/2} e_i = \lambda u_i, \quad \lambda \in \mathbb{R}. \quad \Box
\end{align*}
$$

**Proposition 3.** Let $u_i$ be defined in (16). For all $i$, $\|u_i\| = 1$. Moreover, for all $i, j$, the angle between the vectors $u_i$ and $u_j$ is $\alpha_{i,j} := \arccos a_{i,j} \in (0, \pi)$.

*Proof.* To prove the first point, notice that $\Delta^{\frac{1}{2}}$ is a symmetric matrix, and thus

$$
\|u_i\|^2 = \langle \Delta^{\frac{1}{2}} e_i, \Delta^{\frac{1}{2}} e_i \rangle = \langle e_i, \Delta e_i \rangle = e_i^T \Delta e_i = a_{i,i} = 1.
$$

To show the second assertion, note that, on the one hand, $\langle u_i, u_j \rangle = \cos(\alpha_{i,j}) \|u_i\| \|u_j\| = \cos(\alpha_{i,j})$,
and on the other hand, $\langle u_i, u_j \rangle = \langle \Delta^{\frac{1}{2}} e_i, \Delta^{\frac{1}{2}} e_j \rangle = e_i^T \Delta e_j = a_{i,j}$. Thus, $\cos(\alpha_{i,j}) = a_{i,j}$. $\square$

We now compute the angles between any two hyperplanes defining $T = \Delta^{-\frac{1}{2}}\mathbb{R}_{+}^{d}$. We define
the angle $\widehat{H_iH_j}$ between two hyperplanes $H_i$ and $H_j$ bounding $T$ by the interior angle within the
orthant $T$, as shown in Figure 3. As the following result proves, the interior angles of $T = \Delta^{-\frac{1}{2}}\mathbb{R}_{+}^{d}$
can be read directly from the matrix $\Delta$.
<figure><img src="image_6.png" /><figcaption>FIGURE 3. Measure of the angle $\widehat{H_i H_j}$ between two hyperplanes $H_i$ and $H_j$ in $T$, in terms of the angle $(\widehat{u_i, u_j})$ between the normal vectors $u_i$ and $u_j$ in (16). The relationship between the angle $\widehat{H_i H_j}$ and $(\widehat{u_i, u_j})$ is determined by the orientation of the normal vectors $u_i$ and $u_j$ being inward: $(\widehat{u_i, u_j}) = \pi - \widehat{H_i H_j}$.</figcaption></figure>

**Proposition 4.** It holds that

$$ \widehat{H_i H_j} = - \arccos a_{i,j}. \qquad (18) $$

*Proof.* Fix $i \in \{1, \dots, d\}$. We prove that $u_i$ is an inward, normal unit vector with respect to $T$. We have already shown that $u_i$ is a normal unit vector, see Lemma 2. To prove the inward property, we take any point on $v \in H_i \cap \partial T$ (but not in $H_j$ for $j \neq i$) and show that for small $t > 0$, $v + tu_i \in T$. Take for instance $v = \Delta^{-\frac{1}{2}}w$, with

$$ w = e_1 + \dots + e_{i-1} + e_{i+1} + \dots + e_d. $$

We have $w \in G_i \cap \partial \mathbb{R}_+^d$ and $w \notin G_j$ if $j \neq i$, remembering that $G_i$ is defined in (15). Using (16), we can write

$$ v + tu_i = \Delta^{-\frac{1}{2}}(w + t\Delta e_i). $$

Denoting by $\mu_1, \dots, \mu_d$ the coordinates of $w + t\Delta e_i$ in the canonical basis, we get that, since $\Delta = (a_{i,j})_{1 \le i,j \le d}$:

$$ \forall j \in \{1, \dots, d\} \setminus \{i\}, \quad \mu_j = 1 + ta_{j,i} \quad \text{and} \quad \mu_i = ta_{i,i} = t. $$

All these coordinates are positive for small $t > 0$ and thus $w + t\Delta e_i \in \mathbb{R}_+^d$, which proves that $v + tu_i \in T = \Delta^{-\frac{1}{2}}\mathbb{R}_+^d$. This shows that $u_i$ is inward, which clearly implies that for all $i, j \in \{1, \dots, d\}$,

$$ (\widehat{u_i, u_j}) = \pi - \widehat{H_i H_j}. $$

By applying Proposition 3, Equation (18) follows. $\square$

Let $S$ be a set of directions and $\chi_S$ the associated polynomial (5). We denote by $G$ the group (6) generated by the transformations (7), which we reformulate as $\varphi_i = \langle x_1, \dots, x_{i-1}, \sigma_i, x_{i+1}, \dots, x_d \rangle$, with $\sigma_i = \frac{1}{x_i A_i}$. From now on, $\Delta = (a_{i,j})_{1 \le i,j \le d}$ is the covariance matrix introduced in Theorem 1.
3.2. Main result. The main result in this section is a reformulation of the group $G$ as the preimage by a morphism of a reflection group. To state this result, we recall our notation $H_i = \langle u_i \rangle^{\perp}$ and introduce $r_i$, the orthogonal reflection with respect to $H_i$. Finally, we introduce the reflection group

$$H = \langle r_1, \dots, r_d \rangle. \tag{19}$$

By definition, this is the group generated by the reflections with respect to the sides of the linear transformation of the orthant $\Delta^{-\frac{1}{2}}\mathbb{R}_+^d$.

We need to define two more quantities. First, we introduce the application

$$J: \left| \begin{array}{lcl} G & \to & GL_d(\mathbb{R}) \\ g & \mapsto & Jac_{x_0} g \end{array} \right. \tag{20}$$

where $x_0$ is the unique minimum of $\chi_S$, see (9). Secondly, we define a symmetric bilinear form on $\mathbb{R}^d$ by setting, for all $h, k \in \mathbb{R}^d$,

$$[h, k] := D^2\chi_S(x_0)(h, k) = \sum_{i,j=1}^{d} \frac{\partial^2\chi_S}{\partial x_i \partial x_j}(x_0)h_i k_j \tag{21}$$

and we set $f_i = \frac{e_i}{\sqrt{|e_i e_i|}}$. The function in (21) is the quadratic form associated with the covariance matrix of the random walk $(X_n)_{n \ge 0}$ introduced in Section 2. Notice that the Jacobian of some elements of the group $G$ was already used in [11, Sec. 3] (for two-dimensional models) and in [21, 28] (for three-dimensional models), in order to prove that in some cases, the group $G$ is infinite. As we will see later, the Jacobian application (20) can be used to obtain various and new results about the group $G$. In particular, it works in any dimension and applies to the comparison of the groups $G$ in (6) and $H$ in (19).

**Theorem 5.** The following assertions hold true:

(i) The map $J$ is a morphism.

(ii) $[\cdot, \cdot]$ is a scalar product.

(iii) $[\cdot, \cdot]$ is invariant under Im $J$.

(iv) The map

$$\Phi: \left| \begin{array}{lcl} \mathbb{R}^d & \to & \mathbb{R}^d \\ f_i & \mapsto & u_i \end{array} \right. \tag{22}$$

is an isometry from $(\mathbb{R}^d, [\cdot, \cdot])$ to $(\mathbb{R}^d, \langle \cdot, \cdot \rangle)$.

(v) For all $i$, $S_i = J\varphi_i$ is the orthogonal reflection with respect to $e_i$ in $(\mathbb{R}^d, [\cdot, \cdot])$.

*Proof.* Let us first show that $J$ is a morphism. A first well-known observation is that since $x_0$ is the minimum of $\chi_S$, $x_0$ is a fixed point of all $g \in G$. It suffices to check this fact for all generators $\varphi_i$ of $G$. Since $\chi_S = \bar{x}_i C_i + B_i + x_i A_i$, we have, if we note $x_0 = (x_0^1, \dots, x_0^d)$,

$$0 = \frac{\partial \chi_S}{\partial x_i}(x_0) = \frac{-1}{(x_0^i)^2} C_i(x_0) + A_i(x_0).$$

Thus,

$$\varphi_i(\mathbf{x}_0) = \left[ x_0^1, \dots, x_0^{i-1}, \frac{1}{x_0^i} \frac{C_i(\mathbf{x}_0)}{A_i(\mathbf{x}_0)}, x_0^{i+1}, \dots, x_0^d \right] = \mathbf{x}_0.$$

For all $g, g' \in G$, we thus get

$$J(gg') = Jac_{x_0}(g \circ g') = Jac_{g'(x_0)}g Jac_{x_0}g' = Jac_{x_0}g Jac_{x_0}g' = J(g)J(g').$$
We now prove (ii). Obviously using (10) one has for $h \in \mathbb{R}^d$

$$[h, h] = \mathrm{D}^2\chi_S(\mathbf{x}_0)(h, h) = \sum_{i,j=1}^{d} \frac{\partial^2\chi_S}{\partial x_i \partial x_j}(\mathbf{x}_0)h_i h_j > 0.$$

The positivity follows from the positive definiteness of the covariance matrix of the random walk $(X_n)_{n \ge 0}$, which in turn follows from (H1).

We now provide the proof of (iii), by showing that

$$[J(g)h, J(g)k] = [\mathrm{Jac}_{\mathbf{x}_0}g(h), \mathrm{Jac}_{\mathbf{x}_0}g(k)] = [h, k] \quad (23)$$

for all $g \in G$ and all $h, k \in \mathbb{R}^d$. We have

$$[J(g)h, J(g)k] = \mathrm{D}^2\chi_S(\mathbf{x}_0)(\mathrm{Jac}_{\mathbf{x}_0}g(h), \mathrm{Jac}_{\mathbf{x}_0}g(k)) \\ = \sum_{i,j=1}^{d} \frac{\partial^2\chi_S}{\partial x_i \partial x_j}(\mathbf{x}_0)(\mathrm{Jac}_{\mathbf{x}_0}g(h))_i(\mathrm{Jac}_{\mathbf{x}_0}g(k))_j.$$

By differentiating twice the equality $\chi_S \circ g = \chi_S$ at $\mathbf{x}_0$, we obtain

$$\mathrm{D}^2\chi_S(g(\mathbf{x}_0))(J(g)h, J(g)k) + \mathrm{D}\chi_S(g(\mathbf{x}_0)) \circ \mathrm{D}^2g(\mathbf{x}_0)(h, k) = \mathrm{D}^2\chi_S(g(\mathbf{x}_0))(h, k).$$

Since $g(\mathbf{x}_0) = \mathbf{x}_0$ is a critical point of $\chi_S$, the last term of the left-hand side vanishes and we get

$$\mathrm{D}^2\chi_S(g(\mathbf{x}_0))(J(g)h, J(g)k) = \mathrm{D}^2\chi_S(g(\mathbf{x}_0))(h, k),$$

i.e., $[J(g)h, J(g)k] = [h, k]$. This proves Equation (23).

We move to the proof of (iv). We show that for all $i, j \in \{1, \dots, d\}$, $\langle u_i, u_j \rangle = [f_i, f_j]$, with $u_k$ defined in (16) and $f_k = \frac{e_k}{\sqrt{[e_k, e_k]}}$. Indeed, we have

$$[f_i, f_j] = \left[ \frac{e_i}{\sqrt{[e_i, e_i]}}, \frac{e_j}{\sqrt{[e_j, e_j]}} \right] = \frac{\frac{\partial^2 \chi_S}{\partial x_i \partial x_j}(\mathbf{x}_0)}{\sqrt{\frac{\partial^2 \chi_S}{\partial x_i^2}(\mathbf{x}_0) \cdot \frac{\partial^2 \chi_S}{\partial x_j^2}(\mathbf{x}_0)}} = a_{i,j} = \langle u_i, u_j \rangle,$$

where we recall that $\Delta = (a_{i,j})_{1 \le i,j \le d}$ is the covariance matrix introduced in Theorem 1 and where the last equality comes from Proposition 3.

Finally we show (v). First notice that since $\varphi_i^2 = \mathrm{Id}$, it holds that $S_i^2 = (J\varphi_i)^2 = \mathrm{Id}$. We compute the following matrix form of $S_i$, where we denote by $\varphi_i^j$ the j-th coordinate function of $\varphi_i = (x_1, \dots, x_{i-1}, \sigma_i, x_{i+1}, \dots, x_d)$:

$$S_i = \begin{pmatrix} 1 & 0 & \cdots & \cdots & \cdots & \cdots & 0 \\ 0 & \ddots & \ddots & & & & & \vdots \\ \vdots & & 1 & 0 & \cdots & \cdots & 0 & \vdots \\ \frac{\partial \varphi_i^i}{\partial x_1}(\mathbf{x}_0) & \frac{\partial \varphi_i^i}{\partial x_2}(\mathbf{x}_0) & \cdots & -1 & \cdots & \cdots & \frac{\partial \varphi_i^i}{\partial x_n}(\mathbf{x}_0) & \vdots \\ 0 & 0 & \cdots & 0 & 1 & 0 & \vdots & \vdots \\ \vdots & \vdots & \cdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & \cdots & \cdots & 0 & 1 \end{pmatrix}. \quad (24)$$

To prove (24), we only need to justify the calculations leading to the i-th row. Since $\sigma_i = \frac{1}{x_i} \frac{C_i}{A_i}$ by (7), we have $\frac{\partial \varphi_i^i}{\partial x_i}(\mathbf{x}_0) = \frac{\partial \sigma_i}{\partial x_i}(\mathbf{x}_0) = -\frac{1}{x_i^2} \frac{C_i}{A_i}$. On the other hand, since $\mathbf{x}_0$ is the minimum of $\chi_S$, we have $\frac{\partial \chi_S}{\partial x_i}(\mathbf{x}_0) = -\frac{1}{x_i^2} C_i + A_i = 0$, so that $\frac{\partial \varphi_i^i}{\partial x_i}(\mathbf{x}_0) = -1$.
The matrix $S_i$ in (24) is diagonalisable, with eigenvalues $-1$ (simple) and $1$ (multiplicity $d-1$). Moreover, from (24), $e_i$ is clearly a eigenvector associated to $-1$.

We denote by $E_i = \{x \in \mathbb{R}^d | S_i(x) = x\}$ the eigenspace of $\varphi_i$ associated with eigenvalue 1 and show that $E_i = \langle e_i \rangle^{\perp[\cdot, \cdot]}$. For $x \in E_i$, since $[\cdot, \cdot]$ is invariant under $\mathrm{Im} J$ by (iii),

$$[x, e_i] = [S_i(x), e_i] = [S_i^2(x), S_i(e_i)] = [x, -e_i].$$

Hence, $[x, e_i] = 0$ and $E_i \subset \langle e_i \rangle^{\perp[\cdot, \cdot]}$. But since $E_i$ has dimension $d-1$, we get $E_i = \langle e_i \rangle^{\perp[\cdot, \cdot]}$. Thus, $S_i$ is indeed the orthogonal reflection with respect to $E_i$ in $(\mathbb{R}^d, [\cdot, \cdot])$. $\square$

We will now state two important consequences of Theorem 5, all of which concern the groups $G$ and $H$. In the first corollary below, we show that the image of $G$ by $J$ in (20) is isomorphic to the reflection group $H$. Before giving the result, we first note that $\Phi$ in (22) induces an isomorphism $\tilde{\Phi}$ between the orthogonal groups $O(\mathbb{R}^d, [\cdot, \cdot])$ and $O(\mathbb{R}^d, \langle \cdot, \cdot \rangle)$. More precisely, for all $s \in O(\mathbb{R}^d, [\cdot, \cdot])$, define

$$\tilde{\Phi}(s) = \Phi \circ s \circ \Phi^{-1},$$

which belongs to $O(\mathbb{R}^d, [\cdot, \cdot])$ since $\Phi$ is an isometry. Note that by construction we have $\tilde{\Phi}(S_i) = r_i$ for all $i$. As an immediate consequence we get:

**Corollary 6.** The restriction of $\tilde{\Phi}$ to $\mathrm{Im} J$ is an isomorphism between the two reflection groups $\mathrm{Im} J$ and $H$ such that for all $i$, $\tilde{\Phi}(S_i) = r_i$. In particular, $\tilde{\Phi} \circ J : G \to H$ is a surjective morphism that sends the set of generators $(\varphi_1, \dots, \varphi_d)$ of $G$ to the set of generators $(r_1, \dots, r_d)$ of $H$.

While Corollary 6 shows a strong connection between the groups $G$ and $H$, it is important to note that in general these two groups do not coincide. See Example 9 for a concrete example where the group $H$ is of order 8 while $G$ is infinite. However, we obtain the following consequence:

**Corollary 7.** If $G$ is finite, then $H$ is finite.

In Propositions 10, 11 and 12, we give sufficient conditions for the groups $G$ and $H$ to be isomorphic. As we will explain in Section 4.1, a possible application of Corollary 7 is that if $H$ is infinite, then necessarily $G$ should be infinite. This may be of practical interest, since reflection groups are well understood and more classical than the combinatorial group $G$.

**3.3. Illustration in dimension two.** The case of dimension two is the one that has attracted the most attention in the literature, see e.g. [33, 23, 11, 9]. Our results do not bring any new progress in this case, but it is interesting to compute the new domain $T$ in (4) and see how it depends on the parameters. The covariance matrix (10) takes the form

$$\Delta = \begin{pmatrix} 1 & a \\ a & 1 \end{pmatrix}, \quad \text{with } a = a_{1,2} = \frac{\frac{\partial^2 \chi_S}{\partial x_1 \partial x_2}(\mathbf{x}_0)}{\sqrt{\frac{\partial^2 \chi_S}{\partial x_1^2}(\mathbf{x}_0) \cdot \frac{\partial^2 \chi_S}{\partial x_2^2}(\mathbf{x}_0)}}.$$

Diagonalizing the matrix $\Delta$ and setting $a = -\cos \alpha$, we easily find

$$\Delta^{\frac{1}{2}} = \begin{pmatrix} \cos(\frac{\pi}{4} - \frac{\alpha}{2}) & -\sin(\frac{\pi}{4} - \frac{\alpha}{2}) \\ -\sin(\frac{\pi}{4} - \frac{\alpha}{2}) & \cos(\frac{\pi}{4} - \frac{\alpha}{2}) \end{pmatrix}.$$

The vectors $u_1$ and $u_2$ in (16) are equal to

$$u_1 = \begin{pmatrix} \cos(\frac{\pi}{4} - \frac{\alpha}{2}) \\ -\sin(\frac{\pi}{4} - \frac{\alpha}{2}) \end{pmatrix} \quad \text{and} \quad u_2 = \begin{pmatrix} -\sin(\frac{\pi}{4} - \frac{\alpha}{2}) \\ \cos(\frac{\pi}{4} - \frac{\alpha}{2}) \end{pmatrix},$$
<figure><img src="image_7.png" /><figcaption>FIGURE 4. In dimension 2, the vectors $u_i$ and the hyperplanes $H_i$ are easily computed in terms of the correlation factor $a$. The chamber becomes the domain between the two hyperplanes $H_1$ and $H_2$, which is a wedge of opening $arccos(-a)$, as already noticed in [17, Ex. 2]. See also Figure 2.</figcaption></figure>

see Figure 4. The hyperplanes $H_i = \langle u_i \rangle^\perp$ in (17) are thus given by

$$H_1 = \left( \sin\left(\frac{\pi}{4} - \frac{\alpha}{2}\right) \cos\left(\frac{\pi}{4} - \frac{\alpha}{2}\right) \right) \quad \text{and} \quad H_2 = \left( \cos\left(\frac{\pi}{4} - \frac{\alpha}{2}\right) \sin\left(\frac{\pi}{4} - \frac{\alpha}{2}\right) \right).$$

## 4. APPLICATIONS

In our opinion, the main interest of our results (Theorem 5 and Corollary 6) is that they clarify a lot about the connections between the combinatorial group $G$ in (6), the reflection group $H$ in (19) and Coxeter groups in general. However, our results also have concrete applications; in particular, they provide some tools to determine whether $G$ is finite or not in several situations.

### 4.1. Infinite group criterion in any dimension.
In dimension two and three, the classification of the models with respect to the (in)finiteness of the group $G$ is complete in the case of unweighted models $S$ (unweighted means that all non-zero weights $w(s)$ are equal; in other words, the walk jumps uniformly to any element of the step set $S$); see [11] for the case of dimension two, and [8, 21, 1, 28] for the case of dimension three. While one can observe by direct computation that a given model admits a finite group (computing all elements of the group, see e.g. [11, 8]), proving that the group $G$ is infinite is more delicate. Let us recall some possible strategies:

* A first observation is that if $H$ is infinite, then $G$ is also infinite. This is obviously a direct application of Corollary 7, but our result is not really needed in the present situation. Indeed, to prove that $G$ is infinite, it is sufficient to show that for some $g \in G$ the matrix $J(g)$ in (20) is of infinite order. This is the strategy proposed in [11] for unweighted models in dimension two. In practice, it is shown that the eigenvalues of $J(g)$ have norm 1 and that their order on the unit circle $S^1$ is infinite.

* The above method may fail; typically, in our notation, if $H$ is finite, then $J(g)$ has finite order for any $g \in G$; see Example 9. In such cases, as we now explain following the authors of [21], the argument can be adapted. In fact, it is not necessary to calculate the order of the Jacobian matrix at $x_0$ in (9). While $x_0$ is the unique fixed point common to all elements
of $G$, any given $g \in G$ admits many more fixed points. For example, denoting $\varphi_1$ and $\varphi_2$ as two generators of the group $G$ as in (6), there exists a fixed point $x_z = (x, y, z)$ of $\varphi_1$ and $\varphi_2$, and thus of the composition $\varphi_1\varphi_2$, for any value of $z \in \mathbb{R}^{d-2}$. In the method in [21], the difficulty is to find a fixed point where $J_{x_z}(g)$ has an eigenvalue of norm other than 1. However, if it can be found, then $J_{x_z}(g)$ is of infinite order, and thus the group $G$ is infinite.

The above methods require long and case-by-case computations, with a number of models that
grows with dimension (more than 11 millions of unweighted in dimension three, see [8]).

Our results allow the previous arguments to be greatly simplified in several situations. As already explained, to prove that $G$ is infinite, it is sufficient to prove that $H$ is infinite. The methods above actually consist of proving that $\mathrm{Im} \, J$ is infinite, but working directly with $H$ can be very helpful:

* First, note that given $g = \varphi_i\varphi_j$, the order of $J(g)$ is known as soon as $x_0$ is computed. In fact, using our notation from Theorem 5, $J(g) = S_iS_j$ (or $r_i r_j \in H$) is then the composition of two reflections and thus a rotation of the angle twice the angle between the hyperplanes $H_i$ and $H_j$ (see (17)). Using Proposition 4, its order can be read directly from the covariance matrix $\Delta$ in (10): it is the order of $e^{2i \arccos a_{i,j}}$ in the circle $S^1$, where $a_{i,j}$ is the coefficient $(i,j)$ of the covariance matrix $\Delta$.

* If $H$ is finite, the method fails, but we can apply the same ideas to a subgroup $G'$ of $G$ at a fixed point of $G'$.

* Another property of $H$ is that it is a reflection group and thus a Coxeter group (see Appendix A for some reminders about Coxeter groups), which are classified. If it is finite, it must belong to a short list of examples, and so to prove that $H$ is infinite it suffices to exclude $H$ from the list of examples. This allows us to deduce Proposition 8 below.

In Proposition 10 below we will further consider the case of a finite group $G$ and give a condition ensuring that $G$ and $H$ are isomorphic.

## 4.2. A method to prove that the reflection group is infinite. We prove the following:

**Proposition 8.** Let $(a_{i,j})_{1\le i,j\le d}$ be the coefficients of the covariance matrix $\Delta$ in (10). Then the group $H$ is infinite as soon as the following two conditions are satisfied:

* $\Delta$ is not, up to a permutation of lines, a matrix diagonal by blocks with a block of size 2;

* there exist $i \neq j$ such that $a_{i,j} \notin \{0, \pm\frac{1}{2}, \pm\frac{\sqrt{2}}{2}, \pm\frac{\sqrt{3}}{2}, \pm\frac{\sqrt{5}-1}{4}, \pm\frac{\sqrt{5}+1}{4}\}$, or equivalently such that $a_{i,j}$ has not the form $\cos(\frac{k\pi}{m})$ with $k \in \mathbb{Z}$ and $m \in \{1, 2, 3, 4, 5, 6\}$.

Let us recall that $H$ is the group spanned by $r_1, \dots, r_d$, the reflections with respect to $H_1 := \langle u_1 \rangle^{\perp}, \dots, H_d := \langle u_d \rangle^{\perp}$, where $u_i = \Delta^{\frac{1}{2}}e_i$, see (16), (17) and (19). A technical difficulty is that the conditions of Proposition 8 do not ensure that $r_1, \dots, r_d$ is a Coxeter system (see Definition 19 in Appendix A for the concept of a Coxeter system), and so to derive conditions on $a_{i,j}$ we cannot directly use Proposition 22, which gives the list of Coxeter systems spanning finite Coxeter groups.

*Proof of Proposition 8.* First, since $(u_1, \dots, u_d)$ is a basis of $\mathbb{R}^d$, the Coxeter group $H$ has rank $d$. Suppose it is finite. We do not know if it is reducible or not, but assume that it has an irreducible factor (see Appendix A), which is a dihedral group of order $2k$. Consider the set of all roots of $H$, i.e.

$$R := \{ \pm hu_i | h \in H \}. \qquad (25)$$
Then, from the classification of finite Coxeter groups, there are exactly 2k roots (corresponding to k hyperplanes) which belong to a plane and are orthogonal to the other roots. More precisely, the dihedral group factor is spanned by the k reflections with respect to these hyperplanes. Since $(u_1, \dots, u_d)$ is a basis, it must contain exactly two of these 2k roots, which are then orthogonal to the other $u_i$. Up to a permutation of the $u_i$ we can assume that these roots are $u_1$ and $u_2$. By Proposition 3, the coefficient $(i, j)$ of $\Delta$ is 0 if $i = 1, 2$ and $j \ge 3$, since $u_i \perp u_j$. The matrix $\Delta$ thus has a 2-diagonal block, which is a contradiction. We deduce that if the assumptions of Proposition 8 are fulfilled, then $H$ has no irreducible dihedral group factor.

Let now $\Lambda := \cup_{w \in R} \langle w \rangle^{\perp}$, with $R$ as in (25). Suppose there exist $i \neq j$ such that $\arccos a_{i,j}$ does not have the form $\frac{k\pi}{m}$ for some $k \in \mathbb{Z}$ and $m \in \{1, 2, 3, 4, 5, 6\}$, and thus $e^{2i \arccos a_{i,j}}$ has order $\alpha_{i,j}$ greater than 7 in $\mathbb{S}^1$. Since $r_i$ and $r_j$ are reflections, this means that $r_i r_j$ is a rotation in the plane $P$ orthogonal to $P^{\perp} := H_i \cap H_j$, with angle $-2 \arccos a_{i,j}$ which is twice the angle between $H_i$ and $H_j$, see (18). The group $\{(r_i r_j)^k | k \in \mathbb{Z}\}$ is the rotation group spanned by $e^{2i \arccos a_{i,j}}$ in $\mathbb{S}^1$ and since $\alpha_{i,j} \ge 7$, there exists $k$ such that $(r_i r_j)^k$ is a rotation of angle $\theta \in [0, \frac{2\pi}{7}]$. Introducing $H'_i := (r_i r_j)^k(H_i)$, this means that $H_i$, $H'_i \in \Lambda$ are two hyperplanes of $\Lambda$ with angle $\theta$. In particular, every chamber of $K$ has two walls whose angle is less than $2\pi/7$, which by Proposition 22 implies that $H$ is infinite. $\square$

**Example 1.** We will now illustrate how we can prove that $H$ (and thus $G$) is infinite, using simple calculations. Let $(x, y, z, w)$ be the standard Cartesian coordinates of $\mathbb{R}^4$. We consider the model whose inventory (5) is given by

$$ \chi_S(x, y, z, w) = xy + \bar{y}z + \bar{z}w + \bar{x}yz + \bar{y}\bar{z}\bar{w} + \bar{x}\bar{y}\bar{z} + \bar{x}\bar{y}\bar{z}. $$

Here we show that $H$ is infinite by computing the covariance matrix. By direct calculation (or using the fact that the drift of the model is zero), the fixed point is $x_0 = (1, 1, 1, 1)$ and the covariance matrix is

$$ \Delta = \begin{pmatrix} \frac{1}{\sqrt{6}} & \frac{1}{2\sqrt{6}} & 0 \\ \frac{1}{\sqrt{6}} & 1 & -\frac{1}{6} \\ -\frac{1}{2\sqrt{6}} & -\frac{1}{6} & 1 \\ 0 & \frac{1}{2\sqrt{3}} & -\frac{1}{\sqrt{3}} \end{pmatrix}. $$

Proposition 8 immediately implies that $H$ is infinite, and therefore $G$ is also infinite.

The method presented in Example 1 could be made systematic on a large class of models; we do not explore this line of research in this paper.

### 4.3. A tool to determine $H$ when $G$ is known.

**Lemma 9.** Let $K$ be a rank $d$ reflection group. Then $|K| \ge 2^d$ with equality if and only if $H = (\frac{z}{2\bar{z}})^d$.

*Proof.* It comes either from the classification of finite Coxeter groups or from the classical Matsumoto's theorem. Let $(s_1, \dots, s_d)$ be a Coxeter system. Define

$$ X := \left| \begin{array}{c} \{0, 1\}^d \\ (a_1, \dots, a_d) \end{array} \rightarrow \begin{array}{c} K \\ s_1^{a_1} \cdots s_d^{a_d} \end{array} \right. $$

Then by Matsumoto's theorem [34], $X$ is injective which implies that $|K| \ge 2^d$. Assume now that $|K| = 2^d$. This means that $K = X(\{0, 1\}^d)$. Let $i < j$, then $s_j s_i$ can be written as $s_j s_i = s_{i_1} \cdots s_{i_r}$ for some $1 \le i_1 < \cdots < i_r \le d$. Again by Matsumoto's theorem, we have $\{j, i\} = \{i_1, \dots, i_r\}$. Since
i < j, this implies that r = 2, i₁ = i and i₂ = j, and consequently that sjsi = sᵢsⱼ. This proves that $H = (\frac{\mathbb{Z}}{2\mathbb{Z}})^d$. □

We are ready to give the following application of Corollary 6, which gives a sufficient condition for the groups G and H to be isomorphic.

**Proposition 10.** Assume that G is finite and let

$$N := \min\{|K| \mid K \text{ is a normal subgroup of } G, K \neq \{\mathrm{Id}\}\}.$$

* If $|G| < 2^d N$, then G and H are isomorphic.

* If $|G| = 2^d N$ and G and H are not isomorphic, then $H = (\frac{\mathbb{Z}}{2\mathbb{Z}})^d$.

*Proof.* Assume first that $|G| < 2^d N$. By Corollary 6, H is isomorphic to $G/\ker(\tilde{\Phi} \circ J)$. Since H is a finite reflection group of rank d, we can deduce from Proposition 9 that $|H| \ge 2^d$. As a consequence, if $\ker(\tilde{\Phi} \circ J) \neq \{\mathrm{Id}\}$, then necessarily

$$|G| \ge |H| \quad |\ker(\tilde{\Phi} \circ J)| \ge 2^d N,$$

which contradicts our assumption. This implies that $\ker(\tilde{\Phi} \circ J) = \{\mathrm{Id}\}$, and so the groups G and H are isomorphic.

Now suppose that $|G| = 2^d N$ and that G and H are not isomorphic. We must have $|H| = 2^d$ and we deduce that $H = (\frac{\mathbb{Z}}{2\mathbb{Z}})^d$. □

We can apply Proposition 10 in several situations, as the following four examples show.

**Example 2.** Let p be a prime number. Assume d = 2 and G = $D_{2p}$ is the dihedral group of order 2p. Then N = p and thus $|G| = 2p < 4N$. Proposition 10 shows that the groups G and H are isomorphic. Recall that the only known finite groups in dimension two are $D_{2p}$ for $p \in \{2, 3, 4, 5\}$, see [11, 29].

**Example 3.** Suppose G is the permutation group $\mathfrak{S}_{d+1}$. Such a situation occurs in dimension three, see [1, Tab. 1]; it also arises naturally when considering the model of non-intersecting lattice paths in arbitrary dimension, see the forthcoming Example 11. In this case, we have $|G| < N2^d$ for all $d \ge 2$, and thus by Proposition 10, the groups G and H are isomorphic.

Indeed, if $d = 2$, then $|G| = 6$, N = 3 and it holds that $|G| < N2^2$. If $d = 3$ then $|G| = 24$, N = 4 and $|G| < N2^3$. Finally if $d \ge 4$, $|G| = (d+1)!$ and $N = \frac{(d+1)!}{2}$ so that again $|G| < N2^d$. Then we conclude that G and H are isomorphic.

**Example 4.** Assume here that $d = 4$ and $G = \mathfrak{S}_3 \times (\frac{\mathbb{Z}}{2\mathbb{Z}})^2$. Some examples of models corresponding to this situation can be found in [12, Tab. 1]. Then $G = |24|$. Since $N \ge 2$, it holds that $|G| < N2^4$ and thus again G and H are isomorphic.

**Example 5.** Assume that $d = 4$ and $G = \mathfrak{S}_3 \times \mathfrak{S}_3$. Some examples of models that fit this situation are in [12, Tab. 2]. Then $|G| = 36$. We claim that $N \ge 3$. Indeed otherwise, N = 2 and there exists $(x, y) \in \mathfrak{S}_3 \times \mathfrak{S}_3$ which has order 2 and such that $\langle (x, y) \rangle$ is a normal subgroup of G. Clearly, this would imply that $\langle x \rangle$ is a normal subgroup of $\mathfrak{S}_3$, which is impossible since $\mathfrak{S}_3$ has no normal subgroup of order 2. We conclude that G and H are isomorphic.
4.4. A tool to determine G when H is known. We first establish the following.

**Proposition 11.** Given any pair $(i, j)$ in $\{1, \dots, d\}^2$, define $m_{i,j}$ as the orders of $\varphi_i\varphi_j$ in G. Let $K_d$ be the Coxeter group spanned by $(a_1, \dots, a_d)$ and defined by the presentation

$$ \mathcal{R} = \{(a_ia_j)^{m_{i,j}} | 1 \le i \le j \le d\}. $$

Then $|K_d| \ge |G| \ge |H|$. In particular, if $|K_d| = |H|$, then G and H are isomorphic.

Note that it is possible to define $K_d$ because $m_{i,i} = 1$ for all $i$.

*Proof.* We already know from Corollary 6 that $|H| \le |G|$. From the definition of a presentation, $K_d$ is isomorphic to the quotient of the free group $F_d$ of rank $d$ by the normal closure of $\mathcal{R}$ in $F_d$ (i.e., the smallest normal subgroup of $F_d$ containing $\mathcal{R}$).

If $(G|\mathcal{S})$ is a presentation of G (written with the generators $(\varphi_1, \dots, \varphi_d)$ of G), then, since $(\varphi_1, \dots, \varphi_d)$ satisfy the relations in $\mathcal{R}$, $(G|\mathcal{S}')$ is also a presentation of G, where we noted $\mathcal{S}' = \mathcal{S} \cup \mathcal{R}$. Now again by the definition of a presentation, G is isomorphic to the quotient of the free group $F_d$ by the normal closure of $\mathcal{S}'$ in $F_d$. Since $\mathcal{R} \subset \mathcal{S}'$, their normal closures satisfy the same inclusion in $F_d$ and we deduce that $|G| \le |K_d|$. $\square$

We show how to apply the above result.

**Example 6.** Consider on $\mathbb{R}^d$ the following model

$$ \chi_{\mathcal{S}}(x_1, \dots, x_d) = \bar{x}_1 + \sum_{i=1}^{d-1} x_i \bar{x}_{i+1} + x_d. $$

In dimension 2 this model is often called the tandem walk [11]. The latter model can thus be interpreted as a $d$-dimensional tandem model. It can also be interpreted as a possible model of non-intersecting lattice paths, where each coordinate represents the difference between two successive walks (see Example 11 for a closely related model).

We calculate that $x_0 = (1, \dots, 1)$ and the covariance matrix $\Delta = (a_{i,j})$ is given by

$$ a_{i,j} = \begin{vmatrix} 1 & \text{if } i = j, \\ -\frac{1}{2} & \text{if } |i - j| = 1, \\ 0 & \text{otherwise.} \end{vmatrix} $$

From the classification of finite Coxeter groups, H is isomorphic to the permutation group $\mathfrak{S}_{d+1}$ and $(r_1, \dots, r_d)$ is a Coxeter system. As easily computed, the orders $m_{i,j}$ of $\varphi_i\varphi_j$ and $r_i r_j$ are the same and equal to

$$ m_{i,j} = \begin{vmatrix} 1 & \text{if } i = j, \\ 3 & \text{if } |i - j| = 1, \\ 2 & \text{otherwise.} \end{vmatrix} $$

We conclude that $H \equiv \mathfrak{S}_{d-1}$ is isomorphic to $K_d$ and from Proposition 11 to G.

As a concluding remark, if $|K_d| = \infty$, Proposition 11 does not give any information. A more general result can be obtained in the same way:

**Proposition 12.** Assume that $\mathcal{R}$ is a set of relations of the generators $(r_1, \dots, r_d)$ of H such that $(H|\mathcal{R})$ is a presentation of H. If for all $r_{i_1} \dots r_{i_n} \in \mathcal{R}$, $\varphi_{i_1} \dots \varphi_{i_n} = \text{Id}$ in G, then G and H are isomorphic.
<figure><img src="image_8.png" /><figcaption>FIGURE 5. Left picture: the model considered in Example 7. Second picture: the model of Example 8. Right picture: the model presented on Example 9.</figcaption></figure>

*Proof.* The proof uses the same argument as in the proof of Proposition 11: if $(G|S)$ is a presentation of $G$ (written with the generators $(\varphi_1, \dots, \varphi_d)$ of $G$), $(G|S')$ with $S' = S \cup \mathcal{R}$ is also a presentation of $G$, which implies $|G| \le |H|$. Again, we deduce from Corollary 6 that $G$ and $H$ are isomorphic. □

4.5. **Dimension two.** Although our results do not bring any novelty in dimension two, we briefly recall what is known about the group $G$, which is a dihedral group, finite or infinite. In the unweighted case, if finite, $G$ can be of order 4, 6 or 8, see [11]. If non-trivial weights are allowed, then the group can be of order 10, see [29, Sec. 7], and it is believed that no higher order is possible.

On the other hand, the group $H$ can be any finite dihedral group. For example, consider any fixed value of $n \ge 3$ and define the transition probabilities $w(1,0) = w(-1,0) = \frac{\sin^2(\pi/n)}{2}$ and $w(1,-1) = w(-1,1) = \frac{\cos^2(\pi/n)}{2}$, then $H$ can be proved to be dihedral of order $2n$ using the computations in Section 3.3; this example is inspired by the work [38].

4.6. **Dimension three.** We consider the three examples represented on Figure 5.

**Example 7.** Consider the following model

$$ \chi_S(x, y, z) = \bar{xyz} + \bar{xy}\bar{z} + \bar{xy} + y + x\bar{y} + x\bar{yz} + xyz, $$

as shown on Figure 5. To illustrate the objects we introduced in Section 3, we compute $x_0 = (1, \frac{2}{\sqrt{3}}, 1)$ and

$$ \Delta = \begin{pmatrix} 1 & 0 & \frac{\sqrt{70}}{10} \\ 0 & 1 & 0 \\ \frac{\sqrt{70}}{10} & 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & -1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 + \frac{\sqrt{70}}{10} & 0 \\ 0 & 0 & 1 - \frac{\sqrt{70}}{10} \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & -\frac{1}{2} \end{pmatrix}. $$

Proposition 8 does not apply here since $H$ has a dihedral factor. From the above diagonalization of $\Delta$, we can easily compute the domain $T$ in (4). Notice that

$$ S_1 = J\varphi_1 = \begin{pmatrix} -1 & 0 & -\frac{7}{5} \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad S_2 = J\varphi_2 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad S_3 = J\varphi_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & -1 \end{pmatrix}, $$

so that we can compute $(S_1S_2)^2 = (S_2S_3)^2 = \text{Id}_3$, while

$$ S_1S_3 = \begin{pmatrix} \frac{9}{5} & 0 & \frac{7}{5} \\ 0 & 1 & 0 \\ -2 & 0 & -1 \end{pmatrix} $$

has eigenvalues 1 and $\frac{2\pm i\sqrt{21}}{5}$. The cosine associated with the second eigenvalue is $\frac{2}{5}$ and therefore rational. According to Niven's theorem [37], the second eigenvalue is of infinite order. The fixed point method shown earlier [21] allows us to conclude that $G$ is infinite, while by Corollary 6 we also conclude that $H$ is infinite (since $\text{Im } J$ is).
**Example 8.** Consider the model

$$ \chi_S(x, y, z) = \bar{x}y\bar{z} + \bar{x} + \bar{x}yz + \bar{z} + \bar{z}y + y + x\bar{y} + x\bar{y}z + x\bar{z}, $$

as shown in the left display on Figure 5. One easily obtains $x_0 = (1, 1, 1)$, because the drift of the model is zero, and the covariance matrix is equal to

$$ \Delta = \begin{pmatrix} 1 & -\frac{1}{3} & -\frac{1}{3} \\ -\frac{1}{3} & 1 & -\frac{1}{3} \\ -\frac{1}{3} & -\frac{1}{3} & 1 \end{pmatrix}. $$

Proposition 8 immediately implies that the group $G$ is infinite. Note that this model belongs to the set $G_1$ in [28, Tab. 1], which means that there is no non-trivial relation between the generators $\varphi_1, \varphi_2, \varphi_3$ in (6).

**Example 9.** We now look at the model on the second display in Figure 5

$$ \chi_S(x, y, z) = \bar{x}y\bar{z} + \bar{x}\bar{y} + \bar{x}z + \bar{x}y + y\bar{z} + yz + x\bar{y}\bar{z} + x\bar{y}z + xz + xy\bar{z}, $$

which also has zero drift, hence $x_0 = (1, 1, 1)$, and whose covariance matrix is the identity, as already observed in [7, Sec. 5.4]. Accordingly, the reflection group $H$ is finite and isomorphic to $(\mathbb{Z}/2\mathbb{Z})^3$. However, this model is known to admit an infinite group by [21].

## Part 2. Eigenvalues of polyhedral nodal domains

In the first part we saw that the asymptotics of the number of excursions $e_C(P, Q; n)$ in the orthant $C = \mathbb{R}_+^d$ is strongly related to the principal eigenvalue $\lambda_1$ of a Dirichlet problem on the polyhedral domain $T$ given by (11), see (3). It is therefore natural to ask which are the polyhedral domains for which it is possible to compute this eigenvalue in closed form. Let us recall some facts in dimensions two and three.

Dimension two is special and allows a systematic computation of $\lambda_1$, just by explicitly solving the eigenvalue problem. See e.g. [17, Ex. 2] and [9, Sec. 2.3] for the implementation of these calculations.

Dimension three is more complicated, and in general (i.e. for generic parameters) it is not possible to compute the eigenvalue in closed form (just as it is not possible to compute the first eigenvalue of a generic triangle in the plane $\mathbb{R}^2$ for the Dirichlet Laplacian). However, a list of polyhedral domains for which $\lambda_1$ (and actually the whole spectrum) can be computed can be found in [4, 5] by Bérard and Besson. The paper [7] explores the connection between walks in the three-dimensional orthant and these particular polyhedral domains, and proposes several examples of models corresponding to the polyhedral domains found in [4, 5].

In Part 2 we extend the results of Bérard and Besson to arbitrary dimensions. We compute the Dirichlet eigenvalue $\lambda_1$ of polyhedral domains which are also nodal domains of $\mathbb{S}^{d-1}$, and we classify all such domains. We show that they must be the intersection of a chamber of a finite Coxeter group with $\mathbb{S}^{d-1}$.

Part 2 consists of three sections. First, the main Theorem 14 is stated and proved in Section 5. In Section 6 we apply Theorem 14 to the case of small dimensions two, three and four and completely classify the polyhedral nodal domains. In this way we recover the existing results of Bérard and Besson [4, 5] in dimension three and of Choe and Soret [14] in dimension four. Finally, in Section 7 we give three examples that connect the first and second parts of our work. We consider some
models of walks in arbitrary dimension and show how to explicitly compute their first eigenvalue $\lambda_1$ and asymptotic exponent $\alpha$ in (3).

## 5. POLYHEDRAL NODAL DOMAINS AND THEIR PRINCIPAL EIGENVALUES

Let $d \ge 2$ and $(\mathbb{S}^{d-1}, \sigma_{d-1})$ be the $(d-1)$-dimensional sphere

$$ \mathbb{S}^{d-1} = \{(x_1, \dots, x_d) \in \mathbb{R}^d : x_1^2 + \dots + x_d^2 = 1\}, $$

equipped with its natural Riemannian metric $\sigma_{d-1}$ obtained as the restriction of the Euclidean metric of $\mathbb{R}^d$.

**Definition 13.** Let $U \subset \mathbb{S}^{d-1}$ be an open set. We say that $U$ is a polyhedral domain if

$$ U = \mathbb{S}^{d-1} \cap H_1^+ \cap \dots \cap H_r^+, \qquad (26) $$

where for all $i$, $H_i^+$ is a half-space of $\mathbb{R}^d$ whose boundary is a linear hyperplane $H_i$. If $U$ is a polyhedral domain, the number $r$, which is assumed to be minimal in (26), is the number of sides of $U$.

See Figure 2 for examples of polyhedral domains in two and three dimensions. The domain $T$ in (26) as well as the orthant $\mathbb{R}_+^d$ are other examples of polyhedral domains.

We denote by $\Delta_d$ the Laplacian on $\mathbb{R}^d$ and by $\Delta_{\sigma_{d-1}}$ the Laplace-Beltrami operator on $\mathbb{S}^{d-1}$, see [31, Sec. 3.2.3]. We are interested in polyhedral domains which are also nodal domains of $\mathbb{S}^{d-1}$, i.e., for which there exists $\phi \in C^\infty(\mathbb{S}^{d-1})$ such that $\phi$ is an eigenfunction of $-\Delta_{\sigma_{d-1}}$ which satisfies $\phi > 0$ on $U$ and $\phi = 0$ on $\partial U = \cup_{i=1}^r (H_i \cap \bar{U})$. Note that, by [31, Prop. 4.5.8], since $\phi$ has a constant sign on $U$, $\phi$ is then an eigenfunction associated to the first eigenvalue $\lambda_1(U)$ for the Dirichlet problem on $(U, \sigma_{d-1})$. In the following, if $H$ is a hyperplane of $\mathbb{R}^d$, we denote by $s_H$ the orthogonal reflection with respect to $H$. We prove:

**Theorem 14.** Let $U = \mathbb{S}^{d-1} \cap H_1^+ \cap \dots \cap H_r^+$ be a polyhedral domain as in (26). Then $U$ is nodal if and only if there exists a finite set $\Lambda$ of hyperplanes such that

* $U$ is a connected component of $\mathbb{S}^{d-1} \cap (\cup_{H \in \Lambda} H)$;

* the Coxeter group $W := \langle s_H | H \in \Lambda \rangle \subset O(d)$ is finite and acts on $\Lambda$.

Moreover, if $U$ satisfies the conditions above, let $k := \#\Lambda$. Then the first eigenvalue of $U$ for the Dirichlet problem is

$$ \lambda_1(U) = k(d - 2 + k). $$

We recall that finite Coxeter groups are reflection groups (see Appendix A). These groups have been extensively studied and are all classified. This allows us to classify all polyhedral nodal domains and compute their associated first eigenvalue. We give the complete list for $d = 2, 3, 4$ in Section 6, i.e., we give the complete list of polyhedral nodal domains of $\mathbb{S}^1, \mathbb{S}^2$ and $\mathbb{S}^3$.

5.1. Preliminary results. Before proving Theorem 14, we need some preliminary results. We first recall a well-known result (see for instance [31, Sec. 5.1.3]).

**Theorem 15.** Assume that $\phi \in C^\infty(\mathbb{S}^{d-1})$, $\phi \ne 0$ satisfies $-\Delta_{\sigma_{d-1}}\phi = \lambda\phi$. Then $\phi$ is the restriction to $\mathbb{S}^{d-1}$ of a homogeneous harmonic polynomial $P$ of $\mathbb{R}^d$. Moreover, if $k$ is the degree of $P$, then $\lambda = k(d - 2 + k)$.

We need the following lemma (the proof of which follows directly from the analyticity of $P|_H$):
**Lemma 16.** Let $P$ be a polynomial on $\mathbb{R}^d$, $H \subset \mathbb{R}^d$ a hyperplane and $V$ an open set having a non-empty intersection with $H$. Assume that $P \equiv 0$ on $H \cap V$. Then $P \equiv 0$ on $H$.

Let $\Lambda$ be a finite set of hyperplanes such that the Coxeter group $W := \langle s_H | H \in \Lambda \rangle \subset O(d)$ is finite and acts on $\Lambda$. For $g \in W$, denote $g \cdot P = P \circ g$.

**Definition 17.** A polynomial $P$ on $\mathbb{R}^d$ is antisymmetric if for all $g \in W$, $g \cdot P = \det(g)P$.

For all $H \in \Lambda$, choose a unit vector $e_H$ orthogonal to $H$ and define $f_H = \langle e_H, \cdot \rangle$ so that $f_H$ is a linear form whose kernel is $H$. Define

$$P_0 := \prod_{H \in \Lambda} f_H. \qquad (27)$$

Then, we will need the following lemma which can also be found in [4, Prop. 3].

**Lemma 18.** The polynomial $P_0$ in (27) is antisymmetric. Moreover, if $P$ is any antisymmetric polynomial, then $P_0$ divides $P$.

*Proof.* We start by proving the second statement. Take an orthonormal basis $(f_1, \dots, f_d)$ such that $f_1 = e_H$ and $f_i \in H$ for all $i \ge 2$. Consider the associated coordinates $(y_1, \dots, y_d)$ so that $f_H = y_1$. Then $P$ can be written as

$$P = \sum_{i=0}^{k} y_1^i Q_i,$$

where for all $i$, $Q_i$ is a polynomial on $\mathbb{R}^d$ which does not depend on $y_1$. The antisymmetry property of $P$ means that $P(-y_1, y_2, \dots, y_d) = -P(y_1, y_2, \dots, y_d)$, which implies that $Q_0 = 0$ and thus $f_H = y_1$ divides $P$. Since for all $H \in \Lambda$, $f_H$ is irreducible and divides $P$, and since the ring of polynomials on $\mathbb{R}^d$ is factorial, this means that $P_0$ divides $P$.

Let us now prove that $P_0$ is antisymmetric. Let $H \in \Lambda$ and consider the set

$$\Lambda_0 := \{H' \in \Lambda \setminus \{H\} | s_H(H') = H'\},$$

so that $H' \in \Lambda_0$ if and only if $H' \perp H$. Define also $\Lambda'$ as a set of representatives of the orbits for the action of the group $\{\mathrm{Id}, s_H\}$ on $\Lambda \setminus \Lambda_0$. Then

$$(\Lambda_0, \Lambda', s_H(\Lambda'))$$

is a partition of $\Lambda$. Let us write (27) under the form

$$P_0 = f_H \prod_{H' \in \Lambda_0} f_{H'} \prod_{H' \in \Lambda'} \alpha_{H'}$$

where $\alpha_{H'} = f_{H'} f_{s_H(H')}$. Then, note that

* $s_H \cdot f_H = -f_H$,

* $s_H \cdot f_{H'} = f_{H'}$ if $H' \in \Lambda_0$,

* $s_H \cdot \alpha_{H'} = \alpha_{H'}$ if $H' \in \Lambda'$,

which implies that $s_H \cdot P_0 = -P_0$ and thus $P_0$ is antisymmetric. $\square$
5.2. **Proof of Theorem 14.** Let $U$ be a polyhedral domain as in (26). Assume that there exists a finite set $\Lambda$ of hyperplanes such that

* $U$ is a connected component of $\mathbb{S}^{d-1} \cap (\cup_{H \in \Lambda} H)$;

* the Coxeter group $W := \langle s_H | H \in \Lambda \rangle \subset O(d)$ is finite and acts on $\Lambda$.

Define $P_0$ as in (27). Since the Laplacian operator $\Delta_d$ commutes with the action of $W$, then for all $g \in W$, $g \cdot \Delta_d P_0 = \Delta_d(g \cdot P_0)$. By Lemma 18, $P_0$ is antisymmetric and we obtain that $\Delta_d P_0$ is also antisymmetric. Again by Lemma 18, $P_0$ must divide $\Delta_d P_0$ and thus must be 0 since $\deg(\Delta_d P_0) < P_0$. Hence, $P_0$ is a homogeneous harmonic polynomial and, by Theorem 15, its restriction to the sphere is an eigenfunction for the eigenvalue $k(d-2+k)$, where $k = \deg(P_0) = \#\Lambda$. Since $P_0$ vanishes only on $\cup_{H \in \Lambda} H$, it does not vanish on $U$ and thus $U$ is a nodal domain.

Conversely, assume that $U$ is a nodal domain as in (26). Then there exists an eigenfunction $\phi$ of $\Delta_{\sigma_{d-1}}$ on $\mathbb{S}^{d-1}$ which is positive on $U$ and vanishes on $\partial U$. By Theorem 15, $\phi$ is the restriction to $\mathbb{S}^{d-1}$ of a homogeneous harmonic polynomial $P$. By assumption, for all $i$, $P$ vanishes on $H_i \cap \bar{U}$ and since $P$ is homogeneous, vanishes on the cone

$$ \{t(H_i \cap \bar{U}) | t \in \mathbb{R}\}, $$

whose interior in $H_i$ is not empty. By Lemma 16, $P$ vanishes on $H_i$.

Let now $\Lambda$ be the set of hyperplanes on which $P$ is identically 0 ($\Lambda$ contains the $H_i$ and possibly other hyperplanes). We first observe that $\Lambda$ is finite. Otherwise $P$ would vanish on an infinite number of hyperplanes and by analyticity, would vanish everywhere. Let $W := \langle s_H | H \in \Lambda \rangle$. We prove that

* $W$ acts on $\Lambda$. Given $H \in \Lambda$, consider the two open half-spaces $H^+$ and $H^-$ delimited by $H$. Define

$$ g: \begin{array}{c|c} P + s_H \cdot P & \text{on } \overline{H^+}, \\ 0 & \text{on } H^- \end{array} $$

On $H$, $\partial_{e_H}(P + s_H \cdot P) = 0$. Since $P + s_H \cdot P$ vanishes on $H$ and is harmonic, $\partial_{e_H}^2(P + s_H \cdot P) = 0$, which implies that $g$ is $C^2$, harmonic and vanishes on a half-space; it must vanish everywhere. We deduce that $P + s_H \cdot P = 0$. Since $H \in \Lambda$ is arbitrary and since the $\{s_H | H \in \Lambda\}$ is a system of generators of $W$, we get that for all $g \in W$, $g \cdot P = \det(g)P$, which means that $P$ is antisymmetric with respect to $W$. In particular, if $P$ vanishes everywhere on $H \in \Lambda$, it vanishes also everywhere on $g \cdot H$ with, by definition of $\Lambda$, implies that $g \cdot H \in \Lambda$. This proves that $W$ acts on $\Lambda$.

* $W$ is finite. Assume $W$ is infinite and set $\Gamma = \cup_{H \in \Lambda} \{e_H, -e_H\}$. Then $W$ acts also on $\Gamma$. Since $W$ is infinite, there exists $e \in \Gamma$ such that the stabilizer

$$ W_e = W_{-e} = \{g \in W | g \cdot \pm e = \pm e\} $$

is infinite. Then $W_e$ acts on $\Gamma \setminus \{e, -e\}$. By the same argument, there exists $e' \in \Gamma \setminus \{e, -e\}$ such that the stabilizer $(W_e)_{e'} = W_e \cap W_{e'}$ is infinite. By an immediate induction, we show that the intersection of all stabilizers $W_0 = \cap_{e \in \Gamma} W_e$ is infinite. Now set $V = \text{span}\Gamma$. Then $W_0$ acts on $V$ as $\{\text{Id}\}$ (since it acts as $\{\text{Id}\}$ on a basis of $V$). Notice that if $x \in V^{\perp}$ then $x \in \cap_{H \in \Lambda} H$ and thus is invariant under the action of $W$ and thus of $W_0$. This means that $W_0$ acts on $V$ and $V^{\perp}$ as $\{\text{Id}\}$ and thus $W_0 = \{\text{Id}\}$, which is a contradiction.
• Conclusion. Let $C = \cup_{t>0} tU$. Clearly $C$ is connected, does not intersect $\cup_{H \in \Lambda} H$ (since $P$ does not vanish on $C$) and any point of $\partial U$ belongs to $\cup_{H \in \Lambda} H$. This means that $C$ is a connected component of $\mathbb{R}^d \setminus (\cup_{H \in \Lambda} H)$, which implies that $U$ is a connected component of $\mathbb{S}^{d-1} \cap (\cup_{H \in \Lambda} H)$.

## 6. CLASSIFICATION OF POLYHEDRAL NODAL DOMAINS IN SMALL DIMENSIONS

Let $U = \mathbb{S}^{d-1} \cap H_1^+ \cap \cdots \cap H_r^+$ be a polyhedral domain with $r$ sides, as in (26). It is completely characterized (up to an isometry) by the $\frac{r(r-1)}{2}$ angles $\alpha_{i,j} := (\hat{H_i}, \hat{H_j})$, $i < j$. In this section, we give the exact list of angles for which $U$ is nodal. For any given polyhedral domain $U$, we will set

$$a(U) = (\alpha_{1,2}, \dots, \alpha_{1,r}, \alpha_{2,3}, \dots, \alpha_{2,r}, \dots, \alpha_{r-1,r}).$$

The following matrix representation of the (cosine of the) angles also appears in the literature (see e.g. [10, Chap. 5]):

$$ \begin{pmatrix} 1 & -\cos \alpha_{1,2} & \cdots & \cdots & -\cos \alpha_{1,r} \\ -\cos \alpha_{1,2} & 1 & -\cos \alpha_{2,3} & \cdots & -\cos \alpha_{2,r} \\ \vdots & -\cos \alpha_{2,3} & \ddots & \ddots & \vdots \\ \vdots & \cdots & \ddots & 1 & -\cos \alpha_{r-1,r} \\ -\cos \alpha_{1,r} & \cdots & \cdots & \cos \alpha_{r-1,r} & 1 \end{pmatrix}. $$

Interestingly, by Proposition 4 the above matrix corresponds exactly to our covariance matrix $\Delta$ in (10).

We will say that a $\frac{r(r-1)}{2}$-tuple $a$ is admissible if there exists a polyhedral nodal domain $U$ such that $a(U) = a$. From Theorem 14, to each finite Coxeter group $W$ acting on $\mathbb{R}^d$ corresponds a unique polyhedral domain (uniqueness comes from the fact that all chambers are isometric). We then use the classification of irreducible Coxeter groups to classify these domains, as given in [27, Chap. 2].

Let $W = W_1 \times \cdots \times W_m$ be a Coxeter group of $\mathbb{R}^d$. We use the decomposition $\mathbb{R}^d = (\oplus_{i=1}^m V_i) \oplus Z$ of Appendix A; the quantity $r = d - \dim Z$ is the rank of $W$. Since in the whole paper (except in Example 11), we deal with Coxeter groups of rank $d$ in $\mathbb{R}^d$, we reduce here the computation to the case where $W$ has rank $d$, i.e.

$$ \mathbb{R}^d = \bigoplus_{i=1}^m V_i \qquad (28) $$

and $U$ has exactly $r = d$ sides. In a second step, we will classify the $\frac{d(d-1)}{2}$-admissible tuples.

Observe that if $\sigma$ is a permutation of $\{1, \dots, d\}$, then $a(U) = (\alpha_{i,j})$ is admissible if and only if $a(V) = (\alpha_{\sigma(i),\sigma(j)})$ is admissible, since the polyhedral domain $V$ can be obtained by $U$ by an isometry permuting the indices. In particular, in the classification below, we just choose one admissible tuple in each class under the action of the permutation group.

We will denote $k_1, \dots, k_m$ the dimensions of the $V_i$ in (28), or equivalently, the ranks of the irreducible Coxeter groups $W_i$. Note that, with the notation of Appendix A, it holds that $\#\Lambda = \sum_{i=1}^m \#\Lambda_i$. In the following, we use the classification of Coxeter groups given in [27, Chap. 2]. Note that in this classification the Coxeter group $A_d$ is isomorphic to the permutation group $S_{d+1}$. We use this several times in the paper.
6.1. **Dimension two.** For $n = 2$, there is no need to use Theorem 14: up to an isometry, a nodal domain is just of the form $U_0 = \mathbb{S}^1$ or $U_k = \{(\cos(t), \sin(t))|t \in (0, \frac{\pi}{k})\}$ for some $k \ge 1$. In the latter case, using the same notation as in Example 2, the Coxeter group $W$ is the dihedral group $D_{2k}$ of order $2k$.

6.2. **Dimension three.** Here $\frac{d(d-1)}{2} = 3$ and we give all admissible triplets and the corresponding $\lambda_1(U)$.

<figure><img src="image_9.png" /><figcaption>FIGURE 6. Classification of reducible (on the left) and irreducible (on the right) Coxeter groups in dimension $d=3$. For each graph, the set of vertices is $a(U)$, and two vertices $\alpha$ and $\beta$ are connected by an edge if $m(\alpha, \beta) \ge 3$, where $m(\alpha, \beta)$ is the order of $\alpha\beta$. In this case, the edge connecting $\alpha$ to $\beta$ is labeled with $m(\alpha, \beta)$ (this label is omitted if $m(\alpha, \beta) = 3$). Two vertices $\alpha$ and $\beta$ that are not connected satisfy $m(\alpha, \beta) = 2$. The Coxeter groups $A_3$ and $B_3$ belong to one-parameter families $A_d$ and $B_d$, which will be properly introduced in Examples 11 and 12, respectively.</figcaption></figure>

We recall that $m$ is the number of irreducible components of $W$ (see (28)) and $k_1, \dots, k_m$ are the ranks of these irreducible components. See Figure 6 for some important definitions. The following is a list of possible cases:

• $m=3$, then necessarily $k_1 = k_2 = k_3 = 1$. Then $a(U) = (\pi/2, \pi/2, \pi/2)$, $W = \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ and $\#\Lambda = 3$, so by Theorem 14, $\lambda_1(U) = 12$.

• $m=2$, then (up to a permutation) $k_1 = 1$ and $k_2 = 2$. Then there exists $k \ge 2$ such that $a(U) = (\pi/2, \pi/2, \pi/4)$, $W = \mathbb{Z}/2\mathbb{Z} \times D_{2k}$ and $\#\Lambda = k+1$, so by Theorem 14, $\lambda_1(U) = (k+1)(k+2)$.

• $m=1, k_1=3$. Then, the list of admissible triplets are
  - $a(U) = (\pi/3, \pi/2, \pi/3)$, $W = A_3$, $\#\Lambda = 6$, so by Theorem 14, $\lambda_1(U) = 42$;
  - $a(U) = (\pi/3, \pi/2, \pi/4)$, $W = B_3$, $\#\Lambda = 9$, so by Theorem 14, $\lambda_1(U) = 90$;
  - $a(U) = (\pi/5, \pi/2, \pi/3)$, $W = H_3$, $\#\Lambda = 15$, so by Theorem 14, $\lambda_1(U) = 240$.

6.3. **Dimension four.** We shall use the classification of Coxeter groups in dimension four, which we now recall:
<figure><img src="image_10.png" /><figcaption>FIGURE 7. Classification of reducible (on the left) and irreducible (on the right) Coxeter groups in dimension $d = 4$.</figcaption></figure>

We now classify all admissible 6-tuples (up to isometry) and recover the classification done in dimension four by Choe and Soret in [14, Sec. 5]:

* $m = 4, k_1 = k_2 = k_3 = k_4 = 1$. Then $a(U) = (\frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{2})$, $W = (\frac{Z}{2Z})^4$ and $\sharp\Lambda = 4$, so by Theorem 14, $\lambda_1(U) = 24$;

* $m = 3, k_1 = 2, k_2 = k_3 = 1$. Then $a(U) = (\frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{2})$, $k \ge 2$, $W = (\frac{Z}{2Z})^2 \times D_{2k}$ and $\sharp\Lambda = k + 2$, so by Theorem 14, $\lambda_1(U) = (k+2)(k+4)$;

* $m = 2, k_1 = k_2 = 2$. Then $a(u) = (\frac{\pi}{k}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{k'})$, $k, k' \ge 2$, $W = D_{2k} \times D_{2k'}$ and $\sharp\Lambda = k + k'$, so by Theorem 14, $\lambda_1(U) = (k+k')(k+k'+2)$;

* $m = 2, k_1 = 3, k_2 = 1$. Using the classification in dimension 3 (see Figure 6 on the right), we obtain the following cases:

- $a(U) = (\frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{3}, \frac{\pi}{3})$, $W \simeq A_3 \times \frac{Z}{2Z}$ and $\sharp\Lambda = 7$, so by Theorem 14, $\lambda_1(U) = 63$;

- $a(U) = (\frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{3}, \frac{\pi}{4})$, $W \simeq B_3 \times \frac{Z}{2Z}$ and $\sharp\Lambda = 10$, so by Theorem 14, $\lambda_1(U) = 120$;

- $a(U) = (\frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{3}, \frac{\pi}{5})$, $W \simeq H_3 \times \frac{Z}{2Z}$ and $\sharp\Lambda = 16$, so by Theorem 14, $\lambda_1(U) = 288$;

* $m = 1, k_1 = 4$. There are five possibilities:

- $a(U) = (\frac{\pi}{3}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{3}, \frac{\pi}{3})$, $W = A_4$, $\sharp\Lambda = 10$, $\lambda_1(U) = 120$;

- $a(U) = (\frac{\pi}{3}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{3}, \frac{\pi}{4})$, $W = B_4$, $\sharp\Lambda = 16$, $\lambda_1(U) = 272$;

- $a(U) = (\frac{\pi}{3}, \frac{\pi}{3}, \frac{\pi}{3}, \frac{\pi}{2}, \frac{\pi}{2})$, $W = D_4$, $\sharp\Lambda = 12$, $\lambda_1(U) = 168$;

- $a(U) = (\frac{\pi}{3}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{4}, \frac{\pi}{3})$, $W = F_4$, $\sharp\Lambda = 24$, $\lambda_1(U) = 624$;

- $a(U) = (\frac{\pi}{5}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{3}, \frac{\pi}{3})$, $W = H_4$, $\sharp\Lambda = 60$, $\lambda_1(U) = 3720$.

### 7. THREE EXAMPLES

To conclude this part, we give three examples where our results allow $\lambda_1$ to be computed explicitly. We recall (see Theorem 1) that $\lambda_1$ is the smallest eigenvalue of the Dirichlet problem (1), and its explicit value gives the asymptotics (1) of the number of excursions between two points.

**Example 10.** Consider the 4-dimensional model whose inventory (5) is given by

$$ \chi_S(x, y, z, w) = \bar{w} + x\bar{z} + \bar{x}y + z + \bar{y}w. $$
This is model 37 in [12, Tab. 3], whose group $G$ is proved in [12] to be isomorphic to the symmetry group $\mathfrak{S}_5$. We have $x_0 = (1, 1, 1, 1)$ and a simple calculation gives

$$ \Delta = \begin{pmatrix} 1 & -\frac{1}{2} & -\frac{1}{2} & 0 \\ -\frac{1}{2} & 1 & 0 & -\frac{1}{2} \\ -\frac{1}{2} & 0 & 1 & 0 \\ 0 & -\frac{1}{2} & 0 & 1 \end{pmatrix}. $$

Using the notation of Section 6, the list of angles between the hyperplanes bounding $\Delta^{-\frac{1}{2}}\mathbb{R}_+^d$ is given by Proposition 3 and its consequence (18): $(\frac{\pi}{3}, \frac{\pi}{3}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{3}, \frac{\pi}{2})$. The permutation of variables $(x, y, z, w) \to (z, x, y, w)$ gives rise to the list

$$ (\frac{\pi}{3}, \frac{\pi}{2}, \frac{\pi}{2}, \frac{\pi}{3}, \frac{\pi}{2}, \frac{\pi}{3}). $$

From the classification of Section 6.3, we obtain that $\lambda_1 = 120$.

This example is actually a particular case (up to a permutation of variables) of the $d$-dimensional example given in Section 4.4. With the same argument, one checks that for the $d$-dimensional case, it holds that $\lambda_1 = \frac{1}{4}d(d+1)(d+4)(d-1)$.

**Example 11.** Consider the simple $d$-dimensional random walk with jumps

$$ \chi_S(x_1, \dots, x_d) = x_1 + \bar{x}_1 + \dots + x_d + \bar{x}_d, $$

in the cone given by the Weyl chamber of type $A$, namely

$$ W_A = \{x_1 < x_2 < \dots < x_d\}. $$

The asymptotics of the number of such walks (sometimes called non-intersecting lattice paths) is known and the exponent $\alpha$ in (1) is given by $\alpha = \frac{d^2}{2}$; see e.g. [25, Thm 2.1], [22, Thm 1.1] and [16, Thm 1]. Let us briefly explain how this relates to our results. First, we observe that the walls of $W_A$ are the hyperplanes $H_i$, $1 \le i \le d-1$ defined by the equations $x_i = x_{i+1}$. Define $u_i = e_i - e_{i+1}$, where $(e_1, \dots, e_d)$ is the canonical basis of $\mathbb{R}^d$. Then $u_i \perp H_i$ and is clearly outward with respect to $W_A$. Since $(u_i, u_j) = \|u_i\|\|u_j\| \cos(\widehat{u_i u_j})$, we obtain that

$$ \widehat{H_i H_j} = \pi - \widehat{u_i u_j} = \begin{cases} \frac{\pi}{3} & \text{if } |i-j| = 1, \\ \frac{\pi}{2} & \text{otherwise.} \end{cases} \qquad (29) $$

From the classification of Coxeter groups, we get that $W_A$ is a chamber of the group $A_{d-1} = \mathfrak{S}_d$ which is a $(d-1)$-rank Coxeter group. We use our Theorem 14 to show that

$$ \lambda_1(U) = k(d-2+k), $$

where $k = \#\Lambda$ is the number of hyperplanes needed to define the Weyl chamber $W_A$, or equivalently the number of reflections in $A_d$, which is known to be $k = \frac{d(d-1)}{2}$. Using the formula (3), we immediately obtain $\alpha = \frac{d^2}{2}$.

**Example 12.** Considering the same random walk as in Example 11, but in the Weyl chamber of type $B$

$$ W_B = \{0 < x_1 < x_2 < \dots < x_d\}, $$

this model has also been explored in the literature, see [30, Thm 2.3] and [24, Thm 5.1]. It is also known as a model of $d$ vicious walkers models subject to a wall restriction. In particular, it is known
that the exponent is $\alpha = d^2 + \frac{d}{2}$. The chamber $W_B$ has the same walls as $W_A$ above plus $H_0$ defined by $x_1 = 0$. Clearly, beside the relations (29), we have, since $e_1$ is an inward normal vector to $H_0$,

$$ \widehat{H_0H_i} = \widehat{e_1u_i} = \begin{cases} \frac{\pi}{4} & \text{if } i = 1, \\ \frac{\pi}{2} & \text{otherwise.} \end{cases} $$

We deduce that the associated Coxeter group is the $d$-rank group $B_d$. As in Example 11, we use Theorem 14 with $k = d^2$ (corresponding to the number of reflections in $B_d$) and $\lambda_1(U) = k(d-2+k)$, and finally we use (3) and get the announced value of the exponent $\alpha$.

## APPENDIX A. COXETER GROUPS

In this section we recall some facts about Coxeter groups used throughout our article; they can all be found in [27].

**Definition 19.** Let $W$ be a group.

* A Coxeter system is a set $S \subset W$ of generators, subject only to relations $(ss')^{m(s,s')} = 1$ for all $s, s' \in S$. Here $m(s, s') \in \mathbb{N}$ satisfies $m(s, s) = 1$ and if $s \neq s'$, $m(s, s') \ge 2$.

* The group $W$ is a Coxeter group if it admits a Coxeter system.

Many results are known about Coxeter groups, but we focus on two results that play a crucial role in our paper:

**Theorem 20** (p. 16 in [27]). Let $V$ be a finite dimensional space with a scalar product $\langle \cdot, \cdot \rangle$, and let $\Lambda$ be a set of independent vectors. For each $v \in \Lambda$, let $s_v$ be the orthogonal reflection with respect to $\langle v \rangle^{\perp}$ and $W$ be the subgroup of $(V, \langle \cdot, \cdot \rangle)$ spanned by $\{s_v | v \in \Lambda\}$. Then the reflection group $W$ is a Coxeter group.

**Theorem 21** (p. 133 in [27]). Every Coxeter group can be realised as a reflection group (as in the statement of the above theorem).

Let $S$ be a Coxeter system of a finite Coxeter group $W$. All results in the following are, for example, given in [27]. The integers $m(s, s')$ in Definition 19 completely determine $W$. The classification of finite Coxeter groups implies the following

**Proposition 22.** If the Coxeter group $W$ has no irreducible component which is a dihedral group, then for all $s, s' \in S$, $m(s, s') \in \{2, 3, 4, 5, 6\}$.

Let $\Lambda$ be a set of hyperplanes of $\mathbb{R}^d$ and $W$ be the group of isometries spanned by $\{s_H | H \in \Lambda\}$. We assume that $W$ is finite. Then, there exist subspaces $V_1, \dots, V_m, Z$ of $\mathbb{R}^d, W_1, \dots, W_m$ finite irreducible Coxeter groups of $V_1, \dots, V_m$, such that

* $\mathbb{R}^d = (\bigoplus_{i=1}^m V_i) \oplus Z$ and the sum is orthogonal;

* $W = W_1 \times \dots \times W_m$;

* $W$ acts on $Z$ as the identity;

* $W_i$ acts transitively on the set $\Lambda_i$ of hyperplanes $H_i$ of $V_i$ such that

$$ H := Z \times V_1 \times \dots V_{i-1} \times H_i \times V_{i+1} \times \dots \times V_m \in \Lambda. \qquad (30) $$
In particular $\Lambda = \cup_{i=1}^{m} \Lambda_i$, where the hyperplanes of $V_i$ are identified to hyperplanes of $\mathbb{R}^d$ via Equation (30). The rank of $W$ is by definition

$$ \sum_{i=1}^{m} \dim V_i = d - \dim Z. $$

A connected component of $\mathbb{R}^d \setminus (\cup_{H \in \Lambda} H)$ is called a *chamber of W*, and the hyperplanes of $\Lambda$ which intersect the boundary of a chamber are called *walls*. With this terminology, Theorem 14 says that a polyhedral domain $U$ of $\mathbb{S}^{d-1}$ is nodal if and only if it is the intersection of the chamber of a finite Coxeter group $W$ with $\mathbb{S}^{d-1}$. A classical theorem asserts that the number of walls of a chamber is the rank of $W$. We thus deduce that the number of sides of $U$ must also be the rank of $W$ and thus must be smaller than $d$. Note also that all the chambers are isometric. Finally, in the present situation, we have:

**Theorem 23.** Let $C$ be a chamber of a finite Coxeter group and let $\Lambda_C$ be the set of hyperplanes bounding $C$. Then $S = \{s_H | H \in \Lambda_C\}$ is a Coxeter system of $W$.

## ACKNOWLEDGMENTS

We would like to thank Gérard Besson, Thomas Gobet, Jérémie Guilhot, Manuel Kauers and Cédric Lecouvey for interesting discussions. EH is supported by the project Einstein-PPF (ANR-23-CE40-0010), funded by the French National Research Agency. KR is supported by the project RAWABRANCH (ANR-23-CE40-0008), funded by the French National Research Agency. KR thanks the VIASM (Hanoï, Vietnam) for their hospitality and wonderful working conditions.

## REFERENCES

[1] A. BACHER, M. KAUERS, AND R. YATCHAK, *Continued classification of 3D lattice models in the positive octant*, in 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016), vol. BC of Discrete Math. Theor. Comput. Sci. Proc., Assoc. Discrete Math. Theor. Comput. Sci., Nancy, [2016] ©2016, pp. 95–106.

[2] C. BANDERIER AND P. FLAJOLET, *Basic analytic combinatorics of directed lattice paths*, Theor. Comput. Sci., 281 (2002), pp. 37–80.

[3] R. BAÑUELOS AND R. G. SMITS, *Brownian motion in cones*, Probab. Theory Relat. Fields, 108 (1997), pp. 299–319.

[4] P. BÉRARD AND G. BESSON, *Spectres et groupes cristallographiques. II: Domaines sphériques. (Spectra and crystallographic groups. II: Spherical domains)*, Ann. Inst. Fourier, 30 (1980), pp. 237–248.

[5] P. H. BÉRARD, *Remarques sur la conjecture de Weyl. (Remarks on the conjecture of Weyl)*, Compos. Math., 48 (1983), pp. 35–53.

[6] J. BERTOIN AND R. A. DONEY, *On conditioning a random walk to stay nonnegative*, Ann. Probab., 22 (1994), pp. 2152–2167.

[7] B. BOGOSEL, V. PERROLLAZ, K. RASCHEL, AND A. TROTIGNON, *3d positive lattice walks and spherical triangles*, J. Comb. Theory, Ser. A, 172 (2020), p. 47. Id/No 105189.

[8] A. BOSTAN, M. BOUSQUET-MÉLOU, M. KAUERS, AND S. MELCZER, *On 3-dimensional lattice walks confined to the positive octant*, Ann. Comb., 20 (2016), pp. 661–704.

[9] A. BOSTAN, K. RASCHEL, AND B. SALVY, *Non-D-finite excursions in the quarter plane*, J. Comb. Theory, Ser. A, 121 (2014), pp. 45–63.

[10] N. BOURBAKI, *Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitres IV, V et VI: Groupes de Coxeter et systèmes de Titres. Groupes engendrés par des réflexions. Systèmes de racines*. Actualités Scientifiques et Industrielles. 1337. Paris: Hermann & Cie. 288 p. F 48,00 (1968)., 1968.

[11] M. BOUSQUET-MÉLOU AND M. MISHNA, *Walks with small steps in the quarter plane*, in Algorithmic probability and combinatorics. Papers from the AMS special sessions. Chicago, IL, USA, October 5–6, 2007 and Vancouver, BC, Canada, October 4–5, 2008, Providence, RI: American Mathematical Society (AMS), 2010, pp. 1–39.
[12] M. BUCHACHER, S. HOFMANNINGER, AND M. KAUERS, *Walks with small steps in the 4d-orthant*, Ann. Comb., 25 (2021), pp. 153–166.

[13] I. CHAVEL, *Eigenvalues in Riemannian geometry. With a chapter by Burton Randol. With an appendix by Jozef Dodziuk*, vol. 115 of Pure Appl. Math., Academic Press, Academic Press, New York, NY, 1984.

[14] J. CHOE AND M. SORET, *First eigenvalue of symmetric minimal surfaces in $S^3$*, Indiana Univ. Math. J., 58 (2009), pp. 269–281.

[15] R. D. DEBLASSIE, *Exit times from cones in $\mathbb{R}^n$ of Brownian motion*, Probab. Theory Relat. Fields, 74 (1986), pp. 1–29.

[16] D. DENISOV AND V. WACHTEL, *Conditional limit theorems for ordered random walks*, Electron. J. Probab., 15 (2010), pp. 292–322. Id/No 11.

[17] ——, *Random walks in cones*, Ann. Probab., 43 (2015), pp. 992–1044.

[18] ——, *Alternative constructions of a harmonic function for a random walk in a cone*, Electron. J. Probab., 24 (2019), p. 26. Id/No 92.

[19] Y. DOUMERC AND N. O'CONNELL, *Exit problems associated with finite reflection groups*, Probab. Theory Relat. Fields, 132 (2005), pp. 501–538.

[20] T. DREYFUS, C. HARDOUIN, J. ROQUES, AND M. F. SINGER, *On the nature of the generating series of walks in the quarter plane*, Invent. Math., 213 (2018), pp. 139–203.

[21] D. K. DU, Q.-H. HOU, AND R.-H. WANG, *Infinite orders and non-D-finite property of 3-dimensional lattice walks*, Electron. J. Comb., 23 (2016), pp. research paper p3.38, 15.

[22] P. EICHELSBACHER AND W. KÖNIG, *Ordered random walks*, Electron. J. Probab., 13 (2008), pp. 1307–1336.

[23] G. FAYOLLE, R. IASNOGORODSKI, AND V. MALYSHEV, *Random walks in the quarter plane. Algebraic methods, boundary value problems, applications to queueing systems and analytic combinatorics*, vol. 40 of Probab. Theory Stoch. Model., Cham: Springer, 2nd edition, previously published with the subtitle Algebraic methods, boundary value problems and applications ed., 2017.

[24] T. FEIERL, *Asymptotics for the number of walks in a Weyl chamber of type B*, Random Struct. Algorithms, 45 (2014), pp. 261–305.

[25] ——, *Asymptotics for the number of zero drift reflectable walks in a Weyl chamber of type A*. Preprint, arXiv:1806.05998 [math.CO] (2018), 2018.

[26] L. HILLAIRET, H. JENNE, AND K. RASCHEL, *Lattice walks confined to an octant in dimension 3: (non-rationality of the second critical exponent*, Ann. Inst. Henri Poincaré D, Comb. Phys. Interact., 11 (2024), pp. 683–713.

[27] J. E. HUMPHREYS, *Reflection groups and Coxeter groups*, vol. 29 of Camb. Stud. Adv. Math., Cambridge etc.: Cambridge University Press, 1990.

[28] M. KAUERS AND R.-H. WANG, *Lattice walks in the octant with infinite associated groups*, in Extended abstracts of the ninth European conference on combinatorics, graph theory and applications, EuroComb 2017, Vienna, Austria, August 28 – September 1, 2017, Amsterdam: Elsevier, 2017, pp. 703–709.

[29] M. KAUERS AND R. YATCHAK, *Walks in the quarter plane with multiple steps*, in Proceedings of the 27th international conference on formal power series and algebraic combinatorics, FPSAC 2015, Daejeon, South Korea, July 6–10, 2015, Nancy: The Association. Discrete Mathematics & Theoretical Computer Science (DMTCS), 2015, pp. 25–36.

[30] W. KÖNIG AND P. SCHMID, *Random walks conditioned to stay in Weyl chambers of type C and D*, Electron. Commun. Probab., 15 (2010), pp. 286–296.

[31] O. LABLÉE, *Spectral theory in Riemannian geometry*, EMS Textb. Math., Zürich: European Mathematical Society (EMS), 2015.

[32] C. LECOUVEY, E. LESIGNE, AND M. PEIGNÉ, *Random walks in Weyl chambers and crystals*, Proc. Lond. Math. Soc. (3), 104 (2012), pp. 323–358.

[33] V. A. MALYSHEV, *Positive random walks and Galois theory*, Usp. Mat. Nauk, 26 (1971), pp. 227–228.

[34] H. MATSUMOTO, *Générateurs et relations des groupes de Weyl généralisées*, C. R. Acad. Sci., Paris, 258 (1964), pp. 3419–3422.

[35] S. MELCZER AND M. MISHNA, *Asymptotic lattice path enumeration using diagonals*, Algorithmica, 75 (2016), pp. 782–811.

[36] S. MELCZER AND M. C. WILSON, *Higher dimensional lattice walks: connecting combinatorial and analytic behavior*, SIAM J. Discrete Math., 33 (2019), pp. 2140–2174.

[37] I. NIVEN, *Irrational numbers*, vol. 11 of Carus Math. Monogr., Mathematical Association of America, Washington, DC, 1956.

[38] K. RASCHEL, *Green functions for killed random walks in the Weyl chamber of Sp(4)*, Ann. Inst. Henri Poincaré, Probab. Stat., 47 (2011), pp. 1001–1019.

[39] N. T. VAROPOULOS, *Potential theory in conical domains*, Math. Proc. Camb. Philos. Soc., 125 (1999), pp. 335–384.
[40] R. YATCHAK, Automated positive part extraction for lattice path generating functions in the octant, in Extended abstracts of the ninth European conference on combinatorics, graph theory and applications, EuroComb 2017, Vienna, Austria, August 28 – September 1, 2017, Amsterdam: Elsevier, 2017, pp. 1061–1067.

UNIVERSITÉ DE TOURS, INSTITUT DENIS POISSON, TOURS, FRANCE. EMAIL: lea.gohier@univ-tours.fr

UNIVERSITÉ DE TOURS, INSTITUT DENIS POISSON, TOURS, FRANCE. EMAIL: emmanuel.humbert@univ-tours.fr

CNRS, INTERNATIONAL RESEARCH LABORATORY FRANCE-VIETNAM IN MATHEMATICS AND ITS APPLICATIONS, VIETNAM INSTITUTE FOR ADVANCED STUDY IN MATHEMATICS, HANOI, VIETNAM. EMAIL: raschel@math.cnrs.fr