LARGE SUM-FREE SETS IN TERNARY SPACES

VSEVOLOD F. LEV

Abstract. We show that any sum-free subset A ⊆ 𝔽_{3}^{r} (with an integer r ≥ 3), satisfying |A| > 5 · 3^{r−3}, is contained in a hyperplane. This bound is best possible: there exist sum-free subsets of cardinality |A| = 5 · 3^{r−3} not contained in a hyperplane.

Conjecturally, if A ⊆ 𝔽_{3}^{r} is maximal sum-free and aperiodic (not a union of cosets of a non-zero subgroup), then |A| ≤ (3^{r−1} + 1)/2. If true, this is best possible and allows one for any fixed ε > 0 to establish the structure of all sum-free subsets A ⊆ 𝔽_{3}^{r} such that |A| > (1/6 + ε) · 3^{r}.

1. Preliminaries and summary of results

A subset A of an abelian group is called sum-free if the equation x + y = z has no solutions in the elements of A; in other words, if a_{1} + a_{2} ∉ A for any a_{1}, a_{2} ∈ A. For the background motivating one’s interest in sum-free sets, historical account, and current state of the art, we refer the reader to [GR00, K98], or [WSW72].

How large can a sum-free subset of a finite abelian group be? For some groups the answer has been known for over 30 years, see [DY69, RS70, Y72, Y75]; however, for a number of “tough” groups this question remained open until recent paper by Green and Ruzsa [GR00]. Much effort has been made also to determine the structure of sum-free subsets of the maximum possible size; for numerous results of this sort and further references see [WSW72]. Particularly relevant in our context is [WSW72, Corollary 7.11] asserting that any sum-free subset of the elementary abelian 3-group of rank r has at most 3^{r−1} elements and moreover, any sum-free subset with this maximum possible number of elements is a coset of an index three subgroup. On the other hand, to our knowledge there were almost no attempts to advance one step further and to describe all large sum-free subsets of a given finite abelian group.

One remarkable exception is [DT89] by Davydov and Tombak where it is shown that any sum-free subset A of the elementary abelian 2-group of rank r ≥ 4, such that |A| > 5 · 2^{r−4}, is contained in a proper coset. The bound 5 · 2^{r−4} is tight: there are sum-free subsets of this cardinality, not contained in a proper coset. Indeed, the main result of [DT89] is much stronger and in a sense is parallel to Conjecture 1 below. It is worth mentioning that Davydov and Tombak were motivated by coding theory applications; their results can be interpreted also in terms of the finite projective geometry PG(r − 1, 2).

In this paper we consider another particular family of groups, specifically, the elementary abelian 3-groups. We identify these groups with the additive groups of finite-dimensional vector spaces over the three-element field, and accordingly denote them by 𝔽_{3}^{r}; here the integer r ≥ 1 is the rank of the group, or equivalently the dimension of the vector space.

For an abelian group G, by SF[G] we denote the family of all sum-free subsets of G. Since any A ∈ SF[G] is contained in a maximal (by inclusion) sum-free subset, these latter play a particularly important role, and we denote the collection of all maximal sum-free subsets of G by MSF[G].

Suppose that A ∈ SF[𝔽_{3}^{r}] and fix arbitrarily a ∈ A. Then (a + A) ∩ (a − A) = ∅ as a + a_{1} = a − a_{2} is equivalent to a_{1} = 2a_{2}, which is impossible for a_{1}, a_{2} ∈ A. Thus a − A, a + A, and A are pairwise disjoint and it follows that |A| ≤ |𝔽_{3}^{r}|/3 = 3^{r−1}.

Conversely, any hyperplane in 𝔽_{3}^{r} (that is, a set of the form g + H where H < 𝔽_{3}^{r} is an index three subgroup and g ∈ 𝔽_{3}^{r} \ H) is sum-free, and so is any subset of a hyperplane. This shows that the maximum possible cardinality of a sum-free subset A ⊆ 𝔽_{3}^{r} is 3^{r−1}, and suggests the following question:

how large can |A| be given that A ∈ SF[𝔽_{3}^{r}] is not contained in a hyperplane?

For r ≥ 1 we let

