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

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 $\mathsf{P}(n)$ and often called the permutohedron on $n$ letters, of which the Tamari lattice $\mathsf{A}(n)$ 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 $\mathsf{P}(n)$ and of all $\mathsf{A}(n)$ are both decidable.

Theorem I. There exists a lattice identity that holds in all $\mathsf{P}(n)$, 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.