On the longest common subsequence of Thue-Morse words (Q2203606)

Let \(t_n\) be the \(n\)-th Thue-Morse word (that is, the prefix of length \(2^{n-1}\) of the infinite Thue-Morse word). Let \(\overline{t_n}\) be the bitwise complement of \(t_n\), and let \(a(n)\) be the length of the longest common (scattered) subsequence (LCS) of \(t_n\) and \(\overline{t_n}\). For example, the LCS of \(t_4=01101001\) and \(\overline{t}_4=10010110\) is \(01010\), of length \(5\), hence \(a(4)=5\). The first few values of the sequence \(a(n)\) are \(0, 1, 2, 5, 12, 26, 54, 110, 226, 462, 942, 1908,\ldots\). In 2006, Jean Berstel asked whether a formula for \(a(n)\) exists. In the current paper, the author proves that \(a(n)\) can be lower-bounded by \(2^n(1-o(1))\), that is, the fraction of omitted letters in the longest common subsequence of the \(n\)-th Thue-Morse word and its bitwise complement goes to 0 as \(n\) goes to infinity.