The Max-Plus Martin Boundary

Marianne Akian, Stéphane Gaubert, and Cormac Walsh

Received: June 3, 2005 Revised: May 17, 2009

Communicated by Alfred K. Louis

Abstract. We develop an idempotent version of probabilistic potential theory. The goal is to describe the set of max-plus harmonic functions, which give the stationary solutions of deterministic optimal control problems with additive reward. The analogue of the Martin compactification is seen to be a generalisation of the compactification of metric spaces using (generalised) Busemann functions. We define an analogue of the minimal Martin boundary and show that it can be identified with the set of limits of “almost-geodesics”, and also the set of (normalised) harmonic functions that are extremal in the max-plus sense. Our main result is a max-plus analogue of the Martin representation theorem, which represents harmonic functions by measures supported on the minimal Martin boundary. We illustrate it by computing the eigenvectors of a class of Lax-Oleinik semigroups with nondifferentiable Lagrangian: we relate extremal eigenvector to Busemann points of normed spaces.

2000 Mathematics Subject Classification: Primary 31C35; Secondary 49L20, 47175. Keywords and Phrases: Martin boundary, metric boundary, potential theory, Lax-Oleinik semigroup, weak KAM solutions, max-plus algebra, dynamic programming, deterministic optimal control, Markov decision process, eigenvalues, eigenvectors, Busemann functions, extremal generators.

This work was started during a post-doctoral stay of the third author at INRIA, supported by an ERCIM-INRIA fellowship

Documenta Mathematica 14 (2009) 195–240

196 Marianne Akian, Stéphane Gaubert, and Cormac Walsh

1 Introduction

There exists a correspondence between classical and idempotent analysis, which was brought to light by Maslov and his collaborators [Mas87, MS92, KM97, LMS01]. This correspondence transforms the heat equation to an Hamilton-Jacobi equation, and Markov operators to dynamic programming operators. So, it is natural to consider the analogues in idempotent analysis of harmonic functions, which are the solutions of the following equation

u_{i} = sup_{j∈S}(A_{ij} + u_{j})  for all i ∈ S.  (1)

The set S and the map A : S × S → ℝ ∪ {−∞}, (i, j) ↦ A_{ij}, which plays the role of the Markov kernel, are given, and one looks for solutions u : S → ℝ ∪ {−∞}, i ↦ u_{i}. This equation is the dynamic programming equation of a deterministic optimal control problem with infinite horizon. In this context, S is the set of states, the map A gives the weights or rewards obtained on passing from one state to another, and one is interested in finding infinite paths that maximise the sum of the rewards. Equation (1) is linear in the max-plus algebra, which is the set ℝ ∪ {−∞} equipped with the operations of maximum and addition. The term idempotent analysis refers to the study of structures such as this, in which the first operation is idempotent. In potential theory, one uses the Martin boundary to describe the set of harmonic and super-harmonic functions of a Markov process, and the final behaviour of its paths. Our goal here is to obtain analogous results for Equation (1). The original setting for the Martin boundary was classical potential theory [Mar41], where it was used to describe the set of positive solutions of Laplace’s equation. Doob [Doo59] gave a probabilistic interpretation in terms of Wiener processes and also an extension to the case when time is discrete. His method was to first establish an integral representation for super-harmonic functions and then to derive information about final behaviour of paths. Hunt [Hun60] showed that one could also take the opposite approach: establish the results concerning paths probabilistically and then deduce the integral representation. The approach taken in the present paper is closest to that of Dynkin [Dyn69], which contains a simplified version of Hunt’s method. There is a third approach to this subject, using Choquet theory. However, at present, the tools in the max-plus setting, are not yet sufficiently developed to allow us to take this route. Our starting point is the max-plus analogue of the Green kernel,

A_{ij}^{∗} := sup{A_{i_{0}i_{1}} + ⋯ + A_{i_{n−1}i_{n}} | n ∈ ℕ, i_{0}, …, i_{n} ∈ S, i_{0} = i, i_{n} = j} .

Thus, A_{ij}^{∗} is the maximal weight of a path from i to j. We fix a map i ↦ σ_{i}, from S to ℝ ∪ {−∞}, which will play the role of the reference measure. We set π_{j} := sup_{k∈S} σ_{k} + A_{kj}^{∗}. We define the max-plus Martin space ℳ to be the closure of the set of maps 𝒦 := {A_{·j}^{∗} − π_{j} | j ∈ S} in the product topology, and the Martin boundary to be ℳ \ 𝒦 . This term must be used with caution however, since 𝒦 may not be open in ℳ (see Example 10.6). The reference measure is often chosen to be a max-plus Dirac function, taking the value 0 at some basepoint b ∈ S and the value −∞ elsewhere. In this case, π_{j} = A_{bj}^{∗}. One may consider the analogue of an “almost sure” event to be a set of outcomes (in our case paths) for which the maximum reward over the complement is −∞. So we are lead to the notion of an “almost-geodesic”, a path of finite total reward, see Section 7. The almost sure convergence of paths in the probabilistic case then translates into the convergence of every almost-geodesic to a point on the boundary. The spectral measure of probabilistic potential theory also has a natural analogue, and we use it to give a representation of the analogues of harmonic functions, the solutions of (1). Just as in probabilistic potential theory, one does not need the entire Martin boundary for this representation, a particular subset, called the minimal Martin space, will do. The probabilistic version is defined in [Dyn69] to be the set of boundary points for which the spectral measure is a Dirac measure located at the point itself. Our definition (see Section 4) is closer to an equivalent definition given in the same paper in which the spectral measure is required only to have a unit of mass at the point in question. The two definitions are not equivalent in the max-plus setting and this is related to the main difference between the two theories: the representing max-plus measure may not be unique. Our main theorem (Theorem 8.1) is that every (max-plus) harmonic vector u that is integrable with respect to π, meaning that sup_{j∈S} π_{j} + u_{j} < ∞, can be represented as

u = sup_{w∈ℳ^{m}} ν(w) + w,  (2)

where ν is an upper semicontinuous map from the minimal Martin space ℳ^{m} to ℝ ∪ {−∞}, bounded above. The map ν is the analogue of the density of the spectral measure. We also show that the (max-plus) minimal Martin space is exactly the set of (normalised) harmonic functions that are extremal in the max-plus sense, see Theorem 8.3. We show that each element of the minimal Martin space is either recurrent, or a boundary point which is the limit of an almost-geodesic (see Corollary 7.7 and Proposition 7.8). To give a first application of our results, we obtain in Corollary 11.3 an existence theorem for non-zero harmonic functions of max-plus linear kernels satisfying a tightness condition, from which we derive a characterisation of the spectrum of some of these kernels (Corollary 11.4). To give a second application, we obtain in Section 12 a representation of the eigenvectors of the Lax-Oleinik semigroup [Eva98, §3.3]:

T^{t}u(x) = sup_{y∈ℝ^{n}} −tL(\frac{y − x}{t}) + u(y) ,

where L is a convex Lagrangian. This is the evolution semigroup of the Hamilton-Jacobi equation

\frac{∂u}{∂t} = L^{⋆}(∇u) ,

where L^{⋆} denotes the Legendre-Fenchel transform of L. An eigenvector with eigenvalue λ ∈ ℝ is a function u such that T^{t}u = λt + u holds for all t > 0. We compute the eigenvectors for a subclass of possibly nondifferentiable Lagrangians (Corollary 12.3 and Theorem 12.5). Results and ideas related to the ones of present paper have appeared in several works: we now discuss them. Max-plus harmonic functions have been much studied in the finite-dimensional setting. The representation formula (2) extends the representation of harmonic vectors given in the case when S is finite in terms of the critical and saturation graphs. This was obtained by several authors, including Romanovski [Rom67], Gondran and Minoux [GM77] and Cuninghame-Green [CG79, Th. 24.9]. The reader may consult [MS92, BCOQ92, Bap98, GM02, AG03, AGW05] for more background on max-plus spectral theory. Relations between max-plus spectral theory and infinite horizon optimisation are discussed by Yakovenko and Kontorer [YK92] and Kolokoltsov and Maslov [KM97, § 2.4]. The idea of “almost-geodesic” appears there in relation with “Turnpike” theorems. The max-plus Martin boundary generalises to some extent the boundary of a metric space defined in terms of (generalised) Busemann functions by Gromov in [Gro81] in the following way (see also [BGS85] and [Bal95, Ch. II]). (Note that this is not the same as the Gromov boundary of hyperbolic spaces.) If (S, d) is a complete metric space, one considers, for all y, x ∈ S, the function b_{y,x} given by

b_{y,x}(z) = d(x, z) − d(x, y) for z ∈ S .

One can fix the basepoint y in an arbitrary way. The space 𝒞 (S) can be equipped with the topology of uniform convergence on bounded sets, as in [Gro81, Bal95], or with the topology of uniform convergence on compact sets, as in [BGS85]. The limits of sequences of functions b_{y,x_{n}} ∈ 𝒞 (S), where x_{n} is a sequence of elements of S going to infinity, are called (generalised) Busemann functions. When the metric space S is proper, meaning that all closed bounded subsets of S are compact, the set of Busemann functions coincides with the max-plus Martin boundary obtained by taking A_{zx} = A_{zx}^{∗} = −d(z, x), and σ the maxplus Dirac function at the basepoint y. This follows from Ascoli’s theorem, see Remark 7.10 for details. Note that our setting is more general since −A^{∗} need not have the properties of a metric, apart from the triangle inequality (the case when A^{∗} is not symmetrical is needed in optimal control). We note that Ballman has drawn attention in [Bal95, Ch. II] to the analogy between this boundary and the probabilistic Martin boundary. The same boundary has recently appeared in the work of Rieffel [Rie02], who called it the metric boundary. Rieffel used the term Busemann point to designate those points of the metric boundary that are limits of what he calls “almost-geodesics”. We shall see in Corollary 7.13 that these are exactly the points of the max-plus minimal Martin boundary, at least when S is a proper metric space. We also relate Busemann points to extremal eigenvectors of Lax-Oleinik semigroups, in Section 12. Rieffel asked in what cases are all boundary points Busemann points. This problem, as well as the relation between the metric boundary and other boundaries, has been studied by Webster and Winchester [WW06, WW05] and by Andreev [And04, And07]. However, representation problems like the one dealt with in Theorem 8.1 do not seem to have been treated in the metric space context. Results similar to those of max-plus spectral theory have recently appeared in weak-KAM theory. In this context, S is a Riemannian manifold and the kernel A is replaced by a Lax-Oleinik semigroup, that is, the evolution semigroup of a Hamilton-Jacobi equation. Max-plus harmonic functions correspond to the weak-KAM solutions of Fathi [Fat97b, Fat97a, Fat08], which are essentially the eigenvectors of the Lax-Oleinik semigroup, or equivalently, the viscosity solutions of the ergodic Hamilton-Jacobi equation, see [Fat08, Chapter 8]. In weak-KAM theory, the analogue of the Green kernel is called the Mañe potential, the role of the critical graph is played by the Mather set, and the Aubry set is related to the saturation graph. In the case when the manifold is compact, Contreras [Con01, Theorem 0.2] and Fathi [Fat08, Theorem 8.6.1] gave a representation of the weak-KAM solutions, involving a supremum of fundamental solutions associated to elements of the Aubry set. The case of non-compact manifolds was considered by Contreras, who defined an analogue of the minimal max-plus Martin boundary in terms of Busemann functions, and obtained in [Con01, Theorem 0.5] a representation formula for weak-KAM solutions analogous to (2). Busemann functions also appear in [Fat03]. Other results of weak-KAM theory concerning non-compact manifolds have been obtained by Fathi and Maderna [FM02]. See also Fathi and Siconolfi [FS04]. Let us point out that some results of weak-KAM theory with a discrete flavor were established by MacKay, Slijepčević, and Stark [MSS00]. Extremality properties of the elements of the max-plus Martin boundary (Theorems 6.2 and 8.3 below) do not seem to have been considered in weak-KAM theory. Despite the general analogy, the proofs of our representation theorem for harmonic functions (Theorem 8.1) and of the corresponding theorems in [Con01] and [Fat08] require different techniques. In order to relate both settings, it would be natural to set A = B_{s}, where (B_{t})_{t≥0} is the Lax-Oleinik semigroup, and s > 0 is arbitrary. However, only special kernels A can be written in this way, in particular A must have an “infinite divisibility” property. Also, not every harmonic function of B_{s} is a weak-KAM solution associated to the semigroup (B_{t})_{t≥0}. Thus, the discrete time case is in some sense more general than the continuous-time case, but eigenvectors are more constrained in continuous time, so both settings require distinct treatments. Nevertheless, in some special cases, a representation of weak-KAM solutions follows from our results. This happens for example in Section 12, where our assumptions imply that the minimal Martin space of B_{s} is independent of s. We note that the Lagrangian there is not necessarily differentiable, a property which is required in [Fat08] and [Con01]. The lack of uniqueness of the representing measure is examined in a further work [Wal09], where it is shown that the set of (max-plus) measures representing a given (max-plus) harmonic function has a least element. After the submission of the present paper, a boundary theory which has some similarities with the present one was developed by Ishii and Mitake [IM07]. The results there are in the setting of viscosity solutions and are independent of the present ones. We note that the main results of the present paper have been announced in the final section of a companion paper, [AGW05], in which max-plus spectral theory was developed under some tightness conditions. Here, we use tightness only in Section 11. We finally note that the results of the present paper have been used in the further works [Wal07, Wal08].

Acknowledgements. We thank Albert Fathi for helpful comments, and in particular for having pointed out to us the work of Contreras [Con01]. We also thank Arnaud de la Fortelle for references on the probabilistic Martin boundary theory.

2 The max-plus Martin kernel and max-plus Martin space

To show the analogy between the boundary theory of deterministic optimal control problems and classical potential theory, it will be convenient to use max-plus notation. The max-plus semiring, ℝ_{max}, is the set ℝ∪{−∞} equipped with the addition (a, b) ↦ a ⊕ b := max(a, b) and the multiplication (a, b) ↦ a ⊙ b := a + b. We denote by 𝟘 := −∞ and 𝟙 := 0 the zero and unit elements, respectively. We shall often write ab instead of a ⊙ b. Since the supremum of an infinite set may be infinite, we shall occasionally need to consider the completed max-plus semiring \overline{ℝ}_{max}, obtained by adjoining to ℝ_{max} an element +∞, with the convention that 𝟘 = −∞ remains absorbing for the semiring multiplication. The sums and products of matrices and vectors are defined in the natural way. These operators will be denoted by ⊕ and concatenation, respectively. For instance, if A ∈ \overline{ℝ}_{max}^{S×S}, (i, j) ↦ A_{ij}, denotes a matrix (or kernel), and if u ∈ \overline{ℝ}_{max}^{S}, i ↦ u_{i} denotes a vector, we denote by Au ∈ \overline{ℝ}_{max}^{S}, i ↦ (Au)_{i}, the vector defined by

(Au)_{i} := ⨁_{j∈S} A_{ij}u_{j} ,

where the symbol ⊕ denotes the usual supremum. We now introduce the max-plus analogue of the potential kernel (Green kernel).

Given any matrix A ∈ \overline{ℝ}_{max}^{S×S}, we define

A^{∗} = I ⊕ A ⊕ A^{2} ⊕ ⋯ ∈ \overline{ℝ}_{max}^{S×S} ,
A^{+} = A ⊕ A^{2} ⊕ A^{3} ⊕ ⋯ ∈ \overline{ℝ}_{max}^{S×S}

where I = A^{0} denotes the max-plus identity matrix, and A^{k} denotes the kth power of the matrix A. The following formulae are obvious:

A^{∗} = I ⊕ A^{+},  A^{+} = AA^{∗} = A^{∗}A,  and  A^{∗} = A^{∗}A^{∗} .

It may be useful to keep in mind the graph representation of matrices: to any matrix A ∈ \overline{ℝ}_{max}^{S×S} is associated a directed graph with set of nodes S and an arc from i to j if the weight A_{ij} is different from 𝟘. The weight of a path is by definition the max-plus product (that is, the sum) of the weights of its arcs. Then, A_{ij}^{+} and A_{ij}^{∗} represent the supremum of the weights of all paths from i to j that are, respectively, of positive an nonnegative length. Motivated by the analogy with potential theory, we will say that a vector u ∈ ℝ_{max}^{S} is (max-plus) harmonic if Au = u and super-harmonic if Au ≤ u. Note that we require the entries of a harmonic or super-harmonic vector to be distinct from +∞. We shall say that a vector π ∈ ℝ_{max}^{S} is left (max-plus) harmonic if πA = π, π being thought of as a row vector. Likewise, we shall say that π is left (max-plus) super-harmonic if πA ≤ π. Super-harmonic vectors have the following elementary characterisation.

Proposition 2.1. A vector u ∈ ℝ_{max}^{S} is super-harmonic if and only if u = A^{∗}u.

Proof. If u ∈ ℝ_{max}^{S} is super-harmonic, then A^{k}u ≤ u for all k ≥ 1, from which it follows that u = A^{∗}u. The converse also holds, since AA^{∗}u = A^{+}u ≤ A^{∗}u.

From now on, we make the following assumption.

Assumption 2.2. There exists a left super-harmonic vector with full support, in other words a row vector π ∈ ℝ^{S} such that π ≥ πA.

