On the size of the alphabet and the subword complexity of square-free DOI languages

A word is called square-free if it does not contain a subword of the form αα where α is a nonempty word. A language is called square-free if it consists of square-free words only. The subword complexity of a language K, denoted π_K, is a function of positive integers which for a positive integer n assigns the number of different subwords of lenght n occurring in words of K. It is known that if a DOL language K is square-free then, for all n, π_K(n) ≤ r n log₂ for some positive integer r. We demonstrate that there exists a square-free DOL language K on four letters such that, for all n, π_K(n) ≥ r n log₂ for some positive real p. This turns out to be the best lower bound on the size of the alphabet needed for a square-free DOL language to have the number of subwords of order nlog_nn