On some famous sequences

Sergey Kitaev

Monday, February 9, 2004
1:00 pm, 845 Patterson Office Tower

Abstract:

The Arshon sequence was given in 1937 in connection with the problem of constructing a square-free sequence on a given alphabet, that is, a sequence that does not contain any subword of the type XX, where X is any non-empty word over the alphabet. The question of the existence of such a sequence, as well as the question of the existence of sequences avoiding other kinds of repetitions, were studied in algebra, discrete analysis, and in dynamical systems.

The Dragon curve (the paperfolding sequence) was discovered by physicist John Heighway and was described by Martin Gardner in 1978. It is defined as follows: we fold a sheet of paper in half, then fold in half again, and again, etc. and then unfold in such way that each crease created by the folding process is opened out into a 90-degree angle. The "curve" refers to the shape of the partially unfolded paper as seen edge on. It turns out that the Dragon curve is related to the sigma-sequence that was used by Evdokimov in 1968 in order to construct chains of maximal length in the n-dimensional unit cube.

The Peano curve was studied by the Italian mathematician Giuseppe Peano in 1890 as an example of a continuous space filling curve. The Peano infinite word is a discrete analog of the Peano curve.

Are there any similarities between the Arshon sequence, the Dragon curve, and the Peano infinite word in terms of combinatorics on words? In this talk, I will answer this question using some recent results.