Dedicated to the memory of Uffe V. Haagerup

#  C*-dynamical rapid decay

Erik Christensen  Erik Christensen, Mathematics Institute, University of
Copenhagen, Copenhagen, Demark<EMAIL_ADDRESS>
###### Abstract.

Some well known results by Haagerup, Jolissaint and de la Harpe may be
extended to the setting of a reduced crossed product of a C*-algebra
${\mathcal{A}}$ by a discrete group $G.$ We show that for many discrete
groups, which include Gromov’s hyperbolic groups and finitely generated
discrete groups of polynomial growth, an inequality of the form

$\|X\|\leq C\sqrt{\sum_{g\in G}(1+|g|)^{4}\|X_{g}\|^{2}}$

holds for any finitely supported operator $X$ in the reduced crossed product.

###### Key words and phrases:

Haagerup, C*-algebra, discrete group, crossed product, rapid decay

###### 2010 Mathematics Subject Classification:

Primary: 46L55, 37A55. Secondary: 22D55, 46L07.

##  1\. Introduction

Any result in classical harmonic analysis naturally raises the question, does
this extend to a non commutative setting ? In the situation of a discrete
dynamical system, you may work with the group of integers ${\mathbb{Z}}$ which
acts on a compact space as the group of homeomorphisms generated by a single
homeomorphism. By Gelfand’s fundamental theorem we know that the set of
compact topological spaces correspond to unital commutative C*-algebras, and
then the classical discrete dynamical system as described above can be made
non commutative in 2 ways, either by studying a general non commutative
C*-algebra equipped with a single *-automorphism or by investigating
properties of an action of a general discrete group of homeomorphisms on a
compact space. The construction named reduced crossed product  of a C*-algebra
by a discrete group encodes a set up for the study of the action of a general
discrete group on a C*-algebra.

Here we will extend results, by Haagerup from [8] on free non abelian groups
${\mathbb{F}}_{d},$ by Jolissaint [11] on the concept named rapid decay and by
de la Harpe [10] on hyperbolic groups, from the setting of a reduced group
C*-algebra  to the setting of a reduced crossed product C*-algebra.  The
C*-algebra ${\mathcal{A}}$ upon which the discrete group $G$ acts by
*-automorphisms $\alpha_{g}$ may be abelian or non abelian, and the case where
the algebra is the trivial ${\mathcal{A}}={\mathbb{C}}I$ is the reduced group
C*-algebra case.

Uffe Haagerup’s article [8] has been very influential in the study of discrete
groups and von Neumann algebras of type II${}_{1},$ and his name and results
are linked to many fundamental mathematical properties such as the Haagerup
approximation property  [3], [9], the completely bounded approximation
property  [5] and the Haagerup tensor product  [16]. We will not go into the
study of any of these aspects but concentrate on an extension of the first
basic result from [8] and lift it from the reduced group case to the reduced
crossed product case for discrete hyperbolic groups acting on general
C*-algebras. In this setting we prove that there exists an $C>0,$ depending on
the group only, such that for any linear combination $X=\sum L_{g}X_{g}$ in
the algebraic reduced crossed product we have the following inequality

(1.1) $\|X\|\leq C\sqrt{\sum_{g\in G}(1+|g|)^{4}\|X_{g}\|^{2}}\,$

which is a direct generalization of Haagerup’s estimate in the group algebra
case, since for these groups $C<2.$ In the article [11] Jolissaint showed
that, in the group algebra case, inequalities like (1.1) may be obtained for
many other discrete groups, which are not free, and he introduced the property
named rapid decay  for a discrete group $G$ with a length function $|g|,$ if
there exist positive constants $C,r$ such that for any $x=\sum
x_{g}\lambda_{g}$ in ${\mathbb{C}}[G]$

(1.2) $\|x\|_{op}\leq C\sqrt{\sum(1+|g|)^{2r}|x_{g}|^{2}}.$

Shortly after Jolissaint had obtained his results they were extended to the
setting of hyperbolic groups by de la Harpe [10], and it turns out that it is
possible to extend both Jolissaint’s and de la Harpe’s results to the crossed
product setting. The basic insight which makes this possible was formulated by
Jollisaint in his lemmas 3.2.2 and 3.2.3. Then de la Harpe proved that these
lemmas are true in the setting of discrete finitely generated hyperbolic
groups, so Jolissaint’s findings could be extended. Here we have collected the
statements from Jolissaint’s basic lemmas into a property (J) which a discrete
group with a length function may have, and then we prove that the inequality
(1.1) holds, in any reduced crossed product of a C*-algebra and a group
satisfying property (J). It seems possible to us that property (J) implies
hyperbolicity, but we have very little experience in dealing with such a
question.

We have also considered reduced crossed products of C*-algebras by discrete
finitely generated groups which have polynomial growth. In this case it is
possible to get the following - much better - result. If a discrete finitely
generated group has polynomial growth then there exist $C>0,$ $s>0$ such that
for any finitely supported operator $X=\sum L_{g}X_{g}$ in a reduced crossed
product $C^{*}_{r}({\mathcal{A}}\rtimes_{\alpha}G)$ we have

(1.3) $\displaystyle\|X\|\leq C$ $\displaystyle\|\sum_{g\in
G}(1+|g|)^{2s}L_{g}X_{g}X_{g}^{*}L_{g}^{*}\|^{\frac{1}{2}}$
$\displaystyle\|X\|\leq C$ $\displaystyle\|\sum_{g\in
G}(1+|g|)^{2s}X_{g}^{*}X_{g}\|^{\frac{1}{2}}$

The advantage of (1.3) over (1.2) is that usually

$\|\sum_{g\in C_{k}}X_{g}^{*}X_{g}\|^{\frac{1}{2}}<\big{(}\sum_{g\in
C_{k}}\|X_{g}^{*}X_{g}\|\big{)}^{\frac{1}{2}}.$

##  2\.  Notation and norms

Most of the content of this section is well known in the setting of a reduced
group C*-algebra, but here we deal with a reduced crossed product C*-algebra.
In order to be able to generalize the methods from Haagerup’s paper [8], we
need a characterization of the operator norm in a reduced crossed product of a
C*-algebra by a discrete group, and this result, which we think might be known
but unpublished, is presented in Proposition 2.4 in a self contained frame. We
start with a well known operator theoretical version of Cauchy-Schwarz’
inequality, [16].

######  Definition 2.1.

Let $H,\,K$ be Hilbert spaces, $J$ be an index set and $(a_{\iota})_{(\iota\in
J)}$ a family of bounded operators in $B(H,K).$

  * (i)

If the sum $\sum_{\iota}a_{\iota}^{*}a_{\iota}$ is ultrastrongly convergent in
$B(H)$ we say that the family $(a_{\iota})$ is column bounded with column norm
$\|(a_{\iota})\|_{c}:=\|\sum a_{\iota}^{*}a_{\iota}\|^{\frac{1}{2}}.$

  * (ii)

If the sum $\sum_{\iota}a_{\iota}a_{\iota}^{*}$ is ultrastrongly convergent in
$B(K)$ we say that the family $(a_{\iota})$ is row bounded with row norm
$\|(a_{\iota})\|_{r}:=\|\sum a_{\iota}a_{\iota}^{*}\|^{\frac{1}{2}}.$

######  Proposition 2.2.

Let $H,\,K$ be Hilbert spaces, $J$ be an index set and $(a_{\iota})_{(\iota\in
J)},$ $(b_{\iota})_{(\iota\in J)}$ be column bounded families of operators in
$B(H,K).$

  * (i)

The sum $\sum_{\iota}a_{\iota}^{*}b_{\iota}$ is ultrastrongly convergent in
$B(H)$ and the operator norm of the sum satisfies
$\|\sum_{\iota}a_{\iota}^{*}b_{\iota}\|\leq\|(a_{\iota})\|_{c}\|(b_{\iota})\|_{c}.$

  * (ii)

There exists a column bounded family $(e_{\iota})_{(\iota\in J)}$ of column
norm at most $1$ such that for the positive bounded operator $h$ on $H$
defined by $h:=(\sum_{\iota}a_{\iota}^{*}a_{\iota})^{\frac{1}{2}}$ we have for
each $\iota\in J,\,a_{\iota}=e_{\iota}h$ and the sum
$\sum_{\iota}e_{\iota}^{*}e_{\iota}$ equals the range projection of $h.$

  * (iii)

