% 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 $s0$, $\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