Paperfolding, Automata, and Rational Functions

Alf van der Poorten

The act of folding a sheet of paper in half, and iterating the operation, places in that sheet a sequence of creases appearing as valleys or ridges. Coding these as $1$ and $0$ respectively yields a sequence $(f_h)$, the paper folding sequence, with generating function $f(X)=\sum_{h\ge1}f_hX^h$, the paperfolding function. It turns out to be easy to notice that $f(X)$ satisfies a functional equation of a kind first studied by Mahler nearly seventy years ago. Moreover, viewed as defined over $\mathbb F_2$, the field of two elements, the paperfolding function is algebraic --- it satisfies a polynomial equation over $\mathbb F_2(X)$. It's also easy to see that the paperfolding sequence is `automatic'; it is generated by binary substitutions. These phenomena are not unique to paperfolding. They are shared by the good reductions modulo a prime $p$ of arbitrary diagonals of arbitrary rationals functions in many variables, equivalently by the reductions of a wide class of series in one variable satisfying linear differential equations with polynomial coefficients. I will tell some of these stories and will show some relevant pictures from Michael Crichton's novel {\it Jurassic Park\/}. Audience members should bring note paper along, not to write on, of course, but to fold.