\documentstyle[11pt]{article}
\newcommand{\GN}{\mbox{\rm I$\!$N}}
\newcommand{\GF}{\mbox{\rm I$\!$F}}
\newcommand{\GZ}{\mbox{\rm Z$\!\!$Z}}

\author{J.-P. Allouche
\thanks{C. N. R. S., Math\'ematiques, 351 cours de la
Lib\'eration, F-33405 Talence Cedex, (France).}}
\title{Finite automata and arithmetic}
\date{}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}

\begin{document}
\maketitle

\section{Introduction}

The notion of sequence generated by a finite automaton, (or
more precisely a finite automaton with output function, 
i. e. a ``uniform tag system") has been introduced 
and studied by Cobham in 1972 (see \cite{Cobham1}; see also
\cite{Eilenberg}). 
In 1980, Christol, Kamae, Mend\`es France and Rauzy, 
(\cite{CKMFR}), proved that a sequence with values in a finite 
field is automatic if and only if the related formal power 
series is algebraic over the rational functions with coefficients 
in this field: this was the starting point of numerous results
linking automata theory, combinatorics and number theory.
Our aim is to survey some results in this area, especially
transcendence results, and to provide
the reader with examples of automatic sequences. We will also
give a bibliography where more detailed studies can be found.
See in particular the survey of Dekking, Mend\`es France and 
van der Poorten, \cite{Dekking}, or the author's, 
\cite{Alloucheexpo}, where many relations between finite 
automata and number theory (and between finite automata and 
other mathematical fields) are described. For applications of
finite automata to physics see \cite{Allouchephys}.

In the first part of this paper we will recall the basic 
definitions and give the theorem of Christol, Kamae, Mend\`es 
France and Rauzy. We will also give five typical examples of 
sequences generated by finite automata.

In the second part we will discuss transcendence results 
related to automata theory, giving in particular some results
concerning the Carlitz zeta function.

We will indicate in the third part of this paper the possible 
generalizations of these automatic sequences.

Finally in an appendix we will give  an elementary ``automatic" 
proof of the transcendence of the Carlitz formal power series 
$\Pi$.
 
\section{Generalities, examples, the main theorem}

\subsection{Sequences generated by finite automata}

\begin{definition}

Let $q$ be an integer ($q \geq 2$). A $q$-automaton consists of

- a finite set $S = \{a_1 = i, a_2, \cdots, a_d \}$, which is
called the set of states. One of the states is denoted by $i$ and 
called the initial state,

- $q$ maps from $S$ to itself, labelled $0, 1, \cdots, q-1$. The
image of the state $s$ by the map $j$ is denoted by $j.s$,

- a map (the output function), say $\varphi$, from $S$ to a set $Y$.

\noindent This ``machine" generates a sequence with values in $Y$,
say $(u_n)_{n \geq 0}$, as follows: to compute the term $u_n$, 
one expands $n$ in base $q$, say $n = \sum_{j=0}^{\ell} n_j q^j$,
with $0 \leq n_j \leq q-1$. Then each $n_j$ is interpreted as
one of the maps from $S$ to itself, and these maps are applied
to $i$ to obtain:
$$u_n = \varphi \left [n_{\ell}(n_{\ell -1}(\cdots(n_1(n_0.i))\cdots))
\right ].$$


\noindent Such a sequence is called a {\bf $q$-automatic sequence}.

\end{definition}

\bigskip

\subsection{Examples}

1) The Prouhet-Thue-Morse sequence

\medskip

This sequence has been studied by Thue at the beginning of the century,
to give an example of a binary sequence without cubes (i. e. without
three consecutive identical blocks, see \cite{Thue1} and 
\cite{Thue2}), by Morse in the 20's, (see \cite{Morse}), but also by 
Prouhet in 1851 (\cite{Prouhet}). It can be 
defined by the following $2$-automaton :

\medskip

- the set of states is $S = \{i, a \}$,

- the maps $0$ and $1$ from $S$ to $S$ are defined by,
$$0.i = i, \, 0.a = a,$$
$$1.i = a, \, 1.a = i,$$

- the output function is defined by,
$$\varphi(i) = 0, \, \varphi(a) = 1.$$
Hence this sequence begins by:
$$0 \, 1 \, 1 \, 0 \, 1 \, 0 \, 0 \, 1 \, 1 \, 0 \, 0 \, 1 \, \cdots$$

\newpage

\begin{figure}[h]
\setlength{\unitlength}{0.02in}%
\begin{picture}(187,64)(220,530)
\thicklines
\put(300,600){\circle{20}}
\put(400,600){\circle{20}}
\put(320,610){\oval(40,40)[tl]}
\put(380,610){\oval(40,40)[tr]}
\put(320,630){\vector(1,0){34}}
\put(350,630){\line(1,0){30}}
\put(320,590){\oval(40,40)[bl]}
\put(380,590){\oval(40,40)[rb]}
\put(318,570){\line(1,0){40}}
\put(380,570){\vector(-1,0){32}}
\put(291,600){\oval(30,15)[l]}
\put(409,600){\oval(30,15)[r]}
\put(350,634){$1$}
\put(350,560){$1$}
\put(298,598){i}
\put(398,598){a}
\put(269,598){0}
\put(428,598){0}
\put(324,540){$\varphi(i) = 0, \, \varphi(a)=1$}
\end{picture}
\caption{An automaton which generates the Prouhet-Thue-Morse sequence}
\end{figure}

\bigskip

\noindent 2) The Rudin-Shapiro sequence

\medskip

Let $a = (a_n)_{n \geq 0}$ be any sequence of $\pm 1$. What can be said 
of the asymptotic size of the supremum of its Fourier transform
$$F_N(a) = \sup_{x \in [0, 1]}\mid \sum_{n=0}^{N-1} a_n e^{2i\pi n x} 
\mid?$$
The following bounds are trivial:
$$\sqrt{N} = \parallel \sum_{n=0}^{N-1} a_n e^{2i\pi n x} 
\parallel_{L^2} \leq \parallel \sum_{n=0}^{N-1} a_n e^{2i\pi n x}
\parallel_{L^{\infty}} = F_N(a) \leq N.$$
On the other hand, for almost all (in the sense of the Haar
measure on $\{-1, +1\}^{\scriptsize \GN}$) sequences of $\pm 1$, one has
$$F_N(a) \leq \sqrt{N \log N}.$$
In other words, for a ``random" sequence $a$, $F_N(a)$ behaves roughly
like $\sqrt{N}$. Shapiro in 1951 (\cite{Shapiro}) and Rudin in 1959
(\cite{Rudin}) constructed a sequence $a$ for which $F_N(a) \leq 
C \sqrt{N}$ and which is {\em deterministic} for any reasonable 
definition of this notion. Moreover this sequence is $2$-automatic,
and can be generated by the following $2$-automaton:

\medskip

- set of states $S = \{i, a, b, c \}$,

- maps from $S$ to $S$,
$$0.i = i, \, 0.a = i, \, 0.b = c, \, 0.c = c,$$
$$1.i = a, \, 1.a = b, \, 1.b = a, \, 1.c = b,$$

- output function,
$$\varphi(i) = \varphi(a) = +1,$$
$$\varphi(b) = \varphi(c) = -1.$$

\medskip

\noindent Hence this sequence begins by:
$$+1 \, +1 \, +1 \, -1 \, +1 \, +1 \, -1 \, +1 \, +1 \, \cdots$$

\bigskip

\begin{figure}[h]
\setlength{\unitlength}{0.012in}%
\begin{picture}(187,104)(240,530)
\thicklines
\multiput(300,600)(100,0){4}{\circle{20}}
\multiput(320,610)(100,0){3}{\oval(40,40)[tl]}
\multiput(380,610)(100,0){3}{\oval(40,40)[tr]}
\multiput(320,630)(100,0){3}{\vector(1,0){30}}
\multiput(350,630)(100,0){3}{\line(1,0){30}}
\multiput(320,590)(100,0){3}{\oval(40,40)[bl]}
\multiput(380,590)(100,0){3}{\oval(40,40)[rb]}
\multiput(320,570)(100,0){3}{\line(1,0){30}}
\multiput(380,570)(100,0){3}{\vector(-1,0){30}}
\put(291,600){\oval(30,15)[l]}
\put(609,600){\oval(30,15)[r]}
\put(350,634){$1$}
\put(350,556){$0$}
\put(450,634){$1$}
\put(450,556){$1$}
\put(550,634){$0$}
\put(550,556){$1$}
\put(298,597){i}
\put(397,597){a}
\put(497,596){b}
\put(597,597){c}
\put(266,596){$0$}
\put(628,596){$0$}
\put(352,530){$\varphi(i) = \varphi(a) = +1, \, 
\varphi(b) = \varphi(c) = -1$}
\end{picture}
\caption{An automaton which generates the Rudin-Shapiro sequence}
\end{figure}

\bigskip

\noindent 3) The paperfolding sequence

\medskip

Folding repeatedly a sheet of paper yields a sequence of ``peaks"
$\Lambda$ and ``valleys" V which has been studied by many authors 
since the paper of Davis and Knuth (\cite{Davis}). This sequence can 
indeed be generated by the following $2$-automaton:

\medskip

- set of states $S = \{i, a, b, c \}$,

- maps from $S$ to $S$,
$$0.i = a, \, 0.a = b, \, 0.b = b, \, 0.c = c,$$
$$1.i = i, \, 1.a = c, \, 1.b = b, \, 1.c = c,$$

- output function,
$$\varphi(i) = \varphi(a) = \varphi(b) = \mbox{\rm V}, \, 
\varphi(c) = \Lambda.$$

\medskip

\noindent Hence this sequence begins by:
$$\mbox{\rm V} \, \mbox{\rm V} \, \Lambda \, \mbox{\rm V} \, 
\mbox{\rm V} \, \Lambda \, \Lambda \, \mbox{\rm V} \, \cdots$$

\newpage

\begin{figure}[h]
\setlength{\unitlength}{0.016in}%
\begin{picture}(187,64)(240,540)
\thicklines
\put(300,600){\circle{20}}
\put(400,600){\circle{20}}
\put(311,600){\line(1,0){79}}
\put(311,600){\vector(1,0){44}}
\put(500,650){\circle{20}}
\put(500,550){\circle{20}}
\put(508,650){\oval(34,15)[r]}
\put(509,650){\oval(20,8)[r]}
\put(520,648){$\scriptstyle 0$}
\put(526,648){$\scriptstyle 1$}
\put(508,550){\oval(34,15)[r]}
\put(509,550){\oval(20,8)[r]}
\put(520,548){$\scriptstyle 0$}
\put(526,548){$\scriptstyle 1$}
\put(291,600){\oval(30,15)[l]}
\put(272,598){$\scriptstyle 1$}
\put(408.92,604.46){\line(2,1){82}}
\put(408.92,604.46){\vector(2,1){47}}
\put(408.92,595.54){\line(2,-1){82}}
\put(408.92,595.54){\vector(2,-1){47}}
\put(350,603){$\scriptstyle 0$}
\put(450,629){$\scriptstyle 0$}
\put(450,579){$\scriptstyle 1$}
\put(298,598){i}
\put(398,598){a}
\put(498,648){b}
\put(498,548){c}
\put(300,540){$\varphi(i) = \varphi(a) = \varphi(b) = \mbox{\rm V}, 
\, \varphi(c) = \Lambda$}
\end{picture}
\caption{An automaton which generates the paperfolding sequence}
\end{figure}

\bigskip

\noindent 4) The Baum-Sweet sequence

\medskip

It is well known that, if a real number is quadratic over the 
rationals, then its continued fraction expansion is periodic or 
ultimately periodic. But nothing is known for algebraic numbers of 
degree $\geq 3$: no example is known with bounded partial quotients, 
nor with unbounded quotients.

If one replaces the real numbers by the field of Laurent series 
$\GF_q((X^{-1}))$ over the finite field $\GF_q$, the field of 
rational numbers by $\GF_q(X)$, and the ring of integers $\GZ$ by
the ring of polynomials $\GF_q[X]$, more is known. There is
indeed a theory of continued fractions, and the property of bounded
partial quotients has to be replaced by the property of quotients of
bounded degree (or equivalently quotients taking a finite number of 
values).

A first result has been given by Baum and Sweet in 1976 
(\cite{BaumSweet}): {\em there exists a Laurent series in} $\GF_2((X^{-1}))$,
{\em of degree $3$ over } $\GF_2(X)$, {\em such that its continued fraction has 
only finitely many partial quotients}. By the Christol, Kamae, Mend\`es
France and Rauzy theorem, (where the variable $X$ is replaced by 
$X^{-1}$), the sequence of coefficients of the Baum-Sweet
series is $2$-automatic. Here is a $2$-automaton which generates this 
sequence: 

\medskip

- set of states $S = \{i, a, b \}$,

- maps from $S$ to $S$,
$$0.i = a, \, 0.a = i, \, 0.b = b,$$
$$1.i = i, \, 1.a = b, \, 1.b = b,$$

- output function,
$$\varphi(i) = 1, \, \varphi(a) = \varphi(b) = 0.$$

\medskip

\noindent Hence this sequence begins by:
$$1 \, 1 \, 0 \, 1 \, 1 \, 0 \, 0 \, 1 \, 0 \, \cdots$$

\newpage

\begin{figure}[h]
\setlength{\unitlength}{0.015in}%
\begin{picture}(187,94)(220,532)
\thicklines
\put(300,600){\circle{20}}
\put(400,600){\circle{20}}
\put(500,600){\circle{20}}
\put(320,610){\oval(40,40)[tl]}
\put(380,610){\oval(40,40)[tr]}
\put(320,630){\vector(1,0){34}}
\put(350,630){\line(1,0){30}}
\put(320,590){\oval(40,40)[bl]}
\put(380,590){\oval(40,40)[rb]}
\put(318,570){\line(1,0){40}}
\put(380,570){\vector(-1,0){32}}
\put(293,600){\oval(35,15)[l]}
\put(506,600){\oval(35,15)[r]}
\put(509,600){\oval(15,8)[r]}
\put(410,600){\vector(1,0){45}}
\put(450,600){\line(1,0){40}}
\put(350,634){$\scriptstyle 0$}
\put(350,560){$\scriptstyle 0$}
\put(450,604){$\scriptstyle 1$}
\put(299,597){i}
\put(398,598){a}
\put(497.5,597){b}
\put(270,598){$\scriptstyle 1$}
\put(525,598){$\scriptstyle 1$}
\put(518,598){$\scriptstyle 0$}
\put(300,540){$\varphi(i) = 1, \, \varphi(a) = \varphi(b) = 0$}
\end{picture}
\caption{An automaton which generates the Baum-Sweet sequence}
\end{figure}

\bigskip

It can be shown that the term $u_n$ of the Baum-Sweet sequence $u$ is 
equal to $1$ if and only if there is no string of $0$'s of odd length 
in the binary expansion of $n$. Other examples have been given by
Mills and Robbins for all characteristics (\cite{MillsRobbins}).
A natural question due to Mend\`es France arises: given an algebraic
Laurent series whose partial quotients take only a finite number of
values, is the sequence of these partial quotients automatic? (remember
that the sequence of coefficients of the series is itself automatic
from the Christol, Kamae, Mend\`es France and Rauzy theorem).
The answer is yes for the example of Mills and Robbins in 
characteristic 3, (see \cite{AlloucheBetremaShallit}), and for their
examples in characteristic $p \geq 3$, (see \cite{Allouchefc}).
The sequence of partial quotients of the Baum-Sweet series has recently
been shown non-automatic by Mkaouar, \cite{Mkaouar}, but this sequence
can be generated by a non-uniform morphism, see below.
 
\bigskip

\noindent 5) The Hanoi sequence

\medskip

The well known towers of Hanoi game is the following: $N$ disks of 
diameter, say $1$, $2$, $\cdots$, $N$, are stacked on the first of 
three vertical pegs. At each step one is allowed to pick the topmost 
disk on a peg and to put it on another one, provided it is not stacked 
on a smaller disk. The game is over when all the disks are on a (new) 
peg. A classical recursive algorithm gives a (finite) sequence of moves 
of length $2^N -1$, which is optimal, to transfer $N$ disks from the 
first peg to another one. If one chooses to transfer the disks to the 
second peg if $N$ is odd, and to the third one if $N$ 
is even, all the sequences of moves of length $2^N-1$ given by the
algorithm are prefixes of a unique infinite sequence of moves on the 
six-letter alphabet of all possible moves. 
It has been proved in \cite{AlloucheDress} that this infinite
sequence is indeed $2$-automatic, and that it can be generated 
by the $2$-automaton given below.
Note that in the cyclic towers of Hanoi, (where the pegs are on a 
circle and where only clockwise moves are allowed), the infinite 
sequence of moves resulting from the classical cyclic algorithm is 
NOT automatic, but can be generated by a non-uniform morphism, 
(see \cite{AlloucheHanoicyclique}).

\begin{figure}[h]
\setlength{\unitlength}{0.0066in}%
\begin{picture}(500,693)(140,360)
\thicklines
%********************************************
\put(210,700){\circle{30}}
\put(405,765){\circle{30}}
%********************************************
\put(600,830){\circle{30}}
\put(596,826){\scriptsize $\overline{\rm c}$}
\put(650,916){\circle{30}}
\put(646,912){\scriptsize $\overline{\rm c}$}
\put(750,916){\circle{30}}
\put(746,912){\scriptsize $\overline{\rm a}$}
\put(800,830){\circle{30}}
\put(796,826){\scriptsize $\overline{\rm a}$}
\put(750,744){\circle{30}}
\put(746,739){\scriptsize $\overline{\rm b}$}
\put(650,744){\circle{30}}
\put(646,739){\scriptsize $\overline{\rm b}$}
%********************************************
\put(600,570){\circle{30}}
\put(596,567){\scriptsize a}
\put(650,484){\circle{30}}
\put(646,481){\scriptsize a}
\put(750,484){\circle{30}}
\put(746,481){\scriptsize c}
\put(800,570){\circle{30}}
\put(796,567){\scriptsize c}
\put(750,656){\circle{30}}
\put(746,652){\scriptsize b}
\put(650,656){\circle{30}}
\put(646,652){\scriptsize b}
%********************************************
\put(220,708){\vector(3,1){90}}
\put(220,708){\line(3,1){171}}
\put(296,742){\scriptsize $0$}
\put(394,757){\vector(-3,-1){90}}
\put(394,757){\line(-3,-1){170}}
\put(308,712){\scriptsize $0$}
\put(419,765){\vector(3,1){90}}
\put(419,765){\line(3,1){170}}
\put(497,799){\scriptsize $1$}
%********************************
%********************************
\put(612,835){\line(3,5){40}}
\put(626,860){\vector(-1,-1){0}}
\put(600,844){\line(3,5){38}}
\put(624,880){\vector(1,1){0}}
\put(638,860){\scriptsize $0$}
\put(610,880){\scriptsize $0$}
%********************************
\put(662,909){\line(1,0){75}}
\put(693,909){\vector(-1,0){0}}
\put(662,923){\line(1,0){75}}
\put(706.8,923){\vector(1,0){0}}
\put(697,892){\scriptsize $1$}
\put(697,929){\scriptsize $1$}
%********************************
\put(762,911){\line(3,-5){40}}    
\put(787,871){\vector(1,-1){0}}   
\put(750,902){\line(3,-5){37}}     
\put(765,877){\vector(-1,1){0}}    
\put(788,880){\scriptsize $0$}
\put(760,856){\scriptsize $0$}
%********************************
\put(762,749){\line(3,5){40}}
\put(776,774){\vector(-1,-1){0}}
\put(750,758){\line(3,5){38}}
\put(774,794){\vector(1,1){0}}
\put(788,774){\scriptsize $1$}
\put(760,794){\scriptsize $1$}
%********************************
\put(662,737){\line(1,0){75}}
\put(693,737){\vector(-1,0){0}}
\put(662,751){\line(1,0){75}}
\put(706.8,751){\vector(1,0){0}}
\put(697,720){\scriptsize $0$}
\put(697,757){\scriptsize $0$}
%********************************
\put(612,825){\line(3,-5){40}}    
\put(637,785){\vector(1,-1){0}}   
\put(600,816){\line(3,-5){37}}     
\put(615,791){\vector(-1,1){0}}    
\put(638,794){\scriptsize $1$}
\put(610,770){\scriptsize $1$}
%********************************
%********************************
\put(612,575){\line(3,5){40}}
\put(626,600){\vector(-1,-1){0}}
\put(600,584){\line(3,5){38}}
\put(624,620){\vector(1,1){0}}
\put(638,600){\scriptsize $1$}
\put(610,620){\scriptsize $1$}
%********************************
\put(662,649){\line(1,0){75}}
\put(693,649){\vector(-1,0){0}}
\put(662,663){\line(1,0){75}}
\put(706.8,663){\vector(1,0){0}}
\put(697,632){\scriptsize $0$}
\put(697,669){\scriptsize $0$}
%********************************
\put(762,651){\line(3,-5){40}}    
\put(787,611){\vector(1,-1){0}}   
\put(750,642){\line(3,-5){37}}     
\put(765,617){\vector(-1,1){0}}    
\put(788,620){\scriptsize $1$}
\put(760,596){\scriptsize $1$}
%********************************
\put(762,489){\line(3,5){40}}
\put(776,514){\vector(-1,-1){0}}
\put(750,498){\line(3,5){38}}
\put(774,534){\vector(1,1){0}}
\put(788,514){\scriptsize $0$}
\put(760,534){\scriptsize $0$}
%********************************
\put(662,477){\line(1,0){75}}
\put(693,477){\vector(-1,0){0}}
\put(662,491){\line(1,0){75}}
\put(706.8,491){\vector(1,0){0}}
\put(697,460){\scriptsize $1$}
\put(697,497){\scriptsize $1$}
%********************************
\put(612,565){\line(3,-5){40}}    
\put(637,525){\vector(1,-1){0}}   
\put(600,556){\line(3,-5){37}}     
\put(615,531){\vector(-1,1){0}}
\put(638,534){\scriptsize $0$}    
\put(610,510){\scriptsize $0$}
%********************************
%********************************
\put(224,700){\line(3,-1){365}}
\put(224,700){\vector(3,-1){188}}
\put(400,624){\scriptsize $1$}
%********************************
\put(180,380){(The - significant - states 
have been replaced by their images
by $\varphi$)}
\end{picture}
\caption{An automaton which generates the Hanoi 
sequence}
\end{figure}

\bigskip


\subsection{Sequences generated by uniform morphisms}

\begin{definition} 

A sequence $u = (u_n)_{n \geq 0}$ with values in a finite set $Y$ is
said to be the image of a fixed point of a uniform morphism of length
$q$, ($q$ being an integer $\geq 2$), if there
exists:

- a set $A$,

- a uniform morphism $\sigma$ of length $q$ on $A$, i. e. a map which 
associates to each letter in $A$ a $q$-letter word on $A$. This map is 
extended by concatenation to a morphism of the free monoid $A^*$ 
generated by $A$, and by continuity to the infinite sequences with
values in $A$,

- a sequence $v = (v_n)_{n \geq 0}$ with values in $A$, which is a fixed
point of $\sigma$,

- a map $\psi$ from $A$ to $Y$ such that $\forall n \in \,  $\mbox{\em \GN, }
$\psi(v_n) = u_n$.

\end{definition}

\bigskip

\subsection{Examples}

The patient reader can check (or prove) that the five examples given
previously are images of fixed points of uniform morphisms of length
$2$, indeed:

\bigskip

\noindent 1) The Prouhet-Thue-Morse sequence

\medskip

This sequence is the fixed point of the $2$-morphism on $\{0, 1\}$ 
given by:
$$\begin{array}{lll}
\sigma(0) & = & 01, \\
\sigma(1) & = & 10.
\end{array}
$$

\bigskip

\noindent 2) The Rudin-Shapiro sequence

\medskip

Let $A = \{a, b, c, d \}$, define $\sigma$ on $A$ by:
$$
\begin{array}{lll}
\sigma (a) & = & ab, \\ 
\sigma (b) & = & ac, \\
\sigma (c) & = & db, \\
\sigma (d) & = & dc,
\end{array}
$$
and let $\psi$ be the map:
$$\psi(a) = \psi(b) = +1, \, \psi(c) = \psi(d) = -1.$$
Then the sequence $v = (v_n)_{n \geq 0}$ defined by 
$v = \lim_{k \rightarrow \infty} \sigma^k(a)$ is a fixed point of 
$\sigma$, and the Rudin-Shapiro sequence is the pointwise image of
the sequence $v$ by the map $\psi$.

\newpage

\noindent 3) The paperfolding sequence

\medskip

Let $A = \{a, b, c, d \}$, define $\sigma$ on $A$ by:
$$\begin{array}{lll}
\sigma (a) & = & ab, \\
\sigma (b) & = & cb, \\
\sigma (c) & = & ad, \\
\sigma (d) & = & cd,
\end{array}
$$
and let $\psi$ be the map:
$$\psi(a) = \psi(b) = \mbox{\rm V}, \, \psi(c) = \psi(d) = 
\Lambda.$$
Then the sequence $v = (v_n)_{n \geq 0}$ defined by 
$v = \lim_{k \rightarrow \infty} \sigma^k(a)$ is a fixed point of 
$\sigma$, and the paperfolding sequence is the pointwise image of
the sequence $v$ by the map $\psi$.

\bigskip

\noindent 4) The Baum-Sweet sequence

\medskip

Let $A = \{a, b, c, d \}$, define $\sigma$ on $A$ by:
$$\begin{array}{lll}
\sigma (a) & = & ab, \\
\sigma (b) & = & cb, \\
\sigma (c) & = & bd, \\
\sigma (d) & = & dd,
\end{array}
$$
and let $\psi$ be the map:
$$\psi(a) = \psi(b) = 1, \, \psi(c) = \psi(d) = 0.$$
Then the sequence $v = (v_n)_{n \geq 0}$ defined by 
$v = \lim_{k \rightarrow \infty} \sigma^k(a)$ is a fixed point of 
$\sigma$, and the Baum-Sweet sequence is the pointwise image of
the sequence $v$ by the map $\psi$.

\bigskip

\noindent 5) The Hanoi sequence

\medskip

This sequence is the fixed point of the $2$-morphism $\sigma$
defined on the alphabet $A = \{a, b, c, \overline{a}, \overline{b},
\overline{c}\}$ by:

$$\begin{array}{lll}
\sigma(a) & = & a \overline{c}, \\
\sigma(b) & = & c \overline{b}, \\
\sigma(c) & = & b \overline{a}, \\
\sigma(\overline{a}) & = & a c, \\
\sigma(\overline{b}) & = & c b, \\
\sigma(\overline{c}) & = & b a.
\end{array}
$$

\bigskip

\subsection{The main theorem}

It is not by chance that our five examples are simultaneously 
$2$-automatic and images of fixed points of uniform morphisms of
length $2$. Indeed a theorem due to Cobham, \cite{Cobham1}, asserts
that this is general:

\begin{theorem} {\em (\cite{Cobham1})}. A sequence is 
$q$-automatic if and only if it is the image of a fixed point 
of a $q$-substitution.
\end{theorem}

\bigskip

The proof of this theorem uses a combinatorial property of these
sequences: both properties above are equivalent to saying that the 
set of subsequences $N_q(u)$ defined by:
$$N_q(u) = \left \{ n \rightarrow u_{q^k n + a}, \, k \geq 0, \,
0 \leq a \leq q^k-1J\right \},$$
(also called the $q$-kernel of the sequence $u$, see \cite{Salon2}),
is finite.

\bigskip

Christol, Kamae, Mend\`es France and Rauzy, gave in 1980, \cite{CKMFR}, 
an arithmetical condition which is equivalent
to the theo\-re\-tical-com\-pu\-ter-science condition and to the 
combinatorial condition given above:

\begin{theorem} {\em (\cite{CKMFR})}. Let $u$ be a sequence 
with values in the finite field {\em \GF}$_q$, ($q$ is a power of a prime 
number $p$). Then the sequence $u$ is $q$-automatic if and only if 
the formal power series $\sum_{n = 0}^{+ \infty} u_n X^n$ is 
algebraic over the field {\em \GF}$_q(X)$ of rational functions with 
coefficients in {\em \GF}$_q$.
\end{theorem}

\bigskip

\noindent {\bf Remarks}

\medskip

- this theorem has, of course, nothing to do with the 
Chomsky-Sch\"utzen\-berger theorem, (\cite{Chomsky});
\medskip

- to give the flavour of this theorem, let us consider again the 
Prouhet-Thue-Morse sequence quoted above. Remember that this sequence 
is the fixed point of the $2$-morphism $\sigma$ defined by:
$$\begin{array}{lll}
\sigma(0) & = & 01, \\
\sigma(1) & = & 10.
\end{array}
$$
We consider from now on $0$ and $1$ as the two elements of \GF$_2$ and
we make all computations modulo $2$. The definition of our sequence $u$
by the morphism $\sigma$ shows that:
$$\forall n \in \GN, \, u_{2n} = u_n, \, u_{2n+1} = 1+u_n.$$
Hence:
\begin{eqnarray*}
F(X) & := & \sum_{n = 0}^{+ \infty}u_nX^n = \sum_{n = 0}^{+ \infty}
u_{2n}X^{2n} + \sum_{n = 0}^{+ \infty} u_{2n+1}X^{2n+1} \\
&\, = & \sum_{n = 0}^{+ \infty}
u_nX^{2n} + \sum_{n = 0}^{+ \infty} (1+u_{n})X^{2n+1} \\
&\, = & (\sum_{n = 0}^{+ \infty}
u_nX^n)^2 + X(\sum_{n = 0}^{+ \infty} u_{n}X^n)^2 + \frac{X}
{(1+X)^2} \\
&\, = & F^2(X) + XF^2(X) + \frac{X}{(1+X)^2}.
\end{eqnarray*}

One sees that $F$ satisfies the equation:
$$(1+X)^3F^2 + (1+X)^2F + X = 0,$$
which shows that $F$ is algebraic (quadratic) on $\GF_2(X)$.

\bigskip

Another condition can be given for the automaticity of a sequence 
with values in a finite field. This is a theorem of Furstenberg's, 
which he proved in 1967, \cite{Furstenberg}:

\begin{theorem} {\em \cite{Furstenberg}.} 
Let $u = (u_n)_{n \geq 0}$ be a sequence with values in the finite 
field {\em \GF}$_q$. Then the series $\sum u_n X^n$ is algebraic over the 
field {\em \GF}$_q(X)$ if and only if there exists a double formal power 
series $\sum_{m, n \geq 0} a_{m, n} X^m Y^n$ such that

- this series is a rational function, i. e. belongs to the field
{\em \GF}$_q(X, Y)$,

- the sequence $u$ is the diagonal of the sequence $a$, i. e. :
$\forall n \in \,$ {\em \GN}, $u_n = a_{n,n}$.

\end{theorem}

Putting all these conditions together one obtains the following 
fundamental theorem:

\bigskip

\noindent {\bf Fundamental Theorem} {\em Let $u = (u_n)_{n \geq 0}$ be 
a sequence with values in the finite field {\em \GF}$_q$. Then the following 
conditions are equivalent:

i) the $q$-kernel of the sequence $u$, i. e. the set of subsequences
$$N_q(u) = \left \{ n \rightarrow u_{q^k n + a}, \, k \geq 0, \,
0 \leq a \leq q^k-1J\right \},$$ 
is finite,

ii) the sequence $u$ is $q$-automatic,

iii) the sequence $u$ is the image of a fixed point of a uniform 
morphism of length $q$,

iv) the formal power series $\sum_{n=0}^{+ \infty} u_n X^n$ is
algebraic over the field {\em \GF}$_q(X)$,

v) there exists a double sequence $a = (a_{m, n})_{m,n}$ with values in 
{\em \GF}$_q$ such that the formal power series 
$\sum_{m, n \geq 0} a_{m, n} X^m Y^n$
is a rational function, (i. e. an element of {\em \GF}$_q(X,Y)$), and such
that $u$ is the diagonal of $a$, (i. e. $\forall n \in \,${\em \GN}, 
$u_n = a_{n, n}$)}.

\bigskip

\section{Transcendence results and finite automata}

In this chapter we will see two kinds of transcendence results: 

- transcendence over $\GF_q(X)$ of formal power series with 
coefficients in $\GF_q$, using the Christol, Kamae, Mend\`es France and
Rauzy theorem. In particular we will devote a paragraph to the Carlitz
zeta function.

- transcendence of real numbers over the rational numbers.

\subsection{Miscellaneous transcendental formal power series}

- An old question of Mahler's asks whether a binary sequence
$(a_n)_n$ such that both numbers $\sum_{n=0}^{+ \infty} a_n 2^{-n}$ 
and $\sum_{n=0}^{+ \infty} a_n 3^{-n}$ are algebraic over the 
rational numbers is necessary an ultimately periodic sequence, 
(i. e. whether both numbers are ``trivial", indeed whether they are 
both rational). Actually, although this question is still open, the 
result is true if one replaces the usual operations by operations 
without carries:

\begin{theorem} Let $(a_n)_n$ be a binary sequence such that the formal
power series $\sum_{n=0}^{+ \infty} a_n X^n$ is algebraic over
{\em \GF}$_2(X)$ when considered as an element of {\em \GF}$_2[[X]]$, and algebraic
over {\em \GF}$_3(X)$ when considered as an element of {\em \GF}$_3[[X]]$. Then 
this sequence  is ultimately periodic, i. e. both formal power series
are indeed rational functions.
\end{theorem}

The proof of this result is an easy consequence of the theorem of 
Christol, Kamae, Mend\`es France and Rauzy and of a (non-easy!) result
of Cobham which asserts that a sequence which is both $q$-automatic
and $q'$-automatic, with $q$ and $q'$ multiplicatively independent,
is necessary ultimately periodic, (\cite{Cobham2}).

\bigskip

\noindent - Let $s_q(n)$ be the residue modulo $q$ of the sum of the digits of 
the integer $n$ in its $q$-ary expansion. It is not hard to see that
the sequence $(s_q(an+b))_n$ is $q$-automatic; in particular for
$q = 2$, $a=1$, $b=0$, one gets the Prouhet-Thue-Morse sequence.
But what can be said of $(s_q(n^2))$? A result of the author 
(\cite{Allouchesomme}), states that this sequence is NOT $q$-automatic.

\begin{theorem} {\em \cite{Allouchesomme}.} Let $P$ be a 
polynomial of degree $\geq 2$, such that $P(${\em \GN}$) \subset \,${\em \GN}. 
Then the sequence $(s_q(P(n))_n$ is not $q$-automatic.
Hence, if $q$ is a prime number, the formal power series
$\sum s_q(P(n)) X^n$ is transcendental over {\em \GF}$_q(X)$.

\end{theorem}


\noindent - As seen previously, the paperfolding sequence is $2$-automatic, hence
the paperfolding series is algebraic over $\GF_2(X)$. Now suppose that
at each step you choose to fold either up or down arbitrarily; you 
thus obtain an uncountable number of paperfolding sequences. Of course 
they cannot be all automatic, as the set of automatic sequences is
countable. It can be shown that such a sequence is $2$-automatic if 
and only if the sequence of its ``folding instructions" 
(i. e. the sequence of choices to fold one way or the other way) is 
ultimately periodic: in other words any non-ultimately periodic 
sequence of folding instructions yields a formal power series which is 
transcendental over $\GF_2(X)$. 

\subsection{The Carlitz zeta function}

In 1935 Carlitz introduced a function now known as the Carlitz zeta
function which ressembles the Riemann zeta function (see for instance
\cite{Carlitz}). This function from $\GN^*$ to $\GF_q[[X^{-1}]]$ is 
defined by:
$$\forall n \in \GN^*, \, \zeta(n) = \sum_{P 
\mbox{ \rm\scriptsize monic }\in \, 
\mbox{\scriptsize \GF}_q[X]} \frac{1}{P^n}.$$
Moreover there exists a formal Laurent series denoted by $\Pi$ such 
that:
$$\forall n \equiv 0 \bmod{(q-1)}, \, n \neq 0, \, \exists r_n \in \GF_q(X), \, 
\zeta(n) = \Pi^n r_n.$$
The expression for $\Pi$ is:
$$\Pi = \prod_{j=1}^{+ \infty} \left ( 1 - 
\frac{X^{q^j}-X}{X^{q^{j+1}}-X} \right ).$$
Note that this property can be compared to the classical result on 
the values of the Riemann zeta function at the even integers. 

\medskip

One can ask whether this formal Laurent series $\Pi$, the values of 
this zeta function, and the values $\frac{\zeta(n)}{\Pi^n}$ are 
transcendental over $\GF_q(X)$. Remember that the real number $\pi$
is transcendental over the field of rational numbers, hence the values
of the Riemann zeta function at the even integers are also 
transcendental, as the numbers $\zeta(2n)/\pi^{2n}$ are rational.
For the other values of the Riemann zeta function, 
(divided by a suitable power of $\pi$ or not), the only thing which is 
known is the irrationality of $\zeta(3)$ proved by Ap\'ery in 1978.

Four methods are available for the Carlitz zeta function and the
related series:

- the original method due to Wade in the 40's, 
(he proved many transcendence results, in particular
{\em the transcendence of the formal power series $\Pi$}), ressembles 
transcendence methods for the case of real numbers. This method has 
been extended recently by Dammame and Hellegouarch, who proved
the {\em transcendence of all the values $\zeta(n)$, $\forall n \in$ 
{\em \GN}$^*$};

- the method of diophantine approximation is worked out by de Mathan
and Ch\'erif and gives {\em irrationality measures for the values of 
the Carlitz zeta function};

- the method of Yu uses Drinfeld modules and gives the most complete 
results, indeed {\em $\zeta(n)$ is transcendental $\forall n \in $
{\em \GN}$^*$ and $\frac{\zeta(n)}{\Pi^n}$ is transcendental for every 
$n \not\equiv 0 \bmod{(q-1)}$};

- the ``automatic method".
This method has been proposed by the author to give {\em an  
``elementary" proof of the transcendence of the formal series $\Pi$},
(see \cite{AllouchePi}). The reader will find in the appendix a 
different (but even simpler) proof of the transcendence of this
series $\Pi$. This ``automatic" method has been recently extended
by Berth\'e: she gave an elementary automatic proof of {\em the 
transcendence of $\zeta(n)$, $\forall n \leq q-2$}, 
(see \cite{Berthe1}), as well as {\em linear independence results for 
these series}, (\cite{Berthe2}), and {\em transcendence results for the
Carlitz logarithm}, (see \cite{Berthe3}).

\subsection{Transcendence of real numbers and finite automata}

The consequence of Cobham's theorem quoted above (Theorem 4) can be 
described, roughly speaking, by saying: 
{\em ``changing bases kills algebraicity"}.
Hence a natural question posed in \cite{CKMFR} asks whether every 
real number $\sum a_n 2^{-n}$ such that the sequence of coefficients 
in its base-2 expansion is $2$-automatic and not ultimately periodic
is indeed a transcendental number.
The answer is yes, it is due to Loxton and van der Poorten, 
(see also the work of Nishioka):
\begin{theorem} {\em \cite{LoxtonvdP}}. 
If the coefficients of the base-$q$ expansion of a real number form
an automatic sequence, then this number is either rational or
transcendental.
\end{theorem}

In other words a number like $\sqrt 2$ cannot have an automatic 
expansion in any base. Note that this theorem gives the transcendence 
of a countable set of ``ad hoc" real numbers, and that one should not
hope to get that way the transcendence of classical numbers like
the Euler constant (!), even for numbers which are known to be 
transcendental: a reasonable but out of reach conjecture is that
the real numbers $\pi$ and $e$ are not automatic. Note also that
Mend\`es France and van der Poorten proved that a real number
whose base-2 expansion is any paperfolding sequence is transcendental,
(see \cite{MendesvdP}), this gives an uncountable (but ``thin") set
of numbers, (which of course are not all automatic numbers), for which 
the transcendence can be proved using this kind of methods.

\section{Generalizations}

In this chapter we will survey quickly some possible generalizations 
of the automatic sequences. The interested reader can find a survey
with more details in \cite{AlloucheLNCS}, in particular what is kept 
and what is lost in each of these generalizations.

\subsection{The multidimensional case}

Instead of considering one-dimensional morphisms which consist of 
replacing a letter by a word, one can imagine of a multidimensional
morphism. Thus a two-dimensional morphism associates to
each letter a ``square", for instance:
$$ 0 \rightarrow 
\begin{array}{ll}
0 & 1 \\
1 & 0 
\end{array}, \quad 1 \rightarrow 
\begin{array}{ll}
1 & 0 \\
0 & 1 
\end{array}.
$$
This can be extended as previously, iterating this map gives:
$$0 \rightarrow
\begin{array}{ll}
0 & 1 \\
1 & 0
\end{array}
\rightarrow
\begin{array}{llll}
0 & 1 & 1 & 0  \\
1 & 0 & 0 & 1  \\
1 & 0 & 0 & 1  \\
0 & 1 & 1 & 0 
\end{array}
\rightarrow
\cdots
$$
The reader can find in \cite{Salon1} and \cite{Salon2} more details,
in particular a theorem analogous to the Christol, Kamae, Mend\`es
France and Rauzy theorem holds true. 

\subsection{Non-uniform morphisms}

A non-uniform morphism maps each letter of a finite alphabet on a
word with letters in this alphabet, but all these words do not have
necessarily the same length. A classical example is the Fibonacci
morphism defined on $\{0, 1\}$ by:
$$0 \rightarrow 01, \, \, 1 \rightarrow 0.$$
Iterating this morphism gives:
$$0 \rightarrow 01 \rightarrow 010 \rightarrow 01001 \rightarrow 
01001010 \rightarrow \cdots$$ 
The arithmetic properties of the infinite sequences which are 
(images of) fixed points of these morphisms are not very simple 
as the numeration base associated to them is not the base $q$ for 
some integer $q \geq 2$.
For instance, in the above example, the numeration base is the 
Fibonacci base: $F_0 = 1$, $F_1=2$, $F_2=3$, $F_3=5$, $\cdots$

On this subject one can read the paper of Shallit (\cite{Shallit}), 
and also the work of Fabre. 

\subsection{From finite fields to fields of positive characteristic}

Remember that the theorem of Christol, Kamae, Mend\`es France and Rauzy
can be stated in the following way, (see theorem 2):

\medskip

{\em Let $q$ be an integer $\geq 2$. For a sequence $u=(u_n)_n$ define 
its $q$-kernel as the set of subsequences
$$N_q(u) = \left \{ n \rightarrow u_{q^k n + a}, \, k \geq 0, \,
0 \leq a \leq q^k-1 \right \}.$$
Suppose that $u$ takes its values in the finite field {\em \GF}$_q$. Then 
the series $\sum u_n X^n$ is algebraic over {\em \GF}$_q(X)$ if and only if 
its $q$-kernel $N_q(u)$ is finite}.

\medskip

\noindent The main result obtained by Sharif and Woodcock in
\cite{SharifWoodcock} and Harase in \cite{Harase} (see also the survey
of the author \cite{AlloucheSW}), can be stated as follows:

\begin{theorem} {\em \cite{SharifWoodcock}, \cite{Harase}}. 
Let $u$ be a sequence with values in a field $K$ of positive 
characteristic $p$. Let $s$ be any integer $\geq 1$, $q=p^s$, and 
let $\overline{K}$ be a perfect field containing $K$, 
(for instance its algebraic closure).

Then the series $\sum u_n X^n$ is algebraic over $K(X)$ if and 
only if the vector space spanned over $\overline{K}$ by the
``modified" $q$-kernel of $u$
$$N_q'(u) = \left \{ n \rightarrow u_{q^k n + a}^{1/q^k}, \, 
k \geq 0, \, 0 \leq a \leq q^k-1J\right \}.$$
has finite dimension.
\end{theorem}

Note that this theorem contains the Christol, Kamae, Mend\`es France 
and Rauzy theorem, and that it can be easily extended to the 
multidimensional case. Note also that two interesting corollaries
can been proved, using the work of Salon for a finite field, or more
generally the above theorem for a field of positive characteristic, 
(these results have been first given by Deligne by a non-elementary
method in \cite{Deligne}):

\medskip

- {\em the Hadamard product of two algebraic formal power series 
with coefficients in a field of positive characteristic,
$\sum u_n X^n$ and $\sum v_n X^n$, i. e. the ``naive" product
$\sum u_n v_n X^n$, is itself an algebraic formal power series}.

\medskip

- {\em let $\sum u_{m,n}X^m Y^n$ be a double formal power series 
in $K[[X,Y]]$, algebraic over $K(X,Y)$, (where $K$ is a field of
positive characteristic). Then its diagonal
$\sum u_{n,n}X^n$ is algebraic over the field $K(X)$}.

\subsection{$q$-regular sequences}

Let $s(n)$ be the sum of the digits of $n$ in the binary
expansion, then the sequence $(s(n))_n \bmod 2$ is the 
Prouhet-Thue-Morse sequence, hence is a $2$-automatic sequence. 
What can be said of the sequence $(s(n))_n$ not reduced modulo $2$?

The notion of $q$-regular sequence has been introduced by Shallit and
the author in \cite{AlloucheShallit} to answer this question {\em  
inter alia}.

\medskip

{\em Let $q$ be an integer $\geq 2$. Let $u=(u_n)_n$ be a sequence with
values in a N{\oe}therian ring $R$. This sequence is said to be
$q$-regular  if its kernel $N_q(u)$ generates a module of finite type}.

\noindent (Remember that the $q$-kernel of the sequence $u$ is defined 
as: $N_q(u) = \left \{ n \rightarrow u_{q^k n + a}, \, k \geq 0, \,
0 \leq a \leq q^k-1J\right \}$). 

\medskip

The reader is referred to \cite{AlloucheShallit} for the properties of
these sequences and for numerous examples of such sequences, together
with ``their Sloane numbers" for the sequences which are quoted in 
Sloane's book \cite{Sloane}.

\section{Appendix: an easy ``automatic" proof of the transcendence of
the formal power series $\Pi$}

As said in chapter 3.2 the Carlitz formal power series $\Pi$, given by
$$\Pi = \prod_{j=1}^{+ \infty} \left ( 1 - 
\frac{X^{q^j}-X}{X^{q^{j+1}}-X} \right ).$$
has been proved transcendental by Wade in the 40's. We gave an
``automatic" proof of this result in \cite{AllouchePi}. We want to 
present now another - still simpler - ``automatic" proof.

\medskip

The first step consists of a remark due to Laurent Denis concerning an
expression for $\frac{\Pi'}{\Pi}$. Indeed taking the derivative of the 
expression of $\Pi \in \GF_q((X^{-1}))$, one has:
$$\frac{\Pi'}{\Pi} = \sum_{j=1}^{+ \infty} \frac{
\left ( 1 - 
\frac{X^{q^j}-X}{X^{q^{j+1}}-X} \right )'}{
\left ( 1 - 
\frac{X^{q^j}-X}{X^{q^{j+1}}-X} \right )} =
\sum_{j=1}^{+ \infty} \frac{1}{X^{q^{j+1}}-X}.$$
A traditional notation is $[j] = X^{q^j}-X$, hence the above equality 
can be written  
$$\frac{\Pi'}{\Pi} = \sum_{j=1}^{+ \infty} \frac{1}{[j+1]}.$$
If $\Pi$ were algebraic, that would be the case also for $\Pi'$, (the
proof is left to the reader who might use - for instance - the Christol,
Kamae, Mend\`es France an Rauzy theorem, where the variable $X$ is
replaced by $X^{-1}$), hence for $\frac{\Pi'}{\Pi}$.

Finally to prove the transcendence of $\Pi$ it suffices to prove the
transcendence of the series $\sum_{j=1}^{+ \infty} \frac{1}{[j]}$. 
This series is known as the ``bracket" series and has been proved
transcendental by Wade, but we gave in \cite{AllouchePi} an
``automatic" proof for the transcendence of slightly more general 
series. We rewrite here this - easy - proof in the case of the bracket
series. One has:
$$\sum_{j=1}^{+ \infty} \frac{1}{[j]} = 
\sum_{j=1}^{+ \infty} \frac{1}{X^{q^{j}}-X} =
\sum_{j=1}^{+ \infty} \frac{1}{X^{q^j}} \left ( 1 - \left (
\frac{1}{X} \right )^{q^j -1} \right )^{-1}$$
$$ = \sum_{\stackrel{{\scriptstyle j \geq 1}}{m \geq 0}} 
\left ( \frac{1}{X} \right )^{q^j+m(q^j-1)}
= \frac{1}{X} \sum_{\stackrel{{\scriptstyle j \geq 1}}
{m \geq 1}} \left ( \frac{1}{X} \right )^{m(q^j-1)} 
= \frac{1}{X} \sum_{n \geq 1} \left ( 
\sum_{\stackrel{{\scriptstyle j, m}}
{m(q^j-1) = n}} 1 \right ) \frac{1}{X^n}.$$
This last expression can also be written
$$\frac{1}{X} \sum_{n \geq 1} \left ( 
\sum_{\stackrel{{\scriptstyle j}}
{(q^j-1) \mid n}} 1 \right ) \frac{1}{X^n}.$$
Using the theorem of Christol, Kamae, Mend\`es France and Rauzy one
sees that the series above is algebraic over $\GF_q(X)$ if and
only if the sequence
$$ 
n \rightarrow  \sum_{\stackrel{{\scriptstyle j}} {(q^j-1) \mid n}} 1
$$
is $q$-automatic. So we have to prove that it is not.

But if a sequence $v$ is $q$-automatic, then the subsequence
$n \rightarrow v_{q^n-1}$ is ultimately periodic, (hint:
the base-$q$ expansion of $q^n - 1$ consists of $n$ digits all equal
to $q-1$). It thus suffices to show that the sequence:
$$n \rightarrow  \sum_{\stackrel{{\scriptstyle j}}
{(q^j-1) \mid (q^n-1)}} 1 $$
is not ultimately periodic. But it is well known that 
$(q^j-1) \mid (q^n-1)$ if and only if $j \mid n$. Hence, using the 
classical notation $\tau(n)$ to denote the number of divisors of
the integer $n$, it suffices to show that the sequence
$$n \rightarrow \tau(n)$$
is not ultimately periodic.
OF COURSE THIS SEQUENCE HAS TO BE TAKEN modulo $p$, where $p$ is the
characteristic of $\GF_q$.

\medskip

Now, suppose that $(\tau(n))_n \bmod p$ is ultimately periodic. Then
there exist two integers $T \geq 1$ and $n_0 \geq 1$ such that:
$$\forall n \geq n_0, \, \forall k \in \GN, \,
\tau(n+kT) \equiv \tau(n) \bmod p.$$
This implies
$$\forall n \geq n_0, \, \forall k \in \GN, \,
\tau(n(1+kT)) = \tau(n+knT) \equiv \tau(n) \bmod p.$$
Now choose $k$ large enough such that $(1+kT) \geq n_0$ and 
$(1+kT)$ is a prime number, say $\overline{\omega}$: this is possible
from the arithmetic progression theorem for prime numbers, (note that
this case, i. e. the existence of arbitrarily large prime numbers in 
the progression $1+kT$, can be proved in a very elementary way, using 
cyclotomic polynomials). Taking $n = (1+kT) = \overline{\omega}$,
one gets:
$$\tau(\overline{\omega}^2) \equiv \tau(\overline{\omega}) \bmod p,$$
i. e. 
$$3 \equiv 2 \bmod p,$$
which yields the desired contradiction.


\bigskip

\begin{thebibliography}{99}
\bibitem{Allouchesomme} J.-P. Allouche, {\em Somme des chiffres et
transcendance}, Bull. Soc. math. France, {\bf 110} (1982), 279--285.
\bibitem{Alloucheexpo} J.-P. Allouche, {\em Automates finis en th\'eorie
des nombres}, Expo. Math., {\bf 5} (1987), 239--266.
\bibitem{Allouchefc} J.-P. Allouche, {\em Sur le d\'eveloppement en
fraction continue de certaines s\'eries formelles}, C. R. Acad. Sci.
Paris, S\'erie I, {\bf 307} (1988), 631--633.
\bibitem{AlloucheSW} J.-P. Allouche, {\em Note sur un article de
Sharif et Woodcock}, S\'eminaire de Th\'eorie des Nombres de Bordeaux,
S\'erie II, {\bf 1} (1989), 163--187.
\bibitem{AllouchePi} J.-P. Allouche, {\em Sur la transcendance de la 
s\'erie formelle $\Pi$}, S\'eminaire de Th\'eorie des Nombres de 
Bordeaux, S\'erie II, {\bf 2} (1990), 103--117.
\bibitem{Allouchephys} J.-P. Allouche, {\em Finite automata in 
$1$-dimensional and $2$-dimensional physics}, Number theory and physics,
J.-M. Luck, P. Moussa, M. Waldschmidt (Eds.), Proceedings in Physics,
Springer, {\bf 47} (1990), 177--184. 
\bibitem{AlloucheLNCS} J.-P. Allouche, {\em $q$-regular sequences and 
other generalizations of $q$-automatic sequences}, Lecture Notes in
Computer Science, {\bf 583} (1992), 15--23.
\bibitem{AlloucheHanoicyclique} J.-P. Allouche, {\em Note on the cyclic
towers of Hanoi}, Theoret. Comput. Sci., (to appear).
\bibitem{AlloucheBetremaShallit} J.-P. Allouche, J. B\'etr\'ema and
J. Shallit, {\em Sur des points fixes de morphismes d'un mono\"{\i}de
libre}, Inform. Th\'eor. Appl., {\bf 23} (1989), 235--249.
\bibitem{AlloucheDress} J.-P. Allouche and F. Dress, {\em Tours de 
Hano\"{\i} et automates}, Inform. Th\'eor. Appl., {\bf 24} 
(1990), 1--15.
\bibitem{AlloucheShallit} J.-P. Allouche and J. Shallit, {\em The ring
of $k$-regular sequences}, Theoret. Comput. Sci., {\bf 98} (1992),
163--197. 
\bibitem{BaumSweet} L. E. Baum and M. M. Sweet, {\em Continued fractions
of algebraic power series in characteristic $2$}, Ann. of Math.,
{\bf 103} (1976), 539--610.
\bibitem{Berthe1} V. Berth\'e, {\em De nouvelles preuves 
``automatiques" de transcendance pour la fonction z\'eta de Carlitz},
Journ\'ees arithm\'etiques de Gen\`eve, Ast\'erisque, {\bf 209}
(1992), 159--168.
\bibitem{Berthe2} V. Berth\'e, {\em Combinaisons lin\'eaires de 
$\frac{\zeta(s)}{\Pi^s}$ sur {\em \GF}$_q(x)$, pour $1 \leq s \leq (q-2)$}, 
submitted.
\bibitem{Berthe3} V. Berth\'e, {\em Automates et valeurs de 
transcendance du logarithme de Carlitz}, Acta Arithmetica, (to appear).
\bibitem{Carlitz} L. Carlitz, {\em On certain functions connected with 
polynomials in a Galois field}, Duke Math. J., {\bf 1} (1935), 137--168.
\bibitem{Chomsky} N. Chomsky and M. P. Sch\"utzenberger, {\em The
algebraic theory of context-free languages}, in Computer programming
and formal languages, 118--161, North Holland, Amsterdam, 1963.
\bibitem{CKMFR} G. Christol, T. Kamae, M. Mend\`es France, G. Rauzy,
{\em Suites alg\'e\-bri\-ques, automates et substitutions}, Bull. Soc. 
math. France, {\bf 108} (1980), 401--419.
\bibitem{Cobham1} A. Cobham, {\em Uniform tag sequences}, Math. Systems
Theory, {\bf 6} (1972), 164--192.
\bibitem{Cobham2} A. Cobham, {\em On the base-dependence of sets of
numbers recognizable by finite automata}, Math. Systems Theory,
{\bf 3} (1969), 186--192.
\bibitem{Davis} C. Davis and D. E. Knuth, {\em Number representations 
and dragon curves, I, II}, J. Recr. Math. {\bf 3} (1970), 161--181 and 
133--149.
\bibitem{Dekking} M. Dekking, M. Mend\`es France and A. van der Poorten,
{\em FOLDS!}, Math. Intell. {\bf 4} (1982), 130--138, 173--181 and 
190--195. 
\bibitem{Deligne} P. Deligne, {\em Int\'egration sur un cycle 
\'evanescent}, Invent. Math., {\bf 76} (1984), 129--143.
\bibitem{Eilenberg} S. Eilenberg,  {\em Automata, Languages and 
Machines}, vol. A, Acad. Press, New York, 1974.
\bibitem{Furstenberg} H. Furstenberg, {\em Algebraic functions over
finite fields}, J. Algebra, {\bf 7} (1967), 271--277.
\bibitem{Harase} T. Harase, {\em Algebraic elements in formal power 
series rings}, Israel J. Math., {\bf 63} (1988), 281--288.
\bibitem{LoxtonvdP} J. H. Loxton and A. J. van der Poorten, {\em
Arithmetic properties of automata: regular sequences}, J. Reine
Angew. Math., {\bf 392} (1988), 57--69.
\bibitem{MendesvdP} M. Mend\`es France and A. van der Poorten,
{\em Arithmetic and analytic properties of paperfolding sequences},
dedicated to K. Mahler, Bull. Austral. Math. Soc., {\bf 24} (1981),
123--131.
\bibitem{MillsRobbins} W. H. Mills and D. P. Robbins, {\em Continued
fractions for certain algebraic power series}, J. Number Theory,
{\bf 23} (1986), 388--404.
\bibitem{Mkaouar} M. Mkaouar, Th\`ese, Lyon, 1993.
\bibitem{Morse} M. Morse, {\em Recurrent geodesics on a surface of
negative curvature}, Trans. Amer. Math. Soc., {\bf 22} (1921), 84--100.
\bibitem{Prouhet}  E. Prouhet, Comptes-Rendus de l'Acad\'emie des
Sciences, Paris, {\bf 33} (1851), 225. 
\bibitem{Rudin} W. Rudin, {\em Some theorems on Fourier coefficients},
Proc. Amer. Math. Soc., {\bf 10} (1959), 855--859.
\bibitem{Salon1} O. Salon, {\em Suites automatiques \`a multi-indices 
et alg\'ebricit\'e}, C. R. Acad. Sci. Paris, S\'erie I, {\bf 305} 
(1987), 501--504.
\bibitem{Salon2} O. Salon, {\em Suites automatiques \`a multi-indices}, 
S\'eminaire de Th\'eorie des Nombres de Bordeaux, Expos\'e 4, 
1986--1987.
\bibitem{Shallit} J. Shallit, {\em A generalization of automatic
sequences}, Theoret. Comput. Sci., {\bf 61} (1988), 1--16.
\bibitem{Shapiro} H. S. Shapiro, {\em Extremal problems for polynomial
and power series}, Thesis, M.I.T., 1951.
\bibitem{SharifWoodcock} H. Sharif and C. F. Woodcock, {\em Algebraic
functions over a field of positive characteristic and Hadamard
products}, J. Lond. Math. Soc., {\bf 37} (1988), 395--403.
\bibitem{Sloane} N. J. A. Sloane, {\em A Handbook of Integer Sequences},
Academic Press, New York, 1973.
\bibitem{Thue1} A. Thue, {\em \"Uber unendliche Zeichenreihen}, Norske
vid. Selsk. Skr. I. Mat. Kl. Christiana, {\bf 7} (1906), 1--22.
\bibitem{Thue2} A. Thue, {\em Lage gleicher Teile gewisse 
Zeichenreihen}, Norske vid. Selsk. Skr. I. Mat. Kl. Christiana, {\bf 1}
(1912), 1--67.
\end{thebibliography}



\end{document}
