Affinely Self-Generating Sets and Morphisms

David Garth and Adam Gouge Division of Mathematics and Computer Science Truman State University Kirksville, MO 63501 USA

                   dgarth@truman.edu
                   acg938@truman.edu

Abstract

Kimberling defined a self-generating set S of integers as follows. Assume 1 is a member of S, and if x is in S, then 2x and 4x − 1 are also in S. We study similar self-generating sets of integers whose generating functions come from a class of affine functions for which the coefficients of x are powers of a fixed base. We prove that for any positive integer m, the resulting sequence, reduced modulo m, is the image of an infinite word that is the fixed point of a morphism over a finite alphabet. We also prove that the resulting characteristic sequence of S is the image of the fixed point of a morphism of constant length, and is therefore automatic. We then give several examples of self-generating sets whose expansions in a certain base are characterized by sequences of integers with missing blocks of digits. This expands upon earlier work by Allouche, Shallit, and Skordev. Finally, we give another possible generalization of the original set of Kimberling.

1 Introduction

Kimberling [4] defined a self-generating set S as follows.

1. 1 belongs to S;

2. if x belongs to S, then 2x and 4x − 1 belong to S; and

3. nothing else belongs to S.

Writing the integers in S in increasing order gives the sequence

1, 2, 3, 4, 6, 7, 8, 11, 12, 14, 15, 16, 22, 23, 24, 27, 28, 30, 31, 32, …, which is Sloane’s A052499 [7]. Reducing the sequence modulo 2, we obtain

1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, …

Kimberling found that this last sequence, starting at the second term, is the well-known Fibonacci word. Recall that the Fibonacci word can be obtained as the fixed point of the morphism 0 → 01, 1 → 0. The paper by Kimberling also noted that the sequence R(n) of ranks past 1 of the even terms of S is

R(n) = 1, 3, 4, 6, 8, 9, 11, …,

which is sequence A000201 [7].

Allouche, Shallit, and Skordev [2] made some additional interesting observations about S. In particular, they showed that the set T := S −1, the set obtained from S by subtracting 1 from all the elements of S, is also self-generating as follows:

1. 0 belongs to T

2. If x belongs to T then 2x + 1 and 4x + 2 belong to T

3. Nothing else belongs to T.

In addition, they showed that T is the set of integers whose base 2 representation does not contain the block 00. These binary expansions correspond to the lazy Fibonacci expansions of the set of natural numbers.

Kimberling [5] generalized the notion of self-generating sets of integers in the following way. Let F be a countable set of affine functions with integer coefficients. Let S_{F} be the set of numbers satisfying the conditions that 1 ∈ S_{F}, and if x ∈ S_{F} and f ∈ F, then f(x) ∈ S_{F}.

Kimberling’s paper contained several examples. The paper by Allouche, Shallit, and Skordev [2] cited some of these examples in connection with sequences of integers with missing blocks. For most of these examples they showed that the characteristic sequence of S_{F} is 2-automatic. They then asked, “How far can the sequence proposed by Kimberling be generalized?” In particular they asked, “Under which conditions is the corresponding characteristic sequence automatic?” We address these questions for a general class of affine functions.

For the remainder of this paper, let F be the family of functions defined as follows. Let v and a be positive integers, let ℓ_{i} be integers satisfying

1 = ℓ_{0} ≤ ℓ_{1} ≤ ℓ_{2} ≤ ⋯ ≤ ℓ_{v}

and let b_{i} be integers satisfying

b_{0} = 0, and 0 ≤ b_{i} ≤ a^{ℓ_{i}} − 1 for 1 ≤ i ≤ v.

For 0 ≤ i ≤ v let f_{i}(x) = a^{ℓ_{i}}x − b_{i}, and define F = {f_{i} : 0 ≤ i ≤ v}. Let S denote the set S_{F} described earlier. We prove the following two results.

Theorem 1. Let m be a positive integer. Then the sequence S reduced modulo m is the image, under a coding, of an infinite word that is a fixed point of a morphism over a finite alphabet.

Theorem 2. The characteristic sequence of S is a-automatic.

The family F considered here is slightly more general than a similar family studied by Kimberling [5]. In particular, he added several restrictions to the functions in F that ensure that the sets f_{j}(S) are pairwise disjoint. In this case the numbers in S are matched in one-to-one correspondence with the words over the alphabet {0, …, v}. For such sets he also studied, for fixed j, the distribution of the numbers {f_{j}(x) : x ∈ S} in S. As a result of Theorem 1 these frequencies, when they exist, are coordinates of a normalized eigenvector of the incidence matrix of the morphism corresponding to its Perron-Frobenius eigenvalue ([1], Theorem 8.4.6).

