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 she decides to move forward or backward by . If corresponds to the chosen direction then writing and
we obtain sequence of Atalatan’s position on the real line.
In the non-oscillating case ( for all ) then this just corresponds to a geometric series of common ration . converges to 1 by lower values, with remaining distance being . More generally, is just the partial sum of an absolutely convergent series and so is convergent to a destination . It is easy to see that , and . If additionally is chosen so that it is not ultimately constant (i.e. Atalatan’s position keeps oscillating) then this becomes a strict inequality .
In theory, it is possible to reach any destination using this approach. Just define if and only if (i.e. “move toward ”). It is easy to prove by recurrence that for all and so . However, this assumes we already know in order to decide the sequence of directions . Let’s see how to build sequences without knowing the destination.
Avoiding an at most countable subset
Suppose that is at most countable and let be a sequence of real numbers such that . We want to find a sequence such that .
Assuming additionally that it has infinitely many terms above and infinitely many terms below , then we obtain a non-ultimately-constant sequence by defining if and only if (i.e. “move away from ”). This is because so there are always infinitely many terms in front of and behind Atalanta.
Incidentally, with trivial enumeration shows a simple counter-example with no term below and ultimately constant . In that case, and and for . But .
To workaround that issue, we can alternatively define the sequence if and only if and . This still moves away from all once, keeps oscillating and does not require additional assumption on .
Whatever the decision chosen, we can show that . Otherwise, consider one such that is defined by moving away from . Then either and or . But in any case, we would have which contradicts our strict inequality for not ultimately constant .
As explained in the previous blog, this shows that (or any complete subspace containing ) is uncountable. Otherwise, we could use a sequence enumerating it to arrive to a contradiction.
Similarly, because is countable then we can find a sequence such that , which gives us an irrational number . If instead is the set of algebraic numbers (which is countable and contains ) then we obtain a transcendental .
An explicit computation
The big difference between the case of and the set of algebraic numbers is that it’s much easier to actually compute a list of that lists all the . For example, a simple way to enumerate the fractions without trying to avoid duplicate values is, for each to enumerate the integers and bounded by in the lexicographical order. One can similarly enumerate for each the non-constant polynomial of degree at most and integer coefficient bounded by but it’s not obvious how to actually compute their roots.
One can rely on root finding algorithm to estimate the roots in order to be able to calculate the sign and so determine . But in theory, can be arbitrary close to so it’s not clear how much precision to request.
Instead, let’s consider an enumeration of the non-constant polynomial with integer cofficients and define if and only if . With that new formula, can be calculated very easily in from the cofficients of using Horner’s method.
For any integer , let’s consider . Then its product with its derivative is . Its value at any has the same sign as and if it just . For any , we can find large enough such that and have not been enumerated yet. So is not ultimately constant. Alternatively, we could have used the trick from the previous section to force that property.
Now let’s prove that is still algebraic. If that’s not the case, let such that . We can choose such that is of minimal degree and so . Since has only finitely many roots, there is such that at maximum distance around , is the only root of and does not vanish. Let’s large enough such that the polynomial has not been enumerated before . Let’s such that .
In the considered neighbourhood of , has only one root , has the same sign as and its derivative has the same nonzero constant sign as . Analyzing each combination positive/negative and greater/smaller than , we verify that is chosen such that which is obviously also true if . This agains contradict our strict inequality. Q.E.D.