Differences

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

--- start [2025/02/11 20:11] – 139.124.146.3
+++ start [2025/04/22 14:24] (current) – 139.124.146.3
@@ Line 22: / Line 22: @@
 ==== Upcoming talks ====
-**February 25 2025: Bartek Pawlik**
+**May 6 2025: Jarkko Peltomäki**
+**May 20 2025: Pranjal Jain**
+**June 3 2025: Curtis Bright**
+**June 17 2025: [[https://sites.google.com/view/noysofferaranov/bio|Noy Soffer Aranov]]**
+**July 15 2025: [[https://apacz.matinf.uj.edu.pl/users/1719-elzbieta-krawczyk|Elżbieta Krawczyk]]**  //Quasi-fixed points of substitutions and substitutive systems//
+We study automatic sequences and automatic systems (symbolic dynamical systems) generated by general constant length (nonprimitive) substitutions. While an automatic system is typically uncountable, the set of automatic sequences is countable, implying that most sequences within an automatic system are not themselves automatic. We provide a complete classification of automatic sequences that lie in a given automatic system in terms of the so-called quasi-fixed points of the substitution defining the system. Quasi-fixed points have already appeared implicitly in a few places (e.g. in the  study of substitutivity of lexicographically minimal points in substitutive systems or in the study of subsystems of substitutive systems) and they have been described in detail by Shallit and Wang and, more recently, B\'eal, Perrin, and Restivo . We conjecture that a similar statement holds for general nonconstant length substitutions.
+==== 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.
+**April 8 2025: [[https://trios.tsukuba.ac.jp/en/researcher/0000003624|Hajime Kaneko]]** //Analogs of Markoff and Lagrange spectra on
+one-sided shift spaces//
+{{ seminar2025:20250408kaneko.pdf |slides}}
+{{ seminar2025:20250408kaneko.mp4 |video of the talk}}
+The Lagrange spectrum is related to the rational approximations of badly
+approximable numbers. The discrete part of the spectrum is denoted in terms
+of Christoffel words. A multiplicative analog of the Lagrange spectrum was
+recently investigated, which is defined by Diophantine approximations of geometric sequences and more general linear recurrences. Dubickas investigated
+the minimal limit points of certain multiplicative Markoff-Lagrange spectra in
+terms of symbolic dynamical systems and certain substitutions.
+In this talk, we study an analog of the Markoff-Lagrange spectrum for general
+one-sided shift spaces. As our main results, we determine the discrete parts and
+minimal limit points in terms of $S$-adic sequences, where $S$ is an infinite set of
+substitutions. This is joint work with Wolfgang Steiner.
+**March 25 2025: [[https://page.mi.fu-berlin.de/vbui/|Vuong Bui]]** //An explicit condition for boundedly supermultiplicative subshifts//
+{{ seminar2025:20250325bui.pdf |slides}}
+{{ seminar2025:20250325bui.mp4 |video of the talk}}
+We study some properties of the growth rate of  $L(A,F)$, that is, the language of words over the alphabet $A$ avoiding the set of forbidden factors $F$. We first provide a sufficient condition on $F$ and $A$ for the growth of $L(A,F)$ to be boundedly supermultiplicative.  That is, there exist constants $C>0$ and $\alpha\ge 0$, such that for all $n$, the number of words of length $n$ in $L(A,F)$ is between $\alpha^n$ and $C\alpha^n$. In some settings, our condition provides a way to compute $C$, which implies that $\alpha$, the growth rate of the language, is also computable whenever our condition holds.
+We also apply our technique to the specific setting of power-free words where the argument can be slightly refined to provide better bounds. Finally, we apply a similar idea to $F$-free circular words and in particular we make progress toward a conjecture of Shur about the number of square-free circular words.
 **March 11 2025:[[https://www.irif.fr/users/letouzey/index|Pierre Letouzey]]** //Generalizing some Hofstadter functions: G, H and beyond//
+{{ seminar2025:20250311letouzey.pdf |slides}}
 Hofstadter's G function is recursively defined via $G(0)=0$ and then
@@ Line 45: / Line 109: @@
-**March 25 2025: Vuong Bui**
+**February 25 2025: [[https://ms.polsl.pl/pracownik.php?kod=pawl|Bartek Pawlik]]** //Words Avoiding Tangrams//
-**April 8 2025: Hajime Kaneko**
+{{ seminar2025:20250225pawlik.pdf |slides}}
-**April 22 2025: Be'eri Greenfeld**
+{{ seminar2025:20250225pawlik.mp4 |video of the talk}}
-**May 6 2025: Jarkko Peltomäki**
-**May 20 2025: Pranjal Jain**
+Work in collaboration with Michał Dębski, Jarosław Grytczuk, Jakub Przybyło and Małgorzata Śleszyńska-Nowak.
-**June 3 2025: Curtis Bright**
-**June 17 2025: [[https://sites.google.com/view/noysofferaranov/bio|Noy Soffer Aranov]]**
+If, in a given word $W$, each letter appears an even number of times, then $W$ can be split into two identical, disjoint subwords. For example, the word $\mathtt{hotshots}$ can be split into two $\mathtt{hots}$ by dividing the word exactly in the middle: $\mathtt{hots\,|\,hots}$. More generally, any square can be separated into two identical words with a single cut. The word $\mathtt{tattletale}$ requires three cuts: $\mathtt{tat\,|\,tle\,|\,ta\,|\,le}$ to split it into two words $\mathtt{tatle}$. The minimal number of cuts needed to divide a word $W$ into two identical subwords is called the //cut number// of $W$. During the lecture, I will discuss several topics related to the cut number.
-**July 15 2025: [[https://apacz.matinf.uj.edu.pl/users/1719-elzbieta-krawczyk|Elżbieta Krawczyk]]**  //Quasi-fixed points of substitutions and substitutive systems//
-We study automatic sequences and automatic systems (symbolic dynamical systems) generated by general constant length (nonprimitive) substitutions. While an automatic system is typically uncountable, the set of automatic sequences is countable, implying that most sequences within an automatic system are not themselves automatic. We provide a complete classification of automatic sequences that lie in a given automatic system in terms of the so-called quasi-fixed points of the substitution defining the system. Quasi-fixed points have already appeared implicitly in a few places (e.g. in the  study of substitutivity of lexicographically minimal points in substitutive systems or in the study of subsystems of substitutive systems) and they have been described in detail by Shallit and Wang and, more recently, B\'eal, Perrin, and Restivo . We conjecture that a similar statement holds for general nonconstant length substitutions.
-==== Past talks 2025 ====