2024/11/22 by Amey Bhangale, Bhangale, Amey, Subhash Khot +5 · 2 citations
Computer Science · #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.2411.15133
We prove local and global inverse theorems for general 3-wise correlations over pairwise-connected distributions. Let μ be a distribution over Σ× Γ× Φ such that the supports of μxy, μxz, and μyz are all connected, and let f: Σn → ℂ, g: Γn → ℂ, h: Φn → ℂ be 1-bounded functions satisfying |𝔼(x,y,z) ∼ μ⊗ n[f(x)g(y)h(z)]| ≥ ε. In this setting, our local inverse theorem asserts that there is δ:=\textsfexp(-ε-Oμ(1)) such that with probability at least δ, a random restriction of f down to δn coordinates δ-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 δn coordinates is δ-correlated with a product function with probability at least δ, then f is 2^-\textsfpoly(log(1/δ))-correlated with a function of the form L⋅ P, where L is a function of degree \textsfpoly(1/δ), ‖L‖2≤ 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 Σ be a finite set and S ⊆ Σ× Σ× Σ such that: (1) (x, x, x) ∈ S for all x ∈ S, and (2) the supports of Sxy, Sxz, and Syz are all connected. Then, any set A ⊆ Σn with |Σ|-n|A| ≥ Ω((log log log n)-c) contains x, y, z ∈ A, not all equal, such that (xi,yi,zi) ∈ S for all i. This gives the first reasonable bounds for the restricted 3-AP problem over finite fields.