Exact universal-enveloping-algebra formula for the binary Burnside chain

Source. Persi Diaconis, Andrew Lin, and Arun Ram, Schur–Weyl duality for diagonalizing a Markov chain on the hypercube, Conjecture 6.3. We also use and explicitly credit the coordinate-restriction property already proved by the same authors in A curiously slowly mixing Markov chain, Proposition 3.3; its one-coordinate matrix form is Proposition 6.1 in the conjecture's source.

The conjectured identity holds for every $n\geq0$. More precisely, if

$$p^+=\frac12\begin{pmatrix}1&1\\1&1\end{pmatrix}, \qquad p^-=\frac12\begin{pmatrix}1&-1\\-1&1\end{pmatrix}, \qquad p^+h=\frac12\begin{pmatrix}1&-1\\1&-1\end{pmatrix}, \tag{1}$$

and $f(x,y,z)$ is the sum of all distinct ordered tensor products containing $x$ factors $p^+$, $y$ factors $p^-$, and $z$ factors $p^+h$, then the binary Burnside transition matrix satisfies

$$\boxed{ K_n=\sum_{x+y+z=n}c_{y,z}f(x,y,z), } \tag{2}$$

where

$$c_{y,z}= \begin{cases} \displaystyle \left( \frac{y!z!} {(y/2)!(z/2)!((y+z)/2)!\,2^{y+z}} \right)^2, &y,z\text{ both even}, \\ 0,&\text{otherwise}. \end{cases} \tag{3}$$

In fact, the proof identifies every Walsh–Fourier matrix entry separately.

1. Walsh coordinates reduce the conjecture to a triangular coefficient formula

Let

$$J=\frac1{\sqrt2} \begin{pmatrix}1&1\\1&-1\end{pmatrix}. \tag{4}$$

A direct multiplication gives

$$Jp^+J=E_{00}, \qquad Jp^-J=E_{11}, \qquad J(p^+h)J=E_{01}, \tag{5}$$

where $E_{ij}$ denotes the corresponding matrix unit. Identify binary vectors with subsets of $[n]$, and define the Walsh characters

$$\chi_A(x)=(-1)^{\sum_{i\in A}x_i}. \tag{6}$$

The conjugated transition matrix has entries

$$\widehat K_n(A,B) = \bigl(J^{\otimes n}K_nJ^{\otimes n}\bigr)_{A,B} = 2^{-n} \sum_{x\in\{0,1\}^n} \chi_A(x)(K_n\chi_B)(x). \tag{7}$$

By (5), a tensor product contributes to the $(A,B)$ entry exactly when

$$A\subseteq B, \qquad x=n-|B|, \qquad y=|A|, \qquad z=|B\setminus A|. \tag{8}$$

For fixed $A\subseteq B$, exactly one ordered tensor product has those prescribed matrix units at its individual coordinates. Therefore (2) is equivalent to the explicit stronger entrywise identity

$$\boxed{ \widehat K_n(A,B)= \begin{cases} c_{|A|,|B\setminus A|},&A\subseteq B, \\ 0,&A\not\subseteq B. \end{cases} } \tag{9}$$

2. Coordinate restriction eliminates every extraneous Walsh coordinate

The previously established coordinate-restriction theorem states that observing the binary Burnside process on any coordinate subset $B\subseteq[n]$ gives precisely the binary Burnside process on that subset. Consequently,

$$(K_n\chi_B)(x) = (K_{|B|}\chi_{[|B|]})(x_B). \tag{10}$$

If $A\not\subseteq B$, summing (7) over any coordinate in $A\setminus B$ gives zero. If $A\subseteq B$, summing over the $n-|B|$ remaining coordinates gives

$$\widehat K_n(A,B) = 2^{-|B|} \sum_{x\in\{0,1\}^{|B|}} \chi_A(x) (K_{|B|}\chi_{[|B|]})(x). \tag{11}$$

Thus it remains to calculate the full-support Walsh character in each dimension.

3. Cycle coloring reduces the character to even-cycle probabilities

Start the dimension-$m$ binary Burnside chain from $x\in\{0,1\}^m$. Its first step chooses independent uniform permutations on the zero coordinates and the one coordinates. Its second step assigns an independent fair binary label to every permutation cycle, producing the next state $Y$.

