In this post here, I outlined some things that I might want to prove. Very bottom of that list was:

Extending the Upper Bound Lemma to the non-Kac case. As I speak, this is beyond what I am capable of. This also requires work on the projection and quantum total variation distances (i.e. show they are equal in this larger category).

After that post, Simeng Wang wrote with the, for me, exciting news that he had proven the Upper Bound Lemma in the non-Kac case, and had an upcoming paper with Amaury Freslon and Lucas Teyssier. At first glance the paper is an intersection of the work of Amaury in random walks on compact quantum groups, and Lucas’ work on limit profiles, a refinement in the understanding of how the random transposition random walk converges to uniform. The paper also works with continuous-time random walks but I am going to restrict attention to what it does with random walks on S_N^+.


For the case of a family of Markov chains (X_N)_{N\geq 1} exhibiting the cut-off phenomenon, it will do so in a window of width w_N about a cut-off time t_N, in such a way that w_N/t_N\rightarrow 0, and, where d_N(t) is the ‘distance to random’ at time t, d_N(t_N+cw_N) will be close to one for c<0 and close to zero for c>0. The cutoff profile of the family of random walks is a continuous function f:\mathbb{R}\rightarrow[0,1] such that as N\rightarrow \infty,

\displaystyle d_N(t_N+cw_N)\rightarrow f(c).

I had not previously heard about such a concept, but the paper gives a number of examples in which the analysis had been carried out. Lucas however improved the Diaconis–Shahshahani Upper Bound Lemma and this allowed him to show that the limit profile for the random transpositions random walk is given by:

\displaystyle d_{\text{TV}}(\text{Poi}[1+e^{-c}],\text{Poi}[1])

Without looking back on Lucas’ paper, I am not sure exactly how this d_{\text{TV}} works… I will guess it is, where \xi_1\sim \text{Poi}[1+e^{-c}] and \xi_2\sim \text{Poi}[2], and so:

\displaystyle f_{\text{RT}}(c)=\frac{1}{2}\sum_{k=0}^{\infty}\left|\mathbb{P}[\xi_1=k]-\mathbb{P}[\xi_2=k]\right|,

and I get f(0)\approx 0.330, f(2)\approx 0.0497 and f(-2)\approx 0.949 on CAS. Looking at Lucas’ paper thankfully this is correct.

The article confirms that Lucas’ work is the inspiration, but the study will take place with infinite compact quantum groups. The representation theory carries over so well from the classical to quantum case, and it is representation theory that is used to prove so many random-walk results, that it might have been and was possible to study limit profiles for random walks on quantum groups.

More importantly, technical issues which arise as soon as N>4 disappear if the pure quantum transposition random walk is considered. This is a purely quantum phenomenon because the random walk driven only by transpositions in the classical case is periodic and does not converge to uniform. I hope to show in an upcoming work how something which might be considered a quantum transposition behaves very differently to a classical/deterministic transposition. My understanding at this point, in a certain sense (see here)) is that a quantum transposition has N-2 fixed points in the sense that it is an eigenstate (with eigenvalue N-2) of the character \text{fix}=\sum_i u_{ii}. I am hoping to find a dual with a quantum transposition that for example does not square to the identity (but this is a whole other story). This would imply in a sense that there is no quantum alternating group.

The paper will show that the quantum version of the ordinary random transposition random walk and of this pure random transposition walk asymptotically coincide. They will detect the cutoff at time \frac12 N\ln N, and find an explicit limit profile (which I might not be too interested in).

I will skip the stuff on O_N^+ but as there are some similarities between the representation theory of quantum orthogonal and quantum permutation groups I may have to come back to these bits.

Quantum Permutations

Character Theory

At this point I will move away and look at this Banica tome on quantum permutations for some character theory.

Banica talks about looking at the law of the main character,

\displaystyle \chi=\sum_{i=1}^Nu_{ii}=\text{tr}(u)=\text{fix},

where \text{fix} is my own notation. In the classical case it is known that as N\rightarrow \infty, \text{fix}\sim \text{Poi}[1], and in the quantum case it can be shown that \text{fix}\sim \text{Poi}^+[1], the free Poisson distribution.

Proposition 1.17 (Banica tome)

The characters of corepresentations, given by:

\displaystyle \chi_{v}=\sum_{i=1}{d_v}\rho_{ii}^v

behave as follows, in respect to the various operations:


\chi_{v\otimes w}=\chi_v\cdot \chi_w


In addition if v\cong w then \chi_v=\chi_w\quad\bullet

Proposition 1.21 (Banica tome)

The moments of \text{fix} are

\displaystyle M_k=\text{dim}(\text{Fix}(u^{\otimes k}))

When u\cong \overline{u}, the law of \text{fix} is a real measure, supported by \sigma(\text{fix}).

The second part here is most important at the moment.

Theorem 3.14 (Banica tome)

The quantum groups S_N^+ with N\geq 4 have the following properties.

The moments of fix are the Catalan numbers:


The character “fix” follows the Marchenko-Pastur law (related to free Poisson). I might denote it \text{Poi}^+1[1].

The fusion rules for irreducible representations are the same as for \text{SO}_3:

r_k\otimes r_l=r_{|k-l|}+r_{|k-l|+1}+\cdots+r_{k+l}

The dimensions of the representations are as follows, with q^2-(N-2)q+1=0

\displaystyle \text{dim}(r_k)=\frac{q^{k+1}-q^{-k}}{q-1}.

In proving this, Banica exhibits via a recurrence that:

r_{k}\otimes r_1=r_{k-1}+r_{k}+r_{k+1}\Rightarrow \chi_k\chi_1=\chi_{k-1}+\chi_{k}+\chi_{k+1}

I just need to check have we that \chi_k\chi_1=\chi_1\chi_k… actually this follows from the fusions rules. So, the characters of the irreducible representations satisfy


Furthermore, by the fusion rules, they commute, and so the \mathrm{C}^*-algebra generated by them is commutative. At this point we will do some work with Brannan to better understand what is going on with such commutative \mathrm{C}^*-algebras. This necessitates working with O_N^+.

Free Orthogonal Quantum Groups

Let C(O_N^+) be the universal \mathrm{C}^*-algebra generated by the elements of a unitary matrix of self-adjoint u^{O_N^+}_{ij}=u^{O_N^+}_{ij} (u^{O_N^+})_{i,j=1}^N, i.e. such that:

\displaystyle \sum_{k=1}^Nu_{ik}^{O_N^+}u_{jk}^{O_N^+}=\delta_{i,j}=\sum_{k=1}^Nu_{ki}^{O_N^+}u_{kj}^{O_N^+}.

The representation theory was studied by Banica:

Theorem 4.1 (numbering Brannan’s)

For any fixed N\geq 2 there is a maximal family of irreducible representations of O_N^+, labelled by non-negative integers with the the properties that \kappa_0 is the trivial representation, \kappa_1 is the fundamental representation u^{O_N^+}. The representations are self-conjugate and satisfy the fusion rules:

\displaystyle \kappa_r\boxtimes \kappa_s\cong \bigoplus_{\ell=0}^{\min\{r,s\}}\kappa_{r+s-2\ell}

For N=2, d_n=n+1, and for N\geq 3:

\displaystyle d_n=\dfrac{q(N)^{n+1}-q(N)^{-n-1}}{q(N)-q(N)^{-1}},

where q(N) is defined by q(N)+q(N)^{-1}=N. The characters \chi_n\in C(O_N^+) are self-adjoint and satisfy


This implies that the characters commute and the central *-algebra generated by the characters is generated by \chi_0 and \chi_1. The spectral measure \mu_{\chi_1} of \chi_1 relative to the Haar state (might have to return to this) is Wigner’s semicircle law:

\displaystyle d\mu_{\chi_1}(t)=\mathbf{1}_{[-2,2]}(t)\frac{\sqrt{4-t^2}}{2\pi}\,dt