We prove Theorems 1 and 2 in Sections 3 and 4, respectively. The proofs give rise to simple algorithms for constructing the morphisms. The algorithms also reveal that Theorems 1 and 2 hold when the functions in F are of the form f_{i}(x) = a^{ℓ_{i}}x + b_{i}. In Section 5 we mention some examples of self-generating sets that have further connections with sequences of integers with missing blocks. In Section 6 we suggest another possible generalization of the Kimberling set in which these results apply. We begin, however, by proving some necessary lemmas.

2 Preliminary Lemmas for Theorem 1

In this section we show how to put a tree structure on S that gives rise to the morphisms. Let L = max{ℓ_{0}, …, ℓ_{v}}, and let B = max{b_{0}, …, b_{v}}. Let S = {s_{n}}_{n=1}^{∞} = {s_{1} < s_{2} < s_{3} < …}, and define s_{0} = 0. For n ≥ 1, define the set

R_{n} = {x : as_{n−1} < x ≤ as_{n}}.

For h ≥ 0, define a rooted tree τ_{n,h} of height h with root s_{n} as follows. Let τ_{n,0} = s_{n}, and for τ_{n,1}, the children of s_{n} are the elements of R_{n} in increasing order. Thus, if R_{n} = {s_{i_{n}}, …, s_{i_{n}+p_{n}}}, then τ_{n,1} is as shown in Figure 1. (Notice that s_{i_{n}+p_{n}} = as_{n}).

\begin{matrix}s_{i_{n}} & … & s_{n} & s_{i_{n}+p_{n}} \\ Figure 1: τ_{n,1} \end{matrix}

For h > 1, we continue this process recursively on the children of s_{n} to obtain τ_{n,h}.

Example 1. If F = {2x, 8x − 3, 16x − 4}, then S = {1, 2, 4, 5, 8, 10, 12, 13, 16, …} and τ_{1,4} is as presented in Figure 2. Notice that τ_{1,3}, τ_{1,2}, τ_{1,1}, τ_{2,3}, τ_{2,2}, τ_{2,1}, τ_{3,2}, τ_{3,1}, τ_{4,1}, and τ_{5,1} are all contained in τ_{1,4}.

1 2 4 5 8 10 12 13 16 1 2 4 5 8 1 2 4 1 2 1

Figure 2: τ_{1,4} in Example 1

Notice that the vertices in level h of τ_{1,h}, in order, correspond to the first few elements of S. The following lemmas provide useful results about the structure of τ_{n,h}. The first two are clear from the definitions. Note that it follows from the definition of S and the fact that b_{0} = 0 and ℓ_{0} = 1 that if s ∈ S, then a^{h}s = f_{0}^{h}(s) ∈ S for all h ≥ 1.

Lemma 1. For h ≥ 1, the smallest element of S in level h of τ_{n,h} is the successor in S of a^{h}s_{n−1}, and the largest element in level h is a^{h}s_{n}.

Lemma 2. Let s ∈ S. Then a^{h}s_{n−1} < s ≤ a^{h}s_{n} if and only if s is a vertex in level h of τ_{n,h}.

Lemma 3. If s_{n} ∈ S and a^{ℓ}x − b = f(x) ∈ F, then a^{ℓ}s_{n} − b is a vertex in level ℓ of τ_{n,ℓ}.

Proof. Note that a^{ℓ}s_{n} − b ∈ S. By definition, 0 ≤ b < a^{ℓ}, so

a^{ℓ}s_{n−1} ≤ a^{ℓ}(s_{n} − 1) = a^{ℓ}s_{n} − a^{ℓ} < a^{ℓ}s_{n} − b ≤ a^{ℓ}s_{n}

It follows from Lemma 2 that a^{ℓ}s_{n} − b is a leaf in the tree τ_{n,ℓ}. □

As a result of Lemmas 1 and 2, we can write an arbitrary vertex s in level h of τ_{n,h} in the form a^{h}s_{n} − c for some constant c. The next Lemma establishes a bound for this constant.

Lemma 4. Let h ≥ 1, and let a^{h}s_{n} − c be a vertex at level h in the tree τ_{n,h}. Then

c ≤ (\frac{a^{h} − 1}{a − 1}) B.  (1)