s(𝔽_{3}^{r}) := max{|A|: A ∈ SF[𝔽_{3}^{r}] is not contained in a hyperplane}
= max{|A|: A ∈ MSF[𝔽_{3}^{r}] is not a hyperplane},

with the understanding that max ∅ = 0. (A simple yet important observation implicitly used here is that a maximal sum-free subset of 𝔽_{3}^{r} is contained in a hyperplane if and only if it is a hyperplane itself.) Our main goal is to find the precise value of s(𝔽_{3}^{r}) for all r ≥ 1.

Evidently, any non-empty sum-free subset of 𝔽_{3}^{1} consists of exactly one non-zero element, hence this subset is a hyperplane and therefore

s(𝔽_{3}^{1}) = 0.

Furthermore, it is easily seen (Lemma 2 below) that up to linear automorphisms there is just one maximal sum-free subset of 𝔽_{3}^{2}, namely

A := {e_{1}, e_{2}, 2e_{1} + 2e_{2}}

where e_{1}, e_{2} form a basis of 𝔽_{3}^{2}. Since A = e_{1} + {0, e_{2} − e_{1}, e_{1} − e_{2}} is a hyperplane, one has

s(𝔽_{3}^{2}) = 0.

Things change when we pass to r = 3: subsets A ∈ MSF[𝔽_{3}^{3}] which are not a hyperplane do exist. Indeed, Lemma 3 shows that up to automorphisms of 𝔽_{3}^{3} there are two such subsets, specifically

{e_{1}, e_{2}, e_{3}, 2e_{1} + 2e_{2} + 2e_{3}}

and

{e_{1}, e_{2}, e_{3}, e_{1} + e_{2} + e_{3}, e_{1} + 2e_{2} + 2e_{3}}

where e_{1}, e_{2}, e_{3} form a basis of 𝔽_{3}^{3}. Therefore

s(𝔽_{3}^{3}) = 5.

Using a “lifting procedure” it is easy now, for any r ≥ 3, to construct A ∈ MSF[𝔽_{3}^{r}] which is not a hyperplane and such that |A| = 5 · 3^{r−3}.

Example 1. Suppose that r ≥ 3. Fix a subspace L < 𝔽_{3}^{r} of dimension dim L = r − 3 and a basis {ē_{1}, ē_{2}, ē_{3}} of the quotient space 𝔽_{3}^{r}/L. Let A ⊆ 𝔽_{3}^{r} be the full pre-image under the canonical mapping 𝔽_{3}^{r} → 𝔽_{3}^{r}/L of the set

\overline{A} := \{ē_{1}, ē_{2}, ē_{3}, ē_{1} + ē_{2} + ē_{3}, ē_{1} + 2ē_{2} + 2ē_{3}\} ⊆ 𝔽_{3}^{r}/L.

Clearly |A| = 3^{r−3}|\overline{A}| = 5 · 3^{r−3}, and with a little meditation from the fact that \overline{A} is maximal sum-free one deduces that so is A. Observe that A is not a hyperplane as its cardinality is distinct from 3^{r−1}; therefore

s(𝔽_{3}^{r}) ≥ |A| = 5 · 3^{r−3}.

We are now ready to state our main result.

Main Theorem. Let r ≥ 3 and suppose that A ∈ SF[𝔽_{3}^{r}] satisfies |A| > 5 · 3^{r−3}. Then A is contained in a hyperplane of 𝔽_{3}^{r}. Consequently,

s(𝔽_{3}^{r}) = 5 · 3^{r−3}

in view of Example 1.

We prove the Main Theorem and the two lemmas mentioned above in the next section. In Section 3 we introduce a quantity, intimately related to and in a sense, lying somewhat deeper than s(𝔽_{3}^{r}); namely, the maximum cardinality t(𝔽_{3}^{r}) of an aperiodic maximal sum-free subset of 𝔽_{3}^{r}. We discuss then the relation between s(𝔽_{3}^{r}) and t(𝔽_{3}^{r}) and show that t(𝔽_{3}^{r}) ≥ (3^{r−1} + 1)/2 for r ≥ 3; conjecturally, the expression at the right gives the exact value of t(𝔽_{3}^{r}).

