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.