\section*{Introduction}

This  article is the second of a three-part series (with \cite{me-2011a} and \cite{me-2012-canonization}) examining the model-theoretic geometry of an algorithmic problem -- the $L^k$-Canonization Problem. Here, $L^k$ denotes the fragment of first-order logic consisting of formulas with at most $k$ distinct variables, \emph{free or bound}, and it can be shown that for any finite structure $\M$ (in a finite relational signature $\rho$), its complete $k$-variable theory $Th^k(\M)$ is finitely axiomatizable in a uniform way. The $L^k$-Canonization Problem asks us to devise an operator $F$ that takes the theories $Th^k(\M)$ to finite models $F(Th^k(\M))\models Th^k(\M)$ -- thus, defining a ``canonical'' model of each complete $k$-variable theory that does have finite models. Composing the canonization operator $F$ with the mapping $\M\mapsto Th^k(\M)$, the operator $F(Th^k(-))$ can be thought of as a solution to a natural relaxation of the Graph Isomorphism Problem, the status of which is a major open problem in complexity theory (see \cite{graph-isom-survey} for an old survey).

Although this problem is known to be unsolvable over the class of \emph{all} $L^k$-theories (in particular, over all $L^3$-theories of finite structures -- see\cite{Grohe97largefinite}), it has been shown that for the class of stable $L^k$-theories  and for the class of super-simple $L^k$-theories with trivial forking dependence (with additional amalgamation assumptions), the $L^k$-Canonization Problem is {\em recursively} solvable (see \cite{koponen-2001} and \cite{koponen-2006}, respectively).
In both of those cases, resolution of the $L^k$-Canonization Problem is reduced to showing that certain complete first-order theories associated with the original $L^k$-theories have the finite sub-model property. Thus, after the heavy lifting done by the model theory, the algorithm itself is extremely simple-minded. Moreover, the analyses in \cite{koponen-2001} and \cite{koponen-2006} do not assume \emph{a priori} that the $L^k$-theories in question certainly have finite models. In contrast, in this series of articles, we will examine the $L^k$-Canonization Problem for $L^k$-theories that do certainly have finite models. Moreover, we will consider implementation of $L^k$-Canonization operators in a significantly restricted model of computation, leading to a notion we call ``efficient constructibility.'' Finally, we will expand the original $L^k$-Canonization Problem to take whole $L^k$-elementary diagrams as input, which allows us to work with individual $L^k$-theories in a non-trivial way. Thus, the goal of this series of articles is to prove the following:
\begin{mainthm}
Let $\M_0$ be a finite structure, and let $K$ be the class of all finite models of $T = Th^k(\M_0)$. Assuming that $K$ has adequate amalgamation properties, let $T^{\lim}$ be the complete first-order theory of the direct limit of $K$. Then the following are equivalent:
\begin{enumerate}
\item $T^{\lim}$ is super-rosy of finite $U^\thorn$-rank.
\item $K$ is rosy.
\item The $K$-Construction Problem is solvable in a certain ``relational'' model of computation (based on \cite{abiteboul-vianu-1995} and exposed in \cite{me-2011b}):
\begin{quote}
\textsc{Given} $\M[A]$ for some (implicit) $\M\in K$ and $A\subseteq M$,\footnote{Here $\M[A]$ denotes the induced substructure of $\M$ on the subset $A$, so $\M[A]$ \emph{does not} carry any further information about $\M$.}

\textsc{Return} $\N\in K$ such that $A\subseteq N$ and $\N[A] = \M[A]$.
\end{quote}
\end{enumerate}
\end{mainthm}

In \cite{me-2011a}, we established the content of parts 1 and 2 of the Main Theorem, and showed that, in fact, 1 and 2 are equivalent. In this article, we will prove the implication
$$\textnormal{``Efficient constructibility''\,\,$\implies$\,\,1,2.}$$
We save for another day (i.e. \cite{me-2012-canonization}) the demonstrations that (1) a solution in the relational model of computation induces efficient constructibility in the sense of this article (immediate from the definitions), and (2) that the $K$-Construction Problem is in fact solvable by a relational Turing machine whenever $K$ is rosy (so, super-rosy of finite $U^\thorn$-rank

\begin{thm}
Let $\M_0$ be a finite structure, and let $K$ be the class of all finite models of $T = Th^k(\M_0)$. Assuming that $K$ has adequate amalgamation properties, let $T^{\lim}$ be the complete first-order theory of the direct limit of $K$. If $K$ is efficiently constructible, then $K$ is rosy (super-rosy of finite $U^\thorn$-rank).
\end{thm}

\section{Background and the Main Setting}

The contents of subsections \ref{subsec-start} and \ref{subsec-end} is taken \emph{verbatim} from the companion article, \cite{me-2011a}. Naturally, we require the settings to be identical. In the last subsection, we recall the necessary facts about \th-independence and rosiness that were established in \cite{me-2011a}.

\subsection{Finite-variable Logics}\label{subsec-start}

Finite-variable fragments of first-order logic, $L^k$, were formulated by many authors independently (e.g. \cite{poizat-1982}, but our main references have been \cite{otto-1997} and \cite{libkin-FMTbook-2004}). The importance of $L^k$ and its infinitary extension $L^k_{\infty,\omega}$ in finite-model theory is difficult to overstate. For our purposes, $L^k$ is satisfying because a ``complete'' $L^k$-theory -- that is, complete for $L^k$-sentences -- can have many non-isomorphic finite models, which is surely a prerequisite for bringing classical model-theoretic ideas to bear in finite-model theory.

\begin{defn}
Let $\rho$ be a finite relational signature. Assume $k\geq\ari(\rho)= \max \left\{\ari(R):R\in\rho\right\}$ and $k\geq 2$.
\begin{enumerate}
\item Fix a set $X = \{x_1,...,x_k\}$ of exactly $k$ distinct variables. Then, $L^X = L^X_\rho$ is the fragment of the first-order logic $L=L_\rho$ keeping only those formulas all of whose variables, \emph{free or bound}, come from $X$. If $V = \{x_0,x_1,...,x_n,...\}$ is the infinite set of first-order variables understood in the construction of the full first-order logic, then $L^k =\bigcup\left\{L^X:X\in{V\choose k}\right\}$, where ${V\choose k}$ is the set of $k$-element subsets of $V$.

As usual, we write $\phi(x_1,...,x_k)$ to mean that the set of free variables of $\phi$ is a subset of $\{x_1,...,x_k\}$, but not necessarily identical to it.

\item For a $\rho$-structure $\M$, the $k$-variable theory of $\M$, denoted $Th^k(\M)$ is the set of sentences $\phi$ of $L^k$ such that $\M\models\phi$. Note that $Th^k(\M)$ is complete with respect to $k$-variable sentences in that either $\phi\in Th^k(\M)$ or $\neg\phi\in Th^k(\M)$ for every $k$-variable sentence $\phi$.

\item For a $k$-tuple $\aa\in M^k$, we set
$tp^k(\aa;\M) = \left\{\phi(x_1,...,x_k)\in L^k:\M\models\phi(\aa)\right\}$
and if $T = Th^k(\M)$, then $S^k_k(T) = \left\{tp^k(\aa;\M):\aa\in M^k\right\}$.

It can be shown -- in a number of ways -- that for a complete $L^k$-theory $T$, $T$ has a finite model only if $S^k_k(T)$ is finite. All of those methods also show that $S^k_k(T)$ is an invariant of $T = Th^k(\M)$ rather than $\M$ itself -- that is, if $Th^k(\N) = T$ for some other $\rho$-structure $\N$ (equivalently, if $\N\equiv^k\M$), then
$\left\{tp^k(\bb;\N):\bb\in N^k\right\}= S^k_k(T)$, too. Finally, it can also be shown that if $\M$ is finite, then $Th^k(\M)$ is finitely axiomatizable, and in fact, the mapping $\M\mapsto Th^k(\M)$ is computable in $\textrm{Rel-}$\textsc{Ptime} (see \cite{abiteboul-vianu-1995}). This latter fact is the basis for our notion of efficient constructibility.

\item Let $\M$ be a $\varrho$-structure, and let $B\subseteq M$. Then for $X\in{V\choose k}$ as above and $e:X\to B\cup X$, we define $L^X(e)$ to be the set,
$$\left\{\phi(e(x_1),...,e(x_n)): \phi(x_1,...,x_n)\in L^X\right\}.$$
Then,
$$L^k(B) = \bigcup_X\bigcup_{e:X\to B\cup X}L^X(e),$$
where, again, $X$ ranges over ${V\choose k}$. In particular, $L^k(B)$ \emph{is not} obtained by adding $B$ as collection of constant symbols to the underlying signature.
Finally, we define
$$\diag^k(B;\M) =\left\{\phi\in L^k(B):\M\models\phi,\textrm{ $\phi$ has no free variables}\right\}.$$
We note that the object $\diag^k(B;\M)$ \emph{does not carry} the whole of $\M$ with it; this observation is crucial in understanding why the Strong $L^k$-Canonization Problem (below) is non-trivial.

\end{enumerate}
\end{defn}
Having defined the $k$-variable logic, we  define  the {\em $L^k$-Canonization Problem} by specifying what would amount to its solution. Thus, an {\em $L^k$-Canonization operator} (in the signature $\rho$) is a polynomial-time computable mapping $F:\fin[\rho]\to\fin[\rho]$ such that,
\begin{enumerate}
\item $F(\M)\equiv^k\M$ for all $\M\in\fin[\rho]$.
\item If $\M\equiv^k\N$, then $F(\M) = F(\N)$.
\end{enumerate}
(Here, $\fin[\rho]$ denotes the class of all finite $\rho$-structures.) The map $F$ selects a representative of each $\equiv^k$-class,  a ``canonical'' finite model of each complete $k$-variable theory that does actually have finite models.\footnote{In particular, $F$ is supposed to be invariant with respect re-encodings of a given structure. In the model of computation that we will work with in these articles, which works directly with unencoded structures, this issue will actually disappear entirely.} For $k\geq 3$, this is entirely impossible \cite{Grohe97largefinite}, so the natural move is to ask for canonization operators $F:K\to\fin[\rho]$ for sub-classes $K\subsetneq\fin[\rho]$. As stated, the operator $F$ really acts on theories, not structures, and this seems to be a serious impediment to studying the question from the point of view of ``geometric'' model theory; we therefore move again to a related problem which yields a better ``grip'' on the model theory of each $L^k$-theory.
Here, we call this the Strong $L^k$-Canonization Problem:
\begin{quote}
\textsc{Given} $\diag^k(A;\M)$ for some (implicit) $\M\in\fin[\rho]$ and $A\subseteq M$,\\
\textsc{Return} a model $\M'\models Th^k(\M)$ such that $A\subseteq M$ and $\diag^k(A;\M') = \diag^k(A;\M)$.
\end{quote}
(As usual, $\diag^k(A;\M)$, the $L^k$-elementary diagram of $A$ in $\M$, actually contains $Th^k(\M)$, as the sentences of $Th^k(\M)$ are precisely the $0$-ary formulas satisfied in $\M$ by $0$-tuples from $A$.) Of course, Strong $L^k$-Canonization initially appears to be a significantly harder problem than the original $L^k$-Canonization Problem, but we note that previous positive results on the $L^k$-Canonization Problem for $k=2$ and over restricted classes of $L^k$-theories have always yielded solutions of the Strong $L^k$-Canonization Problem with no additional toil -- see \cite{koponen-2001} and \cite{otto-1997b}.
We derive another advantage from the move to Strong $L^k$-Canonization in that it can be sensibly considered around a single fixed $L^k$-theory without trivializing the problem\footnote{There is an asymmetry in fixating on a single $L^k$-theory $T$. If we were initially studying classes $K\subseteq\fin[\rho]$ over which (Strong) $L^k$-Canonization has a solution, there is an implicit expectation of uniformity in that we would have expected a single algorithm to serve as an $L^k$-Canonization operator over the entire class. By fixing a single theory $T$, we allow ourselves to exploit additional properties of it that might be hard or impossible to read-off from its a finite presentation.}.

\subsection{Main Setting}\label{subsec-end}

The context for the the Main Theorem (for this and the two companion articles) is the following. Let $\MM_0$ be a countable $\aleph_0$-categorical structure in a finite relational signature $\rho$. We  assume that $Th(\MM_0)$ has the finite sub-model property in the following strong sense:
\begin{quote}
For every sentence $\phi$ and every finite $A_0\subset\MM_0$, $\phi\in Th(\MM_0)$ if and only if there is an algebraically closed finite $A\subset\MM_0$ such that $A_0\subseteq A$ and $A\models \phi$.
\end{quote}
Under this assumption, the $k$-variable theory $T = Th^k(\MM_0)$ has finite models of all sizes. We will also make two additional universality assumptions about $\MM_0$ with respect to finite models of $T$.
\begin{enumerate}
\item[U1.] For $B\subseteq\MM_0$, define
$$\cl_{+1}^k(B) = B\cup \left\{a\in \MM_0: \diag^k(B;\MM_0)\models \textrm{$\tp^k(a/B)$ is algebraic}\right\},$$
$$\cl_0^k(B) = B,\,\,\cl_{n+1}^k(B) = \cl_{+1}^k(\cl^k_n(B)),\,\,\cl^k(B) = \bigcup_n\cl^k_n(B).$$
We require that for all $B\subset_\fin\MM_0$, $\acl(B) = \cl^k(B)$ and, if $B =\acl(B)$, then $tp(B)\equiv tp^k(B)\cup Th(\MM_0)$.
\item[U2.] $T\models Th_\forall(\MM_0)$.

This assumption has two invaluable consequences:
\begin{enumerate}
\item For every sufficiently large finite model $\A\models T$, there is an $L^k$-elementary embedding $\A\to\MM_0$.
\item For large enough finite $\B\models T$, for any $A\subseteq B$ such that $A = \cl^k(A)$, and any $f_0:A\to\MM_0$ -- a partial $L^k$-elementary map -- there is an $L^k$-elementary embedding $f:\B\to\MM_0$ extending $f_0$.
\end{enumerate}
\end{enumerate}

\noindent From all of these assumptions and appealing to \cite{baldwin-lessmann-2002} (Lemma 19 of that article, combined with the assumption on algebraic closures above), we may associate with $T$ a direct limit -- a countable structure  $\MM$ with the following properties:
\begin{enumerate}
\item[C1.] $\MM$ also satisfies the universality conditions expressed above.
\item[C2.] For any finite tuple $\aa$ from $\MM$, $\tp(\aa) \equiv \tp^k(\aa)\cup Th(\MM)$.
\item[C3.] Let $K_0$ be a set of representatives of every isomorphism-type of finite $L^k$-elementary sub-models of $\MM_0$. Then for any non-principal ultrafilter $\Psi$ on $K_0$, $\MM\equiv\Pi K_0/\Psi$.
\end{enumerate}
Abusing the terminology of \cite{baldwin-lessmann-2002} slightly, we call the theory $T^{\lim} = Th(\MM)$ the {\em canonical completion} of $T$.