Proof. We use induction on h. Suppose h = 1. There exists an s ∈ S and a function f(x) = a^{ℓ}x − b ∈ F, with 0 ≤ b < a^{ℓ}, such that a^{ℓ}s − b = f(s) = as_{n} − c. By definition of S, a^{ℓ−1}s ∈ S, and it follows that s_{n} ≤ a^{ℓ−1}s. To see why, suppose a^{ℓ−1}s < s_{n}. Then a^{ℓ−1}s ≤ s_{n−1}, and so a^{ℓ}s ≤ as_{n−1}. Since as_{n} − c is a vertex in τ_{n,1}, by Lemma 2 we have that as_{n} − c > as_{n−1} ≥ a^{ℓ}s ≥ a^{ℓ}s − b = as_{n} − c, a contradiction. Thus, as_{n} ≤ a^{ℓ}s, and since as_{n} − c = a^{ℓ}s − b, it follows that c ≤ b ≤ B.

Now suppose that (1) holds for some h ≥ 1. Let a^{h+1}s_{n} − c be a vertex in level h + 1 of τ_{n,h+1}. Then a^{h+1}s_{n} − c is a child of some vertex s_{j} in level h of τ_{n,h}. Write s_{j} in the form a^{h}s_{n} − c′ for some constant c′. By hypothesis c′ ≤ (\frac{a^{h}−1}{a−1}) B. Also, a^{h+1}s_{n} − c is a vertex in τ_{j,1}. We can then write a^{h+1}s_{n} − c = as_{j} − c′′ for some c′′. By the proof of the h = 1 case, we have that c′′ ≤ B. Also, since s_{j} = a^{h}s_{n} − c′, it follows that

a^{h+1}s_{n} − c = as_{j} − c′′ = a^{h+1}s_{n} − ac′ − c′′.

It follows then that c = ac′ + c′′ ≤ a (\frac{a^{h}−1}{a−1}) B + B = (\frac{a^{h+1}−1}{a−1}) B. □

The next Lemma shows that for h ≥ L − 1, the form of τ_{n,h} is completely determined by τ_{n,L−1}, and in particular by the differences between successive vertices in each level of the tree τ_{n,L−1}.

Lemma 5. Assume L ≥ 1, k ≠ 1, and n ≠ 1. Assume also that τ_{k,L−1} and τ_{n,L−1} have the property that a^{i}s_{k} − c is a vertex in τ_{k,L−1} if and only if a^{i}s_{n} − c is a vertex in τ_{n,L−1}. Then τ_{k,L} and τ_{n,L} also possess this property.

Proof. If L = 1 then for k ≠ 1 and n ≠ 1, R_{k} = {as_{k} − b_{i} : 0 ≤ i ≤ v} and R_{n} = {as_{n} − b_{i} : 0 ≤ i ≤ v}, and the result is trivial. Assume then that L > 1. Let s = a^{L}s_{k} − c be a vertex in level L of τ_{k,L}. We will show that a^{L}s_{n} − c is a vertex in level L of τ_{n,L}. Since s ∈ S, there is an s′ ∈ S and a function f(x) = a^{ℓ}x − b ∈ F such that f(s′) = s. By Lemma 3, s is a vertex in level ℓ of the tree with root s′. Since s is also in level L of τ_{k,L}, and since ℓ ≤ L, it follows that s′ is a leaf in the tree τ_{k,h}, where h := L − ℓ. Let c′ be such that s′ = a^{h}s_{k} − c′. Since f(s′) = s, we have that

a^{L}s_{k} − c = s = f(s′) = f(a^{h}s_{k} − c′) = a^{ℓ+h}s_{k} − a^{ℓ}c′ − b = a^{L}s_{k} − a^{ℓ}c′ − b,

and so c = a^{ℓ}c′ +b. On the other hand, since h ≤ L−1, by hypothesis we have that a^{h}s_{n} −c′ is a vertex in level h of τ_{n,L−1}. By Lemma 3 again, it follows that f(a^{h}s_{n} − c′) is a vertex in level ℓ of the tree with root a^{h}s_{n} − c′. Thus,

f(a^{h}s_{n} − c′) = a^{ℓ+h}s_{n} − a^{ℓ}c′ − b = a^{L}s_{n} − c

is a vertex in level L of τ_{n,L}. We have thus shown that if a^{L}s_{k} − c is a vertex in τ_{k,L}, then a^{L}s_{n} − c is a vertex in τ_{n,L}. Reversing the roles of k and n, we can show that that if a^{L}s_{n} − c is a vertex in τ_{n,L} then a^{L}s_{k} − c is a vertex in τ_{k,L}. This completes the proof. □

Note that it is a consequence of the definition of the trees that any two trees τ_{k,h} and τ_{n,h} satisfying the property of Lemma 5 have the same tree structure. Also notice that the requirement that k ≠ 1 and n ≠ 1 is only necessary when L = 1. This is because n = 1 is the only value of n for which s_{n} ∈ R_{n}.

3 Proof of Theorem 1

