# On error bounds and optimality conditions at infinity

NGUYEN VAN TUYEN1 1Department of Mathematics, Hanoi Pedagogical University 2,
Xuan Hoa, Phuc Yen, Vinh Phuc, Vietnam<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

In this paper, we establish sufficient conditions for the existence of error
bounds at infinity for lower semicontinuous inequality systems. We also show
that the existence of an error bound at infinity of constraint systems plays
an important role in deriving necessary optimality conditions at infinity for
constrained optimization problems.

###### Key words and phrases:

Error bound at infinity, Limiting subdifferential at infinity, Normal cone at
infinity, Optimality conditions at infinity

###### 1991 Mathematics Subject Classification:

49K40, 90C26, 49J52, 90C46

Dedicated to Professor Do Sang Kim on the occasion of his 70th birthday

##  1\. Introduction

Consider the inequality system

$S:=\\{x\in\Omega\subset X\;:\;g(x)\leq 0\\}$ (1)

where $X$ is a Banach space, $\Omega$ is a nonempty and closed subset in $X$,
and $g\colon X\to\overline{\mathbb{R}}$ is a lower semicontinuous function.

We say that $S$ has a local error bound at a point $\bar{x}\in S$ if there
$\tau>0$ and a neighborhood $V$ of $\bar{x}$ such that

$d(x;S)\leq\tau[g(x)]_{+}\ \ \forall x\in\Omega\cap V,$ (2)

where $d(x;S)$ denotes the distance from $x$ to $S$ and
$[g(x)]_{+}:=\max\\{g(x),0\\}$. If we can choose $V=X$ in (2), then we say
that $S$ has a global/Hoffman error bound.

The concept of error bound plays a center role in many fields of mathematical
programming theory including, for example, in analyzing the convergence of
algorithms, in studying optimality conditions, stability, sensitivity,
subdifferential calculus, and so on. Today, the literature on error bounds is
rich and there are many conditions that ensure the existence of error bounds,
see, for example [1, 3, 6, 7, 8, 9, 10, 12, 13, 14, 17, 18, 20, 23, 24, 27,
28].

To the best of our knowledge, the first result on global error bounds was
established by Hoffman [8]. The author proved that if $g$ is a maximum of a
finite number of affine functions in $\mathbb{R}^{n}$, then $S$ has a global
error bound. In [24], Robinson extended the Hoffman’s result to bounded convex
differentiable inequality systems in infinite dimensional spaces. The
existence of global error bound for unbounded convex inequality systems in
reflexive Banach spaces was studied by Deng [2]. In [9], Ioffe presented a
sufficient condition for the existence of a local error bound for nonconvex
and nondifferentiable Lipschitz continuous equality system in infinite
dimension. The relationship between the existence of local error bounds and
Abadie constraint qualification conditions for convex inequality systems can
be found in [10, 17, 18, 27, 28]. Regarding to the existence of Hölder error
bounds, we refer the readers to references [3, 6, 12, 14, 20, 26].

In mathematical programming, there are numerous problems where the objective
function is bounded from below but nevertheless fails to attain its minimum at
any finite feasible solution; see, for example, [4]. When this happens, the
Fermat’s rule cannot be applied. However, there exists a sequence of feasible
solutions tending to infinity such that the corresponding sequence of
objective values tends to its infimum. Therefore, optimality conditions in
this case must somehow be taken “at infinity”. To do this, very recently,
Nguyen and Pham [19] introduced the notions of Clarke’s tangent, normal cones,
subgradients, Lipschitz continuity, …, at infinity and established necessary
optimality conditions at infinity. Thereafter, Kim, Nguyen and Pham [11]
proposed the concepts of limiting normal cones at infinity to unbounded sets
as well as limiting and singular subdifferentials at infinity and then they
derived necessary optimality conditions as well as sufficient conditions for
the weak sharp minima property at infinity. To obtain necessary optimality
conditions at infinity, the authors used a constraint qualification of
Mangasarian–Fromovitz type at infinity for Lipschitz at infinity functions. We
note here that both assumptions on the Lipschitzness and the
Mangasarian–Fromovitz constraint qualification at infinity are rather strict.

To the best of our knowledge, so far there have been no papers studying the
concept of error bound at infinity. In this paper, we introduce the concept of
error bound at infinity for general constraint systems and derive sufficient
conditions for such ones have an error bound at infinity. Then we show that
the existence of an error bound at infinity is essential to derive upper
estimate for the normal cone at infinity of constraint systems. As a
byproduct, we obtain new necessary optimality conditions at infinity for
problems which do not attain its minimum.

The rest of the paper is organized as follows. Section 2 contains some
definitions and preliminary results from variational analysis and generalized
differentiation. In Section 3, we derive sufficient conditions for error
bounds at infinity. Section 4 is devoted to upper estimates of the normal cone
of constraint systems and optimality conditions at infinity.

##  2\. Preliminaries

In this section, we recall some notions related to generalized differentiation
from [11, 15, 16, 21, 25]. The space $\mathbb{R}^{n}$ is equipped with the
usual scalar product $\langle\cdot,\cdot\rangle$ and the corresponding
Euclidean norm $\|\cdot\|$. The closed unit ball and the nonnegative orthant
in $\mathbb{R}^{n}$ are denoted, respectively, by $\mathbb{B}$ and
$\mathbb{R}^{n}_{+}$. The convex hull of a set $D\subset\mathbb{R}^{n}$ and
the Euclidean projector of a point $x\in\mathbb{R}^{n}$ to $D$ are denoted,
respectively, by $\mathrm{co}\,D$ and $\Pi_{D}(x)$. As usual, we denote
$[\alpha]_{+}:=\max\,\\{\alpha,0\\}$ for any $\alpha\in\mathbb{R}$,
$\overline{\mathbb{R}}:=\mathbb{R}\cup\\{\infty\\}$, and $d(x;D)$ is the
distance of a point $x\in\mathbb{R}^{n}$ to $D$, that is,

$d(x;D):=\inf\\{\|y-x\|\;:\;y\in D\\}.$

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ be a set-valued mapping.
The domain and the graph of $F$ are given, respectively, by

${\rm dom}\,F=\\{x\in\mathbb{R}^{n}\mid F(x)\not=\emptyset\\}$

and

${\rm gph}\,F=\\{(x,y)\in\mathbb{R}^{n}\times\mathbb{R}^{m}\mid y\in F(x)\\}.$

The set-valued mapping is called $F$ proper if $\mbox{\rm
dom}\,F\not=\emptyset.$ The Painlevé-Kuratowski outer/upper limit of $F$ at
$\bar{x}$ is defined by

$\displaystyle\mathop{{\rm Lim}\,{\rm
sup}}\limits_{x\rightarrow\bar{x}}F(x):=\bigg{\\{}y\in\mathbb{R}^{m}\mid\exists
x_{k}\rightarrow\bar{x},y_{k}\rightarrow y\ \mbox{with}\ y_{k}\in
F(x_{k}),\forall k=1,2,....\bigg{\\}}.$

###  2.1. Normal cones and Subdifferentials

######  Definition 2.1 (see [15, 16]).

Let $\Omega$ be a nonempty subset of $\mathbb{R}^{n}$ and $\bar{x}\in\Omega$.

  1. (i)

The regular/Fréchet normal cone to $\Omega$ at $\bar{x}$ is defined by

$\displaystyle\widehat{N}(\bar{x};\Omega)=\left\\{v\in\mathbb{R}^{n}\mid\limsup\limits_{x\xrightarrow{\Omega}\bar{x}}\dfrac{\langle
v,x-\bar{x}\rangle}{\|x-\bar{x}\|}\leq 0\right\\},$

where $x\xrightarrow{\Omega}\bar{x}$ means that $x\rightarrow\bar{x}$ and
$x\in\Omega$.

  2. (ii)

The limiting/Mordukhovich normal cone to $\Omega$ at $\bar{x}$ is given by

$\displaystyle N(\bar{x};\Omega)=\mathop{{\rm Lim}\,{\rm
sup}}\limits_{x\xrightarrow{\Omega}\bar{x}}\widehat{N}(x;\Omega).$

When $\bar{x}\not\in\Omega$, we put
$\widehat{N}(\bar{x};\Omega)=N(\bar{x};\Omega)=\emptyset$.

By definition, it is clear that

$\displaystyle\widehat{N}(x;\Omega)\subset N(x;\Omega),\ \ \ \forall
x\in\Omega.$

Let $f:\mathbb{R}^{n}\rightarrow\overline{\mathbb{R}}$ be an extend real-
valued function. The effective domain and the epigraph of $f$ are denoted,
respectively, by

$\mbox{dom}\,f:=\\{x\in\mathbb{R}^{n}\mid f(x)<+\infty\\}$

and

${\rm{epi}}\,f:=\\{(x,\alpha)\in\mathbb{R}^{n}\times\mathbb{R}\mid\alpha\geq
f(x)\\}.$

We say that $f$ is proper if its $\mathrm{dom}f$ is nonempty.

######  Definition 2.2 (see [15, 16]).

Consider a function $f\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ and a
point $\bar{x}\in{\rm dom}f$.

  1. (i)

The regular/Fréchet subdifferential of $f$ at $\bar{x}$ is defined by

$\widehat{\partial}f(\bar{x}):=\\{v\in\mathbb{R}^{n}\mid(v,-1)\in\widehat{N}((\bar{x},f(\bar{x}));\mathrm{epi}f)\\}.$

  2. (ii)

The limiting/Mordukovich subdifferential and the limiting/Mordukovich singular
subdifferential of $f$ at $\bar{x}$ are defined, respectively, by

$\partial
f(\bar{x}):=\\{v\in\mathbb{R}^{n}\mid(v,-1)\in{N}((\bar{x},f(\bar{x}));\mathrm{epi}f)\\},$

and

$\partial^{\infty}f(\bar{x}):=\\{v\in\mathbb{R}^{n}\mid\exists
v_{k}\in\widehat{\partial}f(\bar{x}),\lambda_{k}\downarrow
0,\lambda_{k}v_{k}\to v\\}.$

It is well-known that

$\partial f(\bar{x})=\mathop{{\rm Lim}\,{\rm
sup}}_{x\xrightarrow{f}\bar{x}}\widehat{\partial}f(x)\supseteq\widehat{\partial}f(x),$

where $x\xrightarrow{f}\bar{x}$ means that $x\to\bar{x}$ and $f(x)\to
f(\bar{x})$. When the function $f$ is convex, then the subdifferentials
$\widehat{\partial}f(\bar{x})$ and $\partial f(\bar{x})$ coincide with the
subdifferential in the sense of convex analysis.

For the singular subdifferential, we have

$\displaystyle\partial^{\infty}f(\bar{x})\subseteq\\{v\in\mathbb{R}^{n}\mid(v,0)\in
N((\bar{x},f(\bar{x}));\mathrm{epi}f)\\},$

and the inclusion holds with equality whenever $f$ is locally lower
semicontinuous (l.s.c.) at $\bar{x}$; see [25, Theorem 8.9].

Let $\Omega\subset\mathbb{R}^{n}$. The indicator function
$\delta_{\Omega}\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ of $\Omega$ is
defined by

$\delta_{\Omega}(x):=\begin{cases}0&\textrm{ if }x\in\Omega,\\\
+\infty&\textrm{ otherwise.}\end{cases}$

It holds that
$\partial\delta_{\Omega}(x)=\partial^{\infty}\delta_{\Omega}(x)=N(x;\Omega)$
for any $x\in\Omega$; see [15, 16, 25].

The following result is the nonsmooth versions of Fermat’s rule.

######  Lemma 2.1 (see [15, Proposition 1.114]).

If a proper function $f\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ has a
local minimum at $\bar{x},$ then
$0\in\widehat{\partial}f(\bar{x})\subset\partial f(\bar{x}).$

The next result gives sum rules for limiting and singular subgradients of
extended-real-valued functions.

######  Lemma 2.2 (see [15, Theorem 3.36]).

Let $f_{i}\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$, $i=1,\ldots,m$,
$m\geqq 2$, be l.s.c. around $\bar{x}$ and let all but one of these functions
be locally Lipschitz around $\bar{x}$. Then we have the following inclusions

$\displaystyle\partial(f_{1}+\ldots+f_{m})(\bar{x})\subset\partial
f_{1}(\bar{x})+\ldots+\partial f_{m}(\bar{x}),$
$\displaystyle\partial^{\infty}(f_{1}+\ldots+f_{m})(\bar{x})\subset\partial^{\infty}f_{1}(\bar{x})+\ldots+\partial^{\infty}f_{m}(\bar{x}).$

We now recall the Ekeland variational principle (see [5]).

######  Lemma 2.3 (Ekeland variational principle).

Let $f\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be a proper l.s.c.
function and bounded from below. Let $\epsilon>0$ and $x_{0}\in\mathbb{R}^{n}$
be satisfied

$\displaystyle f(x_{0})$ $\displaystyle\leq$
$\displaystyle\inf_{x\in\mathbb{R}^{n}}f(x)+\epsilon.$

Then, for any $\lambda>0$ there exists $x_{1}\in\mathbb{R}^{n}$ such that

  1. (i)

$f(x_{1})\leq f(x_{0}),$

  2. (ii)

$\|x_{1}-x_{0}\|\leq\lambda,$ and

  3. (iii)

