Numeration Systems, Linear Recurrences, and Regular Sets

Jeffrey Shallit^{∗} Department of Computer Science University of Waterloo Waterloo, Ontario, Canada N2L 3G1

            shallit@graceland.waterloo.edu

December 10, 1991

Abstract

A numeration system based on a strictly increasing sequence of positive integers u_{0} = 1, u_{1}, u_{2}, … expresses a non-negative integer n as a sum n = ∑_{j=0}^{i} a_{j}u_{j}. In this case we say the string a_{i}a_{i−1} ⋯ a_{1}a_{0} is a representation for n. If gcd(u_{0}, u_{1}, …) = g, then every sufficiently large multiple of g has some representation.

If the lexicographic ordering on the representations is the same as the usual ordering of the integers, we say the numeration system is order-preserving. In particular, if u_{0} = 1, then the greedy representation, obtained via the greedy algorithm, is orderpreserving. We prove that, subject to some technical assumptions, if the set of all representations in an order-preserving numeration system is regular, then the sequence u = (u_{j})_{j≥0} satisfies a linear recurrence. The converse, however, is not true.

The proof uses two lemmas about regular sets that may be of independent interest. The first shows that if L is regular, then the set of lexicographically greatest strings of every length in L is also regular. The second shows that the number of strings of length n in a regular language L is bounded by a constant (independent of n) iff L is the finite union of sets of the form xy^{∗}z.

1 Introduction

Let Σ be a finite or infinite alphabet. A numeration system is a map r : IN → Σ^{∗} that assigns a string r(n), called the representation of n, to a nonnegative integer n. Sometimes not every integer have a representation, in which case r is a partial function, rather than a function.

∗Supported in part by a grant from NSERC .

Common examples of numeration systems include radix-k representation (for k an integer ≥ 2), Fibonacci representation, factorial representation, etc. See [11, 12] for surveys on numeration systems.

In this paper we consider only linear numeration systems constructed as follows: given a strictly increasing sequence of positive integers u_{0}, u_{1}, u_{2}, …, we try to express n as a non-negative integer linear combination of the u_{j}, say n = ∑_{0≤j≤i} a_{j}u_{j}. If we can write n in this manner, we say n is u–representable (or representable if the sequence u is clear from the context), and one representation of n is the string a_{i}a_{i−1} ⋯ a_{1}a_{0}. We define the mapping val from strings back to integers as follows:

val(a_{i}a_{i−1} ⋯ a_{1}a_{0}) = ∑_{0≤j≤i} a_{j}u_{j}.  (1)

We say such a representation is normal if a_{i} ≠ 0. In this paper, we consider only normal representations.

Note that if

gcd(u_{0}, u_{1}, …) = g,

then every sufficiently large multiple of g is representable.

For some choices of the sequence u = (u_{j})_{j≥0}, the “digits” a_{j} may be required to be arbitrarily large. An example of this is the so-called factorial representation, where u_{j} = (j + 1)!. See, for example, [11]. In this paper we only consider numeration systems whose digits are bounded by some fixed constant. A necessary condition to ensure bounded digits is that the ratio u_{j}/u_{j−1} is bounded by a constant.

Since, in general, there may be many normal representations with bounded digits for a number n, we must identify one of these representations in order to specify the map r. This can be done in a variety of ways; for example, one could choose r(n) to be the lexicographically greatest representation for n, among all nonnegative linear combinations of terms of the sequence u. The lexicographic order we use is defined as follows: if x = x_{1}x_{2} ⋯ x_{i} and y = y_{1}y_{2} ⋯ y_{j} are strings, we say x is lexicographically greater than y, and write x > y, if i > j, or if i = j and there exists an integer k, 1 ≤ k ≤ i, such that x_{1} = y_{1}, x_{2} = y_{2}, …, x_{k−1} = y_{k−1}, but x_{k} > y_{k}.^{1}

Another possible choice for r(n) is the greedy representation gr(n). We define gr(n) for a positive integer n as follows: let i be the largest index such that u_{i} ≤ n. Then successively set a_{i} ← ⌊n/u_{i}⌋, n ← n − a_{i}u_{i}, and i ← i − 1 until i < 0. If n = ∑_{0≤j≤i} a_{j}u_{j}, then the greedy representation for n is the string a_{i}a_{i−1} ⋯ a_{1}a_{0}, and we say n is greedily representable. If not, then the representation for n is undefined. The greedy representation for 0 is defined to be ϵ, the empty string. The set of greedy representations for all greedily representable integers is written G(u).

