A CRITERION FOR NON-AUTOMATICITY OF SEQUENCES

Jan-Christoph Schlage-Puchta

Mathematisches Institut Eckerstr. 1 79111 Freiburg Germany

                   jcp@arcade.mathematik.uni-freiburg.de

Abstract

We give a criterion for a sequence (a_{n})_{n≥1} to be non-automatic, i.e., for when there does not exist a finite automaton generating this sequence. As application we generalize a result of Yazdani on the non-automaticity of multiplicative sequences.

1. Introduction.

A finite automaton consists of a finite set S of states with a specified starting state s_{0}, an input alphabet A, an output alphabet B, and two functions f : A × S → S, g : S → B. Given a word w over A, the output of the automaton is determined as follows: At first, the automaton is in s_{0}. Then the first letter a of w is read, and the new state of the automaton is changed to s_{1} = f(a, s_{0}). Then the next letter b of w is read, and the state of the automaton is changed to s_{2} = f(b, s_{1}). This is repeated untill all letters of w are read, and the procedure terminates. If the automaton ends in the state s, it returns the value g(s).

Fix some integer q ≥ 2. In our context, the alphabet A consists of the integers 0, 1, …, q− 1, and B consists of integers or elements in some fixed finite fields. Every integer n ≥ 1 can be written in the form n = ∑ e_{i}(n)q^{i} with e_{i}(n) ∈ {0, 1, …, q − 1}, hence n can be viewed as word over A, and the automaton can be applied to this word. More precisely, write n = ∑_{i=0}^{k} e_{i}q^{i} with e_{i} ∈ {0, 1, …, q − 1} and e_{k} ≠ 0, and identify the integer n with the string e_{k}e_{k−1} … e_{1}e_{0}. In this way, every automaton defines a sequence (a_{n})_{n≥0}. An automaton with A = {0, 1, …, q − 1} is called a q-automaton, and an arbitrary sequence is called q-automatic, if there exists a q-automaton which generates this sequence. More generally, a sequence is called automatic, if it is k-automatic for some integer k ≥ 2.

Apart from intrinsic interest, the question whether a given sequence is automatic is of interest because of its number theoretical consequences. In fact, automaticity and algebraicity are linked via the following result of G. Christol, T. Kamae, M. Mendès France and G. Rauzy [2].

Theorem 1. Let p be a prime number, (a_{n})_{n≥1} be a sequence of elements in 𝔽_{p}. Then the series ∑_{n=1}^{∞} a_{n}x^{n} is algebraic over 𝔽_{p}(x) if and only if the sequence (a_{n}) is p-automatic.

Hence, to prove the transcendence of a power series, we need only to show that a certain sequence is not automatic. This can for example be accomplished by the following theorem of A. Cobham [3].

Theorem 2. Let (a_{n})_{n≥1} be an automatic seqence over an alphabet B. Assume that for some a ∈ B the limit δ_{a} = lim_{x→∞} \frac{1}{x}|\{n ≤ x : a_{n} = a\}| exists. Then δ_{a} is rational.

In [1], J.-P. Allouche used this to prove the following result.

Corollary 1. The power series f(x) = ∑_{n≥1}(μ(n) mod p)x^{n} is transcendental over 𝔽_{p}(x) for all primes p.

Here, μ(n) denotes the Möbius-function, i.e., the multiplicative function satisfying μ(p) = −1, μ(p^{k}) = 0 for all primes p and integers k ≥ 2.

Proof. Since μ(n) = 0 if and only if n is divisible by some square a^{2}, a ≥ 2, we see that in the notation of Theorem 2,

δ_{0} = lim_{x→∞} \frac{1}{x}|\{n ≤ x : ∃a ≥ 2, a^{2}|n\} = 1 − ∏_{p} (1 − \frac{1}{p^{2}} ) = 1 − \frac{π^{2}}{6} ,

hence, the limit exists and is irrational. So by Theorem 2, the sequence (μ(n) (mod p))_{n≥1} is not automatic. □