\begin{defn}
Let $K$ denote the class of (up to isomorphism) finite $L^k$-elementary sub-models of $\MM$ quasi-ordered by the $L^k$-elementary substructure relation. That is to say, starting with the set of finite $L^k$-elementary sub-models of $\MM_0$, we close under isomorphisms and obtain an object $(K,\preceq^k)$ that is much like an abstract elementary class (AEC). By definition, the model theory of the $k$-variable theory $T$ is, effectively, just the model theory of the class $(K,\preceq^k).$\footnote{In fact, if $T$ is any $k$-variable theory whose \emph{finite models} have the Joint-Embedding and Amalgamation Properties indicated by the two consequences of U2, it is still possible to generate a limit model $\MM$ as above; given $\MM$, one can then go through this entire process with $\MM_0=\MM$. Thus, we can also view the model theory of $Th(\MM)$ as a by-product of the model theory of $T$ or of $(K,\preceq^k)$. This is the approach taken in \cite{baldwin-lessmann-2002}.}
For $\M\in K$ and $C\subseteq M$, we define,
$$K_{(C;\M)} = \left\{\N\in K: C\subseteq N,\,\diag^k(C;\N) = \diag^k(C;\M)\right\}.$$
Writing $K_{(C;\M)}$ over and over again is rather cumbersome, so we often write $K_C$ -- taking $\M$ to be clear from context or assuming that a $k$-variable diagram for $C$ is fixed. Also, we will often identify the pair $(C;\M)$ both with the set $C$ and the diagram $\diag^k(C;\M)$.
\end{defn}

\begin{obs}\label{obs:almost-EI}
There is a finite set $\mathbf{E}$ of 0-definable equivalence relations such that for any other 0-definable equivalence relation $E(\yy_1,\yy_2)$, there is a boolean combination $\phi(\yy_1,\yy_2)$ of members of $\mathbf{E}$ such that $T^{\lim}\models E(\yy_1,\yy_2)\bic \phi(\yy_1,\yy_2)$. In particular, let $\MM_\mathbf{E}$ be the reduct of $\MM^\eq$ consisting of the home-sort and the finitely many imaginary sorts corresponding to equivalence relations in $\mathbf{E}$; then $Th(\MM_\mathbf{E})$ eliminates imaginaries.

Moreover, each equivalence relation $E$ in $\mathbf{E}$ is expressible as boolean combination of formulas of $L^k$. Thus, for $\A\preceq^k\MM$ and $\aa,\bb\in A$, $\A\models E(\aa,\bb)$ if and only if $\MM\models E(\aa,\bb)$; this is true even when $\A$ is a finite substructure. Thus, each finite $L^k$-elementary substructure $\A$ of $\MM$, naturally expands to a substructure $\A_\mathbf{E}$ of $\MM_\mathbf{E}$ carrying all of the relevant information from $\MM^\eq$. In this way, we also obtain an expansion of the class $(K,\preceq^k)$ (see below) to $K_\mathbf{E}$, and where the ambiguity is not dangerous, we will identify $K$ and $K_\mathbf{E}$.
\end{obs}

In model theory, it is a common practice it is a common practice to Morley-ize a theory under study -- adding relation symbols for every 0-definable relation so that the theory automatically has quantifier-elimination. Indeed, subsequently taking the reduct to the language consisting of only the new relation symbols still does not change anything about the theory essentially. Here, we implicitly take a similar approach, working in a language in which the $k$-variable $k$-types are named as relation symbols as are the projection maps to the finitely-many needed imaginary sorts. As a point of interest, while this move is already justified in our Main Setting, it is possible to show that a ``capped'' $L^k$-theory -- in which every diagram of a finite subset of a model extends to a finite model -- \emph{automatically} falls into our Main Setting. This is discussed in Appendix \ref{app1} below.

\subsection{Rosiness, model-theoretic independence relations and geometric elimination of imaginaries}

To conclude this section, we recall some definitions and facts from \cite{me-2011a} about super/rosiness of $L^k$-theories and their limit theories consistent with Main Setting. We recall, in particular, we essentially defined the phrase, ``$K$ is rosy,'' for $K$ the class of finite models of $T$,  to mean, ``$T^{\lim}$ is rosy'' (this is in contrast to the developments in \cite{hyttinen-2000} and \cite{koponen-2006}). For the sake of brevity, then, we make several definitions in the context of the limit theory and its models, but we don't mention their translations into the context of the underlying class $K$ itself.

\begin{defn}
[Model-theoretic independence relation]
Let $T$, $K$ and $T^{\lim}$ be as in the Main Setting, and let $\MM\,(=\MM^\eq)$ be a countable model of $T^{\lim}$. An independence relation $\oind$ is a subset of $\left\{ (A,B,C):A,B,C\subset_\fin \MM\right\}$ satisfying the following for all $A,B,C\subset_\fin \MM$:
\begin{enumerate}
\item[] Invariance: If  $\sigma\in Aut(\MM)$, then $A\oind_CB$ iff $\sigma[A]\oind_{\sigma[C]}\sigma[B]$.
\item[] Preservation of algebraic dependence: If $A\oind_CB$, then $\acl(AC)\cap \acl(BC)=\acl(C)$.
\item[] Existence: $A\oind_CC$.
\item[] Extension: If $A\oind_CB$ and $BC\subseteq D\subset_\fin M$, then there is an $A'\equiv_{BC}A$ such that $A'\oind_CD$.
\item[] Symmetry: $A\oind_CB$ if and only if $B\oind_CA$
\item[] Transitvity: If $C_0\subseteq C\subseteq B$, then $A\oind_{C_0}B$ iff $A\oind_{C_0}C\,\&\,A\oind_CB$.
\item[] Local character: For every finite family $S = \{S_0,...,S_{n-1}\}$ of sorts of $\M^\eq$, there is a function $g_S:\omega\to\omega$ such that if $A,B\subseteq \bigcup_iS_i^{\M^\eq}$, then there is a subset $B_0\subseteq B$ such that $|B_0|\leq g_S(|A|)$ and $A\oind_{B_0}B$.
\end{enumerate}
The relation $\oind$ is a a notion of independence if it satisfies Invariance, Preservation of algebraic dependence, Extension, and,
\begin{enumerate}
\item[] Partial right-transtivity: If $C_0\subseteq C\subseteq B$, then $A\oind_{C_0}B$ implies $A\oind_{C_0}C\,\&\,A\oind_CB$.
\end{enumerate}
but not necessarily Symmetry, (full) Transitivity or Local character.
\end{defn}
In \cite{me-2011a}, we showed that for $T$, $T^{\lim}$ as in the Main Setting the restriction to triples of finite sets in the definition of an independence relation is fully consistent with the usual definitions for independence relations. Further, we found that in this setting, there is no actual need to prove Local Character -- it follows from the other axioms in this strong (``super'') way. In the next sections, we will build, from the assumption of ``efficient construbility,'' a notion of independence $\dind$ which is symmetric and transitive. From this, it will follow that $T$ is rosy. The key theorem from \cite{me-2011a} that we need here is the following; it is built upon on similar theorems of \cite{ealy-onshuus-2007} and \cite{adler-2007}:

\begin{thm}[Rosy = ``has an independence relation'']
Let $T$, $T^{\lim}$, and $K$ be as in the Main Setting. The following are equivalent:
\begin{enumerate}
\item $K$ is rosy.
\item $K$ admits an independence relation (without reference to Local Character).
\item $T^{\lim}$ is rosy.
\item $T^{\lim}$ admits an independence relation.
\item $T^{\lim}$ admits a notion of independence with Symmetry and Transitivity.
\item $T^{\lim}$ admits a notion of independence with Local character.
\end{enumerate}
(In either of the last two cases, that notion of independence is, then, an independence relation.)
\end{thm}

