Printer Friendly

Anti-power j-fixes of the Thue-Morse word.

1 Introduction

A finite word is called a k-power if it is of the form [w.sup.k] for some word w. A particularly famous consequence of the study of k-powers is Axel Thue's 1912 paper Thue (1912), which introduces an infinite binary word that does not contain any 3-powers as subwords. This word has since caught the interest of numerous academicians Allouche and Cohen (1985); Allouche and Shallit (1999); Brlek (1989); Bugeaud and Han (2014); Cooper and Dutle (2013); Defant (2017); Dejean (1972); Mahler (1929); Narayanan (2020); Palacios-Huerta (2012) spanning the fields of combinatorics, analytic number theory Allouche and Cohen (1985), game theory Cooper and Dutle (2013), and economics Palacios-Huerta (2012). It is now known as the Thue-Morse word.

Definition 1.1 Let A0 = 0. For each nonnegative integer n, let [B.sub.n] = [A.sub.n] be the Boolean complement of [A.sub.n], and let [A.sub.n+1] = [A.sub.n][B.sub.n]. The Thue-Morse word t is defined as

[mathematical expression not reproducible]

As a natural adaptation of the Ramsey-type notion of a k-power, Fici, Restivo, Silva, and Zamboni Fici et al. (2018) introduce the anti-Ramsey-type notion of a k-anti-power. A k-anti-power is a word w of the form w = [w.sup.(1)][w.sup.(2)] * * * [w.sup.(k)], where [w.sup.(1)], [w.sup.(2)],..., [w.sup.(k)] are distinct words of the same length. For example, 110100 is a 3-anti-power, while 101011 is not. Since the introduction of this notion in 2016, k-anti-powers have received much attention Badkobeh et al. (2018); Burcroff (2018); Defant (2017); Narayanan (2020).

As their main result, Fici et al. show that every infinite word contains powers of any order or anti-powers of any order. In doing so, they define the following set, which corresponds to an infinite word w and a positive integer k:

AP(w, k) = {m [member of] [Z.sup.+] | [w.sub.1][w.sub.2] * * * [w.sub.km] is a k-anti-power}.

Here, [w.sub.i] indicates the i-th letter of the infinite word w. Such subwords (i.e. those starting from the first index of w) are called prefixes of w. In Defant (2017), Defant introduces the generalized definition

[AP.sub.j](w, k) = {m [member of] Z+ | [w.sub.j+1][w.sub.j+2] * * * [w.sub.j+km] is a k-anti-power},

himself studying [AP.sub.0](t, k) = AP(t, k). Subwords beginning at the (j + 1)-st index of a word w will be referred to as j-fixes of w. An easy consequence of (Fici et al., 2018, Theorem 6) is that [AP.sub.j] (t, k) is nonempty for any nonnegative integer j and all positive integers k. Therefore, we can make the following definition:

Definition 1.2 Let [[gamma].sub.j](k) = min([AP.sub.j](t,k)).

For j = 0, it is the case that m [member of] [AP.sub.0](t, k) if and only if 2m [member of] [AP.sub.0](t, k) (see Remark 2.1). As a consequence, the only interesting elements of [AP.sub.0](t, k) are those that are odd. Thus, Defant Defant (2017) makes the following definition for j = 0 (which we have written in terms of arbitrary j [member of] [Z.sup.[greater than or equal to]0]):

Definition 1.3 Let [F.sub.j] (k) denote the set of odd positive integers m such that the j-fix oft of length km is a k-anti-power. Let [[GAMMA].sub.j](k) = sup((2[Z.sup.+] - 1) \[F.sub.j](k)).

For sufficiently large k, [[GAMMA].sub.j](k) is a well-defined odd positive integer (see Remark 4.8). However, if j [not equal to] 0, it is not necessarily the case that m [member of] [AP.sub.j](t, k) if and only if 2m [member of] [AP.sub.j](t, k). For example, 4 [member of] [AP.sub.2] (t, 3), whereas 2 [member of] [AP.sub.2] (t, 3). However, we will later prove that the statement "m [member of] [AP.sub.j] (t, k) if and only if 2m [member of] [AP.sub.j](t, k)" holds for sufficiently large m (see Corollary 4.4), so it still makes sense to define [[GAMMA].sub.j] (t, k) in this way. See Section 4 for further motivation for this definition.

Remark 1.4 It is immediate from Definition 1.3 that [F.sub.j](1) [[contains].bar] [F.sub.j](2) [[contains].bar] [F.sub.j] (3) [[contains].bar] * * * for any j [member of] [Z.sup.[greater than or equal to]0]. It follows that [[gamma].sub.j](1) [less than or equal to] [[gamma].sub.j](2) [less than or equal to] [[gamma].sub.j](3) [less than or equal to] *** and that [[GAMMA].sub.j](k) is nondecreasing when it is finite.

As a means to understanding [[gamma].sub.j](k) and [[GAMMA].sub.j](k), it will often be useful to consider the following related function:

Definition 1.5 For a positive integer m, let [R.sub.j](m) denote the smallest positive integer k such that the j-fix of t of length km is not a k-anti-power.

A simple application of the Pigeonhole Principle gives that [R.sub.j](m) [less than or equal to] [2.sup.m] + 1. However, Defant Defant (2017) and Narayanan Narayanan (2020) prove significantly better bounds on [R.sub.0](m), showing it grows linearly in m. Using these bounds, Defant Defant (2017) is ultimately able to show the following:

Theorem 1.6 (Defant (2017))

[mathematical expression not reproducible]

* [mathematical expression not reproducible]

* [mathematical expression not reproducible]

* [mathematical expression not reproducible]

Narayanan Narayanan (2020) improves the above asymptotic bounds in the following way: Theorem 1.7 (Narayanan (2020))

* [mathematical expression not reproducible]

* [mathematical expression not reproducible]

The goal of this paper is to demonstrate similarly good bounds on the asymptotic growth of [[gamma].sub.j](k) and [[GAMMA].sub.j](k) for general j. To do so, we will roughly follow the outline of Defant's paper Defant (2017), generalizing his bounds for [R.sub.0](m) to bounds for [R.sub.j] (m); this will in turn allow us to prove that [[gamma].sub.j](k) and [[GAMMA].sub.j](k) grow linearly in k. Specifically, we aim to prove the following:

* [mathematical expression not reproducible]

* [mathematical expression not reproducible]

* [mathematical expression not reproducible]

* [mathematical expression not reproducible]

Remark 1.8 Note that we follow the methods of Defant Defant (2017) rather than those of Narayanan Narayanan (2020), which seem more difficult to generalize to arbitrary j [member of] [Z.sup.[greater than or equal to]0].

In Section 2, we cover preliminary results relating to the Thue-Morse word. In Section 3 (resp. Section 4), we prove the aforementioned asymptotic bounds on [[gamma].sub.j](k)/k (resp. [[GAMMA].sub.j](k)/k).

2 Properties of the Thue-Morse Word

In this section, we will discuss some properties of the Thue-Morse word t = [t.sub.1][t.sub.2][t.sub.3] * * * that will be of use throughout the remainder of the paper. It is well known that the i-th letter [t.sub.i] of the Thue-Morse word has the same parity as the number of 1's in the binary expansion of i - 1. In his 1912 paper Thue (1912), Thue proved that t is overlap-free, meaning that if x and y are finite words (with x nonempty), then t does not contain xyxyx as a subword. Taking y to be empty shows that t does not contain any 3-powers as subwords.