By applying Proposition 2.1 to the transpose of A, we conclude that π = πA^{∗}. Since π has no components equal to 𝟘, we see that one consequence of the above assumption is that A_{ij}^{∗} ∈ ℝ_{max} for all i, j ∈ S. A fortiori, A_{ij} ∈ ℝ_{max} for all i, j ∈ S. The choice of π we make will determine which set of harmonic vectors is the focus of attention. It will be the set of harmonic vectors u that are π-integrable, meaning that πu < ∞. Of course, the boundary that we define will also depend on π, in general. For brevity, we shall omit the explicit dependence on π of the quantities that we introduce and shall omit the assumption on π in the statements of the theorems. We denote by ℋ and 𝒮, respectively, the set of π-integrable harmonic and π-integrable super-harmonic vectors. It is often convenient to choose π := A_{b·}^{∗} for some b ∈ S. (We use the notation M_{i·} and M_{·i} to denote, respectively, the ith row and ith column of any matrix M.) We shall say that b is a basepoint when the vector π defined in this way has finite entries (in particular, a basepoint has access to every node in S). With this choice of π, every super-harmonic vector u ∈ ℝ_{max}^{S} is automatically π-integrable since, by Proposition 2.1, πu = (A^{∗}u)_{b} = u_{b} < +∞. So, in this case, ℋ coincides with the set of all harmonic vectors. This conclusion remains true when π := σA^{∗}, where σ is any row vector with finite support, that is, with σ_{i} = 𝟘 except for finitely many i. We define the Martin kernel K with respect to π:

K_{ij} := A_{ij}^{∗}(π_{j})^{−1} for all i, j ∈ S .  (3)

Since π_{i}A_{ij}^{∗} ≤ (πA^{∗})_{j} = π_{j}, we have

K_{ij} ≤ (π_{i})^{−1} for all i, j ∈ S .  (4)

This shows that the columns K_{·j} are bounded above independently of j. By Tychonoff’s theorem, the set of columns 𝒦 := {K_{·j} | j ∈ S} is relatively compact in the product topology of ℝ_{max}^{S}. The Martin space ℳ is defined to be the closure of 𝒦 . We call ℬ := ℳ \ 𝒦 the Martin boundary. From (3) and (4), we get that Aw ≤ w and πw ≤ 𝟙 for all w ∈ 𝒦 . Since the set of vectors with these two properties can be written

{w ∈ ℝ_{max}^{S} | A_{ij}w_{j} ≤ w_{i} and π_{k}w_{k} ≤ 𝟙 for all i, j, k ∈ S}

and this set is obviously closed in the product topology of ℝ_{max}^{S}, we have that

ℳ ⊂ 𝒮 and πw ≤ 𝟙 for all w ∈ ℳ .  (5)

3 Harmonic vectors arising from recurrent nodes

Of particular interest are those column vectors of K that are harmonic. To investigate these we will need some basic notions and facts from max-plus spectral theory. Define the maximal circuit mean of A to be

ρ(A) := ⨁_{k≥1}(tr A^{k})^{1/k} ,

where tr A = ⨁_{i∈S} A_{ii}. Thus, ρ(A) is the maximum weight-to-length ratio for all the circuits of the graph of A. The existence of a super-harmonic row vector with full support, Assumption 2.2, implies that ρ(A) ≤ 𝟙 (see for instance Prop. 3.5 of [Dud92] or Lemma 2.2 of [AGW05]). Define the normalised matrix Ã = ρ(A)^{−1}A. The max-plus analogue of the notion of recurrence is defined in [AGW05]:

Definition 3.1 (Recurrence). We shall say that a node i is recurrent if Ã_{ii}^{+} = 𝟙. We denote by N^{r}(A) the set of recurrent nodes. We call recurrent classes of A the equivalence classes of N^{r}(A) with the relation R defined by iRj if Ã_{ij}^{+}Ã_{ji}^{+} = 𝟙.

This should be compared with the definition of recurrence for Markov chains, where a node is recurrent if one returns to it with probability one. Here, a node is recurrent if we can return to it with reward 𝟙 in Ã. Since AA^{∗} = A^{+} ≤ A^{∗}, every column of A^{∗} is super-harmonic. Only those columns of A^{∗} corresponding to recurrent nodes yield harmonic vectors:

Proposition 3.2 (See [AGW05, Prop. 5.1]). The column vector A_{·i}^{∗} is harmonic if and only if ρ(A) = 𝟙 and i is recurrent.

The same is true for the columns of K since they are proportional in the maxplus sense to those if A^{∗}. The following two results show that it makes sense to identify elements in the same recurrence class.

Proposition 3.3. Let i, j ∈ S be distinct. Then K_{·i} = K_{·j} if and only if ρ(A) = 𝟙 and i and j are in the same recurrence class.

Proof. Let i, j ∈ S be such that K_{·i} = K_{·j}. Then, in particular, K_{ii} = K_{ij}, and so A_{ij}^{∗} = π_{j}(π_{i})^{−1}. Symmetrically, we obtain A_{ji}^{∗} = π_{i}(π_{j})^{−1}. Therefore, A_{ij}^{∗}A_{ji}^{∗} = 𝟙. If i ≠ j, then this implies that A_{ii}^{+} ≥ A_{ij}^{+}A_{ji}^{+} = A_{ij}^{∗}A_{ji}^{∗} = 𝟙, in which case ρ(A) = 𝟙, i is recurrent, and i and j are in the same recurrence class. This shows the “only if” part of the proposition. Now let ρ(A) = 𝟙 and i and j be in the same recurrence class. Then, according to [AGW05, Prop. 5.2], A_{·i}^{∗} = A_{·j}^{∗}A_{ji}^{∗}, and so K_{·i} = K_{·j}(π_{i})^{−1}π_{j}A_{ji}^{∗}. But since π = πA^{∗}, we have that π_{i} ≥ π_{j}A_{ji}^{∗}, and therefore K_{·i} ≤ K_{·j}. The reverse inequality follows from a symmetrical argument.

Proposition 3.4. Assume that ρ(A) = 𝟙. Then, for all u ∈ 𝒮 and i, j in the same recurrence class, we have π_{i}u_{i} = π_{j}u_{j}.

Proof. Since π ∈ ℝ^{S}, we can consider the vector π^{−1} := (π_{i}^{−1})_{i∈S}. That π is super-harmonic can be expressed as π_{j} ≥ π_{i}A_{ij}, for all i, j ∈ S. This is equivalent to (π_{i})^{−1} ≥ A_{ij}(π_{j})^{−1}; in other words, that π^{−1}, seen as a column vector, is super-harmonic. Proposition 5.5 of [AGW05] states that the restriction of any two ρ(A)-super-eigenvectors of A to any recurrence class of A are proportional. Therefore, either u = 𝟘 or the restrictions of u and π^{−1} to any recurrence class are proportional. In either case, the map i ∈ S ↦ π_{i}u_{i} is constant on each recurrence class.

Remark 3.5. It follows from these two propositions that, for any u ∈ 𝒮, the map S → ℝ_{max}, i ↦ π_{i}u_{i} induces a map 𝒦 → ℝ_{max}, K_{·i} ↦ π_{i}u_{i}. Thus, a super-harmonic vector may be regarded as a function defined on 𝒦 . Let u ∈ ℝ_{max}^{S} be a π-integrable vector. We define the map μ_{u} : ℳ → ℝ_{max} by

μ_{u}(w) := lim sup_{K_{·j}→w} π_{j}u_{j} := inf_{W ∋w} sup_{K_{·j}∈W} π_{j}u_{j} for w ∈ ℳ ,

where the infimum is taken over all neighbourhoods W of w in ℳ. The reason why the limsup above cannot take the value +∞ is that π_{j}u_{j} ≤ πu < +∞ for all j ∈ S. The following result shows that μ_{u} : ℳ → ℝ_{max} is an upper semicontinuous extension of the map from 𝒦 to ℝ_{max} introduced in Remark 3.5.

Lemma 3.6. Let u be a π-integrable super-harmonic vector. Then, μ_{u}(K_{·i}) = π_{i}u_{i} for each i ∈ S and μ_{u}(w)w ≤ u for each w ∈ ℳ. Moreover,

u = ⨁_{w∈𝒦} μ_{u}(w)w = ⨁_{w∈ℳ} μ_{u}(w)w .

Proof. By Proposition 2.1, A^{∗}u = u. Hence, for all i ∈ S,

u_{i} = ⨁_{j∈S} A_{ij}^{∗}u_{j} = ⨁_{j∈S} K_{ij}π_{j}u_{j} .  (6)

We conclude that u_{i} ≥ K_{ij}π_{j}u_{j} for all i, j ∈ S. By taking the limsup with respect to j of this inequality, we obtain that

u_{i} ≥ lim sup_{K_{·j}→w} K_{ij}π_{j}u_{j} ≥ lim inf_{K_{·j}→w} K_{ij} lim sup_{K_{·j}→w} π_{j}u_{j} = w_{i}μ_{u}(w) ,  (7)

for all w ∈ ℳ and i ∈ S. This shows the second part of the first assertion of the lemma. To prove the first part, we apply this inequality with w = K_{·i}. We get that u_{i} ≥ K_{ii}μ_{u}(K_{·i}). Since K_{ii} = (π_{i})^{−1}, we see that π_{i}u_{i} ≥ μ_{u}(K_{·i}). The reverse inequality follows from the definition of μ_{u}. The final statement of the lemma follows from Equation (6) and the first statement.

4 The minimal Martin space

In probabilistic potential theory, one does not need the entire boundary to be able to represent harmonic vectors, a certain subset suffices. We shall see that the situation in the max-plus setting is similar. To define the (max-plus) minimal Martin space, we need to introduce another kernel:

K_{ij}^{♭} := A_{ij}^{+}(π_{j})^{−1} for all i, j ∈ S .

Note that K_{·j}^{♭} = AK_{·j} is a function of K_{·j}. For all w ∈ ℳ, we also define w^{♭} ∈ ℝ_{max}^{S}:

w_{i}^{♭} = lim inf_{K_{·j}→w} K_{ij}^{♭} for all i ∈ S .

The following lemma shows that no ambiguity arises from this notation since (K_{·j})^{♭} = K_{·j}^{♭}.

Lemma 4.1. We have w^{♭} = w for w ∈ ℬ, and w^{♭} = K_{·j}^{♭} = Aw for w = K_{·j} ∈ 𝒦 . For all w ∈ ℳ, we have w^{♭} ∈ 𝒮 and πw^{♭} ≤ 𝟙.

Proof. Let w ∈ ℬ. Then, for each i ∈ S, there exists a neighbourhood W of w such that K_{·i} ∉ W. So

w_{i}^{♭} = lim inf_{K_{·j}→w} K_{ij}^{♭} = lim inf_{K_{·j}→w} K_{ij} = w_{i} ,

proving that w^{♭} = w. Now let w = K_{·j} for some j ∈ S. Taking the sequence with constant value K_{·j}, we see that w^{♭} ≤ K_{·j}^{♭}. To establish the opposite inequality, we observe that

w^{♭} = lim inf_{K_{·k}→w} AK_{·k} ≥ lim inf_{K_{·k}→w} A_{·i}K_{ik} = A_{·i}w_{i} for all i ∈ S ,

or, in other words, w^{♭} ≥ Aw. Therefore we have shown that w^{♭} = K_{·j}^{♭}. The last assertion of the lemma follows from (5) and the fact that π is superharmonic.

Next, we define two kernels H and H^{♭} over ℳ.

H(z, w) :=μ_{w}(z) = lim sup_{K_{·i}→z} π_{i}w_{i} = lim sup_{K_{·i}→z} lim_{K_{·j}→w} π_{i}K_{ij}
H^{♭}(z, w) :=μ_{w^{♭}}(z) = lim sup_{K_{·i}→z} π_{i}w_{i}^{♭} = lim sup_{K_{·i}→z} lim inf_{K_{·j}→w} π_{i}K_{ij}^{♭} .

Using the fact that K^{♭} ≤ K and Inequality (4), we get that

H^{♭}(z, w) ≤ H(z, w) ≤ 𝟙 for all w, z ∈ ℳ .

If w ∈ ℳ, then both w and w^{♭} are elements of 𝒮 by (5) and Lemma 4.1. Using the first assertion in Lemma 3.6, we get that

H(K_{·i}, w) = π_{i}w_{i}  (8)
H^{♭}(K_{·i}, w) = π_{i}w_{i}^{♭} .  (9)

In particular

H(K_{·i}, K_{·j}) = π_{i}K_{ij} = π_{i}A_{ij}^{∗}(π_{j})^{−1}  (10)
H^{♭}(K_{·i}, K_{·j}) = π_{i}K_{ij}^{♭} = π_{i}A_{ij}^{+}(π_{j})^{−1} .  (11)

Therefore, up to a diagonal similarity, H and H^{♭} are extensions to ℳ × ℳ of the kernels A^{∗} and A^{+} respectively.

Lemma 4.2. For all w, z ∈ ℳ, we have

H(z, w) = \begin{cases}H^{♭}(z, w) & when w ≠ z or w = z ∈ ℬ , \\ 𝟙 & otherwise . \end{cases}

Proof. If w ∈ ℬ, then w^{♭} = w by Lemma 4.1, and the equality of H(z, w) and H^{♭}(z, w) for all z ∈ ℳ follows immediately. Let w = K_{·j} for some j ∈ S and let z ∈ ℳ be different from w. Then, there exists a neighbourhood W of z that does not contain w. Applying Lemma 4.1 again, we get that w_{i}^{♭} = K_{ij}^{♭} = K_{ij} = w_{i} for all i ∈ W. We deduce that H(z, w) = H^{♭}(z, w) in this case also. In the final case, we have w = z ∈ 𝒦 . The result follows from Equation (10).

We define the minimal Martin space to be

ℳ^{m} := {w ∈ ℳ | H^{♭}(w, w) = 𝟙} .

From Lemma 4.2, we see that

{w ∈ ℳ | H(w, w) = 𝟙} = ℳ^{m} ∪ 𝒦 .  (12)

Lemma 4.3. Every w ∈ ℳ^{m} ∪ 𝒦 satisfies πw = 𝟙.

Proof. We have

πw = sup_{i∈S} π_{i}w_{i} ≥ lim sup_{K_{·i}→w} π_{i}w_{i} = H(w, w) = 𝟙.

By Equation (5), πw ≤ 𝟙, and the result follows.

Proposition 4.4. Every element of ℳ^{m} is harmonic.

Proof. If 𝒦 ∩ ℳ^{m} contains an element w, then, from Equation (11), we see that ρ(A) = 𝟙 and w is recurrent. It follows from Proposition 3.2 that w is harmonic. It remains to prove that the same is true for each element w of ℬ ∩ ℳ^{m}. Let i ∈ S be such that w_{i} ≠ 𝟘 and assume that β > 𝟙 is given. Since w ∈ ℬ, w and K_{·i} will be different. We make two more observations. Firstly, by Lemma 4.2, lim sup_{K_{·j}→w} π_{j}w_{j} = 𝟙. Secondly, lim_{K_{·j}→w} K_{ij} = w_{i}. From these facts, we conclude that there exists j ∈ S, different from i, such that

𝟙 ≤ βπ_{j}w_{j}  and  w_{i} ≤ βK_{ij} .  (13)

Now, since i and j are distinct, we have A_{ij}^{∗} = A_{ij}^{+} = (AA^{∗})_{ij}. Therefore, we can find k ∈ S such that

A_{ij}^{∗} ≤ βA_{ik}A_{kj}^{∗} .  (14)

The final ingredient is that A_{kj}^{∗}w_{j} ≤ w_{k} because w is super-harmonic. From this and the inequalities in (13) and (14), we deduce that w_{i} ≤ β^{3}A_{ik}w_{k} ≤ β^{3}(Aw)_{i}. Both β and i are arbitrary, so w ≤ Aw. The reverse inequality is also true since every element of ℳ is super-harmonic. Therefore w is harmonic.

5 Martin spaces constructed from different basepoints

We shall see that when the left super-harmonic vector π is of the special form π = A_{b·}^{∗} for some basepoint b ∈ S, the corresponding Martin boundary is independent of the basepoint.

Proposition 5.1. The Martin spaces corresponding to different basepoints are homeomorphic. The same is true for Martin boundaries and minimal Martin spaces.

Proof. Let ℳ and ℳ′ denote the Martin spaces corresponding respectively to two different basepoints, b and b′. We set π = A_{b·}^{∗} and π′ = A_{b′·}^{∗}. We denote by K and K′ the Martin kernels corresponding respectively to π and π′. By construction, K_{bj} = 𝟙 holds for all j ∈ S. It follows that w_{b} = 𝟙 for all w ∈ ℳ. Using the inclusion in (5), we conclude that ℳ ⊂ 𝒮_{b} := {w ∈ 𝒮 | w_{b} = 𝟙}, where 𝒮 denotes the set of π-integrable super-harmonic functions. Observe that A_{bi}^{∗} and A_{b′j}^{∗} are finite for all i, j ∈ S, since both b and b′ are basepoints. Due to the inequalities π′ ≥ A_{b′b}^{∗}π and π ≥ A_{bb′}^{∗}π′, π-integrability is equivalent to π′-integrability. We deduce that ℳ′ ⊂ 𝒮_{b′} := {w′ ∈ 𝒮 | w′_{b′} = 𝟙}. Consider now the maps ϕ and ψ defined by

ϕ(w) = w(w_{b′})^{−1}, ∀w ∈ 𝒮_{b} ψ(w′) = w′(w′_{b})^{−1}, ∀w′ ∈ 𝒮_{b′} .