2. Proofs

For two sets A, B ⊆ 𝔽_{3}^{r} we write A + B := {a + b: a ∈ A, b ∈ B} and A − B := {a − b: a ∈ A, b ∈ B} and we abbreviate A + A by 2A.

Lemma 1. Let r ≥ 1 be an integer and suppose that A ∈ SF[𝔽_{3}^{r}] and g ∈ 𝔽_{3}^{r}. Then in order for A ∪ {g} ∈ SF[𝔽_{3}^{r}] to hold it is necessary and sufficient that g ∉ 2A and g ∉ A − A.

Leaving the easy verification to the reader, we only note that for abelian groups other than 𝔽_{3}^{r} the extra restriction 2g ∉ A is to be imposed on g. For elementary 3-groups this restriction can be omitted as 2g = a is equivalent to g = 2a.

Corollary 1. A set A ∈ SF[𝔽_{3}^{r}] (with an integer r ≥ 1) is maximal sum-free if and only if 2A ∪ A ∪ (A − A) = 𝔽_{3}^{r}.

Lemma 2. Suppose that A ∈ MSF[𝔽_{3}^{2}]. Then there is a basis {e_{1}, e_{2}} of 𝔽_{3}^{2} such that A = {e_{1}, e_{2}, 2e_{1} + 2e_{2}}.

Proof. Since A is maximal sum-free it is not contained in a proper subspace of 𝔽_{3}^{2}: otherwise for any g not in the subspace the set A∪{g} properly contains A and is sumfree by Lemma 1. Consequently, there is a basis {e_{1}, e_{2}} of 𝔽_{3}^{2} such that {e_{1}, e_{2}} ⊆ A. Evidently 0, 2e_{1}, 2e_{2}, e_{1} + e_{2}, e_{1} − e_{2}, e_{2} − e_{1} ∉ A whence

A ⊆ {e_{1}, e_{2}, 2e_{1} + 2e_{2}},  (1)

and since the set at the right is sum-free we actually have equality in (1). □

Suppose that {e_{1}, e_{2}, e_{3}} is a basis of 𝔽_{3}^{3} and consider the set

A := {e_{1}, e_{2}, e_{3}, e_{1} + e_{2} + e_{3}, e_{1} + 2e_{2} + 2e_{3}}.

We have

2A = {2e_{1}, 2e_{2}, 2e_{3}, e_{1} + e_{2}, e_{2} + e_{3}, e_{1} + e_{3}, e_{1} + 2e_{2}, e_{1} + 2e_{3}, 2e_{1} + e_{2} + e_{3}, e_{1} + 2e_{2} + e_{3}, e_{1} + e_{2} + 2e_{3}, 2e_{1} + 2e_{2} + 2e_{3}}

and

A − A = {0, e_{1} + e_{2}, e_{2} + e_{3}, e_{1} + e_{3}, 2e_{1} + 2e_{2}, 2e_{2} + 2e_{3}, 2e_{1} + 2e_{3}, e_{1} + 2e_{2}, e_{1} + 2e_{3}, e_{2} + 2e_{1}, e_{2} + 2e_{3}, e_{3} + 2e_{1}, e_{3} + 2e_{2},

e_{1} + 2e_{2} + e_{3}, 2e_{1} + e_{2} + 2e_{3}, e_{1} + e_{2} + 2e_{3}, 2e_{1} + 2e_{2} + e_{3}},

thus A ∩ 2A = ∅ and 2A ∪ A ∪ (A − A) = 𝔽_{3}^{3} whence A ∈ MSF[𝔽_{3}^{3}] by Corollary 1. Moreover, A is not a hyperplane since |A| = 5 ≠ 3^{2}.

Lemma 3. Suppose that A ∈ MSF[𝔽_{3}^{3}] is not a hyperplane of 𝔽_{3}^{3}. Then there exists a basis {e_{1}, e_{2}, e_{3}} of 𝔽_{3}^{3} such that either

A = {e_{1}, e_{2}, e_{3}, 2e_{2} + 2e_{2} + 2e_{3}}

or

A = {e_{1}, e_{2}, e_{3}, e_{1} + e_{2} + e_{3}, e_{1} + 2e_{2} + 2e_{3}}.

