PROGRESSION-FREE SETS IN FINITE ABELIAN GROUPS

VSEVOLOD F. LEV

Abstract. Let G be a finite abelian group. Write 2G := {2g: g ∈ G} and denote by rk(2G) the rank of the group 2G.

Extending a result of Meshulam, we prove that if A ⊆ G is free of “true” arithmetic progressions (that is, a_{1} + a_{3} = 2a_{2} with a_{1}, a_{2}, a_{3} ∈ A implies that a_{1} = a_{3}), then |A| < 2|G|/ rk(2G). When G is of odd order this reduces to the original result of Meshulam.

As a corollary, we generalize a result of Alon and show that if an integer k ≥ 2 and a real ε > 0 are fixed, |2G| is large enough, and a subset A ⊆ G satisfies |A| ≥ (1/k + ε) |G|, then there exists A_{0} ⊆ A such that 1 ≤ |A_{0}| ≤ k and the elements of A_{0} add up to zero. When G is of odd order or cyclic this reduces to the original result of Alon.

1. Motivation and background

Since the fundamental paper of Roth [R53] one of the central problems in combinatorial number theory is to estimate the maximum possible cardinality of an integer set A ⊆ [1, m], free of three-term arithmetic progressions; here m is a growing to infinity integer parameter. Equivalently, one can consider progression-free subsets of ℤ_{m}, the cyclic group of order m. If D(ℤ_{m}) denotes the maximum possible cardinality of such a subset, then the result of Roth can be formulated as D(ℤ_{m}) = O(m/ ln ln m), and further refinements due to Heath-Brown [H87], Szemerédi [S90], and Bourgain [B99] as D(ℤ_{m}) = O(m/ ln^{α} m) with an absolute constant α > 0.

A natural generalization is to replace ℤ_{m} with an arbitrary finite abelian group G and estimate D(G), the maximum possible cardinality of a subset A ⊆ G, free of three-term arithmetic progressions. For abelian groups G of odd order, Brown and Buhler in [BB82] and independently Frankl, Graham, and Rödl in [FGR87] proved that D(G) = o(|G|) as |G| → ∞. A quantitative estimate is due to Meshulam [M95] who has shown that D(G) ≤ 2|G|/ rk(G) for any non-trivial abelian group G of odd order; here and below throughout the paper rk(G) denotes the rank of G. As Meshulam shows, along with the result of Heath-Brown and Szemerédi this implies that D(G) = O(|G|/ ln^{β} |G|) for some absolute constant β > 0 and any non-trivial abelian group G of odd order.

2 VSEVOLOD F. LEV

Suppose now that G is either abelian of odd order or finite cyclic. Using the result of Frankl, Graham, and Rödl in the first case, and the result of Roth is the second case, Alon proved in [A87] the following. Suppose that an integer k ≥ 2 and a real ε > 0 are fixed. Then provided that |G| is large enough, for any subset A ⊆ G satisfying |A| > (1/k + ε) |G| there exists A_{0} ⊆ A such that 1 ≤ |A_{0}| ≤ k and the elements of A_{0} add up to zero.

2. Notation and summary of results

Our goal is to extend the results of Meshulam and Alon onto arbitrary finite abelian groups, not necessarily of odd order. First we discuss a question which we have not addressed yet, namely: what is a three-term arithmetic progression and when we say that a set is free of such progressions? The answer is quite straightforward for groups of odd order but somewhat subtler for even order groups: is the set {1, 6} ⊆ ℤ_{10} free of arithmetic progressions?

Let G be an abelian group. We say that a three-element sequence P = (a_{1}, a_{2}, a_{3}) of elements of G is an arithmetic progression if a_{1} + a_{3} = 2a_{2}, and not all elements of P are equal to each other. If, moreover, all elements of P are pairwise distinct (equivalently, if a_{1} ≠ a_{3}) then we say that P is a true arithmetic progression. Clearly, if G has no elements of even order then any arithmetic progression is true and the notions of “arithmetic progression” and “true arithmetic progression” coincide. By PF[G] we denote the family of all subsets of G, free of true arithmetic progressions; that is, all subsets A ⊆ G such that a_{1} + a_{3} = 2a_{2} with a_{1}, a_{2}, a_{3} ∈ A implies that a_{1} = a_{3}. Assuming that G is finite, we let

D(G) := max{|A|: A ∈ PF[G]},

the maximum possible cardinality of a subset of G, free of true arithmetic progressions.

One last bit of notation before we can formulate our results. For an abelian group G we write

2G := {2g: g ∈ G}.

Clearly, 2G is a subgroup of G, and if G is finite of odd order then 2G = G. Furthermore, 2G is the trivial group if and only if G is an elementary abelian 2-group.

Theorem 1. For any finite abelian group G such that 2G is non-trivial we have

D(G) < \frac{2|G|}{rk(2G)}.

Corollary 1. There exist absolute real constants C and β > 0 with the property that for any finite abelian group G such that 2G is non-trivial we have

D(G) < C \frac{|G|}{(ln |2G|)^{β}} .

When G is of odd order Theorem 1 and Corollary 1 reduce to [M95, Theorem 1.2] and [M95, Corollary 1.3], respectively. We prove Theorem 1 in the next section using a version of Meshulam’s argument (which itself originates from Roth’s method) and employing some additional ideas. Corollary 1 can be derived from Theorem 1 and the result of Heath-Brown and Szemerédi in the same way as [M95, Corollary 1.3] is derived from [M95, Theorem 1.2]; the only difference is that instead of a “large” cyclic subgroup H ≤ G one should consider a “large” cyclic subgroup H ≤ 2G. We refer the reader to [M95] for the details.

Theorem 2. Let G be a finite abelian group. Then for any integer k ≥ 2 and any subset A ⊆ G satisfying |A| ≥ (1/k)|G| + 4kD(G) there exists A_{0} ⊆ A such that 1 ≤ |A_{0}| ≤ k and the elements of A_{0} add up to zero.

Corollary 2. For any integer k ≥ 2 and real ε > 0 there exists an integer n_{0}(k, ε) with the following property. Let G be a finite abelian group such that |2G| > n_{0}(k, ε) and suppose that a subset A ⊆ G satisfies |A| ≥ (1/k + ε) |G|. Then there exists A_{0} ⊆ A such that 1 ≤ |A_{0}| ≤ k and the elements of A_{0} add up to zero.

When G is a finite cyclic group, Corollary 2 reduces to [A87, Theorem 1.1] and Theorem 2 is analogous to [A87, Proposition 2.5]. The proof of Theorem 2 can be conducted following the proof of [A87, Proposition 2.5], except that the three-uniform hypergraph considered by Alon is to be replaced by the graph in which two vertices are adjacent if and only if the corresponding elements are the endterms of a true three-term arithmetic progression. For completeness and reader’s convenience we outline the proof at the end of the next section; details can be retrieved from [A87]. Corollary 2 is immediate from Theorem 2 and Corollary 1.

3. Proof of Theorems 1 and 2

Proof of Theorem 1. Using induction on the integer n ≥ 1, we show that if G is a finite abelian group such that rk(2G) ≥ n, then D(G) < 2|G|/n. The case n = 1 is trivial and we assume that n ≥ 2. Suppose that A ∈ PF[G]; we want to show that |A| < 2|G|/n.

Consider the endomorphism φ ∈ End(G) defined by φ(g) = 2g (g ∈ G). The image of φ is 2G and the kernel of φ is G_{0} := {g ∈ G: 2g = 0}. Thus G/G_{0} ≅ 2G and

4 VSEVOLOD F. LEV

writing t := |2G| we conclude that G is a union of t disjoint G_{0}-cosets. Accordingly, A is a union of t disjoint subsets contained in a G_{0}-coset each. Let n_{1}, …, n_{t} denote the cardinalities of these subsets so that n_{1}+⋯+n_{t} = |A| and 0 ≤ n_{i} ≤ |G_{0}| (i = 1, …, t).

By Â we denote the Fourier coefficients of the characteristic function of A; that is, for a character χ ∈ Ĝ we write

Â(χ) := ∑_{a∈A} χ̄(a),

where χ̄ is the character conjugate to χ. The cartesian square and cartesian cube of A are denoted by A^{2} and A^{3}, respectively.

Since A ∈ PF[G], using orthogonality relations we obtain

∑χ∈Ĝ(Â(χ))^{2}Â(χ̄^{2}) = |G| #{(a_{1}, a_{2}, a_{3}) ∈ A^{3} : a_{1} + a_{3} = 2a_{2}}

= |G| #{(a_{1}, a_{2}) ∈ A^{2} : 2a_{1} = 2a_{2}} = |G| #{(a_{1}, a_{2}) ∈ A^{2} : a_{2} − a_{1} ∈ G_{0}} = |G| (n_{1}^{2} + ⋯ + n_{t}^{2})

≤ |G| (n_{1} + ⋯ + n_{t}) max_{1≤i≤t} n_{i}

≤ |G||A||G_{0}|.

We single out those summands corresponding to real characters χ. Notice that χ is real if and only if χ^{2} = χ_{0}, the principle character. In this case Â(χ̄^{2}) = |A| and we get

