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.

A Zeno paradox to prove the reals are uncountable

A simple variant of Zeno’s paradoxes can be described as follows. Atalanta wishes to walk to the end of a path. When she gets halfway, she still have to walk the remaining half of the path ; When she gets halfway of that remaining half, she still needs to walk the remaining quarter of the path ; When she gets halfway of that remaining quarter, she still needs to walk the remaining eight of the path ; and so on. Hence it seems she will never reach the end of the path, which is paradoxical.

Obviously, this is not true: Atalanta is going to reach the end of the path after a certain amount of time. The issue in the previous reasoning is that (assuming she walks at constant velocity) walking these subpaths also takes her respectively half, a quarter, a eight, etc of the total time she actually needs to arrive to her destination… and the observations are only done for a total time that is less than the one needed.

A modern variant

Now suppose the ground is an infinite real line, itself covered by an infinite treadmill on which Atalanta is walking. This treadmill brings Atalanta in the opposite direction by twice her velocity. She can decide to turn the treadmill on or off, but its state must remain the same during the whole walk of a subpath. In the following schema, the treadmill was enabled when she was on the second subpath:

After the total duration considered in the previous problem, Atalanta has walked exactly the same total distance on the treadmill. The conveyor belt also moves by summing up distances that are twice the distances on subpaths. Because the treadmill can be on or off, the conveyor’s belt position is not following a simple linear function of the time. Let’s admit for a while it still converges to a certain distance when getting closer to the total duration, I will come back to this at the end of the blog post.

With respect to the ground, Atalanta’s position is basically given by her departure position, moved backward by the distance of the conveyor belt with respect to the ground and moved forward by the distance she walked on the treadmill. As a consequence of the previous paragraph, Atalanta is also converging to a destination with respect to the ground.

Modern Zeno’s paradox (with a flaw)

Now consider an enumeration of all the points of the real line. At the beginning the treadmill is off. Before walking the first half of the path, Atalanta picks the first point in that enumeration and enables the treadmill if she can see that point in front of her. Before walking the next quarter of the path, she picks the second point and enables or disables the treadmill according to whether she can see that second point in front of her. She continues that way for each subpath and each point of the real line.

When a given point is picked there are two options. Either it is not in front of her and so she will just walk forward to a certain distance ; or otherwise the the treamill will additionnaly take her backward by twice that distance. In any case, with respect to the ground, she is moving away from the picked point by the distance she walks during that subpath.

At some step, the point of the real line corresponding to Atalanta’s destination will be picked and she will move away from that destination by a certain distance. But the remaining subpaths are half, a quarter, a eight, etc that distance. To have a chance to converge to the destination again she must now always keep the same direction. But so far, only finitely many points have been picked and so there is at least one point beyond the destination that has not been chosen yet (actually infinitely many). This means she will have to change her direction at least once in the future and so will never be able to reach her destination!

Uncountability of the real line

How to solve the paradox in this modern variant?

First, let’s go back to why the distance of the conveyor belt with respect to the ground is convergent. Consider the binary number whose digits describe the sequences of states of the treadmill: 0 if turned off and 1 if turned on. Place the binary point after the first digit to obtain a real number. Then one can check that the distance of the conveyor belt is given by that real number multiplied by Atalanta’s total distance on the treadmill. Of course, one must admit that such a binary number with infinitely many digits after the binary point is well defined!

For a rigorous proof, note that the conveyor belt is always going in the same direction and at most twice Atalanta’s total walking distance on the treadmill. So the convergence of the conveyor belt just comes from the monotone convergence theorem. This assumption was correct.

However, reading more carefully the argumentation, we actually assumed that there is a countable enumeration of all the points of the real line. But Cantor proved at the end of the 19th century that this is wrong, the real line is uncountable!

It is interesting to actually turn this modern Zeno’s paradox into an apparently “elementary” alternative of Cantor’s diagonal argument, in a way that involves only concepts understandable by the Ancient Greeks and no advanced mathematical formalisms. In particular, this is not mentioning explicitly the positional notation invented by Indian mathematicians. As a comparison, Cantor’s proof assumes that a decimal notation with infinitely many digits after the decimal point is well defined (similar to what we used for our proof with binary numbers) ; or it must deal with the edge case of a real number with two different decimal notations (e.g. 0.4999999… = 0.5).

For completeness

Nevertheless, we still had to use some kind of completeness property in order to prove that the moving distance of the conveyor belt is convergent. Actually, Cauchy completeness is enough.

It is also interesting to note that all the moves as well as Atalanta’s total distance on the treadmill are rational numbers. Since the rational numbers are countable, this modern Zeno’s paradox can also be performed by considering only rational points on the ground. In that case, the flaw is then in the assumption that the conveyor belt converges to a rational point: the set of rational numbers is not complete.

More generally, we can also applie this modern Zeno’s paradox to any ordered field since they include a subset isomorphic to the rational numbers. The conclusion becomes that if the field is Cauchy-complete then it is uncountable.

S[α] for strings of ordinals

Update 2020/03/10: Added complexity analysis for S.substr(α, N)

In a previous blog post, I defined for each ordinal $\alpha$ a string $S_\alpha$ (made of the characters for the empty set, comma, opening brace and closing brace) that enumerates the element of $\alpha$. I gave a simple formulas to calculate the length $L_\alpha$ of this string.

My colleague Ioanna was a bit disappointed that I didn’t provide a script for calculating the infinite $S_\alpha$ strings. Obviously, the complexity would be “$\Omega\left(\omega\right)$” but it is still possible to evaluate the string at a given position: Given $\beta < L_\alpha$, what is the character of $S_\alpha$ at position $\beta$?

