% LaTeX file for an 8 page document
\documentclass[12pt]{article}

\usepackage{amssymb,amsmath,amsthm}

%% The lines between the two rows of %'s are more or less compulsory.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setlength{\textwidth}{6.3in}
\setlength{\textheight}{8.7in}
\setlength{\topmargin}{0pt}
\setlength{\headsep}{0pt}
\setlength{\headheight}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}

\makeatletter
\newfont{\footsc}{cmcsc10 at 8truept}
\newfont{\footbf}{cmbx10 at 8truept}
\newfont{\footrm}{cmr10 at 10truept}
\renewcommand{\ps@plain}{%
\renewcommand{\@oddfoot}{\footsc the electronic journal of combinatorics
  {\footbf 11} (2004), \#R00\hfil\footrm\thepage}}
\makeatother
\pagestyle{plain}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% The further structure of the front page need not be exactly as below,
%% but the header must contain the names and addresses of the authors
%% as well as the submission and acceptance dates.

\title{On Some Non-Holonomic Sequences}

\author{Stefan Gerhold\thanks{Supported by the SFB-grant F1305 of the Austrian FWF}\\
\small Research Institute for Symbolic Computation\\[-0.8ex]
\small Johannes Kepler University Linz, Austria\\[-0.8ex]
\small \texttt{stefan.gerhold@risc.uni-linz.ac.at}}

\date{\small 
Submitted: Oct 15, 2003;  Accepted: Nov 25, 2004; Published: Dec 15, 2004\\
\small Mathematics Subject Classifications: 11B37, 11R32, 11J81}

\begin{document}
\maketitle

\begin{abstract}
A sequence of complex numbers is holonomic if it satisfies a linear recurrence with
polynomial coefficients. A power series is holonomic if it satisfies
a linear differential equation with polynomial coefficients, which is
equivalent to its coefficient sequence being holonomic. It is well known
that all algebraic power series are holonomic. We show that the analogous
statement for sequences is false by proving that the sequence $\{\sqrt{n}\}_n$ is not holonomic.
In addition, we show that $\{n^n\}_n$, the Lambert $W$ function and $\{\log{n}\}_n$ are not holonomic,
where in the case of $\{\log{n}\}_n$ we have to rely on an open conjecture from transcendental number theory.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}


\section{Introduction}

A sequence $u:\mathbb{N}\rightarrow\mathbb{C}$
is called \emph{holonomic} ($P$\emph{-recursive}, $P$\emph{-finite}) over a field $K\subseteq\mathbb{C}$ if it satisfies a homogeneous linear recurrence
\begin{equation}\label{eq:rec}
  p_0(n)u(n) + p_1(n)u(n+1) + \ldots + p_d(n)u(n+d)=0 \qquad n\geq 0,
\end{equation}
where the $p_k$ are polynomials with coefficients in $K$ and $p_d$
is not identically zero. If $K$ is not mentioned, it is understood to
be $\mathbb{C}$. Many combinatorial sequences are holonomic.
A formal power series $f(z)=\sum_{n\geq 0}u(n)z^n$ is \emph{holonomic} ($D$\emph{-finite}, $P$\emph{-finite}) if it satisfies a homogeneous linear
ordinary differential equation
\begin{equation}\label{eq:deq}
  p_0(z)f(z) + p_1(z)f'(z) + \ldots + p_d(z)f^{(d)}(z)=0
\end{equation}
with polynomial coefficients. Holonomicity of meromorphic functions is defined in the same way.
It is well known \cite{St80}
that a power series is holonomic if and only if its coefficient sequence is.

There are powerful methods for showing that certain power series are \emph{not}
holonomic. For instance, given that $f$ is holonomic, $1/f$ (if defined)
is holonomic if and only if $f'/f$ is algebraic, and $\exp(\int f)$ is
holonomic if and only if $f$ is algebraic \cite{Ha85,Si86}. Such results can be used
to show that a given sequence is not holonomic by applying
them to its generating function. For instance, the Bell numbers and the Bernoulli numbers with exponential generating
functions $\exp(\mathrm{e}^z-1)$ and $z/(\mathrm{e}^z-1)$, respectively, can be
seen to be non-holonomic in this way.

On the sequence level, we have that a sequence that is not
eventually zero but has arbitrarily long runs of zeros cannot
satisfy a recurrence of the form \eqref{eq:rec}. Furthermore, for every
holonomic sequence $u$ there is a constant $\gamma$ such that $|u(n)|\leq
n!^\gamma$ for $n\geq 2$ \cite{KMa76,EMa03}. In general, this bound is best possible, since $\{n!^m\}_n$ is easily
seen to be holonomic for integer $m$. However, none of these techniques
apply to the sequences $\{\sqrt{n}\}_n$, $\{\log{n}\}_n$ and $\{n^n\}_n$ or to the corresponding power series.

\section{Powers of Hypergeometric Sequences}

A power series $f(z)$ is called \emph{algebraic} if it satisfies
$Q(f(z),z)=0$ for some non-zero bivariate polynomial $Q$. All algebraic power series are holonomic \cite{St80}. The following theorem shows that
the analogous statement for sequences does not hold. For instance, putting $p=q=1$, $a_1=2$, $b_1=1$, $r=\frac{1}{2}$ shows
that the sequence $\{\sqrt{n+1}\}_n$ (and hence also $\{\sqrt{n}\}_n$) is not holonomic.

\begin{theorem}\label{thm:hg^r}
  Let $a_1,\dots,a_p,b_1,\dots,b_q$ be pairwise distinct positive integers (possibly $p=0$ or $q=0$, but not both).
  Define the sequence $\{h(n)\}_n$ by
  \begin{equation}\label{eq:h(n)}
    h(n)=\frac{(a_1)_n\dots(a_p)_n}{(b_1)_n\dots(b_q)_n}\quad n\geq 0,
  \end{equation}
  where $(c)_n$ denotes the rising factorial
  \[
    (c)_n=\prod_{i=1}^n (c+i-1),
  \]
  and let $r \in \mathbb{Q} \backslash \mathbb{Z}$.
  Then the sequence $\{h(n)^r\}_n$ is not holonomic.
\end{theorem}

Before proving Theorem \ref{thm:hg^r}, we briefly comment on
its assumptions. Sequences like \eqref{eq:h(n)} are called
\emph{hypergeometric}, where in general the $a_i$ and $b_i$ may be complex numbers with
the exception that no $b_i$ can be a negative integer or zero. Such sequences
have the property that the quotient $\frac{h(n+1)}{h(n)}$ is a rational
function of $n$, and they are obviously holonomic, since they satisfy a linear recurrence of order one
with polynomial coefficients. We assume the
$a_i$ and $b_i$ to be pairwise distinct to rule out cases like
$\sqrt{(1)_n(1)_n}=n!$. The fact that $a_i$ and $b_i$ are integers
will be used in an argument from algebraic number theory. Finally, if
some $a_i$ was negative, the sequence $h(n)^r$ would be
eventually zero, hence holonomic. Indeed, it is not difficult to see that
if two sequences differ only at finitely many entries, one of them is holonomic
if and only if the other one is.

If a sequence of real numbers is holonomic (over $\mathbb{C}$), it is holonomic over $\mathbb{R}$:
\[  
  \sum_{k=0}^d p_k(n) u(n+k) = 0\quad \Longrightarrow\quad
  \sum_{k=0}^d \Re(p_k(n)) u(n+k) = 0.
\]
The following lemma generalizes this.

\begin{lemma}\label{le:coeffs in K}
  Let $K$ be a subfield of $\mathbb{C}$ and $\{u(n)\}_n$ be a holonomic sequence with $u(n)\in K$
  for all $n$. Then $\{u(n)\}_n$ is holonomic over $K$.
\end{lemma}

\begin{proof}
  Suppose
  \begin{equation}\label{eq:rec beg of proof}
    \sum_{k=0}^d p_k(n) u(n+k) = 0 \quad\text{with}\quad p_k(n)=\sum_{i=0}^{m_k} c_{ki} n^i, \quad c_{ki}\in \mathbb{C},
  \end{equation}
  and set $m= m_0 + \dots + m_d + d + 1$.
  Since $u(n)\in K$, for each $n$ the recurrence \eqref{eq:rec beg of proof} gives rise to a linear equation
  $v_n^T c=0$ with $v_n\in K^m$ that is satisfied
  by the coefficient vector
  \[
    c = (c_{00},\dots,c_{0m_0},\ \dots\ ,c_{d0},\dots,c_{dm_d})^T \in \mathbb{C}^m.
  \]
  We may assume that $u$ is not the zero sequence (otherwise the statement of the lemma is trivial), hence not all $v_n$ are the zero vector. Let $s$ be
  maximal such that there are $s$ vectors $v_{n_1},\dots,v_{n_s}$ that are
  linearly independent over $\mathbb{C}$. We have $s<m$ since $c\neq 0$. The linear system  
  \begin{align*}
    v_{n_1}^T c & = 0\\
    & \vdots \\
    v_{n_s}^T c & = 0
  \end{align*}
  with coefficients in $K$ has more unknowns than equations, hence there is a solution $0\neq \tilde{c}\in K^m$. Since
  any vector $v_n$ is a $\mathbb{C}$-linear combination of $v_{n_1},\dots,v_{n_s}$,
  the vector $\tilde{c}$ satisfies $v_n^T \tilde{c} = 0$ for all $n$. We obtain the desired
  recurrence for $u(n)$ by replacing each $c_{ki}$ in \eqref{eq:rec beg of proof} with the corresponding entry
  of $\tilde{c}$.
\end{proof}

Another proof of Lemma \ref{le:coeffs in K} has been given by Lipshitz \cite{Li89}.

\begin{lemma}\label{le:product}
  If $\{u(n)\}_n$ and $\{v(n)\}_n$ are holonomic sequences, then their termwise (or Hadamard) product
  $\{u(n)v(n)\}_n$ is holonomic. In particular, powers of holonomic sequences with positive integer exponent are holonomic.
\end{lemma}
\begin{proof}
  See, e.g., \cite{St80}.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm:hg^r}]
