# Enumeration Techniques on Cyclic Schur Rings

Andrew Misseldine111Andrew Misseldine, Southern Utah University,
<EMAIL_ADDRESS>(telephone) 435-865-8228, (fax) 435-865-8666

(17 September 2021)

###### Abstract

Any Schur ring is uniquely determined by a partition of the elements of the
group. In this paper we present a general technique for enumerating Schur
rings over cyclic groups using traditional Schur rings. We also survey recent
efforts to enumerate Schur rings over cyclic groups of specific orders.

Keywords: Schur ring, cyclic group, association scheme, lattice of subgroups

AMS Classification: 20c05, 05c25, 05e30, 05a15 05e16 20k27

##  1 Introduction

The Bell numbers $B(n)$ count the number of ways a finite set $X$ can be
partitioned when $|X|=n$. Without the loss of generality, we may assume
$X=\\{0,1,2,\ldots,n-1\\}$. Hence, the Bell numbers count the number of _set
partitions_ of $X$. The first few Bell numbers are given as
$1,1,2,5,15,52,203,877,4140,\ldots$222Sequence A000110 in OEIS. Could a
similar counting problem be considered for finite groups? That is, could one
construct a sequence of numbers which enumerate the group partitions of a
finite group $G$ when $|G|=n$? We would only want to count partitions that in
some way “respect” the group structure. Some examples of group-theoretic
partitions could be conjugacy classes, automorphism classes, inverse pairs,
(double) cosets, or membership of a subgroup, to name a few possibilities. All
of these examples of group-theoretic partitions are, in fact, examples of
Schur rings (see Definition 1.1).

Schur rings were first introduced by Wielandt [33] as a tool to study
permutation groups and are based upon a method originated by Schur [30]. See
[34] for a detailed treatment of this “Method of Schur.” As Schur rings
themselves are subrings of groups algebras first considered by Schur, their
name is fitting. On the other hand, Schur rings are constructed using
partitions of the group which themselves satisfy the group axioms, that is,
Schur partitions are partitions of a group which are closed under identity,
inverses, and multiplication. Hence, Schur partitions, that is, those
partitions of a group which afford a Schur ring, are the natural candidate to
be the group-theoretic partition we seek to count in this paper.

In the category of sets, the only invariant of a set is its cardinality.
Hence, the Bell numbers are indexed by natural numbers. Our counting of Schur
rings over a group should likewise be indexed by its isomorphism type. The
family of cyclic groups is a natural place to begin this enumeration since the
set $X$ can always be given the structure of a cyclic group. Let
$\mathcal{Z}_{n}=\langle z\rangle$ denote the cyclic group of order $n$,
written multiplicatively. Schur rings over cyclic groups have been of great
interest for the last few decades because of their connection to algebraic
graph theory (see [23]). Cyclic groups are also among a small set of group
families that currently possess a classification theorem of Schur rings (see
Theorem 2.1). For these reasons, we consider the sequence of numbers
$\Omega(n)$ which denote the number of Schur rings over the cyclic group
$\mathcal{Z}_{n}$.

We will now establish some notation for this paper. Let $G$ be a finite group,
and let $\mathbb{Q}[G]$ denote its rational group algebra. Let
$\mathcal{L}(G)$ denote the lattice of subgroups of $G$. For any subset
$C\subseteq G$, we may identify this subset with an element of the group
algebra $\mathbb{Q}[G]$, namely, $\sum_{g\in C}g\in\mathbb{Q}[G]$. Such an
element is called a _simple quantity_ , and when there is no confusion we will
denote simple quantities by the subsets themselves. Define
$C^{*}:=\\{x^{-1}\mid x\in C\\}$ for all $C\subseteq G$.

######  Definition 1.1.

Let $\\{C_{1},C_{2},\ldots,C_{r}\\}$ be a partition of $G$, and let
$\mathfrak{S}$ be the subspace of $\mathbb{Q}[G]$ spanned by the simple
quantities $C_{1},C_{2},\ldots C_{r}$. We say that $\mathfrak{S}$ is a _Schur
ring_ over $G$ if

  1. 1.

$C_{1}=\\{1\\}$,

  2. 2.

For each $i$, there is a $j$ such that $C_{i}^{*}=C_{j}$,

  3. 3.

For each $i$ and $j$,
$C_{i}C_{j}=\displaystyle\sum_{k=1}^{r}\lambda_{ijk}C_{k}$, for
$\lambda_{ijk}\in\mathbb{N}$.

The sets $C_{1},C_{2},\ldots,C_{r}$ are called the _primitive sets_ of
$\mathfrak{S}$ or the _$\mathfrak{S}$ -classes_.

Note that a Schur ring $\mathfrak{S}$ is uniquely determined by its associated
partition of $G$. We will denote this partition as
$\mathcal{D}(\mathfrak{S})$.

The first attempt to classify Schur rings began with Schur himself. In this
original setting, the _transitivity module_ of a permutation group $G$ acting
on a regular subgroup $H$ is the subspace of $\mathbb{Q}[H]$ spanned by the
$G_{e}$-orbits, where $G_{e}$ is the stabilizer of the identity $e\in H$.
Transitivity modules are always Schur rings. Schur conjectured that all Schur
rings over $H$ were transitivity modules for some $G\leq\text{Sym}(H)$. Such a
Schur ring is called _Schurian_ , first coined by Pöschel [29], and a group
$H$ is likewise called _Schurian_ if all Schur rings over $H$ are Schurian.
Wielandt [34] disproved this conjecture. As Schur himself mostly worked with
cyclic Schur rings, another conjecture suggested that all cyclic groups were
Schurian. This conjecture was likewise disproved by Evdokimov and Ponomarenko
in [7]. Evdokimov, Kovács, and Ponomarenko later classified all Schurian
cyclic groups in [9] as those cyclic groups whose orders333We point out that
all the cyclic group examples considered in Section 4 are Schurian by this
theorem. are $p^{k},pq^{k},2pq^{k},pqr,2pqr$, where $p,q,r$ are distinct
primes. See [10] for a history of efforts made to classify Schurian cyclic and
non-cyclic groups.

The first attempt to enumerate Schur rings began with Liskovets and Pöschel
[21] who enumerated wreath-indecomposable Schur rings over the cyclic group of
order $p^{n}$, where $p$ is an odd prime, in an attempt to count certain
circulant graphs. Kovács [16] later solves the more difficult problem when
$p=2$. In [22], the author provides recursive formulas to count the number of
Schur rings over a cyclic group of order $p^{n}$, where $p$ is an arbitrary
prime. In [14], Keller, the author, and Sullivan enumerate all Schur rings
over cyclic groups of order $pq$ and $4p$, where $p$ and $q$ are distinct odd
primes. In [13], Humphries and Wagner enumerate symmetric Schur ring over
cyclic groups and show these Schur rings are in one-to-one or one-to-two
correspondence with central Schur rings of projective special linear groups.
In [35], Ziv-Av enumerates all Schur rings over small finite groups up to
order 63 using computer software.

In this paper, we generalize the enumeration techniques illustrated introduced
in [22], as well as survey the enumerations found in [22] and [14]. Also,
using the computer software MAGMA [4], we enumerate the number of all Schur
rings over cyclic groups of orders up to 400 (see Table 1.1).

Table 1.1: The Number of Schur Rings over $\mathcal{Z}_{n}$

