Anti-powers in infinite words (Q1747764): Difference between revisions

An anti-power of order \(k\), or a \(k\)-anti-power, is a concatenation of \(k\) consecutive pairwise distinct words of the same length. The authors observe that every infinite word contains powers of any order or anti-powers of any order (Theorem~1). A finitary version of this result is that for all integers \(\ell>1\) and \(k>1\), there exists \(N(\ell,k)\) such that every word of length \(N(\ell,k)\) contains either an \(\ell\)-power or a \(k\)-anti-power (Theorem~14). For \(k>2\), the authors establish the estimates \(k^2-1\leq N(k,k)\leq k^3{k\choose2}\). An infinite word \(w\) is said to avoid \(k\)-anti-powers if no factor of \(w\) is a \(k\)-anti-power. The authors show that an infinite word avoiding \(3\)-anti-powers must be ultimately periodic (Corollary~11) but exhibit an example of an aperiodic word avoiding \(4\)-anti-powers (Proposition~12) and an example of an aperiodic recurrent word avoiding \(6\)-anti-powers (Proposition~13). In contrast, for every aperiodic uniformly recurrent word \(x\) and every \(k>1\), there is an occurrence of a \(k\)-anti-power starting at every position of \(w\) (Corollary~7).