Posted March 16, 2025
Mathematical Physics and Representation Theory Seminar
2:30 pm – 3:20 pm Lockett 233
Justin Lanier, University of Sydney
TBA
TBA
Posted March 31, 2025
Algebra and Number Theory Seminar Questions or comments?
2:30 pm – 3:30 pm Lockett 233 or click here to attend on Zoom
Be'eri Greenfeld , University of Washington
Complexity and Growth of Infinite Words and Algebraic Structures
Given an infinite word (for example, 01101001$\ldots$), its complexity function counts, for each n, the number of distinct subwords of length n. A longstanding open problem is the "inverse problem": Which functions $f:\mathbb N\to \mathbb N$ arise as complexity functions of infinite words? We resolve this problem asymptotically, showing that, apart from submultiplicativity and a classical obstruction found by Morse and Hedlund in 1938, there are essentially no further restrictions. We then explore parallels and contrasts with the theory of growth of algebras, drawing on noncommutative constructions associated with symbolic dynamical systems.