Bounds for the generalized repetition threshold (Q544880): Difference between revisions

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\).