text:
\begin{document}

\title{A quantitative analysis of the ``Lion-Man'' game}

\author{Ulrich Kohlenbach$^{a}$, Genaro L\'{o}pez-Acedo$^{b}$, Adriana Nicolae$^{b,c}$}
\date{}
\maketitle

\begin{center}
{\scriptsize
$^{a}$Department of Mathematics, Technische Universit\" at Darmstadt, Schlossgartenstra\ss{}e 7, 64289 Darmstadt, Germany
\ \\
$^{b}$Department of Mathematical Analysis - IMUS, University of Seville, C/ Tarfia s/n, 41012 Seville, Spain
\ \\
$^{c}$Department of Mathematics, Babe\c s-Bolyai University, Kog\u alniceanu 1, 400084 Cluj-Napoca, Romania \\
\ \\
E-mail addresses: kohlenbach@mathematik.tu-darmstadt.de (U. Kohlenbach), glopez@us.es (G. L\'{o}pez-Acedo), anicolae@math.ubbcluj.ro (A. Nicolae)
}
\end{center}

\begin{abstract}
In this paper we focus on a discrete lion and man game with an $\eps$-capture criterion. We prove that in uniformly convex bounded domains the lion always wins and, using ideas stemming from proof mining, we extract a uniform rate of convergence for the successive distances between the lion and the man. As a byproduct of our analysis, we study the relation among different convexity properties in the setting of geodesic spaces. \\

\noindent {\em MSC: 91A24, 49N75 (primary), 53C23, 03F10 (secondary)}
\\

\noindent {\em Keywords}: Lion and man game, \and rate of convergence, \and uniform convexity, \and betweenness property.
\end{abstract}

\section{Introduction}
The lion and man problem, which goes back to R. Rado, is one of the most challenging pursuit-evasion games and can be described as follows: a lion and a man move in a circular arena with equal maximum speeds. If the arena is viewed as a closed disc, the positions of the lion and of the man are regarded as two points (considering the initial position of the lion at the center of the disc) and the lion moves so that the center of the disc, its position and the one of the man are collinear in this order, can the lion catch the man? A detailed discussion of the solution to this problem can be found in \cite{Cr64,Li86,Na07}. Very similar problems have appeared under different names in the literature (e.g. the robot and the rabbit \cite{H69} or the cop and the robber \cite{AF84}).

The analysis of the lion and man game is closely tied to the geometric structure of the domain where the game is played. This fact, as well as the potential applications in different fields such as robotics \cite{BH10},  biology \cite{BBH08}  and random processes \cite{BBK13,BBK14}, have given rise to several variants of this game, both continuous \cite{BLW12} and discrete (the discrete version is attributed to D. Gales, see \cite{S01} for more details). Such games involve one or more evaders  in a fixed domain being hunted by one or more pursuers who win the game if certain appropriate capture criteria are satisfied. Such criteria may be physical capture (the pursuers move to the location of the evaders) or $\eps$-capture \cite{AGR92} (the pursuers get within a distance less than $\eps$ to the evaders).

Here we focus on a discrete-time equal-speed game with an $\eps$-capture criterion that was  considered in \cite{AleBisGhr06,AleBisGhr10}. The domain $A$ of our game is a convex subset of a uniquely geodesic space. Initially, the lion and the man are located at two points in $A$, $L_0$ and $M_0$, respectively. One fixes a positive upper bound $D>0$ on the distance the lion and the man may jump. After $n$ steps, the man  moves from the point $M_{n}$ to any point $M_{n+1} \in A$ which is within distance $D$. The lion moves from the point $L_n$ to the point $L_{n+1}$ along the geodesic from $L_{n}$ to $M_{n}$ such that its distance to $L_{n}$ equals $\min\{D,d(L_n,M_n)\}$. We say that the lion wins if $\lim_{n\to\infty} d(L_{n+1},M_n) = 0$. When we refer in the sequel to the Lion-Man game, we will always mean the game we have just described. In \cite{AleBisGhr10}, it was stated that in CAT$(0)$ spaces the lion always wins if and only if the domain is compact. Nonetheless, this characterization of compactness proved to be false as \cite{Bac12} contains an example of an unbounded CAT$(0)$ space where the lion always wins. Further advances in this problem were made in \cite{LNP1} where a characterization of compactness of the domain in terms of the success of the lion was obtained in complete, locally compact, uniquely geodesic spaces that satisfy a betweenness property. In addition, the success of the lion in the Lion-Man game was also linked in this setting to the fixed point property for continuous mappings. However, none of these results provides any information on the speed of convergence towards $0$ of the sequence $d(L_{n+1},M_n)$.

Our aim in this paper is twofold: on the one hand to weaken the topological and geometric hypotheses that ensure the success of the lion, and on the other hand to give a rate of convergence for the sequence $d(L_{n+1},M_n)$ that only depends on some geometric properties of the domain. The ideas that led to our results have their roots in proof mining. By ``proof mining'' we mean the logical analysis, using proof-theoretic tools, of mathematical proofs with the aim of extracting relevant information hidden in the proofs. This new information can be both of quantitative nature, such as algorithms and effective bounds, as well as of qualitative nature, such as uniformities in the bounds or weakening of the premises. A comprehensive reference for proof mining is the book \cite{K08}. The first step towards obtaining the desired rate of convergence is to introduce quantitative uniform versions of the convexity properties used in \cite{LNP1} as main ingredients in the study of the Lion-Man game. More precisely, the properties in question refer to the uniqueness of geodesics and a betweenness relation.

The organization of the paper is as follows. In Section \ref{section-conv} we analyze the geometric background that we later rely on to prove our main result. Although the existence of unique geodesics between any two given points in a geodesic space is a widely known and well-understood condition, here we consider a quantitative uniform version thereof (see Definition \ref{def-UU}) and study its connection with other convexity properties. In Theorem \ref{thm-UC-UU} we prove that uniformly convex geodesic spaces admitting a monotone modulus of uniform convexity $\eta$ are uniformly uniquely geodesic and one can define a modulus of uniform uniqueness in terms $\eta$. Actually, in normed vector spaces, uniform convexity is equivalent to uniform uniqueness of geodesics, but in general these two concepts are different. This distinction in nonlinear settings is an interesting feature of uniform uniqueness which could motivate the further study of its relevance. Along with the uniqueness of geodesics, a betweenness property also plays an important role in the study of the Lion-Man game. This property (see Definition \ref{def-BTW}) holds e.g. in all strictly convex normed spaces, but also in a wide class of geodesic spaces as we will point out. Betweenness relations have already been considered in very early works such as \cite{HK17,DW}. We introduce a quantitative uniform variant of the betweenness property (see Definition \ref{def-UBTW}) which will be central to the quantitative analysis of the Lion-Man game. In Theorem \ref{thm-UU-UBTW} we show that the uniform betweenness property holds in uniformly uniquely geodesic spaces whose distance function satisfies a convexity condition, and that a modulus of uniform uniqueness generates a modulus of uniform betweenness. In Section \ref{section-rate} we prove our main result contained in Theorem \ref{thm-main} and Corollary \ref{co-main}, which states that under the assumption of boundedness, uniform uniqueness, and uniform betweenness for the domain where the Lion-Man game is played, the lion always wins. The result applies in particular for all uniformly convex normed spaces, $\CAT(\kappa)$ spaces (of sufficiently small diameter for $\kappa > 0$), or compact uniquely geodesic spaces satisfying the betweenness property. Consequently, we notably weaken and unify previously known geometric conditions that were imposed on the domain in order to guarantee the success of the lion. Moreover, Corollary \ref{co-main} provides a rate of convergence for the sequence $d(L_{n+1},M_n)$ towards $0$, and hence gives an explicit bound on the number of steps to be taken for an $\eps$-capture. This rate of convergence is expressed in terms of the moduli of uniform uniqueness and of uniform betweenness, and can be explicitly computed e.g. in $L_p$ spaces over measurable spaces with $1 < p < \infty$ or $\CAT(\kappa)$ spaces.  The last section contains a general discussion on the proof mining techniques used to develop our quantitative analysis.

\section{Convexity properties in geodesic spaces}\label{section-conv}

This section discusses several geometric properties of geodesic spaces with emphasis on convexity notions that play an essential role in our main result. We start with a brief account of some basic definitions on geodesic spaces and refer to \cite{Bri99} for a more detailed treatment.

Let $(X,d)$ be a metric space. For $x \in X$ and $r > 0$, we denote the {\it closed ball} centered at $x$ with radius $r$ by $\overline{B}(x,r)$. If $A$ is a nonempty and bounded subset of $X$, the {\it diameter} of $A$ is
\[\diam(A) = \sup\{d(a,a'): a,a' \in A\},\]
the {\it separation} of $A$ is
\[\sep(A) = \inf\{d(a,a'): a,a' \in A, a \ne a'\},\]
and the {\it distance} of a point $x \in X$ to $A$ is
\[\dist(x,A) = \inf\{d(x,a) : a \in A\}.\]

Let $x,y \in X$. A {\it geodesic} joining $x$ to $y$ is a mapping $\gamma:[0,l] \subseteq \R \to X$ such that $\gamma(0)=x$, $\gamma(l)=y$ and
\[d(\gamma(s),\gamma(s'))=|s-s'| \quad \text{for all }s,s'\in[0,l].\]
It follows that $l=d(x,y)$. We say that a geodesic $\gamma$ {\it starts} at $x$ if $\gamma(0) = x$. If every two points in $X$ are joined by a (unique) geodesic, then $X$ is called a {\it (uniquely) geodesic space}. The image $\gamma([0,l])$ of a geodesic $\gamma$ is called a {\it geodesic segment} with endpoints $x$ and $y$. A point $z\in X$ belongs to a geodesic segment with endpoints $x$ and $y$ if and only if there exists $t\in [0,1]$ such that
\[d(z,x)= td(x,y) \quad \text{and} \quad d(z,y)=(1-t)d(x,y).\]
In this case, if $\gamma$ is the geodesic in question, then $z=\gamma(tl)$. When $t=1/2$, we call such a point $z$ a {\it midpoint} of $x$ and $y$ and also denote it by $m(x,y)$. In a geodesic space, two given points $x$ and $y$ may be joined by more than one geodesics and thus may have more than one midpoint. If there is a unique geodesic segment with endpoints $x$ and $y$, we denote it by $[x,y]$ and in this case for all $t\in [0,1]$ there exists only one point $z \in X$, denoted by $(1-t)x + ty$, satisfying $d(z,x)= td(x,y)$ and $d(z,y)=(1-t)d(x,y)$. In particular, $x$ and $y$ have a unique midpoint $m(x,y) = (1/2)x+(1/2)y$.
\begin{de}\label{def-str-conv}
Let $(X,d)$ be a geodesic space. We say that $X$ is {\it strictly convex} if for all $z,x,y \in X$ with $x \ne y$ and all midpoints $m(x,y)$ of $x$ and $y$ we have
\[d(z, m(x,y)) < \max\{d(z,x),d(z,y)\}.\]
\end{de}
Strictly convex geodesic spaces are uniquely geodesic. Indeed, let $\gamma_1$ and $\gamma_2$ be two geodesics joining $x$ to $y$. Denote $u_s=\gamma_1(s)$ and $v_s=\gamma_2(s)$, where $s \in [0,d(x,y)]$. If $u_s \ne v_s$, then taking any midpoint $m(u_s,v_s)$ it follows that
\begin{align*}
d(x,y) & \le d(x,m(u_s,v_s)) + d(y,m(u_s,v_s)) \\
& < \max\{d(x,u_s),d(x,v_s)\} + \max\{d(y,u_s),d(y,v_s)\}\\
& = s + d(x,y) - s = d(x,y),
\end{align*}
a contradiction. Hence $u_s=v_s$ for any $s \in [0,d(x,y)]$, which shows that $\gamma_1=\gamma_2$. This also shows that in Definition \ref{def-str-conv} one can equivalently consider some midpoint of $x$ and $y$ instead of all midpoints as this is enough to prove the uniqueness of geodesics.

Any normed vector space is a geodesic space. For this class of spaces, strict convexity is actually equivalent to the existence of unique geodesics between any two points. However, in general this equivalence fails to hold as the following example shows.
\begin{ex} \label{ex-sphere}
The {\it $2$-dimensional sphere $\mathbb{S}^2$} is the set $\left\{u \in {\R}^{3} : (u \mid u) = 1\right\}$, where $(\cdot\mid \cdot)$ is the Euclidean scalar product. Endowed with the distance $d: \mathbb{S}^2 \times \mathbb{S}^2 \to \R$ that assigns to each $(x,y) \in \mathbb{S}^2 \times \mathbb{S}^2$ the unique number $d(x,y) \in [0,\pi]$ such that $\cos d(x,y) = (x\mid y)$, $\mathbb{S}^2$ is a geodesic space called the spherical space. Any octant of $\mathbb{S}^2$ is a uniquely geodesic space that is not strictly convex.
\end{ex}

Uniform convexity is a strengthening of strict convexity and was first introduced in the linear case in \cite{Cla36} and in a nonlinear setting in \cite{GoeSekSta80,GoeRei84}. Since then it was used in various forms in metric spaces and we consider here the following variant (see also \cite{Leu07}).

\begin{de} \label{def-UC}
A geodesic space $(X,d)$ is {\it uniformly convex} if for all $\eps \in (0,2]$ and $r>0$ there exists $\delta \in (0,1]$ such that for all $z, x, y\in X$ and all midpoints $m(x,y)$
we have
\begin{eqnarray}\nonumber
\left.\begin{array}{l}
d(z,x)\le r\\
d(z,y)\le r\\
d(x,y)\ge\varepsilon r
\end{array}
\right\}
& \Rightarrow & d(z,m(x,y))\le (1-\delta)r.
\end{eqnarray}
A mapping $\eta : (0,2] \times (0,\infty) \to (0,1]$ providing for given $r > 0$ and $\eps \in (0, 2]$ such a $\delta = \eta(\eps,r)$ is called {\it a modulus of uniform convexity}. A modulus of uniform convexity is said to be {\it monotone} if it is nonincreasing in the second argument.
\end{de}

Every uniformly convex geodesic space is strictly convex, hence uniquely geodesic. Again, uniform convexity is in fact equivalent to the condition obtained by considering the above implication for some midpoint of $x$ and $y$ instead of all midpoints. Besides, one can show that every compact strictly convex geodesic space is uniformly convex.

In normed vector spaces that are uniformly convex in the sense of Definition \ref{def-UC}, by rescaling balls, one can always find moduli of uniform convexity that do not depend on the second argument, namely on the radii $r$. In fact, one usually considers the notion of {\it the modulus of convexity} of a normed vector space $X$ defined as the function $\delta : [0,2] \to [0,1]$ given by
\[\delta(\eps) = \inf \left\{ 1 - \left\|\frac{x+y}{2}\right\| : \|x\| \le 1, \|y\| \le 1, \|x-y\| \ge \eps\right\},\]
or equivalently,
\[\delta(\eps) = \inf \left\{ 1 - \left\|\frac{x+y}{2}\right\| : \|x\| = 1, \|y\| = 1, \|x-y\| \ge \eps\right\}.\]
Note that $\delta$ is nondecreasing on $[0,2]$ and continuous on $[0,2)$. The normed vector space $X$ is uniformly convex (in the sense of Definition \ref{def-UC} and equivalently in the sense of \cite{Cla36}) if and only if $\delta(\eps) > 0$ for all $\eps > 0$. In this case $\delta$ is the largest possible modulus of uniform convexity one can define for $X$.

For $1 < p < \infty$, an $L_p$ space over a measurable space is uniformly convex and, if $\delta$ is its modulus of convexity and $\eta : (0,2] \to (0,1]$ is defined by
\begin{equation}\label{eq-mod-Lp}
\eta(\eps)=\left\{
\begin{array}{ll}
\displaystyle\frac{p-1}{8}\eps^2, & \mbox{if } 1 < p \le 2,\\
\displaystyle\frac{1}{p2^p}\eps^p, & \mbox{if } 2 < p < \infty,
\end{array}
\right.
\end{equation}
then $\delta(\eps) \ge \eta(\eps)$ for all $\eps \in (0,2]$. Hence, $\eta$ is a modulus of uniform convexity for $L_p$.

A related notion is {\it the characteristic of convexity} of a normed vector space defined as the number
\[\eps_0 = \sup\{\eps \in [0,2]: \delta(\eps) = 0\}.\]
Then $X$ is uniformly convex if and only if $\eps_0 = 0$. In addition, $\delta$ is strictly increasing on $[\eps_0,2]$. These concepts and proofs of the properties mentioned above can be found e.g. in \cite[Chapter 5]{GK90}.

A particular notion of uniform convexity, called $p$-uniformly convexity, was introduced by Ball, Carlen and Lieb \cite{BalCarLie94} in the linear case and, more recently, in the setting of geodesic spaces by Naor and Silberman \cite{NS11} in the following way: given $1<p<\infty$, a geodesic space $(X,d)$ is {\it $p$-uniformly convex} if there exists a parameter $c>0$ such that for all $x,y,z\in X$, all $t\in[0,1]$ and all geodesics $\gamma$ joining $x$ to $y$,
\begin{equation}\label{eq-p-UC}
d(z,\gamma(td(x,y)))^p\leq(1-t)\,d(z,x)^p+t\,d(z,y)^p-\frac{c}{2}\,t(1-t)\,d(x,y)^p.
\end{equation}
Thus, a geodesic space that is $p$-uniformly convex geodesic space with parameter $c>0$ is uniformly convex (in the sense of Definition \ref{def-UC}) and admits a modulus of uniform convexity that does not depend on the second argument
\begin{equation} \label{eq-mod-p-UC}
\eta(\eps) = \frac{c}{8p} \eps^p.
\end{equation}
Estimations on $c$ depending on the value of $p$ can be found in \cite{Kuw14}. Every $L_p$ space over a measurable space is $p$-uniformly convex if $p > 2$ and $2$-uniformly convex if $p \in (1,2]$. As for geodesic spaces, every $\CAT(0)$ space is $2$-uniformly convex with parameter $c=2$ and, in this case, (\ref{eq-p-UC}) provides a characterization of $\CAT(0)$ spaces. For $\kappa>0$, any $\CAT(\kappa)$ space $X$ with $\diam(X)<\pi/(2\sqrt{\kappa})$ is $2$-uniformly convex with parameter $c=(\pi-2\sqrt{\kappa}\,\eps)\,\tan(\sqrt{\kappa}\,\eps)$ for any $0<\eps\leq\pi/(2\sqrt{\kappa})-\diam(X)$, see \cite{Oht07}. We remark at this point that $\CAT(\kappa)$ spaces are defined in terms of comparisons with the model planes i.e. the complete simply connected $2$-dimensional Riemannian manifolds of constant sectional curvature $\kappa$. More precisely, in $\CAT(\kappa)$ spaces, geodesic triangles (which consist of three points and three geodesic segments joining them) are ``thin'' when compared to triangles with the same side lengths in the model planes. Note also that a normed real vector space which is $\CAT(\kappa)$ for some $\kappa \in \R$ is pre-Hilbert. A comprehensive exposition of $\CAT(\kappa)$ spaces can be found in \cite{Bri99}.

Unless otherwise stated, in what follows we always assume that $(X,d)$ is a uniquely geodesic space. As we pointed out in the introduction, for our main result we need a quantitative uniform version of the property that there exists exactly one geodesic joining two points in $X$, and we define it below.
\begin{de}\label{def-UU}
We say that $X$ is {\it uniformly uniquely geodesic} if for all $\eps, b > 0$ there exists $\varphi > 0$ such that for all $x, y, z\in X$ and all $r_1 , r_2 \in (0,b]$ we have
\begin{eqnarray}\nonumber
\left.\begin{array}{l}
d(z,x)\le r_1\\
d(z,y)\le r_2 + \varphi \\
d(x,y)\ge r_1 + r_2
\end{array}
\right\}
& \Rightarrow & \text{dist}(z,[x,y]) < \eps.
\end{eqnarray}
A mapping $\Phi : (0,\infty)\times(0,\infty)\to (0,\infty)$ providing for given $\eps, b > 0$ such a $\varphi = \Phi(\eps,b)$ is called {\it a modulus of uniform uniqueness}.
\end{de}
A somehow related property for CAT$(0)$ spaces can be found in \cite[Lemma 17.20]{K08} and \cite[Chapter II, Lemma 9.15]{Bri99}.

\begin{pro} \label{rmk-cpt}
Compact uniquely geodesic spaces are uniformly uniquely geodesic.
\end{pro}
\begin{proof}
Although this fact is almost straightforward, we include its proof because uniform uniqueness of geodesics plays an essential role in this work. We argue by contradiction. Suppose that $(X,d)$ is compact and uniquely geodesic, but not uniformly uniquely geodesic. Then there exist $\eps, b > 0$ such that for all $n \in \mathbb{N}$ we can find points $x_n, y_n, z_n \in X$ and numbers $r_1^n, r_2^n \in (0,b]$ satisfying
\[d(z_n,x_n) \le r_1^n, \quad d(z_n,y_n) \le r_2^n + \frac{1}{n}, \quad d(x_n,y_n) \ge r_1^n + r_2^n,\]
and
\begin{equation} \label{eq1-cmp-uu}
\text{dist}(z_n, [x_n,y_n]) \ge \eps.
\end{equation}
By compactness, we may assume that there exist $x,y,z \in X$ and $r_1,r_2 \in [0,b]$ such that $x_n \to x$, $y_n \to y$, $z_n \to z$, $r_1^n \to r_1$ and $r_2^n \to r_2$. Then
\[r_1 + r_2 \le d(x,y) \le d(z,x) + d(z,y) \le r_1 + r_2,\]
from where $z \in [x,y]$. Note that if $\gamma_n$ is the geodesic starting at $x_n$ whose image is $[x_n,y_n]$, then $(\gamma_n)$ converges uniformly to the geodesic starting at $x$ whose image is $[x,y]$ (see, e.g., \cite[Chapter I, Lemma 3.12]{Bri99}). This contradicts \eqref{eq1-cmp-uu}.
\end{proof}

In normed vector spaces that are uniformly uniquely geodesic, by rescaling balls, it is enough to define $\Phi(\cdot, 1)$ in order to obtain a modulus of uniform uniqueness: one can take $\Phi(\eps,b) = b\Phi(\eps/b,1)$ for all $\eps, b > 0$.

We show next that uniform convexity with a monotone modulus of uniform convexity $\eta$ implies uniform uniqueness of geodesics and one can define a modulus of uniform uniqueness in terms of $\eta$.

\begin{thm} \label{thm-UC-UU}
Let $(X,d)$ be a uniformly convex geodesic space that admits a monotone modulus of uniform convexity $\eta$. The $X$ is uniformly uniquely geodesic and $\Phi : (0,\infty)\times(0,\infty)\to (0,\infty)$ defined by
\[\Phi(\eps,b) = \eps \eta\left(\frac{\eps}{b+\eps}, b+\eps\right)\]
is a modulus of uniform uniqueness for $X$.

In addition, if $\eta$ can be written as $\eta(\eps,r) = \eps\tilde{\eta}(\eps,r)$, where $\tilde{\eta}$ is nondecreasing in $\eps$, then one can take
\[\Phi(\eps,b) = \eps \tilde{\eta}\left(\frac{\eps}{b+\eps}, b+\eps\right).\]
\end{thm}
\begin{proof}
Let $\eps,b > 0$ and denote $\varphi = \Phi(\varepsilon, b)$. Note that $\varphi \le \eps$.

Take $x,y,z\in X$, $r_1,r_2 \in (0,b]$ with
\[d(z,x)\le r_1,\quad d(z,y)\le r_2 + \varphi, \quad \text{and} \quad d(x,y)\ge r_1 + r_2.\]
We need to show that $\text{dist}(z,[x,y]) < \eps$. Suppose, on the contrary, that $\text{dist}(z,[x,y])\ge \eps$. In this case
\[\eps \le \text{dist}(z,[x,y]) \le d(z,y) \le r_2 + \varphi,\]
so
\begin{equation} \label{thm-UC-UU-eq1}
r_2 + \varphi \ge \eps.
\end{equation}
Let $z' \in [x,y]$ such that $d(x,z') = r_1$. As $d(x,z)\le r_1$ and
\[d(z,z') \ge \text{dist}(z,[x,y]) \ge \eps = \frac{\eps}{r_1}r_1,\]
by uniform convexity,
\begin{equation} \label{thm-UC-UU-eq2}
d\left(x,m(z,z')\right)\le \left(1-\eta\left(\frac{\varepsilon}{r_1},r_1\right)\right)r_1.
\end{equation}
Since
\[r_1 + d(z',y) = d(x,y) \leq d(z,x) + d(z,y) \leq r_1 + r_2 + \varphi,\]
it follows that $d(z',y) \le r_2 + \varphi$. Moreover, $d(y,z) \le r_2 + \varphi$ and
\[d(z,z') \ge \eps \ge \frac{\eps}{b+\eps}(r_2+\varphi).\]
Again, by uniform convexity,
\begin{equation} \label{thm-UC-UU-eq3}
d\left(y,m(z,z')\right)\le \left(1-\eta\left(\frac{\varepsilon}{b+\eps},r_2 + \varphi\right)\right)(r_2 + \varphi).
\end{equation}
Hence,
\begin{align*}
r_1 + r_2 & \le d(x,y) \le d(x,m(z,z')) + d(y,m(z,z'))\\
& \le \left(1-\eta\left(\frac{\eps}{r_1},r_1\right)\right)r_1 + \left(1-\eta\left(\frac{\eps}{b+\eps},r_2 + \varphi\right)\right)(r_2 + \varphi) \quad \text{by } \eqref{thm-UC-UU-eq2} \text{ and }\eqref{thm-UC-UU-eq3}\\
& \le r_1 + r_2 - r_1\eta\left(\frac{\eps}{r_1},r_1\right) + \varphi - \eps\eta\left(\frac{\eps}{b+\eps},r_2 + \varphi\right) \quad \text{by }\eqref{thm-UC-UU-eq1}.
\end{align*}
Using the monotonicity of $\eta$ we obtain
\[0 < r_1\eta\left(\frac{\varepsilon}{r_1 },r_1\right)\le \varphi - \eps \eta\left(\frac{\eps}{b+\eps}, b+\eps\right),\]
a contradiction.

Suppose now $\eta(\eps,r) = \eps\tilde{\eta}(\eps,r)$ with $\tilde{\eta}$ nondecreasing in $\eps$. As $d(z',y) \le r_2 + \varphi$, $d(y,z) \le r_2 + \varphi$ and
\[d(z,z') \ge \eps = \frac{\eps}{r_2+\varphi}(r_2+\varphi),\]
by uniform convexity and the monotonicity of $\eta$ we have
\begin{align*}
d\left(y,m(z,z')\right)&\le \left(1-\eta\left(\frac{\varepsilon}{r_2 + \varphi},r_2 + \varphi\right)\right)(r_2 + \varphi)\\
& \le \left(1-\eta\left(\frac{\varepsilon}{r_2 + \varphi},b+\eps\right)\right)(r_2 + \varphi)\\
& = \left(1-\frac{\varepsilon}{r_2 + \varphi}\tilde{\eta}\left(\frac{\varepsilon}{r_2 + \varphi},b+\eps\right)\right)(r_2+\varphi).
\end{align*}
Using the monotonicity of $\tilde{\eta}$ we obtain
\begin{equation} \label{thm-UC-UU-eq4}
d\left(y,m(z,z')\right) \le \left(1-\frac{\varepsilon}{r_2 + \varphi}\tilde{\eta}\left(\frac{\varepsilon}{b+\eps},b+\eps\right)\right)(r_2+\varphi).
\end{equation}
The same reasoning as before applying now \eqref{thm-UC-UU-eq4} instead of \eqref{thm-UC-UU-eq3} finishes the proof.
\end{proof}

In particular, using \eqref{eq-mod-Lp}, for $1 < p < \infty$, $L_p$ spaces over measurable spaces admit a modulus of uniform uniqueness $\Phi : (0,\infty)\times(0,\infty)\to (0,\infty)$ defined by
\begin{equation}
\Phi(\eps,b)=\left\{
\begin{array}{ll}
\displaystyle\frac{p-1}{8}\frac{\eps^2}{(b+\eps)}, & \mbox{if } 1 < p \le 2,\\
\displaystyle\frac{1}{p2^p}\frac{\eps^{p}}{(b+\eps)^{p-1}}, & \mbox{if } 2 < p < \infty.
\end{array}
\right.
\end{equation}
If $X$ is $p$-uniformly convex with parameter $c$, then, according to \eqref{eq-mod-p-UC},
\begin{equation}
\Phi(\eps,b) = \frac{c}{8p}\frac{\eps^p}{(b+\eps)^{p-1}},
\end{equation}
acts as a modulus of uniform uniqueness for $X$.

Revisiting Example \ref{ex-sphere} we can immediately notice that there exist uniformly uniquely geodesic spaces that are not uniformly convex. Indeed, any octant of ${\mathbb{S}}^2$ is a compact uniquely geodesic space, thus, by Proposition \ref{rmk-cpt}, it is uniformly uniquely geodesic. However, it is not strictly convex, and hence not uniformly convex.

On the other hand, recall that in normed vector spaces, strict convexity is equivalent to uniqueness of geodesics. This equivalence still holds when passing to the uniform versions of these properties. Namely, Theorems \ref{thm-UC-UU} and \ref{thm-normed-UU-UC} show that uniform uniqueness of geodesics is equivalent to uniform convexity, and respective moduli can be expressed in terms of each other. Before proving Theorem \ref{thm-normed-UU-UC}, we recall the following property of the modulus of convexity. Its proof can be found e.g. in \cite[p. 56]{GK90}, but since it is short, for completeness we include it below.

\begin{lem}[Goebel and Kirk \cite{GK90}] \label{lemma-mod-conv}
Let $(X,\|\cdot\|)$ be a normed vector space with modulus of convexity $\delta$ and characteristic of convexity $\eps_0$. If $\eps_0 < 2$, then
\[\delta(2(1-\delta(\eps))) \le 1 - \frac{\eps}{2},\]
for all $\eps \in (\eps_0,2]$.
\end{lem}
\begin{proof}
Let $\eps \in (\eps_0,2]$. Clearly, if $\delta(\eps) = 1$ (which can only happen for $\eps = 2$), then the inequality holds. Moreover, $\delta(\eps) > 0$ and so we can assume that $\delta(\eps) \in (0,1)$. Let $\tau \in (0,1-\delta(\eps))$ and take $x, y \in X$ with
\[\|x\|=\|y\|=1, \quad \|x-y\|\ge \eps, \quad \text{and} \quad \left\|\frac{x+y}{2}\right\| \ge 1 - \delta(\eps) - \tau.\]
As $\delta$ is nondecreasing, we get $\delta(\|x+y\|) \ge \delta(2(1-\delta(\eps)-\tau))$. Furthermore,
\[\frac{\eps}{2} \le \frac{\|x-y\|}{2} = \frac{\|x+(-y)\|}{2} \le 1 - \delta(\|x-(-y)\|) = 1 - \delta(\|x+y\|).\]
Hence,
\[\delta(2(1-\delta(\eps)-\tau)) \le 1 - \frac{\eps}{2}\]
and we only need to let $\tau \searrow 0$ to obtain the desired inequality.
\end{proof}

\begin{thm}\label{thm-normed-UU-UC}
Let $(X,\|\cdot\|)$ be a normed vector space that is uniformly uniquely geodesic with a modulus of uniform uniqueness $\Phi$ satisfying $\Phi < 1$. Then $X$ is uniformly convex and its modulus of convexity $\delta$ can be estimated by
\[\delta(\eps) \ge \frac{1}{2}\Phi\left(\frac{\eps}{3},1\right),\]
for all $\eps \in (0,2]$. In particular, $\eta:(0,2] \rightarrow (0,1]$ defined by
\[\eta(\eps) = \frac{1}{2}\Phi\left(\frac{\eps}{3},1\right)\]
is a modulus of uniform convexity for $X$.
\end{thm}
\begin{proof}
Let $\eps_0$ be the characteristic of convexity of $X$ and denote for simplicity $\varphi : (0,\infty) \to (0,1)$, $\varphi(\eps)=\Phi(\eps,1)$.

We show first that $\eps_0 < 2$. If $\eps_0 = 2$, then $\delta(2-\varphi(1/2)) = 0$, so there exist $x,y \in X$ with
\[\|x\|=\|y\|=1, \quad \|x-y\| \ge 2-\varphi(1/2), \quad \text{and} \quad \left\|\frac{x+y}{2}\right\| > \frac{1}{2}.\]
Writing $\|y\| = 1 - \varphi(1/2) + \varphi(1/2)$, by uniform uniqueness,
\[\left\|\frac{x+y}{2}\right\| = \text{dist}(0,[x,y]) < \frac{1}{2},\]
a contradiction.

Since $\delta$ is continuous on $[0,2)$, we have $\delta(\eps_0) = 0$. Suppose that $\eps_0 > 0$. Then we can take $\eps \in (\eps_0,2)$ such that $\delta(\eps) < \varphi(\eps_0/2)/2$. Applying Lemma \ref{lemma-mod-conv}, there exist $x,y \in X$ such that
\[\|x\|=\|y\|=1, \quad \|x-y\|\ge 2(1-\delta(\eps)), \quad \text{and} \quad \left\|\frac{x+y}{2}\right\| > \frac{\eps_0}{2}.\]
Because $\|y\|=1-\varphi(\eps_0/2) + \varphi(\eps_0/2)$ and $\|x-y\|\ge 2 - \varphi(\eps_0/2)$, we get
\[\left\|\frac{x+y}{2}\right\| < \frac{\eps_0}{2},\]
another contradiction. Therefore, $\eps_0 = 0$, so $X$ is uniformly convex.

Assume now that $\delta(\eps) < \varphi(\eps/3)/2$ for some $\eps \in (0,2]$. By Lemma \ref{lemma-mod-conv}, there exist $x,y \in X$ satisfying
\[\|x\|=\|y\|=1, \quad \|x-y\| \ge 2(1-\delta(\eps)), \quad \text{and} \quad \left\|\frac{x+y}{2}\right\| > \frac{\eps}{3}.\]
Arguing as before one shows that the assumption is false, hence the desired estimate holds.
\end{proof}

We describe next another convexity condition that refers to betweenness and plays in \cite{LNP1} an important role in the study of the Lion-Man game and whose quantitative uniform version will be essential in the proof of our main result. Postulates for betweenness relations and their relevance with other convexity conditions already appeared in very early works such as \cite{HK17,DW}. Here we consider the following relation.
\begin{de}\label{def-BTW}
A subset $A$ of a uniquely geodesic space $X$ satisfies the {\it betweenness property} if for every four pairwise distinct points $x,y,z,w \in A$,
\begin{eqnarray}\nonumber
\left.\begin{array}{l}
y \in [x,z]\\
z \in [y,w]
\end{array}
\right\}
& \Rightarrow & y,z \in [x,w].
\end{eqnarray}
\end{de}
This property was further studied in connection to the geometry of geodesic spaces in \cite{Pap05,Nic13,LNP1}. Proposition 3.4 in \cite{Nic13} shows in particular that the betweenness property holds in every uniquely geodesic space $X$ satisfying the following convexity condition
\begin{equation}\label{eq-metric-conv}
d(z,(1-t)x+ty) \le (1-t)d(z,x) + td(z,y),
\end{equation}
for all $x,y,z \in X$ and all $t \in [0,1]$. In other words, given any $z \in X$, the function $d(z,\cdot)$ is convex. This condition holds e.g. in any strictly convex normed space, any geodesic space that is nonpositively curved in the sense of Busemann or in any CAT$(\kappa)$ space (of diameter smaller than $\pi/(2\sqrt{\kappa})$ if $\kappa > 0$).

We introduce now a quantitative uniform variant of this property.
\begin{de}\label{def-UBTW}
We say that $X$ satisfies the {\it uniform betweenness property} if for all $\eps,a,b >0$ there exists $\theta > 0$ such that for all $x,y,z,w\in X$ we have
\begin{eqnarray} \nonumber
\left.\begin{array}{l}
\sep\{x,y,z,w\}\ge a\\
\diam\{x,y,z,w\} \le b\\
\text{dist}(y,[x,z]) < \theta\\
\text{dist}(z,[y,w]) < \theta
\end{array}
\right\}
& \Rightarrow & \max \left\{\text{dist}(y,[x,w]), \text{dist}(z,[x,w]) \right\} < \eps.
\end{eqnarray}
A mapping $\Theta :(0,\infty)\times(0,\infty)\times(0,\infty) \to (0,\infty )$ providing for given $\eps, a, b > 0$ such a $\theta = \Theta(\eps,a,b)$ is called {\it a modulus of uniform betweenness}.
\end{de}

In the presence of compactness, betweenness coincides with uniform betweenness. The proof of this fact is similar to the one of Proposition \ref{rmk-cpt}.
\begin{pro} \label{rmk-cpt-btw}
Compact uniquely geodesic spaces with the betweenness property satisfy the uniform betweenness property as well.
\end{pro}

The remainder of this subsection is devoted to showing that uniformly uniquely geodesic spaces where \eqref{eq-metric-conv} holds also satisfy the uniform betweenness property. In addition, given a modulus of uniform uniqueness, one can convert it into a modulus of uniform betweenness. First we prove a rather technical property needed to this end and also in the proof of the main result.
\begin{lem} \label{lemma-UU}
Let $(X,d)$ be a uniformly uniquely geodesic space with a modulus of uniform uniqueness $\Phi$ satisfying $\Phi(\eps,b) < \eps$ for all $\eps,b>0$. Let $\eps, b >0$, $x,y,z\in X$ with
\[\max\{d(x,y),d(x,z)\} \le b \quad \text{and} \quad d(y,z) \le \frac{1}{2}\Phi(\eps,b).\]
Then
\[\max\{\dist(y_t,[x,z]), \dist(z_t,[x,y])\} < \eps,\]
for all $t \in [0,1]$, where $y_t = (1-t) x+ ty$ and $z_t = (1-t) x+ tz$.
\end{lem}
\begin{proof}
By symmetry, it is enough to prove that $\text{dist}(y_t,[x,z])< \eps$. First note that for $t\in\{0,1\}$ the conclusion is immediate. Thus, we may assume $t\in (0,1)$. By the triangle inequality,
\[d(y_t,z) \le d(y_t,y) + d(y,z) = (1-t)d(x,y) + d(y,z).\]
If $(1-t)d(x,y) \le d(y,z)$, then
\[d(y_t,z) \le 2d(y,z) \le \Phi(\eps,b)<\eps,\]
hence $\text{dist}(y_t,[x,z])< \eps$. Otherwise, $(1-t)d(x,y) > d(y,z)$ and we denote
\[r_1=td(x,y) \quad \text{and} \quad r_2=(1-t)d(x,y)-d(y,z).\]
Clearly, $r_1,r_2 \in (0,b]$. As $d(y_t,x) = td(x,y) = r_1$,
\[d(y_t,z)\le 2 d(y,z)+r_2 \le \Phi(\eps,b)+r_2\]
and
\[d(x,z) \ge d(x,y) - d(y,z) = r_1+r_2,\]
by uniform uniqueness, $\text{dist}(y_t,[x,z])< \eps$.
\end{proof}

\begin{thm}\label{thm-UU-UBTW}
Let $(X,d)$ be a uniformly uniquely geodesic space with a modulus of uniform uniqueness $\Phi$ satisfying $\Phi(\eps,b) < \eps$ for all $\eps,b>0$. Additionally, suppose that \eqref{eq-metric-conv} holds for all $x,y,z \in X$ and all $t \in [0,1]$. Then $X$ satisfies the uniform betweenness property and the mapping $\Theta :(0,\infty)\times(0,\infty)\times(0,\infty) \to (0,\infty )$ defined by
\[\Theta(\eps,a,b) =\frac{1}{2}\min\left\{\eps,\Phi\left(\frac{a}{6b}\Phi\left(\frac{\Phi(\eps/2,b)}{2},b\right),b+\frac{\eps}{2}\right)\right\}\]
for $\eps \le a$ and by $\Theta(\eps,a,b)=\Theta(a,a,b)$ for $\eps > a$ is modulus of uniform betweenness for $X$.
\end{thm}
\begin{proof}
Let $\eps,a,b>0$. Note that it is sufficient to consider the case $\eps \le a$. Denoting $\theta= \Theta(\eps,a,b)$, we have
\begin{equation}\label{thm-UU-UBTW-eq1}
\theta \le \frac{\eps}{2}\le\frac{a}{2}.
\end{equation}
Let $x,y,z,w \in X$ such that
\[\sep\{x,y,z,w\}\ge a, \quad \diam\{x,y,z,w\} \le b, \quad \text{dist}(y,[x,z]) < \theta, \quad \text{and} \quad \text{dist}(z,[y,w]) < \theta.\]
Denote
\[\tau = \frac{a}{6b}\Phi\left(\frac{\Phi(\eps/2,b)}{2},b\right).\]
Then
\begin{equation}\label{thm-UU-UBTW-eq2}
\theta < \frac{\tau}{2}
\end{equation}
and
\begin{equation}\label{thm-UU-UBTW-eq3}
\tau < \frac{a}{6b}\frac{\Phi(\eps/2,b)}{2} < \frac{a\eps}{24b} \le \frac{a^2}{24b}
\end{equation}
Let $z'\in [y,w]$ and $y^*\in [x,z]$ with $d(z',z) < \theta$ and $d(y^*,y)< \theta$. Observe now that
\[d(z',z) < \theta \le \frac{\Phi(\tau,b+\eps/2)}{2}.\]
At the same time,  $d(z,x)\le b$ and
\[d(z',x)\le d(z,x)+d(z',z)\le b+\theta \le b+\frac{\eps}{2}.\]
Using Lemma \ref{lemma-UU} we deduce $\text{dist}(y^*,[x,z'])<\tau$, hence there exists $y'\in [x,z']$ such that $d(y^*,y') < \tau$. Therefore,
\[d(y,y') \le d(y,y^*) + d(y^*,y') < \theta + \tau < \frac{3\tau}{2} \quad \text{by }\eqref{thm-UU-UBTW-eq2}.\]
By the triangle inequality,
\[d(x,y)\le d(x,y')+\frac{3\tau}{2} \quad \text{and} \quad d(y,z')\le d(z',y') + \frac{3\tau}{2}.\]
Adding these two inequalities we obtain
\begin{equation}\label{thm-UU-UBTW-eq4}
d(x,y)+d(y,z') \le d(x,z') + 3\tau.
\end{equation}
As $z' \in [y,w]$, there exists $t \in [0,1]$ such that $z' = (1-t) y + t w$.  Since
\[tb \ge t d(y,w) = d(y,z') \ge d(y,z)-d(z,z') > a-\theta \ge \frac{a}{2} \quad \text{by }\eqref{thm-UU-UBTW-eq1},\]
we get $t \ge a/(2b)$. Then
\begin{align*}
d(x,y) + td(y,w) & = d(x,y)+d(y,z') \\
& \le d(x,z') + 3\tau \quad \text{by }\eqref{thm-UU-UBTW-eq4}\\
& \le (1-t)d(x,y)+td(x,w)+3\tau \quad \text{by }\eqref{eq-metric-conv}.
\end{align*}
Thus,
\begin{equation}\label{thm-UU-UBTW-eq5}
d(x,y)+d(y,w)\le d(x,w)+\frac{3\tau}{t}\le d(x,w)+\frac{6b}{a}\tau.
\end{equation}
Denote $r_1 = d(x,y)$ and
\[r_2 = d(y,w) - \frac{6b}{a}\tau \ge a - \frac{6b}{a}\tau > \frac{3a}{4} > 0 \quad \text{by }\eqref{thm-UU-UBTW-eq3}.\]
Thus, $r_1,r_2 \in (0,b]$, $d(x,w) \ge r_1 + r_2$ by \eqref{thm-UU-UBTW-eq5}, and
\[d(y,w) = r_2 + \frac{6b}{a}\tau = r_2 +\Phi\left(\frac{\Phi(\eps/2,b)}{2},b\right).\]
By uniform uniqueness,
\[\text{dist}(y,[x,w])<  \frac{\Phi(\eps/2,b)}{2} < \eps.\]
This means that there exists $y^{**} \in [x,w]$ such that $d(y,y^{**}) < \Phi(\eps/2,b)/2$. Because $z' \in [y,w]$, using again Lemma \ref{lemma-UU} we obtain $\text{dist}(z',[y^{**},w]) < \eps/2$, so $\text{dist}(z',[x,w]) < \eps/2$. Therefore,
\[\text{dist}(z,[x,w]) \le d(z,z') + \text{dist}(z',[x,w]) < \theta + \frac{\eps}{2} \le \eps \quad \text{by } \eqref{thm-UU-UBTW-eq1}.\]
 \end{proof}

\section{A rate of convergence for the Lion-Man game}\label{section-rate}

The main goal of this section is to analyze the Lion-Man game from the quantitative viewpoint using the convexity notions and results given in Section \ref{section-conv}. We recall first the exact definition of the game.

Let $(X,d)$ be a uniquely geodesic space and $A \subseteq X$ nonempty and convex. Take $D > 0$ and suppose that $L_0, M_0 \in A$ are the starting points of the lion and the man, respectively. At step $n+1$, $n \in \N$, the lion moves from the point $L_n$ to the point $L_{n+1} \in [L_n,M_n]$ such that $d(L_n,L_{n+1}) = \min\{D,d(L_n,M_n)\}$. The man moves from the point $M_n$ to any point $M_{n+1} \in A$ as long as $d(M_n,M_{n+1}) \le D$. We say that lion wins if the sequence $(d(L_{n+1},M_n))$ converges to $0$. Otherwise the man wins.

Denote $D_n = d(L_n,M_n)$, $n \in \N$. Note first that if $D_n \ge D$, then
\begin{equation}\label{eq-Dn-decr}
D_{n+1} \le d(L_{n+1},M_n) + d(M_n,M_{n+1}) = D_n - D + d(M_n,M_{n+1}) \le D_n.
\end{equation}
Thus, if $D_n \ge D$ for all $n \in \N$, then $(D_n)$ is nonincreasing.

We can distinguish two mutually exclusive situations when the lion wins:
\begin{itemize}
\item[(1)] there exists $n_0 \in \N$ such that $D_{n_0} < D$.
\item[(2)] $D_n \ge D$ for all $n \in \N$ and $\lim_{n \to \infty}D_n = D$.
\end{itemize}

The main result of this paper provides a rate for $D$ being an approximate upper bound on $(D_n)$ (and as a consequence, a rate of convergence for the sequence $(d(L_{n+1},M_n))$ towards $0$) under appropriate regularity conditions imposed on the geodesic space that ensure the success of the lion. These conditions refer to uniform uniqueness of geodesics and uniform betweenness. We fix below the precise setting and notation we consider.

Let $A \subseteq X$ be a nonempty, convex and bounded set of diameter $b \ge D$ where the Lion-Man game is played. Take $N \in \N$ such that
\begin{equation}\label{eq-diam-A}
b+1 < ND.
\end{equation}

Suppose that $X$ is uniformly uniquely geodesic with a modulus of uniform uniqueness $\Phi$. Moreover, assume that $X$ satisfies the uniform betweenness property with a modulus of uniform betweenness $\Theta$ and that the moduli $\Phi$ and $\Theta$ satisfy the condition
\begin{equation}\label{eq-Phi-Theta-eps}
\Phi(\eps, b) < \eps \quad \text{and} \quad \Theta(\eps,a,b) < \eps \quad \text{for all }\eps,a>0.
\end{equation}
Additionally, denote
\[\Delta(\eps) = \Theta(\eps,\eps,b) \quad \text{and} \quad \Psi(\eps) = \frac{\Phi(\Delta(\eps),b)}{2} \quad \text{for all } \eps > 0.\]
Then
\begin{equation}\label{eq-Psi-Delta-eps}
\Psi(\eps) < \Delta(\eps) < \eps,
\end{equation}
for all $\eps > 0$.

Before giving our main result, we recall the following property of bounded nonincreasing real sequences which follows from Proposition 2.27
and Remark 2.29 in \cite{K08}.
\begin{lem}[Kohlenbach \cite{K08}] \label{lemma-mon-seq}
Let $b>0$ and $(a_n)$ be a nonincreasing sequence in $[0,b]$. Then
\[\forall \tau > 0\; \forall g:\N\to\N\; \exists I \le \tilde{g}^{\left(\left\lceil\frac{b}{\tau}\right\rceil\right)}(0) \; \forall n,m\in[0,g(I)]\; \left(|a_{I+n} - a_{I+m}| \le \tau\right),\]
where $\tilde{g} = \text{Id}+g$.
\end{lem}

\begin{thm}\label{thm-main}
For all $\alpha > 0$ and all $n \ge \Omega_{D,b,N,\Phi,\Theta}(\alpha)$, $D_n < D + \alpha$,
where
\[\Omega_{D,b,N,\Phi,\Theta}(\alpha) = N + \Gamma_{b,\Phi,\Theta}(\eps), \quad \Gamma_{b,\Phi,\Theta}(\eps) = N\left\lceil\frac{b}{\Phi(\Psi^N(\eps),b)}\right\rceil\]
and
\begin{equation} \label{thm-main-eq-eps}
\quad 0 < \eps \le \min\left\{\frac{1}{3N},\frac{D}{4},\frac{\alpha}{3}\right\}.
\end{equation}
\end{thm}
\begin{proof}
Let $\alpha > 0$. We use the notation introduced above. For simplicity, denote
\[\omega = \Omega_{D,b,N,\Phi,\Theta}(\alpha).\]
Suppose first that there exists $n_0 \in \mathbb{N}$ such that $D_{n_0} < D$. If $n_0 \le \omega$, then for all $n \ge n_0$, $D_n \le D < D+\alpha$ and the conclusion holds.

So we only need to consider the following two cases:
\begin{itemize}
\item[(i)] there exists $n_0 > \omega$ with $D_{n_0} < D$ and $D_n \ge D$ for all $n \le n_0 - 1$.
\item[(ii)] $D_n \ge D$ for all $n \in \mathbb{N}$.
\end{itemize}

Observe that in case (i), applying \eqref{eq-Dn-decr}, $D_{n+1} \le D_n$ for all $n \le n_0 - 1$. Then it is enough to show that there exists $n \le \omega$ such that $D_n < D+\alpha$. Indeed, if $k \in [\omega, n_0-1]$, then $D_k \le D_\omega \le D_n < D+ \alpha$. Otherwise, if $k \ge n_0$, $D_k \le D < D+\alpha$.

For case (ii), as $(D_n)$ is nonincreasing, again we only need to show that there exists $n \le \omega$ such that $D_n < D+\alpha$. Consequently, in the following we treat both cases at once.

Consider the sequence $(E_n)$ defined by
\[
E_n=\left\{
\begin{array}{ll}
D_n, & \mbox{if } n \le \omega,\\
D, & \mbox{otherwise}.
\end{array}
\right.
\]
This is a nonincreasing sequence in $[0,b]$ and we can apply Lemma \ref{lemma-mon-seq} taking $\tau = \Phi(\Psi^N(\eps),b)$ and the function $g$ constantly equal to $N$. Thus, there exists $I \le \Gamma_{b,\Phi,\Theta}(\eps)$ such that for all $n,m \in [0,N]$,
\begin{equation} \label{thm-main-eq1}
|D_{I+n} - D_{I+m}| \le \Phi(\Psi^N(\eps),b).
\end{equation}
Note that for all $n \in [0,N]$, $I + n \le \omega$, so $E_{I+n} = D_{I+n}$. Assume that for all $n \in [0, N]$, $D_{I+n} \ge D+\alpha$. Denoting $\gamma = D_{I+N} - D \ge \alpha$, we have
\begin{align*}
D+\gamma & = D_{I+N} \le D_{I+n} \\
& \le D_{I+N} + \Phi(\Psi^N(\eps),b) \quad \text{by }\eqref{thm-main-eq1}\\
& = D + \gamma + \Phi(\Psi^N(\eps),b),
\end{align*}
hence
\begin{equation} \label{thm-main-eq2}
D+\gamma \le D_{I+n} \le D + \gamma + \Phi(\Psi^N(\eps),b),
\end{equation}
for all $n \in [0,N]$.

Denote now $l_n = L_{I+n}$ and $m_n = M_{I+n}$ for $n\in[0,N]$. Then $d(l_n,m_n) = D_{I+n}$.
\begin{claim}
$\dist(l_n,[l_0,m_n]) < \Psi^{N-n}(\eps)$ \text{ and } $d(l_0,l_n) \ge n(D-3\eps)$ for all $n \in [0, N]$.
\end{claim}
\begin{proof}[Proof of Claim]
For $n=0$, the two inequalities are obviously true. Suppose that they hold for $n=k \le N-1$. We prove that they also hold for $n=k+1$.

Let $p \in [l_0,m_k]$ such that
\[d(l_k,p) < \Psi^{N-k}(\eps)=\frac{1}{2}\Phi(\Delta(\Psi^{N-k-1}(\eps)),b).\]
Because $l_{k+1} \in [l_k,m_k]$, by Lemma \ref{lemma-UU}, $\text{dist}(l_{k+1},[p,m_k]) < \Delta(\Psi^{N-k-1}(\eps))$, hence
\begin{equation}\label{thm-main-claim-eq1}
\text{dist}(l_{k+1},[l_0,m_k]) < \Delta(\Psi^{N-k-1}(\eps))
\end{equation}
and, by \eqref{eq-Psi-Delta-eps}, $d(l_k,p)  < \eps$. Then
\begin{equation}\label{thm-main-claim-eq2}
d(l_0,p) \ge d(l_0,l_k) - d(l_k,p) > k(D-3\eps) - \eps.
\end{equation}
At the same time, as $D+\gamma \le d(l_k,m_k)$ by \eqref{thm-main-eq2},
\begin{equation}\label{thm-main-claim-eq3}
d(p,m_k) \ge d(l_k,m_k) - d(l_k,p) > D + \gamma - \eps.
\end{equation}
Adding \eqref{thm-main-claim-eq2} and \eqref{thm-main-claim-eq3},
\begin{equation}\label{thm-main-claim-eq4}
d(l_0,m_k) = d(l_0,p) + d(p,m_k) > (k+1)D + \gamma - (3k+2)\eps.
\end{equation}
Hence,
\begin{align*}
d(l_0,l_{k+1}) & \ge d(l_0,m_k) - d(l_{k+1},m_k) = d(l_0,m_k) - D_{I+k} + D\\
& \ge d(l_0,m_k) - \gamma - \Phi(\Psi^N(\eps),b) \quad \text{by }\eqref{thm-main-eq2}\\
& \ge d(l_0,m_k) - \gamma - \eps \quad \text{by }\eqref{eq-Phi-Theta-eps} \text{ and } \eqref{eq-Psi-Delta-eps}\\
& \ge (k+1)(D-3\eps) \quad \text{by }\eqref{thm-main-claim-eq4}.
\end{align*}
Because $d(m_k,m_{k+1}) \le D$, $d(m_k,l_{k+1}) \le \gamma + \Phi(\Psi^N(\eps),b)$, $d(m_{k+1},l_{k+1}) \ge D+\gamma$ by \eqref{thm-main-eq2}, and $D,\gamma \in (0,b]$, using the uniform uniqueness and \eqref{eq-Psi-Delta-eps} we get
\begin{equation}\label{thm-main-claim-eq5}
\text{dist}(m_k,[m_{k+1},l_{k+1}]) < \Psi^N(\eps) < \Psi^{N-k}(\eps) < \Delta(\Psi^{N-k-1}(\eps)).
\end{equation}
We verify next that $\sep\{l_0,l_{k+1},m_k,m_{k+1}\} \ge \eps$. Using \eqref{thm-main-eq-eps}, \eqref{thm-main-claim-eq4} and \eqref{thm-main-eq2} it is easy to see that
\begin{enumerate}
\item $d(l_0,l_{k+1}) \ge (k+1)(D-3\eps) \ge \eps$.
\item $d(l_0,m_k) \ge (k+1)D + \gamma - (3k+2)\eps \ge (k+1)(D-3\eps) + \alpha \ge 4\eps$.
\item $d(l_0,m_{k+1}) \ge d(l_0,m_k) - d(m_k,m_{k+1}) \ge k(D-3\eps)+\gamma - 2\eps \ge \eps$.
\item $d(l_{k+1},m_k) = D_{I+k} - D \ge \gamma \ge 3\eps.$
\item $d(l_{k+1},m_{k+1}) = D_{I+k+1} \ge D+\gamma \ge 7\eps$.
\item $d(m_k,m_{k+1}) \ge d(l_{k+1},m_{k+1}) - d(l_{k+1},m_k) \ge D+\gamma - \gamma -  \eps \ge 3\eps.$
\end{enumerate}
As $\diam\{l_0,l_{k+1},m_k,m_{k+1}\} \le b$, taking into account \eqref{thm-main-claim-eq1} and \eqref{thm-main-claim-eq5}, the uniform betweenness property yields $\dist(l_{k+1},[l_0,m_{k+1}]) < \Psi^{N-k-1}(\eps)$. This finishes the proof of the claim.
\end{proof}

Consequently,
\begin{align*}
d(l_0,l_N) & \ge N(D-3\eps) \\
& > b+1-3N\eps \quad \text{by }\eqref{eq-diam-A}\\
& \ge b \quad \text{by }\eqref{thm-main-eq-eps},
\end{align*}
a contradiction to the fact that $b$ is the diameter of $A$. This shows that there exists $n \le I + N \le \omega$ such that $D_n < D + \alpha$.
\end{proof}

As an immediate consequence we obtain the next result.
\begin{co}\label{co-main}
For all $\alpha > 0$ and all $n \ge \Omega_{D,b,N,\Phi,\Theta}(\alpha)$, $d(L_{n+1},M_n) < \alpha$, where $\Omega_{D,b,N,\Phi,\Theta}$ is defined above.
\end{co}
\begin{proof}
Let $n \ge \Omega_{D,b,N,\Phi,\Theta}(\alpha)$. According to Theorem \ref{thm-main},
\[d(L_{n+1}, M_n) = \max\{0,D_n-D\} < \alpha.\]
\end{proof}

\begin{re}
As the domain of the game is the set $A$, it is sufficient for the conditions referring to uniform uniqueness and uniform betweenness to hold only on $A$.
\end{re}

Based on the discussion from Section \ref{section-conv}, it is immediate that Theorem \ref{thm-main} applies in particular for $L_p$ spaces over measurable spaces with $1 < p < \infty$ and $\CAT(\kappa)$ spaces with diameter smaller than $\pi/(2\sqrt{\kappa})$ if $\kappa > 0$. For these classes of spaces, using \eqref{eq-mod-Lp}, \eqref{eq-mod-p-UC} and Theorem \ref{thm-UU-UBTW}, we have explicit moduli $\Phi$ and $\Theta$ satisfying \eqref{eq-Phi-Theta-eps} and therefore we can compute the exact expression of the rate of convergence provided by Theorem \ref{thm-main}. Disregarding the quantitative aspect, in the setting of $\CAT(\kappa)$ spaces, this recovers corresponding results from \cite{AleBisGhr10}.

Observe that Theorem \ref{thm-main} also guarantees the success of the lion when the Lion-Man game is played in a bounded and convex subset of a uniformly convex normed space. Moreover, by Propositions \ref{rmk-cpt} and \ref{rmk-cpt-btw}, we obtain as a consequence one of the implications proved in \cite[Theorem 4.2]{LNP1}, namely that the lion always wins the Lion-Man game played in a compact uniquely geodesic space that satisfies the betweenness property.

\section{Comments on the use of logic in arriving at the quantitative analysis (`proof mining')}

The point of departure for the investigation in this paper has been the
noneffective proof for the convergence $\lim_{n\to \infty} D_n=D,$ when
$D_n\ge D$ for all $n\in\N$, for {\it compact} uniquely geodesic spaces
satisfying the betweenness property as given in \cite{LNP1} (see Theorem
4.2). Since the sequence $(D_n)$ {\it decreases} to $D$ this statement is
of the logical form
\[ \forall k\in\N\,\exists n\in\N\, \left(D_n<D+\frac{1}{2^{n}}\right)\in \forall\exists.\]
General logical metatheorems due to the first author (see, e.g.,
\cite{K08}) guarantee in such situations the extractability of an
explicit and effective rate of convergence which only depends on general
metric bounds, a modulus of total boundedness (as a quantitative form of
the compactness assumption), and moduli providing quantitative forms of
`uniformized' versions of being `uniquely geodesic' and satisfying the
`betweenness property'. Technically speaking, these moduli serve to
produce a solution for the monotone G\"odel functional interpretation (see \cite{K08}) of
the respective properties which in this uniformized form become (essentially)
purely universal assumptions in these moduli which can be taken as
number-theoretic functions (although, for convenience, we used their
$\varepsilon/\delta$-variants). Hence, the moduli can w.l.o.g. be assumed to be
self-majorizing (in the technical sense of \cite{K08}) which would not be the
case if these moduli would not be uniform by depending on points in $X.$

In the case of uniqueness of geodesics,
the process of uniformization and subsequent witnessing by a modulus
$\Phi:\N^2\to \N$
yields
\[
\forall k,b\in\N\,\forall x,y,z\in X\, \forall r_1,r_2 \in [0,b]
\left(
\left.\begin{array}{l}
d(z,x)<r_1 \\
d(z,y)<r_2+\Phi(k,b)\\
d(x,y)>r_1+r_2
\end{array}
\right\}
\,\, \Rightarrow \,\, \mbox{dist}(z,[x,y])\le \frac{1}{2^{k}}\right),
\]
which is (using that $<,>$ resp. $\le$ on $\R$ are purely existential
resp. purely universal relations; see \cite[Chapter 4]{K08}) equivalent
(essentially)
to a purely universal sentence. We omit here various details on how
to represent $[x,y]$ by a suitable operator $W$ and also that there is
a bounded quantifier hidden in
\[\mbox{dist}(z,[x,y])\le \frac{1}{2^{k}}\]
which should be written as
\[\exists t\in [0,1] \,\left(d(z,W(t,x,y))\le \frac{1}{2^{k}}\right),\]
so that the sentence
actually has the form of an axiom $\Delta$ as in \cite{GK16} which is as good
as being purely universal in this context. For convenience, we use in our official definition of the
modulus the non-strict forms $\le,\ge$ in the premise and $<$ instead of
$\le$ in the
conclusion, which - modulo a simple shift in the modulus - of course is
inessential. A similar discussion applies
to the concepts of moduli of uniform convexity and the uniform betweenness
property.

The actual extraction of the rate of convergence in these moduli from the
convergence proof of \cite[Theorem 4.2]{LNP1} made this proof completely constructive by
avoiding altogether the (even nested)
sequential compactness argument used in the
original proof and hence the
need to assume compactness in the first place {\it once}
the uniqueness of geodesics and
the betweenness property are written in their uniform variants (to which they
are equivalent in the presence of compactness). As a consequence,
the actual rate of convergence extracted
only uses moduli for the uniform uniqueness of geodesics
and the uniform betweenness property, but no modulus of total boundedness.
The phenomenon that `compactness' disappears from the proof in the
process of its logical analysis is a feature of this particular proof
being analyzed (see \cite{KLN} for situations where this is not
the case).

The uniqueness of geodesics follows from the strict convexity of a
geodesic space. Again, the general methods from  \cite{K08} guarantee
that from a proof of this fact it must be possible to extract a procedure
on how to translate a modulus of {\it uniform} convexity into a modulus
of being {\it uniformly} uniquely geodesic (Theorem \ref{thm-UC-UU}). In a
normed vector space $X,$ the uniqueness of geodesics implies conversely
the strict convexity of $X.$ In line with general proof mining facts,
this explains why it must be possible to translate a modulus for being
uniformly uniquely geodesic into a modulus of uniform convexity of $X$ in
the linear case
(Theorem \ref{thm-normed-UU-UC}).

From the proof of the fact that the property of being uniquely geodesic
together with the convexity condition (\ref{eq-metric-conv})
implies the betweenness property,
the methods of proof mining guarantee that any given modulus for being
{\it uniformly} uniquely geodesic can be transformed into
a modulus for the uniform betweenness property (Theorem \ref{thm-UU-UBTW}).
This crucially uses that the convexity property can be written in
purely universal form
(and so only contributes to the verification of the new modulus but not to its
construction) when uniqueness of geodesics is already assumed as then
(\ref{eq-metric-conv}) follows from stipulating this only for
$W(t,x,y)$ instead of corresponding points on any geodesic (with $W$
satisfying the clauses $(i),(ii)$ of Definition 17.9 in
\cite{K08}).

As usual with case studies in proof mining, when the actual extraction of
the data in question is carried out it also comes with an ordinary
analytical proof of their correctness which does not refer to any
results from logic which, however, were instrumental for finding these data.


TITLE: Algebraic problem - Equation and mean value
QUESTION [0 upvotes]: "The price of a train-ticket is 110 dollars for grown-ups and 90 dollars for children. To a train, 120 tickets were sold for a total of 11640 dollars. How many grown-ups bought a ticket to the train?"
So here's my thought process:
$11640/120 = 97$
So now I have the mean value, but I have no idea how to get the number of grown-ups that bought a ticket and are on the train. Help is extremely appreciated!

REPLY [1 votes]: You're going about it the wrong way. Use elimination in a system of equations.
                                g + c = 120
                                110g + 90c = 11640

Then, you can turn the top equation negative, and simply forget about the reality of it.
                              -g - c = -120

Then, you multiply it by either 90 or 110, trying to remove one of the variables.
                           -90g - 90c = -10800

or
                           -110g - 110c = 13200

I'm going to use the first instance in this case(-90g - 90c = -10800) and add it to 110g + 90c = 11640, and I get 20g = 840. Then, you can divide by 20, giving you g = 42 or 42 grownups bought tickets for the train. You can then input it into one of your earlier equations, g + c = 120
                              g + c = 120
                              c = 120 - g

Then, lastly, you input grownups, and subtract, giving you your children, which is 78.
So, in the end, you get 42 grownups and 78 children riding your train.


TITLE: Understanding Power Series Multiplication Step
QUESTION [5 upvotes]: Working on Spivak's Calculus problems, I searched online, trying to understand the solution provided for Problem 4a of Chapter 2. I found the question I needed:
Spivak's Calculus - Exercise 4.a of 2nd chapter.
However, the answer provided there started with the following equation, and then went on from it to explain other things, which I could understand. But this part, which lies at the foundation of the argument, I don't understand.
Could I get an explanation for why it is that:
$$
\begin{align}
\left(\sum_{k=0}^\infty a_kx^k\right)\left(\sum_{k=0}^\infty b_kx^k\right)
&=\sum_{k=0}^\infty\left(\sum_{j=0}^k a_j\color{#C00000}{x^j}b_{k-j}\color{#C00000}{x^{k-j}}\right)
\end{align}
$$
Keep in mind I'm a beginner, working on an introductory Calculus book as my first exposure to the subject. I'd appreciate both intuitive and rigorous answers.

REPLY [9 votes]: Write the product out longhand:
$$\left(a_0+a_1x+a_2x^2+a_3x^3+\ldots\right)\left(b_0+b_1x+b_2x^2+b_3x^3+\ldots\right)\;.$$
This is the sum of all possible products of the form $(a_kx^k)(b_\ell x^\ell)=a_kb_\ell x^{k+\ell}$. The $x^n$ term in the product will therefore be the sum of all of these term $a_kb_\ell x^{k+\ell}$ for which $k+\ell=n$. Let’s look specifically at $n=3$, just to get a clearer picture of what’s going on. If $k+\ell=3$, where $k$ and $\ell$ are exponents in the two factors, then clearly $\langle k,\ell\rangle$ must be one of the pairs $\langle 0,3\rangle,\langle 1,2\rangle,\langle 2,1\rangle$, or $\langle 3,0\rangle$. Thus, the $x^3$ term in the product is
$$(a_0x^0)(b_3x^3)+(a_1x^1)(b_2x^2)+(a_2x^2)(b_1x^1)+(a_3x^3)(b_0x^0)=\sum_{k=0}^3(a_kx^k)(b_{3-k}x^{3-k})\;,$$
or
$$\left(a_0b_3+a_1b_2+a_2b_1+a_3b_0\right)x^3=\left(\sum_{k=0}^3a_kb_{3-k}\right)x^3\;.$$
If you generalize this to an arbitrary power $n$ of $x$, you get
$$(a_0x^0)(b_nx^n)+(a_1x^1)(b_{n-1}x^{n-1})+\ldots+(a_{n-1}x^{n-1})(b_1x^1)+(a_nx^n)(b_0x^0)=\sum_{k=0}^n(a_kx^k)(b_{n-k}x^{n-k})\;,$$
or
$$(a_0b_n+a_1b_{n-1}+\ldots+a_{n-1}b_1+a_nb_0)x^n=\left(\sum_{k=0}^na_kb_{n-k}\right)x^n\;.$$
In other words, the coefficient of $x^n$ in the product series is
$$\sum_{k=0}^na_kb_{n-k}\;.$$


text:
\section{Relating Algebraic and Tropical Enumerative Geometry}
\label{tSec:Relating Algebraic and Tropical Enumerative Geometry}

We have seen in the previous section that the problems of counting algebraic curves and tropical curves are very closely related. In fact, given the formulation of the classical problem as the determination of the number of points in intersections of preimages of generic points via the evaluation maps, we obtain the tropical problem by tropicalizing the moduli space and the evaluation maps and then formulating the same problem. The fact that the tropicalization of the algebraic moduli space is again a moduli space in the tropical world is, of course, more than a mere coincidence, but this knowledge is not needed to pose the tropical enumerative problem. So the natural abstraction of the problem of relating an algebraic and tropical enumerative problem consists of
\begin{itemize}
\item A subscheme $M$ of an algebraic torus $T$, and
\item evaluation maps $\ev i: M\rightarrow T_i$ for $1\leq i\leq n$ into algebraic tori $T_i$, which extend to morphisms $\extev i: T\rightarrow T_i$ of algebraic tori.
\end{itemize}
After possibly passing to subtori of the $T_i$ we can assume that the morphisms $\extev i$ are dominant. Note that morphisms of tori are dominant if and only if they are surjective if and only if they are flat.

Tropicalizing the given algebraic objects we obtain
\begin{itemize}
\item A tropical subvariety $\mathfrak M=\Trop(M)$ of a tropical torus $\ttorus=\Trop(T)$, and
\item evaluation maps $\tev i:\mathfrak M\rightarrow \ttorus_i$ for $1\leq i\leq n$ into tropical tori $\ttorus_i=\Trop(T_i)$, which extend to morphisms $\Trop(\extev i)=\textev i:\ttorus\rightarrow \ttorus_i$ of tropical tori.
\end{itemize}
The fact that the $\extev i$ are dominant implies that the corresponding tropical morphisms $\textev i$ are surjective.

In this situation, we want to prove that for an appropriate number $n$ of generic points $p_i\in T_i$ the number of points in $M$ mapped to $p_i$ by $\ev i$ for all $i$ is finite and equal to the number of points, counted with the appropriate multiplicities, in $\mathfrak M$ mapped to $\mathfrak p_i\coloneqq\trop(p_i)$ by $\tev i$ for all $i$. As we want to define the occurring multiplicities intersection-theoretically, the natural claim is that
\begin{equation}
\label{tEqu:Numbers are Equal}
|\ev 1^{-1}\{p_1\}\cap\dots\cap\ev n^{-1}\{p_n\}|=\deg(\tev 1^*[\mathfrak p_1]\cdots \tev n^*[\mathfrak p_n]\cdot \mathfrak M)
\end{equation}
is fulfilled for generic $p_i$. By generic we mean that for every point $\mathfrak p=(\mathfrak p_i)\in\VG(\prod_i\ttorus_i)$ there is a subset of $\trop^{-1}\{\mathfrak p\}$ which is dense in $\prod_i T_i$ such that the equation holds for every point $p=(p_i)$ in this set.

It seems curios that "counting" in algebraic geometry translates to "counting with multiplicities" in tropical geometry. The reason for this is that even though the intersection $\ev 1^{-1}\{p_1\}\cap\dots\cap\ev n^{-1}\{p_n\}$ is finite and reduced for generic $p_i$, we cannot assure that all of its points tropicalize to distinct points of $\ttorus$. But if several points tropicalize to the same point $\mathfrak p$, it is only natural to count $\mathfrak p$ with multiplicity greater $1$. In fact, we will show that for generic points $p_i$ the multiplicity of any point of $\tev 1^*[\mathfrak p_1]\cdots \tev n^*[\mathfrak p_n]\cdot \mathfrak M$ is exactly the number of points in $\ev 1^{-1}\{p_1\}\cap\dots\cap\ev n^{-1}\{p_n\}$ having it as tropicalization.

 To make the analogy between algebraic and tropical enumerative geometry even more visible, let us assume for a moment that $M$ is the moduli space of parametrized rational curves. In the modern treatment of the subject, the  study of the number on the left hand side of Equation \ref{tEqu:Numbers are Equal} usually uses a modular compactification $\overline M$ of $M$ to which the evaluation maps can be extended. After using a Bertini argument to show that the set $\ev 1^{-1}\{p_1\}\cap\dots\cap\ev n^{-1}\{p_n\}$ is finite, reduced, and contained in $M$ for a generic choice of the $p_i$, one can use intersection theory on $\overline M$ to show that its cardinality is independent of the choice of points and equal to
\begin{equation*}
\deg(\ev 1^*[p_1]\cdots \ev n^*[p_n]\cdot \overline M).
\end{equation*}
This is clearly analogous to the expression on the right hand side of Equation \ref{tEqu:Numbers are Equal}. The only difference between the two expressions, except the use of different fonts, reveals one of the big advantages of passing to the tropical world: in tropical geometry we do not need to compactify the moduli space because intersection products and pull-backs are well-defined as tropical cycles. And even if we allow rational equivalence we can still take degrees of cycle classes. This allows us to move the points into special positions without having to deal with the often very difficult task of finding a suitable modular compactification of the moduli space.

To prove the equality in Equation \ref{tEqu:Numbers are Equal} we will need several auxiliary statements. We start by showing that in the simplest case where $M=T$, and we only have one evaluation map, taking inverse images commutes with tropicalization.

\begin{prop}
\label{tProp:Pullback and Tropicalization commutes}
Let $f:T\rightarrow T'$ be a dominant morphism of algebraic tori and $\mathfrak f:\ttorus\rightarrow \ttorus'$ its tropicalization. Furthermore, let $X\subseteq T'$ be a pure-dimensional subscheme of $T'$. Then
\begin{equation*}
\Trop(f^{-1}X)=\mathfrak f^*\Trop(X),
\end{equation*}
that is tropicalization commutes with flat pull-back.
\end{prop}

\begin{proof}
Let $M$ and $M'$ denote the character lattices of $T$ and $T'$, respectively. Since $f$ is dominant, the induced morphism $f^*:M'\rightarrow M$ is injective and we can assume that $M'$ is a subgroup of $M$. Let $\wM$ denote the saturation of $M'$ in $M$. Then the inclusion $M'\hookrightarrow M$ factors through $\wM$, that is $f^*$ is the composite of the inclusions $M'\hookrightarrow \wM$ and $\wM\hookrightarrow M$. Denoting the torus associated to $\wM$  by $\wT=\Spec(K[\wM])$, we see that we can write $f$ as the composite of two dominant morphism $T\rightarrow\wT$ and $\wT\rightarrow T'$ of which the first one splits and the second one is finite. As both the algebraic and the tropical pull-backs are functorial, it suffices to assume that $f$ is either finite or splits.

First suppose that $f$ splits. In this case, we can assume that $T=T'\times\bT$ for some torus $\bT$, and $f$ is the projection onto the first coordinate. Then $f^{-1}X=X\times\bT$ and, writing $\Trop(\bT)=\overline{\ttorus}$, it is immediate that the underlying set of its tropicalizations is equal to $|\Trop(X)|\times \overline{\ttorus}$, which is the underlying set of the pull-back of $\Trop(X)$. As for multiplicities, let $\mathfrak t=(\mathfrak t',\overline{\mathfrak t})\in \ttorus\times\overline{\ttorus}$. After an appropriate extension of scalars we may assume that there is a $t=(t',\overline t)\in T'\times\overline T$ that tropicalizes to $\mathfrak t$. The pull-back of $t'^{-1}X$ along $f$ is equal to $t^{-1}(f^{-1}X)$. Together with the flatness of $f$ this implies $\ini_{\mathfrak t}(f^{-1}X)\cong f_\kappa^{-1}\left(\ini_{\mathfrak t'}(X)\right)$ by \cite[Cor. 4.5]{Gub12}, where $f_\kappa$ is the induced morphism $T_\kappa\rightarrow T'_\kappa$ between the initial degenerations of the tori. Because flat pull-backs are compatible with pulling back subschemes (\cite[Lemma 1.7.1]{F98}), the sum of the multiplicities of the components of $\ini_{\mathfrak t}(f^{-1}X)$ is equal to the sum of the multiplicities of the components of $\ini_{\mathfrak t'}(X)$. Since these sums are, by definition, the multiplicities of the tropicalizations of $f^{-1}X$ and $X$ at $\mathfrak t$ and $\mathfrak t'$, respectively, we get the desired result that $\mathfrak f^*\Trop(X)=\Trop(X)\times \overline{\ttorus}=\Trop(f^{-1}X)$ as tropical cycles.

Now suppose that $f$ is finite. Then its degree is equal to the index $[M:M']$. By \cite[Ex. 1.7.4]{F98} the push-forward of the cycle associated to $f^{-1} X$ is equal to $f_*[f^{-1} X]=f_*(f^*[X])=[M:M']\cdot[X]$. Now we tropicalize this equation. As the tropicalization of a torus subscheme is equal to the tropicalization of its associated cycle \cite[Remark 13.12]{Gub12} and tropicalization commutes with push-forward \cite[Thm. 13.17]{Gub12} we get $\mathfrak f_*\Trop(f^{-1} X)=[M:M']\cdot\Trop(X)$. On the other hand, using tropical intersection theory we obtain the equation
\begin{align*}
\mathfrak f_*\mathfrak f^*\Trop(X)=\mathfrak f_*(\mathfrak f^*\Trop(X)\cdot \ttorus)
&= \Trop(X)\cdot  \mathfrak f_*\ttorus=\\&=\Trop(X)\cdot ([M:M']\cdot\ttorus')=[M:M']\cdot\Trop(X),
\end{align*}
where the second equality uses the projection formula \cite[Thm. 8.3]{FR10}. We see that $\Trop(f^{-1}X)$ and $\mathfrak f^*\left(\Trop(X)\right)$ have the same push-forward under $\mathfrak f$. But since $\mathfrak f$ is an isomorphism of $\mathds R$-vector spaces, the push-forward $\mathfrak f_*:Z_*(\ttorus)\rightarrow Z_*(\ttorus')$ is injective. We conclude that $\Trop(f^{-1}X)=\mathfrak f^*\left(\Trop(X)\right)$, finishing the proof.
\end{proof}

The preceding proposition shows that for every point $p\in T_i$ we have the equality $\Trop(\extev i^{-1}\{p\})=\textev i^*[\trop(p)]$. This is helpful, yet we are actually interested in $\ev i$ rather than in $\extev i$. We can recover $\ev i^{-1}\{p\}$ from $\extev i^{-1}\{p\}$ by intersecting with $M$. In a similar vein, $\tev i^*[\trop(p)]\cdot\mathfrak M$ is equal to $\textev i^*[\trop(p)]\cdot \mathfrak M$. So the equality we wish to have is $\Trop(\extev i^{-1}\{p\}\cap M)=\textev i^*[\trop(p)]\cdot\mathfrak M$. Unfortunately, this cannot be expected to be true in general, because intersection and tropicalization do not always commute. However, as shown in \cite[Thm. 5.3.3]{OP13}, we actually get equality if we translate $\extev i^{-1}\{p\}$ by a general $R$-integral point $t\in T$. The translate $t\cdot\extev i^{-1}\{p\}$ is equal to $\extev i^{-1}\{\extev i(t)p\}$, which is the pull-back of a translate of $p$. For this to be of use for us we need that $\extev i(t)$ is a general $R$-integral point of $T_i$, the problem of course being the generality. A positive answer to this is provided by the following proposition.

\begin{prop}
\label{tProp:Induced morphism of R-integral points is open}
Let $f:T\rightarrow T'$ be a dominant morphism of tori. Then the induced map $f_R:\mathcal T(R) \rightarrow \mathcal T'(R)$ between their respective $R$-integral points is open.
\end{prop}

\begin{proof}
Let $M$ and $M'$ denote the character lattices of $T$ and $T'$, respectively. Then $\TR$ is canonically in bijection with $\Hom(M, R^*)$ and, analogously, $\TpR$ with $\Hom(M', R^*)$. Identifying $T_\kappa(\kappa)$ and $T'_\kappa(\kappa)$ with $\Hom(M,\kappa^*)$ and $\Hom(M',\kappa^*)$, respectively, we get a commutative diagram
\begin{center}
\begin{tikzpicture}[auto]
\matrix[matrix of math nodes,row sep=0.8cm]{
|(HMR)|\Hom(M,R^*) &[0.9cm] |(HM'R)| \Hom(M',R^*) \\
|(HMk)|\Hom(M,\kappa^*) & |(HM'k)|\Hom(M',\kappa^*),\\
};
\begin{scope}[->,font=\footnotesize]
\draw (HMR)  --node{$f_R$} (HM'R);
\draw (HM'R) --node{$r'$} (HM'k);
\draw (HMR)  --node{$r$} (HMk);
\draw (HMk)  --node{$f_\kappa$} (HM'k);
\end{scope}
\end{tikzpicture}
\end{center}
with the vertical morphisms $r$ and $r'$ being the reduction maps. We recall that the topology on $R$-integral points is defined as the initial topology with respect to the reduction map. Hence, to show the openness it is sufficient to prove that $f_\kappa$ is open and $f_R(r^{-1}U)=(r')^{-1}f_\kappa(U)$ for all open sets $U\subseteq \Hom(M,\kappa^*)$. The first of these assertions follows immediately  from $f_\kappa$ being a dominant morphism of tori over an algebraically closed field. For the latter one it suffices to show that the map from $\Hom(M,R^*)$ into the set-theoretic fiber product of $\Hom(M,\kappa^*)$ and $\Hom(M',R^*)$ over $\Hom(M',\kappa^*)$ is surjective. To show this consider the commutative diagram
\begin{center}
\begin{tikzpicture}[auto]
\matrix[matrix of math nodes,row sep=0.8cm, column sep=0.6cm]{
 |(HM1)|\Hom(M,1+\mathfrak{m})			&	|(HMR)|\Hom(M,R^*) 		&	|(HMk)|\Hom(M,\kappa^*) &	|(2se)|0\\
 |(HM'1)|\Hom(M',1+\mathfrak{m})		&	|(HM'R)| \Hom(M',R^*)	&	|(HM'k)|\Hom(M',\kappa^*)	& |(3se)|0\\
 |(1ze)| 0								&	|(2ze)| 0				&	|(3ze)| 0	.			&\\
};
\begin{scope}[->,font=\footnotesize]

\draw (HM1) -- (HM'1);
\draw (HM'1) -- (1ze);

\draw (HMR)  -- (HM'R);
\draw (HM'R) -- (2ze);

\draw (HMk)  -- (HM'k);
\draw (HM'k) -- (3ze);

\draw (HM1) -- (HMR);
\draw (HMR)  -- (HMk);
\draw (HMk) -- (2se);

\draw (HM'1) -- (HM'R);
\draw (HM'R) -- (HM'k);
\draw (HM'k) -- (3se);
\end{scope}
\end{tikzpicture}
\end{center}
It has exact rows because $M$ and $M'$ are free, and the last two columns are exact since $R^*$ and $\kappa^*$ are divisible. If we can show that the first column is exact as well the rest of the proof is just an easy diagram chase. Thus it suffices to show that $1+\mathfrak m$ is divisible. Let $a\in 1+\mathfrak{m}$ and $n\in \mathds N$. Then the polynomial $x^n-a\in R[x]$ factors in $R[x]$ as $(x-b_1)\cdots (x-b_n)$ for appropriate $b_i\in R$, because $K$ is algebraically closed and $R$ is integrally closed	 in $K$.  Reducing modulo $\mathfrak{m}$ yields $x^n-1=(x-b_1)\cdots (x-b_n)$ in $\kappa[x]$. Plugging in  $1$ we get that $b_i\in 1+\mathfrak{m}$ for some $i$. Hence $a$ has an $n$-th root in $1+\mathfrak{m}$, proving the desired divisibility.
\end{proof}

We have seen so far that if $p$ is a point in $T_i$ and $t\in T_i$ is a general element with tropicalization $0$, then $\Trop(\ev i^{-1}\{t\cdot p\})=\tev i^*[\trop(p)]\cdot\mathfrak M$, that is pull-backs of general points under an evaluation map commute with tropicalization. Looking back at Equation \ref{tEqu:Numbers are Equal} this is exactly what we need, only that we need to consider several evaluation maps at once. But with the result of the following lemma, the general situation can be handled analogously.

\begin{lem}
\label{tLem:Generic Intersection and Tropicalization commute}
Let $X_1,\dots, X_n$ be subschemes of the torus $T$. Then for general $R$-integral points $(t_2,\dots, t_n)$ of $T^{n-1}$ we have
\begin{equation*}
\Trop\left(X_1\cap t_2X_2\cap\dots\cap t_nX_n\right)=\Trop(X_1)\cdots\Trop(X_n).
\end{equation*}
\end{lem}

\begin{proof}
For $n=2$ this is just the statement of \cite[Thm. 5.3.3]{OP13}. To prove the general case let $\Delta:T\rightarrow T^n$ be the diagonal embedding, which makes $T$ a subscheme of $T^n$. It corresponds to the diagonal embedding $\mathfrak D:\ttorus\rightarrow \ttorus^n$ on the tropical side. By the $n=2$ case, for every general $R$-integral point $t=(t_1,\dots, t_n)\in T^n$ we have
\begin{equation*}
\Trop(\Delta\cap t(X_1\times\dots\times X_n))=\Trop(\Delta)\cdot\Trop\left(X_1\times\dots\times X_n\right).
\end{equation*}
Since $\Delta\cap t(X_1\times\dots\times X_n)$ is the push-forward of $t_1 X_1\cap\dots\cap t_n X_n$, and tropicalization commutes with push-forwards, the term on the left hand side is equal to $\mathfrak D_*(\Trop(t_1 X_1\cap \dots\cap t_n X_n))$. On the other hand, by  \cite[Prop. 5.2.2]{OP13} the term on the right is equal to $\mathfrak D_*(\Trop(X_1)\cdots\Trop(X_n))$. Because $\mathfrak D_*$ is one-to-one, it follows that $\Trop(t_1 X_1\cap \dots\cap t_n X_n)=\Trop(X_1)\cdots\Trop(X_n)$. After multiplying by $t_1^{-1}$ we can assume that $t_1=1$, and Proposition \ref{tProp:Induced morphism of R-integral points is open} ensures that the resulting $R$-rational point $(t_2,\dots,t_n)\in T^{n-1}$ still is generic.
\end{proof}

\begin{thm}
\label{tThm:Tropicalization commutes with pullback of generic translate}
Using the notation introduced at the beginning of this section, let $P_i\subseteq T_i$ be a pure-dimensional closed subscheme of $T_i$ with tropicalization $\Trop(P_i)=\mathfrak P_i$. Then for generic $R$-integral points $(t_1,\dots, t_k)\in\prod_i T_i$ we have
\begin{equation*}
\label{tEqu:Tropicalization and generic preimage commute}
\Trop(\ev 1^{-1}(t_1P_1)\cap\dots\cap\ev n^{-1}(t_n P_n))=\ev 1^*(\mathfrak P_1)\cdots \ev n^*(\mathfrak P_n)\cdot\mathfrak M.
\end{equation*}
In particular, if $\mathfrak p=(\mathfrak p_1,\dots,\mathfrak p_n)\in\VG(\prod_i\ttorus_i)$, then for generic  points $p=(p_1,\dots,p_n)$ of $\trop^{-1}\{\mathfrak p\}$ we have
\begin{equation*}
\Trop\left(\ev 1^{-1}\{p_1\}\cap\dots\cap\ev n^{-1}\{p_n\}\right)=\ev 1^*[\mathfrak p_1]\cdots \ev n^*[\mathfrak p_n]\cdot\mathfrak M.
\end{equation*}
\end{thm}

\begin{proof}
Proposition \ref{tProp:Pullback and Tropicalization commutes} and Lemma \ref{tLem:Generic Intersection and Tropicalization commute} tell us that for a generic $R$-integral point $(s_1,\dots,s_n)\in T^n$ we have
\begin{equation}
\label{tEqu:Tropicalization and generic preimage commute. Aux1}
\Trop\left(s_1 \cdot\extev 1^{-1}(P_1)\cap\dots\cap s_n\cdot\extev n^{-1}(P_n)\cap M\right)
=\textev 1^*(\mathfrak P_1)\cdots\textev n^*(\mathfrak P_n)\cdot\mathfrak M.
\end{equation}
Let $t=(t_1,\dots,t_n)=(\extev 1(s_1),\dots,\extev n(s_n))\in\prod_i T_i$. Because all evaluation maps are dominant we can apply Proposition \ref{tProp:Induced morphism of R-integral points is open} and see that $t$ is again generic. Furthermore, the left-hand side of Equation \ref{tEqu:Tropicalization and generic preimage commute. Aux1} is equal to
\begin{equation*}
\Trop\left(\extev 1^{-1}(t_1P_1)\cap\dots\cap \extev n^{-1}(t_nP_n)\cap M\right)
=\Trop\left(\ev 1^{-1}(t_1P_1)\cap\dots\cap\ev n^{-1}(t_n P_n)\right).
\end{equation*}
As the right-hand side of Equation \ref{tEqu:Tropicalization and generic preimage commute. Aux1} is equal to $\tev 1^*(\mathfrak P_1)\cdots\tev n^*(\mathfrak P_n)\cdot\mathfrak M$ this proves the main statement of the theorem.

For the "in particular" statement let $\mathfrak p=(\mathfrak p_1,\dots,\mathfrak p_n)\in\VG(\prod_i\ttorus_i)$, and choose an arbitrary $s=(s_1,\dots,s_n)\in\trop^{-1}\{\mathfrak p\}$. By what we already proved, we have
\begin{equation*}
\Trop\left(\ev 1^{-1}\{t_1 s_1\}\cap\dots\cap\ev n^{-1}\{t_n s_n\}\right)=\ev 1^*[\mathfrak p_1]\cdots \ev n^*[\mathfrak p_n]\cdot\mathfrak M.
\end{equation*}
for generic $t=(t_1,\dots, t_n)\in\trop^{-1}\{0\}$. Since $\trop^{-1}\{\mathfrak p\}$ is a $\trop^{-1}\{0\}$-torsor, the elements of the form $ts$ for generic $R$-rational points $t$ are generic in $\trop^{-1}\{\mathfrak p\}$.
\end{proof}

As a corollary to Theorem \ref{tThm:Tropicalization commutes with pullback of generic translate} we obtain the result that Equation \ref{tEqu:Numbers are Equal} is indeed generally true.

\begin{cor}
\label{tCor:Tropical and Algebraic Numbers are Equal}
With the notation as in the beginning of this section, assume that $M$ is integral, and $\dim(M)=\sum_i \dim(T_i)$. Then for every $\mathfrak p=(\mathfrak p_i)\in\VG(\prod_i \ttorus_i)$ there exists $p=(p_i)\in\prod_i T_i$ with $\trop(p)=\mathfrak p$ such that
\begin{equation*}
|\ev 1^{-1}\{p_1\}\cap\dots\cap\ev n^{-1}\{p_n\}|=\deg(\tev 1^*[\mathfrak p_1]\cdots \tev n^*[\mathfrak p_n]\cdot \mathfrak M),
\end{equation*}
and such that the multiplicity of every point $\mathfrak q\in \left|\tev 1^*[\mathfrak p_1]\cdots \tev n^*[\mathfrak p_n]\cdot \mathfrak M\right|$  is equal to the number of points in $\ev 1^{-1}\{p_1\}\cap\dots\cap\ev n^{-1}\{p_n\}$ tropicalizing to it. Furthermore, the set of such $p$ is dense in $\prod_i T_i$. More precisely, $p$ can be any point in the intersection of a nonempty open subset of $\trop^{-1}\{\mathfrak p\}$ and a nonempty open subset of $\prod_i T_i$.
\end{cor}

\begin{proof}
Let $\mathfrak p=(\mathfrak p_i)\in\prod_i \ttorus_i$. Then by Theorem \ref{tThm:Tropicalization commutes with pullback of generic translate} there is a nonempty open subset $W\subseteq \trop^{-1}\{\mathfrak q\}$ such that
\begin{equation*}
\Trop(\ev 1^{-1}\{p_1\}\cap\dots\cap\ev n^{-1}\{p_n\})=\ev 1^*[\mathfrak p_1]\cdots \ev n^*[\mathfrak p_n]\cdot\mathfrak M
\end{equation*}
for every $(p_1,\dots,p_n)\in W$. Using a Bertini-type argument, we find a dense open subset $U\subseteq\prod_i T_i$ such that $\ev 1^{-1}\{p_1\}\cap\dots\cap\ev n^{-1}\{p_n\}$ is a reduced finite subscheme of $M$. By \cite[Thm. 4.2.5]{OP13}, every nonempty open subset of a fiber of the tropicalization map $\trop:\prod T_i\rightarrow \prod\ttorus_i $ is dense in $\prod T_i$. Hence $W\cap U$ is dense in $\prod T_i$, as well. The corollary follows, since the tropicalization of a reduced finite subscheme of a torus is nothing but the union of the tropicalizations of its points where each point has as multiplicity the number of points tropicalizing to it.
\end{proof}

config: arxiv


TITLE: Isotropy and Noise
QUESTION [0 upvotes]: If you have a field which value is just Gaussian noise plus a constant do you call it isotropic?

there is no preferred direction
however it is not "the same" in all directions if "the same" means "constant"

The question is about a definition of a word, thus obviously conflicting answers can arise. However what definition do you use or have seen used: "no preferred direction" or "constant wrt translation"?

REPLY [1 votes]: The way I would approach this is to consider blackbody radiation, where a spherical blackbody radiator is isotropic, e.g. it emits radiation equally in all directions.  If we were to model the noise introduced by such a blackbody, it would be additive Gaussian white noise.  In this example, it is called white noise because it has a flat power spectrum density, and it is Gaussian because the noise has Gaussian amplitude distribution.  It is additive because it can be added linearly to the desired signal.
In this case isotropy is a characteristic of the emitter.  If I would interpret isotropy in terms of noise, I would understand it as being the same in all directions with respect to the receiver, e.g. regardless of direction, the received signal would have identical noise functions that were added to the signal.  If the noise had some constant associated with it, as long is the constant was additive and the same in all directions with respect to the receiver, I would consider that isotropic as well.


TITLE: What is generalized law of mean and what is a book that introduce that?
QUESTION [0 upvotes]: What is generalized and extension law of mean/mean value theorem and what is a book that introduce that and the topics below?
I want to learn more about that before i taking that course.
That course also introduce  limit, continuity, derivative and differential of a function of one variable. Other topics include real numbers and the axiom of continuity, convergence of a sequence of real numbers; elements of point set topology; and extensions and generalizations of the law of the mean.
I had no idea what textbook of that course called advanced calculus 1 will be using...
I already try out the college bookstore website but the the course isn't there.
It can't be Larson or Gilbert text since it is considerably more rigorous and advanced than calculus 3
I guess the course textbook had all these terminology in the book index
Website: http://www.baruch.cuny.edu/math/course_syllabi/4010.html

REPLY [2 votes]: Wow, Baruch. My undergraduate alma mater was Queens College of CUNY,so I feel obligated to answer in a family-sorta way.......lol
A great-and now cheap-text on single variable advanced calculus by a master teacher at MIT is Arthur Mattuck's Introduction To Analysis.  I was absolutely floored to learn this incredible book was reissued in a fantastically cheap paperback last year after becoming exceedingly scarce-and correspondingly expensive-in it’s original hardcover edition. Mattuck’s reissuing of the book through Createspace in a 13 dollar (!) paperback as the standard text for the 18.100A course at MIT, which he has taught there for many years, demonstrates this legendary teacher’s commitment to assisting students learn analysis who do not have the strong background and/or talent of students who can directly enter an abstract analysis course based on metric spaces. The author’s “mission statement” of the text in the Preface is quite informative and should be read by all students and teachers of mathematics. Basically, the need for such a text became clear from Mattuck’s many years of teaching analysis to students who struggled in the typical metric spaces-based analysis course. (And these were MIT students, so the usual snarky response of mathematics honors students that they just weren’t bright enough to learn analysis becomes manifestly absurd in this case…..)
For beginners, analysis should look like calculus, only much more careful. The author takes great pains to give proofs in great detail, all done by specific calculational methods at first, which slowly give way to more general arguments as theorems are established throughout the book. The Completeness property is given in terms of Cauchy convergence. The author writes beautifully and clearly, with many deep insights that are usually omitted as obvious in not only analysis courses, but calculus courses. For example, he goes into some detail on why subtracting inequalities is illegal.  He also can be wryly amusing at times. There are tons of excellent problems all with complete solutions, which will make the book incredibly useful for self-study. Mattuck has written an outstanding textbook that all students of mathematics regardless of level can learn from. It’s  an absolute gift that the book is now available so cheaply to beginning students of analysis and there’s no reason not to have a copy. I think you'll find it a perfect fit for your needs and budget-hopefully,your professor decides to use it.
The generalized law of the mean and how it it's related to the ordinary mean value theorem is discussed at some length in Mattuck and other books. Let's review with the regular MVT. Geometrically,what it means roughly is that given a planar arc between two endpoints, there is at least one point at which the tangent to the arc is parallel to the secant through its endpoints, like so:

Now the generalized or extended MVT,which is called sometimes the Cauchy MVT since it was discovered by Cauchy. It states that if there exists functions f and g both continuous on the closed interval [a,b], and differentiable on the open interval (a, b), then there exists some c ∈ (a,b), such that (f(b) - f(a)) (g'(c)) =  (g(b) - g(a)) (f'(c)). This result is quite useful in calculus, particularly in proving results with indeterminate forms, such as L'Hopital's rule. Geometrically, what the extended MTV says is that there is some tangent to the graph of the curve $L:[a,b] \rightarrow R^{2}$ where for every $t\in[a,b]$ $t\rightarrow (f(g),g(t))$ which is parallel to the line defined by the points (f(a),g(a)) and (f(b),g(b)) like so:

However Cauchy's theorem does not claim the existence of such a tangent in all cases where (f(a),g(a)) and (f(b),g(b)) are distinct points, since it might be satisfied only for some value c with f′(c) = g′(c) = 0.
Full proofs of these results are given in any good elementary real analysis or advanced calculus book.
Hope you found this post helpful. Good luck!


text:
\begin{document}
\maketitle

\centerline{Shengxin Zhu}
\medskip
{\footnotesize

\centerline{Laboratory for Intelligent Computing and Financial Technology}
 \centerline{Department of Mathematics, Xi'an Jiaotong-Liverpool University }

   \centerline{Suzhou, 215123, P.R.China}
}

\bigskip

 \centerline{(Communicated by the associate editor name)}

\begin{abstract}
A proper choice of parameters of the Jacobi modular identity (Jacobi Imaginary transformation)
implies that the summation of Gaussian shifts on infinity periodic grids can be represented as
the Jacobi's third Theta function. As such, connection between summation of Gaussian shifts and
the solution to a Schr\"{o}dinger equation is explicitly shown. A concise and controllable upper
bound of the saturation error for approximating constant functions with summation of Gaussian shifts
can be immediately obtained in terms of the underlying shape parameter of the Gaussian. This sheds
light on how to choose a shape parameter and provides further understanding on using Gaussians with increasingly flatness.

\end{abstract}
\section{Background}
Gaussian radial basis functions(RBFs) are widely used in machine learning and in solving partial differential equations\cite{B03,F07,W05,ZW15}. It has been for long time noticed that Gaussian interpolation does not provide uniform convergence in the \emph{stationary} interpolation setting, i.e. to choose supports of RBFs proportional to the \emph{fill distance}.  Powell took such a perspective and shew that Gaussian fails badly\cite{P90}\cite[p.185]{W05}. Ron proved that interpolation with shift of Gaussian in the \emph{nonstationary} setting enjoys spectral converge \cite{R92}. Maz\'ya and Schmidt proved that \emph{approximate approximation} with Gaussian converges fast to certain threshold and then remains constant afterwards  \cite{MS96,MS07}, this saturation error can be controlled to be negligible by adjusting the \emph{shape parameter} ($\frac{1}{d}$ in the paper). In fact this provides a theoretical basis for using Gaussian with flatness limit. This will be clear in this short paper without involved mathematics as in \cite{MS96}\cite{SZ03}\cite{Wu93}. It is clear now that Gaussian is a positive definite kernel whose associate native space is `very small', and only functions belong to the underlying native space can converge very fast \cite{SW02}. For functions do not belong to native space, saturation error exists. Buhmann has pointed out that estimate for \emph{saturation order} remained to be open problems \cite[p.236]{B03}. In particularly, Buhmann applied
the cardinal function approach to derive the local polynomial reproduction properties, he proved that it is impossible for the so called \emph{pseudoadmissible} (one can ignore the definition)
basis functions to recover a constant and Gaussian is a pseudoadmissible function \cite[Thm 23]{B90}. This implies that Gaussian can not reproduce a constant function. Boyd and Wang recently studied that saturation error for Gaussian RBFs \cite{Bo10B,BW09} and showed that RBF interpolant/approximant to the constant function, 1, on infinite periodic grids must be of the following form \cite{BW09}
\begin{linenomath}
$$
1 \approx \lambda \sum_{-\infty}^{\infty} \phi(\frac{\alpha}{h}(x-mh)),
$$
\end{linenomath}
i.e. the coefficients of the basis functions must be equal on infinity periodic grids. And recently Ye designed an optimization approach to choose the shape parameters \cite{Ye16}.

Compared with Buhmann, Boyd, Ye and Wang's results, here provides a precise formula as a direct consequence of the \emph{modular identity} \cite[eq.2.3]{C03}(see also \cite{CT05}\cite{R07}), Lemma 1 bellow) or \emph{Jacobi's imaginary transformation}\cite[p.475]{WW4}(see eq.\eqref{eq:lemma} below). A simple and controllable upper bound for the saturation error in terms of the \emph{shape parameters} is immediately obtained by using a proper form of the Jacobi Theta function, without any other sophisticated mathematics. These concise results precisely reveal why the ``flatter'' Gaussian radial basis functions result in better approximation quality and how the shape parameter control the saturation error.

What we should mention is that the close relationship between summation of Gaussian shifts and the Theta function of Jacobi type has been noticed for a long time. In \cite{B94}, when Baxter estimated the lower and upper bounds of Toeplitz matrices related to Gaussian radial basis functions (Lemma 2.7 in \cite{B94}), he in fact leveraged the Poisson summation formula and the Theta function of Jacobi type to derive a sharp lower and upper bound of the quadratic forms in the following form
\begin{linenomath}
$$
      m\sum_{ j \in \mathbb{Z}^d} a_j^2     \leq \sum_{j, k \in \mathbb{Z}^d} a_j a_k f(j-k) \leq M \sum_{j \in \mathbb{Z}^d} a_j^2
$$
\end{linenomath}
where $f(x)=e^{ -\lambda \|x \|^2}$,
\begin{linenomath}
$$m=(\frac{\pi }{\lambda})^{d/2}  \sum_{k \in \mathbb{Z}^d} e^{ - \frac{\| \pi 1 +2 \pi k \|^2 }{4 \lambda} }  \text{ and } M= (\frac{\pi}{\lambda})^{d/2} \sum_{k\in \mathbb{Z}^d} e^{- \frac{  \|\pi k\|^2}{\lambda}}.$$
\end{linenomath}
Such a technique was further developed to derive the explicit formula for the condition number of certain bi-infinite Toeplitz matrix in the form of a multiple of the Jacobian elliptic function $dn$ \cite[Thm 2.7]{BS96}\cite{RS99}. The Jacobi Theta function was also involved in analysis of the approximate approximation with Gaussian in\cite{MS96}, and recently in orthogonalization for systems consisting of Gaussian shifts \cite{ZKMS11}. These results are technically elegant. However, it seems that such a connection between Gaussian and the Jacobi Theta function has not been mentioned in popular books on RBF \cite{B03,F07,FM15,W05,SZ03} and other many publications as far as we know.  The novelty here lies on that concise constructive results are obtained only by choosing proper parameters of a modular identity of the Jacobi Theta function. This modular identity or imaginary transformation is often used to obtain definite numerical results in problems involving \emph{elliptic functions}, \emph{elliptic curves}, and \emph{modular groups} \cite{H04}. No other sophisticated harmonic analysis is used. Limitation of this method is that such a formulae is concise for one dimensional cases, for higher dimensional cases, involved mathematics as in \cite{MS96} are required.

Such a concise formulae provides an alternative perspective to using flat radial basis functions, which was largely popularized due to Driscoll and Fornberg's investigation \cite{DF02}.

\section{Main Results}

\begin{theorem}
\label{thm:1}
Let $\vartheta_3(z,\tau)$ be the third Theta function defined as
\begin{linenomath}
\begin{equation}
\vartheta_3(z,\tau) =\sum_{ n\in \mathbb{Z}} e^{2  i n z + \pi i n^2 \tau} \label{eq:def}
\end{equation}
\end{linenomath}
on $\mathbb{C} \times \mathbb{H}$, where $\mathbb{H}\subset \mathbb{C}$ is the upper half complex plane. i.e. $Im (\tau) >0$.
If $d$ is positive constant, then
\begin{linenomath}
\begin{equation}
 \frac{1}{\sqrt{\pi d}}\sum_{n=-\infty}^{\infty} e^{-\frac{(z-n\pi)^2}{d\pi^2}} = \vartheta_3(z, i \pi d). \label{eq:result}
\end{equation}
\end{linenomath}
or equivalently
\begin{linenomath}
\begin{equation}
 \frac{1}{\sqrt{\pi d}}\sum_{n=-\infty}^{\infty} e^{-\frac{(z-n)^2}{d}} = \vartheta_3(\pi z, i \pi d). \label{eq:result2}
\end{equation}
\end{linenomath}
\end{theorem}

As a direct consequence of the result, the saturation error for approximating the constant function 1 on infinity periodic grids can be controlled to be negligible by adjusting the \emph{shape parameter} $d$.
\begin{theorem}
\label{thm:2}
If $d$ is positive constant, then
\begin{linenomath}
\begin{equation}
\left| \frac{1}{\sqrt{\pi d}}\sum_{n=-\infty}^{\infty} e^{-\frac{(x-n)^2}{d}} -1 \right| = \left| \vartheta_3(\pi z, i \pi d)-1 \right| < \mathrm{csch(\pi^2 d)}

\label{eq:th2}
\end{equation}
\end{linenomath}
\end{theorem}

\begin{figure}[ht]
\begin{minipage}[t]{0.45\linewidth}
\centering
\includegraphics[width=0.95\linewidth]{GaussianSummation_04.eps}
\caption{$ \log_{10} \csc h (\pi^2 d)$}
\end{minipage}
\begin{minipage}[t]{0.45\linewidth}
\centering
\includegraphics[width=0.95\linewidth]{GaussianSummation_03.eps}
\caption{ $e^{-\frac{x^2}{d}}$ }
\end{minipage}
\label{figu}
\end{figure}

\begin{figure}[ht]
\begin{minipage}[t]{0.45\linewidth}
\centering
\includegraphics[width=0.9\linewidth]{GaussianSummation_01.eps}
\end{minipage}
\begin{minipage}[t]{0.45\linewidth}
\centering
\includegraphics[width=0.9\linewidth]{GaussianSummation_02.eps}
\end{minipage}
\caption{ error ({\color{blue}-}) and control line ({\color{red}-.-})}
\end{figure}
To demonstrate Theorem \ref{lem:2}, we plot the $\log_{10} \csc(\pi^2 d)$ against $d$ in FIGURE 1. And we use the basis functions in FIGURE 2 to approximate the constant function 1, and plot the error function
$$
error(x)= \frac{1}{\sqrt{\pi d}} \sum_{n=-1000}^{1000} e^{-\frac{(x-n)^2}{d}} -1
$$
and the control terms $ \pm \csc h(\pi^2 d)$ in FIGURE 3 (for $d=4$, the control terms are $\pm \epsilon$, the machine precision). This is a vivid example which can mathematically show that \emph{flatter} Gaussian provides better approximation.

\section{Proof the main results}

To make this communication self-contained, we first introduce some relevant results to the Theta function defined in \eqref{eq:def}, which is also called the third Jacobi Theta function and denoted as $\vartheta_3(z,\tau)$. It is obvious that $\vartheta_3(z,\tau)= \vartheta_3(-z,\tau)$ is an even function with respect to $z$ and can be written as the following equivalent form
\begin{equation}
 \vartheta_3(z,\tau) = 1+ 2\sum_{n=1}^{\infty} q^{n^2} \cos 2 \pi n  z ,
\label{lem:1}
\end{equation}
where $q= e^{ i \pi \tau}$.  This representation will be used to derive the result in Theorem \ref{thm:2}. The following \emph{modular identity} or \emph{Jacobi's imaginary transformation} plays  an essential role in deriving our main results.

\begin{lemma}
\label{lem:2}
If $\vartheta(z,\tau)$ is defined in \eqref{eq:def}, then
\begin{linenomath}
\begin{equation}
\vartheta_3(z, \frac{-1}{\tau}) =\frac{1}{\sqrt{ -i \tau}} e^{\frac{z^2}{i \pi \tau}} \vartheta_3(\frac{z}{\tau}, -\frac{1}{\tau}). \label{eq:lemma}
\end{equation}
\end{linenomath}
\end{lemma}

\begin{proof} This is the exactly formula in \cite[p.475]{WW4} and \cite[eq.4.1]{Bel61}. One can also refer to
\cite[eq.2.3]{C03}(also \cite{CT05}\cite{R07}) for a brief proof of an equivalent identity.
\end{proof}

\section*{Proof of Theorem \ref{thm:1}}

\begin{proof}

By applying the modular identity to $\vartheta_3(z, i \pi d)$, we have
 \begin{linenomath}
 \begin{align*}
  \vartheta_3(z, i\pi d) & = \frac{1}{\sqrt{\pi d}}  e^{ -\frac{z^2}{\pi^2 d} }
  \vartheta_3(\frac{z}{i\pi d},-\frac{1}{i \pi d} ) \\
 & = \frac{1}{ \sqrt{\pi d}} e^{ -\frac{z^2}{\pi^2 d} }
   \sum_{ n\in \mathbb{Z}} e^{2 n i \frac{z}{i \pi d} +  i \pi n^2 (-\frac{1}{i\pi d} ) }
    \\
   &=\frac{1}{ \sqrt{\pi d}}\sum_{ n\in \mathbb{Z}}e^{- \frac{(z -\pi n)^2}{\pi^2 d}} .
 \end{align*}
 \end{linenomath}
Similarly we can obtain \eqref{eq:result2}.
\end{proof}

Equivalent results in Theorem \ref{thm:1} have appeared elsewhere.
\begin{remark}
In the classical book \cite[p.476]{WW4}, the identity is in the form
\begin{equation}
\sum_{n \in \mathbb{Z}} e^{2 n i z + n^2 \pi i \tau} = \frac{1}{\sqrt{i \tau}} \sum_{-\infty}^{\infty} e^{\frac{(z-n\pi)^2}{\pi i \tau}}.
\label{eq:477}
\end{equation}
Set $\tau= i \pi d$ in \eqref{eq:477}, we can obtain \eqref{eq:result}.
\end{remark}
\begin{remark}
In \cite[eq.19.2]{Bel61}, the formula reads as
$$
1+2 \sum_{m=1}^{\infty} e^{-m^{2} \pi^{2} t} \cos 2 m \pi x=\frac{1}{\sqrt{\pi t}} \sum_{n=-\infty}^{\infty} e^{-(n+x)^{2} / t}.
$$
Let $t=d$, and change $n$ to $-n$ in the right hand side we can obtain \eqref{eq:result2}.
\end{remark}

\section*{Proof of Theorem \ref{thm:2}}
\begin{proof}
According to the equivalent formulation of $\vartheta_3$ in  \eqref{lem:1}, let $q= e^{i \pi \tau} = e^{-\pi^2 d}$ we have
\begin{linenomath}
\begin{align*}
& \left| \frac{1}{\sqrt{\pi d}}\sum_{n=-\infty}^{\infty} e^{-\frac{(x-n \pi)^2}{d\pi^2}} -1 \right|= \left|\vartheta_3(z, i \pi d) -1\right| =2 \left| \sum_{n=1}^{\infty} q^{n^2} \cos 2 \pi n z  \right|\\
& =2\left| \sum_{n=1}^\infty e^{-\pi^2 d n^2}  \cos  2 \pi n z \right| \leq 2\sum_{n=1}^{\infty} \left|e^{-\pi^2 d n^2}\right| \left| \cos 2 \pi n z  \right| \\
& \leq 2\sum_{n=1}^{\infty} e^{-\pi^2 d n^2}= \vartheta_3(0,i\pi d)-1 \\
& <2\sum_{n=1}^{\infty} e^{-\pi^2 d(2n-1)} = 2 e^{\pi^2 d}  \sum_{n=1}^{\infty} (e^{-2\pi^2 d})^n=e^{\pi^2 d} \frac{ 2e^{-2 \pi^2 d}}{ 1- e^{-2 \pi^2 d}}\\
&= \frac{2 e^{-\pi^2 d}}{1 - e^{-2 \pi^2 d}} = \frac{2}{ e^{\pi^2 d}- e^{-\pi^2 d}}=csch(\pi^2 d).
\end{align*}
\end{linenomath}
For the last inequality, notice that $n^2 \geq 2n -1 $.

\end{proof}

\section{Discussion}

Because $Im(\tau)>0$, then $|e^{\pi i n^2 \tau}|<1$, the infinite series in \eqref{eq:def} is absolutely convergent to $\theta(z,\tau)$, then the derivative of the summation is equal to the summation of the derivatives\cite[p.470]{WW4}:
\begin{linenomath}
\begin{align*}
\frac{d^2 \vartheta_3(z,\tau)}{dz^2}  & = \sum_{n\in \mathbb{Z}} \frac{d^2}{dz^2} e^{2 i n z + \pi i n^2 \tau} = -4 n^2 \sum_{n\in \mathbb{Z}} e^{2 i nz +\pi i n^2 \tau} \\
 & = -\frac{4}{\pi i} \sum_{n\in \mathbb{Z}} \pi i \pi n^2 e^{2 i nz +\pi i n^2 \tau}  = -\frac{4}{\pi i}\frac{d \vartheta_3(z,\tau)}{d \tau}.
\end{align*}
\end{linenomath}
Therefore, both the summation of the Gaussian shifts and the Theta function satisfy the following Schr\"{o}dinger equation. Such a connection may shed new light on investigating Gaussian RBFs.

The present results only works for the one dimensional case on infinite periodic grids. For higher dimensional cases, involved mathematics should be applied as in \cite{MS96}\cite{FHW12}. The results may be related to the quasi-interpolation as said by the author \cite{Gao12}\cite{GXWZ20} and related to the learnability \cite{Zhou07}. Finally, we would like to point out that recent research has connected a class of compact radial basis functions with the hypergeometric functions \cite{CH14,S11,H12}. It seems that there are various research opportunities in this direction.

\providecommand{\href}[2]{#2}
\providecommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{arXiv:#1}}
\providecommand{\url}[1]{\texttt{#1}}
\providecommand{\urlprefix}{URL }