Let $k:=(\sum_{\iota}b_{\iota}^{*}b_{\iota})^{\frac{1}{2}},$ then there exists
a contraction $c$ in $B(H)$ such that
$\sum_{\iota}b_{\iota}^{*}a_{\iota}=kch.$

###### Proof.

The families $(a_{\iota})$ and $(b_{\iota})$ represent bounded column
operators in the operator space $M_{(J,1)}\big{(}B(H,K)\big{)}$ and the
statement (i) follows from properties of the operator product.

The statement (ii) follows from the polar decomposition applied to the column
operator $(a_{\iota}).$

The result in statement (ii) may be applied to the column operator
$(b_{\iota})$ such that each $b_{\iota}=f_{\iota}k,$ we can then define a
contraction $c$ in $B(H)$ by $c:=\sum_{\iota}f_{\iota}^{*}e_{\iota}$ and
statement (iii) follows. ∎

The rest of this article takes place in the setting of the reduced crossed
product of a C*-algebra ${\mathcal{A}}$ by a discrete group $G,$ which acts on
${\mathcal{A}}$ by the *-automorphisms $\alpha_{g}.$ We made a study of the
properties of this crossed product in the article [4] and we will use most of
the notation and several of the results of that article below. A basic point
of view in Section 2 of [4] is that there are many facts related to properties
of the coefficients of a Fourier series which generalize to properties of the
coefficients of an element in a reduced discrete C*-crossed product.

We recall that any element $X$ in
${\mathcal{C}}:=C^{*}_{r}({\mathcal{A}}\rtimes_{\alpha}G)$ has a Fourier
series expansion $X\sim\sum_{g\in G}L_{g}X_{g},$ where the sum is convergent
in the norm $\|.\|_{\pi}$ described in Proposition 2.2 of [4]. A simple
computation shows that for $X\sim\sum L_{g}X_{g}$ we have that the column and
row norms of the family $(L_{g}X_{g})_{(g\in G)}$ may be computed as

(2.1) $\displaystyle\|(L_{g}X_{g})_{(g\in G)}\|_{c}^{2}$
$\displaystyle=\|\pi(X^{*}X)\|=\|(X^{*}X)_{e}\|$
$\displaystyle\|(L_{g}X_{g})_{(g\in G)}\|_{r}^{2}$
$\displaystyle=\|\pi(XX^{*})\|=\|(XX^{*})_{e}\|.$

In particular we notice the following proposition.

######  Proposition 2.3.

Let $X\sim\sum_{g}L_{g}X_{g}$ be an element in ${\mathcal{C}}$ then the sum
converges in the column norm.

We will use the $\pi-$norm or column norm to estimate the operator norm in the
computations to come, so we need the following proposition. It may be known to
several people, but may be in a slightly different setting. We are not aware
of an explicit formulation as the one we present, but the results of [17] have
a similar flavour. We do also think that people who prefer to look at
completely positive mappings as correspondences or operator bimodules may know
the result, but still we are missing a reference.

######  Proposition 2.4.

Let ${\mathcal{B}}$ be a C*-algebra, $H$ a Hilbert space and
$\pi:{\mathcal{B}}\to B(H)$ a completely positive and faithful mapping then

$\forall
b\in{\mathcal{B}}:\|b\|=\sqrt{\sup\\{\|\pi(x^{*}b^{*}bx)\|\,:\,\|\pi(x^{*}x)\|\leq
1\\}}.$

###### Proof.

We may suppose that ${\mathcal{B}}$ is a subalgebra of $B(K)$ for some Hilbert
space $K,$ then since $\pi$ is completely positive and faithful there exists
by Stinespring’s result [18] a faithful representation $\rho$ of
${\mathcal{B}}$ on $H$ and a bounded operator $C$ in $B(K,H)$ such that

$\forall b\in{\mathcal{B}}:\quad\pi(b)=C^{*}\rho(b)C.$

We may define a semi norm, say $n,$ on ${\mathcal{B}}$ by

(2.2) $\forall b\in{\mathcal{B}}:\quad
n(b):=\sup\\{\|\rho(bx)C\|:\|\rho(x)C\|\leq 1\\}.$

Since $\|C^{*}\rho(y^{*}y)C\|=\|\rho(y)C\|^{2}$ for any $y$ in ${\mathcal{B}}$
and $\pi$ is faithful we get that $n$ is a norm and that

$\forall
b\in{\mathcal{B}}:n(b)=\sqrt{\sup\\{\|\pi(x^{*}b^{*}bx)\|\,:\,\|\pi(x^{*}x)\|\leq
1\\}}.$

On the other hand the definition (2.2) implies that for $b,d$ in
${\mathcal{B}}$ we have $n(bd)\leq n(b)n(d)$ so $n$ is an algebra norm and
$n(b)\leq\|b\|.$ For any pair $b,x$ in ${\mathcal{B}}$ with
$\|\rho(x)C\|^{2}=\|\pi(x^{*}x)\|\leq 1$ we have

$\displaystyle n(b^{*}b)$
$\displaystyle\geq\|\rho(b^{*}bx)C\|\geq\|C^{*}\rho(x^{*}b^{*}bx)C\|=\|\rho(bx)C\|^{2},\text{
so }$ $\displaystyle n(b^{*})n(b)$ $\displaystyle\geq n(b^{*}b)\geq n(b)^{2}.$

From here it follows that $n(b)=n(b^{*})$ and then $n(b^{*}b)=n(b)^{2},$ and
the completion say $\hat{\mathcal{B}}$ of ${\mathcal{B}}$ with respect to the
C*-norm $n$ becomes a C*-algebra such that the inclusion of ${\mathcal{B}}$ in
$\hat{\mathcal{B}}$ is a contractive faithful *-homomorphism and hence an
isometry. The proposition follows. ∎

In Haagerup’s and Jolissaint’s articles, [8], [11] they use the symbol $*$ to
denote the operator product in a group algebra, since this is really a
convolution product. In our article on crossed product C*-algebras [4] the
operator product is an invisible dot and the $*$ is used to denote the
Hadamard product, which in the notation from above takes the form

$\big{(}\sum_{g}L_{g}X_{g}\big{)}*\big{(}\sum_{h}L_{h}Y_{h}\big{)}:=\sum_{f}L_{f}X_{f}Y_{f}.$

We will use this convention here, too.

##  3\.  The property (J)

The basic ideas in the arguments to come are taken from Haagerup’s article,
and in the setting of a non commutative free group it is clear that for two
group elements $x,y$ with reduced words $x=x_{1}\dots x_{k}$ and $y=y_{1}\dots
y_{l}$ the number of cancellations, say $p,$ needed to spell to $xy$ gives the
spelling of $xy$ directly as $xy=x_{1}\dots x_{(k-p)}y_{(p+1)}\dots y_{l}.$ In
Jolissaint’s article he uses this observation in a very clever original way,
and he shows that this idea may be generalized to work up to a controllable
error  in some groups of isometries on a Riemannian manifold with bounded
strictly negative sectional curvature. Then de la Harpe showed that
Jolissaint’s method of dealing with cancellations works in any finitely
generated discrete group which is hyperbolic, as defined by Gromov, [7] and
[6]. Here we will instead take these results as the basis for the definition
of a property we have named (J).

We will now define the setting in which we will use Haagerup’s, Jolissaint’s
and de la Harpe’s ideas. We define the cancellation number in a general group
with a length function as follows.

######  Definition 3.1.

Let $G$ be a group with a length function $g\to|g|.$ For $g,h$ in $G$ the
cancellation number $c(g,h)$ of the pair is defined as the non negative
integer $p(g,h)$ which satisfies

$2p(g,h)\leq|g|+|h|-|gh|<2p(g,h)+2.$

It follows from the properties of a length function that $0\leq
p(g,h)\leq\min\\{|g|,|h|\\},$ and the cancellation number divides the
cartesian product $G\times G$ into a sequence of disjoint subsets
$(P_{p})_{(p\in{\mathbb{N}}_{0})}$ defined by $P_{p}:=\\{(g,h)\in G\times
G\,:\,p(g,h)=p.\\}.$

Following Jolissaint we define certain subsets of a group $G$ with a length
function $|g|$ as follows

######  Definition 3.2.

  *   * (i)

$\forall r\geq 0:\quad\quad\quad\quad\,\,\,\,\,B_{r}:=\\{g\in G\,:\,|g|\leq
r\\},$

  * (ii)

$\forall k\geq 0:\,\quad\quad\quad\,\,\,\,\quad C_{k}:=\\{g\in
G\,:\,k-1<|g|\leq k\\},$

  * (iii)

$\forall k\geq 0\,\forall\alpha\geq 0:\quad C_{k,\alpha}:=\\{g\in
G\,:\,k-\alpha\leq|g|\leq k+\alpha\\},$

We can now collect the sufficient conditions, we have have dragged out of
[11], into a property we name (J). We will not focus on which groups that may
satisfy the property (J), but we think that the survey article on rapid decay
[2] by Chatterji will show that many groups do have property (J). On the other
hand we will sketch arguments which show that Jolissaint’s and de la Harpe’s
examples do have property (J). It is easy to see that free non abelian groups
do have property (J) with the extra very nice properties that the constants of
the definition satisfy $\alpha=\beta=\gamma=0$ and $N=1.$

######  Definition 3.3.

Let $G$ be a discrete group with a length function $g\to|g|.$ The pair
$(G,|\cdot|)$ has property, (J) if

(3.1) $\displaystyle\exists\alpha>0,\beta>0,\gamma>0,:$ $\displaystyle(i)\,$
$\displaystyle\forall g\in G,\forall 0\leq s<|g|+1,\,\exists u_{(g,s)}\in
C_{s,\alpha}$ $\displaystyle(ii)\,$ $\displaystyle
v_{(g,s)}:=u_{(g,s)}^{-1}g\in C_{(|g|+1-s),\beta}$ $\displaystyle(iii)\,$
$\displaystyle\forall p\in{\mathbb{N}}_{0},\forall(a,b)\in
P_{p}\,\exists\,c(a,b)\in C_{p,\gamma}\text{ s. t. }$ $\displaystyle
a=u_{(ab,(|a|-p))}c(a,b),\,b=c(a,b)^{-1}v_{(ab,(|a|-p))}.$ (3.2)
$\displaystyle\forall\mu>0,\nu>0\,\exists N\in{\mathbb{N}}:$
$\displaystyle\forall b\in G\forall\,0\leq p\leq|b|\,:\,\,|\\{(c,v)\in
C_{p,\mu}\times C_{(|b|-p),\nu}:c^{-1}v=b\\}|\leq N.$

######  Remark 3.4.

It is important for the following proofs in the next section to notice that
the group element $u_{(g,s)}$ is determined uniquely by $g$ and $s,$ and then
$v_{(g,s)}=u_{(g,s)}^{-1}g$ is also determined by $g$ and $s$ only.

The interesting thing about the factors $c(a,b)$ is that they always
approximately satisfy $|c(a,b)|=p.$

In Jolissaint’s proof the group element $u_{(g,s)}$ is chosen geometrically,
as we sketch now. On the geodesic which connects a point $m$ in the manifold
with its image $g(m),$ one chooses the point $n_{s}$ which has the distance
$s$ to $g(m).$ Then $u_{(g,s)}$ is chosen such that the distance between
$n_{s}$ and $u_{(g,s)}^{-1}\big{(}g(m)\big{)}$ is minimal among the distances
between $n_{s}$ and the set $\\{u(m)\,:\,u\in G\\}.$ We will not continue to
quote Jolissaints proof, but show that a group $G,$ which is hyperbolic with
respect to a given word length, has the property (J). The proof follows that
of de la Harpe [10], but in order to explicitly establish the property (J)
from the definition above, we repeat part of it here. We will use the
following notation. For a real number $s,$ the expression $\lfloor s\rfloor$
means the largest integer dominated by $s.$

######  Lemma 3.5.

Let $G$ be a finitely generated discrete group which is hyperbolic with
respect to word length. Then $G$ has the property (J).

###### Proof.

For a group element $g$ written in reduced form as $g=g_{1}\dots g_{|g|}$ and
a real $s,\,0\leq s<|g|+1$ we define

$u_{(g,s)}:=\begin{cases}e\quad\quad\quad\,\,\,\text{ if }0\leq s<1\\\
g_{1}\dots g_{\lfloor s\rfloor}\text{ if }1\leq s<|g|+1,\end{cases}$

and we find that $u_{(g,s)}\in C_{s,1}$ so $\alpha=1$ may be used. Similarly
we find

$v_{(g,s)}=\begin{cases}g_{(\lfloor s\rfloor+1)}\dots g_{|g|}\text{ if
}\,\,0\leq s<|g|\\\ e\quad\quad\quad\,\,\quad\quad\text{ if }|g|\leq
s<g+1,\end{cases}$

and we get $v_{(g,s)}\in C_{(|g|+1-s),1},$ so $\beta=1$ is possible.

Given a non negative integer $p$ and a pair of group elements $(a,b)\in P_{p}$
with $ab=g,$ then for $k:=|a|,$ $l:=|b|$ there exists $c\in\\{0,1\\}$ such
that $|g|=k+l-2p-c.$ Then for $u_{(g,k-p)}$ we may apply the lemma at the
bottom of page 771 in [10], to see that there exists an $M\geq 0,$ independent
of $k,l,p,c$ such that for $c(a,b):=u_{(g,k-p)}^{-1}a$ the following
inequalities hold

(3.3) $p\leq|c(a,b)|\leq p+M,$

so $c(a,b)\in C_{p,M}.$

In order to establish the property (3.2) we remark, that in our case we have
$v_{(g,(k-p))}\in C_{(|g|+1-k+p),1}=C_{(l-p-c+1),1},$ which means

$c(a,b)\in C_{p,M},\,\,v_{g,(k-p)}\in C_{(|b|-p),2}\text{ and
}c(a,b)v_{(g,(k-p))}=b.$

The result then follows from item (ii) in the lemma of [10].

∎

##  4\. Rapid decay

The most basic example of the phenomenon named rapid decay  by Paul Jolissaint
in [11] is presented quite early in many courses on Fourier series. The
example tells, that if $f(t)$ is a differentiable complex
$2\pi-$periodic function on ${\mathbb{R}},$ then its Fourier series is
uniformly convergent. This is proven via the following argument based on the
Cauchy-Schwarz inequality, as follows. Let $f(t)$ have the Fourier series
$f(t)\sim\sum_{\mathbb{Z}}c_{n}e^{int},$ then the derivative $f^{\prime}(t)$
has the Fourier series $f^{\prime}(t)\sim\\\ \sum_{\mathbb{Z}}inc_{n}e^{int},$
and the sequence of complex numbers $(nc_{n})_{(n\in{\mathbb{Z}})}$ is in
$\ell^{2}({\mathbb{Z}}).$ Since for $n\neq 0$ we may write
$c_{n}=\frac{1}{n}(nc_{n}),$ we get that the sequence
$(c_{n})_{(n\in{\mathbb{Z}})}$ is in $\ell^{1}({\mathbb{Z}})$ with
$\|(c_{n})\|_{1}\leq|c_{0}|+\frac{\pi}{\sqrt{3}}\|(nc_{n})\|_{2}.$ If we
translate this to the setting of the discrete group ${\mathbb{Z}}$ equipped
with the natural length function $|n|,$ we find that the group algebra
$C^{*}_{r}({\mathbb{Z}})$ may be identified with the complex continuous
$2\pi-$periodic functions on the real axis and an element $x$ in the group
algebra which correspond to a differentiable function has a presentation as a
uniformly convergent sum $x=\sum_{(n\in{\mathbb{Z}})}x_{n}\lambda_{n}.$ This
example may be generalized to the setting of a discrete group with a length
function when the content of the example is formulated as in the following
proposition.

######  Proposition 4.1.

Let $x\sim\sum_{\mathbb{Z}}x_{n}\lambda_{n}$ be an operator in
$C^{*}_{r}({\mathbb{Z}}).$ If the sequence
$\big{(}(1+|n|)x_{n}\big{)}_{(n\in{\mathbb{Z}})}$ is in
$\ell^{2}({\mathbb{Z}}),$ then the series is uniformly convergent and
$\|x\|\leq\big{(}\frac{\pi^{2}}{3}-1\big{)}^{\frac{1}{2}}\big{(}\sum_{n\in{\mathbb{Z}}}|x_{n}|^{2}(1+|n|)^{2}\big{)}^{\frac{1}{2}}.$

