Monthly Archives: October 2014

27/10/2014 · 12:37 am

An Application of Zorn’s Lemma: Transcendence Bases

Zorn’s Lemma is a very useful result when it comes to dealing with an infinite collection of things. In ZFC Set Theory it is equivalent to the Well-Ordering Theorem (every set can be well-ordered) and to the Axiom of Choice (a Cartesian product of non-empty sets is non-empty). I happened to use it a few days ago in proving the existence of transcendence bases, hence this post!

Zorn’s Lemma. If every chain in a poset $P$ has an upper bound in $P$ , then $P$ contains a maximal element.

Let $K/k$ be a field extension. We call a subset $S\subseteq K$ algebraically independent if for any $m\ge 0$ and $s_1,\dots,s_m\in S$ , $p(s_1,\dots,s_m)=0$ implies $p=0$ , where $p\in k[X_1,\dots,X_m]$ is a polynomial. A maximal (with respect to $\subseteq$ ) algebraically independent subset is called a transcendence base.

Theorem. Every field extension has a transcendence base.

Proof. If $K/k$ is algebraic, the transcendence base is the empty set. Suppose that $K/k$ is not algebraic. Let $\mathcal F$ be the family of all algebraically independent subsets $S\subseteq K$ . By Zorn’s lemma, it suffices to show that every chain in $\mathcal F$ has an upper bound. Let $\mathcal C$ be a chain in $\mathcal F$ , and let

$T=\displaystyle\bigcup_{S\in \mathcal C} S$ .

It suffices to show that $T\in\mathcal F$ , since then $T$ would be an upper bound for $\mathcal C$ in $\mathcal F$ .

Let $P(m)$ be the statement:

If $t_1,\dots,t_m\in T$ are distinct, and $p(t_1,\dots, t_m)=0$ for some $p\in k[X_1,\dots,X_m]$ , then $p=0$ .

If $t_1\in T$ , then $t_1\in S$ for some $S\in \mathcal C$ . Since $\mathcal S$ is algebraically independent, $p(t_1)=0$ implies $p=0$ in $k[X_1]$ . Thus $P(1)$ is true.

Suppose $P(m-1)$ is true. Let $t_1,\dots,t_m\in T$ be distinct such that $p(t_1,\dots,t_m)=0$ for some $p\in k[X_1,\dots,X_m]$ . We can view $p(t_1,\dots,t_m)$ as a polynomial in $t_m$ with coefficients in $k[t_1,\dots,t_{m-1}]$ , i.e. say

$\displaystyle p(t_1,\dots,t_m)=\sum_{i=0}^n p_i(t_1,\dots,t_{m-1})t_m^i=0$ .

Since $P(1)$ is true, it folows that $p_i(t_1,\dots,t_{m-1})=0$ for each $i=0,1,\dots,n$ . But then $p_i=0$ for each $i$ by our hypothesis. Thus $p=0$ , implying $P(m)$ is true.

Therefore, by induction, $T$ is algebraically independent, i.e. $T\in\mathcal F$ . $\square$

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.

Finite Automata 2: Cobham’s Theorem

Positive integers $x$ and $y$ are said to be multiplicatively dependent if $x^m=y^n$ for some $m,n\in\mathbb N$ . If $x$ and $y$ are not multiplicatively dependent, we say they are multiplicatively independent. Cobham’s theorem states the following:

Theorem 1 (Cobham, 1969). If an infinite set is both $p$ -automatic and $q$ -automatic, then $p$ and $q$ are multiplicatively dependent.

We are not going to prove theorem 1, but let us prove the following special case:

Theorem 2. If $S=\{1,p,p^2,\dots\}$ is $q$ -automatic, then $p$ and $q$ are multiplicatively dependent.

At first glance it is perhaps not obvious that theorem 2 is a special case of theorem 1. So let us show that it indeed is:

Theorem 3. The set $S$ in theorem 2 is $p$ -automatic.

Proof. We construct a DFA $(\Sigma_{p},Q,q_0,\delta,F)$ as follows:

$Q=\{q_0,q_1,q_2\}$
$F=\{q_1\}$
$\delta(q_0,0)=q_0$
$\delta(q_0,1)=q_1$
$\delta(q_0,j)=q_2$ for each $j\in\Sigma_p\backslash\{0,1\}$
$\delta(q_1,k)=q_2$ for each $k\in\Sigma_p$
$\delta(q_2,k)=q_2$ for each $k\in\Sigma_p$

This shows that $S$ is $p$ -automatic. $\square$

In fact, from the following result it follows that the set $S$ in theorem 2 is actually $p^k$ -automatic for each $k\in\mathbb N$ :

Theorem. If $S\subseteq\mathbb N$ is $p$ -automatic, then it is $p^k$ -automatic for each $k\in\mathbb N$ .

Proof. Since $S$ is $p$ -automatic, there exists a DFA $\Gamma=(\Sigma_{p},Q,q_0,\delta,F)$ such that $S=\{[w]_p:w\in\mathcal L_\Gamma\}$ . Now we construct a new DFA $(\Sigma_{p^k},Q,q_0,\delta',F)$ by defining $\delta'(q,p^j+r)=\delta(q,r)$ inductively for each $j\in\{1,2,\dots,k-1\}$ and $r\in\{0,1,\dots,p^j-1\}$ . This shows that $S$ is $p^k$ -automatic. $\square$

Proof of theorem 2. Since $S=\{1,p,p^2,\dots\}$ is $q$ -automatic, by the Pumping Lemma there exists a DFA $\Gamma=(\Sigma_{q},Q,q_0,\delta,F)$ and $a,b,c\in\Sigma_q^*$ with $|b|\ge 1$ such that $ab^nc\in\mathcal L_\Gamma$ for all $n\ge 0$ . So $[ab^nc]_q\in S$ for all $n\ge 0$ , i.e. there exist integers $0\le k_0< k_1<\cdots$ such that $[ab^nc]_q=p^{k_n}$ for all $n$ . Note that

$[ab^nc]_q=q^{n|b|+|c|}[a]_q+q^{(n-1)|b|+|c|}[b]_q+\cdots+q^{|c|}[b]_q+[c]_q.$

$p^{k_{n+1}}-q^{|b|}p^{k_n}=[c]_q+q^{|c|}[b]_q-q^{|b|}[c]_q$

for each $n\ge 0$ . The right-hand-side above is constant, and is divisible by $p^{k_n}$ for each $n\ge 0$ . So it must be identically $0$ , i.e.

$q^{|c|}[b]_q=(q^{|b|}-1)[c]_q.$

Since $|b|\ge 1$ , we have $\gcd(q^{|c|},q^{|b|}-1)=1$ . Hence $q^{|c|}$ divides $[c]_q$ . If we write $[c]_q=c_0+c_1q+\cdots+c_mq^m$ , then $q^{|c|}=q^{m+1}>[c]_q$ . So $[c]_q=0$ . As a result, $[b]_q=0$ . Therefore $q^{|b|}=p^{k_{n+1}-k_n}$ , i.e. $p$ and $q$ are multiplicatively dependent, as required. $\square$

1 Comment

Filed under Combinatorics, Number Theory

Tagged as finite automata

25/10/2014 · 6:01 pm

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.

Monthly Archives: October 2014

An Application of Zorn’s Lemma: Transcendence Bases

Finite Automata 3: Non-Automatic Sets

Finite Automata 2: Cobham’s Theorem

Finite Automata 1: Automatic Sets

Posts

Categories

Archives

Tags

Visits