pith. sign in

arxiv: 2606.32024 · v1 · pith:U3FGTW3Unew · submitted 2026-06-30 · 🧮 math.CO · math.FA· math.PR

The sharp diagonal spectral correlation inequality on the discrete cube

Fan Chang , Hong Liu , Miao Liu This is my paper

Pith reviewed 2026-07-01 04:14 UTC · model grok-4.3

classification 🧮 math.CO math.FAmath.PR
keywords increasing Boolean functionsFourier analysiscovarianceHarris-Kleitman inequalityspectral correlationChvátal conjectureequality cases
0
0 comments X

The pith

Covariance of any two increasing Boolean functions is bounded below by four times their degree-weighted Fourier collision sum.

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

The paper proves that for increasing functions f and g from the discrete cube to {0,1}, their covariance is at least four times the sum over nonempty subsets S of |S| times the square of the product of the Fourier coefficients of f and g at S. This gives a sharp quantitative version of the Harris-Kleitman inequality that tracks how the non-constant Fourier mass of the two functions overlaps, weighted by degree. The result also settles the unweighted diagonal spectral conjecture in the special case of an increasing family paired with a maximal intersecting family. The proof introduces a new induction that couples four codimension-one restrictions at correlation exactly one-half.

Core claim

For every pair of increasing Boolean functions f,g:{0,1}^n→{0,1}, Cov(f,g)≥4∑_{∅≠S⊆[n]}|S|ˆf(S)^2ˆg(S)^2. The constant 4 is optimal. Equality holds precisely when the relevant coordinate sets of f and g are disjoint, when f and g are the same dictatorship, or (up to coordinate relabeling and swapping f with g) when the pair is (x_i x_j, x_i ∨ x_j).

What carries the argument

Correlated four-restriction induction that couples the four codimension-one restrictions of each function with pairwise correlation 1/2, turning the missing mixed Fourier terms into a nonnegative square.

If this is right

  • The inequality implies the unweighted diagonal spectral conjecture of Friedgut-Kahn-Kalai-Keller when one function is the indicator of a maximal intersecting family.
  • The factor 4 cannot be improved, as shown by the equality cases.
  • The result strengthens the classical Harris-Kleitman inequality by controlling the precise overlap of the two Fourier spectra.

Where Pith is reading between the lines

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

  • The same coupling technique might apply directly to correlation inequalities for monotone functions on other product spaces with different marginal measures.
  • One could check whether the four-restriction induction yields analogous sharp bounds when the functions take values in a larger range rather than {0,1}.

Load-bearing premise

The four codimension-one restrictions can be coupled with exact correlation 1/2 so that the mixed Fourier information appears as a nonnegative square in the induction step.

What would settle it

A concrete pair of increasing functions on the cube for which the covariance is strictly smaller than four times the degree-weighted sum of squared Fourier coefficient products, or an equality case outside the three families listed in the theorem.

read the original abstract

We prove the sharp diagonal spectral correlation conjecture of Friedgut, Kahn, Kalai and Keller, proposed in their Fourier-analytic approach to Chv\'atal'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.

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

0 major / 2 minor

Summary. The paper proves the sharp diagonal spectral correlation conjecture: for every pair of increasing Boolean functions f,g:{0,1}^n→{0,1}, Cov(f,g)≥4∑_{∅≠S⊆[n]}|S|ˆf(S)^2ˆg(S)^2. The factor 4 is optimal; equality holds precisely when the relevant coordinate sets are disjoint, when f and g are common dictatorships, or (up to relabeling and swapping) for the pair (x_i x_j, x_i ∨ x_j). The proof proceeds by a correlated four-restriction induction that couples the four codimension-one restrictions at exact correlation 1/2, allowing the mixed Fourier terms to appear as a nonnegative square, together with a sharp endpoint convolution inequality. The result strengthens the Harris–Kleitman inequality and implies the unweighted diagonal conjecture for an increasing family and a maximal intersecting family.

Significance. If correct, the theorem supplies the sharp Fourier-analytic strengthening of Harris–Kleitman that was conjectured by Friedgut–Kahn–Kalai–Keller, with explicit equality cases and an optimal constant. The new induction technique, which preserves monotonicity while extracting degree-weighted spectral energy, is likely to be reusable in other Boolean-analysis settings. The manuscript provides a complete, self-contained proof together with a classification of equality cases.

minor comments (2)
  1. The abstract states the inequality with the sum restricted to nonempty S; confirm that the S=∅ term is omitted consistently in all displayed statements and in the induction step (e.g., §3).
  2. Notation for the four codimension-one restrictions (f_{0,0}, f_{0,1}, …) should be introduced once with a single displayed equation rather than re-defined inline in the induction paragraph.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading, accurate summary of the main results, and positive recommendation to accept the manuscript. We are pleased that the report highlights the strengthening of the Harris–Kleitman inequality, the classification of equality cases, and the potential reusability of the correlated four-restriction technique.