We recall from Chatterji’s survey article [2], Definition 2.9, in a modified
form.

######  Definition 4.2.

Let $G$ be a discrete group with a length function $|g|,$ then $G$ has the
rapid decay property, with respect to $|g|$ if there exists positive constants
$C,s$ such that for any operator $x=\sum_{g}x_{g}\lambda_{g}$ in the reduced
group C*-algebra and with finite support we have

$\|x\|\leq C\sqrt{\sum_{g\in G}|x_{g}|^{2}(1+|g|)^{2s}}.$

It is immediate that this definition may be extended to the setting of a
reduced crossed product of a C*-algebra by a discrete group in several ways.
We have played with 3 possibilities of definition, but only been able to
obtain results for the 2 of them, which we define below. The third possibility
is mentioned after the definition.

######  Definition 4.3.

Let $G$ be a discrete group with a length function $g\to|g|,$ such that $G$
acts on a C*-algebra ${\mathcal{A}}$ via a group of *-automorphisms
$\alpha_{g}.$ The reduced crossed product
${\mathcal{C}}:=C^{*}_{r}({\mathcal{A}}\rtimes_{\alpha}G)$ has rapid decay  of
operator type  or scalar type if there exist positive constants $C,s$ such
that for any operator $X=\sum L_{g}X_{g}$ with finite support:

operator type: $\displaystyle\|X\|\leq C\|\sum_{g\in
G}(1+|g|)^{2s}(L_{g}X_{g}X_{g}^{*}L_{g}^{*}+X_{g}^{*}X_{g})\|^{\frac{1}{2}}$
scalar type: $\displaystyle\|X\|\leq C\bigg{(}\sum_{g\in
G}(1+|g|)^{2s}\|X_{g}\|^{2}\bigg{)}^{\frac{1}{2}}$

If one of the properties above holds for any C*-algebra ${\mathcal{A}}$
carrying an action $\alpha_{g}$ of $G$ we say that $G$ possesses complete
rapid decay  of respectively operator type and scalar type.

In the very first version of the article we thought that we could prove that
free non abelian groups do have a sort of mixed rapid decay defined as

mixed type: $\displaystyle\|X\|\leq
C\bigg{(}\sum_{k=0}^{\infty}(1+|k|)^{2s}\|\sum_{g\in
C_{k}}\big{(}L_{g}X_{g}X_{g}^{*}L_{g}^{*}+X_{g}^{*}X_{g}\big{)}\|\bigg{)}^{\frac{1}{2}}.$

Unfortunately we were wrong, but it may still be that some discrete groups
with non polynomial growth satisfy such a condition, and that would be very
helpful in the study of multipliers of the form $M_{\varphi}$, as it follows
from the proof of Proposition 7.1.

The complete operator type of rapid decay  may be established for finitely
generated groups with polynomial growth by a simple imitation of the proofs
from the group algebra case. For other groups it seems impossible to us to
establish the operator type of rapid decay outside the reduced group algebra
case. We establish the complete scalar type of rapid decay  for discrete
groups which possess property (J) with respect to a length function.

##  5\. complete operator rapid decay in a reduced crossed product of a
C*-algebra by a finitely generated group with polynomial growth

Here we modify some of Jolissaint’s results from his section 3.1 of [11] to
cover our situation.

######  Theorem 5.1.

Let ${\mathcal{A}}$ be a C*-algebra, $G$ a finitely generated discrete group
with polynomial growth which has an action $\alpha_{g}$ on ${\mathcal{A}}$ as
a group of *-automorphisms. There exists positive reals $M,s$ such that for
any finitely supported operator $X=\sum L_{g}X_{g}$ in
${\mathcal{C}}:=C^{*}_{r}({\mathcal{A}}\rtimes_{\alpha}G):$

$\displaystyle\|X\|$ $\displaystyle\leq M\|\sum_{g\in
G}(1+|g|)^{s+2}L_{g}X_{g}X^{*}_{g}L^{*}_{g}\|^{\frac{1}{2}}$
$\displaystyle\|X\|$ $\displaystyle\leq M\|\sum_{g\in
G}(1+|g|)^{s+2}X^{*}_{g}X_{g}\|^{\frac{1}{2}}.$

###### Proof.

The polynomial growth implies that there exists positive reals $C,s$ such that
$|C_{k}|\leq C(1+k)^{s},$ then the following manipulations are standard, and
the proof follows from Proposition 2.2 as follows

$\displaystyle X=$ $\displaystyle\sum_{k=0}^{\infty}\sum_{g\in
C_{k}}\frac{1}{(1+k)|C_{k}|^{\frac{1}{2}}}\big{(}(1+k)|C_{k}|^{\frac{1}{2}}L_{g}X_{g}\big{)}$
$\displaystyle\leq$ $\displaystyle\sqrt{C}\sum_{k=0}^{\infty}\sum_{g\in
C_{k}}\frac{1}{(1+k)|C_{k}|^{\frac{1}{2}}}\big{(}(1+k)^{(1+\frac{s}{2})}{\frac{1}{2}}L_{g}X_{g}\big{)}$
$\displaystyle\|X\|\leq$
$\displaystyle\frac{\pi\sqrt{C}}{\sqrt{6}}\|\sum_{k=0}^{\infty}\sum_{g\in
C_{k}}(1+k)^{(2+s)}X_{g}^{*}X_{g}\|^{\frac{1}{2}}$ $\displaystyle\leq$
$\displaystyle\frac{\pi\sqrt{C}}{\sqrt{6}}\sqrt{2}\|\sum_{g\in
G}(1+|g|)^{(2+s)}X_{g}^{*}X_{g}\|^{\frac{1}{2}}$

so $M:=\frac{\pi\sqrt{2C}}{\sqrt{6}},$ may be used. The inequality involving
$L_{g}X_{g}X_{g}^{*}L_{g}^{*}$ follows in the same way. ∎

##  6\. Complete scalar rapid decay for discrete groups with property (J)

The basic result in this section is the proposition just below, and this is a
combined extension of some of the first results in [8].

######  Proposition 6.1.

Let $(G,|\cdot|)$ be a discrete group with a length function satisfying the
property (J). There exists a positive constant $N$ such that for any action of
$G$ as a group of *-automorphisms $\alpha_{g}$ on a C*-algebra
${\mathcal{A}},$ any non negative integer $k$ and any operator $X=\sum_{g\in
G}L_{g}X_{g}$ in ${\mathcal{C}}:=C^{*}_{r}({\mathcal{A}}\rtimes_{\alpha}G)$
with finite support in $C_{k}:$

$\|X\|\leq N(1+k)\sqrt{\sum\|X_{g}\|^{2}}.$

###### Proof.

We will let $Y$ denote any finitely supported element in ${\mathcal{C}}$ with
column or $\pi-$norm at most 1. By Proposition 2.4 it is sufficient to bound
the $\pi-$norm of $XY$ in order to bound the operator norm $\|X\|.$ Using the
cancellation numbers, the operator $XY$ may be written as a sum of $k+1$
summands $S_{p}$ defined as follows

$\displaystyle XY$ $\displaystyle=\sum_{a\in C_{k}}\sum_{b\in
G}L_{a}X_{a}L_{b}Y_{b}$ (6.1) $\displaystyle=\sum_{p=0}^{k}\sum_{\\{(a,b)\in
P_{p}\,:a\in C_{k}\\}}L_{a}X_{a}L_{b}Y_{b}$
$\displaystyle=\sum_{p=0}^{k}S_{p}$

Then let us fix a $p$ in the set $\\{0,1,\dots,k\\}.$ By the property (J)
there exists $\alpha>0,\hat{\beta}>0,M>0$ such that to each group element $g,$
each $p$ and each pair of group elements $(a,b)\in P_{p}$ with $ab=g$ and
$a\in C_{k}$ there exist group elements
$u_{(g,(k-p))},\,v_{(g,(k-p))},\,c(a,b)$ such that

(6.2) $\displaystyle u_{(g,(k-p))}\in C_{(k-p),\alpha},\,\quad
v_{(g,(k-p))}\in C_{(|g|+1-k+p),\hat{\beta}},\quad c(a,b)\in C_{p,M},$
$\displaystyle a=u_{(g,(k-p))}c(a,b),\,\quad b=c(a,b)^{-1}v_{(g,(k-p))}.$

