The sharp diagonal spectral correlation inequality on the discrete cube
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
Abstract
We prove the sharp diagonal spectral correlation conjecture of Friedgut, Kahn, Kalai and Keller, proposed in their Fourier-analytic approach to Chvátal's conjecture. For every pair of increasing Boolean functions $f,g:\{0,1\}^n\to\{0,1\}$, $$\mathrm{Cov}(f,g)\ge4\sum_{\varnothing\ne S\subseteq[n]}|S|\hat{f}(S)^2\hat{g}(S)^2.$$ Thus covariance controls the degree-weighted collision of the two nonconstant Fourier spectra, giving a sharp Fourier strengthening of the Harris--Kleitman inequality. The theorem also implies the unweighted diagonal conjecture of Friedgut--Kahn--Kalai--Keller for an increasing family and a maximal intersecting family.
The factor $4$ is optimal, and we determine all equality cases. Apart from pairs whose relevant coordinate sets are disjoint, equality occurs only for a common dictatorship and, up to relabelling coordinates and interchanging $f$ and $g$, for the two-coordinate AND-OR pair $(f,g)=(x_i x_j,\,x_i\vee x_j).$
The main novelty is a correlated four-restriction induction and a sharp endpoint convolution inequality. The usual two-restriction induction behind Harris--Kleitman sees only the parallel restricted pairs and loses the mixed Fourier information needed to control the degree-weighted diagonal spectral energy. We instead couple the four codimension-one restricted pairs with correlation $1/2$; this precise correlation extracts the missing degree-weighted energy as a nonnegative square.