text:
\def\DATE{July 22, 2017}

\line{\fchapter\hfill\the\chapterNo.\qquad Introduction}
\vSkipAfterTitle

\def\prevs{\the\chapterNo.\the\statementNo}
\def\preveq{(\the\chapterNo.\the\equationNo)}

\noindent
A \ikey{$q$-algebraic equation} is a functional equation given by a complex
polynomial of several variables, $P(z,z_0,z_1,\ldots,z_k)$, a complex
number $q$, and is of the form
$$
  P\bigl(z,f(z),f(qz),\ldots,f(q^kz)\bigr)=0 \, ,
  \eqno{\equa{qAlgebraic}}
$$
where $f$ is the unknown.
Since the coefficients of the polynomial are free parameters,
they may in fact depend on $q$ in any fashion that one wishes. These
$q$-algebraic equations occur in various areas, including combinatorics,
dynamical systems, knot theory, and mathematical physics.

Some important problems on $q$-algebraic equations parallel those
on differential equations and, loosely speaking, concern the existence,
uniqueness, and some form of regularity of the solutions. For those
three problems to make sense, one needs to state the domain of the
equation, that is, what sort of $f(z)$ are considered. In full generality,
all three problems are in terms of formal power series, with possibly
non-integer exponents, which may or may not be convergent. In
this setting, the regularity problem is to be interpreted as that of the
asymptotic behavior of the coefficients of the formal solutions. The purpose
of this book is to address these issues.

\bigskip

\def\prevs{\the\chapterNo.\the\sectionNo.\the\statementNo}
\def\preveq{(\the\chapterNo.\the\sectionNo.\the\equationNo)}

\section{\poorBold{$q$}-algebraic equations in perspective}

\setbox1=\hbox to 200pt{\hskip -18pt\vbox to 155pt{
  \eightpoints
  \hsize=160pt
  \kern 245pt
  \special{psfile=Figures/prolegomenon_fig01.eps}
  \anotePT{50}{-9}{$q^{n+1}t$}
  \anotePT{75}{-9}{$q^nt$}
  \anotePT{92}{-9}{$t$}
  \anotePT{-12}{63}{$t^\lambda$}
  \anotePT{-27}{50}{$(q^nt)^\lambda$}
  \anotePT{-36}{35}{$(q^{n+1}t)^\lambda$}

  \anotePT{0}{-25}{\flabel{prolegomenonFigA}}
  \vfill
  \vss
}\hfill}

\wd1=0pt\dp1=0pt\ht1=0pt
\parshape 11 0pt \hsize 0pt 135pt 0pt 135pt 0pt 135pt 0pt 135pt 0pt 135pt 0pt 135pt 0pt 135pt 0pt 135pt 0pt 135pt 0pt \hsize\box1
The origin of the subject in the 17th century seems both analytic and
number theoretic. Andrew, Askey and Roy (1999, \S 10.1) report that
Fermat, searching for a closed formula for the integral $\int_0^tx^\lambda\d x$
when $\lambda$ is not an integer, considered the approximation of that
integral using a geometric series, namely, taking $q$ in $(0,1)$,
$$\eqalign{
  \sum_{n\geq 0} (q^nt)^\lambda (q^nt-q^{n+1}t)
  &{}= t^{\lambda+1} \sum_{n\geq 0} q^{(\lambda+1)n}(1-q)\cr
  &{}=t^{\lambda+1} {1-q\over 1-q^{\lambda+1}} \, . \cr}
$$

\setbox1=\hbox to 1700pt{\hskip 25pt\vbox to 155pt{
  \eightpoints
  \hsize=160pt
  \kern 130pt
  \special{psfile=Figures/prolegomenon_fig01.eps}
  \anotePT{50}{-9}{$q^{n+1}t$}
  \anotePT{75}{-9}{$q^nt$}
  \anotePT{93}{-9}{$t$}
  \anotePT{-25}{80}{$(q^nt)^\lambda$}
  \anotePT{0}{-25}{\flabel{prolegomenonFigA}}
  \vfill
  \vss
}\hfill}

