Are the q-Catalan numbers q-holonomic?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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?

Answer 4

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$.