THE SMALLEST UNIVOQUE NUMBER IS NOT ISOLATED

VILMOS KOMORNIK, PAOLA LORETI, AND ATTILA PETHŐ

Dedicated to the 80th birthday of Professor Lajos Tamássy.

Abstract. Komornik and Loreti [9] showed that there exists a smallest univoque number q′ ≈ 1.787. Later Allouche and Cosnard [1] proved that this number is transcendental. The aim of this note is to construct a (decreasing) sequence of algebraic numbers converging to q′.

1. Introduction

Given a real number 1 ≤ q ≤ 2, there exists at least one sequence (c_{i}) of zeroes and ones satisfying the equality

1 = \frac{c_{1}}{q} + \frac{c_{2}}{q^{2}} + \frac{c_{3}}{q^{3}} + … (1)

One such sequence, denoted by (γ_{i}), can be obtained by the so-called greedy algorithm of Rényi [13]: proceeding by induction, we choose c_{i} = 1 whenever possible. Among all expansions for a given q, this is lexicographically the largest.

If q = 2, then this is the unique possible expansion: c_{i} = 1 for all i. Erdős, Horváth and Joó [5] discovered that there exist also smaller numbers q having this curious uniqueness property; following Daróczy and Kátai [3] we call them univoque numbers. Subsequently, they were characterized algebraically in [6] (see also [10] for an extension of this result):

Theorem 1. A number 1 ≤ q ≤ 2 is univoque if and only if there exists an expansion (γ_{i}) of 1 satisfying the following two conditions (in the lexicographic sense):

(2) γ_{i+1}γ_{i+2} ⋯ < γ_{1}γ_{2} … whenever γ_{i} = 0

and

(3) \overline{γ_{i+1}γ_{i+2} …} < γ_{1}γ_{2} … whenever γ_{i} = 1.

Here and in the sequel we use the notation \overline{c} := 1 − c.

Among several interesting properties of the set U of univoque numbers, for which we refer to the papers [1], [2], [3], [4], [5], [8] and [9], we recall from [9] that there exists a smallest univoque number q′ ≈ 1.787, and the corresponding expansion is given by the truncated Thue–Morse sequence

(τ_{i})_{i=1}^{∞} = 1101 0011 …

Date: July 17, 2002.

Mathematics Subject Classification: 11A63, 11A67, 11B85 Key words and phrases: β-expansion, univoque number, Thue-Morse sequence.

The research of the first two authors was partially supported by the Consiglio Nazionale delle Ricerche. The research of the third author was partially supported by Hungarian National Foundation for Scientific Research, Grant No. T29330 and 38225.

The purpose of this note is to investigate the following two questions:

• One may wonder whether q′ is an isolated univoque number or not. In the first case one could look for the second smallest univoque number, and so on.

• Allouche and Cosnard proved in [1] that q′ is transcendental. It is than natural to look for the smallest algebraic univoque number if it exists.

Both problems are solved by the following

Theorem 2. There exists a (decreasing) sequence of algebraic univoque numbers converging to q′. In particular, q′ is not an isolated point of U.

2. Proof of theorem 2

For the purpose of the present paper, it is advantageous to adopt the following definition of the Thue–Morse sequence (τ_{i}): if

i = ε_{k}2^{k} + ⋯ + ε_{0}

is the dyadic expansion of some nonnegative integer i, then we define

(4) τ_{i} := \begin{cases}1 & if ε_{k} + ⋯ + ε_{0} is odd, \\ 0 & if ε_{k} + ⋯ + ε_{0} is even. \end{cases}

In particular, τ_{0} = 0. See [9] for its equivalence with another usual definition.

Our main tool is the following strenghtening of a property of the Thue–Morse sequence τ_{1}, τ_{2}, …, established in [9].

Lemma 3. Let 1 ≤ i < 2^{N+1} for some nonnegative integer N.

(a) If τ_{i} = 0, then τ_{i+1} … τ_{i+2^{N}} < τ_{1} … τ_{2^{N}} in the lexicographic sense.