\wd1=0pt\dp1=0pt\ht1=0pt
\bigskip

Taking the limit as $q$ tends to $1$
yields $\int_0^t x^\lambda \d x=t^{\lambda+1}/(\lambda+1)$. This lead
Thomae (1869) and Jackson (1910) to introduce the $q$-integral
$$
  \int_0^t f(x)\d_qx
  = \sum_{n\geq 0} f(tq^n)(tq^n-tq^{n+1}) \, ,
$$
and consequently, to the development of a discrete form of integral
and differential calculus, to which we will come back.

A different source is number theoretic and combinatorial, with the theory of
partitions. A partition of an integer $n$ is a nondecreasing
tuple $(k_1,\ldots,k_m)$
of positive integers such that $k_1+\cdots+k_m=n$. For instance, the partitions
of $3$ are $(3)$, $(1,2)$, and $(1,1,1)$. In a different way, a partition
of $n$ can be identified with the sequence of nonnegative integers
$(n_k)_{k\in \NN}$ such that $n=\sum_{k\in \NN} n_k k$, the number $n_k$ counting
how many times $k$ appears in the partition. Writing $p(n)$ for the number
of partitions of $n$, Euler calculates the generating function of the sequence
$\bigl(p(n)\bigr)$, noting that
$$\eqalign{
  \sum_{n\geq 0} p(n)q^n
  &{}=\prod_{k\geq 1} (1+q^k+q^{2k}+q^{3k}+\cdots) \cr
  &{}=\prod_{k\geq 1} {1\over 1-q^k} \, . \cr}
$$
Writing
$$
  \inot{(z;q)_n}=\prod_{0\leq k< n} (1-zq^k)
$$
with $(z;q)_0=1$, defining also
$$
  (z;q)_\infty=\prod_{k\geq 0} (1-zq^k) \, ,
$$
we see that
$$
  \sum_{n\geq 0} p(n) q^n = {1\over (q;q)_\infty} \, .
$$
In the course of his investigations, Euler discovered the formula
$$
  \sum_{n\geq 0} {z^n\over (q;q)_n}={1\over (z;q)_\infty} \, .
$$
Considering the left hand side of this identity, set
$$
  f(z)=\sum_{n\geq 0} {z^n\over (q;q)_n} \, .
$$
We see that
$$\eqalign{
  f(qz)
  &{}=\sum_{n\geq 0} {q^nz^n\over (q;q)_n} \cr
  &{}=\sum_{n\geq 0} {(q^n-1)z^n\over (q;q)_n} +\sum_{n\geq 0} {z^n\over (q;q)_n}
   \cr
  &{}=-z\sum_{n\geq 1} {z^{n-1}\over (q;q)_{n-1}}+f(z) \cr
  &{}=(1-z)f(z) \, . \cr}
$$
Therefore, $f$ obeys a $q$-algebraic equation $f(qz)=(1-z)f(z)$, corresponding
to the polynomial $P(z,z_0,z_1)=(1-z)z_0-z_1$ in \qAlgebraic. From this
equation, it is easy to see that if $|q|$ is less than $1$, then
$$
  f(z)={f(qz)\over 1-z}={f(q^2z)\over (1-z)(1-qz)}
  = \cdots  = {f(0)\over (z;q)_\infty}
  = {1\over (z;q)_\infty}\, ,
$$
which is Euler's formula.

Euler's line of study led Jackson (1908) to introduce the \ikey{$q$-difference
operator}
$$
  \inot{\D_q}f(z)= {f(z)-f(qz)\over (1-q)z} \, ,
$$
with the heuristic that
$$
  \lim_{q\to 1} \D_qf(z)={d\over \d z} f(z) \, ,
