Sergi Elizalde
email: sergi.elizalde@dartmouth.edu.

Megan Martinez
email: megan.a.martinez.gr@dartmouth.edu.

The frequency of pattern occurrence in random walks

Keywords: permutation pattern, random walk, time series analysis, ordinal pattern, pattern frequency

In the past decade, the use of ordinal patterns in the analysis of time series and dynamical systems has become an important tool. Ordinal patterns (otherwise known as a permutation patterns) are found in time series by taking n data points at evenly-spaced time intervals and mapping them to a length-n permutation determined by relative ordering. The frequency with which certain patterns occur is a useful statistic for such series. However, the behavior of the frequency of pattern occurrence is unstudied for most models. We look at the frequency of pattern occurrence in random walks in discrete time, and we define a natural equivalence relation on permutations under which equivalent patterns appear with equal frequency, regardless of probability distribution. We characterize these equivalence classes applying combinatorial methods.

Résumé. Au cours de la dernière décennie, l'utilisation des motifs ordinaux dans l'analyse des séries chronologiques et systèmes dynamiques est devenu un outil important. Des motifs ordinaux (autrement appelés motifs de permutations) se trouvent dans les séries chronologiques en prenant n points de données au intervalles de temps uniformément espacées et les faisant correspondre à une permutation de longueur n déterminée par leur ordre relatif. La fréquence avec laquelle certains motifs apparaissent est une statistique utile pour ces séries. Toutefois, le comportement de la fréquence d'apparition de ces motifs n'a pas été étudié pour la plupart des modèles. Nous regardons la fréquence d'occurrence des motifs dans les marches aléatoires en temps discret, et nous définissons une relation d'équivalence naturelle sur des permutations dans laquelle les motifs équivalents apparaissent avec la même fréquence, quelle que soit la distribution de probabilité. Nous caractérisons ces classes d'équivalence utilisant des méthodes combinatoires.

Introduction

Time series analysis deals with the extraction of information from sequences of data points, typically measured at uniform time intervals. Understanding the characteristics of the data enables better predictions of the future behavior of a phenomenon. There are a number of different statistical methods that can be applied to the study of time series. A relatively new method involves the analysis of its "ordinal patterns." This approach, pioneered in the dynamical systems community by Bandt, Keller and Pompe [START_REF] Bandt | Permutation entropy: A natural complexity measure for time series[END_REF][START_REF] Bandt | Entropy of interval maps via permutations[END_REF] and surveyed by Amigó [START_REF] Amigó | Permutation complexity in dynamical systems[END_REF], is particularly amenable to a combinatorial treatment. For one-dimensional deterministic time series that arise from iterating a map, combinatorial analyses of the ordinal patterns for specific maps have appeared in [START_REF] Amigó | Forbidden patterns and shift systems[END_REF][START_REF] Elizalde | The number of permutations realized by a shift[END_REF][START_REF] Elizalde | Permutations and β-shifts[END_REF][START_REF] Archer | Cyclic permutations realized by signed shifts[END_REF]. However, perhaps surprisingly, very little is known about the behavior of ordinal patterns in a random setting.

In this paper we study, from a combinatorial perspective, the ordinal patterns that occur in random walks. We define an equivalence relation on permutations, which we conjecture determines when two patterns occur with the same probability in any random walk, and we provide a combinatorial characterization of the equivalence classes. We expect such a characterization to be useful in many of the applications of ordinal patterns in random walks that have recently appeared in the dynamical systems literature. Such applications include the analysis of stock indices and economic indicators, both to quantify the randomness of certain time periods in the series [START_REF] Zanin | Forbidden patterns in financial time series[END_REF], and to show that the degree of market inefficiency is correlated with the number of missing patterns [START_REF] Zunino | Forbidden patterns, permutation entropy and stock market inefficiency[END_REF]. In the related setting of Gaussian processes with stationary increments, the frequency of ordinal patterns has been estimated in [START_REF] Sinn | Estimation of ordinal pattern probabilities in Gaussian processes with stationary increments[END_REF] and computed exactly for some small patterns in [START_REF] Bandt | Order patterns in time series[END_REF].

Permutation patterns are found in a time series by taking n data points at evenly-spaced time intervals and mapping them to a length-n permutation determined by relative ordering. For example, a sequence 4.8, -4.1, 3.1, 5.2 would map to the permutation 3124 ∈ S 4 . The frequencies of the patterns that occur are measured and used to make conclusions about the behavior of the data. Central to this analysis is an understanding of the frequency with which patterns occur in a random time series.

Among the different models that are used for random time series, one of the most basic and applicable is a one-dimensional random walk in discrete time. To construct such a walk, take n -1 independent and identically distributed (i.i.d.) continuous random variables X 1 , X 2 , . . . , X n-1 ; we call these steps. The walker starts at 0, and at time i the walker is at X 1 +X 2 +. . .+X i . It is easy to see that not all permutation patterns occur with equal probability in such a random walk. For example, if the X i 's are chosen from a distribution that only takes positive values, then the pattern 123 . . . n will occur with probability 1.

Define a map p : R n-1 → S n where p(X 1 , . . . , X n-1 ) = π if the entries of the permutation π have the same relative ordering as the walk Z 0 , Z 1 , . . . , Z n-1 , where

Z i = X 1 + • • • + X i for all i (with Z 0 = 0). More precisely, p(X 1 , . . . , X n-1 ) = π if π(i) = |{k | Z k ≤ Z i }| for all i.
If the associated random walk contains repeated values, i.e. Z i = Z j for some i, j, it will be our convention to leave p undefined. Since we only deal with continuous distributions, the probability of having repeated values is zero.

While not all permutations occur in the image of p with equal probability, it turns out that there are certain classes of permutations that do have equal probability of occurring, regardless of the probability distribution chosen for the X i 's. For example, the pattern 132 will always occur with equal probability as 213, since p(X 1 , X 2 ) = 132 if and only if p(X 2 , X 1 ) = 213. In general, the reverse-complement of a permutation will occur with equal probability as the permutation itself. It turns out that such equivalencies are not restricted to reverse-complements, but are littered across S n . For example, 1432 and 2143 also occur with equal probability because p(X 1 , X 2 , X 3 ) = 1432 if and only if p(X 2 , X 1 , X 3 ) = 2143.

In this paper we define an equivalence relation on permutations that arises naturally from the above examples. It has the property that any two permutations π and τ in the same equivalence class satisfy P(p(X 1 , . . . , X n-1 ) = π) = P(p(X 1 , . . . , X n-1 ) = τ ) for any continuous probability distribution on the X i (as long as they are i.i.d.). Our main result, stated in Section 2, gives a complete characterization of the equivalence classes. Sections 3, 4, and 5 introduce the tools and ideas used in the proof. Finally, in Section 6 we conjecture that the converse property holds, that is, if two permutations occur equally often for any continuous probability distribution on the X i , then they are equivalent under our definition.

Equivalence on Permutations

We define a natural equivalence relation on permutations π, τ ∈ S n , which is suggested by the above examples. We let π ∼ τ if there exists some ρ ∈ S n-1 such that for every x 1 , . . . , x n ∈ R, we have p(x 1 , . . . , x n-1 ) = π if and only if p(x ρ(1) , . . . , x ρ(n-1) ) = τ . If X 1 , . . . , X n-1 are i.i.d. random variables, then the sequences (X 1 , . . . , X n-1 ) and (X ρ(1) , . . . , X ρ(n-1) ) have the same joint probability distribution, and so π ∼ τ implies that P(p(X 1 , . . . , X n-1 ) = π) = P(p(X 1 , . . . , X n-1 ) = τ ) for any continuous probability distribution on the random variables X i .

The main result of this paper precisely characterizes the equivalence classes for ∼. Our characterization is best illustrated by displaying permutations π ∈ S n on an n × n grid by filling the boxes (i, π(i)) for 1 ≤ i ≤ n with a dot. Our convention is that the (i, j) box is in the ith column from the left and the jth row from the bottom, as in cartesian coordinates.

Let us introduce a few definitions. A block in a permutation is a set of consecutive entries whose values also form a consecutive set. On the grid, a block is a square subgrid with a dot in each row and column, which implies that the regions right, left, above, and below a block are empty. A cylindrical block is a generalization of this notion where the requirement of consecutive positions is relaxed by considering 1 and n to be consecutive. If we identify the left and right edges of our n × n grid, then a cylindrical block is a square subgrid of the resulting cylinder with a dot in each row and column. Note that a cylindrical block can be either a regular block or a block that spans the left and right sides of the grid. We say that a cylindrical block is bordered if it has at least three entries, and the entries with highest and lowest value occur precisely at the outer positions, regardless of which one is on which side (see Figure 1). Given a permutation that contains a bordered cylindrical block, we can generate another permutation by performing a flip on the bordered cylindrical block. For a regular block, a flip is simply a 180 • rotation of the contents of the block. For a cylindrical block that spans the left/right boundary, a flip is akin to a 180 • rotation, except the entries on the left side of the block are rotated and moved to the right and vice-versa, while the entries that are not part of the block are shifted right or left accordingly (see Figure 2). Recall that the reverse-complement operation on π corresponds to a 180 • rotation of the whole n × n grid, which is a block, but not necessarily bordered. Our main theorem characterizes equivalence classes in S n in terms of flips: Proving this result requires us to delve into the structure of permutations. Our aim is to understand how we can permute the steps of one permutation (seen as a random walk) to get another. For real numbers x 1 , . . . , x n-1 to satisfy p(x 1 , . . . , x n-1 ) = π, there are some forced relationships among them. For example, if p(x 1 , x 2 , x 3 ) = 1423, then x 1 + x 2 > 0 and x 1 > x 3 , among other relations.

It will be convenient to draw each step of π (seen as a walk) as a vertical, directed edge. In the coordinate plane, we draw edge e i as the line segment that connects (i, π(i)) to (i, π(i + 1)), directed upwards if π(i + 1) > π(i) and downwards otherwise. Define sgn(e i ) = sgn(π(i + 1) -π(i)). We denote the (unordered) set of n -1 edges corresponding to π by E π and call it its edge diagram (see Figure 3). We think of the y-coordinates 1, 2, . . . , n as vertices, and of e i as a directed edge from π(i) to π(i + 1). With this interpretation, a sequence of edges e i , e i+1 , . . . , e j-1 forms a path from vertex π(i) to vertex π(j).

       0 0 0 0 1 1 -1 -1 -1 -1 -1 -1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 -1 -1 -1 0 0 0 1 0 0 0        L(π)
Fig. 3: The permutation π = 5712634, its edge diagram, and its matrix L(π).

We partition the y-axis of our edge diagram into the intervals

1 = [1, 2], 2 = [2, 3], . . . , n -1 = [n -1, n],
that we call levels. We can then write each edge as a formal sum of the levels it covers:

e i = π(i+1)-1 j=π(i) j when π(i) < π(i + 1
) and e i = -π(i)-1 j=π(i+1) j when π(i + 1) < π(i). Notice that letting L(π) be the (n -1) × (n -1) matrix with entries -1, 0, 1 where

(L(π)) ij = sgn(π(i + 1) -π(i))), if π(i) ≤ j < π(i + 1) or π(i + 1) ≤ j < π(i), 0, otherwise, then we have that e i = n-1 j=1 (L(π)) ij • j, that is,    e 1 . . . e n-1    = L(π) •    1 . . . n -1    . (1)
For ease of notation, we write j ∈ e i if (L(π)) ij = 0.

