RESTRICTED SET ADDITION IN GROUPS, II.

A GENERALIZATION OF THE ERDŐS-HEILBRONN CONJECTURE

Vsevolod F. Lev

Institute of Mathematics Hebrew University Jerusalem 91904, Israel

                    seva@math.huji.ac.il

Submitted: June 18, 1998; Accepted: January 29, 2000

Abstract. In 1980, Erdős and Heilbronn posed the problem of estimating (from below) the number of sums a+b where a ∈ A and b ∈ B range over given sets A, B ⊆ ℤ/pℤ of residues modulo a prime p, so that a ≠ b. A solution was given in 1994 by Dias da Silva and Hamidoune. In 1995, Alon, Nathanson and Ruzsa developed a polynomial method that allows one to handle restrictions of the type f(a, b) ≠ 0, where f is a polynomial in two variables over ℤ/pℤ.

In this paper we consider restricting conditions of general type and investigate groups, distinct from ℤ/pℤ. In particular, for A, B ⊆ ℤ/pℤ and R ⊆ A × B of given cardinalities we give a sharp estimate for the number of distinct sums a + b with (a, b) ∉ R, and we obtain a partial generalization of this estimate for arbitrary Abelian groups.

1. Background: mapping restrictions

For two subsets A and B of the set of elements of a group G we write

A ˙+ B = {a + b: a ∈ A, b ∈ B, a ≠ b}.

(The group G = ℤ/pℤ of residues modulo a prime p was historically first to emerge in this context, hence the additive notation.) In other words, A ˙+ B is the set of all elements of G, representable as a sum of two distinct elements from A and B.

The Erdős-Heilbronn conjecture (see [5, p. 95]), resolved (affirmatively) in [4] (cf. also [1, 2]) is the following.

1991 Mathematics Subject Classification. Primary: 11B75; Secondary: 11P99, 05C25, 05C35. Partially supported by the Edmund Landau Center for Research in Mathematical Analysis and

Related Areas, sponsored by the Minerva Foundation (Germany).

Conjecture 1 (Erdős and Heilbronn). For any two sets A, B ⊆ ℤ/pℤ,

|A ˙+ B| ≥ min{|A| + |B| − 3, p}. (1)

The set A ˙+ B is obtained from A + B = {a + b: a ∈ A, b ∈ B} by excluding those sums with b = a. It seems plausible that (1) remains valid even if the sums to be excluded are chosen according to a more general pattern.

Specifically, given a mapping τ: A → B, we define A +^{τ} B to be the set of all the sums a + b such that b ≠ τ(a):

A +^{τ} B = {a + b: a ∈ A, b ∈ B, b ≠ τ(a)}.

In [3], we conjectured the following.

Conjecture 2 (Lev). Let A and B be subsets of ℤ/pℤ satisfying |A| ≤ |B|, and let τ: A → B be an arbitrary mapping from A to B. Then

|A +^{τ} B| ≥ min{|A| + |B| − 3, p}.

It turns out, however, that this latter conjecture was too optimistic. Fix two integers k, d ≥ 1 such that (2k + 1)(2d − 1) ≤ 2p + 1 and let

A = {−1, −2, −3, …, −kd} (mod p),
B = {0, d, 2d, …, (k + 1)d, (k + 1)d + 1, …, p − 1} (mod p).

Furthermore, define τ: A → B by

τ(−td + r) = td; 1 ≤ t ≤ k, 0 ≤ r < d.

This construction can be illustrated by the diagram below:

[figure: A:; B:; d; 2d; kd; (k+1)d; p; −1; −d; −d−1; −2d; −(k−1)d−1; −kd; ⋯; ⋯; ⋯; ⋯; ⋯]

We have then

|A| + |B| = kd + k + (p − (k + 1)d + 1) = p + k + 1 − d,

while

A +^{τ} B = {d, d + 1, d + 2, …, p − 1},

and therefore

|A +^{τ} B| = p − d = |A| + |B| − k − 1.

