Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture

Bousch, Thierry¹ ; Mairesse, Jean²

¹ Laboratoire de Mathématique (UMR 8628 du CNRS), bât. 425, Université de Paris-Sud, 91405 Orsay Cedex, France
² LIAFA, CNRS et Université Paris 7, case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France

Journal of the American Mathematical Society, Tome 15 (2002) no. 1, pp. 77-111

Résumé

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 for the joint spectral radius of a set of matrices. 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 sur le rayon spectral joint d’un ensemble de matrices.

Détail

DOI : 10.1090/S0894-0347-01-00378-2

Bibliographie

[1] Aliprantis, Charalambos D., Border, Kim C. Infinite-dimensional analysis 1999

[2] Baccelli, François Louis, Cohen, Guy, Olsder, Geert Jan, Quadrat, Jean-Pierre Synchronization and linearity 1992

[3] Berger, Marc A., Wang, Yang Bounded semigroups of matrices Linear Algebra Appl. 1992 21 27

[4] Brilman, Matthieu, Vincent, Jean-Marc Dynamics of synchronized parallel systems Comm. Statist. Stochastic Models 1997 605 617

[5] Bullett, Shaun, Sentenac, Pierrette Ordered orbits of the shift, square roots, and the devil’s staircase Math. Proc. Cambridge Philos. Soc. 1994 451 481

[6] Carlson, D. A., Haurie, A. Infinite horizon optimal control 1987

[7] Cohen, Guy, Dubois, Didier, Quadrat, Jean-Pierre, Viot, Michel A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing IEEE Trans. Automat. Control 1985 210 220

[8] Random matrices and their applications 1986

[9] Crandall, Michael G., Tartar, Luc Some relations between nonexpansive and order preserving mappings Proc. Amer. Math. Soc. 1980 385 390

[10] Daubechies, Ingrid, Lagarias, Jeffrey C. Sets of matrices all infinite products of which converge Linear Algebra Appl. 1992 227 263

[11] Denker, Manfred, Grillenberger, Christian, Sigmund, Karl Ergodic theory on compact spaces 1976

[12] Fathi, Albert Théorème KAM faible et théorie de Mather sur les systèmes lagrangiens C. R. Acad. Sci. Paris Sér. I Math. 1997 1043 1046

[13] Gaubert, Stéphane Performance evaluation of (max,+) automata IEEE Trans. Automat. Control 1995 2014 2025

[14] Idempotency 1998

[15] Gaubert, Stéphane, Mairesse, Jean Modeling and analysis of timed Petri nets using heaps of pieces IEEE Trans. Automat. Control 1999 683 697

[16] Idempotency 1998

[17] Gurvits, Leonid Stability of discrete linear inclusion Linear Algebra Appl. 1995 47 85

[18] Jenkinson, Oliver Frequency locking on the boundary of the barycentre set Experiment. Math. 2000 309 317

[19] Lagarias, Jeffrey C., Wang, Yang The finiteness conjecture for the generalized spectral radius of a set of matrices Linear Algebra Appl. 1995 17 42

[20] Mañé, Ricardo Introdução à teoria ergódica 1983

[21] Mañé, Ricardo Generic properties and problems of minimizing measures of Lagrangian systems Nonlinearity 1996 273 310

[22] Venkatarayudu, T. The 7-15 problem Proc. Indian Acad. Sci., Sect. A. 1939 531

[23] Idempotency 1998

[24] Rota, Gian-Carlo, Strang, Gilbert A note on the joint spectral radius Indag. Math. 1960 379 381

[25] Simon, Imre The nondeterministic complexity of a finite automaton 1990 384 400

[26] Graves, Lawrence M. The Weierstrass condition for multiple integral variation problems Duke Math. J. 1939 656 660