An Improved Lower Bound on the Number of Ternary Squarefree Words

Michael Sollami Ditto Labs, Inc.

1 Broadway, 14th Floor Cambridge, MA 02142

USA

michaelsollami@gmail.com

Craig C. Douglas University of Wyoming

School of Energy Resources and Department of Mathematics

1000 E. University Ave., Dept. 3036

Laramie, WY 82072

USA

cdougla6@uwyo.edu

Manfred Liebmann Technische Universität München Center for Mathematical Sciences

Boltzmannstraße 3 85748 Garching bei München

Germany

manfred.liebmann@tum.de

Abstract

Let s_{n} 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 (s_{n}) grows exponentially at a rate of about 1.317277^{n}. 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: 952^{n/53} ≈ 1.1381531^{n}.

1 Introduction

A word of length n is a string of n symbols from a finite alphabet Σ. We let Σ^{∗} denote the set of all finite words over Σ. A word w is said to be squarefree if it does not contain an adjacent repetition of a subword (or factor), i.e., w cannot be written as axxb for subwords a, b, and x where x is nonempty. In the field of combinatorics on words, the literature on pattern-avoiding words is vast and there has always been much progress in the study of powerfree words such as the binary cubefree and ternary squarefree words [9]. It is easy to see that there are only six nonempty binary squarefree words:

{0, 1, 01, 10, 101, 010}.

Using the Prouhet-Thue-Morse sequence (\underline{A010060}), the number of ternary squarefree words was proven to be infinite [12]. We let s_{n} denote the number of ternary squarefree words of length n [1, 12]; it grows exponentially [13]. We let A(n) denote the set of ternary squarefree words of length n.

This paper is organized into five sections. In Section 2, we define basic properties of n-Brinkhuis k-triples. In Section 3, we define how we searched for the 54-Brinkhuis 952-triple. In Section 4, we produce the newly discovered 54-Brinkhuis 952-triple. In Section 5, we describe how to get the code that found the specialized Brinkhuis triple of Section 4 and how to run it.

2 n-Brinkhuis k-triples

In this section, we define a n-Brinkhuis k-triple, prove a theorem about the lower bound on the growth rate s of the ternary squarefree words, and provide a history of estimates for the lower bound.

Definition 1. An n-Brinkhuis k-triple is a set B = {B^{0}, B^{1}, B^{2}} of three sets of words B^{i} = {w_{j}^{i} | 1 ≤ j ≤ k}. The w_{j}^{i} are squarefree words of length n such that for all squarefree words i_{1}i_{2}i_{3} with i_{1}, i_{2}, i_{3} ∈ {0, 1, 2} has the property that the word w_{j_{1}}^{i_{1}}w_{j_{2}}^{i_{2}}w_{j_{3}}^{i_{3}} of length 3n with j_{1}, j_{2}, j_{3} ∈ {1, 2, ⋯, k} is also squarefree.

An example of an 18-Brinkhuis 2-triple [8] is given by

B = { B^{0} = {210201202120102012, 210201021202102012},
B^{1} = {021012010201210120, 021012102010210120},
B^{2} = {102120121012021201, 102120210121021201} }.

The lower bound on the growth rate is given in the following theorem [5]:

Theorem 2. The existence of a special n-Brinkhuis k-triple implies that the lower bound on the growth rate of the ternary squarefree words is

k^{1/(n−1)} ≤ s = lim_{m→∞}(s_{m})^{1/m}.

Proof. We define the a set of uniformly growing morphisms by

