On repetition-free binary words of minimal density
We study the minimal proportion (density) of one letter in nth power-free binary words. First, we introduce and analyse a general notion of minimal letter density for any infinite set of words which does not contain a specified set of "prohibited" subwords. We then prove that for nth power-free binary words the density function is 1/n + 1/n(3) + 1/n(4) + O(1/n(5)). We also consider a generalization of nth power-free words for fractional powers (exponents): a word is xth power-free for a real x, if it does not contain subwords of exponent I or more. We study the minimal proportion of one letter in xth power-foe binary words as a function of x and prove, in particular, that this function is discontinuous at 7/3 as well as at all integer points n greater than or equal to 3. Finally, we give an estimate of the size of the jumps. (C) 1999 Elsevier Science B.V. All rights reserved.
minimal density power-free words exponent unavoidable patterns