The Thue–Morse Sequence in Base 3/2

F. M. Dekking CWI Amsterdam and Delft University of Technology Faculty EEMCS P.O. Box 5031 2600 GA Delft The Netherlands

                        F.M.Dekking@math.tudelft.nl

Abstract We discuss the base 3/2 representation of the natural numbers. We prove that the sum-of-digits function of the representation is a fixed point of a 2-block substitution on an infinite alphabet, and that this implies that sum-of-digits function modulo 2 of the representation is a fixed point x_{3/2} of a 2-block substitution on {0, 1}. We prove that x_{3/2} is invariant for taking the binary complement, and present a list of conjectured properties of x_{3/2}, which we think will be hard to prove. Finally, we make a comparison with a variant of the base 3/2 representation, and give a general result on p-q-block substitutions.

1 Introduction

A natural number N is written in base 3/2 if N has the form

N = ∑_{i≥0} d_{i}(\frac{3}{2})^{i},  (1)

with digits d_{i} = 0, 1 or 2.

Base 3/2 representations are also known as sesquinary representations of the natural numbers; see Propp [6]. We write these expansions as

SQ(N) = d_{R}(N) ⋯ d_{1}(N)d_{0}(N) = d_{R} ⋯ d_{1}d_{0}.

We have, for example, SQ(7) = 211, since 2 · (9/4) + (3/2) + 1 = 7. See \underline{A024629} for the continuation of Table 1. Ignoring leading 0’s, the base 3/2 representation of a number N is unique (see Section 3).

\begin{matrix}N & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ SQ(N) & 0 & 1 & 2 & 20 & 21 & 22 & 210 & 211 & 212 & 2100 & 2101 \end{matrix}

Table 1: Base 3/2 expansions for N = 1, …, 10.

For N ≥ 0 let

s_{3/2}(N) := ∑_{i=0}^{i=R} d_{i}(N)

be the sum-of-digits function of the base 3/2 expansions. We have (see \underline{A244040})

s_{3/2} = 0, 1, 2, 2, 3, 4, 3, 4, 5, 3, 4, 5, 5, 6, 7, 4, 5, 6, 5, 6, 7, 7, 8, 9, 5, 6, 7, 5, 6, 7, 7, 8, 9, 8, 9, 10, …

In this note we study the base 3/2 analogue of the Thue–Morse sequence \underline{A010060} (where the base equals 2), i.e., the sequence (see \underline{A357448})

(x_{3/2}(N)) := (s_{3/2}(N) mod 2) = 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, …

The Thue Morse sequence is the fixed point starting with 0 of the substitution 0 → 01, 1 → 10. This might be called a 1-2-block substitution.

Let p ≤ q be two natural numbers. A p-q-block substitution κ on an alphabet A is a map κ : A^{p} → A^{q}. A p-q-block substitution κ acts on (A^{p})^{∗} by defining

κ(w_{1}w_{2} ⋯ w_{pm−1}w_{pm}) = κ(w_{1} ⋯ w_{p}) ⋯ κ(w_{pm−p+1} ⋯ w_{pm})

for w_{1}w_{2} ⋯ w_{pm−1}w_{pm} ∈ (A^{p})^{∗} and m = 1, 2, . . .. Its action extends to infinite sequences x = x_{0}x_{1} ⋯ by defining κ : x ↦ y by y_{qm} ⋯ y_{qm+q−1} = κ(x_{pm} ⋯ x_{pm+p−1}) for m = 0, 1, . . ..

Theorem 1. The sequence x_{3/2} is a fixed point of the 2-3-block substitution

κ : \begin{cases}00 & → 010 \\ 01 & → 010 \\ 10 & → 101 \\ 11 & → 101 \end{cases}

Theorem 1 will be proved in Section 2.2.

2 Sum of digits function and Thue–Morse in base 3/2

2.1 Sum of digits function in base 3/2

Let s_{3/2} = (0, 1, 2, 2, 3, 4, 3, 4, 5, 3, 4, 5, 5, 6, 7, 4, 5, …) be the sum-of-digits function of the base 3/2 expansions. To describe this sequence, we extend the notion of a p-q-block substitution to alphabets of infinite cardinality.

Theorem 2. The sequence s_{3/2} is the fixed point starting with 0 of the 2-3-block substitution given by

a, b ↦ a, a + 1, a + 2 for a = 0, 1, 2, … and b = 0, 1, 2, ….

Proof. We have d(0) = 0, d(1) = 1 and from the uniqueness of the base 3/2 expansions it follows immediately that d(3N + r) = d(2N) + r for N ≥ 0 and r = 0, 1, 2.

