TITLE: Can I eat myself into a black hole?
QUESTION [37 upvotes]: This was a humorous thought experiment that occurred while chatting about black holes.  The person that I was talking to assumed that a black hole required a specific density to be achieved. I pointed to the formula for the Schwarzschild radius.  This suggests that low density black holes are possible if they are large enough.  I'll assume simple spherical, non-rotating, uncharged black holes.
$$
r = \frac{2 G M}{c ^ 2}
$$
Using $\rho$ as the the average density.
$$
M = \frac{4}{3} \pi r^3 \rho
$$
$$
\rho = \frac{3}{8 \pi}\frac{c^2}{G r^2}
$$
Which can be as small as you like by having $r$ large enough.
So, assuming that the average density of a person is approximately that of water, I calculate that if I achieved a radius of approximately $4 \times 10^8 km$ then I would become a black hole.  If I was centred at the Sun then I would extend into the asteroid belt.  Of course, people are not usually spherical though if you get this large then it is probably a good approximation.  There may also be some health issues and practical issues with obtaining sufficient food, oxygen, etc but they are off-topic in this group.
Am I right, is a black hole with the same average density as water possible?
Apart from the biological and nutrient issues, what others might I face?  I guess that I will suffer severe problems long before I reach this size.  Would I collapse and become a star (quite literally)?
Alternatively, if an extremely large number of people gathered in a huge group hug, could they become a black hole?
Update
Thanks to the comments from kleingordon and dmitry-brant, my main question is answered.  This leaves:

Is my calculation right?  (To 1 significant digit)
Would I become a star or face some other calamity before becoming a black hole?

REPLY [42 votes]: As you suggest, long before you got that large gravitation would become dominant.  One of the early what ifs is about what you get if you take a mole (ie $6\times 10^{23}$) of moles (small animals) which results in something a little larger than the Moon, and the answer is not very pretty (at least not for the moles).
This is indeed why stars happen: if you get very large collections of matter, they collapse in on themselves gravitationally, fusion starts in their cores (you are mostly carbon, which would fuse I presume).  I don't know if anyone has done the sums describing the formation of stars whose precursors were very large humans: I suspect not.  But this would happen long before you got large enough to reach your Schwarzschild radius.
In fact, long before that you would hit another problem: surface to volume and temperature.  A grovel over the internet says that humans dissipate about $100\,\mathrm{W}$, so if the average human has a mass of $60\,\mathrm{kg}$, then this is about $1.6\,\mathrm{W/kg}$ or (assuming humans are about as dense as water) about $1.6\,\mathrm{kW/m^3}$.  If you assume humans are spherical then you get surface flux, I think, of about $550 r\,\mathrm{W/m^3}$, where $r$ is the radius of the human (the units are right here: r has the dimensions of length so the flux comes out as $\mathrm{W/m^2}$).  And since humans are approximately black bodies, this corresponds to a surface temperature of
$$\left(\frac{550r}{\sigma}\right)^{\frac{1}{4}}$$
So this is going like $r^{1/4}$ which smells right to me.  Plugging in some numbers, a $100\,\mathrm{m}$ radius human is at around $1000\,\mathrm{K}$.  So you're dead well before you get that big.
So no, you can't eat yourself into a black hole: you die of heat exhaustion before gravity even becomes significant.


TITLE: Trace of a differential operator
QUESTION [8 upvotes]: Given the differential operator:
$$A=\exp(-\beta H)$$
where $$H=\frac{1}{2}\left( -\frac{d^2}{dx^2}+x^2 \right)$$
and $\beta\gt 0$
How can I get the trace of this operator?
Thanks in advance.

REPLY [7 votes]: The trace of this operator is easily obtained in the following way:
$$
   Z={\rm Tr}\exp(-\beta H).
$$
that is equivalent to
$$
 Z=\sum_n \langle n|\exp(-\beta H)|n\rangle.
$$
Assuming $H|n\rangle=E_n|n\rangle$, this is just
$$
  Z=\sum_n\exp(-\beta E_n).
$$
Your case is the harmonic oscillator $E_n=n+\frac{1}{2}$ and the sum is just a geometric series easy to perform.


text:
\begin{document}

\title[COUNTEREXAMPLES FOR TOPOLOGICAL COMPLEXITY IN DIGITAL IMAGES]{COUNTEREXAMPLES FOR TOPOLOGICAL COMPLEXITY IN DIGITAL IMAGES}

\author{MEL\.{I}H \.{I}S and \.{I}SMET KARACA}
\date{\today}

\address{\textsc{Melih Is}
Ege University\\
Faculty of Sciences\\
Department of Mathematics\\
Izmir, Turkey}
\email{melih.is@ege.edu.tr}
\address{\textsc{Ismet Karaca}
Ege University\\
Faculty of Science\\
Department of Mathematics\\
Izmir, Turkey}
\email{ismet.karaca@ege.edu.tr}

\subjclass[2010]{68R01, 65D18, 55M30, 68U10}

\keywords{Digital image, topological complexity number, digital topological complexity number, higher topological complexity, Betti number}

\begin{abstract}
Digital topology has its own working conditions and sometimes differs from the normal topology. In the area of topological robotics, we have important counterexamples in this study to emphasize this red line between a digital image and a topological space. We indicate that the results on topological complexities of certain path-connected topological spaces show alterations in digital images. We also give a result about the digital topological complexity number using the genus of a digital surface in discrete geometry.
\end{abstract}

\maketitle

\section{Introduction}
\quad Digital topology makes it possible to analyze digital images by transferring topological properties into itself. This analyzing process provides advantages in technologies that include especially computer science and image analysis. After that digital topology is introduced by Rosenfeld \cite{Ros:1979} with its most primitive concepts, it has been involved in the studies of a wide variety of fields. One of the most significant of these studies points to the subject of robotics, including algebraic topology over the past 20 years.

\quad Farber \cite{Farber:2003} assigns a positive integer called the topological complexity number $TC(X)$ for each path-connected topological space $X$ and makes inferences about the complexity of the motion area in which a robot is located with obstacles. Afterwards, as the structure of the required topological space differs, the results about computing the topological complexity number also get vary. For example, if $X$ is a connected Lie group, then the topological complexity number $TC(X)$ of $X$ equals the Lusternik Schnirelmann category $cat(X)$ of $X$ \cite{Farber:2004}. Davis \cite{Davis:2017}, \cite{Davis2:2017} has different approaches on the topological complexity number of certain path-connected topological spaces such as a circle or a Klein bottle. The higher topological complexity $TC_{n}$, defined by Rudyak \cite{Rudyak:2010}, is the Schwarz genus of a special fibration and a positive integer such as $cat$ and $TC$. These are all homotopy invariants. Many essential concepts of the algebraic topology, for instance cohomological cup product \cite{Farber:2003}, help to calculate these numbers. Hence, it is the main task to have concrete ideas about the topological complexities of the digital images by making more use of the algebraic topology methods. See \cite{Farber:2008} for more information about the concepts, results and methods for topological robotics.

\quad Digital topology has started to incorporate the algebraic topology methods in time and this process has not ended yet. One of the richest content of these methods is cohomology rings of topological spaces. Ege and Karaca \cite{EgeKaraca:2013} presented the general framework related to the digital simplicial cohomology groups and introduced the cohomological cup-products in digital images. In digital topology, researchers generally deal with the two-dimensional or three-dimensional digital images and they call them as digital curves and digital surfaces, respectively. Rosenfeld \cite{Ros:1970} defined the digital curve and stated that the digital image $X$ is said to be a simple (closed) curve if each point of $X$ has exactly two adjacent points in $X$. On the other hand, the definition of the digital surface was given by Morgenthaler and Rosenfeld \cite{MorgenRosen:1981}. Digital surfaces are so important not only for digital topology but also for discrete and computational geometry. Chen \cite{Chen:2004} used one of the most important notions related to topology and geometry in digital images for the first time: digital manifolds. A digital manifold can be regarded as a discretization of a manifold. In other saying, it is a combinatorial manifold which is defined in digital images. Chen and Rong \cite{ChenRong:2010} improved a powerful method for computing genus and the Betti numbers of a digital image.

