A spectral correlation inequality for increasing Boolean functions

Fan Chang

arxiv: 2606.08958 · v1 · pith:C6LO6JBLnew · submitted 2026-06-08 · 🧮 math.CO · math.PR

A spectral correlation inequality for increasing Boolean functions

Fan Chang This is my paper

Pith reviewed 2026-06-27 16:41 UTC · model grok-4.3

classification 🧮 math.CO math.PR

keywords Boolean functionsFourier analysiscorrelation inequalityincreasing functionscovariancenoise operatorTalagrand inequality

0 comments

The pith

Increasing Boolean functions satisfy Cov(f,g) ≥ 2 ∑_{S≠∅} |S| ˆf(S)^2 ˆg(S)^2

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

The paper proves that the covariance between any two increasing Boolean functions is bounded from below by twice a sum over their Fourier coefficients weighted by set size. This spectral lower bound strengthens Talagrand's correlation inequality and addresses a conjecture of Friedgut, Kahn, Kalai, and Keller. The argument combines the reverse Bonami-Beckner inequality with Young's convolution inequality. A companion pointwise inequality for the noise operator is established and integrated to obtain a modestly stronger constant factor.

Core claim

For all increasing Boolean functions f and g from the hypercube to {0,1}, Cov(f,g) ≥ 2 ∑_{S≠∅} |S| ˆf(S)^2 ˆg(S)^2. The proof proceeds by applying the reverse Bonami-Beckner inequality to the pair of increasing functions and then invoking Young's inequality. The paper also determines the exact optimal constant c_ρ,n in the pointwise inequality ⟨f, T_ρ g⟩ ≥ c_ρ,n ‖f * g‖_2^2, which equals 1 for ρ ≤ 1/2, (2(1-ρ))^n for 1/2 < ρ < 1, and 0 at ρ=1; integrating this yields the improved factor 4(n+1)/(2n).

What carries the argument

Reverse Bonami-Beckner inequality applied to increasing functions, combined with Young's convolution inequality to produce the spectral lower bound on covariance.

Load-bearing premise

The reverse Bonami-Beckner inequality applies directly to pairs of increasing functions in the form required for the spectral bound.

What would settle it

An explicit pair of increasing functions f and g on {0,1}^n for which the computed covariance falls below twice the indicated spectral sum would disprove the inequality.

read the original abstract

Talagrand's correlation inequality provides a quantitative strengthening of the Harris--Kleitman inequality for increasing Boolean functions. Motivated by a Fourier-analytic conjecture of Friedgut, Kahn, Kalai, and Keller, we prove that $$ \mathrm{Cov}(f,g)\ge 2\sum_{S\neq\emptyset}|S|\hat f(S)^2\hat g(S)^2 $$ holds for all increasing Boolean functions $f,g:\{0,1\}^n\to\{0,1\}$. The proof combines the reverse Bonami--Beckner inequality with Young's convolution inequality. We also establish a sharp pointwise inequality: for every $n\ge1$, every $0\le\rho\le1$, and every $f,g:\{0,1\}^n\to[0,1]$, the optimal constant $c_{\rho,n}$ for which $$ \left\langle f,T_\rho g \right\rangle\ge c_{\rho,n}\|f*g\|_2^2 $$ holds for all such $f,g$ is $1$ for $0\le\rho\le1/2$, $(2(1-\rho))^n$ for $1/2<\rho<1$, and $0$ for $\rho=1$. Integrating this pointwise inequality yields, for $n\ge1$, the slightly improved bound $$ \mathrm{Cov}(f,g)\ge 4\cdot\frac{n+1}{2n}\sum_{S\neq\emptyset}|S|\hat f(S)^2\hat g(S)^2. $$

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.

Desk Editor's Note private letter to a colleague

The paper gives a new |S|-weighted spectral lower bound on covariance for increasing Boolean functions via reverse Bonami-Beckner plus Young, plus a separate pointwise inequality with explicit optimal constants.

read the letter

The main takeaway is a concrete Fourier lower bound: Cov(f,g) is at least twice the sum over nonempty S of |S| times f-hat(S)^2 g-hat(S)^2, for increasing f and g. They also get a slightly stronger version with a factor of 4(n+1)/(2n) by first proving a pointwise inequality on the noise inner product.

