On the length of fully commutative elements
HTML articles powered by AMS MathViewer
- by Philippe Nadeau PDF
- Trans. Amer. Math. Soc. 370 (2018), 5705-5724 Request permission
Abstract:
In a Coxeter group $W$, an element is fully commutative if any two of its reduced expressions can be linked by a series of commutations of adjacent letters. These elements have particularly nice combinatorial properties, and index a basis of the generalized Temperley–Lieb algebra attached to $W$.
We give two results about the sequence counting these elements with respect to their Coxeter length. First we prove that this sequence always satisfies a linear recurrence with constant coefficients, by showing that reduced expressions of fully commutative elements form a regular language. Then we classify those groups $W$ for which the sequence is ultimately periodic, extending a result of Stembridge. These results are applied to the growth of generalized Temperley–Lieb algebras.
References
- A. V. Anīsīmov and D. E. Knuth, Inhomogeneous sorting, Internat. J. Comput. Inform. Sci. 8 (1979), no. 4, 255–260. MR 539874, DOI 10.1007/BF00993053
- Georgia Benkart and Joanna Meinel, The center of the affine nilTemperley-Lieb algebra, Math. Z. 284 (2016), no. 1-2, 413–439. MR 3545499, DOI 10.1007/s00209-016-1660-7
- Riccardo Biagioli, Frédéric Jouhet, and Philippe Nadeau, Fully commutative elements in finite and affine Coxeter groups, Monatsh. Math. 178 (2015), no. 1, 1–37. MR 3384889, DOI 10.1007/s00605-014-0674-7
- Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005. MR 2133266
- Brigitte Brink and Robert B. Howlett, A finiteness property and an automatic structure for Coxeter groups, Math. Ann. 296 (1993), no. 1, 179–190. MR 1213378, DOI 10.1007/BF01445101
- B. Casselman. Coxeter groups part II. Word processing. CRM Winter School on Coxeter groups, 2002.
- Ronald de Man, The generating function for the number of roots of a Coxeter group, J. Symbolic Comput. 27 (1999), no. 6, 535–541. MR 1701093, DOI 10.1006/jsco.1999.0280
- The Sage Developers. Sage Mathematics Software (Version 6.9), 2015. http://www. sagemath.org.
- C. Kenneth Fan and John R. Stembridge, Nilpotent orbits and commutative elements, J. Algebra 196 (1997), no. 2, 490–498. MR 1475121, DOI 10.1006/jabr.1997.7119
- C. Kenneth Fan, A Hecke algebra quotient and properties of commutative elements of a Weyl group, ProQuest LLC, Ann Arbor, MI, 1995. Thesis (Ph.D.)–Massachusetts Institute of Technology. MR 2716583
- Sergey Fomin and Curtis Greene, Noncommutative Schur functions and their applications, Discrete Math. 193 (1998), no. 1-3, 179–200. Selected papers in honor of Adriano Garsia (Taormina, 1994). MR 1661368, DOI 10.1016/S0012-365X(98)00140-X
- J. J. Graham, Modular Representations of Hecke Algebras and Related Algebras, Ph.D. thesis, University of Sydney, 1995.
- R. M. Green, Combinatorics of minuscule representations, Cambridge Tracts in Mathematics, vol. 199, Cambridge University Press, Cambridge, 2013. MR 3025147
- Christopher R. H. Hanusa and Brant C. Jones, The enumeration of fully commutative affine permutations, European J. Combin. 31 (2010), no. 5, 1342–1359. MR 2644423, DOI 10.1016/j.ejc.2009.11.010
- Christophe Hohlweg, Philippe Nadeau, and Nathan Williams, Automata, reduced words and Garside shadows in Coxeter groups, J. Algebra 457 (2016), 431–456. MR 3490088, DOI 10.1016/j.jalgebra.2016.04.006
- James E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. MR 1066460, DOI 10.1017/CBO9780511623646
- V. F. R. Jones, Hecke algebra representations of braid groups and link polynomials, Ann. of Math. (2) 126 (1987), no. 2, 335–388. MR 908150, DOI 10.2307/1971403
- Günter R. Krause and Thomas H. Lenagan, Growth of algebras and Gelfand-Kirillov dimension, Revised edition, Graduate Studies in Mathematics, vol. 22, American Mathematical Society, Providence, RI, 2000. MR 1721834, DOI 10.1090/gsm/022
- Hideya Matsumoto, Générateurs et relations des groupes de Weyl généralisés, C. R. Acad. Sci. Paris 258 (1964), 3419–3422 (French). MR 183818
- Alexander Postnikov, Affine approach to quantum Schubert calculus, Duke Math. J. 128 (2005), no. 3, 473–509. MR 2145741, DOI 10.1215/S0012-7094-04-12832-5
- Jacques Sakarovitch, Elements of automata theory, Cambridge University Press, Cambridge, 2009. Translated from the 2003 French original by Reuben Thomas. MR 2567276, DOI 10.1017/CBO9781139195218
- John R. Stembridge, On the fully commutative elements of Coxeter groups, J. Algebraic Combin. 5 (1996), no. 4, 353–385. MR 1406459, DOI 10.1023/A:1022452717148
- John R. Stembridge, Some combinatorial aspects of reduced words in finite Coxeter groups, Trans. Amer. Math. Soc. 349 (1997), no. 4, 1285–1332. MR 1389789, DOI 10.1090/S0002-9947-97-01805-9
- H. N. V. Temperley and E. H. Lieb, Relations between the “percolation” and “colouring” problem and other graph-theoretical problems associated with regular planar lattices: some exact results for the “percolation” problem, Proc. Roy. Soc. London Ser. A 322 (1971), no. 1549, 251–280. MR 498284, DOI 10.1098/rspa.1971.0067
- Jacques Tits, Le problème des mots dans les groupes de Coxeter, Symposia Mathematica (INDAM, Rome, 1967/68) Academic Press, London, 1969, pp. 175–185 (French). MR 0254129
- V. A. Ufnarovskij, Combinatorial and asymptotic methods in algebra [ MR1060321 (92h:16024)], Algebra, VI, Encyclopaedia Math. Sci., vol. 57, Springer, Berlin, 1995, pp. 1–196. MR 1360005, DOI 10.1007/978-3-662-06292-0_{1}
- Gérard Xavier Viennot, Heaps of pieces. I. Basic definitions and combinatorial lemmas, Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985) Lecture Notes in Math., vol. 1234, Springer, Berlin, 1986, pp. 321–350. MR 927773, DOI 10.1007/BFb0072524
- M. V. Zavodovskiĭ, Growth of generalized Temperley-Lieb algebras associated with Coxeter graphs (four projectors), Dopov. Nats. Akad. Nauk Ukr. Mat. Prirodozn. Tekh. Nauki 7 (2010), 12–15 (Russian, with English and Ukrainian summaries). MR 3112747
- M. V. Zavodovskii and Yu. S. Samoilenko, Growth generalized Temperley-Lieb algebras connected with simple graphs, Ukraïn. Mat. Zh. 61 (2009), no. 11, 1579–1585 (Russian, with Russian summary); English transl., Ukrainian Math. J. 61 (2009), no. 11, 1858–1864. MR 2888564, DOI 10.1007/s11253-010-0318-6
Additional Information
- Philippe Nadeau
- Affiliation: CNRS, Institut Camille Jordan, Université Claude Bernard Lyon 1, 69622 Villeurbanne Cedex, France
- Email: nadeau@math.univ-lyon1.fr
- Received by editor(s): June 27, 2016
- Received by editor(s) in revised form: December 12, 2016
- Published electronically: February 8, 2018
- © Copyright 2018 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 370 (2018), 5705-5724
- MSC (2010): Primary 05E15, 16Z05; Secondary 05A15
- DOI: https://doi.org/10.1090/tran/7183
- MathSciNet review: 3812113