(b) If τ_{i} = 1, then \overline{τ_{i+1} … τ_{i+2^{N}}} < τ_{1} … τ_{2^{N}} in the lexicographic sense.

Remark. In fact, part (a) remains valid even if τ_{i} = 1, except the case where N = 0 and i = 1, while part (b) remains always valid even if τ_{i} = 0. An analogous property was established recently by Glendinning and Sidorov [7].

Proof. Consider first the case τ_{i} = 0. Then ε_{k} + ⋯ + ε_{0} is even and therefore ε_{k} + ⋯ + ε_{0} ≥ 2 because i ≥ 1 by assumption. Hence we may write i = 2^{n} + 2^{m} + j with 2^{n} > 2^{m} > j ≥ 0. We claim that

τ_{i+1} … τ_{i+2^{N}} < τ_{j+1} … τ_{j+2^{N}} . (5)

We distinguish two cases. If n ≥ m + 2, then using (4) we have

τ_{i+k} = τ_{j+k} for 1 ≤ k < 2^{m} − j

but

τ_{i+2^{m}−j} = τ_{2^{n}+2^{m+1}} = 0 < 1 = τ_{2^{m}} = τ_{j+2^{m}−j}.

Since

2^{m} − j ≤ 2^{m} ≤ 2^{N−1} < 2^{N},

this proves (5).

If n = m + 1, then using (4) we obtain by a similar reasoning that

τ_{i+k} = τ_{j+k} for 1 ≤ k < 2^{m+1} − j

but

τ_{i+2^{m+1}−j} = τ_{2^{m+2}+2^{m}} = 0 < 1 = τ_{2^{m+1}} = τ_{j+2^{m+1}−j}.

Since

2^{m+1} − j ≤ 2^{m+1} = 2^{n} ≤ 2^{N},

(5) follows again.

Since τ_{j} = τ_{i} = 0, we may iterate (5) until we obtain j = 0, thereby proving the desired inequality.

Now consider the case τ_{i} = 1 and write i = 2^{m} + j with 2^{m} > j ≥ 0. We claim that

\overline{τ_{i+1} … τ_{i+2^{N}}} < τ_{j+1} … τ_{j+2^{N}} . (6)

Indeed, using (4) we have

\overline{τ_{i+k}} = τ_{j+k} for 1 ≤ k < 2^{m} − j

but

\overline{τ_{i+2^{m}−j}} = \overline{τ_{2^{m+1}}} = 0 < 1 = τ_{2^{m}} = τ_{j+2^{m}−j}.

Since

2^{m} − j ≤ 2^{m} ≤ 2^{N},

this proves (6).

If j = 0, then we are done. If j > 0, then we complete the proof by combining (5) and (6).

Now fix a nonnegative integer N and introduce the following sequence:

c_{i} := \begin{cases}τ_{i} & if 1 ≤ i < 2^{N+1}, \\ c_{i−2^{N}} & if i ≥ 2^{N+1}. \end{cases} (7)

This sequence was used for different purposes in a recent work of Glendinning and Sidorov [7]. Observe that the sequence (c_{n}) is periodic with period 2^{N} beginning with c_{2^{N}}. Let us write down the first 16 elements of the Thue–Morse sequence and of the sequences (c_{n}) for N = 0, 1, 2:

(τ_{i}) :  1101 0011 0010 1101 …
N = 0 :  1111 1111 1111 1111 …
N = 1 :  1101 0101 0101 0101 …
N = 2 :  1101 0011 0011 0011 …

Let us note for further reference that

τ_{i} = τ_{i−2^{N}} for 2^{N+1} ≤ i < 2^{N+1} + 2^{N}. (8)

Indeed, this follows easily from (4).

It is clear that the equation

1 = \frac{c_{1}}{q} + \frac{c_{2}}{q^{2}} + \frac{c_{3}}{q^{3}} + … (9)