The following lemma, whose proof is omitted in this extended abstract, states that L is a group homomorphism between S n and GL n-1 (C). Thus, L gives a representation of the symmetric group, which can be shown to be isomorphic to the standard representation. Lemma 2.2 For every π, τ ∈ S n , we have L(τ π) = L(π)L(τ ).

Noticing that L maps the identity permutation to the identity matrix, it follows from Lemma 2.2 that L(π -1 ) = L(π) -1 , and, in particular, that L(π) is always invertible. Additionally, since L(π) and L(π -1 ) are matrices with integral entries, they have integral determinants, and so det(L(π)) = ±1.

In order to classify equivalence classes, we first show that π ∼ τ if and only if L(π) and L(τ ) are related by permutations of rows and columns. In the following lemma, P ρ denotes the permutation matrix associated to ρ; that is, (P ρ ) ij equals 1 if ρ(i) = j and 0 otherwise.

Lemma 2.3 For π, τ ∈ S n , π ∼ τ if and only if there exist σ, ρ ∈ S n-1 such that P ρ -1 L(π)P σ = L(τ ).
The proof of this lemma uses the fact that if we let

D π = {x ∈ R n-1 | p(x) = π}, then multiplication by L(π) is a bijection from R n-1 >0 to D π . Thus, if ρ ∈ S n-1 is such that (x 1 , . . . , x n-1 ) ∈ D π if and only if (x ρ(1) , . . . , x ρ(n-1) ) ∈ D τ , then multiplication by L(π -1 )P ρ L(τ ) is a bijection from R n-1
>0 to itself. Since this matrix and its inverse have non-negative integer entries, it must be a permutation matrix P σ .

If we consider the results of Lemma 2.3 in the context of an edge diagram, σ is applied to the levels and ρ is applied to the edges. Since the edges of an edge diagram are unordered, we only need to consider permutations of the levels by σ, as will be stated in Lemma 2.4.

We need a notation that describes edges in terms of levels. For vertices s, t ∈ [n] with s < t in an edge diagram, we write the interval between s and t as [s, t] and define this to be the union of levels s∪s + 1∪. . .∪t -1. We write an edge

e i ∈ E π as a directed interval [π(i), π(i+1)] + (if π(i) < π(i+1)) or [π(i + 1), π(i)] -(if π(i) > π(i + 1)) for 1 ≤ i ≤ n -1;
the subscripts indicate upwards or downwards direction, respectively. For example, in Figure 3 Permuting the levels of an edge diagram by σ takes level i and moves it to height σ(i). Intervals and edges are shifted accordingly: the interval [i, j] is moved to σ.[i, j] = σ(i) ∪ σ(i + 1) ∪ . . . ∪ σ(j -1) (note that σ.[i, j] may no longer be an interval), and the edge [i, j] ± is moved to (σ.[i, j]) ± , where the sign is preserved. The set of images of elements of E π is denoted by E σ.π , and we say that this is a welldefined edge diagram if for every edge [i, j] ± ∈ E π , σ.[i, j] is an interval. If E σ.π is the edge diagram of a permutation, we say that E σ.π is a proper edge diagram and call the corresponding permutation σ.π.

Recall that the edge diagram of a permutation τ forms a path τ (1), τ (2), . . . , τ (n) where the vertices τ (i) and τ (i + 1) are connected by an edge e i . A well-defined edge diagram E σ.π is proper if and only if its edges form a path. This allows us to ignore the order of the edges in E π , since π can be recovered from the path. This idea is useful when proving the following statement:

Lemma 2.4 Given π, τ ∈ S n , π ∼ τ if and only if there exists σ ∈ S n-1 such that E σ.π = E τ .
Example 2.5 Let π = 54621873, τ = 73218465 ∈ S 8 , whose edge diagrams are drawn in Figure 4, and let σ = 2365471 ∈ S 7 . Then Definition 2.6 Let π ∈ S n and σ ∈ S n-1 such that E σ.π is well-defined. We say that σ is valid with respect to π if E σ.π is proper. If σ is valid with respect to π, we will say that σ acts validly on π.

E π = {[4, 5] -, [4, 6] + , [2, 6] -, [1, 2] -, [1, 8] + , [7, 8] -, [3, 7] -} and E σ.π = {[3, 7] -, [2, 3] -, [1, 2] -, [1, 8] + , [4, 8] -, [4, 6] + , [5, 6] -} = E τ . Therefore π ∼ τ .
One of the goals of the next few sections to describe all σ that are valid with respect to π and understand how they transform π. Note that if σ 1 , σ 2 ∈ S n-1 are such that E σ1.π and E σ2.(σ1.π) are proper edge diagrams, then E σ2.(σ1.π) = E (σ2σ1).π . Allowing edge diagrams that are not well-defined (meaning the edges are not contiguous) would give a group action of S n-1 on S n , but for our purposes it is convenient to restrict only to well-defined diagrams.

Valid Flips

In this section, we define an operation on edge diagrams that is analogous to a flip of a bordered cylindrical block. The remaining sections will then focus on proving that any two equivalent permutations differ by a sequence of these operations.

We will use the following two properties of edge diagrams:

(1) Let {p π , q π } = {π(1), π(n)} be the endpoints in the edge diagram for π (assume p π < q π ). Then for any i ∈ [n -1], the number of edges that contain i is odd if i ∈ [p π , q π ] and even otherwise. So, if σ is valid with respect to π, then σ.[p π , q π ] must be an interval.

(2) Define a cycle in an edge diagram to be a sequence of vertices v 1 , v 2 , v 3 , . . . , v k where either

[v i , v i+1 ] + or [v i+1 , v i ]
-is an edge for every i, and either

[v k , v 1 ] + or [v 1 , v k ] -is an edge. If E σ.
π is well-defined, then it does not contain a cycle.

Property ( 1) is straightforward. To prove property (2), one can show that a cycle in E σ.π would require the existence of a cycle in E π .

Property (1) suggests a slight alteration to our edge diagrams. Since [p π , q π ] must remain an interval, any σ that is valid with respect to π must treat [p π , q π ] as if it were a "phantom" edge. Let [p π , q π ] ± be an edge such that sgn([p π , q π ] ± ) = 1 if π(n) < π(1) and sgn([p π , q π ] ± ) = -1 if π(1) < π(n). Define a modified edge diagram on a permutation π to be E π = E π ∪ [p π , q π ] ± . The ornamentation on [p π , q π ] ± is needed to ensure there is a bijective correspondence between permutations and modified edge diagrams. This added edge, which converts the path of E π into a cycle, will be represented with a dashed line in a drawing of E π (see Figure 5). However, [p π , q π ] ± is mathematically treated like any other edge.

The terminology from edge diagrams can be naturally extended to modified edge diagrams. For instance, we say that σ.E π = {σ.e | e ∈ E π } is well-defined if σ.[i, j] is an interval for every edge The proof of Lemma 3.1 requires using property (2) to show that E σ.π will form a path whenever σ.E π forms a cycle. As a consequence of Lemma 3.1, working with modified edge diagrams is analogous to working with edge diagrams. Additionally, σ.E π will be notated as E σ.π .

[i, j] ± ∈ E π . Additionally, σ.E π is proper if E σ.π is proper.
Define a flip to be a permutation σ ∈ S n-1 of the form

σ = 1 2 3 ••• i-1 i i+1 ••• j-1 j ••• n-1 1 2 3 ••• i-1 j-1 j-2 ••• i j ••• n-1
where j > i + 1. We say that σ flips the interval [i, j].

Since adjacent transpositions are a particular case of flips, it is clear that flips generate S n-1 . Given any interval

[i, j] in E π , we say that [i, j] respects E π if for every e ∈ E π , e ⊆ [i, j], [i, j] ⊆ e, or [i, j] ∩ e = ∅.
Lemma 3.2 Suppose that σ ∈ S n-1 is a flip of the interval [i, j] (where j > i + 1). Then σ is valid with respect to π if and only if [i, j] respects E π .

We omit the proof of this lemma. The idea is that the cycle in E π behaves well in relation to the interval [i, j]. Therefore, flipping [i, j] will simply reorder certain portions of the cycle.

The intervals mentioned in Lemma 3.2 correspond to bordered cylindrical blocks. We therefore call a flip as described in Lemma 3.2 a valid flip (with respect to π) and the interval it flips a valid interval (in E π ). In general, we say that σ transforms π by a sequence of valid flips if there exist σ 1 , . . . , σ l ∈ S n-1 with σ l σ l-1 • • • σ 1 = σ such that σ i is a valid flip with respect to σ i-1 σ i-2 . . . σ 1 .π for every i. Lemma 3.3 For every π ∈ S n , the interval [i, j] is valid in E π if and only if in the grid of π, the values [i, j] (which are in positions π -1 (i), π -1 (i+1), . . . , π -1 (j)) form a bordered cylindrical block or [i, j] = [1, n]. In this case, flipping the valid interval [i, j] in E π is equivalent to flipping the corresponding bordered cylindrical block in the grid of π, or, when [i, j] = [1, n], to taking the reverse-complement. For an example of Lemma 3.3, see Figure 5. Now we can restate Theorem 2.1 as follows:

Theorem 3.4 Let π, τ ∈ S n . Then π ∼ τ if and only if τ can be obtained from π by a sequence of valid flips.

In order to prove this theorem, we need to further explore the structure of edge diagrams. The aim of the definitions and lemmas in the following section will be to decompose our edge diagrams into nested structures to which we will be able to apply an inductive argument.

Irreducible Intervals

For given π ∈ S n , most permutations of the levels of its edge diagram are not valid. Our induction argument will rely on the ability to partition the levels of the edge diagram into intervals that remain intervals under any valid permutation of the levels. We first introduce the idea of an irreducible interval, which is a maximal interval whose levels remain adjacent under the action of any valid permutation. Then we show that every edge diagram can be uniquely partitioned into intervals of this type. Definition 4.1 Let π ∈ S n . An interval [s, t] in the modified edge diagram of π is said to satisfy the linked conditions if, for every σ ∈ S n-1 that is valid with respect to π, the following are true:

(1) The image σ.[s, t] is an interval.

(2) If we let i, j ∈ [n] be such that σ.[s, t] = [i, j], then the ordered tuple (σ(s), σ(s + 1), σ(s + 2), . . . , σ(t -1)) equals either (i, i + 1, . . . , j -1) or (j -1, j -2, . . . , i).

Additionally, [s, t] is called an irreducible interval if it is a maximal interval that satisfies the linked conditions (i.e. for any interval [x, y] such that [s, t] [x, y], [x, y] does not satisfy the linked conditions).

Note that any proper subinterval of an irreducible interval will satisfy the linked conditions but will fail the maximality condition. Since intervals of width 1 trivially satisfy the linked conditions, it is clear that every level of the edge diagram is contained in some irreducible interval. The condition on maximality for irreducible intervals implies that the partition is unique.

2

We let I π = {[x i , x i+1 ] : 0 ≤ i < k}, where x 0 = 1 and x k = n, denote the partition of the levels of some E π into irreducible intervals. We call I π the irreducible partition of π, and we call the x i its borders.

It is not true that every irreducible interval is valid; for instance, interval [START_REF] Amigó | Permutation complexity in dynamical systems[END_REF][START_REF] Bandt | Entropy of interval maps via permutations[END_REF] in Figure 6(c) is irreducible but not valid. However, any valid interval is the union of adjacent irreducible intervals. Indeed, given an interval [i, j] that is valid (so j > i + 1) with respect to E π , we know by Lemma 3.2 that if σ flips [i, j], then E σ.π is proper. When j = i + 1, this implies that i and j are borders of the irreducible partition I π , since σ.(i -1 ∪ i) = i -1 ∪ j -1 and σ.(j -1 ∪ j) = i ∪ j are not intervals.

