# Nonexpansive maps with surjective displacement

Brian Lins  Brian Lins, Hampden-Sydney College<EMAIL_ADDRESS>
###### Abstract.

We investigate necessary and sufficient conditions for a nonexpansive map $f$
on a Banach space $X$ to have surjective displacement, that is, for
$f-\mathrm{id}$ to map onto $X$. In particular, we give a computable necessary
and sufficient condition when $X$ is a finite dimensional space with a
polyhedral norm. We give a similar computable necessary and sufficient
condition for a fixed point of a polyhedral norm nonexpansive map to be
unique. We also consider applications to nonlinear Perron-Frobenius theory and
suggest some additional computable sufficient conditions for surjective
displacement and uniqueness of fixed points.

###### Key words and phrases:

Nonexpansive maps, surjective displacement, nonlinear Perron-Frobenius theory,
topical maps, subtopical maps, existence and uniqueness of fixed points,
metric compactification, horofunctions

###### 2010 Mathematics Subject Classification:

Primary 47H09, 47H10, 47H07; Secondary 54D35

##  1\. Introduction

Given a nonexpansive map on a metric space, it is not always easy to determine
whether the map has any fixed points. In Banach spaces with the fixed point
property, any nonexpansive map that leaves a closed, bounded, convex set
invariant has a fixed point. However, in applications it can be difficult to
determine whether a nonexpansive map has any invariant, bounded, closed,
convex sets.

For finite dimensional Banach spaces, necessary and sufficient conditions for
nonexpansive maps to have a nonempty and bounded set of fixed points were
given in [21]. When $X$ is a finite dimensional normed space with either a
smooth norm or a polyhedral norm, [21, Section 4] describes a non-
deterministic algorithm that eventually halts (almost certainly) if and only
if the fixed point set is nonempty and bounded.

Somewhat surprisingly, it may be easier to determine whether a nonexpansive
map $f:X\rightarrow X$ has the stronger property that the map $f+u$ has a
fixed point for every $u\in X$. This is equivalent to $f$ having surjective
displacement, that is $f-\mathrm{id}$ being onto. The main result of this
paper is a computable test involving a finite set of limits which determines
whether or not $f$ has surjective displacement when $X$ is a polyhedral normed
space. A similar test can also determine whether a fixed point of a
nonexpansive map on a polyhedral normed space is unique.

A motivation for this investigation comes from nonlinear Perron-Frobenius
theory which seeks conditions for the existence and also uniqueness of
eigenvectors of order-preserving and homogeneous maps. Some general results in
this area include [7, 23, 25, 24, 12, 3]. Many of these results rely on the
close connection between nonlinear Perron-Frobenius theory and the theory of
nonexpansive maps, see e.g. [20, 22].

Our results are inspired by a hypergraph condition from [3] that determines
whether or not an order-preserving, additively homogeneous function
$T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ has several properties, one of
which is that the functions $T+u$ have an additive eigenvector for every
$u\in\mathbb{R}^{n}$ (see also [2] where the hypergraph condition was first
introduced for Shapley operators associated with certain two-player games).
Order-preserving and additively homogeneous maps on $\mathbb{R}^{n}$ are
nonexpansive with respect to the variation seminorm, so the results in [2] and
[3] can be interpreted as fixed point results for a special class of
nonexpansive maps. We will show that the results in [3] can be derived from
our general test for surjective displacement of a polyhedral norm nonexpansive
map.

The paper is organized as follows. We begin by collecting some facts about
nonexpansive maps, Banach spaces, and the metric compactification and
horofunctions of a Banach space. We use these facts in Section 3 to identify
necessary and sufficient conditions for a nonexpansive map to have surjective
displacement. The main result of Section 3 is Theorem 3.7 which summarizes
these conditions for finite and infinite dimensional Banach spaces. In Section
4 we prove our main result which is a computable necessary and sufficient
condition for a polyhedral norm nonexpansive map to have surjective
displacement. We look at applications of our main result to nonlinear Perron-
Frobenius theory in Section 5 and in Section 6 we give a computable necessary
and sufficient condition for a fixed point of a polyhedral norm nonexpansive
map to be unique. We conclude with a look at other computable sufficient
conditions for a nonexpansive map to have surjective displacement or a unique
fixed point.

##  2\. Preliminaries

For any metric space $(X,d)$, a map $f:X\rightarrow X$ is _nonexpansive_ if
$d(f(x),f(y))\leq d(x,y)$ for all $x,y\in M$. Here we focus on nonexpansive
maps $f$ defined on a real Banach space. For a Banach space $X$, we use the
following notation for the norm $\|\cdot\|$, dual space $X^{*}$, and dual norm
$\|\cdot\|_{*}$. Let $B_{R}$ denote the closed ball with radius $R$ and center
$0$ in $X$ and let $B^{*}_{R}$ denote the closed ball of radius $R$ around $0$
in $X^{*}$. The identity map on $X$ is $\mathrm{id}$, and $J$ denotes the set-
valued _duality map_ $J:X\rightrightarrows X^{*}$ given by

$J(x):=\\{x^{*}\in X^{*}:\|x^{*}\|_{*}=\|x\|,\left\langle
x,x^{*}\right\rangle=\|x\|\,\|x^{*}\|_{*}\\}.$

For any function $f:X\rightarrow X$, we refer to $f-\mathrm{id}$ as the
_displacement map_ associated with $f$. We say that $f$ has _surjective
displacement_ if $f-\mathrm{id}$ maps onto $X$ and $f$ has _dense
displacement_ if the range of $f-\mathrm{id}$ is dense in $X$. For any
$\delta\geq 0$, we define $F_{\delta}(f)=\\{x\in X:\|f(x)-x\|\leq\delta\\}$.
When $\delta>0$, we refer to $F_{\delta}(f)$ as an _approximate fixed point
set_ of $f$. Of course, $F_{0}(f)$ is the set of fixed points of $f$.

A convex subset $F$ of a convex set $C$ is called a _face_ of $C$ if
$tx+(1-t)y\in F$ with $x,y\in C$ and $0<t<1$ implies that $x$ and $y$ are
contained in $F$. If $F$ is a face of $C$ and $F\neq C$, then $F$ is a _proper
face_. The intersection of a supporting hyperplane with $C$ is called an
_exposed face_. All exposed faces are proper faces, but there are simple
examples where proper faces are not exposed faces (see [29, Section 18]). For
any convex set $C$, we denote the extreme points of $C$ by
$\operatorname{ext}C$ and the relative interior of $C$ by
$\operatorname{ri}C$. For a proper face of $F$ of the unit ball in a real
Banach space, the _dual face_ $F^{*}$ is the image of $\operatorname{ri}F$
under the duality mapping $J$.

A norm $\|\cdot\|$ on $X$ is _polyhedral_ if the unit ball $B_{1}$ is a convex
polytope, that is, if it has a finite number of extreme points. A real Banach
space $X$ is _strictly convex_ if $\|x+y\|<2$ whenever $x,y\in X$ with $x\neq
y$ and $\|x\|=\|y\|=1$. It is _uniformly convex_ if for every $0<\epsilon\leq
2$, there is a $\delta>0$ such that for any $x,y\in X$ with $\|x\|=\|y\|=1$
and $\|x-y\|\geq\epsilon$, $\|x+y\|\leq 2-\delta$. A real Banach space $X$ is
_smooth_ if $X^{*}$ is strictly convex, and _uniformly smooth_ if $X^{*}$ is
uniformly convex. Note that uniformly convex and uniformly smooth Banach
spaces are always reflexive [8, Corollary 3.21 and Theorem 3.31].

A Banach space $X$ has the _fixed point property_ if for every closed,
bounded, convex subset $C\subset X$ and every nonexpansive map $f:C\rightarrow
C$, $f$ has a fixed point. Browder [9] and Göhde [14] independently proved
that uniformly convex Banach spaces have the fixed point property, while Kirk
proved that reflexive Banach spaces with normal structure have the fixed point
property [19]. It turns out that all uniformly convex Banach spaces have
normal structure [5, Theorem 4.1], while there are examples of reflexive
Banach spaces with normal structure that are not isomorphic to any uniformly
convex Banach space [6]. Therefore Kirk’s result is more general than the
results of Browder and Göhde. Since then, other conditions have been found
that are sufficient for a Banach space to have the fixed point property. It is
a famous open problem whether or not all reflexive Banach spaces have the
fixed point property. See [11] and the references therein for some recent
contributions and a good introduction to the topic.

###  2.1. The metric compactification and horofunctions.

In any metric space $(X,d)$, we can choose an arbitrary base point $b$, and
consider the functions

$h_{y}(x)=d(x,y)-d(b,y).$

Each of these functions is 1-Lipschitz and $h_{y}(b)=0$. Therefore $h_{y}(x)$
takes values in the closed interval $[-d(x,b),d(x,b)]\subset\mathbb{R}$ for
each $x\in X$, so each function $h_{y}$ can be identified with an element of
the product space

$\prod_{x\in X}[-d(x,b),d(x,b)]$

which is a compact topological space by Tychonoff’s theorem. The topology on
the product space is equivalent to the topology of pointwise convergence, and
the closure of the set $\\{h_{y}:y\in X\\}$ in this topology is known as the
_metric compactification of_ $(X,d)$. The elements of the metric
compactification are called _metric functionals_. Metric functionals include
both the functions $h_{y}$ described above, and also functions on the boundary
of the metric compactification, which are known as _horofunctions_. Any
horofunction $h$ is a pointwise limit

$h(x)=\lim_{\beta}d(x,y_{\beta})-d(b,y_{\beta})$

where $y_{\beta}$ is a net in $(X,d)$. For 1-Lipschitz functions, the topology
of pointwise convergence is equivalent to the topology of uniform convergence
on compact subsets of $X$ by the Arzelà-Ascoli theorem. If the metric space
$(X,d)$ is proper, i.e., all closed balls in $X$ are compact, then the
topology of uniform convergence on compact subsets of $X$ is metrizable. In
that case, we can use sequences $y_{k}$ to define horofunctions rather than
nets. This is true, in particular, if $X$ is a finite dimensional Banach
space. In addition, $d(b,y_{k})\rightarrow\infty$ for any sequence $y_{k}$
that defines a horofunction in a proper metric space. Note that horofunctions
are always 1-Lipschitz. In a Banach space, horofunctions are also convex.
Since the base point $b\in X$ is arbitrary, it is standard practice to choose
$b=0$ when $X$ is a Banach space.

In a finite dimensional real Banach space, Walsh has shown (implicitly in [31,
Theorem 1.1]), that a subset of the horofunctions known as the Busemann points
are given by

(2.1) $h(x)=\sup_{\nu\in F^{*}}\left\langle u-x,\nu\right\rangle,$

where $F^{*}$ is a proper face of $B_{1}^{*}$ and $u\in X$ satisfies
$\sup_{\nu\in F^{*}}\left\langle u,\nu\right\rangle=0$. For some finite
dimensional Banach spaces all horofunctions are Busemann points, but this is
not true in general. The following is [31, Theorem 1.2].

######  Theorem 2.1 (Walsh).

Let $X$ be a finite dimensional real Banach space. All horofunctions on $X$
are Busemann points given by (2.1) if and only if the faces of the dual unit
ball $B_{1}^{*}$ are closed in the Painlevé-Kuratowski topology. This is true,
in particular, if $X$ has a polyhedral norm or if $X$ is smooth.

Even when a horofunction on a finite dimensional normed space is not a
Busemann point, we can still make the following observation. Note that this
result was part of the proof of [21, Theorem 3.4], however we reproduce the
proof here for the reader’s convenience.

######  Lemma 2.2.

Let $X$ be a finite dimensional real Banach space. For any horofunction $h$ on
$X$, there is a $v\in X$ with $\|v\|=1$ such that

$h(x+tv)=h(x)-t$

for all $x\in X$ and $t\in\mathbb{R}$.

###### Proof.

There is a sequence $x_{k}$ with $\|x_{k}\|\rightarrow\infty$ such that

$h(x)=\lim_{k\rightarrow\infty}\|x-x_{k}\|-\|x_{k}\|.$

We may assume, by passing to a subsequence if necessary, that
$\lim_{k\rightarrow\infty}x_{k}/\|x_{k}\|=v$. Then

$\displaystyle\left|\left|x+t\frac{x_{k}-x}{\|x_{k}-x\|}-x_{k}\right|\right|-\|x_{k}\|$
$\displaystyle=\|x-x_{k}\|\left(1-\frac{t}{\|x_{k}-x\|}\right)-\|x_{k}\|$
$\displaystyle=\|x-x_{k}\|-\|x_{k}\|-t.$

In the limit as $k\rightarrow\infty$, this equation becomes $h(x+tv)=h(x)-t$.
∎

Unfortunately, Lemma 2.2 does not hold for infinite dimensional Banach spaces.
Gutiérrez [15] has given a complete description of the horofunctions on
infinite dimensional Hilbert spaces and $\ell_{p}$ spaces with $1\leq
p<\infty$. In some Banach spaces (including Hilbert spaces), there are non-
trivial horofunctions $h$ that are bounded below. Even when a horofunction is
not bounded below, it is possible that there is no direction $v\in X$ such
that $\lim_{t\rightarrow\infty}h(tv)=-\infty$ as the following example shows.

######  Example 2.3.

By [15, Theorem 3.6], the function

$h(x)=\sum_{i\in\mathbb{N}}(|x_{i}-1|-1)$

