Category Archives: Analysis

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

More on irrationality

Recall some of the irrationality criteria that we discussed in the last post. We showed that

Proposition 1. Let a_1,a_2,\dots be a sequence of non-zero integers such that

(\dagger)\qquad\displaystyle S=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\dots exists, and

(\ddagger)\qquad\displaystyle \frac{1}{a_{n+1}}+\frac{1}{a_{n+1}a_{n+2}}+\frac{1}{a_{n+1}a_{n+2}a_{n+3}}+\dots\to 0 as n\to\infty.

Then S is irrational.

In particular,

Proposition 2. If a_1,a_2,\dots is a sequence of non-zero integers such that |a_1|\le |a_2|\le\dots and \displaystyle\lim_{n\to\infty}|a_n|=\infty, then

\displaystyle S=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\dots

exists and is irrational.

Having proven these, it is natural to ask whether every irrational number can have such a representation. Interestingly, work has already been done on this. The Engel expansion of a positive real number x is a unique expansion of the form

\displaystyle x=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\dots

where \{a_n\} is a non-decreasing sequence of positive integers. Every positive rational number has a finite Engel expansion, and x is irrational if an only if this expansion is infinite.

In this post we shall slightly improve our previous results.

Proposition 3. Let a_1,a_2,\dots and b_1,b_2,\dots be sequences of non-zero integers such that

