Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 39 (1998), No. 1, 219-229.

Automaticity of Rational Functions

F. v. Haeseler^{1} A. Petersen^{2}

CeVis, Universität Bremen Postfach 330440, 28334 Bremen, Germany e-mail: Fritz@mathematik.uni-Bremen.de e-mail: Antje@mathematik.uni-Bremen.de

Abstract. We study double sequences with values in a finite commutative ring R. We discuss under which conditions a double sequence, which is given by a rational function, is definable in ⟨ℕ, +⟩. Moreover, we give a complete characterization of the automaticity properties of double sequences defined by rational functions with coefficients in the ring ℤ/(m) = ℤ/mℤ. Thus answering a question posed by Salon in [15], p. II-9.

Introduction

Let R be a non–trivial finite commutative ring with one, denote by R^{∗} the multiplicative group of units of R, and let p(x), q(x) ∈ R[x], q(0) ∈ R^{∗}, be polynomials. Then f(x) = \frac{p(x)}{q(x)} is a rational function. Associated with this rational function is its formal power series

f(x) = \frac{p(x)}{q(x)} = ∑_{n=0}^{∞} s(n)x^{n},

with coefficients s(n) ∈ R. It is a well known fact that the sequence {s(n)}_{n≥0} is ultimately periodic. In fact, the converse is also true. If {s(n)}_{n≥0} ∈ R^{ℕ} is an ultimately periodic sequence then f(x) = ∑_{n=0}^{∞} s(n)x^{n} is a rational function. In the framework of automatic sequences, cf. [1] for a good introduction, an ultimately periodic sequence {s(n)}_{n≥0} is k– automatic for all k ≥ 2.

1Supported by the DFG-Forschergruppe “Dynamische Systeme”

2Supported by DFG-Graduiertenkolleg “Komplexe Dynamische Systeme”

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1998 Heldermann Verlag

Now let P (X, Y), Q(X, Y) ∈ R[X, Y] be polynomials with Q(0, 0) ∈ R^{∗}, then

F (X, Y) = \frac{P (X, Y)}{Q(X, Y)} = ∑_{n,t=0}^{∞} s(n, t)X^{n}Y^{t},

is called a rational function with coefficients in R. In the sequel we always assume the polynomials P (X, Y) and Q(X, Y) to be coprime. In this paper, we discuss the automaticity properties of the double sequence {s(n, t)}_{n,t≥0} defined by a rational function F (X, Y) ∈ R(X, Y).

As the work of Allouche et al. [2, 3] exhibits, a characterization of the automaticity properties of double sequences defined by rational functions over a ring is much more delicate than the one–dimensional case. As an example, we consider the rational function \frac{1}{1−Y (1+X)} with coefficients in ℤ/(2). Due to the theorems in [3], we have that the double sequence {s(n, t)}_{n,t≥0} defined by

∑_{n,t=0}^{∞} s(n, t)X^{n}Y^{t} = \frac{1}{1 − Y (1 + X)}

is 2^{α}–automatic for all α ≥ 1 and is not k–automatic for any other k, see also Korec [12].

Thus, even for “simple” rational functions of two variables, it is not true that the double sequence \{s(n, t)\}_{n,t≥0} is k–automatic for all k ≥ 2. Moreover, if one considers \frac{1}{1−Y (1+X)}, with coefficients in ℤ/(6), then the double sequence is not k–automatic for any k ≥ 2.

There is yet another interpretation of the rational function \frac{1}{1−Y (1+X)} which is the point of view expressed in [3]. We have the following formal identity,

F (X, Y) = \frac{1}{1 − Y (1 + X)} = ∑_{t=0}^{∞} Y^{t}(1 + X)^{t},

which holds, of course, in any commutative ring R. Therefore we can interpret F (X, Y) as the complete orbit of a cellular automaton which is defined by the polynomial R(X) = 1+X. To be more precise, any polynomial R(X) ∈ R[X] defines a (linear) cellular automaton (LCA) by ∑_{j∈ℤ} α_{j}X^{j} ↦ R(X)(∑_{j∈ℤ} α_{j}X^{j}), which is simply the multiplication of a polynomial by a formal Laurent series. Thus, the automaticity of the double sequence {s(n, t)}_{n,t≥0} yields certain regularity features of the dynamics of the associated cellular automaton.

In this framework, the authors of [2] prove the following theorem.

Theorem. (Automaticity of orbits of LCA)

Let m ∈ ℕ, m ≥ 2 and let F (X, Y) = \frac{A(X)}{1−Y R(X)} ∈ ℤ(X, Y), with A(X) ≢ 0 modulo m.

1. If there exist at least two different prime divisors p and q of m such that R(X) modulo p and R(X) modulo q are not monomials then F (X, Y) modulo m is not k–automatic for any k ≥ 2.

2. If there exists exactly one prime divisor p of m such that R(X) modulo p is not a monomial then F (X, Y) modulo m is p–automatic (p^{α}–automatic for any α ≥ 1) and not k–automatic for any other k.

3. If R(X) modulo p is a monomial for all prime divisors p of m then F (X, Y) modulo m is k–automatic for all k ≥ 2.

The main ingredients of the proof are the so called Slice Lemma. The Slice Lemma and Cobham’s theorem ensure the existence of one–dimensional subsequences {s(αn, βn)}_{n∈ℕ} (the slices) which are not ultimately periodic. The existence of these slices relies heavily on the special form of the rational function under consideration.

Note that the above theorem completely characterizes the automaticity properties of certain rational functions. In the sequel, we present a characterization for arbitrary rational functions.

In order to formulate the main result, we introduce some notation. Let P (X, Y) ∈ R[X, Y] be a polynomial. Then P (X, Y) has the monomial factor property (over R) if there exist a polynomial S(X, Y) ∈ R[X, Y] and finitely many monomials δ_{j}(X, Y) = ρ_{j}X^{n_{j}}Y^{t_{j}}, j = 1, …, N such that

S(X, Y)P (X, Y) = ∏_{j=1}^{N}(1 − δ_{j}(X, Y)).

Let m ∈ ℕ, m ≥ 2, and let F (X, Y) = \frac{P (X,Y)}{Q(X,Y)} ∈ ℤ(X, Y), P (X, Y) ≢ 0 modulo m, be a rational function. Then we define

M_{m}(F (X, Y)) = { p | p is a prime divisor of m and Q(X, Y) mod p does not have the monomial factor property over ℤ/(p). }

Furthermore, χ_{m}(F) denotes the cardinality of M_{m}(F (X, Y)).

Then the main result can be stated as follows.

Theorem. (Automaticity of rational functions)

Let m ∈ ℕ, m ≥ 2 and let F (X, Y) = \frac{P (X,Y)}{Q(X,Y)} ∈ ℤ(X, Y) be a rational function. Then the following holds

1. If χ_{m}(F) ≥ 2, then F (X, Y) modulo m is not k–automatic for any k ≥ 2.

2. If χ_{m}(F) = 1, then F (X, Y) modulo m is p^{α}–automatic for all α ∈ ℕ \ {0} and p ∈ M_{m}(F (X, Y)) and F (X, Y) modulo m is not k–automatic for all k ≠ p^{α}.

3. If χ_{m}(F) = 0, then F (X, Y) modulo m is definable in ⟨ℕ, +⟩, i.e., k–automatic for all k ≥ 2.

The paper is organized as follows. In Section 1, we give the necessary definitions of automaticity and of the definability of sequences. Moreover, we point out the important connections between these two apparently different concepts. In Section 2, we characterize rational functions of two variables such that the associated double sequence is k–automatic for all k ≥ 2. Finally, Section 3 is devoted to the proof of the Main Theorem.

For the sake of simplicity we restrict our proofs to the two–dimensional case, but all results can be directly extended to the multidimensional case.

1. Preliminaries

Let R be a finite commutative ring with zero and one. We study sequences s : ℕ^{2} → R. Associated with any such sequence is a formal power series F (X, Y) = ∑_{n,t≥0} s(n, t)X^{n}Y^{t} over the ring R. Any subset S ⊂ ℕ^{2} can be viewed as a sequence by identifying the set with its characteristic sequence

