Counting without listing: polynomial patterns in symmetry groups

The main objects of study are affine Weyl groups, certain discrete subgroups of the group of isometries of a Euclidean space. Each such group comes with a natural order on its elements, and one can ask how many elements lie below a given one. Experiments suggest that the sizes of these intervals are polynomials, closely related to the number of lattice points in certain polytopes. We decompose and parametrize the elements of the group. For some regions we prove polynomiality, and for others we currently obtain only quasi-polynomiality. The resulting polynomials are also closely related to the volume polynomials of faces of permutohedra.

This is joint work with Tristram Bogart, Damian de la Fuente, Nicolas Libedinsky, and David Plaza.