Control and its applications in additive combinatorics

In this paper we start to investigate a new body of questions in additive combinatorics. The fundamental Cauchy--Davenport theorem gives a lower bound on the size of a sumset A+B for subsets of the cyclic group Zp of order p (p prime), and this is just one example of a large family of results. Our aim in this paper is to investigate what happens if we restrict the number of elements of one set that we may use to form the sums. Here is the question we set out to answer: given ...

This is a sequel to the paper arXiv:1312.6438 by the same authors. In this sequel, we quantitatively improve several of the main results of arXiv:1312.6438, and build on the methods therein. The main new results is that, for any finite set $A \subset \mathbb R$, there exists $a \in A$ such that $|A(A+a)| \gtrsim |A|^{\frac{3}{2}+\frac{1}{186}}$. We give improved bounds for the cardinalities of $A(A+A)$ and $A(A-A)$. Also, we prove that $|\{(a_1+a_2+a_3+a_4)^2+\log a_5 : a_i...

Sumset estimates, which provide bounds on the cardinality of sumsets of finite sets in a group, form an essential part of the toolkit of additive combinatorics. In recent years, probabilistic or entropic analogs of many of these inequalities were introduced. We study analogues of these sumset estimates in the context of convex geometry and Lebesgue measure on ${\mathbb R}^n$. First, we observe that, with respect to Minkowski summation, volume is supermodular to arbitrary orde...

This paper describes problems concerning the range of cardinalities of sumsets and restricted sumsets of finite subsets of the integers and finite subsets of ordered abelian groups.

Let $P \subset \mathbb R^2$ be a point set with cardinality $N$. We give an improved bound for the number of dot products determined by $P$, proving that, \[ |\{ p \cdot q :p,q \in P \}| \gg N^{2/3+c}. \] A crucial ingredient in the proof of this bound is a new superquadratic expander involving products and shifts. We prove that, for any finite set $X \subset \mathbb R$, there exist $z,z' \in X$ such that \[ \left|\frac{(zX+1)^{(2)}(z'X+1)^{(2)}}{(zX+1)^{(2)}(z'X+1)}\right| \...

In the present paper we show that if A is a set of n real numbers, and the product set A.A has at most n^(1+c) elements, then the k-fold sumset kA has at least n^(log(k/2)/2 log 2 + 1/2 - f_k(c)) elements, where f_k(c) -> 0 as c -> 0. We believe that the methods in this paper might lead to a much stronger result; indeed, using a result of Trevor Wooley on Vinogradov's Mean Value Theorem and the Tarry-Escott Problem, we show that if |A.A| < n^(1+c), then |k(A.A)| > n^(Omega((k...

We establish new bounds in the Bogolyubov-Ruzsa lemma, demonstrating that if A is a subset of a finite abelian group with density alpha, then 3A-3A contains a Bohr set of rank O(log^2 (2/alpha)) and radius Omega(log^{-2} (2/alpha)). The Bogolyubov-Ruzsa lemma is one of the deepest results in additive combinatorics, with a plethora of important consequences. In particular, we obtain new results toward the Polynomial Freiman-Ruzsa conjecture and improved bounds in Freiman's the...

We investigate additive properties of sets $A,$ where $A=\{a_1,a_2,\ldots ,a_k\}$ is a monotone increasing set of real numbers, and the differences of consecutive elements are all distinct. It is known that $|A+B|\geq c|A||B|^{1/2}$ for any finite set of numbers $B.$ The bound is tight up to the constant multiplier. We give a new proof to this result using bounds on crossing numbers of geometric graphs. We construct examples showing the limits of possible improvements. In par...

We prove that every subset of $\{1,\dots, N\}$ which does not contain any solutions to the equation $x+y+z=3w$ has at most $\exp(-c(\log N)^{1/5+o(1)})N$ elements, for some $c>0$. This theorem improves upon previous estimates. Additionally, our method has the potential to yield an optimal estimate for this problem that matches the known Behrend's lower estimate. Our approach relies on a new result on almost-periodicity of convolutions.

Szemeredi's regularity lemma is an important tool in graph theory which has applications throughout combinatorics. In this paper we prove an analogue of Szemeredi's regularity lemma in the context of abelian groups and use it to derive some results in additive number theory. One is a structure theorm for sets which are almost sum-free. If A is a subset of [N] which contains just o(N^2) triples (x,y,z) such that x + y = z then A may be written as the union of B and C, wher...