Albeit short and ingenious, the proof has the disadvantage that it is difficult to apply to other situations for two reasons. First, it requires the evaluation of ∏_{p} (1 − \frac{1}{p^{2}} ) and a proof that the result is irrational. This is equivalent to Euler’s evaluation of ζ(2) and the fact that π^{2} is irrational. In our case, these are well known, yet non-trivial facts. However, in other cases there might be no known formula for δ_{a}. The second, more fundamental problem is that in many cases δ_{a} = \frac{1}{|B|} for all a, so Theorem 2 cannot be applied.

The aim of this note is to give another proof of Corollary 1. In fact, we have the following more general result.

Theorem 3. Let (a_{n})_{n≥1} be an automatic sequence. Assume that for some letter a and for every integer k there exists an integer n such that a_{n} = a_{n+1} = ⋯ = a_{n+k} = a. Then there is a constant c > 0 such that for an infinite number of integers x we have a_{n} = a for all n ∈ [x, (1 + c)x].

Other criteria involving strings of repeated values can be found in [4].

2. Main results

Before proving our theorem, we first give some corollaries.

Corollary 2. Let (q_{i})_{i≥1} be a sequence of positive integers such that ∑_{i} \frac{1}{q_{i}} < ∞. Assume that for all k ≥ 1, there are indices i_{1}, …, i_{k} such that (q_{i_{l}}, q_{i_{m}}) = 1 for 1 ≤ l < m ≤ k. For all integers n ≥ 1, set a_{n} = 0, if there exists some i such that q_{i}|n, and a_{n} = 1 otherwise. Then the sequence (a_{n})_{n≥1} is not automatic.

Proof. Assume that the sequence (a_{n})_{n≥1} is automatic, and let k be a given integer. Choose indices i_{1}, …, i_{k} as in the Corollary. By the Chinese remainder theorem, there is some integer n solving n + l ≡ 0 (mod q_{i_{l}}), that is, a_{n+l} = 0 for 1 ≤ l ≤ k. Hence, the assumptions of Theorem 3 are satisfied, and we deduce that there exist some c > 0 and arbitrarily large integers x such that a_{n} = 0 for all n ∈ [x, (1 + c)x]. On the other hand, we can bound from below the number of integers n ∈ [x, (1 + c)x] such that a_{n} = 0 in the following way. Let ϵ > 0 be given, and let K be some constant with ∑_{i>K} \frac{1}{q_{i}} < ϵ. Let L be the least common multiple of q_{1}, …, q_{K}. Then the set of all integers n such that q_{i} |̸n for all i ≤ K is periodic with period L, and has density d_{K} ≥ ∏_{i≤K} (1 − \frac{1}{q_{i}} ), with equality if and only if the q_{i} are pairwise coprime. Note that

d_{K} > ∏_{i=1}^{∞} (1 − \frac{1}{q_{i}} ) > 0,

that is, d_{K} can be bounded away from 0 independently of K. Now for x → ∞, we have

|{n ∈ [x, (1 + c)x] : a_{n} = 1}| ≥ |{n ∈ [x, (1 + c)x] : ∀i ≤ K : q_{i} |̸n}|  (1)

− ∑_{i>K} |{n ∈ [x, (1 + c)x] : q_{i}|n}|

≥ d_{K}cx − L − ϵcx − |{i : q_{i} ≤ (1 + c)x}|
≥ (d_{K} − ϵ)cx + o(x),

since |\{i : q_{i} ≤ (1 + c)x\}| = o(x), for otherwise the series ∑ \frac{1}{q_{i}} would diverge. In fact, if

lim sup_{x→∞} \frac{|\{i : q_{i} < x\}|}{x} > 0,

there exists some constant k > 0 such that

lim sup_{n→∞} \frac{|\{i : 2^{n} ≤ q_{i} < 2^{n+1}\}|}{2^{n+1}} > k,

thus, ∑_{i} \frac{1}{q_{i}} = ∞. By Theorem 3 we would find arbitrarily large integers x such that the left-hand side of (1) is zero, thus we arrive at a contradiction. So the sequence (a_{n})_{n≥1} is not automatic. □

