Monochromatic arithmetic progressions in the Fibonacci, Thue–Morse, and Rudin–Shapiro words G. Joshi, D. Rust Abstract . We investigate the lengths and starting positions of the longest monochromatic arithmetic progressions for a fixed difference in the Fibonacci word. We provide a complete classification for their lengths in terms of a simple formula. Our strongest results are proved using methods from dynamical systems, especially the dynamics of circle rotations. We also employ computer-based methods in the form of the automatic theorem-proving software Walnut . This allows us to extend recent results concerning similar questions for the Thue–Morse word and the Rudin–Shapiro word. This also allows us to obtain some results for the Fibonacci word that do not seem to be amenable to dynamical methods. 2020 Mathematics Subject Classification 52C23, 37B10, 11B85, 68Q45 1. Introduction Consider an infinite sequence of coloured positions taken from a finite colour palette. A monochromatic arithmetic progression with constant difference is the finite or infinite repetition of a single colour in that sequence with a fixed finite difference between those positions. Equivalently, we may consider infinite words over a finite alphabet \mathcal{A} and occurrences of a letter from \mathcal{A} that appear in arithmetic progression within the word. Throughout this work, we write ‘MAP’ to mean ‘monochromatic arithmetic progression’. Van der Waerden’s celebrated theorem [ 29 ] says that for any finite alphabet \mathcal{A} and any natural number k , there is a natural number N such that for any finite word over \mathcal{A} of length N , there must exist a MAP of length k . For a general infinite word, Van der Waerden’s theorem only guarantees the existence of arbitrarily long MAPs, not their lengths or positions in the word. Likewise, it is not true that the existence of arbitrarily long MAPs implies the existence of infinite MAPs. These properties are therefore worth exploring for particular infinite words or families of words. In this work, we are not so concerned with the existence of infinite MAPs. Morgenbesser, Shallit, and Stoll [ 13 ] showed that the Thue–Morse word only admits finite MAPs as a consequence of a result of Gelfond [ 8 ] . Works by Durand and Goyheneche [ 7 ] , and by Nagai, Akiyama and Lee [ 15 ] (for tilings) address the question for general uniformly recurrent sequences (resp. primitive substitution tilings) from a dynamical perspective, giving conditions for the non-existence of infinite MAPs in terms of spectral properties of the subshift (resp. hull) associated with a sequence (resp. tiling). Instead, we turn our attention to understanding how long MAPs can be for a fixed difference and the starting positions of their first occurrence. There has been recent progress in this direction for certain families of words. In particular, most of the literature has so far focused on words coming from substitutions of constant length, also known as k -automatic sequences. For an introduction to fixed points of substitutions on finite alphabets we refer the reader to the book by Queffélec [ 19 ] , and for a primer on finite-state automata and automatic sequences, see the book by Allouche and Shallit [ 4 ] . Parshina [ 18 ] addressed the question of determining the lengths of longest MAPs for generalised binary Thue–Morse words. Aedo, Grimm, Nagai, and Staynova [ 2 ] , and the same authors with Mañibo [ 3 ] performed similar studies for ‘Thue–Morse like’ words and substitutions with certain symmetries, including the Rudin–Shapiro word. Unfortunately, they were still unable to resolve the question of classifying the lengths of longest MAPs completely for any of these words, only providing bounds for the most part and, in the best cases, exact values for very specific families of fixed differences. The question of determining the position of the first occurrence of a MAP of maximal length for a fixed difference is less well studied. However some results exist in the literature; most notably Parshina [ 17 ] tackled this question for generalised binary Thue–Morse words, and Sobolewski [ 27 ] , using a computational approach, was able to determine first occurrences for some fixed differences for the Rudin–Shapiro word. Conspicuously missing from all of these studies is an attempt to understand these questions for words coming from substitutions that are not constant length 1 1 1 beyond the existence or non-existence of infinite MAPs, which is addressed by the results of Durand and Goyheneche [ 7 ] . . This includes a lack of any results concerning perhaps the most well-known substitution, the Fibonacci substitution. This is likely due to the fact that the methods brought to bear in tackling these problems rely heavily on the k -automatic structure of the words associated with substitutions of constant length, which explains why the strongest results in this setting are for when the fixed difference is close to a power of the length of the substitution (e.g., powers of 2 for the Thue–Morse substitution). Our primary focus in this article is the study of the Fibonacci word. We make use of two novel approaches that prove to be exceptionally powerful: the first is that we make use of the fact that the Fibonacci word can be described in terms of the itinerary of an orbit of an irrational rotation on a circle, allowing us to use results from Diophantine approximation and dynamical systems; the second is that we take advantage of the fact that, although the Fibonacci word is not k -automatic, it is automatic with respect to the Zeckendorf numeration system, which allows us to use new computational technologies in the form of automatic theorem-proving software. Walnut is a software package written by Hamoon Mousavi [ 14 ] designed to automatically prove propositions concerning automatic sequences that can be stated within the first-order theories of extended Presburger arithmetic or Büchi arithmetic. This includes sequences that are automatic with respect to non-uniform numeration systems such as Zeckendorf numeration. Together, these two methods allow us to completely resolve the question of which lengths of MAPs exist for a fixed difference, culminating in two simple formulae for the maximal length (Theorems 4.6 and 4.15 ). We also make significant progress in understanding the positions of first occurrences of MAPs of maximal length. In some instances, we provide proofs of statements using both methods, but it is worth noting that both methods have limitations and so our work benefits from a blending of the two. The paper is organised as follows. Section 2 provides the necessary preliminaries for substitutions, monochromatic arithmetic progressions, finite state automata, and Walnut . Section 3 is devoted to results obtained from the use of Walnut . These include extensions of previous results concerning MAPs in the Thue–Morse and Rudin–Shapiro words, as well as our first results that address the Fibonacci word. Section 4 then details our strongest results on both longest MAPs and positions of their first occurrence for the Fibonacci word. In this final section, we reinterpret the Fibonacci word as a rotation sequence on the interval [0,1] and MAPs as segments of orbits of a power of the rotation. This in turn allows us to take advantage of results from the theory of dynamical systems and Diophantine approximation. 2. Preliminaries 2.1. Substitutions Let {\mathbb{N}} , {\mathbb{N}}_{0} and {\mathbb{Z}} denote the set of natural numbers, the set of non-negative integers and the set of integers, respectively. Given a finite alphabet \mathcal{A} , let \mathcal{A}^{n} denote the set of words of length n over \mathcal{A} with the empty word \varepsilon\in\mathcal{A}^{0} , and let \mathcal{A}^{{\mathbb{N}}_{0}} denote the set of {\mathbb{N}}_{0} -indexed infinite sequences over \mathcal{A} . Let \mathcal{A}^{*}=\bigsqcup_{n=0}^{\infty}\mathcal{A}^{n} denote the free monoid of finite words in \mathcal{A} under concatenation, and let \mathcal{A}^{+}=\bigsqcup_{n=1}^{\infty}\mathcal{A}^{n} denote the set of non-empty words in \mathcal{A} . A function \theta\colon\mathcal{A}\to\mathcal{A}^{+} is called a substitution and naturally extends to a function \theta\colon\mathcal{A}^{+}\to\mathcal{A}^{+} by concatenation of words. In this way, a substitution can be iterated by defining \theta^{1}=\theta and \theta^{n+1}=\theta\circ\theta^{n} . A substitution is called primitive if there exists a power p\geq 1 such that for all letters \mathtt{a,b}\in\mathcal{A} , the word \theta^{p}(\mathtt{b}) contains the letter \mathtt{a} . Note that letters in an alphabet are written in Teletype font, and may include digits such as \mathtt{0} and \mathtt{1} . Example 2.1 . Let \phi denote the Fibonacci substitution on the alphabet \mathcal{A}=\{\mathtt{0,1}\} , defined by \phi\colon\mathtt{0}\mapsto\mathtt{01},\,\mathtt{1}\mapsto\mathtt{0} . This substitution is primitive, as both \phi^{2}(\mathtt{0}) and \phi^{2}(\mathtt{1}) contain both letters \mathtt{0} and \mathtt{1} . In this work, we focus on substitution fixed (resp. substitution periodic) points. That is, sequences {\mathbf{x}} such that \theta({\mathbf{x}})={\mathbf{x}} (resp. \theta^{p}({\mathbf{x}})={\mathbf{x}} for some p\geq 1 ). For example, the Fibonacci word {\mathbf{f}}=\left(f_{i}\right)_{i\geq 0}\in\{\mathtt{0,1}\}^{{\mathbb{N}}_{0}} is the unique fixed point of the Fibonacci substitution \phi and is generated by taking the limit of \phi^{i}(\mathtt{0}) for increasing powers i , giving \mathtt{0}\mapsto\mathtt{01}\mapsto\mathtt{010}\mapsto\mathtt{01001}\mapsto\cdots\mapsto{\mathbf{f}}=\mathtt{010010100100101}\cdots. Here, note that f_{i} denotes the letter at position i in the sequence {\mathbf{f}} . For example, f_{4}=\mathtt{1} . 2.2. Monochromatic arithmetic progressions Definition 2.2 . When a letter \mathtt{a} in a sequence {\mathbf{x}} repeats \ell times with a difference d , we call it a monochromatic arithmetic progression of difference d and length \ell . That is, for some i\geq 0 , x_{i}=x_{i+d}=x_{i+2d}=\cdots=x_{i+(\ell-1)d}. We write ‘MAP’ to mean ‘monochromatic arithmetic progression’. Definition 2.3 . Let {\mathbf{x}}\in\mathcal{A}^{{\mathbb{N}}_{0}} and d\in{\mathbb{N}} . We let A_{\mathbf{x}}(d)=\max\{\ell\mid\text{there is a MAP of difference $d$ and length $\ell$ in ${\mathbf{x}}$}\} denote the longest length of a MAP of difference d that can be found in {\mathbf{x}} , where by convention A_{\mathbf{x}}(d)=\infty if no finite maximum exists. Remark 2.4 . Parshina [ 18 ] first used the notation A_{\mathbf{x}}(c,d) to mean the longest length of the MAP of difference d , where c denotes the starting position of the MAP. We adopt this notation, but suppress c as we consider here MAPs beginning at any position in {\mathbf{x}} . Definition 2.5 . We let i_{\mathbf{x}}(d) denote the first position at which a MAP of maximal length and of difference d starts in the sequence {\mathbf{x}} . That is, i_{\mathbf{x}}(d)=\min\{j\mid x_{j}=x_{j+d}=\cdots=x_{j+(A(d)-1)d}\}. We avoid subscripts and write A(d) and i(d) when the context is clear. Example 2.6 . In the Fibonacci word {\mathbf{f}} , we find a MAP of difference d=3 and length \ell=5 given by f_{20}=f_{23}=f_{26}=f_{29}=f_{32}=\mathtt{0}. It can be shown that there is no MAP of difference d=3 longer than 5 and so A(3)=5 (see Section 3.1 ). As f_{20} is the earliest starting position of a length- 5 MAP of difference 3 (all earlier MAPs are shorter), we have i(3)=20 . Recall that the set of all infinite words is denoted by \mathcal{A}^{\mathbb{N}_{0}} . A word {\mathbf{x}} is called periodic if there exists x\in\mathcal{A}^{*} such that {\mathbf{x}}=x^{\omega} . A word {\mathbf{x}} is called eventually periodic if there exist x,y\in\mathcal{A}^{*} such that {\mathbf{x}}=yx^{\omega} . A word {\mathbf{x}} is called non-periodic otherwise. A first simple observation provides a uniform lower bound on A_{\mathbf{x}}(d) when {\mathbf{x}} is a non-periodic sequence over a binary alphabet. Lemma 2.7 . Let {\mathbf{x}} be a non-periodic sequence over the alphabet \{\mathtt{0,1}\} . For every d , A_{{\mathbf{x}}}(d)\geq 2 . Proof. Since the sequence is non-empty, it is clear that A_{\mathbf{x}}(d) is never 0 . Suppose that for some d\geq 1 , we have A_{\mathbf{x}}(d)=1 . Then for all k\geq 0 , we have x_{k}\neq x_{k+d} . Let {\mathbf{x}}_{[0,d-1]}=x_{0}x_{1}\cdots x_{d-1} be the length- d prefix of {\mathbf{x}} . Let \overline{x_{i}} denote the complement of x_{i} ; i.e., x_{i}=\mathtt{0}\iff\overline{x}_{i}=\mathtt{1} . Given the observation that no symbol repeats with difference d , we conclude that {\mathbf{x}} must have the following structure {\mathbf{x}}=x_{0}x_{1}\cdots x_{d-1}\overline{x_{0}x_{1}\cdots x_{d-1}}x_{0}x_{1}\cdots x_{d-1}\overline{x_{0}x_{1}\cdots x_{d-1}}\cdots. That is, {\mathbf{x}}=(x_{0}x_{1}\cdots x_{d-1}\overline{x_{0}x_{1}\cdots x_{d-1}})^{\omega} . So, {\mathbf{x}} is periodic with period 2d . This contradicts the non-periodicity of {\mathbf{x}} . So, A_{\mathbf{x}}(d)=1 must be false. That means, A_{\mathbf{x}}(d)\geq 2 for all d . ∎ 2.3. Automata Theory A deterministic finite automaton (DFA) is a finite-state machine that accepts or rejects an input string of symbols. A standard reference for the study of automatic sequences (including the following technical definitions) is the book of Allouche and Shallit [ 4 ] . Definition 2.8 . A DFA M is defined as a 5-tuple M=(\mathcal{Q},\Sigma,\delta,q_{0},F) , where • \mathcal{Q} is a finite set of states, • \Sigma is the finite input alphabet, • \delta\colon\mathcal{Q}\times\Sigma\mapsto\mathcal{Q} is the transition function, • q_{0}\in\mathcal{Q} is the initial state, and • F\subseteq\mathcal{Q} is the set of accepting states. We can extend \delta iteratively to a function \delta\colon\mathcal{Q}\times\Sigma^{*}\to\mathcal{Q} by defining, for a letter a and finite word u , \delta(q,au)\coloneq\delta(\delta(q,a),u) , where \delta(q,\varepsilon)=q . Note that this definition implicitly assumes that we read words from left to right, which will correspond to reading representations of natural numbers from the most significant digit (msd-first). See Figure 2 for an example of a DFA where the input is read in binary with msd-first. We will almost always use msd-first throughout this text, although one can always define a DFA that reads inputs from right to left, which we refer to as reading from the least significant digit (lsd-first). 2.3.1. k -automatic sequences Definition 2.9 . Let k\geq 2 . A k -DFAO is a DFA with an output and whose input alphabet comprises k symbols. That is, a k -DFAO is a 6 -tuple M=(\mathcal{Q},\Sigma=\{0,1,\dots,k-1\},\delta,q_{0},\mathcal{A},\vartheta) with \mathcal{Q},\Sigma,\delta,q_{0} as given in Definition 2.8 , \mathcal{A} is the output alphabet, and \vartheta is a map \vartheta\colon\mathcal{Q}\to\mathcal{A} called a coding . A sequence {\mathbf{x}} is k -automatic if it is the output of a k -DFAO. That is, the n -th term in {\mathbf{x}} is given by x_{n}=\vartheta(\delta(q_{0},(n)_{k})) , where (n)_{k} is the k -ary representation of the natural number n seen as a word over \{0,1,\ldots,k-1\} . Example 2.10 . The Thue–Morse word {\mathbf{t}} is the output of the 2 -DFAO shown in Figure 1 and is therefore 2 -automatic. \mathtt{0} \mathtt{1} 0 1 1 0 Figure 1 . A 2 -DFAO that generates the Thue–Morse word \mathtt{0110100110010110\cdots} . Comparing to Definition 2.9 , the 2 -DFAO that generates {\mathbf{t}} is defined with \mathcal{Q}=\mathcal{A}=\{\mathtt{0,1}\} , \Sigma=\{0,1\} , q_{0}=\mathtt{0} , and the identity map \vartheta . For example, to find t_{6} , the 6 -th term in {\mathbf{t}} , one reads (6)_{2}=110 with msd-first and records the output state as follows: \rightarrow\mathtt{0}\overset{1}{\longrightarrow}\mathtt{1}\overset{1}{\longrightarrow}\mathtt{0}\overset{0}{\longrightarrow}\mathtt{0}. So, t_{6}=\mathtt{0} . Note that the Thue–Morse word is also the fixed point of the substitution \mathtt{0}\mapsto\mathtt{01},\,\mathtt{1}\mapsto\mathtt{10} . 2.4. Walnut We use the automatic theorem-proving software Walnut , originally written by Hamoon Mousavi [ 14 ] . Walnut is based on an algorithm that can decidably prove or disprove first-order logical statements involving automatic sequences, made possible by Büchi’s decidability theorem ( [ 22 , Theorem 6.3.2] ). For a detailed account of the development of Walnut and an introduction to its use, we recommend the book by Shallit [ 22 ] . It is also worth mentioning that Shallit currently maintains a directory of academic works that have made use of Walnut in a research setting [ 23 ] . In this work, we make reference in several places to outputs generated by Walnut . In these cases, we provide code whose output can be confirmed by running the same command in the Walnut software. Thankfully, Walnut code is intuitive to read for a working mathematician, and so for the benefit of the reader that is not familiar with Walnut but would like to understand the code provided in this work without needing to run it in the software, we provide some of the basics of Walnut syntax that are useful for understanding our code: • E is the existential quantifier, and A is the universal quantifier. • ?msd_k tells Walnut to represent integers in base- k to be read msd-first. For example, ?msd_2 for binary and ?msd_fib for base Fibonacci. In the absence of that, it represents the integers in binary by default. • ~ is logical NOT, & is logical AND, | is logical OR, => is logical implication. • def defines an automaton accepting the values of the free variables, making the logical statement true. • eval returns TRUE (resp. FALSE ) when the output DFA accepts (resp. rejects) all input values. • T , RS , and F are predefined in Walnut to be the Thue–Morse, Rudin–Shapiro, and Fibonacci words respectively. • Representations of families of integers can be defined in Walnut using regular expressions using the reg command. For example, the following command defines a regular expression that accepts only values of the form 2^{n} for some n\in{\mathbb{N}} : reg ispower2 ?msd_2 "0*10*"; . Here, u* is to be interpreted as an arbitrarily long (possibly empty) concatenated string of u ’s. In terms of automata, u* corresponds to a cycle whose labelled edges read u . 3. Automatically proved results for MAPs Most of the results in this section are proved using the automatic theorem-proving software Walnut . 3.1. Encoding MAPs in Walnut We define the following basic Walnut commands that will be used to find the values of A(d) and i(d) for any fixed value of d in an automatic sequence {\mathbf{x}} . Note that, since the multiplication of two variables is prohibited in extended Presburger arithmetic, we must manually fix the difference d when evaluating terms such as d*k in the following list of commands. Hence, the commands must be rerun for each new value of d . • def map "Ak (k X[i]=X[i+d*k]": # Accepts all pairs (l,i) for which there is a MAP of length l of difference d , beginning at position i in {\mathbf{x}} . • def imap "Ei $map(i,l)": # Accepts all values of l for which there is a MAP of length l of difference d . • def lmap "$imap(l) & Am (m>l) => ~$imap(m)": # Accepts A(d) , the length of the longest MAP of difference d . • def fmap "$map(i,l) & Aj (j ~$map(j,l)": # Accepts i(d) , the starting position of the first MAP of length A(d) ; note that l in fmap must be manually replaced with the value of A(d) found by lmap. Remark 3.1 . For a fixed difference d , it is known to be decidable whether an automatic sequence admits an infinite MAP [ 7 , Proposition 22] . One may use the following command in Walnut to check the same: eval infmapcheck "Ei (An (n>0) => X[i]=X[i+n*d])"; . 3.2. The Thue–Morse word Morgenbesser et al. [ 13 ] and Aedo et al. [ 2 ] investigated bounds on the lengths of MAPs for the Thue–Morse word {\mathbf{t}} . In particular, Aedo et al. showed that for all d\geq 1 and n\geq 1 , A(2^{n}d)=A(d) . In particular, A(2^{n})=2 for all n\geq 1 , and this can be checked in Walnut (we leave the details to the interested reader). They were also able to prove the following uniform bound for all other values of A(d) . Lemma 3.2 ( [ 2 , Lemma 13] ) . Let d>1 be an odd integer. Then A(d)\geq 3 . The authors conjectured that this bound can be improved to A(d)\geq 4 . That is, they claimed that there exists no odd d for which A(d)=3 . We resolve this conjecture and, as a consequence, find the optimal lower bound for A(d) . Proposition 3.3 . Let d\geq 1 . If d=2^{n} for n\geq 0 , then A(d)=2 . If d has an odd factor, then A(d)\geq 4 . Further, there exists d for which A(d)=4 . Proof. The statement for powers of 2 follows from the fact that A(1)=2 and A(2^{n}d)=A(d) . For the second statement, we first prove that if d>1 is odd, then A(d)\geq 4 . Running the following command in Walnut returns TRUE : • def odd "En (d=2*n+1)"; # Accepts all odd values of d . • eval tmad_geq4 "Ad ($odd(d) & d>1) => Ei (T[i]=T[i+d] & T[i]=T[i+2*d] & T[i]=T[i+3*d])"; # This checks if for all odd d>1 , the MAP has length at least 4 . As A(2^{n}d)=A(d) , this confirms the same result for all d with an odd factor. To see that the bound is sharp, we observe that A(11)=4 , as the input (11)_{2} reaches an accepting state in the DFA given in Figure 2 . ∎ As A(2^{n}d)=A(d) for all d\geq 1 , it is only necessary to understand A(d) for odd values of d . It would be convenient if a similar result held for i(d) . For instance, we have that i(2^{n})=2^{n} for all n\geq 0 . This can be checked in Walnut or proved by elementary methods (see Proposition 3.4 ). In principal, one may also verify in Walnut that for all n\geq 0 , i(2^{n}d)=2^{n}i(d) for any given fixed difference d\geq 1 . The reason that this statement can be encoded in Walnut is because A(2^{n}d) is fixed over all n\geq 0 . Unfortunately, Walnut cannot be used (to our knowledge) to show that this relationship holds simultaneously for all d . Thankfully, we are able to show this by hand using traditional methods. Proposition 3.4 . For all d\geq 1 and for all n\geq 0 , i(2^{n}d)=2^{n}i(d) . In particular, if d is even, then i(d) is even. Proof. We prove the statement for n=1 , from which the full statement follows by a simple induction. First, because A(2d)=A(d) , and the Thue–Morse substitution has constant substitution length \ell=2 , by simply applying the substitution to the earliest MAP of length d , we get that i(2d)\leq 2i(d) . It now remains to show that i(2d)\geq 2i(d) . For that, we use another defining property of {\mathbf{t}} that for all n , t_{2n}=t_{n} and t_{2n+1}=\overline{t_{n}} . Suppose that i(2d) is even. Then as t_{i(2d)}=t_{i(2d)+2d}=\cdots=t_{i(2d)+(A(d)-1)2d}, we must also have t_{i(2d)/2}=t_{i(2d)/2+d}=\cdots=t_{i(2d)/2+(A(d)-1)d}. Hence i(2d)/2 is the first position of a MAP of difference d and length A(2d)=A(d) . So, i(d)\leq i(2d)/2 , giving 2i(d)\leq i(2d) . Now suppose that i(2d) is odd. Then as t_{i(2d)}=t_{i(2d)+2d}=\cdots=t_{i(2d)+(A(d)-1)2d}, we must also have \overline{t_{(i(2d)-1)/2}}=\overline{t_{(i(2d)-1)/2+d}}=\cdots=\overline{t_{(i(2d)-1)/2+(A(d)-1)d}}. Hence (i(2d)-1)/2 is the first position of a MAP of difference d and length A(2d)=A(d) . So, i(d)\leq(i(2d)-1)/2 , giving 2i(d)\leq 2i(d)+1\leq i(2d) . ∎ Remark 3.5 . The above proof can easily be adapted to show that for any fixed point of a bijective substitution of length \ell , we have that for all d\geq 1 and n\geq 0 , i(\ell^{n}d)=\ell^{n}i(d) . Here, by bijective substitution , we mean a substitution \theta of constant length \ell such that for each 0\leq i\leq\ell-1 there exists a bijection \alpha_{i}\colon\mathcal{A}\to\mathcal{A} such that for all a\in\mathcal{A} , \theta(a)_{i}=\alpha_{i}(a) . 3.2.1. Preimages of A(d) Though Proposition 3.4 is proved using traditional methods, in the initial attempt to use Walnut to prove it, an interesting fact emerged which we mention below. Proposition 3.6 . The largest odd d for which A(d)=4 is 35 . Proof. The proof is enumerating the DFA generated by the following Walnut command: def tmad4 "Ei (T[i]=T[i+d] & T[i]=T[i+2*d] & T[i]=T[i+3*d] & T[i]!=T[i+4*d]) & (Aj (j>=0) => ~(T[j]=T[j+d] & T[j]=T[j+2*d] & T[j]=T[j+3*d] & T[j]=T[j+4*d]))"; This outputs the DFA given in Figure 2 . Figure 2 . DFA enumerating all values of d for which A(d)=4 . The (unique) longest accepted input ending in a 1 is 100011 , corresponding to 35 . ∎ Let O_{\max}\colon{\mathbb{N}}\to{\mathbb{N}}\cup\{-\infty,\infty\} denote the maximal odd value of d for which A(d)=n . That is, O_{\max}(n)\coloneqq\max\{d\mid A(d)=n,\ d\text{ odd}\} , where it is understood that O_{\max}(n)\coloneqq-\infty if the set of odd d for which A(d)=n is empty, and O_{\max}(n)\coloneqq\infty if there are infinitely many odd d for which A(d)=n . Hence, for instance, Proposition 3.6 can be restated as O_{\max}(4)=35 . We similarly calculate the following values of O_{\max}(n) in Table 1 by suitably modifying the Walnut command in the proof of Proposition 3.6 . n 1 2 3 4 5 6 7 O_{\max}(n) -\infty 1 -\infty 35 29 \infty \infty Table 1 . n:=A(d) , and O_{\max}(n):= largest odd d for which A(d)=n . The time taken by Walnut to find the DFA enumerating O_{\max} grows exponentially. For n=1,\dots,5 , it took 3,11,86,1926,21746 milliseconds respectively. For n=6 , Walnut took approximately 10 minutes. For n=7 , Walnut took approximately an hour and over 300 GB of memory. On hardware available to the authors, Walnut was unable to calculate O_{\max} for n\geq 8 due to memory limitations. We do not understand the behaviour of the function O_{\max} from the values in Table 1 . Indeed, it is unclear if O_{\max} takes mostly finite or infinite values. This motivates the following set of questions. Question 3.7 . Are there infinitely many values of n for which O_{\max}(n)=-\infty , or is \{1,3\} the full set of values for which O_{\max}=-\infty ? Are there infinitely many values of n for which O_{\max}(n)=\infty ? Are there infinitely many values of n for which O_{\max}(n)<\infty , or is \{2,4,5\} the full set of values for which O_{\max} is finite? 3.2.2. i(d) for particular families of d We cannot produce an automaton whose output is i(d) for all d\geq 1 simultaneously, as A(d) varies in d and this would therefore require a product of variables in Walnut . Likewise, for certain infinite families of d , we may conjecture that i(d) takes a particular form, but this cannot be checked if A(d) is not constant on the family. Some conjectures of this form are given below: Aedo et al. showed that for all n\geq 2 , A(2^{n}+1)=2^{n}+2 and for all n\geq 2 , A(2^{n}-1)=2^{n}+4 if n is even and A(2^{n}-1)=2^{n} if n is odd [ 2 ] . Further to this, based on empirical observations (see A342827 ), it would appear that the identities given in Conjecture 3.8 hold, but a proof remains elusive. Conjecture 3.8 . We have \displaystyle i(2^{n}+1) \displaystyle=3.2^{2n}-2^{n}-1, \displaystyle i(2^{2n}-1) \displaystyle=3.2^{4n}-2^{2n}+1, \displaystyle i(2^{2n+1}-1) \displaystyle=2^{2n+1}-1. There are still many other open questions relating to MAPs in the Thue–Morse word. However, as this is not the focus of this work, we address an automatic sequence of interest, the Rudin–Shapiro word, before finally focussing our attention on our principal sequence of interest, the Fibonacci word. 3.3. The Rudin–Shapiro word The Rudin–Shapiro sequence {\mathbf{r}}:=\mathtt{0001001000011101}\cdots is another binary automatic sequence of frequent interest [ 10 , 24 , 21 ] . It can be defined as a coding of the fixed point of the substitution \mathtt{a}\mapsto\mathtt{ab},\,\mathtt{b}\mapsto\mathtt{ac},\,\mathtt{c}\mapsto\mathtt{db},\,\mathtt{d}\mapsto\mathtt{dc} , with coding morphism given by \mathtt{a},\mathtt{b}\mapsto\mathtt{0},\text{ and }\mathtt{c},\mathtt{d}\mapsto\mathtt{1} . Aedo et al. studied MAPs of generalisations of the Rudin–Shapiro word [ 3 ] . In particular, they showed that there is no infinite MAP in {\mathbf{r}} ( [ 3 , Proposition 41] ). They also proved that A(2^{n}d)=A(d) ; in particular A(2^{n})=A(1)=4 ( [ 3 , Section 4.1] ). Sobolewski extended these results by considering families of values of d of the form 2^{n}\pm k for some k [ 27 ] . Due to the aforementioned limitations of Walnut , we are only able to reprove some of these results by automatic methods; namely when A(d) is constant. In such cases, we are often able to determine the first positions of longest MAPs, i(d) . Proposition 3.9 . For all n\geq 0 , i(2^{n})=7\cdot 2^{n} . Proof. We first confirm that for all n\geq 0 , A(2^{n})=4 . It is then only necessary to check that there is a MAP of length 4 and difference 2^{n} beginning at position 7\cdot 2^{n} and no earlier such MAPs appear. • def run4rs "RS[i]=RS[i+d] & RS[i]=RS[i+2*d] & RS[i]=RS[i+3*d]"; # Accepts all pairs (d,i) for which i is the starting position of a MAP of length at least 4 with difference d . • def run5rs "RS[i]=RS[i+d] & RS[i]=RS[i+2*d] & RS[i]=RS[i+3*d] & RS[i]=RS[i+4*d]"; # Accepts all i for which i is the starting position of a MAP of length at least 5 with difference d . • eval rsad4check "Ad ($power2(d)) => Ei ($run4rs(d,i) & Aj ~$run5rs(d,j))"; # Returns TRUE if and only if for all n\geq 0 , A(2^{n})=4 . Walnut returns TRUE. • eval propcheck "Ad ($ispower2(d)) => ($run4rs(d,7*d) & (Aj (j<7*d) => ~$run4rs(d,j)))"; # Returns TRUE if and only if for all n\geq 0 , there is a MAP of length 4 and difference 2^{n} beginning at position 7\cdot 2^{n} and no earlier such MAP appears. Walnut returns TRUE. ∎ 3.4. The Fibonacci word We now shift our attention to the Fibonacci word, the fixed point of the substitution \mathtt{0}\mapsto\mathtt{01},\,\mathtt{1}\mapsto\mathtt{0} . As this substitution is not constant-length, and the Fibonacci word cannot be encoded from the fixed point of a constant-length substitution, we need a more general setting in which to consider this sequence automatic. 3.4.1. Fibonacci-automatic Let \{F_{0},F_{1},\ldots\} denote the set of Fibonacci numbers defined by F_{0}=0 , F_{1}=1 and recursively F_{n+2}=F_{n+1}+F_{n} for all n\geq 0 . Ostrowski [ 16 ] , Lekkerkerker [ 11 ] and Zeckendorf [ 30 ] showed that there is a unique way to represent non-negative integers as the sum of distinct Fibonacci numbers with the restriction that no pair of consecutive Fibonacci numbers are used. This is often called the Zeckendorf representation or base Fibonacci . So, every non-negative integer n has a unique representation of the form n=\sum_{i\geq 2}a_{i}F_{i}, where a_{i}\in\{0,1\} , and a_{i}a_{i+1}=0 for all i\geq 2 [ 6 ] . This representation is conventionally written as a binary word (n)_{F} with msd-first: (n)_{F}\coloneqq a_{t}a_{t-1}\cdots a_{2} , with (0)_{F}=\varepsilon , the empty word. For example, (45)_{F}=10010100 as 45=F_{9}+F_{6}+F_{4} . We say an F -DFAO is a DFAO with input read in Zeckendorf representation, and a sequence is Fibonacci-automatic if and only if an F -DFAO generates it (see, e.g., [ 22 , Section 5.9] ). Example 3.10 . The n -th term of the Fibonacci word {\mathbf{f}} can also be given by the last digit in the Zeckendorf representations of n . Therefore, {\mathbf{f}} is an output sequence of the F -DFAO shown in Figure 3 , which has states and output alphabet \mathcal{Q}=\mathcal{A}=\{\mathtt{0},\mathtt{1}\} with initial state q_{0}=\mathtt{0} , the input alphabet \Sigma=\{0,1\} , with the identity coding map \tau\colon\mathcal{Q}\to\mathcal{A} . For example, in order to determine the 11 -th term in {\mathbf{f}} , we first find the Zeckendorf representation of 11 by noting that 11=8+3=F_{5}+F_{3} , so (11)_{F}=10100 . We begin at the initial state q_{0}=\mathtt{0} and follow the sequence of edges that reads 10100 from the most significant digit to the least. So we follow the path \rightarrow\mathtt{0}\stackrel{{\scriptstyle 1}}{{\longrightarrow}}\mathtt{1}\stackrel{{\scriptstyle 0}}{{\longrightarrow}}\mathtt{0}\stackrel{{\scriptstyle 1}}{{\longrightarrow}}\mathtt{1}\stackrel{{\scriptstyle 0}}{{\longrightarrow}}\mathtt{0}\stackrel{{\scriptstyle 0}}{{\longrightarrow}}\mathtt{0} which confirms f_{11}=\mathtt{0} . In this simple DFAO, the output is i if and only if the input ends in i , but this need not be the case for more complex DFAOs. \mathtt{0} \mathtt{1} 0 1 0 Figure 3 . F -DFAO generating {\mathbf{f}} 3.4.2. Investigating MAPs in the Fibonacci word with Walnut By running the commands map , imap , lmap and fmap (from Subsection 3.1 ) for the Fibonacci word with fixed values of the difference d , we found the values of A(d) and i(d) for 1\leq d\leq 234 as listed in Table 2 . The A(d) values are listed as sequence A339949 on the OEIS [ 26 ] . Note that when encoding propositions for the Fibonacci word, ?msd_fib is recalled each time as the necessary numeration system of choice. d A(d) i(d) d A(d) i(d) d A(d) i(d) d A(d) i(d) d A(d) i(d) d A(d) i(d) 1 2 2 40 3 7 79 4 7 118 9 20 157 20 32 196 5 11 2 3 3 41 2 0 80 4 16 119 4 2 158 2 2 197 3 7 3 5 20 42 15 20 81 11 87 120 4 3 159 3 11 198 2 0 4 6 16 43 4 23 82 2 2 121 3 2 160 6 20 199 56 28656 5 7 11 44 4 11 83 3 32 122 4 21 161 36 70 200 4 31 6 3 20 45 4 20 84 8 20 123 34 32 162 6 87 201 3 3 7 2 0 46 4 8 85 6 2 124 2 2 163 3 7 202 4 2 8 12 143 47 13 11 86 5 32 125 3 3 164 2 0 203 6 783 9 4 2 48 2 2 87 3 2 126 5 7 165 26 88 204 8 11 10 4 11 49 3 11 88 4 55 127 14 16 166 4 10 205 3 54 11 4 54 50 7 20 89 123 231 128 6 11 167 3 3 206 2 0 12 4 8 51 8 36 90 2 2 129 3 7 168 4 7 207 10 54 13 18 32 52 5 11 91 3 3 130 2 0 169 4 16 208 4 2 14 2 2 53 3 7 92 5 20 131 17 88 170 10 32 209 4 3 15 3 11 54 2 0 93 8 50 132 4 23 171 2 2 210 3 2 16 6 7 55 77 6764 94 7 11 133 4 32 172 3 32 211 4 42 17 20 70 56 4 31 95 3 20 134 4 7 173 8 7 212 27 32 18 5 3 57 3 3 96 2 0 135 4 8 174 6 91 213 2 2 19 3 7 58 5 376 97 13 54 136 12 11 175 4 3 214 3 3 20 2 0 59 6 84 98 4 2 137 2 2 176 3 2 215 6 232 21 30 986 60 8 11 99 4 11 138 3 11 177 4 110 216 28 160 22 4 10 61 3 54 100 4 20 139 7 7 178 62 231 217 6 11 23 3 3 62 2 0 101 4 8 140 6 15 179 2 2 218 3 7 24 4 7 63 10 20 102 16 32 141 5 11 180 3 3 219 2 0 25 4 16 64 4 2 103 2 2 142 3 7 181 5 7 220 20 10945 26 9 11 65 4 3 104 3 11 143 2 0 182 8 16 221 4 10 27 2 2 66 3 2 105 6 7 144 200 75024 183 7 32 222 4 87 28 3 87 67 4 42 106 12 70 145 4 86 184 3 20 223 4 7 29 9 376 68 24 87 107 5 3 146 3 3 185 2 0 224 4 16 30 4 2 69 2 2 108 3 7 147 5 20 186 14 20 225 11 11 31 4 3 70 3 3 109 2 0 148 6 16 187 4 2 226 2 2 32 3 2 71 6 54 110 39 10945 149 8 87 188 4 11 227 3 32 33 4 21 72 78 304 111 4 65 150 3 20 189 4 20 228 8 4180 34 47 87 73 6 11 112 3 3 151 2 0 190 4 8 229 6 2 35 2 2 74 3 7 113 4 7 152 11 20 191 14 11 230 5 32 36 3 3 75 2 0 114 4 3 153 4 2 192 2 2 231 3 2 37 5 7 76 22 2583 115 9 32 154 4 11 193 3 11 232 4 233 38 10 16 77 4 11 116 3 609 155 4 143 194 7 88 233 322 608 39 6 3 78 3 3 117 2 0 156 4 13 195 10 413 234 2 2 Table 2 . Values of A(d) , and i(d) for the Fibonacci word calculated using Walnut . The following simple Lemma 3.11 allows us to always consider \mathtt{0} without loss of generality to be the repeated element in the longest MAP for the Fibonacci word. Lemma 3.11 . In the Fibonacci word {\mathbf{f}} , for all d\geq 1 , f_{i(d)}=\mathtt{0} . Proof. Suppose f_{i(d)}=\mathtt{1} . Then f_{i(d)+k\cdot d}=\mathtt{1} for all 0\leq k=0) => ~(F[j]=F[j+d] & F[j]=F[j+2*d]))"; # Accepts the values of d for which A(d)=2 . The F -DFAO output by this command is shown in Figure 4 . • eval fibad2fpos0or2 "?msd_fib Ad ($fibad2(d)) => (F[0]=F[d] | F[2]=F[2+d])"; # Checks that if A(d)=2 , then either i(d)=0 or i(d)=2 . Walnut returns TRUE. Figure 4 . DFA accepting only the values of d for which A(d)=2 . ∎ Remark 3.13 . The DFA obtained from fibad2 in Figure 4 is also mentioned in Shallit’s book [ 22 , Figure 8.3] , and enumerates sequence A339950 in the OEIS. The converse of a part of Proposition 3.12 that if i(d)=2 then A(d)=2 is FALSE (from Table 2 ), because i(9)=2 but A(9)=4\neq 2 . We claim that the converse of the other part of Proposition 3.12 holds. That is, for all d , if i(d)=0 then A(d)=2 . But since i(d) depends on d and A(d) , it cannot be encoded in Walnut . Fortunately, we are able to prove it in Proposition 4.33 using traditional dynamical methods. Proposition 3.14 . For all d , A(d)=3 if and only if d is accepted by the automaton in Figure 5 . Figure 5 . DFA accepting every d for which A(d)=3 . Proof. We run the following command in Walnut . • def fibad3aut "?msd_fib Ek (F[k]=F[k+d] & F[k]=F[k+2*d]) & (Aj ~(F[j]=F[j+d] & F[j]=F[j+2*d] & F[j]=F[j+3*d]))"; # Accepts d if A(d)=3 . The F -DFAO output by this command is shown in Figure 5 . ∎ Upon enumerating, we find the following sequence of values of d for which A(d)=3 : 2,6,15,19,23,28,32,36,40,49,\dots. (See more values in Table 2 .) As can be seen from the automaton, even though the sequence of accepted values for A(d)=3 is automatic, it is not simple to describe these values, say by an easy-to-understand regular expression. Still, the above suggests that we can similarly produce automata that enumerate all values of d for which A(d)=l for some fixed l . Indeed, this is made precise in Proposition 4.26 . We now investigate the values of A(d) and i(d) for specific families of values of d . Propositions 3.15 and 3.16 completely describe the values of A(d) and i(d) when d=F_{n}-1 and d=F_{n}+1 respectively. Proposition 3.15 . Let d=F_{n}-1 for n\geq 3 . We have: A(d)=\begin{cases}2&\text{ if }n=3,\\ 3&\text{ if }n=4,\\ 6&\text{ if }n=5,\\ 2&\text{ if }n\geq 6,\ n\text{ even},\\ 4&\text{ if }n\geq 7,\ n\text{ odd},\end{cases}\qquad\text{ and }\qquad i(d)=\begin{cases}2&\text{ if }n=3,\\ 3&\text{ if }n=4,\\ 16&\text{ if }n=5,\\ 0&\text{ if }n\geq 6,\ n\text{ even},\\ F_{n-1}&\text{ if }n\geq 7,\ n\text{ odd}.\end{cases} Moreover, we have a partial converse. That is, for all d\geq 1 , the following hold: • A(d)=2 and i(d)=0 if and only if d=F_{n}-1 and n\geq 6 is even; • A(d)=4 and i(d)=F_{n-1} if and only if d=F_{n}-1 and n\geq 7 is odd. Proof. The values of A(d) and i(d) for n=3,4,5 can be checked by hand, or verified from the data presented in Table 2 . Recall fibad2 from the proof of Proposition 3.12 . For all n\geq 6 , we run the following Walnut commands: • reg fiboyes msd_fib "0*10*"; # Accepts all Fibonacci numbers. • reg f_nevenyes msd_fib "0*1(00)*"; # Accepts all even-indexed Fibonacci numbers. • reg f_noddyes msd_fib "0*10(00)*"; # Accepts all odd-indexed Fibonacci numbers. • reg adjfibnodd msd_fib msd_fib "[0,0]*[1,0][0,1]([0,0][0,0])*"; # Accepts all pairs of consecutive Fibonacci numbers (F_{n},F_{n-1}) for n\geq 3 odd. • def fibad4fpos "?msd_fib (F[i]=F[i+d] & F[i]=F[i+2*d] & F[i]=F[i+3*d] & F[i]!=F[i+4*d]) & (Aj (j>=0) => ~(F[j]=F[j+d] & F[j]=F[j+2*d] & F[j]=F[j+3*d] & F[j]=F[j+4*d])) & (Ak (k ~(F[k]=F[k+d] & F[k]=F[k+2*d] & F[k]=F[k+3*d]))"; # Accepts all pairs (d,i) for which A(d)=4 , and the starting position of the first MAP of length 4 is i . • eval prop_neven "?msd_fib Ad ($fiboyes(d+1) & d>=7) => ($fibeven(d+1) <=> ($fibad2(d) & F[d]=F[0]))"; # This checks that for all d=F_{n}-1\geq 7 , n is even if and only if A(d)=2 and i(d)=0 . Walnut returns TRUE. • eval prop_nodd "?msd_fib Ad ($fiboyes(d+1) & d>=12) => ($fibodd(d+1) <=> Ei ($fibad4fpos(d,i) & $adjfibnodd(d+1,i)))"; # Checks that for all d=F_{n}-1\geq 12 , n is odd if and only if A(d)=4 and i(d)=F_{n-1} . Walnut returns TRUE. ∎ Proposition 3.16 . Let d=F_{n}+1 for n\geq 0 . We have: A(d)=\begin{cases}2&\text{ if }n=0,\\ 3&\text{ if }n=1,2,5,\\ 5&\text{ if }n=3,\\ 6&\text{ if }n=4,\\ 4&\text{ if }n\geq 6,\ n\text{ even},\\ 2&\text{ if }n\geq 7,\ n\text{ odd},\end{cases}\qquad\text{ and }\qquad i(d)=\begin{cases}2&\text{ if }n=0,\\ 3&\text{ if }n=1,2,\\ 20&\text{ if }n=3,5,\\ 16&\text{ if }n=4,\\ F_{n-1}-3&\text{ if }n\geq 6,\ n\text{ even},\\ 2&\text{ if }n\geq 7,\ n\text{ odd}.\end{cases} The proof follows similarly to the proof of Proposition 3.15 and so we leave this as a Walnut exercise for the interested reader. ∎ Proposition 3.17 . Let d=F_{n}+2 for n\geq 0 . We have: A(d)=\begin{cases}3&\text{ if }n=0,\\ 5&\text{ if }n=1,2,\\ 6&\text{ if }n=3,\\ 7&\text{ if }n=4,\\ 2&\text{ if }n=5,\\ 4&\text{ if }n=6,\\ 3&\text{ if }n\geq 7,\end{cases}\qquad\text{ and }\qquad i(d)=\begin{cases}3&\text{ if }n=0,\\ 20&\text{ if }n=1,2,\\ 16&\text{ if }n=3,\\ 11&\text{ if }n=4,6,7,\\ 0&\text{ if }n=5,\\ 3&\text{ if }n\geq 8.\end{cases} In particular, if d=2 or d=F_{n}+2 for some n\geq 8 , then A(d)=i(d)=3 . Again, the proof is left as an exercise in Walnut . ∎ Remark 3.18 . The observant reader may have sought some special families of values of d for which A(d)=3 in Figure 5 . One such loop in Figure 5 reads the accepted value of d in Zeckendorf representation as F_{n}+2 as mentioned in Proposition 3.17 . Note that there exist other values of d for which A(d)=i(d)=3 , not covered by the above proposition. For example, d=70\neq F_{n}+2 for some n , while A(70)=i(70)=3 . The classification of all such values can be done in Walnut in a similar fashion to Proposition 3.14 . Note that this is not the full extent of our investigation of the values of A(d) . In the next section we address a method that applies to all values of d simultaneously. Moreover, the techniques that we introduce can also be applied to determining the values of i(d) (see Section 4.5 ). One can formulate similar results to Propositions 3.15 , 3.16 , and 3.17 for A(F_{n}\pm k) and i(F_{n}\pm k) for any choice of k\geq 1 . Notice that we make no mention of the case when k=0 , because A(F_{n}) is not eventually constant, as will be shown in the next section. Nevertheless, there appears to be a simple relationship describing the values of i(d) in this case. Empirical evidence generated by Walnut suggests making the following Conjecture 3.19 . Unfortunately, because A(F_{n}) is not eventually constant, we once again run into the limitation of Walnut ’s inability to handle the multiplication of two variables. Conjecture 3.19 . We have i(F_{2n+1})=F_{2n+3}-2 , and i(F_{2n})=F_{4n}-1 . 4. Dynamically proved results for MAPs in the Fibonacci word 4.1. Maxima of longest MAP lengths In Figure 6 , the values of A(d) are plotted for the first few values of d . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 10 20 30 40 50 d A(d) Figure 6 . Plot of A(d) for the first few values of d ; the overall-peak values of A(d) seem to appear at d=F_{n} as shown with a dotted line. Let k\in{\mathbb{N}} . We observe that local maxima of A(d) appear to occur at values d=F_{n} . Other ‘locally large’ values that are not themselves Fibonacci numbers seem to occur at integer multiples and fractions of Fibonacci numbers, namely when d=kF_{n} and d=F_{n}/k for k\geq 1 . For instance, one can check A(d) values in Table 2 for d=17=F_{9}/2,\,26=2F_{7},\,29=F_{14}/13,\,72=F_{12}/2 . Our goal in this section is to make these observations precise and to use this to completely classify the values of A(d) . We begin with the case that k=1 and so d=F_{n} is a Fibonacci number. 4.1.1. Rotation sequences We recall some basic notation. For a real number \alpha , let \{\alpha\} denote its fractional part. That is, \alpha=\lfloor\alpha\rfloor+\{\alpha\} , where \lfloor\alpha\rfloor=\max\{n\in{\mathbb{Z}}\mid n\leq\alpha\} is the floor function. We also recall the following well-known identities describing relationships between consecutive Fibonacci numbers F_{n} for n\geq 2 involving the golden ratio \tau=\frac{1}{2}(1+\sqrt{5}) . \displaystyle\tau F_{n-1}+F_{n-2} \displaystyle=\tau^{n} (1) \displaystyle F_{n+1}-\tau F_{n} \displaystyle=\frac{(-1)^{n}}{\tau^{n}} (2) For d=F_{n} , we observe that A(F_{n}) appears to be given by \lceil\tau^{n-1}\rceil . It is unclear if this statement can be encoded in first-order Presburger arithmetic, and so we are unable to employ automatic tools like Walnut in attempting to demonstrate this equality. The next result provides an equivalent formulation of the Fibonacci word as a Sturmian word, also known as a rotation sequence . Let I_{0}=(\tau^{-2},1) and I_{1}=[0,\tau^{-2}) . These intervals correspond to the reading of a \mathtt{0} or \mathtt{1} in the Sturmian word of slope \tau^{-1} . Proposition 4.1 ( [ 9 , Prop. 6.1.17] ) . For all m\geq 0 , the m -th term in the Fibonacci word {\mathbf{f}} is given by f_{m}=\begin{cases}\mathtt{0}&\text{if }\{(m+1)\tau\}\in I_{0}\\ \mathtt{1}&\text{if }\{(m+1)\tau\}\in I_{1}.\end{cases} For example, as shown in Figure 7 , the positions of \{(m+1)\tau\} for m=0,1,2,3,4,5 in [0,1) give f_{0}=\mathtt{0},f_{1}=\mathtt{1},f_{2}=\mathtt{0},f_{3}=\mathtt{0},f_{4}=\mathtt{1},f_{5}=\mathtt{0} respectively. 0 1 \{\tau\} \{2\tau\} \{3\tau\} \{4\tau\} \{5\tau\} \{6\tau\} I_{1} I_{0} Figure 7 . Generating the Fibonacci word using Proposition 4.1 . The next lemma follows easily from the formulation of {\mathbf{f}} as a rotation sequence in Proposition 4.1 . Lemma 4.2 . Fix d\geq 1 . There exists a length- \ell MAP of difference d on the symbol j\in\{\mathtt{0},\mathtt{1}\} in {\mathbf{f}} starting at f_{i-1} if and only if all of the points \{i\tau\},\{(i+d)\tau\},\{(i+2d)\tau\},\ldots,\{(i+(\ell-1)d)\tau\} belong to the interval I_{j} . The next examples illustrate this correspondence given in Lemma 4.2 between segments of orbits and MAPs. Example 4.3 . For d=F_{4}=3 , p\geq 0 and i=21 , the maximum number of successive points in I_{0} are 5 , and the points \{i-F_{4}\tau\} and \{i+\ell F_{4}\tau\} are in I_{1} , as shown in Figure 8 . That is, A(F_{4})=5 . 0 1 \{18\tau\} \{21\tau\} \{24\tau\} \{27\tau\} \{30\tau\} \{33\tau\} \{36\tau\} \tau^{-2} \tau^{-1} Figure 8 . A segment of the orbit (\{(18+3n)\tau\})_{n\geq 0} illustrating that A(3)=5 . Example 4.4 . For d=F_{5}=5 and i=12 , we get A(F_{5})=7 as shown in Figure 9 . 0 1 \{7\tau\} \{12\tau\} \{17\tau\} \{22\tau\} \{27\tau\} \{32\tau\} \{37\tau\} \{42\tau\} \{47\tau\} \tau^{-2} \tau^{-1} Figure 9 . A segment of the orbit (\{(12+5n)\tau\})_{n\geq 0} illustrating that A(5)=7 . By Weyl’s theorem , as d\tau is irrational for all d\geq 1 , the sequence of points (\{(i+md)\tau\})_{m\geq 0} are dense and uniformly distributed in [0,1) . Then an immediate consequence of Lemma 4.2 and Weyl’s theorem is that MAPs in {\mathbf{f}} are all finite in length, as any orbit of the form (\{(i+nd)\tau\})_{n\geq 0} must transition between the intervals I_{0} and I_{1} infinitely often. This provides a simple proof in the special case of {\mathbf{f}} (and indeed any Sturmian word) of a more general result of Durand and Goyeneche [ 7 , Proposition 8] . Proposition 4.5 . The Fibonacci word admits no infinite MAP. ∎ Therefore, A(d) always takes finite values. In order to determine exact values for A(d) , it is useful to analyse the pairwise distances between consecutive points of the form \{(i+nd)\tau\} and \{(i+(n+1)d)\tau\} for some n\in{\mathbb{Z}} in an orbit. Let g(d) denote the step distance defined by g(d)=\min\left(\{d\tau\},1-\{d\tau\}\right). (3) Note that g(d)=\|d\tau\| , where \|x\|=\min|x-{\mathbb{Z}}| , which is a common notation from Diophantine approximation denoting the distance to the nearest integer. One should consider two cases that are illustrated in Figure 10 ; either \{d\tau\}<0.5 , in which case we are stepping to the right by a distance of g(d) , or else \{d\tau\}>0.5 , in which case we are stepping to the left by a distance of g(d) . 0 \tau^{-2} 1 \tau^{-2} \{d\tau\}<0.5 g(d) \{d\tau\}>0.5 g(d) Figure 10 . Illustrating when steps are taken to the right or the left. Suppose that each of the points \{i\tau\},\{(i+d)\tau\},\{(i+2d)\tau\},\ldots,\{(i+(\ell-1)d)\tau\} lies in the interval I_{0} , corresponding to the existence of a MAP of length \ell with difference d by Lemma 4.2 . If g(d) is sufficiently small (such as in Figure 10 ), then consecutive pairs in this orbit segment are a distance g(d) apart. So, these pairs of points are the end points of consecutive touching intervals that are all of length g(d) . Hence, the sum of these lengths, \ell g(d) , must be shorter than the length of I_{0} . Note that |I_{1}|<|I_{0}| and so to maximise the length of a MAP, we may always consider points that fall into I_{0} (compare Lemma 3.11 ). As the orbit \{i\tau\} is dense in [0,1) , if \ell g(d)<|I_{0}| , then there exists a point \{i\tau\}\in I_{0} as close as we like to an end point of the interval I_{0} (which end point depends on if we are jumping to the left or the right) so that we can ensure that all of the points \{i\tau\},\{(i+d)\tau\},\{(i+2d)\tau\},\ldots,\{(i+(\ell-1)d)\tau\} also fall into the interval I_{0} . This means that \ell g(d)<|I_{0}| implies the existence of a MAP of length \ell with distance d . As soon as \{(i+(\ell-1)d)\tau\} falls strictly within a distance g(d) of the other end of I_{0} from \{i\tau\} , the next point \{(i+\ell d)\tau\} must be in I_{1} . This situation is illustrated in Figures 8 and 9 (notice the points \{33\tau\} and \{36\tau\} , respectively \{42\tau\} and \{47\tau\} ). Then, any orbit segment of greater length must necessarily enter the interval I_{1} because we have chosen g(d) small enough that one cannot ‘jump over’ the interval I_{1} . This means that there is no MAP of length \ell+1 with distance d . In other words, A(d)=\ell . Of course, this argument only holds if g(d) is small enough, and in particular if g(d)<\tau^{-2} , as in this range, consecutive points in an orbit cannot jump over I_{1} in order to land back into I_{0} . It is therefore necessary to consider two distinct cases; we either have 0\leq g(d)<\tau^{-2} or \tau^{-2}\leq g(d)\leq 0.5 . The above argument holds in the first case, so we have that A(d) satisfies (A(d)-1)g(d)<|I_{0}|\text{ and }A(d)g(d)\geq|I_{0}|. As |I_{0}|=\tau^{-1} , this gives the following classification of A(d) in this case. Theorem 4.6 . For g(d)<\tau^{-2} , A(d)=\left\lfloor\frac{|I_{0}|}{g(d)}\right\rfloor+1=\left\lceil\frac{|I_{0}|}{g(d)}\right\rceil=\left\lceil\frac{\tau^{-1}}{g(d)}\right\rceil. ∎ Note that |I_{0}|/g(d) is never an integer. Hence, the second equality in the above holds. It is sometimes useful to consider the two ranges that g(d) falls into instead as ranges that \{d\tau\} falls into. Comparing the definitions of g(d) and \{d\tau\} then gives the following. Lemma 4.7 . We have \displaystyle g(d)\in[0,\tau^{-2}) \displaystyle\quad\Longleftrightarrow\quad\{d\tau\}\in[0,\tau^{-2})\cup(\tau^{-1},1], \displaystyle g(d)\in[\tau^{-2},0.5] \displaystyle\quad\Longleftrightarrow\quad\{d\tau\}\in[\tau^{-2},\tau^{-1}]. Remark 4.8 . It is easy to show that for all d\geq 1 the only value of d for which \{d\tau\} is a boundary point of any of the above intervals is when d=1 , since \{\tau\}=\tau^{-1} . So, it is not so important if the intervals in the above ranges are open or closed. Similarly, one can show that \{d\tau\} never divides into \tau^{-1} a non-trivial integer number of times, which is useful to know when discussing A(F_{n}/k) later. Before proving the analogue of Theorem 4.6 in the case g(d)\in[\tau^{-2},0.5] , we analyse an important family of differences that fall into the g(d)\leq\tau^{-2} case; namely, we consider the case that d is a Fibonacci number. Corollary 4.9 . For all n\geq 2 , g(F_{n})=\tau^{-n} and A(F_{n})=\left\lceil\tau^{n-1}\right\rceil . Proof. By Equation 2 , we have \{F_{n}\tau\}=\left\{F_{n+1}-\frac{(-1)^{n}}{\tau^{n}}\right\}. In particular, if n is odd, then \{F_{n}\tau\}=\tau^{-n}\in[0,\tau^{-2}] , and if n is even, then \{F_{n}\tau\}=\{1-\tau^{-n}\}=1-\tau^{-n}\in[\tau^{-1},1] . So, by Lemma 4.7 and the definition of g(d) , we get g(F_{n})=\tau^{-n}. Finally, we use Theorem 4.6 to conclude that A(F_{n})=\left\lceil\frac{\tau^{-1}}{g(F_{n})}\right\rceil=\left\lceil\frac{\tau^{-1}}{\tau^{-n}}\right\rceil=\left\lceil\tau^{n-1}\right\rceil. ∎ Remark 4.10 . Notice that it is not always true that A(d)=\lceil\tau^{n-1}\rceil implies d=F_{n} . For example, A(6)=3 , where 3=\lceil\tau^{n-1}\rceil for n=3 , but 6 is not a Fibonacci number. Remark 4.11 . Using the theory of model sets , Aedo et al. provided an independent proof of Corollary 4.9 in their unpublished work [ 1 ] . They gave the formulation A(F_{n})=F_{n-2}+\lceil\tau F_{n-1}\rceil , which can be easily shown to be equivalent to ours by Equation 1 . From Corollary 4.9 and a simple application of Binet’s formula, we obtain the following asymptotic result describing the slope shown in Figure 6 , which tracks the linear growth rate of A(d) when d is a Fibonacci number. Corollary 4.12 . \lim_{n\to\infty}\frac{A(F_{n})}{F_{n}}=\lim_{n\to\infty}\frac{\left\lceil\tau^{n-1}\right\rceil}{F_{n}}=\sqrt{5}\tau^{-1}\approx 1.3819\ldots. 4.2. Multiples of Fibonacci numbers The following lemma is a natural extension of what the step distance looks like for an integer multiple of d , and hence will prove useful when determining A(nd) . Lemma 4.13 . We have g(nd)=\min(\{ng(d)\},1-\{ng(d)\}). Proof. First, it is well known that for n\in{\mathbb{Z}} and x\in{\mathbb{R}} , \displaystyle\{n\{x\}\} \displaystyle=\{nx\}\qquad\text{and} \displaystyle\{-x\} \displaystyle=1-\{x\}. Now, by definition of step distance from Equation 3 , \displaystyle g(nd) \displaystyle=\min(\{nd\tau\},1-\{nd\tau\}) \displaystyle=\min(\{n\{d\tau\}\},1-\{n\{d\tau\}\}). If g(d)=\{d\tau\} , we have g(nd)=\min(\{ng(d)\},1-\{ng(d)\}); and if g(d)=1-\{d\tau\} , we have \displaystyle g(nd) \displaystyle=\min(\{n(1-g(d))\},1-\{n(1-g(d))\}) \displaystyle=\min(\{-ng(d)\},1-\{-ng(d)\}) \displaystyle=\min(1-\{ng(d)\},1-(1-\{ng(d)\})) \displaystyle=\min(1-\{ng(d)\},\{ng(d)\}). ∎ The following proposition uses Theorem 4.6 and Corollary 4.9 to generalise the formula for A(F_{n}) to A(kF_{n}) given a small enough multiplier k and large enough index n . Proposition 4.14 . Let k\in{\mathbb{N}} and N be such that k\leq\tau^{N-2} . For all n\geq N , A(kF_{n})=\left\lceil\frac{A(F_{n})}{k}\right\rceil=\left\lceil\frac{\tau^{n-1}}{k}\right\rceil. Proof. As k\leq\tau^{N-2} , then g(F_{n})\leq\tau^{-2}/k for all n\geq N . We therefore also have kg(F_{n})=g(kF_{n}) , as kg(F_{n})\leq 0.5 . So, g(kF_{n})\leq\tau^{-2} and we can apply Theorem 4.6 . This gives A(kF_{n})=\left\lceil\frac{\tau^{-1}}{g(kF_{n})}\right\rceil=\left\lceil\frac{\tau^{-1}}{kg(F_{n})}\right\rceil=\left\lceil\frac{\tau^{n-1}}{k}\right\rceil=\left\lceil\frac{A(F_{n})}{k}\right\rceil. ∎ We now classify A(d) for the remaining case that g(d)\in[\tau^{-2},0.5] . Theorem 4.15 . If d\geq 2 and \tau^{-2}\leq g(d)\leq 0.5 , then A(d)=2\left\lceil\frac{\tau^{-1}-g(d)}{g(2d)}\right\rceil. Proof. Without loss of generality, we may assume that \{d\tau\}<0.5 so that we are jumping to the right. The case \{d\tau\}>0.5 is completely analogous. Choose i such that 1-g(d)-g(2d)<\{i\tau\}<1-g(d) . Then we have \{i\tau\}+g(d)<1 and \{i\tau\}-kg(2d)\geq\tau^{-2} for some k and by construction, no other starting interval satisfies these inequalities for a larger value of k . That is, k is maximal with this property. The first inequality means that the next point \{i\tau\}+g(d)=\{(i+d)\tau\} lands just before the point 1 , and so remains in I_{0} . The next point \{(i+2d)\tau\} avoids falling in I_{1} because g(d)>\tau^{-2} and \{(i+d)\tau\} is within some small enough \epsilon of the point 1 . See Figure 11 . \tau^{-2} {\scriptstyle 1-g(d)} \{i\tau\} \{(i+d)\tau\} \tau^{-2} {\scriptstyle 1-g(d)} \{i\tau\} \{(i+d)\tau\} \times {\scriptstyle g(2d)} Figure 11 . Two clusters of points in the orbit segment form when g(d)>\tau^{-2} due to the ability for consecutive points to ‘jump over’ the shorter interval I_{1} . Now, by Lemma 4.13 , we know that every (n+2) -th point falls g(2d) to the left of the n -th point. This continues until a point \{(i+2kd)\tau\}=\{i\tau\}-2kg(2d) falls within a distance g(2d) to the right of \tau^{-2} . Then, the next point \{(i+(2k+1)d)\tau\} is the last consecutive point that appears in I_{0} because we necessarily have \{(i+(2k+2)d)\tau\}<\tau^{-2} by the maximality of k . So, the points in the orbit segment fall into one of two equal-sized clusters of points that appear towards either end of the interval I_{0} (see, e.g., Figure 12 ), with each cluster containing exactly k+1 points. It follows that A(d)\geq 2(k+1) . Since we have k\leq\frac{\{i\tau\}-\tau^{-2}}{g(2d)}\leq\frac{1-g(d)-\tau^{-2}}{g(2d)}=\frac{\tau^{-1}-g(d)}{g(2d)}, then for k to be maximal, we have k=\left\lfloor\frac{\tau^{-1}-g(d)}{g(2d)}\right\rfloor, which gives A(d)\geq 2\left(\left\lfloor\frac{\tau^{-1}-g(d)}{g(2d)}\right\rfloor+1\right)=2\left\lceil\frac{\tau^{-1}-g(d)}{g(2d)}\right\rceil because g(2d) never divides \tau^{-1}-g(d) an integer number of times for d\geq 2 . This can be seen by observing that \tau^{-1}-g(d)=\tau^{-1}-0.5+\frac{1}{2}g(2d) together with the fact that g(2d)\in\mathbb{Z}[\tau] . In order to see that in fact this is the maximal value of A(d) , we notice that any other starting point gives rise to an orbit segment that either satisfies the same conditions as \{i\tau\} (so gives rise to a MAP of the same length), or else must enter I_{1} earlier because the orbit segment will be a translate of the orbit segment starting at position \{i\tau\} and k was chosen maximally. ∎ So, Theorems 4.6 and 4.15 together allow us to determine A(d) for any d\geq 1 . Note that if g(d)\in[\tau^{-2},0.5] , then g(2d)=1-2g(d) , so A(d) can also be written as either A(d)=2\left\lceil\frac{\tau^{-1}-g(d)}{1-2g(d)}\right\rceil\quad\text{or}\quad A(d)=2\left\lceil\frac{\tau^{-1}-0.5+\frac{1}{2}g(2d)}{g(2d)}\right\rceil, so one only needs to compute either g(d) or g(2d) , not both. Example 4.16 . Given d=148 , we get A(148)=6 and Figure 12 shows the distribution of points starting at i=17 . The step distance between the adjacent points in each cluster is g(296) . 0 1 0 1 2 3 4 5 6 -1 \tau^{-2} \tau^{-1} Figure 12 . Counting the repetition of \mathtt{0} to find A(148) ; the points \{(i+nd)\tau\} are denoted only by n for convenience. It is apparent from Figure 6 that the values A(F_{n}) achieve new maxima of A(d) over all 1\leq d\leq F_{n} . To prove this, we employ a version of the three-gap theorem in the specific case of the rotation being given by \tau . A suitable reference for this special case appears in work of Ravenstein [ 20 , Section 3] , which we provide here. Theorem 4.17 ( [ 20 ] ) . The set of points P_{d}=\{\{i\tau\}\mid 1\leq i\leq d\} partition the circle [0,1]/\{0,1\} into intervals taking at most 3 distinct lengths. If F_{n-1}\leq d0.5 and \{\tau^{2n+1}\}<0.5 for all n\geq 2 . ∎ Note that this formula simplifies to \lceil\tau^{n-3}\rceil+1 if n\equiv 0\pmod{6} and simplifies to \lceil\tau^{n-3}\rceil+2 if n\equiv 3\pmod{6} . By applying Binet’s formula, the above result gives an asymptotic for the slope of the line passing through the peaks of A(d) for d=F_{n}/2 . We get Corollary 4.20 . \lim_{n\to\infty}\frac{A(F_{n}/2)}{F_{n}/2}=\lim_{n\to\infty}2\left\lceil\frac{1}{2}\tau^{n-3}+1/2\right\rceil\frac{2}{F_{n}}=2\sqrt{5}\tau^{-3}\approx 1.0557\ldots.\qed Using an analysis similar to that in the proof of Corollary 4.18 , one can show that for all d0 . However, this is a contradiction as k is an integer, while \tau^{N_{k}} is irrational. We could have also used the fact that F_{m_{i}}|F_{n_{i}} if and only if m_{i}|n_{i} , which can only hold for finitely many pairs (n_{i},m_{i}) , as n_{i}-m_{i} is eventually constant and equal to N_{k} . Hence m_{i}|m_{i}+N_{k} , meaning m_{i}|N_{k} . However, N_{k} admits only finitely many factors. We conclude that 0 cannot be a cluster point of g(F_{n}/k) and so the set of possible cluster points is a subset of \{i/k\mid 1\leq i\leq\lfloor k/2\rfloor\} . We therefore have the following result. Proposition 4.21 . Let k\geq 3 be fixed. And let \alpha(k) be the rank of k . The sequence (g(F_{n\alpha(k)}/k))_{n\geq 1} admits at most \lfloor k/2\rfloor cluster points, none of which is 0 .∎ Similar reasoning shows that g(2F_{n}/k) also admits finitely many cluster points, none of which is 0 . In particular, Theorems 4.6 and 4.15 give A(d) as functions that only take large values in the case that either g(d) or g(2d) are small. However, in both cases, g(F_{n}/k) and g(2F_{n}/k) never have 0 as a cluster point, and so A(F_{n\alpha(k)}/k) is uniformly bounded for a fixed k . Proposition 4.22 . Let k\geq 3 be fixed and let \alpha(k) be the rank of k . \{A(F_{n\alpha(k)}/k)\mid n\geq 1\} takes finitely many values.∎ Thankfully, in the case that k=3 , we still have g(F_{n}/3)\to 1/3 , and so we can treat this case similarly to the case of k=2 . We have \alpha(3)=4 and so we consider the Fibonacci numbers with index a multiple of 4 . We find that g(F_{4n}/3)\to 1/3 . F_{4}/3=1 and so this case is trivial. For n=2 , already we have g(F_{8}/3)=g(7)\approx 0.326\in[0,\tau^{-2}] and |g(F_{4n}/3)-1/3| monotonically decreases, so we are always in the case that we can apply Theorem 4.6 . Also, we have 0.326\leq g(F_{4n}/3)\leq 0.341 by the above monotonicity. It follows that, for n\geq 2 , we have A(F_{4n}/3)=\left\lceil\frac{\tau^{-1}}{g(F_{4n}/3)}\right\rceil=2, because the inequality 0.326\leq g(F_{4n}/3)\leq 0.341 gives 1.812\leq\tau^{-1}/g(F_{4n}/3)\leq 1.896 . We can check this in Walnut : • reg fib4n msd_fib "0*100(0000)*"; # This accepts F_{4n} for all n>0 . • def fib4nby3 "?msd_fib Ek ($fib4n(k) & k=3*n)"; # This only accepts F_{4n}/3 for all n>0 . • eval isfibcheck "?msd_fib An (n>=0) => ($fib4nby3(n) & $fiboyes(n))"; # Checks if F_{4n}/3 is F_{m} for some m ; returns FALSE. • eval fib4nby3ad2check "?msd_fib Ad (d>0 & $fib4nby3(d) => $fibAd2(d))"; # Checks if all A(F_{4n}/3)=2 ; returns TRUE. We may similarly use Walnut to get the following list of A(F_{n}/k) values for the first few k , which would be laborious to prove using the methods we employed in the k=2 and k=3 case because g(d) can (a priori) take more than one value 2 2 2 Nevertheless, sometimes, as in the case for k=5 , even though g(F_{n}/k) has more than one cluster point, A(F_{n}/k) still only takes one value. : Proposition 4.23 . We have • A(F_{4n}/3)=2 for all n\geq 1 • A(F_{6n}/4)=3 for all n\geq 1 • A(F_{5n}/5)=4 for all n\geq 2 (and A(F_{5}/5)=2 ) • A(F_{12n}/6)=4 for all n\geq 1 • A(F_{8n}/7)=5 for all n\geq 1 • A(F_{6n}/8)\in\{2,5\} for all n\geq 1 (in particular, A(F_{12n-6}/8)=2 and A(F_{12n}/8)=5 ) • A(F_{12n}/9)=6 for all n\geq 1 • A(F_{15n}/10)\in\{3,7\} for all n\geq 1 (in particular, A(F_{30n-15}/10)=3 and A(F_{30n}/10)=7 ) So, the first k for which A(F_{n}/k) takes more than one value infinitely often is k=8 . The reason we were so interested in finding families of d for which A(d) is constant or at least takes only finitely many values was two-fold: first, if A(d) is constant for the family, then one can use Walnut to prove properties about the entire family simultaneously (for instance finding automata that describe i(d) , the earliest index at which a longest arithmetic progression appears); secondly, it was hoped that if enough values of A(d) could be shown to be small, then it would be possible to improve the asymptotic bounds on A(d) . Unfortunately, we were not able to realise the second point and so we leave this as a conjecture. Conjecture 4.24 . For all d\geq 1 , \frac{A(d)-1}{d}<\frac{\sqrt{5}}{\tau}. The appearance of ‘ -1 ’ in the numerator takes into account that while A(F_{n})/F_{n}\to\sqrt{5}\tau^{-1} , this convergence is from above. So these ratios appear to overestimate the slope with error uniformly bounded above by 1 . For non-Fibonacci values of d , this correction term should not be necessary. 4.4. The step distance ranges We now pivot to investigate the function g(d) in more detail. Corollary 4.25 . If \tau^{-2}\tau^{-2} . For example, when A(d)=4 , along with g(d)\in(\tau^{-1}/4,\tau^{-1}/3) , we also have the interval g(d)\in\left(\tau^{-2},\frac{2-\tau^{-1}}{3}\right) using the formula for A(d) from Theorem 4.15 . The general result is the following. Proposition 4.26 . Let k\geq 3 . If k is odd, then A(d)=k if and only if g(d)\in\left(\frac{\tau^{-1}}{k},\frac{\tau^{-1}}{k-1}\right); and if k is even, then A(d)=k if and only if g(d)\in\left(\frac{\tau^{-1}}{k},\frac{\tau^{-1}}{k-1}\right)\cup\left(\frac{k-2\tau}{2k-6},\frac{k-2\tau^{-1}}{2k-2}\right). Proof. For this, we consider the range of g(d) and use the corresponding A(d) formulae given in Theorems 4.6 and 4.15 respectively. In particular, we first substitute A(d)=k into each formula and remove the ceiling to find the lower limit of g(d) . Then for the upper limit, we repeat the process but instead substitute A(d)=k+1 . Since A(d) is always even for g(d)>\tau^{-2} (Corollary 4.25 ), only one formula for A(d) applies in the case that A(d)=k is odd, giving rise to a single interval coming from Theorem 4.6 . In the case that A(d) is even, there are corresponding values of g(d) in both of the intervals [0,\tau^{-2}) and [\tau^{-2},0.5] . Whence, we obtain a union of two disjoint g(d) ranges when A(d)=k is even, corresponding to the two different formulae for A(d) coming from both Theorem 4.6 and Theorem 4.15 . ∎ Remark 4.27 . Notice that since the ranges of g(d) except for the first case of A(d)=2 are always open. This means that for k\geq 2 , the isolated points \tau^{-1}/k and \frac{k-2\tau}{2k-6} on the range of g(d) are avoided. An immediate consequence of this result is that A(d) takes all possible values and indeed infinitely often because the sequence g(d) is dense in [0,0.5] . Proposition 4.28 . For all k\geq 2 , there exist infinitely many d\geq 1 such that A(d)=k .∎ We can further show the density of values of d for which A(d)=k for a fixed k\geq 1 . Let \mathrm{dens}_{\,{\mathbf{f}}}(k)=\lim_{n\to\infty}\frac{\#\left\{d\in\{1,\dots,n\}\mid A(d)=k\right\}}{n}. In order to calculate the density, we first need to show that not only is the orbit of g(d) dense in [0,0.5] , but it is also uniformly distributed. Proposition 4.29 . The values of g(d) are uniformly distributed in the interval [0,0.5] . Proof. Recall the definition of step distance, g(d)=\min\{\{d\tau\},1-\{d\tau\}\} . So we may interpret g as a function g\colon{\mathbb{N}}\to[0,0.5] . We know that the function r_{\tau}\colon{\mathbb{N}}\to[0,1] given by r_{\tau}\colon d\mapsto\{d\tau\} is uniformly distributed in [0,1] by Weyl’s theorem, as \tau is irrational. Now let h\colon[0,1]\to[0,0.5] denote the function h(x)=\begin{cases}x\,&\text{ if }\>00.50.5 then i(d)=2 . Proof. For all d , if A(d)=2 , then by Proposition 4.26 , the possible step distance range is g(d)\in(\tau^{-1}/2,\tau^{-2}] . Now, there are two ways we can have g(d) in the above range. From Figure 10 , recall if \{d\tau\}<0.5 and if the points x_{n}=\{nd\tau\} and x_{n+1}=\{(n+1)d\tau\} are both in I_{0} , then x_{n+1}>x_{n} , so we are stepping to the right; otherwise we are stepping to the left. We should determine the interval of starting positions within I_{0} of orbits that correspond to longest arithmetic progressions of length exactly 2 . We consider each case in turn. Case 1 ( \{d\tau\}<0.5 ): In this case, we are stepping to the right. Therefore, such a starting position must satisfy (see Figure 14 ) the following conditions: (1) we start in I_{0} , (2) by stepping to the left we enter I_{1} , (3) we are able to step exactly once to the right remaining in I_{0} , (4) a second step places us outside of I_{0} . Let \hat{x}\in I_{0} be such a starting point. Hence, \hat{x} must satisfy the following four inequalities (i) \tau^{-2}<\hat{x}<1 (ii) \hat{x}-g(d)<\tau^{-2} (iii) \hat{x}+g(d)<1 (iv) \hat{x}+2g(d)>1 0 \tau^{-2} 1 \tau^{-2} \hat{x} g(d) g(d) g(d) Figure 14 . A potential starting position \hat{x} corresponding to the case A(d)=2 and \{d\tau\}<0.5 . Figure 14 illustrates which subinterval of I_{0} we are considering to find a suitable \hat{x} . Solving the system of inequalities, together with the fact that \tau^{-1}/2\leq g(d)\leq\tau^{-2} , we get that j\in(\tau^{-2},1-\frac{\tau^{-1}}{2}) . The least value of n for which \{n\tau\}\in(\tau^{-2},1-\frac{\tau^{-1}}{2}) is n=1 . Hence, i(d)=0 . Case 2 ( \{d\tau\}>0.5 ): In this case, we are stepping to the left, otherwise it works similarly. We find that a starting position must satisfy the following conditions: (1) we start in I_{0} , (2) by stepping to the right we enter I_{1} , (3) we are able to step exactly once to the left remaining in I_{0} , (4) a second step places us outside of I_{0} . Let \hat{x}\in I_{0} be such a starting point. Hence, \hat{x} must satisfy the following four inequalities (i) \tau^{-2}<\hat{x}<1 (ii) 1-\hat{x}\tau^{-2} (iv) \hat{x}-2g(d)<\tau^{-2} Solving the system of inequalities, together with the fact that \tau^{-1}/2\leq g(d)\leq\tau^{-2} , we get that \hat{x}\in(1-\frac{\tau^{-1}}{2},1) . The least value of n for which \{n\tau\}\in(1-\frac{\tau^{-1}}{2},1) is n=3 . Hence, i(d)=2 . ∎ Remark 4.32 . Notice that, in Figure 4 , the accepting states 1 and 7 correspond to the values of d for which A(d)=2 . Walnut can be used to show that the accepting state 1 corresponds to the values of d where i(d)=2 , and the accepting state 7 corresponds to the values of d where i(d)=0 . Also, from Proposition 4.31 , the accepting states 1 and 7 equivalently correspond to the values of d for which \{d\tau\}>0.5 and \{d\tau\}<0.5 respectively. Proposition 4.33 (Partial converse of Proposition 3.12 ) . For all d , if i(d)=0 then A(d)=2 . Proof. Suppose, A(d)\geq 3 . Then Proposition 4.26 implies g(d)\in(0,\tau^{-1}/2]\cup(\tau^{-2},0.5) . If i(d)=0 , that is, if one begins at the point \{\tau\} , then we have two cases: firstly, for g(d)\in(0,\tau^{-1}/2] , there is always room for more points to fit inside I_{0} by shifting the first point to either side, which means i(d) cannot be 0 ; secondly, for g(d)\in(\tau^{-2},0.5) , when one begins at \{\tau\} , the next point will always appear in I_{1} , which implies that A(d)=1 , which is a contradiction. ∎ Proposition 4.34 (Part of Proposition 3.17 ) . For d=F_{n}+2 for some n\geq 8 , A(d)=i(d)=3 . Proof. We have from Corollary 4.9 that \{2\tau\}=g(F_{3})=\tau^{-3} and g(F_{8})=\tau^{-8} . So for d=F_{n}+2 for n\geq 8 , we have g(F_{n}+2)=\{(F_{n}+2)\tau\}\in[\tau^{-3}-\tau^{-8},\tau^{-3}+\tau^{-8}] . This is because \{F_{2n}\tau\}\to 1 from below and \{F_{2n+1}\tau\}\to 0 from above, both monotonically. Since g(F_{n}+2)\leq\tau^{-2} , we use the formula for A(d) from Theorem 4.6 . That is, A(F_{n}+2)=\left\lceil\frac{\tau^{-1}}{g(F_{n}+2)}\right\rceil=3. Since \{(F_{n}+2)\tau\}<0.5 , we always step to the right when counting the MAP (again, see Figure 10 ). Hence we find a candidate starting point \hat{x}\in I_{0} which must satisfy the following inequalities: (i) \tau^{-2}<\hat{x}<1 (ii) \hat{x}-g(F_{n}+2)<\tau^{-2} (iii) \hat{x}+2g(F_{n}+2)<1 (iv) \hat{x}+3g(F_{n}+2)>1 Solving the system of inequalities, we get that \hat{x}\in(\tau^{-2},\tau^{-1}+\tau^{-8}) . The least value of n for which \{n\tau\}\in(\tau^{-2},\tau^{-1}+\tau^{-8}) is n=4 . Hence, i(d)=3 . ∎ In principle, one can prove similar statements for other families of d using analogous methods, although the arguments will become ever increasingly complicated. One can therefore further partition the g(d) intervals identified in Proposition 4.26 into subintervals on which i(d) is constant. For example, it can be shown that A(d)=3 and i(d)=3 if and only if g(d)\in\left(\frac{\tau^{-1}}{3},\frac{1-\{4\tau\}}{2}\right) . The complete general result in this direction requires a careful analysis of the first returns of the orbits (\{nd\tau\})_{n\geq 1} to particular subintervals, the full formulation of which is somewhat more technical and is therefore reserved for the first author’s future output. Declarations GJ received research support from the Open University, UK. DR has no financial interests to declare.