We assume that $h(n)^r$ is holonomic.
Write $r=\frac{\alpha}{\beta}$ with $\beta>0$, $\gcd(\alpha,\beta)=1$ and
take integers $\alpha^\prime$, $\beta^\prime$ such that
$\alpha^\prime \alpha + \beta^\prime \beta = 1$.
\\

\noindent \emph{Case 1:} $\alpha^\prime>0$. The sequence $h(n)$ is holonomic.
Observe that $h(n)^{-1}$ is of the form \eqref{eq:h(n)}, too, hence it is also holonomic.
By Lemma \ref{le:product}, we find that
\[
  (h(n)^r)^{\alpha^\prime} h(n)^{\beta^\prime} = h(n)^\frac{1-\beta^\prime \beta}{\beta} h(n)^{\beta^\prime} = h(n)^{1/\beta}
\]
is holonomic.

\noindent \emph{Case 2:} $\alpha^\prime<0$. In this case
\[
  (h(n)^r)^{-\alpha^\prime} h(n)^{-\beta^\prime} = h(n)^\frac{\beta^\prime \beta-1}{\beta} h(n)^{-\beta^\prime} = h(n)^{-1/\beta}
\]
is holonomic.

\noindent \emph{Case 3:} $\alpha^\prime=0$. This cannot happen since $\beta\neq \pm 1$.
\\