Thus s_{3/2}(3N) = s_{3/2}(2N), s_{3/2}(3N +1) = s_{3/2}(2N)+1, and s_{3/2}(3N +2) = s_{3/2}(2N)+2. This gives the result.

Remark 3. The base-4/3 version of this sequence is \underline{A244041}; the base-2 version is \underline{A000120}; the base-3 version is \underline{A053735}; the base-10 version is \underline{A007953}.

2.2 Thue–Morse in base 3/2

Proof of Theorem 1. This follows directly from Theorem 2 by taking a and b modulo 2.

Although iterates of κ : 00 → 010, 01 → 010, 10 → 101, 11 → 101 are undefined, we can generate the fixed point x_{3/2} by iteration of a map κ′ defined by κ′(w) = κ(w) if w has even length, and κ′(v) = κ(w) if v = w0 or v = w1 has odd length.

The fact that the iterates of κ are undefined causes difficulty in establishing properties of x_{3/2}. This is similar to the lack of progress in the last 25 years to prove the conjectures on the Kolakoski sequence, which is also a fixed point of a 2-block substitution (cf. the papers [2, 3]). Here is a property that is open for the Kolakoski sequence \underline{A000002}, but can be proved for x_{3/2}.

Proposition 4. If a word w occurs in x_{3/2}, then its binary complement \overline{w} defined by \overline{0} = 1, \overline{1} = 0, also occurs in x_{3/2}.

Proof. First one checks this for all 16 words of length 6 that occur in x_{3/2}. Note that then also \overline{w} occurs for all w with |w| ≤ 6, where |w| denotes the length of w. Let u be a word of length m ≥ 7. By adding at most 3 letters at the beginning and/or end of u one can obtain a word v with |v| = 3n that occurs in x_{3/2} at a position 0 modulo 3. But then Theorem 1 gives that v = κ(w) for at least one word w occurring in x_{3/2}. The length of w is |w| = 2n. Since \overline{κ(w)} = κ(\overline{w}) the result follows by induction on m = |u|. For example, for |u| = m = 7, one has |v| = 9, and so |w| = 6.

Here are some conjectured properties of x_{3/2}.

Conjecture 5. x_{3/2} is reversal invariant, i.e., if the word w = w_{1} ⋯ w_{m} occurs in x_{3/2} then \overleftarrow{w} = w_{m} ⋯ w_{1} occurs in x_{3/2}.

Conjecture 6. x_{3/2} is uniformly recurrent, i.e., each word that occurs in x_{3/2} occurs infinitely often, with bounded gaps between consecutive occurrences.

Conjecture 7. The frequencies μ[w] of the words w occurring in x_{3/2} exist. Two conjectured values: μ[00] = 1/10, μ[01] = 4/10.

Conjecture 8. μ is invariant for binary complements, i.e., μ[w] = μ[\overline{w}] for all words w.

Conjecture 9. μ is reversal invariant, i.e., μ[w] = μ[\overleftarrow{w}] for all words w.

Conjecture 10. (Shallit) The critical exponent (=largest number of repeated blocks) of x_{3/2} is 5.

3 Base 3/2 and base 1/2 · 3/2

Many authors refer to the paper [1] from Akiyama, Frougny, and Sakarovitch for the properties of base 3/2 expansions (see, e.g., Propp [6] and Rigo and Stipulanti [7]). However, the q/p expansions studied in paper [1] are different from the 3/2 expansions that are usually considered as in Equation (1). In the paper [1]:

N = ∑_{i≥0} d_{i} \frac{1}{p}(\frac{q}{p})^{i},  (2)

with digits d_{i} = 0, 1 or 2. We write AFS(N) for the expansion of N. Remark 11. There is a small notational problem here: Akiyama, Frougny, and Sakarovitch write about p/q expansions with p > q, but in this note we consider q/p expansions with p ≤ q. This fits better with the p-q-block substitutions, and with the order of p and q in the alphabet.

Here is the table given in the paper [1] for the case 3/2:

\begin{matrix}N & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ AFS(N) & ε & 2 & 21 & 210 & 212 & 2101 & 2120 & 2122 & 21011 & 21200 & 21202 \end{matrix}

Table 2: Base 1/2 · 3/2 expansions for N = 1, …, 10.

These expansions will not even be found in the OEIS (at the moment).

The situation is clarified in the paper [5] by Frougny and Klouda. They consider both representations, called, respectively, base p/q and base 1/q · p/q representations. In the present note these are called respectively base q/p and base 1/p · q/p representations.

