Loading Web-Font TeX/Math/Italic
| 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.