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

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 2^{1/17} = 1.0416...
improving on Brinkhuis and Brandenburg's lower bounds
of 2^{1/24}=1.0293... and
2^{1/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 2^{n/24},
and 2^{n/21} respectively.
Here we show, by extending the method of [3], that
a(n) is greater than 2^{n/17}, and hence that
mu:=the limit of a(n)^{1/n} as n goes to infinity, is larger
than 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, [U or V]0 [U or V]1 , [U or V]0 [U or V]2, [U or V]1 [U or V]2, [U or V]1 [U or V]0, [U or V]2 [U or V]0, [U or V]2 [U or V]1, (i.e. U0U1, U0V1, ..., V2V1), are all square-free.
- For every length r, between k/2 and k , the 12 words consisting of the heads and tails of U0,U1,U2,V0,V1,V2 of length r are all distinct.

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

[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!

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