We have $|g|=|a|+|b|-2p-c$ with $c\in\\{0,1\\},$ hence since $|a|=k$ we get
$|g|+1-k+p=|b|-p+1-c$ so for $\beta:=\hat{\beta}+1$ we have

(6.3) $v_{(g,(k-p))}\in C_{(|b|-p),\beta}.$

In Haagerup’s case with free groups we get $u_{(g,(k-p))}=a_{1}\dots
a_{(k-p)},\newline \,c(a,b)=a_{(k-p+1)}\dots
a_{k},\,v_{(g,(k-p))}=b_{(p+1)}\dots b_{|b|},$ with
$u_{(g,(k-p))}\in C_{(k-p)},\,c(a,b)\in C_{p},\,v_{(g,(k-p))}\in C_{(|b|-k)}.$
In the case of a free non commutative group the 2 first elements $u,c$ are
determined by $a,p$ and the last 2 elements $c,v$ are determined by $b,p,$ but
in the general case $a,p$ does not determine the pair $u_{(g,(k-p))},c(a,b)$
nor does the pair $b,p$ determines the pair $c(a,b),v_{(g,(k-p))}.$ The
condition (3.2) is designed to deal with this problem.

We can now start the estimation, and we will use the results of Proposition
2.2, so for a given $g$ we define a positive operator $Q_{u_{(g,(k-p))}}$ by

(6.4) $\displaystyle Q_{u_{(g,(k-p))}}^{2}:$ $\displaystyle=\sum_{\\{(a,b)\in
P_{p}:a\in C_{k},\,ab=g\\}}L_{a}X_{a}X_{a}^{*}L_{a}^{*}.$

To each pair $(a,b)$ in $P_{p}$ with $a$ in $C_{k},$ and $ab=g$ there exists a
contraction $q(a,b)$ such that $L_{a}X_{a}=Q_{u_{(g,(k-p))}}q(a,b)$ with

$\sum_{\\{(a,b)\in P_{p}:a\in C_{k},ab=g\\}}q(a,b)q(a,b)^{*}\leq I.$

Analogously we define $R_{v_{(g,(k-p))}}$ as the positive operator which is
given by

(6.5) $\displaystyle R_{v_{(g,(k-p))}}^{2}$ $\displaystyle=\sum_{\\{(a,b)\in
P_{p}:a\in C_{k}\,ab=g\\}}Y_{b}^{*}Y_{b}$

To each group element $g$ and each pair $(a,b)$ in $P_{p}$ with $g=ab$ and $a$
in $C_{k},$ there exists a contraction $r(a,b)$ such that
$L_{b}Y_{b}=r(a,b)R_{v_{(g,(k-p))}}$ with

$\sum_{\\{(a,b)\in P_{p}:a\in C_{k},ab=g\\}}r(a,b)^{*}r(a,b)\leq I,$

and according to Proposition 2.2 we may define a contraction operator $m_{g}$
by

(6.6) $\forall g\in G:\quad m_{g}:=\sum_{\\{(a,b)\in P_{p}:a\in
C_{k}\,ab=g\\}}q(a,b)r(a,b).$

When combining these equations we get

(6.7) $S_{p}(g)=Q_{u_{(g,(k-p))}}m_{g}R_{v_{(g,(k-p))}}$

and then

(6.8) $\displaystyle\sum_{g\in G}S_{p}(g)^{*}S_{p}(g)=\sum_{g\in
G}R_{v_{(g,(k-p))}}m_{g}^{*}Q_{u_{(g,(k-p))}}^{2}m_{g}R_{v_{(g,(k-p))}}\text{by
}\|m_{g}\|\leq 1$ $\displaystyle\leq$ $\displaystyle\sum_{g\in
G}\|Q_{u_{(g,(k-p))}}^{2}\|R_{v_{(g,(k-p))}}^{2}\text{ by }(\ref{Q})\text{ and
}(\ref{GG})$ $\displaystyle\leq$ $\displaystyle\sum_{g\in
G}\big{(}\sum_{(a,b)\in
P_{p}:ab=g}\|X_{u_{(g,(k-p))}c(a,b)}\|^{2}\big{)}\cdot$
$\displaystyle\big{(}\sum_{(e,f)\in
P_{p}:ef=g}Y_{c(e,f)^{-1}v_{(g,(k-p))}}^{*}Y_{c(e,f)^{-1}v_{(g,(k-p))}}\big{)}\text{
split to sum over }h,\,g$ $\displaystyle\leq$ $\displaystyle\big{(}\sum_{g\in
G}\sum_{(a,b)\in P_{p}:ab=g}\|X_{u_{(g,(k-p))}c(a,b)}\|^{2}\big{)}\cdot$
$\displaystyle\big{(}\sum_{h\in G}\sum_{(e,f)\in
P_{p}:ef=h}Y_{c(e,f)^{-1}v_{(g,(k-p))}}^{*}Y_{c(e,f)^{-1}v_{(g,(k-p))}}\big{)}$

In the last 2 sums depending on $g$ and $h$ respectively, one can via the
property (3.2) get an upper bound on the number of times each element of the
form $\|X_{a}\|^{2}$ or $Y_{f}^{*}Y_{f}$ appears in the sum. Let $a$ in
$C_{k}$ be given, then the number of solutions to the equation

$u\in C_{(k-p),\alpha},\,c\in C_{p,M}:\quad uc=a$

is at most $N.$ Similarly for each $f$ the number of solutions to the equation

$v\in C_{(|f|-p),\beta},\,c\in C_{p,M}:\quad c^{-1}v=f$

is at most $N,$ and hence by (6.8)

(6.9) $\displaystyle\|S_{p}\|_{\pi}\leq$ $\displaystyle N\big{(}\sum_{a\in
C_{k}}\|X_{a}\|^{2}\big{)}^{\frac{1}{2}}\|Y\|_{\pi}\text{ so }$
$\displaystyle\|XY\|_{\pi}\leq$ $\displaystyle(k+1)N\big{(}\sum_{a\in
C_{k}}\|X_{a}\|^{2}\big{)}^{\frac{1}{2}}\|Y\|_{\pi}\text{ by Proposition
}\ref{cpnorm}$ $\displaystyle\|X\|\leq$ $\displaystyle(k+1)N\big{(}\sum_{a\in
C_{k}}\|X_{a}\|^{2}\big{)}^{\frac{1}{2}},$

and the proposition follows

∎

In the case of a free non abelian group ${\mathbb{F}}_{d}$ with any set,
finite or infinite, of generators the proposition above holds with $N=1.$ The
reason is that for a pair $(a,b)$ in $P_{p}$ with $a\in C_{k}$ the
decompositions $a=u_{(g,(k-p))}c(a,b)$ and $b=c(a,b)^{-1}v_{(g,(k-p))}$ are
described in an exact form just below the equation (6.3), such that the
constants $\alpha,\,\beta,\,\gamma$ in Definition 3.3 may be used with value
0. The exact decomposition also shows that in this case there will only be one
solution to the equation (3.2) so we get $N=1$ in this case, and we may note
the following corollary.

######  Corollary 6.2.

Let ${\mathcal{A}}$ be a C*-algebra with an action $\alpha_{g}$ of
${\mathbb{F}}_{d},$ the free non commutative group with $d$ generators, then
for any $k\in{\mathbb{N}}_{0}$ and any $X$ in $C^{*}_{r}({\mathcal{A}})$ with
finite support in $C_{k}$:

$\|X\|\leq(k+1)\big{(}\sum_{a\in C_{k}}\|X_{a}\|^{2}\big{)}^{\frac{1}{2}}.$

It is worth to remark that the result in the corollary above in the case of
the trivial C*-algebra ${\mathcal{A}}={\mathbb{C}}I$ gives exactly the content
of Lemma 1.5 in [8]. The content of Lemma 1.3 in [8] is named the Haagerup
property  in [15]. We may also here add a corollary describing the form the
Haagerup property takes in the setting of a reduced crossed product of a
C*-algebra by a discrete group with the property (J) This is the natural
extension of Jolissaint’s Proposition 3.2.4 in [11].

######  Corollary 6.3.

For $k,l,m$ non negative integers and any pair of finitely supported elements
$X=\sum_{g}L_{g}X_{g}$ with support in $C_{k}$ and $Y=\sum_{g}L_{g}Y_{g}$ with
support in $C_{l}:$