1Note that this ordering, called “radix order” by Berstel [1, p. 76] is a well-order (i.e. each nonempty set has a least element), and it differs from the lexicographic order defined by other authors [26, p. 64]; [1]. It is, however, the natural order for our problem.

It is easy to see that every non-negative integer is greedily representable iff u_{0} = 1. If u_{0} ≠ 1, it is possible for a number to be representable, but not greedily representable. For example, consider expressing 4 in the numeration system (u_{0}, u_{1}, u_{2}, …) = (2, 3, 5, …). Note that if u_{0} = 1, then the greedy representation is in fact the lexicographically greatest representation.

A desirable property of any numeration system is that the mapping r that sends an integer n to its representation be order-preserving. More precisely, we require that for integers m, n in the domain of r, we have m > n iff r(m) > r(n). It is easy to see that the greedy representation is order-preserving.

Given a numeration system r, based on the sequence u, we define R(r, u) = R(u) to be the set of its representations for all non-negative integers. More formally,

R(u) = ∑_{{n≥0 \atop n∈Dom r}} r(n).  (2)

Example 1.

Let u_{j} = k^{j}, for k an integer ≥ 2. Then the set of greedy representations G(u) is

ϵ + (1 + 2 + ⋯ + k − 1)(0 + 1 + ⋯ + k − 1)^{∗},

which is nothing more than the ordinary radix-k representation.

If we let u_{j} = j + 1, then the set of greedy representations is simply ϵ + 10^{∗}. This numeration system is essentially “unary” notation.

Example 2.

Let u_{j} = F_{j+2}, where F_{j} is the jth Fibonacci number. Then it can be shown that the set of greedy representations G(u) is

ϵ + 1(0 + 01)^{∗}.

(For more on Fibonacci representations, see [25, Ex. 1.2.8.34], [31], [5], [24], and [2].)

Example 3.

Let u_{j} = 2^{j+1} − 1. Then the set of greedy representations G(u) is

(ϵ + 1(0 + 1)^{∗})(ϵ + 20^{∗}).

See the recent paper of Cameron and Wood [4].

Suppose we are given an increasing sequence of positive integers (u_{j})_{j≥0}, and suppose there is a constant C such that every non-negative integer n has a representation n = ∑_{0≤j≤i} a_{j}u_{j} with 0 ≤ a_{j} ≤ C. Let r(n) be defined as the lexicographically least representation among all such representations for n.

It is not difficult to show that this r is order-preserving. An example is as follows:

Example 4.

Let u_{j} = 2^{j}, and consider expressing integers n as n = ∑_{0≤j≤i} a_{j}u_{j} with 0 ≤ a_{j} ≤ 2. Then Reznick has shown [29] that the number of such such representations is s(n+1), where s(n) is the Stern function, defined by s(0) = 0; s(1) = 1; s(2n) = s(n); and s(2n+1) = s(n)+s(n+1) for n ≥ 1.

Now define r(n) to be the lexicographically least representation of this form for n; for example, r(13) = 221. Then it is easy to see that r(n) is a string of 1’s and 2’s; in fact, R(u), the set all such representations, is (1 + 2)^{∗}. This corresponds to the well-known observation that every non-negative integer can be written uniquely in base 2, using only the digits 1 and 2. Note that this numeration system is not obtained via the greedy algorithm.

The main result of this paper is Theorem 6, which proves the following: suppose the numeration system r is such that the set R(r, u) is regular. Then, subject to some technical conditions on r, the sequence u must satisfy a linear recurrence with integer constant coefficients.

The proof depends on two lemmas about regular sets, which may be of independent interest.

Remarks on the literature.

The point of view we will adopt in this paper is similar to that of Frougny, who has written extensively on this topic. See [13, 14, 15, 16, 17, 18, 19].

In [30], I proved that the set of greedy representations is regular for the numeration systems with bounded digits considered by Fraenkel [11].

We note several other papers that have examined the relationship between ways of representing numbers and regular sets. See [20, 27, 7, 8, 21, 22]. However, these papers have adopted a very different point of view.

2 More Notation

Throughout this paper, Σ is a finite alphabet, and q, s, t denote regular expressions. The letters v, w, x, y, z denote strings. The lower-case letters a, b, c, d, e, g, i, j, k, m, n and the upper-case letters A, B, C denote integers. We also use the letters a and b to represent elements of Σ. The capital letters L and Z denotes languages and the capital letters W, X, Y denote finite languages.

