congruence on words: having the same (scattered) subwords of length at most n 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.
 A: A bound is given in the paper
On the word problem for syntactic monoids of piecewise testable languages, 
by K. Kátai-Urbán, P.P. Pach,  G. Pluhár, A. Pongrácz and C. Szabó.
See Prop. 5.1: $\log C_{n,k}=\Theta(k^{(n+1)/2})$ if $n$ is odd, and $\log C_{n,k} = \Theta(k^{n/2} \log k)$, if $n$ is even.
A: 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)}$.