Finding irreducible intervals using Definition 4.1 is impractical. A corollary to Theorem 3.4, omitted in this extended abstract, states that irreducible intervals are completely determined by the valid intervals. More precisely, any interval [a, b] satisfies the linked conditions if and only if [a, b] is contained in or disjoint from every valid interval in E π . Thus, x i is a border of I π if and only if x i is an endpoint of some valid interval. The proof is not obvious; a correspondence between valid intervals in equivalent permutations is established in order to derive these facts.

Although a few permutations only have irreducible intervals of width one, such as 1 2 3 . . . n and 1 n (n -1) . . . 2, permutations often have wide irreducible intervals. For instance, whenever an edge diagram has an edge of width two, the two levels covered by this edge must remain adjacent, thereby creating an irreducible interval with width at least 2. In fact, many permutations have one single irreducible interval [1, n]. Examples of irreducible intervals are given in Figure 6. We write the signed permutation µ as µ(1)µ(2) . . . µ(n), leaving out the images of the negative numbers since they follow, and writing µ(i) instead of -µ(i). Note that the barring operation is an involution, i.e. µ(i) = µ(i). Let |µ(i)| denote the entry µ(i) without a bar. We denote the set of signed permutations of length k by B k , and the infinite set of all signed permutations by B.

If π ∈ S n has k irreducible intervals, we can apply a signed permutation µ ∈ B k to the edge diagram of π as follows. Each entry of µ describes where the corresponding irreducible interval of π is moved, and a barred entry indicates that the order of the levels inside the irreducible interval is reversed. As an example, see Figure 7. We denote the image of applying µ to the irreducible intervals of a modified edge diagram, E π , by E µ.π . If, additionally, this is a proper modified edge diagram, we say that µ is valid with respect to π and denote the corresponding permutation by µ.π.

We need to generalize our notion of a valid flip to signed permutations. If [x i , x j ] is a valid interval in E π , then we say that µ = 1 2

• • • i j j-1 • • • i+1 j+1 • • • k ∈ B k
is a valid flip with respect to π. We say that µ transforms π by a sequence of valid flips if there exist µ 1 , . . . , µ l ∈ B k with µ l µ l-1 • • • µ 1 = µ such that µ i is a valid flip with respect to µ i-1 µ i-2 . . . µ 1 .π for all i.

We can now restate our main theorem using the irreducible partition.

Cohesive Intervals and Partitions

In this section, we introduce the notion of a cohesive partition, a generalization of the irreducible partition.

We are going to induct on the number of blocks of a partition of the edge diagram of π, so the purpose of this generalization is to have a method of coarsening the irreducible partition. Condition (2) is difficult to check, since one would in principle have to verify the property for all signed permutations of length k. Notice that every edge in E π satisfies condition (2), but most will fail [START_REF] Amigó | Permutation complexity in dynamical systems[END_REF]. All irreducible intervals satisfy condition (2), but not necessarily condition (1), as is the case for interval [START_REF] Amigó | Permutation complexity in dynamical systems[END_REF][START_REF] Bandt | Entropy of interval maps via permutations[END_REF] in Figure 6(c). Some examples of cohesive intervals are given in Figure 8; notice that [START_REF] Amigó | Permutation complexity in dynamical systems[END_REF][START_REF] Elizalde | The number of permutations realized by a shift[END_REF] and [START_REF] Bandt | Order patterns in time series[END_REF][START_REF] Zanin | Forbidden patterns in financial time series[END_REF] are valid intervals but not cohesive. Since all cohesive intervals are valid, they are the union of consecutive irreducible intervals; we will sometimes use the borders x i of the irreducible partition to describe them. For convenience, we write {a 0 , a 1 , . . . , a l } < to denote the partition into intervals [a i , a i+1 ] for 0 ≤ i < l. Fig. 8: In E π , where π = 1 10 8 9 7 6 2 4 3 5, the intervals [START_REF] Amigó | Permutation complexity in dynamical systems[END_REF][START_REF] Bandt | Order patterns in time series[END_REF], [START_REF] Amigó | Permutation complexity in dynamical systems[END_REF][START_REF] Zanin | Forbidden patterns in financial time series[END_REF], [START_REF] Amigó | Forbidden patterns and shift systems[END_REF][START_REF] Bandt | Permutation entropy: A natural complexity measure for time series[END_REF], and [START_REF] Elizalde | The number of permutations realized by a shift[END_REF][START_REF] Zanin | Forbidden patterns in financial time series[END_REF] are cohesive.

Fig. 1 :

 1 Fig. 1: Examples of bordered and unbordered cylindrical blocks in π = 8 6 1 3 4 2 5 10 7 9.

Theorem 2 . 1 Fig. 2 :

 212 Fig. 2: A sequence of flips of bordered cylindrical blocks that maps π = 5712634 to τ = 6371245.

e 1 e 2 e 3 e 4 e 5 e 6

 6

  , the edges in E π are e 1 = [5, 7] + , e 2 = [1, 7] -, e 3 = [1, 2] + , e 4 = [2, 6] + , e 5 = [6, 3] -, e 6 = [3, 4] + . Given an edge e = [i, j] ± ∈ E π and any interval [s, t], we write [s, t] ⊆ e if [s, t] ⊆ [i, j] and e ⊆ [s, t] if [i, j] ⊆ [s, t].

EτFig. 4 :

 4 Fig. 4: π = 54621873 is mapped to τ = 73218463 by applying σ = 2365471. The edges of E τ are first displayed in the same order as in E π , and then rearranged to form a path.

Lemma 3 . 1

 31 Let π ∈ S n and σ ∈ S n-1 such that σ.E π is a well-defined edge diagram. Then σ.E π forms a cycle if and only if E σ.π is a proper edge diagram.

Fig. 5 :

 5 Fig.5: Flipping valid interval[START_REF] Amigó | Forbidden patterns and shift systems[END_REF][START_REF] Bandt | Order patterns in time series[END_REF] in the edge diagram for π = 235461 yields the same result as flipping the bordered cylindrical block with values[START_REF] Amigó | Forbidden patterns and shift systems[END_REF][START_REF] Bandt | Order patterns in time series[END_REF] (and positions[START_REF] Amigó | Permutation complexity in dynamical systems[END_REF][START_REF] Bandt | Permutation entropy: A natural complexity measure for time series[END_REF]) in the grid of π.

Lemma 4 . 2

 42 For any π ∈ S n , the interval[1, n] in the modified edge diagram of π can be uniquely partitioned into irreducible intervals.Proof: Suppose that [s, t] and [u, v] are irreducible intervals with a nonempty intersection. By the maximality condition, [s, t] cannot properly contain [u, v] and vice versa. Without loss of generality, assume that s ≤ u and t ≤ v. Then [s, t] ∩ [u, v] = [u, t]. Since both [s, t] and [u, v] satisfy the linked conditions, every σ that is valid with respect to π maps [s, t] and [u, v] to intervals. Since these intervals have nonempty intersection, it follows that σ maps [s, t] ∪ [u, v] = [s, v] to an interval. In fact, the second linked condition for [s, t] and [u, v] quickly implies that [s, v] satisfies the condition as well. By the maximality of irreducible intervals, this is only possible if s = u and t = v. Therefore, any two irreducible intervals are either disjoint or equal.

  The modified edge diagram for 435216 has two irreducible intervals:[START_REF] Amigó | Permutation complexity in dynamical systems[END_REF][START_REF] Amigó | Forbidden patterns and shift systems[END_REF] and[START_REF] Amigó | Forbidden patterns and shift systems[END_REF][START_REF] Bandt | Order patterns in time series[END_REF].

  The modified edge diagram for 35241 has one irreducible interval:[START_REF] Amigó | Permutation complexity in dynamical systems[END_REF][START_REF] Bandt | Permutation entropy: A natural complexity measure for time series[END_REF].

  The modified edge diagram for 1327564 has two irreducible intervals:[START_REF] Amigó | Permutation complexity in dynamical systems[END_REF][START_REF] Bandt | Entropy of interval maps via permutations[END_REF] and[START_REF] Bandt | Entropy of interval maps via permutations[END_REF][START_REF] Elizalde | The number of permutations realized by a shift[END_REF].

Fig. 6 :

 6 Fig. 6: Examples of irreducible intervals

1

 1

3 Fig. 7 : 2 1 3 5 4 6 9 7 8 10 is mapped to 1 3 2 4 7 5 6 8 10 9 by applying µ = 31 2 . 4 . 3

 37243 Fig. 7: 2 1 3 5 4 6 9 7 8 10 is mapped to 1 3 2 4 7 5 6 8 10 9 by applying µ = 31 2.

Definition 5 . 1

 51 Let π ∈ S n with k irreducible intervals. We say that an interval [a, b] is cohesive in π if (1) [a, b] is a valid interval in E π ,and (2) for every µ ∈ B k that is valid with respect to π, µ.[a, b] is an interval.

(a) The bordered cylindrical block 1 3 4 2 5. (b) The unbordered cylindrical block 5 10 7 9 8 6.(c) The bordered cylindrical block 10 7 9 8 6.

Acknowledgements

The authors thank Adeline Pierrot for useful ideas during the early stages of this work.

Partially supported by grant #280575 from the Simons Foundation and by grant H98230-14-1-0125 from the NSA.

Definition 5.2 A partition P = {x s = a 0 , a 1 , a 2 , . . . , a l = x t } < of a cohesive interval [x s , x t ] is called a cohesive partition if [a i , a i+1 ] is irreducible or cohesive for every 1 ≤ i < l.

Cohesive partitions provide us a more general setting to prove our main theorem: we will consider signed permutations of the blocks in P that result in a valid modified edge diagram, and show that all such permutations are sequences of valid flips. We can then prove Theorem 4.3 as a special case, using that [1, n] is a cohesive interval and the irreducible partition is a cohesive partition.

In the rest of this section, we assume that π ∈ S n has k irreducible intervals, and we use P = {a 0 , a 1 , a 2 , . . . , a l } < to denote a cohesive partition of the cohesive interval [x s , x t ]. The notation [x s , x t ] P is used when considering [x s , x t ] as a union of the blocks of P. This is in contrast to [x s , x t ], which is thought of as a union of levels.

In order to consider signed permutations of the blocks for a partition P in a cohesive interval [x s , x t ], we need to introduce a few definitions. Given µ ∈ B k , its reverse-complement is the signed permutation with µ RC (i) = µ(k -i + 1) for 1 ≤ i ≤ k. For α 1 , α 2 , . . . , α k ∈ B, we define the inflation of µ by α 1 , α 2 , . . . , α k to be the signed permutation obtained by replacing each µ(i) with a block that has the pattern α i if µ(i) is positive, and α RC i if µ(i) is negative. The relative ordering of the blocks is determined by the relative unsigned on µ (meaning we consider simply absolute values). We denote this inflation by µ[α 1 , α 2 , . . . , α k ]. For example, 3 12[ 21, 31 2, 1] = 65 2 13 4.

In the following definition, 1 stands for the identity permutation of length one and 1 t stands for the identity permutation of length t. We write 1 l to denote a sequence of l ones.

