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.