We assume that we are in Case 1. Case 2 can be reduced to Case 1 by replacing $h(n)$ with $h(n)^{-1}$.
For any integer $s \geq 2$ we define
\[
  K_s = \mathbb{Q}(2^{1/\beta},3^{1/\beta},\dots,s^{1/\beta}).
\]
Then $K = \bigcup_{s \geq 2} K_s$ is a field. Indeed, $K$ is the intersection
of all subfields of $\mathbb{C}$ that contain the set $\{s^{1/\beta} \mid s \in \mathbb{N}\}$. Since $h(n)^{1/\beta} \in K$ for all $n$, by Lemma
\ref{le:coeffs in K} the sequence $h(n)^{1/\beta}$ satisfies a recurrence
\[
  \sum_{k=0}^d p_k(n) h(n+k)^{1/\beta} = 0 \qquad n\geq 0,
\]
where the $p_k$ are polynomials with coefficients in $K$. There is an integer
$s_0$ such that all these coefficients are in $K_{s_0}$.
For simplicity of notation assume
\begin{equation}\label{eq:max}
  a_1=\max(a_1,\dots,a_p,b_1,\dots,b_q).
\end{equation}
Now choose $n_0$ larger than the roots of $p_d$ and such that
$n_1=a_1+n_0+d-1$ is larger than $s_0$ and prime. Then
\begin{align*}
  h(n_0+d)^{1/\beta} &= n_1^{1/\beta}
  \left(\frac{(a_1)_{n_0+d-1}(a_2)_{n_0+d} \dots (a_p)_{n_0+d}}{(b_1)_{n_0+d} \dots (b_q)_{n_0+d}}\right)^{1/\beta} \\
  &= -p_d(n_0)^{-1} \sum _{k=0}^{d-1} p_k(n_0) h(n_0+k)^{1/\beta}
\end{align*}
implies
\begin{equation}\label{eq:n1}
 n_1^{1/\beta} \in K_{n_1-1}.
