Currie–Saari recurrence conjecture for unbordered factors of the Thue–Morse sequence

Let t=t0t1t2\mathbf{t}=t_0t_1t_2\cdots be the Thue–Morse sequence, defined by t0=0t_0=0, t2n=tnt_{2n}=t_n, and t2n+1=1tnt_{2n+1}=1-t_n for n0n\geq 0. Let f(n)f(n) denote the number of unbordered factors of length nn in t\mathbf{t}. Currie–Saari's conjecture. The initial values are

f(0)=1,f(1)=2,f(2)=2,f(0)=1,\qquad f(1)=2,\qquad f(2)=2,

and, for n0n\geq 0, ff satisfies

f(4n+1)=f(2n+1),f(8n+2)=f(2n+1)8f(4n)+f(4n+3)+4f(8n),f(8n+3)=2f(2n)f(2n+1)+5f(4n)+f(4n+2)3f(8n),f(8n+4)=4f(4n)+2f(4n+2)+2f(8n),f(8n+6)=2f(2n)f(2n+1)+f(4n)+f(4n+2)+f(4n+3)f(8n),f(16n)=2f(4n)+3f(8n),f(16n+7)=2f(2n)+f(2n+1)5f(4n)+f(4n+2)+3f(8n),f(16n+8)=8f(4n)+4f(4n+2)+4f(8n),f(16n+15)=8f(4n)+2f(4n+3)+4f(8n)+f(8n+7).\begin{aligned} f(4n+1)&=f(2n+1),\\ f(8n+2)&=f(2n+1)-8f(4n)+f(4n+3)+4f(8n),\\ f(8n+3)&=2f(2n)-f(2n+1)+5f(4n)+f(4n+2)-3f(8n),\\ f(8n+4)&=-4f(4n)+2f(4n+2)+2f(8n),\\ f(8n+6)&=2f(2n)-f(2n+1)+f(4n)+f(4n+2)+f(4n+3)-f(8n),\\ f(16n)&=-2f(4n)+3f(8n),\\ f(16n+7)&=-2f(2n)+f(2n+1)-5f(4n)+f(4n+2)+3f(8n),\\ f(16n+8)&=-8f(4n)+4f(4n+2)+4f(8n),\\ f(16n+15)&=-8f(4n)+2f(4n+3)+4f(8n)+f(8n+7). \end{aligned}

The conjecture seeks an explicit description of the number of unbordered factors of each length; the preceding characterization determines which lengths occur but not their multiplicities. Its status is unresolved in the supplied source context.

Sources & referencesView supporting material

Primary source

Daniel Goc, Hamoon Mousavi and Jeffrey Shallit, “On the Number of Unbordered Factors”, arXiv:1211.1301 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.