is a horofunction on the real Banach space $\ell_{1}(\mathbb{N})$. At the same
time, it can be shown that $\lim_{t\rightarrow\infty}h(tv)=+\infty$ for all
nonzero $v\in\ell_{1}(\mathbb{N})$ even though
$\inf_{x\in\ell_{1}(\mathbb{N})}h(x)=-\infty$.

However, when $X$ is uniformly smooth, the following result is an immediate
consequence of [15, Lemma 5.3].

######  Lemma 2.4 (Gutiérrez).

Let $X$ be a uniformly smooth real Banach space. If $h$ is a horofunction on
$X$ with $\inf_{x\in X}h(x)=-\infty$, then there is a nonzero linear
functional $\nu\in B_{1}^{*}$ such that $h(x)=-\left\langle
x,\nu\right\rangle$ for all $x\in X$.

In the sequel, we will use horofunctions to help understand nonexpansive maps.
One important result we will use is the following special case of [13, Theorem
1]. Note that all Banach spaces are metrically star-shaped, as is any convex
subset of a Banach space.

######  Theorem 2.5 (Gaubert-Vigeral).

Let $T$ be a nonexpansive self-map of a complete metrically star-shaped metric
space $(X,d)$. If $\rho(T)=\inf_{y\in X}d(y,T(y))>0$, then there is a
horofunction $h$ on $X$ such that $h(T(x))\leq h(x)-\rho(T)$ for all $x\in X$.

##  3\. Surjective displacement

The following theorem characterizes when nonexpansive maps on a finite
dimensional normed space have surjective displacement. The equivalence of
conditions (2), (3), and (4) was already observed by Hochart in [16, Corollary
4].

######  Theorem 3.1.

Let $X$ be a finite dimensional real Banach space and suppose $f:X\rightarrow
X$ is nonexpansive. The following are equivalent:

  1. (1)

There is no horofunction $h$ and constant $c\in\mathbb{R}$ such that
$h(f(x))\leq h(x)+c$ for all $x\in X$.

  2. (2)

The approximate fixed point sets $F_{\delta}(f)$ are bounded for all
$\delta>0$.

  3. (3)

$f+u$ has a nonempty and bounded set of fixed points for all $u\in X$.

  4. (4)

$f-\mathrm{id}$ maps onto $X$.

###### Proof.

(1) $\Rightarrow$ (2). Suppose $F_{\delta}(f)$ is not bounded for some
$\delta>0$. Then there is a sequence $x_{k}$ such that
$\|x_{k}\|\rightarrow\infty$ while $\|f(x_{k})-x_{k}\|\leq\delta$ for all
$k\geq 0$. Replacing $x_{k}$ with a subsequence if necessary, we may assume
that the horofunction $h(x)=\lim_{k\rightarrow\infty}\|x-x_{k}\|-\|x_{k}\|$ is
defined on $X$. Then

$\displaystyle h(f(x))$
$\displaystyle=\lim_{k\rightarrow\infty}\|f(x)-x_{k}\|-\|x_{k}\|$
$\displaystyle\leq\liminf_{k\rightarrow\infty}\|f(x)-f(x_{k})\|+\|f(x_{k})-x_{k}\|-\|x_{k}\|$
$\displaystyle(\text{triangle inequality})$
$\displaystyle\leq\liminf_{k\rightarrow\infty}\|x-x_{k}\|+\delta-\|x_{k}\|$
$\displaystyle(\text{by nonexpansiveness})$ $\displaystyle=h(x)+\delta$

for all $x\in X$. This contradicts (1).

(2) $\Rightarrow$ (3). Choose any $u\in X$. Let $x_{k}$ be defined recursively
by $x_{0}=0$ and $x_{k+1}=f(x_{k})+u$. Since $f+u$ is nonexpansive,

$\displaystyle\|f(x_{k})-x_{k}\|$
$\displaystyle\leq\|f(x_{k})+u-x_{k}\|+\|u\|$ $\displaystyle(\text{triangle
inequality})$ $\displaystyle\leq\|f(0)+u\|+\|u\|$ $\displaystyle(\text{by
nonexpansiveness})$

for all $k$. Let $\delta=\|f(0)+u\|+\|u\|$. Since the set $F_{\delta}(f)$ is
bounded, it follows that $x_{k}$ is a bounded orbit of $f+u$, and therefore
$f+u$ must have a fixed point [22, Proposition 3.2.4]. The fixed point set for
$f+u$ must also be bounded because it is contained in $F_{\delta}(f)$.

(3) $\Rightarrow$ (4). This is obvious since $-u$ is in the range of
$f-\mathrm{id}$ if and only if $f+u$ has a fixed point.

(4) $\Rightarrow$ (1). Consider any horofunction $h$ on $X$. By Lemma 2.2,
there is a $v\in X$ such that $h(x+tv)=h(x)-t$ for all $t\in\mathbb{R}$ and
$x\in X$. Since $f-\mathrm{id}$ is onto, we can choose $x\in X$ such that
$f(x)=x+tv$. Then $h(f(x))=h(x)-t$, which proves (1). ∎

In the rest of this section, we will consider necessary and sufficient
conditions on any (finite or infinite dimensional) Banach space to have
surjective displacement. Before proving the main result of the section, we
need the following minor results.

######  Lemma 3.2.

Suppose that $X$ is a real Banach space and $f:X\rightarrow X$ is
nonexpansive. For any $x\in X$ with $\|x\|=1$, and any $x^{*}\in J(x)$, the
real function $t\mapsto\left\langle f(tx)-tx,x^{*}\right\rangle$ is monotone
decreasing. Consequently, $\lim_{t\rightarrow\infty}\left\langle
f(tx)-tx,x^{*}\right\rangle$ is either $-\infty$ or it converges to a finite
value.

###### Proof.

Consider $t_{1}<t_{2}$ and observe that

$\displaystyle\left\langle f(t_{2}x)-f(t_{1}x),x^{*}\right\rangle$
$\displaystyle\leq\|f(t_{2}x)-f(t_{1}x)\|$ $\displaystyle\text{ (since
}\|x^{*}\|_{*}=1)$ $\displaystyle\leq\|t_{2}x-t_{1}x\|$ (by nonexpansiveness)
$\displaystyle=\left\langle t_{2}x-t_{1}x,x^{*}\right\rangle.$
$\displaystyle\text{ (since }t_{2}>t_{1}\text{ and }x^{*}\in J(x))$

Rearranging terms, we have $\left\langle
f(t_{2}x)-t_{2}x,x^{*}\right\rangle\leq\left\langle
f(t_{1}x)-t_{1}x,x^{*}\right\rangle$, as claimed. ∎

The next lemma is a semidifferentiability property of Banach space norms that
is not new, but we could not find a reference. Before stating the result, we
review some terminology about convex functions. Let $X$ be a real Banach space
and suppose that $f:X\rightarrow\mathbb{R}$ is a convex function. An $x^{*}\in
X^{*}$ is called a _subgradient_ of $f$ at $x$ if $f(z)-f(x)\geq\left\langle
z-x,x^{*}\right\rangle$ for all $z\in X$. The set of all subgradients at $x$
is called the _subdifferential_ of $f$ at $x$. For any $x\in X$ with
$\|x\|=1$, the subdifferential for the norm at $x$ is precisely $J(x)$.

######  Lemma 3.3.

Let $X$ be a real Banach space and let $x,y\in X$ with $\|x\|=1$. Then there
exists $x^{*}\in J(x)$ such that

(3.1) $\lim_{t\rightarrow\infty}\|tx-y\|-\left\langle
tx-y,x^{*}\right\rangle=0.$

###### Proof.

If $X$ is finite dimensional, then [29, Theorem 23.4] says that

$\lim_{\epsilon\rightarrow 0^{+}}\frac{\|x-\epsilon
y\|-\|x\|}{\epsilon}=\sup_{x^{*}\in J(x)}\left\langle-y,x^{*}\right\rangle$

since $J(x)$ is the subdifferential of the norm at $x$. Furthermore $J(x)$ is
compact, so there is an $x^{*}\in J(x)$ where the supremum is attained, and
then

$\lim_{\epsilon\rightarrow 0^{+}}\frac{\|x-\epsilon
y\|-\|x\|}{\epsilon}=-\left\langle y,x^{*}\right\rangle.$

By replacing $\epsilon$ with $t^{-1}$, we have (3.1). The infinite dimensional
version follows by first applying the result to the finite dimensional
subspace spanned by $x$ and $y$, and then extending the linear functional
$x^{*}$ to all of $X$ using the Hahn-Banach theorem. ∎

For any nonzero $x\in X$, let $W_{x}=\\{w\in X:\sup_{x^{*}\in
J(x)}\left\langle w,x^{*}\right\rangle<0\\}$. Note that each $W_{x}$ is a
nonempty open convex cone in $X$. The following result says that if certain
limits are bounded below, then the range of the displacement map does not
intersect a translate of $W_{x}$ for some $x$.

######  Lemma 3.4.

Let $X$ be a real Banach space and let $f:X\rightarrow X$ be nonexpansive. Let
$x\in X$ with $\|x\|=1$. If $\lim_{t\rightarrow\infty}\left\langle
f(tx)-tx,x^{*}\right\rangle\geq c$ for all $x^{*}\in J(x)$, then
$\operatorname{range}(f-\mathrm{id})$ does not intersect the open affine cone
$W_{x}+cx$.

###### Proof.

By Lemma 3.3, for any $y\in X$ there is an $x^{*}\in J(x)$ such that

$\displaystyle 0$
$\displaystyle=\lim_{t\rightarrow\infty}\|tx-y\|-\left\langle
tx-y,x^{*}\right\rangle$
$\displaystyle\geq\limsup_{t\rightarrow\infty}\|f(tx)-f(y)\|-\left\langle
tx-y,x^{*}\right\rangle$ $\displaystyle(\text{nonexpansiveness})$
$\displaystyle\geq\limsup_{t\rightarrow\infty}\left\langle
f(tx)-f(y),x^{*}\right\rangle-\left\langle tx-y,x^{*}\right\rangle$
$\displaystyle(\text{since }\|x^{*}\|_{*}=1)$
$\displaystyle=\lim_{t\rightarrow\infty}\left\langle
f(tx)-tx,x^{*}\right\rangle-\left\langle f(y)-y,x^{*}\right\rangle$
$\displaystyle\geq c-\left\langle f(y)-y,x^{*}\right\rangle.$

This means that $\sup_{x^{*}\in J(x)}\left\langle
f(y)-y,x^{*}\right\rangle\geq c$ so $f(y)-y\notin W_{x}+cx$. ∎

The next observation is also about the range of displacement maps, this time
when $f$ is nonexpansive with respect to a uniformly smooth norm. This lemma
can be proved directly from a more general result [27, Theorem 5.2] which says
that the closure of the range of an $m$-accretive operator on a smooth Banach
space is always convex. Here we take a different approach using horofunctions.

######  Lemma 3.5.

Let $X$ be a uniformly smooth real Banach space and suppose that
$f:X\rightarrow X$ is nonexpansive. The closure of the range of
$f-\mathrm{id}$ is convex.

###### Proof.

Suppose that $u\in X\backslash\overline{\operatorname{range}}(f-\mathrm{id})$.
Then $\inf_{x\in X}\|f(x)-u-x\|=\rho>0$. By Theorem 2.5, there is a
horofunction $h$ on $X$ such that $h(f(x)-u)\leq h(x)-\rho$ for all $x\in X$.
This horofunction cannot be bounded below since the iterates $(f-u)^{k}(0)$
have $h((f-u)^{k}(0))\rightarrow-\infty$. So Lemma 2.4 implies that there is a
nonzero linear functional $\nu\in B_{1}^{*}$ such that $h(x)=-\left\langle
x,\nu\right\rangle$ for all $x$. Then

$-\left\langle f(x)-u,\nu\right\rangle\leq-\left\langle
x,\nu\right\rangle-\rho$

for all $x\in X$. Equivalently,

$\left\langle f(x)-x,\nu\right\rangle\geq\left\langle
u,\nu\right\rangle+\rho.$

Therefore the linear functional $\nu$ separates $u$ from
$\overline{\operatorname{range}}(f-\mathrm{id})$. This means that
$\overline{\operatorname{range}}(f-\mathrm{id})$ is the intersection of an
infinite family of closed half-spaces (one for each
$u\notin\overline{\operatorname{range}}(f-\mathrm{id})$), and as such, it must
be a convex set. ∎

The last preliminary observation before the main result of this section is the
following fixed point theorem [17, Theorem 2.4].

######  Theorem 3.6 (Kaewcharoen-Kirk).

Let $X$ be a Banach space which has the fixed point property, let $C$ be a
closed, convex subset of $X$, and suppose that $f:C\rightarrow C$ is
nonexpansive. If $F_{\delta}(f)=\\{x\in C:\|f(x)-x\|\leq\delta\\}$ is bounded
and nonempty for some $\delta\geq 0$, then $f$ has a fixed point.

The main result of this section is the following theorem. Condition a in the
theorem is sufficient for a nonexpansive map to have surjective displacement
when the Banach space has the fixed point property, while condition e is
necessary for surjective displacement on any Banach space.

######  Theorem 3.7.

Let $f:X\rightarrow X$ be a nonexpansive map on a real Banach space $X$.
Consider the following possible conditions on $f$.

  1. (a)

The approximate fixed point sets $F_{\delta}(f)$ are bounded for all
$\delta>0$.

  2. (b)

$f+u$ has a nonempty and bounded set of fixed points for all $u\in X$.

  3. (c)

$f-\mathrm{id}$ maps onto $X$.

  4. (d)

The range of $f-\mathrm{id}$ is dense in $X$.

  5. (e)

