Number of equivalence classes in regular languages as a function of DFA size This question is related to a recent
question
by Janoma.
Background
In constraint programming, a regular global constraint $c$ over a
domain $D$ is a pair $(s, M)$ with $s$ a tuple of variables (the
scope) and $M$ a DFA over the domain $D$. An assignment $\theta$ to
$s$ satisfies $c$ if $M$ accepts the string
$\theta(s_1)\theta(s_2)\ldots\theta(s_n)$.
Below, assume that the domain $D$ is fixed. Define an equivalence
relation $\sim$ over the set of strings $T = D^{|s|}$ such that $a
\sim b$ if for every DFA $M$ either $a, b \in L(M)$ or $a, b \not\in
L(M)$. Intuitively, two strings are equivalent iff no DFA can
distinguish them. If that is true, then they also satisfy the same
regular constraints.
If we do not restrict the DFAs in any way, then the set of equivalence
classes $T/{\sim}$ is just $T$ itself. I am interested in the number of
equivalence classes wrt. $\sim$ as a function of the number of states $n$
that we allow for the DFA. Clearly, if $n = |D|^{|s|}$ (ignore
constants) then $|T/{\sim}| = |T|$. (Of course, $n$ here will itself be a
function of $|s|$.)
Questions

What is the smallest $n$ for which $|T/{\sim}| = |T|$?
What happens below that? In particular,

is there an $n$ such that $|T/{\sim}| = O(|s|^{|D|})$?
is there an $n$ such that $|T/{\sim}| = O(|s| \times |D|)$?



My motivation for this question is that having a polynomial
($|s|^{|D|}$) number of equivalence classes like this gave me a
tractable case of constraint problems with cardinality constraints. I
am now trying to see if something along these lines can be done for
the regular constraint.
Edit: Note also this answer by Hermann Gruber to the question referenced at the top. The bounds in the paper the answer links should yield a $k$ such that the answer to question 1 must be $\geq k$, but it is not obvious to me.
Answer to Question 1,


  What is the smallest $n$ for which $|T/{\sim}|=|T|$?


We have $$n=\max_{|w|=|x|=s,\\ w\ne x}\mathrm{sep}(w,x)$$
where $\mathrm{sep}(w,x)$ is the smallest number of states in any DFA that accepts one of $w$ and $x$, but not the other.
The best known upper bound on $n$ is then (see some slides by Jeffrey Shallit)


  $n=O(s^{2/5}(\log s)^{3/5})$.


which was obtained in

Robson, J. M., Separating strings with small automata, Inf. Process. Lett. 30, No. 4, 209-214 (1989). ZBL0666.68051.