``There Are More Than 2**(n/17) n-Letter Ternary Square-Free Words'' By S. B. Ekhad and D. Zeilberger

Appeared in Jorunal of Integer Sequences, 98.1.9.

Written: Aug. 28, 1998.

Last Update: Aug. 30, 1998.

More than fifteen years ago, Jan Brinkhuis was GLOBALLY clever, by having a brilliant STRATEGY for proving lower bounds for connective constant for the sequence of the numbers of n-letter square-free ternary words.

Since he only used pencil-and-paper, he also had had to be LOCALLY clever, and develop some sneaky TACTICS in order to implement his global idea. This local cleverness is no longer necessary, since computers make it superflous. In fact, by merely programming Brinkhuis's global idea, it was prossible to do much better!

(Plain ) .tex version (2 pages)

.dvi version (for previewing)

.ps version

.pdf version

html version

Most importantly, download the Maple package JAN, thanks to which Salosh found the improved bound.

To understand the present paper, you are advised to read first Steve Finch's fascinating essay on Pattern-Avoiding words..

Added March 30, 2001: Jon McCammond wrote a more efficient program (using GAP) that showed that even with the much larger haystack, in which the components Brinkhaus pairs are not related, one still gets the same kind of needles, i.e. 2^(1/17) is best possible (with this method).

Added June 12, 2001: Erratum: Uwe Grimm pointed out that the definition of Brinkhuis triple-pair, as stated, is insufficient to guarantee square-freenes-preservation of the homomorphisms, by presenting a counterexample (see Uwe Grimm's message). However, this is easily fixed. The first conditon for being a Brinkhuis triple-pair is equivalent to demanding that

for every square-free word of length 2: [a,b] (there are six of them) the four words
[U or V]_a [U or V]_b
are all square-free.

This condition needs to be replaced by the following condition.

For every square-free word of length 3: [a,b,c] (there are twelve of them) the eight words
[U or V]_a [U or V]_b [U or V]_c ,
are square-free.

It is readily checked (by hand, or use procedure Images1 in JAN), that the proposed Brinkhuis triple-pair is indeed one, even in this new, stronger sense, hence the conclusion of the paper is upheld.

I than Uwe Grimm for his careful reading, and for spotting this inaccuracy.

Added Oct. 2001: 1)The result in this paper was mentioned in Brian Hayes's beatiful essay on the ternary system, published in his Nov.-Dec. 2001 Computing Column of American Scientist.

Thanks to Brian Hayes I also learned that Uwe Grimm extended the method of this paper, and improved the lower bound. See Grimm's interesting article

Back to Doron Zeilberger's List of Papers

Back to Doron Zeilberger's Home Page