11institutetext: LMAM & School of Mathematical Sciences, Peking University
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Non-Termination Sets of Simple Linear Loops

Liyun Dai  Bican Xia
Corresponding author

###### Abstract

A simple linear loop is a simple while loop with linear assignments and linear
loop guards. If a simple linear loop has only two program variables, we give a
complete algorithm for computing the set of all the inputs on which the loop
does not terminate. For the case of more program variables, we show that the
non-termination set cannot be described by Tarski formulae in general.

###### Keywords:

Simple linear loop, termination, non-termination set, eigenvalue, Tarski
formula

##  1 Introduction

Termination of programs is an important property of programs and one of the
main research topics in the field of program verification. It is well known
that the following so-called “uniform halting problem” is undecidable in
general.

Using only a finite amount of time, determine whether a given program will
always finish running or could execute forever.

However, there are some well known techniques for deciding termination of some
special kinds of programs. A popular technique is to use ranking functions. A
ranking function for a loop maps the values of the loop variables to a well-
founded domain; further, the values of the map decrease on each iteration. A
linear ranking function is a ranking function that is a linear combination of
the loop variables and constants. Some methods for the synthesis of ranking
functions and some heuristics concerning how to automatically generate linear
ranking functions for linear programs have been proposed, for example, in
Colón and Sipma [3], Dams et al. [4] and Podelski and Rybalchenko [6].
Podelski and Rybalchenko [6] provided an efficient and complete synthesis
method based on linear programming to construct linear ranking functions. Chen
et al. [2] proposed a method to generate nonlinear ranking functions based on
semi-algebraic system solving. The existence of ranking function is only a
sufficient condition on the termination of a program. There are programs,
which terminate, but do not have ranking functions. Another popular technique
based on well-orders, presented in Lee et al. [5], is size-change principle.
The well-founded data can ensure that there are no infinitely descents, which
guarantees termination of programs.

For linear loops, some other methods based on calculating eigenvectors of
matrices have been proposed. Tiwari [7] proved that the termination problem of
a class of linear programs (simple loops with linear loop conditions and
updates) over the reals is decidable through Jordan form and eigenvector
computation. Braverman [1] proved that it is also decidable over the integers.
Xia et al. [8] considered the termination problems of simple loops with linear
updates and polynomial loop conditions, and proved that the termination
problem of such loops over the integers is undecidable. In [9], Xia et al.
provided a novel symbolic decision procedure for termination of simple linear
loops, which is as efficient as the numerical one given in [7].

A counter-example to termination is an infinite program execution. In program
verification, the search for counter-examples to termination is as important
as the search for proofs of termination. In fact, these are the two folds of
termination analysis of programs. Gupta et al. [10] proposed a method for
searching counter-examples to termination, which first enumerates lasso-shaped
candidate paths for counter-examples and proves the feasibility of a given
lasso by solving the existence of a recurrent set as a template-based
constraint satisfaction problem. Gulwani et al. [11] proposed a constraint-
based approach to a wide class of program analyses and weakest precondition
and strongest postcondition inference. The approach can be applied to
generating most-general counter-examples to termination.

In this paper, we consider the set of all inputs on which a given program does
not terminate. The set is called NT throughout the paper. For simple linear
loops, we are interested in whether the NT is decidable and how to compute it
if it is decidable. Similar problems was also considered in [12]. Our
contributions in this paper are as follows. First, for homogeneous linear
loops (see Section 2 for the definition) with only two program variables, we
give a complete algorithm for computing the NT. For the case of more program
variables, we show that the NT cannot be described by Tarski formulae in
general.

The rest of this paper is organized as follows. Section 2 introduces some
notations and basic results on simple linear loops. Section 3 presents an
algorithm for computing the NT of homogeneous linear loops with only two
program variables. The correctness of the algorithm is proved by a series of
lemmas. For linear loops with more than two program variables, it is proved in
Section 4 that the NT is not a semi-algebraic set in general, i.e., it cannot
be described by Tarski formulae in general. The paper is concluded in Section
5.

##  2 Preliminaries

In this paper, the domain of inputs of programs is ${\mathbb{R}}$, the field
of real numbers. A simple linear loop in general form over ${\mathbb{R}}$ can
be formulated as

${\tt P1}:\quad{\rm while}\ \left({B\vec{x}>\vec{b}}\right)\
\left\\{{\vec{x}:=A\vec{x}+\vec{c}}\right\\}$

where $\vec{b},\vec{c}$ are real vectors, $A_{n\times n},B_{m\times n}$ are
real matrices. $B\vec{x}>\vec{b}$ is a conjunction of $m$ linear inequalities
in $\vec{x}$ and $\vec{x}:=A\vec{x}+\vec{c}$ is a linear assignment on the
program variables $\vec{x}$.

###### Definition 1

[7] The non-termination set of a program is the set of all inputs on which the
program does not terminate. It is denoted by NT in this paper.

In particular,

${\rm NT}({\tt P1})=\\{\vec{x}\in{\mathbb{R}}^{n}|{\tt P1}\ {\rm does\ not\
terminate\ on}\ \vec{x}\\}\enspace.$

We list some related results in [7].

###### Proposition 1

[7] For a simple linear loop P1, the following is true.

  * •

The termination of P1 is decidable.

  * •

If $A$ has no positive eigenvalues, the NT is empty.

  * •

The NT is convex.

In this paper, only the following homogeneous case is considered.

${\tt P2}:\quad{\rm while}\ ({B\vec{x}>0})\ \\{\vec{x}:=A\vec{x}\\}\enspace.$

Let $B_{1},\ldots,B_{m}$ be the rows of $B$. Consider the following loops

$L_{i}:\quad{\rm while}\ (B_{i}\vec{x}>0)\ \\{\vec{x}:=A\vec{x}\\}\enspace.$

Obviously, NT(P2)=$\bigcap_{i=1}^{m}{\rm NT}(L_{i}).$ Therefore, without loss
of generality, we assume throughout this paper that $m=1$, i.e., there is only
one inequality as the loop guard. The following is a simple example of such
loops.

${\rm while}\ (4x_{1}+x_{2}>0)\quad\left\\{\left(\begin{array}[]{c}x_{1}\\\
x_{2}\end{array}\right):=\left(\begin{array}[]{cc}-2&4\\\
4&0\end{array}\right)\left(\begin{array}[]{c}x_{1}\\\
x_{2}\end{array}\right)\right\\}\enspace.$

That is $B=(4,1),A=\left(\begin{array}[]{cc}-2&4\\\
4&0\end{array}\right)\enspace.$

##  3 Two-variable case

To make things clear, we restate the problem for this two-variable case as
follows.

For a given homogeneous linear loop P2 with exactly two program variables and
only one inequality as the loop guard, compute NT(P2).

For simplicity, we denote the program variables by $x_{1},x_{2}$ and use NT
instead of NT(P2) in this section. If $\vec{\alpha}$ is a non-zero point in
the plane, we denote by $\overrightarrow{\vec{\alpha}}$ a ray starting from
the origin of plane and going through the point $\vec{\alpha}$.

###### Proposition 2

NT must be one of the following:
(1) an empty set;
(2) a ray starting from the origin;
(3) a sector between two rays starting from the origin.

###### Proof

We view an input $(x_{1},x_{2})$ as a point in the real plane with origin $O$.
If there exists a point $M(x_{1},x_{2})\in$ NT, any point $\vec{P}$ on the ray
$\overrightarrow{\vec{OM}}$ can be written as $\vec{P}=kM=(kx_{1},kx_{2})$ for
a positive number $k$. So
$BA^{n}(kx_{1},kx_{2})^{T}=k^{n}BA^{n}(x_{1},x_{2})^{T}>0$ for any
$n\in{\mathbb{N}}$. That means $\vec{P}\in{\rm NT}$. Therefore, it is clear
from the item 3 of Proposition 1 that the conclusion is true.

By the above proposition, the key point for computing the NT is to compute the
ray(s) which is (are) the boundary of NT. We give the following algorithm to
compute the ray(s) (and thus the NT) for P2 if the NT is not empty. The
algorithm, as can be expected, is mainly based on the computation of
eigenvalues and eigenvectors of $A$. The correctness of our algorithm will be
proved by a series of lemmas following the algorithm.

Input: Matrices $A_{2\times 2}$ and $B_{1\times 2}$.

Output: The NT of P2 with $A$ and $B$.

1 if  _$A={\bf 0}$ or $B={\bf 0}$_ then

2 return $\emptyset$;

3Compute the eigenvalues of $A$ and denote them by $\lambda_{1},\lambda_{2}$;

4 if  _$\lambda_{1}\ngtr 0\wedge\lambda_{2}\ngtr 0$_ then

5 return $\emptyset$; // Proposition 1

6Take $\vec{\alpha_{0}}\in{\mathbb{R}}^{2}\setminus\\{0\\}$ such that
$B\vec{\alpha_{0}}=0$ and $BA\vec{\alpha_{0}}\geq 0$;

7 if  _$BA\vec{\alpha_{0}}=0$_ then

8 choose $\vec{\xi}$ such that $B\vec{\xi}>0$

9 if  _$B(A\vec{\xi}) >0$_ then

10 return $\\{\vec{x}|\vec{x}\in{\mathbb{R}}^{2},B\vec{x}>0\\}$ // Lemma 4

11 else

12 return $\emptyset$ // Lemma 5

13

14if  _$\lambda_{1}=0\vee\lambda_{2}=0$_ then

15 return $\\{\vec{x}|\vec{x}\in{\mathbb{R}}^{2},B\vec{x}>0,BA\vec{x}>0\\}$;
// Lemma 6

16Suppose $\lambda_{1}\geq\lambda_{2}$

17 if  _$\lambda_{1}\geq\lambda_{2} >0$_ then

18 choose an eigenvector $\vec{\beta_{2}}$ related to $\lambda_{2}$ such that
$B\vec{\beta_{2}}\geq 0$;

19 return
$\\{\vec{x}|\vec{x}=k_{1}\vec{\alpha_{0}}+k_{2}\vec{\beta_{2}},k_{1}\geq
0,k_{2}>0\\}$; // Lemmas 7 and 8

20if  _$\lambda_{1} >0\wedge\lambda_{2}<0$_ then

21 if  _$\lambda_{1}\geq|\lambda_{2}|$_ then

22 let $\vec{\alpha_{-1}}=A^{-1}\vec{\alpha_{0}}$ and return
$\\{\vec{x}|\vec{x}=k_{1}\vec{\alpha_{0}}+k_{2}\vec{\alpha_{-1}},k_{1}>0,k_{2}>0\\}$;

23 if  _$\lambda_{1} <|\lambda_{2}|$_ then

24 choose an eigenvector $\vec{\beta}$ related to $\lambda_{1}$ such that
$B\vec{\beta}>0$ and

25 return $\\{\vec{x}|\vec{x}=k\vec{\beta},k>0\\}$ // Lemma 10

26

Algorithm 1 NonTermination Figure 1: Lemma 1

###### Lemma 1

Suppose NT is not empty and $\partial{\rm NT}$ is the boundary of NT. If
$\vec{x}\in\partial{\rm NT}$ and $B\vec{x}\neq 0$, then
$A\vec{x}\in\partial{\rm NT}$.

###### Proof

Obviously, $B$ is a linear map from ${\mathbb{R}}^{2}$ to ${\mathbb{R}}$ .
Because $B\vec{y}>0$ for all $\vec{y}\in{\rm NT}$, we have $B\vec{x}\geq 0$.
And thus $B\vec{x}>0$ by the assumption that $B\vec{x}\neq 0$. Hence, there
exists an open ball $o_{1}(\vec{x},r_{1})$ such that $B\vec{y}>0$ for all
$\vec{y}\in o_{1}(\vec{x},r_{1}).$

