Frédéric Wang Subscribe   About   Mathematics   Computer Science   Miscellaneous   Archive

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 nn she decides to move forward or backward by 12n+1\frac{1}{2^{n+1}}. If ϵn{1,1}\epsilon_n \in {\{-1, 1\}} corresponds to the chosen direction then writing S0=0S_0 = 0 and

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

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

Avoiding an at most countable subset

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

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

Incidentally, X=X = \mathbb N with trivial enumeration xn=nx_n = n shows a simple counter-example with no term below 1-1 and ultimately constant ϵn\epsilon_n. In that case, S0=0S_0 = 0 and S1=12S_{1} = \frac{1}{2} and Sn+1=Sn12n+1S_{n+1} = S_{n} - \frac{1}{2^{n+1}} for n1n \geq 1. But S=0S_\infty = 0 \in \mathbb N.

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

Whatever the decision chosen, we can show that SXS_{\infty} \notin X. Otherwise, consider one NN such that ϵN\epsilon_{N} is defined by moving away from SS_{\infty}. Then either SNS0{S_N - S_\infty} \geq 0 and SN+1=SN+12N+1S+12N+1S_{N+1} = {S_N + \frac{1}{2^{N+1}}} \geq {S_\infty + \frac{1}{2^{N+1}}} or SN+1=SN12N+1<S12N+1S_{N+1} = {S_N - \frac{1}{2^{N+1}}} < {S_\infty - \frac{1}{2^{N+1}}}. But in any case, we would have |SSN+1|12N+1{\left| S_\infty - S_{N+1} \right| \geq \frac{1}{2^{N+1}}} which contradicts our strict inequality for not ultimately constant ϵn\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 {xn:n}=\left\{ x_n : n \in \mathbb N \right\} = \mathbb Q, which gives us an irrational number SS_\infty. If instead XX is the set of algebraic numbers (which is countable and contains \mathbb Q) then we obtain a transcendental SS_\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 (xn)n{(x_n)}_{n \in \mathbb N} that lists all the \mathbb Q. For example, a simple way to enumerate the fractions pq\frac{p}{q} without trying to avoid duplicate values is, for each M=0,1,2,...M=0, 1, 2, ... to enumerate the integers pp and q0q \neq 0 bounded by MM in the lexicographical order. One can similarly enumerate for each MM the non-constant polynomial of degree at most MM and integer coefficient bounded by MM 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 SnαS_n - \alpha and so determine ϵn\epsilon_n. But in theory, α\alpha can be arbitrary close to SnS_n so it’s not clear how much precision to request.

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

For any integer M1M \geq 1, let’s consider QM±=(X±2)MQ_M^\pm = {(X \pm 2)}^M. Then its product with its derivative is M(X±2)2M1M {(X \pm 2)}^{2M -1}. Its value at any xx has the same sign as x±2x \pm 2 and if |x|<1\left|x\right| < 1 it just ±\pm. For any nn, we can find MM large enough such that QM+Q_M^+ and QMQ_M^- have not been enumerated yet. So ϵn\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 SS_\infty is still algebraic. If that’s not the case, let nn such that Pn(S)=0{P_n(S_\infty)} = 0. We can choose nn such that PnP_n is of minimal degree and so Pn(S)0{P_n\prime(S_\infty)} \neq 0. Since PnP_n has only finitely many roots, there is knk \geq n such that at maximum distance 12k\frac{1}{2^k} around SS_\infty, SS_\infty is the only root of PnP_n and PnP_n\prime does not vanish. Let’s MM large enough such that the polynomial RM=Pn2M+1R_M = P_n^{2M+1} has not been enumerated before PkP_k. Let’s ll such that Pl=RMP_l = R_M.

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