You are currently browsing the category archive for the ‘arXiv’ category.

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.

Read the rest of this entry »

This post follows on from this one. The purpose of posts in this category is for me to learn more about the research being done in quantum groups. This post looks at this paper of Schmidt.


Compact Matrix Quantum Groups

The author gives the definition and gives the definition of a (left, quantum) group action.

Definition 1.2

Let G be a compact matrix quantum group and let C(X) be a \mathrm{C}^*-algebra. An (left) action of G on X is a unital *-homomorphism \alpha: C(X)\rightarrow C(X)\otimes C(G) that satisfies the analogue of g_2(g_1x)=(g_2g_1)x, and the Podlés density condition:

\displaystyle \overline{\text{span}(\alpha(C(X)))(\mathbf{1}_X\otimes C(G))}=C(X)\otimes C(G).

Quantum Automorphism Groups of Finite Graphs

Schmidt in this earlier paper gives a slightly different presentation of \text{QAut }\Gamma. The definition given here I understand:

Definition 1.3

The quantum automorphism group of a finite graph \Gamma=(V,E) with adjacency matrix A is given by the universal \mathrm{C}^*-algebra C(\text{QAut }\Gamma) generated by u\in M_n(C(\text{QAut }\Gamma)) such that the rows and columns of u are partitions of unity and:



The difference between this definition and the one given in the subsequent paper is that in the subsequent paper the quantum automorphism group is given as a quotient of C(S_n^+) by the ideal given by \mathcal{I}=\langle Au=uA\rangle… ah but this is more or less the definition of universal \mathrm{C}^*-algebras given by generators E and relations R:

\displaystyle \mathrm{C}^*(E,R)=\mathrm{C}^*( E)/\langle \mathcal{R}\rangle

\displaystyle \Rightarrow \mathrm{C}^*(E,R)/\langle I\rangle=\left(\mathrm{C}^*(E)/R\right)/\langle I\rangle=\mathrm{C}*(E)/(\langle R\rangle\cap\langle I\rangle)=\mathrm{C}^*(E,R\cap I)

where presumably \langle R\rangle \cap \langle I \rangle=\langle R\cap I\rangle all works out OK, and it can be shown that I is a suitable ideal, a Hopf ideal. I don’t know how it took me so long to figure that out… Presumably the point of quotienting by (a presumably Hopf) ideal is so that the quotient gives a subgroup, in this case \text{QAut }\Gamma\leq S_{|V|}^+ via the surjective *-homomorphism:

C(S_n^+)\rightarrow C(S_n^+)/\langle uA=Au\rangle=C(\text{QAut }\Gamma).


Compact Matrix Quantum Groups acting on Graphs

Definition 1.6

Let \Gamma be a finite graph and G a compact matrix quantum group. An action of G on \Gamma is an action of G on V (coaction of C(G) on C(V)) such that the associated magic unitary v=(v_{ij})_{i,j=1,\dots,|V|}, given by:

\displaystyle \alpha(\delta_j)=\sum_{i=1}^{|V|} \delta_i\otimes v_{ij},

commutes with the adjacency matrix, uA=Au.

By the universal property, we have G\leq \text{QAut }\Gamma via the surjective *-homomorphism:

C(\text{QAut }\Gamma)\rightarrow C(G), u\mapsto v.

Theorem 1.8 (Banica)

Let X_n=\{1,\dots,n\}, and \alpha:F(X_n)\rightarrow F(X_n)\otimes C(G), \alpha(\delta_j)=\sum_i\delta_i\otimes v_{ij} be an action, and let F(K) be a linear subspace given by a subset K\subset X_n. The matrix v commutes with the projection onto F(K) if and only if \alpha(F(K))\subseteq F(K)\otimes C(G)

Corollary 1.9

The action \alpha: F(V)\rightarrow F(V)\otimes C(\text{QAut }\Gamma) preserves the eigenspaces of A:

\alpha(E_\lambda)\subseteq E_\lambda\otimes C(\text{QAut }\Gamma)

Proof: Spectral decomposition yields that each E_\lambda, or rather the projection P_\lambda onto it, satisfies a polynomial in A:

\displaystyle P_\lambda=\sum_{i}c_iA^i

\displaystyle \Rightarrow P_\lambda A=\left(\sum_i c_i A^i\right)A=A P_\lambda,

as A commutes with powers of A \qquad \bullet

A Criterion for a Graph to have Quantum Symmetry

Definition 2.1

Let V=\{1,\dots,|V|\}. Permutations \sigma,\,\tau: V\rightarrow V are disjoint if \sigma(i)\neq i\Rightarrow \tau(i)=i, and vice versa, for all i\in V.

In other words, we don’t have \sigma and \tau permuting any vertex.

Theorem 2.2

Let \Gamma be a finite graph. If there exists two non-trivial, disjoint automorphisms \sigma,\tau\in\text{Aut }\Gamma, such that o(\sigma)=n and o(\tau)=m, then we get a surjective *-homomorphism C(\text{QAut }\Gamma)\rightarrow C^*(\mathbb{Z}_n\ast \mathbb{Z}_m). In this case, we have the quantum group \widehat{\mathbb{Z}_n\ast \mathbb{Z}_m}\leq \text{QAut }\Gamma, and so \Gamma has quantum symmetry.

Read the rest of this entry »

Some notes on this paper.

1. Introduction and Main Results

A tree has no symmetry if its automorphism group is trivial. Erdos and Rényi showed that the probability that a random tree on n vertices has no symmetry goes to zero as n\rightarrow \infty.

Banica (after Bichon) wrote down with clarity the quantum automorphism group of a graph. It contains the usual automorphism group. When it is larger, the graph is said to have quantum symmetry.

Lupini, Mancinska, and Roberson show that almost all graphs are quantum antisymmetric. I am fairly sure this means that almost all graphs have no quantum symmetry, and furthermore for almost all (as n\rightarrow \infty) graphs the automorphism group is trivial.

The paper in question hopes to show that almost all trees have quantum symmetry — but at this point I am not sure if this is saying that the quantum automorphism group is larger than the classical.

2. Preliminaries

2.1 Graphs and Trees

Standard definitions. No multi-edges. Undirected if the edge relation is symmetric. As it is dealing with trees, this paper is concerned with undirected graphs without loops, and identify V=\{v_1,\dots,v_n\}\cong \{1,2,\dots,n\}. A path is a sequence of edges. We will not see cycles if we are discussing trees. Neither will we talk about disconnected graphs: a tree is a connected graph without cycles (this throws out loops actually.

The adjacency matrix of a graph is a matrix A=(a_{ik})_{i,j\in V} with a_{ij}=1 iff there is an edge connected i and j. The adjacency matrix is symmetric.

2.2 Symmetries of Graphs

An automorphism of a graph \Gamma is a permutation of V that preserves adjacency and non-adjacency. The set of all such automorphisms, \text{Aut }\Gamma, is a group where the group law is composition. It is a subgroup of S_n, and S_n itself can be embedded as permutation matrices in M_n(\mathbb{C}). We then have

\text{Aut }\Gamma=\{\sigma\in S_n\,:\,\sigma A=A\sigma\}\subseteq S_n.

If \text{Aut }\Gamma=\{e\}, it is asymmetric. Otherwise it is or rather has symmetry.

2.3 Compact Matrix Quantum Groups

compact matrix quantum group is a pair (C(G),u), where C(G) is a unital \mathrm{C}^\ast-algebra, and u=(u_{ij})_{i,j=1}^n\in M_n(C(G)) is such that:

  • C(G) is generated by the u_{ij},
  • There exists a morphism \Delta:C(G)\rightarrow C(G)\otimes C(G), such that \Delta(u_{ij})=\sum_{k=1}^n u_{ik}\otimes u_{kj}
  • u and u^T are invertible (Timmermann only asks that \overline{u}=(u_{ij}^\ast) be invertible)

The classic example (indeed commutative examples all take this form) is a compact matrix group G\subseteq U_n(\mathbb{C}) and u_{ij}:G\rightarrow \mathbb{C} the coordinates of G.

Example 2.3

The algebra of continuous functions on the quantum permutation group S_n^+ is generated by n^2 projections u_{ij} such that the row sums and column sums of u=(u_{ij}) both equal \mathbf{1}_{S_n^+}.

The map \varphi:C(S_{n}^+)\rightarrow C(S_n), u_{ij}\mapsto \mathbf{1}_{\{\sigma\in S_n\,|\,\sigma(j)=i\}} is a surjective morphism that is an isomorphism for n=1,2,3, so that the sets \{1\},\,\{1,2\},\,\{1,2,3\} have no quantum symmetries.

2.4 Quantum Symmetries of Graphs

Definition 2.4 (Banica after Bichon)

Let \Gamma=(V,E) be a graph on n vertices without multiple edges not loops, and let A be its adjacency matrix. The quantum automorphism group \text{QAut }\Gamma is defined as the compact matrix group with \mathrm{C}^\ast-algebra:

\displaystyle C(\text{QAut }\Gamma)=C(S_n^+)/\langle uA=Au\rangle

For me, not the authors, this requires some work. Banica says that \langle uA=Au\rangle is a Hopf ideal.

Hopf ideal is a closed *-ideal I\subset C(G) such that

\Delta(I)\subset C(G)\otimes I+I\otimes C(G).

Classically, I the set of functions vanishing on a distinguished subgroup. The quotient map is f\mapsto f+I, and f+I=g+I if their difference is in I, that is if they agree on the subgroup.

The classical version of Au=uA ends up as a_{ij}=a_{\sigma(i)\sigma(j)}… the group in question the classical \text{Aut }\Gamma. In that sense perhaps Au=uA might be better given as fA=Af.

Easiest thing first, is it a *-ideal? Well, take the adjoint of fA=Af\Rightarrow A^*f^*=f^*A^* and A=A^* so I is *closed. Suppose f\in I and g\in C(S_n^+)… I cannot prove that this is an ideal! But time to move on.

3. The Existence of Two Cherries

In this section the authors will show that almost all trees have two cherries. Definition 3.4 says with clarity what a cherry is, here I use an image [credit:]:


(3,5,4) and (7,9,8) are cherries

Remark 3.2

If a graph admits a cherry (u_1,u_2,v), the transposition (u_1\quad u_2) is a non-trivial automorphism.

Theorem 3.3 (Erdos, Réyni)

Almost all trees contains at least one cherry in the sense that

\displaystyle \lim_{n\rightarrow \infty}\mathbb{P}[C_n\geq 1]=1,

where C_n is #cherries in a (uniformly chosen) random tree on n vertices.

Corollary 4.3

Almost all trees have symmetry. 

The paper claims in fact that almost all trees have at least two cherries. This will allow some S_4^+ action to take place. This can be seen in this paper which is the next point of interest.

%d bloggers like this: