Gunther Cornelissen: Solving equations using Turing machines
Time: Wed 2020-02-19 11.00
Lecturer: Gunther Cornelissen, Utrecht
Location: Kräftriket, house 5, room 31
It is relevant for various problems in group theory and algebraic geometry to construct explicit power series (with coefficients in a finite field) that are of finite order under composition. Only a handful of examples is known. We give a finite deterministic description of such series using automata (a kind of memoryless Turing machine), based on finding algebraic equation for such series and using a theorem of Christol. We then we study various complexity measures of the associated series (for example, what is the number of states, what is the density of non-vanishing coefficients?). Joint work with Jakub Byszewski (Krakow) and Djurre Tijsma (Dusseldorf).