Talagrand-Type Correlation Inequalities for Submodular and Supermodular Functions on the Hypercube

Abstract

Talagran's correlation inequality provides quantitative lower bounds on the covariance of two increasing Boolean functions in terms of their coordinate influences, but, in general, a logarithmic loss is necessary. Motivated by a question of Kalai, Keller and Mossel, we identify a natural log-free regime. We prove that if two increasing Boolean functions on $\{0,1{\}}^n$ are either both submodular or both supermodular, then $$\mathbb{E}[fg]-\mathbb{E}[f]\mathbb{E}[g]\ge \frac{1}{4}\cdot \sum _{i=1}^n{\mathrm{Inf}}_i[f]{\mathrm{Inf}}_i[g],$$ where the constant $1/4$ is optimal. We also prove a real-valued extension: for two functions with the same second-difference sign, the covariance is bounded below by the sum of products of their Level-1 Fourier coefficients. As a consequence, we verify the Friedgut--Kahn--Kalai--Keller spectral conjecture in this structured setting. The proofs combine a heat-semigroup representation based on second-order discrete derivatives with an independent induction argument for the Boolean case.

20 pages