Observe that if w ∈ 𝒮_{b}, then w_{b′} ≥ A_{b′b}^{∗}w_{b} = A_{b′b}^{∗} ≠ 𝟘. Hence, w ↦ w_{b′} does not take the value 𝟘 on 𝒮_{b}. By symmetry, w′ ↦ w′_{b} does not take the value zero on 𝒮_{b′}. It follows that ϕ and ψ are mutually inverse homeomorphisms which exchange 𝒮_{b} and 𝒮_{b′}. Since ϕ sends K_{·j} to K′_{·j}, ϕ sends the the Martin space ℳ, which is the closure of 𝒦 := {K_{·j} | j ∈ S}, to the Martin space ℳ′, which is the closure of 𝒦 ′ := {K′_{·j} | j ∈ S}. Hence, ϕ sends the Martin boundary ℳ \ 𝒦 to the Martin boundary ℳ′ \ 𝒦 ′. It remains to show that the minimal Martin space corresponding to π, ℳ^{m}, is sent by ϕ to the minimal Martin space corresponding to π′, ℳ′^{m}. Let

H′^{♭}(z′, w′) = lim sup_{K′_{·i}→z′} lim inf_{K′_{·j}→w′} A_{b′i}^{∗}A_{ij}^{+}(A_{b′j}^{∗})^{−1} .

Since ϕ is an homeomorphism sending K_{·i} to K′_{·i}, a net (K_{·i})_{i∈I} converges to w if and only if the net (K′_{·i})_{i∈I} converges to ϕ(w), and so

H′^{♭}(ϕ(z), ϕ(w)) = lim sup_{K_{·i}→z} lim inf_{K_{·j}→w} A_{b′i}^{∗}A_{ij}^{+}(A_{b′j}^{∗})^{−1} = z_{b′}w_{b′}^{−1}H^{♭}(z, w) .

It follows that H^{♭}(w, w) = 𝟙 if and only if H′^{♭}(ϕ(w), ϕ(w)) = 𝟙. Hence, ϕ(ℳ^{m}) = ℳ′^{m}.

Remark 5.2. Consider the kernel obtained by symmetrising the kernel H^{♭},

(z, w) ↦ H^{♭}(z, w)H^{♭}(w, z) .

The final argument in the proof of Proposition 5.1 shows that this symmetrised kernel is independent of the basepoint, up to the identification of w and ϕ(w). The same is true for the kernel obtained by symmetrising H,

(z, w) ↦ H(z, w)H(w, z) .

6 Martin representation of super-harmonic vectors

In probabilistic potential theory, each super-harmonic vector has a unique representation as integral over a certain set of vectors, the analogue of ℳ^{m} ∪ 𝒦 . The situation is somewhat different in the max-plus setting. Firstly, according to Lemma 3.6, one does not need the whole of ℳ^{m} ∪ 𝒦 to obtain a representation: any set containing 𝒦 will do. Secondly, the representation will not necessarily be unique. The following two theorems, however, show that ℳ^{m} ∪ 𝒦 still plays an important role.

Theorem 6.1 (Martin representation of super-harmonic vectors). For each u ∈ 𝒮, μ_{u} is the maximal ν : ℳ^{m} ∪ 𝒦 → ℝ_{max} satisfying

u = ⨁_{w∈ℳ^{m}∪𝒦} ν(w)w ,  (15)

Any ν : ℳ^{m} ∪ 𝒦 → ℝ_{max} satisfying this equation also satisfies

sup_{w∈ℳ^{m}∪𝒦} ν(w) < +∞  (16)

and any ν satisfying (16) defines by (15) an element u of 𝒮.

Proof. By Lemma 3.6, u can be written as (15) with ν = μ_{u}. Suppose that ν : ℳ^{m} ∪ 𝒦 → ℝ_{max} is an arbitrary function satisfying (15). We have

πu = ⨁_{w∈ℳ^{m}∪𝒦} ν(w)πw .

By Lemma 4.3, πw = 𝟙 for each w ∈ ℳ^{m} ∪ 𝒦 . Since πu < +∞, we deduce that (16) holds. Suppose that ν : ℳ^{m} ∪ 𝒦 → ℝ_{max} is an arbitrary function satisfying (16) and define u by (15). Since the operation of multiplication by A commutes with arbitrary suprema, we have Au ≤ u. Also πu = ⨁_{w∈ℳ^{m}∪𝒦} ν(w) < +∞. So u ∈ 𝒮. Let w ∈ ℳ^{m} ∪ 𝒦 . Then ν(w)w_{i} ≤ u_{i} for all i ∈ S. So we have

ν(w)H(w, w) = ν(w) lim sup_{K_{·i}→w} π_{i}w_{i} ≤ lim sup_{K_{·i}→w} π_{i}u_{i} = μ_{u}(w) .

Since H(w, w) = 𝟙, we obtain ν(w) ≤ μ_{u}(w).

We shall now give another interpretation of the set ℳ^{m} ∪ 𝒦 . Let V be a subsemimodule of ℝ_{max}^{S}, that is a subset of ℝ_{max}^{S} stable under pointwise maximum and the addition of a constant (see [LMS01, CGQ04] for definitions and properties of semimodules). We say that a vector ξ ∈ V \{𝟘} is an extremal generator of V if ξ = u ⊕ v with u, v ∈ V implies that either ξ = u or ξ = v. This concept has, of course, an analogue in the usual algebra, where extremal generators are defined for cones. Max-plus extremal generators are also called join irreducible elements in the lattice literature. Clearly, if ξ is an extremal generator of V then so is αξ for all α ∈ ℝ. We say that a vector u ∈ ℝ_{max}^{S} is normalised if πu = 𝟙. If V is a subset of the set of π-integrable vectors, then the set of its extremal generators is exactly the set of αξ, where α ∈ ℝ and ξ is a normalised extremal generator.

Theorem 6.2. The normalised extremal generators of 𝒮 are precisely the elements of ℳ^{m} ∪ 𝒦 .

The proof of this theorem relies on a series of auxiliary results.

Lemma 6.3. Suppose that ξ ∈ ℳ^{m} ∪ 𝒦 can be written in the form ξ = ⨁_{w∈ℳ} ν(w)w, where ν : ℳ → ℝ_{max} is upper semicontinuous. Then, there exists w ∈ ℳ such that ξ = ν(w)w.

Proof. For all i ∈ S, we have ξ_{i} = ⨁_{w∈ℳ} ν(w)w_{i}. As the conventional sum of two upper semicontinuous functions, the function ℳ → ℝ_{max} : w ↦ ν(w)w_{i} is upper semicontinuous. Since ℳ is compact, the supremum of ν(w)w_{i} is attained at some w^{(i)} ∈ ℳ, in other words ξ_{i} = ν(w^{(i)})w_{i}^{(i)}. Since H(ξ, ξ) = 𝟙, by definition of H, there exists a net (i_{k})_{k∈D} of elements of S such that K_{·i_{k}} converges to ξ and π_{i_{k}}ξ_{i_{k}} converges to 𝟙. The Martin space ℳ is compact and so, by taking a subnet if necessary, we may assume that (w^{(i_{k})})_{k∈D} converges to some w ∈ ℳ. Now, for all j ∈ S,

K_{ji_{k}}π_{i_{k}}ξ_{i_{k}} = A_{ji_{k}}^{∗}ξ_{i_{k}} = A_{ji_{k}}^{∗}ν(w^{(i_{k})})w_{i_{k}}^{(i_{k})} ≤ ν(w^{(i_{k})})w_{j}^{(i_{k})} ,

since w^{(i_{k})} is super-harmonic. Taking the limsup as k → ∞, we get that ξ_{j} ≤ ν(w)w_{j}. The reverse inequality is true by assumption and therefore ξ_{j} = ν(w)w_{j}.

The following consequence of this lemma proves one part of Theorem 6.2.

Corollary 6.4. Every element of ℳ^{m}∪𝒦 is a normalised extremal generator of 𝒮.

Proof. Let ξ ∈ ℳ^{m} ∪ 𝒦 . We know from Lemma 4.3 that ξ is normalised. In particular, ξ ≠ 𝟘. We also know from Equation (5) that ξ ∈ 𝒮. Suppose u, v ∈ 𝒮 are such that ξ = u ⊕ v. By Lemma 3.6, we have u = ⨁_{w∈ℳ} μ_{u}(w)w and v = ⨁_{w∈ℳ} μ_{v}(w)w. Therefore, ξ = ⨁_{w∈ℳ} ν(w)w, with ν = μ_{u} ⊕ μ_{v}. Since μ_{u} and μ_{v} are upper semicontinuous maps from ℳ to ℝ_{max}, so is ν. By the previous lemma, there exists w ∈ ℳ such that ξ = ν(w)w. Now, ν(w) must equal either μ_{u}(w) or μ_{v}(w). Without loss of generality, assume the first case. Then ξ = μ_{u}(w)w ≤ u, and since ξ ≥ u, we deduce that ξ = u. This shows that ξ is an extremal generator of 𝒮.

The following lemma will allow us to complete the proof of Theorem 6.2.

Lemma 6.5. Let ℱ ⊂ ℝ_{max}^{S} have compact closure ℱ̄ in the product topology. Denote by V the set whose elements are of the form

ξ = ⨁_{w∈ℱ} ν(w)w ∈ ℝ_{max}^{S},  with ν : ℱ → ℝ_{max}, sup_{w∈ℱ} ν(w) < ∞ . (17)

Let ξ be an extremal generator of V, and ν be as in (17). Then, there exists w ∈ ℱ̄ such that ξ = ν̂(w)w, where

ν̂(w) := lim sup_{w′→w, w′∈ℱ} ν(w′).

Proof. Since ν ≤ ν̂, we have ξ ≤ ⨁_{w∈ℱ} ν̂(w)w ≤ ⨁_{w∈ℱ̄} ν̂(w)w. Clearly, ν(w)w_{i} ≤ ξ_{i} for all i ∈ S and w ∈ ℱ. Taking the limsup as w → w′ for any w′ ∈ ℱ̄, we get that

ξ_{i} ≥ ν̂(w′)w′_{i}.

Combined with the previous inequality, this gives us the representations

ξ = ⨁_{w∈ℱ} ν̂(w)w = ⨁_{w∈ℱ̄} ν̂(w)w .  (18)

Consider now, for each i ∈ S and α < 𝟙, the set

U_{i,α} := {w ∈ ℱ̄ | ν̂(w)w_{i} < αξ_{i}} ,

which is open in ℱ̄ since the map w ↦ ν̂(w)w_{i} is upper semicontinuous. Let ξ ∈ V \{𝟘} be such that ξ ≠ ν̂(w)w for all w ∈ ℱ̄. We conclude that there exist i ∈ S and α < 𝟙 such that αξ_{i} > ν̂(w)w_{i}, which shows that (U_{i,α})_{i∈S,α<𝟙} is an open covering of ℱ̄. Since ℱ̄ is compact, there exists a finite sub-covering U_{i_{1},α_{1}}, …, U_{i_{n},α_{n}}. Using (18) and the idempotency of the ⊕ law, we get

ξ = ξ^{1} ⊕ ⋯ ⊕ ξ^{n}  with ξ^{j} = ⨁_{w∈U_{i_{j} ,α_{j}} ∩ℱ} ν̂(w)w ,  (19)

for j = 1 …, n. Since the supremum of ν̂ over ℱ̄ is the same as that over ℱ, the vectors ξ^{1}, …, ξ^{n} all belong to V. Since ξ is an extremal generator of 𝒮, we must have ξ = ξ^{j} for some j. Then U_{i_{j},α_{j}} ∩ ℱ is non-empty, and so ξ_{i_{j}} > 𝟘. But, from the definition of U_{i_{j},α_{j}},

ξ_{i_{j}}^{j} = ⨁_{w∈U_{i_{j} ,α_{j}} ∩ℱ} ν̂(w)w_{i_{j}} ≤ α_{i_{j}}ξ_{i_{j}} < ξ_{i_{j}} .

This shows that ξ^{j} is different from ξ, and so Equation (19) gives the required decomposition of ξ, proving it is not an extremal generator of V.

We now conclude the proof of Theorem 6.2:

Corollary 6.6. Every normalised extremal generator of 𝒮 belongs to ℳ^{m} ∪ 𝒦 .

Proof. Take ℱ = ℳ^{m} ∪ 𝒦 and let V be as defined in Lemma 6.5. Then, by definition, ℱ̄ = ℳ, which is compact. By Theorem 6.1, V = 𝒮. Let ξ be a normalised extremal generator of 𝒮. Again by Theorem 6.1, ξ = ⊕_{w∈ℱ} μ_{ξ}(w)w. Since μ_{ξ} is upper semicontinuous on ℳ, Lemma 6.5 yields ξ = μ_{ξ}(w)w for some w ∈ ℳ, with μ_{ξ}(w) ≠ 𝟘 since ξ ≠ 𝟘. Note that μ_{αu} = αμ_{u} for all α ∈ ℝ_{max} and u ∈ 𝒮. Applying this to the previous equation and evaluating at w, we deduce that μ_{ξ}(w) = μ_{ξ}(w)μ_{w}(w). Thus, H(w, w) = μ_{w}(w) = 𝟙. In addition, ξ is normalised and so, by Lemma 4.3,

𝟙 = πξ = μ_{ξ}(w)πw = μ_{ξ}(w).

Hence ξ = w ∈ ℳ^{m} ∪ 𝒦 .

7 Almost-geodesics

In order to prove a Martin representation theorem for harmonic vectors, we will use a notion appearing in [YK92] and [KM97, § 2.4], which we will call almostgeodesic. A variation of this notion appeared in [Rie02]. We will compare the two notions later in the section. Let u be a super-harmonic vector, that is u ∈ ℝ_{max}^{S} and Au ≤ u. Let α ∈ ℝ_{max} be such that α ≥ 𝟙. We say that a sequence (i_{k})_{k≥0} with values in S is an α-almost-geodesic with respect to u if u_{i_{0}} ∈ ℝ and

u_{i_{0}} ≤ αA_{i_{0}i_{1}} ⋯ A_{i_{k−1}i_{k}}u_{i_{k}} for all k ≥ 0 .  (20)

Similarly, (i_{k})_{k≥0} is an α-almost-geodesic with respect to a left super-harmonic vector σ if σ_{i_{0}} ∈ ℝ and

σ_{i_{k}} ≤ ασ_{i_{0}}A_{i_{0}i_{1}} ⋯ A_{i_{k−1}i_{k}} for all k ≥ 0 .

We will drop the reference to α when its value is unimportant. Observe that, if (i_{k})_{k≥0} is an almost-geodesic with respect to some right super-harmonic vector u, then both u_{i_{k}} and A_{i_{k−1}i_{k}} are in ℝ for all k ≥ 0. This is not necessarily true if (i_{k})_{k≥0} is an almost-geodesic with respect to a left super-harmonic vector σ, however, if additionally σ_{i_{k}} ∈ ℝ for all k ≥ 0, then A_{i_{k−1}i_{k}} ∈ ℝ for all k ≥ 0.

Lemma 7.1. Let u, σ ∈ ℝ_{max}^{S} be, respectively, right and left super-harmonic vectors and assume that u is σ-integrable, that is σu < +∞. If (i_{k})_{k≥0} is an almost-geodesic with respect to u, and if σ_{i_{0}} ∈ ℝ, then (i_{k})_{k≥0} is an almostgeodesic with respect to σ.

Proof. Multiplying Equation (20) by σ_{i_{k}}(u_{i_{0}})^{−1}, we obtain

σ_{i_{k}} ≤ ασ_{i_{k}}u_{i_{k}}(u_{i_{0}})^{−1}A_{i_{0}i_{1}} ⋯ A_{i_{k−1}i_{k}} ≤ α(σu)(σ_{i_{0}}u_{i_{0}})^{−1}σ_{i_{0}}A_{i_{0}i_{1}} ⋯ A_{i_{k−1}i_{k}} .

So (i_{k})_{k≥0} is a β-almost-geodesic with respect to σ, with β := α(σu)(σ_{i_{0}}u_{i_{0}})^{−1} ≥ α.

Lemma 7.2. Let (i_{k})_{k≥0} be an almost-geodesic with respect to π and let β > 𝟙. Then, for ℓ large enough, (i_{k})_{k≥ℓ} is a β-almost-geodesic with respect to π.

Proof. Consider the matrix Ā_{ij} := π_{i}A_{ij}(π_{j})^{−1}. The fact that (i_{k})_{k≥0} is an α-almost-geodesic with respect to π is equivalent to

p_{k} := (Ā_{i_{0}i_{1}})^{−1} ⋯ (Ā_{i_{k−1}i_{k}})^{−1} ≤ α for all k ≥ 0 .

Since (Ā_{i_{ℓ−1}i_{ℓ}})^{−1} ≥ 𝟙 for all ℓ ≥ 1, the sequence {p_{k}}_{k≥1} is nondecreasing. The upper bound then implies it converges to a finite limit. The Cauchy criterion states that

lim_{ℓ,k→∞, ℓ<k} Ā_{i_{ℓ}i_{ℓ+1}} ⋯ Ā_{i_{k−1}i_{k}} = 𝟙 .

This implies that, given any β > 𝟙, Ā_{i_{ℓ}i_{ℓ+1}} ⋯ Ā_{i_{k−1}i_{k}} ≥ β^{−1} for k and ℓ large enough, with k > ℓ. Writing this formula in terms of A rather than Ā, we see that, for ℓ large enough, (i_{k})_{k≥ℓ} is a β-almost-geodesic with respect to π.

Proposition 7.3. If (i_{k})_{k≥0} is an almost-geodesic with respect to π, then K_{·i_{k}} converges to some w ∈ ℳ^{m}.

Proof. Let β > 𝟙. By Lemma 7.2, (i_{k})_{k≥ℓ} is a β-almost-geodesic with respect to π, for ℓ large enough. Then, for all k > ℓ,