χ_{S}(n, t) = \{ \begin{matrix}1 & if (n, t) ∈ S \\ 0 & otherwise. \end{matrix}

Associated with the characteristic sequence is its formal power series

χ_{S}(X, Y) = ∑_{n,t≥0} χ_{S}(n, t)X^{n}Y^{t}.

Considering sequences, one can ask for certain regularity features. The simplest regularity feature is the periodicity of one–dimensional sequences. Another important regularity feature of (not necessarily one–dimensional) sequences, is the k–automaticity.

Definition 1. Let k ∈ ℕ, k ≥ 2. A two–dimensional sequence

s = {s(n, t)}_{n,t≥0}, with s(n, t) ∈ R

is called k–automatic if its k–kernel, i.e., the set of subsequences

{(n, t) → s(k^{i}n + j, k^{i}t + ℓ); i ≥ 0, 0 ≤ j, ℓ ≤ k^{i} − 1}

is finite.

If a sequence {s(n, t)}_{n,t≥0} is k–automatic then there exists a finite k–automaton generating the sequence (see [14]). Moreover, we say that a subset S ∈ ℕ is k–automatic if its characteristic sequence is k–automatic.

Given two sequences s : ℕ^{2} → R and s̃ : ℕ^{2} → R and their associated power series F (X, Y), F̃(X, Y), respectively, we can define the sum of s and s̃ by F (X, Y) + F̃(X, Y) and the product of s and s̃ is generated by the product F (X, Y)F̃(X, Y).

It is an important observation that the sum and the product of two k–automatic sequences are again k–automatic.

Since the theory of automatic sequences is closely related to logic we present some elementary concepts from logic.

By V_{k} : ℕ \ {0} → ℕ we denote the function which sends x to the greatest power of k which divides x and by P_{k} we denote the set of powers of k. In the sequel we will only consider first–order logic.

Definition 2. (cf. [5]) We say that a set S ⊂ ℕ^{2} is definable in the structure ⟨ℕ, +, V_{k}⟩, if it can be defined by a formula built up from =, + and V_{k} using only ∧ (“and”), ∨ (“or”), ¬ (“not”), → (“if … then …” ), ∃x (“there exists x ∈ ℕ …”, where x is a symbol for a variable) and ∀x (“for all x ∈ ℕ …”, where x is a symbol for a variable).

We say that S is definable in ⟨ℕ, +⟩ if it can be defined by a formula of the above type, without using V_{k}. And for P_{k} a subset of ℕ we say that S is definable in ⟨ℕ, +, P_{k}⟩ if it can be defined in the above way using now also the relation P_{k}(x), meaning x ∈ P_{k} (x being either a natural number or tuples of natural numbers according to the case).

Identifying a set S ⊂ ℕ^{2} with its characteristic sequence χ_{S} : ℕ^{2} → {0, 1} we say that the sequence χ_{S} is definable in a certain structure if S is definable in this structure. For the general case of sequences s : ℕ^{2} → R, where R is not necessarily equal to {0, 1}, we need a new definition.

Definition 3. (cf. [5]) A sequence s : ℕ^{2} → R is said to be definable in ⟨ℕ, +, V_{k}⟩ if its graph {(n_{1}, n_{2}, r) ∈ ℕ^{2} × R : r = s(n_{1}, n_{2})} is definable in ⟨ℕ, +, V_{k}⟩.

As a consequence, we obtain that a sequence s : ℕ^{2} → R is definable in ⟨ℕ, +, V_{k}⟩ if and only if each of the sets M_{r} = s^{−1}(r), r ∈ R, is definable in ⟨ℕ, +, V_{k}⟩.

Remark. Given a sequence s : ℕ^{2} → R, we can represent the associated formal power series F (X, Y) = ∑_{n,t≥0} s(n, t)X^{n}Y^{t} by F (X, Y) = ∑_{r∈R} rF_{r}(X, Y), where F_{r}(X, Y) = χ_{M_{r}}(X, Y).

In 1960, Büchi [6] developed the idea of relating the notions of k–automaticity and definability. He conjectured that a sequence s : ℕ^{2} → A, where A is a finite set, is definable in the structure ⟨ℕ, +, P_{k}⟩ if and only if it is k–automatic. His conjecture was claimed to be wrong by McNaughton [13] and has been disproved by Semenov [16]. In 1985, Boffa suggested to replace P_{k} by the function V_{k}, see [5].

The modified conjecture has been proved to be true by Bruyère [4].

Theorem. (Büchi–Bruyère) Let k ≥ 2 be an integer and let s : ℕ^{2} → A be a sequence. Then the sequence s is k–automatic if and only if it is definable in ⟨ℕ, +, V_{k}⟩.

Now we can state the two-dimensional version of Cobham’s theorem [5, 8, 16].

Theorem. (Cobham–Semenov) Let p, q ≥ 2 be multiplicatively independent integers and let s : ℕ^{2} → A be a sequence. If s is definable in ⟨ℕ, +, V_{p}⟩ and definable in ⟨ℕ, +, V_{q}⟩, then s is definable in ⟨ℕ, +⟩.

As a consequence of the above theorems we obtain that a sequence s : ℕ^{2} → A is k–automatic for all k ≥ 2 if it is definable in ⟨ℕ, +⟩.

From [5] we learn that a sequence s : ℕ^{2} → A is definable in ⟨ℕ, +⟩ if and only if for each a ∈ A the set M_{a} = s^{−1}(a) is semilinear (see [10] for a proof). Moreover, a subset S ⊂ ℕ^{2} is semilinear if and only if it is definable in ⟨ℕ, +⟩. Semilinear sets give a grid–like pattern on ℕ^{2}, which is similar to the notion of periodicity we have in one dimension.

Consider the monoid (ℕ^{2},+), where + is the usual addition. Let A, B ⊂ ℕ^{2}. The “sum” A + B is defined by A + B = {c ∈ ℕ^{2} | ∃a ∈ A, ∃b ∈ B : c = a + b}. Given any subset P of ℕ^{2}, the set P^{∗} = ⋃_{n≥0} P_{n}, where P_{0} = {(0, 0)} and P_{n+1} = P_{n} + P, is the set of all linear combinations of elements of P respectively the set of all finite sums ∑ α_{i}p_{i}, α_{i} ∈ ℕ, p_{i} ∈ P. The set P^{∗} is called the submonoid of ℕ^{2} generated by P.

Definition 4. (cf. [11]) A set S ⊂ ℕ^{2} is said to be linear in ℕ^{2} (or for short linear) if there exists an element e ∈ ℕ^{2} and a finite set S̃ ⊂ ℕ^{2} such that S = e + S̃^{∗}.

A set S ⊂ ℕ^{2} is said to be semilinear in ℕ^{2} (or for short semilinear) if it can be represented by a finite union of linear sets, i.e., if there exist e_{1}, …, e_{ℓ} ∈ ℕ^{2} and S̃_{1}, …, S̃_{ℓ} ⊂ ℕ^{2} such that S = ⋃_{i=1}^{ℓ}(e_{i} + S̃_{i}^{∗})

The semilinear subsets of ℕ^{2} are of the form:

S = ⋃_{i=1}^{ℓ}((α_{i}, β_{i}) + {(n_{i1}, t_{i1}), …, (n_{iv_{i}}, t_{iv_{i}})}^{∗}).

Example. (to be continued)

S = (11, 1)
∪ (2, 5)^{∗}
∪ (5, 3) + {(2, 1), (1, 2), (2, 3)}^{∗}

For the characterization of subsets S ⊂ ℕ^{2} which are definable in ⟨ℕ, +⟩ the notion of unambiguously semilinear sets is very important.

Definition 5. (cf. [11]) A set S ⊂ ℕ^{2} is said to be unambiguously linear if it is representable as a linear set S = e + S̃^{∗}, where the elements of the set S̃ are linearly independent.

A set S ⊂ ℕ^{2} is said to be unambiguously semilinear if it is representable as the disjoint union of unambiguously linear sets.

Remark. Every semilinear set is unambiguously semilinear [9, 11]. In particular, if S = ⋃_{i=1}^{ℓ}(e_{i} + S̃_{i}^{∗}) is an unambiguous representation of a semilinear set in ℕ^{2} then each of the sets S̃_{i} contains at most two elements, as any third element would be ℝ–linearly dependent of the first two.

Example. (continued) The unambiguous representation of S is given by

S = (11, 1)
∪ {(2, 5)}^{∗}
∪ (5, 3) + {(2, 1)}^{∗}
∪ (6, 5) + {(2, 1), (1, 2)}^{∗}
∪ (7, 6) + {(2, 1), (1, 2)}^{∗}
∪ (9, 9) + {(2, 1), (1, 2)}^{∗}

We will summarize some important equivalences pointed out in this section:

(1) A sequence s : ℕ^{2} → A is k–automatic if and only if it is definable in ⟨ℕ, +, V_{k}⟩.

(2) A sequence s : ℕ^{2} → A is k–automatic for all k ≥ 2 if and only if it is definable in ⟨ℕ, +⟩.

(3) A sequence s : ℕ^{2} → A is definable in ⟨ℕ, +⟩ if and only if for each a ∈ A the set M_{a} = s^{−1}(a) is semilinear.

(4) A subset S ⊂ ℕ^{2} is k–automatic for all k ≥ 2 if and only if S is definable in ⟨ℕ, +⟩.

(5) A subset S ⊂ ℕ^{2} is definable in ⟨ℕ, +⟩ if and only if it is semilinear.

It is obvious how to generalize the above theories to more than 2 dimensions, cf. [5].

2. Semilinear sets and rational functions

In this section, we characterize subsets S ⊂ ℕ which are definable in ⟨ℕ, +⟩ with the help of their characteristic formal power series. Then we consider sequences s : ℕ^{2} → R which are definable in ⟨ℕ, +⟩ and their corresponding power series. The chapter culminates in a characterization of rational functions which are definable in ⟨ℕ, +⟩. Throughout this section let R be a non–trivial finite commutative ring with one.

Lemma 1. A set S ⊂ ℕ^{2} is definable in ⟨ℕ, +⟩ if and only if its characteristic formal power series is of the form

χ_{S}(X, Y) = ∑_{i=1}^{ℓ} X^{α_{i}}Y^{β_{i}} ∏_{j=1}^{v_{i}} \frac{1}{1 − X^{n_{ij}}Y^{t_{ij}}} = ∑_{i=1}^{ℓ} G_{i}(X, Y) ∈ R(X, Y),

with 0 ≤ v_{i} ≤ 2, ∏_{j=1}^{0} = 1, (α_{i}, β_{i}), (n_{ij}, t_{ij}) ∈ ℕ^{2} where the G_{i}(X, Y) have disjoint supports and for each i = 1, …, ℓ the vectors (n_{ij}, t_{ij}) are ℝ-linearly independent.

Proof. A set S ⊂ ℕ^{2} is definable in ⟨ℕ, +⟩ if and only if it is semilinear. Let S be a semilinear set and let

S = ⋃_{i=1}^{ℓ}((α_{i}, β_{i}) + {(n_{i1}, t_{i1}), (n_{i2}, t_{i2})}^{∗})

be an unambiguous representation of S, where (n_{i1}, t_{i1}) or (n_{i2}, t_{i2}) can be equal to zero. Then its characteristic formal power series is given by

χ_{S}(X, Y) = ∑_{i=1}^{ℓ} X^{α_{i}}Y^{β_{i}} ∏_{j=1}^{v_{i}} \frac{1}{1 − X^{n_{ij}}Y^{t_{ij}}} , with 0 ≤ v_{i} ≤ 2.

Let

F (X, Y) = ∑_{i=1}^{ℓ} X^{α_{i}}Y^{β_{i}} ∏_{j=1}^{v_{i}} \frac{1}{1 − X^{n_{ij}}Y^{t_{ij}}} , with 0 ≤ v_{i} ≤ 2

= ∑_{i=1}^{ℓ} G_{i}(X, Y),

where the G_{i}(X, Y) have disjoint supports and for each 1 ≤ i ≤ ℓ the vectors (n_{ij}, t_{ij}) are linearly independent. Then F (X, Y) = χ_{S}(X, Y) for the semilinear set

S = ⋃_{i=1}^{ℓ}((α_{i}, β_{i}) + {(n_{i1}, t_{i1}), (n_{i2}, t_{i2})}^{∗}) ⊂ ℕ^{2}. □

Lemma 2. Let R be a finite, commutative ring and let w ≥ 1 be an integer. Then

F (X, Y) = ∏_{i=1}^{w} \frac{1}{(1 − X^{α_{i}}Y^{β_{i}})} ∈ R(X, Y)

is definable in ⟨ℕ, +⟩.

Proof. By Lemma 1, G_{i}(X, Y) = \frac{1}{1−X^{α_{i}}Y^{β_{i}}} is k–automatic for all k ≥ 2. As products of k–automatic rational maps are again k–automatic the assertion follows. □

Lemma 3. Let R be a finite, commutative ring. A sequence s : ℕ^{2} → R is definable in ⟨ℕ, +⟩ if and only if there exists a rational function F (X, Y) ∈ R(X, Y) of the form

F (X, Y) = ∑_{i=1}^{ℓ} X^{α_{i}}Y^{β_{i}} ∏_{j=1}^{w_{i}} \frac{1}{1 − X^{n_{ij}}Y^{t_{ij}}} ,

which defines the sequence.

Proof. Let s : ℕ^{2} → R be definable in ⟨ℕ, +⟩ then for each r ∈ R the set M_{r} = s^{−1}(r) is definable in ⟨ℕ, +⟩. Let χ_{M_{r}}(X, Y) denote the characteristic formal power series of M_{r}. Then

F (X, Y) = ∑_{r∈R} rχ_{M_{r}}(X, Y)

defines the sequence and, by Lemma 1, F (X, Y) is of the required form.

Let

F (X, Y) = ∑_{i=1}^{ℓ} X^{α_{i}}Y^{β_{i}} ∏_{j=1}^{w_{i}} \frac{1}{1 − X^{n_{ij}}Y^{t_{ij}}} .

By Lemma 2 each term ∏_{j=1}^{w_{i}} \frac{X^{α_{i}}Y^{β_{i}}}{1−X^{n_{ij}} Y^{t_{ij}}} is k–automatic for all k ≥ 2. Since finite sums of k–automatic sequences are k–automatic the assertion follows. □

It is obvious that Lemma 3 is also true if F (X, Y) can be written as

F (X, Y) = ∑_{i=1}^{ℓ} τ_{i}X^{α_{i}}Y^{β_{i}} ∏_{j=1}^{w_{i}} \frac{1}{1 − ρ_{ij}X^{n_{ij}}Y^{t_{ij}}} .

The following theorem gives a characterization of those rational functions F (X, Y) with coefficients in a finite ring which are definable in ⟨ℕ, +⟩.

Theorem 1. Let R be a finite, commutative ring. A rational function F (X, Y) = \frac{P (X,Y)}{Q(X,Y)} with P (X, Y), Q(X, Y) ∈ R[X, Y], Q(0, 0) ∈ R^{∗} and P (X, Y) ≢ 0 is definable in ⟨ℕ, +⟩ if and only if Q(X, Y) has the monomial factor property (over R).

Proof. Let Q(X, Y) have the monomial factor property, i.e., there exists a polynomial S(X, Y) ∈ R[X, Y] such that S(X, Y) · Q(X, Y) = ∏_{i=1}^{N}(1 − δ_{i}(X, Y)), where δ_{i} ∈ R(X, Y) are finitely many monomials. By Lemma 2,

F (X, Y) = \frac{P (X, Y) · S(X, Y)}{Q(X, Y) · S(X, Y)} = ∏_{i=1}^{N} \frac{P (X, Y) · S(X, Y)}{1 − δ_{i}(X, Y)}

is definable in ⟨ℕ, +⟩.

Let F (X, Y) = \frac{P (X,Y)}{Q(X,Y)} be definable in ⟨ℕ, +⟩. Then F (X, Y) is the formal power series of a sequence which is definable in ⟨ℕ, +⟩. By Lemma 3, F (X, Y) is of the form F (X, Y) = ∑_{i=1}^{ℓ} X^{α_{i}}Y^{β_{i}} ∏_{j=1}^{w_{i}} \frac{1}{1−X^{n_{ij}} Y^{t_{ij}}}. □

3. Rational functions with coefficients in the integers modulo m

In this section, we restrict the study of rational functions with coefficients in a finite commutative ring to the case R = ℤ/(m) = ℤ/mℤ. The theorem of the previous section together with the following lemma and the theorem of Cobham and Semenov provides a tool to generalize the results about the automaticity of the Pascal triangle, [3], which is defined by the rational function F (X, Y) = \frac{1}{1−Y (1+X)}, and more generally about the automaticity of orbits of linear cellular automata [2]. Let F (X, Y) ∈ ℤ(X, Y) be a rational function. If p is a prime number such that F (X, Y) mod p is a rational function with coefficients in ℤ/(p), then, due to a theorem in [7], F (X, Y) mod p is p–automatic, or definable in ⟨ℕ, +, V_{p}⟩. Moreover F (X, Y) mod p^{α} is p–automatic for all α ∈ ℕ.

For the definability in ⟨ℕ, +⟩ we obtain a similar result.

Lemma 4. Let p be a prime number and let F (X, Y) = P (X, Y)/Q(X, Y) with polynomials P (X, Y), Q(X, Y) ∈ ℤ[X, Y]. Then F (X, Y) mod p is definable in ⟨ℕ, +⟩ if and only if F (X, Y) mod p^{α}, α ≥ 1, is definable in ⟨ℕ, +⟩.

Proof. Let α ≥ 2 and suppose that F (X, Y) = \frac{P (X,Y)}{Q(X,Y)} mod p^{α} is definable in ⟨ℕ, +⟩. Then, by Theorem 1, we may assume that there exists a polynomial S(X, Y) ∈ ℤ[X, Y] such that S(X, Y)Q(X, Y) mod p^{α} is of the form

Q(X, Y) mod p^{α} = ∏_{i=1}^{ℓ}(1 − δ_{i}(X, Y)) mod p^{α},

which yields that Q(X, Y) mod p = ∏_{i=1}^{ℓ}(1−δ_{i}(X, Y)) mod p. By Theorem 1, F (X, Y) mod p is definable in ⟨ℕ, +⟩.

Now suppose that F (X, Y) mod p is definable in ⟨ℕ, +⟩. Due to Theorem 1, we may assume that

Q(X, Y) mod p = ∏(1 − δ_{i}(X, Y)) mod p.

Therefore there exists a polynomial Q_{1}(X, Y) ∈ ℤ such that

Q(X, Y) mod p^{2} = ∏(1 − δ_{i}(X, Y)) + pQ_{1}(X, Y) mod p^{2}.

That gives

Q(X, Y)^{p} mod p^{2} = (∏(1 − δ_{i}(X, Y)))^{p} mod p^{2},

in other words, Q(X, Y)^{p} mod p^{2} can be written as a product of the form ∏(1 − δ_{j}(X, Y)). Theorem 1 implies that F (X, Y) mod p^{2} is definable in ⟨ℕ, +⟩. The proof for the case p^{α} with α ≥ 3 proceeds in a similar fashion. □

The above lemma together with the definition of M_{m}(F (X, Y)) allows a characterization of automaticity properties of rational maps.

Theorem 2. (Automaticity of rational functions)

Let F (X, Y) ∈ ℤ(X, Y) be a rational function and m ∈ ℕ, m ≥ 2. Then the following holds: i) If χ_{m}(F) ≥ 2 , then F (X, Y) modulo m is not k–automatic for any k ≥ 2. ii) If χ_{m}(F) = 1 , then F (X, Y) modulo m is p^{α}–automatic, where p ∈ M_{m}(F) and

α ∈ ℕ \ {0} and not k–automatic for k ≠ p^{α}. iii) If χ_{m}(F) = 0, then F (X, Y) modulo m is definable in ⟨ℕ, +⟩, i.e., k–automatic for all

k ≥ 2.

Proof.

i) Assume that F (X, Y) modulo m is k–automatic. Then the projections π_{p}(F) = F (X, Y) modulo p and π_{q}(F) = F (X, Y) modulo q, are k–automatic as well. Let p ∈ M_{m}(F (X, Y)). Then F (X, Y) mod p is p–automatic. Since p ∈ M_{m}(F (X, Y)) and by Theorem 1, F (X, Y) modulo p is not definable in ⟨ℕ, +⟩ and by the above it is k–automatic. The same holds for q ∈ M_{m}(F (X, Y)), q ≠ p; but this is a contradiction to the theorem of Cobham–Semenov.

ii) Let p ∈ M_{m}(F), then F (X, Y) modulo p is p^{α}–automatic and not k–automatic for k ≢ p^{α}. If we assume that F (X, Y) modulo m is k–automatic and k not of the form p^{α}, then, by projection, F (X, Y) modulo p would be k–automatic, which is a contradiction.

iii) Let m = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{w}^{α_{w}} be the prime number decomposition of m. For each i ∈ {1, …, w}, there exists a polynomial S_{i}(X, Y) ∈ ℤ/(p_{i})[X, Y] such that

S_{i}(X, Y)Q(X, Y) = ∏(1 − δ_{j,i}(X, Y)) mod p_{i},

where δ_{j,i}(X, Y) are monomials.

Then by Theorem 1, F (X, Y) modulo p_{i} is definable in ⟨ℕ, +⟩. By Lemma 4, F (X, Y) modulo p_{i}^{α_{i}} is definable in ⟨ℕ, +⟩ for all i = 1, …, w. Let s_{p_{i}} : ℕ^{2} → ℤ/(p_{i}^{α_{i}}) denote the associated double sequences. As s_{p_{i}} is definable in ⟨ℕ, +⟩ each of the sets M_{a_{i}}^{p_{i}} := s_{p_{i}}^{−1}(a), a_{i} ∈ ℤ/(p_{i}^{α_{i}}) is semilinear. By the Chinese Remainder Theorem, for all b ∈ ℤ/(m) there exist unique a_{i} ∈ ℤ/(p_{i}^{α_{i}}) such that c ≡ a_{i} mod p_{i}^{α_{i}} for all i = 1, …, w. We thus obtain

M_{c}^{m} = ⋂_{i=1}^{w} M_{a_{i}}^{p_{i}}, ,

i.e., M_{c}^{m} is the intersection of finitely many semilinear sets and therefore semilinear. In other words F (X, Y) modulo m is k–automatic for all k. □

References

[1] Allouche, J.-P. Automates finis en théorie des nombres. Expo. Math. 5 (1987), 239–266.

[2] Allouche, J.-P.; v. Haeseler, F.; Peitgen, H.-O.; Petersen, A.; Skordev, G.: Automaticity of double sequences generated by 1-dimensional linear cellular automata. Theoretical Computer Science (to appear).

[3] Allouche, J.-P.; v. Haeseler, F.; Peitgen, H.-O.; Skordev, G.: Linear cellular automata, finite automata and Pascal’s triangle. Discrete Appl. Math. 66 (1996), 1–22.

[4] Bruyère, V.: Entiers et automates finis. U. E. Mons, mémoire de licence (1984-85).

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

[6] Büchi, J. R.: Weak second–order arithmetic and finite automata. Zeitschr. f. Math. Logik Grundlagen Math. 6 (1960), 66–92.

[7] Christol, G.; Kamae, T.; Mendès France, M.; Rauzy, G.: Suites algébriques, automates et substitutions. Bull. Soc. Math. France 108 (1980), 401–419.

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

[9] Eilenberg, S.; Schützenberger, M. P.: Rational Sets in Commutative Monoids. J. of Algebra 13 (1969), 173–191.

[10] Ginsburg, S.; Spanier, E. H.:Semigroups, Presburger formulas and languages. Pacific J. Math. 16 (1966), 285–296.

[11] Haas, J.-P.: Theorie und Anwendung semilinearer Vektormengen. FB Informatik, Univ. Hamburg, Bericht 130, 1987.

[12] Korec, I.: Pascal triangles modulo n and modular trellises. Computers and Artificial Intelligence 9 (1990), 105–113.

[13] MacNaughton, R.: Review of [6]. J. Symb. Logic 28 (1963), 100–102.

[14] Salon, O.: Suites automatiques à multi–indices. Séminaire de Théorie des Nombres de Bordeaux, Exposé no. 4 (1986–1987), followed by an Appendix by J. Shallit, 4-29A–4-36A.

[15] Salon, O.: Proprietes arithmétiques des automates multidimensionneles. Thèse, Université Bordeaux I, (1989).

[16] Semenov, A. L.: On certain extensions of the arithmetic of addition of natural numbers. Math. USSR, Izvestiya 15 (1980), 401–418.

Received December 19, 1996