Circularity Check

0 steps flagged

No significant circularity; direct inductive proof of external conjecture

full rationale

The derivation consists of a correlated four-restriction induction that couples codimension-one restrictions at exact correlation 1/2, allowing cross terms to appear as a nonnegative square while preserving monotonicity. This is presented as a self-contained mathematical argument establishing the inequality directly from the definitions of covariance and Fourier coefficients on the cube. No parameter is fitted to data and then renamed as a prediction; no load-bearing step reduces to a self-citation whose content is itself unverified; the cited conjecture originates from independent prior work (Friedgut-Kahn-Kalai-Keller); equality cases are classified by explicit case analysis rather than by construction. The endpoint convolution inequality is stated as sharp but derived within the induction closure. The paper is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the standard Fourier basis for the hypercube and the domain assumption that the functions are monotone; no free parameters or new entities are introduced in the abstract.

axioms (2)
  • standard math The Fourier-Walsh expansion of Boolean functions on the hypercube is orthonormal and complete
    Invoked implicitly when writing Cov in terms of Fourier coefficients
  • domain assumption f and g are increasing (monotone non-decreasing)
    Required for the statement and for the induction to preserve the relevant sign properties

pith-pipeline@v0.9.1-grok · 5811 in / 1509 out tokens · 51053 ms · 2026-07-01T04:14:59.659602+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

28 extracted references · 3 canonical work pages · 2 internal anchors

  1. [1]

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

    1975

  2. [2]

    Beltran, P

    D. Beltran, P. Ivanisvili, J. Madrid, and L. Patil. Optimal Young’s convolutions inequality and its reverse form on the hypercube.arXiv preprint arXiv:2507.06115, 2025

    work page arXiv 2025

  3. [3]

    Benjamini, G

    I. Benjamini, G. Kalai, and O. Schramm. Noise sensitivity of Boolean functions and applications to percolation.Inst. Hautes ´Etudes Sci. Publ. Math., 90:5–43 (2001), 1999

    2001

  4. [4]

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

    1971

  5. [5]

    F. Chang. A spectral correlation inequality for increasing Boolean functions.arXiv preprint arXiv:2606.08958, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  6. [6]

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

    F. Chang and Y. Chen. Talagrand-Type Correlation Inequalities for Submodular and Supermodular Functions on the Hypercube.arXiv preprint arXiv:2510.22307, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  7. [7]

    Chv´ atal

    V. Chv´ atal. Intersecting families of edges in hypergraphs having the hereditary property. In Hypergraph 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

  8. [8]

    A. De, S. Nadimpalli, and R. A. Servedio. Quantitative correlation inequalities via extremal power series.Probab. Theory Related Fields, 183(1-2):649–675, 2022

    2022

  9. [9]

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

    2022

  10. [10]

    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. 15

    2018

  11. [11]

    Galicza and G

    P. Galicza and G. Pete. Sparse reconstruction in spin systems. I: iid spins.Israel J. Math., 262(1):43–96, 2024

    2024

  12. [12]

    Galicza and G

    P. Galicza and G. Pete. Sparse reconstruction in spin systems II: Ising and other factor of IID measures.Probab. Theory Related Fields, pages 1–96, 2025

    2025

  13. [13]

    Garban, G

    C. Garban, G. Pete, and O. Schramm. The Fourier spectrum of critical percolation.Acta Math., 205(1):19–104, 2010

    2010

  14. [14]

    Garban and J

    C. Garban and J. E. Steif.Noise sensitivity of Boolean functions and percolation, volume 5 of Institute of Mathematical Statistics Textbooks. Cambridge University Press, New York, 2015

    2015

  15. [15]

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

    1960

  16. [16]

    Kalai, N

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

    2016

  17. [17]

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

    2009

  18. [18]

    N. Keller. On the influences of variables on Boolean functions in product spaces.Combin. Probab. Comput., 20(1):83–102, 2011

    2011

  19. [19]

    N. Keller. A simple reduction from a biased measure on the discrete cube to the uniform measure. European J. Combin., 33(8):1943–1957, 2012

    1943

  20. [20]

    Keller and O

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

    2019

  21. [21]

    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

    2014

  22. [22]

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

    1966

  23. [23]

    Mossel, R

    E. Mossel, R. O’Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality.Ann. of Math. (2), 171(1):295–341, 2010

    2010

  24. [24]

    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

    2006

  25. [25]

    O’Donnell.Analysis of Boolean functions

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

    2014

  26. [26]

    T. Royen. A simple proof of the Gaussian correlation conjecture extended to some multivariate gamma distributions.Far East J. Theor. Stat., 48(2):139–145, 2014

    2014

  27. [27]

    Schramm and J

    O. Schramm and J. E. Steif. Quantitative noise sensitivity and exceptional times for percolation. Ann. of Math. (2), 171(2):619–672, 2010

    2010

  28. [28]

    Talagrand

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

    1996