Journal of Integer Sequences, Vol. 1 (1998), Article 98.1.9

There are More Than 2n/17 n-Letter Ternary Square-Free Words

Shalosh B. Ekhad and Doron Zeilberger
Department of Mathematics,
Temple University, Philadelphia, PA 19122, USA.
Email: zeilberg@math.rutgers.edu

Abstract: We prove that the "connective constant" for ternary square-free words is at least 21/17 = 1.0416... improving on Brinkhuis and Brandenburg's lower bounds of 21/24=1.0293... and 21/21=1.033... 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 non-empty word x. For example, "example" is square-free, but "exampample" is not. See Steven Finch's Mathematical Constants site [4] 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 [5] listing, 1,3,6,12,18,30,42, ....). Brinkhuis [3] and Brandenburg [2] (see also [1]) showed that a(n) is greater than 2n/24, and 2n/21 respectively. Here we show, by extending the method of [3], that a(n) is greater than 2n/17, and hence that mu:=the limit of a(n)1/n as n goes to infinity, is larger than 21/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.

It is easy to see (directly, or by adapting the argument in [3]), that if [[U0,V0],[U1,V1],[U2,V2]] is a k-Brinkhuis triple-pair, then for every square-free word x=x1...xn of length n in the alphabet {0,1,2}, the 2n words of length nk, [U or V]x1[U or V]x2...[U or V]xn are also all square-free. Thus the mere existence of a k-Brinkhuis triple-pair implies that a(nk) is greater than 2n *a(n), which implies that mu is greater than 21/(k-1).

Theorem: The following is an 18-Brinkhuis triple-pair

[[210201202120102012, 210201021202102012],
  [021012010201210120, 021012102010210120],
  [102120121012021201, 102120210121021201]].

Proof: Purely routine!

Remark: The above 18-Brinkhuis triple-pair was found by the first author by running procedure FindPair(); in the Maple package JAN, written by the second author.

Another Remark: Brinkhuis [3] constructed a 25-Brinkhuis triple-pair in which U0 and V0 were palindromes, and U1, U2, were obtained from U0 by adding, component-wise, 1 and 2 mod 3, respectively, and similarly for V1, V2. Our improved example resulted from relaxing the superfluous condition of palindromity, but we still have the second property. It is very likely that by relaxing the second property, it would be possible to find even shorter Brinkhuis triple-pairs, and hence get yet better lower bounds for mu. Alas, in this case the haystack gets much larger!

References

1. M. Baake, V. Elser and U. Grimm, The entropy of square-free words, Mathl. Comput. Modelling 26 (1997) 13-26.

2. F.-J. Brandenburg, Uniformly growing kth power-free homomorphisms, Theor. Comp. Sci. 23 (1983) 69-82.

3. J. Brinkhuis, Non-repetitive sequences on three symbols, Quart. J. Math. Oxford (2) 34 (1983) 145-149.

4. S. R. Finch, Mathematical Constants, Cambridge Univ. Press, 2003, pp. 367--371.

5. N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995. See also the Encyclopedia of Integer Sequences.


Received Aug. 28, 1998; revised Sept. 10, 1998. Published in Journal of Integer Sequences Oct. 23, 1998. Errata added March 26, 2003. Reference [4] changed, January 1 2007.


Return to Journal of Integer Sequences home page