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

      Add remark

      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.

          Add remark

          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)}}$.
            1. Remark. [Olof Sisask] Progress on finding the true bounds by Ben Green: https://arxiv.org/abs/2102.01543

                • 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?

                  Add remark

                  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.


                      Add remark

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

                          Add remark

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

                              Add remark

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

                                  Add remark

                                  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.

                                      Add remark

                                      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.


                                          Add remark

                                          Problem 2.45.

                                          [Shachar Lovett] Prove that polynomial Freiman Ruzsa conjecture implies Polynomial Bogolyubov Ruzsa conjecture.

                                            • Finding almost subspace inside A+A


                                              Add remark

                                              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$


                                                  Add remark

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

                                                      Add remark

                                                      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.