# 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.

-
I think this is still open. – Benjamin Steinberg Jun 11 '13 at 13:45
So anagrams in general are 1-related but not 2-related? Gerhard "Likes The Phrase Anagram Sheperd" Paseman, 2013.06.11 – Gerhard Paseman Jun 11 '13 at 22:55
For words of length at least $n$ the counts for subwords of length exactly $n$ give all the information about shorter words. So there are $k^n+k^{n-1}+\cdots+k+1$ classes for "short" words and all but $k$ have a unique member. The exceptions are for the long single letter words.. – Aaron Meyerowitz Jun 16 '13 at 3:07
The bound given for $k=2$ is still very loose: if my calculations are correct, the sequence $C_{n,2}$ starts with $1,4,16,68,312,1560,\ldots$ – Ale De Luca Jun 26 '13 at 21:02
Thanks for the calculations. My $C_{n,2}$ values agree and go on with ..,1560,8528,50864,... so we can confirm one another's code. I agree that the upper bound is loose. However, my question is, for fixed $k$, whether $C_{n,k}$ is simply or doubly exponential in $n$. This is now answered for $k=2$. – phs Jun 26 '13 at 21:09

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.

-
Thanks for pointing to this recent paper! Very interesting. The way I see it, it does not exactly answer my question since it fixes $n$ and let $k$ vary. In particular, the multiplicative constants implicit in the $\Theta(..)$ notation of Prop. 5.1 are different for each value of $n$. – phs Jun 29 '13 at 10:13

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)}$.

-
A more detailed analysis by P. Karandikar and myself is now available at arxiv: 1310.1278. It shows the $2^{O(n^k)}$ upper bound for $C_{n,k}$ and a new $2^{\Omega(n^{k-1})}$ lower bound. The comments we received here were a great help and motivation. Thanks to all. – phs Oct 7 '13 at 4:05
After one year, and with some outside help, we improved this to a "tight" $2^{\Theta(n^{k-1}\log n)}$ asymptotic value. See last version of arxiv: 1310.1278. – phs Oct 12 '14 at 20:08