Cohesive partitions play an important role in our proof. In some cases, P contains a proper cohesive interval, which is a cohesive interval [a i , a j ] where j = i+1 and (i, j) = (0, l). In these cases, we are able to create two new cohesive partitions, P = {a 0 , a 1 , . . . , a i , a j , . . . , a l } < and P = {a i , a i+1 , . . . , a j } < , and use them to decompose the action of a valid µ, as described in the following lemma. Lemma 5.4 Let µ ∈ B l be valid with respect to [x s , x t ] P . If [a i , a j ] is a proper cohesive interval, there exist α ∈ B l-j+i+1 and β ∈ B j-i such that µ = α[1 i , β, 1 l-j ]. Additionally, β is valid with respect to [a i , a j ] P .

The idea of the proof, which is omitted in this extended abstract, is that there are only two obvious choices for our α, β pair. In one of them, α(i) is positive, and in the other it is negative. One can show that both of these choices make β valid with respect to [x i , x j ] P . Since µ is valid with respect to [x s , x t ] P , this amounts to examining the behavior of the cycle at the vertices a i and a j after applying β; showing that both a i and a j have indegree and outdegree one is enough to show that the result is a cycle.

We now have all the tools needed to handle the main theorem. In fact we prove the following more general statement about cohesive partitions. Proposition 5.5 Every µ ∈ B l that is valid with respect to [x s , x t ] P transforms [x s , x t ] P by a sequence of valid flips.

The idea of the proof, again omitted, is that if P contains a proper cohesive interval [a i , a j ], we can then use induction to find a sequence of valid flips that first permutes the intervals inside of [a i , a j ] and then the intervals outside of [a i , a j ]. The difficulty comes when there is no proper cohesive interval. We deal with this case separately and directly in the proof. Theorem 4.3, and thus its equivalent restatements Theorems 3.4 and 2.1, follow now as a consequence of Proposition 5.5 taking l = k, s = 0, t = k and P = I π , the irreducible partition.

Future Work

We have defined a natural equivalence ∼ on permutations and characterized the equivalence classes using valid flips. We conjecture that our equivalence classes describe precisely when two permutations are obtained with the same probability in a random walk regardless of the probability distribution on the steps. We are currently working on proving this statement. Conjecture 6.1 For π, τ ∈ S n , P(p(X 1 , X 2 , . . . , X n-1 ) = π) = P(p(X 1 , X 2 , . . . , X n-1 ) = τ ) for every probability distribution on the i.i.d. random variables X 1 , X 2 , . . . , X n-1 if and only if π ∼ τ .


Greta Panova
email: panova@math.upenn.edu

Lozenge tilings with free boundary

Keywords: lozenge tilings, symmetric plane partitions, limit shapes, GUE eigenvalues

We study tilings with lozenges of a domain with free boundary conditions on one side. These correspond to boxed symmetric plane partitions. We show that the positions of the horizontal lozenges near the left flat boundary, in the limit, have the same joint distribution as the eigenvalues from a Gaussian Unitary Ensemble (the GUE-corners/minors process). We also prove the existence of a limit shape of the height function (the symmetric plane partition). We also consider domains where the sides converge to ∞ at different rates and recover again the GUE-corners process.

Résumé. Nous étudions les pavages par losanges d'un domaine dont le bord vertical est "libre". Nous montrons que les positions des losanges horizontaux proches du bord gauche ont la même distribution que les valeurs propres de l'ensemble gaussien unitaire. Nous montrons aussi l'existence d'une limite de la forme de la fonction de hauteur (une partition plane symétrique). Nous considérons aussi des domaines ou des bords différents convergent vers ∞ des taux différents et nous retrouvons nouveau les processus EGU au bord.

Introduction

We study lozenge tilings of certain domains with partially free boundary conditions. These are tilings of a domain on a triangular grid into unit-sided lozenges, see Figure 1. In the particular setting, we are interested in a half-hexagonal domain, such that on its side corresponding to the main diagonal of the hexagon, we have free boundary conditions -that is, the "horizontal" lozenges are allowed to cross that (free) boundary at any place and protrude halfway through. Let m be the length of the vertical side of the hexagon, let n the other two lengths, and denote by T f (n, m) the set of all so-described free-boundary tilings. Reflecting the tiling along the right boundary line of the domain gives a symmetric tiling, which corresponds to a boxed symmetric plane partition fitting in an m × n × n box (each lozenge represents a side of a cube).

Lozenge tilings of fixed boundary domains have been studied extensively both as combinatorial objects corresponding to plane partitions (see e.g. [START_REF] Stanley | Enumerative combinatorics[END_REF]) and as integrable models in statistical mechanics, where the interest has been the limiting behavior as the mesh (triangle) size goes to 0 and the domain has a fixed boundary. In these cases, most aspects of the limit behavior have been understood -the "frozen regions" (covered by just one type of tile) bounded by algebraic "arctic curves" (see e.g. [KO], [CLP]), the surface as a limit of the height function, also referred to as "limit shape", (see [BBO, BG, CLP, CKP]), the fluctuations near the frozen boundary being the Airy process (see [Petrov] and references therein) and the fact that the positions of the horizontal lozenges near a flat vertical boundary have the same joint distribution as the eigenvalues of Gaussian Unitary Ensemble (GUE) matrices (see [GP, OR] and works by [Johansson-Nordenstam], [Nordenstam], [Novak]). Symmetric lozenge tilings (plane partitions) have also been studied when the symmetry is along the horizontal axis instead of the vertical axis as considered here (referring to Figure 1), with results by [Forrester-Nordenstam] and in [BG].

n m λ 1 + N -1 λ 2 + N -2 λ N m n y 3 1 y 3 2 y 3 3 Line k = 3
Fig. 1: Top, middle: the half-hexagon domain in the triangular grid, which is tiled with the 3 types of lozenges (on the right) -the right boundary of the domain (middle dashed line) is allowed to cut a lozenge in half as shown and the positions of these "cut" lozenges are unrestricted. Left: the positions y k of the horizontal lozenges on vertical line k of a tiling whose rightmost boundary is given by the partition λ = (5, 4, 3, 1, 0), here k = 3 and y 3 = (4, 3, 0). Right: the corresponding vertically-symmetric boxed plane partition.

Here we study the same aspects for lozenge tilings with free boundaries as the ones studied for fixed domains, described above. We show that the positions of the horizontal lozenges near the left boundary have the same distribution as the GUE matrices eigenvalues, see Theorem 4.3. We also prove the existence of the limit shape of the height function (i.e. the symmetric plane partition) in Theorem 5.3. The existence of the limit shape was assumed (without proof) in [DR], where the limit shape and arctic curves were calculated under these assumptions, but the limit shape existence in such tilings has not been studied with the present variational methods.

Theorem 1.1 Let m/n → a as n, m → ∞. The rescaled height function of the uniformly random lozenge tilings of a half-hexagon with free right boundary (i.e. the symmetric plane partition) converges (in probability) to a unique limit shape, which coincides over the half-hexagon with the limit shape for the tilings of the full hexagon (fixed boundary) as described in [CLP]. Moreover, the positions of the horizontal lozenges (shifted by m/2 and rescaled by n(a 2 + 2a)/8) on the r-th vertical line from the left have the same joint distributions as n, m → ∞, which is the distribution of the eigenvalues of r × r matrices from the Gaussian Unitary Ensemble. Further, the joint distribution of these positions on all lines 1, . . . , k converges to the joint distribution of the collection of the eigenvalues of the principal submatrices of sizes 1, . . . , k of a GUE matrix, known as the GUE-corners (GUE-minors) process.

Our methods to proving the GUE distribution follow the approach developed in [GP] on asymptotics of symmetric functions through certain integral representations and steepest descent asymptotic analysis. There GUE was shown for tilings of fixed boundary domains by using asymptotics of their moment generating functions, which were certain Schur functions. As it turns out here, the role of Schur functions is replaced by symplectic characters and so we derive their asymptotics explicitly. The proof of the existence of the limit shape follows the approach of [BBO] and [BG] with moment generating functions for certain measures. It relies on some further symmetric function identities and their asymptotics. Finally, the GUE phenomenon for differently scaled m and n is also shown through asymptotic analysis of symplectic characters using the exact formulas from [GP] with care on the analysis in the unusual regimes. For the complete proofs, technical definitions and statements, and the full list of references we refer the reader to the full version of this paper, available at ARXIV:1408.0417.

Preliminaries

Rational irreducible representations of Lie groups are parametrized by their highest weights (also called signatures or integer partitions when the entries are nonnegative integers) λ -sequences of (half)integers

λ = (λ 1 ≥ λ 2 ≥ • • • ≥ λ N ).
Denote the set of highest weights/signatures of length N by GT N . We will use the characters of these representations. For GL N (C), these are the Schur functions s λ (x 1 , . . . , x N ), which can be defined for any sequence λ via Weyl's character formula, and when λ is an integer partition these are the generating functions for semi-standard Young tableaux of shape λ, see [START_REF] Stanley | Enumerative combinatorics[END_REF][START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]. The value of the character of the irreducible representation of the symplectic group Sp 2N (C), parameterized by λ ∈ GT N , on a symplectic matrix with eigenvalues x 1 , x -1 1 , . . . , x N , x -1 N is given by

χ λ (x 1 , . . . , x N ) = det x λj +N +1-j i -x -(λj +N +1-j) i N i,j=1 det x N +1-j i -x -N -1+j i N i,j=1
.

We now repeat definitions, results and setups from [GP] which will be used later. The normalized Schur function/ symplectic character on k variables are defined as

S λ (x 1 , . . . , x k ; N ) = s λ (x 1 , . . . , x k , 1 N -k ) s λ (1 N ) X λ (x 1 , . . . , x k ; N ) = χ λ (x 1 , . . . , x k , 1 N -k ) χ λ (1 N ) .
Proposition 2.1 (Proposition 3.19 in [GP]) For any signature λ ∈ GT + N we have

X λ (x; N ) = 2 x + 1 S ν (x; 2N, 1), (1)
where ν ∈ GT 2N is given by ν i = λ i + 1 for i = 1, . . . , N and

ν i = -λ 2N -i+1 for i = N + 1, . . . , 2N .
In [GP] explicit asymptotic expansions for the normalized Schur functions S λ were found, when λ(N ) converges to a limiting profile function f on [0, 1] in the sense of λ(N ) i /N → f (i/N ) under specific conditions as N → ∞ for i = 1, . . . , N . The precise results and convergence conditions can be found in [GP] and the full version of this paper, here we just state them informally.

Proposition 2.2 (Proposition 4.3 in [GP]) Suppose that f (t) is piecewise-differentiable, and λ(N )/N → f as N → ∞ in a certain sense (see [GP]). Then for any fixed h ∈ R

S λ(N ) (e h/ √ N ; N ) = exp √ N E(f )h + 1 2 S(f )h 2 + o(1)
as N → ∞, where

E(f ) = 1 0 f (t)dt, S(f ) = 1 0 f (t) 2 dt -E(f ) 2 + 1 0 f (t)(1 -2t)dt.
Moreover, the error o( 1) is uniform over h belonging to compact subsets of R \ 0.

Proposition 2.3 (Proposition 4.1 in [GP].) For y ∈ R \ {0}, suppose that f (t) is piecewise-continuous, λ(N )/N → f in a certain sense, and w 0 = w 0 (y) is the (unique) real root of (∂/∂w)F(w; y) = 0, where F(w; f ) = 1 0 ln (w -(f (t) + 1 -t)) dt . If y ∈ R \ {0} id such that w 0 is outside the interval [ λ N (N ) N , λ1(N ) N + 1] for all N large enough, then lim N →∞ ln S λ(N ) (e y ; N ) N = yw 0 -F(w 0 ) -1 -ln(e y -1). (2)
We use the formula for the multivariate symplectic characters from [START_REF] Gorin | Asymptotics of symmetric polynomials with applications to statistical mechanics and representation theory[END_REF]Theorem 3.17] to derive the asymptotics for k > 1 out of developed asymptotics for k = 1:

