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!
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 (in his book "Mathematical Constants").
for every square-free word of length 2: [a,b] (there are six of them)
the four words
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
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 thank Uwe Grimm for his careful reading, and for spotting this
inaccuracy.
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 Home Page
.pdf
.ps
.tex
.html
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
[U or V]_a [U or V]_b
are all square-free.
[U or V]_a [U or V]_b [U or V]_c ,
are square-free.
Added Oct. 2001:
1)The result in this paper was mentioned in Brian Hayes's intriguing
essay on the ternary system, published in his
Nov.-Dec. 2001 Computing Column of American Scientist.
Added Nov. 2003: My student
Xinyu Sun
currently holds the world record.
He broke Uwe Grimm's previous record.
See his paper, Vol. 6 of
Jorunal of Integer Sequences, paper 03.3.2 .
Back to
Doron Zeilberger's List of Papers