Since the initial segments of the strings are compatible, another way to express this is by introducing the class $S = \bigcup_\left\{\alpha \in \left\{\mathrm\left\{Ord\right\}\right\}\right\} S_\alpha$ corresponding to a giant string enumerating the class $\mathrm\left\{Ord\right\}$ of all ordinals. Given an ordinal $\alpha$, what is $S\left[\alpha\right]$?

A small generalization of this S.charAt(α) operation is S.substr(α, N) calculating the substring of length $N$ starting at $\alpha$.

Example

• $S_\left\{2\right\}$ is "∅,{∅}", so $S\left[0\right]$ is the character ∅, $S\left[1\right]$ is a comma, $S\left[2\right]$ is an opening brace and $S\left[4\right]$ is a closing brace.
• $S_\left\{\omega+1\right\}$ is made of of an $\omega$-concatenation of finite strings (the character ∅, a comma, $S_1$ surrounded by braces, a comma, $S_2$ surrounded by braces, a comma, $S_4$ surrounded by braces, a comma, etc), followed by a comma, an opening brace, the same $\omega$-concatenation of finite strings and finally a closing brace. So $S\left[\omega\right]$ is a comma, $S\left[\omega+1\right]$ is an opening brace, $S\left[\omega+2\right]$ is the character "∅" and $S\left[\omega2\right]$ is a closing brace.

In the previous example, we have basically analyzed the string $S_\left\{\alpha+1\right\}$ at a given successor ordinal, splitting it into two copies of $S_\alpha$, comma and braces. This suggests some easy values of $S$:

Lemma

For any $n < \omega$ and $\beta \geq 1$, $S\left[\alpha\right]$ is:

• A comma if $\alpha$ can be written $2^n - 3$ or $\omega^\beta 2^n + n$
• An opening brace if $\alpha$ can be written $2^n - 2$ or $\omega^\beta 2^n + n + 1$
• A closing brace if $\alpha$ can be written $2^\left\{n+1\right\} - 4$ or $\omega^\beta 2^\left\{n+1\right\} + n$

Proof: For any ordinal $\alpha$, by viewing the string $S_\left\{\alpha+1\right\}$ as a concatenation of $S_\alpha$, a comma, an opening fence, $S_\alpha$ and a closing fence, we deduce that:

• $\left\{S\left\left[L_\left\{\alpha\right\}\right\right]\right\}$ is a comma.
• $\left\{S\left\left[L_\left\{\alpha\right\} + 1 \right\right]\right\}$ is an opening brace.
• $L_\left\{\alpha+1\right\}$ is a successor ordinal and $\left\{S\left\left[L_\left\{\alpha+1\right\} - 1 \right\right]\right\}$ is a closing brace.

The lemma follows immediately from the calculation of string lengths performed in the previous blog post. □

Warning: The rest of the blog post gives the solution to this puzzle, so you might want to have fun solving it yourself first and then go back checking my proposed solution later 😉...

More generally, the proof of the lemma can be extended by saying that if we find $n$ such that $\left\{2^n - 1\right\} \leq \alpha \leq \left\{2^\left\{n+1\right\} - 5\right\}$ then $\delta = \left\{\alpha - \left\{\left(2^n - 1\right)\right\}\right\} \leq \left\{2^n - 4\right\}$ is the index of $\left\{S\left[\alpha\right]\right\}$ in the second substring $S_\alpha$ of $S_\left\{\alpha+1\right\}$ and so $\left\{S\left[\alpha\right]\right\} = \left\{S\left[\delta\right]\right\}$.

Details will be provided in the theorem below but one can already write a simple JavaScript recursive program to evalute $S$ at finite ordinals:

Script for $\alpha < \omega$

The character of $S$ at position $\alpha =$

is

The following intermediary step will be helpful to evaluate $S$ at infinite ordinal $\alpha$:

Proposition

Let $\alpha$ is infinite and $\beta = \log_\left\{\omega\right\}\left(\alpha\right) \geq 1$. Let $1 \leq q < \omega$ and $0 \leq \rho < \omega^\beta$ be the quotient and remainder of the euclidean division of $\alpha$ by $\omega^\beta$. Let’s define:

Then $S\left[\alpha\right]$ is:

• A comma if $\alpha = \left\{\omega^\left\{\beta\right\} 2^n + n\right\}$
• An opening brace if $\alpha = \left\{\omega^\left\{\beta\right\} 2^n + n + 1\right\}$
• An closing brace if $\alpha = \left\{\omega^\left\{\beta\right\} 2^\left\{n+1\right\} + n\right\}$
• $S\left[\delta\right]$ otherwise where $\delta$ is the unique ordinal such that $\alpha = \left\{\omega^\beta 2^n + n + 2 + \delta\right\}$ and $\delta < \left\{\omega^\left\{\beta\right\} 2^n + n\right\}$.

Proof: First by construction we have $\alpha = \left\{ \left\{\omega^\beta q \right\} + \rho\right\}$.

If the first case of the definition of $n$, $2^n \leq q < 2^\left\{n+1\right\}$ so we always have $\alpha < \left\{\omega^\beta \left\{\left(q+1\right)\right\}\right\} \leq \omega^\beta 2^\left\{n+1\right\} \leq L_\left\{\omega\left\{\beta\right\} + n + 1\right\}$. If additionnaly $q$ is not a power then $2^n < q$ and so $\alpha \geq \left\{\omega^\left\{\beta\right\}q\right\} \geq \left\{\omega^\left\{\beta\right\}\left\{\left(2^n+1\right)\right\}\right\} \geq L_\left\{\omega\left\{\beta\right\} + n\right\}$. Otherwise $q = 2^n$ and $n \leq \rho$ and so again $\alpha \geq L_\left\{\omega\left\{\beta\right\} + n\right\}$.