$f(x_{1})\leq f(x)+\dfrac{\epsilon}{\lambda}\|x-x_{1}\|$ for all
$x\in\mathbb{R}^{n}.$

###  2.2. Normal cones and subdifferentials at infinity

Let $\Omega$ be a locally closed subset of $\mathbb{R}^{n}$, i.e., for any
$x\in\Omega$ there is a neighborhood $U$ of $x$ such that $\Omega\cap U$ is
closed. Assume that $\Omega$ is unbounded.

######  Definition 2.3 (see [11]).

The norm cone to the set $\Omega$ at infinity is defined by

$\displaystyle N(\infty;\Omega)$ $\displaystyle:=$ $\displaystyle\mathop{{\rm
Lim}\,{\rm sup}}_{x\xrightarrow{\Omega}\infty}\widehat{N}(x;\Omega).$

The following result is the intersection rule for normals at infinity.

######  Proposition 2.1 (see [11, Proposition 3.7]).

Let $\Omega_{1},\Omega_{2}$ be locally closed subsets of $\mathbb{R}^{n}$
satisfying the normal qualification condition at infinity

$\displaystyle N(\infty;\Omega_{1})\cap\big{(}-N(\infty;\Omega_{2})\big{)}$
$\displaystyle=$ $\displaystyle\\{0\\}.$

Then we have the inclusion

$\displaystyle N(\infty;\Omega_{1}\cap\Omega_{2})$ $\displaystyle\subset$
$\displaystyle N(\infty;\Omega_{1})+N(\infty;\Omega_{2}).$

Now let $f\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be a l.s.c. function
and assume that $f$ is proper at infinity in the sense that the set
$\mathrm{dom}f$ is unbounded.

######  Definition 2.4 (see [11]).

The limiting/Mordukhovich and the singular subdifferentials of $f$ at infinity
are defined, respectively, by

$\displaystyle\partial f(\infty)$ $\displaystyle:=$
$\displaystyle\\{u\in\mathbb{R}^{n}\ |\ (u,-1)\in\mathcal{N}\\},$
$\displaystyle\partial^{\infty}f(\infty)$ $\displaystyle:=$
$\displaystyle\\{u\in\mathbb{R}^{n}\ |\ (u,0)\in\mathcal{N}\\},$

where $\mathcal{N}:=\displaystyle\mathop{{\rm Lim}\,{\rm
sup}}_{x\to\infty}{N}((x,f(x));\textrm{epi}f).$

The following result gives limiting representations of limiting and singular
subgradients at infinity.

######  Proposition 2.2 (see [11, Proposition 4.4]).

The following relationships hold

$\displaystyle\partial f(\infty)$ $\displaystyle=\mathop{{\rm Lim}\,{\rm
sup}}_{x\to\infty}\partial f(x)=\mathop{{\rm Lim}\,{\rm
sup}}_{x\to\infty}\widehat{\partial}f(x),$
$\displaystyle\partial^{\infty}f(\infty)$ $\displaystyle=\mathop{{\rm
Lim}\,{\rm sup}}_{x\to\infty,r\downarrow 0}r\partial f(x)\supseteq\mathop{{\rm
Lim}\,{\rm sup}}_{x\to\infty}\partial^{\infty}f(x).$

######  Remark 2.1.

Let $\Omega$ be an unbounded and closed subset of $\mathbb{R}^{n}$. Then it
follows from Proposition 2.2 and [16, Proposition 1.19] that

$\partial\delta_{\Omega}(\infty)=\partial^{\infty}\delta_{\Omega}(\infty)=N(\infty;\Omega).$

We now recall the notion of the Lipschitz property at infinity for l.s.c.
functions (see [11, 19]).

######  Definition 2.5.

Let $f\colon\mathbb{R}^{n}\to\mathbb{R}$ be a l.s.c function. We say that $f$
is Lipschitz at infinity if there exist constants $L>0$ and $R>0$ such that

$\displaystyle|f(x)-f(x^{\prime})|$ $\displaystyle\leq$ $\displaystyle
L\|x-x^{\prime}\|\ \ \textrm{ for all }\ \
x,x^{\prime}\in\mathbb{R}^{n}\setminus\mathbb{B}_{R}.$

The following result gives a necessary and sufficient condition for the
Lipschitz property at infinity of l.s.c. functions.

######  Proposition 2.3 (see [11, Proposition 5.2]).

Let $f\colon\mathbb{R}^{n}\to\mathbb{R}$ be a l.s.c. function. Then $f$ is
Lipschitz at infinity if and only if $\partial^{\infty}f(\infty)=\\{0\\}.$ In
this case, $\partial f(\infty)$ is nonempty compact.

The next results present calculus rules for both basic and singular
subdifferentials at infinity. These results obtained from [11] by induction.

######  Proposition 2.4 (cf. [11, Proposition 4.9]).

Let $f_{1},\ldots,f_{m}\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be l.s.c.
functions such that the following qualification condition holds

$\left[u_{1}+\ldots+u_{m}=0,u_{i}\in\partial^{\infty}f_{i}(\infty)\right]\Rightarrow
u_{i}=0,i=1,\ldots,m,$ (3)

Then we have

$\displaystyle\partial(f_{1}+\ldots+f_{m})(\infty)$ $\displaystyle\subset$
$\displaystyle\partial f_{1}(\infty)+\ldots+\partial f_{m}(\infty),$
$\displaystyle\partial^{\infty}(f_{1}+\ldots+f_{m})(\infty)$
$\displaystyle\subset$
$\displaystyle\partial^{\infty}f_{1}(\infty)+\ldots+\partial^{\infty}f_{m}(\infty).$

######  Proposition 2.5 (cf. [11, Proposition 4.11]).

Let $f_{1},\ldots,f_{m}\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be l.s.c.
functions such that the qualification condition (3) is satisfied. Then one has
the inclusions

$\displaystyle\partial(\max\\{f_{1},\ldots,f_{m}\\})(\infty)$
$\displaystyle\subset$
$\displaystyle\bigcup\left\\{\sum_{i=1}^{m}\lambda_{i}\circ\partial
f_{i}(\infty)\;:\;\lambda\in\Delta_{m}\right\\},$
$\displaystyle\partial^{\infty}(\max\\{f_{1},\ldots,f_{m}\\})(\infty)$
$\displaystyle\subset$
$\displaystyle\sum_{i=1}^{m}\partial^{\infty}f_{i}(\infty),$

where
$\Delta_{m}:=\\{\lambda\in\mathbb{R}^{m}_{+}\;:\;\sum_{i=1}^{m}\lambda_{i}=1\\}$
and $\lambda_{i}\circ\partial f_{i}(\infty)$, $i=1,\ldots,m$, are defined as
follow

$\lambda_{i}\circ\partial f_{i}(\infty)=\begin{cases}\lambda_{i}\partial
f_{i}(\infty)\ \ &\text{if}\ \ \lambda_{i}>0,\\\
\partial^{\infty}f_{i}(\infty)\ \ &\text{if}\ \ \lambda_{i}=0.\end{cases}$

######  Remark 2.2.

By Proposition 2.3, the qualification condition (3) holds if all but one of
functions $f_{1},\ldots,f_{m}$ are Lipschitz at infinity.

######  Proposition 2.6 (cf. [11, Proposition 4.12]).

Let $f_{1},\ldots,f_{m}\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be l.s.c.
functions. Then we have

$\partial(\min\\{f_{1},\ldots,f_{m}\\})(\infty)\subset\bigcup\\{\partial
f_{i}(\infty)\;:\;i=1,\ldots,m\\}.$

##  3\. Sufficient conditions for error bounds at infinity

Let $\Omega$ be a nonempty and closed subset in $\mathbb{R}^{n}$ and
$g\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be a l.s.c. function. Consider
the constraint set

$S:=\\{x\in\Omega\;:\;g(x)\leq 0\\}.$ (4)

Assume that $\Omega\cap\mbox{\rm dom}\,g$ is nonempty and unbounded.

Our main purpose in this section is to derive sufficient conditions for the
existence of error bounds at infinity for the constraint set $S$ in (4).

######  Definition 3.1.

We say that the constraint set $S$ has an error bound at infinity if there
exist $\alpha>0$ and $R>0$ such that

$d(x;S)\leq\alpha[g(x)]_{+}$

for all $x\in\Omega$ with $\|x\|>R$.

######  Theorem 3.1.

Assume that

$\partial^{\infty}g(\infty)\cap(-N(\infty;\Omega))=\\{0\\}$ (5)

and

$0\notin\partial g(\infty)+N(\infty;\Omega).$ (6)

Then the constraint set $S$ in (4) has an error bound at infinity.

###### Proof.

Suppose on the contrary that $S$ has no error bound at infinity. Then, for
each $k\in\mathbb{N}$, there exists $x_{k}\in\Omega$ such that
$\|x_{k}\|\to\infty$ as $k\to\infty$ and

$d(x_{k};S)>k^{2}[g(x_{k})]_{+}.$ (7)

This implies that $x_{k}\notin S$ for all $k\in\mathbb{N}$. Hence,
$\epsilon_{k}:=[g(x_{k})]_{+}=g(x_{k})>0$ and

$[g(x_{k})]_{+}\leq\inf_{y\in\Omega}[g(y)]_{+}+\epsilon_{k}$

for all $k\in\mathbb{N}$. By the closedness of $\Omega$ and the Ekeland
variational principle (see Lemma 2.3), for each $k\in\mathbb{N}$ and
$\lambda_{k}=k\epsilon_{k}>0$, there exists $y_{k}\in\Omega$ such that

$\displaystyle\|y_{k}-x_{k}\|\leq\lambda_{k},$ (8)
$\displaystyle[g(y_{k})]_{+}\leq[g(y)]_{+}+\frac{1}{k}\|y-y_{k}\|\ \ \text{for
all}\ \ y\in\Omega.$ (9)

It follows from (7) that

$\lambda_{k}<\frac{1}{k}d(x_{k};S)\leq d(x_{k};S).$ (10)

This implies that $y_{k}\notin S$ and so $g(y_{k})>0$. Indeed, if otherwise,
then

$\|y_{k}-x_{k}\|\geq d(x_{k};S)>\lambda_{k},$

a contradiction. Now fixed $\bar{x}\in S$, then by (8) and (10), one has

$\displaystyle\|y_{k}\|\geq\|x_{k}\|-\|y_{k}-x_{k}\|\geq\|x_{k}\|-\lambda_{k}$
$\displaystyle>\|x_{k}\|-\frac{1}{k}d(x_{k};S)$
$\displaystyle\geq\|x_{k}\|-\frac{1}{k}\|x_{k}-\bar{x}\|$
$\displaystyle=\|x_{k}\|\left(1-\frac{1}{k}\left\|\frac{x_{k}}{\|x_{k}\|}-\frac{\bar{x}}{\|x_{k}\|}\right\|\right)$

and so $\|y_{k}\|\to\infty$ as $k\to\infty$. On the other hand, by (9) $y_{k}$
is a global minimizer of the l.s.c. function
$[g(\cdot)]_{+}+\delta_{\Omega}(\cdot)+\frac{1}{k}\|\cdot-y_{k}\|$ on
$\mathbb{R}^{n}$. By the l.s.c. property of $g$ and the fact that $g(y_{k})>0$
there exists a neighborhood of $y_{k}$ on which we have

$[g(\cdot)]_{+}+\delta_{\Omega}(\cdot)+\frac{1}{k}\|\cdot-
y_{k}\|=g(\cdot)+\delta_{\Omega}(\cdot)+\frac{\epsilon_{k}}{\lambda_{k}}\|\cdot-
y_{k}\|.$

By Fermat rule (Lemma 2.1), we obtain

$0\in\partial\left(g(\cdot)+\delta_{\Omega}(\cdot)+\frac{1}{k}\|\cdot-
y_{k}\|\right)(y_{k}).$

By the Lipschitz property of the function $\|\cdot-y_{k}\|$ and the sum rule
(Lemma 2.2), one gets

$0\in\partial(g(\cdot)+\delta_{\Omega}(\cdot))(y_{k})+\frac{1}{k}\partial(\|\cdot-
y_{k}\|)(y_{k}).$ (11)

We now show that condition (5) implies that there exists $R>0$ such that

$\partial^{\infty}g(x)\cap(-N(x;\Omega))=\\{0\\}\ \ \text{when}\ \ \|x\|>R.$
(12)

Indeed, if otherwise, there exist sequences $z_{k}\in\mathbb{R}^{n}$ and
$u_{k}\in\partial^{\infty}g(z_{k})\cap(-N(z_{k};\Omega))$ such that
$\|z_{k}\|\to\infty$ and $u_{k}\neq 0$ for all $k\in\mathbb{N}$. Clearly,

$\frac{u_{k}}{\|u_{k}\|}\in\partial^{\infty}g(z_{k})\cap(-N(z_{k};\Omega)).$

By passing to a subsequence if necessary we may assume that
$\frac{u_{k}}{\|u_{k}\|}$ converges to some $u$ with $\|u\|=1$. Thus, by
Proposition 2.2 we get
$u\in\partial^{\infty}g(\infty)\cap(-N(\infty;\Omega))$, a contradiction.

By (12), (11) and the sum rule, we have

$0\in\partial
g(y_{k})+\partial\delta_{\Omega}(y_{k})+\frac{1}{k}\partial(\|\cdot-
y_{k}\|)(y_{k}).$ (13)

