#

Qinian Jin  Mathematical Sciences Institute, Australian National University,
Canberra, ACT 2601, Australia<EMAIL_ADDRESS>
# On growth error bound and Kurdyka-Łojasiewicz condition

Qinian Jin  Mathematical Sciences Institute, Australian National University,
Canberra, ACT 2601, Australia<EMAIL_ADDRESS>
###### Abstract.

In this paper, by using the proximal point algorithm, we provide a more
accessible and elementary proof of the fact that Kurdyka-Łojasiewicz
conditions imply the growth error bounds for convex functions which has been
established before via a subgradient flow. We further extend the result for
nonconvex functions. Finally we show that every definable function in an
o-minimal structure must satisfy a growth error bound.

###### Key words and phrases:

Kurdyka-Łojasiewicz condition, growth error bound, o-minimal structure,
definable functions

###### 2010 Mathematics Subject Classification:

90C31, 90C30, 90C25

##  1\. Introduction

Many algorithms have been developed to solve minimization problems of the form

$\displaystyle\min_{x\in X}f(x),$ (1.1)

where $X$ is a Hilbert space and $f:X\to(-\infty,\infty]$ is a proper lower
semi-continuous function. Various favorable conditions have been proposed on
$f$ to guarantee desired convergence rates for many specific algorithms. When
$f$ is a proper convex function, the following error bound conditions have
been introduced at a point $\bar{x}\in S:=\arg\min_{x\in X}f(x)$ to derive
linear convergence for a number of first order optimization methods ([4, 5,
14, 23, 24]):

  1. $\bullet$

Quadratic growth condition: there exist $r>0$ and $\gamma>0$ such that

$d^{2}(x,S)\leq\gamma(f(x)-f_{*}),\qquad\forall x\in B_{r}(\bar{x}).$

  2. $\bullet$

Kurdyka-Łojasiewicz (KL) condition with exponent $1/2$: there exist $r>0$ and
$\gamma>0$ such that

$f(x)-f_{*}\leq\gamma d^{2}(0,\partial f(x)),\qquad\forall x\in
B_{r}(\bar{x}).$

  3. $\bullet$

Subdifferential error bound condition: there exist constants $r>0$ and
$\gamma>0$ such that

$d(x,S)\leq\gamma d(0,\partial f(x)),\qquad\forall x\in B_{r}(\bar{x}).$

  4. $\bullet$

Proximal error bound condition: there exist $r>0$ and $\gamma>0$ such that

$d(x,S)\leq\gamma\|x-\mbox{prox}_{f}(x)\|,\qquad\forall x\in B_{r}(\bar{x}).$

where, $f_{*}:=f(\bar{x})$, $\partial f$ and $\mbox{prox}_{f}$ denote the
convex subdifferential and the proximal mapping of $f$ respectively, and
$d(x,S)$ denotes the distance from $x$ to $S$, i.e. $d(x,S):=\inf_{z\in
S}\|x-z\|.$ Note that the subdifferential error bound condition is the metric
subregularity of $\partial f$ at the point $(\bar{x},0)$ in the graph of
$\partial f$ ([12, 15]). When $f$ is continuously differetiable, the KL
condition with exponent $1/2$ is also called the Polyak-Łojasiewicz condition
([21, 22, 25]).

These error bound conditions constitute important mathematical concepts with
diverse applications in optimization, analysis, and variational inequalities.
They play a crucial role in establishing convergence properties of algorithms,
characterizing critical points, and understanding the behavior of functions in
various settings. Thus, the exploration of relationships among these error
bound conditions becomes a compelling endeavor, which has witnessed recent
advancements.

Notably, the equivalence between the subdifferential error bound condition and
the proximal error bound condition has been established in [14]. This
equivalence is demonstrated through the utilization of properties of proximal
mapping, resulting in a relatively straightforward argument. Based on
Ekeland’s variational principle, the equivalence between the quadratic growth
condition and the subdifferential error bound condition has been proved in [2,
3]. Furthermore, the equivalence between the quadratic growth condition and
the KL condition with exponent $1/2$ has been established in [9] as a special
case of a more general result. Actually, it has been proved in [9] that if a
proper, lower semi-continuous, convex function $f:X\to(-\infty,\infty]$
satisfies at a point $\bar{x}\in S$ the growth error bound

$\displaystyle d(x,S)\leq\varphi(f(x)-f_{*}),\quad\forall x\in
B_{r}(\bar{x})\cap\\{f<f(\bar{x})+\eta\\}$ (1.2)

for some $r>0$, $\eta\in(0,\infty]$ and a desingularizing function
$\varphi\in{\mathcal{K}}(0,\eta)$, where

${\mathcal{K}}(0,\eta):=\\{\varphi\in C[0,\eta)\cap
C^{1}(0,1):\varphi(0)=0,\varphi\mbox{ is concave},\varphi^{\prime}(s)>0\\},$

and if there exists $c>0$ such that

$\displaystyle s\varphi^{\prime}(s)\geq c\varphi(s)\quad\mbox{for all
}s\in(0,\eta),$ (1.3)

then $f$ must satisfy at $\bar{x}$ the KL condition

$\displaystyle\varphi^{\prime}(f(x)-f_{*})d(0,\partial f(x))\geq
1,\quad\forall x\in B_{r}(\bar{x})\cap\\{f(\bar{x})<f<f(\bar{x})+\eta\\}$
(1.4)

and, moreover, the converse holds without requiring (1.3). The proof that
(1.2) implies (1.4) is somewhat straightforward. However, establishing the
reverse implication is highly nontrivial. The proof provided in [9] is based
on the subgradient flow