In the second case of the definition of $n$, $\left\lfloor \left\{\log_2\left(q\right)\right\} \right\rfloor \geq \rho + 1$ so $n \geq \rho \geq 0$. $q$ is a power of 2 and more precisely $q = 2^\left\{n+1\right\} > 2^n$ so we deduce the same way as in the previous case that $\alpha \geq L_\left\{\omega\left\{\beta\right\} + n\right\}$. Moreover, $\rho < n + 1$ so again $\alpha = \left\{\omega^\beta 2^\left\{n+1\right\} + \rho\right\} < L_\left\{\omega\left\{\beta\right\} + n + 1\right\}$.

We can thus view $S_\left\{\omega \beta + n + 1\right\}$ as a concatenation of $S_\left\{\omega \beta+n\right\}$, a comma, an opening brace, $S_\left\{\omega \beta+n\right\}$ and a closing brace. We assume that $\left\{ \left\{\omega^\left\{\beta\right\} \left\{2^n\right\}\right\} + n + 2\right\} \leq \alpha < \left\{\omega^\left\{\beta\right\} 2^\left\{n+1\right\} + n\right\}$ as the three other cases are handled by the lemma. Then $\delta$ is well-defined and is actually the index of $S\left[\alpha\right]$ in the second copy of $S_\left\{\omega \beta + n\right\}$ so $\left\{S\left[\alpha\right]\right\} = S\left\{\left[\delta\right]\right\}$. □

We are now ready to give a nice way to evaluate $S$ at any ordinal $\alpha$:

Theorem

$S\left[\alpha\right]$ can be calculated inductively as follows:

• If $\alpha = 0$, $S\left[\alpha\right]$ is the character "∅".
• If $0 < \alpha \leq \omega$ then $\right\rfloor\right\}\right\} - 3\right\} \leq \alpha \leq \right\rfloor + 1\right\}\right\} - 4\right\}$ and $S\left[\alpha\right]$ is equal to:
• A comma if $\alpha = \left\{2^\left\{\left\lfloor \left\{\log_2\left\{\left(\alpha+3\right)\right\}\right\} \right\rfloor\right\} - 3\right\}$
• An opening brace if $\alpha = \left\{2^\left\{\left\lfloor \left\{\log_2\left\{\left(\alpha+3\right)\right\}\right\} \right\rfloor\right\} - 2\right\}$
• A closing brace if $\alpha = \left\{2^\left\{\left\lfloor \left\{\log_2\left\{\left(\alpha+3\right)\right\}\right\} \right\rfloor + 1\right\}\right\} - 4$
• $S\left[\delta\right]$ otherwise where $\delta = \left\{\alpha - \left\left( 2^\left\{\left\lfloor \left\{\log_2\left\{\left(\alpha+3\right)\right\}\right\} \right\rfloor\right\} - 1 \right\right)\right\} \leq \left\{2^\left\{\left\lfloor \left\{\log_2\left\{\left(\alpha+3\right)\right\}\right\} \right\rfloor\right\} - 4\right\} \leq \alpha - 3$.
Moreover $\delta$ compares against $\alpha$ as follows: $\frac\left\{\delta\right\}\left\{\alpha\right\} \leq \frac\left\{1\right\}\left\{2\right\} + \frac\left\{1\right\}\left\{2^\left\{\left\lfloor \left\{\log_2\left\{\left(\alpha+3\right)\right\}\right\} \right\rfloor + 1\right\}\right\} \leq \frac\left\{3\right\}\left\{4\right\}$ and $\left\{\left\lfloor \left\{\log_2\left\{\left(\delta+3\right)\right\}\right\} \right\rfloor\right\} < \left\{\left\lfloor \left\{\log_2\left\{\left(\alpha+3\right)\right\}\right\} \right\rfloor\right\}$
• If $\alpha$ is infinite, let $0 < c_1 < \omega$ be the coefficient in its Cantor normal form corresponding to the smallest infinite term and $c_0 < \omega$ be finite term if there is one, or zero otherwise. Let $k$ be the exponent corresponding to the smallest nonzero term in the binary decomposition of $c_1$. Then $S\left[\alpha\right]$ is equal to:
• A closing brace if $c_0 \leq k - 1$.
• A comma if $c_0 = k$.
• An opening brace if $c_0 = k + 1$.
• $S\left[\left\{c_0 - \left\{\left(k+2\right)\right\}\right\}\right]$ if $c_0 \geq k + 2$.

Proof:

The case $\alpha = 0$ is clear. Suppose $0 < \alpha < \omega$ and let $l = \left\{\left\lfloor \left\{\log_2\left\{\left(\alpha+3\right)\right\}\right\} \right\rfloor\right\}$. By definition $2^l \leq \alpha + 3 < 2^\left\{l+1\right\}$ so $2^l - 3 \leq \alpha \leq 2^\left\{l+1\right\} - 4$. Let’s consider the case $2^l - 1 \leq \alpha \leq 2^\left\{l+1\right\} - 5$ as the three other cases are already known from the Lemma. $S_\left\{l+1\right\}$ is made of the concatenation of $S_l$, a comma and $S_l$ surrounded by braces. $\delta$ is actually the index of $S\left[\alpha\right]$ in the second copy of $S_l$ so $\left\{S\left[\alpha\right]\right\} = S\left\{\left[\delta\right]\right\}$. The first equality is straighforward:

$\delta = \left\{\alpha - \left\{\left(2^l -1\right)\right\}\right\} \leq \left\{2^\left\{l+1\right\} - 5 - \left\{\left(2^l -1\right)\right\}\right\} = \left\{2^l - 4\right\} = \left\{2^l - 1 - 3\right\}\leq \alpha - 3$

Morever we have:

$\frac\left\{\delta\right\}\left\{\alpha\right\} \leq \left\{1 - \frac\left\{2^l - 1\right\}\left\{2^\left\{l+1\right\}+5\right\}\right\} \leq \left\{1 - \frac\left\{2^l - 1\right\}\left\{2^\left\{l+1\right\}\right\}\right\} \leq \left\{\frac\left\{1\right\}\left\{2\right\} + \frac\left\{1\right\}\left\{2^\left\{l+1\right\}\right\}\right\}$

and so the second inequality follows from the fact that $l \geq 1$. Finally, the third inequality comes from:

$2^\left\{\left\lfloor \left\{\log_2\left\{\left(\delta+3\right)\right\}\right\} \right\rfloor\right\} \leq \left\{\delta + 3\right\} \leq \left\{2^l - 4 + 3\right\} < 2^l$

Let’s consider the case of an infinite $\alpha$. For some $N \geq 1$, $\beta_N > \beta_\left\{N-1\right\} > \dots > \beta_1 \geq 1$ and $c_0 < \omega$ and $0 < c_1, c_2, c_N < \omega$, we can write Cantor’s Normal form as:

$\alpha = \left\{ \omega^\left\{\beta_N\right\} c_N\right\} + \left\{ \omega^\left\{\beta_\left\{N-1\right\}\right\} c_\left\{N-1\right\} \right\} + \dots + \left\{ \omega^\left\{\beta_\left\{1\right\}\right\} c_\left\{1\right\} \right\} + c_0$

With the notation of the proposition, we have $\beta = \beta_N$, $q = c_N$ and

$\rho = \left\{ \omega^\left\{\beta_\left\{N-1\right\}\right\} c_\left\{N-1\right\} \right\} + \dots + \left\{ \omega^\left\{\beta_\left\{1\right\}\right\} c_\left\{1\right\} \right\} + c_0$

If $N \geq 2$, then $\rho$ is infinite and so $n = \left\lfloor \left\{\log_2\left(q\right)\right\} \right\rfloor$ and we are in the fouth bullet of the proposition. Moreover $q \geq 2^n$ and we can write:

$\alpha = \left\{ \omega^\left\{\beta\right\} 2^n\right\} + \left\{\omega^\left\{\beta\right\} \left\left(q-2^n\right\right)\right\} + \rho = \left\{ \omega^\left\{\beta\right\} 2^n\right\} + n + 2 + \delta$

where $\delta = \left\{\omega^\left\{\beta\right\} \left\left(q-2^n\right\right)\right\} + \rho$ is infinite and so cancels out the $n + 2$ term. It follows that $S\left\{\left[\alpha\right]\right\} = S\left\left[ \left\{\omega^\left\{\beta\right\} \left\left(q-2^n\right\right)\right\} + \rho \right\right]$. Essentially, we have just removed from $c_\left\{N\right\}$ its term of highest exponent in its binary decomposition!

By repeated application of the theorem, we can remove each binary digit of the $c_i$ for $i$ going from $N$ to $2$. When then arrive at $i = 1$:

$\left\{S\left[\alpha\right]\right\} = S\left\left[ \omega^\left\{\beta_1\right\} c_1 + c_0\right\right]$

With the notation of the proposition, we now have $\beta = \beta_1$, $q = c_1$ and $\rho = c_0$. If the binary decomposition of $c_1$ has more than one nonzero digit then so $q$ is not a power of 2. So although $\rho$ is now finite, we are still in the first case of the proposition and $\delta$ remains infinite. So we can remove all but the last digit of $c_1$ by repeated application of the proposition:

$\left\{S\left[\alpha\right]\right\} = S\left\left[ \omega^\left\{\beta_1\right\} 2^k + c_0\right\right]$

where $k$ is the exponent corresponding to the smallest nonzero term in the binary decomposition of $c_1$.

Using the lemma, $S\left[\alpha\right]$ is a comma if $k = c_0$, an opening brace if $k = c_0 - 1$ and a closing brace if $k = c_0 + 1$.

If $k \leq c_0 - 2$ then $k = \left\lfloor \left\{\log_2\left(2^k\right)\right\} \right\rfloor \leq c_0$ and writing

$\left\{\omega^\left\{\beta_1\right\} 2^k + c_0\right\} = \omega^\left\{\beta_1\right\} 2^k + k + 2 + \left\left(c_0 - \left\{\left(k + 2\right)\right\}\right\right)$

we deduce from the proposition that $\left\{S\left[\alpha\right]\right\} = \left\{S\left[\left\{c_0 - \left\{\left(k+2\right)\right\}\right\}\right]\right\}$.

Finally, if $k \geq c_0 + 2$ then $k = \left\lfloor \left\{\log_2\left(2^k\right)\right\} \right\rfloor > c_0$ and writing

$\left\{\omega^\left\{\beta_1\right\} 2^k + c_0\right\} = \left\{\omega^\left\{\beta_1\right\} 2^\left\{k-1\right\}\right\} + k - 1 + 2 + \left\{\omega^\left\{\beta_1\right\} 2^\left\{k-1\right\}\right\} + c_0$

