Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
start [2025/03/25 18:53] – 139.124.146.3start [2025/04/22 14:24] (current) – 139.124.146.3
Line 23: Line 23:
  
  
-**April 8 2025: [https://trios.tsukuba.ac.jp/en/researcher/0000003624|Hajime Kaneko]** //Analogs of Markoff and Lagrange spectra on+**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// 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 The Lagrange spectrum is related to the rational approximations of badly
Line 38: Line 71:
 substitutions. This is joint work with Wolfgang Steiner. substitutions. This is joint work with Wolfgang Steiner.
  
-**April 22 2025: Be'eri Greenfeld** 
  
-**May 6 2025: Jarkko Peltomäki**+**March 25 2025: [[https://page.mi.fu-berlin.de/vbui/|Vuong Bui]]** //An explicit condition for boundedly supermultiplicative subshifts//
  
-**May 20 2025: Pranjal Jain** 
  
-**June 3 2025: Curtis Bright**+{{ seminar2025:20250325bui.pdf |slides}}
  
-**June 17 2025: [[https://sites.google.com/view/noysofferaranov/bio|Noy Soffer Aranov]]**+{{ seminar2025:20250325bui.mp4 |video of the talk}}
  
-**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 ==== 
- 
-**March 25 2025: [[https://page.mi.fu-berlin.de/vbui/|Vuong Bui]]** //An explicit condition for boundedly supermultiplicative subshifts// 
  
 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 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.