On Approximability of Satisfiable $k$-CSPs: VI

We prove local and global inverse theorems for general $3$-wise correlations over pairwise-connected distributions. Let $\mu$ be a distribution over $\mathrm{\Sigma }\times \mathrm{\Gamma }\times \mathrm{\Phi }$ such that the supports of ${\mu }_{xy}$, ${\mu }_{xz}$, and ${\mu }_{yz}$ are all connected, and let $f:{\mathrm{\Sigma }}^n\to \mathbb{C}$, $g:{\mathrm{\Gamma }}^n\to \mathbb{C}$, $h:{\mathrm{\Phi }}^n\to \mathbb{C}$ be $1$-bounded functions satisfying $$\mid {\mathbb{E}}_{(x,y,z)\sim {\mu }^{\otimes n}}[f(x)g(y)h(z)]\mid \ge \epsilon \mathrm{.}$$ In this setting, our local inverse theorem asserts that there is $\delta :=\mathsf{\text{exp}}(-{\epsilon }^{-O_{\mu }(1)})$ such that with probability at least $\delta$, a random restriction of $f$ down to $\delta n$ coordinates $\delta$-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 $\delta n$ coordinates is $\delta$-correlated with a product function with probability at least $\delta$, then $f$ is $2^{-\mathsf{\text{poly}}(\log (1\mathrm{/}\delta ))}$-correlated with a function of the form $L\cdot P$, where $L$ is a function of degree $\mathsf{\text{poly}}(1\mathrm{/}\delta )$, $\mathrm{\parallel }L{\mathrm{\parallel }}_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 $\mathrm{\Sigma }$ be a finite set and $S\subseteq \mathrm{\Sigma }\times \mathrm{\Sigma }\times \mathrm{\Sigma }$ 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 {\mathrm{\Sigma }}^n$ with $\mathrm{\mid }\mathrm{\Sigma }{\mathrm{\mid }}^{-n}\mathrm{\mid }A\mathrm{\mid }\ge \mathrm{\Omega }((\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.