$\displaystyle\left\\{\begin{array}[]{lll}\dot{x}(t)\in-\partial
f(x(t))\quad\mbox{for almost all }t\in(0,\infty),\\\ x(0)=x\end{array}\right.$

generated by $\partial f$ and hence the argument relies heavily on the theory
of differential inclusion which involves a lot of machinery.

In this note, by using the proximal point algorithm we will provide an
alternative argument to show that the KL condition (1.4) implies the growth
error bound (1.2) for proper lower semi-continuous convex functions, offering
a more accessible and elementary proof. Furthermore, we will extend our
argument to demonstrate that, for proper lower semi-continuos nonconvex
functions, (1.4) still implies (1.2) on a possibly smaller set. As a direct
consequence, we may use the result in [8], which states that every definable
function in an o-minimal structure must satisfy the KL condition, to conclude
that every definable function satisfies the growth error bound (1.2).
Nevertheless, we will provide a direct derivation of this fact because the
proof of KL property of definable functions in [8] involves a lot of
machinery, including the Whitney stratification and the projection formula
related to the stratum.

##  2\. KL condition implies growth error bound

We start by proving that the KL condition implies the growth error bound for
proper lower semi-continuous convex functions.

######  Theorem 2.1.

Let $f:X\to(-\infty,\infty]$ be a proper, lower semi-continuous, convex
function with $S:=\arg\min_{x\in X}f(x)\neq\emptyset$. Let $\bar{x}\in S$ and
$f_{*}:=f(\bar{x})$. If there exist $r>0$, $\eta>0$ and a desingularizing
function $\varphi\in{\mathcal{K}}(0,\eta)$ such that

$\varphi^{\prime}(f(x)-f_{*})d(0,\partial f(x))\geq 1$

for all $x\in B_{r}(\bar{x})\cap\\{f_{*}<f<f_{*}+\eta\\}$, then

$d(x,S)\leq 2\varphi(f(x)-f_{*})$

for all $x\in B_{r}(\bar{x})\cap\\{f_{*}\leq f<f_{*}+\eta\\}$.

###### Proof.

Given any $x\in B_{r}(\bar{x})\cap\\{f_{*}<f<f_{*}+\eta\\}$ and consider the
sequence $\\{x^{k}\\}$ defined by the proximal point algorithm

$x^{k}=\arg\min_{z\in
X}\left\\{f(z)+\frac{1}{2\tau}\|z-x^{k-1}\|^{2}\right\\},\quad k=1,2,\cdots$

with $x^{0}:=x$, where $\tau>0$ is a constant. Because $f$ is convex and lower
semi-continuous, we have the following results (see [6, Theorem 28.1] for
instance):

  1. $\bullet$

$\|x^{k+1}-\bar{x}\|\leq\|x^{k}-\bar{x}\|$ for all $k\geq 0$. This implies
$x^{k}\in B_{r}(\bar{x})$ for all $k\geq 0$.

  2. $\bullet$

$f(x^{k+1})\leq f(x^{k})$ for all $k$. Consequently $x^{k}\in\\{f_{*}\leq
f<f_{*}+\eta\\}$ for all $k\geq 0$.

  3. $\bullet$

$f(x^{k})\to f_{*}$ and $x^{k}\rightharpoonup x^{*}$ as $k\to\infty$ for some
$x^{*}\in S$. where $\rightharpoonup$ denotes the weak convergence in $X$.

We now show that for all integers $k\geq 1$ there holds

$\displaystyle
2\|x^{k+1}-x^{k}\|\leq\|x^{k}-x^{k-1}\|+2\left[\varphi(f(x^{k})-f_{*})-\varphi(f(x^{k+1})-f_{*})\right].$
(2.1)

If $f(x^{k})=f_{*}$, then by the definition of $x^{k+1}$ we have

$\displaystyle f(x^{k+1})+\frac{1}{2\tau}\|x^{k+1}-x^{k}\|^{2}\leq f(x^{k})$
(2.2)

which implies $f(x^{k+1})=f_{*}$ and $x^{k+1}=x^{k}$ and hence (2.1) holds
trivially. So we may assume $f(x^{k})>f_{*}$. By the definition of $x^{k}$ we
have $(x^{k-1}-x^{k})/\tau\in\partial f(x^{k})$. Thus, by the given condition
we have

$\displaystyle\varphi^{\prime}(f(x^{k})-f_{*})\geq\frac{1}{d(0,\partial
f(x^{k}))}\geq\frac{\tau}{\|x^{k}-x^{k-1}\|}.$ (2.3)

It follows from the concavity of $\varphi$, (2.2) and (2.3) that

$\displaystyle\varphi(f(x^{k+1})-f_{*})$
$\displaystyle\leq\varphi(f(x^{k})-f_{*})+\varphi^{\prime}(f(x^{k})-f_{*})(f(x^{k+1})-f(x^{k}))$
$\displaystyle\leq\varphi(f(x^{k})-f_{*})-\frac{\|x^{k+1}-x^{k}\|^{2}}{2\|x^{k}-x^{k-1}\|}.$

Therefore

$\displaystyle 2\|x^{k+1}-x^{k}\|$
$\displaystyle\leq\|x^{k}-x^{k-1}\|+\frac{\|x^{k+1}-x^{k}\|^{2}}{\|x^{k}-x^{k-1}\|}$
$\displaystyle\leq\|x^{k}-x^{k-1}\|+2\left[\varphi(f(x^{k})-f_{*})-\varphi(f(x^{k+1})-f_{*})\right]$

which shows (2.1) again.

For any integer $l>1$, by summing (2.1) over $k$ from $1$ to $l-1$ we can
obtain

$\displaystyle 2\sum_{k=1}^{l-1}\|x^{k+1}-x^{k}\|$
$\displaystyle\leq\sum_{k=1}^{l-1}\|x^{k}-x^{k-1}\|+2\left[\varphi(f(x^{1})-f_{*})-\varphi(f(x^{l})-f_{*})\right]$
$\displaystyle\leq\sum_{k=1}^{l-1}\|x^{k}-x^{k-1}\|+2\varphi(f(x^{1})-f_{*})$
$\displaystyle\leq\sum_{k=1}^{l-1}\|x^{k}-x^{k-1}\|+2\varphi(f(x^{0})-f_{*}).$

Consequently

$\displaystyle\|x^{l}-x^{0}\|\leq\sum_{k=0}^{l-1}\|x^{k+1}-x^{k}\|\leq
2\|x^{1}-x^{0}\|+2\varphi(f(x^{0})-f_{*}).$ (2.4)

Since $x^{l}\rightharpoonup x^{*}$ as $l\to\infty$, we have

$\|x^{*}-x\|^{2}=\lim_{l\to\infty}\langle
x^{l}-x,x^{*}-x\rangle\leq\liminf_{l\to\infty}\|x^{l}-x\|\|x^{*}-x\|$

which implies $\|x^{*}-x\|\leq\liminf_{l\to\infty}\|x^{l}-x\|$. Therefore, by
using $x^{*}\in S$, $x^{0}=x$ and (2.4) we can obtain

$\displaystyle
d(x,S)\leq\|x^{*}-x\|\leq\liminf_{l\to\infty}\|x^{l}-x^{0}\|\leq
2\|x^{1}-x^{0}\|+2\varphi(f(x)-f_{*}).$

By the definition of $x^{1}$ we have $\|x^{1}-x^{0}\|^{2}\leq
2\tau(f(x^{0})-f(x^{1}))\leq 2\tau(f(x)-f_{*})$. Therefore

$\displaystyle d(x,S)\leq 2\sqrt{2\tau(f(x)-f_{*})}+2\varphi(f(x)-f_{*})$

which is valid for all $\tau>0$. Letting $\tau\to 0$ then shows the result. ∎

For a given convex function, we may use Theorem 2.1 to derive the growth error
bound of its Moreau envelop from the growth error bound of the function
itself. Recall that for a proper, lower semi-continuous, convex function
$f:X\to(-\infty,\infty]$, its Moreau envelop $M_{\lambda f}$, for any
$\lambda>0$, is defined by

$M_{\lambda f}(x):=\inf_{x\in
X}\left\\{f(z)+\frac{1}{2\lambda}\|z-x\|^{2}\right\\},\quad x\in X.$

It is well known ([6]) that $M_{\lambda f}$ is a continuous differentiable
convex function with $M_{\lambda f}(x)\leq f(x)$ for all $x\in X$,

$\min_{x\in X}f(x)=\min_{x\in X}M_{\lambda f}(x),$

and $f$ and $M_{\lambda f}$ have the same set of minimizers; moreover

$\displaystyle\nabla M_{\lambda
f}(x)=\frac{1}{\lambda}\left(x-\mbox{prox}_{\lambda f}(x)\right),\quad x\in
X,$ (2.5)

where $\mbox{prox}_{\lambda f}$ denotes the proximal mapping of $f$ with
parameter $\lambda$, i.e.

$\mbox{prox}_{\lambda f}(x):=\arg\min_{x\in
X}\left\\{f(z)+\frac{1}{2\lambda}\|z-x\|^{2}\right\\},\quad x\in X.$

By the firmly nonexpansiveness of the proximal mapping, $\nabla M_{\lambda f}$
is Lipschitz continuous with constant $1/\lambda$. We have the following
result.

######  Corollary 2.2.

Let $f:X\to(-\infty,\infty]$ be a proper, lower semi-continuous, convex
function with $S:=\arg\min_{x\in X}f(x)\neq\emptyset$. If $f$ satisfies a
growth error bound at a point $\bar{x}\in S$, i.e. there exist $C>0$, $r>0$,
$\eta\in(0,\infty]$ and $\alpha\in(0,1]$ such that

$\displaystyle d(x,S)\leq C\left(f(x)-f(\bar{x})\right)^{\alpha}$ (2.6)

for all $x\in B_{r}(\bar{x})\cap\\{f(\bar{x})\leq f<f(\bar{x})+\eta\\}$, then
there exists a constant $\tilde{C}>0$ such that

$d(x,S)\leq\tilde{C}\left(M_{\lambda f}(x)-M_{\lambda
f}(\bar{x})\right)^{\min\\{\alpha,1/2\\}}$

for all $x\in B_{r}(\bar{x})\cap\\{M_{\lambda f}(\bar{x})\leq M_{\lambda
f}<M_{\lambda f}(\bar{x})+\eta\\}$.

###### Proof.

By using (2.6) and [9, Theorem 5 (ii)] we first have

$\displaystyle\left(f(x)-f(\bar{x})\right)^{1-\alpha}\leq\frac{C}{\alpha}d(0,\partial
f(x))$ (2.7)

for all $x\in B_{r}(\bar{x})\cap\\{f(\bar{x})\leq f<f(\bar{x})+\eta\\}$. We
next show that $M_{\lambda f}$ satisfies the KL condition at $\bar{x}$ with
exponent $\min\\{1-\alpha,1/2\\}$. Let $x\in B_{r}(\bar{x})\cap\\{M_{\lambda
f}(\bar{x})\leq M_{\lambda f}<M_{\lambda f}(\bar{x})+\eta\\}$ be any point. By
noting that

$M_{\lambda f}(x)=f(\mbox{prox}_{\lambda
f}(x))+\frac{1}{2\lambda}\|\mbox{prox}_{\lambda f}(x)-x\|^{2}$

and (2.5), we have $f(\bar{x})\leq f(\mbox{prox}_{\lambda f}(x))\leq
M_{\lambda f}(x)<f(\bar{x})+\eta$ and

$\displaystyle M_{\lambda f}(x)-M_{\lambda f}(\bar{x})=f(\mbox{prox}_{\lambda
f}(x))-f(\bar{x})+\frac{\lambda}{2}\|\nabla M_{\lambda f}(x)\|^{2}.$

By the nonexpansiveness of the proximal mapping, we have

$\|\mbox{prox}_{\lambda f}(x)-\bar{x}\|=\|\mbox{prox}_{\lambda
f}(x)-\mbox{prox}_{\lambda f}(\bar{x})\|\leq\|x-\bar{x}\|<r.$

Thus we may use (2.7) to conclude

$\displaystyle M_{\lambda f}(x)-M_{\lambda
f}(\bar{x})\leq\left(\frac{C}{\alpha}\right)^{\frac{1}{1-\alpha}}d(0,\partial
f(\mbox{prox}_{\lambda f}(x)))^{\frac{1}{1-\alpha}}+\frac{\lambda}{2}\|\nabla
M_{\lambda f}(x)\|^{2}.$

By the definition of $\mbox{prox}_{\lambda f}(x)$ we have

$\nabla M_{\lambda f}(x)=\frac{1}{\lambda}(x-\mbox{prox}_{\lambda
f}(x))\in\partial f(\mbox{prox}_{\lambda f}(x)).$

and thus $d(0,\partial f(\mbox{prox}_{\lambda f}(x)))\leq\|\nabla M_{\lambda
f}(x)\|$. Therefore

$\displaystyle M_{\lambda f}(x)-M_{\lambda
f}(\bar{x})\leq\left(\frac{C}{\alpha}\right)^{\frac{1}{1-\alpha}}\|\nabla
M_{\lambda f}(x)\|^{\frac{1}{1-\alpha}}+\frac{\lambda}{2}\|\nabla M_{\lambda
f}(x)\|^{2}$

Note that

$\|\nabla M_{\lambda f}(x)\|=\|\nabla M_{\lambda f}(x)-\nabla M_{\lambda
f}(\bar{x})\|\leq\frac{1}{\lambda}\|x-\bar{x}\|<\frac{r}{\lambda}.$

Thus, there must exist a constant $C_{1}>0$ such that

$\displaystyle M_{\lambda f}(x)-M_{\lambda f}(\bar{x})\leq C_{1}\|\nabla
M_{\lambda f}(x)\|^{\min\\{\frac{1}{1-\alpha},2\\}}$ (2.8)

for all $x\in B_{r}(\bar{x})\cap\\{M_{\lambda f}(\bar{x})\leq M_{\lambda
f}\leq M_{\lambda f}(\bar{x})+\eta\\}$. Finally, by using (2.8) and Theorem
2.1 we can complete the proof immediately. ∎

######  Remark 2.1.

Let $f:X\to(-\infty,\infty]$ be a proper, lower semi-continuous, convex
function that is a KL function with exponent $\gamma\in(0,1]$. It has been
proved in [19, Theorem 3.4] that if $\gamma\in(0,2/3)$ then its Moreau envelop
$M_{\lambda f}$ for any $\lambda>0$ is a KL function with exponent
$\max\\{1/2,\gamma/(2-2\gamma)\\}$. In the proof of Corrolary 2.2, we have
actually obtained the tighter result that $M_{\lambda f}$ is a KL function
with exponent $\max\\{1/2,\gamma\\}$ for all $\gamma\in(0,1]$. This tight
result has been proved in [28] recently as a special case of a general result
with an involved argument, see Theorem 5.2 and Remark 5.1 in [28]. Our
derivation is simple and straightforward.

Next we will consider extending Theorem 2.1 to nonconvex functions. We need to
replace the convex subdifferential by the Fréchet subdifferential. Recall that
for a proper function $f:X\to(-\infty,\infty]$ its Fréchet subdifferential at
a point $x\in\mbox{dom}(f):=\\{x\in X:f(x)<\infty\\}$ is the set
$\hat{\partial}f(x)$ consisting of all vectors $\xi\in X$ satisfying

$\liminf_{y\neq x,y\to x}\frac{f(y)-f(x)-\langle\xi,y-x\rangle}{\|y-x\|}\geq
0.$

When $x\notin\mbox{dom}(f)$, we set $\hat{\partial}f(x)=\emptyset$. By
definition it is straightforward to show that

$\displaystyle\hat{\partial}(f+g)(x)=\nabla
f(x)+\hat{\partial}g(x),\quad\forall x\in X$ (2.9)

if $f:X\to{\mathbb{R}}$ is continuously differentiable and
$g:X\to(-\infty,\infty]$ is proper.

In the following result we will extend Theorem 2.1 to nonconvex functions by
showing that if $f$ satisfies a KL condition at a point
$\bar{x}\in\mbox{dom}(f)$ then $f$ satisfies a growth error bound at $\bar{x}$
on a possibly smaller set.

######  Theorem 2.3.

Let $f:X\to(-\infty,\infty]$ be a proper, weakly lower semi-continuous
function and $\bar{x}\in\emph{dom}(f)$. If there exist $r>0$, $\eta>0$ and a
desingularizing function $\varphi\in{\mathcal{K}}(0,\eta)$ such that

$\displaystyle\varphi^{\prime}(f(x)-f(\bar{x}))d(0,\hat{\partial}f(x))\geq 1$
(2.10)

for all $x\in B_{r}(\bar{x})\cap\\{f(\bar{x})<f<f(\bar{x})+\eta\\}$, then
there exist $0<\tilde{r}\leq r$ and $0<\tilde{\eta}\leq\eta$ such that

$d(x,S)\leq 2\varphi(f(x)-f(\bar{x}))$

for all $x\in B_{\tilde{r}}(\bar{x})\cap\\{f(\bar{x})\leq
f<f(\bar{x})+\tilde{\eta}\\}$, where $S:=\\{x\in X:f(x)\leq f(\bar{x})\\}$.

###### Proof.

By considering the function $\tilde{f}(x):=\max\\{f(x)-f(\bar{x}),0\\}$, which
is still proper and weakly lower semi-continuous, and noting that

$\bar{x}\in S=\arg\min_{x\in X}\tilde{f}(x)$

and $\hat{\partial}\tilde{f}(x)=\hat{\partial}f(x)$ for $x$ satisfying
$f(x)>f(\bar{x})$, it suffices to prove the result by assuming that $\bar{x}$
is a minimizer of $f$. In the following we set $f_{*}:=f(\bar{x})$.

Since $\varphi\in C[0,\eta)$ and $\varphi(0)=0$, we may take
$\tilde{r}\in(0,r]$ and $\tilde{\eta}\in(0,\eta]$ such that

$\displaystyle\tilde{r}+2\varphi(\tilde{\eta})<r.$ (2.11)

Let $x\in
B_{\tilde{r}}(\bar{x})\cap\\{f(\bar{x})<f<f(\bar{x})+\tilde{\eta}\\}$ be any
fixed point, we define $x^{0}:=x$ and

$\displaystyle
x^{k}\in\arg\min_{z\in{\mathbb{R}}^{n}}\left\\{f(z)+\frac{1}{2\tau}\|z-x^{k-1}\|^{2}\right\\}$
(2.12)

for $k=1,2,\cdots$, where $\tau>0$ is a constant. Since $S\neq\emptyset$, $f$
is bounded from below. Thus, by using the weak lower semi-continuity of $f$,
it is easy to show that the sequence $\\{x^{k}\\}$ is well-defined for
$\tau>0$; due to the possible non-convexity of $f$, (2.12) may have many
solutions, we take $x^{k}$ to be any one of them. The sequence $\\{x^{k}\\}$
does not possess the nice convergence property in general as in the convex
situation. However, we may follow [4, 5] and use (2.10) to show that
$\\{x^{k}\\}$ converges to a point in $S$ with which we can establish the
desired result.

Indeed, by the definition of $\\{x^{k}\\}$ we have

$\displaystyle f(x^{k})+\frac{1}{2\tau}\|x^{k}-x^{k-1}\|^{2}\leq f(x^{k-1})$
(2.13)

which implies

$\displaystyle f_{*}\leq
f(x^{k})\leq\tilde{f}(x^{0})=f(x)<f(\bar{x})+\tilde{\eta}\quad\mbox{ for all
}k\geq 0.$ (2.14)

By the optimality of $x^{k}$ and (2.9) we also have
$\frac{1}{\tau}(x^{k-1}-x^{k})\in\hat{\partial}f(x^{k})$ and thus

$\displaystyle
d(0,\hat{\partial}f(x^{k}))\leq\frac{1}{\tau}\|x^{k}-x^{k-1}\|.$ (2.15)

We will use an induction argument to show that $x^{k}\in B_{r}(\bar{x})$ for
all $k\geq 0$ if

$\displaystyle
0<\tau<\frac{1}{8\tilde{\eta}}\left(r-\tilde{r}-2\varphi(\tilde{\eta})\right)^{2}$
(2.16)

which will be assumed in the following. Since $x^{0}=x\in
B_{\tilde{r}}(\bar{x})$ and $\tilde{r}<r$, this is trivial for $k=0$. By using
(2.13) with $k=0$ we also have

$\displaystyle\|x^{1}-x^{0}\|\leq\sqrt{2\tau(f(x^{0})-f(x^{1}))}\leq\sqrt{2\tau(f(x)-f_{*})}.$
(2.17)

Therefore, by using (2.16),

$\displaystyle\|x^{1}-\bar{x}\|\leq\|x^{0}-\bar{x}\|+\sqrt{2\tau(f(x)-f_{*})}<\tilde{r}+\sqrt{2\tau\tilde{\eta}}<r$

which shows $x^{1}\in B_{r}(\bar{x})$. Now we assume that $x^{k}\in
B_{r}(\bar{x})$ for all $0\leq k\leq j$ for some $j\geq 1$. We will show that
$x^{j+1}\in B_{r}(\bar{x})$. Based on (2.13) and (2.15) we may use the same
argument in the proof of Theorem 2.1 to establish (2.1), i.e.

$\displaystyle
2\|x^{k+1}-x^{k}\|\leq\|x^{k}-x^{k-1}\|+2\left[\varphi(f(x^{k})-f_{*})-\varphi(f(x^{k+1})-f_{*})\right]$

for all $1\leq k\leq j$. Summing the above equation over $k$ from $k=1$ to
$k=j$ gives

$\displaystyle
2\sum_{k=1}^{j}\|x^{k+1}-x^{k}\|\leq\sum_{k=1}^{j}\|x^{k}-x^{k-1}\|+2\varphi(f(x^{0})-f_{*}).$

This implies that

$\displaystyle\sum_{k=1}^{j}\|x^{k+1}-x^{k}\|+\|x^{j+1}-x^{j}\|\leq\|x^{1}-x^{0}\|+2\varphi(f(x^{0})-f_{*}).$
(2.18)

Therefore

$\displaystyle\|x^{j+1}-\bar{x}\|$
$\displaystyle\leq\sum_{k=1}^{j}\|x^{k+1}-x^{k}\|+\|x^{1}-x^{0}\|+\|x^{0}-\bar{x}\|$
$\displaystyle\leq\|x-\bar{x}\|+2\|x^{1}-x^{0}\|+2\varphi(f(x)-f_{*}).$

Consequently, by virtue of (2.17), (2.11) and (2.16) we then obtain

$\displaystyle\|x^{j+1}-\bar{x}\|$
$\displaystyle\leq\|x-\bar{x}\|+2\sqrt{2\tau(f(x)-f_{*})}+2\varphi(f(x)-f_{*})$
$\displaystyle<\tilde{r}+\sqrt{8\tau\tilde{\eta}}+2\varphi(\tilde{\eta})<r$

which implies that $x^{j+1}\in B_{r}(\bar{x})$.

Since $x^{k}\in B_{r}(\bar{x})$ for all $k\geq 0$, we can see that (2.18)
holds for all $j\geq 0$. In particular

$\sum_{k=1}^{\infty}\|x^{k+1}-x^{k}\|\leq\|x^{1}-x^{0}\|+2\varphi(f(x)-f_{*})<\infty$

which shows that $\\{x^{k}\\}$ has a finite length. Therefore $\\{x^{k}\\}$ is
a Cauchy sequence and thus it is convergent, i.e. there is $x^{*}\in X$ such
that $x^{k}\to x^{*}$ as $k\to\infty$. According to (2.13) and (2.14),
$\\{f(x^{k})\\}$ is monotonically decreasing and thus
$\bar{f}:=\lim_{k\to\infty}f(x^{k})$ exists with
$f_{*}\leq\bar{f}<f_{*}+\tilde{\eta}$. If $\bar{f}\neq f_{*}$, then
$f(x^{k})\geq\bar{f}>f_{*}$ for all $k$. Thus, by (2.10) and (2.15) we have

$1\leq\varphi^{\prime}(f(x^{k})-f_{*})d(0,\hat{\partial}f(x^{k}))\leq\frac{1}{\tau}\varphi^{\prime}(f(x^{k})-f_{*})\|x^{k}-x^{k-1}\|.$

Since $\|x^{k}-x^{k-1}\|\to 0$, we must have
$\varphi^{\prime}(f(x^{k})-f_{*})\to+\infty$ as $k\to\infty$. By the
continuity of $\varphi^{\prime}$ on $(0,\tilde{\eta})$ we then obtain

$+\infty=\lim_{k\to\infty}\varphi^{\prime}(f(x^{k})-f_{*})=\varphi^{\prime}(\bar{f}-f_{*})<\infty$

which is a contradiction. Thus $\bar{f}=f_{*}$. By the lower semi-continuity
of $f$ we have

$f_{*}\leq
f(x^{*})\leq\liminf_{k\to\infty}f(x^{k})=\lim_{k\to\infty}f(x^{k})=\bar{f}=f_{*}.$

Therefore $f(x^{*})=f_{*}$, i.e. $x^{*}\in S$. Consequently, it follows from
(2.18) and the definition of $x^{1}$ that

$\displaystyle d(x,S)\leq\|x^{*}-x\|$
$\displaystyle=\lim_{k\to\infty}\|x^{k}-x^{0}\|\leq
2\|x^{1}-x^{0}\|+2\varphi(f(x^{0})-f_{*})$ $\displaystyle\leq
2\sqrt{2\tau(f(x)-f_{*})}+2\varphi(f(x)-f_{*}).$

Letting $\tau\to 0$ shows the desired estimate. ∎

######  Remark 2.2.

For the special case that $f$ is differntiable and satisfies the KL condition
with exponent $1/2$, i.e., (2.10) with $\varphi(t)=ct^{1/2}$ for some constant
$c>0$, the result in Theorem 2.3 has been proved in [20].

Let us give a brief application of Theorem 2.3 to the Levenberg-Marquardt
method considered in [1] for solving the system of nonlinear equations

$h(x)=0$

whose solution set, denoted by $S$, is assumed to be nonempty, where
$h:{\mathbb{R}}^{m}\to{\mathbb{R}}^{n}$ is a continuously differentiable
mapping. This problem is equivalent to solving the minimization problem

$\min_{x\in{\mathbb{R}}^{m}}\left\\{\psi(x):=\frac{1}{2}\|h(x)\|^{2}\right\\}.$

The Levenberg-Marquardt method takes the form

$x^{k+1}=x^{k}-(\mu_{k}I+J_{k}^{T}J_{k})^{-1}J_{k}^{T}h(x^{k}),$

where $J_{k}$ denote the Jacobian of $h$ at $x^{k}$. The local convergence
property has been analyzed in [1]. In particular, under the Hölderian local
error bound at a solution $x^{*}\in S$, i.e. there exist $\beta>0$, $r>0$ and
$\delta\in(0,1]$ such that

$\displaystyle\beta d(x,S)\leq\|h(x)\|^{\delta},\quad\forall x\in
B_{r}(x^{*})$ (2.19)

and the Łojasiewicz gradient inequality at $x^{*}$, i.e. there exist
$\kappa>0$, $\epsilon>0$ and $\theta\in(0,1)$ such that

$\displaystyle\psi(x)^{\theta}\leq\kappa\|\nabla\psi(x)\|,\quad\forall x\in
B_{\epsilon}(x^{*}),$ (2.20)

with careful choices of the regularization parameter $\mu_{k}>0$ it has been
shown in [1, Theorem 1] that if $\theta\in(0,1/2]$ then $\psi(x^{k})\to 0$ and
$d(x^{k},S)\to 0$ linearly as $k\to\infty$ and if $\theta\in(1/2,1)$ then
there hold the sublinear convergence rates

$\psi(x^{k})=O(k^{-\frac{1}{2\theta-1}})\quad\mbox{and}\quad
d(x^{k},S)=O(k^{-\frac{\delta}{2(2\theta-1)}}).$

According to Theorem 2.3, (2.20) implies (2.19) with $\delta=2(1-\theta)$ and
therefore (2.19) can be dropped from [1, Theorem 2].

##  3\. Growth error bound for definable functions

In [8] it has been shown that any proper, lower semi-continuous, definable
function $f:{\mathbb{R}}^{n}\to(-\infty,\infty]$ in an o-minimal structure on
the real field $({\mathbb{R}},+,\cdot)$ satisfies a KL condition at each point
in its domain. To be more precise, for any $\bar{x}\in\mbox{dom}(f)$ and any
$r>0$, there exist $\eta\in(0,\infty]$ and a definable desingularizing
function $\varphi\in{\mathcal{K}}(0,\eta)$ such that

$\displaystyle\varphi^{\prime}(f(x)-f(\bar{x}))d(0,\partial f(x))\geq 1$ (3.1)

for all $x\in B_{r}(\bar{x})\cap\\{f(\bar{x})<f\leq f(\bar{x})+\eta\\}$, Here
$\partial f(x)$ denotes the limiting subdifferential of $f$ at
$x\in{\mathbb{R}}^{n}$ which is the set consisting of all those vectors
$\xi\in{\mathbb{R}}^{n}$ such that there exist sequences $\\{x^{k}\\}$ and
$\\{\xi^{k}\\}$ in ${\mathbb{R}}^{n}$ with the properties

$x^{k}\to x,\quad f(x^{k})\to f(x)\quad\mbox{ and
}\quad\xi^{k}\in\hat{\partial}f(x^{k})$

such that $\xi^{k}\to\xi$ as $k\to\infty$. Clearly
$\hat{\partial}f(x)\subset\partial f(x)$ and hence from (3.1) it follows that

$\displaystyle\varphi^{\prime}(f(x)-f(\bar{x}))d(0,\hat{\partial}f(x))\geq 1$

for all $x\in B_{r}(\bar{x})\cap\\{f(\bar{x})<f\leq f(\bar{x})+\eta\\}$.
Consequently we may use Theorem 2.3 to obtain

$\displaystyle d(x,S)\leq 2\varphi(f(x)-f_{*})$ (3.2)

for all $x\in B_{\tilde{r}}(\bar{x})\cap\\{f_{*}\leq f<f_{*}+\tilde{\eta}\\}$
for some $0<\tilde{r}\leq r$ and $0<\tilde{\eta}\leq\eta$, where
$S:=\\{x\in{\mathbb{R}}^{n}:f(x)\leq f(\bar{x})\\}$.

Recall that the proof of (3.1) given in [8] involves a lot of machinery,
including the existence of a Whitney stratification for the graph of $f$ and a
projection formula of $\partial f(x)$ onto the tangent space of the stratum
containing $x$. Thus, the derivation of (3.2) using the above procedure can be
rather involved. In the following we will provide a straightforward derivation
of (3.2) which avoids using those involved machinery.

Let us first recall the definition of o-minimal structures and definable
functions (see [10, 13, 16]).

######  Definition 3.1.

An o-minimal structure on the real field $({\mathbb{R}},+,\cdot)$ is a
sequence $\mathcal{O}=(\mathcal{O}_{n})_{n}$ of collections $\mathcal{O}_{n}$,
$n\in{\mathbb{N}}$, of subsets of ${\mathbb{R}}^{n}$ satisfying the following
axioms:

  1. (i)

For every $n\in{\mathbb{N}}$, the collection $\mathcal{O}_{n}$ is closed under
Boolean operations, i.e. finite intersections, unions, and complements.

  2. (ii)

If $A\in\mathcal{O}_{n}$ and $B\in\mathcal{O}_{m}$, then $A\times
B\in\mathcal{O}_{n+m}$.

  3. (iii)

For any set $A\in\mathcal{O}_{n+1}$ there holds $\pi(A)\in\mathcal{O}_{n}$,
where $\pi:{\mathbb{R}}^{n+1}\to{\mathbb{R}}^{n}$ denotes the canonical
projection onto ${\mathbb{R}}^{n}$,

  4. (iv)

$\mathcal{O}_{n}$ contains the family of algebraic subsets of
${\mathbb{R}}^{n}$, that is, every set of the form
$\\{x\in{\mathbb{R}}^{n}:p(x)=0\\}$, where $p:{\mathbb{R}}^{n}\to{\mathbb{R}}$
is a polynomial function.

  5. (v)

The elements of $\mathcal{O}_{1}$ are exactly the finite unions of open
intervals and points.

Every set in $\mathcal{O}_{n}$ is called a definable subset of
${\mathbb{R}}^{n}$.

######  Definition 3.2.

Given an o-minimal structure $\mathcal{O}=(\mathcal{O}_{n})_{n}$ over the real
field $({\mathbb{R}},+,\cdot)$ and a subset $A\subset{\mathbb{R}}^{m}$. A
mapping $F:A\to{\mathbb{R}}^{n}$ is called definable in $\mathcal{O}$ if its
graph

$\mbox{Gr}(F):=\\{x,y)\in A\times{\mathbb{R}}^{n}:y=F(x)\\}$

