The equational theory of the weak Bruhat order on finite symmetric groups

  • Luigi Santocanale

    Aix-Marseille Université, France
  • Friedrich Wehrung

    Université de Caen, France

Abstract

It is well known that the weak Bruhat order on the symmetric group on a finite number n of letters is a lattice, denoted by and often called the permutohedron on letters, of which the Tamari lattice is a lattice retract. The equational theory (or word problem) of a class of lattices is the set of all lattice identities satisfied by all members of that class. Our main results imply, as particular cases, the following.

Theorem I. The equational theories of all and of all are both decidable.

Theorem I. There exists a lattice identity that holds in all , but fails in a certain 3,338-element lattice.

Theorem III. The equational theory of all extended permutohedra, on arbitrary (possibly infinite) posets, is trivial.

The proofs of Theorems I and II involve reductions of algebraic statements to certain tiling properties of finite chains.

Cite this article

Luigi Santocanale, Friedrich Wehrung, The equational theory of the weak Bruhat order on finite symmetric groups. J. Eur. Math. Soc. 20 (2018), no. 8, pp. 1959–2003

DOI 10.4171/JEMS/804