Chains of Preorders

26 Aug 2022
Joshua Moerman

In this post, I show how long a chain of refinements of preorders can be:

\leq_{1} ⊋ \leq_{2} ⊋ \dots ⊋ \leq_{k}

Here, each $\leq_{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?

We start with a set $X$ . A preorder is a relation $\leq$ such that:

The relation is reflexive: $x \leq x$ for all $x$ , and
The relation is transitive: $x \leq y$ and $y \leq z$ implies $x \leq z$ for all $x, y, z$ .

Given two such relations $\leq_{1}$ and $\leq_{2}$ , we say that $\leq_{2}$ is (strictly) finer than $\leq_{1}$ if $\leq_{2} ⊊ \leq_{1}$ . In words: the relation $\leq_{2}$ relates fewer elements than $\leq_{1}$ .

The coarsest preorder is the relation where everything is related, i.e., $\leq = X \times X$ . On the other extreme, we have the finest relation $\leq = {(x, x) ∣ x \in 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 \in 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 brute-force 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 \times Y ∣ + len (X) + len (Y) .

Here, $+$ is the disjoint union of sets, $\times$ 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, \dots, 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) \in X \times Y$ one-by-one (in any order). This results in a chain of length $∣ X \times Y ∣ + 1$ :

Δ (X + Y) ⊋ Δ (X + Y) \cup {(x, y)} ⊋ \dots ⊋ Δ (X + Y) \cup X \times 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} \leq x_{2}$ and already have $x_{2} \leq y,$ but every $x$ is already related to $y$ at this point in the chain, so $x_{1} \leq 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 \times X$ . And so, we can make one more step in this chain.

Carefully glueing each chain together (the end-points are equal and shouldn’t be counted twice), we obtain the length

∣ X \times 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, \dots, n}) = T_{n} = \frac{n ( n + 1 )}{2}

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} ↠ \dots ↠ 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 \times Y ∣ + len (X) + len (Y)

also holds for nominal sets, I believe. Here you should read $∣ X \times Y ∣$ as the number of orbits of the product $X \times 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}$ .