$m_{1}=r_{1}\tau(v_{1})\cdots r_{i-1}\tau(v_{i-1})r_{i}$. By closure under
multiplication, we get that
$(m_{1}t_{1}ft^{\prime}_{1},s_{1}t_{1}ft^{\prime}_{1})$ is a good pair. We get
$(s_{1}t_{1}ft^{\prime}_{1})^{\omega+1}=(s_{1}t_{1}ft^{\prime}_{1})^{\omega}m_{1}t_{1}ft^{\prime}_{1}(s_{1}t_{1}ft^{\prime}_{1})^{\omega}$
from Lemma 42. Since $q_{1}=q_{1}s_{1}t_{1}ft^{\prime}_{1}$, multiplying by
$q_{1}$ on the left yields the equality
$q_{1}=q_{1}m_{1}t_{1}ft^{\prime}_{1}(s_{1}t_{1}ft^{\prime}_{1})^{\omega}$. We
let $m^{\prime}_{1}=t_{1}ft^{\prime}_{1}(s_{1}t_{1}ft^{\prime}_{1})^{\omega}$.
Thus, $q_{1}=q_{1}m_{1}m^{\prime}_{1}$. For all $j$, we have
$[\tau(v_{j})]_{N}=g_{j}=[e_{j}]_{N}$ and $(e_{j},e_{j}\tau(v_{j})e_{j})$ is a
good pair by Lemma 44. Since $r_{j}e_{j}=r_{j}$ and $e_{j}r_{j+1}=r_{j+1}$ for
all $j$, closure under multiplication yields that
$(\widehat{r_{1}}m^{\prime}_{1},m_{1}m^{\prime}_{1})$ is a good pair as well.
We use Lemma 42 to get
$(m_{1}m^{\prime}_{1})^{\omega+1}=(m_{1}m^{\prime}_{1})^{\omega}\widehat{r_{1}}m^{\prime}_{1}(m_{1}m^{\prime}_{1})^{\omega}$.
Since $q_{1}=q_{1}m_{1}m^{\prime}_{1}$, multiplying by $q_{1}$ on the left
yields
$q_{1}=q_{1}\widehat{r_{1}}m^{\prime}_{1}(m_{1}p^{\prime}_{1})^{\omega}$. If
we define $r^{\prime}_{1}=m^{\prime}_{1}(m_{1}m^{\prime}_{1})^{\omega}$, we
get indeed
$[r^{\prime}_{1}]_{N}=[t_{1}ft^{\prime}_{1}(\widehat{r_{1}}t_{1}ft^{\prime}_{1})^{\omega}]_{N}$.
∎

###  5.7. Second step: full cover of $\eta^{-1}(d)$

This step is the same whether $J$ is maximal or not. Indeed, in both cases, we
have a $(q_{1},q_{2})$-safe $\textup{BPol}(\mathscr{C})$-cover
$\mathbf{K}_{\smash{\widebar{S}}}$ of $\tau^{-1}(\smash{\widebar{S}})$. We
let,

$K^{\prime}=\bigcup_{K\in\mathbf{K}_{\smash{\widebar{S}}}}K,\quad
K_{\bot}=\eta^{-1}(d)\setminus
K^{\prime}\quad\text{and}\quad\mathbf{K}=\\{K_{\bot}\\}\cup\mathbf{K}_{\smash{\widebar{S}}}.$

Since $\eta$ is a $\mathscr{C}$-morphism and $K\in\textup{BPol}(\mathscr{C})$
for all $K\in\mathbf{K}_{\smash{\widebar{S}}}$, we have
$K_{\bot}\in\textup{BPol}(\mathscr{C})$. Therefore, $\mathbf{K}$ is a
$\textup{BPol}(\mathscr{C})$-cover of $\eta^{-1}(d)$ by definition. We prove
that it is $(q_{1},q_{2})$-safe. Let $K\in\mathbf{K}$, $w,w^{\prime}\in K$,
$q=\tau(w)$ and $r=\tau(w^{\prime})$. We show that $q_{1}qq_{2}=q_{1}rq_{2}$.
If $K\in\mathbf{K}_{\smash{\widebar{S}}}$, this is because
$\mathbf{K}_{\smash{\widebar{S}}}$ is $(q_{1},q_{2})$-safe.

Assume now that $K=K_{\bot}$. By definition of $K_{\bot}$, we know that
$w,w^{\prime}\in\eta^{-1}(d)$ and
$w,w^{\prime}\not\in\bigcup_{K\in\mathbf{K}_{\smash{\widebar{S}}}}K$. Thus,
$q,r\not\in\smash{\widebar{S}}$ since $\mathbf{K}_{\smash{\widebar{S}}}$ is a
cover of $\tau^{-1}(\smash{\widebar{S}})$. In other words, we have
$(q_{1},d,q_{2})\xrightarrow{\smash{q}}(q_{1},d,q_{2})$ and
$(q_{1},d,q_{2})\xrightarrow{\smash{r}}(q_{1},d,q_{2})$. We get
$s_{1},s_{2},s^{\prime}_{1},s^{\prime}_{2},t_{1},t_{2},t^{\prime}_{1},t^{\prime}_{1}\in
Q$ and $e,f\in E(Q)$ such that,

  1. (1)

$[s_{1}es_{2}]_{N}=d$, $[e]_{N}=[s^{\prime}_{1}]_{N}d[s^{\prime}_{2}]_{N}$,
$[t_{1}ft_{2}]_{N}=d$, $[f]_{N}=[t^{\prime}_{1}]_{N}d[t^{\prime}_{2}]_{N}$.

  2. (2)

$q=s_{1}es_{2}$, $q_{1}=q_{1}s_{1}es^{\prime}_{1}$,
$q_{2}=s^{\prime}_{2}es_{2}q_{2}$,
$r=t_{1}ft_{2}$, $q_{1}=q_{1}t_{1}ft^{\prime}_{1}$,
$q_{2}=t^{\prime}_{2}ft_{2}q_{2}$.

This yields $[e]_{N}=[s^{\prime}_{1}t_{1}ft_{2}s^{\prime}_{2}]_{N}$ and
$[f]_{N}=[t^{\prime}_{1}s_{1}es_{2}t^{\prime}_{2}]_{N}$. Hence, we apply Lemma
41 (which follows from (7)) to get,

$\begin{array}[]{c}(es^{\prime}_{1}t_{1}ft^{\prime}_{1}s_{1}e)^{\omega}(es_{2}t^{\prime}_{2}ft_{2}s^{\prime}_{2}e)^{\omega}=\\\
(es^{\prime}_{1}t_{1}ft^{\prime}_{1}s_{1}e)^{\omega}s^{\prime}_{1}t_{1}ft_{2}s^{\prime}_{2}(es_{2}t^{\prime}_{2}ft_{2}s^{\prime}_{2}e)^{\omega}\end{array}$

We multiply by $q_{1}s_{1}$ on the left and $s_{2}q_{2}$ on the right. Recall
that $q_{1}=q_{1}s_{1}es^{\prime}_{1}$, $q_{2}=s^{\prime}_{2}es_{2}q_{2}$,
$q_{1}=q_{1}t_{1}ft^{\prime}_{1}$ and $q_{2}=t^{\prime}_{2}ft_{2}q_{2}$. We
deduce that $q_{1}s_{1}es_{2}q_{2}=q_{1}t_{1}ft_{2}q_{2}$. Since we have
$q=s_{1}es_{2}$ and $r=t_{1}ft_{2}$, we finally obtain
$q_{1}qq_{2}=q_{1}rq_{2}$, as desired.

##  6\. Handling full levels above two

We specialize Theorem 35 to characterize the classes
$\textup{BPol}(\mathscr{C})$ when $\mathscr{C}$ is itself of the form
$\mathscr{C}=\textup{BPol}(\mathscr{D})$. More precisely, we prove that in
this case, Equation (7) (which is based on $\mathscr{C}$-swaps) is equivalent
to a property based on $\mathscr{C}$-_sets_.

######  Proposition 56.

Let $\mathscr{D}$ be a prevariety and
$\mathscr{C}=\textup{BPol}(\mathscr{D})$. Let $\alpha:A^{*}\to M$ be a
surjective morphism. Then, $\alpha$ satisfies (7) if and only if it satisfies
the following condition:

(15)
$\begin{array}[]{c}(eqfre)^{\omega}(esfte)^{\omega}=(eqfre)^{\omega}qft(esfte)^{\omega}\text{
for every}\\\ \text{$\mathscr{C}$-set $\\{q,r,s,t,e,f\\}\subseteq M$ such that
$e,f\in E(M)$}.\end{array}$

Before we prove Proposition 56, let us combine it with Theorem 35. This yields
the following theorem.

######  Theorem 57.

Let $\mathscr{D}$ be a prevariety, let
$\mathscr{C}=\textup{BPol}(\mathscr{D})$ and let $\alpha:A^{*}\to M$ be a
surjective morphism. Then, $\alpha$ is a $\textup{BPol}(\mathscr{C})$-morphism
if and only if it satisfies the two following equations:

(4)
$\displaystyle\begin{array}[]{c}(eset)^{\omega+1}=(eset)^{\omega}et(eset)^{\omega}\text{
for every $t\in M$}\\\ \text{and every $\mathscr{C}$-pair $(e,s)\in E(M)\times
M$}.\end{array}$ (15)
$\displaystyle\begin{array}[]{c}(eqfre)^{\omega}(esfte)^{\omega}=(eqfre)^{\omega}qft(esfte)^{\omega}\text{
for every}\\\ \text{$\mathscr{C}$-set $\\{q,r,s,t,e,f\\}\subseteq M$ such that
$e,f\in E(M)$}.\end{array}$

Given a prevariety $\mathscr{C}$ with decidable _covering_ , Lemmas 26 and 31
imply that the $\mathscr{C}$-pairs and the $\mathscr{C}$-sets associated to an
input morphism can be computed. Hence, one may decide (4) and (15) in this
case. We get the following corollary.

######  Corollary 58.

Let $\mathscr{D}$ be a prevariety and let
$\mathscr{C}=\textup{BPol}(\mathscr{D})$. If $\mathscr{C}$-covering is
decidable, then so is $\textup{BPol}(\mathscr{C})$-membership.

Corollary 58 implies that given a concatenation hierarchy, if a _non-zero
full_ level has decidable _covering_ , then the next full level has decidable
_membership_. Together with Theorem 24 (which is proved in [41, 35]), this
yields the following.

######  Corollary 59.

If $\mathscr{G}$ is a group prevariety with decidable separation, the classes
$\textup{BPol}_{2}(\mathscr{G})$ and $\textup{BPol}_{2}(\mathscr{G}^{+})$ have
decidable membership.

Also, applying Theorem 25 (which is proved in [42]) yields the decidability of
membership for the levels _three_ in both the Straubing-Thérien hierarchy and
the dot-depth.

######  Corollary 60.

The classes $\textup{BPol}_{3}(\textup{ST})$ and
$\textup{BPol}_{3}(\textup{DD})$ have decidable membership.

######  Remark 61.