3 Lexicographically Largest Strings

Suppose L is a regular language over a finite alphabet Σ. Suppose Σ has a total ordering; for example, suppose Σ = {0, 1, 2, …, k − 1}. If x, y ∈ Σ^{n}, we say x > y if x is lexicographically greater than y. More precisely, we say x > y if there exists an integer i, 1 ≤ i ≤ n, such that x_{1} = y_{1}, x_{2} = y_{2}, …, x_{i−1} = y_{i−1}, but x_{i} > y_{i}.^{2} Then we informally define B(L) as follows: it is the union, over all n ≥ 0, of the lexicographically largest string of length n in L. ^{3} More formally, define

B(L) = ⋃_{n≥0} {x ∈ L ∩ Σ^{n} : ∀ (y ∈ L ∩ Σ^{n}) x ≥ y}.  (3)

For example, B(1(0 + 01)^{∗}) = (10)^{∗}(ϵ + 1).

Lemma 1 If L is regular, then so is B(L).

Proof.

We show that L − B(L), the relative complement of B(L) in L, is a regular set. From this the result follows: B(L) ⊆ L, and so

(Σ^{∗} − (L − B(L))) ∩ L = B(L).

But regular sets are closed under complement and intersection, and so B(L) is regular.

Let M = (Q, Σ, δ, q_{0}, F) be a deterministic finite automaton accepting L. (See [23] for the basic notions about automata and the notational conventions that we use here.) The idea is to accept L − B(L) with a nondeterministic finite automaton. We use two “fingers” to mimic the behavior of M on input w: the first “finger” imitates M precisely. The second “finger” nondeterministically simulates M on all possible inputs of length |w|, trying to find some string in L that is lexicographically greater than w. If we succeed, and w is accepted by M, then we have found a string in L that is not lexicographically greatest, and so we accept.

More formally, let M′ = (Q′, Σ, δ′, q′_{0}, F′), a nondeterministic finite automaton, where Q′ = Q × Q × {g, e, l}. Here g indicates that in the current state, we have already found a string lexicographically greater than the prefix of the input seen so far. Similarly, e indicates equality, and l indicates less than. For each a ∈ Σ, define

δ′([p, q, g], a) = {[δ(p, a), δ(q, b), g] : b ∈ Σ^{∗}},
δ′([p, q, e], a) = {[δ(p, a), δ(q, b), x] : b ∈ Σ^{∗}},

where x = g if a > b, x = e if a = b, and x = l if a < b, and

δ′([p, q, l], a) = {[δ(p, a), δ(q, b), l] : b ∈ Σ^{∗}}.

Finally, define q′_{0} = [q_{0}, q_{0}, e] and

F′ = {[p, q, l] : p, q ∈ F }.

We leave it to the reader to show that M′ accepts w if and only if w ∈ L − B(L).

2See footnote 1.

3Of course, it is possible that for some n, there is no string of length n in L. These n correspond to no string in B(L). See Eq. (3).

Corollary 2 If L is regular, then so is the set

S(L) = ⋃_{n≥0} {x ∈ L ∩ Σ^{n} : ∀ (y ∈ L ∩ Σ^{n}) x ≤ y}

of lexicographically smallest strings of every length in L.

It is perhaps worthwhile to note that we can use the technique of Lemma 1 to answer a question of D. Klarner (personal communication). He asked, suppose f is a recognizable relation. (For this concept, see Eilenberg [9] or Berstel [1].) Then is it true that the set of lexicographically smallest strings, one chosen from each nonempty equivalence class of f, must be regular? Using the technique above, it is easy to see that the answer is yes. For the case of f being a rational relation, I believe the question is still open.

4 Bounded Regular Sets

In this section we prove that if L is a regular language such that the number of strings of length n in L is bounded by a constant (independent of n), then L is the finite union of sets of particularly simple form. More formally, we have

Lemma 3 The following two statements are equivalent:

(i) L ⊆ Σ^{∗} is regular and there exists a constant c such that |L ∩ Σ^{n}| ≤ c for all n ≥ 0 (ii) L is the finite union of sets of the form xy^{∗}z, where x, y, z ∈ Σ^{∗}.

Proof.

(ii) ⇒ (i): Suppose

L = ∑_{i=1}^{c} x_{i}y_{i}^{∗}z_{i}.

Then for each n ≥ 0, x_{i}y_{i}^{∗}z_{i} contains at most one string of length n. Hence L contains at most c strings of length n.

