The umpteen operator and its Lifshitz tails

As put forth by Kerov in the early 1990s and elucidated in subsequent works, numerous properties of Wigner random matrices are shared by certain linear maps playing an important role in the representation theory of the symmetric group. We introduce and study an operator of representation-theoretic origin which bears some similarity to discrete random Schrodinger operators acting on the $d$-dimensional lattice. In particular, we define its integrated density of states and prove that in dimension $d \geq 2$ it boasts Lifshitz tails similar to those of the Anderson model. The construction bears a close connection to the fifteen puzzle, a popular sliding puzzle from the XIX-th century. To define the operator, we let the adjacency matrix of an infinite-board version of the puzzle act on a randomly chosen representation of the infinite symmetric group. The proof of the main result boils down to the following problem, possibly of independent interest: estimate the probability that after $n$ random moves the puzzle returns to its initial state. We establish a two-sided estimate on this probability using a new Peierls-type argument.