# Groups Containing Small Locally Maximal Product-Free Sets

Authors: Chimere S. Anabanti; Sarah B. Hart
Journal: International Journal of Combinatorics
 (2016)

---

## Abstract

LetG be a group and S a nonempty subset of G. Then, S isproduct-free if a
b
∉
S for all a
,
b
∈
S. We say S is alocally maximal product-free set if S is product-free and not properly contained in any other product-free set. It is natural to ask whether it is possible to determine the smallest possible size of a locally maximal product-free set in G. Alternatively, given a positive integer k, one can ask the following: what is the largest integer n
k such that there is a group of order n
k with a locally maximal product-free set of size k? The groups containing locally maximal product-free sets of sizes 1 and 2 are known, and it has been conjectured that n
3
=
24. The purpose of this paper is to prove this conjecture and hence show that the list of known locally maximal product-free sets of size 3 is complete. We also report some experimental observations about the sequence n
k.


---

## Body

## 1. Introduction

LetG be a group and S a nonempty subset of G. Then, S isproduct-free if a
b
∉
S for all a
,
b
∈
S. For example, if H is a subgroup of G then H
g is a product-free set for any g
∉
H. Traditionally these sets have been studied in abelian groups and have therefore been called sum-free sets (see, e.g., [1, 2]). Since we are working with arbitrary groups it makes more sense to say “product-free” in this context. We say S is alocally maximal product-free set if S is product-free and not properly contained in any other product-free set. We use the termlocally maximal rather than maximal because the majority of the literature in this area usesmaximal to mean maximal by cardinality (e.g., [3, 4]).There are some obvious questions from the definition: given a groupG, what is the maximum cardinality of a product-free set in G and what are the maximal (by cardinality) product-free sets? How many product-free sets are there in G? Given that each product-free set is contained in a locally maximal product-free set, what are the locally maximal product-free sets? What are the possible sizes of locally maximal product-free sets? Most of the work on product-free sets has been done in the abelian group case, particularly for Z and Z
n. The number of sum-free sets in the integers has been studied by, for example, Cameron and Erdös [1] and Green [5], who with Ruzsa also studied the density and number of sum-free sets in abelian groups [6]. The number of sum-free sets of {
1,2
,
…
,
n
} is 2
(
1
/
2
+
o
(
1
)
)
n. The number of sum-free sets of an arbitrary abelian group is 2
(
μ
(
G
)
+
o
(
1
)
)
n. See [7] for further work in this direction. Petrosyan [8] determined the asymptotic behaviour of the number of product-free sets in groups of even order. Green and Ruzsa in [6] also determined the maximal size of a sum-free set in an arbitrary abelian group. For the nonabelian case Kedlaya [9] showed that there exists a constant c such that the largest product-free set in a group of order n is of size at least c
n
11
/
14. See also [10]. Gowers in his work on quasirandom groups proved that if the smallest nontrivial representation of a group G is of dimension k then the largest product-free set in G is of size at most k
-
1
/
3
n (Theorem 3.3 and commentary at the start of Section 5 of [11]). Much less is known about the minimum sizes of locally maximal product-free sets. This question was first asked in [3] and later in [12], where the authors ask what is the minimum size of a locally maximal product-free set in a group of order n? A good bound for this minimum size is still not known. Small locally maximal product-free sets when G is an elementary abelian 2-group are of interest in finite geometry, because they correspond to complete caps in PG(n
-
1,2). Locally maximal sum-free sets for elementary abelian 2-groups of order up to 64 were classified in [13]. In [14], all groups containing locally maximal product-free sets of sizes 1 and 2 were classified. Some general results were also obtained. Furthermore, there was a classification (Theorem 5.6 of [14]) of groups containing locally maximal product-free sets S of size 3 for which not every subset of size 2 in S generates 〈
S
〉. Each of these groups has order of at most 24. Conjecture 5.7 of [14] was that if G is a group of order greater than 24, then G does not contain a locally maximal product-free set of size 3. A list was given of all locally maximal product-free sets in groups of orders up to 24. So the conjecture asserts that this list is the complete list of all such sets. (This list is given in the current paper as Table 1; we include it both for ease of reference and because information from it is needed in the proofs of our results.) The main result of this paper is the following and its immediate corollary.Table 1
Locally maximal product-free sets of size3.
G
S
S
# of locally maximal product-free sets of size3 in G
g
:
g
6
=
1
≅
C
6
g
,
g
3
,
g
5
≅
C
6
1
g
,
h
:
g
3
=
h
2
=
1
,
h
g
h
=
g
-
1
≅
D
6
h
,
g
h
,
g
2
h
≅
D
6
1
g
:
g
8
=
1
≅
C
8
g
,
g
-
1
,
g
4
≅
C
8
2
g
,
h
:
g
4
=
h
2
=
1
,
h
g
h
-
1
=
g
-
1
≅
D
8
h
,
g
h
,
g
2
≅
D
8
4
g
:
g
9
=
1
≅
C
9
g
,
g
3
,
g
8
,
g
,
g
4
,
g
7
≅
C
9
8
g
,
h
:
g
3
=
h
3
=
1
,
g
h
=
h
g
≅
C
3
×
C
3
g
,
h
,
g
2
h
2
≅
C
3
×
C
3
8
g
:
g
10
=
1
≅
C
10
g
2
,
g
5
,
g
8
,
g
,
g
5
,
g
8
≅
C
10
6
g
:
g
11
=
1
≅
C
11
g
,
g
3
,
g
5
≅
C
11
10
g
:
g
12
=
1
≅
C
12
g
2
,
g
6
,
g
10
≅
C
6
1
g
,
g
6
,
g
10
,
g
,
g
3
,
g
8
≅
C
12
8
g
,
h
:
g
6
=
1
,
g
3
=
h
2
,
h
g
h
-
1
=
g
-
1
≅
Q
12
g
,
g
3
,
g
5
≅
C
6
1
Alternating group of degree 4
=
Alt
⁡
(
4
)
x
,
y
,
z
:
x
2
=
y
2
=
z
3
=
1
≅
Alt
⁡
(
4
)
48
x
,
z
,
x
z
x
:
x
2
=
z
3
=
1
x
,
z
,
z
x
z
:
x
2
=
z
3
=
1
g
:
g
13
=
1
≅
C
13
g
,
g
3
,
g
9
,
g
,
g
6
,
g
10
≅
C
13
16
g
:
g
15
=
1
≅
C
15
g
,
g
3
,
g
11
≅
C
15
4
g
,
h
:
g
4
=
h
4
=
1
,
g
h
=
h
g
≅
C
4
×
C
4
g
,
h
,
g
-
1
h
-
1
≅
C
4
×
C
4
16
g
,
h
:
g
8
=
1
,
g
4
=
h
2
,
h
g
h
-
1
=
g
-
1
≅
Q
16
g
,
g
4
,
g
-
1
≅
C
8
2
g
,
h
:
g
8
=
h
2
=
1
,
h
g
h
-
1
=
g
5
(Order 16)
g
,
g
6
,
g
3
h
≅
G
8
g
,
h
:
g
10
=
1
,
g
5
=
h
2
,
h
g
h
-
1
=
g
-
1
≅
Q
20
g
,
g
5
,
g
8
,
g
2
,
g
5
,
g
8
≅
C
10
6
g
,
h
:
g
3
=
h
7
=
1
,
g
h
g
-
1
=
h
2
≅
C
7
⋊
C
3
g
h
,
g
h
-
1
,
g
-
1
≅
C
7
⋊
C
3
42
x
:
x
3
=
1
×
g
,
h
:
g
4
=
1
,
g
2
=
h
2
,
h
g
h
-
1
=
g
-
1
≅
C
3
×
Q
8
g
2
,
x
g
2
,
x
2
g
2
≅
C
6
1
g
,
h
:
g
12
=
1
,
g
6
=
h
2
,
h
g
h
-
1
=
g
-
1
≅
Q
24
g
2
,
g
6
,
g
10
≅
C
6
1
g
,
g
6
,
g
10
≅
C
12
4Theorem 1.
SupposeS is a locally maximal product-free set of size 3 in a group G, such that every two-element subset of S generates 〈
S
〉. Then |
G
|
≤
24.Corollary 2.
If a groupG contains a locally maximal product-free set S of size 3, then |
G
|
≤
24 and the only possibilities for G and S are listed in Table 1.Proof.
If not every two-element subset ofS generates 〈
S
〉, then, by Theorem 5.6 of [14], |
G
|
≤
24. We may therefore assume that every two-element subset of S generates 〈
S
〉. Then |
G
|
≤
24 by Theorem 1. Now Table 1 is a list of all locally maximal product-free sets of size 3 occurring in groups of order up to 24 (a version of this table appeared in [14] as a list of such sets in groups of order up to 37). Since we have shown that all locally maximal product-free sets of size 3 occur in groups of order up to 24, this table now constitutes a complete list of possibilities.More generally, given a positive integerk, one can ask the following: what is the largest integer n
k such that there is a group of order n
k with a locally maximal product-free set of size k? Using GAP [15] we have tested all groups of order up to 100 when k
≤
5, and the results suggest that the sequence n
k begins 8,16,24,40,64, which means the sequence (
1
/
8
)
n
k begins 1,2
,
3,5
,
8. This is rather intriguing and it would be interesting to know what the sequence actually is.We finish this section by establishing the notation to be used in the rest of the paper and giving some basic results from [14]. For subsets A and B of a group G, we use the standard notation A
B for the product of A and B. That is, A
B
=
{
a
b
:
a
∈
A, b
∈
B
}. By definition, a nonempty set S
⊆
G is product-free if and only if S
∩
S
S
=
⌀. In order to investigate locally maximal product-free sets, we introduce some further notations. For a set S
⊆
G, we define the following sets:(1)
S
2
=
a
2
:
a
∈
S
;
S
-
1
=
a
-
1
:
a
∈
S
;
S
=
x
∈
G
:
x
2
∈
S
;
T
S
=
S
∪
S
S
∪
S
S
-
1
∪
S
-
1
S
;
S
^
=
s
∈
S
:
s
⊄
S
.For a singleton set {
a
}, we usually write a instead of {
a
}.For a positive integern, we will denote by A
l
t
(
n
) the alternating group of degree n, by C
n the cyclic group of order n, by D
2
n the dihedral group of order 2
n, and by Q
4
n the dicyclic group of order 4
n given by Q
4
n
:
=
〈
x
,
y
:
x
2
n
=
1, x
n
=
y
2, y
x
=
x
-
1
y
〉.We now state the results from [14] that we will use.Lemma 3 (see [14, Lemma 3.1]).
SupposeS is a product-free set in the group G. Then S is a locally maximal product-free set if and only if G
=
T
(
S
)
∪
S.The next result lists, in order, Proposition3.2, Theorem 3.4, Propositions 3.6, 3.7, and 3.8, and Corollary 3.10 of [14].Theorem 4.
LetS be a locally maximal product-free set in a group G. Then (i)
〈
S
〉 is normal in G and G
/
〈
S
〉 is either trivial or an elementary abelian 2-group;
(ii)
|
G
|
≤
2
|
T
(
S
)
|
·
|
〈
S
〉
|;
(iii)
if〈
S
〉 is not an elementary abelian 2-group and |
S
^
|
=
1, then |
G
|
=
2
|
〈
S
〉
|;
(iv)
every elements of S
^ has even order, and all odd powers of s lie in S;
(v)
if there existss
∈
S and integers m
1
,
…
,
m
t such that S
^
=
{
s
,
s
m
1
,
…
,
s
m
t
}, then |
G
| divides 4
|
〈
S
〉
|;
(vi)
ifS
∩
S
-
1
=
⌀, then |
G
|
≤
4
|
S
|
2
+
1.We require one final fact.Theorem 5 (see [14, Theorem 5.1]).
Up to isomorphism, the only instances of locally maximal product-free setsS of size 3 of a group G where |
G
|
≤
37 are given in Table 1.


