You are currently browsing the tag archive for the ‘sum-free sets’ tag.

Van Vu and I just posted to the arXiv our paper “sum-free sets in groups” (submitted to Discrete Analysis), as well as a companion survey article (submitted to J. Comb.). Given a subset of an additive group , define the quantity to be the cardinality of the largest subset of which is *sum-free in * in the sense that all the sums with distinct elements of lie outside of . For instance, if is itself a group, then , since no two elements of can sum to something outside of . More generally, if is the union of groups, then is at most , thanks to the pigeonhole principle.

If is the integers, then there are no non-trivial subgroups, and one can thus expect to start growing with . For instance, one has the following easy result:

*Proof:* We use an argument of Ruzsa, which is based in turn on an older argument of Choi. Let be the largest element of , and then recursively, once has been selected, let be the largest element of not equal to any of the , such that for all , terminating this construction when no such can be located. This gives a sequence of elements in which are sum-free in , and with the property that for any , either is equal to one of the , or else for some with . Iterating this, we see that any is of the form for some and . The number of such expressions is at most , thus which implies . Since , the claim follows.

In particular, we have for subsets of the integers. It has been possible to improve upon this easy bound, but only with remarkable effort. The best lower bound currently is

a result of Shao (building upon earlier work of Sudakov, Szemeredi, and Vu and of Dousse). In the opposite direction, a construction of Ruzsa gives examples of large sets with .

Using the standard tool of Freiman homomorphisms, the above results for the integers extend to other torsion-free abelian groups . In our paper we study the opposite case where is finite (but still abelian). In this paper of Erdös (in which the quantity was first introduced), the following question was posed: if is sufficiently large depending on , does this imply the existence of two elements with ? As it turns out, we were able to find some simple counterexamples to this statement. For instance, if is any finite additive group, then the set has but with no summing to zero; this type of example in fact works with replaced by any larger Mersenne prime, and we also have a counterexample in for arbitrarily large. However, in the positive direction, we can show that the answer to Erdös’s question is positive if is assumed to have no small prime factors. That is to say,

Theorem 2For every there exists such that if is a finite abelian group whose order is not divisible by any prime less than or equal to , and is a subset of with order at least and , then there exist with .

There are two main tools used to prove this result. One is an “arithmetic removal lemma” proven by Král, Serra, and Vena. Note that the condition means that for any *distinct* , at least one of the , , must also lie in . Roughly speaking, the arithmetic removal lemma allows one to “almost” remove the requirement that be distinct, which basically now means that for almost all . This near-dilation symmetry, when combined with the hypothesis that has no small prime factors, gives a lot of “dispersion” in the Fourier coefficients of which can now be exploited to prove the theorem.

The second tool is the following structure theorem, which is the main result of our paper, and goes a fair ways towards classifying sets for which is small:

Theorem 3Let be a finite subset of an arbitrary additive group , with . Then one can find finite subgroups with such that and . Furthermore, if , then the exceptional set is empty.

Roughly speaking, this theorem shows that the example of the union of subgroups mentioned earlier is more or less the “only” example of sets with , modulo the addition of some small exceptional sets and some refinement of the subgroups to dense subsets.

This theorem has the flavour of other inverse theorems in additive combinatorics, such as Freiman’s theorem, and indeed one can use Freiman’s theorem (and related tools, such as the Balog-Szemeredi theorem) to easily get a weaker version of this theorem. Indeed, if there are no sum-free subsets of of order , then a fraction of all pairs in must have their sum also in (otherwise one could take random elements of and they would be sum-free in with positive probability). From this and the Balog-Szemeredi theorem and Freiman’s theorem (in arbitrary abelian groups, as established by Green and Ruzsa), we see that must be “commensurate” with a “coset progression” of bounded rank. One can then eliminate the torsion-free component of this coset progression by a number of methods (e.g. by using variants of the argument in Proposition 1), with the upshot being that one can locate a finite group that has large intersection with .

At this point it is tempting to simply remove from and iterate. But one runs into a technical difficulty that removing a set such as from can alter the quantity in unpredictable ways, so one has to still keep around when analysing the residual set . A second difficulty is that the latter set could be considerably smaller than or , but still large in absolute terms, so in particular any error term whose size is only bounded by for a small could be massive compared with the residual set , and so such error terms would be unacceptable. One can get around these difficulties if one first performs some preliminary “normalisation” of the group , so that the residual set does not intersect any coset of too strongly. The arguments become even more complicated when one starts removing more than one group from and analyses the residual set ; indeed the “epsilon management” involved became so fearsomely intricate that we were forced to use a nonstandard analysis formulation of the problem in order to keep the complexity of the argument at a reasonable level (cf. my previous blog post on this topic). One drawback of doing so is that we have no effective bounds for the implied constants in our main theorem; it would be of interest to obtain a more direct proof of our main theorem that would lead to effective bounds.

## Recent Comments