THE INDEPENDENCE NUMBER OF A SUBSET OF AN ABELIAN GROUP

Béla Bajnok^{1}

Department of Mathematics, Gettysburg College, Gettysburg, PA 17325-1486, USA

                         bbajnok@gettysburg.edu

Imre Ruzsa^{2}

Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Pf. 127, H-1364,

Hungary

                             ruzsa@renyi.hu

Received: 11/8/02, Accepted: 1/26/03, Published:1/27/03

Abstract

We call a subset A of the (additive) abelian group G t-independent if for all non-negative integers h and k with h + k ≤ t, the sum of h (not necessarily distinct) elements of A does not equal the sum of k (not necessarily distinct) elements of A unless h = k and the two sums contain the same terms in some order. A weakly t-independent set satisfies this property for sums of distinct terms. We give some exact values and asymptotic bounds for the size of a largest t-independent set and weakly t-independent set in abelian groups, particularly in the cyclic group ℤ_{n}.

1. Introduction

Our motivation for studying the independence number of subsets of an abelian group comes from spherical combinatorics. It was shown by the first author in [4] that if the set of integers A = {a_{1}, a_{2}, …, a_{m}} forms a 3-independent set in the cyclic group ℤ_{n} (as defined below), then the set of n points X = {x_{1}, x_{2}, …, x_{n}} with

x_{i} = \frac{1}{\sqrt{m}} · (cos(\frac{2πia_{1}}{n}), sin(\frac{2πia_{1}}{n}), …, cos(\frac{2πia_{m}}{n}), sin(\frac{2πia_{m}}{n}))

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A02 2

( i = 1, 2, …, n) forms a spherical 3-design on the unit sphere S^{2m−1} (the case of S^{2m} can be reduced to this case). We believe that the concept of t-independence in ℤ_{n} and other abelian groups, extending some of the most well known concepts from additive number theory such as sum-free sets, Sidon sets, and B_{h}-sequences, is of independent interest; here we intend to provide the framework for a general discussion.

1Supported by a Gettysburg College Professional Development Grant and by the Department of Mathematics at Cornell University.

2Supported by the Hungarian National Foundation for Scientific Research (OTKA), Grants No. T 25617, T 29759, T 38396.

Throughout this paper G denotes a finite abelian group with order |G| = n ≥ 2, written in additive notation, and A is a subset of G of size m ≥ 1. For a positive integer h, we use the notation

h · A = \underbrace{A + A + ⋯ + A}_{h} = \{a_{1} + a_{2} + ⋯ + a_{h}|a_{1}, a_{2}, …, a_{h} ∈ A\}.

We introduce the following measure for the degree of independence of A ⊆ G.

Definition 1 Let t be a non-negative integer and A = {a_{1}, a_{2}, …, a_{m}}. We say that A is a t-independent set in G, if whenever

λ_{1}a_{1} + λ_{2}a_{2} + ⋯ + λ_{m}a_{m} = 0

for some integers λ_{1}, λ_{2}, …, λ_{m} with

|λ_{1}| + |λ_{2}| + ⋯ + |λ_{m}| ≤ t,

we have λ_{1} = λ_{2} = ⋯ = λ_{m} = 0. We call the largest t for which A is t-independent the independence number of A in G, and denote it by ind(A).

Equivalently, A is a t-independent set in G, if for all non-negative integers h and k with h + k ≤ t, the sum of h (not necessarily distinct) elements of A can only equal the sum of k (not necessarily distinct) elements of A in a trivial way, that is, h = k and the two sums contain the same terms in some order. We can break up our definition of t-independence into the following three requirements:

0 ∉ h · A for 1 ≤ h ≤ t;  (1)

(h · A) ∩ (k · A) = ∅ for 1 ≤ h < k ≤ t − h;  (2)

and

|h · A| = \binom{m + h − 1}{h} for 1 ≤ h ≤ ⌊\frac{t}{2}⌋.  (3)

It is enough, in fact, to require these conditions for equations containing a total of t or t − 1 terms; therefore the total number of equations considered can be reduced to 2 + (t − 2) + 1 = t + 1.

These conditions and their variations have been studied very vigorously for a long time; it might be worthwhile to briefly review some of the related classic and recent literature here.

Sets satisfying condition (1) (or its versions where there is no limit on the number of terms and/or the terms need to be distinct – see weak independence in Section 5) are called zero-sum-free sets. For example, Erdős and Heilbronn ([14], see also C15 in [18]) asked for the largest number of distinct elements in the cyclic group ℤ_{n} so that no subset has sum zero. Related results can be found in the papers of Alon and Dubiner [1], Caro [11], Gao and Hamidoune [16], Harcos and Ruzsa [20], and their references.

Sets satisfying the condition (h · A) ∩ (k · A) = ∅ are called (h, k)-sum-free sets. The first of these, (1, 2)-sum-free sets, are simply called sum-free sets, and have a vast literature. It is well known and not hard to see that, if sf(G) denotes the maximum size of a sum-free set in G, then

\frac{2}{7}n ≤ sf(G) ≤ \frac{1}{2}n,  (4)

where both inequalities are sharp as sf(ℤ_{7}) = 2 and sf(ℤ_{2}) = 1. A comprehensive survey on sum-free sets in abelian groups can be found in Street’s article [30]; see also the works of Erdős [12], Alon and Kleitman [2], and Cameron and Erdős [10]. Recently, (h, k)-sum-free sets have been investigated in cyclic groups of odd prime order by Bier and Chin [6]. Other recent work on (h, k)-sum-free sets (among the positive integers rather than groups) includes a study of (1, k)-sum-free sets for k ≥ 3 by Calkin and Taylor [9], (3, 4)-sum-free sets by Bilu [7], and (h, k)-sum-free sets by Schoen [28]. We return to sum-free sets in Section 2 as we study 3-independent sets.

Sets satisfying the condition that h-term sums of elements of A be distinct up to the rearrangement of terms, as in (3), are called B_{h}-sequences. They have been studied very extensively among the positive integers, see the book of Halberstam and Roth [19], sections C9 and C11 in Guy’s book [18], and the survey paper of Graham [17]. The case h = 2 is worth special mentioning; a B_{2}-sequence is called a Sidon-sequence after Sidon who introduced them to study Fourier series [29]. An excellent extensive survey of Sidonsequences was written (in Hungarian) by Erdős and Freud [13]. We review Sidon-sets and B_{h}-sequences as we study t-independence for t ≥ 4 in Section 3.