X λ (x 1 , . . . , x k ; N ) = ∆ 1 s (1 N ) ∆ 1 s (x 1 , . . . , x k , 1 N -k ) × (-1) ( k 2 ) det x i ∂ ∂x i 2(j-1) k i,j=1 k i=1 X λ (x i ; N ) (x i -x -1 i )(2 -x i -x -1 i ) N -1 2(2N -1)! , (3)
where the ∆ 1 s are Vandermonde-type explicit polynomials. We use the following crucial formula from [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]I.5,Example 16], which we refer to as Macdonald's identity, to compute the sum of Schur functions, indexed by partitions λ ⊂ (m n ):

φ m (x 1 , . . . , x n ) := λ∈(m n ) s λ (x 1 , . . . , x n ) = det[x m+2n-i j -x i-1 j ] 1≤i,j≤n det[x 2n-i j -x i-1 j ] 1≤i,j≤n . (4)
The right-hand side of ( 4) is also (a shifted version of) Weyl's dimensional formula for the character γ λ corresponding to the irreducible representation of highest weight λ = (m/2) of the odd orthogonal group O 2n+1 (C).Using a combinatorial interpretation by Seshadri coming from algebraic geometry, Macdonald's identity (4) is evident in Proctor's work and further generalized by Krattenthaler. It relies on the "branching rule" for the restriction of a representation of o(2n + 1) to a subalgebra sl(n). However, no direct combinatorial proof is known relating the semi-standard Young tableaux of n letters which fit into the (m n ) rectangle, and the combinatorial interpretation of the orthogonal characters, coming from the SO 2n-1 → SO 2n+1 branching rule, which corresponds to certain "half" Gelfand-Tsetlin triangles.

In order to take advantage of some established relationships between symplectic characters and Schur functions from [GP], we express (using Weyl's character formula), φ m as a ratio of symplectic characters. Denote τ r = ((r/2 -1/2) n ). After certain algebraic manipulations we derive the special moment generating function (m.g.f.) for tilings from T f (n, m), whose role will become evident later:

( ) Φ m (x 1 , . . . , x k ; n) = φ m (x 1 , . . . , x k , 1 n-k ) φ m (1 n ) = k i=1 x m 2 i X τ m (x 1 , . . . , x k ; n) X τ 0 (x 1 , . . . , x k ; n) .
3 Asymptotics I: when lim n→∞ m n ∈ (0, +∞)

We derive the asymptotic behavior for the normalized symplectic characters and so via ( ) for Φ.

Proposition 3.1 When m n → a for 0 < a < ∞ we have that

X τ m (e h √ n ; n) = exp 1 4 (a 2 + a)h 2 + o(1) and X τ 0 (e h/ √ n ; n) = 1 + o(1),
where the error terms o(1) converge to 0 uniformly on compact real domains for h.

Proof sketch: Using Proposition 2.1 we derive asymptotic formulas for S ν m (e h √ 2n ; 2n, 1) when m/n → a = 0, ∞ and also when m = 0. In the m = 0 case we apply the formula 2.2 directly, in the m = 0 we use the integral formula for the normalized Schur functions from [START_REF] Gorin | Asymptotics of symmetric polynomials with applications to statistical mechanics and representation theory[END_REF]Section 3.2] to derive that S λ (x; N ) = S λ (x 1/β ; N ) for λ i = βλ i + (β -1)(Ni) and then apply the same analysis with ν 0 which now satisfies the conditions in Proposition 2.2.

2 Proposition 3.2 Let {a i } ∞ i=1 , {b i } ∞ i=1 be
; N ) e b N (y1+•••+y k ) = g(y 1 ) • • • g(y k )
uniformly on compact subsets of D k . This result will be used primarily for a N = 1/ √ N and b N = 0 in the case when m/n is bounded nonzero, and later in Section 6 with a n = √ n m and b n = 0 when m/n → ∞. The proof uses formula (3) with certain substitutions and bounds on the derivatives, and will be omitted in this abstract.

Proposition 3.3 Suppose that λ(N ) is a sequence of signatures, such that ln X λ(N ) (u; N ) N → X(u) , as N → ∞
, where the convergence is uniform in a complex neighborhood of u = 1. Then

ln X λ(N ) (u 1 , . . . , u k ; N ) N → X(u 1 ) + • • • + X(u k )
as N → ∞, where the convergence is uniform in a neighborhood of (1 k ) in C k .

Proof sketch:

The proof uses the observation that

∂ ∂u j X λ (u; N ) X λ (u; N ) ∈ Z ∂ ∂u ln X λ (u; N ), . . . , ∂ j ∂u j ln X λ (u; N ) , i.e.
it lhs is a degree j polynomial in the given ring. This allows us to apply formula (3) with suitable substitutions/normalizations. 2

Applying the asymptotic results above together with equation ( ) gives the following.

Theorem 3.4 For any fixed y 1 , y 2 , . . . , y k ∈ R we have that

Φ m (e y1/ √ n , . . . , e y k / √ n ; n) exp -( m 2 √ n ) k i=1 y i → exp 1 16 (a 2 + 2a) i y 2 i + o(1) ,
as n → ∞, m/n → a, uniformly over (h 1 , . . . , h k ) belonging to compact domains of (R \ 0) k .

Convergence to the GUE-corners process

We In order to prove the convergence to GUE we use moment generating functions. Introduce the multivariate normalized Bessel function in (x; y) = (x 1 , . . . , x k ; y 1 , . . . , y k ), defined as

B k (x; y) = det [exp(x i y i )] k i,j=1 i<j (x i -x j ) i<j (y i -y j ) i<j (j -i) = s y-δ k (e x ) s y-δ k (1 k ) ∆(e x ) ∆(x) ,
where

δ k = (k -1, k -2, . . . , 1, 0) and ∆(z) = i<j (z i -z j ) is the Vandermonde determinant. Let GUE k denote the k eigenvalues ε 1 ≥ ε 2 ≥ • • • ≥ ε k of a random
Hermitian k × k matrix from a Gaussian Unitary Ensemble. The idea is to show that the m.g.f. EB k for the uniformly random lozenge tilings from T f (n, m) converges to the corresponding m.g.f. for GUE k , computed in [START_REF] Gorin | Asymptotics of symmetric polynomials with applications to statistical mechanics and representation theory[END_REF]Prop 5.6] as:

EB k (x; GUE k ) = exp 1 2 (x 2 1 + • • • x 2 k ) . (5)
Proposition 4.1 We have that the expectation of B k (x; Y k n,m ), where Y k n,m is the k-tuple of the positions of the horizontal lozenges at line k of a tiling chosen uniformly from T f n,m , is given by

EB k x; Y k n,m -m/2 √ n = k i=1 exp(- m 2 √ n x i )Φ m (e x1/ √ n , . . . , e x k / √ n ; n) ∆(e x/ √ n ) ∆(x/ √ n) .
Proof: First, we calculate the probability that {y k j } are the positions of the horizontal lozenges on the k-th vertical line of a uniformly random tiling fromT f n,m . Tilings in T f n,m are in bijection with Gelfand-Tsetlin patterns of n rows and entries no larger than m. Those, on the other hand, are in bijection with semistandard Young tableaux (SSYT) T filled with the numbers 1, . . . , n and shapes λ (corresponding to the positions of the right-most horizontal lozenges as in Figure 1) that fit in the m n rectangle, i.e. λ 1 ≤ m.

The positions of the horizontal lozenges on the k-th vertical line are simply the entries on the k-th row of the Gelfand-Tsetlin pattern. These correspond to the sub-tableaux of T occupied by the entries which are no larger than k. See Figure 2.

2 0 3 0 1 3 0 0 3 3 0 0 3 3 4 ⇔ T =
1 1 2 5 3 4 4 5 5 5

Fig. 2: The correspondence between the k-th line of a Gelfand-Tsetlin pattern and sub-tableau of an SSYT consisting of the entries ≤ k. Here λ = (4, 3, 3, 0, 0) and y 3 -δ3 = (3, 1, 0).

The total number of tilings in T f n,m is equal to the total number of SSYTs with entries 1, . . . , n and shapes fitting inside m n . The number of SSYTs with entries 1, . . . , n of a given shape λ is just s λ (1, . . . , 1 n ) and so the total number of tilings in T f n,m is exactly φ m (1, . . . , 1 n

). The number of tilings whose horizontal lozenges on the k-th diagonal are at positions y k = (y k 1 , . . . , y k k ), via the bijection with SSYTs described above, is equal to

λ⊂(m n ) s y k -δ k (1, . . . , 1 k )s λ/(y k -δ k ) (1, . . . , 1 n-k
) and thus the probability of the positions of the horizontal lozenges on the k-th vertical line being y k is just that last quantity divided by φ m (1 n ). Using the formula for B k as ratio of Schur functions, we get

B k (x; y k -m 2 √ n ) ∆(x/ √ n) ∆(e x/ √ n ) = i exp(- x i m 2 √ n )s y k -δ k (E x 1 √ n , . . . , e x k √ n )/s y k -δ k (1 k ).
By the combinatorial description of Schur functions, for two alphabets z, w we have that

s α (z, w) = β s β (z)s α/β (w),
which we apply with α = λ, β = y kδ k , w = 1 n-k and z = e x/ √ n :

EB k x; Y k n,m -m/2 √ n ∆(x/ √ n) ∆(e x/ √ n ) = y k B k (x; y k -m 2 √ n ) λ⊂(m n ) s y k -δ k (1 k )s λ/(y k -δ k ) (1 n-k ) φ m (1 n ) = y k i exp(- x i m 2 √ n ) s y k (e x 1 √ n , . . . , e x k √ n ) s y k -δ k (1 k ) s y k -δ k (1 k ) λ⊂(m n ) s λ/(y k -δ k ) (1 n-k ) φ m (1 n ) = i exp(- x i m 2 √ n ) 1 φ m (1 n ) λ⊂(m n ) s λ (e x 1 √ n , . . . , e x k √ n , 1, . . . , 1 n-k ) = i exp(- x i m 2 √ n )Φ m (e x 1 √ n , . . . , e x k √ n ; n). 2
Lemma 4.2 As n, m → ∞ with m/n → a, we have that

EB k x; Y k n,m -m/2 √ n → exp 1/16(a 2 + 2a)(x 2 1 + • • • x 2 k )
Proof: This is a direct consequence of Proposition 4.1, the asymptotics of Φ m from Theorem 3.4 and the fact that

∆(x/ √ n) ∆(e x/ √ n ) → 1 uniformly on compact neighborhoods of x as n → ∞. 2 Theorem 4.3 We have that, as n, m → ∞ with m/n → a for a > 0, Y k n,m -m/2 n(a 2 + 2a)/8 → GUE k
in the sense of weak convergence of random variables. Moreover, the so-rescaled positions of the horizontal lozenges on the first k vertical lines, i.e.

Y j n,m -m/2 √ n(a 2 +2a)/8 k j=1
weakly converge as random variables to the collection of eigenvalues {ε j } k j=1 of the principle submatrices from a k × k matrix from the GUE ensemble, where {ε j } are the eigenvalues of the submatrix formed by the first j rows and columns.