Proof. Since A is not contained in a hyperplane, there exist z ∈ 𝔽_{3}^{3} and a basis F := {f_{1}, f_{2}, f_{3}} of 𝔽_{3}^{3} such that, letting F_{0} := {0, f_{1}, f_{2}, f_{3}}, we have z + F_{0} ⊆ A. Throughout the rest of the proof we consider 𝔽_{3}^{3} as the three-dimensional coordinate space (over the field 𝔽_{3}) with the standard basis F; thus, for instance, (0, 1, 2) = f_{2} + 2f_{3}.

Since A is sum-free, so is z+F_{0}; this means (2(z+F_{0}))∩(z+F_{0}) = ∅ or equivalently z ∉ F_{0} − 2F_{0}. One checks easily that the complement of F_{0} − 2F_{0} in 𝔽_{3}^{3} is the set

{(1, 1, 1), (2, 2, 2), (1, 1, 2), (1, 2, 1), (2, 1, 1)},

hence up to a renumbering of the basis vectors there are just three options resulting in z + F_{0} ∈ SF[𝔽_{3}^{3}]:

z = (1, 1, 1), z = (2, 2, 2), and z = (1, 1, 2).

The third option actually reduces to the first in view of

f_{1} + f_{2} + 2f_{3} + {0, f_{1}, f_{2}, f_{3}} = (f_{1} + 2f_{3}) + (f_{2} + 2f_{3}) + 2f_{3} + {0, f_{1} + 2f_{3}, f_{2} + 2f_{3}, 2f_{3}}

and since f_{1} + 2f_{3}, f_{2} + 2f_{3}, 2f_{3} form a basis of 𝔽_{3}^{3}. The two remaining cases are now easy to handle.

Suppose first that z = (1, 1, 1). Then

2(z + F_{0}) = {(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1),
(0, 1, 1), (1, 0, 1), (1, 1, 0), (2, 0, 0), (0, 2, 0), (0, 0, 2)} + (2, 2, 2)
= {(2, 0, 0), (0, 2, 0), (0, 0, 2), (0, 2, 2), (2, 0, 2), (2, 2, 0),
(1, 2, 2), (2, 1, 2), (2, 2, 1), (2, 2, 2)}

and

