TY - JOUR

T1 - Anti-powers in infinite words

AU - Fici, Gabriele

AU - Restivo, Antonio

AU - Silva, Manuel

AU - Zamboni, Luca Q.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - In combinatorics of words, a concatenation of k consecutive equal blocks is called a power of order k. In this paper we take a different point of view and define an anti-power of order k as a concatenation of k consecutive pairwise distinct blocks of the same length. As a main result, we show that every infinite word contains powers of any order or anti-powers of any order. That is, the existence of powers or anti-powers is an unavoidable regularity. Indeed, we prove a stronger result, which relates the density of anti-powers to the existence of a factor that occurs with arbitrary exponent. As a consequence, we show that in every aperiodic uniformly recurrent word, anti-powers of every order begin at every position. We further show that every infinite word avoiding anti-powers of order 3 is ultimately periodic, while there exist aperiodic words avoiding anti-powers of order 4. We also show that there exist aperiodic recurrent words avoiding anti-powers of order 6.

AB - In combinatorics of words, a concatenation of k consecutive equal blocks is called a power of order k. In this paper we take a different point of view and define an anti-power of order k as a concatenation of k consecutive pairwise distinct blocks of the same length. As a main result, we show that every infinite word contains powers of any order or anti-powers of any order. That is, the existence of powers or anti-powers is an unavoidable regularity. Indeed, we prove a stronger result, which relates the density of anti-powers to the existence of a factor that occurs with arbitrary exponent. As a consequence, we show that in every aperiodic uniformly recurrent word, anti-powers of every order begin at every position. We further show that every infinite word avoiding anti-powers of order 3 is ultimately periodic, while there exist aperiodic words avoiding anti-powers of order 4. We also show that there exist aperiodic recurrent words avoiding anti-powers of order 6.

KW - Anti-power

KW - Infinite word

KW - Unavoidable regularity

UR - http://www.scopus.com/inward/record.url?scp=85042588071&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2018.02.009

DO - 10.1016/j.jcta.2018.02.009

M3 - Article

AN - SCOPUS:85042588071

VL - 157

SP - 109

EP - 119

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

SN - 0097-3165

ER -