Let [W.sub.1] and [W.sub.2] be sets of words. We say a function f : [W.sub.1] [right arrow] [W.sub.2] is a morphism if f(xy) = f(x)f(y) for all words x, y [member of] [W.sub.1]. We will write [A.sup.[less than or equal to][omega]] to refer to the set of all words over an alphabet A. Using this notation, let [micro] : [{0,1}.sup.[less than or equal to][omega]] [right arrow] [{01,10}.sup.[less than or equal to][omega]] be the morphism uniquely defined by [micro](0) = 01 and [micro](1) = 10. Similarly, let [sigma] : [{01,10}.sup.[less than or equal to][omega]] [{0,1}.sup.[less than or equal to][omega]] be the morphism uniquely defined by [sigma](01) = 0 and [sigma](10) = 1. The Thue-Morse word t and its Boolean complement t are the unique one-sided infinite words over the alphabet {0,1} that are fixed by [micro]. Similarly, t and t, as viewed over the alphabet {01,10}, are the unique one-sided infinite words fixed by [sigma]. The observation that [micro](t) = t allows us to view t as a word over the alphabet {01,10}. More generally, if we recall the definitions of [A.sub.n] and [B.sub.n] from Definition 1.1 and note the equalities [A.sub.n] = [[micro].sup.n](0) and [B.sub.n] = [[micro].sup.n](1), we can view t as a word over the alphabet {[A.sub.n],[B.sub.n]}.

Remark 2.1 Using that [micro](t) = t and [sigma](t) = t, it is straightforward to see that m [member of] [AP.sub.0](t, k) if and only if 2m [member of] [AP.sub.0](t, k).

We will follow Defant Defant (2017) in using the notation ([alpha], [beta]) = [t.sub.[alpha]][t.sub.[alpha]+1] * * * [t.sub.[beta]] for any positive integers [alpha], [beta] with [alpha] < [beta]. We are now in a position to establish some preliminary results relating to t.

Fact 2.2 For any positive integers n andr, ([2.sup.n]r + 1, [2.sup.n](r + 1)} = [[micro].sup.n]([t.sub.r+1]).

Lemma 2.3 For m [member of] Z+, [t.sub.2m]+1 [not equal to] [t.sub.2m+2].

[t.sub.2m+1][t.sub.2m+2] 01. Ineithe r case, [t.sub.2m+1] = [t.sub.2m+2]. []

Lemma 2.4 Let k [member of] [Z.sup.+]. Then [t.sub.2k+1][t.sub.2k+2] = [t.sub.4k+1][t.sub.4k+2].

Proof: Fix some k [member of] Z+ and suppose that [t.sub.k+1] = 1. (The case in which [t.sub.k+1] = 0 can be done s im i larly.) Note that [micro]([t.sub.k+1]) = [2.sub.k+1][t.sub.2k+2] =. Sim i larly, [micro]( [t.sub.2k+1]) = [t.sub.4k+1] [t.sub.4k+2] =. So we have that [t.sub.2k+1][t.sub.2k+2] 10 = [t.sub.4k+1][t.sub.4k+2], asdesi red. []

3 Asymptotics for [[gamma].sub.j](k)

In this section, we prove that [mathematical expression not reproducible] and [mathematical expression not reproducible]. These asymptotic results relate to a conjecture from a recent paper of Berger and DefantBerger and Defant (2020), which states that for any sufficiently well-behaved aperiodic, morphic word W (see Berger and Defant (2020) for the relevant definitions), there exists a constant C = C(W) such that for all integers j [greater than or equal to] 0 and k [greater than or equal to] 1, W contains a k-anti-power j -fix of length at most [Ck.sup.2]. The lower bounds proved in this section indicate that the quadratic upper bound in this conjecture is the best that could be true in general. Our upper bounds obtained in the next section also prove an effective version of this conjecture in the case of W = t (which Berger and Defant do not obtain).

Many of the statements proved in this section for general j have j = 0 analogues in Defant (2017). Moreover, many of the proofs of these general statements closely follow the corresponding proofs in Defant (2017). In these cases, we highlight the key differences between the corresponding proofs and refer the reader to Defant (2017) for the remaining details.

3.1 Lower Bounds for [[gamma].sub.j](k)/k

In this subsection, we present a series of lemmas that collectively establish an upper bound for [R.sub.j] (m) for anyintegerm [greater than or equal to] 2. This will allow us to establish lower bounds for [mathematical expression not reproducible] and limsup([[gamma].sub.j](k)/k).

We begin with three lemmas that we will apply in the proofs of many of the lemmas later in this subsection.

Lemma 3.1 Let m,j [member of] [Z.sup.[greater than or equal to]0] with m [greater than or equal to] 2, and let l = [[log.sub.2](m+j)]. For any s,a [member of] [Z.sup.+], there exists a nonnegative integer r such that

[2.sup.l](s-1) + 1 [less than or equal to]rm+j + 1 <(r + 1)m+j <[2.sup.l](s + a).

Proof: Fix some s, a [member of] [Z.sup.+]. Note that

[mathematical expression not reproducible] (1)

Since (r + 1)m + j - (rm + j) = m for any integer r, it follows that there exists r G Z satisfying

[mathematical expression not reproducible] (2)

Moreover, we can always choose r to be nonnegative; to verify this fact, it suffices to check that r = 0 satisfies (2) when s = 1:

[mathematical expression not reproducible] (3)

When s [greater than or equal to] 2, any integer r satisfying (2) is clearly positive. []

Lemma 3.2 (cf. (Defant, 2017, Lemma 12)) Let j [member of] [Z.sup.[greater than or equal to]0], m [member of] [Z.sup.+], and l = [[log.sub.2](m + j)]. If [mathematical expression not reproducible], then [t.sub.m+1][t.sub.m+2] = 11 and[t.sub.2m+1][t.sub.2m+2] = 10.

Proof: Suppose [R.sub.j](m) > [2.sup.l] + 1. Let [w.sub.0] = (j + 1, m + j), [w.sub.1] = {[2.sup.l-1]m + j + 1, ([2.sup.l-1] + 1)m + j), and [w.sub.2] = {[2.sup.l]m+j + 1,([2.sup.l] + 1)m+j). By our assumption that [R.sub.j](m) > [2.sup.l] + 1, we have that [w.sub.0], [w.sub.1], and [w.sub.2] are distinct. Notice that for each n [member of] {0,1,2}, the word wn is a j-fix of

[mathematical expression not reproducible] (4)

It follows that [t.sub.1][t.sub.2], [t.sub.m+1][t.sub.m+2], and [t.sub.2m+1][t.sub.2m+2] are dis tinct. Note that [t.sub.1][t.sub.2] = 01 and that [t.sub.2m+1] [not equal to] [t.sub.2m+2] (by Lemma 2.3); hence, [t.sub.2m+1][t.sub.2m+2] = 10. Therefore, [micro]([t.sub.m+1]) = [t.sub.2m+1][t.sub.2m+2] = 10, which implies that [t.sub.m+1] = 1. Consequently, [t.sub.m+1][t.sub.m+2] = 11. []

Lemma 3.3 (cf. (Defant, 2017, Lemma 13)) Let j,m [member of] [Z.sup.[greater than or equal to]0] with m [greater than or equal to] 2, and let l = [[log.sub.2](m + j)]. Suppose there exists s [member of] [Z.sup.+] such that [t.sub.s][t.sub.s+1] = [t.sub.m+s][t.sub.m+s+1]. Then

[mathematical expression not reproducible]