What is new is the explicit |S| weight in the spectral sum, motivated by the Friedgut-Kahn-Kalai-Keller conjecture. The argument stays within standard tools: reverse Bonami-Beckner on the pair followed by Young's convolution inequality, plus the pointwise result that pins down the best constant c_rho,n for the inequality involving ||f * g||_2^2. The pointwise part looks clean and holds for general [0,1]-valued functions, not just increasing ones.

The soft spot is exactly the step the stress-test flags. Reverse Bonami-Beckner gives a lower bound on a noise inner product, but turning that into the precise quadratic form with the |S| factor and the leading 2 requires the convolution term from Young to line up exactly with the desired spectral expression. The increasing assumption only supplies non-negativity; it is not clear from the abstract whether extra structure on the supports or signs is needed for the pair (f,g). If that alignment holds without hidden steps, the bound is fine. If not, the constant 2 might need work. The improved constant from the pointwise inequality is minor and does not change the picture.

This is for people working in Boolean analysis or discrete Fourier methods who care about quantitative correlation inequalities. It is a short, self-contained argument from known inequalities, so it deserves a serious referee even if the main derivation needs a close look at the convolution step.

Referee Report

0 major / 1 minor

Summary. The paper proves that Cov(f,g) ≥ 2 ∑_{S≠∅} |S| ˆf(S)^2 ˆg(S)^2 for all increasing Boolean functions f,g : {0,1}^n → {0,1}. The proof combines the reverse Bonami-Beckner inequality with Young's convolution inequality. It also establishes the sharp pointwise inequality ⟨f, T_ρ g⟩ ≥ c_{ρ,n} ||f*g||_2^2 for f,g : {0,1}^n → [0,1], where c_{ρ,n} equals 1 for 0≤ρ≤1/2, (2(1-ρ))^n for 1/2<ρ<1, and 0 for ρ=1; integrating this yields the improved bound Cov(f,g) ≥ 4·(n+1)/(2n) ∑_{S≠∅} |S| ˆf(S)^2 ˆg(S)^2.

Significance. If the central inequality holds, the result supplies a Fourier-analytic strengthening of Talagrand's correlation inequality and resolves a conjecture of Friedgut-Kahn-Kalai-Keller in the monotone setting. The sharpness of the pointwise inequality (optimal in each ρ regime) is a clear strength, as is the explicit integration to a slightly better constant. The reliance on standard external tools (reverse Bonami-Beckner and Young) rather than ad-hoc constructions is also a positive feature.

minor comments (1)

The abstract states the main inequality for range {0,1} but the pointwise inequality is stated for [0,1]-valued functions; a brief remark clarifying whether the main proof extends verbatim to the [0,1] case would aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the recognition of the sharpness of the pointwise inequality and the explicit integration yielding the improved constant, and for recommending acceptance.

Circularity Check

0 steps flagged

No circularity; derivation relies on external inequalities without self-reference or reduction to inputs

full rationale

The central claim is obtained by combining the reverse Bonami-Beckner inequality with Young's convolution inequality, both standard external tools. The increasing assumption ensures non-negativity of f and g but does not create a self-definitional loop or fitted prediction. The pointwise inequality is separately established and integrated to yield a slight improvement, but neither step reduces by construction to the target spectral form. No self-citations appear in the load-bearing steps, and the derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard properties of Fourier analysis on the hypercube and monotonicity of Boolean functions; no free parameters or invented entities are introduced.

axioms (2)

standard math Fourier analysis decomposes Boolean functions into Walsh-Fourier basis with the usual inner product and Parseval identity.
Invoked implicitly when writing Cov(f,g) and the sum over Fourier coefficients.
standard math The reverse Bonami-Beckner inequality and Young's convolution inequality hold in the stated forms for functions on the hypercube.
These are the two tools combined in the proof.

pith-pipeline@v0.9.1-grok · 5792 in / 1382 out tokens · 20712 ms · 2026-06-27T16:41:29.595619+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

The sharp diagonal spectral correlation inequality on the discrete cube
math.CO 2026-06 unverdicted novelty 8.0

Proves Cov(f,g) ≥ 4 ∑_{∅≠S} |S| ˆf(S)^2 ˆg(S)^2 for increasing Boolean f,g on {0,1}^n, with the factor 4 sharp and all equality cases determined.

Reference graph

Works this paper leans on

14 extracted references · 1 linked inside Pith · cited by 1 Pith paper

[1]

Inequalities in Fourier analysis.Ann

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

1975
[2]

Optimal Young’s convolu- tions inequality and its reverse form on the hypercube.arXiv preprint arXiv:2507.06115, 2025

David Beltran, Paata Ivanisvili, Jos´ e Madrid, and Lekha Patil. Optimal Young’s convolu- tions inequality and its reverse form on the hypercube.arXiv preprint arXiv:2507.06115, 2025

arXiv 2025
[3]

´Etude des coefficients de Fourier des fonctions deL p(G).Ann

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

1971
[4]

Talagrand-type correlation inequalities for submodular and supermodular functions on the hypercube.arXiv preprint arXiv:2510.22307, 2025

Fan Chang and Yu Chen. Talagrand-type correlation inequalities for submodular and supermodular functions on the hypercube.arXiv preprint arXiv:2510.22307, 2025

Pith/arXiv arXiv 2025
[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

1972
[6]

Chv´ atal’s conjecture and corre- lation inequalities.J

Ehud Friedgut, Jeff Kahn, Gil Kalai, and Nathan Keller. Chv´ atal’s conjecture and corre- lation inequalities.J. Combin. Theory Ser. A, 156:22–43, 2018

2018
[7]

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

1960
[8]

On the correlation of increasing families

Gil Kalai, Nathan Keller, and Elchanan Mossel. On the correlation of increasing families. J. Combin. Theory Ser. A, 144:250–276, 2016

2016
[9]

Lower bound on the correlation between monotone families in the average case.Adv

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

2009
[10]

Biased halfspaces, noise sensitivity, and local Chernoff inequalities.Discrete Anal., 2019

Nathan Keller and Ohad Klein. Biased halfspaces, noise sensitivity, and local Chernoff inequalities.Discrete Anal., 2019. Paper No. 13, 50 pp

2019
[11]

Geometric influences II: correlation inequalities and noise sensitivity.Ann

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

2014
[12]

Kleitman

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

1966
[13]

Cambridge University Press, New York, 2014

Ryan O’Donnell.Analysis of Boolean functions. Cambridge University Press, New York, 2014

2014
[14]

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

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

1996

[1] [1]

Inequalities in Fourier analysis.Ann

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

1975

[2] [2]

Optimal Young’s convolu- tions inequality and its reverse form on the hypercube.arXiv preprint arXiv:2507.06115, 2025

David Beltran, Paata Ivanisvili, Jos´ e Madrid, and Lekha Patil. Optimal Young’s convolu- tions inequality and its reverse form on the hypercube.arXiv preprint arXiv:2507.06115, 2025

arXiv 2025

[3] [3]

´Etude des coefficients de Fourier des fonctions deL p(G).Ann

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

1971

[4] [4]

Talagrand-type correlation inequalities for submodular and supermodular functions on the hypercube.arXiv preprint arXiv:2510.22307, 2025

Fan Chang and Yu Chen. Talagrand-type correlation inequalities for submodular and supermodular functions on the hypercube.arXiv preprint arXiv:2510.22307, 2025

Pith/arXiv arXiv 2025

[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

1972

[6] [6]

Chv´ atal’s conjecture and corre- lation inequalities.J

Ehud Friedgut, Jeff Kahn, Gil Kalai, and Nathan Keller. Chv´ atal’s conjecture and corre- lation inequalities.J. Combin. Theory Ser. A, 156:22–43, 2018

2018

[7] [7]

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

1960

[8] [8]

On the correlation of increasing families

Gil Kalai, Nathan Keller, and Elchanan Mossel. On the correlation of increasing families. J. Combin. Theory Ser. A, 144:250–276, 2016

2016

[9] [9]

Lower bound on the correlation between monotone families in the average case.Adv

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

2009

[10] [10]

Biased halfspaces, noise sensitivity, and local Chernoff inequalities.Discrete Anal., 2019

Nathan Keller and Ohad Klein. Biased halfspaces, noise sensitivity, and local Chernoff inequalities.Discrete Anal., 2019. Paper No. 13, 50 pp

2019

[11] [11]

Geometric influences II: correlation inequalities and noise sensitivity.Ann

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

2014

[12] [12]

Kleitman

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

1966

[13] [13]

Cambridge University Press, New York, 2014

Ryan O’Donnell.Analysis of Boolean functions. Cambridge University Press, New York, 2014

2014

[14] [14]

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

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

1996