For a fixed finite alphabet $A=\{a,b,...\}$, write $x \sim\_n y$ if the two words $x$ and $y$ have the same (scattered) subwords of length at most $n$. The relation $\sim\_n$ is a congruence of finite index and [SS83] asks what is the number of congruence classes. Has there been any progress on this question? I cannot find any recent paper mentioning it.


Write $k=\mid A\mid$ for the cardinal of $A$. Since two different words of length at most $n$ cannot be congruent, there must be at least $\mid A^{\leq n}\mid=k^n+k^{n-1}+\cdots+1=\frac{k^{n+1}-1}{k-1}$ congruence classes. And since each class is characterized by a subset of $A^{\leq n}$, there are less than $2^{\mid A^{\leq n}\mid}\leq 2^{k^{n+1}}$ congruence classes. 


For $n=1$, $\sim\_1$ means "same set of occurring letters" and obviously there are $2^k$ congruence classes.
But observe that, for $n>1$, not all subsets of $A^{\leq n}$ are realizable sets of subwords. E.g., if $x$ has $aa$ and $bb$ as subwords of length $n=2$, it must also have $ab$ or $ba$ (at least one of them).


There is a very large gap between the obvious lower and upper bounds given above. Can we narrow it? The question I am interested in is **for fixed $k$ and as a function of $n$, is the number of classes simply exponential or doubly exponential? (or something else?)**


**Added June 17th:** 
Write $C\_{n,k}$ for the number of classes. I did some computations for $k=3$, i.e., when $A=\{a,b,c\}$ has three letters: 
\[ 
C\_{0,3}=1, \quad 
C\_{1,3}=8, \quad 
C\_{2,3}=152, \quad
C\_{3,3}=5312, \quad
C\_{4,3}=334202.
\]
This leaves me perplexed. Much bigger than $k^n$ but much smaller than $2^{k^n}$.


**Added June 26th:** 
For $k=2$, $C\_{n,2}$ can be bounded by $2^{2n^2+1}$, hence is "simply" exponential. Indeed, when $A=\{a,b\}$, a *shortest witness* for a congruence class does not have $n+1$ consecutive $a$'s (or $b$'s) and does not alternate more than $2n$ times between $a$'s and $b$'s. Hence each congruence class has a witness of length $\leq 2n^2$.


**References:**
[SS83] J. Sakarovitch and I. Simon's. "Subwords", chapter 6 in M. Lothaire's [*Combinatorics on words*](http://www-igm.univ-mlv.fr/~berstel/Lothaire/), 1983.


**Acknowledgments:**
Jean-Éric Pin pointed me to the [SS83] ref for the open question.



congruence on words: having the same (scattered) subwords of length at most n
I could generalize my earlier proof for the $k=2$ case and show that, for any fixed $k$, $C\_{n,k}$ is in $2^{O(n^k)}$ hence simply exponential.


When some given $n$ is understood, we say that $x\in A^\*$ is *minimal*
if $x$ has minimal length inside its $\sim\_n$-class. Since $\sim\_n$ is a
congruence, all factors of a minimal $x$ are themselves minimal.


For a fixed $k$-letter alphabet $A$, write $l\_{n,k}$ for the
length of the longest minimal word wrt $\sim\_n$. Thus
$C\_{n,k}\leq k^{l\_{n,k}+1}$ since every congruence class has a
minimal representative.


A word $x\in A^\*$ is *rich* if each letter of $A$
occurs at least once in $x$, otherwise $x$ is *poor*. A minimal poor word has length $\leq l\_{n,k-1}$ since at least one letter is not used. 


We decompose a word $x$ under the form $x=r\_1 \cdots r\_m\cdot x'$
where $r\_1$ is the shortest rich prefix of $x$, $r\_2$ is the
shortest rich prefix of the rest, etc., until there only
remains a poor suffix $x'$. 
E.g., assuming $k=3$, $x=bbaaabbccccaabbbaa$
is written $x=bbaaabbc\cdot cccaab \cdot bbaa$.
Also, if $x$ is poor then
$m=0$ and $x'=x$.


Assume now that $x$ is minimal. Then $\mid{x'}\mid\leq l\_{n,k-1}$
since $x'$ is poor. Also, for any $i=1,\ldots,m$,
$\mid{r\_i}\mid\leq 1+l\_{n,k-1}$, since $r\_i$ minus its last
letter is not yet rich. If now $m\geq n$ then
$x$ already has all possible subwords (so
$\mid{x}\mid=kn$ if $x$ is minimal). Otherwise $m<n$ and
$\mid{x}\mid\leq n\cdot l\_{n,k-1}+n-1$. We deduce
$l\_{n,k}\leq \max(kn,n\cdot l\_{n,k-1}+n-1)$.
Since $l\_{n,1}=n$ we see that $l\_{n,k}<
n^k+n^{k-1}+\cdots+n+1$. Hence for fixed $k$, $C\_{n,k}$ is in
$2^{O(n^k)}$.