(z + F_{0}) − (z + F_{0}) = {(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (2, 0, 0), (0, 2, 0), (0, 0, 2), (0, 1, 2), (0, 2, 1), (1, 0, 2), (2, 0, 1), (1, 2, 0), (2, 1, 0)},

so that all elements of 𝔽_{3}^{3} except

(0, 1, 1), (1, 0, 1), (1, 1, 0)  (2)

are contained either in z + F_{0}, or in 2(z + F_{0}), or in (z + F_{0}) − (z + F_{0}). By Lemma 1, the set A is obtained from z + F_{0} by adding to it some of the vectors (2). It remains to observe that in fact, adding any one of these vectors we get a maximal sum-free set of the required kind; say, letting e_{1} := (2, 1, 1), e_{2} := (1, 2, 1), and e_{3} := (1, 1, 2) we get

(z + F_{0}) ∪ {(0, 1, 1)} = {(1, 1, 1), (2, 1, 1), (1, 2, 1), (1, 1, 2), (0, 1, 1)} = {e_{1}, e_{2}, e_{3}, e_{1} + e_{2} + e_{3}, e_{1} + 2e_{2} + 2e_{3}}

and by the remark preceding the lemma this set is maximal sum-free.

Now suppose that z = (2, 2, 2). Then

2(z + F_{0}) = {(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1),

(0, 1, 1), (1, 0, 1), (1, 1, 0), (2, 0, 0), (0, 2, 0), (0, 0, 2)} + (1, 1, 1)

= {(1, 2, 2), (2, 1, 2), (2, 2, 1), (2, 1, 1), (1, 2, 1), (1, 1, 2),
(0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1)}

and (z+F_{0})−(z+F_{0}) is as above, hence (2(z+F_{0}))∪(z+F_{0})∪((z+F_{0})−(z+F_{0})) = 𝔽_{3}^{3} and therefore z + F_{0} ∈ MSF[𝔽_{3}^{3}] by Corollary 1. It follows that

A = z + F_{0} = {(2, 2, 2), (0, 2, 2), (2, 0, 2), (2, 2, 0)}

and letting e_{1} := (0, 2, 2), e_{2} := (2, 0, 2), e_{3} := (2, 2, 0) we get

A = {e_{1}, e_{2}, e_{3}, 2e_{1} + 2e_{2} + 2e_{3}},

as wanted. □

To establish the Main Theorem we need one more lemma. Given a vector system {e_{1}, e_{2}, …} we denote by ⟨e_{1}, e_{2}, …⟩ its linear span; that is, the subgroup generated by e_{1}, e_{2}, …

Lemma 4. Suppose that e_{1}, e_{2}, e_{3} ∈ 𝔽_{3}^{4} are linearly independent, and let A ∈ SF[𝔽_{3}^{4}] satisfy either {e_{1}, e_{2}, e_{3}, e_{1} + e_{2} + e_{3}} ⊆ A or {e_{1}, e_{2}, e_{3}, 2e_{1} + 2e_{2} + 2e_{3}} ⊆ A. Then

|A \ ⟨e_{1}, e_{2}, e_{3}⟩| ≤ 10.

We have not proved Lemma 4 in a “traditional way” but rather verified it using a computer^{1}.

Proof of the Main Theorem. We have to prove that if r ≥ 4 and A ∈ MSF[𝔽_{3}^{r}] is not a hyperplane, then |A| ≤ 5 · 3^{r−3}. We distinguish two cases.

1) First, assume that there exist a_{1}, a_{2}, a_{3} ∈ A such that a_{1} + a_{2} + a_{3} ∈ A. Since A is sum-free, none of a_{1}, a_{2}, a_{3}, and ε_{1}a_{1} + ε_{2}a_{2} + ε_{3}a_{3} with ε_{1}, ε_{2}, ε_{3} ∈ {1, 2} equal zero. Furthermore, equalities of the sort a_{1} + εa_{2} = 0 with ε ∈ {1, 2} do not hold either, for if a_{1} + a_{2} = 0 then 2a_{1} = a_{2} ∈ A, and if a_{1} + 2a_{2} = 0 then a_{3} − a_{2} = a_{1} + a_{2} + a_{3} ∈ A. This shows that a_{1}, a_{2}, and a_{3} are linearly independent, and we let L := ⟨a_{1}, a_{2}, a_{3}⟩ so that

A ∩ L ⊇ {a_{1}, a_{2}, a_{3}, a_{1} + a_{2} + a_{3}}.

For any z ∈ 𝔽_{3}^{r} \ L, applying Lemma 4 to the set A ∩ ⟨a_{1}, a_{2}, a_{3}, z⟩ we get

|((z + L) ∪ (−z + L)) ∩ A| ≤ 10.  (3)

Partitioning 𝔽_{3}^{r} into L-cosets and estimating the intersection of A with each pair of non-zero cosets, we obtain

|A \ L| ≤ \frac{3^{r−3} − 1}{2} · 10 = 5 · 3^{r−3} − 5.  (4)

1Our computer program uses a branch-and-cut algorithm to construct all sum-free sets A ⊆ 𝔽_{3}^{4} such that either A ∩ ⟨e_{1}, e_{2}, e_{3}⟩ ⊇ {e_{1}, e_{2}, e_{3}, e_{1} + e_{2} + e_{3}}, or A ∩ ⟨e_{1}, e_{2}, e_{3}⟩ ⊇ {e_{1}, e_{2}, e_{3}, 2e_{1} + 2e_{2} + 2e_{3}}, and which are maximal under this condition. The algorithm is implemented as a recursive sub-routine determining those elements of 𝔽_{3}^{4} \⟨e_{1}, e_{2}, e_{3}⟩ which can be added to A without violating the sum-free property. Once such an element is found, it is added to A, and then the procedure invokes itself recursively to add more elements, if possible.

We notice now that A ∩ L is a sum-free subset of L not contained in a hyperplane of L in view of

