# Transcendental number from the oscillating zeno's paradox

## 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 $\backslash frac\{1\}\{2^\{n+1\}\}$. If $\backslash epsilon\_n\; \backslash in\; \{\backslash \{-1,\; 1\backslash \}\}$ corresponds to the chosen direction then writing $S\_0\; =\; 0$ and

$$S\_\{n+1\}\; =\; S\_n\; +\; \backslash frac\{\backslash epsilon\_n\}\{2^\{n+1\}\}$$we obtain sequence of Atalatan’s position on the real line.

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

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

## Avoiding an at most countable subset

Suppose that $X\; \backslash subseteq\; \backslash mathbb\; R$ is at most countable and let $\{(x\_n)\}\_\{n\; \backslash in\; \backslash mathbb\; N\}$ be a sequence of real numbers such that $X\; =\; \backslash left\backslash \{\; x\_n\; :\; n\; \backslash in\; \backslash mathbb\; N\; \backslash right\backslash \}$. We want to find a sequence such that $S\_\backslash infty\; \backslash 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 $\backslash epsilon\_n\; =\; 1$ if and only if $S\_n\; \backslash 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\; =\; \backslash mathbb\; N$ with trivial enumeration $x\_n\; =\; n$ shows a simple counter-example with no term below $-1$ and ultimately constant $\backslash epsilon\_n$. In that case, $S\_0\; =\; 0$ and $S\_\{1\}\; =\; \backslash frac\{1\}\{2\}$ and $S\_\{n+1\}\; =\; S\_\{n\}\; -\; \backslash frac\{1\}\{2^\{n+1\}\}$ for $n\; \backslash geq\; 1$. But $S\_\backslash infty\; =\; 0\; \backslash in\; \backslash mathbb\; N$.

To workaround that issue, we can alternatively define the sequence $\backslash epsilon\_\{2n\}\; =\; 1$ if and only if $S\_n\; \backslash geq\; x$ and $\backslash epsilon\_\{2n+1\}\; =\; -\backslash epsilon\_\{2n\}$. 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\_\{\backslash infty\}\; \backslash notin\; X$. Otherwise, consider one $N$ such that $\backslash epsilon\_\{N\}$ is defined by moving away from $S\_\{\backslash infty\}$. Then either $\{S\_N\; -\; S\_\backslash infty\}\; \backslash geq\; 0$ and $S\_\{N+1\}\; =\; \{S\_N\; +\; \backslash frac\{1\}\{2^\{N+1\}\}\}\; \backslash geq\; \{S\_\backslash infty\; +\; \backslash frac\{1\}\{2^\{N+1\}\}\}$ or $S\_\{N+1\}\; =\; \{S\_N\; -\; \backslash frac\{1\}\{2^\{N+1\}\}\}\; <\; \{S\_\backslash infty\; -\; \backslash frac\{1\}\{2^\{N+1\}\}\}$. But in any case, we would have $\{\backslash left|\; S\_\backslash infty\; -\; S\_\{N+1\}\; \backslash right|\; \backslash geq\; \backslash frac\{1\}\{2^\{N+1\}\}\}$ which contradicts our strict inequality for not ultimately constant $\backslash epsilon\_n$.

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

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

## An explicit computation

The big difference between the case of $\backslash mathbb\; Q$ and the set of algebraic numbers is that it’s much easier to actually compute a list of $\{(x\_n)\}\_\{n\; \backslash in\; \backslash mathbb\; N\}$ that lists all the $\backslash mathbb\; Q$. For example, a simple way to enumerate the fractions $\backslash frac\{p\}\{q\}$ without trying to avoid duplicate values is, for each $M=0,\; 1,\; 2,\; ...$ to enumerate the integers $p$ and $q\; \backslash 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 $\backslash alpha$ in order to be able to calculate the sign $S\_n\; -\; \backslash alpha$ and so determine $\backslash epsilon\_n$. But in theory, $\backslash alpha$ can be arbitrary close to $S\_n$ so it’s not clear how much precision to request.

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

For any integer $M\; \backslash geq\; 1$, let’s consider $Q\_M^\backslash pm\; =\; \{(X\; \backslash pm\; 2)\}^M$. Then its product with its derivative is $M\; \{(X\; \backslash pm\; 2)\}^\{2M\; -1\}$. Its value at any $x$ has the same sign as $x\; \backslash pm\; 2$ and if $\backslash left|x\backslash right|\; <\; 1$ it just $\backslash pm$. For any $n$, we can find $M$ large enough such that $Q\_M^+$ and $Q\_M^-$ have not been enumerated yet. So $\backslash 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\_\backslash infty$ is still algebraic. If that’s not the case, let $n$ such that $\{P\_n(S\_\backslash infty)\}\; =\; 0$. We can choose $n$ such that $P\_n$ is of minimal degree and so $\{P\_n\backslash prime(S\_\backslash infty)\}\; \backslash neq\; 0$. Since $P\_n$ has only finitely many roots, there is $k\; \backslash geq\; n$ such that at maximum distance $\backslash frac\{1\}\{2^k\}$ around $S\_\backslash infty$, $S\_\backslash infty$ is the only root of $P\_n$ and $P\_n\backslash prime$ does not vanish. Let’s $M$ large enough such that the polynomial $R\_M\; =\; P\_n^\{2M+1\}$ has not been enumerated before $P\_k$. Let’s $l$ such that $P\_l\; =\; R\_M$.

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