title: A decoding problem in dynamics and in number theory.
abstract: Given a homeomorphism f of the circle, any splitting of this circle in two semiopen arcs induces a coding process for the orbits of f, which can be determined by recording the successive arcs visited by the orbit. The problem of describing these codes has a two hundred year history (that we briefly recall) in the particular case when the arcs are limited by a point and its image; in modern language, it is the kneading theory of such maps, and as such is relevant for our understanding of dynamical problems involving oscillations. This paper deals with questions attached to the general case, a problem considered by many mathematicians in the 50's and 60's in the case where f is a rotation, and which has recently found some applications in physiology. We show that, except for trivial cases, any code determines the rotation number, up to the orientation, of the homeomorphism which generates it. In the case the code is periodic, we can also determine whether or not it can be generated in this way. An equivalent problem in arithmetic consists of finding +/-p, knowing a collection of classes in Z/qZ of the form {m,m+p,.,m+(k-1)p}, where 2</=k</=q-2 and p and q are relatively prime. We describe this equivalence, and give simple solutions of the decoding problem both in the dynamical context and in the number theoretic context.
authors.affiliation: Center for Molecular and Behavioral Neuroscience, Rutgers University, Newark, New Jersey 07102I.B.M., Yorktown Heights, New York 10598Columbia University, Department of Mathematics, New York, New York 10027.
authors.forename: Ralph M.
authors.initials: RM
authors.lastname: Siegel
authors.forename: Charles
authors.initials: C
authors.lastname: Tresser
authors.forename: George
authors.initials: G
authors.lastname: Zettler