π_{i_{k}} ≤ βπ_{i_{ℓ}}A_{i_{ℓ}i_{k}}^{+} ≤ βπ_{i_{ℓ}}A_{i_{ℓ}i_{k}}^{∗} .

Since π is left super-harmonic, we have π_{i_{ℓ}}A_{i_{ℓ}i_{k}}^{∗} ≤ π_{i_{k}}. Dividing by βπ_{i_{k}} the former inequalities, we deduce that

β^{−1} ≤ π_{i_{ℓ}}K_{i_{ℓ}i_{k}}^{♭} ≤ π_{i_{ℓ}}K_{i_{ℓ}i_{k}} ≤ 𝟙 .  (21)

Since ℳ is compact, it suffices to check that all convergent subnets of K_{·i_{k}} have the same limit w ∈ ℳ^{m}. Let (i_{k_{d}})_{d∈D} and (i_{ℓ_{e}})_{e∈E} denote subnets of (i_{k})_{k≥0}, such that the nets (K_{·i_{k_{d}}})_{d∈D} and (K_{·i_{ℓe}})_{e∈E} converge to some w ∈ ℳ and w′ ∈ ℳ, respectively. Applying (21) with ℓ = ℓ_{e} and k = k_{d}, and taking the limit with respect to d, we obtain β^{−1} ≤ π_{i_{ℓe}} w_{i_{ℓe}}. Taking now the limit with respect to e, we get that β^{−1} ≤ H(w′, w). Since this holds for all β > 𝟙, we obtain 𝟙 ≤ H(w′, w), thus H(w′, w) = 𝟙. From Lemma 3.6, we deduce that w ≥ μ_{w}(w′)w′ = H(w′, w)w′ = w′. By symmetry, we conclude that w = w′, and so H(w, w) = 𝟙. By Equation (12), w ∈ ℳ^{m} ∪ 𝒦 . Hence, (K_{·i_{k}})_{k≥0} converges towards some w ∈ ℳ^{m} ∪ 𝒦 .

Assume by contradiction that w ∉ ℳ^{m}. Then, w = K_{·j} for some j ∈ S, and H^{♭}(w, w) < 𝟙 by definition of ℳ^{m}. By (11), this implies that π_{j}K_{jj}^{♭} = A_{jj}^{+} < 𝟙. If the sequence (i_{k})_{k≥0} takes the value j infinitely often, then, we can deduce from Equation (21) that A_{jj}^{+} = 𝟙, a contradiction. Hence, for k large enough, i_{k} does not take the value j, which implies, by Lemma 4.1, that w_{i_{k}} = w_{i_{k}}^{♭}. Using Equation (21), we obtain H^{♭}(w, w) ≥ lim sup_{k→∞} π_{i_{k}}w_{i_{k}}^{♭} = lim sup_{k→∞} π_{i_{k}}w_{i_{k}} = 𝟙, which contradicts our assumption on w. We have shown that w ∈ ℳ^{m}.

Remark 7.4. An inspection of the proof of Proposition 7.3 shows that the same conclusion holds under the weaker hypothesis that for all β > 𝟙, we have π_{i_{k}} ≤ βπ_{i_{ℓ}}A_{i_{ℓ}i_{k}}^{+} for all ℓ large enough and k > ℓ.

Lemma 7.5. If (i_{k})_{k≥0} is an almost-geodesic with respect to π, and if w is the limit of K_{·i_{k}}, then

lim_{k→∞} π_{i_{k}}w_{i_{k}} = 𝟙 .

Proof. Let β > 𝟙. By Lemma 7.2, (i_{k})_{k≥ℓ} is a β-almost-geodesic with respect to π for ℓ large enough. Hence, for all k ≥ ℓ, π_{i_{k}} ≤ βπ_{i_{ℓ}}A_{i_{ℓ}i_{k}}^{∗}, and so 𝟙 ≤ βπ_{i_{ℓ}}A_{i_{ℓ}i_{k}}^{∗}π_{i_{k}}^{−1} = βπ_{i_{ℓ}}K_{i_{ℓ}i_{k}}. Since K_{i_{ℓ}i_{k}} converges to w_{i_{ℓ}} when k tends to infinity, we deduce that 𝟙 ≤ β lim inf_{ℓ→∞} π_{i_{ℓ}}w_{i_{ℓ}}, and since this holds for all β > 𝟙, we get 𝟙 ≤ lim inf_{ℓ→∞} π_{i_{ℓ}}w_{i_{ℓ}}. Since π_{j}w_{j} ≤ 𝟙 for all j, the lemma is proved.

Proposition 7.6. Let u be a π-integrable super-harmonic vector. Then, μ_{u} is continuous along almost-geodesics, meaning that if (i_{k})_{k≥0} is an almostgeodesic with respect to π and if K_{·i_{k}} tends to w, then,

μ_{u}(w) = lim_{k→∞} μ_{u}(K_{·i_{k}}) = lim_{k→∞} π_{i_{k}}u_{i_{k}} .

Proof. Recall that π_{i}u_{i} = μ_{u}(K_{·i}) holds for all i, as shown in Lemma 3.6. It also follows from this lemma that u ≥ μ_{u}(w)w, and so π_{i}u_{i} ≥ π_{i}w_{i}μ_{u}(w) for all i ∈ S. Hence,

lim inf_{k→∞} π_{i_{k}}u_{i_{k}} ≥ lim inf_{k→∞} π_{i_{k}}w_{i_{k}}μ_{u}(w)
= μ_{u}(w) ,

by Lemma 7.5. Moreover, lim sup_{k→∞} π_{i_{k}}u_{i_{k}} ≤ μ_{u}(w), by definition of μ_{u}(w).

Combining Lemma 7.1 and Proposition 7.3, we deduce the following.

Corollary 7.7. If (i_{k})_{k≥0} is an almost-geodesic with respect to a π-integrable super-harmonic vector, then K_{·i_{k}} converges to some element of ℳ^{m}.

For brevity, we shall say sometimes that an almost-geodesic (i_{k})_{k≥0} converges to a vector w when K_{·i_{k}} converges to w. We state a partial converse to Proposition 7.3.

Proposition 7.8. Assume that ℳ is first-countable. For all w ∈ ℳ^{m}, there exists an almost-geodesic with respect to π converging to w.

Proof. By definition, H^{♭}(w, w) = 0. Writing this formula explicitly in terms of A_{ij} and making the transformation Ā_{ij} := π_{i}A_{ij}(π_{j})^{−1}, we get

lim sup_{K_{·i}→w} lim inf_{K_{·j}→w} Ā_{ij}^{+} = 𝟙 .

Fix a sequence (α_{k})_{k≥0} in ℝ_{max} such that α_{k} > 𝟙 and α := α_{0}α_{1} ⋯ < +∞. Fix also a decreasing sequence (W_{k})_{k≥0} of open neighbourhoods of w. We construct a sequence (i_{k})_{k≥0} in S inductively as follows. Given i_{k−1}, we choose i_{k} to have the following three properties:

a. K_{·i_{k}} ∈ W_{k},

b. lim inf_{K_{·j}→w} Ā_{i_{k}j}^{+} > α_{k}^{−1},

c. Ā_{i_{k−1}i_{k}}^{+} > α_{k−1}^{−1}.

Notice that it is possible to satisfy (c) because i_{k−1} was chosen to satisfy (b) at the previous step. We require i_{0} to satisfy (a) and (b) but not (c). Since ℳ is first-countable, one can choose the sequence (W_{k})_{k≥0} in such a way that every sequence (w_{k})_{k≥0} in ℳ with w_{k} ∈ W_{k} converges to w. By (c), one can find, for all k ∈ ℕ, a finite sequence (i_{k}^{ℓ})_{0≤ℓ≤N_{k}} such that i_{k}^{0} = i_{k}, i_{k}^{N_{k}} = i_{k+1}, and

Ā_{i_{k}^{0},i_{k}^{1}} ⋯ Ā_{i_{k}^{N_{k}−1},i_{k}^{N_{k}}} > α_{k}^{−1} for all k ∈ ℕ .

Since Ā_{ij} ≤ 𝟙 for all i, j ∈ S, we obtain

Ā_{i_{k}^{0},i_{k}^{1}} ⋯ Ā_{i_{k}^{n−1},i_{k}^{n}} > α_{k}^{−1} for all k ∈ ℕ, 1 ≤ n ≤ N_{k} .

Concatenating the sequences (i_{k}^{ℓ})_{0≤ℓ≤N_{k}}, we obtain a sequence (j_{m})_{m≥0} such that α^{−1} ≤ Ā_{j_{0}j_{1}} ⋯ Ā_{j_{m−1}j_{m}} for all m ∈ ℕ, in other words an α-almost-geodesic with respect to π. From Lemma 7.3, we know that K_{·j_{m}} converges to some point in ℳ. Since (i_{k}) is a subsequence of (j_{m}) and K_{·i_{k}} converges to w, we deduce that K_{·j_{m}} also converges to w.

Remark 7.9. If S is countable, the product topology on ℳ is metrisable. Then, the assumption of Proposition 7.8 is satisfied.

Remark 7.10. Assume that (S, d) is a metric space, let A_{ij} = A_{ij}^{∗} = −d(i, j) for i, j ∈ S, and let π = A_{b·}^{∗} for any b ∈ S. We have K_{·j} = −d(·, j) + d(b, j). Using the triangle inequality for d, we see that, for all k ∈ S, the function K_{·k} is non-expansive, meaning that |K_{ik} − K_{jk}| ≤ d(i, j) for all i, j ∈ S. It follows that every map in ℳ is non-expansive. By Ascoli’s theorem, the topology of pointwise convergence on ℳ coincides with the topology of uniform convergence on compact sets. Hence, if S is a countable union of compact sets, then ℳ is metrisable and the assumption of Proposition 7.8 is satisfied.

Example 7.11. The assumption in Proposition 7.8 cannot be dispensed with. To see this, take S = ω_{1}, the first uncountable ordinal. For all i, j ∈ S, define A_{ij} := 0 if i < j and A_{ij} := −1 otherwise. Then, ρ(A) = 𝟙 and A = A^{+}. Also A_{ij}^{∗} equals 0 when i ≤ j and −1 otherwise. We take π := A_{0·}^{∗}, where 0 denotes the smallest ordinal. With this choice, π_{i} = 𝟙 for all i ∈ S, and K = A^{∗}. Let 𝒟 be the set of maps S → {−1, 0} that are non-decreasing and take the value 0 at 0. For each z ∈ 𝒟, define s(z) := sup{i ∈ S | z_{i} = 0} ∈ S ∪ {ω_{1}}. Our calculations above lead us to conclude that

𝒦 = {z ∈ 𝒟 | s(z) ∈ S and z_{s(z)} = 0} .

We note that 𝒟 is closed in the product topology on {−1, 0}^{S} and contains 𝒦 . Furthermore, every z ∈ 𝒟 \ 𝒦 is the limit of the net (A_{·d}^{∗})_{d∈D} indexed by the directed set D = {d ∈ S | d < s_{z}}. Therefore the Martin space is given by ℳ = 𝒟. Every limit ordinal γ less than or equal to ω_{1} yields one point z^{γ} in the Martin boundary ℬ := ℳ \ 𝒦 : we have z_{i}^{γ} = 0 for i < γ, and z_{i}^{γ} = −1 otherwise. Since A_{ii}^{+} = A_{ii} = −1 for all i ∈ S, there are no recurrent points, and so 𝒦 ∩ ℳ^{m} is empty. For any z ∈ ℬ, we have z_{d} = 0 for all d < s(z). Taking the limsup, we conclude that H(z, z) = 𝟙, thus ℳ^{m} = ℬ. In particular, the identically zero vector z^{ω_{1}} is in ℳ^{m}. Since a countable union of countable sets is countable, for any sequence (i_{k})_{k∈ℕ} of elements of S, the supremum I = sup_{k∈ℕ} i_{k} belongs to S, and so its successor ordinal, that we denote by I+1, also belongs to S. Since lim_{k→∞} K_{I+1,i_{k}} = −1, K_{·i_{k}} cannot converge to z^{ω_{1}}, which shows that the point z^{ω_{1}} in the minimal Martin space is not the limit of an almost-geodesic. We now compare our notion of almost-geodesic with that of Rieffel [Rie02] in the metric space case. We assume that (S, d) is a metric space and take A_{ij} = A_{ij}^{∗} = −d(i, j) and π_{j} = −d(b, j), for an some b ∈ S. The compactification of S discussed in [Rie02], called there the metric compactification, is the closure of 𝒦 in the topology of uniform convergence on compact sets, which, by Remark 7.10, is the same as its closure in the product topology. It thus coincides with the Martin space ℳ. We warn the reader that variants of the metric compactification can be found in the literature, in particular, the references [Gro81, Bal95] use the topology of uniform convergence on bounded sets rather than on compacts. Observe that the basepoint b can be chosen in an arbitrary way: indeed, for all b′ ∈ S, setting π′ = A_{b′·}^{∗}, we get π′ ≥ A_{b′b}^{∗}π and π ≥ A_{bb′}^{∗}π′, which implies that almost-geodesics in our sense are the same for the basepoints b and b′. Therefore, when speaking of almost-geodesics in our sense, in a metric space, we will omit the reference to π. Rieffel defines an almost-geodesic as an S-valued map γ from an unbounded set T of real nonnegative numbers containing 0, such that for all ϵ > 0, for all s ∈ T large enough, and for all t ∈ T such that t ≥ s,

|d(γ(t), γ(s)) + d(γ(s), γ(0)) − t| < ϵ .

By taking t = s, one sees that |d(γ(t), γ(0)) − t| < ϵ. Thus, almost-geodesics in the sense of Rieffel are “almost” parametrised by arc-length, unlike those in our sense.

Proposition 7.12. Any almost-geodesic in the sense of Rieffel has a subsequence that is an almost-geodesic in our sense. Conversely, any almost-geodesic in our sense that is not bounded has a subsequence that is an almost-geodesic in the sense of Rieffel.

Proof. Let γ : T → S denote an almost-geodesic in the sense of Rieffel. Then, for all β > 𝟙, we have

A_{γ(0),γ(t)}^{∗} ≤ βA_{γ(0),γ(s)}^{∗}A_{γ(s)γ(t)}^{∗}  (22)

for all s ∈ T large enough and for all t ∈ T such that t ≥ s. Since the choice of the basepoint b is irrelevant, we may assume that b = γ(0), so that π_{γ(s)} = A_{γ(0),γ(s)}^{∗}. As in the proof of Lemma 7.2 we set Ā_{ij} = π_{i}A_{ij}^{∗}π_{j}^{−1}. We deduce from (22) that

β^{−1} ≤ Ā_{γ(s)γ(t)} ≤ 𝟙 .

Let us choose a sequence β_{1}, β_{2}, … ≥ 𝟙 such that the product β_{1}β_{2} … converges to a finite limit. We can construct a sequence t_{0} < t_{1} < … of elements of T such that, setting i_{k} = γ(t_{i_{k}}),

Ā_{i_{k}i_{k+1}} ≥ β_{k}^{−1} .

Then, the product Ā_{i_{0}i_{1}} Ā_{i_{1}i_{2}} ⋯ converges, which implies that the sequence i_{0}, i_{1}, … is an almost-geodesic in our sense. Conversely, let i_{0}, i_{1}, … be an almost-geodesic in our sense, and assume that t_{k} = d(b, i_{k}) is not bounded. After replacing i_{k} by a subsequence, we may assume that t_{0} < t_{1} < . . .. We set T = {t_{0}, t_{1}, …} and γ(t_{k}) = i_{k}. We choose the basepoint b = i_{0}, so that t_{0} = 0 ∈ T , as required in the definition of Rieffel. Lemma 7.2 implies that

A_{bi_{k}}^{∗} ≤ βA_{bi_{ℓ}}^{∗}A_{i_{ℓ}i_{k}}^{∗}

holds for all ℓ large enough and for all k ≥ ℓ. Since t_{k}^{−1} = A_{bi_{k}}^{∗}, γ is an almost-geodesic in the sense of Rieffel.

Rieffel called the limits of almost-geodesics in his sense Busemann points.

Corollary 7.13. Let S be a proper metric space. Then the minimal Martin space is the disjoint union of 𝒦 and of the set of Busemann points of S.

Proof. Since A_{ii}^{+} = −d(i, i) = 0 for all i, the set 𝒦 is included in the minimal Martin space ℳ^{m}. We next show that ℳ^{m} \𝒦 is the set of Busemann points. Let w ∈ ℳ be a Busemann point. By Proposition 7.12 we can find an almostgeodesic in our sense i_{0}, i_{1}, … such that K_{·i_{k}} converges to w and d(b, i_{k}) is unbounded. We know from Proposition 7.3 that w ∈ ℳ^{m}. It remains to check that w ∉ 𝒦 . To see this, we show that for all z ∈ ℳ,

lim_{k→∞} H(K_{·i_{k}}, z) = H(w, z) .  (23)

Indeed, for all β > 𝟙, letting k tend to infinity in (21) and using (8), we get

β^{−1} ≤ π_{i_{ℓ}}w_{i_{ℓ}} = H(K_{·i_{ℓ}}, w) ≤ 𝟙 ,

