# Extensions of Sperner and Tucker’s lemma for manifolds

Oleg R. Musin This research is partially supported by NSF grant DMS - 1101688.

###### Abstract

The Sperner and Tucker lemmas are combinatorial analogous of the Brouwer and
Borsuk - Ulam theorems with many useful applications. These classic lemmas are
concerning labellings of triangulated discs and spheres. In this paper we show
that discs and spheres can be substituted by large classes of manifolds with
or without boundary.

Keywords: Sperner’s lemma, Tucker’s lemma, the Borsuk-Ulam theorem.

##  1 Introduction

Throughout this paper the symbol ${\mathbb{R}}^{d}$ denotes the Euclidean
space of dimension $d$. We denote by ${\mathbb{B}}^{d}$ the $d$-dimensional
ball and by ${\mathbb{S}}^{d}$ the $d$-dimensional sphere. If we consider
${\mathbb{S}}^{d}$ as the set of unit vectors $x$ in ${\mathbb{R}}^{d+1}$,
then points $x$ and $-x$ are called antipodal and the symmetry given by the
mapping $x\to-x$ is called the antipodality on ${\mathbb{S}}^{d}$.

###  1.1 Sperner’s lemma

Sperner’s lemma is a statement about labellings of triangulated simplices
($d$-balls). It is a discrete analog of the Brouwer fixed point theorem.

Figure 1: A 2-dimensional illustration of Sperner’s lemma

Let $S$ be a $d$-dimensional simplex with vertices $v_{1},\ldots,v_{d+1}$. Let
$T$ be a triangulation of $S$. Suppose that each vertex of $T$ is assigned a
unique label from the set $\\{1,2,\ldots,d+1\\}$. A labelling $L$ is called
Sperner’s if the vertices are labelled in such a way that a vertex of $T$
belonging to the interior of a face $F$ of $S$ can only be labelled by $k$ if
$v_{k}$ is on $S$.

######  Theorem 1.1.

(Sperner’s lemma [15]) Every Sperner labelling of a triangulation of a
$d$-dimensional simplex contains a cell labelled with a complete set of
labels: $\\{1,2,\ldots,d+1\\}$.

There are several extensions of this lemma. One of the most interesting is the
De Loera - Petersen - Su theorem. In the paper [4] they proved the Atanassov
conjecture [1].

######  Theorem 1.2.

(Polytopal Sperner’s lemma [4]) Let $P$ be a polytope in ${\mathbb{R}}^{d}$
with vertices $v_{1},\ldots,v_{n}$. Let $T$ be a triangulation of $P$. Let
$L:V(T)\to\\{1,2,\ldots,n\\}$ be a Sperner labelling. Then there are at least
$(n-d)$ fully-colored (i.e. with distinct labels) $d$-simplices of $T$.

Meunier [8] extended this theorem:

######  Theorem 1.3.

Let $P^{d}$ be a $d$-dimensional PL manifold embedded in ${\mathbb{R}}^{d}$
that has bondary $B$. Suppose $B$ has $n$ vertices $v_{1},\ldots,v_{n}$. Let
$T$ be a triangulation of $P$. Let $L:V(T)\to\\{1,2,\ldots,n\\}$ be a Sperner
labelling. Let $d_{i}$ denote the number of edges of $B$ which are connected
to $v_{i}$. Then there are at least $n+\lceil\min_{i}\\{d_{i}\\}/d\rceil-d-1$
fully-labelled $d$-simplices such that any pair of these fully-labelled
simplices receives two different labellings.

###  1.2 Tucker’s lemma

Figure 2: A 2-dimensional illustration of Tucker’s lemma

Let $T$ be some triangulation of the $d$-dimensional ball ${\mathbb{B}}^{d}$.
We call $T$ antipodally symmetric on the boundary if the set of simplices of
$T$ contained in the boundary of ${\mathbb{B}}^{d}={\mathbb{S}}^{d-1}$ is an
antipodally symmetric triangulation of ${\mathbb{S}}^{d-1}$, that is if
$s\subset{\mathbb{S}}^{d-1}$ is a simplex of $T$, then $-s$ is also a simplex
of $T$.

######  Theorem 1.4.

(Tucker’s lemma [16]) Let $T$ be a triangulation of ${\mathbb{B}}^{d}$ that
antipodally symmetric on the boundary. Let

$L:V(T)\to\\{+1,-1,+2,-2,\ldots,+d,-d\\}$

be a labelling of the vertices of $T$ that satisfies $L(-v)=-L(v)$ for every
vertex $v$ on the boundary. Then there exists an edge in $T$ that is
complementary, i.e. its two vertices are labelled by opposite numbers.

Consider also the following version of Tucker’s lemma:

######  Theorem 1.5.

Let $T$ be a centrally symmetric triangulation of the sphere
${\mathbb{S}}^{d}$. Let

$L:V(T)\to\\{+1,-1,+2,-2,\ldots,+d,-d\\}$

be an equivariant (or Tucker’s) labelling, i.e. $L(-v)=-L(v)$). Then there
exists a complementary edge.

Tucker’s lemma was extended by Ky Fan [5]:

######  Theorem 1.6.

Let $T$ be a centrally symmetric triangulation of the sphere
${\mathbb{S}}^{d}$. Suppose that each vertex $v$ of $T$ is assigned a label
$L(v)$ from $\\{\pm 1,\pm 2,\ldots,\pm n\\}$ in such a way that $L(-v)=-L(v)$.
Suppose this labelling does not have complementary edges. Then there are an
odd number of $d$-simplices of $T$ whose labels are of the form
$\\{k_{0},-k_{1},k_{2},\ldots,(-1)^{d}k_{d}\\}$, where $1\leq
k_{0}<k_{1}<\ldots<k_{d}\leq n$. In particular, $n\geq d+1$.

In this paper we consider extensions of the Sperner, De Loera - Petersen - Su,
Tucker and Fan theorems for manifolds. We show that for all cases $d$-balls
and spheres can be substituted by $d$-manifolds with or without boundary.

##  2 Preliminaries

Throughout this paper we consider manifolds that admit triangulations. The
class of such manifolds is called piecewise linear (PL) manifolds. Note that a
smooth manifold can be triangulated, therefore it is also a PL manifold.
However, there are topological manifolds that do not admit a triangulation.

A topological manifold is a topological space that resembles Euclidean space
near each point. More precisely, each point of a $d$-dimensional manifold has
a neighbourhood that is homeomorphic to the Euclidean space of dimension $d$.
A compact manifold without boundary is called closed. If a manifold contains
its own boundary, it is called a manifold with boundary.

Smooth manifolds (also called differentiable manifolds) are manifolds for
which overlapping charts “relate smoothly” to each other, meaning that the
inverse of one followed by the other is an infinitely differentiable map from
Euclidean space to itself.

$M$ is called a piecewise linear (PL) manifold if it is a topological manifold
together with a piecewise linear structure on it. Every PL manifold $M$ admits
a triangulation: that is, we can find a collection of simplices $T$ of
dimensions $0,1,\ldots,d$, such that (1) any face of a simplex belonging to
$T$ also belongs to $T$, (2) any nonempty intersection of any two simplices of
$T$ is a face of each, and (3) the union of the simplices of $T$ is $M$. (See
details in [3].)

Note that the circle is the only one-dimensional closed manifold. Closed
manifolds in two dimensions are completely classified. (See details and proofs
in [14].) An orientable two-manifold (surface) is the sphere or the connected
sum of $g$ tori, for $g\geq 1$. For any positive integer $n$, a distinct
nonorientable surface can be produced by replacing $n$ disks with Möbius
bands. In particular, replacing one disk with a Möbius band produces the real
projective plane and replacing two disks produces the Klein bottle. The
sphere, the $g$-holed tori, and this sequence of nonorientable surfaces form a
complete list of compact, boundaryless two-dimensional manifolds.

Example 2.1. The real projective plane, ${\mathbb{R}P}^{2}$, can be viewed as
the union of a Möbius band and a disc. The correspondent model of the Möbius
band is shown in Fig. 3. Note that this model cannot be embedded to
${\mathbb{R}}^{3}$.

Figure 3: Möbius band. Diametrically opposite points of the inner boundary
circle are to be identified. The outer circle is the boundary of the Möbius
band.

Let $T$ be a triangulation of a PL manifold $M$. Then $T$ is a simplicial
complex. The vertex set of $T$, denoted by $V(T)$ is the union of the vertex
sets of all simplices of $T$.

Given two triangulations $T_{1}$ and $T_{2}$ of two PL manifolds $M_{1}$ and
$M_{2}$. A simplicial map is a function $f:V(T_{1})\to V(T_{2})$ that maps the
vertices of $T_{1}$ to the vertices of $T_{2}$ and that has the property that
for any simplex (face) $s$ of $T_{1}$, the image set $f(s)$ is a face of
$T_{2}$.

Note that the original Brouwer proof of his fixed point theorem that is based
on the concept of the degree of a continuous mapping. Let $f:M_{1}\to M_{2}$
be a continuous map between two closed manifolds $M_{1}$ and $M_{2}$ of the
same dimension. Intuitively, the degree is a number that represents the number
of times that the domain manifold wraps around the range manifold under the
mapping. Then $\operatorname{deg_{2}}2(f)$ (the degree modulo 2) is 1 if this
number is odd and 0 otherwise.

It is well known that the degree of a continuous map $f$ of a closed manifold
to a manifold is a topological invariant modulo 2 (see, for instance, [10] and
[7, pp. 44–46]). Therefore, the degree of $f$ is odd if any generic point in
the range of the map has an odd number of preimages.

Now we define $\operatorname{deg_{2}}2(f)$ more rigorously. Let $T_{1}$ be a
triangulation of a closed $d$-dimensional PL manifold $M_{1}$. Suppose that
$T_{2}$ is a triangulation of a $d$-dimensional PL manifold $M_{2}$. (We do
not assume that $M_{2}$ is closed.) Let $f:V(T_{1})\to V(T_{2})$ be a
simplicial map. Consider any $d$-simplex $s$ of $T_{2}$. Denote by $m$ the
number of preimages of $s$ in $T_{1}$. Then $\operatorname{deg_{2}}2(f)=1$ if
$m$ is odd and $\operatorname{deg_{2}}2(f)=0$ if $m$ is even. Since the parity
of $m$ does not depend on $s$, the degree of map modulo 2 is well defined.
Thus, the degree of a continuous map of a closed manifold to a manifold is a
topological invariant modulo 2.

