DIFFERENCE BASES IN FINITE ABELIAN GROUPS

arXiv:1704.02471v2 [math.CO] 13 Apr 2017

TARAS BANAKH AND VOLODYMYR GAVRYLKIV
Abstract. A subset B of a group G is called a difference basis of G if each element g ∈ G can be written as
the difference g = ab−1 of some elements a, b ∈ B. The smallest cardinality |B| of a difference basis B ⊂ G
∆[G]
is called the difference size of G and is denoted by ∆[G]. The fraction ð[G] := √
is called the difference
|G|

characteristic of G. Using properies of the Galois rings, we prove recursive upper bounds for the difference
sizes and characteristics of finite Abelian groups. In particular, √
we prove that for a prime number
p ≥ 11,
√ √p−1
p−1
any finite Abelian p-group G has difference characteristic ð[G] < √p−3 · supk∈N ð[Cpk ] < 2 · √p−3 . Also we
calculate the difference sizes of all Abelian groups of cardinality < 96.

1. Introduction
A subset B of a group G is called a difference basis for a subset A ⊂ G if each element a ∈ A can be written
as a = xy −1 for some x, y ∈ B. The smallest cardinality of a difference basis for A is called the difference size of
A and is denoted by ∆[A]. For example, the set {0, 1, 4, 6} is a difference basis for the interval A = [−6, 6] ∩ Z
witnessing that ∆[A] ≤ 4. The difference size is subadditive in the sense that ∆[A ∪ B] < ∆[A] + ∆[B] for any
non-empty finite subsets A, B of a group G (see Proposition 4.1).
p
The definition of a difference basis B for a set A in a group G implies that |A| ≤ |B|2 and hence ∆[A] ≥ |A|.
The fraction
∆[A]
≥1
ð[A] := p
|A|

is called the difference characteristic of A. The difference characteristic is submultiplicative in the sense that
ð[G] ≤ ð[H] · ð[G/H] for any normal subgroup H of a finite group G, see [1, 1.1].
In this paper we are interested in evaluating the difference characteristics of finite Abelian groups. In fact,
this problem has been studied in the literature. A fundamental result in this area is due to Kozma and Lev [8],
who proved (using the classification of finite simple groups) that each finite group G has difference characteristic
ð[G] ≤ √43 ≈ 2.3094. For finite cyclic groups G the upper bound √43 can be lowered to ð[G] ≤ 23 (and even to
ð[G] < √23 if |G| ≥ 2 · 1015 ), see [2]. In this paper we continue investigations started in [2] and shall give some
lower and upper bounds for the difference characteristics of finite Abelian groups. In some cases (for example,
for Abelian p-groups with p ≥ 11) our upper bounds are better than the general upper bound √43 of Kozma
and Lev.
In particular, in Theorem 6.3 we prove that for any prime number p ≥ 11, any finite Abelian p-group G has
difference characteristic
√
√
p−1
p−1 √
ð[G] ≤ √
· sup ð[Cpk ] < √
· 2.
p − 3 k∈N
p−3
These results are obtained exploiting a structure of a Galois ring on the groups Cprk . Here Cn = {z ∈ C :
z = 1} is the cyclic group of order n. The group Cn is isomorphic to the additive group of the ring Zn = Z/nZ.
n

2. Known results
In this section we recall some known results on difference bases in finite groups. The following fundamental
fact was proved by Kozma and Lev [8].
Theorem 2.1 (Kozma, Lev). Each finite group G has difference characteristic ð[G] ≤
1991 Mathematics Subject Classification. 05B10, 05E15, 16L99, 16Z99, 20D60, 20K01.
Key words and phrases. finite group, Abelian group, difference basis, difference characteristic.
1

√4 .
3

2

TARAS BANAKH AND VOLODYMYR GAVRYLKIV

For a real number x we put
⌈x⌉ = min{n ∈ Z : n ≥ x} and ⌊x⌋ = max{n ∈ Z : n ≤ x}.

The following proposition is proved in [1, 1.1].

Proposition 2.2. Let G be a finite group. Then
√


1+ 4|G|−3
≤ ∆[G] ≤ |G|+1
,
(1)
2
2
(2) ∆[G] ≤ ∆[H] · ∆[G/H] and ð[G] ≤ ð[H] · ð[G/H] for any normal subgroup H ⊂ G;
(3) ∆[G] ≤ |H| + |G/H| − 1 for any subgroup H ⊂ G;


Finite groups G with ∆[G] = |G|+1
were characterized in [1] as follows.
2

Theorem 2.3 (Banakh, Gavrylkiv, Nykyforchyn). For a finite group G

 |G|
(i) ∆[G] = |G|+1
> 2 if and only if G is isomorphic to one of the groups:
2
C1 , C2 , C3 , C4 , C2 × C2 , C5 , D6 , (C2 )3 ;
(ii) ∆[G] = |G|
2 if and only if G is isomorphic to one of the groups: C6 , C8 , C4 × C2 , D8 , Q8 .
In this theorem by D2n we denote the dihedral group of cardinality 2n and by Q8 the 8-element group of
quaternion units. In [1] the difference size ∆[G] was calculated for all groups G of cardinality |G| ≤ 13.
Table 1. Difference sizes of groups of order ≤ 13
G:
∆[G]
G:
∆[G]

C2
2
C7
3

C3
2
C11
4

C5
3
C13
4

C4
3
C9
4

C2 ×C2
3
C3 ×C3
4

C6
3
C10
4

D6
4
D10
4

C8
4
C12
4

C2 ×C4
4
C2 ×C6
5

D8
4
D12
5

Q8
4
A4
5

(C2 )3
5
C3 ⋊C4
5

An important role in evaluating the difference sizes of cyclic groups is due to difference sizes of the orderintervals [1, n]∩Z in the additive group Z of integer numbers. For a natural number n ∈ N by ∆[n] we denote the
√
difference size of the order interval [1, n] ∩ Z and by ð[n] := ∆[n]
its difference characteristic. The asymptotics
n
∞
of the sequence (ð[n])n=1 was studied by Rédei and Rényi [10], Leech [7] and Golay [6] who eventually proved
that
r
q
q
128
sin(ϕ)
4
2 + 3π
< ð[6] = 83 .
< 2 + max 2 ϕ+π
≤ lim ð[n] = inf ð[n] ≤ ð[6166] = √
n→∞
0<ϕ<2π
n∈N
6166
In [2] the difference sizes of the order-intervals [1, n] ∩ Z were applied to give upper bounds for the difference
sizes of finite cyclic groups.


