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\subset A\) is called sum-avoiding in \(A\) if no two elements of \(B\) add up to an element of \(A\). Write \(\phi(A)\) for the size of the largest sum-avoiding subset of \(A\). If \(G=\mathbb Z\) and \(|A|=n\), then it is known that \(\phi(A)\) must be at least \(\log n(\log\log n)^{1/2-o(1)}\), and examples are known of sets for which \(\phi(A)\) is at most \(\exp(O(\sqrt{\log n}))\). 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 \(\phi(A)\) is bounded. Indeed, if \(A\) is any subgroup, then \(\phi(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 \(\phi(A)\leq 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 \(\phi(A)\leq k\), then there exist subgroups \(H_1,\dots,H_m\) with \(m\leq k\) such that \(|A\cap H_i|\geq c|H_i|\) for each \(i\), and all but at most \(C\) elements of \(A\) belong to \(H_1\cup\dots\cup H_m\). 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 \(\phi(A)\leq 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.