Combinatorics Seminar

When: Sunday, April 15, 10am Where: Schreiber 309 Speaker: Yossi Moshe, Hebrew University Title: On the subword complexity of some generalized Thue-Morse sequences

Abstract:

Let A=(a_n)_{n=0}^{\infty} be a sequence over a finite set X. The (subword) complexity of A is the function m->P_A(m) where P_A(m) counts the number of distinct blocks a_k...a_{k+m-1} of size m in A. We begin with a background on the complexity function. Then we study the complexity of some sequences which are related to the Thue-Morse sequence (t_n)_{n=0}^{\infty}=0110100... (where t_n denotes the sum modulo 2 of the digits in the binary representation of n). This includes the Rudin-Shapiro sequence, the period-doubling sequence, and some subsequences of (t_n). In particular, we answer two questions of Allouche and Shallit [1] regarding (t_{n^2})_{n=0}^{\infty}.

We also study the patterns in the base-k representation of some squares n^2.

[1] J.-P. Allouche and J. O. Shallit, Automatic Sequences. Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003.