defines an algebraic number 1 < q_{N} ≤ 2 satisfying q_{N} → q′ as N → ∞.

Proof of Theorem 2. Thanks to Theorem 1, it suffices to verify that the sequence (c_{n}) is admissible in the following sense:

(10) c_{i+1} … c_{i+2^{N}} < c_{1} … c_{2^{N}} whenever c_{i} = 0

and

(11) \overline{c_{i+1} … c_{i+2^{N}}} < c_{1} … c_{2^{N}} whenever c_{i} = 1.

For 1 ≤ i < 2^{N+1} both relations follow from the similar properties of the Thue– Morse sequence established in the preceding lemma because the first 2^{N+1} + 2^{N} − 1 of the two sequences coincide by equation (8).

For i ≥ 2^{N+1} the relations (10) and (11) now follow by induction because the sequences c_{i+1} … c_{i+2^{N}} and c_{i+1−2^{N}} … c_{i} coincide, and also c_{i} = c_{i−2^{N}}, so that c_{i} = 0 implies c_{i−2^{N}} = 0 and c_{i} = 1 implies c_{i−2^{N}} = 1.

References

[1] J.-P. Allouche and M. Cosnard, The Komornik–Loreti constant is transcendental, Amer. Math. Monthly 107 (2000), 448-449.

[2] J.-P. Allouche and M. Cosnard, Non-integer bases, iteration of continuous real maps, and an arithmetic self-similar set, Acta Math. Hungar. 91 (2001), 325-332.

[3] Z. Daróczy and I. Kátai, Univoque sequences, Publ. Math. Debrecen 42 (1993), 3-4, 397-407.

[4] Z. Daróczy and I. Kátai, On the structure of univoque numbers, Publ. Math. Debrecen 46 (1995), 3-4, 385-408.

[5] P. Erdős, M. Horváth and I. Joó, On the uniqueness of the expansions 1 = ∑ q^{−n_{i}}, Acta Math. Hungar. 58 (1991), 333-342.

[6] P. Erdős, I. Joó and V. Komornik, Characterization of the unique expansions 1 = ∑ q^{−n_{i}} and related problems, Bull. Soc. Math. France 118 (1990), 377-390.

[7] P. Glendinning and N. Sidorov, Unique representations of real numbers in non-integer bases, Math. Res. Lett. 8 (2001), no. 4, 535–543.

[8] G. Kallós, The structure of the univoque set in the small case, Publ. Math. Debrecen 54 (1999), 1-2, 153-164.

[9] V. Komornik and P. Loreti, Unique developments in non-integer bases, Amer. Math. Monthly 105 (1998), 636-639.

[10] V. Komornik and P. Loreti, Subexpansions, superexpansions and uniqueness properties in non-integer bases, to appear in Periodica Math. Hungar. 44 (2002).

[11] M. Morse, Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc. 22 (1921), 84-100.

[12] W. Parry, On the β-expansions of real numbers, Acta Math. Acad. Sci. Hungar. 11 (1960), 401-416.

[13] A. Rényi, Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar. 8 (1957), 477-493.

[14] A. Thue, Über unendliche Zeichenreihen, Christiania Vidensk. Selsk. Skr. Mat. Nat. Kl. 7 (1906), 1-22. Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, 139-158.

[15] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Christiania Vidensk. Selsk. Skr. Mat. Nat. Kl. 1 (1912), 1-67. Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, 413-478.

Institut de Recherche Mathématique Avancée, Université Louis Pasteur et CNRS, 7, rue René Descartes, 67084 Strasbourg Cedex, France

E-mail address: komornik@math.u-strasbg.fr

Dipartimento di Metodi e Modelli, Matematici per le Scienze Applicate, Università di Roma “La Sapienza”, Via A. Scarpa, 16, 00161 Roma, Italy

E-mail address: loreti@dmmm.uniroma1.it

Department of Computer Science, University of Debrecen, H-4010 Debrecen, P.O. Box 12, Hungary

E-mail address: pethoe@neumann.math.klte.hu