There are More Than 2^(n/17) n-Letter Ternary Square-Free Words
Shalosh B. Ekhad, Doron Zeilberger · 1998
Abstract: We prove that the ‘connective constant ’ for ternary square-free words is at least 2 1/17 = 1.0416..., improving on Brinkhuis and Brandenburg’s lower bounds of 2 1/24 = 1.0293... and 2 1/22 = 1.032... respectively. This is the first improvement since 1983. A word is square-free if it never stutters, i.e. if it cannot be written as axxb for words a,b and nonempty word x. For example, ‘example ’ is square-free, but ‘exampample ’ is not. See Steven Finch’s famous Mathematical Constants site[3] for a thorough discussion and many references. Let a(n) be the number of ternary square-free n-letter words ( A006156, M2550 in the Sloane-Plouffe[4] listing, 1,3,6,12,18,30,42,...). Brinkhuis[2] and Brandenburg[1] showed that a(n) ≥ 2 n/24, and a(n) ≥ 2 n/22 respectively. Here we show, by extending the method of [2], that a(n) ≥ 2 n/17, and hence that µ: = limn→ ∞ a(n) 1/n ≥ 2 1/17 = 1.0416.... Definition: A triple-pair [[U0,V0], [U1,V1], [U2,V2]] where U0,V0,U1,V1,U2,V2 are words in the alphabet {0,1,2} of the same length k, will be called a k-Brinkhuis triple-pair if the following conditions are satisfied. • The 24 words of length 2k,