Let $F$ be the linear map from ${\mathbb{R}}^{2}$ to ${\mathbb{R}}^{2}$ that
$F(\vec{y})=A\vec{y}$ for any $\vec{y}\in{\mathbb{R}}^{2}$ and hence $F$ is
continuous. So for any neighborhood $o(A\vec{x},r)$ of $A\vec{x}$, there
exists a positive real number $r_{2}$ such that $o_{2}(\vec{x},r_{2})\subseteq
o_{1}(\vec{x},r_{1})$ and $F(o_{2}(\vec{x},r_{2}))\subseteq o(A\vec{x},r).$
Because $\vec{x}\in\partial{\rm NT}$, there exist $\vec{y},\vec{z}\in
o_{2}(\vec{x},r_{2})$ such that $\vec{y}\in{\rm NT}$ and $\vec{z}\notin{\rm
NT}$. Then $A(\vec{y})$, $A(\vec{z})\in o(A\vec{x},r)$, $A\vec{(y})\in{\rm
NT}$ and $A(\vec{z})\notin{\rm NT}$. It is followed that there are both
terminating and non-terminating inputs in any neighborhood of $A\vec{x}$.
Therefore, $A\vec{x}\in\partial{\rm NT}$.

Figure 2: Lemma 2

###### Lemma 2

Suppose NT is neither empty nor a ray and $\partial{\rm NT}\
\cap\\{\vec{x}|B\vec{x}=0\\}=\\{(0,0)\\}$. If $B\vec{y}=0$ and $BA\vec{y}>0$,
then $A\vec{y}\in{\rm NT}$.

###### Proof

By Proposition 2, $\partial{\rm NT}$ consists of two rays. Let $l_{1},l_{2}$
be the two rays. Since neither $l_{1}$ nor $l_{2}$ is on $Bx=0$, $l_{1}$ and
$l_{2}$ are not collinear. So we can choose two points $\vec{z}\in l_{1}$ and
$\vec{v}\in l_{2}$ such that $B\vec{z}>0$, $B\vec{v}>0$ and
$\vec{y}=t_{1}\vec{z}+t_{2}\vec{v}$ for some
$t_{1}\in{\mathbb{R}},t_{2}\in{\mathbb{R}}$. By Lemma 1, $A\vec{z}$ and
$A\vec{v}$ must be on the boundary of NT, i.e., $l_{1}$ or $l_{2}$. Thus, we
have at most four possible cases as follows.

  * (1)

$A\vec{z}=k_{1}\vec{z},A\vec{v}=k_{2}\vec{v},$ (i.e., $A\vec{z}\in
l_{1},A\vec{v}\in l_{2}$)

  * (2)

$A\vec{z}=k_{1}\vec{z},A\vec{v}=k_{2}\vec{z},$ (i.e., $A\vec{z}\in
l_{1},A\vec{v}\in l_{1}$)

  * (3)

$A\vec{z}=k_{1}\vec{v},A\vec{v}=k_{2}\vec{v},$ (i.e., $A\vec{z}\in
l_{2},A\vec{v}\in l_{2}$)

  * (4)

$A\vec{z}=k_{1}\vec{v},A\vec{v}=k_{2}\vec{z},$ (i.e., $A\vec{z}\in
l_{2},A\vec{v}\in l_{1}$)

where $k_{1}>0,k_{2}>0$.

Case (1). Because $B\vec{y}=t_{1}B\vec{z}+t_{2}B\vec{v}=0$ and

$BA\vec{y}=BA(t_{1}\vec{z}+t_{2}\vec{v})=t_{1}k_{1}B\vec{z}+t_{2}k_{2}B\vec{v}>0,$

we have $t_{1}t_{2}<0$. Without loss of generality, assume that $t_{1}>0$ and
$t_{2}<0$. We denote $t_{1}B\vec{z}$ by $P$. Note that $P>0$ and
$t_{2}B\vec{v}=-P$. Since $BA\vec{y}=(k_{1}-k_{2})P>0$, we have
$k_{1}>k_{2}>0$ and

$BA^{n}(A\vec{y})=k_{1}^{n+1}t_{1}B\vec{z}+k_{2}^{n+1}t_{2}B\vec{v}=k_{1}^{n+1}P-k_{2}^{n+1}P>0$

for any $n\in\mathbb{N}$. By the definition of ${\rm NT}$, $A\vec{y}\in{\rm
NT}$.

Case (2). Because $BA\vec{y}=(t_{1}k_{1}+t_{2}k_{2})B\vec{z}>0$, we have

$BA^{n}(A\vec{y})=k_{1}^{n}(t_{1}k_{1}+t_{2}k_{2})B\vec{z}>0$

for any $n\in\mathbb{N}.$ By the definition of NT, we have $A\vec{y}\in{\rm
NT}$.

Case (3). Similarly as Case (2), we can prove $A\vec{y}\in{\rm NT}$.

Case (4). We shall show that this case cannot happen. Let

$S=\\{\vec{x}|\vec{x}=r_{1}\vec{y}+r_{2}A\vec{y},r_{1}>0,r_{2}>0\\}$

be the sector between the two rays $\overrightarrow{\vec{y}}$ and
$\overrightarrow{\vec{Ay}}$. For any $\vec{w}\in S$, we have
$B\vec{w}=r_{1}B\vec{y}+r_{2}BA\vec{y}=r_{2}BA\vec{y}>0$.

Because

$A^{2}\vec{y}=A(t_{1}k_{1}\vec{v}+t_{2}k_{2}\vec{z})=t_{1}k_{1}k_{2}\vec{z}+t_{2}k_{1}k_{2}\vec{v}=k_{1}k_{2}\vec{y},$

we have
$A\vec{w}=r_{1}A\vec{y}+r_{2}A^{2}\vec{y}=r_{1}A\vec{y}+r_{2}k_{1}k_{2}\vec{y}\in
S$. Therefore, $\vec{w}\in{\rm NT}$ and $S\subseteq{\rm NT}$. As
$\overrightarrow{\vec{y}}$ is a boundary of $S$ and $B\vec{y}=0$,
$\overrightarrow{\vec{y}}$ is contained in $\partial{\rm NT}$, which
contradicts with the assumption of the lemma. So (4) cannot happen.

In summary, $A\vec{y}\in{\rm NT}$.

Figure 3: Lemma 3

###### Lemma 3

If $\partial{\rm NT}$ is composed of two rays $l_{1}$ and $l_{2}$, then either
$l_{1}$ or $l_{2}$ is on $B\vec{x}=0$.

###### Proof

Assume neither $l_{1}$ nor $l_{2}$ is on $B\vec{x}=0$. Choose a point
$\vec{y}$ such that $\vec{y}\neq\bf{0}$ , $B\vec{y}=0$ and $BA\vec{y}\geq 0$.

Suppose $BA\vec{y}=0$. As ${\rm NT}$ is not empty, there exists
$\vec{z}\in{\rm NT}$. Hence $A\vec{y}$ can be rewritten as
$A\vec{y}=h_{1}\vec{z}+h_{2}\vec{y}$ for some
$h_{1}\in{\mathbb{R}},h_{2}\in{\mathbb{R}}$. As a result of
$BA\vec{y}=h_{1}B\vec{z}+h_{2}B\vec{y}=h_{1}B\vec{z}=0$, $h_{1}=0$. Note that

$A^{n}\vec{y}=h_{2}^{n}\vec{y},BA^{n}\vec{y}=h_{2}^{n}B\vec{y}=0\enspace.$ (1)

According to Eq.(1) and $\vec{z}\in{\rm NT}$, we have
$BA^{n}(k_{1}\vec{z}+k_{2}\vec{y})=k_{1}BA^{n}\vec{z}+k_{2}BA^{n}\vec{y}=k_{1}BA^{n}\vec{z}>0$
for any $k_{1}>0,n\in\mathbb{N}$. Hence
$\\{\vec{x}|\vec{x}=k_{1}\vec{z}+k_{2}\vec{y},k_{1}>0\\}\subseteq{\rm NT}$.
Therefore, $\\{\vec{x}|B\vec{x}=0\\}=\partial{\rm NT}$, which contradicts with
the assumption.

If $BA\vec{y}>0$, $A\vec{y}\in{\rm NT}$ follows from Lemma 2. Let
$S=\\{\vec{x}|k_{1}\vec{y}+k_{2}A\vec{y},k_{1}>0,k_{2}>0\\}$. And we have
$BA^{n}\vec{z}=k_{1}BA^{n}y+k_{2}BA^{n+1}\vec{y}>0$ for any $n\in\mathbb{N}$,
$\vec{z}\in S$. Thus $\vec{z}\in{\rm NT}$ and $S\subseteq{\rm NT}$. By the
method of choosing $\vec{y}$, $\overrightarrow{\vec{y}}\subseteq\partial{\rm
NT}$. That means $\overrightarrow{\vec{y}}$ is $l_{1}$ or $l_{2}$, which
contradicts with the assumption.

###### Lemma 4

Suppose $A$ has positive eigenvalues and has an eigenvector $\vec{\alpha}$
satisfying $B\vec{\alpha}=0$. If $\vec{\xi}$ is a vector such that
$B\vec{\xi}>0$ and $BA\vec{\xi}>0$, then ${\rm NT}=\\{\vec{x}|B\vec{x}>0\\}$.

###### Proof

For any $\vec{y}\in\\{\vec{x}|B\vec{x}>0\\}$, it can be written as
$\vec{y}=k_{1}\vec{\xi}+k_{2}\vec{\alpha}$ for some
$k_{1}\in{\mathbb{R}},k_{2}\in{\mathbb{R}}$. As
$B\vec{y}=k_{1}B\vec{\xi}+k_{2}B\vec{\alpha}=k_{1}B\vec{\xi}>0$, we have
$k_{1}>0$. Thus
$BA\vec{y}=k_{1}BA\vec{\xi}+k_{2}BA\vec{\alpha}=k_{1}BA\vec{\xi}>0$ and
$A\vec{y}\in\\{\vec{x}|B\vec{x}>0\\}$. By the definition of ${\rm NT}$, we
have $\\{\vec{x}|B\vec{x}>0\\}\subseteq{\rm NT}$ and hence ${\rm
NT}=\\{\vec{x}|B\vec{x}>0\\}$.

###### Lemma 5

Suppose $A$ has positive eigenvalues and has an eigenvector $\vec{\alpha}$
satisfying $B\vec{\alpha}=0$. If there is a vector $\vec{\xi}$ such that
$B\vec{\xi}>0$ and $BA\vec{\xi}\leq 0$, then ${\rm NT}=\emptyset$.

###### Proof

For any $\vec{y}\in\\{\vec{x}|B\vec{x}>0\\},$ it can be written as
$\vec{y}=k_{1}\vec{\alpha}+k_{2}\vec{\xi}$ for some
$k_{1}\in{\mathbb{R}},k_{2}\in{\mathbb{R}}$. Since
$B\vec{y}=k_{2}B\vec{\xi}>0$, we have $k_{2}>0$. And because
$BA\vec{y}=k_{2}BA\vec{\xi}\leq 0$, ${\rm NT}=\emptyset$.

###### Lemma 6

Suppose $A$ has a positive eigenvalue and a zero eigenvalue. If $\vec{\gamma}$
is an eigenvector related to the positive eigenvalue such that
$B\vec{\gamma}>0$, then ${\rm NT}=\\{\vec{x}|B\vec{x}>0,BA\vec{x}>0\\}.$

