Talk (JeanPaul Allouche)
Automatic sequences in number theory, computer science, and physics
JeanPaul Allouche
http://www.math.jussieu.fr/~allouche
This talk will be centered on a class of sequences, coming (essentially) from theoretical
computer science, and having nice numbertheoretical 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≥0}, provides the
"ProuhetThueMorse" sequence
(t(n))_{n≥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≥0} is finite
K := {(t(n))_{n≥0},
(t(2n))_{n≥0},
(t(2n+1))_{n≥0},
(t(4n))_{n≥0},
(t(4n+1))_{n≥0},
(t(4n+2))_{n≥0},
(t(4n+3))_{n≥0},
... }
= {(t(2^{k}n+r))_{n≥0},
with k≥0 and 0≤r≤2^{k}1}
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
∑ t(n) X^{n} is algebraic
over the field of fractions in $X$ modulo 2.

Less easy is to prove that
the formal power series ∑ t(n) X^{n}
is transcendental over the field of fractions in $X$ modulo 3.

It was proved by Mahler, then by Dekking that the real number
∑ 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 numbertheoretic 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.
Four pictures related to the talk
Kolam (1)
Kolam (2)
Penrose tiling (1)
Penrose tiling (2)