## 2. Proof of Theorem1

Proposition 6.
SupposeS is a locally maximal product-free set of size 3 in G. If 〈
S
〉 is cyclic, then |
G
|
≤
24.Proof.
WriteS
=
{
a
,
b
,
c
}. First note that since 〈
S
〉 is abelian, S
S
-
1
=
S
-
1
S; moreover a
a
-
1
=
b
b
-
1
=
c
c
-
1
=
1; so |
S
S
-
1
|
≤
7. Also S
S
⊆
{
a
2
,
b
2
,
c
2
,
a
b
,
a
c
,
b
c
}. Thus (2)
T
S
=
S
∪
S
S
∪
S
S
-
1
≤
3
+
6
+
7
=
16
.By Lemma 3, G
=
T
(
S
)
∪
S; so 〈
S
〉
=
T
(
S
)
∪
(
〈
S
〉
∩
S
). Elements of cyclic groups have at most two square roots. Therefore |
〈
S
〉
|
≤
16
+
6
=
22. By Table 1, 〈
S
〉 must now be one of C
6, C
8, C
9, C
10, C
11, C
12, C
13, or C
15. Theorem 4(iv) tells us that every element s of S
^ has even order and all odd powers of s lie in S. This means that, for C
9, C
11, C
13, or C
15, we have S
^
=
⌀ and so G
=
〈
S
〉. In particular, |
G
|
≤
24.
It remains to considerC
6, C
8, C
10, and C
12. For C
6
=
〈
g
:
g
6
=
1
〉, the unique locally maximal product-free set of size 3 is S
=
{
g
,
g
3
,
g
5
}. Now if g or g
5 is contained in S
^, then S
^ consists of powers of a single element; so, by Theorem 4(v), |
G
| divides 24. If neither g nor g
5 is in S
^, then |
S
^
|
≤
1, and so by Theorem 4(iii), therefore, |
G
| divides 12. In C
8 there is a unique (up to group automorphisms) locally maximal product-free set of size 3, and it is {
g
,
g
-
1
,
g
4
}, where g is any element of order 8. If S
^ contains g or g
-
1, then S contains all odd powers of that element by Theorem 4(iv), and hence S contains {
g
,
g
3
,
g
5
,
g
7
}, a contradiction. Therefore |
S
^
|
≤
1 and so |
G
| divides 16. Next, we consider 〈
S
〉
=
C
10. Recall that elements of S
^ must have even order. If S
^ contains any element of order 10, then S contains all five odd powers of this element, which is impossible by Theorem 4(iv). This leaves only the involution of C
10 as a possible element of S
^. Hence again |
S
^
|
≤
1 and |
G
| divides 20. Finally we look at C
12. If S
^ contains any element of order 12, then |
S
|
≥
6, a contradiction. If S
^ contains an element x of order 6 then S contains all three of its odd powers, so S
=
{
x
,
x
3
,
x
5
}. But then 〈
S
〉
≅
C
6, contradicting the assumption that 〈
S
〉
=
C
12. Therefore, S
^ can only contain elements of order 2 or 4. Up to group automorphism, we see from Table 1 that every locally maximal product-free set S of size 3 in C
12 with 〈
S
〉
=
C
12 is one of {
g
,
g
6
,
g
10
} or {
g
,
g
3
,
g
8
} for some generator g of C
12. Each of these sets contains exactly one element of order 2 or 4. Therefore, in every case, |
S
^
|
≤
1 and so |
G
| divides 24. This completes the proof.Note that the bound on|
G
| in Proposition 6 is attainable. For example, in Q
24 there is a locally maximal product-free set S of size 3, with 〈
S
〉
≅
C
12.Proposition 7.
SupposeS is a locally maximal product-free set of size 3 in G such that every 2-element subset of S generates 〈
S
〉. Then either |
G
|
≤
24 or S contains exactly one involution.Proof.
First supposeS contains no involutions. If S
∩
S
-
1
=
⌀, then Theorem 4(vi) tells us that G has order of at most 37, and then, by Theorem 5, (
G
,
S
) is one of the possibilities listed in Table 1. In particular |
G
|
≤
24. If S
∩
S
-
1
≠
⌀, then S
=
{
a
,
a
-
1
,
b
} for some a, b. But then 〈
S
〉
=
〈
a
,
a
-
1
〉
=
〈
a
〉, so 〈
S
〉 is cyclic. Now by Proposition 6 we get |
G
|
≤
24. Next, suppose that S contains at least two involutions (a, b), with the third element being c. Then, since every 2-element subset of S generates 〈
S
〉, we have that H
=
〈
S
〉
=
〈
a
,
b
〉 is dihedral and S is a locally maximal product-free set in H. Let o
(
a
b
)
=
m, so H
≅
D
2
m. The nontrivial coset of the subgroup 〈
a
b
〉 is product-free of size m. So if c lies in this coset, then we have m
=
3 and H
≅
D
6. If c does not lie in this coset then c
=
(
a
b
)
i for some i, and from the relations in a dihedral group a
c
-
1
=
c
a, c
-
1
a
=
a
c, b
c
-
1
=
c
b, and c
-
1
b
=
b
c. The coset 〈
a
b
〉
a consists of m involutions, which cannot lie in S. Thus 〈
a
b
〉
a
⊆
T
(
S
) by Lemma 3. A straightforward calculation shows that (3)
a
b
a
=
T
S
∩
a
b
a
=
a
,
b
,
a
c
,
c
a
,
b
c
,
c
b
,
a
c
-
1
,
c
-
1
a
,
b
c
-
1
,
c
-
1
b
=
a
,
b
,
a
c
,
c
a
,
b
c
,
c
b
.This means m
≤
6, and S consists of two generating involutions a, b plus a power of their product a
b, with the property that any two-element subset of S generates 〈
a
,
b
〉. A glance at Table 1 shows there are no locally maximal product-free sets of this form in D
2
m for m
≤
6. Therefore the only possibility is that 〈
S
〉
≅
D
6, with S consisting of the three reflections in 〈
S
〉. By Theorem 4(i), the index of 〈
S
〉 in G is a power of 2. By Theorem 4(ii), |
G
|
≤
2
|
T
(
S
)
|
·
|
〈
S
〉
|. Thus |
G
|
∈
{
6,12,24,48
}. Suppose for contradiction that |
G
|
=
48. Now G
=
T
(
S
)
∪
S, and since S consists of involutions, the elements of S have order 4. So G contains two elements of order 3 and three elements of order 2 and the remaining nonidentity elements have order 4. Then the 46 elements of G whose order is a power of 2 must lie in three Sylow 2-subgroups of order 16, with trivial pairwise intersection. Each of these groups therefore has a unique involution and 14 elements of order 4, all of which square to the given involution. But no group of order 16 has fourteen elements of order 4. Hence |
G
|
≠
48, and so |
G
|
≤
24. Therefore either |
G
|
≤
24 or G contains exactly one involution.Before we establish the next result, we first make a useful observation. SupposeS
=
{
a
,
b
,
c
}, where a
,
b
,
c
∈
G and c is an involution. Then a straightforward calculation shows that(4)
T
S
⊆
1
,
a
,
b
,
c
,
a
2
,
b
2
,
a
b
,
b
a
,
a
c
,
c
a
,
b
c
,
c
b
,
a
b
-
1
,
b
a
-
1
,
c
a
-
1
,
c
b
-
1
,
a
-
1
b
,
a
-
1
c
,
b
-
1
a
,
b
-
1
c
.Lemma 8.
SupposeS is a locally maximal product-free set of size 3 in G, every 2-element subset of S generates 〈
S
〉, and S contains exactly one involution. Then either |
G
|
≤
24 or S
=
{
a
,
b
,
c
}, where a, b have order 3 and c is an involution.Proof.
SupposeS
=
{
a
,
b
,
c
}, where c is an involution and a, b are not. Consider a
-
1. Recall that G
=
T
(
S
)
∪
S. If a
-
1
∈
S then a
-
2
∈
{
a
,
b
,
c
} which implies that either a has order 3 or 〈
S
〉 is cyclic (because, e.g., if a
-
2
=
b then 〈
S
〉
=
〈
a
,
b
〉
=
〈
a
〉). Thus if a
-
1
∈
S then either a has order 3 or (by Proposition 6)   |
G
|
≤
24. Now suppose that a
-
1
∈
T
(
S
). The elements of T
(
S
) are given in (4). If a
-
1
∈
{
b
,
b
2
,
a
b
,
b
a
,
a
b
-
1
,
b
a
-
1
,
a
-
1
b
,
b
-
1
a
} then, by remembering that 〈
S
〉
=
〈
a
,
b
〉, we deduce that 〈
S
〉 is cyclic, generated by either a or b. For example, a
-
1
=
b
a implies b
∈
〈
a
〉. Similarly, if a
-
1
∈
{
c
,
a
c
,
c
a
,
a
-
1
c
,
c
-
1
a
}, then 〈
S
〉 is cyclic. Since a has order of at least 3, we cannot have a
-
1
∈
{
1
,
a
}. If a
-
1
∈
{
b
c
,
c
b
,
b
-
1
c
,
c
-
1
b
}, then S would not be product-free. For instance, a
-
1
=
b
-
1
c implies that b
-
1
c
a
=
1, and hence a
c
=
b. The only remaining possibility is a
-
1
=
a
2, meaning that a has order 3. The same argument with b
-
1 shows that b also has order 3.We can now prove Theorem1, which states that if S is a locally maximal product-free set of size 3 in a group G, such that every two-element subset of S generates 〈
S
〉, then |
G
|
≤
24.Proof of Theorem1.
SupposeS is a locally maximal product-free set of size 3 in G such that every two-element subset of S generates 〈
S
〉. Then, by Lemma 8, either |
G
|
≤
24 or S
=
{
a
,
b
,
c
}, where a, b have order 3 and c is an involution. In the latter case, we observe that a
c
a
-
1 is an involution and so must be contained in T
(
S
). Using (4) we work through the possibilities. Obviously it is impossible for a
c
a
-
1 to be equal to any of 1
,
a
,
b
,
a
2, or b
2 because these elements are not of order 2. If any of a
c
,
c
a
,
a
-
1
c
,
c
-
1
a
,
b
c
,
c
b
,
b
-
1
c, or c
b
-
1 were involutions, then it would imply that 〈
S
〉 was generated by two involutions whose product has order 3. For example, if a
c were an involution then 〈
c
,
a
c
〉
=
〈
a
,
c
〉
=
〈
S
〉. That is, 〈
S
〉 would be dihedral of order 6. But there is no product-free set in D
6 containing two elements of order 3, because if x, y are the elements of order 3 in D
6 then x
2
=
y and y
2
=
x. So the remaining possibilities for a
c
a
-
1 are c
,
a
b
,
b
a
,
a
b
-
1
,
b
a
-
1
,
a
-
1
b, and b
-
1
a. Now a
c
a
-
1
=
a
b implies c
=
b
a, whereas a
c
a
-
1
=
a
b
-
1 implies b
c
=
a and a
c
a
-
1
=
b
a
-
1 implies b
=
a
c, each of which contradicts the fact that S is product-free. We are now left with the cases a
c
a
-
1
=
c, a
c
a
-
1
=
b
a, and a
c
a
-
1
=
a
-
1
b (which, if it is an involution, equals b
-
1
a). If a
c
a
-
1
=
c, then 〈
S
〉
=
〈
a
,
c
〉
=
C
6, but the only product-free set of size 3 in C
6 contains no elements of order 3, so this is impossible. Therefore a
c
a
-
1
∈
{
b
a
,
a
-
1
b
}. If a
c
a
-
1
=
b
a, then a
-
1
b
a
=
c
a
-
1, so a
c
=
a
-
1
b
-
1
a, which has order 3. If a
c
a
-
1
=
a
-
1
b, then a
c
=
a
-
1
b
a, again of order 3. So we see that 〈
S
〉
=
〈
a
,
c
:
a
3
=
1
,
c
2
=
1
,
(
a
c
)
3
=
1
〉. This is a well known presentation of the alternating group A
l
t
(
4
). As c is the only element of S whose order is even, we see that |
S
^
|
≤
1, and hence |
G
|
≤
2
|
A
l
t
(
4
)
|
=
24. Therefore in all cases |
G
|
≤
24.


## 3. A Table of All Locally Maximal Product-Free Sets of Size 3

Though Table1 is essentially the same as the one in [14], we have taken the opportunity here to correct a typographical error in the entry for the (unnamed) group of order 16. The data was obtained using simple GAP programs [15] and additionally verified by hand for the smaller groups.



---

*Source: 8939182-2016-10-13.xml*