MULTIPLE SET ADDITION IN ℤ_{p}

Tomasz Schoen^{1}

Department of Discrete Mathematics, Adam Mickiewicz University, Poznań, Poland

                            schoen@amu.edu.pl

Received: 2/22/03, Revised: 10/6/03, Accepted: 11/1/03, Published: 11/5/03

Abstract

It is shown that there exists an absolute constant H such that for every h > H, every prime p, and every set A ⊆ ℤ_{p} such that 10 ≤ |A| ≤ p(ln h)^{1/2}/(9h^{9/4}) and |hA| ≤ h^{3/2}|A|/(8(ln h)^{1/2}), the set A is contained in an arithmetic progression modulo p of cardinality max_{1≤j≤h−1} \frac{|hA|−P_{j}(|A|)}{h−j} + 1, where P_{j}(n) = \frac{(j+1)j}{2} n − j^{2} + 1. This result can be viewed as a generalization of Freiman’s “2.4-theorem”.

1. Introduction

For a non-empty subset A of an additively written group and an integer h ≥ 2 the h-sumset of A is defined as

hA = {a_{1} + ⋯ + a_{h} : a_{1}, …, a_{h} ∈ A};

and by a sumset we mean a 2-sumset of A. The following well-known “2.4-theorem” of Freiman [2] describes the structure of sets A ⊆ ℤ_{p} with small sumsets.

Theorem 1 (Freiman). Let A, |A| ≤ p/35, be a subset of ℤ_{p} for some prime p. If

|2A| ≤ 2.4|A| − 3,

then A is contained in an arithmetic progression of ℤ_{p} with |2A| − |A| + 1 terms.

Freiman’s proof goes roughly as follows. Since A has a small sumset, the characteristic function of A has a large non-zero Fourier coefficient. Hence A is dense in some arithmetic progression P ⊆ ℤ_{p} of length (p−1)/2. The set A′ = A∩P is isomorphic (in the sense of Freiman) to a subset of integers, hence one can apply to A′ Freiman’s additive theorem for integers, and infer that A′ is contained in an arithmetic progression of cardinality |2A′| − |A′| + 1. As a last step one shows that A′ = A, otherwise we would have |2A| > 2.4|A| − 3.

1Research partially supported by KBN Grant 2 P03A 007 24

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

In this note we generalize Freiman’s theorem to h summands, provided h is large. Our main result is as follows.

Theorem 2. There is an absolute constant H such that for every h > H, every prime p, and every A ⊆ ℤ_{p} such that 10 ≤ |A| ≤ \frac{p(ln h)^{1/2}}{9h^{9/4}} and

|hA| ≤ \frac{h^{3/2}}{8(ln h)^{1/2}} |A|,

the set A is contained in an arithmetic progression of cardinality max_{1≤j≤h−1} \frac{|hA|−P_{j}(|A|)}{h−j} + 1, where P_{j}(n) = \frac{(j+1)j}{2} n − j^{2} + 1.

Our approach follows the main idea of Freiman’s proof. First we observe that the absolute value of some Fourier coefficient of the characteristic function of A is very close to |A|. We use this fact to show the existence of a large subset A′ of A contained in an arithmetic progression of cardinality roughly p(ln h/h)^{1/2}. Then we apply a result of Lev (Theorem 3 below) to A′ and some h_{0} > (h/ ln h)^{1/2} to prove that A′ is, in fact, contained in a much shorter arithmetic progression. Finally we employ a well-known theorem of Cauchy-Davenport to infer that A′ = A.

In order for our method to work we have to impose some restrictions on the sizes of A and hA. Thus, we assume that h > H, where the value of an absolute constant H can be explicitly computed. In our result Freiman’s constant “2.4” is replaced by “h^{3/2}/4(ln h)^{1/2}”, although one can expect that, as in Theorem 3, the assertion holds for each A with |hA| ≤ \frac{(h+1)h}{2}|A| − h^{2}.

2. Auxiliary results

