# Revisiting the action of a subgroup of the modular group on imaginary
quadratic number fields

Abdulaziz Deajim  Department of Mathematics, King Khalid University, P.O. Box
9004, Abha, Saudi Arabia<EMAIL_ADDRESS>
###### Abstract.

Consider the modular group $\mbox{PSL}(2,\mathbb{Z})=\langle
x,\,y\,|\,x^{2}=y^{3}=1\rangle$ generated by the transformations
$x:z\mapsto-1/z$ and $y:z\mapsto(z-1)/z$. Let $H$ be the proper subgroup
$\langle y,\,v\,|\,y^{3}=v^{3}=1\rangle$ of $\mbox{PSL}(2,\mathbb{Z})$, where
$v=xyx$. The reference (M. Ashiq and Q. Mushtaq, Actions of a subgroup of the
modular group on an imaginary quadratic field, Quasigropus and Related Systems
14 (2006), 133–146) proposed results concerning the action of $H$ on the
subset
$\\{\frac{a+\sqrt{-n}}{c}\,|\,a,b=\frac{a^{2}+n}{c},c\in\mathbb{Z},c\neq 0\\}$
of the imaginary quadratic number field $\mathbb{Q}(\sqrt{-n})$ for a positive
square-free integer $n$. In the current article, the author points out and
corrects errors appearing in the aforementioned reference. Most importantly,
the corrected estimate for the number of orbits arising from this action is
given, where symmetries in the orbits play a crucial role in the proof.

###### Key words and phrases:

quadratic fields, modular group, group action, orbits

###### 2010 Mathematics Subject Classification:

05A18, 05E18, 11R11, 11A25, 20F05

##  1\. Introduction

The study of the action of the modular group $\mbox{PSL}(2,\mathbb{Z})$ and
its subgroups on various commutative algebraic structures has been common
since the works of Graham Higman and his collaborators in the 1980s ([7],
[10], [11]). Moreover, various tracks of applications of the action of the
modular group (especially in multimedia security) have been appearing
recently, see for instance [1], [13], [15], [16], and [17]. This indeed
suggests a promising future for the applications of this seemingly purely
mathematical topic.

Stothers in [18] showed that the modular group $G=\mbox{PSL}(2,\mathbb{Z})$
has the finite presentation $\langle x,\,y\,|\,x^{2}=y^{3}=1\rangle$, where
$x$ and $y$ are, respectively, the linear fractional transformations
$z\mapsto-1/z$ and $z\mapsto(z-1)/z$. For a square-free integer $m$, the
action of $G$ and its subgroups on certain subsets of the quadratic number
field ${\mathbb{Q}}(\sqrt{m})$ has been extensively studied (see for instance
[4], [5], [6], [8], [9], [11], [12], [14], and [19]). In particular, Ashiq and
Mushtaq (in [3]) studied the proper subgroup $H$ of $G$ generated by the
transformations $y$ and $v=xyx:z\mapsto-1/(z+1)$, where they showed that
$y^{3}=v^{3}=1$ are defining relations for $H$, so $H=\langle
y,\,v\,|\,y^{3}=v^{3}=1\rangle$.

For a positive square-free integer $n$, consider the following subset of the
imaginary quadratic number field ${\mathbb{Q}}(\sqrt{-n})$:

${\mathbb{Q}}^{*}(\sqrt{-n}):=\\{\frac{a+\sqrt{-n}}{c}\,|\,a,b=\frac{a^{2}+n}{c},c\in\mathbb{Z},c\neq
0\\}.$

Deajim and Aslam in [6] studied the action of $G$ on
${\mathbb{Q}}^{*}(\sqrt{-n})$, in which the main result is counting the orbits
resulting from this action. Ashiq and Mushtaq in [2] studied the action of the
subgroup $H$ on ${\mathbb{Q}}^{*}(\sqrt{-n})$, where they suggested a formula
to count the orbits resulting from this action. However, the author of this
article has found some technical/mathematical mistakes in [2] which invited
the need to revisit its findings with the aim of correcting these mistakes
and, particularly, giving the correct formula for the number of orbits.

In Section 2, the errors of [2] are listed along with the reasoning for such a
judgment. Section 3 aims primarily at correcting the main result of [2],
namely [2, Theorem 9], by giving in Theorem 3.5 the accurate formula for the
number of orbits arising from the action of $H$ on
${\mathbb{Q}}^{*}(\sqrt{-n})$. Besides, some lemmas which were used to prove
Theorem 3.5 help also in correcting some of the mistakes of [2] mentioned in
Section 2. Finally, a conclusion containing a summary of the main findings of
the article is given in Section 4.

##  2\. A summary of errors in [2]

Throughout this article, $n$ denotes a positive square-free integer.

An element $\alpha=(a+\sqrt{-n})/c\in{\mathbb{Q}}^{*}(\sqrt{-n})$ is said to
be totally positive if $ac>0$, totally negative if $ac<0$, and of norm zero if
$||\alpha||:=|a|=0$. For $b=(a^{2}+n)/c$, it is obvious that $bc>0$ and so $b$
and $c$ are always of the same sign.

For every $\alpha\in{\mathbb{Q}}^{*}(\sqrt{-n})$, denote the $H$-orbit
$\\{h(\alpha)\,|\,h\in H\\}$ by $\alpha^{H}$ and the $G$-orbit
$\\{g(\alpha)\,|\,g\in G\\}$ by $\alpha^{G}$. It is clear that
$\alpha^{H}\subseteq\alpha^{G}$. Denote the set of $H$-orbits (resp. the set
of $G$-orbits) in ${\mathbb{Q}}^{*}(\sqrt{-n})$ by $\mathcal{O}^{H}_{-n}$
(resp. $\mathcal{O}^{G}_{-n}$).

As usual, we denote by $\lfloor\;.\;\rfloor$ the floor function, by $d(k)$ the
number of positive divisors of $k$, and by $d_{\leq i}(k)$, for
$i,k\in\mathbb{N}$ with $i\leq k$, the number of positive divisors of $k$
which do not exceed $i$. For example, $d(15)=4$ and $d_{\leq 5}(15)=3$. Recall
that $d$ is a multiplicative function and, for a prime $p$, $d(p^{t})=t+1$
where $t\in\mathbb{N}$.

For $\alpha=(a+\sqrt{-n})/c\in{\mathbb{Q}}^{*}(\sqrt{-n})$, we sometimes use
the notation $a_{\alpha}$, $b_{\alpha}$, and $c_{\alpha}$ for $a$, $b$, and
$c$ respectively. Throughout the article and without mention, we shall make
use of the following table which shows the effect of the action of
$t\in\\{x,y,y^{2},v,v^{2}\\}$ on $\alpha$ and can be verified through
straightforward computations:

$t$ | $a_{t(\alpha)}$ |  | $b_{t(\alpha)}$ |  | $c_{t(\alpha)}$
---|---|---|---|---|---
$x$ | $-a$ |  | $c$ |  | $b$
$y$ | $-a+b$ |  | $-2a+b+c$ |  | $b$
$y^{2}$ | $-a+c$ |  | $c$ |  | $-2a+b+c$
$v$ | $-a-c$ |  | $c$ |  | $2a+b+c$
$v^{2}$ | $-a-b$ |  | $2a+b+c$ |  | $b$

Table 1: The action of $x,y,y^{2},v,$ and $v^{2}$

We summarize below the main errors in [2] with some comments on them.

  * Claim 1

[2, line 1 of the proof of Theorem 6]:

> Let $\alpha$ be a totally positive imaginary quadratic number. Then, by
> Theorem 3 (i), $y(\alpha)$ or $y^{2}(\alpha)$ is a totally negative
> imaginary quadratic number.
>

Claim 1 is not necessarily true. We show in Lemma 3.1 that if $\alpha$ is
totally positive, then one of $y(\alpha)$ and $y^{2}(\alpha)$ is totally
positive and the other is either totally positive, totally negative, or of
norm zero. For instance, consider the totally positive element
$\alpha=(2+\sqrt{-5})/3$. Then, both $y(\alpha)=(1+\sqrt{-5})/3$ and
$y^{2}(\alpha)=(1+\sqrt{-5})/2$ are totally positive as well. Another example
is given by $\beta=(1+\sqrt{-1})/2$, then $y(\beta)=\sqrt{-1}$ is of norm zero
and $y^{2}(\beta)=1+\sqrt{-1}$ is totally positive. On the other hand, it
should also be noted that [2, Theorem 3 (i)] states that $y(\alpha)$ and
$y^{2}(\alpha)$ are totally positive when $\alpha$ is totally negative, which
is true, but Claim 1 above strangely misquotes it. Note that Claim 1 being
false renders the proof of [2, Theorem 6] false.

  * Claim 2

[2, Theorem 8]:

> (v) If $\alpha=(1+\sqrt{-n})/c_{1}$ ($n\neq 3$), where $1+n=c_{1}c_{2}$,
> $c_{1}\neq 1$ or $n+1$, then $\alpha$ is the only element of norm 1 in
> $\alpha^{H}$.
>

It is strange that their proof of (v) contradicts the statement above, where
the authors of [2] stated explicitly that
$y^{2}(\alpha)=(1+\sqrt{-n})/\frac{(n+1)}{2}$ when $c_{1}=2$. But then it is
obvious that $y^{2}(\alpha)\in\alpha^{H}$ and is of norm 1 with $\alpha\neq
y^{2}(\alpha)$! This shows that the statement of (v) is false in general. For
instance, consider $\alpha=(1+\sqrt{-5})/2$. Then $\alpha$ is of norm 1 and
satisfies the assumptions of Theorem 8 (v) mentioned above. However,
$y^{2}(\alpha)=(1+\sqrt{-5})/3$ is also of norm 1 belonging to $\alpha^{H}$
and is different from $\alpha$.

As for the other parts of [2, Theorem 8], it is also noted that the arguments
in the proof of parts (iii) and (iv) of [2, Theorem 8] are not sufficient
although the statements are correct. In fact, parts (iii) and (iv) specify
certain cases where an $H$-orbit contains only one element of norm zero. Part
of the proof of Theorem 3.5 shows that this is always the case for any $n$ and
for any $H$-orbit containing an element of norm zero.

  * Claim 3

[2, Theorem 9]:

> If $n\neq 3$, then the total number of orbits of
> ${\mathbb{Q}}^{*}(\sqrt{-n})$ under the action of $H$ are:
>
>     * (i)
>
> $2[d(n)+2d(n+1)-6]$ if $n$ is odd, and
>
>     * (ii)
>
> $2[d(n)+2d(n+1)-4]$ if $n$ is even.
>