A combination of the results in [1] and [5] yields a proof of the uniqueness of the base 3/2 expansions (QS(N)). There is also a direct proof of uniqueness in the paper by Edgar et al. [4]; see Theorem 1.1.

Note that AFS(N) = QS(2N) for N > 0. So uniqueness of the base 3/2 representation implies immediately uniqueness of the 1/2 · 3/2 representation AFS(N). This observation obviously extends to base q/p.

Next we consider the question whether also the sequence y_{3/2}, the sum-of-digits function modulo 2 of the base 1/2 · 3/2 representation, is a fixed point of a 2-block substitution. This is indeed the case, and this 2-block substitution is given by Rigo and Stipulanti in [7].

Theorem 12. ([7]) y_{3/2} is the fixed point with prefix 00 of the 2-3-block substitution

κ′ : \begin{cases}00 & → 001 \\ 01 & → 000 \\ 10 & → 111 \\ 11 & → 110 \end{cases}

In the paper [7] the proof of Theorem 12 is based on a generalization of Cobham’s theorem to what are called S-automatic sequences built on tree languages with a periodic labeled signature. Here we consider a more direct route, based on a simple closure property of p-q-block substitutions. Recall that a coding is a letter to letter map from one alphabet to another.

Theorem 13. Let x = (x(N)) be a fixed point of a p-q-block substitution. Let r be a positive integer. Then the sequence (x(rN)) is the fixed point of a coding of a p-q-block substitution.

Proof. If x is a fixed point of a p-q-block substitution, then x is also a fixed point of a prqr-block substitution. As new alphabet, take the words of length r occurring in x. On this alphabet, the pr-qr-block substitution induces a p-q-block substitution in an obvious way. Mapping each word of length r to its first letter is a coding that gives the result.

Alternative proof for Theorem 12. Apply Theorem 13 with r = 2. The 4-6-block substitution is given by

0010 → 010101, 0100 → 010010, 0101 → 010010, 0110 → 010101,
1001 → 101010, 1010 → 101101, 1011 → 101101, 1101 → 101010.

Coding 00 ↦ a, 01 ↦ b, 10 ↦ c, 11 ↦ d, this induces the 2-3-block substitution

ac → bbb, ba → bac, bb → bac, bc → bbb, cb → ccc, cc → cdb, cd → cdb, db → ccc.

If we code further a, b ↦ 0, and c, d ↦ 1, then we obtain κ′ from Theorem 12.

4 Acknowledgment

I am grateful to Jean-Paul Allouche for several useful comments. I also thank an anonymous referee for useful remarks.

References

[1] S. Akiyama, C. Frougny, and J. Sakarovitch, Powers of rationals modulo 1 and rational base number systems, Israel J. Math. 168 (2008), 53–91.

[2] F. M. Dekking, What is the long range order in the Kolakoski sequence?, in The Mathematics of Long-Range Aperiodic Order, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Vol. 489, Kluwer Acad. Publ., 1997, pp. 115–125.

[3] F. M. Dekking and M. Keane, Two-block substitutions and morphic words, arxiv preprint arXiv:2202.13548 [math.CO], 2022. Available at https://arxiv.org/abs/2202.13548.

[4] T. Edgar, H. Olafson, and J. Van Alstine, Some combinatorics of rational base representa-

   tions, preprint, 2014. Available at https://community.plu.edu/~edgartj/preprints/
   basepqarithmetic.pdf.

[5] C. Frougny and K. Klouda, Rational base number systems for p-adic numbers, RAIRO Theor. Inform. Appl. 46 (2019), 87–106.

[6] J. Propp, How do you write one hundred in base 3/2? Available at https://tinyurl. com/2p9auyz6. Accessed January 2023.

[7] M. Rigo and M. Stipulanti, Automatic sequences: from rational bases to trees, Disc. Math. Theor. Comput. Sci. 24 (2022), #25.

[8] N. J. A. Sloane et al., On-Line Encyclopedia of Integer Sequences, electronically available

   at https://oeis.org, 2023.

2020 Mathematics Subject Classification: Primary 11B85, Secondary 68R15 Keywords: Base 3/2, Thue–Morse sequence, sum of digits, two-block substitution.

(Concerned with sequences \underline{A000002}, \underline{A000120}, \underline{A007953}, \underline{A010060}, \underline{A024629}, \underline{A053735}, \underline{A244040}, \underline{A244041}, and \underline{A357448}.)

Received February 9 2023; revised version received February 12 2023. Published in Journal of Integer Sequences, February 23 2023.

Return to Journal of Integer Sequences home page.