Sum-avoiding sets in groups

Terence Tao ; Van Vu

Discrete analysis (2016)

Résumé

Let $A$ be a finite subset of an arbitrary additive group $G$, and let $φ(A)$ denote the cardinality of the largest subset $B$ in $A$ that is sum-avoiding in $A$ (that is to say, $b_1+b_2 \not \in A$ for all distinct $b_1,b_2 \in B$). The question of controlling the size of $A$ in terms of $φ(A)$ in the case when $G$ was torsion-free was posed by Erdős and Moser. When $G$ has torsion, $A$ can be arbitrarily large for fixed $φ(A)$ due to the presence of subgroups. Nevertheless, we provide a qualitative answer to an analogue of the Erdős-Moser problem in this setting, by establishing a structure theorem, which roughly speaking asserts that $A$ is either efficiently covered by $φ(A)$ finite subgroups of $G$, or by fewer than $φ(A)$ finite subgroups of $G$ together with a residual set of bounded cardinality. In order to avoid a large number of nested inductive arguments, our proof uses the language of nonstandard analysis. We also answer negatively a question of Erdős regarding large subsets $A$ of finite additive groups $G$ with $φ(A)$ bounded, but give a positive result when $|G|$ is not divisible by small primes.

Détail

Publié le : 2016-08-31