We note here that $\partial\delta_{\Omega}(y_{k})=N(y_{k};\Omega)$ and
$\partial(\|\cdot-y_{k}\|)(y_{k})=\mathbb{B}$. Thus (13) means that

$0\in\partial g(y_{k})+N(y_{k};\Omega)+\frac{1}{k}\mathbb{B}.$

Hence, for each $k\in\mathbb{N}$ there exist $u_{k}\in\partial g(y_{k})$ and
$v_{k}\in N(y_{k};\Omega)$ such that

$\|u_{k}+v_{k}\|\leq\frac{1}{k}$ (14)

and so $\lim_{k\to\infty}(u_{k}+v_{k})=0$.

We have the following two cases.

Case 1. The sequence $u_{k}$ is bounded. Then by (14), the sequence $v_{k}$ is
also bounded. By passing to a subsequence if necessary we may assume that
$u_{k}\to u$ and $v_{k}\to v$ as $k\to\infty$. Thus we arrive at

$u\in\partial g(\infty),v\in N(\infty;\Omega)\ \ \text{and}\ \ u+v=0,$

which contradicts (6).

Case 2. The sequence $u_{k}$ is unbounded. By passing to a subsequence if
necessary we may assume that $u_{k}\to\infty$ as $k\to\infty$ and so is
$v_{k}$. Furthermore, by (14) we have

$\|v_{k}\|\leq\|u_{k}+v_{k}\|+\|u_{k}\|\leq\frac{1}{k}+\|u_{k}\|.$

Hence,

$\frac{\|v_{k}\|}{\|u_{k}\|}\leq 1+\frac{1}{k\|u_{k}\|}.$

This implies that the sequence $\frac{v_{k}}{\|u_{k}\|}$ is bounded and
$\frac{v_{k}}{\|u_{k}\|}\in N(y_{k};\Omega)$ for all $k\in\mathbb{N}$. Hence,
by passing to a subsequence if necessary we may assume that
$\frac{u_{k}}{\|u_{k}\|}\to u$ and $\frac{v_{k}}{\|u_{k}\|}\to v$ as
$k\to\infty$. By Proposition 2.2, $u\in\partial^{\infty}g(\infty)$. Clearly,
$u\neq 0$, $v\in N(\infty;\Omega)$ and $u+v=0$, which contradicts (5). The
proof is complete. ∎

######  Remark 3.1.

By Proposition 2.3, the condition (5) holds automatically when $g$ is
Lipschitz at infinity or $\Omega=\mathbb{R}^{n}$.

The following simple example is to illustrate Theorem 3.1.

######  Example 3.1.

Consider the constraint (4) with $\Omega=\mathbb{R}^{2}$, $g(x,y)=x^{2}+y^{2}$
for all $(x,y)\in\mathbb{R}^{2}$. Then $S=\\{(0,0)\\}$. It is easy to see that
$\partial g(\infty)=\emptyset$. Hence, by Theorem 3.1, $S$ has an error bound
at infinity. However, we can check that $S$ has no error bound of Hoffman’s
type, that is, there exists $\tau>0$ such that

$d((x,y);S)\leq\tau[g(x,y)]_{+}\ \ \forall(x,y)\in\mathbb{R}^{2};$ (15)

see, for example, [8, 14, 17]. Indeed, if otherwise, let
$(x_{k},y_{k})=(0,\frac{1}{k})$. Then by (15), we obtain

$\frac{1}{k}\leq\tau\frac{1}{k^{2}}\ \ \forall k\in\mathbb{N},$

a contradiction.

We now apply Theorem 3.1 to constraint systems described not by a single
inequality but possibly by finitely many inequalities.

######  Theorem 3.2.

Let $S$ be a constraint set defined by

$S:=\\{x\in\Omega\;:\;g_{i}(x)\leq 0,i=1,\ldots,m\\}$ (16)

where $g_{i}\colon\mathbb{R}^{n}\to\mathbb{R}$, $i\in I:=\\{1,\ldots,m\\}$,
are l.s.c. functions, $\Omega$ is an unbounded closed subset in
$\mathbb{R}^{n}$ such that $\Omega\cap(\cap_{i\in I}\,\mbox{\rm
dom}\,\,g_{i})$ is unbounded. If the following conditions hold

$\left[u_{1}+\ldots+u_{m}+v=0,u_{i}\in\partial^{\infty}g_{i}(\infty),v\in
N(\infty;\Omega)\right]\Rightarrow u_{i}=v=0\ \ \forall i\in I,$ (17)

and

$\nexists\lambda\in\Delta_{m}\ \ \text{such that}\ \
0\in\sum_{i=1}^{m}\lambda_{i}\circ\partial g_{i}(\infty)+N(\infty;\Omega)$
(18)

then $S$ has an error bound at infinity, i.e., there exist $\alpha>0$ and
$R>0$ such that

$d(x;S)\leq\alpha\sum_{i=1}^{m}[g_{i}(x)]_{+}\ \ \forall x\in\Omega\ \
\text{with}\ \ \|x\|>R.$ (19)

###### Proof.

Let $g$ be the maximum function defined by $g(x):=\max\,\\{g_{i}(x)\;:\;i\in
I\\}$. Then

$S=\\{x\in\Omega\;:\;g(x)\leq 0\\}.$

It follows from (17) that

$\left[u_{1}+\ldots+u_{m}=0,u_{i}\in\partial^{\infty}g_{i}(\infty)\right]\Rightarrow
u_{i}=0\ \ \forall i\in I.$

By Proposition 2.5, one has

$\partial
g(\infty)\subset\bigcup\left\\{\sum_{i=1}^{m}\lambda_{i}\circ\partial
f_{i}(\infty)\;:\;\lambda\in\Delta_{m}\right\\}$

This and (18) imply that $0\notin\partial g(\infty)+N(\infty;\Omega)$. Thus,
by Theorem 3.1, there exist $\alpha>0$ and $R>0$ such that

$d(x;S)\leq\alpha[g(x)]_{+}\ \ \forall x\in\Omega\ \ \text{with}\ \ \|x\|>R.$
(20)

It is clear that

$[g(x)]_{+}\leq\sum_{i=1}^{m}[g_{i}(x)]_{+}\ \ \forall x\in\mathbb{R}^{n}$

which together with (20) implies (19). The proof is complete. ∎

When $g_{i}$, $i\in I$, are Lipsschitz at infinity, we have the following
result.

######  Theorem 3.3.

Let $S$ be given as in (16), where $\Omega$ is a nonempty and unbounded closed
subset in $\mathbb{R}^{n}$, $g_{i}\colon\mathbb{R}^{n}\to\mathbb{R}$, $i\in
I$, are l.s.c. functions and Lipschitz at infinity. If

$0\notin\mathrm{co}\,\\{\partial g_{i}(\infty)\;:\;i\in I\\}+N(\infty;\Omega)$

then $S$ has an error bound at infinity, i.e., there exist $\alpha>0$ and
$R>0$ such that

$d(x;S)\leq\alpha\sum_{i=1}^{m}[g_{i}(x)]_{+}\ \ \forall x\in\Omega\ \
\text{with}\ \ \|x\|>R.$

###### Proof.

Since $g_{i}$, $i\in I$, are Lipsschitz at infinity, so is for its maxima $g$.
Hence, the condition (5) is satisfied. Then the desired result follows from
Theorem 3.1 and Proposition 2.5. ∎

The next result gives a sufficient condition for the existence of error bound
at infinity for a constraint system described by the pointwise minimum of
finitely many l.s.c. functions.

######  Theorem 3.4.

Let $S$ be given as in (16), where $\Omega$ is a nonempty and unbounded closed
subset in $\mathbb{R}^{n}$, $g_{i}\colon\mathbb{R}^{n}\to\mathbb{R}$, $i\in
I$, are l.s.c. functions and $g(x):=\min\,\\{g_{i}(x)\;:\;i\in I\\}$ for all
$x\in\mathbb{R}^{n}$. Assume that the following condition

$0\notin\bigcup\\{\partial g_{i}(\infty)\;:\;i\in I\\}+N(\infty;\Omega).$ (21)

is satisfied. Then the set $S$ has an error bound at infinity, i.e., there
exist $\alpha>0$ and $R>0$ such that

$d(x;S)\leq\alpha[g(x)]_{+}\ \ \forall x\in\Omega\ \ \text{with}\ \ \|x\|>R.$

###### Proof.

By Proposition 2.6, the condition (21) implies that $0\notin\partial
g(\infty)+N(\infty;\Omega)$. Thus the desired result follows directly from
Theorem 3.1. ∎

##  4\. Optimality conditions at infinity

In this section, by using the existence of error bounds at infinity, we derive
an upper estimate the normal cone at infinity of the constraint set. This
result is instrumental to derive necessary optimality conditions at infinity
for constrained optimization problems that have no solution.

We first derive an upper estimate for the normal cone at infinity of a given
unbounded subset via the subdifferential of the distance function to the set
in question.

######  Proposition 4.1.

Let $S$ be a nonempty, closed and unbounded subset in $\mathbb{R}^{n}$. Then
we have

$N(\infty;S)\subset\mathbb{R}_{+}\partial d(\infty;S).$

###### Proof.

Let $u\in N(\infty;S)$. Clearly, if $u=0$, then $u\in\mathbb{R}_{+}\partial
d(\infty;S)$. If $u\neq 0$, then there exist sequences $x_{k}\in S$ and
$u_{k}\in\widehat{N}(x_{k};S)\setminus\\{0\\}$ such that $x_{k}\to\infty$ and
$u_{k}\to u$ as $k\to\infty$. Clearly,
$\frac{u_{k}}{\|u_{k}\|}\to\frac{u}{\|u\|}$ and by [15, Corollary 1.96] we
have

$\frac{u_{k}}{\|u_{k}\|}\in\widehat{N}(x_{k};S)\cap\mathbb{B}=\widehat{\partial}d(x_{k};S).$

Hence, $\frac{u}{\|u\|}\in\partial d(\infty;S)$ and so
$u\in\mathbb{R}_{+}\partial d(\infty;S)$. The proof is complete. ∎

######  Remark 4.1.

In [15, Theorem 1.97], Mordukhovich showed that

$N(x;S)=\mathbb{R}_{+}\partial d(x;S)\ \ \forall x\in S.$

However, this equality does not hold at infinity. For example, let

$S=\\{x=(x_{1},x_{2})\;:\;x_{1}\in\mathbb{R},x_{2}=x_{1}^{2}\\}.$

Then it is easily to check that $N(\infty;S)=\mathbb{R}\times\\{0\\}$.
Furthermore, by [16, Theorem 1.33], we have

$\partial d(x;S)=\begin{cases}N(x;S)\cap\mathbb{B}\ \ &\text{if}\ \ x\in S,\\\
\frac{x-\Pi_{S}(x)}{d(x;S)}\ \ &\text{otherwise}.\end{cases}$

Thus

$\partial d(\infty;S)=(N(\infty;S)\cap\mathbb{B})\cup\mathop{{\rm Lim}\,{\rm
sup}}_{x\to\infty,\,x\notin S}\frac{x-\Pi_{S}(x)}{d(x;S)}.$

Take $x^{k}=(0,-k)$, $k\in\mathbb{N}$, then

$\lim_{k\to\infty}\frac{x^{k}-\Pi_{S}(x^{k})}{d(x^{k};S)}=(0,-1)\in\partial
d(\infty;S)$

and $(0,-1)\notin N(\infty;S)$.

The following result gives an upper estimate for constraint systems that have
an error bound at infinity.

######  Proposition 4.2.

Let the constraint set $S$ be defined by

$S:=\\{x\in\mathbb{R}^{n}\;:\;g(x)\leq 0\\},$ (22)

where $g\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ is a l.s.c. function.
Assume that $S$ has an error bound at infinity. Then we have

$N(\infty;S)\subset\bigcup\\{\lambda\circ\partial g(\infty)\;:\;\lambda\geq
0\\}.$

If in addition $g$ is Lipschitz at infinity, then

$N(\infty;S)\subset\bigcup\\{\lambda\partial g(\infty)\;:\;\lambda\geq 0\\}.$
(23)

###### Proof.

By assumption, there exist $\alpha>0$ and $R>0$ such that

$d(x;S)\leq\alpha[g(x)]_{+}\ \ \forall
x\in\mathbb{R}^{n}\setminus\mathbb{B}_{R}.$

Put $f(x):=\alpha[g(x)]_{+}$ for all $x\in\mathbb{R}^{n}$. Then the function
$f$ possess the following properties

$\displaystyle f(x)=0\ \ \forall x\in S,$ $\displaystyle d(x,S)\leq f(x)\ \
\forall x\in\mathbb{R}^{n}\setminus\mathbb{B}_{R}.$

Hence, by definition of Fréchet subdiffential and [15, Corollary 1.96], we
have

$\widehat{N}(x;S)\cap\mathbb{B}=\widehat{\partial}d(x,S)\subset\widehat{\partial}f(x)\
\ \forall x\in S\setminus\mathbb{B}_{R}.$

This implies that

$\mathop{{\rm Lim}\,{\rm
sup}}_{x\xrightarrow{S}\infty}[\widehat{N}(x;S)\cap\mathbb{B}]\subset\mathop{{\rm
Lim}\,{\rm sup}}_{x\xrightarrow{S}\infty}\widehat{\partial}f(x)\subset\partial
f(\infty).$