In this section we recall some theorems and definitions used in the proof of our main result. First we state a consequence of [3, Corollary 1] . Here and below L(A) denotes the cardinality of the shortest arithmetic progression containing A.

Theorem 3 (Lev [3]). Let h ≥ 2 and A be a finite subset of ℤ, |A| ≥ 2 such that |hA| ≤ \frac{(h+1)h}{2}|A| − h^{2}. Then

L(A) ≤ max_{1≤j≤h−1} \frac{|hA| − P_{j}(|A|)}{h − j} + 1,

where P_{j}(n) = \frac{(j+1)j}{2} n − j^{2} + 1.

Remark 1. The estimate of Theorem 3 is tight, as shows the following example given in [3]. Let ℓ ≥ n − 1, A = \{0, …, n − 2\} ∪ \{ℓ\} and put k = ⌈\frac{ℓ−1}{n−2}⌉ − 1. If h > \frac{ℓ−1}{n−2} then it is easily seen that |hA| = P_{k}(n) + (h − k)l < P_{h}(n) and

max_{1≤j≤h−1} \frac{|hA| − P_{j}(n)}{h − j} + 1 = ℓ + 1 = L(A),

maximum is attained for j = k.

Remark 2. Note that under the assumptions of Theorem 3 we have

L(A) ≤ \frac{2|hA|}{h} + 1.

Indeed, suppose that the maximum is attained for j_{0}. If j_{0} ≤ h/2 then the inequality follows immediately. Assume that j_{0} > h/2 and

\frac{|hA| − P_{j_{0}}(|A|)}{h − j_{0}} > \frac{2|hA|}{h}.

Then we have

|hA| > \frac{h}{2j_{0} − h}P_{j_{0}}(|A|) ≥ min_{h/2<j≤h} \frac{h}{2j − h}P_{j}(|A|).

Since \frac{h}{2j−h}P_{j}(n) is a strictly decreasing function of j it follows that

|hA| > P_{h}(|A|) > \frac{(h + 1)h}{2}|A| − h^{2},

contradicting the assumptions of Theorem 3.

Theorem 4 (Cauchy-Davenport). Let p be a prime number and let A be a nonempty subset of ℤ_{p}. Then, for every integer h ≥ 2,

|hA| ≥ min(p, h|A| − h + 1).

We will also need the following straightforward consequence of Theorem 4.

Corollary 1. Let p be a prime number and let A be a nonempty subset of ℤ_{p} such that |hA| < p. Then, for every integers h ≥ h_{1} ≥ 2,

|h_{1}A| < ⌊h/h_{1}⌋^{−1} |hA| + 1.

Proof. By Cauchy-Davenport theorem, we have

|hA| ≥ | ⌊h/h_{1}⌋ (h_{1}A)| ≥ ⌊h/h_{1}⌋|h_{1}A| − ⌊h/h_{1}⌋ + 1. □

Let G and H be abelian groups and let A ⊆ G and B ⊆ H. We say that a mapping ϕ : A → B is a Freiman’s isomorphism of order h ( briefly, F_{h}-isomorphism), if for every a_{1}, …, a_{h}, a′_{1}, …, a′_{h} ∈ A the equation

a_{1} + ⋯ + a_{h} = a′_{1} + ⋯ + a′_{h}

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A17 4

holds if and only if

ϕ(a_{1}) + ⋯ + ϕ(a_{h}) = ϕ(a′_{1}) + ⋯ + ϕ(a′_{h})

holds. In particular F_{h}-isomorphisms preserve the size of h-sumsets.

3. Proof of the main theorem For a set S ⊆ ℤ_{p} let {Ŝ(r)}_{r∈ℤ_{p}} denote the Fourier coefficients of the indicator function of S ( Ŝ(r) = ∑_{s∈S} e^{2πirs/p}). It is easy to see that |Ŝ(0)| = |S|. We recall also Parseval formula

∑_{r=0}^{p−1} |Ŝ(r)|^{2} = |S|p.