###### Proof

Let $\vec{\beta}$ be an eigenvector with respect to eigenvalue 0 and $\lambda$
be the positive eigenvalue. Let $S$ be the set
$\\{\vec{x}|B\vec{x}>0,BA\vec{x}>0\\}$. For any $\vec{y}\in S$, it can be
written as $k_{1}\vec{\beta}+k_{2}\vec{\gamma}$ for some
$k_{1}\in{\mathbb{R}},k_{2}\in{\mathbb{R}}$. We have $BA\vec{y}=k_{2}\lambda
B\vec{\gamma}>0$, thus $k_{2}>0$. Note that
$BA^{n}\vec{y}=k_{2}\lambda^{n}\vec{\gamma}>0$ for any $n\in\mathbb{N}$, hence
$S\subseteq{\rm NT}$. Because $\\{\vec{x}|B\vec{x}\leq 0\vee BA\vec{x}\leq
0\\}\cap{\rm NT}=\emptyset$, ${\rm NT}=\\{\vec{x}|B\vec{x}>0,BA\vec{x}>0\\}$.

###### Lemma 7

Suppose $A$ has two positive eigenvalues $\lambda_{1}>\lambda_{2}>0$ and two
eigenvectors $\vec{\beta_{1}}$ and $\vec{\beta_{2}}$ related to $\lambda_{1}$
and $\lambda_{2}$, respectively, such that
$B\vec{\beta_{1}}>0,B\vec{\beta_{2}}>0$. If $\vec{\alpha}$ is a vector such
that $B\vec{\alpha}=0$ and $BA\vec{\alpha}>0$, then ${\rm
NT}=\\{\vec{x}|\vec{x}=k_{1}\vec{\alpha}+k_{2}\vec{\beta_{2}},k_{1}\geq
0,k_{2}>0\\}.$

###### Proof

It is easy to know $\vec{\beta_{1}},\vec{\beta_{2}}\in{\rm NT}$, thus NT is
neither empty nor a ray. By Lemma 3 there is a
$\overrightarrow{\vec{y}}\subseteq\partial{\rm NT}$ and $\vec{y}$ satisfies
$B\vec{y}=0$. Since for any $\vec{z}\in\partial{\rm NT}$, we have
$BA\vec{z}\geq 0$. So $BA\vec{y}\geq 0$ and hence
$\overrightarrow{\vec{\alpha}}=\overrightarrow{\vec{y}}$. In other word,
$\overrightarrow{\vec{\alpha}}$ is one ray of $\partial{\rm NT}$. Let the
other ray of $\partial{\rm NT}$ be $l$. As $-BA\vec{\alpha}<0$,
$\overrightarrow{\vec{-\alpha}}$ is not $l$. By Lemma 1, we have
$Al\in\partial{\rm NT}$. So $l$ is one of
$\overrightarrow{\vec{\beta_{1}}},\overrightarrow{\vec{\beta_{2}}}$ and
$\overrightarrow{\vec{A^{-1}}\alpha}$. By directly checking, we know
$\overrightarrow{\vec{\beta_{2}}}$ is $l$ and so ${\rm
NT}=\\{\vec{x}|\vec{x}=k_{1}\vec{\alpha}+k_{2}\vec{\beta_{2}},k_{1}\geq
0,k_{2}>0\\}$.

###### Lemma 8

Assume that $A$ has one positive eigenvalue $\lambda$ with multiplicity $2$
and only one eigenvector $\vec{\beta}$ satisfying $B\vec{\beta}>0$. If
$\vec{\alpha}$ is a vector such that $B\vec{\alpha}=0$ and $BA\vec{\alpha}>0$,
then ${\rm NT}=\\{\vec{x}|\vec{x}=h_{1}\vec{\alpha}+h_{2}\vec{\beta},k_{1}\geq
0,k_{2}>0\\}$.

###### Proof

By the theory of Jordan normal form in linear algebra, there exists a vector
$\vec{\beta_{1}}$ such that
$A\vec{\beta_{1}}=\vec{\beta}+\lambda\vec{\beta_{1}}$ and $\vec{\beta}$ and
$\vec{\beta_{1}}$ are linearly independent.

Let $\vec{\alpha_{1}}=A\vec{\alpha}$. We claim that

$\forall n\in\mathbb{N}.(BA^{n}\vec{\alpha_{1}}>0\wedge\exists
h_{2}>0.(A^{n}\vec{\alpha_{1}}=h_{1}\vec{\beta}+h_{2}\vec{\beta_{1}})).$ (2)

To prove this claim we use induction on the value of $n$.

Suppose $\vec{\alpha}=h_{1}\vec{\beta}+h_{2}\vec{\beta_{1}}$. If $n=0$, then
$\vec{\alpha_{1}}=A\vec{\alpha}=(h_{1}\lambda+h_{2})\vec{\beta}+h_{2}\lambda\vec{\beta_{1}}$.
Because $B\vec{\alpha_{1}}=\lambda
B\vec{\alpha}+h_{2}B\vec{\beta}=h_{2}B\vec{\beta}>0$, we have $h_{2}>0$.

Now assume that the claim is true for $n-1$. Let
$A^{n-1}\vec{\alpha_{1}}=h_{1}\vec{\beta}+h_{2}\vec{\beta_{1}}$ where
$h_{2}>0$. Because $A^{n}\vec{\alpha_{1}}=A(A^{n-1}\vec{\alpha_{1}})=(\lambda
h_{1}+h_{2})\vec{\beta}+\lambda h_{2}\vec{\beta_{1}}$, we have $\lambda
h_{2}>0$ and $BA^{n}\vec{\alpha_{1}}=\lambda
BA^{n-1}\vec{\alpha_{1}}+h_{2}B\vec{\beta}>0$. So the claim is true for any
$n\in\mathbb{N}$ and we have $\vec{\alpha_{1}}\in{\rm NT}$.

Obviously, $\vec{\beta}\in{\rm NT}$ and $\vec{\beta}$ and $\vec{\alpha_{1}}$
are linearly independent, so NT is not a ray. By Lemma 3,
$\overrightarrow{\vec{\alpha}}\subseteq\partial{\rm NT}$.

Let the other ray of $\partial{\rm NT}$ be $l$. As $-BA\vec{\alpha}<0$,
$\overrightarrow{\vec{-\alpha}}$ is not $l$. By Lemma 1, $Al=l$ or
$Al=\overrightarrow{\vec{\alpha}}$. So $l$ must be
$\overrightarrow{\vec{\beta}}$ or $\overrightarrow{\vec{A^{-1}\alpha}}$. By
directly checking, we know $l$ is $\overrightarrow{\vec{\beta}}$ and thus
${\rm NT}=\\{\vec{x}|\vec{x}=k_{1}\vec{\alpha}+k_{2}\vec{\beta},k_{1}\geq
0,k_{2}>0\\}$.

###### Lemma 9

Suppose $A$ has a positive eigenvalue $\lambda_{1}$ and a negative eigenvalue
$\lambda_{2}$ with $\lambda_{1}\geq|\lambda_{2}|$ and two eigenvectors
$\vec{\beta_{1}}$ and $\vec{\beta_{2}}$ related to $\lambda_{1}$ and
$\lambda_{2}$, respectively, such that
$B\vec{\beta_{1}}>0,B\vec{\beta_{2}}>0$. Suppose $\vec{\alpha}$ is a vector
such that $B\vec{\alpha}=0$ and $BA\vec{\alpha}>0$. Let
$\vec{\alpha_{-1}}=A^{-1}\vec{\alpha}$, $\vec{\alpha_{1}}=A\vec{\alpha}$. Then
${\rm NT}=\\{k_{1}\vec{\alpha}+k_{2}\vec{\alpha_{-1}},k_{1}>0,k_{2}>0\\}$.

###### Proof

Let $\vec{\alpha_{-1}}=h_{1}\vec{\beta_{1}}+h_{2}\vec{\beta_{2}}$. So
$\vec{\alpha}=A\vec{\alpha_{-1}}=h_{1}\lambda_{1}\vec{\beta_{1}}+h_{2}\lambda_{2}\vec{\beta_{2}}$
and
$\vec{\alpha_{1}}=A\vec{\alpha}=h_{1}\lambda_{1}^{2}\vec{\beta_{1}}+h_{2}\lambda_{2}^{2}\vec{\beta_{2}}$.
Because $B\vec{\alpha}=0$ and $B\vec{\alpha_{1}}>0$, $h_{1}$, $h_{2}$ and
$A\vec{\alpha_{-1}}$ are all positive.

Note that
$\vec{\alpha_{1}}=(-\lambda_{1}\lambda_{2})\vec{\alpha_{-1}}+(\lambda_{1}+\lambda_{2})\vec{\alpha}$
where $-\lambda_{1}\lambda_{2}>0$ and $\lambda_{1}+\lambda_{2}\geq 0$. Let
$S=\\{\vec{x}|\vec{x}=k_{1}\vec{\alpha}+k_{2}\vec{\alpha_{-1}}$, $k_{1}>0$,
$k_{2}>0\\}$. Since $B\vec{y}=k_{2}B\vec{\alpha_{-1}}>0$ and
$A\vec{y}=(k_{2}+k_{1}(\lambda_{1}+\lambda_{2}))\vec{\alpha}-k_{1}\lambda_{1}\lambda_{2}\vec{\alpha_{-1}}\in
S$ for any $\vec{y}\in S$, we have ${\rm NT}\supseteq S$.

Let $\vec{y}=k_{1}\vec{\alpha}+k_{2}\vec{\alpha_{-1}}$. Because
$B\vec{y}=k_{2}B\vec{\alpha_{-1}}\leq 0$ for any $k_{2}\leq 0$ and
$BA\vec{y}=k_{1}B\vec{\alpha_{1}}\leq 0$ for any $k_{1}\leq 0$, we have ${\rm
NT}=S$.

###### Lemma 10

Suppose A has a positive eigenvalue $\lambda_{1}$ and a negative eigenvalue
$\lambda_{2}$ such that $\lambda_{1}<|\lambda_{2}|$. If there are two
eigenvectors $\vec{\beta_{1}}$ and $\vec{\beta_{2}}$ related to $\lambda_{1}$
and $\lambda_{2}$, respectively, such that $B\vec{\beta_{1}}>0$ and
$B\vec{\beta_{2}}>0$, then ${\rm
NT}=\\{\vec{x}|\vec{x}=k\vec{\beta_{1}},k>0\\}$.

###### Proof

Consider any
$\vec{\beta}=k_{1}\vec{\beta_{1}}+k_{2}\vec{\beta_{2}}\in{\mathbb{R}}^{2}$.

If $k_{2}\neq 0$, because
$A^{n}(k_{1}\vec{\beta_{1}}+k_{2}\vec{\beta_{2}})=k_{1}\lambda_{1}^{n}\vec{\beta_{1}}+k_{2}\lambda_{2}^{n}\vec{\beta_{2}}$
and

$BA^{n}(k_{1}\vec{\beta_{1}}+k_{2}\vec{\beta_{2}})BA^{n+1}(k_{1}\vec{\beta_{1}}+k_{2}\vec{\beta_{2}})<0$

when $n$ is large enough, $k_{1}\vec{\beta_{1}}+k_{2}\vec{\beta_{2}}\notin{\rm
NT}$.

If $k_{2}=0$, obviously, ${\rm
NT}\supseteq\\{\vec{x}|\vec{x}=k\vec{\beta_{1}},k>0\\}$ and
$Bk\vec{\beta_{1}}\ \not\in{\rm NT}$ for any $k\leq 0$.

