On the Recognizability of Self-Generating Sets

Tomi Kärki^{1} University of Turku Department of Mathematics FI-20014 Turku Finland

                     topeka@utu.fi

Anne Lacroix and Michel Rigo University of Liège Department of Mathematics Grande Traverse 12 (B37) B-4000 Liège Belgium

                  A.Lacroix@ulg.ac.be
                   M.Rigo@ulg.ac.be

Abstract

Let I be a finite set of integers and F be a finite set of maps of the form n ↦ k_{i} n+ℓ_{i} with integer coefficients. For an integer base k ≥ 2, we study the k-recognizability of the minimal set X of integers containing I and satisfying φ(X) ⊆ X for all φ ∈ F. We answer an open problem of Garth and Gouge by showing that X is k-recognizable when the multiplicative constants k_{i} are all powers of k and additive constants ℓ_{i} are chosen freely. Moreover, solving a conjecture of Allouche, Shallit and Skordev, we prove under some technical conditions that if two of the constants k_{i} are multiplicatively independent, then X is not k-recognizable for any k ≥ 2.

1Part of this research was done when the author was working in the Department of Mathematics at the University of Liège. The financial support from the Osk. Huttunen Foundation is gratefully acknowledged.

1 Introduction

In the general framework of numeration systems, the so-called recognizable sets of integers have been extensively studied. Let k ≥ 2 be an integer. The function rep_{k}: ℕ → {0, …, k − 1}^{∗} maps a non-negative integer onto its k-ary representation (without leading zeros). A set X ⊆ ℕ is k-recognizable if the language rep_{k}(X) = {rep_{k}(n) | n ∈ X} is regular; see, for instance, [3]. A similar definition can be given for the k-recognizable subsets of ℤ using convenient conventions to represent negative numbers, like adding a symbol “−” to the alphabet or considering the positive and the negative elements separately. Since the seminal work of Cobham [5], it is well-known that the recognizability of a set depends on the choice of the base k — except for the ultimately periodic sets, i.e., the union of a finite set and a finite number of infinite arithmetic progressions, which are easily seen to be k-recognizable for all k ≥ 2. The celebrated theorem of Cobham can be stated as follows. Let k, ℓ ≥ 2 be two multiplicatively independent bases, i.e., log k/ log ℓ is irrational. If a set X ⊆ ℕ is both k-recognizable and ℓ-recognizable, then it is ultimately periodic.

Kimberling [13] introduced the so-called self-generating sets of integers. They can be defined as follows. Let r ≥ 1 and G = {φ_{1}, φ_{2}, …, φ_{r}} be a set of affine maps where φ_{i}: n ↦ k_{i} n + ℓ_{i} with k_{i}, ℓ_{i} ∈ ℤ and 2 ≤ k_{1} ≤ k_{2} ≤ ⋯ ≤ k_{r}. The set generated by G and a finite set of integers I is the minimal subset X of ℤ containing I and such that φ_{i}(X) ⊆ X for all i = 1, …, r. For any subset S ⊆ ℤ, we set G(S) := {φ(s) | s ∈ S, φ ∈ G}, G^{0}(S) := S and G^{m+1}(S) := G(G^{m}(S)) for all m ≥ 0. Otherwise stated, X = ⋃_{m≥0} G^{m}(I) is the set of all integers n such that there exist m ≥ 0, a ∈ I and a finite sequence (φ_{i_{1}}, φ_{i_{2}}, …, φ_{i_{m}}) of maps in G such that

n = φ_{i_{m}} ∘ φ_{i_{m−1}} ∘ ⋯ ∘ φ_{i_{1}}(a) = φ_{i_{m}}(φ_{i_{m−1}}(⋯ φ_{i_{1}}(a) ⋯)).  (1)

Example 1. Kimberling [13] showed for G = {n ↦ 2n, n ↦ 4n − 1} and I = {1} that the corresponding self-generating set

K_{1} = {1, 2, 3, 4, 6, 7, 8, 11, 12, 14, 15, 16, …}

is closely related to the Fibonacci word. This relationship will be developed in Section 4, where with our techniques we obtain again Kimberling’s original result. Notice that for I = {0}, we get a subset containing negative integers: K_{0} = {0, −1, −2, −4, −5, −8, −9, …}. In particular, for I = {0, 1}, the corresponding self-generating set is K_{0} ∪ K_{1}.

Self-generating sets are also called affinely recursive in [14] where the correspondence between words i_{1}i_{2} ⋯ i_{m} over the alphabet {1, 2, …, r} and integers φ_{i_{m}}(φ_{i_{m−1}}(⋯ φ_{i_{1}}(1) ⋯)) is studied. For example, conditions under which this correspondence is one-to-one are given, which in turn implies that the natural ordering of the integers induces an ordering on the set of non-empty words over {1, 2, …, r} providing a kind of abstract numeration system [15]. Note that in the definition of affinely recursive sets [14] the set of generating functions G can be an infinite set of maps of the form φ_{i}: n ↦ k_{i} n + ℓ_{i}, where k_{i}, ℓ_{i} ∈ ℕ.

Allouche, Shallit and Skordev [2] consider a general framework for self-generating sets. The k-ary representations of the elements of some self-generating sets are related to words over Σ_{k} = {0, 1, …, k−1} where some fixed block of digits is missing. As an illustration, one can notice that the set K_{1} − 1 = {0, 1, 2, 3, 5, 6, 7, 10, …} introduced in Example 1 consists of all integers whose binary expansion does not contain “00” as factor. Recall that the characteristic sequence (c_{X}(n))_{n≥0} of a set X ⊆ ℕ is defined by c_{X}(n) = 1, if n ∈ X and c_{X}(n) = 0, otherwise. In particular, X is k-recognizable (resp., ultimately periodic) if and only if (c_{X}(n))_{n≥0} is k-automatic (resp., an ultimately periodic infinite word). Self-generating sets are consequently studied from the point of view of automatic and morphic sequences as well as in relation to non-standard numeration systems; for the definitions and further information, see [1, 16]. Moreover, Allouche, Shallit and Skordev ask the following question: Under what conditions is the characteristic sequence of a self-generating set k-automatic? They also present the following conjecture. Conjecture 2. With “mixed base” rules, such as G = {n ↦ 2n + 1, n ↦ 3n}, the set generated from I = {1} is not k-recognizable for any integer base k ≥ 2.

Let us fix the notation once and for all. Definition 3. In this paper, instead of considering a set G of maps as described above, we will moreover consider the extended set of r + 1 ≥ 2 maps

F = G ∪ {φ_{0}} = {φ_{0}, φ_{1}, …, φ_{r}}

where φ_{0} : n ↦ n and φ_{i}: n ↦ k_{i} n + ℓ_{i} with k_{i}, ℓ_{i} ∈ ℤ and

2 ≤ k_{1} ≤ k_{2} ≤ ⋯ ≤ k_{r}.

Having the identity function φ_{0} at our disposal, for any set S ⊆ ℤ, we have F^{m}(S) ⊆ F^{m+1}(S). Therefore, for any finite set I of integers, the set

F^{ω}(I) := lim_{m→∞} F^{m}(I)

is exactly the self-generating set with respect to G and I.

This article is an extended version of our presentation given in the MFCS conference 2009 [12]. The content of the paper is the following. In Section 2 we give some simple observations on self-generating sets. For example, if we add to F an extra map ψ: n ↦ n + ℓ with ℓ ≠ 0, then the corresponding self-generating set F^{ω}(I) is ultimately periodic and therefore krecognizable for all k ≥ 2. We also show that we can restrict our considerations to subsets of ℕ and assume that all additive constants ℓ_{i} for the maps φ_{i} ∈ F are non-negative.

