# Finding automorphism groups of double coset graphs and Cayley graphs are
equivalent

Rachel Barber  Rachel Barber, Department of Mathematics, Hood College
401 Rosemont Ave, Frederick, MD 21701, USA<EMAIL_ADDRESS>and  Ted Dobson
Ted Dobson, University of Primorska, UP IAM, Muzejski trg 2, SI-6000 Koper,
Slovenia and
University of Primorska, UP FAMNIT, Glagoljaška 8, SI-6000 Koper, Slovenia
<EMAIL_ADDRESS>
###### Abstract.

It has long been known that a vertex-transitive graph $\Gamma$ is isomorphic
to a double coset graph ${\rm Cos}(G,H,S)$ of a transitive group $G\leq{\rm
Aut}(\Gamma)$, a vertex stabilizer $H\leq G$, and some subset $S\subseteq G$.
We show that the automorphism group of the Cayley graph ${\rm Cay}(G,S)$ with
connection set $S$ can be obtained from the automorphism group of ${\rm
Cos}(G,H,S)$ and vice versa. We also show that the isomorphism problem for
double coset graphs is equivalent to the isomorphism problem for Cayley graphs
provided one knows all groups $G$ for which a fixed Cayley graph is a Cayley
graph of $G$. Our main tool is a “recognition theorem”, which recognizes when
a Cayley graph of a group $G$ is a wreath product of two graphs based upon its
connection set.

This work is supported in part by the Slovenian Research Agency (research
program P1-0285 and research projects N1-0140, N1-0160, J1-2451, N1-0208,
J1-3001, J1-3003, J1-4008, and J1-50000).

##  1\. Introduction

The problem of determining the automorphism group of a vertex-transitive graph
is perhaps the most important and central problem in algebraic graph theory.
In this paper, we will show in Corollary 4.10 that the problem of determining
the automorphism group of a double coset graph ${\rm Cos}(G,H,S)$ is
equivalent to the problem of determining the automorphism group of its
corresponding Cayley graph, ${\rm Cay}(G,S)$. As every vertex-transitive graph
is isomorphic to a double coset graph [21, Theorem 2], the seemingly larger
problem of determining automorphism groups of vertex-transitive graphs is
equivalent to the problem of finding the automorphism groups of Cayley graphs
(assuming one knows a transitive subgroup of the graphs’ automorphism group).
We also show a similar result concerning isomorphisms between vertex-
transitive graphs and Cayley graphs, but we must also know all groups $G$ for
which the Cayley graph is Cayley graph of $G$. All results in this paper are
true not just for graphs, but also digraphs.

The fundamental tool that we will use is a “recognition theorem” for double
coset graphs that can be written as a wreath product. That is, in Theorem 3.3
we find necessary and sufficient conditions on the connection set $S$ of a
double coset graph of $G$ to be isomorphic to a wreath product of two smaller
graphs. It is known that a Cayley digraph ${\rm Cay}(A,S)$ of an abelian group
$A$ is isomorphic to a wreath product of two smaller digraphs if and only if
there exists $1<B<A$ such that $S\setminus B$ is a union of cosets of $B$.
This was shown explicitly for prime powers in [14, 18] and mentioned without
proof in [2]. Theorem 3.3 can be used to show a bijective correspondence
between the sets of double coset graphs of $G$ with a natural property and
reducible Cayley graphs of $G$ (Corollary 4.5). This correspondence gives a
more “graph theoretic” and intuitive definition (Definition 4.7) of a double
coset graph of $G$ as a quotient of a Cayley graph of $G$, and shows that
double coset graphs can be interpreted as nothing more than devices for
succinctly storing the symmetry information of some Cayley graphs of $G$.

To finish, we are able to extend the definition of generalized wreath product
digraphs to all double coset digraphs. Generalized wreath product digraphs are
a relatively new but very important family of digraphs from the point of view
of computing automorphisms groups, and previously were only defined for Cayley
digraphs of abelian groups precisely because the recognition problem of wreath
products was only solved for Cayley digraphs of abelian groups. This last
problem was the original motivation for this work.

##  2\. Digraphs as wreath products

In this section, we collect the basic definitions and results we will need.
For most, additional information as well as illustrative examples can be found
in [8].

######  Definition 2.1.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be digraphs. The wreath product of
$\Gamma_{1}$ and $\Gamma_{2}$, denoted $\Gamma_{1}\wr\Gamma_{2}$, is the
digraph with vertex set $V(\Gamma_{1})\times V(\Gamma_{2})$ and arc set

$\\{((u,v)(u,v^{\prime})):u\in V(\Gamma_{1}){\rm\ and\ }(v,v^{\prime})\in
A(\Gamma_{2})\\}\cup\\{((u,v)(u^{\prime},v^{\prime})):(u,u^{\prime})\in
A(\Gamma_{1}){\rm\ and\ }v,v^{\prime}\in V(\Gamma_{2})\\}.$

The wreath product is sometimes referred to as the lexicographic product,
graph composition, or the $\Gamma_{2}$-extension of $\Gamma_{1}$.

######  Definition 2.2.

Let $X$ be a set, $G\leq S_{X}$ be a transitive group, and $B\subseteq X$. We
call $B$ a block of $G$ if whenever $g\in G$, then $g(B)\cap B=\emptyset$ or
$B$. If $B=\\{x\\}$ for some $x\in X$ or $B=X$, then $B$ is a trivial block.

Note that if $B$ is a block of $G$, then so is $g(B)$ for every $g\in G$, and
is called a conjugate block of $B$. The set of all blocks conjugate to $B$,
denoted $\mathcal{B}$, is a partition of $X$, and is called a block system of
$G$. If $\operatorname{\mathcal{B}}$ is the set orbits of a normal subgroup of
$G$, it is called a normal block system of $G$.

######  Definition 2.3.

Let $G\leq S_{X}$ and $H\leq S_{Y}$. Define the wreath product of $G$ and $H$,
denoted $G\wr H$, to be the set of all permutations of $X\times Y$ of the form
$(x,y)\mapsto(g(x),h_{x}(y))$, where $g\in G$ and each $h_{x}\in H$.

It is straightforward to show that $G\wr H$ is a group. We will have need of a
special block system of the wreath product of two transitive permutation
groups.

######  Definition 2.4.

Let $G\leq S_{X}$ and $H\leq S_{Y}$ be transitive groups. The lexi-partition
of $G\wr H$ with respect to $H$ is the block system
$\operatorname{\mathcal{B}}=\\{\\{(x,y):y\in Y\\}:x\in X\\}$.

A transitive permutation group with a block system has an induced action on
the block system.

######  Definition 2.5.

Suppose that $G\leq S_{n}$ is a transitive group with a block system
$\operatorname{\mathcal{B}}$. Then $G$ has an induced action on
$\operatorname{\mathcal{B}}$, which we denote by
$G/\operatorname{\mathcal{B}}$. Namely, for $g\in G$, we define
$g/\operatorname{\mathcal{B}}(B)=B^{\prime}$ if and only if $g(B)=B^{\prime}$,
and set $G/\operatorname{\mathcal{B}}={\\{g/\operatorname{\mathcal{B}}:g\in
G\\}}$. We also define the fixer of $\operatorname{\mathcal{B}}$ in $G$,
denoted $\text{fix}_{G}(\operatorname{\mathcal{B}})$, to be $\\{g\in
G:g/\operatorname{\mathcal{B}}=1\\}$.

So ${\rm fix}_{G}({\mathcal{B}})$ is the kernel of the induced action of $G$
on ${\mathcal{B}}$.

######  Definition 2.6.

Let $\Gamma$ be a vertex-transitive digraph whose automorphism group contains
a transitive subgroup $G$ with a block system $\operatorname{\mathcal{B}}$.
Define the block quotient digraph of $\Gamma$ with respect to
$\operatorname{\mathcal{B}}$, denoted $\Gamma/\operatorname{\mathcal{B}}$, to
be the digraph with vertex set $\operatorname{\mathcal{B}}$ and arc set
$A(\Gamma/\operatorname{\mathcal{B}})={\\{(B,B^{\prime}):B\not=B^{\prime}\in\operatorname{\mathcal{B}}\text{
and }(u,v)\in A(\Gamma),u\in B,v\in B^{\prime}\\}.}$

So in a block quotient digraph, a block $B$ is out-adjacent to a block
$B^{\prime}$ if and only if some vertex of $B$ is out-adjacent to some vertex
of $B^{\prime}$.

The following result gives necessary and sufficient conditions to recognize
that a vertex-transitive digraph is a wreath product (but not from its
connection set). The first version of this result is by Joseph [12, Lemma
3.11]. The following is a generalization of her result, whose very similar
proof can be found in [8, Theorem 4.2.15].

######  Lemma 2.7.

Let $\Gamma$ be a vertex-transitive digraph whose automorphism group contains
a transitive subgroup $G$ that has a block system
$\operatorname{\mathcal{B}}$. Then
$\Gamma\cong\Gamma/\operatorname{\mathcal{B}}\wr\Gamma[B_{0}]$,
$B_{0}\in\operatorname{\mathcal{B}}$, if and only if whenever
$B,B^{\prime}\in\operatorname{\mathcal{B}}$ are distinct then there is an arc
$(x,x^{\prime})$ from a vertex $x\in B$ to a vertex $x^{\prime}\in B^{\prime}$
if and only if every arc of the form $(x,x^{\prime})$ with $x\in B$ and
$x^{\prime}\in B^{\prime}$ is contained in $A(\Gamma).$

The following theorem was proven in [6, Theorem 5.7], and gives the
automorphism group of the wreath product of finite vertex-transitive digraphs.

######  Theorem 2.8.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be finite vertex-transitive digraphs. If
$\Gamma=\Gamma_{1}\wr\Gamma_{2}$ and ${\rm Aut}(\Gamma)\not={\rm
Aut}(\Gamma_{1})\wr{\rm Aut}(\Gamma_{2})$, then there exist positive integers
$r>1$ and $s>1$ and vertex-transitive digraphs $\Gamma_{1}^{\prime}$ and
$\Gamma_{2}^{\prime}$ for which $\Gamma_{1}\cong\Gamma_{1}^{\prime}\wr
K_{r},\;\Gamma_{2}\cong K_{s}\wr\Gamma_{2}^{\prime}$ or
$\Gamma_{1}\cong\Gamma_{1}^{\prime}\wr\bar{K_{r}},\;\Gamma_{2}\cong\bar{K_{s}}\wr\Gamma_{2}^{\prime}$.
In either case, ${\rm Aut}(\Gamma)\cong{\rm Aut}(\Gamma_{1}^{\prime})\wr
S_{rs}\wr{\rm Aut}(\Gamma_{2}^{\prime}).$

Suppose ${\rm Aut}(\Gamma_{1}\wr\Gamma_{2})\not={\rm Aut}(\Gamma_{1})\wr{\rm
Aut}(\Gamma_{2})$ and $\Gamma_{1}\wr\Gamma_{2}$ is neither complete nor the
complement of a complete graph; that is, assume that in the statement of
Theorem 2.8, we have that $\Gamma_{1}^{\prime}$ or $\Gamma_{2}^{\prime}$ has
more than one vertex. Theorem 2.8 implies that $\Gamma_{1}\wr\Gamma_{2}$ can
be written as another wreath product of two vertex transitive digraphs whose
automorphism group is the wreath product of the automorphism groups. That is,
if $\Gamma\cong\Gamma_{1}\wr\Gamma_{2}$ with ${\rm Aut}(\Gamma)\not\cong{\rm
Aut}(\Gamma_{1})\wr{\rm Aut}(\Gamma_{2})$, then there are two nontrivial
digraphs $\Gamma_{3},\Gamma_{4}$ where $\Gamma\cong\Gamma_{3}\wr\Gamma_{4}$
with ${\rm Aut}(\Gamma)={\rm Aut}(\Gamma_{3})\wr{\rm Aut}(\Gamma_{4})$. For
example, if $\Gamma_{1}\cong\Gamma_{1}^{\prime}\wr K_{r}$ and $\Gamma_{2}\cong
K_{s}\wr\Gamma_{2}^{\prime}$, then we may take
$\Gamma_{3}=\Gamma_{1}^{\prime}$ and
$\Gamma_{4}=K_{rs}\wr\Gamma_{2}^{\prime}$, while if
$\Gamma_{1}\cong\Gamma_{1}^{\prime}\wr\bar{K_{r}}$ and
$\Gamma_{2}\cong\bar{K_{s}}\wr\Gamma_{2}^{\prime}$ then we may take
$\Gamma_{3}=\Gamma_{1}^{\prime}$ and
$\Gamma_{4}=\bar{K}_{rs}\wr\Gamma_{2}^{\prime}$.

We now give the definitions of double coset digraphs and Cayley digraphs,
after giving the definition of double cosets.

######  Definition 2.9.

Let $G$ be a group and $H,K<G$. For each $g\in G$, the set $HgK=\\{hgk:h\in
H,k\in K\\}$ is called the $(H,K)$-double coset of $g$ in $G$. If $H=K$, then
the $(H,K)$-double cosets are referred to as the double cosets of $H$ in $G$.

The $(H,K)$-double cosets of $G$ form a partition of $G$ and need not have the
same cardinality. Note that the $(\\{1\\},K)$-double cosets are the left
cosets of $K$ in $G$ and the $(H,\\{1\\})$-double cosets are just the right
cosets of $H$ in $G$. In general, $HgK$ is a union of right cosets of $H$ as
well as a union of left cosets of $K$.

Throughout the paper, we denote the set of left cosets of $H$ in $G$ by $G/H$.

######  Definition 2.10.

Let $G$ be a group, $H\leq G$, and $S\subset G$ such that $S\cap H=\emptyset$
and $HSH=S$. Define a digraph $\text{Cos}(G,H,S)$ with vertex set
$V(\text{Cos}(G,H,S))=G/H$ the set of left cosets of $H$ in $G$, and arc set
$A(\text{Cos}(G,H,S))=\\{(gH,gsH):g\in G{\rm\ and\ }s\in S\\}$. The digraph
$\text{Cos}(G,H,S)$ is called the double coset digraph of $G$ with connection
set $S$ (or $HSH$).

