BORDERS OF FIBONACCI STRINGS

L. J. Cummings^{∗} University of Waterloo D. Moore Curtin University of Technology J. Karhumäki^{†} Turku University

August 22, 1995

Abstract We determine all borders of the n\underline{th} Fibonacci string, f_{n}, n ≥ 3. In particular, we give two proofs that the longest border of f_{n} is f_{n−2}. One proof is independent of the Defect Theorem.

1 Introduction.

A Fibonacci string f_{n} is a string on a binary alphabet A = {a, b} defined by

f_{0} = b; f_{1} = a; f_{n} = f_{n−1}f_{n−2}, ∀ n ≥ 2.  (1)

Equivalently, the strings f_{n} may be defined as the orbit of a under the morphism h : A^{∗} → A^{∗} defined by

h : a → ab b → a.  (2)

∗Supported by the Natural Sciences and Engineering Research Council of Canada

†supported by grant no. 11181 of the Academy of Finland

An interesting facet of the structure of Fibonacci strings was shown by de Luca [8].

Proposition 1.1 (de Luca) For all n ≥ 3,

f_{n} = α_{n}d_{n}

where for each n, α_{n} is a palindrome and

d_{n} = \{ \begin{matrix}ab & if n is even \\ ba & if n is odd \end{matrix} .

Since f_{7} contains the cube (aba)^{3}, for each n ≥ 7, f_{n} contains at least this cube. But one of us has shown that no Fibonacci string contains a fourth power [6].

The well-known Fibonacci numbers can be defined as the lengths of the Fibonacci strings: F_{n} = |f_{n}|. The usual definition of these numbers is then immediate:

F_{n} = F_{n−1} + F_{n−2}, ∀ n ≥ 2.  (3)

It is well-known that F_{n} ∈ Ω(ϕ^{n}) where ϕ is the ”golden ratio” satisfying the quadratic equation ϕ^{2} = ϕ+1. It is less widely known that the Fibonacci numbers are the basis of a number system [2, 9].

Theorem 1.1 (Zeckendorf) Every positive integer n can be represented as a sum of distinct Fibonacci numbers

F_{n} = F_{k_{r}} + F_{k_{r−1}} + ⋯ + F_{1},  (4)

where k_{r} ≥ k_{r−1} ≥ ⋯ ≥ 1.

The representation (4) is unique if k_{i+1} ≥ k_{i} + 2, for all i.

A border of a string x is a substring which is both a prefix and a suffix of x. The longest border of a string x is often called the border of x. Arguably the empty string and x itself are borders of x but we exclude these trivial cases although it can be convenient to include the empty string as a border when initializing variables in an algorithm.

More formally, Definition 1.1 If for some integer b, 0 < b < n, a given string x of length n has a proper prefix b = x[1..b] that is equal to a suffix x[n−b+1..n], then b is said to be a border of x. If x has a border then its longest border is denoted by b^{∗}(x).

According to Definition 1.1 a string is never its own border. Clearly any border b of a string x is both a prefix and a suffix of b^{∗}(x). In notation: b ⪯ b^{∗}(x) and b^{∗}(x) ⪰ b. We let |x| denotes the length of the string x. We will show that if n ≥ 3 then b^{∗}(f_{n}) = f_{n−2}.

For example the string f_{6} = abaababaabaab has two borders: ab and abaab. Similarly, the string a^{n} has borders a, a^{2}, …, a^{n−1}, of which, for i = ⌈(n+1)/2⌉, the borders a^{i}, a^{i+1}, …, a^{n−1} overlap.

It has been shown that the longest border of an arbitrary string can be computed in Θ(n) time [4]. The notion of a border is central to the pattern matching algorithms of Knuth-Morris-Pratt and Boyer-Moore. For an excellent survey see [1].

From Definition 1.1 we note the relationship between the periods of arbitrary strings and their borders. Namely, the integer p is a period of a string x if p = n − |b| where b is a border of x. If b is the longest border of x, then p is traditionally called the period of x. Accordingly, by determining all borders of f_{n} we determine all periods of f_{n}.

2 The Defect Theorem and b^{∗}(f_{n})

The set of all strings with entries in an alphabet A is a free monoid or code denoted by A^{∗}. Any subset X of A^{∗} has an associated code, F(X), which is the intersection of all codes containing X. The Defect Theorem says that if X is not a code itself, then |F(X)| < |X|. For a proof and discussion of the history of the Defect Theorem see [5]. Two strings x, y ∈ A^{∗} are conjugate if there exist α, β ∈ A^{∗} such that

x = αβ  (5)
y = βα.  (6)

One consequence of the Defect Theorem is that two strings x, y are conjugate if and only if there is a third string z such that xz = zy. (See Proposition 1.3.4 of [7].)

Theorem 2.1 If n ≥ 3 then b^{∗}(f_{n}) = f_{n−2}.

First Proof. Clearly, f_{n−2} is a border of f_{n} since f_{n} = f_{n−2}f_{n−3}f_{n−2}. Therefore, f_{n−2} ⪯ b^{∗}(f_{n}) and b^{∗}(f_{n}) ⪰ f_{n−2}. Equivalently, there are binary strings x,y with 0 < |x| = |y| < |f_{n−1}| such that

f_{n−2}x = yf_{n−2}.

The Defect theorem implies that x and y are conjugate. (See Proposition 1.3.4 of [7].) Let α and β be elements of A^{∗} such that

x = αβ  (7)
y = βα  (8)
f_{n−2} = β(αβ)^{t}  (9)

for some t ≥ 0.

The proof falls into two cases:

Case 1. |x| ≤ |f_{n−3}|.

In this case, x is a prefix of f_{n−3} and f_{n−3} ⪯ f_{n−2}, which implies x = y since f_{n−2}x = yf_{n−2}. Therefore,αβ = βα. It now follows by Proposition 1.3.2 of [7] that α and β and hence f_{n−2} are powers of a single primitive string, say p. Since f_{n−3} ⪯ f_{n−2} and y^{r} ⪯ f_{n−3}^{r}, (7) implies that f_{n−3} is also a power of p. But then we have f_{k} is a power of p for all k ≥ n − 3, a contradiction.

Case 2. |x| > |f_{n−3}|.

If as in (7) f_{n−2} is of the form β(αβ)^{t} for some t ≥ 1 then we can proceed as in Case 1 since f_{n−2} ⪯ f_{n−3}f_{n−2}. (Note that f_{n−2} = f_{n−3}f_{n−4} and f_{n−4} ⪯ f_{n−2}.) Therefore, the only remaining case is when f_{n−2} = β. In this case, f_{n−1} ⪯ βαβ since x = αβand (βα)^{r} ⪯ f_{n−1}^{r} where |βα| < |f_{n−1}|. It now follows that there exists a string q and t ≥ 1 such that f_{n−1} = q^{t}. As in Case 1 this implies that every f_{k} is a power of q which is impossible.

3 Expansions and Borders

As noted before, for each n ≥ 3 it is clear that f_{n−2} is a border of f_{n} since

f_{n} = f_{n−2}f_{n−3}f_{n−2}.  (10)

Proposition 1.1 can be applied immediately to equation (10) to conclude that, since n−3 and n−2 are of differing parity, the prefix f_{n−2}f_{n−3} cannot be a border of f_{n}. We apply a similiar argument after each uniform expansion of (10) by the rules

f_{k} → f_{k−2}f_{k−3}f_{k−2}
f_{2} → f_{1}f_{0}
f_{1} → f_{1}  (11)
f_{0} → f_{0}.

For example, at level 2 of the expansion f_{n−2}f_{n−3}f_{n−2} becomes

f_{n−4}f_{n−5}f_{n−4}f_{n−5}f_{n−6}f_{n−5}f_{n−4}f_{n−5}f_{n−4}.  (12)

The expansion terminates when only f_{0}’s and f_{1}’s remain. At level k of the expansion with (11) we have

f_{n−2k}f_{n−2k−1}f_{n−2k}⋯ f_{n−2k}f_{n−2k−1}f_{n−2k}.  (13)

By symmetry, each such expansion is a palindrome over an alphabet of appropriate f_{n}. Therefore, each prefix consisting of, say, k consecutive f_{j}’s is of the same length as the corresponding suffix of k consecutive f_{j}’s. In the level 2 expansion (12), no prefix of f_{j}’s ending in f_{n−5} can be a border of f_{n}. By induction, we see that at each step of the expansion, each f_{k} is adjacent only to f_{k+1} or to f_{k−1} on either the left or the right. When, say, f_{k−1}f_{k} occurs in the expansion, it must be preceded by either f_{k} or f_{k−2}. In the second case, necessarily f_{k−1}f_{k−2}f_{k−1}f_{k} must occur. This follows because the definition (11) precludes four consecutive f_{i}’s with strictly increasing (or strictly decreasing) indices.

For each f_{n−j} in some level of the expansion (11) there is a potential border

f_{n−2k}f_{n−2k−1}f_{n−2k}⋯ f_{n−j} = f_{n−j}⋯ f_{n−2k}f_{n−2k−1}f_{n−2k}. (14)

Since f_{n−2} is a border of f_{n}, to show f_{n−2} is the longest border we need only rule out potential borders (14) which end to the right of the f_{k} which make up f_{n−2}.

If n−j is even and n is odd then n−2k is odd and (14) cannot be a border since f_{n−j} must end in ab while f_{n−2k} ends in ba by 1.1. Similiarly, if n−j is odd and n is even then n−2k is even and (14) cannot be a border since f_{n−j} must end in ba while f_{n−2} ends in ab. Consequently, at any level of expansion we need only consider those potential borders (14) for which n−j and n−2k have the same parity.

Lemma 3.1 If a prefix f_{n−2k}f_{n−2k−1}f_{n−2k}⋯ f_{n−j} of f_{n} has the property that it ends in a square of the form f_{i}^{2} = f_{i}f_{i} for some i then it is not a border of f_{n}.

Proof. If n and i are not both odd or both even then the last element of f_{i} cannot match the last element of f_{n} by (1.1). Accordingly, we need only consider the cases when i or n are both odd or both even.

Consider the successive expansions (13). The list of final f_{i}’s from each level of the expansion is:

f_{n−2}, f_{n−4}, f_{n−6}, ⋯, f_{n−j}.  (15)

If n is odd (even) then every odd (even) integer less than n appears in the list of indices in (15). Accordingly, given a prefix ending in a square f_{i}^{2} = f_{i}f_{i}, some level of expansion will also end in f_{i}. But by (11) f_{i} must be preceded by f_{i−1} and by (1.1), f_{i−1} and f_{i} have differing final entries.

Theorem 3.1 For all n ≥ 3,

b^{∗}(f_{n}) = f_{n−2}.

Proof. We argue that any potential border of the form

f_{n−2k}f_{n−2k−1}f_{n−2k}⋯ f_{n−j}

ends in exactly one of the following:

i) f_{n−j+1}f_{n−j}
ii) f_{n−j−1}f_{n−j−2}f_{n−j−1}f_{n−j}

