Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
What is the differential equation in the case of classical Catalan numbers? –  john mangual May 4 '10 at 15:32
5  
The linear differential equation is $z(1 - 4z)f'(z) + (1 - 2z)f(z) - 1 = 0$ –  Johann Cigler May 4 '10 at 15:57
1  
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: You misprinted $sqrt$ (without backslash) but I am surprised you do in LaTeX now. It would be honest to say that the mathoverflow.net/questions/21663 is related to the sequence of Catalan's numbers, and the mentioned project with Ole Warnaar (arXiv:1003.1999) with its $q$-version. Although we discuss different properties there. Let me also mention that the polynomials $p_i(z)$ and $P_i(z)$ in your definition depends not only on $z$ but also on $q$ (polynomially). –  Wadim Zudilin May 7 '10 at 11:55
show 3 more comments

4 Answers 4

up vote 10 down vote accepted

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.

share|improve this answer
    
@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
    
Thank you, this proof is better than a reference. –  Johann Cigler May 9 '10 at 7:57
    
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
add comment

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.

share|improve this answer
    
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
add comment

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?

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.