On Inverse Theorems and Combinatorial Lines

The problem of studying k-wise correlations in product spaces, i.e., correlations of the form ${\mathbb{E}_{\left( {{x_1}, \ldots ,{x_k}} \right)\sim \mu \otimes n}}\left[ {{f_1}\left( {{x_1}} \right) \cdots f\left( {{x_k}} \right)} \right]$ where ${\text{ }}{f_i}:\sum\nolimits_i^n \to \mathbb{C}$ are all 1-bounded functions and µ is a distribution over Σ1× … × Σk, appears in many different contexts throughout discrete mathematics. Examples include additive combinatorics, extremal combinatorics, hardness of approximation and probability. The goal in an inverse theorem is to characterize the type of functions f1,…,fkthat achieve non-trivial correlations, under minimal assumptions on the distribution µ.We give new inverse theorems for k-wise correlations for all k ⩾ 3. For k = 3, our inverse theorem works for any distribution µ which is pairwise-connected, which is essentially the minimal assumption required for a nontrivial inverse theorem to hold. For k > 3, our inverse theorem applies for distributions µ satisfying the stronger condition of not having any Abelian embeddings. This resolves a conjecture from [Bhangale-Khot-Minzer, STOC 2022].We give applications of our inverse theorems to additive combinatorics, hardness of approximation, and property testing. First, we show that there exists c > 0 such that any set A ⊆ 0,1,2nwith density at least Ω((loglogloglogn)−c) must contain a combinatorial line, i.e., x,y,z ∈ 0,1,2n, not all equal, such that xi= yi= zior (xi,yi,zi) = (0,1,2) for all i = 1,2,…,n. In other words, we give "reasonable bounds" for the density Hales-Jewett theorem of length 3. This involves combining our inverse theorems with several additional insights, motivated by Shkredov’s proof of the corners theorem and Polymath’s combinatorial proof of the density Hales-Jewett theorem. Second, we show how to construct a dictatorship vs quasi-random test that has perfect completeness and soundness s + ε from integrality gap instances with similar parameters, provided that its local distributions have no Abelian embeddings. Third, we analyze the direct-sum tester of [Dinur-Golubev, RANDOM 2019] in the low-soundness regime.