Remote Access Representation Theory
Green Open Access

Representation Theory

ISSN 1088-4165

 
 

 

Automata and cells in affine Weyl groups


Author: Paul E. Gunnells
Journal: Represent. Theory 14 (2010), 627-644
MSC (2010): Primary 20F10, 20F55
DOI: https://doi.org/10.1090/S1088-4165-2010-00391-X
Published electronically: October 1, 2010
MathSciNet review: 2726285
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ \tilde{W}$ be an affine Weyl group, and let $ C$ be a left, right, or two-sided Kazhdan-Lusztig cell in $ \tilde{W}$. Let $ \mathtt{Red}(C)$ be the set of all reduced expressions of elements of $ C$, regarded as a formal language in the sense of the theory of computation. We show that $ \mathtt{Red}(C)$ is a regular language. Hence, the reduced expressions of the elements in any Kazhdan-Lusztig cell can be enumerated by a finite state automaton.


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

  • 1. C. A. Athanasiadis, Algebraic combinatorics of graph spectra, subspace arrangements, and Tutte polynomials, Ph.D. thesis, MIT, 1996.
  • 2. R. Bédard, Cells for two Coxeter groups, Comm. Algebra 14 (1986), no. 7, 1253-1286. MR 842039 (87h:20066)
  • 3. -, The lowest two-sided cell for an affine Weyl group, Comm. Algebra 16 (1988), no. 6, 1113-1132. MR 939034 (89d:20041)
  • 4. -, Left V-cells for hyperbolic Coxeter groups, Comm. Algebra 17 (1989), no. 12, 2971-2997. MR 1030605 (91a:20051)
  • 5. M. Belolipetsky and P. E. Gunnells, Experiments and conjectures for planar hyperbolic Coxeter groups, in preparation.
  • 6. M. Belolipetsky, Cells and representations of right-angled Coxeter groups, Selecta Math. (N.S.) 10 (2004), no. 3, 325-339. MR 2099070 (2006f:20048)
  • 7. R. Bezrukavnikov, On tensor categories attached to cells in affine Weyl groups, Representation theory of algebraic groups and quantum groups, Adv. Stud. Pure Math., vol. 40, Math. Soc. Japan, Tokyo, 2004, pp. 69-90. MR 2074589 (2006e:20086)
  • 8. R. Bezrukavnikov and V. Ostrik, On tensor categories attached to cells in affine Weyl groups. II, Representation theory of algebraic groups and quantum groups, Adv. Stud. Pure Math., vol. 40, Math. Soc. Japan, Tokyo, 2004, pp. 101-119. MR 2074591 (2006e:20006)
  • 9. A. Björner and F. Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005. MR 2133266 (2006d:05001)
  • 10. N. Bourbaki, Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines, Actualités Scientifiques et Industrielles, No. 1337, Hermann, Paris, 1968. MR 0240238 (39:1590)
  • 11. B. Brink and R. B. Howlett, A finiteness property and an automatic structure for Coxeter groups, Math. Ann. 296 (1993), no. 1, 179-190. MR 1213378 (94d:20045)
  • 12. W. A. Casselman, Automata to perform basic calculations in Coxeter groups, Representations of groups (Banff, AB, 1994), CMS Conf. Proc., vol. 16, Amer. Math. Soc., Providence, RI, 1995, pp. 35-58. MR 1357194 (96i:20050)
  • 13. C. D. Chen, The decomposition into left cells of the affine Weyl group of type $ \tilde{D}\sb 4$, J. Algebra 163 (1994), no. 3, 692-728. MR 1265858 (95b:20063)
  • 14. J. Du, The decomposition into cells of the affine Weyl group of type $ \tilde{B}\sb 3$, Comm. Algebra 16 (1988), no. 7, 1383-1409. MR 941176 (89i:20074)
  • 15. -, Cells in the affine Weyl group of type $ \tilde{D}\sb 4$, J. Algebra 128 (1990), no. 2, 384-404. MR 1036398 (91a:20052)
  • 16. -, Sign types and Kazhdan-Lusztig cells, Chinese Ann. Math. Ser. B 12 (1991), no. 1, 33-39. MR 1098597 (92c:20089)
  • 17. J. Ellson, E. Gansner, E. Koutsofios, S. North, and G. Woodhull, Graphviz and dynagraph - static and dynamic graph drawing tools, Graph Drawing Software (M. Junger and P. Mutzel, eds.), Springer-Verlag, 2003, pp. 127-148.
  • 18. H. Eriksson, Computational and combinatorial aspects of Coxeter groups, Ph.D. thesis, KTH Stockholm, 1994.
  • 19. J. Guilhot, Kazhdan-Lusztig cells in affine Weyl groups with unequal parameters, Ph.D. thesis, Université Claude Bernard Lyon I and Aberdeen University, 2008.
  • 20. -, personal communication, 2009.
  • 21. P. E. Gunnells, Cells in Coxeter groups, Notices Amer. Math. Soc. 53 (2006), no. 5, 528-535. MR 2254399 (2007d:20068)
  • 22. P. Headley, Reduced expressions in infinite Coxeter groups, Ph.D. thesis, University of Michigan, 1994.
  • 23. J. E. Hopcroft and J. D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley Publishing Co., Reading, Mass., 1979, Addison-Wesley Series in Computer Science. MR 645539 (83j:68002)
  • 24. J. E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. MR 1066460 (92h:20002)
  • 25. D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), no. 2, 165-184. MR 560412 (81j:20066)
  • 26. -, Schubert varieties and Poincaré duality, Geometry of the Laplace operator (Proc. Sympos. Pure Math., Univ. Hawaii, Honolulu, Hawaii, 1979), Proc. Sympos. Pure Math., XXXVI, Amer. Math. Soc., Providence, R.I., 1980, pp. 185-203. MR 573434 (84g:14054)
  • 27. G. Lusztig, Left cells in Weyl groups, Lie group representations, I (College Park, Md., 1982/1983), Lecture Notes in Math., vol. 1024, Springer, Berlin, 1983, pp. 99-111. MR 727851 (85f:20035)
  • 28. -, Some examples of square-integrable representations of $ p$-adic semisimple groups, Trans. Amer. Math. Soc. 277 (1983), 623-653. MR 694380 (84j:22023)
  • 29. -, Characters of finite groups of Lie type, Ann. of Math. Studies, vol. 107, Princeton University Press, 1984. MR 742472 (86j:20038)
  • 30. -, Cells in affine Weyl groups, Algebraic groups and related topics (Kyoto/Nagoya, 1983), Adv. Stud. Pure Math., vol. 6, North-Holland, Amsterdam, 1985, pp. 255-287. MR 803338 (87h:20074)
  • 31. -, Cells in affine Weyl groups. II, J. Algebra 109 (1987), no. 2, 536-548. MR 902967 (88m:20103a)
  • 32. M. Mohri, F. C. N. Pereira, and M. D. Riley, AT&T Finite State Machine Library, available from AT&T Labs.
  • 33. A. Postnikov and R. P. Stanley, Deformations of Coxeter hyperplane arrangements, J. Combin. Theory Ser. A 91 (2000), no. 1-2, 544-597, In memory of Gian-Carlo Rota. MR 1780038 (2002g:52032)
  • 34. J. Y. Shi, The Kazhdan-Lusztig cells in certain affine Weyl groups, Lecture Notes in Mathematics, vol. 1179, Springer-Verlag, Berlin, 1986. MR 835214 (87i:20074)
  • 35. -, Sign types corresponding to an affine Weyl group, J. London Math. Soc. (2) 35 (1987), no. 1, 56-74. MR 871765 (88g:20103b)
  • 36. J.-Y. Shi, Fully commutative elements and Kazhdan-Lusztig cells in the finite and affine Coxeter groups, Proc. Amer. Math. Soc. 131 (2003), no. 11, 3371-3378 (electronic). MR 1990625 (2004d:20044)
  • 37. J. R. Stembridge, On the fully commutative elements of Coxeter groups, J. Algebraic Combin. 5 (1996), no. 4, 353-385. MR 1406459 (97g:20046)
  • 38. L. Wall, The Perl Programming Language, v5.8.8.

Similar Articles

Retrieve articles in Representation Theory of the American Mathematical Society with MSC (2010): 20F10, 20F55

Retrieve articles in all journals with MSC (2010): 20F10, 20F55


Additional Information

Paul E. Gunnells
Affiliation: Department of Mathematics and Statistics, University of Massachusetts, Amherst, Massachusetts 01003
Email: gunnells@math.umass.edu

DOI: https://doi.org/10.1090/S1088-4165-2010-00391-X
Keywords: Kazhdan–Lusztig cells, finite state automata, regular languages, affine Weyl groups, Coxeter hyperplane arrangements
Received by editor(s): September 5, 2008
Received by editor(s) in revised form: July 27, 2009
Published electronically: October 1, 2010
Article copyright: © Copyright 2010 American Mathematical Society

American Mathematical Society