So ${\rm NT}=\\{\vec{x}|\vec{x}=k\vec{\beta_{1}},k>0\\}$.

Now, the correctness of our algorithm NonTermination can be easily obtained as
follows.

###### Theorem 3.1

The algorithm NonTermination is correct.

###### Proof

First, the termination of NonTermination is obvious because there are no loops
and no iterations in it. Second, it is also clear that the algorithm discusses
all the cases of eigenvalues of $A$, respectively. According to Lemmas 4-10
(each of them corresponds to a certain case in the algorithm as commented in
the algorithm), the output of the algorithm in each case is correct.

###### Example 1

Compute the NT of the following loop.

${\rm while}~{}(4x_{1}+x_{2}>0)\quad\left\\{\left(\begin{array}[]{c}x_{1}\\\
x_{2}\\\ \end{array}\right)=\left(\begin{array}[]{cc}-2&4\\\ 4&0\\\
\end{array}\right)\left(\begin{array}[]{c}x_{1}\\\ x_{2}\\\
\end{array}\right)\right\\}$

Herein, $B=(4,1),A=\left(\begin{array}[]{cc}-2&4\\\ 4&0\\\
\end{array}\right).$

The computation of NonTermination on the loop is:

Line 1. $B\neq 0$ and $A\neq 0$.

Line 4. $A$ has a positive eigenvalue $-1+\sqrt{17}$.

Line 6. Let
$\vec{\alpha_{0}}=(-1,4)^{T},\vec{\alpha_{1}}=A\vec{\alpha_{0}}=(18,-4)^{T}$.

Line 7. $B\vec{\alpha_{1}}=68\neq 0$.

Line 13. The two eigenvalues of $A$ are $-1+\sqrt{17},-1-\sqrt{17}$,
respectively. Neither of them is $0$.

Line 19. $A$ has two eigenvalues, of which one is positive and the other
negative.

Line 20. The absolute value of the negative eigenvalue is greater than the
positive eigenvalue.

Line 22. The eigenvector with respect to the positive eigenvalue is
$\vec{\beta}=(1,\frac{\sqrt{17}+1}{4})^{T}$ and $B\vec{\beta}>0$. Return
$\\{\vec{x}|\vec{x}=k\vec{\beta},k>0\\}$.

##  4 More variables

###### Theorem 4.1

In general, NT is not a semi-algebraic set.

###### Remark 1

All Tarski formulae are in the form of conjunctions or/and disjunctions of
polynomial equalities and/or inequalities, so, in other words, semi-algebraic
sets are exactly the sets defined by Tarski formulae. By Theorem 4.1, we can
conclude that the non-termination sets of linear loops with more than two
variables cannot be defined by Tarski formulae in general.

###### Remark 2

It should be noticed that all polynomial invariants are semi-algebraic sets.

In order to prove the above theorem, we give an example to demonstrate its NT
is not a semi-algebraic set.

###### Proposition 3

Let a linear loop with three program variables be as follows.

${\tt P3:}\ {\rm while}\ (x_{1}+2x_{2}+x_{3}\geq
0)\quad\left\\{\left(\begin{array}[]{c}x_{1}\\\ x_{2}\\\ x_{3}\\\
\end{array}\right)=\left(\begin{array}[]{ccc}2&0&0\\\ 0&3&0\\\ 0&0&5\\\
\end{array}\right)\left(\begin{array}[]{c}x_{1}\\\ x_{2}\\\ x_{3}\\\
\end{array}\right)\right\\}.$

Then NT(P3) is not a semi-algebraic set.

The conclusion can be proved by using the following lemmas. For simplicity,
NT(P3) is denoted by NT in this section.

###### Lemma 11

Denote by $\tau$ the following set

$\\{9(x_{1}^{2}+x_{2}^{2})-x_{3}^{2}<0,x_{3}>0\\},$

then $\tau\subseteq{\rm{\rm NT}}.$

###### Proof

For any $(x_{1},x_{2},x_{3})\in\tau$, we have $x_{3}>3|x_{1}|,x_{3}>3|x_{2}|$
and thus $x_{1}+2x_{2}+x_{3}>0.$ Because
$A(x_{1},x_{2},x_{3})^{T}=(2x_{1},3x_{2},5x_{3})^{T}$ and
$9(4x_{1}^{2}+9x_{2}^{2})-25x_{3}^{2}<0$, $A(x_{1},x_{2},x_{3})^{T}\in\tau$.
Therefore $\tau\subseteq{\rm{\rm NT}}$.

###### Lemma 12

$\partial{\rm NT}\subseteq{\rm NT}.$

###### Proof

Because the loop guard is of the form $B(x_{1},x_{2},x_{3})^{T}\geq 0$, NT is
a closed set. So the conclusion is correct. Furthermore, for any
$(x_{1},x_{2},x_{3})\in\partial{\rm NT},x_{1}+2x_{2}+x_{3}\geq 0.$

###### Lemma 13

If $(x_{1},x_{2},x_{3})\in{\rm NT}$ and
$A(x_{1},x_{2},x_{3})^{T}\in\partial{\rm NT}$, then
$(x_{1},x_{2},x_{3})\in\partial{\rm NT}.$

###### Proof

Let $\vec{x}=(x_{1},x_{2},x_{3})$. If the conclusion is not true, there exists
a ball $o(\vec{x},r)\subseteq{\rm NT}$. Because $A\vec{x}^{T}\in\partial{\rm
NT}$, there exists $\vec{x^{\prime}}$ such that
$|A\vec{x}-\vec{x^{\prime}}|<r$ and $\vec{x^{\prime}}$ is not in NT.

Since $|A^{-1}\vec{x^{\prime}}-\vec{x}|<|\vec{x^{\prime}}-A\vec{x}|<r$,
$A^{-1}\vec{x^{\prime}}\in o(\vec{x},r)$. So $A^{-1}\vec{x^{\prime}}\in{\rm
NT}$ and thus $\vec{x^{\prime}}\in{\rm NT}$, which is a contradiction.

###### Lemma 14

$\\{(\frac{1}{2^{n}},-\frac{1}{3^{n}},\frac{1}{5^{n}})\\}_{n=0}^{\infty}\subseteq\partial{\rm
NT}.$

###### Proof

Let $\vec{p}_{n}=(\frac{1}{2^{n}},-\frac{1}{3^{n}},\frac{1}{5^{n}}),n\geq 0.$
We use induction on the value of $n$.

When $n=0$, because $B\vec{p}_{0}=B(1,-1,1)^{T}=0$ and

$BA^{k}\vec{p}_{0}=2^{k}-2\times 3^{k}+5^{k}>0\ ~{}~{}{\rm for\ any}\
k\in{\mathbb{N}}^{+},$

we have $\vec{p}_{0}\in\partial{\rm NT}.$

Now assume that the conclusion holds for $n-1$. So,
$A\vec{p}_{n}=\vec{p}_{n-1}\in\partial{\rm NT}\subseteq{\rm NT}.$ By Lemma 13,
$\vec{p}_{n}\in\partial{\rm NT}$.

###### Lemma 15

For any non-zero polynomial
$f(x_{1},x_{2},x_{3})\in{\mathbb{R}}[x_{1},x_{2},x_{3}]$, there exists an $N$
such that $f(\frac{1}{2^{n}},-\frac{1}{3^{n}},\frac{1}{5^{n}})\neq 0$ for all
$n>N$.

###### Proof

Assume that the conclusion does not hold. Then there exists a subsequence
$\\{((\frac{1}{2})^{n_{k}},-(\frac{1}{3})^{n_{k}},(\frac{1}{5})^{n_{k}})\\}_{k=1}^{\infty}$
such that $f$ vanishes on each point of it.

Let
$f=b_{1}x_{1}^{\alpha_{1}}x_{2}^{\beta_{1}}x_{3}^{\gamma_{1}}+...+b_{s}x_{1}^{\alpha_{s}}x_{2}^{\beta_{s}}x_{3}^{\gamma_{s}}$
where $b_{i}\in\mathbb{R},b_{i}\neq
0,\alpha_{i}\in\mathbb{N},\beta_{i}\in\mathbb{N},\gamma_{i}\in\mathbb{N},$ and
$(\alpha_{i},\beta_{i},\gamma_{i})\neq(\alpha_{j},\beta_{j},\gamma_{j})$ for
$i\neq j.$

Obviously $s\geq 1$ because $f\not\equiv 0$. Let
$t_{i}=(\frac{1}{2})^{\alpha_{i}}(\frac{1}{3})^{\beta_{i}}(\frac{1}{5})^{\gamma_{i}}$.

It is an obvious fact that $2^{\alpha_{j}}3^{\beta_{j}}5^{\gamma_{j}}\neq
2^{\alpha_{i}}3^{\beta_{i}}5^{\gamma_{i}}$ for $i\neq j.$ Hence
$t_{1},t_{2},...,t_{s}$ are pairwise distinct. Without loss of generality, let
$t_{1}>t_{2}>...>t_{s}.$

For every $j>1,$ we have
$\lim\limits_{k\to\infty}{(\frac{t_{j}}{t_{1}})^{n_{k}}}=0$. Thus

$\lim\limits_{k\to\infty}{|\frac{f((\frac{1}{2})^{n_{k}},-(\frac{1}{3})^{n_{k}},(\frac{1}{5})^{n_{k}})}{((\frac{1}{2})^{\alpha_{1}}(\frac{1}{3})^{\beta_{1}}(\frac{1}{5})^{\gamma_{1}})^{n_{k}}}|=|b_{1}|}\neq
0\enspace.$

This contradicts with
$f((\frac{1}{2})^{n_{k}},-(\frac{1}{3})^{n_{k}},(\frac{1}{5})^{n_{k}})=0$.
Therefore the conclusion follows.

Using the above lemmas, we can now prove Theorem 4.1.

###### Proof

Denote by $S$ the sequence
$\\{(\frac{1}{2})^{n},-(\frac{1}{3})^{n},(\frac{1}{5})^{n})\\}$. By Lemma 14,
$S\subseteq\partial{\rm NT}.$

Assume ${\rm NT}$ is a semi-algebraic set. Then there exist finite many
polynomials $f_{i,j}\in\mathbb{R}[x_{1},x_{2},x_{3}]$ and
$\triangleleft_{i,j}\in\\{<,=\\}$ for $i=1,...,s$ and $j=1,...,r_{i}$ such
that

${\rm
NT}=\bigcup\limits_{i=1}^{s}\bigcap\limits_{j=1}^{r_{i}}\\{(x_{1},x_{2},x_{3})\in\mathbb{R}^{3}|f_{i,j}\triangleleft_{i,j}0\\}.$
(3)

Because $S\subseteq\partial{\rm NT}\subseteq\\{f_{i,j}=0\\}_{i,j}$, for any
$x\in S$, there exists a polynomial $f_{i,j}$ such that $f_{i,j}(x)=0$. By
pigeonhole principle there exists an $f_{i,j}$ and a subsequence $S_{1}$ of
$S$ such that $f_{i,j}$ vanishes on $S_{1}$, which contradicts with Lemma 15.

##  5 Conclusion

In this paper, we consider whether the NT of a simple linear loop is decidable
and how to compute it if it is decidable. For homogeneous linear loops with
only two program variables, we give a complete algorithm for computing the NT.
For the case of more program variables, we show that the NT cannot be
described by Tarski formulae in general.

## Acknowledgements

The work is partly supported by NNSFC 91018012 and the EXACTA project from ANR
and NSFC.

