2019/03/30 by Blikstad, Joakim
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1904.00248
The length a(n) of the longest common subsequence of the n'th Thue-Morse word and its bitwise complement is studied. An open problem suggested by Jean Berstel in 2006 is to find a formula for a(n). In this paper we prove new lower bounds on a(n) by explicitly constructing a common subsequence between the Thue-Morse words and their bitwise complement. We obtain the lower bound a(n) = 2n(1-o(1)), saying that when n grows large, the fraction of omitted symbols in the longest common subsequence of the n'th Thue-Morse word and its bitwise complement goes to 0. We further generalize to any prefix of the Thue-Morse sequence, where we prove similar lower bounds.