Skip to Main content Skip to Navigation
Journal articles

On repetition-free binary words of minimal density

Roman Kolpakov Gregory Kucherov 1 Yuri Tarannikov
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We study the minimal proportion (density) of one letter in $n$-th power-free binary words. First, we introduce and analyse a general notion of minimal letter density for any infinite set of words which don't contain a specified set of ``prohibited'' subwords. We then prove that for $n$-th power-free binary words the density function is $\frac{1}{n}+\frac{1}{n^3}+\frac{1}{n^4}+ {\cal O}(\frac{1}{n^5})$. We also consider a generalization of $n$-th power-free words for fractional powers (exponents): a word is $x$-th 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 $x$-th power-free binary words as a function of $x$ and prove, in particular, that this function is discontinuous at $\frac{7}{3}$ as well as at all integer points $n\geq 3$. Finally, we give an estimate of the size of the jumps.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00098854
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:39:18 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM

Identifiers

  • HAL Id : inria-00098854, version 1

Collections

Citation

Roman Kolpakov, Gregory Kucherov, Yuri Tarannikov. On repetition-free binary words of minimal density. Theoretical Computer Science, Elsevier, 1999, 218 (1), pp.161--175. ⟨inria-00098854⟩

Share

Metrics

Record views

160