## References

  * [1] M. Braverman: Termination of Integer Linear Programs. CAV 2006, LNCS 4114, 372–385, 2006.
  * [2] Y. Chen, B. Xia, L. Yang, N. Zhan and C. Zhou: Discovering Non-linear ranking functions by Solving Semi-algebraic Systems. LNCS 4711, 34–49, 2007.
  * [3] M. A. Colón and H. B. Sipma: Synthesis of linear ranking functions. TACAS 01, LNCS 2031, 67–81, 2001.
  * [4] D. Dams, R. Gerth, and O. Grumberg: A heuristic for the automatic generation of ranking functions. Workshop on Advances in Verification (WAVe 00), 1–8, 2000.
  * [5] C. S. Lee, N. D. Jones and A. M. Ben-Amram: The size-change principle for program termination. POPL, 81–92, 2001.
  * [6] A. Podelski and A. Rybalchenko: A complete method for the synthesis of linear ranking functions. VMCAI, LNCS 2937, 465–486, 2004.
  * [7] A. Tiwari: Termination of Linear Programs. CAV 2004, LNCS 3114, 70–82, 2004.
  * [8] B. Xia and Z. Zhang: Termination of linear programs with nonlinear constraints, Journal of Symbolic Computation, 45: 1234–1249, 2010.
  * [9] B. Xia, L. Yang, N. Zhan and Z. Zhang: Symbolic decision procedure for termination of linear programs. Formal Aspects of Computing, 23:171–190, 2011.
  * [10] A. Gupta, T. Henzinger, R. Majumdar, A. Rybalchenko and R.-G. Xu: Proving non-termination, POPL, 147–158, 2008.
  * [11] S. Gulwani, S. Srivastava and R. Venkatesan: Program analysis as constraint solving, POPL, 281–292, 2008.
  * [12] S. Zhao and D. Chen: Decidability Analysis on Termination Set of Loop Programs. The International Conference on Computer Science and Service System(CSSS), 3124–3127, 2011.


11institutetext: Tianjin Astrophysics Center, Tianjin Normal University,
Tianjin 300387, People’s Republic of China; 11email<EMAIL_ADDRESS>22institutetext: Department of Astronomy, Beijing Normal University, Beijing
100875, People’s Republic of China; 22email<EMAIL_ADDRESS>33institutetext: National Astronomical Observatories, Chinese Academy of
Sciences, Beijing 100012, People’s Republic of China 44institutetext: Research
School of Astronomy and Astrophysics, Australian National University, Cotter
Rd., Weston, ACT 2611, Australia 55institutetext: School of Computing,
Australian National University, Acton ACT 2601, Australia 66institutetext:
South-Western Institute For Astronomy Research, Yunnan University, Kunming
650500, People’s Republic of China

# Spatial metallicity variations of mono-temperature stellar populations
revealed by early-type stars in LAMOST

Chun Wang 11 Haibo Yuan 22 Maosheng Xiang 33 Yuan-Sen Ting 4455 Yang Huang 33
Xiaowei Liu 66

(Received —; accepted —)

We investigate the radial metallicity gradients and azimuthal metallicity
distributions on the Galactocentric $X$–$Y$ plane using mono-temperature
stellar populations selected from LAMOST MRS young stellar sample. The
estimated radial metallicity gradient ranges from $-$0.015 dex/kpc to $-$0.07
dex/kpc, which decreases as effective temperature decreases (or stellar age
increases) at $7500<T_{\rm eff}<12500$ K ($\tau<$1.5 Gyr). The azimuthal
metallicity excess (metallicity after subtracting radial metallicity gradient,
$\Delta$ [M/H]) distributions exhibit inhomogeneities with dispersions of 0.04
dex to 0.07 dex, which decrease as effective temperature decreases. We also
identify five potential metal-poor substructures with large metallicity excess
dispersions. The metallicity excess distributions of these five metal-poor
substructures suggest that they contain a larger fraction of metal-poor stars
compared to other control samples. These metal-poor substructures may be
associated with high-velocity clouds that infall into the Galactic disk from
the Galactic halo, which are not quickly well-mixed with the pre-existing ISM
of the Galactic disk. As a result, these high-velocity clouds produce some
metal-poor stars and the observed metal-poor substructures. The variations of
metallicity inhomogeneities with different stellar populations indicate that
high-velocity clouds are not well mixed with the pre-existing Galactic disk
ISM within 0.3 Gyr.

###### Key Words.:

Galaxy: abundances - Galaxy: disk - Galaxy: evolution

##  1 Introduction

Metals in the interstellar medium (ISM) regulate its’ cooling process and the
star formation of galaxies. The mixing process between infalling gas and the
local ISM changes the fundamental properties, including the chemical
abundance, of the local ISM and the future star formation process.
Understanding the mixing process of the ISM is crucial for informing our
understanding of galaxy formation and evolution histories, such as Galactic
archaeology and chemical evolution (Tinsley 1980; Matteucci 2012, 2021). Most
studies thus far assume that the ISM is well mixed at a small scale.

The metallicity inhomogeneity of the ISM could help us to understand the ISM
mixing. At a large scale, the ISM of the Galactic disk shows a negative radial
metallicity gradient (Balser et al. 2011a), suggesting an “inside-out” disk
formation scenario. At a small scale, the metallicity of the ISM (Balser et
al. 2011b, 2015; De Cia et al. 2021), Cepheid variable stars (Pedicelli et al.
2009; Poggio et al. 2022), open clusters (Davies et al. 2009; Poggio et al.
2022), young upper main-sequence stars (Poggio et al. 2022), and young main-
sequence stars (Hawkins 2022) in the Milky Way (MW) present azimuthal
metallicity variations. For other external spiral galaxies, people also found
azimuthal ISM metallicity variations (after subtracting the radial metallicity
gradients) by studying the metallicity of H II regions (Ho et al. 2017, 2018;
Kreckel et al. 2019, 2020). All these observed azimuthal metallicity
inhomogeneities of the MW and other spiral galaxies suggest that the ISM is
not well mixed. To better understand the ISM mixing process, we need to
explore the variations of metallicity inhomogeneity of the ISM over time,
which has not been well studied yet.

Stellar surface chemical abundance remains almost unchanged during the main-
sequence evolutionary stage. It is thus a fossil record of the ISM during the
birth of these stars. The metallicity inhomogeneity of ISM and its variations
over time can be studied using a stellar sample with a wide age coverage.
However, stars in the MW have moved away from their birth positions duo to the
secular evolution of the MW. Old stars have experienced stronger radial
migration (Minchev & Famaey 2010; Kubryk et al. 2015; Frankel et al. 2018,
2020; Lian et al. 2022) compared to young stars. According to Frankel et al.
(2018) and Frankel et al. (2020), 68% of stars have migrated within a distance
of $3.6\sqrt{\tau/8\rm\,{Gyr}}$ kpc and $2.6\sqrt{\tau/6\rm\,{Gyr}}$ kpc,
respectively. Hence, stars can move up $\sim$ 1 kpc within $\,1$ Gyr. Lian et
al. (2022) suggest that the average migration distance is 0.5–1.6 kpc at age
of 2 Gyr and 1.0–1.8 kpc at age of 3 Gyr. In conclusion, young stars in the MW
are valuable for studying the ISM mixing process due to their large sample
size and wide age coverage compared to other young objects (e.g., open
clusters, Cepheid variable stars, H II regions)and because they are less
affected by secular evolution compared to older stars. For young main-sequence
stars, effective temperatures are tightly correlated with stellar ages
(Schaller et al. 1992; Zorec & Royer 2012; Sun et al. 2021). The variations of
ISM metallicity homogeneity (or inhomogeneity) over time can be investigated
using a young main-sequence stellar sample with accurate determinations of
stellar atmospheric parameters (effective temperature $T_{\mathrm{eff}}$,
surface gravity $\log g$ and metallicity [M/H]).

Recently, accurate stellar atmospheric parameters were derived from LAMOST
medium-resolution spectra for 40,034 young (early-type) main-sequence stars
(Sun et al. 2021). The stellar sample spans a wide range of effective
temperatures (7500-15000K), and covers a large and contiguous volume of the
Galactic disk. It allows us to investigate the ISM metallicity inhomogeneity
and its variations over time. In this work, we investigate the radial
metallicity gradients and azimuthal metallicity distribution features of mono-
temperature stellar populations across the Galactic disk within $-10.5<X<-8.0$
kpc, $-1.0<Y<1.5$ kpc and $|Z|<0.15$ kpc using the young stellar sample.

This paper is organized as follows. In Section 2, we introduce the adopted
young stellar sample. In Section 3, we present the radial metallicity
gradients of mono-temperature stellar populations. We present the azimuthal
metallicity distributions of mono-temperature stellar populations in Section
4. The constraints on the ISM mixing process using the azimuthal metallicity
distributions are discussed in Section 5. Finally, we summarize our work in
Section 6.

##  2  Young stellar sample from the LAMOST Medium-Resolution Spectroscopic
Survey

###  2.1 Coordinate Systems and Galactic Parameters

Two coordinate systems are used in this paper. One is a right-handed Cartesian
coordinate system ($X,Y,Z$) centred on the Galactic centre, with $X$
increasing towards the Galactic centre, $Y$ in the direction of Galactic
rotation, and $Z$ representing the height from the disk mid-plane, positive
towards the north Galactic pole. The other is a Galactocentric cylindrical
coordinate system $(R,\Phi,Z)$, with $R$ representing the Galactocentric
distance, $\Phi$ increasing in the direction of Galactic rotation, and $Z$ the
same as that in the Cartesian system. The Sun is assumed to be at the Galactic
midplane (i.e., $Z_{\odot}=$ 0 pc) and has a value of $R_{\odot}$ equal to
8.34 kpc (Reid et al. 2014).

###  2.2 Sample selections

As of March 2021, the LAMOST Medium-Resolution Spectroscopic Survey had
collected 22,356,885 optical (4950–5350 Å and 6300–6800 Å) spectra with a
resolution of $R\sim 7500$. Sun et al. (2021) selected 40,034 late-B and
A-type main-sequence stars from the LAMOST Medium-Resolution Spectroscopic
Survey (hereafter named the LAMOST-MRS young stellar sample) and extracted
their accurate stellar atmospheric parameters. For a star with spectral SNR
$\sim$60, the cross validated scatter is $\sim$ 75 K, 0.06 dex and 0.05 dex
for $T_{\mathrm{eff}}$, $\log g$ and [M/H], respectively. We adopt the
photogeometric distances provided by Bailer-Jones et al. (2021) for these
stars. The $X,Y,Z,R,\Phi$ of each star are estimated using its distance and
coordinates, and the corresponding errors are also given using the error
transfer function.

For the LAMOST-MRS young stellar sample, stars with $T_{\mathrm{eff}}$ and
[M/H] uncertainties larger than 75 K and 0.05 dex are discarded to ensure the
reliability of the results. Only stars with $7000<T_{\mathrm{eff}}<15000$ K,
$\log g>3.5$ dex, and $-1.2<$ [M/H] $<0.5$ dex are selected, as they are main-
sequence stars with accurate metallicity determinations. Because young stars
are mostly located in the Galactic plane, stars of $|Z|\geq 0.15$ kpc are also
removed to reduce the contaminations from old stars. Finally, our LAMOST-MRS
young stellar sample consists of 14,692 unique stars. The stellar number
density distribution on the $X$–$Y$ plane is shown in Figure 1.

