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

About 14 years old · traced to

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=1−tnt_{2n+1}=1-t_n for n≥0n\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 n≥0n\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.

References

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.