$n$ | $\Omega(n)$ | $n$ | $\Omega(n)$ | $n$ | $\Omega(n)$ | $n$ | $\Omega(n)$ | $n$ | $\Omega(n)$ | $n$ | $\Omega(n)$ | $n$ | $\Omega(n)$ | $n$ | $\Omega(n)$ | $n$ | $\Omega(n)$ | $n$ | $\Omega(n)$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
1 | 1 | 41 | 8 | 81 | 92 | 121 | 21 | 161 | 53 | 201 | 53 | 241 | 20 | 281 | 16 | 321 | 27 | 361 | 43
2 | 1 | 42 | 188 | 82 | 25 | 122 | 37 | 162 | 1224 | 202 | 28 | 242 | 128 | 282 | 188 | 322 | 360 | 362 | 55
3 | 2 | 43 | 8 | 83 | 4 | 123 | 55 | 163 | 10 | 203 | 81 | 243 | 345 | 283 | 8 | 323 | 103 | 363 | 289
4 | 3 | 44 | 61 | 84 | 1397 | 124 | 119 | 164 | 121 | 204 | 1863 | 244 | 179 | 284 | 119 | 324 | 15934 | 364 | 5147
5 | 3 | 45 | 140 | 85 | 60 | 125 | 58 | 165 | 670 | 205 | 93 | 245 | 450 | 285 | 997 | 325 | 659 | 365 | 139
6 | 7 | 46 | 13 | 86 | 25 | 126 | 2099 | 166 | 13 | 206 | 25 | 246 | 380 | 286 | 546 | 326 | 31 | 366 | 558
7 | 4 | 47 | 4 | 87 | 41 | 127 | 12 | 167 | 4 | 207 | 177 | 247 | 153 | 287 | 109 | 327 | 81 | 367 | 8
8 | 10 | 48 | 1033 | 88 | 334 | 128 | 2989 | 168 | 12494 | 208 | 3256 | 248 | 658 | 288 | 218905 | 328 | 694 | 368 | 2030
9 | 7 | 49 | 21 | 89 | 8 | 129 | 53 | 169 | 43 | 209 | 79 | 249 | 27 | 289 | 31 | 329 | 53 | 369 | 373
10 | 10 | 50 | 79 | 90 | 1581 | 130 | 457 | 170 | 411 | 210 | 8339 | 250 | 558 | 290 | 457 | 330 | 8339 | 370 | 679
11 | 4 | 51 | 35 | 91 | 97 | 131 | 8 | 171 | 283 | 211 | 16 | 251 | 8 | 291 | 83 | 331 | 16 | 371 | 81
12 | 32 | 52 | 91 | 92 | 61 | 132 | 1397 | 172 | 119 | 212 | 91 | 252 | 23526 | 292 | 180 | 332 | 61 | 372 | 2745
13 | 6 | 53 | 6 | 93 | 53 | 133 | 99 | 173 | 6 | 213 | 53 | 253 | 53 | 293 | 6 | 333 | 442 | 373 | 12
14 | 13 | 54 | 232 | 94 | 13 | 134 | 25 | 174 | 284 | 214 | 13 | 254 | 37 | 294 | 3327 | 334 | 13 | 374 | 467
15 | 21 | 55 | 41 | 95 | 61 | 135 | 854 | 175 | 353 | 215 | 81 | 255 | 1051 | 295 | 41 | 335 | 81 | 375 | 1464
16 | 37 | 56 | 334 | 96 | 6719 | 136 | 442 | 176 | 3030 | 216 | 26202 | 256 | 14044 | 296 | 766 | 336 | 126762 | 376 | 334
17 | 5 | 57 | 40 | 97 | 12 | 137 | 8 | 177 | 27 | 217 | 125 | 257 | 9 | 297 | 1063 | 337 | 20 | 377 | 133
18 | 42 | 58 | 19 | 98 | 128 | 138 | 188 | 178 | 25 | 218 | 37 | 258 | 366 | 298 | 19 | 338 | 262 | 378 | 20441
19 | 6 | 59 | 4 | 99 | 177 | 139 | 8 | 179 | 4 | 219 | 82 | 259 | 153 | 299 | 81 | 339 | 69 | 379 | 16
20 | 47 | 60 | 1103 | 100 | 563 | 140 | 2142 | 180 | 17888 | 220 | 2142 | 260 | 3590 | 300 | 24672 | 340 | 3275 | 380 | 3181
21 | 27 | 61 | 12 | 101 | 9 | 141 | 27 | 181 | 18 | 221 | 119 | 261 | 275 | 301 | 125 | 341 | 145 | 381 | 79
22 | 13 | 62 | 25 | 102 | 243 | 142 | 25 | 182 | 658 | 222 | 421 | 262 | 25 | 302 | 37 | 342 | 3168 | 382 | 25
23 | 4 | 63 | 187 | 103 | 8 | 143 | 81 | 183 | 81 | 223 | 8 | 263 | 4 | 303 | 61 | 343 | 113 | 383 | 4
24 | 172 | 64 | 657 | 104 | 514 | 144 | 21451 | 184 | 334 | 224 | 13299 | 264 | 12494 | 304 | 3027 | 344 | 658 | 384 | 319416
25 | 13 | 65 | 67 | 105 | 670 | 145 | 67 | 185 | 100 | 225 | 2096 | 265 | 67 | 305 | 133 | 345 | 670 | 385 | 1318
26 | 19 | 66 | 147 | 106 | 19 | 146 | 37 | 186 | 366 | 226 | 31 | 266 | 672 | 306 | 2683 | 346 | 19 | 386 | 43
27 | 25 | 67 | 8 | 107 | 4 | 147 | 289 | 187 | 69 | 227 | 4 | 267 | 55 | 307 | 12 | 347 | 4 | 387 | 369
28 | 61 | 68 | 77 | 108 | 2219 | 148 | 135 | 188 | 61 | 228 | 2071 | 268 | 119 | 308 | 2715 | 348 | 2157 | 388 | 181
29 | 6 | 69 | 27 | 109 | 12 | 149 | 6 | 189 | 1225 | 229 | 12 | 269 | 6 | 309 | 53 | 349 | 12 | 389 | 6
30 | 147 | 70 | 281 | 110 | 281 | 150 | 2124 | 190 | 415 | 230 | 281 | 270 | 14283 | 310 | 549 | 350 | 4128 | 390 | 14253
31 | 8 | 71 | 8 | 111 | 61 | 151 | 12 | 191 | 8 | 231 | 839 | 271 | 16 | 311 | 8 | 351 | 1949 | 391 | 69
32 | 151 | 72 | 2311 | 112 | 2030 | 152 | 496 | 192 | 45694 | 232 | 514 | 272 | 2872 | 312 | 20014 | 352 | 13299 | 392 | 7641
33 | 27 | 73 | 12 | 113 | 10 | 153 | 238 | 193 | 14 | 233 | 8 | 273 | 1611 | 313 | 16 | 353 | 12 | 393 | 53
34 | 16 | 74 | 28 | 114 | 277 | 154 | 360 | 194 | 37 | 234 | 3267 | 274 | 25 | 314 | 37 | 354 | 188 | 394 | 28
35 | 41 | 75 | 185 | 115 | 41 | 155 | 81 | 195 | 1142 | 235 | 41 | 275 | 395 | 315 | 8717 | 355 | 81 | 395 | 81
36 | 284 | 76 | 90 | 116 | 91 | 156 | 2157 | 196 | 904 | 236 | 61 | 276 | 1397 | 316 | 119 | 356 | 121 | 396 | 22162
37 | 9 | 77 | 53 | 117 | 291 | 157 | 12 | 197 | 9 | 237 | 53 | 277 | 12 | 317 | 6 | 357 | 1152 | 397 | 18
38 | 19 | 78 | 284 | 118 | 13 | 158 | 25 | 198 | 1989 | 238 | 467 | 278 | 25 | 318 | 284 | 358 | 13 | 398 | 37
39 | 41 | 79 | 8 | 119 | 69 | 159 | 41 | 199 | 12 | 239 | 8 | 279 | 369 | 319 | 81 | 359 | 4 | 399 | 1601
40 | 262 | 80 | 1646 | 120 | 10130 | 160 | 11256 | 200 | 4973 | 240 | 107165 | 280 | 19935 | 320 | 80768 | 360 | 257731 | 400 | 51694

In terms of enumerating Schur rings over $G$, Schurian rings are somewhat
problematic because they depend upon subgroups of $\text{Sym}(G)$ which are
external to $G$ and do not lead to recursive methods. Instead, this paper will
employ an alternative classification of Schur rings given by Leung and Man
[19, 20], which were coined _traditional Schur rings_ in [3] (see Section 2).
In the 1990’s, Leung, Man, and others (e.g., [18, 24, 25, 26]) investigated
how cyclic Schur rings could be classified internally, namely using subgroups
and quotients. This internal classification444It should be noted that the
classification of Schurian groups does not necessarily inhibit enumeration.
Lang in [17] using the classificiation of Schurian abelian groups in [10] to
enumerate supercharacter theories over groups of the form
$\mathcal{Z}_{p}\times\mathcal{Z}_{2}\times\mathcal{Z}_{2}$. Hendrickson [12]
showed that supercharacter theories of a group are equivalent to the central
Schur rings of that group. Much work of late has been made to classify
supercharacter theories, e.g., [1, 2, 5] which is parallel to these efforts to
classify and enumerate Schur rings. of Schur rings better allows for recursion
in our enumeration and will be the foundation of our technique.

