16
$\begingroup$

The Catalan numbers $C_n$ count both

  1. the Dyck paths of length $2n$, and
  2. the ways to associate $n$ repeated applications of a binary operation.

We call the latter magma expressions; we will explain below.

Dyck paths, and their lattice structure

A Dyck path of length $2n$ is a sequence of $n$ up-and-right strokes and $n$ down-and-right strokes, all having equal length, such that the sequence begins and ends on the same horizontal line and never passes below it. A picture of the five length-6 Dyck paths is shown here:

A:          B:          C:          D:          E:
    /\
   /  \        /\/\        /\            /\
  /    \      /    \      /  \/\      /\/  \      /\/\/\

There is an order relation on the set of length-$2n$ Dyck paths: $P\leq Q$ if $P$ fits completely under $Q$; I'll call it the height order, though in the title of the post, I called it "Dyck order". I've been told it should be called the Stanley lattice order. For $n=3$ it gives the following lattice:

   A
   |
   B
  / \
 C   D
  \ /
   E

For any $n$, one obtains a poset structure on the set of length-$2n$ Dyck paths using height order, and in fact this poset is always a Heyting algebra (it represents the subobject classifier for the topos of presheaves on the twisted arrow category of $\mathbb{N}$, the free monoid on one generator; see this mathoverflow question).

Magma expressions and the "exponential evaluation order"

A set with a binary operation, say •, is called a magma. By a magma expression of length $n$, we mean a way to associate $n$ repeated applications of the operation. Here are the five magma expressions of length 3:

A:            B:             C:             D:             E:
  a•(b•(c•d))   a•((b•c)•d)    (a•b)•(c•d)    (a•(b•c))•d    ((a•b)•c)•d

It is well-known that the set of length-$n$ magma expressions has the same cardinality as the set of length-$2n$ Dyck paths: they are representations of the $n$th Catalan number.

An ordered magma is a magma whose underlying set is equipped with a partial order, and whose operation preserves the order in both variables. Given an ordered magma $(A,$•$,\leq)$, and magma expressions $E(a_1,\ldots,a_n)$ and $F(a_1,\ldots,a_n)$, write $E\leq F$ if the inequality holds for every choice of $a_1,\ldots,a_n\in A$. Call this the evaluation order.

Let $P=\mathbb{N}_{\geq 2}$ be the set of natural numbers with cardinality at least 2, the logarithmically positive natural numbers. This is an ordered magma, using the usual $\leq$-order, because if $2\leq a\leq b$ and $2\leq c\leq d$ then $a^c\leq b^d$.

Question: Is the exponential evaluation order on length-$n$ expressions in the ordered magma $(P,$^$,\leq)$ isomorphic to the height order on length-$2n$ Dyck paths?

I know of no a priori reason to think the answer to the above question should be affirmative. A categorical approach might be to think of the elements of $P$ as sets with two special elements, and use them to define injective functions between Hom-sets, e.g. a map $$\mathsf{Hom}(c,\mathsf{Hom}(b,a))\to\mathsf{Hom}(\mathsf{Hom}(c,b),a).$$ However, while I can define the above map, I'm not sure how to generalize it. And the converse, that being comparable in the exponential evaluation order means that one can define a single injective map between hom-sets, is not obvious to me at all.

However, despite the fact that I don't know where to look for a proof, I do have evidence to present in favor of an affirmative answer to the above question.

Evidence that the orders agree

It is easy to check that for $n=3$, these two orders do agree:

            a^(b^(c^d))                     A := A(a,b,c,d)
                 |                          |
            a^((b^c)^d)                     B
            /         \                    / \
 (a^b)^(c^d)           (a^(b^c))^d        C   D
            \         /                    \ /
            ((a^b)^c)^d                     E

This can be seen by taking logs of each expression. (To see that C and D are incomparable: use a=b=c=2 and d=large to obtain C>D; and use a=b=d=2 and c=large to obtain D>C.) Thus the evaluation order on length-3 expressions in $(P,$^$,\leq)$ agrees with the height order on length $6$ Dyck paths.

(Note that the answer to the question would be negative if we were to use $\mathbb{N}$ or $\mathbb{N}_{\geq 1}$ rather than $P=\mathbb{N}_{\geq2}$ as in the stated question. Indeed, with $a=c=d=2$ and $b=1$, we would have $A(a,b,c,d)=2\leq 16=E(a,b,c,d)$.)

It is even easier to see that the orders agree in the case of $n=0,1$, each of which has only one element, and the case of $n=2$, where the order $(a^b)^c\leq a^{(b^c)}$ not-too-surprisingly matches that of length-4 Dyck paths:

             /\ 
 /\/\   ≤   /  \

