A decoding problem in dynamics and in number theory

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