Abelian periods, partial words, and an extension of a theorem of Fine and Wilf^∗

¹ Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402–6170, USA.
blanchet@uncg.edu
² Department of Mathematics, Massachusetts Institute of Technology, Building 2, Room 236, 77 Massachusetts Avenue, Cambridge, MA 02139–4307, USA
³ Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, IL 61801, USA
⁴ Department of Mathematics, The University of Arizona, 617 N. Santa Rita Ave., P.O. Box 210089 Tucson, AZ 85721–0089, USA

Received: 2 November 2010
Accepted: 21 January 2013

Abstract

Recently, Constantinescu and Ilie proved a variant of the well-known periodicity theorem of Fine and Wilf in the case of two relatively prime abelian periods and conjectured a result for the case of two non-relatively prime abelian periods. In this paper, we answer some open problems they suggested. We show that their conjecture is false but we give bounds, that depend on the two abelian periods, such that the conjecture is true for all words having length at least those bounds and show that some of them are optimal. We also extend their study to the context of partial words, giving optimal lengths and describing an algorithm for constructing optimal words.