# Transcendental number from the oscillating zeno's paradox

In a previous blog post, I described an oscillating Zeno’s paradox, which can be formalized as follows. Atalanta moves on the real line. She leaves from 0 and at step $n$ she decides to move forward or backward by $\frac\left\{1\right\}\left\{2^\left\{n+1\right\}\right\}$. If $\epsilon_n \in \left\{\\left\{-1, 1\\right\}\right\}$ corresponds to the chosen direction then writing $S_0 = 0$ and

$S_\left\{n+1\right\} = S_n + \frac\left\{\epsilon_n\right\}\left\{2^\left\{n+1\right\}\right\}$

we obtain sequence of Atalatan’s position on the real line.

In the non-oscillating case ($\epsilon_n = 1$ for all $n$) then this just corresponds to a geometric series of common ration $\frac\left\{1\right\}\left\{2\right\}$. $S_n$ converges to 1 by lower values, with remaining distance being $\frac\left\{1\right\}\left\{2^n\right\}$. More generally, $S_n$ is just the partial sum of an absolutely convergent series and so is convergent to a destination $S_\infty = \left\{\sum_\left\{n=0\right\}^\left\{+\infty\right\} \frac\left\{\epsilon_n\right\}\left\{2^\left\{n+1\right\}\right\}\right\}$. It is easy to see that $\left|S_n\right| < 1$, $\left|S_\infty\right| \leq 1$ and $\left\{\left| S_\infty - S_n \right| \leq \frac\left\{1\right\}\left\{2^n\right\}\right\}$. If additionally $\epsilon_n$ is chosen so that it is not ultimately constant (i.e. Atalatan’s position keeps oscillating) then this becomes a strict inequality $\left\{\left| S_\infty - S_n \right| < \frac\left\{1\right\}\left\{2^n\right\}\right\}$.

In theory, it is possible to reach any destination $x \in \left\{\left[-1,1\right]\right\}$ using this approach. Just define $\epsilon_n = 1$ if and only if $S_n \leq x$ (i.e. “move toward $x$”). It is easy to prove by recurrence that $\left\{\left| x - S_n \right| \leq \frac\left\{1\right\}\left\{2^n\right\}\right\}$ for all $n$ and so $S_\infty = x$. However, this assumes we already know $x$ in order to decide the sequence of directions $\epsilon_n$. Let’s see how to build sequences without knowing the destination.

## Avoiding an at most countable subset

Suppose that $X \subseteq \mathbb R$ is at most countable and let $\left\{\left(x_n\right)\right\}_\left\{n \in \mathbb N\right\}$ be a sequence of real numbers such that $X = \left\\left\{ x_n : n \in \mathbb N \right\\right\}$. We want to find a sequence such that $S_\infty \notin X$.

Assuming additionally that it has infinitely many terms above $1$ and infinitely many terms below $-1$, then we obtain a non-ultimately-constant sequence by defining $\epsilon_n = 1$ if and only if $S_n \geq x_n$ (i.e. “move away from $x$”). This is because $-1 < S_n < 1$ so there are always infinitely many terms in front of and behind Atalanta.

Incidentally, $X = \mathbb N$ with trivial enumeration $x_n = n$ shows a simple counter-example with no term below $-1$ and ultimately constant $\epsilon_n$. In that case, $S_0 = 0$ and $S_\left\{1\right\} = \frac\left\{1\right\}\left\{2\right\}$ and $S_\left\{n+1\right\} = S_\left\{n\right\} - \frac\left\{1\right\}\left\{2^\left\{n+1\right\}\right\}$ for $n \geq 1$. But $S_\infty = 0 \in \mathbb N$.

To workaround that issue, we can alternatively define the sequence $\epsilon_\left\{2n\right\} = 1$ if and only if $S_n \geq x$ and $\epsilon_\left\{2n+1\right\} = -\epsilon_\left\{2n\right\}$. This still moves away from all $x_n$ once, keeps oscillating and does not require additional assumption on $X$.

Whatever the decision chosen, we can show that $S_\left\{\infty\right\} \notin X$. Otherwise, consider one $N$ such that $\epsilon_\left\{N\right\}$ is defined by moving away from $S_\left\{\infty\right\}$. Then either $\left\{S_N - S_\infty\right\} \geq 0$ and $S_\left\{N+1\right\} = \left\{S_N + \frac\left\{1\right\}\left\{2^\left\{N+1\right\}\right\}\right\} \geq \left\{S_\infty + \frac\left\{1\right\}\left\{2^\left\{N+1\right\}\right\}\right\}$ or $S_\left\{N+1\right\} = \left\{S_N - \frac\left\{1\right\}\left\{2^\left\{N+1\right\}\right\}\right\} < \left\{S_\infty - \frac\left\{1\right\}\left\{2^\left\{N+1\right\}\right\}\right\}$. But in any case, we would have $\left\{\left| S_\infty - S_\left\{N+1\right\} \right| \geq \frac\left\{1\right\}\left\{2^\left\{N+1\right\}\right\}\right\}$ which contradicts our strict inequality for not ultimately constant $\epsilon_n$.

