Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



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

Authors: Thierry Bousch and Jean Mairesse
Journal: J. Amer. Math. Soc. 15 (2002), 77-111
MSC (2000): Primary 49J27, 37D35
Published electronically: September 10, 2001
MathSciNet review: 1862798
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


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.

References [Enhancements On Off] (What's this?)

  • Charalambos D. Aliprantis and Kim C. Border, Infinite-dimensional analysis, 2nd ed., Springer-Verlag, Berlin, 1999. A hitchhiker’s guide. MR 1717083
  • François Louis Baccelli, Guy Cohen, Geert Jan Olsder, and Jean-Pierre Quadrat, Synchronization and linearity, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1992. An algebra for discrete event systems. MR 1204266
  • Marc A. Berger and Yang Wang, Bounded semigroups of matrices, Linear Algebra Appl. 166 (1992), 21–27. MR 1152485, DOI
  • [BeS]berstel J. Berstel and P. Séébold, Sturmian words, in M. Lothaire (ed.), Algebraic combinatorics on words, to appear in Cambridge University Press [BT1]jsr-nc V. D. Blondel and J. N. Tsitsiklis, The boundedness of all products of a pair of matrices is undecidable, Systems and Control Letters 41 (2000), pp. 135–140 [BT2]bt-complex V. D. Blondel and J. N. Tsitsiklis, Complexity of stability and controllability of elementary hybrid systems, Automatica 35 (1999), pp. 479–489 [B1]poisson T. Bousch, Le poisson n’a pas d’arêtes, Ann. Inst. H. Poincaré Proba. Stat. 36 (2000), pp. 489–508 [B2]cwalters T. Bousch, La condition de Walters, Ann. Sci. Ec. Norm. Sup. 34 (2001), pp. 287–311
  • Matthieu Brilman and Jean-Marc Vincent, Dynamics of synchronized parallel systems, Comm. Statist. Stochastic Models 13 (1997), no. 3, 605–617. MR 1457662, DOI
  • Shaun Bullett and Pierrette Sentenac, Ordered orbits of the shift, square roots, and the devil’s staircase, Math. Proc. Cambridge Philos. Soc. 115 (1994), no. 3, 451–481 (English, with English and French summaries). MR 1269932, DOI
  • D. A. Carlson and A. Haurie, Infinite horizon optimal control, Lecture Notes in Economics and Mathematical Systems, vol. 290, Springer-Verlag, Berlin, 1987. Theory and applications. MR 1117222
  • Guy Cohen, Didier Dubois, Jean-Pierre Quadrat, and Michel Viot, A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing, IEEE Trans. Automat. Control 30 (1985), no. 3, 210–220. MR 778424, DOI
  • Joel E. Cohen, Harry Kesten, and Charles M. Newman (eds.), Random matrices and their applications, Contemporary Mathematics, vol. 50, American Mathematical Society, Providence, RI, 1986. MR 841077
  • [CLT]thieu G. Contreras, A. Lopes and P. Thieullen, Lyapunov minimizing measures for expanding maps of the circle, manuscript (1999), to appear in Ergodic Theory and Dynamical Systems
  • Michael G. Crandall and Luc Tartar, Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc. 78 (1980), no. 3, 385–390. MR 553381, DOI
  • Ingrid Daubechies and Jeffrey C. Lagarias, Sets of matrices all infinite products of which converge, Linear Algebra Appl. 161 (1992), 227–263. MR 1142737, DOI
  • [DL2]daubechies2 I. Daubechies and J. Lagarias, Corrigendum/addendum to: [DL1], Linear Algebra Appl. 327 (2001), pp. 69–83
  • Manfred Denker, Christian Grillenberger, and Karl Sigmund, Ergodic theory on compact spaces, Lecture Notes in Mathematics, Vol. 527, Springer-Verlag, Berlin-New York, 1976. MR 0457675
  • Albert Fathi, Théorème KAM faible et théorie de Mather sur les systèmes lagrangiens, C. R. Acad. Sci. Paris Sér. I Math. 324 (1997), no. 9, 1043–1046 (French, with English and French summaries). MR 1451248, DOI
  • Stéphane Gaubert, Performance evaluation of $(\max ,+)$ automata, IEEE Trans. Automat. Control 40 (1995), no. 12, 2014–2025. MR 1364950, DOI
  • [Ga2]cours-gaubert S. Gaubert, Introduction aux systèmes dynamiques à événements discrets, ENSTA course notes (1993) [GG]gg S. Gaubert and J. Gunawardena, A nonlinear hierarchy for discrete event dynamical systems, in A. Giua, R. Smedinga and M. Spathopoulos (eds.), Proceedings of WODES 98, IEE (1998)
  • Jeremy Gunawardena (ed.), Idempotency, Publications of the Newton Institute, vol. 11, Cambridge University Press, Cambridge, 1998. Papers from the workshop held in Bristol, October 3–7, 1994. MR 1608365
  • Stéphane Gaubert and Jean Mairesse, Modeling and analysis of timed Petri nets using heaps of pieces, IEEE Trans. Automat. Control 44 (1999), no. 4, 683–697. MR 1684424, DOI
  • [GM3]gm3 S. Gaubert and J. Mairesse, Performance evaluation of timed Petri nets using heaps of pieces, in P. Bucholz and M. Silva (eds.), Petri nets and performance models (PNPM’99), IEEE Computer Society (1999), pp. 158–169. [G1]gaujal1 B. Gaujal, M. Jafari, M. Baykal-Gürsoy \textand G. Alpan, Allocation sequences of two processes sharing a resource, IEEE Trans. Robotics and Automation 11 (1995), pp. 748–753 [G2]gaujal2 B. Gaujal, Optimal allocation sequences of two processes sharing a resource, Discrete Event Dynamical Systems 7 (1997), pp. 327–354
  • Jeremy Gunawardena (ed.), Idempotency, Publications of the Newton Institute, vol. 11, Cambridge University Press, Cambridge, 1998. Papers from the workshop held in Bristol, October 3–7, 1994. MR 1608365
  • Leonid Gurvits, Stability of discrete linear inclusion, Linear Algebra Appl. 231 (1995), 47–85. MR 1361100, DOI
  • [Gu2]gurvits2 L. Gurvits, Stability of linear inclusions. Part 2, NEC Research report TR 96-173 (1996) [HO]hunt-ott B. R. Hunt and E. Ott, Optimal periodic orbits of chaotic systems occur at low period, Phys. Rev. E 54 (1996), pp. 328–337
  • Oliver Jenkinson, Frequency locking on the boundary of the barycentre set, Experiment. Math. 9 (2000), no. 2, 309–317. MR 1780215
  • Jeffrey C. Lagarias and Yang Wang, The finiteness conjecture for the generalized spectral radius of a set of matrices, Linear Algebra Appl. 214 (1995), 17–42. MR 1311628, DOI
  • Ricardo Mañé, Introdução à teoria ergódica, Projeto Euclides [Euclid Project], vol. 14, Instituto de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, 1983 (Portuguese). MR 800092
  • Ricardo Mañé, Generic properties and problems of minimizing measures of Lagrangian systems, Nonlinearity 9 (1996), no. 2, 273–310. MR 1384478, DOI
  • [MV]mv J. Mairesse and L. Vuillon, Optimal sequences in a heap model with two pieces, Liafa research report 98/09, Univ. Paris 7 (1998), to appear in Theor. Comp. Sci. [MH]mhed M. Morse and G. A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Am. J. Math. 62 (1940), pp. 1–42
  • Jeremy Gunawardena (ed.), Idempotency, Publications of the Newton Institute, vol. 11, Cambridge University Press, Cambridge, 1998. Papers from the workshop held in Bristol, October 3–7, 1994. MR 1608365
  • Gian-Carlo Rota and Gilbert Strang, A note on the joint spectral radius, Nederl. Akad. Wetensch. Proc. Ser. A 63 = Indag. Math. 22 (1960), 379–381. MR 0147922
  • Imre Simon, The nondeterministic complexity of a finite automaton, Mots, Lang. Raison. Calc., Hermès, Paris, 1990, pp. 384–400. MR 1252678
  • [TB]jsr-hard J. N. Tsitsiklis and V. D. Blondel, The Lyapunov exponent and joint spectral radius of pairs of matrices are hard, when not impossible, to compute and to approximate, Mathematics of Control, Signals and Systems 10 (1997), pp. 31–40 & correction p. 381 ; [Vin]vincent J. M. Vincent, Some ergodic results on stochastic iterative discrete event systems, Discrete Event Dynamic Systems 7 (1997), pp. 209–233

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 49J27, 37D35

Retrieve articles in all journals with MSC (2000): 49J27, 37D35

Additional Information

Thierry Bousch
Affiliation: Laboratoire de Mathématique (UMR 8628 du CNRS), bât. 425, Université de Paris-Sud, 91405 Orsay Cedex, France

Jean Mairesse
Affiliation: LIAFA, CNRS et Université Paris 7, case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France

Keywords: Topical maps, max-plus automata, Tetris, sturmian processes, optimal control, finiteness conjecture. (<I> Mots-cl&#233;s.</I> Applications topicales, automates max-plus, Tetris, processus sturmiens, contr&#244;le optimal, conjecture de finitude.)
Received by editor(s): July 11, 2000
Published electronically: September 10, 2001
Additional Notes: The work of the second author was partially supported by the European Community Framework IV programme through the research network ALAPEDES (“The ALgebraic Approach to Performance Evaluation of Discrete Event Systems”)
Article copyright: © Copyright 2001 American Mathematical Society