is a definable set in ${\mathbb{R}}^{m}\times{\mathbb{R}}^{n}$, i.e.
$\mbox{Gr}(F)\in\mathcal{O}_{m+n}$.

According to the definition of definable sets and definable functions, it is
easy to derive the following facts ([16]):

  1. $\bullet$

Images and inverse images of definable sets under definable functions are
definable.

  2. $\bullet$

The sum and composition of definable functions are definable.

  3. $\bullet$

If $A\subset{\mathbb{R}}^{m}$ is a definable set, then $x\to d(x,A)$ is a
definable function on ${\mathbb{R}}^{m}$. More generally, if
$g:A\subset{\mathbb{R}}^{m}\to(-\infty,\infty]$ is a definable function that
is bounded from below and $F:A\to{\mathbb{R}}^{n}$ is a definable mapping,
then the function $\varphi:{\mathbb{R}}^{n}\to(-\infty,\infty]$ defined by

$\varphi(y):=\left\\{\begin{array}[]{lll}\inf\\{g(x):x\in F^{-1}(y)\\}&\mbox{
if }F^{-1}(y)\neq\emptyset,\\\ +\infty&\mbox{ if
}F^{-1}(y)=\emptyset\end{array}\right.$

is also definable.

For single variable definable functions there holds the following monotonicity
result, see [16, Lemma 2] for instance.

######  Lemma 3.3 (Monotonicity lemma).

Let $f:(a,b)\to{\mathbb{R}}$ be a definable function and $l\in{\mathbb{N}}$.
Then there is a finite number of points $a=t_{0}<t_{1}<\cdots<t_{k}<t_{k+1}=b$
such that, on every interval $(t_{i},t_{i+1})$, $f$ is $C^{l}$ and either
strictly monotone or constant.

Next we prove a result which generalizes the well known Łojasiewicz inequality
for continuous definable functions on compact sets, see [16, Theorem 0] for
instance. Our result allows one of the functions to be lower semi-continuous
which is crucial for proving (3.2). We will make use of ideas from [17].

######  Proposition 3.4.

Let $K$ be a compact definable set in ${\mathbb{R}}^{n}$ and let
$g:K\to[0,\infty)$ and $h:K\to[0,\infty]$ be definable functions. If $g$ is
continuous, $h$ is lower semi-continuous and

$\displaystyle\\{x\in K:h(x)=0\\}\subset\\{x\in K:g(x)=0\\},$ (3.3)

then there exists a strictly increasing, definable, concave function
$\varphi\in C[0,\infty)\cap C^{1}(0,\infty)$ with $\varphi(0)=0$ such that

$g(x)\leq\varphi(h(x)),\quad\forall x\in K\cap\emph{dom}(h).$

###### Proof.

For any $t\in{\mathbb{R}}$ we set $h^{-1}(t):=\\{x\in K:h(x)=t\\}$ and
similarly for $g^{-1}(t)$. If $h^{-1}(0)=K$, then $g^{-1}(0)=K$ by (3.3) and
thus the result holds trivially with $\psi(t)=t$. If $h^{-1}(0)=\emptyset$,
then by the lower semi-continuity and nonnegativity of $h$ we can see that $h$
has a positive lower bound on $K$. Since $g$ is continuous on $K$ and $K$ is
compact, we have

$0\leq M:=\sup_{x\in K}g(x)<\infty$

and thus the result holds again with $\psi(t)=Ct$ for some positive constant
$C$. We therefore need only to consider the situation that
$h^{-1}(0)\neq\emptyset$ and $h^{-1}(0)\neq K$.

Since $K$ is a definable set and $h:K\to{\mathbb{R}}$ is a definable function,
$h(K)$ is a definable set in ${\mathbb{R}}$ and hence $h(K)$ is a finite union
of points and intervals with $0\in h(K)$.

If $0$ is an isolated point in $h(K)$, then there is a constant
$\varepsilon>0$ such that $h(x)\geq\varepsilon$ whenever $h(x)\neq 0$.
Therefore for $x\in K$ with $h(x)<\varepsilon$ we have $h(x)=0$ and hence
$g(x)=0$ by the given condition (3.3); while for $x\in K$ with
$h(x)\geq\varepsilon$ we have

$g(x)\leq M+1\leq\frac{M+1}{\varepsilon}h(x).$

We thus obtain the desired result with $\psi(t):=(M+1)t/\varepsilon$.

In the following we therefore assume $0$ is not an isolated point in $h(K)$.
By the structure of $h(K)$ as a definable set in ${\mathbb{R}}$, we can find
$T>0$ such that $[0,T]\subset h(K)$. Thus $h^{-1}(t)\neq\emptyset$ for each
$t\in[0,T]$. Define

$\mu(t):=\sup_{x\in h^{-1}(t)}g(x),\qquad t\in[0,T]$

Then $\mu$ is a definable function on $[0,T]$ and $\mu(0)=0$ by the given
condition (3.3).

We claim that $\mu$ is continuous at $t=0$. If not, then there exist
$\delta>0$ and a sequence $\\{t_{k}\\}\subset(0,T]$ with $t_{k}\to 0$ as
$k\to\infty$ such that $\mu(t_{k})\geq\delta$ for all $k$. By the definition
of supremum, there is $x^{k}\in h^{-1}(t_{k})$ such that

$g(x^{k})\geq\mu(t_{k})-\delta/2\geq\delta/2,\quad\forall k.$

Since $\\{x^{k}\\}\subset K$ and $K$ is compact, by taking a subsequence if
necessary, we may assume $x^{k}\to\bar{x}$ as $k\to\infty$ for some
$\bar{x}\in K$. By the continuity of $g$ we then have
$g(\bar{x})\geq\delta/2>0$. By the lower semi-continuity of $h$ we also have

$0\leq h(\bar{x})\leq\liminf_{k\to\infty}h(x^{k})=\lim_{k\to\infty}t_{k}=0$

which means $h(\bar{x})=0$. This together with (3.3) shows $g(\bar{x})=0$
which is a contradiction.

Now we apply Lemma 3.3 to $\mu$ and use the continuity of $\mu$ at $t=0$ to
conclude the existence of $\varepsilon\in(0,T)$ such that $\mu\in
C[0,\varepsilon]\cap C^{1}(0,\varepsilon]$. $\mu(0)=0$, and $\mu$ is either
constant or strictly monotone on $[0,\varepsilon]$.

If $\mu$ is constant on $[0,\varepsilon]$, then by using $\mu(0)=0$ we have
$\mu(t)=0$ for all $t\in[0,\varepsilon]$. Thus for $x\in K$ with
$h(x)\leq\varepsilon$ we have $g(x)=0$; while for $x\in K$ with
$h(x)>\varepsilon$ we have $g(x)\leq\frac{M+1}{\varepsilon}h(x)$. Thus the
desired result holds with $\psi(t)=(M+1)t/\varepsilon$.

If $\mu$ is strictly monotone on $[0,\varepsilon]$, by applying Lemma 3.3 to
$\mu$ and $\mu^{\prime}$ we may have $\mu(t)>0$, $\mu^{\prime}(t)>0$ and
$\mu^{\prime\prime}(t)$ has a constant sign on $(0,\varepsilon]$ by shrinking
$\varepsilon$ if necessary. By the definition of $\mu$ we have for all $x\in
K$ with $t:=h(x)\leq\varepsilon$ that

$g(x)\leq\mu(t)=\mu(h(x)).$

In case $\mu^{\prime\prime}\leq 0$ on $(0,\varepsilon]$, $\mu$ is a concave
function on $[0,\varepsilon]$. Therefore, by introducing the function

$\displaystyle\varphi(t):=\left\\{\begin{array}[]{lll}C_{0}\mu(t),&0\leq
t\leq\varepsilon,\\\
C_{0}\left(\mu(\varepsilon)+\mu^{\prime}(\varepsilon)(t-\varepsilon)\right),&\varepsilon<t<\infty\end{array}\right.$

with $C_{0}:=\max\\{1,(M+1)/\mu(\varepsilon)\\}$ and noting that $g(x)<M+1$
for $x\in K$, it is easy to see that $g(x)\leq\varphi(h(x))$ for all $x\in K$
and $\varphi\in C[0,\infty)\cap C^{1}(0,\infty)$ is strictly increasing,
definable and concave with $\varphi(0)=0$. In case $\mu^{\prime\prime}>0$ on
$(0,\varepsilon]$, $\mu$ is a convex function on $[0,\varepsilon]$. By using
$\mu(0)=0$ we then have $\mu(t)\leq\frac{\mu(\varepsilon)}{\varepsilon}t$ for
$t\in[0,\varepsilon]$. Define

$\varphi(t)=\max\left\\{\frac{\mu(\varepsilon)}{\varepsilon},\frac{M+1}{\varepsilon}\right\\}t,\quad
t\in[0,\infty).$

Again we can easily verify $g(x)\leq\varphi(h(x))$ for $x\in K$. The proof is
therefore complete. ∎

By virtue of Proposition 3.4, we are now ready to prove a growth error bound
for definable functions which in particular implies (3.2).

######  Theorem 3.5.

Let $f:{\mathbb{R}}^{n}\to(-\infty,\infty]$ be a proper, lower semi-
continuous, definable function and let $\gamma\in{\mathbb{R}}$ be such that

$S:=\\{x\in{\mathbb{R}}^{n}:f(x)\leq\gamma\\}\neq\emptyset.$

Then for any $\bar{x}\in{\mathbb{R}}^{n}$ and $r>0$ there exists a strictly
increasing, definable, concave function $\varphi\in C[0,\infty)\cap
C^{1}(0,\infty)$ with $\varphi(0)=0$ such that

$\displaystyle d(x,S)\leq\varphi([f(x)-\gamma]_{+})$ (3.4)

for all $x\in B_{r}(\bar{x})\cap\emph{dom}(f)$.

###### Proof.

Let

$g(x):=d(x,S)\quad\mbox{ and }\quad h(x):=[f(x)-\gamma]_{+}.$

Then $g$ is continuous and $h$ is lower semi-continuous on ${\mathbb{R}}^{n}$.
By the definability of $f$ we can see that both $g$ and $h$ are definable.
Moreover, $h(x)=0$ implies $g(x)=0$. Thus, we may apply Proposition 3.4 to $g$
and $h$ on the compact definable set $\overline{B_{r}(\bar{x})}$ to conclude
the proof. ∎

For semi-algebraic functions we can improve the result in Theorem 3.5 by
establishing Hölder growth error bounds. To see this, recall that a set in
${\mathbb{R}}^{n}$ is called semi-algebraic if it is a union of finite many
sets of the form

$\\{x\in{\mathbb{R}}^{n}:f(x)=0\mbox{ and }f_{i}(x)<0\mbox{ for
}i=1,\cdots,p\\},$

where $f,f_{i}:{\mathbb{R}}^{n}\to{\mathbb{R}}$ are real polynomials, and a
function $f:{\mathbb{R}}^{n}\to(-\infty,\infty]$ is called semi-algebraic if
its graph is a semi-algebraic set in ${\mathbb{R}}^{n+1}$, see [11]. It is
known that $\mathcal{SA}:=\\{\mathcal{SA}_{n}\\}$ is the smallest o-minimal
structure on the real field $({\mathbb{R}},+,\cdot)$, where $\mathcal{SA}_{n}$
denotes the collection of all semi-algebraic sets in ${\mathbb{R}}^{n}$. Thus,
for a proper, lower semi-continuous, semi-algebraic function
$f:{\mathbb{R}}^{n}\to(-\infty,\infty]$, we may use Theorem 3.5 to conclude
that (3.4) holds with a strictly increasing, semi-algebraic, concave function
$\varphi\in C[0,\infty)\cap C^{1}(0,\infty)$ satisfying $\varphi(0)=0$.
Applying the Puiseux lemma ([27]) to $\varphi$ we can conclude that

$\varphi(t)\leq Ct^{\alpha},\quad\forall t\geq 0$

for some constants $C>0$ and $\alpha\in(0,1]$. Consequently we have the
following result.

######  Corollary 3.6.

Let $f:{\mathbb{R}}^{n}\to(-\infty,\infty]$ be a proper, lower semi-
continuous, semi-algebraic function and let $\gamma\in{\mathbb{R}}$ be such
that $S:=\\{x\in{\mathbb{R}}^{n}:f(x)\leq\gamma\\}\neq\emptyset$. Then for any
$\bar{x}\in{\mathbb{R}}^{n}$ and $r>0$ there exist constants $C>0$ and
$\alpha\in(0,1]$ such that

$d(x,S)\leq C[f(x)-\gamma]_{+}^{\alpha},\quad\forall x\in B_{r}(\bar{x}).$

######  Remark 3.1.

For a given semi-algebraic function, Corollary 3.6 establishes the Hölder
growth error bound for some parameter $\alpha\in(0,1]$. Nevertheless, it does
not specify the precise value of $\alpha$. Determining this value presents a
challenging task. Interested readers can find relevant insights in [18], where
further results on this aspect are discussed.

## References

  * [1] M. Ahookhosh, F. J. Aragón Artacho, R. M. T. Fleming and P. T. Vuong, Local convergence of the Levenberg-Marquardt method under Hölder metric subregularity, Adv. Comput. Math., 45 (2019), 2771–2806.
  * [2] F. J. Aragón Artacho and M. H. Geoffroy, Characterization of metric regularity of subdifferentials, J. Convex Anal. 15 (2008), 365–380.
  * [3] F. J. Aragón Artacho and M. H. Geoffroy, Metric subregularity of the convex subdifferential in Banach spaces, J. Nonlinear Convex Anal., 15 (2014),
  * [4] H. Attouch and J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., Ser. B, 116 (2009), 5–16.
  * [5] H. Attouch, J. Bolte, B. F. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., 137 (2013), 91–129.
  * [6] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, 2011.
  * [7] J. Bolte, A. Daniilidis, and A. Lewis, The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17 (2006), 1205–1223.
  * [8] J. Bolte, A. Daniilidis, A. Lewis, and M. Shiota, Clarke Subgradients of Stratifiable Functions, SIAM J. Optim., 18 (2007), no. 2, 556–572.
  * [9] J. Bolte, T. P. Nguyen, J. Peypouquet and B. W. Suter, From error bounds to the complexity of first-order descent methods for convex functions, Math. Program., Ser. A, 165 (2017), 471–507.
  * [10] M. Coste, An Introduction to O-minimal Geometry, RAAG Notes, Institut de Recherche Mathématiques de Rennes, 81 pp., 1999.
  * [11] M. Coste, An Introduction to Semialgebraic Geometry, preprint, 2002. Available online from http://perso.univ-rennes1.fr/michel.coste/polyens/SAG.pdf
  * [12] A. L. Dontchev and R. T. Rockafellar, Implicit functions and solution mappings, A view from variational analysis, Springer Monographs in Mathematics, Springer, Dordrecht, 2009.
  * [13] L. van den Dries and C. Miller, Geometric categories and o-minimal structures, Duke Math. J., 84 (1996), no. 2, 497–540.
  * [14] D. Drusvyatskiy and A. S. Lewis, Error bounds, quadratic growth, and linear convergence of proximal methods, Math. Oper. Res., 43 (2018), no. 3, 919–948.
  * [15] A. D. Ioffe, Necessary and sufficient conditions for a local minimum. I. A reduction theorem and first order conditions, SIAM J. Control Optim., 17 (1979), no. 2, 245–250.
  * [16] K. Kurdyka, On gradients of functions definable in o-minimal structures, Annales de l’institut Fourier, 48 (1998), no. 3, 769–783.
  * [17] J. H. Lee and T. S. Pham, Openness, Hölder metric regularity, and Hölder continuity properties of semialgebraic set-valued maps, SIAM J. Optim., 32 (2022), no. 1, pp. 56–74.
  * [18] G. Li, Global error bounds for piecewise convex polynomials, Math. Program., 137 (2013), no. 1–2, Ser. A, 37–64.
  * [19] G. Li and T. K. Pong, Calculus of the exponent of Kurdyka–Lojasiewicz inequality and its applications to linear convergence of first-order methods, Found. Comput. Math., 18 (2018), 1199–1232.
  * [20] C. Liu, D. Drusvyatskiy, M. Belkin, D. Davis and Y. Ma, Aiming towards the minimizers: dast convergence of SGD for overparametrized problems, arXiv: 2306.02601, 2023.
  * [21] S. Lojasiewicz, Une propriété topologique des sous-ensembles analytiques reéls, in: Les Equations aux Dériveés Partielles, Editions du centre National ´ de la Recherche Scientifique, Paris, 1963.
  * [22] S. Lojasiewicz, Ensembles Semi-analytiques, lecture notes, Institut des Hautes Etudes Scientifiques Buressur-Yvette (Seine-et-Oise), France, 1965.
  * [23] Z. Q. Luo and P. Tseng, Error bounds and convergence analysis of feasible descent methods: a general approach, Ann. Oper. Res., 46–47 (1993), no. 1, 157–178.
  * [24] I. Necoara, Yu. Nesterov and F. Glineur, Linear convergence of first order methods for non-strongly convex optimization, Math. Program., 175 (2019), 69–107.
  * [25] B. T. Polyak, Gradient methods for minimizing functionals (in Russian), Zh. Vychisl. Mat. Mat. Fiz., 643–653, 1963.
  * [26] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer, 1998.
  * [27] C. T. C. Wall, Singular points of plane curves, London Mathematical Society Student Texts, 63. Cambridge University Press, Cambridge, 2004.
  * [28] P. Yu, G. Li and T. K. Pong, Kurdyka-Łojasiewicz Exponent via Inf-projection, Found. Comput. Math., 22 (2022), 1171–1217.


# Upper bounds of orders of automorphism groups of leafless metric graphs

Yusuke Nakamura  Graduate School of Mathematical Sciences, the University of
Tokyo, 3-8-1 Komaba, Meguro-ku, Tokyo 153-8914, Japan.
<EMAIL_ADDRESS>and  Song JuAe  Tokyo Metropolitan University 1-1
Minami-Ohsawa, Hachioji, Tokyo, 192-0397, Japan<EMAIL_ADDRESS>
###### Abstract.

We prove a tropical analogue of the theorem of Hurwitz: a leafless metric
graph of genus $g\geq 2$ has at most $12$ automorphisms when $g=2$; $2^{g}g!$
automorphisms when $g\geq 3$. These inequalities are optimal; for each genus,
we give all metric graphs which have the maximum numbers of automorphisms. The
proof is written in terms of graph theory.

###### Key words and phrases:

tropical curves, automorphisms of graphs, tropical analogue of the theorem of
Hurwitz

###### 2020 Mathematics Subject Classification:

Primary 14T20; Secondary 05C99

##  1\. Introduction

In classical algebraic geometry, the theorem of Hurwitz says that an algebraic
curve of genus $g\geq 2$ has at most $84(g-1)$ automorphisms (cf. [3, Ex. 2.5.
in Chapter IV]). In this paper, we will prove a tropical analogue of this
theorem.

Tropical geometry is, roughly speaking, an algebraic geometry over the
tropical semifield $\boldsymbol{T}:=(\boldsymbol{R}\cup\\{-\infty\\},{\rm
max},+)$ (cf. [5] for an introduction to tropical geometry). The process of
passing from classical arithmetic (resp. classical algebro-geometric objects)
to tropical arithmetic (resp. tropical objects) is referred to as
tropicalization.

Tropicalizations of algebraic curves have abstract tropical curve structures.
An abstract tropical curve is an extension of a metric graph. A metric graph
is defined as the underlying metric space of the pair of an unweighted,
undirected, finite, connected nonempty multigraph $G$ which may have loops and
a length function $l:E_{G}\to\boldsymbol{R}_{>0}$ with an identification of
each edge $e$ of $G$ with the closed interval $[0,l(e)]$, where $E_{G}$
denotes the set of edges of $G$. For an abstract tropical curve $\varGamma$,
we allow $l$ to take the value $\infty$ on only edges incident to leaves. Each
point $\infty\in[0,\infty]$ must be identified with a leaf, where $[0,\infty]$
is the one point compactification of $[0,\infty)$. If $l$ takes the value
$\infty$, then $\varGamma$ is no longer a metric space, but a topological
space (cf. [4] for more details).

An abstract tropical curve $\varGamma$ has a genus in the usual topological
sense. It coincides with $\\#E_{G}-\\#V_{G}+1$ for any pair $(G,l)$ defining
$\varGamma$, where $V_{G}$ denotes the set of vertices of $G$. Nonnegative
integer $\\#E_{G}-\\#V_{G}+k$ for a graph $G$ with $k$ connected components is
sometimes called the (first) Betti number of $G$ (cf. [2]).

In the category of abstract tropical curves, morphisms between abstract
tropical curves are (finite) harmonic morphisms. An automorphism of a metric
graph $\varGamma$, i.e., a finite harmonic morphism $\varGamma\to\varGamma$ of
degree one is an isometry $\varGamma\to\varGamma$, and vice versa. For a
metric graph $\varGamma$, we write its automorphism group as
$\operatorname{Aut}(\varGamma)$, which coincides with the isometry group of
$\varGamma$.

The following is our main theorem:

######  Theorem 1.

Let $\varGamma$ be a leafless metric graph of genus $g\geq 2$. Then the
inequality

$\\#\operatorname{Aut}(\varGamma)\leq\begin{cases}2^{g}g!&\text{if $g\geq
3$,}\\\ 12&\text{if $g=2$}\end{cases}$

holds. Furthermore, the inequality becomes an equality if and only if
$\varGamma$ is one of the following:

  * •

$\varGamma$ is defined by the pair of $G_{{\rm banana},g}$ and some $l$ whose
image is one point with $g=2,3$.

  * •

$\varGamma$ is defined by the pair of $G_{{\rm bouquet},g}$ and some $l$ whose
image is one point with $g\geq 3$.

  * •

$\varGamma$ is defined by the pair of $G_{{\rm lollipop},g}$ and some $l$ such
that all $g$ loops have the same length and all $g$ bridges have the same
length with $g\geq 3$.

Here, an abstract tropical curve is leafless if it has no one valent points
(it is said to be minimal in [1]). The valency of a point $x$ of an abstract
tropical curve is the minimum number of connected components of
$U\setminus\\{x\\}$ with all neighborhoods $U$ of $x$. For $g\geq 1$, $G_{{\rm
banana},g}$ denotes the multigraph that has only two vertices and $g+1$
multiple edges between them. For $g\geq 1$, $G_{{\rm bouquet},g}$ denotes the
graph that has only one vertex and $g$ loops incident to it. For $g\geq 2$,
$G_{{\rm lollipop},g}$ denotes the graph obtained from $G_{{\rm bouquet},g}$
by replacing the unique vertex with the star $S_{g}$ with $g$ leaves.

We note that there are no upper bounds of $\\#\operatorname{Aut}(\varGamma)$
without the leafless condition in Theorem 1. Let $\varGamma$ be a metric graph
of genus $g$, and let $v\in\varGamma$ be a point. Let $\varGamma^{\prime}$ be
the metric graph obtained from $\varGamma$ by attaching $0$’s of $n$ copies of
the intervals $[0,1]$ to the point $v$. Then $\varGamma^{\prime}$ has genus
$g$, and we have $\\#\operatorname{Aut}(\varGamma^{\prime})\geq n!$ since
$\operatorname{Aut}(\varGamma^{\prime})$ contains the symmetric group of
degree $n$ as a subgroup.

In tropical geometry, it is natural to deal only leafless ones. There is an
operation called tropical modification which defines an equivalence relation
on all abstract tropical curves. Two abstract tropical curves are equivalent
to each other if and only if one of them is obtained from the other by a
finite number of retractions that contract a leaf edge to its one point (cf.
[1]). Hence for an equivalence class, all representatives have the same genus
and there exists a unique leafless representative. For this reason, in
tropical geometry, one studies leafless metric graphs for some essential
information of their equivalence classes (cf. [6] for higher dimension cases).

Theorem 1 follows the following combinatorial proposition:

######  Proposition 2.

Let $G$ be a connected leafless graph of Betti number $g\geq 2$. Then the
inequality

$\\#\operatorname{Aut}(G)\leq\begin{cases}2^{g}g!&\text{if $g\geq 3$,}\\\
12&\text{if $g=2$}\end{cases}$

holds. Furthermore, the inequality becomes an equality if and only if $G$ is
one of the following:

  * (A)

$G$ is a graph obtained from $G_{{\rm banana},g}$ by subdividing all $g+1$
edges into the same number ($\geq 1$) of edges with $g=2,3$.

  * (B)

$G$ is a graph obtained from $G_{{\rm bouquet},g}$ by subdividing all $g$
loops into the same number ($\geq 2$) of edges with $g\geq 3$.

  * (C)

$G$ is a graph obtained from $G_{{\rm lollipop},g}$ by subdividing all $g$
loops into the same number ($\geq 2$) of edges and all $g$ bridges into a same
number ($\geq 1$) of edges with $g\geq 3$.

Figure 1. The left graph is $G_{{\rm banana},2}$, the center graph is $G_{{\rm
bouquet},3}$ and the right graph is $G_{{\rm lollipop},4}$. Black dots (resp.
lines) stand for vertices (resp. edges).

The rest of this paper is organized as follows. In Section 2, we prepare
definitions in graph theory and three lemmas which we need later. Section 3
gives the proofs of the two assertions above.

## Acknowledgements

The first author is partially supported by JSPS KAKENHI Grant Number 18K13384.
The second author is supported by JSPS KAKENHI Grant Number 20J11910.

##  2\. Preliminaries

In this paper, a graph $G=(V_{G},E_{G},\varepsilon_{G})$ means an undirected
finite graph allowing multiple edges and loops. Here, $V_{G}$ is the finite
set of vertices, and $E_{G}$ is the finite set of edges, and
$\varepsilon_{G}:E_{G}\to 2^{V_{G}}$ is the map that associates an edge $e\in
E_{G}$ with its vertices, where $2^{V_{G}}$ is the power set of $V_{G}$. We
note that $\\#(\varepsilon_{G}(e))\in\\{1,2\\}$ holds for any $e\in E_{G}$. An
edge $e$ is called a loop when $\\#(\varepsilon_{G}(e))=1$. A cut vertex
(resp. bridge) of a graph $G$ is a vertex (resp. an edge) whose deletion
increases the number of connected components of $G$. The degree of a vertex is
the number of edges incident to it, where a loop is counted twice. A vertex of
degree one is called a leaf.

An automorphism $f=(f_{V},f_{E})$ of a graph $G$ is bijective maps
$f_{V}:V_{G}\to V_{G}$ and $f_{E}:E_{G}\to E_{G}$ satisfying
$f_{V}\circ\varepsilon_{G}=\varepsilon_{G}\circ f_{E}$.
$\operatorname{Aut}(G)$ denotes the set of all automorphisms of $G$. For a
subset $S\subset V_{G}\sqcup E_{G}$, $\operatorname{Aut}(G)_{S}$ denotes the
set of all $f\in\operatorname{Aut}(G)$ satisfying $f_{V}(v)=v$ and
$f_{E}(e)=e$ for any $v\in S\cap V_{G}$ and $e\in S\cap E_{G}$. When $S$
consists of only one element $x$, we sometimes write
$\operatorname{Aut}(G)_{x}$ instead of $\operatorname{Aut}(G)_{\\{x\\}}$. We
note that according to this definition, $\\#\operatorname{Aut}(G_{{\rm
bouquet},1})=1$.