(i) ⇒ (ii): Let q be a non-trivial regular expression denoting L. (When it is necessary to make the distinction, we will use the notation L(q) to represent the language denoted by the regular expression q.)

The result is clearly true for L = ∅. Thus we may assume that the regular expression q does not contain ∅. We will show the following two “reduction” steps (recalling that the letters X, Y, W denote finite sets):

(a) If q contains a subexpression of the form t^{∗}, then L(t^{∗}) can be rewritten in the form X + Y z^{∗}, and

(b) If q contains a subexpression of the form s_{1}^{∗}ts_{2}^{∗}, where t contains no star, then L(s_{1}^{∗}ts_{2}^{∗}) can be rewritten in the form W z^{∗}X.

The implication (i) ⇒ (ii) will then follow.

(a) Suppose r contains a subexpression of the form t^{∗}. Clearly if |L(t)| ≤ 1, then t^{∗} is already of the form X + Y z^{∗}. Suppose |L(t)| = 2, say L(t) = {x, y}. Choose a positive integer m sufficiently large such that the linear Diophantine equation

a|x| + b|y| = m  (4)

has ≥ c + 1 solutions (a, b) in non-negative integers. (For example, it suffices to choose m = c lcm(|x|, |y|).) Then by the hypothesis, we must have

x^{a}y^{b} = x^{a′}y^{b′}

for some distinct pairs (a, b), (a′, b′) satisfying (4), for otherwise t^{∗} and hence L would contain ≥ c + 1 strings of length n, for some n.

Without loss of generality we may assume a ≥ a′, b ≤ b′. Then

x^{a−a′} = y^{b′−b}.

By [26, Prop. 1.3.1] there exists a string z and integers i, j such that x = z^{i}, y = z^{j}. Hence

(x + y)^{∗} = (z^{i} + z^{j})^{∗} = X + z^{ij}(z^{gcd(i,j)})^{∗}

for some finite set X. Thus we can replace the t^{∗} in q by a set of the form X + Y z^{∗}.

If |L(t)| > 2, we can repeat the argument above on pairs to obtain that each element of L(t) is a power of some string z. Thus, there is some (finite or infinite) set S such that

L(t) = ∑_{i∈S} z^{a_{i}}.

Set g = gcd(a_{1}, a_{2}, …). Then there is a finite subset of the a_{i}, say b_{1} ≤ b_{2} ≤ … ≤ b_{k}, such that g = gcd_{1≤j≤k} b_{j}. Choose m sufficiently large such that eg is a non-negative integer linear combination of the b_{i} for all e ≥ m; by a theorem of Brauer [3, Corollary to Thm. 1], we may in fact choose

m = (b_{1} − 1)(b_{k} − 1).

Let

X = {z^{d} ∈ L(t^{∗}) : d < gm};

note that X is a finite set. I claim that

L(t^{∗}) = X + z^{gm}(z^{g})^{∗}.

For let z^{d} ∈ L(t^{∗}); if d < gm, then z^{d} ∈ X, by construction. Otherwise d ≥ gm; clearly d must be a multiple of g and hence z^{d} ∈ z^{gm}(z^{g})^{∗}.

It remains to see that z^{gm}(z^{g})^{∗} ⊆ L(t^{∗}). We know that if e ≥ m, then eg is a nonnegative integer linear combination of the b_{i}. Hence every string z^{eg} with e ≥ m must be in (z^{b_{1}} + z^{b_{2}} + ⋯ + z^{b_{k}})^{∗}, and hence in L(t^{∗}). This completes the proof of (a) and shows incidentally that L is of star-height 1. Hence by a theorem of Cohen [6, Lemma 3.1], we may assume that

L = Z_{1} + Z_{2} + ⋯ + Z_{j},

where each set Z_{i} can be written in the form

w_{1}x_{1}^{∗}w_{2}x_{2}^{∗} ⋯ w_{k}x_{k}^{∗}w_{k+1}.  (5)

To prove (b), suppose q contains a subexpression of the form s_{1}^{∗}ts_{2}^{∗}. Then by Eq. (5) we may assume without loss of generality that L(s_{1}) = {x}, L(s_{2}) = {y}, and L(t) = {z}.

As above, choose m sufficiently large such that

a|x| + b|y| = m  (6)

has ≥ c + 1 solutions. Then by the hypothesis that L contains no more than c strings of length n for all n, we must have