There have recently been attempts to combine some of these conditions. For example, Nathanson [25] investigated sum-free Sidon sets in ℤ_{n}; large Sidon sets were also used to construct small sum-free sets by Baltz, Schoen, and Srivastav [5]. The present paper provides a more general setting for a discussion of these conditions.

Zero-sum-free sets, (h, k)-sum-free sets, and B_{h}-sequences are only three of the many interesting families of linear equations among the integers or in an abelian group. For a survey of general results and other known cases, see the papers of Ruzsa [26] and [27], as well as sections C8 through C16, E12, E28, and E32 of Guy’s wonderful book [18].

We note that some, but not all, of the methods that we describe below can easily be modified to treat t-independence in non-abelian groups. Sum-free (i.e. product-free) sets and Sidon sets in non-abelian groups were discussed by Babai and Sós [3]; see also the recent results of Kedlaya in [21] and [22].

Our objective in this paper is to study the size of a largest t-independent set in an abelian group G, which we denote by s(G, t) (if G has no t-independent subsets, we set s(G, t) = 0).

Since 0 ≤ ind(A) ≤ n − 1 holds for every subset A of G (so no subset is “completely” independent), we see that s(G, 0) = n and s(G, n) = 0. It is also clear that ind(A) = 0 if and only if 0 ∈ A, hence s(G, 1) = n − 1. For the rest of the paper, we assume that 2 ≤ t ≤ n − 1.

First we derive an upper bound for s(G, t) using a simple counting argument, as follows. Suppose that A is a t-independent set in G of size m. Define

⟨A, ⌊t/2⌋⟩ = ⋃_{h=1}^{⌊t/2⌋} h · A.

Since A is t-independent, by conditions (2) and (3) we see that ⟨A, ⌊t/2⌋⟩ has size exactly

∑_{h=1}^{⌊t/2⌋} \binom{m + h − 1}{h} = \binom{m + ⌊t/2⌋}{⌊t/2⌋} − 1.

Therefore, the set −⟨A, ⌊t/2⌋⟩, consisting of the negatives of the elements of ⟨A, ⌊t/2⌋⟩, also has this size; furthermore, we have

⟨A, ⌊t/2⌋⟩ ∩ −⟨A, ⌊t/2⌋⟩ = ∅.

Additionally, by condition (1),

0 ∉ ⟨A, ⌊t/2⌋⟩ ∪ −⟨A, ⌊t/2⌋⟩,

so

n − 1 ≥ 2 · |⟨A, ⌊t/2⌋⟩|,

and therefore

n ≥ 2 · \binom{m + ⌊t/2⌋}{⌊t/2⌋} − 1.

Since for t ≥ 2,

2 · \binom{m + ⌊t/2⌋}{⌊t/2⌋} − 1 > 2 · \frac{m^{⌊t/2⌋}}{⌊t/2⌋!},

we get the following result.

Proposition 2 For every t ≥ 2 we have

s(G, t) < (\frac{1}{2} ⌊\frac{t}{2}⌋!n)^{1/⌊t/2⌋} .

In section 3 we show that Proposition 2 gives the correct magnitude of s(G, t) if G is the cyclic group ℤ_{n}, that is

s(ℤ_{n}, t) = Θ(n^{1/⌊t/2⌋}).

Namely, we prove

Theorem 3 For every ϵ > 0, t ≥ 2, and large enough n,

s(ℤ_{n}, t) > (\frac{1 − ϵ}{t · ⌊(t + 1)/2⌋} · n)^{1/⌊t/2⌋} .

We have succeeded in finding the exact values of s(ℤ_{n}, t) only for t ≤ 3. We have already seen that s(ℤ_{n}, 1) = n − 1, and we can easily verify that

s(ℤ_{n}, 2) = ⌊(n − 1)/2⌋  (5)

(the set {1, 2, …, ⌊(n − 1)/2⌋} is 2-independent and has maximum size as we must have A ∩ −A = ∅). For t = 3, in Section 2 we prove

Theorem 4