######  Lemma 3.

Let $G$ be a connected leafless graph. Let $x$ be a vertex and let
$e_{1},\ldots,e_{d}$ be all the edges incident to $x$. Let $G^{\prime}$ be the
subgraph of $G$ obtained by removing $x,e_{1},\ldots,e_{d}$ from $G$. Let
$G^{\prime\prime}$ be the maximum subgraph of $G^{\prime}$ in which all
vertices have degree at least two. We set

$S=\left(E_{G}\setminus E_{G^{\prime\prime}}\right)\sqcup\bigcup_{e\in
E_{G}\setminus E_{G^{\prime\prime}}}\varepsilon_{G}(e).$

Then the following hold.

  1. (1)

$\operatorname{Aut}(G)_{\\{x,e_{1},\ldots,e_{d}\\}}=\operatorname{Aut}(G)_{S}$.

  2. (2)

Suppose that $G^{\prime\prime}\not=\varnothing$. Then there exists an
injective map
$\operatorname{Aut}(G)_{\\{x,e_{1},\ldots,e_{d}\\}}\to\operatorname{Aut}(G^{\prime\prime})_{y}$
for some vertex $y\in V_{G^{\prime\prime}}$.

###### Proof.

If $G$ is trivial, then the assertions are clear. Assume that $G$ is not
trivial. $G^{\prime\prime}$ is obtained from $G^{\prime}$ by repeating the
following two operations:

  * (a)