Let $f:M_{1}\to M_{2}$ be a continuous map between two manifolds $M_{i}$ with
$d_{1}:=\dim(M_{1})\geq d_{2}:=\dim(M_{2})$. Then for a point $y\in M_{2}$ the
map $f$ is called transversal to $y$ (or generic with respect to $y$) if there
are open sets $U_{i}\subset M_{i}$ such that $U_{2}$ contains $y$,
$U_{2}=f(U_{1})$ and $U_{1}=f^{-1}(U_{2})$. In the case
$M_{2}={\mathbb{R}}^{d_{2}}$ and $y=0$, where $0$ is the origin of
${\mathbb{R}}^{d_{2}}$, $f$ is called transversal to zero.

Let $M$ be a closed PL-manifold. A simplicial map $A:M\to M$ is called a free
involution if $A(A(x))=x$ and $A(x)\neq x$ for all $x\in M$. A triangulation
$T$ of $M$ is called antipodal or equivariant if $A:T\to T$ is a simplicial
map. Let us call a pair $(M,A)$, where $A$ is a free simplicial involution as
${\mathbb{Z}}_{2}$-manifold.

Example 2.2. It is clear that $({\mathbb{S}}^{d},A)$ with $A(x)=-x$ is a
${\mathbb{Z}}_{2}$-manifold. Suppose that $M$ can be represented as a
connected sum $N\\#N$, where $N$ is a closed PL manifold. Then admits a free
involution. Indeed, $M$ can be “centrally symmetric” embedded to
${\mathbb{R}}^{k}$ with some $k$ and the antipodal symmetry $x\to-x$ in
${\mathbb{R}}^{k}$ implies a free involution $T:M\to M$ [12, Corollary 1]. For
instance, orientable two-dimensional manifolds $M^{2}_{g}$ with even genus $g$
and non-orientable manifolds $P^{2}_{m}$ with even $m$, where $m$ is the
number of Möbius bands, are ${\mathbb{Z}}_{2}$-manifolds.

Figure 4: The double torus that is centrally symmetric embedded to
${\mathbb{R}}^{3}$.

Suppose that $M$ admits a free simplicial involution $A$. We say that a map
$f:M\to{\mathbb{R}}^{d}$ is antipodal (or equivariant) if $f(A(x))=-f(x)$.

##  3 Extensions of Sperner’s lemma for manifolds

A $d$-simplex $S$ where each corner is labelled between 1 and $d+1$ such that
all labels are used exactly once is called fully labelled. Suppose that points
are added in $S$, then it may be triangulated, i.e. subdivided into smaller
$d$-simplices such that none of the smaller simplices contain any points: all
the points are corners of smaller simplices. This subdivision may be done in
many ways.

Now label all the interior points according to the following rule: an interior
point that is on a facet of the simplex must be given one of the labels of one
of the corners of that facet. The result is called a Sperner labelling.

Note that in this definition an interior point of $S$ can be labelled by any
label. So Sperner’s constraint is only for the boundary of $S$ that is
homeomorphic to ${\mathbb{S}}^{d-1}$. Let us extend this definition to any
closed manifold.

Definition. Let $K$ be a closed $m$-dimensional PL manifold with vertices
$V=\\{v_{1},\ldots,v_{n}\\}$ and faces $\\{F_{i}\\}$ of dimension from 1 to
$m$. Let $T$ be a triangulation of $K$ such that for any face (that is a
simplex) $F_{i}$ it is a triangulation of $F_{i}$. Suppose that the vertices
of $T$ have a labelling satisfying the following conditions: each vertex
$v_{k}$ of $V$ is assigned a unique label from $\\{1,2,\ldots,n\\}$, and each
other vertex $v$ of $T$ belonging to a face $F_{i}$ with vertices
$V(F_{i}):=\\{v_{i_{1}},\ldots,v_{i_{\ell}}\\}$ from $V$ is assigned a label
of one of the vertices of $V(F_{i})$. Such a labelling is called a Sperner
labelling of $T$.

Definition. We say that a $d$-simplex is a fully labelled cell or simply a
full cell if all its labels are are distinct.

Let $T$ be a triangulation of a $d$-dimensional PL manifold. Let
$L:V(T)\to\\{1,\ldots,n\\}$ be a labelling of $T$. Let $Q$ be a set of
$(d+1)$-subsets of $\\{1,\ldots,n\\}$. We denote by $\mathop{\rm
fc}\nolimits(L,T,Q)$ the number of fully labelled cells that are labelled as
labels in $Q$. In the case $n=d+1$ we denote $\mathop{\rm
fc}\nolimits(L,T):=\mathop{\rm fc}\nolimits(L,T,\\{1,\ldots,d+1\\})$.

Let $P$ be a set of $n$ points $p_{1},\ldots,p_{n}$ in ${\mathbb{R}}^{d}$.
Denote by $S(P)$ the collection of all simplices spanned by vertices
$\\{p_{i_{1}},\ldots,p_{i_{k}}\\}$ with $1\leq k\leq d+1$. Consider a point
$x\in{\mathbb{R}}^{d}$ and the set $S_{x}(P)$ of all simplices from $S(P)$
which cover $x$. If no such simplices exist, we write $S_{x}(P)=\emptyset$.
Denote this set of simplices by $\mathop{\rm cov}\nolimits_{P}(x)$ or just by
$\mathop{\rm cov}\nolimits(x)$.

Example 3.1. Let $P$ be a pentagon, see Fig. 5. Then

$\mathop{\rm cov}\nolimits(p_{1})=(123)\cup(124)\cup(125);\;\mathop{\rm
cov}\nolimits(p_{2})=(135)\cup(145)\cup(235)\cup(245);\;$ $\mathop{\rm
cov}\nolimits(p_{3})=(134)\cup(234)\cup(345);\;\mathop{\rm
cov}\nolimits(O)=(124)\cup(134)\cup(135)\cup(235)\cup(245);\;$

Figure 5: Pebbles and $\mathop{\rm cov}\nolimits(x)$ for a pentagon

Definition. Let $P:=\\{p_{1},\ldots,p_{n}\\}$ be points in ${\mathbb{R}}^{d}$.
Let $T$ be a triangulation of a closed PL manifold $M$ of dimension $m$. Let
$L$ be an $n$-labelling of $T$, i.e. a labelling (map)
$L:V(T)\to\\{1,2,\ldots,n\\}$. If for $v\in V(T)$ we have $L(v)=i$, then set
$f_{L,P}(v):=p_{i}$. Therefore, $f_{L,P}$ is defined for all vertices of $T$,
and it uniquely defines a simplicial (piecewise linear) map
$f_{L,P}:M\to{\mathbb{R}}^{d}$.

######  Theorem 3.1.

Let $P:=\\{p_{1},\ldots,p_{n}\\}\subset{\mathbb{R}}^{d}$. Suppose
$x\in{\mathbb{R}}^{d}$ is such that $\mathop{\rm cov}\nolimits_{P}(x)$
consists of $d$-simplices. Let $M$ be a a closed PL $d$-dimensional manifold.
Then any $n$-labelling $L$ of a triangulation $T$ of $M$ must contain an even
number of full cells which are labelled as simplices in $\mathop{\rm
cov}\nolimits_{P}(x)$.

###### Proof.

Consider $f_{L,P}:T\to{\mathbb{R}}^{d}$. It is easy to see that
$\operatorname{deg_{2}}2(f_{L,P})=0$. Indeed, if $y\in{\mathbb{R}}^{d}$ lies
outside of the convex hull of $P$ in ${\mathbb{R}}^{d}$, then
$f^{-1}_{L,P}(y)=\emptyset$. Therefore, for any point $x$ in
${\mathbb{R}}^{d}$ which is a regular value of $f_{L,P}$, we have
$|f^{-1}_{L,P}(x)|\equiv|f^{-1}_{L,P}(y)|\equiv 0\pmod{2}$. Thus, the number
of full cells which are labelled as simplices in $\mathop{\rm
cov}\nolimits_{P}(x)$ is even. ∎

For the classical case $n=d+1$ we have the following result (also see [6]):

######  Corollary 3.1.

Let $T$ be a triangulation of a closed PL manifold $M^{d}$. Any
$(d+1)$-labelling of $T$ must contain an even number of full cells.

######  Corollary 3.2.

Let $M$ be a $d$-dimensional compact PL manifold with boundary $B$. Let $B$ be
PL homeomorphic to the boundary of a $d$-simplex (i.e.
$B\cong{\mathbb{S}}^{d-1}$) with vertices $v_{1},\ldots,v_{d+1}$. Then any
$(d+1)$-labelling $L$ of a triangulation $T$ of $M$ such that $L(v_{i})=i$ and
$L$ is a Sperner labelling on the boundary $B$ must contain an odd number of
full cells.

Figure 6: Sperner’s lemma for the Möbius band

###### Proof.

We prove this corollary by induction on $d$. It is clear for $d=1$. Let $S$
denote a $d$-simplex. Two manifolds $M$ and $S$ can be glued together along
$B$. We denote the new manifold by $N$. Then $N$ is a closed manifold.
Corollary 3.1 implies that any $(d+1)$-labelling of any triangulation of $N$
has an even number of full cells.

Let us add to the vertices of $T$ one more vertex $q$ that is an internal
point of $S$. Let $C=$cone$(T|_{B})$ be the cone triangulation of $S$ with
vertex $q$. (Here $T|_{B}$ denote the triangulation $T$ on $B$.) Actually, $C$
consists of simplices formed by the union of all segments connecting the
points of $B$ with $q$ and the boundary triangulation $T|_{B}$. Then we obtain
the triangulation $\tilde{T}:=T\cup C$ of $N$.

Consider the following labelling $\tilde{L}$ on $\tilde{T}$. Let
$\tilde{L}(v):=L(v)$ for all $v\in V(T)$ and $\tilde{L}(q):=1$. Since
$\tilde{T}$ is a triangulation of $N$, we have that the number of full cells
$\mathop{\rm fc}\nolimits(\tilde{L},\tilde{T})$ is even.

By induction the face $F=v_{2}\ldots v_{d+1}$ of $B$ has an odd number of full
cells. Then $\mathop{\rm fc}\nolimits(\tilde{L},C)=\mathop{\rm
fc}\nolimits(L,T|_{F},\\{2,\ldots,d+1\\})$ is odd. Note that