iii) f_{n−j}f_{n−j−1}f_{n−j}.

For, as previously noted, each f_{k} is preceded only by f_{k+1} or f_{k−1}. If f_{n−j} is preceded by f_{n−j+1} = f_{n−2k+1}as in i) then (1.1) implies (14) is not a border because the expansion at level k always terminates in f_{n−2k}f_{n−2k−1}f_{n−2k}. As a consequence, we may always suppose that f_{n−j} is preceded by f_{n−j−1}. In the same way, f_{n−j−1} is always preceded by f_{n−j} or f_{n−j−2}. If f_{n−j−1} is preceded by f_{n−j−2} as in ii) then (14) is not a border because the expansion at level k always terminates in f_{n−2k}f_{n−2k−1}f_{n−2k}.

Consider iii). Either f_{n−j−1}or f_{n−j+1} is the immediate predecessor of this substring. But, if the potential border (14) is

f_{n−j−1}f_{n−j}f_{n−j−1}f_{n−j} = (f_{n−j−1}f_{n−j})^{2}  (16)

then Lemma 3.1 yields a contradiction.

In the same way, if the immediate predecessor of iii) is f_{n−j+1} then the potential border (14) ends in

f_{n−j+1}f_{n−j}f_{n−j−1}f_{n−j} = f_{n−j}f_{n−j−1}f_{n−j}f_{n−j−1}f_{n−j}mber
= f_{n−j}(f_{n−j−1}f_{n−j})^{2}  (17)