We claim that

$N(\infty;S)\cap\mathbb{B}=\mathop{{\rm Lim}\,{\rm
sup}}_{x\xrightarrow{S}\infty}[\widehat{N}(x;S)\cap\mathbb{B}]$

and so

$N(\infty;S)\cap\mathbb{B}\subset\partial f(\infty).$ (24)

Indeed, it is easy to see that

$\mathop{{\rm Lim}\,{\rm
sup}}_{x\xrightarrow{S}\infty}[\widehat{N}(x;S)\cap\mathbb{B}]\subset
N(\infty;S)\cap\mathbb{B}.$

Now take any $u\in N(\infty;S)\cap\mathbb{B}$. If $u=0$, then
$u\in\mathop{{\rm Lim}\,{\rm
sup}}_{x\xrightarrow{S}\infty}[\widehat{N}(x;S)\cap\mathbb{B}]$. Otherwise,
there exist sequences $x_{k}\in S$, $u_{k}\in\widehat{N}(x_{k};S)$ such that
$x_{k}\to\infty$ and $u_{k}\to u$ as $k\to\infty$. Since $u\in\mathbb{B}$, we
see that

$\frac{\|u\|}{\|u_{k}\|}.u_{k}\in\widehat{N}(x_{k};S)\cap\mathbb{B}\ \
\text{and}\ \ \frac{\|u\|}{\|u_{k}\|}.u_{k}\to u$

and so $u\in\mathop{{\rm Lim}\,{\rm
sup}}_{x\xrightarrow{S}\infty}[\widehat{N}(x;S)\cap\mathbb{B}]$, as required.

We now obtain from (24) and Proposition 2.5 that

$\displaystyle N(\infty;S)=\mathbb{R}_{+}[N(\infty)\cap\mathbb{B}]$
$\displaystyle\subset\mathbb{R}_{+}\partial f(\infty)$
$\displaystyle=\mathbb{R}_{+}\big{[}(0,\alpha]\partial
g(\infty)\cup\partial^{\infty}g(\infty)\big{]}$
$\displaystyle=[\mathbb{R}_{+}\partial
g(\infty)]\cup\partial^{\infty}g(\infty)$
$\displaystyle=\bigcup\\{\lambda\circ\partial g(\infty)\;:\;\lambda\geq 0\\}.$

If $g$ is Lipschitz at infinity, then by Proposition 2.3,
$\partial^{\infty}g(\infty)=0$ and so (23) is valid. The proof is complete. ∎

We now apply the estimate (23) to derive necessary optimality conditions at
infinity for constrained optimization problems. Let
$f\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be a l.s.c. function and let
$S$ be a nonempty and closed subset in $\mathbb{R}^{n}$. Assume that the
following conditions hold:

(A1) $\mbox{\rm dom}\,f\cap S$ is unbounded;

(A2) $f$ in bounded from below on $S$.

Consider the following minimization problem

$\text{minimize}\,f(x)\ \ \text{such that}\ \ x\in S.$ (P)

Let us recall necessary optimality conditions at infinity to problem (P).

######  Theorem 4.1 ([11, Theorem 6.1]).

If $f$ does not attain its infimum on $S$ and the following condition holds

$-\partial^{\infty}f(\infty)\cap N(\infty;S)=\\{0\\},$ (25)

then

$0\in\partial f(\infty)+N(\infty;S).$

The following result gives necessary optimality conditions at infinity to
problem (P) when the constraint set $S$ is given as in (22).

######  Theorem 4.2.

Consider the problem (P) with $S$ defined as in (22). Assume that conditions
(A1), (A2) and the following condition hold

$-\partial^{\infty}f(\infty)\cap\bigg{[}\bigcup\\{\lambda\circ\partial
g(\infty)\;:\;\lambda\geq 0\\}\bigg{]}=\\{0\\}.$ (26)

If $f$ does not attains its infimum on $S$ and $S$ has an error bound at
infinity, then there exists $\lambda\geq 0$ such that

$0\in\partial f(\infty)+\lambda\circ\partial g(\infty).$

If in addition $g$ is Lipschitz at infinity, then there exists $\lambda\geq 0$
such that

$0\in\partial f(\infty)+\lambda\partial g(\infty).$

###### Proof.

By assumptions and Proposition 4.2, we have

$N(\infty;S)\subset\bigcup\\{\lambda\circ\partial g(\infty)\;:\;\lambda\geq
0\\}.$ (27)

This and (26) imply that the condition (25) is satisfied. The desired
conclusions follow from (27) and Theorem 4.1. ∎

######  Remark 4.2.

If $f$ and $g$ are Lipschitz at infinity, then the condition (26) holds
automatically.

The following example is designed to illustrate Theorem 4.2.

######  Example 4.1.

Consider problem (P) with $f(x)=e^{x}+\frac{1}{|x|+1}$, $g(x)=x$ for all
$x\in\mathbb{R}$ and $S=\\{x\in\mathbb{R}\;:\;g(x)\leq 0\\}=\mathbb{R}_{-}$.
Clearly, $g$ is Lipschitz at infinity and $\partial g(\infty)=1$. Hence, by
Theorem 3.1, $S$ has an error bound at infinity. An easy computation shows
that $\partial^{\infty}f(\infty)=\mathbb{R}_{+}$ and so the condition (26) is
satisfied. Furthermore, the function $f$ is bounded from below on $S$ but does
not attain a minimum. Thus there exists $\lambda\geq 0$ such that

$0\in\partial f(\infty)+\lambda\partial g(\infty).$

The following result is deduced from Theorem 4.2 and Proposition 2.5.

######  Corollary 4.1.

Consider the problem (P) with $S$ defined as in (16) with
$\Omega=\mathbb{R}^{n}$. Assume that conditions (A1), (A2), (17) and the
following condition hold

$-\partial^{\infty}f(\infty)\cap\bigg{[}\bigcup\Big{\\{}\sum_{i=1}^{m}\lambda_{i}\circ\partial
g_{i}(\infty)\;:\;\lambda\in\mathbb{R}^{m}_{+}\Big{\\}}\bigg{]}=\\{0\\}.$

If $f$ does not attains its infimum on $S$ and $S$ has an error bound at
infinity, then there exists $\lambda\in\mathbb{R}^{m}_{+}$ such that

$0\in\partial f(\infty)+\sum_{i=1}^{m}\lambda_{i}\circ\partial g_{i}(\infty).$

If in addition $g_{1},\ldots,g_{m}$ are Lipschitz at infinity, then there
exists $\lambda\in\mathbb{R}^{m}_{+}$ such that

$0\in\partial f(\infty)+\sum_{i=1}^{m}\lambda_{i}\partial g_{i}(\infty).$

###### Proof.

Let $g$ be the function defined by
$g(x):=\max\,\\{g_{i}(x)\;:\;i=1,\ldots,m\\}$. Then the desired result follows
from Theorem 4.2 and Proposition 2.5. ∎

## Acknowledgments

A part of this work was done while the author was visiting Department of
Applied Mathematics, Pukyong National University, Busan, Korea in October
2023. The author would like to thank the department for hospitality and
support during their stay.

## References

  * [1] A. A. Auslender and J. -P. Crouzeix, Global regularity theorems, Math. Oper. Res. 13 (1988), 243–253.
  * [2] S. Deng, Computable error bounds for convex inequality systems in reflexive Banach spaces, SIAM J. Optim., 7 (1997), 274–279.
  * [3] S. T. Dinh, H. V. Ha, and T. S. Pham, Hölder-type global error bounds for non-degenerate polynomial systems, Acta. Math. Vietnam, 42 (2017), 563–585.
  * [4] M. Dudík, R. E. Schapire, and M. Telgarsky, Convex analysis at infinity: An introduction to astral space. (2022); https://arxiv.org/abs/2205.03260
  * [5] I. Ekeland, On the variational principle, J. Math. Anal. Appl. 47 (1974), 324–353.
  * [6] H. V. Ha, Global Hölderian error bound for nondegenerate polynomials, SIAM J. Optim. 23 (2013), 917–933.
  * [7] N. T. V. Hang and J. - C. Yao, Sufficient conditions for error bounds of difference functions and applications, J. Glob. Optim. 66 (2016), 439–456.
  * [8] A. J. Hoffman, On approximate solutions of systems of linear inequalities, J. Res. Natl. Bur. Standards 49 (1952), 263–265.
  * [9] A. D. Ioffe, Regular points of Lipschitz functions, Trans. Amer. Math. Soc. 251 (1979), 61–69.
  * [10] A. Jourani, Hoffman’s error bound, local controllability, and sensitivity analysis, SIAM J. Control Optim. 38 (2000), 947–970.
  * [11] D. S. Kim, M. T. Nguyen and T. S. Pham, Subdifferentials at infinity and applications in optimization. (2023); https://doi.org/10.48550/arXiv.2307.15861
  * [12] G. Li, B. S. Mordukhovich, and T. S. Pham, New fractional error bounds for polynomial systems with applications to Hölderian stability in optimization and spectral theory of tensors, Math. Program. 153 (2015), 333–362.
  * [13] G. Li, B. S. Mordukhovich, T. T. A. Nghia, and T. S. Pham, Error bounds for parametric polynomial systems with applications to higher-order stability analysis and convergence rates, Math. Program. 168 (2018), 313–346.
  * [14] X. -D. Luo and Z. -Q. Luo, Extension of Hoffman’s error bound to polynomial systems, SIAM J. Optim., 4 (1994), 383–392.
  * [15] B. S. Mordukhovich, Variational Analysis and Generalized Differentiation, I: Basic Theory; II: Applications, Springer, Berlin, 2006.
  * [16] B. S. Mordukhovich, Variational Analysis and Applications, Springer, New York, 2018.
  * [17] H. V. Ngai and M. Théra, Error bounds for convex differentiable inequality systems in Banach spaces, Math. Program. 104 (2005), 465–482.
  * [18] H. V. Ngai and M. Théra, Error bounds for systems of lower semicontinuous functions in Asplund spaces, Math. Program. 116 (2009), 397–427.
  * [19] M. T. Nguyen and T. S. Pham, Clarke’s tangent cones, subgradients, optimality conditions and the Lipschitzness at infinity. (2022); https://doi.org/10.48550/arXiv.2211.08677
  * [20] J. -S. Pang, Error bounds in mathematical programming, Math. Program., 79 (1997), 299–332.
  * [21] J. -P. Penot: Calculus Without Derivatives, Graduate Texts in Mathematics 266, Springer, New York (2013).
  * [22] T. S. Pham, Optimality conditions for minimizers at infinity in polynomial programming, Math. Oper. Res. 44 (2019), 1381–1395.
  * [23] S. M. Robinson, An application of error bounds for convex programming in a linear space, SIAM J. Control, 13 (1975), 271–273.
  * [24] S. M. Robinson, Generalized equations and their solutions, part I: Basic theory, Math. Program. Study, 10 (1979), 128–141.
  * [25] R. T. Rockafellar and R. J -B. Wets, Variational Analysis, Springer, Berlin, 1998.
  * [26] T. Wang and J. -S. Pang, Global error bound for convex quadratic inequality systems, Optimization 31 (1994), 1–12.
  * [27] Z. Wei, J. -C. Yao, and X. Y. Zheng, Strong Abadie CQ, ACQ, calmness and linear regularity, Math. Program. 145 (2014), 97–131.
  * [28] Z. Wei and J. C. Yao, Study on basic constraint qualification by Mordukhovich subdifferentials and applications, J. Nonlinear Convex Anal. 21 (2020), 953–971.


151112200 LABEL:LastPageFeb. 4, 2022Aug. 30, 2023

# An Axiomatization for the Universal Theory
of the Heisenberg Group

Anthony M. Gaglione  Departmant of Mathematics
U.S. Naval Academy
Annapolis, MD 21402<EMAIL_ADDRESS>and  Dennis Spellman  Department of
Statistics
Temple University
Philadelphia, PA 19122<EMAIL_ADDRESS>This paper is dedicated to the
memory of Benjamin Fine.

###### Abstract.

The Heisenberg group, here denoted $H$, is the group of all $3\times 3$ upper
unitriangular matrices with entries in the ring $\mathbb{Z}$ of integers. A.G.
Myasnikov posed the question of whether or not the universal theory of $H$, in
the language of $H$, is axiomatized, when the models are restricted to
$H$-groups, by the quasi-identities true in $H$ together with the assertion
that the centralizers of noncentral elements be abelian. Based on earlier
published partial results we here give a complete proof of a slightly stronger
result.

###### Key words and phrases:

Noncentral commutative transitivity, quasi-identity, locally
residually-$\mathbb{Z}$, diagram, Lame Property.

###### 1991 Mathematics Subject Classification:

Primary 05C38, 15A15; Secondary 05A15, 15A18

##  1\. Introduction

A (multiplicatively written) group $G$ is _commutative transitive_ , briefly
CT, provided the relation of commutativity is transitive on
$G\backslash\\{1\\}$; equivalently, provided the centralizer of every element
$g\neq 1$ is abelian.

Noncyclic free groups are universally equivalent, even elementarily
equivalent. Myasnikov and Remeslennikov [MR] proved that their universal
theory is axiomatized by the quasi-identities they satisfy together with
commutative transitivity. Fixing a noncyclic free group $F$, they proved the
analogous result in the language of $F$ when the models are restricted to
$F$-groups.

