Tag Archives: linear recurrence

Finite automata 3: Non-automatic sets

The key ingredients in our proof of the special case of Cobham’s theorem were the pumping lemma and the following fact:

(*)\qquad [ab^{n+1}c]_q-q^{|b|}[ab^nc]_q=\text{constant}

We can formally put them together into the following lemma:

Lemma 1. If S\subseteq\mathbb N is an infinite automatic set, then there exist distinct s_0,s_1,\ldots\in S and integers A>1 and B such that s_{n+1}=As_n+B for all n.

Proof. Say S is q-automatic. By the pumping lemma we can take s_n=[ab^nc]_q for some a,b,c\in\Sigma_q^* with |b|\ge 1. Note that these are distinct as we don’t allow leading zeros. The conclusion now follows from (*). \square

Lemma 1 can be a powerful tool in proving that sets are not automatic, because it transforms a question from automata theory into the language of simple unary recurrences. For instance, we can use it to easily prove the following theorem of Minsky and Papert:

Theorem 1 (Minsky and Papert, 1966). The set of prime numbers is not automatic.

We are actually able to prove the following stronger result:

Theorem 2 (Schützenberger, 1968). An infinite set of prime numbers is not automatic.

Proof. Assume the contrary. Then by lemma 1 there exist distinct prime numbers p_1,p_2,\dots and integers A>1 and B such that p_{n+1}=Ap_n+B for all n\ge 1. Then

p_{n+j}\equiv B(A^{j-1}+\dots +A+1)\pmod{p_n}

for all j,n\ge 1. Now pick n large enough so that p_n\nmid A(A-1). Then

\displaystyle p_{n+p_n-1}\equiv\frac{B(A^{p_n-1}-1)}{A-1}\equiv 0\pmod{p_n}

by Fermat’s little theorem, a contradiction. \square

Note that lemma 1 implies that any set whose elements increase very rapidly cannot be automatic. To put it formally:

Theorem 3. Let f:\mathbb N\to\mathbb N such that f(n+1)/f(n)\to\infty as n\to\infty. Then the set \{f(1),f(2),f(3),\dots\} is not automatic.

Proof. Assume the contrary. Then there exist integers 0<s_0<s_1<\cdots such that f(s_{n+1})=Af(s_n)+B for all n, where A>1 and B are fixed integers. Then f(s_{n+1})/f(s_n)\to A as n\to\infty, a contradiction. \square

Corollary 1. The set \{1!,2!,3!,\dots\} of factorials is not automatic.

Proof. Take f(n)=n! in theorem 3. \square

Corollary 2. The set \{2^{2^0}+1,2^{2^1}+1,2^{2^2}+1,\dots\} of Fermat numbers is not automatic.

Proof. Take f(n)=2^{2^{n-1}}+1 in theorem 3. \square

It is possible to use lemma 1 in other ways to show that sets are not automatic. For example:

Theorem 4. Let f:\mathbb N\to\mathbb N such that f(n+1)/f(n)\to\alpha as n\to\infty, where \alpha is a real number such that \alpha^m\not\in\mathbb N for any m\in\mathbb N. Then the set \{f(1),f(2),f(3),\dots\} is not automatic.

Proof. Assume the contrary. Then by lemma 1 there exist distinct positive integers s_0,s_1,\dots such that f(s_{n+1})=Af(s_n)+B for all n, where A>1 and B are fixed integers. Now

\displaystyle\lim_{n\to\infty}\frac{f(n+m)}{f(n)}=\alpha^{m}

for all m\in\mathbb N. Therefore, as f(s_{n+1})/f(s_n)\to A, it follows that A=\alpha^m for some m\in\mathbb N. But this is impossible, as \alpha^m\not\in\mathbb N for any m\in\mathbb N. \square

Corollary 3. The set \{0,1,1,2,3,5,\dots\} of Fibonacci numbers is not automatic.

Proof. Let F_n denote the n-th Fibonacci number. Note that F_{n+1}/F_n\to\varphi=(1+\sqrt 5)/2 as n\to\infty, and that \varphi^m=F_m\varphi+F_{m-1}\not\in\mathbb N for all m\in\mathbb N. So the result follows by theorem 4. \square

