The Prouhet-Thue-Morse sequence is obtained by starting with the letter a and successively substituting a by ab and b by ba. In each iteration, the previous step is a prefix of the next, and so we get an infinite sequence of letters, which is a fixed point of the substitution. This sequence appears in many contexts, including number
theory, algebra, combinatorics, geometry, and symbolic dynamics. The purpose of this talk is to identify the patterns in two variables (both finite and infinite) that can be found in the Prouhet-Thue-Morse sequence. We also show that, in the finite case, most patterns can only be found in a trivial way, up to a finite number of exceptions that are identified. We also show that there are no other infinite patterns than the obvious ones.
(Joint work with O. Klíma.)