2.1 HL-extensions

We fix some notation to be used in the rest of the paper. Throughout this paper let $\mathcal {L}$ be a finite relational language. Let $C,D$ be $\mathcal {L}$ -structures. We say that D is an extension of C if C is a substructure of D. Interchangeably, we use the same terminology when D contains an isomorphic copy of C.

A homomorphism from C to D is a map $\pi : C\to D$ such that for every n-ary relation $R\in \mathcal {L}$ and every $a_1,\dots , a_n\in C$ ,

$$\begin{align*}R^C(a_1,\dots, a_n)\Rightarrow R^D(\pi(a_1),\dots,\pi(a_n)).\end{align*}$$

An isomorphism from C to D is a bijection $\pi : C\to D$ such that for every n-ary relation $R\in \mathcal {L}$ and every $a_1,\dots ,a_n\in C$ ,

$$\begin{align*}R^C(a_1,\dots,a_n) \iff R^D(\pi(a_1),\dots,\pi(a_n)).\end{align*}$$

An isomorphism from C to C is also called an automorphism of C. The set of all automorphisms of C is denoted as $\mbox {Aut}(C)$ . Under composition of maps, $\mbox {Aut}(C)$ becomes a group.

A partial isomorphism of C is an isomorphism between two finite substructures of C. The set of all partial isomorphisms of C is denoted as $\mathcal {P}(C)$ . Although $\mathcal {P}(C)$ is not necessarily a group, it is a groupoid and for each $p\in \mathcal {P}(C)$ we can speak of the inverse map $p^{-1}$ , which is still a partial isomorphism.

If D is an extension of C, then every partial isomorphism of C is also a partial isomorphism of D. In symbols, we have $\mathcal {P}(C)\subseteq \mathcal {P}(D)$ if C is a substructure of D.

If $p, q\in \mathcal {P}(C)$ , we say that q extends p, and write $p\subseteq q$ , if

$$\begin{align*}\{ (a, p(a))\,:\, a\in\mbox{dom}(p)\}\subseteq \{ (a, q(a))\,:\, a\in\mbox{dom}(q)\}.\end{align*}$$

We let $1_C$ denote the identity automorphism on C, i.e., $1_C(a){{\kern-2.5pt}={\kern-2.5pt}}a$ for all $a{{\kern-2.5pt}\in{\kern-2.5pt}}C$ . Let $\mathcal {P}_C$ denote the set of all $p{{\kern-2pt}\in{\kern-2pt}} \mathcal {P}(C)$ such that $p{{\kern-2pt}\not \subseteq{\kern-2pt}} 1_C$ . We refer to elements of $\mathcal {P}_C$ as nonidentity partial isomorphisms of C. Note that if $p{{\kern-2pt}\in{\kern-2pt}} \mathcal {P}_C$ then $p^{-1}{{\kern-2pt}\in{\kern-2pt}} \mathcal {P}_C$ and $p^{-1}{{\kern-2pt}\neq{\kern-2pt}} p$ .

The main concept we study in this paper is that of an HL-extension.

Note that if $(D, \phi )$ is an HL-extension of C then we can always modify $\phi $ so that for all $p\in \mathcal {P}_C$ , $\phi (p^{-1})=\phi (p)^{-1}$ . We will tacitly assume this property for all the HL-extensions we consider.

Note that an equivalent restatement of Herwig–Lascar theorem (Theorem 1.3) is that every finite $\mathcal {T}$ -free $\mathcal {L}$ -structure has a finite $\mathcal {T}$ -free HL-extension.

We will need the following notion of homomorphism between HL-extensions.

We also define the notion of minimality for an HL-extension as follows.

2.2 A canonical HL-extension

In this subsection we describe a canonical construction of an HL-extension that is essentially due to Herwig–Lascar [Reference Herwig and Lascar3]. In the rest of the paper let $\mathcal {T}$ be a fixed finite set of finite $\mathcal {L}$ -structures.

First, note that for every finite $\mathcal {L}$ -structure C there is a unique partition of C into substructures $\{C_i \ : \ i=1,\dots ,n\}$ such that each $C_i$ is a maximal subset of C satisfying that for every $a,b\in C_i$ , the map that sends a to b (that is, the map $\{(a,b)\}$ ) is a partial isomorphism of C. In other words, we partition C into maximal subsets whose elements satisfy the same unary predicates. We call this partition with a specific point from each set a natural factorization of C. That is, a natural factorization of C is of the form $\{(C_i,a_i): i=1,\dots , n\}$ , where each $a_i\in C_i$ .

Let C be a finite $\mathcal {T}$ -free $\mathcal {L}$ -structure. Let $\{(C_i,a_i) \ : \ i=1,\dots ,n\}$ be a natural factorization of C. For every $1\leq i\leq n$ we define

$$ \begin{align*} H_i=\{g\in \mathbb{F}(\mathcal{P}_C) \ : \ g(a_i)=a_i\}, \end{align*} $$

where $\mathbb {F}(\mathcal {P}_C)$ is the free group with the generating set $\mathcal {P}_C$ (with the convention that the inverse of $p\in \mathcal {P}_C$ in $\mathbb {F}(\mathcal {P}_C)$ coincides with $p^{-1}$ ). By $g(a_i)=a_i$ we mean that if $g=p_1\cdots p_m$ with $p_1,\dots , p_m\in \mathcal {P}_C$ , then $p_1(\cdots ( p_m(a_i))\cdots )$ is defined and

$$\begin{align*}p_1(\cdots (p_m(a_i))\cdots)=a_i.\end{align*}$$

Each $H_i$ is a subgroup of $\mathbb {F}(\mathcal {P}_C)$ .

Let $\Gamma $ be the $\mathcal {L}$ -structure with domain

$$\begin{align*}\mathbb{F}(\mathcal{P}_C)/H_1\sqcup \cdots \sqcup \mathbb{F}(\mathcal{P}_C)/H_n\end{align*}$$

and such that for every m-ary relation symbol $R\in \mathcal {L}$ , we have $R^\Gamma (g_1H_{i_1},\dots ,g_mH_{i_m})$ iff there are $p_1,\dots ,p_m\in \mathcal {P}_C$ and $g\in \mathbb {F}(\mathcal {P}_C)$ such that $p_j(a_{i_j})$ is defined for each $j=1,\dots , m$ , $(g_1H_{i_1},\dots ,g_mH_{i_m})=(gp_1H_{i_1},\dots ,gp_mH_{i_m})$ , and $R^C(p_1(a_{i_1}),\dots ,p_m(a_{i_m}))$ .

Note that C can be viewed as a substructure of $\Gamma $ . In fact, consider the map $\pi :C\rightarrow \Gamma $ defined as