(\dagger')\qquad\displaystyle S=\frac{b_1}{a_1}+\frac{b_2}{a_1a_2}+\frac{b_3}{a_1a_2a_3}+\dots exists, and

(\ddagger')\qquad\displaystyle \frac{b_{n+1}}{a_{n+1}}+\frac{b_{n+2}}{a_{n+1}a_{n+2}}+\frac{b_{n+3}}{a_{n+1}a_{n+2}a_{n+3}}+\dots\to 0 as n\to\infty.

Then S is irrational.

Proof. The same argument in the proof of Proposition 1 applies. \square

Proposition 4. If a_1,a_2,\dots and b_1,b_2,\dots are sequences of non-zero integers such that |a_1|\le |a_2|\le\dots and \displaystyle\lim_{n\to\infty}|b_n/a_n|=0 then

\displaystyle S=\frac{b_1}{a_1}+\frac{b_2}{a_1a_2}+\frac{b_3}{a_1a_2a_3}+\dots

exists and is irrational.

Proof. It suffices to show that (\dagger') and (\ddagger') above hold.

Convergence follows easily using the ratio test. So we show that (\ddagger') holds.

We have, for sufficiently large n,

\displaystyle\left|\frac{b_{n+1}}{a_{n+1}}+\frac{b_{n+2}}{a_{n+1}a_{n+2}}+\frac{b_{n+3}}{a_{n+1}a_{n+2}a_{n+3}}+\dots\right|

\displaystyle\le\left|\frac{b_{n+1}}{a_{n+1}}\right|+\left|\frac{b_{n+2}}{a_{n+2}}\right|\frac{1}{|a_{n+1}|}+\left|\frac{b_{n+3}}{a_{n+3}}\right|\frac{1}{|a_{n+1}a_{n+2}|}+\dots

\displaystyle\le\left|\frac{b_{n+1}}{a_{n+1}}\right|+\frac{1}{|a_{n+1}|}+\frac{1}{|a_{n+1}|^2}+\frac{1}{|a_{n+1}|^3}+\dots

\displaystyle =\left|\frac{b_{n+1}}{a_{n+1}}\right|+\frac{1}{|a_{n+1}|-1}

\displaystyle\le\left|\frac{b_{n+1}}{a_{n+1}}\right|+\frac{2}{|a_{n+1}|}

\displaystyle\le 3\left|\frac{b_{n+1}}{a_{n+1}}\right|\to 0 as n\to\infty.

So (\ddagger') holds, as desired. \square

As an immediate corollary we get:

Corollary 1. Let f:\mathbb R\to\mathbb R have an infinite Taylor expansion about x=0 that converges for |x|\le 1. If f^{(n)}(0)\in\mathbb Z\,\forall n\ge 0 and f^{(n)}(0)=o(n) as n\to\infty, then f(1/k) is irrational \forall k\in\mathbb Z\backslash\{0\}.

Taking, for example, f(x)=\rho\exp(x)+\mu\sin(x)+\nu\cos(x) yields:

Corollary 2. Let \rho,\mu,\nu be integers, not all zero. Then \rho\exp(1/k)+\mu\cos(1/k)+\nu\sin(1/k) is irrational \forall k\in\mathbb Z\backslash\{0\}.

In particular, e\pm\sin 1, e\pm\cos 1,\sin 1\pm\cos 1, e\pm\sin 1\pm\cos 1  etc are all irrational.

Leave a comment

Filed under Analysis, Number theory

An irrationality criterion

Recall Corollary 4 from this post:

Corollary 4. If S is a subgroup of (\mathbb R,+), then the following are equivalent:

(i) S is well-ordered;

(ii) S is not dense;

(iii) S is cyclic.

Let \alpha be a non-zero real number and take S=\langle 1,\alpha\rangle to be the subgroup of (\mathbb R,+) generated by 1 and \alpha. This is a cyclic group if and only if \exists \beta, \langle 1,\alpha\rangle=\langle \beta\rangle
\Leftrightarrow 1=m\beta', \alpha=n\beta' for some m,n\in\mathbb Z and \beta'
\Leftrightarrow \alpha/1=n/m, i.e. \alpha is rational.

Now by the above corollary, S is dense iff it is not well-ordered, i.e. iff

(*)\qquad\forall\varepsilon>0,\exists m,n\in\mathbb Z, 0<m\alpha-n<\varepsilon.

So we have the following criterion for irrationality:

Criterion 1. \alpha is irrational if and only if (*) holds.

Note that S is dense in \mathbb R iff S/\mathbb Z=\{\{n\alpha\}:=n\alpha-\lfloor n\alpha\rfloor : n\in\mathbb Z\} is dense in (0,1). So we deduce:

Criterion 2. \alpha is irrational \Leftrightarrow\forall\varepsilon>0,\exists n\in\mathbb Z, 0<\{n\alpha\}<\varepsilon.

We demonstrate how this may be useful by proving that certain types of numbers are irrational.

Proposition 1. Let a_1,a_2,\dots be a sequence of non-zero integers such that

(\dagger)\qquad\displaystyle S=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\dots exists, and

(\ddagger)\qquad\displaystyle\frac{1}{a_{n+1}}+\frac{1}{a_{n+1}a_{n+2}}+\frac{1}{a_{n+1}a_{n+2}a_{n+3}}+\dots\to 0 as n\to\infty.

Then S is irrational.

Proof. We have

\displaystyle \left\{a_1\cdots a_nS\right\}=\left\{\frac{1}{a_{n+1}}+\frac{1}{a_{n+1}a_{n+2}}+\frac{1}{a_{n+1}a_{n+2}a_{n+3}}+\dots\right\}.

Multiplying by -1 if necessary, we can take the expression in brackets on the right to be positive and it tends to 0 as n\to \infty. Moreover, if

\displaystyle\frac{1}{a_{n+1}}+\frac{1}{a_{n+1}a_{n+2}}+\frac{1}{a_{n+1}a_{n+2}a_{n+3}}+\dots=0

then

\displaystyle\frac{1}{a_{n+2}}+\frac{1}{a_{n+2}a_{n+3}}+\frac{1}{a_{n+2}a_{n+3}a_{n+4}}\dots=-1

which cannot happen infinitely often as the left hand side tends to zero. So the conclusion follows by Criterion 2. \square

Proposition 2. If a_1,a_2,\dots is a sequence of non-zero integers such that |a_1|\le |a_2|\le\dots and \displaystyle\lim_{n\to\infty}|a_n|=\infty, then

\displaystyle S=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\dots

exists and is irrational.

Proof. It suffices to show that (\dagger) and (\ddagger) above hold.

Convergence follows easily from the ratio test, so (\dagger) holds. Now

\displaystyle\left|\frac{1}{a_{n+1}}+\frac{1}{a_{n+1}a_{n+2}}+\frac{1}{a_{n+1}a_{n+2}a_{n+3}}+\dots\right|

\displaystyle\le\frac{1}{|a_{n+1}|}+\frac{1}{|a_{n+1}a_{n+2}|}+\frac{1}{|a_{n+1}a_{n+2}a_{n+3}|}+\dots

\displaystyle\le\frac{1}{|a_{n+1}|}+\frac{1}{|a_{n+1}|^2}+\frac{1}{|a_{n+1}|^3}+\dots 

\displaystyle =\frac{1}{|a_{n+1}|-1}\to 0 as n\to \infty,

i.e. (\ddagger) holds. \square

Some special cases of Proposition 2 are particularly interesting:

Corollary 1. \displaystyle \sum_{n=0}^\infty\frac{1}{(n!)^k} is irrational for all positive integers k.

Proof. Take a_n=n^k. \square.

Corollary 2. e is irrational.

Proof. Take k=1 in Corollary 1. \square

Corollary 3. \sin 1 and \cos 1 are irrational.

Proof. Take a_1=1 and for n>1, a_n=-(2n-2)(2n-1) for sine, a_n=-(2n-3)(2n-2) for cosine. \square

Corollary 4. I_0(2) and I_1(2) are irrational, where I_\alpha(x) is the modified Bessel function of the first kind.

Proof. Taking k=2 in Corollary 1 shows that I_0(2) is irrational. Taking a_n=n(n+1) shows that I_1(2) is irrational. \square

Corollary 5. e^{\sqrt{2}} is irrational.

Proof. If it is rational, then so is e^{-\sqrt{2}}, and so is

\displaystyle \cosh(\sqrt 2)=\frac{e^{\sqrt{2}}+e^{-\sqrt 2}}{2}=\sum_{n=0}^\infty\frac{2^n}{(2n)!}.

Taking a_n=n(2n-1) in the above shows that this is false. \square

Corollary 6. Let k>1 be an integer and F_0,F_1,F_2,\dots the Fibonacci sequence. Then

(i) \displaystyle \sum_{n=0}^\infty\frac{1}{k^{F_n}} is irrational.

(ii) \displaystyle \sum_{n=0}^\infty\frac{1}{F_{k^n}} is irrational.

Proof. (i) Take a_n=k^{F_n} and use F_0+F_1+\dots+F_n=F_{n+2}-1.

(ii) Take a_n=F_{k^n}/F_{k^{n-1}}. \square

1 Comment

Filed under Analysis, Number theory