$\mathop{\rm fc}\nolimits(\tilde{L},\tilde{T})=\mathop{\rm
fc}\nolimits(L,T)+\mathop{\rm fc}\nolimits(\tilde{L},C).$

Thus $T$ must contain an odd number of full cells. ∎

Note that for the case when $M$ is a $d$-simplex Corollary 3.2 is Sperner’s
lemma.

Now we show how the De Loera - Peterson - Su theorem follows from Theorem 3.1.

######  Corollary 3.3.

Let $P$ be a convex polytope in ${\mathbb{R}}^{d}$ with vertices
$p_{1},\ldots,p_{n}$. Let $M$ be a compact $d$-dimensional PL manifold with
boundary $B$. Let $B$ be piecewise linearly homeomorphic to the boundary of
$P$. Suppose $x\in{\mathbb{R}}^{d}$ is such that $\mathop{\rm
cov}\nolimits_{P}(x)$ consists of $d$-simplices. Then any $n$-labelling $L$ of
a triangulation $T$ of $M$ that is a Sperner labelling on the boundary must
contain an odd number of full cells which are labelled as simplices in
$\mathop{\rm cov}\nolimits_{P}(x)$. In other words, $\mathop{\rm
fc}\nolimits(L,T,\mathop{\rm cov}\nolimits(x))$ is odd.

###### Proof.

This corollary can be proved by similar arguments as Corollary 3.2. Indeed,
two manifolds $M$ and $P$ can be glued together along $B$. We denote the new
manifold by $N$. Then $N$ is a closed manifold.

Let $C:=$cone$(T|_{B})$ be the cone triangulation of $P$ with vertex $q$,
where $q$ is an internal point of $P$. Then we have the triangulation
$\tilde{T}:=T\cup C$ of $N$.

Consider the following labelling $\tilde{L}$ on $\tilde{T}$. Let
$\tilde{L}(v):=L(v)$ for all $v\in V(T)$ and $\tilde{L}(q):=1$. Now we show
that $\mathop{\rm fc}\nolimits(\tilde{L},C,\mathop{\rm cov}\nolimits(x))$ is
odd.

Consider the line in ${\mathbb{R}}^{d}$ passes through points $p_{1}$ and $x$.
By assumptions, this line intersects the boundary $B$ of the polytope $P$ in
two points $p_{1}$ and $y$, where $y$ is an internal point of some
$(d-1)$-simplex of $T|_{B}$ with distinct labels $\ell_{1},\ldots,\ell_{d}$.
Therefore, $y$ lies on the face $F=v_{\ell_{1}}\ldots v_{\ell_{d}}$. By
induction $\mathop{\rm fc}\nolimits(L,T|_{F},\\{\ell_{1},\ldots,\ell_{d})$ is
odd. Note that $\tilde{L}$ on $C$ contains only one labelling
$(1\ell_{1}\ldots\ell_{d})$ from $\mathop{\rm cov}\nolimits(x)$. Then

$\mathop{\rm fc}\nolimits(\tilde{L},C,\mathop{\rm
cov}\nolimits(x))=\mathop{\rm
fc}\nolimits(\tilde{L},C,\\{1,\ell_{1},\ldots,\ell_{d}\\})=\mathop{\rm
fc}\nolimits(L,T|_{F},\\{\ell_{1},\ldots,\ell_{d}\\})=1\mathop{\rm(mod}\nolimits
2).$

We have

$\mathop{\rm fc}\nolimits(\tilde{L},\tilde{T},\mathop{\rm
cov}\nolimits(x))=\mathop{\rm fc}\nolimits(L,T,\mathop{\rm
cov}\nolimits(x))+\mathop{\rm fc}\nolimits(\tilde{L},C,\mathop{\rm
cov}\nolimits(x)),$

where $\mathop{\rm fc}\nolimits(\tilde{L},\tilde{T},\mathop{\rm
cov}\nolimits(x))$ is even and $\mathop{\rm
fc}\nolimits(\tilde{L},C,\mathop{\rm cov}\nolimits(x))$ is odd. Thus
$\mathop{\rm fc}\nolimits(L,T,\mathop{\rm cov}\nolimits(x))$ is odd. ∎

######  Corollary 3.4.

Let $P$ be a convex polytope in ${\mathbb{R}}^{d}$ with vertices
$p_{1},\ldots,p_{n}$. Let $M$ be a compact $d$-dimensional PL manifold with
boundary $B$. Let $B$ be PL homeomorphic to the boundary of $P$. Then any
$n$-labelling of a triangulation of $M$ that is a Sperner labelling on the
boundary contains at least $n-d$ full cells.

For the case $M=P$ this statement is the polytopal Sperner lemma [4, Th. 1].

###### Proof.

A proof of this corollary follows from another theorem from [4, Th. 4]: Any
convex polytope $P$ in ${\mathbb{R}}^{d}$ with $n$ vertices contains a pebble
set of size $n-d$. (A finite set of points (pebbles) in $P$ is called a pebble
set if each $d$-simplex of $P$ contains at most one pebble interior to
chambers.)

Consider a pebble set $\\{p_{i}\\}$ of size $n-d$. Then for $i\neq j$ we have
$\mathop{\rm cov}\nolimits(p_{i})\cap\mathop{\rm
cov}\nolimits(p_{j})=\emptyset$. Thus Corollary 3.3 guarantees that there are
at least $n-d$ full cells. ∎

Remark. In fact, Meunier’s proof of his extension of the polytopal Sperner
lemma (De Loera - Peterson - Su’s theorem) is not based on the “pebbles set
theorem.” It is an interesting problem to find an extension of Meunier’s
theorem for manifolds.

Example 3.2. Consider the case when $P$ is a pentagon. In $P$ there are three
pebbles $p_{1},p_{2},p_{3}$, see Fig. 5. So the polytopal Sperner’s lemma
(Theorem 1.2) and Corollary 3.4 implies that there are at least three fully
labelled triangles. Actually, this statement can be improved.

Note that there are 10 5-labellings for triangles. Five of them are
consecutive: (123), (234), (345), (451), (512) and five are non-consecutive.
In fact, $\mathop{\rm cov}\nolimits(O)$ consists of non-consecutive
labellings, see Example 3.1. Then Corollary 3.3 implies the following
statement:
Any Sperner 5-labelling of a triangulation $T$ of a pentagon $P$ must contain
at least three full cells. Moreover, at least one of them is not consecutive
labelled.

##  4 Extensions of Tucker’s lemma for manifolds

Definition.  Let $M$ be a closed PL $d$-dimensional manifold with a free
simplicial involution $A:M\to M$. We say that a pair $(M,A)$ is a BUT (Borsuk-
Ulam Type) manifold if for any continuous $g:M\to{\mathbb{R}}^{d}$ there is a
point $x\in M$ such that $g(A(x))=g(x)$. Equivalently, if a continuous map
$f:M\to{\mathbb{R}}^{d}$ is antipodal, then the zeros set $Z_{f}:=f^{-1}(0)$
is not empty.

In [12], we found several equivalent necessary and sufficient conditions for
manifolds to be BUT. For instance, $M$ is a BUT manifold if and only if $M$
admits an antipodal continuous transversal to zeros map
$h:M\to{\mathbb{R}}^{d}$ with $|Z_{h}|=2\pmod{4}$.

Let $T$ be any equivariant triangulation of $M$. We say that

$L:V(T)\to\\{+1,-1,+2,-2,\ldots,+d,-d\\}$

is an equivariant (or Tucker’s) labelling if $L(A(v))=-L(v)$).

An edge $e$ in $T$ is called complementary if its two ends are labelled by
opposite numbers, i.e. if $e=uv$, then $L(v)=-L(u)$.

######  Theorem 4.1.

A closed PL $d$-dimensional manifold $M$ with a free simplicial involution $A$
is BUT if and only if for any equivariant labelling of any equivariant
triangulation $T$ of $M$ there exists a complementary edge.

For the case $M={\mathbb{S}}^{d}$ this is Tucker’s lemma.

###### Proof.

Let $e_{1},\ldots,e_{d}$ be an orthonormal basis of ${\mathbb{R}}^{d}$. Any
equivariant labelling $L$ of a triangulation $T$ of $M$ defines a simplicial
map $f_{L}:T\to C^{d}$, where $C^{d}$ is the crosspolytope in
${\mathbb{R}}^{d}$ with vertex set
$\\{e_{1},-e_{1},e_{2},-e_{2},\ldots,e_{d},-e_{d}\\}$, where for $v\in V(T)$,
$f_{L}(v)=e_{i}$ if $L(v)=i$ and $f_{L}(v)=-e_{i}$ if $L(v)=-i$. (See details
in [7, Sec. 2.3].) In other words, $f_{L}=f_{L,C^{d}}$ (see Section 3).

Note that any fully labelled simplex contains a complementary edge. Therefore,
if $L$ has no complementary edges, then $f_{L}:T\to{\mathbb{R}}^{d}$ has no
zeros.

The reverse implication can be proved by the same arguments as equivalence of
the Borsuk-Ulam theorem and Tucker’s lemma in [7, 2.3.2], i.e. if there is
continuous antipodal map $f:M\to{\mathbb{S}}^{d-1}$ (i.e. $Z_{f}=\emptyset$)
then $T$ and $L$ can be constructed with no complementary edges. (See also
Theorem 4.2.) ∎

Theorem 4.1 and [12, Theorem 2] immediately imply:

######  Corollary 4.1.

Let $M$ be a closed PL manifold with a free involution $A$. Then $M$ is a BUT
manifold if and only if there exist an equivariant triangulation $\Lambda$ of
$M$ and an equivariant labelling of $V(\Lambda)$ such that
$f_{L}:\Lambda\to{\mathbb{R}}^{d}$ is transversal to zeros and the number of
complementary edges is $4k+2$, where $k$ is integer.

######  Corollary 4.2.

Let $T$ be a triangulation of a PL-compact $d$-dimensional manifold $M$ with
boundary $B$ that is homeomorphic to ${\mathbb{S}}^{d-1}$. Assume $T$ is
antipodally symmetric on the boundary. Let
$L:V(T)\to\\{+1,-1,+2,-2,\ldots,+d,-d\\}$ be a labelling of the vertices of
$T$ which satisfies $L(-v)=-L(v)$ for all vertices $v$ in $B$. Then there is a
complementary edge in $T$.