\quad In digital topology, not everything is the same as in ordinary topology. As an example, K{\"u}nneth Theorem does not work for digital images \cite{EgeKaraca:2013}. This leads to us to show that cohomological cup product does not hold for digital images \cite{MelihKaraca}. Therefore, the digital interpretations of $cat$ \cite{BorVer:2018}, $TC$ \cite{KaracaIs:2018} and $TC_{n}$ \cite{MelihKaraca} have different results from the topological spaces. In this study, we focus on such results and give counterexamples in digital topology. First, we remind the basic notions of the digital topology, give some concepts and results from discrete geometry and mention about certain definitions of the main tools of robotics in Section \ref{section2}. Thus, we recall a few deliberately selected results on mostly Farber's topological complexity numbers. The main goal of this study gives counterexamples for each properties that is valid in the usual topology but not in digital topology. This shows that digital topology cannot be thought as the same as the usual topology. They often have different impact areas in mathematics because the methods of algebraic topology can lose its influence such as in the example of K{\"u}nneth Theorem and this is the strength of digital topology conditions.

\quad In the first example, we consider the digital image $X = [0,1]_{\mathbb{Z}}$. Since the closed interval $[0,1]$ is contractible in topological spaces, the higher topological complexity of $[0,1]$ for any $n$ is $1$. Moreover, Proposition \ref{p1} supports this result using the cohomological cup-product but in digital images, using the digital cup-product does not give the same result. Hence, the digital image $X = [0,1]_{\mathbb{Z}}$ is a counterexample of that Proposition \ref{p1} does not hold for digital images. Second, we show that the diagonal map of digital images does not coincide with the digital cup product homomorphism. In the next example, we choose a special digital image that the Betti number is $2$. In the usual topology, it is expected that the topological complexity number of a space is $3$, when $b_{1}(X) = 2$ but we prove that it is possible that the digital topological complexity number of such an image is less than $3$. We present a result about the digitally connected digital curves with considering the first Betti numbers. Our next counterexample is constructed on showing that the digital version of the topological complexity number of the wedge of $2$ sphere $S^{2}$ does not have to be $3$. Finally, we study with two digital surfaces such that genus of them are $1$ and $2$. In topology, the topological complexity number of a compact orientable surface of genus $1$ is $3$ whereas the topological complexity number of a compact orientable surface of genus $2$ is $5$. We prove that both of this results does not hold for digital surfaces. We show that the digital topological complexity number of digital simple closed surfaces of genus $0$, $1$ and $2$ are $1$, $2$ and $3$, respectively.

\section{Preliminaries}\label{section2}
\quad This section basically consists of the fundamental notions of the digital topology. In addition, remarkable points of the study of topological robotics are mentioned in the section.

\quad Let $\mathbb{Z}^{m}$ be a set of only integers points of Euclidean space $\mathbb{R}^{m}$. Let $X$ be any finite subset of $\mathbb{Z}^{m}$. Then $(X,\kappa)$ is a \textit{digital image} \cite{Boxer:1999}, where $\kappa$ is an adjacency relation for the points of $X$. Let $x$ and $y$ be any two different points in $\mathbb{Z}^{m}$. Let $k$ be a positive integer such that $k$ is less than or equal to $m$. $x$ and $y$ are \textit{$c_{k}-$adjacent} \cite{Boxer:1999} if there are at most $k$ indices $i$ such that $|x_{i} - y_{i}| = 1$ and for all other indices $i$ such that $|x_{i} - y_{i}| \neq 1$, $x_{i} = y_{i}$. Whereas two points of $\mathbb{Z}$ has only $c_{1} = 2-$adjacency, two points of $\mathbb{Z}^{2}$ has $c_{1} = 4-$adjacency and $c_{2} = 8-$adjacency. Similarly, two points of $\mathbb{Z}^{3}$ has $c_{1} = 6-$adjacency, $c_{2} = 18-$adjacency and $c_{3} = 26-$adjacency.

\quad Let $X$ be a digital image in $\mathbb{Z}^{m}$. $X$ is \textit{$\kappa-$connected} \cite{Herman:1993} if and only if for every pair of different points $x,y \in X$, there is a set $\{x_{0},x_{1}, ...,x_{l}\}$ of points of $X$ such that $x=x_{0}$, $y=x_{l}$ and $x_{i}$ and $x_{i+1}$ are $\kappa-$adjacent where $i=0,1,...,l-1$. Let $f : X_{1} \rightarrow X_{2}$ be a digital map such that $X_{1}$ has an adjacency relation $\kappa_{1}$ in $\mathbb{Z}^{m_{1}}$ and $X_{2}$ has an adjacency relation $\kappa_{2}$ in $\mathbb{Z}^{m_{2}}$. Then $f$ is \textit{$(\kappa_{1},\kappa_{2})-$continuous} \cite{Boxer:1999} if, for any $\kappa_{1}-$connected subset $U_{1}$ of $X_{1}$, $f(U_{1})$ is $\kappa_{2}-$connected. Moreover, if $f$ is both digitally continuous and bijective and the digital map $f^{-1}$ is $(\kappa_{2},\kappa_{1})-$continuous, then $f$ is \textit{$(\kappa_{1},\kappa_{2})-$isomorphism} \cite{Boxer2:2006}.

\quad Let $X$ and $Y$ be any two digital images such that $f,f^{'} : X \rightarrow Y$ are $(\kappa_{1},\kappa_{2})-$continuous maps. If there exists a positive integer $n$ and a digital map \[G : X \times [0,n]_{\mathbb{Z}} \rightarrow Y\] such that the following conditions hold, then $f$ and $f^{'}$ are said to be \textit{digitally $(\kappa_{1},\kappa_{2})-$homotopic} \cite{Boxer:1999} in $Y$. $G$ is called a \textit{digital $(\kappa_{1},\kappa_{2})-$homotopy} between $f$ and $f^{'}$.

\begin{itemize}
	\item for all $x \in X$, $G(x,0)=f(x)$ and $G(x,n) = f^{'}(x)$;

	\item for all $x \in X$, the digital map $G_{x} : [0,n]_{\mathbb{Z}} \rightarrow Y$, defined by $G_{x}(t) = G(x,t)$, is $(2,\kappa_{2})-$continuous, for all $t \in [0,n]_{\mathbb{Z}}$;

	\item for all $t \in [0,n]_{\mathbb{Z}}$, the digital map $G_{t} : X \rightarrow Y$, defined by $G_{t}(x) = G(x,t)$, is $(\kappa_{1},\kappa_{2})-$continuous, for all $x \in X$.
\end{itemize}

\quad Let $X$ be a digital image. If the identity map $X \rightarrow X$ is $(\kappa,\kappa)-$homotopic to a constant map \[c : X \longrightarrow X\]
\hspace*{5.9cm}$x \longmapsto c(x) = c_{0}$, \\
for all $x \in X$, then $(X,\kappa)$ is \textit{$\kappa-$contractible} \cite{Boxer:1999}.

\quad Let $X_{1}$ be a digital image with $\lambda_{1}-$adjacency and let $X_{2}$ be a digital image with $\lambda_{2}-$adjacency. Given two points $(x_{1},x_{2})$ and $(x_{1}^{'},x_{2}^{'})$ in the cartesian product digital image $X_{1} \times X_{2}$. Then \textit{$(x_{1},x_{2})$ and $(x_{1}^{'},x_{2}^{'})$ are adjacent in $X_{1} \times X_{2}$} \cite{BoxKar:2012} if one of the following conditions holds:
\begin{itemize}
	\item $x_{1} = x_{1}^{'}$ and $x_{2} = x_{2}^{'}$; or

	\item $x_{1} = x_{1}^{'}$ and $x_{2}$ and $x_{2}^{'}$ are $\lambda_{2}-$adjacent; or

	\item $x_{1}$ and $x_{1}^{'}$ are $\lambda_{1}-$adjacent and $x_{2} = x_{2}^{'}$; or

	\item $x_{1}$ and $x_{1}^{'}$ are $\lambda_{1}-$adjacent and $x_{2}$ and $x_{2}^{'}$ are $\lambda_{2}-$adjacent.
\end{itemize}

\quad Let $X$ be a digital image. If $f : [0,n]_{\mathbb{Z}} \rightarrow X$ is a $(2,\kappa)-$continuous map such that $f(0)=x$ and $f(n)=x^{'}$, then $f$ is called a \textit{digital path} \cite{Boxer:2006} from $x$ to $x^{'}$ in $X$. A simple closed $\kappa-$curve of $r \geq 4$ points in a digital image $X$ is a sequence $\{g(0), g(1), ... , g(r-1)\}$ of images of the $\kappa-$path $g : [0,r-1]_{\mathbb{Z}} \rightarrow X$ such that $g(m)$ and $g(n)$ are \textit{$\kappa-$adjacent} if and only if $n = (m \pm 1)mod \hspace*{0.2cm}r$ \cite{Boxer:2005}. A \textit{digital surface} \cite{MorgenRosen:1981} is the set of surface points each of which has two adjacent components not in the surface in its neighborhood. Let $\kappa$ be an adjacency relation defined on $\mathbb{Z}^{m}$. A \textit{$\kappa-$neighbor} \cite{Herman:1993} of $x \in \mathbb{Z}^{m}$ is a point in $\mathbb{Z}^{m}$ that is $\kappa-$adjacent to $x$.

\begin{theorem}\cite{ChenRong:2010}
	If $X$ is a closed digital surface, then the genus of the surface is
	\[g = 1 + \frac{(|M_{5}|+2.|M_{6}|-|M_{3}|)}{8},\]

	where $M_{i}$ is a set of points with $i-$neighbors.
\end{theorem}

\quad Let $(X,\kappa)$ be a digital image in $\mathbb{Z}^{2}$. \textit{The digital wedge union $X \vee X$} \cite{Han:2005} is the disjoint union of two $X$ with only one point $x_{0}$ in common and for any different elements $x$ and $y$ in $X$, $x$ and $y$ are not $\kappa-$adjacent to each other except the point $x_{0}$.

\quad Let $PX$ denote the set of all digitally continuous paths $\alpha : [0,n]_{\mathbb{Z}} \rightarrow X$ in $X$. $\pi : PX \rightarrow X \times X$ is a digitally continuous map that takes any digitally continuous path $\alpha$ in $X$ to the pair of its starting and ending points $(\alpha(0),\alpha(n))$.

\begin{definition}\cite{KaracaIs:2018}
	\textit{Digital topological complexity number $TC(X,\kappa)$} is the minimal number $l$ such that $U_{1}, U_{2}, ..., U_{l}$ is a cover of $X \times X$ and for all $1 \leq i \leq l$, there is a digitally continuous map $s_{i} : U_{i} \rightarrow PX$ such that $\pi \circ s_{i} = id_{U_{i}}$. If no such $l$ exists we will set $TC(X,\kappa) = \infty$.
\end{definition}

\quad In the definition of the digital topological complexity number, the digital continuity of $s_{i}$ is required. Due to this reason, the task is to define an adjacency relation between two digital paths. Let $\alpha_{1} : [0,n_{1}]_{\mathbb{Z}} \rightarrow X$ and $\alpha_{2} : [0,n_{2}]_{\mathbb{Z}} \rightarrow X$ be any digitally continuous paths in $X$. Then $\alpha_{1}$ and $\alpha_{2}$ are $\lambda-$connected on $PX$, if for all $t$ times, $\alpha_{1}(t)$ and $\alpha_{2}(t)$ are $\lambda-$connected. Note that $\alpha_{1}$ and $\alpha_{2}$ can have different $t$ times. Without loss of generality, assume that $n_{1} < n_{2}$. In this case, the steps of the shortest path are extended such that $\alpha_{1}(n_{1} + l) = \alpha_{1}(n_{1})$, where $0 \leq l \leq n_{2}-n_{1}$. Hence, $\alpha_{1}$ is synchronized with $\alpha_{2}$.

\begin{definition}\cite{MelihKaraca}
	Let $p : X \longrightarrow X^{'}$ be a digital fibration. \textit{The digital Schwarz genus of $p$} is defined as the minimum number $l$ such that $U_{1}, U_{2}, ..., U_{l}$ is a cover of $X^{'}$ and for all $1 \leq j \leq l$, there is a digitally continuous map $t_{j} : U_{j} \rightarrow X$, such that $p \circ t_{j} = id_{U_{j}}$.
\end{definition}

\begin{definition}\cite{MelihKaraca}
	Let $X$ be any $\kappa$-connected digital image. Let $J_{n}$ be the wedge of $n-$digital intervals $[0,m_{1}]_{\mathbb{Z}}, [0,m_{2}]_{\mathbb{Z}}, ... , [0,m_{n}]_{\mathbb{Z}}$, for a positive integer $n$, where $0_{i} \in [0,m_{i}]$, $i = 1, ... ,n$, are identified. Then \textit{the digital higher topological complexity $TC_{n}(X,\kappa)$} is defined by the digital Schwarz genus of the digital fibration $$e_{n}:X^{J_{n}} \rightarrow X^{n}$$
	\hspace*{5.7cm} $f \longmapsto (f(m_{1})_{1},...,f(m_{n})_{n})$,

	where $(m_{i})_{k}$, $k=1, ..., n$ denotes the endpoints of the $i-$th interval for each $i$.
\end{definition}

\quad Note that for $n=2$, the digital higher topological complexity number coincides with the topological complexity number \cite{MelihKaraca}. The digital higher topological complexity is a homotopy invariant of digital images. $TC_{n}$ is a natural lower bound for $TC_{n+1}$.

\begin{definition}\cite{BorVer:2018}
	Let $X$ be a digital image. Then \textit{the digital Lusternik-Schnirelmann category $cat_{\kappa}(X)$} of $X$ is defined to be the minimum number $l$ such that there is a cover $U_{1}, U_{2}, ..., U_{l}$ of $X$ such that for all $i = 1, ..., l$, each $U_{i}$ is $\kappa-$contractible to a point in $X$.
\end{definition}

\begin{definition}\cite{MelihKaraca2}
	Let $X$ be a digital image with $\kappa-$adjacency and let $(X,\circ)$ be a group. Let $X \times X$ be equipped the minimum of adjacency relation for the cartesian product. $(X,\kappa,\ast)$ is a \textit{$\kappa-$topological group} if the digital maps
	\[\alpha : X \times X \longrightarrow X \hspace*{1.0cm} \text{and} \hspace*{1.0cm} \beta : X \to X,\]
	\hspace*{3.5cm}$(x,x^{'}) \longmapsto x \circ x^{'}$ \hspace*{2.4cm} $x \longmapsto x^{-1}$,

	are digitally continuous, for all $x$, $x^{'} \in X$.
\end{definition}

\begin{theorem}\label{t1}\cite{MelihKaraca2}
	Let $(H,\kappa,\circ)$ be a $\kappa-$topological group such that $(H,\kappa)$ is digitally connected and $n > 1$. Then \[TC_{n}(H,\kappa) = cat_{\kappa_{\ast}}(H^{n-1}),\]
	where $\kappa_{\ast}$ is an adjacency relation for $H^{n-1}$.
\end{theorem}

\quad We use the cohomology groups of the digital image $MSS^{'}_{6}$ \cite{Han:2007} in the next chapter, so we completely need to know these values. As a special example of the computation of cohomology groups of digital images, Proposition \ref{p2} answers it. Let us recall the example with its proof. (See \cite{Gulseli:2014} and \cite{GulseliKaraca:2017} for more examples of digital curves and digital surfaces about computations in details of both homology and cohomology groups of the digital images.)

\begin{proposition}\cite{Gulseli:2014}\label{p2}
	Let $MSS^{'}_{6}$ be a digital image which consists of $8$ points $p_{0}$, $p_{1}$, $p_{2}$, $p_{3}$, $p_{4}$, $p_{5}$, $p_{6}$ and $p_{7}$ in $\mathbb{Z}^{3}$, where
	\begin{eqnarray*}
		&&p_{0} = (1,0,0), p_{1} = (1,1,0), p_{2} = (1,1,1), p_{3} = (1,0,1), \\
		&&p_{4} = (0,0,1), p_{5} = (0,1,1), p_{6} = (0,1,0), p_{7} = (0,0,0).
	\end{eqnarray*}
    The digital cohomology groups of $MSS^{'}_{6}$ are \[H^{q,6}(MSS^{'}_{6}) = \begin{cases} \mathbb{Z}, & q=0 \\ \mathbb{Z}^{5}, & q=1 \\ 0 & q \neq 0,1. \end{cases}\]
\end{proposition}

\begin{proof}
	Let $p_{7} < p_{4} < p_{6} < p_{5} < p_{0} < p_{3} < p_{1} < p_{2}$. $C_{0}^{6}(MSS^{'}_{6})$ and $C_{1}^{6}(MSS^{'}_{6})$ are free abelian groups with bases $0-$simplexes $<p_{0}>, ..., <p_{7}>$ and $1-$simplexes
	\begin{eqnarray*}
	&&e_{0} = <p_{0}p_{1}>, e_{1} = <p_{0}p_{3}>, e_{2} = <p_{1}p_{2}>, e_{3} = <p_{6}p_{1}>\\
	&&e_{4} = <p_{5}p_{2}>, e_{5} = <p_{3}p_{2}>, e_{6} = <p_{4}p_{3}>, e_{7} = <p_{7}p_{4}>\\
	&&e_{8} = <p_{4}p_{5}>, e_{9} = <p_{6}p_{5}>, e_{10} = <p_{7}p_{6}>, e_{11} = <p_{7},p_{0}>,
	\end{eqnarray*}
    respectively. For $q > 1$,  $C_{q}^{6}(MSS^{'}_{6}) = \{0\}$. Then the short exact sequence
    \begin{eqnarray*}
    	0 \stackrel{\partial_{2}}{\longrightarrow}C_{1}^{6}(MSS^{'}_{6}) \stackrel{\partial_{1}}{\longrightarrow}C_{0}^{6}(MSS^{'}_{6}) \stackrel{\partial_{0}}{\longrightarrow} 0
    \end{eqnarray*}
    is obtained. Since
    \begin{eqnarray*}
    	&&C^{0,6}(MSS^{'}_{6}) = Hom(C_{0}^{6}(MSS^{'}_{6}),\mathbb{Z}) \hspace*{0.3cm} \text{and}\\
    	&&C^{1,6}(MSS^{'}_{6}) = Hom(C_{1}^{6}(MSS^{'}_{6}),\mathbb{Z}),
    \end{eqnarray*}
    we have the sequence
    \begin{eqnarray*}
    	0 \stackrel{\delta^{-1}}{\longrightarrow}C^{0,6}(MSS^{'}_{6}) \stackrel{\delta^{0}}{\longrightarrow}C^{1,6}(MSS^{'}_{6}) \stackrel{\delta^{1}}{\longrightarrow} 0.
    \end{eqnarray*}
    It is easy to see that
    \begin{eqnarray*}
    	&&\partial_{1}(e_{0}) = p_{1}-p_{0}, \hspace*{0.2cm} \partial_{1}(e_{1}) = p_{3}-p_{0},\hspace*{0.2cm}  \partial_{1}(e_{2}) = p_{2}-p_{1},\hspace*{0.2cm}  \partial_{1}(e_{3}) = p_{1}-p_{6}, \\
    	&&\partial_{1}(e_{4}) = p_{2}-p_{5},\hspace*{0.2cm}  \partial_{1}(e_{5}) = p_{2}-p_{3},\hspace*{0.2cm}  \partial_{1}(e_{6}) = p_{3}-p_{4},\hspace*{0.2cm}  \partial_{1}(e_{7}) = p_{4}-p_{7}, \\
    	&&\partial_{1}(e_{8}) = p_{5}-p_{4},\hspace*{0.2cm}  \partial_{1}(e_{9}) = p_{5}-p_{6},\hspace*{0.2cm}  \partial_{1}(e_{10}) = p_{6}-p_{7},\hspace*{0.2cm}  \partial_{1}(e_{11}) = p_{0}-p_{7}.
    \end{eqnarray*}
    So we find $0-$cochains
    \begin{eqnarray*}
    	&&\delta^{0}p_{0}^{*} = -e_{0} - e_{1} + e_{11}, \hspace*{0.2cm} \delta^{0}p_{1}^{*} = e_{0} - e_{2} + e_{3}, \hspace*{0.2cm} \delta^{0}p_{2}^{*} = e_{2} + e_{4} + e_{5}, \\
    	&&\delta^{0}p_{3}^{*} = e_{1} - e_{5} + e_{6}, \hspace*{0.2cm} \delta^{0}p_{4}^{*} = -e_{6} + e_{7} - e_{8}, \hspace*{0.2cm} \delta^{0}p_{5}^{*} = -e_{4} + e_{8} + e_{9}, \\
    	&&\delta^{0}p_{6}^{*} = -e_{3} - e_{9} + e_{10}, \hspace*{0.2cm} \delta^{0}p_{7}^{*} = -e_{7} - e_{10} - e_{11}.
    \end{eqnarray*}
    Moreover, we get
    \begin{eqnarray*}
    	\delta^{0}(\displaystyle \sum_{i=1}^{7}n_{i}p_{i}^{*}) &=& e_{0}(-n_{0} + n_{1}) + e_{1}(-n_{0} + n_{3}) + e_{2}(-n_{1} + n_{2}) + e_{3}(n_{1} - n_{6})\\
    	&+& e_{4}(n_{2} - n_{5}) + e_{5}(n_{2} - n_{3}) + e_{6}(n_{3} - n_{4}) + e_{7}(n_{4} - n_{7})\\
    	&+& e_{8}(-n_{4} + n_{5}) + e_{9}(n_{5} - n_{6}) + e_{10}(n_{6} - n_{7}) + e_{11}(n_{0} - n_{7}).
    \end{eqnarray*}
    If $\delta^{0}(\displaystyle \sum_{i=1}^{7}n_{i}p_{i}^{*}) = 0$, then we find $n_{0} = n_{1} = ... = n_{7} = n$. This shows that $Ker\delta^{0} = \mathbb{Z}$. Therefore, we have that $Z^{0,6}(MSS^{'}_{6}) \cong \mathbb{Z}$. Since $Im\delta^{-1} = \{0\}$, we have that $B^{0,6}(MSS^{'}_{6}) \cong \{0\}$. Hence, we get $H^{0,6}(MSS^{'}_{6}) \cong \mathbb{Z}$. In addition, we have that
    \begin{eqnarray*}
    B^{1,6}(MSS^{'}_{6}) = Im\delta^{0} &=& \{t_{0}e_{0} + t_{1}e_{1} + t_{2}e_{2} + t_{3}e_{3} + t_{4}e_{4} \\
    &+& (t_{2} - t_{1})e_{5}, + t_{5}e_{6} + t_{6}e_{7} + (-t_{1} + t_{2} - t_{4} + t_{5})e_{8} \\
    &+& (t_{2} + t_{3} - t_{4})e_{9} + (t_{0} - t_{1} - t_{3} + t_{5} + t_{6})e_{10} \\
    &+& (- t_{1} + t_{5} + t_{6})e_{11} \hspace*{0.2cm}| \hspace*{0.2cm} i = 0,1,...,6, \hspace*{0.2cm} \forall t_{i} \in \mathbb{Z}\} \cong \mathbb{Z}^{7}.
    \end{eqnarray*}
    By the definition, we see that $Z^{1,6}(MSS^{'}_{6}) = Ker\delta^{1} \cong \mathbb{Z}^{12}$. This implies that $H^{1,6}(MSS^{'}_{6}) = Z^{1,6}(MSS^{'}_{6}) / B^{1,6}(MSS^{'}_{6}) \cong \mathbb{Z}^{5}$. Finally, we get our result
    \begin{eqnarray*}
    	H^{q,6}(MSS^{'}_{6}) = \begin{cases} \mathbb{Z}, & q=0 \\ \mathbb{Z}^{5}, & q=1 \\ 0 & q \neq 0,1. \end{cases}
    \end{eqnarray*}
\end{proof}

\quad Before ending the section, we list some results on computing the topological complexity numbers or the higher topological complexity numbers in topological spaces. Each of the results is invalid in digital images. The counterexamples of the digital images are exhibited in Section \ref{section3}.

\begin{proposition}\cite{Rudyak:2010}\label{p1}
	Let $\Delta_{n} : X \rightarrow X^{n}$ be the diagonal map. If there exist $v_{i} \in H^{\ast}(X^{n};M_{i})$, $i = 1, ... ,k$, for which $(\Delta_{n})_{\ast}v_{i} = 0$ and $v_{1} \smile v_{2} \smile ... \smile v_{k} \neq 0$ in the cohomology $H^{\ast}(X^{n};M_{1} \otimes M_{2} \otimes ... \otimes M_{k})$, then $TC_{n}(X) \geq k+1$.
\end{proposition}

\begin{theorem}\cite{Farber:2004} \label{t2}
	Let $X$ be a connected graph. Then
	\[TC(X) =
	\begin{cases}
	1, & \text{if} \hspace*{0.2cm}b_{1}(X) = 0, \\ 2, & \text{if} \hspace*{0.2cm} b_{1}(X) = 1, \\ 3, & \text{if} \hspace*{0.2cm} b_{1}(X) \geq 2,
	\end{cases}\]
	where $b_{1}(X)$ denotes the first Betti number of $X$.
\end{theorem}

\begin{lemma}\label{l1}\cite{Farber:2004}
	Let $X$ denote the wedge of $k$ spheres $S^{n}$. Then
	\[TC(X) =
	\begin{cases}
	2, & \text{if} \hspace*{0.2cm} k=1 \hspace*{0.2cm} \text{and} \hspace*{0.2cm} n \hspace*{0.1cm} \text{is} \hspace*{0.1cm} \text{odd}, \\ 3, & \text{if} \hspace*{0.2cm} \text{either} \hspace*{0.2cm} k>1, \hspace*{0.2cm} \text{or} \hspace*{0.2cm} n \hspace*{0.1cm} \text{is} \hspace*{0.1cm} \text{even}.
	\end{cases}\]
\end{lemma}

\begin{example}\label{e2}\cite{Farber:2006}
	Let $X = \sum_{g}$ be a compact orientable surface of genus $g$. Then
	\[ TC(X) = \begin{cases}
	3, & \text{if} \hspace*{0.2cm} g \leq 1 \\
	5, & \text{if} \hspace*{0.2cm} g > 1.
	\end{cases}\]
\end{example}
\section{MAIN RESULTS}\label{section3}
\quad The aim of this section is to emphasize the differences between the topological spaces and the digital images in the sense of the objects of topological robotics. The results and the examples in this section wish to indicate that the studies of the topological complexity numbers are so valuable and can be transfered into the digital images to get interesting results. This does not lose the value of the studies, contrarily it enriches the studies by carrying into the different platform. The results can be instructive for the future study of the topological complexity in digital image processing.

\quad First, we show that Proposition \ref{p1} is not valid in digital images.

\begin{example}\label{e1}
	Take $n=3$ and $X = [0,1]_{\mathbb{Z}}$ in the Proposition \ref{p1}. Let $M$ be a field. The diagonal map $\Delta_{3} : (X,2) \rightarrow (MSS^{'}_{6},6)$ induces the digital homomorphism on digital cohomology with the coefficent $\mathbb{M}$ for the first dimension \[(\Delta_{3})_{\ast} : H^{1,6}(MSS^{'}_{6};\mathbb{M}) \rightarrow H^{1,2}(X;\mathbb{M}).\]
	Proposition \ref{p2} tells us that $(\Delta_{3})_{\ast}$ is basically the digital map $\mathbb{M}^{5} \rightarrow 0$. This shows that $ker((\Delta_{3})_{\ast}) = \mathbb{M}^{5}$. For any nonzero element $(v_{1}, v_{2}, v_{3}, v_{4}, v_{5})$ of $\mathbb{M}^{5}$, we have that $(\Delta_{3})_{\ast} (v_{1}, v_{2}, v_{3}, v_{4}, v_{5}) = 0$. Hence, we obtain $k \geq 1$. On the other hand, we shall show that $TC_{3}(X,2) = 1$. $([0,1]_{\mathbb{Z}},2,\circ)$ is a $2-$topological group, where $\circ$ is defined by
	\[\circ (a,b) = \begin{cases}
	0, & a=b \\ 1, & a \neq b,
	\end{cases}\]
	for all $a$, $b \in [0,1]_{\mathbb{Z}}$. By Theorem \ref{t1}, $TC_{3}(X,2) = cat_{4}(X^{2})$. Since $X^{2}$ is $4-$contractible, we obtain $TC_{3}(X,2) = 1$. As a result, $TC_{3}(X,2) < k+1$.
\end{example}

 \quad As a result of this example, [Proposition 3.2,\cite{GrantLuptonOprea:2013}] becomes meaningless in digital images because the diagonal map $\Delta_{n}$ cannot be identified with the digital cup product homomorphism $\cup_{n}(X)$ in [Definition 3.1,\cite{GrantLuptonOprea:2013}]. We shall explain it with an example in digital images:

\begin{example}
	Let $\mathbb{M}$ be a field. Consider the digital cohomology induced by the diagonal map $\Delta_{3}$, with the coefficient $M$ for the first dimension,  given in Example \ref{e1}. Although $(\Delta_{3})_{\ast}$ is the digital map $\mathbb{M}^{5} \rightarrow 0$, the digital cup product homomorphism \[\smile_{3} : H^{1,2}(X;\mathbb{M}) \otimes_{\mathbb{M}} H^{1,2}(X;\mathbb{M}) \otimes_{\mathbb{M}} H^{1,2}(X;\mathbb{M}) \rightarrow H^{3,2}(X;\mathbb{M})\]
	is the digital map $0 \otimes_{\mathbb{M}} 0 \otimes_{\mathbb{M}} 0 \rightarrow 0$. This shows that $Ker(\smile_{3}) = 0$. Hence, $Ker(\smile_{3})$ does not coincidence with $Ker((\Delta_{3})_{\ast})$. Thus, we conclude that \[nil(Ker(\smile_{3})) < TC_{3}(X,2) < nil(Ker(\Delta_{3})_{\ast}).\]
\end{example}

\quad In the next example we show that Theorem \ref{t2} does not hold for digital images for the case $b_{1}(X) \geq 2$.

\begin{figure*}[h]
	\centering
	\includegraphics[width=0.40\textwidth]{g1.png}
	\caption{The digital image $X$.}
	\label{fig1:figure1}
\end{figure*}
\begin{example}\label{e3}
	Let $X$ be a digital image as shown in the Figure \ref{fig1:figure1}. The first Betti number of $X$ is $2$, because $X$ has two digital quadrilateral holes. On the other hand, we shall show that $TC(X,4) = 2$. $X$ is not $4-$contractible, so $TC(X,4) > 1$. Let $\alpha = \{a_{1}, a_{15}, a_{14}, a_{13}, a_{5}, a_{6}, a_{7}, a_{8}, a_{9}\}$ and $\beta = \{a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{12}, a_{11}, a_{10}, a_{9}\}$ be the subsets of $X$ as shown in the Figure \ref{fig2:figure2}.
	\begin{figure*}[h]
		\centering
		\includegraphics[width=0.90\textwidth]{g2.png}
		\caption{The digital images $\alpha$ on the left and $\beta$ on the right in $X$.}
		\label{fig2:figure2}
	\end{figure*}
     $X \times X$ can be written as the union of the following sets
    \begin{eqnarray*}
    	&&U_{1} = \{(x,y) \in X \times X \hspace*{0.2cm}|\hspace*{0.2cm} (x,y) \in \beta \hspace*{0.2cm} \text{or} \hspace*{0.2cm} (x,y) \in \beta \times \alpha \hspace*{0.2cm} \text{or} \hspace*{0.2cm} (x,y) \in \alpha \times \beta\} \\
    	&&\hspace*{4.0cm}\text{and}\\
    	&&U_{2} = \{(x,y) \in X \times X \hspace*{0.2cm}|\hspace*{0.2cm} (x,y) \in \alpha\}.
    \end{eqnarray*}
    By the definition, the minimal number is $2$ for the digital topological complexity number of $X$. Finally, we conclude that $TC(X,4) = 2$.
\end{example}

\begin{theorem}
	Let $X$ be a digitally connected digital curve and $b_{1}(X)$ denote the first Betti number of $X$. Then
	\[TC(X) =
	\begin{cases}
	1, & \text{if} \hspace*{0.2cm}b_{1}(X) = 0, \\ 2, & \text{if} \hspace*{0.2cm} b_{1}(X) \geq 1.
	\end{cases}\]
\end{theorem}
\begin{figure*}[h]
	\centering
	\includegraphics[width=1.00\textwidth]{g3olacak.png}
	\caption{The left one is the digital image with the Betti number $n > 1$. The red and blue lines describe the paths passing through the elements of $T_{1}$ and $T_{2}$, respectively.}
	\label{fig10:figure10}
\end{figure*}
\begin{proof}
	Let $X$ be a digitally connected digital curve. If $b_{1}(X) = 0$, then $X$ has no quadrilateral holes in it. This means that $X$ is $k-$contractible. Hence, we find that $TC(X,\kappa) = 1.$ If $b_{1}(X) = 1$, there is only one hole in $X$ and we cover $X$ by two sets such like that in Example \ref{e3}. The digital homotopy invariance property of the digital topological complexity number concludes that $TC(X,\kappa) = 2$. Consider the case $b_{1}(X) > 1.$ Let $b_{1}(X) = n$, where $n > 1$. Then $X$ is covered by two sets $T_{1}$ and $T_{2}$, where $T_{i} = W_{i} \times W_{i}$ (see Figure \ref{fig10:figure10} for the images $W_{i}$), for $i=1,2$. By the homotopy invariance property, we get $TC(X,\kappa) = 2$, for $b_{1}(X)>1$.
\end{proof}

\quad The following example shows that Lemma \ref{l1} is not true in the digital meaning of topological complexity.

\begin{example}
	 Take both the numbers $k$ and $n$ as $2$ in Lemma \ref{l1}. Then we have the space $S^{2} \vee S^{2}$. The digitally equivalent of this space is digitally isomorphic to the digital image $X = MSC^{'}_{6} \vee MSC^{'}_{6}$ with the wedge point $(0,0,0)$ as shown in Figure \ref{fig3:figure3}. Since the digital topological complexity is a digital homotopy invariant, we observe that $TC(MSC^{'}_{6} \vee MSC^{'}_{6},6) = 3$. On the other hand, $MSC^{'}_{6} \vee MSC^{'}_{6}$ is $6-$contractible. Indeed, the homotopy between the identity map on $MSC^{'}_{6} \vee MSC^{'}_{6}$ and the constant map at the point $(0,0,0)$ has $3$ steps. For $t \in [0,2]_{\mathbb{Z}}$, we explain how the contraction homotopy
	 \begin{eqnarray*}
	 	H : (MSC^{'}_{6} \vee MSC^{'}_{6}) \times [0,3]_{\mathbb{Z}} \rightarrow MSC^{'}_{6} \vee MSC^{'}_{6}
	 \end{eqnarray*}
     works (see Figure \ref{fig4:figure4}). For the time $t=0$, each point of $MSC^{'}_{6} \vee MSC^{'}_{6}$ is located in its original place. For the time $t=1$, the upper $MSC^{'}_{6}$ is deformed to the square whose points are $b_{1}$, $b_{2}$, $b_{3}$ and $(0,0,0)$. Similarly, for the lower $MSC^{'}_{6}$, we have the square whose points are $b_{4}$, $b_{5}$, $b_{6}$ and $(0,0,0)$. For the time $t=2$, the squares are deformed to the point $(0,0,0)$. Consequently, this is a contradiction because the $6-$contractibility of the image gives us that $TC(MSC^{'}_{6} \vee MSC^{'}_{6},6) = 1$.
	 \begin{figure*}[h]
	 	\centering
	 	\includegraphics[width=0.40\textwidth]{g3.png}
	 	\caption{The digital image $MSC^{'}_{6} \vee MSC^{'}_{6}$ and the wedge point $(0,0,0)$.}
	 	\label{fig3:figure3}
	 \end{figure*}
     \begin{figure*}[h]
     	\centering
     	\includegraphics[width=0.70\textwidth]{g4.png}
     	\caption{The digital contraction of $MSC^{'}_{6} \vee MSC^{'}_{6}$.}
     	\label{fig4:figure4}
     \end{figure*}
\end{example}

\begin{corollary}
	Let $(X,\kappa)$ be a digital image that consists of the wedge of $r$ digital cube in $\mathbb{Z}^{n}$, for $n>1$. Then
	\[TC(X,\kappa) =
	\begin{cases}
	1, & \text{if} \hspace*{0.2cm} n=3 \hspace*{0.2cm} \text{or} \hspace*{0.2cm} n=2 \hspace*{0.2cm} \text{and} \hspace*{0.2cm} \kappa = 8 \\ 2, & \text{if} \hspace*{0.2cm} n=2 \hspace*{0.2cm} \text{and} \hspace*{0.2cm} \kappa = 4 \\
	\end{cases}\]
\end{corollary}

\begin{proof}
	If $n=3$ and $r=1$, then the topological complexity number of $X$ is the same as the topological complexity number of the digital image $MSC^{'}_{6}$. Since this is a $6-$contractible space, the topological complexity of $X$ is independence from the number $r$ and the adjacencies in $\mathbb{Z}^{3}$. If $n=2$, then the topological complexity number of $X$ is equal to the topological complexity number of $MSC_{4}$. By $TC(MSC_{4},4) = 2$ and $TC(MSC_{4},8) = 1$, the result holds.
\end{proof}

\quad The next result shows that Example \ref{e2} is not true for digital images.

\begin{example}\label{e4}
	Let $X$ and $Y$ be two digital images as in Figure \ref{fig7:figure7}.
	\begin{figure*}[h]
		\centering
		\includegraphics[width=0.70\textwidth]{g7.png}
		\caption{The digital images with genus $1$ and genus $2$, respectively.}
		\label{fig7:figure7}
	\end{figure*}
    Chen \cite{Chen:2004} shows that $X$ is an example of the digital closed surface with genus $1$ and $Y$ is an example of the digital closed surface with genus $2$. By Example \ref{e2}, the digital topological complexity number of $X$ is $3$ and the topological complexity number of $Y$ is $5$. However, we shall show this is a contradiction.
    \begin{figure*}[h]
    	\centering
    	\includegraphics[width=0.50\textwidth]{g8.png}
    	\caption{Divide the digital image $X$ into $2$ parts.}
    	\label{fig8:figure8}
    \end{figure*}
    Take $U_{1}$ and $U_{2}$ as in Figure \ref{fig8:figure8}. If we define $V_{i} = U_{i} \times U_{i}$, for all $i=1,2$, then we get $TC(X,6) = 2$.
    Similarly, take $T_{1}$, $T_{2}$ and $T_{3}$ as in Figure \ref{fig9:figure9}. If we define $W_{i} = T_{i} \times T_{i}$, for all $1 \leq i \leq 3$, then we obtain that $TC(Y,6) = 3$.
    \begin{figure*}[h]
    	\centering
    	\includegraphics[width=0.70\textwidth]{g9.png}
    	\caption{Divide the digital image $Y$ into $3$ parts.}
    	\label{fig9:figure9}
    \end{figure*}
\end{example}

\begin{corollary}
	Let $X$ be a digital simple closed surface of genus $g$ with $6-$adjacency. Then
	\[TC(X,6) = \begin{cases}
	1, & \text{if} \hspace*{0.2cm} g= 0 \\
	2, & \text{if} \hspace*{0.2cm} g = 1 \\
	3, & \text{if} \hspace*{0.2cm} g = 2.
	\end{cases}\]
\end{corollary}

\begin{proof}
	It is enough to show that $TC(X,6) = 1$, when $g=0$. The image $MSC^{'}_{6}$ is an example of a digital surface of genus $0$. It is clear that $TC(MSC^{'}_{6},6) = 1$. The fact that the digital topological complexity number is a homotopy invariance of digital images gives the desired result.
\end{proof}

\section{Conclusion}
\quad The subjects of robotics are widely studied in every aspect of science. Algebraic topology has put these studies on a different and effective ground by means of configuration spaces. Our purpose in the future is to use digital topology instead of ordinary topology and obtain remarkable results in the development of computer sciences. The evaluation of robotics' works in digital topology is still very new. First, the differences and the similarities should be determined. Therefore, determining the differences between the topological complexity number of a topological space and the digital topological complexity number of a digital image is the main goal of this study.

\quad We begin with considering how the relation between cohomological cup product homomorphism and the diagonal map works for digital images. Second, we take a connected graph as a topological space such that the first Betti number of the graph is greater than $1$ and we observe the result in the digital setting. Our next example is the digital interpretation of the topological complexity number of the wedge of $k-$spheres. Finally, we deal with a compact orientable surface of genus $g$. After giving a counterexample in digital images, we reveal how the digital topological complexity numbers of the digital simple closed surface with genus $g$ works in digital images. \\

\acknowledgment{The first author is granted as fellowship by the Scientific and Technological Research Council of Turkey TUBITAK-2211-A. In addition, this work was partially supported by Research Fund of the Ege University (Project Number: FDK-2020-21123)}

config: arxiv


TITLE: How can I compute this:$I=\int_0^\infty \frac{\ln(2x)^2 \cosh x} {1+\cosh 2x} dx$
QUESTION [1 upvotes]: How can I solve this integral? $$I=\int_0^\infty \frac{\ln(2x)^2 \cosh x} {1+\cosh 2x} dx$$ I get this: $I=I_1+I_2$ and $I_1=\int_0^\infty\frac{\ln 2}{e^x+e^{-x}}dx=\pi/2$ and $I_2=\int_0^\infty\frac{\ln x}{e^x+e^{-2x}}dx$ and I can't solve $I_2$. Any help would be appreciated.

REPLY [2 votes]: After @J.G.'s answer
$$\beta(1)=\frac \pi 4$$
$$\beta'(1)=-\frac{1}{4} \left(\gamma _1\left(\frac{1}{4}\right)-\gamma
   _1\left(\frac{3}{4}\right)+2 \pi  \log (2)\right)$$
$$\beta''(1)=\frac{1}{4} \left(\gamma _2\left(\frac{1}{4}\right)-\gamma
   _2\left(\frac{3}{4}\right)+4 \left(\gamma _1\left(\frac{1}{4}\right)-\gamma
   _1\left(\frac{3}{4}\right)\right) \log (2)+4 \pi  \log ^2(2)\right)$$
If I am not wrong
$$I_2=\frac{1}{18} \left(-3 \log ^2(2)+3 \log (2) \log (3)+\sqrt{3} \pi  \left(\log
   \left(\frac{128}{27}\right)+8 \log (\pi )-12 \log \left(\Gamma
   \left(\frac{1}{3}\right)\right)\right)\right)$$


text:
\begin{document}

\maketitle

\begin{abstract}
We develop an approach for estimating models described via conditional moment restrictions, with a prototypical application being non-parametric instrumental variable regression. We introduce a min-max criterion function, under which the estimation problem can be thought of as solving a zero-sum game between a modeler who is optimizing over the hypothesis space of the target model and an adversary who identifies violating moments over a test function space. We analyze the statistical estimation rate of the resulting estimator for arbitrary hypothesis spaces, with respect to an appropriate analogue of the mean squared error metric, for ill-posed inverse problems. We show that when the minimax criterion is regularized with a second moment penalty on the test function and the test function space is sufficiently rich, then the estimation rate scales with the critical radius of the hypothesis and test function spaces, a quantity which typically gives tight fast rates. Our main result follows from a novel localized Rademacher analysis of statistical learning problems defined via minimax objectives. We provide applications of our main results for several hypothesis spaces used in practice such as: reproducing kernel Hilbert spaces, high dimensional sparse linear functions, spaces defined via shape constraints, ensemble estimators such as random forests, and neural networks. For each of these applications we provide computationally efficient optimization methods for solving the corresponding minimax problem (e.g. stochastic first-order heuristics for neural networks). In several applications, we show how our modified mean squared error rate, combined with conditions that bound the ill-posedness of the inverse problem, lead to mean squared error rates. We conclude with an extensive experimental analysis of the proposed methods.
\end{abstract}

\etocdepthtag.toc{mtchapter}
\etocsettagdepth{mtchapter}{subsection}
\etocsettagdepth{mtappendix}{none}

\section{Introduction}
\blfootnote{A very preliminary version of this work appeared as \emph{Adversarial Generalized Method of Moments} (see \url{https://arxiv.org/abs/1803.07164})}
Understanding how policy choices affect social systems requires an understanding of the underlying causal relationships between them.

To measure these causal relationships, social scientists look to either field experiments, or quasi-experimental variation in observational data.
Most observational studies rely on assumptions that can be formalized in moment conditions.
This is the basis of the estimation approach known as generalized method of moments (GMM) \citep{Hansen1982}.

While GMM is an incredibly flexible estimation approach, it suffers from some drawbacks.
The underlying independence (randomization) assumptions often imply an infinite number of moment conditions.
Imposing all of them is infeasible with finite data, but it is hard to know which ones to select.
For some special cases, asymptotic theory provides some guidance, but it is not clear that this guidance translates well when the data is finite and/or the models are non-parametric.
Given the increasing availability of data and new machine learning approaches, researchers and data scientists may want to apply adaptive non-parametric learners such as reproducing kernel Hilbert spaces, high-dimensional regularized linear models, neural networks and random forests to these GMM estimation problems, but this requires a way of finding \emph{solutions to the moment conditions within complex hypothesis classes imposed by the learner} and selecting moment conditions \emph{that are adapted to the hypothesis class of the learner}.

Most recent theoretical developments in machine learning and high-dimensional statistics are founded on statistical learning theory: formulate a loss function (typically strongly convex with respect to the output of the hypothesis), whose minimizer over the hypothesis space is the desired solution; typically referred to as an $M$-estimator. Being able to frame the problem as an $M$-estimation problem with a strongly convex function, leads to many desirable properties
: i) tight generalization bounds and mean squared error rates based on localized notions of statistical complexity can be invoked to provide tight and fast finite sample rates with minimal assumptions \citep{bartlett2005local,wainwright2019high}, ii) regularization can be invoked to make the estimation adaptive to the complexity of the true hypothesis space, without knowledge of that complexity \citep{Lecue2018,lecue2017regularization,negahban2012}, iii) the computational problem can be typically efficiently solved via first order methods that can scale massively \citep{agarwal2014reliable,rahimi2008random,le2013building,sra2012optimization,Bottou2007}. This formulation is seemingly at odds with the method of moments language, as many times the moment conditions do not correspond to the gradient of some loss function and this problem is exacerbated in the case of non-parametric endogenous regression problems (i.e. when the instruments in the observational study does not coincide with the treatments). The problem is: \emph{Can we develop an analogue of modern statistical learning theory of $M$-estimators, for non-parametric problems defined via moment restrictions?}

Our starting point is a set of conditional moment restrictions:
\begin{equation}\label{eqn:cond-moments}
    \E[y - h(x) \mid z] = 0
\end{equation}
where $y$ is an outcome of interest, $x$ is a vector of treatments and $z$ is a vector of instruments.

To obtain a criterion function, we first move to an unconditional moment formulation, where the moment restrictions are products of the moment conditions and test functions in the instruments.
We then take as our criterion function the maximum moment deviation over the set of test functions, where the set of test functions is potentially infinite.
\begin{equation}
\label{eqn:minimax-form}
    h_0 = \arginf_{h\in \mcH} \sup_{f\in \mcF} \E[(y - h(x)) f(z)] =: \Psi(h, f)
\end{equation}

We show that as long as the set of test functions $\mcF$ contains all functions of the form $f(z) = \E[h(x) - h'(x) \mid z]$ for $h,h'\in \mcH$, then such an estimator achieves a projected MSE rate that scales with the critical radius of the function classes $\mcF$, $\mcH$ and their tensor product class (i.e. functions of the form $f(z)\cdot h(x)$, with $f\in \mcF$ and $h\in \mcH$). The critical radius captures information theoretically optimal rates for many function classes of interest and thereby this main theorem can be used to derive tight estimation rates for many hypothesis spaces. Moreover, if the regularization terms relate to the squared norms of $h, f$ in their corresponding spaces, then the estimation error scales with the norm of the true hypothesis, without knowledge of this norm.

We offer several applications of our main theorems for several hypothesis spaces of practical interest, such as reproducing kernel Hilbert spaces (RKHS), sparse linear functions, functions defined via shape restrictions, neural networks and random forests.
For many of these estimators, we offer optimization algorithms with performance guarantees.
As we illustrate in extensive simulation studies, different estimators are best in different regimes.

\paragraph{Related work}
The non-parametric IV problem has a long history in econometrics \cite{newey2003instrumental,blundell2007semi,chen2012estimation,chen2018optimal,hall2005nonparametric,horowitz2007asymptotic,horowitz2011applied,darolles2011nonparametric,chen2009efficient}. Arguably the closest to our work is that of \cite{chen2012estimation}, who consider estimation of non-parametric function classes and estimation via the method of sieves and a penalized minimum distance estimator of the form: $\min_{h \in \mcH} \E[\E[y-h(x)\mid z]^2] + \lambda R(h)$, where $R(h)$ is a regularizer. As we show in \Cref{app:related}, our estimator can be interpreted asymptotically as a minimum distance estimator, albeit our estimation method applies to arbitrary function classes and non just linear sieves.
There is also a growing body of work in the machine learning literature on the non-parametric instrumental variable regression problem \cite{deepiv,bennett2019deep,singh2019kernel,muandet2019dual,muandet2020kernel}. Our work has several features that draw connections to each of these works, e.g. \cite{bennett2019deep,muandet2019dual,muandet2020kernel} also use a minimax criterion and \cite{bennett2019deep,muandet2019dual} also impose some form of variance penalty on the test function. We discuss subtle differences in \Cref{app:related}. Moreover, \cite{singh2019kernel,muandet2019dual} also study RKHS hypothesis spaces and \cite{deepiv,bennett2019deep} also study neural net hypothesis spaces. None of these prior works provide finite sample estimation error rates for arbitrary hypothesis spaces and typically only show consistency for the particular hypothesis space analyzed (with the exception of \cite{singh2019kernel}, who provide finite sample rates for RKHS spaces, under further conditions on the smoothness of the true hypothesis). In \Cref{app:related} we offer a more detailed exposition on the related work and how it relates to our main results.

\section{Preliminary Definitions}

We consider the problem of estimating a flexible econometric model that satisfies a set of conditional moment restrictions presented in \Cref{eqn:cond-moments} (see also Appendix~\ref{app:beyond-iv}),
where $z\in \mcZ\subseteq \R^{d}$, $X \in \mcX \subseteq \R^p$, $y\in \R$, $h\in \mcH \subseteq (\mcX \to \R)$ for $\mcH$ a hypothesis space. For simplicity of notation we will also denote with $\psi(y; h(x))=y - h(x)$.
The truth is some model $h_0$ that satisfies all the moment restrictions.

We assume we have access to a set of $n$ i.i.d. sample points $\{v_i:=(y_i,x_i, z_i)\}_{i=1}^n$ drawn from some unknown distribution $\cD$ that satisfies the moment condition in Equation~\cref{eqn:cond-moments}.
We will analyze estimators that optimize an empirical analogue of the minimax objective presented in the introduction, potentially adding norm-based penalties $\Phi: \mcF\to \R_+$, $R: \mcH\to \R_+$:
\begin{equation}
    \hat{h} := \argmin_{h\in \mcH} \sup_{f\in \mcF} \Psi_n(h, f) - \lambda\, \Phi(f) + \mu\, R(h)
\end{equation}
where $\Psi_n(h, f) := \frac{1}{n} \sum_{i=1}^n \psi(y_i; h(x_i))\, f(z_i)$.

We assume that $\mcH$ and $\mcF$ are classes of bounded functions on their corresponding domains and, without loss of generality, their image is a subset of $[-1, 1]$. Similarly, we will also assume that $y\in [-1,1]$. The results of this section hold for a general bounded range $[-b, b]$ via standard re-scaling arguments with an extra multiplicative factor of $b$. Moreover, we will assume that $\mcF$ is a symmetric class, i.e. if $f\in \mcF$ then $-f \in \mcF$. Moreover, we will assume that $\mcH$ and $\mcF$ are equipped with norms $\|\cdot\|_{\mcH}, \|\cdot\|_{\mcF}$ and we will define the norm-constrained classes and for any function class $\mcG$ we let $\mcG_B= \{g\in \mcG: \|g\|\leq B\}$, be the $B$ bounded norm subset of the class.

Our estimation target is good generalization performance with respect to the projected residual mean squared error (RMSE), defined as the RMSE projected onto the space of instruments:
\begin{equation}
\label{eqn:cond-mse}
    \textstyle{\|T(\hat{h}-h_0)\|_2 := \sqrt{\E\left[\left(\E[\hat{h}(x) - h_0(x) \mid z] \right)^2\right]}} \tag{Projected RMSE}
\end{equation}
where $T:\mcH \to \mcF$ is the linear operator defined as $T h := \E[h(X)\mid Z=\cdot]$.
This performance metric is appropriate given the ill-posedness problem well known in this setting; imposing further conditions on the strength of the correlation between the treatments and instruments (instrument strength) allows one to, translate bounds on the projected RMSE to bounds on the RMSE (see e.g. \cite{chen2012estimation} and other references in the applications below).

We start by defining some preliminary notions from empirical process theory that are required to state our main results. Let $\mcG$ a class of uniformly bounded functions $g: \mcV \to [-1, 1]$ from some domain $\mcV$ to $[-1, 1]$. The \emph{localized Rademacher complexity} of the function class is defined as:
$\mcR_n(\delta; \mcG) = \E_{\{\epsilon_i\}_{i=1}^n, \{v_i\}_{i=1}^n}\left[\sup_{\substack{g\in \mcG\\ \|g\|_2\leq \delta}} \left| \frac{1}{n} \sum_{i=1}^n \epsilon_i g(v_i)\right| \right]$,
where $\{v_i\}_{i=1}^n$ are i.i.d. samples from some distribution $D$ on $\mcV$ and $\{\epsilon_i\}_{i=1}^n$ are i.i.d. Rademacher random variables taking values equiprobably in $\{-1, 1\}$. We will also denote with $\mcR_n(\mcG)$, the un-restricted Rademacher complexity, i.e. $\delta=\infty$.

We denote with $\|\cdot\|_2$ the \emph{$\ell_2$-norm} with respect to the distribution $D$, i.e. $\|g\|_2=\sqrt{\E_{v\sim D}[g(v)^2]}$, and analogously we define the \emph{empirical $\ell_2$-norm} as $\|g\|_{2,n}=\sqrt{\frac{1}{n}\sum_i g(v_i)^2}$. In our context, where $v=(y, x, z)$, when functions take as input subsets of the vector $v$, then we will overload notation and let $\|\cdot\|_2$ and $\|\cdot\|_{2,n}$ denote the population and sample $\ell_2$ norms with respect to the marginal distribution of the corresponding input, e.g., if $h$ is a function of $x$ alone and $f$ a function of $z$ alone, we write $\|h\|_2=\sqrt{\E_{x}[h(x)^2]}$, $\|f\|_2=\sqrt{\E_{z}[f(z)^2]}$, and $\|h f\|_2=\sqrt{\E_{x, z}[h(x)^2\, f(z)^2]}$.

A function class $\mcG$ is said to be \emph{symmetric} if $g\in \mcG \implies -g \in \mcG$.
Moreover, it is said to be \emph{star-convex} if: $g\in \mcG \implies r\, g \in \mcG, \forall r\in [0,1]$.
The \emph{critical radius} $\delta_n$ of the function class $\mcG$ is any solution to the inequality
$\mcR_n(\delta; \mcG) \leq \delta^2$.

\section{Main Theorems}
\label{sec:estimation}

We show that, if the function space $\mcF_{U}$ contains projected differences of hypothesis spaces $h\in \mcH_B$, with some benchmark hypothesis $h_*\in \mcH_B$, i.e. $T(h-h_*)\in \mcF_U$, then a regularized minimax estimator can achieve estimation rates that are of the order of the projected root-mean-squared-error of the benchmark hypothesis $h_*$ and the critical radii of (i) the function class $\mcF_{3U}$ and (ii) a function class $\mcG$ that consists of functions of the form: $q(x)\cdot Tq(z)$, for $q=h-h_*$.
The projected root mean squared error of the benchmark class can be understood as the \emph{approximation error} or \emph{bias} of the hypothesis space $\mcH_B$, and the critical radius can be understood as the \emph{sampling error} or \emph{variance} of the estimate. If $h_0\in \mcH_B$, then the \emph{approximation error} is zero.
We present a slightly more general statement, where we also allow for $\mcF_U$ to not exactly include $T(h-h_*)$, but rather functions that are close to it with respect to the $\ell_2$ norm. For this reason, we will need to define the following slightly more complex hypothesis space, in order to state our main theorem:
\begin{align}\label{eqn:reg-class-G}
\hat{\mcG}_{B, U} :=& \{(x,z)\to r\, (h(x)-h_*(x))\, f_h^U(z): h\in \mcH \text{ s.t. } h-h_*\in \mcH_B, r\in [0,1]\}
\end{align}
where $f_{h}^U=\argmin_{f\in \mcF_U} \|f-T(h-h_*)\|_2$. If $T(h-h_*)\in \mcF_U$, then this simplifies to the class of functions of the form: $(h-h_*)(x)\, T(h-h_*)(z)$.

\begin{theorem}\label{thm:reg-main-error}
Let $\mcF$ be a symmetric and star-convex set of test functions and
consider the estimator:
\begin{equation}\label{eqn:reg-estimator}
    \hat{h} =
    \argmin_{h\in \mcH} \,\,\,\,\sup_{f\in \mcF}\,\, \Psi_n(h, f) - \lambda \left(\|f\|_{\mcF}^2 + \frac{U}{\delta^2} \|f\|_{2,n}^2\right) + \mu \|h\|_{\mcH}^2
\end{equation}
Let $h_*\in \mcH$ be any fixed hypothesis (independent of the samples) and $h_0$ be any hypothesis (not necessarily in $\mcH$) that satisfies the Conditional Moment~\eqref{eqn:cond-moments} and suppose that:
\begin{equation}\label{cond:reg-unnormalized}
\forall h\in \mcH: \min_{f\in \mcF_{L^2\|h-h_*\|_{\mcH}^2}} \|f - T(h-h_*)\|_2 \leq \eta_n
\end{equation}
Assume that functions in $\mcH_B$ and $\mcF_{3U}$ have uniformly bounded ranges in $[-1, 1]$ and that:
$\delta:=\delta_n + c_0 \sqrt{\frac{\log(c_1/\zeta)}{n}}$,
for universal constants $c_0, c_1$, and $\delta_n$ an upper bound on the critical radii of $\mcF_{3U}$ and $\hat{\mcG}_{B, L^2B}$.
If $\lambda \geq \delta^2/U$ and $\mu\geq 2\lambda (4 L^2 + 27U/B)$, then $\hat{h}$ satisfies w.p. $1-3\,\zeta$:
\begin{equation}
    \textstyle{\|T(\hat{h}-h_*)\|_2, \|T(\hat{h} - h_0)\|_2 \leq O\left(\delta + \eta_n + \|h_*\|_{\mcH}^2 \frac{\lambda+\mu}{\delta} + \|T(h_*-h_0)\|_2 + \frac{\|T(h_*-h_0)\|_2^2}{\delta}\right)}
\end{equation}
If further $\lambda, \mu = O(\delta^2)$ and $\delta \geq \|T(h_*-h_0)\|_2$, then:
\begin{equation}
    \|T(\hat{h}-h_*)\|_2, \|T(\hat{h} - h_0)\|_2 \leq O\left(\delta\max\{1, \|h_*\|_{\mcH}^2\} + \eta_n + \|T(h_*-h_0)\|_2\right)
\end{equation}
\end{theorem}

Observe that if the classes $\mcH,\mcF$ already are norm constrained, then the theorem directly applies to the estimator that solely penalizes the $\ell_{2,n}$ norm of $f$, i.e.:\footnote{By setting $\lambda=\delta^2/U$, $\mu=2\lambda \left(4L^2 + 27U/B\right)$ using an $\ell_{\infty}$ norm in both function spaces and taking $U, B\to \infty$. Observe that we can also take $L=1$, since $\|Th\|_{\infty} \leq \|h\|_{\infty}$ for any $T$.}
\begin{equation}
    \label{eqn:minimax-no-norms}
    \hat{h} := \argmin_{h\in \mcH} \sup_{f\in \mcF} \Psi_n(h, f) - \|f\|_{2,n}^2
\end{equation}
However, as we show below, imposing norm regularization as opposed to hard norm constraints leads to adaptivity properties of the estimator.

\paragraph{Adaptivity of regularized estimator} Suppose that we know that for $B, U=1$, we have that functions in $\mcH_B, \mcF_U$ have ranges in $[-1, 1]$ as their inputs range in $\mcX$ and $\mcZ$ correspondingly. Then our Theorem requires that we set: $\lambda \geq \delta^2$ and $\mu\geq 2\lambda (4L^2 + 27)$, where $\delta^2$ depends on the critical radius of the function class $\mcF_1$ and $\mcG_1$. Observe that none of these values depend on the norm of the benchmark hypothesis $\|h_*\|_{\mcH}$, which can be arbitrary and not constrained by our theorem (see also Appendix~\ref{app:adaptivity}).

For some function classes $\mcH$ that admit sparse representations, we can get an improved performance if instead of testing for classes of functions $\mcF$ that contain $T(h-h_*)$, we test functions whose linear span contains $T(h-h_*)$, i.e. that $T(h-h_*)=\sum_i w_i f_i$, assuming the weights required in this linear span have small $\ell_1$ norm. The reason being that the generalization error of linear spans with bounded $\ell_1$ norm can be prohibitively large to get fast error rates, i.e. the Rademacher complexity of the span of $\mcF$ can be much larger than $\mcF$, thereby introducing large sampling variance to our sup-loss objective. To state the improved result, we define for any function space $\mcF$:
$\spanF_{\kappa}(\mcF) := \left\{\sum_{i=1}^p w_i f_i: f_i\in \mcF, \|w\|_1\leq \kappa, p\leq\infty\right\}$,
i.e. the set of functions that consist of linear combinations of a finite set of elements $\mcF$, with the $\ell_1$ norm of the weights bounded by $R$. To get fast rates in this second result, we will require that the $\ell_2$-normalized $T(h-h_*)$ belongs to the span. We present the theorem in the well-specified setting, but a similar result holds in the case where $h_0\notin \mcH_B$, with the extra modification of adding a second moment penalty on $f$.

\begin{theorem}\label{thm:reg-main-error-2}
Consider a set of test functions $\mcF:=\cup_{i=1}^d \mcF^i$, that is decomposable as a union of $d$ symmetric test function spaces $\mcF^i$ and let $\mcF_U^i = \{f\in \mcF^i: \|f\|_{\mcF}^2\leq U\}$. Consider the estimator:
\begin{equation}\label{eqn:reg-estimator-2}
    \hat{h} =
    \argmin_{h\in \mcH} \,\,\,\,\sup_{f\in \mcF_{U}}\,\, \Psi_n(h, f) + \lambda \|h\|_{\mcH}
\end{equation}
Let $h_0\in \mcH_B$ be any fixed (independent of the samples) hypothesis that satisfies the Conditional Moment~\eqref{eqn:cond-moments}. Let $\delta_{n,\zeta}:=2\max_{i=1}^d \mcR(\mcF_U^i) + c_0 \sqrt{\frac{\log(c_1\, d/\zeta)}{n}}$,
for some universal constants $c_0, c_1$ and $B_{n, \lambda, \zeta}:= \|h_0\|_{\mcH} + \delta_{n,\zeta}/\lambda$. Suppose that:
\begin{equation}\label{cond:normalized-span}
\textstyle{\forall h\in \mcH_{B_{n,\lambda, \zeta}}: \frac{T(h-h_0)}{\|T(h-h_0)\|_2} \in \spanF_{\kappa}(\mcF_{U})}
\end{equation}
Then if $\lambda \geq \delta_{n,\zeta}$, $\hat{h}$ satisfies for some universal constants $c_0, c_1$, that w.p. $1-\zeta$:
\begin{equation}
    \|T(h_0-\hat{h})\|_2 \leq \kappa \left( 2\left(B+1\right) \mcR(\mcH_1) + \delta_{n,\zeta} + \lambda \left(\|h_0\|_{\mcH}-\|\hat{h}\|_{\mcH}\right)\right)
\end{equation}
\end{theorem}

In \Cref{app:further-main} we provide further discussion related to our main theorems: i) we provide further discussion on the adaptivity of our estimators, ii) we provide connections between the critical radius and the entropy integral and how to bound the critical radius via covering arguments, iii) we provide generic approaches to solving the optimization problem, iv) we show how to combine our main theorem on the projected MSE with bounds on the ill-posedness of the inverse problem in order to achieve MSE rates, v) we offer a discussion on the optimality of our estimation rate.

\section{Application: Reproducing Kernel Hilbert Spaces}\label{sec:rkhs}

In this section we describe how \Cref{thm:reg-main-error} applies to the case where $h_0$ lies in a Reproducing Kernel Hilbert space (RKHS) with kernel $K_\mcH:\mcX\times \mcX \to \R$, denoted with $\bbH_K$ and $T h_0$ lies in another RKHS with kernel $K_{\mcF}: \mcZ \times \mcZ \to \R$ (see \Cref{app:rkhs} for more details). We outline here the main ideas behind the three components required to apply our general theory and defer the full discussion to \Cref{app:rkhs}.

First we characterize the set of test functions that are sufficient to satisfy the requirement that $T(h-h_0)\in \mcF_U$. We show (see \Cref{lem:rkhs2}) that if the conditional density function $p(x\mid z)$ satisfies that the function $p(x\mid \cdot)$ falls in an RKHS $\bbH_{\KF}$, then $Th\in \bbH_{\KF}$. Moreover, we show that under the stronger conditions (see \Cref{lem:rkhs}) that $p(x\mid z)=\rho(x-z)$ and $\KH(x,y) = k(x-y)$, for $k$ positive definite and continuous, then $Th\in \bbH_K$, i.e. $Th$ falls in the same RKHS as $h$. These two theorems give conrete guidance in terms of primitive assumptions, on what RKHS should be used as a test function space, so that the condition that $T(h-h_0)\in \mcF$ is satisfied.

Second, by recent results in statistical learning theory, the critical radius of any RKHS-norm constrained subset of an RKHS class with kernel $K$ and norm bound $B$, can be characterized as a function of the \emph{eigen-decay of the empirical kernel matrix ${\bf K}$ defined as ${\bf K}_{ij}=K(x_i, x_j)/n$}. More concretely, it is the solution to:
$B\sqrt{\frac{2}{n}}\sqrt{\sum_{j=1}^{n} \min\{\lambda_j^S, \delta^2\}} \leq \delta^2$, where $\lambda_j^S$ are the empirical eigenvalues. In the worst-case is of the order of $n^{-1/4}$. In the context of \Cref{thm:reg-main-error},
the function classes $\mcF$ and $\mcG_B$ are kernel classes, with kernels $\KF$ and $K_{\times}((x, z), (x',z'))=\KH(x,x')\cdot \KF(z,z')$. Thus we can bound the critical radius required in the theorem as a function of the eigendecay of the corresponding empirical kernel matrices, which are data-dependent quantities.

Combining these two facts, we can then apply \Cref{thm:reg-main-error}, to get a bound on the estimation error of the minimax or regularized minimax estimator. Moreover, we show that for this set of test functions and hypothesis spaces, \emph{the empirical min-max optimization problem can be solved in closed form}. In particular, the estimator in Equation~\eqref{eqn:reg-estimator} takes the form:
\begin{align}\label{eqn:optimal-min-vector-rkhs-reg}
\hat{h} =~& \textstyle{\sum_{i=1}^n \alpha_{\lambda_*, i} \KH(x_i, \cdot)}
&
\alpha_{\lambda}
:=~& (\KHn M\KHn  + 4\,\lambda\, \mu \KHn)^{\dagger}\KHn M y
\end{align}
where $K_{\mcH,n} = (K_{\mcH}(x_i,x_j))_{i,j=1}^n$ and $K_{\mcF,n} = (K_{\mcF}(z_i,z_j))_{i,j=1}^n$, are empirical kernel matrices, and $M = K_{\mcF,n}^{1/2}(\textfrac{U}{n\delta^2}K_{\mcF,n} + I)^{-1} K_{\mcF,n}^{1/2}$ (where $A^\dagger$ is the Moore-Penrose pseudoinverse of $A$). Moreover, in \Cref{app:rkhs-optimization}, we discuss how ideas from low rank kernel matrix approximation (such as the Nystrom method) can avoid the $O(n^3)$ running time for matrix inverse computation in the latter closed form.
Finally, we show (see \Cref{app:rkhs-illposedness}) that if we make further assumptions on the rate at which the operator $T$ distorts the orthonormality of the eigenfunctions of the kernel $\KH$, then we can show that our estimator also implies mean-squared-error rates.

\section{Application: High-Dimensional Sparse Linear Function Spaces}\label{sec:high-dim-linear}

In this section we deal with high-dimensional linear function classes, i.e. the case when $\mcX, \mcZ\subseteq \R^p$ for $p\gg n$ and $h_0(x) = \ldot{\theta_0}{x}$ (see \Cref{app:high-dim-linear} for more details). We will address the case when the function $\theta_0$ is assumed to be sparse, i.e. $\|\theta_0\|_{0}:=\{j\in [p]: |\theta_j|>0\}\leq s$. We will be denoting with $S$ the subset of coordinates of $\theta_0$ that are non-zero and with $S^c$ its complement. For simplicity of exposition we will also assume that $\E[x_i\mid z]=\ldot{\beta}{z}$, though most of the results of this section also extend to the case where $\E[x_i\mid z]\in \mcF_i$ for some $\mcF_i$ with small Rademacher complexity. Variants of this setting have been analyzed in the prior works of \citep{gautier2011high,fan2014endogeneity}. We focus on the case where the covariance matrix $V:=\E[\E[x\mid z]\E[x\mid z]^\top ]$, has a restricted minimum eigenvalue of $\gamma$ and apply \Cref{thm:reg-main-error-2}.
We note that without the minimum eigenvalue condition, our \Cref{thm:reg-main-error} provides slow rates of the order of $n^{-1/4}$, for computationally efficient estimators that replace the hard sparsity constraint with an $\ell_1$-norm constraint.

\begin{corollary}\label{cor:sparse-linear-reg-ell1}
Suppose that $h_0(x)=\ldot{\theta_0}{x}$ with $\|\theta_0\|_0\leq s$ and $\|\theta_0\|_1\leq B$ and $\|\theta_0\|_{\infty}\leq 1$. Moreover, suppose that $\E[x_i\mid z] = \ldot{\beta_0^i}{z}$, with $\beta_0^i\in \R^p$ and $\|\beta_0^i\|_1\leq U$ and that the co-variance matrix $V$ satisfies the following restricted eigenvalue condition:
\begin{equation}
    \forall \nu\in \R^p \text{ s.t. } \|\nu_{S^c}\|_1 \leq \|\nu_S\|_1 + 2\,\delta_{n,\zeta}: \nu^\top  V\nu \geq \gamma \|\nu\|_2^2
\end{equation}
Then let $\mcH = \{x\to \ldot{\theta}{x}: \theta \in \R^p\}$, $\|\ldot{\theta}{\cdot}\|_{\mcH}=\|\theta\|_1$, $\mcF_U=\{z \to \ldot{\beta}{z}: \beta\in \R^p, \|\beta\|_1\leq U\}$ and $\|\ldot{\beta}{\cdot}\|_{\mcF}=\|\beta\|_1$. Then the estimator presented in Equation~\eqref{eqn:reg-estimator-2} with $\lambda\leq \frac{\gamma}{8s}$, satisfies that w.p. $1-\zeta$:
\begin{equation}
    \textstyle{\|T(\hat{h}-h_0)\|_2 \leq O\left( \max\left\{1, \frac{1}{\lambda}\frac{\gamma}{s}\right\} \sqrt{\frac{s}{\gamma}} \left((B + 1)\sqrt{\frac{\log(p)}{n}} + U\sqrt{\frac{\log(p)}{n}} + \sqrt{\frac{\log(p/\zeta)}{n}}\right)\right)}
\end{equation}
If instead we assume that $\|\beta_0^i\|_2\leq U$ and $\sup_{z\in \mcZ} \|z\|_2\leq R$ then by setting $\mcF_U=\{z\to \ldot{\beta}{z}: \|\beta\|_2\leq U\}$ and $\|\ldot{\beta}{\cdot}\|_\mcF= \|\beta\|_2$, then the later rate holds with $U\sqrt{\frac{\log(p)}{n}}$ replaced by $\frac{U\, R}{\sqrt{n}}$.
\end{corollary}

Notably, observe that in the case of $\|\beta_0^i\|_2\leq U$, we note that if one wants to learn the true $\beta$ with respect to the $\ell_2$ norm or the functions $\E[x_i\mid z]$ with respect to the RMSE, then the best rate one can achieve (by standard results for statistical learning with the square loss), even when one assumes that $\sup_{z\in \mcZ} \|z\|_2\leq R$ and that $\E[zz^{\top}]$ has minimum eigenvalue of at least $\gamma$, is: $\min\left\{\sqrt{\frac{p}{n}}, \left(\frac{U\, R}{n}\right)^{1/4}\right\}$. For large $p\gg n$ the first rate is vacuous. Thus we see that even though we cannot accurately learn the conditional expectation functions at a $1/\sqrt{n}$ rate, we can still estimate $h_0$ at a $1/\sqrt{n}$ rate, assuming that $h_0$ is sparse. Therefore, the minimax approach offers some form of robustness to nuisance parameters, reminiscent of Neyman orthogonal methods (see e.g. \cite{Chernozhukov2018double}).

In \Cref{app:high-dim-linear-opt} we also provide first-order iterative and computationally efficient algorithms with provable guarantees for solving the optimization problem. Moreover, we show that recent advances in online learning theory can be utilized to get fast iteration complexity, i.e. achieve error $\epsilon$ after $O(1/\epsilon)$ iterations (instead of the typical rate of $O(1/\epsilon^2)$ for non-smooth functions). Finally, in \Cref{app:high-dim-linear-ill}, we also show if we assume that the minimum eigenvalue of $V$ is at least $\gamma$ and the maximum eigenvalue of $\Sigma=\E[xx^\dagger]$ is at most $\sigma$, then the same rate as the one presented in \Cref{cor:sparse-linear-reg-ell1} holds for the MSE, multiplied by the constant $\sqrt{\sigma/\gamma}$.

\section{Neural Networks}\label{sec:neural-networks}

In this section we describe how one can apply the theoretical findings from the previous sections to understand how to train neural networks that solve the conditional moment problem. We will consider the case when our true function $h_0$ can be represented (or well-approximated) by a deep neural network function of $x$, for some given domain specific network architecture, and we will represent it as $h_0(x)=h_{\theta_0}(x)$, where $\theta_0$ are the weights of the neural net (see \Cref{app:neural-networks} for more details). Moreover, we will assume that the linear operator $T$, satisfies that for any set of weights $\theta$, we have that $T h_{\theta}$ belongs to a set of functions that can be represented (or well-approximated) as another deep neural network architecture, and we will denote these functions as $f_w(z)$, where $w$ are the weights of the neural net.

\paragraph{Adversarial GMM Networks (AGMM)} Thus we can apply our general approach presented in \Cref{thm:reg-main-error} (simplified for the case when $U=B=1$, $\lambda = \delta^2$, $\mu = 2\delta^2 (4L^2 + 27)$, where $L$ is a bound on the lipschitzness of the operator $T$ with respect to the two function space norms and $\delta$ is a bound on the critical radius of the function spaces $\mcF_{3}$ and $\hat{\mcG}_{1,L^2}$):

\begin{equation}
    \hat{\theta} = \argmin_{\theta} \sup_{w}  \E_n[\psi(y_i;h_{\theta}(x_i)) f_{w}(z)] - \delta^2 \|f_w\|_{\mcF}^2 - \frac{1}{n}\sum_i f_w(z_i)^2 + c\, \delta^2 \|h_{\theta}\|_{\mcH}^2
\end{equation}
for some constant $c>1$ that depends on the lipschitzness of the operator $T$. The AGMM criterion for training neural networks is closely related to the work of \cite{bennett2019deep}. However, the regularization presented in \cite{bennett2019deep} is not a simple second moment penalization. Here we show that such re-weighting is not required if one simply wants fast projected MSE rates (in \Cref{app:neural-networks} we provide further discussion).
Moreover, in \Cref{app:neural-networks-mmd}, we show how to derive intuition from our RKHS analysis to develop an architecture for the test function network that under conditions is guaranteed to contain the set of functions of the form $Th$. This leads to an MMD-GAN style adversarial GMM approach, where we consider test functions of the form: $f(z) = \frac{1}{s}\sum_{i=1}^s \beta_i K(c_i, g_w(z))$, where $c_i$ are parameters that could also be trained via gradient descent. The latter essentially corresponds to adding what is known as an RBF layer at the end of the adversary neural net (denoted as KLayerTrained in experiments). Finally, in \Cref{app:neural-networks-opt}, we provide heuristic methods for solving the non-convex/non-concave zero-sum game, using first order dynamics.

\section{Random Forests via a Reduction Approach}\label{sec:ensemble}

We will show that we can reduce the problem presented in \Cref{eqn:minimax-no-norms} to a regression oracle over the function space $\mcF$ and a classification oracle over the function space $\mcH$ (see \Cref{app:ensemble} for more details). We will assume that we have a regression oracle that solves the square loss problem over $\mcF$: for any set of labels and features $z_{1:n}, u_{1:n}$ it returns
\begin{equation}
    \textstyle{\text{Oracle}_{\mcF}(z_{1:n}, u_{1:n}) = \argmin_{f\in \mcF} \frac{1}{n}\sum_{i=1}^n \left(u_i -  f(z_i)\right)^2}
\end{equation}
Moreover, we assume that we have a classification oracle that solves the weighted binary classification problem over $\mcH$ w.r.t. the accuracy criterion: for any set of sample weights $w_{1:n}$, binary labels $v_{1:n}$ in $\{0, 1\}$ and features $x_{1:n}$:
\begin{equation}
    \textstyle{\text{Oracle}_{\mcH}(x_{1:n}, v_{1:n}, w_{1:n}) = \argmax_{h\in {\cal \mcH}} \frac{1}{n}\sum_{i=1}^n w_i\, \Pr_{z_i\sim \text{Bernoulli}\left(\frac{1+h(x_i)}{2}\right)}\left[v_i = z_i\right]}
\end{equation}

\begin{theorem}\label{thm:reduction-algorithm}
Consider the algorithm where for $t=1, \ldots, T$: let
\begin{align}
    u_i^t =~& \textstyle{\frac{1}{2} \left( y_i - \frac{1}{t-1} \sum_{\tau=1}^{t-1} h_{\tau}(x_i)\right),} &
    f_t =~& \textstyle{\text{Oracle}_{\mcF}\left(z_{1:n}, u_{1:n}^t\right)}\\
    v_i^t =~& 1\{f_t(z_i) > 0\},
    w_i^t = |f_t(z_i)| &
    h_t =~& \text{Oracle}_{\mcH}\left(x_{1:n}, v_{1:n}^t, w_{1:n}^t\right)
\end{align}
Suppose that the set $A=\{(f(z_1),\ldots, f(z_n)): f\in \mcF\}$ is a convex set. Then the ensemble: $\bar{h}=\frac{1}{T} \sum_{t=1}^T h_t$, is a $\frac{8\, (\log(T)+1)}{T}$-approximate solution to the minimax problem in Equation~\eqref{eqn:minimax-no-norms}.
\end{theorem}

In practice, we will consider a random forest regression method as the oracle over $\mcF$ and a binary decision tree classification method as the oracle for $\mcH$ (which we will refer to as RFIV). Prior work on random forests for causal inference has focused primarily on learning forests that capture the heterogeneity of the treatment effect of a treatment, but did not account for non-linear relationships between the treatment and the outcome variable. The method proposed in this section makes this possible. Observe that the convexity of the set $A$ is violated by the random forest function class with a bounded set of trees. Albeit in practice this non-convexity can be alleviated by growing a large set of trees on bootstrap sub-samples or using gradient boosted forests as oracles for $\mcF$. Moreover, observe that we solely addressed the optimization problem and postpone the statistical part of random forests (e.g. critical radius) to future work (see also Appendix~\ref{app:ensemble}).

\section{Further Applications}

In the appendix we also provide further applications of our main theorems. In \Cref{sec:sieves} we show how our theorems apply to the case where $\mcH$ and $\mcF$ are growing linear sieves, which is a typical approach to non-parametric estimation in the econometric literature (see e.g. \cite{chen2012estimation}). In \Cref{sec:shape} we analyze the case where $\mcH$ and $\mcF$ are function classes defined via shape constraints. We analyze the case of total variation bound constraints and convexity constraints. This applications provides analogues of the convex regression and the isotonic regression to the endogenous regression setting and draws connections to recent works in econometrics on estimation subject to monotonicity constraints \cite{Chetverikov2017}.

\section{Experimental Analysis}

\paragraph{Experimental Design.}
We consider the following data generating processes: for $n_x=1$ and $n_z\geq 1$

\begin{align}
    y =~& h_0(x[0]) + e + \delta, & \delta \sim N(0, .1)\\
    x =~& \gamma\, z[0] + (1-\gamma)\, e + \gamma, &
    z \sim N(0, 2\, I_{n_z}), e\sim N(0, 2), \gamma\sim N(0, .1)
\end{align}
While, when $n_x=n_z>1$, then we consider the following modified treatment equation:
\begin{align}
x =~& \gamma\, z + (1-\gamma)\, e + \gamma, &
\end{align}
We consider several functional forms for $h_0$ including absolute value, sigmoid and sin functions (more details in \Cref{app:funcform}) and several ranges of the number of samples $n$, number of treatments $n_x$, number of instruments $n_z$ and instrument strength $\gamma$. We consider as classic benchmarks 2SLS with a polynomial features of degree $3$ (2SLS) and a regularized version of 2SLS where ElasticNetCV is used in both stages (Reg2SLS).

In addition to these regimes, we consider high-dimensional experiments with images, following the scenarios proposed in \cite{bennett2019deep} where either the instrument $z$ or treatment $x$ or both are images from the MNIST dataset consisting of grayscale images of $28\times28$ pixels. We compare the performance of our approaches to that of \cite{bennett2019deep}, using their code.
A full description of the DGP is given in the supplementary material.

\paragraph{Results.} The main findings are: i) for small number of treatments, the RKHS method with a Nystrom approximation (NystromRKHS), outperforms all methods (Figure~\ref{fig:table1}), ii) for moderate number of instruments and treatments, Random Forest IV (RFIV) significantly outperforms most methods, with second best being neural networks (AGMM, KLayerTrained) (Figure~\ref{fig:table2}), iii) the estimator for sparse linear hypotheses can handle an ultra-high dimensional regime (Figure~\ref{fig:table3}), iv) neural network methods (AGMM, KLayerTrained) outperform the state of the art in prior work \citep{bennett2019deep} for tasks that involve images (Figure~\ref{fig:mnist_dgps}). The figures below present the average MSE across $100$ experiments ($10$ experiments for Figure~\ref{fig:mnist_dgps}) and two times the standard error of the average MSE.
\begin{figure}[H]
    \centering
    \scriptsize
    \begin{tabular}{c||c|c|c|c|c|c|c}
    & NystromRKHS & 2SLS & Reg2SLS & RFIV\\
    \hline
    abs & {\bf 0.045 $\pm$ 0.010 } & 0.100 $\pm$ 0.035 & 1.733 $\pm$ 2.981 & 0.084 $\pm$ 0.007 \\