\end{equation}
(In the case where the maximum in \eqref{eq:max} occurs among the
denominator parameters $b_i$ it is important to note $h(n_0+d)^{1/\beta} \neq 0$.)
But
\[
  K_{n_1-1} = \mathbb{Q}(\rho_1^{1/\beta},\dots,\rho_t^{1/\beta}),
\]
where $\rho_1,\dots,\rho_t$ are the primes smaller than $n_1$, and by Galois
Theory \cite[Section 4.12]{Ga98}, the degree of this field over $\mathbb{Q}$ is
\[
  [K_{n_1-1}:\mathbb{Q}] = [\mathbb{Q}(\rho_1^{1/\beta},\dots,\rho_t^{1/\beta}):\mathbb{Q}] = \beta^t.
\]
Adjoining $n_1^{1/\beta}$ would enlarge the degree to $\beta^{t+1}$, hence \eqref{eq:n1}
is impossible. This contradiction shows that $h(n)^r$ is not holonomic.
\end{proof}

As an application we show that $f(x,n)=1/(x^2+n)$ is not holonomic. We will not need the definition of holonomicity for functions
$f(x_1,\dots,x_r,n_1,\dots,n_s)$ of several continuous and several discrete arguments here, but only the fact that
definite integration preserves holonomicity \cite{Ze90b}. For $n\geq 1$ we have
\[
  \int_0^\infty \frac{dx}{x^2+n} = \left. \frac{1}{\sqrt{n}} \arctan \frac{x}{\sqrt{n}} \right|_{x=0}^\infty =
  \frac{\pi}{2 \sqrt{n}},
\]
thus $1/(x^2+n)$ is not holonomic by Theorem \ref{thm:hg^r}.

\section{The Sequence $\log n$}

The proof of Theorem \ref{thm:hg^r} immediately yields the following criterion.

\begin{proposition}\label{pr:infnot}
  If there are infinitely many $n$ such that
  \[
    u(n) \notin \mathbb{Q}(\{u(k)\mid 0\leq k<n\}),
  \]
  then the sequence $\{u(n)\}_n$ is not holonomic.
\end{proposition}

With this criterion we can prove that $\{\log{n}\}_n$ is not holonomic, assuming the following weak form of Schanuel's Conjecture.

\begin{conjecture}\label{cj:schanuel}
  Suppose that $\alpha_1,\dots,\alpha_s\in\mathbb{R}$ are linearly independent over $\mathbb{Q}$, and that
  $\mathrm{e}^{\alpha_1},\dots,\mathrm{e}^{\alpha_s}$ are integers. Then $\alpha_1,\dots,\alpha_s$ are algebraically independent.
\end{conjecture}

\begin{theorem}
  If Conjecture \ref{cj:schanuel} holds, then $\{\log{n}\}_n$ is not holonomic.
\end{theorem}
\begin{proof}
  For distinct primes $\rho_1,\dots,\rho_s$, the numbers $\log{\rho_1},\dots,\log{\rho_s}$ are linearly independent over
  $\mathbb{Q}$, since for all $c_1,\dots,c_s\in\mathbb{Z}$ we have
  \begin{equation}
    0 = \sum_{i=1}^s c_i \log{\rho_i} = \log(\rho_1^{c_1}\dots \rho_s^{c_s})
      \Longrightarrow \rho_1^{c_1}\dots \rho_s^{c_s} = 1 \Longrightarrow \forall i: c_i = 0.
  \end{equation}
  By Conjecture \ref{cj:schanuel}, $\log{\rho_1},\dots,\log{\rho_s}$ are algebraically independent and thus
  the assumption of Proposition \ref{pr:infnot} is satisfied.
\end{proof}

\section{The Sequence $n^n$ and the Lambert $W$ Function}

\begin{theorem}\label{thm:n^n}
  For rational numbers $a,b$ with $b\neq 0$, the sequence $\{(a+n)^{bn}\}_n$ is not holonomic.
