Differences

This shows you the differences between two versions of the page.

--- start [2025/04/08 19:11] – 139.124.146.3
+++ start [2025/04/22 14:24] (current) – 139.124.146.3
@@ Line 22: / Line 22: @@
 ==== Upcoming talks ====
-**April 22 2025: Be'eri Greenfeld**
 **May 6 2025: Jarkko Peltomäki**
@@ Line 40: / Line 38: @@
 ==== Past talks 2025 ====
+**April 22 2025: [[https://sites.google.com/view/beeri-greenfeld|Be'eri Greenfeld]]** //On the Complexity of Infinite Words//
+{{ seminar2025:20250422greenfeld.mp4 |video of the talk}}
+Given an infinite word $w$, its complexity function $p_w(n)$ counts the number of distinct subwords of length $n$ it contains. A longstanding open problem in the combinatorics of infinite words is the {\it inverse problem}: describe which functions $f: \mathbb N \to \mathbb N$ arise as complexity functions of infinite words. Such functions must be non-decreasing and, unless eventually constant, strictly increasing; they must also be submultiplicative, i.e., $f(n+m)≤f(n)f(m)$. Many interesting results, both positive and negative, have been obtained in this direction.
+We resolve this problem up to asymptotic equivalence in the sense of large-scale geometry. Specifically, given any increasing, submultiplicative function $f$, we construct an infinite recurrent word $w$ such that $c f(cn) ≤ p_w(n) ≤ d f(dn)$ for some constants $c,d>0$. For uniformly recurrent words, we obtain a weaker version allowing a linear error factor. Time permitting, we will discuss connections and applications of these results to asymptotic questions in algebra.
+Joint work with C. G. Moreira and E. Zelmanov.