The general technique of counting Schur rings over cyclic groups comes from
the following basic strategy. By the Fundamental Theorem of Schur Rings over
Cyclic Groups proven by Leung and Man (see Theorem 2.1), all Schur rings over
cyclic groups are traditional. The MAGMA code recursively enumerates all
traditional Schur rings over the subquotients of $\mathcal{Z}_{n}$ and checks
for _wedge-compatibility_. _Indecomposable_ Schur rings are classified and
wedge-compatiability is considered to develop recursive relations on the
number of Schur rings over subquotients of $\mathcal{Z}_{n}$. From here, wedge
and direct products of Schur rings are considered using this recursion. In
regard to proving counting formulas, a similar approach is taken. As this
manuscript is primarily survey in nature, many details are omitted for the
sake of brevity, but great efforts have also been made to include sufficient
details to make this enumeration technique self-contained. The reader should
consult the extensive bibliography for further details.

The author wants to personally thank Stephen P. Humphries for his very
appreciated technical assistance rendered for the enumeration of
$\mathcal{Z}_{288}$ and all orders above $300$. The author would like also to
thank Brent Kerby whose code in [15] offered inspiration of the code used
herein. Finally, the author wants to thank the anonymous referee whose helpful
comments significantly improved this manuscript.

##  2 Traditional Schur Rings

We begin with examples of Schur rings that are important for classifying Schur
rings over cyclic groups.

Given a finite group $G$, the partition of the group into singletons, that is,
$\\{\\{g\\}\mid g\in G\\}$, affords a Schur ring structure called the
_discrete Schur ring_. Note that this is just the group algebra
$\mathbb{Q}[G]$ itself. As the coefficient ring will play little role here, we
will abuse notation by using $G$ to both denote the group $G$ and the group
ring $\mathbb{Q}[G]$, when the context is clear. Another example is the
partition $\\{1,G\smallsetminus 1\\}$. We call this Schur ring the _trivial
Schur ring_ and denote it as $G^{0}$. For any finite group, the discrete and
trivial Schur rings are always available. In the case of $\mathcal{Z}_{1}$ and
$\mathcal{Z}_{2}$, they are one and the same (in fact, there is only one Schur
ring over both $\mathcal{Z}_{1}$ and $\mathcal{Z}_{2}$). Otherwise, they are
distinct.

Let $\operatorname{Aut}(G)$ be the automorphism group of $G$, and let
$\mathcal{H}\leq\operatorname{Aut}(G)$. Then $\mathcal{H}$ partitions $G$
according to the automorphic action of $\mathcal{H}$ on $G$, via the
$\mathcal{H}$-orbits. This Schur ring is called an _automorphic Schur ring_
555Automorphic Schur ring are also commonly referred to as _orbit Schur rings_
, as was the case in [22] and is denoted $G^{\mathcal{H}}$. Note that the
discrete Schur ring is automorphic where $\mathcal{H}=1$. The center of the
group algebra, namely $Z(\mathbb{Q}[G])$, is likewise an automorphic Schur
ring associated to the subgroup of inner automorphisms $\text{Inn}(G)$.

Let $H\subseteq G$ and let $\mathfrak{S}$ be a Schur ring over $G$. We say
that $H$ is an _$\mathfrak{S}$ -subset_ if $H$ is a union of primitive sets of
$\mathfrak{S}$. We say $H$ is an _$\mathfrak{S}$ -subgroup_ if $H$ is both a
subgroup of $G$ and an $\mathfrak{S}$-subset. Note that the family of all
$\mathfrak{S}$-subsets forms a sublattice of the power set of $G$. Likewise,
if $\mathcal{L}(G)$ denotes the lattice of all subgroups of $G$, then the
family of all $\mathfrak{S}$-subgroups form a sublattice of $\mathcal{L}(G)$.

We say a Schur ring is _primitive_ if the only $\mathfrak{S}$-subgroups are
$1$ and $G$. The trivial Schur ring is primitive and all Schur rings over
$\mathcal{Z}_{p}$, where $p$ is a prime, are necessarily primitive. Wielandt
[34] showed that these are the only primitive Schur rings over cyclic groups.

For a Schur ring $\mathfrak{S}$ and an $\mathfrak{S}$-subgroup $H$, let
$\mathfrak{S}_{H}:=\mathfrak{S}\cap H$ be the Schur ring over $H$ associated
to the partition of $H$ given by

$\mathcal{D}(\mathfrak{S}_{H})=\\{C\in\mathcal{D}(\mathfrak{S})\mid C\subseteq
H\\}.$

We say that a Schur ring $\mathfrak{T}$ is a _Schur subring_ of $\mathfrak{S}$
if $\mathfrak{T}=\mathfrak{S}_{H}$ for some $\mathfrak{S}$-subgroup $H$. As
the subgroups of $\mathcal{Z}_{n}$ are uniquely determined by its order, if
$\mathfrak{S}$ is a Schur ring over $\mathcal{Z}_{n}$ and $H$ is an
$\mathfrak{S}$-subgroup, then $\mathfrak{S}_{|H|}:=\mathfrak{S}_{H}$.

For automorphic Schur rings $\mathfrak{S}=G^{\mathcal{H}}$, the
$\mathfrak{S}$-subgroups are exactly the $\mathcal{H}$-invariant subgroups of
$G$, which includes all characteristic subgroups. Hence, if $\mathfrak{S}$ is
an automorphic Schur ring over $G$ with $\mathfrak{S}$-subgroup $K$, then
$S_{K}=K^{\mathcal{H}}$ which is necessarily automorphic itself.

For any group homomorphism $\varphi:G\to H$, this map lifts to a map on group
algebras $\varphi:\mathbb{Q}[G]\to\mathbb{Q}[H]$ by the rule
$\varphi\left(\sum_{g}\alpha_{g}g\right)=\sum_{g}\alpha_{g}\varphi(g)\in\mathbb{Q}[H]$.
Let $\mathfrak{S}$ be a Schur ring over $G$. If $\ker\varphi$ is an
$\mathfrak{S}$-subgroup, then $\varphi(\mathfrak{S})$ is a Schur ring over
$\varphi(G)$. In particular, the associated partition of
$\varphi(\mathfrak{S})$ is

$\mathcal{D}(\varphi(\mathfrak{S}))=\\{\varphi(C)\mid
C\in\mathcal{D}(\mathfrak{S})\\}.$

If $\mathfrak{T}$ is a Schur ring over $H$ such that $\varphi(G)$is a
$\mathfrak{T}$-subgroup and $\mathfrak{T}_{\varphi(G)}=\varphi(\mathfrak{S})$,
then $\varphi:\mathfrak{S}\to\mathfrak{T}$ induces a homomorphism between
Schur rings. In the case that $\varphi:K\hookrightarrow G$ is the natural
inclusion map, then $\varphi:\mathfrak{S}_{K}\hookrightarrow\mathfrak{S}$
becomes the inclusion map on Schur rings.

Suppose $G$ is a direct product of two groups, say $G=H\times K$. Let
$\mathfrak{S}$ and $\mathfrak{T}$ be Schur rings over $H$ and $K$,
respectively. Then the _direct product_ 666These Schur rings are also known as
tensor products, as in [31]. of Schur rings, denoted by
$\mathfrak{S}\times\mathfrak{T}$, is given by the partition

$\mathcal{D}(\mathfrak{S}\times\mathfrak{T})=\\{CD\mid
C\in\mathcal{D}(\mathfrak{S}),D\in\mathcal{D}(\mathfrak{T})\\},$

where $CD$ is viewed as a subset of $G$. By construction, $H$ and $K$ are both
$\mathfrak{S}\times\mathfrak{T}$-subgroups. In fact,
$(\mathfrak{S}\times\mathfrak{T})_{H}=\mathfrak{S}$ and
$(\mathfrak{S}\times\mathfrak{T})_{K}=\mathfrak{T}$. The direct product is the
smallest Schur ring over $G$ with this property. The usual group projections
$\pi_{1}:H\times K\to H$ and $\pi_{2}:H\times K\to K$ induce Schur ring
projections $\pi_{1}:\mathfrak{S}\times\mathfrak{T}\to\mathfrak{S}$ and
$\pi_{2}:\mathfrak{S}\times\mathfrak{T}\to\mathfrak{T}$.

If ${h}\in\mathcal{D}(\mathfrak{S})$ for some Schur ring $\mathfrak{S}$ over
$G$, then $hC\in\mathcal{D}(\mathfrak{S})$ for all
$C\in\mathcal{D}(\mathfrak{S})$. Likewise, the collection of singletons in
$\mathcal{D}(\mathfrak{S})$ forms an $\mathfrak{S}$-subgroup $H$ of $G$. Of
course, $\mathfrak{S}_{H}=H$, that is, $\mathfrak{S}_{H}$ is discrete.
Furthermore, if $G=H\times K$ and $\mathfrak{S}$ is a Schur ring over $G$ such
that $H,K$ are $\mathfrak{S}$-subgroups and $\mathfrak{S}_{H}$ is discrete,
then
$\mathfrak{S}=\mathfrak{S}_{H}\times\mathfrak{S}_{K}=H\times\mathfrak{S}_{K}$.777This
fact was proven in [10] in the case of abelian groups, but the commutativity
assumption can be dropped with no loss.

