CECM Colloquium

**Wednesday February 20, 2002
in K9509, SFU
**

3:30 - 4:20

Dr Alf van der Poorten

Centre for Number Theory Research, Macquarie University, Sydney, Australia

**Title:**
"Paperfolding, automata, and rational functions"

**Abstract:**
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 the hardcover edition of * Jurassic
Park*. Audience members should bring note paper along, not
necessarily to write on, but to fold.