pith. sign in

arxiv: 2510.22307 · v2 · pith:5VFNKG57new · submitted 2025-10-25 · 🧮 math.CO · math.FA· math.PR

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

Fan Chang , Yu Chen This is my paper

Pith reviewed 2026-05-21 21:04 UTC · model grok-4.3

classification 🧮 math.CO math.FAmath.PR
keywords correlation inequalitiessubmodular functionssupermodular functionsBoolean functionsinfluencesFourier analysishypercubeTalagrand inequality
0
0 comments X

The pith

Two increasing submodular or supermodular Boolean functions have covariance at least one-fourth the sum of their influence products.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a correlation inequality without logarithmic loss for pairs of increasing Boolean functions that are both submodular or both supermodular. It proves that their covariance is at least one-fourth the sum of the products of their coordinate influences, and shows that this constant is the best possible. This structured case avoids the log factor required in the general Talagrand inequality. The result extends to real-valued functions sharing the sign of second differences, bounding covariance by the sum of products of level-one Fourier coefficients, and confirms a spectral conjecture under these conditions.

Core claim

If two increasing Boolean functions on {0,1}^n are either both submodular or both supermodular, then E[fg] - E[f]E[g] is at least (1/4) times sum_i Inf_i[f] Inf_i[g], with the constant 1/4 optimal. For real-valued functions with the same sign of second differences, the covariance is at least the sum of products of their level-1 Fourier coefficients. The proofs rely on a heat-semigroup representation based on second-order discrete derivatives together with an induction argument.

What carries the argument

Heat-semigroup representation based on second-order discrete derivatives, used with induction to derive the bound on the hypercube.

If this is right

  • The constant 1/4 is optimal and cannot be replaced by any larger number for this class of functions.
  • The Friedgut-Kahn-Kalai-Keller spectral conjecture holds when restricted to submodular or supermodular functions.
  • Real-valued functions with matching second-difference signs satisfy the covariance lower bound by level-1 Fourier coefficients.
  • The inequality provides quantitative control without logarithmic factors for these structured monotone functions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The bound may simplify analysis of optimization or sampling problems that involve submodular or supermodular set functions.
  • The second-difference sign condition could be used to obtain similar log-free inequalities on other product spaces or lattices.

Load-bearing premise

The two functions must both be submodular or both supermodular, sharing the same sign for their second differences.

What would settle it

A pair of increasing submodular functions on the hypercube where the covariance is strictly less than one-fourth the sum of the products of their influences.