Lemma 4.2 (Brannan)

Let N\geq 2. Then \sigma(\chi_1)=[-N,N].

It’s hilarious how bad I am at this stuff… I just spent 25 minutes trying to prove that \|u_{ii}\|\leq 1… I guess I got there in the end via Murphy Theorem 5.1.11… there is a (pure) state \rho(u_{ii}^2)=\|u_{ii}^2\|. Also \sum_ku_{ik}^2=\mathbf{1}_{O_N^+}. Hit both of these with \rho to find:

\displaystyle \|u_{ii}^2\|=\|u_{ii}\|^2=1-\sum_{k\neq i}\rho(u_{ik}^2)\leq 1\Rightarrow \|u_{ii}\|\leq 1.

Now we move on

Proof: So, from that

\displaystyle \|\chi_1\|=\left\|\sum_{i=1}^Nu_{ii}^{O_N^+}\right\|\leq \sum_{i=1}^N\|u_{ii}^{O_N^+}\|\leq N,

therefore \sigma(\text{fix})\subset [-N,N]. The universal property gives a surjective \mathrm{C}^*-homomorphism \pi onto C(O_N). We have \text{fix}(\pm I_N)=\pm N, and Brannan says that in fact the spectrum of fix in this algebra of functions is the whole of [-N,N] (nice argument here). Brannan argues that the spectrum of any element of a \mathrm{C}^*-algebra contains the spectrum of its image, we have that [-N,N]\subset \sigma(\text{fix})\quad\bullet

Let (u_n)_{n\geq 0} denote the sequence of polynomials defined by initial conditions u_0=1, u_1=\text{id}, and the recursion:

\text{id}\cdot u_n=u_{n+1}-u_{n-1}.

Think these are u_n(x)=U_n(x/2), for U_n Chebyshev of second kind.

Corollary 4.3 (Brannan)

Let C(O_N^+)_0:=\mathrm{C}^*(\chi_n\,:\,n\geq 0)\subset C(O_N^+) be the unital \mathrm{C}^*-algebra generated by the irreducible characters. Then there is a \mathrm{C}^*-isomorphism C(O_N^+)_0\cong C([-N,N]) defined by:

\chi_n \mapsto \left.u_n\right|_{[-N,N]}\qquad\bullet

OK, I think I understand this central algebra a little better. What I want to do now is show that the characters for S_N^+ have some nice properties, and related to these u_n. I don’t think there is any issue using these… but should the restriction be to [0,N] rather than [0,4]? Surely. I know that in the dual of the dihedral group the spectrum of fix is [0,4] and it isn’t hard to suppose that that can be stretched to… well now… the paper continues to use [0,4]. Presumably that is enough. Nice to have recognised the [0,4] from some other works I am looking at.

FTW work with [0,4] because in the reduced algebra this is the spectrum of fix.


Back to FTW. If I rewrite the orthogonal quantum group character recurrence as:


And if I write the recurrence for the Chebyshev polynomials of the second kind:


If we give these are an argument and input x/2 we get the orthogonal group character recurrence. Now we are looking for the recurrence for the quantum permutation group characters:


Struggling again I once again consult work of Brannan (p.13)… euh I’m an idiot… that was not difficult.

Right, so the quantum permutation characters are


I am now going to focus on the quantum random transpositions (incidentally Freslon gave a talk on this topic here).

Now I have to back and look at Freslon’s first random walk paper.

Pure State Random Walks

Consider a pure state on \mathcal{O}(O_N^+). Restricted to the central algebra \mathcal{O}(O_N^+)_0 a pure state is still pure. And pure states on an abelian algebra are evaluation at points of the spectrum:


For O_N^+ the spectrum in the universal version (this is surely the same as the enveloping C*-algebra?) is [-N,N] so that for all t\in [-N,N] there is a central state on \mathcal{O}(O_N^+) defined by:

\displaystyle \varphi_t(n)=\frac{u_n(t)}{d_n}.

