On approximability of satisfiable k -CSPs: II

Let Σ be an alphabet and μ be a distribution on Σ ᵏ for some k 2 . Let α > 0 be the minimum probability of a tuple in the support of μ (denoted supp(μ ) ). We treat the parameters Σ , k, μ , α as fixed and constant. We say that the distribution μ has a linear embedding if there exist an Abelian group G (with the identity element 0G ) and mappings σ ᵢ : Σ → G , 1 i k , such that at least one of the mappings is non-constant and for every (a₁, a₂, … , aₖ)∈ supp(μ ) , ∑ ᵢ₌₁ᵏ σ ᵢ(aᵢ) = 0G . In [Bhangale-Khot-Minzer, STOC 2022], the authors asked the following analytical question. Let fᵢ: Σ ⁿ→ [\!-1,1] be bounded functions, such that at least one of the functions fᵢ essentially has degree at least d , meaning that the Fourier mass of fᵢ on terms of degree less than d is at most δ . If μ has no linear embedding (over any Abelian group), then is it necessarily the case that {equation*} | {E}_{({x}_1, {x}_2, … , {x}_k)~ μ ⊗ n}[f_1({x}_1)f_2({x}_2)⋯ f_k({x}_k)] | = od, δ(1),{equation*} where the right hand side → 0 as the degree d → ∞ and δ → 0 ? In this paper, we answer this analytical question fully and in the affirmative for $k=3$ . We also show the following two applications of the result. 1. The first application is related to hardness of approximation. Using the reduction from [5], we show that for every $3$ -ary predicate P:Σ ³ → \0,1\ such that P has no linear embedding, an SDP (semi-definite programming) integrality gap instance of a P -Constraint Satisfaction Problem (CSP) instance with gap $(1,s)$ can be translated into a dictatorship test with completeness $1$ and soundness $s+o(1)$ , under certain additional conditions on the instance. 2. The second application is related to additive combinatorics. We show that if the distribution μ on Σ ³ has no linear embedding, marginals of μ are uniform on Σ , and (a,a,a)∈ supp(μ ) for every a∈ Σ , then every large enough subset of Σ ⁿ contains a triple (x₁, x₂,x₃) from μ ⊗ n (and in fact a significant density of such triples).