Indeed, the order-isomorphism for $n=2$ is not too surprising because there are only two possible partial orders on a set with two elements. However, according to the OEIS, there are 1338193159771 different partial orders on a set with $C_4=14$ elements. So it would certainly be surprising if the evaluation order for length-4 expressions in $(P,$^$,\leq)$ were to match the height order for length-8 Dyck paths. But after some tedious calculations, I have convinced myself that these two orders in fact do agree for $n=4$! Of course, this could just be a coincidence, but it is certainly a striking one.

Thoughts?

$\endgroup$
  • $\begingroup$ Why is the height order the same as inclusion order on the downset model? I believe they have quite different properties. The height order is given by height levels, with everything on a lower level less than everything on an upper level. For downsets, I believe you can easily have a "higher" downset not including a "lower" one, no? $\endgroup$ – მამუკა ჯიბლაძე Jan 2 '18 at 5:41
  • 1
    $\begingroup$ Besides, this lattice on Dyck paths is sometimes called "Stanley lattice". $\endgroup$ – Martin Rubey Jan 2 '18 at 14:30
  • 2
    $\begingroup$ I think it boils down to the following: a path $D$ is covered by a path $E$ in the Stanley lattice, if and only if a peak is converted to a valley. In terms of the binary trees, a peak is a pair of siblings where the right sibling $x$ does not have further children. In terms of magma expressions, this amounts to changes of the form $A^{B^x}$ to $(A^B)^x$, and possibly some others. Details have to be checked, of course. $\endgroup$ – Martin Rubey Jan 2 '18 at 18:14
  • 2
    $\begingroup$ @DavidSpivak : I agree with მამუკა ჯიბლაძე that "height order" is confusing. In your example of length-6 Dyck paths, my first instinct was to say that B, C, and D all have "height 2" because in all three cases, the highest peak is 2 units above the baseline, and so if we were to "compare their heights" then we would conclude that they all have equal height. But (I think) this isn't what you mean by "comparing the heights." You mean that B > C because the diagram of C would lie (weakly) underneath the diagram of B if we were to start and end the B and C paths at the same points. $\endgroup$ – Timothy Chow Jan 2 '18 at 20:00
  • 2
    $\begingroup$ A related paper is ac.els-cdn.com/0097316589900071/… by John Stembridge. It lends credence to the possibility that the iterated exponentiation order is not the Dyck order. $\endgroup$ – Richard Stanley Jan 3 '18 at 13:34
6
$\begingroup$

EDIT: I can complete half of the proof, showing that the magma order refines the Dyck order.


Following Martin Rubey's comment, there is a standard bijection between association orders and Dyck paths that uses reverse Polish notation (RPN). For $n=3$, the five association orders, when written in RPN, are

a b c d ^ ^ ^
a b c ^ d ^ ^
a b ^ c d ^ ^
a b c ^ ^ d ^
a b ^ c ^ d ^

If we ignore the initial a and interpret letters as up strokes and carets as down strokes then we get Dyck paths. The Dyck order is generated by the operation "replace x ^ with ^ x" (where x is any letter). So proving your claim reduces to showing that

  1. if you replace x ^ with ^ x then the value of the entire expression decreases, for all choices of values (from $\mathbb{N}_{\ge2}$) of the variables; and

  2. if you have a pair of RPN expressions such that you cannot get from one to the other by a sequence of such replacements, then you can get either expression to be larger than the other by suitably choosing values (from $\mathbb{N}_{\ge2}$) for the variables.

To prove part 1, note first that in a fixed RPN expression, weakly increasing the value of any variable causes the overall value to weakly increase, by the ordered magma property.

Now consider two valid RPN expressions $\alpha$ and $\beta$ that differ only in that at one point, $\alpha$ has x ^ while $\beta$ has ^ x. Just after completing this part of the calculation, stack $\alpha$ will have $A,B^C$ on top while stack $\beta$ will have $A^B,C$ on top, for some $A$, $B$, and $C$ in $\mathbb{N}_{\ge2}$. If we continue the calculation until just before the first caret that affects $A$ in stack $\alpha$ (equivalently, until the first caret that affects $A^B$ in stack $\beta$), then the top of stack $\alpha$ will look like $A, B^{CD}$ (followed by a caret) while the top of stack $\beta$ will look like $A^B, C^D$ (followed by a caret) for some $D$ (possibly equal to 1, in the case where said caret shows up immediately). Applying the caret then yields $A^{B^{CD}}$ on stack $\alpha$ and $A^{BC^D}$ on stack $\beta$. But $B^{CD} = (B^C)^D \ge (BC)^D \ge (B^{1/D}C)^D = BC^D$ for all $B, C \in\mathbb{N}_{\ge2}$ and $D\ge1$. So the value on stack $\alpha$ at this stage is $\ge$ the value on stack $\beta$. Since the remainder of the computation is the same for both stacks, the eventual value of $\alpha$ will be $\ge$ the eventual value of $\beta$.