OK, I think the idea is to say, OK, we could define the state on the central algebra as \widetilde{\varphi_t}(u_n)=u_n(t)… and that could be written as \widetilde{\varphi_t}(n)=u_n(t). Instead Freslon chooses rather than u_n in the central algebra as a representative of n\in\text{Irr}(O_N^+), but u_n/d_n… and of course we know about d_n.

Now as a central state, and via the Upper Bound Lemma,

\displaystyle \|\varphi_t^{\star k}-h\|_{\text{TV}}\leq \frac{1}{4}\sum_{n=1}^{\infty}d_n\frac{u_n(t)^2k}{d_{n}^{2k-1}}

The power 2k-1 comes from the fact that the upper bound lemma involves a trace and there is a I_{V_n} lying around whose trace is d_n

Let us jump back to S_N^+ and consider \varphi_{N-2}(Q_N/d_N)… none the clearer on this… I get:

\displaystyle \varphi_{N-2}(\chi_1)=\frac{Q_1(N-2)}{N-1}

OK, I have cleared up the issue… I thought \chi_0+\chi_1=\text{fix} had to be a typo, but no it is correct.

Now! Finally we have that this other state \varphi_{\text{tr}} (which we must explore after this calculation):




So in the language of my paper in preparation, \varphi_{\text{tr}} is a quantum permutation with N-2 fixed points… the question for me would we have, for \xi_{\text{tr}} the cyclic vector in the GNS representation \pi_{\varphi_{\text{tr}}}(\text{fix})(\xi)=(N-2)\xi (all sorted now)?

Is \varphi_{\text{tr}}=\varphi_{N-2}? I find:

\displaystyle \varphi_{N-2}(\text{fix})=1+\frac{N-3}{N-1}.

OK, now I understand the confusion. It is the case that \varphi_{N-2}=\varphi_{\text{rt}} and both are simply evaluation at N-2… but \varphi_{N-2}(n)=Q_n(N-2)/Q_n(N) is only notation and not the same as \varphi_{N-2}(\chi_n)=\chi_n(N-2) and so \varphi_{N-2}(\text{fix})=N-2 indeed.

Some analysis

We will end with some analysis.

Any state on \mathcal{O}(\mathbb{G}) has a unique extension to a state on C(\mathbb{G}). Such a state is an element of the Fourier-Stieltjes algebra, the topological dual C(\mathbb{G})^* of C(\mathbb{G}). Denote the norm by \|\cdot \|_{\text{FS}}. We also have the topological double dual which I denote by \ell^{\infty}(\mathbb{G}). It can be shown then that:

\displaystyle \frac12 \|\varphi-\psi\|_{\text{FS}}=\sup_{p\in \mathcal{P}}|\varphi(p)-\psi(p)|,

where \mathcal{P} are the orthogonal projections in \ell^{\infty}(\mathbb{G}). Then this is used to define the total variation distance.

Now we turn to absolute continuity. Define an inner product on \mathcal{O}(\mathbb{G}) by \langle f,g\rangle=h(f^*g). Complete to L^2(\mathbb{G}) and \mathcal{O}(\mathbb{G}) embeds through left multiplication into B(L^2(\mathbb{G})). The weak closure of the embedding of \mathcal{O}(\mathbb{G}) in B(L^2(\mathbb{G})) is called L^{\infty}(\mathbb{G}) and is a vNa. If \varphi:\mathcal{O}(\mathbb{G})\rightarrow \mathbb{C} extends to a normal bounded map on L^{\infty}(\mathbb{G}), then \varphi becomes an element of the Fourier algebra which is the Banach space predual of L^{\infty}(\mathbb{G}) _* of L^{\infty}(\mathbb{G}), and, crucially (quoting from a heavy LCQG paper of Brannan and Ruan):


which further implies, if \varphi and \psi states on the algebra of regular functions extend to the vNa L^{\infty}(\mathbb{G}), that the total variation norm can be given as a supremum over projections in L^\infty(\mathbb{G}). Cool.