$\displaystyle\|M_{\chi_{m}}*\big{(}XY\big{)}\|\leq N\big{(}\sum_{a\in
C_{k}}\|X_{a}\|^{2}\big{)}^{\frac{1}{2}}\|\sum_{b\in
C_{l}}Y_{b}^{*}Y_{b}\|^{\frac{1}{2}}$
$\displaystyle\|M_{\chi_{m}}*\big{(}XY\big{)}\|\leq N\|\sum_{a\in
C_{k}}L_{a}X_{a}X_{a}^{*}L_{a}^{*}\|^{\frac{1}{2}}\big{(}\sum_{b\in
C_{l}}\|Y_{b}\|^{2}\big{)}^{\frac{1}{2}}$

When $G$ is a free non abelian group $N=1.$

###### Proof.

Let $a\in C_{k}$ and $b\in C_{l}$ be such that $ab\in C_{m}$ then there exists
uniquely determined $c\in\\{0,1\\}$ and $p$ in ${\mathbb{N}}_{0}$ such that

$k+l-m=2p+c.$

In particular at most one $S_{p}\neq 0,$ and the first inequality of the
corollary follows from the proof of the theorem. The second follows from the
first when applied to $(Y^{*}X^{*}).$ The free group statement follows from
the corollary just above. ∎

The fact that there are 2 inequalities above indicates to us that there might
be a hope for the desired inequality  below to be true for a finitely
supported $X$ with support in $C_{k}$ and a finitely supported $Y$ with
support in $C_{l}$ we hope that

desired inequality $\displaystyle\|M_{\chi_{m}}*\big{(}XY\big{)}\|\leq
N\|\sum_{a\in C_{k}}L_{a}X_{a}X_{a}^{*}L_{a}^{*}\|^{\frac{1}{2}}\|\sum_{b\in
C_{l}}Y_{b}^{*}Y_{b}\|^{\frac{1}{2}}$

We may then continue and consider general elemnts $X$ with finite support.

######  Theorem 6.4.

Let $G$ be a discrete group with a length function such that $G$ satisfies the
condition (J). There exists an $M>0$ such that for any action $\alpha_{g}$ of
$G$ on a C*-algebra ${\mathcal{A}}$ and any $X=\sum_{g\in G}L_{g}X_{g}$ of
finite support in $C^{*}_{r}({\mathcal{A}}\rtimes_{\alpha}G):$

$\|X\|\leq M\sqrt{\sum_{g\in G}(1+|g|)^{4}\|X_{g}\|^{2}}.$

###### Proof.

We may proceed as in the proof of Lemma 1.5 in [8], so

$\displaystyle\|X\|\leq$ $\displaystyle\sum_{k=0}^{\infty}\|\sum_{g\in
C_{k}}X_{g}\|$ $\displaystyle\leq$ $\displaystyle
N\sum_{k=0}^{\infty}(k+1)^{-1}\bigg{(}(k+1)^{2}\big{(}\sum_{g\in
C_{k}}\|X_{g}\|^{2}\big{)}^{\frac{1}{2}}\bigg{)}$ $\displaystyle\leq$
$\displaystyle
N\frac{\pi}{\sqrt{6}}\bigg{(}\sum_{k=0}^{\infty}(k+1)^{4}\sum_{g\in
C_{k}}\|X_{g}\|^{2}\bigg{)}^{\frac{1}{2}}$ $\displaystyle\leq$ $\displaystyle
N\frac{\pi}{\sqrt{6}}\sqrt{2}\bigg{(}\sum_{g\in
G}(1+|g|)^{4}\|X_{g}\|^{2}\bigg{)}^{\frac{1}{2}}$

and the theorem follows, since for $g\in C_{k}$ we have $k-1<|g|\leq k.$ ∎

Again there is a sharper estimate in the case of a free non abelian group.

######  Corollary 6.5.

If $G$ is a free non abelian group the constant $M$ may be chosen as $M=2.$

##  7\. Applications

The theory of rapid decay  for group C*-algebras has been applied to various
types of approximation properties for operator algebras [2], [3] [5], [9], and
many research articles are based on, or inspired by these works.

Jolissaint realized from the beginning [12] that the rapid decay property
makes it possible to base some K-theoretical computations on a subalgebra of
rapidly decreasing operators,  and this was then used by Lafforgue [14] in his
fundamental work on the Baum-Connes conjecture.

The construction of a spectral triple for a reduced group C*-algebra of a
discrete group, which occurs in Connes’ non commutative geometry, has an
obvious candidate if the group has a length function. It seems natural to use
the property rapid decay  to get some information on the properties of this
spectral triple, and such attempts have appeared in [1] and [15]. It is
interesting to see that the so-called Haagerup  condition of [15] is the
content of the very basic Lemma 1.3 of [8] and of Proposition 3.2.4 of [11].
Here it is contained in the corollary 6.3.

It is not our intent to pursue possible extensions of the results based on
rapid decay from the group algebra case to the crossed product setting, but we
have made one easy observation, which may be applied to a possible extension
of some of the approximation properties.

In Haagerup’s first article [8] he shows in Lemma 1.7 that for a function
$\varphi$ on a free non abelain group $G$ the multiplier $M_{\varphi}$ is
bounded if $\sup\\{|\varphi(g)|(1+|g|)^{2}:g\in G\\}$ is finite and
$\|M_{\varphi}\|\leq 2\sup\\{|\varphi(g)|(1+|g|)^{2}:g\in G\\}.$ This result
makes it possible for him to cut the completely positive multiplier of norm 1
given by $M_{\varphi_{\lambda}}$ with $\varphi_{\lambda}(g):=e^{-\lambda|g|}$
to the subsets $B_{n},$ and in this way he obtains a bounded approximate
multiplier unit consisting of functions with finite support. We can not obtain
such a nice result here because Haagerup’s estimate is based on the fact that
in the group algebra case we have $\|\lambda(f)\|\geq\|f\|_{2},$ and the
analogous statement for crossed products is not true. We can get a result
which is is similar to Haagerup’s Lemma 1.7 for a group action which has
operator rapid decay.

######  Proposition 7.1.

Let ${\mathcal{A}}$ be a C*-algebra, G a discrete group with a length function
and $\alpha_{g}$ an action of the group on ${\mathcal{A}}$ such that the
reduced crossed product has operator rapid decay with coefficients $C,s.$ If a
complex function $\varphi$ on the group satisfies
$m:=\sup\\{|\varphi(g)|(2+|g|)^{(s+1)}\,:\,g\in G\\}<\infty$ then the
multiplier $M_{\varphi}$ on $C^{*}_{r}({\mathcal{A}}\rtimes_{\alpha}G)$ is
bounded and satisfies $\|M_{\varphi}\|\leq 2Cm.$ If the action of $\alpha_{g}$
has complete operator rapid decay, then $M_{\varphi}$ is completely bounded
with $\|M_{\varphi}\|_{cb}\leq 4Cm.$

###### Proof.

Suppose $\varphi$ is given with $m$ finite then for any $X=\sum L_{g}X_{g}$
with finite support

(7.1) $\displaystyle\|M_{\varphi}*X\|^{2}$ $\displaystyle\leq
C^{2}\|\sum_{g\in
G}(1+|g|)^{2s}|\varphi(g)|^{2}(L_{g}X_{g}X_{g}^{*}L_{g}^{*}+X_{g}^{*}X_{g})\|$
$\displaystyle\leq C^{2}\|\sum_{g\in
G}(1+|g|)^{-2}m^{2}(L_{g}X_{g}X_{g}^{*}L_{g}^{*}+X_{g}^{*}X_{g})\|$
$\displaystyle\leq 4C^{2}m^{2}\sum_{k=0}^{\infty}(1+k)^{-2}\|\sum_{g\in
C_{k}}L_{g}X_{g}X_{g}^{*}L_{g}^{*}+X_{g}^{*}X_{g}\|$ $\displaystyle\leq
8C^{2}m^{2}\frac{\pi^{2}}{6}\|X\|^{2}$ $\displaystyle\leq
16C^{2}m^{2}\|X\|^{2}.$

If $G$ possesses complete operator rapid decay, the action $\alpha_{g}$ on
${\mathcal{A}}$ may be lifted to actions on $M_{n}({\mathcal{A}}),$ which all
have operator rapid decay with coefficients $C,s$ and the result follows. ∎