It is customary to impose on $H$ the condition that it is core-free in $G$.
That is, that it contains no nontrivial normal subgroups of $G$. This ensures
that the action of $G$ on the left cosets of $H$ in $G$ is faithful, which is
certainly a condition one would want if one were, say, drawing a particular
double coset digraph. We will NOT follow this custom - several of the
applications of our main results are actually false if this convention is
followed. The custom also, inconveniently for us, means that abelian groups
$A$, for example, have NO double coset digraphs of $A$ that are not Cayley
digraphs of $A$ as the only core-free subgroup of an abelian group is the
trivial group.

It is also customary to insist that $S\cap H=\emptyset$, as this means that
double coset digraphs do not have loops. In some sense, it does not matter at
all whether or not one allows loops. In fact, the results in the next section
are completely independent of this choice, although the condition that $HSH=S$
forces $S\cap H=\emptyset$ or $S\cap H=H$, and so each vertex would have $|H|$
loops at a vertex (to obtain $r<|H|$ loops one would insist that $H(S\setminus
H)H=S\setminus H$, and then insist that $|H\cap S|=r$). The results in Section
4 though, have statements that do depend upon $S\cap H=\emptyset$. By this, we
mean that if one allowed loops, those results are not true “as is”, but it
would be a simple matter to modify them appropriately. We follow this custom
for two reasons. One is the custom (and indeed this condition goes back to
Sabidussi’s original work on double coset graphs). The other is that the
results in Section 4 are easier to state in this form.

######  Definition 2.11.

Let $G$ be a group and $S\subset G$ such that $1\not\in S$. Define a Cayley
digraph of $G$, denoted $\text{Cay}(G,S)$, to be the digraph with vertex set
$V(\text{Cay}(G,S))=G$ and arc set $A(\text{Cay}(G,S))=\\{(g,gs):g\in\nobreak
G,s\in S\\}.$ We call $S$ the connection set of $\text{Cay}(G,S)$.

So a Cayley digraph of $G$ is simply the special case of a double coset
digraph of $G$ with $H=1$.

##  3\. Double coset digraphs as wreath products

We begin with a result which is probably known by many readers, but which we
will state and prove anyway due to its importance.

######  Lemma 3.1.

Let $G$ be a group, $H\leq G$, and let $G$ act on $G/H$ by left
multiplication. Then $G$ acts transitively on $G/H$, and any block system
${\mathcal{B}}$ of this action has blocks the set of left cosets of $H$
contained in some left coset of a subgroup $H\leq K\leq G$.

###### Proof.

That $G$ is transitive on $G/H$ is well known. By [4, Theorem 1.5A], there is
$K\geq H$ such that the block $B\in{\mathcal{B}}$ that contains $H$ is the
orbit of $K$ that contains $H$. Then $B$ is the set of all left cosets of $H$
contained in $K$. Any block conjugate to $B$ is simply of the form $gB$ for
some $g\in G$, and so is the set of left cosets of $H$ contained in $gK$. ∎

######  Lemma 3.2.

Let $G$ be a group, $H\leq G$, and $S\subset G$ such that $S\cap H=\emptyset$
and $S=HSH$. Suppose $\Gamma={\rm Cos}(G,H,S)\cong\Gamma_{1}\wr\Gamma_{2}$ for
$\Gamma_{1}$ and $\Gamma_{2}$ vertex-transitive digraphs with at least two
vertices. Let ${\mathcal{B}}$ be the lexi-partition of ${\rm
Aut}(\Gamma_{1})\wr{\rm Aut}(\Gamma_{2})$ with respect to ${\rm
Aut}(\Gamma_{2})$. If ${\mathcal{B}}$ is the set of left cosets of $K$ in $G$,
then $S\setminus K=K(S\setminus K)K$.

###### Proof.

By Lemma 3.1, ${\mathcal{B}}$ is the set of left cosets of some subgroup
$H\leq K\leq G$. Suppose $a\in S\setminus K$. Let $B=aK\in{\mathcal{B}}$ (here
$aK$ is viewed as a union of left cosets of $H$ in $G$). Then $H\not\subseteq
B$ as $H\leq K$. Since there is an arc from $H$ to $aH$ if and only if there
is an arc from $H$ to every left coset of $H$ contained in $B$ as
$\Gamma=\Gamma_{1}\wr\Gamma_{2}$ and ${\mathcal{B}}$ is the lexi-partition
with respect to ${\rm Aut}(\Gamma_{2})$, we conclude that $aK\subseteq S=HSH$,
and so $H(S\setminus K)H$ is a union of left cosets of $K$ in $G$. Then, for
every $k,k^{\prime}\in K$, we have $kH,k^{\prime}H\subseteq K$, and
$(kH,ak^{\prime}H)\in A(\text{Cos}(G,H,S))$. Hence $k^{-1}ak^{\prime}\in HSH$
for every $k,k^{\prime}\in K$. So $KaK\subseteq HSH$. As $a\not\in K$,
$k^{-1}ak^{\prime}\in H(S\setminus K)H$. Thus, $H(S\setminus K)H$ is a union
of double cosets of $K$ in $G$. ∎

With the next result, we are able to recognize double coset digraphs that are
isomorphic to nontrivial wreath products from their connection sets.

######  Theorem 3.3.

Let $G$ be a group, $H\leq G$, and $S\subset G$ such that $S\cap H=\emptyset$
and $HSH=S$. The double coset digraph $\Gamma={\rm Cos}(G,H,S)$ is isomorphic
to a nontrivial wreath product of two vertex-transitive digraphs of smaller
order if and only if there exists $H<K<G$ such that $H(S\setminus K)H$ is a
union of double cosets of $K$ in $G$. If such a $H<K<G$ exists and
$\mathcal{B}$ is the set of left cosets of $K$ in $G$, then

(3.1) $\displaystyle{\rm
Cos}(G,H,S)\cong\Gamma/\mathcal{B}\wr\Gamma[K]\cong{\rm Cos}(G,K,S\setminus
K)\wr{\rm Cos}(K,H,(S\cap K)).$

Additionally, if $\Gamma$ is neither complete nor the complement of a complete
graph and $K$ is chosen to be maximal in $G$ with the above properties, then

(3.2) $\displaystyle{\rm Aut}({\rm Cos}(G,H,S))\cong{\rm Aut}({\rm
Cos}(G,K,S\setminus K))\wr{\rm Aut}({\rm Cos}(K,H,(S\cap K))).$

###### Proof.

Suppose $\Gamma=\Gamma_{1}\wr\Gamma_{2}$, where both $\Gamma_{1}$ and
$\Gamma_{2}$ are nontrivial and not $\Gamma$. Then the lexi-partition
${\mathcal{B}}$ of ${\rm Aut}(\Gamma_{1})\wr{\rm Aut}(\Gamma_{2})$ with
respect to ${\rm Aut}(\Gamma_{2})$ is a block system of ${\rm
Aut}(\Gamma_{1})\wr{\rm Aut}(\Gamma_{2})\leq{\rm Aut}(\Gamma)$. The result
follows by Lemma 3.2.

Conversely suppose $H<K<G$ such that $H(S\setminus K)H$ is a union of double
cosets of $K$ in $G$. We now show
$\Gamma\cong\Gamma/{\mathcal{B}}\wr\Gamma[K]$. This will complete the “if and
only if” part of the proof as well as the first part of Equation 3.1. Suppose
$(ak_{1}H,bk_{2}H)\in A(\Gamma)$ and $ak_{1}H$ and $bk_{2}H$ are not contained
in the same left coset of $K$ in $G$, where $k_{1},k_{2}\in K$. This gives
$k_{1}^{-1}a^{-1}bk_{2}\not\in K$. Then $k_{1}^{-1}(a^{-1}b)k_{2}\in
K(S\setminus K)K=H(S\setminus K)H$, with the last equality holding as
$H(S\setminus K)H$ is a union of double cosets of $K$ in $G$. Thus
$K(a^{-1}b)K\subseteq K(S\setminus K)K$ and $(ak^{\prime}H,bkH)\in A(\Gamma)$
for all $k,k^{\prime}\in K$. This means that whenever
$B,B^{\prime}\in\operatorname{\mathcal{B}}$ are distinct then there is an arc
$(x,x^{\prime})$ from a vertex $x\in B$ to a vertex $x^{\prime}\in B^{\prime}$
if and only if every arc of the form $(x,x^{\prime})$ with $x\in B$ and
$x^{\prime}\in B^{\prime}$ is contained in $A(\Gamma).$ By Lemma 2.7,
$\Gamma\cong\Gamma/\mathcal{B}\wr\Gamma[K]$.

We next show $\Gamma/{\mathcal{B}}={\rm Cos}(G,K,S\setminus K)$. The digraph
${\rm Cos}(G,K,S\setminus K)$ is a well-defined double coset digraph as
$S\setminus K$ is a union of double cosets of $K$. Let $a,b\in G$ such that
$a^{-1}b\not\in K$ (or $a^{-1}b\in S\setminus K$). Then $(aK,bK)\in
A(\Gamma/{\mathcal{B}})$ if and only if there is $a_{1},b_{1}\in G$ such that
$a_{1}H\subseteq aK$, $b_{1}H\subseteq bK$, and $(a_{1}H,b_{1}H)\in
A(\Gamma)$. This occurs if and only if $a_{1}^{-1}b_{1}H\subseteq S$. As
$S\setminus K$ is a union of double cosets of $K$ and
$a_{1}^{-1}b_{1}^{-1}H\subseteq a^{-1}bK$, we see $a_{1}^{-1}b_{1}K\in
S\setminus K$ (viewing $S\setminus K$ as a union of left cosets of $K$ in
$G$). Thus $(aK,bK)\in A(\Gamma/{\mathcal{B}})$ if and only if $a^{-1}bK\in
S\setminus K$, which occurs if and only if $(aK,bK)\in A({\rm
Cos}(G,K,S\setminus K))$. So $\Gamma/{\mathcal{B}}={\rm Cos}(G,K,S\setminus
K)$.

As $K$ is a left coset of itself, $K\in\operatorname{\mathcal{B}}$. Then ${\rm
Cos}(G,H,S)[K]={\rm Cos}(K,H,K\cap S)$, and so $\Gamma[K]={\rm Cos}(K,H,S\cap
K)$. This completes the proof of Equation 3.1.

It now only remains to show that if $\Gamma$ is neither complete nor the
complement of a complete graph and $K$ is maximal with the property that
$H(S\setminus K)H$ is a union of double cosets of $K$, then Equation (3.2)
holds. Suppose otherwise. Then ${\rm Cos}(G,K,S\setminus K)$ can be written as
a nontrivial wreath product by Theorem 2.8 and the comment following it. By
what we have already shown, there is some $K<K^{\prime}<G$ such that
$S\setminus K^{\prime}$ is a union of double cosets of $K^{\prime}$ in $G$,
contradicting the maximality of $K$. ∎

If one follows the convention that $H$ is core-free in $G$ for double coset
digraphs, then with $N={\rm core}_{G}(H)$, ${\mathcal{C}}$ the set of left
cosets of $K/N$ in $G/N$, and $T=\\{(sN)(K/N):s\in H(S\setminus K)H\\}$,
Equation 3.2 becomes

$\displaystyle{\rm Cos}(G/N,H/N,\\{sN:s\in S\\})$ $\displaystyle\cong$
$\displaystyle\Gamma/\mathcal{C}\wr\Gamma[K/N]$ $\displaystyle\cong$
$\displaystyle{\rm Cos}(G/N,K/N,T)\wr{\rm Cos}(K/N,H/N,(S\cap K)N).$

When $H=\\{1_{G}\\}$, ${\rm Cos}(G,H,S)\cong{\rm Cay}(G,S)$ and we have a
special case of Theorem 3.3 for Cayley digraphs.

######  Corollary 3.4.

Let $G$ be a group and $S\subset G$ such that $1\not\in S$. The Cayley digraph
$\Gamma={\rm Cay}(G,S)$ is isomorphic to a nontrivial wreath product of two
vertex-transitive digraphs of smaller order if and only if there exists
$1<K<G$ such that $S\setminus K$ is a union of double cosets of $K$ in $G$. If
such a $1<K<G$ exists and $\mathcal{B}$ is the set of left cosets of $K$ in
$G$, then

${\rm Cay}(G,S)\cong\Gamma/\mathcal{B}\wr\Gamma[K]\cong{\rm
Cos}(G,K,S\setminus K)\wr{\rm Cay}(K,S\cap K).$

Additionally, if $\Gamma$ is neither complete nor the complement of a complete
graph and $K$ is chosen to be maximal in $G$ with the above properties, then

${\rm Aut}({\rm Cay}(G,S))\cong{\rm Aut}({\rm Cos}(G,K,S\setminus K))\wr{\rm
Aut}({\rm Cay}(K,S\cap K)).$

We note that in [3] it was shown that for the special case of Cayley graphs,
we only need that $SH=S$. They also mention that for graphs the condition that
$SH=S$ and $HSH=S$ are equivalent. This is easy to see as if $SH=S$ and
$S^{-1}=S$, then $SH=S$ implies that $(SH)^{-1}=H^{-1}S^{-1}=HS=H(SH)=HSH$.
If, in the previous result, we have $K\triangleleft G$, then we get a slightly
nicer sufficient (but not necessary) condition for a Cayley graph of $G$ to be
a wreath product.

######  Corollary 3.5.

Let $G$ be a group and $S\subset G$ such that $1\not\in S$. The Cayley digraph
$\Gamma={\rm Cay}(G,S)$ is isomorphic to a nontrivial wreath product of two
vertex-transitive digraphs of smaller order if there exists $1<K\triangleleft
G$ such that $S\setminus K$ is a union of cosets of $K$ in $G$. In this case,
if ${\mathcal{B}}$ is the set of cosets of $K$ in $G$, then

${\rm Cay}(G,S)\cong\Gamma/\operatorname{\mathcal{B}}\wr\Gamma[K]\cong{\rm
Cay}(G/K,S_{1})\wr{\rm Cay}(K,S_{2})$

where $S_{1}$ is the set of cosets of $K$ contained in $S$ and $S_{2}=K\cap
S.$ Additionally, if $\Gamma$ is not complete nor the complement of a complete
graph and $K$ is chosen to be maximal in $G$ with the above properties, then