Define an equivalence relation ∼ on S as follows. Let τ_{n,L−1} mod m be the tree obtained from τ_{n,L−1} by reducing the vertices of τ_{n,L−1} modulo m. We begin by defining s_{1} ∼ s_{1}. For n ≠ 1 and k ≠ 1, we say s_{n} ∼ s_{k} if and only if τ_{n,L−1} and τ_{k,L−1} satisfy the property of Lemma 5 and τ_{n,L−1} mod m = τ_{k,L−1} mod m. We pause from the proof for a brief example.

Example 2. Let F = {2x, 4x − 1, 8x − 3}. Then 2 ∼ 4 when reducing modulo 2, as the following tree structures show.

5678101013 14 15 16 τ_{2,2} τ_{2,2} mod 2 = τ_{4,2} mod 2 τ_{4,2} 341078204

When reducing modulo 3, note that 2 ≁ 4, but 2 ∼ 8, as the following tree structures show.

5678201229 30 31 32 τ_{2,2} τ_{2,2} mod 3 = τ_{8,2} mod 3 τ_{8,2} 340115 16 228

Now, by Lemma 4 there are only finitely many equivalence classes for this relation. We now define the morphism. Suppose R_{n} = \{s_{i_{n}}, …, s_{i_{n}+p_{n}}\}. Let \overline{s_{n}} denote the equivalence class of s_{n}, and let A be a complete set of equivalence class representatives. Define σ : A → A^{∗}, where A^{∗} is the set of finite words over A, by

σ(\overline{s_{n}}) = \overline{s_{i_{n}}} \overline{s_{i_{n}+1}} ⋯ \overline{s_{i_{n}+p_{n}}}.

To see that σ is well-defined, suppose \overline{s_{n}} = \overline{s_{k}} and σ(\overline{s_{k}}) = \overline{s_{i_{k}}} ⋯ \overline{s_{i_{k}+p_{k}}}. If L > 1, then since \overline{s_{n}} = \overline{s_{k}}, it follows that τ_{n,L−1} and τ_{k,L−1} have the same tree structure, and therefore p_{n} = p_{k}. If L = 1, it was shown in the proof of Lemma 5 that p_{n} = p_{k}. In either case, it then follows from Lemma 5 that

\overline{s_{i_{n}}} = \overline{s_{i_{k}}}, \overline{s_{i_{n}+1}} = \overline{s_{i_{k}+1}}, …, \overline{s_{i_{n}+p_{n}}} = \overline{s_{i_{k}+p_{k}}}.

Thus, σ is well defined.

Extend σ by concatenation to get a morphism from A^{∗} → A^{∗}. It is clear that σ(\overline{s_{1}}) = \overline{s_{1}} ⋯ \overline{s_{a}}. Thus, the infinite word given by

lim_{i→∞} σ^{i}(\overline{s_{1}})  (2)

is a fixed point of σ. Now define a map ρ : A → {0, 1, …, m − 1} by

ρ(\overline{s_{n}}) = s_{n} mod m.

Clearly ρ is well defined. Extend ρ by concatenation to obtain a morphism from A^{∗} → {0, 1, …, m − 1}^{∗}. This morphism is then a coding [1]. It is clear that the sequence S reduced modulo m is the image, under ρ, of the fixed point (2). This completes the proof of Theorem 1.

Example 3. Let F = {3x, 3x−1}. For this F the resulting sequence S is A032924+1, where A032924 is the sequence of natural numbers whose ternary representation contains no 0. We will produce the morphism for S mod 3. We see that L = 1, so for n ≠ 1 and k ≠ 1, s_{n} ∼ s_{k} if and only if s_{n} mod 3 = s_{k} mod 3. The complete set of equivalence class representatives is then \{\overline{1}, \overline{2}, \overline{3}\}. The morphism is therefore

\overline{1} → \overline{1} \overline{2} \overline{3}
\overline{2} → \overline{5} \overline{6} = \overline{2} \overline{3}
\overline{3} → \overline{8} \overline{9} = \overline{2} \overline{3}

Letting a = \overline{1}, b = \overline{2}, and c = \overline{3}, we get the morphism a → abc, b → bc, c → bc. Iterating this morphism on a produces a fixed point. Now define the morphism ρ : {a, b, c}^{∗} → {0, 1, 2}^{∗} by ρ(a) = 1, ρ(b) = 2, and ρ(c) = 0. The proof of Theorem 1 shows that the sequence S mod 3 is the image of the fixed point of σ under this coding.

Example 4. Let F = {2x, 4x − 1, 8x − 3}. We will find the morphism for S mod 2. Using the method described above, we find