again contradicting Lemma 3.1.

The above arguments rule out any border of the form f_{n−2}u of f_{n}, where u is a substring of length not more than F_{n} − F_{n−2}, since iterations of the expansion (11) terminate when every f_{j} has become f_{1} = a or f_{0} = b.

This completes the proof.

Theorem 3.2 For all n ≥ 3, the borders of f_{n} are

f_{n−2}, f_{n−4}, ⋯, f_{p}  (18)

where k = 2 if n is even and 1 otherwise.

Proof. By Theorem 3.1 f_{n−2}is the longest border of f_{n}. In the successive expansions of (11) we see that each of the Fibonacci strings in (18) are borders of f_{n}. Further, no Fibonacci string of the form f_{n−(2k+1)} can be a border since, although each such is a prefix, it would then need to be a suffix of f_{n} but f_{n−2k} is also a suffix of f_{n} for all appropriate k, and f_{n−(2k+1)}, f_{n−2k} have different endings by (1.1).

References

[1] A. Aho, Pattern Matching in Strings, Handbook of Theoretical Computer Science, Elsevier, 1990, 255-300.

[2] J. Berstel, Fibonacci words — a survey, Book of L, Springer-Verlag, 1986, 13-27.

[3] A. Ehrenfeucht and D. M. Silberger, Periodicity and unbordered segments of words, Discrete Mathematics, 26(1979), 101-109.

[4] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms Addison-Wesley, 1974, 330-334.

[5] J. Berstel, D. Perrin, J.F. Perrot, and A. Restivo, Sur le théorème du défault Journal of Algebra, 60(1979), 169-180.

[6] J. Karhumäki, On cube-free ω-words generated by binary morphisms, Discrete Applied Mathematics, 5(1983), 279-297.

[7] M. Lothaire, Combinatorics on Words Addison-Wesley, 1983.

[8] A. de Luca, A combinatorial property of Fibonacci words, Information Processing Letters, 12(1981), 193-195.

[9] E. Zeckendorf, Reprèsentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Royale des Sciences de Liége, 1972, 179-182.