x^{a}zy^{b} = x^{a′}zy^{b′}

for two distinct pairs (a, b), (a′, b′) satisfying (6). We may assume without loss of generality that a > a′ and b < b′. Then

x^{a−a′}z = zy^{b′−b}.

Using [26, Prop. 1.3.4], we see that there exist strings v, w and an integer e such that

x^{a−a′} = vw; y^{b′−b} = wv; z = v(wv)^{e} = (vw)^{e}v.

Hence

x^{a−a′}zy^{b′−b} = (vw)^{e+2}v.

Thus we see that

x^{∗}zy^{∗} = (ϵ + x + x^{2} + ⋯ + x^{A−1})(vw)^{∗}(vw)^{e}v(wv)^{∗}(ϵ + y + y^{2} + ⋯ + y^{B−1}),

where A = a − a′ and B = b′ − b. Thus we have x^{∗}zy^{∗} = X(vw)^{∗}Y for finite sets X and Y.

To complete the proof of the lemma, we apply observation (b) repeatedly to terms of the form (5). At each stage, a term with k > 1 stars is reduced to a sum of terms with k − 1 stars. The final result is a sum of terms with one star, and the result follows.

After the author proved Lemma 3, other proofs were shown to him by S. Yu and F. Fich.

5 Two Lemmas on Linear Recurrences

In this section we provide two useful lemmas about linear recurrences.

Suppose we are given a sequence whose even and odd-numbered terms each satisfy a linear recurrence with integer coefficients, but not the same one, such as

A_{2n} = 2A_{2n−1} + A_{2n−2}
A_{2n−1} = 3A_{2n−2} + A_{2n−3} + A_{2n−4} − A_{2n−5}.  (7)

Can we then conclude that the sequence A_{n} itself satisfies a linear recurrence with integer coefficients?

The answer is yes, as the following lemma shows:

Lemma 4 Let k, d be positive integers, with d ≥ k, and let M = [M_{ij}] be a k × d matrix of integers such that for all n sufficiently large we have

A_{kn} = M_{11}A_{kn−1} + M_{12}A_{kn−2} + ⋯ + M_{1d}A_{kn−d}
A_{kn−1} = M_{21}A_{kn−2} + M_{22}A_{kn−3} + ⋯ + M_{2d}A_{kn−d−1}
⋮
A_{kn−k+1} = M_{k1}A_{kn−k} + M_{k2}A_{kn−k−1} + ⋯ + M_{kd}A_{kn−k−d+1}.

Then the sequence A_{n} itself satisfies a linear recurrence with constant coefficients.

Proof.

Note that d is the maximum degree of the characteristic polynomials for the subsequences A_{kn}, A_{kn+1}, …, A_{kn+k−1}.

By successively substituting the relations for A_{kn−1}, A_{kn−2}, ⋯ in the relation for A_{kn}, etc., we can find a d × d matrix P = [P_{ij}] such that for all n sufficiently large, we have

A_{kn} = P_{11}A_{kn−k} + P_{12}A_{kn−k−1} + ⋯ + P_{1d}A_{kn−k−d+1}
A_{kn−1} = P_{21}A_{kn−k} + P_{22}A_{kn−k−1} + ⋯ + P_{2d}A_{kn−k−d+1}
⋮
A_{kn−d+1} = P_{d1}A_{kn−k} + P_{d2}A_{kn−k−1} + ⋯ + P_{dd}A_{kn−k−d+1}.

Let f(X) be the characteristic polynomial of P. Then each of the sequences

A_{kn}, A_{kn−1}, …, A_{kn−k+1}

satisfies the same linear recurrence, namely, the one whose characteristic polynomial is f(X) (at least for n sufficiently large). Thus for n large enough, A_{n} satisfies the linear recurrence whose characteristic polynomial is f(X^{k}).

Example.

For the recurrence specified by (7), we get

[ \begin{matrix}A_{2n} \\ A_{2n−1} \\ A_{2n−2} \\ A_{2n−3} \end{matrix} ] = [ \begin{matrix}7 & 2 & 2 & −2 \\ 3 & 1 & 1 & −1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} ] [ \begin{matrix}A_{2n−2} \\ A_{2n−3} \\ A_{2n−4} \\ A_{2n−5} \end{matrix} ] .

The characteristic polynomial for the matrix is X^{4} − 8X^{3} − X, so A_{n} satisfies the recurrence A_{n} = 8A_{n−2} + A_{n−6}.