###### Proof.

Consider two copies of $M$: $M_{+}$ and $M_{-}$, where for $M_{+}$ we take a
given labelling $L$ and for $M_{-}$ we take a labelling $\bar{L}=(-L)$, i.e.
$\bar{L}(v)=-L(v)$. Since $L$ is antipodal on the boundary
$B={\mathbb{S}}^{d-1}$ the connected sum $N:=M\\#M$ with a free involution
$I:N\to N$, where $I(M_{+})=M_{-}$, is well defined. [12, Corollary 1] implies
that $N$ is BUT. Thus, from Theorem 4.1 follows that there is a complementary
edge. ∎

Figure 7: Tucker’s lemma for the Möbius band

Now we extend Theorem 4.1 for $n$-labellings.

######  Theorem 4.2.

Let $P=\\{p_{1},-p_{1},\ldots,p_{n},-p_{n}\\}$ be a centrally symmetric set of
$2n$ points in ${\mathbb{R}}^{d}$. Let points in $P$ be equivariantly labelled
by $\\{+1,-1,+2,-2,\ldots,+n,-n\\}$. Let $M$ be a closed PL $d$-dimensional
manifold with a free involution. Then $M$ is a BUT manifold if and only if for
any equivariant triangulation $T$ of $M$ and for any equivariant labelling
$L:V(T)\to\\{+1,-1,+2,-2,\ldots,+n,-n\\}$ there exists a simplex $s$ in $T$
such that $0\in f_{L,P}(s)$.

###### Proof.

If $M$ is BUT, then $f_{L,P}$ has zeros, so there is a simplex $s$ as
required.

Suppose $M$ is not BUT. Then there is a continuous antipodal
$h:M\to{\mathbb{S}}^{d-1}$. Let $T$ be an equivariant triangulation of $M$.
Let $Q$ denote the boundary of the convex hull of $P$ in ${\mathbb{R}}^{d}$.
Without loss of generality we may assume that $h:M\to Q$ and for any vertex
$v\in V(T)$ the image $f(v)$ has only one closest vertex $p$ in $Q$. Then set
$L(v):=L(p)$. This labelling implies that $f_{L,P}$ is an antipodal simplicial
map from $T$ to $Q$. Thus, $0$ in ${\mathbb{R}}^{d}$ is not covered by
$f_{L,P}$, a contradiction. ∎

##  5 Radon partitions and Ky Fan’s lemma for manifolds

In this section we show that Ky Fan’s lemma follows from Theorem 4.2.

Radon’s theorem on convex sets states that any set $S$ of $d+2$ points in
${\mathbb{R}}^{d}$ can be partitioned into two (disjoint) sets $A$ and $B$
whose convex hulls intersect. Moreover, if rank$(S)=d$, then this partition is
unique.

The partition $S=A\bigcup B$ is called the Radon partition of $S$.

Breen [2] proved that if $S$ is a $(d+2)$-subset of the moment curve $C_{d}$
in ${\mathbb{R}}^{d}$, then $S=A\bigcup B$ is the Radon partition if and only
if $A$ and $B$ alternate along $C_{d}$. Actually, Breen’s theorem can be
extended for convex curves in ${\mathbb{R}}^{d}$.

We say that a curve $K$ in $\mathbb{R}^{d}$ is convex if for every hyperplane
$K$ intersects it at no more than $d$ points. It is well known that the moment
curve $C_{d}$ is convex. In [11, Sec. 3] we considered several other examples
of convex curves.

Definition. Let $K=\\{x(t)=(x_{1}(t),\ldots,x_{d}(t)):t\in[a,b]\\}$ be a curve
in $\mathbb{R}^{d}$. Let $S=\\{x(t_{1}),\ldots,x(t_{d+2})\\}$, where
$a<t_{1}<t_{2}<\ldots<t_{d+2}<b$. We say that $A$ and $B$ alternate along $K$
if $S=A\bigcup B$, where $A=\\{x(t_{1}),x(t_{3}),\ldots\\}$ and
$B=\\{x(t_{2}),x(t_{4}),\ldots\\}$.

######  Theorem 5.1.

A curve $K$ in $\mathbb{R}^{d}$ is convex if and only if for any
$(d+2)$-subset $S$ of $K$ its Radon partition sets $A$ and $B$ alternate along
$K$.

###### Proof.

Let $K$ be convex and $S=\\{x(t_{1}),\ldots,x(t_{d+2})\\}$ be a $(d+2)$-subset
of $K$. Let $A\bigcap B$ be the Radon partition of $S$. If $A$ and $B$ do not
alternate along $K$, there are at most $d$ points $P=\\{x(\tau_{i})\\}$ which
separate $A$ and $B$ on $K$. If $r=|P|<d$, we add to $P$ $d-r$ points
$x(\tau)$ with $\tau\in(a,t_{1})$. Then $P$ defines a hyperplane $H$ which
passes through the points in $P$. Clearly, $H$ separates $A$ and $B$ in
$\mathbb{R}^{d}$. Thus, $A\bigcap B$ cannot be the Radon partition of $S$, a
contradiction.

Suppose that for any $(d+2)$-subset $S$ of $K$, its Radon partition sets $A$
and $B$ alternate along $K$. If $K$ is not convex, then there is a hyperplane
$H$ which intersects $K$ at $r\geq d+1$ points. Therefore, $H$ separates $K$
into $r+1$ connected components $C_{1},\ldots,C_{r+1}$. Let
$S=\\{x(t_{1}),\ldots,x(t_{d+2})\\}$, where $x(t_{i})\in C_{i}$. Since $A$ and
$B$ which alternate along $K$ are separated by $H$, the partition $S=A\bigcup
B$ is not Radon’s - a contradiction. ∎

Definition. Let $P$ be a convex polytope in $\mathbb{R}^{d}$ with $2n$
centrally symmetric vertices $\\{p_{1},-p_{1},\ldots,p_{n},-p_{n}\\}$. We say
that $P$ is ACS (Alternating Centrally Symmetric) $(n,d)$-polytope if the set
of all simplices in $\mathop{\rm cov}\nolimits_{P}(0)$, that contain the
origin $0$ of $\mathbb{R}^{d}$ inside, consists of edges $(p_{i},-p_{i})$ and
$d$-simplices with vertices {$p_{k_{0}},-p_{k_{1}},\ldots,(-1)^{d}p_{k_{d}}$}
and {$-p_{k_{0}},p_{k_{1}},\ldots,(-1)^{d+1}p_{k_{d}}$}, where $1\leq
k_{0}<k_{1}<\ldots<k_{d}\leq n$.

######  Theorem 5.2.

For any integer $d\geq 2$ and $n\geq d$ there exists ASC $(n,d)$-polytope.

###### Proof.

Let $q_{1},\ldots,q_{n}$ be points on a convex curve $K$ in
$\mathbb{R}^{d-1}$. Let $p_{i}=(q_{i},1)\in\mathbb{R}^{d}$. Denote by $P(n,d)$
a convex polytope with vertices $\\{p_{1},-p_{1},\ldots,p_{n},-p_{n}\\}$.
Clearly, $0\in(-p_{i},p_{i})$. Let $\Delta$ be a simplex spaned by vertices of
$P(n,d)$. Let $V(\Delta)=A\bigcup(-B)$, where $A$ and $B$ are vertices with
$x_{d}=1$. It is easy to see that $0\in\Delta$ if and only if $\mathop{\rm
conv}\nolimits(A)\bigcap\mathop{\rm conv}\nolimits(B)=\emptyset$, i.e.
$S=A\bigcup B$ is the Radon partition of $S$. Then Theorem 5.1 implies that
$A$ and $B$ alternate along $K$. Thus, $P(n,d)$ is an ASC $(n,d)$-polytope. ∎

Let $P$ be an ASC $(n,d)$-polytope. If we apply Theorem 4.2 for $P$, then we
obtain the following theorem.

######  Theorem 5.3.

Let $M$ be a BUT $d$-dimensional manifold with a free involution $A$. Let $T$
be any equivariant triangulation of $M$. Let
$L:V(T)\to\\{+1,-1,+2,-2,\ldots,+n,-n\\}$ be an equivariant labelling. Suppose
that there are no complementary edges in $T$. Then there are an odd number of
$d$-simplices with labels in the form
$\\{k_{0},-k_{1},k_{2},\ldots,(-1)^{d}k_{d}\\}$, where $1\leq
k_{0}<k_{1}<\ldots<k_{d}\leq n$.

For the case $M={\mathbb{S}}^{d}$ this theorem is Ky Fan’s combinatorial lemma
[5]. Actually, it is a new proof of this lemma.

##  6 Sperner and Tucker’s type lemmas for the case $m\geq d$

Now we consider extensions of the polytopal Sperner and Tucker lemmas for the
case when $d\leq\dim{M}=m$. In this case, the set of fully-colored
$d$-simplices defines certain $(m-d)$-submanifold $S$ of $M$. A natural
extension of Theorem 3.1 is that $S$ is cobordant to zero. We also consider an
extension of the Tucker lemma.

An $m$-dimensional manifold $M$ is called null-cobordant (or cobordant to
zero) if there is a cobordism between $M$ and the empty manifold; in other
words, if $M$ is the entire boundary of some $(m+1)$-manifold. Equivalently,
its cobordism class is trivial.

######  Theorem 6.1.

Let $P=\\{p_{1},\ldots,p_{n}\\}$ be a set of points in ${\mathbb{R}}^{d}$.
Suppose $y\in{\mathbb{R}}^{d}$ is such that $\mathop{\rm cov}\nolimits_{P}(y)$
consists of $d$-simplices. Let $M$ be a a closed PL $m$-dimensional manifold
with $m\geq d$. Then for any $n$-labelling $L$ of a triangulation $T$ of $M$
the set $S:=f_{L,P}^{-1}(y)$ is a null-cobordant manifold of dimension $d-m$.

Note that for $d=m$ this theorem yields Theorem 3.1. In this case $S$ consists
of even number of points.

###### Proof.

Let

$W:=M\times[0,1],\;M_{0}:=M\times\\{0\\}\mbox{ and }M_{1}:=M\times\\{1\\}.$

Let $f_{0}:=f_{L,P}:M_{0}\to{\mathbb{R}}^{d}$. Let us fix a point $q\neq y$ in
${\mathbb{R}}^{d}$ and set $f_{1}(x)=q$ for all $x\in M_{1}$.