for ℓ large enough. Hence, lim_{ℓ→∞} H(K_{·i_{ℓ}}, w) = 𝟙. By Lemma 3.6, z ≥ H(w, z)w. We deduce that H(K_{·i_{ℓ}}, z) ≥ H(w, z)H(K_{·i_{ℓ}}, w), and so lim inf_{ℓ→∞} H(K_{·i_{ℓ}}, z) ≥ H(w, z). By definition of H, lim sup_{ℓ→∞} H(K_{·i_{ℓ}}, z) ≤ lim sup_{K_{·j}→w} H(K_{·j}, z) = H(w, z), which shows (23). Assume now that w ∈ 𝒦 , that is, w = K_{·j} for some j ∈ S, and let us apply (23) to z = K_{·b}. We have H(K_{·i_{k}}, z) = A_{bi_{k}}^{∗}A_{i_{k}b}^{∗} = −2 × d(b, i_{k}) → −∞. Hence, H(w, z) = −∞. But H(w, z) = A_{bj}^{∗}A_{jb}^{∗} = −2 × d(b, j) > −∞, which shows that w ∉ 𝒦 . Conversely, let w ∈ ℳ^{m} \ 𝒦 . By Proposition 7.8, w is the limit of an almostgeodesic in our sense. Observe that this almost-geodesic is unbounded. Otherwise, since S is proper, i_{k} would have a converging subsequence, and by continuity of the map i ↦ K_{·i}, we would have w ∈ 𝒦 , a contradiction. It follows from Proposition 7.12 that w is a Busemann point.

8 Martin representation of harmonic vectors

Theorem 8.1 (Poisson-Martin representation of harmonic vectors). Any element u ∈ ℋ can be written as

u = ⨁_{w∈ℳ^{m}} ν(w)w ,  (24)

with ν : ℳ^{m} → ℝ_{max}, and necessarily,

sup_{w∈ℳ^{m}} ν(w) < +∞ .

Conversely, any ν : ℳ^{m} → ℝ_{max} satisfying the latter inequality defines by (24) an element u of ℋ . Moreover, given u ∈ ℋ , μ_{u} is the maximal ν satisfying (24).

Proof. Let u ∈ ℋ . Then u is also in 𝒮 and so, from Lemma 3.6, we obtain that

u = ⨁_{w∈ℳ} μ_{u}(w)w ≥ ⨁_{w∈ℳ^{m}} μ_{u}(w)w .  (25)

To show the opposite inequality, let us fix some i ∈ S such that u_{i} ≠ 𝟘. Let us also fix some sequence (α_{k})_{k≥0} in ℝ_{max} such that α_{k} > 𝟙 for all k ≥ 0 and such that α := α_{0}α_{1} ⋯ < +∞. Since u = Au, one can construct a sequence (i_{k})_{k≥0} in S starting at i_{0} := i, and such that

u_{i_{k}} ≤ α_{k}A_{i_{k}i_{k+1}}u_{i_{k+1}} for all k ≥ 0 .

Then,

u_{i_{0}} ≤ αA_{i_{0}i_{1}} ⋯ A_{i_{k−1}i_{k}}u_{i_{k}} ≤ αA_{i_{0}i_{k}}^{∗}u_{i_{k}} for all k ≥ 0 ,  (26)

and so (i_{k})_{k≥0} is an α-almost-geodesic with respect to u. Since u is π-integrable, we deduce using Corollary 7.7 that K_{·i_{k}} converges to some w ∈ ℳ^{m}. From (26), we get u_{i} ≤ αK_{ii_{k}}π_{i_{k}}u_{i_{k}}, and letting k go to infinity, we obtain u_{i} ≤ αw_{i}μ_{u}(w). We thus obtain

u_{i} ≤ α ⨁_{w∈ℳ^{m}} μ_{u}(w)w_{i} .

Since α can be chosen arbitrarily close to 𝟙, we deduce the inequality opposite to (25), which shows that (24) holds with ν = μ_{u}. The other parts of the theorem are proved in a manner similar to Theorem 6.1.

Remark 8.2. The maximal representing measure μ_{u} at every point that is the limit of an almost geodesic can be computed by taking the limit of π_{i}u_{i} along any almost-geodesic converging to this point. See Proposition 7.6. In particular, ℋ = {𝟘} if and only if ℳ^{m} is empty. We now prove the analogue of Theorem 6.2 for harmonic vectors.

Theorem 8.3. The normalised extremal generators of ℋ are precisely the elements of ℳ^{m}.

Proof. We know from Theorem 6.2 that each element of ℳ^{m} is a normalised extremal generator of 𝒮. Since ℋ ⊂ 𝒮, and ℳ^{m} ⊂ ℋ (by Proposition 4.4), this implies that each element of ℳ^{m} is a normalised extremal generator of ℋ . Conversely, by the same arguments as in the proof of Corollary 6.6, taking ℱ = ℳ^{m} in Lemma 6.5 and using Theorem 8.1 instead of Lemma 3.6, we get that each normalised extremal generator ξ of ℋ belongs to ℳ^{m} ∪ 𝒦 . Since, by Proposition 3.2, no element of 𝒦 \ ℳ^{m} can be harmonic, we have that ξ ∈ ℳ^{m}.

Remark 8.4. Consider the situation when there are only finitely many recurrence classes and only finitely many non-recurrent nodes. Then 𝒦 is a finite set, so that ℬ is empty, ℳ = 𝒦 , and ℳ^{m} coincides with the set of columns K_{·j} with j recurrent. The representation theorem (Theorem 8.1) shows in this case that each harmonic vector is a finite max-plus linear combination of the recurrent columns of A^{∗}, as is the case in finite dimension.

9 Product Martin spaces

In this section, we study the situation where the set S is the Cartesian product of two sets, S_{1} and S_{2}, and A and π can be decomposed as follows:

A = A_{1} ⊗ I_{2} ⊕ I_{1} ⊗ A_{2} , π = π_{1} ⊗ π_{2} .  (27)

Here, ⊗ denotes the max-plus tensor product of matrices or vectors, A_{i} is an S_{i} ×S_{i} matrix, π_{i} is a vector indexed by S_{i}, and I_{i} denotes the S_{i} ×S_{i} max-plus identity matrix. For instance, (A_{1} ⊗ I_{2})_{(i_{1},i_{2}),(j_{1},j_{2})} = (A_{1})_{i_{1}j_{1}}(I_{2})_{i_{2}j_{2}}, which is equal to (A_{1})_{i_{1}j_{1}} if i_{2} = j_{2}, and to 𝟘 otherwise. We shall always assume that π_{i} is left super-harmonic with respect to A_{i}, for i = 1, 2. We denote by ℳ_{i} the corresponding Martin space, by K_{i} the corresponding Martin kernel, etc. We introduce the map

ı : ℝ_{max}^{S_{1}} × ℝ_{max}^{S_{2}} → ℝ_{max}^{S}, ı(w_{1}, w_{2}) = w_{1} ⊗ w_{2} ,

which is obviously continuous for the product topologies. The restriction of ı to the set of (w_{1}, w_{2}) such that π_{1}w_{1} = π_{2}w_{2} = 𝟙 is injective. Indeed, if w_{1} ⊗ w_{2} = w′_{1} ⊗ w′_{2}, applying the operator I_{1} ⊗ π_{2} on both sides of the equality, we get w_{1} ⊗ π_{2}w_{2} = w′_{1} ⊗ π_{2}w′_{2}, from which we deduce that w_{1} = w′_{1} if π_{2}w_{2} = π_{2}w′_{2} = 𝟙.

Proposition 9.1. Assume that A and π are of the form (27), and that π_{i}w_{i} = 𝟙 for all w_{i} ∈ ℳ_{i} and i = 1, 2. Then, the map ı is a homeomorphism from ℳ_{1} × ℳ_{2} to the Martin space ℳ of A, and sends 𝒦_{1} × 𝒦_{2} to 𝒦 . Moreover, the same map sends

ℳ_{1}^{m} × (𝒦_{2} ∪ ℳ_{2}^{m}) ∪ (𝒦_{1} ∪ ℳ_{1}^{m}) × ℳ_{2}^{m}

to the minimal Martin space ℳ^{m} of A.

The proof of Proposition 9.1 relies on several lemmas.

Lemma 9.2. If A is given by (27), then, A^{∗} = A_{1}^{∗} ⊗ A_{2}^{∗} and

A^{+} = A_{1}^{+} ⊗ A_{2}^{∗} ⊕ A_{1}^{∗} ⊗ A_{2}^{+} .

Proof. Summing the equalities A^{k} = ⨁_{1≤ℓ≤k} A_{1}^{ℓ} ⊗ A_{2}^{k−ℓ}, we obtain A^{∗} = A_{1}^{∗} ⊗ A_{2}^{∗}. Hence, A^{+} = AA^{∗} = (A_{1}⊗I_{2}⊕I_{1}⊗A_{2})(A_{1}^{∗}⊗A_{2}^{∗}) = A_{1}^{+}⊗A_{2}^{∗}⊕A_{1}^{∗}⊗A_{2}^{+}.

We define the kernel H∘ı from (ℳ_{1}×ℳ_{2})^{2} to ℝ_{max}, by H∘ı((z_{1}, z_{2}), (w_{1}, w_{2})) = H(ı(z_{1}, z_{2}), ı(w_{1}, w_{2})). The kernel H^{♭} ∘ ı is defined from H^{♭} in the same way.

Lemma 9.3. If A^{∗} = A_{1}^{∗} ⊗ A_{2}^{∗} and π = π_{1} ⊗ π_{2}, then 𝒦 = ı(𝒦_{1} × 𝒦_{2}) and ı(ℳ_{1} × ℳ_{2}) = ℳ. Moreover, if π_{i}w_{i} = 𝟙 for all w_{i} ∈ ℳ_{i} and i = 1, 2, then ı is an homeomorphism from ℳ_{1} × ℳ_{2} to ℳ, and H ∘ ı = H_{1} ⊗ H_{2}.

Proof. Observe that K = K_{1} ⊗ K_{2}. Hence, 𝒦 = ı(𝒦_{1} × 𝒦_{2}). Let \overline{X} denote the closure of any set X. Since \overline{𝒦_{i}} = ℳ_{i}, we get \overline{𝒦_{1} × 𝒦_{2}} = ℳ_{1} × ℳ_{2}, and so \overline{𝒦_{1} × 𝒦_{2}} is compact. Since ı is continuous, we deduce that ı(\overline{𝒦_{1} × 𝒦_{2}} ) = \overline{ı(𝒦_{1} × 𝒦_{2})} . Hence, ı(ℳ_{1}×ℳ_{2}) = \overline{𝒦} = ℳ. Assume now that π_{i}w_{i} = 𝟙 for all w_{i} ∈ ℳ_{i} and i = 1, 2, so that the restriction of ı to ℳ_{1} × ℳ_{2} is injective. Since ℳ_{1} × ℳ_{2} is compact, we deduce that ı is an homeomorphism from ℳ_{1} × ℳ_{2} to its image, that is, ℳ. Finally, let z = ı(z_{1}, z_{2}) and w = ı(w_{1}, w_{2}), with z_{1}, w_{1} ∈ ℳ_{1} and z_{2}, w_{2} ∈ ℳ_{2}. Since ı is an homeomorphism from ℳ_{1} × ℳ_{2} to ℳ, we can write H(z, w) in terms of limsup and limit for the product topology of ℳ_{1} × ℳ_{2}:

H(z, w) = lim sup_{{(K_{1})_{·i_{1}} →z_{1} \atop (K_{2})_{·i_{2}} →z_{2}}} lim_{{(K_{1})_{·j_{1}} →w_{1} \atop (K_{2})_{·j_{2}} →w_{2}}} π_{(i_{1},i_{2})}K_{(i_{1},i_{2}),(j_{1},j_{2})} .  (28)

Since A^{∗} = A_{1}^{∗} ⊗ A_{2}^{∗} and π = π_{1} ⊗ π_{2}, we can write the right hand side term of (28) as the product of two terms that are both bounded from above:

π_{(i_{1},i_{2})}K_{(i_{1},i_{2}),(j_{1},j_{2})} = ((π_{1})_{i_{1}}(K_{1})_{i_{1},j_{1}}) ((π_{2})_{i_{2}}(K_{2})_{i_{2},j_{2}}) .

Hence, the limit and limsup in (28) become a product of limits and limsups, respectively, and so H(z, w) = H_{1}(z_{1}, w_{1})H_{2}(z_{2}, w_{2}).

Lemma 9.4. Assume that A and π are of the form (27) and that π_{i}w_{i} = 𝟙 for all w_{i} ∈ ℳ_{i} and i = 1, 2. Then

H^{♭} ∘ ı = H_{1}^{♭} ⊗ H_{2} ⊕ H_{1} ⊗ H_{2}^{♭} .  (29)

Proof. By Lemma 9.2, A^{+} = A_{1}^{+} ⊗ A_{2}^{∗} ⊕ A_{1}^{∗} ⊗ A_{2}^{+}, and so

K^{♭} = K_{1}^{♭} ⊗ K_{2} ⊕ K_{1} ⊗ K_{2}^{♭} .

Let z = ı(z_{1}, z_{2}) and w = ı(w_{1}, w_{2}), with z_{1}, w_{1} ∈ ℳ_{1}, z_{2}, w_{2} ∈ ℳ_{2}. In a way similar to (28), we can write H^{♭} as

H^{♭}(z, w) = lim sup_{{(K_{1})_{·i_{1}} →z_{1} \atop (K_{2})_{·i_{2}} →z_{2}}} lim inf_{{(K_{1})_{·j_{1}} →w_{1} \atop (K_{2})_{·j_{2}} →w_{2}}} π_{(i_{1},i_{2})}K_{(i_{1},i_{2}),(j_{1},j_{2})}^{♭} .

The right hand side term is a sum of products:

π_{(i_{1},i_{2})}K_{(i_{1},i_{2}),(j_{1},j_{2})}^{♭}
=  (π_{1})_{i_{1}}(K_{1}^{♭})_{i_{1}j_{1}}(π_{2})_{i_{2}}(K_{2})_{i_{2}j_{2}} ⊕ (π_{1})_{i_{1}}(K_{1})_{i_{1}j_{1}}(π_{2})_{i_{2}}(K_{2}^{♭})_{i_{2}j_{2}} .

We now use the following two general observations. Let (α_{d})_{d∈D}, (β_{e})_{e∈E}, (γ_{d})_{d∈D}, (δ_{e})_{e∈E} be nets of elements of ℝ_{max} that are bounded from above. Then,

lim sup_{d,e} α_{d}β_{e} ⊕ γ_{d}δ_{e} = (lim sup_{d} α_{d})(lim sup_{e} β_{e}) ⊕ (lim sup_{d} γ_{d})(lim sup_{e} δ_{e}) .

If additionally the nets (β_{e})_{e∈E} and (γ_{d})_{d∈D} converge, we have

lim inf_{d,e} α_{d}β_{e} ⊕ γ_{d}δ_{e} = (lim inf_{d} α_{d})(lim_{e} β_{e}) ⊕ (lim_{d} γ_{d})(lim inf_{e} δ_{e}) .

Using both identities, we deduce that H^{♭} is given by (29).

Proof of Proposition 9.1. We know from Lemma 9.2 that A^{∗} = A_{1}^{∗}⊗A_{2}^{∗}, and so, by Lemma 9.3, ı is an homeomorphism from ℳ_{1} ×ℳ_{2} to ℳ. Since the kernels H_{1}, H_{1}^{♭}, H_{2} and H_{2}^{♭} all take values less than or equal to 𝟙, we conclude from (29) that, when z = ı(z_{1}, z_{2}), H^{♭}(z, z) = 𝟙 if and only if H_{1}^{♭}(z_{1}, z_{1}) = H_{2}(z_{2}, z_{2}) = 𝟙 or H_{1}(z_{1}, z_{1}) = H_{2}^{♭}(z_{2}, z_{2}) = 𝟙. Using Equation (12) and the definition of the minimal Martin space, we deduce that

ℳ^{m} = ı(ℳ_{1}^{m} × (𝒦_{2} ∪ ℳ_{2}^{m}) ∪ (𝒦_{1} ∪ ℳ_{1}^{m}) × ℳ_{2}^{m}) .

Remark 9.5. The assumption that π_{i}w_{i} = 𝟙 for all w_{i} ∈ ℳ_{i} is automatically satisfied when the left super-harmonic vectors π_{i} originate from basepoints, that is, when π_{i} = (A_{i})_{b_{i},·}^{∗} for some basepoint b_{i}. Indeed, we already observed in the proof of Proposition 5.1 that every vector w_{i} ∈ ℳ_{i} satisfies (π_{i})_{b_{i}}(w_{i})_{b_{i}} = 𝟙. By (5), π_{i}w_{i} ≤ 𝟙. We deduce that π_{i}w_{i} = 𝟙.

Remark 9.6. Rieffel [Rie02, Prop. 4.11] obtained a version of the first part of Lemma 9.3 for metric spaces. His result states that if (S_{1}, d_{1}) and (S_{2}, d_{2}) are locally compact metric spaces, and if their product S is equipped with the sum of the metrics, d((i_{1}, i_{2}), (j_{1}, j_{2})) = d_{1}(i_{1}, j_{1}) + d_{2}(i_{2}, j_{2}), then the metric compactification of S can be identified with the Cartesian product of the metric compactifications of S_{1} and S_{2}. This result can be re-obtained from Lemma 9.3 by taking (A_{1})_{i_{1},j_{i}} = −d_{1}(i_{1}, j_{1}), (A_{2})_{i_{2},j_{2}} = −d_{2}(i_{2}, j_{2}), π_{i_{1}} = −d_{1}(i_{1}, b_{1}), and π_{i_{2}} = −d(i_{2}, b_{2}), for arbitrary basepoints b_{1}, b_{2} ∈ ℤ. We shall illustrate this in Example 10.4.

10 Examples and Counter-Examples

We now illustrate our results and show various features that the Martin space may have.