σ(\overline{1}) = \overline{1} \overline{2}
σ(\overline{2}) = \overline{3} \overline{4} = \overline{3} \overline{2}
σ(\overline{3}) = \overline{5} \overline{6} = \overline{5} \overline{2}
σ(\overline{5}) = \overline{10} = \overline{2}

Thus, the sequence S mod 2 is the image by the coding a → 1, b → 0, c → 1, d → 1, of the fixed point of the morphism a → ab, b → cb, c → db, d → b.

Example 5. We use the same procedure to get the morphism for S mod 3 when F = {2x, 4x − 1, 8x − 3}:

σ(\overline{1}) = \overline{1} \overline{2} σ(\overline{6}) = \overline{11} \overline{6}  a → ab f → hf
σ(\overline{2}) = \overline{3} \overline{4} σ(\overline{7}) = \overline{13} \overline{2}  b → cd g → ib
σ(\overline{3}) = \overline{5} \overline{6} σ(\overline{11}) = \overline{21} \overline{4} or c → ef h → jd
σ(\overline{4}) = \overline{7} \overline{2} σ(\overline{13}) = \overline{2}  d → gb i → b
σ(\overline{5}) = \overline{4} σ(\overline{21}) = \overline{6}  e → d j → f

with the coding b → 2, e → 2, h → 2, a → 1, d → 1, g → 1, i → 1, c → 0, f → 0, j → 0.

4 Proof of Theorem 2

Recall that L = max{ℓ_{0}, …, ℓ_{v}} and B = max{b_{0}, …, b_{v}}. Let {u_{n}}_{n=0}^{∞} be the characteristic sequence of S. We will show that {u_{n}} is the image, under a coding, of a fixed point of a morphism of constant length. Specifically, we will show how to construct a morphism of length a for which {u_{n}} is the image, under a coding, of one of its fixed points. It will follow that {u_{n}} is a-automatic ([1], Theorem 6.3.2).

Define an equivalence relation ∼ on {u_{n}} as follows. Associate with each u_{n} a rooted tree of height L − 1, with u_{n} as the root , in which each vertex u_{i} has children

u_{ai−(a−1)}, …, u_{ai−1}, u_{ai},

in order. It follows from this definition that the vertices of the tree of level h are the terms

u_{a^{h}n−(a^{h}−1)}, …, u_{a^{h}n−1}, u_{a^{h}n}.

Figure 3 shows a tree for u_{n} when L = 3 and a = 2.

u_{n}u_{2n−1} u_{2n} u_{4n−3} u_{4n−2} u_{4n−1} u_{4n}

Figure 3: Tree associated with u_{n} for L = 3 and a = 2

To define ∼, let u_{1} ∼ u_{1}. If n ≠ 1 and k ≠ 1, we say u_{n} ∼ u_{k} if and only if the corresponding vertices of the trees are equal. Clearly there are only finitely many equivalence classes for this relation. Let \overline{u_{n}} be the equivalence class of u_{n}, and let A be a complete set of equivalence class representatives. Define the mapping σ : A → A^{∗} by

σ(\overline{u_{n}}) = \overline{u_{an−(a−1)}} ⋯ \overline{u_{an−1}} \overline{u_{an}}.

To show that σ is well-defined, assume that \overline{u_{n}} = \overline{u_{k}}. We need to show that \overline{u_{an−i}} = \overline{u_{ak−i}} for 0 ≤ i ≤ a − 1. It suffices to consider the case that n ≠ 1 and k ≠ 1, since u_{1} is the only element in the equivalence class for u_{1}. Extend the trees associated with u_{n} and u_{k} by one level to obtain rooted trees of height L. Figure 4 shows an extended tree for L = 3 and a = 2.

u_{n}u_{2n−1} u_{2n} u_{4n−3} u_{4n−2} u_{4n−1} u_{4n} u_{8n−7} u_{8n−6} u_{8n−5} u_{8n−4} u_{8n−3} u_{8n−2} u_{8n−1} u_{8n}

Figure 4: The extended tree for u_{n} with L = 3 and a = 2.

Since \overline{u_{n}} = \overline{u_{k}}, the corresponding vertices in the extended trees associated with u_{n} and u_{k} are equal for levels 0 through L − 1. We will show that the corresponding vertices in level L of the extended trees are also equal.

Let u_{a^{L}n−j} be a vertex at level L of the extended tree for u_{n}, where 0 ≤ j ≤ a^{L} − 1. Assume also that u_{a^{L}n−j} = 1. We will show that u_{a^{L}k−j} = 1. Since u_{a^{L}n−j} = 1, then a^{L}n − j is an element of S. Since n ≠ 1, then a^{L}n − j ≠ 1, and so there is an s ∈ S and an f(x) = a^{ℓ}x − b ∈ F such that

