How big must the sumset $A+A$ be if $A$ satisfies no translation-invariant equations of low height?

Question

Suppose $A$ is a finite subset of an abelian group. If there is no solution to $ma+nb=(m+n)c$ with $0\leq m,n\leq M$, can we bound $|A+A|$ from below? I am interested if one can obtain bounds much better than, say, applying Roth or Freiman type theorems.

Answer 1

This problem was considered by Yonutz Stanchescu ("Planar sets containing no three collinear points and non-averaging sets of integers", Discrete Math. 256 (2002), no. 1–2, pp. 387–395). Stanchescu called sets with this property non-averaging of order $M$, and showed that if $A$ is such a set then, letting for brevity $n:=|A|$ and denoting by $s_M(n)$ the largest size of a non-averaging of order $M$ subset of $[1,n]$, one has $$ |A\pm A| \ge (16M^2)^{1/(4M)}\left(\frac{n}{s_M(n)}\right)^{1/(4M)}n. $$ (Notice that $s_M(n)\le s_1(n)$, and that $s_1(n)$ is the size of the largest subset of $[1,n]$ free of three-term arithmetic progressions.)

The proof is based on the results of Ruzsa, and in fact the case $M=1$ was established by Ruzsa himself ("Arithmetical progressions and the number of sums", Period. Math. Hungar. 25 (1992), no. 1, 105–111).

Answer 2

In the comments Terry Tao suggested looking at Behrend-type sets. I wanted to calculate exactly what kinds of lower bounds this gives.

The bounds I got this way don't really depend on $M$. Indeed, if you're in a truly arbitrary abelian group then there are sets (with small sumsets) that do not have nontrivial solutions of $ma+ nb = (m+n)c$ for any positive $m,n$. Indeed, any such $a,b,c$ in $\mathbb R^n$ or $\mathbb Z^n$ must be colinear, so a set without colinear triples provides an example. I will provide an example of a set without colinear triples with a small sumset.

Let $c$ be a number the equation $\sum_{i=1}^n x_i^2 = c$ has the maximum number of integer solutions $x_1,\dots,x_n$ satisfying $x_i \in \{-k,\dots,k\}$ for all $c$ in the interval $[0,n k^2]$. Then by pidgeonhole $|A| \geq (2k+1)^n / (nk^2)$ and since clearly $A + A \subseteq [-2k,\dots,2k]^n$, $|A+A| \leq (4k+1)^n$.

Setting $k$ to be exponential in $n$, we see that $|A+A|/|A|$ is exponential in $n$ while $|A|$ is exponential in $n^2$, so we can have $|A+A| \leq |A| e^{ O(\sqrt{\log |A|})}$ for any $M$, uniformly in $M$.

Of course something similar will work in much more restricted groups, including cyclic groups, using base notation, as long as the order of the group is much larger than $|A|$.