$$ \begin{align*}\pi(a)=\left\{\begin{array}{ll} H_i, & \mbox{ if } a=a_i, \\ pH_i, & \mbox{ if } a\neq a_i \mbox{ and } p\in \mathcal{P}_C \mbox{ satisfies } p(a_i)=a, \end{array}\right. \end{align*}$$

for $a\in C_i$ . It is easy to see that $\pi $ is well-defined and is indeed an isomorphic embedding from C into $\Gamma $ .

Given any $\gamma \in \mathbb {F}(\mathcal {P}_C)$ , the map $\Phi _\gamma $ defined by $\Phi _\gamma (gH_i)=\gamma gH_i$ is an automorphism of $\Gamma $ . Thus, $(\Gamma , \Phi )$ is an HL-extension of C with $\Phi : \mathcal {P}_C\to \mbox {Aut}(\Gamma )$ defined as $\Phi (p)=\Phi _p$ . Note that by definition, $(\Gamma ,\Phi )$ is a minimal HL-extension of C.

Assume C has a $\mathcal {T}$ -free HL-extension $(D,\phi )$ . Consider the map $\psi :\Gamma \rightarrow D$ defined by $\psi (gH_i)=\phi (g)(a_i)$ , where $\phi (g)=\phi (p_1)\cdots \phi (p_m)$ if $g=p_1\dots p_m$ . Then $\psi $ is a homomorphism. It follows that $\Gamma $ is also $\mathcal {T}$ -free.

2.3 Finite HL-extensions

Let C be a finite $\mathcal {T}$ -free $\mathcal {L}$ -structure as before. We give a description of all finite $\mathcal {T}$ -free, minimal HL-extensions of C. For this we first describe a finite $\mathcal {T}$ -free, minimal HL-extension by replacing each group $H_i$ in the above canonical $\Gamma $ with a larger group of the form $N_iH_i$ , where $N_i$ is a normal subgroup of $\mathbb {F}(\mathcal {P}_C)$ of finite index.

Let $N_1,\dots , N_n\unlhd \mathbb {F}(\mathcal {P}_C)$ be normal subgroups of finite index. We define

$$\begin{align*}\Gamma_{\vec{N}}=\mathbb{F}(\mathcal{P}_C)/N_1H_1\sqcup \cdots \sqcup \mathbb{F}(\mathcal{P}_C)/N_nH_n.\end{align*}$$

The structure on $\Gamma _{\vec {N}}$ is defined analogously to the structure on the canonical HL-extension $\Gamma $ . More precisely, to define the structure on $\Gamma _{\vec {N}}$ , let $R\in \mathcal {L}$ be an m-ary relation symbol. Then $R^{\Gamma _{\vec {N}}}(g_1N_{i_1}H_{i_1},\dots ,g_mN_{i_m}H_{i_m})$ iff there are $p_1,\dots ,p_m\in \mathcal {P}_C$ and $g\in \mathbb {F}(\mathcal {P}_C)$ such that $p_j(a_{i_j})$ is defined for each $j=1,\dots , m$ ,

$$ \begin{align*} (g_1N_{i_1}H_{i_1},\dots,g_mN_{i_m}H_{i_m})=(gp_1N_{i_1}H_{i_1},\dots,gp_mN_{i_m}H_{i_m}), \end{align*} $$

and $R^C(p_1(a_{i_1}),\dots ,p_m(a_{i_m}))$ .

Consider the map $\pi _{\vec {N}}:C\rightarrow \Gamma _{\vec {N}}$ defined by

$$ \begin{align*}\pi_{\vec{N}}(a)=\left\{\begin{array}{ll} N_iH_i, & \mbox{ if } a=a_i, \\ pN_iH_i, & \mbox{ if } a\neq a_i \mbox{ and } p\in \mathcal{P}_C \mbox{ satisfies } p(a_i)=a, \end{array}\right.\end{align*}$$

for $a\in C_i$ . Then $\pi _{\vec {N}}$ is well-defined. Under suitable assumptions (that will be discussed in Theorem 2.4), $\pi _{\vec {N}}$ becomes an isomorphic embedding. In this case $\pi _{\vec {N}}(C)$ is an isomorphic copy of C as a substructure of $\Gamma _{\vec {N}}$ .

We define $\Phi _{\vec {N}}:\mathcal {P}_C\rightarrow \mbox {Aut}(\Gamma _{\vec {N}})$ by letting

$$\begin{align*}\Phi_{\vec{N}}(p)(gN_iH_i)=p gN_iH_i.\end{align*}$$

Assuming the above map $\pi _{\vec {N}}$ is an isomorphic embedding, and noting that there is a canonical surjective homomorphism from $\Gamma $ to $\Gamma _{\vec {N}}$ , it follows from the minimality of $(\Gamma , \Phi )$ that $(\Gamma _{\vec {N}}, \Phi _{\vec {N}})$ is also a minimal HL-extension of C.

We are now ready to describe any finite $\mathcal {T}$ -free, minimal HL-extension of C as a homomorphic image of some $(\Gamma _{\vec {N}}, \Phi _{\vec {N}})$ , which is itself a finite $\mathcal {T}$ -free, minimal HL-extension of C.

Proof. For each $i=1,\dots , n$ , let $D_i=\{\phi (g)(a_i): g\in \mathbb {F}(\mathcal {P}_C)\}$ . We define

$$ \begin{align*} N_i=\{g\in \mathbb{F}(\mathcal{P}_C) : \phi(g)(a)=a \text{ for every } a\in D_i \}. \end{align*} $$

Then $N_i\unlhd \mathbb {F}(\mathcal {P}_C)$ . Since D is finite, each $N_i$ is of finite index.

Let $\Gamma _{\vec {N}}$ and $\pi _{\vec {N}}: C\to \Gamma _{\vec {N}}$ be defined as above. We claim that $\pi _{\vec {N}}$ is an isomorphic embedding. To see this, let $a, a'\in C_i$ with $a\neq a'$ . Let $p, p'\in \mathcal {P}_C$ with $p(a_i)=a$ and $p'(a_i)=a'$ . We show that $p^{\prime {-1}}pH_i\cap N_i=\emptyset $ , which implies $pN_iH_i\neq p'N_iH_i$ . For this, let $g\in H_i$ . Since

$$\begin{align*}\phi(p^{\prime{-1}}pg)(a_i)=\phi(p^{\prime{-1}})\phi(p)\phi(g)(a_i)=\phi(p')^{-1}p(a_i)\neq a_i,\end{align*}$$

we have that $p^{\prime {-1}}pH_i\cap N_i=\emptyset $ . This shows that $\pi _{\vec {N}}$ is injective. It is easy to see that $\pi _{\vec {N}}$ is an isomorphism between the structures C and $\pi _{\vec {N}}(C)$ .

Now we define $\psi _{\vec {N}}:\Gamma _{\vec {N}}\rightarrow D$ by $\psi _{\vec {N}}(gN_iH_i)=\phi (g)(a_i)$ . Note that $\psi _{\vec {N}}$ is well-defined since if $g_1^{-1}g_2\in N_iH_i$ then by definition of $N_i,H_i$ we have $\phi (g_1^{-1}g_2)(a_i)=a_i$ and therefore $\phi (g_1)(a_i)=\phi (g_2)(a_i)$ . $\psi _{\vec {N}}$ is onto since D is minimal. It is also easy to verify that $\psi _{\vec {N}}$ is a homomorphism. It follows that $\Gamma _{\vec {N}}$ is $\mathcal {T}$ -free, and thus $(\Gamma _{\vec {N}}, \Phi _{\vec {N}})$ is a finite $\mathcal {T}$ -free, minimal HL-extension of C.

Finally, it is routine to check that for every $p\in \mathcal {P}_C$ , $\phi (p)\circ \psi _{\vec {N}}=\psi _{\vec {N}}\circ \Phi _{\vec {N}}(p)$ . Thus $\psi _{\vec {N}}$ is a homomorphism from $(\Gamma _{\vec {N}}, \Phi _{\vec {N}})$ onto $(D, \phi )$ . ⊣

3.1 The HL-property

First, we need the following definitions.

Definition 3.1 Herwig–Lascar [3]. Let G be a group and let $H_1,\dots ,H_n\leq G$ . A left system of equations on $H_1,\dots ,H_n$ is a finite set of equations with variables $x_1,\dots ,x_m$ and constants $g_1,\dots ,g_l$ such that each equation is of the form

$$ \begin{align*} x_iH_j=g_kH_j \text{ or } x_iH_j=x_rg_kH_j, \end{align*} $$

where $1\leq i,r\leq m$ , $1\leq k\leq l$ and $1\leq j\leq n$ .

By results of [Reference Herwig and Lascar3], Section $3$ , the Herwig–Lascar theorem (Theorem 1.3) implies the HL-property for all free groups with finitely many generators. Our results below will imply that they are actually equivalent.

Recall that we say a group G has the RZ-property if for any finitely generated subgroups $H_1, \dots , H_n\leq G$ , $H_1\cdots H_n$ is closed in the profinite topology of G. Equivalently, a group G has the RZ-property iff for any finitely generated $H_1,\dots ,H_n\leq G$ and $g\notin H_1\cdots H_n$ there exist a normal subgroup $N\unlhd G$ of finite index, such that $gN\cap H_1\cdots H_n=\emptyset $ . Ribes–Zalesskii [Reference Ribes and Zalesskii6] proved the RZ-property for free groups with finitely many generators. As noted in [Reference Herwig and Lascar3], the HL-property is a strengthening of the RZ-property, and therefore the Herwig–Lascar theorem is a strengthening of the Ribes–Zalesskii result.

Rosendal in [Reference Rosendal7] considered the RZ-property and showed that it is equivalent to a statement about extensions of partial isometries for finite metric spaces which he called finite approximability. Earlier, Coulbois [Reference Coulbois1] gave a characterization of the RZ-property in terms of extensions of partial isomorphisms of finite structures, and used it to show that the RZ-property is closed under taking finite free products. Below we give a characterization of the HL-property also in terms of extensions of partial isomorphisms of finite structures. Our characterization is analogous to Rosendal’s notion of finite approximability.

To state the theorem, we need the following notions. Let G be a group acting on sets X and Y and let $A\subseteq X$ and $F\subseteq G$ be arbitrary subsets. An F-map from A to Y is a function $\pi : A\to Y$ such that for all $g\in F$ and $x\in A$ , if $g(x)\in A$ , then $\pi (g(x))=g(\pi (x))$ . Moreover, if X and Y are $\mathcal {L}$ -structures, then $\pi $ is called an F-embedding if $\pi $ is an injective F-map that is an isomorphism between A and $\pi (A)$ .

An $\mathcal {L}$ -structure C is called a Gaifman clique if for every $a, b\in C$ there is a relation symbol $R\in \mathcal {L}$ with arity $m\geq 2$ and $c_1,\dots , c_m\in C$ with $a, b\in \{c_1, \dots , c_m\}$ and $R^C(c_1,\dots , c_m)$ .

The next two subsections are devoted to a proof of Theorem 3.3. We will show (i) $\Rightarrow $ (ii) $\Rightarrow $ (iii) $\Rightarrow $ (i). Since (ii) $\Rightarrow $ (iii) is obvious, we focus on showing (i) $\Rightarrow $ (ii) and (iii) $\Rightarrow $ (i).

3.2 Proof of Theorem 3.3 (i) $\Rightarrow $ (ii)

We assume G has the HL-property. Let $C\subseteq D$ be $\mathcal {T}$ -free $\mathcal {L}$ -structures, where C is finite. For $1\leq i\leq n$ , let $D_i=S_i^D$ and $C_i=S_i^C$ . Then $\{D_i: 1\leq i\leq n\}$ is a partition of D and $\{C_i:1\leq i\leq n\}$ is a partition of C. Without loss of generality, assume $D_i\neq \emptyset $ for every $1\leq i\leq n$ . Then, by extending C, we may assume that $C_i\neq \emptyset $ for every $1\leq i\leq n$ . Let $\{(C_i,a_i): 1\leq i\leq n\}$ be a natural factorization of C. Since G acts transitively on each $D_i$ , we have $D_i=G(a_i)$ . By minimizing the structure on D, we may also assume that for any m-ary relation symbol $R\in \mathcal {L}$ and for any $d_1,\dots , d_m\in D$ , we have $R^D(d_1,\dots ,d_m)$ iff there are $c_1,\dots ,c_m\in C$ and $g\in G$ such that $R^C(c_1,\dots ,c_m)$ and $(d_1,\dots ,d_m)=(g(c_1),\dots ,g(c_m))$ .

Define $\rho : G\to \mathcal {P}(C)$ by letting, for any $g\in G$ and $c\in C$ , $\rho (g)(c)=g(c)$ , if $g(c)\in C$ ; $\rho (g)(c)$ is undefined otherwise. Since G acts by isomorphisms on D, if $c\in C_i$ for some $1\leq i\leq n$ and $\rho (g)(c)$ is defined, then $\rho (g)(c)\in C_i$ . Since C is finite, the set $\rho (G)\cap \mathcal {P}_C=\{\rho (g)\in \mathcal {P}_C: g\in G\}$ is finite.

Let $F\subseteq G$ be finite. Since the action of G on D is faithful, by extending C with finitely many points, we may assume that $\rho (F\setminus \{1_C\})\subseteq \mathcal {P}_C$ . Pick a finite $K\subseteq G$ such that $F\subseteq K$ , $K^{-1}=K$ and $\rho (K\setminus \{1_C\})=\rho (G\setminus \{1_C\})\cap \mathcal {P}_C$ . Define

$$ \begin{align*} H_i=\{p_1\cdots p_l \ : \ p_1,\dots, p_l\in K \mbox{ and }\rho(p_1)(\cdots \rho(p_l)(a_i)\cdots)=a_i\}. \end{align*} $$

Since C and K are finite, $H_i$ is finitely generated. To see this, consider an edge-labeled directed graph on C defined as follows: there is an edge from $c_1$ to $c_2$ labeled by p if $p\in K$ is such that $p(c_1)=c_2$ . Note that this graph can have multiple edges and loops. The generators of $H_i$ are precisely those $p_1\cdots p_l$ that give a minimal cycle from $a_i$ back to $a_i$ .

Let $\Gamma $ be the $\mathcal {L}$ -structure with domain $G/H_1\sqcup \cdots \sqcup G/H_n$ such that for $i=1,\dots , n$ , $S_i^\Gamma =G/H_i$ , and for any m-ary relation symbol $R\in \mathcal {L}$ and for any $g_1,\dots , g_m\in G$ , $R^\Gamma (g_1H_{i_1},\dots ,g_mH_{i_m})$ iff there are $p_1,\dots , p_m\in K$ and $g\in G$ such that $p_j(a_{i_j})\in C_{i_j}$ for each $j=1,\dots , m$ , $R^C(p_1(a_{i_1}),\cdots , p_m(a_{i_m}))$ , and

$$ \begin{align*} (g_1H_{i_1},\dots,g_mH_{i_m})=(gp_1H_{i_1},\dots,gp_mH_{i_m}). \end{align*} $$

G acts on $\Gamma $ by left multiplication. Consider the map $\pi : C\to \Gamma $ defined as

$$ \begin{align*}\pi(c)=\left\{\begin{array}{ll} H_i, & \mbox{ if } c=a_i, \\ pH_i, & \mbox{ if } c\in C_i, c\neq a_i, \mbox{ and } p\in K \mbox{ with } p(a_i)=c. \end{array}\right.\end{align*}$$

Since G acts transitively on each $D_i$ , $\pi $ is well-defined. We claim that $\pi $ is an isomorphic embedding of C into $\Gamma $ . In fact, $\pi $ is injective because of the following fact:

1. (C1) For every $p,q\in K$ and $1\leq i\leq n$ , if $p(a_i), q(a_i)\in C_i$ and $p(a_i)\neq q(a_i)$ , then $p^{-1}q\notin H_i$ .

Furthermore, $\pi $ is an isomorphism between C and $\pi (C)$ because of the following fact:

1. (C2) For any $p_1,\dots ,p_m,q_1,\dots ,q_m\in K$ such that for all $j=1,\dots , m$ ,

   $$\begin{align*}p_j(a_{i_j}), q_j(a_{i_j})\in C_{i_j}\end{align*}$$
   for some $1\leq i_1,\dots , i_m\leq n$ , if
   $$\begin{align*}R^C(p_1(a_{i_1}),\dots p_m(a_{i_m})) \mbox{ and } \neg R^C(q_1(a_{i_1}),\dots q_m(a_{i_m})),\end{align*}$$
   then there does not exist $g\in G$ such that
   $$\begin{align*}(p_1H_{i_1},\dots,p_mH_{i_m})=(gq_1H_{i_1},\dots,gq_mH_{i_m}).\end{align*}$$

(C2) is true since otherwise in D we would have

$$\begin{align*}R^D(p_1(a_{i_1}),\dots, p_m(a_{i_m})) \mbox{ and } \neg R^D(q_1(a_{i_1}),\dots, q_m(a_{i_m}))\end{align*}$$

and yet $(p_1(a_{i_1}),\dots , p_m(a_{i_m}))=(gp_1(a_{i_1}),\dots , gp_m(a_{i_m}))$ , violating that g is an isomorphism of the structure D.

Consider the map $\psi :\Gamma \to D$ defined by $\psi (gH_i)=g(a_i)$ . Then $\psi $ is a homomorphism from the structure $\Gamma $ onto the structure D. Since D is $\mathcal {T}$ -free, so is $\Gamma $ . Thus, we also have the following

1. (C3) For every structure $T\in \mathcal {T}$ there is no homomorphism from T into $\Gamma $ .

Next we demonstrate that conditions (C1)–(C3) can all be equivalently expressed as certain left systems of equations on $H_1,\dots , H_n$ not having solutions. To do this, we first establish some general lemmas.

Lemma 3.4. Let $\mathcal {G}$ be a group and $\mathcal {H}\leq \mathcal {G}$ . For any $\gamma , \eta \in \mathcal {G}$ , $\gamma ^{-1}\eta \notin \mathcal {H}$ iff the following left system with variable x does not have a solution

(3.1) $$ \begin{align} \begin{array}{l} x\mathcal{H}=\gamma\mathcal{H} \\ x\mathcal{H}=\eta\mathcal{H.} \end{array} \end{align} $$

Proof. Again we prove the contrapositives. First, assume that there is $g\in \mathcal {G}$ such that $(\gamma _1\mathcal {H}_1, \dots , \gamma _m\mathcal {H}_m)=(g\eta _1\mathcal {H}_1, \dots , g\eta _m\mathcal {H}_m)$ . Thus we have m equations

$$ \begin{align*}\begin{array}{l} \gamma_1 \mathcal{H}_1 = g\eta_1\mathcal{H}_1 \\ \dots\dots \\ \gamma_m\mathcal{H}_m=g\eta_m\mathcal{H}_m. \end{array} \end{align*}$$

Each equation above, which is of the form $\gamma _i\mathcal {H}_i=g\eta _i\mathcal {H}_i$ , is equivalent to there existing $x_i$ such that

$$ \begin{align*}\begin{array}{l} x_i\mathcal{H}_i=\gamma_i\mathcal{H}_i \\ x_i\mathcal{H}=g\eta_i\mathcal{H}_i,\end{array} \end{align*}$$

similar to the proof of Lemma 3.4. Thus the totality of these m equations is equivalent to there existing solutions for the $2m$ equations in (3.2). Conversely, if (3.2) has a solution, then each pair of equations involving $x_i$ give rise to an equation of the form $\gamma _i\mathcal {H}_i=x\eta _i\mathcal {H}_i$ . The solution for x witnesses the existence of the desired element $g\in \mathcal {G}$ in clause (i). ⊣

We are now ready to argue that conditions (C1)–(C3) can be equivalently expressed as certain left systems of equations on $H_1,\dots , H_n\leq G$ not having solutions. For (C1), simply apply Lemma 3.4 to the appropriate $H_i, p, q$ . Then $p^{-1}q\notin H_i$ is equivalent to the following system not having a solution

(3.3) $$ \begin{align} \begin{array}{l} xH_i=pH_i \\ xH_i=qH_i. \end{array} \end{align} $$

Since K is finite, there are only finitely many such systems. To summarize, there are finitely many left systems on $H_1,\dots , H_n$ such that (C1) holds iff each of the left systems does not have a solution.

For (C2), apply Lemma 3.5. The left system correspondent to the condition is

(3.4) $$ \begin{align} \begin{array}{l} x_1H_{i_1}=p_1H_{i_1} \\ x_1H_{i_1}=xq_1H_{i_1} \\ \cdots\cdots \\ x_mH_{i_m}=p_mH_{i_m} \\ x_mH_{i_m}=xq_mH_{i_m}.\end{array} \end{align} $$

Again, since K is finite, there are only finitely many such systems, and (C2) holds iff each of these left systems does not have a solution.

For (C3), we consider any $T\in \mathcal {T}$ . Enumerate the elements of T as $t_1, \dots , t_l$ . Introduce variables $y_1,\dots , y_l$ correspondent to $t_1,\dots , t_l$ . Suppose first there is a homomorphism of T into $\Gamma $ . Then there are $g_1, \dots , g_l\in G$ and $1\leq i_1, \dots , i_l\leq n$ such that, for any m-ary relation symbol $R\in \mathcal {L}$ , whenever $R^T(t_{j_1}, \dots , t_{j_m})$ where $1\leq j_1, \dots , j_m\leq l$ , we have

$$\begin{align*}R^\Gamma(g_{j_1}H_{i_{j_1}}, \dots, g_{j_m}H_{i_{j_m}}).\end{align*}$$

Note that $R^\Gamma (g_{j_1}H_{i_{j_1}}, \dots , g_{j_m}H_{i_{j_m}})$ iff there are $p_1, \dots , p_m\in K$ and $g\in G$ such that $p_k(a_{i_{j_k}})\in C_{i_{j_k}}$ for all $k=1,\dots , m$ ,

$$\begin{align*}R^C(p_1(a_{i_{j_1}}), \dots, p_m(a_{i_{j_m}})),\end{align*}$$

and

$$\begin{align*}(g_{j_1}H_{i_{j_1}}, \dots, g_{j_m}H_{i_{j_m}})=(gp_1H_{i_{j_1}}, \dots gp_mH_{i_{j_m}}).\end{align*}$$

Applying Lemma 3.5, the above statement is equivalent to the following: there are $1\,{\leq}\, i_1,\dots , i_l\leq n$ such that for any m-ary relation symbol $R\in \mathcal {L}$ , whenever $R^T(t_{j_1},\dots , t_{j_m})$ with $1\leq j_1,\dots , j_m\leq l$ , there are $p_1,\dots , p_m\in K$ such that $p_k(a_{i_{j_k}})\in C_{i_{j_k}}$ for all $k\,{=}\,1,\dots , m$ ,

$$\begin{align*}R^C(p_1(a_{i_{j_1}}), \dots, p_m(a_{i_{j_m}})),\end{align*}$$

and the following left system with variables $ y_1,\dots , y_l, x, z_1,\dots , z_m$ has a solution

(3.5) $$ \begin{align}\begin{array}{l} z_1H_{i_{j_1}}=y_{j_1}H_{i_{j_1}}\\ z_1H_{i_{j_1}}=xp_1H_{j_1} \\ \dots\dots \\ z_mH_{i_{j_m}}=y_{j_m}H_{i_{j_m}}\\ z_mH_{i_{j_m}}=xp_mH_{i_{j_m}.} \end{array} \end{align} $$

Here the variables $x, z_1,\dots , z_m$ and the left system (3.5) are introduced for each instance of $j_1, \dots , j_m$ and $p_1,\dots , p_m\in K$ that satisfy the conditions $R^T(t_{j_1},\dots , t_{j_m})$ , $p_k(a_{i_{j_k}})\in C_{i_{j_k}}$ for all $k=1,\dots , m$ , and $ R^C(p_1(a_{i_{j_1}}), \dots , p_m(a_{i_{j_m}}))$ . We call these $j_1,\dots , j_m$ and $p_1,\dots , p_m\in K$ a set of witnesses. There are only finitely many possible sets of witnesses. Accumulating all sets of witnesses together, and introducing a left system (3.5) with distinct variables $x, z_1,\dots , z_m$ for each set of witnesses, we obtain a single finite left system that is the union of all these left systems for each set of witnesses. Now this resulting left system has a solution. Conversely, if this system has a solution, then the solutions for $y_1, \dots , y_l$ will witness a homomorphism of T into $\Gamma $ . Thus the existence of a homomorphism of T into $\Gamma $ is equivalent to a single left system having a solution.

Finally, since $\mathcal {T}$ is finite, we again have finitely many left systems such that (C3) holds iff each of the finitely many left systems on $H_1, \dots , H_n$ does not have a solution.

In summary, all conditions (C1)–(C3) can be represented as finitely many left systems on $H_1,\dots , H_n$ not having a solution. Since G has the HL-property, we can find $N_1,\dots ,N_n\unlhd G$ such that each of the left systems described by (C1)–(C3) does not have a solution with respect to $(N_1H_1,\dots ,N_nH_n)$ . Indeed, for each of the left system $\Sigma $ there are such $N_1^\Sigma , \dots , N_n^\Sigma $ for the system. For each $i=1, \dots , n$ , let $N_i$ be the intersection of all $N_i^\Sigma $ . We thus get $N_1, \dots , N_n$ which are still of finite index in G so that all of the left systems on $N_1H_1, \dots , N_nH_n$ still do not have a solution. This implies that the conditions (C1)–(C3) continue to hold with $H_i$ replaced by $N_iH_i$ .

We now define $D'$ to be the finite $\mathcal {L}$ -structure with domain $G/N_1H_1\sqcup \cdots \sqcup G/N_nH_n$ such that $S_i^{D'}=G/N_iH_i$ for all $i=1,\dots , n$ , and for any m-ary relation symbol $R\in \mathcal {L}$ , we have $R^{D'}(g_1N_{i_1}H_{i_1},\dots ,g_mN_{i_m}H_{i_m})$ iff there are $p_1,\dots ,p_m\in K$ and $g\in G$ such that $p_j(a_{i_j})\in C_{i_j}$ for all $j=1,\dots , m$ , $R^C(p_1(a_{i_1}),\cdots ,p_m(a_{i_m}))$ , and

$$ \begin{align*} (g_1N_{i_1}H_{i_1},\dots,g_mN_{i_m}H_{i_m})=(gp_1N_{i_1}H_{i_1},\dots,gp_mN_{i_m}H_{i_m}). \end{align*} $$

Consider the map $\pi ': C\to D'$ defined as

$$ \begin{align*}\pi'(c)=\left\{\begin{array}{ll} N_iH_i, & \mbox{ if } c=a_i, \\ pN_iH_i, & \mbox{ if } c\in C_i, c\neq a_i, \mbox{ and } p\in K \mbox{ with } p(a_i)=c. \end{array}\right.\end{align*}$$

Then conditions (C1) and (C2) with $H_i$ replaced by $N_iH_i$ guarantee that $\pi '$ is an isomorphic embedding. Condition (C3) with $H_i$ replaced by $N_iH_i$ implies that $D'$ is $\mathcal {T}$ -free. The action of G on $D'$ is by left multiplication, and each of $g\in G$ gives an isomorphism of the structure $D'$ . Finally, we check that $\pi '$ is a K-map, and therefore an F-map. Let $p\in K$ and $c\in C_i$ , and assume $p(c)\in C_i$ . Suppose $q\in K$ with $q(a_i)=c$ and $r\in K$ with $r(a_i)=p(c)$ . Then $\pi '(p(c))=rN_iH_i=pqN_iH_i=p(\pi '(c))$ , where $r^{-1}pq\in H_i$ by the definition of $H_i$ . This completes the proof of (i) $\Rightarrow $ (ii).

3.3 Proof of Theorem 3.3 (iii) $\Rightarrow $ (i)

We assume (iii) holds and show that G has the HL-property. Suppose $H_1, \dots , H_n\leq G$ are finitely generated subgroups. Consider a left system $\Sigma $ with l many equations on $H_1,\dots ,H_n$ that does not have a solution. Let A be the finite set of $g, g^{-1}\in G$ for all constants g appearing in $\Sigma $ . Let $H_0=\{1_G\}\leq G$ be the trivial subgroup. Consider a relational structure D defined as follows:

1. a) the domain of D is $G/H_0\sqcup G/H_1\sqcup \cdots \sqcup G/H_n$ ;

2. b) there are $n+1$ many unary relation symbols $S_0, \dots , S_n$ such that $S_i^D=G/H_i$ for $i=0,\dots , n$ ;

3. c) there is a binary relation symbol U such that $U^D=D\times D$ ;

4. d) for each $g\in A$ , there is a binary relation $B_g$ such that $B_g^D=\{(hH_0, hgH_0): h\in G\}$ ;

5. e) for each tuple $t=(i_1,\dots , i_m)$ , where $2\leq m\leq 2l+n+1$ and $0\leq i_j\leq n$ for each $j=1, \dots , m$ , there is an m-ary relation symbol $R_t$ such that

   $$\begin{align*}R_t^D(g_1H_{i_1},\dots,g_mH_{i_m}) \mbox{ iff } g_1H_{i_1}\cap\dots\cap g_mH_{i_m}\neq \emptyset.\end{align*}$$

