Talk (Jean-Paul Allouche)

Automatic sequences in number theory, computer science, and physics

Jean-Paul 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 number-theoretical properties. Our leading thread will be a classical automatic sequence defined as follows. Let s2(n) be the sum of the binary digits of the integer n. Looking at the parity sequence of the sequence (s2(n))n≥0, provides the "Prouhet-Thue-Morse" 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(2kn+r))n≥0, with k≥0 and 0≤r≤2k-1}

Our first question is: how much "algebraic" is the sequence t? Is "transcendence" synonym of "complexity"? 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.

Four pictures related to the talk

Kolam (1)

Kolam (2)

Penrose tiling (1)

Penrose tiling (2)