Chains of Preorders
26 Aug 2022
Joshua Moerman
In this post, I show how long a chain of refinements of preorders can be:
$β€_{1}ββ€_{2}ββ―ββ€_{k}$Here, each $β€_{i}$ is a preorder on some fixed set. The number $k$ (of the longest chain possible) is what I am after.
This problem came up when I wanted to analyse the query complexity of the NL* algorithm by Bollig et al myself. NL* is a automata learning algorithm for nondeterministic automata. Simplifying a lot: this algorithm has an βouter loopβ that refines a certain preorder. The number of iterations of this loop is bounded by how often a preorder can be refined. So how long can a chain of preorders be?
Preorders and refinement
We start with a set $X$. A preorder is a relation $β€$ such that:
 The relation is reflexive: $xβ€x$ for all $x$, and
 The relation is transitive: $xβ€y$ and $yβ€z$ implies $xβ€z$ for all $x,y,z$.
Given two such relations $β€_{1}$ and $β€_{2}$, we say that $β€_{2}$ is (strictly) finer than $β€_{1}$ if $β€_{2}ββ€_{1}$. In words: the relation $β€_{2}$ relates fewer elements than $β€_{1}$.
The coarsest preorder is the relation where everything is related, i.e., $β€=XΓX$. On the other extreme, we have the finest relation $β€={(x,x)β£xβX}$. In the finest relation nothing is related (except each element $x$ with itself). I will use this diagonal set later on, so I introduce the notation $Ξ(X)={(x,x)β£xβX}$.
The NL* algorithm starts with the coarsest relation, assuming that everything (states of an automaton) is equal. Only when observations show that the elements must be different, the algorithm refines that relation. Say $X$ has $n$ elements. Clearly the number of times it can be refined is bounded by $n_{2}$, as the coarsest relation has only $n_{2}$ elements. A slightly better bound is $n_{2}βn$, because we know the last relation has to be reflexive. Can we exactly compute how often we can refine the relation, also taking into account transitivity?
Examples
Letβs compute some examples by hand.

$n=1$: In this case there is only one element, and only one preorder. So the length of the longest chain is 1.

$n=2$: In this case, there are four preorders. And we can chain three of them as follows:
${(1,1),(1,2),(2,1),(2,2)}β{(1,1),(1,2),(2,2)}β{(1,1),(2,2)}.$There is another chain of length 3 where we choose to include $(2,1)$ instead of $(1,2)$. The length of the longest chain is 3.

$n=3$: This is a bit more involved. I will add a figure to show a chain of length 6 later.
I wanted to find a pattern in these numbers, so I wrote a bruteforce program to enumerate all possibilities. Doing so, I got the sequence 1, 3, 6, 10 and 15. Do you recognise these numbers?
The triangular numbers
I didnβt, but luckily oeis does! These numbers are exactly the triangular numbers. But whyβ½
This puzzled me and so I asked around. Together with Todd Schmid, we found an inductive proof of why the triangular numbers show up here. Below, I will show the main construction.
Proof
Let $len(X)$ denote the length of the longest preorder chain on the set $X$. I will show that
$len(X+Y)=β£XΓYβ£+len(X)+len(Y).$Here, $+$ is the disjoint union of sets, $Γ$ the cartesian product of sets and $β£(β)β£$ the cardinality of a set. As a special case, we may take $Y={β}$ to be a singleton and retrieve an inductive proof that $len({1,β¦,n})=T_{n}$.
For the main construction to show the above formula, I find it easier to think about going from the finest relation to the coarsest. We have our sets $X$ and $Y$ and we imagine that $X$ will be smaller than $Y$ during the whole construction, this is without loss of generality. We start with the finest relation and add pairs $(x,y)βXΓY$ onebyone (in any order). This results in a chain of length $β£XΓYβ£+1$:
$Ξ(X+Y)βΞ(X+Y)βͺ{(x,y)}ββ―βΞ(X+Y)βͺXΓY$Note that we donβt have to care about transitivity here: each $x$ is below $y$, but nothing is below $x$ or above $y$.
We continue this chain by using the longest chain for $X$. Again, we donβt have to take action for transitivity: we might introduce a relation $x_{1}β€x_{2}$ and already have $x_{2}β€y,$ but every $x$ is already related to $y$ at this point in the chain, so $x_{1}β€y$ holds. After the chain for $X$, we glue on the chain for $Y$ (again no special care for transitivity is needed).
So far we have constructed three chains, but we havenβt arrived at the coarsest relation yet. To do so, we may add any element $(y,x)$, and this forces (by transitivity) to include all pairs $YΓX$. And so, we can make one more step in this chain.
Carefully glueing each chain together (the endpoints are equal and shouldnβt be counted twice), we obtain the length
$β£XΓYβ£+len(X)+len(Y)$as required.
Note that the above chain cannot be made any longer. In the first part, we add single elements, which cannot be done any better. Then, inductively, we assume the longest chains for $X$ and $Y$. And then, we are forced to the coarsest relation by adding any element.
This does not yet mean that this is the longest chain. (It is a local optimum, not a global one.) Some more thinking is required to convince yourself that there is no longer chain. To be honest, I donβt know a good argument for that.
Quadratic length
We now know the exact number of refinements possible (using only the assumptions of a preorder):
$len({1,β¦,n})=T_{n}=2n(n+1)β$Unfortunately this precise bound is still quadratic, just as our lazy bound of $n_{2}$ was. (Although the bounds is roughly half of the lazy bound.)
This is different if we go to equivalence relations. For equivalence relations, the longest chain of refinements is linear! This is because each equivalence relation corresponds to a partition. And so a chain of refinements corresponds to a chain of surjections
$XβX_{2}ββ―βX_{k}$Each surjection at best reduces the number of elements by 1. So starting with $n$, we can only reduce the size $nβ1$ times, resulting in a chain of length $n$.
For nominal sets
I wanted to know the precise bound in the context of automata learning of nondeterministic nominal automata. Our current bound (based on the lazy $n_{2}$) was too high for my taste. Unfortunately, the exact bound is still high (asymptotically still quadratic). The formula
$len(X)=β£XΓYβ£+len(X)+len(Y)$also holds for nominal sets, I believe. Here you should read $β£XΓYβ£$ as the number of orbits of the product $XΓY$, which can be quite big.
As a base case, we have the single orbit sets $A_{(k)}$ (the set of $k$tuples of distinct atoms). I conjecture that
$len(A_{(k)})=k+1$As an example, $A$ has length 2 because $Ξ(A)βA_{2}$. There is no longer chain, since $A_{2}$ only has two orbits.
Conclusion
There is not much more to say. I do really like relating bounds of algorithms to a chains of mathematical objects. In this case I considered chains of preorders to obtain a bounds of a learning algorithms. Doing so, I tightened a $n_{2}$ bound to the triangular numbers $T_{n}$.
Again thanks to Todd and his partner to help me with the proof. I posted this problem on a slack channel of a research group and, as I understand it, they had fun solving this problem during a dinner in London! Thanks!