For an _arbitrary_ prevariety $\mathscr{C}$, it remains true that (4) and (15)
form a necessary condition for being a $\textup{BPol}(\mathscr{C})$-morphism.
On the other hand, they need not be sufficient. For instance, consider the
class MOD of modulo languages. One can reformulate the equations with a notion
tailored to MOD: _stable monoids_ [53]. Specifically, one can prove that a
morphism satisfies (4) and (15) if and only if its stable monoid is
$\mathrel{\mathscr{J}}$-trivial. It is well-known that this property is not
sufficient for membership in $\textup{BPol}(\textup{MOD})$ (see _e.g._ [12]).

On the other hand, Theorem 57 does hold for some input classes $\mathscr{C}$
which are _not_ of the form $\textup{BPol}(\mathscr{D})$. For instance, this
is the case for $\mathscr{C}=\textup{AT}$ as seen in Corollary 37. This is
also the case when $\mathscr{C}=\textup{ST}$ (for
$\textup{ST}=\\{\emptyset,A^{*}\\}$) or $\mathscr{C}=\textup{GR}$ (for the
class GR of all group languages).

###  6.1. Proposition 56: “only if” direction

Let $\mathscr{C}=\textup{BPol}(\mathscr{D})$ for a prevariety $\mathscr{D}$
and let $\alpha:A^{*}\to M$ be a morphism. We start with the simpler “only if”
direction, which does not require the hypothesis
$\mathscr{C}=\textup{BPol}(\mathscr{D})$. Assume that $\alpha$ satisfies (7).
We show that (15) holds as well. Let $\\{q,r,s,t,e,f\\}\subseteq M$ be a
$\mathscr{C}$-set such that $e,f\in E(M)$. We show that,

(16) $(eqfre)^{\omega}(esfte)^{\omega}=(eqfre)^{\omega}qft(esfte)^{\omega}.$

Lemma 34 yields a $\mathscr{C}$-morphism $\eta:A^{*}\to N$ such that the
$\mathscr{C}$-swaps are exactly the $\eta$-swaps. Since
$\\{q,r,s,t,e,f\\}\subseteq M$ is a $\mathscr{C}$-set, Lemma 33 implies that
it is an $\eta$-set. We obtain a set $F\subseteq A^{*}$ such that
$\alpha(F)=\\{q,r,s,t,e,f\\}$ and $\eta(u)=\eta(u^{\prime})$ for every
$u,u^{\prime}\in F$. Therefore, there exist $x\in N$ and, for each
$p\in\\{q,r,s,t,e,f\\}$, a word $u_{p}\in F$ such that $\alpha(u_{p})=p$ and
$\eta(u_{p})=x$. Let $k=\omega(N)$. We define the following words:

$\begin{array}[]{c}u^{\prime}_{q}=u_{q}u_{f}^{k-1},\
u^{\prime}_{r}=u_{r}u_{e}^{k-1},\ u^{\prime}_{s}=u_{e}^{k-1}u_{s},\
u^{\prime}_{t}=u_{f}^{k-1}u_{t},\\\ u^{\prime}_{e}=u_{e}^{k}\text{ and
}u^{\prime}_{f}=u_{f}^{k}.\end{array}$

Since $e,f\in E(M)$, we have $\alpha(u^{\prime}_{q})=qf$,
$\alpha(u^{\prime}_{r})=re$, $\alpha(u^{\prime}_{s})=es$,
$\alpha(u^{\prime}_{t})=ft$, $\alpha(u^{\prime}_{e})=e$ and
$\alpha(u^{\prime}_{f})=f$. Also, $\eta(u^{\prime}_{p})=x^{\smash{k}}\in E(N)$
for all $p\in\\{q,r,s,t,e,f\\}$ by definition of $k$. Thus,
$\eta(u^{\prime}_{q}u^{\prime}_{f}u^{\prime}_{t})=\eta(u^{\prime}_{e})$ and
$\eta(u^{\prime}_{r}u^{\prime}_{e}u^{\prime}_{s})=\eta(u^{\prime}_{f})$.
Hence, $(qf,re,es,ft,e,f)$ is an $\eta$-swap and a $\mathscr{C}$-swap by
definition of $\eta$. We now apply (7) to get (16) as desired.

###  6.2. Proposition 56: “if” direction, preliminaries

We now turn to the more difficult “if” direction, where we need the hypothesis
that $\mathscr{C}$ is of the form $\textup{BPol}(\mathscr{D})$. Assume now
that $\alpha$ satisfies (15). We prove that (7) holds as well. Therefore, we
fix a $\mathscr{C}$-swap $(q,r,s,t,e,f)\in M^{6}$ such that $e,f\in E(M)$ and
show that,

(17) $(eqfre)^{\omega}(esfte)^{\omega}=(eqfre)^{\omega}qft(esfte)^{\omega}.$

We adopt the same strategy as for the “only if” direction: we build a
$\mathscr{C}$-set from $(q,r,s,t,e,f)$ and then apply (15) to it to get (17).
First, we build a $\mathscr{C}$-morphism $\eta$ such that the $\eta$-sets are
exactly the $\mathscr{C}$-sets and satisfying properties tied to the
hypothesis $\mathscr{C}=\textup{BPol}(\mathscr{D})$.

######  Lemma 62.

There exists a $\textup{Pol}(\mathscr{D})$-morphism $\eta:A^{*}\to(N,\leq)$
satisfying the two following properties:

  * •

For all $p\in N$, the set $\alpha(\eta^{-1}(p))\subseteq M$ is a
$\mathscr{C}$-set for $\alpha$.

  * •

For all $g,g^{\prime}\in E(N)$, if $g\leq g^{\prime}$, then
$g^{\prime}=g^{\prime}gg^{\prime}$.

###### Proof.

By Corollary 13, the class $\mathscr{C}=\textup{BPol}(\mathscr{D})$ is a
prevariety. Hence, it follows from Lemma 33 that there exists a
$\mathscr{C}$-morphism $\beta_{1}:A^{*}\to T_{1}$ such that for every
$S\subseteq M$, $S$ is a $\mathscr{C}$-set for $\alpha$ if and only if $S$ is
a $\beta_{1}$-set. Additionally, since $\textup{Pol}(\mathscr{D})$ is a
positive prevariety by Theorem 12 and
$\mathscr{C}=\textup{BPol}(\mathscr{D})$, Lemma 14 yields a
$\textup{Pol}(\mathscr{D})$-morphism $\beta_{2}:A^{*}\to(T_{2},\leq)$ and a
morphism $\delta:T_{2}\to T_{1}$ such that $\beta_{1}=\delta\circ\beta_{2}$.
Finally, it follows from Lemma 27 that there exists a $\mathscr{D}$-morphism
$\gamma:A^{*}\to Q$ such that for every pair $(x,y)\in N^{2}$, $(x,y)$ is a
$\mathscr{D}$-pair for $\beta_{2}$ if and only if $(x,y)$ is a $\gamma$-pair.
Since $\mathscr{D}\subseteq\textup{Pol}(\mathscr{D})$, $\gamma$ is also a
$\textup{Pol}(\mathscr{D})$-morphism (recall that we view $Q$ as ordered
monoid $(Q,=)$). We now consider the ordered monoid $(T_{2}\times Q,\leq)$
equipped with componentwise multiplication and whose ordering is defined by
$(t,q)\leq(t^{\prime},q^{\prime})$ if and only if $t\leq t^{\prime}$ and
$q=q^{\prime}$ for all $(t,q),(t^{\prime},q^{\prime})\in T_{2}\times Q$.
Moreover, we let $\beta_{3}:A^{*}\to(T_{2}\times Q,\leq)$ as the morphism
which is defined by $\beta_{3}(w)=(\beta_{2}(w),\gamma(w))$ for every $w\in
A^{*}$. Finally, we let $\eta:A^{*}\to(N,\leq)$ as the surjective restriction
of $\beta_{3}$. Since $\textup{Pol}(\mathscr{D})$ is a positive prevariety by
Theorem 12, it is clear that $\eta$ is a $\textup{Pol}(\mathscr{D})$-morphism.
Indeed, the definition implies that every language recognized by $\eta$ is
built by making unions and intersections of languages recognized by the
$\textup{Pol}(\mathscr{D})$-morphisms $\beta_{2}$ and $\gamma$. It remains to
verify that $\eta$ satisfies the two assertions.

For the first assertion, let $p\in N$. By definition of $\eta$, all words in
$\eta^{-1}(p)$ have the same image under $\beta_{2}$ and therefore under
$\beta_{1}$ as well since $\beta_{1}=\delta\circ\beta_{2}$. Hence,
$\alpha(\eta^{-1}(p))$ is a $\beta_{1}$-set for $\alpha$. It follows from the
definition of $\beta_{1}$ that $\alpha(\eta^{-1}(p))\subseteq M$ is a
$\mathscr{C}$-set for $\alpha$.

We turn to the second assertion. Let $g,g^{\prime}\in E(N)$ such that $g\leq
g^{\prime}$. We prove that $g^{\prime}=g^{\prime}gg^{\prime}$. Since
$g^{\prime}\in E(N)$ and $g\leq g^{\prime}$, it is immediate that
$g^{\prime}gg^{\prime}\leq g^{\prime}$. Hence, it suffices to show that
$g^{\prime}\leq g^{\prime}gg^{\prime}$. Since $\eta$ is surjective by
construction, there exist $u,u^{\prime}\in A^{*}$ such that $\eta(u)=g$ and
$\eta(u^{\prime})=g^{\prime}$. It remains to prove that
$\eta(u^{\prime})\leq\eta(u^{\prime}uu^{\prime})$. Since for all $w\in A^{*}$,
we have $\eta(w)=(\beta_{2}(w),\gamma(w))$, this amounts to proving that
$\beta_{2}(u^{\prime})\leq\beta_{2}(u^{\prime}uu^{\prime})$ and
$\gamma(u^{\prime})=\gamma(u^{\prime}uu^{\prime})$. Since $\eta(u^{\prime})\in
E(N)$, we have $\gamma(u^{\prime})\in E(Q)$ and $\beta_{2}(u^{\prime})\in
E(T_{2})$. From $\eta(u)\leq\eta(u^{\prime})$, we deduce
$\gamma(u)=\gamma(u^{\prime})$, yielding
$\gamma(u^{\prime})=\gamma(u^{\prime}uu^{\prime})$. Moreover,
$\gamma(u)=\gamma(u^{\prime})$ also implies that
$(\beta_{2}(u^{\prime}),\beta_{2}(u))$ is a $\gamma$-pair for $\beta_{2}$.
Therefore, it is a $\mathscr{D}$-pair for $\beta_{2}$ by definition of
$\gamma$. Since $\beta_{2}(u^{\prime})\in E(T_{2})$ and $\beta_{2}$ is a
$\textup{Pol}(\mathscr{D})$-morphism, we deduce that
$\beta_{2}(u^{\prime})\leq\beta_{2}(u^{\prime}uu^{\prime})$ from Theorem 29,
completing the proof. ∎

We use the $\textup{Pol}(\mathscr{D})$-morphism $\eta:A^{*}\to(N,\leq)$ to
construct a $\mathscr{C}$-morphism $\beta:A^{*}\to R$. Since $(q,r,s,t,e,f)$
is a $\mathscr{C}$-swap, this will imply that it is also a $\beta$-swap. We
shall then exploit the definition of $\beta$ to build our $\mathscr{C}$-set
from $\eta$ using the first assertion in Lemma 62.

