\documentclass[12pt,reqno]{amsart} \usepackage{latexsym} \usepackage{amssymb} \usepackage{color} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} %\definecolor{webgreen}{rgb}{0,.5,0} %\definecolor{webbrown}{rgb}{.6,0,0} %\usepackage{psfig,epsf,latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\textheight}{8.7in} \setlength{\topmargin}{0.0in} \newtheorem{Theo}{Theorem} \newtheorem{prop}{Proposition} \newtheorem{lemma}{Lemma} \newtheorem{Cor}{Corollary} \newcommand{\F}{\mathbb{F}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \bigskip \title{A criterion for non-automaticity of sequences} \maketitle \centerline{Jan-Christoph Schlage-Puchta} \begin{center} Mathematisches Institut\\ Eckerstr. 1\\ 79111 Freiburg\\ Germany\\ \href{jcp@arcade.mathematik.uni-freiburg.de}{\tt jcp@arcade.mathematik.uni-freiburg.de} \\ \end{center} \vskip .4in \begin{center} {\bf Abstract} \end{center} We give a criterion for a sequence $(a_n)_{n\geq 1}$ to be non-automatic, i.e., for when there does not exist a finite automaton generating this sequence. As application we generalize a result of Yazdani on the non-automaticity of multiplicative sequences. \vskip .4in \section{Introduction.} A finite automaton consists of a finite set $\mathcal{S}$ of states with a specified starting state $s_0$, an input alphabet $\mathcal{A}$, an output alphabet $\mathcal{B}$, and two functions $f:\mathcal{A}\times\mathcal{S}\rightarrow\mathcal{S}$, $g:\mathcal{S}\rightarrow\mathcal{B}$. Given a word $w$ over $\mathcal{A}$, the output of the automaton is determined as follows: At first, the automaton is in $s_0$. Then the first letter $a$ of $w$ is read, and the new state of the automaton is changed to $s_1=f(a, s_0)$. Then the next letter $b$ of $w$ is read, and the state of the automaton is changed to $s_2=f(b, s_1)$. This is repeated untill all letters of $w$ are read, and the procedure terminates. If the automaton ends in the state $s$, it returns the value $g(s)$. Fix some integer $q\geq 2$. In our context, the alphabet $\mathcal{A}$ consists of the integers $0, 1, \ldots, q-1$, and $\mathcal{B}$ consists of integers or elements in some fixed finite fields. Every integer $n\geq 1$ can be written in the form $n=\sum e_i(n) q^i$ with $e_i(n)\in\{0, 1,\ldots, q-1\}$, hence $n$ can be viewed as word over $\mathcal{A}$, and the automaton can be applied to this word. More precisely, write $n=\sum_{i=0}^k e_i q^i$ with $e_i\in\{0, 1, \ldots, q-1\}$ and $e_k\neq 0$, and identify the integer $n$ with the string $e_ke_{k-1}\ldots e_1e_0$. In this way, every automaton defines a sequence $(a_n)_{n\geq 0}$. An automaton with $\mathcal{A}=\{0, 1, \ldots, q-1\}$ is called a $q$-automaton, and an arbitrary sequence is called $q$-automatic, if there exists a $q$-automaton which generates this sequence. More generally, a sequence is called automatic, if it is $k$-automatic for some integer $k\geq 2$. Apart from intrinsic interest, the question whether a given sequence is automatic is of interest because of its number theoretical consequences. In fact, automaticity and algebraicity are linked via the following result of G. Christol, T. Kamae, M. Mend\`es France and G. Rauzy \cite{CKMR}. \begin{Theo} Let $p$ be a prime number, $(a_n)_{n\geq 1}$ be a sequence of elements in $\F_p$. Then the series $\sum_{n=1}^\infty a_n x^n$ is algebraic over $\F_p(x)$ if and only if the sequence $(a_n)$ is $p$-automatic. \end{Theo} Hence, to prove the transcendence of a power series, we need only to show that a certain sequence is not automatic. This can for example be accomplished by the following theorem of A. Cobham \cite{Cob}. \begin{Theo}\label{ratcrit} Let $(a_n)_{n\geq 1}$ be an automatic seqence over an alphabet $\mathcal{B}$. Assume that for some $a\in\mathcal{B}$ the limit $\delta_a=\lim_{x\rightarrow\infty}\frac{1}{x}|\{n\leq x: a_n=a\}|$ exists. Then $\delta_a$ is rational. \end{Theo} In \cite{All}, J.-P. Allouche used this to prove the following result. \begin{Cor}\label{AllCor} The power series $f(x)=\sum_{n\geq 1} (\mu(n)\bmod p) x^n$ is transcendental over $\F_p(x)$ for all primes $p$. \end{Cor} Here, $\mu(n)$ denotes the M\"obius-function, i.e., the multiplicative function satisfying $\mu(p)=-1, \mu(p^k)=0$ for all primes $p$ and integers $k\geq 2$. \begin{proof} Since $\mu(n)=0$ if and only if $n$ is divisible by some square $a^2, a\geq 2$, we see that in the notation of Theorem \ref{ratcrit}, \[ \delta_0=\lim_{x\rightarrow\infty}\frac{1}{x} |\{n\leq x:\exists a\geq 2, a^2|n\} = 1-\prod_p\left(1-\frac{1}{p^2}\right) = 1-\frac{\pi^2}{6}, \] hence, the limit exists and is irrational. So by Theorem \ref{ratcrit}, the sequence $(\mu(n)\pmod{p})_{n\geq 1}$ is not automatic. \end{proof} Albeit short and ingenious, the proof has the disadvantage that it is difficult to apply to other situations for two reasons. First, it requires the evaluation of $\prod_p\left(1-\frac{1}{p^2}\right)$ and a proof that the result is irrational. This is equivalent to Euler's evaluation of $\zeta(2)$ and the fact that $\pi^2$ is irrational. In our case, these are well known, yet non-trivial facts. However, in other cases there might be no known formula for $\delta_a$. The second, more fundamental problem is that in many cases $\delta_a=\frac{1}{|\mathcal{B}|}$ for all $a$, so Theorem \ref{ratcrit} cannot be applied. The aim of this note is to give another proof of Corollary 1. In fact, we have the following more general result. \begin{Theo}\label{gapcrit} Let $(a_n)_{n\geq 1}$ be an automatic sequence. Assume that for some letter $a$ and for every integer $k$ there exists an integer $n$ such that $a_n=a_{n+1}=\cdots=a_{n+k}=a$. Then there is a constant $c>0$ such that for an infinite number of integers $x$ we have $a_n=a$ for all $n\in[x, (1+c)x]$. \end{Theo} Other criteria involving strings of repeated values can be found in \cite{Yao}. \section{Main results} Before proving our theorem, we first give some corollaries. \begin{Cor}\label{sieve} Let $(q_i)_{i\geq 1}$ be a sequence of positive integers such that $\sum_i\frac{1}{q_i}<\infty$. Assume that for all $k\geq 1$, there are indices $i_1, \ldots, i_k$ such that $(q_{i_l}, q_{i_m})=1$ for $1\leq l0$ and arbitrarily large integers $x$ such that $a_n=0$ for all $n\in[x, (1+c)x]$. On the other hand, we can bound from below the number of integers $n\in[x, (1+c)x]$ such that $a_n=0$ in the following way. Let $\epsilon>0$ be given, and let $K$ be some constant with $\sum_{i>K}\frac{1}{q_i}<\epsilon$. Let $L$ be the least common multiple of $q_1, \ldots, q_K$. Then the set of all integers $n$ such that $q_i\not|n$ for all $i\leq K$ is periodic with period $L$, and has density $d_K\geq\prod_{i\leq K} \left(1-\frac{1}{q_i}\right)$, with equality if and only if the $q_i$ are pairwise coprime. Note that \[ d_K>\prod_{i=1}^\infty \left(1-\frac{1}{q_i}\right)>0, \] that is, $d_K$ can be bounded away from 0 independently of $K$. Now for $x\rightarrow\infty$, we have \begin{eqnarray} |\{n\in[x, (1+c)x]: a_n=1\}| & \geq & |\{n\in[x, (1+c)x]: \forall i\leq K: q_i\not| n\}|\label{diveq}\\ &&\qquad - \sum_{i>K}|\{n\in[x, (1+c)x]: q_i| n\}|\nonumber\\ & \geq & d_Kcx - L - \epsilon cx - |\{i: q_i\leq (1+c)x\}|\nonumber\\ & \geq & (d_K-\epsilon)cx + o(x)\nonumber, \end{eqnarray} since $|\{i: q_i\leq (1+c)x\}|=o(x)$, for otherwise the series $\sum\frac{1}{q_i}$ would diverge. In fact, if \[ \limsup\limits_{x\rightarrow\infty}\frac{|\{i:q_i0, \] there exists some constant $k>0$ such that \[ \limsup\limits_{n\rightarrow\infty} \frac{|\{i: 2^n\leq q_i<2^{n+1}\}|}{2^{n+1}} > k, \] thus, $\sum_i \frac{1}{q_i}=\infty$. By Theorem~\ref{gapcrit} we would find arbitrarily large integers $x$ such that the left-hand side of (\ref{diveq}) is zero, thus we arrive at a contradiction. So the sequence $(a_n)_{n\geq 1}$ is not automatic. \end{proof} Choosing $q_i=p_i^2$, with $p_i$ the $i$-th prime number, we find that the sequence $(\mu(n)^2\pmod{p})_{n\geq 1}$ is not automatic, which is slightly stronger then Corollary \ref{AllCor}. Out next result deals with the automaticity of multiplicative functions. \begin{Cor} \label{Cor:Yaz} Let $f:\N\rightarrow\Z$ be a multiplicative function. Let $q\geq 2$ be an integer. Assume that the following conditions hold. \begin{enumerate} \item There exist infinitely many primes $p$ such that there exists some $h_p\geq 1$ with $q|f(p^{h_p})$. \item If $b_n$ denotes the $n$-th integer with $f(b_n)\not\equiv 0\pmod{q}$, we have $\frac{b_{n+1}}{b_n}\rightarrow 1$. \end{enumerate} Then the sequence $(f(n)\pmod{q})_{n\geq 1}$ is not automatic. \end{Cor} \begin{proof} As in the proof of Corollary \ref{sieve}, the first condition implies that for every $k$ there exist some $n$ with $f(n)\equiv f(n+1)\equiv \cdots \equiv f(n+k)\equiv 0\pmod{q}$, while the second condition means that for every $c>0$ there are only finitely many integers $x$ such that $f(n)\equiv0\pmod{q}$ holds for all $n\in[x, (1+c)x]$. Together with Theorem \ref{gapcrit}, we obtain the desired conclusion. \end{proof} This result generalizes a theorem of S. Yazdani \cite[Theorem 2]{Yaz}. In fact, the conditions on $f$ are relaxed in two aspects: First, the integers $h_p$ are allowed to depend on $p$. More important, the lower bound for the density of the set of integers $n$ satisfying $q\nmid f(n)$ in the second condition of Corollary \ref{Cor:Yaz} is smaller then in \cite[Theorem 2]{Yaz}. The latter theorem requires $q\nmid f(p)$ for all primes in a residue class, which by the prime number theorem for arithmetic progressions implies condition (2) of Corollary \ref{Cor:Yaz}. \medskip Now we return to the proof of Theorem \ref{gapcrit}. \medskip {\em Proof of Theorem \ref{gapcrit}.} Assume that $(a_n)_{n\geq 1}$ is a sequence satisfying the conditions of Theorem \ref{gapcrit}, and it is generated by a $q$-automaton. For every integer $l$, let $n$ be an integer such that $a_{n+i}=a$ for all $i\leq q^l$. We may assume that $n$ is divisible by $q^l$. Indeed, by hypothesis, for all integers $l\geq 1$ there exists an integer $m$ such that $a_{m+i}=a$ for $0\leq i<2q^l$. Let $n_l$ be the least integer such that $n\geq m$ and $q^l|n$. Then $n