Our second lemma concerns integer linear recurrences with rational coefficients.

Lemma 5 Suppose the infinite integer sequence u_{0}, u_{1}, u_{2}, … satisfies a linear recurrence relation

u_{n} = a_{1}u_{n−1} + a_{2}u_{n−2} + ⋯ a_{d}u_{n−d},

for all n ≥ 0, where each a_{i} is a rational number. Then u_{n} satisfies a (possibly different) linear recurrence relation where all the a_{i} are actually integers.

Proof.

This follows immediately from the following lemma of Fatou [10] (also see [28, Part VIII, Problem 156]): if v(z) is a rational function whose Taylor series has rational integer coeffcients, then v(z) can be written in the form f(z)/g(z), where f and g are polynomials with integer coefficients and g(0) = 1.

6 Proof of the Main Result

In this section, we prove the result mentioned in the introduction. The details of the proof are a little messy, so it may be helpful to first give the proof in the case of ordinary base-3 representation. In this case, the set of representations R(u) is ϵ + (1 + 2)(0 + 1 + 2)^{∗}. It is easy to see that B(R(u)), the set of lexicographically greatest representations, is 2^{∗}. Since

val(1 \overbrace{00 ⋯ 0}^{k}) = 1 + val(\overbrace{22 ⋯ 2}^{k}),

it follows that

u_{k} = 1 + 2u_{k−1} + 2u_{k−2} + ⋯ + 2u_{0}.  (8)

Similarly, we also have

u_{k+1} = 1 + 2u_{k} + 2u_{k−1} + ⋯ + 2u_{0}.  (9)

Subtracting (8) from (9), we see

u_{k+1} − u_{k} = 2u_{k},

and hence u_{k+1} = 3u_{k}.

We now state and prove the main result of the paper:

Theorem 6 Let u_{0}, u_{1}, … be a strictly increasing sequence of non-negative integers, and let r be a linear numeration system based on u. Let R(u) be as in Eq. (2). Suppose that

(a) gcd(u_{0}, u_{1}, …) = g, and r(kg) is defined for all sufficiently large integers k;

(b) for all sufficiently large n, there exists a representation in R(u) of length n; and

(c) r is order-preserving.

If R(u) is regular, then the sequence u = (u_{n})_{n≥0} satisfies a linear recurrence with integer constant coefficients.

Before we begin the proof, let us explain the role of the technical hypotheses (a)–(b). For (a), if gcd(u_{0}, u_{1}, …) = g, then every sufficiently large multiple of g has some representation as a non-negative integer linear combination of the u_{i}. We wish to avoid the case where “most” representable integers simply are not in the domain of the partial function r.

Hypothesis (b) is needed to exclude cases such as the following: suppose our numeration system is

1, u_{0}, 10, u_{1}, 100, u_{2}, …,  (10)

where u is any sequence that does not satisfy a linear recurrence, and 10^{i} < u_{i} ≤ 10^{i+1}. If we choose as our numeration system ordinary base-10 representation, and simply never use the u_{i} in any representation, we get a numeration system that is order-preserving, and a set of representations which is regular. However, the sequence (10) clearly does not satisfy a linear recurrence.

Note that hypothesis (b) is satisfied by both the greedy representation and the lexicographically greatest representation, for in these cases we have the representation of u_{n} is 1 0^{n}. In fact, if u_{0} = 1, then all three hypotheses are satisfied when r is the greedy representation.

Now let us begin the proof of Theorem 6.

Proof.

Let g = gcd(u_{0}, u_{1}, …). Then by hypothesis (a), there exists an integer C such that r(n) is defined for all n ≥ C with g | n.

If L = R(u) is regular, then by Lemma 1, the set B(L) of lexicographically greatest strings of every length in L is also regular. By hypothesis (b) of the theorem, there exists C′ such that B(L) exactly one string of length j for each j ≥ C′. Thus Lemma 3 applies and so

B(L) = ∑_{i=1}^{k} x_{i}y_{i}^{∗}z_{i}.  (11)

Similarly, by Corollary 2, the set S(L) can also be written in the form

∑_{i=1}^{k′} x′_{i}y′_{i}^{∗}z′_{i}.

To avoid unnecessary complication, we first show how the proof goes in the case S(L) = 1 0^{∗}. At the end of the proof we sketch what needs to be done when S(L) ≠ 1 0^{∗}. (Note that in fact S(L) = 1 0^{∗} for the most common case, when r is the greedy representation.)