For a Schur ring $\mathfrak{S}$, we say that an $\mathfrak{S}$-subgroup $K$ is
_normal_ if $K\trianglelefteq G$. Let $\varphi:G\to G/K$ be the natural map.
Then we call the Schur ring $\varphi(\mathfrak{S})$ the _quotient Schur ring_
of $\mathfrak{S}$ over $G/K$ and denote it as $\mathfrak{S}/K$.

Conversely, if $\varphi:G\to H$ is a group homomorphism and $\mathfrak{T}$ is
a Schur ring over $H$, then define

$\varphi^{-1}(\mathfrak{T}):=\operatorname{Span}\\{\varphi^{-1}(C)\mid
C\in\mathcal{D}(\mathfrak{T})\\}.$

It is elementary to show that $\varphi^{-1}(\mathfrak{T})$ is closed under $*$
and multiplication, but, the class containing the identity is $\ker\varphi$,
which, in general, is not $1$. As such, we call $\varphi^{-1}(\mathfrak{T})$ a
_pre-Schur ring_. Note that all primitive sets in $\varphi^{-1}(\mathfrak{T})$
are unions of cosets of $\ker\varphi$.

We say that $[K,H]$ is an _$\mathfrak{S}$ -section_ if $1\leq K\leq H\leq G$,
$K\trianglelefteq G$, and $H,K$ are $\mathfrak{S}$-subgroups. We say that a
section $[K,H]$ is _proper_ if $1<K\leq H<G$, and we say that $[K,H]$ is
_trivial_ if $K=H$. As all subgroups of $\mathcal{Z}_{n}$ are normal and
uniquely determined by their orders, we shall denote the section
$[\mathcal{Z}_{d},\mathcal{Z}_{e}]$ simply as $[d,e]$.

We say that $\mathfrak{S}$ is _wedge-decomposable_ if there exists a proper
$\mathfrak{S}$-section $[K,H]$ such that for every $\mathfrak{S}$-class $C$
either $C\subseteq H$ or $C$ is a union of cosets of $K$. Otherwise,
$\mathfrak{S}$ is _wedge-indecomposable_.

Let $U=[K,H]$ be a proper section of $G$. We say a pair of Schur rings
$\mathfrak{S}$ and $\mathfrak{T}$ over $H$ and $G/K$, respectively, are
_wedge-compatible_ if $K$ is an $\mathfrak{S}$-subgroup, $H/K$ is a
$\mathfrak{T}$-subgroup, and $\mathfrak{S}/K=\mathfrak{T}_{H/K}$. Then the
_wedge product_ 888The wedge product was first introduced by Leung and Man
[20]. In [8], Evdokimov and Ponomarenko independently introduce the similar
notion of a _(generalized) wreath product_. of two wedge-compatible Schur
rings $\mathfrak{S}$ and $\mathfrak{T}$, denoted
$\mathfrak{S}\wedge_{U}\mathfrak{T}$, is given by the rule
$\mathfrak{S}\wedge_{U}\mathfrak{T}:=\mathfrak{S}+\varphi^{-1}(\mathfrak{T})$,
where $\varphi:G\to G/K$ is the natural map. Note that

$\mathcal{D}(\mathfrak{S}\wedge_{U}\mathfrak{T})=\mathcal{D}(\mathfrak{S})\cup\\{\varphi^{-1}(C)\subseteq
G\smallsetminus H\mid C\in\mathcal{D}(\mathfrak{T})\\}.$

Note that by construction $U$ is an
$\mathfrak{S}\wedge_{U}\mathfrak{T}$-section,
$(\mathfrak{S}\wedge_{U}\mathfrak{T})_{H}=\mathfrak{S}$, and
$(\mathfrak{S}\wedge_{U}\mathfrak{T})/K=\mathfrak{T}$. The wedge product is,
in fact, the smallest Schur ring over $G$ with this property. Furthermore,
Schur rings over $G$ can be factored as a wedge product if and only if the
Schur ring is wedge-decomposable.

With a trivial section wedge-compatibility is automatic. Thus, if $G$ is any
group extension of $Q$ by $N$, then we may form the wedge product
$S\wedge_{[N,N]}\mathfrak{T}$ over $G$ where $\mathfrak{S}$ and $\mathfrak{T}$
are any Schur rings over $N$ and $Q$, respectively. In this case, the
subscript is omitted and the product is denoted simply as
$\mathfrak{S}\wedge\mathfrak{T}$.

Finally, we say that a Schur ring over $G$ is _traditional_ if the Schur ring
can be recursively built using automorphic and trivial Schur rings over
sections of $G$ via the operations of direct products and wedge products. In
other words, a Schur ring is traditional if it belongs to one of four Schur
ring families: trivial Schur rings, automorphic Schur rings, direct products,
or wedge products. Leung and Man show in [19] the following important
classification of Schur rings over cyclic groups.

######  Theorem 2.1 (The Fundamental Theorem of Schur Rings over Cyclic
Groups).

All Schur rings over the finite999In [3], this result is extended to the
infinite cyclic group, among others. cyclic group $\mathcal{Z}_{n}$ are
traditional.

##  3 Counting Schur Rings

In order to compute $\Omega(n)$, we use the above Fundamental Theorem and
count the number of Schur rings of each of the four families of traditional
rings, with particular attention on what conditions cause them to overlap.

For any $n$, there is exactly one trivial Schur ring. As it is primitive, the
trivial Schur rings $\mathcal{Z}_{n}^{0}$ will never be wedge-decomposable nor
factorable as a direct product, since both products require a proper subgroup
which is absent for primitive Schur rings. In the case that $n=p$,
$\mathcal{Z}_{p}^{0}=\mathcal{Z}_{p}^{\operatorname{Aut}(\mathcal{Z}_{p})}$.
If $n$ is not prime, then elements of different orders in
$\mathcal{Z}_{n}^{0}$ are fused together, a feature impossible in any
automorphic Schur ring. Hence, the trivial Schur ring is automorphic if and
only if the group has prime order. Thus, the trivial Schur ring will
contribute a single count to $\Omega(n)$ and is distinct from the other three
traditional families for composite orders.

Let $n=ab$ be a unitary factorization, that is, $\gcd(a,b)=1$. The number of
direct product Schur rings over $\mathcal{Z}_{n}$ with respect to this
factorization will be $\Omega(a)\Omega(b)$, since each such Schur ring has the
form $\mathfrak{S}\times\mathfrak{T}$, where $\mathfrak{S}$ and $\mathfrak{T}$
are Schur rings over $\mathcal{Z}_{a}$ and $\mathcal{Z}_{b}$, respectively.
One can enumerate all direct product Schur rings over $\mathcal{Z}_{n}$ by
enumerating all unitary factorizations of $n$. As the direct product is an
associative, commutative operator on groups, a typical inclusion-exclusion
argument is necessary when $n$ has at least three prime divisors. For example,
the number of direct product Schur rings over $\mathcal{Z}_{pqr}$ would be
$\Omega(p)\Omega(qr)+\Omega(q)\Omega(pr)+\Omega(r)\Omega(pq)-2\Omega(p)\Omega(q)\Omega(r).$

Let $H$ and $K$ be groups and let $\mathcal{H}\leq\operatorname{Aut}(H)$ and
$\mathcal{K}\leq\operatorname{Aut}(K)$. If $G=H\times K$, then we may
naturally view $\mathcal{H}\times\mathcal{K}$ as a subgroup of
$\operatorname{Aut}(G)$ by the following rule. If $\sigma\in\mathcal{H}$ and
$\tau\in\mathcal{K}$, then define the map $\sigma\times\tau:H\times K\to
H\times K$ as $(h,k)^{\sigma\times\tau}=(h^{\sigma},k^{\tau})$. If follows
that $\mathfrak{S}\times\mathfrak{T}$ is automorphic if and only if
$\mathfrak{S}$ and $\mathfrak{T}$ are automorphic.

The automorphic Schur rings over $\mathcal{Z}_{n}$ are in Galois
correspondence with the subgroups of
$\operatorname{Aut}(\mathcal{Z}_{n})$.101010See Equation (3.1) in [22]. Let
$U(n)$ denote the set of units of the finite ring $\mathbb{Z}_{n}$, that is,
integers modulo $n$. Thus, $U(n)$ is the set of integers coprime to $n$. It is
clear that $\operatorname{Aut}(\mathcal{Z}_{n})\cong U(n)$ and