It seems very likely to me that we can prove part 2 by finding a place $P$ where Dyck path 1 exceeds Dyck path 2 and another place $Q$ where Dyck path 2 exceeds Dyck path 1, and inserting an extremely large number at one of these points to force whichever expression we want to be larger. But I haven't quite figured out how to say this rigorously.

$\endgroup$
3
$\begingroup$

(This is what I have written just before my wife killed the internet connection 12 hours ago before she went to bed. I only show that $D\leq E \Rightarrow A\leq B$ where $D$ and $E$ are Dyck paths and $A$ and $B$ the corresponding binary trees. I didn't look at Timothy's answer yet, but I am guessing it's the same.)

Indeed, the bijection between (ordered, full) binary trees (with leaves labelled $a,b,c,\dots$ from left to right) and Dyck paths (traversing the binary tree starting at the root, first traversing the right subtree, and writing an up step for a right branch and a down step for a left branch) induces an order preserving map between the Stanley lattice and the exponential evaluation order.

A path $D$ is covered by a path $E$ in the Stanley lattice, if and only if a peak in $D$ is converted to a valley in $E$, all other steps remaining the same.

In terms of binary trees, a peak in the Dyck path corresponds to a pair of siblings where the right sibling $x$ does not have further children and there is a left branch somewhere after $x$, in the order the tree is traversed.

To see what the covering relation in the Stanley lattice corresponds to, we first do an easy special case:

Suppose that, in the binary tree $B$ corresponding to the Dyck path $E$, the parent $y$ of $x$ is a right child.

Let $L_1$ be the subtree rooted at the sibling of $x$, and let $L_2$ be the subtree rooted at the sibling of $y$. The magma expression corresponding to the subtree rooted at the parent of $y$ is $L_2 (L_1 x)$.

Then the binary tree $A$ corresponding to $D$ is obtained from $B$ by replacing the subtree rooted at the parent of $y$ with the binary tree corresponding to the magma expression $(L_2 L_1) x$, which is smaller than $L_2 (L_1 x)$.

The general case is only superficially more complicated:

Suppose that, in the binary tree $B$ corresponding to the Dyck path $E$, there is a (maximal) path of $k$ left branches from a node $y$ to the parent of $x$, with (right) siblings having subtrees $D_1,D_2,\dots,D_k$. Let $L_1$ be the subtree rooted at the (left) sibling of $x$ and $L_2$ be the subtree rooted at the (left) sibling of $y$. The magma expression corresponding to the subtree rooted at the parent of $y$ is $$L_2(\cdots((L_1 x)R_1)\cdots R_k).$$

Then the binary tree $A$ corresponding to $D$ is obtained from $B$ by replacing the subtree rooted at the parent of $y$ with the binary tree corresponding to the magma expression $$(L_2 L_1)(x (R_1(\cdots R_k))).$$

Setting $R=R_1\cdots R_k$, it remains to check that $L_2^{(L_1^{xR})} \geq (L_2^{L_1})^{(x^R)}$.

$\endgroup$
  • $\begingroup$ Maybe I missed it, but does this show that the exponential evaluation agrees with the Stanley lattice order, or just that the former is a refinement of the latter? $\endgroup$ – David Spivak Jan 3 '18 at 19:20
  • $\begingroup$ @DavidSpivak : Only that the former is a refinement of the latter. $\endgroup$ – Timothy Chow Jan 3 '18 at 21:00
  • 1
    $\begingroup$ Yes, but I think Timothy's idea (last paragraph of his excellent answer) should work to show also the converse: I guess it suffices to consider two Dyck paths that differ only by one valley and one peak, no? $\endgroup$ – Martin Rubey Jan 3 '18 at 21:07
  • 1
    $\begingroup$ @MartinRubey : I'm not sure if the problem can be reduced that way. If p is incomparable to q and q is incomparable to r then it does not follow that p is incomparable to r. Maybe this trivial observation does not rule out the reduction you have in mind but it does illustrate that one has to be more careful about "reductions" for this half of the argument. $\endgroup$ – Timothy Chow Jan 3 '18 at 21:48
  • 1
    $\begingroup$ You are right. However, there is another reduction: to show that expression $A$ and $B$ corresponding to paths $D$ and $E$ are incomparable, let's first consider a path $D'<D$, which is only at one peak larger than $E$, and the minimal path thereafter. Moreover, let $E'>E$ be the path coinciding with $E$ up to this peak and the maximal path thereafter (some details to check here...). We then show that the expression $A'$ corresponding to $D'$ is not smaller than the expression $B'$ corresponding to $E'$. If this works out, then we cannot have $A<B$, because otherwise $A'<A<B<B'$. $\endgroup$ – Martin Rubey Jan 4 '18 at 7:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.