Proposition 2.4. For every n ∈ N we get the upper bound ∆[Cn ] ≤ ∆ ⌈ n−1
2 ⌉ , which implies that
64
2
1
<√ .
lim sup ð[Cn ] ≤ √ inf ð[n] ≤ √
n∈N
2
3083
3
n→∞

The following facts on the difference sizes of cyclic groups were proved in [2].
Theorem 2.5 (Banakh, Gavrylkiv). For any n ∈ N the cyclic group Cn has the difference characteristic:
(1) ð[Cn ] ≤ ð[C4 ] = 32 ;
√
(2) ð[Cn ] ≤ ð[C2 ] =√ð[C8 ] = 2 if n 6= 4;
(3) ð[Cn ] ≤ √1273 < 2 if n ≥ 9;
(4) ð[Cn ] ≤ √24
< √1273 if n ≥ 9 and n 6= 292;
293
2
(5) ð[Cn ] < √3 if n ≥ 2 · 1015 .
For some special numbers n we have more precise upper bounds for ∆[Cn ]. We recall that a number q is a
prime power if q = pk for some prime number p and some k ∈ N.
The following theorem was derived in [2] from the classical results of Singer [13], Bose, Chowla [4], [5] and
Rusza [12].
Theorem 2.6. Let p be a prime number and q be a prime power. Then
(1) ∆[Cq2 +q+1 ] = q + 1;

DIFFERENCE BASES IN FINITE ABELIAN GROUPS

3

√
(2) ∆[Cq2 −1 ] ≤ q − 1 + ∆[Cq−1 ] ≤ q − 1 + 23 q − 1;
√
√
(3) ∆[Cp2 −p ] ≤ p − 3 + ∆[Cp ] + ∆[Cp−1 ] ≤ p − 3 + 23 ( p + p − 1).

The following table of difference sizes of cyclic groups Cn for ≤ 100 is taken from [2].
Table 2. Difference sizes and characteristics of cyclic groups Cn for n ≤ 100
n ∆[Cn ]
1
1
2
2
3
2
4
3
5
3
6
3
7
3
8
4
9
4
10
4
11
4
12
4
13
4
14
5
15
5
16
5
17
5
18
5
19
5
20
6
21
5
22
6
23
6
24
6
25
6

ð[Cn ]
1
1.4142...
1.1547...
1.5
1.3416...
1.2247...
1.1338...
1.4142...
1.3333...
1.2649...
1.2060...
1.1547...
1.1094...
1.3363...
1.2909...
1.25
1.2126...
1.1785...
1.1470...
1.3416...
1.0910...
1.2792...
1.2510...
1.2247...
1.2

n ∆[Cn ]
26
6
27
6
28
6
29
7
30
7
31
6
32
7
33
7
34
7
35
7
36
7
37
7
38
8
39
7
40
8
41
8
42
8
43
8
44
8
45
8
46
8
47
8
48
8
49
8
50
8

ð[Cn ]
1.1766...
1.1547...
1.1338...
1.2998...
1.2780...
1.0776...
1.2374...
1.2185...
1.2004...
1.1832...
1.1666...
1.1507...
1.2977...
1.1208...
1.2649...
1.2493...
1.2344...
1.2199...
1.2060...
1.1925...
1.1795...
1.1669...
1.1547...
1.1428...
1.1313...

n ∆[Cn ]
51
8
52
9
53
9
54
9
55
9
56
9
57
8
58
9
59
9
60
9
61
9
62
9
63
9
64
9
65
9
66
10
67
10
68
10
69
10
70
10
71
10
72
10
73
9
74
10
75
10

ð[Cn ]
n ∆[Cn ]
ð[Cn ]
1.1202... 76
10
1.1470...
1.2480... 77
10
1.1396...
1.2362... 78
10
1.1322...
1.2247... 79
10
1.1250...
1.2135... 80
11
1.2298...
1.2026... 81
11
1.2222...
1.0596... 82
11
1.2147...
1.1817... 83
11
1.2074...
1.1717... 84
11
1.2001...
1.1618... 85
11
1.1931...
1.1523... 86
11
1.1861...
1.1430... 87
11
1.1793...
1.1338... 88
11
1.1726...
1.125
89
11
1.1659...
1.1163... 90
11
1.1595...
1.2309... 91
10
1.0482...
1.2216... 92
11
1.1468...
1.2126... 93
12
1.2443...
1.2038... 94
12
1.2377...
1.1952... 95
12
1.2311...
1.1867... 96
12
1.2247...
1.1785... 97
12
1.2184...
1.0533... 98
12
1.2121...
1.1624... 99
12
1.2060...
1.1547... 100
12
1.2

3. A lower bound for the difference size
In this section we prove a simple lower bound for the difference size of an arbitrary finite set in a group.
This lower bound improves the lower bound given in Proposition 2.2(1). For a group G by 1G we denote the
unique idempotent of G.
Theorem 3.1. Each finite subset A of a group G has difference size
p
p
1 + 4|A>2 | + 8|A2 | + 1
1 + 4|A>1 | + 1
∆[A] ≥
≥
,
2
2
where A>2 = {a ∈ A : a−1 6= a}, A2 = {a ∈ A : a−1 = a 6= 1G } and A>1 = {a ∈ A : a 6= 1G }.

Proof. Take a difference basis B ⊂ G for the set A of cardinality |B| = ∆[A] and consider the map ξ :
B × B → G, ξ : (x, y) 7→ xy −1 . Observe that for the unit 1G of the group G the preimage ξ −1 (1G ) coincides
with the diagonal {(x, y) ∈ B × B : x = y} of the square B × B and hence has cardinality |ξ −1 (e)| = |B|.
Observe also that for any element g ∈ A2 = {a ∈ A : a−1 = a 6= 1G } and any (x, y) ∈ ξ −1 (g), we get
yx−1 = (xy −1 )−1 = g −1 = g, which implies that |ξ −1 (g)| ≥ 2. Then
X
X
|B|2 = |B × B| ≥ |ξ −1 (1G )| +
|ξ −1 (g)| +
|ξ −1 (g)| ≥ |B| + 2|A2 | + |A>2 |
a∈A2