s(ℤ_{n}, 3) = \{ \begin{matrix}⌊\frac{n}{4}⌋ & if n is even \\ (1 + \frac{1}{p}) \frac{n}{6} & if n is odd, has prime divisors congruent to 5 (mod 6), \\ & and p is the smallest such divisor \\ ⌊\frac{n}{6}⌋ & otherwise \end{matrix}

Note that these results imply that the coefficient of n in Theorem 3 cannot be improved for t = 2 and t = 3.

Let us now turn to general abelian groups. First note that, according to Proposition 2 and Theorem 3, the exponent of n in the upper bound on s(G, t) given in Proposition 2 is sharp; for

S(t) = lim sup \frac{s(G, t)^{1/⌊t/2⌋}}{n}

we have

\frac{1}{t · ⌊(t + 1)/2⌋} ≤ S(t) ≤ \frac{1}{2} ⌊\frac{t}{2}⌋!.

These inequalities yield S(2) = 1/2, and we later prove that S(3) = 1/4. We do not know the values of S(t) for t ≥ 4.

As for lower bounds, it is clear that we cannot expect a lower bound for s(G, t) in terms of n = |G| only; in fact, if the exponent κ of G is not more than t, then obviously s(G, t) = 0.

We will use the following notations. For a positive integer h, let the “h-torsion” subgroup of G be

Tor(G, h) = {x ∈ G|hx = 0};  (6)

then

Ord(G, h) = ∪_{h=1}^{t}Tor(G, h)  (7)

is the set of those elements of G which have order at most t. By condition (1), no element of Ord(G, h) can be in a t-independent set of G.

We have already noted that s(G, 1) = n − 1, and we can now easily determine the value of s(G, 2): to get a maximum 2-independent set in G, take exactly one of each element or its negative in G \ Ord(G, 2), hence we have

s(G, 2) = \frac{n − Ord(G, 2)}{2}.  (8)

As a special case, for the cyclic group of order n we have (5).

Note that if Ord(G, 2) = G then s(G, 2) = 0; for n ≥ 2 this occurs only for the elementary abelian 2-group. If Ord(G, 2) ≠ G then, since Ord(G, 2) is a subgroup of G, we have 1 ≤ |Ord(G, 2)| ≤ n/2, and therefore we get the following.

Proposition 5 If G is isomorphic to the elementary abelian 2-group, then s(G, 2) = 0. Otherwise

\frac{1}{4}n ≤ s(G, 2) ≤ \frac{1}{2}n.

Let us now consider t = 3. As noted before, if Ord(G, 3) = G, then s(G, 3) = 0; this occurs if and only if G is isomorphic to the elementary abelian p-group for p = 2 or p = 3. In Section 2 we determine some exact values and sharp upper and lower bounds for s(G, 3) in terms of the exponent of G (see Theorem 12); in particular, we prove the following.

Theorem 6 If G is isomorphic to the elementary abelian p-group for p = 2 or p = 3, then s(G, 3) = 0. Otherwise

\frac{1}{9}n ≤ s(G, 3) ≤ \frac{1}{4}n.

These bounds can be attained since s(ℤ_{9}, 3) = 1 and s(ℤ_{4}, 3) = 1.

Studying t-independent sets in G for larger values of t seems considerably more difficult. As a case in point, let t ≥ 4, κ > t be fixed, and consider the sequence of groups

G_{k} = ℤ_{2}^{k} × ℤ_{κ}

(k = 1, 2, 3 …). Suppose that A is a t-independent set in G_{k} and that for some a_{1}, a_{2} ∈ ℤ_{2}^{k} and x ∈ ℤ_{κ}, g_{1} = (a_{1}, x) and g_{2} = (a_{2}, x) are elements of A. Then g_{1} + g_{1} = g_{2} + g_{2} is a non-trivial equation in G_{k}, thus we conclude that g_{1} = g_{2} and |A| ≤ κ. This implies that, as k approaches infinity, we have s(G_{k}, t) = O(1).

Therefore, in order to have a lower bound on s(G, t) which tends to infinity with n, we must have more than just Ord(G, t) ≠ G (as was the case for t ≤ 3); although this will be sufficient for elementary abelian groups (see Corollary 8 below). In general, we require that |Ord(G, t)| be not too large compared to |G| = n; in Section 4, we make this more precise by setting

σ(G, t) = ∑_{k=1}^{t} |Tor(G, k)|  (9)

and proving the following theorem.

Theorem 7 With σ(G, t) as in (9) above we have

s(G, t) ≥ ⌊(\frac{n}{2σ(G, t)})^{1/t}⌋ .

Since obviously σ(G, t) ≤ t · |Ord(G, t)|, we get the corollary that

s(G, t) ≥ ⌊(\frac{n}{2t · |Ord(G, t)|})^{1/t}⌋ .

It is worth comparing the lower bounds of Theorems 3 and 7 for the cyclic group. In ℤ_{n} we have

σ(ℤ_{n}, t) = ∑_{h=1}^{t} |Tor(ℤ_{n}, h)| = ∑_{h=1}^{t} gcd(h, n) ≤ \frac{t(t + 1)}{2}.

Therefore both the exponent of n and the coefficient are approximately twice as large in Theorem 3 as they are in Theorem 7.

Let us state a corollary of Theorem 7 for elementary abelian p-groups.

Corollary 8 Let G be an elementary abelian p-group for a prime p. If p ≤ t, then s(G, t) = 0; otherwise

s(G, t) ≥ (\frac{1}{2}n)^{1/t} .

Finally, in Section 5, we examine weak t-independence: where for all non-negative integers h and k with h + k ≤ t, sums of h distinct elements of a set do not equal sums of k distinct elements in a non-trivial way. A comparison between sum-free and weak sumfree, as well as Sidon and weak Sidon sets, and B_{h} sequences versus weak B_{h} sequences, can be found in Ruzsa’s papers [26] and [27]; there it was shown that their maximum sizes among the positive integers behave similarly. This certainly does not hold for tindependence in abelian groups. Denoting the maximum size of a weakly t-independent set in G by w(G, t), we find that for each fixed t, lim inf w(G, t) tends to infinity with n = |G| (see Theorem 18), while obviously lim inf s(G, t) = 0 for each t ≥ 2. Moreover, the weak independence number of each subset of G can be arbitrarily large, even infinity, while its independence number cannot be more than n.

This paper provides a modest attempt to discuss independence and weak independence in abelian groups. Numerous interesting questions remain open, warranting further study.

2. 3-independent sets in abelian groups

In this section we develop upper and lower bounds for s(G, 3), and provide exact values for some groups, including the cyclic group ℤ_{n}.

Note that, by conditions (1), (2), and (3), a subset A of G is 3-independent, if and only if 0 ∉ A, 0 ∉ A + A, 0 ∉ A + A + A, and

(A + A) ∩ A = ∅.  (10)

Sets satisfying (10) are called sum-free, and have been studied extensively; see [30] for a comprehensive survey.

It is not hard to determine bounds on the maximum size sf(G) of a sum-free set in G. First, note that the set

{⌊(n + 1)/3⌋, ⌊(n + 1)/3⌋ + 1, …, 2⌊(n + 1)/3⌋ − 1}

is a sum-free set in ℤ_{n}; when n is even, the larger set

{1, 3, 5, …, n − 1}

is also sum-free. Since ⌊(n + 1)/3⌋ ≥ \frac{2}{7}n when n ≥ 3 is odd, we have sf(ℤ_{n}) ≥ \frac{2}{7}n. Clearly, if A is sum-free in ℤ_{n}, then H × A is sum-free in H × ℤ_{n} for any abelian group H, so the bound sf(G) ≥ \frac{2}{7}n holds for any G (with n > 1). On the other hand, if A is sum-free in G, then by (10) n ≥ |A + A| + |A| ≥ 2|A|, and we get the well known result that

\frac{2}{7}n ≤ sf(G) ≤ \frac{1}{2}n.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A02 9

Note that these bounds are sharp, as sf(ℤ_{7}) = 2 and sf(ℤ_{2}) = 1.

Our goal is to prove a similar result for 3-independent sets. Let us start with the upper bound.

Proposition 9 Suppose that A is a 3-independent set in G of size m.

1. If none of the divisors of n are congruent to 2 (mod 3), then m ≤ \frac{1}{6}n.

2. Otherwise, let p be the smallest divisor of n which is congruent to 2 (mod 3). Then we have m ≤ \frac{1}{6} (1 + \frac{1}{p}) n.

Proof. Let B = A ∪ (−A). Since A is 3-independent, we have A ∩ (−A) = ∅, thus |B| = 2m. Furthermore, we have

B ∩ (B + B) = ∅.

We apply Kneser’s theorem [24] to the set B. It asserts that either we have

|B + B| ≥ 2|B|,

or there is a subgroup H and an integer k such that B is contained in k cosets of H, and B + B is equal to the union of 2k − 1 cosets.

In the first case we have

n ≥ |B| + |B + B| ≥ 3|B| = 6m

and we are done.

Assume that the second possibility holds. Write |H| = d and q = \frac{n}{d}; we then have

2m = |B| ≤ dk = \frac{n}{q}k,

hence

m ≤ \frac{nk}{2q} .  (11)

Since B cannot intersect any of the 2k − 1 cosets contained in B + B, we have k + (2k − 1) = 3k − 1 ≤ q; if strict inequality holds here, then by (11) we have

m ≤ \frac{nk}{2(3k)} = \frac{1}{6}n,

and we are done again.

Otherwise, q = 3k − 1 ≡ 2 (mod 3), and from (11) we get

m ≤ \frac{n}{2q} \frac{q + 1}{3} = \frac{1}{6} (1 + \frac{1}{q}) n ≤ \frac{1}{6} (1 + \frac{1}{p}) n,

as claimed. □

Note that when n is even, Proposition 9 yields s(G, 3) ≤ \frac{1}{4}n. This is clearly not sharp when Ord(G, 2) is large; by (8) we must have s(G, 2) and therefore s(G, 3) small. More precisely, we have the following upper bound.

Proposition 10 Let κ be the exponent of G and Ord(G, 2) be the set of elements of G with order at most 2. If κ is congruent to 2 (mod 4), then s(G, 3) ≤ \frac{1}{4}(n−|Ord(G, 2)|).

Proof. When κ ≡ 2 (mod 4), we can write G = Z_{2}^{i} × G_{1}, |G_{1}| = n_{1} where n_{1} is odd. The case n_{1} = 1 is obvious, so assume n_{1} ≥ 3. Let A be a 3-independent set in G and write |A| = m. We want to show that m ≤ 2^{i−2}(n_{1} − 1).

Following the proof (and the notations) of Proposition 9 above, we see that we either have

m ≤ \frac{1}{6}n,

or there is a subgroup H of G of index q = 3k − 1, such that B = A ∪ (−A) is contained in k cosets of H, and B + B is equal to the union of 2k − 1 cosets; in this case from (11) we have

m ≤ \frac{nk}{6k − 2}.

Since n_{1} ≥ 3 implies

\frac{1}{6}n ≤ 2^{i−2}(n_{1} − 1),

we can assume that the second possibility holds. Furthermore, an easy computation shows that if n_{1} ≥ 5 and k ≥ 2, then

\frac{nk}{6k − 2} ≤ 2^{i−2}(n_{1} − 1),

so we only need to consider the cases of n_{1} = 3 or k = 1.

If n_{1} = 3, then G = Z_{2}^{i} × Z_{3}. Let B_{0}, B_{1}, B_{2} be the parts of B in the three cosets of Z_{2}^{i}. We have B_{0} = ∅, B_{2} = −B_{1} and B_{1} ∩ (B_{2} + B_{2}) = ∅. Now by an obvious pigeonhole argument we have |B_{2}| ≤ 2^{i−1}, so m ≤ n/6 again. This concludes this case.

Finally assume k = 1. Thus H is a subgroup of index 2, B is contained in the coset G \ H and B + B = H. Since Ord(G, 2) is a subgroup of G of order 2^{i} and H has order 2^{i−1}n_{1}, we have |H ∩ Ord(G, 2)| ≤ 2^{i−1}, and therefore |B| ≤ n/2 − 2^{i−1}, from which our claim follows. □

Now we turn to the lower bound.

Proposition 11 Let κ be the exponent of G and Ord(G, 2) be the set of elements of G with order at most 2.

1. If κ is divisible by 4, then G contains a 3-independent set of size \frac{1}{4}n.

2. If κ is congruent to 2 (mod 4), then G contains a 3-independent set of size \frac{1}{4}(n − |Ord(G, 2)|).

3. Suppose that the odd positive integer d divides κ. Then G contains a 3-independent set of size \frac{1}{d}⌊\frac{d+1}{6}⌋n.

Proof. We construct the desired set explicitly as follows. Suppose that the positive integer d divides κ, and choose a subgroup H and an element g of G so that G is the union of the d distinct cosets H, H + g, …, H + (d − 1)g.

Consider first the set

A = ⋃_{\frac{d}{6} <j< \frac{d}{3}}(H + jg).

It is clear that A is 3-independent. To determine the size of A, note that there are exactly

f(d) = ⌊\frac{d − 1}{3}⌋ − ⌈\frac{d + 1}{6}⌉ + 1

integers strictly between \frac{d}{6} and \frac{d}{3}. When d is odd, f(d) = ⌊\frac{d+1}{6}⌋, proving the last part of our Proposition. Also, f(4) = 1; so choosing d = 4 when κ is divisible by 4 proves the first case of our Proposition.

Assume now that κ is even, but not divisible by 4, and set d = κ. Define

A = ⋃_{i=1}^{⌊ \frac{κ}{4} ⌋}(H + (2i − 1)g).

It is easy to see that A is 3-independent (note that κ is even). For the size of A we have

|A| = ⌊\frac{κ}{4}⌋ · |H| = \frac{κ − 2}{4} · \frac{n}{κ}.

We add some elements to A as follows. Let H′ be a 2-independent set in H of maximum size, and define

A′ = \{h′ + \frac{κ}{2}g|h′ ∈ H′\}.

Since \frac{κ}{2} is odd, it is easy to check that A ∪ A′ is 3-independent. Using (8), we get

|A′| = s(H, 2) = \frac{\frac{n}{κ} − |Ord(H, 2)|}{2}.

But G ≅ H × ℤ_{κ}, therefore |Ord(G, 2)| = 2 · |Ord(H, 2)|, and we get

|A ∪ A′| = \frac{κ − 2}{4} · \frac{n}{κ} + \frac{\frac{n}{κ} − |Ord(H, 2)|}{2} = \frac{1}{4}(n − |Ord(G, 2)|),

as claimed. □

We can now use Propositions 9, 10, and 11 to establish the following bounds and exact values for s(G, 3).

Theorem 12 Let κ be the exponent of G.

1. If κ is divisible by 4, then

s(G, 3) = \frac{n}{4}.

2. If κ is even but not divisible by 4, then

s(G, 3) = \frac{1}{4}(n − |Ord(G, 2)|).

3. If κ (iff n) is odd and has prime divisors congruent to 5 (mod 6), and p is the smallest such divisor, then

s(G, 3) = (1 + \frac{1}{p}) \frac{n}{6}.

4. Finally, if κ (iff n) is odd and has no prime divisors congruent to 5 (mod 6),

then

⌊\frac{κ}{6}⌋ \frac{n}{κ} ≤ s(G, 3) ≤ \frac{n}{6}.

Since the exponent of the cyclic group ℤ_{n} is n, we have settled the value of S(ℤ_{n}, 3); see Theorem 4.

In order to prove Theorem 6, we should estimate |Ord(G, 2)| when κ is even. Let K be a cyclic subgroup of G of order κ, and write H = G/K. Then, since κ is even, |Ord(G, 2)| = 2·|Ord(H, 2)|. Since obviously |Ord(H, 2)| ≤ |H| = \frac{n}{κ}, we get |Ord(G, 2)| ≤ \frac{2n}{κ}, and the first two cases of Theorem 12 yield that when κ is even, we have

⌊\frac{κ}{4}⌋ \frac{n}{κ} ≤ s(G, 3) ≤ \frac{n}{4}.

So if κ ≥ 4 is even, we get

\frac{n}{6} ≤ s(G, 3) ≤ \frac{n}{4},

and when κ ≥ 5 is odd, Theorem 12 implies

\frac{n}{9} ≤ s(G, 3) ≤ \frac{n}{5}.

In particular, we have proved Theorem 6.

3. t-independent sets in the cyclic group

In this section we study the maximum size of a t-independent set in the cyclic group ℤ_{n}. In view of (5) and Theorem 4, it is enough to focus on 4 ≤ t ≤ n − 1.

For t = 4 (in fact, for t ≥ 4), condition (3) requires that pairwise sums (or, equivalently, pairwise differences) of elements of A be essentially distinct. This condition has been studied extensively among the set of positive integers. For a fixed positive integer N, a subset B of {1, 2, …, N} with this property is called a Sidon-sequence after Sidon who introduced them to study Fourier series [29]. An excellent survey of Sidon-sequences was written (in Hungarian) by Erdős and Freud [13]. Denoting the maximum cardinality of a Sidon-sequence in {1, 2, …, N} by F_{2}(N), we have the classic result of Erdős and Turán [15] which says that for every ϵ > 0, δ > 0, and large enough N,

(1 − ϵ)\sqrt{N} < F_{2}(N) < (1 + δ)\sqrt{N};  (12)

and it is a famous conjecture of Erdős that, in fact, |F_{2}(N) − \sqrt{N}| = O(1).

More generally, a subset B of {1, 2, …, N} with the property that all h-term sums of (not necessarily distinct) elements of B are distinct, except for the order of the terms, is called a B_{h}-sequence. Bose and Chowla [8] have shown that, if F_{h}(N) denotes the maximum size of a B_{h}-sequence in {1, 2, …, N}, then for every ϵ > 0 and large enough N, we have

F_{h}(N) > (1 − ϵ)N^{\frac{1}{h}} .  (13)

The simple counting argument leading to Proposition 2, noting that h-term sums of elements of B are in the interval [1, hN], yields the upper bound

F_{h}(N) ≤ (hh!N)^{\frac{1}{h}};

reducing the coefficient of N is the subject of vigorous recent study (see C11 in [18] and its references). It is unknown whether the limit

lim_{n→∞} \frac{F_{h}(N)}{N^{1/h}}

exists for any h ≥ 3. For further references on B_{h}-sequences see the book by Halberstam and Roth [19]; sections C9 and C11 in Guy’s book [18]; and the survey paper of Graham [17].

We use B_{h}-sequences to construct t-independent sets in the cyclic group ℤ_{n}. Elements of ℤ_{n} will be denoted by 0, 1, 2, …, n − 1.

Proposition 13 Let 3 ≤ t ≤ n − 1 and

N = ⌊\frac{⌊n/t⌋}{⌊(t + 1)/2⌋}⌋ ,  (14)

and suppose that B is a B_{⌊t/2⌋}-sequence in the interval [1, N]. Then the set

A = {⌊n/t⌋ − b|b ∈ B}

is t-independent in the cyclic group ℤ_{n}.

Proof. First note that 3 ≤ t ≤ n − 1 guarantees that N < ⌊n/t⌋, and thus, for each a ∈ A, we have

0 < ⌊n/t⌋ − N ≤ a ≤ ⌊n/t⌋ − 1 < n/t.

We verify that requirements (1), (2), and (3) hold. (i) Let 1 ≤ h ≤ t. Since g ∈ h · A satisfies

0 < h · (⌊n/t⌋ − N) ≤ g ≤ h · (⌊n/t⌋ − 1) < n,

we see that (1) holds.

(ii) To show (2), let 1 ≤ h < k ≤ t − h, and suppose, indirectly, that g ∈ h · A ∩ k · A. Then we must have

k · (⌊n/t⌋ − N) ≤ g ≤ h · (⌊n/t⌋ − 1) .

Since k ≥ h + 1, this implies

(h + 1) · (⌊n/t⌋ − N) ≤ h · (⌊n/t⌋ − 1) ,

or, equivalently,

N ≥ \frac{⌊n/t⌋ + h}{h + 1}.

But this contradicts (14), since h ≤ ⌊(t − 1)/2⌋.

(iii) Finally, (3) holds, since for 1 ≤ h ≤ ⌊t/2⌋, B is a B_{h}-sequence in [1, N] and, using self-explanatory notation,

a_{1} + a_{2} + ⋯ + a_{h} = a′_{1} + a′_{2} + ⋯ + a′_{h} in ℤ_{n}

implies

a_{1} + a_{2} + ⋯ + a_{h} = a′_{1} + a′_{2} + ⋯ + a′_{h} in ℤ

and this further implies

b_{1} + b_{2} + ⋯ + b_{h} = b′_{1} + b′_{2} + ⋯ + b′_{h} in ℤ.

□

Theorem 3 is now an easy corollary to Proposition 13 and (13) (also using (5) for t = 2).

It is worthwhile to further analyze the cases t = 4 and t = 5 as follows. Suppose that A is a t-independent set in ℤ_{n} where t ≥ 4. Without loss of generality, we may assume that each a ∈ A satisfies 1 ≤ a ≤ ⌊\frac{n−1}{2}⌋ (replace a by n − a, if necessary). Note that A is a Sidon-sequence in \{1, 2, …, ⌊\frac{n−1}{2}⌋\}. Therefore, by (12), we have

|A| ≤ (1 + o(1)) · \sqrt{n/2},

and this results in the following improvements.

Corollary 14 For every ϵ > 0, δ > 0, and large enough n we have

(\frac{1}{\sqrt{8}} − ϵ) · \sqrt{n} ≤ s(ℤ_{n}, 4) ≤ (\frac{1}{\sqrt{2}} + δ) · \sqrt{n}.

(\frac{1}{\sqrt{15}} − ϵ) · \sqrt{n} ≤ s(ℤ_{n}, 5) ≤ (\frac{1}{\sqrt{2}} + δ) · \sqrt{n}.

We have determined the values of s(ℤ_{n}, 4) and s(ℤ_{n}, 5) for all n ≤ 200. While neither sequence is monotone, the values of s(ℤ_{n}, 4) tend to grow more uniformly; we venture to state the following conjectures.

Conjecture 15 We have

1. lim \frac{s(ℤ_{n},4)}{\sqrt{n}} = \frac{1}{\sqrt{3}},

2. lim \frac{s(ℤ_{n},5)}{\sqrt{n}} does not exist.

It is worth to recall, in comparison, that the sequence s(ℤ_{n}, 2)/n is convergent while s(ℤ_{n}, 3)/n is not. A further observation on these sequences: by Theorem 4, the sequence s(ℤ_{n}, 3) is monotone for even values of n (but not for the odd values); we find that, for n ≤ 200, the sequence s(ℤ_{n}, 5) is monotone for odd values of n (but not for the even values).

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A02 16

4. t-independent sets in abelian groups

In this section we prove the general lower bound for s(G, t) stated in Theorem 7.

Recall that for a positive integer h, we let the “h-torsion” subgroup of G be

Tor(G, h) = {x ∈ G|hx = 0};

and we also defined

σ(G, t) = ∑_{h=1}^{t} |Tor(G, h)|.

Proposition 16 Suppose that m is a positive integer for which

n > σ(G, t) · \binom{2m − 2 + t}{t}.

Then G has a t-independent set of size m.

Proof. We use induction on m. For m = 1 we have n > σ(G, t), thus we can choose an element

a ∈ G \ ⋃_{h=1}^{t} Tor(G, h).

Clearly, {a} is then a t-independent set in G.

Assume now that our proposition holds for a positive integer m and suppose that

n > σ(G, t) · \binom{2m + t}{t}.

Since this value is greater than

σ(G, t) · \binom{2m − 2 + t}{t},

our inductive hypothesis implies that G has a t-independent set A of size m.

Define B = A ∪ (−A) and

⟨B, t⟩ = ⋃_{h=1}^{t} h · B.

First, note that ⟨B, t⟩ has size at most

∑_{h=1}^{t} \binom{2m + h − 1}{h} = \binom{2m + t}{t} − 1.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A02 17

For a fixed positive integer h and group element g, define

Root_{h}(g) = {x ∈ G|hx = g}.

We prove the following

Claim. If Root_{h}(g) ≠ ∅, then |Root_{h}(g)| = |Tor(G, h)|. Proof of Claim. Fix x ∈ Root_{h}(g). Our claim follows from the fact that y ∈ Root_{h}(g), if and only if, y − x ∈ Tor(G, h).

Now define

C = ⋃_{b∈⟨B,t⟩} ⋃_{h=1}^{t} Root_{h}(b).

An obvious upper bound for the size of C is

σ(G, t) · (\binom{2m + t}{t} − 1) .

Therefore, according to our inductive hypothesis, the set G\C is non-empty; fix a ∈ G\C.

Claim. A ∪ {a} is a t-independent set of size m + 1 in G. Proof. To see that A ∪ {a} is of size m + 1, note that

a ∈ G \ C ⊆ G \ ⟨B, t⟩ ⊆ G \ B ⊆ G \ A.

Now let A = {a_{1}, a_{2}, …, a_{m}} and assume that

λ_{1}a_{1} + λ_{2}a_{2} + ⋯ + λ_{m}a_{m} + λa = 0

for some integers λ_{1}, λ_{2}, …, λ_{m}, λ. Suppose, indirectly, that

1 ≤ |λ_{1}| + |λ_{2}| + ⋯ + |λ_{m}| + |λ| ≤ t.

Set

x = λ_{1}a_{1} + λ_{2}a_{2} + ⋯ + λ_{m}a_{m}.

Note that x ∈ ⟨B, t⟩ and therefore −x ∈ ⟨B, t⟩; we also have a ∈ Root_{λ}(−x).

Without loss of generality, we can assume that λ ≥ 0. If 1 ≤ λ ≤ t, then we have a ∈ Root_{λ}(−x) ⊆ C, a contradiction with the choice of a. Otherwise, λ = 0, from which x = 0; a contradiction, since A is t-independent. This completes the proof of our claim and therefore our Proposition. □

Now Theorem 7 follows from Propositions 16, by noting that

\binom{2m − 2 + t}{t} = ∏_{k=1}^{t} \frac{2m − 2 + k}{k}

= ∏_{k=1}^{t} \frac{mk − (k − 2)(m − 1)}{k}
≤ (2m − 1)m^{t−1}
< 2m^{t}.

5. Weakly t-independent sets in abelian groups

When discussing solutions of equations in a set, it is natural to consider the version when we restrict ourselves to distinct solutions; this is referred to as the weak property. A comparison between sum-free and weak sum-free, as well as Sidon and weak Sidon sets, and B_{h} sequences versus weak B_{h} sequences, can be found in Ruzsa’s papers [26] and [27]; there it was shown that their maximum sizes among the positive integers behave similarly. This certainly does not hold for t-independence in abelian groups, as we see in this section.

For a positive integer h, we use the notation

h ⋆ A = {a_{1} + a_{2} + ⋯ + a_{h}|a_{1}, a_{2}, …, a_{h} ∈ A are distinct}.

We introduce the following measure for the degree of weak independence of A ⊆ G.

Definition 17 Let t be a non-negative integer and A = {a_{1}, a_{2}, …, a_{m}}. We say that A is a weakly t-independent set in G, if whenever

λ_{1}a_{1} + λ_{2}a_{2} + ⋯ + λ_{m}a_{m} = 0

for some integers λ_{1}, λ_{2}, …, λ_{m} ∈ {−1, 0, 1} with

|λ_{1}| + |λ_{2}| + ⋯ + |λ_{m}| ≤ t,

we have λ_{1} = λ_{2} = ⋯ = λ_{m} = 0. We call the largest t for which A is weakly tindependent the weak independence number of A in G and denote it by wind(A); if A is weakly t-independent for every t, we set wind(A) = ∞.

Equivalently, A is a weakly t-independent set in G, if for all non-negative integers h and k with h + k ≤ t, the sum of h distinct elements of A can only equal the sum of k distinct elements of A in a trivial way, that is, h = k and the two sums contain the same terms in some order.

This time, we have the following three requirements:

0 ∉ h ⋆ A for 1 ≤ h ≤ t;  (15)

(h ⋆ A) ∩ (k ⋆ A) = ∅ for 1 ≤ h < k ≤ t − h;  (16)

and

|h ⋆ A| = \binom{m}{h} for 1 ≤ h ≤ ⌊\frac{t}{2}⌋.  (17)

The difference between independence and weak independence can be illustrated by the following examples in G = ℤ_{30}: we see that ind({1, 2, 4, 8, 16}) = 2 (as 1 + 1 = 2), and wind({1, 2, 4, 8, 16}) = 3 (we have 2 + 4 + 8 + 16 = 0); but ind({1, 2, 4, 8}) = 2 still, yet wind({1, 2, 4, 8}) = ∞.

For a non-negative integer t, we let w(G, t) denote the size of a maximum weakly t-independent set in G; we also set w(G, ∞) to be the largest size of a subset A of G for which wind(A) = ∞. It is easy to see that

w(G, 0) = n,
w(G, 1) = n − 1,

and

w(G, 2) = \frac{n + |Ord(2)| − 2}{2};

the last equation results from the fact that no element of G, other than those of order 2, can be in a weakly 2-independent set together with its negative. On the other end, if the invariant factor decomposition of G contains s terms, then w(G, ∞) ≥ s; in particular, if κ denotes the exponent of G, then

w(G, t) ≥ w(G, ∞) ≥ \frac{log n}{log κ}

holds for every t.

It is not hard to prove the following stronger result.

Theorem 18 For t ≥ 2 we have

(\frac{t!}{2^{t}} n)^{1/t} − \frac{t}{2} < w(G, t) < (⌊\frac{t}{2}⌋!n)^{1/⌊t/2⌋} + \frac{t}{2}.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A02 20

Proof. Let us first prove two claims.

Claim 1. Suppose that m is a positive integer for which

n > ∑_{h=1}^{t} \binom{2m − 2}{h} + 1.

Then G has a weakly t-independent set of size m. Proof of Claim 1. The proof will be similar (but simpler than) that of Proposition 16. We use induction on m. For m = 1 we have n ≥ 2, and clearly {a} is a weakly t-independent set in G whenever a ≠ 0.

Assume now that our proposition holds for a positive integer m and suppose that

n > ∑_{h=1}^{t} \binom{2m}{h} + 1.

Since this value is greater than

∑_{h=1}^{t} \binom{2m − 2}{h} + 1,

our inductive hypothesis implies that G has a weakly t-independent set A of size m.

Define B = A ∪ (−A) and

⟨B, t⟩^{∗} = ⋃_{h=1}^{t} h ⋆ B.

Then |⟨B, t⟩^{∗}| ≤ ∑_{h=1}^{t} \binom{2m}{h}. Therefore, we can choose an a ∈ G \ ⟨B, t⟩^{∗}. Then clearly a ∉ A, and, as in the proof of Proposition 16, we can show that A ∪ {a} is a weakly t-independent set of size m + 1 in G.

Claim 2. Suppose that A is a weakly t-independent set in G of size m. Then

n ≥ ∑_{h=1}^{⌊t/2⌋} \binom{m}{h} + 1

. Proof of Claim 2. Define

⟨A, ⌊t/2⌋⟩^{∗} = ⋃_{h=1}^{⌊t/2⌋} h ⋆ A.

By (15), 0 ∉ ⟨A, ⌊t/2⌋⟩^{∗}, so we have n − 1 ≥ |⟨A, ⌊t/2⌋⟩^{∗}|. Furthermore, by conditions (16) and (17), we see that ⟨A, ⌊t/2⌋⟩^{∗} has size exactly

∑_{h=1}^{⌊t/2⌋} \binom{m}{h},

proving our Claim.

To derive our upper and lower bounds for w(G, t), we use the (rather crude) estimates that for positive integers c and d we have

\frac{(d + 2 − c)^{c}}{c!} ≤ \binom{d + 1}{c} ≤ ∑_{h=0}^{c} \binom{d}{h} ≤ \binom{d + c}{c} ≤ \frac{(d + c)^{c}}{c!} .  (18)

Namely, using Claim 1 and (18) for d = 2m − 2 and c = t we see that if

n > \frac{(2m − 2 + t)^{t}}{t!} ,

then G has a weakly t-independent set of size m, implying the lower bound

w(G, t) ≥ \frac{(t!n)^{1/t} − t + 2}{2} − 1 = (\frac{t!}{2^{t}} n)^{1/t} − \frac{t}{2}.

The upper bound for w(G, t) follows similarly from Claim 2 and (18). □

Note that, for a fixed t, we have

lim inf w(G, t) = ∞

as |G| = n approaches ∞, in contrast to

lim inf s(G, t) = 0

for each t ≥ 2; in Section 1 we have seen that even

lim inf{s(G, t)|Ord(G, t) ≠ G} = O(1)

as t ≥ 4. Thus t-independence and weak t-independence behave quite differently in abelian groups.

Acknowledgments

The values of s(ℤ_{n}, 4) and s(ℤ_{n}, 5) for n ≤ 200, on which Conjecture 15 was based, were computed by Nick Laza; we thank him for his time and efforts.

References

[1] N. Alon and M. Dubiner. Zero-sum sets of prescribed size. In D. Miklós, V. T. Sós, and T. Szőnyi, editors, Combinatorics, Paul Erdős is eighty, Vol. 1., pages 33–50. Bolyai Society Mathematical Studies, Budapest, 1993.

[2] N. Alon and D. J. Kleitman. Sum-free subsets. In A. Baker, B. Bollobás, and A. Hajnal, editors, A Tribute to Paul Erdős, pages 13–26. Cambridge University Press, Cambridge, 1990.

[3] L. Babai and V. T. Sós. Sidon sets in groups and induced subgraphs of Cayley graphs. European J. Combin., 6/2:101–114, 1985.

[4] B. Bajnok. Constructions of spherical 3-designs. Graphs Combin., 14/2:97–107, 1998.

[5] A. Baltz, T. Schoen, and A. Srivastav. Probabilistic construction of small strongly sum-free sets via large Sidon sets. Colloq. Math., 86/2:171–176, 2000.

[6] T. Bier and A. Y. M. Chin. On (k, l)-sets in cyclic groups of odd prime order. Bull. Austral. Math. Soc., 63/1:115–121, 2001.

[7] Y. Bilu. Sum-free sets and related sets. Combinatorica, 18/4:449–459, 1998.

[8] R. C. Bose and S. Chowla. Theorems in the additive theory of numbers. Comment. Math. Helv., 37:141–147, 1962-63.

[9] N. J. Calkin and A. C. Taylor. Counting sets of integers, no k of which sum to another. J. Number Theory., 57/2:323–327, 1996.

[10] P. J. Cameron and P. Erdős. Notes on sum-free and related sets. Recent trends in combinatorics (Mátraháza, 1995). Combin. Probab. Comp., 8/1-295–107, 1999.

[11] Y. Caro. Zero-sum subsequences in abelian non-cyclic groups. Israel J. Math., 92/1-3:221–233, 1995.

[12] P. Erdős. Extremal problems in number theory. Proc. Sympos. Pure Math., 8:181-189, Amer. Math. Soc., Providence, R.I., 1965.

[13] P. Erdős and R. Freud. A Sidon prowlémakör. Mat. Lapok, 1991/2:1–44, 1991.

[14] P. Erdős and H. Heilbronn. On the addition of residue classes mod p. Acta Arith., 9:149–159, 1969.

[15] P. Erdős and P. Turán. On a problem of Sidon in additive number theory and some related problems. J. London Math. Soc., 16:212–215, 1941.

[16] W. D. Gao and Y. O. Hamidoune. Zero sums in abelian groups. Combin. Probab. Comp., 7/3:261–263, 1998.

[17] S. W. Graham. B_{h} sequences. In B. C. Berndt, H. G. Diamond, and A. J. Hildebrand, editors, Analytic number theory, Vol.1. (Allerton Park, IL, 1995), pages 431-449, Progr. Math. 138, Birkhäuser Boston, Boston, MA, 1996.

[18] R. K. Guy. Unsolved Problems in Number Theory. Second edition. Springer-Verlag New York, 1994.

[19] H. Halberstam and K. F. Roth. Sequences. Second edition. Springer-Verlag New York – Berlin, 1983.

[20] G. Harcos and I. Ruzsa. A problem on zero subsums in abelian groups. Period. Math. Hungar., 35/1-2:31–34, 1997.

[21] K. S. Kedlaya. Product-free subsets of groups. Amer. Math. Monthly, 105/10:900– 906, 1998.

[22] K. S. Kedlaya. Large product-free subsets of finite groups. J. Combin. Theory, Ser. A, 77/2:339–343, 1997.

[23] J. Komlós, M. Sulyok, and E. Szemerédi. Linear problems in combinatorial number theory. Acta Math. Acad. Sci. Hungar., 26:113–121, 1975.

[24] M. Kneser. Summenmengen in lokalkompakten abelschen Gruppen. Math. Zeitschr., 66:88–110, 1956.

[25] M. B. Nathanson. N-graphs, modular Sidon and sum-free sets, and partition identities. Ramanujan J., 4/1:59–67, 2000.

[26] I. Ruzsa. Solving linear equations in a set of integers I. Acta Arith., 65/3:259–282, 1993.

[27] I. Ruzsa. Solving linear equations in a set of integers II. Acta Arith., 72/4:385–397, 1995.

[28] T. Schoen. A note on the number of (k, l)-sum-free sets. Electron. J. Combin., 7/1: Research Paper 30, 8pp (electronic), 2000.

[29] S. Sidon. Ein Satz über trigonometrische Polynome und seine Anwendung in der Theorie der Fourier-Reihen. Math. Ann., 106:536–539, 1932.

[30] W. D. Wallis, A. P. Street, and J. S. Wallis. Combinatorics: Room Squares, Sum-free Sets, Hadamard Matrices, Lecture Notes in Mathematics, Vol. 292, Part 3. Springer-Verlag, Berlin-New York, 1972.