Removing a vertex $v$ of degree zero.

  * (b)

Removing a leaf $v$ and the edge $e$ incident to $v$.

Let

$G^{\prime}=G_{0}\supset G_{1}\supset\cdots\supset G_{c}=G^{\prime\prime}$

be its process. Then, corresponding to the two operations above, the following
hold:

  * (a)

$E_{G_{i+1}}=E_{G_{i}}$ and $V_{G_{i}}\setminus V_{G_{i+1}}=\\{v\\}$.

  * (b)

$E_{G_{i}}\setminus E_{G_{i+1}}=\\{e\\}$ and $V_{G_{i}}\setminus
V_{G_{i+1}}=\\{v\\}$.

We set

$S_{i}=\left(E_{G}\setminus E_{G_{i}}\right)\sqcup\bigcup_{e\in E_{G}\setminus
E_{G_{i}}}\varepsilon_{G}(e).$

Since $G$ is connected and nontrivial, $d\geq 1$ holds. Hence
$S_{0}\supset\\{x,e_{1},\ldots,e_{d}\\}$. By the definition of $S_{0}$, we
have
$\operatorname{Aut}(G)_{\\{x,e_{1},\ldots,e_{d}\\}}=\operatorname{Aut}(G)_{S_{0}}$.
Thus, to prove (1), it is sufficient to show
$\operatorname{Aut}(G)_{S_{i}}=\operatorname{Aut}(G)_{S_{i+1}}$ for each
$0\leq i\leq c-1$.

The assertion is clear for case (a). Suppose (b). Let $u$ be the end point of
$e$ that is not $v$. Since all vertices of $G$ have degree at least two, it
follows that $v\in S_{i}$. Furthermore, any edge of $G$ incident to $v$ other
than $e$ is contained in $S_{i}$. Therefore any
$f\in\operatorname{Aut}(G)_{S_{i}}$ fixes $e$ and hence $u$ too. Thus we have
$\operatorname{Aut}(G)_{S_{i}}=\operatorname{Aut}(G)_{S_{i+1}}$, which
completes the proof of (1).

By construction, it follows that $S\cap V_{G^{\prime\prime}}\not=\varnothing$
when $G^{\prime\prime}\not=\varnothing$. Pick any $y\in S\cap
V_{G^{\prime\prime}}$. Then the restriction map
$\operatorname{Aut}(G)_{S}\to\operatorname{Aut}(G^{\prime\prime})_{y}$ is
induced and it is injective. ∎

Let $G$ be a graph and $S\subset E_{G}$. Then the contraction $G/S$ is a graph
defined as follows:

$V_{G/S}=V_{G}/\sim,\qquad E_{G/S}=E_{G}\setminus
S,\qquad\varepsilon_{G/S}:E_{G/S}\to 2^{V_{G/S}},$

where $\sim$ is the minimum relation satisfying $x\sim y$ for any $x,y\in
V_{G}$ with $\\{x,y\\}\in\varepsilon_{G}(S)$, and $\varepsilon_{G/S}$ is the
composition $E_{G/S}\to E_{G}\xrightarrow{\varepsilon_{G}}2^{V_{G}}\to
2^{V_{G/S}}$.

######  Lemma 4.

Let $G$ be a graph and $S\subset E_{G}$. Let $G/S$ be its contraction. Then
the following hold.

  1. (1)

If $S$ is $\operatorname{Aut}(G)$-invariant, there exists a group homomorphim
$\operatorname{Aut}(G)\to\operatorname{Aut}(G/S)$ which commutes with the
projection $V_{G}\to V_{G/S}$ and the inclusion $E_{G/S}\to E_{G}$.

  2. (2)

Let $S$ be the set of all bridges of $G$. Then, the Betti number of $G/S$ is
equal to that of $G$.

  3. (3)

In addtion to (2), we assume that $G$ is leafless. Then the group homomorphism
$\operatorname{Aut}(G)\to\operatorname{Aut}(G/S)$ is injective.

###### Proof.

We shall prove (1). Let $f=(f_{V},f_{E})\in\operatorname{Aut}(G)$. Since $S$
is $\operatorname{Aut}(G)$-invariant, $f_{V}$ and $f_{E}$ induce the bijective
maps $f^{\prime}_{V}$ on $V_{G/S}=V_{G}/\sim$ and $f^{\prime}_{E}$ on
$E_{G/S}=E_{G}\setminus S$, respectively. Since they satisfy
$f^{\prime}_{E}\circ\varepsilon_{G/S}=\varepsilon_{G/S}\circ f^{\prime}_{V}$,
we have
$f^{\prime}=(f^{\prime}_{V},f^{\prime}_{E})\in\operatorname{Aut}(G/S)$. Then
we obtain a group homomorphim
$\operatorname{Aut}(G)\to\operatorname{Aut}(G/S);\ f\mapsto f^{\prime}$, which
proves (1).

Since $S$ forms the union of trees, we have
$\\#V_{G}-\\#V_{G/S}=\\#E_{G}-\\#E_{G/S}$, which proves (2).

We shall prove (3). Let $f\in\operatorname{Aut}(G)$ be an element whose image
in $\operatorname{Aut}(G/S)$ is the identity map. Let $H$ be the subgraph of
$G$ such that $E_{H}=S$ and $V_{H}=\bigcup_{e\in S}\varepsilon_{G}(e)$. By
assumption, $f\in\operatorname{Aut}(G)_{F}$ holds for $F=(V_{G}\setminus
V_{H})\sqcup(E_{G}\setminus E_{H})$. Let $v$ be a leaf of $H$ and let $e$ be
the edge of $H$ incident to $v$. First, we shall see that $f$ fixes $v$. Since
$v$ has degree at least two in $G$, there exists an edge $e_{1}\in
E_{G}\setminus E_{H}$ such that $e_{1}\not=e$ and
$v\in\varepsilon_{G}(e_{1})$. If $e_{1}$ is a loop, then $f$ fixes $v$ because
$f$ fixes $e_{1}$. Suppose that $e_{1}$ is not a loop. Let $v^{\prime}$ be the
end point of $e_{1}$ that is not $v$. Since $f$ fixes $e_{1}$, it follows that
$f_{V}(v)=v$ or $f_{V}(v)=v^{\prime}$. Since $S$ does not contain a circuit,
it follows that $v\not\sim v^{\prime}$. On the other hand, since the image of
$f$ in $\operatorname{Aut}(G/S)$ is the identity map, we have $f_{V}(v)\sim
v$. Therefore $f$ fixes $v$. Since $f$ fixes all edges incident to $v$ except
$e$, it also fixes $e$. Let $v^{\prime\prime}$ be the end point of $e$ that is
not $v$. Then $f$ also fixes $v^{\prime\prime}$. Let $H^{\prime}$ be the
subgraph of $H$ obtained by removing $e$ and $v$. Then we have showed that
$f\in\operatorname{Aut}(G)_{F^{\prime}}$ for $F^{\prime}=(V_{G}\setminus
V_{H^{\prime}})\sqcup(E_{G}\setminus E_{H^{\prime}})$. Since $H$ is a finite
union of trees, we can see $f\in\operatorname{Aut}(G)_{V_{G}\sqcup
E_{G}}=\\{{\rm id}_{G}\\}$ by induction, which completes the proof. ∎