Example 10.1. Let S = ℕ, A_{i,i+1} = 0 for all i ∈ ℕ, A_{i,0} = −1 for all i ∈ ℕ \ {0} and A_{ij} = −∞ elsewhere. We choose the basepoint 0, so that π = A_{0,·}^{∗}. The graph of A is:

0  0  0 −1 −1 0 −1

States (elements of S) are represented by black dots. The white circle represents the extremal boundary element ξ, that we next determine. In this example, ρ(A) = 𝟙, and A has no recurrent class. We have A_{ij}^{∗} = 𝟙 for i ≤ j and A_{ij}^{∗} = −1 for i > j, so the Martin space of A corresponding to π = A_{0·}^{∗} consists of the columns A_{·j}^{∗}, with j ∈ ℕ, together with the vector ξ whose entries are all equal to 𝟙. We have ℬ = {ξ}. One can easily check that H(ξ, ξ) = 𝟙. Therefore, ℳ^{m} = {ξ}. Alternatively, we may use Proposition 7.3 to show that ξ ∈ ℳ^{m}, since ξ is the limit of the almost-geodesic 0, 1, 2, . . .. Theorem 8.1 says that ξ is the unique (up to a multiplicative constant) non-zero harmonic vector.

Example 10.2. Let us modify Example 10.1 by setting A_{00} = 0, so that the previous graph becomes:

0  0  0 −1 −1 0 −1 0

We still have ρ(A) = 𝟙, the node 0 becomes recurrent, and the minimal Martin space is now ℳ^{m} = {K_{·0}, ξ}, where ξ is defined in Example 10.1. Theorem 8.1 says that every harmonic vector is of the form αK_{·0} ⊕ βξ, that is sup(α + K_{·0}, β + ξ) with the notation of classical algebra, for some α, β ∈ ℝ ∪ {−∞}.

Example 10.3. Let S = ℤ, A_{i,i+1} = A_{i+1,i} = −1 for i ∈ ℤ, and A_{ij} = 𝟘 elsewhere. We choose 0 to be the basepoint, so that π = A_{0,·}^{∗}. The graph of A is:

We are using the same conventions as in the previous examples, together with the following additional conventions: the arrows are bidirectional since the matrix is symmetric, and each arc has weight −1 unless otherwise specified. This example and the next were considered by Rieffel [Rie02].

We have ρ(A) = −1 < 𝟙, which implies there are no recurrent nodes. We have A_{i,j}^{∗} = −|i − j|, and so K_{i,j} = |j| − |i − j|. There are two Martin boundary points, ξ^{+} = lim_{j→∞} K_{·j} and ξ^{−} = lim_{j→−∞} K_{·j}, which are given by ξ_{i}^{+} = i and ξ_{i}^{−} = −i. Thus, the Martin space ℳ is homeomorphic to \overline{ℤ} := ℤ ∪ \{±∞\} equipped with the usual topology. Since both ξ^{+} and ξ^{−} are limits of almostgeodesics, ℳ^{m} = {ξ^{+}, ξ^{−}}. Theorem 8.1 says that every harmonic vector is of the form αξ^{+} ⊕ βξ^{−}, for some α, β ∈ ℝ_{max}.

Example 10.4. Consider S := ℤ×ℤ and the operator A given by A_{(i,j),(i,j±1)} = −1 and A_{(i,j),(i±1,j)} = −1, for each i, j ∈ ℤ, with all other entries equal to −∞. We choose the basepoint (0, 0). We represent the graph of A with the same conventions as in Example 10.3:

For all i, j, k, l ∈ ℤ,

A_{(i,j),(k,l)}^{∗} = −|i − k| − |j − l| .

Note that this is the negative of the distance in the ℓ_{1} norm between (i, j) and (k, l). The matrix A can be decomposed as A = A_{1} ⊗ I ⊕ I ⊗ A_{2}, where A_{1}, A_{2} are two copies of the matrix of Example 10.3, and I denotes the ℤ × ℤ identity matrix (recall that ⊗ denotes the tensor product of matrices, see Section 9 for details). The vector π can be written as π_{1} ⊗ π_{2}, with π_{1} = (A_{1})_{0,·}^{∗} and π_{2} = (A_{2})_{0,·}^{∗}. Hence, Proposition 9.1 shows that the Martin space of A is homeomorphic to the Cartesian product of two copies of the Martin space of Example 10.3, in other words, that there is an homeomorphism from ℳ to \overline{ℤ} × \overline{ℤ}. Proposition 9.1 also shows that the same homeomorphism sends 𝒦 to ℤ × ℤ and the minimal Martin space to (\{±∞\} × \overline{ℤ}) ∪ (\overline{ℤ} × \{±∞\}). Thus, the Martin boundary and the minimal Martin space are the same. This example may be considered to be the max-plus analogue of the random walk on the 2dimensional integer lattice. The Martin boundary for the latter (with respect to eigenvalues strictly greater than the spectral radius) is known [NS66] to be the circle.

Example 10.5. Let S = ℚ and A_{ij} = −|i − j|. Choosing 0 to be the basepoint, we get K_{ij} = −|i − j| + |j| for all j ∈ ℚ. The Martin boundary ℬ consists of the functions i ↦ −|i − j| + |j| with j ∈ ℝ \ ℚ, together with the functions i ↦ i and i ↦ −i. The Martin space ℳ is homeomorphic to \overline{ℝ} := ℝ ∪ \{±∞\} equipped with its usual topology.

Example 10.6. We give an example of a complete locally compact metric space (S, d) such that the canonical injection from S to the Martin space ℳ is not an embedding, and such that the Martin boundary ℬ = ℳ \ 𝒦 is not closed. Consider S = {(i, j) | i ≥ j ≥ 1} and the operator A given by

A_{(i,j),(i+1,j)} = A_{(i+1,j),(i,j)} = −1, for i ≥ j ≥ 1,

A_{(i,j),(i,j+1)} = A_{(i,j+1),(i,j)} = −2, for i − 1 ≥ j ≥ 1,
A_{(1,1),(i,i)} = A_{(i,i),(0,0)} = −1/i, for i ≥ 2,

with all other entries equal to −∞. We choose the basepoint (1, 1). The graph of A is depicted in the following diagram:

−1/2 −1/3 −1/4

We are using the same conventions as before. The arcs with weight −2 are drawn in bold. One can check that

A_{(i,j),(k,ℓ)}^{∗} = max ( − |i − k| − 2|j − ℓ|, −(i − j) − (k − ℓ) − ϕ(j) − ϕ(ℓ))

where ϕ(j) = 1/j if j ≥ 2, and ϕ(j) = 0 if j = 1. In other words, an optimal path from (i, j) to (k, ℓ) is either an optimal path for the metric of the weighted ℓ_{1} norm (i, j) ↦ |i| + 2|j|, or a path consisting of an horizontal move to the diagonal point (j, j), followed by moves from (j, j) to (1, 1), from (1, 1) to (ℓ, ℓ), and by an horizontal move from (ℓ, ℓ) to (k, ℓ). Since A is symmetric and A^{∗} is zero only on the diagonal, d((i, j), (k, ℓ)) := −A_{(i,j),(k,ℓ)}^{∗} is a metric on S. The metric space (S, d) is complete since any Cauchy sequence is either ultimately constant or converges to the point (1, 1). It is also locally compact since any point distinct from (1, 1) is isolated, whereas the point (1, 1) has the basis of neighbourhoods consisting of the compact sets V_{j} = {(i, i) | i ≥ j} ∪ {(1, 1)}, for j ≥ 2. If ((i_{m}, j_{m}))_{m≥1} is any sequence of elements of S such that both i_{m} and j_{m} tend to infinity, then, for any (k, ℓ) ∈ S,

A_{(k,ℓ),(i_{m},j_{m})}^{∗} = A_{(k,ℓ),(1,1)}^{∗}A_{(1,1),(i_{m},j_{m})}^{∗} for m large enough.

(Intuitively, this is related to the fact that, for m large enough, every optimal path from (k, ℓ) to (i_{m}, j_{m}) passes through the point (1, 1)). It follows that K_{·,(i_{m},j_{m})} converges to K_{·,(1,1)} as m → ∞. However, the sequence (i_{m}, j_{m}) does not converge to the point (1, 1) in the metric topology unless i_{m} = j_{m} for m large enough. This shows that the map (i, j) → K_{·,(i,j)} is not an homeomorphism from S to its image. The Martin boundary consists of the points ξ^{1}, ξ^{2}, …, obtained as limits of horizontal half-lines, which are almost-geodesics. We have

ξ_{(i,j)}^{ℓ} := lim_{k→∞} K_{(i,j),(k,ℓ)} = max (i − ℓ − 2|j − ℓ| + ϕ(ℓ), −(i − j) − ϕ(j)) .

The functions ξ^{ℓ} are all distinct because i ↦ ξ_{(i,i)}^{ℓ} has a unique maximum attained at i = ℓ. The functions ξ^{ℓ} do not belong to 𝒦 because ξ_{(3j,j)}^{ℓ} = j + ℓ + ϕ(ℓ) ∼ j as j tends to infinity, whereas for any w ∈ 𝒦 , w_{(3j,j)} = −2j − ϕ(j) ∼ −2j as j tends to infinity,. The sequence ξ^{ℓ} converges to K_{·,(1,1)} as ℓ tends to infinity, which shows that the Martin boundary ℬ = ℳ \ 𝒦 is not closed.

Example 10.7. We next give an example of a Martin space having a boundary point which is not an extremal generator. The same example has been found independently by Webster and Winchester [WW06]. Consider S := ℕ×{0, 1, 2} and the operator A given by

A_{(i,j),(i+1,j)} = A_{(i+1,j),(i,j)} = A_{(i,1),(i,j)} = A_{(i,j),(i,1)} = −1,

for all i ∈ ℕ and j ∈ {0, 2}, with all other entries equal to −∞. We choose (0, 1) as basepoint, so that π := A_{(0,1),·}^{∗} is such that π_{(i,j)} = −(i + 1) if j = 0 or 2, and π_{(i,j)} = −(i + 2) if j = 1 and i ≠ 0. The graph associated to the matrix A is depicted in the following diagram, with the same conventions as in the previous example.

There are three boundary points. They may be obtained by taking the limits

ξ^{0} := lim_{i→∞} K_{·,(i,0)},  ξ^{1} := lim_{i→∞} K_{·,(i,1)},  and ξ^{2} := lim_{i→∞} K_{·,(i,2)}.

Calculating, we find that

ξ_{(i,j)}^{0} = i − j + 1,  ξ_{(i,j)}^{2} = i + j − 1,  and ξ^{1} = ξ^{0} ⊕ ξ^{2}.

We have H(ξ^{0}, ξ^{0}) = H(ξ^{2}, ξ^{2}) = H(ξ^{2}, ξ^{1}) = H(ξ^{0}, ξ^{1}) = 0. For all other pairs (ξ′, ξ) ∈ ℬ × ℬ, we have H(ξ′, ξ) = −2. Therefore, the minimal Martin boundary is ℳ^{m} = {ξ^{0}, ξ^{2}}, and there is a non-extremal boundary point, ξ^{1}, represented above by a gray circle. The sequences ((i, 0))_{i∈ℕ} and ((i, 2))_{i∈ℕ} are almost-geodesics, while it should be clear from the diagram that there are no almost-geodesics converging to ξ^{1}. So this example provides an illustration of Propositions 7.3 and 7.8.

Example 10.8. Finally, we will give an example of a non-compact minimal Martin space. Consider S := ℕ × ℕ × {0, 1} and the operator A given by

A_{(i,j,k),(i,j+1,k)} =A_{(i,j+1,k),(i,j,k)} =−1, for all i, j ∈ ℕ and k ∈ {0, 1},
A_{(i,j,k),(i,j,1−k)} =−1, for all i ∈ ℕ, j ∈ ℕ\{0} and k ∈ {0, 1},
A_{(i,0,k),(i,0,1−k)} =−2, for all i ∈ ℕ and k ∈ {0, 1},
A_{(i,0,k),(i+1,0,k)} =A_{(i+1,0,k),(i,0,k)} =−1, for all i ∈ ℕ and k ∈ {0, 1},

with all other entries equal to −∞. We take π := A_{(0,0,0),·}^{∗}. With the same conventions as in Examples 10.4 and 10.7, the graph of A is

Recall that arcs of weight −1 are drawn with thin lines whereas those of weight −2 are drawn in bold. For all (i, j, k), (i′, j′, k′) ∈ S,

A_{(i,j,k),(i′,j′,k′)}^{∗} = −|k′ −k|−|i′ −i|−|j′ −j|χ_{i=i′} −(j +j′)χ_{i≠i′} −χ_{j=j′=0, k≠k′} ,

where χ_{E} takes the value 1 when condition E holds, and 0 otherwise. Hence,

K_{(i,j,k),(i′,j′,k′)} =k′ − |k′ − k| + i′ − |i′ − i| + j′ − |j′ − j|χ_{i=i′} − (j + j′)χ_{i≠i′}
+ χ_{j′=0,k′=1} − χ_{j=j′=0, k≠k′} .

By computing the limits of K_{·,(i′,j′,k′)} when i′ and/or j′ go to +∞, we readily check that the Martin boundary is composed of the vectors

ξ^{i′,∞,k′} := lim_{j′→∞} K_{·,(i′,j′,k′)},
ξ^{∞,∞,k′} := lim_{i′,j′→∞} K_{·,(i′,j′,k′)}
ξ^{∞,0,k′} := lim_{i′→∞} K_{·,(i′,0,k′)}.

where the limit in i and j′ in the second line can be taken in either order. Note that lim_{i′→∞} K_{·,(i′,j′,k′)} = ξ^{∞,∞,k′} for any j′ ∈ ℕ \ {0} and k′ ∈ {0, 1}. The minimal Martin space is composed of the vectors ξ^{i′,∞,k′} and ξ^{∞,0,k′} with i′ ∈ ℕ and k′ ∈ {0, 1}. The two boundary points ξ^{∞,∞,0} and ξ^{∞,∞,1} are non-extremal and have representations

ξ^{∞,∞,0} = ξ^{∞,0,0} ⊕ −3ξ^{∞,0,1} ,
ξ^{∞,∞,1} = ξ^{∞,0,0} ⊕ −1ξ^{∞,0,1}.

For k′ ∈ {0, 1}, the sequence (ξ^{i′,∞,k′})_{i∈ℕ} converges to ξ^{∞,∞,k′} as i goes to infinity. Since this point is not in ℳ^{m}, we see that ℳ^{m} is not compact.

11 Tightness and existence of harmonic vectors

We now show how the Martin boundary can be used to obtain existence results for eigenvectors. As in [AGW05], we restrict our attention to the case where S is equipped with the discrete topology. We say that a vector u ∈ ℝ_{max}^{S} is A-tight if, for all i ∈ S and β ∈ ℝ, the super-level set {j ∈ S | A_{ij}u_{j} ≥ β} is finite. We say that a family of vectors {u^{ℓ}}_{ℓ∈L} ⊂ ℝ_{max}^{S} is A-tight if sup_{ℓ∈L} u^{ℓ} is A-tight. The notion of tightness is motivated by the following property.

Lemma 11.1. If a net {u^{ℓ}}_{ℓ∈L} ⊂ ℝ_{max}^{S} is A-tight and converges pointwise to u, then Au^{ℓ} converges pointwise to Au.

Proof. This may be checked elementarily, or obtained as a special case of general results for idempotent measures [Aki95, AQV98, Aki99, Puh01] or, even more generally, capacities [OV91]. We may regard u and u^{l} as the densities of the idempotent measures defined by

Q_{u}(J) = sup_{j∈J} u_{j}  and  Q_{u^{l}}(J) = sup_{j∈J} u_{j}^{l} ,

for any J ⊂ S. When S is equipped with the discrete topology, pointwise convergence of (u^{ℓ})_{ℓ∈L} is equivalent to convergence in the hypograph sense of convex analysis. It is shown in [AQV98] that this is then equivalent to convergence of (Q_{u^{l}})_{ℓ∈L} in a sense analogous to the vague convergence of probability theory. It is also shown that, when combined with the tightness of (u_{l})_{ℓ∈L}, this implies convergence in a sense analogous to weak convergence. The result follows as a special case.

Proposition 11.2. Assume that S is infinite and that the vector π^{−1} := (π_{i}^{−1})_{i∈S} is A-tight. Then, some element of ℳ is harmonic and, if 𝟘 ∉ ℳ, then ℳ^{m} is non-empty. Furthermore, each element of ℬ is harmonic.

Proof. Since S is infinite, there exists an injective map n ∈ ℕ ↦ i_{n} ∈ S. Consider the sequence (i_{n})_{n∈ℕ}. Since ℳ is compact, it has a subnet (j_{k})_{k∈D}, j_{k} := i_{n_{k}} such that {K_{·j_{k}}}_{k∈K} converges to some w ∈ ℳ. Let i ∈ S. Since (AA^{∗})_{ij} = A_{ij}^{+} = A_{ij}^{∗} for all j ≠ i, we have

(AK_{·j_{k}})_{i} = K_{ij_{k}}

when j_{k} ≠ i. But, by construction, the net (j_{k})_{k∈D} is eventually in S\{i} and so we may pass to the limit, obtaining lim_{k∈K} AK_{·j_{k}} = w. Since π^{−1} is A-tight, it follows from (4) that the family (K_{·j})_{j∈S} is A-tight. Therefore, by Lemma 11.1, we get w = Aw. If 𝟘 ∉ ℳ, then ℋ contains a non-zero vector, and applying the representation formula (24) to this vector, we see that ℳ^{m} cannot be empty. It remains to show that ℬ ⊂ ℋ . Any w ∈ ℬ is the limit of a net {K_{·j_{k}}}_{k∈D}. Let i ∈ S. Since w ≠ K_{·i}, the net {K_{·j_{k}}}_{k∈D} is eventually in some neighbourhood of w not containing K_{·i}. We deduce as before that w is harmonic.