Note that $f_{0}$ is transversal to $y$ and $f_{1}^{-1}(y)$ is empty. Let

$F(x,t):=(1-t)f_{0}(x)+tf_{1}(x)$

Then $F:W\to{\mathbb{R}}^{d}$ is transversal to $y$ with $F|_{M_{0}}=f_{0}$
and $F|_{M_{1}}=f_{1}$. Therefore, $Z_{F}:=F^{-1}(y)$ is a manifold of
dimension $(m+1-d)$.

Denote $Z_{i}:=Z_{F}\bigcap M_{i}=f_{i}^{-1}(y),\,i=0,1.$ It is clear that
$Z_{0}=S$ and $Z_{1}$ is empty. Thus, $Z_{0}$ is the boundary of $Z_{F}$ and
so it is a null-cobordant $(m-d)$-dimensional manifold. ∎

Now we extend the class of BUT manifolds.

Definition.  We say that a closed PL-free $m$-dimensional
${\mathbb{Z}}_{2}$-manifold $(M,A)$ is a $\mathop{\rm BUT}\nolimits_{m,d}$ if
for any continuous $g:M\to{\mathbb{R}}^{d}$ there is a point $x\in M$ such
that $g(A(x))=g(x)$. Equivalently, if a continuous map
$f:M\to{\mathbb{R}}^{d}$ is antipodal, then the zeros set $Z_{f}:=f^{-1}(0)$
is not empty.

We obviously have

$\mathop{\rm BUT}\nolimits=\mathop{\rm BUT}\nolimits_{m,m}\subset\mathop{\rm
BUT}\nolimits_{m,m-1}\subset\ldots\subset\mathop{\rm BUT}\nolimits_{m,1}.$

Note that in our paper [12] we found a sufficient condition for $(M,\Lambda)$
to be a BUTm,d, see [12, Corollary 3].

Let $T$ be an antipodal triangulation of $M$ Any equivariant labelling
$L:V(T)\to\\{+1,-1,+2,-2,\ldots,+d,-d\\}$ defines a simplicial map $f_{L}:T\to
C^{d}$, where $C^{d}$ is the crosspolytope in ${\mathbb{R}}^{d}$ (see Section
4). It is easy to see that if $L$ has no complementary edges, then
$f_{L}:T\to{\mathbb{R}}^{d}$ has no zeros. It implies the following theorem.

######  Theorem 6.2.

Let $m\geq d$. Let $T$ be any equivariant triangulation of a $\mathop{\rm
BUT}\nolimits_{m,d}$ manifold $(M,A)$. Let
$L:V(A)\to\\{+1,-1,+2,-2,\ldots,+d,-d\\}$ be any equivariant labelling of $T$.
Then there exists a complementary edge in $T$.

This theorem is an extension of Theorem 4.1. When $m\geq d$, it is not hard to
extend other theorems and corollaries from Sections 4 and 5.

Acknowledgment. I wish to thank Arseniy Akopyan and Frédéric Meunier for
helpful discussions and comments.

## References

  * [1] K. T. Atanassov, On Sperner’s lemma, Studia Sci. Math. Hungar., 32 (1996), 71-74.
  * [2] M. Breen, Primitive Radon partitions for cyclic polytopes, Isr. J. Math., 15 (1973), 156-157.
  * [3] J. L. Bryant, Piecewise linear topology, Handbook of geometric topology, 219-259, North-Holland, Amsterdam, 2002.
  * [4] J. A. De Loera, E. Peterson, and F. E. Su, A Polytopal Generalization of Sperner’s Lemma, J. of Combin. Theory Ser. A, 100 (2002), 1-26.
  * [5] K. Fan, A generalization of Tucker’s combinatorial lemma with topological applications. Ann. of Math., 56 (1952), 431-437.
  * [6] K. Fan, Simplicial maps from an orientable n-pseudomanifold into ${\bf S}^{m}$ with the octahedral triangulation, J. of Combinatorial Theory, 2 (1967), 588-602.
  * [7] J. Matoušek, Using the Borsuk-Ulam theorem, Springer-Verlag, Berlin, 2003.
  * [8] F. Meunier, Sperner labellings: a combinatorial approach, J. of Combin. Theory Ser. A, 113 (2006), 1462-1475.
  * [9] M. D. Meyerson and A. H. Wright, A new and constructive proof of the Borsuk-Ulam theorem, Proc. Amer. Math. Soc., 73 (1979), 134-136.
  * [10] J. W. Milnor, Topology from the differentiable viewpoint, The University Press of Virginia, Charlottesville, Virginia, 1969.
  * [11] O. R. Musin, Chebyshev systems and zeros of a function on a convex curve, Proc. Steklov Inst. of Math., 221 (1998), 236-246, arXiv:0903.1908.
  * [12] O. R. Musin, Borsuk-Ulam type theorems for manifolds, Proc. Amer. Math. Soc. 140 (2012), 2551-2560.
  * [13] T. Prescott and F. E. Su. A constructive proof of Ky Fan’s generalization of Tucker’s lemma, J. Combin. Theory Ser. A, 111 (2005), 257-265.
  * [14] H. Seifert and W. Threlfall, Lehrbuch der Topologie, Teubner, 1934; Chelsea, 1947; translated as A Textbook of Topology, Academic Press, 1980.
  * [15] E. Sperner, Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes, Abh. Math. Sem. Univ. Hamburg 6 (1928), 265-272.
  * [16] A. W. Tucker, Some topological properties of the disk and sphere. In: Proc. of the First Canadian Math. Congress, Montreal, 285-309, 1945.

O. R. Musin
Department of Mathematics, University of Texas at Brownsville, One West
University Boulevard, Brownsville, TX, 78520
and
IITP RAS, Bolshoy Karetny per. 19, Moscow, 127994, Russia
E-mail address<EMAIL_ADDRESS>


$C_{n,g}(\bar{\theta})=n\mathbb{E}_{n}\left[g^{\prime}\left(Z,\bar{\theta},\eta_{0}\right)\right]W_{n,g}^{-}\mathbb{E}_{n}\left[g^{\prime}\left(Z,\bar{\theta},\eta_{0}\right)\right],$

where $W_{n,g}^{-}$ is a consistent estimator for $W_{g}^{\dagger},$
$W_{g}=\mathbb{E}\left[g\left(Z,\bar{\theta},\eta_{0}\right)g^{\prime}\left(Z,\bar{\theta},\eta_{0}\right)\right],$
and $A^{\dagger}$ denotes the Moore-Penrose generalized inverse of $A$. Let
$c_{\alpha}(r)$ be the $1-\alpha$ quantile of a chi-square distribution with
$r$ degrees of freedom, $\chi_{r}^{2}$. The score test based on $g$ is
$S_{n,g}(\bar{\theta})=1(C_{n,g}(\bar{\theta})>c_{\alpha}(r_{g})),$ where
$1(A)$ is the indicator of the event $A\ $and $r_{g}=rank(W_{g})>0.$ For the
special case $g=\tilde{s}_{\theta},$ we use the notation
$\tilde{S}_{n}(\bar{\theta})=1(\tilde{C}_{n}(\bar{\theta})>c_{\alpha}(\tilde{r})),$
where $\tilde{r}=rank(\tilde{I}_{\theta}).$ For any orthogonal moment $g$ and
a path (2.11) with score $s=s_{\eta}+\delta^{\prime}s_{\theta},$ the local
power function is

$\pi_{g}(\delta):=\lim_{n\rightarrow\infty}\mathbb{P}_{1/\sqrt{n}}\left(C_{n,g}(\bar{\theta})>c_{\alpha}(r_{g})\right),$

Note that the local power function depends on the score $s$ only through
$\delta\ $by (2.13), and more specifically, only on the orthogonal projection
of $\delta$ onto the range of $\tilde{I}_{\theta},$ denoted by
$\delta_{\perp}$, i.e. $\pi_{g}(s)\equiv\pi_{g}(\delta_{\perp}).$ Let
$\chi_{r}^{2}(d)$ denote a chi-square random variable with $r$ degrees of
freedom and non-centrality parameter $d.$

Define the drift parameter

$\mu\equiv\mu(\delta,g)=\mathbb{E}[g(Z,\theta_{0},\eta_{0})\delta^{\prime}\tilde{s}_{\theta}(Z)]$

and the non-centrality parameter $\Delta=\mu^{\prime}W_{g}^{\dagger}\mu,$
which can be nicely expressed as the squared norm of an orthogonal projection,

$\Delta=\left\|\Pi_{\mathcal{G}}\left(\delta^{\prime}\tilde{s}_{\theta}(Z)\right)\right\|^{2},$

where $\mathcal{G}$ is the linear span of $g$ in $L_{2},$ as shown in the
proof of the next result.

###### Proposition S.1.1

The asymptotic local power function of orthogonal score-based tests is given
by

$\pi_{g}(\delta)=\mathbb{P}\left(\chi_{r_{g}}^{2}(\Delta)>c_{\alpha}(r_{g})\right).$

The function $\pi_{g}(\delta)$ satisfies: (i) if
$\Pi_{\mathcal{G}}\delta^{\prime}\tilde{s}_{\theta}(Z)\neq 0,$ then
$\pi_{g}(\delta)>\alpha;$ (ii) if
$\Pi_{\mathcal{G}}\delta^{\prime}\tilde{s}_{\theta}(Z)=0$ a.s., then
$\pi_{g}(\delta)=\alpha;$ (iii) furthermore, for all $a>0,$

$\inf_{\delta\in B(a)}\pi_{g}(\delta)\leq\inf_{\delta\in
B(a)}\pi_{\tilde{s}_{\theta}}(\delta),$

where
$B(a)=\\{\delta\in\mathbb{R}^{p}:\delta^{\prime}\tilde{I}_{\theta}\delta\geq
a\\}.$

Proof: By Lecam’s Third Lemma and (2.13), under local alternatives (2.11)
$\mathbb{P}_{n^{-1/2}}$ with score $s\in L_{2}^{0}$,
$s=s_{\eta}+\delta^{\prime}s_{\theta},$ (consistent with
$H_{1n}:\theta_{0}=\bar{\theta}+\delta n^{-1/2}),$ it holds

