% 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