$$
so that $\D_q$ is a discrete approximation of the differential
operator $\d/\d z$. Immediately, this opens the door to an interesting
$q$-analogue of differential equations, and therefore of various special
functions, many motivated by applications, not just for the sake of
generalization. As an elementary example, a $q$-analogue of the exponential
function $e^{\lambda z}$ may be defined by the identity $\D_qf(z)=\lambda f(z)$,
which means that $f$ satisfies the $q$-algebraic equation
$$
  f(z)-f(qz)-\lambda(1-q)zf(z)=0 \, ,
$$
represented as in \qAlgebraic\ by the polynomial
$$
  P(z,z_0,z_1)=z_0-z_1-\lambda(1-q)zz_0\, .
$$

A still different perspective on $q$-algebraic equations comes from algebra
with the study of functions of $q$-commuting operators, that is, operators
$x$ and $y$ such that $yx=qxy$. In that context, one can prove the
$q$-binomial formula
$$
  (x+y)^n=\sum_{0\leq k\leq n} {n \brack k}_q x^{n-k}y^k
$$
where
$$
  {n\brack k}_q={(q;q)_n\over (q;q)_k(q;q)_{n-k}}
$$
is the $q$-binomial
coefficient, also called the Gauss polynomial. While this formula is
reported to have been known in the 19th century, its proof is due to
Sch\"utzenberger (1953).

\setbox1=\hbox to 170pt{\hskip 155pt\vtop to 160pt{
  \eightpoints
  \hsize=160pt
  \kern 160pt
  \special{psfile=Figures/prolegomenon_fig02.eps}
  \anotePT{100}{-10}{$n$}
  \anotePT{-10}{100}{$n$}
  \anotePT{57}{-10}{$k$}
  \anotePT{0}{-30}{\flabel{prolegomenonFigB}}
  \vfill
  \vss
}\hfill}
\dp1=0pt\wd1=0pt\ht1=0pt

\parshape 5 0pt\hsize 0pt\hsize 0pt\hsize 0pt\hsize 0pt 150pt
The \box1 last source of the subject which we mention is combinatorics. It
is the main motivation for this book. Many combinatorial
structures are defined recursively. As an example, consider the \ikey{Catalan
paths}, which are the nondecreasing paths on the lattice $\NN^2$ which
join $(0,0)$ to $(n,n)$ and remain above the diagonal. Let $C_n$ be
the number of such paths. By considering the first time $k$ that a Catalan path
hits the diagonal, we obtain the recursion
$$\eqalign{
  C_n
  &{}=\sum_{1\leq k\leq n} C_{k-1} C_{n-k} \cr
  &{}=\sum_{0\leq k\leq n-1} C_k C_{n-1-k} \, ,\cr}
$$
as long as we agree that $C_0=1$.

Consider the generating
function $C(z)=\sum_{n\geq 0} C_n z^n$. The recursion  yields
$$\eqalign{
  C(z)
  &{}=1+z\sum_{\ss n\geq 1\atop \ss 0\leq k\leq n-1}
    C_k z^k C_{n-1-k} z^{n-1-k} \cr
  &{}=1+z\sum_{k,m\geq 0} z^kC_k z^mC_m \cr
  &{}=1+zC(z)^2\, . \cr}
$$
Therefore, $C$ solves the algebraic equation
$$
  zC(z)^2-C(z)+1=0 \, .
  \eqno{\equa{ProlegCatalanEq}}
$$
This is a quadratic equation in $C$, and we obtain that
$$
  C(z)={1-\sqrt{1-4z}\over 2z} \, .
$$
Therefore $C_n$ is the coefficient of $z^n$ in $(1-\sqrt{1-4z})/2z$. As
illustrated throughout the book by Flajolet and Sedgewick (2009),
this is enough to show that
$$
  C_n\sim {4^n\over n^{3/2}\sqrt\pi}
  \eqno{\equa{ProlegCatalanAsymptotic}}
$$
as $n$ tends to infinity. Relation \ProlegCatalanAsymptotic\
allows one to estimate asymptotically the number of Catalan paths from
$(0,0)$ to $(n,n)$ without calculating that number exactly.
For this specific example, it is possible to show that $C_n$ is in fact
the \ikey{Catalan number}
$$
  C_n={1\over n+1}{2n\choose n} \, ,