− ∑_{χ∈Ĝ: χ^{2}≠χ_{0}} (Â(χ))^{2}Â(χ̄^{2}) ≥ ∑_{χ∈Ĝ: χ^{2}=χ_{0}} (Â(χ))^{2}Â(χ̄^{2}) − |G||A||G_{0}|

= |A| ∑_{χ∈Ĝ: χ^{2}=χ_{0}} (Â(χ))^{2} − |G||A||G_{0}|

= |A| S − |G||A||G_{0}|,  (1)

where S = ∑_{χ∈Ĝ: χ^{2}=χ_{0}} (Â(χ))^{2}. Set

M := max_{χ∈Ĝ: χ^{2}≠χ_{0}} |Â(χ̄^{2})|.

Since Â(χ) is real for any real character χ, from (1) and the Parseval identity it follows that

|A| S − |G||A||G_{0}| ≤ M ∑_{χ∈Ĝ: χ^{2}≠χ_{0}} |Â(χ)|^{2}

= M ( ∑_{χ∈Ĝ} |Â(χ)|^{2} − S)

= (|A||G| − S) M.

We now observe that |S| ≥ |A|^{2} (as all summands in the definition of S are nonnegative, and the term corresponding to the principle character contributes |A|^{2} to the sum), hence

M ≥ \frac{|A|^{2} − |G||G_{0}|}{|G| − |A|}.  (2)

We need the following simple lemma, in which the usual notation for (non-normalized) Fourier coefficients and the averaging operator is used.

Lemma 1. Let f: G → ℝ be a real-valued function on the finite abelian group G, and let χ be a non-trivial character of G. If χ_{0} denotes the trivial character of G and W = ker χ, then there exists g ∈ G such that

∑_{w∈W} f(g + w) ≥ \frac{|W |}{|G|} (f̂(χ_{0}) + |f̂(χ)|);

in other words,

𝔼_{g+W} (f) ≥ 𝔼_{G}(f) + |𝔼_{G}(f · χ)|.

Proof. Let U be a system of representatives of W -cosets and write

C := max_{g∈U} ∑_{w∈W} f(g + w).

Since χ(g) = χ(g + w) for any g ∈ G and w ∈ W, we have

|f̂(χ)| = | ∑_{g∈U} (C − ∑_{w∈W} f(g + w))χ̄(g)|

≤ ∑_{g∈U} (C − ∑_{w∈W} f(g + w))

= C |G/W | − f̂(χ_{0})

and it follows that C ≥ (f̂(χ_{0}) + |f̂(χ)|) |W |/|G|, as wanted. □

Back to the proof of the theorem, fix a non-real character χ such that |Â(χ̄^{2})| = M and let W < G be the kernel of χ^{2}; that is, W = {g ∈ G: χ^{2}(g) = 1}. By (2) and Lemma 1, applied to the characteristic function of A, there exists g ∈ G with

|A ∩ (g + W)| ≥ \frac{|W |}{|G|} (|A| + M) ≥ \frac{|A| − |G_{0}|}{|G| − |A|} |W |.

Observing that ((A − g) ∩ W ) ∈ PF[W] and writing for brevity κ := D(W)/|W | we derive from the last estimate that

κ ≥ \frac{|A| − |G_{0}|}{|G| − |A|}.  (3)

We now use the induction hypothesis (applied to W) to bound κ from above. Since the quotient group G/W is isomorphic to the image of χ^{2}, which is a finite subgroup of the multiplicative group of the field of complex numbers, we conclude that G/W is cyclic or trivial. It follows that 2G/2W is cyclic or trivial, too, whence

rk(2W) ≥ rk(2G) − 1 ≥ n − 1

and therefore κ < 2/(n − 1). Substituting to (3) and re-arranging the terms we get

|A| < \frac{2/(n − 1) + |G_{0}|/|G|}{2/(n − 1) + 1} |G|.  (4)

Since the quotient |G_{0}|/|G| can be rather large, at this point we have to take into account the algebraic structure of G. Write r := rk(G) and G = ⨁_{i=1}^{r} G_{i}, where the direct summands are cyclic subgroups of G the orders of which d_{i} := |G_{i}| (i = 1, …, r) satisfy 2 ≤ d_{1} | ⋯ | d_{r}. Set j := max{i ∈ [1, n]: d_{i} = 2} (with the understanding that max ∅ = 0) and put

G′ := ⨁_{i=1}^{j} G_{i}, G′′ := ⨁_{i=j+1}^{r} G_{i}.

Consequently, we have G = G′ ⊕ G′′, 2G′ = {0}, and

rk(G′′) = rk(2G′′) = rk(2G) ≥ n.  (5)

We distinguish two cases. First we assume that G satisfies rk(2G) = rk(G). In this case G′ is the trivial group and

