Bounds for the generalized repetition threshold
type: Item
instance of: scholarly article
title: Bounds for the generalized repetition threshold
zbMATH Open document ID: 1232.68097
author: Francesca Fiorenzi
author: Pascal Ochem
author: Elise Vaslet
published in: Theoretical Computer Science
publication date: 2011-06-16T00:00:00Z
review text: A word \(w\) is a repetition of order \(\alpha\in\mathbb{Q}\) and length \(l\in\mathbb{N}\), if \(w=x^{n}x^{\prime}\), where \(x^{\prime}\) is a prefix of \(x\), \(|x|=\alpha\), and \(|w|=\alpha|x|\). A word is \(\left( \alpha,l\right) \)-free if it contains no factor being an \(\left( \alpha^{\prime},l^{\prime }\right) \)-repetition with \(\alpha^{\prime}\geq\alpha\) and \(l^{\prime}\geq l\). A word is \(\left( \alpha^{+},l\right) \)-free if it is \(\left( \alpha^{\prime},l\right) \)-free for all \(\alpha^{\prime}>\alpha\) (thus the condition on the \(\alpha\)-part is relaxed here; \(\alpha\) may be an irrational number as well). The repetition threshold is the least exponent \(\alpha\left( k\right) \) such that there exist infinite words over a \(k\)-letter alphabet \(\Sigma_{k}\) that avoid \(\left( \alpha+\varepsilon \right) \)-powers for all \(\varepsilon>0\). To investigate avoidance of repetitions with sufficiently long period, the generalized repetition threshold \ \(R\left( k,l\right) \) is defined as the smallest real number \(\alpha\) such that there exists an infinite \(\left( \alpha^{+},l\right) \)-free word over \(\Sigma_{k}\). The paper presents an improvement of the known estimation \(1+l/k^{l}\leq R\left( k,l\right)\leq2\). The authors' new lower bound, for \(k,l\geq3\), is \(1+1/m\), where \(m=k\left( 5l/6-1/2+2/\left( 2l-1\right) \right) \), and the upper bound, for a fixed \(k\) and sufficiently large \(l\), is \(1+\left( 2\ln l\right) /\left( l\ln\lambda\right) +O\left( 1/l\right) \), where \(\lambda=\left( k-1+\sqrt{\left( k-1\right) \left( k+3\right) }\right) /2\).
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 5908425
zbMATH Keywords: repetition threshold
zbMATH Keywords: Dejean's conjecture
reviewed by: Anton Černý
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.10.009
OpenAlex ID: W1987554801
cites work: Uniformly growing k-th power-free homomorphisms
cites work: On Dejean's conjecture over large alphabets
cites work: Dejean's conjecture and Sturmian words
cites work: Dejean's conjecture holds for N ≥ 27
cites work: A proof of Dejean’s conjecture
cites work: Sur un théorème de Thue
cites work: A generalization of repetition threshold
cites work: Proof of Dejean's conjecture for alphabets with \(5, 6, 7, 8, 9, 10\) and \(11\) letters
cites work: A propos d'une conjecture de F. Dejean sur les répétitions dans les mots
cites work: Last cases of Dejean's conjecture
DOI: 10.1016/J.TCS.2010.10.009
description: scientific article; zbMATH DE number 5908425