On Approximability of Satisfiable $k$-CSPs: VI

Abstract

We prove local and global inverse theorems for general $3$-wise correlations over pairwise-connected distributions. Let $\hat{I}¼$ be a distribution over $\hat{I}\pounds \times \hat{I}“\times \hat{I}¦$ such that the supports of $\hat{I}{¼}_{xy}$, $\hat{I}{¼}_{xz}$, and $\hat{I}{¼}_{yz}$ are all connected, and let $f:\hat{I}{\pounds }^n\to \mathbb{C}$, $g:\hat{I}{“}^n\to \mathbb{C}$, $h:\hat{I}{¦}^n\to \mathbb{C}$ be $1$-bounded functions satisfying \[ \left|\mathbb{E}_{(x,y,z) \sim μ^{\otimes n}}[f(x)g(y)h(z)]\right| \geq \varepsilon. \] In this setting, our local inverse theorem asserts that there is $\hat{I}´:=\text{exp}(-{\epsilon }^{-O_{\hat{I}}¼(1)})$ such that with probability at least $\hat{I}´$, a random restriction of $f$ down to $\hat{I}´n$ coordinates $\hat{I}´$-correlates to a product function. To get a global inverse theorem, we prove a restriction inverse theorem for general product functions, stating that if a random restriction of $f$ down to $\hat{I}´n$ coordinates is $\hat{I}´$-correlated with a product function with probability at least $\hat{I}´$, then $f$ is $2^{-\text{poly}(\log (1/\hat{I}´))}$-correlated with a function of the form $L\cdot P$, where $L$ is a function of degree $\text{poly}(1/\hat{I}´)$, $\Vert L{\Vert }_2\le 1$, and $P$ is a product function. We show applications to property testing and to additive combinatorics. In particular, we show the following result via a density increment argument. Let $\hat{I}\pounds$ be a finite set and $S\subseteq \hat{I}\pounds \times \hat{I}\pounds \times \hat{I}\pounds$ such that: (1) $(x,x,x)\in S$ for all $x\in S$, and (2) the supports of $S_{xy}$, $S_{xz}$, and $S_{yz}$ are all connected. Then, any set $A\subseteq \hat{I}{\pounds }^n$ with $|\hat{I}\pounds {|}^{-n}|A|\ge \hat{I}\text{c◯}((\log \log \log n{)}^{-c})$ contains $x,y,z\in A$, not all equal, such that $(x_i,y_i,z_i)\in S$ for all $i$. This gives the first reasonable bounds for the restricted 3-AP problem over finite fields.