This shows that some additional conditions are necessary in order for |A +^{τ} B| ≥ |A| + |B| − 3 to hold.

The situation might be somewhat better if τ is injective. In this case, we were only able to construct A, B and τ so that |A| + |B| is as large as ⌊4p/3⌋, and yet |A +^{τ} B| = p − 2. Specifically, assume for definiteness p = 3m + 2 (the case p ≡ 1(mod 3) can be dealt with similarly) and let

A = {1, 3, 4, 6, 7, …, 3m, 3m + 1} (mod p),
B = {0, −1, −3, −4, −6, −7, …, −3m + 2, −3m} (mod p).

Furthermore, define τ(a_{i}) = b_{i}, where a_{i} and b_{i} are ith elements of A and B, respectively, in the above indicated order. Then

|A| + |B| = 2(2m + 1) = \frac{1}{3}(4p − 2) = ⌊4p/3⌋ ,

while A +^{τ} B consists of all residues modulo p, except 1 and 2, and therefore

|A +^{τ} B| = p − 2.

The following example (based on a suggestion of A. Dudek for p = 11) gives the largest known value of |A| + |B| subject to |A +^{τ} B| = p − 3. Let

A = B = {0, 1, 3, 4, 5, …, (p − 1)/2, (p + 1)/2},
τ(0) = 3, τ(1) = 1, τ(3) = 0,
τ(a) = (p + 9)/2 − a for a = 4, 5, …, (p − 1)/2, (p + 1)2.

The corresponding diagram:

[figure: A:; B:; 0; 1; 3; 4; 5; \frac{p−1}{2}; \frac{p+1}{2}; 0; 1; 3; 4; 5; \frac{p−1}{2}; \frac{p+1}{2}; ⋯; ⋯]

Here |A| + |B| = p + 1, and as indicated above, |A +^{τ} B| = p − 3 (notice that 2, 3 and (p + 9)/2 are not in A +^{τ} B).

Is it true that

|A +^{τ} B| ≥ \begin{cases}|A| + |B| − 3, & if |A| + |B| ≤ p, \\ p − 3, & if |A| + |B| = p + 1, \\ p − 2, & if |A| + |B| ≥ p + 2 \end{cases} (2)

for any injective τ? Though this may not be the case, there is little doubt that it is close to the truth. Finding the best possible estimate of this kind seems to require fresh ideas and is of certain interest.

2. Summary of results

Below, we discuss the results that will be proved in Section 3.

We first bring into consideration restricting conditions of a more general sort. Let A, B ⊆ G be subsets of a group G, and let R ⊆ A × B be any subset of the Cartesian

product A × B. We define A +^{R} B to be the set of all sums a + b, such that (a, b) ∉ R:

A +^{R} B = {a + b: a ∈ A, b ∈ B, (a, b) ∉ R}.

To simplify the notation, we write throughout the rest of the paper

m = |A|, n = |B|, r = |R|,

and we tacitly assume r > 0 (that is, R ≠ ∅). Plainly, when R is induced by a mapping τ: A → B, we have r = m.

Our main result for the group ℤ/pℤ is the following.

Theorem 1. Let A, B ⊆ ℤ/pℤ, and let R ⊆ A × B. Assume for definiteness m ≤ n. Then

|A +^{R} B| ≥ \begin{cases}m + n − 2\sqrt{r} − 1, & if m + n ≤ p + \sqrt{r} and \sqrt{r} ≤ m, \\ p − \frac{r}{m+n−p}, & if m + n ≥ p + \sqrt{r}, \\ n − \frac{r}{m}, & if \sqrt{r} ≥ m. \end{cases}

Observe, that m+n ≥ p+\sqrt{r} and \sqrt{r} ≥ m can occur simultaneously only when n = p and m = \sqrt{r}, in which case the two last estimates of Theorem 1 coincide.

Theorem 1 is extremely sharp and in fact, establishes the minimum possible value of

the cardinality of the restricted sum A +^{R} B. To see this, consider the following example.

Example 1. Let A = {0, …, m − 1}(mod p) and B = {0, …, n − 1}(mod p), where 1 ≤ m ≤ n ≤ p. Fix a positive integer k such that

\frac{m + n − 1 − p}{2} ≤ k ≤ \frac{m + n − 1}{2}

and define

R := {(a, b): a ∈ A, b ∈ B, a + b ∉ [k, m + n − 2 − k] (mod p)}.

(Notice, that R “eliminates” sums a + b with minimal number of representations. The

condition that k is positive ensures that R ≠ ∅.) We have then A +^{R} B ⊆ [k, m+n−2−k] (mod p), whence

|A +^{R} B| ≤ m + n − 2k − 1. (3)

Now, if k is chosen to satisfy m ≤ k ≤ (m + n − 1)/2, one can verify that

r = m(2k + 1 − m) > m^{2},

and by (3),

|A +^{R} B| ≤ n − \frac{r}{m}.

If m + n − p ≤ k ≤ m − 1, then

r = k(k + 1) < m^{2}, m + n ≤ p + k < p + \sqrt{r};

by (3),

|A +^{R} B| < m + n − 2\sqrt{r}.

Finally, if (m + n − p − 1)/2 ≤ k ≤ m + n − p − 1, then

r = (p + 2k + 1 − m − n)(m + n − p) < (m + n − p)^{2};

it follows that m + n > p + \sqrt{r} and

|A +^{R} B| ≤ p − \frac{r}{m + n − p}.

We now turn to generalizations onto groups, distinct from ℤ/pℤ. The second estimate of Theorem 1 has an analog even in the non-commutative case.

Theorem 2. Let A, B ⊆ G be subsets of a finite group G of order q = |G|, and let R ⊆ A × B. Suppose that m + n ≥ q + 1. Then

|A +^{R} B| ≥ q − \frac{r}{m + n − q} .

Corollary 1. Let G, A, B and R be as in Theorem 2. Assume that m + n ≥ (1 + ε)q and r ≤ C min{m, n} for some ε, C > 0.

|A +^{R} B| ≥ q − Cε^{−1}.

Proof.

\frac{r}{m + n − q} ≤ \frac{C}{2} \frac{m + n}{(m + n) − q} ≤ \frac{C}{2} \frac{1}{1 − (1 + ε)^{−1}} = \frac{C}{2} (1 + \frac{1}{ε}) < Cε^{−1}.

A refinement is possible when R is induced by an injective mapping and the sum m + n only slightly exceeds q.

Theorem 3. Let A, B ⊆ G be subsets of a finite group G of order q = |G|, and let τ: A → B be an injective mapping from A to B. Suppose that m + n ≥ q + 1. Then

|A +^{τ} B| > q − \sqrt{q} − \frac{1}{2}.

In a certain (rather narrow) range of m, n and in the particular case of R induced by an injective mapping, Theorem 3 improves Theorem 1.

To deal with the generalization of the most important and most difficult case of Theorem 1 — that of small m + n — we make a simplifying assumption that R satisfies the following conditions:

(a) to any fixed a_{0} ∈ A there corresponds at most one b ∈ B such that (a_{0}, b) ∈ R;

(b) to any fixed b_{0} ∈ B there corresponds at most one a ∈ A such that (a, b_{0}) ∈ R. We note that these conditions automatically hold when R is induced by an injective mapping; in general, they are not vital, but make possible certain simplifications. Furthermore, for real L > 0 we consider an additional condition:

(c) for any c ∈ G there are at most L pairs (a, b) ∈ R such that a + b = c.

The relevance of this condition for the estimates of |A +^{R} B| is hinted to by [6, Conjecture 2] and [6, Theorem 3]: when R is induced by the equality relation, L can be chosen to be the “doubling constant” of [6].

Our next result is parallel to [6, Theorem 3]. The difference is that in [6] we were only concerned with the “classical” restriction b ≠ a and considered only the case B = A; on the other hand, the latter allowed us to cover non-commutative groups.

Theorem 4. Let G be an Abelian group, let A, B ⊆ G be subsets of G, and let R satisfy

