# What are the periodic Dyck paths?

I changed the thread completely so that everything is now elementary linear algebra.

A Dyck path of length $$n$$ is a list of positive integers $$[c_1,c_2,...,c_n]$$ with $$c_i -1 \leq c_{i+1}$$ for all $$i$$ and $$c_i \geq 2$$ for $$i \neq n$$ and $$c_n=1$$. (One can show that those sequences really correspond to the classical Dyck paths via the area sequence and the number of Dyck paths of length $$n$$ is $$C_{n-1}$$ when $$C_n$$ denotes the Catalan numbers)

Let $$D=[c_1,c_2,...,c_n]$$ be a Dyck path of length $$n$$. We define the Cartan matrix $$C_D$$ of $$D$$ as the $$n \times n$$ upper triangular matrix with entries 0 or 1 as follows: In the $$i$$-th row $$C_D$$ has entries equal to one in position $$(i,i)$$, $$(i,i+1)$$,...,$$(i,i+c_i-1)$$ and all other entries are zero. Define the Coxeter matrix $$\phi_D$$ as $$-C_D^{-1} C_D^T$$. Call a matrix $$M$$ periodic in case $$M^k=id$$ for some $$k \geq 1$$ and the minimal such $$k$$ is called the period of $$M$$ (and let the period be zero in case no such $$k$$ exists). Call a Dyck path Coxeter-periodic, or for short just periodic, in case its Coxeter matrix is periodic and the Coxeter-period, or just period, of the Dyck path is defined as the period of the Coxeter matrix.

Call a Dyck path bouncing in case it is of the form $$[a_1+1,a_1,...,3,2,a_2+1,a_2,...,2,...,a_r+1,a_r,...,3,2,1]$$.

I can prove that bouncing Dyck paths of length $$n$$ have period $$n+1$$ (as suggested by the comment of Michael Albert). It seems that the converse is also true:

Conjecture: A Dyck path of length $$n$$ is bouncing if and only if it has period $$n+1$$.

The conjecture is checked for $$n \leq 9$$.

Moreover there are the following natural questions:

What are the periodic Dyck paths and how can they be enumerated? What is the statistics of their period?

For $$n \leq 5$$ all Dyck paths are periodic. For $$n \geq 6$$ the sequence of non-periodic Dyck paths starts with 1,17,167,... See http://www.findstat.org/StatisticsDatabase/St001218 for the period of all Dyck paths with $$n \leq 7$$.

Here two examples: $$[ 3, 4, 3, 3, 2, 1 ]$$ is not periodic. $$[2,5,4,3,3,2,1]$$ is periodic with period 12. The Cartan matrix of $$[2,5,4,3,3,2,1]$$ is given by

$$\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}$$

and the Coxeter matrix is given by $$\begin{bmatrix} 0 & 0 & -1 & 0 & 0 & 0 & 0 \\ -1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & -1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & -1 & -1 & -1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & -1 & -1 & -1 \\ \end{bmatrix}$$

Algebraic background: Dyck paths can be identified with Nakayama algebras with a linear quiver, which are finite dimensional algebras. The definition of Cartan and Coxeter matrices is then natural, see for example https://www.sciencedirect.com/science/article/pii/S0024379505001709 . In particular, the study of Coxeter matrices is interesting because it is a derived invariant of the algebra and has many applications. For example one can conclude that two algebras with different periods are not derived equivalent.

In case the conjecture is true, one would have the following nice equivalent characterisations of bouncing Dyck paths:

1.$$D$$ is bouncing (combinatorial characterisation).

2.$$D$$ is derived equivalent (=iterated tilted) to a hereditary algebra of Dynkin type $$\mathcal{A}$$ (homological characterisation).

3.The trivial extension of $$D$$ is a Brauer tree algebra (representation-theoretic characterisation).

4.The coxeter polynomial is equal to $$\sum\limits_{k=0}^{n}{x^k}$$ (polynomial characterisation).

5.The Coxeter matrix of $$D$$ has period $$n+1$$ (linear algebraic characterisation).

6.The corresponding Nakayama algebra is Koszul.

The equivalences of 1., 2., 3., 4. and 6. is proven and the equivalence with 5. would follow from the conjecture in the thread.