The faint limiting magnitude of the LAMOST-MRS is $g\sim$ 15 mag. The faintest
stars in the four effective temperature bins (adopted in the following
context) have absolute $g$-band magnitudes of $\sim$ 4.5 mag
($7500<T_{\mathrm{eff}}<8000$ K), $\sim$ 4.0 mag ($8000<T_{\mathrm{eff}}<8500$
K), $\sim$ 3.5 mag ($9500<T_{\mathrm{eff}}<10500$ K), and $\sim$ 3.2 mag
($10000<T_{\mathrm{eff}}<12500$ K). Based on the distance modulus, stellar
samples with $7500<T_{\mathrm{eff}}<8000$ K, $8000<T_{\mathrm{eff}}<8500$ K,
$9500<T_{\mathrm{eff}}<10500$ K and $10000<T_{\mathrm{eff}}<12500$ K are
incomplete at distance ($d$)$\,>$ 1.258 kpc, $d>$ 1.584 kpc, $d>$ 1.955 kpc
and $d>$ 2.29 kpc, respectively.

Figure 1:  Stellar number density distribution on the $X$–$Y$ plane of the
final LAMOST-MRS young stellar sample.

###  2.3 Correcting for the Teff-metallicity systematics caused by NLTE effect

Metallicities of LAMOST-MRS young stars are estimated based on LTE models. But
the NLTE effects can significantly affect their spectra. The NLTE effects may
incur a bias of estimated metallicity with respect to $T_{\mathrm{eff}}$
(Xiang et al. 2022). To reduce the NLTE effects on the estimated metallicity
values, we use a sixth-order polynomial to model the
$T_{\mathrm{eff}}$–metallicity trend of the LAMOST-MRS young stellar sample.
The dependency of metallicity on $T_{\mathrm{eff}}$ is mitigated by
subtracting the fitted relation. We fit the relation of metallicity and
$T_{\mathrm{eff}}$ only using stars of $8.7<R$ $<9.5$ kpc to avoid the effects
of the radial metallicity gradients. Figure 2 shows the polynomial fit of
estimated $T_{\mathrm{eff}}$–metallicity trend. The distribution of stars on
the $T_{\mathrm{eff}}$–$\rm[M/H]_{corr}$ plane is also presented in Figure 2,
where the $\rm[M/H]_{corr}$ is the metallicity after subtracting the trend.
The figure shows that the final metallicity ($\rm[M/H]_{corr}$) does not vary
with $T_{\mathrm{eff}}$ after subtracting the mean trend. The used metallicity
is the corrected metallicity ($\rm[M/H]_{corr}$) in the following context.

Figure 2:  The stellar number density distributions on the effective
temperature and metallicity planes. The left panel displays the relation
between the estimated metallicity and $T_{\mathrm{eff}}$ (black symbols) and
their corresponding polynomial fit (red solid line) for the LAMOST-MRS young
stellar sample. The black symbol represents the mean estimated metallicity and
$T_{\mathrm{eff}}$ in each $T_{\mathrm{eff}}$ bin with a
$\Delta_{T_{\mathrm{eff}}}\rm{of}\,100$ K. The dashed red lines represent the
corresponding standard deviations of the metallicity in each
$T_{\mathrm{eff}}$ bin. Additionally, the stellar number density distribution
on the $T_{\mathrm{eff}}$-$\rm[M/H]$ plane is plotted in the left panel. Right
panel shows the stellar number density distribution on the
$T_{\mathrm{eff}}$-$\rm[M/H]_{corr}$ plane. The solid and dashed red lines
represent the mean corrected metallicity values and the corresponding standard
deviations of the metallicity in each $T_{\mathrm{eff}}$ bin, respectively.

##  3 Radial metallicity gradients of mono-temperature young stellar
populations

In this section, we investigate the radial metallicity gradients of mono-
temperature stellar populations. We divide stars from the LAMOST-MRS stellar
sample into different stellar populations in four effective temperature bins:
$7500<T_{\mathrm{eff}}<8000$ K, $8500<T_{\mathrm{eff}}<9000$ K,
$9500<T_{\mathrm{eff}}<10500$ K, and $10000<T_{\mathrm{eff}}<12500$ K. We
discard stars with $9000<T_{\mathrm{eff}}<9500$ K because the $\rm H{\alpha}$
lines of these stars are not sensitive with $T_{\mathrm{eff}}$, which leads to
large uncertainties of the measured metallicities. In each temperature bin, we
further divide stars into a small radial annulus of 0.25 kpc. Bins containing
fewer than 3 stars are discarded. We perform linear regression on the
metallicity as a function of the Galactic radius $R$. The slope is adopted as
the radial metallicity gradient. Figure 3 shows the fitting results for these
four mono-temperature stellar populations. As shown in the figure, a linear
regression captures the trend between metallicity and Galactic radius $R$
well.

The radial metallicity gradient of the Galactic disk plays an important role
in the study of Galactic chemical and dynamical evolution histories. It is
also a fundamental input parameter in any models of Galactic chemical
evolution. Previous studies on the radial metallicity gradient of the Galactic
disk using different tracers (including OB stars by Daflon & Cunha (2004),
Cepheid variables by Andrievsky et al. (2002); Luck et al. (2006), H ii
regions by Balser et al. (2011a), open clusters by Chen et al. (2003); Magrini
et al. (2009), planetary nebulae by Costa et al. (2004); Henry et al. (2010) ,
FGK dwarfs by Katz et al. (2011); Cheng et al. (2012); Boeche et al. (2013),
red giant stars by Hayden et al. (2014); Boeche et al. (2014) and red clump
stars by Huang et al. (2015)) have presented that the Galactic disk has a
negative radial metallicity gradient, which generally supports an “inside-out”
disk-forming scenario. The variations of radial metallicity gradient with
stellar age ($\tau$) have also been investigated by Xiang et al. (2015) and
Wang et al. (2019) using main-sequence turn-off (MSTO) stars and other works
(e.g., Casagrande et al. 2011; Toyouchi & Chiba 2018). Wang et al. (2019)
found that radial metallicity gradients steepen with increasing age at $\tau<$
4 Gyr, reach a maximum at $4<\tau<6$ Gyr , and then flatten with age. Xiang et
al. (2015) also found a similar trend of radial metallicity gradients with
stellar ages. The relation of radial metallicity gradient with stellar age for
the youngest stellar populations ($\tau<2$ Gyr) was not investigated in these
two works due to the inaccuracy of estimated stellar ages for the youngest
MSTO stars.

For the youngest main-sequence stars, the stellar age has a tight relation
with the effective temperature. We derive median stellar ages for these four
mono-temperature stellar populations according to the PARSEC isochrones
(Bressan et al. 2012). Age distributions in these four effective temperature
bins with the metallicity range of $-0.5$ dex and 0.5 dex (similar to the
metallicity coverage of our sample) predicted by the PARSEC isochrones are
shown in Figure 4. The median ages are 1.00 Gyr, 0.72 Gyr, 0.39 Gyr, and 0.27
Gyr, respectively, in these four effective temperature bins of
$7500<T_{\mathrm{eff}}<8000$ K, $8500<T_{\mathrm{eff}}<9000$ K,
$9500<T_{\mathrm{eff}}<10500$ K, and $10000<T_{\mathrm{eff}}<12500$ K.

Figure 5 shows the variations of radial metallicity gradients with the stellar
ages of LAMOST-MRS young stellar sample by us, the stellar ages of MSTO stars
presented by Wang et al. (2019) and Xiang et al. (2015). Radial metallicity
gradients estimated using young objects (including OB stars, Cepheid
variables, H ii regions and open clusters (OCs)) are also over-plotted in the
figure. We assume a mean age of 0.2 Gyr for OB stars, Cepheid variables, H ii
regions. Chen et al. (2003) divided their OCs into two age bins: $\tau<0.8$
Gyr and $\tau>0.8$ Gyr. We assume a mean age of 0.1 Gyr and 2 Gyr following
Chen et al. (2003). Radial metallicity gradients estimated using our LAMOST-
MRS young stellar sample are well aligned with those values estimated using
other young objects of previous works (Daflon & Cunha 2004; Andrievsky et al.
2002; Luck et al. 2006; Balser et al. 2011a; Chen et al. 2003) within the
uncertainties of the measurements. We find that radial metallicity gradients
of young stellar populations ($\tau<2$ Gyr) steepen as age increases (with a
gradient of $\sim-0.055\,\rm{dex\,kpc^{-1}\,Gyr^{-1}}$) within the uncertainty
of our estimates. The result is consistent with those of Wang et al. (2019)
and Xiang et al. (2015), who also found that the radial metallicity gradients
decrease with increasing stellar age for young stellar populations (1.5
$<\tau<$ 4 Gyr). Our results extend the relation between radial metallicity
gradient and stellar age to $\tau<$ 1.5 Gyr compared to Wang et al. (2019) and
Xiang et al. (2015).

Figure 3: Radial metallicity gradients of these four mono-temperature stellar
populations. The red symbols represent the median metallicity values in
individual radial bins. The line in red represents the linear regression over
the red symbols. The temperature range of each stellar population, the slope
of the linear fit (the radial metallicity gradient), and its associated
uncertainty are marked at the bottom left panel. Figure 4: The age
distributions of stars within the metallicity range of $-0.5$ dex and 0.5 dex
in these four effective temperature bins of $7500<T_{\mathrm{eff}}<8000$ K,
$8500<T_{\mathrm{eff}}<9000$ K, $9500<T_{\mathrm{eff}}<10500$ K, and
$10000<T_{\mathrm{eff}}<12500$ K predicted by the PARSEC isochrones. The
median ages are over-plotted with dashed lines. The effective temperature
ranges and median ages for each bin are marked at the top right corner of the
figure.  Figure 5:  Radial metallicity ([M/H]/[Fe/H]) gradient variations’
with stellar ages of the LAMOST-MRS young stellar sample in this work and
these of MSTO presented by Wang et al. (2019) and Xiang et al. (2015). Radial
metallicity gradients estimated using young objects (OB stars, Cepheid
variables, H ii regions and OCs) from previous works are also shown using
different symbols as labelled in the figure. Note that the $X$-axis is
logarithmic.

##  4 Azimuthal metallicity distributions of mono-temperature stellar
populations

This section aims to investigate the azimuthal metallicity distributions of
different mono-temperature stellar populations, as divided in Section 3. Doing
so, we further divide all these four mono-temperature stellar populations into
different $X$–$Y$ bins with a bin size of 0.1$\times$0.1 kpc. This chosen
spatial bin size aims to strike a balance between spatial resolution and the
number of stars in each bin, with a preference for higher spatial resolution
and a larger number of stars in each bin. Figure 8 displays the distributions
of stellar numbers in all $X$–$Y$ bins. The typical uncertainties of $X$ and
$Y$ are respectively 0.0114 kpc and 0.0055 kpc, which are much smaller than
the bin size of 0.1 kpc. To better visualize the azimuthal variation, we
subtract the mean radial metallicity gradient as measured in the previous
section. We introduce a new metallicity scale denoted as the ”Metallicity
Excess”, $\Delta\rm[M/H]=[M/H]-[M/H]_{R}$, where $\rm[M/H]_{R}$ is the median
metallicity in each $R$ bin with a bin scale of 0.5 kpc. In each $X$ and $Y$
bin, we estimated the mean $\Delta\rm[M/H]$ and its associated dispersion
($\sigma\rm[M/H]$), as well as their uncertainties.

###  4.1 Global statistics

Figure 6 shows the azimuthal metallicity excess ($\Delta\rm[M/H]$)
distributions of these four mono-temperature stellar populations on the
$X$–$Y$ plane, which shows significant inhomogeneities on the bin scale of
0.1$\times$0.1 kpc. The difference of metallicity excess spans almost 0.4 dex
(ranging from $-0.2$ dex to 0.2 dex). The dispersions of the (median)
metallicity excess (shown in Figure 6), are respectively 0.04 dex, 0.058 dex,
0.057 dex, and 0.066 dex for the stellar populations with effective
temperature coverage of $7500<T_{\mathrm{eff}}<8000$ K,
$8500<T_{\mathrm{eff}}<9000$ K, $9500<T_{\mathrm{eff}}<10500$ K, and
$10000<T_{\mathrm{eff}}<12500$ K as shown in Figure 7. The metallicity excess
dispersion increases as temperature increases.

