A conversion routine revisited

In the following, $c(k:1\leq k)$ is a sequence of integers satisfying

(0) ${c}_{k} \geq 2\;$ for all $k \geq 1$ ,

but, for the time being, only $c_{k} \neq 0$ is relevant: it allows us to define $\omega (k;0\leq k)$ by

(1) ${w}{0} = 1$ ${w}{k - 1} = {c}{k} * {w}{k}\;$ for all $k \geq 1$ .

We now consider the following program defining the sequence $d\left( {k : {1st}}\right)$ in terms of the real number $R$

$$ \begin{array}{l} n, p := 0, R \quad {P o } \ ; \underline {{d o}} \quad t r u e \rightarrow \quad n: = n + 1 \quad {P _ {1} } \ ; d _ {n}, f := I N T F R A. (f * c _ {n}) {P o } \ \mathrm {o d} \ \end{array} $$

where, for the time being, our only knowledge about the pair-valued function INTFRA of a real argument is

$\Rightarrow x + y = 2$

The above suffices to demonstrate the invariance of

[{P}{0} : \;R = \left( {{2k} : 0 < k \land k \leq n : {d}{k} * {w}{k}}\right) + {f}^{ * }{w}{n}]

(Leaving the fact that $n$ is natural understood).

In order to verify that the initialiZation establishes Po we observe

$$ \begin{array}{l} w p _ {n, f} = 0, R ^ {\prime \prime}. P o \ = {\mathrm {a x i o m o f a s s i g n m e n t}, \mathrm {d e f i n i t i o n o f P O} } \ R = (\sum k: 0 < k \land k \leq 0: d _ {k} * w _ {k}) + R * w _ {0} \ = {\mathrm {d e f i n i t i o n o f e m p t y s u m}; (1) \ R = 0 + R * 1 \ = \begin{array}{l} {{\mathrm {a r i t h m e r i c} }} \ {\mathrm {t r u e}} \end{array} \ \end{array} $$

In order to verify the invariance of $P_0$

we observe -after introducing the abbreviation $S$ :

$$ S = d _ {n}, f := I n t e r a. (f * c _ {n}) $$

$$ \begin{array}{l} f o r n \geqslant 1 \ w p. S. P o \ = {\mathrm {d e f i n i t i o n} o f P _ {0} } \ w p. S. (R = (\sum k: 0 < k \land k \leq n: d _ {k} * w _ {k}) + f * w _ {n}) \ = {\mathrm {s p l i t t i n g t h e r a n g e , a s} n \geqslant 1 } \ w p. S. (\widehat {R} = (\sum k: 0 < k \land k \leq n - 1: d _ {k} * w _ {k}) + \ (d _ {n} + f) * w _ {n}) \ = {\mathrm {a x i o m o f} P \mathrm {a s s i g n m e n t}, \mathrm {d e f i n i t i o n o f} S, (3) } \ (\sum k: 0 < k \land k \leq n - 1: d _ {k} \times w _ {k}) + f * c _ {n} \times w _ {n} \ = {(2) \mathrm {w i t h} k := n } \ (\sum k: 0 < k \land k \leq n - 1: d _ {k} * w _ {k}) + f * w _ {n - 1} \ = {\mathrm {d e f i n i t i o n o f} P O \mathrm {a n d o f s u b s t i t u l i o n} } \ (n := n - 1). P _ {0} \ = {\mathrm {o u r n o m e n d a t u r e} } \ p _ {1} \ \end{array} $$

Since $[wp..^{n:= n+1}, P_1 \equiv P_0]$ , the invariance of $P_0$ has now been established.

Our next target is

$R = \left( {\sum k : 0 < k : {d}{k} * {w}{k}}\right)$ a relation which follows from $P$ of (5) $\mathop{\lim }\limits_{{k \rightarrow \infty }}{f}^{ * }{w}_{k} = 0\;\left( {k \rightarrow \infty }\right)$

In view of (0) which now becomes relevant - and (2), $\mathop{\lim }\limits_{{k \rightarrow \infty }}{w}_{k} = 0$ ,so (5) follows if $f$ is bounded .

A look at the program tells us that boundedness of $f$ depends on the function $\text{INTERA}$ , about which, up till now, only (3) has been given. For given $z$ , the relation $x + y = z$ of (3)'s consequent can be satisfied in many ways: the one extreme, viz. $x = 0 \land y = z$ , leads to unbounded $f$ , the other extreme, viz. $x = z \land y = 0$ leads, instead of to the general (4), to $R = d_{1} * w_{1}$ , which is not interesting. So we choose something in between.

The left element of INTFRA.2 is constrained by

(6) $x,y = \operatorname{INTFRA.2} \Rightarrow x$ is integer

which allows us to restrict $y$ to a unit interval. For

the constraint on $y$ we consider the following two alternatives:

(i) $x,y =$ INFRA.2 $\Rightarrow 0 \leq y \land y < 1\;$ and (ii) $x,y =$ INFRA. $z \Rightarrow 0 < y \land y \leq 1$

We now restrict our investigation of these alternatives to $0 < R \land R < 1$ ; in the following it becomes relevant that $c$ is a sequence of integers.

Alternative (i) leads to the invariance of

$$ 0 \leq f \wedge f < 1; $$

alternative (ii) leads to the invariance of

$$ 0 < f \land f \leq 1 $$

In both cases we have for all $k$

$$ 0 \leq d _ {k} \wedge d _ {k} < c _ {k} $$

The minimum value 0 and the maximum value ${c}{k} - 1$ can in both cases occur for ${d}{k}$ .

For a given sequence $c$ , we call an R-value sensitive if its corresponding sequence $d$ depends on whether (i) or (ii) has been chosen, otherwise we call it insensitive. We shall see below that for any sequence $c$ , values of both types exist.

Because of $0 < R \land R < 1$ ,the initialiZation

$0 < f$ , $f < 1$

If with one of the alternatives for INFRA, $f * c_n$ is never integer, (7) is an invariant and the computation is indistinguishable from the one with the same $R$ but the other alternative for INFRA: $R$ is insensitive. (E.g. $R = \frac{1}{2}$ for $c_k = 3$ .)

We now investigate the case in which, sooner or later, the repeatable statement falsifies (7). That occurs when, with $f$ satisfying (7), $f * c_n$ is integer; let then

$$ f \star c _ {n}, n = q, N $$

Because $f$ satisfies (7), $g$ satisfies

$$ 1 \leq q \wedge q < c _ {N} $$

The rest of the computation depends on which alternative has been chosen for INTERA. With (i), the assignment is effectively

$$ d _ {N}, f := q, 0 $$

and, $f = 0$ being stable with (i), the program defines

$$ (\underline {{A}}) _ {k}: N < k: d _ {k} = 0), $$

