De Fermat a Gauss-Gegenbauer: dinâmica de congruências, colares e palavras

Tese de mestrado em Matemática, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2011O recurso a sistemas dinâmicos para estudar resultados de outras áreas da matemática, incluindo da matemática discreta, tem sido objecto de recentes trabalhos publicados. O pequeno teorema de Fermat, por exemplo, foi provado usando aplicações do círculo. De facto, é possível obter a congruência deste teorema através da contagem de pontos e órbitas periódicos de certo tipo de aplicações do círculo. O mesmo método pode ser usado para uma alargada generalização que é conhecida desde 1863, quando foi publicado um artigo póstumo de Gauss. A sua notação usual é devida a Gegenbauer. Apresenta-se uma notação combinatória alternativa para este resultado. Este é diferente da mais conhecida generalização: o teorema de Euler. Também existem demonstrações destes resultados usando os conceitos de palavra primitiva, palavra de Lyndon e colar. Neste trabalho mostra-se a relação entre a dinâmica de determinadas aplicações do círculo e palavras e colares. Estabelecem-se bijecções identificando cada órbita com um colar aperiódico, correspondendo a identificá-la com uma palavra de Lyndon. De facto, é possível obter todas as palavras primitivas (ou palavras de Lyndon) de comprimento n num alfabeto de cardinalidade a através de todas as órbitas de período mínimo n da aplicação do círculo a . x (mod 1). Reciprocamente, tendo uma palavra primitiva (ou palavra de Lyndon), podem calcular-se explicitamente os pontos da órbita periódica correspondente. Apresentam-se algumas aplicações em termos de linguagens faladas, nomeadamente utilizando as cifras de César e Atbash.The use of dynamical systems to study results in other areas of mathematics, including discrete mathematics, has been the subject of recent work. Fermat’s little theorem, for instance, has been proved using circle maps. In fact, it is possible to obtain the congruence of this theorem by counting periodic orbits and points of certain circle maps. The same method can be used to a generalization of Fermat’s little theorem known since 1863, when a posthumous paper of Gauss was published. Its usual notation is due to Gegenbauer. We give an alternative combinatorial notation for this result. This result differs substantially from the most common generalization, the Euler theorem. There are proofs of these results using the concepts of primitive word, Lyndon word and necklace. In this work we establish a relation between the dynamics of certain circle maps with words and necklaces. We set up bijections identifying each periodic orbit with an aperiodic necklace, which corresponds to identifying it with a Lyndon word. In fact, it is possible to obtain all primitive words (or Lyndon words) of length n over a finite alphabet of cardinality a through all the orbits of minimum period n of the circle map a .x (mod 1). Conversely, having a primitive word (or Lyndon word) we can compute explicitly the points of the corresponding periodic orbit. We give some applications in terms of spoken languages, namely, using the Caesar and Atbash ciphers