{a_{1}, a_{2}, a_{3}, a_{1} + a_{2} + a_{3}} = a_{1} + a_{2} + a_{3} + {0, 2a_{1} + 2a_{2}, 2a_{1} + 2a_{3}, 2a_{2} + 2a_{3}} ⊆ A

and since 2a_{1} + 2a_{2}, 2a_{1} + 2a_{3}, 2a_{2} + 2a_{3} generate L. By Lemma 3 it follows that

|A ∩ L| ≤ s(𝔽_{3}^{3}) = 5  (5)

and comparing this with (4) we get the desired estimate.

2) Now assume that a_{1} + a_{2} + a_{3} ∉ A for any a_{1}, a_{2}, a_{3} ∈ A so that

2A ∩ (A − A) = ∅.  (6)

In this case we observe first that 2A ⊈ −A: otherwise for any a_{0}, a_{1}, a_{2} ∈ A there exist a_{3}, a_{4} ∈ A such that

a_{1} − a_{2} + a_{0} = −a_{3} − a_{2} = a_{4},

hence (a_{1} − a_{0}) − (a_{2} − a_{0}) = a_{4} − a_{0}, showing that A − a_{0} is a (proper) subspace of 𝔽_{3}^{r} and contradicting the assumption that A is not a hyperplane. Now fix an element g ∈ 2A \ (−A). Then −g ∉ A, −g ∉ A − A (else g ∈ 2A ∩ (A − A) contradicting (6)), whence −g ∈ 2A by Corollary 1. It follows that there exist a_{1}, a_{2}, a_{3}, a_{4} ∈ A satisfying g = a_{1} + a_{2} and −g = a_{3} + a_{4}, which implies −a_{1} − a_{2} − a_{3} ∈ A. We now proceed as in the first case letting L := ⟨a_{1}, a_{2}, a_{3}⟩ (the interested reader will verify easily that a_{1}, a_{2}, and a_{3} are linearly independent) and observing that

A ∩ L ⊇ {a_{1}, a_{2}, a_{3}, 2a_{1} + 2a_{2} + 2a_{3}},

whence (3) holds true for any z ∈ 𝔽_{3}^{r} \ L by Lemma 4, and (5) holds true in view of

{a_{1}, a_{2}, a_{3}, 2a_{1} + 2a_{2} + 2a_{3}} = 2a_{1} + 2a_{2} + 2a_{3} + {0, 2a_{1} + a_{2} + a_{3}, a_{1} + 2a_{2} + a_{3}, a_{1} + a_{2} + 2a_{3}} ⊆ A

and since 2a_{1} + a_{2} + a_{3}, a_{1} + 2a_{2} + a_{3}, a_{1} + a_{2} + 2a_{3} generate L. □

We conclude this section with a lemma expressing a simple, yet rather unusual property of the groups 𝔽_{3}^{r}. This lemma will be used in the next section.

Lemma 5. Let r be a positive integer and suppose that A ⊆ 𝔽_{3}^{r} satisfies |A| > 3^{r−1}. Then A − A = 𝔽_{3}^{r}.

Proof. Fix g ∈ 𝔽_{3}^{r} \ {0} and partition 𝔽_{3}^{r} into cosets of the (three-element) subgroup, generated by g. If g ∉ A − A then any such coset contains at most one element from A whence |A| does not exceed the number of cosets, which is 3^{r−1}. □

Since (A − A) ∩ A = ∅ for a sum-free subset A, Lemma 5 supplies yet another proof of the fact that |A| ≤ 3^{r−1} for any A ∈ SF[𝔽_{3}^{r}].

3. Aperiodic maximal sum-free sets

Recall that for an abelian group G and a subset A ⊆ G, the period of A (in G) is the subgroup of G defined by

H(A) := {h ∈ G: A + h = A}.

Clearly, A is a union of H(A)-cosets and moreover, if A is a union of H-cosets for a subgroup H ≤ G, then H(A) lies above H. The set A is called periodic or aperiodic depending on whether H(A) ≠ {0} or H(A) = {0}.