2dpoly & 0.121 $\pm$ 0.014 & {\bf 0.036 $\pm$ 0.022 } & 9.068 $\pm$ 16.071 & 0.379 $\pm$ 0.022 \\
sigmoid & {\bf 0.016 $\pm$ 0.003 } & 0.071 $\pm$ 0.037 & 0.429 $\pm$ 0.244 & 0.044 $\pm$ 0.006 \\
sin & {\bf 0.023 $\pm$ 0.003 } & 0.090 $\pm$ 0.042 & 0.801 $\pm$ 0.420 & 0.057 $\pm$ 0.007 \\
frequentsin & 0.129 $\pm$ 0.005 & 0.193 $\pm$ 0.040 & 0.145 $\pm$ 0.017 & {\bf 0.126 $\pm$ 0.010} \\
step & {\bf 0.035 $\pm$ 0.003 } & 0.103 $\pm$ 0.043 & 0.497 $\pm$ 0.276 & 0.056 $\pm$ 0.007 \\
3dpoly & 0.220 $\pm$ 0.037 & {\bf 0.004 $\pm$ 0.003 } & 0.066 $\pm$ 0.014 & 0.687 $\pm$ 0.069 \\
linear & 0.019 $\pm$ 0.003 & 0.038 $\pm$ 0.021 & 0.355 $\pm$ 0.189 & 0.048 $\pm$ 0.005 \\
band & {\bf 0.059 $\pm$ 0.003 } & 0.125 $\pm$ 0.051 & 0.085 $\pm$ 0.017 & 0.071 $\pm$ 0.008
\end{tabular}
    \caption{$n=300$, $n_z=1$, $n_x=1$, $\gamma=.6$}
    \label{fig:table1}
