4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ One can modify the Behrend construction to make $|A+A|$ reasonably small. I think it is unlikely that with current technology one can do much better than just using all the usual machinery used to prove the Roth and Freiman theorems. $\endgroup$
    – Terry Tao
    Nov 18 '16 at 4:12
3
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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|$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.