\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