Suppose that A is a maximal sum-free subset of 𝔽_{3}^{r} and let H be the period of A. Then the canonical image of A in the quotient group 𝔽_{3}^{r}/H is maximal sum-free, too, and this canonical image is aperiodic. Conversely, if H is a proper subgroup of 𝔽_{3}^{r}, then by means of the “lifting procedure” (see Example 1) any aperiodic maximal sum-free subset of the quotient group 𝔽_{3}^{r}/H yields a maximal sum-free subset of 𝔽_{3}^{r}. This shows that aperiodic maximal sum-free subsets are, in a sense, “primitive”, while all other maximal sum-free subsets are “induced”. In other words, aperiodic maximal sum-free subsets are the building blocks from which all other sum-free subsets can be constructed using the lifting procedure. It would be very interesting, therefore, to figure out how large can an aperiodic maximal sum-free subset of 𝔽_{3}^{r} be. Accordingly, for integer r ≥ 1 we define

t(𝔽_{3}^{r}) := max{|A|: A ∈ MSF[𝔽_{3}^{r}] is aperiodic},

the maximum possible size of an aperiodic maximal sum-free subset of 𝔽_{3}^{r}. Evidently, we have

t(𝔽_{3}^{1}) = 1

(maximal sum-free subsets of 𝔽_{3}^{1} are of size one, hence aperiodic). Furthermore,

t(𝔽_{3}^{2}) = 0

by Lemma 2: this is because {e_{1}, e_{2}, 2e_{1} + 2e_{2}} is a periodic subset of 𝔽_{3}^{2}; indeed, it is a coset of the subgroup generated by e_{1} + 2e_{2}. Next, by Lemma 3

t(𝔽_{3}^{3}) = 5  (7)

since the set {e_{1}, e_{2}, e_{3}, e_{1} + e_{2} + e_{3}, e_{1} + 2e_{2} + 2e_{3}} is aperiodic (the cardinality of a periodic subset of 𝔽_{3}^{r} is divisible by three). Using a computer we were able to find also the next value:

t(𝔽_{3}^{4}) = 14.  (8)

Clearly, for any r ≥ 2 we have t(𝔽_{3}^{r}) ≤ s(𝔽_{3}^{r}): for if a subset A ∈ MSF[𝔽_{3}^{r}] is aperiodic then it is not a hyperplane. The following example provides a lower-bound estimate.

Example 2. Let r ≥ 3 be an integer. Fix arbitrarily a subgroup L < 𝔽_{3}^{r} of index [𝔽_{3}^{r} : L] = 3, an element g ∈ 𝔽_{3}^{r} \L, and a subset L_{0} ⊆ L such that 0 ∉ L_{0}, L_{0} ∩(−L_{0}) = ∅, and |L_{0}| = (|L| − 1)/2; thus

L = L_{0} ∪ {0} ∪ (−L_{0})

is a partition of L into a union of three pairwise disjoint subsets. Now define

A := (g + L_{0}) ∪ {2g}.  (9)

It is immediately verified that A is aperiodic and A ∈ SF[𝔽_{3}^{r}]. Moreover, we have

2A = L_{0} ∪ {g} ∪ (2g + 2L_{0})  (10)

and

A − A = (L_{0} − L_{0}) ∪ (g − L_{0}) ∪ (2g + L_{0}).  (11)

We observe that L_{0} − L_{0} = L by Lemma 5 and

{2g} ∪ (2g + 2L_{0}) ∪ (2g + L_{0}) ⊇ 2g + ({0} ∪ (−L_{0}) ∪ L_{0}) = 2g + L

so that A ∪ 2A ∪ (A − A) = 𝔽_{3}^{r} by (9), (10), and (11). Corollary 1 shows that A ∈ MSF[𝔽_{3}^{r}] and therefore

t(𝔽_{3}^{r}) ≥ |A| = (3^{r−1} + 1)/2.

Based on (7), (8), and Example 2 we conjecture the following.

Conjecture 1. For all integer r ≥ 3 we have

t(𝔽_{3}^{r}) = (3^{r−1} + 1)/2.

As already indicated above, Conjecture 1 implies easily our Main Theorem and in fact allows one to go far beyond, establishing for any fixed ε > 0 the structure of all those A ∈ SF[𝔽_{3}^{r}] satisfying |A| > (1/6+ε)·3^{r}. We finish our paper with a proposition explaining (to some extent) this claim.