we deduce from the proposition that

$\left\{S\left[\alpha\right]\right\} = S\left\left[ \omega^\left\{\beta_1\right\} 2^\left\{k-1\right\} + c_0\right\right]$

We have essentially decremented $k$ and we can repeat this until we reach the case $k = c_0 + 1$ for which we already said that the character is a closing brace. □

As an application of this theorem, here is a few simple exercises:

Exercise 1

1. $S\left\left[2^72 + 2\right\right]$ is an empty set.
2. $S\left\left[\omega^72\right\right]$ is a comma.
3. $S\left\left[\omega^72 72 + 72\right\right]$ is a closing brace.
4. $S\left\left[\omega^72 72 + \omega^42 42 + 12\right\right]$ is an opening brace.

Exercise 2

The evaluation of $S$ at

Corollary 1: Time complexity

Let $\alpha$ be an ordinal. Let $c_1 < \omega$ be the coefficient in its Cantor normal form corresponding to the smallest infinite term if there is one, or zero otherwise. Let $c_0 < \omega$ be its finite term if there is one, or zero otherwise. Then $S\left[\alpha\right]$ can be evaluated in:

• $O\left\left( \log_2\left\{\left(c_0+2\right)\right\}^2 + \log_2\left\{\left(c_1+2\right)\right\} \right\right)$ elementary arithmetic operations and comparisons on integers.
• $O\left\left( \log_2\left\{\left(c_0+2\right)\right\}\right\right)$ elementary operations if integers are represented in binary and leading/trailing zero counting and bit shifts are elementary operations.

Proof: First note that the “+ 2” is just to workaround for the edge cases $c_0 = 0$ or $c_1 = 0$.

For the infinite case $c_1 > 0$ we need to calculate $k$ that is performing the find first set. A naive implementation can be done in $O\left(\log_2\left\{\left(c_1+2\right)\right\}\right)$ steps by browsing the digits of $c_1$ to find the first nonzero for example by calculating the remainder modulo increasing power of 2. Each iteration requires only $O\left(1\right)$ elementary integer operations %, * and comparisons. Then returning the result of moving to the finite case requires $O\left(1\right)$ integer operations +, − and comparisons.

For the finite case $c_1 = 0$ and $\alpha = c_0$, first notice that we only require $O\left\left( \log_2\left\{\left(c_0+2\right)\right\}\right\right)$ recursive calls given the inequality:

$\left\{\left\lfloor \left\{\log_2\left\{\left(\delta+3\right)\right\}\right\} \right\rfloor\right\} < \left\{\left\lfloor \left\{\log_2\left\{\left(\alpha+3\right)\right\}\right\} \right\rfloor\right\}$

The case $\alpha = 0$ only requires one comparison. For the case $\alpha > 0$, we need to calculate $l = \left\{\left\lfloor \left\{\log_2\left\{\left(\alpha+3\right)\right\}\right\} \right\rfloor\right\}$ which is integer rounding of the binary logarithm or even just $2^l$. As above, we can provide a naive implementation by calculating the quotient modulo increasing power of 2 in $O\left(l\right)$ comparisons and elementary integer operations /, *. Then returning the result of moving to a $\delta < \alpha$ requires only $O\left(1\right)$ integer operations and comparisons. In total, complexity is $O\left\left( \log_2\left\{\left(c_0+2\right)\right\}^2\right\right)$.

Finally, this can be simplified if one calculates $k$ and $l$ by a simple leading/trailing zero counting (or similar) and $2^l$ by a bit shift. □

Script based on Cantor normal form

If the coefficients of Cantor normal form of $\alpha$ corresponding the smallest infinite term and finite term are
$c_1$ =
$c_0$ =
Then the character of $S$ at position $\alpha$ is

Once we have an algorithm for S.charAt(α), it is easy to get an algorithm of $N$ times that complexity for S.substr(α, N) calculating the substring of length $N$ starting at position $\alpha$ by repeated calls to S.charAt(α). Let’s analyze a bit more carefully how we can make this recursive and more efficient:

Corollary 2: Algorithm for S.substr(α, N)

Let $\alpha$ be an ordinal and $N < \omega$. Then S.substr(α, N) can be calculated as follows:

• If $N = 0$ then it is the empty string.
• If $\alpha = 0$ and $N = 1$ then it is the character "∅".
• If $0 < \alpha < \omega$, let $l = \left\lfloor \left\{\log_2\left\{\left(\alpha+N+2\right)\right\}\right\} \right\rfloor$. We have $2^l-3 \leq \left\{\alpha + N - 1\right\} \leq 2^\left\{l+1\right\} - 4$ and the result is obtained by concatenating the following strings:
1. If $\alpha \leq 2^l - 4$, the substring at offset $\alpha$ and length $2^l - 3 - \alpha$.
2. If $\alpha \leq \left\{2^l - 3\right\}$, a comma.
3. If $\alpha \leq \left\{2^l - 2\right\} \leq \left\{\alpha + N - 1\right\}$, an opening brace.
4. If $\left\{\alpha + N - 1\right\} \geq \left\{2^l - 1\right\}$, the substring at offset $\delta = \mathrm\left\{max\right\}\left\{\left(0, \alpha - \left\{\left(2^l - 1\right)\right\}\right)\right\}$ and length $1 + \mathrm\left\{min\right\}\left\{\left(\left\{\alpha + N - 1\right\}, \left\{2^\left\{l+1\right\} - 5\right\}\right)\right\} - \mathrm\left\{max\right\}\left\{\left(\alpha, \left\{\left(2^l - 1\right)\right\}\right)\right\}$.
5. If $\left\{\alpha + N - 1\right\} = \left\{2^\left\{l+1\right\} - 4\right\}$, a closing brace.
• If $\alpha$ is infinite, let $0 < c_1 < \omega$ be the coefficient in its Cantor normal form corresponding to the smallest infinite term and $c_0 < \omega$ be finite term if there is one, or zero otherwise. Let $k$ be the exponent corresponding to the smallest nonzero term in the binary decomposition of $c_1$. Then the result is obtained by a concatenating the following strings:
1. If $c_0 \leq k - 1$, $\left\{\mathrm\left\{min\right\}\left\{\left(N, k - c_0\right)\right\}\right\}$ closing braces.
2. If $c_0 \leq k \leq c_0 + N - 1$, a comma.
3. If $c_0 \leq k + 1 \leq c_0 + N - 1$, an opening brace.
4. If $c_0 + N - 1 \geq k + 2$, the substring at offset $\delta = \mathrm\left\{max\right\}\left\{\left(\left\{0, \left\{c_0 - \left\{\left(k + 2\right)\right\}\right\}\right\}\right)\right\}$ and length $c_0 + N - \left\{\mathrm\left\{max\right\}\left\{\left(c_0, k + 2\right)\right\}\right\}$.

Moreover, this only adds $O\left(N\right)$ compared to the complexity of evaluating to a single offset.

Proof: The algorithm is just direct application of the Theorem. For the case where $\alpha \geq \omega$, the only change is that we add at most $N$ characters before moving to the finite case. The case $\alpha < \omega$ is essentially a divide-and-conquer algorithm and we have a relation of the form:

$\left\{T\left(L\right)\right\} = 2\left\{T\left\left(\frac\left\{L\right\}\left\{2\right\}\right\right)\right\} + \left\{f\left(L\right)\right\}$

where $L = 2^l = \left\{\Theta\left\{\left(\alpha + N\right)\right\}\right\}$ and $f\left\{\left(L\right)\right\}$ is $O\left(1\right)$ or $O\left(\log_2\left\{L\right\}\right)$ depending on available operations, but in any case $O\left\{\left(\sqrt\left\{L\right\}\right)\right\}$. So from the master theorem, $\left\{T\left\{\left(L\right)\right\}\right\} = \left\{O\left(L\right)\right\} = \left\{O\left(\alpha+N\right)\right\}$. In general, this bound is not as good as repeating $N$ calls to S.charAt!

However, we note that if we assume that $\alpha > N - 4$ then $\left\{\alpha + 2 + N\right\} < \left\{2\left\{\left(\alpha+3\right)\right\}\right\}$ and so

$\log_2\left\left(\alpha + 2 + N\right\right) < \left\{1 + \log_2\left\{\left(\alpha+3\right)\right\}\right\}$

We can easily discard the edge case where these start/end offsets point to a brace surrounding the right substring of the iterative step and so we get:

$\left\lfloor \left\{\log_2\left\{\left(\alpha+N+2\right)\right\}\right\} \right\rfloor = \left\lfloor \left\{\log_2\left\{\left(\alpha+3\right)\right\}\right\} \right\rfloor$

which means that the left substring is just empty and so the complexity is not changed compared to S.charAt. Finally, when $\alpha \leq N - 4$ the previous bound tells us that the steps are done in $O\left(N\right)$. □

Script for S.substr(α, N)

If the coefficients of Cantor normal form of $\alpha$ corresponding the smallest infinite term and finite term are
$c_1$ =
$c_0$ =
Then the character of $S$ substring of length $N$ =
and offset $\alpha$ is

Ordinals as strings of ∅, commas and braces

This week, my colleagues at Igalia were talking about cutting text at a 72-characters limit for word-wrapping emails. One might say that the real question is whether 72 is a cut or a limit. Or wonder how one has decided to set that particular value?

The latter link explains the recursive definition of 72 as a finite set, which can be written with only braces, commas and the empty set $\empty$:

$0 = \left\{\\left\{\\right\}\right\} = \empty$ $1 = 0 \union \left\{\\left\{0\\right\}\right\} = \left\{\\left\{0\\right\}\right\} = \left\{\\left\{\empty\\right\}\right\}$ $2 = 1 \union \left\{\\left\{1\\right\}\right\} = \left\{\\left\{0,1\\right\}\right\} = \left\{\\left\{ \empty, \left\{\\left\{\empty\\right\}\right\} \\right\}\right\}$ $3 = 2 \union \left\{\\left\{2\\right\}\right\} = \left\{\\left\{0,1,2\\right\}\right\} = \left\{\\left\{ \empty, \left\{\\left\{\empty\\right\}\right\}, \left\{\\left\{ \empty, \left\{\\left\{\empty\\right\}\right\} \\right\}\right\} \\right\}\right\}$

and so forth until

$72 = 71 \union \left\{\\left\{71\\right\}\right\} = \left\{\\left\{0,1,2,\dots,71\\right\}\right\} = \dots$

You can notice that $1$ has only one element $\varnothing$ and for any $n \geq 1$, in order to enumerate the elements of $n+1$ using only the four characters "∅", ",", "{" and "}", you first write the elements of $n$, followed by a comma, followed by an opening brace, followed by the elements of $n$ and finally followed by a closing brace. One can write a simple JavaScript loop that initializes a variable string = "∅" and performs the concatenation string += ,{\${string}} at each step:

The elements of are

Length of the string