Proof: This proof follows from a straightforward modification of the proof of (Defant, 2017, Lemma 13) and an application of Lemma 3.1 with a = 1. []

Now that we have established the preceding preliminary results, we are ready to derive upper bounds for [R.sub.j](m) for all integers m [greater than or equal to] 2. We consider the cases m [equivalent to] 0 (mod 2), m [equivalent to] 1 (mod 8), m [equivalent to] 29 (mod 32), and remaining values of m. We then combine the bounds derived in each of these cases into a uniform upper bound on [R.sub.j] (m). We first consider the case in which m [equivalent to] 0 (mod 2).

Lemma 3.4 Let m = [2.sup.L]k, where L,k [member of] [Z.sup.+]. Let j [member of] [Z.sup.[greater than or equal to]0], and let l = [[log.sub.2](m + j)]. Then

[mathematical expression not reproducible]

Proof: By Lemma 2.4, we have that [mathematical expression not reproducible]. It follows that

[mathematical expression not reproducible](5)

Applying Lemma 3.1 with s = 1 and a = 1 shows that there exists r [member of] [Z.sup.[greater than or equal to]0] such that

[mathematical expression not reproducible] (6)

We can thus write the prefix of t of length [2.sup.l+1] as

[mathematical expression not reproducible] (7)

where w = (1, rm + j) and z = ((r + 1)m + j + 1,[2.sup.l+1]). Adding [2.sup.l]m everywhere in (6) similarly shows that we can write

[mathematical expression not reproducible] (8)

where w< = ([2.sup.l]m + 1, ([2.sup.l] + r)m + j) and z' = {([2.sup.l] + r + 1)m + j + 1,[2.sup.l](m + 2)). In the same way, adding [2.sup.l+1]m everywhere in (6) gives that

[mathematical expression not reproducible] (9)

where w" = ([2.sup.l+1]m+ 1, ([2.sup.l+1] + r)m + j) and z" = (([2.sup.l+1] +r+ 1)m + j + 1, [2.sup.l+1](m+ 1)). Observe that |w" | = rm + j = | w' |. As a result, Equations (8) and (9) give that

[mathematical expression not reproducible] (10)

Using (6) to note that r + 1 < [mathematical expression not reproducible], we get

[mathematical expression not reproducible] (11)

as desired. []

The following two lemmas establish upper bounds for [R.sub.j] (m) when m = 1 (mod 8). Setting j = 0 in Lemma 3.5 implies Defant's result (Defant, 2017, Lemma 15), while setting j = 0 in Lemma 3.7 gives a bound for [R.sub.0] (m) that is worse than the one given in (Defant, 2017, Lemma 16) by a factor of two.

Lemma 3.5 (cf. (Defant, 2017, Lemma 15)) Let j [member of] [Z.sup.[greater than or equal to]0], and suppose m = [2.sup.L]h + 1, where L and h are integers with L [greater than or equal to] 3 and h odd. Let l = [[log.sub.2] (m + j)]. We have

[mathematical expression not reproducible]

Proof: Suppose, for the sake of contradiction, that [R.sub.j](m) [greater than or equal to] [mathematical expression not reproducible]. We obtain a contradiction to Lemma 3.3 by finding a positive integer[mathematical expression not reproducible] such that [mathematical expression not reproducible]. Note that m has abinary expansion of the formx[01.sup.r][0.sup.L-1]1, where x is a (possibly empty) binary string. Since m [greater than or equal to] [2.sup.3] * 1 + 1 = 9, we have that r [greater than or equal to] 1. Let N be the number of 1's in x. The binary expansion of m + [2.sup.L] + 2 can be expressed as x[10.sup.r+L-2]11, which has N + 3 1's. Similarly, we obtain the following table:
i                    Binary Expansion of i         Number of 1's in
                                                   Binary Expansion of i

m + [2.sup.L] + 2    x[10.sup.r+L-2] 11            N +3
m + [2.sup.L] + 3    x[10.sup.r+L]-3100            N +2
m + [2.sup.L+1] + 2  x[10.sup.r-1][10.sup.L-2]11   N +4
m + [2.sup.L+1] + 3  x[10.sup.r-1][10.sup.L-3]100  N +3


Recall that the parity of [t.sub.i] is the same as the parity of the number of 1 's in the binary expansion of i - 1. It follows that [mathematical expression not reproducible] if N is odd and [mathematical expression not reproducible] if N is even. Observe that [mathematical expression not reproducible]. Therefore, setting s = [2.sup.L] + 3 yields a contradiction to Lemma 3.3 if N is odd, and setting s = [2.sup.L+1] + 3 yields the desired contradiction if N is even. []

Remark 3.6 The proof of Lemma 3.5 closely follows that of (Defant, 2017, Lemma 15). Note, however, that in Defant's proof of (Defant, 2017, Lemma 15), he mistakenly claims that [mathematical expression not reproducible], rather than [mathematical expression not reproducible]. Setting j = 0 in the above proof yields a correct proof of (Defant, 2017, Lemma 15).

Lemma 3.7 (cf. (Defant, 2017, Lemma 16)) Let j [member of] [Z.sup.[greater than or equal to]0]. Suppose m = [2.sup.L]h + 1, where L and h are integers with L [greater than or equal to] 3 and h odd. Let l = |[log.sub.2](m + j)|. If n is an integer such that 2 [less than or equal to] n [less than or equal to] [2.sup.L-1], [t.sub.m-n] = [t.sub.m-n+1], and m + j [less than or equal to] [mathematical expression not reproducible], then

[mathematical expression not reproducible]

Proof: By the proof of (Defant, 2017, Lemma 16), we have that [t.sub.m-2n][t.sub.m-2n+1] = [t.sub.2m-2n][t.sub.2m-2n+1] for any m and n satisfying the hypotheses of the lemma. Consequently,

[mathematical expression not reproducible] (12)

[mathematical expression not reproducible] (13)

[mathematical expression not reproducible] (14)

We want to show that there is an integer r < [2.sup.l] - 1 such that

[mathematical expression not reproducible] (15)

To this end, note that

[mathematical expression not reproducible] (16)

and that

[mathematical expression not reproducible] (17)

It follows that there exists r [member of] Z satisfying (15). To see that r can always be chosen such that r [less than or equal to] [2.sup.l] - 1, it suffices to note that our choice of r is forced to be largest when n is maximal (i.e. when n = [2.sup.L-1]), and that (15) is satisfied by r = [2.sup.l] - 1 in this case. Therefore, for some integer r < [2.sup.l] - 1, we have

[mathematical expression not reproducible] (18)

where w= {(m-2n- 1)[2.sup.l] + 1, ([2.sup.l] - r - 1)m + j) and z = (([2.sup.l] - r)m + j + 1, (m - 2n + 1)[2.sup.l]).

Adding [2.sup.l]m everywhere in (15) similarly gives that

[mathematical expression not reproducible] (19)

where [mathematical expression not reproducible] and [mathematical expression not reproducible]. Note that [mathematical expression not reproducible]. Therefore, (18) and (19) give that

[mathematical expression not reproducible] (20)

Noting from (15) that [mathematical expression not reproducible], we have

[mathematical expression not reproducible] (21)

as desired. []

Remark 3.8 We make note of an error in Defant's proof of (Defant, 2017, Lemma 16). In his proof Defant claims that for m, n, and l satisfying his hypotheses,

[mathematical expression not reproducible] (22)

