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

Abstract

A classical theorem of Frucht states that any finite group appears as the automorphism group of a finite graph. In the quantum setting the problem is to understand the structure of the compact quantum groups which can appear as quantum automorphism groups of finite graphs. We discuss here this question, notably with a number of negative results.

with Teo Banica, Glasgow Math J., to appear. Arxiv link here.

Abstract

An exposition of quantum permutation groups where an alternative to the ‘Gelfand picture’ of compact quantum groups is proposed. This point of view is inspired by algebraic quantum mechanics and posits that states on the algebra of continuous functions on a quantum permutation group can be interpreted as quantum permutations. This interpretation allows talk of an element of a compact quantum permutation group, and allows a clear understanding of the difference between deterministic, random, and quantum permutations. The interpretation is illustrated with the Kac-Paljutkin quantum group, the duals of finite groups, as well as by other finite quantum group phenomena.

Arxiv link here.

Giving a talk 17:00, September 1 2020:

See here for more.

Slides.

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.

Preliminaries

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:

uA=Au.

_______________________________________

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 »

Warning: This is written by a non-expert (I know only about finite quantum groups and am beginning to learn my compact quantum groups), and there is no attempt at rigour, or even consistency. Actually the post shows a wanton disregard for reason, and attempts to understand the incomprehensible and intuit the non-intuitive. Speculation would be too weak an adjective.

Groups

A group is a well-established object in the study of mathematics, and for the purposes of this post we can think of a group G as the set of symmetries on some kind of space, given by a set X together with some additional structure D(X). The elements of G  act on X as bijections:

G \ni g:X\rightarrow X,

such that D(X)=D(g(X)), that is the structure of the space is invariant under g.

For example, consider the space (X_n,|X_n|), where the set is X_n=\{1,2,\dots,n\}, and the structure is the cardinality. Then the set of all of the bijections X_n\rightarrow X_n is a group called S_n.

A set of symmetries G, a group, comes with some structure of its own. The identity map e:X\rightarrow X, x\mapsto x is a symmetry. By transitivity, symmetries g,h\in G can be composed to form a new symmetry gh:=g\circ h\in G. Finally, as bijections, symmetries have inverses g^{-1}, g(x)\mapsto x.

Note that:

gg^{-1}=g^{-1}g=e\Rightarrow (g^{-1})^{-1}=g.

A group can carry additional structure, for example, compact groups carry a topology in which the composition G\times G\rightarrow G and inverse {}^{-1}:G\rightarrow G are continuous.

Algebra of Functions

Given a group G together with its structure, one can define an algebra A(G) of complex valued functions on G, such that the multiplication A(G)\times A(G)\rightarrow A(G) is given by a commutative pointwise multiplication, for s\in G:

(f_1f_2)(s)=f_1(s)f_2(s)=(f_2f_1)(s).

Depending on the class of group (e.g. finite, matrix, compact, locally compact, etc.), there may be various choices and considerations for what algebra of functions to consider, but on the whole it is nice if given an algebra of functions A(G) we can reconstruct G.

Usually the following transpose maps will be considered in the structure of A(G), for some tensor product \otimes_\alpha such that A(G\times G)\cong A(G)\otimes_\alpha A(G), and m:G\times G\rightarrow G, (g,h)\mapsto gh is the group multiplication:

\begin{aligned}  \Delta: A(G)\rightarrow A(G)\otimes_{\alpha}A(G)&,\,f\mapsto f\circ m,\,\text{the comultiplication}  \\ S: A(G)\rightarrow A(G)&,\, f\mapsto f\circ {}^{-1},\,\text{ the antipode}  \\ \varepsilon: A(G)\rightarrow \mathbb{C}&,\, f\mapsto f\circ e,\,\text{ the counit}  \end{aligned}

See Section 2.2 to learn more about these maps and the relations between them for the case of the complex valued functions on finite groups.

Quantum Groups

Quantum groups, famously, do not have a single definition in the same way that groups do. All definitions I know about include a coassociative (see Section 2.2) comultiplication \Delta: A(G)\rightarrow A(G)\otimes_\alpha A(G) for some tensor product \otimes_\alpha (or perhaps only into a multiplier algebra M(A(G)\otimes_\alpha A(G))), but in general that structure alone can only give a quantum semigroup.

Here is a non-working (quickly broken?), meta-definition, inspired in the usual way by the famous Gelfand Theorem:

A quantum group G is given by an algebra of functions A(G) satisfying a set of axioms \Theta such that:

  • whenever A(G) is noncommutative, G is a virtual object,
  • every commutative algebra of functions satisfying \Theta is an algebra of functions on a set-of-points group, and
  • whenever commutative algebras of functions A(G_1)\cong_{\Theta} A(G_2), G_1\cong G_2 as set-of-points groups.

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: www-math.ucdenver.edu]:

cherry

(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.

Abstract

Necessary and sufficient conditions for a Markov chain to be ergodic are that the chain is irreducible and aperiodic. This result is manifest in the case of random walks on finite groups by a statement about the support of the driving probability: a random walk on a finite group is ergodic if and only if the support is not concentrated on a proper subgroup, nor on a coset of a proper normal subgroup. The study of random walks on finite groups extends naturally to the study of random walks on finite quantum groups, where a state on the algebra of functions plays the role of the driving probability. Necessary and sufficient conditions for ergodicity of a random walk on a finite quantum group are given on the support projection of the driving state.

Link to journal here.

In the hope of gleaning information for the study of aperiodic random walks on (finite) quantum groups, which I am struggling with here, by couching Freslon’s Proposition 3.2, in the language of Fagnola and Pellicer, and in the language of my (failed) attempts (see here, here, and here) to find the necessary and sufficient conditions for a random walk to be aperiodic. It will be necessary to extract the irreducibility and aperiodicity from Freslon’s rather ‘unilateral’ result.

Well… I have an inkling that because dual groups satisfy what I would call the condition of abelianness (under the ‘quantisation’ functor), all (quantum) subgroups are normal… this is probably an obvious thing to write down (although I must search the literature) to ensure it is indeed known (or is untrue?). Edit: Wang had it already, see the last proposition here.

Let F(G) be a the algebra of functions on a finite classical (as opposed to quantum) group G. This has the structure of both an algebra and a coalgebra, with an appropriate relationship between these two structures. By taking the dual, we get the group algebra, \mathbb{C}G=:F(\widehat{G}). The dual of the pointwise-multiplication in F(G) is a coproduct for the algebra of functions on the dual group \widehat{G}… this is all well known stuff.

Recall that the set of probabilities on a finite quantum group is the set of states M_p(G):=\mathcal{S}(F(G)), and this lives in the dual, and the dual of F(\widehat{G}) is F(G), and so probabilities on \widehat{G} are functions on G. To be positive is to be positive definite, and to be normalised to one is to have u(\delta^e)=1.

The ‘simplicity’ of the coproduct,

\Delta(\delta^g)=\delta^g\otimes\delta^g,

means that for u\in M_p(\widehat{G}),

(u\star u)(\delta^g)=(u\otimes u)\Delta(\delta^g)=u(\delta^g)^2,

so that, inductively, u^{\star k} is equal to the (pointwise-multiplication power) u^k.

The Haar state on \widehat{G} is equal to:

\displaystyle \pi:=\int_{\hat{G}}:=\delta_e,

and therefore necessary and sufficient conditions for the convergence of u^{\star k}\rightarrow \pi is that u is strict. It can be shown that for any u\in M_p(G) that |u(\delta^g)|\leq u(\delta^e)=1. Strictness is that this is a strict inequality for g\neq e, in which case it is obvious that u^{\star k}\rightarrow \delta_e.

Here is a finite version of Freslon’s result which holds for discrete groups.

Freslon’s Ergodic Theorem for (Finite) Group Algebras

Let u\in M_p(\widehat{G}) be a probability on the dual of finite group. The random walk generated by u is ergodic if and only if u is not-concentrated on a character on a non-trivial subgroup H\subset G.

Freslon’s proof passes through the following equivalent condition:

The random walk on \widehat{G} driven by u\in M_p(\widehat{G}) is not ergodic if u is bimodularwith respect to a non-trivial subgroup H\subset G, in the sense that

\displaystyle u(\underbrace{\delta^g\delta^h}_{=\delta^{gh}})=u(\delta^g)u(\delta^h)=u\left(\underbrace{\delta^h\delta^g}_{=\delta^{hg}}\right).

Before looking at the proof proper, we might note what happens when G is abelian, in which case \widehat{G} is a classical group, the set of characters on G.

To every positive definite function u\in M_p(\widehat{G}), we can associate a probability \nu_u\in M_p(\widehat{G}) such that:

\displaystyle u(\delta^g)=\sum_{\chi\in\hat{G}} \chi(\delta^g) \nu_u(\chi).

This is Bochner’s Theorem for finite abelian groups. This implies that positive definite functions on finite abelian groups are exactly convex combinations of characters.

Freslon’s condition says that to be not ergodic, u must be a character on a non-trivial subgroup H\subset G. Such characters can be extended in [G\,:\,H] ways.

Therefore, if u is not ergodic, u_{\left|H\right.}=\eta\in \widehat{H}.

For h\in H, we have

\displaystyle u(h)=\sum_{\chi\in\widehat{G}}\chi(h)\nu_u(\chi),

dividing both sides by u(h)=\eta(h)\neq 0 yields:

\displaystyle\sum_{\chi \in \widehat{G}} (\eta^{-1}\chi)(h)\nu_u (\chi)=1.

As \nu_u\in M_p(\widehat{G}), and (\eta^{-1}\chi)(h)\in \mathbb{T}, this implies that \nu_u is supported on characters such that, for all h\in H:

\eta^{-1}(h)\chi(h)=1\Rightarrow \chi=\eta\tilde{\chi},

such that \tilde{\chi}(H)=\{1\}. The set of such \tilde{\chi} is the annihilator of H in \widehat{G}, and it is a subgroup. Therefore \nu_u is concentrated on the coset of a normal subgroup (as all subgroups of an abelian group are normal).

This, via Pontragin duality, is not looking at the ‘support’ of u, but rather of \nu_u. Although we denote \mathbb{C}G=:F(\widehat{G}), and when G is abelian, \widehat{G} is a group (unnaturally, of characters) isomorphic to G. Is it the case though that,

\Delta(\chi)=\chi\otimes\chi

gives the same object in as

\displaystyle\Delta(\chi)=\sum_{g\in G}\chi(\delta^g)\Delta(\delta_g)

\displaystyle =\sum_{g\in G}\chi(\delta^g)\sum_{t\in G}\delta_{gt^{-1}}\otimes \delta_t?

Well… of course this is true because \chi(gh)=\chi(g)\chi(h).

We could proceed to look at Fagnola & Pellicer’s work but first let us prove Freslon’s result, hopefully in the finite case the analysis disappears…

Proof: Assume that u is not strict and let

\Lambda:=|u|^{-1}(\{1\}).

There exists a unitary representation \Phi:G\rightarrow B(H) and a unit vector \xi such that

u(g)=\langle \Phi(g)\xi,\xi\rangle

Cauchy-Schwarz implies that

|u(g)|\leq \|\Phi(g)\xi\|\|\xi\|=\|\xi\|^2.

If h is not strict there is an h such that this is an inequality and so \Phi(h)\xi is colinear to \xi, it follows that \Phi(h)\xi=u(h)\xi.

This implies for h\in \Lambda and g\in G:

|u(gh)|=|\langle \Phi(gh)\xi,\xi\rangle|=|u(h)||\langle \Phi(g)\xi,\xi\rangle|=|u(g)|,

and so \Lambda is closed under multiplication. Also u(g^{-1})=\overline{u(g)} and so \Lambda and so \Lambda is a subgroup. It follows that u is a character on \Lambda, which is not trivial because u is not strict.

I don’t really need to go through the third equivalent condition. If u coincides with a character on a subgroup \Lambda, for h\in \Lambda

|u(h)|^2=u(h)\overline{u(h)}=u(h)u(h^{-1})=u(e)=1,

and so u is not strict \bullet

Now let us look at the language of Fagnola and Pellicer. What is a projection in \mathbb{C}G? First note the involution in \mathbb{C}G is (\delta^g)^*=\delta^{g^{-1}}. The second multiplication is the convolution. This means projections in the algebra are symmetric with respect to the group inverses and they are also idempotents. They are actually equal to Haar states on finite subgroups.

I think periodicity is also wrapped up in Freslon’s result as I think all subgroups of dual groups are normal. Perhaps, oddly, not being concentrated on a subgroup means that the positive function (probability on the dual) is one on that subgroup…

Well… let us start with irreducible. Suppose u fails to be ergodic because it is irreducible. This means there is a projection p_H=\int_H such that that P_u(p_H)=p_H (and support u less than p_H?)

Let us look at the first condition:

P_u(p_H)=(u\otimes I)\Delta(p_H)=\cdots=\frac{1}{|H|}\sum_{h\in H}u(h)\delta^h=p_H\Rightarrow u_{\left|H\right.}=1.

What now is the support of u? Well… some work I have done offline shows that the special projections, the group-like projections, correspond to to \pi_H for H a subgroup of G.  If u is reducible, it is concentrated on such a quasi-subgroup, and this means that u coincides with a trivial character on H. In terms of Fagnola Pellicer, P_u(\pi_H)=\pi_H.

Now let us tackle aperiodicity. It is going to correspond, I think, with being concentrated on a ‘coset’ of a non-trivial character on H

Well, we can show that if u is periodic, there is a subset S\subset G such that u(s)=e^{2\pi i a_s/d} for all s\in S. We can use Freslon’s proof to show that S is in a subgroup on which |u|=1.

Now what I want to do is put this in the language of ‘inclusion’ matrices… but the inclusions for cocommutative quantum groups are trivial so no go…

We can reduce Freslon’s conditions down to irreducible and aperiodic: not coinciding with a trivial character, and not coinciding with a character.

 

 

In my pursuit of an Ergodic Theorem for Random Walks on (probably finite) Quantum Groups, I have been looking at analogues of Irreducible and Periodic. I have, more or less, got a handle on irreducibility, but I am better at periodicity than aperiodicity.

The question of how to generalise these notions from the (finite) classical to noncommutative world has already been considered in a paper (whose title is the title of this post) of Fagnola and Pellicer. I can use their definition of periodic, and show that the definition of irreducible that I use is equivalent. This post is based largely on that paper.

Introduction

Consider a random walk on a finite group G driven by \nu\in M_p(G). The state of the random walk after k steps is given by \nu^{\star k}, defined inductively (on the algebra of functions level) by the associative

\nu\star \nu=(\nu\otimes\nu)\circ \Delta.

The convolution is also implemented by right multiplication by the stochastic operator:

\nu\star \nu=\nu P,

where P\in L(F(G)) has entries, with respect to a basis (\delta_{g_i})_{i\geq 1} P_{ij}=\nu(g_jg_{i^{-1}}). Furthermore, therefore

\nu^{\star k}=\varepsilon P^k,

and so the stochastic operator P describes the random walk just as well as the driving probabilty \nu.

The random walk driven by \nu is said to be irreducible if for all g_\ell\in G, there exists k\in\mathbb{N} such that (if g_1=e) [P^k]_{1\ell}>0.

The period of the random walk is defined by:

\displaystyle \gcd\left(d\in\mathbb{N}:[P^d]_{11}>0\right).

The random walk is said to be aperiodic if the period of the random walk is one.

These statements have counterparts on the set level.

If P is not irreducible, there exists a proper subset of G, say S\subsetneq G, such that the set of functions supported on S are P-invariant.  It turns out that S is a proper subgroup of G.

Moreover, when P is irreducible, the period is the greatest common divisor of all the natural numbers d such that there exists a partition S_0, S_1, \dots, S_{d-1} of G such that the subalgebras A_k of functions supported in S_k satisfy:

P(A_k)=A_{k-1} and P(A_{0})=A_{d-1} (slight typo in the paper here).

In fact, in this case it is necessarily the case that \nu is concentrated on a coset of a proper normal subgroup N\rhd G, say gN. Then S_k=g^kN.

Suppose that f is supported on g^kNWe want to show that for Pf\in A_{k-1}Recall that 

\nu^{\star k-1}P(f)=\nu^{\star k}(f).

This shows how the stochastic operator reduces the index P(A_k)=A_{k-1}.

A central component of Fagnola and Pellicer’s paper are results about how the decomposition of a stochastic operator:

P(f)=\sum_{\ell}L_\ell^*fL_{\ell},

specifically the maps L_\ell can speak to the irreducibility and periodicity of the random walk given by P. I am not convinced that I need these results (even though I show how they are applicable).

Stochastic Operators and Operator Algebras

Let F(X) be a \mathrm{C}^*-algebra (so that X is in general a  virtual object). A \mathrm{C}^*-subalgebra F(Y) is hereditary if whenever f\in F(X)^+ and h\in F(Y)^+, and f\leq h, then f\in F(Y)^+.

It can be shown that if F(Y) is a hereditary subalgebra of F(X) that there exists a projection \mathbf{1}_Y\in F(X) such that:

F(Y)=\mathbf{1}_YF(X)\mathbf{1}_Y.

All hereditary subalgebras are of this form.

Read the rest of this entry »

In the case of a finite classical group G, we can show that if we have i.i.d. random variables \zeta_i\sim\nu\in M_p(G), that if \text{supp }\nu\subset Ng, for Ng a coset of a proper normal subgroup N\rhd G, that the random walk on G driven by \nu, the random variables:

\xi_k=\zeta_k\cdots \zeta_1,

exhibits a periodicity because

\xi_k\in Ng^{k}.

This shows that a necessary condition for ergodicity of a random walk on a finite classical group G driven by \nu\in M_p(G) is that the support of \nu not be concentrated on the coset of a proper normal subgroup.

I had hoped that something similar might hold for the case of random walks on finite quantum groups but alas I think I have found a barrier.

Read the rest of this entry »

%d bloggers like this: