show/hide this revision's text 3 Added an answer to the subquestion; added 8 characters in body

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

If we writeF(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)$ impliesa_{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)$ isexactly $2^{n(n-1)/2}$.

If the function $F_q(z)$ were algebraic then its specialization $F_{1/2}(z)$ should bealgebraic. 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.
show/hide this revision's text 2 added 93 characters in body

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{polynomial P_1(z)+G(z)\cdot\text{rational function in }z,q,G(z) =0. 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.
show/hide this revision's text 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{polynomial in }z,q,G(z) =0. $$ 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.