The polynomial languages and ordered syntactic monoids

Question

A polynomial language is a languge which could be represented as the finite union of languages of the form: $$ A_0^* a_1 A_1^* a_2 \cdots a_k A_k^* \quad a_i \in X, A_i \subseteq X $$ Such an expression is called a monom and it's degree is the value $k$. Equivalently it could be defined as the smallest class containing the finite languages, languages of the form $A^*$ for $A \subseteq X$ and closed under union and concatentation.

The degree of a polynomial language is the maximum degree of the monoms in a minimal (with regard to the degree) representation of the polynomial language in the form of unions of monoms.

An ordered monoid $(M, \le)$ is a monoid $M$ together with a partial order which is compatible with multiplication. A set $D$ is called downward closed if $p \in D$ and $q \le p$ implies $q \in D$. An ordered monoid recognized a language $L$ via a morphism $\varphi : X^* \to M$ if $$ L = \varphi{-1}(\downarrow\varphi(L)) $$ where $\downarrow D$ denotes the smallest downward closed subset containing $D$.

For the syntactic monoid $Syn(L)$ there is a natural order given by $u \le_L v$ iff $$ \forall p,q \in X^* : pvq \in L \Rightarrow puq \in L. $$ Then for $[u], [v] \in Syn(L)$ it is $[u] \le [v] :\Leftrightarrow u \le_L v$.

Let us consider a polynomial language $L$ of degree $k$ and words $u,v$ with $\mbox{alph}(v) \subseteq \mbox{alph}(u)$. Then for all $p,q$ we have $pu^{k+1} q \in L$ implies that $pu^kv u^k q\in L$, too. Thus, the syntactic orderd monoid of $L$ satisfied an equation of type $u^{\pi}vu^{\pi} \le_L u^{\pi}$

Remark: $u^{\pi}$ denotes the unique idempotent associated with $u$, for example $\pi = n!$ where $n$ is the size of the finite monoid.

The shaded paragraph I do not understand, the relation $$ pu^{k+1}q \in L \Rightarrow pu^k vu^k q \in L $$ for $\mbox{alph}(v) \subseteq \mbox{alph}(u)$ and $k$ the degree of the polynomial is clear cause a monom of degree $k$ can "fix" just $k$ letters, and so some $u$ lies in some $A_i^* \subseteq X^*$ and so also $v$. But why does this order relation for the syntactic monoid follows? Is there any simple relation between the idempotent powers and the degree I do not see?

Answer 1

The relation $pu^{k+1}q\in L\Rightarrow pu^k vu^kq\in L$ is true for any $p,q$, $k$ big enough and $v$ with $alph(v)\subseteq alph(u)$.

Let call $a$ the first letter of $u$ and $b$ the last letter. Let $v$ with $alph(v)\subseteq alph(u)$, and $v'=uvu$.

Then by using the relation above with $v'$, we get that for any $p,q$ and $k$ big enough, we have $pu^{k}q\in L\Rightarrow pu^k vu^kq\in L$, which is the definition of $u^kvu^k\leq_L u^k$. In particular, for $n$ big enough, we get $u^{n!}vu^{n!}\leq_L u^{n!}$, which is the wanted equation.