Enumeration of minimal factors of the form xxxRxxx^R

About 12 years old · traced to

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±F3k−2n=F_{3k+1}\pm F_{3k-2} there are 22 such words. Otherwise there are none. For k≥3k\geq 3, the words are exactly the factors of r\bf r beginning at the positions whose Fibonacci representations are

(p1)F=1000(010)k−3001,(p2)F=10(010)k−2001,(p_1)_F=1000(010)^{k-3}001,\quad (p_2)_F=10(010)^{k-2}001, (p3)F=1001000(010)k−3001,(p4)F=1010(010)k−2001,(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)k−3001,(q2)F=10000(010)k−3001,(q_1)_F=10(010)^{k-3}001,\quad (q_2)_F=10000(010)^{k-3}001,

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

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

for length F3k+1+F3k−2F_{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.

References

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.