$$
but this information is not needed to obtain \ProlegCatalanAsymptotic\ from
\ProlegCatalanEq, and overall, as explained in Flajolet and Sedgewick (2009),
singularity analysis often allows one to obtain the asymptotic behavior
of the coefficients of a power series if one knows that this power series
satisfies an algebraic equation.

A more involved but related problem gives rise to a $q$-algebraic equation,
namely, that of counting
the number of Catalan paths whose area between the path and the diagonal
is given. This problem has been considered first by Carlitz and Riordan (1964)
and then by Carlitz (1972). Let $f_{n,\calA}$ be the number of Catalan paths
joining
$(0,0)$ to $(n,n)$ whose area between the path and the diagonal is $\calA$. We
introduce the bivariate generating function
$$
  f(z,q)=q^{1/2}\sum_{n,\calA} f_{n,\calA}z^n q^\calA \, .
$$
We may decompose it, defining first
$$
  f_n(q)=q^{1/2}\sum_\calA f_{n,\calA}q^\calA\, ,
$$
so that $f(z,q)=\sum_{n\geq 0} f_n(q)z^n$. Note that the summation in $f_n(q)$
is finite, so that $f_n(q)$ are in fact polynomials in $q^{1/2}$.

\setbox1=\hbox to 170pt{\hskip 180pt\vtop to 150pt{
  \eightpoints
  \hsize=160pt
  \kern 110pt
  \special{psfile=Figures/prolegomenon_fig03.eps}
  \anotePT{100}{-10}{$n$}
  \anotePT{-10}{100}{$n$}
  \anotePT{57}{-10}{$k$}
  \anotePT{0}{-30}{\flabel{prolegomenonFigB}}
  \vfill
  \vss
}\hfill}

\wd1=0pt\ht1=0pt\dp1=0pt

\parshape 10 0pt 145pt 0pt 145pt 0pt 145pt 0pt 145pt 0pt 145pt 0pt 145pt 0pt 145pt 0pt 145pt 0pt 145pt 0pt \hsize
\box1 Again, by decomposing a path according to its first encounter with the
diagonal at $(k,k)$ say, we obtain that
$$
  f_{n,\calA}=\sum_{k,\calB,\calC} f_{k-1,\calB}f_{n-k,\calC}
$$
where the summation is over all $k$, $\calB$ and $\calC$
with $\calB+k-(1/2)+\calC=\calA$. It follows that
$$\eqalign{
  \finetune{\hskip -80pt} f_n(q)
  &{}=\sum_{k,\calB,\calC} f_{k-1,\calB}f_{n-k,\calC}\, q^\calB q^\calC q^k \cr
  &{}=\sum_{k,\calB,\calC} f_{k,\calB}f_{n-1-k,\calC}\, q^\calB q^\calC
    q^{k+1/2}q^{1/2} \cr
  &{}=\sum_k q^k f_k(q)f_{n-1-k}(q) \, , \cr}
$$
as long as we agree that $f_0(q)=1$.

Therefore, we obtain
$$\eqalign{
  f(z,q)
  &{}=f_0(q)+\sum_{\ss n\geq 1\atop\ss 0\leq k\leq n-1}
    (zq)^k f_k(q) f_{n-1-k}(q)z^{n-k} \cr
  &{}=1 +z\sum_{k,m} (zq)^k f_k(q) f_m(q) z^m\cr
  &{}=1+zf(qz,q)f(z,q) \, . \cr}
$$
This equation is a $q$-algebraic equation, called the \ikey{$q$-Catalan equation}
and the $f_n(q)$ are called the $q$-Catalan numbers. The second variable, $q$,
is often omitted, and the equation is then written as
$$
  f(z)=1+zf(z)f(qz) \, ,
$$
corresponding to the polynomial
$$
  P(z,z_0,z_1)=1-z_0-zz_0z_1
