text:
# Operator representations of cross product algebras of Podles’ quantum spheres

## 0 Introduction

In this paper we investigate Hilbert space representations of the left cross product $``$-algebras $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ of the quantized enveloping algebras $`𝒰_q(\mathrm{su}_2)`$ and the coordinate algebras $`𝒪(S_{qc}^2)`$, $`c[0,+\mathrm{}]`$, of the Podles’ spheres. As discussed in the introduction of our previous paper \[SW\], there are two principal methods. In the first approach, we begin with a representation of the $``$-algebras $`𝒪(S_{qc}^2)`$ given in a canonical form and extend it to a representation of $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$. The main technical tool for this is to ”decouple” the cross relations of the cross product algebra by finding an auxiliary $``$-subalgebra $`𝒴_c`$ of a slightly larger cross product $``$-algebra $`\widehat{𝒪}(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ which commutes with the $``$-algebra $`𝒪(S_{qc}^2)`$. Such decouplings have been found and studied in \[F\]. Since elements of $`𝒴_c`$ act as unbounded operators, we impose some regularity conditions during the derivation of the corresponding representations. In the second approach, we assume that there exists some $`l\frac{1}{2}_0`$ such that the restriction to $`𝒰_q(\mathrm{su}_2)`$ is a direct sum of representations $`T_{l+n}`$, $`n_0`$. The Heisenberg representation (see \[SW\], 5.2) of $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ satisfies this condition with $`l=0`$. We show that for any $`l\frac{1}{2}`$ there exist precisely two inequivalent irreducible representations of $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ having this property. In the case $`l=1/2`$ the existence of these representations was known for two special quantum spheres. For the Podles’ sphere $`S_{q,\mathrm{}}^2`$ related to the quantum vector space $`_q^3`$ they appeared in \[SW\], Section 6.5. For the standard quantum sphere $`S_{q,0}^2`$ the representations with $`l=1/2`$ are contained in \[DS\].

This paper is organized as follows. The definition of the cross product algebra $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ is given in Section 1. The ”decoupling” procedure is developed in Section 2. Representations of the auxiliary $``$-algebra $`𝒴_c`$ are studied in Section 3. The first approach as explained above is carried out in Section 4. The second approach is contained in Section 5.

All facts and notions on quantum groups used in this paper can be found, for instance, in \[KS\]. The algebra $`𝒰_q(\mathrm{sl}_2)`$ and the Podles’ spheres $`S_{qc}^2`$ have been discovered in \[KR\] and \[P\], respectively.

Throughout this paper, $`q`$ stands for a real number of the open interval $`(0,1)`$. We abbreviate $`\lambda :=(qq^1)`$, $`\lambda _n:=(1q^{2n})^{1/2}`$ and $`[n]:=(q^nq^n)/(qq^1)`$.

## 1 Definition of the cross product algebra

Let $`𝒰`$ be a Hopf $``$-algebra and let $`𝒳`$ be a left $`𝒰`$-module $``$-algebra, that is, $`𝒳`$ is a unital $``$-algebra with left $`𝒰`$-action $``$ satisfying $`fxy=(f_{(1)}x)(f_{(2)}y)`$, $`f1=\epsilon (f)1`$ and $`(fx)^{}=S(f)^{}x^{}`$ for $`x,y𝒳`$ and $`f𝒰`$. Here $`\mathrm{\Delta }(f)=f_{(1)}f_{(2)}`$ is the Sweedler notation for the comultiplication $`\mathrm{\Delta }(f)`$ of $`f𝒰`$. Then the left cross product $``$-algebra $`𝒳𝒰`$ is the $``$-algebra generated by the two $``$-subalgebras $`𝒳`$ and $`𝒰`$ with respect to the cross commutation relation

$$fx=(f_{(1)}x)f_{(2)},x𝒳,f𝒰.$$
(1)
The Hopf $``$-algebra $`𝒰_q(\mathrm{su}_2)`$ is generated by elements $`E,F,K,K^1`$ with relations

$$KK^1=K^1K=1,KE=qEK,FK=qKF,EFFE=\lambda ^1(K^2K^2),$$
(2)
involution $`E^{}=F`$, $`K=K`$ and comultiplication

$$\mathrm{\Delta }(E)=EK+K^1E,\mathrm{\Delta }(F)=FK+K^1K,\mathrm{\Delta }(K)=KK.$$

There is a dual pairing $`,`$ of Hopf $``$-algebras $`𝒰_q(\mathrm{su}_2)`$ and $`𝒪(\mathrm{SU}_q(2))`$ given on generators by

$$K^{\pm 1},d=K^1,a=q^{\pm 1/2},E,c=F,b=1$$

and zero otherwise, where $`a,b,c,d`$ are the usual generators of the Hopf algebra $`𝒪(\mathrm{SU}_q(2))`$ (see e.g. \[KS\], Chapter 4).

We shall use the definition of the coordinate algebras $`𝒪(S_{qc}^2)`$, $`c[0,+\mathrm{}]`$, of Podles’ spheres as given in \[P\]. For $`c[0,+\mathrm{})`$, $`𝒪(S_{qc}^2)`$ is the $``$-algebra with generators $`A=A^{},B,B^{}`$ and defining relations

$$AB=q^2BA,AB^{}=q^2B^{}A,B^{}B=AA^2+c,BB^{}=q^2Aq^4A^2+c.$$
(3)
For $`c=+\mathrm{}`$, the defining relations of $`𝒪(S_{q,+\mathrm{}}^2)`$ are

$$AB=q^2BA,AB^{}=q^2B^{}A,B^{}B=A^2+1,BB^{}=q^4A^2+1.$$
(4)
Let $`c<\mathrm{}`$. As shown in \[P\], $`𝒪(S_{qc}^2)`$ is a right $`𝒪(\mathrm{SU}_q(2))`$-comodule $``$-algebra such that

$$x_1:=q^1(1+q^2)^{1/2}B,x_1:=(1+q^2)^{1/2}B^{},x_0:=1(1+q^2)A.$$
(5)
transform by the spin $`1`$ matrix corepresentation $`(t_{ij}^1)`$ of $`\mathrm{SU}_q(2)`$. Hence $`𝒪(S_{qc}^2)`$ is a left $`𝒰_q(\mathrm{su}_2)`$-module $``$-algebra with left action given by $`fx_j=_ix_if,t_{ij}^1`$ for $`f𝒰_q(\mathrm{su}_2)`$, $`j=1,0,1`$. Inserting the form of the matrix $`(t_{ij}^1)`$ (see \[P\], p. 194, or \[KS\], p. 124) and the Hopf algebra pairing $`,`$ into (1) we derive the following cross relations for the cross product algebra $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$:

$`KA=AK,EA=AE+q^{1/2}B^{}K,FA=AFq^{3/2}BK,`$
$`KB=q^1BK,EB=qBEq^{1/2}(1+q^2)AK+q^{1/2}K,FB=qBF,`$
$`KB^{}=qB^{}K,EB^{}=q^1B^{}E,FB^{}=q^1B^{}F+q^{1/2}(1+q^2)AKq^{1/2}K.`$
That is, $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ is the algebra with generators $`A`$, $`B`$, $`B^{}`$, $`E`$, $`F`$, $`K`$, $`K^1`$, with defining relations (2), (3) (resp. (4)) and the preceding set of cross relations.

For $`c=\mathrm{}`$, we set

$$x_1:=q^1(1+q^2)^{1/2}B,x_1:=(1+q^2)^{1/2}B^{},x_0:=(1+q^2)A.$$
(6)
Then the cross relations for the cross product algebra $`𝒪(S_q\mathrm{}^2)𝒰_q(\mathrm{su}_2)`$ can be written as

$`KA=AK,EA=AE+q^{1/2}B^{}K,FA=AFq^{3/2}BK,`$
$`KB=q^1BK,EB=qBEq^{1/2}(1+q^2)AK,FB=qBF,`$
$`KB^{}=qB^{}K,EB^{}=q^1B^{}E,FB^{}=q^1B^{}F+q^{1/2}(1+q^2)AK.`$
## 2 ”Decoupling” of the cross product algebra

Let us first suppose that $`c[0,+\mathrm{})`$. From the relations $`AB=q^2BA`$ and $`AB^{}=q^2B^{}A`$ it is clear that $`𝒮=\{A^n;n_0\}`$ is a left and right Ore set of the algebra $`𝒪(S_{qc}^2)`$. Moreover the algebra $`𝒪(S_{qc}^2)`$ has no zero divisors. Hence the localization algebra, denoted by $`\widehat{𝒪}(S_{qc}^2)`$, of $`𝒪(S_{qc}^2)`$ at $`𝒮`$ exists. The $``$-algebra $`𝒪(S_{qc}^2)`$ is then a $``$-subalgebra of $`\widehat{𝒪}(S_{qc}^2)`$ and all elements $`A^n`$, $`n_0`$, are invertible in $`\widehat{𝒪}(S_{qc}^2)`$. From Theorem 3.4.1 in \[LR\] we conclude that $`\widehat{𝒪}(S_{qc}^2)`$ is a left (resp. right) $`𝒰_q(\mathrm{su}_2)`$-module $``$-algebra which contains $`𝒪(S_{qc}^2)`$ as a left (resp. right) $`𝒰_q(\mathrm{su}_2)`$-module $``$-subalgebra. The left action of the generators $`E,F,K`$ on $`A^1`$ is given by

$$EA^1=q^{5/2}B^{}A^2,FA^1=q^{1/2}BA^2,KA^1=A^1.$$

Hence the left cross product algebra $`\widehat{𝒪}(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ is a well-defined $``$-algebra.

Let $`𝒴_c`$ denote the $``$-subalgebra of $`\widehat{𝒪}(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ generated by

$`X:=q^{3/2}\lambda FK^1A+qB,X^{}=q^{3/2}\lambda AK^1E+qB^{},`$ (7)
$`Y:=qK^2A,Y^1=q^1A^1K^2.`$ (8)
Note that $`Y=Y^{}`$. It is straightforward to check that the elements $`X`$, $`X^{}`$, $`Y`$, $`Y^1`$ commute with the generators $`A`$, $`B`$, $`B^{}`$ of $`𝒪(S_{qc}^2)`$. Hence the algebras $`𝒴_c`$ and $`\widehat{𝒪}(S_{qc}^2)`$ commute inside the cross product algebra $`\widehat{𝒪}(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$. Moreover, the generators of $`𝒴_c`$ satisfy the commutation relations

$$YX=q^2XY,YX^{}=q^2X^{}Y,X^{}Xq^2XX^{}=(1q^2)(Y^2+c).$$
(9)
We denote by $`𝒰_q^{}(\mathrm{su}_2)`$ the Hopf $``$-subalgebra generated by $`e:=EK`$, $`f:=K^1F`$ and $`k:=K^2.`$ As an algebra, $`𝒰_q^{}(\mathrm{su}_2)`$ has generators $`e`$, $`f`$, $`k`$, $`k^1`$ with defining relations

$$kk^1=k^1k=1,ke=q^2ek,kf=q^2fk,effe=\lambda ^1(kk^1).$$
(10)
The comultiplication on the generators $`e`$, $`f`$, $`k`$ is given by

$$\mathrm{\Delta }(e)=ek+1e,\mathrm{\Delta }(f)=f1+k^1f,\mathrm{\Delta }(k)=kk.$$

From (7) and (8) we obtain

$$f=q^{1/2}\lambda ^1(XqB)A^1,e=q^{1/2}\lambda ^1(X^{}q^1B^{})Y^1,k=qY^1A.$$
(11)
Hence the two commuting algebras $`𝒴_c`$ and $`\widehat{𝒪}(S_{qc}^2)`$ generate the $``$-subalgebra $`\widehat{𝒪}(S_{qc}^2)𝒰_q^{}(\mathrm{su}_2)`$ of $`\widehat{𝒪}(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$. So one can say that $`𝒴_c`$ and $`\widehat{𝒪}(S_{qc}^2)`$ completely ”decouple” the cross product algebra $`\widehat{𝒪}(S_{qc}^2)𝒰_q^{}(\mathrm{su}_2)`$.

There is an alternative way to define the $``$-algebra $`\widehat{𝒪}(S_{qc}^2)𝒰_q^{}(\mathrm{su}_2)`$ by taking the two sets $`A=A^{}`$, $`B`$, $`B^{}`$ and $`X`$, $`X^{}`$, $`Y=Y^{}`$, $`Y^1`$ of pairwise commuting generators with defining relations (3), (9) and the obvious relations

$$AA^1=A^1A=1,YY^1=Y^1Y=1.$$
(12)
Indeed, if we define $`e,f,k`$ by (11), then the relations (10) of $`𝒰_q(\mathrm{su}_2)`$ and the cross relations of $`\widehat{𝒪}(S_{qc}^2)𝒰_q^{}(\mathrm{su}_2)`$ can be derived from this set of defining relations.

The larger cross product algebra $`\widehat{𝒪}(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ can be redefined in a similar manner if we replace the generator $`Y`$ by $`K`$. That is, $`\widehat{𝒪}(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ is the $``$-algebra with the two sets $`A=A^{}`$, $`B`$, $`B^{}`$ and $`X`$, $`X^{}`$, $`K`$, $`K^1`$ of pairwise commuting generators with defining relations (3), (12), and

$$KA=AK,BK=qKB,KB^{}=qB^{}K,X^{}Xq^2XX^{}=(1q^2)(q^2K^4A^2+c).$$
(13)
The generators $`F`$ and $`E`$ are then given by

$$F=q^{3/2}\lambda ^1(XqB)KA^1,E=q^{3/2}\lambda ^1A^1K(X^{}qB^{}).$$
(14)
The preceding considerations and facts carry over almost verbatim to the case $`c=+\mathrm{}`$. The only difference is that in the case $`c=+\mathrm{}`$ one has to set $`c=1`$ in the third equations of (9) and (13).

## 3 Operator representations of the $``$-algebra $`𝒴_𝐜`$

For the study of representations of the $``$-algebra $`𝒴_c`$ we need two auxiliary lemmas. The first one restates the Would decomposition of an isometry (see \[SF\], Theorem 1.1), while the second is Lemma 4.2 (ii) in \[SW\].

###### Lemma 3.1

Each isometry $`v`$ on a Hilbert space $`𝒦`$ is up to unitary equivalence of the following form: There exist Hilbert subspaces $`𝒦^u`$ and $`𝒦_0^s`$ of $`𝒦`$ and a unitary operator $`v_u`$ on $`𝒦^u`$ such that $`v=v_uv_s`$ on $`𝒦=𝒦^u𝒦^s`$ and $`v_s`$ acts on $`𝒦^s=_{n=0}^{\mathrm{}}𝒦_n^s`$ by $`v_s\zeta _n=\zeta _{n+1}`$, where each $`𝒦_n^s`$ is $`𝒦_0^s`$ and $`\zeta _n𝒦_n^s`$. Moreover, $`𝒦^u=_{n=0}^{\mathrm{}}v^n𝒦`$.

###### Lemma 3.2

Let $`v`$ be the operator $`v_s`$ on $`𝒦^s=_{n=0}^{\mathrm{}}𝒦_n^s`$, $`𝒦_n^s=𝒦_0^s`$, from Lemma 3.1 and let $`Y`$ be a self-adjoint operator on $`𝒦^s`$ such that $`q^2vYYv`$. Then there is a self-adjoint operator $`Y_0`$ on the Hilbert space $`𝒦_0^s`$ such that $`Y\zeta _n=q^{2n}Y_0\zeta _n`$ and $`v\zeta _n=\zeta _{n+1}`$ for $`\zeta _n𝒦_n^s`$ and $`n_0`$.

We treat the case $`c[0,+\mathrm{})`$. Suppose that we have a representation of relations (9) by closed operators $`X`$, $`X^{}`$ and a self-adjoint operator $`Y`$ with trivial kernel acting on a Hilbert space $`𝒦`$.

Let $`X=v|X|`$ be the polar decomposition of the operator $`X`$. Since $`q(0,1)`$, $`c0`$ and $`\mathrm{ker}Y=\{0\}`$, we have $`\mathrm{ker}X=\{0\}`$ by the third equation of (9). Hence $`v`$ is an isometry on $`𝒦`$, that is, $`v^{}v=I`$.

By (9), we have $`YX^{}X=X^{}XY`$. We assume that the self-adjoint operators $`Y`$ and $`X^{}X`$ strongly commute. Then $`Y`$ and $`|X|=(X^{}X)^{1/2}`$ also strongly commute. Again by (9), $`Yv|X|=YX=q^2XY=q^2v|X|Y=q^2vY|X|`$. Since $`\mathrm{ker}|X|=\mathrm{ker}X=\{0\}`$, we conclude that

$$q^2vY=Yv.$$
(15)
Since $`X^{}=|X|v^{}`$, the third equation of (9) rewrites as

$$|X|^2=q^2v|X|^2v^{}+(1q^2)(Y^2+c).$$
(16)
Multiplying by $`v`$ and using the relations $`v^{}v=I`$ and (15) we get

$$|X|^2v=v\left(q^2|X|^2+(1q^2)(q^4Y^2+c)\right).$$

Proceeding by induction and using once more (15) we derive

$$|X|^2v^n=v^n\left(q^{2n}|X|^2+(1q^{2n})(q^{2n+2}Y^2+c)\right).$$
(17)
Now we use the Would decomposition $`v=v_uv_s`$ on $`𝒦=𝒦^u𝒦^s`$ of the isometry $`v`$ by Lemma 3.1. Since $`𝒦^u=_{n=0}^{\mathrm{}}v^n𝒦`$ and $`Yv=q^2vY`$, the Hilbert subspace $`𝒦^u`$ reduces the self-adjoint operator $`Y`$. From (17) it follows that $`|X|^2`$ leaves a dense subspace of the space $`𝒦^u`$ invariant. We assume that $`𝒦^u`$ reduces $`|X|^2`$. Hence we can consider all operators occurring in relation (17) on the subspace $`𝒦^u`$. For the unitary part $`v_u`$ of $`v`$ we have $`v_uv_u^{}=I`$ on $`𝒦^u`$. Multiplying (17) by $`(v_u^{})^n`$ and using again relation (15) we derive on $`𝒦^u`$

$$0q^{2n}v_u^n|X|^2(v_u^{})^n=|X|^2(1q^{2n})c+q^2Y^2q^{2n+2}Y^2$$

for all $`n`$. Letting $`n\mathrm{}`$ and remembering that $`\mathrm{ker}Y=\{0\}`$ and $`q(0,1)`$ we conclude that the latter is only possible when $`𝒦^u=\{0\}`$. That is, the isometry $`v`$ is (unitarily equivalent to ) the unilateral shift operator $`v_s`$.

Since $`v=v_s`$, Lemma 3.2 applies to the relation $`q^2vY=Yv`$. Hence there exists a self-adjoint operator $`Y_0`$ on $`𝒦_0^s`$ such that $`Y\zeta _n=q^{2n}Y_0\zeta _n`$ on $`𝒦^s=_{n=0}^{\mathrm{}}𝒦_n^s`$, $`𝒦_n^s=𝒦_0^s`$. Since $`v^{}\zeta _0=0`$, (16) yields $`|X|^2\zeta _0=(1q^2)(Y_0^2+c)\zeta _0`$. Using this equation and (16) we compute

$`|X|^2\zeta _n`$ $`=|X|^2v^n\zeta _0=v^n\left(q^{2n}|X|^2+(1q^{2n})(q^{2n+2}Y^2+c)\right)\zeta _0`$
$`=v^n\left(q^{2n}(1q^2)(Y_0^2+c)\zeta _0+(1q^{2n})(q^{2n+2}Y_0^2+c)\zeta _0\right)`$
$`=\lambda _{n+1}^2(q^{2n}Y_0^2+c)\zeta _n`$ (18)
for $`\zeta _n𝒦_n^s`$. We assumed above that the pointwise commuting self-adjoint operator $`|X|^2`$ and $`Y`$ strongly commute. Hence their reduced parts on each subspace $`𝒦_n^s`$ strongly commute. Therefore, (3) implies that $`|X|\zeta _n=\lambda _{n+1}(q^{2n}Y_0^2+c)^{1/2}\zeta _n`$. Recall that $`X=v|X|`$ and $`X^{}=|X|v^{}`$. Renaming $`𝒦_n^s`$ by $`𝒦_n`$ and summarizing the preceding, we obtain the following form of the operators $`X`$, $`X^{}`$ and $`Y`$:

$`X\zeta _n=\lambda _{n+1}(q^{2n}Y_0^2+c)^{1/2}\zeta _{n+1},X^{}\zeta _n=\lambda _n(q^{2n2}Y_0^2+c)^{1/2}\zeta _{n1},`$
$`Y\zeta _n=q^{2n}Y_0\zeta _n\mathrm{on}𝒦=_{n=0}^{\mathrm{}}𝒦_n,𝒦_n=𝒦_0,`$
where $`Y_0`$ is self-adjoint operator with trivial kernel on the Hilbert space $`𝒦_0`$. Conversely, it is easy to check that these operators $`X,X^{},Y`$ satisfy the relations (9), so they define indeed a Hilbert space representation of the $``$-algebra $`𝒴_c`$.

## 4 Representations of the cross product algebras: <br>First approach

First let us review the representations of the $``$-algebra $`𝒪(S_{qc}^2)`$ from \[P\]. For $`c[0,\mathrm{})`$ and $`n_0`$ we abbreviate

$$\lambda _\pm :=1/2\pm (c+1/4)^{1/2},c_\pm (n):=(c+\lambda _\pm q^{2n}(\lambda _\pm q^{2n})^2)^{1/2}.$$

Let $`^0,_0^+`$ and $`_0^{}`$ be Hilbert spaces and let $`u`$ be a unitary operator on $`^0`$. Let $`^\pm =_{n=0}^{\mathrm{}}_n^\pm `$, where $`_n^\pm =_0^\pm `$, and let $`=^0^+^{}`$ for $`c(0,+\mathrm{}]`$ and $`=^0^+`$ for $`c=0`$. The generators of $`𝒪(S_{qc}^2)`$ act on the Hilbert space $``$ by the following formulas:

$`c[0,+\mathrm{}):A=0,B=c^{1/2}u,B^{}=c^{1/2}u^{}\mathrm{on}^0,`$
$`A\eta _n=\lambda _\pm q^{2n}\eta _n,B\eta _n=c_\pm (n)\eta _{n1},B^{}\eta _n=c_\pm (n+1)\eta _{n+1}\text{on}^\pm .`$
$`c=+\mathrm{}:A=0,B=u,B^{}=u^{}\text{on}_0,`$
$`A\eta _n=\pm q^{2n}\eta _n,B\eta _n=(1q^{4n})^{1/2}\eta _{n1},B^{}\eta _n=(1q^{4(n+1)})^{1/2}\eta _{n+1}\text{on}^\pm .`$
Remind that for $`c=0`$ there is no Hilbert space $`^{}`$. From Proposition 4 in \[P\] it follows that up to unitary equivalence any $``$-representation of $`𝒪(S_{qc}^2)`$ is of the above form. Note that all operators are bounded and $`^0=\mathrm{ker}A`$, $`A>0`$ on $`^+`$ and $`A<0`$ on $`^{}`$.

Next we show that for any $``$-representation of the algebras $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ or $`𝒪(S_{qc}^2)𝒰_q^{}(\mathrm{su}_2)`$ the space $`^0`$ is $`\{0\}`$, so the operator $`A`$ is invertible. We carry out the reasoning for $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$. Assuming that the commuting self-adjoint operators $`A`$ and $`K`$ strongly commute it follows that $`K`$ leaves $`^0=\mathrm{ker}A`$ invariant. By (3) (resp. (4)), $`B^0^0`$. Let $`\xi ^0`$. Using the relation $`FA=AFq^{3/2}BK`$ we see that

$$q^3BK\xi ^2=AF\xi ^2=q^{3/2}BK\xi ,AF\xi =q^{3/2}ABK\xi ,F\xi =0.$$

That is, $`BK\xi =0`$ and $`AF\xi =0`$, so that $`F\xi ^0`$. For $`c(0,+\mathrm{}]`$, $`BK`$ is invertible on $`^0`$ and hence $`\xi =0`$. For $`c=0`$ we have $`B^{}\xi =B^{}F\xi =0`$. From the cross relation $`FB^{}=q^1B^{}F+q^{1/2}(1+q^2)AKq^{1/2}K`$ we get $`K\xi =0`$ and so $`\xi =0`$. Thus, $`^0=\{0\}`$.

Consider now a $``$-representation of the $``$-algebra $`\widehat{𝒪}(S_{qc}^2)𝒰_q^{}(\mathrm{su}_2)`$. Its restriction to $`𝒪(S_{qc}^2)`$ is a $``$-representation of the form described above with $`^0=\{0\}`$. All operators of the $``$-subalgebra $`𝒴_c`$ commute with $`A`$ and $`B`$. Let us assume that the spectral projections of the self-adjoint operator $`A`$ commute also with all operators of $`𝒴_c`$. (Note that for a $``$-representation by bounded operators on a Hilbert space the latter fact follows. For unbounded $``$-representation it does not and we restrict ourselves to the class of well-behaved representations which satisfy this assumption.) Since $`_n^\pm `$ is the eigenspace of $`A`$ at eigenvalue $`\lambda _\pm q^{2n}`$ and these eigenvalues are pairwise distinct, the operators of $`𝒴_c`$ leave $`_n^\pm `$ invariant. That is, we have a $``$-representation of $`𝒴_c`$ on $`_n^\pm `$. But $`𝒴_c`$ commutes also with $`B`$. Since $`B`$ is a weighted shift operators with weights $`c_\pm (n)0`$ for $`n`$, it follows that the representations of $`𝒴_c`$ on $`_n^\pm =_0^\pm `$ are the same for all $`n_0`$. Using the structure of the representation of the $``$-algebra $`𝒴_c`$ on the Hilbert space $`𝒦:=_0^\pm `$ derived in Section 3 and inserting the formulas for $`X,X^{},Y`$ and $`A,B,B^{}`$ into (11), one obtains the action of the generators $`e,f,k,k^1`$ of $`𝒰_q^{}(\mathrm{su}_2)`$. We do not list these formulas, but we will do so below for the generators of $`𝒰_q(\mathrm{su}_2)`$.

Let us turn to a $``$-representation of the larger $``$-algebra $`\widehat{𝒪}(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$. Then, in addition to the considerations of the preceding paragraph, we have to deal with the generator $`K`$. We assumed above that $`K`$ and $`A`$ are strongly commuting self-adjoint operators. Therefore, $`K`$ commutes with the spectral projections of $`A`$. Hence each space $`_n^\pm `$ is reducing for $`K`$. The relation $`BK=qKB`$ implies that there is an invertible self-adjoint operator $`K_0`$ on $`_0^\pm `$ such that $`K\eta _n=q^nK_0\eta _n`$ for $`\eta _n_n^\pm `$. Recall that we have $`XK=qKX`$ and $`YK=KY`$ in the algebra $`\widehat{𝒪}(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$. Inserting for $`X`$ and $`Y`$ the corresponding operators on $`𝒦_0^\pm =_{n=0}^{\mathrm{}}𝒦_n`$ from Section 3 we conclude that there exists an invertible self-adjoint operator $`H`$ on $`𝒦_0`$ such that $`K_0\zeta _n=q^nH\zeta _n`$ for $`\zeta _n𝒦_n`$. Further, since $`Y=qK^2A`$, we have $`Y\zeta _0=Y_0\zeta _0=qH^2\lambda _\pm \zeta _0`$ for $`\zeta _0𝒦_0`$. Inserting the preceding facts and the results from Section 3 into (14) and renaming $`𝒦_0`$ by $`𝒢`$ we obtain the following $``$-representations of the cross product $``$-algebra $`\widehat{𝒪}(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ for $`c(0,+\mathrm{})`$:

$`(I)_{\pm ,H}:`$ $`A\eta _{nj}=\lambda _\pm q^{2n}\eta _{nj},B\eta _{nj}=c_\pm (n)\eta _{n1,j},B^{}\eta _{nj}=c_\pm (n+1)\eta _{n+1,j},`$
$`E\eta _{nj}=q^{1/2}\lambda ^1[q^n\lambda _j(\lambda _\pm ^2q^{2j}c+H^4)^{1/2}H\eta _{n,j1}`$
$`q^j(\lambda _\pm ^2q^{2n2}c+\lambda _\pm ^1q^{2n+2})^{1/2}H\eta _{n+1,j}],`$
$`F\eta _{nj}=q^{1/2}\lambda ^1[q^n\lambda _{j+1}(\lambda _\pm ^2q^{2j2}c+H^4)^{1/2}H\eta _{n,j+1}`$
$`q^j(\lambda _\pm ^2q^{2n}c+\lambda _\pm ^1q^{2n})^{1/2}H\eta _{n1,j}],`$
$`K\eta _{nj}=q^{nj}H\eta _{nj},`$
where $`H`$ is an invertible self-adjoint operator on a Hilbert space $`𝒢`$. The representation space is the direct sum $`=_{n,j=0}^{\mathrm{}}_{nj}`$, where $`_{nj}=𝒢`$. In the case $`c=0`$ there is only the representation $`(I)_{+,H}`$. The case $`c=+\mathrm{}`$ has already been treated in \[SW\].

## 5 Representations of the cross product algebras: <br>Second approach

For $`l\frac{1}{2}_0`$ let $`T_l`$ denote the type 1 spin $`l`$ representations of $`𝒰_q(\mathrm{su}_2)`$. Recall that $`T_l`$ is an irreducible $``$-representation of the $``$-algebra $`𝒰_q(\mathrm{su}_2)`$ acting on a $`(2l+1)`$-dimensional Hilbert space with orthonormal basis $`\{v_j^l;j=l,l+1,\mathrm{},l\}`$ by the formulas (see, for instance, \[KS\], p. 61)

$$Kv_j^l=q^jv_j^l,Ev_j^l=[lj]^{1/2}[l+j+1]^{1/2}v_{j+1}^l,Fv_j^l=[lj+1]^{1/2}[l+j]^{1/2}v_{j1}^l.$$
(19)
Let $`l_0\frac{1}{2}_0`$ be fixed. The aim of this section is classify all $``$-representations of the cross product $``$-algebra $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ having the following property:

The restriction to $`𝒰_q(\mathrm{su}_2)`$ is the direct sum representation $`_{n=0}^{\mathrm{}}T_{l_0+n}`$. $`()`$
In this section we shall use the generators $`x_j`$ defined by (5) (resp. (6)) rather than $`A,B,B^{}`$.

Suppose we have such a representation. First note that then there exist complex numbers $`\alpha ^ϵ(l,j)`$ and $`\beta ^ϵ(l,j)`$, $`ϵ=+,0,`$, $`ll_0`$, $`j=l,l+1,\mathrm{},l`$, $`ll_0_0`$, such that

$`x_1v_j^l`$ $`=\alpha ^+(l,j)v_{j+1}^{l+1}+\alpha ^0(l,j)v_{j+1}^l+\alpha ^{}(l,j)v_{j+1}^{l1}`$ (20)
$`x_0v_j^l`$ $`=\beta ^+(l,j)v_j^{l+1}+\beta ^0(l,j)v_j^l+\overline{\beta ^+(l1,j)}v_j^{l1}`$ (21)
$`x_1v_j^l`$ $`=q^1(\overline{\alpha ^{}(l+1,j1})v_{j1}^{l+1}+\overline{\alpha ^0(l,j1)}v_{j1}^l+\overline{\alpha ^+(l1,j1)}v_{j1}^{l1}),`$ (22)
where the vectors $`v_{l+1}^l`$, $`v_{l1}^l`$ and the corresponding coefficients are set zero. In order to prove this fact we argue as in \[DS\]; a similar argument appeared also in \[S\], p. 258. Since $`Kx_1=qx_1K`$, $`x_1v_j^l`$ is a weight vector with weight $`j+1`$. Moreover, since $`E^{lj+1}x_1v_j^l=q^{l+j1}x_1E^{lj+1}v_j^l=0`$, $`x_1v_j^l`$ is in the linear span of vectors $`v_{j+1}^r`$, where $`rl+1`$. Similarly, replacing $`x_1`$ by $`x_1`$ and $`E`$ by $`F`$ we conclude that $`x_1v_j^l`$ belongs to the span of vectors $`v_{j1}^r`$, $`rl+1`$. Therefore, since $`x_1=q^1x_1^{}`$, $`x_{\pm 1}v_j^l\mathrm{Lin}\{v_{j\pm 1}^{l1},v_{j\pm 1}^l,v_{j\pm 1}^{l+1}\}`$, so $`x_{\pm 1}v_j^l`$ is of the form (20) (resp. (22)). From the last two relations of (3) (resp. (4)) it follows that $`x_0v_j^l`$ is of the form (21).

Inserting (19) and (20)–(22) into the equation $`Ex_1v_j^l=q^1x_1Ev_j^l`$ we get

$`[lj]^{1/2}[l+j+3]^{1/2}\alpha ^+(l,j)`$ $`=q^1[lj]^{1/2}[l+j+1]^{1/2}\alpha ^+(l,j+1),`$
$`[lj1]^{1/2}[l+j+2]^{1/2}\alpha ^0(l,j)`$ $`=q^1[lj]^{1/2}[l+j+1]^{1/2}\alpha ^0(l,j+1),`$
$`[lj2]^{1/2}[l+j+1]^{1/2}\alpha ^{}(l,j)`$ $`=q^1[lj]^{1/2}[l+j+1]^{1/2}\alpha ^{}(l,j+1).`$
The solutions of these recurrence relations are given by

$`\alpha ^+(l,j)`$ $`=q^{l+j}[l+j+1]^{1/2}[l+j+2]^{1/2}[2l+1]^{1/2}[2l+2]^{1/2}\alpha ^+(l,l),`$
$`\alpha ^0(l,j)`$ $`=q^{l+j+1}[lj]^{1/2}[l+j+1]^{1/2}[2l]^{1/2}\alpha ^0(l,l1),`$
$`\alpha ^{}(l,j)`$ $`=q^{l+j+2}[lj1]^{1/2}[lj]^{1/2}[2]^{1/2}\alpha ^{}(l,l2).`$
Similarly, from the equation $`Ex_0v_j^l=(x_0E+[2]^{1/2}x_1K)v_j^l`$ we obtain

$`[lj+1]^{1/2}[l+j+2]^{1/2}\beta ^+(l,j)=[lj]^{1/2}[l+j+1]^{1/2}\beta ^+(l,j+1)+[2]^{1/2}q^j\alpha ^+(l,j),`$
$`[lj]^{1/2}[l+j+1]^{1/2}\beta ^0(l,j)=[lj]^{1/2}[l+j+1]^{1/2}\beta ^0(l,j+1)+[2]^{1/2}q^j\alpha ^0(l,j).`$
The equation $`Ex_0v_l^l=(x_0E+[2]^{1/2}x_1K)v_l^l`$ yields in addition

$$\beta ^+(l,l)=q^l[2]^{1/2}[2l+2]^{1/2}\alpha ^+(l,l).$$
(23)
Further, the equation $`0=v_l^l,(x_1F+q[2]^{1/2}x_0KqFx_1)v_l^l`$ implies that

$$\alpha ^0(l,l1)=[2]^{1/2}[2l]^{1/2}q^{l+1}\beta ^0(l,l).$$
(24)
Using (23) and (24) it follows that the above recurrence relations for $`\beta ^+(l,j)`$ and $`\beta ^0(l,j)`$ have the following solutions:

$`\beta ^+(l,j)`$ $`=q^j[lj+1]^{1/2}[l+j+1]^{1/2}[2]^{1/2}[2l+1]^{1/2}[2l+2]^{1/2}\alpha ^+(l,l),`$ (25)
$`\beta ^0(l,j)`$ $`=(1q^{l+j+1}[lj][2][2l]^1)\beta ^0(l,l).`$ (26)
From $`0=v_{l1}^l,(Ex_1qx_1E[2]^{1/2}x_0K)v_{l1}^{l1}`$ we derive that $`\beta ^+(l1,l1)=q^l[2l1]^{1/2}\overline{\alpha ^{}(l,l2)}`$. Combining this equation with (23) gives

$$\alpha ^{}(l,l2)=q^{2l1}[2]^{1/2}[2l1]^{1/2}[2l]^{1/2}\overline{\alpha ^+(l1,l1)}.$$
(27)
From (23)–(27) we conclude that the representation is completely described if the numbers $`\alpha ^+(l,l)`$ and $`\beta ^0(l,l)`$ for $`l=l_0,l_0+1,\mathrm{}`$ are known. Our next aim is to determine these numbers.

Since $`\mathrm{ker}B=\{0\}`$ (cf. Section 4), we have $`\alpha ^+(l,l)0`$. By applying a unitary transformation, we can assume without loss of generality that $`\alpha ^+(l,l)`$ is a positive real number. Furthermore, $`\beta ^0(l,l)`$ is real since $`x_0`$ is self-adjoint. As a consequence, all coefficients occurring in (20)–(22) are real.

We now compute $`\beta ^0(l_0,l_0)`$ for $`l_0>0`$. Assume first that $`c<\mathrm{}`$. We abbreviate $`\rho :=1+(q+q^1)^2c`$. The two relations $`BB^{}=q^2Aq^4A^2+c`$ and $`B^{}B=AA^{}+c`$ lead to the equations

$`(1+q^2)(\alpha ^0(l_0,l_0)^2+\alpha ^{}(l_0+1,l_01)^2)=`$
$`q^2\rho +(1q^2)\beta ^0(l_0,l_0)(\beta ^0(l_0,l_0)^2+\beta ^+(l_0,l_0)^2),`$
$`(1+q^2)\alpha ^+(l_0,l_0)^2=q^2\rho (1q^2)q^2\beta ^0(l_0,l_0)q^4(\beta ^0(l_0,l_0)^2+\beta ^+(l_0,l_0)^2).`$
By inserting (23), (24) and (27) into these two relations, we get after some computations

$`(1+q^2)q[2l_0+3][2l_0+2]^1\alpha ^+(l_0,l_0)^2=`$
$`q^2\rho (1q^2)q^2\beta ^0(l_0,l_0)q^4\beta ^0(l_0,l_0)^2,`$ (28)
$`(1+q^2)q^{2l_0+1}[2l_0+3][2l_0+2]^1[2l_0+1]^1\alpha ^+(l_0,l_0)^2=`$
$`q^2\rho +(1q^2)\beta ^0(l_0,l_0)q^2[2]^1[2l_0]^1\left([2l_0+3]+q^{2l_0}\right)\beta ^0(l_0,l_0)^2.`$
Eliminating $`\alpha ^+(l_0,l_0)`$ from these equations we obtain the following quadratic equation for the coefficient $`\beta ^0(l_0,l_0)`$:

$$q^2\left([2l_0+2][2l_0]^1\beta ^0(l_0,l_0)\right)^2(1q^2)[2l_0+2][2l_0]^1\beta ^0(l_0,l_0)\rho =0.$$

This equation has the solutions $`\beta ^0(l_0,l_0)_\pm `$ given by

$$\beta ^0(l_0,l_0)_\pm =[2l_0][2l_0+2]^1(q^2\lambda _\pm \lambda _{}).$$
(29)
In the case $`c=\mathrm{}`$ one gets by analogous calculations the quadratic equation $`q^2([2l_0+2][2l_0]^1\beta ^0(l_0,l_0))^2(q+q^1)^2=0`$ with the solutions

$$\beta ^0(l_0,l_0)_\pm =\pm [2l_0][2l_0+2]^1(q^2+1).$$
(30)
Note that $`\beta ^0(l_0,l_0)_+>0`$ and $`\beta ^0(l_0,l_0)_{}<0`$ for $`l_0>0`$. Now let $`l_0=0`$. Then $`h()=v_0^0,v_0^0`$ is the unique $`𝒰_q(\mathrm{su}_2)`$-invariant state on $`𝒪(S_{qc}^2)`$. Hence $`\beta ^0(0,0)=x_0v_0^0,v_0^0=h(x_0)=0`$. That is, formulas (29) are also valid for $`l_0=0`$.

Next we determine the coefficient $`\beta ^0(l_0+n,l_0+n)`$ for $`n`$. Using the fact that $`x_1^nv_{l_0}^{l_0}^1x_1^nv_{l_0}^{l_0}=v_{l_0+n}^{l_0+n}`$ and the commutation relations of the generators of the algebras $`𝒪(S_{qc}^2)`$ we derive

$`x_1^nv_{l_0}^{l_0}^2\beta ^0(l_0+n,l_0+n)=x_1^nv_{l_0}^{l_0},x_0x_1^nv_{l_0}^{l_0}`$
$`=x_1^nv_{l_0}^{l_0},\left(q^{2n}x_1^nx_0+(1q^{2n})x_1^n\right)v_{l_0}^{l_0}`$
$`=x_1^nv_{l_0}^{l_0}^2\left(1q^{2n}+q^{2n}\beta ^0(l_0,l_0)\right)+q^{2n}\beta ^+(l_0,l_0)x_1^nv_{l_0}^{l_0},x_1^nv_{l_0}^{l_0+1}.`$ (31)
On the other hand, applying the relation $`x_1v_{l_0}^{l_0}=\alpha ^+(l_0,l_0)v_{l_0+1}^{l_0+1}`$ and the commutation rules of the cross product algebra we compute

$`[2l_0+2]^{1/2}x_1^nv_{l_0}^{l_0},x_1^nv_{l_0}^{l_0+1}=x_1^nv_{l_0}^{l_0},x_1^nFv_{l_0+1}^{l_0+1}`$
$`=x_1^nv_{l_0}^{l_0},\left(q^nFx_1^nq[2n][2]^{1/2}x_0x_1^{n1}K\lambda [n][n1][2]^{1/2}x_1^{n1}K\right)v_{l_0+1}^{l_0+1}`$
$`=\left([2n]q^{l_0+2}\beta ^0(l_0+n,l_0+n)\lambda q^{l_0+1}[n][n1]\right)[2]^{1/2}\alpha ^+(l_0,l_0)^1x_1^nv_{l_0}^{l_0}^2.`$
Inserting this identity into (5) and using (23) with $`l`$ replaced by $`l_0`$ we obtain after some further computations

$$\beta ^0(l_0+n,l_0+n)=[2l_0+2n+2]^1\left([2l_0+2]\beta ^0(l_0,l_0)+(q^21)[n][2l_0+n+1]\right).$$

By (29) and (30), this equation can be written as

$$\beta ^0(l,l)_\pm =[2l+2]^1\left([2l_0](q^2\lambda _\pm \lambda _{})(1q^2)[ll_0][l+l_0+1]\right)$$
(32)
and

$$\beta ^0(l,l)_\pm =[2l+2]^1\left(\pm q^1[2][2l_0](1q^2)[ll_0][l+l_0+1]\right)$$
(33)
for $`c<\mathrm{}`$ and $`c=\mathrm{}`$, respectively.

Finally, we determine $`\alpha ^+(l,l)`$. Note that (5) remains valid if $`l_0`$ is replaced by an arbitrary $`ll_0`$. For $`c<\mathrm{}`$, Equation (5) is equivalent to

$$\alpha ^+(l,l)^2=[2][2l+2][2l+3]^1\left(c+1/4\{(1+q^2)^1(1\beta ^0(l,l))1/2\}^2\right).$$

Inserting $`\beta ^0(l,l)_\pm `$ from (29) into this equation we obtain two solutions $`\alpha ^+(l,l)_\pm `$ which can be written as

$`\alpha ^+(l,l)_\pm =`$ $`[2]^{1/2}[2l+3]^{1/2}[2l+2]^{1/2}([2l+2]^2(c+1/4)`$
$`\{\lambda /2[ll_0+1][l+l_0+1]\pm [2l_0](c+1/4)^{1/2}\}^2)^{1/2}.`$ (34)
By similar arguments one gets in the case $`c=\mathrm{}`$

$`\alpha ^+(l,l)_\pm =`$ $`[2]^{1/2}[2l+3]^{1/2}[2l+2]^{1/2}([2l+2]^2`$
$`\{\lambda [2]^1[ll_0+1][l+l_0+1]\pm [2l_0]\}^2)^{1/2}.`$ (35)
By Equations (32)–(35), all coefficients $`\alpha ^ϵ(l,j)`$ and $`\beta ^ϵ(l,j),ϵ=+,0,`$, are known, so the corresponding representation of the cross product algebra is completely described by formulas (20)–(22). Thus we have shown that for $`l_0\frac{1}{2}`$ there exits at most two$``$-representations of $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ satisfying condition $`()`$. For $`l_0=0`$ there is only one such representation. From the corresponding formulas it follows easily that these representations are irreducible.

It still remains to verify that formulas (20)–(21) define a representation of $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$. For $`l_0=0`$ this is clear, because then $`v_0^0`$ is a $`𝒰_q(\mathrm{su}_2)`$-invariant vector and hence we have the Heisenberg representation. For $`l_0\frac{1}{2}`$ this can be done by showing that the defining relations of $`𝒪(S_{qc}^2)`$ and the cross relations of $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ are satisfied. We have checked this. We omit the details of these lengthy and tedious computations. In a forthcoming paper we will construct for any $`l_0\frac{1}{2}`$ two inequivalent $``$-representations of $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ for which $`()`$ holds. By the uniqueness proof given above, these representations must be given by formulas (20)–(21), so these formulas define indeed a $``$-representation.

Let us summarize the outcome of the preceding considerations:
For any $`l_0\frac{1}{2}`$ there exist two $``$-representations and for $`l_0=0`$ there exists one $``$-representation of the cross product $``$-algebra $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$ such that the restrictions to the $``$-subalgebra $`𝒰_q(\mathrm{su}_2)`$ is the representation $`_{n=0}^{\mathrm{}}T_{l_0+n}`$.
These representations are irreducible. They are labeled by the lower indices $`+`$ and $``$ of the coefficients $`\alpha ^+(l,l)`$ and $`\beta ^0(l,l)`$ given by (34) and (32) (resp. (35) and (33)). The underlying Hilbert space has an orthonormal basis $`\{v_j^l;j=l,\mathrm{},l`$, $`l_0`$, $`ll_0\}`$. The generators $`E,F,K`$ of $`𝒰_q(\mathrm{su}_2)`$ act on this basis by (19). The action of the generators $`x_1,x_0,x_1`$ of $`𝒪(S_{qc}^2)`$ is given by the following formulas:

$`x_1v_j^l=`$ $`q^{l+j}[l+j+1]^{1/2}[l+j+2]^{1/2}[2l+1]^{1/2}[2l+2]^{1/2}\alpha ^+(l,l)_\pm v_{j+1}^{l+1}`$
$`q^{j+2}[lj]^{1/2}[l+j+1]^{1/2}[2]^{1/2}[2l]^1\beta ^0(l,l)_\pm v_{j+1}^l`$
$`q^{l+j+1}[lj1]^{1/2}[lj]^{1/2}[2l1]^{1/2}[2l]^{1/2}\alpha ^+(l1,l1)_\pm v_{j+1}^{l1},`$
$`x_0v_j^l=`$ $`q^j[lj+1]^{1/2}[l+j+1]^{1/2}[2]^{1/2}[2l+1]^{1/2}[2l+2]^{1/2}\alpha ^+(l,l)_\pm v_j^{l+1}`$
$`+\left(1q^{l+j+1}[lj][2][2l]^1\right)\beta ^0(l,l)_\pm v_j^l`$
$`+q^j[lj]^{1/2}[l+j]^{1/2}[2]^{1/2}[2l1]^{1/2}[2l]^{1/2}\alpha ^+(l1,l1)_\pm v_j^{l1},`$
$`x_1v_j^l=`$ $`q^{l+j}[lj+1]^{1/2}[lj+2]^{1/2}[2l+1]^{1/2}[2l+2]^{1/2}\alpha ^+(l,l)_\pm v_{j1}^{l+1}`$
$`+q^j[lj+1]^{1/2}[l+j]^{1/2}[2]^{1/2}[2l]^1\beta ^0(l,l)_\pm v_{j1}^l`$
$`q^{l+j1}[l+j1]^{1/2}[l+j]^{1/2}[2l1]^{1/2}[2l]^{1/2}\alpha ^+(l1,l1)_\pm v_{j1}^{l1}.`$
For $`l_0>0`$ the two representations are not unitarily equivalent. For $`l_0=0`$ they coincide with the Heisenberg representations of $`𝒪(S_{qc}^2)𝒰_q(\mathrm{su}_2)`$.


format: text

text:
# Traveling Salesmen in the Presence of Competition

## 1 Introduction

In the classical Traveling Salesman Problem (TSP), we are given a (weighted) graph $`G=(V,E)`$ and the task to find a shortest roundtrip that visits every vertex precisely once. This reflects the situation where a salesman has to visit a set of customers and return to his initial position.

However, a salesman may be confronted with competitors who are eager to sign up the same clientele – giving a new twist to the old motto “first come, first serve”.

This situation motivates the “Competitive Salesmen problem” (CSP):

We are given a (directed or undirected) road system, i.e., a graph $`G=(V,E)`$ and the locations of the customers, i.e., a subset $`V_CV`$ of the vertices. There are two players, I and II, with starting positions $`v_I`$ and $`v_{II}`$, and an initial score of zero. Starting with I, both players take turns moving by changing from the current location to an adjacent vertex. Depending on the scenario, players may or may not be allowed to pass. At any given time, both players know of their own and their opponent’s position as well as about all the remaining vertices with customers. If a player reaches a vertex with a customer, his score is increased by one, and the vertex is removed from the set $`V_C`$ of still available customers, but not removed from $`V`$. The game ends when no further customers can be captured, i. e., when $`V_C=\mathrm{}`$ or when no player has a path to an uncaptured customer. Whoever has a higher score at the end of the play, wins. If both players end up with the same score, the game is tied.

An immediate generalization is to consider two competing teams of salesmen; in the CSP$`(h,k)`$, a move of player I consists of moving one of his $`h`$ pieces, while player II has the choice between one of his $`k`$ pieces.

## 2 Preliminaries

The CSP is a combinatorial game. See  for classical references on this well-studied area, and  for other related papers. Here we just note an important distinction for the outcome of games that are not won by either player:

A game that is won neither by I nor by II is called

* tied, if it ends with both players having the same score,
* drawn, if it does not end.

Throughout this paper, we mostly concentrate on the case of an undirected graph. Some of the results include the directed case, but we do point out some additional difficulties in one interesting case. Throughout the paper, there are a number of illustrations; in these figures, the set $`V_CV`$ is indicated by circled dots. Without loss of generality, we assume that a start vertex never belongs to $`V_C`$; in several cases, a start vertex is indicated by a hexagon.

The rest of this paper is organized as follows. In Section 3, we show that the CSP is PSPACE-complete, even for the case of bipartite undirected graphs, with both players starting at distance 2 from each other. In Section 4, we discuss the situation in which both players start from the same vertex. We show that even in this case, player I may not be able to avoid a loss, and that there may be draws. We also show that in the case of bipartite graphs, player I can avoid a loss. We also show that this result does not apply to directed graphs. In Section 5, we give some results and open problems for the special case of trees, and Section 6 considers the further restriction to trees with only one vertex of degree higher than two.

## 3 Complexity

While the TSP on directed or undirected graphs is merely NP-complete, the two-player competitive game CSP turns out to be PSPACE-complete.

###### Theorem 3.1

The decision problem whether player I can win in CSP$`(1,1)`$ is PSPACE-complete, even for the special case of bipartite graphs, with both players starting at distance 2 from each other.

Proof: A position in CSP$`(h,k)`$ is a quintuple $`(\tau ,G,V_C^{^{}},u_I,u_{II})`$, where $`\tau \{I,II\}`$ indicates whether Player I or Player II moves from the position, $`G=(V,E)`$ is the (di-)graph on which the game is played, $`V_C^{^{}}`$ is the current set of uncaptured customers; and $`u_I`$ and $`u_{II}`$ are the vertices on which player I and player II reside. A draw can be declared after a position is repeated, that is, when a new position is encountered which is identical to a previous one. Identical positions can be detected by sequentially storing all the positions from the position at which $`V_C^{^{}}`$ was last diminished until it decreases again, beginning with the original $`V_C`$. If there are $`h`$ and $`k`$ salesmen for the two sides, at most $`O(n^{h+k})`$ positions have to be stored between any two consecutive changes of $`V_C^{^{}}`$, where $`n=|V|`$. If $`h`$ and $`k`$ are fixed, this is of polynomial size in the input size, in particular, if $`h=k=1`$. Therefore, for fixed $`h`$ and $`k`$, CSP$`(h,k)`$ PSPACE.

To see that CSP$`(1,1)`$ is PSPACE-hard, we describe a reduction from Quantified 3SAT (Q3SAT), where the Boolean formula $`F`$, containing $`m`$ clauses and $`n`$ variables, is in conjunctive normal form with 3 literals per clause.

For technical reasons, and without loss of generality, we shall make the following assumptions.

* The number $`n`$ of variables is even; because otherwise we may postfix $`F`$ with $`x_{n+1}x_{n+2}x_{n+3}(x_{n+1}+\overline{x}_{n+1}+x_{n+2})(\overline{x}_{n+2}+x_{n+3}+\overline{x}_{n+3})`$.
* There is a clause which contains a true literal and a false literal for every truth assignment of the variables; because if such a clause does not exist, then we can postfix $`F`$ with $`x_{n+1}x_{n+2}(x_{n+1}+\overline{x}_{n+1}+x_{n+2})(x_{n+1}+x_{n+2}+\overline{x}_{n+2})`$.

From a given instance of Q3SAT, we construct an instance of CSP$`(1,1)`$ by specifying the graph $`G=(V,E)`$ on which it is played. For simplicity and clearer drawings, we first construct a graph that contains some odd cycles in the subgraphs representing the clauses. It is straightforward to turn this graph into a bipartite one, by subdividing all the original edges, in effect doubling all distances.

We proceed to describe $`G`$ by listing all vertices and edges of the construction. In the following, we use $`B:=n^2/2`$ for simpler notation. Different parts of the construction are shown in Figure 1 for the variable gadget, in Figure 2 for the $`m`$ clause gadgets, and in Figure 3 for a cache gadget.

$`V`$ $`=`$ $`\{x_i,\overline{x}_i:1in\}`$
$``$ $`\{v_I,v_{II}\}`$
$``$ $`\{u_{i,h}:1in2,1h2n\}`$
$``$ $`\{u_{i,h}:n1in,1hB\}`$
$``$ $`\{v_j,a_j,b_j,c_j,y_j^1,y_j^2,y_j^3:1jm\}`$
$``$ $`\{v_0\}`$
$``$ $`\{p_{j,h}^k:1k3,1jm,1hBn\}`$
$``$ $`\{q_{i,h}:0i2n,1hn^3\}`$
$``$ $`\{d_i:0i5m+n6\}.`$
$`E`$ $`=`$ $`\{(v_I,v_{II}),(v_I,u_{1,1}),(v_{II},u_{0,1})\}`$
$``$ $`\{(u_{i,h},u_{i,h+1}):1in2,1h2n\}`$
$``$ $`\{(u_{i,h},u_{i,h+1}):n1in,1hB\}`$
$``$ $`\{(u_{i,2n},x_{i+2}),(u_{i,2n},\overline{x}_{i+2}):1in2\}`$
$``$ $`\{(x_i,u_{i,1}),(\overline{x}_i,u_{i,1}):1in\}`$
$``$ $`\{(u_{2i+1,h},u_{2i+2,h}):1in/21,1h2n\}`$
$``$ $`\{(u_{n1,h},u_{n,h}):1hB\}`$
$``$ $`\{(u_{n1,B},v_0)\}`$
$``$ $`\{(u_{n,B},a_j),(v_0,v_j),(a_j,b_j),(b_j,c_j):1jm\}`$
$``$ $`\{(y_j^1,y_j^2),(y_j^1,y_j^3),(y_j^2,y_j^3):1jm\}`$
$``$ $`\{(v_j,y_j^k),(c_j,y_j^k):1k3,1jm\}`$
$``$ $`\{(y_j^k,p_{j,1}^k):1k3,1jm\}`$
$``$ $`\{(p_{j,h}^k,p_{j,h+1}^k):1k3,1jm,1hBn\}`$
$``$ $`\{(p_{j,Bn}^k,x_i):\mathrm{iff}c_j\mathrm{contains}x_i\mathrm{as}\mathrm{literal}k,`$
$`1k3,1in,1jm\}`$
$``$ $`\{(p_{j,Bn}^k,\overline{x}_i):\mathrm{iff}c_j\mathrm{contains}\overline{x}_i\mathrm{as}\mathrm{literal}k,`$
$`1k3,1in,1jm\}`$
$``$ $`\{(x_i,q_{2i,1}),(\overline{x}_i,q_{2i1,1}),(x_i,d_0),(\overline{x}_i,d_0):1in\}`$
$``$ $`\{(q_{i,h},q_{i,h+1}):0i2n,1hn^31\}`$
$``$ $`\{(d_0,q_{0,1})\}`$
$``$ $`\{(q_{i,n^3},d_1):0i2n\}`$
$``$ $`\{(d_h,d_{h+1}):1h5m+n6\}.`$
We single out the subset of $`V`$ on which customers reside:

$`V_C`$ $`=`$ $`\{x_i,\overline{x}_i:1in\}`$
$``$ $`\{a_j,b_j,y_j^1,y_j^2,y_j^3:1jm\}`$
$``$ $`\{u_{i,h}:1in2,1h2n\}`$
$``$ $`\{u_{i,h}:n1in,1hB\}`$
$``$ $`\{d_i:0i5m+n6\}.`$
The initial vertices for player I and player II are $`v_I`$ and $`v_{II}`$, respectively. Note that $`|V|=2n+2+2n^2+2B+7m+1+3m(Bn)+2n^4+5m+n5=2n^4+3mn^2/2+3n^23mn+12m+3n4`$, $`|V_C|=2n+5m+2n^2+2B+5m+n5=3n^2+10m+3n5`$. The construction is clearly polynomial. An example with $`n=4`$ is depicted in Figure 1. (Note that this yields $`2n=8=n^2/2=B`$.) A clause gadget is shown in Figure 2. To avoid cluttering the figure, some of the edges connecting the diamonds (the subgraphs induced by $`(u_{i2,2n},x_i,\overline{x}_i,u_{i,1})`$) with other parts of the construction are only shown symbolically. Figure 3 shows the structure of the remaining part. The vertices $`p_{j,h}^k`$ induce a collection of feedback paths that connect the triangles $`(y_j^1,y_j^2,y_j^3)`$ in the gadget representing clause $`j`$ to the variable representations of the literals $`y_j^1`$, $`y_j^2`$, and $`y_j^3`$.

It will be useful to designate the subgraph of $`G`$ induced by $`q_{0,1},\mathrm{},q_{2n,n^3}`$, $`d_0,d_1,\mathrm{},d_{5m+n6}`$ as the cache part $`G_2=(V_2,E_2)`$ of $`G`$, and the subgraph of $`G`$ induced by $`VV_2`$ as the main part $`G_1=(V_1,E_1)`$.

Remarks.

* We have $`|V_CV_2|=5m+n6`$, $`|V_CV_1|=3n^2+5m+2n+1`$, and a player wins by collecting at least $`3n^2/2+5m+3n/22`$ customers.
* Moving from the main part to the cache part takes longer than visiting all vertices of the main part.
* In the proof we shall see that in every play on $`G`$, all the customers are captured. Only after capturing at least $`3n^2/2+n/2+4`$ customers in the main part can a player win by moving to the cache part. For by (a), $`(3n^2/2+n/2+4)+5m+n6=3n^2/2+5m+3n/22=|V_C/2|+1`$. Thus, a player who captured precisely $`3n^2/2+n/2+4`$ customers in the main part and then goes for the cache part before the opponent starts to do so wins by at least one customer.

Here is the “regular” play on $`G`$. We shall see later that “small” deviations are compatible with regular play, but “large” deviations lead to the defeat of the deviator.

The players move down their respective sides of the “ladders” formed by the $`u_{i,h}`$, and traverse the diamonds according to their chosen truth assignments in the given instance of Q3SAT, i.e., traversing $`x_i`$ if $`x_i=1`$, otherwise traversing $`\overline{x}_i`$. In this manner, player I gets to assign the “odd”, i.e. existentially quantified, variables, while II gets to assign the “even”, i.e., all-quantified, variables. After this stage, I makes the move $`(u_{n1,B},v_0)`$. Player II now selects a clause $`c_j`$ by moving from $`x_n`$ to $`a_j`$. This is matched by the move $`(v_0,v_j)`$ of I. While II traverses $`b_j,c_j`$, player I selects the literal within $`c_j`$ to which II should move. Player I enforces this by capturing the other two of the customers in the triangle $`T_j=(y_j^1,y_j^2,y_j^3)`$. Then II captures the remaining $`y_j^{k_3}`$. Following the feedback path incident to $`y_j^{k_2}`$, I takes $`Bn`$ moves to get to a suitable literal, say $`z_{i_2}`$, on one of the diamonds, and II takes the same number of moves from $`y_j^{k_3}`$ along its feedback path to a literal, say $`z_{i_3}`$, on a diamond.

At this stage each of the players has captured $`3n^2/2`$ customers along the ladders, and $`n/2`$ customers on the diamonds; I has also captured two customers on the triangle $`T_j`$, and possibly a customer on $`z_{i_2}`$. Thus I has captured $`3n^2/2+n/2`$ plus 2 or plus 3 customers. Player II has captured two customers on $`a_j,b_j`$ and one on $`T_j`$, possibly also one on $`z_{i_3}`$. Thus II has now captured $`3n^2+n/2`$ plus 3 or plus 4 customers.

Suppose first that II can win in the given instance of Q3SAT. This means that for any truth assignment of the variables of player I, player II can assign truth values so that at least one clause $`c_j`$ is false, i.e, all the literals in $`c_j`$ have value 0. In terms of regular play, this means that II captured a customer on $`z_{i_3}`$. Thus II captured $`3n^2/2+n/2`$ plus 4 customers, at least one more than player I. At this point I moves next. If I chooses to move straight to the cache part, player I will capture a total of at most $`3n^2/2+n/2+3+5m+n6=3n^2/2+5m+3n/23<|V_C|/2`$. By restricting himself to the main part, II can capture all the rest, namely $`3n^2/2+5m+3n/22`$, so II wins by precisely one customer. Therefore player I will make some other move, e.g., the move $`(z_{i_2},d_0)`$. Then II responds by moving to the cache part. By Remark (c), II thus wins in the constructed instance of CSP$`(1,1)`$ by precisely one customer.

Secondly, suppose that player I can win in the given instance of Q3SAT. This implies that player I can assign truth values such that for any truth assignment of II, every clause contains at least one true literal. In terms of regular play on the constructed instance of CSP$`(1,1)`$, this means that player I can arrange that $`z_{i_3}`$ will already have been captured during the initial diamond traversal, so II will have captured only $`3n^2/2+n/2+3`$ customers up to and including the feedback edge traversal. We consider two cases.

* The clause $`c_j`$ selected by II contains a false literal, say $`z_i_{\mathrm{}}`$. Then I continues according to regular play, playing in the triangle $`T_j`$ such that II is “forced” to move to $`z_{i_k}`$, and I himself moves to $`z_i_{\mathrm{}}`$. Then player I will have captured $`3n^2/2+n/2+3`$ customers, the same as II. It is now the turn of I. As above it is seen that if I moves immediately to the cache part, he loses by one customer. A better move for I is $`(z_i_{\mathrm{}},d_0)`$. Now II cannot afford to let I take the cache, so II has to move $`(z_{i_k},q_{i_k,1})`$. This allows I to take a remaining customer on a literal vertex, maintaining a distance of $`n^3`$ to the cache. II still has to guard the cache by limiting his distance from $`d_1`$ to at most $`n^31`$, and is thus forced to move $`(q_{i_k,1},q_{i_k,2})`$. Eventually, I picks up all remaining literal customers by going via $`d_0`$. In a similar manner, I can collect all remaining customers in the main part: First I picks up all remaining customers at vertices $`y_j^k`$, which have distance $`n^3+Bn`$ from the cache. This is possible without exceeding this distance; at the same time, II cannot afford to move to the same distance from the cache, as this would leave the cache unguarded. Next, I can move on to collecting the vertices $`b_j`$ (which have distance $`n^3+Bn+2`$ from the cache) one by one, and finally collect the vertices $`a_j`$, which have distance $`n^3+Bn+3`$. At this point, I has won the game.
* The clause $`c_j`$ selected by II contains no false literal. Then I deviates slightly from regular play, by moving to a clause, say $`c_{\mathrm{}}`$, which does contain a false literal $`z_{i_f}`$. Such a clause exists by assumption (3) above. After I captures two customers in $`T_{\mathrm{}}`$, I moves to $`z_{i_f}`$, having thus far captured $`(3n^2/2+n/2)+3`$ customers. Then player I continues as in the case (i), winning. Note that the 3 paths leading out from $`c_j`$ to the diamonds all end in literals whose customers have already been captured, and that I wins independently of whether II captures one, two or three customers in $`T_j`$.

We have shown that if the players stick to regular play, then player I can win in Q3SAT if and only if player I can win in CSP$`(1,1)`$. It remains to check nonregular play.

First of all, not proceeding down a ladder (say, to collect a customer at $`d_0`$ or at an additional literal vertex) takes at least two moves per additional customer. This lets the other player change over to the deviator’s side of the ladder, continue in a zig-zagging fashion back and forth between both sides of and down the ladder, and thus continue to collect one customer per move. Therefore, the violator loses in the balance, compared to regular play. Furthermore, remark (c) above implies that if either player goes for the cache part at any point during the diamond traversal before having traversed a feedback edge, then that player loses, since a minimum of $`3n^2/2+n/2+4`$ captures have to be made by a winning player in the main part prior collecting the cache.

If II loses in CSP$`(1,1)`$, II can possibly use a feedback edge leading back to a literal $`z_i_{\mathrm{}}`$ whose customer has not been captured during the diamond traversal, by using a vertex of $`T_j`$ whose customer was already captured by I. But then the balance of customers captured by II up to the capture at $`z_i_{\mathrm{}}`$ is unchanged, and I still wins.

Conversely, if II wins in CSP$`(1,1)`$, player I might traverse a feedback edge after having captured only one customer on a triangle $`T_j^{}`$ (possibly $`j^{}j`$), hoping to capture enough customers during a second traversal of the diamonds, before II will have captured enough. An easy accounting argument, left to the reader, shows that player I cannot muster a sufficient supply of customers with this maneuver. $`\mathrm{}`$

It is not hard to see that the above construction can be modified to establish a proof of the PSPACE-completeness of the CSP on bipartite directed graphs without antiparallel edges. Furthermore, it can be modified to cover the scenario in which both players move simultaeneously: after scaling edge lengths by a factor of two, give Player I a headstart of one move.

## 4 Identical Starting Point

The result in the previous section shows that deciding the outcome of a CSP instance is quite difficult, even when both players start very close to each other, and the graph is bipartite. In this section, we concentrate on the natural special case in which both players start from the same vertex. As it turns out, this scenario is quite different.

###### Theorem 4.1

For the CSP on bipartite graphs with both players starting at the same point, player I can avoid a loss.

Proof: By way of contradiction, suppose player II has a winning strategy, and both players start from vertex $`v_0`$. Now suppose I moves to vertex $`v_1^I`$, and II can counter this move by $`v_1^{II}`$. In the following, let I visit any sequence of vertices $`v_1^I,v_2^I,v_3^I,\mathrm{}`$ By assumption, II has a winning strategy, so there is a sequence of moves $`v_1^{II},v_2^{II},v_3^{II},\mathrm{}`$ that ends with II capturing an absolute majority of customers. Note that each $`v_i^{II}`$ is determined by the sequence $`v_1^I,v_2^I,v_3^I,\mathrm{},v_i^I`$; by induction, we can write $`v_i^{II}(v_i^I)`$ to indicate that I’s move to $`v_i^I`$ was successfully countered by II by moving to $`v_i^{II}`$.

Now consider, for any sequence $`u_1^{II},u_2^{II},u_3^{II},\mathrm{}`$ of moves by II, the following sequence of moves for I:

$$v_1^I,v_0,v_1^{II}(u_1^{II}),v_2^{II}(u_2^{II}),v_3^{II}(u_3^{II}),\mathrm{}$$

This means that player I gives up two moves by moving to any neighbor $`v_1^I`$ and back to $`v_0`$, thereby giving player II a head start of 1 1/2 moves. Then I plays against a “phantom player” II’ that is one move lagging behind the real player II, i.e., precisely 1/2 move ahead of I, which allows I to “steal” the assumed second player’s strategy against such a player.

By assumption, the above is a well-defined sequence of moves for I. Therefore, player I wins more than half of the customers against II’, but II wins more than half of the customers against I. Hence, there must be a customer (say, at vertex $`v_{}`$) that I reaches before II’, but that II reaches before I. Therefore, I must be moving to vertex $`v_{}`$ when II is already there, and just before II’ gets there.

This is a contradiction to the bipartiteness of $`G`$: After a move of I, both players must always occupy vertices of opposite color, so $`I`$ cannot reach $`v_{}`$ with II positioned on that vertex.

Therefore, II cannot have a winning strategy, proving the claim. $`\mathrm{}`$

Note that the theorem remains valid for directed graphs, if there is a single pair of anti-parallel edges that allows I to leave and return to $`v_0`$ in just two moves.

The following example (courtesy of David Wood) shows that the possibility of moving back to $`v_0`$ is crucial for the proof: In the absence of an undirected edge at $`v_0`$, player I may be limited to winning a single customer.

###### Theorem 4.2

There is a family of instances of CSP on directed graphs in which I cannot win more than 1 out of $`n`$ customers.

Proof: Consider the graph shown in Figure 4. The initial vertex for both players is denoted by $`v_0`$, the vertex set $`V_C`$ is indicated by the circled vertices.

Suppose I starts by moving to vertex $`v_i`$; then II responds by moving to vertex $`v_{i+2}`$. Now the rest of the game is determined, and I only wins the customer at $`v_i`$. $`\mathrm{}`$

For non-bipartite graphs, I may lose, even on undirected graphs, provided passing is not allowed.

###### Theorem 4.3

There are instances where I cannot avoid a loss, even if both players start from the same vertex.

Proof: Consider the graph shown in Figure 5. The initial vertex for both players is denoted by $`v_0`$, the vertex set $`V_C`$ is indicated by the three circled vertices.

Player I is in a zugzwang situation: Suppose I starts by moving to vertex $`v_1`$; then II moves to vertex $`v_2`$. If then I moves back to $`v_0`$, II moves on to $`v_4`$; it is straightforward to check that now II will force a win by taking the customer at $`v_6`$ and at least one of $`v_3`$ and $`v_8`$. Hence we can assume that I’s second move is to $`v_3`$. However, this is answered by II by moving to $`v_4`$, and I cannot prevent II from taking both $`v_6`$ and $`v_8`$.

Therefore consider the case where I starts by moving to $`v_2`$; II responds by moving to $`v_1`$. As in the previous case, II wins by moving to $`v_3`$ if I moves back to $`v_0`$. Hence we can assume that I’s second move is to $`v_4`$, followed by II moving to $`v_3`$, securing the first customer. Regardless of I’s next move, II can again force a win by taking at least one of the remaining two customers.

This concludes the proof. $`\mathrm{}`$

An immediate consequence is the following:

###### Theorem 4.4

There are instances where optimal play from both I and II forces a draw, even if both players start from the same vertex.

Proof: Consider the graph shown in Figure 6. The initial vertex for both players is denoted by $`v_0`$, the vertex set $`V_C`$ is indicated by the three circled vertices.

Suppose player $`X`$ is the first to move to one of the vertices in $`\overline{V}=\{v_1,v_2\}`$, while the other player $`Y`$ has not left the vertex set $`\{v_0,v_0^{}\}`$. Then the analysis of Theorem 4.3 shows that player $`Y`$ can force a win by moving to the other vertex in $`\overline{V}`$.

Therefore, neither of the players is willing to leave the set $`\{v_0,v_0^{}\}`$, resulting in a draw. $`\mathrm{}`$

## 5 Trees

Our proof of Theorem 4.1 is purely existential. Furthermore, there is still no proof that player I cannot just avoid a loss, but also avoid a draw, and end the game with a win or a tie.

###### Conjecture 5.1

For the CSP on trees, one of the players can force a win or a tie.

In particular, this implies that for the case of identical starting point and an odd number of customers, player I always wins the game.

We have a pretty good idea how to tackle this problem; a constructive argument may use bookkeeping on subsets of customers, and the number of moves necessary to collect them and return to a previous position. (This means generalizing the idea of playing against a phantom player, and arguing that on trees it can only be an advantage to have extra moves to spare.) We hope to finish this argument at a later time. But even if this works out, the resulting construction is exponential in size and rather awkward. It would be a lot more satisfying to have a simple strategy that guarantees a win for player I.

However, there are a number of difficulties that are indicated by the following observations.

###### Theorem 5.2

There are instances of CSP on trees, with both players starting from the same vertex $`v_0`$, the number of customers being $`2k+1`$, and the only way for player I to win allows II to potentially collect $`k`$ customers before I reaches even a single customer.

Proof: Consider the graph shown in Figure 7. It has $`k`$ customers at an intermediate distance from the starting vertex $`v_0`$, and at twice that distance from each other. Furthermore, there is a cluster of $`k+1`$ customers at a large distance from $`v_0`$, but at a small distance from each other.

If I starts by taking one of the nearer customers, II collects all the distant customers and wins. On the other hand, II may take all the near customers before I takes one of the distant ones. $`\mathrm{}`$

###### Theorem 5.3

Consider instances of CSP on trees, where both players start on the same vertex $`v_0`$. In general, player I cannot avoid a loss by adapting an a-priori strategy, i. e., by prioritizing the customers in an appropriate way, and always trying to collect the customer with the highest priority.

Proof: Consider the graph shown in Figure 8. It consists of a symmetric tree with nine customers at the leaves, grouped into three triples.

Without loss of generality, assume that $`v_1`$ is the first customer on I’s list; furthermore, assume that $`v_4`$ is the first customer on the list that is none of $`v_1`$, $`v_2`$, $`v_3`$. Then it is straightforward to check that II can collect the customers $`v_5`$, $`v_6`$, $`v_7`$, $`v_8`$, $`v_9`$ without any interference from I, thus winning the game: In order to win, I would be forced to visit customers from all three different clusters, which takes longer than II needs to collect all five customers. $`\mathrm{}`$

Finally, player II can limit his losses in a natural special case. A rather involved argument for the following can be found in the fourth author’s thesis. We omit this proof, as we believe that there should be a relatively simple argument; in particular, a proof of Conjecture 5.1 as described should do the trick.

###### Theorem 5.4

Consider an instance of the CSP where the graph $`G`$ is a tree $`T`$ and both players start at the same vertex $`v_0`$. Suppose all customers are positioned at leaves of the tree. Then player II can avoid a loss by more than one customer. In particular, II can avoid a loss when the number of customers is even.

## 6 Stars

It may be easier to come up with a strategy for the class of CSP instances in which the graph $`G`$ is a star, i.e., a tree $`T`$ with at most one vertex of degree higher than two. Again, we consider both players starting from the same vertex. If customers are only contained in leaves, it is not hard to see that there is a simple optimal strategy for both players, by always choosing the nearest free customer when returning to the central node.

However, it is straightforward to see that the example in Figure 9 cannot be won using this approach: If I collects all five customers along the longest ray, II gets all customers along the other two rays. Similarly, it follows that I loses when trying to pick up all the customers along a single ray. We leave it to the reader as an exercise to work out a winning strategy for this instance.

## 7 Conclusions

In this paper we have introduced the Competing Salesman Problem. Many open problems remain. Besides the ones mentioned directly or indirectly throughout the paper, there are many more. One of the more interesting scenarios may be a continuous geometric version, in which customers are points in some space of fixed dimension, and the players move continuously or in discrete portions along arbitrary paths. Clearly, this introduces additional difficulties.

As there are innumerable variants of the TSP, due to many different practical constraints, requirements, or objective functions, it is quite conceivable that there are many more related games. One such variant (called the freeze tag problem, FTP) has been considered in , where a set of cooperating players have to awake each other, and any awake player can awake a sleeping player by moving next to him. In the original game of freeze tag, there are two competing teams, and one wins if it can freeze all opposing players, while the second one tries to avoid this permanently.

## Acknowledgments

Some of this work was stimulated and motivated by the Dagstuhl Seminar on Algorithmic Combinatorial Game Theory, 17–22 February, 2002, organized by Erik Demaine, Rudolf Fleischer, Aviezri Fraenkel, and Richard Nowakowski. We thank all participants for contributing to the fruitful atmosphere of this workshop, in particular David Wood for pointing out the example in Theorem 4.2.

Earlier parts of this work originated from work on the fourth author’s diploma thesis ; other parts of this paper were written during a stay at the Department of Computer Science and Software Engineering, University of Newcastle, NSW, Australia, where Sándor Fekete was supported by a Visiting Researcher Grant. Rudolf Fleischer’s work described in this paper was partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. HKUST6010/01E).