Random walks on the hyperoctahedral group

Given a finite group G and a set of generators S, we can look at a random walk on the Cayley graph Cay(G,S) where the starting point is the unit of G, and at each step we move from an element g of G to the element sg, where s is drawn from S according to a given distribution. The most basic invariant of this random walk is the spectral gap. While, initially, one would have to analyze a |G| by |G| matrix to find the spectral gap, it is well known that the relevant matrix has a block decomposition according to the irreps (irreducible representations) of G, and therefore if one knows which irrep is responsible for the spectral gap, then the calculation reduces to a much smaller matrix.

When the group is Sn and the set of generators is the transpositions (ij), this random walk is called the interchange process. An important conjecture in this field, called the Aldous conjecture, was that for the interchange process, the standard representation of Sn is always responsible for the spectral gap. This conjecture was proved in 2009 by Caputo, Liggett and Richthammer.

In 2020, F. Cesi has extended this result to the case of the hyperoctahedral group Bn. This group has order n2^n, and can be described as the wreath product of the group of order 2 by Sn, or as the group of n by n matrices such that each row and each column contains a unique nonzero element, which is either 1 or -1. In Cesi's work, the set of generators includes all the transpositions (ij) and all the diagonal matrices with a single (-1) entry. He proved that in this case, the spectral gap comes from one of two specific representations. He also conjectured that the same holds when the generators include the transpositions and all diagonal matrices with determinant -1.

In this work we show that Cesi's conjecture is false, and characterize the set of irreps from which the spectral gap can come. This set includes n irreps, of total dimension O(2^n). We also prove similar results where the generators include the transpositions and all the diagonal matrices.

Joint work with Subhajit Ghosh.