For every $v\in A^{*}$, we let $\lceil v\rceil_{\eta}=\\{v^{\prime}\in
A^{*}\mid\eta(v)\leq\eta(v^{\prime})\\}$ which a language recognized by
$\eta$. Hence, $\lceil v\rceil_{\eta}\in\textup{Pol}(\mathscr{D})$ since
$\eta$ is a $\textup{Pol}(\mathscr{D})$-morphism. Let
$k=|M|^{2}\times|N|^{2}+2$. We define $\mathbf{H}=\\{\lceil
v_{1}\rceil_{\eta}\cdots\lceil v_{\ell}\rceil_{\eta}\mid\ell\leq k\text{ and
}v_{1},\dots,v_{\ell}\in A^{*}\\}$. Since $\textup{Pol}(\mathscr{D})$ is
closed under concatenation by Theorem 12, it follows that $\mathbf{H}$ is a
_finite_ set of languages in $\textup{Pol}(\mathscr{D})\subseteq\mathscr{C}$.
Thus, Proposition 10 yields a $\mathscr{C}$-morphism $\beta:A^{*}\to R$
recognizing every $H\in\mathbf{H}$. Since $v\in\lceil v\rceil_{\eta}$ for all
$v\in A^{*}$, one may verify that for all $w,w^{\prime}\in A^{*}$, we have
$\beta(w)=\beta(w^{\prime})\Rightarrow\eta(w)=\eta(w^{\prime})$. We shall use
this fact repeatedly.

######  Remark 63.

The construction of $\eta$ and $\beta$ is where we need the hypothesis that
$\mathscr{C}=\textup{BPol}(\mathscr{D})$.

###  6.3. Proposition 56: “if” direction, main proof

We are ready to start the construction of a $\mathscr{C}$-set from our
$\mathscr{C}$-swap $(q,r,s,t,e,f)$. By definition of the $\mathscr{C}$-swaps,
the hypothesis that $\beta:A^{*}\to R$ is a $\mathscr{C}$-morphism yields
$u_{q},u_{r},u_{s},u_{t},u_{e},u_{f}\in A^{*}$ such that
$\beta(u_{e}),\beta(u_{f})\in E(R)$, $\beta(u_{e})=\beta(u_{q}u_{f}u_{t})$,
$\beta(u_{f})=\beta(u_{r}u_{e}u_{s})$ and $\alpha(u_{x})=x$ for every
$x\in\\{q,r,s,t,e,f\\}$. We define $p_{q}=\eta(u_{q})$, $p_{r}=\eta(u_{r})$,
$p_{s}=\eta(u_{s})$, $p_{t}=\eta(u_{t})$, $g_{e}=\eta(u_{e})$ and
$g_{f}=\eta(u_{f})$.

Recall that $\beta(w)=\beta(w^{\prime})\Rightarrow\eta(w)=\eta(w^{\prime})$
for all $w,w^{\prime}\in A^{*}$. Hence, by hypothesis on
$u_{q},u_{r},u_{s},u_{t},u_{e},u_{f}\in A^{*}$, the definitions imply that
$g_{e},g_{f}\in E(N)$, $g_{e}=p_{q}g_{f}p_{t}$ and $g_{f}=p_{r}g_{e}p_{s}$.

######  Fact 64.

We have the following equalities:

  * •

$g_{e}=g_{e}p_{s}g_{f}p_{r}g_{e}=(g_{e}p_{s}g_{f}p_{t}g_{e})^{\omega}$ and

  * •

$g_{f}=g_{f}p_{t}g_{e}p_{q}g_{f}=(g_{f}p_{t}g_{e}p_{s}g_{f})^{\omega}$.

###### Proof.

First, observe that since $g_{e},g_{f}\in E(N)$, $g_{e}=p_{q}g_{f}p_{t}$ and
$g_{f}=p_{r}g_{e}p_{s}$, we have the equalities
$g_{e}=g_{e}p_{q}g_{f}p_{t}g_{e}$ and $g_{f}=g_{f}p_{r}g_{e}p_{s}g_{f}$.

We now prove that $g_{e}=(g_{e}p_{s}g_{f}p_{t}g_{e})^{\omega}$. By Lemma 2, it
suffices to prove that $g_{e}\mathrel{\mathscr{H}}g_{e}p_{s}g_{f}p_{t}g_{e}$.
It is clear that $g_{e}p_{s}g_{f}p_{t}g_{e}\leqslant_{\mathscr{H}}g_{e}$.
Furthermore, since $g_{e}=g_{e}p_{q}g_{f}p_{t}g_{e}$ and
$g_{f}=g_{f}p_{r}g_{e}p_{s}g_{f}$, we get
$g_{e}=g_{e}p_{q}(g_{f}p_{r}g_{e}p_{s}g_{f})p_{t}g_{e}=g_{e}p_{q}g_{f}p_{r}(g_{e}p_{s}g_{f}p_{t}g_{e})$.
Therefore, $g_{e}\leqslant_{\mathscr{J}}g_{e}p_{s}g_{f}p_{t}g_{e}$ and Lemma 1
yields $g_{e}\mathrel{\mathscr{H}}g_{e}p_{s}g_{f}p_{t}g_{e}$ as desired. The
proof of the equality $g_{f}=(g_{f}p_{t}g_{e}p_{s}g_{f})^{\omega}$ is
symmetrical.

We turn to proving that $g_{e}=g_{e}p_{s}g_{f}p_{r}g_{e}$ and
$g_{f}=g_{f}p_{t}g_{e}p_{q}g_{f}$. By symmetry, we only prove the first
equality. Observe that since $g_{f}=p_{r}g_{e}p_{s}$, we have
$g_{e}p_{s}g_{f}p_{r}g_{e}g_{e}p_{s}g_{f}p_{r}g_{e}=g_{e}p_{s}g_{f}p_{r}g_{e}$.
Thus, $g_{e}p_{s}g_{f}p_{r}g_{e}\in E(N)$ and by Lemma 2 it suffices to prove
that $g_{e}p_{s}g_{f}p_{r}g_{e}\mathrel{\mathscr{H}}g_{e}$. Clearly,
$g_{e}p_{s}g_{f}p_{r}g_{e}\leqslant_{\mathscr{H}}g_{e}$. Furthermore, since we
have $g_{f}=p_{r}g_{e}p_{s}$ and $g_{f}=(g_{f}p_{t}g_{e}p_{s}g_{f})^{\omega}$,
we know that $g_{f}\leqslant_{\mathscr{J}}g_{e}p_{s}g_{f}p_{r}g_{e}$. Finally,
since we have $g_{e}=p_{q}g_{f}p_{t}$, we get
$g_{e}\leqslant_{\mathscr{J}}g_{f}\leqslant_{\mathscr{J}}g_{e}p_{s}g_{f}p_{r}g_{e}$.
It then follows from Lemma 1 that
$g_{e}\mathrel{\mathscr{H}}g_{e}p_{s}g_{f}p_{r}g_{e}$, which completes the
proof. ∎

We now use the morphism $\beta$ to decompose $u_{e}$ and $u_{f}$. We shall
then use the factors to construct our $\mathscr{C}$-set.

######  Lemma 65.

There exist six words $x_{e},y_{e},z_{e},x_{f},y_{f},z_{f}\in A^{*}$ and
$g^{\prime}\in E(N)$ satisfying the following conditions:

  * •

$\alpha(y_{e})\in E(M)$, $e=\alpha(x_{e}y_{e}z_{e})$ and
$g_{e}=\eta(x_{e}y_{e}z_{e})$

  * •

$\alpha(y_{f})\in E(M)$, $f=\alpha(x_{f}y_{f}z_{f})$ and
$g_{f}=\eta(x_{f}y_{f}z_{f})$.

  * •

$g^{\prime}=\eta(y_{e})=\eta(y_{f})$ and
$g^{\prime}=g^{\prime}g_{f}g^{\prime}$.

  * •

$g_{f}\leq\eta(x_{f})$, $g_{f}\leq\eta(z_{f})$.

  * •

$g_{e}p_{q}g_{f}\leq\eta(x_{e})$ and $g_{f}p_{t}g_{e}\leq\eta(z_{e})$.

###### Proof.

We let $w_{1,0}=\cdots=w_{k,0}=u_{f}$ and use induction on an integer $h\geq
1$ to build $2k$ words $v_{1,h},\dots,v_{k,h},w_{1,h},\dots,w_{k,h}\in A^{*}$
satisfying the following conditions:

  * •

$u_{e}=v_{1,h}\cdots v_{k,h}$ and $u_{f}=w_{1,h}\cdots w_{k,h}$.

  * •

$\eta(w_{i,h-1})\leq\eta(v_{i,h})\leq\eta(w_{i,h})$ for $2\leq i<k$.

  * •

$g_{e}p_{q}\eta(w_{1,h-1})\leq\eta(v_{1,h})$ and
$g_{f}p_{r}\eta(v_{1,h})\leq\eta(w_{1,h})$.

  * •

$\eta(w_{k,h-1})p_{t}g_{e}\leq\eta(v_{k,h})$ and
$\eta(v_{k,h})p_{s}g_{f}\leq\eta(w_{k,h})$.

Let $h\geq 1$. Assume that $w_{1,h-1},\dots,w_{k,h-1}$ are defined. We have
$\beta(w_{1,h-1}\cdots w_{k,h-1})=\beta(u_{f})$. Since $\beta(u_{e})\in E(R)$
and $\beta(u_{e})=\beta(u_{q}u_{f}u_{t})$, we get
$\beta(u_{e})=\beta(u_{e}u_{q}w_{1,h-1}\cdots w_{k,h-1}u_{t}u_{e})$.
Furthermore, $\beta$ recognizes the following language by definition,

$H=\lceil u_{e}u_{q}w_{1,h-1}\rceil_{\eta}\lceil
w_{2,h-1}\rceil_{\eta}\cdots\lceil w_{k-1,h-1}\rceil_{\eta}\lceil
w_{k,h-1}u_{t}u_{e}\rceil_{\eta}.$

Since $u_{e}u_{q}w_{1,h-1}\cdots w_{k,h-1}u_{t}u_{e}\in H$, we get $u_{e}\in
H$. Therefore, there exist words $v_{1,h},\dots,v_{k,h}$ such that
$u_{e}=v_{1,h}\cdots v_{k,h}$, $v_{1,h}\in\lceil
u_{e}u_{q}w_{1,h-1}\rceil_{\eta}$, $v_{i,h}\in\lceil w_{i,h-1}\rceil_{\eta}$
for every $2\leq i<k$, and $v_{k,h}\in\lceil
w_{k,h-1}u_{t}u_{e}\rceil_{\eta}$. We obtain
$g_{e}p_{q}\eta(w_{1,h-1})\leq\eta(v_{1,h})$,
$\eta(w_{i,h-1})\leq\eta(v_{i,h})$ for $2\leq i<k$ and
$\eta(w_{k,h-1})p_{t}g_{e}\leq\eta(v_{k,h})$. Since $\beta(u_{f})\in E(R)$ and
$\beta(u_{f})=\beta(u_{r}u_{e}u_{s})$ by hypothesis. A symmetrical argument
yields words $w_{1,h},\dots,w_{k,h}$ such that $u_{f}=w_{1,h}\cdots w_{k,h}$,
$g_{f}p_{r}\eta(v_{1,h})\leq\eta(w_{1,h})$, $\eta(v_{i,h})\leq\eta(w_{i,h})$
for $2\leq i<k$ and $\eta(v_{k,h})p_{s}g_{f}\leq\eta(w_{k,h})$. This concludes
the construction of the $2k$ words satisfying the desired construction.

