Programme

• Jean-Paul Allouche, 13:30 – 14:15

• Clemens Kupke, 14:30 – 15:15

• Joost Winter, 15:30 – 16:15

Unexpected values for infinite series and products

Jean-Paul Allouche ¹

I have always been fascinated by closed-form expressions for infinite series or products of real numbers. In particular because closed form expressions are often quite unexpected. The most famous examples are probably the Euler solution of the Basel (or Mengoli) problem and the Wallis infinite product (discovered about 80 years before Euler’s result), namely $\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \cdots = \frac{\pi^2}{6}$ and $\frac{\pi}{2} = \frac{2}{1} \times \frac{2}{3} \times \frac{4}{3} \times \frac{4}{5} \times \frac{6}{5} \times \frac{6}{7} \times \frac{8}{7} \times \frac{8}{9} \times \cdots = \prod_{n=1}^{\infty} \frac{(2n)(2n)}{(2n-1)(2n+1)}$. In both case, how could we guess that $\pi$, the area of a circle of radius 1, would occur? We propose here to describe several families of unexpected closed-forms for infinite series or products related to “digit-sequences”, in particular automatic sequences.

Here are two emblematic examples.

• Let $(u(n))_{n \geq 0}$ be the Thue-Morse sequence, i.e., $u(n) = (-1)^{s_2(n)}$ where $s_2(n)$ is the sum of the binary digits of the integer $n$. Look at the two sequences (the first one is the Wood-Robbins product, the second one is related to the Flajolet-Martin constant)

  $${\scriptstyle \frac{1}{2}}, \quad \frac{\ \scriptstyle \frac{1}{2}\ }{\ \scriptstyle \frac{3}{4}\ }, \quad \frac{\ \ \frac{\ \scriptstyle \frac{1}{2}\ }{\ \scriptstyle \frac{3}{4}\ } \ \ } {\frac{\ \scriptstyle \frac{5}{6}\ }{\ \scriptstyle \frac{7}{8}\ }} \quad \dotsm \quad \text{and} \quad {\scriptstyle \frac{2}{3}}, \ \ \ \frac{\ \scriptstyle \frac{2}{3}\ }{\ \scriptstyle \frac{4}{5}\ }, \ \ \ \frac{\ \ \frac{\ \scriptstyle \frac{2}{3}\ }{\ \scriptstyle \frac{4}{5}\ } \ \ } {\frac{\ \scriptstyle \frac{6}{7}\ }{\ \scriptstyle \frac{8}{9}\ }} \quad \dotsm$$

  Their limits can also be written respectively

  $$\left(\frac{1}{2}\right)^{u(0)} \left(\frac{3}{4}\right)^{u(1)} \left(\frac{5}{6}\right)^{u(2)} \left(\frac{7}{8}\right)^{u(3)} \dotsm = \prod_{n \geq 0} \left(\frac{2n+1}{2n+2}\right)^{u(n)} \\$$

  and

  $$\left(\frac{2}{3}\right)^{u(1)} \left(\frac{4}{5}\right)^{u(2)} \left(\frac{6}{7}\right)^{u(3)} \left(\frac{8}{9}\right)^{u(4)} \dotsm = \prod_{n \geq 1} \left(\frac{2n}{2n+1}\right)^{u(n)}.$$

  What is known about these two infinite products is that

  $$\prod_{n \geq 0} \left(\frac{2n+1}{2n+2}\right)^{u(n)} = \frac{\sqrt{2}}{2}$$

  while no closed form expression is known for

  $$\prod_{n \geq 1} \left(\frac{2n}{2n+1}\right)^{u(n)}.$$

• Let $(v(n))_{n \geq 0}$ be the (regular) paper-folding sequence. For this sequence we have that

  $$\prod_{n \geq 1} \left(\frac{2n}{2n+1}\right)^{v(n)} = \frac{\Gamma(1/4)^2}{8\sqrt{2 \pi}}$$

  while no closed form expression is known for

  $$\prod_{n \geq 0} \left(\frac{2n+1}{2n+2}\right)^{v(n)}.$$

Differential Equations for streams and other coinductive types

Clemens Kupke ²

Simple stream differential equations (SDEs) define infinite streams by specifying the first element (“head”) of a stream, and its derivative (“tail”). A basic example is provided by the equations ones(0) = 1 and ones’ = ones that uniquely define the stream that consists of 1’s only.

In my talk, I will first recall several syntactic formats that guarantee that SDEs have unique solutions. After that, I will demonstrate that the expressiveness of a given format crucially depends on the choice of stream derivative(s). As an illustration of this phenomenon I am going to compare several “non-standard” choices for stream derivatives. One such choice leads to a simple coalgebraic characterisation of automatic sequences.

Finally, I plan to discuss behavioural differential equations that can be used for the specification of other coinductive datatypes such as trees and bi-infinite streams.

Classes of streams: from theory to Haskell

Joost Winter ³

In this talk, we discuss how the coalgebraic view on automata makes it possible to implement a variety of theoretical constructions directly in the programming language Haskell. First, we observe (as shown in my dissertation) that a variety of classes of streams (rational, algebraic, k-automatic, k-rational) can directly be translated into Haskell-code. Here, Haskell’s Num type can be regarded as being in analogy with the algebraic concept of a ring (or semiring).

We next illustrate this general idea with a number of cases of results or constructions, highlighting the analogies between theory and Haskell code. As an example, we present an implementation of the result by Chomsky and Schützenberger, yielding a Haskell function taking a grammar in Greibach normal form as input, and outputting a stream giving its counting function.

Secondly, we take a look at a generalization of the k-regular sequences, relating to the algebraic power series in the same way the k-regular sequences relate to the rational power series, yielding a notion of k-algebraic sequences (related to, but distinct from, the notion of k-context free sequences known in the literature). Here again, coinductive specification formats in Haskell are easily derived from the definition, most notably including a “k-ary” variant on Brzozowski’s product rule.