\section{Definition of `Efficient constructibility'}\label{sec:def-of-EC}

As  noted in the introduction, our remaining goal for this article is to show that ``efficiently constructible'' classes $K$ (arising as in the Main Setting along with $T$, $T^{\lim}$) are rosy by constructing a notion of independence with Symmetry and Transitivity. For this, of course, we will need to make several definitions leading up to the definition of efficient constructibility.

We should also apologize to the reader for our use of the word ``efficient'' here. It is well-known to finite-model theorists that the logic FO+IFP -- first-order logic extended with the inflationary fixed-point operator -- captures \emph{relational}-\texttt{PTime} (see \cite{abiteboul-vianu-1995}); thus, the central role of the IFP-operator in our definition already suggests that the word ``efficient'' is more-or-less appropriate in that sense.

From now on, we fix $T$, $K$ and $T^{\lim}$ as in the Main Setting with a fixed finite relational signature $\rho$, and $\MM$ always denotes a countable model of $T^{\lim}$. We define
$$\acl[\MM] = \left\{\acl(A): A\subset_\fin \MM\right\}$$
which is a family of finite sets. In this presentation, we will not make any real use of Morley-ization of the langauge in the sense of Appendix \ref{app1}.

\begin{defn}[Inflationary fixed-points of expanded formulas]
Let $X^{(r)}$ be a new relation symbol, not in $\varrho$. Then a formula, say $\psi(\xx) = \psi(x_0,...,x_{r-1};X)$, of $L[\varrho\cup\{X\}]$ will be called a proper expanded formula. For $A\in\acl[\MM]$, we define a subset $\psi^\infty[A]$ of $A^r$ as follows:
\begin{itemize}
\item $\psi^0[A] = \emptyset$
\item Given $\psi^t[A]\subseteq A^r$, define
$$\psi^{t+1}[A] = \psi^t[A]\cup\left\{\aa\in A^r:(A,\psi^t[A])\models \psi(\aa)\right\}$$
where $(A,\psi^t[A])$ is the $\varrho\cup\{X\}$-expansion of $A$ in which $X$ is interpreted is $\psi^t[A]$.
\item $\psi^\infty[A] = \bigcup_{t<\omega}\psi^t[A] = \psi^{|A|^{O(1)}}[A]$
\end{itemize}
Note that that for every $t<\omega$, the set $\psi^t[A]$ and $\psi^{t+1}[A]\setminus\psi^t[A]$ are first-order $A$-definable sets. We also note that satisfaction, here, is evaluated with respect to the induced substructure $A$, rather than with respect to $\MM$.
\end{defn}

\begin{defn}
A {\em pre-program for $K$} will consist of the  data,
$$\Pi = (\varrho^{test},\varrho^+,\Theta = \{\theta_i\}_{i<N_0},\Phi = \{\phi_i\}_{i<N},\Sigma = \{\psi_\sigma,\xi_\sigma\}_{\sigma:\Phi\to2},\yy = (y_0,...,y_{r-1}))$$
as follows:
\begin{itemize}
\item $\varrho^{test} = \varrho\cup\{X_0^{(r)},...,X_{N_0-1}^{(r)}\}$ is an expansion of $\varrho$ and for each $i<N$,  $\theta_i(x_0,...,x_{r-1};X_i^{(r)})$  is a proper expanded  $\exists$-formula of $L[\varrho\cup\{X_i\}]$.
\item  $\Phi = \left\{\phi_0,...,\phi_{N-1}\right\}$ is a family of sentences of $L[\varrho^{test}]$.
\item  $\varrho^+ = \varrho\cup\{Y^{(r)}\}$ is another expansion of $\varrho$; for each map $\sigma:\Phi\to2$,  $\psi_\sigma(x_0,...,x_{r-1})$ is a proper expanded $\exists$-formula of $L[\varrho^+]$;  $\xi_\sigma(\yy,z_0,...z_{m-1})$ is an arbitrary formula of $L[\varrho^+]$.
\end{itemize}
For $A\subset_\fin \MM$, we write $A^{test}$ for the expansion $(A,\theta_0^\infty[A],...,\theta_{N_0-1}^\infty[A])$, and we write $A^\sigma$ for the expansion $(A,\psi_\sigma^\infty[A])$.

Suppose $A = \acl(A)\subset_\fin \MM$. Write $\sigma_A$ for the function $\Phi\to2$ given by
$$\sigma_A(\phi_i) = 1\iff A^{test}\models \phi_i$$
for each $i<N$. We say that $A$ {\em requests attention at $(a_0,...,a_{r-1})\in A^r$} just in case,
$$\aa\in \psi_{\sigma_A}^\infty[A]\textrm{ and }A^{\sigma_A}\models \neg\exists \yy\,\xi_{\sigma_A}(\yy,a_{0},...,a_{r-1}).$$
If $A$ does not request attention at any $\aa\in A^r$, then we say that $A$ is $\Pi$-complete. Finally, $\Pi$ is genuinely a pre-program for $\K$ if  for any $A\in\acl[\MM]$
$$\textrm{$A$ is $\Pi$-complete iff $A\models T$ (iff $A\in K$)}.$$
\end{defn}

\begin{defn}
Let $\Pi = (\varrho^{test},\varrho^+,\Theta,\Phi,\Sigma,\yy)$ be a pre-program for $K$, and let $\M\models T$. A command operator for $\Pi$ is a map,
$$F:\acl[\M]\longrightarrow \P_\fin(S_E^\M)$$
satisfying the following whenever $A = \acl^\M(A)\subset_\fin M$.
\begin{itemize}
\item If $A$ is $\Pi$-complete, then $F(A) = \emptyset$.
\item Suppose $A$ is $\Pi$-incomplete. Up to an \emph{a priori} fixed linear order of quantifier-free $r$-types of $\varrho^{test}$ over $\emptyset$, suppose $A$ requests attention at $\aa\in A^r$, and $\pi = qtp(\aa;A^{test})$ is minimal for this condition. (In what follows, we will say that $(\Pi,F)$ acts on $A$ at $\aa$.)
Then $F(A)$ is of the form,
$$\left\{(\bb_{\cc},\cc)/E:\cc\in \mathtt{Req}(\sigma_A,\aa)\right\}$$
where $E =E_{\sigma_A,\pi}$ is a 0-definable equivalence relation on $r$-tuples and
$$\mathtt{Req}(\sigma_A,\aa) = \left\{\cc\in A^r:A^{test}\models \pi(\cc)\,\&\,A^{\sigma_A}\models \neg\exists \yy\,\xi_{\sigma_A}(\yy,\cc)\right\}$$
and $\bb_{\cc}\in M^r$ for each $\cc\in\mathtt{Req}(\sigma_A,\aa)$.
  Finally, we require that given $\sigma_A$, the pairs $\left(\cc,\,(\bb_{\cc},\cc)/E\right)$ are elements of an $\aa'$-definable relation (though not necessarily a function) for some $\aa'\models\pi$ in $A$.
\end{itemize}
 Together, $(\Pi,F)$ is a {\em program} for $K$, which then defines an operator
$$\mathtt{eval} = \mathtt{eval}_{\Pi,F}:\acl[\MM]\longrightarrow\acl[\MM]$$
as follows: For $A \in\acl[\MM]$,
$$\mathtt{eval}(A) = \acl\left(A\cup F(A)\right)\cap \MM$$

For $A=A_{-1}\subset_\fin M$, $(\Pi,F)$ induces a sequence $\mathtt{eval}^*(A)=(A_i)_{i<\omega}$ as follows:
$$A_0=\acl^\M(A_{-1}),\,\,A_{i+1} =\mathtt{eval}(A_i)\textrm{ for all $i<\omega$}.$$
\end{defn}

\begin{defn}
We say that $K$ is {\em efficiently constructible} if there is a program $(\Pi,F)$ for $K$ such that the following conditions are satisfied:
\begin{enumerate}
\item There is a polynomial $p(t)\in\NN[t]$ such that for any $A\subset_\fin \MM$, if $(A_i)_{i<\omega} = \mathtt{eval}^*(A)$, then $A_i = A_{p(|A|)}$ whenever $p(|A|)\leq i<\omega$.

\noindent (We may then define $A_{\Pi,F}:= A_{p(|A|)}$, and we note that $A\leq A_{\Pi,F}\leq_\fin \M$ and $A_{\Pi,F}\in K$.)

\item $(\Pi,F)$ is weakly automorphism invariant: For $A,B\subset_\fin \MM$, if there is an elementary bijection $f:A\to B$, then $A_{\Pi,F}\cong B_{\Pi,F}$ via an isomorphism extending $f$.

\item For all $A\subseteq B\subset_\fin M$, there is an automorphism $g\in Aut(\M/A)$ such that $g[A_{\Pi,F}]\subseteq B_{\Pi,F}$.
\end{enumerate}
\end{defn}

\subsection{Induction graphs and construction graphs}

Much of the proof of theorem \ref{tim:ec-implies-rosy} consists in defining a certain family of directed acyclic graphs (DAGs) -- construction graphs -- that represent all of the relevant model-theoretic information in runs of a program $(\Pi,F)$. (See  Appendix \ref{app:dags} for background on DAGs and $d$-separation.) Eventually, we will recover an independence relation $K$ (hence for $T^{\lim}$) by synthesizing two previously existing ideas. The first of these is that of $d$-separation in DAGs, which is well-known in statistical learning theory under the rubric of ``graphical models.'' In a fixed finite DAG, $d$-separation has several properties in common with model-theoretic independence relations (although Extension and Invariance don't make any sense there). The second idea is the definition of \th-indepedence, $\thind$, found in \cite{adler-2007}:
\begin{itemize}
\item $A\indep^\textsc{m}_CB$ iff $\acl(AC')\cap\acl(BC') = \acl(C')$ whenever $C\subseteq C'\subseteq \acl(BC)$
\item $A\thind_CB$ iff for every $D\supseteq BC$, there is an $A'\equiv_{BC}A$ such that $A'\indep^\textsc{m}_CD$.
\end{itemize}
In effect, we will just replace $\indep^\textsc{m}$ by a perturbation of $d$-separation in our construction graphs and play the same game as in \cite{adler-2007}. A certain easy observation about the definability of our construction graphs (in $\MM=\MM^\eq$) will guarantee that we can win this game.

Finally, we must remark that our construction seems to be only loosely tied to the original $K$-Construction problem (or Strong $L^k$-Canonization). Accordingly, it may be of some more general interest to investigate a larger world of connections between rosiness in, say, $\aleph_0$-categorical theories and constructibility conditions defined using inflationary fixed-points of formulas.

\begin{defn}
Let $\phi(x_0,...,x_{r-1};X^{(r)})$ be a formula of $L[\varrho\cup\{X\}]$. Let $A\subset_\fin \MM$, $R\subseteq A^r$ and
$$R' = R\cup \left\{\aa\in A^r:(A,R)\models \phi(\aa)\right\}.$$
For $\aa,\bb\in A^r$, we define
$$\textrm{``$\bb\forces^\phi\aa\in R'$ w.r.t. $(A,R)$''}$$
to mean that:
\begin{enumerate}
\item $\aa\in R'\setminus R$ and $\bb\in R$;
\item $(A,R)\models \phi(\aa)$;
\item $(A,R_{(\bb)})\models \neg\phi(\aa)$ where $R_{(\bb)} = R\setminus \acl(\bb)^r$.
\end{enumerate}
Assuming $\phi^\infty[A] = \phi^e[A]$, we define $IG_\phi[A,e]$ to be the directed graph with vertex set $e{+}1\times A^r$ and edge set $\bigcup_{t<e}E^t_\phi[A,e]$, where for each $t<e$,
$$E^t_\phi[A,e] = \bigcup\begin{cases}
\left\{\,\,\left((t,\aa),(t{+}1,\aa)\right):\aa\in A^r\right\}\\
\left\{\,\,\left((t,\bb),(t{+}1,\aa)\right):\textrm{$\bb\forces^\phi\aa\in \phi^{t+1}[A]$ w.r.t. $(A,\phi^t[A])$}\right\}\\
\end{cases}$$
\end{defn}

\begin{defn}
To define the induction graph of $\Pi$ on $A$, denoted $IG_{\Pi}[A]$, we first set
$$e^\Pi = \min\left\{e:\bigwedge_{i<N_0}\theta_i^\infty[A] =\theta_i^e[A]\right\}.$$
Then $IG_\Pi^0[A]$ has vertex set $e^\Pi{+}1\times A^r$ and edge set
$$E_\Pi[A] = \bigcup_{i<N_0}E_{\theta_i}[A,e]$$
Now, let $\sigma = \sigma_A$ and $e_A =\min\left\{e:\psi_\sigma^\infty[A] =\psi_\sigma^e[A]\right\}$. Then $IG_\Pi[A]$, with vertex set $(e^\Pi{+}e_A{+}1)\times A^r$, is obtained by gluing $IG_{\psi_\sigma}[A,e_A]$ to the end of $IG^0_\Pi[A]$ in the natural way.
\end{defn}

\begin{defn}
Let $A\subset_\fin \MM$.
We first define $CG^0[A] = CG^0_{\Pi,F}[A]$ as follows:
\begin{enumerate}
\item Let $\mathtt{eval}^*(A) = (A_i)_{i<\omega}$ and set $p = p(|A|)$. (For the statement here, we assume that $A_i$ is $\Pi$-incomplete for each $i\geq p(|A|)$.)
\item  For each $i=0,1,...,p-1$, we define an enlargement $IG_\Pi[A_i]^+$ of the induction graph $IG_\Pi[A_i]$. Assuming  $(\Pi,F)$ acts on $A_i$ at $\aa_i\in A_i^r$ and setting $\pi_i = qtp(\aa_i;A_i^{test})$, we define
$$C_i = \left\{\cc_i\in A_i^r: A_i^{test}\models \pi_i(\cc)\,\&\,A_i^{\sigma_{A_i}}\models \neg\exists \yy\,\xi_{\sigma_{A_i}}(\yy,\cc) \right\}$$
and let $\cc\mapsto (\dd_{\cc},\cc)/E$ be the map associated with the application of $F$.
To make $E_\Pi[A_i,\aa_i]^+$, we just add a new layer to $E_\Pi[A_i]$: the set of new vertices is  $\{\star_i\}\times A_{i+1}^r$, and the new edges are of the form
$$\left(\,(e^\Pi(A_i){+}e_{A_i}{+}1,\cc), (\star_i,\bb)\,\right)$$
for $\cc\in C_i$ and $\bb\in A_{i+1}^r\cap \acl^{\M^\eq}\left( \,(\dd_{\cc},\cc)/E\,\right)$.

\item We obtain $CG^0[A]$ be gluing/identifying each vertex $(\star_i,\aa)$ of $E_\Pi[A_i]^+$ with the vertex $(0,\aa)$ of $E_\Pi[A_{i+1},\aa_{i+1}]^+$.
\end{enumerate}
Next, we define the construction graph $CG[A]$ by pruning $CG^0[A]$ as follows:
\begin{enumerate}
\item $CG[A]$ retains only the following vertices:
\begin{itemize}
\item The vertices of the very first layer (those from the first layer of $E_\Pi[A_0]^+$), which we now write as $(\star_{-1},\aa)$.
\item Those of the form $(\star_i,\bb)$ for some $i\leq p$
\end{itemize}
\item For $i=-1,0,...,p-1$, $\left(\,(\star_i,\aa),(\star_{i+1},\bb)\,\right)$ is an edge of $CG[A]$ if one of the following holds:
\begin{itemize}
\item $rng(\aa) = rng(\bb)$;
\item There is a (directed) path from $(\star_i,\aa)$ to $(\star_{i+1},\bb)$ in $E_\Pi[A_i,\aa_i]^+$, \emph{\textbf{and}}
 $\aa\in\acl(\bb)$.
\end{itemize}
\end{enumerate}
\end{defn}

We will need to do a bit more bookkeeping in our construction graphs than we can easily express without some further machinery. Thus, we define a certain ``tuple-labeling function'' that connects everything produced in a run of the program $(\Pi,F)$ on $A\subset_\fin M$ back to the original set $A$. From this, we define the notion of ``hereditary descendants'' in our construction graphs, which will be indispensable in both the definition and the analysis of our independence relation.

\begin{defn}
Tuple-labeling maps $\lambda^A:V(CG[A])\to H(A)$ and hereditary descendents.

For a non-empty set $X$, we define $H(X)$ as follows:
\begin{itemize}
\item $H_0(X) = (\{0\}\times X)^{<\omega}$
\item $H_{n+1}(X) = \left\{\left(\,(n{+}1,\aa_0),...,(n{+}1,\aa_{k-1})\,\right):\aa_0,...,\aa_{k-1}\in H_n(X), 0<k<\omega\right\}$
\item $H(X) = \bigcup_{n<\omega}H_n(X)$.
\end{itemize}
We define $\lambda^A:V(CG^0[A])\to H(A)$ as follows.
\begin{itemize}
\item Let $\lambda_0^A$ be just $(\star_{-1},\aa)\mapsto \left((0,a_0),...,(0,a_{r-1})\right)$
\item Given $\lambda_i^A$: for a vertex $(\star_{i+1},\bb)$, let $(\star_i,\aa_0),...,(\star_i,\aa_{n-1})$ enumerate $(\star_{i+1},\bb)$'s predecessors in $CG[A]$. Then set
$$\lambda^A_{i+1}(\star_{i+1},\bb) = \left(\,(i{+}1,\lambda^A_i(\aa_0)),...,(i{+}1,\lambda^A_i(\aa_{n-1}))\,\right).$$
\item Set $\lambda^A = \bigcup_{i\leq p}\lambda^A_i$
\end{itemize}
Finally, if $A_0\subseteq A$, we define the set of {\em hereditary descendants} of $A_0$ with respect to $A$, $\mathtt{hdesc}(A_0;A)$ inductively as follows:
\begin{enumerate}
\item $\{\star_{-1}\}\times A_0^r\subseteq\mathtt{hdesc}(A_0;A)$
\item If $\lambda^A(\star_{i+1},\bb) = \left(\,(i{+}1,\lambda^A_i(\star_i,\aa_0)),...,(i{+}1,\lambda^A_i(\star_i,\aa_{n-1}))\,\right)$ and $(\star_i,\aa_j)\in \mathtt{hdesc}(A_0;A)$ for some $j<n$, then $(\star_{i+1},\bb)\in \mathtt{hdesc}(A_0;A)$
\end{enumerate}
\end{defn}

The following observation is very important, even though it follows very easily from noticing that (i) finitely many iterations of the inflationary fixed-point operation amount to a first-order formula, and (ii) given $A\subset_\fin \MM$, each of the hypothetical scenarios $A\subseteq B\subset_\fin \MM$ can be encoded as a first-order statement.

\begin{obs}[Definability of construction graphs]\label{obs:def-of-CGs}
For each $k<\omega$, there is a finite family of $X^k_0,...,X^k_{n_k-1}$ of sorts of $\MM^\eq$ such that the following holds: Let $A\subseteq B\subset_\fin \MM$. Then for any $g\in Aut(\MM/A)$ such that $g[A_{\Pi,F}]\subseteq B_{\Pi,F}$, there is a mapping,
$$f^A: \mathtt{hdesc}(A;B)\longrightarrow\dcl^\eq(g[A_{\Pi,F}])$$
satisfying the following conditions:
\begin{enumerate}
\item If $k\neq \ell$, then $\{X^k_i\}_{i<n_k}\cap \{X^{\ell}_j\}_{j<n_{\ell}}=\emptyset$
\item For each $k\leq p(|B|)$ and $(\star_k,\aa)\in (\{\star_k\}{\times}B^r_k)\cap \mathtt{hdesc}(A;B)$, $f^A(\star_k,\aa)\in X^k_0\,{\dot\cup}\,\cdots\,{\dot\cup}\, X^k_{n_k-1}$
\item For each $k\leq p(|B|)$, and $(\star_k,\aa_1),(\star_k,\aa_2)\in \{\star_k\}{\times}B_k^r\cap \mathtt{hdesc}(A;B)$,
$$\tp(f^A(\star_k,\aa_2)/A) = \tp(f^A(\star_k,\aa_2)/A)\textnormal{ in $\MM = \MM^\eq$}$$
implies
$$\tp_{\exists}(\aa_1;B_k^{test})=\tp_{\exists}(\aa_2;B_k^{test})$$
where $\tp_\exists(-;B_k^{test})$ indicates a partial type consisting of existential formulas with satisfaction evaluated in the finite structure $B_k^{test}$.
\item For any $k\leq p(|B|)$ and  $(\star_k,\aa)\in (\{\star_k\}{\times}B_k^r)\cap \mathtt{hdesc}(A;B)$,
$\acl(\aa)\subseteq\acl\left(A\cup\left\{f^A(k,\aa)\right\}\right)$
\end{enumerate}
\end{obs}

We derive the following lemma as an immediate consequence of Observation \ref{obs:def-of-CGs} and the fact that $T$ is $\aleph_0$-categorical, hence uniformly locally finite. We refer the reader to  Appendix \ref{app:dags} for the notion of $d$-separation and the notation $[-\amalg-|-]$.
\begin{lemma}\label{lemma:bdd-local-wt}
There is function $\mathtt{loc}:\omega\times\omega \to\omega$ such that for all $A,B\subseteq C\subset_\fin \MM$,
 and any $\cc_0,...,\cc_n\in C^r$ with $n\geq \mathtt{loc}(|A|,|B|)$, if:
$$\left[(\star,\cc_i)\,\amalg\,(\star,\cc_j)\,\,|\,\,\mathtt{hdesc}(AB;C)\right]_{CG[C]}$$
for all $i<j\leq n$ (setting $\star = \star_{-1}$ forevermore), then
$$\left[(\star,\cc_i)\,\amalg\,\{\star\}{\times} A^r\,\,|\,\,\mathtt{hdesc}(B;C)\right]_{CG[C]}$$
for some $i\leq n$.
\end{lemma}

\section{Deviation and $d$-Independence}\label{sec:dev-and-d-indep}

In this section, we use the construction graphs developed  above to define an independence relation $\dind$ on our efficiently constructible class $K$. To do this, we first make a perturbation $\downarrow$ -- called local separation, for lack of inspiration -- of the $d$-separation relation; thereafter, we use local separation as a substitute for the $\indep^\textsc{m}$ relation of \cite{adler-2007}, and we proceed along similar lines.
\begin{defn}
Let $A,B,C\subseteq D=\acl(D)\subset_\fin M$. We say that $A,B$ are locally separated over $C$ in $D$ -- denoted $A\downarrow_CB/D$ -- if
$$\left[\,\{\star\}{\times}A^r\,\amalg\,\{\star\}{\times}B^r\,\,|\,\,\mathtt{hdesc}(\acl(C');D)\right]_{CG[D]}$$
whenever $C\subseteq C'\subseteq \acl(BC)$.

Again with $B,C\subseteq D\subset_\fin M$, though $D$ need not be algebraically closed, let $\pi(\xx)$ be a partial type over $BC$. We define $\Delta_0[\pi(\xx),C]_D$ to be the set of finite sets $D\subseteq D'\in\acl[\M]$ such that:
\begin{enumerate}
\item $\pi(\xx)$ {\em is} realized  in $D'$;
\item For every realization $\aa$ of $\pi(\xx)$ in $D'$,
$$\aa\downarrow_{BC}D/D'\,\,\implies\,\, \aa\,\hbox{${\downarrow}\kern-.5em\hbox{\char'57}$}\,_CD/D'$$
(using $\aa$ as shorthand for the set $rng(\aa)$).
\end{enumerate}
We define $\Delta[\pi,C]_D$ to the be the set of isomorphism types over $D$ appearing in $\Delta_0[\pi,C]_D$, and we call $\Delta[\pi,C]_D$ {\em the deviation of $\pi$ over $C$ with respect to $D$}.

Finally, we define $A\dind_CB$ to mean that $\Delta[p,C]_D$ is finite whenever $ABC\subseteq D\subset_\fin M$, $p = tp(\aa/BC)$ and $\aa$ is an enumeration of $A$. We also say, then, that $p$ does not deviate over $C$.
\end{defn}

\begin{lemma}
Let $A,B,C\subseteq D\subset_\fin M$ where $D = \acl(D)$.
\begin{enumerate}
\item[] {\em $\downarrow$-Monotonicity}: If $A\downarrow_CB/D$ and $B_0\subseteq B$, then $A\downarrow_CB_0/D$.
\item[] {\em $\downarrow$-Base-monotonicity}: If $A\downarrow_CB/D$ and $B_0\subseteq B$, then $A\downarrow_{CB_0}B/D$.
\item[] {\em Preservation of algebraic dependence} If $A\downarrow_CB/D$, then $\acl(AC)\cap\acl(BC)=\acl(C)$.
\end{enumerate}
\end{lemma}
\begin{proof}[Proof of $\downarrow$-Monotonicity]
Assuming $A\downarrow_CB/D$, we consider $C\subseteq X\subseteq \acl(B_0C)$. Clearly, $C\subseteq X\subseteq \acl(BC)$, so
$$\left[\,\{\star\}{\times}A^r\,\amalg\, \{\star\}{\times}B^r\,\,|\,\,\mathtt{hdesc}(\acl(X);D)\,\right]_{CG[D]}.$$
By the monotonicity of $[\,-\,\amalg\,-\,|\,-\,]$ (see the appendix), we find
$$\left[\,\{\star\}{\times}A^r\,\amalg\, \{\star\}{\times}B_0^r\,\,|\,\,\mathtt{hdesc}(\acl(X);D)\,\right]_{CG[D]}$$
and this suffices.
\end{proof}

\begin{proof}[Proof of $\downarrow$-Base-monotonicity]
Assuming $A\downarrow_CB/D$, we now consider $B_0C\subseteq X\subseteq \acl(BC)$. Again, $C\subseteq X\subseteq\acl(BC)$, so
$$\left[\,\{\star\}{\times}A^r\,\amalg\, \{\star\}{\times}B^r\,\,|\,\,\mathtt{hdesc}(\acl(X);D)\,\right]_{CG[D]}$$
follows from the assumption.
\end{proof}

\begin{proof}[Proof of preservation of algebraic dependence]
For the contrapositive, suppose $e\in \acl(AC)\cap\acl(BC)$ and $e\notin\acl(C)$. Then $\underset{\textrm{$n$ times}}{\underbrace{(e,...,e)}}$ witnesses,
$$\left[\,\{\star\}{\times}A^r\,\,\hbox{${\amalg}\kern-.7em\hbox{\char'57}$}\,\, \{\star\}{\times}B^r\,\,|\,\,\mathtt{hdesc}(\acl(X);D)\,\right]_{CG[D]}$$
so $A\,\hbox{${\downarrow}\kern-.5em\hbox{\char'57}$}\,_CB/D$.
\end{proof}

In preparation for some slightly more complex arguments, we collect a few useful observations
\begin{obs}\label{obs:dev-containment}
Let $B,C\subseteq D\subseteq D_1\subseteq E\in\acl[\M]$, and let $\pi_0(\xx)\subseteq \pi(\xx)$ be partial types over $BC$.
\begin{enumerate}
\item If $E\in \Delta[\pi,C]_{D}$, then $E\in\Delta[\pi,C]_{D_1}$
\item If $E\in\Delta[\pi_0,C]_D$, then $E\in\Delta[\pi,C]_D$.
\end{enumerate}
\end{obs}

\begin{obs}\label{obs:alg-extensions}
Let $\pi(\xx)$ be a partial type over $C\subset_\fin M$. If every complete extension of $\pi$ to $C$ is algebraic, then $\pi$ is algebraic.
\end{obs}

The following proposition just collects together what we know of $\dind$ so far; that is, $\dind$ is a notion of independence -- if not an independence relation -- even if the underlying program $(\Pi,F)$ does not actually witness efficient constructibility.

\begin{prop}\label{prop:properties-without-bdd-loc-wt}
$\dind$ has the following properties:
\begin{enumerate}
\item[] {\em Invariance}: If $A,B,C\subset_\fin M$ and $\sigma\in Aut(\M)$, then
$A\dind_CB\iff \sigma[A]\dind_{\sigma[C]}\sigma[B]$.

\item[] {\em Preservation of algebraic dependence}: For $A,B,C\subset_\fin M$, if $A\dind_CB$, then
$$\acl(AC)\cap \acl(BC) = \acl(C).$$

\item[] {\em Existence}: If $A,C\subset_\fin M$, then $A\dind_CC$.

\item[] {\em Extension}: For $A,B,B_1,C\subset_\fin M$ with $BC\subseteq B_1$, if $A\dind_CB$, then there is an $A'\equiv_{BC}A$ such that $A'\dind_CB_1$.
\item[] {\em Partial right-transitivity}: For $A,B_0,B,C\subset_\fin M$ with $B_0\subseteq B$, if $A\dind_CB$, then $A\dind_CB_0$ and $A\dind_{CB_0}B$.

\item[] {\em Partial left-transitivity}: For $A,A_0,B,C\subset_\fin M$ with $A_0\subseteq A$, If $A_0\dind_CB$ and $A\dind_{CA_0}B$, then $A\dind_CB$.

\end{enumerate}
\end{prop}

Both Invariance and Existence are self-evident from the definitions, and Preservation-of-algebraic-dependence for $\dind$ is an easy consequence of  Preservation-of-algebraic-dependence for $\downarrow$. Partial left-transitivity is somewhat more involved, so we defer its proof to later in this section; the proof wants for Lemma \ref{lemma:non-dev-ext-to-algebraicity} below.
\begin{proof}[Proof of Extension]
Let $A,B,B_1,C\subset_\fin M$ with $BC\subseteq B_1$, and suppose $A\dind_CB$. Let $\aa$ be an enumeration of $A$, and let $p(\xx) = tp(\aa/BC)$. By the $\aleph_0$-categoricity of $T = Th(\M)$, let $p_0,...,p_{n-1}\in S(B_1)$ be an enumeration of the complete extensions of $p$ to $B_1$. Towards a contradiction, suppose that for each $i<n$, there is some $B_1\subseteq D_i\subset_\fin M$ such that $\Delta[p_i,C]_{D_i}$ is infinite. Without loss of generality, we may assume that  $\Delta[p_i,C]_{D}$ is infinite for each $i<n$, where $D = D_0\cup \cdots\cup D_{n-1}$. It follows that $\Delta[p,C]_D$ is infinite, which contradicts the $A\dind_CB$. Hence, we may certainly choose some $p_i$ and a realization $\aa'\models p_i$ such that $\aa'\dind_CB_1$, as desired.
\end{proof}

\begin{proof}[Proof of Partial right-transitivity]
Let $A,B,B_0,C\subset_\fin M$ with $B_0\subseteq B$, and suppose $A\dind_CB$. We show that $A\dind_{CB_0}B$. Let $E\in \acl[\M]_D\setminus \Delta_0[\tp(\aa/BC),C]_D$, where $BC\subseteq D\subseteq E$ and $\aa$ enumerates $A$. We obtain an $\aa_1\in E^{|\aa|}$ such that $\aa_1\models \tp(\aa/BC)$, $\aa_1\downarrow_{BC}D/E$ and $\aa_1\downarrow_CD/E$. BY $\downarrow$-base-monotonicity, we have $\aa_1\downarrow_{CB_0}D/E$, so $\aa_1$ violates the condition, ``$\aa_1\downarrow_{CB_0}D/E\implies \aa_1\,\hbox{${\downarrow}\kern-.5em\hbox{\char'57}$}\,_CD/E$.'' We have shown, then, that
$$\acl[\M]_D\setminus \Delta_0[\tp(\aa/BC),C]_D\subseteq \acl[\M]_D\setminus \Delta_0[\tp(\aa/BC),CB_0]_D$$
and with $A\dind_CB$, it follows that $A\dind_{CB_0}B$, as desired. The proof that $A\dind_CB_0$ is similar, so we omit that portion.
\end{proof}

\begin{lemma}\label{lemma:bad-seq-maker}
Let $A,B,C\subset_\fin M$ where $|A|, |B|\leq r$, and suppose $A\dind_CB$ but $B\ndind_CA$. Then $B\nsubseteq \acl(AC)$.
\end{lemma}
\begin{proof}
Towards a contradiction, suppose $B\subseteq \acl(AC)$. Let $\aa$ and $\bb$ be enumerations of $A$ and $B$, respectively. From the hypothesis $B\ndind_CA$, we may take $\Delta[p(\aa,\yy),C]_{D\aa}$ to be infinite, where $p = tp(\aa\bb/C)$ and $C\subseteq D\subset_\fin M\setminus A$. From preservation of algebraic dependence, we know that $B\ndind_{AC}AD$. Applying Extension and Invariance repeatedly, we implement the following construction:

\noindent\emph{Construction}:
\begin{itemize}
\item[] Stage 0: Set $\aa_0 = \aa$
\item[] Stage $i{+}1$: At the beginning of stage $i+1$, we have $\aa_0,...,\aa_i$, pairwise distinct, such that for each $j\leq i$,
\begin{itemize}
\item $\aa_j\equiv_{BD}\aa_0$;
\item $\aa_j\dind_{BD}\,D\bb\aa_0...\aa_{j-1}$.
\end{itemize}

We then choose $\aa_{i+1}\equiv_{D\bb\aa_0...\aa_{i-1}}\aa_i$ such that $\aa_{i+1}\dind_{BD}\,D\bb\aa_0...\aa_i$.
\end{itemize}
Since $\Delta[p(\xx,\bb),C]_E$ is finite for almost every $E$ containing $C\bb$ (up to automorphisms over $C\bb$), and applying Ramsey's theorem and the $\aleph_0$-categoricity of $T$, we may also choose a chain $E_0\subseteq E_1\subseteq\cdots\subseteq E_i\subseteq\cdots \subset_\fin M$ of algebraically closed sets such that
$$\left[ (\star,\aa_i)\amalg (\star,\aa_j)\,|\,\mathtt{hdesc}(\acl(D\bb);E_k\right]_{CG[E_k]}$$
 and
 $$\left[(\star,\aa_i)\,\hbox{${\amalg}\kern-.7em\hbox{\char'57}$}\,\,(\star,\bb)\,|\,\mathtt{hdesc}(\acl(D);E_k) \right]_{CG[E_k]}$$
  whenever $i<j<k<\omega$. This contradicts Lemma \ref{lemma:bdd-local-wt}, so this lemma is proven.
\end{proof}

Lemma \ref{lemma:non-dev-ext-to-algebraicity} now follows from Lemma \ref{lemma:bad-seq-maker} and Observation \ref{obs:alg-extensions}.

\begin{lemma}\label{lemma:non-dev-ext-to-algebraicity}
Let $C\subset_\fin M$ and $\aa,\bb\in M^r$, and let $p(\xx,\yy) = tp(\aa\bb/C)$. Let $C\bb\subseteq D\subset_\fin M$, and suppose $\Delta[p(\xx,\bb),C]_D$ is infinite. If $q(\xx,\bb)$ is a complete extension of $p(\xx,\bb)$ to $D$ which does not deviate over $C\bb$, then $q(\xx,\bb)$ is algebraic.
\end{lemma}

\begin{proof}[Proof of Partial left-transitivity]
Assume $\aa_1\dind_CB$ and $\aa_2\dind_{C\aa_1}B$, and towards a contradiction, suppose $\aa_1\aa_2\ndind_CB$, where $\aa_1,\aa_2\in M^{<\omega}$ and $BC\subset_\fin M$.  By a straightforward argument using the Extension, we may work under the assumption that $\Delta[tp(\aa_1\aa_2/BC),C]_{BC}$ is infinite. By Existence and the preceding lemma, we know that $tp(\aa_1\aa_2/BC)$ must be algebraic -- i.e. $\aa_1\aa_2\in \acl(BC)$. For the contradiction, then, we will derive that $tp(\aa_1\aa_2/BC)$ is non-algebraic.

For a (local) contradiction, suppose $tp(\aa_1\aa_2/BC)$ is algebraic. From preservation of algebraic dependence, one can show that $\aa_1\aa_2\ndind_CB$ implies $\aa_1\aa_2\notin \acl(C)$, and it follows that  $tp(\aa_1/C)$ and $tp(\aa_2/C\aa_1)$ are not {\em both} algebraic. Similarly, as $tp(\aa_1\aa_2/BC)$ is algebraic, it cannot be that both $tp(\aa_1/BC)$ and $tp(\aa_2/BC\aa_1)$ are non-algebraic. If $tp(\aa_1/BC)$ is algebraic, then we have $\aa_1\ndind_CB$, and if $tp(\aa_2/BC\aa_1)$ is algebraic, then $\aa_2\ndind_{C\aa_1}B$ -- in either case, a contradiction. Thus, $tp(\aa_1\aa_2/BC)$ must be non-algebraic -- the higher level contradiction -- which completes the proof.
\end{proof}

\begin{thm}
$\dind$ is symmetric and fully transitive. With Proposition \ref{prop:properties-without-bdd-loc-wt}, $\dind$ is an independence relation for $K$, so $K$ is rosy.
\end{thm}
\begin{proof}
By partial right- and left-transitivity, we need only demonstrate symmetry. Let $C\subset_\fin M$ and $\aa,\bb\in M^{<\omega}$, and assume $\aa\dind_C\bb$. Towards a contradiction, we suppose that $\bb\ndind_C\aa$ -- that is, let $C\subseteq D\subset_\fin M\setminus rng(\aa)$ such that $\Delta[tp(\bb/C\aa),C]_{D\aa}$ is infinite. By lemma \ref{lemma:bad-seq-maker}, we know that $p(\aa,\yy) = tp(\bb/C\aa)$ is non-algebraic, so $p(\aa,\yy)$ has a non-algebraic extension $q(\aa,\yy)$ to $D\aa$, which by lemma \ref{lemma:non-dev-ext-to-algebraicity}, must deviate over $C\aa$. Thus, we can choose $D\subseteq D'\subset_\fin M\setminus rng(\aa)$ such that $\Delta[q(\aa,\yy),C\aa]_{D\aa}$ is infinite. Using the construction from the proof of lemma  \ref{lemma:bad-seq-maker}, we obtain a sequence $(\bb_i,E_i)_{i<\omega}$ such that $(\bb_i)_{i<\omega}$ is $\acl(D'\aa)$-indiscernible, $\bb_0 \equiv_{D'\aa}\bb$ and for every $i<\omega$,
$\bb_i\dind_{D'\aa}D'\aa\bb_0...\bb_{i-1}$ and
$$\bb_i\downarrow_{D\aa}D'\aa/E_j\,\,\implies \bb_i\,\hbox{${\downarrow}\kern-.5em\hbox{\char'57}$}\,_{C\aa}D'\aa/E_j$$
whenever $i<j<\omega$. By Ramsey's theorem, again, we may then assume that either $\bb_i\,\hbox{${\downarrow}\kern-.5em\hbox{\char'57}$}\,_{D\aa}D'\aa/E_j$ for all $i<j<\omega$, of $\bb_i\,\hbox{${\downarrow}\kern-.5em\hbox{\char'57}$}\,_{C\aa}D'\aa/E_j$ for all $i<j<\omega$. In either case, we derive a contradiction to lemma  \ref{lemma:bdd-local-wt}.
\end{proof}

\bibliographystyle{plain}


\section{Introduction}
For a closed orientable 3-manifold $M$, we say that $V_{1}\cup_{S} V_{2}$ is a {\it Heegaard splitting} of $M$ if $V_{1}, V_{2}$ are handlebodies such that $M=V_{1}\cup V_{2}$ and $\partial V_{1}=\partial V_{2}=S$.
Heegaard splittings of compact orientable 3-manifolds with nonempty boundaries can be defined similarly (see Section \ref{sec-pre}).
In \cite{He}, Hempel gave the definition of \textit{distance} of Heegaard splitting by using curve complex introduced by Harvey \cite{Ha}, and showed that there exist arbitrarily high distance Heegaard splittings for closed 3-manifolds by using a construction of Kobayashi \cite{K2}.
The manifolds are obtained by gluing two copies of handlebodies along their boundaries by the $n$th power of a pseudo-Anosov map for each $n$.
Abrams and Schleimer \cite{AS} showed that the distance of the Heegaard splitting grows linearly with respect to $n$ by using the result of Masur and Minsky \cite{MM1}.  Moreover, Evans \cite{E} gave a combinatorial method to construct Heegaard splittings of high distance.
The main purpose of this paper is to give an answer to the following question.

\medskip
\noindent
{\bf Question}
Given $n\geq 1$ and $g\geq 2$, does there exist a genus-$g$ Heegaard splitting with distance exactly $n$?
\medskip

For certain values, there are known examples that answer the above question affirmatively.
For example, Berge and Scharlemann \cite{BS} showed that there exist 3-manifolds each of which admits  genus-$2$ Heegaard splittings with distance exactly $3$.

In this paper, for each integer $n\geq 2$, we first construct a Heegaard splitting of a compact orientable 3-manifold with nonempty boundary which has distance exactly $n$.

\begin{theorem}\label{thm-1}
For any integers $n\geq 2$ and $g\geq 2$, there exists a genus-$g$ Heegaard splitting $C_{1}\cup_{P}C_{2}$ with distance exactly $n$, where $C_{1}$ and $C_{2}$ are compression bodies.
\end{theorem}

To prove Theorem \ref{thm-1}, we give a method of constructing a pair of curves with distance exactly $n$.
In fact, Schleimer \cite{S} gave a method of constructing a pair of curves with distance exactly four on the five-holed sphere by using {\it subsurface projection maps} defined by Masur and Minsky \cite{MM2} (for the definition, see Section \ref{sec-pre}).
In Section \ref{sec-curves}, we mimic the idea of Schleimer to construct a pair of curves with distance exactly $n$ for any positive integer $n$.
By using the pair of curves and the properties of a compression body obtained by adding a 1-handle to $S\times[0,1]$ where $S$ is a closed surface (for detail, see Section \ref{sec-disk-complex}), we give the proof of Theorem \ref{thm-1}.
As a consequence of Theorem \ref{thm-1}, we have Corollary \ref{thm-2}.

\begin{corollary}\label{thm-2}
For any integers $n\geq 2$ and $g\geq 2$, there exists a genus-$g$ Heegaard splitting of a closed 3-manifold with distance exactly $n$.
\end{corollary}

\begin{remark}
{\rm
In \cite{QZG}, the statement completely including Corollary \ref{thm-2} is given.
In fact, they show in \cite[Theorem 1]{QZG} that for each pair of integers $n\geq 1$ and $g\geq 2$ with $(n,g)\neq (1,2)$, there is a genus-$g$ Heegaard splitting of a closed 3-manifold with distance $n$.
We note that it is also remarked in \cite{QZG} that the pair $(n,g)=(1,2)$ is not realizable.
}
\end{remark}

After finishing the first version of this paper, Ruifeng Qiu informed us that there was a gap in the proof of the theorem which we used in the proof of Corollary 1.2 in the first version, and he sent us the paper \cite{MQZ}.
We tried to fill the gap, and could give a partial result which works to give the corollary in our setting.
By the way, we learned from \cite{MQZ} that Li \cite{Li} gave a very sharp estimation of the radius of the image of the disk complex of a compact 3-manifold by subsurface projections, and this drastically improved the conclusion of Corollary 1.2 in the first version.
When the new version was almost completed, we found that \cite{QZG} was uploaded on arXiv.org, and the main result of \cite{QZG} completely covers Corollary \ref{thm-2} of this paper.
Further, Yanqing Zou, who is one of the authors of \cite{QZG}, informed us that our arguments in the revised version mentioned above contains a gap and made some suggestions.
Thanks to the suggestion, precisely speaking with consulting \cite{QZG}, we could give the formulation of Proposition \ref{prop-appendix} in this paper.

We thank Dr. Michael Yoshizawa for many helpful discussions, particularly for teaching us the ideas of his dissertation which includes the existence of Heegaard splitting of distance $2n$ for each integer $n\geq 1$,
and we also thank Professor Yo'av Rieck for helpful information.
We would like to especially thank Professor Ruifeng Qiu and Dr. Yanqing Zou for giving us information including the preprints \cite{MQZ, QZG}.

\section{Preliminaries}\label{sec-pre}

Let $S$ be a compact connected orientable surface with genus $g$ and $p$ boundary components.
A simple closed curve in $S$ is {\it essential} if it does not bound a disk in $S$ and is not parallel to a component of $\partial{S}$.
An arc properly embedded in $S$ is {\it essential} if it does not co-bound a disk in $S$ together with an arc on $\partial{S}$.
We say that $S$ is {\it sporadic} if $g=0, p\leq 4$ or $g=1, p\leq1$.
We say that $S$ is {\it simple}, if $S$ contains no essential simple closed curves.
We note that $S$ is simple if and only if $S$ is a 2-sphere with at most three boundary components.
A subsurface $X$ in $S$ is {\it essential} if each component of $\partial X$ is contained in $\partial S$ or is essential in $S$.

\medskip
\noindent
{\bf Heegaard splittings}

A connected 3-manifold $V$ is a {\it compression body} if there exists a closed (possibly empty) surface $F$ and a 0-handle $B$ such that $V$ is obtained from $F\times[0, 1]\cup B$
by adding 1-handles to $F \times \{1\}\cup \partial B$.
The subsurface of $\partial V$ corresponding to $F\times\{0\}$ is denoted by $\partial_{-} V$.
Then $\partial_{+} V$ denotes the subsurface $\partial V\setminus\partial_{-} V$ of $\partial V$.
The genus of $\partial_{+} V$ is the {\it genus} of the compression body $V$.
A compression body $V$ is called a {\it handlebody} if $\partial_- V=\emptyset$.
A disk $D$ properly embedded in $V$ is called an {\it essential disk} if $\partial D$ is an essential simple closed curve in $\partial_{+}V$.

Let $M$ be a compact orientable 3-manifold.
We say that $C_{1}\cup_{P}C_{2}$ is a {\it genus-$g$ Heegaard splitting} of $M$ if $C_{1}$ and $C_{2}$ are compression bodies of genus $g$ in $M$ such that $C_{1}\cup C_{2}=M$ and $C_1\cap C_2=\partial_{+}C_{1}=\partial_{+}C_{2}=P$.
Alternatively, given a Heegaard splitting $C_{1}\cup_{P}C_{2}$ of $M$, we may regard that there is a homeomorphism $f:\partial_+ C_1\rightarrow\partial_+C_2$ such that $M$ is obtained from $C_1$ and $C_2$ by identifying $\partial_+ C_1$ and $\partial_+C_2$ via $f$.
When we take this viewpoint, we will denote the Heegaard splitting by the expression $C_{1}\cup_{f}C_{2}$.

\medskip
\noindent
{\bf Curve complexes}

Except in sporadic cases, the {\it curve complex} $\mathcal{C}(S)$ is defined as follows: each vertex of $\mathcal{C}(S)$ is the isotopy class of an essential simple closed curve on $S$, and a collection of $k+1$ vertices forms a $k$-simplex of $\mathcal{C}(S)$ if they can be realized by mutually disjoint curves in $S$.
In sporadic cases, we need to modify the definition of the curve complex slightly, as follows.
Note that the surface $S$ is simple unless $S$ is a torus, a torus with one boundary component, or a sphere with 4 boundary components.
When $S$ is a torus or a torus with one boundary component (resp. a sphere with 4 boundary components), a collection of $k+1$ vertices forms a $k$-simplex of $\mathcal{C}(S)$ if they can be realized by curves in $S$ which mutually intersect exactly once (resp. twice).
The {\it arc-and-curve complex} $\mathcal{AC}(S)$ is defined similarly, as follows: each vertex of $\mathcal{AC}(S)$ is the isotopy class of an essential properly embedded arc or an essential simple closed curve on $S$, and a collection of $k+1$ vertices forms a $k$-simplex of $\mathcal{AC}(S)$ if they can be realized by mutually disjoint arcs or simple closed curves in $S$.
Throughout this paper, for a vertex $x\in\mathcal{C}(S)$ we often abuse notations and use $x$ to represent (the isotopy class of) a geometric representative of $x$.
The symbol $\mathcal{C}^0(S)$ (resp. $\mathcal{AC}^0(S)$) denotes the 0-skeleton of $\mathcal{C}(S)$ (resp. $\mathcal{AC}(S)$).

For two vertices $x, y$ of $\mathcal{C}(S)$, we define the {\it distance} $d_{\mathcal{C}(S)}(x, y)$ between $x$ and $y$, which will be denoted by $d_{S}(x, y)$ in brief, as the minimal number of 1-simplexes of a simplicial path in $\mathcal{C}(S)$ joining $x$ and $y$.
For two subsets $X, Y$ of $\mathcal{C}^0(S)$,
we define ${\rm diam}_{S}(X, Y):=$ the diameter of $X\cup Y$.
Similarly, we can define $d_{\mathcal{AC}(S)}(x, y)$ for $x,y\in\mathcal{AC}^0(S)$ and ${\rm diam}_{\mathcal{AC}(S)}(X, Y)$ for $X,Y\subset\mathcal{AC}^0(S)$.

For a sequence $a_0,a_1,\dots,a_n$ of vertices in $\mathcal{C}(S)$ with $a_i\cap a_{i+1}
=\emptyset$ $(i=0,1,\dots,n-1)$, we denote by $[a_0,a_1,\dots,a_n]$ the path in $\mathcal{C}(S)$ with vertices $a_0,a_1,\dots,a_n$ in this order.
We say that a path $[a_0,a_1,\dots,a_n]$ is a {\it geodesic} if $n=d_S(a_0,a_n)$.

Let $V$ be a compression body.
Then the {\it disk complex} $\mathcal{D}(V)$ is the subset of $\mathcal{C}^0(\partial_{+}V)$ consisting of the vertices with representatives bounding disks of $V$. For a genus-$g(\geq 2)$ Heegaard splitting $C_{1}\cup_{P}C_{2}$, the (Hempel) {\it distance} of $C_{1}\cup_{P}C_{2}$ is defined by $d_{P}(\mathcal{D}(C_{1}),\mathcal{D}(C_{2}))=\min\{d_{P}(x, y)\mid x\in\mathcal{D}(C_{1}), y\in\mathcal{D}(C_{2})\}$.

\medskip
\noindent
{\bf Subsurface projection maps}

Let $\mathcal{P}(Y)$ denote the power set of a set $Y$.
Suppose that $X$ is an essential subsurface of $S$.
We call the composition $\pi_0\circ\pi_A$ of maps $\pi_A:\mathcal{C}^{0}(S)\rightarrow \mathcal{P}(\mathcal{AC}^{0}(X))$ and $\pi_0:\mathcal{P}(\mathcal{AC}^{0}(X))\rightarrow\mathcal{P}(\mathcal{C}^{0}(X))$ a {\it subsurface projection} if they satisfy the following: for a vertex $\alpha$, take a representative $\alpha$
so that $|\alpha\cap X|$ is minimal, where $|\cdot|$ is the number of connected components. Then

\begin{itemize}
\item $\pi_{A}(\alpha)$ is the set of all isotopy classes of the components of $\alpha\cap X$,
\item $\pi_0(\{\alpha_1,\dots,\alpha_n\})$ is the union, for all $i=1,\dots,n$, of the set of all isotopy classes of the components of $\partial N(\alpha_{i}\cup\partial X)$ which are essential in $X$, where $N(\alpha_{i}\cup\partial X)$ is a regular neighborhood of $\alpha_i\cup\partial X$ in $X$.
\end{itemize}

We say that $\alpha$ {\it misses} $X$ (resp. $\alpha$ {\it cuts} $X$) if $\alpha\cap X=\emptyset$ (resp. $\alpha\cap X\neq\emptyset$).

\begin{lemma}\label{subsurface distance}
Let $X$ be as above.
Let $[\alpha_{0}, \alpha_{1}, . . . , \alpha_{n}]$ be a path in $\mathcal{C}(S)$
such that every $\alpha_{i}$ cuts $X$.
Then ${\rm diam}_{X}(\pi_{X}(\alpha_{0}), \pi_{X}(\alpha_{n}))\leq 2n$.
\end{lemma}

\begin{proof}
Since $d_S(\alpha_i,\alpha_{i+1})=1$ and every $\alpha_i$ cuts $X$, we have $${\rm diam}_{\mathcal{AC}(X)}(\pi_A(\alpha_i), \pi_A(\alpha_{i+1}))\leq1$$ for every $i=0,1,\dots,n-1$.
This together with \cite[Lemma 2.2]{MM2} implies
$${\rm diam}_{X}(\pi_0(\pi_A(\alpha_i)), \pi_0(\pi_A(\alpha_{i+1})))(={\rm diam}_X(\pi_X(\alpha_i),\pi_X(\alpha_{i+1})))\leq2.$$
Since ${\rm diam}_{X}(\pi_{X}(\alpha_{0}), \pi_{X}(\alpha_{n}))\leq\displaystyle\sum_{i=0}^{n-1}{\rm diam}_{X}(\pi_{X}(\alpha_{i}), \pi_{X}(\alpha_{i+1}))$, this implies
$${\rm diam}_{X}(\pi_{X}(\alpha_{0}), \pi_{X}(\alpha_{n}))\leq 2n.$$
\end{proof}

\begin{remark}\label{rmk-non-sep}
{\rm
Let $X$ be an essential subsurface of $S$. Suppose that $X$ is disconnected, and at least two components of $X$ are non-simple.
Then for any pair of curves $\alpha,\alpha'$ on $S$ we have ${\rm diam}_X(\pi_X(\alpha),\pi_X(\alpha'))\leq 2$.
To be precise, let $X_1$ be one of the non-simple components of $X$, and $X_2$ the union of the others.
Let $a$ and $a'$ be elements of $\pi_X(\alpha)$ and $\pi_X(\alpha')$, respectively.
If both $a$ and $a'$ are contained in $X_i$ for some $i=1,2$, say $X_1$, then we can find a curve on $X_2$ that is disjoint from $a\cup a'$, which implies $d_X(a,a')\leq 2$.
If $a\subset X_1$ and $a'\subset X_2$ (or $a\subset X_2$ and $a'\subset X_1$), we have $d_X(a,a')\leq 1$.
Thus $d_X(a,a')\leq 2$ for any pair of elements $a\in\pi_X(\alpha)$ and $a'\in\pi_X(\alpha')$,
and hence we have ${\rm diam}_X(\pi_X(\alpha),\pi_X(\alpha'))\leq 2$.
}
\end{remark}

\section{Disk complexes}\label{sec-disk-complex}

Let $\mathcal{D}(V)\,(\subset \mathcal{C}^0(\partial_+V))$ be the disk complex of a compression body $V$.
We have a decomposition $\mathcal{D}(V)=\mathcal{D}_{\rm nonsep}(V)\sqcup \mathcal{D}_{\rm sep}(V)$, where $\mathcal{D}_{\rm nonsep}(V)$ (resp. $\mathcal{D}_{\rm sep}(V)$) denotes the subset of $\mathcal{D}(V)$ consisting of the vertices with representatives bounding non-separating (resp. separating) essential disks of $V$.
In this section, we prove the following proposition.

\begin{proposition}\label{prop-disk-complex}
Let $V$ be a compression body obtained by adding a 1-handle to $F \times [0,1]$, where $F$ is a genus-$(g-1)$ closed orientable surface ($g\geq 2$). Then we have the following.
\begin{enumerate}
\item $\mathcal{D}_{\rm nonsep}(V)$ consists of a point, say $c_0$.
\item For each element $c_{\alpha}$ of $\mathcal{D}_{\rm sep}(V)$, there is a 1-simplex in $\mathcal{C}(\partial_+V)$ joining $c_0$ and $c_{\alpha}$.
\end{enumerate}
\end{proposition}

\begin{remark}
{\rm
In fact, we can see that $\mathcal{D}_{\rm sep}(V)$ is a countable, infinite set and that there is no 1-simplex between $c_{\alpha}$ and $c_{\alpha'}$ for each pair $c_{\alpha},c_{\alpha'}\in \mathcal{D}_{\rm sep}(V)$.
}
\end{remark}

In the remaining of this section, $V$ denotes a compression body obtained by adding a 1-handle to $F \times [0,1]$, where $F$ is a genus-$(g-1)$ closed orientable surface ($g\geq 2$).
Then $D$ denotes the essential disk of $V$ corresponding to the co-core of the 1-handle.
Proposition \ref{prop-disk-complex} follows from Lemmas \ref{lem-nonsepa} and \ref{lem-sepa} below.

\begin{lemma}\label{lem-nonsepa}
Any non-separating disk properly embedded in $V$ is ambient isotopic to $D$.
\end{lemma}

\begin{proof}
Let $D'$ be a non-separating disk in $V$.
Assume that $D$ and $D'$ intersect transversely, and $|D\cap D'|$ is minimized up to ambient isotopy class of $D'$.

Suppose $|D\cap D'|=0$, i.e., $D\cap D'=\emptyset$.
Then $D'$ is properly embedded disk in the manifold obtained from $V$ by cutting along $D$, that is, $F\times [0,1]$.
Since any disk properly embedded in $F\times [0,1]$ is boundary parallel and $D'$ is non-separating in $V$, we see that $D\cup D'$ bounds a product region, and hence $D'$ is ambient isotopic to $D$.

Suppose $|D\cap D'|>0$.
By standard innermost disk arguments, we can see that $D\cap D'$ has no loop components.
Note that there are at least two components of $D'\setminus D$ which are outermost in $D'$.
Take a pair of such outermost components, say $\Delta_1$ and $\Delta_2$, which are the next to each other, i.e., there is a subarc $\beta\subset \partial D'$ such that $\beta\cap \Delta_1$ is an endpoint of $\beta$ and $\beta\cap\Delta_2$ is the other endpoint of $\beta$, and $\beta$ does not intersect any other outermost disk of $D'\setminus D$.
Note that we can retrieve $F\times [0,1]$ by cutting $V$ along $D$.
Let $D^{+}, D^{-}$ be the copies of $D$ in $F \times\{1\}$, and let $\overline{\Delta}_{1}$ (resp. $\overline{\Delta}_{2}$) be the closure of the image of $\Delta_{1}$ (resp. $\Delta_{2}$) in $F\times [0,1]$.
Note that $\overline{\Delta}_{1}$ and $\overline{\Delta}_{2}$ are disks properly embedded in $F\times [0,1]$, and $\overline{\Delta}_{i}\cap(D^+\cup D^-)$ consists of an arc properly embedded in $D^+\cup D^-$.
Let $\Gamma_i$ $(i=1,2)$ be the disk in $F\times\{1\}$ such that $\partial\Gamma_i=\partial\overline{\Delta}_{i}$.
Without loss of generality, we may suppose $\overline{\Delta}_{1}\cap(D^+\cup D^-)=\overline{\Delta}_{1}\cap D^+$.
Note that if $D^-$ is not contained in $\Gamma_1$, we can isotope $D'$ in $V$ via the product region between $\overline{\Delta}_{1}$ and $\Gamma_1$ to reduce $|D\cap D'|$, a contradiction.
Hence, $D^-$ is contained in $\Gamma_1$.
Let $\beta$ be the arc in $\partial D'$ as above.
Then $\beta\cap D$ consists of finite number of points, say $p_0,p_1,\dots,p_n$, where $\partial\beta=\{p_0,p_n\}$, $p_0\in\partial\overline{\Delta}_{1}$, $p_n\in\partial\overline{\Delta}_{2}$, and $p_0,p_1,\dots,p_n$ are arrayed on $\beta$ in this order.
Then a small neighborhood of $p_0$ in $\beta$ is contained in a small neighborhood of $D^-$ in $F\times[0,1]$.
If the other endpoint of the subarc $\overline{p_0p_1}$ of $\beta$ is contained in $\partial D^-$, then we see that the subarc $\overline{p_0p_1}$ is an inessential arc in ${\rm Cl}(F\times\{1\}\setminus (D^+\cup D^-))$.
This shows that we can reduce $|D\cap D'|$ by an isotopy on $D'$, a contradiction.
By applying the same argument successively, we see that each subarc $\overline{p_{i-1}p_i}$ $(i=1,2,\dots,n)$ joins $D^+$ and $D^-$, and particularly, a small neighborhood of $p_n$ in $\beta$ is contained in a small neighborhood of $D^+$. This shows that $\overline{\Delta}_2\cap(D^+\cup D^-)=\overline{\Delta}_2\cap D^-$.
Then we see that $D^+$ is not contained in $\Gamma_2$, hence we have a contradiction by using the argument as above.
\end{proof}

Let $D'$ be a separating essential disk properly embedded in $V$.
By an argument similar to that in the proof of Lemma \ref{lem-nonsepa}, we can see that $D'$ is ambient isotopic to a disk disjoint from $D$.
Hence, we have the following lemma.

\begin{lemma}\label{lem-sepa}
Any separating essential disk properly embedded in $V$ can be isotoped to be disjoint from the non-separating disk $D$.
\end{lemma}

\section{A pair of curves with distance exactly $n$}\label{sec-curves}

In this section, for each integer $n\geq 3$, we construct pairs of curves with distance exactly $n$.
Let $S$ be a closed connected orientable surface with genus greater than or equal to $2$.
We first prove Propositions \ref{prop1} and \ref{prop2}.
Then we describe the constructions of paths in $\mathcal{C}(S)$ of length $n$ and show that they are geodesics in $\mathcal{C}(S)$.

\begin{proposition}\label{prop1}
For an integer $n(\geq 4)$,
let $[\alpha_0, \alpha_1,\dots,\alpha_n]$ be a path in $\mathcal{C}(S)$ satisfying the following.
\begin{itemize}
\item[(H1)] $[\alpha_0,\dots,\alpha_{n-2}]$ and $[\alpha_{n-2},\alpha_{n-1},\alpha_n]$ are geodesics in $\mathcal{C}(S)$,
\item[(H2)] ${\rm diam}_{X_{n-2}}(\pi_{X_{n-2}}(\alpha_{n-4}),\pi_{X_{n-2}}(\alpha_{n}))\geq 4n$, where $X_{n-2}={\rm Cl}(S\setminus N(\alpha_{n-2}))$.
\end{itemize}
Then $[\alpha_0, \alpha_1,\dots,\alpha_n]$ is a geodesic in $\mathcal{C}(S)$.
\end{proposition}

\begin{remark}\label{rem-non-sep-1}
{\rm
In Proposition \ref{prop1}, we note that $X_{n-2}$ is connected, i.e., $\alpha_{n-2}$ is non-separating in $S$. This can be shown by using Remark \ref{rmk-non-sep} together with the condition (H2).
}
\end{remark}

\begin{proof}[Proof of Proposition \ref{prop1}]
Let $[\beta_0,\beta_1,\dots,\beta_m]$ be a geodesic in $\mathcal{C}(S)$ such that $\beta_{0}=\alpha_0$, $\beta_{m}=\alpha_n$.
Then note that $m\leq n$.

\begin{claim}\label{claim1}
$\beta_{j}=\alpha_{n-2}$ for some $j\in\{0,1,\dots,m\}$.
\end{claim}

\begin{proof}
Assume on the contrary that $\beta_{j}\neq \alpha_{n-2}$ for any $j$.
Then, by Remark \ref{rem-non-sep-1}, every $\beta_{j}$ cuts $X_{n-2}$.
By Lemma \ref{subsurface distance}, we have ${\rm diam}_{X_{n-2}}(\pi_{X_{n-2}}(\beta_{0}), \pi_{X_{n-2}}(\beta_{m}))\leq2m$.
On the other hand, since $[\alpha_0, \alpha_1,\dots,\alpha_{n-2}]$ is a geodesic, no $\alpha_i$ $(0\leq i\leq n-3)$ is isotopic to $\alpha_{n-2}$.
Hence each $\alpha_i$ $(0\leq i\leq n-3)$ cuts $X_{n-2}$.
By Lemma \ref{subsurface distance}, we have ${\rm diam}_{X_{n-2}}(\pi_{X_{n-2}}(\alpha_{0}), \pi_{X_{n-2}}(\alpha_{n-4}))\leq 2(n-4)<2n.$
These imply
\begin{align*}
  {\rm diam}_{X_{n-2}}(\pi_{X_{n-2}}(\alpha_{n-4}), \pi_{X_{n-2}}(\alpha_{n})) &\leq {\rm diam}_{X_{n-2}}(\pi_{X_{n-2}}(\alpha_{n-4}), \pi_{X_{n-2}}(\alpha_{0}))\\&\hspace{5mm}+{\rm diam}_{X_{n-2}}(\pi_{X_{n-2}}(\alpha_{0}), \pi_{X_{n-2}}(\alpha_{n}))\\
  &< 2n+{\rm diam}_{X_{n-2}}(\pi_{X_{n-2}}(\beta_{0}), \pi_{X_{n-2}}(\beta_{m}))\\
  &\leq 2n+2m\\  &\leq 4n.
\end{align*}
This contradicts the hypothesis (H2).
\end{proof}

By Claim \ref{claim1} and the hypothesis (H1), we have the equalities
\begin{eqnarray*}
  j=d_{S}(\beta_{0}, \beta_{j})&=&d_S(\alpha_0,\alpha_{n-2})=n-2,\\
  m-j=d_{S}(\beta_{j}, \beta_{m})&=&d_{S}(\alpha_{n-2}, \alpha_{n})=2.
\end{eqnarray*}
By combining the above equalities, we have $m=n$.
Recall that $[\beta_0, \beta_1,\dots,\beta_m]$ is a geodesic in $\mathcal{C}(S)$ with $\beta_0=\alpha_0$ and $\beta_m=\alpha_n$.
Hence, $[\alpha_0, \alpha_1,\dots,\alpha_n]$ is a geodesic in $\mathcal{C}(S)$.
\end{proof}

\begin{proposition}\label{prop2}
For an integer $n(\geq 3)$,
let $[\alpha_0, \alpha_1,\dots,\alpha_n]$ be a path in $\mathcal{C}(S)$ satisfying the following.
\begin{itemize}
\item[(H1')] $[\alpha_0,\dots,\alpha_{n-1}]$ and $[\alpha_{n-2},\alpha_{n-1},\alpha_n]$ are geodesics in $\mathcal{C}(S)$,
\item[(H2')] $\alpha_{n-2}\cup\alpha_{n-1}$ is non-separating in $S$, and ${\rm diam}_{S'}(\pi_{S'}(\alpha_{0}),\pi_{S'}(\alpha_{n}))>2n$, where $S'={\rm Cl}(S\setminus N(\alpha_{n-2}\cup\alpha_{n-1}))$.
\end{itemize}
Then $[\alpha_0, \alpha_1,\dots,\alpha_n]$ is a geodesic in $\mathcal{C}(S)$.
\end{proposition}

\begin{proof}
Let $[\beta_0,\beta_1,\dots,\beta_m]$ be a geodesic in $\mathcal{C}(S)$ such that $\beta_{0}=\alpha_{0}$, $\beta_{m}=\alpha_{n}$.
Then note that $m\leq n$.

\begin{claim}
There exists $j\in\{0,1,\dots,m\}$ such that $\beta_{j}=\alpha_{n-2}$ or $\beta_{j}=\alpha_{n-1}$.
\end{claim}

\begin{proof}
Suppose that $\beta_{j}\neq\alpha_{n-2}$ and $\beta_{j}\neq\alpha_{n-1}$ for any $j$.
Since $\alpha_{n-2}\cup\alpha_{n-1}$ is non-separating in $S$, each $\beta_{j}$ cuts $S'$.
Hence, by Lemma \ref{subsurface distance}, we have $${\rm diam}_{S'}(\pi_{S'}(\beta_{0}), \pi_{S'}(\beta_{m}))\leq 2m \leq 2n.$$
On the other hand, by (H2'), ${\rm diam}_{S'}(\pi_{S'}(\beta_{0}), \pi_{S'}(\beta_{m}))>2n$, a contradiction.
\end{proof}

Suppose $\beta_{j}=\alpha_{n-2}$. Then we have the equalities
\begin{eqnarray*}
   j=d_{S}(\beta_{0}, \beta_{j})&=&d_S(\alpha_0,\alpha_{n-2})=n-2,\\
   m-j=d_{S}(\beta_{j}, \beta_{m})&=&d_{S}(\alpha_{n-2}, \alpha_{n})=2.
\end{eqnarray*}
By combining the above equalities, we have $n=m$.
Hence, $[\alpha_0, \alpha_1,\dots,\alpha_n]$ is a geodesic in $\mathcal{C}(S)$.
We can use a similar argument for the case when $\beta_{j}=\alpha_{n-1}$.
This completes the proof of Proposition \ref{prop2}.
\end{proof}

\subsection{A construction of a concrete example: the case when $n$ is even}\label{even}

We first assume that $n$ is an even integer with $n\geq 4$.
Let $\alpha_0$, $\alpha_2$ be essential non-separating simple closed curves on $S$ which intersect transversely in one point, and let $\alpha_1$ be an essential simple closed curve on $S$ which is disjoint from $\alpha_0\cup\alpha_2$.
Let $X_{2}={\rm Cl}(S\setminus N(\alpha_2))$.
Note that $[\alpha_{0}, \alpha_{1}, \alpha_{2}]$ is a geodesic of length two in $\mathcal{C}(S)$.
Choose a homeomorphism $\varphi_2:S\rightarrow S$ such that $\varphi_2(N(\alpha_2))=N(\alpha_2)$ and that ${\rm diam}_{X_{2}}(\pi_{X_{2}}(\alpha_{0}), \pi_{X_{2}}(\varphi_2(\alpha_{0})))\geq 4n$.
This is possible by \cite[Proposition 4.6]{MM1}.
Let $\alpha_{3}=\varphi_2(\alpha_{1})$ and $\alpha_{4} =\varphi_2(\alpha_{0})$.
Note that $[\alpha_{2}, \alpha_{3}, \alpha_{4}]$ is a geodesic of length two in $\mathcal{C}(S)$, and $|\alpha_2\cap\alpha_4|=1$.

\begin{figure}[htbp]
 \begin{center}
 \includegraphics[width=55mm]{curve1.eps}
 \end{center}
 \caption{}
\label{fig:1}
\end{figure}

We repeat this process to construct a path $[\alpha_0,\alpha_1,\dots,\alpha_n]$ inductively as follows.
Suppose we have constructed a path $[\alpha_0,\alpha_1,\dots,\alpha_i]$ with $|\alpha_{i-2}\cap\alpha_i|=1$ for an even integer $i(<n)$.
Let $X_{i}={\rm Cl}(S\setminus N(\alpha_i))$.
Choose a homeomorphism $\varphi_i:S\rightarrow S$ such that $\varphi_i(N(\alpha_i))=N(\alpha_i)$ and that
\begin{equation}\label{eqn-f_i}
{\rm diam}_{X_{i}}(\pi_{X_{i}}(\alpha_{i-2}), \pi_{X_{i}}(\varphi_i(\alpha_{i-2})))\geq 4n.
\end{equation}
Then we let $\alpha_{i+1}= \varphi_i(\alpha_{i-1})$ and $\alpha_{i+2} = \varphi_i(\alpha_{i-2})$.
Note that $[\alpha_{i}, \alpha_{i+1}, \alpha_{i+2}]$ is a geodesic of length two in $\mathcal{C}(S)$, and we have obtained the path $[\alpha_0,\alpha_1,\dots,\alpha_i,\alpha_{i+1},\alpha_{i+2}]$ with $|\alpha_{i}\cap\alpha_{i+2}|=1$.

\begin{assertion}\label{prop-even}
For each $k\in\{2, 4,\dots, n\}$, the path $[\alpha_0,\alpha_1,\dots,\alpha_k]$ in $\mathcal{C}(S)$ is a geodesic.
\end{assertion}

\begin{proof}
We prove the proposition by mathematical induction on $k$.
It is clear that $[\alpha_{0}, \alpha_{1}, \alpha_{2}]$ is a geodesic in $\mathcal{C}(S)$.
Hence, Assertion \ref{prop-even} holds for $k=2$.
Assume that $[\alpha_0,\alpha_1,\dots,\alpha_k]$ is a geodesic in $\mathcal{C}(S)$ for some $k\in\{2,4,\dots,n-2\}$.
We note that $[\alpha_{k}, \alpha_{k+1}, \alpha_{k+2}]$ is a geodesic in $\mathcal{C}(S)$.
Furthermore, by the inequality (\ref{eqn-f_i}), we have ${\rm diam}_{X_{k}}(\pi_{X_{k}}(\alpha_{k-2}), \pi_{X_{k}}(\alpha_{k+2}))\geq 4n\geq 4(k+2)$.
Hence, by Proposition \ref{prop1}, the path $[\alpha_0,\alpha_1,\dots,\alpha_{k+2}]$ is a geodesic in $\mathcal{C}(S)$,
which shows that Assertion \ref{prop-even} holds for $k+2$.
This completes the proof of Assertion \ref{prop-even}.
\end{proof}

\subsection{A construction of a concrete example: the case when $n$ is odd}\label{odd}

Suppose that $n$ is an odd integer with $n\geq 3$.
Let $[\alpha_0,\alpha_1,\dots,\alpha_{n-1}]$ be a geodesic in $\mathcal{C}(S)$ as in the previous subsection.
Here, in addition, we assume that each $\alpha_{i}$ is a non-separating curve.
(It is easy to see that this holds if we take a non-separating curve in $S$ for $\alpha_1$ at the beginning of the construction of the geodesic.)
Note that $\alpha_{n-3}$ intersects $\alpha_{n-1}$ transversely in one point and is disjoint from $\alpha_{n-2}$.
Note also that $\alpha_{n-2}$ is non-separating.
It is easy to see that these imply that $\alpha_{n-1}\cup\alpha_{n-2}$ is non-separating.
Choose a non-separating essential simple closed curve $\gamma$ on $S$ such that $\gamma\cap\alpha_{n-1}=\emptyset$ and $\gamma$ intersects $\alpha_{n-2}$ transversely in one point.
Let $S'={\rm Cl}(S\setminus N(\alpha_{n-2}\cup\alpha_{n-1}))$.
By \cite[Proposition 4.6]{MM1}, there exists a homeomorphism $\varphi:S\rightarrow S$ such that $\varphi(N(\alpha_{n-2}))=N(\alpha_{n-2})$, $\varphi(N(\alpha_{n-1}))=N(\alpha_{n-1})$ and ${\rm diam}_{S'}(\pi_{S'}(\alpha_{0}), \pi_{S'}(\varphi(\gamma)))>2n$.
Let $\alpha_{n}=\varphi(\gamma)$.
Note that $\alpha_{n}\cap\alpha_{n-1}=\emptyset$ and
$\alpha_{n}$ intersects $\alpha_{n-2}$ transversely in one point.
This fact implies that $[\alpha_{n-2},\alpha_{n-1},\alpha_n]$ is a geodesic in $\mathcal{C}(S)$.
On the other hand, $[\alpha_{0},\dots,\alpha_{n-1}]$ is also a geodesic in $\mathcal{C}(S)$.
Hence, by Proposition \ref{prop2} together with the above inequality ${\rm diam}_{S'}(\pi_{S'}(\alpha_{0}), \pi_{S'}(\varphi(\gamma)))>2n$, we see that the path $[\alpha_0,\alpha_1,\dots,\alpha_n]$ is a geodesic in $\mathcal{C}(S)$.

\begin{figure}[htbp]
 \begin{center}
 \includegraphics[width=55mm]{curve2.eps}
 \end{center}
 \caption{}
\label{fig:2}
\end{figure}

\section{Proofs of Theorem \ref{thm-1} and Corollary \ref{thm-2}}

\begin{proof}[Proof of Theorem \ref{thm-1}]
Let $C_1$ and $C_2$ be copies of the compression body obtained by adding a 1-handle to $F\times [0,1]$, where $F$ is a genus-$(g-1)$ closed orientable surface ($g\geq 2$).
Let $\alpha_0$ be the boundary of the non-separating essential disk $D_1$ properly embedded in $C_1$ and $\alpha_2$ a simple closed curve on $\partial_{+} C_1$ which intersects $\alpha_0$ transversely in one point.
Then we construct a geodesic $[\alpha_0,\alpha_1,\dots,\alpha_{n+2}]$ on $\partial_{+} C_1$ as in Section \ref{sec-curves}.
Note that $\alpha_{n+2}$ intersects $\alpha_{n}$ transversely in one point by the construction.
Take any homeomorphism $f:\partial_+C_1\rightarrow \partial_+C_2$ such that $f(\alpha_{n+2})=\partial D_2$,
where $D_2$ is the non-separating essential disk properly embedded in $C_2$.
We identify the boundary components $\partial_+C_1$ and $\partial_+C_2$ by $f$, and let $P=\partial_+C_1=f^{-1}(\partial_+C_2)$.
Then $C_1\cup_P C_2$ is a genus-$g$ Heegaard splitting of a compact orientable 3-manifold.

Let $D_1'$ be a separating essential disk in $C_{1}$ disjoint from $\alpha_{2}$ obtained as follows.
Let $D_1^+$ and $D_1^-$ be the components of ${\rm Cl}(\partial N(D_1)\setminus \partial_+C_1)$, where $N(D_1)$ is a regular neighborhood of $D_1$ in $C_1$.
Take the subarc of $\alpha_2$ lying outside of the product region $N(D_1)$ betwteen $D_1^+$ and $D_1^-$.
Then $D_1'$ is obtained from $D_1^+\cup D_1^-$ by adding a band along the subarc of $\alpha_2$.
Similarly, we can obtain a separating essential disk $D_{2}'$ in $C_{2}$ disjoint from $\alpha_{n}$, by using $D_2$ and $\alpha_n$.
On the other hand, we have $d_{P}(\alpha_{2}, \alpha_{n})=n-2$ since $[\alpha_0,\alpha_1,\dots,\alpha_{n+2}]$ is a geodesic in $\mathcal{C}(P)$.
Hence,
\begin{align*}
   d_{P}(\partial D_{1}', \partial D_{2}') &\leq d_{P}(\partial D_{1}', \alpha_{2})+d_{P}(\alpha_{2}, \alpha_{n})+d_{P}(\alpha_{n}, \partial D_{2}')\\
        &= 1+(n-2)+1\\
        &=n.
\end{align*}

Let $D_1''\subset C_1$ and $D_2''\subset C_2$ be  any essential disks.
By Proposition \ref{prop-disk-complex}, we have $d_P(\partial D_i'',\partial D_i)\leq 1$ for $i=1,2$.
This implies
\begin{align*}
d_P(\partial D_1,\partial D_2)&\leq d_P(\partial D_1,\partial D_1'')+d_P(\partial D_1'',\partial D_2'')+d_P(\partial D_2'',\partial D_2)\\
&\leq 1+d_P(\partial D_1'',\partial D_2'')+1,
\end{align*}
and hence
\begin{align*}
d_P(\partial D_1'',\partial D_2'')&\geq d_{P}(\partial D_{1}, \partial D_{2})-2\\
&=d_{P}(\alpha_{0}, \alpha_{n+2})-2\\
&=(n+2)-2\\&=n.
\end{align*}
Hence $d_P(\partial D_1'',\partial D_2'')\geq n$ for any pair of essential disks $D_1''\subset C_1$ and $D_2''\subset C_2$, which implies $d_{P}(\mathcal{D}(C_{1}), \mathcal{D}(C_{2}))\geq n$.
Since $d_P(\partial D_1',\partial D_2')\leq n$, we have $d_{P}(\mathcal{D}(C_{1}), \mathcal{D}(C_{2}))=n$.
\end{proof}

In the remaining of the paper, we prove Corollary \ref{thm-2} by using the following proposition.
(Throughout this paper, given an embedding $\varphi:X\rightarrow Y$ between compact surfaces $X$ and $Y$, we abuse notations and use $\varphi$ to denote the map $\mathcal{C}^0(X)\rightarrow \mathcal{C}^0(Y)$ or $ \mathcal{P}(\mathcal{C}^0(X))\rightarrow  \mathcal{P}(\mathcal{C}^0(Y))$ induced by $\varphi:X\rightarrow Y$.)

\begin{proposition}\label{prop-appendix}
Let $V_1\cup_f V_2$ be a genus-$g(\geq 2)$ Heegaard splitting, where $V_1$ and $V_2$ are handlebodies.
Let $D_0$ be a separating essential disk in $V_1$, and let $\mathcal{D}_2$ be either $\mathcal{D}(V_2)$ or a finite subset of $\mathcal{D}(V_2)$.
Assume that $d_{\partial V_2}(f(\partial D_0),\mathcal{D}_2)=n\geq 3$.
Then there exists a homeomorphism $g:\partial V_1\rightarrow \partial V_1$
such that $d_{\partial V_2}(fg(\mathcal{D}(V_1)),\mathcal{D}_2)=n$.
\end{proposition}

\begin{proof}
Let $V_1^1$ and $V_1^2$ be the closures of the two components of $V_1\setminus D_0$.
For $i=1,2$, let $F_i$ be the subsurface $\partial V_1^i\cap \partial V_1$ of $\partial V_1$,
and let $\pi_{F_i}=\pi_0\circ\pi_A^i:\mathcal{C}^{0}(\partial V_1)\rightarrow \mathcal{P}(\mathcal{AC}^{0}(F_i))\rightarrow \mathcal{P}(\mathcal{C}^{0}(F_i))$ be the subsurface projection introduced in Section 2.
Let $P_i:F_i\rightarrow F_i\cup D_0$ be the inclusion map.
Since $D_0$ is separating, the image of any essential simple closed curve in $F_i$ by $P_i$ is essential in $F_i\cup D_0$.
This immediately implies:
\begin{claim}\label{claim-Pi}
For any non-empty subset $E$ of $\mathcal{C}^0(F_i)$, we have
\begin{itemize}
\item $P_i(E)$ is non-empty, and
\item ${\rm diam}_{F_i\cup D_0}(P_i(E))\leq{\rm diam}_{F_i}(E)$.
\end{itemize}
\end{claim}

We note that there exists a constant $N$ such that
\begin{equation}\label{eqn-0}
{\rm diam}_{F_i}(\pi_{F_i}f^{-1}(\mathcal{D}_2))\leq N\ (i=1,2).
\end{equation}
In fact, if $\mathcal{D}_2$ is a finite subset of $\mathcal{D}(V_2)$, this is clear.
If $\mathcal{D}_2=\mathcal{D}(V_2)$, then, by \cite[Theorem 1]{Li} together with the assumption $d_{\partial V_2}(f(\partial D_0), \mathcal{D}_2)\geq 3$, we see that ${\rm diam}_{f(F_i)}(\pi_{f(F_i)}(\mathcal{D}_2))\leq 12$, which means ${\rm diam}_{F_i}(\pi_{F_i}f^{-1}(\mathcal{D}_2))\leq 12$.
By Claim \ref{claim-Pi}, the inequality (\ref{eqn-0}) implies
\begin{equation}\label{eqn-0-2}
{\rm diam}_{F_i\cup D_0}(P_i\pi_{F_i}f^{-1}(\mathcal{D}_2))\leq  N\ (i=1,2).
\end{equation}

Let $\mathcal{D}'(V_1^i)$ be the subset of $\mathcal{C}^0(F_i)$ consisting of simple closed curves that bound disks in $V_1^i$ ($i=1,2$).
By the inequality (\ref{eqn-0-2}) and \cite{He} (see also \cite{AS}), we see that there exists a homeomorphism $g:\partial V_1\rightarrow \partial V_1$ such that $g(\partial D_0)=\partial D_0$ and
\begin{equation}\label{eqn-1-1}
d_{F_i\cup D_0}(P_i(\mathcal{D}'(V_1^i)), \hat{g_i}^{-1}(P_i\pi_{F_i}f^{-1}(\mathcal{D}_2)))\geq 2n
\end{equation}
for each $i=1,2$, where $\hat{g_i}:F_i\cup D_0\rightarrow F_i\cup D_0$ is a homeomorphism obtained by extending $g|_{F_i}:F_i\rightarrow F_i$.
(We note that $g|_{F_i}:F_i\rightarrow F_i$ extends to a homeomorphism $\hat{g_i}:F_i\cup D_0\rightarrow F_i\cup D_0$ in a unique way up to isotopy in $D_0$ by Alexander's trick.)
Since $g(\partial D_0)=\partial D_0$, it is easy to see that $\hat{g_i}^{-1}(P_i\pi_{F_i}f^{-1}(\mathcal{D}_2))=P_i(g|_{F_i})^{-1}\pi_{F_i}f^{-1}(\mathcal{D}_2)=P_i\pi_{F_i}g^{-1}f^{-1}(\mathcal{D}_2)=P_i\pi_{F_i}(fg)^{-1}(\mathcal{D}_2)$.
We denote the map
$P_i\pi_{F_i}(fg)^{-1}(=\hat{g_i}^{-1}P_i\pi_{F_i}f^{-1}):\mathcal{C}^{0}(\partial V_2)\rightarrow \mathcal{P}(\mathcal{C}^0(F_i\cup D_0))$ by $\Phi_i$.
Then, by the inequality (\ref{eqn-1-1}), we have
\begin{equation}\label{eqn-1-2}
d_{F_i\cup D_0}(P_i(\mathcal{D}'(V_1^i)), \Phi_i(\mathcal{D}_2))\geq 2n\ (i=1,2).
\end{equation}

Note that $d_{\partial V_2}(fg(\mathcal{D}(V_1)), \mathcal{D}_2)\leq n$ since $f(\partial D_0)=fg(\partial D_0)\in fg(\mathcal{D}(V_1))$ and $d_{\partial V_2}(f(\partial D_0),\mathcal{D}_2)=n$ by the assumption.
To prove $d_{\partial V_2}(fg(\mathcal{D}(V_1)), \mathcal{D}_2)=n$,
assume on the contrary that $d_{\partial V_2}(fg(\mathcal{D}(V_1)), \mathcal{D}_2)<n$, or equivalently, $d_{\partial V_1}(\mathcal{D}(V_1),$ $(fg)^{-1}(\mathcal{D}_2))<n$.
Then there exist $a\in \mathcal{D}(V_1)$ and $b\in \mathcal{D}_2$ such that
\begin{equation}\label{eqn-a-b}
d_{\partial V_1}(a,(fg)^{-1}(b))=m<n.
\end{equation}
Let $[\gamma_0,\gamma_1,\dots,\gamma_m]$ be a geodesic in $\mathcal{C}(\partial V_1)$ from $a$ to $(fg)^{-1}(b)$.
\begin{claim}\label{claim-gamma-cuts-fi}
Every $\gamma_j$ $(j=1,2,\dots,m)$ cuts both $F_1$ and $F_2$.
\end{claim}
\begin{proof}
Assume that $\gamma_j$ does not cut $F_i$ for some $j\in\{1,2,\dots,m\}$ and some $i\in\{1,2\}$.
Then $\gamma_j$ is disjoint from $\partial D_0(=\partial F_1=\partial F_2)$, and hence we have
\begin{eqnarray*}
n&=&d_{\partial V_1}(\partial D_0,(fg)^{-1}(\mathcal{D}_2))\\
&\leq& d_{\partial V_1}(\partial D_0,\gamma_j)+d_{\partial V_1}(\gamma_j,(fg)^{-1}(\mathcal{D}_2))\\
&\leq& d_{\partial V_1}(\partial D_0,\gamma_j)+d_{\partial V_1}(\gamma_j,\gamma_m)\\
&\leq& 1+(m-j)\\
&<& 1+n-j,
\end{eqnarray*}
a contradiction.
\end{proof}

Let $D_a$ be a disk in $V_1$ bounded by $a$.
We may assume that $|D_a\cap D_0|$ is minimal.
By using innermost disk arguments, we see that $D_a\cap D_0$ has no loop components.

\vspace{2mm}
{\it Case 1}. $|D_a\cap D_0|\neq 0$.
\vspace{2mm}

Let $\Delta$ be a component of $D_a\setminus D_0$ that is outermost in $D_a$.
Then $\Delta\subset V_1^i$ for some $i=1,2$.
Without loss of generality, we may assume that $\Delta\subset V_1^1$, which implies $a(=\gamma_0)$ cuts $F_1$.
This, together with Claim \ref{claim-gamma-cuts-fi}, shows that every $\gamma_j$ $(j=0,1,\dots,m)$ in the geodesic $[\gamma_0,\gamma_1,\dots,\gamma_m]$ from $a$ to $(fg)^{-1}(b)$ cuts $F_1$.
Hence, by Lemma \ref{subsurface distance}, we have
\begin{equation}\label{eqn-2-1}
{\rm diam}_{F_1}(\pi_{F_1}(a), \pi_{F_1}(fg)^{-1}(b))\leq 2m<2n
\end{equation}
which implies, by Claim \ref{claim-Pi},
\begin{equation}\label{eqn-2}
{\rm diam}_{F_1\cup D_0}(P_1\pi_{F_1}(a), \Phi_1(b))<2n
\end{equation}
Note that $\partial\Delta\cap F_1$ is an element of the image of $a$ by $\pi_A^1:\mathcal{C}^0(\partial V_1)\rightarrow \mathcal{P}(\mathcal{AC}^0(F_1))$.
Further, by the minimality of $|D_a\cap D_0|$, the disk $\Delta$ is essential in $V_1^1$.
Let $D_0^1$ and $D_0^2$ be the two components of $D_0\setminus \Delta$,
and let $\Delta'$ be one of the disks properly embedded in $V_1^1$ which are parallel to $D_0^1\cup \Delta$ or $D_0^2\cup \Delta$.
Then we have $\partial\Delta'\in P_1(\mathcal{D}'(V_1^1))$, and also $\partial\Delta'\in P_1\pi_0(\partial\Delta\cap F_1)\subset P_1\pi_0\pi_A^1(a)=P_1\pi_{F_1}(a)$.
These, together with the inequality (\ref{eqn-2}), imply
\begin{eqnarray*}
d_{F_1\cup D_0}(P_1(\mathcal{D}'(V_1^1)), \Phi_1(\mathcal{D}_2))&\leq& d_{F_1\cup D_0}(\partial\Delta', \Phi_1(b))\\
&\leq&{\rm diam}_{F_1\cup D_0}(P_1\pi_{F_1}(a), \Phi_1(b))\\
&<&2n,
\end{eqnarray*}
which contradicts the inequality (\ref{eqn-1-2}).

\vspace{2mm}
{\it Case 2}. $|D_a\cap D_0|= 0$.
\vspace{2mm}

In this case, the arguments in Case 1 work with regarding $D_a=\Delta'$ to have a contradiction.

The above contradictions give $d_{\partial V_2}(fg(\mathcal{D}(V_1)),\mathcal{D}_2)=n$.
\end{proof}

\begin{remark}
{\rm
If we pose the assumption that the distance $d(V_1\cup_f V_2)$ of the genus-$g$ Heegaard splitting $V_1\cup_f V_2$ is greater than or equal to $2$ in Proposition \ref{prop-appendix}, then the statement of the proposition can be strengthened as in the following form:
}

Let $D_0$ be a separating essential disk in $V_1$, and let $\mathcal{D}_2$ be any subset of $\mathcal{D}(V_2)$.
If $d_{\partial V_2}(f(\partial D_0),\mathcal{D}_2)=n$,
then there exists a homeomorphism $g:\partial V_1\rightarrow \partial V_1$
such that $d_{\partial V_2}(fg(\mathcal{D}(V_1)),\mathcal{D}_2)=n$.\\
{\rm
In fact, the statement can be proved basically by using the arguments of the proof of Proposition \ref{prop-appendix}.
The difference is the proof of inequality (\ref{eqn-0}).
We should replace it with:

Note that $f(\partial D_0)(=f(\partial F_1)=f(\partial F_2))$ intersects with every essential loop in $\mathcal{D}(V_2)$, since $d_{\partial V_2}(f(\partial D_0),\mathcal{D}(V_2))\geq d(V_1\cup_f V_2)\geq 2$.
By \cite[Theorem 1]{Li}, either
\begin{equation}\label{eqn-00}
{\rm diam}_{F_i}(\pi_{F_i}f^{-1}(\mathcal{D}_2))\leq {\rm diam}_{F_i}(\pi_{F_i}f^{-1}(\mathcal{D}(V_2)))\leq 12
\end{equation}
or $V_2$ is a $[0,1]$-bundle over $f(F_1)$.
In the latter case, it is easy to see that $g$ must be even and that the union of $V_2$ and $N(D_0)$ is homeomorphic to a $[0,1]$-bundle over a closed surface, say $S$, of genus $g/2$.
Note that the exterior of the union of $V_2$ and $N(D_0)$ is ${\rm Cl}(V_1\setminus N(D_0))$ and consists of two handlebodies of genus $g/2$.
Thus, $S$ is a Heegaard surface of genus $g/2$, and $\partial V_2(=f(\partial V_1))$ is a stabilization of $S$.
This implies $d(V_1\cup_f V_2)=0$, a contradiction.
Hence, we have the inequality (\ref{eqn-00}).
}
\end{remark}

\begin{proof}[Proof of Corollary \ref{thm-2}]
We first note that the proof of the corollary for the case when $n=2$ is exceptional,
and we give it in Appendix of this paper, and
in this proof we show the corollary for the case $n \geq 3$.
Let $C_1\cup_P C_2=C_1\cup_f C_2$ be a genus-$g$ Heegaard splitting with distance $n(\geq 3)$ obtained in Theorem \ref{thm-1}.
By the proof of Theorem \ref{thm-1}, there are separating essential disks $D_1$ and $D_2$ in $C_1$ and $C_2$, respectively, such that $d_{\partial_+C_2}(f(\partial D_1),\partial D_2)=n$.
Let $H_i$ $(i=1,2)$ be a handlebody of genus $(g-1)$.
Take and fix any homeomorphism $h_i:\partial H_i\rightarrow \partial_-C_i$, and put $V_i:=C_i\cup_{h_i}H_i$(, hence, $V_i$ is a handlebody of genus $g$).
Then $V_1\cup_f V_2$ is a genus-$g$ Heegaard splitting.

By Proposition \ref{prop-appendix}, there exists a homeomorphism $g_1:\partial V_1\rightarrow\partial V_1$ such that $d_{\partial V_2}(fg_1(\mathcal{D}(V_1)), \partial D_2)=n$.
By applying Proposition \ref{prop-appendix} again to $V_2\cup_{(fg_1)^{-1}}V_1$, we see that there exists a homeomorphism $g_2:\partial V_2\rightarrow\partial V_2$ such that $$d_{\partial V_1}((fg_1)^{-1}g_2(\mathcal{D}(V_2)), \mathcal{D}(V_1))=n.$$
That is, the distance of the Heegaard splitting $V_1\cup_{g_2^{-1}fg_1}V_2$ is exactly $n$.
\end{proof}