\frac{|G_{0}|}{|G|} = ∏_{i∈[1,r]: d_{i} is odd} \frac{1}{d_{i}} ∏_{i∈[1,r]: d_{i} is even} \frac{2}{d_{i}} ≤ (\frac{1}{2})^{r} ≤ \frac{1}{2^{n}} < \frac{2}{n(n − 1)}.  (6)

From (4) and (6) we obtain

|A| < \frac{2/(n − 1) + 2/n(n − 1)}{2/(n − 1) + 1} |G| = \frac{2}{n} |G|,

as required.

PROGRESSION-FREE SETS 7

It remains to consider the case when rk(2G) < rk(G); that is, the group G′ is nontrivial. To this end we observe that D(G) ≤ |G′| D(G′′). Indeed, if B ⊆ G satisfies |B| > |G′| D(G′′), then there exists a coset g + G′′ (with some g ∈ G) such that |B ∩ (g + G′′)| > D(G′′); by the definition of D(G′′), the set B − g ⊆ G′′ contains a true arithmetic progression, and so does B. Now by (5) and the argument above, as applied to the group G′′, we have

D(G) ≤ |G′| D(G′′) < |G′| \frac{2|G′′|}{n} = \frac{2|G|}{n}.

This completes the proof of Theorem 1. □

Sketch of the proof of Theorem 2. Suppose that G, k, and A are as in the theorem. We can assume that k ≥ 3 as otherwise the assertion follows readily from the pigeonhole principle. Define A′ to be the set of all those elements of A which are the midterms of at least 2(k − 1) true three-term arithmetic progressions with the elements in A:

A′ := {a ∈ A: #{(a_{1}, a_{2}) ∈ A^{2} : a_{1} + a_{2} = 2a, a_{1} ≠ a_{2}} ≥ 2(k − 1)}.

Write A′′ := A \ A′ and consider the graph Γ = (A′′, E) on the vertex set A′′ in which two (distinct) vertices a_{1}, a_{2} ∈ A′′ are adjacent if and only if there exists a ∈ A′′ such that a_{1} + a_{2} = 2a. The number of edges of Γ is

|E| ≤ (k − 2)|A′′|

(as any a ∈ A′′ satisfies at most 2(k−2) equalities of the form a_{1}+a_{2} = 2a with a_{1}, a_{2} ∈ A′′, a_{1} ≠ a_{2}), hence by a simple probabilistic argument there is an independent vertex set B ⊆ A′′ of cardinality |B| ≥ |A′′|^{2}/(4|E|) ≥ |A′′|/(4(k − 2)). By the construction we have B ∈ PF[G] whence |B| ≤ D(G); therefore |A′′| ≤ 4(k − 2)D(G) and consequently |A′| > |G|/k. By [A87, Corollary 2.3] there exists an integer h ∈ [1, k] and a sequence (a_{1}, …, a_{h}) of not necessarily distinct elements of A′ such that a_{1} + ⋯ + a_{h} = 0. By the choice of the set A′, for any i ∈ [1, h] there are at least 2(k − 1) representations 2a_{i} = a_{i}^{(1)} + a_{i}^{(2)} with a_{i}^{(1)}, a_{i}^{(2)} ∈ A and a_{i}^{(1)} ≠ a_{i}^{(2)}, and it is not difficult to conclude that the sum a_{1} + ⋯ + a_{h} can be re-written as a sum of h pairwise distinct elements of A; see the proof of [A87, Proposition 2.5] for the explanation. Thus we have found h ∈ [1, k] pairwise distinct elements of A with zero sum. □

References

[A87] N. Alon, Subset sums, J. Number Theory 27 (1987), 196–205.

[B99] J. Bourgain, On triples in arithmetic progression, Geom. Func. Anal. 9 (1999), 968–984.

[BB82] T.C. Brown and J.C. Buhler, A density version of a geometric Ramsey theorem, J. Combin. Theory, Ser. A 32 (1982), 20–34.

[FGR87] P. Frankl, G Graham, and V. Rödl, On subsets of abelian groups with no 3-term arithmetic progression, J. Combin. Theory, Ser. A 45 (1987), 157–161.

[H87] R. Heath-Brown, Integer sets containing no arithmetic progressions, J. London Math. Soc. 35 (1987), 385–394.

[M95] R. Meshulam, On subsets of finite abelian groups with no 3-term arithmetic progressions, J. Combin. Theory, Ser. A 71 (1995), 168–172.

[R53] K.F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104–109.

[S90] E. Szemerédi, Integer sets containing no arithmetic progressions, Acta Math. Hungar. 56 (1990), 155–158.

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

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