Proposition 1. Let r ≥ 3 be an integer and suppose that A ∈ SF[𝔽_{3}^{r}] satisfies |A| > 14 · 3^{r−4}(≈ 0.1728 · 3^{r}). Assume that Conjecture 1 holds true. Then either A is contained in a hyperplane of 𝔽_{3}^{r}, or there exist a subgroup H < 𝔽_{3}^{r} of index [𝔽_{3}^{r} : H] = 3^{3} and elements e_{1}, e_{2}, e_{3} ∈ 𝔽_{3}^{r} such that 𝔽_{3}^{r} = ⟨e_{1}, e_{2}, e_{3}⟩ ⊕ H and

A ⊆ {e_{1}, e_{2}, e_{3}, e_{1} + e_{2} + e_{3}, e_{1} + 2e_{2} + 2e_{3}} + H.

Proof. Without loss of generality we can assume that A is maximal sum-free. Let H < 𝔽_{3}^{r} be the period of A and let the index of H in 𝔽_{3}^{r} be 3^{k}. Denote by \overline{A} the image of A in the quotient group 𝔽_{3}^{r}/H. Since \overline{A} is an aperiodic maximal sum-free subset of 𝔽_{3}^{r}/H ≅ 𝔽_{3}^{k}, by Conjecture 1 we have |\overline{A}| ≤ (3^{k−1} + 1)/2 whence

|A| = |\overline{A}||H| ≤ (3^{k−1} + 1) 3^{r−k}/2 = (3^{r−1} + 3^{r−k})/2

and therefore k ≤ 3: for otherwise

|A| ≤ (3^{r−1} + 3^{r−4})/2 = 14 · 3^{r−4},

contradicting the assumptions. There are three possibilities: k = 1, k = 2, and k = 3. If k = 1 then 𝔽_{3}^{r}/H ≅ 𝔽_{3}^{1}; consequently, \overline{A} consists of just one element, hence A is an H-coset. The case k = 2 cannot occur as 𝔽_{3}^{2} contains no aperiodic maximal sum-free subsets (Lemma 2). Finally, if k = 3 then

14 · 3^{r−4} < |A| = |\overline{A}||H| = 3^{r−3}|\overline{A}|

implying |\overline{A}| > 14/3 > 4. By Lemma 3, there is a basis \{ē_{1}, ē_{2}, ē_{3}\} of 𝔽_{3}^{r}/H such that \overline{A} = \{ē_{1}, ē_{2}, ē_{3}, ē_{1} + ē_{2} + ē_{3}, ē_{1} + 2ē_{2} + 2ē_{3}\}; the assertion follows. □

References

[DT89] A. Davydov and L. Tombak, Quasi-perfect linear binary codes with distance 4 and complete caps in projective geometry, Problemy Peredachi Informatzii 25 (4) (1989), 11–23.

[DY69] P.H. Diananda and H.P. Yap, Maximal sum-free sets of elements in finite groups, Proc. Japan Acad. 45 (1969), 1–5.

[GR00] B. Green and I.Z. Ruzsa, Sum-free sets in abelian groups, Submitted.

[K98] K.S. Kedlaya, Product-free subsets of groups, Amer. Math. Monthly 105 (10) (1998), 900–906.

[RS70] A.H. Rhemtulla and A.P. Street, Maximal sum-free sets in finite abelian groups, Bull. Austral. Math. Soc. 2 (1970), 289–297.

[WSW72] J.S. Wallis, A.P. Street, and W.D. Wallis, Combinatorics: Room squares, sum-free sets, Hadamard matrices, Lecture Notes in Mathematics 292 (1972), Springer-Verlag.

[Y72] H.P. Yap, Maximal sum-free sets in finite abelian groups. IV, Nanta Math. 5 (3) (1972), 70–75.

[Y75] H.P. Yap, Maximal sum-free sets in finite abelian groups. V, Bull. Austral. Math. Soc. 13 (3) (1975), 337–342.

Department of Mathematics, University of Haifa at Oranim, Tivon 36006, Israel.

  E-mail address: seva@math.haifa.ac.il