## References

  * [1] C. Antonescu, E. Christensen,Metrics on group C*-algebras and a non-commutative Arzelà-Ascoli theorem, J Funct. Anal. 214 (2004), 247-–259.
  * [2] I. Chatterji, Introduction to the rapid decay property. Around Langlands correspondences, Contemp. Math. Amer. Math. Soc. 691 (2017), 53 – 72.
  * [3] P.-A. Cherix, M. Cowling, P. Jolissaint, P. Julg, A. Valette, Groups with the Haagerup property, Progress in Mathematics, 197 (2001), BirkhäuserVerlag, Basel.
  * [4] E. Christensen, The block Schur product is a Hadamard product, Math. Scand. 126 (2020), 603-–616.
  * [5] M. G. Cowling, U. Haagerup, Completely bounded multipliers of the Fourier algebra of a simple Lie group of real rank one, Invent. Math.96 (1989), 507-–549.
  * [6] E. Ghys, P. de la Harpe, Sur les groupes hyperboliques d’après Mikhael Gromov, ed., Birkhäuser Boston Inc., Boston, MA, 1990.
  * [7] M. Gromov, Hyperbolic groups, Essays in group theory, S. M. Gersten, ed., Springer,1987.
  * [8] U. Haagerup, An example of a non nuclear C*-Algebra, which has the metric approximation property, Inv. Math. 50 (1979), 279–293
  * [9] U. Haagerup, J. Kraus Approximation properties for group C*-Algebras and group von Neumann algebras, Transactions Amer. Math. Soc. 334 (1994),667–699
  * [10] P. de la Harpe, Groupes hyperboliques, algèbres d’opérateurs et un théorème de Jolissaint, C. R. Acad. Sci. Paris, 307 1988, 771–774,
  * [11] P. Jolissaint, Rapidly decreasing functions in reduced C*-algebras of groups, Trans. Amer. Math. Soc. 317 (1990), 167 – 196.
  * [12] P. Jolissaint, K-Theory of reduced C*-Algebras and rapidly decreasing functions on groups, K-Theory 2 (1989), 723-–735.
  * [13] R. V. Kadison, J. R. Ringrose, Fundamentals of the theory of operator algebras, Academic Press, 1986.
  * [14] V. Lafforgue, KK-théorie bivariante pour les algèbres de Banach et conjecture de Baum-Connes,  Invent. Math. 149 (2002), 1–95.
  * [15] N. Ozawa, M. A. Rieffel, Hyperbolic group C*-algebras and free-product C*-algebras as compact quantum metric spaces, Canad. J. Math. 57 (2005), 1056–1079.
  * [16] V. Paulsen, Completely bounded maps and operator algebras, Cambridge Univ. Press, Cambridge, 2002\.
  * [17] F. Pop, A. M. Sinclair, R. R. Smith, Norming C*-algebras by C*-subalgebras, J. Funct. Anal. 175 (2000), 168–196.
  * [18] W. F. Stinespring, Positive functions on C*-algebras, Proc. Amer. Math. Soc. 6 (1955), 211–216.


#  scikit-hubness: Hubness Reduction and Approximate Neighbor Search

Roman Feldbauer  Division of Computational Systems Biology, Department of
Microbiology and Ecosystem Science
University of Vienna, Althanstraße 14, 1090 Vienna, Austria  Thomas Rattei
Division of Computational Systems Biology, Department of Microbiology and
Ecosystem Science
University of Vienna, Althanstraße 14, 1090 Vienna, Austria  Arthur Flexer
Austrian Research Institute for Artificial Intelligence (OFAI)
Freyung 6/6/7, 1010 Vienna, Austria

###### Abstract

This paper introduces scikit-hubness, a Python package for efficient nearest
neighbor search in high-dimensional spaces. Hubness is an aspect of the curse
of dimensionality, and is known to impair various learning tasks, including
classification, clustering, and visualization. scikit-hubness provides
algorithms for hubness analysis (“Is my data affected by hubness?”), hubness
reduction (“How can we improve neighbor retrieval in high dimensions?”), and
approximate neighbor search (“Does it work for large data sets?”). It is
integrated into the scikit-learn environment, enabling rapid adoption by
Python-based machine learning researchers and practitioners. Users will find
all functionality of the scikit-learn neighbors package, plus additional
support for transparent hubness reduction and approximate nearest neighbor
search. scikit-hubness is developed using several quality assessment tools and
principles, such as PEP8 compliance, unit tests with high code coverage,
continuous integration on all major platforms (Linux, MacOS, Windows), and
additional checks by LGTM. The source code is available at
https://github.com/VarIr/scikit-hubness under the BSD 3-clause license.
Install from the Python package index with $ pip install scikit-hubness.

#### Key words

hubness, nearest neighbors, curse of dimensionality, scikit-learn, Python

##  1 Introduction

Hubness is a phenomenon in nearest neighbor graphs (Radovanović et al., 2010),
that is often detrimental to data mining and learning tasks building upon
them. It is an aspect of the curse of dimensionality, which describes
challenges arising when data are embedded in high dimensions. Specifically,
hubness describes the increasing occurrence of hubs and antihubs with
increasing data dimensionality: Hubs are objects, that appear uncommonly often
among the nearest neighbors of others objects, while antihubs are never
retrieved as neighbors. As a consequence, hubs may propagate their information
(for example, class labels) too widely within the neighbor graph, while
information from antihubs is depleted. These semantically distorted graphs can
reduce learning performance in various tasks, such as classification
(Radovanović et al., 2010), clustering (Schnitzer and Flexer, 2015), or
visualization (Flexer, 2015). Hubness is known to affect a variety of applied
learning systems,causing—for instance—odd music recommendations (Schnitzer et
al., 2012), or improper transport mode detection (Feldbauer et al., 2018).

Multiple hubness reduction algorithms have been developed to mitigate these
effects (Schnitzer et al., 2012; Flexer and Schnitzer, 2013; Hara et al.,
2015, 2016). In a recent survey, we compared these algorithms exhaustively
(Feldbauer and Flexer, 2019), and developed approximate hubness reduction
methods with linear time and memory complexity for the most successful
algorithms (Feldbauer et al., 2018).

In this paper we describe scikit-hubness, which provides readily available,
easy-to-use hubness analysis and reduction for both machine learning
researchers and practitioners.

##  2 Software Development and Architecture

scikit-hubness is a Python package built upon the SciPy stack (Virtanen et
al., 2019) and scikit-learn (Pedregosa et al., 2011) with cross-platform
support for Linux, MacOS, and Windows. It consists of three sub-packages, that
are detailed in the sections below. Code style and API design is based on the
guidelines of scikit-learn, with PEP 8 compliance, NumPy documentation format,
and additional criteria, such as those tested by LGTM.111Automated code
analysis is performed by https://lgtm.com/projects/g/VarIr/scikit-hubness/.
Code development is aided by continuous integration on all three platforms,
with an extensive set of tests covering nearly the complete code base. Source
code, issue tracker, quickstart, and additional links are available at
GitHub.222Source code, issue tracker, and additional links etc. can be found
at https://github.com/VarIr/scikit-hubness/. The online documentation is
available at Read the Docs.333Online documentation is available at
https://scikit-hubness.readthedocs.io/.

###  2.1 analysis: Hubness Analysis

The skhubness.analysis sub-package allows to determine, whether data is
affected by hubness. This is often the first step in a user’s workflow,
allowing for quick assessment of potential improvements due to hubness
reduction. The package provides several hubness measures, including long-
proven ones, such as the $k$-occurrence skewness (Radovanović et al., 2010),
as well as recently proposed measures, such as the Robin-Hood index (Feldbauer
et al., 2018).

###  2.2 reduction: Hubness Reduction Algorithms

The skhubness.reduction sub-package provides hubness reduction algorithms. At
the time of writing, the most successful methods (Feldbauer and Flexer, 2019)
are available: mutual proximity, local scaling (Schnitzer et al., 2012), and
DisSimLocal (Hara et al., 2016). We implement both the exact methods
(quadratic complexity), and their approximations (linear complexity, Feldbauer
et al., 2018). Neighbor graphs can be hubness-reduced directly with classes
from this package, which may be especially useful for hubness-related
research.

###  2.3 neighbors: Neighbors-Based Learning

Practitioners find convenient interfaces to hubness-reduced neighbors-based
learning in the skhubness.neighbors sub-package. It features all functionality
from sklearn.neighbors and adds support for hubness reduction, where
applicable. This includes, for example, the supervised KNeighborsClassifier
and RadiusNeighborsRegressor, NearestNeighbors for unsupervised learning, and
the general kneighbors_graph.

