Prépublication d'Orsay numéro 34 (06/06/2000)

ASYMPTOTIC HEIGHT OPTIMIZATION FOR TOPICAL IFS, TETRIS HEAPS, AND THE FINITENESS CONJECTURE.
BOUSCH, Thierry - Topologie et Dynamique, Université Paris-Sud, Bât. 425, 91405 Orsay cedex
MAIRESSE, Jean - Université Paris7, case 7014, 2 place Jussieu, 75251 Paris Cedex 05.



Mots Clés : Applications topicales; Automates max-plus; Tetris; Processus sturmiens; Contrôle optimal; Conjecture de finitude.

Classification MSC : 49J27; 37D35.

Résumé :
Etant donné un système itéré de fonctions (IFS) topicales, vérifiant certaines conditions, nous montrons que les questions d'optimisation asymptotique de la hauteur sont équivalentes à la recherche des extrema d'une fonctionnelle continue, la hauteur moyenne, sur un certain espace compact de mesures. Nous présentons des résultats généraux permettant de déterminer ces extrema, puis appliquons ces méthodes à deux problèmes concrets. Premièrement, nous redémontrons que les empilements les plus denses de deux pièces de Tetris sont Sturmiens. Deuxièmement, nous construisons un contre-exemple effectif à la conjecture de finitude de Lagarias et Wang.
Abstract :
Given an Iterated Function System (IFS) of topical maps verifying some conditions, we prove that the asymptotic height optimization problems are equivalent to finding the extrema of a continuous functional, the average height, on some compact space of measures. We give general results to determine these extrema, and then apply them to two concrete problems. First, we give a new proof of the theorem that the densest heaps of two Tetris pieces are sturmian. Second, we construct an explicit counterexample to the Lagarias-Wang finiteness conjecture.
Contact : Thierry.Bousch@math.u-psud.fr