On the minimal complexity of infinite words

AbstractLet Q be an alphabet on q letters. Let W : Z ≥0 → Q be a word such that each letter of Q occurs with asymptotic density and that these q densities are linearly independent over the rationals. Let P(n) denote the cardinality of subwords of W of length n. We prove a theorem which implies that P(n) > n(q − 1) for every n. We further show that there are words W as above with P(n) = n(q − 1) + 1 for every n