# 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 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.

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 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, 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.

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 the following from Theorem 2 of this post.

Lemma 1. If $p$ is a prime factor of $a_k$ such that $p\nmid v$, then for all $n\ge 0$,

$p^r\parallel a_k\implies p^{n+r}\parallel a_{kp^n}$.

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)}\implies 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$

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 the following.

Theorem 1. (Lifting the Exponent) Let $\alpha,\beta\in\mathbb Z$ and put

$a_n=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}.$

Then for an odd prime $p$ coprime to $\alpha,\beta$, and for $r\ge 1$,

$p^r\parallel a_k\implies p^{n+r}\parallel a_{kp^n}$

for all integers $n\ge 0$.

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

We generalize Theorem 1 to general rings of algebraic integers.

Theorem 2. Let $K$ be 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=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}$

is an integer for all integers $n\ge 0$. Then

$p^r\parallel a_k\implies p^{n+r}\parallel a_{kp^n}$

for all integers $r\ge 1$ and $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+\cdots}{\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)}\implies 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. By hypothesis, $k(p^{n+r-1})=kp^{n-1}$ so $p^{n+r-1}\mid p^{n+r}\mid F_j\implies kp^{n-1}\mid j. Then $1\le \frac{j}{kp^{n-1}}, 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$