text:
# Transcending the Limits of Turing ComputabilityVAA is grateful for partial support from the USA Civil Research and Development Foundation (CRDF grant UM1-2090); CSC and BSP have been partially supported by the Auckland University Vice-Chancellor’s Development Fund 23124; BSP was also partially supported by JSPS(L02704) and RFFI(01149) grants.

## 1 Introduction

Hypercomputation or super-Turing computation is a “computation” that transcends the limit imposed by Turing’s model of computability; for a recent perspective see the special issue of the journal Minds and Machines (12, 4, 2002). Currently there are various proposals to break Turing’ Barrier by showing that certain classes of computing procedures have super-Turing power (see ). A specific class of computing procedures,  make essential use of some physical theory, relativity theory in , quantum theory ; they all reflect an attitude advocated by Landauer  (information is inevitably physical) and Deutsch  (the reason why we find it possible to construct, say, electronic calculators, and indeed why we can perform mental arithmetic …is that the laws of physics “happen” to permit the existence of physical models for the operations of arithmetic).

The aim of the present paper is to revisit the solutions offered in . We will focus on the novelty of the approach and we will discuss its power and its limits. No proofs will be offered.

## 2 The Classical Merchant Problem

Recall that in the classical version of the Merchant Problem we have $`10`$ stacks of coins, each stack containing $`100`$ coins, and we know that at most one stack contains only false coins, weighting $`1.01g`$; true coins weight $`1g`$. The problem is to find the stack with false coins (if any) by only one weighting. The classical solution reduces the problem to the weighting of a special combination of coins: one coin from the first stack, two coins from the second stack, …, ten coins from the tenth stack. If the false coins are present in the $`N`$-th stack, then the weight of the combination will be $`55+\frac{N}{100}g`$; otherwise the weight is just $`55g`$. The Merchant Problem quoted above was widely spread in allies armies during the Second World War, cf. . Probably the elegant solution described above was the very first solution of a computational problem bearing typical features of quantum computing, see an extended discussion in .

## 3 The Infinite Merchant Problem

In what follows we are going to consider the following generalization of the problem, the Infinite Merchant Problem: we assume that we have countable many stacks, given in some computable way, all of them, except at most one, containing true coins only. True coins weight $`1`$ and false coins weight $`1+2^j`$, $`j>0`$. Again we are allowed to take a coin from each stack and we want to determine whether all coins are true or there is a stack of false coins.

Next we will show that the Infinite Merchant Problem is classically undecidable by reducing it to the Halting Problem, i.e. the problem to decide whether an arbitrary Turing machine (TM) halts on an arbitrary input. Assume that a TM operates on positive integers and suppose, for the sake of contradiction, that there exists a TM HALT which can decide whether a TM $`T`$ (given by its code $`\mathrm{\#}T`$, a positive integer) eventually stops on input $`x`$:

$$\mathrm{𝙷𝙰𝙻𝚃}(\mathrm{\#}T,x)=\{\begin{array}{cc}1,\hfill & \text{if }T(x)\text{ stops,}\hfill \\ 0,\hfill & \text{otherwise.}\hfill \end{array}$$

We construct a TM $`Q`$

$$Q(x)=\{\begin{array}{cc}1,\hfill & \text{if }\mathrm{𝙷𝙰𝙻𝚃}(x,x)=0,\text{ }\hfill \\ \text{loops forever},\hfill & \text{otherwise,}\hfill \end{array}$$

and deduce the contradiction:

$$\mathrm{𝙷𝙰𝙻𝚃}(\mathrm{\#}Q,\mathrm{\#}Q)=1\text{ iff }\mathrm{𝙷𝙰𝙻𝚃}(\mathrm{\#}Q,\mathrm{\#}Q)=0.$$

We next describe the reduction. Assume that we have a classical solution of the Infinite Merchant Problem and we are given a TM $`T`$ and an input $`x`$ for $`T`$. We construct a computable sequence $`q_1,q_2,\mathrm{}q_i\mathrm{}`$ as follows: if the computation of $`T(x)`$ did not stop till the $`i`$-th step, then we put $`q_i=1`$; if the computation halted at step $`i_0`$, then we put $`q_{i_0}=1+2^j`$ and $`q_r=1`$, for all $`r>i_0`$. The sequence $`q_i`$ satisfies all conditions of the Infinite Merchant Problem and $`T(x)`$ halts if and only if there is a false coin, i.e., $`q_{i_0}=1+2^j`$, for some $`j`$. This shows that the Infinite Merchant Problem is undecidable as the Halting Problem is undecidable.

In fact the two problems are equivalent. Indeed, assume that we could classically solve the Halting Problem. To every sequence $`(q_i)`$ satisfying the conditions of the Infinite Merchant Problem we associate the TM $`T`$ such that $`T(i)=1`$ if $`q_i=1`$, and $`T(i)=0`$ otherwise. The TM $`T^{}`$ defined by $`T^{}(0)=\mathrm{min}\{iT(i)=0\}`$ halts at $`0`$ if and only if there an $`i_0`$ such that $`q_{i_0}=1+2^j`$, i.e., $`T^{}(0)`$ halts if and only if there are false coins in the system. Hence, a classical solution of the Halting Problem will produce a classical solution for the Infinite Merchant Problem.

The above discussion shows that undecidability is determined by the impossibility to decide in a finite time the answers to an infinite number of questions, “does the first stack contain a false coin?”, “does the second stack contain a false coin?”, etc. This might be caused either by the fact that the time of the computation grows indefinitely or by the fact that the space of computation grows indefinitely or both. The classical theories of computability and complexity (see, for example, ) do not give any indication in this respect. In the following section we will show that time can be made finite provided we use a specific probabilistic strategy.

## 4 A Probabilistic Solution

In this section we present, in a slightly different way, the probabilistic solution proposed in . We will adopt the following strategy. We are given a probability $`\theta =2^n`$ and we assume that we work with a “device” described below111As in  we use quotation marks when referring to our mathematical “device”. with sensitivity given by a real $`\epsilon =2^m`$. Then, we compute classically a time $`T=T_{\theta ,\epsilon }`$ and run the “device” on a random input for the time $`T`$. If we get a click, then the system has false coins; if we don not get a click, then we conclude that with probability greater than $`1\theta `$ all coins are true. An essential part of the method is the requirement that the time limit $`T`$ is classically computable.

The “device” (with sensitivity $`\epsilon `$) will distinguish the values of the iterated quadratic form $`𝐐^t(𝐱),𝐱=_{i=1}^{\mathrm{}}q_i^t|x_i|^2,`$ by observing the difference between averaging over trajectories of two discrete random walks with two non-perturbed and perturbed sequences $`t_l,\stackrel{~}{t}_l`$ of “stops”. The non-perturbed sequence corresponds to equal steps $`\delta _m=1`$, $`t_l=_{m=0}^l\delta _m`$, and the perturbed corresponds to the varying steps $`\mathrm{\Delta }_m,\mathrm{\hspace{0.17em}0}<\mathrm{\Delta }_m<\delta _m,\stackrel{~}{t}_l=_{m=0}^l\mathrm{\Delta }_m.`$ We work with the intersections of $`l_2`$ with the discrete Sobolev class $`l_2^1`$ of square-summable sequences with the square norm

$$𝐱_1^2=\underset{_{_{m=1}}}{\overset{\mathrm{}}{}}|x__mx_{_{m1}}|^2,$$
(1)
and the discrete Sobolev class $`\stackrel{~}{l}_2^1`$ of weighted-summable sequences with the square norm

$$𝐱_1^2=\underset{_{_{m=1}}}{\overset{\mathrm{}}{}}\frac{1\mathrm{\Delta }_m}{\mathrm{\Delta }_m}|x__mx_{_{m1}}|^2.$$
(2)
By natural extension from cylindrical sets we can define the Wiener measures $`\stackrel{~}{W}`$ and $`W`$ on the spaces of trajectories of the perturbed and non-perturbed random walks respectively and use the absolute continuity $`\stackrel{~}{W}`$ with respect to $`W`$: that is for every $`W`$–measurable set $`\mathrm{\Omega }`$,

$$\stackrel{~}{W}(\mathrm{\Omega })=\frac{1}{_{l=1}^{\mathrm{}}\sqrt{\mathrm{\Delta }_l}}_\mathrm{\Omega }e^{_{m=1}^{\mathrm{}}\frac{1\mathrm{\Delta }_m}{\mathrm{\Delta }_m}x_mx_{m1}^2}𝑑W.$$

Assume that the “device” revealing the exponential growth of the quadratic form of the iterations $`𝐐^t(𝐱),𝐱`$ clicks if

$$𝐐^t(𝐱),𝐱𝐱^2+\epsilon 𝐱_1^2.$$

Thus the “device” sensitivity is defined in terms of the Sobolev norm.

Two cases may appear. If for some $`T>0`$, $`𝐐^T(𝐱),𝐱𝐱^2+\epsilon 𝐱_1^2,`$ then the “device” has clicked and we know for sure that there exist false coins in the system. However, it is possible that at some time $`T>0`$ the “device” hasn’t (yet?) clicked because $`𝐐^t(𝐱),𝐱<𝐱^2+\epsilon 𝐱_1^2.`$ This may happen because either all coins are true, i.e., $`𝐐^t(𝐱),𝐱<𝐱^2+\epsilon 𝐱_1^2`$, for all $`t>0`$, or because at time $`T`$ the growth of $`𝐐^T(𝐱),𝐱`$ hasn’t yet reached the threshold $`𝐱^2+\epsilon 𝐱_1^2`$. In the first case the “device” will never click, so at each stage $`t`$ the test-vector $`𝐱`$ produces “true” information; we can call $`𝐱`$ a “true” vector. In the second case, the test-vector $`𝐱`$ is “lying” at time $`T`$ as we do have false coins in the system, but they were not detected at time $`T`$; we say that $`𝐱`$ produces “false” information at time $`T`$.

If we assume that there exist false coins in the system, say at stack $`j`$, but the “device” does not click at the moment $`T`$, then the test-vector $`𝐱`$ belongs to the indistinguishable set

$$_{\epsilon ,T}=\{𝐱l_2^1((1+\gamma )^T1)x_j^2<\epsilon 𝐱_1^2,\text{for some }j\}.$$

In  it was proven that the Wiener measure of the indistinguishable set tends to zero as $`T\mathrm{}`$:

$$\stackrel{~}{W}(_{\epsilon ,T})\left(\frac{\epsilon }{((1+\gamma )^T1\epsilon )_{m=1}^{\mathrm{}}\mathrm{\Delta }_m}\right)^{1/2}.$$

This fact is not enough to realize the scheme described in the beginning of this section: we need a more precise result, namely we have to prove that $`\stackrel{~}{W}(_{\epsilon ,T})`$ converges computably to zero. And, indeed, this is true because:

$$\stackrel{~}{W}(_{\epsilon ,T})\eta ,\text{ provided }t>\mathrm{log}_{1+\gamma }\left(\frac{\epsilon }{\eta ^2_{m=1}^{\mathrm{}}\mathrm{\Delta }_m}+1+\epsilon \right).$$

Denote by $`P(𝒩)`$ the a priori probability of absence of false coins in the system. Then, the a posteriori probability that the system contains only true coins, when the “device” did not click after running the experiment for the time $`T`$, is

$$𝐏_{\text{non-click}}(𝒩)>1\frac{1P(𝒩)}{P(𝒩)}\frac{\sqrt{\epsilon }}{\sqrt{(1+\gamma )^T1\epsilon }\sqrt{_{m=1}^{\mathrm{}}\mathrm{\Delta }_m}}\text{.}$$

## 5 A Brownian Solution Based on Resonance Amplification

In  the idea to consider a single act of quantum computation as a scattering process was suggested.

We will first illustrate the method by describing a simple quantum scattering system realizing the quantum $`C_{\text{NOT}}`$ gate, i.e., a quantum gate satisfying exactly to the same truth-table as the classical controlled-NOT gate. The $`C_{\text{NOT}}`$ device has two input and output channels. Each channel can be only in two different states, say $`|0,|1`$. The in and out states of the control-channel are the same, $`|I_{in}=|I_{out}`$, but the in and out states of the current-channel may be different, $`|J_{in}|J_{out},`$ depending upon the state $`|J_{in}`$ and the control-channel state. The classical controlled-NOT gate has the following truth-table:

$$\begin{array}{cccc}I_{in}& J_{in}& I_{out}& J_{out}\\ & & & \\ & & & \\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 1\\ 1& 1& 1& 0\end{array}$$

which describes the effect of the device on the above in states,

$$\begin{array}{ccc}|I_{in}J_{in}& & |I_{out}J_{out}\\ & & \\ & & \\ |\mathrm{0\hspace{0.17em}\hspace{0.17em}0}& & |\mathrm{0\hspace{0.17em}\hspace{0.17em}0}\\ |\mathrm{0\hspace{0.17em}\hspace{0.17em}1}& & |\mathrm{0\hspace{0.17em}\hspace{0.17em}1}\\ |\mathrm{1\hspace{0.17em}\hspace{0.17em}0}& & |\mathrm{1\hspace{0.17em}\hspace{0.17em}1}\\ |\mathrm{1\hspace{0.17em}\hspace{0.17em}1}& & |\mathrm{1\hspace{0.17em}\hspace{0.17em}0}\end{array}$$

The quantum $`C_{\text{NOT}}`$ gate operates not only on the “classical” states $`|0`$ and $`|1`$, ($`C_{\text{NOT}}|ij=|ik`$, where $`i,j\{0,1\}`$ $`k=ij`$ (mod 2)), but also on all their linear combinations,

$$\alpha _{00}|00+\alpha _{01}|01+\alpha _{10}|10+\alpha _{11}|11\alpha _{00}|00+\alpha _{01}|01+\alpha _{10}|11+\alpha _{11}|10.$$

This quantum transformation can be presented via the unitary matrix

$$U=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right),$$
(3)
with respect to the canonical basis $`(e_1,e_2,e_3,e_4)=(|00,|01,|10,|11)`$. More importantly, $`C_{\text{NOT}}`$ in combination with all 1-qubit gates is universal 222Every classically computable function can be computed by a small universal set of gates like $`\{`$OR, NOT$`\}`$ or $`\{`$NAND$`\}`$. A set of quantum gates $`𝒮`$ is called universal if any unitary operation can be approximated with an arbitrary accuracy by a quantum circuit involving gates in $`𝒮`$; see more in . and it cannot be written as a tensor product of two binary operators $`U=U_1U_2,U_lI`$.

We claim that the matrix $`U`$ in (3) can be realized as a scattering matrix of a special quantum dot. First, here is the motivation. Consider Figure 1 in which two isolated quantum wires are placed in proximity and there is a window region in which the two wires are coupled. An electron moving in the window region oscillates between the two quantum wires and the probability of the electron exiting into a specific quantum wire depends on the length of the window. This “switching phenomenon” was discovered by del Alamo and Eugster  and intensely discussed in literature, see for instance . We can arrange the setup in such a way that, under normal conditions, the electron exits from the same wire it enters, but switches to the other wire when a classical extra potential is applied, a realization of the $`C_{\text{NOT}}`$ relay. If the control is quantum too, then we obtain the $`C_{\text{NOT}}`$ gate.

We continue with the mathematical model and assume that the quantum dot is inserted in an one-dimensional quantum wire $`𝐑=(\mathrm{},\mathrm{})=𝐑_+𝐑_{}`$ between the wires $`𝐑_+,𝐑_{}`$ and a single electron may be redirected according to the state of the dot.

We assume also that the inner Hamiltonian of the quantum dot is presented by a finite or an infinite diagonal matrix $`A=\text{diag}\{\alpha _1^2,\alpha _2^2,\mathrm{},\alpha _N^2,\mathrm{}\}`$ with positive diagonal elements $`\alpha _1^2<\alpha _2^2<\alpha _3^2<\mathrm{}<\alpha _N^2<\mathrm{}`$. We assume that the quantum dot is inserted in an one-dimensional quantum wire $`\mathrm{}<x<\mathrm{}`$ at the origin and a proper boundary condition is satisfied (see (9)) for connecting it with the Schrödinger operator on the wire defined in the space of square-integrable vector-functions $`L_2(𝐑_+,)`$ with values in the infinitely-dimensional Hilbert space $``$

$$l=\frac{d^2}{dx^2}$$
(4)
One could assign to the above quantum system a product space $`H_eH_d`$ constituted respectively by the states of the electron and the states of the dot, and consider an evolution of the system generated by the total Hamiltonian $`_e+_d+_{int}`$ with a proper interaction term. This would lead to a quite sophisticated problem of quantum mechanics, similar to three-body problems, see for instance . We assume now that the state of the dot is selected independently and thus reduce the above problem to the corresponding one-body problem for an electron scattered in the quantum wire depending on the state of the dot. The corresponding device should be called rather quantum relay rather than quantum gate; however, it may be transformed into a quantum gate if the state of the dot is obtained as a quantum state with finite life-time. Practically the model suggested below is acceptable if the life-time of the state of the dot is long enough during the scattering experiment.The corresponding general “zero-range” quantum Hamiltonian (solvable model) is described as a self-adjoint extension $`𝐀_\beta `$ of the orthogonal sum $`lA`$ restricted to $`l_0A_0`$ in $`L_2(𝐑,)E`$ onto a proper domain; here $``$ is the infinitely-dimensional input space and $`E`$ is the inner space (with dim $`(E)2`$). The spectrum $`\sigma _\beta `$ of the operator $`𝐀_\beta `$ is absolutely-continuous and fills the positive half-axis $`\lambda 0`$ with multiplicity dim $`()`$. The role of eigen-functions of the spectral point $`p^2=\lambda >0`$ is played by the scattered waves $`\stackrel{}{\mathrm{\Psi }}_\nu ,\stackrel{}{\mathrm{\Psi }}_\nu `$, labeled with vectors $`\nu `$. The components of the scattered waves $`\mathrm{\Psi }_\nu (p)`$ in the outer space $`L_2(𝐑)`$ are presented as linear combinations of exponentials:

$$\stackrel{}{\mathrm{\Psi }}_{\nu ,p}(x)=\{\begin{array}{cc}e^{ipx}\nu +e^{+ipx}\stackrel{}{R}(p)\nu ,& x<0,\\ e^{ipx}\stackrel{}{T}(p)\nu ,& x>0,\end{array}$$

$$\stackrel{}{\mathrm{\Psi }}_{\nu ,p}(x)=\{\begin{array}{cc}e^{ipx}\nu +e^{ipx}\stackrel{}{R}(p)\nu ,& x>0,\\ e^{ipx}\stackrel{}{T}(p)\nu ,& x<0.\end{array}$$
(5)
The matrix

$$𝐒_\beta (p)=\left(\begin{array}{cc}\stackrel{}{T}(p)& \stackrel{}{R}(p)\\ \stackrel{}{R}(p)& \stackrel{}{T}(p)\end{array}\right),$$
(6)
is called the scattering matrix of the operator $`𝐀_\beta `$.333The transmission coefficients appear on the main diagonal of the matrix to fit the physical meaning of the scattering matrix for small values of $`|\beta |`$, when it is reduced to the undisturbed transmission $`𝐒(p)=I`$.

The evolution of the wave function of the quantum mechanical system with Hamiltonian $`𝐀_\beta `$ given by the equation

$$\frac{1}{i}\frac{\mathrm{\Psi }}{t}=𝐀_\beta \mathrm{\Psi },$$
(7)
and proper initial condition

$$\mathrm{\Psi }|_{t=0}=\mathrm{\Psi }_0,$$

can be described by the correspopnding evolution operator constructed from the above scattered waves and square-integrable bound states $`\mathrm{\Psi }_s`$ which satisfy the homogeneous equation

$$𝐀_\beta \mathrm{\Psi }_s=\lambda _s\mathrm{\Psi }_s,$$

with negative eigen-values $`\lambda _s`$. Bound states do not play an essential role in our construction, so we may assume that the initial state $`\mathrm{\Psi }_0`$ is orthogonal to all bound states and may be expanded in an analog of Fourier integral over the scattered waves

$$\mathrm{\Psi }_0=\frac{1}{2\pi }_R\underset{\nu }{}\mathrm{\Psi }_{\nu ,p}\mathrm{\Psi }_{\nu ,p},\mathrm{\Psi }_0dp.$$

Then the evolution described by the solution of the equation (7) and the above initial data can be presented as a (continuous) linear combination

$$\mathrm{\Psi }(t)=\frac{1}{2\pi }_𝐑\underset{\nu }{}e^{ip^2t}\mathrm{\Psi }_{\nu ,p}\mathrm{\Psi }_{\nu ,p},\mathrm{\Psi }_0dp$$

of modes incoming from infinity on the left $`(\mathrm{})`$ and on the right $`(+\mathrm{})`$, and outgoing modes scattered to both directions $`\pm \mathrm{}`$ according to the solution of the time-dependent Schrödinger equation $`\frac{1}{i}\frac{𝐔}{t}=\mathrm{𝐀𝐔}:`$

$$𝐒_\beta (p):e^{ip^2t}\left(\begin{array}{c}e^{ipx}\nu _{left}\\ e^{ipx}\nu _{right}\end{array}\right)e^{ip^2t}\left(\begin{array}{cc}e^{ipx}(\stackrel{}{T}(p)\nu _{left}+& \stackrel{}{R}(p)\nu _{right})\\ e^{ipx}(\stackrel{}{R}(p)\nu _{left}+& \stackrel{}{T}(p)\nu _{right})\end{array}\right).$$
(8)
The analytic structure of the scattering matrix depends upon the structure of the inner Hamiltonian and a sort of interaction between the inner $`E`$ and outer $`L_2(𝐑,)`$ spaces. To avoid the discussion of the general situation we use here a scattering matrix for a solvable model of the quantum dot which is based on zero-range potential with inner structure, introduced in  and already used in  for the description of typical features of nano-devices, see also .

If we choose an infinitely-dimensional input space $``$ with components corresponding to the amplitudes of the scattered waves at $`\pm \mathrm{}`$ and an one-dimensional deficiency subspace $`𝒩_i`$ spanned by the normalized vector $`e=e_i`$ (see ) and introduce the scalar function

$$=\frac{I+\lambda A}{A\lambda I}e,e,$$

then using the interaction defined by the boundary conditions (9) depending on a vector $`\beta `$ imposed on the boundary values (the jump $`[u^{}](0)`$ and the value $`u(0)`$ at the origin) of the component of the wave-function in the outer space and the symplectic coordinates $`\stackrel{}{\xi }_\pm `$ of the inner component of the wave-function (see ):

$$\left(\begin{array}{c}[u^{}](0)\\ \stackrel{}{\xi }_{}\end{array}\right)=\left(\begin{array}{cc}0& \beta \\ \beta ^+& 0\end{array}\right)\left(\begin{array}{c}u(0)\\ \stackrel{}{\xi }_+\end{array}\right),$$
(9)
we obtain the scattering matrix in the form

$$𝐒_\beta (p)=\left(\begin{array}{cc}\stackrel{}{T}(p)& \stackrel{}{R}(p)\\ \stackrel{}{R}(p)& \stackrel{}{T}(p)\end{array}\right),$$

with equal transmission and reflection coefficients $`\stackrel{}{T},\stackrel{}{T},\stackrel{}{R},\stackrel{}{R}`$:

$$\stackrel{}{T}(p)=\stackrel{}{T}(p)=𝐏_\beta ^{}+\frac{2ip}{2ip+|\beta |^2^1}𝐏_\beta ,\stackrel{}{R}(p)=\stackrel{}{R}(p)=\frac{|\beta |^2^1}{2ip+|\beta |^2^1}𝐏_\beta .$$

Here $`𝐏_\beta `$ is the orthogonal projection of $``$ onto the one-dimensional space spanned by the vector $`\beta `$, and $`𝐏_\beta ^{}=I𝐏_\beta `$ is the orthogonal projection on the complimentary space. The constructed solvable model reveals the role of zeroes of the scattering matrix – the resonances – in implementing the switching function.

We observe first the behaviour of the scattering matrix at the resonance energy $`\alpha _1^2>0`$ in case the resonance level $`\alpha _1^2`$ in the quantum dot is vacant as well as all levels $`\alpha _l^2`$ above $`\alpha _1^2`$. In this case we have

$$_1=\frac{1+\alpha _1^2\lambda }{\alpha _1^2\lambda }|e_1|^2+\underset{l=2}{\overset{N}{}}\frac{1+\alpha _l^2\lambda }{\alpha _l^2\lambda }|e_l|^2=\frac{1+\alpha _1^2\lambda }{\alpha _1^2\lambda }|e_1|^2+_3,$$

where $`|e_l|^2`$ are the squares of the Fourier coefficients of the deficiency vector $`e`$ with respect to the eigen-vectors of the operator $`A`$.

Next we consider the case when the resonance level $`\alpha _1^2`$ is occupied. In this case

$$_2=\frac{1+\alpha _2^2\lambda }{\alpha _2^2\lambda }|e_2|^2+\underset{l=3}{\overset{N}{}}\frac{1+\alpha _l^2\lambda }{\alpha _l^2\lambda }|e_l|^2=\frac{1+\alpha _2^2\lambda }{\alpha _2^2\lambda }|e_2|^2+_3.$$

In the above analysis we have ignored the electron spin, that is we have assumed that all electrons have the same constant spin on the quantum circuit $`𝐑_{}𝐑_+`$, with the quantum dot attached.444Our hypothesis is satisfied in case the travelling electrons are polarized and the electron on the level $`\alpha _1^2`$ is polarized. Note that Pauli’s exclusion principle is still valid, but with only one electron on each orbital: the magnetic field is absent, so the polarization is not changed during the experiment. We may assume that the circuit lies on the surface of a semiconductor with Fermi-level $`\alpha _1^2`$ (see ).

We assume that the state of the dot with the level $`\alpha _1^2`$ vacant corresponds to $`I_{in}=I_{out}=0`$ and the state of the dot with the level $`\alpha _1^2`$ occupied corresponds to $`I_{in}=I_{out}=1`$. We identify these states of the system as state $`S_1`$ and state $`S_2`$, respectively.

For every vector $`\beta `$ the transmission coefficients on the resonance electron’s energy $`\lambda =\alpha _1^2`$ can be expressed as (see ):

$$\stackrel{}{T}(p)=\stackrel{}{T}(p)=𝐏_\beta ^{}+\frac{2ip}{2ip+|\beta |^2_1^1}𝐏_\beta =I.\stackrel{}{R}(p)=\stackrel{}{R}(p)=0,$$

(at the resonance energy we have $`_1^1=0`$), so the scattering matrix becomes the identity when $`\alpha _1^2`$ is not occupied.

In the second case, when the resonance level $`p^2=\lambda =\alpha _1^2`$ is occupied, we obtain (due again to Pauli’s exclusion principle) the following expression for the transmission coefficients of passing electrons with resonance energy:

$$\stackrel{}{T}(p)=\stackrel{}{T}(p)=\frac{2ip_2(\lambda )}{2ip_2(\lambda )|\beta |^2}=\frac{2ip\left(\frac{1+\alpha _2^2\alpha _1^2}{\alpha _2^2\alpha _1^2}|e_2|^2+_{l=3}^N\frac{1+\alpha _l^2\alpha _1^2}{\alpha _l^2\alpha _1^2}|e_l|^2\right)}{2ip\left(\frac{1+\alpha _2^2\alpha _1^2}{\alpha _2^2\alpha _1^2}|e_2|^2+_{l=3}^N\frac{1+\alpha _l^2\alpha _1^2}{\alpha _l^2\alpha _1^2a}|e_l|^2\right)+|\beta |^2}\text{,}$$

and the corresponding expressions for the reflection coefficients

$$\stackrel{}{R}(p)=\stackrel{}{R}(p)=\frac{|\beta |^2}{2ip_2+|\beta |^2}𝐏_\beta ,$$

which can be approximated, for large enough $`\beta `$, as

$$\stackrel{}{T}(\alpha _1)=\stackrel{}{T}(\alpha _1)𝐏_\beta ^{},\stackrel{}{R}(\alpha _1)=\stackrel{}{R}(\alpha _1)𝐏_\beta .$$

Hence the scattering matrix is equal to

$$𝐒_\beta (\alpha _1^2)=\left(\begin{array}{cc}𝐏_\beta ^{}& 𝐏_\beta \\ 𝐏_\beta & 𝐏_\beta ^{}\end{array}\right)=I\left(\begin{array}{cc}𝐏_\beta & 𝐏_\beta \\ 𝐏_\beta & 𝐏_\beta \end{array}\right),$$
(10)
for relatively large enough $`\beta `$, if the resonance level $`\alpha _1^2`$ is occupied.

We continue by showing how the probabilistic approach discussed in the previous section can be realised.We consider now an imaginable quantum scattering system with an infinitely-dimensional input-space and, in particular, with the infinite dimensional space $``$ for which a solvable model was described above as an extension of the orthogonal sum $`l_0A_0`$ with boundary condition (9), in which , however, the $`\beta `$-channel connecting the outer subspace $`L_2(𝐑,)`$ with the inner subspace $`E`$ is as before two-dimensional. We associate these extensions with two states $`(S_1,S_2)`$ of the total quantum system combined of the inner and outer components, with the interaction respectively switched on via the boundary condition (9), $`\beta 0`$, or switched off, $`\beta =0`$, and we interpret the Halting Problem in a probabilistic setting as the problem of distinguishing of the states $`(S_1,S_2)`$ of the quantum system via a scattering experiment with a random input.

Following the probabilistic strategy in Section 4, we compare the scattering matrices $`𝐒_\beta (\alpha _1^2)`$ in states $`S_1`$ and $`S_2`$. In the first state this matrix coincides with identity, hence

$$\frac{1}{2}(I+𝐒_\beta (\alpha _1^2))=I.$$

In the second state we have

$$\frac{1}{2}(I+𝐒_\beta (\alpha _1^2))=\left(\begin{array}{cc}I& 0\\ 0& I\end{array}\right)+\left(\begin{array}{cc}𝐏_\beta & 0\\ 0& 𝐏_\beta \end{array}\right)𝒫_{sym},$$

where $`𝒫_{sym}=\frac{1}{2}\left(\begin{array}{cc}I& I\\ I& I\end{array}\right)`$ is the projection onto the symmetric subspace of the input space $``$ consisting of vectors with equal componenets $`\left(\begin{array}{c}e\\ e\end{array}\right)`$. The projections $`\left(\begin{array}{cc}𝐏_\beta & 0\\ 0& 𝐏_\beta \end{array}\right)`$ and $`𝒫_{sym}`$ commute and their product gives the projection onto the space spanned by $`\stackrel{}{\beta }=\left(\begin{array}{c}\beta \\ \beta \end{array}\right)`$. Hence,

$$\frac{1}{2}(I+𝐒_\beta (\alpha _1^2))=\left(\begin{array}{cc}I& 0\\ 0& I\end{array}\right)𝒫_\beta ,$$

where $`𝒫_\beta `$ is the orthogonal projection on the subspace $``$ which is collinear to the vector $`\stackrel{}{\beta }`$ in the input space. Therefore, in the second case, for every vector $`e`$ we have:

$$\frac{1}{2}(e,e+𝐒_\beta (\alpha _1^2)e,e)=|e|^2|𝒫_\beta e|^2.$$

The expectation is that if the probability of the event $`𝒫_\beta e=0`$ is zero, then by choosing a random test-vector, with probability $`1`$ the above correlation is strictly less than $`1`$. To obtain the corresponding quantitative result we will assume that we have a testing “device” distinguishing between the two states of the system , which “clicks” if

$$|𝒫_\beta e|^2>\epsilon |e|^2.$$
(11)
Unfortunately, the above “device” is not sensitive enough to derive proper estimates for probabilities and we need another norm in the right-hand side of the last inequality. In our case the input space $``$ is $`l_2`$ with the standard orthogonal basis $`𝐱\left\{x_m\right\}_{m=0}^{\mathrm{}}.`$ Following () we consider the discrete Sobolev classes and norms introduced in Section 4, (1) and (2) in order to define the case when the “device” clicks. Next we assume that the (complex) increments $`x_mx_{m1}`$ are independent. We are going to use, together with $`l_2`$ two more spaces of test-vectors. Both are stochastic spaces of all trajectories $`𝐱(t)`$ of a Brownian particle on the complex plane along different discrete sequences of intermediate moments of time (“stops”): the equidistant sequence $`t_l=_{m=1}^l\delta _m`$, for the first space, and the perturbed sequence $`\stackrel{~}{t}_l=_{m=1}^l\mathrm{\Delta }_m`$, for the second space. Both spaces are equipped with proper Wiener measures $`W,\stackrel{~}{W}`$ (see ). The measure $`W`$ is defined on the algebra of all finite-dimensional cylindrical sets $`C_{_{_{\mathrm{\Delta }_1,\mathrm{\Delta }_2,\mathrm{},\mathrm{\Delta }_N}}}^{t_1,t_2,\mathrm{},t_N}`$ of trajectories with fixed initial point $`x_0=0`$ and “gates” $`\mathrm{\Delta }_l,l=1,\mathrm{},N`$ (which are open discs in the complex plane):

$$C_{_{_{\mathrm{\Delta }_1,\mathrm{\Delta }_2,\mathrm{},\mathrm{\Delta }_N}}}^{^{^{t_1,t_2,\mathrm{},t_N}}}=\{𝐱x_{t_l}\mathrm{\Delta }_l,l=1,2,\mathrm{},N\},$$

via multiple convolutions of the Green functions $`G(x_{l+1},t_{l+1}|x_l,t_l)`$ corresponding to the sequence $`\delta _{l+1}=t_{l+1}t_l`$:

$$W(C_{_{_{\mathrm{\Delta }_1,\mathrm{\Delta }_2,\mathrm{},\mathrm{\Delta }_N}}}^{^{^{t_1,t_2,\mathrm{},t_N}}})=$$

$$\frac{\mathrm{}_{\mathrm{\Delta }_N,\mathrm{\Delta }_{N1},\mathrm{},\mathrm{\Delta }_1}\frac{dx_1dx_2\mathrm{}dx_N}{\pi ^{\frac{N}{2}\sqrt{\delta _N\delta _{N1}\mathrm{}\delta _1}}}e^{^{\frac{|x_Nx_{N1}|^2}{\delta _N}}}\mathrm{}e^{^{\frac{|x_1x_0|^2}{\delta _1}}}}{\mathrm{}_{𝐑_N,𝐑_{N1},\mathrm{},𝐑_1}\frac{dx_1dx_2\mathrm{}dx_N}{\pi ^{\frac{N}{2}\sqrt{\delta _N\delta _{N1}\mathrm{}\delta _1}}}e^{^{\frac{|x_Nx_{N1}|^2}{\delta _N}}}\mathrm{}e^{^{\frac{|x_1x_0|^2}{\delta _1}}}},$$
(12)
where $`𝐑_N=𝐑_{N1}=\mathrm{}=𝐑_1=𝐑`$. Using the convolution formula, the denominator of (12) can be reduced to the Green function $`G(x_N,t_N0,0)`$, for any $`\tau (s,t)`$:

$$G(x,ty,s)=_{\mathrm{}}^{\mathrm{}}G(x,t\xi ,\tau )G(\xi ,\tau y,s)𝑑\xi .$$

In a similar way we can define the Wiener measure for trajectories corresponding to the “perturbed” sequence $`\stackrel{~}{t}_l`$.

In what follows we are going to use the absolute continuity of the perturbed Wiener measure $`\stackrel{~}{W}`$ with respect to the non-perturbed one $`W`$: for every $`W`$–measurable set $`\mathrm{\Omega }`$,

$$\stackrel{~}{W}(\mathrm{\Omega })=\frac{1}{_{l=1}^{\mathrm{}}\sqrt{\mathrm{\Delta }_l}}_\mathrm{\Omega }e^{_{m=1}^{\mathrm{}}\frac{1\mathrm{\Delta }_m}{\mathrm{\Delta }_m}x_mx_{m1}^2}𝑑W.$$
(13)
Further we consider the class of quasi-loops, that is the class of all trajectories of the “perturbed process” which begin from $`(x_0,\stackrel{~}{t}_0)=(0,0)`$ and for any $`t`$, $`\mathrm{max}_{0<s<t}|x_s|^2<Ct`$. We note that

* every $`𝐱l_2^1`$ is a quasi-loop (with $`C=𝐱_1^2`$),
* due to the reflection principle (see , p. 221), the class of all quasi-loops has Wiener measure one, both in respect of $`W,\stackrel{~}{W}`$.

We assume that the device clics, if the result of averaging exceeds a certain level defined by the above norm $`_1^2`$:

$$|𝒫_\beta 𝐱|^2>\epsilon 𝐱_1^2.$$

This device cannot identify the state of the system from the observation of the Breit-Wigner averaged correlation between the input and output of a single act of scattering when presented a randomly chosen input $`𝐱`$ if $`|𝒫_\beta 𝐱|^2<\epsilon 𝐱_1^2.`$ This means that the test-vector $`𝐱`$ belongs to the indistinguishable set

$`_\epsilon `$ $`=`$ $`\left\{𝐱l_2l_2^1,|𝒫_\beta 𝐱|^2<\epsilon \left({\displaystyle \underset{_{_{m=1}}}{\overset{\mathrm{}}{}}}{\displaystyle \frac{1\mathrm{\Delta }_m}{\mathrm{\Delta }_m}}|x__mx_{_{m1}}|^2\right)\right\}`$
$`=`$ $`\{𝐱l_2l_2^1,|𝒫_\beta 𝐱|^2<\epsilon 𝐱_1^2\}.`$
Though technically we may easily consider, with Breit-Wiegner averaging, the iterated scattering processes described by the powers $`𝐒^m`$ of the scattering matrix, we will analyze now the independent single acts of scattering. In this case the indistinguishable set depends only upon the positive number $`\epsilon `$, the vector $`\stackrel{}{\beta }`$ defining the interaction in the quantum system, and the sequence $`\mathrm{\Delta }`$. Without loss of generality we may assume that the vector $`\stackrel{}{\beta }`$ has all non-zero components $`\stackrel{}{\beta }_l0`$. We assume that the vector $`𝐛=\left\{b_l\right\}_{l=1}^{\mathrm{}},b_l=_{m=l}^{\mathrm{}}\stackrel{}{\beta }_m`$ belongs to $`l_2`$:

$$|b|_l^2=\underset{m=1}{\overset{\mathrm{}}{}}m^2|\stackrel{}{\beta }_m|^2<\mathrm{}.$$
(15)
Our main result reads: If the condition (15) is satisfied, then the Wiener probability $`\stackrel{~}{W}(_{\epsilon ,1})`$ of the indistinguishable set $`_{\epsilon ,1}`$ corresponding to a single act of scattering is finite and is estimated as

$$\stackrel{~}{W}(_\epsilon )<\frac{\sqrt{\epsilon }|\stackrel{}{\beta }|}{_{l=1}^{\mathrm{}}\sqrt{\mathrm{\Delta }_l}\sqrt{\epsilon |\stackrel{}{\beta }|^2+|b|^2}}\text{.}$$
(16)
Following the calculation presented in , we approximate the indistinguishable set with finite-dimensional cylinder sets and reduce the estimation of $`\stackrel{~}{W}(_{\epsilon ,1})`$ to the calculation of a Wiener integral with respect to the $`W`$ measure on trajectories associated with “equidistant stops”. We have:

$$\stackrel{~}{W}(_{\epsilon ,1})$$

$``$ $`{\displaystyle _{\text{quasi-loops},x_0=0|𝐱,\stackrel{}{\beta }|^2<\epsilon 𝐱_1^2}}𝑑\stackrel{~}{W}`$
$`=`$ $`\underset{C\mathrm{}}{lim}{\displaystyle _{sup_{sl}|x_s|<C\sqrt{l},lN,x_0=0|𝐱,\stackrel{}{\beta }|^2<\epsilon 𝐱_1^2}}𝑑\stackrel{~}{W}`$
$`=`$ $`{\displaystyle \frac{1}{_{l=1}^{\mathrm{}}\sqrt{\mathrm{\Delta }_l}}}\underset{C\mathrm{}}{lim}\underset{N\mathrm{}}{lim}`$
$`{\displaystyle \frac{_{sup_{sl}|x_s|<C\sqrt{l},lN,x_0=0}\mathrm{}_{\mathrm{}}^{\mathrm{}}𝑑x_1𝑑x_2\mathrm{}𝑑x_Ne^{\frac{|x_Nx_{N1}|^2}{\mathrm{\Delta }_N}}\mathrm{}e^{\frac{|x_1x_0|^2}{\mathrm{\Delta }_1}}}{\pi ^N_{_{|x_N|<C\sqrt{N}}}𝑑x_Ne^{\frac{x_Nx_0}{\stackrel{~}{t}_N}}}}`$
$`{\displaystyle \frac{1}{_{l=1}^{\mathrm{}}\sqrt{\mathrm{\Delta }_l}}}\underset{C\mathrm{}}{lim}\underset{N\mathrm{}}{lim}`$
$`{\displaystyle \frac{_{sup_{sl}|x_s|<C\sqrt{l},lN,x_0=0}\mathrm{}_{\mathrm{}}^{\mathrm{}}𝑑x_1𝑑x_2\mathrm{}𝑑x_Ne^{_{s=1}^N\frac{|x_sx_{s1}|^2}{\delta _s}}e^{(x_0,x_1,x_2\mathrm{}x_N)}}{\pi ^N_{|x_N|<C\sqrt{N}}𝑑x_Ne^{\frac{|x_Nx_0|^2}{\stackrel{~}{t}_N}}}}\text{.}`$
The integrand of the inner integral in the numerator contains the exponential factor

$$e^{}=e^{(1\mathrm{\Delta }_N)\frac{|x_Nx_{N1}|^2}{\mathrm{\Delta }_N}(1\mathrm{\Delta }_{N1})\frac{|x_{N1}x_{N2}|^2}{\mathrm{\Delta }_{N1}}(1\mathrm{\Delta }_1)\frac{|x_1x_0|^2}{\mathrm{\Delta }_1}},$$

which can be estimated due to (5) by the exponential:

$$e^{\frac{1}{\epsilon }|𝒫_\stackrel{}{\beta }𝐱|^2}=e^{\frac{1}{\epsilon |\stackrel{}{\beta }|^2}|𝐱,\stackrel{}{\beta }|^2}.$$

Using this equality, the exponential in the numerator can be estimated from below by the quadratic form

$$\underset{m=1}{\overset{N}{}}|x_mx_{m1}|^2\frac{1}{\epsilon |\stackrel{}{\beta }|^2}|𝐱,\stackrel{}{\beta }|^2.$$
(17)
This quadratic form can be simplified using new vector variables $`\xi _m=x_mx_{m1}`$:

$$\stackrel{}{\beta },𝐱=\underset{m=1}{\overset{\mathrm{}}{}}x_m\overline{\stackrel{}{\beta }}_m=\underset{m=1}{\overset{\mathrm{}}{}}\xi _m\overline{\underset{l=m}{\overset{\mathrm{}}{}}\stackrel{}{\beta }_l}.$$

Recall that the vector $`𝐛,b_m=_{l=m}^{\mathrm{}}\beta _l`$ belongs to $`l_2`$. Then the quadratic form in the exponent of the numerator can be presented as a quadratic form of an operator

$$\xi ,A_\epsilon \xi =|\xi |^\mathrm{𝟐}+\frac{\mathrm{𝟏}}{|\stackrel{}{\beta }|^\mathrm{𝟐}\epsilon }|𝐛,\xi |=\xi ,\left(𝐈+\frac{|𝐛|^\mathrm{𝟐}}{|\stackrel{}{\beta }|^\mathrm{𝟐}\epsilon }𝐏_𝐛\right)\xi ,$$

where $`𝐏_b`$ is the orthogonal projection onto the one-dimensional subspace in $`l_2`$ spanned by the vector $`𝐛`$. The ratio of the $`N`$-dimensional Gaussian integral in the numerator, normalized by the factor $`\pi ^{N/2}`$ and the Gaussian integral in the denominator can be expressed as

$$\frac{1}{\pi ^{N/2}}\mathrm{}e^{\xi ,A_\epsilon \xi }𝑑\xi _1𝑑\xi _2\mathrm{}𝑑\xi _N=\frac{1}{\sqrt{\text{det}A_\epsilon }}=\frac{\sqrt{\epsilon }\stackrel{}{\beta }|}{\sqrt{\epsilon |\stackrel{}{\beta }|^2+|b|^2}}\text{.}$$

Finally, we obtain the announced result by taking into account the omitted factor $`_l\sqrt{\mathrm{\Delta }_l}`$.

## Acknowledgement

We thank Radu Ionicioiu for his comments on a draft form of this paper. Calude and Pavlov have been supported in part by the The Vice-Chancellor’s University Development Fund 23124/2002.


format: text

text:
# Quantum automorphism groups of small metric spaces

## Introduction

Let $`X`$ be a finite set. Consider faithful coactions $`v:(X)(X)H`$ of Hopf $`^{}`$-algebras $`H`$ on $`X`$. If $`H`$ is commutative, it has to be of the form $`(G)`$, with $`G`$ a finite group of permutations of $`X`$. In the general case, a group dual example shows that such an $`H`$ can be non commutative and infinite dimensional. The universal Hopf $`^{}`$-algebra $`H(X)`$ coacting on $`X`$ is constructed by Wang in .

If $`X`$ has 1, 2 or 3 points then $`H(X)`$ is the algebra of functions on the permutation group of $`X`$. If $`X`$ has more than 4 points $`H(X)`$ is non commutative and infinite dimensional. The fusion rules for its irreducible corepresentations are the same as fusion rules for irreducible representations of $`SO(3)`$, independently of $`\mathrm{\#}X`$.

It is a natural question to ask whether such uniformisation results still hold when adding some extra structure to $`X`$. The case of coactions on certain fibrations $`XY`$ is studied in . A universal Hopf $`^{}`$-algebra $`H(XY)`$ can be constructed and once again, fusion rules for its corepresentations are given by the combinatorics of the Fibonacci graph, independently of the initial data.

At the level of planar algebras, $`H(X)`$ corresponds to the Temperley-Lieb algebra and $`H(XY)`$ corresponds to the Fuss-Catalan algebra of Bisch and Jones ().

In this paper we study the more general situation when we are given a metric $`d`$ on $`X`$. A universal Hopf $`^{}`$-algebra $`H(X,d)`$ can be constructed in this case as well. In many cases $`H(X,d)`$ collapses to the algebra of functions on the usual automorphism group $`G(X,d)`$. In other cases the coaction of $`H(X,d)`$ is not transitive, meaning that there exists a non-constant function $`f(X)`$ such that $`v(f)=f1`$.

The most interesting case is when $`H(X,d)`$ is not commutative and its coaction is transitive. For instance in the case where $`X`$ is a simplex, meaning that all distances between points are equal, $`H(X,d)`$ is the above $`H(X)`$. The algebra $`H(XY)`$ is as well of the form $`H(X,d)`$, for a suitable choice of the distance $`d`$.

We prove that for metric spaces $`(X,d)`$ having at most 7 points the algebras $`H(X,d)`$ fall into one of these four classes: commutative, non-transitive, corresponding to the Temperley-Lieb algebra, corresponding to the Fuss-Catalan algebra.

This is inspired from recent work of Bisch and Jones. In ,  they prove the following result. Let $`P`$ be a spherical $`^{}`$-planar algebra satisfying the following conditions. (1) $`dim(P_1)=1`$ and $`P`$ is generated by a 2-box $`bP_2`$. (2) $`dim(P_2)=3`$. (3) $`dim(P_3)13`$. Then (4) $`P`$ is a Temperley-Lieb or a Fuss-Catalan algebra, or is the algebra associated to $`_3`$, or is another algebra, associated to $`_2`$ and $`D_5`$.

The above result can be reformulated as follows (cf. , ). Let $`P`$ be a spherical $`^{}`$-planar algebra satisfying the following conditions. ($`1^{}`$) $`dim(P_1)=1`$ (“transitivity”) and $`P`$ is generated by a 2-box $`bP_2`$ (“universality”). ($`2^{}`$) $`P`$ embeds into the depth 1 planar algebra associated in  to the inclusion $`(X)`$ and $`b`$ corresponds in this way to a distance matrix (“tannakian conditions”). ($`3^{}`$) $`\mathrm{\#}X7`$. Then ($`4^{}`$) $`P`$ is a Temperley-Lieb or a Fuss-Catalan algebra, or there is a 4-box in $`P`$ which corresponds to the flip automorphism of $`X\times X`$ (“commutativity”).

We see that the general conditions (1) and ($`1^{}`$) are the same and that the key conditions (2) and ($`2^{}`$) are of different nature. The conclusions (4) and ($`4^{}`$) look a bit similar just because the auxiliary conditions (3) and ($`3^{}`$) are too strong.

The methods we use for the proof are quite different from those of Bisch and Jones. The fact that the 2-box here is given by an explicit operator brings lots of simplifications with respect to the much more general situation considered in , . As an example, Landau’s exchange relation (), which is one of the main tools in classifying planar algebras, says for a 2-box $`p`$ that the image of the corresponding projection $`P((X))`$ must be closed under multiplication, and this is very easy to check.

In fact the proof of the above result just uses our previous work on the Fuss-Catalan algebra  plus some elementary matrix computations. It is also possible to apply the powerful results of Bisch and Jones to the Hopf $`^{}`$-algebras $`H(X,d)`$. After making all necessary identifications, the problem is to check dimension conditions on the planar algebra of $`H(X,d)`$. The geometric formulation of these conditions requires some combinatorial work, and this is exactly the kind of work we do in this paper.

We don’t know what happens for $`\mathrm{\#}X8`$. Some exceptional examples are expected to arise, for instance in connection with complex Hadamard matrices and Krishnan-Sunder biunitary permutation matrices. Associated to such matrices are quite exotic lattice models and commuting squares, which can be described by coactions (cf. , , ). In fact, these coactions are the second motivation for the study of the algebras $`H(X,d)`$. So far the universal Hopf algebras $`H(X)`$ haven’t been useful for getting new results on vertex models, but one can hope that the Hopf algebras $`H(X,d)`$, which are somehow of “second level”, could produce better results.

From the point of view explained by Bisch and Jones in  the simplest planar algebras are those generated by a 2-box, and among them, simplest are those having small dimension. There is a similar hierarchy for Hopf $`^{}`$-algebras: (I) By Woronowicz’s result  each unital Hopf $`^{}`$-algebra is an inductive limit of pairs $`(H,v)`$ as in . (II) By replacing $`v`$ with $`ad(v1)`$ we may assume that $`v:AAH`$ is a coaction on a finite dimensional $`^{}`$-algebra. (III) We say that $`(H,v)`$ has length $`k`$ if it is isomorphic to the universal pair $`(K,w)`$ satisfying $`Hom(1,v^k)Hom(1,w^k)`$. (This means that the associated planar algebra has planar depth $`k`$ in the sense of .) By analogy with discrete groups, each pair $`(H,v)`$ is a projective limit of length $`k`$ pairs. (IV) The simplest situation is when $`k=2`$. Here $`(H,v)`$ is presented by the relations $`dv=vd`$, where $`d`$ is a generator of $`Hom(1,v^2)End(v)`$ (the “2-box”). (V) The simplest case is when $`A`$ is abelian and $`d`$ is a metric on its spectrum $`X`$. Here $`H=H(X,d)`$.

Generalisations of the algebras $`H(X,d)`$ can be found by going up through this hierarchy. On the other side, when trying to generalise a metric space, the first thought goes to Connes’ notion of a spectral triple (). There are many problems here, the main one being probably to find a good hierarchy of spectral triples, reflecting somehow the corepresentation theory complexity of the associated Hopf $`^{}`$-algebra (if any). See Paschke and Sitarz  and Rieffel  for more comments on this subject.

The paper is organised as follows. 1. is a preliminary section, with material from  and . In 2. we establish some basic facts about coactions on finite metric spaces. In 3. we find some geometric rules for detecting commutativity or non-transitivity of $`H(X,d)`$, the main tool being diagonalisation of distance matrices. In 4. we assume that $`\mathrm{\#}X7`$ and we prove the main result.

## 1. Coactions on finite sets

Let $`X`$ be a finite set. We denote by $`(X)`$ the algebra of complex functions on $`X`$. We use the canonical involution and trace of $`(X)`$, given by the following formulae.

$$f^{}(i)=\overline{f(i)}tr(f)=\underset{i}{}f(i)$$

If $`K`$ is a set we denote by $`M_X(K)`$ the set of functions from $`X\times X`$ to $`K`$. Such a function can be written as a matrix $`(v_{ij})`$ with indices $`i,j`$ in $`X`$ and entries $`v_{ij}`$ in $`K`$.

The group of permutations of $`X`$ is denoted by $`𝒮_X`$.

Let $`H`$ be the Hopf $`^{}`$-algebra associated to a compact quantum group of Kac type. That is, $`H`$ is a unital $`^{}`$-algebra together with linear maps

$$\mathrm{\Delta }:HHH\epsilon :HS:HH$$

called comultiplication, counit and antipode and subject to the following axioms. The maps $`\mathrm{\Delta }`$ and $`\epsilon `$ are morphisms of $`^{}`$-algebras satisfying the conditions

$$(id\mathrm{\Delta })\mathrm{\Delta }=(\mathrm{\Delta }id)\mathrm{\Delta }(id\epsilon )\mathrm{\Delta }=(\epsilon id)\mathrm{\Delta }=id$$

and the antipode is an antimultiplicative involutive map satisfying

$$m(idS)\mathrm{\Delta }=m(Sid)\mathrm{\Delta }=idS^2=id$$

By  the Hopf $`^{}`$-algebra $`H`$ has a Haar functional and the dense $``$-subalgebra $`H_s`$ of “smooth functions on the quantum group” is a cosemisimple Hopf $``$-algebra.

###### Definition 1.1.

A coaction of $`H`$ on $`X`$ is a morphism of complex $``$-algebras

$$v:(X)(X)H_s$$

satisfying the coassociativity condition $`(vid)v=(id\mathrm{\Delta })v`$, the counitality condition $`(id\epsilon )v=id`$ and the trace-preservation condition $`(trid)v=tr(.)1`$.

Consider the basis of $`(X)`$ formed by the Dirac masses $`\delta _i`$ with $`iX`$. The coaction $`v`$ is given by the following sum.

$$v(\delta _i)=\underset{j}{}\delta _jv_{ji}$$

The elements $`v_{ij}`$ are called coefficients of the coaction. A coaction is called faithful if its coefficients generate the $``$-algebra $`H`$. In general we have a factorisation

$$\begin{array}{ccc}(X)& \stackrel{v^{}}{}& (X)H^{}\\ & & \\ & v& id\\ & & \\ & & (X)H\end{array}$$

where $`H^{}H`$ is the $``$-algebra generated by the coefficients of $`v`$. From the axioms for $`v`$ we get that $`H^{}`$ is stable under comultiplication, so $`v^{}`$ is a coaction as well. Thus any coaction factorises through a faithful coaction.

As a first example, consider the Hopf $`^{}`$-algebra $`(G)`$ associated to a finite group $`G`$. Here the comultiplication, counit and antipode are obtained by applying the $``$ functor to the multiplication, unit and inverse map of $`G`$.

$$\mathrm{\Delta }(\delta _g)=\underset{hk=g}{}\delta _h\delta _k\epsilon (f)=f(1)S(\delta _g)=\delta _{g^1}$$

If $`(x,g)gx`$ is an action of $`G`$ on $`X`$, by applying the the $``$ functor we get a map from $`(X)`$ to $`(X\times G)(X)(G)`$, which is a coaction.

$$v(\delta _i)=\underset{g}{}\delta _{gi}\delta _g=\underset{j}{}\delta _j\underset{gi=j}{}\delta _g$$

This shows that $`v`$ is faithful if and only if the action map $`G𝒮_X`$ is injective. Thus any subgroup of the symmetric group $`𝒮_X`$ produces a faithful coaction on $`X`$.

Note that the trace-preservation condition says that the action of $`G`$ must preserve the counting measure on $`X`$, and this is always true. In general this condition is not satisfied, and in case it does not hold unwanted decomposition appears in the corepresentation theory of $`H`$ (). In topological terms, the trace-preservation condition is needed in order to avoid “floating circles” in the corresponding planar algebra. See , .

Note also that the Kac algebra assumption $`S^2=id`$ is satisfied for $`H=(G)`$. In general, this assumption cannot be dropped, in the sense that for any Hopf $`^{}`$-algebra coacting faithfully on $`(X)`$ the square of the antipode must be the identity.

The axioms for $`v`$ can be translated in terms of its coefficients $`v_{ij}`$. First, the fact that $`v`$ is coassociative and counital translates into two “comultiplicative” formulae.

$$\mathrm{\Delta }(v_{ij})=\underset{k}{}v_{ik}v_{kj}\epsilon (v_{ij})=\delta _{ij}$$

These conditions say that $`v`$ is a corepresentation of $`H`$ on the linear space $`(X)`$.

$$(id\mathrm{\Delta })v=v_{12}v_{13}(id\epsilon )v=1$$

For the other axioms, note first that the structure of $`(X)`$ is given by the formulae

$$\delta _i^2=\delta _i\delta _i\delta _I=01=\underset{\iota }{}\delta _\iota \delta _i^{}=\delta _itr(\delta _i)=1$$

valid for any $`i`$ and any $`Ii`$. Thus the fact that $`v`$ is a multiplicative, unital, involutive and trace-preserving translates into the following “multiplicative” formulae.

$$v_{ji}^2=v_{ji}v_{ji}v_{jI}=0\underset{\iota }{}v_{j\iota }=1v_{ji}^{}=v_{ji}\underset{j}{}v_{ji}=1$$

The first four formulae say that each row of $`v`$ is a partition of the unity of $`H`$ with self-adjoint projections. In particular the matrix $`v^{}v`$ is diagonal. The diagonal entries of $`v^{}v`$ being the sums in the fifth formula, this formula says that $`v`$ satisfies $`v^{}v=1`$. Since $`v`$ is a corepresentation, it follows that $`v`$ is unitary and that the antipode is given by the following “third comultiplicative formula”.

$$S(v_{ij})=v_{ji}$$

By applying $`S`$ to the second multiplicative formula we get that the columns of $`v`$ are also partitions of unity with self-adjoint projections.

Summing up, in order for the map $`v`$ to be a coaction the matrix $`v`$ must be a corepresentation, as well as a magic biunitary in the following sense.

###### Definition 1.2.

A matrix $`vM_X(K)`$ over a complex $``$-algebra $`K`$ is called a magic biunitary if its lines and columns are partitions of the unity of $`K`$ with projections.

This vaguely reminds the definition of a magic square in combinatorics.

Let $`Z_i`$ be a finite sets and let $`v_i:(Z_i)(Z_i)H_i`$ be coactions. Consider the corresponding magic biunitary corepresentations $`v_i`$. Then the matrix

$$v_i=\left(\begin{array}{cccc}v_1& 0& \mathrm{}& 0\\ 0& v_2& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 0& 0& \mathrm{}& v_n\end{array}\right)$$

is a magic biunitary corepresentation of the free product $`H_i`$, so we get a coaction of $`H_i`$ on the disoint union $`Z_i`$.

$$v_i:(Z_i)(Z_i)(H_i)$$

This coaction is faithful if and only if all $`v_i`$ are faithful.

As a first example, let $`n_i`$ be positive integers. For each $`i`$ the canonical action of the cyclic group $`_{n_i}`$ on itself produces a faithful coaction – the comultiplication.

$$\mathrm{\Delta }_i:(_{n_i})(_{n_i})(_{n_i})$$

The free product $`(_{n_i})`$ can be computed by using the Fourier transform over cyclic groups and the distributivity of the free product of Hopf $``$-algebras with respect to the $`^{}`$ functor for discrete groups (see Wang ).

$$(_{n_i})^{}(_{n_i})^{}(_{n_i})$$

We get in this way a faithful coaction

$$\mathrm{\Delta }_i:(_{n_i})(_{n_i})^{}(_{n_i})$$

In particular for any $`n4`$ we can take $`n_1=2`$ and $`n_2=n2`$ and we get a faithful coaction of $`^{}(_2_{n2})`$ on the set with $`n`$ points. Thus $`H`$ can be infinite-dimensional. Together with the above remarks on the square of the antipode and on the trace-preservation condition, this justifies the formalism in definition 1.1.

The universal Hopf $`^{}`$-algebra coacting on $`X`$ is constructed by Wang in .

###### Definition 1.3.

The universal $`^{}`$-algebra $`H(X)`$ is defined with generators $`v_{ij}`$ with $`i,jX`$ and with the relations making $`v`$ a magic biunitary.

The comultiplication, counit of antipode of $`H(X)`$ are constructed by using its universal property. Thus $`H(X)`$ is a Hopf $`^{}`$-algebra coacting on $`X`$. For any coaction $`v:(X)(X)H`$ we have the following factorisation diagram.

$$\begin{array}{ccc}(X)& & (X)H(X)\\ & & \\ & v& idp\\ & & \\ & & (X)H\end{array}$$

In particular we have a morphism $`p_{com}:H(X)(G(X))`$ onto the algebra of functions on the usual symmetric group $`G(X)`$. For sets having $`1,2,3`$ points this map $`p_{com}`$ is an isomorphism. If $`X`$ has at least 4 points the above free product example shows that $`H(X)`$ has quotients of the form $`^{}(\mathrm{\Gamma })`$ with $`\mathrm{\Gamma }`$ infinite discrete group. In particular $`H(X)`$ must be non commutative and infinite dimensional, and $`p_{com}`$ cannot be an isomorphism. See Wang .

Some useful information about $`H(X)`$ can be obtained by using corepresentation theory techniques. In  Woronowicz finds a general Tannaka-Krein type duality, and applies it to the algebra $`H=(SU(N))_q`$ with $`q>0`$. The idea is that (1) generators and relations defining $`H`$ translate into a presentation result of the associated tensor category, and (2) this latter equations turn to have a diagrammatic solution, and using diagrams one can compute various corepresentation theory invariants of $`H`$.

The same method works for $`H=H(X)`$. Consider the multiplication and the unit operator of the algebra $`(X)`$.

$$m:(X)(X)(X)u:(X)$$

These are arrows in the tensor $`^{}`$-category whose objects are tensor powers of $`(X)`$, and where arrows are linear maps between such tensor powers. Let $`<m,u>`$ be the tensor $`^{}`$-category generated by $`m`$ and $`u`$. This is by definition the smallest tensor $`^{}`$-category containing $`m`$ and $`u`$. Its objects are the tensor powers of $`(X)`$, and arrows are all possible linear combinations of compositions of tensor products of maps of the form $`m,u,m^{},u^{},id`$, where $`id`$ is the identity of $`(X)`$.

Since $`v`$ is multiplicative and unital we have the following relations.

$$mHom(v^2,v)uHom(1,v)$$

Thus both $`m,u`$ are arrows in the category $`C`$ of finite dimensional corepresentations of $`H(X)`$. The above category $`<m,u>`$ can be regarded as a subcategory of $`C`$.

On the other hand both $`mHom(v^2,v)`$ and $`uHom(1,v)`$ give rise to a collection of relations between coefficients $`v_{ij}`$, which are easily seen to be equivalent to those expressing the magic biunitary condition. At the level of categories, this means that $`C`$ is the completion of $`<m,u>`$, meaning the smallest semisimple tensor $`^{}`$-category containing $`<m,u>`$.

This was step (1) in Woronowicz’s method. What is left is step (2), namely computation of $`<m,u>`$ by using some combinatorial tool, such as planar diagrams. The diagrams needed here are those related to the Temperley-Lieb algebra. There are several approaches to them, beginning with those in work of Jones  and Kauffman . In this paper we use a formalism close to the one of Bisch and Jones in .

Let $`\delta _X=\sqrt{\mathrm{\#}X}`$ and consider the category $`TL^2(\delta _X)`$ whose objects are positive integers and where arrows between $`k`$ and $`l`$ are linear combinations of Temperley-Lieb diagrams between $`2k`$ and $`2l`$ points. (Such a diagram has $`k+l`$ non-crossing strings joining points etc.) The operations are as follows. The composition is vertical concatenation, the tensor product is horizontal concatenation, the involution is upside-down turning and erasing a floating circle is the same as multiplying by $`\delta _X`$.

$$\text{A}\text{B}=\begin{array}{c}\text{B}\\ \text{A}\end{array}\text{A}\text{B}=\text{A}\text{B}\text{ }\text{A}^{}==\delta _X$$

This tensor $`^{}`$-category is generated by the diagrams

$$M=\delta _X^{\frac{1}{2}}U=\delta _X^{\frac{1}{2}}$$

and a direct computation shows that $`Mm`$ and $`Uu`$ gives an isomorphism between $`TL^2(\delta _X)`$ and $`<m,u>`$. Thus the category of finite dimensional corepresentations of $`H(X)`$ is isomorphic to the completion of $`TL^2(\delta _X)`$. See .

Let $`Y,Z`$ be finite sets and consider the product $`X=Y\times Z`$. The projection $`XY`$ gives a unital embedding of $`(Y)`$ into $`(X)`$, so we can consider coactions on $`X`$ which restrict to coactions on $`Y`$.

$$\begin{array}{ccc}(X)& \stackrel{v}{}& (X)H\\ & & \\ & & id\\ & & \\ (Y)& & (Y)H\end{array}$$

For a coaction $`v`$ to restrict to $`(Y)`$, it must send $`(Y)`$ into $`(Y)H`$.

###### Definition 1.4.

The Hopf $`^{}`$-algebra $`H(XY)`$ is the quotient of $`H(X)`$ by the closed two-sided $``$-ideal generated by the relations coming from the equality $`ev=ve`$, where $`e:(X)(X)`$ is the linear map implemented by the projection $`XY`$.

The Hopf $`^{}`$-algebra $`H(XY)`$ coacts on $`X`$ and the coaction restricts to $`Y`$. For any coaction on $`X`$ which restricts to $`Y`$ we have the following factorisation diagram.

$$\begin{array}{ccc}(X)& & (X)H(XY)\\ & & \\ & v& idp\\ & & \\ & & (X)H\end{array}$$

The category of corepresentations of $`H(XY)`$ can be computed by using the same techniques as for $`H(X)`$, with the Fuss-Catalan diagrams of Bisch and Jones .

First, the universal property of $`H(XY)`$ translates into the fact that its category of corepresentations is the completion of the tensor $`^{}`$-category generated by $`m`$, $`u`$ and $`e`$. Let $`\delta _Y=\sqrt{\mathrm{\#}Y}`$ and $`\delta _Z=\sqrt{\mathrm{\#}Z}`$ and consider the category $`FC(\delta _Y,\delta _Z)`$ whose objects are positive integers and where the arrows between $`l`$ and $`k`$ are linear combinations of Fuss-Catalan diagrams between $`4l`$ points and $`4k`$ points. These are by definition Temperley-Lieb diagrams with both rows of points colored

$$y,z,z,y,y,z,z,y,\mathrm{}$$

such that strings join points having the same color. Then $`FC(\delta _Y,\delta _Z)`$ is a tensor $`^{}`$-category, with operations given by usual horizontal and vertical concatenation and upside-down turning of diagrams, plus the following rule: erasing a $`y`$-colored or $`z`$-colored circle is the same as multiplying the diagram by $`\delta _Y`$ or $`\delta _Z`$.

$$\text{y-colored}=\delta _Y\text{z-colored}=\delta _Z$$

With $`\delta _X=\delta _Y\delta _Z=\sqrt{\mathrm{\#}X}`$ this category is generated by the diagrams

$$M=\delta _X^{\frac{1}{2}}U=\delta _X^{\frac{1}{2}}E=\delta _Z^{\frac{1}{2}}\begin{array}{c}\\ \end{array}$$

and computation shows that $`Mm`$, $`Uu`$ and $`Ee`$ gives an isomorphism between $`FC(\delta _Y,\delta _Z)`$ and $`<m,u,e>`$. Thus the category of finite dimensional corepresentations of $`H(XY)`$ is isomorphic to the completion of $`FC(\delta _Y,\delta _Z)`$. See .

Finally, let us mention that quite exotic examples, not to be discussed in this paper, can be obtained from magic biunitary matrices. Let $`X,Y`$ be finite sets and let $`(u_{ij})`$ be a magic biunitary with $`i,jX`$ and $`u_{ij}M_Y()`$. The universal property of $`H(X)`$ gives a representation on $`M_Y()`$ sending the fundamental corepresentation $`v`$ to $`u`$.

$$\pi :H(X)M_Y()(id\pi )v=u$$

By dividing $`H(X)`$ by a suitable ideal we get a factorisation $`\pi =\pi _up_u`$ through a minimal possible Hopf $`^{}`$-algebra $`H(u)`$. This coacts on $`(X)`$ via $`v_u=(idp_u)v`$.

$$\pi _u:H(u)M_Y()(id\pi _u)v_u=u$$

For instance if $`G`$ is a subgroup of $`𝒮_Y`$ and $`u`$ is the magic biunitary corresponding to the action of $`G`$ on $`Y`$ then $`H(u)=(G)`$ and $`v_u=u`$.

More complicated examples come from lattice models and commuting squares. For instance complex Hadamard matrices and Krishnan-Sunder biunitary permutation matrices are known to produce magic biunitaries (cf. , , ). So far nothing seems to be known about the associated Hopf $`^{}`$-algebras, besides their existence.

## 2. Coactions on finite metric spaces

Let $`(X,d)`$ be a finite metric space. That is, we are given a finite set $`X`$ and a function $`d:X\times X_+`$ which is symmetric, which has 0 on the diagonal and positive values outside the diagonal, and whose entries satisfy the triangle inequality.

Let $`G`$ be a group acting on $`X`$. Consider the corresponding coaction of $`(G)`$ on $`X`$.

$$v:(X)(X)(G)v(\delta _i)=\underset{g}{}\delta _{gi}\delta _g$$

The products $`dv`$ and $`vd`$ are given by the following formulae.

$$(dv)_{ij}=\underset{g}{}d(i,gj)\delta _g(vd)_{ij}=\underset{g}{}d(g^1i,j)\delta _g$$

Thus the coaction of $`(G)`$ on $`X`$ preserves the metric if and only if the action of $`G`$ on $`X`$ preserves the metric. This suggests the following definition.

###### Definition 2.1.

Let $`H`$ be the Hopf $`^{}`$-algebra associated to a compact quantum group of Kac type. A coaction of $`H`$ on $`X`$

$$v:(X)(X)Hv(\delta _i)=\underset{j}{}\delta _jv_{ji}$$

is said to preserve the metric if the matrix $`v=(v_{ij})`$ commutes with $`d=(d(i,j))`$.

Let $`H(X,d)`$ be the quotient of $`H(X)`$ by the relations coming from $`dv=vd`$. Then $`H(X,d)`$ coacts on $`(X)`$ and preserves the metric. For any other coaction which preserves the metric we have the following factorisation diagram.

$$\begin{array}{ccc}(X)& & (X)H(X,d)\\ & & \\ & v& idp\\ & & \\ & & (X)H\end{array}$$

In particular we have the following factorisation of the universal coaction

$$\begin{array}{ccc}(X)& & (X)H(X,d)\\ & & \\ & v_{com}& idp_{com}\\ & & \\ & & (X)(G(X,d))\end{array}$$

where $`G(X,d)`$ is the automorphism group of $`(X,d)`$ and $`v_{com}`$ is the corresponding coaction. We will see that in many cases the projection $`p_{com}`$ is an isomorphism.

The simplest example of a finite metric space is a finite set with the 0–1 distance on it. More generally, let us call simplex a finite metric space having the same distance between all pairs of disjoint points.

###### Proposition 2.1.

If $`(X,d)`$ is a simplex then any coaction on $`X`$ preserves the metric. We have $`H(X,d)=H(X)`$.

###### Proof.

The distance on a simplex is given by the formula

$$d=a(𝕀1)$$

where $`a`$ is the non-zero value of the distance, $`1`$ is the identity matrix and $`𝕀`$ is the matrix having 1 everywhere.

$$𝕀=\left(\begin{array}{ccc}1& \mathrm{}& 1\\ \mathrm{}& \mathrm{}& \mathrm{}\\ 1& \mathrm{}& 1\end{array}\right)$$

Let $`v`$ be the magic biunitary corepresentation corresponding to a coaction on $`X`$. Since right and left multiplication by $`𝕀`$ is making sums on rows and columns, $`𝕀`$ commutes with $`v`$. Thus $`v`$ commutes with $`d`$ as well. ∎

The metric analogue of the free product example is as follows. Let $`(Y,D)`$ be a metric space and for each $`iY`$ let $`(Z_i,d_i)`$ be a metric space. Assume that the following condition is satisfied.

$$2D(i,j)d_i(p,q)$$

This must hold for any $`i,jY`$ and for any $`p,qZ_i`$. The disjoint union $`X=Z_i`$ becomes a metric space, with distance $`d`$ equal to $`d_i`$ on each $`Z_i`$ and equal to $`D(i,j)`$ between points of $`Z_i`$ and $`Z_j`$ for $`ij`$. It is useful to keep in mind the following picture: $`(X,d)`$ is made of a metric “macrospace” $`(Y,D)`$ having around each of its points $`i`$ a metric “microspace” $`(Z_i,d_i)`$.

###### Proposition 2.2.

If $`v_i:(Z_i)(Z_i)H_i`$ are coactions then the coaction

$$v_i:(X)(X)(H_i)$$

preserves the metric $`d`$ if and only if each $`v_i`$ preserves the metric $`d_i`$.

###### Proof.

If points of $`Y`$ are labelled from 1 to $`n`$ then the distance on $`X`$ is

$$d=\left(\begin{array}{cccc}d_1& D(1,2)𝕀& \mathrm{}& D(1,n)𝕀\\ D(2,1)𝕀& d_2& \mathrm{}& D(2,n)𝕀\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ D(n,1)𝕀& D(n,2)𝕀& \mathrm{}& d_n\end{array}\right)$$

where $`𝕀`$ denotes rectangular matrices of suitable size filled with $`1`$’s. Since multiplication by $`𝕀`$ is making sums on rows or columns, $`𝕀`$ commutes with each $`v_i`$. Thus $`v_i`$ commutes with $`d`$ is and only if each $`v_i`$ commutes with $`d_i`$. ∎

As an example, let $`Y`$ be the segment of length $`1`$ and let $`Z_i`$ be two segments of length $`\sqrt{2}`$. The metric space $`X`$ is a square. Since $`_2`$ acts on both segments, now diagonals of the square, it follows that $`^{}(_2_2)`$ coacts on the square.

More generally, let $`Y`$ be a simplex with nonzero distance $`A`$ and $`Z`$ be a simplex with nonzero distance $`a`$ and assume that $`Aa`$ and $`2Aa`$. For any $`iY`$ define $`Z_i=Z`$. The disjoint union in the above example is $`X=Y\times Z`$, with the following metric.

$$d=\left(\begin{array}{cccc}a(𝕀1)& A𝕀& \mathrm{}& A𝕀\\ A𝕀& a(𝕀1)& \mathrm{}& A𝕀\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ A𝕀& A𝕀& \mathrm{}& a(𝕀1)\end{array}\right)$$

It is useful to keep in mind the following picture: $`X`$ is a space made of a “macrosimplex” $`Y`$, having around each of its points a copy of the “microsimplex” $`Z`$.

###### Proposition 2.3.

A coaction on $`X`$ preserves the metric if and only if it restricts to $`Y`$. We have $`H(X,d)=H(XY)`$.

###### Proof.

We have the following formula

$$d=A𝕀+(aA)(\mathrm{\#}Z)ea1$$

where $`1`$ is the identity matrix and where $`e`$ is the following operator.

$$e=\frac{1}{\mathrm{\#}Z}\left(\begin{array}{cccc}𝕀& 0& \mathrm{}& 0\\ 0& 𝕀& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 0& 0& \mathrm{}& 𝕀\end{array}\right)$$

Let $`v`$ be a coaction on $`X`$. Since commutation of $`v`$ with $`1`$ and with $`𝕀`$ is automatic, $`v`$ preserves the distance if and only if it commutes with $`e`$. But $`e`$ is the projection onto the subalgebra $`(Y)`$ of $`(X)`$. ∎

Given a finite metric space $`(X,d)`$ and a group $`G`$ acting on $`X`$, the fact that $`G`$ preserves or not the metric only depends on some equivalence class of the metric: the one which takes into account the equalities between various pairs of distances, but neglects their precise values. In other words, the induced action of $`G`$ on $`X\times X`$ must preserve the 0–1 matrix of Kronecker symbols

$$K(i,j,k,l)=\delta _{d(i,j),d(k,l)}$$

Instead of using $`K`$ or other purely combinatorial objects, it is convenient to use the metric and to draw pictures, but to keep in mind that the set of values of the distance function is irrelevant. We will call this values “colors” and the picture of a metric space will consist of points plus colored lines between them, with the convention that same color means same distance. Because of typographical reasons colors in this paper will be different kinds of lines, plus a “void color” that is not pictured. The void color is used in order to simplify pictures and will be typically a most frequent color, i.e. a number $`a`$ which maximizes the following quantity.

$$\mathrm{\#}\{(i,j)|d(i,j)=a\}$$

As an example, here is a rectangle which is not a square. The void color is here the length of the diagonals, which is different from the lengths of the sides.

$$|\begin{array}{c}\mathrm{}\mathrm{}\\ \mathrm{}\mathrm{}\end{array}|$$

Let $`(X,d)`$ be a metric space with color set $`C_+`$. For any color $`aC`$ we denote by $`d_a`$ the 0–1 matrix having $`1`$ if $`d(i,j)=a`$ and 0 elsewhere. The following formula will be called the color decomposition of the metric.

$$d=\underset{aC}{}ad_a$$

For instance the color decomposition for the rectangle having sides of lengths $`a`$ and $`c`$ and diagonals of lengths $`b`$ is as follows (in order to obtain usual $`4\times 4`$ matrices, the numers 1,2,3,4 are assigned clockwise to the vertices of the rectangle).

$$\left(\begin{array}{cccc}0& a& b& c\\ a& 0& c& b\\ b& c& 0& a\\ c& b& a& 0\end{array}\right)=a\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)+b\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\end{array}\right)+c\left(\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 1& 0& 0& 0\end{array}\right)$$

The equivalence classes of the spaces $`(X,d_a)`$ will be called color components of $`(X,d)`$. Note that each $`(X,d_a)`$ is not exactly a metric space, because the “distances” $`d_a`$ can have 0 values outside the diagonal. But each such space corresponds to a unique equivalence class of a metric space, which can be obtained by replacing all non-diagonal $`0`$ entries of $`d_a`$ with some positive number which is different from 1, bigger than 0.5 and smaller than 2. For instance each color component of the rectangle is a square.

With these notations, the equivalence class of a metric space $`(X,d)`$ is given by its color components. The above remark about actions of groups on equivalence classes has the following reformulation. A group $`G`$ acting on $`X`$ preserves the metric if and only if preserves the metric of all color components of $`(X,d)`$.

This has the following analogue.

###### Proposition 2.4.

A coaction of $`H`$ on $`X`$ preserves the metric if and only if it preserves all its color components.

###### Proof.

Assume that $`H`$ preserves the metric and consider the multiplication and comultiplication of $`(X)`$.

$$m:\delta _i\delta _j\delta _i\delta _jc:\delta _i\delta _i\delta _i$$

Then $`m`$ and $`c`$ intertwine $`v^2`$ and $`v`$. It follows that their iterations

$$m^{(k)}:\delta _1\mathrm{}\delta _k\delta _1\mathrm{}\delta _kc^{(k)}:\delta _i\delta _i\mathrm{}\delta _i$$

are in $`Hom(v^k,v)`$ and $`Hom(v,v^k)`$ respectively. In particular the operator

$$d^{(k)}=m^{(k)}d^kc^{(k)}:\delta _i\underset{j}{}d(i,j)^k\delta _j$$

is in the commutant $`End(v)`$ of $`v`$. Since $`d^{(k)}`$ is obtained from $`d`$ by raising all its entries to the power $`k`$, it has the following decomposition.

$$d^{(k)}=\underset{aC}{}a^kd_a$$

If $`A`$ is the biggest color then the sequence $`A^kd^{(k)}`$ of elements of $`End(v)`$ converges to $`d_A`$, so $`d_A`$ has to be an element of $`End(v)`$. By substracting $`Ad_A`$ from $`d`$ we get in this way by induction that each $`d_a`$ is in $`End(v)`$. ∎

###### Corollary 2.1.

Let $`v:(X)(X)H`$ be a metric-preserving coaction. If $`K`$ is an eigenspace of some color component $`d_a`$ then $`v(K)KH`$.

###### Proof.

Consider the orthogonal projection $`P_K`$ onto $`K`$. Since $`K`$ is an eigenspace of $`d_a`$ this projection is in the $`^{}`$-algebra generated by $`d_a`$ in $`((X))`$. Thus from $`d_aEnd(v)`$ we get that $`P_K`$ is in $`End(v)`$ as well. On the other hand we have $`v(K)KH`$ if and only if $`v`$ commutes with $`P_K`$. ∎

## 3. Rules for computing the Hopf algebra

In this section we find some rules for the computation of $`H(X,d)`$ and its corepresentations. There is a lot of structure on finite metric spaces that can be exploited. For instance simple geometric properties of $`(X,d)`$ lead to invariant subspaces or subalgebras of $`v`$ of dimension 1,2 or 3 and the universal properties of the Hopf $`^{}`$-algebras $`^{}()`$, $`(SU(2))`$, $`(SU(2))_1`$, $`(_2)`$ and $`(_3)`$ can be used. However, the computation of $`H(X,d)`$ seems to be hard in the general case and the set of needed “rules” might be infinite. In fact we don’t know what happens in the $`n=8`$ case and our less ambitious project here is just to find enough rules for dealing with the $`n7`$ case.

We begin with reformulations of three facts from the previous sections.

###### Lemma 3.1 (Triangle Rule).

If $`X`$ has at most 3 points then $`H(X,d)=(G(X,d))`$.

###### Lemma 3.2 (Simplex Rule).

If $`X`$ is a simplex having at least 4 points the category of finite dimensional corepresentations of $`H(X,d)`$ is the completion of the category of Temperley-Lieb diagrams of parameter $`\delta _X=\sqrt{\mathrm{\#}X}`$.

###### Lemma 3.3 (Duplex Rule).

If $`X=Y\times Z`$ is a product of simplices then the category of finite dimensional corepresentations of $`H(X,d)`$ is the completion of the category of Fuss-Catalan diagrams of parameters $`\delta _Y=\sqrt{\mathrm{\#}Y}`$ and $`\delta _Z=\sqrt{\mathrm{\#}Z}`$.

Let $`(X,d)`$ be a finite metric space with color set $`C_+`$. For any partition

$$C=\{a_1,\mathrm{},a_m\}\{b_1,\mathrm{},b_n\}\{c_1,\mathrm{},c_p\}\mathrm{}$$

we get a new space $`(X^{},d^{})`$ by identifying all $`a`$-colors, all $`b`$-colors, all $`c`$-colors etc. This is not exactly a metric space, but it corresponds to a unique equivalence class of a metric space (cf. comments in 2.). We say that $`(X^{},d^{})`$ is a decoloration of $`(X,d)`$.

As an example, consider the rectangle. Its color set has three elements $`\{a,b,c\}`$ so there are 5 possible partitions of it. The corresponding decolorations are the rectangle itself (no decoloration), the square (appearing 3 times, obtained by identifying 2 colors) and the 4-simplex (obtained by identifying all colors).

Each color component of $`(X,d)`$ being a decoloration of $`(X,d)`$, proposition 2.4 has the following slight generalisation plus reformulation.

###### Lemma 3.4 (Decoloration Rule).

If $`(X^{},d^{})`$ is a decoloration of $`(X,d)`$ then $`H(X,d)`$ is a quotient of $`H(X^{},d^{})`$.

This can be used as follows. Let $`(X,d)`$ be a finite metric space and assume that we have found a decoloration $`(X^{},d^{})`$ such that $`H(X^{},d^{})`$ is commutative. Then $`H(X,d)`$ must be commutative as well, so it has is equal to $`(G(X,d))`$. A similar corollary holds with “commutativity” replaced by the “transitivity” notion discussed below.

We say that a color $`a`$ is cyclic if there exists a labelling of the points of $`X`$ such that the $`a`$ color connects 1 to 2 to 3 etc.

###### Lemma 3.5 (Cycle Rule).

Assume there exists a cyclic color and that the space has $`n5`$ points. Then $`H(X,d)=(G(X,d))`$.

###### Proof.

By using the decoloration rule it is enough to prove that if a Hopf $`^{}`$-algebra $`H`$ coacts faithfully on the cycle $`(X,d_a)`$ then $`H`$ is commutative.

The matrix of the cycle is

$$M=\left(\begin{array}{cccccccc}0& 1& 0& 0& \mathrm{}& 0& 0& 1\\ 1& 0& 1& 0& \mathrm{}& 0& 0& 0\\ 0& 1& 0& 1& \mathrm{}& 0& 0& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ 0& 0& 0& 0& \mathrm{}& 1& 0& 1\\ 1& 0& 0& 0& \mathrm{}& 0& 1& 0\end{array}\right)$$

Let $`w`$ be a $`n`$-th root of 1 and consider the vector

$$f=\left(\begin{array}{c}1\\ w\\ w^2\\ \mathrm{}\\ w^{n1}\end{array}\right)$$

Then $`f`$ is an eigenvector of $`M`$ with eigenvalue $`w+w^{n1}`$. Now by taking $`w`$ to be a primitive $`n`$-th root of 1, it follows that all vectors $`1,f,f^2,\mathrm{},f^{n1}`$ are eigenvectors of $`M`$. The invariant subspaces of $`M`$ are

$$1,ff^{n1},f^2f^{n2},\mathrm{}$$

where the last subspace has dimension 1 or 2 depending on the parity of $`n`$. Write

$$v(f)=fa+f^{n1}b$$

with $`a,bH`$ (cf. corollary 2.1, to be used many times in what follows). By taking the square of this equality we get

$$v(f^2)=f^2a^2+f^{n2}b^2+1(ab+ba)$$

It follows that $`ab=ba`$ and that $`v(f^2)`$ is given by the formula

$$v(f^2)=f^2a^2+f^{n2}b^2$$

By multiplying this with $`v(f)`$ we get

$$v(f^3)=f^3a^3+f^{n3}b^3+f^{n1}ab^2+fba^2$$

But $`n5`$ implies that 1 and $`n1`$ are different from 3 and from $`n3`$, so we must have $`ab^2=ba^2=0`$. Now by using this and $`ab=ba`$ we get by induction on $`k`$ that

$$v(f^k)=f^ka^k+f^{nk}b^k$$

for any $`k`$. In particular for $`k=n1`$ we get

$$v(f^{n1})=f^{n1}a^{n1}+fb^{n1}$$

On the other hand we have $`f^{}=f^{n1}`$, so by applying $``$ to $`v(f)`$ we get

$$v(f^{n1})=f^{n1}a^{}+fb^{}$$

Thus $`a^{}=a^{n1}`$ and $`b^{}=b^{n1}`$. Together with $`ab^2=0`$ this gives

$$(ab)(ab)^{}=abb^{}a^{}=ab^na^{n1}=(ab^2)b^{n2}a^{n1}=0$$

and from positivity we get $`ab=0`$. Together with $`ab=ba`$ this shows that $`a`$ and $`b`$ commute. On the other hand $`H`$ is generated by the coefficients of $`v`$, which are powers of $`a`$ and $`b`$, so $`H`$ must be commutative. ∎

Assume that the metric space $`(X,d)`$ has an even number of points. A star in $`X`$ is given by two colors $`a`$ and $`b`$ and a labelling of points of $`X`$ from $`1`$ to $`2k`$ such that $`(X,d_a)`$ consists of the segments $`(1,2)`$, $`(3,4)`$,…,$`(2k1,2k)`$ and $`(X,d_b)`$ consists of the segments $`(2,3)`$, $`(4,5)`$,…,$`(2k2,2k1)`$. (If points of $`X`$ are arranged clockwise this doesn’t quite look like a star; but a suitable rearrangement of points justifies terminology.)

###### Lemma 3.6 (Star Rule).

If $`X`$ has a star then $`H(X,d)=(G(X,d))`$.

###### Proof.

By using the projection $`p_{com}`$ it is enough to prove that $`H(X,d)`$ is commutative.

Let $`(X^{},d^{})`$ be the decoloration of $`(X,d)`$ obtained by identifying the colors $`a`$ and $`b`$. The star in $`X`$ becomes a cycle in $`X^{}`$. From the decoloration rule we get that $`H(X,d)`$ is a quotient of $`H(X^{},d^{})`$, so if $`H(X^{},d^{})`$ is commutative then $`H(X,d)`$ is commutative as well. This is the case for $`k3`$, because we have $`2k6`$ and the cycle rule applies.

In the remaining $`k=2`$ case $`X`$ must be a rectangle. Consider the vectors

$$1=\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)A=\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)B=\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)C=\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)$$

By using the color decomposition of the rectangle given in 3. we see that these are eigenvectors for all three matrix distances, corresponding to different eigenvalues. By corollary 2.1 the three 1-dimensional spaces spanned by $`A`$, $`B`$ and $`C`$ must be left invariant by the coaction, so we must have

$$v(A)=Aav(B)=Bbv(C)=Cc$$

for some elements $`a,b,cH`$. We have the following relations between $`A,B,C`$

$$AB=BA=CAC=CA=BCB=BC=A$$

and by applying $`v`$ we get from the multiplicativity of $`v`$ that $`a,b,c`$ satisfy similar formulae, hence commute. But $`a,b,c`$ generate $`H`$, so $`H`$ is commutative. ∎

A coaction $`v:(X)(X)H`$ is called transitive if $`v(f)=f1`$ implies that $`f`$ is a constant function. This is an extension of the classical notion of transitivity: in the $`H=(G)`$ case we have the formulae

$$v(f)=\underset{j}{}\delta _j\underset{g}{}f(g^1j)\delta _gf1=\underset{j}{}\delta _j\underset{g}{}f(j)\delta _g$$

so the coaction of $`(G)`$ is transitive if and only if the action of $`G`$ has one orbit.

A metric space $`(X,d)`$ is called homogenous if its automorphism group acts transitively, meaning has one orbit. This is the same as asking that for any $`x,yX`$ there is a metric-preserving permutation $`g𝒮_X`$ such that $`gx=y`$.

One can say that $`(X,d)`$ is “quantum homogenous” is the coaction of $`H(X,d)`$ is transitive in the above sense. We have here the following necessary condition.

###### Lemma 3.7 (Magic Rule).

If the coaction of $`H(X,d)`$ is transitive then the following condition must be satisfied. For any two points $`x,yX`$ there exists a bijection $`\sigma :XX`$ such that $`\sigma (x)=y`$ and such that $`d(x,z)=d(y,\sigma (z))`$ for any $`z`$.

The terminology comes from the following fact. Assume that $`X`$ has $`n`$ points and that there are exactly $`n1`$ colors. By replacing these colors with the numbers from 1 to $`n1`$, the matrix distance must be a magic matrix, i.e. a $`n\times n`$ matrix having the numbers from 0 to $`n1`$ on each row and column. As an example, here is the magic matrix corresponding to the rectangle.

$$\left(\begin{array}{cccc}0& 1& 2& 3\\ 1& 0& 3& 2\\ 2& 3& 0& 1\\ 3& 2& 1& 0\end{array}\right)$$

###### Proof.

For any color $`a`$ we have $`d_aEnd(v)`$, so $`d_a(1)`$ is fixed by the coaction. But $`d_a(1)`$ is scalar if and only if the matrix $`d_a`$ has the same number of 1’s on each row. ∎

We say that a color $`a`$ is bicyclic if $`(X,d_a)`$ consists of two disjoint cycles $`C_nC_N`$.

###### Lemma 3.8 (Bicycle Rule).

Assume there exists a bicyclic color component of the form $`C_nC_N`$ with $`nN`$. Then the coaction of $`H(X,d)`$ is not transitive.

###### Proof.

By using the decoloration rule it is enough to prove that if a Hopf $`^{}`$-algebra $`H`$ coacts on the bicycle then the coaction is not transitive.

If one of $`n`$ and $`N`$ is $`2`$ then the magic rule shows that $`H(X,d)`$ is not transitive. So we may assume $`n,N3`$. Label the points of $`X`$ such that the matrix of distances is

$$M=\left(\begin{array}{cc}M_n& 0\\ 0& M_N\end{array}\right)$$

where $`M_n`$ and $`M_N`$ are the matrices of the two cycles. Let $`w`$ be a primitive $`n`$-th root of unity and consider the vector $`f`$ consisting of powers of $`w`$. Then the eigenvalues and eigenvectors of the matrix $`(_{0}^{M_n}{}_{0}{}^{0})`$ are given by

$$2:\left[\left(\begin{array}{c}1\\ 0\end{array}\right)\right],(w+w^{n1}):[\left(\begin{array}{c}f\\ 0\end{array}\right),\left(\begin{array}{c}f^{n1}\\ 0\end{array}\right)],(w^2+w^{n2}):[\left(\begin{array}{c}f^2\\ 0\end{array}\right),\left(\begin{array}{c}f^{n2}\\ 0\end{array}\right)]\mathrm{}$$

where each eigenvalue is followed by its eigenvectors and where the end of the sequence depends on the parity of $`n`$. Similarly, the matrix $`(_{0}^{0}{}_{M_N}{}^{0})`$ gives

$$2:\left[\left(\begin{array}{c}0\\ 1\end{array}\right)\right],(W+W^{N1}):[\left(\begin{array}{c}0\\ F\end{array}\right),\left(\begin{array}{c}0\\ F^{N1}\end{array}\right)],(W^2+W^{N2}):[\left(\begin{array}{c}0\\ F^2\end{array}\right),\left(\begin{array}{c}0\\ F^{N2}\end{array}\right)]\mathrm{}$$

where $`W`$ is a primitive $`N`$-th root of unity and $`F`$ is the vector consisting of powers of $`W`$. Since $`nN`$ it follows that the decomposition corresponding to $`M`$ is

$$[\left(\begin{array}{c}1\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 1\end{array}\right)],\begin{array}{c}[\left(\begin{array}{c}f\\ 0\end{array}\right),\left(\begin{array}{c}f^{n1}\\ 0\end{array}\right)],[\left(\begin{array}{c}f^2\\ 0\end{array}\right),\left(\begin{array}{c}f^{n2}\\ 0\end{array}\right)],\mathrm{}\\ & \\ [\left(\begin{array}{c}0\\ F\end{array}\right),\left(\begin{array}{c}0\\ F^{N1}\end{array}\right)],[\left(\begin{array}{c}0\\ F^2\end{array}\right),\left(\begin{array}{c}0\\ F^{N2}\end{array}\right)],\mathrm{}\end{array}$$

where the two series might interfere on their last entries, depending on the parity of $`n`$ and $`N`$. Consider the first subspace, corresponding to the eigenvalue 2.

$$[\left(\begin{array}{c}1\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 1\end{array}\right)]=[\left(\begin{array}{c}1\\ 1\end{array}\right),\left(\begin{array}{c}1\\ 1\end{array}\right)]$$

By corollary 2.1 this space is invariant by $`v`$, so we can find $`\xi ,uH`$ such that

$$v\left(\begin{array}{c}1\\ 1\end{array}\right)=\left(\begin{array}{c}1\\ 1\end{array}\right)\xi +\left(\begin{array}{c}1\\ 1\end{array}\right)u$$

From the trace-preservation property of $`v`$ we get that $`tr\left(\begin{array}{c}1\\ 1\end{array}\right)1=0`$ is equal to

$$(trid)v\left(\begin{array}{c}1\\ 1\end{array}\right)=tr\left(\begin{array}{c}1\\ 1\end{array}\right)\xi +tr\left(\begin{array}{c}1\\ 1\end{array}\right)u=2\xi $$

It follows that $`\xi =0`$, so we have

$$v\left(\begin{array}{c}1\\ 1\end{array}\right)=\left(\begin{array}{c}1\\ 1\end{array}\right)u$$

From this we get that $`v`$ is given on the subspace by

$$v\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)\frac{1+u}{2}+\left(\begin{array}{c}0\\ 1\end{array}\right)\frac{1u}{2}$$

$$v\left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)\frac{1u}{2}+\left(\begin{array}{c}0\\ 1\end{array}\right)\frac{1+u}{2}$$

Assume that one of $`n`$ and $`N`$ is greater than 5, say $`n5`$. By arguing like in the proof of the cycle rule we get from a formula of type

$$v\left(\begin{array}{c}f\\ 0\end{array}\right)=\left(\begin{array}{c}f\\ 0\end{array}\right)a+\left(\begin{array}{c}f^{n1}\\ 0\end{array}\right)b$$

that the following formula is true for any $`k`$.

$$v\left(\begin{array}{c}f^k\\ 0\end{array}\right)=\left(\begin{array}{c}f^k\\ 0\end{array}\right)a^k+\left(\begin{array}{c}f^{nk}\\ 0\end{array}\right)b^k$$

In particular for $`k=n`$ we get

$$v\left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)a^n+\left(\begin{array}{c}1\\ 0\end{array}\right)b^n=\left(\begin{array}{c}1\\ 0\end{array}\right)(a^n+b^n)$$

and comparison with the above formula for $`v\left(\begin{array}{c}1\\ 0\end{array}\right)`$ gives $`u=1`$. It follows that $`\left(\begin{array}{c}1\\ 1\end{array}\right)`$ is a fixed vector of the coaction, so the coaction is not transitive.

The remaining case is $`n,N4`$. Since $`n,N`$ are different and both are greater than 3, one is 3 and the other is 4. Assume $`N=4`$ and consider the vector

$$\gamma =F^2=\left(\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right)$$

This is the unique eigenvector of $`M_N`$ corresponding to the eigenvalue $`0`$. Since $`n=3`$ is odd, $`M_n`$ has no eigenvalue 0. It follows that $`\left(\begin{array}{c}0\\ \gamma \end{array}\right)`$ is the unique eigenvector of $`M`$ corresponding to the eigenvalue $`0`$, so we must have

$$v\left(\begin{array}{c}0\\ \gamma \end{array}\right)=\left(\begin{array}{c}0\\ \gamma \end{array}\right)c$$

for some $`cH`$. By taking the square of this equality we get

$$v\left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)c^2$$

and comparison with the above formula for $`v\left(\begin{array}{c}1\\ 0\end{array}\right)`$ gives $`u=1`$. Once again, it follows that $`\left(\begin{array}{c}1\\ 1\end{array}\right)`$ is a fixed vector of the coaction, so the coaction is not transitive. ∎

## 4. Classification for $`n7`$

The purpose of this section is to compute the corepresentation theory invariants of the Hopf algebra $`H(X,d)`$, in case the metric space $`(X,d)`$ has at most 7 points.

In order to cut off unwanted complexity, there is a natural condition to be put on $`(X,d)`$, namely quantum homogeneity. Recall from previous section that $`(X,d)`$ is said to be quantum homogenous when the universal coaction $`v:(X)(X)H(X,d)`$ is transitive, meaning that $`v(f)=f1`$ implies that $`f`$ is a scalar function.

The motivating remark here is that functions satisfying $`v(f)=f1`$ are those belonging to the relative commutant of the associated subfactor (see ), so quantum homogeneity corresponds to the well-known irreducibility condition in subfactors.

It is clear from definitions that a homogenous space is quantum homogenous. It turns out that for spaces having at most 7 points the converse holds. We do not know if these notions are equivalent in general.

The decoloration rule shows that all color components of a quantum homogenous space must be quantum homogenous. These color components are graphs, so our first task is to prove that for a graph having at most 7 vertices, homogeneity is equivalent to quantum homogeneity.

The complement of a graph $`(X,d)`$ with vertex set $`X`$ and incidency matrix $`d`$ is by definition the graph $`(X,𝕀1d)`$, where $`𝕀`$ is the matrix filled with 1’s. Since $`v𝕀=𝕀v=𝕀`$ for any magic biunitary matrix $`v`$, we have $`H(X,d)=H(X,𝕀1d)`$.

###### Lemma 4.1.

A graph with $`n7`$ vertices is homogenous if and only if it is quantum homogenous. There are $`24`$ such graphs.

(1) point.

(2) $`2`$ points, segment.

(3) $`3`$ points, triangle.

(4) $`4`$ points, tetrahedron, $`2`$ segments, square.

(5) $`5`$ points, $`5`$-simplex, $`5`$-cycle.

(6) $`6`$ points, $`6`$-simplex, plus $`6`$-cycle, $`3`$ segments, $`2`$ triangles, and their complements.

(7) $`7`$ points, $`7`$-simplex, $`7`$-cycle and its complement.

###### Proof.

Homogenous implies quantum homogenous, and all graphs in the list are homogenous. It remains to prove that any quantum homogenous graph with $`n7`$ vertices is in the list.

Let $`(X,d)`$ be such a graph. The magic rule applies and shows that the incidency matrix $`d`$ has the same number of 1’s, say $`k`$, on each of its rows and columns. Thus $`(X,d)`$ must be a $`k`$-regular graph, for a certain number $`k`$. By replacing the graph with its complement we may assume that that the valence $`k`$ of the graph is smaller or equal than the valence $`nk1`$ of its complement.

Summing up, it remains to prove the following assertion. Any quantum homogenous $`k`$-regular graph with $`n`$ vertices, $`2k+1n7`$, is in the list.

For $`k=0`$ the graph must be $`n`$ points and no edges, in the list.

For $`k=1`$ the only graphs are the 2 or 3 segments, in the list.

For $`k=2`$ the graph must be a union of $`m`$-cycles with values of $`m`$ greater than 3. The bicycle rule shows that the $`m`$’s must be the same for all $`m`$-cycles, and the graphs left are the $`n`$-cycles with $`3n7`$, plus the 2 triangles, all of them in the list.

For $`k3`$ we must have $`n2\times 3+1=7`$. The only possible case is $`k=3`$ and $`n=7`$, but this is excluded by the observation that the incidency matrix must have $`nk/2`$ values of $`1`$ above the diagonal. ∎

###### Theorem 4.1.

Let $`(X,d)`$ be a metric space having at most 7 points. Then one of the following happens.

(1) The coaction of $`H(X,d)`$ is not transitive.

(2) $`H(X,d)`$ is the algebra of functions on the usual automorphism group of $`(X,d)`$.

(3) $`X`$ is a simplex and the category of finite dimensional corepresentations of $`H(X,d)`$ is the completion of the category of Temperley-Lieb diagrams of parameter $`\delta _X=\sqrt{\mathrm{\#}X}`$.

(4) $`X=Y\times Z`$ is a product of simplices and the category of finite dimensional corepresentations of $`H(X,d)`$ is the completion of the category of Fuss-Catalan diagrams of parameters $`\delta _Y=\sqrt{\mathrm{\#}Y}`$ and $`\delta _Z=\sqrt{\mathrm{\#}Z}`$.

###### Proof.

If $`X`$ is a simplex the triangle or simplex rule applies and shows that we are in situation (2) or (3). If $`X`$ doesn’t satisfy the magic rule we are in situation (1). Thus it remains to prove the following statement.

Let $`(X,d)`$ be metric space having $`n=4,5,6`$ or $`7`$ points, having at least two colors and satisfying the magic rule. Then (1), (2) or (4) holds.

For $`n=4`$ the only spaces which are left are the square and the rectangle. The duplex rule applies to the square and the star rule applies to the rectangle.

For $`n=5,7`$ lemma 4.1 shows that all color components must be $`n`$-cycles. The cycle rule applies and shows that we are in situation (2).

For $`n=6`$ lemma 4.1 shows that all color components must be among the following 6 graphs: 6-cycle, 3 segments, 2 triangles, and their complements. If there is a 6-cycle the cycle rule applies and (2) must hold. The same happens whenever the complement of the 6-cycle is present. In the remaining cases, either the duplex rule applies and (4) must hold, or the star rule applies and we are in situation (2). ∎

In the $`n=8`$ case the situation is a bit more complicated. There are 14 homogenous graphs with 8 vertices, and an analogue of lemma 4.1 holds. Techniques in this paper apply to most of them, and there are 3 graphs left. First is the cube, which can be shown to correspond to a tensor product between 2 Temperley-Lieb algebras. Second is a graph which looks like a wheel with 8 spokes, which gives $`(D_8)`$. Third is the graph formed by 2 squares. This corresponds to a Fuss-Catalan algebra on 3 colors, but the proof is quite long.

As for the passage from graphs to metric spaces, or colored graphs, this is done by an easy application of the decoloration rule, as in proof of theorem 4.1. However, there is a problem at $`n=8`$, with one space left, which is formed by 2 rectangles. We don’t know yet how to compute invariants of the associated Hopf algebra.

For $`n=9`$ an analogue of lemma 4.1 holds one again, but the proof is long. All graphs give $`(D_9)`$ or correspond to Fuss-Catalan algebras, except for an exceptional graph, which looks like a torus. So far, we have no results about this graph.