$\sqrt{n}\mathbb{E}_{n}\left[g(Z,\bar{\theta},\eta_{0})\right]\longrightarrow_{d}Z\sim
N_{k}\left(\mathbb{E}\left[g(Z,\bar{\theta},\eta_{0})s(Z)\right],W_{g}\right).$

By orthogonality of $g$, it follows

$\mathbb{E}\left[g(Z,\bar{\theta},\eta_{0})s(Z)\right]=\mathbb{E}\left[g(Z,\bar{\theta},\eta_{0})\delta^{\prime}\tilde{s}_{\theta}\right]\equiv\mu.$

Therefore, consistency of $W_{n,g}^{-}$ and the continuous mapping theorem
yield, under $\mathbb{P}_{n^{-1/2}}$

$C_{n,g}(\bar{\theta})\longrightarrow_{d}Z^{\prime}W_{g}^{\dagger}Z\sim\chi_{r_{g}}^{2}(\Delta),$

where $\Delta=\mu^{\prime}W_{g}^{\dagger}\mu.$ To see that
$Z^{\prime}W_{g}^{\dagger}Z\sim\chi_{r_{g}}^{2}(\Delta)$ use the spectral
decomposition of $W_{g},$ so $W_{g}^{\dagger}=U\Lambda^{-1}U^{\prime},$
$\Lambda$ is a $r\times r$ diagonal matrix with the non-zero eigenvalues and
$U$ has as columns the corresponding $r$ orthonormal eigenvectors. Then,

$\Lambda^{-1/2}U^{\prime}Z\sim
N_{r}\left(\Lambda^{-1/2}U^{\prime}\mu,I_{r}\right),$

and hence $Z^{\prime}W_{g}^{\dagger}Z\sim\chi_{r_{g}}^{2}(\Delta)$ with
$\Delta=\mu^{\prime}W_{g}^{\dagger}\mu.$ Note

$\displaystyle\Delta$
$\displaystyle=\mu^{\prime}W_{g}^{\dagger}W_{g}W_{g}^{\dagger}\mu$
$\displaystyle=\beta^{\prime}W_{g}\beta,$

where $\beta\equiv W_{g}^{\dagger}\mu$ is the minimum norm solution in the
orthogonal projection
$\Pi_{\mathcal{G}}\left(\delta^{\prime}\tilde{s}_{\theta}(Z)\right)=\beta^{\prime}g,$
and thus
$\Delta=\left\|\Pi_{\mathcal{G}}\left(\delta^{\prime}\tilde{s}_{\theta}(Z)\right)\right\|^{2}.$
These results show parts (i) and (ii). Part (iii) follows from Lemma 3.2(ii)
in Chen and Santos (2018).

Proposition S.1.1 gives the general expression of the asymptotic local power
function of score based tests. Note
$\Pi_{\mathcal{G}}\left(\delta^{\prime}\tilde{s}_{\theta}(Z)\right)=\Pi_{c_{g}^{\prime}\tilde{s}_{\theta}}\left(\delta^{\prime}\tilde{s}_{\theta}(Z)\right),$
so the local power is determined by the position of $c_{g}$ relative to the
direction $\delta.$ The choice $g=\tilde{s}_{\theta}$ leads to
$\Pi_{\tilde{s}_{\theta}}\left(\delta^{\prime}\tilde{s}_{\theta}(Z)\right)=\delta^{\prime}\tilde{s}_{\theta}(Z)$
and a non-centrality parameter $\delta^{\prime}\tilde{I}_{\theta}\delta,$
which is positive provided $\delta_{\perp}\neq 0.$ Part (iii) shows this is
the optimal choice of orthogonal moment for local alternatives at a distance
$a$ of the null hypothesis.

The previously introduced score tests are not feasible, because $\eta_{0}$ is
unknown. However, the asymptotic local power properties of feasible tests are
the same as the infeasible ones, as it follows from the orthogonality and
Lecam’s Third Lemma. Feasible tests will be studied in a companion paper.

##  S.2 Relationship with identification

The main discussion in the text makes it clear that RLN and RLS are not
related to identification of the structural parameter, as they involve only
the null hypothesis, while identification requires to study what happens when
the structural parameter changes.141414Under some additional conditions, non-
surjectivity may be related to identification. For example, Johnson (2004) has
shown that in discrete choice panel data models with compactly supported
covariates, RLN is necessary for identification of $\theta_{0}.$ With infinite
support on covariates, $\theta_{0}$ might be point identified in surjective
discrete choice models, as shown in Manski (1987). Lack of identification of
the structural parameter will do have an impact on power, though, as
directions of identification failure, i.e. $\delta^{\prime}s$ such that
$\delta^{\prime}\tilde{s}_{\theta}(Z)=0,$ will also have zero slope by (2.13).
These directions correspond to zeros of the efficient information matrix
$\tilde{I}_{\theta}=\mathbb{E}[\tilde{s}_{\theta}(Z)\tilde{s}_{\theta}^{\prime}(Z)].$
For non-trivial local power, we require $\tilde{I}_{\theta}$ to have positive
rank, but not necessarily full rank. In the partly linear model the dimension
of $\theta$ is one, and the situation of $\tilde{I}_{\theta}$ being not zero
but not full rank does not arise. This situation does arise in other examples,
as we illustrate with sample selection models.

Example 4: Sample Selection Models. Consider a data observation $Z=(Y,X)$ such
that $Y=(Y_{1},Y_{2}),$ $Y_{1}=Y^{\ast}Y_{2},$ with

$\displaystyle Y^{\ast}$ $\displaystyle=X^{\prime}\theta_{0}+U$ $\displaystyle
Y_{2}$ $\displaystyle=1(X^{\prime}\gamma_{0}-V\geq 0),$

where $(U,V)$ are independent of $X,$ with joint density $g_{0}.$ Here,
$\eta_{0}=(g_{0},\gamma_{0}).$ This is the well known sample selection model,
see, e.g. Heckman (1979). The information in semiparametric versions of this
model where $g_{0}$ is unknown was studied in detail by Chamberlain (1986),
who showed

$\tilde{s}_{\theta}(Z)=\varphi(Y_{2},U,X^{\prime}\gamma_{0})\left(X-\mathbb{E}\left[\left.X\right|X^{\prime}\gamma_{0}\right]\right),$

for some function $\varphi\in L_{2}$ which is irrelevant for our purposes. In
this example, $\tilde{s}_{\theta}=0$ a.s. iff
$\mathbb{E}\left[\left.X\right|X^{\prime}\gamma_{0}\right]=X$ a.s., which
typically holds with discrete regressors $X$. If there are no exclusion
restrictions, in the sense of all components of $\theta_{0}$ being non zero,
then the efficient score satisfies $\tilde{s}_{\theta}^{\prime}\gamma_{0}=0$
a.s. Thus, even when RLN holds the local power will be zero for paths such
that $\theta_{\tau}=\bar{\theta}+\tau\gamma_{0}+o(1)$. This is a consequence
of the efficient Fisher Information being not full rank and $\theta_{0}$ not
being identified. Nevertheless, orthogonal moments do exist when
$\mathbb{P}_{0}\left(\mathbb{E}\left[\left.X\right|X^{\prime}\gamma_{0}\right]\neq
X\right)>0$ and we can have power in other directions different from
$\gamma_{0}$. Existence of LR moments does not require exclusion restrictions
in sample selection models. $\square$

Surjectivity is in general not related to identification of nuisance
parameters either. To explain the difference, consider the common situation
where there exists a linear and continuous operator
$S_{\eta_{0}}:T(\eta_{0})\subset\mathcal{H}\mapsto L_{2},$ that maps “scores”
of $\eta_{0}$ into scores of the model, so that

$s_{\eta}=S_{\eta_{0}}b.$ (S.2.1)

The mapping $S_{\eta_{0}}$ is called the score operator for the nuisance
parameter $\eta_{0}$, see, e.g., Begun, Hall, Huang and Wellner (1983). In the
setting where (S.2.1) holds, the tangent space for nuisance parameters is
obtained as the range of $S_{\eta_{0}},$ $\mathcal{R}(S_{\eta_{0}}),$ i.e.

$T_{0}=\\{s_{\eta}\in L_{2}^{0}:s_{\eta}=S_{\eta_{0}}b\text{ for some }b\in
T(\eta_{0})\\}\equiv\mathcal{R}(S_{\eta_{0}}).$

Identification of the nuisance parameter is about injectivity of
$S_{\eta_{0}},$ i.e. is about $\mathcal{N}(S_{\eta_{0}}):=\\{b\in
T(\eta_{0}):$ $S_{\eta_{0}}b=0\\},$ while RLS or RLN is about
$\mathcal{R}(S_{\eta_{0}}).$ When $\mathcal{N}(S_{\eta_{0}})\neq\\{0\\}$ the
nuisance parameter is generally not identified. Whether this lack of
identification affects identification of
$\mathbb{E}[g(Z,\theta_{0},\eta_{0})]$ depends on the moment function $g,$ but
it is more likely that identification of
$\mathbb{E}[g(Z,\theta_{0},\eta_{0})]$ will hold with a LR moment $g$ than
otherwise, as by definition LR moments are insensitive to small departures of
$\eta$ from $\eta_{0},$ including departures along directions of
identification failure.

In general, RLS and identification of nuisance parameters are not related in
infinite dimensional problems, because $\mathcal{N}(S_{\eta_{0}})$ and
$\mathcal{R}(S_{\eta_{0}})$ are not related, an exception being the following
example.

Example 2: Normal means model, cont. Consider a data observation
$Z_{i}=\alpha_{i}+\sqrt{\theta_{0}}u_{i},$ $\alpha_{i}\sim\eta_{0},$
$u_{i}\sim N(0,1),$ $\alpha_{i}$ independent of $u_{i},$ with an absolutely
continuous density $\eta_{0}$ with respect to the Lebesgue measure on
$\mathbb{R}.$ The density of the data $Z_{i}$ is

$f_{\theta_{0},\eta_{0}}(z)=\int\phi(\left(z-\alpha\right)/\sqrt{\theta_{0}})\eta_{0}(\alpha)d\alpha,$

where $\phi$ is the standard Gaussian pdf. Identification of $\eta_{0}$ when
$\theta_{0}$ is known requires that if

$\int\phi(\left(z-\alpha\right)/\sqrt{\theta_{0}})\eta_{0}(\alpha)d\alpha=\int\phi(\left(z-\alpha\right)/\sqrt{\theta_{0}})\eta(\alpha)d\alpha\text{
a.s.}$

then $\eta_{0}=\eta,$ or equivalently, by taking $\eta=\eta_{0}(1+b)$,
$\mathcal{N}(S_{\eta_{0}})=0,$ where

$S_{\eta_{0}}b(z)=\frac{1}{f_{\theta_{0},\eta_{0}}(z)}\int\phi(\left(z-\alpha\right)/\sqrt{\theta_{0}})b(\alpha)\eta_{0}(\alpha)d\alpha$

is a linear mapping from $T(\eta_{0})\subset L_{2}^{0}(\eta_{0})$ to $L_{2}$.
By Fubini,

$\displaystyle\langle S_{\eta_{0}}b,s\rangle$ $\displaystyle=\int
S_{\eta_{0}}b(z)s(z)f_{\theta_{0},\eta_{0}}(z)dz$ $\displaystyle=\int
b(\alpha)\left(\int\phi(\left(z-\alpha\right)/\sqrt{\theta_{0}})s(z)dz\right)\eta_{0}(\alpha)d\alpha$
$\displaystyle=\langle b,S_{\eta_{0}}^{\ast}s\rangle,$

where $S_{\eta_{0}}^{\ast}$ is the (implicitly defined) adjoint operator of
$S_{\eta_{0}}.$ By duality, see Luenberger (1997, p.157), it is known that

$\overline{\mathcal{R}(S_{\eta_{0}})}^{\perp}=\mathcal{N}(S_{\eta_{0}}^{\ast}).$
(S.2.2)

However, by symmetry of the Gaussian density
$\mathcal{N}(S_{\eta_{0}}^{\ast})=\\{0\\}$ iff
$\mathcal{N}(S_{\eta_{0}})=\\{0\\},$ and hence $\mathcal{N}(S_{\eta_{0}})=0$
iff $\overline{\mathcal{R}(S_{\eta_{0}})}=L_{2}^{0}.$ Thus, in this example
RLS holds iff $\eta_{0}$ is nonparametrically point identified. Note the same
is true if the Gaussian pdf is replaced by any other symmetric pdf. This is
summarized in the following result.

###### Proposition S.2.1

In the normal means model $\eta_{0}$ is nonparametrically identified under
$H_{0}$ iff RLS holds (hence iff an orthogonal moment for $\theta_{0}$ does
not exist).

Proof of Proposition S.2.1: $\mathcal{N}(S_{\eta_{0}}^{\ast})=\\{0\\}$ iff
$\mathcal{N}(S_{\eta_{0}})=\\{0\\},$ and hence $\mathcal{N}(S_{\eta_{0}})=0$
iff $\overline{\mathcal{R}(S_{\eta_{0}})}=L_{2}^{0}.$ Thus, in this example
RLS holds iff $\eta_{0}$ is nonparametrically point identified. $\square$

More generally, using (S.2.2) we can characterize RLN in terms of injectivity
of the adjoint of the score operator for nuisance parameters.151515This
generalizes Bonhomme (2012, footnote 26) to essentially any regular
semiparametric model for which the representation (S.2.1) holds. Let
$S_{\eta_{0}}^{\ast}$ denote the adjoint operator of $S_{\eta_{0}}$ in
(S.2.1).

###### Proposition S.2.2

Let (S.2.1) hold. The model satisfies RLN iff
$\mathcal{N}(S_{\eta_{0}}^{\ast})\neq 0.$

Proposition S.2.2 establishes a link between surjectivity and completeness or
injectivity assumptions, such as those used in the nonparametric instrumental
variable literature; see e.g. Newey and Powell (2003). Thus, we can use known
results on completeness to establish surjectivity.

Example 2: Normal means model, cont. Applying the previous proposition to this
example, from the completeness properties of the Gaussian family it follows
that

$\int\phi(\left(z-\alpha\right)/\sqrt{\theta_{0}})s(z)dz=0\text{ for all
}\alpha,$ (S.2.3)

iff $s=0$ a.s. Therefore, RLS holds and no orthogonal moment for $\theta_{0}$
exists in this example. $\square$

By (S.2.2) orthogonal moments are those in $\mathcal{N}(S_{\eta_{0}}^{\ast}).$
The relation between Fisher Information for the parameter of interest and
existence of orthogonal moments is determined by the position of the score
$s_{\theta}$ relative to the set of orthogonal moments
$\mathcal{N}(S_{\eta_{0}}^{\ast}).$ If $s_{\theta}$ is orthogonal to
$\mathcal{N}(S_{\eta_{0}}^{\ast})\neq\\{0\\},$ then $\tilde{I}_{\theta}=0$ and
orthogonal moments exists, although they are not informative about
$\theta_{0}.$ On the contrary, if $s_{\theta}$ is not orthogonal to
$\mathcal{N}(S_{\eta_{0}}^{\ast})\neq\\{0\\},$ then orthogonal moments exists
and they are informative about $\theta_{0}.$

##  S.3 Relation with Functional Differencing

Bonhomme (2012) constructs moments that do not depend on $\eta_{0}$. The
setting is a fixed-$T$ panel data setting with strictly exogenous covariates.
Here, we provide the general idea of Bonhomme’s (2012) approach and state
conditions under which his approach and ours are equivalent for the setting he
considers.

Let $Z=\left(Y,X\right)$. For a given value $X=x$ and $\theta$, Bonhomme
(2012) introduces the following operator:

$\left[L_{\theta,x}h\right](y)=\int_{\mathcal{A}}f_{y|\alpha,x}\left(y|\alpha,x;\theta\right)h(\alpha)d\nu\left(\alpha\right),$

where $\mathcal{A}$ is a known set that contains the support of
$\eta_{0}\left(\alpha|x\right),$ for all $x.$ As
$L_{\bar{\theta},x}\eta_{0}(\cdot|x)=f_{\bar{\theta},\eta_{0}}(\cdot|x)$, this
operator can be understood as a mapping from the distribution function of
individual effects to that of the data. Instead, we work with the score
operator $S_{\eta_{0}}$ which is a mapping from the tangent set of UH to the
tangent set of the model $\mathcal{P}_{0}$:

$\left[S_{\eta_{0}}b\right](y)=\frac{1}{f_{\bar{\theta},\eta_{0}}(y|x)}\int_{\mathcal{A}}f_{y|\alpha,x}\left(y|\alpha,x;\bar{\theta}\right)b(\alpha)\eta_{0}(\alpha|x)d\nu\left(\alpha\right).$

To make our setting comparable to that in Bonhomme (2012) we fix $X=x$ so that
now the score operator should be understood as a function of $y$ only.

Even though $L_{\theta,x}$ can be defined for any $\theta$, we set
$\theta=\bar{\theta}$ as we are interested in inference. Moreover, the
functions $h$ and $b$ might depend on $x$, however, we suppress this explicit
dependence to simplify the notation. Bonhomme (2012) introduces the spaces of
square integrable functions with domains $\mathcal{A}$ and $\mathcal{Y}$,
respectively:

$\begin{split}\mathcal{M}_{\alpha}&=\left\\{h:\mathcal{A}\mapsto\mathbb{R},\int_{\mathcal{A}}h^{2}(\alpha)\pi_{\alpha}(\alpha)d\nu\left(\alpha\right)<\infty\right\\},\\\
\mathcal{M}_{y}&=\left\\{q:\mathcal{Y}\mapsto\mathbb{R},\int_{\mathcal{Y}}q^{2}(y)\pi_{y}(y)d\mu_{Y}\left(y\right)<\infty\right\\},\end{split}$

where $\pi_{\alpha}$ and $\pi_{y}$ are two positive functions (which can
depend on $x$) and are chosen by the econometrician. Then, under some
conditions $L_{\bar{\theta},x}$ is an operator that maps
$h\in\mathcal{M}_{\alpha}$ to $L_{\bar{\theta},x}h\in\mathcal{M}_{y}$. Note
that $\mathcal{M}_{\alpha}$ and $\mathcal{M}_{y}$ are both Hilbert spaces,
endowed with the scalar products $\left\langle
h_{1},h_{2}\right\rangle=\int_{\mathcal{A}}h_{1}(\alpha)h_{2}(\alpha)\pi_{\alpha}(\alpha)d\alpha$
and $\left\langle
q_{1},q_{2}\right\rangle=\int_{\mathcal{Y}}q_{1}(\alpha)q_{2}(\alpha)\pi_{y}(y)dy$,
respectively (we drop the dependence on the integrating measure for
simplicity). The corresponding norms are
$\left|\left|h\right|\right|=\left\langle h,h\right\rangle^{1/2}$ and
$\left|\left|q\right|\right|=\left\langle q,q\right\rangle^{1/2}$. The range
of $L_{\bar{\theta},x}$ is defined as follows:

$\mathcal{R}(L_{\bar{\theta},x})=\left\\{L_{\bar{\theta},x}h\in\mathcal{M}_{y}:h\in\mathcal{M}_{\alpha}\right\\}.$

Then, non-surjectivity holds in Bonhomme’s (2012) setting when
$\overline{R(L_{\theta,x})}\neq\mathcal{M}_{y}$ $v_{X}-$a.s. for all
$\theta\in\Theta.$ In this case, to construct a moment that does not depend on
the UH ($\eta_{0}$) we need to find a function $g_{FD}$ that is orthogonal to
$\mathcal{R}(L_{\bar{\theta},x})$. A moment based on such a function is a
Functional Differencing moment (FD). This can be accomplished by:

$g_{FD}\left(z,\bar{\theta}\right)=q(z)-\Pi_{\overline{R(L_{\bar{\theta},x})}}q(z),\;\;q\in\mathcal{M}_{y}.$
(S.3.1)

If $f_{\bar{\theta},\eta_{0}}\in\mathcal{M}_{y}$ $v_{X}-$a.s., Theorem 2 in
Bonhomme (2012) states that
$\mathbb{E}\left[\pi_{y}(Y)g_{FD}\left(Z,\bar{\theta}\right)|X\right]=0$. This
moment does not depend on $\eta_{0}$ and is trivially a NF moment.

Under Bonhomme’s (2012) conditions a more general characterization of FD
moments can be shown. Note that by duality theory, see Luenberger (1997,
p.157),
$\overline{\mathcal{R}(L_{\bar{\theta},x})}^{\perp}=\mathcal{N}(L_{\bar{\theta},x}^{\ast}).$
We aim to find $L_{\bar{\theta},x}^{\ast}.$ Simple algebra shows, by Fubini,

