## Abstract

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} + script O sign(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 x or more. We study the minimal proportion of one letter in xth power-free 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 ≥ 3. Finally, we give an estimate of the size of the jumps.

Original language | English |
---|---|

Pages (from-to) | 161-175 |

Number of pages | 15 |

Journal | Theoretical Computer Science |

Volume | 218 |

Issue number | 1 |

DOIs | |

Publication status | Published - 28 Apr 1999 |

Externally published | Yes |

## Keywords

- Exponent
- Minimal density
- Power-free words
- Unavoidable patterns