In the exact same manner we also get:

Corollary4. The set \{2,1,3,4,7,11,\dots\} of Lucas numbers is not automatic.

Advertisements

Leave a comment

Filed under Analysis, Combinatorics, Number theory

Finite automata 1: Automatic sets

In one of my recent courses I had to learn about finite automata theory. The main purpose was to understand a generalisation of the celebrated Skolem-Mahler-Lech theorem in positive characteristic. Let \mathbb N_0 denote the set of non-negative integers and K be a field. For a linear recurrence f:\mathbb N_0\to K, define its zero set to be \{n\in\mathbb N_0 : f(n)=0\}. Then the Skolem-Mahler-Lech theorem states the following:

Theorem (Skolem-Mahler-Lech, 1953). The zero set of a linear recurrence f:\mathbb N_0\to\mathbb K, where K is a field of characteristic 0, is a finite union of arithmetic progressions along with a finite set.

Derksen in his 2005 paper was able to provide the correct analogue of this result in positive characteristic for the first time:

Theorem (Derksen, 2007). The zero set of a linear recurrence f:\mathbb N_0\to K, where K is a field of characteristic p>0, is a p-automatic set.

To understand this theorem we need to know about finite automata. In this and the next few posts I want to write about some interesting elementary results about automatic sets. Since my knowledge of computer science is epsilon(!), I will mostly touch on some very basic mathematical aspects.

A deterministic finite-state automaton (DFA) is a directed multigraph \Gamma satisfying certain properties. Firstly, its vertex-set Q (which we call the set of states) contains a special vertex (or state) q_0, called the initial state. We also have a finite non-empty set \Sigma of symbols. Each edge of \Gamma is labelled with a symbol from \Sigma. As a result, we have a transition function \delta:Q\times\Sigma\to Q such that if an edge from q_1 to q_2 is labelled with the symbol a\in\Sigma, then we write \delta(q_1,a)=q_2. Finally, we have a set F\subseteq Q (possibly empty) called the set of accepting or final states.

So \Gamma can be formally written as a quintuple (\Sigma,Q,q_0,\delta,F).

Let \Sigma^* be the free monoid on \Sigma. We can extend the transition function \delta to a map \delta:Q\times\Sigma^*\to Q by setting \delta(q_0,wa)=\delta(\delta(q_0,a),w) for all a\in\Sigma and w\in\Sigma^*. Thus, to \Gamma we can associate a language

\mathcal L_\Gamma:=\{w\in\Sigma^*:\delta(q_0,w)\in F\}\subseteq\Sigma^*.

We call such a language produced from a DFA a regular language. If w\in\mathcal L_\Gamma for some w\in\Sigma^*, we say that w is accepted by \Gamma.

Let \mathbb N denote the set of the positive integers, and let k>1 be an integer. Define \Sigma_k:=\{0,1,\dots,k-1\}. A subset S\subset\mathbb N is said to be k-automatic if there exists a DFA \Gamma=(\Sigma_k,Q,q_0,\delta,F) such that S is precisely the set of those j\in\mathbb N whose base-k representation, when regarded as a string in \Sigma^*, is accepted by \Gamma. If S\subseteq\mathbb N is k-automatic for some k>1, we say S is an automatic set.

For w=w_nw_{n-1}\cdots w_0\in\Sigma_k^* with each w_i\in\Sigma_k we define

[w]_k:=w_nk^n+w_{n-1}k^{n-1}+\cdots+w_0.

In this case we also define |w|:=n+1 to be the length of w.

So S\subseteq\mathbb N is k-automatic precisely when S=\{[w]_k:w\in\mathcal L_\Gamma\} for some DFA \Gamma.

Note that we can set \delta(q,0) to be in Q\backslash F for every q\in Q (if F=Q, just create a new state). Thus we may without loss of generality assume that all our DFAs only accept words without leading zeros.

A basic result about regular languages is the pumping lemma:

Lemma (Pumping lemma). If \mathcal L is an infinite regular language, then there exist words a,b,c with |b|\ge 1 such that ab^nc\in\mathcal L for all n\ge 0.

Proof. Since \mathcal L is infinite, there are words of arbitrarily large length in \mathcal L. Let w=w_nw_{n-1}\cdots w_0\in\mathcal L be a word of sufficient length. Then there exist 0\le i<j\le n such that w_i\cdots w_0=w_j\cdots w_0\in\mathcal L. Taking a=w_n\cdots w_j, b=w_{j-1}\cdots w_i, c=w_{i-1}\cdots w_0 shows that ab^nc\in\mathcal L for all n\ge 0. Moreover, since i<j, it follows that |b|\ge 1. \square

In the following posts we are going to use the pumping lemma, together with other machinery, to derive some interesting results on the automaticity of certain sets.

Leave a comment

Filed under Algebra, Combinatorics, Number theory

Some divisibility properties of Fibonacci-like sequences

Here we shall aim to generalise the corollary from the last post, and on the way generalise some other important properties of the Fibonacci sequence, to general Fibonacci-like sequences.

Consider a sequence \{a_n\} with a_0=0, a_1=1 and a_n=ua_{n-1}+va_{n-2} for n\ge 2, where u,v\in\mathbb Z such that u^2+4v\neq 0. Let \alpha,\beta be the roots of x^2-ux-v=0. Then

\displaystyle a_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}.

Let p be an odd prime. Suppose (\alpha) and (p) have a common factor. By Dedekind’s factorisation criterion, (p) is either prime or it factors into two (not necessarily distinct) prime ideals each with norm p. In the first case, we must have (p)\mid (\alpha) i.e. p^2\mid v, taking ideal norms. In the second case, if one of the prime factors of (p) divides (\alpha), then (again taking norms) p must divide v.

So we take (p,v)=1 which ensures that (\alpha) and (p) are coprime. Thus we deduce from the general exponent lifting result,

Lemma 1. If p is a prime factor of a_k such that p\nmid v, then p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0.

Next, recalling the proof of the corollary from last time, we seem to require the condition (a_m,a_n)=a_{(m,n)}.

Lemma 2. If (u,v)=1, then (a_m,a_n)=a_{(m,n)} for all m,n.

Proof. First, it is clear that (a_m,a_n)/a_{(m,n)}\in\mathcal O_K, where K=\mathbb Q(\alpha), and that (a_m,a_n)/a_{(m,n)}\in\mathbb Q. Thus (a_m,a_n)/a_{(m,n)}\in\mathbb Z.

Let p be a prime factor of (a_m,a_n). Then for m\ge n,

\displaystyle p\mid\frac{\alpha^m-\beta^m}{\alpha-\beta}-\frac{\alpha^{m-n}(\alpha^n-\beta^n)}{\alpha-\beta}=\frac{\beta^n(\alpha^{m-n}-\beta^{m-n})}{\alpha-\beta}=\beta^na_{m-n}.

If (p) and (\beta^n) share a common factor, then (taking ideal norms,) p\mid v. Hence a_n\equiv ua_{n-1}\equiv u^{n-1}\equiv 0\pmod p, a contradiction as (u,p)=1.

Hence (a_m,a_n)\mid a_{m-n} and by the Euclidean algorithm we get (a_m,a_n)\mid a_{(m,n)}. Thus (a_m,a_n)=a_{(m,n)}, as desired. \square

Now we define k(n) to be the least k such that n\mid a_k, and we are ready for our generalisation!

Theorem. Let \{a_n\} be given by a_0=0,a_1=1 and a_n=ua_{n-1}+va_{n-2} for n\ge 2, where u,v are coprime integers such that u^2+4v\neq 0. Then for an odd prime p for which k(p) exists,

p^r\parallel a_{k(p)}\Rightarrow k(p^n)=\begin{cases}p^{n-r}k(p)&\text{ if }n\ge r,\\ k(p)&\text{ if }n\le r.\end{cases}