⬇

from skhubness.data import\

load_dexter

X, y = load_dexter()

from sklearn.neighbors import\

KNeighborsClassifier

knn_vanilla = KNeighborsClassifier(

n_neighbors=5, metric="cosine",

)

from sklearn.model_selection import\

cross_val_score

acc_vanilla = cross_val_score(

knn_vanilla, X, y, cv=5)

# Accuracy (vanilla kNN):

print(f"{acc_vanilla.mean():.3f}")

# 0.793

⬇

from skhubness.data import\

load_dexter

X, y = load_dexter()

from skhubness.neighbors import\

KNeighborsClassifier

knn_mp = KNeighborsClassifier(

n_neighbors=5, metric="cosine",

hubness="mutual_proximity" )

from sklearn.model_selection import\

cross_val_score

acc_mp = cross_val_score(

knn_mp, X, y, cv=5)

# Accuracy (hubness-reduced kNN)

print(f"{acc_mp.mean():.3f}")

# 0.893

Example 1: Quickstart example. Left: kNN classification in scikit-learn.
Right: Hubness reduction is enabled in scikit-hubness by providing one
additional parameter.

Time and memory requirements of exact nearest neighbor algorithms scale
quadratically with the number of samples. In order to support very large data
sets, scikit-hubness provides approximate neighbor search with linear
complexity. Several methods are currently available, including locality-
sensitive hashing and hierarchical navigable small-world graphs(Aumüller et
al., 2019; Malkov and Yashunin, 2016). Note, that approximate search can be
employed in conjunction with or independently from hubness reduction.
Therefore, scikit-hubness provides powerful neighbor search in large-scale
data, hubness-affected or not.

##  3 Installation and Basic Example

Assuming an existing Python environment, scikit-hubness can be installed from
the Python package index via $ pip install scikit-hubness at the command line.

Example 1 shows a quickstart example of text classification. Adapting sklearn-
based nearest neighbor pipelines to use hubness reduction requires only minor
modifications (see highlighted code). Given the vast user base of scikit-
learn, hubness reduction is now available to a large number of machine
learning researchers and practitioners with very little transition effort.

##  4 Comparison to Similar Software

Tool | Platform |  | Last
---
update
| Mutual
---
proximity
| Local
---
scaling
| DisSim
---
Local
| Approximate
---
hubness reduction
| scikit-learn
---
compatible
HubMiner444HubMiner is available from http://ailab.ijs.si/tools/hub-miner/. | Java | 2015 | ✓ | ✓ | ✗ | ✗ | (N/A)
Hub-Toolbox555Hub-Toolbox for MATLAB is available from https://github.com/OFAI/hub-toolbox-matlab. | Matlab | 2016 | ✓ | ✓ | ✗ | ✗ | (N/A)
Hub-Toolbox666Hub-Toolbox for Python is available from https://github.com/OFAI/hub-toolbox-python3. | Python | 2019 | ✓ | ✓ | ✓ | ✓ | (partial)
scikit-hubness | Python | 2019 | ✓ | ✓ | ✓ | ✓ | ✓
Table 1: Comparison of hubness reduction software packages

Several tools for hubness reduction have previously been developed. Table 1
provides an overview of selected features. Within the last three years, only
the Hub-Toolbox for Python and scikit-hubness have been actively developed.
Both tools originate from our research groups. The Hub-Toolbox was released
primarily to enable reproducibility for hubness research performed in our
labs. It features only partial compatibility with scikit-learn, and is
currently lacking a consistent API. Scikit-hubness succeeds the Hub-Toolbox,
and puts a strong focus on usability. It has been rewritten from scratch in
order to provide a more user-friendly, more easily extensible, fully scikit-
learn compatible machine learning package.

##  5 Conclusion and Outlook

Ever since its original release, scikit-learn has become one of the most
popular machine learning frameworks with over $65\,000$ dependent repositories
on GitHub at the time of writing (August 2019). Scikit-hubness integrates
seamlessly with scikit-learn, and introduces effective hubness reduction and
approximate neighbor search into this ecosystem. We are confident to provide
the most user-friendly hubness analysis and reduction software package
released so far.

Future plans include adaption to significant changes of sklearn.neighbors
likely to be introduced in the next major release: The KNeighborsTransformer
and RadiusNeighbors- Transformer777Upcoming scikit-learn changes:
https://github.com/scikit-learn/scikit-learn/pull/10482 transform data into
sparse neighbor graphs, which can subsequently be used as input to other
estimators. Hubness reduction and approximate search can then be implemented
as Transformers. This provides the means to turn skhubness.neighbors from a
drop-in replacement of sklearn.neighbors into a scikit-learn plugin, which
will  (1) accelerate development,  (2) simplify addition of new hubness
reduction and approximate search methods, and  (3) facilitate more flexible
usage.

#### Acknowledgements

We thank Silvan David Peter for testing the software.
This research is supported by the Austrian Science Fund (FWF): P27703 and
P31988

## References

  * Aumüller et al. [2019] Martin Aumüller, Tobias Christiani, Rasmus Pagh, and Michael Vesterli.  PUFFINN: parameterless and universally fast finding of nearest neighbors.  In _Annual European Symposium on Algorithms, ESA_ , volume 144, pages 10:1–10:16, 2019.
  * Feldbauer and Flexer [2019] Roman Feldbauer and Arthur Flexer.  A comprehensive empirical comparison of hubness reduction in high-dimensional spaces.  _Knowledge and Information Systems_ , 59(1):137, April 2019.
  * Feldbauer et al. [2018] Roman Feldbauer, Maximilian Leodolter, Claudia Plant, and Arthur Flexer.  Fast approximate hubness reduction for large high-dimensional data.  In _IEEE International Conference on Big Knowledge (ICBK)_ , pages 358–367, November 2018.
  * Flexer [2015] Arthur Flexer.  Improving visualization of high-dimensional music similarity spaces.  In _International Society for Music Information Retrieval Conference (ISMIR)_ , pages 547–553, 2015.
  * Flexer and Schnitzer [2013] Arthur Flexer and Dominik Schnitzer.  Can shared nearest neighbors reduce hubness in high-dimensional spaces?  In _IEEE International Conference on Data Mining (ICDM) Workshops_ , pages 460–467, December 2013.
  * Hara et al. [2015] Kazuo Hara, Ikumi Suzuki, Masashi Shimbo, Kei Kobayashi, Kenji Fukumizu, and Miloš Radovanović.  Localized centering: Reducing hubness in large-sample data.  In _Conference on Artificial Intelligence (AAAI)_ , 2015.
  * Hara et al. [2016] Kazuo Hara, Ikumi Suzuki, Kei Kobayashi, Kenji Fukumizu, and Milos Radovanovic.  Flattening the density gradient for eliminating spatial centrality to reduce hubness.  In _Conference on Artificial Intelligence (AAAI)_ , 2016.
  * Malkov and Yashunin [2016] Yury Malkov and Dmitry Yashunin.  Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.  _arXiv preprint_ , 2016.  URL https://arxiv.org/abs/1603.09320.
  * Pedregosa et al. [2011] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, et al.  Scikit-learn: Machine learning in Python.  _J. Mach. Learn. Res._ , 12:2825–2830, November 2011.
  * Radovanović et al. [2010] Miloš Radovanović, Alexandros Nanopoulos, and Mirjana Ivanović.  Hubs in space: Popular nearest neighbors in high-dimensional data.  _J. Mach. Learn. Res._ , 11:2487–2531, December 2010.
  * Schnitzer and Flexer [2015] Dominik Schnitzer and Arthur Flexer.  The unbalancing effect of hubs on k-medoids clustering in high-dimensional spaces.  In _International Joint Conference on Neural Networks (IJCNN)_ , July 2015.
  * Schnitzer et al. [2012] Dominik Schnitzer, Arthur Flexer, Markus Schedl, and Gerhard Widmer.  Local and global scaling reduce hubs in space.  _J. Mach. Learn. Res._ , 13(1):2871–2902, October 2012.
  * Virtanen et al. [2019] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, et al.  SciPy 1.0–fundamental algorithms for scientific computing in Python.  _arXiv preprint_ , 2019.  URL http://arxiv.org/abs/1907.10121v1.