$\displaystyle\left\langle L_{\bar{\theta},x}h,g\right\rangle$
$\displaystyle=\int_{\mathcal{Y}}L_{\bar{\theta},x}h(y)g(y,x,\bar{\theta})\pi_{y}(y)d\mu_{Y}(y)$
$\displaystyle=\int_{\mathcal{Y}}\int_{\mathcal{A}}f_{y|\alpha,x}\left(y|\alpha,x;\theta\right)h(\alpha)d\nu\left(\alpha\right)g(y,x,\bar{\theta})\pi_{y}(y)d\mu_{Y}(y)$
$\displaystyle=\int_{\mathcal{A}}\left(\int_{\mathcal{Y}}f_{y|\alpha,x}\left(y|\alpha,x;\theta\right)\pi_{y}(y)g(y,x,\bar{\theta})\frac{1}{\pi_{\alpha}(\alpha)}d\mu_{Y}(y)\right)h(\alpha)\pi_{\alpha}(\alpha)d\nu\left(\alpha\right)$
$\displaystyle=\left\langle h,L_{\bar{\theta},x}^{\ast}g\right\rangle.$

Thus,

$L_{\bar{\theta},x}^{\ast}g=\frac{1}{\pi_{\alpha}(\alpha)}\int_{\mathcal{Y}}f_{y|\alpha,x}\left(y|\alpha,x;\theta\right)\pi_{y}(y)g(y,x,\bar{\theta})d\mu_{Y}(y),$

and

$\displaystyle\overline{\mathcal{R}(L_{\bar{\theta},x})}^{\perp}$
$\displaystyle=\mathcal{N}(L_{\bar{\theta},x}^{\ast})$
$\displaystyle=\left\\{g_{FD}(\cdot,x,\bar{\theta})\in\mathcal{M}_{y}:\int_{\mathcal{Y}}g_{FD}(y,x,\bar{\theta})\pi_{y}(y)f_{y|\alpha,x}\left(y|\alpha,x;\theta\right)d\mu_{Y}(y)=0\right\\}$
$\displaystyle=\left\\{g_{FD}(\cdot,x,\bar{\theta})\in\mathcal{M}_{y}:\mathbb{E}\left[\left.\pi_{y}(Y)g_{FD}(Z,\bar{\theta})\right|X,\alpha\right]=0,v_{X}\times\pi_{\alpha}-a.s\right\\}.$

It follows from our results that:

###### Proposition S.3.1

If $g_{FD}$ is a FD moment, then $\pi_{y}g_{FD}$ is a LR moment provided the
support of $v_{X}\times\pi_{\alpha}$ contains that of $v_{X}\times\eta_{0}.$

We have discussed in the main text conditions under which the reciprocal is
true.

We now compare our definition of non-surjectivity with that in Bonhomme
(2012). He defines non-surjectivity as the condition that for all
$\theta\neq\theta_{0}$ in $\Theta,$
$\overline{\mathcal{R}(L_{\theta,x})}\neq\mathcal{M}_{y},$ with positive
probability in $x.$ The first difference relative to our definition is that we
require surjectivity only at $\theta=\theta_{0}.$ Second, from our arguments
above, $\overline{\mathcal{R}(L_{\theta_{0},x})}\neq\mathcal{M}_{y}$ is
equivalent to existence of $g_{FD}(\cdot,x,\theta_{0})\in\mathcal{M}_{y}$ such
that $g_{FD}\neq 0$ and
$\mathbb{E}\left[\left.\pi_{y}(Y)g_{FD}(Z,\theta_{0})\right|X,\alpha\right]=0$
$v_{X}\times\pi_{\alpha}-a.s.$ This implies our non-surjectivity condition by
taking $g=\pi_{y}g_{FD},$ by the support conditions on $\pi_{\alpha}.$

##  S.4 Results on Analytic Functions

We start with some definitions of real analytic functions. Let $\mathcal{A}$
denote an open connected set of $\mathbb{R}^{d_{\alpha}}.$ A function
$f:\mathcal{A}\rightarrow\mathbb{R}$ is real analytic on $\mathcal{A}$ if $f$
is infinitely differentiable on $\mathcal{A}$ and for every compact
$K\subset\mathcal{A}$ there exists a $C>0$ such that for all multi-index
$r\in\mathbb{Z}^{d_{\alpha}}$

$\sup_{\alpha\in
K}\left|\frac{\partial^{r}f(\alpha)}{\partial\alpha}\right|\leq
C^{\left|r\right|+1}r!.$

An important theorem is the Identity Theorem. If the set of zeros of an
analytic function $f$ has an accumulation point inside its domain, then $f$ is
zero everywhere on the connected component containing the accumulation point.

We will apply these results to functions of the form

$f(\alpha)=\int
g(z,\theta_{0},\eta_{0})f_{z|\alpha}\left(z|\alpha;\theta_{0}\right)d\mu(z),$

defined on the support of $\eta_{0}$, say $\mathcal{S},$ where
$\mathcal{S}\subset\mathcal{A},$ and $\mathcal{A}$ is a known connected open
set of $\mathbb{R}^{d_{\alpha}}$. The following result holds by the Identity
Theorem.

###### Proposition S.4.1

If $\mathcal{S}$ contains an open set $U$, $f(\alpha)=0$ for all $\alpha\in
U,$ and $f$ is real-analytic on $\mathcal{A}$, then $f(\alpha)=0$ for all
$\alpha\in\mathcal{A}$.

In many applications the analyticity follows from well known results. For
example, consider the conditional density in the exponential family

$f_{z|\alpha}\left(z|\alpha;\theta_{0}\right)=c(\alpha;\theta_{0})d(z;\theta_{0})\exp(\alpha^{\prime}z),$
(S.4.1)

where $d(z;\theta_{0})$ is a non-negative measurable function and
$c(\alpha;\theta_{0})$ is the normalizing constant

$c(\alpha;\theta_{0})=\frac{1}{\int
d(z;\theta_{0})\exp(\alpha^{\prime}z)d\mu(z)}.$

Set $N_{d,\mu}=\\{\alpha\in\mathbb{R}^{d_{\alpha}}:\int
d(z;\theta_{0})\exp(\alpha^{\prime}z)d\mu(z)<\infty\\}$. Then, a well known
result in the theory of exponential families is that $c(\cdot;\theta_{0})$ is
analytic on $N_{d,\mu}.$ Furthermore,

$\displaystyle f(\alpha)$ $\displaystyle=\int
g(z,\theta_{0},\eta_{0})f_{z|\alpha}\left(z|\alpha;\theta_{0}\right)d\mu(z)$
$\displaystyle=c(\alpha;\theta_{0})\int
g(z,\theta_{0},\eta_{0})d(z;\theta_{0})\exp(\alpha^{\prime}z)d\mu(z)$
$\displaystyle=c(\alpha;\theta_{0})\int\exp(\alpha^{\prime}z)d\nu(z),$
$\displaystyle\equiv c(\alpha;\theta_{0})b(\alpha),$

where
$\nu(A)=\int_{A}g(z,\theta_{0},\eta_{0})d(z;\theta_{0})\exp(\alpha^{\prime}z)d\mu(z).$
Define,

$N=\\{\alpha\in\mathbb{R}^{d_{\alpha}}:\int\left(\left|g(z,\theta_{0},\eta_{0})\right|\vee
1\right)d(z;\theta_{0})\exp(\alpha^{\prime}z)d\mu(z)<\infty\\}.$

Therefore, provided $\mathcal{A}\subset N$ then $f(\alpha)$ is analytic, see
Theorem 2.7 and Lemma 2.8 in Brown (1986). It suffices to apply the Identity
Theorem to $b.$ For this we need to check that $b$ is real-analytic. By the
fact that $b$ is analytic, and that its derivatives can be obtained by
differentiating under the integral sign, this means that

$\sup_{\alpha\in
K}\left|\int\left|g(z,\theta_{0},\eta_{0})\right|d(z;\theta_{0}){\displaystyle\prod\limits_{i=1}^{d_{\alpha}}}z_{i}^{r_{i}}\exp(\alpha^{\prime}z)d\mu(z)\right|\leq
C^{\left|r\right|+1}r!.$

If we assume that $\inf_{\alpha\in K}c(\alpha;\theta_{0})>0$ for every compact
$K\subset\mathcal{A},$ then a sufficient condition for the last display is

$\sup_{\alpha\in
K}\left|\int\left|g(z,\theta_{0},\eta_{0})\right|{\displaystyle\prod\limits_{i=1}^{d_{\alpha}}}z_{i}^{r_{i}}f_{z|\alpha}\left(z|\alpha;\theta_{0}\right)d\mu(z)\right|\leq
C^{\left|r\right|+1}r!.$

For example, if $g$ is bounded, this is a standard growth moment condition.

## References

  * (1)
  * Begun, Hall, Huang, and Wellner (1983) Begun, J. M., Hall, W. J., Huang, W. M., and Wellner, J. A. (1983): “Information and Asymptotic Efficiency in Parametric-Nonparametric Models”, _Annals of Statistics_ , 11, 432-452.
  * Bonhomme (2012) Bonhomme, S. (2012): “Functional Differencing”, _Econometrica_ , 80(4), 1337-1385.
  * B86 (1986) Brown, L.D. (1986): _Fundamentals of Statistical Exponential Families: with Applications in Statistical Decision Theory_ , Institute of Mathematical Statistics.
  * Chamberalin (1986) Chamberlain, G. (1986): “Asymptotic Efficiency in Semi-Parametric Models with Censoring”, _Journal of Econometrics_ , 34, 305-334.
  * Chen, Santos (2018) Chen, X. and Santos, A. (2018): “Overidentification in Regular Models”, _Econometrica_ , 86(5), 1771-1817.
  * H79 (1979) Heckman, J. J. (1979): “Sample Selection Bias As a Specification Error,”  _Econometrica,_ 47, 153–161.
  * Luenberger (1997) Luenberger, D. G. (1997): _Optimization by Vector Space Methods_. New York: John Wiley & Sons. 1969 edition.
  * Newey and Powell (2003) Newey, W. K., and J. Powell (2003): “Instrumental Variables Estimation for Nonparametric Models”,  _Econometrica_ , 71, 1565-1578.