As explained in the previous blog, this shows that $\mathbb R$ (or any complete subspace containing $\mathbb Q$) is uncountable. Otherwise, we could use a sequence enumerating it to arrive to a contradiction.

Similarly, because $\mathbb Q$ is countable then we can find a sequence such that $\left\\left\{ x_n : n \in \mathbb N \right\\right\} = \mathbb Q$, which gives us an irrational number $S_\infty$. If instead $X$ is the set of algebraic numbers (which is countable and contains $\mathbb Q$) then we obtain a transcendental $S_\infty$.

## An explicit computation

The big difference between the case of $\mathbb Q$ and the set of algebraic numbers is that it’s much easier to actually compute a list of $\left\{\left(x_n\right)\right\}_\left\{n \in \mathbb N\right\}$ that lists all the $\mathbb Q$. For example, a simple way to enumerate the fractions $\frac\left\{p\right\}\left\{q\right\}$ without trying to avoid duplicate values is, for each $M=0, 1, 2, ...$ to enumerate the integers $p$ and $q \neq 0$ bounded by $M$ in the lexicographical order. One can similarly enumerate for each $M$ the non-constant polynomial of degree at most $M$ and integer coefficient bounded by $M$ but it’s not obvious how to actually compute their roots.

One can rely on root finding algorithm to estimate the roots $\alpha$ in order to be able to calculate the sign $S_n - \alpha$ and so determine $\epsilon_n$. But in theory, $\alpha$ can be arbitrary close to $S_n$ so it’s not clear how much precision to request.

Instead, let’s consider $\left\{\left(P_n\right)\right\}_\left\{n \in \mathbb N\right\}$ an enumeration of the non-constant polynomial with integer cofficients and define $\epsilon_n = 1$ if and only if $\left\{\left(P_n\prime P_n\right)\right\}\left\{\left(S_n\right)\right\} \geq 0$. With that new formula, $\epsilon_n$ can be calculated very easily in $O\left(\deg P_n\right)$ from the cofficients of $P_n$ using Horner’s method.

For any integer $M \geq 1$, let’s consider $Q_M^\pm = \left\{\left(X \pm 2\right)\right\}^M$. Then its product with its derivative is $M \left\{\left(X \pm 2\right)\right\}^\left\{2M -1\right\}$. Its value at any $x$ has the same sign as $x \pm 2$ and if $\left|x\right| < 1$ it just $\pm$. For any $n$, we can find $M$ large enough such that $Q_M^+$ and $Q_M^-$ have not been enumerated yet. So $\epsilon_n$ is not ultimately constant. Alternatively, we could have used the trick from the previous section to force that property.

Now let’s prove that $S_\infty$ is still algebraic. If that’s not the case, let $n$ such that $\left\{P_n\left(S_\infty\right)\right\} = 0$. We can choose $n$ such that $P_n$ is of minimal degree and so $\left\{P_n\prime\left(S_\infty\right)\right\} \neq 0$. Since $P_n$ has only finitely many roots, there is $k \geq n$ such that at maximum distance $\frac\left\{1\right\}\left\{2^k\right\}$ around $S_\infty$, $S_\infty$ is the only root of $P_n$ and $P_n\prime$ does not vanish. Let’s $M$ large enough such that the polynomial $R_M = P_n^\left\{2M+1\right\}$ has not been enumerated before $P_k$. Let’s $l$ such that $P_l = R_M$.

In the considered neighbourhood of $S_\infty$, $P_l$ has only one root $S_\infty$, has the same sign as $P_n$ and its derivative $\left\{\left(2M+1\right)\right\}P_n^\left\{2M\right\} P_n\prime$ has the same nonzero constant sign as $P_n\prime$. Analyzing each combination $P_l\prime$ positive/negative and $S_l$ greater/smaller than $S_\infty$, we verify that $\epsilon_l$ is chosen such that $\left\{\left| S_\infty - S_\left\{l+1\right\} \right| \geq \frac\left\{1\right\}\left\{2^\left\{l+1\right\}\right\}\right\}$ which is obviously also true if $S_l = S_\infty$. This agains contradict our strict inequality. Q.E.D.