conditions (a)–(c). Suppose that A +^{R} B ≠ A + B. Then

|A +^{R} B| > (1 − δ)(m + n) − (L + 2), (4)

where

δ = \frac{mn}{(m + n)^{2}} ≤ \frac{1}{4}.

The condition A +^{R} B ≠ A + B may look odd at first sight and is worth explanation. The point is that there is such a powerful tool as Kneser’s theorem to estimate the

number of elements of the non-restricted sum A + B from below. If A +^{R} B = A + B, this theorem automatically yields lower-bound estimates for the number of elements of the

restricted sum A +^{R} B; Theorem 4 deals with the complementary case A +^{R} B ≠ A + B.

To be more specific, if (4) fails, while A +^{R} B = A + B, then it follows immediately from Kneser’s theorem that A and B posses a very rigid structure:

– either there exist elements a ∈ A, b ∈ B and a subgroup H ⊆ G such that A ⊆ a + H, B ⊆ b + H, m + n ≥ 4(|H| + L + 2)/3, and

A +^{R} B = A + B = a + b + H;

– or there exist elements a_{1}, a_{2} ∈ A, b ∈ B and a subgroup H ⊆ G such that A ⊆ (a_{1} + H) ∪ (a_{2} + H), B ⊆ b + H, m + n ≥ 8(|H| + L + 2)/3, and

A +^{R} B = A + B = (a_{1} + b + H) ∪ (a_{2} + b + H),

– or there exist elements a ∈ A, b_{1}, b_{2} ∈ B and a subgroup H ⊆ G such that A ⊆ a + H, B ⊆ (b_{1} + H) ∪ (b_{2} + H), m + n ≥ 8(|H| + L + 2)/3, and

A +^{R} B = A + B = (a + b_{1} + H) ∪ (a + b_{2} + H).

The coefficient 1 − δ in Theorem 4 can be slightly improved using the methods of [6]; in particular, for B = A it can be increased to (\sqrt{5} + 1)/4 ≈ 0.80.

The proofs of Theorems 1–4 are mostly combinatorial, with a somewhat surprising interference of graph theory in the proof of Theorem 3 — see also Section 4, the Conclusion.

3. Proofs

Proof of Theorem 1. For i = 1, 2, … we denote by N_{i} the number of residues c ∈ A + B with at least i representations of the form c = a+b (a ∈ A, b ∈ B), and by N′_{i} the number

of residues c ∈ (A + B) \ (A +^{R} B) with at least i representations of this form. Obviously,

N_{i} − N′_{i} counts the number of elements of A +^{R} B with at least i representations, whence

N_{i} − N′_{i} ≤ |A +^{R} B| and

t|A +^{R} B| ≥ (N_{1} − N′_{1}) + ⋯ + (N_{t} − N′_{t}) (5)

for any integer t ≥ 1.

Now, by Pollard’s theorem (see [7]) we have

N_{1} + ⋯ + N_{t} ≥ t min{p, m + n − t},

provided t ≤ m, and at the same time, clearly

N′_{1} + ⋯ + N′_{t} ≤ N′_{1} + ⋯ + N′_{t} + ⋯ = ∑_{c∈(A+B)\(A +^{R} B)} ν(c) ≤ r,

where ν(c) is the number of representations of c. Comparing to (5) we conclude that

t|A +^{R} B| ≥ t min{p, m + n − t} − r,
|A +^{R} B| ≥ min{p − r/t, m + n − (t + r/t)},

and it remains to optimize in t by choosing

t = \begin{cases}⌈\sqrt{r} ⌉, & if m + n ≤ p + \sqrt{r} and \sqrt{r} ≤ m, \\ m + n − p, & if m + n ≥ p + \sqrt{r}, \\ m, & if \sqrt{r} ≥ m. \end{cases}

