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*, 1983.

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

veryloose: if my calculations are correct, the sequence $C_{n,2}$ starts with $1,4,16,68,312,1560,\ldots$ – Alessandro De Luca Jun 26 '13 at 21:02