$$
in \qAlgebraic. This time, singularity
analysis, as developed in Flajolet and Sedgewick (2009) does not apply anymore
when $|q|$ is greater than $1$, because it can be shown that $f(z)$ is
a divergent power series. When $|q|$ is less than $1$, singularity analysis
does apply, but provides the asymptotic behavior of $f_n(q)$ in an implicit
way, namely, that generically in $q$, we have $f_n(q)\sim \zeta^n$ for some
$\zeta$ defined from $f$ itself.

\bigskip

Part of the theory of $q$-algebraic equations is also related to complex
dynamics. Consider a function $\varphi$ which is an automorphism of a region
$\calR$ of the complex plane containing the origin. Define the $k$-th
iterate of $\varphi$ by $\varphi^{[k]}=\varphi\circ\varphi^{[k-1]}$, $k\geq 1$,
with $\varphi^{[0]}$ being the identity and $\varphi^{[-k]}$ being the
compositional inverse of $\varphi^{[k]}$. Gr\'evy (1894) started the study
of equations of the form
$$
  P\bigl( z, f\circ \varphi^{[0]}(z),f\circ\varphi^{[1]}(z),\ldots,
  f\circ\varphi^{[k]}(z)\bigr) = 0 \, .
  \eqno{\equa{ProlegGrevy}}
$$
As indicated by B\'ezivin (1992b), equation \ProlegGrevy\ can be put in the
form of \qAlgebraic\ as follows. Define $\psi$ by the requirement $\psi(0)=0$,
$\psi'(0)=1$ and
$$
  \varphi(z)=\psi\bigl(q\psi^{[-1]}(z)\bigr) \, .
$$
Then
$$
  \varphi^{[j]}=\psi\bigl(q^j\psi^{[-1]}(z)\bigr) \, ,
$$
so that \ProlegGrevy\ becomes
$$
  P\Bigl( z, f\circ\psi\bigl(q^0\psi^{[-1]}(z)\bigr),
          f\circ\psi\bigl(q^1\psi^{[-1]}(z)\bigr),\ldots,
          f\circ\psi\bigl(q^k\psi^{[-1]}(z)\bigr)\Bigr) = 0 \, .
$$
Substituting $\psi(z)$ for $z$ yields
$$
  P\bigl( \psi(z),f\circ\psi(q^0z),f\circ\psi(q^1z),\ldots,
          f\circ\psi(q^kz)\bigr)
  = 0 \, ,
$$
which means that $g=f\circ\psi$ solves an equation quite similar
to \qAlgebraic. However, the function
$$
  P\bigl(\psi(z),z_0,z_1,\ldots,z_k\bigr)
$$
may not be a polynomial, because of the term $\psi(z)$. But it is a polynomial
in $z_0,\ldots,z_k$, whose coefficents are power series in $z$
if $\varphi(z)$ is also a power series in $z$. We will develop our theory
in a slightly more general setting. However, while our results presumably
yield some information on \ProlegGrevy, we will not investigate
it any further.

\bigskip

We refer to the books by Ernst (2000, 2012) and the survey by Di Vizio,
Ramis, Sauloy and Zhang (2003) for further historical information and other
areas where $q$-algebraic equations occur naturally.

\bigskip

\section{Modern developments in the theory of \poorBold{$q$}-algebraic equations}

While this book proposes a quite extensive theory
of the solutions of $q$-algebraic equations and the asymptotic behavior
of their coefficients, it omits important topics which have been extensively
studied in recent years. We now recall some of those, without being
exhaustive.

Symmetries and classification problems have been extensively studied for
linear
$q$-algebraic equations, at least since the work of Birkhoff and Guenther
(1941). For the most recent advances, we refer to the works of Ramis, Sauloy
and Zhang
(2004, 2013), Van der Put and Reversat (2007), Di Vizio and Sauloy (2011)
and Di Vizio (2009) for instance, and to the work of Ramis, Sauloy and
Zhang (2013) and references therein.