\end{figure}

\begin{figure}[H]
    \centering
    \scriptsize
    \begin{tabular}{c||c|c|c|c|c|c}
    & NystromRKHS & 2SLS & Reg2SLS & RFIV & AGMM & KLayerTrained\\
    \hline
    abs & 0.143 $\pm$ 0.005 & 10050.672 $\pm$ 13267.141 & 0.122 $\pm$ 0.011 & {\bf 0.049 $\pm$ 0.001 } &  0.062 $\pm$ 0.003  & 0.127 $\pm$ 0.007\\
2dpoly & 0.595 $\pm$ 0.025 & 5890.128 $\pm$ 8261.553 & 4.510 $\pm$ 1.245 & 0.346 $\pm$ 0.014 & {\bf 0.099 $\pm$ 0.006 }&0.240 $\pm$ 0.014\\
sigmoid & 0.045 $\pm$ 0.003 & 11712.144 $\pm$ 16799.716 & 0.091 $\pm$ 0.005 & {\bf 0.017 $\pm$ 0.001 } & 0.040 $\pm$ 0.001 & 0.024 $\pm$ 0.001\\
sin & 0.058 $\pm$ 0.003 & 13769.428 $\pm$ 20805.861 & 0.114 $\pm$ 0.006 & {\bf 0.029 $\pm$ 0.001 } &0.074 $\pm$ 0.002 & 0.057 $\pm$ 0.002\\
frequentsin & 0.136 $\pm$ 0.004 & 12928.749 $\pm$ 19554.361 & 0.144 $\pm$ 0.004 & {\bf 0.120 $\pm$ 0.002 } & 0.158 $\pm$ 0.002&0.128 $\pm$ 0.002\\
step & 0.064 $\pm$ 0.003 & 12187.342 $\pm$ 17814.756 & 0.109 $\pm$ 0.004 & {\bf 0.027 $\pm$ 0.001 } &0.066 $\pm$ 0.002& 0.050 $\pm$ 0.001\\
3dpoly & 0.648 $\pm$ 0.039 & 432.572 $\pm$ 596.731 & {\bf 0.061 $\pm$ 0.005 } & 0.444 $\pm$ 0.029 &  0.426 $\pm$ 0.027 & 0.491 $\pm$ 0.029\\
linear & 0.080 $\pm$ 0.002 & 6964.376 $\pm$ 9566.774 & 0.107 $\pm$ 0.006 & 0.016 $\pm$ 0.001 &0.020 $\pm$ 0.001& {\bf 0.013 $\pm$ 0.001 }\\
band & 0.078 $\pm$ 0.004 & 20401.368 $\pm$ 29655.000 & 0.090 $\pm$ 0.004 & {\bf 0.049 $\pm$ 0.002 } & 0.088 $\pm$ 0.003 & 0.074 $\pm$ 0.003
    \end{tabular}
    \caption{$n=2000$, $n_z=10$, $n_x=10$, $\gamma=.6$}
    \label{fig:table2}