Let $\mathcal {L}$ be the language of D. We claim that the left system $\Sigma $ has a solution iff a specific finite $\mathcal {L}$ -structure T has a homomorphic image inside D.

First we turn $\Sigma $ into an equivalent left system $\Sigma ^*$ with the same number of equations. To do this, collect all equations in $\Sigma $ of the form $xH_i=gH_i$ where x is a variable and $g\in A$ . Introduce a new variable y and replace every equation in the above collection by the equation $xH_i=ygH_i$ . Denote the resulting left system as $\Sigma ^*$ . We claim that $\Sigma $ has a solution iff $\Sigma ^*$ has a solution. First suppose $\Sigma $ has a solution. Then the solution for $\Sigma $ together with $y=1_G$ is a solution for $\Sigma ^*$ . Conversely, suppose $\Sigma ^*$ has a solution in which $y=h$ in particular. Then this solution with every term left-multiplied by $h^{-1}$ is still a solution for $\Sigma ^*$ , which, with y dropped, is a solution for $\Sigma $ . Thus, without loss of generality, we may assume that all equations in $\Sigma $ are of the form $xH_i=ygH_i$ where $x, y$ are variables and $g\in A$ .

Next we note that every equation of the form $xH_i=ygH_i$ can be replaced with two equations of the form $xH_i=x_{\text {new}}H_i$ and $x_{\text {new}}H_0=ygH_0$ , where the last equation can be rearranged as $yH_0=x_{\text {new}}g^{-1}H_0$ . By repeating this process, we may obtain an equivalent left system $\Sigma '$ with $\leq 2l$ many equations such that for any variable x in $\Sigma $ , the equations in $\Sigma '$ involving x are all of the form $xH_i=yH_i$ or $xH_0=ygH_0$ for some variable y and constant $g\in A$ . Note that for the new variable $x_{\text {new}}$ above, we get two equations $x_{\text {new}}H_i=xH_i$ and $x_{\text {new}}H_0=ygH_0$ by moving the cosets for $x_{\text {new}}$ to the left hand side of the equations. Now for each variable x in $\Sigma '$ , consider the left system $\Sigma _x$ consisting only of the equations in $\Sigma '$ that involve x. From the above discussion we know that $\Sigma _x$ can be listed as:

$$ \begin{align*}\begin{array}{l} xH_{i_1}=\epsilon_1 H_{i_1} \\ \cdots\cdots \\ xH_{i_k}= \epsilon_k H_{i_k} \end{array} \end{align*}$$

for $k\leq 2l$ and each $\epsilon _j$ is either a variable y or of the form $yg$ (in which case $i_j=0$ ) for a variable y and a constant $g\in A$ . Note that $\Sigma _x$ has a solution iff the following expression has a solution:

(3.6) $$ \begin{align} xH_0\cap xH_1\cap \cdots \cap xH_n\cap \epsilon_1H_{i_1}\cap \cdots \cap \epsilon_kH_{i_k}\neq\emptyset. \end{align} $$

In fact, if $\Sigma _x$ has a solution $x, y, \dots $ , then x is in the intersection of (3.6). Conversely, if (3.6) holds for some $x, y,\dots $ then they become a solution of $\Sigma _x$ . Thus each $\Sigma _x$ corresponds to a formal relation

(3.7) $$ \begin{align} R_t(xH_0, xH_1, \dots, xH_n, \epsilon_1H_{i_1}, \dots, \epsilon_k H_{i_k}) \end{align} $$

for a suitable t of length $k+n+1\leq 2l+n+1$ .

We now describe a finite $\mathcal {L}$ -structure T. The domain of T is the set of all formal cosets $xH_i$ and $xgH_0$ , where x is a variable in $\Sigma '$ , $g\in A$ , and $i=0,\dots , n$ . The definition of $S_i^T$ is obvious. Also $U^T=T\times T$ . For each $g\in A$ , let $B_g^T=\{(xH_0, xgH_0): x \mbox { is a variable in } \Sigma '\}$ . The above formal relation (3.7) becomes now the definition of $R_t^T$ . For other relation symbols $R_t$ , $R_t^T$ is empty. Note that T is a Gaifman clique.

