Dekking's conjecture on the subword complexity of the Fibonacci-Thue-Morse sequence

Let (ftm[n])n0({\bf ftm}[n])_{n\geq 0} be the Fibonacci-Thue-Morse sequence, obtained by summing modulo 22 the bits in the Fibonacci representation of nn. Let ρftm(n)\rho_{\bf ftm}(n) denote its subword complexity, and define

d(n):=ρftm(n+1)ρftm(n).d(n):=\rho_{\bf ftm}(n+1)-\rho_{\bf ftm}(n).

For each i2i\geq 2, let FiF_i denote the iith Fibonacci number. Dekking's conjecture. The first-difference sequence of the subword complexity is

(d(n))n0=(1,2,4,6,10)i26Fi+(1)i8Fi,(d(n))_{n\geq 0}=(1,2,4,6,10)\prod_{i\geq 2}6^{F_i+(-1)^i}\,8^{F_i},

that is, it begins

1,2,4,6,10,6,6,8,6,8,8,6,6,6,6,8,8,8,6,6,6,.1,2,4,6,10,6,6,8,6,8,8,6,6,6,6,8,8,8,6,6,6,\ldots.

The quantity d(n)d(n) counts the right-special factors of length nn in the Fibonacci-Thue-Morse sequence. The paper proves this conjecture, so the asserted formula is no longer open.

Sources & referencesView supporting material

Primary source

Jeffrey Shallit, “Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture”, arXiv:2010.10956 (2020).

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.