Avoiding fractional powers over the natural numbers (Q1753115): Difference between revisions

Let \(v = v_1 v_2 \ldots v_d\) be a (finite) word. For a rational number \(a/b\), with \(a\) and \(b\) positive coprime integers and \(b\) dividing \(d\), the fractional power \(a/b\) of \(v\) is defined as \(v^{a/b} := v^{\lfloor a/b \rfloor} v_1 v_2 \ldots v_{\{a/b\} d}\), where \(\lfloor a/b \rfloor\) and \(\{a/b\}\) are the integer part and the fractional part of \(a/b\). For example \((0111)^{3/2} = 011101\). A natural way of constructing long finite words (or possibly infinite words) that do not contain some pattern on a given ordered alphabet consists of starting with the empty word, then iteratively either appending the least letter of the alphabet, or, if this choice introduces an instance of the forbidden pattern, appending the next least letter, and so on. This procedure, possibly with backtracking, gives -- if it exists -- the lexicographically least infinite word that does not contain the forbidden pattern. Note that in the case of words on the nonnegative numbers, no backtracking is needed. The authors are interested in lexicographically least infinite words on the nonnegative integers that do not contain \(a/b\)-powers. In particular, using both technical lemmas and an automated procedure, they obtain \(a/b\)-power-free words as fixed points of (uniform) morphisms for three infinite families of rationals and for several ``sporadic'' rationals. To give the flavor of their far-from-easy results, let us cite two of them: The lexicographically least \(7/4\)-power-free word on the nonnegative integers is a fixed point of a \(50847\)-uniform morphism; he lexicographically least \(27/23\)-power-free word on the nonnegative integers is in fact a \(353\)-automatic sequence on the finite alphabet \(\{0,1,2\}\).