It is now clear that $\Sigma '$ has a solution iff there is a homomorphism from the structure T into the structure D. Since $\Sigma $ does not have a solution, neither does $\Sigma '$ and it follows that D is T-free.

G acts faithfully on D by left multiplication, and it is clear that the left multiplication by any $g\in G$ preserves the structure of D. It is also clear that G acts transitively on $S_i^D=G/H_i$ for each $i=0, \dots , n$ .

Let C be a finite substructure of D whose domain consists of all $H_i$ and $gH_i$ for $g\in A$ and $i=0,\dots , n$ . Define $\rho : G\to \mathcal {P}(C)$ by letting $\rho (g)(c)=g(c)$ if $c, g(c)\in C$ ; otherwise $\rho (g)(c)$ is undefined. Since C is finite, the set $\rho (G)$ is finite. Let $F\subseteq G$ be a finite subset so that $A\subseteq F$ , $\rho (F)=\rho (G)$ and for each $i=1,\dots , n$ , F contains a finite set of generators for $H_i$ . Since the action of G on $S_i^D$ is transitive for each $i=0, \dots , n$ , the partial action of $\rho (F)$ on $S_i^C$ is also transitive. Apply (iii) to get a finite T-free extension $D'$ of C on which G acts by isomorphisms, and an F-embedding $\pi $ from C into $D'$ . Note that $H_i$ is an element of C and $\pi (H_i)$ is an element of $D'$ , and we may assume that $D'=G(\pi (H_0))\sqcup \cdots \sqcup G(\pi (H_n))$ . Let