######  Lemma 5.

  1. (1)

Let $l$, $m$ and $n$ be positive integers with $m,n\geq l$. Then we have

$m!n!\leq l!(m+n-l)!.$

  2. (2)

Let $n_{1},\ldots,n_{c}$ be positive integers. Then we have

$(n_{1}!)(n_{2}!)\dotsm(n_{c}!)\leq\left(-c+1+\sum_{i=1}^{c}n_{i}\right)!.$

The inequality becomes an equality if and only if all but one of
$n_{1},\ldots,n_{c}$ are equal to one.

###### Proof.

(1) is straightforward. By induction on $c$, (2) is reduced to (1) for $l=1$.
∎

##  3\. Main results

In this section, we will prove the two assertions in Section 1.

The following proposition is valid also for $g=1$ in contrast to Proposition
2.

######  Proposition 6.

Let $G$ be a connected leafless graph of Betti number $g$ and $x$ a vertex of
$G$. Then the inequality

$\\#\operatorname{Aut}(G)_{x}\leq 2^{g}g!$

holds.

###### Proof.

If $g=0$, then $G$ is trivial, and the assertion is clear. Therefore we may
assume that $g\geq 1$. Furthermore, by Lemma 4, we may assume that $G$ has no
bridges.

Let

$G\setminus\\{x\\}=U_{1}\sqcup\cdots\sqcup U_{k}$

be the decomposition to the connected components. Let $G_{i}=U_{i}\cup\\{x\\}$
be the subgraph of $G$. Let $g_{i}$ be the Betti number of $G_{i}$. Then
$g=\sum_{i=1}^{k}g_{i}$ and $g_{i}\geq 1$ hold. Furthermore, since $G$ has no
bridges, each $G_{i}$ is leafless.

First, we treat the case when $k=1$.

######  Claim 7.

When $k=1$, the inequality

$\\#\operatorname{Aut}(G)_{x}\leq 2^{g-d+1}d!(g-d+1)!$

holds, where $d$ is the number of edges incident to $x$. In particular,
Proposition 6 holds when $k=1$.

###### Proof.

Let $e_{1},\ldots,e_{d}$ be all the edges incident to $x$. Let
$S_{d}=S\\{e_{1},\ldots,e_{d}\\}$ denote the permutation group of
$\\{e_{1},\ldots,e_{d}\\}$. Then a group homomorphism $s$ is defined by

$s:\operatorname{Aut}(G)_{x}\to S_{d};\qquad
f\mapsto\left(\begin{smallmatrix}e_{1}&e_{2}&\cdots&e_{d}\\\
f(e_{1})&f(e_{2})&\cdots&f(e_{d})\end{smallmatrix}\right).$

Thus

$\\#\operatorname{Aut}(G)_{x}\leq\\#S_{d}\cdot\\#\operatorname{Ker}(s)=d!\cdot\\#\operatorname{Aut}(G)_{\\{x,e_{1},\ldots,e_{d}\\}}$

hold. We define the subgraph $G^{\prime}$ of $G$ by removing
$x,e_{1},\ldots,e_{d}$ from $G$. Let $G^{\prime\prime}$ be the maximum
subgraph of $G^{\prime}$ in which all vertices have degree at least two. We
note that $G^{\prime}$ and $G^{\prime\prime}$ are connected since $k=1$.
Furthermore, $G^{\prime}\not=\varnothing$ holds unless $G=G_{{\rm
bouquet},1}$. If $G^{\prime}\not=\varnothing$, then the Betti number of
$G^{\prime}$ is equal to $g-d+1$. In particular, we have $g-d+1\geq 0$.

Suppose $d=g+1$. Then $G^{\prime}$ is a tree, and it follows that
$G^{\prime\prime}=\varnothing$. Then by Lemma 3,

$\\#\operatorname{Aut}(G)_{\\{x,e_{1},\ldots,e_{d}\\}}=\\#\operatorname{Aut}(G)_{V_{G}\sqcup
E_{G}}=1,$

and hence

$\\#\operatorname{Aut}(G)_{x}\leq
d!\cdot\\#\operatorname{Aut}(G)_{\\{x,e_{1},\ldots,e_{d}\\}}=(g+1)!\leq
2^{g}g!.$

Suppose that $g-d+1\geq 1$. If $G=G_{{\rm bouquet},1}$, then we have
$\\#\operatorname{Aut}(G)_{x}=1<2=2^{g-d+1}d!(g-d+1)!$. In what follows, we
suppose $G^{\prime\prime}\not=\varnothing$. Then we have $d\geq 2$ and the
Betti number of $G^{\prime\prime}$ is equal to $g^{\prime}:=g-d+1$. Then by
Lemma 3(2), there exists a vertex $y$ of $G^{\prime\prime}$ such that

$\\#\operatorname{Aut}(G)_{\\{x,e_{1},\ldots,e_{d}\\}}\to\\#\operatorname{Aut}(G^{\prime\prime})_{y};\qquad
f\mapsto f|_{G^{\prime\prime}}$

is injective. Thus, we have

$\\#\operatorname{Aut}(G)_{\\{x,e_{1},\ldots,e_{d}\\}}\leq\\#\operatorname{Aut}(G^{\prime\prime})_{y}.$

By induction on the Betti number, we may assume that

$\\#\operatorname{Aut}(G^{\prime\prime})_{y}\leq
2^{g^{\prime}}g^{\prime}!=2^{g-d+1}(g-d+1)!.$

Therefore, we have

$\\#\operatorname{Aut}(G)_{x}\leq 2^{g-d+1}d!(g-d+1)!<2^{g}g!.$

Here, the second inequality follows from Lemma 5 and $d\geq 2$. ∎

Suppose $k\geq 2$. Then by $f\in\operatorname{Aut}(G)_{x}$, each $G_{i}$ is
mapped to some $G_{j}$. It induces the group homomorphism

$t:\operatorname{Aut}(G)_{x}\to S_{k}=S\\{G_{1},\ldots,G_{k}\\};\qquad
f\mapsto\left(\begin{smallmatrix}G_{1}&G_{2}&\cdots&G_{k}\\\
f(G_{1})&f(G_{2})&\cdots&f(G_{k})\end{smallmatrix}\right).$

Since the kernel $\operatorname{Ker}(t)$ consists of all
$f\in\operatorname{Aut}(G)_{x}$ such that $f(G_{i})=G_{i}$ for each $i$,

$\\#\operatorname{Aut}(G)_{x}\leq\\#S_{k}\cdot\\#\operatorname{Ker}(t)\leq
k!\cdot\\#\operatorname{Aut}(G_{1})_{x}\dotsm\\#\operatorname{Aut}(G_{k})_{x}$

hold. Then, by induction on the Betti number, we have

(6.1) $\displaystyle\\#\operatorname{Aut}(G)_{x}$ $\displaystyle\leq
k!(2^{g_{1}}g_{1}!)\dotsm(2^{g_{k}}g_{k}!)$
$\displaystyle=2^{g}(k!)(g_{1}!)\dotsm(g_{k}!)$ (6.2) $\displaystyle\leq
2^{g}\left(-k-1+1+k+\sum_{i=1}^{k}g_{i}\right)!$ $\displaystyle=2^{g}g!.$

The last inequality follows from Lemma 5. We complete the proof of Proposition
6. ∎

######  Remark 8.

In Proposition 6, the equality $\\#\operatorname{Aut}(G)_{x}=2^{g}g!$ holds if
and only if the pair of $G$ and $x$ is one of the following:

  1. (1)

$G$ is trivial and $x$ is the unique vertex.

  2. (2)

$G$ is a subdivision of $G_{{\rm banana},1}$ and $x$ is any vertex.

  3. (3)

$G$ is one of the graphs in (B) of Proposition 2 with $g\geq 2$ and $x$ is the
unique cut vertex.

  4. (4)

$G$ is one of the graphs in (C) of Proposition 2 with $g\geq 2$ and $x$ is the
unique cut vertex of $S_{g}$.

First, it is clear that $G$ and $x$ in the above list satisfy the equality
$\\#\operatorname{Aut}(G)_{x}=2^{g}g!$. In what follows, we shall see the
inverse implication.

Suppose that $G$ and $x$ satisfy the equality. If $g=0$, then $G$ must be (1).
Suppose that $g\geq 1$ and $G$ is bridgeless. When $k=1$, we have $g=1$ by the
second inequality in (7.1) in the proof of Claim 7, and the pair $(G,x)$ is
confined to (2). When $k\geq 2$, we note that the inequality (6.2) becomes an
equality only if $g_{1}=\cdots=g_{k}=1$. In this case, $G$ must be a
subdivision of $G_{{\rm bouquet},g}$. For such $G$, it is clear that only the
pairs $(G,x)$ as in (3) satisfy the equality. Finally, suppose that $g\geq 1$
and $G$ has a bridge. Let $S$ be the set of all bridges, and let $G/S$ be the
contraction. Then, from what we have already seen, $G/S$ must be one of the
graphs in (3). Therefore, the pair $(G,x)$ turns out to be one of the pairs in
(4).

Now we can prove Proposition 2.

###### Proof of Proposition 2.

First, it is clear that $G$ in the list (A), (B), and (C) satisfies the
equality

$\\#\operatorname{Aut}(G)=\begin{cases}2^{g}g!&\text{if $g\geq 3$,}\\\
12&\text{if $g=2$}.\end{cases}$

Suppose that $G$ has a bridge. Let $S$ be the set of all bridges, and let
$G/S$ be the contraction. Then by Lemma 4, we have
$\\#\operatorname{Aut}(G)\leq\\#\operatorname{Aut}(G/S)$. Furthermore, if $G$
satisfies the equality ($\star$) and if $G/S$ is one of the graphs in (A) and
(B), then it is easy to see that $G$ is one of the graphs in (C).

Suppose that $G$ has a loop. Let $G^{\prime}$ be the subdivision of $G$
obtained by adding one vertex to each loop of $G$. Then $G^{\prime}$ is a
loopless graph and we have
$\\#\operatorname{Aut}(G)<\\#\operatorname{Aut}(G^{\prime})$.

By the discussion above, it is sufficient to show the inequality in
Proposition 2 for $G$ with the following additional condition:

  * •

$G$ is loopless and bridgeless.

Furthermore, for such $G$, it is sufficient to show the equality ($\star$)
holds only if $G$ is one of the graphs in (A) and (B). In what follows, we
suppose that $G$ is loopless and bridgeless.

Let $d$ be the maximum degree of the vertices of $G$ and let $l$ be the number
of vertices of $G$ of degree $d$. Since $g\geq 2$, we have $d\geq 3$.
Furthermore, by the hand-shaking lemma, we have

$2\\#E_{G}\geq dl+2(\\#V_{G}-l),$

and hence

$\displaystyle g$ $\displaystyle=\\#E_{G}-\\#V_{G}+1$
$\displaystyle\geq\frac{dl}{2}+\\#V_{G}-l-\\#V_{G}+1$
$\displaystyle=\left(\frac{d}{2}-1\right)l+1.$

As $d\geq 3$, we have $l\leq 2g-2$.

Let $x_{1},\ldots,x_{l}$ be all the vertices of $G$ of degree $d$. Set
$x=x_{1}$. If $l=1$, then $\operatorname{Aut}(G)=\operatorname{Aut}(G)_{x}$
holds and the assertion follows from Proposition 6 and Remark 8. In what
follows, we assume $l\geq 2$, and in particular, $g\geq d-1$. The group
homomorphism

$s:\operatorname{Aut}(G)\to S_{l}=S\\{x_{1},\ldots,x_{l}\\};\quad
f\mapsto\left(\begin{smallmatrix}x_{1}&x_{2}&\cdots&x_{l}\\\
f(x_{1})&f(x_{2})&\cdots&f(x_{l})\end{smallmatrix}\right)$

induces an injective map on the left cosets

$\bigl{\\{}f\operatorname{Aut}(G)_{x}\ \big{|}\
f\in\operatorname{Aut}(G)\bigr{\\}}\to\bigl{\\{}\sigma
S\\{x_{2},\ldots,x_{l}\\}\ \big{|}\ \sigma\in
S\\{x_{1},\ldots,x_{l}\\}\bigr{\\}}.$

Therefore we have

$\\#\operatorname{Aut}(G)\leq l\cdot\\#\operatorname{Aut}(G)_{x}.$