\end{theorem}
\begin{proof}
  By Lemma \ref{le:product} we may assume $b\in\mathbb{Z}$. Now the entries of the sequence are in $\mathbb{Q}$, and if
  it was holonomic, then by Lemma \ref{le:coeffs in K}
  there would be polynomials $p_k$ with rational coefficients, $p_d\neq 0$, such that
  \[
    \sum_{k=0}^d p_k(n)(n+a+k)^{b(n+k)} = 0 \qquad n\geq 0.
  \]
  Multiplying both sides with $n^{-bn}$ yields
  \[
    \sum_{k=0}^d (n+a+k)^{bk} p_k(n) \left(1+\frac{a+k}{n}\right)^{bn} = 0.
  \]
  Putting
  \[
    m = \max_{0\leq k\leq d}(\deg{p_k} + bk) \quad\text{and}\quad M = \{k \mid \deg{p_k} + bk =m\},
  \]
  we find (lc denotes the leading coefficient)
  \begin{align*}
    &\sum_{k=0}^d n^{bk} p_k(n) \left(1 + \frac{a+k}{n}\right)^{bn} = O(n^{m-1}) \quad\text{as}\quad n \to \infty \\
    &\sum_{k \in M} \text{lc}(p_k) \left(1 + \frac{a+k}{n}\right)^{bn} = O(n^{-1}).
  \end{align*}
  Now we take the limit $n \to \infty$.
  \[
    \sum_{k \in M} \text{lc}(p_k) \mathrm{e}^{b(a+k)} = 0,
  \]
  hence
  \[
    \sum_{k \in M} \text{lc}(p_k) \mathrm{e}^{bk} = 0.
  \]
  This contradicts the transcendence of $\mathrm{e}^b$.
\end{proof}

The Lambert $W$ function is defined implicitly by the equation
\[
  W(z)\mathrm{e}^{W(z)}=z.
\]
In combinatorics $-W(-z)$ is known as the exponential generating function of rooted labelled trees.
All information we will need about $W(z)$ can be found in \cite{Co96}.

\begin{corollary}The Lambert $W$ function is not holonomic.
\end{corollary}
\begin{proof}This follows from Theorem \ref{thm:n^n} with $a=0$ and $b=1$, Lemma \ref{le:product} and the series expansion
\[
  W(z) = \sum_{n=1}^\infty \frac{(-n)^{n-1}}{n!} z^n.
\]
\end{proof}

Alternatively, a well-known method for proving non-holonomicity \cite{St80} can be applied to $W(z)$. The derivatives
of $W(z)$ can be written as polynomials in $z$ and $W(z)$ \cite{Co96}, and plugging this representation
into \eqref{eq:deq} yields a non-zero bivariate polynomial $Q$ with $0=Q(z,W(z))=Q(W(z) \mathrm{e}^{W(z)}, W(z))$.
This is impossible, since the exponential function is not algebraic.

We remark that $W$ satisfies the algebraic differential equation
\[
  z(W(z)+1)W'(z) = W(z).
\]

\section{Open Problems}

We have proved that $\{n^r\}_n$ is not holonomic for $r\in\mathbb{Q}\backslash \mathbb{Z}$. It is natural to
conjecture that it is not holonomic for $r\in\mathbb{C}\backslash \mathbb{Z}$. We did not succeed in finding a
proof that $\{\log{n}\}_n$ is not holonomic that does not depend on Schanuel's Conjecture.
Furthermore, there are many other sequences that could be considered. For instance, we do not know of any proof
that the sequence of primes is not holonomic.


\begin{thebibliography}{99}

\bibitem{Co96}
\textsc{R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, D. E. Knuth} (1996):
On the Lambert $W$ Function,
\emph{Advances in Computational Mathematics}, vol. 5, 329-359

\bibitem{Ga98}
\textsc{L. Gaal} (1998):
\emph{Classical Galois Theory with Examples},
AMS Chelsea Publishing

\bibitem{Ha85}
\textsc{W. Harris, Y. Sibuya} (1985):
The Reciprocals of Solutions of Linear Ordinary Differential Equations,
\emph{Advances in Mathematics} 58, 119-132

\bibitem{Li89}
\textsc{L. Lipshitz}
(1988): $D$-finite Power Series,
\emph{J. Algebra} 122, 353-373

\bibitem{KMa76}
\textsc{K. Mahler} (1976):
Lectures on Transcendental Numbers,
\emph{Lecture Notes in Mathematics} 546,
Springer

\bibitem{EMa03}
\textsc{E. Maillet} (1903):
Sur les s\'eries div\'ergentes et les \'equations diff\'erentielles,
\emph{Ann. Sci. Ecole Norm. Sup.} Ser 3, 3, 487-518

\bibitem{Si86}
\textsc{M. Singer} (1986):
Algebraic Relations Among Solutions of Linear Differential Equations,
\emph{Trans. Amer. Math. Soc.} 295 2, 753-763

\bibitem{St80}
\textsc{R. P. Stanley} (1980):
Differentiably Finite Power Series,
\emph{Europ. J. Combinatorics} 1, 175-188

\bibitem{Ze90b}
\textsc{Zeilberger, D.} (1990):
A Holonomic Systems Approach to Special Functions Identities,
\emph{J. of Computational and Applied Math.} 32, 321-368

\end{thebibliography}

\end{document}