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 2 For 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 3 Let
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.
11 comments
Comments feed for this article
11 March, 2016 at 9:44 am
Anonymous
Is it possible to get information on the structure of
from the knowledge of
for sufficiently many subsets
of
?
11 March, 2016 at 6:39 pm
arch1
“this paper of Erdos” – link missing?
[Corrected, thanks – T.]
12 March, 2016 at 5:23 pm
anonymouse
The link of Van Vu in the first sentence seems wrong.
[Corrected, thanks – T.]
13 March, 2016 at 5:32 am
HUMBERTO
$order o(1) ???$
4 December, 2018 at 1:25 am
Rik Bos
Does proposition 1 hold when A contains 0? For instance, if A={0,1,3,4} then k=2 and a sum-free subset of cardinality 3 does not exist.
4 December, 2018 at 3:01 am
Bik Ros
0 is not a natural number
4 December, 2018 at 8:14 am
Rik Bos
Well, that seems to be an ongoing debate. Since Bourbaki, many people tend to include 0 to the natural numbers. Also, this paper is about additive groups, where 0 plays an important role. Finally, a comment from https://terrytao.wordpress.com/books/analysis-i/ states:
“Natural numbers have no zero divisors” should read “Positive natural numbers have no zero divisors”.
4 December, 2018 at 3:21 pm
Bik Ros
There should not be any debate. See the middle of page 7 of the paper he links to (“sum-free sets in groups”, now named “sum-avoiding sets in groups”), which says “the natural numbers N = {1,2,…}”.
With this in mind, the responses to your points are the following:
1). Terry does not consider 0 a natural number.
2). I don’t see why 0 playing an important role should mean it is a natural number.
3). The example you provided seems more like an exception.
6 December, 2018 at 9:15 am
Rik Bos
Well, especially the reference to p. 7 settles my question, even though the comment related to his book seems to indicate otherwise. Indeed, p. 18 of his book states:
*Axiom 2.1.* 0 is a natural number
7 December, 2018 at 12:55 pm
Terence Tao
Regarding the question of when to include zero amongst the natural numbers, I can refer readers to my previous comments on this question at https://terrytao.wordpress.com/books/analysis-i/#comment-439818 and https://terrytao.wordpress.com/2014/11/23/254a-notes-1-elementary-multiplicative-number-theory/#comment-442582 (and also Remark 2.1.2 of my “Analysis I” book). The short answer is that in some contexts it is slightly preferable to consider zero a natural number, and in other contexts it is preferable not to. (But it is ultimately worth bearing in mind that, the quote attributed to Kronecker notwithstanding, the choice of what we do or do not consider to be a natural number is ultimately a human convention.)
7 December, 2018 at 2:15 pm
Rik Bos
Thanks for your answer. So basically, you state that the inclusion or exclusion of 0 as a natural number is context-dependent. I guess my context is that 0 is a natural number unless stated otherwise (since as you write, it is ultimately a matter of convention).