For every $x\in X$ with $\|x\|=1$, there is an $x^{*}\in J(x)$ such that

$\lim_{t\rightarrow\infty}\left\langle f(tx)-tx,x^{*}\right\rangle=-\infty.$

For these conditions, the following implications are true.

  * •

Condition a implies d, b implies c, and d implies e.

  * •

If $X$ has the fixed point property, then a implies b.

  * •

If $X$ is uniformly smooth, then conditions d and e are equivalent.

  * •

If $X$ is a Hilbert space, then conditions b and c are equivalent.

  * •

If $X$ is finite dimensional with a smooth or polyhedral norm, then all five
conditions are equivalent.

###### Proof.

a $\Rightarrow$ d. Suppose by way of contradiction that condition d is false.
Then there is a $u\in
X\backslash\overline{\operatorname{range}}(f-\mathrm{id})$ and
$\rho=\inf_{x\in X}\|f(x)-u-x\|>0$. By Theorem 2.5, there is a horofunction
$h$ on $X$ such that $h(f(x)-u)\leq h(x)-\rho$ for all $x\in X$. Let the
sequence $x_{k}$ be defined recursively by $x_{0}=0$ and $x_{k+1}=f(x_{k})-u$.
Then $h(x_{k})\leq-\rho k$ for all $k\geq 0$. Since $h$ is 1-Lipschitz, this
implies that $\|x_{k}\|\rightarrow\infty$. At the same time, for all $k$ we
have

$\displaystyle\|f(x_{k})-x_{k}\|$
$\displaystyle\leq\|f(x_{k})-u-x_{k}\|+\|u\|$ (triangle inequality)
$\displaystyle\leq\|f(0)-u\|+\|u\|.$ $\displaystyle\text{(since }f-u\text{ is
nonexpansive)}$

So $x_{k}$ is an unbounded sequence contained in the set $F_{\delta}(f)$ with
$\delta=\|f(0)-u\|+\|u\|$ which contradicts a.

d $\Rightarrow$ e. Suppose that condition e fails, that is, there is a
constant $c\in\mathbb{R}$ and $x\in X$ with $\|x\|=1$ such that
$\lim_{t\rightarrow\infty}\left\langle f(tx)-tx,x^{*}\right\rangle\geq c$ for
all $x^{*}\in J(x)$. By Lemma 3.4, the range of $f-\mathrm{id}$ does not
contain any elements in the nonempty open set $\\{y\in X:\max_{y^{*}\in
J(x)}\left\langle y,y^{*}\right\rangle<c\\}$. This contradicts d.

a $\Rightarrow$ b. We assume here that $X$ has the fixed point property. Let
$x,u\in X$. Then $\|f(x)-x\|\leq\|f(x)+u-x\|+\|u\|$ by the triangle
inequality. Therefore $F_{\delta}(f+u)\subseteq F_{(\delta+\|u\|)}(f)$ is
bounded for every $\delta\geq 0$. By choosing $\delta$ large enough so that
$F_{\delta}(f+u)$ is nonempty and letting $C=X$, we see that Theorem 3.6
implies that $f+u$ has a fixed point. In addition, the fixed point set
$F_{0}(f+u)$ is bounded because it is contained in $F_{\|u\|}(f)$.

e $\Rightarrow$ d. Suppose now that $X$ is uniformly smooth. By Lemma 3.5,
$\overline{\operatorname{range}}(f-\mathrm{id})$ is convex. Suppose there
exists $u\in X\backslash\overline{\operatorname{range}}(f-\mathrm{id})$. By
the Hahn-Banach theorem, there is a linear functional $x^{*}\in X^{*}$ such
that $\left\langle f(x)-x,x^{*}\right\rangle>\left\langle
u,x^{*}\right\rangle$ for all $x\in X$. We may assume that $\|x^{*}\|_{*}=1$.
Since any uniformly smooth Banach space is reflexive, there exists $x\in X$
such that $x^{*}\in J(x)$, and since $X^{*}$ is uniformly convex, $x^{*}$ is
the only element of $J(x)$. Then the fact that $\left\langle
f(tx)-tx,x^{*}\right\rangle>\left\langle u,x^{*}\right\rangle$ for all $t>0$
contradicts e.

It is obvious that b implies c, so we will just prove the converse when $X$ is
a Hilbert space.

c $\Rightarrow$ b. Let $X$ be a Hilbert space. It suffices to prove that the
fixed point set $F_{0}(f)$ is bounded since the same argument will apply to
$f+u$ for any $u$. Choose any $w\in F_{0}(f)$ and $y\in X$. Since $f$ has
surjective displacement, there is an $x\in X$ such that $f(x)=x+y$. Then
$\|x+y-w\|^{2}=\|f(x)-f(w)\|^{2}\leq\|x-w\|^{2}$ by nonexpansiveness. Using
the inner-product to expand the norms in this inequality, and then canceling
terms, we find that $\left\langle w,y\right\rangle\geq\left\langle
x,y\right\rangle+\tfrac{1}{2}\|y\|^{2}$. We can also find a corresponding
upper bound $\left\langle w,y\right\rangle\leq\left\langle
x,y\right\rangle-\tfrac{1}{2}\|y\|^{2}$ by finding an $x\in X$ such that
$f(x)=x-y$. So there is a constant $b_{y}>0$, depending only on $y$, such that
$|\left\langle w,y\right\rangle|\leq b_{y}$ for all $w\in F_{0}(f)$. Thus
$F_{0}(f)$ is weakly bounded which means it must also be strongly bounded [8,
Corollary 2.4].

Now suppose that $X$ is finite dimensional and is either smooth or has a
polyhedral norm. By Theorem 3.1, conditions a, b, and c are equivalent, and
the above results tell us that a implies d and d implies e. Therefore, it
suffices to prove that e implies a.

e $\Rightarrow$ a. Suppose that condition a is not true. By Theorem 3.1, there
is a horofunction $h$ on $X$ and a constant $c\in\mathbb{R}$ such that
$h(f(x))\leq h(x)+c$ for all $x\in X$. Since we are assuming that either $X$
is smooth or $X$ has a polyhedral norm, Theorem 2.1 implies that $h$ is given
by (2.1) for some proper face $F^{*}$ of $B_{1}^{*}$ and some $u\in X$ such
that $\sup_{\nu\in F^{*}}\left\langle u,\nu\right\rangle=0$. Also, when $X$ is
smooth or has a polyhedral norm, all proper faces of $B^{*}_{1}$ are exposed
faces. Thus, there is an $x\in X$ with $\|x\|=1$ such that $F^{*}=J(x)$. Now,
for any $x^{*}\in F^{*}$ and $t>0$,

$\displaystyle\left\langle u-f(tx),x^{*}\right\rangle$
$\displaystyle\leq\sup_{\nu\in F^{*}}\left\langle u-f(tx),\nu\right\rangle$
$\displaystyle=h(f(tx))$ $\displaystyle(\text{by }\eqref{eq:Cormac})$
$\displaystyle\leq h(tx)+c$ $\displaystyle=\sup_{\nu\in F^{*}}\left\langle
u-tx,\nu\right\rangle+c$ $\displaystyle(\text{by }\eqref{eq:Cormac}\text{
again})$ $\displaystyle=-t+c.$ $\displaystyle(\text{since }J(x)=F^{*})$

By rearranging terms, we have $\left\langle
u,x^{*}\right\rangle-c\leq\left\langle f(tx),x^{*}\right\rangle-t=\left\langle
f(tx)-tx,x^{*}\right\rangle$. Since this is true for all $x^{*}\in J(x)$ and
$t>0$, we have contradicted condition e. ∎

######  Remark 3.8.

The implication a $\Rightarrow$ d appears to already be known. In fact, the
following is [10, Exercise 13.6(a)]: If $F$ is an $m$-accretive operator (also
known as a hyperaccretive operator) on a Banach space $X$ such that $\\{x\in
X:\|F(x)\|\leq\alpha\\}$ is bounded for all $\alpha$, then $F$ has dense
range. For any nonexpansive map $f:X\rightarrow X$, the map $\mathrm{id}-f$ is
$m$-accretive, so this exercise implies that a $\Rightarrow$ d. If $X$ has the
fixed point property, then a $\Rightarrow$ c is also known. In that case, if
$F$ is an $m$-accretive operator such that $\\{x\in X:\|F(x)\|\leq\alpha\\}$
is bounded for all $\alpha$, then [28, Theorem 6] implies that $F$ is
surjective.

######  Remark 3.9.

If $X$ is a Hilbert space and $f:X\rightarrow X$ is nonexpansive, then the
multivalued map $u\mapsto F_{0}(f+u)$ is maximally monotone. Since monotone
operators on a Hilbert space are locally bounded on the interior of their
domains [10, Theorem 23.2], this gives an alternative proof of the equivalence
of conditions b and c. This also implies that if $f$ has surjective
displacement, then the set of $u$ such that $F_{0}(f+u)$ is single-valued is a
dense $G_{\delta}$ subset of $X$ [10, Theorem 23.6].

In infinite dimensions, it is easy to construct nonexpansive maps with dense
displacement, but not surjective displacement.

######  Example 3.10.

Let $T:\ell_{2}(\mathbb{N})\rightarrow\ell_{2}(\mathbb{N})$ be the right shift
operator

$T(x_{1},x_{2},x_{3},\ldots)=(0,x_{1},x_{2},\ldots).$

If $e_{1}=(1,0,0,\ldots)$, then the map $T+e_{1}$ is an isometry with no fixed
points in $\ell_{2}(\mathbb{N})$. Thus $T$ does not have surjective
displacement. However, $\|T(x)-x\|^{2}=2\|x\|^{2}-2\left\langle
T(x),x\right\rangle>0$ for all nonzero $x\in\ell_{2}(\mathbb{N})$. Therefore,
$\left\langle T(tx)-tx,x\right\rangle=t\left\langle
T(x)-x,x\right\rangle\rightarrow-\infty$ as $t\rightarrow\infty$ for all
nonzero $x$. This shows that $T$ has dense displacement by Theorem 3.7.

Condition a is sufficient for a nonexpansive map to have surjective
displacement, but the following example shows that it is not necessary in
infinite dimensions.

######  Example 3.11.

Let $X=\ell_{2}(\mathbb{N})$, let $\\{e_{k}\\}_{k\in\mathbb{N}}$ denote the
standard basis for $\ell_{2}(\mathbb{N})$, and let $f:X\rightarrow X$ be the
map defined entrywise by

$f_{j}(x)=\begin{cases}\tfrac{j}{j+1}(x_{j}+1)&\text{if }x_{j}<-1\\\
0&\text{if }|x_{j}|\leq 1\\\ \tfrac{j}{j+1}(x_{j}-1)&\text{if
}x_{j}>1.\end{cases}$

Then $f$ is nonexpansive and $f-\mathrm{id}$ is onto. After all, for any $u\in
X$, $|u_{j}|\leq 1$ for all but finitely many $j\in\mathbb{N}$. Therefore, we
can choose $x\in X$ as follows:

$x_{j}=\begin{cases}-(j+1)u_{j}+j&\text{if }u_{j}>1\\\ -u_{j}&\text{if
}|u_{j}|\leq 1\\\ -(j+1)u_{j}-j&\text{if }u_{j}<-1,\end{cases}$

so that $f(x)-x=u$. On the other hand, observe that the approximate fixed
point set $F_{2}(f)$ contains $(k+2)e_{k}$ for all $k\in\mathbb{N}$. Therefore
$f$ has surjective displacement even though the approximate fixed point set
$F_{2}(f)$ is not bounded.

For linear nonexpansive maps, condition c implies condition a from Theorem
3.7.

######  Lemma 3.12.

Suppose $X$ is a real Banach space, $T:X\rightarrow X$ is linear and
nonexpansive, and $T$ has surjective displacement. Then all approximate fixed
point sets $F_{\delta}(T)$ are bounded.

###### Proof.

For any nonzero $x\in X$,

$\lim_{t\rightarrow\infty}\left\langle
T(tx)-tx,x^{*}\right\rangle=\lim_{t\rightarrow\infty}t\left\langle
T(x)-x,x^{*}\right\rangle=-\infty$

for some $x^{*}\in J(x)$ by Theorem 3.7. Therefore $T(x)-x\neq 0$ and so the
kernel of $T-\mathrm{id}$ is $\\{0\\}$. This means that $T-\mathrm{id}$ is
one-to-one and onto, so it is invertible with a bounded inverse. Then
$F_{\delta}(T)=(T-\mathrm{id})^{-1}B_{\delta}$, so $F_{\delta}(T)$ is bounded
for all $\delta\geq 0$. ∎

An interesting corollary of Theorem 3.7 is the following.

######  Corollary 3.13.

Let $X$ be a real Banach space and suppose that $f$ and $g$ are both
nonexpansive maps on $X$. If $X$ is uniformly smooth and $f$ has dense
displacement, then $cf+(1-c)g$ is a nonexpansive map with dense displacement
for all $0<c<1$. If $f$ has surjective displacement and $X$ is finite
dimensional with either a smooth or polyhedral norm, then $cf+(1-c)g$ is a
nonexpansive map with surjective displacement for all $0<c<1$.

###### Proof.

It is easy to verify that $cf+(1-c)g$ is nonexpansive for all $0<c<1$. By
Lemma 3.2,

$\lim_{t\rightarrow\infty}\left\langle
cf(tx)+(1-c)g(tx)-tx,x^{*}\right\rangle$

