1 Introduction and statement of the result
1.1 Polyhedral sets
A polyhedral set
$P$
in
$\mathbb{R}^{d}$
is an intersection of finitely many closed half-spaces. That is,
$P$
is a closed convex set which can be represented as
$$\begin{eqnarray}P=\{x\in \mathbb{R}^{d}:Mx\leqslant b\},\end{eqnarray}$$
where
$M$
is an
$m\times d$
-matrix and
$b\in \mathbb{R}^{m}$
. A bounded polyhedral set is called a polytope. A polyhedral cone is an intersection of finitely many closed half-spaces whose boundaries contain the origin. If not otherwise stated, polyhedral sets, cones and polytopes are assumed to be non-empty.
A polyhedral set
$P$
is called line-free if it does not contain a line, i.e. a set of the form
$\{x+\unicode[STIX]{x1D706}y:\unicode[STIX]{x1D706}\in \mathbb{R}\}$
,
$x\in \mathbb{R}^{d}$
,
$y\in \mathbb{R}^{d}\setminus \{0\}$
. In general, the lineality space of
$P$
, represented in the form (1), is
$U_{P}=\{x\in \mathbb{R}^{d}:Mx=0\}$
. Then,
$P$
is line-free if its lineality space is
$\{0\}$
, or, equivalently, if the matrix
$M$
has rank
$d$
. Every polyhedral set has an orthogonal decomposition
$P=P_{0}+U_{P}$
, where
$P_{0}$
is a line-free polyhedral set; see [Reference Padberg9, §7.2] or [Reference Schneider16, Lemma 1.4.2].
The finite set of faces of a polyhedral set
$P$
is denoted by
${\mathcal{F}}(P)$
, which includes
$P$
itself but does not include the empty face. For the notion and basic properties of a face of a polyhedral set we refer to [Reference Padberg9, §7.2.1] or [Reference Rockafellar12] and, for general convex sets, to [Reference Schneider16, §§2.1 and 2.4]. The face structure of a polyhedral set is much simpler than that of a general convex set. In particular, faces are always support sets. The normal cone of
$P$
at a point
$x\in P$
is defined as
$$\begin{eqnarray}N(P,x)=\{u\in \mathbb{R}^{d}:\langle u,z-x\rangle \leqslant 0\text{ for all }z\in P\},\end{eqnarray}$$
where
$\langle \cdot \,,\cdot \rangle$
denotes the scalar product of the underlying Euclidean space
$\mathbb{R}^{d}$
. For a face
$F\in {\mathcal{F}}(P)$
, the normal cone
$N(P,x)$
does not depend on the choice of a point
$x\in \operatorname{relint}F$
(the relative interior of
$F$
), hence it is denoted by
$N(P,F)$
and referred to as the normal cone of
$P$
at the face
$F$
. Note that
$N(P,F)$
is a closed polyhedral cone and
$N(P,P)=\{0\}$
if
$\text{dim}(P)=d$
. In general,
$N(P,P)=L(P)^{\bot }$
, where
$L(P)$
is the linear subspace parallel to the affine hull
$\operatorname{aff}(P)$
of
$P$
.
1.2 Statement of the result
The indicator function of a set
$A\subset \mathbb{R}^{d}$
is denoted by
$\unicode[STIX]{x1D7D9}_{A}$
. For two sets
$A,B\subset \mathbb{R}^{d}$
let
$$\begin{eqnarray}A+B=\{a+b:a\in A,b\in B\},\qquad A-B=\{a-b:a\in A,b\in B\}.\end{eqnarray}$$
The aim of the present note is to prove the following Euler-type inclusion–exclusion relation.
Theorem 1.1. Let
$P\subset \mathbb{R}^{d}$
be a polyhedral set. Then, the function
$\unicode[STIX]{x1D711}_{P}:\mathbb{R}^{d}\rightarrow \mathbb{Z}$
defined by
$$\begin{eqnarray}\unicode[STIX]{x1D711}_{P}:=\mathop{\sum }_{F\in {\mathcal{F}}(P)}(-1)^{\operatorname{dim}F}\unicode[STIX]{x1D7D9}_{F-N(P,F)}\end{eqnarray}$$
is constant and takes values in
$\{-1,0,1\}$
. If
$P=P_{0}+U_{P}$
, where
$U_{P}$
is the lineality space of
$P$
and
$P_{0}$
is a line-free polyhedral set, then
$\unicode[STIX]{x1D711}_{P}\equiv (-1)^{\operatorname{dim}U_{P}}$
if
$P_{0}$
is bounded and
$\unicode[STIX]{x1D711}_{P}\equiv 0$
if
$P_{0}$
is unbounded.
In particular, if
$P$
is a polytope, then
$\unicode[STIX]{x1D711}_{P}\equiv 1$
, whereas for an unbounded line-free polyhedral set we have
$\unicode[STIX]{x1D711}_{P}\equiv 0$
.
1.3 Comments
Previously, the function
$\unicode[STIX]{x1D711}_{P}$
was known to be constant everywhere outside some exceptional set of Lebesgue measure
$0$
. For polyhedral cones, this statement was given without proof by McMullen in [Reference McMullen8, p. 249]. Proofs for polyhedral cones can be found in the book of Schneider and Weil [Reference Schneider and Weil17], see the proof of Theorem 6.5.5 there, and in the PhD Thesis of Glasauer [Reference Glasauer4], see Hilfssatz 4.3.2 there. Both proofs follow an approach suggested by McMullen. It was conjectured in [Reference Glasauer4] that the formula should hold without the need to exclude an exceptional set. A proof of the formula for polytopes was given by Glasauer in [Reference Glasauer5]. An extension to Minkowski geometry with a general convex gauge body was obtained by Hug [Reference Hug6, Corollary 2.25 on p. 89]. In all these results, an exceptional set of measure
$0$
is present. Our contribution is to remove such an exceptional set. Shortly before this paper was completed, we became aware of the preprint of Schneider [Reference Schneider15], where the exceptional set was removed for polyhedral cones. The method used in the present paper is different from Schneider’s approach and yields a result valid in the more general setting of polyhedral sets. In fact, reducing the general case of polyhedral sets to polyhedral cones is the core of our proof. After such a reduction has been accomplished, the result for cones follows quickly.
The starting point of the present paper was the observation that the relations stated in Theorem 1.1 are similar to the inclusion–exclusion identities for convex hulls obtained by Cowan [Reference Cowan2, Reference Cowan3]. Cowan proved his identities outside an exceptional set of measure zero. Recently, the exceptional set was removed in [Reference Kabluchko, Last and Zaporozhets7]. The method of [Reference Kabluchko, Last and Zaporozhets7] (based on an extended Euler relation) is quite different from the approach of the present paper.
Let us mention two “topological” interpretations of Theorem 1.1. It is well known that
$$\begin{eqnarray}\mathop{\sum }_{F\in {\mathcal{F}}(P)}\unicode[STIX]{x1D7D9}_{\operatorname{relint}F+N(P,F)}=1.\end{eqnarray}$$
Consider a piecewise linear map
$\unicode[STIX]{x1D6F9}:\mathbb{R}^{d}\rightarrow \mathbb{R}^{d}$
defined by
$f(x+u)=x-u$
, where
$x\in \operatorname{relint}F$
,
$u\in N(P,F)$
. This map reflects each set
$\operatorname{relint}F+N(P,F)$
at the corresponding face
$F$
. The restriction of
$\unicode[STIX]{x1D6F9}$
to
$P$
is the identity map. The map
$\unicode[STIX]{x1D6F9}$
is continuous but not smooth everywhere. Let
$J_{\unicode[STIX]{x1D6F9}}$
be the Jacobian of
$\unicode[STIX]{x1D6F9}$
(whenever it is defined). For the “regular values”
$z$
which do not belong to the boundaries of the sets
$F-N(P,F)$
, we may define the degree of
$\unicode[STIX]{x1D6F9}$
as
$$\begin{eqnarray}\displaystyle (\deg \unicode[STIX]{x1D6F9})(z) & = & \displaystyle \mathop{\sum }_{a\in \unicode[STIX]{x1D6F9}^{-1}(z)}\operatorname{sgn}\det J_{\unicode[STIX]{x1D6F9}}(a)=\mathop{\sum }_{F\in {\mathcal{F}}(P)}(-1)^{d-\dim F}\unicode[STIX]{x1D7D9}_{F-N(P,F)}(z)\nonumber\\ \displaystyle & = & \displaystyle (-1)^{d}\unicode[STIX]{x1D711}_{P}(z).\nonumber\end{eqnarray}$$
To give another interpretation, consider the normal bundle of
$P$
defined as
$$\begin{eqnarray}\text{NB}(P)=\mathop{\bigcup }_{F\in {\mathcal{F}}(P)}\{(x,u):x\in F,u\in N(P,F)\}\subset \mathbb{R}^{d}\times \mathbb{R}^{d}.\end{eqnarray}$$
This is the union set of the normal manifold (normal fan) as defined in [Reference Robinson10, Reference Lu and Robinson11, Reference Scholtes13, Reference Scholtes14, Reference Ziegler18]. For regular values
$z$
one can interpret
$\unicode[STIX]{x1D711}_{P}(z)$
as the “intersection index” between
$\text{NB}(P)$
and the
$d$
-dimensional linear subspace
$$\begin{eqnarray}L_{z}=\{(x,y)\in \mathbb{R}^{d}\times \mathbb{R}^{d}:x-y=z\}.\end{eqnarray}$$
Comparing to classical results in differentiable topology, it is not surprising that
$\unicode[STIX]{x1D711}_{P}(z)$
stays constant for regular points
$z\in \mathbb{R}^{d}$
. The main contribution of the present note is the analysis of the non-regular values.
1.4 Notation
The rest of the paper is devoted to the proof of Theorem 1.1. Let us fix some notation. Let
$\operatorname{int}K$
be the interior of a set
$K$
and
$\unicode[STIX]{x2202}K$
its boundary. Let
$\operatorname{relint}K$
be the relative interior of a set
$K$
, that is the interior with respect to its affine hull
$\operatorname{aff}K$
. If
$A\subset \mathbb{R}^{d}$
, then we write
$\text{conv}(A)$
for the convex hull and
$\text{pos}(A)$
for the positive hull of
$A$
. For a convex set
$K\subset \mathbb{R}^{d}$
, let
$L(K)$
denote the linear subspace parallel to the affine subspace
$\operatorname{aff}K$
. Let
$B(z,\unicode[STIX]{x1D700})=\{y\in \mathbb{R}^{d}:\Vert z-y\Vert \leqslant \unicode[STIX]{x1D700}\}$
be the closed ball of radius
$\unicode[STIX]{x1D700}$
around
$z\in \mathbb{R}^{d}$
, where
$\Vert \cdot \Vert$
denotes the Euclidean norm.
2 Proof of Theorem 1.1
Step 0. We use induction over the dimension
$d$
. In Steps 1–7 below, we prove the following two claims.
Claim 2.1 (Reduction to cones).
If the function
$\unicode[STIX]{x1D711}_{P}$
is constant for every polyhedral cone
$P$
, then it is constant for every polyhedral set
$P$
.
Claim 2.2 (Induction for cones).
If the function
$\unicode[STIX]{x1D711}_{P}$
is constant for every polyhedral cone
$P$
in dimensions
${\leqslant}d-1$
, then it is constant for every polyhedral cone
$P$
in dimension
${\leqslant}d$
.
Once Claim 2.2 has been established, it follows by induction over
$d$
that
$\unicode[STIX]{x1D711}_{P}$
is constant for every polyhedral cone in any dimension. The induction assumption in dimension
$d=1$
is easily checked because there are just the following cones:
$\{0\}$
,
$[0,\infty )$
,
$(-\infty ,0]$
,
$\mathbb{R}$
. In fact, for a polyhedral cone
$P\subset \mathbb{R}^{d}$
which is not a linear subspace, we even have
$\unicode[STIX]{x1D711}_{P}\equiv 0$
because
$$\begin{eqnarray}\unicode[STIX]{x1D711}_{P}(0)=\mathop{\sum }_{F\in {\mathcal{F}}(P)}(-1)^{\operatorname{dim}F}\unicode[STIX]{x1D7D9}_{F-N(P,F)}(0)=\mathop{\sum }_{F\in {\mathcal{F}}(P)}(-1)^{\operatorname{dim}F}=0\end{eqnarray}$$
by the Euler relation for polyhedral cones; see, e.g., [Reference Amelunxen and Lotz1, Theorem 2.1]. Given that
$\unicode[STIX]{x1D711}_{P}$
is constant for polyhedral cones, Claim 2.1 implies that
$\unicode[STIX]{x1D711}_{P}$
is constant for all polyhedral sets. It remains to determine the value of this constant, which is done by exhibiting at least one point for which an explicit computation is possible.
Case 1. Let
$P$
be a non-empty bounded polyhedral set. Take any vertex
$p$
of
$P$
and let
$u\in \operatorname{int}N(P,\{p\})$
. We claim that for each
$F\in {\mathcal{F}}(P)$
,
$F\neq \{p\}$
, there is some
$\unicode[STIX]{x1D706}_{F}>0$
such that
$p-\unicode[STIX]{x1D706}u\notin F-N(P,F)$
for
$\unicode[STIX]{x1D706}>\unicode[STIX]{x1D706}_{F}$
. If not, then there is an increasing sequence
$(\unicode[STIX]{x1D706}_{i})_{i\in \mathbb{N}}$
in
$(0,\infty )$
with
$\unicode[STIX]{x1D706}_{i}\rightarrow \infty$
for
$i\rightarrow \infty$
such that
$p-\unicode[STIX]{x1D706}_{i}u=f_{i}-u_{i}$
with
$f_{i}\in F$
and
$u_{i}\in N(P,F)$
, for all
$i\in \mathbb{N}$
. Hence
$u-u_{i}/\unicode[STIX]{x1D706}_{i}=(p-f_{i})/\unicode[STIX]{x1D706}_{i}\rightarrow 0$
as
$i\rightarrow \infty$
(here we use that
$F\subset P$
is bounded). Since
$u\in \operatorname{int}N(P,\{p\})$
, it follows that
$u_{i}\in \unicode[STIX]{x1D706}_{i}\operatorname{int}N(P,\{p\})=\operatorname{int}N(P,\{p\})$
if
$i$
is large enough. Since
$\operatorname{int}N(P,\{p\})\cap N(P,F)=\varnothing$
if
$F\neq \{p\}$
, we arrive at a contradiction. Hence, choosing
$\unicode[STIX]{x1D706}>0$
larger than
$\max \{\unicode[STIX]{x1D706}_{F}:F\in {\mathcal{F}}(P),F\neq \{p\}\}$
, we get
$\unicode[STIX]{x1D711}_{P}(p-\unicode[STIX]{x1D706}u)=(-1)^{0}=1$
.
Case 2. Let
$P$
be an unbounded, line-free polyhedral set. Then there are points
$a_{1},\ldots ,a_{k}\in \mathbb{R}^{d}$
and vectors
$b_{1},\ldots ,b_{m}\in \mathbb{R}^{d}\setminus \{0\}$
such that
$$\begin{eqnarray}P=\text{conv}\{a_{1},\ldots ,a_{k}\}+\text{pos}\{b_{1},\ldots ,b_{m}\},\end{eqnarray}$$
where
$k,m\in \mathbb{N}$
(see [Reference Rockafellar12, Theorem 19.1] or [Reference Padberg9, 7.3(d) on p. 149]). Then
$C:=\text{pos}\{b_{1},\ldots ,b_{m}\}$
is a closed convex cone and
$C^{\ast }:=C\setminus \{0\}$
is non-empty and convex, since
$P$
is line-free. The reflected polar cone
$-C^{\circ }$
of
$C$
is also convex and non-empty. We have
$C\cap (-C^{\circ })\neq \{0\}$
, since otherwise
$C^{\ast }\cap (-C^{\circ })=\varnothing$
and a separation argument then yields a vector
$u\neq 0$
such that
$C^{\ast }\subset u^{-}:=\{z\in \mathbb{R}^{d}:\langle z,u\rangle \leqslant 0\}$
and
$C^{\circ }\subset u^{-}$
. But then
$u\in C^{\circ }\subset u^{-}$
, and thus
$u=0$
, a contradiction. Hence there is some
$y\in C^{\circ }\setminus \{0\}$
with
$-y\in C$
. Alternatively, the fact that
$C\cap (-C^{\circ })\neq \{0\}$
could be deduced from the generalized Farkas lemma [Reference Amelunxen and Lotz1, Lemma 2.3].
We can assume that
$\langle a_{1},y\rangle =\max \{\langle a_{i},y\rangle :i=1,\ldots ,k\}$
. From
$y\in C^{\circ }$
we conclude that
$\langle y,b_{j}\rangle \leqslant 0$
for
$j=1,\ldots ,m$
. Moreover, if
$p\in P$
and
$u\in N(P,p)$
, then
$\langle p-(a_{1}-\unicode[STIX]{x1D706}y),u\rangle \geqslant 0$
for all
$\unicode[STIX]{x1D706}\geqslant 0$
, hence
$\langle p-a_{1},u\rangle +\unicode[STIX]{x1D706}\langle y,u\rangle \geqslant 0$
for all
$\unicode[STIX]{x1D706}\geqslant 0$
which implies that
$\langle y,u\rangle \geqslant 0$
.
Now we can conclude that
$a_{1}+y\notin F-N(P,F)$
for all
$F\in {\mathcal{F}}(P)$
. In fact, assume that there are
$F\in {\mathcal{F}}(P)$
,
$f\in F$
and
$u\in N(P,F)$
such that
$a_{1}+y=f-u$
. Since
$f\in P$
, there are
$\unicode[STIX]{x1D706}_{i},\unicode[STIX]{x1D707}_{j}\geqslant 0$
for
$i=1,\ldots ,k$
and
$j=1,\ldots ,m$
with
$\unicode[STIX]{x1D706}_{1}+\cdots +\unicode[STIX]{x1D706}_{k}=1$
such that
$f=\sum _{i=1}^{k}\unicode[STIX]{x1D706}_{i}a_{i}+\sum _{j=1}^{m}\unicode[STIX]{x1D707}_{j}b_{j}$
. Now we get
$$\begin{eqnarray}\langle f-u,y\rangle =\mathop{\sum }_{i=1}^{k}\unicode[STIX]{x1D706}_{i}\langle a_{i},y\rangle +\mathop{\sum }_{j=1}^{m}\unicode[STIX]{x1D707}_{j}\langle b_{j},y\rangle -\langle u,y\rangle \leqslant \langle a_{1},y\rangle <\langle a_{1}+y,y\rangle ,\end{eqnarray}$$
a contradiction.
It follows that
$a_{1}+y$
is not contained in a set of the form
$F-N(P,F)$
,
$F\in {\mathcal{F}}(P)$
, and hence,
$\unicode[STIX]{x1D711}_{P}(a_{1}+y)=0$
.
Case 3. Finally, if
$P$
is not line-free, then
$P=P_{0}+U_{P}$
, where
$P_{0}$
is a line-free polyhedral set and
$U_{P}\subset L(P)$
is the lineality space of
$P$
. We can choose
$P_{0}$
such that
$L(P_{0})=L(P)\cap U_{P}^{\bot }$
and hence
$U_{P}=L(P_{0})^{\bot }\cap L(P)$
. First, we observe that
$F\in {\mathcal{F}}(P)$
if and only if there is some (uniquely determined)
$F_{0}\in {\mathcal{F}}(P_{0})$
with
$F=F_{0}+U_{P}$
. Conversely,
$F_{0}+U_{P}\in {\mathcal{F}}(P)$
for every
$F_{0}\in {\mathcal{F}}(P_{0})$
. Let
$N_{L(P_{0})}(P_{0},F_{0})\subset L(P_{0})=U_{P}^{\bot }\cap L(P)=(U_{P}+L(P)^{\bot })^{\bot }$
be the normal cone of
$P_{0}$
at its face
$F_{0}$
with respect to
$\operatorname{aff}P_{0}$
as the ambient space. In this situation, using [Reference Schneider16, Theorem 2.2.1(a)] for the second and [Reference Schneider16, (2.5)] for the third equation, we get
$$\begin{eqnarray}\displaystyle N(P,F) & = & \displaystyle N(P_{0}+U_{P},F_{0}+U_{P})=N(P_{0},F_{0})\cap U_{P}^{\bot }\nonumber\\ \displaystyle & = & \displaystyle (N_{L(P_{0})}(P_{0},F_{0})+L(P_{0})^{\bot })\cap U_{P}^{\bot }\nonumber\\ \displaystyle & = & \displaystyle (N_{L(P_{0})}(P_{0},F_{0})+L(P)^{\bot }+U_{P})\cap U_{P}^{\bot }\nonumber\\ \displaystyle & = & \displaystyle N_{L(P_{0})}(P_{0},F_{0})+L(P)^{\bot }\subset U_{P}^{\bot }.\nonumber\end{eqnarray}$$
If
$x\in \mathbb{R}^{d}$
, then there are uniquely determined
$x_{0}\in \operatorname{aff}P_{0}$
,
$u\in U_{P}$
, and
$v\in L(P)^{\bot }$
such that
$x=x_{0}+u+v$
, and hence
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D711}_{P}(x) & = & \displaystyle \mathop{\sum }_{F\in {\mathcal{F}}(P)}\!\!(-1)^{\dim F}\unicode[STIX]{x1D7D9}_{\operatorname{relint}F-N(P,F)}(x)\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{F_{0}\in {\mathcal{F}}(P_{0})}\!\!(-1)^{\dim F_{0}+\dim U_{P}}\unicode[STIX]{x1D7D9}_{\operatorname{relint}F_{0}+U_{P}-N_{L(P_{0})}(P_{0},F_{0})+L(P)^{\bot }}(x_{0}+u+v)\nonumber\\ \displaystyle & = & \displaystyle (-1)^{\dim U_{P}}\mathop{\sum }_{F_{0}\in {\mathcal{F}}(P_{0})}\!\!(-1)^{\dim F_{0}}\unicode[STIX]{x1D7D9}_{\operatorname{relint}F_{0}-N_{L(P_{0})}(P_{0},F_{0})}(x_{0}).\nonumber\end{eqnarray}$$
The assertion now follows from the preceding two cases.
In the following we prove Claims 2.1 and 2.2. The proofs of both claims will be parallel.
Step 1. In the following, let
$P\subset \mathbb{R}^{d}$
be a polyhedral set. Let
$x\in \mathbb{R}^{d}$
be arbitrarily chosen. Our aim is to show that
$\unicode[STIX]{x1D711}_{P}$
is constant in a sufficiently small neighbourhood of
$x$
. We start with some preparations, with the aim of splitting the summation involved in
$\unicode[STIX]{x1D711}_{P}$
into two parts, one of which is easy to treat. If
$F\in {\mathcal{F}}(P)$
is such that
$x\notin \unicode[STIX]{x2202}(F-N(P,F))$
, then
$$\begin{eqnarray}\unicode[STIX]{x1D7D9}_{F-N(P,F)}(x)=\unicode[STIX]{x1D7D9}_{F-N(P,F)}(y)\quad \text{for all }y\in B(x,\unicode[STIX]{x1D700}),\end{eqnarray}$$
provided
$\unicode[STIX]{x1D700}>0$
is small enough. To see this, observe that the set
$\mathbb{R}^{d}\setminus \unicode[STIX]{x2202}(F-N(P,F))$
is open.
Step 2. Now we suppose
$x\in \unicode[STIX]{x2202}(F-N(P,F))$
for some
$F\in {\mathcal{F}}(P)$
. Our aim is to show that the set
$$\begin{eqnarray}S_{x}:=\{(G,H)\in {\mathcal{F}}(P)\times {\mathcal{F}}(P):G\subset H,G\neq H,x\in \operatorname{relint}G-\operatorname{relint}N(P,H)\}\end{eqnarray}$$
is non-empty. By basic properties of faces of closed convex sets (see [Reference Schneider16, §2.1, Theorem 2.1.2]) we have a disjoint decomposition
It follows from [Reference Schneider16, Theorem 2.1.2] and [Reference Lu and Robinson11, Proposition 1], based on [Reference Scholtes13] or its reprint [Reference Scholtes14, Chs 2.1 and 2.4], that
For the sake of convenience we provide another argument based on duality. For this, let
$W$
be a polytope with
$\operatorname{int}W\cap \operatorname{relint}F\neq \varnothing$
. By [Reference Schneider16, Theorem 2.2.1(b)], we have
$N(P,F)=N(P\cap W,F\cap W)$
and
$N(P,H)=N(P\cap W,H\cap W)$
for any
$H\in {\mathcal{F}}(P)$
with
$F\subset H$
. Clearly,
$H\cap W\in {\mathcal{F}}(P\cap W)$
and any face of
$P\cap W$
is of this form. Then, using also [Reference Schneider16, (2.5)] twice and writing
$L=L(P)$
, we get
where the main step is the third equality which is the reduction to full dimensional polytopes. To prove the assertion in this special case, we use [Reference Schneider16, Theorem 2.4.9] to see that
$$\begin{eqnarray}N(P,F)=\operatorname{pos}\{u_{i}:F\subset F_{i},i\in [n]\},\end{eqnarray}$$
where
$[n]=\{1,\ldots ,n\}$
,
$F_{1},\ldots ,F_{n}$
are the facets of
$P$
and
$u_{i}\in \mathbb{S}^{d-1}$
is the exterior unit normal vector of
$F_{i}$
for
$i=1,\ldots ,n$
. The proof of [Reference Schneider16, Theorem 2.4.9] also shows that
$S\in {\mathcal{F}}(N(P,F))$
if and only if there is a set
$J\subset I=\{i\in [n]:F\subset F_{i}\}$
with
$S=\operatorname{pos}\{u_{j}:j\in J\}$
, and then
$H:=\cap \{F_{j}:j\in J\}$
is the uniquely determined face of
$P$
with
$F\subset H$
and
$S=N(P,H)$
. Conversely, if
$H\in {\mathcal{F}}(P)$
with
$F\subset H$
then
$N(P,H)$
is a face of
$N(P,F)$
. Now the assertion follows from [Reference Schneider16, Theorem 2.1.2].
Since
$L(F)$
and
$L(N(P,F))$
are complementary linear subspaces, it follows that
is the decomposition of the
$d$
-dimensional polyhedral set
$F-N(P,F)$
into the relative interiors of its faces. Here we use that
$\operatorname{relint}(A+B)=\operatorname{relint}A+\operatorname{relint}B$
for all convex sets
$A,B\subset \mathbb{R}^{d}$
(see [Reference Rockafellar12, Corollary 6.6.2]). In particular,
$$\begin{eqnarray}\operatorname{int}(F-N(P,F))=\operatorname{relint}F-\operatorname{relint}N(P,F)\end{eqnarray}$$
and
It follows that the set
$S_{x}$
is non-empty.
Step 3. For
$G,H\in {\mathcal{F}}(P)$
with
$G\subset H$
we consider the “interval”
$$\begin{eqnarray}I(G,H):=\{F\in {\mathcal{F}}(P):G\subset F\subset H\}.\end{eqnarray}$$
Lemma 2.3. If
$(G_{1},H_{1})\in S_{x}$
,
$(G_{2},H_{2})\in S_{x}$
and
$(G_{1},H_{1})\neq (G_{2},H_{2})$
, then
$$\begin{eqnarray}I(G_{1},H_{1})\cap I(G_{2},H_{2})=\varnothing .\end{eqnarray}$$
Proof. We proceed by contradiction. For this we assume that there is a face
$F\in I(G_{1},H_{1})\cap I(G_{2},H_{2})$
. Then
$G_{i}\subset F\subset H_{i}$
and
$$\begin{eqnarray}x\in \operatorname{relint}G_{i}-\operatorname{relint}N(P,H_{i})\subset F-N(P,F),\end{eqnarray}$$
for
$i=1,2$
. Hence
$x=g_{i}-v_{i}$
with
$g_{i}\in \operatorname{relint}G_{i}\subset F$
and
$v_{i}\in \operatorname{relint}N(P,H_{i})\subset N(P,F)$
for
$i=1,2$
. From
$g_{1}-g_{2}=v_{1}-v_{2}\in L(F)\cap L(N(P,F))=\{0\}$
we see that
$g_{1}=g_{2}$
and
$v_{1}=v_{2}$
. This implies that
$\operatorname{relint}G_{1}=\operatorname{relint}G_{2}$
and
$\operatorname{relint}N(P,H_{1})=\operatorname{relint}N(P,H_{2})$
, and thus
$G_{1}=G_{2}$
and
$H_{1}=H_{2}$
.◻
Step 4. After these preparations, for
$(G,H)\in S_{x}$
and
$y\in \mathbb{R}^{d}$
, we define
$$\begin{eqnarray}\unicode[STIX]{x1D711}_{G,H}(y):=\mathop{\sum }_{F\in I(G,H)}(-1)^{\dim F}\unicode[STIX]{x1D7D9}_{F-N(P,F)}(y).\end{eqnarray}$$
Then Lemma 2.3 implies that
$$\begin{eqnarray}\unicode[STIX]{x1D711}_{P}(y)=\mathop{\sum }_{(G,H)\in S_{x}}\unicode[STIX]{x1D711}_{G,H}(y)+\mathop{\sum }_{F\in C_{x}}(-1)^{\dim F}\unicode[STIX]{x1D7D9}_{F-N(P,F)}(y),\end{eqnarray}$$
where
If
$F\in C_{x}$
, then
$x\notin \unicode[STIX]{x2202}(F-N(P,F))$
as we have seen in Step 2, and therefore
$\unicode[STIX]{x1D7D9}_{F-N(P,F)}$
is constant in a sufficiently small neighbourhood of
$x$
by Step 1. Therefore, it is sufficient to show that for all
$(G,H)\in S_{x}$
the function
$\unicode[STIX]{x1D711}_{G,H}$
is constant in a sufficiently small neighbourhood of
$x$
.
Step 5. So let
$(G,H)\in S_{x}$
be fixed and consider
$\unicode[STIX]{x1D711}_{G,H}(y)$
for
$y\in B(x,\unicode[STIX]{x1D700})$
. Put
$L_{1}:=L(G)$
,
$L_{2}:=L(N(P,H))$
and
$L_{3}:=(L_{1}+L_{2})^{\bot }=L_{1}^{\bot }\cap L(H)$
. Thus, we have an orthogonal decomposition
$\mathbb{R}^{d}=L_{1}+L_{2}+L_{3}$
. Further, recalling (4), we have
$x=x_{1}+x_{2}$
with uniquely determined
$x_{1}\in \operatorname{relint}G$
and
$x_{2}\in -\operatorname{relint}N(P,H)$
. If
$y\in \mathbb{R}^{d}$
and
$y\in B(x,\unicode[STIX]{x1D700})$
, then
$y=x+\unicode[STIX]{x1D6E5}_{1}+\unicode[STIX]{x1D6E5}_{2}+\unicode[STIX]{x1D6E5}_{3}$
with
$\unicode[STIX]{x1D6E5}_{i}\in L_{i}$
and
$\Vert \unicode[STIX]{x1D6E5}_{i}\Vert \leqslant \unicode[STIX]{x1D700}$
for
$i=1,2,3$
.
Lemma 2.4. Let
$T\subset \mathbb{R}^{d}$
be a polyhedral set,
$C$
a face of
$T$
and
$z\in \operatorname{relint}C$
. Then there is some
$\unicode[STIX]{x1D700}>0$
such that
$\unicode[STIX]{x1D7D9}_{T}(z_{1})=\unicode[STIX]{x1D7D9}_{T}(z_{2})$
for all
$z_{1},z_{2}\in B(z,\unicode[STIX]{x1D700})$
with
$z_{2}-z_{1}\in L(C)$
.
Proof. The system of inequalities defining
$P$
can be written in the form
$$\begin{eqnarray}\langle u_{1},y\rangle \leqslant \unicode[STIX]{x1D6FC}_{1},\ldots ,\langle u_{m},y\rangle \leqslant \unicode[STIX]{x1D6FC}_{m}\end{eqnarray}$$
for some
$u_{1},\ldots ,u_{m}\in \mathbb{R}^{d}\setminus \{0\}$
and
$\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{m}\in \mathbb{R}$
. Faces of
$T$
are obtained by turning some of these inequalities into equalities. Without loss of generality, let us assume that
$\operatorname{relint}C$
is given by
$$\begin{eqnarray}\langle u_{1},y\rangle <\unicode[STIX]{x1D6FC}_{1},\ldots ,\langle u_{l},y\rangle <\unicode[STIX]{x1D6FC}_{l},\qquad \langle u_{l+1},y\rangle =\unicode[STIX]{x1D6FC}_{l+1},\ldots ,\langle u_{m},y\rangle =\unicode[STIX]{x1D6FC}_{m},\end{eqnarray}$$
for some
$0\leqslant l\leqslant m$
. Note that ignoring the strict inequalities, we obtain a system defining
$\operatorname{aff}C$
. Let now
$z_{1},z_{2}$
be as in the statement of the lemma. Since linear functions are continuous, we can find some
$\unicode[STIX]{x1D700}>0$
such that for all
$\,z_{1},z_{2}\in \,B(z,\unicode[STIX]{x1D700})$
we have
$$\begin{eqnarray}\langle u_{1},z_{i}\rangle <\unicode[STIX]{x1D6FC}_{1},\ldots ,\langle u_{l},z_{i}\rangle <\unicode[STIX]{x1D6FC}_{l},\quad i=1,2.\end{eqnarray}$$
Since
$z_{1}-z_{2}\in L(C)$
, we also have
$$\begin{eqnarray}\langle u_{l+1},z_{1}\rangle =\langle u_{l+1},z_{2}\rangle ,\ldots ,\langle u_{m},z_{1}\rangle =\langle u_{m},z_{2}\rangle ,\end{eqnarray}$$
which implies that
$z_{1}\in T$
if and only if
$z_{2}\in T$
.◻
We apply Lemma 2.4 with
$T=F-N(P,F)$
,
$C=G-N(P,H)$
(which is a face of
$T$
by (5)),
$z=x$
,
$z_{1}=x+\unicode[STIX]{x1D6E5}_{3}$
and
$z_{2}=y$
, where
$z_{2}-z_{1}=\unicode[STIX]{x1D6E5}_{1}+\unicode[STIX]{x1D6E5}_{2}\in L(C)=L_{1}+L_{2}$
and
$z_{1},z_{2}\in B(x,\unicode[STIX]{x1D700})$
. We conclude that
$\unicode[STIX]{x1D7D9}_{F-N(P,F)}(x+\unicode[STIX]{x1D6E5}_{3})=\unicode[STIX]{x1D7D9}_{F-N(P,F)}(y)$
. This shows that
$\unicode[STIX]{x1D711}_{G,H}(x+\unicode[STIX]{x1D6E5}_{3})=\unicode[STIX]{x1D711}_{G,H}(y)$
whenever
$y\in B(x,\unicode[STIX]{x1D700})$
and
$\unicode[STIX]{x1D700}>0$
is small enough.
Step 6. In order to complete the proof that
$\unicode[STIX]{x1D711}_{G,H}(x+w)$
is independent of
$w\in L_{3}$
provided
$\Vert w\Vert \leqslant \unicode[STIX]{x1D700}$
and
$\unicode[STIX]{x1D700}>0$
is sufficiently small, we need some preparation. Let
$F$
be any face in
$I(G,H)$
. Then we consider the polyhedral cones
$$\begin{eqnarray}\displaystyle F^{\ast } & := & \displaystyle \operatorname{pos}((F-x_{1})\cap L(G)^{\bot })\nonumber\\ \displaystyle & = & \displaystyle \mathop{\bigcup }_{t>0}(t(F-x_{1})\cap L(G)^{\bot })\subset L(F)\cap L(G)^{\bot }\subset L_{3},\nonumber\\ \displaystyle H^{\ast } & := & \displaystyle \operatorname{pos}((H-x_{1})\cap L(G)^{\bot })\subset L_{3}.\nonumber\end{eqnarray}$$
The idea is that we factor
$G$
out and that in a small neighbourhood of
$x_{1}$
, faces look like cones. We claim that
$F^{\ast }$
is a face of the cone
$H^{\ast }$
and, conversely, all faces of
$H^{\ast }$
are of the form
$F^{\ast }$
for some
$F\in I(G,H)$
. Also,
$\dim F^{\ast }=\dim F-\dim G$
,
$\dim H^{\ast }=\dim H-\dim G$
. Let
$N_{L_{3}}(H^{\ast },F^{\ast })$
denote the normal cone of
$H^{\ast }$
at its face
$F^{\ast }$
with respect to
$L_{3}$
as the ambient space.
In order to verify the preceding statements, we put
$$\begin{eqnarray}H^{-}(u,\unicode[STIX]{x1D6FC}):=\{z\in \mathbb{R}^{d}:\langle z,u\rangle \leqslant \unicode[STIX]{x1D6FC}\}\quad \text{and}\quad H(u,\unicode[STIX]{x1D6FC}):=\{z\in \mathbb{R}^{d}:\langle z,u\rangle =\unicode[STIX]{x1D6FC}\},\end{eqnarray}$$
that is
$H(u,\unicode[STIX]{x1D6FC})=\unicode[STIX]{x2202}H^{-}(u,\unicode[STIX]{x1D6FC})$
, for
$u\in \mathbb{R}^{d}\setminus \{0\}$
and
$\unicode[STIX]{x1D6FC}\in \mathbb{R}$
. The polyhedral set
$P$
is given in the form
$$\begin{eqnarray}P=\mathop{\bigcap }_{i=1}^{n}H^{-}(u_{i},\unicode[STIX]{x1D6FC}_{i}),\end{eqnarray}$$
for suitable
$n\in \mathbb{N}$
,
$u_{1},\ldots ,u_{n}\in \mathbb{R}^{d}\setminus \{0\}$
and
$\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{n}\in \mathbb{R}$
, since we can assume that
$P\neq \mathbb{R}^{d}$
and hence
$n\neq 0$
(the case
$P=\mathbb{R}^{d}$
is trivial). In the following, intersections over an empty index set are interpreted as
$\mathbb{R}^{d}$
. Let
$F$
be a face of
$P$
. Then we put
$I_{F}:=\{i\in [n]:F\subset H(u_{i},\unicode[STIX]{x1D6FC}_{i})\}$
,
$J_{F}:=\{j\in [n]:G\subset H(u_{j},\unicode[STIX]{x1D6FC}_{j}),F\not \subset H(u_{j},\unicode[STIX]{x1D6FC}_{j})\}$
, and
$R_{F}:=\{l\in [n]:G\not \subset H(u_{l},\unicode[STIX]{x1D6FC}_{l})\}$
. Then
$$\begin{eqnarray}\displaystyle F^{\ast } & = & \displaystyle \mathop{\bigcup }_{t>0}\biggl[t\biggl(\mathop{\bigcap }_{i\in I_{F}}H(u_{i},\unicode[STIX]{x1D6FC}_{i})\cap \mathop{\bigcap }_{j\in J_{F}}H^{-}(u_{j},\unicode[STIX]{x1D6FC}_{j})\cap \mathop{\bigcap }_{l\in R_{F}}H^{-}(u_{l},\unicode[STIX]{x1D6FC}_{l})-x_{1}\biggr)\nonumber\\ \displaystyle & & \displaystyle \quad \hspace{8.00003pt}\cap \,L(G)^{\bot }\biggr]\nonumber\\ \displaystyle & = & \displaystyle \mathop{\bigcup }_{t>0}\biggl[\mathop{\bigcap }_{i\in I_{F}}H(u_{i},0)\cap \mathop{\bigcap }_{j\in J_{F}}H^{-}(u_{j},0)\cap \mathop{\bigcap }_{l\in R_{F}}H^{-}(u_{l},t(\unicode[STIX]{x1D6FC}_{l}-\langle x_{1},u_{l}\rangle ))\nonumber\\ \displaystyle & & \displaystyle \quad \hspace{8.00003pt}\cap \,L(G)^{\bot }\biggr]\nonumber\\ \displaystyle & = & \displaystyle \!\mathop{\bigcap }_{i\in I_{F}}\!H(u_{i},0)\!\cap \!\mathop{\bigcap }_{j\in J_{F}}\!H^{-}(u_{j},0)\!\cap \mathop{\bigcup }_{t>0}\,\mathop{\bigcap }_{l\in R_{F}}\!H^{-}(u_{l},t(\unicode[STIX]{x1D6FC}_{l}-\langle x_{1},u_{l}\rangle ))\!\cap \!L(G)^{\bot }\nonumber\\ \displaystyle & = & \displaystyle \mathop{\bigcap }_{i\in I_{F}}H(u_{i},0)\cap \mathop{\bigcap }_{j\in J_{F}}H^{-}(u_{j},0)\cap L(G)^{\bot }\nonumber\\ \displaystyle & = & \displaystyle \mathop{\bigcap }_{j\in J_{F}}H^{-}(u_{j},0)\cap L(F)\cap L(G)^{\bot },\nonumber\end{eqnarray}$$
where we used that
$\langle x_{1},u_{i}\rangle =\unicode[STIX]{x1D6FC}_{i}$
for
$i\in I_{F}\cup J_{F}$
and
$\langle x_{1},u_{l}\rangle <\unicode[STIX]{x1D6FC}_{l}$
for
$l\in R_{F}$
. Similarly, we obtain
$$\begin{eqnarray}H^{\ast }=\mathop{\bigcap }_{j\in J_{H}}H^{-}(u_{j},0)\cap L(H)\cap L(G)^{\bot },\end{eqnarray}$$
where
$J_{H}:=\{j\in [n]:G\subset H(u_{j},\unicode[STIX]{x1D6FC}_{j}),H\not \subset H(u_{j},\unicode[STIX]{x1D6FC}_{j})\}$
. Thus,
$J_{F}\subset J_{H}$
and
$F^{\ast }$
is a face of
$H^{\ast }$
which is obtained from
$H^{\ast }$
by turning some of the defining inequalities in (6) into equalities. Conversely, all faces of
$H^{\ast }$
arise in this way.
Lemma 2.5. If
$\unicode[STIX]{x1D700}>0$
is sufficiently small and
$w\in L_{3}$
with
$\Vert w\Vert \leqslant \unicode[STIX]{x1D700}$
, then
$x+w\in F-N(P,F)$
if and only if
$w\in F^{\ast }-N_{L_{3}}(H^{\ast },F^{\ast })$
. Consequently, if
$\unicode[STIX]{x1D700}>0$
is sufficiently small, then
$\unicode[STIX]{x1D711}_{G,H}(x+w)=\unicode[STIX]{x1D711}_{H^{\ast }}(w)$
.
Proof. First, assume that
$x+w\in F-N(P,F)$
. Then there is some
$f\in F$
such that
$-(x_{1}+x_{2}-f+w)\in N(P,F)\subset L(F)^{\bot }$
. Hence
$f\in x_{1}+x_{2}+w+L(F)^{\bot }\subset x_{1}+L(G)^{\bot }$
, since
$L(G)\subset L(F)$
,
$w\in L_{3}\subset L(G)^{\bot }$
, and
$x_{2}\in L(H)^{\bot }\subset L(G)^{\bot }$
. Since also
$f\in x_{1}+L(F)$
, we get
$$\begin{eqnarray}f\in (x_{1}+L(G)^{\bot })\cap (x_{1}+L(F))=x_{1}+(L(G)^{\bot }\cap L(F))\subset x_{1}+L_{3}.\end{eqnarray}$$
We now claim that there is some
$f_{0}\in \operatorname{relint}(F)\cap (x_{1}+L_{3})$
. To see this, we can argue in
$\operatorname{aff}F$
and hence assume that
$\operatorname{aff}F=\mathbb{R}^{d}$
. Suppose that
$(\operatorname{int}F)\cap (x_{1}+L(G)^{\bot })=\varnothing$
. Then there is a hyperplane
$H_{0}$
, bounding the closed halfspaces
$H_{0}^{+},H_{0}^{-}$
such that
$\operatorname{int}F\subset H_{0}^{-}$
and
$x_{1}+L(G)^{\bot }\subset H_{0}^{+}$
. Since
$x_{1}\in G\subset F\subset H_{0}^{-}$
and
$x_{1}\in x_{1}+L(G)^{\bot }\subset H_{0}^{+}$
, we get
$x_{1}\in H_{0}$
and thus
$x_{1}+L(G)^{\bot }\subset H_{0}$
. Moreover,
$x_{1}\in \operatorname{relint}(G)\cap H_{0}$
and
$G\subset F\subset H_{0}^{-}$
imply that also
$G\subset H_{0}$
. Thus we arrive at the contradiction
$d=\dim H_{0}=d-1$
.
Choosing
$f_{0}\in \operatorname{relint}(F)\cap (x_{1}+L_{3})$
, we get
$$\begin{eqnarray}\langle -(x+w-f),p-f_{0}\rangle \leqslant 0,\quad p\in P,\end{eqnarray}$$
since
$-(x-f+w)\in N(P,F)$
. Using that
$x_{2}\in L(H)^{\bot }$
and
$h-f_{0}\in L(H)$
for
$h\in H$
and
$f_{0}\in F\subset H$
, we get
$$\begin{eqnarray}\langle -(x_{1}+w-f),h-f_{0}\rangle =\langle -(x+w-f),h-f_{0}\rangle \leqslant 0\end{eqnarray}$$
for all
$h\in H$
. Thus
$x_{1}+w-f\in -N_{L(H)}(H,F)\cap L_{3}$
, where the lower index indicates the subspace in which the normal cone is considered. Applying [Reference Schneider16, (2.2)] in
$L(H)$
(the polar with respect to
$L(H)$
of a cone
$C\subset L(H)$
is denoted by
$C_{L(H)}^{\circ }$
, and similarly for
$L_{3}$
) and arguing as in the derivation of (6), we obtain
$$\begin{eqnarray}\displaystyle & & \displaystyle N_{L(H)}(H,F)\nonumber\\ \displaystyle & & \displaystyle \quad =\biggl(\mathop{\bigcup }_{t>0}t(H-f_{0})\biggr)_{L(H)}^{\circ }\nonumber\\ \displaystyle & & \displaystyle \quad =\biggl(\bigcap \{H^{-}(u_{i},0)\cap L(H):F\subset H(u_{i},\unicode[STIX]{x1D6FC}_{i}),i\in [n]\}\biggr)_{L(H)}^{\circ }\nonumber\\ \displaystyle & & \displaystyle \quad =\biggl(\!L(G)+\bigcap \{H^{-}(u_{i},0)\cap L(H)\cap L(G)^{\bot }:F\subset H(u_{i},\unicode[STIX]{x1D6FC}_{i}),i\in [n]\}\biggr)_{\!L(H)}^{\circ }\nonumber\\ \displaystyle & & \displaystyle \quad =\biggl(\bigcap \{H^{-}(u_{i},0)\cap L(H)\cap L(G)^{\bot }:F\subset H(u_{i},\unicode[STIX]{x1D6FC}_{i}),i\in [n]\}\biggr)_{L_{3}}^{\circ }\nonumber\\ \displaystyle & & \displaystyle \quad =\biggl(\bigcap \{H^{-}(u_{i},0)\cap L_{3}:F\subset H(u_{i},\unicode[STIX]{x1D6FC}_{i}),i\in [n]\}\biggr)_{L_{3}}^{\circ }\nonumber\\ \displaystyle & & \displaystyle \quad =\biggl(\mathop{\bigcup }_{t>0}t(H^{\ast }-(f_{0}-x_{1}))\biggr)_{L_{3}}^{\circ }\nonumber\\ \displaystyle & & \displaystyle \quad =N_{L_{3}}(H^{\ast },F^{\ast }).\nonumber\end{eqnarray}$$
Thus we conclude that
$x_{1}+w-f\in -N_{L_{3}}(H^{\ast },F^{\ast })$
or
$w\in F^{\ast }-N_{L_{3}}(H^{\ast },F^{\ast })$
. (For this direction, we do not have to assume that
$\Vert w\Vert$
is small.)
Now, we assume that
$w\in F^{\ast }-N_{L_{3}}(H^{\ast },F^{\ast })$
and
$\Vert w\Vert \leqslant \unicode[STIX]{x1D700}$
for a sufficiently small
$\unicode[STIX]{x1D700}>0$
. Then
$w=f^{\ast }-v$
, where
$f^{\ast }\in F^{\ast }$
with
$\Vert f^{\ast }\Vert \leqslant \unicode[STIX]{x1D700}$
and
$v\in N_{L_{3}}(H^{\ast },F^{\ast })$
. Further,
$f^{\ast }=f_{1}^{\ast }-x_{1}$
with
$f_{1}^{\ast }\in (x_{1}+\operatorname{pos}(F-x_{1}))\cap (x_{1}+L_{3})$
. If
$\Vert f^{\ast }\Vert \leqslant \unicode[STIX]{x1D700}$
and
$\unicode[STIX]{x1D700}>0$
is small enough, then
$f_{1}^{\ast }\in F\cap (x_{1}+L_{3})$
, hence we have
$x_{1}+w-f_{1}^{\ast }\in -N_{L_{3}}(H^{\ast },F^{\ast })$
or
$$\begin{eqnarray}\langle -(x_{1}+w-f_{1}^{\ast }),x_{1}+h^{\ast }-(x_{1}+f_{0}^{\ast })\rangle \leqslant 0\end{eqnarray}$$
for
$h^{\ast }\in H^{\ast }$
and any fixed
$f_{0}^{\ast }\in \operatorname{relint}F^{\ast }$
which we choose such that
$x_{1}+f_{0}^{\ast }\in \operatorname{relint}F$
. Thus we get
$$\begin{eqnarray}\langle -(x_{1}+w-f_{1}^{\ast }),h-f_{0}\rangle \leqslant 0\end{eqnarray}$$
for any
$h\in H\cap (x_{1}+L_{3})$
and some (but then also for any)
$f_{0}\in \operatorname{relint}F$
. Since
$x_{1}+w-f_{1}^{\ast }=w-f^{\ast }\in L(G)^{\bot }$
, (7) holds for all
$h\in H$
. Now we put
$W=f_{0}+[-1,1]^{d}$
and consider the polytope
$\bar{P}:=P\cap W$
. Then
$\bar{H}=H\cap W$
and
$\bar{F}=F\cap W$
are faces of
$\bar{P}$
with
$f_{0}\in \operatorname{relint}\bar{F}$
. Since
$-x_{2}\in \operatorname{relint}N(P,H)$
and
$N(P,H)=N(\bar{P},\bar{H})$
(by [Reference Schneider16, Theorem 2.2.1(b)]), it follows that
$\langle -x_{2},h-h_{0}\rangle =0$
for all
$h\in \bar{H}$
and
$\langle -x_{2},p-h_{0}\rangle <0$
for all
$h\in \bar{P}\setminus \bar{H}$
(see [Reference Schneider16, (2.26)]). In particular, writing
$\operatorname{ext}\bar{P}$
for the finite set of vertices (extreme points) of
$\bar{P}$
, we have
$$\begin{eqnarray}\max \{\langle -x_{2},e-f_{0}\rangle :e\in \operatorname{ext}\bar{P}\setminus \bar{H}\}=:\unicode[STIX]{x1D700}_{1}<0,\end{eqnarray}$$
where we used that
$\langle -x_{2},e-f_{0}\rangle =\langle -x_{2},e-h_{0}\rangle$
, since
$\langle -x_{2},f_{0}-h_{0}\rangle =0$
and
$\bar{F}\subset \bar{H}$
. For
$e\in \bar{P}$
, we obtain
$$\begin{eqnarray}|\langle -(x_{1}+w-f_{1}^{\ast }),e-f_{0}\rangle |\leqslant (\Vert w\Vert +\Vert f^{\ast }\Vert )\Vert e-f_{0}\Vert \leqslant 2\unicode[STIX]{x1D700}\sqrt{d}<-\unicode[STIX]{x1D700}_{1},\end{eqnarray}$$
if
$\unicode[STIX]{x1D700}$
is chosen sufficiently small.
If
$e\in \operatorname{ext}\bar{P}\cap \bar{H}$
, then
$$\begin{eqnarray}\displaystyle \langle -(x_{1}+w-f_{1}^{\ast })-x_{2},e-f_{0}\rangle & = & \displaystyle \langle -(x_{1}+w-f_{1}^{\ast }),e-f_{0}\rangle +\langle -x_{2},e-f_{0}\rangle \nonumber\\ \displaystyle & {\leqslant} & \displaystyle 0+0=0.\nonumber\end{eqnarray}$$
If
$e\in \operatorname{ext}\bar{P}\setminus \bar{H}$
, then
$$\begin{eqnarray}\displaystyle \langle -(x_{1}+w-f_{1}^{\ast })-x_{2},e-f_{0}\rangle & = & \displaystyle \langle -(x_{1}+w-f_{1}^{\ast }),e-f_{0}\rangle +\langle -x_{2},e-f_{0}\rangle \nonumber\\ \displaystyle & {\leqslant} & \displaystyle -\unicode[STIX]{x1D700}_{1}+\unicode[STIX]{x1D700}_{1}=0.\nonumber\end{eqnarray}$$
Thus we have
$$\begin{eqnarray}\langle -(x_{1}+w-f_{1}^{\ast }-x_{2}),e-f_{0}\rangle \leqslant 0,\end{eqnarray}$$
first for all
$e\in \operatorname{ext}\bar{P}$
, but then for all
$e\in \bar{P}$
, since for any
$p\in \bar{P}$
there are
$\unicode[STIX]{x1D706}_{e}\geqslant 0$
with
$\sum _{e\in \operatorname{ext}\bar{P}}\unicode[STIX]{x1D706}_{e}=1$
and
$p=\sum _{e\in \operatorname{ext}\bar{P}}\unicode[STIX]{x1D706}_{e}e$
. Hence we have
$\,p-f_{0}=\sum _{e\in \operatorname{ext}\bar{P}}\unicode[STIX]{x1D706}_{e}(e-f_{0})$
, from which the assertion follows.
This shows that
$-(x+w-f_{1}^{\ast })\in N(\bar{P},\bar{F})=N(P,F)$
, and therefore
$x+w\in F-N(P,F)$
.◻
Step 7. Lemma 2.5 reduces the problem to the case of polyhedral cones, i.e. it proves Claim 2.1. To prove Claim 2.2, let
$P$
be a polyhedral cone but not a linear subspace. If
$x=0$
, then
$\unicode[STIX]{x1D711}_{P}(x)=0$
by the classical Euler relation (3). If
$x\neq 0$
, then going through the preceding argument again, we see that we have to show that
$$\begin{eqnarray}\unicode[STIX]{x1D711}_{H^{\ast }}(w)=\mathop{\sum }_{F^{\ast }\in {\mathcal{F}}(H^{\ast })}(-1)^{\dim F^{\ast }}\unicode[STIX]{x1D7D9}_{F^{\ast }-N_{H^{\ast }}(H^{\ast },F^{\ast })}(w)\end{eqnarray}$$
is independent of
$w\in L_{3}$
. But since
$x\neq 0$
,
$G\subset H$
,
$G\neq H$
and
$x\in \operatorname{relint}G-\operatorname{relint}N(P,H)$
, we must have
$\dim G>0$
or
$\dim H<d$
, since otherwise
$0\neq x\in \operatorname{relint}(\{0\})-\operatorname{relint}N(P,P)=\{0\}$
, a contradiction. But then
$\dim H^{\ast }=\dim H-\dim G<d$
, so that the induction hypothesis of Claim 2.2 can be applied.