This is the main result of [2], which is inaccurate. Its proof relies on [2,
Theorem 8], which has some gaps (see Claim 2). The correct estimate of the
number of orbits is given in Theorem 3.5 below. We briefly give here some
counter-examples to [2, Theorem 9]. For odd integers, consider $n=1$ and
$n=21$ for instance. For $n=1$, the above estimate gives
$|\mathcal{O}^{H}_{-1}|=-2$ which is absurd. Our estimate (see Theorem 3.5)
gives $|\mathcal{O}^{H}_{-1}|=2$. For $n=21$, the above estimate gives
$|\mathcal{O}^{H}_{-21}|=12$, whereas our estimate gives
$|\mathcal{O}^{H}_{-21}|=16$. In fact, according to Theorem 3.5, the number of
orbits in this case has to be congruent to zero modulo 8. For even integers,
consider $n=26$ for instance. The above estimate gives
$|\mathcal{O}^{H}_{-26}|=16$, whereas our estimate gives
$|\mathcal{O}^{H}_{-26}|=24$. The details of the computations of these
counter-examples are given just after the proof of Theorem 3.5.

##  3\. Lemmas and Main Result

The main result of the article is to prove Theorem 3.5 which gives the precise
estimate for the number of $H$-orbits $|\mathcal{O}^{H}_{-n}|$, correcting [2,
Theorem 9]. Besides serving to prove Theorem 3.5, some of the lemmas below
contribute also in correcting some of the errors of [2] mentioned in Section
2.

######  Lemma 3.1.

Let $\alpha=(a+\sqrt{-n})/c\in{\mathbb{Q}}^{*}(\sqrt{-n})$.

  1. (1)

If $\alpha$ is totally positive, then one of $y(\alpha)$ and $y^{2}(\alpha)$
is totally positive and the other is either totally positive, totally
negative, or of norm zero; whereas both $v(\alpha)$ and $v^{2}(\alpha)$ are
totally negative.

  2. (2)

If $\alpha$ is totally negative, then one of $v(\alpha)$ and $v^{2}(\alpha)$
is totally negative and the other is either totally negative, totally
positive, or of norm zero; whereas both $y(\alpha)$ and $y^{2}(\alpha)$ are
totally positive.

  3. (3)

If $\alpha$ is of norm zero, then both $y(\alpha)$ and $y^{2}(\alpha)$ are
totally positive and both $v(\alpha)$ and $v^{2}(\alpha)$ are totally
negative.

### Proof.

Once and for all, note here and elsewhere that Table 1 is used without
mention.

  1. (1)

Assume that $a,b,c>0$ (the case $a,b,c<0$ is proved similarly). We show first
that at least one of $y(\alpha)$ and $y^{2}(\alpha)$ is totally positive. To
the contrary, suppose that neither of them is totally positive. If $y(\alpha)$
is totally negative, then (as $c_{y(\alpha)}=b>0$) $a_{y(\alpha)}=-a+b<0$. As
$b_{y^{2}(\alpha)}=c>0$ and as $b_{y^{2}(\alpha)}$ and $c_{y^{2}(\alpha)}$
have the same sign, we have $-a+b-a+c=c_{y^{2}(\alpha)}>0$ implying that
$a_{y^{2}(\alpha)}=-a+c>0$ (as $-a+b<0$). So, $y^{2}(\alpha)$ is totally
positive, a contradiction. Similarly, if $y^{2}(\alpha)$ is totally negative,
then $y(\alpha)$ is totally positive, a contradiction. On the other hand, if
$y(\alpha)$ is of norm zero, then $a_{y(\alpha)}=-a+b=0$. So,
$c_{y^{2}(\alpha)}=-a+b-a+c=-a+c=a_{y^{2}(\alpha)}$ implying that (as
$c_{y^{2}(\alpha)}\neq 0$) $a_{y^{2}(\alpha)}c_{y^{2}(\alpha)}>0$ and thus
$y^{2}(\alpha)$ is totally positive, a contradiction. Similarly, if
$y^{2}(\alpha)$ is of norm zero, then $y(\alpha)$ is totally positive, a
contradiction. This argument leads to the assertion that at least one of
$y(\alpha)$ and $y^{2}(\alpha)$ is totally positive. Suppose that it is
$y(\alpha)$ which is totally positive (if it were $y^{2}(\alpha)$, then the
proof would be similar). It then follows that $y^{2}(\alpha)$ is either
totally positive, totally negative, or of norm zero depending respectively on
whether $a_{y^{2}(\alpha)}>0$, $a_{y^{2}(\alpha)}<0$, or
$a_{y^{2}(\alpha)}=0$. As for $v(\alpha)$ and $v^{2}(\alpha)$, note that
having $a_{v(\alpha)}=-a-c<0$ and $c_{v(\alpha)}=2a+b+c>0$ implies that
$v(\alpha)$ is totally negative. Also, having $a_{v^{2}(\alpha)}=-a-b<0$ and
$c_{v^{2}(\alpha)}=b>0$ implies that $v^{2}(\alpha)$ is totally negative.

  2. (2)

Similar to the proof of part (1).

  3. (3)

Suppose that $a=0$. Then $a_{y(\alpha)}c_{y(\alpha)}=b^{2}>0$,
$a_{y^{2}(\alpha)}c_{y^{2}(\alpha)}=bc+c^{2}>0$ ($b$ and $c$ are of the same
sign), and so $y(\alpha)$ and $y^{2}(\alpha)$ are totally positive. On the
other hand, $a_{v(\alpha)}c_{v(\alpha)}=-bc-c^{2}<0$,
$a_{v^{2}(\alpha)}c_{v^{2}(\alpha)}=-b^{2}<0$, and so $v(\alpha)$ and
$v^{2}(\alpha)$ are totally negative.

$\square$

We have the following obvious observations (see [6, Lemmas 3.2 and 3.3]).

######  Lemma 3.2.

$($[6, Lemmas 3.2 and 3.3]$)$ For
$\alpha=(a+\sqrt{-n})/c\in{\mathbb{Q}}^{*}(\sqrt{-n})$, we have

  * (i)

$\alpha$ is totally positive if and only if $x(\alpha)$ is totally negative.

  * (ii)

$\alpha$ has norm zero if and only if $x(\alpha)$ has norm zero.

For $\alpha\in{\mathbb{Q}}^{*}(\sqrt{-n})$, the sets $\stackrel{{\scriptstyle
y}}{{\widehat{\;\alpha\;}}}=\\{\alpha,y(\alpha),y^{2}(\alpha)\\}$ and
$\stackrel{{\scriptstyle
v}}{{\widehat{\;\alpha\;}}}=\\{\alpha,v(\alpha),v^{2}(\alpha)\\}$ are called
respectively the $y$-cycle and the $v$-cycle of $\alpha$ (or just cycles when
$\alpha$, $y$, and $v$ are clear in the context). We call a cycle totally
positive (resp. totally negative) if all its elements are totally positive
(resp. if all its elements are totally negative).

######  Lemma 3.3.

Under the action of $H$ on ${\mathbb{Q}}^{*}(\sqrt{-n})$, the following holds
for $\alpha=(a+\sqrt{-n})/c\in{\mathbb{Q}}^{*}(\sqrt{-n})$:

  * (i)

[6, Lemma 3.3] The cycle $\stackrel{{\scriptstyle y}}{{\widehat{\;\alpha\;}}}$
is totally positive if and only if either $($$a>0$, $a<b$, $a<c$$)$ or
$($$a<0$, $a>b$, $a>c$$)$.

  * (ii)

The cycle $\stackrel{{\scriptstyle v}}{{\widehat{\;\alpha\;}}}$ is totally
negative if and only if either $($$a>0$, $-a>b$, $-a>c$$)$ or $($$a<0$,
$-a<b$, $-a<c$$)$.

  * (iii)

The cycle $\stackrel{{\scriptstyle y}}{{\widehat{\;\alpha\;}}}$ is totally
positive if and only if the cycle $\stackrel{{\scriptstyle
v}}{{\,\widehat{x(\alpha)\,}}}$ is totally negative.

  * (iv)

If the cycle $\stackrel{{\scriptstyle y}}{{\widehat{\;\alpha\;}}}$ is totally
positive, then $\alpha^{H}\neq x(\alpha)^{H}$ (i.e. $\alpha$ and $x(\alpha)$
belong to distinct $H$-orbits).

  * (v)

If $n\neq 1$ and $\alpha$ has norm zero, then $\alpha^{H}\neq x(\alpha)^{H}$.

### Proof.

  * (i)

This is [6, Lemma 3.3].

  * (ii)

Suppose that $\stackrel{{\scriptstyle v}}{{\widehat{\;\alpha\;}}}$ is totally
negative. As $\alpha$ is totally negative, either ($a>0$ and $b,c<0$) or
($a<0$ and $b,c>0$). Assume that $a>0$ and $b,c<0$. Since $b_{v(\alpha)}=c<0$,
we get $c_{v(\alpha)}<0$. As further $v(\alpha)$ is totally negative, we must
then have $-a-c=a_{v(\alpha)}>0$ and so $-a>c$. Since also
$c_{v^{2}(\alpha)}=b<0$ and $v^{2}(\alpha)$ is totally negative,
$a_{v^{2}(\alpha)}=-a-b>0$ and so $-a>b$. A similar argument yields that if
$a<0$ and $b,c>0$ then $-a<b$ and $-a<c$.

Conversely, suppose that $a>0$, $-a>b$, and $-a>c$ (the case when $a<0$,
$-a<b$, and $-a<c$ is handled similarly). Since $a>0$ and $-a>c$, $c<0$ and so
$\alpha$ is totally negative. As $a_{v(\alpha)}=-a-c>0$ and
$b_{v(\alpha)}=c<0$ and $b_{v(\alpha)},c_{v(\alpha)}$ are of the same sign,
$v(\alpha)$ is totally negative too. As $a_{v^{2}(\alpha)}=-a-b>0$ and
$c_{v^{2}(\alpha)}=b<0$, $v^{2}(\alpha)$ is totally negative as well. Hence,
the cycle $\stackrel{{\scriptstyle v}}{{\widehat{\;\alpha\;}}}$ is totally
negative.

  * (iii)

Suppose that $\stackrel{{\scriptstyle y}}{{\widehat{\;\alpha\;}}}$ is totally
positive. By (i), if $a>0$, $a<b$, and $a<c$, then it follows from (ii) that
$\stackrel{{\scriptstyle v}}{{\,\widehat{x(\alpha)\,}}}$ is totally negative
since $a_{x(\alpha)}=-a<0$, $-a_{x(\alpha)}=a<c=b_{x(\alpha)}$, and
$-a_{x(\alpha)}=a<b=c_{x(\alpha)}$. The case when $a<0$, $a>b$, and $a>c$ is
similar.