Let $d=\omega(M)\times\omega(N)$. Since $N$ is finite, there are two indices
$m<m^{\prime}$ and $\eta(w_{i,dm})=\eta(w_{i,dm^{\prime}})$ for $2\leq i<k$.
We fix these two numbers $m,m^{\prime}\geq 1$. Since
$k-2=|M|^{2}\times|N|^{2}$, the pigeonhole principle yields $1\leq i<j<k$ such
that,

$\begin{array}[]{lll}\alpha(w_{2,dm}\cdots w_{i,dm})&=&\alpha(w_{2,dm}\cdots
w_{j,dm}),\\\ \alpha(v_{2,dm+1}\cdots v_{i,dm+1})&=&\alpha(v_{2,dm+1}\cdots
v_{j,dm+1}),\\\ \eta(w_{2,dm}\cdots w_{i,dm})&=&\eta(w_{2,dm}\cdots
w_{j,dm}),\\\ \eta(v_{2,dm+1}\cdots v_{i,dm+1})&=&\eta(v_{2,dm+1}\cdots
v_{j,dm+1}).\end{array}$

We now define,

$\begin{array}[]{ll}x_{e}=v_{1,dm+1}\cdots v_{i,dm+1}&x_{f}=w_{1,dm}\cdots
w_{i,dm},\\\ y_{e}=(v_{i+1,dm+1}\cdots v_{j,dm+1})^{d}&y_{f}=(w_{i+1,dm}\cdots
w_{j,dm})^{d},\\\ z_{e}=v_{j+1,dm+1}\cdots v_{k,dm+1}&z_{f}=w_{j+1,dm}\cdots
w_{k,dm}.\end{array}$

It remains to prove that the conditions in the lemma are satisfied. For the
first two, we have $\alpha(y_{e}),\alpha(y_{f})\in E(M)$ by definition of $d$.
In addition, by definition of $i$ and $j$, we know that we have

$\alpha(x_{e}y_{e}z_{e})=\alpha(v_{1,dm+1}\cdots v_{k,dm+1})=\alpha(u_{e})=e,$

as well as

$\alpha(x_{f}y_{f}z_{f})=\alpha(w_{1,dm}\cdots w_{k,dm})=\alpha(u_{f})=f.$

Furthermore, $\eta(x_{e}y_{e}z_{e})=\eta(u_{e})=g_{e}$ and
$\eta(x_{f}y_{f}z_{f})=\eta(u_{f})=g_{f}$.

We turn to the third assertion. Define $g^{\prime}=\eta(y_{e})$. By choice of
$d$, we have $g^{\prime}\in E(N)$. Moreover, for $2\leq\ell<k$, we have
$\eta(w_{\ell,0})\leq\eta(w_{\ell,dm})\leq\eta(v_{\ell,dm+1})\leq\eta(w_{\ell,dm^{\prime}})$.
Hence, since $w_{i,0}=u_{f}$, $g_{f}=\eta(u_{f})$ and
$\eta(w_{\ell,dm})=\eta(w_{\ell,dm^{\prime}})$ for $2\leq\ell<k$, we obtain
that $g_{f}\leq\eta(w_{\ell,dm})=\eta(v_{\ell,dm+1})$. One can multiply these
inequalities for $i+1\leq\ell\leq j$. Since $g_{f}\in E(N)$, this yields
$g_{f}\leq\eta(y_{e})=\eta(y_{f})$ by definition. Hence,
$g^{\prime}=\eta(y_{e})=\eta(y_{f})$ and $g_{f}\leq g^{\prime}$. We get
$g^{\prime}=g^{\prime}g_{f}g^{\prime}$ from Lemma 62.

For the remaining assertions, we only show that $g_{f}\leq\eta(x_{f})$ and
$g_{e}p_{q}g_{f}\leq\eta(x_{e})$. The proof of the other inequalities is
symmetrical. By definition, we have $w_{1,0}=u_{f}$,
$g_{e}p_{q}\eta(w_{1,h-1})\leq\eta(v_{1,h})$ and
$g_{f}p_{r}\eta(v_{1,h})\leq\eta(w_{1,h})$ for all $h\geq 1$. Since
$g_{\smash{f}}\in E(N)$, we get
$g_{e}p_{q}(g_{f}p_{r}g_{e}p_{q}g_{f})^{h-1}\leq\eta(v_{1,h})$ and
$(g_{f}p_{r}g_{e}p_{q}g_{f})^{h}\leq\eta(w_{1,h})$ by a simple induction.
Also, $g_{f}=(g_{f}p_{r}g_{e}p_{q}g_{f})^{\omega}$ by Fact 64. Thus, we have
$g_{f}\leq\eta(w_{1,dm})$ and $g_{e}p_{q}g_{f}\leq\eta(v_{1,dm+1})$ by
definition of $d$. Finally, we have
$g_{f}\leq\eta(w_{\ell,dm})=\eta(v_{\ell,dm+1})$ for $2\leq i<k$. Hence,
$g_{f}\leq\eta(x_{f})$ and $g_{e}p_{q}g_{f}\leq\eta(x_{e})$. ∎

We fix the words $x_{e},y_{e},z_{e},x_{f},y_{f},z_{f}\in A^{*}$ and the
element $g^{\prime}\in E(N)$ given by Lemma 65. Let
$h=\omega(M)\times\omega(N)$. We let,

$\begin{array}[]{ll}y_{q}=y_{e}z_{e}u_{q}x_{f}y_{f},&y_{r}=y_{f}z_{f}(u_{r}u_{e}u_{q}u_{f})^{h-1}u_{r}x_{e}y_{e},\\\
y_{t}=y_{f}z_{f}u_{t}x_{e}y_{e},&y_{s}=y_{e}z_{e}u_{s}(u_{f}u_{t}u_{e}u_{s})^{h-1}x_{f}y_{f}.\end{array}$

Let $\hat{x}=\alpha(y_{x})$ for $x\in\\{q,r,s,t,e,f\\}$. Recall that in order
to apply Equation (15), we need to construct a $\mathscr{C}$-set. We will show
below that $\\{\hat{q},\hat{r},\hat{s},\hat{t},\hat{e},\hat{f}\\}$ is such a
$\mathscr{C}$-set. Note that $\hat{e},\hat{f}\in E(M)$ by Lemma 65. Since
$\alpha(y_{f}),\alpha(y_{e})\in E(M)$ and
$\alpha(x_{f}y_{f}z_{f})=\alpha(u_{f})=f$ by Lemma 65, one can verify that,

$\begin{array}[]{lll}\hat{e}\hat{q}\hat{f}\hat{r}\hat{e}&=&\alpha(y_{e}z_{e})qf(reqf)^{h-1}r\alpha(x_{e}y_{e}),\\\
&=&\alpha(y_{e}z_{e})(qfre)^{h-1}qfr\alpha(x_{e}y_{e}).\end{array}$

Symmetrically, one can verify that,

$\begin{array}[]{lll}\hat{e}\hat{s}\hat{f}\hat{t}\hat{e}&=&\alpha(y_{e}z_{e})s(ftes)^{h-1}ft\alpha(x_{e}y_{e}),\\\
&=&\alpha(y_{e}z_{e})sft(esft)^{h-1}\alpha(x_{e}y_{e}).\end{array}$

Since $\alpha(x_{e}y_{e}z_{e})=e$ by Lemma 65, it follows that,

$\alpha(x_{e})(\hat{e}\hat{q}\hat{f}\hat{r}\hat{e})^{\omega}(\hat{e}\hat{s}\hat{f}\hat{t}\hat{e})^{\omega}\alpha(z_{e})=(eqfre)^{\omega}(esfte)^{\omega}.$

Moreover, the definitions yield
$\hat{q}\hat{f}\hat{t}=\alpha(y_{e}z_{e})qft\alpha(x_{e}y_{e})$. Hence, using
again the equality $\alpha(x_{e}y_{e}z_{e})=e$ of Lemma 65, we get,

$\alpha(x_{e})(\hat{e}\hat{q}\hat{f}\hat{r}\hat{e})^{\omega}\hat{q}\hat{f}\hat{t}(\hat{e}\hat{s}\hat{f}\hat{t}\hat{e})^{\omega}\alpha(z_{e})=(eqfre)^{\omega}qft(esfte)^{\omega}.$

We prove that
$(\hat{e}\hat{q}\hat{f}\hat{r}\hat{e})^{\omega}(\hat{e}\hat{s}\hat{f}\hat{t}\hat{e})^{\omega}=(\hat{e}\hat{q}\hat{f}\hat{r}\hat{e})^{\omega}\hat{q}\hat{f}\hat{t}(\hat{e}\hat{s}\hat{f}\hat{t}\hat{e})^{\omega}$.
In view of the above, this will imply that (17) holds as desired (namely that
$(eqfre)^{\omega}(esfte)^{\omega}=(eqfre)^{\omega}qft(esfte)^{\omega}$). Since
$\alpha$ satisfies (15), it suffices to prove that
$\\{\hat{q},\hat{r},\hat{s},\hat{t},\hat{e},\hat{f}\\}\subseteq M$ is a
$\mathscr{C}$-set. We show that
$\\{\hat{q},\hat{r},\hat{s},\hat{t},\hat{e},\hat{f}\\}$ is a subset of
$\alpha(\eta^{-1}(g^{\prime}))$, which is a $\mathscr{C}$-set by Lemma 62.
Thus, $\\{\hat{q},\hat{r},\hat{s},\hat{t},\hat{e},\hat{f}\\}$ is itself a
$\mathscr{C}$-set by Fact 32.

By definition, we have to prove that for
$y\in\\{y_{q},y_{r},y_{s},y_{t},y_{e},y_{f}\\}$, we have $\eta(y)=g^{\prime}$.
By Lemma 65, we already know this for $y=y_{e}$ and $y=y_{f}$. By symmetry, we
only treat the cases $y=y_{q}$ and $y=y_{r}$. It suffices to prove that
$\eta(y)\mathrel{\mathscr{H}}g^{\prime}$ and $g^{\prime}\leq\eta(y)$. Indeed,
since $g^{\prime}\in E(N)$, Lemma 2 and
$\eta(y)\mathrel{\mathscr{H}}g^{\prime}$ imply
$(\eta(y))^{\omega}=g^{\prime}$. Moreover, $g^{\prime}\leq\eta(y)$ yields
$g^{\prime}\leq(\eta(y))^{\omega-1}$. Multiplying by $\eta(y)$ yields
$g^{\prime}\eta(y)\leq(\eta(y))^{\omega}=g^{\prime}$. Since
$g^{\prime}\eta(y)=\eta(y)$ (by definition of $y_{q},y_{r}$ as
$\eta(y_{e})=\eta(y_{f})=g^{\prime}$), we get $\eta(y)\leq g^{\prime}$.
Altogeter, we obtain $g^{\prime}=\eta(y)$, as desired.

