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"?
• It is not difficult to prove that the formal power series ∑ t(n) Xn is algebraic over the field of fractions in \$X\$ modulo 2.
• Less easy is to prove that the formal power series ∑ t(n) Xn 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 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)