The confluence problem consists in determining the limit of the solutions,
possibly
rescaled, as $q$ tends to $1$. In the setting of linear $q$-algebraic
equations, Di Vizio and Zhang (2009) gave some key results. In this book,
we give a couple of very elementary
confluence results motivated by the applications in the last chapter.

The asymptotics of the solutions as $q$ tends to $0$ or infinity has been
studied in the specific context of the $q$-Lagrange inversion by
Barbe and McCormick (2013), leading to unexpected connections between
the Taylor formula and renewal theory.

Di Vizio (2002) and Andr\'e and Di Vizio (2004) cover the case where $q$ is
of modulus $1$, which gives rise to arithmetic considerations.

The asymptotic behavior of the coefficients of the solutions when $q$
depends on $n$
and tends to $1$, that is, of $f_n(q_n)$ with $\lim_{n\to\infty} q_n=1$, is
important for some applications in probability and physics. Perhaps
Tackacz (1991, 1995) are the first rigorous studies of this topic, in the
special case of the $q$-Catalan equation, and these results are mentioned in
some of the surveys in Guttman (2009).

\bigskip

\section{Content of this book}

This book is inspired by the combinatorial nature of $q$-algebraic
equations. In particular, understanding the asymptotic behavior of
the coefficients of the solution yields some information on the combinatorial
structure that they count. As illustrated in the surveys edited by
Guttman (2009), the asymptotic questions of interest in combinatorics and
its applications to physics are difficult and hence, so far, have resisted
systematic methods. This book is a modest first step toward addressing these
problems, presenting a rather systematic study of $q$-algebraic equations
and the asymptotic behavior of the coefficients of their solutions. As we
will illustrate on concrete examples in the last chapter, our results yield
quite a good understanding of the solutions and their regularity, as well as
useful algorithms and numerical methods for studying the asymptotic behavior
of their coefficients.

\bigskip

In order to determine the solutions and the exponents occurring in them,
we will use a Newton-Puiseux polygon. As documented in Christensen
(1996) and Enriques (1915), this method was originally designed to compute
formal power series solutions of algebraic equations. It was also used
in the context of differential equations by Briot and Bouquet (1856),
Fine (1898, 1890), Ince (1926), Ritt (1936) and Cano (1993). Its use in the
$q$-algebraic setting goes back to the earliest papers in the subject, such as
Adams (1931).  This technique allows us to show that the set of exponents of
any solution of \qAlgebraic\ is contained in a finitely generated semi-group,
which is an analogue of Puiseux's theorem. This mirrors a similar result of
Grigoriev and Singer (1991) for differential equations. However, in general,
there is no guarantee that a $q$-algebraic equation has such a solution,
unlike algebraic ones.

Building upon the work of van der Hoeven (2001)
in the differential equation setting, the Newton-Puiseux
construction allows us to show that up to ramifications and a further change
of function, we may often assume that the polynomial $P$ in \qAlgebraic\
is in solved form, meaning that it has the form
$$
  c+a_0z_0+a_1z_1+\cdots +a_kz_k+zQ(z,z_0,z_1,\ldots,z_k) \, ,
$$
where the $a_i$ and $c$ are complex numbers, some nonzero, and $Q$ is a
new polynomial.
In other words, the coefficient of $z^0$ in $P$ is an affine function of
$z_0,z_1,\ldots,z_k$. This solved form yields a recursion for the coefficients
of the solution, albeit a complicated one. Despite this somewhat daunting
complexity, this recursion is the key to obtaining asymptotic estimates
on the coefficients of the solution.

Maillet's (1903) theorem is a classical result on the growth of the
coefficients of a formal solution of a nonlinear differential equation. It
states that the formal solution $\varphi(z)=\sum_{n\geq 0} \varphi_n z^n$ of a
differential equation satisfies $|\varphi_n|\leq n!^s R^n$ for some constants
$s$ and $R$. This result was refined by Malgrange (1989) who gave
bounds for $s$. These bounds were recovered by Cano (1993) also for singular
solutions.