exists and is contained in $[-\infty,\infty)$ for all $x\in X$ with $\|x\|=1$
and $x^{*}\in J(x)$. Suppose $f$ has dense displacement. Then $f$ satisfies
condition e of Theorem 3.7 and so must $cf+(1-c)g$ for all $0<c<1$. Then if
$X$ is uniformly smooth, it follows that from Theorem 3.7 that $cf+(1-c)g$ has
dense displacement. If $X$ is finite dimensional and smooth or $X$ has a
polyhedral norm, then Theorem 3.7 implies that $cf+(1-c)g$ has surjective
displacement. ∎

Some of the implications from Theorem 3.7 may not be best possible. It is not
clear whether condition a implies surjective displacement on Banach spaces
without the fixed point property or whether condition e implies surjective
displacement on every finite dimensional real Banach space. We also don’t know
whether conditions b and c are equivalent on Banach spaces that are not
Hilbert spaces.

##  4\. Polyhedral norm nonexpansive maps

The following theorem gives a computational procedure involving a finite
number of limits that determine whether or not a nonexpansive map on a space
with a polyhedral norm has surjective displacement.

######  Theorem 4.1.

Let $X$ be a finite dimensional real Banach space with a polyhedral norm and
suppose that $f:X\rightarrow X$ is nonexpansive. For every face $F$ of the
unit ball $B_{1}$, choose an $x_{F}$ in the relative interior of $F$ and an
$x_{F}^{*}$ in the relative interior of the corresponding dual face $F^{*}$ of
$B_{1}^{*}$. Then $f-\mathrm{id}$ maps onto $X$ if and only if

(4.1) $lim_{t\rightarrow\infty}\left\langle
f(tx_{F})-tx_{F},x_{F}^{*}\right\rangle=-\infty$

for every proper face $F$.

Of course, Theorem 4.1 is only useful as a test for the existence of fixed
points if it is possible to calculate the limits in (4.1). However, given an
explicit expression for $f$, this is frequently the case. Before proving the
theorem, we make the following general observation.

######  Lemma 4.2.

Let $X$ be a real Banach space, let $x,y\in X$ with $\|x\|=\|y\|=1$, and
suppose that $J(x)\subseteq J(y)$. Then for any $x^{*}\in J(x)$,

$\lim_{t\rightarrow\infty}\left\langle
f(tx)-tx,x^{*}\right\rangle\leq\lim_{t\rightarrow\infty}\left\langle
f(ty)-ty,x^{*}\right\rangle.$

In particular, if $J(x)=J(y)$, then the two limits are equal.

###### Proof.

By Lemma 3.3, for any $s>0$ there is a $z^{*}\in J(x)$ such that

$\displaystyle 0$ $\displaystyle=\lim_{t\rightarrow\infty}\|tx-
sy\|-\left\langle tx-sy,z^{*}\right\rangle$
$\displaystyle=\lim_{t\rightarrow\infty}\|tx-sy\|-t+s$
$\displaystyle\text{(since }z^{*}\in J(x)\subseteq J(y))$
$\displaystyle\geq\limsup_{t\rightarrow\infty}\|f(tx)-f(sy)\|-t+s$
$\displaystyle(\text{nonexpansiveness})$
$\displaystyle\geq\limsup_{t\rightarrow\infty}\left\langle
f(tx)-f(sy),x^{*}\right\rangle-t+s$ $\displaystyle(\text{since
}\|x^{*}\|_{*}=1)$ $\displaystyle=\lim_{t\rightarrow\infty}\langle
f(tx)-tx,x^{*}\rangle-\left\langle f(sy)-sy,x^{*}\right\rangle.$

We have shown that $\left\langle
f(sy)-sy,x^{*}\right\rangle\geq\lim_{t\rightarrow\infty}\langle
f(tx)-tx,x^{*}\rangle$ for all $s>0$. The conclusion follows by letting
$s\rightarrow\infty$. ∎

###### Proof of Theorem 4.1.

Choose any proper face $F$ of $B_{1}$. If $f-\mathrm{id}$ maps onto $X$, then
Theorem 3.7 implies that $\lim_{t\rightarrow\infty}\left\langle
f(tx_{F})-tx_{F},x^{*}\right\rangle=-\infty$ for at least one $x^{*}\in
F^{*}$. Any $x_{F}^{*}$ in the relative interior of $F^{*}$ can be expressed
as a non-trivial convex combination of $x^{*}$ with some other $y^{*}\in
F^{*}$, that is, $x_{F}^{*}=cx^{*}+(1-c)y^{*}$ where $0<c<1$. Since the
$\lim_{t\rightarrow\infty}\left\langle
f(tx_{F})-tx_{F},y^{*}\right\rangle<\infty$ by Lemma 3.2, it follows that
$\lim_{t\rightarrow\infty}\left\langle
f(tx_{F})-tx_{F},x_{F}^{*}\right\rangle=-\infty$. This proves that the
condition given by (4.1) is necessary in order for $f-\mathrm{id}$ to map onto
$X$.

Now, suppose that (4.1) holds for one $x_{F}\in\operatorname{ri}F$. For any
other $y_{F}\in\operatorname{ri}F$, $J(x_{F})=J(y_{F})$. Then by Lemma 4.2

$\lim_{t\rightarrow\infty}\left\langle
f(ty_{F})-ty_{F},x_{F}^{*}\right\rangle=\lim_{t\rightarrow\infty}\left\langle
f(tx_{F})-tx_{F},x_{F}^{*}\right\rangle=-\infty$

for all $y_{F}\in\operatorname{ri}F$. Therefore confirming (4.1) for one
representative $x_{F}$ in the relative interior of each proper face $F$ is
sufficient to confirm it for all $y_{F}\in\operatorname{ri}F$. Since every
$x\in X$ with $\|x\|=1$ is contained in the relative interior of some face
$F$, verifying (4.1) for every face $F$ will establish condition e in Theorem
3.7. That is sufficient to show that $f$ has surjective displacement. ∎

One might wonder if checking (4.1) for a subset of the faces of $B_{1}$ might
be sufficient to prove that (4.1) holds for all proper faces? For the supremum
norm on $\mathbb{R}^{n}$, this is not the case. The following example shows
that for any proper face $F$ of the unit ball in
$(\mathbb{R}^{n},\|\cdot\|_{\infty})$, there is an $\ell_{\infty}$
nonexpansive map such that (4.1) holds for every face except $F$.

######  Example 4.3.

Let $X=\mathbb{R}^{n}$ with the supremum norm $\|x\|_{\infty}$. Let
$N=\\{1,\ldots,n\\}$. For any subset $I\subseteq N$, let $e_{I}$ be the vector
in $\mathbb{R}^{n}$ defined by

$(e_{I})_{i}=\begin{cases}1&\text{if }i\in I\\\
0&\text{otherwise.}\end{cases}$

The faces of the unit ball in $X$ are the sets

$F_{IJ}=\\{x\in B_{1}:x_{i}=1\text{ if }i\in I,x_{i}=-1\text{ if }i\in J\\}$

where $I$ and $J$ are disjoint subsets of $N$. Note that $F_{IJ}$ is a proper
face if at least one of the sets $I,J$ is nonempty. The corresponding dual
faces are

$F_{IJ}^{*}=\\{x\in B_{1}^{*}:\sum_{i\in I}x_{i}-\sum_{j\in J}x_{j}=1\\}.$

For each face $F_{IJ}$, let $x_{IJ}=e_{I}-e_{J}$ and
$x_{IJ}^{*}=\tfrac{1}{|I|+|J|}(e_{I}-e_{J})$. Observe that
$x_{IJ}\in\operatorname{ri}(F_{IJ})$ and
$x_{IJ}^{*}\in\operatorname{ri}(F_{IJ}^{*})$.

In order to apply Theorem 4.1 to a nonexpansive map $f$ on $X$, we must check
whether

$\lim_{t\rightarrow\infty}\left\langle
f(tx_{IJ})-tx_{IJ},x_{IJ}^{*}\right\rangle=-\infty$

for every disjoint pair $I,J\subseteq N$ with $I\cup J\neq\varnothing$.

Fix disjoint sets $K,L\subset N$ such that $K\cup L$ is nonempty. Let
$P_{KL}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be the map

$P_{KL}(x)_{i}=\begin{cases}\max\\{x_{i},0\\}&\text{if }i\in K\cup L\\\
0&\text{otherwise.}\end{cases}$

Let $D_{L}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be the transformation

$D_{L}(x)_{i}=\begin{cases}-x_{i}&\text{if }i\in L\\\
x_{i}&\text{otherwise.}\end{cases}$

Finally, let $\sigma$ be a permutation of $N$ that is a cyclic permutation of
the elements of $K\cup L$ and let $S:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$
be the permutation operator corresponding to $\sigma$, that is
$S(x)_{i}=x_{\sigma(i)}$.

Each of the maps $P_{KL}$, $D_{L}$, and $S$ are nonexpansive on $X$, and
therefore so is the composition $f=D_{L}\circ S\circ P_{KL}\circ D_{L}$.
Observe that $tx_{KL}$ is a fixed point of $f$ for all $t>0$. Therefore $f$
cannot have surjective displacement. But every one of the limits (4.1) holds,
except for the one corresponding to the face $F_{KL}$.

When $\|\cdot\|$ is either the $\ell_{1}$ or the $\ell_{\infty}$ norm on
$\mathbb{R}^{n}$, the condition of Theorem 4.1 involves checking $3^{n}-1$
limit inequalities. Interestingly, according to Kalai’s $3^{d}$ conjecture
[18, 30], any centrally symmetric $n$-dimensional polytope should have at
least $3^{n}$ nonempty faces. Thus the number of limits needed to check the
conditions of Theorem 4.1 for other polyhedral norms on $\mathbb{R}^{n}$
should always be at least $3^{n}-1$.

Unfortunately, there is no way to show that an $\ell_{2}$-nonexpansive map on
$\mathbb{R}^{n}$ has surjective displacement using a finite set of limits of
the type in Theorem 4.1. To see why, let $f$ be an orthogonal projection onto
a one-dimensional subspace spanned by $v\in\mathbb{R}^{n}$ with $\|v\|_{2}=1$.
For any $x$ that is not a scalar multiple of $v$ (that is, almost every $x$),
we have $|\left\langle x,v\right\rangle|<\|x\|_{2}$, so
$\lim_{t\rightarrow\infty}\left\langle f(tx)-tx,x\right\rangle=t(|\left\langle
x,v\right\rangle|^{2}-\|x\|_{2}^{2})\rightarrow-\infty$. This is despite the
fact that $f$ has an unbounded set of fixed points. In section 7, we will give
a computable sufficient condition for confirming surjective displacement when
$f$ is a nonexpansive map on a smooth finite dimensional normed space.

##  5\. Perron-Frobenius theory

Let $N=\\{1,\ldots,n\\}$. For any subset $I\subseteq N$, let $e_{I}$ be the
vector in $\mathbb{R}^{n}$ defined by

$(e_{I})_{i}=\begin{cases}1&\text{if }i\in I\\\
0&\text{otherwise.}\end{cases}$

We use $\geq$ to denote the natural partial ordering on $\mathbb{R}^{n}$:
$x\geq y$ if and only if $x_{i}\geq y_{i}$ for all $i\in N$. A map
$T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is _order-preserving_ if $T(x)\geq
T(y)$ whenever $x\geq y$. $T$ is _additively homogeneous_ if
$T(x+te_{N})=T(x)+te_{N}$ for all $x\in\mathbb{R}^{n}$ and $t\in\mathbb{R}$
and $T$ is _additively subhomogeneous_ if $T(x+te_{N})\leq T(x)+te_{N}$ for
all $x\in\mathbb{R}^{n}$ and $t\geq 0$.

If $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is order-preserving, then $T$
is nonexpansive with respect to the $\ell_{\infty}$-norm if and only if it is
additively subhomogeneous [22, Lemma 2.7.2]. Such maps are called
_subtopical_. Order-preserving maps on $\mathbb{R}^{n}$ that are additively
homogeneous are called _topical_.

###  5.1. Surjective displacement for subtopical maps

The following necessary and sufficient condition for a subtopical map to have
surjective displacement only requires computing $2(2^{n}-1)$ limits as opposed
to the $3^{n}-1$ limits needed by the condition in Theorem 4.1 for
$\ell_{\infty}$-nonexpansive maps that are not order-preserving.

######  Theorem 5.1.

Let $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be subtopical. Then $T$ has
surjective displacement if and only if for every nonempty $I\subseteq N$,

(5.1) $\lim_{t\rightarrow\infty}\left\langle
T(te_{I}),e_{I}\right\rangle-t|I|=-\infty\text{ and
}\lim_{t\rightarrow\infty}\left\langle
T(-te_{I}),e_{I}\right\rangle+t|I|=+\infty.$

###### Proof.

Since $T$ is subtopical, it is nonexpansive with respect to the supremum norm
$\|\cdot\|_{\infty}$. We use the notation from Example 4.3 for the faces
$F_{IJ}$, dual faces $F_{IJ}^{*}$ and representative points
$x_{IJ}\in\operatorname{ri}F_{IJ}$ and
$x_{IJ}^{*}\in\operatorname{ri}F_{IJ}^{*}$ of the unit ball $B_{1}$ in
$(\mathbb{R}^{n},\|\cdot\|_{\infty})$. By Theorem 4.1, $T$ has surjective
displacement if and only if

$\lim_{t\rightarrow\infty}\left\langle
T(tx_{IJ})-tx_{IJ},x_{IJ}^{*}\right\rangle=-\infty$