We compute the two-point correlation function of metallicity excess for these
four mono-temperature stellar populations to quantify the scale length
associated with the observed metallicity inhomogeneity with the same method of
Kreckel et al. (2020). The 50% level scale length is $\sim$ 0.05 kpc, which is
smaller than our spatial bin size of 0.1 kpc. The result suggests that the
scale length of metallicity inhomogeneity is smaller than 0.1 kpc. This scale
length is much smaller than the 0.5-1.0kpc predicted by Krumholz & Ting (2018)
and the 0.3 kpc (50% level) estimated by Kreckel et al. (2020) using HII
regions in external galaxies. It is possible that their results in external
galaxies may not be directly applicable to the Milky Way. The origin of the
chemical inhomogeneities observed in this paper may differ from those observed
in external galaxies. The scale length is consistent with that of De Cia et
al. (2021), who suggests that pristine gas falling into the ”Galactic disk”
can produce chemical inhomogeneities on the scale of tens of pc.

To check the reliability of metallicity inhomogeneities, we study the
distributions of metallicity excess uncertainties ($\Delta\rm[M/H]_{err}$) in
Figure 9. $\Delta\rm[M/H]_{err}$ are mostly smaller than 0.1 dex (with median
values of 0.030, 0.039, 0.042, and 0.048 dex for stellar populations of
$7500<T_{\mathrm{eff}}<8000$ K, $8500<T_{\mathrm{eff}}<9000$ K,
$9500<T_{\mathrm{eff}}<10500$ K, and $10000<T_{\mathrm{eff}}<12500$ K,
respectively), which is much smaller than the difference of metallicity excess
shown in Figure 6. The comparison between Figure 6 and Figure 9 suggests that
the observed azimuthal metallicity inhomogeneities are reliable.

Figure 6 and Figure 7 not only show the azimuthal metallicity inhomogeneity
but also its variations with effective temperature. Azimuthal metallicity
inhomogeneities (larger metallicity dispersion means larger metallicity
inhomogeneity) of young stellar populations ($T_{\mathrm{eff}}>8000$ K) are
much larger than that of the old stellar population ($T_{\mathrm{eff}}<8000$
K).

Besides metallicity excess distributions, we also investigate the spatial
distributions of metallicity excess dispersions. Figures 10 and 11 show the
spatial distributions of metallicity excess dispersion and its associated
uncertainty. From Figure 10, we can find inhomogeneities of metallicity
dispersion distributions for the four mono-temperature stellar populations.
Inhomogeneities of young stellar populations ($T_{\mathrm{eff}}>8000$ K) are
much larger than those of the old stellar population ($T_{\mathrm{eff}}<8000$
K). Metallicity dispersion uncertainties shown in Figure 11 are much smaller
than the difference of metallicity dispersions shown in Figure 10, which
suggests that observed azimuthal metallicity dispersion distributions in
Figure 10 are reliable.

Figure 6: Metallicity excess distributions after subtracting radial
metallicity gradients for these four mono-temperature stellar populations,
binned by 0.1$\times$0.1 kpc on the $X$–$Y$ plane. Bins that contained fewer
than eight stars are discarded. The minimum number of stars in each bin is
selected to ensure that the median metallicity excess uncertainties produced
in these bins could distinguish the metal-poor substructures from other
regions. The positions at $R=$ 8.5, 9.0, 9.5, 10.0, and 10.5 kpc are marked
with black arcs. The black star symbol indicates the position of the Sun. The
centre and 1$\sigma$ width of the spiral arms are shown by blue solid and
dashed lines in all panels. Regions framed in red lines and magenta dashed
lines indicate the spatial positions of these five metal-poor substructures
(labelled by ‘a’, ‘b’, ‘c’, ‘d’, and ‘e’). A region framed by red lines means
that it is a real metal-poor substructure of this mono-temperature stellar
population. The region framed by magenta dashed lines is a corresponding
region of metal-poor substructure in other mono-temperature stellar
populations. Control regions are framed in black lines.  Figure 7: Bin number
density distributions of metallicity excess in Figure 6 of these four mono-
temperature stellar populations. The effective temperature ranges and
dispersions of these four distributions are marked at the right top corner of
the figure.

###  4.2 Metal-poor substructures

From Figure 6 and Figure 10, we observe several metal-poor substructures with
large metallicity dispersions. In the old stellar population
($8000<T_{\mathrm{eff}}<9000$ K), we identify one metal-poor substructure
(labelled ‘a’ in Figure 6), which is not found in the stellar populations of
$T_{\mathrm{eff}}>9500$ K. The metallicity of this metal-poor substructure is
smaller than its nearby regions by $\sim$ 0.1 dex. The metal-poor substructure
is also found in the stellar population of $7500<T_{\mathrm{eff}}<8000$ K,
while it is much weaker. In the younger stellar population
($9500<T_{\mathrm{eff}}<12500$ K), there are four metal-poor regions labelled
‘b’, ‘c’, ‘d, and ‘e’ in Figure 6, which are not found in the two old stellar
populations. The metallicities of these four regions are also smaller than
their nearby regions by $\sim$ 0.1 dex. The spatial sizes of ‘a’, ‘b’, ‘c’,
‘d’, and ‘e’ substructures are respectively $\sim 0.7\times 0.2$, $0.3\times
0.2$, $0.8\times 0.2$, $0.4\times 0.1\,\rm kpc$, and $0.1\times 0.4\,\rm kpc$.

Azimuthal metallicity variations with spatial positions may be tracked along
spiral arms (e.g., Khoperskov et al. 2018; Poggio et al. 2022). We compare the
azimuthal metallicity distributions, especially those of the five identified
metal-poor substructures, with the spiral arms (shown as the blue solid and
dashed line, indicating from left to right segments of the Local (Orion) arm
and the Perseus arm) determined using high mass star forming regions by Reid
et al. (2019). From Figure 6, we find that metallicity distributions of all
these four mono-temperature stellar populations do not track the expected
locations of spiral arms, similar to the results presented by Hawkins (2022).
Hawkins (2022) mapped out azimuthal metallicity distributions using LAMOST
OBAF young stars selected from LAMOST low-resolution spectra by Xiang et al.
(2022). However, our detailed azimuthal metallicity patterns have large
differences compared to those of Hawkins (2022). We cross-match the LAMOST-MRS
young stellar sample with their OBAF stellar sample and plot azimuthal
metallicity distributions using the common stars. For these common stars, the
azimuthal metallicity distributions are similar either using the metallicity
of the LAMOST-MRS or LAMOST OBAF sample, which are also similar to the results
presented here. Different fractions and the origin of contaminations from cold
stars of the two samples may be responsible for the difference between the
results of us and those of Hawkins (2022).

In Figure 12 we show the normalised metallicity excess distributions of these
five metal-poor regions (‘a’, ‘b’, ‘c, ‘d’, and ‘e’ regions) and those of
control regions (framed in black lines). The skewnesses of the metallicity
distributions are also estimated. All these skewness are smaller than zero,
suggesting that metallicity distributions, both in the metal-poor regions and
control regions, have metal-poor tails. Metal-poor substructures contain a
larger fraction of metal-poor stars and have much smaller skewness compared to
control regions.

##  5 The ISM mixing process

Azimuthal metallicity distributions mapped out by the LAMOST-MRS stellar
sample presented in Section 4 suggest that there are significant azimuthal
metallicity inhomogeneities. Similarly, the azimuthal metallicity
distributions of the ISM (Balser et al. 2011b, 2015; De Cia et al. 2021),
Cepheid variable stars (Pedicelli et al. 2009), and open clusters(Davies et
al. 2009; Fu et al. 2022) in the MW also show significant azimuthal
metallicity inhomogeneities. Azimuthal metallicity inhomogeneities of external
spiral galaxies are also found through investigating the metallicity of H II
regions (Ho et al. 2017, 2018; Kreckel et al. 2019, 2020). These observed
azimuthal metallicity inhomogeneities both in the MW and external spiral
galaxies suggest that the ISM is not well mixed.

High-velocity clouds infalling into the Galactic disk from the Galaxy halo are
metal-poor, with metallicities ranging from 0.1 to 1.0 solar metal (Fox 2017;
Wright et al. 2021; De Cia et al. 2021). High-velocity clouds can be generated
by the “galactic fountain” cycle and other gas accretion processes.
Intermediate-velocity clouds are also the main observational manifestations of
the ongoing “galactic fountain” cycle (Wakker & van Woerden 1997). However,
unlike high-velocity clouds, intermediate-velocity clouds are nearby systems
and have near or solar metallicity. These five metal-poor substructures found
in the current paper have smaller mean metallicity values and larger
dispersions. They also contain a larger fraction of metal-poor stars than
other Galactic disk regions. These results suggest that these five metal-poor
substructures may be associated with high-velocity clouds, which infall into
the Galactic disk from the Galactic halo. These high-velocity clouds are not
quickly well mixed with the ISM of the Galactic disk after they infall into
the Galactic disk, thus they have time to produce stars, which are more metal-
poor than stars born in the pre-existing Galactic disk ISM. As a result, the
metallicity dispersions in the locations of these high-velocity clouds are
larger than those of other regions.

As shown in Section 4, the azimuthal metallicity inhomogeneity and dispersion
increase as temperature increases. Five metal-poor (large metallicity
dispersion) substructures are found. Four of these substructures are only
found in the metallicity distributions of young stellar populations ($T_{\rm
eff}>9500\,\rm K$). These metal-poor substructures of the stellar population
with $9500<T_{\rm eff}<10500\,\rm K$ (with a median stellar age of 0.39 Gyr)
may suggest that the corresponding high-velocity clouds had infalled into the
Galactic disk 0.39 Gyr ago. Similarly, these metal-poor substructures of
$10000<T_{\rm eff}<12500\,\rm K$ (with a median stellar age of 0.27 Gyr) may
suggest that these corresponding high-velocity clouds had not been well mixed
into the Galactic disk ISM before 0.27 Gyr. In conclusion, these high-velocity
clouds infalling into the Galactic disk from the Galactic halo are not well
mixed with the pre-existing Galactic disk ISM within 0.12 Gyr ($0.39-0.27$
Gyr).

It is noted that the ‘d’ metal-poor substructure of the stellar population
with $10000<T_{\rm eff}<12500\,\rm K$ move $\sim 0.1$ kpc on the $X$–$Y$ plane
compared to that of $9500<T_{\rm eff}<10500\,\rm K$. This may be the
consequence of the velocity difference between infalling high-velocity clouds
and stars or ISM of the Galactic disk. A velocity difference of $\sim
0.82\,\rm kms^{-1}$ is needed to move 0.1 kpc within 0.12 Gyr, which is
reasonable.

The other metal-poor substructure is found in the metallicity distributions of
old stellar populations ($T_{\rm eff}<9000\,\rm K$), suggesting that the
corresponding high-velocity cloud had not sufficiently mixed with the Galactic
disk ISM before 0.72 Gyr (the median age of the stellar population with
$8000<T_{\rm eff}<9000\,\rm K$) and had infalled into the Galactic disk 1.0
Gyr (the median age of the stellar population with $7500<T_{\rm eff}<8000\,\rm
K$) ago. The results suggest that the high-velocity cloud is not well mixed
into Galactic disk ISM within 0.28 Gyr. This substructure is not found in the
metallicity distributions of young stellar populations, suggesting that this
high-velocity cloud had been well mixed into the Galactic disk ISM 0.39 Gyr
ago.

