Boris Adamczewski

Université Claude Bernard Lyon 1 - France

March 2011

• Distinguished Lecture Colloquium
• TUCS Short Course

Distinguished Lecture Colloquium

Automata in Number Theory

Among infinite sequences or infinite sets of integers, some have a rigid structure, such as periodic sequences or arithmetic progressions, whereas others, such as random sequences or random sets, are totally unordered and could not be described in a simple way. Finite automata are one of the most basic model of computation and thus take place at the bottom of the hierarchy associated with Turing machines. Such machines can naturally be used at once to generate sequences with values over a finite set, and as a device to recognize some sets of integers. One of the main interest of these automatic sequences/sets comes from the fact that they are highly ordered without necessarily being trivial. One can thus consider that they lie somewhere between order and chaos, even if, in most respects, they appear to have a rigid structure.

In this talk, I will survey some of the connections between automatic sequences/sets and number theory. Several substantial advances have recently been made in this area and I will try to give an overview of some of these new results. This will possibly includes discussions about prime numbers, the decimal expansion of algebraic numbers, and some Diophantine equations over fields of positive characteristic.

TUCS Short Course

Combinatorics on words, automata and number theory

Combinatorics on words is the study of the combinatorial properties of finite or infinite sequences with values in a finite or countable set. It constitutes a natural framework for interaction between various fields, including in particular algebra (group theory), dynamical systems (symbolic dynamics), theoretical computer science, tiling theory, discrete geometry, and of course number theory.

In number theory, finite or infinite words naturally occur via the use of numeration systems, that is, as soon as one aims at representing all elements of a given set (integers, real numbers, p-adic numbers, fields of Laurent series...) in a unified way. For instance, decimal expansions, binary expansions, and continued fraction expansions are all different ways of associating with every real number a unique finite or infinite word that corresponds to its sequence of digits.

A fundamental reoccurring theme in these lectures will be the use of infinite words and finite automata to study problems of a number theoretical flavor. Following the own taste of the speaker, these lectures aim at describing some interplay between numeration systems and number theory.

Lectures schedule:

• Repetition in infinite words, transcendence and Diophantine approximation (normal numbers, complexity, periods, Cobham's conjecture).
• Beyond transcendence: irrationality and transcendance measures for real numbers with sublinear complexity.
• Symmetric patterns and continued fractions. Examples for Littlewood's conjecture, existence of extremal numbers, transcendence.
• Zeros of linear recurrences, Christol's theorem and formal power series in positive characteristic.