$U(n)=\prod_{i=1}^{r}U(p_{i}^{e_{i}}),$

where $n=\prod_{i=1}^{r}p_{i}^{e_{i}}$ is the prime factorization of $n$.
Hence, counting automorphic Schur rings over $\mathcal{Z}_{n}$ is equivalent
to computing $|\mathcal{L}(U(n))|$.

Note, $U(n)$ is cyclic if and only if $n=p^{k}$ or $n=2p^{k}$. In this case
$\mathcal{L}(U(n))$ decomposes into a tower of sublattices, which we call
_layers_ , where each layer is lattice-isomorphic to $U(p)$ and sits on top of
the previous layer by degree $p$ extensions. Additionally, $U(p)$ is
isomorphic to the divisor lattice associated to $p-1$. If $x$ is the number of
divisors of $p-1$, then the number of automorphic Schur rings over
$\mathcal{Z}_{p^{k}}$ or $\mathcal{Z}_{2p^{k}}$ is $(k-1)x$.

The general problem of enumerating automorphic Schur rings over
$\mathcal{Z}_{n}$ is much more difficult, as every abelian group is a subgroup
of $U(n)$ for some sufficiently large $n$. The problem of counting the number
of subgroups of an arbitrary abelian group is a well studied problem in the
literature, for example [27], [28], and [32], which essentially all derive
from a theorem of Goursat [11]. Our consideration of this problem will follow
the method of Călugăreanu [6]. We say that two sections $U=[K,H]$ and
$U^{\prime}=[K^{\prime},H^{\prime}]$ over $G$ and $G^{\prime}$, respectively,
are _isomorphic_ , if $H/K\cong H^{\prime}/K^{\prime}$. If $G=H\times K$, we
say a subgroup $D$ is _diagonal_ if
$D\in\mathcal{L}(G)\smallsetminus(\mathcal{L}(H)\times\mathcal{L}(K))$. As
shown in [6], diagonal subgroups of $G=H\times K$ correspond exactly to
automorphisms between isomorphic, non-trivial sections of the lattices
$\mathcal{L}(H)$ and $\mathcal{L}(K)$. If $\gcd(|H|,|K|)=1$ then it follows
that $\mathcal{L}(H\times K)\cong\mathcal{L}(H)\times\mathcal{L}(K)$. Thus, it
suffices to consider the case that $H$ and $K$ are both cyclic $p$-groups. We
illustrate Călugăreanu’s technique below.

######  Example 3.1.

In $\mathcal{Z}_{4}\times\mathcal{Z}_{4}$ there are 6 diagonal subgroups. To
see this, note that the sections in $\mathcal{Z}_{4}$ are $[1,2]$, $[2,4]$,
and $[1,4]$. The first two sections are isomorphic to $\mathcal{Z}_{2}$. Since
there is only one automorphism over $\mathcal{Z}_{2}$, $1\cdot 2\cdot 2=4$ of
the diagonal subgroups arise from the combinations of $[1,2]$ and $[2,4]$. The
last $2\cdot 1\cdot 1=2$ come from there being two automorphisms over
$\mathcal{Z}_{4}$ and the single combination of $[1,4]$ and itself. Given that
$|\mathcal{L}(\mathcal{Z}_{4})|=3$, this shows that
$|\mathcal{L}(\mathcal{Z}_{4}\times\mathcal{Z}_{4})|=3^{2}+6=15$.

######  Lemma 3.2 ([6]).

The number of subgroups of $\mathcal{Z}_{p^{k}}\times\mathcal{Z}_{p^{\ell}}$
is given as

$\left|\mathcal{L}\middle(\mathcal{Z}_{p^{k}}\times\mathcal{Z}_{p^{\ell}}\middle)\right|=\sum_{j=0}^{\min(k,\ell)}\phi(p^{j})(k-j+1)(\ell-j+1),$

where $\phi$ denotes Euler’s totient function.

Note that for $\mathcal{Z}_{4}\times\mathcal{Z}_{4}$, we see that

$|\mathcal{L}(\mathcal{Z}_{4}\times\mathcal{Z}_{4})|=1(3)(3)+1(2)(2)+2(1)(1)=15,$

which agrees with Example 3.1.

If $\mathfrak{S}$ is wedge-decomposable with section $[K,H]$, then
$\mathfrak{S}$ is likewise decomposable for the section $[K^{\prime},H]$ where
$K^{\prime}\trianglelefteq G$ and $K^{\prime}\leq K$. Thus, it is advantageous
to choose $K$ to be a minimal normal subgroup to avoid unnecessary over-
counting of the same wedge product that can be formed from distinct sections.
In [22], the section $[p,p^{j}]$ was used, where $j$ was allowed to vary, for
this very reason. For general $n$, when the subgroup $H$ has multiple prime
divisors, there are multiple minimal subgroup choices for $K$ and an
inclusion-exclusion argument is again necessary.

When enumerating direct product Schur rings, it is important to observe that
if $G=H\times K$ is a group and
$\mathfrak{S}=\mathfrak{S}_{H}\times\mathfrak{S}_{K}$ is a direct product
Schur ring over $G$ such that $\mathfrak{S}_{H}$ is wedge-decomposable, then
$\mathfrak{S}$ is itself wedge-decomposable.111111This is immediate
consequence of [9, Theorem 4.1], but an elementary argument using sections is
also possible allowing for the assumption that $G$ is cyclic to be removed.
Hence, it suffices to count only those with wedge-indecomposable direct
factors, as any complete enumeration of wedge products will contain the rest.
The indecomposable Schur rings are necessarily then trivial, automorphic, or
direct products of indecomposable factors. Hence, the trivial and
indecomposable automorphic Schur rings will be the atomic building blocks for
all higher Schur rings over cyclic groups.

For $\mathcal{Z}_{p^{k}}$, the indecomposable Schur rings include the trivial
ring $\mathcal{Z}_{p^{k}}^{0}$ and the top-layer automorphic rings,121212Such
Schur rings were considered in [8] using a different approach. In particular,
they showed that a Schur ring over a cyclic group is indecomposable if and
only if its radical is trivial. In the case of orbit Schur rings, it is shown
that this occurs exactly when the associated automorphic group’s order is
coprime to to $p$. Most arguments involving the representation $\omega$ in
this manuscript could be alternatively argued using this radical. that is,
those automorphic Schur rings that correspond to the subgroups of $U(p)$
viewed as a subgroup of $U(p^{k})$. To see this, consider the representation
$\omega:\mathbb{Q}[\mathcal{Z}_{n}]\to\mathbb{Q}(\zeta_{n})$ afforded by the
rule $z\mapsto\zeta_{n}$, where $\zeta_{n}$ is a complex, primitive $n$th root
of unity and $\mathbb{Q}(\zeta_{n})$ is the associated cyclotomic
field.131313Because of this representation by cyclotomic fields, automorphic
Schur rings over a cyclic group are often called _cyclotomic_ in the
literature. See [8, 23, 10]. For a Schur ring $\mathfrak{S}$,
$\omega(\mathfrak{S})$ is necessarily a subfield of $\mathbb{Q}(\zeta_{n})$
and, as $U(n)$ is the Galois group of $\mathbb{Q}(\zeta_{n})$ over
$\mathbb{Q}$, the correspondence between automorphic Schur rings and the
subgroups of $U(n)$ is identical to the Galois correspondence of subfields of
$\mathbb{Q}(\zeta_{n})$ with subgroups of $U(n)$. Note that141414See [22,
Equations (3.1)–(3.3)]. Direct products were not considered here because
$\mathcal{Z}_{p^{k}}$ has not such factorization.
$\omega(\mathcal{Z}_{n}^{0})=\mathbb{Q}$,
$\omega(\mathcal{Z}_{n}^{\mathcal{H}})=\mathbb{Q}(\zeta_{n})^{\mathcal{H}}$,
and $\omega(\mathfrak{S}_{H}\wedge\mathfrak{S}/K)=\omega(\mathfrak{S}_{H})$.
Likewise, $\omega(\mathfrak{S}_{m})\subseteq\mathbb{Q}(\zeta_{m})$. In
particular, a wedge-decomposable ring cannot map into the _top-layer_ of
$\mathbb{Q}(\zeta_{n})$, those subfields of $\mathbb{Q}(\zeta_{n})$ which are
not subfields of $\mathbb{Q}(\zeta_{d})$ for any proper divisor $d$ of $n$.
This implies that those rings which do map to the top-layer are
indecomposable, as claimed.