In sections 3 and 4 we consider the multiplicatively dependent case. The results are based on Frougny’s normalization transducer; see, e.g., Chapter 7 in [16]. If all multiplicative constants k_{i} are pairwise multiplicatively dependent, then we give a general method to build a finite automaton recognizing rep_{k}(F^{ω}(I)) for any k that is multiplicatively dependent on every k_{i}. This allows us to generalize a recognizability result of Garth and Gouge [9]. Moreover, a new proof of the relation between the Kimberling set K_{1} and the infinite Fibonacci word is given in Section 4; for other proofs, see [2, 13].

In the multiplicatively independent case of Section 5 we study differences and ratios of consecutive elements in the considered self-generating set. The results rely on a classical gap theorem; see Theorem 14. We prove that if there exist i, j such that k_{i} and k_{j} are multiplicatively independent and if ∑_{i=1}^{r} k_{i}^{−1} < 1, then F^{ω}(I) is not k-recognizable for any k ≥ 2. In particular, this condition always holds for sets F where r = 2 and k_{1} < k_{2} are multiplicatively independent, answering Conjecture 2 in the affirmative.

2 Some reductions

First we show that assuming k_{i} ≥ 2 for every i = 1, 2, …, r is not a real restriction from the point of view of recognizability.

Lemma 4. If we add to F in Definition 3 an extra map ψ: n ↦ n + ℓ with ℓ ≠ 0, then the corresponding self-generating set F^{ω}(I) is ultimately periodic of period ℓ.

Proof. Denote by F^{j}(I) mod ℓ the set {n mod ℓ | n ∈ F^{j}(I)}. Recall that the identity function φ_{0} belongs to F. Since there are finitely many congruence classes modulo ℓ and F^{j}(I) mod ℓ ⊆ F^{j+1}(I) mod ℓ, there must exist an integer J such that F^{J+1}(I) mod ℓ = F^{J}(I) mod ℓ. Moreover, this means that F^{j}(I) mod ℓ = F^{J}(I) mod ℓ for every j ≥ J, and, consequently,

F^{ω}(I) mod ℓ = F^{J}(I) mod ℓ.  (2)

On the other hand, if n ∈ F^{ω}(I), then ψ^{t}(n) = n + t ℓ ∈ F^{ω}(I). Since n + t ℓ ≡ n mod ℓ, we conclude by (2), for any n ≥ max F^{J}(I), that

