Is the order on repeated exponentiation the Dyck order?

Question

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. Equipped with the operation given by exponentiation, $c$•$d\:=c^d$, we obtain an ordered magma, using the usual $\leq$-order. Indeed, 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?

Answer 1

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.

Answer 2

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