How Many Square Occurrences Must a Binary Sequence Contain?

  • Gregory Kucherov
  • Pascal Ochem
  • Michaël Rao


Every binary word with at least four letters contains a square. A. Fraenkel and J. Simpson showed that three distinct squares are necessary and sufficient to construct an infinite binary word. We study the following complementary question: how many square occurrences must a binary word contain? We show that this quantity is, in the limit, a constant fraction of the word length, and prove that this constant is $0.55080...$.

Article Number