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/02/06 18:11] – 139.124.146.3start [2025/04/22 14:24] (current) – 139.124.146.3
Line 23: Line 23:
  
  
-**February 11 2025: [[https://dblp.org/pid/10/10715.html|Josef Rukavicka]]** //Palindromic length of infinite aperiodic words//+**May 6 2025: Jarkko Peltomäki**
  
-The palindromic length of the finite word $v$ is equal to the minimal number of palindromes whose concatenation is equal to $v$. It was conjectured in 2013 that for every infinite aperiodic word $x$, the palindromic length of its factors is not bounded. +**May 20 2025: Pranjal Jain**
-We prove this conjecture to be true.+
  
-Here is [[https://arxiv.org/abs/2410.12714|the paper]].+**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. 
 + 
  
-**February 25 2025: Bartek Pawlik** 
  
 **March 11 2025:[[https://www.irif.fr/users/letouzey/index|Pierre Letouzey]]** //Generalizing some Hofstadter functions: G, H and beyond// **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 Hofstadter's G function is recursively defined via $G(0)=0$ and then
Line 53: 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**+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.
  
-**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.+**February 11 2025: [[https://dblp.org/pid/10/10715.html|Josef Rukavicka]]** //Palindromic length of infinite aperiodic words//
  
 +{{ seminar2025:20250211rukavicka.pdf |slides}}
  
 +{{ seminar2025:20250211rukavicka.mp4 |video of the talk}}
  
-==== Past talks 2025 ==== 
  
-{{ seminar2025:20250128mol.pdf |slides}}+The palindromic length of the finite word $v$ is equal to the minimal number of palindromes whose concatenation is equal to $v$. It was conjectured in 2013 that for every infinite aperiodic word $x$, the palindromic length of its factors is not bounded. 
 +We prove this conjecture to be true. 
 + 
 +Here is [[https://arxiv.org/abs/2410.12714|the paper]]. 
  
-{{ seminar2025:20250128mol.mp4 |video of the talk}} 
  
  
  
 **January 28 2025: [[https://faculty.tru.ca/lmol/|Lucas Mol]]** //Avoiding abelian and additive powers in rich words// **January 28 2025: [[https://faculty.tru.ca/lmol/|Lucas Mol]]** //Avoiding abelian and additive powers in rich words//
 +
 +{{ seminar2025:20250128mol.pdf |slides}}
 +
 +{{ seminar2025:20250128mol.mp4 |video of the talk}}
 +
  
 We construct an infinite additive 5-power-free rich word over $\{0,1\}$ and an infinite additive 4-power-free rich word over $\{0,1,2\}$.  Both constructions involve affine morphisms, for which the length and sum of the images of the letters are linear functions of the letters.  This allows us to prove the additive power-freeness of our constructions using a recent variation of the template method due to Currie, Mol, Rampersad, and Shallit. We construct an infinite additive 5-power-free rich word over $\{0,1\}$ and an infinite additive 4-power-free rich word over $\{0,1,2\}$.  Both constructions involve affine morphisms, for which the length and sum of the images of the letters are linear functions of the letters.  This allows us to prove the additive power-freeness of our constructions using a recent variation of the template method due to Currie, Mol, Rampersad, and Shallit.