By the definition all sums a_{1} + ⋯ + a_{h}, a_{1}, …, a_{h} ∈ A belong to the set hA, hence

∑_{r=0}^{p−1} Â(r)^{h} ˆ (hA)(−r) = |A|^{h}p

and

∑_{r=1}^{p−1} Â(r)^{h} ˆ (hA)(−r) = |A|^{h}p − |A|^{h}|hA| ≥ |A|^{h}p/2.

Put M =max_{r≠0} |Â(r)|. By Cauchy-Schwarz inequality and Parseval formula we have

|A|^{h}p/2 ≤ ∑_{r=1}^{p−1} |Â(r)|^{h}| ˆ (hA)(−r)| ≤ M^{h−1} ∑_{r=1}^{p−1} |Â(r)|| ˆ (hA)(−r)|
≤ M^{h−1}( ∑_{r=1}^{p−1} |Â(r)|^{2})^{1/2}( ∑_{r=1}^{p−1} | ˆ (hA)(−r)|^{2})^{1/2}
< M^{h−1}|A|^{1/2}|hA|^{1/2}p.

Thus,

M > (\frac{|A|}{4|hA|})^{\frac{1}{2(h−1)}} |A| ≥ (h^{−3/2})^{\frac{1}{2(h−1)}} |A|
= exp ( − \frac{3}{4} \frac{ln h}{h − 1})|A| > (1 − \frac{3}{4} \frac{ln h}{h − 1})|A|
> (1 − \frac{ln h}{h})|A|.  (1)

Let r_{0} ∈ ℤ_{p} \ {0} be an element with |Â(r_{0})| = M. Put γ = arg Â(r_{0}), α = arccos (1 − \frac{2 ln h}{h}), so that α ≤ π(\frac{ln h}{2h})^{1/2}. Define

B = \{r_{0}a: a ∈ A and d(γ − 2π \frac{(r_{0}a)_{p}}{p} ) ≤ α\},

where (r_{0}a)_{p} stands for the least non-negative integer congruent to r_{0}a modulo p and d(x) denotes the distance of x from the nearest number of the form 2πk, k ∈ ℤ. It follows that

|Â(r_{0})| ≤ |B| + (cos α)(|A| − |B|),

and by (1)

|B| ≥ \frac{1 − \frac{ln h}{h} − cos α}{1 − cos α}|A| = |A|/2.  (2)

Observe that B is F_{h_{0}}-isomorphic to a subset of integers, where h_{0} = ⌊2π/α⌋ . Then h_{0} ≥ 2(\frac{h}{ln h})^{1/2} and by Corollary 1, (1), and (2), we get

|h_{0}B| ≤ \frac{|hB|}{⌊h/h_{0}⌋} + 1 ≤ \frac{2h_{0}|hA|}{h} + 1 ≤ \frac{h_{0}h^{1/2}|A|}{4(ln h)^{1/2}} + 1
≤ \frac{h_{0}h^{1/2}|B|}{2(ln h)^{1/2}} + 1 ≤ \frac{h_{0}^{2}}{4} |B| + 1
< \frac{(h_{0} + 1)h_{0}|B|}{2} − h_{0}^{2} + 1.

Thus, one can apply Theorem 3 to the set B, so that B is contained in an arithmetic progression in ℤ_{p} of size

max_{1≤j≤h_{0}−1} \frac{|h_{0}B| − P_{j}(|B|)}{h_{0} − j} + 1 ≤ \frac{2|h_{0}B|}{h_{0}} + 1 ≤ \frac{2|hB|}{h_{0} ⌊h/h_{0}⌋} + 2
≤ \frac{4|hA|}{h} + 2 ≤ \frac{h^{1/2}|A|}{2(ln h)^{1/2}} + 2
≤ \frac{p}{2h^{7/4}} .  (3)

