{'fraction_non_alphanumeric': 0.0620793355291422, 'fraction_numerical': 0.03644565373048833, 'mean_word_length': 3.2221886336154775, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Binary words containing infinitely many overlaps

We characterize the squares occurring in infinite overlap-free binary words and construct various alpha power-free binary words containing infinitely many overlaps.


Introduction
If α is a rational number, a word w is an α power if there exists words x and x ′ , with x ′ a prefix of x, such that w = x n x ′ and α = n + |x ′ |/|x|. We refer to |x| as a period of w. An α + power is a word that is a β power for some β > α. A word is α power-free (resp. α + power-free) if none of its subwords is an α power (resp. α + power). A 2 power is called a square; a 2 + power is called an overlap.
Thue [17] constructed an infinite overlap-free binary word; however, Dekking [7] showed that any such infinite word must contain arbitrarily large squares. Shelton and Soni [16] characterized the overlap-free squares, but it is not hard to show that there are some overlapfree squares, such as 00110011, that cannot occur in an infinite overlap-free binary word. In this paper, we characterize those overlap-free squares that do occur in infinite overlap-free binary words.
Shur [15] considered the bi-infinite overlap-free and 7/3 power-free binary words and showed that these classes of words were identical. There have been several subsequent papers [1,9,10,13] that have shown various similarities between the classes of overlap-free binary words and 7/3 power-free binary words. Here we contrast the two classes of words by showing that there exist one-sided infinite 7/3 power-free binary words containing infinitely many overlaps. More generally, we show that for any real number α > 2 there exists a real number β arbitrarily close to α such that there exists an infinite β + power-free binary word containing infinitely many β powers.
All binary words considered in the sequel will be over the alphabet {0, 1}. We therefore use the notation w to denote the binary complement of w; that is, the word obtained from w by replacing 0 with 1 and 1 with 0.

Properties of the Thue-Morse morphism
In this section we present some useful properties of the Thue-Morse morphism; i.e., the morphism µ defined by µ(0) = 01 and µ(1) = 10. It is well-known [11,17] that the Thue- is overlap-free.
The following property of µ is easy to verify. Lemma 1. Let x and y be binary words. Then x is a prefix (resp. suffix) of y if and only if µ(x) is a prefix (resp. suffix) of µ(y).
Theorem 2 (Shur). Let w be a binary word and let α > 2 be a real number. Then w is α power-free if and only if µ(w) is α power-free.
The following sharper version of one direction of this theorem (implicit in [9]) is also useful.
Karhumäki and Shallit [9] gave the following generalization of the factorization theorem of Restivo and Salemi [14]. The extension to infinite words is clear.
Theorem 5 (Pansiot; Brlek). The set of squares in t is exactly the set A.
We can use this result to prove the following.
Proposition 6. For any position i, there is at most one square in t beginning at position i.
Proof. Suppose to the contrary that there exist distinct squares x and y that begin at position i. Without loss of generality, suppose that x and y begin with 0. Then by Theorem 5, x = µ p (u) and y = µ q (v), for some p, q and u, v ∈ {00, 010010}. Suppose p ≤ q and let w = µ q−p (v). By Lemma 1, either u is a proper prefix of w or w is a proper prefix of u, neither of which is possible for any choice of u, v ∈ {00, 010010}.
The set A does not contain all possible overlap-free squares. Shelton and Soni [16] characterized the overlap-free squares (the result is also attributed to Thue in [4]).
Theorem 7 (Shelton and Soni). The overlap-free binary squares are the conjugates of the words in A.
Some overlap-free squares cannot occur in any infinite overlap-free binary word, as the following lemma shows. Proof. It is easy to see that x = uvvuvv for some u, v ∈ {0, 1} * , where u and v begin with different letters. Thus one of uvvuvva or vva is an overlap.
We can characterize the squares that can occur in an infinite overlap-free binary word.
Theorem 9. The set of squares that can occur in an infinite overlap-free binary word is A ∪ B. Furthermore, if w is an infinite overlap-free binary word containing a subword x ∈ B, then w begins with x and there are no other occurrences of x in w.
Proof. Let w be an infinite overlap-free binary word beginning with a square yy ∈ A ∪ B. Suppose further that yy is a smallest such square that can be extended to an infinite overlapfree word. If |y| ≤ 3, then yy ∈ A ∪ B is one of 011011 or 100100, neither of which can be extended to an infinite overlap-free word by Lemma 8. We assume then that |y| > 3. Since, by Theorem 7, yy is a conjugate of a word in A, we have two cases.
Case 1: yy = µ(zz) for some z ∈ {0, 1} * . By Theorem 4, w = µ(zzw ′ ) for some infinite w ′ , where zzw ′ is overlap-free. Thus zz is a smaller square not in A∪B that can be extended to an infinite overlap-free word, contrary to our assumption.
Since both cases lead to a contradiction, our assumption that yy ∈ A ∪ B must be false.
To see that each word in A ∪ B does occur in some infinite overlap-free binary word, note that Allouche, Currie, and Shallit [2] have shown that the word s = 001001t is overlap-free. Now consider the words µ k (s) and µ k (s), which are overlap-free for all k ≥ 0.
Finally, to see that any occurrence of x ∈ B in w must occur at the beginning of w, we note that by an argument similar to that used in Lemma 8, ax contains an overlap for all a ∈ {0, 1}, and so x occurs at the beginning of w.

Words containing infinitely many overlaps
In this section we construct various infinite α power-free binary words containing infinitely many overlaps. We begin by considering the infinite 7/3 power-free binary words.
Proposition 10. For all p ≥ 1, an infinite 7/3 power-free word contains only finitely many occurrences of overlaps with period p.
Proof. Let x be an infinite 7/3 power-free word containing infinitely many overlaps with period p. Let k ≥ 0 be the smallest integer satisfying p ≤ 3 · 2 k . Suppose x contains an overlap w with period p starting in a position ≥ 2 k+1 . Then by Theorem 4, we can write where each u i ∈ {ǫ, 0, 1, 00, 11}. The overlap w occurs as a subword of µ k (y). By Lemma 3, y contains an overlap with period p/2 k ≤ 3. But any overlap with period ≤ 3 contains a 7/3 power. Thus, x contains a 7/3 power, a contradiction.
The following theorem provides a striking contrast to Shur's result [15] that the bi-infinite 7/3 power-free words are overlap-free.
Theorem 11. There exists a 7/3 power-free binary word containing infinitely many overlaps.
Proof. We define the following sequence of words: A 0 = 00 and A n+1 = 0µ 2 (A n ), n ≥ 0. The first few terms in this sequence are We first show that in the limit as n → ∞, this sequence converges to an infinite word a. It suffices to show that for all n, A n is a prefix of A n+1 . We proceed by induction on n. Certainly, A 0 = 00 is a prefix of A 1 = 0µ 2 (00) = 001100110. Now A n = 0µ 2 (A n−1 ), A n+1 = 0µ 2 (A n ), and by induction, A n−1 is a prefix of A n . Applying Lemma 1, we see that A n is a prefix of A n+1 , as required.
Note that for all n, A n+1 contains µ 2n (A 1 ) as a subword. Since A 1 is an overlap with period 4, µ 2n (A 1 ) contains 2 2n overlaps with period 2 2n+2 . Thus, a contains infinitely many overlaps.
We must show that a does not contain a 7/3 power. It suffices to show that A n does not contain a 7/3 power for all n ≥ 0. Again, we proceed by induction on n. Clearly, A 0 = 00 does not contain a 7/3 power. Consider A n+1 = 0µ 2 (A n ). By induction, A n is 7/3 powerfree, and by Theorem 2, so is µ 2 (A n ). Thus, if A n+1 contains a 7/3 power, such a 7/3 power must occur as a prefix of A n+1 . Note that A n+1 begins with 00110011. The word 00110011 cannot occur anywhere else in A n+1 , as that would imply that A n+1 contained a cube 000 or 111, or the 5/2 power 1001100110. If A n+1 were to begin with a 7/3 power with period ≥ 8, it would contain two occurrences of 00110011, contradicting our earlier observation. We conclude that the period of any such 7/3 power is less than 8. Checking that no such 7/3 power exists is now a finite check and is left to the reader.
In fact, we can prove the following stronger statement.
Theorem 12. There exist uncountably many 7/3 power-free binary words containing infinitely many overlaps.
Note that g b (0) always starts with a 0, so that for any finite binary words p and b, g p (0) is always a prefix of g pb (0). Since g 0 (0) is not a prefix of g 1 (0), g p0 (0) is not a prefix of g p1 (0) for any p, so that distinct b give distinct words. Given an infinite binary sequence b = b 1 b 2 b 3 · · · where the b i ∈ {0, 1}, define an infinite binary sequence w b to be the limit of g ǫ (00), g b 1 (00), g b 1 b 2 (00), g b 1 b 2 b 3 (00), . . . By an earlier argument, each w b is 7/3 power-free. Since g 1 (00) = 001100110 is an overlap, g b1 (00) = g b (001100110) ends with an overlap for any finite word b. Thus, each 1 in b introduces an overlap in w b . Since uncountably many binary sequences contain infinitely many 1's, uncountably many of the w b are 7/3 power-free words containing infinitely many overlaps.
Next, we show that the sequence a constructed in the proof of Theorem 11 is an automatic sequence (in the sense of [3]). The word h ω (0) can thus be parsed in terms of a new morphism f : The parsing in terms of f works as follows: If we write h ω (0) = 0w, then w = f (0w). It is useful to rewrite this relation in terms of the finite words h n (0). For non-negative integer n let x n be the unique letter such that h n (0)x n is a prefix of h ω (0). Thus x 0 = 1, x 1 = 2, etc. We then have h n (0)x n = 0f (h n−1 (0)), n ≥ 1.
The result of Theorem 11 can be strengthened even further.
Theorem 14. For every real number α > 2 there exists a real number β arbitrarily close to α, such that there is an infinite β + power-free binary word containing infinitely many β powers.
Proof. Let s ≥ 3 be a positive integer, and let r = ⌊α + 1⌋. Let t be the largest positive integer such that r − t/2 s > α, and such that the word obtained by removing a prefix of length t from µ s (0) begins with 00. Let β = r − t/2 s . Since α ≥ r − 1, we have t < 2 s . Also, µ 3 (0) = 01101001 and µ 3 (1) = 10010110 are of length 8, and both contain 00 as a subword; it follows that |α − β| ≤ 8/2 s , so that by choosing large enough s, β can be made arbitrarily close to α. We construct sequences of words A n , B n and C n . Define C 0 = 00. For each n ≥ 0: 1. Let A n = 0 r−2 C n .
3. Remove the first t letters from B n to obtain a new word C n+1 beginning with 00.
Since each A n begins with the r power 0 r , each B n = µ s (A n ) begins with an r power of period 2 s . Removing the first t letters ensures that C n+1 commences with an (r2 s − t)/2 s power, viz., a β power. The limit of the C n gives the desired infinite word. Let us check that this limit exists: Let w be the word consisting of the first t letters of µ s (0). Since all the A n commence with 0 by construction, all the B n commence with µ s (0), and hence with w. This means that B n = wC n+1 for each n.
We show that A n is always a prefix of A n+1 by induction. Certainly A 0 is a prefix of A 1 . Assume that A n−1 is a prefix of A n . Since A n = 0 r−2 C n and A n+1 = 0 r−2 C n+1 , A n is a prefix of A n+1 if C n is a prefix of C n+1 . Since B n−1 = wC n and B n = wC n+1 , C n is a prefix of C n+1 if B n−1 is a prefix of B n . By Lemma 1, B n−1 is a prefix of B n if A n−1 is a prefix of A n , which is our inductive assumption. We conclude that A n is a prefix of A n+1 .
It follows that C n is a prefix of C n+1 for n ≥ 0, so that the limit of the C n exists. It will thus suffice to prove the following claim: Claim: The A n , B n and C n satisfy the following: 1. The word C n contains no β + powers.
2. The only β + power in A n is 0 r .
3. Any β + powers in B n appear only in the prefix µ s (0 r ).
Certainly C 0 contains no β + powers, and since β > r − 1, the only β + power in A 0 is 0 r . Suppose then that the claim holds for A n and C n . Now suppose that B n = µ s (0 r−2 )µ s (C n ) contains a β + power u with period p. Since C n contains no β + powers, Theorem 2 ensures that µ s (C n ) contains no β + powers. We can therefore write B n = xuy where |x| < |µ s (0 r−2 )|. In other words, u overlaps µ s (0 r−2 ) from the right. By Theorem 3, the preimage of B n under µ, i.e., µ s−1 (A n ), contains a β + power of length at least |u|/2 and period p/2. In fact, iterating this argument, A n contains a β + power of period p/2 s of length at least |u|/2 s . Since the only β + power in A n is 0 r , with period 1, we see that p/2 s = 1, whence p = 2 s and |u| ≤ r2 s .
Recall that B n has a prefix µ s (0 r ) which also has period 2 s , and that this prefix is overlapped by u. It follows that all of xu is a β + power with period p = 2 s . However, as just argued, this means that |xu| ≤ r2 s = |µ s (0 r )|, so that u is contained in µ s (0 r ) and part 3 of our claim holds for B n . We now show that parts 1 and 2 hold for C n+1 and A n+1 respectively, and the truth of our claim will follow by induction.
Part 1 follows immediately from part 3. Now suppose that A n+1 contains a β + power u. Recall that A n+1 = 0 r−2 C n+1 , and C n+1 begins with 00, but contains no β + powers. It follows that u is not a subword of C n+1 . Therefore, 000 must be a prefix of u. If u = 0 q for some integer q, then q ≤ r by the construction of A n+1 , and r ≥ q > β > α > r − 1.
This implies that q = r, and u = 0 r , as claimed. If we cannot write u = 0 q , then |u| 1 ≥ 1. Because u is a 2 + power, 000 must appear twice in u with a 1 lying somewhere between the two appearances. This implies that 000 is a subword of C n+1 , and hence of B n = µ s (A n ). However, no word of the form µ(w) contains 000. This is a contradiction.