a^{L}n − j = f(s) = a^{ℓ}s − b.  (3)

Recall that 0 ≤ b < a^{ℓ}, and ℓ ≤ L.

If ℓ = L, then a^{L}s − b = a^{L}n − j, and so a^{L}(s − n) = b − j. Since 0 ≤ b, j < a^{L}, this is only possible if b = j and s = n. In this case we have that n ∈ S. Since \overline{u_{n}} = \overline{u_{k}}, it must be the case that u_{k} = 1, and so k ∈ S. It follows that f(k) = a^{L}k − b = a^{L}k − j is also in S, and thus u_{a^{L}k−j} = 1.

Suppose then that ℓ < L. It must be the case that a^{L−ℓ}n − (a^{L−ℓ} − 1) ≤ s ≤ a^{L−ℓ}n. To see why, notice that if s < a^{L−ℓ}n − (a^{L−ℓ} − 1), then s ≤ a^{L−ℓ}n − (a^{L−ℓ} − 1) − 1 = a^{L−ℓ}(n − 1), and so by (3) we have

a^{L}n − j = a^{ℓ}s − b ≤ a^{ℓ}(a^{L−ℓ}(n − 1)) − b
= a^{L}(n − 1) − b
≤ a^{L}(n − 1)
< a^{L}(n − 1) + 1
= a^{L}n − (a^{L} − 1)
≤ a^{L}n − j.

This is a contradiction, and so a^{L−ℓ}n − (a^{L−ℓ} − 1) ≤ s. On the other hand, suppose that s > a^{L−ℓ}n. Then s ≥ a^{L−ℓ}n + 1, and since 0 ≤ b < a^{ℓ}, it follows from (3) again that

a^{L}n − j = a^{ℓ}s − b ≥ a^{ℓ}(a^{L−ℓ}n + 1) − b
= a^{L}n + a^{ℓ} − b
≥ a^{L}n + 1
> a^{L}n − j,

a contradiction, and so s ≤ a^{L−ℓ}n. We have shown then that if ℓ < L, then a^{L−ℓ}n − (a^{L−ℓ} − 1) ≤ s ≤ a^{L−ℓ}n. It follows then that u_{s} is a vertex in the tree of height L − 1 associated with u_{n}, and we can write

s = a^{L−ℓ}n − m,  (4)

where 0 ≤ m ≤ a^{L−ℓ} − 1. Notice that we also have that a^{L−ℓ}k − m is a vertex in the tree of height L−1 associated with u_{k}. By (3) and (4) we have that a^{L}n−j = f(s) = a^{L}n−a^{ℓ}m−b, and thus

j = a^{ℓ}m + b.  (5)

Now, since a^{L−ℓ}n − m = s ∈ S, u_{s} = 1, and since \overline{u_{n}} = \overline{u_{k}}, we have that a^{L−ℓ}k − m is in S. It also follows from (5) that a^{L}k − j = a^{L}k − a^{ℓ}m − b = f(a^{L−ℓ}k − m). Thus, a^{L}k − j is also in S, and therefore u_{a^{L}k−j} = 1.

We have shown that if u_{a^{L}n−j} = 1 then u_{a^{L}k−j} = 1. By reversing the roles of n and k, the same proof shows that if u_{a^{L}k−j} = 1 then u_{a^{L}n−j} = 1. Thus, for 0 ≤ j ≤ a^{L} − 1, u_{a^{L}n−j} = 1 if and only if u_{a^{L}k−j} = 1. This proves that u_{a^{L}n−j} = u_{a^{L}k−j} for 0 ≤ j ≤ a^{L} − 1. Thus, the extended trees for u_{n} and u_{k} are the same. Since, for 0 ≤ i ≤ a − 1, the trees associated with u_{an−i} and u_{ak−i} are subtrees of the extended trees for u_{n} and u_{k}, respectively, it follows that u_{an−i} = u_{ak−i} for 0 ≤ i ≤ a − 1. Thus, σ is well-defined.

Now extend σ to a mapping from A^{∗} → A^{∗} by concatenation. Since σ(\overline{u}_{1}) = \overline{u_{1}} ⋯ \overline{u_{an}}, repeated iteration of σ on \overline{u}_{1} generates a fixed point. As in the end of the proof of Theorem 1, we can define a coding which associates \overline{u_{n}} with u_{n}. The characteristic sequence \{u_{n}\} is then the image of this fixed point. Since the morphism σ is of length a, the characteristic sequence is a-automatic ([1], Theorem 6.3.2).

Example 6. We find the morphism generating the characteristic sequence of S when F = {2x, 4x − 1, 8x − 3}.

