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

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

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.

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