What is the relation between the number syntactic congruence classes, and the number of Nerode relation classes?

Question

For a monoid $M$ and a subset $S$ of $M$, define the syntactic congruence $\equiv_S$ of $S$ as the least congruence on $M$ that saturates $S$, i.e. : $$u \equiv_S v \Leftrightarrow (\forall x, y)[xuy \in S \leftrightarrow xvy \in S].$$

Now define the Nerode equivalence as the following right congruence : $$u \sim_S v \Leftrightarrow (\forall x)[ux \in S \leftrightarrow vx \in S].$$

Let $[u]_\equiv$ be the equivalence class of $u$ with respect to $\equiv_S$ and $[u]_\sim$ with respect to $\sim_S$.

Now define $i_\equiv (n)$ to be the number of different $[u]_\equiv$ for $u$ of size $n$.

Define $i_\sim(n)$ in a similar fashion.

Now the question is, how do the two $i$ functions relate ?

For instance, a standard theorem says that $i_\sim(n)$ is bounded by a constant whenever $i_\equiv(n)$ is, and reciprocally. Is there any other result in this trend?

Answer 1

Let $L$ be a regular language. Then the index of the Nerode equivalence of $L$ is the number of states $n$ of its minimal automaton and the index its syntactic congruence is the size $N$ of its syntactic monoid.

It is well known that $N \leqslant n^n$ and that this bound can be reached on a three-letter alphabet. I will now slightly modify this construction to show that, for each $n$, there is a language $L_n$ on a four-letter alphabet $\{a, b, c, d\}$ such that, for $k$ large enough, $i_\sim(k) = n$ and $i_\equiv(k) = n^n$.

Consider $a, b, c, d$ as transformations on $\{1, ..., n\}$: $a$ is the cyclic permutation, $b$ is a transposition, say $(2, 1)$, $c$ maps every state $\not= n$ to itself, but maps $n$ to $1$. Finally $d$ is the identity. This defines a deterministic automaton $\mathcal{A}$, with $1$ as the initial and unique final state. Let $L_n$ be the language recognized by this automaton. Now, for $k \geqslant n$, the words $d^{k-j}a^j$ have the same length $k$ and define $n$ distinct $\sim$-classes, since $1 \cdot d^{k-j}a^j = j$ in $\mathcal{A}$. Thus $i_\sim(k) = n$ for $k \geqslant n$.

Now, it is known that the transformation monoid generated by $\{a, b, c\}$ is the full transformation monoid $\mathcal{T}_n$, which has $n^n$ elements. For each $s \in \mathcal{T}_n$, let $u_s$ be a shortest word representing $s$ and let $R = \max \{ |u_s| \mid s \in \mathcal{T}_n\}$ (an obvious upper-bound for $R$ is $n^n$). Now, for $k \geqslant R$, the $n^n$ words $d^{k-|u_s|}u_s$ (for $s \in \mathcal{T}_n$) have the same length $k$ and define distinct elements of $\mathcal{T}_n$. Therefore $i_\equiv(k) = n^n$ for $k \geqslant R$.

Answer 2

Since you are talking about size of monoid elements, I assume you want a finitely geerated monoid and wish to use word length for size.

Since ${\equiv}\subseteq {\sim}$ trivially one has $i_{\sim}(n)\leq i_{\equiv}(n)$. I believe that in the other direction no good bounds hold. For instance let $G$ be the Grigorchuk group and let $P$ be a parabolic subgroup with respect to a generic boundary point of the 2-ary tree. Then the minimal automaton for $P$ is the Schreier graph for $G/P$, which is known to be infinte with polynomial growth. On the other hand $G$ is just infinite so $G$ is the syntactic monoid of $P$. $G$ is known to have intermediate growth. Thus the syntactic congruence for $P$ has many more classes in a strong sense than the Nerode congruence.