Let $A$ be a countably infinite set well-ordered as

$\\{a_{1},a_{2},...,a_{n},...\\}=\\{a_{n+1}:~{}n<\omega\\}$

where $\omega$ is the first limit ordinal which we take as the set of
nonnegative integers provided with its natural order. Let
$F_{\omega}(\mathcal{N}_{2})$ be the group free in the variety of all
2-nilpotent groups on the generators $A$. For each integer $n\geq 2$ let
$F_{n}(\mathcal{N}_{2})$ be the subgroup of $F_{\omega}(\mathcal{N}_{2})$
generated (necessarily freely) by the initial segment
$\\{a_{1},a_{2},...,a_{n}\\}$ of $A$. The _Heisenberg group_ is the group $H$
of all $3\times 3$ upper unitriangular matrices with entries in the ring
$\mathbb{Z}$ of integers. It is free in $\mathcal{N}_{2}$ on the generators

$a_{1}=\begin{bmatrix}1&0&0\\\ 0&1&1\\\ 0&0&1\end{bmatrix}\ \ \text{and}\ \
a_{2}=\begin{bmatrix}1&1&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$

(See [4]). We take the liberty of identifying $F_{2}(\mathcal{N}_{2})$ with
$H$.

Now $F_{\omega}(\mathcal{N}_{2})$ is _discriminated_ by the family of
retractions $F_{\omega}(\mathcal{N}_{2})\rightarrow H$. That means that given
finitely many elements $f_{1},...,f_{k}\in
F_{\omega}(\mathcal{N}_{2})\backslash\\{1\\}$ there is a retraction
$F_{\omega}(\mathcal{N}_{2})\rightarrow H$ which doesn’t annihilate any of
them. ($H$ _discriminates_ $\mathcal{N}_{2}$ in the sense of Hanna Neumann
[8].) From this it follows that $F_{n}(\mathcal{N}_{2})$, $n\geq 2$, are
universally equivalent; moreover, since the discrimination is done by
retractions, they are universally equivalent in the language of $H$. (See
[3]).

Let CT(1) or _noncentral commutative transitivity_ , briefly NZCT, be the
property that the relation of commutativity be transitive on $G\backslash
Z(G)$ where $Z(G)$ is the center of $G$. Equivalently, NZCT asserts that the
centralizers of noncentral elements are abelian. A special case of a question
posed by A.G. Myasnikov is whether or not the universal theory of noncyclic
free 2-nilpotent groups is axiomatized by the quasi-identities they satisfy
together with NZCT and whether or not that theory in the language of $H~{}$ is
so axiomatized when the models are restricted to $H$-groups.

In this paper, in the case of the language of $H$, we answer that question in
the positive. In fact we prove a slightly stronger result. The remainder of
this paper contains four additional sections. In Section 2 we fix definitions
and notation. In Section 3 we prove the main result. In Section 4 we ponder
but do not settle the question in the language without parameters from $H$.
Finally in Section 5 we suggest problems for future research.

Before closing the introduction we note that the variety $\mathcal{A}^{2}$ of
metabelian groups is discriminated by its rank $2$ free group. From this it
follows that the noncyclic free metabelian groups are universally equivalent.
It is worth mentioning in passing that Remeslenikov and Stohr proved in [9]
that the universal theory of the noncyclic free metabelian groups is
axiomatized by the quasi-identities they satisfy together with commutative
transitivity.

##  2\. Pedantic Preliminaries

Let $L_{0}$ be the first order language with equality containing a binary
operation symbol $\cdot$ , a unary operational symbol -1 and a constant symbol
$\widehat{1}.$ If $G$ is a (multiplicatively written) group $L_{0}[G]$ is
obtained from $L_{0}$ by adjoining names $\widehat{g}$ for the elements $g\in
G\backslash\\{1\\}$ as new constant symbols. We find it convenient to commit
the ”abuses” of identifying $\widehat{g}$ with $g$ for all $g\in G$ and
replacing $\cdot$ with juxtaposition. Moreover, we find it convenient to write
an inequation $\sim(s=t)$ as $s\neq t$.

An _identity_ , in $L_{0}[G]$ (Note: $L_{0}=L[\\{1\\}]$) is a universal
sentence of the form $\forall\overline{x}~{}(s(\overline{x})=t(\overline{x}))$
where $\overline{x}$ is a tuple of variables and $s(\overline{x})$ and
$t(\overline{x})$ are terms of $L_{0}[G]$. Examples of identities are the
group axioms, namely:

$\displaystyle\forall x_{1},x_{2},x_{3}~{}((x_{1}x_{2})x_{3}~{}$
$\displaystyle=$ $\displaystyle~{}x_{1}(x_{2}x_{3}))$ $\displaystyle\forall
x~{}(x1)$ $\displaystyle=$ $\displaystyle x$ $\displaystyle\forall
x~{}(x~{}x^{-1})\ $ $\displaystyle=$ $\displaystyle\ 1).$

A _quasi-identity_ of $L_{0}[G]$ is universal sentence of the form

$\forall~{}\overline{x}~{}\left(\mathop{\displaystyle\bigwedge}\limits_{i=1}^{k}~{}(~{}s_{i}(~{}\overline{x})=t_{i}(~{}\overline{x}))\rightarrow\
(s(~{}\overline{x})=t(~{}\overline{x}))\right)$

where $~{}\overline{x}$ is a tuple of variables and the
$s_{i}(~{}\overline{x})$, $t_{i}(~{}\overline{x}),~{}\ s(~{}\overline{x})$ and
$t(~{}\overline{x})$ are terms of $L_{0}[G]$. Every identity is equivalent to
a quasi-identity since
$\forall\overline{x}~{}(s(\overline{x})=t(\overline{x}))$ is equivalent to

$\forall\overline{x},y~{}((y=y)\rightarrow~{}(s(\overline{x})=t(\overline{x}))).$

In particular, the group axioms are equivalent to quasi-identities.

If $G$ is a group and we let $\mathcal{Q}^{0}(G)$ be the set of all quasi-
identities of $L_{0}$ true in $G$ and $\mathcal{Q}(G)$ be the set of all
quasi-identities of $L_{0}[G]$ true in $G$. We view the group axioms as
contained in $\mathcal{Q}^{0}(G)\subseteq\mathcal{Q}(G)$. We let
$Th_{\forall}^{0}(G)$ be the set of all universal sentences of $L_{0}$ true in
$G$ and $Th_{\forall}(G)$ be the set of all universal sentences of $L_{0}[G]$
true in $G$. Note that quantifier free sentences are viewed as special cases
of universal sentences. In particular, the _diagram_ of $G$, briefly
$\text{diag}(G)$, consisting of the atomic and negated atomic sentences of
$L_{0}[G]$ true in $G$ is a set of universal sentences of $L_{0}[G]$.

A _$G$ -group_ $\Gamma$ is a model of the group axioms and $\text{diag}(G)$.
That is equivalent to the group $\Gamma$ containing a distinguished copy of
$G$ as a subgroup. A _$G$ -polynomial_ is a group word on the elements of $G$
and variables. (If you like, an element of the free product $G\ast\langle
x_{1},...,x_{n};~{}\rangle$ for some $n$.) Note that, modulo the group axioms,
every identity of $L_{0}$ ($L_{0}[G]$ ) is equivalent to one of the form
$\forall\overline{x}~{}\left(w(\overline{x})=1\right)$ where $w(\overline{x})$
is a group word ($G$-polynomial) and every quasi-identity of $L_{0}$
($L_{0}[G]$ ) is equivalent to one of the form

$\forall~{}\overline{x}~{}\left(\mathop{\displaystyle\bigwedge}\limits_{i=1}^{k}~{}(~{}u_{i}(~{}\overline{x})=1)\rightarrow\
(w(~{}\overline{x})=1)\right)$

where the $u_{i}(\overline{x})$ and $w(~{}\overline{x})$ are group words
($G$-polynomials).

In this paper by ”ring” we shall always mean commutative ring with
multiplicative identity $1\neq 0$. Subrings are required to contain $1$ and
homomorphisms are required to preserve $1$. A ring $R$ is _residually_
-$\mathbb{Z}$ provided, given $r\in R\backslash\\{0\\}$, there is a
homomorphism $R\rightarrow\mathbb{Z}$ which does not annihilate $r$. This
forces $R$ to have characteristic zero and we identify the minimum subring of
$R$ with $\mathbb{Z}$. Hence, we view $R$ as separated by retractions
$R\rightarrow\mathbb{Z}$. A ring is _locally residually- $\mathbb{Z}$ _
provided every finitely generated subring is residually-$\mathbb{Z}$ . Being
locally residually-$\mathbb{Z}$ is equivalent to being a model of the quasi-
identities of ring theory true in $\mathbb{Z}$ (See [4]).

It was proven in [4] that every model of $\mathcal{Q}(H)\cup\text{diag}(H)$
$H$-embeds in $UT_{3}(R)$ for some locally residually-$\mathbb{Z}$ ring $R$.
(Conversely every $H$-subgroup of such a $UT_{3}(R)$ is a model of
$\mathcal{Q}(H)\cup\text{diag}(H)$.) Here an _$H$ -embedding_ is an embedding
which is the identity on $H$. (The meanings of _$H$ -subgroup_ and _$H$
-homomorphism_ in the category of $H$-groups are readily apparent.)

Let $G$ be a group and $g\in G$. We let $C_{G}(g)$ be the centralizer of $g$
in $G$. NZCT is the following universal sentence of $L_{0}:$

$\forall x_{1},x_{2},x_{3},y~{}\left((([x_{2},y]\neq
1)\wedge([x_{1},x_{2}]=1)\wedge([x_{2},x_{3}]=1))\rightarrow([x_{1},x_{3}]=1)\right).$

A group $G$ satisfies NZCT if and only if $C_{G}(g)$ is abelian for all $g\in
G\backslash Z(G)$. The following quasi-identity of $L_{0}[H]$ holds in $H$.

$\forall
x,z~{}\left((([z,a_{1}]=1)\wedge([a_{2},z]=1))\rightarrow([z,x]=1)\right).$

It follows that, if $G$ is any model of $\mathcal{Q}(H)\cup\text{diag}(H)$,
then $C_{G}(a_{1})\cap C_{G}(a_{2})=Z(G)$. In particular, if $G$ additionally
satisfies NZCT, then the following universal sentence $\tau$ of $L_{0}[H]$ is
a consequence