$$ \begin{align*} N_i=\{g\in G : g(a)=a \text{ for every } a\in G(\pi(H_i))\}. \end{align*} $$

Since $D'$ is finite, $N_i$ is a normal subgroup of finite index. Now let $\Sigma _{\vec {N}}$ be obtained from $\Sigma $ by replacing $H_1,\dots , H_n$ respectively by $N_1H_1,\dots , N_nH_n$ . We claim that $\Sigma _{\vec {N}}$ does not have a solution, which shows that G has the HL-property.

Towards a contradiction, assume the left system $\Sigma _{\vec {N}}$ on $N_1H_1,\dots ,N_nH_n$ has a solution. Similarly to the above, we can obtain an equivalent left system $\Sigma _{\vec {N}}^*$ such that each equation in $\Sigma _{\vec {N}}^*$ is of the form $xN_iH_i=ygN_iH_i$ . Let $M_0=N_0\cap N_1\cap \cdots \cap N_n$ . Then $M_0$ is still a normal subgroup of finite index, and obviously $M_0\leq N_i$ for all $i=0, \dots , n$ . Now each equation of the form $xN_iH_i=ygN_iH_i$ in $\Sigma _{\vec {N}}^*$ can be equivalently replaced by $xN_iH_i=x_{\text {new}}N_iH_i$ and $x_{\text {new}}M_0H_0=ygM_0H_0$ . Also, the last equation can be reformulated as $yM_0H_0=x_{\text {new}}g^{-1}M_0H_0$ because of the normality of $M_0$ . Thus we obtain an equivalent left system $\Sigma _{\vec {N}}'$ in a similar way as before, whose solution describes a homomorphic image of T in a structure $\Gamma =G/M_0H_0\sqcup G/N_1H_1\sqcup \cdots \sqcup G/N_nH_n$ . The exact definition of the structure $\Gamma $ is similar to the definition of D above. For notational convenience we define $M_i=N_i$ for $i=1, \dots , n$ .