σ(\overline{u_{1}}) = \overline{u_{1}} \overline{u_{2}}
σ(\overline{u_{2}}) = \overline{u_{3}} \overline{u_{4}} = \overline{u_{3}} \overline{u_{2}}
σ(\overline{u_{3}}) = \overline{u_{5}} \overline{u_{6}} = \overline{u_{5}} \overline{u_{2}}
σ(\overline{u_{5}}) = \overline{u_{9}} \overline{u_{10}} = \overline{u_{9}} \overline{u_{2}}
σ(\overline{u_{9}}) = \overline{u_{17}} \overline{u_{18}} = \overline{u}_{9} \overline{u_{9}}

This corresponds to the morphism a → ab, b → cb, c → db, d → eb, and e → ee, whose fixed point produced by iteration on a yields the characteristic sequence of S via the coding a → 1, b → 1 c → 1, d → 1, e → 0.

Example 7. Let F = {3x, 9x − 1}. Then L = 2, and so each u_{n} in the characteristic sequence {u_{n}} of S is associated with the tree of height 1 having children u_{3n−2}, u_{3n−1}, and u_{3n}. The morphism generating the characteristic sequence maps \overline{u_{n}} → \overline{u_{3n−2}} \overline{u_{3n−1}} \overline{u_{3n}}. We find that

σ(\overline{u_{1}}) = \overline{u_{1}} \overline{u_{2}} \overline{u_{3}}
σ(\overline{u_{2}}) = \overline{u_{4}} \overline{u_{5}} \overline{u_{6}} = \overline{u_{2}} \overline{u_{2}} \overline{u_{2}}
σ(\overline{u_{3}}) = \overline{u_{7}} \overline{u_{8}} \overline{u_{9}} = \overline{u_{2}} \overline{u_{8}} \overline{u_{3}}
σ(\overline{u_{8}}) = \overline{u_{22}} \overline{u_{23}} \overline{u_{24}} = \overline{u_{2}} \overline{u_{2}} \overline{u_{3}}

This corresponds to the morphism a → abc, b → bbb, c → bdc, and d → bbc. The fixed point of this morphism produced by iteration on a gives the characteristic sequence via the coding a → 1, c → 1, d → 1, b → 0.

5 Examples

In this section we give some additional examples of self-generating sets which produce sequences of integers defined by missing blocks. It was mentioned already that the original sequence of Kimberling [4] is 1+A003754, where A003754 is the sequence of integers whose binary expansion does not contain the block 00. The binary expansions of the integers in this sequence also correspond to the lazy Fibonacci expansions of the natural numbers. The following examples expand this idea. (For more on lazy expansions, see [3] and [6]).

Example 8. Let S be the set generated by F = {2x, 4x − 1, 8x − 3}, starting with 1. By reasoning similar to that used for the original Kimberling sequence, S is 1+A003796, where A003796 is the sequence of integers whose binary expansion does not contain the block 000. The binary expansions of the integers in this sequence also correspond to the lazy expansions of the natural numbers with respect to the sequence of Tribonacci numbers, starting with t_{2} = 1, t_{3} = 2, t_{4} = 4, and t_{n} = t_{n−1} + t_{n−2} + t_{n−3} for n ≥ 5. The sequence S reduced modulo 2, starting with the second term, gives

0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, …,

which is the image of the fixed point of the tribonacci morphism a → ab, b → ac, c → a, under the coding a → 0 and b → 1, c → 1.

Example 9. In general, if F = {2^{k}x − (2^{k−1} − 1) : 1 ≤ k ≤ n}, then S − 1 is the sequence of integers whose binary expansion does not contain blocks of n zeros. These expansions correspond to the lazy expansions of the natural numbers with respect to the base given by the sequence of n-bonacci numbers. The sequence S reduced modulo 2, starting at the second term, is the image of the fixed point of the morphism a_{1} → a_{1}a_{2}, a_{2} → a_{1}a_{3}, …, a_{n−1} → a_{1}a_{n−1}, and a_{n} → a_{1}, under the coding a_{1} → 0 , a_{2} → 1, ⋯, a_{n} → 1.

Familiarity with the method of the proof Theorem 1 reveals that the Theorem is also valid when the functions in F are all of the form f_{i}(x) = a^{ℓ_{i}}x + b_{i}. Moreover, if the minimal requirement is that 0 ∈ S, then the requirement that b_{0} = 0 can be removed.