and hence

as A>2 ∪ A2 = A>1 .

∆[G] = |B| ≥

1+

a∈A>2

p
p
1 + 4|A>2 | + 8|A2 |
1 + 1 + 4|A>1 |
≥
2
2



4

TARAS BANAKH AND VOLODYMYR GAVRYLKIV

Corollary 3.2. Each finite group G has difference size ∆[G] ≥
g 6= 1G } is the set of elements of order 2 in G.

1+

√

4|G|+4|G2 |−3
,
2

where G2 = {g ∈ G : g −1 =

4. The subadditivity and submultiplicativity of the difference size
In this section we prove two properties of the difference size called the subadditivity and the submultiplicativity.
Proposition 4.1. For any non-empty finite subsets A, B of a group G we get ∆[A ∪ B] ≤ ∆[A] + ∆[B] − 1.
Proof. Given non-empty sets A, B ⊂ G, find difference bases DA and DB for the sets A, B of cardinality
|DA | = ∆[A] and |DB | = ∆[B]. Taking any point d ∈ DA and replacing DA by its shift DA d−1 , we can assume
that the unit 1G of the group G belongs to DA . By the same reason, we can assume that 1G ∈ DB . The union
D = DA ∪ DB is a difference basis for A ∪ B, witnessing that
∆[A ∪ B] ≤ |D| ≤ |DA | + |DB | − 1 = ∆[A] + ∆[B] − 1.

Proposition 4.2. Let h : G → H be a surjective homomorphism of groups with finite kernel K. For any
non-empty finite subset A ⊂ H we get ∆[h−1 (A)] ≤ ∆[A] · ∆[K].
Proof. Given a non-empty finite subset A ⊂ H, find a difference basis DA for the set A of cardinality |DA | =
∆[A]. Also fix a difference basis DK for the kernel K ⊂ G of cardinality |DK | = ∆[K].
Fix any subset B ⊂ G such that |B| = |DA | and |h−1 (x) ∩ B| = 1 for any x ∈ DA . We claim that the set
C = BDK is a difference basis for h−1 (A).
Since DA is a difference basis for the set A, for any a ∈ h−1 (A) there are elements a1 , a2 ∈ DA such that
−1
h(a) = a1 a−1
2 . Then a = b1 b2 k for some b1 , b2 ∈ B, k ∈ K. The normality of the subgroup K in G implies
−1
′ −1
that a = b1 b2 k = b1 k b2 for some k ′ ∈ K. Taking into account that DK is a difference basis for the kernel
K, find elements k1 , k2 ∈ DK such that k ′ = k1 k2−1 . Then
−1 −1
−1
a = b1 b2−1 k = b1 k ′ b−1
∈ CC −1
2 = b1 k1 k2 b2 = (b1 k1 )(b2 k2 )

and
∆[h−1 (A)] ≤ |C| ≤ |DA | · |DK | = ∆[A] · ∆[K].



5. Difference bases in rings
In this section we construct difference bases for subsets of finite rings. All rings considered in this section
have the unit. For a ring R by U (R) we denote the multiplicative group of invertible elements in R. An element
x of a ring R is called invertible if there exists an element x−1 ∈ R such that xx−1 = x−1 x = 1. The group
U (R) is called the group of units of the ring R.
The characteristic of a finite ring R is the smallest natural number n such that nx = 0 for every x ∈ R. A
non-empty subset I of a ring R is called an ideal in R if I 6= R, I − I ⊂ I and IR ∪ RI ⊂ I. The spectrum
Spec(R) of a ring is the set of all maximal ideals of R. For any maximal ideal I of a commutative ring R the
quotient ring R/I is a field.
A ring R is called local if it contains a unique maximal ideal, which is denoted by Im . The quotient ring
R/Im is a field called the residue field of the local ring R.
By [3, Ch.6], for every prime number p and natural numbers k, r there exists a unique local ring GR(pk , r)
called the Galois ring of characteristic pk whose additive group is isomorphic to the group (Cpk )r , the maximal
ideal Im coincides with the principal ideal pR generated by p · 1 and whose residue field GR(pk , r) contains pr
elements. The Galois ring GR(pk , r) can be constructed as the quotient ring Z[x]/(pk , f (x)) of the ring Z[x]
of polynomials with integer coefficients by the ideal (pk , f (x)) generated by the constant pk and a carefully
selected monic polynomial f ∈ Z[x] of degree r, which is irreducible over the field Z/pZ, see [3, 6.1]. For k = 1
the Galois ring GR(pk , r) is a field, and for r = 1 the Galois ring GR(pk , r) is isomorphic to the ring Z/pk Z.
The following description of the multiplicative group of a Galois ring is taken from Theorem 6.1.7 of the
book [3].

DIFFERENCE BASES IN FINITE ABELIAN GROUPS

5

Theorem 5.1. Let p be a prime number and k, r be natural numbers. The multiplicative group U (R) of a
Galois ring R := GR(pk , r) is isomorphic to:
(
Cpr −1 × Cprk−1
if either p is odd or p = 2 and k ≤ 2,
r−1
C2r −1 × C2 × C2k−2 × C2k−1 if p = 2 and k ≥ 3.
The following theorem is our principal tool for evaluating the difference sizes of finite Abelian groups of odd
order.
Theorem 5.2. Let R be a finite commutative ring R with unit and (1 + 1) ∈ U (R) and let h : G → R × R be
a surjective homomorphism from a group G onto the Abelian group of the ring R × R. Let K = h−1 (0, 0) be
the kernel of the homomorphism h. Then
X
∆[h−1 (I × R)].
∆[G] ≤ ∆[K] · |R| − |Spec(R)| +
I∈Spec(R)

If the ring R is local, then ∆[G] ≤ ∆[K] · |R| − 1 + ∆[h−1 (Im × R)].
S
Proof. First we observe that R = U (R) ∪ I∈Spec(R) I. Indeed, if an element x ∈ R is not invertible, then
the set xR =S{xy : y ∈ R} is an ideal in R, contained in some
S maximal ideal I ∈ Spec(R). This implies that
R = U (R) ∪ I∈Spec(R) I and hence G = h−1 (U (R) × R) ∪ I∈Spec(R) h−1 (I × R).

Lemma 5.3. The set B = {(x, x2 ) : x ∈ R} is a difference basis for the set U (R) × R in the additive group
R × R.
Proof. Given any pair (a, b) ∈ U (R)×R, we should find two elements x, y ∈ R such that (a, b) = (x−y, x2 −y 2 ).
Solving this system of equations in the ring R, we get the solution
(
x = 2−1 (ba−1 + a)
y = 2−1 (ba−1 − a).

By Lemma 5.3, the set B = {(x, x2 ) : x ∈ R} is a difference basis for the set U (R) × R in R × R. So,
∆[U (R) × R] ≤ |B| = |R|. By Proposition 4.2,
h−1 (U (R) × R) ≤ ∆[K] · ∆[U (R) × R] ≤ ∆[K] · |R|
and by Proposition 4.1,
∆[G] ≤ ∆[h−1 (U (R) × R)] +

X

I∈Spec(R)

(∆[h−1 (I × R)] − 1) ≤ ∆[K] · |R| − |Spec(R)| +

X

I∈Spec(R)

∆[h−1 (I × R)].


Our next theorem will be applied for evaluating the difference characteristics of Abelian 2-groups. This
theorem exploits the structure of a (non)associative ring. By a (non)associative ring we understand an Abelian
group R endowed with a binary operation ◦ : R × R → R which is distributive in the sense that x ◦ (y + z) =
x ◦ y + x ◦ z and (x + y) ◦ z = x ◦ z + y ◦ z for all x, y, z ∈ R. A (non)associative ring R is called a ring if its
binary operation ◦ is associative. In the opposite case R is called a non-associative ring.
For any (non)associative ring R the product R × R, endowed with the binary operation
(x, y) ⋆ (x′ , y ′ ) = (x + x′ , y + y ′ + x ◦ x′ ),

is a group. The inverse element to (x, y) in this group is (−x, −y + x ◦ x). The product R × R endowed with
this group operation will be denoted by R ⋆ R. The group R ⋆ R is commutative if and only if the binary
operation ◦ on R is commutative. For a (non)associative ring R let U (R) be the set of all elements a ∈ R such
that the map R → R, x 7→ x ◦ a, is bijective. The following theorem was known for semifields, see [9, 4.1].
Theorem 5.4. For any finite (non)associative ring R the set B = {(x, x ◦ x) : x ∈ R} is a difference basis for
the set U (R) × R in the group R ⋆ R.

6

TARAS BANAKH AND VOLODYMYR GAVRYLKIV

Proof. Given any pair (a, b) ∈ U (R) × R, we need to find elements x, y ∈ R such that (a, b) = (x, x ◦ x) ⋆
(y, y ◦ y)−1 . The definition of the group operation ⋆ implies that (y, y ◦ y)−1 = (−y, 0). Then the equality
(a, b) = (x, x ◦ x) ⋆ (y, y ◦ y)−1 turns into (a, b) = (x, x ◦ x) ⋆ (−y, 0) = (x − y, x ◦ x − x ◦ y) = (x − y, x ◦ (x − y)).
Since a ∈ U (R), there exists an element x ∈ R such that x ◦ a = b. Let y = x − a and observe that the pair
(x, y) has the required property:
(x, x ◦ x) ⋆ (y, y ◦ y)−1 = (x − y, x ◦ (x − y)) = (a, x ◦ a) = (a, b).

Theorem 5.4 suggests the problem of detecting the structure of the group R ⋆ R for various rings R. For
Galois rings GR(pk , r) this problem is answered in the following two theorems.
Theorem 5.5. Let p be a prime number, and k, r be natural numbers. For the Galois ring R := GR(pk , r) the
group R ⋆ R is isomorphic to
(
Cprk × Cprk
if p ≥ 3,
r
r
C2k+1 × C2k−1 if p = 2.
Proof. First observe that the commutativity of the Galois ring R implies the commutativity of the group R ⋆ R.
To determine the structure of the group R ⋆ R we shall calculate the orders of its elements. Let us recall that
the order of an element x in an Abelian group G is the smallest number n ∈ N such that nx = 0.
Let us fix an element (x, y) ∈ R × R and evaluate its order in the group R ⋆ R. By induction it can be shown
that for every s ∈ N we get (x, y)s = (sx, sy + s(s−1)
x2 ).
2

k
k
If p ≥ 3, then (x, y)p = pk x, pk y + pk p 2−1 x2 = (0, 0) as pk · z = 0 for each element z ∈ R. On the other
k−1
hand, (x, y)p
= (0, 0) if and only if pk−1 x = pk−1 y = 0 if and only if (x, y) ∈ pR × pR, which implies that the
set of elements of order pk−1 has cardinality p2(k−1)r . It remains to observe that up to an isomorphism, Cp2rk is
the unique Abelian p-group of cardinality p2kr that contains p2kr elements of order ≤ pk and p2kr − p2(k−1)r
elements of order pk .
k+1

Next, assume that p = 2. In this case (x, y)2
= (2k+1 x, 2k+1 y + 2k (2k+1 − 1)x2 ) = (0, 0), which means
k
k+1
that each element of the group R ⋆ R has order ≤ 2 . Observe that (x, y)2 = (2k x, 2k y + 2k−1 (2k − 1)x2 ) =
k
(0, 2k−1 (2k − 1)x2 ), which implies that (x, y)2 6= (0, 0) if and only if x2 ∈
/ Im = 2R if and only if x ∈ U (R).
This means that the 2-group R ⋆ R has exactly |U (R) × R| = (2kr − 2(k−1)r )2kr = 2(2k−1)r (2r − 1) elements of
order 2k+1 .
Next, for any i ∈ {0, . . . , k}, we calculate the number of elements of order > 2k−i in R ⋆ R. Observe that
an element (x, y) ∈ R ⋆ R has order > 2k−i if and only if (2k−i x, 2k−i y + 2k−i−1 (2k−i − 1)x2 ) 6= (0, 0) if
and only if either
/ 2i R or x ∈ 2i R and y ∈
/ 2i R. So, the set of elements of order > 2k−i coincides with
 x i∈
i
i
(R \ 2 R) × R ∪ 2 R × (R \ 2 R) and hence has cardinality

|R \ 2i R| · |R| + |2i R| · |R \ 2i R| = (|R| − |2i R|) · (|R| + |2i R|) = |R|2 − |2i R|2 = 22kr − 22(k−i)r = 22(k−i)r (22ir − 1).

This information is sufficient to detect the isomorphic type of the group R ⋆ R. By [11, 4.2.6], the Abelian
Qk+1
2-group R ⋆ R is isomorphic to the product H = i=1 C2mi i for some numbers m1 , . . . , mk+1 ∈ {0} ∪ N. Observe
Q
Q
that the group H contains (2(k+1)mk+1 − 2kmk+1 ) · ki=1 2imi = 2kmk+1 (2mk+1 − 1) · ki=1 2imi elements of order
2k+1 . Taking into account that the group R ⋆ R contains 2(2k−1)r (2r − 1) elements of order 2k+1 , we conclude
that mk+1 = r.
Next, observe that the group H contains exactly
m

m

k+1
k+1
k
|C2k+1
× C2mkk − C2k−1
× C2mk−1
|·

k−1
Y
i=1

|C2mi i | =

= (2(k+1)r+kmk − 2(k−1)(r+mk ) ) ·
k

k−1
Y
i=1

2imi = 2(k−1)(r+mk ) (22r+mk − 1) ·

elements of order ≥ 2 . Taking into account that the group R ⋆ R contains exactly 2
of order ≥ 2k , we conclude that mk = 0.

2(k−1)n

(2

2r

k−1
Y

2imi

i=1

− 1) elements

DIFFERENCE BASES IN FINITE ABELIAN GROUPS

7

The group H contains exactly
m

m

m

m

k+1
k−1
k+1
k−1
k
|C2k+1
× C2mkk × C2k−1
− C2k−2
× C2mk−2
× C2k−2
|·

k−2
Y
i=1

= (2(k+1)r+(k−1)mk−1 − 2(k−2)(r+mk−1 ) ) ·
k−1

|C2mi i | =

k−2
Y
i=1

2imi = 2(k−2)(r+mk−1 ) (23r+mk−1 − 1) ·
(k−2)r

4r

k−2
Y

2imi

i=1

elements of order ≥ 2
. Taking into account that the group R ⋆ R contains exactly 2
(2 − 1) elements
of order ≥ 2k−1 , we conclude that mk−1 = r.
mk+1
mk−1
Taking into account that |C2k+1
× C2k−1
| = |C2rk+1 × C2rk−1 | = 22kr = |R ⋆ R|, we conclude that mi = 0 for
i < k − 1 and hence the group R ⋆ R is isomorphic to C2rk+1 × C2rk−1 .

6. Evaluating the difference characteristics of Abelian p-groups
In this section we shall evaluate the difference characteristics of finite Abelian p-groups for an odd prime
number p. We recall that a group G is called a p-group if each element x ∈ G generates a finite cyclic group
of order pk for some k ∈ N. A finite group G is a p-group if and only if |G| = pk Q
for some k ∈ N.
r
It is well-known that each Abelian p-group G is isomorphic to the product i=1 Cpki of cyclic p-groups.
The number r of cyclic groups in this decomposition is denoted by r(G) and called the rank of G.
Applying Theorem 5.2 to the Galois ring R := GR(pk , r) and taking into account that its additive group is
isomorphic to Cprk and pR coincides with the maximal ideal of R, we get the following corollary.
Corollary 6.1. Let p be an odd prime number, k, r be natural numbers. Let h : G → Cp2rk be a surjective
homomorphism and K be its kernel. Then
∆[G] ≤ ∆[K] · pkr + ∆[h−1 (Cprk−1 × Cprk )] − 1
and

1
1
.
ð[G] ≤ ð[K] + √ r · ð[h−1 (Cprk−1 × Cprk )] − p
p
|G|

This corollary implies the following recursive upper bound for difference characteristics of finite Abelian
p-groups.
Theorem 6.2. Let p be an odd prime number, k1 , . . . , km be natural numbers, and k, r be natural numbers
such that 2r ≤ m and k ≤ min ki . Then
1≤i≤2r

m
hY

∆

i=1

and

Cpki

i

m
r
m
2r
i
i
hY
hY
Y
Y
kr
Cpki − 1
Cpki −1 ×
Cpki · p + ∆
Cpki −k ×
≤∆
i=1

i=2r+1

i=1

i=r+1

m
2r
m
m
m
r
Y
Y


Y
Y
 Y
Y
1
1
p .
Cpki + √ r · ð
Cpki −k ×
Cpki ≤ ð
ð
Cpki −
Cpki −1 ×
p
pki
i=2r+1
i=1
i=1
i=1
i=r+1
i=1

The recursive formulas from the preceding theorem will be used in the following upper bound for the
difference characteristic of finite Abelian p-group.
Theorem 6.3. For any prime number p ≥ 11, any finite Abelian p-group G has difference characteristic
√
√
p−1
p−1
24
ð[G] ≤ √
· sup ð[Cpk ] ≤ √
·√
.
p − 3 k∈N
p−3
293

Proof. For a prime number p and a natural number r let Abrp be the class of Abelian p-groups of rank r. Let
S
S
S
n
≤r
n
r
also Ab<r
p =
n<r Abp and Abp =
n≤r Abp . Let Abp :=
r∈N Abp be the family of finite Abelian p-groups.
For a class C of finite groups we put ð[C] := supG∈C ð[G]. By Theorem 2.1, ð[C] ≤ √43 .
Lemma 6.4. For any odd prime number p and any natural number r we get the upper bound
1
1
≤r
<r
ð[Abrp ] ≤ ð[Ab<r
p ] + p ⌊r/2⌋ · ð[Abp ] ≤ ð[Abp ] + p ⌊r/2⌋ · ð[Abp ].
p
p

8

TARAS BANAKH AND VOLODYMYR GAVRYLKIV

Consequently,
⌊r/2⌋
X 2
1
p
p
≤ ð[Ab1p ] + ð[Abp ] ·
pi
p⌊i/2⌋
i=2
i=1
Q
r
Proof. Any group G ∈ Abr is isomorphic to the product i=1 Cpki for a unique non-decreasing sequence (ki )ri=1
Qr
Q2m
of natural numbers. Let k = k1 and m = ⌊ r2 ⌋. Since k1 − k = 0, the group i=1 Cpki −k × i=2m+1 Cpki has
rank < r. Applying Theorem 6.2, we conclude that

ð[Abrp ] ≤ ð[Ab1p ] + ð[Abp ] ·

2m
r

Y
Y
Cpki −k ×
Cpki < ð
ð[G] = ð
i=1

i=1

r
X

r
Y

r
m
Y


Y
1
Cpki + √ m · ð
Cpki ≤
Cpki −1 ×
p
i=2m+1
i=m+1
i=1

1
1
≤r
<r
≤ ð[Ab<r
p ] + √ m · ð[Abp ] ≤ ð[Abp ] + √ m · ð[Abp ].
p
p


Lemma 6.4 implies that
ð[Abp ] ≤ ð[Ab1p ] + ð[Abp ] ·

∞
X
2
2
p = ð[Ab1p ] + ð[Abp ] · √
i
p
−1
p
i=1

and after transformations
√
√
√

p−1
p−1
p−1
2 −1
24
ð[Abp ] ≤ ð[Ab1p ] · 1 − √
.
= ð[Ab1p ] · √
=√
· sup ð[Cpk ] ≤ √
·√
p−1
p−3
p − 3 k∈N
p−3
293
In the last inequality we use the upper bound supk∈N ð[Cpk ] ≤

√24
293

from Theorem 2.5.



Theorem 6.2 implies:
2n+1
Corollary 6.5. For any odd prime number p and natural numbers k, n the groups Cp2n
have
k and Cpk
difference characteristics
1
1
1
+ √ r · ð[Cpnk−1 × Cpnk ] < 1 + √ r · ð[Abp ]
ð[Cp2n
k ] ≤ 1 −
kr
p
p
p

and
ð[Cp2n+1
] ≤ ð[Cpk ] −
k

1
1
1
+ √ r · ð[Cpnk−1 × Cpn+1
] < ð[Cpk ] + √ r · ð[Abp ].
k
pkr
p
p

7. Evaluating the difference characteristics of 2-groups
In this section we elaborate tools for evaluating the difference characteristics of 2-groups. The following
corollary is a counterpart of Corollary 6.1.
Corollary 7.1. Let k, r be natural numbers. Let h : G → C2rk+1 × C2rk−1 be a surjective homomorphism and K
be its kernel. Then
∆[G] ≤ ∆[K] · 2kr + ∆[h−1 (C2rk × C2rk−1 )] − 1
and

1
1
ð[G] ≤ ð[K] + √ · ð[h−1 (C2rk × C2rk−1 )] − p
.
r
2
|G|

Proof. Consider the Galois ring R := GR(2k , r), whose additive group is isomorphic to C2kr . Its maximal ideal
Im coincides with the subgroup 2R of R, which consists of elements of order ≤ 2k−1 in R. The subset pR × R
of the group R ⋆ R has cardinality 2(2k−1)r and consists of elements of order ≤ 2k in R ⋆ R. By Theorem 5.5,
the group R ⋆ R is isomorphic to C2rk+1 × C2rk−1 . It is easy to see that C2rk × C2rk−1 is the unique subgroup of
cardinality 2(2k−1)r consisting of elements of order ≤ 2k . Therefore, the group C2rk+1 × C2rk−1 can be identified
with the group R ⋆ R and its subgroup C2rk × C2rk−1 with the subgroup 2R × R of the group R × R. By
Theorem 5.4, the set B = {(x, x2 ) : x ∈ R} is a difference base for the set U (R) × R in the group R × R. So,
∆[U (R) × R] ≤ |R| = 2k . By Propositions 4.1 and 4.2,
∆[G] ≤ ∆[K] · ∆[U (R) × R] − 1 + ∆[h−1 (Im × R)] ≤ ∆[K] · |R| − 1 + ∆[h−1 (2R × R)]

DIFFERENCE BASES IN FINITE ABELIAN GROUPS

9

∆[K] · |R|
1
∆[h−1 (2R × R)]
1
1
ð[G] = p
−p
+p
= ð[K] − p
+ √ · ð[h−1 (2R × R)].
2r
|K| · |R|2
|G|
|K| · |2R| · |R| · |R/2R|
|G|



and hence

This corollary implies the following recursive upper bound for difference characteristics of finite Abelian
2-groups.
Theorem 7.2. Let k1 , . . . , km be natural numbers, and k, r be natural numbers such that 2r ≤ m, k + 1 ≤
min ki and k − 1 ≤ min ki . Then

1≤i≤r

r<i≤2r

m
r
m
2r
r
m
i
i
hY
i
hY
hY
Y
Y
Y
C2ki − 1
C2ki −1 ×
C2ki · 2kr + ∆
C2ki −k+1 ×
C2ki −k−1 ×
C2ki ≤ ∆
∆
i=1

i=1

i=r+1

i=1

i=2r+1

i=r+1

and
m
2r
r
m
m
m
r
i
i
hY
hY
i Y
hY
Y
Y
Y
1
1
C2ki + √ · ð
C2ki −k+1 ×
C2ki −k−1 ×
C2ki ≤ ð
ð
C2ki −
C2ki −1 ×
.
ki
r
2
2
i=2r+1
i=r+1
i=1
i=1
i=1
i=r+1
i=1
Now we shall evaluate the difference characteristics of the 2-groups C2rn .

Proposition 7.3. For any n ∈ N the groups C22n and C22n+1 have difference sizes
√
√
1 + 22n+4 − 7
1 + 22n+3 − 7
2n
n+1
≤ ∆[C2 ] < 2
and
≤ ∆[C22n+1 ] < 3 · 2n
2
2
and difference characteristics
√
√
√
√
1 + 22n+3 − 7
1 + 22n+4 − 7
3
2n
√
≤ ð[C22n+1 ] < √ .
≤ ð[C2 ] < 2 and
2<
2<
n+1
n+1
2
2·2
2
√
1+ 8|G|−7
≤ ∆[G] follows from Theorem 3.1.
Proof. The lower bound
2
The upper bound will be derived from Proposition 2.2(3) which implies that
and
These upper bounds imply

∆[C22n ] < |C2n | + |C2n | = 2 · 2n
∆[C22n+1 ] < |C2n | + |C2n+1 | = 3 · 2n .
3
ð[C22n ] < 2 and ð[C22n+1 ] < √ .
2


Proposition 7.4. For any n ∈ N the group C4n has the difference characteristic
1
1
3
1
.
ð[C4n ] ≤ 1 + √ · ð[C2n ] − n < 1 − n + √
n
2
2
2
2n+1
Proof. Consider the numbers k1 = · · · = kn = 2 and kn+1 = · · · = k2n = 1. By Theorem 7.2,
2n
2n
n
i
hY
Y

1
1
1
1 hY
1
3
C2ki = 1 − n + √ ð[C2n ] < 1 − n + √
C2ki ≤ ð[C1 ] − n + √ ð
ð[C4n ] = ð
C2ki −1 ×
.
n
n
n+1
2
2
2
2
2
2
i=n+1
i=1
i=1
In the last inequality we used the upper bound ð[C2n ] <

√3 ,
2

proved in Proposition 7.3.

Theorem 7.2, Proposition 7.4 and Theorem 2.1 imply:
2n+1
Corollary 7.5. For any k, n ∈ N the group C22n
have the difference characteristics
k and C2k
1
4 
1  3
1
n
n
n
√
√
√
√
+
ð[C
+
×
C
]
<
1
+
ð[C22n
k−1
k
k ] < ð[C4 ] −
2
2
2kn
2n
2n
2
3
and

3 
1
4
.
] < ð[C2k ] · 1 + √
ð[C22n+1
] < ð[C4n × C2k ] + √ ð[C2nk−1 × C2n+1
+√
k
k
n
n+1
2
3 · 2n
2



10

TARAS BANAKH AND VOLODYMYR GAVRYLKIV

8. The difference characteristic of the groups R × U (R)
In this section we obtain an upper bound for the difference characteristics of the groups R × U (R), which
are products of the additive group of a ring R and the multiplicative group U (R) of its units.
Theorem 8.1. For any finite ring R and its multiplicative group U (R) of units the set B = {(x, x) : x ∈ U (R)}
is a difference base for the set A = {(x, y) ∈ R × U (R) : ∃z ∈ U (R) (y − 1)z = x} in the group R × U (R). If
the ring R is local with maximal ideal Im and the residue field F = R/Im , then
p
4 |R| p
|F | − 1 + |F |).
∆[R × U (R)] = |U (R)| − 2 + ∆[Im × U (R)] + ∆[R × (1 + Im )] ≤ |U (R)| − 2 + √
3 |F |

and

ð[R × U (R)] <

s

1−


1
4  1
1
+√ p
.
+p
|F |
3
|F |
|F | − 1

Proof. Given a pair (x, y) ∈ A, we should find two elements a, b ∈ U (R) such that (a − b, ab−1 ) = (x, y). Since
(x, y) ∈ A, there exists z ∈ U (R) such that (y − 1)z = x. Then for the pair (a, b) := (yz, z) we get the required
equality (a − b, ab−1 ) = (yz − z, yzz −1) = ((y − 1)z, y) = (x, y).
Now assume that the ring R is local and consider its (unique) maximal ideal Im . Let π : R → R/Im be the
homomorphism of R onto its residue field F := R/Im . It follows that |R| = |F | · |Im |. The maximality of the
ideal Im guarantees that U (R) = R \ Im and 1 + Im = π −1 (π(1)) is a multiplicative subgroup of U (R). We
claim that (Im × U (R)) ∪ (R × (1 + Im )) ∪ A = R × U (R). Indeed, if a pair (x, y) ∈ R × U (R) does not belong
to (Im × U (R)) ∪ (R × (1 + Im )), then x ∈ U (R) and y ∈
/ 1 + Im . It follows that 1 − y ∈
/ Im and hence the
element 1 − y is invertible, so we can find z = (1 − y)−1 x ∈ U (R) and conclude that (x, y) ∈ A. Theorem 2.1
and the subadditivity of the difference size proved in Proposition 2.2(3) guarantee that
∆[R × U (R)] ≤ ∆[A] + ∆[Im × U (R)] + ∆[R × (1 + Im )] − 2 ≤
p
p
p
4 p
4 p
|Im |( |R| − |Im | + |R|) =
≤ |U (R)| − 2 + √ ( |Im | × |U (R)| + |R| × |Im |) = |U (R)| − 2 + √
3
3
p
p
p 

4 |R| p
4
|F | − 1 + |F | .
= |U (R)| − 2 + √ |Im | |R/Im | − 1 + |R/Im | ≤ |U (R)| − 2 + √
3
3 |F |
q
p
p
Dividing ∆[R × U (R)] by |R × U (R)| = |R|(|R| − |Im |) = |R| 1 − |F1 | , we get the required upper bound
for the difference characteristic
s
s

p
p
1
1
4
4  1
1
|U (R)|
ð[R × U (R)] <
+√ p
+√ p
.
( |F | − 1 + |F |) = 1 −
+p
|R|
|F |
3 |F |2 − |F |
3
|F |
|F | − 1



Combining Theorem 8.1 with Theorem 5.1 describing the structure of the multiplicative groups of the Galois
rings GR(pk , r), we get the following two corollaries.
Corollary 8.2. Let p be a prime number and k, r be natural numbers such that either p ≥ 3 or p = 2 and
k ≤ 2. The group G = Cprk × Cprk−1 × Cpr −1 has difference characteristic
r


4  1
1
1
1
.
= 1 + O pr/2
ð[G] < 1 − r + √ √ r + √ r
p
p
p
−
1
3

Corollary 8.3. For any natural numbers r and k ≥ 3 the group

G := C2rk × C2r−1
k−1 × C2k−2 × C2 × C2r −1
has difference characteristic
ð[G] <

r

1−


4  1
1
1
√
√
√
+
+
=1+O
2r
2r − 1
3
2r

1
2r/2


.

DIFFERENCE BASES IN FINITE ABELIAN GROUPS

11

9. The results of computer calculations
In Table 3 we present the results of computer calculations of the difference sizes of all non-cyclic Abelian
groups G of order 12 ≤ |G| < 96. In this table
&
'
p
1 + 4|G| + 4|G2 | − 3
lb[G] :=
2
is the lower bound given in Corollary 3.2.
Table 3. Difference sizes of non-cyclic Abelian groups G of order 12 ≤ |G| < 96
G
lb[G]
∆[G]
ð[G]

(C2 )2 × C3
5
5
1,4433...

C2 × C8
5
5
1,25

(C4 )2
5
6
1,5

(C2 )2 × C4
6
6
1,5

(C2 )4
6
6
1,5

C2 × (C3 )2
5
5
1,1785...

(C2 )2 × C5
6
6
1,3416...

G
lb[G]
∆[G]
ð[G]

C2 ×C3 ×C4
6
6
1,2247...

(C2 )3 × C3
6
6
1,2247...

(C5 )2
6
6
1,2

C3 × C9
6
6
1,1547...

(C3 )3
6
6
1,1547...

(C2 )2 × C7
6
6
1,1338...

C2 × C16
7
7
1,2374...

G
lb[G]
∆[G]
ð[G]

C4 × C8
7
7
1,2374...

(C2 )2 × C8
7
7
1,2374...

C2 × (C4 )2
7
8
1,4142...

(C2 )3 × C4
8
8
1,4142...

(C2 )5
9
10
1,7677...

(C6 )2
7
7
1,1666...

(C2 )2 × C9
7
7
1,1666...

G
lb[G]
∆[G]
ð[G]

(C3 )2 × C4
7
7
1,1666...

(C2 )3 × C5
8
8
1,2649...

C2 ×C4 ×C5
7
8
1,2649...

(C2 )2 × C11
8
8
1,2060...

(C3 )2 × C5
8
8
1,1925...

C2 ×C3 ×C8
8
8
1,1547...

C3 × (C4 )2
8
8
1,1547...

(C7 )2
8
9
1,2857...

C2 × (C5 )2
8
8
1,1313...

(C2 )2 × C13
8
9
1,2480...

C6 × C9
8
9
1,2247...

C2 × (C3 )3
8
9
1,2247...

G
(C2 )2 ×C3 ×C4 (C2 )4 × C3
lb[G]
8
9
∆[G]
9
10
ð[G]
1,2990...
1,4433...
G
lb[G]
∆[G]
ð[G]

C2 ×C4 ×C7
9
9
1,2026...

(C2 )3 × C7
9
10
1,3363...

(C2 )2 ×C3 ×C5
9
9
1,1618...

(C3 )2 × C7
9
9
1,1338...

C2 × C32
9
10
1,25

C4 × C16
9
10
1,25

C2 ×C4 ×C8
9
10
1,25

G
lb[G]
∆[G]
ð[G]

(C2 )2 ×C16
9
10
1,25

(C8 )2
9
10
1,25

(C4 )3
9
11
1,375

(C2 )3 × C8
10
11
1,375

(C2 )2 ×(C4 )2
10
12
1,5

(C2 )4 × C4
11
12
1,5

(C2 )6
12
14
1,75

G
lb[G]
∆[G]
ð[G]

(C2 )2 ×C17
9
10
1,2126...

C2 ×C4 ×C9
10
10
1,1785...

(C3 )2 × C8
9
10
1,1785...

C2 ×(C3 )2 ×C4 (C2 )3 ×(C3 )2
10
10
10
11
1,1785...
1,2963...

(C2 )3 × C9
10
11
1,2963...

C3 × (C5 )2
10
10
1,1547...

G
lb[G]
∆[G]
ð[G]

(C2 )2 ×C19
10
11
1,2617...

C2 ×C8 ×C5
10
11
1,2298...

(C4 )2 × C5
10
11
1,2298...

(C2 )2 ×C4 ×C5
10
12
1,3416...

(C9 )2
10
11
1,2222...

(C3 )4
10
12
1,3333...

G
lb[G]
∆[G]
ð[G]

(C3 )2 × C9
10
11
1,2222...

C3 × C27
10
11
1,2222...

(C2 )2 ×C3 ×C7 (C2 )3 × C11
10
11
11
12
1,2001...
1,2792...

(C2 )4 × C5
11
12
1,3416...

C2 ×C4 ×C11 C2 ×(C3 )2 ×C5 (C2 )2 ×C23
10
10
11
12
11
12
1,2792...
1,1595...
1,2510...

12

TARAS BANAKH AND VOLODYMYR GAVRYLKIV

10. Acknowledgment
The authors would like to express their sincere thanks to Oleg Verbitsky who turned their attention to
the theory of difference sets and their relation with difference bases, to Orest Artemovych for consultations on
Galois rings, to Alex Ravsky for valuable discussions on difference sizes of product groups, and to MathOverflow
users Seva and Jeremy Rickard for valuable comments.
References
[1] T. Banakh, V. Gavrylkiv, O. Nykyforchyn, Algebra in superextension of groups, I: zeros and commutativity, Algebra Discr.
Math. 3 (2008), 1–29.
[2] T. Banakh, V. Gavrylkiv, Difference bases in cyclic groups, preprint (https://arxiv.org/abs/1702.02631).
[3] G. Bini, F. Flamini, Finite commutative rings and their applications, Kluwer Academic Publishers, Boston, MA, 2002.
[4] R.C. Bose, An affine analogue of Singer’s theorem, Journal of the Indian Mathematical Society 6 (1942), 1–15.
[5] R.C. Bose, S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helvetici 37 (1962-63) 141–147.
[6] M. Golay, Notes on the representation of 1, 2, . . . , n by differences, J. London Math. Soc. (2) 4 (1972) 729–734.
[7] J. Leech, On the representation of 1, 2, . . . , n by differences, J. London Math. Soc. 31 (1956), 160–169.
[8] G. Kozma, A. Lev, Bases and decomposition numbers of finite groups, Arch. Math. (Basel) 58:5 (1992), 417–424.
[9] A. Pott, Kai-Uwe Schmidt, Yue Zhou, Semifields, relative difference sets, and bent functions. Algebraic curves and finite fields,
Radon Ser. Comput. Appl. Math., 16, De Gruyter, Berlin, (2014) 161–178.
[10] L. Rédei, A. Rényi, On the representation of the numbers 1, 2, . . . , N by means of differences, Mat. Sbornik N.S. 24(66)
(1949), 385–389.
[11] D. Robinson, A course in the theory of groups, Springer-Verlag, New York, 1996.
[12] I.Z. Ruzsa, Solving a linear equation in a set of integers I, Acta Arithmetica LXV. 3 (1993) 259–282.
[13] J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43:3
(1938), 377–385.
(T. Banakh) Ivan Franko National University of Lviv (Ukraine), and
Institute of Mathematics, Jan Kochanowski University in Kielce (Poland)
E-mail address: t.o.banakh@gmail.com
(V. Gavrylkiv) Vasyl Stefanyk Precarpathian National University, Ivano-Frankivsk, Ukraine
E-mail address: vgavrylkiv@gmail.com