Since $D'$ is a T-free structure, it is enough to show that there is a homomorphism from $\Gamma $ into $D'$ . Consider the map $\psi :\Gamma \rightarrow D'$ defined by $\psi (gM_iH_i)= g(\pi (H_i))$ . Then $\psi $ is the desired homomorphism. Note that $\psi $ is well-defined since if $g_1M_iH_i=g_2M_iH_i$ then $g_2=g_1nh$ for some $n\in M_i\leq N_i$ and $h\in H_i$ ; using the definition of $N_i$ and $H_i$ and the fact that $\pi $ is an F-embedding, we have $g_2(\pi (H_i))=g_1nh(\pi (H_i))=g_1(\pi (H_i))$ . More precisely, we can write $h=f_1\cdots f_r$ with $f_1,\dots , f_r\in F$ as F contains a finite set of generators for $H_i$ ; since $\pi $ is an F-embedding, we have $h(\pi (H_i))=f_1\cdots f_r(\pi (H_i))=\pi (f_1\cdots f_r(H_i))=\pi (H_i)$ . Also, by definition of $N_i$ , for $n\in N_i$ we have $n(\pi (H_i))=\pi (H_i)$ .

It remains to verify that $\psi $ preserves structure. For this let $t=(i_1,\dots , i_m)$ with $m\leq 2l+n+1$ and assume $R_t^\Gamma (g_1M_{i_1}H_{i_1},\dots ,g_mM_{i_m}H_{i_m})$ , that is,

$$\begin{align*}g_1M_{i_1}H_{i_1}\cap \cdots\cap g_mM_{i_m}H_{i_m}\neq\emptyset.\end{align*}$$

Then there are $n_{i_j}\in M_{i_j}\leq N_{i_j}$ and $h_{i_j}\in H_{i_j}$ for $j=1,\dots , m$ such that

$$\begin{align*}g_1n_{i_1}h_{i_1}=\cdots=g_mn_{i_m}h_{i_m}=g.\end{align*}$$

The action of g on $D'$ sends the tuple $(\pi (H_{i_1}), \dots ,\pi (H_{i_m}))$ to

$$ \begin{align*} (g_1(\pi(H_{i_1})),\dots,g_m(\pi(H_{i_m})))=(\psi(g_1M_{i_1}H_{i_1}),\dots,\psi(g_mM_{i_m}H_{i_m})). \end{align*} $$