i.e. sequence $d$ ends with $d_{N} > 0$ , followed by "the minimum tail".

With (ii), the assignment is effectively

$$ d _ {N}, f := q - 1, 1, $$

and, $f = 1$ being stable with(ii),the program defines

$$ (A k: N < k: d _ {k} = c _ {k - 1}) $$

i.e. sequence $d$ ends with $d_{N} < c_{N} - 1$ , followed by "the maximum tail".

We conclude that an $R$ giving rise to an integer $f * c_n$ is sensitive.

Remark With, for some positive $N$ , $R = {w}_{N}$ , $R$ is sensitive. In view of (4),the above analysis tells us

(8) ${w}{N} = \left( {{\sum k} : N < k : \left( {{c}{k} - 1}\right) * {w}_{k}}\right)$

(End of Remark.)

If $R$ and $d$ satisfy (4), we say that " $d$ is a representation of $R$ ", and in that terminology we just found that insensitive values have at least 1 representation and sensitive values have at least 2 representations. Under the constraint

$$ (\underline {{B}} k: 0 < k: 0 \leq d _ {k} \land d _ {k} < c _ {k}) $$

values don't have more representations. The argument relies primarily on the monotonicity of addition. We ask ourselves under what circumstances two different sequences can represent the same value. Let $X$ be the common prefix of the two sequences, in the one followed by "p tail" and in the other by "q tail", with $p < q$ . We now consider the following sequences and values

X p tailo X p maximum tail R1 $\mathrm{X}\;p + 1$ minimum tail ${\mathrm{R}}_{2}$ X 9 minimum tail R3 [\text{X.}\;g\;t\text{ail}\text{I}\;R\text{4}]

Because in tail O ${d}{k} < {c}{k},{R0} \leq {R1}$ and ${R0} = {R1}$

Because of $p < q,\;{R}{2} \leq {R}{3};\;{R}{2} = {R}{3} \Rightarrow p + 1 = q\cdots$ Because in tail 1, ${0.5}{d}{k},{R}{3} \leq {R}{4}$ and ${R}{3} = {R}_{4}$ $\Rightarrow$ minimum tail = tail 1 . Because the sequence

of $R$ -values is ascending, ${R0} = {R4}$ implies that

they are all equal, hence

$$ \begin{array}{l} t a i l 0 = m a x i m u m t a i l \ p + 1 = q \ t a i l 1 = m i n i m u m t a i l, \ \end{array} $$

and the two sequences representing the sensitive value are the ones generated according to (ii) and

(i) respectively. Also: a sequence not ending in an extreme tail is insensitive.

In other words, the shape of the sequence - i.e. wheth- er or not it has an extreme tail- determines whether the value represented by the sequence is sensitive or not.

Each sensitive $R$ is rational. The fraction $1 / q$ is sensitive provided, for some $N$ , $q$ divides the product of the first $N$ c-values. Hence, each rational $R$ is sensitive provided

(9) $\underset{⏜}{A}q : 0 < q : \left( {{EN} : q\text{divides}\left( {\pi k : 0 < k\;{k\sin }{C}_{k}}\right) }\right) )$ Combining the two observations,we conclude

(9) $\Rightarrow \;\left( {R\text{ is sensitive}}\right) \equiv \left( {R\text{ is rational}}\right)$

Condition (9) is clearly satisfied for $c_{k} = k + 1$ . Hence, the basis of the natural logarithm, is irrational.

Nuenen, 6 January 1991

propd. Edsger W. Dgksha Department of Computer Sciences The University of Texas at Austin Austin, TX 78712-1188 USA