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

2. Additive combinatorics

    1. Non-linear Roth


      Add remark

      Problem 2.1.

      [Boris Bukh] Let $P$ be any (non-linear) polynomial, $A\subset \mathbb{F}_p$ with $|A|>p^{0.99}$. Does there always exist distinct $x,y$ such that $$x,y,y+P(x)-P(y)\in A?$$
          When $P(x)=2x$, this recovers Roth’s Theorem on 3-APs.

        • Roth with common difference $p-1$


          Add remark

          Conjecture 2.2.

          [Mehtaab Sawhney] For all $C>0$ and sufficiently large $N$, if $A\subset [N]$ with $|A|\geq N/\log^C N$, then there exists $x$ and $p$ prime such that $$x,x+p-1,x+2(p-1)\in A.$$
              A hard result of Green says that if $|A|>N^{1-c}$, then we can find $x,x+p-1\in A$, so we don’t reasonably expect to get power-saving bounds for the above conjecture.

          A model problem is the following. Let $W=\prod_{p\text{ prime}, p\leq w}p$ and $S$ the set of positive integers coprime to $W$. Then find in $A$ a 3-AP of the form $x,x+y,x+2y$ with $y\in S$.
            1. Remark. [Cosmin Pohoata] What if we replace the set {p-1 : p prime} with the set of positive integers that can be written as a sum of two squares?

                • Roth with constrained differences


                  Add remark

                  Problem 2.3.

                  [Huy Pham] For which $0\in D\subseteq \mathbb{F}_p$ is it true that any $A\subset \mathbb{F}_p^n$ avoiding $$x,x+y,x+2y\in A\quad \text{with } y\in D^n\setminus\{0\}$$ has size $\leq C^n$ for some $C < p$?
                      Slice rank + "multilinear trick" implies the problem is true for $|D|>p/2$.

                  For $D=\{0,1,2\}$, it is known that we must have $|A|\leq p^n/(\log\log\log n)^c$.

                  When $|D|=2$, Hales-Jewett gives $|A|=o(p^n)$.

                    • Inverse theorem for equilateral triangles on the sphere

                          Denote by $S^n\subset \mathbb{R}^{n+1}$ the unit sphere. For a function $f:S^n\to \mathbb{R}$, define the quantity $$Tf:= \mathbb{E}_{x,y,z\in S^n,x+y+z=0} f(x)f(y)f(z).$$

                      Add remark

                      Problem 2.4.

                      [Dmitrii Zakharov] If $f$ is 1-bounded and $|Tf|>\delta$, does $f$ correlate with a function that depends on $O_{\delta}(1)$ coordinates (with respect to some basis)?
                          This is motivated by the following conjecture: the largest subset of the sphere avoiding $x+y+z=0$ is a hemisphere.

                      Let $T_{\alpha}f=\mathbb{E}_{x,y\in S^n,\langle x,y\rangle=\alpha} f(x)f(y)$. It is known that if $|T_{\alpha}f|>\delta$, then $f$ correlates with a low-degree harmonic function.

                      An analogous problem can be posed on the plane. For example, given $f:[0,10]^2\to\mathbb{C}$, if we instead define $Tf=\mathbb{E}_{x,y,z\text{ unit equilateral triangle}} f(x)f(y)f(z)$, can we prove an inverse theorem in this setting? What about for unit equilateral triangles in $\mathbb{F}_p^2$?

                        • Easier arithmetic Kakeya


                          Add remark

                          Conjecture 2.5.

                          [Manik Dhar] Let $S\subset\mathbb{Z}^n$ be such that for all $(d_1,\ldots,d_r)\in ([N]^n)^r$, $S$ contains the GAP (for some translate $a_0$) $$\{a_0+i_1d_1+\cdots +i_rd_r : i_1,\ldots,i_r\in \{0,1,\ldots,k-1\}\}.$$ Then $|S|\geq N^{c_kn+o_{k\to\infty}(1)}$.
                              The case $r=1$ is a version of arithmetic Kakeya, and is known with bound $N^{0.59n+o_k(1)}$.

                          There is an equivalent entropic formulation. Let $X,Y_1,\ldots,Y_r$ be $\mathbb{Z}$-valued random variables such that $$H(X+a_1Y_1+\ldots+a_rY_r)\leq h\quad \forall a_1,\ldots,a_r\in \{0,1,\ldots,k-1\}.$$ Then $H(Y_1,\ldots,Y_r)\leq rhc_k$.

                            • Popular Furstenberg–Sárközy

                                  (Furstenberg–Sárközy) For all $\epsilon>0$, there exists $N_0=N_0(\epsilon)$ such that for all $N\geq N_0$, $A\subseteq [N]$ with $|A|\geq \delta N$, there exists $y\neq 0$ such that $$|\{x : x,x+y^2\in A\}|\geq (\delta^2-\epsilon)N,$$ with $N_0(\epsilon)\leq e^{1/\epsilon^c}$.

                              Add remark

                              Problem 2.6.

                              [Sean Prendiville] (1) Prove lower bounds of the form $N_0(\epsilon)>superpoly(1/\epsilon)$, or even just $N_0(\epsilon)>1/\epsilon^{10}$.

                              (2) What happens in the function field case $\mathbb{F}_p[t]_{< n}$? Can we prove upper/lower bounds?

                                  Cite this as: AimPL: High-dimensional phenomena in discrete analysis, available at http://aimpl.org/highdimdiscrete.