Conversely, suppose that $\stackrel{{\scriptstyle
v}}{{\,\widehat{x(\alpha)\,}}}$ is totally negative. Then by (ii), if
$a_{x(\alpha)}=-a>0$, $-a_{x(\alpha)}=a>b_{x(\alpha)}=c$, and
$-a_{x(\alpha)}=a>c_{x(\alpha)}=b$, then it follows from (i) that
$\stackrel{{\scriptstyle y}}{{\widehat{\;\alpha\;}}}$ is totally positive. The
case when $a_{x(\alpha)}<0$, $-a_{x(\alpha)}<b_{x(\alpha)}$, and
$-a_{x(\alpha)}<c_{x(\alpha)}$ is similar.

  * (iv)

Suppose that $\stackrel{{\scriptstyle y}}{{\widehat{\;\alpha\;}}}$ is totally
positive. By (iii), $\stackrel{{\scriptstyle v}}{{\,\widehat{x(\alpha)\,}}}$
is totally negative. To show that $\alpha^{H}\neq x(\alpha)^{H}$, we need to
show that $h(\alpha)\neq x(\alpha)$ for any $h\in H$. It can be seen that an
arbitrary non-identity element of $H$ takes one and only one of the following
forms:

$\displaystyle h_{1}$
$\displaystyle=y^{\epsilon},\;\mbox{for}\;\epsilon\in\\{1,2\\}$ $\displaystyle
h_{2}$ $\displaystyle=v^{\delta},\;\mbox{for}\;\delta\in\\{1,2\\}$
$\displaystyle h_{3}$ $\displaystyle=y^{\epsilon_{k}}v^{\delta_{k}}\dots
y^{\epsilon_{2}}v^{\delta_{2}}y^{\epsilon_{1}}v^{\delta_{1}},\;\mbox{for}\;k\geq
1,\epsilon_{i},\delta_{i}\in\\{1,2\\},1\leq i\leq k$ $\displaystyle h_{4}$
$\displaystyle=v^{\delta_{k}}y^{\epsilon_{k-1}}v^{\delta_{k-1}}\dots
y^{\epsilon_{2}}v^{\delta_{2}}y^{\epsilon_{1}}v^{\delta_{1}},\;\mbox{for}\;k\geq
2,\epsilon_{i},\delta_{j}\in\\{1,2\\},1\leq i\leq k-1,1\leq j\leq k$
$\displaystyle h_{5}$ $\displaystyle=v^{\delta_{k}}y^{\epsilon_{k}}\dots
v^{\delta_{2}}y^{\epsilon_{2}}v^{\delta_{1}}y^{\epsilon_{1}},\;\mbox{for}\;k\geq
1,\epsilon_{i},\delta_{i}\in\\{1,2\\},1\leq i\leq k$ $\displaystyle h_{6}$
$\displaystyle=y^{\epsilon_{k}}v^{\delta_{k-1}}y^{\epsilon_{k-1}}\dots
v^{\delta_{2}}y^{\epsilon_{2}}v^{\delta_{1}}y^{\epsilon_{1}},\;\mbox{for}\;k\geq
2,\epsilon_{i},\delta_{j}\in\\{1,2\\},1\leq i\leq k,1\leq j\leq k-1$

    * The $h_{1}$ case:

Since there is no $z\in\mathbb{C}$ such that $y^{\epsilon}(z)=x(z)$, we get
$h_{1}(\alpha)=y^{\epsilon}(\alpha)\neq x(\alpha)$. Alternatively,
$y^{\epsilon}(\alpha)\neq x(\alpha)$ since $y^{\epsilon}(\alpha)$ is totally
positive and $x(\alpha)$ is totally negative (by Lemma 3.2).

    * The $h_{2}$ case:

Since there is no $z\in\mathbb{C}$ such that $v^{\delta}(z)=x(z)$, we get
$h_{2}(\alpha)=v^{\delta}(\alpha)\neq x(\alpha)$. Alternatively,
$v^{\delta}(\alpha)\neq x(\alpha)$ since if equality holds then
$xy^{\delta}x(\alpha)=x(\alpha)$ would imply that
$x(\alpha)=y^{-\delta}(\alpha)$, a contradiction (see the $h_{1}$ case above).

    * The $h_{3}$ case:

As $\alpha$ is totally positive, it follows from Lemma 3.1 (1) that
$v^{\delta_{1}}(\alpha)$ is totally negative and so, by Lemma 3.1 (2),
$y^{\epsilon_{1}}v^{\delta_{1}}(\alpha)$ is totally positive. Repeating this
argument for $i=1,\dots,k$, we get that $h_{3}(\alpha)$ is totally positive.
Since $x(\alpha)$ is totally negative, $h_{3}(\alpha)\neq x(\alpha)$.

    * The $h_{4}$ case:

If we let
$h_{4}^{*}=v^{-\delta_{k}}h_{4}=y^{\epsilon_{k-1}}v^{\delta_{k-1}}\dots
y^{\epsilon_{2}}v^{\delta_{2}}y^{\epsilon_{1}}v^{\delta_{1}}$, then by an
argument similar to that in the $h_{3}$ case, $h_{4}^{*}(\alpha)$ is totally
positive. If $h_{4}(\alpha)=x(\alpha)$, then
$h_{4}^{*}(\alpha)=v^{-\delta_{k}}x(\alpha)\in\stackrel{{\scriptstyle
v}}{{\,\widehat{x(\alpha)\,}}}$ and so $h_{4}^{*}(\alpha)$ is totally
negative, a contradiction.

    * The $h_{5}$ case:

If we let $h_{5}^{*}=v^{-\delta_{k}}h_{5}=y^{\epsilon_{k}}\dots
v^{\delta_{2}}y^{\epsilon_{2}}v^{\delta_{1}}y^{\epsilon_{1}}$, then as
$y^{\epsilon_{1}}(\alpha)$ is totally positive, it follows by an argument
similar to that in the $h_{3}$ case that $h_{5}^{*}(\alpha)$ is totally
positive. If $h_{5}(\alpha)=x(\alpha)$, then
$h_{5}^{*}(\alpha)=v^{-\delta_{k}}x(\alpha)$, which is impossible since
$h_{5}^{*}(\alpha)$ is totally positive, while $v^{-\delta_{k}}x(\alpha)$ is
totally negative (see the $h_{4}$ case).

    * The $h_{6}$ case:

If we let
$h_{6}^{*}=y^{-\epsilon_{k}}h_{6}=v^{\delta_{k-1}}y^{\epsilon_{k-1}}\dots
v^{\delta_{2}}y^{\epsilon_{2}}v^{\delta_{1}}y^{\epsilon_{1}}$, then as
$y^{\epsilon_{1}}(\alpha)$ is totally positive, it follows by an argument
similar to that in the $h_{3}$ case that $h_{6}^{*}(\alpha)$ is totally
negative. If $h_{6}(\alpha)=x(\alpha)$, then
$h_{6}^{*}(\alpha)=y^{-\epsilon_{k}}x(\alpha)$, which is impossible since
$h_{6}^{*}(\alpha)$ is totally negative, while $y^{-\epsilon_{k}}x(\alpha)$ is
totally positive by Lemma 3.1 (2).

Now, by having just shown the impossibility of all cases above, we conclude
that there is no $h\in H$ such that $h(\alpha)=x(\alpha)$ and therefore
$\alpha$ and $x(\alpha)$ belong to distinct $H$-orbits as claimed.

  * (v)

Remark first that we excluded the case $n=1$ since the only elements of
$\mathbb{C}$ fixed by $x$ are $\pm\sqrt{-1}\in{\mathbb{Q}}^{*}(\sqrt{-1})$
(i.e. $x(\pm\sqrt{-1})=\pm\sqrt{-1}$); see [6, Lemma 3.4]. Let $n\neq 1$ and
suppose that $\alpha$ has norm zero. Then, $x(\alpha)$ has norm zero too. We
need to show that $h(\alpha)\neq x(\alpha)$ for any $h\in H$. By Lemma 3.1
(3), both $y(\alpha)$ and $y^{2}(\alpha)$ are totally positive, and both
$v(\alpha)$ and $v^{2}(\alpha)$ are totally negative. Now, for
$h_{1},\dots,h_{6}$ as in (iv), and since none of
$y(\alpha),\,y^{2}(\alpha),\,v(\alpha),v^{2}(\alpha)$ has norm zero it is
easily seen that $h_{i}(\alpha)$ is either totally negative or totally
positive for every $i=1,\dots,6$ (see the argument in (iv)). Thus
$h_{i}(\alpha)\neq x(\alpha)$ for any $i=1,\dots,6$. This settles the claim.

$\square$

######  Example 1.

For $n=7$ and $\alpha=(-1+\sqrt{-7})/(-4)$, it can be checked that
$y(\alpha)=(-1+\sqrt{-7})/(-2)$, $y^{2}(\alpha)=(-3+\sqrt{-7})/(-4)$, and so
$\alpha$, $y(\alpha)$, and $y^{2}(\alpha)$ are all totally positive. On the
other hand, $x(\alpha)=(1+\sqrt{-7})/(-2)$, $vx(\alpha)=(1+\sqrt{-7})/(-4)$,
and $v^{2}x(\alpha)=(3+\sqrt{-7})/(-4)$ which are all totally negative.

######  Lemma 3.4.

$($[6, Corollary 3.1]$)$ Under the action of $G$ on
${\mathbb{Q}}^{*}(\sqrt{-n})$, we have the following:

  * (i)

Every $G$-orbit in ${\mathbb{Q}}^{*}(\sqrt{-1})$ contains a unique element of
norm zero.

  * (ii)

Every $G$-orbit in ${\mathbb{Q}}^{*}(\sqrt{-2})$ contains a unique pair of
distinct elements of norm zero.

  * (iii)

Every $G$-orbit in ${\mathbb{Q}}^{*}(\sqrt{-n})$, for $n\geq 3$, contains
either a unique pair of distinct elements of norm zero or a unique totally
positive cycle, but not both.

The aim of our main result below is to compute the cardinality
$|\mathcal{O}^{H}_{-n}|$ correcting the estimate given in [2, Theorem 9] (see
Claim 3 in Section 2). In particular, we utilize the above results to simply
show that

$|\mathcal{O}^{H}_{-1}|=|\mathcal{O}^{G}_{-1}|$, and
$|\mathcal{O}^{H}_{-n}|=2|\mathcal{O}^{G}_{-n}|$ for $n\geq 2$,

