RAIRO - Theoretical Informatics and Applications

Research Article

Infinite words containing squares at every position

James Curriea1 and Narad Rampersada1

a1 Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba R3B 2E9, Canada; j.currie@uwinnipeg.ca, n.rampersad@uwinnipeg.ca


Richomme asked the following question: what is the infimum of the real numbers α > 2 such that there exists an infinite word that avoids α-powers but contains arbitrarily large squares beginning at every position? We resolve this question in the case of a binary alphabet by showing that the answer is α = 7/3.

(Online publication February 11 2010)

Key Words:

  • Infinite words;
  • power-free words;
  • squares.

Mathematics Subject Classification:

  • 68R15.