Proof of Theorem 2. Let S be the complement of A +^{R} B in G, so that |S| = q − |A +^{R} B|. By the Dirichlet boxing principle, to any s ∈ S there correspond at least m + n − q pairs (a, b) (with a ∈ A, b ∈ B) such that a + b = s, and for any such pair we have (a, b) ∈ R. Totally, we have at least |S|(m + n − q) pairs (a, b) ∈ R. On the other hand, the number of these pairs is r, whence |S| ≤ r/(m + n − q), and the result follows.

Proof of Theorem 3. We define S as above, and we want to prove that |S| < \sqrt{q} + 1/2.

It is convenient to use graph-theoretic terminology. Consider the |S|-regular bipartite graph Γ on two disjoint copies of G, obtained by joining each vertex x ∈ G of the first copy to the |S| vertices −x + s; s ∈ S of the second copy. Formally, we write

Γ = (X ∪ Y, E); E = {(x, y): x ∈ X, y ∈ Y, x + y ∈ S},

where X and Y are thought of as two disjoint copies of G. Furthermore, consider the subgraph Γ_{0} ⊆ Γ, induced by all elements of A in the first copy and all elements of B in the second copy:

Γ_{0} = ⟨(X ∩ A) ∪ (Y ∩ B)⟩.

We claim that Γ_{0} contains no paths of length two. Indeed, a path x_{1}, y, x_{2} with x_{1}, x_{2} ∈ X ∩ A and y ∈ Y ∩ B would mean x_{1} + y ∈ S and x_{2} + y ∈ S, which is impossible: either τ(x_{1}) ≠ y (in which case x_{1} + y ∉ S), or τ(x_{2}) ≠ y (in which case x_{2} + y ∉ S). Similarly, a path of the type y_{1}, x, y_{2} cannot occur in Γ_{0} as τ(x) = y_{1} and τ(x) = y_{2} cannot happen simultaneously.

Our next observation is that Γ contains no rectangles. Indeed, any single rectangle x_{1}, y_{1}, x_{2}, y_{2} can be translated to produce q rectangles

x_{1} + u, −u + y_{1}, x_{2} + u, −u + y_{2}; u ∈ G,

each containing at most two vertices of Γ_{0}: a subgraph induced by any three vertices of a rectangle necessarily contains a path of length two. Summation over all u ∈ G gives 2(|A| + |B|) ≤ 2q, contradicting the assumptions.

We now essentially repeat an Erdős’ argument to show that if Γ contains no rectangles, then |S| (the degree of Γ) is small. We first count all paths of the form x_{1}, y, x_{2} (x_{1}, x_{2} ∈ X, y ∈ Y) in Γ. Obviously, there are totally q\binom{|S|}{2} such paths, as any vertex y ∈ Y participates in \binom{|S|}{2} paths. On the other hand, there are only \binom{q}{2} pairs (x_{1}, x_{2}); x_{i} ∈ X with x_{1} ≠ x_{2}. Since no two distinct paths can share a common pair (this would yield a rectangle), we have

q\binom{|S|}{2} ≤ \binom{q}{2},

|S|^{2} − |S| + 1 ≤ q (6)

whence |S| < \sqrt{q} + 1/2, as required.

There is another way to complete the proof by making a funny observation that S is a Sidon set in G: an equality s_{1} − s_{2} = s′_{1} − s′_{2} with s_{1} ≠ s_{2}, s_{1} ≠ s′_{1} creates a rectangle s_{1}, 0, s_{2}, −s_{2} + s′_{2} = −s_{1} + s′_{1}. It is easy to verify, however, that the cardinality of any Sidon set S ⊆ G satisfies (6).

Proof of Theorem 4. We break the proof in three steps.

i) Since A +^{R} B ≠ A + B, there exist a_{0} ∈ A and b_{0} ∈ B such that c = a_{0} + b_{0} ∉ A +^{R} B. Then

|(A − b_{0}) ∩ (a_{0} − B)| ≤ L,

as any equality a − b_{0} = a_{0} − b gives rise to the representation c = a + b with (a, b) ∈ R

(in view of c ∉ A +^{R} B), and there are at most L such representations. Letting A − B = {a − b: a ∈ A, b ∈ B} we obtain

