Skip to Main content Skip to Navigation

How many square occurrences must a binary sequence contain

Abstract : Every binary word with at least four letters contains a square. Fraenkel and Simpson FraenkelSimpson95 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 we give a good estimation of this constant.
Document type :
Complete list of metadata
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 2:55:48 PM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM


  • HAL Id : inria-00101070, version 1




Gregory Kucherov, Pascal Ochem, Michael Rao. How many square occurrences must a binary sequence contain. [Intern report] A02-R-277 || kucherov02a, 2002, 9 p. ⟨inria-00101070⟩