Enumeration of minimal factors of the form xxxRxxx^R

Let FmF_m be the Fibonacci numbers, let r\bf r be the Rote-Fibonacci word, and let (pi)F(p_i)_F, (qi)F(q_i)_F, and (si)F(s_i)_F denote the specified Fibonacci representations of the starting positions pip_i, qiq_i, and sis_i. Consider finite words of the form xxxRxxx^R having no proper factor of the form wwwRwww^R.

Minimal-xxxRxxx^R enumeration conjecture. For n=F3k+1n=F_{3k+1} there are 44 such words of length nn. For n=F3k+1±F3k2n=F_{3k+1}\pm F_{3k-2} there are 22 such words. Otherwise there are none. For k3k\geq 3, the words are exactly the factors of r\bf r beginning at the positions whose Fibonacci representations are

(p1)F=1000(010)k3001,(p2)F=10(010)k2001,(p_1)_F=1000(010)^{k-3}001,\quad (p_2)_F=10(010)^{k-2}001, (p3)F=1001000(010)k3001,(p4)F=1010(010)k2001,(p_3)_F=1001000(010)^{k-3}001,\quad (p_4)_F=1010(010)^{k-2}001,

for length F3k+1F_{3k+1};

(q1)F=10(010)k3001,(q2)F=10000(010)k3001,(q_1)_F=10(010)^{k-3}001,\quad (q_2)_F=10000(010)^{k-3}001,

for length F3k+1F3k2F_{3k+1}-F_{3k-2}; and

(s1)F=10(010)k3001,(s2)F=1000(01)k2001,(s_1)_F=10(010)^{k-3}001,\quad (s_2)_F=1000(01)^{k-2}001,

for length F3k+1+F3k2F_{3k+1}+F_{3k-2}.

This is a detailed conjectural enumeration of the shortest, or factor-minimal, occurrences of xxxRxxx^R in the Rote-Fibonacci word. It follows an explicit open problem in a section collecting claims the authors had not yet proved, so its status is open.

Sources & referencesView supporting material

Primary source

Chen Fei Du, Hamoon Mousavi, Luke Schaeffer and Jeffrey Shallit, “Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance”, arXiv:1406.0670 (2014).

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.