Choosing q_{i} = p_{i}^{2}, with p_{i} the i-th prime number, we find that the sequence (μ(n)^{2} (mod p))_{n≥1} is not automatic, which is slightly stronger then Corollary 1.

Out next result deals with the automaticity of multiplicative functions.

Corollary 3. Let f : ℕ → ℤ be a multiplicative function. Let q ≥ 2 be an integer. Assume that the following conditions hold.

(1) There exist infinitely many primes p such that there exists some h_{p} ≥ 1 with q|f(p^{h_{p}}).

(2) If b_{n} denotes the n-th integer with f(b_{n}) ≢ 0 (mod q), we have \frac{b_{n+1}}{b_{n}} → 1. Then the sequence (f(n) (mod q))_{n≥1} is not automatic.

Proof. As in the proof of Corollary 2, the first condition implies that for every k there exist some n with f(n) ≡ f(n + 1) ≡ ⋯ ≡ f(n + k) ≡ 0 (mod q), while the second condition means that for every c > 0 there are only finitely many integers x such that f(n) ≡ 0 (mod q) holds for all n ∈ [x, (1 + c)x]. Together with Theorem 3, we obtain the desired conclusion. □

This result generalizes a theorem of S. Yazdani [5, Theorem 2]. In fact, the conditions on f are relaxed in two aspects: First, the integers h_{p} are allowed to depend on p. More important, the lower bound for the density of the set of integers n satisfying q ∤ f(n) in the second condition of Corollary 3 is smaller then in [5, Theorem 2]. The latter theorem requires q ∤ f(p) for all primes in a residue class, which by the prime number theorem for arithmetic progressions implies condition (2) of Corollary 3.

Now we return to the proof of Theorem 3.

Proof of Theorem 3. Assume that (a_{n})_{n≥1} is a sequence satisfying the conditions of Theorem 3, and it is generated by a q-automaton. For every integer l, let n be an integer such that a_{n+i} = a for all i ≤ q^{l}. We may assume that n is divisible by q^{l}. Indeed, by hypothesis, for all integers l ≥ 1 there exists an integer m such that a_{m+i} = a for 0 ≤ i < 2q^{l}. Let n_{l} be the least integer such that n ≥ m and q^{l}|n. Then n < m + q^{l}, and therefore a_{n+i} = a for 0 ≤ i < q^{l}. Let s be the state of the automaton reached when reading all digits of n except the last l digits. Then the definition of s implies that all states accessible from s within precisely l steps return a. To every state s define a set N_{s} ⊆ ℕ such that l ∈ N_{s} if and only if all states accessible from s within precisely l steps return a. Our argument above shows that for every l ∈ ℕ there is some state s accessible from the starting state such that l ∈ N_{s}. Hence, since there are only finitely many states, there exists some s_{0} such that s_{0} is accessible from the starting state, and there are infinitely many l such that all states accessible from s_{0} in precisely l steps return a. Let d be some integer such that when reading d, the automaton stops in the state s_{0}. Then we claim that for all l ∈ N_{s_{0}} and all n ∈ [dq^{l}, dq^{l} + q^{l} − 1], we have a_{n} = a. In fact, after reading d, the automaton is in state s_{0}, then, after reading l arbitrary digits, it is in some state returning a. Hence, our theorem follows with c = (1 − q^{−1})d^{−1}. □

References

[1] J.-P. Allouche, Note on the transcendence of a generating function, in New Trends in Probability and Statistics, Vol. 4 (Palanga, 1996), VSP, Utrecht, 1997, 461–465.

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

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

[4] J.-Y. Yao, Critères de non-automaticité et leurs applications, Acta Arith. 80 (1997), 237–248.

[5] S. Yazdani, Multiplicative functions and k-automatic sequences, J. Théor. Nombres Bordeaux 13 (2001), 651–658.

2000 Mathematics Subject Classification: Primary 11B85. Keywords: Automatic sequence, finite automaton.

A CRITERION FOR NON-AUTOMATICITY OF SEQUENCES 5

Received February 6, 2003; revised version received November 10 2003. Published in Journal of Integer Sequences November 16 2003. Return to Journal of Integer Sequences home page.