The main idea of the proof is as follows: let w ∈ B(L) be sufficiently long such that val(w) > max(C, C′). Let v ∈ S(L) be such that |v| = |w| + 1. Then by hypothesis (c) (i.e., r is order-preserving), we must have val(v) = val(w) + g. Since S(L) = 10^{∗}, we have

u_{|w|} = val(w) + g.  (12)

Now let

g′ = lcm_{{1≤j≤k \atop |y_{j}|≠0}} |y_{j}|.

By replacing y_{i} with y_{i}^{g′/|y_{i}|}, adding extra terms to x_{i} and z_{i}, and renaming, we can rewrite (11) such that |y_{i}| = g′ for all i for which |y_{i}| ≠ 0.

Consider a particular term of the sum in (11), say xy^{∗}z. From (12) we have

u_{j|y|+|xz|} = val(xy^{j}z) + g.

We also have

u_{(j+1)|y|+|xz|} = val(xy^{j+1}z) + g.

Subtracting, we see

u_{(j+1)|y|+|xz|} − u_{j|y|+|xz|} = val(xy^{j+1}z) − val(xy^{j}z)
= val(xy0^{j|y|+|z|}) − val(x0^{j|y|+|z|}),

and the last expression on the right is a linear combination of terms of u such that the smallest coefficient which is possibly non-zero corresponds to u_{j|y|+|z|}. Hence for j sufficiently large, the subsequence u_{(j+1)g′+i} can be expressed as a non-trivial integer linear combination of the g′ + |x| previous terms of u, and the particular linear combination depends only on the value of i (mod g′).

By Lemma 4, we can write u itself as a linear recurrence. This completes the proof in the case where r(n) = 1 0^{n}.

It remains to discuss what needs to be done to handle the more general case, when S(L) is not necessarily equal to 1 0^{∗}. The same techniques apply, except that since the leading coefficient of the recurrence we obtain is no longer necessarily 1, we see that u is a linear recurrence with rational coefficients. Then by Lemma 5, we see that the linear recurrence actually has integer coefficients. This completes the proof.

7 Linear Recurrences and Non-Regular Sets

After seeing the main theorem, one immediately wonders if the converse is true. It is not, as the following theorem shows:

Theorem 7 Suppose u_{j} = (j + 1)^{2} for j ≥ 0. Then the set G(u) of greedy representations is not a regular set.

Note that u_{j}, of course, satisfies the linear recurrence u_{j+3} = 3u_{j+2} − 3u_{j+1} + u_{j} for all j ≥ 0.

Proof.

Let G(u) be the set of greedy representations, and assume it is regular. Then G(u) ∩ 10^{∗}10^{∗} would also be a regular set. However, it is easy to see that

G(u) ∩ 10^{∗}10^{∗} = {10^{a}10^{b} : u_{b+a+2} > u_{b+a+1} + u_{b}}
= {10^{a}10^{b} : b^{2} < 2a + 4},

and this set is evidently not regular.

One would like a simple characterization of those sequence u for which G(u) is regular. The next example shows that such a characterization based on the characteristic polynomial of the recurrence alone will not suffice.

Let f_{j} = 2^{j} + 1 for j ≥ 0. In this numeration system, where the digits are bounded by 2, every integer except 1 has some representation. Let r(n) denote the lexicographically greatest representation for n. (Note that 4 = val(2) > val(10) = 3; hence r is not order-preserving.) Then

R(f) ∩ 1^{∗}0^{∗} = {1^{a}0^{b} : f_{b+a} > f_{b+a−1} + f_{b+a−2} + ⋯ + f_{b}}
= {1^{a}0^{b} : a < 2^{b} + 1},

and this set is clearly not regular. Hence R(f) is not regular. However, f_{j} satisfies the same linear recurrence as the sequence u_{j} = 2^{j+1} − 1 discussed previously in Section 1 (namely f_{j+2} = 3f_{j+1} − 2f_{j} for j ≥ 0), for which G(u) is regular.

It is an open problem to give a sufficient condition for the regularity of R(u).

8 Acknowledgments

An earlier version of Lemma 3 dealt with the case c = 1. I am grateful to E. Bach for having suggested the stronger formulation given in this paper. I would also like to thank A. Lubiw for general discussion and for suggesting an appropriate way to weaken the hypotheses in Theorem 6. C. Stewart pointed out the lemma of Fatou.

References

[1] J. Berstel. Transductions and Context-Free Languages. Teubner, Stuttgart, 1979.