and then make use of the precise estimate of $|\mathcal{O}^{G}_{-n}|$ given in
[6, Theorem 2.1] for all $n\geq 1$.

######  Theorem 3.5.

Under the action of $H$, the number of orbits in ${\mathbb{Q}}^{*}(\sqrt{-n})$
is

$\qquad\qquad|\mathcal{O}^{H}_{-n}|=\begin{cases}|\mathcal{O}^{G}_{-1}|&\mbox{,
if $n=1$}\\\ \\\ 2|\mathcal{O}^{G}_{-n}|&\mbox{, if $n\geq 2$}\\\ \end{cases}$

$\;\,=\begin{cases}2&\mbox{, if $n=1$}\\\ 4&\mbox{, if $n=2$}\\\ 8&\mbox{, if
$n=3$}\\\
2d(n)+\frac{4}{3}\;\sum_{i=1}^{\lfloor(n-1)/2\rfloor}[d(i^{2}+n)-2d_{\leq
i}(i^{2}+n)]&\mbox{, if $n>3$.}\end{cases}$

Moreover, $|\mathcal{O}^{H}_{-n}|\equiv 0\;(\bmod\,8)$ for $n\geq 3$.

### Proof.

We begin with the case $n\geq 2$, where we show that
$|\mathcal{O}_{-n}^{H}|=2|\mathcal{O}_{-n}^{G}|$. We show this equality by
showing that every $G$-orbit splits into two distinct $H$-orbits. Let
$\alpha^{G}\in\mathcal{O}_{-n}^{G}$. We know from Lemma 3.4 (ii, iii) that
$\alpha^{G}$ either contains a unique pair of distinct elements of norm zero
or a unique totally positive cycle, but not both. We proceed by dealing with
these two possibilities.

Firstly, suppose that $\alpha^{G}$ contains a unique pair of distinct elements
$\beta$ and $x(\beta)$ of norm zero. Since $\beta\neq x(\beta)$ in this case,
we get from Lemma 3.3 (v) that it cannot be the case that both elements belong
to $\alpha^{H}$. We show that $\alpha^{G}$ splits into two distinct $H$-orbits
($\alpha^{H}$ and $\beta^{H}$) or ($\alpha^{H}$ and $x(\beta)^{H}$) by showing
that $\alpha^{H}$ must contain one and only one of these two norm-zero
elements while the other belongs to $\alpha^{G}-\alpha^{H}$. If
$\beta\in\alpha^{H}$, then (by Lemma 3.3 (v)) $\alpha^{G}$ is the disjoint
union of $\alpha^{H}$ and $x(\beta)^{H}$ and we are done. Similarly, if
$x(\beta)\in\alpha^{H}$, then $\alpha^{G}$ is the disjoint union of
$\alpha^{H}$ and $\beta^{H}$. Now, it remains to show that one of $\beta$ or
$x(\beta)$ must belong to $\alpha^{H}$. Assume that $\beta\not\in\alpha^{H}$;
we show that $x(\beta)\in\alpha^{H}$. Since $\alpha\in\alpha^{G}-\alpha^{H}$,
there is some $g\in G-H$ such that $\beta=g(\alpha)$. In order to show that
$x(\beta)\in\alpha^{H}$, we argue that $xg\in H$, which then would imply that
$x(\beta)=xg(\alpha)\in\alpha^{H}$ as desired. Keeping in mind the forms
$h_{0}=1$ and $h_{1},\dots,h_{6}$ that elements of $H$ can take (see the proof
of Lemma 3.3 (iv)), we see that $g$, as an element of $G$ but not an element
of $H$, can take one of the forms $xh_{i}$, $h_{i}x$, $y^{\gamma}xh_{i}$, or
$h_{i}xy^{\gamma}$ for an appropriate $h_{i}$, $i=0,\dots,6$,
$\gamma\in\\{1,2\\}$. We do the following argument that exhausts all possible
cases.

If $g=xh_{i}$, then $xg=h_{i}\in H$ for $i=0,\dots,6$.

If $g=y^{\gamma}xh_{i}$, then $xg=xy^{\gamma}xh_{i}=v^{\gamma}h_{i}\in H$ for
$i=0,\dots,6$.

If $g=h_{0}x=x$, then $xg=1\in H$.

If $g=h_{0}xy^{\gamma}$, then $xg=y^{\gamma}\in H$.

If $g=h_{1}x=y^{\epsilon}x$, then $xg=xy^{\epsilon}x=v^{\epsilon}\in H$.

If $g=h_{1}xy^{\gamma}=y^{\epsilon}xy^{\gamma}$, then
$xg=xy^{\epsilon}xy^{\gamma}=v^{\epsilon}y^{\gamma}\in H$.

If $g=h_{2}x=v^{\delta}x=xy^{\delta}$, then $xg=y^{\delta}\in H$.

If $g=h_{2}xy^{\gamma}=v^{\delta}xy^{\gamma}=xy^{\delta+\gamma}$, then
$xg=y^{\delta+\gamma}\in H$.

If $g=h_{3}x$, then $xg=x(y^{\epsilon_{k}}v^{\delta_{k}}\dots
y^{\epsilon_{1}}v^{\delta_{1}})x=v^{\epsilon_{k}}y^{\delta_{k}}\dots
v^{\epsilon_{1}}y^{\delta_{1}}\in H$.

If $g=h_{3}xy^{\gamma}$, then $xg=x(y^{\epsilon_{k}}v^{\delta_{k}}\dots
y^{\epsilon_{1}}v^{\delta_{1}})xy^{\gamma}=v^{\epsilon_{k}}y^{\delta_{k}}\dots
v^{\epsilon_{1}}y^{\delta_{1}+\gamma}\in H$.

If $g=h_{4}x$, then
$xg=x(v^{\delta_{k}}y^{\epsilon_{k-1}}v^{\delta_{k-1}}\dots
y^{\epsilon_{1}}v^{\delta_{1}})x=y^{\delta_{k}}v^{\epsilon_{k-1}}y^{\delta_{k-1}}\dots
v^{\epsilon_{1}}y^{\delta_{1}}\in H$.

If $g=h_{4}xy^{\gamma}$, then
$xg=x(v^{\delta_{k}}y^{\epsilon_{k-1}}v^{\delta_{k-1}}\dots
y^{\epsilon_{1}}v^{\delta_{1}})xy^{\gamma}=y^{\delta_{k}}v^{\epsilon_{k-1}}y^{\delta_{k-1}}\dots
v^{\epsilon_{1}}y^{\delta_{1}+\gamma}\in H$.

If $g=h_{5}x$, then $xg=x(v^{\delta_{k}}y^{\epsilon_{k}}\dots
v^{\delta_{1}}y^{\epsilon_{1}})x=y^{\delta_{k}}v^{\epsilon_{k}}\dots
y^{\delta_{1}}v^{\epsilon_{1}}\in H$.

If $g=h_{5}xy^{\gamma}$, then $xg=x(v^{\delta_{k}}y^{\epsilon_{k}}\dots
v^{\delta_{1}}y^{\epsilon_{1}})xy^{\gamma}=y^{\delta_{k}}v^{\epsilon_{k}}\dots
y^{\delta_{1}}v^{\epsilon_{1}}y^{\gamma}\in H$.

If $g=h_{6}x$, then
$xg=x(y^{\epsilon_{k}}v^{\delta_{k-1}}y^{\epsilon_{k-1}}\dots
v^{\delta_{1}}y^{\epsilon_{1}})x=v^{\epsilon_{k}}y^{\delta_{k-1}}v^{\epsilon_{k-1}}\dots
y^{\delta_{1}}v^{\epsilon_{1}}\in H$.

If $g=h_{6}xy^{\gamma}$, then
$xg=x(y^{\epsilon_{k}}v^{\delta_{k-1}}y^{\epsilon_{k-1}}\dots
v^{\delta_{1}}y^{\epsilon_{1}})xy^{\gamma}=v^{\epsilon_{k}}y^{\delta_{k-1}}v^{\epsilon_{k-1}}\dots
y^{\delta_{1}}v^{\epsilon_{1}}y^{\gamma}\in H$.
This shows that $x(\beta)\in\alpha^{H}$. Similarly, if
$x(\beta)\not\in\alpha^{H}$, then $\beta\in\alpha^{H}$.

Secondly, suppose that $\alpha^{G}$ contains a unique totally positive cycle
$\stackrel{{\scriptstyle y}}{{\widehat{\;\beta\;}}}$. By Lemma 3.3 (iii),
$\stackrel{{\scriptstyle v}}{{\,\widehat{x(\beta)\,}}}$ is a totally negative
cycle which is obviously contained in $\alpha^{G}$. Note also, by Lemma 3.3
(iv), that it cannot be the case that both cycles are contained in
$\alpha^{H}$. Following exactly the same argument of the zero-norm elements
above, we conclude that $\alpha^{G}$ is either the disjoint union of
$\alpha^{H}$ and $\beta^{H}$ or is the disjoint union of $\alpha^{H}$ and
$x(\beta)^{H}$, and therefore $\alpha^{G}$ splits into two distinct $H$-orbits
in this case as well.

We have, so far, proved that $|\mathcal{O}_{-n}^{H}|=2|\mathcal{O}_{-n}^{G}|$
for $n\geq 2$. The proof would by complete in this case by applying [6,
Theorem 2.1], which precisely gives the value of $|\mathcal{O}_{-n}^{G}|$ as
follows:

$\displaystyle|\mathcal{O}^{G}_{-n}|$
$\displaystyle=\left\\{\begin{array}[]{c@{\,,\,}l}2&\mbox{if $n=2$}\\\
4&\mbox{if $n=3$}\\\
d(n)+\frac{2}{3}\;\sum_{i=1}^{\lfloor(n-1)/2\rfloor}[d(i^{2}+n)-2d_{\leq
i}(i^{2}+n)]&\mbox{otherwise.}\end{array}\right.$

and, moreover, declares the congruence $|\mathcal{O}^{G}_{-n}|\equiv
0\;(\bmod\,4)$ for $n\geq 3$.

Finally, for the case $n=1$, the only elements of norm zero in
${\mathbb{Q}}^{*}(\sqrt{-1})$ are $\pm\sqrt{-1}$, and both are fixed by $x$
(see the proof of Lemma 3.3 (v)). We also have by Lemma 3.4 (i) that
$\alpha^{G}$ contains a unique element of norm zero; that is $\alpha^{G}$ must
contain either $\sqrt{-1}$ or $-\sqrt{-1}$ but not both. Suppose that
$\sqrt{-1}\in\alpha^{G}$. If $\sqrt{-1}\not\in\alpha^{H}$, then, by following
the argument in the second paragraph of this proof,
$x(\sqrt{-1})\in\alpha^{H}$. But $x(\sqrt{-1})=\sqrt{-1}$, a contradiction.
Thus, $\sqrt{-1}\in\alpha^{H}$. Similarly, if $-\sqrt{-1}\in\alpha^{G}$, then
$-\sqrt{-1}\in\alpha^{H}$. This shows that $\alpha^{H}=\alpha^{G}$ and hence
$|\mathcal{O}^{H}_{-1}|=|\mathcal{O}^{G}_{-1}|$, which in turn equals 2 (by
[6, Theorem 2.1]). $\square$

######  Remark.

We present below some examples showing that the formulas given by [2, Theorem
9] are incorrect in general (see Claim 3 in Section 2).

1\. For $n=1$, the number of orbits $|\mathcal{O}_{-1}^{H}|$ given by [2,
Theorem 9] is

$2[d(1)+2d(2)-6]=2[1+4-6]=-2,$

which is absurd. By Theorem 3.5, however, $|\mathcal{O}_{-1}^{H}|=2$.

2\. For $n=21$, the number of orbits $|\mathcal{O}_{-21}^{H}|$ given by [2,
Theorem 9] is

$2[d(21)+2d(22)-6]=2[4+8-6]=12.$

This estimate immediately appears to be wrong when tested using the congruence
relation in Theorem 3.5. Nonetheless, Theorem 3.5 gives precisely the
following estimate

$\displaystyle|\mathcal{O}_{-21}^{H}|$
$\displaystyle=2d(21)+\frac{4}{3}\,\sum_{i=1}^{10}\left[d(i^{2}+21)-2d_{\leq
i}(i^{2}+21)\right]$ $\displaystyle=8+\frac{4}{3}\\{d(22)-2d_{\leq
1}(22)+d(25)-2d_{\leq 2}(25)+d(30)-2d_{\leq 3}(30)+d(37)-2d_{\leq 4}(37)$
$\displaystyle\qquad\qquad+d(46)-2d_{\leq 5}(46)+d(57)-2d_{\leq
6}(57)+d(70)-2d_{\leq 7}(70)+d(85)-2d_{\leq 8}(85)$
$\displaystyle\qquad\qquad+d(102)-2d_{\leq 9}(102)+d(121)-2d_{\leq
10}(121)\\}$
$\displaystyle=8+\frac{4}{3}\\{4-2+3-2+8-6+2-2+4-4+4-4+8-8+4-4+8-8+3-2\\}$
$\displaystyle=8+8$ $\displaystyle=16.$

3\. For $n=26$, the number of orbits $|\mathcal{O}_{-26}^{H}|$ given by [2,
Theorem 9] is

$2[d(26)+2d(27)-4]=2[4+8-4]=16.$

Theorem 3.5 gives precisely the following estimate

$\displaystyle|\mathcal{O}_{-26}^{H}|$
$\displaystyle=2d(26)+\frac{4}{3}\,\sum_{i=1}^{12}\left[d(i^{2}+26)-2d_{\leq
i}(i^{2}+26)\right]$ $\displaystyle=8+\frac{4}{3}\\{d(27)-2d_{\leq
1}(27)+d(30)-2d_{\leq 2}(30)+d(35)-2d_{\leq 3}(35)$
$\displaystyle\qquad\qquad+d(42)-2d_{\leq 4}(42)+d(51)-2d_{\leq
5}(51)+d(62)-2d_{\leq 6}(62)$ $\displaystyle\qquad\qquad+d(75)-2d_{\leq
7}(75)+d(90)-2d_{\leq 8}(90)+d(107)-2d_{\leq 9}(107)$
$\displaystyle\qquad\qquad+d(126)-2d_{\leq 10}(126)+d(147)-2d_{\leq
11}(147)+d(170)-2d_{\leq 12}(170)\\}$
$\displaystyle=8+\frac{4}{3}\\{4-2+8-4+4-2+8-6+4-4+4-4+6-6+12-10+2-2$
$\displaystyle\qquad\qquad\;+12-12+6-6+8-8\\}$ $\displaystyle=8+16$
$\displaystyle=24.$

##  4\. Conclusion

Consider the subgroup $H=\langle y,\,v\,|\,y^{3}=v^{3}=1\rangle$ of
$\mbox{PSL}(2,\mathbb{Z})=\langle x,\,y\,|\,x^{2}=y^{3}=1\rangle$, where
$x:z\mapsto-1/z$, $y:z\mapsto(z-1)/z$, and $v=xyx:z\mapsto-1/(z+1)$. For a
square-free $n\in\mathbb{N}$, it is shown that the number of orbits in the set

${\mathbb{Q}}^{*}(\sqrt{-n})=\\{\frac{a+\sqrt{-n}}{c}\in{\mathbb{Q}}(\sqrt{-n})\,|\,a,b=\frac{a^{2}+n}{c},c\in\mathbb{Z},c\neq
0\\},$

under the action of $H$, is given as follows:

$\begin{cases}2&\mbox{, if $n=1$}\\\ 4&\mbox{, if $n=2$}\\\ 8&\mbox{, if
$n=3$}\\\
2d(n)+\frac{4}{3}\;\sum_{i=1}^{\lfloor(n-1)/2\rfloor}[d(i^{2}+n)-2d_{\leq
i}(i^{2}+n)]&\mbox{, if $n>3$}\end{cases}$

and is congruent to 0 modulo 8 for all $n\geq 3$, where $d(k)$ denotes the
number of positive divisors of $k$, $d_{\leq i}(k)$ denotes the number of
positive divisors of $k$ which do not exceed $i$ for $i,k\in\mathbb{N}$ with
$i\leq k$, and $\lfloor\;.\;\rfloor$ is the floor function.

## References

  * [1] H. Alolaiyan, A. Razaq, A. Yousaf, and R. Zahra, A comprehensive overview of the formation of homomorphic copies in coset graphs for the modular group, Journal of Mathematics, vol. 2021, Articl ID 3905425, 11 pages, 2021. https://doi.org/10.1155/2021/3905425.
  * [2] M. Ashiq and Q. Mushtaq, Actions of a subgroup of the modular group on an imaginary quadratic field, Quasigropus and Related Systems 14 (2006), 133–146.
  * [3] M. Ashiq and Q. Mushtaq, Finite presentation of a linear-fractional group, Alg. Colloq. 12 (2005), 585–589.
  * [4] T. Chen, M. Bari, M. Malik, H. Siddiqui, J-B. Liu, Icosahedral group and classification of $\mbox{PSL}(2,\mathbb{Z})$-orbits of real quadratic fields, Journal of Mathematics, vol. 2020, Article ID 9568254, 10 pages, 2020. https://doi.org/10.1155/2020/9568254.
  * [5] A. Deajim, The Hecke group $H(\lambda_{4})$ acting on imaginary quadratic number fields, Journal of Mathematics, vol. 2021, Article ID 9323424, 11 pages, 2021. https://doi.org/10.1155/2021/9323424.
  * [6] A. Deajim and M. Aslam, On the number of orbits arising from the action of $\mbox{PSL}(2,\mathbb{Z})$ on imaginary quadratic number fields, U.P.B. Sci. Bull., Series A 82 (2020), 61–74
  * [7] G. Higman and Q. Mushtaq, Coset diagrams and relations for PSL(2, Z), Arab Gulf J. Sci. Res., 1 (1983), 159–164.
  * [8] M. Malik and M. Riaz, Orbits of ${\mathbb{Q}}^{*}(\sqrt{k^{2}m})$ under the action of the modular group $\mbox{PSL}(2,\mathbb{Z})$, U.P.B. Sci. Bull. Series A, 74 (2012), 109-116.
  * [9] M. Malik and A. Zafar, Real quadratic irrational numbers and modular group action, South East Asian Bul. Math, 35 (2011), 439-445.
  * [10] Q. Mushtaq, Coset Diagrams for the Modular Group, Ph.D. Thesis, University of Oxford, UK, 1983.
  * [11] Q. Mushtaq, Modular group acting on real quadratic fields, Bull. Austral. Math. Soc. 37 (1988), 303–309.
  * [12] Q. Mushtaq, On word structure of the modular group over finite and real quadratic fields, Disc. Math., 178 (1998), 155-164.
  * [13] A. Razaq, A. Yousaf, U. Shuaib, . Siddiqui, Atta Ullah, A. Waheed, A novel construction of substitution box involving coset diagram and a bijective map, Security and Communication Networs, vol. 2017, Article ID 5101934, 16 pages, 2017. https://doi.org/10.1155/2017/5101934.
  * [14] A. Razaq, Action of of the gorup $\langle x,y:x^{2}=y^{6}=1\rangle$ on imaginary quadratic fields, Quasigroups and Related Systems, 26 (2018), 139-148.
  * [15] A. Razaq, H. Alolaiyan, M. Ahmad, M. Yousaf, U. Shuaib, W. Aslam, and M. Alawida, A novel method for generation of strong substitution-boxes based on coset graphs and symmetric groups, IEEE Access, 8 (2020), 75473–75490.
  * [16] A. Razaq, S. Akhtar, A. Yousaf, U. Shuaib, and M. Ahmad, A group theoretic construction of highly nonlinear substitution box and its applications in image encryption, Multimed Tools Appls, 81 (2022), 4163–4184.
  * [17] I. Shahzad, Q. Mushtaq, and A. Razaq, Construction of new S-boxes using action of the modular group for multimedia security, Security and Communication Networks, vol. 2019, Article ID 2847801, 13 pages, 2019. https://doi.org/10.1155/2019/2847801.
  * [18] W. Stothers, Subgroups of the modular group, Proc. Camb. Philos. Soc. 75 (1974), 139–154.
  * [19] A. Yousaf, H. Alolaiyan, A. Razaq, and M. Younis, Evolution of ambiguous numbers under the actions of a Binachi group, J. Taibah Univ. Sci., 14 (2020), 615–620.


# Exploration with Model Uncertainty at Extreme Scale in Real-Time Bidding

Jan Hartman<EMAIL_ADDRESS>Zemanta, an Outbrain
companySloveniaLjubljana and  Davorin Kopič<EMAIL_ADDRESS>Zemanta, an
Outbrain companySloveniaLjubljana

(2022)

###### Abstract.

In this work, we present a scalable and efficient system for exploring the
supply landscape in real-time bidding. The system directs exploration based on
the predictive uncertainty of models used for click-through rate prediction
and works in a high-throughput, low-latency environment. Through online A/B
testing, we demonstrate that exploration with model uncertainty has a positive
impact on model performance and business KPIs.

machine learning, big data, real-time bidding, exploration, uncertainty

††copyright: acmcopyright††journalyear: 2022††copyright:
rightsretained††conference: Sixteenth ACM Conference on Recommender Systems;
September 18-23, 2022; Seattle, WA, USA††booktitle: Sixteenth ACM Conference
on Recommender Systems (RecSys ’22), September 18-23, 2022, Seattle, WA,
USA††doi: 10.1145/3523227.3547383††isbn: 978-1-4503-9278-5/22/09††ccs:
Computing methodologies Machine learning††ccs: Information systems
Computational advertising

##  1\. Introduction

In this work, we describe a large-scale exploration system that utilizes the
predictive uncertainty of machine learning models at Zemanta, an Outbrain
company. Zemanta is a demand-side platform (DSP) in the real-time bidding
(RTB) ecosystem (Wang et al., 2016). In RTB, several DSPs (bidders) compete
for advertising space by bidding for it in real-time while a web page is
loading. Advertising space is sold on a per-ad impression basis, which enables
selling it at market value. Every time a user visits a web page with ad space,
DSPs receive a bid request for that ad impression, to which they can respond
with an ad and bid price. It is important to state that DSPs typically do not
receive any information from auctions they did not win (e.g. user feedback or
the winning price), which means we are dealing with censored data.

RTB can be divided into two components: supply (the ad space on publishers’
sites), and demand (the ads that can be shown and the budgets associated with
them). Exploring both sides efficiently is among the most challenging tasks of
recommender systems used in RTB. One of the more common strategies in RTB is
cost-per-click (CPC) bidding, where a bidder wants to buy clicks at a certain
cost. This is typically done using machine learning models for click-through
rate (CTR) prediction, where the predicted CTR of an ad impression is directly
used in determining the amount of money the bidder is willing to pay for it.
Having a good click prediction model is thus of significant importance. Many
new algorithms and modeling techniques are proposed each year by researchers
in academia and industry (McMahan et al., 2013; He et al., 2014; Cheng et al.,
2016; Zhou et al., 2018).

The RTB field has a few intrinsic properties: large amounts of data (Zemanta
receives millions of bid requests per second) and a low latency requirement
(typically around 100 ms). The RTB network connects advertisers to millions of
publishers, which makes the market enormous and challenging to tackle in terms
of recommendations. The distribution of data also changes rapidly as new
publishers, ads, and users enter and exit, so models need to be updated with
new data frequently to stay competitive. Zemanta uses deep models from the
DeepFM family (Guo et al., 2017) to predict CTR, computing over 600 million
predictions per second (Hartman and Kopič, 2021). At this scale, having
efficient predictive models and training pipelines is essential, which was an
important guideline in designing our exploration system that heavily leverages
ML.

##  2\. Motivation

Many recommender systems use predictive models trained on past behavior of the
system, which means feedback loops are a common pitfall in this area. CTR
models used in RTB are no exception here: we use their predictions to set the
bid price for ad impressions and then train them on the same impressions that
we bought. By doing this, we are essentially creating the models’ training
data with the models themselves. A model that has not observed certain parts
of supply (e.g. publishers) or demand (ads) enough will produce poor
predictions on these areas and will therefore buy fewer impressions from those
areas, therefore completing the loop. To remediate this, we force the models
to explore so they gain more knowledge in areas that they are unfamiliar with.
We must also consider that any exploration system we implement must run
continuously due to RTB’s quickly-changing landscape of publishers,
advertisers, and users.

In this work, we focus on exploring the supply (incoming requests). This task
is somewhat different compared to the usual exploration of a recommender
system’s inventory (ads, videos, products, etc). A DSP can choose not to
respond to a bid request and thus disregard a part of supply (e.g. certain
publishers) entirely. Conversely, even if the DSP responds, they must still
win the auction to get the click feedback data that is used to train CTR
models. This situation with censored data makes exploration in this context a
demanding task.

As mentioned above, we want to explore parts of supply where our model is not
performing well. To do this, we must define how to actually explore and how to
determine the model’s performance. The first point is conceptually simple: we
explore by increasing our bid price for certain impressions. This means that
we are more likely to win and buy these impressions and have the model learn
from them. However, this has trade-offs. We are essentially paying extra for
additional training data and potentially impacting business KPIs. This means
that our exploration has to pay off in the end by improving our model and thus
getting better business results.

There are many options on how to determine the model’s performance on certain
supply. One simple approach could be counting, e.g. saying that we need $N$
impressions from a certain publisher in order for the model to perform well
there (Liu and Yu, 2019). However, counting is problematic as we would need to
manually deal with setting thresholds on all possible dimensions of
exploration. We wanted an approach that could deal with many dimensions at
once and would be tightly correlated to any running CTR prediction model’s
knowledge. One such direction and a growing area of research is predictive
uncertainty. Our idea was to use the uncertainty of a CTR model’s predictions
to determine where and how much to explore. A higher level of uncertainty
should mean the model knows less about certain supply. If our goal is to
improve the model, we should focus on buying those uncertain parts of supply.

##  3\. Implementation

Our main criteria when surveying methods for predictive uncertainty estimation
were their performance and scalability. Due to the massive scale we operate
on, any implementations that we want to use must be efficient. An overview of
such methods can be found in Gawlikowski et al. (Gawlikowski et al., 2021),
while Ovadia et al. (Ovadia et al., 2019) tested a few more performant methods
on dataset shift. The method we ultimately chose for our use case was Monte
Carlo (MC) dropout (Gal and Ghahramani, 2016), which is based on the well-
known dropout regularization technique for neural networks (Srivastava et al.,
2014). However, there exist other well-performing and relatively simple
methods (Lakshminarayanan et al., 2017). Dropout is based on randomly zeroing
out neurons in the network at training time, which prevents overfitting and
makes the model more robust. MC dropout works by also applying dropout at
prediction time, thus making the predictions slightly randomized. By computing
many predictions for a given data instance, we can estimate the predictive
distribution. The standard deviation of this sample of predictions represents
the uncertainty of the model – if the predictions vary significantly, it means
the model is more uncertain. MC dropout is also easy to integrate as any deep
model trained with dropout can use it by merely enabling dropout at prediction
time.

Like most recommender system settings where many items are scored and then
ranked for each request, we score many ads with our CTR prediction model on
each bid request we receive, i.e. we compute one prediction per ad. Most
methods for uncertainty estimation require much more computation than making a
prediction. For example, MC dropout requires making $N$ predictions, which
means we would be computing $\\#ads\times N$ instead of $\\#ads$ CTR
predictions. Because we use deep models, this would mean a substantial
increase in compute usage. This was one of the reasons we decided to explore
with uncertainty only on the supply side – instead of making $N$ times the
predictions (total $\\#ads\times N$), we can make only $N$ additional
predictions per request (total $\\#ads+N$), which is much more scalable. Apart
from being more efficient, this approach also enables us to tackle supply and
demand exploration separately. This approach also brings another
consideration: if we have a CTR model that uses both ad and request data, how
do we make predictions only on the request level? We opted to solve this with
a simple masking approach, where all ad features are replaced with dummy
constants, leaving only request features to be used in the uncertainty
computation.

In the previous section, we mentioned that we want our models to explore the
supply where they lack knowledge. This is equivalent to exploring where the
estimated predictive uncertainty is high, which in our case means increasing
our bid price. Consequently, we have to define a transformation from
uncertainty into a bid modifier. As we are directly impacting the business
with exploration, this transformation must be robust to prevent spending too
much on exploration. Moreover, it must adjust continuously due to new and
unpredictable incoming traffic. For this purpose, we implemented a lightweight
controller. The controller is based on streaming (Apache Kafka (Kreps et al.,
2011)). It continuously receives computed uncertainties and adjusts a handful
of statistic estimates used by our bidder when determining how much to
explore. These uncertainty statistics are computed across a few dimensions,
which helps with more accurate estimates. We calculate the bid modifier based
on the mean uncertainty in the past few minutes: $modifier=unc./\mu_{unc.}$
while using a few quantile values for filtering requests with either too low
or too high uncertainty. This system works in near real-time and automatically
adjusts the obtained modifiers to enable continuous exploration without
compromising business goals. It has a few parameters that can adjust the level
of exploration (explore-exploit ratio): the percentage of requests to explore,
the uncertainty thresholds, and the minimum and maximum bid modifier that can
be applied.

##  4\. Evaluation

Our main way of evaluating our approach was to conduct A/B tests in a live
production environment. The test groups were identical except for the CTR
models and exploration strategies. Each group had a separate CTR model, all
models had identical feature sets, hyperparameters, and starting weights.
However, during the test, each of the models only trained on the data it
bought. This prevents data leakage, as a model could otherwise exploit another
model’s explored impressions. In this way, we could judge if the models had
improved through exploration. We set up three groups:

  * •

Control group: the default, it does not perform any explicit supply
exploration.

  * •

Uncertainty explore group: explores with the uncertainty mechanism described
above.

  * •

Random explore group: explores by increasing the bid price with a random
modifier. This modifier is sampled from the distribution of the modifier
obtained with uncertainty.

The goal was to compare our approach with a non-exploratory strategy and one
that explores randomly. This helps to confirm the idea of exploring by
increasing the bid price, along with the validity of using uncertainty for
exploration. We matched the distributions of bid increases for the two explore
groups to make sure they both explore equally.

The online part of our tests was conducted on a subset of incoming traffic,
where each model received an equal amount of requests, distributed randomly.
We ran the test for several days, where each model bought hundreds of millions
of impressions. Our KPIs here were revenue and CTR. Note that revenue can be
easily increased by just blindly increasing bids and buying more, but this
would lead to not satisfying business constraints, i.e. buying at CPC prices
higher than defined. We report revenue increases where business constraints
were respected. After we concluded the online test, we used the last state of
the online models and tested them offline on data we obtained after this time
(the models had not seen this data). Our goal was to measure whether the
exploration strategies improved the models, so our metrics of choice were AUC
and log loss.

The results are displayed in Table 1. We can observe that both strategies show
improvements over the control group in revenue and AUC, but not CTR and log
loss. The uncertainty-based strategy also outperforms the random one in all
metrics. This confirms our hypotheses that using the model’s uncertainty for
exploration is beneficial overall and that it is better than exploring
randomly. The random exploration strategy obtained a surprising lift in
revenue, but the decrease in CTR along with the worse log loss show that it
does not manage to improve the model. The results also show that apart from
business KPIs, the uncertainty exploration improves the model as well, as the
AUC and log loss are better. In the long run, this should lead to even better
results. We also computed model uncertainties on the offline dataset and
observed that the uncertainty explore model’s uncertainty was on average 14%
lower than the uncertainty of the random explore model, which further
indicates that it was improved through exploration.

| Business KPIs | Model metrics
---|---|---
Group | Revenue | CTR | AUC | Log loss
Uncertainty | 5.0% | 9.6% | 0.24% | -0.26%
Random | 3.2% | -2.3% | 0.19% | 0.8%
Table 1. Results of the online A/B test and offline model comparison. All
metrics are presented as relative increases over the control group. Increases
are considered to be improvements for all metrics except log loss.

##  5\. Conclusion

In this work, we presented a scalable and efficient exploration system
integrated into Zemanta’s real-time bidding system. The system leverages the
uncertainty of deep learning models used for CTR prediction to explore the RTB
supply. We use the Monte Carlo dropout algorithm to compute uncertainty of CTR
predictions on the request level and direct our exploration into areas where
the model’s uncertainty is high. Alongside this, we also implemented a
controller to automate the exploration. Through online A/B tests, we have
shown that this approach brings improvements in business KPIs and model
performance. There is ample opportunity for future work in this area. One
direction could be to estimate uncertainty of ads in a similar manner and use
both estimates to explore with a more complex strategy, or even combining the
two exploration systems into one. We also see great potential in implementing
a more sophisticated controller with better insight into our uncertainty
estimates that could adjust the level of exploration more precisely.

## Speaker Bio

Jan Hartman is a data scientist/machine learning engineer at Zemanta, where he
works with high-throughput, low-latency machine learning pipelines at a large
scale. He leads the initiative for implementing and applying state-of-the-art
models for click prediction along with exploration initiatives. Before joining
Zemanta, he worked on research projects in the fields of distributed
computing, neural network optimization, and cryptography. Honors MSc degree in
Computer & Data Science from the University of Ljubljana. Open-source
contributor. Research interests include deep learning, neural network
embeddings, and model compression.

## References

  * (1)
  * Cheng et al. (2016) Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al. 2016\.  Wide & deep learning for recommender systems. In _Proceedings of the 1st workshop on deep learning for recommender systems_. 7–10.
  * Gal and Ghahramani (2016) Yarin Gal and Zoubin Ghahramani. 2016.  Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In _international conference on machine learning_. PMLR, 1050–1059.
  * Gawlikowski et al. (2021) Jakob Gawlikowski, Cedrique Rovile Njieutcheu Tassi, Mohsin Ali, Jongseok Lee, Matthias Humt, Jianxiang Feng, Anna Kruspe, Rudolph Triebel, Peter Jung, Ribana Roscher, et al. 2021\.  A survey of uncertainty in deep neural networks.  _arXiv preprint arXiv:2107.03342_ (2021).
  * Guo et al. (2017) Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. 2017.  DeepFM: a factorization-machine based neural network for CTR prediction.  _arXiv preprint arXiv:1703.04247_ (2017).
  * Hartman and Kopič (2021) Jan Hartman and Davorin Kopič. 2021.  Scaling TensorFlow to 300 million predictions per second. In _Fifteenth ACM Conference on Recommender Systems_. 595–597.
  * He et al. (2014) Xinran He, Junfeng Pan, Ou Jin, Tianbing Xu, Bo Liu, Tao Xu, Yanxin Shi, Antoine Atallah, Ralf Herbrich, Stuart Bowers, et al. 2014\.  Practical lessons from predicting clicks on ads at facebook. In _Proceedings of the Eighth International Workshop on Data Mining for Online Advertising_. 1–9.
  * Kreps et al. (2011) Jay Kreps, Neha Narkhede, Jun Rao, et al. 2011\.  Kafka: A distributed messaging system for log processing. In _Proceedings of the NetDB_ , Vol. 11. 1–7.
  * Lakshminarayanan et al. (2017) Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. 2017.  Simple and scalable predictive uncertainty estimation using deep ensembles.  _Advances in neural information processing systems_ 30 (2017).
  * Liu and Yu (2019) Shuhao Liu and Yong Yu. 2019.  Bid-aware active learning in real-time bidding for display advertising.  _IEEE Access_ 8 (2019), 26561–26572.
  * McMahan et al. (2013) H Brendan McMahan, Gary Holt, David Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, et al. 2013\.  Ad click prediction: a view from the trenches. In _Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining_. 1222–1230.
  * Ovadia et al. (2019) Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. 2019.  Can you trust your model’s uncertainty? evaluating predictive uncertainty under dataset shift.  _Advances in neural information processing systems_ 32 (2019).
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: a simple way to prevent neural networks from overfitting.  _The journal of machine learning research_ 15, 1 (2014), 1929–1958.
  * Wang et al. (2016) Jun Wang, Weinan Zhang, and Shuai Yuan. 2016.  Display advertising with real-time bidding (RTB) and behavioural targeting.  _arXiv preprint arXiv:1610.03013_ (2016).
  * Zhou et al. (2018) Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. 2018\.  Deep interest network for click-through rate prediction. In _Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining_. 1059–1068.


11institutetext: Division of Medical Image Computing, German Cancer Research
Center (DKFZ) 22institutetext: Helmholtz Imaging

# Extending nnU-Net is all you need

Fabian Isensee equal contribution1122 Constantin Ulrich * 11 Tassilo Wald *
1122 Klaus Maier-Hein 1122

###### Abstract

Semantic segmentation is one of the most popular research areas in medical
image computing. Perhaps surprisingly, despite its conceptualization dating
back to 2018, nnU-Net continues to provide competitive out-of-the-box
solutions for a broad variety of segmentation problems and is regularly used
as a development framework for challenge-winning algorithms. Here we use nnU-
Net to participate in the AMOS2022 challenge, which comes with a unique set of
tasks: not only is the dataset one of the largest ever created and boasts 15
target structures, but the competition also requires submitted solutions to
handle both MRI and CT scans. Through careful modification of nnU-net’s
hyperparameters, the addition of residual connections in the encoder and the
design of a custom postprocessing strategy, we were able to substantially
improve upon the nnU-Net baseline. Our final ensemble achieves Dice scores of
90.13 for Task 1 (CT) and 89.06 for Task 2 (CT+MRI) in a 5-fold cross-
validation on the provided training cases.

###### Keywords:

Abdominal Multi-Organ Segmentation nnU-Net AMOS22.

##  1 Introduction

Automated delineation of all anatomical structures and pathologies in medical
images is a long-standing goal in medical image computing. Due to the need of
expert annotators and the time-intensive nature of 3D annotations, datasets
have so far required careful balancing between the number of target structures
and the number of training cases. Consequently, existing methods are either
trained on many images and can robustly segment few structures or are trained
on few images can segment many structures with reduced robustness. Thus,
whenever a holistic perspective on a patients anatomy is required, multiple
expert models must be pooled together from multiple sources. Not only does
this increase the inference time, but it also creates new issues such as
potentially conflicting predictions. Finally and perhaps most importantly,
with each expert model being trained independently, label synergies cannot be
exploited, thus potentially decreasing the label efficiency of the models as
well as their robustness.
In this context, the Abdominal Multi Organ Segmentation 2022 (AMOS2022)
challenge [5], is set out to catalyzes the development of holistic
segmentation methods. It comes with an unprecedented number of training images
and annotated target structures: 15 organs of interest were labeled in 500 CT
and 100 MRI scans, distributed into 200+40 (CT + MRI) training, 100+20
validation and 200+40 test images. The challenge poses two tasks: Task 1 is a
classic multi-organ segmentation problem on just the CT images whereas Task 2
includes the MRI images and expects submitted methods to handle both
modalities.

Within the context of medical image segmentation, nnU-Net [3] has stood the
test of time. It consistently delivers state-of-the-art results on new
segmentation datasets as they are released, despite its fully automated out-
of-the-box nature. Moreover, nnU-Net was successfully used as a basis for
task-specific method optimization, enabling not just us [4, 1] but also many
other teams [6] to win highly contested challenges. Thus, it seems only
natural to use nnU-Net for our participation in the AMOS2022 challenge as
well.

##  2 Method

nnU-Net is a framework that automatically configures and trains U-Net [7]
based segmentation pipelines. Through rigorous analysis of the target dataset,
nnU-Net makes automated adaptations to the patch size, batch size,
preprocessing, network topology and more. For a full description of nnU-Net,
we refer to [3].

In this section we propose several modifications to nnU-net’s automatically
generated pipeline to maximize segmentation performance on the AMOS2022
challenge. Throughout method development we apply all modifications to both
tasks with the sole difference being the intensity normalization scheme. For
Task 1 we utilize nnU-Net’s ’CT’ scheme (data-driven clipping and
normalization) and for Task 2 we use simple z-scoring of all images (nnU-Net’s
’nonCT’ setting).

###  2.1 Optimization of nnU-Net’s segmentation pipeline to AMOS2022

Starting from the default ’3d_fullres’ configuration provided by nnU-Net we
explore multiple improvements. We experimented with replacing the default
encoder of the U-Net with a residual encoder (based on [2]). We furthermore
optimized the preprocessing, specifically the batch size, patch size and
target spacing. Advances in GPU memory capacity and processing speed allowed
for larger models and batch sizes than the standard nnU-Net. Method
development is performed by running 5-fold cross-validation on the provided
training cases. All models are trained from scratch using the nnU-Net
framework. Our experimentation resulted in three well-performing candidates
for Task 1 and two candidates for Task 2, all of which are summarized in table
1.

Table 1: Final configurations used in our submission. Table highlights changes
to the nnU-Net defaults.

Task Name Patch Size Spacing [mm] Data Aug. batch size norm. Arch. -
’3d_fullres’ [64,160,160] [2,0.69,0.69] default 2 CT/z-score - 1 Configuration
1 [128,192,192] [1.5,1,1] DA5 5 CT A2 Configuration 2 [80,224,192]
[2,0.69,0.69] default 6 CT A1 Configuration 3 [128,192,192] [1.5,1,1] default
5 CT A2 2 Configuration 4 [80,224,192] [2,0.69,0.69] default 6 z-score A1
Configuration 5 [128,192,192] [1.5,1,1] default 5 z-score A2

Fig. 1 shows the segmentation architectures used by our final configurations.
They share the same topology but their feature map sizes differ due to nnU-
Net’s automatic configuration of convolutional strides and kernel sizes as a
function of the patch size.

Figure 1: The two architectures used by our final configurations. Due to nnU-
Net’s automatic configuration of kernel sizes and strides as a function of the
patch size, their feature map sizes differ. Both architectures make use of
residual connections in the encoder.

###  2.2 Inference strategy

Prediction is carried out with the nnU-Net defaults (sliding window). For
validation and test set prediction we use ensembling, using both the 5 models
from our cross-validation as well as multiple different configurations (3
configurations for Task 1: 3 x 5 = 15 models in the ensemble). Ensembling is
implemented as simple averaging of softmax outputs.

###  2.3 Postprocessing

The postprocessing offered by nnU-net was designed to cover a wide variety of
use-cases. We believe that additional performance can be gained on AMOS2022 by
specifically analyzing and targeting failure cases of our method. To identify
those we generated a confusion matrix on our cross-validation results (see
supplementary information fig. 2) and performed rigorous visual inspection of
our predicted segmentation maps.

Left-right confusion. Sometimes parts of the left kidney were classified as
right kidney and vice-versa (same for adrenal glands). Here, removing
disconnected small components is suboptimal because then parts of the kidneys
would be labeled as background. Thus, we pooled the final kidney predictions
into a joint class and use a connected component analysis to determine
connected kidney regions. For each connected region we calculate its position
within the image and assign its label (left/right) accordingly.

Connected component filtering. Just like the default nnU-Net we explore
filtering of connected components. Specifically we determine whether removing
all but the largest connected component can improve the Dice score.

Organ size constraints. Driven by the human anatomy, organs are expected to
have a certain volume. This property can be exploited to filter small false
positive predictions, for example in images in which the target organ is not
present but false positive areas are. We use a parameter called ’rate’ in
combination with the minimum organ size observed in the training set. The rate
is intended to be a safety margin: a rate of 0.75 indicates that components
smaller than 75% of the minimum organ size are removed.

Component filtering with size constraints. We combine the two previous
techniques and remove instances below a volume threshold unless its the only
connected region.

Composition of post-processing steps. In order to find the optimal post-
processing scheme we create compositions of the previously mentioned post-
processing schemes, namely:

  1. 1.

PP1: Left right confusion (only kidneys & adrenal glands) followed by organ
size constraints

  2. 2.

PP2: Left right confusion (only kidneys & adrenal glands) followed by
component filtering with size constraints

  3. 3.

PP3: Left right confusion (only kidneys & adrenal glands) followed by
connected component filtering.

  4. 4.

PP4: Only left right confusion (only kidneys & adrenal glands).

We use the predictions of our ensemble on the 5-fold cross-validation
(training images) to optimize the postprocessing scheme. Each organ is
optimized independently and the best performing postprocessing strategy is
retained. Note that we test multiple possible values for the ’rate’ parameter
where applicable. We refer to supplementary tables 4 and 5 for the final
postprocessing configurations.

##  3 Results

The proposed modifications to the default nnU-Net pipeline substantially
improved the results both on the training set cross-validation as well as the
official validation set. We perform ablation studies to highlight the
contributions of each component, see table 2. Overall, we were able to
increase the Dice for configuration 3 (see table 1) by about 1% w.r.t. the
nnU-Net baseline by modifying nnU-Net’s automated configuration (specifically,
target spacing, patch size) and using residual connections in the encoder of
the U-Net. Increasing the batch size yielded further improvements.

Table 2: Ablation results. Method | Task 1 | Task 2
---|---|---
| 5-fold CV | Val | 5-fold CV | Val
| Dice |  mean score (Dice score) | Dice |  mean score Dice score
nnU-Net default | 88.64 |  86.52 (90.31) | - | -
\+ configuration improvements | 89.08 | - | - | -
\+ residual encoder | 89.45 | - | 88.43 | -
\+ increased batch size (bs 5) (corresponds to configs 3 & 5) | 89.57 |  87.71 (91.43) | 88.68 |  87.72 (90.97)

For the sake of brevity we do not show detailed results of the remaining
configurations. We summarize the cross-validation performance of all our
configurations and their ensembles in table 3. As expected, ensembling
provided a substantial gain in segmentation performance, as did our
postprocessing.

Table 3: 5-fold cross-validation results of all our configurations and their ensembles. Task 1 | Task 2
---|---
Config. | Dice | Config. | Dice
Config. 1 | 89.60 | Config. 4 | 88.56
Config. 2 | 89.59 | Config. 5 | 88.69
Config. 3 | 89.57 |  |
Ensemble | 89.92 | Ensemble | 88.94
\+ postprocessing | 90.13 | \+ postprocessing | 89.06

##  4 Discussion

In this paper we performed task-specific optimizations of the default nnU-Net
pipeline to maximize segmentation performance on the AMOS2022 challenge.
Changing crucial hyperparameters such as the patch size, batch size and target
spacing for resampling yielded substantial gains relative to the default
configuration, as did the addition of residual connections in the encoder of
the U-Net. Our final submission consists of three configurations for Task 1
and two for Task 2. Since each configurations was trained as a 5-fold cross-
validation, our ensembles consist of 15 and 10 models, respectively. At the
time of submission, we ranked third in Task 1 and first in Task 2, although we
should add that none of these submissions are reflected in this paper since we
decided on short notice to deviate from our original plan and use larger
ensembles instead (which according to our testing should take approx. 60h on
Task 1 and 50h on Task 2 for inference on an RTX 3090). This decision was made
after the validation set submission was closed and could thus only be
evaluated on the training set cross-validation. Nonetheless, we are confident
in the capabilities of our solution and hope for the improved performance we
measured to translate into the test set. Naturally, the source code for
training our models as well as the inference dockers will be made publicly
available after the competition.

## Acknowledgements

Part of this work was funded by Helmholtz Imaging, a platform of the Helmholtz
Incubator on Information and Data Science.

## References

  * [1] Full, P.M., Isensee, F., Jäger, P.F., Maier-Hein, K.: Studying robustness of semantic segmentation under domain shift in cardiac mri. In: International Workshop on Statistical Atlases and Computational Models of the Heart. pp. 238–249. Springer (2020)
  * [2] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. vol. 2016-December, pp. 770–778. IEEE Computer Society (dec 2016)
  * [3] Isensee, F., Jaeger, P.F., Kohl, S.A.A., Petersen, J., Maier-Hein, K.H.: nnU-net: a self-configuring method for deep learning-based biomedical image segmentation. Nature Methods 18(2)(2), 203–211 (2021)
  * [4] Isensee, F., Jäger, P.F., Full, P.M., Vollmuth, P., Maier-Hein, K.H.: nnu-net for brain tumor segmentation. In: International MICCAI Brainlesion Workshop. pp. 118–132. Springer (2020)
  * [5] Ji, Y., Bai, H., Yang, J., Ge, C., Zhu, Y., Zhang, R., Li, Z., Zhang, L., Ma, W., Wan, X., et al.: Amos: A large-scale abdominal multi-organ benchmark for versatile medical image segmentation. arXiv preprint arXiv:2206.08023 (2022)
  * [6] Ma, J.: Cutting-edge 3d medical image segmentation methods in 2020: Are happy families all alike? arXiv preprint arXiv:2101.00232 (2021)
  * [7] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: Medical Image Computing and Computer-Assisted Intervention – MICCAI 2015. Lecture Notes in Computer Science, Springer International Publishing (2015)

## Appendix

Figure 2: Confusion of organs. The color encodes the relative percentage per row while the number represents the absolute volume over the entire cross validation dataset. We used this as an indicator which error cases exist and could be solved through postprocessing. The diagonal was removed to not influence percentage calculations. Table 4: Postprocessing results for the different organs. We exemplarily show the results for our final ensemble on Task 1 as calcualted on our cross validation. As previously explained, the rate indicates at which percentage of the minimum volume of the organ, a connected prediction of that organ gets removed. Organ | Min. Organ Vol. [mm³] | best PP method | rate | Dice
---|---|---|---|---
|  |  |  | before PP | after PP
Spleen | 14514.5 | PP1 | 0.9 | 97.104 | 97.624
R. Kidney | 32323.3 | PP1 | 0.10 | 96.516 | 96.753
L. Kidney | 10084.4 | PP3 | - | 95.443 | 96.277
Gall Bladder | 1242.1 | PP1 | 0.25 | 86.014 | 87.360
Esophagus | 418.9 | PP1 | 0.25 | 85.480 | 85.481
Liver | 653406.2 | PP3 | - | 97.880 | 97.944
Stomach | 30.6 | PP1 | 0.9 | 91.580 | 91.579
Aorta | 26481.4 | PP1 | 0.75 | 95.901 | 96.036
Postcava | 31401.8 | PP1 | 0.10 | 91.745 | 91.755
Pancreas | 15213.3 | - | - | 86.734 | 86.734
R. Adrenal Gland | 1076.1 | - | - | 79.689 | 79.689
L. Adrenal Gland | 663.7 | PP1 | 0.1 | 80.996 | 81.010
Duodenum | 19244.0 | - | - | 83.789 | 83.789
Bladder | 14665.4 | PP1 | 0.25 | 92.285 | 92.304
Prostate/Uterus | 7937.5 | PP1 | 0.25 | 87.610 | 87.610
Average |  |  |  | 89.918 | 90.130
Table 5: Postprocessing results for the different organs. Equivalent for Task 2 to table 4. Organ | Min. Organ Vol. [mm³] | best PP method | rate | Dice
---|---|---|---|---
|  |  |  | before PP | after PP
Spleen | 14514.5 | PP1 | 0.10 | 96.915 | 97.325
R. Kidney | 32323.3 | - | - | 96.408 | 96.408
L. Kidney | 10084.4 | - | - | 95.606 | 95.606
Gall Bladder | 1242.1 | PP1 | 0.5 | 85.981 | 86.387
Esophagus | 418.9 | PP1 | 0.95 | 82.792 | 82.798
Liver | 653406.2 | PP3 | - | 97.865 | 97.963
Stomach | 30.6 | PP1 | 0.25 | 91.161 | 91.161
Aorta | 26481.4 | PP2 | 0.9 | 95.392 | 95.495
Postcava | 31401.8 | PP1 | 0.10 | 91.252 | 91.273
Pancreas | 15213.3 | - | - | 86.660 | 86.660
R. Adrenal Gland | 1076.1 | - | - | 77.002 | 77.002
L. Adrenal Gland | 663.7 | - | - | 78.007 | 78.007
Duodenum | 19244.0 | PP1 | 0.10 | 81.935 | 81.948
Bladder | 14665.4 | PP1 | 0.50 | 90.430 | 90.795
Prostate/Uterus | 7937.5 | PP1 | 0.25 | 86.658 | 87.121
Average |  |  |  | 88.938 | 89.064