Proof. If p\mid v, then p\mid a_{k(p)}-va_{k(p)-2}=ua_{k(p)-1}. By definition of k(p), p\nmid a_{k(p)-1}. Hence p\mid u, which is impossible as (u,v)=1. Thus p\nmid v and the proof of the corollary in the previous post now applies. \square

Leave a comment

Filed under Algebra, Number theory

A generalisation of ‘lifting the exponent’

Lifting the exponent is a popular result in elementary number theory. It basically says that if \alpha,\beta\in\mathbb Z and a_n=(\alpha^n-\beta^n)/(\alpha-\beta), then for an odd prime p coprime to \alpha,\beta and for r\ge 1,

Theorem 1. (Lifting the exponent) p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0.

Here, as usual, p^r\parallel x means that p^r\mid x but p^{r+1}\nmid x.

We shall generalise this to general rings of algebraic integers. In the following, K will denote an algebraic number field and \mathcal O_K its ring of integers. Let \alpha,\beta\in\mathcal O_K such that the ideals (\alpha), (\beta) are coprime to (p), and a_n\in\mathbb Z\ \forall n.

Theorem 2. p^r\parallel a_k\Rightarrow p^{n+r}\parallel a_{kp^n}\ \forall n\ge 0.

Proof. We proceed by induction on n. The base case n=0 is clear. Suppose that the assertion holds for n-1. We want to show that p^{n+r}\parallel a_{kp^n}, that is,

\displaystyle p^{n+r}\parallel\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha-\beta}=a_{kp^{n-1}}\cdot\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha^{kp^{n-1}}-\beta^{kp^{n-1}}}

By hypothesis, p^{n+r-1}\parallel a_{kp^{n-1}}. So we need to show that \displaystyle p\parallel\frac{\alpha^{kp^n}-\beta^{kp^n}}{\alpha^{kp^{n-1}}-\beta^{kp^{n-1}}}.

Let c=\alpha^{kp^{n-1}}, d=\beta^{kp^{n-1}}. We want to show that \displaystyle p\parallel\frac{c^p-d^p}{c-d}.

Since p\mid a_k, we have a_k\in (p). Hence \alpha^k-\beta^k=(\alpha-\beta)a_k\in (p), i.e. \alpha^k\equiv\beta^k\pmod p. Hence c\equiv d\pmod p. Let c=d+\mu p for some \mu\in\mathcal O_K. Then

\displaystyle\frac{c^p-d^p}{c-d}=\frac{(d+\mu p)^p-d^p}{\mu p}=\frac{p\cdot d^{p-1}\mu p+\ldots}{\mu p}\equiv pd^{p-1}\pmod{p^2}.

If this is 0, then (p)\mid (d)^{p-1}, which is impossible by unique factorisation as (p) and (d) are coprime. \square

Corollary. Let \{F_n\} be the Fibonacci sequence. Then

p^r\parallel F_{k(p)}\Rightarrow k(p^n)=\begin{cases}p^{n-r}k(p)&\text{ if }n\ge r,\\ k(p)&\text{ if }n\le r.\end{cases}

(Refer to this post for notation.)

Proof. Take \alpha=\varphi=\frac{1+\sqrt 5}{2}, \beta=\bar\varphi=\frac{1-\sqrt 5}{2} (with K=\mathbb Q(\sqrt 5) and \mathcal O_K=\mathbb Z[\varphi]) and let k=k(p). We proceed by induction on n. Suppose p^{n+r}\mid F_j for some j<kp^n. By hypothesis, k(p^{n+r-1})=kp^{n-1} so p^{n+r-1}\mid p^{n+r}\mid F_j\Rightarrow kp^{n-1}\mid j<kp^n. Then 1\le \frac{j}{kp^{n-1}}<p, so \gcd(\frac{j}{kp^{n-1}},p)=1, i.e. \gcd(j,kp^n)=kp^{n-1}. Hence \gcd(F_{kp^n},F_j)=F_{kp^{n-1}} which implies p^{n+r}\mid F_{kp^{n-1}}, a contradiction. \square

2 Comments

Filed under Algebra, Number theory

Fibonacci sequence modulo n: Part 2

See here.

Leave a comment

Filed under Algebra, Number theory