However, the intervals in the RHS of (22) do not always overlap, so we see that (22) is in fact false. Fortunately, setting j = 0 in Lemma 3.7 gives the bound [mathematical expression not reproducible], which is only slightly worse than Defant's intended bound of [R.sub.0] (m) [less than or equal to] [2.sup.l] - n. This worsens Defant's lower bound for liminf ([[gamma].sub.0](k) / k) from 1/2 to 1/4, and his lower bound for limsup([[gamma].sub.0](k)/k) from 1 to 1/2. However, Narayanan Narayanan (2020) proves lim [mathematical expression not reproducible] andlim [mathematical expression not reproducible], so we still know Defant's claimed lower bounds to be true.

We now address the case in which m = 29 (mod 32).

Lemma 3.9 (cf. (Defant, 2017, Lemma 14)) Let m be a positive integer satisfying m = 29 (mod 32). Let j [member of] [Z.sup.[greater than or equal to]0], and let l = [[log.sub.2](m + j)]. We have

[mathematical expression not reproducible]

Proof: Suppose m = 32n - 3. Let N be the number of 1's in the binary expansion of n. It is straightforward to verify that the binary expansion of m + 6 = 32n + 3 has N + 2 1's. Similarly, we obtain the following table:
i       Number of 1's in Binary Expansion of i

m + 6   N + 2
m + 7   N+1
2m+ 6   N
2m + 7  N+1


Consequently, we have that [t.sub.m+7][t.sub.m+8] = [t.sub.2m+7][t.sub.2m+8]. It follows that

[mathematical expression not reproducible] (23)

[mathematical expression not reproducible] (24)

Applying Lemma 3.1 with s = 7 and a = 1 gives that there exists r [member of] [Z.sup.[greater than or equal to]0] such that

[mathematical expression not reproducible] (25)

Therefore, we can write

[mathematical expression not reproducible] (26)

where w = {[2.sub.l] * 6 + 1, rm + j) and z = {(r + 1)m + j + 1,[2.sub.l] * 8). Adding [2.sup.l]m everywhere in (25) similarly gives that

[mathematical expression not reproducible] (27)

where [mathematical expression not reproducible] and [mathematical expression not reproducible]. In the same way, adding [2.sup.l+1]m everywhere in (25) gives that

[mathematical expression not reproducible] (28)

where [mathematical expression not reproducible] and [mathematical expression not reproducible]. Observe that [mathematical expression not reproducible]. Therefore, (27) and (28) imply

[mathematical expression not reproducible] (29)

Noting from (25) that [mathematical expression not reproducible], we get

[mathematical expression not reproducible] (30)

as desired. []

Remark 3.10 We make note of an error in Defant's proof of an upper bound for [R.sub.0](m) in the case m [equivalent to] 29 (mod 32). In Defant's proof of (Defant, 2017, Lemma 14), he claims that

[mathematical expression not reproducible] (31)

which implies the existence of some r [member of] {9,10,..., 17} such that 17/2r < m/2l < 10, r+1, where l = [[log.sub.2] m]. However, (31) is in fact false. This mistake can be highlighted by observing that for m = 32 * 15 - 3 = 477, there does not exist r [member of] {9,10,..., 17} satisfying the desired inequality. Fortunately, setting j = 0 in Lemma 3.9 gives the bound [R.sub.0](m) [mathematical expression not reproducible], which is only slightly worse than Defant's intended bound of [R.sub.0](m) [less than or equal to] [2.sup.l] + 18. In the same way as the error noted in Remark 3.8, thiserror worsens Defant's lower bounds for [mathematical expression not reproducible] and [mathematical expression not reproducible], but we still know Defant's

claimed lower bounds to be true Narayanan (2020).

Finally, we consider the case in which m is an odd positive integer with m [??] 1 (mod 8) and m [??] 29 (mod 32).

Lemma 3.11 (cf. (Defant, 2017, Lemma 14)) Let m be an odd positive integer with m [??] 1 (mod 8) and m [??] 29 (mod 32). Let j [member of] [Z.sup.[greater than or equal to]0], and let l = [[log.sub.2] (m + j)]. We have

[mathematical expression not reproducible]

Proof: Defant's proof of (Defant, 2017, Lemma 14) (up to where he considers the case m = 29 (mod 32)) applies almost exactly: (Defant, 2017, Lemma 12) and (Defant, 2017, Lemma 13) should merely be replaced by Lemma 3.2 and Lemma 3.3, respectively. []

The following two lemmas use the preceding results to establish a single upper bound for [R.sub.j](m) for any integer m [greater than or equal to] 2.

Lemma 3.12 (cf. (Defant, 2017, Lemma 17)) Let j [member of] [Z.sup.[greater than or equal to]0], and suppose m = [2.sup.L]h + 1, where L and h are integers with L [greater than or equal to] 3 and h odd. Let l = [[log.sub.2] (m + j)]. Then

[mathematical expression not reproducible]

Proof: First, assume that [mathematical expression not reproducible]. Observe that [2.sup.e] - [2.sup.L]h = [2.sup.l] - m +1. Since L < l,

we have that [2.sup.L] divides [2.sup.l] - [2.sup.L]h, which further gives that [2.sup.L] divides [2.sup.l] - m + 1. Since [2.sup.l] - m + 1 > 0, this gives that

[mathematical expression not reproducible] (32)

This implies that [2.sup.2L] - 4 * [2.sup.L] < [2.sup.l] + j ([2.sup.L] - 4) + [2.sup.L] - 4. Rearranging and dividing by [2.sup.L] gives the first inequality of

[mathematical expression not reproducible] (33)

the second inequality is straightforward to verify. From Lemma 3.5, we have that [R.sub.j](m) < [2.sup.l] + [mathematical expression not reproducible] Incorporating (33), we get

[mathematical expression not reproducible] (35)

[mathematical expression not reproducible] (36)

[mathematical expression not reproducible] (37)

where, in the last step, we have used that l = [[log.sub.2] (m+j)] [greater than or equal to] L + 1 and that L [greater than or equal to] 3. It follows that

[mathematical expression not reproducible] (38)

Next, assume that [mathematical expression not reproducible] and L [greater than or equal to] 4. Let n be the largest integer such that m - n = 2 (mod 4) and n [less than or equal to] [2.sup.L-1]. Since n [greater than or equal to] [2.sup.L-1] - 3, we have that [mathematical expression not reproducible]. By the condition m - n [equivalent to] 2 (mod 4), we have [t.sub.m-n] = [t.sub.m-n+1]. We can, therefore, apply Lemma 3.7, which gives

[mathematical expression not reproducible]. (39)

Finally, suppose L = 3. By Lemma 3.5,

[mathematical expression not reproducible] (40)

Lemma 3.13 Let j, m [member of] [Z.sup.[greater than or equal to]0] with m [greater than or equal to] 2 and m [??] 1 (mod 8). Let l = [[log.sub.2](m + j)]. Then

[mathematical expression not reproducible]

Proof: If m = 0 (mod 2), we have by Lemma 3.4 that

[mathematical expression not reproducible] (41)

If m = 29 (mod 32), we have by Lemma 3.9 that

[mathematical expression not reproducible] (42)

Finally, if m is an odd positive integer with m [??] 1 (mod 8) and m [??] 29 (mod 32), we have by Lemma 3.11 that

[mathematical expression not reproducible] (43)

We are now ready to prove the lower bounds for [mathematical expression not reproducible] and [mathematical expression not reproducible].

Theorem 3.14 (cf. (Defant, 2017, Theorem 18)) For any nonnegative integer j,