You notice that the length of the string obtained for $n=6$ already exceeds the 72-character limit. From the previous recursive construction of the string one can deduce a recursive definition of its length:

$L_1 = 1$ $L_\left\{n+1\right\} = L_n + 2 + L_n + 1 = 2L_n +3$

It is easy to see that $L_n = \left\{\Omega\left\{\left(2^n\right)\right\}\right\}$ so although the simple JavaScript loop above uses a time complexity of $\left\{O\left\{\left(n\right)\right\}\right\}$ string concatenations, the space complexity is at least exponential. That’s why in the definition of 72 above I used dots instead of showing the whole string!

One can however easily modify the previous JavaScript loop to calculate the length of such a string. At Igalia, we have been working on a new native type called BigInt which is particularly useful to accurately calculate large integers. The case $n = 72$ demonstrates why it is more appropriate than JavaScript Number:

The length of the strings enumerating the elements of has the following length (first field uses Number, second field uses BigInt):

One can do better and try to calculate an explicit formula for $L_n$ for any $n \geq 1$. Since for all $i \geq 1$, $L_\left\{i+2\right\} - L_\left\{i+1\right\} = 2\left\left(L_\left\{i+1\right\} - L_i\right\right)$ the sequence $\left\left(L_\left\{i+1\right\} - L_i\right\right)_\left\{i \geq 1\right\}$ is a geometric sequence with common ratio 2 and for all $i \geq 1$ we can write

$\left\{L_\left\{i+1\right\} - L_\left\{i\right\}\right\} = \left\{2^\left\{i-1\right\} \left\left( L_2 - L_1 \right\right)\right\}$

Summing this up for $1 \leq i \leq n - 1$:

$L_n - L_1 = \left\{\sum_\left\{i=1\right\}^\left\{n-1\right\} L_\left\{i+1\right\} - L_\left\{i\right\}\right\} = \left\{\left\left( L_2 - L_1 \right\right) \left\left(\sum_\left\{i=0\right\}^\left\{n-2\right\} 2^i \right\right)\right\}= \left\{ \left\{\left\left( L_2 - L_1 \right\right)\right\} \left\{\left\left(2^\left\{n-1\right\}-1\right\right)\right\} \right\}$

Finally, given that $L_1 = 1$ and $L_2 = 2L_1 + 3 = 5$, one can write for all $n \geq 1$:

$L_n = \left(2^\left\{n-1\right\}-1\right) \left(5-1\right) + 1 = 2^\left\{n+1\right\} - 3$

This formula can be used to calculate $L_n$ using built-in JavaScript exponentation instead of a loop, as done below.

The length of the strings enumerating the elements of has the following length (first field uses Number, second field uses BigInt):

Order-type of infinite strings

It is possible to generalize this problem to infinite ordinal numbers. The string $S_\left\{\alpha\right\}$ and its length $L_\alpha$ are defined by induction for any ordinal $\alpha$. $S_0$ is the empty string $L_0 = 0$. $S_1$ is the string with one character "∅" and $L_1 = 1$. For $\alpha \geq 1$, $S_\left\{\alpha+1\right\}$ is the string obtained by concatenating the string $S_\alpha$, a comma character ",", an opening brace character "{", the string $S_\alpha$ and finally a closing brace character "}". It is of length $L_\left\{\alpha+1\right\} = L_\alpha + 2 + L_\alpha + 1$. Beware that ordinal operations are not commutative so this cannot be simplified a priori!

For any limit ordinal $\lambda$, the string $S_\lambda$ is obtained by taking the union of the $L_\alpha$-sequence $S_\alpha$ for $\alpha < \lambda$. This is still a well-defined sequence since these strings always agree on the character at a given index. $S_\lambda$ is of length $L_\lambda = \sup_\left\{\alpha < \lambda\right\} L_\alpha$.

By construction, $L_\alpha$ is an increasing sequence of ordinals and so $L_\alpha \geq \alpha$. Can we calculate it more explicitly?

Warning: The rest of the blog post gives the solution to this puzzle, so you might want to have fun solving it yourself first and then go back checking my proposed solution later 😉...

Let’s consider some examples. In the case $\omega = \mathbb N$, the string $S_\omega$ can be more easily seen as the $\omega$-concatenation of finite strings: the empty set, a comma, $S_1$ surrounded by braces, a comma, $S_2$ surrounded by braces, a comma, $S_3$ surrounded by braces, a comma, etc So clearly $L_\left\{\omega\right\} = \omega$ and this aligns with the definition for limit ordinal.

In order to write $S_\left\{\omega+1\right\}$, you first write the elements of $\omega$, followed by a comma, followed by an opening brace, followed by the elements of $\omega$ and finally followed by a closing brace. So really this is an $\omega + \omega + 1$ sequence. This aligns with the definition in the successor ordinal case, using the fact that $k + \omega = \omega$ for any $k < \omega$:

$L_\left\{\omega+1\right\} = L_\omega + 2 + L_\omega + 1 = \omega + 2 + \omega + 1 = \omega2 + 1$

Continuing for other successor ordinals, one can write

$L_\left\{\omega+2\right\} = L_\left\{\omega+1\right\} + 2 + L_\left\{\omega+1\right\} + 1 = \omega2 + 1 + 2 + \omega2 + 1 + 1 = \omega4 + 2$ $L_\left\{\omega+3\right\} = L_\left\{\omega+2\right\} + 2 + L_\left\{\omega+2\right\} + 1 = \omega4 + 1 + 2 + \omega4 + 2 + 1 = \omega8 + 3$

and more generally for all $n < \omega$:

$L_\left\{\omega+n\right\} = \omega\left\{2^n\right\} + n$

To calculate $S_\left\{\omega2\right\}$, one takes the union for $n < \omega$ of the $L_\left\{\omega+n\right\}$-sequence of characters describing $\omega+n$. Its length is

$L_\left\{\omega2\right\} = \left\{\sup_\left\{n < \omega\right\} \left\left(\omega\left\{2^n\right\} + n\right\right)\right\} = \omega^2$

Then the exact same calculation as above leads for all $n < \omega$ to

$L_\left\{\omega2+n\right\} = \omega^2\left\{2^n\right\} + n$

Continuing this kind of calculations for larger values $\omega3, \omega4, \dots, \omega^2$ suggests the following conjecture: For every infinite ordinal $\alpha$, the order-type of the sequence describing its element is:

$L_\left\{\alpha\right\} = L_\left\{\omega \beta + n\right\} = \omega^\beta 2^n + n$

where $\beta \geq 1$ and $n < \omega$ are the quotient and remainder of the euclidean division of $\alpha$ by $\omega$.

Let’s sketch the proof by induction on $\beta$. We already explained the case $\beta = 1$ in the example above. Similarly, for a given $\beta \geq 1$, it is enough to prove the case $n = 0$, the formula for $n > 0$ follows, using the property $\forall k < \omega, k + \omega^\beta = \omega^\beta$ and the calculations we gave for the case $\beta = 1$.

If the formula holds for some $\beta \geq 1$ then because $\omega\left\{\left(\beta + 1\right)\right\}$ is limit and the lengths are increasing, the formula holds for $\beta + 1$:

$L_\left\{\omega \left\{\left(\beta + 1\right)\right\}\right\} = L_\left\{\omega\beta + \omega\right\} = \left\{\sup_\left\{n < \omega\right\} L_\left\{\omega \beta + n\right\}\right\} = \left\{\sup_\left\{n < \omega\right\} \left\{\left(\omega^\beta 2^n + n\right)\right\} \right\} = \omega^\left\{\beta+1\right\}$

Finally, if the formula holds for all $\beta$ below a limit ordinal $\lambda$ then because the lengths are increasing the formula holds for $\lambda$ too:

$L_\left\{\omega \lambda\right\} = \left\{\sup_\left\{\beta < \lambda\right\} L_\left\{\omega \beta\right\}\right\} = \left\{\sup_\left\{\beta < \lambda\right\} \omega^\left\{\beta\right\}\right\} = \omega^\left\{\lambda\right\}$

Q.E.D.

Sorry, no JavaScript program to calculate these infinite strings 😇...

Review of my year 2019 at Igalia

Co-owner and mentorship

In 2016, I was among the new software engineers who joined Igalia. Three years later I applied to become co-owner of the company and the legal paperwork was completed in April. As my colleague Andy explained on his blog, this does not change a lot of things in practice because most of the decisions are taken within the assembly. However, I’m still very happy and proud of having achieved this step 😄

One of my new duty has been to be the “mentor” of Miyoung Shin since February and to help with her integration at Igalia. Shin has been instrumental in Igalia’s project to improve Chromium’s Code Health with an impressive number of ~500 commits. You can watch the video of her BlinkOn lightning talk on YouTube. In addition to her excellent technical contribution she has also invested her energy in company’s life, helping with the organization of social activities during our summits, something which has really been appreciated by her colleagues. I’m really glad that she has recently entered the assembly and will be able to take a more active role in the company’s decisions!

Working with new colleagues

Igalia also hired Cathie Chen last December and I’ve gotten the chance to work with her as part of our Web Platform collaboration with AMP. Cathie has been very productive and we have been able to push forward several features, mostly related to scrolling. Additionally, she implemented ResizeObserver in WebKit, which is a quite exciting new feature for web developers!

The other project I’ve been contributed to this year is MathML. We are introducing new math and font concepts into Chromium’s new layout engine, so the project is both technically challenging and fascinating. For this project, I was able to rely on Rob’s excellent development skills to complete this year’s implementation roadmap on our Chromium branch and start upstreaming patches.

In addition, a lot of extra non-implementation effort has been done which led to consensus between browser implementers, MathML enthusiasts and other web developer groups. Brian Kardell became a developer advocate for Igalia in March and has been very helpful talking to different people, explaining our project and introducing ideas from the Extensible Web, HTML or CSS Communities. I strongly recommend his recent Igalia chat and lightning talk for a good explanation of what we have been doing this year.

Conferences

These are the developer conferences I attended this year and gave talks about our MathML project:

As usual it was nice to meet the web platform and chromium communities during these events and to hear about the great projects happening. I’m also super excited that the assembly decided to try something new for my favorite event. Indeed, next year we will organize the Web Engines Hackfest in May to avoid conflicts with other browser events but more importantly, we will move to a bigger venue so that we can welcome more people. I’m really looking forward to seeing how things go!

Paris - A Coruña by train

Environmental protection is an important topic discussed in our cooperative. This year, I’ve tried to reduce my carbon footprint when traveling to Igalia’s headquarters by using train instead of plane. Obviously the latter is faster but the former is much more confortable and has less security constraints. It is possible to use high-speed train from Paris to Barcelona and then a Trenhotel to avoid a hotel night. For a quantitative comparison, let’s consider this table, based on my personal travel experience:

Traject Transport Duration Price CO2/passenger
Paris - Barcelona TGV ~6h30 60-90€ 6kg
Barcelona - A Coruña Trenhotel ~15h 40-60€ Unspecified
Paris - A Coruña