$\forall
x_{1},x_{2}~{}\left(\begin{array}[]{c}(([x_{2},x_{1}]=1)\wedge([a_{2},x_{2}]=1)\wedge([x_{1},a_{1}]=1)~{}\rightarrow\\\
(([x_{2},a_{1}]=1)\vee([a_{2},x_{1}]=1))\end{array}\right).$

We shall prove in the next section that
$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$ axiomatizes
$Th_{\forall}(H)$.

A _primitive sentence_ of $L_{0}[H]$ is ($\mathop{\rm mod}$ulo the group
axioms) an existential sentence of the form
$\exists~{}\overline{x}~{}\left(\mathop{\displaystyle\bigwedge}\limits_{i}~{}(p_{i}(~{}\overline{x})=1)~{}\wedge(~{}\mathop{\displaystyle\bigwedge}\limits_{j}(q_{j}(~{}\overline{x})\neq
1)\right)$ where the $p_{i}(~{}\overline{x})$ and $q_{j}(~{}\overline{x})$ are
$H$-polynomials.

By writing the matrix of an existential sentence in disjunctive normal form
one sees that every existential sentence of $L_{0}[H]$ is equivalent (modulo
the group axioms) to a disjunction of primitive sentences and so holds in an
$H$-group if and only if at least one disjunct does.

Assume momentarily that there is a universal sentence $\varphi$ of $L_{0}[H]$
which holds in $H$ but is not a consequence of
$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$. Then its negation
$\sim\varphi$ must hold in some model $\ G$ of
$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$. Since $\sim\varphi$ is
equivalent to an existential sentence of $L_{0}[H]$ there must be a primitive
sentence

$\exists
x_{1},...,x_{k}~{}\left(\mathop{\displaystyle\bigwedge}\limits_{i}~{}(p_{i}(~{}a_{1},a_{2},x_{1},...,x_{k})=1)~{}\wedge(~{}\mathop{\displaystyle\bigwedge}\limits_{j}(q_{j}(a_{1},a_{2},x_{1},...,x_{k})\neq
1)\right)$

of $L_{0}[H]$ which holds in $G$ but is false in $H$. Let the assignment
$x_{\lambda}\mapsto g_{\lambda}$, $1\leq\lambda\leq k$, verify the above
sentence in $G$. Then the finitely generated $H$-subgroup $G_{0}=~{}\langle
a_{1},a_{2},g_{1},...g_{k}\rangle$ of $G$ also satisfies the above primitive
sentence and, since universal sentences of $L_{0}[H]$ are preserved in
$H$-subgroups, $G_{0}$ is a model of
$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$. Hence, if a counterexample
exists, then so would a finitely generated counterexample exist. So it
suffices to prove the result for finitely generated models. We shall find it
convenient to prove, more generally, that the result holds for models $G$ such
that the quotient $\overline{G}=G/Z(G)$ is finitely generated.

##  3\. The Lame Property and the Universal Theory of $H$

It was shown in [5] using a characterization due to Mal’cev [7] that a model
$E$ of $\mathcal{Q}(H)\cup\text{diag}(H)$ is of the form $UT_{3}(R)$ for some
locally residually-$\mathbb{Z}$ ring $\ R$ if and only if $E$ satisfies the
following universal-existential sentence

$\sigma$ of $L_{0}[H]:$

$\forall x_{1},x_{2}\exists
y_{1},y_{2}~{}\left(\begin{array}[]{c}([y_{1},a_{1}]=1)\wedge([a_{2},y_{2}]=1)\wedge([x_{2},x_{1}]=[y_{2},a_{1}])\\\
\wedge~{}(~{}[x_{2},x_{1}]=[a_{2},y_{1}])\end{array}\right).$

In other words, for each commutator $[g_{2},g_{1}]$, each of the systems

$S~{}\left\\{\begin{array}[]{c}[a_{2},y]=1\\\
[y,a_{1}]=[g_{2},g_{1}]\end{array}\right.$

and

$T~{}\left\\{\begin{array}[]{c}[x,a_{1}]=1\\\
[a_{2},x]=[g_{2},g_{1}]\end{array}\right.$

has a solution in $E$.

Mimicking the construction of an existentially closed extension (See e.g.
Hodges [H]) we may embed a model $G$ of
$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$ into $UT_{3}(R)$, If we could
preserve $\tau$ at each step then, since universal sentences are preserved in
direct unions, $UT_{3}(R)$ would also satisfy $\tau$. If $UT_{3}(R)$ satisfies
$\tau$, then $R$ is an integral domain. To see this let $(r,s)\in R^{2}$ and
suppose $rs=0$. Let $y=\begin{bmatrix}1&r&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$
and $x=\begin{bmatrix}1&0&0\\\ 0&1&s\\\ 0&0&1\end{bmatrix}$. Then $[y,x]=1$
and $[a_{2},y]=1$ and $[x,a_{1}]=1$. Moreover,
$[y,a_{1}]=\begin{bmatrix}1&0&r\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$ and
$[a_{2},x]=\begin{bmatrix}1&0&s\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$. Since
$UT_{3}(R)$ satisfies $\tau$, $r=0$ or $s=0$ and $R$ indeed is an integral
domain.

A residually-$\mathbb{Z}$ ring $R$ is _$\omega$ -residually-$\mathbb{Z}$_
provided it is discriminated by the family of retractions
$R\rightarrow\mathbb{Z}$ . That is, given finitely many nonzero elements of
$R$, there is a retraction $R\rightarrow\mathbb{Z}$ which does not annihilate
any of them. That is equivalent to $R$ being an integral domain. Suppose first
that $R$ is an integral domain. Let $r_{1},...,r_{n}$ be finitely many nonzero
elements of $R$. Then the product $r=$ $r_{1}\cdots r_{n}\neq 0$ and there is
a retraction $\rho:R\rightarrow\mathbb{Z}$ which does not annihilate $r$ so
cannot annihilate and of $r_{1},...,r_{n}$. Conversely, if $R$ is
$\omega$-residually-$\mathbb{Z}$ and $r$ and $s$ are nonzero elements of $R$,
then there is a retraction $\rho:R\rightarrow\mathbb{Z}$ such that
$\rho(r)\neq 0$ and $\rho(s)\neq 0$; so, $\rho(rs)=\rho(r)\rho(s)\neq 0$ and
hence $rs\neq 0$ and $R$ must be an integral domain. From this it follows that
a locally residually-$\mathbb{Z}$ ring $R$ is locally
$\omega$-residaully-$\mathbb{Z}$ if and only if $R$ is an integral domain. So,
if $UT_{3}(R)$ satisfies $\tau$, then $R$ is locally
$\omega$-residually-$\mathbb{Z}$ .

Given $G\leq_{H}UT_{3}(R)$, $G$ is the direct union
$\underset{\rightarrow}{\lim}~{}(G\cap UT_{3}(R_{0}))$ as $R_{0}$ varies over
the finitely generated subrings of $R$. Ring retractions
$R_{0}\rightarrow\mathbb{Z}$ induce group retractions $G\cap
UT_{3}(R_{0})\rightarrow H$. From this it follows that each $G\cap
UT_{3}(R_{0})$ is discriminated by the family of group retractions $G\cap
UT_{3}(R_{0})\rightarrow H$ and hence each $G\cap UT_{3}(R_{0})$ is a model of
$Th_{\forall}(H)$. Since universal sentences are preserved in direct unions
and $G=$ $\underset{\rightarrow}{\lim}~{}(G\cap UT_{3}(R_{0}))$ we have that
$G$ is a model of $Th_{\forall}(H)$. The bottom line is that we would be
finished if we could construct an overgroup $UT_{3}(R)$ in such a way that
$\tau$ is preserved at each step of the construction.

Let us forget momentarily about this particular $R$ and consider a possible
property that a representation $G\leq_{H}UT_{3}(R)$ might satisfy.

Let $G$ be a model of $\mathcal{Q}(H)\cup\text{diag}(H)$ and let
$G\leq_{H}UT_{3}(R)$ where $R$ is locally residually-$\mathbb{Z}$. We say the
representation satisfies the _Lame Property_ provided, for each
$g=\begin{bmatrix}1&g_{12}&g_{13}\\\ 0&1&g_{23}\\\ 0&0&1\end{bmatrix}\in
C_{G}(a_{1})\cup C_{G}(a_{2})$, either $g_{12}^{2}+g_{23}^{2}=0$ or
$g_{12}^{2}+g_{23}^{2}$ is not a zero divisor in $R$.

######  Lemma 1.

Given a model $G$ of $\mathcal{Q}(H)\cup\text{diag}(H)$ and a representation
$G\leq_{H}UT_{3}(R)$ where $R$ locally residually-$\mathbb{Z}$. The
representation satisfies the Lame Property if and only if it satisfies the
conjunction of the following two conditions:

(1.) For all $y=\begin{bmatrix}1&y_{12}&y_{13}\\\ 0&1&0\\\
0&0&1\end{bmatrix}\in C_{G}(a_{2})\backslash Z(G)$, $~{}y_{12}$ is not a zero
divisor in $R$.

(2.) For all $x=\begin{bmatrix}1&0&x_{13}\\\ 0&1&x_{23}\\\
0&0&1\end{bmatrix}\in C_{G}(a_{1})\backslash Z(G)$, $x_{23}$ is not a zero
divisor in $R$.

######  Proof 3.1.

Suppose the representation satisfies the Lame Property. Let
$y=\begin{bmatrix}1&y_{12}&y_{13}\\\ 0&1&0\\\ 0&0&1\end{bmatrix}\in
C_{G}(a_{2})\backslash Z(G)$. Then $y_{12}\neq 0.$

The quasi-identity $\forall x~{}((x^{2}=0)\rightarrow(x=0))$ holds in
$\mathbb{Z}$ ; hence, it is true in $R$ and $y_{12}^{2}\neq 0$. If $r\neq 0$
annihilates $y_{12}$ then $r(y_{12}^{2}+y_{23}^{2})=ry_{12}^{2}=0$
contradicting $y_{12}^{2}=y_{12}^{2}+y_{23}^{2}$ is not a zero divisor in $R$.
The contradiction shows that the representation satisfies (1.). Similarly, the
representation satisfies (2.).

Now suppose that representation satisfies (1.) and (2.). Let
$g=\begin{bmatrix}1&g_{12}&g_{13}\\\ 0&1&g_{23}\\\ 0&0&1\end{bmatrix}\in
C_{G}(a_{1})\cup C_{G}(a_{2})$. $\mathbb{Z}$ satisfies each of the quasi-
identities

$\displaystyle\forall x,y~{}((x^{2}+y^{2}$ $\displaystyle=$ $\displaystyle
0)\rightarrow(x=0))\text{ and}$ $\displaystyle\forall x,y~{}(x^{2}+y^{2}$
$\displaystyle=$ $\displaystyle 0)\rightarrow(y=0));\text{ so,}$

they must hold in $R$. Hence, if $g_{12}^{2}+g_{23}^{2}\neq 0$, then either
$g_{12}\neq 0$ or $g_{23}\neq 0$.

Suppose there were an $r\neq 0$ which annihilates $g_{12}^{2}+g_{23}^{2}$.
From $r(g_{12}^{2}+g_{23}^{2})=0$ we get
$(rg_{12})^{2}+(rg_{23})^{2}=r^{2}(g_{12}^{2}+g_{23}^{2})=0$. Hence
$rg_{12}=0$ and $rg_{23}=0$. If $g_{12}\neq 0$ (1.) is contradicted while if
$g_{23}\neq 0$ (2.) is contradicted. The contradiction shows that the
conjunction of (1.) and (2,) implies the Lame Property.

We next note that if the representation $G\leq_{H}UT_{3}(R)$ satisfies the
Lame Property, then $G$ satisfies $\tau$.

For suppose $[a_{2},y]=1$ so $y=\begin{bmatrix}1&y_{12}&y_{13}\\\ 0&1&0\\\
0&0&1\end{bmatrix}\in C_{G}(a_{2})$, $[x,a_{1}]=1$ so
$x=\begin{bmatrix}1&0&x_{13}\\\ 0&1&x_{23}\\\ 0&0&1\end{bmatrix}\in
C_{G}(a_{1})$ and $[y,x]=\begin{bmatrix}1&0&y_{12}x_{23}\\\ 0&1&0\\\
0&0&1\end{bmatrix}=1=\begin{bmatrix}1&0&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$.
Then $y_{12}x_{23}=0$. But if $y_{12}\neq 0$, then $x_{23}=0$ otherwise (1.)
is contradicted while if $x_{23}\neq 0$, then $y_{12}=0$ otherwise (2.) is
contradicted. It follows that either $[y,a_{1}]=1$ or $[a_{2},x]=1$ so $\tau$
holds in $G$. For a fixed representation $G\leq_{H}UT_{3}(R)$ satisfying the
Lame Property is a sufficient condition for $\tau$ to hold in $G$; however, it
is not a necessary condition for $G$ to satisfy $\tau$. (None the less we
shall subsequently see that having at least one representation satisfying the
Lame Property is necessary and sufficient.)

The result (proven in [5]) that every $3$-generator model of
$\mathcal{Q}(H)\cup\text{diag}(H)$ is already a model of the $Th_{\forall}(G)$
provides a treasure trove of counterexamples.

Let $G$ be a model of $\mathcal{Q}(H)\cup\text{diag}(H)$ and let $R$ be a
locally residually-$\mathbb{Z}$ ring. We say that $R$ is _appropriate for $G$_
provided

  1. (1)

$G\leq_{H}UT_{3}(R)$ and

  2. (2)

$R$ is generated by the entries of the elements of $G$.

Now $R=\mathbb{Z}\times\mathbb{Z=Z}e_{1}~{}+~{}\mathbb{Z}e_{2}$ where
$e_{1}=(1,0)$ and $e_{2}=(0,1)$ is residually-$\mathbb{Z}$ . Consider the
$3$-generator subgroup $G\leq_{H}UT_{3}(R)$ generated by

$a_{1}=\begin{bmatrix}1&0&0\\\ 0&1&1\\\
0&0&1\end{bmatrix}~{},~{}~{}a_{2}=\begin{bmatrix}1&1&0\\\ 0&1&0\\\
0&0&1\end{bmatrix}~{}~{}\text{and }b=\begin{bmatrix}1&0&0\\\ 0&1&e_{1}\\\
0&0&1\end{bmatrix}.$

Since $1-e_{1}=e_{2}$ , $R=\mathbb{Z}\times\mathbb{Z}$ is generated by the
entries of the elements of $G$. Since $e_{1}e_{2}=0$, $e_{1}$ is a zero
divisor in $R$.

Now $b\in C_{G}(a_{1})\backslash Z(G)$ and $b_{23}=e_{1}$ is a zero divisor in
$R$. Hence, the representation violates the Lame Property. Every $3$-generator
model of $\mathcal{Q}(H)\cup\text{diag}(H)$ is already a model of
$Th_{\forall}(H)$. So this $G=\langle a_{1},a_{2},b\rangle$ satisfies $\tau$.
Now this $G$ is obtained from $H$ by extending $C_{H}(a_{1})$ introducing a
new parameter. (It is a rank $1$ centralizer extension relative to the
category $\boldsymbol{N}_{2}$ of $2$-nilpotent groups.)

Let $\theta$ be an indeterminate over $\mathbb{Z}$ . Then the polynomial ring
$\mathbb{Z}[\theta]$ is residually-$\mathbb{Z}$ and we could have just as well
embedded this $G$ into $UT_{3}($ $\mathbb{Z}[\theta]$ ) as the subgroup
generated by

$a_{1}=\begin{bmatrix}1&0&0\\\ 0&1&1\\\
0&0&1\end{bmatrix}~{},~{}~{}a_{2}=\begin{bmatrix}1&1&0\\\ 0&1&0\\\
0&0&1\end{bmatrix}~{}~{}\text{and }b=\begin{bmatrix}1&0&0\\\ 0&1&\theta\\\
0&0&1\end{bmatrix}.$

Since $\theta$ is an entry of an element of $G$, $\mathbb{Z}[\theta]$ is also
appropriate for $G$. Since $\mathbb{Z}[\theta]$ is an integral domain, the
representation does satisfy the Lame Property.

Anticipating an application to be used later in this paper, suppose $G_{0}$ is
a model of $\mathcal{Q}(H)\cup\text{diag}(H)$ and let $a_{i}$ be a free
generator of $H$, $i\in\\{1,2\\}$. Suppose $G$ is obtained from $G_{0}$ by
extending $C_{G_{0}}(a_{i})$. That is

$G=\langle
G_{0},t;~{}rel(G_{0}),~{}[t,C_{G_{0}}(a_{i})]=1\rangle_{\mathcal{N}_{2}}.$

Using a big powers argument, we get a discriminating family of retractions
$G\rightarrow G_{0}$ via

$\left\\{\begin{array}[]{c}g\mapsto g~{},~{}g\in G_{0}\\\ t\mapsto
a_{i}^{n}~{},~{}n\in\mathbb{Z}\end{array}\right..$

It follows that $G$ is universally equivalent to $G_{0}$.

Now suppose we fix a model $G_{0}$ of
$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$ which admits a representation
$G_{0}\leq_{H}UT_{3}(R)$ satisfying the Lame Property. Let $(g_{1},g_{2})\in
G_{0}^{2}$ and suppose the system

$S\left\\{\begin{array}[]{c}[a_{2},y]=1\\\
[y,a_{1}]=[g_{2},g_{1}]\end{array}\right.$

has no solution in $G_{0}$. Let $[g_{2},g_{1}]=z=\begin{bmatrix}1&0&z_{13}\\\
0&1&0\\\ 0&0&1\end{bmatrix}$. Let $Y$ be the element
$\begin{bmatrix}1&z_{13}&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$ of $UT_{3}(R)$.
Then $[a_{2},Y]=1$ and $[Y,a_{1}]=[g_{2},g_{1}]$ so $Y\notin G_{0}$.

Let $G_{1}$ be the subgroup $\langle G_{0},Y\rangle$ of $UT_{3}(R)$.
Collecting and simplifying we see a typical element of $G_{1}$ has the form
$uY^{n}~{}[Y,w]$ where $n\in\mathbb{Z}$ and $(u,w)\in G_{0}^{2}$. The matrix
representing this element has the form
$\begin{bmatrix}1&u_{12}+nz_{13}&\ast\\\ 0&1&u_{23}\\\ 0&0&1\end{bmatrix}$.
Now suppose $C=\begin{bmatrix}1&c_{12}+nz_{13}&\ast\\\ 0&1&0\\\
0&0&1\end{bmatrix}\in C_{G_{1}}(a_{2})$ and $B=\begin{bmatrix}1&0&\ast\\\
0&1&b_{23}\\\ 0&0&1\end{bmatrix}\in C_{G_{1}}(a_{1})$. Assume further that
$[C,B]=1$. Then $\begin{bmatrix}1&0&(c_{12}+nz_{13})b_{23}\\\ 0&1&0\\\
0&0&1\end{bmatrix}=\begin{bmatrix}1&0&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$ so
$(c_{12}+nz_{13})b_{23}=0$. Now, $\ c_{12}+nz_{13}\neq 0$ and $b_{23}\neq 0$.
Moreover, $B$ has the form $u[Y,w]$ with $u\in C_{G_{0}}(a_{1})$ looking like
$\begin{bmatrix}1&0&\ast\\\ 0&1&b_{23}\\\ 0&0&1\end{bmatrix}$. Since $b_{23}$
is a zero divisor in $R$ that contradicts that the representation $G_{0}$
satisfies the Lame Property. Hence, either $c_{12}+nz_{13}=0$ or $b_{23}=0$ so
either$[C,a_{1}]=1$ or $[a_{2},B]=1$ and $G_{1}$ satisfies $\tau$.

Similarly, if the system

$T\left\\{\begin{array}[]{c}[x,a_{1}]=1\\\
[a_{2},x]=[g_{2},g_{1}]\end{array}\right.$

has no solution in $G_{0}$ we can extend to a model of
$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$ in which $T$ has a solution.

Getting back to $G_{1}$, suppose the system

$T\left\\{\begin{array}[]{c}[x,a_{1}]=1\\\
[a_{2},x]=[g_{2},g_{1}]\end{array}\right.$

has no solution in $G_{1}$. Suppose further that $G_{1}$ admits a
representation $G_{1}\leq_{H}UT_{3}(R)$ satisfying the Lame Property. Then we
can extend $G_{1}$ to a model $G$ of
$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$ in which $T$ has a solution.
We have the chain $G_{0}\leq G_{1}\leq G$. $G$ is a model of
$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$ in which the system

$S\cup T\left\\{\begin{array}[]{c}\begin{array}[]{l}[a_{2},y]=1\\\
[y,a_{1}]=[g_{2},g_{1}]\end{array}\\\ \begin{array}[]{l}[x,a_{1}]=1\\\
[a_{2},x]=[g_{2},g_{1}]\end{array}\end{array}\right.$

has a solution. So, if every model $G$ of
$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$ has at least one
representation satisfying the Lame Property, then $G$ embeds in $UT_{3}(R)$
where $R$ is an integral domain and we are finished. To prove that every model
of $\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$ admits a representation
satisfying the Lame Property, we need some results from model theory.

Let $\mathbb{M}$ be the model class operator. We first paraphrase a result
from Bell and Slomson [1].

######  Proposition 2.

Let $L$ be a first order language with equality. Let $K$ be the class of all
$L$structures and let $X\subseteq K$. Then there is a set $S$ of sentences of
$L$ such that $X=\mathbb{M}(S)$ if and only if $X$ is closed under isomorphism
and ultraproducts and $K\backslash X$ is closed under ultraprowers.

######  Remark 3.

The proof in [1] needed the Generalized Continuum Hypothesis. In view of
Shelah’s [10] improvement of Keisler’s ultrapower theorem that hypothesis may
be omitted.

The next result may be found in Hodges [H].

######  Proposition 4.

Let $L$ be a first order language with equality. Let $T$ be a set of sentences
of $L$. Let $T_{\forall}$ be the set of all universal sentences of $L$ which
are logical consequences of $T$. Then $\mathbb{M}(T_{\forall})$ consists of
all $L$-substructures of models of $T$.

Using Proposition 1, a striaghtforward but tedious verification reveals that
the class of all models of $\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$
which admit a representation satisfying the Lame Property is first order.
Moreover, since this class is closed under $H$-subgroups, it has (as an
application of Proposition 2) a set $\Phi$ of universal axioms in $L_{0}[H]$.
Now
$\mathbb{M}(\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\})\supseteq~{}\mathbb{M}(\Phi)$.
We would be finished if we could prove equality. It will suffice to establish
the result for finitely generated models. We shall prove the result more
generally for models $G$ of $\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$
such that the quotient $\overline{G}=G/Z(G)$ is finitely generated.

######  Theorem 5.

Every model of $\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$ admits a
representation satisfying the Lame Property.

######  Corollary 6.

$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$ is an axiomatization for
$Th_{\forall}(H)$.

######  Corollary 7.

$\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{NZCT\\}$ is an axiomatization for
$Th_{\forall}(H)$.

######  Proof 3.2 (Proof of Theorem 5).

Let $G$ be a model of $\mathcal{Q}(H)\cup\text{diag}(H)\cup\\{\tau\\}$. We may
assume without loss of generality that the quotient $\overline{G}=G/Z(G)$ is
finitely generated. Let $\overline{C_{i}}=C_{G}(a_{i})~{}/Z(G),~{}i=1,2$.
Since $\langle\overline{a_{i}}~{}\rangle=\langle
a_{i}Z(G)\rangle\subseteq\overline{C_{i}}$, $\overline{C_{i}}$ has finite rank
at least $1$, $i=1,2$.

Thus, $\text{rank}(\overline{C_{1}})+\text{rank}(\overline{C_{2}})\geq 2$.
Define the _$C$ -rank_ of $G$ to be

$\text{rank}(\overline{C_{1}})+\text{rank}(\overline{C_{2}})-1.$

The proof will proceed by induction on the $C$-rank.

Suppose first that the $C$-rank of $G$ is $1$. That forces

$\text{rank}(\overline{C_{1}})=1=\text{rank}(\overline{C_{2}})$

and $\overline{C_{i}}~{}=~{}\langle\overline{a_{i}}~{}\rangle=\langle
a_{i}Z(G)\rangle$, $i=1,2$. Let $G\leq_{H}UT_{3}(R)$ be any representation
where $R$ is locally residually-$\mathbb{Z}$ .

It follows from the above that every element of $\ C_{G}(a_{2})\backslash
Z(G)$ looks like $\begin{bmatrix}1&m&\ast\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$
where $m\in\mathbb{Z}\backslash\\{0\\}$ and every element of
$C_{G}(a_{1})\backslash Z(G)$ looks like $\begin{bmatrix}1&0&\ast\\\ 0&1&n\\\
0&0&1\end{bmatrix}$ where $n\in\mathbb{Z}\backslash\\{0\\}$.

Now, for each $k\in\mathbb{Z}\backslash\\{0\\}$, the quasi-identity $\forall
x~{}((kx=0)\rightarrow(x=0))$ holds in $\mathbb{Z}$ . Hence, these quasi-
identities hold in $R$ and consequently every representation of $G$ satisfies
the Lame Property. The initial step of the induction has been established.

Now suppose $G$ has $C$-rank $n>1$ and the result has been established for
models with $C$-rank $k$ with $1\leq k<n$.

Now let $G\leq_{H}UT_{3}(R)$ be any representation of $G$ where $R$ is locally
residually-$\mathbb{Z}$ . Let us extend $G$ to $\widehat{G}$ by adjoining the
elements $\begin{bmatrix}1&0&r\\\ 0&1&0\\\ 0&0&1\end{bmatrix}$ as $r$ varies
over $R$. Since $\tau$ depends on the $(1,2)$ and $(2,3)$ entries only and
since $\widehat{G}$ has the same $C$-rank as $G$, we may replace $G$ with
$\widehat{G}$. This causes no harm since universal sentences are preserved in
subgroups; so $G$ will be a model of $\Phi$ whenever $\widehat{G}$ is.

Since the $C$-rank of $\widehat{G}$ is greater than $1$ at least one of

$\overline{C_{i}}=C\widehat{{}_{G}}(a_{i})/Z(\widehat{G})~{},~{}i=1,2$

must have rank at least $2$. We may assume
$\text{rank}(\overline{C_{2}})=m\geq 2$. Choose elements
$a_{2},b_{1},...,b_{m-1}~{}\in C_{\widehat{G}}(a_{2})$ which project modulo
$Z(\widehat{G})$ to a basis for $\overline{C_{2}}$ . Now let $N$ be the
subgroup $\langle b_{m-1}\rangle\cdot Z(\widehat{G})$ of $\widehat{G}$ . Since
$[\widehat{G},\widehat{G}]\leq Z(\widehat{G})\leq N$, $N$ is normal in
$\widehat{G}$ and $\widehat{G}/N$ is abelian. Let $T$ be a transversal for $N$
in $\widehat{G}$ so that every element $g$ is uniquely expresses in the form
$t(g)\upsilon(g)$ where $t(g)\in T$ and $\upsilon(g)\in N$. Assume further
that, for all $(p,q,z)\in\mathbb{Z}^{2}\times Z(\widehat{G})$,
$~{}t(a_{1}^{p}a_{2}^{q}z)=a_{1}^{p}a_{2}^{q}$ and that $t(x)=1$ for all $x\in
N$.

Let $G_{0}$ be the subgroup of $\widehat{G}$ generated by the coset
representatives of $N$ in $\widehat{G}$ together with $Z(\widehat{G})$ . Since
$b_{m-1}$ is killed off the $C$-rank of $G_{0}$ is less than that of
$\widehat{G}$ and so, by inductive hypothesis, $G_{0}$ is a model of $\Phi$.

Examining the general form of a matrix in $\widehat{G}$ and setting that guy
equal to the identity matrix, we see that, modulo the law
$[x_{1},x_{2},x_{3}]=1$, the only relations in $\widehat{G}$ are consequences
of the relations in $G_{0}$ and the relations $[C_{G_{0}}(a_{2}),b_{m-1}]=1$.
That is, $\widehat{G}$ is the free rank $1$ extension of $C_{G_{0}}(a_{2})$
relative to $\boldsymbol{N}_{2}$ and hence $G_{0}$ and $\widehat{G}$ are
universally equivalent. Then $\widehat{G}$ is a model of $\Phi$ since $G_{0}$
is. Since $G\leq\widehat{G}$ and universal sentences are preserved in
subgroups, $G$ is a model of $\Phi$. That completes the induction and proves
the theorem.

##  4\. The Theory in the Base Language

We wish to ponder whether or not $Q^{0}(H)\cup\\{NZCT\\}$ axiomatizes
$Th_{\forall}^{0}(H)$. To that end let $G_{0}$ be a model of
$Q^{0}(H)\cup\\{NZCT\\}$. We may assume $G_{0}$ is finitely generated. Suppose
that $G_{0}$ is abelian. Then, since models of $Q^{0}(H)$ are torsion free,
$G_{0}$ is free abelian of finite rank $r$. Choose a positive integer $n$ such
that $\left(\begin{array}[]{c}n\\\ 2\end{array}\right)\geq$ max$\\{r,2\\}$. If
$G=F_{n}(\mathcal{N}_{2})$ then $[G,G]$ is free abelian of rank
$\left(\begin{array}[]{c}n\\\ 2\end{array}\right)$. It follows that $G_{0}$
embeds in $G$ . So every universal sentence of $L_{0}$ true in $G$ must also
be true in $G_{0}$. But $G$ is universally equivalent to $H$. Therefore
$G_{0}$ is a model of $Th_{\forall}^{0}(H)$. So it now suffices to assume
$G_{0}$ is a finitely generated nonabelian model of $Q^{0}(H)\cup\\{NZCT\\}$.
A consequence of a result of Grätzer and Lasker [6] is that the quasivariety
generated by $H$ consists of all groups isomorphic to a subgroup of a direct
product of a family of ultrapowers of $H$. View $H$ as $UT_{3}(\mathbb{Z})$
and taking corresponding direct product of ultrapowers of $\mathbb{Z}$ we get
a ring $R$ such that $G_{0}$ embeds in $UT_{3}(R)$. Since quasi-identities are
preserved in direct products and ultrapowers, $R$ is a model of the quasi-
identities true in $\mathbb{Z}$. That is $R$ is locally
residually-$\mathbb{Z}$. Further we may take $R$ to be generated by the
entries of a fixed finite set of generators for $G_{0}$. Thus, $R$ may be
taken finitely generated. Therefore $R$ is residually-$\mathbb{Z}$ and so
separated by the family of retractions $R\rightarrow\mathbb{Z}$. Let
$\overline{G}~{}$be the subgroup $\langle G_{0},H\rangle$ of $UT_{3}(R)$. The
retractions $R\rightarrow\mathbb{Z}$ induce group retractions
$\overline{G}\rightarrow H$ and these separate $\overline{G}$. It follows that
$\overline{G}$ is a model of $Q(H)\cup\text{diag}(H)$. Let us keep this
$\overline{G}~{}$in mind as we move on.

Let us say a group is _$(G_{0},H)$ -group_ if it contains a distinguished copy
of each of $G_{0}$ and $H$. The meanings of _$(G_{0},H)$ -subgroup_ and
_$(G_{0},H)$ -homomorphism_ are readily apparent. A _$(G_{0},H)$ -ideal_ is
the kernel of a $(G_{0},H)$-homomorphism. Equivalently, a $(G_{0},H)$-ideal in
a $(G_{0},H)$-group $G$ is a subgroup $K$ normal in $G$ such that $K\cap
G_{0}=\\{1\\}=K\cap H$.

Suppose $I$ is a nonempty index set and $(G_{i})_{i\in I}$ is a family of
$(G_{0},H)$-groups indexed by $I$. Let $G$ be the direct product
$\mathop{\displaystyle\prod}\limits_{i\in I}~{}G_{i}$. We have the diagonal
embeddings

$\displaystyle\alpha$ $\displaystyle:$ $\displaystyle G_{0}\rightarrow G$
$\displaystyle\alpha(g)(i)$ $\displaystyle=$ $\displaystyle g~{}~{}\text{for
all }g\in G_{0}~{},~{}i\in I$

and

$\displaystyle\beta$ $\displaystyle:$ $\displaystyle H\rightarrow G$
$\displaystyle\beta(h)(i)$ $\displaystyle=$ $\displaystyle h~{}\text{ for all
}h\in H~{},~{}i\in I.$

We view $G$ as a $(G_{0},H)$-group using these diagonal embeddings. Let
$\mathop{\displaystyle\coprod}$ be the $\mathcal{N}_{2}$ free product (See
[8]). Let $G_{1},~{}G_{2},~{}$and $G$ be $2$-nilpotent groups. Let
$\varphi_{i}:~{}G_{i}\rightarrow G$ be a homomorphism $\ i-1,2$. Then there is
a unique homomorphism
$\varphi:G_{1}\mathop{\displaystyle\coprod}G_{2}\rightarrow G$ such that

$\varphi\mid_{G_{i}}=\varphi_{i}~{},~{}i=1,2\text{.}$

Getting back to $\overline{G}$ and letting
$\Gamma=G_{0}\mathop{\displaystyle\coprod}H$ we see there is a unique
$(G_{0},H)$-homomorphism $\varphi:\Gamma\rightarrow\overline{G}$ . Note
$\varphi$ is surjective since $G_{0}$ and $H$ generate $\overline{G}$ . If
$K=Ker(\varphi)$, then $K$ is a $(G_{0},H)$-ideal in $\Gamma$ such that
$\Gamma/K$ is a model of $Q(H)$. Hence the set $\mathbb{K}$ of all
$(G_{0},H)$-ideals, $K$, in $\Gamma$ such that $\Gamma/K$ is a model of $Q(H)$
is nonempty. Let
$K_{0}=\mathop{\displaystyle\bigcap}\limits_{K\in\mathbb{K}}~{}K$. Let
$U_{H}(G_{0})=\Gamma/K_{0}$.

We call $U_{H}(G_{0})$ the _universal $H$-extension of $G_{0}$_. We claim that
$U_{H}(G_{0})$ is a $(G_{0},H)$-group which is a model of $Q(H)$ and that if
$G$ is any $(G_{0},H)$-group which is a model of $Q(H),$ then there is a
unique $(G_{0},H)$-homomorphism $U_{H}(G_{0})\rightarrow G$. Put another way,
we claim that $U_{H}(G_{0})$ is an initial object in the category whose
objects are $(G_{0},H)$-groups which are models of $Q(H)$ and whose morphisms
are $(G_{0},H)$-homomorphisms.

From $K\cap G_{0}=\\{1\\}=K\cap H$ for all $K\in\mathbb{K}$ we get $K_{0}\cap
G_{0}=1=K_{0}\cap H$ as $K_{0}\leq K$ for all $K\in\mathbb{K}$ . Thus, $K_{0}$
is a $(G_{0},H)$-ideal and $U_{H}(G_{0})$ is a $(G_{0},H)$-group.

We get a $(G_{0},H)$-homomorphism

$\varphi:\Gamma\rightarrow\mathop{\displaystyle\prod}\limits_{K\in\mathbb{K}}~{}(\Gamma/K)~{}~{}\text{via}$

$\varphi(\gamma)=(\gamma K)_{K\in\mathbb{K}}$ for all $\gamma\in\Gamma$.
$K_{0}=~{}Ker(\varphi)$. It follows that $U_{H}(G_{0})$ isomorphic to the
image of $\varphi$. Since quasi-identities of $L_{0}[H]$ are preserved in
direct products and $H$-subgroups, $U_{H}(G_{0})$ is a model of $Q(H)$.

Now suppose $G$ is any $(G_{0},H)$-group which is a model of $Q(H)$. Since
$\Gamma=G_{0}\mathop{\displaystyle\coprod}H$ we get a unique homomorphism
$\pi:\Gamma\rightarrow G$ which restricts to the identity on each of $G_{0}$
and $H$. Then $Ker(\pi)\in\mathbb{K}$ and $\pi$ induces $\
\overline{\pi}:U_{H}(G_{0})\rightarrow G$. Since every homomorphism is
determined by its effect on a generating set and
$\Gamma=G_{0}\mathop{\displaystyle\coprod}H$, $\overline{\pi}$ is unique. Our
claims have been established.

Is NZCT preserved in $U_{H}(G_{0})$?

If so, $U_{H}(G_{0})$ would be a model of $Th_{\forall}(H)$ and hence a model
of $Th_{\forall}^{0}(H)$. Since universal sentences are preserved in
subgroups, we would have $G_{0}$ a model of $Th_{\forall}^{0}(H)$.

We observe that

$G_{0}\cap Z(U_{H}(G_{0}))\leq Z(G_{0}).$

We further observe that $Z(G_{0})$ coinciding with $G_{0}\cap Z(U_{H}(G_{0}))$
is a necessary condition for Question 4 to have a positive answer. Recall we
are taking $G_{0}$ nonabelian. Let $g_{1}$ and $g_{2}$ be noncommuting
elements of $G_{0}$ and $g\in Z(G_{0})\backslash(G_{0}\cap Z(U_{H}(G_{0})))$,
then since $g_{1}$ and $g_{2}$ each commute with $g\notin Z(U_{H}(G_{0}))$ ,
NZCT would be violated.

Is $Z(G_{0})=G_{0}\cap Z(U_{H}(G_{0}))$?

##  5\. Questions

Let $c\geq 2$ be an integer. Let $r=\max\\{2,c-1\\}$. Let $s$ be any integer
such that $s\geq r$. Let $G=F_{s}(\mathcal{N}_{c})$. Then
$F_{\omega}(\mathcal{N}_{c})$ is discriminated by the family of retractions
$F_{\omega}(\mathcal{N}_{c})\rightarrow G$. It follows that the
$F_{n}(\mathcal{N}_{c})$ have the same universal theory relative to $L_{0}$
for all $n\geq r$ and that the $F_{n}(\mathcal{N}_{c})$ have the same
universal theory relative to $L_{0}[G]$ for all $n\geq s$ (See [GS 1]). We let
$S_{c}$ be the set of all universal sentences of $L_{0}$ true in
$F_{n}(\mathcal{N}_{c})$. Since $F_{n}(\mathcal{N}_{c})\leq
F_{r}(\mathcal{N}_{c})$ for all $0\leq n\leq r$ and universal sentences are
preserved in subgroups, $S_{c}$ is actually the set of all universal sentences
of $L_{0}$ true in every free $c$-nilpotent group.

For each integer $n\geq 0$ we define $CT(n)$ to be the following universal
sentence of $L_{0}.$

$\displaystyle\forall
x_{1},x_{2},x_{3},w_{1},...,w_{n}~{}((([w_{1},...,w_{n},x_{2}]$
$\displaystyle\neq$ $\displaystyle
1)\wedge(([x_{1},x_{2}]=1)\wedge([x_{2},x_{3}]=1))$ $\displaystyle\rightarrow$
$\displaystyle([x_{1},x_{3}]=1)).$

The interpretation of $CT(n)$ in any group $G$ is that the relation of
commutativity is transitive on $G\backslash Z_{n}(G)$ where $Z_{n}(G)$ is the
$n$-th term of the upper central series of $G$.

Equivalently, it asserts that the centralizer of any element $g\in G\backslash
Z_{n}(G)$ is abelian. It was shown in [2] that the free $c$-nilpotent groups
satisfy $CT(c-1)$. Questions 5–5 below are also due to A.G. Myasnikov.

Does $Q(H)\cup\\{NZCT\\}$ axiomatize $S_{2}=Th_{\forall}^{0}(H)$?

A positive answer to Question 4 would imply a positive answer to Question 5.

Let $s\geq 2$ and let $G=F_{s}(\mathcal{N}_{2})$. Does
$Q(G)\cup\text{diag}(G)\cup\\{NZCT\\}$ axiomatize $Th_{\forall}(G)$?

More generally -

Let $c\geq 2$ and $r=\max\\{2,c-1\\}$. Let $G=F_{n}(\mathcal{N}_{c})$. Does
$Q^{0}(G)\cup\\{CT(c-1)\\}$ axiomatize $S_{c}$?

Let $c\geq 2$ and $s\geq r=\max\\{2,c-1\\}$. Let $G=F_{s}(\mathcal{N}_{c})$.
Does $Q(G)\cup diag(G)\cup\\{CT(c-1)\\}$ axiomatize $Th_{\forall}(G)$?

Let $\theta$ be an indeterminate over $\mathbb{Z}$ . Must every finitely
generated model of $Th_{\forall}(H)$ $H$-embed in
$UT_{3}(\mathbb{Z}[\theta])$?

## References

  * [1] J. L. Bell and A. B. Slomson.  Models and ultraproducts: An introduction.  North-Holland Publishing Co., Amsterdam-London, 1969.
  * [2] Benjamin Fine, Anthony Gaglione, Alexei Myasnikov, Gerhard Rosenberger, and Dennis Spellman.  The elementary theory of groups, volume 60 of De Gruyter Expositions in Mathematics.  De Gruyter, Berlin, 2014.  A guide through the proofs of the Tarski conjectures.
  * [3] Anthony M. Gaglione and Dennis Spellman.  The persistence of universal formulae in free algebras.  Bull. Austral. Math. Soc., 36(1):11–17, 1987.
  * [4] Anthony M. Gaglione and Dennis Spellman.  Some model theory of the Heisenberg group: I.  In Elementary theory of groups and group rings, and related topics, De Gruyter Proc. Math., pages 33–46. De Gruyter, Berlin, 2020.
  * [5] Anthony M. Gaglione and Dennis Spellman.  Some model theory of the Heisenberg group: III. Enter Mal’cev.  Far E. J. of Math. Sci., 138:1–15, 2022.
  * [6] G. Grätzer and H. Lakser.  A note on the implicational class generated by a class of structures.  Canad. Math. Bull., 16:603–605, 1973.
  * [7] A. I. Mal’cev.  On a correspondence between rings and groups.  Mat. Sb. (N.S.), 50(92):257–266, 1960 (English transl., Amer. Math. Soc. Trans (2) 45 (1965), 221-231).
  * [8] Hanna Neumann.  Varieties of groups.  Springer-Verlag New York, Inc., New York, 1967.
  * [9] Vladimir Remeslennikov and Ralph Stöhr.  On algebraic sets over metabelian groups.  J. Group Theory, 8(4):491–513, 2005.
  * [10] Saharon Shelah.  Every two elementarily equivalent models have isomorphic ultrapowers.  Israel J. Math., 10:224–233, 1971.