Example 10. Let F = {3x + 1, 3x + 2, 9x + 3, 9x + 6}. If the minimal requirement for S is that 0 ∈ S, then it is not hard to see that S is the sequence of integers whose ternary representation does not contain the block 00. These ternary representations correspond to the lazy representations of the natural numbers with respect to sequence A028859, which is given recursively by r_{1} = 1, r_{2} = 3, …, r_{n} = 2r_{n−1} + 2r_{n−2}. It is also interesting to note that if the sequence S + 1 is reduced modulo 3 and then reduced again modulo 2, then the resulting sequence, starting from the second character, is the fixed point of the morphism 0 → 001, 1 → 00.

It is worth mentioning that the preceding examples can be easily generalized to generate the sequences of integers with missing blocks of zeros of any length in any base.

6 Further Generalizations

In this section we explore another possible generalization of Kimberling’s set and its connections with morphisms and sequences of integers with missing blocks. Consider the following example.

1. Let 1, 2 belong to S.

2. If x belongs to S then 3x belongs to S.

3. If x belongs to S and either x = 3k or x = 3k − 1 for some k ∈ ℤ, then 3x − 1 and 3x − 2 belong to S.

4. Nothing else belongs to S.

We say that S is conditionally self-generating. Arranging the elements of S in increasing order gives the sequence

S = 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17, 18, 21, 22, 23, …

Letting T := S − 1, it is not hard to see that the integers in T are those whose ternary representation does not contain the blocks 00 or 01. Moreover, these representations are precisely the Lazy representations of the natural numbers with respect to sequence A001333,

1, 3, 7, 17, 41, 99, 239, …,

which is given by the recurrence a_{0} = 1, a_{1} = 3, a_{n} = 2a_{n−1} + a_{n−2}. Reducing S modulo 3 gives the sequence

1, 2, 0, 1, 2, 0, 1, 2, 0, 0, 1, 2, 0, 1, 2, 0, 0, 1, 2, 0, 1, 2, 0, …

It is not hard to see that the proof of Theorem 1 applies to this S. The method of Theorem 1 shows that the sequence S reduced modulo 3 is the image by the map a → 1, b → 2, c → 0, d → 1, e → 2 of the fixed point of the morphism a → abc, b → dec, c → dec, d → c, e → dbc. Reducing this last sequence modulo 2 gives

1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, …

Again, it is not hard to see that the proof of Theorem 1 also applies when reducing modulo 3 and then again modulo 2. This reduced sequence turns out to be the image of the fixed point of the morphism a → abb, b → cbb, and c → b, under the coding a → 1, b → 0, c → 1. It is interesting to note that omitting the first term, this sequence is actually the fixed point of the morphism:

0 → 001 and 1 → 0.

Finally, it is also not hard to see that the proof of Theorem 2 applies in this case, and the characteristic sequence of S is 3-automatic, being the image of the fixed point of the morphism a → abb, b → cbb, c → ddb, and d → ddd, under the coding a → 1, b → 1, c → 1, d → 0.

7 Open Questions

We close with some remaining questions.

• Do Theorems 1 and 2 hold when the generating functions are characterized by “mixed base” rules? For example, do they hold when F = {2x, 3x + 1}? Allouche, Shallit, and Skordev [2] commented that in this case the corresponding characteristic sequence for S is probably not k-automatic for any k. It seems likely that there is no analog of Lemmas 4 and 5 in the mixed base case.

• Do Theorems 1 and 2 hold for more general families of functions? The proofs of Theorems 1 and 2 rely heavily on the fact that if f(x) = a^{ℓ}x − b ∈ F, then 0 ≤ b < a^{ℓ}. What if functions were allowed for which b ≥ a^{ℓ}?

References

[1] Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, Cambridge, 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] P. Erdős, I. Joó, V. Komornik, Characterization of the unique expansions 1 = ∑_{i=1}^{∞} q^{−n_{i}} and related problems, Bull. Soc. Math. France 118 (1990), 377–390.

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

    00.2.8. http://www.cs.uwaterloo.ca/journals/JIS/VOL3/goldentext.html

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

[6] A. Petho and R.F. Tichy, On digit expansions with respect to linear recurrences, J. Number Theory, 33 (1989), 243-256.

[7] N.J.A. Sloane, On-line Encyclopedia of Integer Sequences, published electronically at

    http://www.research.att.com/∼njas/sequences/

2000 Mathematics Subject Classification: Primary 11B99; Secondary 11B85. Keywords: Kimberling sequence, self-generating set, morphism, characteristic sequence, automatic sequence, lazy expansion, integers with missing blocks

(Concerned with sequences \underline{A000201} \underline{A001333}, \underline{A003754}, \underline{A003796}, \underline{A028859}, \underline{A032924}, and \underline{A052499}.)

Received August 4 2006; revised versions received September 14 2006; October 19 2006. Published in Journal of Integer Sequences, December 30 2006.

Return to Journal of Integer Sequences home page.