Corollary 11.3 (Existence of harmonic vectors). Assume that S is infinite, that π = A_{b·}^{∗} ∈ ℝ^{S} for some b ∈ S, and that π^{−1} is A-tight. Then, ℋ contains a non-zero vector.

Proof. We have K_{bj} = 𝟙 for all j ∈ S and hence, by continuity, w_{b} = 𝟙 for all w ∈ ℳ. In particular, ℳ does not contain 𝟘. The result follows from an application of the proposition.

We finally derive a characterisation of the spectrum of A. We say that λ is a (right)-eigenvalue of A if Au = λu for some vector u such that u ≠ 𝟘.

Corollary 11.4. Assume that S is infinite, A is irreducible, and for each i ∈ S, there are only finitely many j ∈ S with A_{ij} > 𝟘. Then the set of right eigenvalues of A is [ρ(A), ∞[.

Proof. Since A is irreducible, no eigenvector of A can have a component equal to 𝟘. It follows from [Dud92, Prop. 3.5] that every eigenvalue of A must be greater than or equal to ρ(A). Conversely, for all λ ≥ ρ(A), we have ρ(λ^{−1}A) ≤ 𝟙. Combined with the irreducibility of A, this implies [AGW05, Proposition 2.3] that all the entries of (λ^{−1}A)^{∗} are finite. In particular, for any b ∈ S, the vector π := (λ^{−1}A)_{b·}^{∗} is in ℝ^{S}. The last of our three assumptions ensures that π^{−1} is (λ^{−1}A)-tight and so, by Corollary 11.3, (λ^{−1}A) has a non-zero harmonic vector. This vector will necessarily be an eigenvector of A with eigenvalue λ.

Example 11.5. The following example shows that when π^{−1} is not A-tight, a Martin boundary point need not be an eigenvector. Consider S := ℕ and the operator A given by

A_{i,i+1} = A_{i+1,i} := −1  and  A_{0i} := 0  for all i ∈ ℕ,

with all other entries of equal to −∞. We take π := A_{0,·}^{∗}. With the same conventions as in Example 10.7, the graph of A is

0  0  0

We have A_{i,j}^{∗} = max(−i, −|i − j|) and π_{i} = 0 for all i, j ∈ ℕ. There is only one boundary point, b := lim_{k→∞} K_{·k}, which is given by b_{i} = −i for all i ∈ ℕ. One readily checks that b is not an harmonic vector and, in fact, A has no non-zero harmonic vectors.

12 Eigenvectors of Lax-Oleinik semigroups and Busemann points of normed spaces

We now use the Martin boundary to solve a class of continuous-time deterministic optimal control problems. Consider the value function v defined by:

v(t, x) := sup_{X(·), X(0)=x} ϕ(X(t)) − ∫_{0}^{t} L(Ẋ(s)) ds .

Here, x is a point in ℝ^{n}, t is a nonnegative real number, the Lagrangian L is a Borel measurable map ℝ^{n} → ℝ ∪ {+∞}, bounded from below, the terminal reward ϕ is an arbitrary map ℝ^{n} → ℝ∪{−∞}, and the supremum is taken over all absolutely continuous functions X : [0, t] → ℝ^{n} such that X(0) = x. This is a special case of the classical Lagrange problem of calculus of variations. The Lax-Oleinik semigroup (T^{t})_{t≥0} is composed of the maps T^{t} sending the value function at time 0, v(0, ·) = ϕ to the value function at time t, v(t, ·). The semigroup property T^{t+s} = T^{t} ∘ T^{s} follows from the dynamic programming principle. The kernel of the operator T^{t} is given by

(x, y) ↦ T_{x,y}^{t} = sup_{X(·), X(0)=x, X(t)=y} − ∫_{0}^{t} L(Ẋ(s)) ds ,

where the supremum is taken over all absolutely continuous functions X : [0, t] → ℝ^{n} such that X(0) = x and X(t) = y. The classical Hopf-Lax formula states that

T_{x,y}^{t} = −t co L(\frac{y − x}{t}), for t > 0 ,

where co L denotes the convex lower semicontinuous hull of L. This is proved, for instance, in [Eva98, §3.3, Th. 4] when L is convex and finite valued, and when the curves X(·) are required to be continuously differentiable. The extension to the present setting is not difficult. Since T^{t} only depends on co L, we shall assume that L is convex, lower semicontinuous, and bounded from below. Moreover, we shall always assume that L(0) is finite.

We say that a function u : ℝ^{n} → ℝ ∪ {−∞}, not identically −∞, is an eigenvector of the semigroup (T^{t})_{t≥0} with eigenvalue λ if

T^{t}u = u + λt, for all t > 0 .

We shall say that u is extremal if it is an extremal generator of the eigenspace of the semigroup (T^{t})_{t≥0} with eigenvalue λ, meaning that u cannot be written as the supremum of two eigenvectors with the same eigenvalue that are both different from it. One easily checks, using the convexity of L, that for all t > 0, the maximal circuit mean of the operator T^{t} is given by

ρ(T^{t}) = −tL(0) .

By Proposition 3.5 of [Dud92] or Lemma 2.2 of [AGW05], any eigenvalue μ of T^{t} must satisfy μ ≥ ρ(T^{t}), and so any eigenvalue λ of the semigroup (T^{t})_{t≥0} satisfies

λ ≥ −L(0) .

We denote by ζ(x) the one sided directional derivative of L at the origin in the direction x:

ζ(x) = lim_{t→0^{+}} t^{−1}(L(tx) − L(0)) = inf_{t>0} t^{−1}(L(tx) − L(0)) ∈ ℝ ∪ {±∞} , (30)

which always exists since L is convex.

Proposition 12.1. Assume that ζ does not take the value −∞. Then, the eigenvectors of the Lax-Oleinik semigroup (T^{t})_{t≥0} with eigenvalue −L(0) are precisely the functions u : ℝ^{n} → ℝ ∪ {−∞}, not identically −∞, such that

−ζ(y − x) + u(y) ≤ u(x) , for all x, y ∈ ℝ^{n} .  (31)

Moreover, when ζ only takes finite values, the extremal eigenvectors with eigenvalue −L(0) are of the form c + w, where c ∈ ℝ and w belongs to the minimal Martin space of the kernel (x, y) ↦ −ζ(y − x) with respect to any basepoint.

Proof. Let us introduce the kernels

A_{s} := T^{s} + sL(0), for all s ≥ 0.

Using the Hopf-Lax formula, we get

(A_{s})_{xy}^{+} = sup_{k∈ℕ\\{0\}} −ksL(\frac{y − x}{ks}) + ksL(0) .

Using (30) and the fact that ζ(0) = 0, we deduce that

(A_{s})_{xy}^{∗} = (A_{s})_{xy}^{+} = −ζ(y − x) .  (32)

The eigenvectors of the semigroup (T^{t})_{t≥0} are precisely the functions that are harmonic with respect to all the kernels A_{s}, with s > 0. Since (A_{s})_{xx} = 0 for all x ∈ ℝ^{n}, the harmonic and super-harmonic functions of A_{s} coincide. It follows from Proposition 2.1 that u is a super-harmonic function of A_{s} if and only if u ≥ A_{s}^{∗}u. Since the latter condition can be written as (31) and is independent of s, the first assertion of the corollary is proved. By (32), when ζ is finite, any point can be taken as the basepoint. The kernels A_{s} and (x, y) ↦ −ζ(y − x) have the same Martin and minimal Martin spaces with respect to any given basepoint, and so the final assertion of the corollary follows from Theorem 6.2.

Remark 12.2. When ∂L(0), the subdifferential of L at the origin, is non-empty, ζ does not take the value −∞. This is the case when the origin is in the relative interior of the domain of L. Then, ζ coincides with the support function of ∂L(0):

ζ(x) = sup_{y∈∂L(0)} y · x, for all x ∈ ℝ^{n} ,

see [Roc70, Th. 23.4]. If in addition the origin is in the interior of the domain of L, then ∂L(0) is non-empty and compact, and so the function ζ is everywhere finite.

Corollary 12.3. When ζ is a norm on ℝ^{n}, the extremal eigenvectors with eigenvalue −L(0) of the Lax-Oleinik semigroup (T^{t})_{t≥0} are precisely the functions x ↦ c − ζ(y − x), where c ∈ ℝ and y ∈ ℝ^{n}, together with the functions c + w, where c ∈ ℝ and w is a Busemann point of the normed space (ℝ^{n}, ζ).

Proof. This follows from Proposition 12.1 and Corollary 7.13.

Remark 12.4. The map ζ is a norm when the origin is in the interior of the domain of L and the subdifferential ∂L(0) is symmetric, meaning that p ∈ ∂L(0) implies −p ∈ ∂L(0). When ζ is a norm, condition (31) means that u is Lipschitz-continuous with respect to ζ or that u is identically −∞. We next study the eigenspace of (T^{t})_{t≥0} for an eigenvalue λ > −L(0) in the special case where L is of the form

L(x) = \frac{∥x∥}{p}^{p} ,

where ∥ · ∥ is an arbitrary norm on ℝ^{n} and p > 1. For all λ > 0, we set

ϑ_{λ} := (qλ)^{\frac{1}{q}} where \frac{1}{p} + \frac{1}{q} = 1 .

Theorem 12.5. Let s > 0 and λ > 0. Any eigenvector of T^{s} with eigenvalue λs is an eigenvector of the Lax-Oleinik semigroup (T^{t})_{t≥0} with eigenvalue λ. Such an eigenvector can be written as

u = sup_{w∈ℳ_{bu}} ν(w) + ϑ_{λ}w ,  (33)

where ℳ_{bu} denotes the set of Busemann points of the normed space (ℝ^{n}, ∥ · ∥) and ν is an arbitrary map ℳ_{bu} → ℝ∪{−∞} bounded from above. The maximal map ν satisfying (33) is given by μ_{u}. Moreover, the extremal eigenvectors with eigenvalue λ are of the form c + ϑ_{λ}w, where c ∈ ℝ and w ∈ ℳ_{bu}.

This theorem follows from Theorem 8.1, Theorem 8.3, and the next lemma.

Lemma 12.6. For all s > 0, the minimal Martin space of the kernel A_{s} := T^{s} − sλ, with respect to any basepoint, coincides with the set of functions ϑ_{λ}w, where w is a Busemann point of the normed space (ℝ^{n}, ∥ · ∥) equipped with the same basepoint.

Proof. For all x, y ∈ ℝ^{n}, we set

ψ(t) := −t^{1−p}L(y − x) − tλ .

It follows from the Hopf-Lax formula that

(A_{s})_{xy}^{+} = sup_{k∈ℕ\{0}} ψ(ks) .  (34)

Since ψ is concave, the supremum of ψ(t) over all t > 0 is attained at the point t̄ such that

ψ′(t̄) = t̄^{−p}(p − 1)L(y − x) − λ = 0 .

It follows that

ψ(t̄) = −ϑ_{λ}∥y − x∥ .

Since ψ is concave, we have ψ(t) ≥ ψ(t̄) + ψ′(t)(t − t̄), and so, for t ≥ t̄,

ψ(t) − ψ(t̄) = ψ(t) − ψ(t̄) − ψ′(t̄)(t − t̄)
≥ (ψ′(t) − ψ′(t̄))(t − t̄) ≥ ψ′′(t̄)(t − t̄)^{2}

since ψ′ is convex. Let k denote the smallest integer such that t̄ ≤ ks, and let t = ks. We deduce that

0 ≥ ψ(t) − ψ(t̄) ≥ −p(p − 1)L(y − x)t̄^{−1−p}(t − t̄)^{2} = −pλt̄^{−1}(t − t̄)^{2} .

Since t̄≤ t ≤ t̄+ s, since t̄= (qλ)^{−1/p}∥y − x∥, and since

ψ(t̄) ≥ (A_{s})_{xy}^{∗} ≥ (A_{s})_{xy}^{+} ≥ ψ(t) ,

we get

(A_{s})_{xy}^{∗} = −ϑ_{λ}∥y − x∥ + ϵ(∥y − x∥) ,  (35)

where ϵ is a function tending to 0 at infinity. Observe that the supremum in (34) is always attained by an integer k which can be bounded by an increasing function of ∥y −x∥. Hence, for all x ∈ ℝ^{n} and every compact set C, we can find an integer N such that (A_{s})_{xy}^{+} = sup_{1≤k≤N} ψ(ks) for all y ∈ C. Since every ψ(ks) is a continuous function of y − x, we deduce that the map y ↦ (A_{s})_{xy}^{+} is continuous. Denote by K the Martin kernel of A_{s} with respect to this basepoint and denote by ℳ, ℳ^{m}, and 𝒦 , the corresponding Martin space, minimal Martin space, and set of columns of the Martin kernel. Also, we denote by H the kernel constructed from K as in Section 4. Define the kernel A′ : (x, y) ↦ −ϑ_{λ}∥y − x∥. We use K′, ℳ′, ℳ′^{m}, 𝒦 ′ and H′ to denote the corresponding objects constructed from A′. We next show that ℳ^{m} = ℳ′^{m} \ 𝒦 ′. An element w of ℳ^{m} is the limit of a net (K_{·y_{d}})_{d∈D}. If the net (y_{d})_{d∈D} had a bounded subnet, it would have a subnet converging to some y ∈ ℝ^{d}. Then, by continuity of the map z ↦ (A_{s})_{·z}^{+}, the element w would be proportional in the max-plus sense either to f := (A_{s})_{·y}^{∗} or to g := (A_{s})_{·y}^{+} (the first case arises if the subnet is ultimately constant). Both cases can be ruled out: we know from Proposition 4.4 that an element of the minimal Martin space is harmonic, but f_{y} = 0 ≠ g_{y} = (A_{s}f)_{y} = −sλ ≠ (A_{s}g)_{y} = −2sλ, and so f and g are not harmonic. This shows that (y_{d})_{d∈D} tends to infinity. By (35), we deduce that K′_{·y_{d}} tends to w. Thus, any net (y_{d})_{d∈D} such that K_{·y_{d}} tends to w is such that y_{d} tends to infinity and K′_{·y_{d}} tends to w. We deduce that w ∈ ℳ′ and H′(w, w) ≥ H(w, w) = 𝟙, and so, by (12), ℳ^{m} ⊂ ℳ′^{m}∪𝒦 ′. We proved that the columns of (A_{s})^{∗} are not harmonic, and so ℳ^{m} ⊂ ℳ \𝒦 . We claim that ℳ^{m} ⊂ ℳ′^{m} \ 𝒦 ′. Indeed, if a net K_{·y_{d}} converges to w ∈ ℳ^{m}, we showed that (y_{d})_{d∈D} tends to infinity, and that K′_{·y_{d}} tends to w. But K′_{·y_{d}} cannot converge to an element K′_{·y} ∈ 𝒦 ′ because the map sending an element of a finite-dimensional normed space to its column of the Martin kernel is an embedding (see [Bal95, Ch. II,§1] for a more general result). So w ∉ 𝒦 ′. Let us take now w′ ∈ ℳ′^{m} \ 𝒦 ′. Then, w′ is the limit of some net (K′_{·y′_{d}})_{d∈D′}, where (y′_{d})_{d∈D′} necessarily tends to infinity, since otherwise, there would be a subnet of (y′_{d})_{d∈D′} converging to some z ∈ ℝ^{n}, and so we would have w′ = K′_{·z} ∈ 𝒦 ′. It follows from (35) that w′ is the limit of K_{·y′_{d}}, and hence w′ ∈ ℳ. These properties also imply that H′(w′, w′) ≤ H(w′, w′). Since w′ ∈ ℳ′^{m}, we have H′(w′, w′) = 𝟙, and so H(w′, w′) = 𝟙, and by (12), w′ ∈ ℳ^{m} ∪ 𝒦 . Observe that the map z ↦ w′_{z} is continuous because it is a pointwise limit of elements of 𝒦 ′, all of which are Lipschitz continuous with constant ϑ_{λ} with respect to the norm ∥ · ∥. For all y ∈ ℝ^{n}, the map x ↦ A_{xy}^{∗} takes the value 0 when x = y and the value (A_{s})_{xy}^{+} ≤ −sλ < 0 when x ≠ y. Thus, the elements of 𝒦 are not continuous, and so, w′ ∉ 𝒦 . It follows that w′ ∈ ℳ^{m} \ 𝒦 = ℳ^{m}. We have shown that ℳ^{m} = ℳ′^{m} \ 𝒦 ′. By Corollary 7.13, ℳ′^{m} \ 𝒦 ′ is the set of Busemann points of the normed space (ℝ^{n}, ϑ_{λ}∥ · ∥). These are precisely the functions of the form ϑ_{λ}w, where w is a Busemann point of (ℝ^{n}, ∥ · ∥).

Remark 12.7. Lemma 12.6 identifies a special situation where the minimal Martin space of T^{s} − sλ is independent of s. This seems related to the fact that the set of functions of the form x ↦ a∥x∥^{p} with a > 0 is stable by infconvolution. One may still obtain a representation of the eigenvectors for more general semigroups (T^{t})_{t≥0}, but this requires adapting some of the present results to the continuous-time setting. We shall present this elsewhere. Example 12.8. Consider the Euclidean norm on ℝ^{n}, ∥x∥ := (x · x)^{1/2}, and L(x) := ∥x∥^{p}/p with p > 1. The set of Busemann points of the normed space (ℝ^{n}, ∥ · ∥), with respect to the basepoint 0, coincides with the set of functions

w : x ↦ x · y ,

where y is an arbitrary vector of norm 1. It follows from Theorem 12.5 that the extremal eigenvectors with eigenvalue λ > 0 of the Lax-Oleinik semigroup are of the form c + ϑ_{λ}w, with c ∈ ℝ, and that any eigenvector with eigenvalue λ is a supremum of maps of this form. In particular, when n = 1, there are two Busemann points, w^{±}(x) = ±ϑ_{λ}x, and any eigenvector u with eigenvalue λ can be written as

x ↦ max(c^{+} + ϑ_{λ}x, c^{−} − ϑ_{λ}x) ,

with c^{±} ∈ ℝ ∪ {−∞}. The Busemann points w^{±} are the limits of the geodesics t ↦ ±t, from [0, ∞[ to ℝ. Hence, Proposition 7.6 allows us to determine the maximal representing measure μ_{u}, or equivalently, the maximal value of the scalars c^{±}, as follows:

c^{±} = lim_{t→±∞} u(t) ∓ ϑ_{λ}t .

In this special case, the representing measure is unique. In order to give another example, we characterise the Busemann points of a polyhedral norm. We call proper face of a polytope the intersection of this polytope with a supporting half-space.

Proposition 12.9. Let ∥ · ∥ denote a polyhedral norm on ℝ^{n}, so that

∥x∥ = max_{i∈I} x′_{i} · x ,

where (x′_{i})_{i∈I} is the finite family of the extreme points of the dual unit ball. The Martin boundary of the kernel (x, y) ↦ −∥x − y∥, taking the origin as the basepoint, is precisely the set of functions of the form

x ↦ min_{j∈J} x′_{j} · (x − X) + max_{j∈J} x′_{j} · X ,  (36)

where X ∈ ℝ^{n} and (x′_{j})_{j∈J} is the set of extreme points of a proper face of the dual unit ball. Moreover, all the points of the Martin boundary are Busemann points.

Proof. Any point f of the Martin boundary is the limit of a sequence of functions

x ↦ f^{k}(x) = ∥X^{k}∥ − ∥X^{k} − x∥ ,

where X^{k} ∈ ℝ^{n} and ∥X^{k}∥ → ∞ when k → ∞. Consider the sequence of vectors

u^{k} = (x′_{i} · X^{k} − ∥X^{k}∥)_{i∈I} .

These vectors lie in [−∞, 0]^{I}, which is compact and metrisable, and so, we may assume, by taking a subsequence if necessary, that u^{k} converges to some vector u ∈ [−∞, 0]^{I}. Since I is finite, we may also assume, again taking a subsequence if necessary, that there exists an index j_{0} ∈ I such that x′_{j_{0}} · X^{k} = ∥X^{k}∥ for all k. Let J := {i ∈ I | u_{i} > −∞}. Observe that J is non-empty since u_{j_{0}} = 0. We have

f(x) = lim_{k→∞} f^{k}(x) = lim_{k→∞} − max_{i∈I}(x′_{i} · X^{k} − ∥X^{k}∥ − x′_{i} · x)

= − max_{j∈J}(u_{j} − x′_{j} · x) .

Observe that the set E := {((x′_{j} − x′_{j_{0}}) · X)_{j∈J} | X ∈ ℝ^{n}} is closed, since it is a finite-dimensional vector space. Since the vector (u^{k})_{j∈J} belongs to E and has a finite limit when k → ∞, this limit belongs to E, and so there exists some X ∈ ℝ^{n} such that u_{j} = x′_{j} · X − x′_{j_{0}} · X for all j ∈ J. Thus,

f(x) = − max_{j∈J} x′_{j} · (X − x) + x′_{j_{0}} · X .

Since f(0) = 0, we have max_{j∈J} x′_{j} · X = x′_{j_{0}} · X, and so

f(x) = − max_{j∈J} x′_{j} · (X − x) + max_{j∈J} x′_{j} · X ,

which is of the form (36). We now have to show that (x′_{j})_{j∈J} is the set of extreme points of a face of the dual unit ball. Let E′ denote the set of vectors x′ ∈ ℝ^{n} such that x′·X^{k} −∥X^{k}∥ remains bounded when k tends to infinity. This is an affine space. Let B′ denote the dual unit ball. We claim that F′ := E′ ∩ B′ is an extreme subset of B′, meaning that

αx′ + (1 − α)y′ ∈ F′ ⟹ x′, y′ ∈ F′, for all x′, y′ ∈ B′ and 0 < α < 1. (37)

Indeed, let x′, y′ ∈ B′ and 0 < α < 1. Since x′ ∈ B′, we have x′·X ≤ ∥X∥ for all X ∈ ℝ^{n}. In particular, x′·X^{k}−∥X^{k}∥ ≤ 0 for all k. Similarly, y′·X^{k}−∥X^{k}∥ ≤ 0 for all k. Since

(αx′ + (1 − α)y′) · X^{k} − ∥X^{k}∥

= α(x′ · X^{k} − ∥X^{k}∥) + (1 − α)(y′ · X^{k} − ∥X^{k}∥)

≤ α(x′ · X^{k} − ∥X^{k}∥)

≤ 0 , we deduce that x′ · X^{k} − ∥X^{k}∥ is bounded if αx′ + (1 − α)y′ ∈ F′. Similarly, y′ · X^{k} − ∥X^{k}∥ is bounded. This shows (37). Let z denote any accumulation point of the sequence ∥X^{k}∥^{−1}X^{k}. We have F′ ⊂ {x′ ∈ B′ | x′ · z = 1}, and so, F′ ≠ B′. Since the dual ball B′ is a polytope, the convex extreme subset F′ ≠ B′ is a proper face of B′. Therefore, the vectors x′_{i}, with i ∈ I, such that x′_{i}·X^{k}−∥X^{k}∥ remains bounded are precisely the x′_{i} that belong to the proper face F′. Hence, these x′_{i} are the extreme points of the proper face F′. Every proper face F′ of the dual ball is the intersection of the dual ball with a supporting hyperplane, so F′ = {x′ ∈ B′ | x′ · y = 1} for some y ∈ B. Observe that the set J of x′_{i} such that x′_{i} · y = 1 is precisely the set of extreme points of F′. Consider now X ∈ ℝ^{n} and the ray t ↦ X + ty, which is a geodesic, and a fortiori an almost-geodesic. One readily checks that the function x ↦ ∥X + ty∥ − ∥X + ty − x∥ converges to the function (36) when t tends to +∞, and so, every point of the Martin boundary is a Busemann point.

Remark 12.10. Karlsson, Metz, and Noskov [KMN06] have shown previously that every boundary point of a polyhedral normed space is the limit of a geodesic, and hence a Busemann point. They did this by characterising the sequences which converge to a boundary point.

Example 12.11. Consider now L(x) := ∥x∥_{∞}^{p}/p with ∥x∥_{∞} := max(|x_{1}|, ⋯, |x_{n}|) and p > 1. By Proposition 12.9, the Busemann points of (ℝ^{n}, ∥ · ∥_{∞}) with respect to the basepoint 0 are of the form:

w : x ↦ min_{i∈I} ϵ_{i}(x_{i} − X_{i}) + max_{i∈I} ϵ_{i}X_{i} ,

where I is a non-empty subset of {1, …, n}, ϵ_{i} = ±1, and the X_{i} are arbitrary reals. Theorem 12.5 shows that any eigenvector with eigenvalue λ > 0 of the Lax-Oleinik semigroup can be written as a supremum of maps c + ϑ_{λ}w, where c ∈ ℝ ∪ {−∞} and w is of the above form. For instance, when n = 2, the functions w are of one of the following forms:

ϵ_{1}x_{1}, ϵ_{2}x_{2}, or min(ϵ_{1}(x_{1} − X_{1}), ϵ_{2}(x_{2} − X_{2})) + max(ϵ_{1}X_{1}, ϵ_{2}X_{2}) ,

with X_{1}, X_{2} ∈ ℝ and ϵ_{1} = ±1, ϵ_{2} = ±1.

Remark 12.12. It is natural to ask whether the eigenvectors of the Lax-Oleinik semigroup (T^{t})_{t≥0} coincide with the viscosity solutions of the ergodic Hamilton-Jacobi equation

L^{⋆}(∇u) = λ ,

where L^{⋆} denotes the Legendre-Fenchel transform of L. This is proved in [Fat08, Chapter 7] in the different setting where the space is a compact manifold and the Lagrangian L can depend on both the position and the speed but must satisfy certain regularity and coercivity conditions.

References

[AG03] M. Akian and S. Gaubert. Spectral theorem for convex monotone homogeneous maps, and ergodic control. Nonlinear Analysis. Theory, Methods & Applications, 52(2):637–679, 2003.

[AGW05] M. Akian, S. Gaubert, and C. Walsh. Discrete max-plus spectral theory. In G. L. Litvinov and V. P. Maslov, editors, Idempotent Mathematics and Mathematical Physics, Contemporary Mathematics, pages 19–51. American Mathematical Society, 2005. arXiv:math.SP/0405225.

[Aki95] Marianne Akian. Theory of cost measures: convergence of decision variables. Rapport de recherche 2611, INRIA, 1995.

[Aki99] Marianne Akian. Densities of idempotent measures and large deviations. Trans. Amer. Math. Soc., 351(11):4515–4543, 1999.

[And04] P.D. Andreev. Ideal closures of Busemann space and singular Minkowski space. arXiv:math.GT/0405121, 2004.

[And07] P. D. Andreev. Geometry of ideal boundaries of geodesic spaces with nonpositive curvature in the sense of Busemann. Mat. Tr., 10(1):16–28, 2007.

[AQV98] M. Akian, Jean-Pierre Quadrat, and M. Viot. Duality between probability and optimization. In J. Gunawardena, editor, Idempotency, pages 331–353. Cambridge University Press, 1998.

[Bal95] Weerner Ballmann. Lecture on spaces of nonpositive curvature. Birkhäuser, 1995.

[Bap98] R. B. Bapat. A max version of the Perron-Frobenius theorem. Linear Algebra Appl., 275/276:3–18, 1998.

[BCOQ92] F. Baccelli, G. Cohen, G. J. Olsder, and Jean-Pierre Quadrat. Synchronization and linearity : an algebra for discrete events systems. John Wiley & Sons, New-York, 1992.

[BGS85] Werner Ballmann, Mikhael Gromov, and Viktor Schroeder. Manifolds of nonpositive curvature, volume 61 of Progress in Mathematics. Birkhäuser Boston Inc., Boston, MA, 1985.

[CG79] Raymond Cuninghame-Green. Minimax algebra. Springer-Verlag, Berlin, 1979.

[CGQ04] G. Cohen, S. Gaubert, and J.-P. Quadrat. Duality and separation theorems in idempotent semimodules. Linear Algebra and Appl., 379:395–422, 2004. arXiv:math.FA/0212294.

[Con01] G. Contreras. Action potential and weak KAM solutions. Calc. Var. Partial Differential Equations, 13(4):427–458, 2001.

[Doo59] J. L. Doob. Discrete potential theory and boundaries. J. Math. Mech., 8:433–458; erratum 993, 1959.

[Dud92] P.I. Dudnikov. Endomorphisms of the semimodules of bounded functions. In Idempotent analysis, volume 13 of Advances In Soviet Mathematics, pages 47–63. Amer. Math. Soc., Providence, 1992.

[Dyn69] E.B. Dynkin. Boundary theory of Markov processes (the discrete case). Russian Math. Surveys, 24(7):1–42, 1969.

[Eva98] Laurence C. Evans. Partial differential equations. AMS, 1998.

[Fat97a] Albert Fathi. Solutions KAM faibles conjuguées et barrières de Peierls. C. R. Acad. Sci. Paris Sér. I Math., 325(6):649–652, 1997.

[Fat97b] Albert Fathi. Théorème KAM faible et théorie de Mather sur les systèmes lagrangiens. C. R. Acad. Sci. Paris Sér. I Math., 324(9):1043–1046, 1997.

[Fat03] Albert Fathi. Regularity of C^{1} solutions of the Hamilton-Jacobi equation. Ann. Fac. Sci. Toulouse Math. (6), 12(4):479–516, 2003.

[Fat08] A. Fathi. Weak KAM theorem in Lagrangian Dynamics. Cambridge University Press, 2008. To appear.

[FM02] A. Fathi and E. Maderna. Weak KAM theorem on non compact manifolds. Preprint. To appear in Nonlinear Differ. Equ. Appl., 2002.

[FS04] Albert Fathi and Antonio Siconolfi. Existence of C^{1} critical subsolutions of the Hamilton-Jacobi equation. Invent. Math., 155(2):363– 388, 2004.

[GM77] M. Gondran and M. Minoux. Valeurs propres et vecteurs propres dans les dioïdes et leur interprétation en théorie des graphes. Bull. Direction Études Recherches Sér. C Math. Informat., 2:i, 25–41, 1977.

[GM02] M. Gondran and M. Minoux. Graphes, Dioïdes et semi-anneaux. TEC & DOC, Paris, 2002.

[Gro81] M. Gromov. Hyperbolic manifolds, groups and actions. In Riemann surfaces and related topics: Proceedings of the 1978 Stony Brook Conference (State Univ. New York, Stony Brook, N.Y., 1978), volume 97 of Ann. of Math. Stud., pages 183–213, Princeton, N.J., 1981. Princeton Univ. Press.

[Hun60] G. A. Hunt. Markoff chains and Martin boundaries. Illinois J. Math., 4:313–340, 1960.

[IM07] H. Ishii and H. Mitake. Representation formulas for solutions of Hamilton-Jacobi equations with convex hamiltonians. Indiana Univ. Math. J., 56(5), 2007.

[KM97] V. N. Kolokoltsov and V. P. Maslov. Idempotent analysis and applications. Kluwer Acad. Publisher, 1997.

[KMN06] A. Karlsson, V. Metz, and G. A. Noskov. Horoballs in simplices and Minkowski spaces. Int. J. Math. Math. Sci., pages Art. ID 23656, 20, 2006.

[LMS01] G. L. Litvinov, V. P. Maslov, and G. B. Shpiz. Idempotent functional analysis: An algebraical approach. Mat. Notes, 69(5):696– 729, 2001.

[Mar41] Robert S. Martin. Minimal positive harmonic functions. Trans. Amer. Math. Soc., 49:137–172, 1941.

[Mas87] V. Maslov. Méthodes opératorielles. Éditions Mir, Moscow, 1987. Translated from the Russian.

[MS92] V. P. Maslov and S. N. Samborskiĭ. Idempotent analysis, volume 13 of Advances In Soviet Mathematics. Amer. Math. Soc., Providence, 1992.

[MSS00] R. S. MacKay, S. Slijepčević, and J. Stark. Optimal scheduling in a periodic environment. Nonlinearity, 13(1):257–297, 2000.

[NS66] P. Ney and F. Spitzer. The Martin boundary for random walk. Trans. A.M.S., 121:116–132, 1966.

[OV91] George L. O’Brien and Wim Vervaat. Capacities, large deviations and loglog laws. In Stable processes and related topics (Ithaca, NY, 1990), volume 25 of Progr. Probab., pages 43–83. Birkhäuser Boston, Boston, MA, 1991.

[Puh01] Anatoly Puhalskiĭ. Large Deviations and Idempotent Probability. Number 119 in Monographs and Surveys in Pure and Applied Mathematics. Chapman & Hall, 2001.

[Rie02] Marc A. Rieffel. Group C^{∗}-algebras as compact quantum metric spaces. Doc. Math., 7:605–651 (electronic), 2002. arXiv:math.OA/0205195.

[Roc70] R. T. Rockafellar. Convex analysis. Princeton University Press Princeton, N.J., 1970.

[Rom67] I. V. Romanovskiĭ. Optimization of stationary control of discrete deterministic process in dynamic programming. Kibernetika, 3(2):66–78, 1967.

[Wal07] Cormac Walsh. The horofunction boundary of finite-dimensional normed spaces. Mathematical Proceedings of the Cambridge Philosophical Society, 142(03):497–507, 2007.

[Wal08] C. Walsh. The horofunction boundary of the Hilbert geometry. Advances in Geometry, 8(4):503–529, 2008.

[Wal09] Cormac Walsh. Minimum representing measures in idempotent analysis. In G.L. Litvinov and S.N. Sergeev, editors, Proceedings of the International Conference on Tropical and Idempotent Mathematics, Contemporary Mathematics. American Mathematical Society, 2009. To appear. Also arXiv:math.MG/0503716.

[WW05] Corran Webster and Adam Winchester. Boundaries of hyperbolic metric spaces. Pacific J. Math., 221(1):147–158, 2005.

[WW06] Corran Webster and Adam Winchester. Busemann points of infinite graphs. Trans. Amer. Math. Soc., 358(9):4209–4224, 2006.

[YK92] S. Yu. Yakovenko and L. A. Kontorer. Nonlinear semigroups and infinite horizon optimization. In Idempotent analysis, volume 13 of Adv. Soviet Math., pages 167–210. Amer. Math. Soc., Providence, RI, 1992.

Marianne Akian INRIA Saclay – Île-de-France and CMAP CMAP, École Polytechnique 91128 Palaiseau Cedex France marianne.akian@inria.fr Stéphane Gaubert INRIA Saclay – Île-de-France and CMAP CMAP, École Polytechnique 91128 Palaiseau Cedex France stephane.gaubert@inria.fr

Cormac Walsh

INRIA Saclay – Île-de-France and CMAP CMAP, École Polytechnique 91128 Palaiseau Cedex France cormac.walsh@inria.fr