Let A_{1} be any subset of A of the maximum cardinality, contained in an arithmetic progression of cardinality ⌊p/h⌋. From (2) and (3) it follows that |A_{1}| ≥ |A|/2. An argument analogous to that used in (3) shows that A_{1} is contained in an arithmetic progression of size at most p/(2h^{7/4}). Without loss of generality we may assume that A_{1} is a subset of the arithmetic progression with the common difference 1 centered at 0 that means ∥a∥ ≤ p/(4h^{7/4}) for every a ∈ A_{1}, where ∥x∥ = min ((x)_{p}, (p−x)_{p}). If a_{0} ∈ A\A_{1}, then

∥ka_{0}∥ ≤ \frac{p}{2h},

for some k ∈ ℕ. Let k be the smallest number with this property. Observe that if k ≤ h^{3/4}, then for every a ∈ A_{1}

∥ka∥ ≤ k∥a∥ ≤ h^{3/4} \frac{p}{4h^{7/4}} < \frac{p}{2h},

so the set A_{1} ∪ {a_{0}} is contained in an arithmetic progression of size at most p/h and the common difference k^{−1} (the multiplicative inverse of k in ℤ_{p}), contradicting the maximality of A_{1}. Hence we may assume that k ≥ h^{3/4}. Put ℓ = ⌊h^{3/4}⌋. Then, the elements a_{0}, 2a_{0}, …, ℓa_{0} are well-spaced:

∥ia_{0} − ja_{0}∥ = ∥(i − j)a_{0}∥ ≥ \frac{p}{2h},

for all i ≠ j, i, j ∈ {1, …, ℓ}. Consequently, the sets

ℓA_{1}, a_{0} + (ℓ − 1)A_{1}, …, (ℓ − 1)a_{0} + A_{1}  (4)

are pairwise disjoint. Indeed, if (ia_{0} + (ℓ − i)A_{1}) ∩ (ja_{0} + (ℓ − j)A_{1}) ≠ ∅ for some i ≠ j, i, j ∈ {0, …, ℓ − 1}, then there are elements a_{1}, …, a_{ℓ−i}, b_{1}, …, b_{ℓ−j} ∈ A_{1} such that

ia_{0} + a_{1} + ⋯ + a_{ℓ−i} = ja_{0} + b_{1} + ⋯ + b_{ℓ−j},

so that we would have

∥ja_{0} − ia_{0}∥ = ∥a_{1} + ⋯ + a_{ℓ−i} − b_{1} − ⋯ − b_{ℓ−j}∥
≤ ∥a_{1}∥ + ⋯ + ∥a_{ℓ−i}∥ + ∥b_{1}∥ + ⋯ + ∥b_{ℓ−j}∥
≤ \frac{p}{2h}.

Now by (4) and Theorem 4

|hA| ≥ |ℓA_{1}| + |a_{0} + (ℓ − 1)A_{1}| + ⋯ + |(ℓ − 1)a_{0} + A_{1}|
≥ (ℓ|A_{1}| − ℓ + 1) + ((ℓ − 1)|A_{1}| − ℓ + 2) + ⋯ + |A_{1}|
> ℓ^{2}|A|/4 − ℓ^{2}/2 > |hA|,

a contradiction. Hence A is contained in an arithmetic progression of cardinality ⌊p/h⌋ in ℤ_{p} and is F_{h}-isomorphic to a subset of integers. Applying Theorem 3 we infer that A is contained in an arithmetic progression of size max_{1≤j≤h−1} \frac{|hA|−P_{j}(|A|)}{h−j} +1, which completes the proof. □

Remark. Using a rectification principle from [1], one can prove that the bound for L(A) similar to that given in Theorem 3 holds also for A ⊆ ℤ_{p}, provided we put much more restrictive bounds on the size of A.

References

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

[2] G. Freiman, “Foundations of a structural theory of set addition,” Translations of Math. Monographs 37 (1973), American Math. Soc., Providence.

[3] V. F. Lev, Structure theorem for multiple addition and the Frobenius problem, Journal of Number Theory 58 (1996), 79–88.