2. Additive combinatorics

Nonlinear Roth
Problem 2.1.
[Boris Bukh] Let $P$ be any (nonlinear) 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?$$ 
Roth with common difference $p1$
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+p1,x+2(p1)\in A.$$
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 3AP of the form $x,x+y,x+2y$ with $y\in S$.
Remark. [Cosmin Pohoata] What if we replace the set {p1 : p prime} with the set of positive integers that can be written as a sum of two squares?


Roth with constrained differences
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$?
For $D=\{0,1,2\}$, it is known that we must have $A\leq p^n/(\log\log\log n)^c$.
When $D=2$, HalesJewett 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).$$Problem 2.4.
[Dmitrii Zakharov] If $f$ is 1bounded and $Tf>\delta$, does $f$ correlate with a function that depends on $O_{\delta}(1)$ coordinates (with respect to some basis)?
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 lowdegree 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
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,k1\}\}.$$ Then $S\geq N^{c_kn+o_{k\to\infty}(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,k1\}.$$ 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}$.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: Highdimensional phenomena in discrete analysis, available at http://aimpl.org/highdimdiscrete.