We can also consider the $\omega$-image of a direct product. Recall that
$\mathfrak{S}\times\mathfrak{T}$ is the compositum ring of $\mathfrak{S}$ and
$\mathfrak{T}$. As such, $\omega$ will map $\mathfrak{S}\times\mathfrak{T}$
onto the compositum field of $\omega(\mathfrak{S})$ and $\omega(\mathfrak{T})$
in $\mathbb{Q}(\zeta_{n})$, that is,

$\omega(\mathfrak{S}\times\mathfrak{T})=\omega(\mathfrak{S})\vee\omega(\mathfrak{T})\cong\omega(\mathfrak{S})\otimes_{\mathbb{Q}}\omega(\mathfrak{T}).$
(3.1)

As mentioned above, if
$\mathfrak{S}=\mathfrak{S}_{H^{\prime}}\wedge_{[K^{\prime},H^{\prime}]}\mathfrak{S}/K^{\prime}$
is wedge-decomposable, then
$\omega(\mathfrak{S})=\omega(\mathfrak{S}_{H^{\prime}})$. If
$\mathfrak{S}_{H^{\prime}}$ is itself wedge-decomposable over the section
$[K^{\prime\prime},H^{\prime\prime}]$, then
$\omega(\mathfrak{S})=\omega(\mathfrak{S}_{H^{\prime\prime}})$. As these
groups are finite, this process will eventually terminate, and there exists an
$\mathfrak{S}$-subgroup $H$ such that
$\omega(\mathfrak{S})=\omega(\mathfrak{S}_{H})$ and $\mathfrak{S}_{H}$ is
indecomposable. Let $H$ be the maximal such subgroup. Then
$\mathfrak{S}_{H}=\mathcal{Z}_{d}^{\mathcal{H}}\times\prod_{i=1}^{k}\mathcal{Z}_{d_{i}}^{0}$,
where any of the divisors $d_{0},d_{1},\ldots$ could be 1. This will be the
unique, maximal wedge-indecomposable Schur subring of $\mathfrak{S}$, which we
call the _wedge-core_ of $\mathfrak{S}$. Two Schur rings with distinct cores
are necessarily distinct. If $\mathfrak{S}$ is itself indecomposable, then it
is equal to its own core. Every Schur ring $\mathfrak{S}$ over a non-trivial
cyclic group will have a non-trivial core as the core will contain all the
Schur subrings over the minimal $\mathfrak{S}$-subgroups. We will enumerate
the possible cores of Schur rings to avoid situations when two different wedge
decompositions give rise to the same partition of $\mathcal{Z}_{n}$.

Let $\Omega(n,\mathfrak{S})$ denote the number of Schur rings over
$\mathcal{Z}_{n}$ that contain the Schur ring $\mathfrak{S}$ as its wedge-
core. We let $\Omega(n,d)$151515Note that this notation has a slightly
different meaning in [22], for which the present paper generalizes the
situation considered in the former. abbreviate $\Omega(n,\mathcal{Z}_{d})$. If
$\mathfrak{S}\wedge_{[K,H]}\mathfrak{T}$ is a wedge product, then it must be
that $\mathfrak{S}/K=\mathfrak{T}_{H/K}$. If we keep $\mathfrak{S}$ fixed,
then $\mathfrak{T}$ may be any Schur ring over $G/K$ so long as the Schur
subring $\mathfrak{T}_{H/K}$ is exactly $\mathfrak{S}/K$. Of course, if
$\mathfrak{S}$ is an indecomposable Schur ring over $\mathcal{Z}_{n}$, then
$\Omega(n,\mathfrak{S})=1$.

######  Lemma 3.3.

If $\mathfrak{S}$ is a primitive Schur ring over $\mathcal{Z}_{d}$ and $d\mid
n$, then $\Omega(n,\mathfrak{S})=\Omega(n/d)$.

###### Proof.

If $\mathfrak{S}\wedge_{U}\mathfrak{T}$ is a Schur ring over $\mathcal{Z}_{n}$
with section $U=[K,H]$, then $K=H$ by the primitivity of $\mathfrak{S}$. As
this is a trivial section, wedge-compatibility is automatic. Thus,
$\mathfrak{T}$ could be any Schur ring over
$\mathcal{Z}_{n}/\mathcal{Z}_{d}\cong\mathcal{Z}_{n/d}$. ∎

##  4 Examples of Enumerating Schur Rings over Cyclic Groups

Using the strategies from the previous section, we consider some examples of
enumerating Schur rings over cyclic groups. The first two can be found in
[22].

######  Example 4.1.

Let $p$ be an odd prime and let $x$ be the number of divisors of $p-1$. Then
$\Omega(p)=x$, as all Schur rings over $\mathcal{Z}_{p}$ are automorphic,
including the trivial one, and these Schur rings are in one-to-one
correspondence with the divisors of $p-1$.

Let $n=p^{k}$ for $k>1$. Then the indecomposable Schur rings over
$\mathcal{Z}_{p^{k}}$ are $\mathcal{Z}_{p^{k}}^{0}$ and those $x$-many top-
layer automorphic Schur rings. In [22, Lemma 4.4], we see that for Schur rings
$\mathfrak{S}$ and $\mathfrak{T}$ over $\mathcal{Z}_{p^{k}}$ whose cores are
indecomposable automorphic Schur subrings of the same order $p^{j}$,
$\Omega(p^{k},\mathfrak{S})=\Omega(p^{k},\mathfrak{T})=\Omega(p^{k},p^{j})$.
This equality is based upon identical recursive relations on these different
functions. Note that for every order $p^{j}$, if
$\Omega(p^{k},\mathfrak{S})=\Omega(p^{k},p^{j})$ then there are exactly
$x=\Omega(p)$ many options for the core of $\mathfrak{S}$, namely the $x$
indecomposable automorphic Schur rings over $\mathcal{Z}_{p^{j}}$. Hence,

$\Omega(p^{k})=\sum_{j=1}^{k}(\Omega(p^{k},\mathcal{Z}_{p^{j}}^{0})+x\Omega(p^{k},p^{j}))-\Omega(p^{k},p).$

Of course, $\Omega(p^{k},\mathcal{Z}_{p^{j}}^{0})=\Omega(p^{k-j})$ and
$\Omega(p^{k},p)=\Omega(p^{k-1})$ by Lemma 3.3. Likewise,
$\Omega(p^{k},p^{k})=1$, as observed in the paragraph before Lemma 3.3.
Finally, by observing the recursive relation
$\Omega(p^{k},p^{j})=\sum_{i=j}^{k}\Omega(p^{k-1},p^{i-1})$ for $1<j<k$, we
may unravel the unravel the equation above into

$\Omega(p^{k})=x\Omega(p^{k-1})+\sum_{j=2}^{k}(c_{j-1}x+1)\Omega(p^{k-j}),$

where $c_{k}=\dfrac{1}{k+1}\dbinom{2k}{k}$ is the $k$th Catalan number. We
illustrate this formula for small powers of $p$. Of course, $\Omega(p)=x$. For
$n=p^{2}$,

$\Omega(p^{2})=x\Omega(p^{2},p)+\Omega(p^{2},\mathcal{Z}_{p^{2}}^{0})+x\Omega(p^{2},p^{2})=x\Omega(p)+\Omega(1)+x\cdot
1=x^{2}+x+1.$

For $n=p^{3}$,

$\Omega(p^{3})=x\Omega(p^{3},p)+\Omega(p^{3},\mathcal{Z}_{p^{2}}^{0})+x\Omega(p^{3},p^{2})+\Omega(p^{3},\mathcal{Z}_{p^{3}}^{0})+x\Omega(p^{3},p^{3})\\\
=x\Omega(p^{2})+\Omega(p)+x(\Omega(p^{2},p)+\Omega(p^{3},p^{3}))+\Omega(1)+x\cdot
1\\\ =x(x^{2}+x+1)+x+x(\Omega(p)+\Omega(1))+1+x\\\ =x^{3}+2x^{2}+4x+1.$

######  Example 4.2.

Let $p=2$. Of course, $\Omega(2)=1$, namely $\mathcal{Z}_{2}$ itself.
Similarly, $\Omega(4)=3$, namely $\mathcal{Z}_{4}^{0}$,
$\mathcal{Z}_{2}\wedge\mathcal{Z}_{2}$, and $\mathcal{Z}_{4}$. For $k>2$, we
note that $U(2^{k})\cong\mathcal{Z}_{2}\times\mathcal{Z}_{2^{k-1}}$. Unlike
the odd prime case, this automorphism group is non-cyclic and contains
diagonal subgroups. As such, the number of Schur rings which have
$\mathcal{Z}_{2^{j}}$ as its core will be distinct from the number of Schur
rings which have $\mathcal{Z}_{2^{j}}^{\pm}$, the automorphic Schur ring
corresponding to the inversion map, as its core. Hence,

