Sum-avoiding sets in groups
Sum-avoiding sets in groups, Discrete Analysis 2016:15, 27 pp.
Let A be a subset of an Abelian group G. A subset B⊂A is called sum-avoiding in A if no two elements of B add up to an element of A. Write ϕ(A) for the size of the largest sum-avoiding subset of A. If G=Z and |A|=n, then it is known that ϕ(A) must be at least logn(loglogn)1/2−o(1), and examples are known of sets for which ϕ(A) is at most exp(O(√logn)). These results are due to Xuancheng Shao and Imre Ruzsa, respectively. Reducing this gap to a reasonable size appears to be a very hard problem.
If on the other hand, G has torsion, then it is possible for A to be large and finite while ϕ(A) is bounded. Indeed, if A is any subgroup, then ϕ(A)=1.
However, this is not the end of the story, as the authors show. Suppose we know that A is a subset of an Abelian group and that ϕ(A)≤k for some fixed k. What can we say about A? Note that this condition expresses a kind of weak closure property: instead of saying that any two elements of A add up to an element of A, it says that from any k+1 elements of A, two must add up to an element of A.
A simple example of such a set that isn’t itself a subgroup is a union of at most k subgroups. Then given more than k elements of A, two must belong to the same subgroup and hence add up to an element of A. In this paper, the authors show a converse to this easy observation: if ϕ(A)≤k, then there exist subgroups H1,…,Hm with m≤k such that |A∩Hi|≥c|Hi| for each i, and all but at most C elements of A belong to H1∪⋯∪Hm. Here, c>0 and C are constants that depend on k only.
If you are familiar with the Balog-Szemerédi theorem and Freiman’s theorem, then you might expect the proof of this result to be a fairly straightforward use of those tools. However, when one attempts to turn this thought into a proof, a significant difficulty arises, which the authors explain in their introduction. They resolve this difficulty by means of a complicated iterative argument – in fact, it is sufficiently complicated that instead of desperately trying to keep control of all the parameters that would arise, they resort to the language of non-standard analysis. This tidies up the argument considerably, but at the price of yielding no bound at all for how the constants c and C depend on k. However, this is not a huge price, as they also say that if they had avoided non-standard analysis, then the bounds they would have obtained would have been extremely weak.
The paper also contains a construction of arbitrarily large sets A with ϕ(A)≤k that contain no inverse pairs. This gives a negative answer to a question of Erdős. The construction, which is surprisingly simple, makes heavy use of the fact that their set lives in a group with order divisible by a small prime. They go on to show that this is necessary: if the order of G has no small prime divisors, then Erdős’s question has a positive answer.