Transcendental number from the oscillating zeno's paradox

06 Apr 2020

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{1}{2^{n+1}}$. If $\epsilon_n \in {\{-1, 1\}}$ corresponds to the chosen direction then writing $S_0 = 0$ and

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

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{1}{2}$. $S_n$ converges to 1 by lower values, with remaining distance being $\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_\infty = {\sum_{n=0}^{+\infty} \frac{\epsilon_n}{2^{n+1}}}$. It is easy to see that $\left|S_n\right| < 1$, $\left|S_\infty\right| \leq 1$ and ${\left| S_\infty - S_n \right| \leq \frac{1}{2^n}}$. 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| S_\infty - S_n \right| < \frac{1}{2^n}}$.

In theory, it is possible to reach any destination $x \in {[-1,1]}$ 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| x - S_n \right| \leq \frac{1}{2^n}}$ 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 ${(x_n)}_{n \in \mathbb N}$ be a sequence of real numbers such that $X = \left\{ x_n : n \in \mathbb N \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_{1} = \frac{1}{2}$ and $S_{n+1} = S_{n} - \frac{1}{2^{n+1}}$ for $n \geq 1$. But $S_\infty = 0 \in \mathbb N$.

To workaround that issue, we can alternatively define the sequence $\epsilon_{2n} = 1$ if and only if $S_n \geq x$ and $\epsilon_{2n+1} = -\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_{\infty} \notin X$. Otherwise, consider one $N$ such that $\epsilon_{N}$ is defined by moving away from $S_{\infty}$. Then either ${S_N - S_\infty} \geq 0$ and $S_{N+1} = {S_N + \frac{1}{2^{N+1}}} \geq {S_\infty + \frac{1}{2^{N+1}}}$ or $S_{N+1} = {S_N - \frac{1}{2^{N+1}}} < {S_\infty - \frac{1}{2^{N+1}}}$. But in any case, we would have ${\left| S_\infty - S_{N+1} \right| \geq \frac{1}{2^{N+1}}}$ 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\{ x_n : n \in \mathbb N \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 ${(x_n)}_{n \in \mathbb N}$ that lists all the $\mathbb Q$. For example, a simple way to enumerate the fractions $\frac{p}{q}$ 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 ${(P_n)}_{n \in \mathbb N}$ an enumeration of the non-constant polynomial with integer cofficients and define $\epsilon_n = 1$ if and only if ${(P_n\prime P_n)}{(S_n)} \geq 0$. With that new formula, $\epsilon_n$ can be calculated very easily in $O(\deg P_n)$ from the cofficients of $P_n$ using Horner’s method.

For any integer $M \geq 1$, let’s consider $Q_M^\pm = {(X \pm 2)}^M$. Then its product with its derivative is $M {(X \pm 2)}^{2M -1}$. 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 ${P_n(S_\infty)} = 0$. We can choose $n$ such that $P_n$ is of minimal degree and so ${P_n\prime(S_\infty)} \neq 0$. Since $P_n$ has only finitely many roots, there is $k \geq n$ such that at maximum distance $\frac{1}{2^k}$ 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^{2M+1}$ 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 ${(2M+1)}P_n^{2M} 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| S_\infty - S_{l+1} \right| \geq \frac{1}{2^{l+1}}}$ which is obviously also true if $S_l = S_\infty$. This agains contradict our strict inequality. Q.E.D.