On subwords in the base-$q$ expansion of polynomial and exponential functions

Abstract

Let $w$ be any word over the alphabet $\{0,1,\dots ,q-1\}$, and denote by $h$ either a polynomial of degree $d\ge 1$ or $h:n\mapsto m^n$ for a fixed $m$. Furthermore, denote by $e_q(w;h(n))$ the number of occurrences of $w$ as a subword in the base-$q$ expansion of $h(n)$. We show that \[ \limsup_{n\to\infty} \frac{e_q(w;h(n))}{\log n}\geq \frac{γ(w)}{l\log q}, \] where $l$ is the length of $w$ and $\gamma (w)\ge 1$ is a constant depending on a property of circular shifts of $w$. This generalizes work by the second author as well as is related to a generalization of Lagarias of a problem of Erdős.

8 pages