Let $G\setminus\\{x\\}=U_{1}\sqcup\cdots\sqcup U_{k}$ be the decomposition to
the connected components of $G\setminus\\{x\\}$. Let $G_{i}=U_{i}\cup\\{x\\}$
be the subgraph of $G$, and let $g_{i}$ be the Betti number of $G_{i}$. Then
$g=\sum_{i=1}^{k}g_{i}$ and $g_{i}\geq 1$ hold. Furthermore, each $G_{i}$ is
loopless since $G$ is bridgeless.

We deal with two cases where $k=1$ and where $k\geq 2$ separately.

Case 1 Suppose $k=1$.

Case 1-1 Suppose $d=g+1$. Then we have

$g\geq\left(\frac{d}{2}-1\right)l+1=g+\left(\frac{l}{2}-1\right)(g-1).$

Therefore, we have $l=2$ since $g\geq 2$ and $l\geq 2$. By Claim 7, we have

$\\#\operatorname{Aut}(G)\leq l\cdot\\#\operatorname{Aut}(G)_{x}\leq
2d!=2\cdot(g+1)!.$

Here, we note that $d$ equals the number of the edges incident to $x$ since
$G$ is loopless.

When $g\geq 3$, we have $2\cdot(g+1)!\leq 2^{g}g!$ and get the desired
inequality $\\#\operatorname{Aut}(G)\leq 2^{g}g!$. We note that the equality
$\\#\operatorname{Aut}(G)=2^{g}g!$ holds only if $(g,d,l)=(3,4,2)$. Under the
assumption that $k=1$, only subdivisions of $G_{{\rm banana},3}$ may satisfy
$(g,d,l)=(3,4,2)$. Hence $G$ must be one of the graphs in (A) with $g=3$ if
$\\#\operatorname{Aut}(G)=48=2^{g}g!$ hold.

When $g=2$, we have $d=3$. In this case, since $G$ is bridgeless, $G$ is a
subdivision of $G_{\rm banana,2}$ and we have $\\#\operatorname{Aut}(G)\leq
12=2^{g}g!$. The equality $\\#\operatorname{Aut}(G)=12$ holds if and only if
$G$ is one of the graphs in (A) with $g=2$.

Case 1-2 Suppose $d<g+1$. By Claim 7, we have

$\displaystyle\\#\operatorname{Aut}(G)$ $\displaystyle\leq
l\cdot\\#\operatorname{Aut}(G)_{x}$ $\displaystyle\leq l\cdot
2^{g-d+1}d!(g-d+1)!$ $\displaystyle\leq(2g-2)2^{g-d+1}d!(g-d+1)!.$

Thus, it is sufficient to show that

$d!(g-d+1)!(2g-2)\leq 2^{d-1}g!.$

If $g-d+1=1$, then the inequality is equivalent to $g-1\leq 2^{g-2}$ and it
holds since $g=d\geq 3$. Therefore we get the desired inequality
$\\#\operatorname{Aut}(G)\leq 2^{g}g!$. We note that the equality
$\\#\operatorname{Aut}(G)=2^{g}g!$ holds only if $g$ and $l$ satisfy

$l=2g-2,\quad g-1=2^{g-2}.$

Since $g=d\geq 3$, $(g,d,l)=(3,3,4)$ is the only case. In this case, $G$ is
one of the following graphs.

  * •

A subdivision of $H_{1}$ in Figure 2.

  * •

A subdivision of $H_{2}$ in Figure 2.

We have $\\#\operatorname{Aut}(G)\leq\\#\operatorname{Aut}(H_{1})=4!<2^{g}g!$
in the formar case, and
$\\#\operatorname{Aut}(G)\leq\\#\operatorname{Aut}(H_{2})=16<2^{g}g!$ in the
latter case. Therefore, the equality $\\#\operatorname{Aut}(G)=2^{g}g!$ never
holds in this case.

Figure 2. We call the left graph $H_{1}$ and the right graph $H_{2}$. Black
dots (resp. lines) stand for vertices (resp. edges).

If $g-d+1\geq 2$, we have

$\displaystyle\frac{2^{d-1}}{2g-2}\cdot\frac{g!}{d!(g-d+1)!}$
$\displaystyle\geq\frac{4}{2g-2}\cdot\frac{g!}{d!(g-d+1)!}$
$\displaystyle=\frac{2}{(g+1)(g-1)}\left(\begin{matrix}g+1\\\
d\end{matrix}\right)$ $\displaystyle>1.$

Here the first inequality follows because $d\geq 3$. The second inequality
follows from the fact that

$\left(\begin{matrix}g+1\\\ d\end{matrix}\right)\geq\left(\begin{matrix}g+1\\\
2\end{matrix}\right)=\frac{(g+1)g}{2}>\frac{(g+1)(g-1)}{2},$

which is obtained by $d\geq 2$ and $g-d+1\geq 2$. Therefore we get the strict
inequality $\\#\operatorname{Aut}(G)<2^{g}g!$ in this case.

Case 2 Suppose $k\geq 2$.

First, we see that $d\geq 4$, and especially $2\leq l\leq g-1$. Suppose the
contrary that $d=3$. Let $e_{1}$, $e_{2}$, and $e_{3}$ be the edges incident
to $x$. As $k\geq 2$, there exists $G_{i}$ such that $E_{G_{i}}$ contains just
one of $e_{1}$, $e_{2}$, and $e_{3}$. Such edge should be a bridge, a
contradiction.

Let $t$ denote the group homomorphism

$t:\operatorname{Aut}(G)_{x}\to S_{k}=S\\{G_{1},\ldots,G_{k}\\};\qquad
f\mapsto\left(\begin{smallmatrix}G_{1}&G_{2}&\cdots&G_{k}\\\
f(G_{1})&f(G_{2})&\cdots&f(G_{k})\end{smallmatrix}\right).$

Then, we have

$\\#\operatorname{Aut}(G)_{x}=\\#\operatorname{Im}(t)\cdot\\#\operatorname{Ker}(t)\leq\\#\operatorname{Im}(t)\cdot\\#\operatorname{Aut}(G_{1})_{x}\dotsm\\#\operatorname{Aut}(G_{k})_{x}.$

Hence, by Proposition 6, we have

$\displaystyle\\#\operatorname{Aut}(G)$ $\displaystyle\leq
l\cdot\\#\operatorname{Aut}(G)_{x}$ $\displaystyle\leq
l\cdot\\#\operatorname{Im}(t)\cdot(2^{g_{1}}g_{1}!)\dotsm(2^{g_{k}}g_{k}!)$
$\displaystyle=l\cdot\\#\operatorname{Im}(t)\cdot
2^{g}\cdot(g_{1}!)\dotsm(g_{k}!).$

Case 2-1 Suppose that $g_{1}=g_{2}=\cdots=g_{k}$ does not hold.

Since $f\in\operatorname{Aut}(G)$ maps $G_{i}$ to only $G_{j}$ such that
$g_{i}=g_{j}$, we have $\\#\operatorname{Im}(t)\leq(k-1)!$ in this case. Then
we have

$\displaystyle l\cdot\\#\operatorname{Im}(t)\cdot(g_{1}!)\dotsm(g_{k}!)$
$\displaystyle\leq(g-1)(k-1)!(g_{1}!)(g_{2}!)\dotsm(g_{k}!)$
$\displaystyle\leq(g-1)(g-1)!$ $\displaystyle<g!.$

Here the second inequality follows from Lemma 5. Therefore we get the strict
inequality $\\#\operatorname{Aut}(G)<2^{g}g!$ in this case.

Case 2-2 Suppose that $k\geq 3$ and $g_{1}=g_{2}=\cdots=g_{k}$.

Suppose that $x$ is fixed for any $f\in\operatorname{Aut}(G)$. Then
$\operatorname{Aut}(G)=\operatorname{Aut}(G)_{x}$ holds and the assertion
follows from Proposition 6 and Remark 8. Therefore we may assume that
$f(x)\not=x$ for some $f\in\operatorname{Aut}(G)$. We set $x^{\prime}=f(x)$.
Let

$G\setminus\\{x^{\prime}\\}=U^{\prime}_{1}\sqcup\cdots\sqcup
U^{\prime}_{k^{\prime}}$

be the decomposition to the connected components of
$G\setminus\\{x^{\prime}\\}$. Let
$G^{\prime}_{i}=U^{\prime}_{i}\cup\\{x^{\prime}\\}$ be the subgraph of $G$,
and let $g^{\prime}_{i}$ be its Betti number. Since the automorphism $f$ maps
$x$ to $x^{\prime}$, $k^{\prime}$ must be $k$ and $g^{\prime}_{i}=\frac{g}{k}$
holds for each $i$. We may assume that $x^{\prime}\in V_{G_{1}}$. Suppose
$x\in V_{G^{\prime}_{i}}$. Then $G_{2},\ldots,G_{k}$ are subgraphs of
$G^{\prime}_{i}$. Therefore it follows that

$\frac{k-1}{k}g=g_{2}+\cdots+g_{k}\leq g^{\prime}_{i}=\frac{g}{k},$

and contradicts the assumption $k\geq 3$.

Case 2-3 Suppose that $k=2$ and $g_{1}=g_{2}$.

Let $g^{\prime}:=g_{1}=g_{2}$. Since $l\leq g-1=2g^{\prime}-1$, we have

$l\cdot\\#\operatorname{Im}(t)\cdot(g^{\prime}!)^{2}\leq(2g^{\prime}-1)\cdot
2\cdot(g^{\prime}!)^{2}\leq(2g^{\prime})!=g!,$

which proves the desired inequality $\\#\operatorname{Aut}(G)\leq 2^{g}g!$. We
note that the equality $\\#\operatorname{Aut}(G)=2^{g}g!$ holds only if
$g^{\prime}$ and $l$ satisfy

$l=2g^{\prime}-1,\quad(2g^{\prime}-1)\cdot
2\cdot(g^{\prime}!)^{2}=(2g^{\prime})!.$

Since $2g^{\prime}=g\geq 3$, we have $(g^{\prime},g,d,l)=(2,4,4,3)$. We note
that such $G$ has no vertices of degree three by the hand-shaking lemma.
Therefore, in this case, $G$ turns out to be a subdivision of the graph $H$ in
Figure 3. Hence we have
$\\#\operatorname{Aut}(G)\leq\\#\operatorname{Aut}(H)=2^{5}<2^{g}g!$, and the
equality $\\#\operatorname{Aut}(G)=2^{g}g!$ never holds in this case. ∎

Figure 3. We call the graph $H$. Black dots (resp. lines) stand for vertices
(resp. edges).

Finally, we shall prove Theorem 1.

###### Proof of Theorem 1.

Let $V$ be the set of all points of $\varGamma$ except two valent points. We
add to $V$ all midpoints of loops. Let $(G,l)$ be the pair defining
$\varGamma$ that has the added set $V$ as its set of vertices. Each
$f\in\operatorname{Aut}(\varGamma)$ induces a permutation of the subset of
$\varGamma$ corresponding to $V_{G}$ and that of the set of intervals of
$\varGamma$ corresponding to edges of $G$. This induces a group homomorphism
$\operatorname{Aut}(\varGamma)\to\operatorname{Aut}(G)$. Since $G$ is
loopless, it is injective. Then we have

$\\#\operatorname{Aut}(\varGamma)\leq\\#\operatorname{Aut}(G).$

By Proposition 2, we have the desired inequality.

In each case of equality conditions of Theorem 1, clearly, the inequality
becomes an equality. The converse follows from Proposition 2 and the fact that
each $f\in\operatorname{Aut}(\varGamma)$ is an isometry
$\varGamma\to\varGamma$. ∎

## References

  * [1] Omid Amini, Matthew Baker, Erwan Brugallé and Joseph Rabinoff, Lifting harmonic morphisms II: Tropical curves and metrized complexes, Algebra & Number Theory 9 (2015), no. 2, 267–315.
  * [2] Mehdi Behzad, Gary Chartrand and Linda Lesniak-Foster, Graphs & digraphs, PWS Publishers, Boston, Mass., 1979.
  * [3] Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52. Springer-Verlag, New York-Heidelberg, 1977.
  * [4] Song JuAe, Generators of invariant linear system on tropical curves for finite isometry group, Hokkaido Math. j. 50 (2021), no. 1, 55–76.
  * [5] Diane Maclagan and Bernd Sturmfels, Introduction to tropical geometry, Vol. 161. American Mathematical Soc., Providence, RI, 2015.
  * [6] Yuto Yamamoto, Tropical contractions to integral affine manifolds with singularities, available at arXiv: 2105.10141.