Note that $R_t^C(H_{i_1},\dots ,H_{i_m})$ and therefore $R_t^{D'}(\pi (H_{i_1}),\dots ,\pi (H_{i_m}))$ . Now since g acts by an isomorphism on $D'$ , we have $R_t^{D'}(g_1(\pi (H_1)),\dots ,g_m(\pi (H_m)))$ .

Finally, consider $(hM_0H_0, hgM_0H_0)\in B_g^\Gamma $ for some $g\in A$ and $h\in G$ . We need to show that $(h(\pi (H_0)), hg(\pi (H_0)))\in B_g^{D'}$ . By the definition of C, we have $H_0, gH_0\in C$ and $B_g^C(H_0, gH_0)$ . Since $g\in A\subseteq F$ and $\pi $ is an F-embedding, we have $\pi (gH_0)=g(\pi (H_0))$ and $B_g^{D'}(\pi (H_0), g(\pi (H_0)))$ . Now h acts by an isomorphism on $D'$ , and so $B_g^{D'}(h\pi (H_0), hg(\pi (H_0)))$ as desired.

This finishes the proof of Theorem 3.3.

3.4 Free products of groups with the HL-property

As a corollary to Theorem 3.3, we show below that the HL-property is closed under taking finite free products. This is analogous to the theorem of Coulbois [Reference Coulbois1] which states that the RZ-property is closed under taking finite free products. In the proof of the corollary we use the coherence result of Sinora–Solecki [Reference Solecki9], which is also established in [Reference Hubička, Konečnỳ and Nešetřil5] with a different proof. We summarize in the following proposition the exact fact we will need in our proof.

Proposition 3.6. Let C be a finite $\mathcal {T}$ -free $\mathcal {L}$ -structure. Then, C has a finite $\mathcal {T}$ -free HL-extension $(D,\phi )$ such that for every substructure $E\subseteq C$ , $\phi _E :\text {Aut}(E)\to \text {Aut}(D)$ defined as

$$\begin{align*}\phi_E(p)=\left\{\begin{array}{ll}\phi(p), &\mbox{if } p\in \text{Aut}(E)\cap \mathcal{P}_C, \\ 1_D, & \mbox{ if } p=1_E, \end{array}\right.\end{align*}$$

is a group isomorphic embedding.

In the proof of the corollary we will also need a property of Gaifman cliques proved by Siniora–Solecki in [Reference Solecki9]. To explain the property, first recall some definitions.

Siniora–Solecki proved in Lemma 4.5 of [Reference Solecki9] that a class $\mathcal {C}$ of $\mathcal {L}$ -structures has the free amalgamation property iff there is a set $\mathcal {T}$ of $\mathcal {L}$ -structures each of which is a Gaifman clique such that $\mathcal {C}$ is exactly the collection of all $\mathcal {L}$ -structures C for which there does not exist any isomorphic embedding from any $T\in \mathcal {T}$ into C. Note that in our context (where $\mathcal {T}$ is a finite set of finite $\mathcal {L}$ -structures) the statement implies that the class of finite $\mathcal {T}$ -free $\mathcal {L}$ -structures has the free amalgamation property iff all $T\in \mathcal {T}$ are Gaifman cliques. This is because, if $\mathcal {T}$ is a set of Gaifman cliques and if we let $\mathcal {T}'$ to be the set of all homomorphic images of structures in $\mathcal {T}$ , then $\mathcal {T}'$ is still a finite set of Gaifman cliques, and the collection of $\mathcal {T}$ -free structures is exactly the collection of structures into which no $T\in \mathcal {T}'$ isomorphically embed.

Proof. Suppose $G_1, G_2$ have the HL-property. To show that $G_1*G_2$ has the HL-property, we use the equivalence between clauses (i) and (iii) of Theorem 3.3. Specifically, we show the following:

• Let $\mathcal {L}$ be a finite relational language with unary relation symbols $S_1,\dots , S_n$ . Let $\mathcal {T}$ be a finite set of finite $\mathcal {L}$ -structures such that every $T\in \mathcal {T}$ is a Gaifman clique. Let D be a $\mathcal {T}$ -free $\mathcal {L}$ -structure such that $\{S_1^D, \dots , S_n^D\}$ is a partition of the domain of D. Let C be a finite substructure of D. Let F be a finite subset of $G_1*G_2$ . Suppose that $G_1*G_2$ acts faithfully by isomorphisms on D and that $G_1*G_2$ acts transitively on each $S_i^D$ for $i=1,\dots , n$ . Then there exists a finite $\mathcal {T}$ -free $\mathcal {L}$ -structure $D'$ on which $G_1*G_2$ acts by isomorphisms, and an F-embedding from C into $D'$ .

In the following we construct the desired structure $D'$ .

Let $F_1\subseteq G_1$ and $F_2\subseteq G_2$ be finite subsets such that $F\subseteq F_1*F_2$ . Let $C'\subseteq D$ be a finite structure extending C such that for every $f=f_1\,f_2\cdots f_l\in F$ where $f_i\in F_1\cup F_2$ for every $i=1,2,\dots ,l$ , and every $a\in C$ where $f (a)\in C$ , we have $f_j\cdots f_l (a)\in C'$ for every $1\leq j\leq l$ . Since $G_1$ and $G_2$ have the HL-property, we can find finite $\mathcal {T}$ -free $\mathcal {L}$ -structures $D_1'$ and $D_2'$ such that for $k=1,2$ :

• (1) $G_k$ acts by isomorphisms on $D_k'$ , and

• (2) there exists an $F_k$ -embedding $\pi _k$ from $C'$ to $D_k'$ .

Let $D_0$ be the free amalgamation of $D_1'$ and $D_2'$ over $\pi _1(C')\cong \pi _2(C')$ , that is, the underlying set of $D_0$ is $(D_1'\setminus \pi _1(C'))\sqcup C'\sqcup (D_2'\setminus \pi _2(C'))$ and for every relation R in the language $R^{D_0}=R^{D_1'}\cup R^{D_2'}$ . Since $\mathcal {T}$ consists of only Gaifman cliques, the collection of all $\mathcal {T}$ -free $\mathcal {L}$ -structures has the free amalgamation property. Thus $D_0$ is $\mathcal {T}$ -free.

By Proposition 3.6, there exists a finite $\mathcal {T}$ -free HL-extension $(D',\phi )$ of $D_0$ such that for every finite substructure $E\subseteq D_0$ , $\phi $ induces a group isomorphic embedding from $\text {Aut}(E)$ to $\text {Aut}(D)$ . In particular, this holds for $E=D_1',D_2'$ . Therefore, $\phi $ induces an action of $G_k$ on $D'$ by $g(a)=\phi (g)(a)$ for $k=1,2$ . By considering the free product of these two actions, we get an action of $G_1*G_2$ on $D'$ by isomorphisms. It remains to show that there exists an F-embedding $\pi $ from C to $D'$ . Let $\pi :C'\rightarrow D'$ denote the inclusion map. We claim $\pi \upharpoonright C$ is as desired. Let $f=f_1\,f_2\cdots f_l\in F$ where $f_i\in F_1\cup F_2$ for every $i=1,2,\dots ,l,$ and $a\in C$ be such that $f(a)\in C$ . Note that for $k=1, 2$ , since $\pi $ is an $F_k$ -embedding from $C'$ to $D_k'$ , we have that $\pi $ is also an $F_k$ -embedding from $C'$ to $D'$ . Therefore,

$$ \begin{align*} \pi(f(a))=\pi(f_1\cdots f_k (a))&=f_1(\pi(f_2\cdots f_l (a)))\\&=\cdots=f_1\cdots f_l (\pi(a))=f(\pi(a)).\\[-37pt] \end{align*} $$

 ⊣