Paperfolding, Automata, and Rational Functions
Alf van der Poorten
Macquarie
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.