|A − B| ≥ |(A − b_{0}) ∪ (a_{0} − B)| ≥ m + n − L. (7)

ii) Fix any c = a_{0} − b_{0} ∈ A − B (where a_{0} ∈ A, b_{0} ∈ B) and let

A_{0} = {a ∈ A: (a, b_{0}) ∉ R}, B_{0} = {b ∈ B: (a_{0}, b) ∉ R},

so that |A_{0}| ≥ m − 1 and |B_{0}| ≥ n − 1 by the conditions (a) and (b). Write ν(c) for the number of representations c = a − b (a ∈ A, b ∈ B). Then

ν(c) ≥ |(a_{0} + B_{0}) ∩ (A_{0} + b_{0})| ≥ |A_{0}| + |B_{0}| − |A +^{R} B|

≥ m + n − 2 − |A +^{R} B|, (8)

as (a_{0} + B_{0}) ∪ (A_{0} + b_{0}) ⊆ A +^{R} B.

iii) By (7) and (8),

mn = ∑_{c∈A−B} ν(c) ≥ (m + n − L)(m + n − 2 − |A +^{R} B|),

|A +^{R} B| ≥ m + n − 2 − \frac{mn}{m + n − L}

> m + n − \frac{mn}{m + n} − (L + 2),

the latter inequality being equivalent to mn < (m + n)(m + n − L), which follows from L < (1 − δ)(m + n) — otherwise, the assertion of the theorem is trivial.

The result follows.

4. Conclusion

We re-state here explicitly several problems that remain open.

Does (2) hold for any two sets A, B ⊆ ℤ/pℤ and any injective mapping τ: A → B? In particular, is it true that |A +^{τ} B| ≥ p − 2, provided |A| + |B| ≥ p + 2? Do similar estimates hold when A and B are subsets of an arbitrary finite group? If some of the answers are negative, what are the best possible estimates of this sort?

A slight modification of the approach used in the proof of Theorem 3 shows that for |A| + |B| ≥ p + 2, this problem can be reformulated in the graph-theoretic language as follows.

Let c ≠ 0, 1 be any fixed residue modulo p. Consider a cubic bipartite graph Γ(c) on two copies of ℤ/pℤ such that any vertex x of the first copy is adjacent to the vertices x, x + 1 and x + c of the second copy. Is it true that any induced subgraph of order p + 2 of any such Γ(c) contains a path of length two?

The answer is certainly positive if c = −1, 2 or (p + 1)/2 (in which cases Γ(c) contains a rectangle). In general, the situation is not clear, however.

The major open problem for generic restriction is that of improving the coefficient 1 − δ in Theorem 4. Quite likely, this coefficient can be replaced by 1 or at least by 1 − ε for any positive ε, provided r is sufficiently (in terms of ε) small compared to m + n.

Acknowledgment

The (core of the) present form of Theorem 1 and an idea incorporated in the proof of Theorem 3 are due to Noga Alon, whom we are greatly indebted for this contribution.

References

[1] N. Alon, M.B. Nathanson and I.Z. Ruzsa, Adding distinct congruence classes modulo a prime, American Math. Monthly, 102 (1995), 250–255.

[2] N. Alon, M.B. Nathanson and I.Z. Ruzsa, The Polynomial Method and Restricted Sums of Congruence Classes, J. Number Theory, 56 (1996), 404–417.

[3] Y. Bilu, V.F. Lev and I.Z. Ruzsa, Rectification principles in additive number theory, Disc. and Comput. Geometry, 19 (1998), 343–353.

[4] J.A. Dias da Silva and Y.O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc. 26 (1994), 140–146.

[5] P. Erdős and R.L. Graham, Old and new problems and results in combinatorial number theory, L’Enseignement Mathématique, Geneva, 1980.

[6] V.F. Lev, Restricted set addition in groups. I. The classical setting, Journal of the London Mathematical Society, to appear.

[7] J.M. Pollard, A generalization of the theorem of Cauchy and Davenport, J. London Math. Soc. 2 (8) (1974), 460–462.