# Representing and Counting the Subgroups of the GroupZ

Authors: Mario Hampejs; Nicki Holighaus; László Tóth; Christoph Wiesmeyr
Journal: Journal of Numbers
 (2014)

---

## Abstract

We deduce a simple representation and the invariant factor decompositions of the subgroups of the groupZ
m
×
Z
n, where m and n are arbitrary positive integers. We obtain formulas for the total number of subgroups and the number of subgroups of a given order.


---

## Body

## 1. Introduction

LetZ
m be the group of residue classes modulo m and consider the direct product G
=
Z
m
×
Z
n, where m and n are arbitrary positive integers. This paper aims to deduce a simple representation and the invariant factor decompositions of the subgroups of the group G. As consequences we derive formulas for the number of certain types of subgroups of G, including the total number s
(
m
,
n
) of its subgroups and the number s
k
(
m
,
n
) of its subgroups of order k (k
∣
m
n).Subgroups ofZ
×
Z (sublattices of the two-dimensional integer lattice) and associated counting functions were considered by several authors in pure and applied mathematics. It is known, for example, that the number of subgroups of index n in Z
×
Z is σ
(
n
), the sum of the (positive) divisors of n. See, for example, [1, 2], [3, item
A
001615]. Although features of the subgroups of G not only are interesting by their own but also have applications, one of them is described below, it seems that a synthesis on subgroups of G cannot be found in the literature.In the casem
=
n, the subgroups of Z
n
×
Z
n play an important role in numerical harmonic analysis, more specifically in the field of applied time-frequency analysis. Time-frequency analysis attempts to investigate function behavior via a phase space representation given by the short-time Fourier transform [4]. The short-time Fourier coefficients of a function f are given by inner products with translated modulations (or time-frequency shifts) of a prototype function g, assumed to be well localized in phase space, for example, a Gaussian. In applications, the phase space corresponding to discrete, finite functions (or vectors) belonging to C
n is exactly Z
n
×
Z
n. Concerned with the question of reconstruction from samples of short-time Fourier transforms, it has been found that when sampling on lattices, that is, subgroups of Z
n
×
Z
n, the associated analysis and reconstruction operators are particularly rich in structure, which, in turn, can be exploited for efficient implementation (cf. [5–7] and references therein). It is of particular interest to find subgroups in a certain range of cardinality; therefore, a complete characterization of these groups helps choose the best one for the desired application.We recall that a finite Abelian group of order>
1 has rank r if it is isomorphic to Z
n
1
×
⋯
×
Z
n
r, where n
1
,
…
,
n
r
∈
N
∖
{
1
} and n
j
∣
n
j
+
1 (1
≤
j
≤
r
-
1), which is the invariant factor decomposition of the given group. Here the number r is uniquely determined and represents the minimal number of generators of the group. For general accounts on finite Abelian groups see, for example, [8, 9].It is known that for every finite Abelian group, the problem of counting all subgroups and the subgroups of a given order reduces top-groups, which follows from the properties of the subgroup lattice of the group (see [10, 11]). In particular, for G
=
Z
m
×
Z
n, this can be formulated as follows. Assume that gcd
(
m
,
n
)
>
1. Then G is an Abelian group of rank two, since G
≃
Z
u
×
Z
v, where u
=
gcd
(
m
,
n
) and v
=
lcm
(
m
,
n
). Let u
=
p
1
a
1
⋯
p
r
a
r and v
=
p
1
b
1
⋯
p
r
b
r be the prime power factorizations of u and v, respectively, where 0
≤
a
j
≤
b
j (1
≤
j
≤
r). Then
(1)
s
(
m
,
n
)
=
∏
j
=
1
r
‍
s
(
p
j
a
j
,
p
j
b
j
)
,
(2)
s
k
(
m
,
n
)
=
∏
j
=
1
r
‍
s
k
j
(
p
j
a
j
,
p
j
b
j
)
,
where k
=
k
1
⋯
k
r and k
j
=
p
j
c
j with some exponents 0
≤
c
j
≤
a
j
+
b
j (1
≤
j
≤
r).Now consider thep-group Z
p
a
×
Z
p
b, where 0
≤
a
≤
b. This is of rank two for 1
≤
a
≤
b. One has the simple explicit formulae:
(3)
s
(
p
a
,
p
b
)
=
(
b
-
a
+
1
)
p
a
+
2
-
(
b
-
a
-
1
)
p
a
+
1
-
(
a
+
b
+
3
)
p
+
(
a
+
b
+
1
)
(
p
-
1
)
2
,
(4)
s
p
c
(
p
a
,
p
b
)
=
{
p
c
+
1
-
1
p
-
1
,
c
≤
a
≤
b
,
p
a
+
1
-
1
p
-
1
,
a
≤
c
≤
b
,
p
a
+
b
-
c
+
1
-
1
p
-
1
,
a
≤
b
≤
c
≤
a
+
b
.Formula (3) was derived by Călugăreanu [12, Section 4] and recently by Petrillo [13, Proposition 2] using Goursat’s lemma for groups. Tărnăuceanu [14, Proposition 2.9] and [15, Theorem 3.3] deduced (3) and (4) by a method based on properties of certain attached matrices.Therefore,s
(
m
,
n
) and s
k
(
m
,
n
) can be computed using (1), (3) and (2), (4), respectively. We deduce other formulas for s
(
m
,
n
) and s
k
(
m
,
n
) (Theorems 3 and 4), which generalize (3) and (4) and put them in more compact forms. These are consequences of a simple representation of the subgroups of G
=
Z
m
×
Z
n, given in Theorem 1. This representation might be known, but the only source we could find is the paper [5], where only a special case is treated in a different form. More exactly, in [5, Lemma 4.1] a representation for lattices in Z
n
×
Z
n of redundancy 2, that is, subgroups of Z
n
×
Z
n having index n
/
2, is given, using matrices in Hermite normal form. Theorem 2 gives the invariant factor decompositions of the subgroups of G. We also consider the number of cyclic subgroups of Z
m
×
Z
n (Theorem 5) and the number of subgroups of a given exponent in Z
n
×
Z
n (Theorem 8).Our approach is elementary, using only simple group-theoretic and number-theoretic arguments. The proofs are given in Section4.Throughout the paper we use the following notations:N
=
{
1,2
,
…
}, N
0
=
{
0,1
,
2
,
…
}, τ
(
n
) and σ
(
n
) are the number and the sum, respectively, of the positive divisors of n, ψ
(
n
)
=
n
∏
p
∣
n
‍
(
1
+
1
/
p
) is the Dedekind function, ω
(
n
) stands for the number of distinct prime factors of n, μ is the Möbius function, ϕ denotes Euler’s totient function, and ζ is the Riemann zeta function.


## 2. Subgroups ofZ
m
×
Z
n

The subgroups ofZ
m
×
Z
n can be identified and visualized in the plane with sublattices of the lattice Z
m
×
Z
n. Every two-dimensional sublattice is generated by two basis vectors. For example, Figure 1 shows the subgroup of Z
12
×
Z
12 having the basis vectors (
3,0
) and (
1,2
).Figure 1This suggests the following representation of the subgroups.Theorem 1.
For everym
,
n
∈
N, let
(5)
I
m
,
n
≔
{
(
a
,
n
b
)
(
a
,
b
,
t
)
∈
N
2
×
N
0
:
a
∣
m
,
b
∣
n
,
0
≤
t
≤
gcd
(
a
,
n
b
)
-
1
}
and, for (
a
,
b
,
t
)
∈
I
m
,
n, define
(6)
H
a
,
b
,
t
:
=
{
(
i
a
+
j
t
a
gcd

(
a
,
n
/
b
)
,
j
b
)
:
0
≤
i
≤
m
a
-
1,0
≤
j
≤
n
b
-
1
(
i
a
+
j
t
a
gcd

(
a
,
n
/
b
)
,
j
b
)
}
.
ThenH
a
,
b
,
t is a subgroup of order m
n
/
a
b of Z
m
×
Z
n and the map (
a
,
b
,
t
)
↦
H
a
,
b
,
t is a bijection between the set I
m
,
n and the set of subgroups of Z
m
×
Z
n.Note that for the subgroupH
a
,
b
,
t, the basis vectors mentioned above are (
a
,
0
) and (
s
,
b
), where
(7)
s
=
t
a
gcd
(
a
,
n
/
b
)
.This notation fors will be used also in the rest of the paper. Note also that in the case a
≠
m, b
≠
n the area of the parallelogram spanned by the basis vectors is a
b, exactly the index of H
a
,
b
,
t.We say that a subgroupH
=
H
a
,
b
,
t is a subproduct of Z
m
×
Z
n if H
=
H
1
×
H
2, where H
1 and H
2 are subgroups of Z
m and Z
n, respectively.Theorem 2.
(i) The invariant factor decomposition of the subgroupH
a
,
b
,
t is given by
(8)
H
a
,
b
,
t
≃
Z
α
×
Z
β
,
where
(9)
α
=
(
m
a
,
n
b
,
n
s
a
b
)
,
β
=
m
n
a
b
α
satisfying α
∣
β.
(ii) The exponent of the subgroupH
a
,
b
,
t is β.
(iii) The subgroupH
a
,
b
,
t is cyclic if and only if α
=
1.
(iv) The subgroupH
a
,
b
,
t is a subproduct if and only if t
=
0 and H
a
,
b
,
0
=
Z
m
/
a
×
Z
n
/
b. Here H
a
,
b
,
0 is cyclic if and only if gcd
(
m
/
a
,
n
/
b
)
=
1.For example, for the subgroup represented by Figure1 one has m
=
n
=
12, a
=
3, b
=
2, s
=
1, α
=
2, and β
=
12, and this subgroup is isomorphic to Z
2
×
Z
12. It is not cyclic and is not a subproduct.According to Theorem1, the number s
(
m
,
n
) of subgroups of Z
m
×
Z
n can be obtained by counting the elements of the set I
m
,
n. We deduce the following.Theorem 3.
For everym
,
n
∈
N, s
(
m
,
n
) is given by
(10)
s
(
m
,
n
)
=
∑
a
∣
m
,
b
∣
n
‍
gcd
(
a
,
b
)
(11)
=
∑
d
∣
gcd
(
m
,
n
)
‍
ϕ
(
d
)
τ
(
m
d
)
τ
(
n
d
)
(12)
=
∑
d
∣
gcd
⁡
(
m
,
n
)
‍
d
τ
(
m
n
d
2
)
.Formula (10) is a special case of a formula representing the number of all subgroups of a class of groups formed as cyclic extensions of cyclic groups, deduced by Calhoun [16] and having a laborious proof. Note that formula (10) is given, without proof in [3, item
A
054584].Note also that the function(
m
,
n
)
↦
s
(
m
,
n
) is representing a multiplicative arithmetic function of two variables; that is, s
(
m
m
′
,
n
n
′
)
=
s
(
m
,
n
)
s
(
m
′
,
n
′
) holds for any m
,
n
,
m
′
,
n
′
∈
N such that gcd
(
m
n
,
m
′
n
′
)
=
1. This property, which is in concordance with (1), is a direct consequence of formula (10). See Section 5.LetN
(
a
,
b
,
c
) denote the number of solutions (
x
,
y
,
z
,
t
)
∈
N
4 of the system of equations x
y
=
a, z
t
=
b, x
z
=
c.Theorem 4.
For everyk
,
m
,
n
∈
N, such that k
∣
m
n,
(13)
s
k
(
m
,
n
)
=
∑
a
∣
m
,
b
∣
n
m
b
/
a
=
k
gcd
(
a
,
b
)
(14)
=
∑
d
∣
gcd
(
k
,
m
)
e
∣
gcd
(
k
,
n
)
k
∣
d
e
ϕ
(
d
e
k
)
(15)
=
∑
d
∣
gcd
⁡
(
m
,
n
,
k
)
‍
ϕ
(
d
)
N
(
m
d
,
n
d
,
k
d
)
.The identities (3) and (4) can be easily deduced from each of the identities given in Theorems 3 and 4, respectively.Theorem 5.
Letm
,
n
∈
N.
(i) The numberc
(
m
,
n
) of cyclic subgroups of Z
m
×
Z
n is given by
(16)
c
(
m
,
n
)
=
∑
a
∣
m
,
b
∣
n
gcd
(
m
/
a
,
n
/
b
)
=
1
gcd
(
a
,
b
)
(17)
=
∑
a
∣
m
,
b
∣
n
‍
ϕ
(
gcd
(
a
,
b
)
)
(18)
=
∑
d
∣
gcd
⁡
(
m
,
n
)
‍
(
μ
*
ϕ
)
(
d
)
τ
(
m
d
)
τ
(
n
d
)
(19)
=
∑
d
∣
gcd
⁡
(
m
,
n
)
‍
ϕ
(
d
)
τ
(
m
n
d
2
)
.
(ii) The number of subproducts ofZ
m
×
Z
n is τ
(
m
)
τ
(
n
) and the number of its cyclic subproducts is τ
(
m
n
).Formula (17), as a special case of an identity valid for arbitrary finite Abelian groups, was derived by the third author [17, 18] using different arguments. The function (
m
,
n
)
↦
c
(
m
,
n
) is also multiplicative.


## 3. Subgroups ofZ
n
×
Z
n

In the casem
=
n, which is of special interest in applications, the results given in the previous section can be easily used. We point out that n
↦
s
(
n
)
:
=
s
(
n
,
n
) and n
↦
c
(
n
)
:
=
c
(
n
,
n
) are multiplicative arithmetic functions of a single variable (sequences [3, items
A
060724
,
A
060648]). They can be written in the form of Dirichlet convolutions as shown by the next corollaries.Corollary 6.
For everyn
∈
N,
(20)
s
(
n
)
=
∑
d
e
=
n
‍
ϕ
(
d
)
τ
2
(
e
)
=
∑
d
e
=
n
‍
d
τ
(
e
2
)
.Corollary 7.
For everyn
∈
N,
(21)
c
(
n
)
=
∑
d
e
=
n
‍
d
2
ω
(
e
)
(22)
=
∑
d
e
=
n
‍
ϕ
(
d
)
τ
(
e
2
)
.Further convolutional representations can also be given; for example,(23)
s
(
n
)
=
∑
d
e
=
n
‍
τ
(
d
)
ψ
(
e
)
,
c
(
n
)
=
∑
d
|
n
‍
ψ
(
d
)
;
all of these follow from the Dirichlet-series representations
(24)
∑
n
=
1
∞
‍
s
(
n
)
n
z
=
ζ
3
(
z
)
ζ
(
z
-
1
)
ζ
(
2
z
)
,
(25)
∑
n
=
1
∞
‍
c
(
n
)
n
z
=
ζ
2
(
z
)
ζ
(
z
-
1
)
ζ
(
2
z
)
,
valid for z
∈
C, R
(
z
)
>
2.Observe that(26)
s
(
n
)
=
∑
d
∣
n
‍
c
(
d
)
(
n
∈
N
)
,
which is a simple consequence of (23) or of (24) and (25). It also follows from the next result.Theorem 8.
For everyn
,
δ
∈
N with δ
∣
n, the number of subgroups of exponent δ of Z
n
×
Z
n equals the number of cyclic subgroups of Z
δ
×
Z
δ.


## 4. Proofs

Proof of Theorem1.
LetH be a subgroup of G
=
Z
m
×
Z
n. Consider the natural projection π
2
:
G
→
Z
n given by π
2
(
x
,
y
)
=
y. Then π
2
(
H
) is a subgroup of Z
n and there is a unique divisor b of n such that π
2
(
H
)
=
〈
b
〉
:
=
{
j
b
:
0
≤
j
≤
n
/
b
-
1
}. Let s
≥
0 be minimal such that (
s
,
b
)
∈
H.
Furthermore, consider the natural inclusionι
1
:
Z
m
→
G given by ι
1
(
x
)
=
(
x
,
0
). Then ι
1
-
1
(
H
) is a subgroup of Z
m and there exists a unique divisor a of m such that ι
1
-
1
(
H
)
=
〈
a
〉.
We show thatH
=
{
(
i
a
+
j
s
,
j
b
)
:
i
,
j
∈
Z
}. Indeed, for every i
,
j
∈
Z, (
i
a
+
j
s
,
j
b
)
=
i
(
a
,
0
)
+
j
(
s
,
b
)
∈
H. On the other hand, for every (
u
,
v
)
∈
H one has v
∈
π
2
(
H
) and hence there is j
∈
Z such that v
=
j
b. We obtain (
u
-
j
s
,
0
)
=
(
u
,
v
)
-
j
(
s
,
b
)
∈
H, u
-
j
s
∈
ι
1
-
1
(
H
) and there is i
∈
Z with u
-
j
s
=
i
a.
Here a necessary condition is that(
s
n
/
b
,
0
)
∈
H (obtained for i
=
0 and j
=
n
/
b), that is, a
∣
s
n
/
b, equivalent to a
/
gcd
(
a
,
n
/
b
)
∣
s. Clearly, if this is verified, then for the above representation of H it is enough to take the values 0
≤
i
≤
m
/
a
-
1 and 0
≤
j
≤
n
/
b
-
1.
Also, dividings by a we have s
=
a
q
+
r with 0
≤
r
<
a and (
r
,
b
)
=
(
s
,
b
)
-
q
(
a
,
0
)
∈
H, showing that s
<
a, by its minimality. Hence s
=
t
a
/
gcd
(
a
,
n
/
b
) with 0
≤
t
≤
gcd
(
a
,
n
/
b
)
-
1. Thus we obtain the given representation.
Conversely, every(
a
,
b
,
t
)
∈
I
m
,
n generates a subgroup H
a
,
b
,
t of order m
n
/
(
a
b
) of Z
m
×
Z
n and the proof is complete.Proof of Theorem2.
(i)-(ii) We first determine the exponent of the subgroupH
a
,
b
,
t. H
a
,
b
,
t is generated by (
a
,
0
) and (
s
,
b
); hence, its exponent is the least common multiple of the orders of these two elements. The order of (
a
,
0
) is m
/
a. To compute the order of (
s
,
b
) note that m
∣
r
s if and only if m
/
gcd
(
m
,
s
)
∣
r. Thus the order of (
s
,
b
) is lcm
(
m
/
gcd
(
m
,
s
)
,
n
/
b
). We deduce that the exponent of H
a
,
b
,
t is
(27)
lcm
(
m
a
,
m
gcd
⁡
(
m
,
s
)
,
n
b
)
=
lcm
(
m
n
n
a
,
m
n
n
gcd
(
m
,
s
)
,
m
n
m
b
)
=
m
n
gcd
(
n
a
,
n
m
,
n
s
,
m
b
)
=
m
n
gcd
(
m
b
,
n
a
,
n
s
)
=
β
.
For every finite Abelian group the rank of a nontrivial subgroup is at most the rank of the group. Therefore, the rank ofH
a
,
b
,
t is 1 or 2. That is, H
a
,
b
,
t
≃
Z
A
×
Z
B with certain A
,
B
∈
N such that A
∣
B. Here the exponent of H
a
,
b
,
t equals that of Z
A
×
Z
B, which is lcm
(
A
,
B
)
=
B. Using (ii) already proved we deduce that B
=
β. Since the order of H
a
,
b
,
t is A
B
=
m
n
/
(
a
b
) we have A
=
m
n
/
(
a
b
β
)
=
α.
(iii) According to (i)H
a
,
b
,
t
≃
Z
α
×
Z
β, where α
∣
β. Hence H
a
,
b
,
t is cyclic if and only if α
=
1.
(iv) The subgroups ofZ
m are of form {
i
a
:
0
≤
i
≤
m
/
a
-
1
}, where a
∣
m, and the properties follow from (6) and (iii).Proof of Theorem3.
By its definition, the number of elements of the setI
m
,
n is
(28)
∑
a
∣
m
,
b
∣
n
‍
∑
0
≤
t
≤
gcd
(
a
,
n
/
b
)
-
1
‍
1
=
∑
a
∣
m
,
b
∣
n
‍
gcd
(
a
,
n
b
)
=
∑
a
∣
m
,
b
∣
n
‍
gcd
(
a
,
b
)
,
representing s
(
m
,
n
). This is formula (10).
To obtain formula (11) apply the Gauss formula n
=
∑
d
∣
n
‍
ϕ
(
d
) (n
∈
N) by writing the following:
(29)
s
(
m
,
n
)
=
∑
a
∣
m
,
b
∣
n
‍
∑
d
∣
gcd
⁡
(
a
,
b
)
‍
ϕ
(
d
)
=
∑
a
x
=
m
b
y
=
n
∑
d
i
=
a
d
j
=
b
ϕ
(
d
)
=
∑
d
i
x
=
m
d
j
y
=
n
ϕ
(
d
)
=
∑
d
u
=
m
d
v
=
n
ϕ
(
d
)
∑
i
x
=
u
j
y
=
v
1
=
∑
d
u
=
m
d
v
=
n
ϕ
(
d
)
τ
(
u
)
τ
(
v
)
=
∑
d
∣
gcd
⁡
(
m
,
n
)
‍
ϕ
(
d
)
τ
(
m
d
)
τ
(
n
d
)
.
Now (12) follows from (11) by the Busche-Ramanujan identity (cf. [19, Chapter 1]):
(30)
τ
(
m
)
τ
(
n
)
=
∑
d
∣
gcd
⁡
(
m
,
n
)
‍
τ
(
m
n
d
2
)
(
m
,
n
∈
N
)
.Proof of Theorem4.
According to Theorem1,
(31)
s
k
(
m
,
n
)
=
∑
a
∣
m
,
b
∣
n
m
n
/
a
b
=
k
gcd
(
a
,
n
b
)
,
giving (13), which can be written, by Gauss’ formula again, as
(32)
s
k
(
m
,
n
)
=
∑
a
|
m
,
b
|
n
m
b
/
a
=
k
∑
c
∣
a
,
c
∣
b
‍
ϕ
(
c
)
=
∑
c
i
x
=
m
c
j
y
=
n
c
j
x
=
k
ϕ
(
c
)
=
∑
d
i
=
m
e
y
=
n
∑
c
x
=
d
c
j
=
e
c
j
x
=
k
ϕ
(
c
)
,
where in the inner sum one has c
=
d
e
/
k and obtains (14). Now, to get (15) write (32) as
(33)
s
k
(
m
,
n
)
=
∑
c
u
=
m
c
v
=
n
c
w
=
k
ϕ
(
c
)
∑
i
x
=
u
j
y
=
v
j
x
=
w
1
=
∑
c
u
=
m
c
v
=
n
c
w
=
k
ϕ
(
c
)
N
(
u
,
v
,
w
)
=
∑
c
∣
gcd
⁡
(
m
,
n
,
k
)
‍
ϕ
(
c
)
N
(
m
c
,
n
c
,
k
c
)
,
and the proof is complete.Proof of Theorem5.
(i) According to Theorems1 and 2/(iii) and using that ∑
d
∣
n
‍
μ
(
d
)
=
1 or 0 and according to n
=
1 or n
>
1,
(34)
c
(
m
,
n
)
=
∑
a
|
m
,
b
|
n
‍
∑
1
≤
s
≤
a
a
b
|
n
s
gcd
(
m
/
a
,
n
/
b
,
n
s
/
a
b
)
=
1
1
=
∑
a
x
=
m
b
y
=
n
∑
1
≤
s
≤
a
a
r
=
y
s
gcd
(
x
,
y
,
r
)
=
1
1
=
∑
a
x
=
m
b
y
=
n
∑
1
≤
s
≤
a
a
r
=
y
s
∑
e
∣
gcd
(
x
,
y
,
r
)
μ
(
e
)
=
∑
a
e
i
=
m
b
e
j
=
n
μ
(
e
)
∑
1
≤
s
≤
a
a
/
gcd
(
a
,
j
)
∣
s
1
,
where the inner sum is gcd
(
a
,
j
). Hence
(35)
c
(
m
,
n
)
=
∑
a
e
i
=
m
b
e
j
=
n
μ
(
e
)
gcd
(
a
,
j
)
.
Now regrouping the terms according toe
i
=
z and b
e
=
t we obtain
(36)
c
(
m
,
n
)
=
∑
a
z
=
m
j
t
=
n
gcd
(
a
,
j
)
∑
e
i
=
z
b
e
=
t
μ
(
e
)
=
∑
a
z
=
m
j
t
=
n
gcd
(
a
,
j
)
∑
e
∣
gcd
⁡
(
z
,
t
)
‍
μ
(
e
)
=
∑
a
z
=
m
j
t
=
n
gcd
(
z
,
t
)
=
1
gcd
(
a
,
j
)
,
which is (16).
The next results follow applying Gauss’ formula and the Busche-Ramanujan formula, similar to the proof of Theorem3.
(ii) For the subproductsH
a
,
b
,
0 the values a
∣
m and b
∣
n can be chosen arbitrary and it follows at once that the number of subproducts is τ
(
m
)
τ
(
n
). The number of cyclic subproducts is
(37)
∑
a
∣
m
b
∣
n
gcd
(
m
/
a
,
n
/
b
)
=
1
1
=
∑
a
x
=
m
b
y
=
n
gcd
(
x
,
y
)
=
1
1
=
∑
a
x
=
m
b
y
=
n
∑
e
∣
gcd
⁡
(
x
,
y
)
‍
μ
(
e
)
=
∑
e
A
=
m
e
B
=
n
μ
(
e
)
τ
(
A
)
τ
(
B
)
=
∑
e
∣
gcd
⁡
(
m
,
n
)
‍
μ
(
e
)
τ
(
m
e
)
τ
(
n
e
)
=
τ
(
m
n
)
,
by the inverse Busche-Ramanujan identity.Proof of Theorem8.
According to Theorem2/(ii), the number of subgroups of exponent δ of Z
n
×
Z
n is
(38)
E
δ
(
n
)
=
∑
a
∣
n
,
b
∣
n
‍
∑
1
≤
s
≤
a
a
b
∣
n
s
n
/
gcd
(
a
,
b
,
s
)
=
δ
1
=
∑
a
x
=
n
b
y
=
n
∑
1
≤
s
≤
a
a
r
=
y
s
gcd
(
a
,
b
,
s
)
=
n
/
δ
1
.
Writea
=
a
1
n
/
δ, b
=
b
1
n
/
δ, and s
=
s
1
n
/
δ with gcd
(
a
1
,
b
1
,
s
1
)
=
1. We deduce, similar to the proof of Theorem 5/(i), that
(39)
E
δ
(
n
)
=
∑
e
i
x
=
δ
e
j
y
=
δ
μ
(
e
)
gcd
(
i
,
y
)
,
which is exactly c
(
δ
,
δ
)
=
c
(
δ
) (cf. (35)).


## 5. Further Remarks

(1)
As mentioned in Section2 the functions (
m
,
n
)
↦
s
(
m
,
n
) and (
m
,
n
)
↦
c
(
m
,
n
) are multiplicative functions of two variables. This follows easily from formulae (10) and (17), respectively. Namely, according to those formulae s
(
m
,
n
) and c
(
m
,
n
) are two variables Dirichlet convolutions of the functions (
m
,
n
)
↦
gcd
(
m
,
n
) and (
m
,
n
)
↦
ϕ
(
gcd
(
m
,
n
)
), respectively, with the constant 1 function, all multiplicative. Since convolution preserves the multiplicativity we deduce that s
(
m
,
n
) and c
(
m
,
n
) are also multiplicative. See [17, Section 2] for details.
(2)
Asymptotic formulas with sharp error terms for the sums∑
m
,
n
≤
x
‍
s
(
m
,
n
) and ∑
m
,
n
≤
x
‍
c
(
m
,
n
) were given in the paper [20].
(3)
For any finite groupsA and B a subgroup C of A
×
B is cyclic if and only if ι
1
-
1
(
C
) and ι
2
-
1
(
C
) have coprime orders, where ι
1 and ι
2 are the natural inclusions ([21, Theorem 4.2]). In the case A
=
Z
m, B
=
Z
n, and C
=
H
a
,
b
,
t one has #
ι
1
-
1
(
C
)
=
m
/
a and #
ι
2
-
1
(
C
)
=
gcd
(
n
/
b
,
n
s
/
a
b
) and the characterization of the cyclic subgroups H
a
,
b
,
t given in Theorem 2/(iii) can be obtained also in this way. It turns out that regarding the sublattice, H
a
,
b
,
t is cyclic if and only if the numbers of points on the horizontal and vertical axes, respectively, are relatively prime. Note that in the case m
=
n the above condition reads n
gcd
(
a
,
b
,
s
)
=
a
b. Thus it is necessary that n
∣
a
b. The subgroup on Figure 1 is not cyclic.
(4)
Note also the next formula for the number of cyclic subgroups ofZ
n
×
Z
n, derived in [22, Example 2]:
(40)
c
(
n
)
=
∑
lcm
(
d
,
e
)
=
n
‍
gcd
(
d
,
e
)
(
n
∈
N
)
,
where the sum is over all ordered pairs(
d
,
e
) such that lcm
(
d
,
e
)
=
n. For a short direct proof of (40) write d
=
l
a, e
=
l
b with gcd
(
a
,
b
)
=
1. Then gcd
(
d
,
e
)
=
l, lcm
(
d
,
e
)
=
l
a
b, and obtain
(41)
∑
lcm
(
d
,
e
)
=
n
‍
gcd
(
d
,
e
)
=
∑
l
a
b
=
n
gcd
(
a
,
b
)
=
1
l
=
∑
l
k
=
n
‍
l
∑
a
b
=
k
gcd
(
a
,
b
)
=
1
1
=
∑
l
k
=
n
‍
l
2
ω
(
k
)
=
c
(
n
)
,
according to (21).
(5)
Every subgroupK of Z
×
Z has the representation K
=
{
(
i
a
+
j
s
,
j
b
)
:
i
,
j
∈
Z
}, where 0
≤
s
≤
a and 0
≤
b are unique integers. This follows like in the proof of Theorem 1. Furthermore, in the case a
,
b
≥
1, 0
≤
s
≤
a
-
1 the index of K is a
b and one obtains at once that the number of subgroups K having index n (n
∈
N) is ∑
a
b
=
n
‍
∑
0
≤
s
≤
a
-
1
‍
1
=
∑
a
b
=
n
‍
a
=
σ
(
n
), mentioned in Section 1.



---

*Source: 491428-2014-10-16.xml*