We first show that $\eta(y_{q})\mathrel{\mathscr{H}}g^{\prime}$ and
$g^{\prime}\leq\eta(y_{q})$. We know that $y_{q}=y_{e}z_{e}u_{q}x_{f}y_{f}$
and Lemma 65 yields $g_{f}\leq\eta(x_{f})$ and
$g_{f}p_{t}g_{e}\leq\eta(z_{e})$. We get
$g^{\prime}g_{f}p_{t}g_{e}p_{q}g_{f}g^{\prime}\leq\eta(y_{q})$. Thus, since
$g_{f}p_{t}g_{e}p_{q}g_{f}=g_{f}$ by Fact 64 and
$g^{\prime}g_{f}g^{\prime}=g^{\prime}$ by Lemma 65, we get
$g^{\prime}\leq\eta(y_{q})$. Moreover, since
$g^{\prime}=\eta(y_{e})=\eta(y_{f})$, it is clear that
$\eta(y_{q})\leqslant_{\mathscr{H}}g^{\prime}$. Thus, we show that
$g^{\prime}\leqslant_{\mathscr{J}}\eta(y_{q})$. This will imply
$\eta(y_{q})\mathrel{\mathscr{H}}g^{\prime}$ by Lemma 1. By definition,
$y_{q}=y_{e}z_{e}u_{q}x_{f}y_{f}$. Hence, Lemma 65 yields,

$\eta(x_{e}y_{q}z_{f})=\eta(x_{e}(y_{e}z_{e}u_{q}x_{f}y_{f})z_{f})=\eta(u_{e}u_{q}u_{f})=g_{e}p_{q}g_{f}.$

Since $g_{f}p_{t}g_{e}p_{q}g_{f}=g_{f}$ by Fact 64, we get
$g_{f}\leqslant_{\mathscr{J}}\eta(y_{q})$. Also,
$g^{\prime}\leqslant_{\mathscr{J}}g_{f}$ since
$g^{\prime}=g^{\prime}g_{f}g^{\prime}$. We get
$g^{\prime}\leqslant_{\mathscr{J}}\eta(y_{q})$ as desired.

We now prove that $\eta(y_{r})\mathrel{\mathscr{H}}g^{\prime}$ and that
$g^{\prime}\leq\eta(y_{r})$. We have
$y_{r}=y_{f}z_{f}(u_{r}u_{e}u_{q}u_{f})^{h-1}u_{r}x_{e}y_{e}$. Lemma 65 yields
$g_{f}\leq\eta(z_{f})$ and $g_{e}p_{q}g_{f}\leq\eta(x_{e})$. Thus,
$g^{\prime}(g_{f}p_{r}g_{e}p_{q}g_{f})^{h}g^{\prime}\leq\eta(y_{r})$. Since
$h$ is a multiple of $\omega(N)$, this yields
$g^{\prime}g_{f}g^{\prime}\leq\eta(y_{r})$ by Fact 64. Thus,
$g^{\prime}\leq\eta(y_{r})$ by Lemma 65. Also, the definition of $y_{r}$ and
the fact that $g^{\prime}=\eta(y_{e})=\eta(y_{f})$ yield
$\eta(y_{r})\leqslant_{\mathscr{H}}g^{\prime}$. Thus, it suffices to show that
$g^{\prime}\leqslant_{\mathscr{J}}\eta(y_{r})$. This implies
$\eta(y_{r})\mathrel{\mathscr{H}}g^{\prime}$ by Lemma 1. By definition,
$y_{r}=y_{f}z_{f}(u_{r}u_{e}u_{q}u_{f})^{h-1}u_{r}x_{e}y_{e}$. Thus, Lemma 65
yields,

$\eta(x_{f}y_{r}z_{e})=(g_{f}p_{r}g_{e}p_{q}g_{f})^{h}p_{r}g_{e}.$

Moreover, $(g_{f}p_{r}g_{e}p_{q}g_{f})^{h}=g_{f}$ by Fact 64. Thus,
$g_{f}\leqslant_{\mathscr{J}}\eta(y_{r})$. Finally, since
$g^{\prime}=g^{\prime}g_{f}g^{\prime}$, we also have
$g^{\prime}\leqslant_{\mathscr{J}}g_{f}$. We get
$g^{\prime}\leqslant_{\mathscr{J}}\eta(y_{r})$, which completes the proof.

##  7\. Conclusion

In this paper, we studied the BPol operator used in the construction of
concatenation hierarchies. We proved a generic characterization of the classes
$\textup{BPol}(\mathscr{C})$ that depends on an _ad hoc_ property of the class
$\mathscr{C}$. While it is not clear when this property on $\mathscr{C}$ is
decidable in general, a first consequence is a new effective characterization
of levels two in the dot-depth and Straubing-Thérien hierarchies, which is
simpler than the previously known ones.

When $\mathscr{C}$ is itself of the form $\textup{BPol}(\mathscr{D})$, our
characterization simplifies and yields a reduction from
$\textup{BPol}(\mathscr{C})$-membership to $\mathscr{C}$-covering. The latter
problem was known to be decidable for level one in several hierarchies whose
bases consist of group languages such as the group and modulo hierarchies.
Combined with our results, this implies that level two is decidable in these
hierarchies. Finally, it was known that level _two_ has decidable covering in
the Straubing-Thérien hierarchy and the dot-depth. Hence, we obtain that level
_three_ is decidable in these hierarchies.

## References

  * [1] Jorge Almeida.  Implicit operations on finite j-trivial semigroups and a conjecture of I. Simon.  Journal of Pure and Applied Algebra, 69:205–218, 1990.
  * [2] Jorge Almeida.  Implicit operations and Knast’s theorem.  In Semigroups (Luino, 1992), pages 1–16. World Sci. Publ., River Edge, NJ, 1993.
  * [3] Jorge Almeida and Ondrej Klíma.  A counterexample to a conjecture concerning concatenation hierarchies.  Information Processing Letters, 110(1):4–7, 2009.
  * [4] Jorge Almeida and Ondrej Klíma.  New decidable upper bound of the 2nd level in the Straubing-Thérien concatenation hierarchy of star-free languages.  Discrete Mathematics & Theoretical Computer Science, 12(4):41–58, 2010.
  * [5] Mustapha Arfi.  Polynomial operations on rational languages.  In Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, STACS’87, pages 198–206. Springer, 1987.
  * [6] Mustapha Arfi.  Opérations polynomiales et hiérarchies de concaténation.  Theoretical Computer Science, 91(1):71 – 84, 1991.
  * [7] Christopher J. Ash.  Inevitable graphs: a proof of the type II conjecture and some related decision procedures.  International Journal of Algebra and Computation, 1(1):127–146, 1991.
  * [8] F. Blanchet-Sadri.  On dot-depth two.  RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 24(6):521–529, 1990.
  * [9] F. Blanchet-Sadri.  On a complete set of generators for dot-depth two.  Discrete Applied Mathematics, 50(1):1–25, 1994.
  * [10] Janusz A. Brzozowski and Rina S. Cohen.  Dot-depth of star-free events.  Journal of Computer and System Sciences, 5(1):1–16, 1971.
  * [11] Janusz A. Brzozowski and Robert Knast.  The dot-depth hierarchy of star-free languages is infinite.  Journal of Computer and System Sciences, 16(1):37–55, 1978.
  * [12] Laura Chaubard, Jean-Éric Pin, and Howard Straubing.  First order formulas with modular predicates.  In Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS’06), pages 211–220, 2006.
  * [13] David Cowan.  Inverse monoids of dot-depth two.  International Journal of Algebra and Computation, 03(04):411–424, 1993.
  * [14] Wojciech Czerwiński, Wim Martens, and Tomáš Masopust.  Efficient separability of regular languages by subsequences and suffixes.  In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, ICALP’13, pages 150–161. Springer, 2013.
  * [15] James Alexander Green.  On the structure of semigroups.  Annals of Mathematics, 54(1):163–172, 1951.
  * [16] Karsten Henckell, Stuart Margolis, Jean-Éric Pin, and John Rhodes.  Ash’s type II theorem, profinite topology and Malcev products.  International Journal of Algebra and Computation, 1:411–436, 1991\.
  * [17] Karsten Henckell and John Rhodes.  The theorem of knast, the pg=bg and type II conjectures.  Monoids and semigroups with applications, Word Scientific, pages 453–463, 1991.
  * [18] Peter Higgins.  A proof of simon’s theorem on piecewise testable languages.  Theoretical computer science, 178(1):257–264, 1997.
  * [19] Ondrej Klima.  Piecewise testable languages via combinatorics on words.  Discrete Mathematics, 311(20):2124–2127, 2011.
  * [20] Robert Knast.  A semigroup characterization of dot-depth one languages.  RAIRO - Theoretical Informatics and Applications, 17(4):321–330, 1983.
  * [21] Manfred Kufleitner and Alexander Lauser.  Around dot-depth one.  International Journal of Foundations of Computer Science, 23(6):1323–1340, 2012.
  * [22] Manfred Kufleitner and Tobias Walter.  One quantifier alternation in first-order logic with modular predicates.  RAIRO Theor. Informatics Appl., 49(1):1–22, 2015.
  * [23] Stuart W. Margolis and Jean-Éric Pin.  Products of group languages.  In FCT’85. Springer, 1985.
  * [24] Crispin St. John Alvah Nash-Williams.  On well-quasi-ordering finite trees.  Mathematical Proceedings of the Cambridge Philosophical Society, 59(4):833–835, 1963.
  * [25] Dominique Perrin and Jean-Éric Pin.  First-order logic and star-free sets.  Journal of Computer and System Sciences, 32(3):393–406, 1986.
  * [26] Jean-Éric Pin.  Varieties Of Formal Languages.  Plenum Publishing Co., 1986.
  * [27] Jean-Éric Pin.  PG = BG, a success story.  NATO Advanced Study Institute, Semigroups, Formal Languages and Groups, pages 33–47, 1995.
  * [28] Jean-Éric Pin.  An explicit formula for the intersection of two polynomials of regular languages.  In DLT 2013, volume 7907 of Lect. Notes Comp. Sci., pages 31–45. Springer, 2013.
  * [29] Jean-Éric Pin.  The dot-depth hierarchy, 45 years later, chapter 8, pages 177–202.  World Scientific, 2017.
  * [30] Jean-Éric Pin.  Mathematical foundations of automata theory.  In preparation https://www.irif.fr/~jep/PDF/MPRI/MPRI.pdf, 2019\.
  * [31] Jean-Éric Pin and Howard Straubing.  Monoids of upper triangular boolean matrices.  In Semigroups. Structure and Universal Algebraic Problems, volume 39, pages 259–272. North-Holland, 1985.
  * [32] Jean-Éric Pin and Pascal Weil.  Profinite semigroups, Mal’cev products and identities.  Journal of Algebra, 182(3):604–626, 1996.
  * [33] Jean-Éric Pin and Pascal Weil.  Polynomial closure and unambiguous product.  Theory of Computing Systems, 30(4):383–422, 1997.
  * [34] Jean-Éric Pin and Pascal Weil.  A conjecture on the concatenation product.  RAIRO Informatique Théorique, 35(6):597–618, 2001.
  * [35] Thomas Place and Marc Zeitoun.  A generic polynomial time approach to separation by first-order logic without quantifier alternation.  In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022, December 18-20, 2022, IIT Madras, Chennai, India, volume 250 of LIPIcs, pages 43:1–43:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
  * [36] Thomas Place and Marc Zeitoun.  Going higher in the first-order quantifier alternation hierarchy on words.  In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, ICALP’14, pages 342–353. Springer, 2014.
  * [37] Thomas Place and Marc Zeitoun.  The covering problem.  Logical Methods in Computer Science, 14(3), 2018.
  * [38] Thomas Place and Marc Zeitoun.  Separating without any ambiguity.  In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP’18, pages 137:1–137:14, 2018.
  * [39] Thomas Place and Marc Zeitoun.  Generic results for concatenation hierarchies.  Theory of Computing Systems (ToCS), 63(4):849–901, 2019.  Selected papers from CSR’17.
  * [40] Thomas Place and Marc Zeitoun.  Going higher in first-order quantifier alternation hierarchies on words.  Journal of the ACM, 66(2):12:1–12:65, 2019.
  * [41] Thomas Place and Marc Zeitoun.  Separation and covering for group based concatenation hierarchies.  In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS’19, pages 1–13, 2019.
  * [42] Thomas Place and Marc Zeitoun.  Separation for dot-depth two.  Logical Methods in Computer Science, 17(3), 2021.
  * [43] Thomas Place and Marc Zeitoun.  All about unambiguous polynomial closure.  TheoretiCS, 2(11):1–74, 2023.
  * [44] Thomas Place and Marc Zeitoun.  Group separation strikes back.  In 38th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS’23, pages 1–13. IEEE Computer Society, 2023.
  * [45] Marcel Paul Schützenberger.  On finite monoids having only trivial subgroups.  Information and Control, 8(2):190–194, 1965.
  * [46] Imre Simon.  Hierarchies of Events of Dot-Depth One.  PhD thesis, University of Waterloo, Department of Applied Analysis and Computer Science, Waterloo, Ontario, Canada, 1972.
  * [47] Imre Simon.  Piecewise testable events.  In Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, pages 214–222. Springer, 1975.
  * [48] Larry J. Stockmeyer.  The complexity of decision problems in automata theory and logic.  PhD thesis, 1974.  PHD.
  * [49] Howard Straubing.  A generalization of the schützenberger product of finite monoids.  Theoretical Computer Science, 13(2):137–150, 1981.
  * [50] Howard Straubing.  Finite semigroup varieties of the form V * D.  Journal of Pure and Applied Algebra, 36:53–94, 1985.
  * [51] Howard Straubing.  Semigroups and languages of dot-depth 2.  In Proceedings of the 13th International Colloquium on Automata, Languages, and Programming, ICALP’86, volume 226 of Lecture Notes in Computer Science, pages 416–423. Springer, 1986.
  * [52] Howard Straubing.  Semigroups and languages of dot-depth two.  Theoretical Computer Science, 58(1):361–378, 1988.
  * [53] Howard Straubing.  Finite Automata, Formal Logic and Circuit Complexity.  Birkhauser, Basel, Switzerland, 1994.
  * [54] Howard Straubing and Denis Thérien.  Partially ordered finite monoids and a theorem of I. Simon.  Journal of Algebra, 119(2):393–399, 1988.
  * [55] Howard Straubing and Pascal Weil.  On a conjecture concerning dot-depth two languages.  Theoretical Computer Science, 104(2):161–183, 1992.
  * [56] Denis Thérien.  Classification of finite monoids: The language approach.  Theoretical Computer Science, 14(2):195–208, 1981.
  * [57] Denis Thérien.  Categories et langages de dot-depth un.  RAIRO Theor. Informatics Appl., 22(4):437–445, 1988.
  * [58] Gabriel Thierrin.  Permutation automata.  Theory of Computing Systems, 2(1):83–90, 1968.
  * [59] Wolfgang Thomas.  Classifying regular events in symbolic logic.  Journal of Computer and System Sciences, 25(3):360–376, 1982.
  * [60] Pascal Weil.  Inverse monoids and the dot-depth hierarchy.  PhD thesis, University of Nebraska, 1988.
  * [61] Pascal Weil.  Inverse monoids of dot-depth two.  Theoretical Computer Science, 66(3):233–245, 1989.
  * [62] Pascal Weil.  Some results on the dot-depth hierarchy.  Semigroup Forum, 46(1):352–370, 1993.
  * [63] Georg Zetzsche.  Separability by piecewise testable languages and downward closures beyond subwords.  In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS’18, pages 929–938, 2018.


