| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

2. Additive combinatorics

    1. 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?
          It’s known that $f(A)\geq \exp{\log^c|A|}$. Also here, the Behrend construction does not imply $f(A)\leq |A|^c$.
        • A question about 2-coloring 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)}$.
              Using Roth’s theorem one can get $W(3,\ell)\leq 2^{\ell^{1+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 (sub-linear) 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 K|A|$. 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 K|A|$. 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 $nA-nA$ 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_{n-1})+\log_2 \sqrt[]{\frac{n}{n-1}} - o(1).$$
                                      This is not even known for $n=3$.
                                    • 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|^{2n-1}.$$ 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{n-1}{n}}.$$

                                                  Problem 2.6.

                                                  [Nets Katz] Suppose $$\rho_{2n+2}^{\frac{n-1}{n}}(A)< K\rho_{2n}(A)$$. Then there is $H\subset (n-1)A, |H|\geq \frac{\rho_{2n}^{\frac{1}{n-1}}}{K^c}$ so that $$E_4(H)\geq \frac{|H|^3}{|A|^{\varepsilon}K^{c'}}.$$
                                                      This conjecture has applications to PFR. In fact, given a set $A$ , we can list all the energies for various $n$, and separate to two cases.

                                                  1. Energy always increases (Smoothing.)

                                                  2. There is one point that the assumption of the conjecture is satisfied.(Non-smoothing) . The conjecture will give us some structure.
                                                    1. 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.