A PROBLEM ON ZERO SUBSUMS IN ABELIAN GROUPS

Gergely Harcos and Imre Z. Ruzsa*

Abstract. Let a_{1}, a_{2}, … be elements of an abelian group such that a_{m} has order larger than m^{m}. Then the multiset of the a_{m}’s can be partitioned into two parts which are free of zero subsums. The result was motivated by a question of Paul Erdős.

1. Introduction

The starting point of the paper was the following conjecture of Pál Erdős, related to us by Prof. Róbert Freud.

Conjecture. If the prime p is large enough in terms of k then any multiset of k nonzero residue classes modulo p can be partitioned into two parts such that in none of the parts does a zero subsum occur.

The authors know about two different proofs of the conjecture, the first by Lajos Pósa and another (later but different) by Ambrus Pál (cf. Remark 1). However, neither proof has been published, and neither provides an effective admissible bound for p. Also, the conjecture admits a straightforward generalization to abelian groups in which one requires that the order of the elements involved be sufficiently large in terms of k. A justification for this conjecture might be that any torsionfree abelian group can be ordered, whence its nonzero elements split into positive and negative parts. We obtain a common extension of these conjectures as follows.

Theorem. Let a_{m} (m = 1, 2, …) be elements of an abelian group A with a_{m} of order larger than m^{m}. Then the multiset of the a_{m}’s can be partitioned into two zero subsum free parts.

Clearly the result implies a similar statement for any finite sequence of the a_{m}’s (by taking A ⊕ ℤ in place of A), therefore we see now that p > k^{k} is admissible in Erdős’ question. In fact, a result of Bilu, Lev and Ruzsa [1] even shows that if p > (2s)^{k} then any k-element set of mod p residues has a Freiman isomorphism into ℤ, that is, a map which induces a bijection between s-term sums from the residues in question and their images. We mention here for sake of completeness that the exponential bound on p is essential, because any 2 < p ≤ 2^{(k−1)/2} would fail in the original conjecture (see Remark 2).

Acknowledgements. The first author is indebted to Róbert Freud for calling his attention to the Erdős problem and to L. van den Dries, Zoltán Füredi and W. Henson for helpful discussion.

Typeset by AMS-TEX

* Supported by Hungarian National Foundation for Scientific Research, Grant No. 17433

2. Proof and remarks

In the following we say that an element a in an abelian group has order larger than m if la ≠ 0 for any integer 1 ≤ l ≤ m.

Proof of the Theorem. A well-known lemma of König on infinite trees shows that it suffices to find the required partition for each multiset {a_{1}, a_{2}, …, a_{k}} (k = 1, 2, …). This we do by induction on k. Suppose that we have found a good partition for k − 1 in place of k. This determines a partition I_{1} ∪ I_{2} of the set I = {1, 2, …, k − 1} of subscripts, and we want to find a similar decomposition of the set L = {1, 2, … k}.

As a_{k} has order larger than k^{k}, there exists a character φ : A → ℝ/ℤ such that φ(a_{k}) also has order larger than k^{k}. For sake of simplicity we represent the circle group ℝ/ℤ by the real interval [−1/2, 1/2). We shall apply Dirichlet’s theorem on simultaneous diophantine approximation to the k numbers φ(a_{m}) (m ∈ L). This theorem yields, for any positive integer Q, an integer 1 ≤ q ≤ Q^{k} such that

|qφ(a_{m})| < \frac{1}{Q} (m ∈ L).

We take Q to be k; then all the qφ(a_{m}) lie in (−1/k, 1/k) and qφ(a_{k}) is not zero by assumption on φ. In particular, the set

J = {m ∈ L : qφ(a_{m}) = 0}

is contained in I, and the partition I_{1} ∪ I_{2} of I determines a partition J_{1} ∪ J_{2} of J by J_{1} = J ∩ I_{1} and J_{2} = J ∩ I_{2}. The complement of J in L is clearly a disjoint union K_{1} ∪ K_{2} where

K_{1} = {m ∈ L : qφ(a_{m}) > 0},
K_{2} = {m ∈ L : qφ(a_{m}) < 0}.

Therefore we get a partition L_{1} ∪ L_{2} of L by putting

L_{1} = J_{1} ∪ K_{1}, L_{2} = J_{2} ∪ K_{2}.

We claim that the corresponding partition of the multiset {a_{1}, a_{2}, …, a_{k}} consists of zero subsum free parts. Let M be any subset of L_{1} or L_{2}. We consider the case M ⊆ L_{1}, the other case being analogous. Assume

(1)  ∑_{m∈M} a_{m} = 0.

Then also

∑_{m∈M} qφ(a_{m}) = 0,

whence

∑_{m∈M\J} qφ(a_{m}) = 0

by definition of J. As

M \ J ⊆ L_{1} \ J = K_{1},

all the terms involved in the last sum are strictly between 0 and 1/k by definition of K_{1} and q. Since the number of terms is at most k, M \ J must be empty. In other words, M is contained in J which gives

M ⊆ J_{1} ⊆ I_{1}.

Now (1) combined with the property of I_{1} shows that in fact M = ∅. This proves our claim, hence the theorem. □

Remark 1. We can read off from the theorem or the proof itself that any k elements of orders larger than k^{k} in an abelian group can be divided into two zero subsum free parts. The existence of a constant depending on k like k^{k} in this statement can also be derived from Gödel’s Compactness Theorem as follows. The Compactness Theorem reduces the existence of the constant depending on k to the statement that in an abelian group A any finite multiset of non-torsion elements can be partitioned into two zero subsum free parts. After passing from A to the quotient A/T where T is the subgroup of torsion elements in A it becomes sufficient to show that in a torsionfree abelian group A any finite multiset of nonzero elements can be partitioned into two zero subsum free parts. That claim, however, is a consequence of the fact quoted above that A can be ordered. This is essentially the idea behind Pál’s solution of the original Erdős problem.

Remark 2. Whenever an odd prime p is at most 2^{(k−1)/2}, it fails to have the property in the Erdős Conjecture. Indeed, with t = [k/2] we have 2 < p ≤ 2^{t}. Consider the multiset of residues mod p consisting of two 1’s, one −1, one 2^{s} for each s = 1, 2, … t−1 and one −2^{s} for each s = 1, 2, … t−2. Altogether we have 3+(t−1)+ (t − 2) = 2t ≤ k nonzero residues modulo p. Suppose that a partition without zero subsums exists. If −1 is in the first class, both 1’s are forced into the second, this implies that the −2 is in the first, 2 in the second and so on. Thus the second class contains 1, 2, 4, ..., 2^{t−1}, whose sums represent every integer up to 2^{t} − 1, including p.

References

[1] Yu. Bilu, V. Lev and I. Z. Ruzsa, Rectification principles in additive number theory, J. Discrete Geo., to appear.

Department of Mathematics, University of Illinois at Urbana–Champaign, 1409 West Green Street, Urbana, IL 61801, USA

E-mail address: harcos@math.uiuc.edu

Mathematical Institute of the Hungarian Academy of Sciences, POB 127, H-1364 Budapest, Hungary

E-mail address: ruzsa@math-inst.hu