Proof sketch:: It is a classical result, following Lévy's continuity theorem, that if the moment generating functions (MGF) E[e Xit ], i = 1, . . . of a sequence of random variables {X i } i=1,... converge uniformly in a compact domain of t to the MGF of a given random variable X, then X i → X in distribution (i.e. weakly). This statement easily generalizes when replacing the random variables by vectors of random variables and MGF by EB k . This fact applies to the sequences Y k n,m since

EB k x; Y k n,m -m/2 n(a 2 + 2a)/8 = EB k x (a 2 + 2a)/8 ; Y k n,m -m/2 √ n → exp 1 2 (x 2 1 + • • • x 2 k ) = EB k (x; GUE k ),
where B k (x; yα) = B k (αx; y) for any constant α and Lemma 4.2 gives the asymptotics.

The convergence of the entire collection of horizontal positions

Y j n,m -m/2 √ n(a 2 +2a)/8 k j=1
to the collection of eigenvalues of all the principal submatrices follows from the Gibbs property satisfied by both collections: given the vector Y k n,m , the distribution of the horizontal lozenges on the first k -1 vertical lines is clearly uniform subject to the interlacing conditions; the same holds for the eigenvalues {ε j } k-1 j=1 given ε k , which are again subject to the interlacing conditions, i.e.

ε j i-1 ≥ ε j-1 i-1 ≥ ε j i (see [Baryshnikov]). 2
We can now compare the results for the free boundary case and the hexagon by comparing with the results for the hexagon implicit or explict in [GP] and [Johansson-Nordenstam, Nordenstam, Novak], which proves the first claim of the Main Theorem.

Limit shape

We now show the existence of a limit shape for the height function (alternatively, the symmetric plane partition) of the tilings with free boundary, which does not follow immediately from other previously considered cases.

We prove that the positions of the horizontal lozenges at any vertical line x = αn, given by a signature (partition) µ αn , converge to a "limit shape" in the following sense. This means that there is a monotone piecewise continuous function f α (t) : [0, b] → R for some sufficiently large b, such that

lim n→∞ µ αn i + αn -i αn → f i αn
in probability (see e.g. [KOS, Section 6.2]), where µ αn is now a random signature of length αn, according to some probability measure on signatures. Moreover, the "limit shape" of the random tilings as n → ∞ should be a function H : R 2 → R. At a point (α, t), this is H(α, t) = f α (t). For any signature λ of length N , define the the counting measure

m[λ] = 1 n N i=1 δ λ i + N -i N ,
where δ is the Dirac delta measure. Clearly, m[λ] is a compactly supported probability measure.

As shown in [START_REF] Borodin | Limit shapes for growing extreme characters of U (∞)[END_REF]Proposition 2.2], if we prove that the sequence of random measures µ N converge to a deterministic probability measure m, this automatically implies the convergence of the limit shape, which is then simply the distribution function of m. Following ideas from [BG] we now prove such convergence.

For any real α ∈ (0, 1) and signature λ of n parts, define for any signature µ = (µ 1 ≥ • • • ≥ µ αn ) of αn parts, the following probability

P α m,n (µ) = λ:λ1≤m s λ/µ (1 n-αn )s µ (1 αn ) λ:λ1≤m s λ (1 n ) . ( 6
)
Combinatorially this is the probability that a random SSYT with at most m columns and N letters will have the first αn letters forming an SSYT of shape µ. Thus, it is evident that summing over all possible shapes µ, we obtain all SSYT of shape λ and n letters, and thus P α,λ is a probability measure on the signatures of length αn . Finally, for any probability measure ρ on the set of signatures of length N , define the GL N -character generating function

S ρ (u 1 , . . . , u N ) = µ: (µ)=N ρ(µ) s µ (u 1 , . . . , u N ) s µ (1 N ) .
Given a probability distribution ρ on signatures λ, we denote (by a slight abuse of notation, to agree with [BG]) by m[ρ] the random counting measures m[λ], where λ ∼ ρ.

We will apply the following result, proven in [BG] and inspired by [BBO].

Theorem 5.1 (Theorem 5.1 in [BG]) For each N , let ρ N be a measure on the set of signatures of length N . Suppose that for every k

lim N →∞ 1 N ln S ρ N (u 1 , . . . , u k , 1 N -k ) = Q(u 1 ) + • • • + Q(u k ),
where Q is an analytic function in a neighborhood of 1 and the convergence is uniform in an open (complex) neighborhood of (1, . . . , 1). Then the random pushforward measures m[ρ N ] converge, as N → ∞, in probability, in the sense of moments, to a deterministic measure M on R, whose moments are given by

R x r M (dx) = r =0 r 1 ( + 1)! ∂ ∂u Q(u) u=1
We apply this theorem to the measure ρ = P α m,n . This measure is the distribution of the partition µ, which represents the positions (height function) of the horizontal lozenges at the vertical line k = αn, i.e. y k as in Section 4 (see Figure 1), of a uniformly random lozenge tiling from T f (n, m). We have that N = αn , and then compute as in Section 4

S P α m,n (u 1 , . . . , u N ) = µ: (mu)=N P α m,n (µ) s µ (u 1 , . . . , u N ) s µ (1 N ) = µ: (µ)=N λ:λ1≤m s λ/µ (1 n-N )s µ (1 N ) λ:λ1≤m s λ (1 n ) s µ (u 1 , . . . , u N ) s µ (1 N ) = Φ m (u 1 , . . . , u N ; n) (7)
Proposition 5.2 Let m, n → ∞ with m/n → a, where a is a positive real number. Then for any fixed k, we have lim

n→∞ 1 n ln Φ m (u 1 , . . . , u k ; n) = Ψ a (u 1 ) + • • • + Ψ a (u k ),
where Ψ a (e y ) = y a 2 + 2φ(y; a) -2 and φ is defined as follows h(y) = 1 4 (e y + 1) + (e y + 1) 2 + (a 2 + 2a) (e y -1)

2 φ(y; a) = a 4 + 1 ln h(y) - a 4 + 1 (e y -1) - a 4 + 1 2 ln h(y) - a 4 + 1 2 (e y -1) + a 4 ln h(y) + a 4 (e y -1) - a 4 - 1 2 ln h(y) + a 4 - 1 2 (e y -1) (8)
Proof sketch: Using the formula for Φ in terms of X, we find the asymptotics for X in the given regime.

Using the relationship to S, we first compute lim By Prosition 2.1, the same limits hold when replacing S ν by the corresponding X τ for one variable. Proposition 3.3, we obtain the corresponding limit for the multivariate characters X τ m and X τ 0 .

Theorem 5.3 Let n, m ∈ Z, such that m/n → a as n → ∞, where a ∈ (0, +∞). Let H(u, v) be the height function of the uniformly random lozenge tiling in T f (n, m) (alternatively, the value of the square in the corresponding plane partition at position (v, uv) with (0, 0) at the lower left corner). Then as n → ∞, for all x ∈ (0, 1), y ≥ 0 the normalized 1 n H(nx, ny) converges in probability to a deterministic function L(x, y), referred to as "the limit shape".

Moreover, for any fixed x ∈ (0, 1), the function L(x, y) is the distribution function of the limit measure M whose moments are given by R

x r M (dx) = r =0 r 1 ( + 1)! ∂ ∂u Ψ a (u) u=1 ,
where Ψ a (u) is defined in Proposition 5.2.

Proof: The distribution ρ n (µ) = P α m,n (µ) defined in equation ( 6) is a probability distribution on the set of signatures of length αn , as explained there. Further, the corresponding GL n -character generating function S ρ n is, by equation ( 7), equal to Φ m . By Proposition 5.2, this S ρ n satisfies the conditions of Theorem 5.1, so the random measures m[µ], defined by the random signatures µ distributed according to P α m,n , converge in probability to a deterministic measure M , defined accordingly through its moments. Finally, Theorem 5.3 applies to this measure M and we obtain the desired limit of the height function L(x, y), which is given as the distribution function of M . 2

To show the Main Theorem, we can compare this result to the analogous statement for the full hexagon: either by the same methods show that it's deterministic measure M has the same moments or compare with the present results from [BG, CLP, CKP].

