### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 109-119 |

Number of pages | 11 |

Journal | JOURNAL OF COMBINATORIAL THEORY. SERIES A |

Volume | 157 |

Publication status | Published - 2018 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Anti-powers in infinite words'. Together they form a unique fingerprint.

## Cite this

Fici, G., Restivo, A., Silva, M., & Zamboni, L. Q. (2018). Anti-powers in infinite words.

*JOURNAL OF COMBINATORIAL THEORY. SERIES A*,*157*, 109-119.