• I know nothing about the topic but on the basis of the numbers and conjectures alone it would seem that one might be looking for a correspondence with compositions of n-1 (of which there are 2^{n-2}) with the various restrictions corresponding to restricting the size of the largest part (Fibonacci = largest part of size at most 2 etc.) The data seem to support the first interpretation with the Dyck paths of period (n+1) apparently being exactly those that are simply the concatenation of a series of peaks i.e., concatenations of parts 1^k 0^k for some k > 0. – Michael Albert Jun 23 '18 at 20:39
• @Vincent What do you mean with "ALL Dyck path"? They are enumerated by the Catalan numbers as is well known and as I wrote in the beginning of the thread ( see mathworld.wolfram.com/DyckPath.html ), but the periodic ones are the interesting ones and not all Dyck paths are periodic as can be seen in the two examples. – Mare Sep 21 '18 at 10:22
• By "ALL Dyck path" I meant "ALL Dyck paths". I forgot to type the "s". And I see now that the answer to my question was already in your post and I had glossed over it. – Vincent Sep 21 '18 at 10:26
• O hey, I see now that you edited in the link into your comment. Thanks! This was just what I was looking for – Vincent Sep 21 '18 at 10:28
• @Vincent No, it seems to be very complicated. But "bouncing Dyck path" has a nice visual interpretation as you might see when looking at some examples. (you can click the findstat link to see pictures of the Dyck paths and look for the period to filter the bouncing ones out). – Mare Sep 21 '18 at 10:39

This answer gives some partial progress towards your conjecture. Since the Coxeter polynomial is also a derived invariant, it should have the same applications.

Theorem: Suppose $$D$$ is a Dyck path of length $$n$$. The Coxeter polynomial (characteristic polynomial of $$\phi_{D}$$) is equal to $$\frac{x^{n+1}-1}{x-1}$$ if and only if $$D$$ is bouncing.

Before we get to the proof, let's set up some notation. We denote by $$(u_1,v_1), (u_2,v_2), \dots, (u_k,v_k)$$ the coordinates of the valleys of $$D$$. These are the coordinates of the entries in the Cartan matrix of $$D$$ which are (1) above the diagonal (2) equal to zero (3) the entries directly below and directly to the left are equal to 1. For example, the valleys of $$[2,5,4,3,3,2,1]$$ are $$(1,3),(4,7)$$.

Next, we define the matrix $$X_D$$ similarly to the Cartan matrix except we put ones in coordinates $$(i,i+c_i-1)$$ and zeros everywhere else. So $$X_D$$ essentially consists of just the "righmost" 1's in the Cartan matrix. The matrix $$Y_D$$ is defined as the matrix with $$-1$$'s in positions $$(u,u+1),(u,u+2),\dots, (u,v)$$ as $$(u,v)$$ ranges through all the valleys, and zeros everywhere else. Finally let $$A_n$$ be the matrix with 1's in entries $$(i,i+1)$$ for $$i=1,\dots,n-1$$. One can check the following explicit form for the Coxeter matrix of a Dyck path: $$\phi_D=A_n+Y_D-X_D^{\top}.$$ We will also need a lemma

Lemma: The characteristic polynomial of $$\phi_D$$ is equal to $$x^n+x^{n-1}+(1-\alpha) x^{n-2}+O(x^{n-3})$$. Where $$\alpha$$ is the number of valleys $$(u,v)$$ of $$D$$ with $$v>u+2$$.

Proof of Lemma: We get $$x^{n}+x^{n-1}$$ by looking at the product of elements in the diagonal of $$xI-\phi_D$$. The coefficient of $$x^{n-2}$$ is precisely $$-\sum_{i. By analyzing the explicit form for $$\phi_D$$ above, we have $$\phi_D(i,j)\phi_D(j,i)=-1$$ when $$(i,j)=(n-1,n)$$ and we have $$\phi_D(i,j)\phi_D(j,i)=1$$ when $$(i,j)=(u-1,v)$$ and $$(u,v)$$ is a valley with $$u+2, and $$\phi_D(i,j)\phi_D(j,i)=0$$ otherwise.

Proof of Theorem: The lemma tells us that the characteristic polynomial of a path which is not bouncing cannot be equal to $$\frac{x^{n+1}-1}{x-1}$$. To show that every bouncing path has this as the characteristic polynomial you can use induction on the length of the Dyck path. If $$D'$$ is the Dyck path corresponding to the sequence $$[c_2,c_3,\dots,c_n]$$ then $$D'$$ is also bouncing, and $$\phi_{D'}$$ is the $$(1,1)$$ cofactor of $$\phi_D$$. By expanding the determinant along the first row one can establish the recurrence $$\det(xI_n-\phi_D)=1+x\det(xI_{n-1}-\phi_{D'})$$ (One needs to show that there is a unique permutation not fixing 1, that has nonzero contribution in the determinant expansion.) This gives us our result when combined together with the inductive claim that the Coxeter polynomial of $$D'$$ is $$\frac{x^n-1}{x-1}$$.

