# Automatic sequences and number theory

Jean-Paul Allouche
(CNRS, Université Pierre et Marie Curie)
Analyseseminar
Tirsdag, 2 oktober, 2012, at 15:15-16:15, in Aud. D1 (1531-113)
Abstrakt:

This talk will be centered on a class of sequences, coming (essentially) from theoretical computer science, and having nice number-theoretical properties. Our leading thread will be a classical automatic sequence defined as follows. Let $s_2(n)$ be the sum of the binary digits of the integer $n$. Looking at the parity sequence of the sequence ($s_2(n))_{n\geq0}$, provides the "Prouhet-Thue-Morse" sequence

$(t(n))_{n\geq 0} = 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 ...$

We first recall rapidly the history of this sequence, noting in passing the (easy) property that the following set $K$ of subsequences of the sequence $(t(n))_{n \geq0}$ is finite:

\begin{align*} K :={}& \{ (t(n))_{n\geq 0},\ (t(2n))_{n\geq 0},\ (t(2n+1))_{n\geq 0},\ (t(4n))_{n\geq 0},\ (t(4n+1))_{n\geq 0},\ (t(4n+2))_{n\geq 0},\ (t(4n+3))_{n\geq 0},\ ... \} \\ = {} & (t(2^kn+r))_{n\geq 0}, \qquad \text{with $k\geq 0$ and $0\leq r\leq 2^{k}-1$} \end{align*}

Our first question is: how much "algebraic" is the sequence $t$? Is "transcendence" synonym of "complexity"?

• It is not difficult to prove that the formal power series $\sum t(n)X^n$ is algebraic over the field of fractions modulo 2.
• Less easy is to prove that the formal power series $\sum t(n) X^n$ is transcendental over the field of fractions modulo 3.
• It was proved by Mahler, then by Dekking that the real number $\sum t(n)2^{-n}$ is transcendental over the rationals.
• It was proved by Queffélec that the continued fraction with partial quotients $(1+t(n))$, i.e., the continued fraction $[1 2 2 1 2 1 1 2 2 1 1 2 1 2 2 1 2 1 1 2 ...]$ is transcendental over the real numbers.

The talk will be a promenade amidst automatic sequences and their number-theoretic properties: transcendence(s), algebraic continued fractions with bounded partial quotients, Carlitz zeta function, etc. We will end up with other kinds of properties, from harmonic analysis to physics and to (theoretical) computer science, with a final allusion to music.

Kontaktperson: Simon Kristensen