The combinatorial low-degree correlation conjecture for pairwise-connected distributions

Let Σ\Sigma be a finite alphabet, let kNk\in\mathbb{N}, and let μ\mu be a pairwise-connected distribution over Σk\Sigma^k in which every atom has mass at least α\alpha. A function P ⁣:ΣnCP\colon\Sigma^n\to\mathbb{C} is a combinatorial degree-kk' function if it factors as

P(x)=T([n]k)PT(xT)P(x)=\prod_{T\in\binom{[n]}{k'}}P_T(x_T)

for suitable functions PT ⁣:ΣTCP_T\colon\Sigma^T\to\mathbb{C}. The combinatorial low-degree correlation conjecture. For every kNk\in\mathbb{N} there exists kNk'\in\mathbb{N} such that, for every ε,α>0\varepsilon,\alpha>0, there are dNd\in\mathbb{N} and δ>0\delta>0 with the following property: if f1,,fk ⁣:ΣnCf_1,\ldots,f_k\colon\Sigma^n\to\mathbb{C} are 11-bounded and

E(x1,,xk)μn[f1(x1)fk(xk)]ε,\left|\mathbb{E}_{(x_1,\ldots,x_k)\sim\mu^{\otimes n}}[f_1(x_1)\cdots f_k(x_k)]\right|\geq\varepsilon,

then there exist a combinatorial degree-kk' function P ⁣:ΣnCP\colon\Sigma^n\to\mathbb{C} with 22-norm equal to 11, and a function L ⁣:ΣnCL\colon\Sigma^n\to\mathbb{C} with 22-norm equal to 11 and deg(L)d{\sf \deg}(L)\leq d, such that

f1,LPδ.\left|\langle f_1,L\cdot P\rangle\right|\geq\delta.

The preceding results settle the corresponding question for arity three and for distributions with no Abelian embeddings, but the general case for k4k\geq4 is open; this conjecture is presented as a natural and plausible answer in the Abelian-embedding case.

Sources & referencesView supporting material

Primary source

Dor Minzer, “The Lens of Abelian Embeddings”, arXiv:2602.22183 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.