For linear $q$-algebraic equations, the first studies of the convergence
or divergence of the solutions seem due to B\'ezivin (1992a, 1992b) and
B\'ezivin and Boutabaa (1992). Simplifying, the analogue of the Maillet
theorem then states that if \qAlgebraic\ has a power series
solution $f(z)=\sum_{n\geq 0} f_n z^n$ and $q$ is of modulus greater than
$1$, then $|f_n|\leq |q|^{sn^2}R^n$ for some $s$ and $R$. For nonlinear
equations, Zhang (1998) gives bounds for $s$ which parallel those of Malgrange
(1989) for differential equations. In most cases,
we will provide more precise estimates of the coefficients in the form of
an asymptotic equivalent up to a term of order $1$ which can often be
evaluated numerically when $q$ is specified. The technique is in essence
a refinement of the Laplace method, using that \qAlgebraic\ expresses a
complex recursion on the coefficients $f_n$ of the solution, and analyzing
precisely the leading terms in that recursion. This analysis allows us to
transform the equation into one of the form
$$
  \calC(z)f(z)=U(f)(z)
$$
where $\calC$ is a polynomial, or eventually an entire function, and $U$ is
an operator which, when acting on $f$, has the property that the radius of
convergence of $U(f)$ is always greater than that of $f$.

The Newton-Puiseux construction also yields numerical algorithms for computing
the solutions. We will describe those algorithms and show their efficiency
on specific equations, some particularly complicated, involving hundreds of
terms.

As we will see, our sharp estimates on the coefficients of the solutions
are generic, meaning that for a specific equation they usually hold for
all but some exceptional values of $q$. For linear equations, we will explore
the non-generic cases, giving a very precise refinement of B\'ezivin's (1992b)
results, in particular constructing explicitly the co-kernel
associated to the linear operator defining a linear $q$-algebraic equation,
acting on various spaces of formal power series. Various index theorems
for these operators follow. The general principle is that regularity of the
solution translates into
the possibility of obtaining a new equation for a functional of this solution,
thus in the possibility of transforming the equation; the key is then to
identify classes of equations which are stable under these transformations.

While most of the results are illustrated throughout the text on simple
equations, and in particular on the $q$-Catalan equation or some elementary
variants, the last chapter is devoted to examples of $q$-algebraic
equations which arise in combinatorial applications, knot theory,
classification of surfaces, and present
sometimes some very substantial challenges. As we will see, our theory brings
a good understanding of these equations, often delivering sharp estimates
on the coefficients of the solutions, but not always. Combined with computer
algebra packages and numerical estimates, the theory developed in this
book yields valuable insights on the solutions of specific $q$-algebraic
equations when $q$ is given.

\bigskip\bigskip\bigskip

\noindent{\bf Some notations and conventions.}

\bigskip

\noindent
While $i$ denotes an integer everywhere in this book, $\imath$ denotes a
complex root of $-1$, that is, $\imath^2=-1$.

\bigskip

\noindent
Throughout the book, if $(u_n)$ and $(v_n)$ are two sequences, with $(v_n)$
having finitely many vanishing terms, we write $u_n\sim c v_n$ as $n$ tends
to infinity to signify $\lim_{n\to\infty} u_n/v_n=c$. In particular,
if $c=0$, this means $u_n=o(v_n)$ as $n$ tends to infinity.

\bigskip

\noindent
A basis is often a Schauder basis, meaning a sequence of elements $(b_n)$ in
a vector space such that any element $f$ has a unique formal decomposition
$f=\sum_{n\in \NN} f_n b_n$. In particular, we consider the sequence of
powers, $(z^n)$, to be a basis of the formal power series.

