It is well-known that the subword complexity of an automatic sequence grows at most linearly, meaning that the number of length-$\ell$ subwords which appear in a given automatic sequence $a = (a(n))_n$ is at most $C \ell$ for a constant $C$ dependent only on $a$. In contrast, arithmetic subword complexity measures the number of subwords which appear along arithmetic progressions, and can grow exponentially even for very simple automatic sequences. Indeed, the classical Thue-Morse sequence has arithmetic subword complexity $2^{\ell}$, which is the maximal possible complexity for $\{0,1\}$-valued sequence.

Together with Jakub Byszewski and Clemens Müllner we obtained a decomposition result which allows us to express any (complex-valued) automatic sequence as the sum of a structured part, which is easy to work with, and a part which is pseudorandom or uniform from the point of view of higher order Fourier analysis. We now apply these techniques to the study of arithmetic subword complexity of automatic sequences. We show that for each automatic sequence $a$ there exists a parameter $r$ --- which we dub "effective alphabet size" --- such that the arithmetic subword complexity of $a$ is at least $r^{\ell}$ and at most $(r+o(1))^{\ell}$.

This talk is based on joint work with Jakub Byszewski and Clemens Müllner.