##  6 Summary

In this work, we use the LAMOST MRS young stellar sample with accurate
effective temperature and metallicity to investigate the radial metallicity
gradients and azimuthal metallicity distributions of different stellar
populations with varying effective temperatures (or ages).

The estimated radial metallicity gradient ranges from $-$0.015 dex/kpc to
$-$0.07 dex/kpc, which decreases as effective temperature decreases (or
stellar age increases). The result is consistent with those of Xiang et al.
(2015) and Wang et al. (2019), who also found that the radial metallicity
gradients decrease with increasing stellar age for young stellar populations
($1.5<\,\tau<4\,\rm Gyr$). Our results extended their study of the relation
between radial metallicity gradient and stellar age to $\tau<1.5\,\rm Gyr$.

After subtracting radial metallicity gradients on the $X$–$Y$ plane, the
azimuthal metallicity distributions of all these four mono-temperature stellar
populations show significant metallicity inhomogeneities, which is consistent
with previous studies of azimuthal metallicity distributions of the Milky Way
(Balser et al. 2011b, 2015; De Cia et al. 2021; Pedicelli et al. 2009; Davies
et al. 2009) and external spiral galaxies (Ho et al. 2017, 2018; Kreckel et
al. 2019, 2020). The result suggests that the ISM is not well mixed at any
time.

We find five metal-poor substructures with sizes of $\sim$ 0.2–1.0 kpc,
metallicities of which are smaller than their nearby regions by $\sim 0.1$
dex. These metal-poor substructures may be associated with high-velocity
clouds infalling into the Galactic disk from the Galactic halo. According to
the results of stellar populations at different ages, we suggest that high-
velocity clouds infalling into the Galactic disk from the Galactic halo are
not well mixed with the pre-existing Galactic disk ISM within 0.3 Gyr.

The size and spatial distribution of our stellar sample are mainly limited by
the faint limiting magnitude (15 mag in $g$-band) of the LAMOST Medium-
Resolution Spectroscopic Survey. Future large-scale spectroscopic surveys,
including SDSS-V (Kollmeier et al. 2017; Zari et al. 2021) and 4MOST (de Jong
et al. 2022), are expected to improve our work by enlarging the sample size
and spatial coverage.

###### Acknowledgements.

We appreciate the helpful comments of the anonymous referee. This work was
funded by the National Key R&D Program of China (No. 2019YFA0405500) and the
National Natural Science Foundation of China (NSFC Grant No.12203037,
No.12222301, No.12173007 and No.11973001). We acknowledge the science research
grants from the China Manned Space Project with NO. CMS-CSST-2021-B03. We used
data from the European Space Agency mission Gaia
(http://www.cosmos.esa.int/gaia), processed by the Gaia Data Processing and
Analysis Consortium (DPAC; see
http://www.cosmos.esa.int/web/gaia/dpac/consortium). Guoshoujing Telescope
(the Large Sky Area Multi-Object Fiber Spectroscopic Telescope LAMOST) is a
National Major Scientific Project built by the Chinese Academy of Sciences.
Funding for the project has been provided by the National Development and
Reform Commission. LAMOST is operated and managed by the National Astronomical
Observatories, Chinese Academy of Sciences.

## References

  * Fox (2017) 2017, Astrophysics and Space Science Library, Vol. 430, Gas Accretion onto Galaxies
  * Andrievsky et al. (2002) Andrievsky, S. M., Kovtyukh, V. V., Luck, R. E., et al. 2002, A&A, 381, 32
  * Bailer-Jones et al. (2021) Bailer-Jones, C. A. L., Rybizki, J., Fouesneau, M., Demleitner, M., & Andrae, R. 2021, AJ, 161, 147
  * Balser et al. (2011a) Balser, D. S., Rood, R. T., Bania, T. M., & Anderson, L. D. 2011a, ApJ, 738, 27
  * Balser et al. (2011b) Balser, D. S., Rood, R. T., Bania, T. M., & Anderson, L. D. 2011b, ApJ, 738, 27
  * Balser et al. (2015) Balser, D. S., Wenger, T. V., Anderson, L. D., & Bania, T. M. 2015, ApJ, 806, 199
  * Boeche et al. (2014) Boeche, C., Siebert, A., Piffl, T., et al. 2014, A&A, 568, A71
  * Boeche et al. (2013) Boeche, C., Siebert, A., Piffl, T., et al. 2013, A&A, 559, A59
  * Bressan et al. (2012) Bressan, A., Marigo, P., Girardi, L., et al. 2012, MNRAS, 427, 127
  * Casagrande et al. (2011) Casagrande, L., Schönrich, R., Asplund, M., et al. 2011, A&A, 530, A138
  * Chen et al. (2003) Chen, L., Hou, J. L., & Wang, J. J. 2003, AJ, 125, 1397
  * Cheng et al. (2012) Cheng, J. Y., Rockosi, C. M., Morrison, H. L., et al. 2012, ApJ, 746, 149
  * Costa et al. (2004) Costa, R. D. D., Uchida, M. M. M., & Maciel, W. J. 2004, A&A, 423, 199
  * Daflon & Cunha (2004) Daflon, S. & Cunha, K. 2004, ApJ, 617, 1115
  * Davies et al. (2009) Davies, B., Origlia, L., Kudritzki, R.-P., et al. 2009, ApJ, 696, 2014
  * De Cia et al. (2021) De Cia, A., Jenkins, E. B., Fox, A. J., et al. 2021, Nature, 597, 206
  * de Jong et al. (2022) de Jong, R. S., Bellido-Tirado, O., Brynnel, J. G., et al. 2022, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 12184, Ground-based and Airborne Instrumentation for Astronomy IX, ed. C. J. Evans, J. J. Bryant, & K. Motohara, 1218414
  * Frankel et al. (2018) Frankel, N., Rix, H.-W., Ting, Y.-S., Ness, M., & Hogg, D. W. 2018, ApJ, 865, 96
  * Frankel et al. (2020) Frankel, N., Sanders, J., Ting, Y.-S., & Rix, H.-W. 2020, ApJ, 896, 15
  * Fu et al. (2022) Fu, X., Bragaglia, A., Liu, C., et al. 2022, A&A, 668, A4
  * Hawkins (2022) Hawkins, K. 2022, arXiv e-prints, arXiv:2207.04542
  * Hayden et al. (2014) Hayden, M. R., Holtzman, J. A., Bovy, J., et al. 2014, AJ, 147, 116
  * Henry et al. (2010) Henry, R. B. C., Kwitter, K. B., Jaskot, A. E., et al. 2010, ApJ, 724, 748
  * Ho et al. (2018) Ho, I. T., Meidt, S. E., Kudritzki, R.-P., et al. 2018, A&A, 618, A64
  * Ho et al. (2017) Ho, I. T., Seibert, M., Meidt, S. E., et al. 2017, ApJ, 846, 39
  * Huang et al. (2015) Huang, Y., Liu, X.-W., Zhang, H.-W., et al. 2015, Research in Astronomy and Astrophysics, 15, 1240
  * Katz et al. (2011) Katz, D., Soubiran, C., Cayrel, R., et al. 2011, A&A, 525, A90
  * Khoperskov et al. (2018) Khoperskov, S., Di Matteo, P., Haywood, M., & Combes, F. 2018, A&A, 611, L2
  * Kollmeier et al. (2017) Kollmeier, J. A., Zasowski, G., Rix, H.-W., et al. 2017, arXiv e-prints, arXiv:1711.03234
  * Kreckel et al. (2020) Kreckel, K., Ho, I. T., Blanc, G. A., et al. 2020, MNRAS, 499, 193
  * Kreckel et al. (2019) Kreckel, K., Ho, I. T., Blanc, G. A., et al. 2019, ApJ, 887, 80
  * Krumholz & Ting (2018) Krumholz, M. R. & Ting, Y.-S. 2018, MNRAS, 475, 2236
  * Kubryk et al. (2015) Kubryk, M., Prantzos, N., & Athanassoula, E. 2015, A&A, 580, A126
  * Lian et al. (2022) Lian, J., Zasowski, G., Hasselquist, S., et al. 2022, MNRAS, 511, 5639
  * Luck et al. (2006) Luck, R. E., Kovtyukh, V. V., & Andrievsky, S. M. 2006, AJ, 132, 902
  * Magrini et al. (2009) Magrini, L., Sestito, P., Randich, S., & Galli, D. 2009, A&A, 494, 95
  * Matteucci (2012) Matteucci, F. 2012, Chemical Evolution of Galaxies
  * Matteucci (2021) Matteucci, F. 2021, A&A Rev., 29, 5
  * Minchev & Famaey (2010) Minchev, I. & Famaey, B. 2010, ApJ, 722, 112
  * Pedicelli et al. (2009) Pedicelli, S., Bono, G., Lemasle, B., et al. 2009, A&A, 504, 81
  * Poggio et al. (2022) Poggio, E., Recio-Blanco, A., Palicio, P. A., et al. 2022, A&A, 666, L4
  * Reid et al. (2019) Reid, M. J., Menten, K. M., Brunthaler, A., et al. 2019, ApJ, 885, 131
  * Reid et al. (2014) Reid, M. J., Menten, K. M., Brunthaler, A., et al. 2014, ApJ, 783, 130
  * Schaller et al. (1992) Schaller, G., Schaerer, D., Meynet, G., & Maeder, A. 1992, A&AS, 96, 269
  * Sun et al. (2021) Sun, W., Duan, X.-W., Deng, L., et al. 2021, ApJS, 257, 22
  * Tinsley (1980) Tinsley, B. M. 1980, Fund. Cosmic Phys., 5, 287
  * Toyouchi & Chiba (2018) Toyouchi, D. & Chiba, M. 2018, ApJ, 855, 104
  * Wakker & van Woerden (1997) Wakker, B. P. & van Woerden, H. 1997, ARA&A, 35, 217
  * Wang et al. (2019) Wang, C., Liu, X. W., Xiang, M. S., et al. 2019, MNRAS, 482, 2189
  * Wright et al. (2021) Wright, R. J., Lagos, C. d. P., Power, C., & Correa, C. A. 2021, MNRAS, 504, 5702
  * Xiang et al. (2022) Xiang, M., Rix, H.-W., Ting, Y.-S., et al. 2022, A&A, 662, A66
  * Xiang et al. (2015) Xiang, M.-S., Liu, X.-W., Yuan, H.-B., et al. 2015, Research in Astronomy and Astrophysics, 15, 1209
  * Zari et al. (2021) Zari, E., Rix, H. W., Frankel, N., et al. 2021, A&A, 650, A112
  * Zorec & Royer (2012) Zorec, J. & Royer, F. 2012, A&A, 537, A120

##  Appendix A Additional figures

Figure 8: Same to Figure 6, but for the stellar number distributions. Figure
9: Same to Figure 6, but for the distributions of metallicity excess
uncertainties.  Figure 10: Same to Figure 6, but for the distributions of the
dispersion of the metallicity excess.  Figure 11: Same to Figure 6, but for
the distributions of metallicity excess dispersion’s uncertainty.  Figure 12:
Metallicity excess distributions in metal-poor regions (red histogram) and
their control regions (black histogram) of these four mono-temperature stellar
populations. The skewness of these distributions is estimated and labelled at
the top right corner of each panel. The total number and the number of stars
with $[\rm M/H]_{corr}<-0.4$ dex are also shown in the figure.