ρ : \{ \begin{matrix}0 → w_{j_{0}}^{0}, \\ 1 → w_{j_{1}}^{1}, \\ 2 → w_{j_{2}}^{2}, \end{matrix}

where 1 ≤ j_{0}, j_{1}, j_{2} ≤ k. As proven in [4, 7, 11], the ρ are squarefree morphisms mapping each squarefree word of length m to k^{m} squarefree words of length nm. Thus, existence of an n-Brinkhuis k-triple indicates that

s_{mn}/s_{m} ≥ k^{m}, ∀ m, n ≥ 1.

Since s = lim_{m→∞}(s_{m})^{1/m},

s^{n−1} = lim_{m→∞} (\frac{s_{mn}}{s_{m}} )^{1/m} ≥ k,

which yields the lower bound of s ≥ k^{1/(n−1)}.

A history of estimates for the lower bound for s is given in Table 1. As is obvious from Theorem 2, the discovery of a n-Brinkhuis k-triple for a new pair (n,k) potentially gives us a new a lower bound for s.

n k  Lower bound  Year Authors
25 2 2^{n/24} ≈ 1.0293022^{n} 1983 Brinkhuis [5]
22 2 2^{n/21} ≈ 1.0335578^{n} 1983 Brandenburg [4]
18 2 2^{n/17} ≈ 1.0416160^{n} 1998 Ekhad and Zeilberger [8]
41 65 65^{n/40} ≈ 1.1099996^{n} 2001 Grimm [10]
43 110 110^{n/42} ≈ 1.1184191^{n} 2003 Sun [16]
54 952 952^{n/53} ≈ 1.1381531^{n} 2016 Sollami, Douglas, and Liebmann

Table 1: Lower bounds for s.

3 Searching for n-Brinkhuis k-triples

In this section we describe how we searched for n-Brinkhuis k-triples.

We can pare down the search by systematically determining the prefixes and suffixes of the words in a special n-Brinkhuis k-triple. Grimm [10] proved that only two classes of special n-Brinkhuis k-triples must be searched, namely

A_{1}(n) = {w ∈ A(n) | w = 012021{0, 1, 2}^{∗}120210} ⊆ A(n)

and

A_{2}(n) = {w ∈ A(n) | w = 012102{0, 1, 2}^{∗}201210} ⊆ A(n),

where we recall that A(n) is the set of ternary squarefree words of length n.

Let \overline{w} be the reversal of symbols in w. We use this notation to be consistent with earlier papers in this field, e.g., [10, 16] (it is sometimes denoted by w^{R} by other authors). For example, if w = 0122, then \overline{w} = 2210. When a word is equivalent to its own reversal we call it a palindrome, and here is an example of one:

w = 2112 = \overline{w}.

We denote the number of potential words, palindromes, and nonpalindromes for each set A_{i}(n), i ∈ {1, 2}, by

a_{i}(n) = |A_{i}(n)|,
a_{ip}(n) = |\{w ∈ A_{i}(n) | w = \overline{w}\}|,
a_{in}(n) = |\{w ∈ A_{i}(n) | w ≠ \overline{w}\}|.

Clearly, there are no palindromic squarefree words of even length. Thus, a_{1p}(2n) = a_{2p}(2n) = 0, a_{1n}(2n) = a_{1}(2n)/2, and a_{2n}(2n) = a_{2}(2n)/2 [10]. If a word in A_{1}(n) or A_{2}(n) is a member of a special n-Brinkhuis k-triple, then it must at least generate a Brinkhuis triple by itself, which motivates the following definition:

Definition 3. A word w is admissible if {w, τ(w), τ^{2}(w)} is a special n-Brinkhuis k-triple, where τ is the permutation

τ : \{ \begin{matrix}0 & → & 1, \\ 1 & → & 2, \\ 2 & → & 0. \end{matrix}  (1)

As before, we denote the number of admissible words, palindromes, and nonpalindromes for each set A_{i}(n), i ∈ {1, 2}, by

b_{i}(n) = |{w ∈ A_{i}(n) and w is admissible}|,
b_{ip}(n) = |\{w ∈ A_{i}(n) | w = \overline{w} and w is admissible\}|,
b_{in}(n) = |\{w ∈ A_{i}(n) | w ≠ \overline{w} and w is admissible\}|.

The strategy we used to find a special n-Brinkhuis k-triple begins by enumerating the set of all admissible words of length n. From this enumeration we determine the largest subset in which any three words w_{1}, w_{2}, w_{3}, form a special n-Brinkhuis triple.

The method we used to find a special n-Brinkhuis k-triple is summarized below in three steps:

Step 1. Find all admissible words in A_{1}(n) and A_{2}(n).

Step 2. Find all triples of admissible words that generate a special n-Brinkhuis k-triple.

Step 3. Find the largest set of admissible words such that all three-elemental subsets are contained in our list of admissible triples.

Steps 1 and 2 are essentially precomputations which involve checking the squarefreeness of words. A naive algorithm for detecting squares has time complexity of order O(n^{3}) for words of length n and a fixed length alphabet. Crochemore [7] improved this algorithm to O(n log n) and it was later improved to O(n) [1].

Experimentally it seems that A_{1} is more likely to provide maximum sized n-Brinkhuis triples for large n than generators from the set A_{2} and so we restricted our search to this specific class [10]. It is also simpler to find n-Brinkhuis k-triples in A_{1}(n) where n is even since a maximum number of generators does not necessarily give the largest Brinkhuis triple (i.e., unless we know that none of the words are palindromes, as they are for even n).

It is in the Step 3 that our main difficulty becomes apparent. The way we found n-Brinkhuis k-triples involved solving a purely combinatorial problem that is an instance of the NP-complete maximum clique problem for hypergraphs [6]. A maximum clique in a hypergraph on n vertices with hyperedges of cardinality at most ℵ can be found using a branching algorithm in O(2^{κn}) time for some κ < 1, depending only on ℵ [2].

4 A 54-Brinkhuis 952-triple

Theorem 4. A special 54-Brinkhuis 952-triple exists, and thus shows

s ≥ 952^{1/53} ≈ 1.1381531 > 110^{1/42} ≈ 1.1184191.

Proof. The proof is completed by a computational construction of a special Brinkhuis triple. We list B^{0} explicitly below, B^{1} is constructed by applying the τ permutation 1 on B^{0}, and B^{2} is constructed by applying the τ permutation on B^{1}. All three sets are available as plain text files on the website [15].

Practical algorithms have been developed to solve the maximum clique problem, Bomze et al. [3] give a comprehensive survey of methods for finding maximum cliques. We adapted these methods to solve the corresponding problem for hypergraphs. Specifically, we used the random hyperclique search algorithm [14] to perform our computer search for maximum cliques.

Formally, the first 476 elements of B^{0} are given below. The remaining 476 elements are reversals of the first 476 elements.

012021201020120210201021012010201210201021012102120210, 012021201020121021201020120210201021201210120102120210, 012021201021012102012101202102012021201210120102120210,

012021020102120102012021020102101202120121020102120210, 012021020102120121012010210121020102120210121020120210, 012021020102120210201202120102101210201202120102120210, 012021020121021201020121012010212012101202120102120210, 012021020102120102012021020102101210201021201020120210, 012021020102120121012010210121020120210121020102120210, 012021020102120210201202120102101210201210120102120210, 012021020121021201020121012021012102012021020102120210, 012021201020120210201021012010212012101202120102120210, 012021201020121021201020120212012101201021012102120210, 012021201021012102120102012021020102101202120102120210,

012021020102120102012021020102101210201202120102120210, 012021020102120121012010210121021202101202120102120210, 012021020102120210201202120102120210201021012102120210, 012021020121021201020121012021012102120121020102120210, 012021201020120210201021012021020120210121020102120210, 012021201020121021201020120212012102012021012102120210, 012021201021012102120102012021201210201021012102120210,

012021020102120102012021020102101210201210120102120210, 012021020102120121012010212021012102010210120102120210, 012021020102120210201202120121020120210121020102120210, 012021020121021201020121012021020102120121020102120210, 012021201020120210201021012102120102012021012102120210, 012021201020121021201021012010201202120121020102120210, 012021201021012102120102012102120121012021012102120210,

012021020102120102012021020121012021201210120102120210, 012021020102120121012010212021012102012021201020120210, 012021020102120210201210120102101210201202120102120210, 012021020121021201020121012021020120210121020102120210, 012021201020120210201021012102120102101202120102120210, 012021201020121021201021012010201210201021012102120210, 012021201021012102120102012102120210201021012102120210,

012021020102120102012021201021012021201210120102120210, 012021020102120121012010212021012102120121020102120210, 012021020102120210201210120102101210201210120102120210, 012021020121021201020121020102120102012021012102120210, 012021201020120210201021012102120121012021012102120210, 012021201020121021201021012010212012101202120102120210, 012021201021012102120102101201020121012021012102120210,

012021020102120102012021201021012102010210120102120210, 012021020102120121012010212021020102101202120102120210, 012021020102120210201210120102120121012021012102120210, 012021020121021201020121020102120102012021020102120210, 012021201020120210201021012102120210201202120102120210, 012021201020121021201021012021020102101202120102120210, 012021201021012102120102101201021202101202120102120210,

012021020102120102012021201021012102012021012102120210, 012021020102120121012010212021020102120121020102120210, 012021020102120210201210120102120121012021020102120210, 012021020121021201020121020102120121012021012102120210, 012021201020120210201021201020120212010210120102120210, 012021201020121021201021012021201210201021012102120210, 012021201021012102120102101202120102012021012102120210,

012021020102120102012021201021012102012021020102120210, 012021020102120121012010212021020120210121020102120210, 012021020102120210201210120102120210201021012102120210, 012021020121021201020121020102120121012021020102120210, 012021201020120210201021201020121021201021012102120210, 012021201020121021201021012102120102012021012102120210, 012021201021012102120121012010201210201021012102120210,

012021020102120102012021201021012102012021201020120210, 012021020102120121012021020102101210201202120102120210, 012021020102120210201210120102120210201202120102120210, 012021020121021201020121020102120210201021012102120210, 012021201020120210201021201020121021201210120102120210, 012021201020121021201021012102120121012021012102120210, 012021201021012102120121012021020102101202120102120210,

012021020102120102012021201021012102120121020102120210, 012021020102120121012021020102120210121021201020120210, 012021020102120210201210120210201021201210120102120210, 012021020121021201020121020102120210201202120102120210, 012021201020120210201021201210120102012021012102120210, 012021201020121021201021012102120210201202120102120210, 012021201021012102120121012021201210201021012102120210, 012021020102120102012021201021012102120210121020120210, 012021020102120121012021020102120210201202120102120210, 012021020102120210201210120212012101201021012102120210, 012021020121021201021012021020120212010210120102120210, 012021201020120210201021201210120102101202120102120210, 012021201020121021201210120102101210201202120102120210, 012021201021012102120121020102120102012021012102120210,

012021020102120102012021201021202101202120121020120210, 012021020102120121012021020120210120102120121020120210, 012021020102120210201210120212012102012021201020120210, 012021020121021201021012102010212012101202120102120210, 012021201020120210201021201210120102120121020102120210, 012021201020121021201210120102101210201210120102120210, 012021201021012102120121020102120121012021012102120210,

012021020102120102012021201021202102010210120102120210, 012021020102120121012021020120212012101202120102120210, 012021020102120210201210212010201210201021012102120210, 012021020121021201021012102012021012102120121020120210, 012021201020120210201021201210120210201021012102120210, 012021201020121021201210120102120210201021012102120210, 012021201021012102120121020102120210201021012102120210,

012021020102120102012021201021202102012021012102120210, 012021020102120121012021020121012021201210120102120210, 012021020102120210201210212012101202120121020102120210, 012021020121021201021012102012101202120121020102120210, 012021201020120210201021201210120210201202120102120210, 012021201020121021201210120102120210201202120102120210, 012021201021012102120121020102120210201202120102120210,

012021020102120102012021201021202102012021201020120210, 012021020102120121012021201020120210201021012102120210, 012021020102120210201210212021012102012021012102120210, 012021020121021201021012102120210201202120121020120210, 012021201020120210201021201210120212010210120102120210, 012021201020121021201210120210121021201021012102120210, 012021201021012102120121020120212012101202120102120210,

012021020102120102012021201210120102012021012102120210, 012021020102120121012021201020121020102120121020120210, 012021020102120210201210212021020102101202120102120210, 012021020121021201210120102012021012102120121020120210, 012021201020120210201021201210201202120121020102120210, 012021201020121021201210120210121021201210120102120210, 012021201021012102120210120102120121012021012102120210,

012021020102120102012021201210120102012021020102120210, 012021020102120121012021201021012021201210120102120210, 012021020102120210201210212021020102120121020102120210, 012021020121021201210120102012101202120121020102120210, 012021201020120210201021202101210212010210120102120210, 012021201020121021201210120210201021201210120102120210, 012021201021012102120210120102120210201021012102120210,

012021020102120102012021201210120102101202120102120210, 012021020102120121012021201021012102012021012102120210, 012021020102120210201210212021020102120210121020120210, 012021020121021201210120102012102120210121020102120210, 012021201020120210201021202102012021201021012102120210, 012021201020121021201210120210201202120121020102120210, 012021201021012102120210120102120210201202120102120210,

012021020102120102012021201210120102120121020102120210, 012021020102120121012021201021012102012021020102120210, 012021020121012010201202101201020121012021012102120210, 012021020121021201210120102101202102010210120102120210, 012021201020120210201021202102012021201210120102120210, 012021201020121021201210120212012102010210120102120210, 012021201021012102120210120212012101201021012102120210,

012021020102120102012021201210120210201021012102120210, 012021020102120121012021201021012102012021201020120210, 012021020121012010201210201021201210201202120102120210, 012021020121021201210120102101202102012021012102120210, 012021201020120210201021202102012101201021012102120210, 012021201020121021201210120212012102012021012102120210, 012021201021012102120210121020120210201021012102120210,

012021020102120102012021201210120210201202120102120210, 012021020102120121012021201021012102120210121020120210, 012021020121012010201210212010201202120121020102120210, 012021020121021201210120102101210201202120121020120210, 012021020102120102012021201210120212010210120102120210, 012021020102120121012021201021202102010210120102120210, 012021020121012010201210212012101202120121020102120210, 012021020121021201210120102101210212010210120102120210, 012021201020120210201210120102101210201210120102120210, 012021201020121021201210201202101210201210120102120210, 012021201021012102120210201202120102012021012102120210,

012021020102120102012021201210120212010210121020120210, 012021020102120121012021201021202102012021012102120210, 012021020121012010212012101201020120210121020102120210, 012021020121021201210120102120121021201021012102120210, 012021201020120210201210120102120121012021012102120210, 012021201020121021201210201202120121012021012102120210, 012021201021012102120210201202120121012021012102120210,

012021020102120102012101201020120210121021201020120210, 012021020102120121012021201021202102012021201020120210, 012021020121012010212012101201020121012021012102120210, 012021020121021201210120102120210201202120121020120210, 012021201020120210201210120102120210201021012102120210, 012021201020121021202101201020120210201021012102120210, 012021201021012102120210201210212012101202120102120210,

012021020102120102012101201021012102012021012102120210, 012021020102120210120102012021012102010210120102120210, 012021020121012010212012101202101210201021012102120210, 012021020121021201210120210201021202101202120102120210, 012021201020120210201210120102120210201202120102120210, 012021201020121021202101201020121021201021012102120210, 012021201021202101201020120210121021201021012102120210,

012021020102120102012101201021012102012021020102120210, 012021020102120210120102012021012102012021201020120210, 012021020121012010212012101202101210201202120102120210, 012021020121021201210120212010201202120121020102120210, 012021201020120210201210120210121021201021012102120210, 012021201020121021202101202120102012101202120102120210, 012021201021202101201021012102120102012021012102120210,

012021020102120102012101201021012102012021201020120210, 012021020102120210120102012021012102120121020102120210, 012021020121012010212012101202101210201210120102120210, 012021020121021201210120212010201210201021012102120210, 012021201020120210201210120210201021201210120102120210, 012021201020121021202101202120121021201021012102120210, 012021201021202101201021012102120121012021012102120210,

012021020102120102012101201021012102120121020102120210, 012021020102120210120102012021020102101202120102120210, 012021020121012010212012101202102010210121020102120210, 012021020121021201210201021201020120210121020102120210, 012021201020120210201210120210201202120121020102120210, 012021201020121021202101210201021202101202120102120210, 012021201021202101201021012102120210201202120102120210,

012021020102120102012101201021012102120210121020120210, 012021020102120210120102012021020102120121020102120210, 012021020121012010212012101202102012102120121020120210, 012021020121021201210201021201020121012021012102120210, 012021201020120210201210120212012101201021012102120210, 012021201020121021202101210212012101201021012102120210, 012021201021202101201021201210120102012021012102120210,

012021020102120102012101201021201210201021012102120210, 012021020102120210120102012021020102120210121020120210, 012021020121012010212012101202120102012021012102120210, 012021020121021201210201021202102010210121020102120210, 012021201020120210201210120212012102012021012102120210, 012021201020121021202101210212012102010210120102120210, 012021201021202101201021201210120210201021012102120210,

012021020102120102012101201021201210201021201020120210, 012021020102120210120212010201202102010210120102120210, 012021020121012010212012101202120102012021020102120210, 012021020121021201210201021202102012102120121020120210, 012021201020120210201210120212012102012021020102120210, 012021201020121021202101210212012102012021012102120210, 012021201021202101201021201210120210201202120102120210, 012021020102120102012101201021201210201202120102120210, 012021020102120210120212010201210120102120121020120210, 012021020121012010212012101202120102120210121020120210, 012021020121021201210201202101201021201210120102120210, 012021201020120210201210212010201202120121020102120210, 012021201020121021202102010210120102012021012102120210, 012021201021202101202120102101202102012021012102120210,

012021020102120102012101201021202101202120121020120210, 012021020102120210120212010201210212010210121020120210, 012021020121012010212012102120102012102120121020120210, 012021020121021201210201202101210212010210120102120210, 012021201020120210201210212010201210201021012102120210, 012021201020121021202102010210121021201210120102120210, 012021201021202101210201021201020121012021012102120210,

012021020102120102012101201021202102010210120102120210, 012021020102120210120212010210120102012021020102120210, 012021020121012010212012102120210201202120121020120210, 012021020121021201210201202120102012101202120102120210, 012021201020120210201210212012101202120121020102120210, 012021201020121021202102010212012101201021012102120210, 012021201021202101210212010210120102012021012102120210,

012021020102120102012101201021202102010210121020120210, 012021020102120210120212010210120210201021012102120210, 012021020121012010212021012021201210201021012102120210, 012021020121021201210201202120102120210121020102120210, 012021201020120210201210212021012102012021012102120210, 012021201020121021202102010212012102010210120102120210, 012021201021202101210212010210120210201021012102120210,

012021020102120102012101201021202102012021012102120210, 012021020102120210120212010210121020102120121020120210, 012021020121012010212021012102120102012021012102120210, 012021020121021201210201202120121021201021012102120210, 012021201020120210201210212021012102120121020102120210, 012021201020121021202102010212012102012021012102120210, 012021201021202101210212010210120210201202120102120210,

012021020102120102012101201021202102012021201020120210, 012021020102120210120212010210121021201210120102120210, 012021020121012010212021012102120102012021020102120210, 012021020121021202101202120102101210201202120102120210, 012021201020120210201210212021020120210121020102120210, 012021201020121021202102012021012102010210120102120210, 012021201021202101210212012102012021201021012102120210,

012021020102120102012101202101210212010210120102120210, 012021020102120210120212010212021012102120121020120210, 012021020121012010212021012102120121012021012102120210, 012021020121021202101202120102101210201210120102120210, 012021201020121012010201202101201021201210120102120210, 012021201020121021202102012102120121012021012102120210, 012021201021202102012021012010201210201021012102120210,

012021020102120102012101202101210212010210121020120210, 012021020102120210120212010212021020102120121020120210, 012021020121012010212021012102120210201202120102120210, 012021020121021202101202120102120210201021012102120210, 012021201020121012010201202101210212010210120102120210, 012021201021012010201202101201021202101202120102120210, 012021201021202102012021012102120121012021012102120210,

012021020102120102012101202102010210121021201020120210, 012021020102120210121021201020120210201021012102120210, 012021020121012010212021020102120102012021012102120210, 012021020121021202101210201021202102010210120102120210, 012021201020121012010201202102012101201021012102120210, 012021201021012010201202102010212012101202120102120210, 012021201021202102012021012102120210201202120102120210,

012021020102120102012101202102012021201021012102120210, 012021020102120210121021201020120212010210120102120210, 012021020121012010212021020102120102012021020102120210, 012021020121021202101210212010201202120121020102120210, 012021201020121012010201202102012102120121020102120210, 012021201021012010201202120102101210201202120102120210, 012021201021202102012021201020120210201021012102120210,

012021020102120102012101202102012021201210120102120210, 012021020102120210121021201020120212010210121020120210, 012021020121012010212021020102120121012021012102120210, 012021020121021202101210212010201210201021012102120210, 012021020102120102012101202102012101201021012102120210, 012021020102120210121021201020121020102120121020120210, 012021020121012010212021020102120121012021020102120210, 012021020121021202101210212012101202120121020102120210, 012021201020121012010201202120121021201021012102120210, 012021201021012010201202120102120210201021012102120210, 012021201021202102012021201021012102012021012102120210,

012021020102120102012101202102012102120121020102120210, 012021020102120210121021201020121021201210120102120210, 012021020121012010212021020120212012101202120102120210, 012021020121021202102012021201020120210121020102120210, 012021201020121012021020102101201021201210120102120210, 012021201021012010201210120102120121012021012102120210, 012021201021202102012021201210120102012021012102120210,

012021020102120102012101202120102120210121020102120210, 012021020102120210121021201021012021201210120102120210, 012021020121012021201020120210120102120121020102120210, 012021020121021202102012021201020121012021012102120210, 012021201020121012021020102101202102012021012102120210, 012021201021012010201210120102120210201021012102120210, 012021201021202102012021201210120210201021012102120210,

012021020102120102012101202120121021201021012102120210, 012021020102120210121021201021012102010210120102120210, 012021020121012021201020120210121021201021012102120210, 012021020121021202102012101201020120210121020102120210, 012021201020121012021020102101210212010210120102120210, 012021201021012010201210120102120210201202120102120210, 012021201021202102012101201021012102012021012102120210,

012021020102120102012102010212012101201021012102120210, 012021020102120210121021201021012102012021012102120210, 012021020121012021201020120210121021201210120102120210, 012021020121021202102012101201021202101202120102120210, 012021201020121012021020102120102012101202120102120210, 012021201021012010201210120210121021201021012102120210, 012021201021202102012101201021201210201021012102120210,

012021020102120102012102010212012102012021012102120210, 012021020102120210121021201021012102012021020102120210, 012021020121012021201020120210201021201210120102120210, 012021020121021202102012101202120102012021020102120210, 012021201020121012021020102120121021201021012102120210, 012021201021012010201210120210121021201210120102120210, 012021201021202102012101201021202102012021012102120210,

012021020102120102012102010212012102012021020102120210, 012021020102120210121021201021012102012021201020120210, 012021020121012021201020120212012102012021012102120210, 012021201020120210121021201020120210201021012102120210, 012021201020121012021020120210120102012021012102120210, 012021201021012010201210120210201021201210120102120210, 012021201210120102012021012010201210201021012102120210,

012021020102120102012102010212012102012021201020120210, 012021020102120210121021201021012102120210121020120210, 012021020121012021201021012102120102012021012102120210, 012021201020120210121021201020120212010210120102120210, 012021201020121012021020120210120102120121020102120210, 012021201021012010201210120212012102010210120102120210, 012021201210120102012021012102120121012021012102120210,

012021020102120102012102010212021012102120121020120210, 012021020102120210121021201210120102012021012102120210, 012021020121012021201021012102120121012021012102120210, 012021201020120210121021201020121021201210120102120210, 012021201020121012021020120210121021201021012102120210, 012021201021012010201210212021012021201210120102120210, 012021201210120102012021020102120102012021012102120210,

012021020102120102012102120102101210201202120102120210, 012021020102120210121021201210120102012021020102120210, 012021020121012021201021012102120121012021020102120210, 012021201020120210121021201021012021201210120102120210, 012021201020121012021020120210121021201210120102120210, 012021201021012010212012101201020121012021012102120210, 012021201210120102012021020102120121012021012102120210, 012021020102120102012102120102101210201210120102120210, 012021020102120210121021201210120102101202120102120210, 012021020121012021201021202101201021201210120102120210, 012021201020120210121021201021012102010210120102120210, 012021201020121012021020120212012101201021012102120210, 012021201021012010212012101201021202101202120102120210, 012021201210120102012021201020121021201021012102120210,

012021020102120102012102120121020120210121020102120210, 012021020102120210121021201210120102120121020102120210, 012021020121012021201021202101210212010210120102120210, 012021201020120210121021201021012102012021012102120210, 012021201020121012021020120212012102010210120102120210, 012021201021012010212012101202101210201021012102120210, 012021201210120102012021201021012102012021012102120210,

012021020102120102012102120210120212010210120102120210, 012021020102120210121021201210120102120210121020120210, 012021020121012021201021202102012021201210120102120210, 012021201020120210121021201021012102012021020102120210, 012021201020121012021020120212012102012021012102120210, 012021201021012010212012101202101210201210120102120210, 012021201210120102012021201021202102012021012102120210,

012021020102120102012102120210121021201210120102120210, 012021020102120210121021201210120210201021012102120210, 012021020121012021201021202102012101201021012102120210, 012021201020120210121021201210120102012021012102120210, 012021201020121012021020121021201210201021012102120210, 012021201021012010212012101202120102012021012102120210, 012021201210120102012102010210120102012021012102120210,

012021020102120102012102120210201021012021201020120210, 012021020102120210121021201210120210201202120102120210, 012021020121012021201021202102012102120121020102120210, 012021201020120210121021201210120102012021020102120210, 012021201020121012021020121021202102012021012102120210, 012021201021012010212021012021201210201021012102120210, 012021201210120102012102010212012102012021012102120210,

012021020102120102012102120210201021201210120102120210, 012021020102120210121021201210120212010210120102120210, 012021020121012021201210120102101210201202120102120210, 012021201020120210121021201210120102101202120102120210, 012021201020121012021201021012102120210121020102120210, 012021201021012010212021012102120102012021012102120210, 012021201210120102101210201202120102012021012102120210,

012021020102120121012010201202101210201021012102120210, 012021020102120210121021201210120212010210121020120210, 012021020121012021201210120102101210201210120102120210, 012021201020120210121021201210120102120121020102120210, 012021201020121012021201021202101202120121020102120210, 012021201021012010212021012102120102101202120102120210, 012021201210120102101210212021012102012021012102120210,

012021020102120121012010201202101210201202120102120210, 012021020102120210121021201210201202120121020102120210, 012021020121012021201210120102120121012021012102120210, 012021201020120210121021201210120210201021012102120210, 012021201020121012021201021202101210201021012102120210, 012021201021012010212021012102120121012021012102120210, 012021201210120102120121020102120102012021012102120210,

012021020102120121012010201202101210201210120102120210, 012021020102120210121021202102012021201021012102120210, 012021020121012021201210120102120121012021020102120210, 012021201020120210121021201210120210201202120102120210, 012021201020121012021201021202101210201202120102120210, 012021201021012010212021012102120210201202120102120210, 012021201210120102120210201202120102012021012102120210,

012021020102120121012010201202102010210121020102120210, 012021020102120210121021202102012021201210120102120210, 012021020121012021201210120102120210201021012102120210, 012021201020120210121021201210120212010210120102120210, 012021201020121012021201021202101210201210120102120210, 012021201021012010212021020102120102012021012102120210, 012021201210120102120210201202120121012021012102120210,

012021020102120121012010201202102012102120121020120210, 012021020102120210121021202102012102120121020102120210, 012021020121012021201210120102120210201202120102120210, 012021201020120210121021201210201202120121020102120210, 012021020102120121012010201202120102120210121020120210, 012021020102120210201202101201020120210121020102120210, 012021020121012021201210212021020102120121020102120210, 012021201020120210121021202102012021201021012102120210, 012021201020121012021201210201021202101202120102120210, 012021201021012010212021020120212012101202120102120210, 012021201210120210121021201021012102012021012102120210,

012021020102120121012010201202120121012021201020120210, 012021020102120210201202101201020121012021012102120210, 012021020121021201020120210201021012102120121020120210, 012021201020120210121021202102012021201210120102120210, 012021201020121021201020120210120102120121020102120210, 012021201021012102012101201021012102012021012102120210, 012021201210120210121021201210120102012021012102120210,

012021020102120121012010201210201021012021201020120210, 012021020102120210201202101201021012102120121020120210, 012021020121021201020120210201021202101202120102120210, 012021201020120210121021202102012102120121020102120210, 012021201020121021201020120210121021201021012102120210, 012021201021012102012101201021201210201021012102120210, 012021201210120210201021012102120102012021012102120210,

012021020102120121012010210121020102101202120102120210, 012021020102120210201202101201021202101202120102120210, 012021020121021201020121012010201202120121020102120210, 012021201020120210201021012010201202120121020102120210, 012021201020121021201020120210121021201210120102120210, 012021201021012102012101201021202102012021012102120210, 012021201210120210201210120212012102012021012102120210.

5 Code availability

The 54-Brinkhuis 952-triple can be verified using the code and accompanying script found at the website [15]. The program can be used to find special Brinkhuis triples for given values of n. While the code is fast for small values of n, e.g., n ≤ 35, it will take a very long time for n ≥ 54. In addition, the output files will require multiple terabytes of disk space.

A sample build and run of the script for n = 35 follows:

% script log Script started on Sat Apr 16 19:20:23 2016 % make runit N=35 clang -w -O3 brinkhuis.c -o brinkhuis clang -w -O3 brinkhuis2t1.c -o brinkhuis2t1 clang -w -O3 brinkhuis2t2.c -o brinkhuis2t2 ./doit 35 Success [ 1]: 01202102010212010201202120102120210 Success [ 2]: 01202102010212010201210120102120210 Success [ 3]: 01202102010212012101202120102120210 Success [ 4]: 01202102010212021012021201020120210 (palindromic) Success [ 5]: 01202102012101201020121020102120210 Success [ 6]: 01202102012101202120102012102120210 Success [ 7]: 01202102012101202120121020102120210 Success [ 8]: 01202102012102120210121020102120210 Success [ 9]: 01202120102012101201021012102120210 Success [ 10]: 01202120102012101202102012102120210 Success [ 11]: 01202120102012102010210120102120210 Success [ 12]: 01202120102012102010212012102120210 Success [ 13]: 01202120102012102120121020102120210 (palindromic) Success [ 14]: 01202120102101210201210120102120210 (palindromic) Success [ 15]: 01202120102120210120212012102120210 Success [ 16]: 01202120102120210201021012102120210 Success [ 17]: 01202120121020102120102012102120210 (palindromic) Success [ 18]: 01210201021012010212021012010201210 Success [ 19]: 01210201021012010212021012021201210 Success [ 20]: 01210201021012021020120212010201210 Success [ 21]: 01210201021012021201020121021201210 Success [ 22]: 01210201021012021201210212010201210 Success [ 23]: 01210201021012102120102012021201210 Success [ 24]: 01210201021012102120121012010201210 (palindromic) Success [ 25]: 01210201021012102120210201021201210 Success [ 26]: 01210201021201020120210121021201210 Success [ 27]: 01210201021201020120210201021201210 Success [ 28]: 01210201021201210120102012021201210 Success [ 29]: 01210201021201210212021012021201210 Success [ 30]: 01210201021202101201020121021201210 Success [ 31]: 01210201021202101201021012021201210 Success [ 32]: 01210201021202102010210121021201210 Success [ 33]: 01210201021202102012101201021201210 Success [ 34]: 01210212010201202101210201021201210 Success [ 35]: 01210212010201210120102012021201210 Success [ 36]: 01210212010201210120210121021201210 Success [ 37]: 01210212012101202120102012021201210 Success [ 38]: 01210212012102010212021012021201210 Success [ 39]: 01210212012102012021020121021201210 (palindromic) Success [ 40]: 01210212021020102120102012021201210 (palindromic) Done: a1=109, a1p= 9, a1n= 50; b1= 30, b1p= 4, b1n= 13 a2=142, a2p= 6, a2n= 68; b2= 43, b2p= 3, b2n= 20 Generated a1 and a2 files. 17 admissible words of length 35 read in admissible triples: 328 admissible triples found Generated t1. 23 admissible words of length 35 read in admissible triples: 483 admissible triples found Generated t2. % exit exit

References

[1] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.

[2] I. Bliznets, F. V. Fomin, M. Pilipczuk, and Y. Villanger, Largest chordal and interval subgraphs faster than 2^{n}, in H. L. Bodlaender and G. F. Italiano, eds., Algorithms—ESA 2013, Lect. Notes in Comp. Sci., Vol. 8125, Springer, 2013, pp. 193–204.

[3] I. M. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo, The maximum clique problem, in D.-Z. Du and P. M. Pardalos, eds., Handbook of Combinatorial Optimization, Supplement Vol. A, Kluwer Academic Publishers, 1999, pp. 1–74.

[4] F. J. Brandenburg, Uniformly growing kth power-free homomorphisms, Theoret. Comput. Sci. 23 (1983), 69–82.

[5] J. Brinkhuis, Nonrepetitive sequences on three symbols, Quart. J. Math. Oxford 34 (1983), 145–149.

[6] S. R. Bulò and M. Pelillo, A continuous characterization of maximal cliques in k-uniform hypergraphs, in V. Maniezzo, R. Battiti, and J.-P. Watson, eds., LION 2007 II, Lect. Notes in Comp. Sci., Vol. 5313, Springer, 2008, pp. 220–233.

[7] M. Crochemore, Sharp characterizations of squarefree morphisms, Theoret. Comput. Sci. 18 (1982), 221–226.

[8] S. B. Ekhad and D. Zeilberger, There are more than 2^{n}/17 n-letter ternary square-free words, J. Integer Seq. 1 (1998), Article 98.1.9. Errata,

https://cs.uwaterloo.ca/journals/JIS/zeile.html.

[9] S. Finch, Pattern-free word constants.

http://pauillac.inria.fr/algo/bsolve/constant/words/words.html.

[10] U. Grimm, Improved bounds on the number of ternary square-free words, J. Integer Sequences 4 (2001), Article 01.2.7.

[11] M. Leconte, A characterization of power-free morphisms, Theoret. Comput. Sci. 38 (1985), 117–122.

[12] M. Lothaire, Combinatorics on Words, Cambridge University Press, 1983.

[13] C. Richard and U. Grimm, On the entropy and letter frequencies of ternary square-free words, Electron. J. Combin. 11 (2004).

[14] M. Sollami, Computational Graph Theory, PhD thesis, Mathematics Department, University of Wyoming, Laramie, WY, 2013.

[15] M. Sollami, C. C. Douglas, and M. Liebmann, A 54-Brinkhuis 952-triple, 2016.

http://www.mgnet.org/~douglas/54-Brinkhuis_952-triple/.

[16] X. Sun, New lower bound on the number of ternary square-free words, J. Integer Sequences 6 (2003), Article 03.3.2.

2000 Mathematics Subject Classifications: Primary 57M15; Secondary 11Y55.

(Concerned with sequences \underline{A006156}, \underline{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.