For a cycle $C$, the contribution of its common random label $\xi_C$ to the full-support character is

$$(-1)^{|C|\xi_C}. \tag{12}$$

Averaging over $\xi_C$ gives one if $|C|$ is even and zero if $|C|$ is odd. Therefore the conditional character expectation is the indicator that every permutation cycle in both coordinate classes has even length.

Let $q_j$ be the probability that a uniform permutation of $j$ elements has only even cycles. The labeled-permutation cycle formula gives

$$\sum_{j\geq0}q_jt^j = \exp\left(\sum_{r\geq1}\frac{t^{2r}}{2r}\right) = (1-t^2)^{-1/2}. \tag{13}$$

Hence

$$q_{2r}=\frac{\binom{2r}{r}}{4^r}, \qquad q_{2r+1}=0. \tag{14}$$

The two permutations are independent, so

$$(K_m\chi_{[m]})(x) = q_{|x|}q_{m-|x|}. \tag{15}$$

4. A two-circle integral evaluates every coefficient

The numbers in (14) are exactly the circular cosine moments:

$$q_j= \frac1{2\pi}\int_0^{2\pi}\cos^j\theta\,d\theta. \tag{16}$$

Let $U=\cos\Theta$ and $V=\cos\Phi$, with $\Theta$ and $\Phi$ independent uniform circular angles. For $A\subseteq[m]$, put

$$a=|A|, \qquad b=m-a. \tag{17}$$

Combining (11), (15), and (16), and summing independently over each binary coordinate, gives

$$\begin{aligned} \widehat K_m(A,[m]) &= 2^{-m} \sum_{x\in\{0,1\}^m} (-1)^{\sum_{i\in A}x_i} \mathbb E\left[U^{|x|}V^{m-|x|}\right] \\ &= \mathbb E\left[ \left(\frac{V-U}{2}\right)^a \left(\frac{V+U}{2}\right)^b \right]. \end{aligned} \tag{18}$$

For complete clarity about the angle change of variables, start instead with independent uniform circular angles $S,T$. The map

$$(S,T) \longmapsto (S+T,S-T) \pmod{2\pi} \tag{19}$$

is a surjective homomorphism of the two-torus, with determinant $-2$. Haar measure therefore pushes forward to Haar measure. In particular, we can realize the independent uniform angles in (18) as

$$\Theta=S+T, \qquad \Phi=S-T.$$

The elementary trigonometric identities are

$$\frac{V-U}{2}=\sin S\sin T, \qquad \frac{V+U}{2}=\cos S\cos T. \tag{20}$$

Substitution into (18) now factors the expectation:

$$\widehat K_m(A,[m]) = \left( \frac1{2\pi} \int_0^{2\pi} \sin^a\theta\cos^b\theta\,d\theta \right)^2. \tag{21}$$

The integral vanishes unless both $a$ and $b$ are even. For

$$a=2r, \qquad b=2s,$$

the beta integral gives

$$\begin{aligned} \frac1{2\pi} \int_0^{2\pi} \sin^{2r}\theta\cos^{2s}\theta\,d\theta &= \frac{\Gamma(r+\tfrac12)\Gamma(s+\tfrac12)} {\pi\,\Gamma(r+s+1)} \\ &= \frac{(2r)!(2s)!} {2^{2r+2s}r!s!(r+s)!}. \end{aligned} \tag{22}$$

Squaring (22) proves that (21) is exactly $c_{a,b}$ from (3). Together with coordinate restriction in Section 2, this proves (9), and therefore the full conjectured identity (2), simultaneously for every dimension.

As a further interpretation absent from the conjectural statement, every coefficient is the square of an explicit mixed circular moment:

$$\boxed{ c_{a,b} = \left( \mathbb E\left[\sin^a\Theta\cos^b\Theta\right] \right)^2. } \tag{23}$$

In particular, the previously observed diagonal coefficients recover the known binary Burnside eigenvalues:

$$c_{2r,0} = \frac{\binom{2r}{r}^2}{2^{4r}}. \tag{24}$$

The separate higher-alphabet conjecture, Conjecture 6.4 in the same paper, is not asserted here.

Conclusion: Conjecture 6.3 is PROVED for every $n$.