$\Omega(2^{k})=\sum_{j=2}^{k}\Omega(2^{k},\mathcal{Z}_{2^{j}}^{0})+\Omega(2^{k},4)+\sum_{j=3}^{k}(\Omega(2^{k},2^{j})+2\Omega(2^{k},\mathcal{Z}_{2^{j}}^{\pm}).$

Some of the calculations are similar to the previous case, by virtue of Lemma
3.3, namely: $\Omega(2^{k},2^{k})=\Omega(2^{k},\mathcal{Z}_{2^{k}}^{\pm})=1$,
$\Omega(2^{k},\mathcal{Z}_{2^{j}}^{0})=\Omega(2^{k-j})$, and
$\Omega(2^{k},2)=\Omega(2^{k-1})$, but the remaining recursive relations are
much more complicated, namely:
$\Omega(2^{k},4)=\Omega(2^{k-1})-\sum_{j=1}^{k-2}\Omega(2^{k-2},\mathcal{Z}_{2^{j}}^{0})$,
$\Omega(2^{k},2^{j})=\sum_{i=j-1}^{k-1}\Omega(2^{k-1},2^{i})$,
$\Omega(2^{k},\mathcal{Z}_{2^{j}}^{\pm})=\Omega(2^{k-1},\mathcal{Z}_{2^{j-1}}^{\pm})+2\sum_{i=j}^{k-1}\Omega(2^{k-1},\mathcal{Z}_{2^{i}}^{\pm})$,
and
$\Omega(2^{k},\mathcal{Z}_{8}^{\pm})=\Omega(2^{k-1},4)+2\sum_{i=3}^{k-1}\Omega(2^{k-1},\mathcal{Z}_{2^{i}}^{\pm}).$
Unraveling the recursive relations, we have

$\Omega(2^{k})=\sum_{j=1}^{3}2^{j}\Omega(2^{k-j})-(c_{k-1}+s_{k-1})+\sum_{j=4}^{k}\left(c_{j-1}+s_{j-1}-\sum_{i=1}^{j-3}(c_{i}+s_{i})\right)\Omega(2^{k-j})$

where $c_{k}=\dfrac{1}{k+1}\dbinom{2k}{k}$ is the $k$th Catalan number and
$s_{k}=\displaystyle\sum_{j=0}^{k}\frac{1}{j+1}\binom{2j}{j}\binom{k+j}{2j}$
is the $k$th Schröder number.

The following two examples can be found in [14].

######  Example 4.3.

Let $p$ and $q$ be distinct primes. For the case $n=pq$ we do not need to
consider any direct products, as they are all automorphic (note all Schur
rings over $\mathcal{Z}_{p}$ and $\mathcal{Z}_{q}$ are automorphic). As the
only proper section over $\mathcal{Z}_{pq}$ are trivial, the only wedge
products are over the sections $[p,p]$ and $[q,q]$, which give, by Lemma 3.3,
$\Omega(p)\Omega(q)$ and $\Omega(q)\Omega(p)$ many Schur rings, respectively.
Thus,

$\Omega(pq)=2\Omega(p)\Omega(q)+|\mathcal{L}(U(pq))|+1.$

Let $p=\prod_{i=1}^{n}r_{i}^{k_{i}}+1$ and
$q=\prod_{i=1}^{n}r_{i}^{\ell_{i}}+1$, where $\\{r_{1},r_{2},\ldots,r_{n}\\}$
is a list of distinct primes. Combining the above formula with Lemma 3.2, we
have

$\Omega(pq)=\prod_{i=1}^{n}\sum_{j=0}^{\min(k_{i},\ell_{i})}\phi(r_{i}^{j})(k_{i}-j+1)(\ell_{i}-j+1)+2\prod_{i=1}^{n}(k_{i}+1)(\ell_{i}+1)+1,$

where $\phi$ denotes Euler’s totient function. We illustrate this formula for
the cases $n=2p,3p,5p$. If $p\neq 2$ is a prime and $x$ is the number of
divisors of $p-1$, then

$\Omega(2p)=3x+1.$

If $p\neq 3$ is a prime such that $p=2^{k}a+1$ where $a$ is odd, then

$\Omega(3p)=\left(\dfrac{7k+6}{k+1}\right)x+1.$

If $p\neq 5$ is a prime such that $p=2^{k}a+1$ where $a$ is odd, then

$\Omega(5p)=\left(\dfrac{13k+7}{k+1}\right)x+1.$

######  Example 4.4.

Let $p$ be an odd prime such that $p=2^{k}a+1$, where a is an odd integer and
$x$ the number of divisors of $p-1$. For the case $n=4p$, the indecomposable
automorphic Schur rings will be in one-to-one correspondence with the
subgroups of $U(4p)\cong\mathcal{Z}_{2}\times\mathcal{Z}_{p-1}$. To see this,
we note that $U(4p)$ contains exactly two layers lattice-isomorphic to $U(p)$
with some diagonal subgroups sitting in between the layers. The top-layer
subgroups of $U(4p)$ correspond to direct products
$\mathcal{Z}_{4}\times\mathfrak{S}$, where $\mathfrak{S}$ is a Schur ring over
$\mathcal{Z}_{p}$, with respect to the usual correspondence of automorphic
Schur rings and automorphic subgroups. On the other hand, the direct products
of the form $\mathcal{Z}_{4}^{0}\times\mathfrak{S}$ are indecomposable and can
be made to correspond the the subgroups of the bottom-layer of $U(4p)$. Those
automorphic Schur rings which correspond to diagonal subgroups of $U(4p)$
necessarily must be wedge-indecomposable. Hence, if we combine together these
three sets of Schur rings, we establish a one-to-one correspondence between
them and the subgroups of $U(4p)$. Therefore,

$\Omega(4p)=\Omega(4p,2)+x\Omega(4p,p)+\Omega(4p,\mathcal{Z}_{2p}^{0})+x\Omega(4p,2p)+\Omega(4p,\mathcal{Z}_{4}^{0})+\Omega(4p,4)\\\
+\Omega(4p,\mathcal{Z}_{4p}^{0})+|\mathcal{L}(U(4p))|=\Omega(2p)+x\Omega(4)+\Omega(2)+x(\Omega(2p,p)+\Omega(2p,2p)+\Omega(4,2)\\\
+\Omega(4,4)-\Omega(2))+\Omega(p)+(\Omega(2p,2)+x\Omega(2p,2p))+\Omega(1)+|\mathcal{L}(U(4p))|\\\
=(3x+1)+3x+1+x(\Omega(2)+\Omega(1)+\Omega(2)+1-1)+x+(\Omega(p)+x\cdot
1)+1+|\mathcal{L}(U(4p))|\\\ =12x+3+|\mathcal{L}(U(4p))|.$

To count the automorphic Schur rings, we compute

$|\mathcal{L}(U(4p))|=|\mathcal{L}(\mathcal{Z}_{2}\times\mathcal{Z}_{2^{k}})||\mathcal{L}(\mathcal{Z}_{a})|=(2(k+1)+k)\left(\dfrac{x}{k+1}\right)=\dfrac{3k+2}{k+1}x.$

Therefore,

$\Omega(4p)=\frac{15k+14}{k+1}x+3.$

Finally, we present a new example to illustrate these enumeration techniques.

######  Example 4.5.

For $n=2p^{2}$,

$\Omega(2p^{2})=\Omega(2p^{2},2)+x\Omega(2p^{2},p)+\Omega(2p^{2},\mathcal{Z}_{2p}^{0})+x\Omega(2p^{2},2p)+\Omega(2p^{2},\mathcal{Z}_{p^{2}}^{0})+x\Omega(2p^{2},p^{2})+\Omega(2p^{2},\mathcal{Z}_{2p^{2}}^{0})\\\
+\Omega(2p^{2},\mathcal{Z}_{2}\times\mathcal{Z}_{p^{2}}^{0})+x\Omega(2p^{2},2p^{2})=\Omega(p^{2})+x\Omega(2p)+\Omega(p)+x(\Omega(p^{2},p)+\Omega(p^{2},p^{2})+\Omega(2p,2)+x\Omega(2p,2p)\\\
-\Omega(2p,2p))+\Omega(2)+x(\Omega(2p,2)+\Omega(2p,2p))+\Omega(1)+x\cdot
1=(x^{2}+x+1)+x(3x+1)+x+x(\Omega(p)+\Omega(1)\\\
+\Omega(p)+x\Omega(1)-\Omega(p))+1+x(\Omega(2)+1)+1+x=6x^{2}+7x+4.$

By a similar computation that is omitted here, we have

$\Omega(2p^{3})=10x^{3}+21x^{2}+31x+6.$

##  5 Conclusion

We can extrapolate from the above examples a general strategy for counting
Schur rings over cyclic groups. We begin by identifying the indecomposable
Schur rings for all divisors of the order $n$. Once this is complete, we
proceed to enumerate all wedge products choosing as the left factor only
indecomposable Schur rings and choosing as sections only those of the form
$[K,H]$, where $K$ is the minimal subgroup of the left wedge-factor. This is
trivial for primitive Schur rings and the Principle of Inclusion-Exclusion is
necessary when distinct minimal subgroups are present. For every left factor
in $\mathfrak{S}\wedge_{[d,e]}\mathfrak{T}$, there are
$\Omega(n/d,\pi(\mathfrak{S}))$ options for $T$. The sum of these mutually
exclusive cases gives $\Omega(n)$.

This general strategy comes with two major obstacles. First, it requires a
strong understanding of the recursive nature of the function
$\Omega(n,\mathfrak{S})$. While ad hoc arguments are used here to handle the
examples considered herein, the potential complexity of
$\Omega(n,\mathfrak{S})$ is seen clearly in [22]. Second, it requires we be
able to effectively enumerate the indecomposable Schur rings. While primitive
Schur rings are easy to identify for cyclic groups and direct products are
indecomposable only if their direct factors are, the indecomposable
automorphic Schur rings are a greater challenge. As we saw throughout, we can
identify the indecomposable automorphic rings using the lattice
$\mathcal{L}(U(n))$, but this lattice becomes increasingly more difficult as
the rank of $U(n)$ increases. Călugăreanu’s technique provides an effective
method of counting subgroups of an abelian group of rank 2, but it becomes far
less effective for rank 3 and beyond. An explicit formula for enumerating
subgroups of an abelian groups of rank 3 is fairly recent (see the
aforementioned references for details), and, at the time of writing, any
explicit formula beyond rank 3 has yet to be discovered. As such, any explicit
formula for enumerating Schur rings over cyclic groups is unlikely without an
explicit formula for counting subgroups of abelian groups.

## References

  * [1] A. R. Ashrafi and F. Koorepazan-Moftakhar.  Towards the classification of finite simple groups with exactly three or four supercharacter theories.  Asian-Eur. J. Math., 11(5):21, 2018.  Id/No 1850096.
  * [2] Ali Reza Ashrafi and Fatemeh Koorepazan-Moftakhar.  Dénombrement des théories de supercaractères d’un groupe fini.  C. R., Math., Acad. Sci. Paris, 357(4):323–326, 2019.
  * [3] Nicholas Bastian, Jaden Brewer, Stephen Humphries, Andrew Misseldine, and Cache Thompson.  On Schur rings over infinite groups.  Algebras and Representation Theory, 2019.
  * [4] Wieb Bosma, John Cannon, and Catherine Playoust.  The Magma algebra system. I. The user language.  J. Symbolic Comput., 24(3-4):235–265, 1997.  Computational algebra and number theory (London, 1993).
  * [5] Shawn Burkett, Jonathan Lamar, Mark L. Lewis, and Casey Wynn.  Groups with exactly two supercharacter theories.  Commun. Algebra, 45(3):977–982, 2017.
  * [6] Grigore Călugăreanu.  The total number of subgroups of a finite Abelian group.  Sci. Math. Jpn., 60(1):157–167, 2004.
  * [7] S. A. Evdokimov and I. N. Ponomarenko.  On a family of Schur rings over a finite cyclic group.  St. Petersbg. Math. J., 13(3):441–451, 2002.
  * [8] S. A. Evdokimov and I. N. Ponomarenko.  Characterization of cyclotomic schemes and normal Schur rings over a cyclic group.  St. Petersbg. Math. J., 14(2):11–55, 2003.
  * [9] S. A. Evdokimov and I. N. Ponomarenko.  Schurity of S-rings over a cyclic group and generalized wreath product of permutation groups.  St. Petersbg. Math. J., 24(3):431–460, 2013.
  * [10] Sergei Evdokimov, István Kovács, and Ilya Ponomarenko.  On schurity of finite abelian groups.  Communications in Algebra, 44(1):101–117, 2016.
  * [11] E. Goursat.  Sur les substitutions orthogonales et les divisions regulières de l’espace.  Ann. Sci. Éc. Norm. Supér. (3), 6:9–102, 1889.
  * [12] Anders O. F. Hendrikson.  Supercharacter theory constructions corresponding to Schur ring products.  Communications in Algebra, 40:4420–4438, 2012.
  * [13] Stephen P. Humphries and David R. Wagner.  Central Schur rings over the projective special linear groups.  Commun. Algebra, 45(12):5325–5337, 2017.
  * [14] Joseph Keller, Andrew Misseldine, and Max Sullivan.  Counting Schur rings over cyclic groups II.  pre-print (submitted).
  * [15] Brent Kerby.  Rational Schur rings over abelian groups.  Master’s thesis, Brigham Young University, 2008.
  * [16] István Kovács.  The number of indecomposable Schur rings over a cyclic 2-group.  Séminaire Lotharingien de Combinatoire, 51:Article B51h”, 2005\.
  * [17] Alexander Lang.  An enumeration of the supercharacter theories of $c_{p}\times c_{2}\times c_{2}$ for prime $p$.  pre-print (submitted).
  * [18] Ka Hin Leung and Siu Lun Ma.  The structure of Schur rings over cyclic groups.  Journal of Pure and Applied Algebra, 66:287–302, 1990.
  * [19] Ka Hin Leung and Shin Hing Man.  On Schur rings over cyclic groups II.  Journal of Algebra, 183:273–285, 1996.
  * [20] Ka Hin Leung and Shin Hing Man.  On Schur rings over cyclic groups.  Israel Journal of Mathematics, 106:251–267, 1998.
  * [21] V. Liskovets and R. Pöschel.  Counting circulant graphs of prime-power order by decomposing into orbit enumeration problems.  Discr. Math., 214:173–191, 2000.
  * [22] Andrew Misseldine.  Counting Schur rings over cyclic groups.  Journal of Algebraic Combinatorics, 51:155–169, Feb 2020.
  * [23] Mikhail Muzychuk and Ilia Ponomarenko.  Schur rings.  European Journal of Combinatorics, 30:1526–1539, 2009.
  * [24] Mikhail E. Muzychuk.  The structure of rational Schur rings over cyclic groups.  European Journal of Combinatorics, 14:479–490, 1993.
  * [25] Mikhail E. Muzychuk.  On the structure of basic sets of Schur rings over cyclic groups.  Journal of Algebra, 169:655–678, 1994.
  * [26] Mikhail E. Muzychuk.  The structure of Schur rings over cyclic groups of square-free order.  Acta Applicandae Mathematicae, 52:163–181, 1998.
  * [27] Ju-Mok Oh.  An explicit formula for the number of subgroups of a finite Abelian $p$-group up to rank 3.  Commun. Korean Math. Soc., 28(4):649–667, 2013.
  * [28] Joseph Petrillo.  Counting subgroups in a direct product of finite cyclic groups.  The College Mathematics Journal, 42(3):215–222, 2011.
  * [29] R. Pöschel.  Investigations of S-rings, especially in the group ring of p-groups.  Math. Message, 60:1–27, 1974.
  * [30] Issai Schur.  Zur theorie der einfach transitiven permutationsgruppen.  Sitzungsber. Preuss. Akad. Wiss. Phy-Math Klasse, Berlin, 118:309–310, 1933.
  * [31] Olaf Tamaschke.  On Schur-rings which define a proper character theory on finite groups.  Math. Z., 117:340–360, 1970.
  * [32] László Tóth.  Subgroups of finite abelian groups having rank two via Goursat’s lemma.  Tatra Mt. Math. Publ., 59:93–103, 2014.
  * [33] Helmut Wielandt.  Zur theorie der einfach transitiven permutationsgruppen II.  Math. Z., 52:384–393, 1949.
  * [34] Helmut Wielandt.  Finite Permutation Groups.  Academic Press, New York-London, 1964.
  * [35] Matan Ziv-Av.  Enumeration of schur rings over small groups.  In Computer algebra in scientific computing. 16th international workshop, CASC 2014, Warsaw, Poland, September 8–12, 2014. Proceedings, pages 491–500. Berlin: Springer, 09 2014.