Source-linked AI summary
Stability of the Courtade-Kumar inequality
Vu Khac Ky, Tuan Tran
TL;DR
The paper asks whether a one-bit summary with information near the dictator value must itself be close to a signed dictator. It proves dimension-independent stability through entropy-production and energy comparisons, with sharp correlation dependence near zero and, for increasing functions, at the noiseless endpoint.
Problem
The Courtade–Kumar conjecture asserts that keeping one input bit is optimal; the paper asks whether summaries retaining nearly that information must be close to an input bit or its complement.
Source: §1 · p. 1Method
An entropy-barrier approach combines quantitative entropy-production estimates with spectral and marked-coordinate energy comparisons, then uses quantitative compression for arbitrary functions.
Source: §1 · p. 1, §1.1 · p. 2Results
Three-variable majority shows both stability bounds have optimal order as ρ ↓ 0, and the increasing-function bound also has optimal order as ρ ↑ 1.
Source: §1 · p. 2Takeaways & Limitations
For 0 < ρ < 1, equality in the Courtade–Kumar bound holds precisely for signed dictators, while at ρ = 1 balanced functions can be far from dictators.
Source: §1 · p. 2The general bound contains an extra factor 1 − ρ from quantitative compression, and the paper does not determine whether it can be removed.
Source: §5.6 · p. 13
Abstract
from arXiv · showhide
We prove dimension-independent stability for the Courtade-Kumar inequality: a Boolean function $f:\{-1,1\}^n\to\{-1,1\}$ whose information is close to the dictator value is close in probability to a signed dictator. The correlation dependence is sharp in order near zero and, for increasing functions, also at the noiseless endpoint.
1. Introduction
The paper studies whether a one-bit summary that nearly matches the Courtade–Kumar dictator information must be close to a signed dictator, with bounds independent of dimension. It proves stability using entropy-production and energy comparisons, and shows the correlation dependence is sharp in the stated endpoint regimes.
1. Introduction
- If I(f(X); Yρ) ≥ Φ(ρ) − ε, then f is close in probability to some signed dictator, with a dimension-independent bound.The theorem applies for 0 < ρ < 1.Source: §1 · p. 1
- For increasing functions, a separate bound controls the probability of differing from an original coordinate, with correlation dependence ρ^2H(ρ).The introduction states the bound as 108ε ρ^2H(ρ).Source: §1 · p. 2
- At ρ = 1, every balanced Boolean function carries log 2 information, even when it is far from a dictator.For 0 < ρ < 1, equality in the Courtade–Kumar bound holds precisely for signed dictators.Source: §1 · p. 2
- Three-variable majority shows both bounds have optimal order as ρ ↓ 0, and the increasing-function bound also has optimal order as ρ ↑ 1.The endpoint dependence is therefore sharp in the stated regimes.Source: §1 · p. 2
1.1. Method and contributions.
- The proof combines entropy-production surplus with spectral and marked-coordinate energy comparisons, then uses quantitative compression to transfer stability from increasing to arbitrary functions.A pointwise-in-correlation deficit comparison leads to a contradiction at the noiseless endpoint if the deficit is too small relative to distance from a signed dictator.Source: §1.1 · p. 2
2. Noise and entropy profiles
This section sets notation for the information deficit and dictator distance, then develops entropy-production profiles and estimates used in the stability proof.
2.1. Fourier coefficients, noise, and entropy production.
- The information deficit is the noisy dictator information minus f’s mutual information, while δ(f) is its probability of disagreement with the nearest signed dictator.At ρ = 1, the deficit is Φ(Ef), accounting for the initial entropy of an unbalanced bit.Source: §2 · p. 2, §2.1 · p. 3
- Noise scales level-k Fourier coefficients by ρ^k, and the entropy-production surplus D(Tρf)/ρ − u measures production beyond the dictator’s rate.The parameter u tends to infinity as correlation approaches the noiseless endpoint.Source: §2.1 · pp. 2–3
2.2. Entropy profiles and their clocks.
- The entropy profile F(v) = H(tanh v) gives the entropy-to-edge-difference ratio, and its inverse defines production heights used to compare source and dictator profiles.Clock propagation converts a profile comparison Q ≤ Pf into Eρ(f) ≥ H(ρ)ρ^−ϵ over the specified correlation range.Source: §2.2 · pp. 3–4
2.3. Coordinate production and martingale energy.
- Coordinate entropy production is bounded using conditional projections and a martingale-energy estimate that retains the energy of the revealed coordinate.The coordinate argument also gives Di(g) ≥ Diri(g).Source: §2.3 · p. 4
3. From entropy estimates to stability
The stability proof turns entropy-production estimates into a deficit bound proportional to dictator distance. A common profile dilation and quantitative compression extend the comparison across coordinates and from increasing to arbitrary functions.
3.1. Comparison with an entropy barrier.
- If production surplus satisfies the criterion below its normalized-deficit threshold, then Δρ(f) ≥ cH(ρ)δ(f) for correlations from tanh u0 to 1.The proof compares the deficit with an entropy barrier and uses the nonnegative noiseless-endpoint deficit to rule out crossing below it.Source: §3.1 · pp. 4–5
3.2. A common dilation for all coordinates.
- A single dilation ϑ = 1 + (Δρ(f))+/H(ρ) adjusts all coordinate profile heights when actual conditional entropy exceeds H(ρ).The dilation supports both coordinate and total production bounds.Source: §3.2 · p. 5
3.3. Quantitative compression.
- Coordinate sorting preserves the mean, does not decrease information, and does not increase dictator distance, but transferring stability also requires controlling the original distance by the compressed distance and information gained.This quantitative estimate enables stability bounds proved for increasing functions to extend to arbitrary Boolean functions.Source: §3.3 · pp. 5–6
4. Local and intermediate correlations
The section develops local deficit bounds and extends stability across low and intermediate correlations. Its estimates apply to arbitrary Boolean functions up to ρ = 457/500 and to increasing functions through ρ = 49/50.
4. Local and intermediate correlations.
- As δ ↓ 0, the deficit is 2ρ atanh(ρ)δ + Oρ(δ^2/(1+ρ^2)), uniformly in dimension, with a sharp leading coefficient and no balance or monotonicity assumption.For sufficiently small δ at fixed ρ, the deficit is at least ρ atanh(ρ)δ.Source: §4 · p. 6
4.1. Local entropy and low-correlation inputs.
- The local comparison Mρ(a) is a computable lower bound for the deficit whose concavity propagates a positive estimate into a linear bound near dictators.Combining dictator-neighborhood estimates with an absolute gap away from dictators yields a stability result for every Boolean function when 0 < ρ ≤ 457/500.Source: §4.1 · pp. 6–7
4.2. Intermediate correlations.
- For increasing functions, a five-band source cover combines local, cubic-energy, clock, and two-coordinate moment comparisons to obtain a positive gap for 457/500 ≤ ρ ≤ 49/50.The two-coordinate moment comparison gives Δρ(f) > (1 − ρ^2)/1000 on its assigned cells.Source: §4.2 · pp. 7–8
5. Production bounds near the noiseless endpoint
The section develops spectral and marked-coordinate production estimates, then combines them with local comparisons to prove stability. It also establishes the endpoint sharpness of the bounds and identifies an unresolved loss in the general-function bound.
5.1. The spectral energy bound and its scalar cost.
- The spectral energy estimate separates retained and discarded Fourier costs, while the entropy remainder J controls the arcsine transform’s linearization error.Retained modes incur costs depending on degree and singleton coefficients; discarded singleton mass is paid from the production budget.Source: §5.1 · p. 9
5.2. Spectral comparison away from dictators.
- For sources away from dictators, the spectral comparison yields m > 1/200000 and Γ/b < 3000 in the compact range, and m > u/200 and Γ/b < 4e^(2u−7)/u for u ≥ 8.The stated parameter ranges satisfy the transfer condition used to compare production with the dictator value while retaining the information deficit.Source: §5.2 · p. 10
5.3. Conditional variance around a marked coordinate.
- Because an unbalanced source’s two sections can have different means, conditional variance measures its dependence on coordinates beyond the marked one.The marked coordinate is chosen with a largest singleton coefficient.Source: §5.3 · p. 10
5.4. A marked-coordinate production estimate.
- The marked-coordinate estimate combines the coordinate’s entropy profile with additional production from the variance in the remaining coordinates.The argument uses a conditional energy estimate and pays retained-coordinate costs from the same production budget.Source: §5.4 · p. 11
5.5. Choosing the marked-coordinate parameters.
- The choice z = 19u/40 − 1/2 and λ = 21u/20 + 2 supplies bounds in the stated distance ranges for log 96 ≤ u ≤ 8 and u ≥ 8.The corollary gives ranges d−(u) ≤ δ ≤ 1/64 and e^(−5u/4) ≤ δ ≤ 1/64, respectively.Source: §5.5 · p. 12
5.6. Proof of the main theorem.
- For increasing f, Δρ(f) ≥ 10^-8ρ^2H(ρ)δ(f); the general-function stability bound includes an extra (1−ρ) factor.The proof combines this production bound with local comparisons to obtain the stated signed-dictator estimates.Source: §5.6 · pp. 12–13
- Three-variable majority shows both bounds have optimal order as ρ ↓ 0, and the increasing-function bound also has optimal order as ρ ↑ 1.The endpoint comparisons establish sharpness in order for this example.Source: §5.6 · p. 13
- The authors do not determine whether the general bound’s extra (1−ρ) factor, which arises from quantitative compression, can be removed.Source: §5.6 · p. 13
A.1. Scalar cost bounds.
The scalar-cost bounds use convex upper bounds to reduce height checks to endpoints.
A.1. Scalar cost bounds.
- Replacing [v − R(v)]/v by a tangent-based expression gives a convex upper bound on the scalar cost over 0 < v ≤ u.The replacement is 1 − R′(c) + [cR′(c) − R(c)]/v for c > 0.Source: §A.1 · p. 14
- Alternatively, bounding the arcsine contribution by π^2/(4v) also yields a convex upper bound.Source: §A.1 · p. 14
- The convex bounds reduce each closed height interval to its endpoints, avoiding numerical inversion of the profile.Source: §A.1 · p. 14
A.2. The analytic spectral margin.
The analytic spectral-margin argument bounds retained costs with convex branches and compares them against the production baseline.
A.2. The analytic spectral margin.
- The retained-cost bound uses a logarithmic branch for a ≤ 1/8 and a quadratic branch for a ≥ 1/8; each branch is convex, so its maximum occurs at an endpoint.Only the two outer heights and ℓu(1/8) need checking.Source: §A.2 · p. 14
- For u ≥ 8, the chosen parameters satisfy t < u − 3 and k(t)ρ^2/u > 3/5, while the normalized baseline N/u exceeds 29/20.The estimates also bound the discarded-coordinate cost below the baseline.Source: §A.2 · p. 14
- The resulting production margin satisfies N/b − u > u/200, with Γ/b < 4e^(2u−7)/u.Source: §A.2 · p. 15
A.3. Normalization of the compact spectral margins.
The compact certificate verifies normalized margins for discarded-coordinate and retained-height inequalities, then translates them into explicit production and loss bounds.
A.3. Normalization of the compact spectral margins.
- The compact certificate covers 24 intervals, with normalized margins greater than 1/1000 for the discarded-coordinate inequality and 1/100 for each retained-height inequality.Source: §A.3 · p. 15
- Multiplying by the stated normalization factors yields the expressions checked for the discarded-coordinate bound and the retained-cost majorant.The retained factor uses height-dependent quantities including log(4/a) and the logarithmic or quadratic cost.Source: §A.3 · p. 15
- The compact parameter estimates imply m > 1/200000 and Γ/b < 3000.The bounds follow from N − ub > 1/56000, b < 3, and the stated bounds on γ and C∗.Source: §A.3 · p. 15
A.4. The marked-coordinate parameter bounds.
The marked-coordinate estimates establish uniform scalar margins for the chosen parameters and yield a lower bound on the production surplus across the stated ranges. The proof controls endpoint and exponential losses to obtain the final bound on P.
A.4. The marked-coordinate parameter bounds.
- The proof bounds discarded cost and entropy loss throughout the interval without requiring a subdivision certificate.It uses the marked-profile bound and endpoint estimates to control the remaining terms.Source: §A.4 · pp. 15–16
- With the parameters of Corollary 5.5, every u ≥ 9/2 satisfies Cz > 7/25 and C(u + 4/7) < 1, as stated in Lemma A.2.Source: §A.4 · p. 15
- The endpoint checks for (5.10) give a lower bound above 1/200 at a = β and 3/5 at a = 1/32.Concavity reduces the check to those endpoints when 2δ ≤ 1/32.Source: §A.4 · p. 16
- P ≥ u(1 + δ/40 − Z+) in both stated parameter ranges.For log 96 ≤ u ≤ 8, the proof takes d = (3/2)e^-u; for u ≥ 8, it takes d = e^(-5u/4).Source: §A.4 · pp. 16–17
A.5. The local bound at the endpoint.
For increasing Boolean sources with sufficiently small distance δ(f) from a dictator, the endpoint argument gives a lower bound on the Courtade-Kumar deficit. The bound holds without a monotonicity assumption in the local estimate itself.
A.5. The local bound at the endpoint.
- For u = atanh ρ ≥ 8 and δ(f) ≤ e^(-5u/4), Δρ(f) ≥ u(1 − ρ)δ(f)/2.The local estimate is established for every Boolean source and requires no monotonicity assumption.Source: §A.5 · p. 17
- The proof compares entropy scales at d = e^(-5u/4) and p = (1 − ρ)/2 to establish the deficit estimate.It bounds the entropy difference using binary-entropy estimates and controls the correction terms for u ≥ 8.Source: §A.5 · p. 17
Appendix B. Certificates and reproducibility
The appendix describes checks that certify the scalar inequalities and domain coverage used in the paper's numerical arguments.
Appendix B. Certificates and reproducibility
- The certificates check strict scalar inequalities and domain coverage using rational or algebraic arithmetic, interval enclosures, and retained subdivisions.Outward-rounded Arb intervals must have a consistent sign; subdivisions retain both children unless infeasibility is proved.Source: Appendix B · p. 17
B.1. Low-correlation margin checks.
The appendix records margin checks and parameter choices supporting the low-correlation and intermediate-range bounds, then describes the compact-range certificate and how to replay the verification.
B.1. Low-correlation margin checks.
- The low-correlation Fourier estimate yields Δρ(f) ≥ cV(ρ) + μ²/100 for the stated mean and correlation ranges, with V(ρ) > 1/50000.The same estimates give A3/5(f) < 9/50 − 1/1000 and support the local and large-mean margins.Source: §B.1 · p. 17
B.2. Intermediate-range margin checks.
- The intermediate source cover uses rational parameters, and a concavity argument certifies χρ(t) ≤ −1/4000 throughout [0, 1].The endpoint supporting-line values are below −1/4000; local endpoint signs and clock margins are also recomputed.Source: §B.2 · p. 18
B.3. The compact spectral parameters.
- For 45951/20000 ≤ u ≤ 8, the compact spectral parameters use z = log u + u/25 − 2/5, t = 49u/100 + 7/5, and γ = 1.The influence cutoff is c(u) = 1 − 2e^-u through u = 4 and 31/32 thereafter; the retained-height checks use bounds at specified endpoints.Source: §B.3 · p. 18
B.4. The compact certificate.
- The compact certificate covers [45951/20000, 8] with 24 closed rational intervals and checks four height inequalities per interval.An independent audit uses separately derived formulas and 384-bit arithmetic over the full extended height domain.Source: §B.4 · p. 18
B.5. Files and replay scope.
- The repository's README gives installation instructions, and python3 verify.py checks the manifest and replays all twelve numerical stages.Assertions must remain enabled; no file from the companion package is required.Source: §B.5 · p. 18