Here a proof attempt of the conjecture in case $$n+1$$ is a prime (using the result of Gjergji Zaimi). Assume $$D$$ is a Dyck path of length $$n$$ and period $$n+1$$, meaning that the Coxeter matrix $$M_D$$ of $$D$$ has period $$n+1$$. By corollary 2.7. of https://www.sciencedirect.com/science/article/pii/S0024379505001709 , $$M_D$$ is diagonalizable and the Coxeter polynomial $$f_D$$ (which has degree $$n$$) is a product of cyclotomic polynomials: $$f_D= \Phi_{r_1} \cdots \Phi_{r_q}$$ for some numbers $$r_i$$. This means that up to a base change, $$M_D$$ is a diagonal matrix with diagonal entries being roots of the $$\Phi_{r_i}$$. So the order of $$M_D$$ should be the least commen multiple of the $$r_i$$: $$order(M_D)= LCM( r_1,...,r_q)$$. But $$order(M_D)=n+1$$ is prime by assumption and thus $$r_i=r_j=n+1$$ for all $$i,j$$. But $$\Phi_{n+1}=1+x+...+x^n$$ (since $$n+1$$ is prime) and thus $$f_D=\Phi_{n+1}$$. Now using the result of Gjergji Zaimi posted in this thread, $$D$$ is a bouncing Dyck path.

Edit: Using QPA I found a counterexample now to my conjecture. There are Dyck paths of length 11 with period 12 that are not bouncing, namely the following Nakayama algebras with the shown Kupisch series:

[ [ 3, 4, 3, 3, 4, 3, 3, 3, 2, 2, 1 ], [ 3, 4, 3, 3, 3, 2, 2, 3, 3, 2, 1 ], [ 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 1 ], [ 3, 3, 4, 3, 3, 3, 2, 3, 3, 2, 1 ], [ 3, 5, 4, 3, 3, 3, 2, 3, 3, 2, 1 ], [ 3, 4, 3, 3, 4, 3, 2, 3, 3, 2, 1 ], [ 3, 4, 3, 3, 3, 2, 3, 3, 3, 2, 1 ], [ 3, 3, 2, 3, 3, 4, 3, 3, 3, 2, 1 ], [ 3, 3, 4, 3, 3, 4, 3, 3, 3, 2, 1 ], [ 3, 5, 4, 3, 3, 4, 3, 3, 3, 2, 1 ], [ 3, 4, 3, 3, 5, 4, 3, 3, 3, 2, 1 ], [ 3, 4, 3, 3, 3, 2, 4, 3, 3, 2, 1 ], [ 3, 3, 2, 2, 3, 3, 4, 3, 3, 2, 1 ], [ 3, 3, 3, 2, 3, 3, 4, 3, 3, 2, 1 ], [ 3, 4, 3, 2, 3, 3, 4, 3, 3, 2, 1 ], [ 3, 3, 2, 4, 3, 3, 4, 3, 3, 2, 1 ], [ 2, 3, 3, 4, 3, 3, 4, 3, 3, 2, 1 ], [ 4, 3, 3, 4, 3, 3, 4, 3, 3, 2, 1 ], [ 3, 3, 5, 4, 3, 3, 4, 3, 3, 2, 1 ], [ 3, 6, 5, 4, 3, 3, 4, 3, 3, 2, 1 ], [ 3, 3, 2, 3, 3, 5, 4, 3, 3, 2, 1 ], [ 3, 3, 4, 3, 3, 5, 4, 3, 3, 2, 1 ], [ 3, 5, 4, 3, 3, 5, 4, 3, 3, 2, 1 ], [ 3, 4, 3, 3, 6, 5, 4, 3, 3, 2, 1 ], [ 3, 4, 3, 3, 4, 3, 3, 4, 3, 2, 1 ] ]

So maybe my conjecture should get turned into the following question: For which $$n$$ is it true that a Dyck path of length $$n$$ is bouncing iff it has period $$n+1$$?

It is true for $$n \leq 10$$ and all $$n$$ such that $$n+1$$ is prime.