$r(x)=\frac{\operatorname{vol}_{1}([p,x])}{\operatorname{vol}_{1}(C_{i}\cap(p+{\mathbb{R}}_{\geq
0}\cdot(x-p))}.$

This is the Minkowski functional of $C_{i}$ when $p$ is interpreted as the
origin. Let $x\in\Gamma\cap\operatorname{int}(K_{i})$. Since the lattice
length of $S$ is at least $c_{3}$, by convexity, the lattice length of the
fiber of $x$ under the projection $\pi$ is at least $c_{3}(1-r(x))$. On the
other hand, since $C_{i}$ is hollow, this fiber must not contain an interior
lattice point of ${\mathbb{Z}}^{d}$. Its lattice length is therefore bounded
by 1 from above. This gives $r(x)\geq 1-\tfrac{1}{c_{3}}$. This means that the
convex body $K_{i}^{\prime}$ obtained by scaling $K_{i}$ by a factor
$1-\tfrac{1}{c_{3}}$ around $p$ is hollow with respect to $\Gamma$ and so we
have with (A.3):

$\mathrm{Flt}(d-1)+\tfrac{1}{2}\leq\operatorname{width}_{{\mathbb{Z}}^{d}}(C_{i})=\operatorname{width}_{\Gamma}(K_{i})=\frac{\operatorname{width}_{\Gamma}(K_{i}^{\prime})}{1-\frac{1}{c_{3}}}\leq\frac{\mathrm{Flt}(d-1)}{1-\frac{1}{c_{3}}}.$

After rearranging this, we see that $c_{3}\leq 2\mathrm{Flt}(d-1)+1$, which
contradicts the choice of $c_{3}$ in (A.4). This finishes the proof. ∎


# Structural Advantages for Integrated Builders in MEV-Boost

Mallesh M. Pai${}^{\text{A}}$ ${}^{\text{A}}$Rice University and Special
Mechanisms Group and  Max Resnick${}^{\text{B}}$ ${}^{\text{B}}$Special
Mechanisms Group<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Currently, over 90% of Ethereum blocks are built using MEV-Boost, an auction
that allows validators to sell their block-building power to builders who
compete in an open English auction in each slot. Shortly after the merge, when
MEV-Boost was in its infancy, most block builders were neutral, meaning they
did not trade themselves but rather aggregated transactions from other
traders. Over time, integrated builders, operated by trading firms, began to
overtake many of the neutral builders. Outside of the integrated builder
teams, little is known about which advantages integration confers beyond
latency and how latency advantages distort on-chain trading.

This paper explores these poorly understood advantages. We make two
contributions. First, we point out that integrated builders are able to bid
truthfully in their own bundle merge and then decide how much profit to take
later in the final stages of the PBS auction when more information is
available, making the auction for them look closer to a second-price auction
while independent searchers are stuck in a first-price auction. Second, we
find that latency disadvantages convey a winner’s curse on slow bidders when
underlying values depend on a stochastic price process that change as bids are
submitted.

###### Key words and phrases:

First-price auction and Second-price auction and Latency Advantage and Common
Value Auction

We thank Davide Crapis, Julian Ma, Barnabè Monnot, Alex Nezlobin and Thomas
Thiery for helpful comments and suggestions.

##  1\. Introduction

Nominally, new Ethereum blocks are produced by ordinary validators who, having
been temporarily anointed as the proposer by the protocol, gather transactions
from the mempool (the set of publicly available transactions) and pack them
together into the most valuable block they can produce.

Choosing a random validator to be the proposer is similar to choosing a random
New Yorker to order all trades on the New York Stock Exchange for the next 12
seconds.111Ethereum builds a new block every 12 seconds so any trades that
come in in the 12 second window between blocks are ordered subject to the
discretion of the proposer. The typical New Yorker, lacking the institutional
knowledge and infrastructure required, would not be able to extract much from
his brief chronological hegemony over the exchange. On the other hand a high-
frequency trading firm does have the expertise and therefore could extract
much more from 12 seconds of chronological hegemony. This suggests a strategy
for the chosen subject: instead of trying to extract the value himself, he
should auction off the ordering rights to the highest bidder. Presumably there
are multiple competing trading firms who would be able to extract significant
value from this opportunity and so auction revenues will be high, and most of
the value from the opportunity will be captured in the form of auction revenue
and passed on to the selected pedestrian.222Indeed, one of the original
motivations for PBS, which we introduce in the subsequent paragraph, is that a
randomly chosen validator may have heterogeneous ability to extract value from
their proposal rights, leading to eventual centralization in favor of more
sophisticated validators. The existence of the auction “levels the playing
field” among validators, which was viewed as desirable. Additionally, given
the scarcity of blockspace, this was also seen as desirable from an efficiency
perspective. See Buterin (2021) for more details.

This strategy has been widely adopted by the Ethereum validator set. Today,
over 90 percent of proposers elect to outsource the building of the block by
auctioning it off to the highest bidder through MEV-Boost (Wahrstätter, Zhou,
Qin, Svetinovic, and Gervais, 2023). The bidders in this auction are called
builders. As the name suggests, builders specialize in building valuable
blocks, by any means necessary. Builders regularly expand the scope of their
block-building beyond ordering transactions in the public mempool: they secure
private order-flow, accept private bundles from MEV searchers, and even
integrate with their own trading shops.

The original conception of the PBS-auction did not involve these activities by
searchers as far as we can tell. The idealistic version of the PBS auction was
that each builder would be neutral (as the first few builders were and many
still are). But Gupta, Pai, and Resnick (2023) revealed that several builders
integrate with their own trading shops in order to more effectively capture
CEX/DEX arbitrage. These ‘HFT’ builders or integrated builders win far more
blocks when the CEX price was volatile in the time since the preceding slot
(when there was more CEX/DEX arbitrage available) relative to when the price
was stable, confirming that these builders have a significant advantage in
extracting CEX/DEX arbitrage.

But why does integration confer such a sizable advantage? One obvious answer
is that integration cuts down the communication time between the searcher and
the builder, allowing for lower-latency strategies. Certainly, this is part of
the reason that integration is important; however, it doesn’t tell the whole
story. In this paper we propose two simple models to show how the latency
advantage plays out in auction settings.

In the first, we consider a private values environment, i.e., one where the
bidders’ value for the good is not influenced by others’ signals. This is the
case, for example, if bidders’ values come purely from the associated tips of
the transactions in their block: the fact that other builders have a different
value just reflects the fact that they constructed a different block, and does
not change their value for winning the PBS auction with their own block. The
PBS auction proceeds in two phases: in the first phase, block construction,
searchers submit bundles to builders, and builders construct the blocks that
maximize their profits. In the second stage builders compete with each other
to see which of their blocks wins. Independent searchers must take profits in
the block construction phase, which means they must shade their bids (relative
to the value of the bundle/ MEV opportunity) in order to retain profit for
themselves. Since they do not know the value of the opportunities others have
found, they do not know precisely how much to shade to get included in the
next block. They instead choose a shading amount that maximizes their expected
profit, i.e. their profit upon inclusion times the probability of inclusion.
The integrated-searchers on the other hand know how much they expect to make
if their bundle lands in the first stage. They can then decide how much profit
to take during the second stage of the auction, which is an English auction.
Since the first stage occurs earlier, and is typically sealed bid, independent
searchers are acting in a pay-your-bid regime, whereas integrated searchers
are bidding in something akin to a second-price regime.

The second model considers a common-value setting. This for example is the
case for a top-of-block CEX/DEX arb (i.e., where the competition is for the
right to trading with an AMM pool on-chain, using information from a
continuous time CEX).333Such arbs are a major source of AMM liquidity provider
(LP) losses, see e.g. Milionis, Moallemi, Roughgarden, and Zhang (2022a);
Milionis, Moallemi, and Roughgarden (2023) for theoretical foundations and
Milionis, Moallemi, Roughgarden, and Zhang (2022b) for some estimates. In this
case latency advantages manifest as an information advantage, i.e. the ability
to bid later in the auction.

The basic upshot of our results is that in either case, integrated/ low-
latency bidders are advantaged. Our results therefore provide additional
reasons for the rise of integrated builders (originally documented in Gupta,
Pai, and Resnick (2023)).

##  2\. Private Values

There are $n=n_{A}+n_{B}$ builders who are builders in the PBS auction. Of
these $n_{A}$ are integrated builders and $n_{B}$ are independent/ non-
integrated builders. In this section we assume independent private values:
every integrated builder has a value that is drawn from a distribution with
CDF $F_{A}$ and density $f_{A}$, and every non-integrated builder has a value
drawn from a distribution with CDF $F_{B}$ and density $f_{B}$. All draws are
independent.

We consider the following hybrid auction:

  1. (1)

There is a single item for sale.

  2. (2)

All bidders simultaneously submit bids.

  3. (3)

The highest bidder wins the item. Payments are defined as follows:

    1. (a)

If the winner is an integrated builder, then they pay the next-highest bid.

    2. (b)

If the winner is instead an independent builder, they pay their own bid.

In short, the integrated builders compete in, what is in their view, a second-
price auction while the non-integrated builders compete in a first-price
auction.

Before we proceed let us make explicit how the model above corresponds to the
setting of interest. Suppose there are $n$ searchers. Each of these searchers
finds single profitable opportunity (for example, this could be a sandwich on
an existing transaction in the mempool). We assume that each searcher’s
opportunity is unique.444In practice multiple searchers may find the same or
related opportunities, this could be modeled as correlated instead of
independent values—we believe this would complicate the model without adding
any extra insight. Each searcher then needs to submit their opportunity to a
builder to be included. Integrated searcher-builders simply submit their
opportunity to their own integrated builder. Independent searchers submit
their opportunity to neutral builders. We assume that each independent
searcher sends to a different netural builder, in line with the simplifying
assumption made in Feldman, Mirrokni, Muthukrishnan, and Pai (2010) in the
context of Ad Exchanges.555Relaxing this assumption would lead to correlated
values among the neutral builders, which in our opinion would complicate the
model without adding any extra insight. At the stage of submitting to these
neutral builders, the independent searchers must choose how much they should
pass along as a fee to the builder, for instance in the form of a bundle tip.
A higher tip increases the chances of inclusion on the chain, but reduces the
net profit of the searcher. Subsequently, the builders bid in the PBS auction.
We assume that there are no other transactions so the block that the winning
bidder would propose is solely the opportunity from their corresponding
searcher. The value of a builder for winning a block is therefore the value of
the underlying opportunity for an integrated searcher-builder, or the
associated tip for a neutral builder. Since the PBS auction is an English
auction, the outcome is the same as a standard sealed-bid second-price
auction. From the perspective of an independent searcher, however, they have
to submit their opportunity before knowing the bidding, and therefore their
builder tip reflects a bid into a pay-your-bid auction.

So now to solve this auction.

######  Observation 1.

It is a weakly dominant strategy for integrated builders to bid their true
values in this hybrid auction, so we restrict attention to these strategies
for the integrated builder.

######  Lemma 1.

From the point of view of the non-integrated builders, the auction is
equivalent to a first-price auction of $n_{B}$ agents where there is a random,
secret reserve price distributed according to the CDF $F_{A}^{n_{A}}$.

  * Proof.

By Observation 1, integrated bidders bid their values in this hybrid auction.
Therefore the highest of these is distributed according to the CDF
$F_{A}^{n_{A}}$. Since the auction is pay-as-bid for the non-integrated
bidders, from their perspective this is a first-price auction with $n_{B}$
total bidders. However to win the object, the winning bidder also needs to be
higher than any of the integrated builders. The latter therefore act as a
secret reserve price distributed according to $F_{A}^{n_{A}}$. ∎

We can now characterize the symmetric Bayes-Nash equilibrium bidding strategy
of non-integrated buyers. Let $\sigma(\cdot)$ denote bidding strategy of the
non-integrated buyers, i.e., a bidder of value $v$ bids $\sigma(v)$. It is
immediate that $\sigma(\cdot)$ is a strictly increasing function. Then we must
have:

######  Lemma 2.

The symmetric Bayes-Nash equilibrium among non-integrated bidders
$\sigma(\cdot)$ solves:

$\displaystyle\sigma(v)=v-\frac{\int_{0}^{v}F_{B}^{n_{B}-1}(t)F_{A}^{n_{A}}(\sigma(t))dt}{F_{B}^{n_{B}-1}(v)F_{A}^{n_{A}}(\sigma(v))}.$
(1)

Figure 1. Strategies for Beta distributed private values with $N_{A}=N_{B}=3$

  * Proof.

To see this, observe that if all non-integrated bidders bid according to
$\sigma(\cdot)$, then a bidder of value $v$ wins with probability:

$\displaystyle x(v)=F_{B}^{n_{B}-1}(v)F_{A}^{n_{A}}(\sigma(v)).$

Here the first term is the probability of beating all other non-integrated
bids (since $\sigma$ is strictly increasing) and the latter is the probability
of the bid beating the secret-reserve price/ all $n_{A}$ integrated bidders’
bids.

Then by revenue equivalence (see e.g. Krishna (2009)), this bidder’s interim
expected surplus in this auction must equal

$\displaystyle S(v)=\int_{0}^{v}x(t)dt.$

However, by bidding $\sigma(v)$ in a first price auction where you win with
probability $x(v)$, the interim expected surplus must equal
$(v-\sigma(v))x(v)$.

Equating the two we have (1) as desired. ∎

###  2.1. Analytical solutions

To see analytical solutions for this let’s firstly assume that $n_{B}=1$ and
that $F_{A}$ is the uniform distribution on [0,1], i.e., $F_{A}(t)=t\iff
t\in[0,1]$. Figure 1 displays numerical results for a range of Beta-
distributions.

In this case (1) reduces to:

$\displaystyle\sigma(v)=v-\frac{\int_{0}^{v}\sigma^{n_{A}}(t)dt}{\sigma^{n_{A}}(v)}$
$\displaystyle\implies$
$\displaystyle\sigma^{n_{A}+1}(v)-v\sigma^{n_{A}}(v)+\int_{0}^{v}\sigma^{n_{A}}(t)dt=0.$
Differentiating, we have:
$\displaystyle(n_{A}+1)\sigma^{n_{A}}(v)\sigma^{\prime}(v)-n_{A}v\sigma^{n_{A}-1}(v)\sigma^{\prime}(v)=0,$
$\displaystyle\implies$
$\displaystyle\sigma^{\prime}(v)\sigma^{n_{A}-1}(v)\left((n_{A}+1)\sigma(v)-n_{A}v\right)=0$
$\displaystyle\implies$ $\displaystyle\sigma(v)=\frac{n_{A}}{n_{A}+1}v$

So in this case, we have that:

######  Proposition 1.

If there is a single non-integrated builder, it bids $\frac{n_{A}}{n_{A}+1}$
of its value in the auction. As a result its equilibrium surplus in the
auction is:

$\displaystyle
S(v)=\left(\frac{n_{A}}{n_{A}+1}\right)^{n_{A}}\frac{v^{n_{A}+1}}{n_{A}+1},$
whereas if this bidder was also integrated its surplus in the auction would be
$\displaystyle S(v)=\frac{v^{n_{A}+1}}{n_{A}+1}.$

In other words being the sole non-integrated builder costs it a fraction
$\left(\frac{n_{A}}{n_{A}+1}\right)^{n_{A}}$ of its surplus relative to if it
had been an integrated builder.

Now let’s suppose that $n_{B}=n$ for $n>1$. We’ll denote the equilibrium in
this case by $\sigma_{n}$. Assume also that $F_{B}$ is also the uniform
distribution on $[0,1]$

In this case, substituting into (1), we have that $\sigma_{n}$ is the solution
to

$\displaystyle\sigma_{n}(v)=v-\frac{\int_{0}^{v}t^{n-1}\sigma_{n}^{n_{A}}(t)dt}{v^{n-1}\sigma_{n}^{n_{A}}(v)},$
$\displaystyle\implies$ $\displaystyle
v^{n-1}\sigma_{n}^{n_{A}+1}(v)-v^{n}\sigma_{n}^{n_{A}}(v)+\int_{0}^{v}t^{n-1}\sigma_{n}^{n_{A}}(t)dt=0,$
Differentiating wrt v, we have that:
$\displaystyle(n-1)v^{n-2}\sigma_{n}^{n_{A}+1}(v)+(n_{A}+1)v^{n-1}\sigma_{n}^{n_{A}}(v)\sigma_{n}^{\prime}(v)-(n-1)v^{n-1}\sigma_{n}^{n_{A}}(v)-n_{A}v^{n}\sigma_{n}^{n_{A}-1}(v)\sigma^{\prime}_{n}(v)=0.$
Dividing throughout by $v^{n-2}$ gives us $\displaystyle\implies$
$\displaystyle(n-1)\sigma_{n}^{n_{A}+1}(v)+(n_{A}+1)v\sigma_{n}^{n_{A}}(v)\sigma_{n}^{\prime}(v)-(n-1)v\sigma_{n}^{n_{A}}(v)-n_{A}v^{2}\sigma_{n}^{n_{A}-1}(v)\sigma^{\prime}_{n}(v)=0.$
Dividing throughout by $\sigma_{n}^{n_{A}-1}$ gives us $\displaystyle\implies$
$\displaystyle(n-1)\sigma_{n}^{2}(v)+(n_{A}+1)v\sigma_{n}(v)\sigma_{n}^{\prime}(v)-(n-1)v\sigma_{n}(v)-n_{A}v^{2}\sigma^{\prime}_{n}(v)=0.$
Collecting terms we have that
$\displaystyle((n_{A}+1)v\sigma_{n}(v)-n_{A}v^{2})\sigma_{n}^{\prime}(v)=(n-1)\sigma_{n}(v)(v-\sigma_{n}(v))$
$\displaystyle\implies$
$\displaystyle\sigma_{n}^{\prime}(v)=\frac{(n-1)\sigma_{n}(v)(v-\sigma_{n}(v))}{v((n_{A}+1)\sigma_{n}(v)-n_{A}v)}$

Since $\sigma_{n}^{\prime}>0$, so that the numerator and denominator are both
positive. We can conclude that:

######  Proposition 2.

The equilibrium bids of the $n$ non-integrated bidders as a function of their
value, $\sigma_{n}(v)$, satisfies:

$\displaystyle\frac{n_{A}}{n_{A}+1}v\leq\sigma_{n}(v)\leq v.$

It follows straightforwardly, by an analogous appeal to revenue equivalence,
that each of these non-integrated bidders still has a lower expected surplus
than if they were bidding truthfully.

##  3\. Common Values

We now consider a setting where the object for sale has a common value, i.e.
the value of the object is the same regardless who eventually wins. This may
be the case if the object for sale is the top slot of a block, designated as
e.g. a CEX-DEX arb or a DeFi liquidation. The realized value would then be the
same regardless of who wins it. Such a common value model was proposed in Ma
(2023).

We consider the case of two kinds of bidders as before, fast bidders and slow
bidder. The slow bidders bid at time 0, at which time the present value of the
object is $v_{0}$. The process follows a martingale, i.e., we assume that $t$
seconds after this the process is worth $v_{t}=(\exp m_{t})v_{0}$ where
$m_{t}\sim N(\mu t,\frac{\sigma^{2}}{2}t)$ and $\mu=-\frac{\sigma^{2}}{2}.$ In
particular the latter implies that $\mathbb{E}[v_{t+\delta}|v_{t}]=v_{t}$ for
any $t,\delta\geq 0$.

###  3.1. An Unraveling Result

We first study the case where the fast bidder bids exactly $\Delta$ seconds
after the slow bidders, i.e. they have superior information. The proposition
below shows the complete unraveling of the auction.

######  Proposition 3.

In the auction described above, the slow bidders always bid 0 and the fast
bidder always wins.

  * Proof.

To see this suppose a slow bidder bids any $b>0$.

The fast bidder continues to see the evolution of the process and bids at time
$\Delta$ after the slow bidder, at which point the object is worth
$v_{\Delta}$. The fast bidder has a simple optimal strategy— if $v_{\Delta}>b$
then outbidding the slow bidder has positive expected value. If
$v_{\Delta}\leq b$ then the outbidding the slow bidder has negative expected
value.

Therefore the fast bidder should outbid the slow bidder if and only if
$v_{\Delta}>b$.

Therefore the slow bidder wins the object if and only if $v_{\Delta}\leq b$.
But in this case, the expected value of the object conditional on winning is
$\mathbb{E}[v_{\Delta}|v_{\Delta}\leq b]<b$. As a result bidding any $b>0$ has
strictly negative expected value for the slow bidder. Therefore all slow
bidders should bid 0, and be outbid with probability equal to 1 by a fast
bidder. ∎

###  3.2. The PBS Candlestick

Validators are not required to call the block exactly at the start of the slot
(Schwarz-Schilling, Saleh, Thiery, Pan, Shah, and Monnot, 2023), network
delays are never a certainty, and clock synchronization can vary between
validators. What this means is that, in practice, a speed advantage may not
manifest itself deterministically. A slow bidder may simply have fewer
opportunities to update their bid in the PBS auction (as a result of their
speed, or lack thereof). We model this as a candlestick auction.666A
candlestick auction is one where bids are accepted until a (real-world) candle
runs out, or some other stochastic process terminates. This was intended to
ensure that no one could know exactly when the auction would end and make a
last-second bid. See https://en.wikipedia.org/wiki/Candle_auction for further
details.

To capture the speed advantage of the fast bidder, we consider the following
simplified model:

  1. (1)

The slow bidders submit sealed bids at time $0$.

  2. (2)

The fast bidder has an option to bid at time $\Delta$ with probability
$p\in[0,1]$.

We assume there are at least two slow bidders.777If there is a single slow
bidder, then the optimal strategy for them is trivially to bid $0$ and win the
auction only when the fast bidder does not have a revision opportunity.

This model is a simplified version of a “revision game” as originally proposed
in Kamada and Kandori (2020). Slow bidders can submit a first bid, but then
the fast bidder has a stochastic opportunity to revise their bid, while the
slow bidder does not have such an opportunity. The parameter $p$ therefore
captures the “speed” of the fast bidder, i.e., a higher $p$ corresponds to a
bidder who can respond more often to the slow bidder’s bid even if they get
outbid initially. Intuitively $p=0$ corresponds to a standard sealed-bid
common value auction (which in this case will conclude at price $v_{0}$),
while $p=1$ corresponds to the unraveling case above. A more general model
where slow bidders have stochastically fewer revision opportunities than fast
bidders is left to future work.

######  Proposition 4.

The winning slow bidder in the period 0 auction bids the largest
$b_{0}^{S}\in[0,v_{0}]$ solving:

$\displaystyle(1-p)(v_{0}-b_{0}^{S})+pP(v_{\Delta}<b_{0}^{S})(E(v_{\Delta}|v_{\Delta}<b_{0}^{S})-b_{0}^{S})=0.$
(2)

They win the item with probability $pP(v_{\Delta}<b_{0}^{S})+(1-p).$

  * Proof.

Let us denote the winning slow bidder’s bid bid $b_{0}^{S}$.

The fast-bidder’s move in the subgame after the period $0$ auction _if they
get a revision opportunity_ is straightforward: whenever the current value at
time $\Delta$, $v_{\Delta}>b_{0}^{S}$ then the fast-bidder updates their bid
to $b_{0}^{S}$. If instead $v_{\Delta}<b_{0}^{S}$, then they choose lose the
auction (i.e. let the slow bidder win despite having a a revision
opportunity).

Therefore, at time $0$, the slow bidder understands that if they have the
higher bid at time $0$, there are two possibilities:

    1. (1)

They lose money whenever the fast bidder gets an opportunity to update their
bid. In particular, in expectation, their net expected profit in this case is:

$\displaystyle
P(v_{\Delta}<b_{0}^{S})(E(v_{\Delta}|v_{\Delta}<b_{0}^{S})-b_{0}^{S})$

    2. (2)

If the fast bidder does not get an opportunity to update their bid, the slow
bidder’s expected profit in this case is:

$\displaystyle(v_{0}-b_{0}^{S}).$

Note that by assumption the probability of the latter event is $1-p$ and the
former is $p$. Consider the solution to:

$\displaystyle(1-p)(v_{0}-b_{0}^{S})+pP(v_{\Delta}<b_{0}^{S})(E(v_{\Delta}|v_{\Delta}<b_{0}^{S})-b_{0}^{S})=0.$
(3)

Note that the left hand side is strictly positive at $b_{0}^{S}=0$ and
strictly negative at $b_{0}^{S}=v_{0}$, which implies that there exists at
least one solution by the intermediate value theorem. The largest solution to
this is the largest amount a slow bidder can bid without losing money.

We claim that any equilibrium must involve at least one slow bidder bidding
the largest $b_{0}^{S}$ solving (2) in period $0$. To see why note that the
since the slow bidders are symmetric they must have 0 profit in equilibrium.
Now suppose the winning bid is something other than the largest root. Since
the left hand side is positive at $b_{0}^{S}=0$ and negative at
$b_{0}^{S}=v_{0}$, by continuity, if there are multiple roots and the winning
slow bidder’s bid is one of the smaller roots, then there exists a larger bid
such that the left hand side of (2) evaluates to strictly positive, so this
cannot be an equilibrium. ∎

Therefore, stochastic opportunities for the fast bidder to outbid the slow
bidder lessens the adverse selection faced by the latter, and therefore allow
for positive bids and positive probability of winning for the fast bidder.

##  4\. Conclusion

As has been documented in multiple venues, the builder market in Ethereum
increasingly favors integrated builder-searchers. A priori, one might think
that there is no reason for searchers to integrate with builders, and indeed
that competitive searchers might be better served focusing on searching and
simply letting builders compete for their orders. While it is understood that
integration confers and advantage to integrated builders relative to non-
integrated builders, little is understood about exactly how. This paper sheds
a first light on how latency advantages play out in an auction setting, both
in the case of private value and common values. We leave to future work
quantifying the source of the advantage, i.e., additional time to construct
blocks etc versus advantages in the auction.

## References

  * (1)
  * Buterin (2021) Buterin, V. (2021): “Proposer/block builder separation-friendly fee market designs,” https://ethresear.ch/t/proposer-block-builder-separation-friendly-fee-market-designs/9725/4.
  * Feldman, Mirrokni, Muthukrishnan, and Pai (2010) Feldman, J., V. Mirrokni, S. Muthukrishnan, and M. M. Pai (2010): “Auctions with intermediaries,” in _Proceedings of the 11th ACM conference on Electronic commerce_ , pp. 23–32.
  * Gupta, Pai, and Resnick (2023) Gupta, T., M. M. Pai, and M. Resnick (2023): “The centralizing effects of private order flow on proposer-builder separation,” .
  * Kamada and Kandori (2020) Kamada, Y., and M. Kandori (2020): “Revision games,” _Econometrica_ , 88(4), 1599–1630.
  * Krishna (2009) Krishna, V. (2009): _Auction theory_. Academic press.
  * Ma (2023) Ma, J. (2023): “A Dynamic Auction Model for PBS,” in _MEV workshop SBC_.
  * Milionis, Moallemi, and Roughgarden (2023) Milionis, J., C. C. Moallemi, and T. Roughgarden (2023): “Automated Market Making and Arbitrage Profits in the Presence of Fees,” _arXiv preprint arXiv:2305.14604_.
  * Milionis, Moallemi, Roughgarden, and Zhang (2022a) Milionis, J., C. C. Moallemi, T. Roughgarden, and A. L. Zhang (2022a): “Automated market making and loss-versus-rebalancing,” _arXiv preprint arXiv:2208.06046_.
  * Milionis, Moallemi, Roughgarden, and Zhang (2022b) (2022b): “Quantifying loss in automated market makers,” in _Proceedings of the 2022 ACM CCS Workshop on Decentralized Finance and Security_ , pp. 71–74.
  * Schwarz-Schilling, Saleh, Thiery, Pan, Shah, and Monnot (2023) Schwarz-Schilling, C., F. Saleh, T. Thiery, J. Pan, N. Shah, and B. Monnot (2023): “Time is Money: Strategic Timing Games in Proof-of-Stake Protocols,” .
  * Wahrstätter, Zhou, Qin, Svetinovic, and Gervais (2023) Wahrstätter, A., L. Zhou, K. Qin, D. Svetinovic, and A. Gervais (2023): “Time to Bribe: Measuring Block Construction Market,” _arXiv preprint arXiv:2305.16468_.