# Are the q-Catalan numbers q-holonomic?

The generating function $f(z)$ of the Catalan numbers which is characterized by $f(z)=1+zf(z)^2$ is D-finite, or holonomic, i.e. it satisfies a linear differential equation with polynomial coefficients. The generating function $F(z)$ of the $q$-Catalan numbers is analogously characterized by the functional equation $F(z)=1+z F(z) F(qz)$. I suspect that $F(z)$ is not $q$-holonomic, i.e. does not satisfy a linear $q$-differential equation with polynomial coefficients. But I have no proof. Is there a proof in the literature or references which may lead to a proof?

Since there were some misunderstandings I want to clarify the situation. A power series $F(z)$ is called $q -$holonomic if there exist polynomials $p_i (z)$ such that $\sum\limits_{i = 0}^r {p_i (z)D_q^i } F(z) = 0$ where $D_q$ denotes the $q -$differentiation operator defined by $D_q F(z) = \frac{{F(z) - F(qz)}}{{z - qz}}.$ Equivalently if there exist (other) polynomials such that $\sum\limits_{i = 0}^r {p_i (z)F(q^i } z) = 0.$

Let $f(z)$ be the generating function of the Catalan numbers $\frac{1}{{n + 1}}{2n\choose n}$ . Then $f(z) = 1 + zf(z)^2$ or equivalently $f(z) = \frac{{1 - \sqrt {1 - 4z} }}{{2z}}.$ There are 3 simple $q -$analogues of the Catalan numbers: a) The polynomials $C_n (q)$ introduced by Carlitz with generating function $F(z) = 1 + zF(z)F(qz)$. My question is about these polynomials. Their generating function satisfies a simple equation, but there is no known formula for the polynomials themselves. b) The polynomials $\frac{1}{{[n + 1]}}{2n\brack n}$ . They have a simple formula but no simple formula for their generating function. c) The $q -$Catalan numbers $c_n (q)$ introduced by George Andrews. Their generating function $A(z)$ is a $q -$analogue of $\frac{{1 - \sqrt {1 - 4z} }}{{2z}}.$ Let $h(z)$ be the $q -$analogue of $sqrt {(1 + z)}$ defined by $h(z)h(qz)=1+z$. Then $A(z)= \frac{1+q}{{4qz}}(1-h(-4qz))$. They have both simple formulas and a simple formula for the generating function. But they are not polynomials in $q.$ Both b) and c) are $q$-holonomic. My question is a proof that a) is not $q$-holonomic.

• What is the differential equation in the case of classical Catalan numbers? – john mangual May 4 '10 at 15:32
• The linear differential equation is $z(1 - 4z)f'(z) + (1 - 2z)f(z) - 1 = 0$ – Johann Cigler May 4 '10 at 15:57
• Great question. This is something I have wondered about. The Catalan numbers are manifestly P-recursive (which is equivalent to D-finite). Are the q-analogues of P-recursive and D-finite also equivalent? The q-Catalan numbers are manifestly q- P-recursive (if I can put it like that). – Bruce Westbury May 4 '10 at 20:59
• In any case, the equation will not be small. I looked for both q-differential equations and q-recurrences using the first 100 coefficients, and found nothing. So it's probably fair to conjecture that there is no linear q-differential equation. Unfortunately, I have absolutely no idea how to prove it. In fact, I know of no proof at all proving something to be not q-holonomic. – Martin Rubey May 5 '10 at 13:31
• @Johann: Your typesetting is good. Martin's response below is actually not too bad as well: by this argument it's possible to show that there is no $D_q$-equation of order 1 or 2 with rational coefficients. I am not at all surprised by the $q$-nonholomicity, because $q$-extensions of simple rational functions are transcendental. (My favourite transcendental example $T_q(z)=\sum_{n=0}^\infty q^{n(n-1)/2}z^n$ corresponds to the rational function $1/(1-z)$ in the limit $q\to0$.) The coefficients of the $q$-version of $f(z)=1+zf(z)^2$ might be like $T_q(z)$... – Wadim Zudilin May 7 '10 at 13:44

## 4 Answers

The problem is to show that the function $F(z)=1+z+(1+q)z^2+O(z^3)$ satisfying the functional equation $F(z)=1+zF(z)F(qz)$ does not satisfy $\sum_{j=0}^{n-1}P_j(z)F(q^jz)+Q(z)=0$ identically in $z$ for some $n$; here $P_j$ and $Q$ are polynomials in both $z$ and $q$. (Although the original question assumes the homogeneous equation, $Q(z)=0$, the limiting case $q\to1$ suggests to consider $Q(z)$ more generally.) In what follows we show that such a functional equation implies the algebraicity of $F(z)$; this is known to be false.

First of all, switch to the function $G(z)=zF(z)$ which satisfies $$G(qz)G(z)=q(G(z)-z).$$ The problem is then to show that the newer function does not satisfy $\sum_{j=0}^{n-1}\tilde P_j(z)G(q^jz)+\tilde Q(z)=0$ for some $n$. By applying $z\mapsto q^{-k}z$ we can assume that $\tilde P_0(z)\ne0$ in this relation. The substitution $z\mapsto qz$ results in the relation $\sum_{j=1}^n\hat P_j(z)G(q^jz)+\hat Q(z)=0$ where $\hat P_1(z)\ne0$.

The next step is to show, by iterating the functional equation for $G(z)$, that $$G(q^nz)\dots G(qz)G(z)=X_n(z)G(z)-Y_n(z).$$ Indeed, we have $X_0=1$, $Y_0=0$, and $$X_n(z)G(z)-Y_n(z)=\bigl(X_{n-1}(qz)G(qz)-Y_{n-1}(qz)\bigr)G(z)$$ implying $$X_n(z)=qX_{n-1}(qz)-Y_{n-1}(qz), \quad Y_n(z)=qzX_{n-1}(qz) \qquad\text{for}\quad n\ge1.$$ By means of the formula we see that $\deg Y_n$ does not decrease with $n$, so that $Y_n\ne0$ for $n\ge1$. Note that our computation implies $$G(q^nz)=\frac{X_n(z)G(z)-Y_n(z)}{X_{n-1}(z)G(z)-Y_{n-1}(z)} \qquad\text{for}\quad n\ge1.$$

Substitute the above finding into the equation $\sum_{j=1}^n\hat P_j(z)G(q^jz)+\hat Q(z)=0$ with $\hat P_1(z)\ne0$. We obtain $$\sum_{j=1}^n\hat P_j(z)\frac{X_j(z)G(z)-Y_j(z)}{X_{j-1}(z)G(z)-Y_{j-1}(z)} +\hat Q(z)=0.$$ The term corresponding to $j=1$ is equal to $$\hat P_1(z)\frac{X_1(z)G(z)-Y_1(z)}{X_0(z)G(z)-Y_0(z)} =\hat P_1(z)\frac{qG(z)-qz}{G(z)}.$$ Note that the denominator $G(z)$ in this expression is not canceled by the other denominators in the former relation because $X_{j-1}(z)G(z)-Y_{j-1}(z)$ is never divisible by $G(z)$ as $Y_{j-1}(z)\ne0$ for $j\ge2$. In other words, after multiplying $$\sum_{j=1}^n\hat P_j(z)\frac{X_j(z)G(z)-Y_j(z)}{X_{j-1}(z)G(z)-Y_{j-1}(z)} +\hat Q(z)=0$$ by $G(z)$ we get an algebraic relation $$-qz\hat P_1(z)+G(z)\cdot\text{rational function in }z,q,G(z) =0$$ where the rational function does not involve $G(z)$ as a multiple in the denominator. Since $\hat P_1(z)\ne0$, this gives us a nontrivial algebraic relation for $G(z)$. Thus the function $G(z)$, hence $F(z)$ as well, are algebraic.

Addition. I have never seen Carlitz's function $F(z)$ before, so I was pretty sure that things like its transcendence had been already established. Especially, since it is not hard (although required some time from me). Any way, this explains my reasons for not having a reference to this fact.

If we write $$F(z)=F_q(z)=\sum_{n=0}^\infty a_n(q)z^n=\sum_{n=0}^\infty a_nz^n=1+z+(1+q)z^2+\dots,$$ the functional equation $F(z)=1+zF(z)F(qz)$ implies $$a_{n+1}=\sum_{k=0}^nq^ka_ka_{n-k} \quad\text{for}\; n\ge0, \qquad a_0=1.$$ The clear induction on $n$ shows that $a_{n+1}(q)$ is a polynomial from $\mathbb Z[q]$ with leading term $q^{n(n-1)/2}$. In particular, the denominator of $a_{n+1}(1/2)$ is exactly $2^{n(n-1)/2}$.

If the function $F_q(z)$ were algebraic then its specialization $F_{1/2}(z)$ should be algebraic. This would imply that for a certain integer $A$ the $z$-expansion of $F_{1/2}(Az)$ has integral coefficients. But no $A\in\mathbb Z$ with the property $A^{n+1}/2^{n(n-1)/2}\in\mathbb Z$ for all $n$ could be given. Therefore, $F_{1/2}(z)$ and $F_q(z)$ in general are transcendental.

• @Wadim: thank you, this is a beautiful proof! By the way, can you give a reference where I find a proof that F(z) cannot be algebraic? – Johann Cigler May 8 '10 at 15:52
• And the last criterion is due to Eisenstein: see the answer of Antoine Chambert-Loir to mathoverflow.net/questions/21290 . – Wadim Zudilin May 9 '10 at 8:00

The q-Catalan numbers satisfy the P-recurrence
$[n+2][n+1]C_{n+1}=[2n+2][2n+1]C_{n}$

It follows from this that this sequence is q-holonomic. The following reference announces a Mathematica package that will find the q-differential equation:

MR2511667 (Review) Kauers, Manuel ; Koutschan, Christoph . A Mathematica package for $q$-holonomic sequences and power series. Ramanujan J. 19 (2009), no. 2, 137--150.

• Sorry I did not mean these q-Catalan numbers but those introduced by Carlitz whose generating function satisfies F(z)=1+zF(z)F(qz). – Johann Cigler May 5 '10 at 9:11

Actually, it seems that if they were q-holonomic, they would be even algebraic, since $F(qz)=(F(z)-1)/(zF(z))$, so we can express every $F(q^kz)$ as a rational function in $q$, $z$, and $F(z)$. Did I make a mistake?

• This need not be true. Consider $h(z)$ which satisfies $h(z)h(qz)=1+z$. This is $q$-holonomic and satisfies $h(z)(1+qz)-(1+z)h(q^2z)=0$. Multiplying by $h(qz)$ we get the trivial identity $(1+z)(1+qz)-(1+z)(1+qz)=0$ and no information whether $h(z)$ is algebraic. – Johann Cigler May 6 '10 at 14:33
• Hm, I'm glad I was sceptical... However, maybe the idea can be saved by an argument taking into account that F(qz) has degree one in F in both numerator and denominator? – Martin Rubey May 6 '10 at 15:32
• @Martin: You give up too early. You have a good start for attacking the problem, but I'd expect that more work is required. – Wadim Zudilin May 7 '10 at 14:59
• No, I didn't give up and I'm actually quite sure that the approach works. But I have no time. A little more detail: I think we can show that first expressing $F(q^k z)$ in terms of $F(z)$, then multiplying by the common denominator, each $F(q^k z)$ will give rise to a term $F^k(z)$. Actually, it might be worth to write a note on this, just to get the topic "q-non-holonomicity" started... – Martin Rubey May 7 '10 at 18:14
• A good strategy! – Wadim Zudilin May 7 '10 at 23:18

Suppose $F$ is $q-$holonomic. This implies, if I understand correctly that there exists a natural integer $d$ and $d+1$ polynomials $P_0,\dots,P_d\in\mathbb C[q,z]$, not all zero, such that $\sum_{k=0}^d P_k\frac{\partial^k F}{\partial q^k}=0$.

We can assume that not all polynomials $P_i$ are divisible by $z$. We can thus write $P_i=Q_i+z\tilde P_i$ with $Q_0,\dots,Q_d$ in $\mathbb C[q]$ and not all zero. Denoting by $F_n\in\mathbb N[q]$ the coefficient of $z^n$ in $F=\sum_{n=0}^\infty F_n$, an induction on $n$ shows easily that $F_n$ has degree ${n\choose 2}$ as a polynomial in $q$. This implies that given an arbitrary natural integer $A$ there exists $N$ such that a all coefficients of degree $\geq {n\choose 2}-A$ of $\sum_{k=0}^d Q_k\frac{\partial^kF_n}{\partial q^k}\in\mathbb C[q]$ are zero for $n\geq N$.

Since the coefficients of $F_n$ enumerate Dyck paths weighted by a suitable area, the leading coefficients of $F_n$ stabilize to the sequence $1,1,2,3,5,7,\dots$ of partition numbers. This implies that for a given $B$ all coefficients of degree at least ${n\choose 2}-B$ in $Q_e\frac{\partial^eF_n}{\partial q^e}$ are zero for $n$ huge enough and for $e$ the largest integer $\geq 0$ such that $Q_e\not=0$. Since $B$ is arbitrary, this implies that arbitrarily many leading terms of $Q_e\frac{d^e}{dq^e}\left(q^n\prod_{n=1}^\infty\frac{1}{1-q^n}\right)$ are zero if $n$ is large enough. This is absurd.

Remark that the last argument can be simplified: we don't need convergency of the leading degrees of $F_n$. In fact, the above proof shows that a series $G=\sum_{n=0}^\infty G_nz^n$ with $G_n\in\mathbb C[q]$ is never $q-$holonomic if $\limsup_{n\rightarrow\infty}\frac{\deg_q(G_n)}{n}>1$.

• I think you have misunderstood the definition of $q$-holonomic. $F(z)$ is $q$-holonomic if there exist polynomials such that $p_0 (z)F(z) + p_1 (z)D_q F(z) + \cdots p_r (z)D_q^r F(z) = 0$ where $D_q$ denotes the q-differentiation operator defined by $D_q f(z) = \frac{{f(z) - f(qz)}} {{z - qz}}.$ – Johann Cigler May 6 '10 at 17:23
• Indeed. It can be modified in order to cope with the correct definition. The resulting proof is somewhat similar to Zudilin's solution except that the final step arises from the fact the $\prod_{n=1}^\infty (1-1/x^n)^{-1}$ is transcendental. – Roland Bacher May 10 '10 at 13:27