${\rm Aut}({\rm Cay}(G,S))\cong{\rm Aut}({\rm Cay}(G/K,S_{1}))\wr{\rm
Aut}({\rm Cay}(K,S_{2}).$

###### Proof.

As $K\triangleleft G$, $G/K$ is a group of order $[G:K]$. Also, ${\rm
Stab}_{K}(1)=1$, and so $K$ is semiregular of order, say, $k$. Let $n=|G|$.
Then $[G:K]=n/k$ and ${\rm fix}_{G}({\mathcal{B}})=\\{k_{L}:k\in K\\}$ has
order $k$. As $G_{L}/{\mathcal{B}}$ is transitive of order $n/k$, we see
$G_{L}/{\mathcal{B}}=(G/K)_{L}$ is regular. Hence $\Gamma/{\mathcal{B}}$ is a
Cayley digraph of $G/K$. As $G\setminus K$ is a union of left cosets of $K$ in
$G$ (as it is a union of double cosets of $K$), we see that
$\Gamma/{\mathcal{B}}$ has connection set $S_{1}$. The rest follows by
Corollary 3.4. ∎

In the case when all subgroups of $G$ are normal, the above sufficient
condition is also necessary. Groups in which every subgroup are normal are
called Dedekind groups. Obviously, abelian groups are Dedekind groups, and
non-abelian Dedekind groups are called the Hamilton groups. Hamilton groups
have the form $G=Q_{8}\times B\times D$ [11, Theorem 12.5.4], where $Q_{8}$ is
the quaternion group of order $8$, $B$ is an elementary abelian $2$-group, and
$D$ is a finite abelian group of odd order. This result also generalizes the
known result mentioned earlier that Cayley digraphs of abelian groups can be
written as nontrivial wreath products of two digraphs of smaller order if and
only if its connection set is a union of cosets of some subgroup.

##  4\. Applications to double coset digraphs

Sabidussi has shown that there is a strong relationship between Cayley graphs
and double coset graphs. He showed in [21, Theorem 4] that ${\rm
Cos}(G,H,S)\wr\bar{K}_{n}$, where $n=|H|$, is isomorphic to a Cayley graph
$\Gamma$ of $G$ ($\Gamma$ has connection set a union of left cosets of $H$ in
$G$). He also showed in [21, Theorem 2] that every double coset graph of $G$
is the quotient of a Cayley graph of $G$ with connection set $S$ by the
partition ${\mathcal{P}}$ of $G$ given by the left cosets of a subgroup of $G$
that is disjoint from $S$. Examining the proofs of these two results (but not
the statements), it turns out the two Cayley graphs Sabidussi constructs in
[21, Theorems 2 and 4] are equal.

In the first part of this section, we more or less continue where Sabidussi
left off, and tighten and make clearer the relationship between Cayley
digraphs of $G$ and double coset digraphs of $G$, culminating in a new, graph
theoretic definition of a double coset digraph of $G$ in Definition 4.7. For
the rest of this section, we exploit Theorem 3.3, which intuitively allows for
the use of a stronger quotient than the block quotient given in Definition
2.6. The block quotient, which Sabidussi also used, maps arcs of $\Gamma$ to
arcs of $\Gamma/{\mathcal{P}}$. The stronger quotient maps arcs of $\Gamma$ to
arcs of $\Gamma/{\mathcal{P}}$ and non-arcs of $\Gamma$ to non-arcs of
$\Gamma/{\mathcal{P}}$. This allows more combinatorial and symmetry
information to lift from $\Gamma/{\mathcal{B}}$ to $\Gamma$ and more to
project from $\Gamma$ to $\Gamma/{\mathcal{P}}$. This is what we will exploit
in the latter part of this section.

While our definition of a double coset digraph is more or less the usual one,
it might be better, for the purposes of this section, to think of first fixing
the group $G$, then choosing $S$, and then letting $H\leq G$ such that
$S=HSH$. The next lemma shows that such a subgroup always exists, even if it
must be $H=1$, in which case a double coset digraph is isomorphic to a Cayley
digraph. In this manner a double coset digraph of $G$ exists for every $S$,
but of course not all of these digraphs will have the same number of vertices.

######  Lemma 4.1.

Let $G$ be a group, $S\subseteq G$, and $K=\\{g\in G:gS=Sg=S\\}$. Then $K\leq
G$ and $K$ is the maximum subgroup of $G$ for which $S=KSK$.

###### Proof.

The only part of showing $K\leq G$ that is not completely straightforward is
showing that if $gS=Sg=S$, then $g^{-1}S=Sg^{-1}=S$. As $1\cdot S=S\cdot 1=S$,
$S=g^{-1}g\cdot S=g^{-1}S$ and $S=S\cdot gg^{-1}=Sg^{-1}$. Hence $K\leq G$. To
see $K$ is the maximum subgroup of $G$ for which $S=KSK$, if $L\leq G$ such
that $S=LSL$, then $gS=Sg=S$ for all $g\in L$, and hence $L\leq K$. ∎

We will need some additional terms.

######  Definition 4.2.

Let $\Gamma$ be a digraph. Define an equivalence relation $R$ on $V(\Gamma)$
by $u\ R\ v$ if and only if the out- and in-neighbors of $u$ and $v$ are the
same. Then $R$ is an equivalence relation on $V(\Gamma)$. We say $\Gamma$ is
irreducible if the equivalence classes of $R$ are singletons, and reducible
otherwise.

The equivalence relation in Definition 4.2 was introduced for graphs by
Sabidussi [20, Definition 3], and independently rediscovered by Kotlov and
Lovász [13], who call $u$ and $v$ twins, and Wilson [22], who calls reducible
graphs unworthy. It is easy to see that a vertex-transitive digraph $\Gamma$
is reducible if and only if it can be written as a wreath product
$\Gamma_{1}\wr\bar{K}_{n}$ for some positive integer $n\geq 2$. Sabidussi
observed in [21] that $R$ is a $G$-congruence for transitive groups $G\leq{\rm
Aut}(\Gamma)$.

######  Definition 4.3.

Let $G$ be a group. Define ${\rm Reducible}(G)$ to be the set of all Cayley
digraphs of $G$ that are reducible. That is, ${\rm Reducible}(G)=\\{{\rm
Cay}(G,S):{\rm Cay}(G,S)\cong\Gamma\wr\bar{K}_{t},\Gamma{\rm\ a\ digraph,\
}t\geq 2\\}$. Let ${\rm Cos}(G)$ be the set of all loopless double coset
digraphs of $G$ that are not Cayley digraphs of $G$. That is,

${\rm Cos}(G)=\\{{\rm Cos}(G,H,S):1<H\leq G,H\cap S=\emptyset,{\rm\ and\
}S=HSH\\}.$

The condition that a double coset digraph ${\rm Cos}(G,H,S)$ is loopless means
that $H\cap S=\emptyset$. We will implicitly use the easy to show fact that if
$H\leq K$, $KSK=S$ and $H\cap S=\emptyset$, then $K\cap S=\emptyset$. This
follows from the also easy to show fact that if $KSK=S$, then $K\cap
S=\emptyset$ or $K\cap S=K$. Note that the digraphs in ${\rm Cos}(G)$ need not
all have the same order. If we followed the convention that $H$ is core-free
in $G$, the next result would not be true for abelian groups, for example, as
the only core-free subgroup of an abelian group is trivial.

######  Theorem 4.4.

Let $G$ be a group. Define $\gamma\colon{\rm Cos}(G)\to{\rm Reducible}(G)$ by
$\gamma({\rm Cos}(G,H,S))={\rm Cay}(G,S)$. Then $\gamma$ is onto, and
$\gamma({\rm Cos}(G,H_{1},S_{1}))=\gamma({\rm Cos}(G,H_{2},S_{2}))$ if and
only if $S_{1}=S_{2}$ and
${\langle}H_{1},H_{2}{\rangle}S{\langle}H_{1},H_{2}{\rangle}=S$.

###### Proof.

Note that $\gamma$ indeed maps ${\rm Cos}(G)$ to ${\rm Reducible}(G)$ as if
${\rm Cos}(G,H,S)\in{\rm Cos}(G)$, then $H\cap S=\emptyset$ and $S=HSH$. By
Theorem 3.3 ${\rm Cay}(G,S)\cong{\rm Cos}(G,H,S)\wr\bar{K}_{h}$ where $h=|H|$.
Thus ${\rm Cay}(G,S)$ is reducible, and the image of $\gamma$ is contained in
${\rm Reducible}(G)$. To see $\gamma$ is onto, let ${\rm Cay}(G,S)\in{\rm
Reducible}(G)$. Then ${\rm Cay}(G,S)$ $\cong\Gamma_{1}\wr\bar{K}_{t}$, where
$\Gamma_{1}$ is a digraph and $t\geq 2$. Choose $\Gamma_{1}$ and $t$ so that
${\rm Aut}({\rm Cay}(G,S))\cong{\rm Aut}(\Gamma_{1})\wr{\rm
Aut}(\bar{K}_{t})$, in which case ${\rm Aut}({\rm Cay}(G,S))\cong{\rm
Aut}(\Gamma_{1})\wr S_{t}$. Then ${\rm Aut}({\rm Cay}(G,S))$ has the lexi-
partition ${\mathcal{B}}$ with respect to $S_{t}$ as a block system with
blocks of size $t$. As $G_{L}\leq{\rm Aut}({\rm Cay}(G,S))$, the blocks of
${\mathcal{B}}$ are the left cosets of some subgroup $K$ of $G$. As ${\rm
Cay}(G,S)=\Gamma_{1}\wr\bar{K}_{t}$ and ${\mathcal{B}}$ is the lexi-partition,
${\rm Cay}(G,S)[gK]\cong\bar{K}_{t}$ for every $g\in G$ and so $S\cap
K=\emptyset$. By Lemma 3.2, $S=K(S\setminus K)K=KSK$. Then ${\rm
Cos}(G,K,S)\in{\rm Cos}(G)$ and $\gamma({\rm Cos}(G,K,S))={\rm Cay}(G,S)$.
Thus $\gamma$ is onto.

To see $\gamma({\rm Cos}(G,H_{1},S_{1}))=\gamma({\rm Cos}(G,H_{2},S_{2}))$ if
and only if $S_{1}=S_{2}$ and
${\langle}H_{1},H_{2}{\rangle}S{\langle}H_{1},H_{2}{\rangle}=S$, let ${\rm
Cos}(G,H_{1},S_{1}),{\rm Cos}(G,H_{2},S_{2})\in{\rm Cos}(G)$. Suppose
$\gamma({\rm Cos}(G,H_{1},S_{1}))=\gamma({\rm Cos}(G,H_{2},S_{2}))$. Then
${\rm Cay}(G,S_{1})={\rm Cay}(G,S_{2})$ and as $S_{1}$ and $S_{2}$ are both
the neighbors of $1_{G}$, $S_{1}=S_{2}$. Set $S=S_{1}=S_{2}$. Then
$H_{1}SH_{1}=S$, $H_{2}SH_{2}=S$, and it is then easy to see that
${\langle}H_{1},H_{2}{\rangle}S{\langle}H_{1},H_{2}{\rangle}=S$. The converse
is similarly difficult. ∎

As, by Lemma 4.1, for every group $G$ and $S\subset G$ there is a maximal (so
unique) subgroup $K$ with $KSK=S$, we may restrict the domain of $\gamma$ to
these unique subgroups $K$, and obtain a bijection.

######  Corollary 4.5.

Let $G$ be a group. Let ${\rm Cos}_{U}(G)$ be the set of all loopless double
coset digraphs of $G$ with connection set $S$ such that $K$ is chosen to be
maximal with $KSK=S$. That is, ${\rm Cos}_{U}(G)=\\{{\rm Cos}(G,K,S):K\leq
G,S=KSK{\rm\ and\ }g_{1}Sg_{2}\not=S{\rm\ for\ some\ }g_{1},g_{2}\in
G\setminus K\\}$. Define $\gamma_{U}\colon{\rm Cos}_{U}(G)\to{\rm
Reducible}(G)$ by $\gamma_{U}({\rm Cos}(G,H,S))={\rm Cay}(G,S)$. Then
$\gamma_{U}$ is a bijection.

######  Theorem 4.6.

Let $G$ be a group, $H\leq G$, and $S\subset G$ such that $S\cap H=\emptyset$.
Then ${\rm Cos}(G,H,S)$ is a well-defined double coset digraph of $G$ if and
only if the set of equivalence classes of $R$ in ${\rm Cay}(G,S)$ is refined
by $G/H$. Additionally, if ${\rm Cos}(G,H,S)$ is a well-defined double coset
digraph of $G$, then ${\rm Cos}(G,H,S)={\rm Cay}(G,S)/(G/H)$.

###### Proof.

If the set of equivalence classes of $R$ in ${\rm Cay}(G,S)$ is refined by
$G/H$, then ${\rm Cay}(G,S)$ can be written as a wreath product
$\Gamma_{1}\wr\Gamma_{2}$, and $\Gamma_{2}$ is the empty digraph on $H$. Then
there is a maximum supergraph $\Gamma_{2}^{\prime}$ of $\Gamma_{2}$ that is an
empty graph and ${\rm Cay}(G,S)\cong\Gamma_{1}^{\prime}\wr\Gamma_{2}^{\prime}$
for some $\Gamma_{1}^{\prime}$. As $\Gamma_{1}^{\prime}\wr\Gamma_{2}^{\prime}$
is isomorphic to a Cayley digraph, we may assume without loss of generality
that ${\rm Aut}(\Gamma_{1}^{\prime}\wr\Gamma_{2}^{\prime})$ contains $G_{L}$.
As $\Gamma_{2}^{\prime}$ is maximum, $\Gamma_{1}^{\prime}$ is irreducible so
${\rm Aut}(\Gamma_{1}^{\prime}\wr\Gamma_{2}^{\prime})\cong{\rm
Aut}(\Gamma_{1}^{\prime})\wr{\rm Aut}(\Gamma_{2}^{\prime})$ by Theorem 2.8. As
$G_{L}\leq{\rm Aut}(\Gamma_{1}^{\prime}\wr\Gamma_{2}^{\prime})$, this gives
that the lexi-partition of ${\rm
Aut}(\Gamma_{1}^{\prime}\wr\Gamma_{2}^{\prime})$ with respect to ${\rm
Aut}(\Gamma_{2}^{\prime})$ is the set of left cosets of a supergroup $K$ of
$H$, and as $\Gamma_{2}^{\prime}$ is a supergraph of $\Gamma_{2}$, $H\leq K$.
As $\Gamma_{2}^{\prime}$ was chosen to be maximum, $K$ is the maximum subgroup
of $G$ for which $\Gamma_{2}^{\prime}$ can be chosen to have vertex set a
subgroup of $G$. Applying $\gamma_{U}^{-1}$ as defined in Corollary 4.5, we
see $\gamma_{U}^{-1}({\rm Cay}(G,S))={\rm Cos}(G,H,S)$ and $S=KSK$. So $S=HSH$
and ${\rm Cos}(G,H,S)$ is a well-defined double coset digraph of $G$.

If ${\rm Cos}(G,H,S)$ is a well-defined double coset digraph, then by
definition, $S=HSH$ and so ${\rm Cay}(G,S)$ is reducible by Corollary 3.4.
Also, ${\rm Cay}(G,S)\cong({\rm Cay}(G,S)/(G/H))\wr\Gamma[H]$. As $S\cap
H=\emptyset$, $\Gamma[H]$ has no arcs. This completes the if and only if
statement of the result. To finish, simply observe ${\rm
Cay}(G,S)/(G/H)\cong{\rm Cos}(G,H,S)$. ∎

As Theorem 4.6 is an “if and only if” it gives an alternative definition of a
double coset digraph as follows:

######  Definition 4.7.

Let $G$ be a group and $S\subset G$ such that ${\rm Cay}(G,S)$ is reducible
with the equivalence classes of $R$ the left cosets of $K\leq G$. Let $H\leq
K$. Define ${\rm Cos}(G,H,S)$ to be the digraph ${\rm Cay}(G,S)/(G/H)$.

Let $G$ be a group, $1<H<G$, and $S\subset G$. Theorem 4.6 also gives an
alternative way of computationally checking whether $S$ is a union of double
cosets of $H$. If $S$ is a union of double cosets of $H$, then Theorem 4.6
gives that ${\rm Cay}(G,S)$ is reducible. This means that the equivalence
classes of $R$ are not singleton sets. Thus one only need check if, say,
$1_{G}$ has the same set of in- and out-neighbors as some other vertex in
${\rm Cay}(G,S)$.

While this method of determining whether a subset $S\subset G$ defines a
double coset digraph, once one has established that ${\rm Cos}(G,H,S)$ is well
defined (even by checking $S=HSH$), the maximum $K$ for which $S=KSK$ is
simply the equivalence class of $R$ which contains $1_{G}$. From a group
theoretic point of view, it is also easy to calculate $K$, as Lemma 4.1 shows.

The next result generalizes [21, Theorem 4], which states that given a double
coset digraph $\Gamma={\rm Cos}(G,H,S)$ of a group $G$, there is a “multiple”
(this is Sabidussi’s terminology) of $\Gamma$ that is a Cayley digraph of $G$.
The result gives the double coset digraphs $\Gamma$ of $G$ for which ${\rm
Cay}(G,S)$ is a “multiple” of $\Gamma$.

######  Theorem 4.8.

Let $G$ be a group, $S\subset G$, and $K\leq G$ maximal such that $S=KSK$.
Assume $S\cap K=\emptyset$. Let $M\leq K$, and $n_{M}=|M|$. Then

${\rm Cos}(G,M,S)\wr\bar{K}_{n_{M}}\cong({\rm
Cay}(G,S)/(G/M))\wr\bar{K}_{n_{M}}\cong{\rm Cay}(G,S).$

###### Proof.

First observe that as $M\leq K$ and $S=KSK$, we have $S=MSM$. So ${\rm
Cos}(G,M,S)$ is well-defined. We apply Theorem 3.3 with $H$ of that result the
subgroup $\\{1_{G}\\}$, and $K$ of that result $M$ of this result. This gives

$\displaystyle{\rm Cos}(G,\\{1_{G}\\},S)$ $\displaystyle=$ $\displaystyle{\rm
Cay}(G,S)\cong{\rm Cos}(G,M,S\setminus M)\wr({\rm Cay}(G,S)[M])$
$\displaystyle\cong$ $\displaystyle{\rm Cay}(G,S)/(G/M)\wr({\rm
Cay}(G,S)[M]).$

As ${\rm Cay}(G,S)$ is loopless and $S=MSM$, $1_{G}\not\in S$ and so $M\cap
S=\emptyset$. Then ${\rm Cay}(G,S)[M]\cong\bar{K}_{n_{M}}$, and the result
follows. ∎

We now give the relationship between the automorphism groups of ${\rm
Cay}(G,S)$ and ${\rm Cos}(G,H,S)$. Determining the automorphism group of a
vertex-transitive digraph is perhaps the most fundamental problem regarding
vertex-transitive digraphs. Corollary 3.4 shows that ${\rm Aut}({\rm
Cay}(G,S))$ can be determined from ${\rm Aut}({\rm Cos}(G,H,S))$, and the next
result shows ${\rm Aut}({\rm Cos}(G,H,S))$ can be obtained from ${\rm
Aut}({\rm Cay}(G,S))$. So the problem of determining the automorphism groups
of double coset digraphs of $G$ is equivalent to the problem of determining
the automorphism groups of Cayley digraphs of $G$! As every vertex-transitive
digraph is isomorphic to a double coset digraph [21, Theorem 2], the problem
of determining the automorphism group of vertex-transitive digraphs is
equivalent to the problem of finding the automorphism groups of Cayley
digraphs. We need one more idea.

######  Definition 4.9.

Let $G\leq S_{n}$ be transitive with block systems ${\mathcal{B}}$ and
${\mathcal{C}}$. We write ${\mathcal{B}}\preceq{\mathcal{C}}$ if every block
of ${\mathcal{C}}$ is a union of blocks of ${\mathcal{B}}$, and say
${\mathcal{B}}$ refines ${\mathcal{C}}$.

######  Corollary 4.10.

Let $G$ be a group, $H\leq G$, and $S\subset G$ such that $S=HSH$ and $S\cap
H=\emptyset$. If $H\leq K$ is chosen to be maximal such that $S=KSK$,
${\mathcal{B}}$ is the set of left cosets of $K$ in $G$, and $n=[K:H]$, then

${\rm Aut}({\rm Cos}(G,H,S))\cong({\rm Aut}({\rm Cay}(G,S))/{\mathcal{B}})\wr
S_{n}.$

###### Proof.

By Theorem 4.8 we have

${\rm Cos}(G,K,S)\wr\bar{K}_{|K|}\cong({\rm
Cay}(G,S)/{\mathcal{B}})\wr\bar{K}_{|K|}\cong{\rm Cay}(G,S)$

and

${\rm Cos}(G,H,S)\wr\bar{K}_{|H|}\cong{\rm Cay}(G,S).$

As ${\rm Cay}(G,S)[K]=\bar{K}_{|K|}$ and choice of $K$, by Corollary 3.4, we
know that

${\rm Aut}({\rm Cay}(G,S))\cong{\rm Aut}({\rm Cos}(G,K,S))\wr S_{|K|}.$

Hence ${\rm Aut}({\rm Cos}(G,K,S))={\rm Aut}({\rm Cay}(G,S))/{\mathcal{B}}$.
Let ${\mathcal{C}}$ be the set of left cosets of $H$ in $G$, and $A\leq{\rm
Aut}({\rm Cay}(G,S))$ be maximal that has ${\mathcal{C}}$ as a block system.
Then $A={\rm Aut}({\rm Cos}(G,K,S))\wr S_{n}\wr S_{|H|}$. As ${\rm
Cos}(G,H,S)\wr\bar{K}_{|H|}\cong{\rm Cay}(G,S)$ and ${\rm Aut}({\rm
Cos}(G,K,S))={\rm Aut}({\rm Cay}(G,S))/{\mathcal{B}}$, we have

${\rm Aut}({\rm Cos}(G,H,S))=A/{\mathcal{C}}={\rm Aut}({\rm Cos}(G,K,S))\wr
S_{n}=({\rm Aut}({\rm Cay}(G,S))/{\mathcal{B}})\wr S_{n}.\qed$

######  Corollary 4.11.

Let $G$ be a group, $H\leq G$, and $S\subset G$ such that $S=HSH$ and $S\cap
H=\emptyset$. If $H\leq K$ is chosen to be maximal such that $S=KSK$,
${\mathcal{C}}$ is the set of left cosets of $H$ in $G$, and $k=|K|$, then

${\rm Aut}({\rm Cay}(G,H,S))\cong({\rm Aut}({\rm
Cos}(G,H,S))/({\mathcal{B}}/{\mathcal{C}}))\wr S_{k}.$

###### Proof.

Let ${\mathcal{B}}$ be the set of left cosets of $K$ in $G$. As $K$ is chosen
to be as large as possible, ${\rm Cay}(G,S)/{\mathcal{B}}$ is irreducible.
Hence ${\rm Aut}({\rm Cay}(G,S))=({\rm Aut}({\rm Cay}(G,S)/{\mathcal{B}})\wr
S_{k}$. As ${\mathcal{C}}$ is a refinement of ${\mathcal{B}}$ as $H\leq K$,
and the vertex set of ${\rm Cos}(G,H,S)$ is the set of left cosets of $H$ in
$G$,

${\rm Cos}(G,H,S)/({\mathcal{B}}/{\mathcal{C}})\cong{\rm
Cos}(G,H,S)/{\mathcal{B}}.$

∎

Our next goal is to show that the isomorphism problem can be solved for all
double coset digraphs of $G$ if and only if it can be solved for the
corresponding Cayley digraphs of $G$. We will need a preliminary lemma.

######  Lemma 4.12.

Let $G$ be a group, $H_{i}\leq K_{i}\leq G$ such that $|H_{1}|=|H_{2}|$ and
$|K_{1}|=|K_{2}|$, and $S_{i}\subset G$ such that $K_{i}\cap S_{i}=\emptyset$
and $K_{i}S_{i}K_{i}=S_{i}$, $i=1,2$. Suppose $\delta\colon G/K_{1}\to
G/K_{2}$ is an isomorphism between ${\rm Cos}(G,K_{1},S_{1})$ and ${\rm
Cos}(G,K_{2},S_{2})$. Define a map $\tilde{\delta}$ from $G/H_{1}$ to
$G/H_{2}$ in the following way: first, $\tilde{\delta}(gK_{1})=\delta(gK_{1})$
for every $g\in G$. That is, $\tilde{\delta}$ maps $G/K_{1}$ to $G/K_{2}$ in
the same fashion as $\delta$. To extend $\delta$ to $\tilde{\delta}$, map
elements of $gK_{1}/H_{1}$, $g\in G$, to the set of left cosets of $H_{2}$ in
the left coset $\delta(gK_{1})$ of $K_{2}$ in $G$ bijectively in any fashion.
Then $\tilde{\delta}$ is an isomorphism from ${\rm Cos}(G,H_{1},S_{1})$ to
${\rm Cos}(G,H_{2},S_{2})$.

###### Proof.

Note that as $K_{i}S_{i}K_{i}=S_{i}$, $H_{i}S_{i}H_{i}=S_{i}$, and, as
$S_{i}\cap K_{i}=\emptyset$, $S_{i}\cap H_{i}=\emptyset$. Hence ${\rm
Cos}(G,H_{i},S_{i})$ is a well-defined coset digraph, $i=1,2$. Then
$[K_{1}:H_{1}]=[K_{2}:H_{2}]=n$ as $|H_{1}|=|H_{2}|$ and $|K_{1}|=|K_{2}|$.
Also, $\tilde{\delta}$ is a bijection as it maps $G/K_{1}$ to $G/K_{2}$ and
maps the left cosets of $H_{1}$ contained in $gK_{1}$ to the left cosets of
$H_{2}$ contained in $\delta(gK_{1})$ for every $g\in G$. By Theorem 3.3, we
see ${\rm Cos}(G,H_{i},S_{i})\cong{\rm Cos}(G,K_{i},S_{i})\wr\bar{K}_{n}$,
$i=1,2$. Let $(xH_{1},yH_{1})\in A({\rm Cos}(G,H_{1},S_{1}))$. Then
$(xK_{1},yK_{1})\in A({\rm Cos}(G,K_{1},S_{1}))$, and, as $K_{1}\cap
S_{1}=\emptyset$, we see $xK_{1}\not=yK_{1}$. Then
$(\delta(xK_{1}),\delta(yK_{1}))=(aK_{2},bK_{2})\in A({\rm
Cos}(G,K_{2},S_{2}))$ for some $a,b\in G$. As $xK_{1}\not=yK_{1}$,
$aK_{2}\not=bK_{2}$. Hence $(ak_{2}H_{2},bk_{2}^{\prime}H_{2})\in A({\rm
Cos}(G,H_{2},S_{2}))$ for every $k_{2},k_{2}^{\prime}\in K_{2}$ so
$\tilde{\delta}(xH_{1},yH_{1})\in A({\rm Cos}(G,H_{2},S_{2}))$, and
$\tilde{\delta}$ is an isomorphism from ${\rm Cos}(G,H_{1},S_{1})$ to ${\rm
Cos}(G,H_{2},S_{2})$. ∎

######  Theorem 4.13.

Let $G$ be a group, $H_{i}\leq G$ such that $|H_{1}|=|H_{2}|$, and
$S_{i}\subset G$ such that $H_{i}\cap S_{i}=\emptyset$ and
$H_{i}S_{i}H_{i}=S_{i}$, $i=1,2$. Then ${\rm Cos}(G,H_{1},S_{1})\cong{\rm
Cos}(G,H_{2},S_{2})$ if and only if ${\rm Cay}(G,S_{1})\cong{\rm
Cay}(G,S_{2})$.

###### Proof.

If ${\rm Cos}(G,H_{1},S_{1})\cong{\rm Cos}(G,H_{2},S_{2})$ then clearly their
vertex-sets have the same cardinality and so $|H_{1}|=|H_{2}|$ (i.e. the
hypothesis that $|H_{1}|=|H_{2}|$ is not needed for this part of the proof).
The result follows from Lemma 4.12 (with $K_{i}$ and $H_{i}$ of that lemma
$H_{i}$ and $\\{1\\}$, respectively).

Now suppose $\delta\colon G\to G$ is an isomorphism between ${\rm
Cay}(G,S_{1})$ and ${\rm Cay}(G,S_{2})$. Let $K_{i}\leq G$ be maximal such
that $S_{i}=K_{i}S_{i}K_{i}$, $i=1,2$. Then $H_{i}\leq K_{i}$, $i=1,2$. By
Theorem 3.4, we have by choice of $K_{i}$ that ${\rm Aut}({\rm
Cay}(G,S_{i}))\cong{\rm Aut}({\rm Cos}(G,K_{i},S_{i}))\wr\bar{K}_{|K_{i}|}$,
$i=1,2$. By Theorem 2.8 we see that ${\rm Cos}(G,K_{i},S_{i})$ cannot be
written as a nontrivial wreath product with the complement of a complete
graph, so ${\rm Cos}(G,K_{i},S_{i})$ is irreducible, $i=1,2$. This in turn
implies $|K_{1}|=|K_{2}|$. As $G/K_{i}$ is the lexi-partition of ${\rm
Cay}(G,S_{i})$ with respect to $\bar{K}_{|K_{i}|}$, $G/K_{i}$ is a block
system of ${\rm Aut}({\rm Cay}(G,S_{i}))$, $i=1,2$, and $\delta(G/K_{1})$ is a
block system of ${\rm Aut}({\rm Cay}(G,S_{2}))$. Then $\delta(G/K_{1})\preceq
G/K_{2}$ or $G/K_{2}\preceq\delta(G/K_{1})$ by [7, Lemma 5], and so
$\delta(G/K_{1})=G/K_{2}$. The result now follows by Lemma 4.12. ∎

The preceding result may appear to reduce the isomorphism problem for vertex-
transitive digraphs to the isomorphism problem for Cayley digraphs, as every
vertex-transitive graph can be written as a double coset digraph. This,
however, is not the case, as it is quite possible that a Cayley digraph is
isomorphic to a Cayley digraph of more than one group, see for example [18].
The preceding result will not give the isomorphisms between two different
representations of a single digraph as Cayley digraphs on different groups.

######  Corollary 4.14.

Let $G_{1}$ and $G_{2}$ be groups with $|G_{1}|=|G_{2}|$, $H_{i}\leq G_{i}$
with $|H_{1}|=|H_{2}|$, and $S_{i}\subset G_{i}$ such that $H_{i}\cap
S_{i}=\emptyset$ and $H_{i}S_{i}H_{i}=S_{i}$, $i=1,2$. Let
$\\{L_{1},\ldots,L_{t}\\}$ be the set of all regular subgroups of ${\rm
Aut}({\rm Cay}(G_{1},S_{1}))$. Then ${\rm Cos}(G_{1},H_{1},S_{1})\cong{\rm
Cos}(G_{2},H_{2},S_{2})$ if and only if there is some $1\leq j\leq t$ such
that $L_{j}\cong G_{2}$ and ${\rm Cay}(G_{2},S_{2})\cong{\rm
Cay}(L_{j},T_{j})$ for some $T_{j}\subseteq L_{j}$.

###### Proof.

As $|G_{1}|=|G_{2}|$ and $n=|H_{1}|=|H_{2}|$ we have that $|V({\rm
Cos}(G_{1},H_{1},S_{1}))|=|V({\rm Cos}(G_{2},H_{2},S_{2}))|$. As
$H_{i}S_{i}H_{i}=S_{i}$, by Corollary 3.4, we have that ${\rm
Cos}(G_{i},H_{i},S_{i})\wr\bar{K}_{n}\cong{\rm Cay}(G_{i},S_{i})$, $i=1,2$.

Suppose ${\rm Cos}(G_{1},H_{1},S_{1})\cong{\rm Cos}(G_{2},H_{2},S_{2})$. Then
${\rm Cos}(G_{1},H_{1},S_{1})\wr\bar{K}_{n}\cong{\rm
Cos}(G_{2},H_{2},S_{2})\wr\bar{K}_{n}$. As ${\rm
Cos}(G_{i},H_{i},S_{i})\wr\bar{K}_{n}\cong{\rm Cay}(G_{i},S_{i})$, ${\rm
Aut}({\rm Cay}(G_{1},S_{1}))$ contains a regular subgroup isomorphic $G_{2}$,
so $G_{2}\cong L_{j}$ for some $L_{j}$. Then there exists $T_{j}\subseteq
L_{j}$ with ${\rm Cay}(G_{2},S_{2})\cong{\rm Cay}(L_{j},T_{j})$ for some
$1\leq j\leq t$.

Conversely, suppose there is some $1\leq j\leq t$ such that $L_{j}\cong G_{1}$
and ${\rm Cay}(G_{2},S_{2})\cong{\rm Cay}(L_{j},T_{j})$. Then ${\rm
Cay}(G_{2},S_{2})\cong{\rm Cay}(G_{1},S_{1})$. As ${\rm
Cos}(G_{i},H_{i},S_{i})\wr\bar{K}_{n}\cong{\rm Cay}(G_{i},S_{i})$, $i=1,2$, we
have ${\rm Cos}(G_{1},H_{1},S_{1})\cong{\rm Cos}(G_{2},H_{2},S_{2})$. ∎

In particular, this shows the importance of the problem of determining when a
Cayley digraph is isomorphic to a Cayley digraph of more than one group.

##  5\. Generalized Wreath Products

Generalized wreath products are a fairly new class of digraphs that were
introduced to describe automorphism groups of circulant digraphs (Cayley
digraphs of cyclic groups). They form one of three broad families of digraphs
(the others being deleted wreath product types whose automorphism group has a
factor a symmetric group, and normal Cayley digraphs of ${\mathbb{Z}}_{n}$),
and it was stated in [17, Theorem 2.3] that all circulant digraphs fall into
at least one of these families. This result is a translation of results proven
using results on Schur rings [10, 15, 16] to the language of vertex-transitive
digraphs. We will not dwell on a fourth family, namely those with primitive
automorphism groups, as for circulant digraphs these digraphs are only the
complete graph and its complement. Normal Cayley digraphs were introduced in a
very nice paper [23] by M.Y. Xu in 1998 and are those Cayley digraphs of $G$
for which $G_{L}\triangleleft{\rm Aut}({\rm Cay}(G,S))$. Deleted wreath type
digraphs were first defined in [2], and are those digraphs whose automorphism
group is the same as a deleted wreath product of two smaller digraphs (in
general this family should probably be those digraphs whose automorphism group
has a factor which is the automorphism group of a digraph of smaller order
that is quasiprimitive).

######  Definition 5.1.

Let $\Gamma_{1}$ and $\Gamma_{2}$ be digraphs. The deleted wreath product of
$\Gamma_{1}$ and $\Gamma_{2}$, denoted $\Gamma_{1}\wr_{d}\Gamma_{2}$, is the
digraph with vertex set $V(\Gamma_{1})\times V(\Gamma_{2})$ and arc set

$\\{((x_{1},y_{1}),(x_{2},y_{2})):(x_{1},x_{2})\in A(\Gamma_{1})\text{ and
}y_{1}\not=y_{2}\text{ or }x_{1}=x_{2}\text{ and }(y_{1},y_{2})\in
A(\Gamma_{2})\\}.$

The determination of automorphism groups of circulant digraphs is not quite
complete, although a polynomial time algorithm to determine a generating set
of the automorphism group is known [19] (which for many purposes does provide
a complete solution). While we have a classification of circulant digraphs
into the three families mentioned above, the automorphism groups of deleted
wreath products are not known at this time, although some partial results are
given in [9]. These results do though give a general template on how to
approach the problem of finding automorphism groups of other classes of
vertex-transitive digraphs. Namely, prove a classification type result to show
that all Cayley digraphs under consideration fall within a certain set of
families of digraphs. Then one should determine the automorphism groups of the
digraphs in each of the families, and a complete determination of the
automorphism groups will be obtained.

Generalized wreath products have thus far only been defined for Cayley
digraphs of abelian groups. The reason that they were not defined for Cayley
digraphs of nonabelian groups or vertex-transitive digraphs that are not
Cayley digraphs is that the recognition problem for when such digraphs are
wreath products had not been solved. The idea behind a generalized wreath
product $\Gamma$ is that we do not have any control over which arcs have both
endpoints inside a block of a block system ${\mathcal{C}}$ of a transitive
subgroup of the automorphism group, but the other arcs form a digraph that is
a wreath product, and the lexi-partition of that wreath product refines
${\mathcal{C}}$. Thus we want to be able to decompose the arc set of the
digraph into two sets in such a way that one set of arcs defines a
disconnected digraph (which is a wreath product) and the other a wreath
product in such a way that the automorphism group of $\Gamma$ contains the
intersection of the automorphism groups of the two wreath products. As up to
now we could not determine, by inspection of the connection set, whether the
remaining arcs formed a wreath product, we could not extend the definition to
other vertex-transitive digraphs. Correcting this defect was the original
motivation for this paper. We now define generalized wreath products for all
double coset digraphs, and recall that by [21, Theorem 2] that every vertex-
transitive digraph is isomorphic to a double coset digraph.

######  Definition 5.2.

Let $G$ be a group with subgroups $1\leq H<K\leq L<G$ and $S\subset G$ a union
of double cosets of $H$ in $G$ such that $S\setminus L$ is a union of double
cosets of $K$. The double coset digraph ${\rm Cos}(G,H,S)$ is called a
$(K,L)$-generalized wreath product.

Notice that if $K=L$, then by Theorem 3.3 we have that ${\rm Cos}(G,H,S)$ is a
wreath product. So generalized wreath products are a generalization of the
wreath product. It is straightforward to show that if ${\rm Cos}(G,H,S)$ is a
$(K,L)$-generalized wreath product, then ${\rm Aut}({\rm Cos}(G,H,S))$ does
contain the intersection of ${\rm Aut}({\rm Cos}(G,H,L\cap S))$ and ${\rm
Aut}({\rm Cos}(G,H,S\setminus L))$, and these digraphs have the properties we
were aiming for.

######  Lemma 5.3.

Let $G$ be a group, $S\subset G$, and $1\leq H<K\leq L<G$. If ${\rm
Cos}(G,H,S)$ is isomorphic to a $(K,L)$-generalized wreath product then

${\rm Aut}(\Gamma)\geq{\rm Aut}({\rm Cos}(G,H,S\cap L))\cap{\rm Aut}({\rm
Cos}(G,H,S\setminus L))\geq(S_{r}\wr\Gamma[L])\cap(\Gamma/{\mathcal{B}}\wr
S_{t}),$

where $r=[G:L]$, $t=|K|$, and ${\mathcal{B}}$ is the set of left cosets of $H$
in $G$.

As a good general rule is that symmetry in digraphs is rare, one expects that
the automorphism group of a $(K,L)$-generalized wreath product would be ${\rm
Aut}({\rm Cos}(G,H,S\cap L))\cap{\rm Aut}({\rm Cos}(G,H,S\setminus L))$. It
seems likely that there will be many ways in which the automorphism group will
be larger than expected. The following problem is then natural, and its
solution is a crucial step in determining automorphism groups of vertex-
transitive digraphs.

######  Problem 5.4.

Determine necessary and sufficient conditions for the automorphism group of a
$(K,L)$-generalized wreath product ${\rm Cos}(G,H,S)$ to have automorphism
group ${\rm Aut}({\rm Cos}(G,H,S\cap L))\cap{\rm Aut}({\rm Cos}(G,H,S\setminus
L))$ as expected. Additionally, for each class of generalized wreath products
that do not have automorphism group ${\rm Aut}({\rm Cos}(G,H,S\cap L))\cap{\rm
Aut}({\rm Cos}(G,H,S\setminus L))$, determine the full automorphism group for
each such class.

It has been shown in [5, Theorem 35] that a $(K,L)$-generalized wreath product
circulant digraph of square-free order $n$ has automorphism group ${\rm
Aut}({\rm Cay}({\mathbb{Z}}_{n},S\cap L))\cap{\rm Aut}({\rm
Cay}({\mathbb{Z}}_{n},S\setminus L))$, and extended to all circulant digraphs
in [1, Lemma 3.4]. Also, Theorem 2.8 solves this problem in the special case
when $\Gamma$ is a wreath product, which is guaranteed when $K=L$.

## References

  * [1] João Araújo, Wolfram Bentz, Edward Dobson, Janusz Konieczny, and Joy Morris, _Automorphism groups of circulant digraphs with applications to semigroup theory_ , Combinatorica 38 (2018), no. 1, 1–28. MR 3776345
  * [2] Soumya Bhoumik, Edward Dobson, and Joy Morris, _On the automorphism groups of almost all circulant graphs and digraphs_ , Ars Math. Contemp. 7 (2014), no. 2, 487–506. MR 3277297
  * [3] Maria Chudnovsky, Michal Cizek, Logan Crew, Ján Mináč, Tung T. Nguyen, Sophie Spirkl, and Nguyên Duy Tân, _On prime cayley graphs_ , 2024.
  * [4] John D. Dixon and Brian Mortimer, _Permutation groups_ , Graduate Texts in Mathematics, vol. 163, Springer-Verlag, New York, 1996. MR MR1409812 (98m:20003)
  * [5] Edward Dobson and Joy Morris, _On automorphism groups of circulant digraphs of square-free order_ , Discrete Math. 299 (2005), no. 1-3, 79–98. MR MR2168697 (2006m:20004)
  * [6] by same author, _Automorphism groups of wreath product digraphs_ , Electron. J. Combin. 16 (2009), no. 1, Research Paper 17, 30. MR MR2475540
  * [7] by same author, _Quotients of CI-groups are CI-groups_ , Graphs Combin. 31 (2015), no. 3, 547–550. MR 3338017
  * [8] Ted Dobson, Aleksander Malnič, and Dragan Marušič, _Symmetry in graphs_ , Cambridge Studies in Advanced Mathematics, vol. 198, Cambridge University Press, Cambridge, 2022. MR 4404766
  * [9] Ted Dobson, Štefko Miklavič, and Primož Šparl, _On automorphism groups of deleted wreath products_ , Mediterr. J. Math. 16 (2019), no. 6, Art. 149, 27. MR 4023823
  * [10] S. A. Evdokimov and I. N. Ponomarenko, _Characterization of cyclotomic schemes and normal Schur rings over a cyclic group_ , Algebra i Analiz 14 (2002), no. 2, 11–55. MR MR1925880 (2003h:20005)
  * [11] Marshall Hall, Jr., _The theory of groups_ , Chelsea Publishing Co., New York, 1976, Reprinting of the 1968 edition. MR MR0414669 (54 #2765)
  * [12] Anne Joseph, _The isomorphism problem for Cayley digraphs on groups of prime-squared order_ , Discrete Math. 141 (1995), no. 1-3, 173–183. MR 1336683 (96e:05071)
  * [13] Andrew Kotlov and László Lovász, _The rank and size of graphs_ , J. Graph Theory 23 (1996), no. 2, 185–189. MR 1408346
  * [14] István Kovács and Mary Servatius, _On Cayley digraphs on nonisomorphic 2-groups_ , J. Graph Theory 70 (2012), no. 4, 435–448. MR 2957057
  * [15] Ka Hin Leung and Shing Hing Man, _On Schur rings over cyclic groups. II_ , J. Algebra 183 (1996), no. 2, 273–285. MR MR1399027 (98h:20009)
  * [16] by same author, _On Schur rings over cyclic groups_ , Israel J. Math. 106 (1998), 251–267. MR MR1656873 (99i:20009)
  * [17] Cai Heng Li, _Permutation groups with a cyclic regular subgroup and arc transitive circulants_ , J. Algebraic Combin. 21 (2005), no. 2, 131–136. MR MR2142403 (2006b:20002)
  * [18] Joy Morris, _Isomorphic Cayley graphs on nonisomorphic groups_ , J. Graph Theory 31 (1999), no. 4, 345–362. MR MR1698752 (2000e:05085)
  * [19] I. N. Ponomarenko, _Determination of the automorphism group of a circulant association scheme in polynomial time_ , Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 321 (2005), no. Vopr. Teor. Predst. Algebr. i Grupp. 12, 251–267, 301. MR MR2138422 (2005m:05241)
  * [20] Gert Sabidussi, _The composition of graphs_ , Duke Math. J 26 (1959), 693–696. MR MR0110649 (22 #1524)
  * [21] by same author, _Vertex-transitive graphs_ , Monatsh. Math. 68 (1964), 426–438. MR MR0175815 (31 #91)
  * [22] Steve Wilson, _A worthy family of semisymmetric graphs_ , Discrete Math. 271 (2003), no. 1-3, 283–294. MR 1999550
  * [23] Ming-Yao Xu, _Automorphism groups and isomorphisms of Cayley digraphs_ , Discrete Math. 182 (1998), no. 1-3, 309–319, Graph theory (Lake Bled, 1995). MR MR1603719 (98i:05096)


# A method for analyzing sampling jitter in audio equipment

Makoto Takeuchi<EMAIL_ADDRESS>Haruo Saito  Graduate School of
Arts and Sciences, The University of Tokyo, Tokyo, 153-8902, JAPAN

###### Abstract

A method for analyzing sampling jitter in audio equipment is proposed. The
method is based on the time-domain analysis where the time fluctuations of
zero-crossing points in recorded sinusoidal waves are employed to characterize
jitter. This method enables the separate evaluation of jitter in an audio
player from those in audio recorders when the same playback signal is
simultaneously fed into two audio recorders. Experiments are conducted using
commercially available portable devices with a maximum sampling rate of 192
000 samples per second. The results show jitter values of a few tens of
picoseconds can be identified in an audio player. Moreover, the proposed
method enables the separation of jitter from phase-independent noise utilizing
the left and right channels of the audio equipment. As such, this method is
applicable for performance evaluation of audio equipment, signal generators,
and clock sources.

##  I  Introduction

Sampling jitter in audio equipment is an error in the sampling instants from
the ideal timing, i.e., $t[i]=(i-1)f_{\mathrm{S}}^{-1}$, where
$f_{\mathrm{S}}$ is the sampling frequency of digital-to-analog converter
(DAC) and analog-to-digital converter (ADC). Sampling jitter
$j_{\mathrm{S}}(t)$ causes the sampling instants to be changed to
$t[i]=(i-1)f_{\mathrm{S}}^{-1}+j_{\mathrm{S}}(t[i])$. Hence, sampling jitter
affects the performance of audio equipment. The sampling jitter has
conventionally been analyzed in the frequency domain[Dunn92, Dunn94Feb,
Dunn94May, Dunn00]. In this method, one plays back a sinusoidal wave whose
frequency is $f_{\mathrm{P}}/4$, where $f_{\mathrm{P}}$ is the sampling
frequency of the audio player, records it, and then examines the frequency
response using a window function with small side-lobe levels such as a
Blackman Harris window. In addition to frequency-domain analysis (FDA), time
domain analysis (TDA) of sampling jitter has been conducted[Nishimura10]. The
Hilbert transform has been employed to obtain the real jitter waveform
$j_{\mathrm{S}}(t)$. The advantage of TDA is that one can separately extract
jitter and amplitude modulation (AM) from a recorded waveform,which is not
possible with FDA.

In this study, we propose an efficient and powerful method to characterize
sampling jitter in audio equipment. The proposed method comprises two key
elements. The first is an improved TDA termed zero-crossing analysis (ZCA). To
apply this method, the zero-crossing points (ZCPs) of a recorded waveform are
analyzed, following which the ZCPs of an ideal sinusoidal wave are calculated.
Time differences in ZCPs between the recorded waveform and an ideal sinusoidal
wave contain the jitter information. We term these time differences “zero-
crossing fluctuations (ZCFs).” The ZCA enables us to extract jitter
information from a recorded waveform even when the input signal contains both
jitter and AM. The second key element is the simultaneous recording of the
same playback signal with two audio recorders to generate two independent
waveforms. We term this “double recorder setup (DRS).” Because ZCA preserves
absolute time information, we can exactly compare and calculate the positive
and negative correlations of ZCFs between the two generated waveforms. Based
on the addition rule of probability, the sampling jitter of the player and
that of the recorders can be individually evaluated.

Note that the proposed method requires neither an optional output clock signal
synchronized with the recorders’ internal clock nor an external clock
generator that is more precise than the internal clock. Thus, the proposed
method is possible using low-cost recorders and is feasible at an end-user
level. The proposed method can be also applied to high-frequency phase noise
and jitter measurements. Replacing the two recorders with two digital
oscilloscopes with higher sampling rates, we can use the proposed method for
performance evaluation of various signal and clock generators that output
high-frequency sinusoidal waves.

The method is somewhat similar to the reciprocal calibration of microphones,
which has been used since the 1940s[MacLean40, Barrera-Figueroa18]; however,
it does not require the bidirectional use of devices. The DRS is similar to
the setup of the cross-spectrum method (CSM) for phase noise
measurement[Rubiola10]. In CSM, repeating FDA with double instruments reduces
the influence of the instruments to $1/\sqrt{m_{\mathrm{CS}}}$, where
$m_{\mathrm{CS}}$ is the number of measurements. The proposed method is the
so-called TDA version of CSM. The influence of the instruments is canceled by
using DRS.

In this study, we focus on the performance of audio equipment; however, it
contributes to the field of human audibility[Ashihara05, Melchior19,
Nittono20]. Previous jitter studies[Ashihara05] demonstrated that the
threshold of perceptual detection of random jitter in music signals is large,
but the original jitter, i.e., the one that is already existing before adding
extra jitter, has not been controlled at that time. Researchers can quickly
select instruments with minimal jitter using the method proposed herein. It
provides an opportunity to examine how the detection threshold is reduced
after the testees are well-trained using audio players with lower levels of
jitter and using music signals with which slight artificial jitter is
compounded. Moreover, the proposed method helps to diagnose whether the player
is appropriately operating in all audibility studies.

The remainder of this study is organized as follows. Section II describes the
principles on which the proposed method is based. Section LABEL:Section4
presents the experimental procedure. Section LABEL:Sec:result_all presents our
results. In Section LABEL:Section5, multiple perspectives are discussed, and
Section LABEL:Section6 provides a summary and outlook. We performed numerical
calculations to confirm the accuracy of the proposed method, the details of
which are presented in Appendix.

##  II Principles

###  II.1 Classification of noise in a playback signal and a recorded waveform

A pure sinusoidal wave $F_{\rm pure}(t)$ is expressed as follows:

$\displaystyle F_{\mathrm{pure}}(t)=A_{0}\cos(\omega t+\theta_{0}),$ (1)

where $t$, $\omega$, $\theta_{0}$, and $A_{0}$ are the time, angular
frequency, initial phase, and amplitude of the wave, respectively. When one
plays a digital audio file by which a pure sinusoidal wave is expected to be
reproduced, the resulting playback signal is not a pure sinusoidal wave. It
contains (i) jitter, (ii) AM, and (iii) phase-independent (PI) noise. Here, we
explain these three noise patterns individually. (i) Jitter is the deviation
of the playback timing at each point. When jitter is present, $t$ is replaced
by $t+j(t)$, where $j(t)$ is the jitter of the player. The pure sinusoidal
wave $F_{\mathrm{pure}}(t)$ is thus changed to


# Learning-based Remote Radio Head Selection and Localization in Distributed
Antenna System
††thanks:

1st Given Name Surname  dept. name of organization (of Aff.)
name of organization (of Aff.)
City, Country
email address or ORCID  2nd Given Name Surname  dept. name of organization (of
Aff.)
name of organization (of Aff.)
City, Country
email address or ORCID  3rd Given Name Surname  dept. name of organization (of
Aff.)
name of organization (of Aff.)
City, Country
email address or ORCID  Artan Salihu†‡, Stefan Schwarz†‡ and Markus Rupp† †
Institute of Telecommunications, Technische Universität (TU) Wien
‡ Christian Doppler Laboratory for Dependable Wireless Connectivity for the
Society in Motion
Email<EMAIL_ADDRESS>

###### Abstract

In this work, we consider estimating user positions in a spatially distributed
antenna system (DAS) from the uplink channel state information (CSI). However,
with the increased number of remote radio heads (RRHs), collecting CSI at a
central unit (CU) can significantly increase the fronthaul overhead and
computational complexity of the CU. This problem can be mitigated by selecting
a subset of RRHs. Thus, we present a deep learning-based approach to select a
subset of RRHs for wireless localization. We employ an RRH selection layer
that is jointly trained with the rest of the network and learn the model
parameters as well as the set of selected RRHs. We show that the selection
strategy comes at a relatively small cost of localization performance.
Nonetheless, by comparison to a trivial approach based on the maximization of
the channel gain, we show that the proposed method leads to significant
performance gains in a propagation environment dominated by non-line-of-sight.

###### Index Terms:

Localization, DAS, RRH Selection, Deep Learning, Massive MIMO.

##  I Introduction

The ever-growing demand for location-enabled applications has caused a surge
of research interest to enhance the accuracy and dependability of wireless
positioning methods for both indoor and outdoor environments. Furthermore,
future mobile communication systems can exploit location information for
various tasks, including better capacity planning, optimization, and dynamic
allocation of resources. This is particularly beneficial as we pursue network
densification, namely adding more antennas and base stations (e.g., to
increase the spectrum spatial reuse).

There exist different strategies to exploit the channel properties of the
transmitter to determine its position, such as received signal strength (RSS),
angle-of-arrival (AOA), and time of arrival (TOA) [1, 2]. Lately, the
deployment of massive multiple-input multiple-output (MIMO) technology in the
fifth generation (5G) networks has encouraged active research in machine
learning (ML) and, in particular, deep learning for wireless positioning [3,
4, 5]. In this case, due to large antenna arrays at the massive MIMO base
station (BS), one can leverage from a considerable amount of high-dimensional
channel state information (CSI) to train a model with examples from known
locations. The model then utilizes the CSI of the unknown transmitter to infer
its position.

In order to provide a more uniform quality of service for users in the region
of interest (ROI), distributed antenna systems (DAS) are being advocated. In
this case, a large number of spatially distributed antennas are utilized by
means of remote radio heads (RHHs) in order to extend the BS antenna ports
[6]. Due to the better spatial diversity, DAS can be favorable for wireless
positioning too. However, the main drawback of DAS is that it requires an
expensive infrastructure to connect RRHs with a central unit (CU).
Additionally, collecting signal information from a large number of RRHs
further increases the computational burden at the CU. Hence, a selection
method that utilizes CSI only from the “best” $M$ out of the $N$ RRHs at a
small expense of localization performance is desired. The problem of interest
is, in fact, a combinatorial optimization that is generally NP-hard.

Regardless of the numerous benefits of DAS in wireless communications, the
investigation regarding its positioning capabilities is limited. The works in
[7, 8] make use of RSS and machine learning (ML) based on Gaussian processes
(GP), while [9, 10] investigate other conventional out-of-the-box ML
techniques and exploit different channel information. None of the former works
considers any selection approach. In contrast, we present a deep learning
method with the capability of RRH subset selection strategy, user localization
and uncertainty estimation.

We structure the remaining of this paper as follows. In Section II, we
describe the system model considered for this work. Then, in Section III, we
provide details on the RRH selection strategy and user location estimation. In
Section IV, we evaluate the performance in DAS. In this section, we also
analyze the effectiveness of the proposed selection strategy concerning the
localization error. Finally, in Section V, we draw our conclusions.

Notation: A matrix is denoted by $\mathbf{Y}$, a vector by $\mathbf{y}$ and a
scalar by $y$. The element of a matrix $\mathbf{Y}$ is $y_{m,n}$ and the
Euclidean norm of vectors is $\|\cdot\|$. The cardinality of a set as well as
the absolute value of a scalar are $|\cdot|$. A categorical variable is
denoted by $\verb*|Cat|(\cdot)$, and a length $N$ binary row of a matrix as
$\verb*|one_hot|_{N}(\cdot)$.

##  II System Model

We consider a distributed massive MIMO system, as shown in Fig. 1. We assume
$N$ spatially distributed and single-antenna remote radio heads (RRHs) at
positions $\mathbf{q}_{n}\in\mathbb{R}^{2}$ with $n\in\mathcal{N}$, where
$\mathcal{N}$ denotes the set of RRH indices and $\left|\mathcal{N}\right|=N$.
Assuming mutually orthogonal pilot sequences across the users, each RRH
receives the wireless signal from $R$ single-antenna transmitters placed at
positions $\mathbf{x}_{r}\in\mathbb{R}^{2}$ with $r\in\mathcal{R}$, where
$\mathcal{R}$ denotes the set of user indices and
$\left|\mathcal{R}\right|=R$. Further, we consider $K$ scattering objects in
the ROI at respective positions, $\mathbf{p}_{k}\in\mathbb{R}^{2}$ with
$k\in\mathcal{K}$, where $\mathcal{K}$ denotes the set of scattering object
indices and $\left|\mathcal{K}\right|=K$.

We assume that all RRHs are connected via high-speed fronthaul links to the
central unit (CU), i.e., the delay between the RRHs and the CU is negligible.
Initially, each RRH obtains signal information from $R$ individual locations
during the training phase and forwards it to the CU. The role of the CU is to
process the per-user channel estimates and learn a subset of RRHs. Then,
throughout the operations phase, the role of the CU becomes to perform
positioning inference of the unknown user transmitter with the channel
information gathered from the subset of RRHs, which are learned during the
preceding phase.

Figure 1: Illustration of the system model considered for RRH selection and
user location estimation in a distributed antenna system (DAS).

The channel between the $r-$th user location and the $n-$th RRH is given by a
spatially consistent and scenario-specific channel model [11]

$h_{r,n}=\alpha_{r,n}+\sum_{k=1}^{K}\beta_{r,k}\alpha_{k,n}\quad,$ (1)

where $\alpha_{r,n}$ is the direct line-of-sight (LOS) path, i.e., it
describes the propagation without involving any scattering. The sum term
describes the signal over $K$ other paths that include a scattering event due
to the scattering objects placed in the ROI. As in [11], path coefficients
$\alpha_{i,j}$ and $\beta_{i,j}$ are obtained as:

$\begin{array}[]{l}\alpha_{i,j}=\frac{\lambda}{4\pi\left\|\mathbf{v}_{i}-\mathbf{v}_{j}\right\|}e^{i\frac{2\pi}{\lambda}\left\|\mathbf{v}_{i}-\mathbf{v}_{j}\right\|},\\\
\\\
\beta_{i,j}=\frac{\delta_{j}}{\sqrt{4\pi}\left\|\mathbf{v}_{\ell}-\mathbf{v}_{j}\right\|}e^{i\frac{2\pi}{\lambda}\left\|\mathbf{v}_{i}-\mathbf{v}_{j}\right\|}.\end{array}$
(2)

The coefficients in (2) describe the wave propagation characteristics between
any two elements $i$ and $j$ at their respective positions $\mathbf{v}_{i}$
and $\mathbf{v}_{j}$ in the ROI. The scattering event $\delta_{j}$ captures
the electromagnetic properties of the scattering objects, and $\lambda$
denotes the carrier wavelength. We assume that scattering objects impose a
random phase-shift, $\varphi_{j}$, of the signal and have an amplitude gain of
$\gamma_{j}=\left|\delta_{j}\right|$. The amplitude gain is equal to the
square root of the bi-static radar cross section (RCS) of the scattering
object. As shown in [11], it can be related to the Rician K-factor of the
effective multipath channel and, therefore determines the relative strength of
LOS and NLOS components. Consequently, we are able to model a more realistic
propagation environment that distinguishes from the extreme LOS and non-line-
of-sight (NLOS) cases in order to better understand the performance limits of
our methods in terms of the localization error. The resulting channel model,
after substituting the scattering coefficients (2) and assuming
$\gamma_{j}=\gamma,\forall j$, is given as

$h_{r,n}=\frac{\lambda}{4\pi\left\|\mathbf{x}_{r}-\mathbf{q}_{n}\right\|}e^{i\frac{2\pi}{\lambda}\left\|\mathbf{x}_{r}-\mathbf{q}_{n}\right\|}+\frac{\lambda\gamma}{(4\pi)^{\frac{3}{2}}}\sum_{k=1}^{K}u\left(\mathbf{p}_{k}\right).\vspace{-0.1cm}$
(3)

The individual sum terms are further expressed as

$\displaystyle
u\left(\mathbf{p}_{k}\right)=\left(\left\|\mathbf{x}_{r}-\mathbf{p}_{k}\right\|\left\|\mathbf{p}_{k}-\mathbf{q}_{n}\right\|\right)^{-1}$
(4) $\displaystyle\times
e^{i\left(\varphi_{k}+\frac{2\pi}{\lambda}\left(\left\|\mathbf{x}_{r}-\mathbf{p}_{k}\right\|+\left\|\mathbf{p}_{k}-\mathbf{q}_{n}\right\|\right)\right)}.$

We maintain a minimum distance between any transmit antenna location and RRH,
$\|\mathbf{x}_{n}-\mathbf{q}_{n}\|>0$, as well as between any scattering
object and RRH, $\|\mathbf{q}_{n}-\mathbf{p}_{n}\|>0$. Finally, for each user
$r$, the CU forms a $N\times 1$ channel vector $\mathbf{h}_{r}$, i.e.,

$\mathbf{h}_{r}=\left[h_{r,1},h_{r,2},\ldots,h_{r,N}\right]^{T}\in\mathbb{C}^{N\times
1}.$ (5)

In this work, we rely on channel strength information for localization,
$\widetilde{\mathbf{h}}_{r}=|\mathbf{h}_{r}|$.

##  III Localization with RRHs selection strategy

###  III-A Problem Formulation

Our goal is to reduce the computational complexity at the CU by determining
which RRHs should be selected while providing accurate and reliable
localization performance. The selection process is fixed and performed once
per ROI. The selected RRHs are used for all the test users over a period of
time, until the next scheduled selection process occurs.

We approach this problem in two steps. First, we describe the developed end-
to-end and DNN-based RRH selection method. Then, using the subset of RRHs, we
elaborate how to utilize another DNN to estimate the final position of the
transmitter and the uncertainty associated with it. An overview of the RRH
selection and localization is shown in Fig. 2.

Specifically, we seek to learn a subset $\mathcal{M}\subseteq\mathcal{N}$ of
spatially distributed RRH indices of $|\mathcal{M}|=M$, as well as, a channel
to location mapping function
$f_{\textrm{RSD}}^{\boldsymbol{\theta}}:\mathbb{R}^{M}\mapsto\mathbb{R}^{2}$,
where $\boldsymbol{\theta}$ denotes the parameters (weights) of the first DNN
model, which we will refer to as RRH selection DNN, or RSD. Thus, we seek to
minimize the localization error between the estimated
$\mathbf{x}_{r}^{\star}=f_{\textrm{RSD}}^{\boldsymbol{\theta}}(\widehat{\mathbf{h}}_{r})$
and the given location information $\mathbf{x}_{r}$. Formally, our goal
becomes to learn the optimal $\mathcal{M}^{\star}$ and
$\boldsymbol{\theta}^{\star}$ such that

$\displaystyle\left\\{\mathcal{M}^{\star},\boldsymbol{\theta}^{\star}\right\\}$
$\displaystyle=\underset{\mathcal{M},\boldsymbol{\theta}}{\arg\min}\,\mathcal{L}_{\textrm{RSD}}(\mathbf{x}_{r},\mathbf{\widehat{{h}}}_{r},\boldsymbol{\theta})$
(6)
$\displaystyle=\underset{\mathcal{M},\boldsymbol{\theta}}{\arg\min}\,\mathbb{E}\left[\left\|f_{\textrm{RSD}}^{\boldsymbol{\theta}}(\mathbf{\widehat{{h}}}_{r})-\mathbf{x}_{r}\right\|^{2}\right].\vspace{-0.3cm}$

In (6), $\mathbf{\widehat{{h}}}_{r}$ contains CSI from $M$ selected RRHs. It
can be written as

$\displaystyle\mathbf{\widehat{h}}_{r}=\mathbf{A}\mathbf{\widetilde{h}}_{r}\;,\vspace{-0.1cm}$
(7)

where $\mathbf{A}\in\\{0,1\\}^{M\times N}$ represents a binary selection
matrix with $m$ selection-rows $\mathbf{a}_{m}$, i.e., $a_{m,n}=1$ if
$n\in\mathcal{M}$.

###  III-B RRH Selection

The RRH selection in (6), is a combinatorial optimization problem over the
discrete set $\mathcal{M}\subseteq\mathcal{N}$ of RRHs. This implies that the
number of RRH subsets grows exponentially with $N$ and $M$. In addition,
implementation difficulties arise due to the inability to backpropagate over
the discrete variables. To circumvent these difficulties, we rely on a
reparameterization approach [12]: instead of directly optimizing over
$\mathbf{a}_{m}$, we relax it by a learnable $N-$dimensional vector
$\boldsymbol{\phi}_{m}\in\mathbb{R}_{+}^{N}$. We do so by introducing an RRH
selection layer, trained together with the rest of the network, that utilizes
_concrete_ variables [13, 14], based on a Gumbel distribution [15]. In this
case, the RRH selection layer controls the intensity of relaxation of the
elements in the binary matrix $\mathbf{A}$, using the layer temperature
$\tau\in(0,\infty)$.

Formally, we begin by defining $z_{m}$ to be a categorical variable over the
domain $\\{1,2,\ldots,N\\}$, which can be represented by a vector of class
probabilities $\boldsymbol{\pi}_{m}\in\mathbb{R}^{N}$, i.e.,

$z_{m}\sim\verb*|Cat|(\boldsymbol{\pi}_{m},N),$ (8)

where the class probabilities are related to vector $\boldsymbol{\phi}_{m}$ as

$\pi_{m,n}=\frac{\exp\phi_{m,n}}{\sum_{i=1}^{N}\exp\phi_{m,i}}.$ (9)

Figure 2: RRH selection DNN (RSD) with a sampling and selection layer and
localization with uncertainty estimation DNN (LUD).

Using the Gumbel-Max trick [15, 16], we can sample from (8) by independently
perturbing $\phi_{m,n}$ with i.i.d. Gumbel noise,
$g_{m,n}=\texttt{Gumbel}(0,1)$. Specifically, we draw $N$ samples from a
uniform distribution and form $\mathbf{u}_{m}\sim\mathcal{U}(0,1)$. Then, we
apply the Gumbel inverse CDF, $F_{G}^{-}(\mathbf{u}_{m})$. In more detail,

$\displaystyle\boldsymbol{g}_{m}$
$\displaystyle=F_{G}^{-}(\mathbf{u}_{m})=-\log(-\log(\mathbf{u}_{m}))$ (10)

and

$\tilde{z}_{m}=\operatorname*{arg\,max}_{n\in\\{1,2,\ldots,N\\}}\\{\phi_{m,n}+g_{m,n}\\}.$
(11)

The $\operatorname*{arg\,max}$ of the respective perturbed probabilities
returns a sample from the original categorical distribution,
$\tilde{z}_{m}\stackrel{{\scriptstyle\text{d}}}{{=}}z_{m}$. Finally, during
the forward pass, we can convert $\tilde{z}_{m}$ into a binary vector
$\mathbf{a}_{m}$, such that $\|\mathbf{a}_{m}\|=1$ and we write

$\displaystyle\mathbf{a}_{m}$
$\displaystyle=\verb*|one_hot|_{N}\\{\tilde{z}_{m}\\}$ (12)
$\displaystyle=\verb*|one_hot|_{N}\\{\operatorname*{arg\,max}_{n}\\{\phi_{m,n}+g_{m,n}\\}\\}.$

However, in order to allow gradient backpropagation during the training phase,
we need to relax the non-differentiable $\operatorname*{arg\,max}(\cdot)$
operation. To do so, we rely on Gumbel-Softmax [14] and approximate the
$\operatorname*{arg\,max}(\cdot)$ in (11) with a continuous soft operation,
$\operatorname*{soft\,max}_{\tau}(\cdot)$. Then, $\mathbf{a}_{m}$ is replaced
by

$\displaystyle\mathbf{a}_{m}=\lim_{\tau\rightarrow
0}\frac{\exp\left\\{\tau^{-1}\left(\boldsymbol{\phi}_{m}+\boldsymbol{g}_{m}\right)\right\\}}{\sum_{n=1}^{N}\exp\left\\{\tau^{-1}\left(\phi_{m,n}+g_{m,n}\right)\right\\}}.\vspace{-0.2cm}$
(13)

As $\tau\rightarrow 0$, (13) smoothly approaches the
$\operatorname*{arg\,max}$, and each of the neurons in the RRH sampling and
selection layer outputs one of the selected RRHs. During the training over a
total number of $T$ epochs, the value of $\tau$ decreases exponentially, and
for the $t-$th epoch, it is given by

$\tau_{t}=\tau_{0}\left(\tau_{\text{e}}/\tau_{0}\right)^{t/T},\vspace{-0.2cm}$
(14)

where $\tau_{\text{0}}$ and $\tau_{\text{e}}$ are the user-defined start and
end temperature values, respectively. This enables the end-to-end network to
explore the combinations of RRHs in the beginning and move from linearly
combining to selecting a particular RRH by the end of the training. The
training process repeats until each unit in the selection layer only selects
one specific RRH, $m\in\mathcal{M}$.

###  III-C DNN Learning and Operation

During the test time, i.e., the RRH selection process and localization, we
drop the stochasticity of the network and replace the continuous
$\operatorname*{soft\,max}_{\tau}(\cdot)$ by a discrete
$\operatorname*{arg\,max}(\cdot)$. The training as well operation phase of the
RSD $\forall{m}\in\mathcal{M}$ are further summarized in Algorithm 1 and
Algorithm 2, respectively.

Given: A training dataset
$\mathcal{D}=\\{\mathbf{h}_{r},\mathbf{x}_{r}\\}_{r=1}^{R}$, number of RRHs to
select $M$, epochs $T$, learning rate $\alpha$, final temperature
$\tau_{\text{e}}$, start temperature $\tau_{0}$
Build RSD, $f_{\textrm{RSD}}^{\boldsymbol{\theta}}(\cdot)$, and initialize
$\boldsymbol{\theta}$.

1: for $m\in\\{1,2,\ldots,M\\}$ do

2: Initialize a $N-$ dimensional vector
$\boldsymbol{\phi}_{m}\in\mathbb{R}_{+}^{N}$.

3: end for

4: for $t\in\\{1,2,\ldots,T\\}$ do

5: Compute $\tau$ according to (14)

6: for $m\in\\{1,2,\ldots,M\\}$ do

7: Compute $\mathbf{a}_{m}$ using (12)

8: Set $\widehat{h}_{r,m}=\mathbf{a}_{m}\widetilde{\mathbf{h}}_{r}$

9: end for

10: Compute the gradients of $\mathcal{L}_{\textrm{RSD}}$ w.r.t.
$\boldsymbol{\theta}$ and each $\boldsymbol{\phi}_{m}$.

11: Update the parameters
$\boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\alpha\nabla_{\boldsymbol{\theta}}\mathcal{L}_{\textrm{RSD}}$
and
$\boldsymbol{\phi}\leftarrow\boldsymbol{\phi}-\alpha\nabla_{\boldsymbol{\phi}}\mathcal{L}_{\textrm{RSD}}$

12: end for

Return: Trained $f_{\textrm{RSD}}^{\theta}(\cdot)$ and learned parameters
$\boldsymbol{\theta}$ and $\boldsymbol{\phi}$.

Algorithm 1 Training RSD

Given: A test channel $\widetilde{\mathbf{h}}_{r}$ and trained parameters
$\boldsymbol{\phi}$

1: for $m\in\\{1,2,\ldots,M\\}$ do

2: Compute $\tilde{z}_{m}=\operatorname*{arg\,max}_{n}\\{\phi_{m,n}\\}$

3: Set $\widehat{h}_{r,m}=\widetilde{h}_{r,\tilde{z}_{m}}$

4: end for

Return: $\widehat{\mathbf{h}}_{r}$.

Algorithm 2 Using RSD for RRH Selection

To derive the final location estimate, the obtained
$\mathbf{\widehat{{h}}}_{r}$ from RSD is fed into the subsequent localization
and uncertainty estimation DNN (LUD), which we recently proposed [17]. Given
$\mathbf{\widehat{{h}}}_{r}$, the second network is parameterized by
$\boldsymbol{\Psi}$ and defined as
$f_{\textrm{LUD}}^{\boldsymbol{\Psi}}:\mathbb{R}^{M}\mapsto\mathbb{R}^{4}$.
This model, provides not only estimates of the position but also the
uncertainty inherent in the samples and the model parameters
$\boldsymbol{\Psi}$. Thus, the final location of the transmitter and its
corresponding uncertainty are denoted by $\widehat{\boldsymbol{\mu}}_{r}$ and
$\widehat{\boldsymbol{\sigma}}_{r}$, respectively. For details, see [17].

##  IV Experiments and Results

In this section, we describe the parameter details for the investigated
scenario, training details, and the results relating to the investigation of
the proposed approach.

###  IV-A Simulation Parameters and Training Detail

We evaluate the proposed approach on a scenario where we consider
$N\in\\{16,36,64\\}$ RRHs distributed in a grid configuration within the ROI
of $100\mathrm{m}\times 100\mathrm{m}$ range. An example of the simulation
scenario with $N=64$ is depicted the Fig. 3. We place $K=100$ scattering
objects normally distributed in clusters $i\in\\{1,2,3\\}$ with
$\mathcal{N}(\boldsymbol{\mu}_{k}^{(i)},\boldsymbol{\sigma}_{k}^{(i)})$, where
$\boldsymbol{\mu}_{k}^{(1)}=[0,-60]$, $\boldsymbol{\mu}_{k}^{(2)}=[60,0]$,
$\boldsymbol{\mu}_{k}^{(3)}=[0,60]$, $\boldsymbol{\sigma}_{k}^{(1)}=[100,1]$,
$\boldsymbol{\sigma}_{k}^{(2)}=[1,100]$, and
$\boldsymbol{\sigma}_{k}^{(3)}=[100,1]$. The scattering coefficient is set as
$\gamma=\\{1.2,3.0\\}$ to provide insights on the impact of NLOS components of
the multipath channel. We uniformly sample from $R=49,000$ locations in the
ROI and we set the minimum distance
$\|\mathbf{x}_{r}-\mathbf{q}_{n}\|>0.5\text{m}$.

We adopt $\mathrm{ReLU}$ for the intermediate non-linear operations. The
number of intermediate layers for RSD is $B=3$ with $350$ units. The number of
units in the selection layer is $M$. For the presented experiments, a dropout
rate of $0.2$ was selected. We train RSD for $800$ epochs with $\tau_{e}=0.1$
and $\tau_{0}=10.0$. For training, we utilize the Adam [18] solver, with a
batch size of $512$ at a fixed learning rate of $10^{-3}$, and an early
stopping if the validation loss does not improve for $80$ epochs. The
parameters, $\boldsymbol{\theta}$ and $\boldsymbol{\phi}$, are initialized
with a Glorot normal initializer [19]. The dataset is split into 0.8 and 0.2
for training and hold out testing, respectively. Performance is reported in
terms of

$\mathrm{RMSE}=\sqrt{\frac{\sum_{r=1}^{R_{\mathrm{test}}}\left\|\mathbf{x}_{r}-\widetilde{\boldsymbol{\mu}}_{r}\right\|^{2}}{R_{\mathrm{test}}}},$
(15)

where $\mathbf{x}_{r}$ is the actual position of the test location and,
$\widetilde{\boldsymbol{\mu}}_{r}$ is the estimated location.

Figure 3: Simulation setup with $N$ spatially distributed RRHs.

###  IV-B DAS Localization Accuracy

First, we investigate the localization accuracy in a DAS without any selection
strategy. More specifically, we look into the impact of the number of RRHs as
the NLOS components become stronger. This is shown in Fig. 4. We can observe
that increasing $\gamma$, i.e., the value of scattering coefficients, the
performance degrades in terms of the localization error for approximately
$1\mathrm{m}$ at $90-$th percentile in case of $N=16$. Naturally, increasing
the number of RRHs improves the overall performance but can also compensate
the impact of the dominant NLOS components, where the gap of the error at
$90-$th percentile is approximately $30\mathrm{cm}$ for $N=64$.

Next, we compare the localization accuracy of a DAS with centralized massive
MIMO for $N=64$. In the case of centralized massive MIMO, we consider that
antennas are aligned in a circular array with a diameter of $1.5\mathrm{m}$.
Further, to include direction of arrival information and improve the
granularity of obtained CSI, we handle the complex-valued coefficients as two
independent real numbers, i.e.,
$\Re\left\\{{h}_{r,n}\right\\},\Im\left\\{{h}_{r,n}\right\\}$, representing
the real and imaginary components of $h_{r,n}$. Thus, the channel vector
considered for comparison in centralized case is
$\widehat{\mathbf{h}}_{r}\in\mathbb{R}^{2N}$. In Fig. LABEL:fig:ECDF_DAS-vs-
Cent, we can observe that DAS improves the performance by more than
$60\mathrm{cm}$ at $90-$th percentile. Moreover, in Fig.
LABEL:fig:Uncertainty-Compared, we show that DAS provides a more uniform error
across the ROI, which is fairly modeled by the learned data uncertainty too.
Further increasing the number of antenna elements does not lower the error for
the centralized massive MIMO.

###  IV-C RRH Selection Strategy

To investigate the selection strategy, we evaluate the performance regarding
the localization error for $M\in\\{55,42,36,32,30\\}$. We compare the
selection strategy to a low-complexity approach based on maximum channel gain
(CG) at each RRH. In this case, we define
$\operatorname*{sort\,max}_{N}(\cdot)$ operation, which provides $M$ indices
of RRHs matching to the largest channel gain values in the descending order,
i.e.,

$\\{z_{1}^{\prime},...,z_{M}^{\prime}\\}=\underset{n\in\mathcal{N}}{\operatorname*{sort\,max}_{M}}\,\sum_{r}\|h_{r,n}\|^{2}\,.$
(16)

Then, the CU selects $\widehat{h}_{r,m}=\widetilde{h}_{r,z^{\prime}_{m}}$,
$\forall m$. In Fig. 6, we show the averaged RMSE over multiple realizations
of LUD and provide $95\%$ confidence interval for different $|\mathcal{M}|$.
We see that the proposed selection strategy allows us to learn a subset of
RRHs at a price of a small positioning performance loss. Compared to the
straightforward CG approach, our method has a significant gain especially when
$M\ll N$.

In Fig. 7, we show an example of the learned RRH selection pattern for $M=36$
out of $N=64$. To possibly understand how does the selection pattern change
with $M$, next we investigated the probability of selecting $n\in\mathcal{N}$
as we vary the number of selected RRHs $|\mathcal{M}|$.

Figure 4: Localization accuracy in DAS for different values of $N$ and
$\gamma=\\{1.2,3.0\\}$. The increase in RRHs improves the overall localization
performance and understates the impact of NLOS.

(a)

(b)

Figure 5: Comparison of DAS with centralized massive MIMO. DAS provides a more
uniform error even for $\gamma=3.0$. Figure 6: Localization accuracy for
different $M$ and $\gamma=3.0$. As the compression ratio increases, the
performance gain is higher for RSD.

###  IV-D RRHs Revelant Positions

An additional advantage of using the RRH selection strategy, is that it allows
us to identify and possibly interpret the most relevant positions of the RRHs.
This can be beneficial especially when it is hard to predict the propagation
environment a priori, and thus no optimal configuration design of RRH
positions can be foreseen. Fig. 8 depicts the $M^{\prime}=15$ most frequently
selected RRHs among $M\in\\{55,42,36,32,30\\}$ and $\gamma=3.0$. It can be
noticed that the learning strategy consistently selects a number of RRHs and
favors those in corners of the ROI. This suggests that certain positions of
spatially distributed RRHs provide a more diverse view on the propagation
environment and thus have a higher impact on minimizing the localization error
during the selection process.

##  V Conclusion

In this work, we presented and investigated a learning-based strategy for RRH
subset selection in a DAS for wireless localization. To alleviate the
frontahul capacity constraints, we propose a scalable DNN-based model that
incorporates a RRH selection layer and allows for end-to-end training over a
discrete set of RRHs. We show that the selection strategy comes at the cost of
small performance degradation. Further, the channel information obtained from
the selected RRHs is utilized to estimate the position of the transmitter and
the inherent uncertainty in its estimates. A spatially distributed antenna
system renders a more uniform localization error compared to centralized
massive MIMO. Finally, the learned parameters in the RRH selection layer can
be further probed to allow the analysis of position importance of the RRHs,
possibly help the interpretation and facilitate design choices.

Figure 7: Learned strategy for $M=36$.

(a)

(b)

Figure 8: The most relevant RRHs in the ROI. (a) The occurrence of the most
selected RRHs. (b) Actual positions of the $M^{\prime}=15$ RRHs.

## Acknowledgment

This work has been funded by ÖBB Infrastruktur AG. The financial support by
the Austrian Federal Ministry for Digital and Economic Affairs, the National
Foundation for Research, Technology and Development and the Christian Doppler
Research Association is gratefully acknowledged.

## References

  * [1] M. Zane, M. Rupp, and S. Schwarz, “Performance investigation of angle of arrival based localization,” in _WSA 2020; 24th International ITG Workshop on Smart Antennas_. VDE, 2020, pp. 1–4.
  * [2] F. Wen, H. Wymeersch, B. Peng, W. P. Tay, H. C. So, and D. Yang, “A survey on 5G massive MIMO localization,” _Digital Signal Processing_ , vol. 94, pp. 21–28, 2019.
  * [3] P. Ferrand, A. Decurninge, and M. Guillaud, “DNN-based localization from channel estimates: Feature design and experimental results,” in _GLOBECOM 2020 - 2020 IEEE Global Communications Conference_ , 2020, pp. 1–6.
  * [4] A. Salihu, S. Schwarz, A. Pikrakis, and M. Rupp, “Low-dimensional representation learning for wireless CSI-based localisation,” in _16th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob)(50308)_. IEEE, 2020, pp. 1–6.
  * [5] X. Sun, C. Wu, X. Gao, and G. Y. Li, “Fingerprint-based localization for massive MIMO-OFDM system with deep convolutional neural networks,” _IEEE Transactions on Vehicular Technology_ , vol. 68, no. 11, pp. 10 846–10 857, 2019.
  * [6] S. Schwarz, “Remote radio head assignment and beamforming in dynamic distributed antenna systems,” in _2018 IEEE International Conference on Communications (ICC)_. IEEE, 2018, pp. 1–6.
  * [7] V. Savic and E. G. Larsson, “Fingerprinting-based positioning in distributed massive MIMO systems,” in _2015 IEEE 82nd vehicular technology conference (VTC2015-Fall)_. IEEE, 2015, pp. 1–5.
  * [8] K. S. V. Prasad, E. Hossain, and V. K. Bhargava, “Machine learning methods for RSS-based user positioning in distributed massive MIMO,” _IEEE Transactions on Wireless Communications_ , vol. 17, no. 12, pp. 8402–8417, 2018\.
  * [9] J. Qiu, K. Xu, and Z. Shen, “Cooperative fingerprint positioning for cell-free massive MIMO systems,” in _2020 International Conference on Wireless Communications and Signal Processing (WCSP)_. IEEE, 2020, pp. 382–387.
  * [10] C. Wei, K. Xu, Z. Shen, X. Xia, W. Xie, L. Chen, and J. Xu, “Joint AOA-RSS fingerprint based localization for cell-free massive MIMO systems,” in _2020 IEEE 6th International Conference on Computer and Communications (ICCC)_. IEEE, 2020, pp. 590–595.
  * [11] S. Pratschner, T. Blazek, E. Zöchmann, F. Ademaj, S. Caban, S. Schwarz, and M. Rupp, “A spatially consistent MIMO channel model with adjustable k factor,” _IEEE Access_ , vol. 7, pp. 110 174–110 186, 2019.
  * [12] D. P. Kingma, T. Salimans, and M. Welling, “Variational dropout and the local reparameterization trick,” _Advances in neural information processing systems_ , vol. 28, pp. 2575–2583, 2015.
  * [13] M. F. Balın, A. Abid, and J. Zou, “Concrete autoencoders: Differentiable feature selection and reconstruction,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 444–453.
  * [14] C. J. Maddison, A. Mnih, and Y. W. Teh, “The concrete distribution: A continuous relaxation of discrete random variables,” _arXiv preprint arXiv:1611.00712_ , 2016.
  * [15] E. J. Gumbel, “Statistical theory of extreme values and some practical applications,” _NBS Applied Mathematics Series_ , vol. 33, 1954.
  * [16] C. J. Maddison, D. Tarlow, and T. Minka, “A sampling,” in _Advances in Neural Information Processing Systems_ , Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, Eds., vol. 27. Curran Associates, Inc., 2014.
  * [17] A. Salihu, S. Schwarz, and M. Rupp, “Towards scalable uncertainty aware DNN-based wireless localisation,” _arXiv preprint arXiv:2106.04697_ , 2021\.
  * [18] S. Ruder, “An overview of gradient descent optimization algorithms,” _arXiv preprint arXiv:1609.04747_ , 2016.
  * [19] X. Glorot and Y. Bengio, “Understanding the difficulty of training deep feedforward neural networks,” in _Proceedings of the thirteenth international conference on artificial intelligence and statistics_. JMLR Workshop and Conference Proceedings, 2010, pp. 249–256.