On the length of fully commutative elements

Nadeau, Philippe

doi:10.1090/tran/7183

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