\end{figure}

\begin{figure}[H]
    \centering
    \scriptsize
    \begin{tabular}{c||c|c|c|c}
     $p=$ & 1000 & 10000 & 100000 & 1000000\\
    \hline
    SpLin & 0.020 $\pm$ 0.003 & 0.021 $\pm$ 0.003 & - & -\\
    StSpLin & 0.020 $\pm$ 0.002  & 0.023 $\pm$ 0.002 & 0.033 $\pm$ 0.002 & 0.050 $\pm$ 0.004
    \end{tabular}
    \caption{$n=400$, $n_z=n_x:=p$, $\gamma=.6$, $h_0(x[0])=x[0]$}
    \label{fig:table3}
\end{figure}

\begin{figure}[H]
    \centering
    \scriptsize
    \begin{tabular}{c||c|c|c|c}
      & DeepGMM (\cite{bennett2019deep}) & AGMM  & KLayerTrained \\
    \hline
    $\text{MNIST}_z$ & 0.12 $\pm$ 0.07 & 0.04 $\pm$ 0.03 & 0.05 $\pm$ 0.02 \\
    $\text{MNIST}_x$ & 0.34 $\pm$ 0.21  & 0.24 $\pm$ 0.08 & 0.36 $\pm$ 0.20  \\
    $\text{MNIST}_{xz}$ & 0.26 $\pm$ 0.16 & 0.21 $\pm$ 0.07 & 0.26 $\pm$ 0.11
    \end{tabular}
    \caption{MSE on the high-dimensional DGPs}
    \label{fig:mnist_dgps}