c_{F^{ω}(I)}(n) = \{ \begin{matrix}1, & if n mod ℓ ∈ F^{J}(I) mod ℓ; \\ 0, & otherwise. \end{matrix}

Hence, the characteristic sequence of F^{ω}(I) is ultimately periodic with preperiod max F^{J}(I) and period ℓ.

Remark 5. In Definition 3 and in what follows, we always assume that all multiplicative constants k_{i} of the affine maps φ_{1}, …, φ_{r} in F are at least 2. This condition does not guarantee that the corresponding self-generating set is not ultimately periodic. For example, if φ_{i}(x) = r x + i for i = 1, …, r, then we easily see that F^{ω}({0}) = ℕ.

The next lemma justifies that we may restrict our consideration to non-negative integers.

Lemma 6. Let F^{ω}(I) be a self-generating set as given in Definition 3. One can effectively construct two finite sets of non-negative integers I^{+} and I^{−} such that

F^{ω}(I) ∩ ℕ = F^{ω}(I^{+}) ∩ ℕ and F^{ω}(I) ∩ −ℕ = −(\overline{F}^{ω}(I^{−}) ∩ ℕ),

where −ℕ is the set of all non-positive integers and \overline{F} = \{φ_{0}, \overline{φ}_{1}, \overline{φ}_{2}, …, \overline{φ}_{r}\} with \overline{φ}_{i}: n ↦ k_{i} n − ℓ_{i} for i = 1, 2, …, r.

Proof. Let m = max{|ℓ_{i}| | i = 1, 2, …, r} and denote by M the interval of integers [[−m, m]]. Define I_{j} := F^{j}(I) ∩ M for j ≥ 0. Since k_{i} ≥ 2 for all i ∈ {1, 2, …, r}, it follows that if n does not belong to M, then φ_{i}(n) ∉ M for all i ∈ {0, 1, …, r}. By this property and since F^{j}(I) ⊆ F^{j+1}(I), there must exist an integer J such that I_{j} = I_{J} for all j ≥ J. Hence, the integers of F^{ω}(I) falling into the interval M are exactly the ones in I_{J} and we can find the set I^{+} := ((F^{ω}(I) ∩ M) ∪ I) ∩ ℕ effectively.

Next we show that F^{ω}(I) ∩ ℕ = F^{ω}(I^{+}) ∩ ℕ. Since I^{+} ⊆ F^{ω}(I), it is clear by definition that F^{ω}(I^{+}) ∩ ℕ ⊆ F^{ω}(I) ∩ ℕ. Assume now that there exists an integer x belonging to (F^{ω}(I) ∩ ℕ) \ (F^{ω}(I^{+}) ∩ ℕ). Since I^{+} contains all non-negative elements of I, the element x must be generated from some negative element a ∈ I. In other words, there exists a finite sequence (φ_{i_{1}}, φ_{i_{2}}, …, φ_{i_{t}}) of maps in F such that x = φ_{i_{t}} ∘ φ_{i_{t−1}} ∘ ⋯ ∘ φ_{i_{1}}(a). Since a is negative and x is positive, there exists j such that φ_{i_{j−1}} ∘ φ_{i_{j−2}} ∘ ⋯ ∘ φ_{i_{1}}(a) = y < 0 and φ_{i_{j}}(y) = z ≥ 0. Hence, we have k_{i_{j}}y < 0 and z = k_{i_{j}}y + ℓ_{i_{j}} < m. This means that z ∈ (F^{ω}(I) ∩ M) ∩ ℕ and therefore x = φ_{i_{t}} ∘ φ_{i_{t−1}} ∘ ⋯ ∘ φ_{i_{j+1}}(z) ∈ F^{ω}(I^{+}) ∩ ℕ. This is a contradiction.

Similarly, by defining I^{−} := −(((F^{ω}(I) ∩ M) ∪ I) ∩ −ℕ), we obtain F^{ω}(I) ∩ −ℕ = F^{ω}(−I^{−}) ∩ −ℕ. If \overline{F} = \{φ_{0}, \overline{φ}_{1}, \overline{φ}_{2}, …, \overline{φ}_{r}\}, where \overline{φ}_{i}: n ↦ k_{i} n − ℓ_{i} for i = 1, 2, …, r, then we clearly have F^{ω}(I) ∩ −ℕ = −(\overline{F}^{ω}(I^{−}) ∩ ℕ), which concludes the proof.

Let y ≥ 0. Recall (for instance, see [3]) that a set Y ⊆ ℕ is k-recognizable if and only if Y + y is k-recognizable. As explained by the following lemma, from the point of view of recognizability of subsets of ℕ, one can also assume that all additive constants ℓ_{i} are non-negative.

Lemma 7. Let F^{ω}(I) be a self-generating set as given in Definition 3. There exist a nonnegative integer y and a self-generating set F̂^{ω}(I − y) such that F^{ω}(I) = F̂^{ω}(I − y) + y and F̂ = {φ_{0}, φ̂_{1}, …, φ̂_{r}}, where φ̂_{i}: n ↦ k_{i} n+ℓ̂_{i} for every i = 1, 2, …, r with some non-negative constants ℓ̂_{i} completely determined by F.

Proof. Assume that at least for some function φ_{i} ∈ F the constant ℓ_{i} is negative. Otherwise, the claim is trivial. Let y = max{|ℓ_{i}| | ℓ_{i} < 0} and set

ℓ̂_{i} := ℓ_{i} + (k_{i} − 1)y

for i = 1, 2, …, r. Since k_{i} ≥ 2, the constants ℓ̂_{i} are non-negative for every i. Let F̂ = {φ_{0}, φ̂_{1}, …, φ̂_{r}} where φ̂_{i}: n ↦ k_{i} n + ℓ̂_{i} for i = 1, …, r. We show by induction on the number of applied maps m that x belongs to F^{m}(I) if and only if x−y belongs to F̂^{m}(I −y).

First, for any x ∈ I, it is obvious that x − y belongs to I − y and vice versa. Assume now that x ∈ F^{m}(I) for some m ≥ 1. In other words, there exist z ∈ F^{m−1}(I) and i ∈ {0, …, r} such that x = φ_{i}(z). By induction hypothesis, z − y belongs to F̂^{m−1}(I − y). If φ_{i} = φ_{0}, then x = z and x − y ∈ F̂^{m−1}(I − y) ⊆ F̂^{m}(I − y). Hence, assume that φ_{i} ≠ φ_{0}. We have φ_{i}(z) = k_{i} z + ℓ_{i} and φ̂_{i}(z − y) = k_{i}(z − y) + ℓ_{i} + (k_{i} − 1)y = φ_{i}(z) − y. This proves that x − y belongs to F̂^{m}(I − y).

Next assume that x − y ∈ F̂^{m}(I − y) for some m ≥ 1, i.e., x − y = φ̂_{i}(z) for some z ∈ F̂^{m−1}(I − y) and i ∈ {0, …, r}. As above, we may assume that φ_{i} ≠ φ_{0}. Then we have x = φ̂_{i}(z) + y = k_{i}(z + y) + ℓ_{i} = φ_{i}(z + y), where z + y belongs to F^{m−1}(I) by induction hypothesis. Hence, x belongs to F^{m}(I).

Example 8. Consider the set K_{1} of Example 1 generated from {1} by the maps n ↦ 2n and n ↦ 4n − 1. Applying the construction given in the previous proof, set y = 1 and consider the maps 2n + 1 and 4n + 2. These two maps generate from {1} − 1 = {0}, the set {0, 1, 2, 3, 5, 6, 7, 10, …} which is equal to K_{1} − 1.

3 Multiplicatively Dependent Case

In this section we assume that the multiplicative coefficients k_{i} appearing in Definition 3 are all pairwise multiplicatively dependent, i.e., for every pair (i, j), there exist positive integers e_{i} and e_{j} such that k_{i}^{e_{i}} = k_{j}^{e_{j}}. Note that k_{i} and k_{j} are multiplicatively dependent if and only if there exist an integer n ≥ 2 and two integers d_{i}, d_{j} ≥ 1 such that k_{i} = n^{d_{i}} and k_{j} = n^{d_{j}}. By this characterization, it is easy to see that if the coefficients k_{i} are pairwise multiplicatively dependent, then there exists an integer k such that every k_{i} is a power of k. Our aim is to build a finite automaton showing that the set F^{ω}(I) is k-recognizable.

Recall that Σ_{k} = {0, 1, …, k − 1} and that rep_{k}: ℕ → Σ_{k}^{∗} maps an integer n to its k-ary representation without leading zeros. For any finite alphabet A ⊆ ℤ, the function val_{A,k}: A^{∗} → ℤ maps a word w = w_{n}w_{n−1} ⋯ w_{0} over A to the corresponding numerical value

val_{A,k}(w) = ∑_{i=0}^{n} w_{i} k^{i}.

The function defined over the set of words w ∈ A^{∗} such that val_{A,k}(w) ≥ 0 and which maps w to rep_{k}(val_{A,k}(w)) is called normalization over A. In the special case A = Σ_{k}, we simply write val_{k} instead of val_{Σ_{k},k}.

Theorem 9. Let F given in Definition 3 be such that the multiplicative coefficients k_{1}, …, k_{r} are all pairwise multiplicatively dependent. For any finite I ⊂ ℤ, the self-generating set F^{ω}(I) is k-recognizable if k_{i} is a power of k for every i = 1, 2, …, r.

We give a proof relying on Frougny’s normalization theorem. Another proof is given in [12].

Proof. Assume that the maps in F are of the kind φ_{i}: n ↦ k^{e_{i}} n + ℓ_{i} with e_{i} ≥ 1 for all i ∈ \{1, …, r\}. Since in the constructions of \overline{F} and F̂ of Lemma 6 and Lemma 7 the multiplicative constants k_{i} are not modified, it suffices to consider only non-negative elements of F^{ω}(I) and, moreover, we may assume that all initial values in I and all additive constants ℓ_{i} are non-negative. Thus, we assume F^{ω}(I) ⊆ ℕ and show that this self-generating set is k-recognizable.

Let n be an element of F^{ω}(I). In other words, there exists a finite sequence (φ_{i_{1}}, φ_{i_{2}}, …, φ_{i_{m}}) of maps in F such that n = φ_{i_{m}}(φ_{i_{m−1}}(⋯ φ_{i_{1}}(a) ⋯)) for some a ∈ I. With that integer, we associate the word

w = a 0^{e_{i_{1}}−1}ℓ_{i_{1}} ⋯ 0^{e_{im}−1}ℓ_{i_{m}}

over the finite alphabet A = I ∪ {0, ℓ_{1}, …, ℓ_{r}} ⊂ ℕ. One can notice that val_{A,k}(w) = n and val_{A,k}(I{0^{e_{1}−1}ℓ_{1}, …, 0^{e_{r}−1}ℓ_{r}}^{∗}) = F^{ω}(I). Frougny’s normalization theorem ([16, Proposition 7.1.4], see also [8]) says that normalization over A is computable by a finite transducer T. It is also well-known (see, e.g., [1, Theorem 4.3.6]) that if a regular language L is an input of a transducer then the output language is also regular. Hence, feeding the transducer T with the language I{0^{e_{1}−1}ℓ_{1}, …, 0^{e_{r}−1}ℓ_{r}}^{∗} gives us the regular language rep_{k}(F^{ω}(I)), which proves the claim.

Remark 10. The set F^{ω}(I) considered in the above theorem is k-recognizable and therefore k^{n}-recognizable for all n ≥ 1; again, see [3] for details. But usually this set is not ultimately periodic and therefore, by Cobham’s Theorem, not ℓ-recognizable for any ℓ ≥ 2 such that k and ℓ are multiplicatively independent. Indeed, if Theorem 15 described below can be applied, then F^{ω}(I) contains arbitrarily large gaps.

Remark 11. Garth and Gouge [9] consider the sequence S_{F} which is the increasing sequence of the elements in F^{ω}(I) in the case where I = {1}, k_{i} = k^{e_{i}}, 1 = e_{1} ≤ e_{2} ≤ ⋯ ≤ e_{r}, ℓ_{1} = 0 and −k^{e_{i}} < ℓ_{i} ≤ 0 for each i = 1, 2, …, r. They prove that this sequence reduced modulo positive integer m is morphic. In other words, there exists a morphism f satisfying f(a) = ax for some letter a and some word x ≠ ε such that S_{F} mod m is the image under a coding of the infinite word

f^{ω}(a) = lim_{n→∞} f^{n}(a) = axf(x)f^{2}(x) ⋯,

which is a fixed point of f. Moreover, they show that the characteristic sequence of F^{ω}(I) is k-automatic.

The authors of [9] ask whether their results hold for more general families of functions, for example, allowing ℓ_{i} ≤ −k^{e_{i}}. The answer for the case where the multiplicative constants k_{i} are powers of a fixed k but additive constants ℓ_{i} are chosen freely follows easily from Theorem 9. Namely, as was mentioned in the introduction, the set of non-negative integers F^{ω}(I) is k-recognizable if and only if its characteristic sequence (c_{F^{ω}(I)}(n))_{n≥0} is k-automatic. Note that in the general case F^{ω}(I) ⊆ ℤ we should consider two-sided k-automatic sequences and two-sided infinite fixed points (see Section 5.3 and Section 7.4 in [1] for more information) or consider non-negative and non-positive integers separately. In any case, by Lemma 6, the general case can be reduced to subsets of ℕ.

Hence, let us consider a self-generating set F^{ω}(I) ⊆ ℕ where the multiplicative constants k_{i} are powers of some k. By Theorem 9, the characteristic sequence (c_{F^{ω}(I)}(n))_{n≥0} is k-automatic. Since (n mod m)_{n≥0} is clearly k-automatic for any k ≥ 2, then also the sequence

u = ([c_{F^{ω}(I)}(n), n mod m])_{n≥0}

over the alphabet Σ_{2} ×Σ_{m} is k-automatic. Thus, by the result of Cobham [6], it is the image under a coding of a fixed point of a k-uniform morphism. Define a morphism f: (Σ_{2}×Σ_{m})^{∗} → Σ_{m}^{∗} by

f([a, b]) = \{ \begin{matrix}ε, & if a = 0; \\ b, & otherwise. \end{matrix}

Since the image of a morphic sequence by any morphism is either finite or morphic [4] (see also [1, Corollary 7.7.5]) and (c_{F^{ω}(I)}(n))_{n≥0} contains infinitely many ones, we conclude that f(u) is morphic. Since f(u) is clearly the sequence S_{F} reduced modulo m, we have answered the open question of Garth and Gouge [9] by generalizing their results for any additive constants ℓ_{i}.

Remark 12. Sequences with missing blocks are considered in [2, 9, 14]. For example, if φ_{1} : n ↦ 2n+1, φ_{2} : n ↦ 4n+2 and I = {0}, then the set F^{ω}(I) is the set of integers that do not contain the block “00” in their normalized binary expansion. Recall that this set is K_{1}−1; see Example 8. In [2] the authors ask whether or not the sequences with missing blocks are always particular cases of affinely recursive sets. We want to make a remark that, if F^{ω}(I) is a sequence with missing blocks, then all constants k_{i} must be multiplicatively dependent. Otherwise, assume that k_{1} and k_{2} are multiplicatively independent. Consider now the subset X_{i} ⊆ F^{ω}(I) generated from I by only applying the map φ_{i}. By Theorem 9, this subset is k_{i}- recognizable. Consider now the language 0^{∗}rep_{k}(X_{i}), where k is multiplicatively independent to k_{i}. It is known that this language is right dense meaning that every word over the alphabet Σ_{k} appears as a prefix of some word in 0^{∗}rep_{k}(X_{i}); for a proof, see [1, Lemma 11.1.1]. Hence, it follows that any block of digits over Σ_{k} is a factor of rep_{k}(n) for some integer n ∈ X_{i}. For any integer k ≥ 2, either k_{1} or k_{2} is multiplicatively independent with k, and therefore the set X_{1} or X_{2}, and consequently also F^{ω}(I), cannot be a set of integers that do not have some block of digits in their normalized base-k representation.

In order to obtain a self-contained proof for Theorem 9, we may tailor Frougny’s normalization transducer for the language 0^{∗}I{0^{e_{1}−1}ℓ_{1}, …, 0^{e_{r}−1}ℓ_{r}}^{∗} and directly conclude that the output language over Σ_{k} is regular. Next we describe this in more detail. The following construction is needed to prove the result relating K_{1} and the infinite Fibonacci word in the next section. By Lemma 6, it suffices to consider the set F^{ω}(I) ∩ ℕ.

Let C ⊂ ℤ be a finite input alphabet and let Σ_{k} be the output alphabet. Denote m = max{|c − a| | c ∈ C, a ∈ Σ_{k}} and let γ = m/(k − 1). Note that by the Euclidean division, for every s ∈ ℤ and c ∈ C, there exist a unique a ∈ Σ_{k} and s′ ∈ ℤ such that s + c = s′k + a. Moreover, if |s| < γ, then |s′| ≤ (|s| + |c − a|)/k < (γ + m)/k = γ. This justifies that we may define a finite right subsequential transducer, where the set of states Q = {s ∈ ℤ | |s| < γ} corresponds to possible carries, the initial state is 0 and the set of edges is

E = {s ⟶^{c/a} s′ | s + c = s′k + a}.  (3)

A right subsequential transducer is a transducer that reads the input from right to left and the underlying automaton where only inputs are considered is deterministic. Moreover, we have a partial terminal function ω: Q → Σ_{k}^{∗} mapping a state s ≥ 0 onto its normalized representation rep_{k}(s). Let w = c_{n}c_{n−1} ⋯ c_{0} ∈ C^{∗} \ 0C^{∗} be a representation of an integer N = val_{C,k}(w) ≥ 0. If we enter w into the transducer, there is a unique path

0 = s_{0} ⟶^{c_{0}/a_{0}} s_{1} ⟶^{c_{1}/a_{1}} s_{2} ⟶^{c_{2}/a_{2}} ⋯ ⟶^{c_{n}/a_{n}} s_{n+1}

such that N = ∑_{i=0}^{n} c_{i}k^{i} = ∑_{i=0}^{n} a_{i}k^{i} + s_{n+1}k^{n+1}. Hence, ω(s_{n+1})a_{n}a_{n_{1}} ⋯ a_{0} is the normalized representation in base k of the integer N. This transducer is Frougny’s normalization transducer for an input not containing leading zeros; see the proof of Lemma 7.1.1 in [16].

Next we adapt the above construction to our specific case of self-generating sets. Let the input alphabet be C = I ∪ {0, ℓ_{1}, …, ℓ_{r}}. We want to restrict the accepted input to the words w ∈ 0^{∗}I{0^{e_{1}−1}ℓ_{1}, …, 0^{e_{r}−1}ℓ_{r}}^{∗} such that val_{C,k}(w) ≥ 0. As was shown in the proof of Theorem 9, these words represent exactly the numbers in F^{ω}(I) ∩ ℕ. Hence, we build a transducer T such that from each carry state q ∈ Q = {s ∈ ℤ | |s| < γ} we may read only words of the form 0^{e_{i}−1}ℓ_{i} from right to left, output the corresponding output of Frougny’s transducer and end up in some carry state q′ ∈ Q. This can be achieved by introducing chains of intermediate states where each state has only one incoming and outgoing edge simulating the behavior of Frougny’s transducer. For example, assume that k = 2, q = 1 and we want to read 003 from right to left. This corresponds to the map φ: n ↦ 8n + 3. By the construction, in our modified transducer there is a path

1 ⟶^{3/0} ˆ2 ⟶^{0/0} ˆ1 ⟶^{0/1} 0,

where ˆ2 and ˆ1 are additional intermediate states and the starting state 1 and the ending state 0 belong to the original set Q. From each state q ∈ Q there are exactly r paths of this kind corresponding to the r maps φ_{i} ∈ F.

In addition, we need transitions corresponding to the initial values I. Let t ∉ Q be a unique final state. For each q ∈ Q and a ∈ I such that q + a ≥ 0, we add extra states and transitions which form a separate path from q to t such that it simulates Frougny’s transducer with input 0^{i}a, where i is the maximum integer satisfying k^{i} ≤ q + a. Padding with sufficiently many zeros insures that the carry is 0 after entering the final state t. Note that since we consider only non-negative elements of F^{ω}(I), we do not build a path from q to the final state t for an initial value a ∈ I such that q + a < 0. For example, in the case k = 2, q = 1 and a = 5 we have i = 2, since k^{2} < q + a = 6 < k^{3}, and the path from q to t is

1 ⟶^{5/0} ˆ3 ⟶^{0/1} ˆ1 ⟶^{0/1} t,

where ˆ3 and ˆ1 are new intermediate states. There is also a loop from the final state t onto itself with input 0 and output 0. This corresponds to allowing leading zeros after the most significant non-zero digit.

By our construction, each path from the initial state 0 to the final state t corresponds to reading some word of the language 0^{∗}I{0^{e_{1}−1}ℓ_{1}, …, 0^{e_{r}−1}ℓ_{r}}^{∗}. Therefore, the output of such an accepted path in our transducer T corresponds to some normalized representation (with possibly leading zeros) of a number in the self-generating set F^{ω}(I). Conversely, the normalized representation of a number in F^{ω}(I) padded with sufficiently many zeros corresponds to the input of some accepted path in our transducer T . Therefore, we may forget the input and consider a finite automaton A where the edges are labeled only with the output. Moreover, let us define that if in A there is a path from a state q to the state t with a label belonging to 0^{∗}, then the set q is an accepting state. This allows us to accept all normalized representations with an arbitrary number of leading zeros. We may also change the reading direction by turning the arrows and changing the roles of the initial and final states. Of course, the automaton obtained this way need not be complete and deterministic, but it can be made complete by adding missing edges which end up in a sink state and it can be made deterministic by the subset construction. Hence, we have constructed this way a deterministic finite automaton B which recognizes 0^{∗}rep_{k}(F^{ω}(I) ∩ ℕ) and, by Lemma 6, we conclude that F^{ω}(I) is k-recognizable.

4 Kimberling set and the Fibonacci word

In this section we show a result connecting the Kimberling set K_{1} considered in Example 1 and the infinite Fibonacci word defined as the fixed point φ^{ω}(0) = 01φ(1)φ^{2}(1) ⋯ = 01001010 ⋯ of the morphism φ: 0 ↦ 01, 1 ↦ 0. Recall that K_{1} = F^{ω}(I), where F = {φ_{0}, φ_{1}, φ_{2}}, φ_{1} : n ↦ 2n, φ_{2} : n ↦ 4n − 1 and I = {1}.

Theorem 13. Let S be the increasing sequence of elements of K_{1}. Omitting the first term, the sequence S reduced modulo 2, is the Fibonacci word φ^{ω}(0).

This was the main result in [13] and it was reproved in [2]. Here we give a third proof based on the transducer construction of the previous section and on some technical manipulation of morphisms.

Proof. Let us first build the transducer T for the set K_{1} = F^{ω}(I) as explained in the end of Section 3. This transducer and the corresponding reduced automaton A are illustrated in Figure 1. Using the same notation as above, we have k = 2, C = {1, 0, −1}, m = 2 and γ = 2. Since we never reach a carry state 1 from the initial state 0, our set Q = {−1, 0, 1} can be reduced to {−1, 0}. The input 0 corresponds to the map φ_{1} and the input 0(−1) corresponds to the map φ_{2}. When we read 0(−1) from right to left starting from either state 0 or −1, we introduce an intermediate state ˆ−1. Namely, for s = 0 and c = −1, we have s + c = (−1) · k + 1 and, for s = −1 and c = −1, we have s + c = (−1) · k + 0. Then from the state ˆ−1 we must read 0 and, since −1 + 0 = −1 · k + 1, we output 1 and end up in −1 ∈ Q. Moreover, we can read the initial value 1 ∈ I starting from any state in Q. For example, there is an edge with label 1/0 from −1 to F, since −1 + 1 = 0 · k + 0.

0  ˆ−1 F  −1 0/0 1/1 −1/1 0/1 0/0 0/1 −1/0 1/0  0  ˆ−1 F  −1 01110100

Figure 1: Transducer T and automaton A corresponding to the Kimberling set.

Using standard techniques we may easily build from A a deterministic automaton B accepting 0^{∗}rep_{2}(K_{1}) when reading digits from left to right. This automaton is described in Figure 2. A number in K_{1} such that its binary representation is accepted by b (the corresponding path ends in the final state b) must be odd, since all incoming edges of b are labeled by 1. Similarly, we conclude that a number having a binary representation accepted by c or d must be even. Hence, with an output function τ: A^{∗} ↦ Σ_{2}^{∗}, where A denotes the set of states of B and

τ(x) = \{ \begin{matrix}1, & if x = b; \\ 0, & if x = c or x = d; \\ ε, & otherwise, \end{matrix}

the automaton B_{τ} generates the sequence S mod 2, where S is the increasing sequence of elements of K_{1}.

The 2-uniform morphism corresponding to B is σ: A^{∗} → A^{∗} defined by

a ↦ ab, b ↦ cb, c ↦ de, d ↦ dg, e ↦ fb, f ↦ ge, g ↦ gg.

ab  c  d e  f  g 01100101 0, 11010

Figure 2: A finite deterministic automaton B accepting 0^{∗}rep_{2}(K_{1}).

By the above reasoning, it is clear that τ(σ^{ω}(a)) = S mod 2. Let us denote B = {a, b, c, d, e, f, g, h}. Using the techniques described in the proof of Theorem 7.6.1 and Theorem 7.7.4 in [1], we obtain a coding ν: B^{∗} → Σ_{2}^{∗} and a non-erasing morphism μ: B^{∗} → B^{∗} such that ν(μ^{ω}(a)) = S(τ(σ^{ω}(a))), where S is the shift function deleting the first element of the infinite word. The morphism μ is defined by

a ↦ abcdbeb, b ↦ cdb, c ↦ fgb, d ↦ eb, e ↦ fh,
f ↦ f, g ↦ gbeb, h ↦ hcdb

and

ν(x) = \{ \begin{matrix}1, & if x = b or x = h; \\ 0, & otherwise. \end{matrix}

Our goal is to show that ν(μ^{ω}(a)) is the infinite Fibonacci word. For this purpose, let us first simplify the morphism μ. Since μ(fgb) = fgbebcdb = μ(cdb), we conclude that ν(μ^{i}(fgb)) = ν(μ^{i}(cdb)) for every i ≥ 0 and, consequently, we may set μ(c) = cdb without changing ν(μ^{ω}(a)). Similarly, μ(fh) = fhcdb = μ(eb) and therefore ν(μ^{i}(e)) = ν(μ^{i}(d)) for i ≥ 0. Thus, we may set e = d and replace the morphism μ by a simpler morphism on a four-letter alphabet {a, b, c, d}:

a ↦ abcdbdb, b ↦ cdb, c ↦ cdb, d ↦ db.

Note that b and c have a different role with respect to the coding, i.e., ν(b) ≠ ν(c). Since b is always preceded by d except in the very beginning, we finally redefine the morphism μ: {a, b, c, d}^{∗} → {a, b, c, d}^{∗} by

a ↦ abcdbdbc, b ↦ db, c ↦ cdb, d ↦ dbc.

Hence, the sequence obtained by reducing S modulo 2 and omitting the first element can be obtained as the image of a coding ν of the fixed point μ^{ω}(a).

Let us next modify the morphism generating the Fibonacci word. First, note that we may replace φ by φ^{2}, since clearly lim_{n→∞} φ^{n}(0) = lim_{n→∞}(φ^{2})^{n}(0). Since φ^{2}(0) = 010 and φ^{2}(1) = 01, we notice that there are two types of zeros in the Fibonacci word: those followed by 0 will be denoted by c and those followed by 1 will be denoted by d. Let us also replace every 1 by b. Hence, we have φ^{ω}(0) = ν(ϕ^{ω}(d)), where ν is the coding defined above and ϕ: {b, c, d}^{∗} → {b, c, d}^{∗} is a morphism such that

b ↦ db, c ↦ dbc, d ↦ dbc.

We denote (f_{n})_{n≥0} = ϕ^{ω}(d) = dbcdb ⋯ and (s_{n})_{n≥0} = μ^{ω}(a) = abcdbdbcdb · · ·. In order to prove the result of Kimberling, we have to show that ν(ϕ^{ω}(d)) = ν(μ^{ω}(a)). Since ν(f_{0}) = ν(d) = 0 = ν(a) = ν(s_{0}), it suffices to show that f_{n} = s_{n} for all n ≥ 1. We do this by induction.

First observe that if s_{n} = f_{n} for all n = 1, 2, …, k, then

|μ(s_{0} ⋯ s_{k})| = |ϕ(f_{0} ⋯ f_{k})| + 5.  (4)

This holds because |μ(x)|_{y} = |ϕ(x)|_{y} for every x and y in {b, c, d} and |μ(s_{0})| = |μ(a)| = |ϕ(f_{0})| + 5. Here |w|_{y} denotes the number of letters y occurring in the word w.

Now assume that s_{n} = f_{n} for 1 ≤ n ≤ l and l is such that ϕ(f_{0} ⋯ f_{k}) = f_{0}f_{1} ⋯ f_{l} for some k > 1 satisfying f_{k} = b. This implies that ϕ(f_{0} ⋯ f_{k}) = uf_{l−1}f_{l} = udb and, by (4) and by the assumption, we have

μ(s_{0} ⋯ s_{k}) = udbs_{l+1}s_{l+2}s_{l+3}s_{l+4}s_{l+5} = udb.dbc.db,  (5)

where s_{l+4}s_{l+5} = μ(s_{k}) = μ(b) and s_{l+1}s_{l+2}s_{l+3} = μ(s_{k−1}) = μ(d), since s_{k} = b must be preceded by d if k > 1. We have two possibilities, either f_{k+1}f_{k+2} = db or f_{k+1}f_{k+2}f_{k+3} = cdb.

If f_{k+1}f_{k+2} = db, then ϕ(f_{0} ⋯ f_{k+2}) = udbϕ(f_{k+1})ϕ(f_{k+2}) = udb.dbc.db and, by comparing this to (5), we conclude that the claim s_{n} = f_{n} holds for 1 ≤ n ≤ l + 5.

Assume next that f_{k+1}f_{k+2}f_{k+3} = cdb. Now f_{1} ⋯ f_{k+3} = s_{1} ⋯ s_{k+3}, since we must have k + 3 ≤ l. Hence, we obtain

ϕ(f_{0} ⋯ f_{k+3}) = udb.dbc.dbc.db,
μ(s_{0} ⋯ s_{k+3}) = udb.dbc.db.cdb.dbc.db,

which implies that s_{n} = f_{n} for 1 ≤ n ≤ l + 8.

Since in the first case f_{k+2} = b and in the second case f_{k+3} = b, we may proceed by induction. This concludes the proof, since the claim clearly holds for small values of n ≥ 1.

5 Multiplicatively Independent Case

In this section our aim is to show that F^{ω}(I) ⊆ ℕ given in Definition 3 is not recognizable in any base k ≥ 2 provided that ∑_{i=1}^{r} k_{i}^{−1} < 1 and that there are at least two multiplicatively independent coefficients k_{i}. For the proof, we introduce the following notation. Let X = {x_{0} < x_{1} < x_{2} < ⋯ } be an infinite ordered subset of ℕ. Then we denote

R_{X} = lim sup_{i→∞} \frac{x_{i+1}}{x_{i}} and D_{X} = lim sup_{i→∞} (x_{i+1} − x_{i}).

In order to prove that a set is not k-recognizable for any base k ≥ 2, we use the following result from [6], see also Eilenberg’s book [7, Chapter V, Theorem 5.4].

Theorem 14 (Gap Theorem). Let k ≥ 2. If X is a k-recognizable infinite subset of ℕ, then either R_{X} > 1 or D_{X} < ∞.

Note that D_{X} < ∞ means that X is syndetic, i.e., there exists a constant C such that the gap x_{i+1} − x_{i} between any two consecutive elements x_{i}, x_{i+1} in X is bounded by C. Let us first show that if ∑_{i=1}^{r} k_{i}^{−1} < 1, then the set F^{ω}(I) given in Definition 3 contains arbitrarily large gaps.

Theorem 15. Let X = F^{ω}(I) be a self-generating subset of ℕ given in Definition 3. If ∑_{i=1}^{r} k_{i}^{−1} < 1, then X is not syndetic.

Proof. Let n ≥ 1 and K = k_{1}k_{2} ⋯ k_{r}. Let g = g_{1} ∘ g_{2} ∘ ⋯ ∘ g_{n} be a composite function, where g_{j} belongs to G = {φ_{1}, φ_{2}, …, φ_{r}} for every j = 1, 2, …, n and g_{j} = φ_{i} for exactly n_{i} integers j ∈ {1, …, n}. Note that n_{1} + n_{2} ⋯ + n_{r} = n. By definition, we have g(x) = k_{1}^{n_{1}}k_{2}^{n_{2}} ⋯ k_{r}^{n_{r}}x + c_{g}, where c_{g} is some constant depending on g. Since k_{1}^{n_{1}}k_{2}^{n_{2}} ⋯ k_{r}^{n_{r}} divides K^{n}, we get

#{g(x) mod K^{n} | x ∈ ℤ} = k_{1}^{n−n_{1}}k_{2}^{n−n_{2}} ⋯ k_{r}^{n−n_{r}}.

Recall that F = G∪{φ_{0}}, where φ_{0} denotes the identity function. The set F^{n}(I) contains exactly the integers obtained by at most n applications of maps in G. For any interval of integers [[N, N +K^{n} −1]] where N > max F^{n}(I), the elements of X belonging to this interval have been obtained by applying at least n + 1 maps. Hence, in the interval [[N, N + K^{n} − 1]] there can be at most k_{1}^{n−n_{1}}k_{2}^{n−n_{2}} ⋯ k_{r}^{n−n_{r}} integers x ∈ X such that the last n maps which produce x correspond to the composite function g, i.e., such that there exists y ∈ X satisfying g(y) = x. For fixed numbers n_{i}, i = 1, 2, …, r, there are n!/(n_{1}!n_{2}! ⋯ n_{r}!) functions g of the type described above. Thus, the number of integers in X ∩ [[N, N + K^{n} − 1]] for any large enough N is at most

∑_{n_{1},n_{2},...,n_{r}} (\frac{n!}{n_{1}!n_{2}! ⋯ n_{r}!}) k_{1}^{n−n_{1}}k_{2}^{n−n_{2}} ⋯ k_{r}^{n−n_{r}} = K^{n} (\frac{1}{k_{1}} + \frac{1}{k_{2}} + ⋯ + \frac{1}{k_{r}} )^{n}

where the sum is over n_{1}, n_{2}, …, n_{r} ≥ 0 satisfying n_{1} + n_{2} + ⋯ + n_{r} = n.

Hence, the biggest gap x_{i+1} − x_{i} between two consecutive elements x_{i}, x_{i+1} ∈ X in the interval [[N, N + K^{n} − 1]] is at least

d(n) = \frac{K^{n}}{K^{n} (\frac{1}{k_{1}} + \frac{1}{k_{2}} + ⋯ + \frac{1}{k_{r}} )^{n}} = (\frac{1}{k_{1}} + \frac{1}{k_{2}} + ⋯ + \frac{1}{k_{r}} )^{−n} .

Since ∑_{i=1}^{r} k_{i}^{−1} < 1, the function d(n) tends to infinity as n tends to infinity. This means that there are arbitrarily large gaps in X. In other words, the self-generating set X is not syndetic.

Before showing that R_{X} = 1 let us first recall the density property of multiplicatively independent integers. A set S is dense in an interval I ⊆ ℝ if every subinterval of I contains an element of S.

Theorem 16. If k, ℓ ≥ 2 are multiplicatively independent, {k^{p}/ℓ^{q} | p, q ≥ 0} is dense in [0, ∞).

This is a consequence of Kronecker’s theorem, which states that for any irrational number θ the sequence ({nθ})_{n≥0} is dense in the interval [0, 1). Here {x} denotes the fractional part of the real number x. The proof of Kronecker’s theorem as well as the proof of Theorem 16 can be found in [1, Section 2.5] or [11]. As an easy consequence of the previous theorem, we obtain the following result.

Corollary 17. Let α > 0 and β be two real numbers. If k and ℓ are multiplicatively independent, then the set {(αk^{p} + β)/ℓ^{q} | p, q ≥ 0} is dense in [0, ∞).

Proof. We show how to get arbitrarily close to any positive real number x. Let ϵ > 0. By Theorem 16, there exist integers p and q such that

|\frac{x}{α} − \frac{k^{p}}{ℓ^{q}} | < \frac{ϵ}{2α} and |\frac{β}{ℓ^{q}} | < \frac{ϵ}{2}.

Hence, it follows that

|x − \frac{αk^{p} + β}{ℓ^{q}} | ≤ |x − \frac{αk^{p}}{ℓ^{q}} | + |\frac{β}{ℓ^{q}} | < \frac{ϵ}{2α}α + \frac{ϵ}{2} = ϵ.

Let us next consider the ratio R_{X} of a self-generating set X.

Theorem 18. For any self-generating set X = F^{ω}(I) ⊆ ℕ given in Definition 3 where k_{i} and k_{j} are multiplicatively independent for some i and j, we have R_{X} = 1.

Proof. Without loss of generality, we may assume that F = {φ_{0}, φ_{1}, φ_{2}}, where φ_{1} : n ↦ k_{1} n + ℓ_{1}, φ_{2} : n ↦ k_{2} n + ℓ_{2}, and k_{1} and k_{2} are multiplicatively independent. Namely, for F ⊆ F′, it is obvious that F^{ω}(I) ⊆ F^{′ω}(I) and consequently, R_{F^{ω}(I)} = 1 implies R_{F^{′ω}(I)} = 1. By Lemma 7, we may also assume that ℓ_{1} and ℓ_{2} are non-negative.

Let a ∈ X be a positive integer and set X_{n} := X ∩ [φ_{1}^{n−1}(a), φ_{1}^{n}(a)] for all n > 0. Note that ∪_{n∈ℕ}X_{n} = X ∩ [a, ∞). Recall that X = {x_{0} < x_{1} < x_{2} < ⋯ } and define

r_{n} := max \{ \frac{x_{i+1} − x_{i}}{x_{i}} | x_{i+1}, x_{i} ∈ X_{n}\} .

Note that, for all x and for j = 1, 2, if we set b_{j} := ℓ_{j}/(k_{j} − 1), then we have

φ_{j}^{n}(x) = k_{j}^{n}x + ℓ_{j} ∑_{i=0}^{n−1} k_{j}^{i} = (x + b_{j}) k_{j}^{n} − b_{j}.  (6)

Let m ≥ 0 and x_{i}, x_{i+1} be two consecutive elements belonging to the set X_{m}. By Corollary 17, there exist infinitely many positive integers p and q such that \frac{φ_{2}^{p}(a)}{k_{1}^{q}} is equal to

\frac{(a + b_{2})k_{2}^{p} − b_{2}}{k_{1}^{q}} ∈ [x_{i+1} + b_{1} − \frac{3}{4}(x_{i+1} − x_{i}), x_{i} + b_{1} + \frac{3}{4}(x_{i+1} − x_{i})] .

Therefore φ_{2}^{p}(a) is an element of X belonging to the interval

[c, d] := [k_{1}^{q}(x_{i+1} + b_{1}) − \frac{3}{4}k_{1}^{q}(x_{i+1} − x_{i}), k_{1}^{q}(x_{i} + b_{1}) + \frac{3}{4}k_{1}^{q}(x_{i+1} − x_{i})] ,

which is a sub-interval^{2} of the interval [φ_{1}^{q}(x_{i}), φ_{1}^{q}(x_{i+1})]. In other words, we have

φ_{1}^{q}(x_{i}) < c < φ_{2}^{p}(a) < d < φ_{1}^{q}(x_{i+1}).

Hence, for all t > q, the difference x_{j+1} − x_{j} of any two consecutive elements x_{j}, x_{j+1} of X in the interval [φ_{1}^{t}(x_{i}), φ_{1}^{t}(x_{i+1})] is at most

max{φ_{1}^{t−q}(φ_{1}^{q}(x_{i+1})) − φ_{1}^{t−q}(φ_{2}^{p}(a)), φ_{1}^{t−q}(φ_{2}^{p}(a)) − φ_{1}^{t−q}(φ_{1}^{q}(x_{i}))}

≤ max\{φ_{1}^{t}(x_{i+1}) − φ_{1}^{t−q}(c), φ_{1}^{t−q}(d) − φ_{1}^{t}(x_{i})\} = \frac{3}{4}k_{1}^{t}(x_{i+1} − x_{i}) + b_{1}k_{1}^{t−q}.

Thus, the ratio (x_{j+1} − x_{j})/x_{j} is at most

\frac{3 k_{1}^{t}(x_{i+1} − x_{i})}{4 φ_{1}^{t}(x_{i})} + \frac{b_{1}k_{1}^{t−q}}{φ_{1}^{t}(x_{i})} = \frac{3 k_{1}^{t}(x_{i+1} − x_{i})}{4 φ_{1}^{t}(x_{i})} + \frac{1}{k_{1}^{q}} \frac{b_{1}k_{1}^{t}}{(x_{i} + b_{1})k_{1}^{t} − b_{1}} .  (7)

The latter term in this sum can be taken as small as possible for q and t large enough (1/k_{1}^{q} tends to 0 and the other factor tends to the constant b_{1}/(x_{i} + b_{1})). In particular, for q and t large enough, we have

\frac{b_{1}k_{1}^{t−q}}{φ_{1}^{t}(x_{i})} < \frac{x_{i+1} − x_{i}}{12x_{i}} .

Moreover, we have

\frac{3 k_{1}^{t}(x_{i+1} − x_{i})}{4 φ_{1}^{t}(x_{i})} = \frac{3 (x_{i+1} − x_{i})}{4 (x_{i} + b_{1} − b_{1}/k_{1}^{t})} < \frac{3 (x_{i+1} − x_{i})}{4 x_{i}} < \frac{10 (x_{i+1} − x_{i})}{12 x_{i}}.

Thus, by (7), we obtain

\frac{x_{j+1} − x_{j}}{x_{j}} < \frac{11 (x_{i+1} − x_{i})}{12 x_{i}}.  (8)

Since the above holds for any consecutive elements x_{i} and x_{i+1} in X_{m} and there are only finitely many such pairs, we conclude that there exists an integer N_{1} such that (8) holds for any consecutive elements x_{j}, x_{j+1} ∈ X_{n} where n ≥ N_{1}. Hence, we obtain r_{n} < \frac{11}{12} r_{m} for every n ≥ N_{1}. Moreover, by repeating this procedure, we conclude that there exists an integer N_{k} such that

r_{n} < (\frac{11}{12})^{k} r_{m}

for every n ≥ N_{k}. This implies that lim sup_{n→∞} r_{n} = 0 and, consequently,

R_{X} = 1 + lim sup_{n→∞} r_{n} = 1.

2c − φ_{1}^{q}(x_{i}) = \frac{1}{4}k_{1}^{q}(x_{i+1} − x_{i}) + b_{1} and φ_{1}^{q}(x_{i+1}) − d = \frac{1}{4}k_{1}^{q}(x_{i+1} − x_{i}) − b_{1} which is positive for large enough q.

Our main result is a straightforward consequence of the previous theorems.

Theorem 19. Let X = F^{ω}(I) ⊆ ℕ be given in Definition 3. If ∑_{t=1}^{r} k_{t}^{−1} < 1 and there exist i, j such that k_{i} and k_{j} are multiplicatively independent, then F^{ω}(I) is not k-recognizable for any integer base k ≥ 2.

Proof. Let X = F^{ω}(I) satisfy the assumptions of the theorem. By Theorem 15, we have D_{X} = ∞ and, by Theorem 18, we have R_{X} = 1. Thus, Theorem 14 implies that X is not k-recognizable for any k ≥ 2.

As a corollary, we have solved the conjecture of Allouche, Shallit and Skordev [2].

Corollary 20. Let F = {φ_{0}, n ↦ k_{1} n + ℓ_{1}, n ↦ k_{2} n + ℓ_{2}}, where k_{1} and k_{2} are multiplicatively independent. Then any infinite self-generating set F^{ω}(I) given in Definition 3 is not k-recognizable for any k ≥ 2.

Proof. This follows directly from Theorem 19. Namely, if k_{1} and k_{2} are multiplicatively independent, then k_{1} ≥ 2 and k_{2} ≥ 3 and k_{1}^{−1} + k_{2}^{−1} ≤ 1/2 + 1/3 = 5/6 < 1.

The condition ∑_{t=1}^{r} k_{t}^{−1} < 1 is not needed in a very special case of self-generating sets where ℓ_{i} = 0 for every i = 1, 2, …, r. This situation is related to so-called y-smooth numbers. An integer is y-smooth if it has no prime factors greater than y. For more on smooth numbers, see, e.g., [10].

Theorem 21. Let X = F^{ω}(I) be given in Definition 3. If ℓ_{i} = 0 for every i = 1, 2, …, r and there exist i, j such that k_{i} and k_{j} are multiplicatively independent, then F^{ω}(I) is not k-recognizable for any integer base k ≥ 2. In particular, for y ≥ 3, the set of y-smooth numbers is not k-recognizable for any k ≥ 2.

Proof. Assume that φ_{i}: n ↦ k_{i}n for i = 1, 2, …, r and denote X = F^{ω}(I). Let x ≥ 2 be an integer and consider n ∈ X ∩[0, x]. By the definition of X, the integer n must be of the form k_{1}^{e_{1}} ⋯ k_{r}^{e_{r}}a, where a ∈ I. Since the exponent e_{i} is at most log_{2}(x) for every i = 1, 2, …, r, the number of integers in X ∩ [0, x] is at most (1 + log_{2}(x))^{r}|I| = O(log^{r}(x)). It follows that x/|X ∩ [0, x]| tends to infinity when x tends to infinity. This implies that F^{ω}(I) cannot be syndetic, i.e., D_{X} = ∞. If there are two multiplicatively independent constants k_{1} and k_{2}, then R_{X} = 1 by Theorem 18. Hence, by Theorem 14, the self-generating set X is not k-recognizable for any k ≥ 2. The second claim follows, since the set of y-smooth numbers can be represented as a self-generating set F^{ω}(I), where I = {1} and φ_{i}: n ↦ p_{i}n for i = 1, 2, …, r. Here p_{i} is the ith smallest prime and p_{r} is the largest prime less than or equal to y.

6 Acknowledgments

We thank the anonymous referees of the MFCS version of this paper for suggesting improvements in the presentation of this paper. In particular, it is one of the referees who pointed out a possible connection with smooth numbers.

References

[1] J.-P. Allouche, J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.

[2] J.-P. Allouche, J. Shallit, G. Skordev, Self-generating sets, integers with missing blocks, and substitutions, Discrete Math. 292 (2005), 1–15.

[3] V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. 1 (1994), 191–238.

[4] A. Cobham, On the Hartmanis-Stearns problem for a class of tag machines, in IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, 1968, pp. 51–60. Also appeared as IBM Research Technical Report RC-2178, August 23, 1968.

[5] A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 (1969), 186–192.

[6] A. Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164–192.

[7] S. Eilenberg, Automata, Languages, and Machines, Vol. A., Pure and Applied Mathematics, Vol. 58, Academic Press, 1974.

[8] C. Frougny, Representations of numbers and finite automata, Math. Systems Theory 25 (1992), 37–60.

[9] D. Garth, A. Gouge, Affinely self-generating sets and morphisms, J. Integer Seq. 10 (2007), Article 07.1.5.

[10] A. Granville, Smooth numbers: computational number theory and beyond, in J. P. Buhler, P. Stevenhagen, eds., Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ. 44, Cambridge University Press, 2008, pp. 267–323.

[11] G. H. Hardy, E. M. Wright, Introduction to the Theory of Numbers, Oxford University Press, 1985.

[12] T. Kärki, A. Lacroix, M. Rigo, On the recognizability of self-generating sets, in R. Královič, D. Niwiński, eds., Proceedings of the 34st International Symposium on Mathematical Foundations of Computer Science, Bratislava, August 24 - 28, 2009, Lecture Notes in Comput. Sci. 5734 (2009), 525–536.

[13] C. Kimberling, A self-generating set and the golden mean, J. Integer Seq. 3 (2000), Article 00.2.8.

[14] C. Kimberling, Affinely recursive sets and orderings of languages, Discrete Math. 274 (2004), 147–159.

[15] P. B. A. Lecomte, M. Rigo, Numeration systems on a regular language, Theory Comput. Syst. 34 (2001), 27–44.

[16] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, 90, Cambridge University Press, 2002.

2000 Mathematics Subject Classification: Primary 68Q45; Secondary 68R15, 11B85. Keywords: self-generating set, recognizability, numeration systems, multiplicatively independent integers, Fibonacci word.

(Concerned with sequences \underline{A000045}, \underline{A000201}, \underline{A001950}, \underline{A003754}, \underline{A003849}, \underline{A052499}.)

Received November 16 2009; revised version received January 21 2010. Published in Journal of Integer Sequences, January 27 2010.

Return to Journal of Integer Sequences home page.