6 Asymptotics II: when lim n→∞ m n = 0, ∞ So far, for reasons concerning the physics nature of the models, the interest has been in studying the "scaling limits" of lattice models, in which the scaling factors are the same in all directions. Here we consider other regimes, in which the scalings in the different directions differ in growth order. For example, the vertical scaling could be proportional to m ∼ √ n and the horizontal is n. We consider again the positions of the horizontal lozenges near the boundary, where now it is not a priori obvious what their correct scaling should be, in order to get a limiting distribution for Y k n,m as m, n → ∞. The following propositions are complementary to Theorem 4.3.

  sequences of positive real numbers, such that a N → 0 and b N N → 0 as N → ∞. Suppose that for some number b we have X λ(N ) (e a N y ; N ) e b N y → g(y) uniformly on compact subsets of a domain D ⊂ C as N → ∞. Then lim N →∞ X λ(N ) (e y1a N , . . . , e y k a N

  now consider the joint distribution of the positions of the horizontal lozenges closest to the left flat boundary of the domain. Let Y k n,m denote the k-tuple Y k n,m = y k 1 , y k 2 , . . . , y k k , where y k = {y k j } are the positions of the horizontal lozenges on the k-th vertical line a uniformly random tiling T f n,m , as depicted in Figure 1. We show that the joint distribution of the ensemble [Y 1 n,m , . . . , Y k n,m ], shifted by m/2 and rescaled by a factor of √ n, converges to the GUE-corners process.

N

  →∞ ln S ν m (e y ; N ) N = φ(y; a) -1. Since both sides are analytic around y = 0, the equality extends to a neighborhood of 0. In the case of m = 0, i.e. for f 0 we calculate directly using the same methods (also justified in [GP, Example 1]) lim N →∞ ln S ν 0 (e y ; N ) N = 0.

Proposition 6. 1

 1 Suppose that m, n → ∞ with m/n → ∞, and suppose that n 2 m = o(1). Then the shifted rescaled positions (Y k n,m ) of the horizontal lozenges on the kth vertical line satisfy: Let n, m → ∞, such that n/m → ∞. ThenY k n,mm/2 2 √ m → GUE kand the collection of shifted rescaled positions of the horizontal lozenges on lines 1, . . . , k converges to the k × k GUE-corners process.

Acknowledgements

We would like to thank Philippe Di Francesco for asking the author about GUE in the free boundary tilings. We also thank Alexei Borodin, Vadim Gorin, Christian Krattenthaler and Nicolai Reshetikhin for helpful discussions on further problems and the background literature. The author was partially supported by a Simons postdoctoral fellowship while doing this work at UCLA.


Louis-Franc ¸ois Préville-Ratelle

Xavier Viennot
email: viennot@xavierviennot.org

An extension of Tamari lattices

Keywords: Tamari lattice, m-Tamari lattice, rational Catalan combinatorics, diagonal coinvariant spaces

For any finite path v on the square lattice consisting of north and east unit steps, we construct a poset Tam(v) that consists of all the paths lying weakly above v with the same endpoints as v. For particular choices of v, we recover the traditional Tamari lattice and the m-Tamari lattice. In particular this solves the problem of extending the m-Tamari lattice to any pair (a, b) of relatively prime numbers in the context of the so-called rational Catalan combinatorics.

For that purpose we introduce the notion of canopy of a binary tree and explicit a bijection between pairs (u, v) of paths in Tam(v) and binary trees with canopy v. Let ←v be the path obtained from v by reading the unit steps of v in reverse order and exchanging east and north steps. We show that the poset Tam(v) is isomorphic to the dual of the poset Tam( ←v ) and that Tam(v) is isomorphic to the set of binary trees having the canopy v, which is an interval of the ordinary Tamari lattice. Thus the usual Tamari lattice is partitioned into (smaller) lattices Tam(v), where the v's are all the paths of length n -1 on the square lattice.

We explain possible connections between the poset Tam(v) and (the combinatorics of) the generalized diagonal coinvariant spaces of the symmetric group.

Résumé. Pour tout chemin v sur le réseau carré formé de pas Nord et Est, nous construisons un ensemble partiellement ordonné Tam(v) dont les éléments sont les chemins au dessus de v et ayant les mêmes extrémités. Pour certains choix de v nous retrouvons le classique treillis de Tamari ainsi que son extension m-Tamari. En particulier nous résolvons le problème d'étendre le treillis m-Tamari à toute paire (a, b) d'entiers premiers entre eux dans le contexte de la combinatoire rationnelle de Catalan.

Pour ceci nous introduisons la notion de canopée d'un arbre binaire et explicitons une bijection entre les paires (u, v) de chemins dans Tam(v) et les arbres binaires ayant la canopée v. Soit ←v le chemin obtenu en lisant les pas en ordre inverse et en échangeant les pas Est et Nord. Nous montrons que Tam(v) est isomorphe au dual de Tam( ←v ) et que Tam(v) est isomorphe à l'ensemble des arbres binaires ayant la canopée v, qui est un intervalle du treillis de Tamari ordinaire. Ainsi le traditionnel treillis de Tamari admet une partition en plus petits treillis Tam(v), où les v sont tous les chemins de longueur n -1 sur le réseau carré. Enfin nous explicitons les liens possibles entre l'ensemble ordonné Tam(v) et (la combinatoire des) espaces diagonaux coinvariants généralisés du groupe symétrique.

Introduction

In this paper, we generalize the m-Tamari lattice to posets of arbitrary paths, as it is explained in section 2. We prove that these posets are actually lattices, that they satisfy a duality property, and that they partition the ordinary Tamari lattice into intervals. We first introduce some basic definitions in section 1.1 and some motivations in section 1.2.

Basic definitions

A binary tree is either empty or a triple (L, r, R) where L and R are binary trees (left and right subtrees) and r is the root of the binary tree. If L (resp. R) is not empty, its root is called the left (resp. right) child of r. A binary tree is complete when all vertices have either two children (internal vertices) or no child (external vertices). Figure 1 displayed the classical bijection between binary trees and complete binary trees. We denote by B the complete binary tree associated to B. . We now define the Tamari lattice. The complete binary trees with n interior vertices can be equipped with a rotation. As in Figure 1, consider a complete binary tree T with an internal vertex s such that the left child of s, denoted by t, is also an internal vertex. Let A be the left subtree of t, B the right subtree of t and C the right subtree of s. Let T be the complete binary tree constructed from T such that t becomes the right child of s, A the left subtree of s, B the left subtree of t and C the right subtree of t. This operation from T to T is called a right rotation, and the operation from T to T is called a left rotation. The right rotation define the covering relation of the well known Tamari lattice (see [START_REF] Tamari | The algebra of bracketings and their enumeration[END_REF][START_REF] Friedman | Problèmes d'associativité: une structure de treillis fini induite par une loi demi-associative[END_REF] ), denoted by T ≺ T .

In this article, we consider a path to be a (finite) walk on the square lattice, starting at (0,0), consisting of north and east unit steps denoted by N and E respectively. The set of ballot paths of height n is the set of paths that consist of n north steps, n east steps and lie weakly above the diagonal, that is, weakly above the path (N E) n . They are also counted by the Catalan numbers. By applying a clockwise rotation of 45 degrees on ballot paths so that the diagonal becomes horizontal, these ballot paths become the well known Dyck paths (see Figure 2). The ballot paths can be generalized with a parameter m that is a positive integer. The m-ballot paths are the paths that consist of n north steps, mn east steps and lie weakly above the line y = x m , that is, weakly above the path (N E m ) n . Using the bijection between complete binary trees with n internal vertices and ballot paths of height n, which is called the postorder traversal on edges, the covering relations for the Tamari lattice can be translated into the following procedure on ballot paths. Let D be a ballot path of height n. Let E be an east step that precedes a north step in D. Draw a diagonal of slope 1 starting at the right extremity of E until it touches D again. Construct D from D by switching E and the portion of the path above this diagonal. Then the covering relation in the Tamari lattice based on ballot paths becomes D ≺ D (see Figure 3 for such a covering relation). Motivated by the higher diagonal coinvariant spaces of the symmetric group, the covering relation on ballot paths is generalized in [START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF] to m-ballot paths by mimicking the above procedure as follows. Let D be an m-ballot path. Let E be an east step that precedes a north step in D. Draw a diagonal of slope 1 m starting at the right endpoint of E until it touches D again. Construct D from D by switching E and the portion of the path above this diagonal. Then the covering relation in the m-Tamari lattice is given by D ≺ D (see Figure 3 for an example). For more on these lattices and for enumerations of their intervals, we refer the reader to section 5.

Rational Catalan combinatorics (a, b)

Let a and b be two relatively prime integers. We consider paths starting at (0, 0) on the square lattice with north and east steps and strictly above the line y = a b x, excluding the start and end points (see [START_REF] Bizley | Derivation of a new formula for the number of minimal lattice paths from (0, 0) to (km, kn) having just t contacts with the line my = nx and having no points above this line; and a proof of Grossman's formula for the number of paths which may touch but do not rise above this line[END_REF]). They are called (a, b)-ballot paths (or (a, b)-Dyck paths), and their study is the subject of very recent work under the term "rational Catalan combinatorics" (see [START_REF] Armstrong | Rational associahedra and noncrossing partitions[END_REF][START_REF] Armstrong | Rational parking functions and Catalan numbers[END_REF][START_REF] Gorsky | Refined knot invariants and Hilbert schemes[END_REF][START_REF] Gorsky | Affine permutations and rational slope parking functions[END_REF][START_REF] Hikita | Affine Springer fibers of type A and combinatorics of diagonal coinvariants[END_REF] for more on this subject). An open question is to give an extension of the Tamari lattice, and more generally of the m-Tamari lattice to any pair (a, b) of relatively prime integers. We propose an answer to this question, by giving a far more general extension of these Tamari lattices and in particular give a construction of a rational (a, b)-Tamari lattice.

2 Extension: The Tamari lattice Tam(v), where v is an arbitrary path

Let v be an arbitrary path, starting at (0,0). Consider all the lattice paths lying weakly above v that start at (0,0) and finish at the end of v. We define the poset Tam(v) on this set of paths with a covering relation.

Let u be such a path above v. Let p be a lattice point on u. We define the horizontal distance horiz v (p) to be the maximum number of east steps that can be added to the right of p without crossing v. An example of these horizontal distances is given in Figure 4 (left). Suppose that p is preceded by an east step E and For v an arbitrary path, let ←v be the path obtained by reading v backward and replacing the east steps by north steps and vice versa. We can now state our main results:

Theorem 1 For any path v, Tam(v) is a lattice.
Recall from the first section that the usual Tamari lattice on complete binary trees with n interior vertices is isomorphic to the lattice Tam((N E) n ).

Theorem 2 The lattice Tam(v) is isomorphic to the dual of Tam( ←v ).

For any pair (a, b) of relatively prime integers, we define the lattice Tam(a, b) as to be the lattice Tam(v) where v is the minimum path above the segment passing through the origin (0, 0) and the point (a, b). The duality between Tam(v) and Tam( ←v ) becomes the duality between Tam(a, b) and Tam(b, a) (see Figure 5). In this

T am((N E)

n ) = |v|=n-1 I(v),
where each I(v) ∼ = T am(v).

An example of Theorem 3 is given in Figure 6.

Canopy of a binary tree

For any binary tree B, we construct a word w(B) on the alphabet {a, ā, b, b}. Walking clockwise around B and starting at the root, we write the letter a when we walk on a left edge for the first time and ā when we walk on a left edge for the second time. Similarly we repeat with the letters b and b for the right edges (see Figure 7 (left) for an example). the two letters {ā, b} in w(B). We identify a path with u(B) by replacing in this sequence the letter ā by a north step and b by an east step. The canopy v(B) of B, which is also a subword of w(B), is obtained similarly by keeping track only of the letters {ā, b}. We identify a path with v(B) by replacing in this sequence the letter ā by a north step and b by an east step (i) . The concept of the canopy was introduced using a different terminology in [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF]. For the binary tree in Figure 7 (left), we show an example of all these words in Figure 8 (left) and draw the paths u(B) and v(B) in Figure 8 (right).

It is no accident that we use the same letter v for the canopy as the letter that defines the poset in the previous section. Before explaining this, we can mention an easy property: Lemma 4 For any given binary tree B, the path u(B) is weakly above the canopy (also a path) v(B).

Let B be a complete binary tree with n vertices. It is not difficult to prove that the canopy can also be defined using the following equivalent definition.

The second definition of the canopy, which is defined in [START_REF] Loday | Hopf algebra of the planar binary trees[END_REF], can be described as follows. Walking around B clockwise starting at the root, record the sequence of left and right external edges, except the first and last external edges. From this sequence, construct a path by changing the right external edges into north steps and the left external edges into east steps. The path obtained is also the canopy (see Figure 7 (right) for an example). Because of this definition, we define the interior canopy of the complete binary tree B to be the canopy of B.

In the proofs of the main theorems, we need a third definition of the canopy. We do not explicit its definition here. It is based on ordering the vertices of the binary tree B in the so-called symmetric order (also called infix or in-order), and considering a certain order on the left edges of B. The sequence of "right heights" of these left edges is related to the sequence of distances between the pairing vertical edges of the paths u and v (the labels of the path v in Figure 9).

Proofs of the main theorems

The proofs of the main theorems rely on the following 3 propositions.

(i) So by abuse of notation, we will refer to the paths u(B) and v(B).

Proposition 5

The map defined in Section 3 associating the pair (u, v) to a binary tree is a bijection from the set of binary trees with n vertices to the set of unordered pairs of non-crossing paths, consisting each of a total of n -1 north and east steps, with the same endpoints.

The bijection between binary trees and pairs of paths (u, v) was introduced in a different form ( [START_REF] Delest | Algebraic languages and polyominoes enumeration[END_REF], [START_REF] Viennot | Canopy of binary trees, intervals in associahedra and exclusion model in physics, Workshop[END_REF] slides 42-53). We have described here a new version of the bijection which fits our purpose. We describe the reverse bijection in terms of a "push-gliding algorithm", which is a kind of "jeu de taquin" on a binary tree attached to a path. The algorithm starts with an empty binary tree and the path v where the vertical edges are labeled by the horizontal distance to the path u. Reading the path v, from bottom to top, sliding is performed according to each labeled vertical edge and pushing according to each horizontal edge. For each pushing, a new edge is introduced in the binary tree attached to the path. At the end the path is empty and we get the binary tree related to pair (u, v), (see Figure 9). This proposition is well known, see for example Proposition 3.5 in [START_REF] Loday | Order structure on the algebra of permutations and of planar binary trees[END_REF] where the Boolean lattice appears as a quotient of the Tamari lattice. The intervals I(v) are the fibres over points of the usual map from the Tamari lattice to the Boolean lattice. These intervals can also be viewed as the images under the map from the symmetric group to the Tamari lattice of the set of permutations with a fixed descent set.

Here we give a direct combinatorial proof. The max and min element of the interval can be defined easily from the "push-gliding" algorithm mentioned above.

Proposition 7 For any path v, the poset I(v) is isomorphic to Tam(v).

The proof relies on a lemma relating the sequence of horizontal distances horiz v (p) of the vertices p of the path u to the sequence of right heights of the vertices of the corresponding binary tree B when traversed in postorder. Then the proof continues by studying the relation between the canopy and the rotation in binary tree. For binary trees with a given canopy, the rotations are restricted, and such rotations can be shown to be equivalent to the covering relation for Tam(v) using the lemma mentioned previously.

We can now prove our main theorems of section 2.

Proof of Theorem 1: An interval of a lattice is always a lattice, therefore I(v) is a lattice by Proposition 6, and so is Tam(v) by Proposition 7. 2

Proof of Theorem 2: After applying a reflection to a binary tree with canopy v, it is easy to see using the second definition of canopy, that the canopy of this tree (obtained by reflection) is precisely ←v . The left and right rotation on a complete binary tree are exchanged and we deduce from the constructions of Tam(v) and Tam( ←v ) that these lattices are isomorphic up to duality (also called anti-isomorphic). 2

Proof of Theorem 3: We partition the complete binary trees with n interior vertices into sets of trees with the same interior canopy. We then apply Proposition 7 to each set of trees. 2

5 Connections with the diagonal coinvariant spaces and perspectives

Our work has been influenced by the combinatorics of the "generalized" diagonal coinvariant spaces of the symmetric group. We give a brief description of the subject here, and refer the reader to [START_REF] Bergeron | Algebraic combinatorics and coinvariant spaces[END_REF][START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF][START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF][START_REF] Bousquet-Mélou | The representation of the symmetric group on m-Tamari intervals[END_REF][START_REF] Haglund | The q,t-Catalan numbers and the space of diagonal harmonics[END_REF] for more details. Let X = (x i,j )1≤i≤k 1≤j≤n be a matrix of variables. A permutation σ of the symmetric group S n permutes the variables columnwise by σ(X) = (x i,σ(j) )1≤i≤k 1≤j≤n , i.e. σ(x i,j ) = x i,σ(j) . This action can be directly extended to all the polynomials in C[X]. All the variables in a same row of X are said to be contained in the same set of variables. Since X contains k rows, there are k sets of variables. Let J be the ideal generated by constant free invariant polynomials under this action. The diagonal coinvariant spaces of S n are defined as DR k,n := C[X] J . They can be generalized using an additional parameter m that is a positive integer. The higher diagonal coinvariant spaces of the symmetric group are defined as

DR m k,n := ε m-1 ⊗ A m-1 J A m-1
, where is the sign representation and A is the ideal generated by alternants, i.e. polynomials f (X) such that σf (X) = ε(σ)f (X), ∀σ ∈ S n . Note that DR k,n = DR 1 k,n . The DR m k,n are representations of S n because the action given above can be applied to the quotient space DR m k,n . They are graded with respect to the degree of each set of variables. We denote the subspace of alternants of DR m k,n by DR m k,n ε .

In the case k = 1, they are classical [START_REF] Steinberg | Differential equations invariant under finite reflection groups[END_REF] and the dimensions of DR m 1,n ε and DR m 1,n are given by 1 and n!, respectively.

In the case k = 2, they were first defined and studied by Garsia and Haiman because of their connections with the Macdonald polynomials. It was proven by Haiman [18] that the dimensions of DR m The spaces DR m 2,n have been studied by many researchers for more than 20 years. Despite that, there are still some important unresolved conjectures left in the field. We mention only one here. The m-shuffle conjecture [START_REF] Haglund | A combinatorial formula for the character of the diagonal coinvariants[END_REF] states that the graded Frobenius series of DR m 2,n is equal to a q, t-weighted sum on mparking functions, which involves the combinatorial statistics area and dinv, and some quasi-symmetric functions associated to these m-parking functions.

For the case k = 3, Haiman [START_REF] Haiman | Conjectures on the quotient ring by diagonal invariants[END_REF] conjectured in the 1990's that the dimensions of DR 3,n ε and DR 3,n are equal to 2 n(n+1)

4n + 1

n -1 and 2 n (n + 1) n-2 respectively. Independently of all this story, Chapoton [START_REF] Chapoton | Sur le nombre d'intervalles dans les treillis de Tamari[END_REF] proved in 2006 that the number of intervals in the Tamari lattice based on complete binary trees with n interval vertices is given by

2 n(n+1) 4n + 1 n -1 .
In 2008, the m-Tamari lattice was introduced in [START_REF] Bergeron | Higher trivariate diagonal harmonics via generalized Tamari posets[END_REF] and it was conjectured that the number of intervals and labelled intervals in the m-Tamari lattice are given by m+1 n(mn+1)

(m + 1) 2 n + m n -1
and (m + 1) n (mn + 1) n-2 , respectively. A labelled interval in the m-Tamari lattice is simply an interval where the top path is decorated as a m-parking function. Refinements of these two results were proven in [START_REF] Bousquet-Mélou | The number of intervals in the m-Tamari lattices[END_REF][START_REF] Bousquet-Mélou | The representation of the symmetric group on m-Tamari intervals[END_REF].

The duality that is proved in this article shows that the number of intervals in Tam((N m E) n ) is the same as in the m-Tamari lattice Tam((N E m ) n ). Using refinements and calculations, it seems that the number of labelled intervals in Tam((N E m ) n ) is equal to the number of labelled intervals on east steps in Tam((N m E) n ), where the labelled intervals on east steps are defined by assigning the labels in the set {1, 2, ..., n} on east steps of the upper path, and such that the labels on consecutive east steps are increasing. Note that for m = 1, this is easy to prove since you can obtain without difficulty the same functional equations for both cases from recurrences. But we have not been able to do so in the case m > 1. It would be interesting to see if the ideas presented in [START_REF] Chatel | Counting smaller elements in the Tamari and m-Tamari lattices[END_REF] could help prove this equality.

More recently, some researchers (see [START_REF] Armstrong | Rational Catalan Combinatorics, Personal website[END_REF][START_REF] Armstrong | Rational associahedra and noncrossing partitions[END_REF][START_REF] Bergeron | Compositional (km, kn)-shuffle conjectures[END_REF][START_REF] Hikita | Affine Springer fibers of type A and combinatorics of diagonal coinvariants[END_REF]) have extended the combinatorics of the DR m 2,n by considering paths and parking functions above the line with endpoints (0,0) and (b, a), where a, b are arbitrary positive integers (ii) . They defined the combinatorial statistics area and dinv on these objects. So this rational Catalan combinatorics can be seen as the combinatorics of some possible generalizations of the spaces DR m 2,n . Even though these spaces have not yet been shown to exist, some preliminary calculations [START_REF] Bergeron | Compositional (km, kn)-shuffle conjectures[END_REF] suggest that they do. One might try now to define a dinv statistic on paths and parking functions above an arbitrary path consisting of east and north steps, even if it is not known to be possible.

It remains to be seen if our lattices Tam(v), for arbitrary paths v, will give a combinatorial setup for the not yet defined generalizations (iii) of the spaces DR m 3,n . It will be interesting to verify this as the theory of the "generalized" diagonal coinvariant spaces develops.

We finish this article by mentioning that in a forthcoming paper [START_REF] Préville-Ratelle | On the number of canopy intervals in the Tamari lattices[END_REF], it will be shown that the total number of intervals in the lattices Tam(v), for all the paths v of length n, is given by 2(3n+3)! (n+2)!(2n+3)! , which is the same as the number of rooted non-separable planar maps with n + 2 edges (sequence A000139 of OEIS).

(ii) Note that the paths above the line with endpoints (0,0) and (mn, n) are the same as the paths above the line with endpoints (0,0) and (mn + 1, n), this is why we use the term extension. (iii) As it is explained in the previous paragraph, at the moment it is not known if these generalizations exist.

Fig. 1 :

 1 Fig. 1: A binary tree B and its associated complete binary tree B (left). Right rotation on a complete binary tree: the covering relation in the Tamari lattice (right).

  These two families of trees are enumerated by the well studied Catalan numbers C n = 1 2n+1 2n + 1 n

Fig. 2 :

 2 Fig. 2: Ballot path and Dyck path.

Fig. 3 :

 3 Fig. 3: The Tamari covering relation for ballot (Dyck) path (left). The covering relation in the m-Tamari lattice (m=2) (right).

  The classical ballot paths and their extensions with any integer m are particular cases of such (a, b)-ballot paths. The simple Catalan ballot paths are obtained by putting (a, b) = (n, n + 1), and their m-extensions are obtained by putting (a, b) = (n, mn + 1).

Fig. 4 :

 4 Fig. 4: A pair (u,v) of paths with the horizontal distance horizv(p) (left). The covering relation defining the poset Tam(v)(right).

  Figure we have drawn with brown dotted arrows the covering relation for the Young lattices Y (v) of Ferrers diagrams included in the Ferrers diagram defined by the path v. The lattice Y (v) can be seen as a refinement of the lattice Tam(v), and in that case, by the simple symmetry exchanging rows and columns, the lattice Y (v) is isomorphic to Y ( ←v ).

Fig. 5 :

 5 Fig. 5: Duality and rational Catalan combinatorics: the lattices Tam(5,3) and Tam(3,5) .

Fig. 6 :

 6 Fig. 6: The decomposition of the Tamari lattice on complete binary trees with 4 interior vertices into the union of 8 disjoint intervals Tam(v) (Theorem 3).

Fig. 7 :

 7 Fig. 7: Walk around a binary tree B: the word w(B) (left). Second definition of the canopy (right).

From

  w(B), we construct two subwords. The first subword u(B) is obtained by keeping track only of

Fig. 8 :

 8 Fig. 8: The words w(B), u(B) and v(B) associated to the binary tree in Figure 7 (left). The pair (u,v) of paths associated to a binary tree in Figure 7(right).

Fig. 9 :

 9 Fig. 9: The "push-gliding" algorithm

  and (mn+1) n-1 , respectively. The first number corresponds to the number of m-ballot paths of height n and the second one to the number of m-parking functions of height n. The m-parking functions of height n are simply the m-ballot paths labelled on the north steps, with the labels in the set {1, 2, ..., n} such that consecutive north steps are labelled increasingly.

Acknowledgements

We are very grateful to Luc Lapointe for inviting the two authors to Talca, making the collaboration between them possible, for many fruitful discussions and for his constant support during the entire process of this work.

LFPR would like to thank Franc ¸ois Bergeron for many fruitful discussions, in particular for providing the first author a conjectural formula that was one of his motivations for this work, and to Ruben Escobar and Miles Jones for multiple corrections.

XV is grateful to Kurusch Ebrahimi-Fard, Vincent Pilaud and Juanjo Rué for inviting him to the workshop in Madrid (27-29 November 2013) "Recent trends in algebraic and geometric combinatorics" to present part of this work, together with some related work (see [28]), and to Mireille Bousquet-Mélou, Michael Drmota, Christian Krattenthaler and Marc Noy for inviting him at the Oberwolfach workshop (3-7 March 2014) "Enumerative Combinatorics" to present the work described in this paper.

was supported by a Proyecto Fondecyt Postdoctorado 3140298.