\DoNotPrint{

Before putting our results in context, their flavor is illustrated on the
equation
$$\eqalignno{\qquad
  2f(z)=
  &{}4z^3f(qz)f(q^6z)+5q^2 z^6f(z)f(q^9z)f(q^{10}z)\cr
  &{}+18q^4 z^7 f(q^{14}z)^2+9z^{10}f(q^{-3}z)f(q^5z)f(q^{14}z)f(q^{16}z)\cr
  &{}+3z^{14}f(q^{-5}z)+(q^8+2q^{17}) z^{14}f(z)\cr
  &{}+72z^{14} f(z)f(q^3z)f(q^5z)+1+15z^7 \, .
  &\equa{runningEx}\cr}
$$
From one of our result and
few lines of simple calculations it follows that whenever $q$ is a complex
number of modulus greater than $1$,
for some positive constant $c_q$ and for the positive root $R_q$ of the
equation $z^3+9q^{-24}z^7=1$, if $f(z)=\sum_{n\geq 0} f_n z^n$,
$$
  f_n\sim c_q q^{n(n-3)} R_q^{-n}
  \eqno{\equa{runningExFinal}}
$$
as $n$ tends to infinity. The main interest of such formula is that $c_q$ does
not depend on $n$, so that the asymptotic growth of the sequence $(f_n)$ is
entirely captured by the term  $q^{n(n-3)} R_q^{-n}$.

The significance of our results is related to the many applications
of $q$-functional equations, and a chapter is devoted to examples
coming from combinatorics, dynamical systems, knot theory
and statistical physics.

The study of {\it linear} $q$-difference equations has a long history
spanning a century, from Carmichael (1912), Birkhoff (1913),
Adams (1929, 1931), Trjitzinsky (1938) to the more recent works of
B\'ezivin (1992), Ramis (1992), Sauloy (2000, 2003), Zhang (2002), Ramis,
Sauloy and Zhang (2013). Nonlinear $q$-functional equations, which
seem more prevalent in applied mathematics, have been
studied systematically only in the past few years by Zhang (1998),
Di Vizio (2008), Li and Zhang (2011). It is noticeable that despite
an apparent increase in complexity from linear to nonlinear equations,
our results when specialized to linear equations are new and much sharper
than previously known ones.

Our regularity results on the asymptotic behavior of $(f_n)$ are reminiscent of
Maillet's (1903) theorem on formal power series\note{all this needs to be
rephrased}
solutions of algebraic differential equations. Maillet's result was extended
to analytic nonlinear differential equations by Malgrange (1989), and though
our technique allows us to extend our result to some $q$-analytic functional
equations, the needed assumptions on the analytic function are not particularly
sightly and we choose to restrict our exposition to $q$-algebraic equations,
a setting which seems suitable in most applications.

The Maillet-Malgrange theorem was extended to $q$-analytic functional
equations by Zhang (1998), who showed that the solution belongs to {\it some}
$q$-Gevrey class, meaning that the sequence $(f_n)$ can grow at most as some
$q^{cn^2}$ for some unspecified $c$. This result was made more precise by
Di Vizio (2009) and Cano and Fortuny Ayuso (2012), in the sense that an upper
bound for $c$ was provided in terms of the Newton polygon associated with
a linearized version of the $q$-functional equation. While these results are
important from a theoretical perspective since they are indeed comparable to
the Maillet-Malgrange theorem, they are insufficient for many applications, in
particular in combinatorics and statistical physics where $(f_n)$ is
the cardinality of some interesting
set, and one is interested in calculating this cadinality in a nice closed
form. Obtaining such an explicit form is usually impossible with
our current knowledge, and one has to settle for less, such as
having a good estimate on the growth of $f_n$ with $n$. Our result
provides such estimate when $f$ is a divergent series, for in many cases
it provides an explicit
asymptotic equivalent for $f_n$ up to a multiplicative constant.

A different view on the existence and regularity questions was developed
by Li and Zhang (2011) who gave sufficient conditions for an analytic
nonlinear $q$-difference equation to have an analytic solution. In the case
of $q$-algebraic equations, we provide an alternative sufficient condition.

There is no loss of generality in assuming that the polynomial $P$ is
irreducible. However, in some applications, such as in combinatorics, one may
derive a $q$-algebraic equation for a generating function, and the polynomial
$P$ may not be irreducible.

}

\vfill\eject