[mathematical expression not reproducible] and [mathematical expression not reproducible]

Proof: Fix j [member of] [Z.sup.[greater than or equal to]0]. For sufficiently large l [member of] [Z.sup.+] (precisely, for l large enough so that [2.sup.l-1] -j > 0), define [mathematical expression not reproducible]. Choose some k [member of] [Z.sup.+] large enough so that [mathematical expression not reproducible] j. Let [mathematical expression not reproducible]. By definition of [[gamma].sub.j], we have that [mathematical expression not reproducible]. Applying Lemmas 3.12 and 3.13 gives [mathematical expression not reproducible]. Therefore, liminf [mathematical expression not reproducible].

By Lemmas 3.12 and 3.13, we have that [mathematical expression not reproducible] for all positive integers m < [2.sup.l] - j. Therefore, by the definition of [[gamma].sub.j], we have that [mathematical expression not reproducible]. Consequently,

[mathematical expression not reproducible] (44)

3.2 Upper Bounds for [[gamma].sub.j](k)/k

In this subsection we establish upper bounds for [mathematical expression not reproducible] and [mathematical expression not reproducible]. We start by stating a result of Defant.

Proposition 3.15 ((Defant, 2017, Proposition 6)) Letm [greater than or equal to] 2 be an integer, and let [delta](m) = [[log.sub.2](m/3)]. Ify and v are words such that yvy is a factor oft and |y| = m, then [2.sup.[delta](m)] divides \yv\.

We proceed with a lemma and theorem whose proofs closely follow those of (Defant, 2017, Lemma 19) and (Defant, 2017, Theorem 20), respectively.

Lemma 3.16 (cf. (Defant, 2017, Lemma 19)) For each integer l[greater than or equal to]3 and any nonnegative integer j, we have

[mathematical expression not reproducible] and [mathematical expression not reproducible]

Proof: Fix l [greater than or equal to] 3 and j [member of] [Z.sup.[greater than or equal to]0]. Let m = 3 * [2.sup.l-2] + 1 and m' = [2.sup.l-1] + 3. By the definitions of [R.sub.j](m) and [R.sub.j](m'), there exist nonnegative integers r < [R.sub.j](m) - 1 and r' < [R.sub.j](m') - 1 such that

(rm + j + 1, (r + 1)m + j) = (([R.sub.j](m) - 1)m + j + 1, [R.sub.j](m)m + j) (45)

and