for every disjoint pair $I,J\subseteq N$ with $I\cup J\neq\varnothing$. Since
$x_{IJ}=(|I|+|J|)x_{IJ}^{*}$, the limit above is equivalent to

$\lim_{t\rightarrow\infty}\left\langle
T(tx_{IJ}),x_{IJ}\right\rangle-t(|I|+|J|)=-\infty.$

In order for $T$ to have surjective displacement, it is necessary that both
limits in (5.1) hold true, as those two limits correspond to the limit
condition above for $x_{I\varnothing}$ and $x_{\varnothing I}$. We will now
show that the limits in (5.1) are also sufficient for $T$ to have surjective
displacement.

Note that $-e_{J}\leq x_{IJ}\leq e_{I}$. Therefore $T(-te_{J})\leq
T(tx_{IJ})\leq T(te_{I})$ for all $t>0$. So

$\displaystyle\left\langle T(tx_{IJ}),x_{IJ}\right\rangle-t(|I|+|J|)$
$\displaystyle=\left\langle T(tx_{IJ}),e_{I}\right\rangle-t|I|-\left\langle
T(tx_{IJ}),e_{J}\right\rangle-t|J|$ $\displaystyle\leq\left\langle
T(te_{I}),e_{I}\right\rangle-t|I|-\left\langle
T(-te_{J}),e_{J}\right\rangle-t|J|$ $\displaystyle=\left(\left\langle
T(te_{I}),e_{I}\right\rangle-t|I|\right)-\left(\left\langle
T(-te_{J}),e_{J}\right\rangle+t|J|\right).$

If (5.1) holds for all nonempty $I$, then the inequality above implies that

$\lim_{t\rightarrow\infty}\left\langle
T(tx_{IJ}),x_{IJ}\right\rangle-t(|I|+|J|)=-\infty$

for all disjoint sets $I,J\subseteq N$ with $I\cup J\neq\varnothing$. Hence
$T$ has surjective displacement by Theorem 4.1. ∎

###  5.2. Existence of additive eigenvectors for topical maps

The results in this subsection are not new, but rather give alternative proofs
of some necessary and sufficient conditions from [3] for a topical map
$T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ to have the property that $T+u$
has an additive eigenvector for all $u\in\mathbb{R}^{n}$. The results in [3]
were proved using a game theoretic approach involving dominions of players in
certain one and two-player games. Here we will show how those results follow
from Theorem 4.1.

For $x\in\mathbb{R}^{n}$, let $\mathsf{t}(x)=\max_{i\in N}x_{i}$ and
$\mathsf{b}(x)=\min_{i\in N}x_{i}$. If
$T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is topical, then $T$ is
nonexpansive with respect to the variation seminorm
$\|x\|_{\text{var}}=\mathsf{t}(x)-\mathsf{b}(x)$ [12, Section 2.2]. Note that
$\|\cdot\|_{\text{var}}$ is not a norm on $\mathbb{R}^{n}$, but it is a norm
on the subspace $V_{0}=\\{x\in\mathbb{R}^{n}:\left\langle
x,e_{N}\right\rangle=0\\}$. The normalized map
$f(x)=T(x)-\tfrac{1}{n}\left\langle T(x),e_{N}\right\rangle e_{N}$ maps
$V_{0}$ into itself and is nonexpansive with respect to
$\|\cdot\|_{\text{var}}$. If $f$ has a fixed point $x$ in $V_{0}$, then $x$ is
an _additive eigenvector_ of $T$, that is, $T(x)=x+\lambda e_{N}$ for some
$\lambda\in\mathbb{R}$. In fact, $T+u$ has an additive eigenvector if and only
if $f+u_{0}$ with $u_{0}=u-\tfrac{1}{n}\left\langle u,e_{N}\right\rangle
e_{N}$ has a fixed point. Since the variation norm is a polyhedral norm on
$V_{0}$, Theorem 4.1 gives a testable necessary and sufficient condition to
see if $T+u$ has an additive eigenvector for every $u\in\mathbb{R}^{n}$. We
will see below that the condition ends up being equivalent to the one given in
[3, Theorem 4.2].

The proper faces of $B_{1}$ in $(V_{0},\|\cdot\|_{\text{var}})$ are the sets

$F_{IJ}=\\{x\in V_{0}\,:\,\|x\|_{\text{var}}=1,\,x_{i}=\mathsf{t}(x)\,\forall
i\in I,\,x_{j}=\mathsf{b}(x)\,\forall j\in J\\}$

where $I,J\subset N$ are nonempty and disjoint. The dual norm is
$\|x\|_{\text{var}}^{*}=\tfrac{1}{2}\sum_{i\in N}|x_{i}|$, and the faces of
the dual unit ball are

$F_{IJ}^{*}=\\{x\in V_{0}\,:\,\|x\|_{\text{var}}^{*}=1,\textstyle{\sum_{i\in
I}}x_{i}=1,\textstyle{\sum_{j\in J}}x_{j}=-1\\}.$

Note that if $x\in F_{IJ}^{*}$, then $x_{i}>0$ for all $i\in I$, $x_{i}<0$ for
$i\in J$ and $x_{i}=0$ for $i\in(I\cup J)^{c}$. Let
$x_{IJ}^{*}=\frac{1}{|I|}e_{I}-\frac{1}{|J|}e_{J}$, and let
$\delta=\|x_{IJ}^{*}\|_{\text{var}}=\left(\frac{1}{|I|}+\frac{1}{|J|}\right).$
By construction, $x_{IJ}^{*}\in\operatorname{ri}F_{IJ}^{*}$. If we let
$x_{IJ}=\tfrac{1}{\delta}x_{IJ}^{*}$, then $x_{IJ}\in\operatorname{ri}F_{IJ}$.

######  Lemma 5.2.

Let $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be topical. Let
$f:V_{0}\rightarrow V_{0}$ be the corresponding normalized map
$f(x)=T(x)-\tfrac{1}{n}\left\langle T(x),e_{N}\right\rangle e_{N}$. Let $I,J$
be disjoint, nonempty subsets of $N$. Then

(5.2) $\lim_{t\rightarrow\infty}\left\langle
f(tx_{IJ})-tx_{IJ},x_{IJ}^{*}\right\rangle=-\infty$

if and only if

(5.3) $\lim_{t\rightarrow\infty}\left\langle
T(-te_{I^{c}}),e_{I}\right\rangle=-\infty\text{ or
}\lim_{t\rightarrow\infty}\left\langle
T(te_{J^{c}}),e_{J}\right\rangle=\infty.$

###### Proof.

Start by observing that

$-\tfrac{1}{\delta|J|}e_{J}\leq x_{IJ}\leq\tfrac{1}{\delta|I|}e_{I}.$

This implies that

$-e_{I^{c}}\leq
x_{IJ}-\tfrac{1}{\delta|I|}e_{N}\leq-\tfrac{1}{\delta|I|}e_{I^{c}}$

and

$\tfrac{1}{\delta|J|}e_{J^{c}}\leq x_{IJ}+\tfrac{1}{\delta|J|}e_{N}\leq
e_{J^{c}}.$

Also,

$\displaystyle\left\langle f(tx_{IJ})-tx_{IJ},x_{IJ}^{*}\right\rangle$
$\displaystyle=\left\langle T(tx_{IJ}),x_{IJ}^{*}\right\rangle-t$
$\displaystyle=\tfrac{1}{|I|}\left\langle
T(tx_{IJ}),e_{I}\right\rangle-\tfrac{1}{|J|}\left\langle
T(tx_{IJ}),e_{J}\right\rangle-t$ $\displaystyle=\tfrac{1}{|I|}\left\langle
T(tx_{IJ}-\tfrac{1}{\delta|I|}e_{N}),e_{I}\right\rangle-\tfrac{1}{|J|}\left\langle
T(tx_{IJ}+\tfrac{1}{\delta|J|}e_{N}),e_{J}\right\rangle.$

Combining these facts, we see that

(5.4) $\left\langle
f(tx_{IJ})-tx_{IJ},x_{IJ}^{*}\right\rangle\geq\tfrac{1}{|I|}\left\langle
T(-te_{I^{c}}),e_{I}\right\rangle-\tfrac{1}{|J|}\left\langle
T(te_{J^{c}}),e_{J}\right\rangle$

and

(5.5) $\left\langle
f(tx_{IJ})-tx_{IJ},x_{IJ}^{*}\right\rangle\leq\tfrac{1}{|I|}\left\langle
T(-\tfrac{t}{\delta|I|}e_{I^{c}}),e_{I}\right\rangle-\tfrac{1}{|J|}\left\langle
T(\tfrac{t}{\delta|J|}e_{J^{c}}),e_{J}\right\rangle.$

As $T$ is order-preserving, both $\left\langle
T(-te_{I^{c}}),e_{I}\right\rangle$ and $\left\langle
T(te_{J^{c}}),e_{J}\right\rangle$ are monotone functions of $t$. So both
$\lim_{t\rightarrow\infty}\left\langle T(-te_{I^{c}}),e_{I}\right\rangle$ and
$\lim_{t\rightarrow\infty}\left\langle T(te_{J^{c}}),e_{J}\right\rangle$
exist. From this and the last two inequalities, the conclusion follows. ∎

The next theorem is equivalent to [3, Theorem 4.2].

######  Theorem 5.3.

Let $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be topical. Then $T+u$ has an
additive eigenvector for all $u\in\mathbb{R}^{n}$ if and only if for every
pair of nonempty, disjoint sets $I,J\subset N$ either

$\lim_{t\rightarrow\infty}\left\langle
T(-te_{I^{c}}),e_{I}\right\rangle=-\infty\text{ or
}\lim_{t\rightarrow\infty}\left\langle
T(te_{J^{c}}),e_{J}\right\rangle=+\infty.$

###### Proof.

The functions $T+u$ have an additive eigenvector for every
$u\in\mathbb{R}^{n}$ if and only if the corresponding normalized map
$f:V_{0}\rightarrow V_{0}$ defined by $f(x)=T(x)-\tfrac{1}{n}\left\langle
T(x),e_{N}\right\rangle e_{N}$ has surjective displacement. By Theorem 4.1,
this happens if and only if (5.2) holds for every disjoint pair of nonempty
subsets $I,J\subset N$. This, in turn, is equivalent to (5.3) holding for each
pair $I,J$ by Lemma 5.2. ∎

The condition of Theorem 5.3 only requires computing $2(2^{n}-1)$ limits,
however one also needs to check that for each nonempty, disjoint pair
$I,J\subset N$, one of the limits in (5.3) is infinite. There are almost
$3^{n}$ such pairs. However, a combinatorial approach using hypergraphs
reduces the number of computations necessary to check the conditions above to
$O(2^{n}n^{2})$. We’ll give a short explanation of the idea here, for more
details see [3, Section 4.2.3].

A _directed hypergraph_ consists of a set of nodes $N$ and a collection of
directed hyperarcs. A _hyperarc_ is an ordered pair $(\mathbf{t},\mathbf{h})$
where $\mathbf{t},\mathbf{h}\subseteq N$. Following [3], we introduce two
directed hypergraphs $\mathcal{H}^{+}_{\infty}(T)$ and
$\mathcal{H}^{-}_{\infty}(T)$ both of which have nodes $N=\\{1,\ldots,n\\}$.
The hyperarcs of $\mathcal{H}^{+}_{\infty}(T)$ are the pairs $(J,\\{i\\})$
with $i\notin J$ such that

$\lim_{t\rightarrow\infty}T_{i}(te_{J})=+\infty.$

The hyperarcs of $\mathcal{H}^{-}_{\infty}(T)$ are $(J,\\{i\\})$ with $i\notin
J$ such that

$\lim_{t\rightarrow\infty}T_{i}(-te_{J})=-\infty.$

Let $\mathcal{H}$ be any directed hypergraph with nodes $N$. For $I\subseteq
N$, we say that $I$ is _invariant_ in $\mathcal{H}$ if there are no hyperarcs
from a subset of $I$ to a subset of $I^{c}$. Since $T$ is order-preserving, if
$I$ is not invariant in $\mathcal{H}^{-}_{\infty}(T)$ or
$\mathcal{H}^{+}_{\infty}(T)$, then there must be a $j\in I^{c}$ such that
$(I,\\{j\\})$ is a hyperarc in the hypergraph. Note that
$\lim_{t\rightarrow\infty}\left\langle
T(-te_{I^{c}}),e_{I}\right\rangle=-\infty$ if and only if $I^{c}$ is not
invariant in $\mathcal{H}^{-}_{\infty}(T)$ and
$\lim_{t\rightarrow\infty}\left\langle
T(te_{J^{c}}),e_{J}\right\rangle=\infty$ if and only if $J^{c}$ is not
invariant in $\mathcal{H}^{+}_{\infty}(T)$.

The _reach_ of $I$ in a hypergraph $\mathcal{H}$ is the smallest invariant
subset of $N$ that contains $I$. Using the notion of reach, we can give an
improved version of Theorem 5.3. This next result is described in the comments
preceding [3, Theorem 4.6].

######  Theorem 5.4.

Let $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be topical. Then $T+u$ has an
additive eigenvector for all $u\in\mathbb{R}^{n}$ if and only if for every
nonempty proper subset $J\subset N$ either

$\lim_{t\rightarrow\infty}\left\langle
T(te_{J^{c}}),e_{J}\right\rangle=+\infty\text{ or
}\operatorname{reach}(J,\mathcal{H}^{-}_{\infty}(T))=N.$

###### Proof.

If $\lim_{t\rightarrow\infty}\left\langle T(te_{J^{c}}),e_{J}\right\rangle$ is
finite for some nonempty proper subset $J\subset N$ and if
$I=N\backslash\operatorname{reach}(J,\mathcal{H}^{-}_{\infty}(T))$ is
nonempty, then $I^{c}=\operatorname{reach}(J,\mathcal{H}^{-}_{\infty}(T))$ is
invariant in $\mathcal{H}^{-}_{\infty}(T)$ so
$\lim_{t\rightarrow\infty}\left\langle
T(-te_{I^{c}}),e_{I}\right\rangle>-\infty$. Therefore Theorem 5.3 implies that
$T+u$ does not have an additive eigenvector for all $u\in\mathbb{R}^{n}$. On
the other hand, if $\operatorname{reach}(J,\mathcal{H}^{-}_{\infty}(T))=N$,
then for any nonempty $I$ disjoint from $J$, we have $J\subseteq I^{c}$, so
$\operatorname{reach}(I^{c},\mathcal{H}^{-}_{\infty}(T))=N$. This means that
$I^{c}$ is not invariant in $\mathcal{H}^{-}_{\infty}(T)$, so
$\lim_{t\rightarrow\infty}\left\langle
T(-te_{I^{c}}),e_{I}\right\rangle=-\infty$ for all nonempty $I$ disjoint from
$J$. Then Theorem 5.3 implies that $T+u$ has an additive eigenvector for all
$u\in\mathbb{R}^{n}$. ∎

Since the reach of a set in $\mathcal{H}^{-}_{\infty}(T)$ can be computed
relatively quickly (see [3, Lemma 4.5]), the condition in Theorem 5.4 can be
checked in $O(2^{n}n^{2})$ computations including limits as a single
computation. See [3, Theorem 4.6] for details.

Although we chose to state Theorem 5.4 using the hypergraph
$\mathcal{H}^{-}_{\infty}(T)$, the following dual result is also true. $T+u$
has additive eigenvector for all $u\in\mathbb{R}^{n}$ if and only if for every
nonempty proper subset $I\subset N$ either

$\lim_{t\rightarrow\infty}\left\langle
T(-te_{I^{c}}),e_{I}\right\rangle=-\infty\text{ or
}\operatorname{reach}(I,\mathcal{H}^{+}_{\infty}(T))=N.$

The proof is essentially the same. It turns out that working with the
hypergraph $\mathcal{H}^{-}_{\infty}(T)$, as in Theorem 5.4, is more
convenient for convex topical maps.

####  5.2.1. Convex topical maps

If $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is convex in addition to being
topical, then we can determine whether or not $T+u$ has an additive
eigenvector for all $u\in\mathbb{R}^{n}$ much more quickly. Let
$\mathcal{G}_{\infty}(T)$ be the directed graph with nodes $N$ and an arc from
$i$ to $j$ if $\lim_{t\rightarrow\infty}T_{i}(te_{\\{j\\}})=\infty$. Note that
the arcs in $\mathcal{G}_{\infty}(T)$ point in the opposite direction of the
corresponding hyperarcs in $\mathcal{H}^{+}_{\infty}(T)$. The graph
$\mathcal{G}_{\infty}(T)$ was introduced in [12] and used in [3] to prove the
following theorem. Recall that the nodes of a directed graph can be
partitioned into their strongly connected components, and a strongly connected
component is called a _final class_ if there are no arcs from that component
to any other.

######  Theorem 5.5 ([3, Corollary 4.4]).

Let $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be convex and topical. Then
$T+u$ has an additive eigenvector for every $u\in\mathbb{R}^{n}$ if and only
if $\mathcal{G}_{\infty}(T)$ has a unique final class $C$ and
$\operatorname{reach}(C,\mathcal{H}^{-}_{\infty}(T))=N$.

Because the strongly connected components of $\mathcal{G}_{\infty}(T)$ can be
computed in $O(n^{2})$ time and
$\operatorname{reach}(C,\mathcal{H}^{-}_{\infty}(T))$ can also be computed in
$O(n^{2})$ [3, Lemma 4.5], the conditions in Theorem 5.5 are much faster to
check than the conditions of Theorems 5.3/5.4 when $n$ is large. See [3,
Corollary 4.7]. The graph $\mathcal{G}_{\infty}(T)$ also leads to the
following (already known) generalization of [12, Theorem 2].

######  Theorem 5.6.

Let $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be topical. If
$\mathcal{G}_{\infty}(T)$ is strongly connected, then $T+u$ has an additive
eigenvector for every $u\in\mathbb{R}^{n}$.

We will prove both Theorem 5.5 and Theorem 5.6 using the following lemma which
relates the graph $\mathcal{G}_{\infty}(T)$ with the hypergraphs
$\mathcal{H}^{+}_{\infty}(T)$ and $\mathcal{H}^{-}_{\infty}(T)$.

######  Lemma 5.7.

Let $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be topical. If $I\subset N$ is
invariant in $\mathcal{H}^{+}_{\infty}(T)$, then $I^{c}$ is invariant in
$\mathcal{G}_{\infty}(T)$. If $T$ is also convex, then for any $J\subset N$
that is invariant in $\mathcal{G}_{\infty}(T)$, $J^{c}$ is invariant in both
$\mathcal{H}^{+}_{\infty}(T)$ and $\mathcal{H}^{-}_{\infty}(T)$.

###### Proof.

If $I\subset N$ is invariant in $\mathcal{H}^{+}_{\infty}(T)$, then
$\lim_{t\rightarrow\infty}\left\langle
T(te_{I}),e_{I^{c}}\right\rangle<\infty$. Since $T$ is order-preserving,

$\lim_{t\rightarrow\infty}T_{j}(te_{\\{i\\}})\leq\lim_{t\rightarrow\infty}T_{j}(te_{I})<\infty$

for all $i\in I$ and $j\in I^{c}$. Therefore $I^{c}$ is invariant in
$\mathcal{G}_{\infty}(T)$.

Now suppose that $T$ is convex and $J\subset N$ is invariant in
$\mathcal{G}_{\infty}(T)$. This means that
$\lim_{t\rightarrow\infty}T_{i}(te_{\\{j\\}})<\infty$ for all $i\in J$ and
$j\in J^{c}$. By the convexity of $T$,

$T_{i}\left(\tfrac{t}{|J^{c}|}e_{J^{c}}\right)\leq\tfrac{1}{|J^{c}|}\sum_{j\in
J^{c}}T_{i}(te_{\\{j\\}})$

therefore $\lim_{t\rightarrow\infty}T_{i}(te_{J^{c}})<\infty$ for all $i\in
J$. This proves that $J^{c}$ is invariant in $\mathcal{H}^{+}_{\infty}(T)$.

Since $T$ is additively homogeneous, $T_{i}(-te_{J^{c}})=T_{i}(te_{J})-t$ for
all $i\in N$. By convexity

$T_{i}(0)+\tfrac{1}{2}t=T_{i}\left(\tfrac{1}{2}te_{N}\right)\leq\tfrac{1}{2}(T_{i}(te_{J})+T_{i}(te_{J^{c}})).$

Rearranging and doubling the inequality above gives

$T_{i}(-te_{J^{c}})=T_{i}(te_{J})-t\geq 2T_{i}(0)-T_{i}(te_{J^{c}}).$

We have already shown that $\lim_{t\rightarrow\infty}T_{i}(te_{J^{c}})<\infty$
when $i\in J$. So we have
$\lim_{t\rightarrow\infty}T_{i}(-te_{J^{c}})>-\infty$ for all $i\in J$. Hence
$J^{c}$ is invariant in $\mathcal{H}^{-}_{\infty}(T)$. ∎

###### Proof of Theorem 5.5.

If $\mathcal{G}_{\infty}(T)$ has two different final classes $I$ and $J$, then
both $I$ and $J$ are invariant in $\mathcal{G}_{\infty}(T)$ so by Lemma 5.7
$I^{c}$ is invariant in $\mathcal{H}^{-}_{\infty}(T)$ and $J^{c}$ is invariant
in $\mathcal{H}^{+}_{\infty}(T)$. This means that

$\lim_{t\rightarrow\infty}\left\langle
T(te_{J^{c}}),e_{J}\right\rangle<\infty\text{ and
}\lim_{t\rightarrow\infty}\left\langle
T(-te_{I^{c}}),e_{I}\right\rangle>-\infty.$

So $T+u$ does not have an additive eigenvector for all $u\in\mathbb{R}^{n}$ by
Theorem 5.3.

Now suppose that $C$ is the unique final class of $\mathcal{G}_{\infty}(T)$.
Since $C$ is invariant in $\mathcal{G}_{\infty}(T)$, $C^{c}$ is invariant in
$\mathcal{H}^{+}_{\infty}(T)$ by Lemma 5.7. This means that

$\lim_{t\rightarrow\infty}\left\langle
T(te_{C^{c}}),e_{C}\right\rangle<\infty,$

so by Theorem 5.4 it is necessary that
$\operatorname{reach}(C,\mathcal{H}^{-}_{\infty}(T))=N$ in order for $T+u$ to
have an additive eigenvector for every $u\in\mathbb{R}^{n}$.

We will now show that $\operatorname{reach}(C,\mathcal{H}^{-}_{\infty}(T))=N$
is also sufficient. Let $J$ be any nonempty proper subset of $N$ such that
$\lim_{t\rightarrow\infty}\left\langle
T(te_{J^{c}}),e_{J}\right\rangle<\infty$, i.e., $J^{c}$ is invariant in
$\mathcal{H}^{+}_{\infty}(T)$. By Lemma 5.7, $J$ is invariant in
$\mathcal{G}_{\infty}(T)$. Any nonempty set that is invariant in
$\mathcal{G}_{\infty}(T)$ must contain $C$, so if
$\operatorname{reach}(C,\mathcal{H}^{-}_{\infty}(T))=N$, then
$\operatorname{reach}(J,\mathcal{H}^{-}_{\infty}(T))=N$ as well. Thus $T+u$
has an additive eigenvector for all $u\in\mathbb{R}^{n}$ by Theorem 5.4. ∎

###### Proof of Theorem 5.6.

If $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is topical and
$\mathcal{G}_{\infty}(T)$ is strongly connected, then Lemma 5.7 implies that
there are no nontrivial invariant subsets of $N$ in the hypergraph
$\mathcal{H}^{+}_{\infty}(T)$. Thus $\lim_{t\rightarrow\infty}\left\langle
T(te_{J^{c}}),e_{J}\right\rangle=\infty$ for all nonempty proper subsets
$J\subset N$, and therefore $T+u$ has an additive eigenvector for all
$u\in\mathbb{R}^{n}$ by Theorem 5.3. ∎

##  6\. Uniqueness of fixed points

In this section, we give necessary and sufficient conditions for the
uniqueness of fixed points of polyhedral norm nonexpansive maps.

######  Lemma 6.1.

Let $X$ be a finite dimensional real Banach space with a polyhedral norm and
suppose that $F$ is a proper face of the unit ball $B_{1}$. For any
$x\in\operatorname{ri}F$, there is a constant $c<1$ such that

$\|Rx-ry\|=R-r$

whenever $y\in F$ and $0\leq r\leq\frac{1}{2}(1-c)R$.

###### Proof.

Since $x,y\in F$, it follows that $\left\langle
x,\nu\right\rangle=\left\langle y,\nu\right\rangle=1$ for all $\nu$ in the
dual face $F^{*}$. Let $c=\max\\{\left\langle
x,\nu\right\rangle\,:\,\nu\in(\operatorname{ext}B_{1})\backslash F^{*}\\}$.
Since $x\in\operatorname{ri}F$, it follows that $c<1$. If $0\leq
r\leq\frac{1}{2}(1-c)R$, then $cR+r\leq R-r$. Observe that $\left\langle Rx-
ry,\nu\right\rangle=R-r$ if $\nu\in F^{*}$, and $\left\langle Rx-
ry,\nu\right\rangle\leq cR+r$ if $\nu\in\operatorname{ext}B_{1}^{*}$ and
$\nu\notin F^{*}$. Therefore $\|Rx-
ry\|=\max_{\nu\in\operatorname{ext}B_{1}^{*}}\left\langle Rx-
ry,\nu\right\rangle=R-r$. ∎

######  Theorem 6.2.

Let $X$ be a finite dimensional real Banach space with a polyhedral norm, let
$f:X\rightarrow X$ be nonexpansive, and suppose that $f(0)=0$. Then the
following are equivalent.

  1. (1)

$f$ has a nonzero fixed point $u\in X$.

  2. (2)

For some $R>0$, there is an $x$ contained in the relative interior of a proper
face $F_{R}$ of $B_{R}$ such that $f(x)\in F_{R}$.

  3. (3)

There is a proper face $G$ of the unit ball $B_{1}$ and an $\epsilon>0$ such
that $rG$ is invariant under $f$ for all $0\leq r\leq\epsilon$.

###### Proof.

(1) $\Rightarrow$ (2). If $u\neq 0$ is a fixed point of $f$, let $R=\|u\|$ and
let $F_{R}$ be the face of $B_{R}$ such that $u\in\operatorname{ri}F$. Then
$f(u)=u\in F_{R}$.

(2) $\Rightarrow$ (3). Suppose $x\in\operatorname{ri}F_{R}$ and $f(x)\in
F_{R}$. Let $G_{R}\subseteq F_{R}$ be the face of $B_{R}$ such that
$f(x)\in\operatorname{ri}G_{R}$. Let $F=\frac{1}{R}F_{R}$ and
$G=\frac{1}{R}G_{R}$ so that $F$ and $G$ are faces of the unit ball $B_{1}$.
Let $G^{*}$ be the dual face corresponding to $G$. Choose any $v\in G$. Since
$G\subseteq F$, we have $\|x-rv\|=R-r$ for all $r>0$ sufficiently small by
Lemma 6.1. Then $\|f(x)-f(rv)\|\leq R-r$ by nonexpansiveness. Observe that
$\left\langle f(x),\nu\right\rangle=\|f(x)\|=R$ for all $\nu\in G^{*}$. At the
same time, $\left\langle f(rv),\nu\right\rangle\leq\|f(rv)\|\leq r$ for all
$\nu\in G^{*}$. Therefore, for any $\nu\in G^{*}$ we have

$R-r\leq\left\langle
f(x)-f(rv),\nu\right\rangle\leq\|f(x)-f(rv)\|\leq\|x-rv\|=R-r.$

This proves that $\left\langle f(rv),\nu\right\rangle=r$ for all $\nu\in
G^{*}$ and therefore $f(rv)\in rG$. Since $v\in G$ was arbitrary, this proves
that $rG$ is invariant under $f$.

(3) $\Rightarrow$ (1). The faces of $B_{1}$ are compact and convex. Therefore,
if $rG$ is invariant for some $r>0$, then it contains a nonzero fixed point of
$f$ by the Brouwer fixed point theorem. ∎

######  Corollary 6.3.

Let $X$ be a finite dimensional real Banach space with a polyhedral norm, let
$f:X\rightarrow X$ be nonexpansive, and suppose $u\in X$ is a fixed point of
$f$. For each face $F$ of the unit ball $B_{1}$, choose
$x_{F}\in\operatorname{ri}F$ and $x_{F}^{*}\in\operatorname{ri}F^{*}$. Then
$u$ is the unique fixed point of $f$ if and only if

(6.1) $\left\langle f(u+tx_{F})-u-tx_{F},x_{F}^{*}\right\rangle<0$

for all $t>0$ and every face $F$ of $B_{1}$.

###### Proof.

We may assume without loss of generality that $u=0$ by replacing $f$ with the
map $x\mapsto f(u+x)-u$. Since $f$ is nonexpansive and $f(0)=0$, it follows
that $\|f(tx_{F})\|\leq t$ for all $t>0$. Therefore $\left\langle
f(tx_{F})-tx_{F},x_{F}^{*}\right\rangle\leq 0$. If (6.1) fails for any face
$F$ and $t>0$, then $\left\langle f(tx_{F}),x_{F}^{*}\right\rangle=t$. This
means that $f(tx_{F})\in tF$ and so $f$ has a nonzero fixed point by Theorem
6.2. Conversely, if (6.1) holds for every face $F$ and $t>0$, then none of the
faces $tF$ are invariant under $f$. Therefore Theorem 6.2 implies that $0$ is
the unique fixed point of $f$. ∎

Note that the functions $t\mapsto\left\langle
f(u+tx_{F})-u-tx_{F},x_{F}^{*}\right\rangle$ in (6.1) are monotone decreasing
by Lemma 3.2. Therefore it suffices to verify that

$\lim_{t\rightarrow 0^{+}}\operatorname{sign}(\left\langle
f(u+tx_{F})-u-tx_{F},x_{F}^{*}\right\rangle)=-1$

for each face $F$ in order to confirm that $u$ is the unique fixed point of
$f$.

For subtopical maps, we have the following criterion for a fixed point to be
unique.

######  Theorem 6.4.

Let $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be subtopical and suppose that
$u$ is a fixed point of $T$. Then $u$ is the unique fixed point of $T$ if and
only if for every nonempty $I\subseteq N$,

$\left\langle T(u+te_{I})-u,e_{I}\right\rangle-t|I|<0\text{ and }\left\langle
T(u-te_{I})-u,e_{I}\right\rangle+t|I|>0$

for all $t>0$.

###### Proof.

We can assume without loss of generality that $u=0$ by replacing $T$ with the
map $x\mapsto T(u+x)-u$ which is also subtopical. All subtopical maps are
nonexpansive with respect to the $\ell_{\infty}$ norm on $\mathbb{R}^{n}$. We
use the same notation as in Example 4.3 for the faces $F_{IJ}$ of the
$\ell_{\infty}$ unit ball $B_{1}$, as well as representative points
$x_{IJ}\in\operatorname{ri}F_{IJ}$ and
$x_{IJ}^{*}\in\operatorname{ri}F_{IJ}^{*}$. In the proof of Theorem 5.1, we
showed that

$\displaystyle(|I|+|J|)\langle T(tx_{IJ})$ $\displaystyle-
tx_{IJ},x_{IJ}^{*}\rangle=\left\langle
T(tx_{IJ}),x_{IJ}\right\rangle-t(|I|+|J|)$
$\displaystyle\leq\left(\left\langle
T(te_{I}),e_{I}\right\rangle-t|I|\right)-\left(\left\langle
T(-te_{J}),e_{J}\right\rangle+t|J|\right)$

for all disjoint $I,J\subset N$ with $I\cup J\neq\varnothing$. Therefore,
(6.1) holds for every face $F_{IJ}$ (including $F_{\varnothing I}$ and
$F_{I\varnothing}$) if and only if

$\left\langle T(te_{I}),e_{I}\right\rangle-t|I|<0\text{ and }\left\langle
T(-te_{I}),e_{I}\right\rangle+t|I|>0$

for all nonempty $I\subseteq N$ and $t>0$. ∎

We can also use the results of this section to give an alternative proof of
[3, Theorem 4.8]. Combining Corollary 6.3 with (5.4) and (5.5) we have the
following.

######  Theorem 6.5.

Let $T:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ be topical. Suppose that $u$
is an additive eigenvector of $T$. Then $u$ is the unique additive eigenvector
of $T$ up to an additive constant if and only if for every pair of nonempty
disjoint sets $I,J\subset N$, and all $t>0$, either

$\left\langle T(u-te_{I^{c}})-u,e_{I}\right\rangle<0\text{ or }\left\langle
T(u+te_{J^{c}})-u,e_{J}\right\rangle>0.$

As is the case with the condition in Theorem 5.3, determining whether an
additive eigenvector is unique can be done more quickly using a hypergraph
approach, particularly when $T$ is convex in addition to topical. See [3,
Subsection 4.3] and [1].

##  7\. Recession maps and semiderivatives

Let $X$ be a real Banach space and $f:X\rightarrow X$ be nonexpansive. If

$f_{\infty}(x)=\lim_{t\rightarrow\infty}t^{-1}f(tx)$

exists for all $x\in X$, then we call $f_{\infty}$ the _recession map_ for
$f$. Recession maps were introduced in [12] for topical functions, but the
same definition applies more broadly. Recession maps don’t always exist, but
when one does it can provide a sufficient condition for $f$ to have surjective
displacement. The following theorem is based on a similar result for topical
maps on $\mathbb{R}^{n}$ [12, Theorem 13]. Related infinite dimensional
results with additional compactness assumptions can be found in [17, Theorem
2.7] and [26, Theorem 12].

######  Theorem 7.1.

Let $X$ be a finite dimensional real Banach space and $f:X\rightarrow X$ be
nonexpansive. If the recession map $f_{\infty}$ exists and 0 is the only fixed
point of $f_{\infty}$, then $f$ has surjective displacement.

###### Proof.

For each $t>1$, let $g_{t}(x)=t^{-1}f(tx)-x$. Since $t^{-1}f(tx)$ is
nonexpansive, each of the functions $g_{t}$ is 2-Lipschitz. If $f_{\infty}$
exists, then the functions $g_{t}$ converge pointwise to
$f_{\infty}-\mathrm{id}$, and therefore they converge uniformly on the unit
sphere $\partial B_{1}$. If $0$ is the only fixed point of $f_{\infty}$, then
there must be an $\epsilon>0$ such that

$\inf_{x\in\partial B_{1}}\|f_{\infty}(x)-x\|=\epsilon.$

Then for $t$ sufficiently large,

$\inf_{x\in\partial B_{1}}\|t^{-1}f(tx)-x\|\geq\tfrac{1}{2}\epsilon,$

or equivalently,

$\|f(tx)-tx\|\geq\tfrac{1}{2}\epsilon t$

for all $x\in\partial B_{1}$. This means that the approximate fixed point sets
$F_{\delta}(f)$ are bounded for all $\delta>0$, which proves that
$f-\mathrm{id}$ is onto by Theorem 3.1. ∎

The condition in Theorem 7.1 is sufficient, but not necessary for $f$ to have
surjective displacement. For example, the $(\mathbb{R},|\cdot|)$-nonexpansive
function

$f(x)=\begin{cases}0&\text{if }x\leq 1\\\ x-\sqrt{x}&\text{ if
}x>1\end{cases}$

has surjective displacement even though $f_{\infty}(x)=x$ for all $x>0$.

Theorem 7.1 fails in infinite dimensions. For example, the right shift
operator on $\ell_{2}(\mathbb{N})$ from Example 3.10 is linear, so it is its
own recession map. Clearly, 0 is the only fixed point of the right shift
operator, and yet the right shift operator only has dense, not surjective,
displacement on $\ell_{2}(\mathbb{N})$. However, when $X$ is a uniformly
smooth and strictly convex Banach space, we can prove the following.

######  Theorem 7.2.

Let $X$ be a real Banach space that is uniformly smooth and strictly convex.
Suppose that $f:X\rightarrow X$ is nonexpansive and the recession map
$f_{\infty}$ exists for $f$. If 0 is the unique fixed point of $f_{\infty}$,
then $f$ has dense displacement.

###### Proof.

Choose any $x\in X$ with $\|x\|=1$. Since $X$ is uniformly smooth, $J(x)$
contains a single element, $x^{*}$. Since $X$ is strictly convex, $x$ is the
only element in $B_{1}$ with $\left\langle x,x^{*}\right\rangle=1$. Therefore,
$\left\langle f_{\infty}(x),x^{*}\right\rangle<\left\langle
x,x^{*}\right\rangle$. This means that

$\lim_{t\rightarrow\infty}t^{-1}\left\langle f(tx)-tx,x^{*}\right\rangle<0$

so

$\lim_{t\rightarrow\infty}\left\langle f(tx)-tx,x^{*}\right\rangle=-\infty,$

which proves that $f$ has dense displacement by Theorem 3.7. ∎

Another simple observation about recession maps is that they are composable.

######  Lemma 7.3.

If $X$ is a real Banach space and $f,g:X\rightarrow X$ are nonexpansive maps
that have recession maps $f_{\infty}$ and $g_{\infty}$ respectively, then the
recession map for $f\circ g$ is $f_{\infty}\circ g_{\infty}$.

###### Proof.

Let $f_{t}(x)=t^{-1}f(tx)$ and $g_{t}(x)=t^{-1}g(tx)$. Note that $f_{t}$ is
nonexpansive for all $t>0$. Therefore

$\displaystyle\|t^{-1}f(g(tx))$ $\displaystyle-
f_{\infty}(g_{\infty}(x))\|=\|f_{t}(g_{t}(x))-f_{\infty}(g_{\infty}(x))\|$
$\displaystyle\leq\|f_{t}(g_{t}(x))-f_{t}(g_{\infty}(x))\|+\|f_{t}(g_{\infty}(x))-f_{\infty}(g_{\infty}(x))\|$
$\displaystyle\leq\|g_{t}(x)-g_{\infty}(x)\|+\|f_{t}(g_{\infty}(x))-f_{\infty}(g_{\infty}(x))\|.$

Since both $\|g_{t}(x)-g_{\infty}(x)\|$ and
$\|f_{t}(g_{\infty}(x))-f_{\infty}(g_{\infty}(x))\|$ approach $0$ as
$t\rightarrow\infty$, we conclude that $f_{\infty}\circ g_{\infty}$ is the
recession map for $f\circ g$. ∎

Just like recession maps provide a sufficient condition for surjective
displacement, the semiderivative of a nonexpansive map can give a sufficient
condition to check uniqueness of fixed points. Nonexpansive maps aren’t always
differentiable. When they aren’t, it is sometimes possible to define a
semiderivative as follows. Let $X$ be a real Banach space, and $f:X\rightarrow
X$ be a function. For any $u\in X$, the _semiderivative_ of $f$ at $u$ is the
function $f^{\prime}_{u}:X\rightarrow X$ given by

$f^{\prime}_{u}(x)=\lim_{t\rightarrow 0^{+}}\frac{f(u+tx)-f(u)}{t},$

assuming those limits exist for all $x\in X$. Semiderivatives are similar to
recession functions. For example, if $0$ is a fixed point of $f$, then the
semiderivative $f^{\prime}_{0}$ and the recession function $f_{\infty}$ are
both limits of the expression $t^{-1}f(tx)$, one as $t\rightarrow 0^{+}$, the
other as $t\rightarrow\infty$. When a semiderivative exists at a fixed point,
it can be used to check if the fixed point is unique. The following is a
special case of [4, Theorem 6.1].

######  Theorem 7.4.

Suppose that $X$ is a finite dimensional real Banach space, $f:X\rightarrow X$
is nonexpansive, and $u\in X$ is fixed point of $f$. If the semiderivative
$f^{\prime}_{u}$ exists and 0 is the unique fixed point of $f^{\prime}_{u}$,
then $u$ is the unique fixed point of $f$.

Note that semiderivatives are composable. In fact, they obey the chain rule.
If $f,g$ are nonexpansive maps on a Banach space $X$ and if $g$ is
semidifferentiable at $u$ and $f$ is semidifferentiable at $g(u)$, then
$(f\circ g)^{\prime}_{u}=f_{g(u)}^{\prime}\circ g_{u}^{\prime}$ (see [4, Lemma
3.4]).