read the original 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\limits_{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript proves a log-free Talagrand-type correlation inequality: if two increasing Boolean functions f,g on {0,1}^n are both submodular or both supermodular, then E[fg]−E[f]E[g] ≥ (1/4) ∑_i Inf_i[f] Inf_i[g], with the constant 1/4 shown to be optimal. It also establishes a real-valued extension bounding covariance from below by the sum of products of level-1 Fourier coefficients for functions sharing the same second-difference sign, and verifies 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.

Significance. If correct, the result identifies a natural regime in which the usual logarithmic loss in Talagrand-type inequalities can be removed, directly addressing a question of Kalai, Keller and Mossel. The optimality of the constant 1/4 and the verification of the spectral conjecture for this class of functions are concrete strengths. The semigroup-plus-induction approach provides a clean structural explanation tied to the sign of second differences.

major comments (1)
  1. Induction argument (Boolean case): the proof must explicitly verify that conditioning on a coordinate preserves both the increasing property and the uniform sign of all second differences (submodularity or supermodularity) on the two slices, and must relate the full-space covariance and influences to the slice quantities without introducing an error term or measure-dependent factor that would degrade the 1/4 constant. The abstract states that the induction is 'independent,' but if the relation between E[fg] and the conditional expectations on the slices is not controlled tightly (e.g., via an exact decomposition or coupling), the claimed bound may fail to close.
minor comments (2)
  1. Abstract: the sentence describing the real-valued extension could explicitly state the precise Fourier-level bound (sum of products of level-1 coefficients) rather than leaving it implicit.
  2. Notation: ensure that the second-order discrete derivative operator used in the heat-semigroup representation is defined with a consistent sign convention before it is invoked in the main argument.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the specific suggestion to strengthen the presentation of the induction argument. We address the point directly below and will revise the manuscript to incorporate the requested explicit verifications.

read point-by-point responses

  1. Referee: Induction argument (Boolean case): the proof must explicitly verify that conditioning on a coordinate preserves both the increasing property and the uniform sign of all second differences (submodularity or supermodularity) on the two slices, and must relate the full-space covariance and influences to the slice quantities without introducing an error term or measure-dependent factor that would degrade the 1/4 constant. The abstract states that the induction is 'independent,' but if the relation between E[fg] and the conditional expectations on the slices is not controlled tightly (e.g., via an exact decomposition or coupling), the claimed bound may fail to close.

    Authors: We agree that explicit verification improves clarity. In the revised manuscript we will add a short preliminary lemma establishing that if f is increasing and submodular (respectively supermodular), then for any coordinate i and any fixed value b in {0,1} the restriction of f to the slice x_i = b remains increasing and submodular (respectively supermodular) on the (n-1)-dimensional subcube; the same holds for g. This follows immediately from the definitions of monotonicity and the sign of all second differences, which are inherited on faces of the hypercube. For the quantitative relation we employ the exact law-of-total-covariance decomposition Cov(f,g) = E[Cov(f,g | x_i)] + Cov(E[f|x_i], E[g|x_i]) together with the corresponding exact identities for the influences (Inf_i[f] equals half the variance of the conditional expectation, with no scaling loss under the uniform measure). Applying the induction hypothesis to the conditional expectations on each slice and summing over coordinates therefore closes the argument with the constant 1/4 preserved exactly and without measure-dependent factors. The induction is independent of the heat-semigroup argument used for the real-valued extension; we will clarify this separation in the text. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation uses structural assumption and independent induction

full rationale

The paper establishes the stated correlation inequality directly from the shared second-difference sign (submodularity or supermodularity) via a heat-semigroup representation on second-order discrete derivatives, followed by a separate induction on the Boolean hypercube. The abstract describes the induction as independent, and the provided text contains no self-citations that bear the central load, no fitted parameters renamed as predictions, and no reduction of the 1/4 constant or the covariance bound to the inputs by definition. The result is therefore self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard definitions of submodularity and supermodularity via second differences on the hypercube, together with properties of the discrete heat semigroup; these are domain assumptions rather than new postulates.

axioms (2)
  • domain assumption Submodular and supermodular functions are defined by the sign of their second discrete differences being non-positive or non-negative respectively.
    This classification is invoked to obtain the log-free regime and is stated as the key structural hypothesis.
  • standard math The heat semigroup on the hypercube admits a representation in terms of second-order discrete derivatives.
    Used as the basis for the covariance lower bound in the proof sketch.

pith-pipeline@v0.9.0 · 5740 in / 1599 out tokens · 63860 ms · 2026-05-21T21:04:39.616994+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    W. Beckner. Inequalities in Fourier analysis.Ann. of Math. (2), 102(1):159–182, 1975

    work page 1975

  2. [2]

    A. Bonami. ´Etude des coefficients de Fourier des fonctions de LppGq.Ann. Inst. Fourier (Grenoble), 20(fasc. 2):335–402 (1971), 1970

    work page 1971

  3. [3]

    C. Borell. Positivity improving operators and hypercontractivity.Math. Z., 180(2):225–234, 1982

    work page 1982

  4. [4]

    Cheraghchi, A

    M. Cheraghchi, A. Klivans, P. Kothari, and H. K. Lee. Submodular functions are noise stable. InProceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1586–1592. ACM, New York, 2012

    work page 2012

  5. [5]

    Chv´ atal

    V. Chv´ atal. Intersecting families of edges in hypergraphs having the hereditary property. InHypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), Lecture Notes in Math., Vol. 411, pages 61–66. Springer, Berlin-New York, 1974

    work page 1972

  6. [6]

    R. Eldan. Second-order bounds on correlations between increasing families.Combinatorica, 42(suppl. 1):1099–1118, 2022

    work page 2022

  7. [7]

    Feldman, P

    V. Feldman, P. Kothari, and J. Vondr´ ak. Representation, approximation and learning of submodular functions using low-rank decision trees. InConference on Learning Theory, pages 711–740. PMLR, 2013

    work page 2013

  8. [8]

    Feldman, P

    V. Feldman, P. Kothari, and J. Vondr´ ak. Tight bounds onℓ1 approximation and learning of self-bounding functions.Theoret. Comput. Sci., 808:86–98, 2020

    work page 2020

  9. [9]

    Feldman and J

    V. Feldman and J. Vondr´ ak. Tight bounds on low-degree spectral concentration of submodular and XOS functions. In2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, pages 923–942. IEEE Computer Soc., Los Alamitos, CA, 2015

    work page 2015

  10. [10]

    Feldman and J

    V. Feldman and J. Vondr´ ak. Optimal bounds on approximation of submodular and XOS functions by juntas.SIAM J. Comput., 45(3):1129–1170, 2016

    work page 2016

  11. [11]

    Friedgut, J

    E. Friedgut, J. Kahn, G. Kalai, and N. Keller. Chv´ atal’s conjecture and correlation inequalities. J. Combin. Theory Ser. A, 156:22–43, 2018

    work page 2018

  12. [12]

    Gupta, M

    A. Gupta, M. Hardt, A. Roth, and J. Ullman. Privately releasing conjunctions and the statistical query barrier.SIAM J. Comput., 42(4):1494–1520, 2013

    work page 2013

  13. [13]

    T. E. Harris. A lower bound for the critical probability in a certain percolation process.Proc. Cambridge Philos. Soc., 56:13–20, 1960

    work page 1960

  14. [14]

    Kalai, N

    G. Kalai, N. Keller, and E. Mossel. On the correlation of increasing families.J. Combin. Theory Ser. A, 144:250–276, 2016

    work page 2016

  15. [15]

    N. Keller. Lower bound on the correlation between monotone families in the average case. Adv. in Appl. Math., 43(1):31–45, 2009

    work page 2009

  16. [16]

    Keller and O

    N. Keller and O. Klein. Biased halfspaces, noise sensitivity, and local Chernoff inequalities. Discrete Anal., pages Paper No. 13, 50, 2019

    work page 2019

  17. [17]

    Keller, E

    N. Keller, E. Mossel, and A. Sen. Geometric influences II: correlation inequalities and noise sensitivity.Ann. Inst. Henri Poincar´ e Probab. Stat., 50(4):1121–1139, 2014

    work page 2014

  18. [18]

    D. J. Kleitman. Families of non-disjoint subsets.J. Combinatorial Theory, 1:153–155, 1966. 17

    work page 1966

  19. [19]

    E. Mossel. Probabilistic aspects of voting, intransitivity and manipulation.arXiv preprint arXiv:2012.10352, 2020

    work page arXiv 2012

  20. [20]

    Mossel, R

    E. Mossel, R. O’Donnell, O. Regev, J. E. Steif, and B. Sudakov. Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality.Israel J. Math., 154:299–336, 2006

    work page 2006

  21. [21]

    Oleszkiewicz

    K. Oleszkiewicz. Boolean functions with small second-order influences on the discrete cube. InHigh dimensional probability IX—the ethereal volume, volume 80 ofProgr. Probab., pages 155–166. Birkh¨ auser/Springer, Cham, [2023]©2023

    work page 2023

  22. [22]

    Przybylowski

    T. Przyby lowski. KKL theorem for the influence of a set of variables.arXiv preprint arXiv:2404.00084, 2024

    work page arXiv 2024

  23. [23]

    Talagrand

    M. Talagrand. On russo’s approximate zero-one law.The Annals of Probability, pages 1576–1587, 1994

    work page 1994

  24. [24]

    Talagrand

    M. Talagrand. How much are increasing sets positively correlated?Combinatorica, 16(2):243– 258, 1996

    work page 1996

  25. [25]

    K. Tanguy. Talagrand inequality at second order and application to Boolean analysis.J. Theoret. Probab., 33(2):692–714, 2020. 18

    work page 2020