2. Additive combinatorics

Doubling of generic set of points
There is a result of Stancescu as follows: If $A\subset \mathbb{R}^2$ is a finite set with no three points on a line, then $$A+A\geq A(\log A)^c $$ for some $c>0$. Also we know that the lower bound of $A^{1\varepsilon}$ is false because of the Behrend construction. We would like to generalize this statement to higher dimensions.Problem 2.05.
[Brandon Hanson] Let $A\subset \mathbb{R}^3$ be a finite set with no five points on a plane. What is the best inequality $$A+A\geq A f(A)$$ that we can have? 
A question about 2coloring of integers
Let $W(k,\ell)$ be the minimum $n$ so that any red/blue coloring of $\{1,\cdots, n\}$ has either a red $k$AP or a blue $\ell$AP. The following conjecture is supported by numerical evidence.Problem 2.1.
[Jacob Fox. Attributed to R. Graham.] $W(3,\ell)= \ell^{2+o(1)}$. 
A stronger BSG theorem
The standard BSG theorem is as follows: let $E(A) = \{(a,b,c,d)\in A^4: a+b=c+d\}$. If $\frac{E(A)}{A^3}\geq \frac{1}{K}$ then there is a subset $A'\subset A$ so that $A'\geq \frac{A}{K^{100}}$ and $A'+A'\leq K^{100}A'$. One of the drawbacks of BSG theorem is that we lose control on $E(A')$. Can we have a stronger BSG theorem as follows?Problem 2.15.
[Freddie Manners] Let $A\subset G$, and suppose $E(A)\geq \frac{A^3}{K}$. Then there is a set $A'\subset A$ so that $$A'\geq \frac{A}{K^{100}},$$ $$A'+A'\leq K^{100}A',$$ $$\frac{E(A')}{A'^3}\geq \frac{E(A)}{A^3}$$ Can we moreover obtain the following? $$\frac{E(A')}{A'^3}\geq \frac{E(A)}{A^3} \left(\frac{A}{A'}\right)^{\frac{1}{100}}$$ 
Finding examples.
Problem 2.2.
[Shachar Lovett/Olof Sisask] Find counter examples to the polynomial Bogolyubov Ruzsa theorem.
Find interesting examples of subset $A\subset \mathbb{F}_2^n$ so that $A+A$ is far from all of $\mathbb{F}_2^n$.
Find interesting examples of $A\subset [N]$ of density $\alpha$ so that $4A$ does not contain long APs. 
Approximate Caratheodory theorem
There is the following important theorem: Let $A\subset \mathbb{R}^d$ be a finite set of points. Also assume that $A$ is contained in the $L^p$ unit Hamming ball for $p\geq 2$. Then any arbitrary point $a$ in the convex hull of $A$ can be approximated by a convex combination of only $O(p\varepsilon^{2})$ many points of $A$.Problem 2.25.
[Olof Sisask] Q. First, assuming some assumptions on the point set $A$, find a better dependence (sublinear) on $p$.
Q. Characterize configurations for which the bound $O(p\varepsilon^{2})$ is tight. status 
Finding good modeling
Let $A,B$ be subset of abelian groups $G, H$ respectively. A map $\phi: A\rightarrow B$ is called a Freiman isomorphism if $$a+b=c+d \iff \phi(a)+\phi(b)=\phi(c)+\phi(d).$$ We have the following modeling lemmas.
1. Let $A\subset \mathbb{F}_2^n$ and $A+A\leq KA$. Then $A$ is Freiman isomorphic to a subset of $\mathbb{F}_2^m$ where $\mathbb{F}_2^m\leq K^{O(1)}A$.
2. Let $A\subset \mathbb{Z}^d$ and $A+A\leq KA$. Then $A$ is Freiman isomorphic to a subset of a group $H$ where $H\leq K^{O(1)}A$.
Moreover, this is false for arbitrary groups instead of $\mathbb{Z}^d$ or $\mathbb{F}_2^n$.Problem 2.3.
[Olof Sisask] Suppose $A\subset G$, and $A+A\leq K A$. Can we find a subset $A'\subset A$ with $A'\geq K^{O(1)}A$ and a group $H$ so that $A'$ is Freiman isomorphic to a subset of $H$ and $H\leq K^{O(1)}A$? 
Product sets in iterated sumsets
Observe that the interval $[N]$ contains $[N^c][N^c]$ for $c=0.5$.Problem 2.35.
[Ilya Shkredov] There exists $n,\varepsilon,\delta$ for which the following holds. Let $A\subset \mathbb{F}_p$ and suppose $A+A\leq A^{1+\varepsilon}$. Then $nAnA$ contains a product set $XY$ where $X,Y\geq A^{1+\varepsilon}$.
If $X$ is polynomially large, how big can you make $Y$? 
Entropy of sum of random variables.
Let $G$ be a torsion free abelian group. Suppose $X$ is a random variable on $G$ and $S_n$ is sum of $n$ many $i.i.d$ copies of $X$. Let $H(\cdot)$ be the discrete entropy function.
We have the following theorem by T. Tao: $$H(S_2)\geq H(S_1)+\log_2 \sqrt[]{2}o(1) $$ where the $o(1)$ term goes to zero as $H(X)$ grows to infinity.Problem 2.4.
[Hoi Nguyen] Show $$H(S_n)\geq H(S_{n1})+\log_2 \sqrt[]{\frac{n}{n1}}  o(1).$$ 
Polynomial Freiman Ruzsa conjecture implies Polynomial Bogolyubov Ruzsa conjecture.
Problem 2.45.
[Shachar Lovett] Prove that polynomial Freiman Ruzsa conjecture implies Polynomial Bogolyubov Ruzsa conjecture. 
Finding almost subspace inside A+A
Problem 2.5.
[Shachar Lovett] Let $A\subset \mathbb{F}_2^n$ be a set of density $\alpha$. Then there is a subspace $V$ of codimension $\log^{O(1)}(\varepsilon^{1}\alpha^{1})$ so that $$V\cap (A+A)\geq (1\varepsilon)V$$ 
Finding structure inside $A+A$
Problem 2.55.
[Kaave Hosseini] Let $A\subset \mathbb{F}_2^n$ be a subset of density $0.01$. Then there is a subset $B\subset \mathbb{F}_2^n$ with density absolute constant, so that $$B+B\subset A+A$$ and $$B = S_1+\cdots+S_\ell$$ for some sets $S_i$’s with $S_i\leq poly(n)$ and $\ell\leq poly(n)$. 
A conjecture about generalized additive energy
Let $A\subset G$ and define $$E_{2n}(A) = \{(a_1,\cdots,a_n)\in A^{2n}: a_1+\cdots+a_n = a_{n+1}+\cdots+a_{2n}\}.$$ Trivial bounds on additive energy are $$A^n\leq E_{2n}(A)\leq A^{2n1}.$$ Define $$\rho_{2n}(A)= \frac{E_{2n}(A)}{A^n}.$$
Given this, one can compare various $\rho_k$’s. For example by an applications of Holder’s inequality one can get $$\rho_8(A) \geq \rho_4^3(A).$$ Moreover, there is the following theorem.
Theorem. Fix some $0<\varepsilon<1$. Suppose $\rho_8(A)\leq K\rho_4^3(A)$. then there is a subset $H\subset A$, so that $$H\geq \rho_4(A)/K^c$$ and $$E_4(H)\geq \frac{H^3}{A^{\varepsilon}K^{c'}}.$$
Now, using Holder’s inequality one can show $$\rho_{2n}\leq \rho_{2n+2}^{\frac{n1}{n}}.$$Problem 2.6.
[Nets Katz] Suppose $$\rho_{2n+2}^{\frac{n1}{n}}(A)< K\rho_{2n}(A)$$. Then there is $H\subset (n1)A, H\geq \frac{\rho_{2n}^{\frac{1}{n1}}}{K^c}$ so that $$E_4(H)\geq \frac{H^3}{A^{\varepsilon}K^{c'}}.$$
1. Energy always increases (Smoothing.)
2. There is one point that the assumption of the conjecture is satisfied.(Nonsmoothing) . The conjecture will give us some structure.
Remark. [Nets Katz] The problem is currently misstated because of an exaggeration of independence of constants. So for instance in the statement of the theorem, the inequality should have an extra factor of $A^{\epsilon}$ in the denominator $E_4(H) \geq {H^3 \over A^{\epsilon} K^{c'}}$ Similarly in the statement of the problem.
It is in fact an open problem whether those factors are really needed. But that isn’t the most important open problem. Even with the extra factors, the connection to Polynomial Freiman Ruzsa is pretty strong.

Cite this as: AimPL: Additive combinatorics and its applications, available at http://aimpl.org/addcombapp.