An Improved Lower Bound for n-Brinkhuis k-Triples

2016/06/02 by Michael Sollami, Sollami, Michael, Craig C. Douglas +3
Computer Science · Mathematics · #Algorithms and Data Compression #Coding theory and cryptography #cs.FL #math.CO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1606.00835

21 pages

arxiv created 2016/06/06 · arxiv updated 2016/06/07

Abstract

Let s_n be the number of words consisting of the ternary alphabet consisting of the digits 0, 1, and 2 such that no subword (or factor) is a square (a word concatenated with itself, e.g., 11, 1212, or 102102). From computational evidence, s_n grows exponentially at a rate of about 1.317277ⁿ. While known upper bounds are already relatively close to the conjectured rate, effective lower bounds are much more difficult to obtain. In this paper, we construct a 54-Brinkhuis 952-triple, which leads to an improved lower bound on the number of n-letter ternary squarefree words: 952^n/53 ≈ 1.1381531ⁿ.

Related

• Improved bounds on the number of ternary square-free words
• There are More Than 2**(n/17) n-Letter Ternary Square-Free Words
• Counting ternary square-free words quickly
• The repetition threshold for ternary rich words
• Fewest repetitions in infinite binary words