\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm {\LARGE\bf The Rational-Transcendental Dichotomy of \\ \vskip .1in Mahler Functions} \vskip 1cm \large Jason P.~Bell\\ Department of Mathematics\\ Simon Fraser University\\ Burnaby, BC\\ Canada\\ \href{mailto:jpb@math.sfu.ca}{\tt jpb@math.sfu.ca}\\ \ \\ Michael Coons\\ School of Mathematical and Physical Sciences\\ The University of Newcastle\\ Callaghan, NSW\\ Australia\\ \href{mailto:Michael.Coons@newcastle.edu.au}{\tt Michael.Coons@newcastle.edu.au}\\ \ \\ Eric Rowland\\ LaCIM\\ Universit\'e du Qu\'ebec \`a Montr\'eal\\ Montr\'eal, QC\\ Canada\\ \href{mailto:rowland@lacim.ca}{\tt rowland@lacim.ca}\\ \end{center} \vskip .2 in \begin{center} {\em To Jean-Paul Allouche on his $(2+3+1+9+5)\cdot 3$-th birthday.} \end{center} \begin{abstract} In this paper, we give a new proof of a result due to B\'ezivin that a $D$-finite Mahler function is necessarily rational. This also gives a new proof of the rational-transcendental dichotomy of Mahler functions due to Nishioka. Using our method of proof, we also provide a new proof of a P\'olya-Carlson type result for Mahler functions due to Rand\'e; that is, a Mahler function which is meromorphic in the unit disk is either rational or has the unit circle as a natural boundary. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The {\em Thue-Morse sequence} $\{t(n)\}_{n\geq 0}$ over the alphabet $\{-1,1\}$ is given by $t(n)=(-1)^{s(n)}$ where $s(n)$ is the number of $1$s in the base $2$ expansion of the number $n$. Using this definition it is immediate that the sequence $\{t(n)\}_{n\geq 0}$ is $2$-automatic. That is, there is a deterministic finite automaton that takes the base $2$ expansion of $n$ as input and outputs the value $t(n)$ (see Figure \ref{Fig1}); the definition of an automatic sequence will be discussed in more detail below. \begin{figure}[htbp] \begin{center} \setlength{\unitlength}{1mm} \begin{picture}(60,20) \put(14.25,4){{$1$}} \put(15,5){\circle{20}} \put(43,4){{$-1$}} \put(45,5){\circle{20}} \put(-2,5){\vector(1,0){10}} \qbezier(40, 10)(30, 15)(20, 10) \put(21, 10.5){\vector(-2,-1){1}} \put(29,14){{\tt 1}} \qbezier(40, 0)(30, -5)(20, 0) \put(39, -.5){\vector(2,1){1}} \put(29,-1){{\tt 1}} \qbezier(12, 11.5)(12, 15)(9, 17) \qbezier(9, 17)(6, 19)(6, 15) \qbezier(6, 15)(6, 11)(9, 9) \put(8.25, 10){\vector(1,-1){1}} \put(12,15){{\tt 0}} \qbezier(50, 10)(54, 13)(52, 17) \qbezier(52, 17)(51, 19)(48, 15) \qbezier(48, 15)(47, 13.3)(47, 12) \put(47.6, 13.6){\vector(-1,-2){1}} \put(53.5,15){{\tt 0}} \end{picture} \caption{The generating $2$-automaton of the Thue-Morse sequence.} \label{Fig1} \end{center} \end{figure} \noindent It is also immediate using the definition that the Thue-Morse sequence is the unique sequence given by $t(0)=1$, $t(2n)=t(n)$ and $t(2n+1)=-t(n)$. Thus, writing the generating power series for $t(n)$ as $T(z)=\sum_{n\geq 0}t(n)z^n$, we have that $T(z)$ satisfies the functional equation $$(1-z)T(z^2)=T(z).$$ The {\em Thue-Morse number} is the evaluation of the generating power series for $\{t(n)\}_{n\geq 0}$ at $z=1/2$; that is, the number $T(1/2)=\sum_{n\geq 0}t(n)2^{-n}.$ Due to the nature of the construction of the Thue-Morse sequence and the functional equation satisfied by its generating power series, the Thue-Morse number and those numbers with similar attributes are a natural class of numbers to consider from the perspectives of transcendental number theory and Diophantine approximation. Focusing on the functional equation aspect, in the late 1920s and early 1930s, Mahler \cite{M1929, M1930a, M1930b} showed that if $F(z)\in\mathbb{Q}[[z]]$ satisfies \begin{equation}\label{LF}a(z)F(z^k)=b(z)F(z)\end{equation} for some $a(z),b(z)\in\mathbb{Q}[z]$ and $F(z)$ is transcendental over $\mathbb{Q}(z)$, then for all but finitely many algebraic points $\alpha$ in radius of convergence of $F(z)$, $F(\alpha)$ is transcendental over $\mathbb{Q}$. One of the main goals of Mahler's above-cited work was to provide a proof of the transcendence of the Thue-Morse number, a goal which Mahler accomplished \cite{M1929}. Extensions of Mahler's work in this area have been, and are still, a vital area of research in number theory under the heading {\em Mahler's method}. In this paper, we are concerned with the following generalization of~\eqref{LF}. Let $k\geq 2$ be a positive integer. We say that a function $F(z)\in\mathbb{C}[[z]]$ is {\em $k$-Mahler} (or sometimes just {\em Mahler}) provided there exist a non-negative integer $d$ and polynomials $a_0(z),\ldots,a_d(z)\in\mathbb{C}[z]$ with $a_0(z)a_d(z)\neq 0$ such that \begin{equation}\label{F} a_0(z)F(z)+a_1(z)F(z^k)+\cdots+a_d(z)F(z^{k^d})=0.\end{equation} The functional equation in \eqref{F} is called a {\em Mahler-type functional equation}. Loxton and van der Poorten \cite{LP1988} claimed an analogue of Mahler's above-mentioned result for functions $F(z)\in\mathbb{Z}[[z]]$ satisfying \eqref{F}, although their proof is not complete \cite[remark following Corollary~2]{B1994}. One may also wish to possibly avoid the functional equation approach and focus on generalizing the automatic aspect inspired by the Thue-Morse sequence. While the definition of automaticity based on computability by finite state automata is useful in a computational setting, we will use an equivalent and combinatorial (or sequential) definition which is more suitably generalized in a mathematical context. Let $\mathbf{f}:=\{f(n)\}_{n\geq 0}$ be a sequence with values in a ring $R$. We define the {\em $k$-kernel} of $\mathbf{f}$ to be the set $$\Big\{\{f(k^ln+r)\}_{n\geq 0}:l\geq 0 \mbox{ and } 0\leq r0$ centered at the origin by $B(0,r)$. \begin{lemma} Let $k\geq 2$ be an integer and let $F(z)\in\mathbb{C}[[z]]$ be a $k$-Mahler function. Then $F(z)$ has a positive radius of convergence. \end{lemma} \begin{proof} Let $k\geq 2$ be an integer and $F(z)\in\mathbb{C}[[z]]$ be a $k$-Mahler function satisfying, say, $$\sum_{j=0}^{d} a_j(z)F(z^{k^j})=0,$$ for $a_j(z)\in\mathbb{C}[z]$ with $a_0(z)a_d(z)\neq 0$. Noting that a $k$-regular series is analytic in the unit disk (see Allouche and Shallit \cite[Theorem 2.10]{AS1992}), Theorem \ref{Dumas} gives that $F(z)$ converges in $B(0,r)$, where $r\in(0,1)$ is the minimal distance from $0$ to a nonzero root of $a_0(z)(z-1)$. \end{proof} \begin{lemma}\label{merofinite} Let $k\geq 2$ be an integer and let $F(z)\in\mathbb{C}[[z]]$ be a $k$-Mahler function. The function $F(z)$ is meromorphic if and only if it has finitely many singularities. Moreover, if $F(z)$ is not meromorphic then it has infinitely many non-polar singularities on the unit circle. \end{lemma} \begin{proof} Let $k\geq 2$ be an integer and $F(z)\in\mathbb{C}[[z]]$ be a $k$-Mahler function satisfying, say, $$\sum_{j=0}^{d} a_j(z)F(z^{k^j})=0,$$ for $a_j(z)\in\mathbb{C}[z]$ with $a_0(z)a_d(z)\neq 0$. Write \begin{equation}\label{F1} F(z^{k^d})=-\sum_{j=0}^{d-1} \frac{a_j(z)}{a_d(z)}F(z^{k^j}).\end{equation} Suppose that $F(z)$ is not meromorphic on the plane, and let $\alpha=Re^{i\vartheta}$ be a non-polar singularity of $F(z)$ with $R\geq 1$ minimal and $\vartheta\in[0,2\pi);$ note that such a minimal singularity exists since the singularity set is closed and $F(z)$ has only polar singularities in the unit circle (see Theorem \ref{Dumas}).%We will consider two cases $R>1$ and $00$ since by the previous lemma $F(z)$ has a positive radius of convergence. We note here that the case $R>1$ cannot occur. To see this, suppose that $z=Re^{i\vartheta_0}$ is a non-polar singularity of $F(z)$ of minimal distance $R>1$ to the origin and $\vartheta_0\in[0,2\pi)$. Then $F(z^{k^d})$ has a non-polar singularity at $z=R^{k^{-d}}e^{i\vartheta_0 k^{-d}},$ and so by \eqref{F1} it must be the case that the right-hand side of \eqref{F1} has a non-polar singularity at $z=R^{k^{-d}}e^{i\vartheta_0 k^{-d}}.$ Since this cannot be contributed by the rational functions, there is some $j_0\in\{0,\ldots,d-1\}$ such that $F(z^{k^{j_0}})$ has a non-polar singularity at $z=R^{k^{-d}}e^{i\vartheta_0 k^{-d}},$ which in turns implies that $F(z)$ has a non-polar singularity at $z=R^{k^{-d+j_0}}e^{i\vartheta_0 k^{-d+j_0}}.$ Since $R^{k^{-d+j_0}}1$ be fixed, but large enough so that all zeros of the polynomials $a_0(z),\ldots,a_d(z)$ have modulus strictly less than $L$. Let $M\in\mathbb{N}$ be such that $M>1$ and $\alpha=Re^{i\vartheta}$ is a singularity of $F(z)$ with $L^{k^{Md}}\leq R1$ such that all of the zeros of $a_d(z)$ are in the open disk $B(0,L)$ of radius $L$ centered at the origin. Notice that since the $a_i(z)$ are polynomials, there is an $N>1$ and a constant $C>1$ such that for $|z|\geq L$, we have \begin{equation}\label{aiadbound} \max_{0\leq i\leq d-1}\left\{\left|\frac{a_i(z)}{a_d(z)}\right|\right\}1$, this implies that there is some constant $b>0$ such that for $n\geq d$ we have $$M_n\leq L^{bk^n}.$$ Now let $m\geq b+2$ be a natural number, fix an $\alpha\in\mathbb{C}$ and consider $$F^{(m-1)}(\alpha)=\frac{1}{2\pi i}\int_{\gamma_n}\frac{F(z)}{(z-\alpha)^m}dz,$$ where $\gamma_n$ is the circle of radius $L^{k^n}$ with $n$ large enough so that $\alpha$ is inside the circle of radius $L^{k^n}/2$ centered at the origin. Then for all $z$ on $\gamma_n$ we have that $$\frac{|z|}{2}\leq |z-\alpha|.$$ Thus for $n$ large enough, we have $$|F^{(m-1)}(\alpha)|\leq \frac{1}{2\pi} \cdot 2\pi L^{k^n}\cdot \frac{2^mM_n}{(L^{k^n})^m}= \frac{2^mM_n}{(L^{k^n})^{m-1}}\leq 2^mL^{k^n(b-m+1)}.$$ Recall that $m\geq b+2$ so that the above gives that $$|F^{(m-1)}(\alpha)|\leq \frac{2^m}{L^{k^n}}.$$ Since $n$ can be taken arbitrarily large, we have that $F^{(m-1)}(\alpha)=0$. But $\alpha\in\mathbb{C}$ was arbitrary, and so $F^{(m-1)}(z)$ is identically zero; hence $F(z)$ is a polynomial. \end{proof} \begin{theorem}\label{main1} Let $k\geq 2$ be an integer and $F(z)\in\mathbb{C}[[z]]$ be a $k$-Mahler function. If $F(z)$ has only finitely many singularities, then $F(z)$ is a rational function. \end{theorem} \begin{proof} Let $k\geq 2$ be an integer and $F(z)\in\mathbb{C}[[z]]$ be a $k$-Mahler function satisfying \begin{equation}\label{F3} \sum_{j=0}^{d} a_j(z)F(z^{k^j})=0,\end{equation} for $a_j(z)\in\mathbb{C}[z]$ with $a_0(z)a_d(z)\neq 0$. If $F(z)$ has only finitely many singularities, then there is a non-zero polynomial $q(z)\in\mathbb{C}[z]$ such that $q(z)F(z)$ is entire. For $j\in\{0,\ldots,d-1\}$ set $$q_j(z):=\frac{1}{q(z^{k^j})}\prod_{i=0}^d q(z^{k^i})\in\mathbb{C}[z].$$ Multiplying \eqref{F3} by $\prod_{i=0}^d q(z^{k^i})\in\mathbb{C}[z]$ we then have that $$\sum_{j=0}^{d} a_j(z)q_j(z)q(z^{k^j})F(z^{k^j})=0,$$ where since $q(z)$ is not identically zero we have that $a_0(z)q_0(z)a_d(z)q_d(z)\neq 0.$ Hence $q(z)F(z)$ is an entire $k$-Mahler function and thus, by the preceding lemma, a polynomial. This proves that $F(z)$ is a rational function. \end{proof} \begin{proof}[Proof of Theorem \ref{Df}] A $D$-finite series has finitely many singularities; namely, if $F(z)$ satisfies $p_0(z) F(z) + p_1(z) F'(z) + \cdots + p_m(z) F^{(m)}(z) = 0$ then each singularity of $F(z)$ is a zero of $p_m(z)$. An application of Theorem \ref{main1} provides the desired result. \end{proof} The following corollary is a result of Nishioka \cite[Theorem~5.1.7]{N1996}. \begin{corollary}[Nishioka \cite{N1996}] Let $k\geq 2$ be an integer and $F(z)\in\mathbb{C}[[z]]$ be a $k$-Mahler function. If $F(z)$ is algebraic, then $F(z)$ is a rational function. \end{corollary} \begin{proof} An algebraic series is $D$-finite; see Stanley \cite[Theorem~2.1]{S1980}. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{A P\'olya-Carlson type result} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\begin{definition} We define the {\em Cartier operators} $\gL_i:\mathbb{C}((x))\to \mathbb{C}((x))$ by $$\gL_i\left(\sum_{n\geq -j}c_nx^n\right)=\sum_{n\geq (-j-i)/k} c_{kn+i}x^n$$ for $i=0,\ldots,k-1$. %\end{definition} %Note that for any $G(z),H(z)\in\mathbb{C}[[z]]$ we have that $\gL_i(G(z)H(z^k))=\gL_i(G(z))H(z)$ for each $i=0,\ldots,k-1$ (see Becker \cite[Lemma 2]{B1994}). \begin{proof}[Proof of Theorem \ref{PC}] Suppose that $F(z)\in\mathbb{C}[[z]]$ is $k$-Mahler and not rational. By the structure theorem, we have that $F(z)$ has only polar singularities in the unit disk. Note that we have already shown that if $F(z)$ is meromorphic, then it is a rational function, so we may suppose that there is some non-polar singularity of $F(z)$. By Lemma \ref{merofinite} we have that there are infinitely many non-polar singularities of $F(z)$ on the unit circle. Let $S$ be the closure of the non-polar singularities of $F(z)$ on the unit circle. We will show that $S$ is the entire unit circle. Towards a contradiction, suppose there are points $\beta,\gamma\in S$ with $\arg\beta<\arg\gamma$ such that the points on the small arc of the unit circle strictly between $\beta$ and $\gamma$ are not singularities of $F(z)$. Let \begin{equation}\label{pFd}\sum_{i=0}^d p_i(z)F(z^{k^i})=0\end{equation} be a non-trivial Mahler functional equation for $F(z)$ which is minimal with respect to $d$, and define the vector space $$V:=\sum_{i\geq 0}\mathbb{C}(z)F(z^{k^i}).$$ It is quite easy to see that $V$ has dimension $d$ as a $\mathbb{C}(z)$-vector space since $d$ is minimal with respect to the relation \eqref{pFd}. Indeed, suppose that $$\sum_{i=0}^n q_i(z)F(z^{k^i})\in V$$ with $q_n(z)\neq 0$ and $n\geq d$. Then multiplying by $1$ and subtracting zero using \eqref{pFd}, we have that \begin{align*} \sum_{i=0}^n q_i(z)&F(z^{k^i}) = \sum_{i=0}^{n-1}q_i(z)F(z^{k^i})\\ &+\frac{1}{p_d(z^{k^{n-d}})}\left(p_d(z^{k^{n-d}})q_n(z)F(z^{k^n})-q_n(z)\sum_{i=0}^d p_i(z^{k^{n-d}})F(z^{k^{n-d+i}})\right)\\ &\quad\qquad = \sum_{i=0}^{n-1}q_i(z)F(z^{k^i})-\frac{1}{p_d(z^{k^{n-d}})}\left(q_n(z)\sum_{i=0}^{d-1} p_i(z^{k^{n-d}})F(z^{k^{n-d+i}})\right)\\ &\quad\qquad \in\sum_{i=0}^{n-1}\mathbb{C}(z)F(z^{k^{i}}). \end{align*} Continuing in this manner shows that $$\sum_{i=0}^n q_i(z)F(z^{k^i})\in\sum_{i=0}^{d-1}\mathbb{C}(z)F(z^{k^{i}}).$$ Thus $\dim_{\mathbb{C}(z)}V\leq d.$ Since $d$ was chosen minimally so that \eqref{pFd} holds, we have that $\dim_{\mathbb{C}(z)}V=d$. Similarly, for all integers $L>0$, the $\mathbb{C}(z)$-vector space $$\sum_{i=0}^{d-1}\mathbb{C}(z)F(z^{k^{i+L}})$$ is $d$-dimensional, and since it is a subspace of $V$ it is equal to $V$. Thus since $F(z)\in V$, there are then polynomials $q_{0,L}(z),\ldots,$ $q_{d,L}(z)$ with $q_{0,L}(z)$ nonzero such that \begin{equation}\label{qFL} q_{0,L}(z)F(z)=\sum_{i=1}^d q_{i,L}(z)F(z^{k^{i+L-1}}).\end{equation} Since $S$ is the closure of the non-polar singularities, and polar singularities are isolated, we can pick a non-polar singularity $\alpha$ of $F(z)$ as close as we wish to $\beta$. Pick such an $\alpha$ and an $L>0$ big enough so that $\alpha\omega^j$ is in the arc between $\beta$ and $\gamma$ for $j=1,\ldots,d+1$ where $\omega:=e^{2\pi i/k^L}.$ Notice that $q_{0,L}(z)F(z)$ has a non-polar singularity at $z=\alpha$ since $q_{0,L}(z)$ is nonzero. Define \begin{multline*}W:=\Big\{(s_1(z),\ldots,s_d(z))\in\mathbb{C}(z)^d:\\ \sum_{i=1}^d s_i(z)F(z^{k^{i+L-1}})\mbox{ has at most a polar singularity at $z=\alpha$}\Big\}.\end{multline*} Note that $W$ is a $\mathbb{C}(z)$-vector space. Then sending $z\mapsto \omega^jz$ in \eqref{qFL} for $j=1,\ldots,d+1$, we have \begin{equation}\label{qFeq} q_{0,L}(\omega^jz)F(\omega^jz)=\sum_{i=1}^d q_{i,L}(\omega^jz)F((\omega^jz)^{k^{i+L-1}}). \end{equation} By construction, the left-hand side of \eqref{qFeq} has no non-polar singularity at $z=\alpha$. Since $\omega$ is a $k^L$th root of unity, $F((\omega^jz)^{k^{i+L-1}}) = F(z^{k^{i+L-1}})$ for all $j$ and all $i\geq 1$, and thus $$\mathbf{u}_j(z):=\left(q_{1,L}(\omega^jz),\ldots,q_{d,L}(\omega^jz)\right)\in W$$ for $j=1,\ldots,d+1$. Since $\dim_{\mathbb{C}(z)}W