###  7.1. Homogeneous nonexpansive maps

If $f$ is nonexpansive, then both the recession function $f_{\infty}$ and all
semiderivatives $f^{\prime}_{u}$ are nonexpansive, assuming they exist. They
are also _homogeneous_ , that is, $f_{\infty}(cx)=cf_{\infty}(x)$ and
$f^{\prime}_{u}(cx)=cf^{\prime}_{u}(x)$ for all $c>0$ and $x\in X$.
Homogeneous nonexpansive maps have some interesting properties that are worth
mentioning here. As motivation, note that all of the theorems so far in this
section involve determining whether 0 is the unique fixed point of a
homogeneous nonexpansive map.

Let $g:X\rightarrow X$ be homogeneous and nonexpansive. By continuity, $0$
must be a fixed point of $g$. When $X$ is finite dimensional, Theorem 7.1
implies that 0 is the only fixed point of $g$ if and only if $g$ has
surjective displacement since $g$ is its own recession map. On the other hand,
if $0$ is not the only fixed point of $g$, then there is a nonzero $u\in X$
such that $tu$ is a fixed point for all $t>0$. Therefore determining whether
$0$ is the unique fixed point of a homogeneous nonexpansive map is equivalent
to determining whether the fixed point set is bounded. For many finite
dimensional real Banach spaces, this question can be answered using a non-
deterministic algorithm proposed in [21]. We will give a brief description of
the idea here.

We say that a vector $v\in X$ _illuminates_ a point $w$ on the boundary of the
unit ball if $\|w+\epsilon v\|<1$ for all sufficiently small $\epsilon>0$.
Combining [21, Theorem 3.4 and Corollary 4.5] with the observation above, we
have the following result.

######  Proposition 7.5.

Let $X$ be a finite dimensional real Banach space and $g:X\rightarrow X$ be
homogeneous and nonexpansive. Then 0 is the unique fixed point of $g$ if and
only if there are points $w_{1},\ldots,w_{m}\in X$ such that every extreme
point of $B_{1}$ is illuminated by $g(w_{i})-w_{i}$ for some $i$. If $X$ is
smooth, then this happens if and only if $0$ is in the interior of the convex
hull of $\\{g(w_{i})-w_{i}:1\leq i\leq m\\}$.

This proposition leads immediately to a simple algorithm to check whether $0$
is the unique fixed point of $g$. Randomly choose $w_{i}\in X$ and calculate
$g(w_{i})-w_{i}$. Repeat until the set $\\{g(w_{i})-w_{i}\\}$ is sufficient to
illuminate every extreme point of the unit ball. If this process eventually
stops, then $0$ is the unique fixed point. For an $n$-dimensional space with a
smooth norm, it only requires $n+1$ vectors to illuminate every extreme point
on the unit ball since a set of vectors $\\{v_{1},\ldots,v_{m}\\}$ illuminates
every extreme point exactly when
$0\in\operatorname{int}\operatorname{conv}\\{v_{1},\ldots,v_{m}\\}$ [21, Lemma
4.3]. Therefore there is hope that this illumination algorithm would halt
fairly quickly for many homogeneous nonexpansive maps. By applying the
illumination algorithm to the recession map $f_{\infty}$ or a semiderivative
$f^{\prime}_{u}$, we can check whether a nonexpansive map has surjective
displacement or a unique fixed point.

For polyhedral norm nonexpansive maps, we already have computable necessary
and sufficient conditions for surjective displacement in Theorem 4.1 and for
uniqueness of fixed points in Corollary 6.3. In some cases however, the
illumination algorithm might be quicker to check. In particular, in
$\mathbb{R}^{n}$ with the $\ell_{1}$-norm, the unit ball only has $2n$ extreme
points, so the illumination algorithm might only need to check on the order of
$2n$ limits in order to verify surjective displacement or uniqueness. For
other spaces, such as $\mathbb{R}^{n}$ with the $\ell_{\infty}$-norm, this
algorithm would require at least $2^{n}$ limit computations (see [21,
Proposition 4.7]), and therefore would not have much, if any, advantage over
the conditions in Theorem 4.1 and Corollary 6.3.

On polyhedral normed spaces, homogeneous nonexpansive maps have additional
structure that is worth mentioning. Let $X$ be a finite dimensional real
Banach space with a polyhedral norm. Let $g:X\rightarrow X$ be homogeneous and
nonexpansive. Note that $g(B_{1})\subseteq B_{1}$ since $0$ is a fixed point
of $g$. For any $x\in B_{1}$, we will use the notation $F_{x}$ to indicate the
closed face of $B_{1}$ with $x$ in its relative interior. There is a simple
partial order that $B_{1}$ inherits from its faces. For $x,y\in B_{1}$, we
write $x\preceq y$ if $F_{x}\subseteq F_{y}$. We will also say that $x$ and
$y$ are _comparable_ , and write $x\sim y$, if $x\preceq y$ and $y\preceq x$,
that is if $x$ and $y$ are both in the relative interior of the same face of
$B_{1}$.

######  Lemma 7.6.

Let $X$ be a finite dimensional real Banach space with a polyhedral norm. Let
$g:X\rightarrow X$ be nonexpansive and homogeneous. Then $g$ is order-
preserving with respect to $\preceq$. That is, if $x,y\in B_{1}$ and
$F_{x}\subseteq F_{y}$, then $F_{g(x)}\subseteq F_{g(y)}$. Consequently, if
$x\sim y$, then $g(x)\sim g(y)$.

###### Proof.

Suppose that $x\preceq y$ for $x,y\in B_{1}$. If $\|g(y)\|<1$, then
$g(x)\preceq g(y)$ trivially since $F_{g(y)}=B_{1}$. Let us assume therefore
that $\|g(y)\|=1$. By Lemma 6.1, for any $t>0$ large enough, $\|ty-x\|=t-1$.
Choose any $\nu\in J(g(y))$. To prove that $F_{g(x)}\subseteq F_{g(y)}$, it
suffices to prove that $\left\langle g(x),\nu\right\rangle=1$. For $t>0$ large
enough,

$\displaystyle t-\left\langle g(x),\nu\right\rangle$
$\displaystyle=\left\langle tg(y)-g(x),\nu\right\rangle$
$\displaystyle(\text{since }\nu\in J(g(y)))$ $\displaystyle=\left\langle
g(ty)-g(x),\nu\right\rangle$ $\displaystyle(\text{homogeneity})$
$\displaystyle\leq\|g(ty)-g(x)\|$ $\displaystyle(\text{since }\|\nu\|_{*}=1)$
$\displaystyle\leq\|tx-y\|=t-1.$ $\displaystyle(\text{nonexpansiveness})$

From this, we conclude that $\left\langle g(x),\nu\right\rangle\geq 1$, which
means that $\left\langle g(x),\nu\right\rangle=1$ since $\|\nu\|_{*}=1$.
Therefore $g(x)\in F_{g(y)}$ as claimed. ∎

An immediate consequence of Lemma 7.6 is that homogeneous nonexpansive maps on
polyhedral normed spaces induce a well-defined order-preserving mapping on the
face lattice of the unit ball as follows: define $\hat{g}(F_{x})$ to be
$F_{g(x)}$ for any face $F_{x}$ of $B_{1}$. Then by Theorem 6.2, $0$ is the
unique fixed point of $g$ if and only if $B_{1}$ is the only fixed point of
$\hat{g}$. This suggests another possible route to check for surjective
displacement or uniqueness of fixed points. Since the face lattice is a finite
partially ordered set, one can search the face lattice for a fixed point of
$\hat{g}$. In some cases it may be possible to use the order-preserving
property of $\hat{g}$ to speed up the search.

### Acknowledgement

The idea for this paper was suggested by Marianne Akian and Stéphane Gaubert
during the 2019 IWOTA conference in Lisbon, Portugal. The author wishes to
thank them both for several discussions during that conference and for their
continued encouragement and suggestions since then. Thanks also to the referee
and to Roger Nussbaum for their careful reading and helpful comments.

## References

  * [1] M. Akian and S. Gaubert.  Spectral theorem for convex monotone homogeneous maps, and ergodic control.  Nonlinear Anal., 52(2):637–679, 2003.
  * [2] M. Akian, S. Gaubert, and A. Hochart.  Ergodicity conditions for zero-sum games.  Discrete Contin. Dyn. Syst., 35(9):3901–3931, 2015.
  * [3] M. Akian, S. Gaubert, and A. Hochart.  A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors.  Discrete Contin. Dyn. Syst., 40(1):207–231, 2020.
  * [4] M. Akian, S. Gaubert, and R. D. Nussbaum.  Uniqueness of the fixed point of nonexpansive semidifferentiable maps.  Trans. Amer. Math. Soc., 368(2):1271–1320, 2016.
  * [5] L. P. Belluce and W. A. Kirk.  Nonexpansive mappings and fixed-points in Banach spaces.  Illinois J. Math., 11:474–479, 1967.
  * [6] L. P. Belluce, W. A. Kirk, and E. F. Steiner.  Normal structure in Banach spaces.  Pacific J. Math., 26:433–440, 1968.
  * [7] G. Birkhoff.  Extensions of Jentzsch’s theorem.  Trans. Amer. Math. Soc., 85:219–227, 1957.
  * [8] H. Brezis.  Functional analysis, Sobolev spaces and partial differential equations.  Universitext. Springer, New York, 2011.
  * [9] F. E. Browder.  Nonexpansive nonlinear operators in a Banach space.  Proc. Nat. Acad. Sci. U.S.A., 54:1041–1044, 1965.
  * [10] K. Deimling.  Nonlinear Functional Analysis.  Dover Books on Mathematics. Dover Publications, 2010.
  * [11] J. García-Falset, E. Llorens-Fuster, and E. M. Mazcuñan Navarro.  Uniformly nonsquare Banach spaces have the fixed point property for nonexpansive mappings.  J. Funct. Anal., 233(2):494–514, 2006.
  * [12] S. Gaubert and J. Gunawardena.  The Perron-Frobenius theorem for homogeneous, monotone functions.  Trans. Amer. Math. Soc., 356(12):4931–4950, 2004.
  * [13] S. Gaubert and G. Vigeral.  A maximin characterisation of the escape rate of non-expansive mappings in metrically convex spaces.  Math. Proc. Cambridge Philos. Soc., 152(2):341–363, 2012.
  * [14] D. Göhde.  Zum Prinzip der kontraktiven Abbildung.  Math. Nachr., 30:251–258, 1965.
  * [15] A. W. Gutiérrez.  On the metric compactification of infinite-dimensional $\ell_{p}$ spaces.  Canad. Math. Bull., 62(3):491–507, 2019.
  * [16] A. Hochart.  An accretive operator approach to ergodic zero-sum stochastic games.  J. Dyn. Games, 6(1):27–51, 2019.
  * [17] A. Kaewcharoen and W. A. Kirk.  Nonexpansive mappings defined on unbounded domains.  Fixed Point Theory Appl., pages Art. ID 82080, 13, 2006.
  * [18] G. Kalai.  The number of faces of centrally-symmetric polytopes.  Graphs Combin., 5(1):389–391, 1989.
  * [19] W. A. Kirk.  A fixed point theorem for mappings which do not increase distances.  Amer. Math. Monthly, 72:1004–1006, 1965.
  * [20] E. Kohlberg and J. W. Pratt.  The contraction mapping approach to the Perron-Frobenius theory: why Hilbert’s metric?  Math. Oper. Res., 7(2):198–210, 1982.
  * [21] B. Lemmens, B. Lins, and R. D. Nussbaum.  Detecting fixed points of nonexpansive maps by illuminating the unit ball.  Israel J. Math., 224(1):231–262, 2018.
  * [22] B. Lemmens and R. D. Nussbaum.  Nonlinear Perron-Frobenius theory, volume 189 of Cambridge Tracts in Mathematics.  Cambridge University Press, Cambridge, 2012.
  * [23] M. Morishima.  Equilibrium, stability, and growth: A multi-sectoral analysis.  Clarendon Press, Oxford, 1964.
  * [24] R. D. Nussbaum.  Hilbert’s projective metric and iterated nonlinear maps.  Mem. Amer. Math. Soc., 75(391):iv+137, 1988.
  * [25] Y. Oshime.  An extension of Morishima’s nonlinear Perron-Frobenius theorem.  J. Math. Kyoto Univ., 23(4):803–830, 1983.
  * [26] J. Penot.  A fixed-point theorem for asymptotically contractive mappings.  Proc. Amer. Math. Soc., 131(8):2371–2377, 2003.
  * [27] S. Reich.  On the asymptotic behavior of nonlinear semigroups and the range of accretive operators. II.  J. Math. Anal. Appl., 87(1):134–146, 1982.
  * [28] S. Reich and R. Torrejón.  Zeros of accretive operators.  Comment. Math. Univ. Carolin., 21(3):619–625, 1980.
  * [29] R. T. Rockafellar.  Convex analysis.  Princeton Mathematical Series, No. 28. Princeton University Press, Princeton, N.J., 1970.
  * [30] R. Sanyal, A. Werner, and G. M. Ziegler.  On Kalai’s conjectures concerning centrally symmetric polytopes.  Discrete Comput. Geom., 41(2):183–198, 2009.
  * [31] C. Walsh.  The horofunction boundary of finite-dimensional normed spaces.  Math. Proc. Cambridge Philos. Soc., 142(3):497–507, 2007.