A note on constructing infinite binary words with polynomial subword complexity^∗

¹ Department of Computer Science, University of North Carolina, PO Box 26170, Greensboro, NC 27402–6170, USA
blanchet@uncg.edu
² Department of Mathematics, University of California, San Diego, 9500 Gilman Drive, Dept 0112, LaJolla, CA 92093–0112, USA
³ School of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213–3891, USA

Received: 18 May 2012
Accepted: 8 January 2013

Abstract

Most of the constructions of infinite words having polynomial subword complexity are quite complicated, e.g., sequences of Toeplitz, sequences defined by billiards in the cube, etc. In this paper, we describe a simple method for constructing infinite words w over a binary alphabet  { a,b }  with polynomial subword complexity p_w. Assuming w contains an infinite number of a’s, our method is based on the gap function which gives the distances between consecutive b’s. It is known that if the gap function is injective, we can obtain at most quadratic subword complexity, and if the gap function is blockwise injective, we can obtain at most cubic subword complexity. Here, we construct infinite binary words w such that p_w(n) = Θ(n^β) for any real number β > 1.