An Improved Lower Bound on the Number of Ternary Squarefree Words
Michael Sollami
Ditto Labs, Inc.
1 Broadway, 14th Floor
Cambridge, MA 02142
USA
Craig C. Douglas
University of Wyoming
School of Energy Resources and Department of Mathematics
1000 E. University Ave., Dept. 3036
Laramie, WY 82072
USA
Manfred Liebmann
Technische Universität München
Center for Mathematical Sciences
Boltzmannstraße 3
85748 Garching bei München
Germany
Abstract:
Let sn
be the number of words in the ternary alphabet Σ = {0, 1, 2} such
that no subword (or factor) is a square (a word concatenated with
itself, e.g., 11, 1212, and 102102). From computational evidence, the
sequence (sn) grows exponentially at a rate of about 1.317277n. While
known upper bounds are already relatively close to the conjectured
rate, effective lower bounds are much more difficult to obtain. In this
paper, we construct a 54-Brinkhuis 952-triple, which leads to an
improved lower bound on the number of n-letter ternary squarefree
words: 952n/53 ≈ 1.1381531n.
Full version: pdf,
dvi,
ps,
latex
Accompanying files:
b0.txt,
b1.txt,
b2.txt,
code.tgz
(Concerned with sequences
A006156
A010060.)
Received March 14 2016; revised version received May 5 2016; June 9 2016.
Published in Journal of Integer Sequences, July 6 2016.
Return to
Journal of Integer Sequences home page