{r'm'+j + 1, (r' + 1)m'+ j) = <([R.sub.j](m') - 1)m' + j + 1, [R.sub.j](m')m' + j). (46)

Following the corresponding part of the proof of (Defant, 2017, Lemma 19) and using Proposition 3.15, we may assume that [R.sub.j](m) = r + [2.sup.l-1] + 1 and that [R.sub.j](m') = r' + [2.sup.l-2] + 1.

Assume for the sake of contradiction that [mathematical expression not reproducible]

and v= {([R.sub.j](m)-1)m+j + 1, [R.sub.j](m)m+j). Following the corresponding part of the proof of (Defant, 2017, Lemma 19) and using the fact that t is overlap-free, we get that u [not equal to] v, a contradiction.

Assume next that [mathematical expression not reproducible]. Let u' = (r' m' + j + 1, (r' + 1)m' + j) and v = <([R.sub.j](m')--1)m' + j + 1, [R.sub.j](m')m' + j). Let [mathematical expression not reproducible] and H = min {(r' + 1)m', (q + 2)[2.sup.l-2] + j}. Set U = (r'm< + j + 1, H + j) and V = ((r' + [2.sup.l-2])m' + j + 1,H + [2.sup.l-2]m'+j). Note that the word U is the prefix of u' of length H - r'm'. Recalling that [R.sub.j] (m') = r< + [2.sup.l-2] + 1, we see that V is the prefix of v' of length H - r'm'. Since u' = v', it follows that U = V. Now, there are words w, z', w", and z" such that we have the following:

[mathematical expression not reproducible] (47)

[mathematical expression not reproducible] (48)

Using that U = V and following the corresponding part of the proof of (Defant, 2017, Lemma 19), we get that

[mathematical expression not reproducible] (49)

and hence that [t.sub.q] = [t.sub.q+m],. Note also that |z'| = |z"| = (q + 2)[2.sup.l-2] - (H + j). We show that H + [2.sup.l-2]m + j + 1-(q + m' + 1)[2.sup.l-2] > 0, which will show that z" is a suffix of [mathematical expression not reproducible]. Observe that

[mathematical expression not reproducible] (50)

[mathematical expression not reproducible] (51)

[mathematical expression not reproducible] (52)

If H = r'm' + m', then H = r'm' + [2.sup.l-1] + 3 > r'm' + [2.sup.l-1], giving H-r'm'-[2.sup.l-1] > 0. Alternatively, if H = (q + 2)[2.sup.l-2] - j, then we have

[mathematical expression not reproducible] (53)

and again H - r'm' - [2.sup.l-1] > 0. It follows that [t.sub.q+2] = [t.sub.q+m'+2]. Similarly, [t.sub.q+1] = [t.sub.q+m'+1].

Now,

[mathematical expression not reproducible] (54)

It follows that [mathematical expression not reproducible], which gives that [mathematical expression not reproducible]. Therefore, q + 4 < [2.sup.l-1]. Consequently, for each s [member of] {0,1, 2}, the binary expansion of q + m' + s - 1 has exactly one more 1 than the binary expansion of q + s + 2. Thus,

[mathematical expression not reproducible] (55)

As in the proof of (Defant, 2017, Lemma 19), this contradicts the fact that t is cube-free. []

Theorem 3.17 (cf. (Defant, 2017, Theorem 20)) For any nonnegative integer j,

[mathematical expression not reproducible] and [mathematical expression not reproducible]

Proof: This proof works in exactly the same way as the proof of (Defant, 2017, Theorem 20) with [mathematical expression not reproducible], and Lemma 3.16 in place of f(l), h(l), and (Defant, 2017, Lemma 19), respectively. []

4 Asymptotics for [[GAMMA].sub.j](k)

Having established asymptotic bounds showing that [[gamma].sub.j] (k) grows linearly in k, we now turn our attention to [[GAMMA].sub.j](k). In this section, we prove that liminf ([[GAMMA].sub.j](k)/k) = 3/2 and limsup([[GAMMA].sub.j](k)/k) = 3. We start by motivating our definition of [[GAMMA].sub.j] (k).

Recall that we have defined [[GAMMA].sub.j](k) := sup((2[Z.sup.+] - 1) \ Fj(k)). Also recall that Defant's motivation for defining [[GAMMA].sub.0](k) := sup((2[Z.sup.+] - 1) \ [F.sub.0](k)) is the property that m [member of] [AP.sub.0](t, k) if and only if 2m [member of] [AP.sub.0](t, k), meaning that the only interesting elements of [AP.sub.0](t, k) are those that are odd. However, as previously noted, it is not necessarily the case for nonzero j that m [member of] [AP.sub.j](t, k) if and only if 2m [member of] [AP.sub.j](t, k). As such, it is not initially clear that we are motivated in generalizing Defant's definition of [[GAMMA].sub.0](k) in the way we have. In other words, if even elements of [AP.sub.j] (t, k) can be interesting, why would we consider only the odd elements? The following proposition demonstrates a drawback of considering all even elements of [AP.sub.j] (t, k).

Proposition 4.1 For k [greater than or equal to] 3, the set 2[Z.sup.+] \ ([AP.sub.0](t, k) [intersection] 2Z+) is unbounded.

Proof: Since [t.sub.1][t.sub.2] * * * [t.sub.9] = 011010011 has two occurrences of 011, we have that 3 [member of] Z+ \ [AP.sub.0](t, k) for all k [greater than or equal to] 3. Recall that m [member of] [AP.sub.0](t, k) if and only if 2m [member of] [AP.sub.0](t, k). Therefore, 3 * [2.sup.L] [member of] 2Z+ \ ([AP.sub.0] (t,k)[intersection] 2Z+) for all L [member of] Z+. The proposition follows. []

As a consequence of Proposition 4.1, if we were to include even numbers by defining [[GAMMA].sub.j](k) := sup([Z.sup.+] \ [AP.sub.j](t, k)), we would have that [[GAMMA].sub.0](k) = [infinity] for k [greater than or equal to] 3, which is contrary to the result we are trying to generalize (namely, that [[GAMMA].sub.0](k) grows linearly in k). Corollary 4.4 below shows that only finitely many even elements of [AP.sub.j](t, k) are interesting, and consequently further motivates our definition of [[GAMMA].sub.j](k). To prove Corollary 4.4, we first require a lemma and proposition, both of which were suggested by an anonymous referee. The lemma follows closely from a much more general result in Queffelec (2010) regarding "recognizability" in certain sequences.

Lemma 4.2 Fix x [member of] [Z.sup.+]. Then there exists N [member of] [Z.sup.+] such that ([n.sub.1] + 1, [n.sub.1] + N) = ([n.sub.2] + 1, [n.sub.2] + N) implies [2.sup.x] | ([n.sub.1] - [n.sub.2]).

Proof: (Queffelec, 2010, Lemma 5.6) gives the following: For all x [member of] [Z.sup.+], there exists N [member of] [Z.sup.+] such that if n is a nonnegative multiple of [2.sup.x] and (n + 1, n + N) = (n' + 1, n' + N), then n' is a nonnegative multiple of [2.sup.x]. In the language of Queffelec (2010), each [[micro].sup.x] is "recognizable."

Now, suppose we are given [n.sub.1], [n.sub.2] [member of] [Z.sup.>0]. Choose the smallest nonnegative multiple of [2.sup.x] that is greater than [n.sub.1] (say, [n.sub.1] + r). By (Queffelec, 2010, Lemma 5.6), there exists N G Z+ such that if ([n.sub.1] + r + 1, [n.sub.1] + N ) = ( [n.sub.2] + r + 1, [n.sub.2] + N ), then [n.sub.2] + r is a nonnegative multiple of [2.sup.x]. With this choice of N, it follow s that if ( [n.sub.1] + 1,[n.sub.1] + N ) = ([n.sub.2] + 1, [n.sub.2] + N), then 2 divides ([n.sub.1] + r ) ([n.sub.2] + r) = [n.sub.1] - [n.sub.2]. []

Proposition 4.3 Let J, k [member of] [Z.sup.+]. Then th ere exists N [member of] Z+ such that for allm [greater than or equal to] N and all 1 [less than or equal to] j,j' [less than or equal to] J, we have that m [member of] [AP.sub.j] (t, k) if and only if m [member of] [AP.sub.j]' (t, k).

Proof: Take a, b [member of] [Z.sup.+] such that J < [2.sup.a] and k < [2.sup.b]. Set x := a + b. Choose N [member of] Z+ corresponding to x, as provided by Lemma 4.2.

Assume that m [??] [AP.sub.j](t, k) for some m [greater than or equal to] N. Then, by definition, {j + 1,j + km) is not a k-anti-power, meaning there exist [l.sub.1] [not equal to] [l.sub.2] [member of] {0,..., k - 1} such that

(j + [l.sub.1]m+ 1,j + ([l.sub.1] + 1)m) = (j + [l.sub.2]m + 1, j + ([l.sub.2] + 1)m). (56)

By our choices of N and m, Lemma 4.2 gives that [2.sup.x] | ([l.sub.2] - [l.sub.1])m. Since | [l.sub.2] - [l.sub.1] | < k < [2.sup.b], this shows that [2.sup.a] | m.

For i = 1,2, (j + [l.sub.i]m + 1, j + ([l.sub.i] + 1)m) can be broken into the partial block (j + [l.sub.i]m + 1, [l.sub.i]m + [2.sup.a]), then some blocks of length [2.sup.a], and finally a partial block (([l.sub.i] + 1)m + 1, j + ([l.sub.i] + 1)m). By assumption, all of these blocks coincide for i = 1, 2. Recall that we can view t as a word over the alphabet {[A.sub.a], [B.sub.a]}, where |[A.sub.a]| = |[B.sub.a]| = [2.sup.a]. Since [A.sub.a] and [B.sub.a] differ at every position, we see that ([l.sub.i]m + 1, [l.sub.i]m + 2a) and (([l.sub.i] + 1)m + 1, ([l.sub.i] + 1)m + [2.sup.a]) must coincide for i = 1,2 as well. Putting this all together, we have that

([l.sub.1]m + 1, ([l.sub.1] + 1)m + [2.sup.a]) = ([l.sub.2]m + 1, ([l.sub.2] + 1)m + [2.sup.a]). (57)

Thus, m [??] [AP.sub.j]' (t, k) for any 1 < j' < [2.sup.a]. Reversing the roles of j and j' completes the proof. []

Corollary 4.4 For any fixed j, k [member of] [Z.sup.[greater than or equal to]0] with k [greater than or equal to] 3, the statement

[mathematical expression not reproducible]

holds for all but finitely many m [member of] [Z.sup.+].

Proof: Recall thatt is fixed under the morphism [mathematical expression not reproducible] uniquely defined by [micro](0) = 01 and [micro](1) = 10. With this in mind, it is easily seen that m [member of] [AP.sub.j](t,k) if and only if 2m [member of] [AP.sub.2j](t,k). Moreover, applying Proposition 4.3, we have that for sufficiently large m, 2m G [AP.sub.2j] (t, k) if and only if 2m [member of] [AP.sub.j](t, k). Together, this shows that for all but finitely many m [member of] [Z.sup.+], m [member of] [AP.sub.j](t, k) if and only if 2 m [member of] [AP.sub.j](t,k) []

Having motivated our definition of [[GAMMA].sub.j](k), let us proceed by proving a Corollary to (Defant, 2017, Proposition 6) (stated above as Proposition 3.15).

Corollary 4.5 (cf. (Defant, 2017, Corollary 7)) Let m,k [member of] [Z.sup.+], where m [member of] (2[Z.sup.+] - 1) \ [F.sub.j](t, k) and [mathematical expression not reproducible]. Then [mathematical expression not reproducible].

Proof: By the hypotheses of the corollary, we have that the j-fix of t of length km is not a k-anti-power. It follows that there exist integers [n.sub.1] and [n.sub.2] with 0 [less than or equal to] [n.sub.1] < [n.sub.2] [less than or equal to] k - 1 such that

([n.sub.1]m + j + 1,([n.sub.1] + 1)m+j) = ([n.sub.2]m + j + 1, ([n.sub.2] + 1)m + j). (58)

Using Proposition 3.15, the remainder of the proof follows easily from the proof of (Defant, 2017, Corollary 7). []

We now present a technical lemma that will be useful for constructing identical pairs of subwords of the Thue-Morse word. These pairs of subwords will allow us to establish upper bounds on [R.sub.j] (m) for certain odd values of m. It will be useful to keep in mind that [[GAMMA].sub.j] (k) > m whenever k [greater than or equal to] [R.sub.j] (m); this fact follows from Definitions 1.3 and 1.5.

Lemma 4.6 (cf. (Defant, 2017, Lemma 8)) Suppose that l [greater than or equal to] 2, 2 [less than or equal to] m [less than or equal to] [2.sup.l], r, h, p, q are nonnegative integers satisfying the following conditions:

* h < [2.sup.l-2]

* [mathematical expression not reproducible]

* [mathematical expression not reproducible]

* [mathematical expression not reproducible]

Then (rm + j + 1, (r + 1)m + j) = ((r + [2.sup.l-2])m + 1, (r + [2.sup.l-2] + 1)m), and [R.sub.j](m) [less than or equal to] r + [2.sup.l-2] + 1.

Proof: Let u = {rm + j + 1, (r + 1)m + j) and v = ((r + [2.sup.l-2])m + j + 1, (r + [2.sup.l-2] + 1)m + j). Following the proof of (Defant, 2017, Lemma 8) almost exactly (replacing his variables and conditions with the corresponding ones established above), we get that u = v.It follows that the j-fix of t of length

(r + [2.sup.l-2] + 1)m is not a (r + [2.sup.l-2] + 1)-anti-power, meaning [R.sub.j](m) < r + [2.sup.l-2] + 1. []

We are now ready to prove one of the two main results of this section, the proof of which adapts a construction from the proof of (Defant, 2017, Theorem 9).

Theorem 4.7 (cf. (Defant, 2017, Theorem 9)) Fix j [member of] [Z.sup.[greater than or equal to]0]. For all integers k [greater than or equal to] 3, we have [[GAMMA].sub.j](k) [less than or equal to] 3k - 4. Moreover, [mathematical expression not reproducible].

Proof: The proof that [[GAMMA].sub.j](k) [less than or equal to] 3k - 4 follows almost exactly the corresponding part of the proof of (Defant, 2017, Theorem 9) (replacing the reference to (Defant, 2017, Corollary 7) with a reference to Corollary 4.5).

It remains to show that [mathematical expression not reproducible]. For each positive integer [alpha], define [k.sub.[alpha]] = [2.sup.2[alpha]] + [2.sup.[alpha]] + 2.

Fix an integer [mathematical expression not reproducible], and set l = 2[alpha] + 2, m = 3 * [2.sup.2[alpha]] - [2.sup.[alpha]] + 1, r = [2.sup.[alpha]] + 1, h = j + 1, p = 3 * [2.sup.[alpha]-3], and q = 3 * [2.sup.2[alpha]-3] + [2.sup.[alpha]-2]. Following the proof of (Defant, 2017, Theorem 9), we see that we can apply Lemma 4.6 to get that [mathematical expression not reproducible]. In other words, we have that the j-fix of t of length [k.sub.[alpha]]m is not a [k.sub.[alpha]]-anti-power, meaning [mathematical expression not reproducible]. It follows that

[mathematical expression not reproducible] (59)

for each [alpha] [greater than or equal to] [[log.sub.2](j)] + 2. Consequently, [mathematical expression not reproducible] is an increasing sequence of positive integers with the property that [mathematical expression not reproducible]. This shows that [mathematical expression not reproducible], completing the proof. []

Remark 4.8 The construction in the previous theorem also functions to show that [mathematical expression not reproducible](k) is nonempty for sufficiently large k. In particular, for j > 0 and for any integer [alpha] > [[log.sub.2](j)], we have that m = 3 * [2.sup.2[alpha]] - [2.sup.[alpha]] + 1 [member of] (2Z+ - 1) \ [F.sub.j](k) for all k [greater than or equal to] [k.sub.[alpha]] = [2.sup.2[alpha]] + [2.sup.[alpha]] + 2.

Next, we present a lemma that will aid in the proof of the final main result of the paper. The lemma adapts constructions from (Defant, 2017, Lemma 10), but it only applies for integers j > 0; (Defant, 2017, Lemma 10) gives the same result in the case that j = 0.

Lemma 4.9 (cf. (Defant, 2017, Lemma 10)) Fix j [member of] Z+ and let n be the number of 1's in the binary expansion of j. For integers [alpha] [greater than or equal to] [[log.sub.2](j)] + 2, [beta] [greater than or equal to] [[log.sub.2](j)] + 9, and [rho] > [[log.sub.2](j)] + 8, define

[mathematical expression not reproducible] and [mathematical expression not reproducible] and [mathematical expression not reproducible].

We have [mathematical expression not reproducible] and [mathematical expression not reproducible], where

[mathematical expression not reproducible]

Proof: The lower bound for [[GAMMA].sub.j]([k.sub.[alpha]]) was established in the proof of Theorem 4.7. To bound [[GAMMA].sub.j]([K.sub.[beta]]) from below, let [mathematical expression not reproducible], and [mathematical expression not reproducible]. Following the proof of (Defant, 2017, Lemma 10), we see that we can apply Lemma 4.6 to get that [mathematical expression not reproducible], meaning the j-fix of t of length [K.sub.[beta]]m is not a [K.sub.[beta]]-anti-power. Hence, [mathematical expression not reproducible], as desired.

We now establish the lower bound for [mathematical expression not reproducible]. Define [mathematical expression not reproducible], and [mathematical expression not reproducible]. It is straightforward to verify that these choices satisfy the first four of the five conditions of Lemma 4.6. To prove that [mathematical expression not reproducible], we present an argument that depends on the parity of the number of 1's in the binary expansion of j (which we have denoted by n). Assume that n is odd; the case in which n is even follows similarly. We consider two cases.

First, assume that [rho] [equivalent to] 0 (mod 2). In this case, [[chi].sub.j] ([rho]) = 4j + 3, so the binary expansion of [[chi].sub.j] ([rho]) has n + 2 1's. Note that

[mathematical expression not reproducible] (60)

It follows that when right-justified, all of the 1's in the binary expansion of 5 * [2.sup.[rho]-4] are to the left of all the 1's in the binary expansion of [[chi].sub.j] ([rho]). Binary subtraction thus shows that there are [rho] - 4 - n 1's in the binary expansion of 5 * [2.sup.[rho]-4] - [[chi].sub.j] ([rho]). Since n is odd and [rho] is even, we get that [rho] - 4 - n is odd, meaning [mathematical expression not reproducible]

Next, assume instead that [rho] = 1 (mod 2), meaning [[chi].sub.j]([rho]) = 2j + 1. In this case, the binary expansion of [[chi].sub.j]([rho]) has n + 1 1's. As before, binary subtraction shows that there are [rho] - 3 - n 1's in the binary expansion of 5 * [2.sup.[rho]-4] - [[chi].sub.j]([rho]). Since n is odd and [rho] is even, we have that [rho] - 3 - n is odd, meaning [mathematical expression not reproducible]

We have shown that l', m', r', h', p', and q' satisfy the conditions of Lemma 4.6. Applying the lemma gives that [mathematical expression not reproducible]. Therefore, [mathematical expression not reproducible]. This completes the proof. []

Theorem 4.10 (cf. (Defant, 2017, Theorem 11)) For any nonnegative integer j, [mathematical expression not reproducible].

Proof: The inequality [mathematical expression not reproducible] follows from the corresponding part of the proof of (Defant, 2017, Theorem 11) (replacing [GAMMA](k) with [[GAMMA].sub.j](k) and (Defant, 2017, Corollary 7) with Corollary 4.5).

It remains to show that lim inf ([[GAMMA].sub.j] (k)/k) [greater than or equal to] 3/2. Recall the definitions of [k.sub.a], [K.sub.[beta]], [[kappa].sub.[rho]], and [[chi].sub.j] ([rho]) from Lemma 4.9. Let [mathematical expression not reproducible], fix k [greater than or equal to] [[kappa].sub.[eta]], and put m = [[GAMMA].sub.j](k). Since k [greater than or equal to] [[kappa].sub.[eta]], Lemma 4.9 and the fact that [[GAMMA].sub.j] is nondecreasing (see Remark 1.4) together give [mathematical expression not reproducible]. Put l = [[log.sub.2] (m +j)]. Let us first assume that 3 * [mathematical expression not reproducible]. Note that

[mathematical expression not reproducible] (61)

In particular, we have that l - 1 [greater than or equal to] [[log.sub.2] j] + 8. We can, therefore, apply Lemma 4.9 to get that [mathematical expression not reproducible]. Observe that

[mathematical expression not reproducible] (62)

[mathematical expression not reproducible] (63)

[mathematical expression not reproducible] (64)

> m. (65)

It follows that [mathematical expression not reproducible]. Because [[GAMMA].sub.j] is nondecreasing, [mathematical expression not reproducible]. Therefore,

[mathematical expression not reproducible] (66)

in the case where 3 * [mathematical expression not reproducible].

Assume next that [2.sup.l] [less than or equal to] m + j [less than or equal to] 3 * [2.sup.l-2] - [2.sup.(l-2)*2] and l is even. By (61), we have l - 2 > 2 [[log.sub.2]j] + 18,so

[mathematical expression not reproducible] (67)

We can thus apply Lemma 4.9 to get that [mathematical expression not reproducible] m. Because [[GAMMA].sub.j] is nondecreasing, k<[k.sub.(l-2)/2].Thus,

[mathematical expression not reproducible] (68)

in this case.

Finally, assume that [mathematical expression not reproducible] and l is odd. By (61), we have l - 3 [greater than or equal to] 2 [[log.sub.2]j] + 18, so

[mathematical expression not reproducible] (69)

Therefore, Lemma4.9 gives that [mathematical expression not reproducible] m. Since [[GAMMA].sub.j] is nondecreasing, we have [mathematical expression not reproducible]. Consequently,

[mathematical expression not reproducible] (70)

in this case.

By (66), (68), and (70), we have that in all cases,

[mathematical expression not reproducible] (71)

This gives that [[GAMMA].sub.j](k)/k is bounded below by a positive function of l. It follows that l [right arrow] oo as k [right arrow] [infinity]. Consequently, [mathematical expression not reproducible]. []

5 Conclusion and Further Directions

In Section 4, we proved that [mathematical expression not reproducible] and that [mathematical expression not reproducible]. While we were able to prove these exact asymptotic results in Section 4, we were only able to obtain the asymptotic

bounds [mathematical expression not reproducible] and [mathematical expression not reproducible] in Section 3. However, as of yet, we have no reason to believe that the asymptotic behavior of [[gamma].sub.j] and [[GAMMA].sub.j] depend on j. As such, we extend a conjecture of Defant (Defant, 2017, Conjecture 22) regarding the exact asymptotic growth of [[gamma].sub.0]:

Conjecture 5.1 (cf. (Defant, 2017, Conjecture 22)) For any nonnegative integer j, we have

[mathematical expression not reproducible]

Note that Narayanan Narayanan (2020) has proven lim sup([[gamma].sub.0](k)/k) = 3/2.

Finally, note that it may be interesting to investigate the properties of [AP.sub.j] (x,k) for other infinite words x; Defant Defant (2017) suggests doing this for j = 0. In this paper, we have utilized the recursive structure of t to prove exact asymptotic values (resp. asymptotic bounds) for [[GAMMA].sub.j](k)/k (resp. [[gamma].sub.j](k)/k) that are independent of j. It may be particularly interesting to know whether there are recursively defined infinite words for which the asymptotic growth of analogously defined functions depends on j.

6 Acknowledgements

This work was supported by NSF grant 1659047 and NSA grant H98230-18-1-0010 as a part of the 2018 Duluth Research Experience for Undergraduates (REU). The author would like to thank Niven Achenjang for suggesting the term j-fix. The author would also like to thank Prof. Joe Gallian for organizing a wonderful REU, as well as Levent Alpoge, Aaron Berger, and Colin Defant for being outstanding advisors. Finally, the author would like to thank Gallian, Defant, and Andrew Kwon for reading through this manuscript and providing helpful feedback.

References

J.-P. Allouche and H. Cohen. Dirichlet series and curious infinite products. Bull. Lond. Math. Soc, 17(6): 531-538,1985.

J.-P. Allouche and J. Shallit. The ubiquitous Prouhet-Thue-Morse sequence. Sequences and their Applications: Proceedings of SETA '98, pages 1-16, 1999.

G. Badkobeh, G. Fici, and S. J. Puglisi. Algorithms for anti-powers in strings. Inform. Process. Lett, 137: 57-60, 2018.

A. Berger and C. Defant. On anti-powers in aperiodic recurrent words. Adv. Appl. Math., 121, 2020.

S. Brlek. Enumeration of factors in the Thue-Morse word. Discrete Appl. Math., 24(1):83 - 96, 1989.

Y. Bugeaud and G.-N. Han. A combinatorial proof of the non-vanishing of Hankel determinants of the Thue-Morse sequence. Electron. J. Combin., 21(3), 2014.

A. Burcroff. (k, [lambda])-anti-powers and other patterns in words. Electon. J. Combin., 25(4), 2018.

J. Cooper and A. Dutle. Greedy Galois games. Amer. Math. Monthly, 120(5):441-451,2013.

C. Defant. Anti-power prefixes of the Thue-Morse word. Electron. J. Combin., 24(1), 2017.

F. Dejean. Sur un theoreme de Thue. J. Combin. Theory Ser. A, 13(1):90 - 99, 1972.

G. Fici, A. Restivo, M. Silva, and L. Q. Zamboni. Anti-powers in infinite words. J. Comb. Theory Ser. A, 157:109-119,2018.

K. Mahler. Arithmetische Eigenschaften der Losungen einer Klasse von Funktionalgleichungen. Math. Ann., 101:342-366,1929.

S. Narayanan. Functions on antipower prefix lengths of the Thue-Morse word. Discrete Math., 343(2), 2020.

I. Palacios-Huerta. Tournaments, fairness and the Prouhet-Thue-Morse sequence. Economic Inquiry, 50 (3):848-849, 2012.

M. Queffelec. Substitution Dynamical Systems--Spectral Analysis, 2nd Ed. Lecture Notes in Mathematics, volume 1294. Springer-Verlag, Heidelberg, 2010.

A. Thue. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl., 1:1-67, 1912.

Marisa Gaetz

Massachusetts Institute of Technology

(i) Erroneously stated in Defant (2017) as 1/2 (as will later be explained)

(ii) Erroneously stated in Defant (2017) as 1 (as will later be explained)

received 2019-05-20, revised 2020-08-05,2021-02-11, accepted 2021-02-18.
COPYRIGHT 2021 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2021 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Gaetz, Marisa
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2021
Words:8565
Previous Article:Determining Genus From Sandpile Torsor Algorithms.
Next Article:Wiener Index and Remoteness in Triangulations and Quadrangulations.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |