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

Less than 1 year old · traced to

Let Σ\Sigma be a finite alphabet, let k∈Nk\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 ⁣:Σn→CP\colon\Sigma^n\to\mathbb{C} is a combinatorial degree-k′k' 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 ⁣:ΣT→CP_T\colon\Sigma^T\to\mathbb{C}. The combinatorial low-degree correlation conjecture. For every k∈Nk\in\mathbb{N} there exists k′∈Nk'\in\mathbb{N} such that, for every ε,α>0\varepsilon,\alpha>0, there are d∈Nd\in\mathbb{N} and δ>0\delta>0 with the following property: if f1,…,fk ⁣:Σn→Cf_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-k′k' function P ⁣:Σn→CP\colon\Sigma^n\to\mathbb{C} with 22-norm equal to 11, and a function L ⁣:Σn→CL\colon\Sigma^n\to\mathbb{C} with 22-norm equal to 11 and deg⁡(L)≤d{\sf \deg}(L)\leq d, such that

∣⟨f1,L⋅P⟩∣≥δ.\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 k≥4k\geq4 is open; this conjecture is presented as a natural and plausible answer in the Abelian-embedding case.

References

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.