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.

Fici, G., Restivo, A., Silva, M., Zamboni, L.Q. (2018). Anti-powers in infinite words. JOURNAL OF COMBINATORIAL THEORY. SERIES A, 157, 109-119 [10.1016/j.jcta.2018.02.009].

Anti-powers in infinite words

Fici, Gabriele
;
Restivo, Antonio;
2018-01-01

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.
2018
Fici, G., Restivo, A., Silva, M., Zamboni, L.Q. (2018). Anti-powers in infinite words. JOURNAL OF COMBINATORIAL THEORY. SERIES A, 157, 109-119 [10.1016/j.jcta.2018.02.009].
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0097316518300244-main.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 316.59 kB
Formato Adobe PDF
316.59 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
279725_Fici_Anti-Powers_in_Infinite_Words.pdf

accesso aperto

Tipologia: Pre-print
Dimensione 309.76 kB
Formato Adobe PDF
309.76 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/279725
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 13
social impact