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?



What is the relation between the number syntactic congruence classes, and the number of Nerode relation classes?
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$.