[2] J. Berstel. Fibonacci words – a survey. In G. Rozenberg and A. Salomaa, editors, The Book of L, pages 13–27. Springer-Verlag, 1986.

[3] A. Brauer. On a problem of Frobenius. Amer. J. Math. 64 (1942), 299–312.

[4] H. Cameron and D. Wood. Pm numbers, ambiguity, and regularity. Technical Report CS-91-47, University of Waterloo, Department of Computer Science, September 1991.

[5] L. Carlitz. Fibonacci representations. Fibonacci Quart. 6(4) (1968), 193–220.

[6] R. S. Cohen. Star height of certain families of regular events. J. Comput. System Sci. 4 (1970), 281–297.

[7] K. Culik II and A. Salomaa. Ambiguity and decision problems concerning number systems. Inform. and Comput. 56 (1983), 139–153.

[8] A. de Luca and A. Restivo. Representations of integers and language theory. In Math. Found. Comp. Sci., Vol. 176 of Lecture Notes in Computer Science, pages 407–415. Springer-Verlag, 1984.

[9] S. Eilenberg. Automata, Languages, and Machines (Vol. A). Academic Press, New York, 1974.

[10] P. Fatou. Séries trigonométriques et séries de Taylor. Acta Math. 30 (1906), 335–400.

[11] A. S. Fraenkel. Systems of numeration. Amer. Math. Monthly 92 (1985), 105–114.

[12] A. S. Fraenkel. The use and usefulness of numeration systems. Inform. and Comput. 81 (1989), 46–61.

[13] C. Frougny. Fibonacci numeration systems and rational functions. In Math. Found. Comp. Sci., Vol. 233 of Lecture Notes in Computer Science, pages 350–359. Springer-Verlag, 1986.

[14] C. Frougny. Linear numeration systems of order two. Inform. and Comput. 77 (1988), 233–259.

[15] C. Frougny. Linear numeration systems, θ–developments and finite automata. In B. Monien and R. Cori, editors, STACS 89, Vol. 349 of Lecture Notes in Computer Science, pages 144–155. Springer-Verlag, 1989.

[16] C. Frougny. Systèmes de numération lineaires et automates finis (Thèse d’État). Technical Report 89-69, Laboratoire Informatique Théorique et Programmation, Université P. et M. Curie, Université Paris VII, September 1989.

[17] C. Frougny. Representations of numbers and finite automata. Math. Systems Theory (1991), to appear.

[18] C. Frougny. Fibonacci representations and finite automata. IEEE Trans. Inform. Theory 37 (1991), 393–399.

[19] C. Frougny. Representation of numbers in non-classical numeration systems. In P. Kornerup and D. W. Matula, editors, Proc. 10th IEEE Symp. Computer Arithmetic, pages 17–21. IEEE Computer Society Press, 1991.

[20] J. Honkala. Unique representation in number systems and L codes. Disc. Appl. Math. 4 (1982), 229–232.

[21] J. Honkala. Bases and ambiguity in number systems. Theoret. Comput. Sci. 31 (1984), 61–71.

[22] J. Honkala. A decision method for the recognizability of sets defined by number systems. RAIRO Informatique Théorique 20 (1986), 395–403.

[23] J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

[24] W. H. Kautz. Fibonacci codes for synchronization control. IEEE Trans. Inform. Theory IT-11 (1965), 284–292.

[25] D. E. Knuth. Fundamental Algorithms, Vol. I of The Art of Computer Programming. Addison-Wesley, 1973.

[26] M. Lothaire. Combinatorics on Words, Vol. 17 of Encyclopedia of Mathematics and Its Applications. Addison-Wesley, 1983.

[27] H. A. Maurer, A. Salomaa, and D. Wood. L codes and number systems. Theoret. Comput. Sci. 22 (1983), 331–346.

[28] G. Pólya and G. Szegö. Problems and Theorems in Analysis, Vol. II. Springer-Verlag, Berlin, 1976.

[29] B. Reznick. Some binary partition functions. In B. C. Berndt, H. G. Diamond, H. Halberstam, and A. Hildebrand, editors, Analytic Number Theory (Proceedings of a Conference in Honor of Paul T. Bateman), pages 451–477. Birkhäuser, Boston, 1990.

[30] J. Shallit. A generalization of automatic sequences. Theoret. Comput. Sci. 61 (1988), 1–16.

[31] E. Zeckendorf. Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. Royale des Sciences de Liège 3-4 (1972), 179–182.