\end{figure}

\bibliographystyle{plainnat}
\bibliography{refs}

\newpage
\appendix

\input{neurips_submission_appendix}

\end{document}


TITLE: Verifying - Trigonometry Homework
QUESTION [3 upvotes]: I have a major problem with verifying a Trigonometric identity. (My teacher couldn't really get it, so I would like to find it just in case it appears on a test)
The problem goes like this:
$$\sin(\theta) + \cos(\theta) = \frac{\sin(\theta)}{1 - \cot(\theta)} + \frac{\cos(\theta)}{1 - \tan(\theta)}$$
Where I must verify that this is true. I have tried numerous operations, mostly getting to $\sin + \cos$ along with a crazy fraction in the numerator and another fraction in the numerator. As I have said, my teacher showed my something, but it really did not work after I continued simplifying.
If there is anyone who would help guide me in this, it would be much appreciated.

REPLY [9 votes]: $$\eqalign{
{\sin\theta\over 1-\cot\theta} +{\cos\theta\over 1-\tan\theta}
&={\sin\theta\over 1-{\cos\theta\over \sin\theta}} +{\cos\theta\over 1-{\sin\theta\over \cos\theta}}\cr
&={\sin^2\theta\over \sin\theta-{\cos\theta }} +{\cos^2\theta\over\cos\theta-{\sin\theta }}
\phantom{{a\over b}\over{c\over d}}\cr
&={\sin^2\theta-\cos^2\theta\over \sin\theta-{\cos\theta }}\phantom{{a\over b}\over{c\over d}}  \cr
&={(\sin\theta +\cos)(\sin\theta -\cos\theta)\over \sin\theta-{\cos\theta }}\phantom{{a\over b}\over{c\over d}}\cr
&=\sin\theta+\cos\theta .
}
$$

REPLY [4 votes]: It bears a vague resemblance to the Pythagorean identity (a sine added to a cosine), and the definitions of $\cot$ and $\tan$ will allow us to realize a route forward by doubling up on them up top:
$$\frac{\sin}{1-\cot} + \frac{\cos}{1-\tan} = \frac{\sin^2}{\sin-\cos}+\frac{\cos^2}{\cos-\sin}=\frac{\sin^2-\cos^2}{\sin-\cos}.$$