pith. sign in

arxiv: 2410.10147 · v5 · submitted 2024-10-14 · 🧮 math.PR · cs.IT· math.IT

Local Optimality of Dictator Functions with Applications to Courtade--Kumar and Li--M\'edard Conjectures

Lei Yu This is my paper

Pith reviewed 2026-05-23 19:09 UTC · model grok-4.3

classification 🧮 math.PR cs.ITmath.IT
keywords dictator functionsΦ-stabilityCourtade-Kumar conjectureLi-Médard conjectureBoolean functionsnoise operatorsmajorizationhypercontractivity
0
0 comments X

The pith

Dictator functions are locally optimal in maximizing the Φ-stability of balanced Boolean functions.

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

The paper establishes that dictator functions achieve a local maximum of Φ-stability among all balanced Boolean functions, where Φ-stability is the expected value of a convex function applied to the noisy version of the function. This local optimality result is obtained by comparing the effect of small perturbations using the majorization properties of the Bonami-Beckner noise operator. Combining the local result with an earlier global bound, the authors apply computer-assisted verification to show that dictators maximize symmetric q-stability in two specific regimes of the parameters q and ρ. These regimes cover the Courtade-Kumar conjecture for correlation up to 0.914 and the symmetrized Li-Médard conjecture for q between 1.36 and 2.

Core claim

Given a convex function Φ from [0,1] to the reals, the Φ-stability of a Boolean function f is defined as the expectation of Φ applied to T_ρ f, where T_ρ is the Bonami-Beckner operator. Dictator functions are locally optimal for maximizing this quantity over all balanced Boolean functions. When restricted to symmetric q-stability, this local optimality plus a prior bound yields computer-assisted proofs that dictators achieve the global maximum for q=1 and ρ in [0,0.914], and for q in [1.36,2) with any ρ in [0,1].

What carries the argument

Majorization ordering of the Bonami-Beckner noise operators T_ρ together with hypercontractivity inequalities, used to establish local optimality under small perturbations of balanced functions.

If this is right

  • Dictator functions maximize symmetric q-stability when q equals 1 and the noise parameter ρ is at most 0.914.
  • Dictator functions maximize symmetric q-stability when q lies in [1.36,2) for every noise parameter ρ between 0 and 1.
  • The balanced version of the Courtade-Kumar conjecture holds for all correlation coefficients up to 0.914.
  • The symmetrized version of the Li-Médard conjecture holds for all q in [1.36,2).

Where Pith is reading between the lines

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

  • The same local-optimality technique may extend to the full range of the conjectures if the majorization ordering can be verified for additional values of q and ρ.
  • The approach could be adapted to prove global optimality for asymmetric stability measures once an appropriate majorization statement is established.
  • Computer-assisted enumeration of low-degree or low-influence functions might become feasible for verifying the remaining parameter regimes.

Load-bearing premise

The function must be balanced with mean zero and the majorization ordering of the noise operators must hold for the chosen convex Φ.

What would settle it

Existence of any balanced Boolean function that is not a dictator yet attains strictly higher Φ-stability than a dictator, for some convex Φ and some ρ in the ranges where the computer check was performed.

Figures

Figures reproduced from arXiv: 2410.10147 by Lei Yu.

Figure 1
Figure 1. Figure 1: The region of (q, ρ) (the gray region here) for which dictator functions maximize the q-stability (i.e., for which the Li–Médard conjecture is true). For q = 1, the corresponding ρ on the boundary of this region is ρ = 0.914. For q ≥ 1.36, the corresponding ρ on the boundary of this region is ρ = 1. investigate the majorization of Tρf for a Boolean function f, and connect it to the noise stability. We then… view at source ↗
Figure 2
Figure 2. Figure 2: The function of ρ 7→ ϵ ∗ 1,ρ. In other words, dictator functions maximize the q-stability for q > 0 and minimize the q-stability for q < 0 over all balanced Boolean functions f such that 0 ≤ mini∈[n] ˜di(f) ≤ ϵ ∗ q,ρ. This corollary still holds when the asymmetric q-stability is replaced by the symmetric q-stability. V. GLOBAL OPTIMALITY OF DICTATORSHIPS We next investigate the global optimality of dictato… view at source ↗
Figure 3
Figure 3. Figure 3: The function of ρ 7→ ϵ ∗ q,ρ with q = 1.36. We now use a computer-assisted method to prove the numerical observation above. The proof of the following theorem is almost identical to that of Theorem 7, and is provided in Section XI. Theorem 9. The optimal value of (25) for Φ = Φsym q with q = 1.36 is negative. In other words, for any ρ ∈ [0, 1] and q ∈ [1.36, 2), it holds that Stabsym q [f] ≤ Stabsym q [fd]… view at source ↗
Figure 4
Figure 4. Figure 4: The function of g. Proof: We first prove Statement 1. Consider the function f(ρ, ϵ) :=  ϵ +  1 + ρ 2 p (1 − 2ϵ) q/p +  ϵ +  1 − ρ 2 p (1 − 2ϵ) q/p −  1 + ρ 2 q −  1 − ρ 2 q , with p = 1 + (q − 1)ρ 2 and q = 1.36. So, by Lemma 1, given ρ ∈ (0, 1), ϵ ∗ q,ρ is the unique solution in (0, 1/2] to f(ρ, ϵ) = 0. Since f(ρ, ϵ) is strictly convex in ϵ and f(ρ, 0) = f(ρ, ϵ∗ q,ρ) = 0, it holds that f(ρ, ϵ)… view at source ↗
read the original abstract

Given a convex function $\Phi:[0,1]\to\mathbb{R}$, the $\Phi$-stability of a Boolean function $f$ is defined as $\mathbb{E}[\Phi(T_{\rho}f(\mathbf{X}))]$, where $\mathbf{X}$ is a random vector uniformly distributed on the discrete cube $\{\pm1\}^{n}$ and $T_{\rho}$ is the Bonami-Beckner operator. In this paper, we prove that dictator functions are locally optimal in maximizing the $\Phi$-stability of $f$ over all balanced Boolean functions. When focusing on the symmetric $q$-stability, combining this result with our previous bound, we use computer-assisted methods to prove that dictator functions maximize the symmetric $q$-stability for $q=1$ and $\rho\in[0,0.914]$ or for $q\in[1.36,2)$ and all $\rho\in[0,1]$. In other words, we confirm the (balanced) Courtade--Kumar conjecture with the correlation coefficient $\rho\in[0,0.914]$ and the (symmetrized) Li--M\'edard conjecture with $q\in[1.36,2)$. We conjecture that dictator functions maximize both the symmetric and asymmetric $\frac{1}{2}$-stability over all balanced Boolean functions. Our proofs are based on majorization of noise operators and hypercontractivity inequalities.

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 / 3 minor

Summary. The paper proves that, for any convex Φ:[0,1]→R, dictator functions are locally optimal maximizers of the Φ-stability E[Φ(T_ρ f(X))] among all balanced Boolean functions f (E[f]=0). The argument proceeds by establishing a majorization ordering on the Bonami-Beckner operators T_ρ and invoking hypercontractivity. As an application, the local result is combined with a prior global bound and computer-assisted enumeration to show that dictators maximize symmetric q-stability for q=1 and ρ∈[0,0.914] and for q∈[1.36,2) with all ρ∈[0,1], thereby confirming the balanced Courtade–Kumar conjecture in the first range and the symmetrized Li–Médard conjecture in the second. The authors also conjecture optimality for the ½-stability case.

Significance. If the local-optimality statement holds, it supplies a clean structural tool for stability questions on the hypercube that does not depend on additional fitted parameters. The partial resolutions of the two conjectures are concrete and falsifiable; the computer-assisted ranges are explicitly delimited. The manuscript credits the majorization and hypercontractivity ingredients and isolates the new local claim from the numerical verification step.

major comments (1)
  1. [Applications section] Applications section (computer-assisted verification paragraph): the discretization grid, interval-arithmetic error bounds, and the precise statement of the enumerated inequalities are described only at high level. Because these checks are load-bearing for the claimed ranges ρ≤0.914 (q=1) and q≥1.36 (all ρ), the verification step requires an explicit listing of the grid size, the floating-point precision used, and either deposited code or a self-contained interval-arithmetic lemma.
minor comments (3)
  1. [Abstract] Abstract and introduction: the phrase “combining this result with our previous bound” should cite the exact prior theorem or paper so that the dependence is immediately clear.
  2. [Section 2 (definitions)] Notation: the domain of Φ is stated as [0,1] but the range of T_ρ f is [-1,1]; clarify whether Φ is extended symmetrically or whether the argument uses only the positive part.
  3. [Concluding remarks] The conjecture for ½-stability is stated without indicating whether the same majorization argument applies or whether a different obstruction appears; a one-sentence remark would help readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation and for the constructive suggestion regarding the computer-assisted verification. We address the single major comment below and will incorporate the requested details in a revised version of the manuscript.

read point-by-point responses

  1. Referee: [Applications section] Applications section (computer-assisted verification paragraph): the discretization grid, interval-arithmetic error bounds, and the precise statement of the enumerated inequalities are described only at high level. Because these checks are load-bearing for the claimed ranges ρ≤0.914 (q=1) and q≥1.36 (all ρ), the verification step requires an explicit listing of the grid size, the floating-point precision used, and either deposited code or a self-contained interval-arithmetic lemma.

    Authors: We agree that the current description of the computer-assisted enumeration is at too high a level for a load-bearing step. In the revised manuscript we will expand the relevant paragraph (or add a short appendix) to state explicitly: (i) the discretization grid size and spacing used for the numerical search over low-degree polynomials, (ii) the floating-point or interval-arithmetic precision and the resulting rigorous error bounds, and (iii) either a self-contained lemma that certifies the enumerated inequalities or a pointer to publicly deposited code that implements the verification. This change will make the claimed ranges fully rigorous and reproducible without altering any of the mathematical claims. revision: yes

Circularity Check

0 steps flagged

Minor self-citation to prior bound; central local-optimality proof independent

full rationale

The derivation of local optimality for dictator functions proceeds from majorization of the Bonami-Beckner operators T_ρ together with hypercontractivity, under the explicitly stated assumptions that Φ is convex and E[f]=0. These steps rely on external inequalities rather than any internal redefinition or fitted parameter. The subsequent applications to the Courtade-Kumar and Li-Médard conjectures combine the new local result with a prior bound from the author's earlier work plus computer-assisted interval-arithmetic checks whose discretization is described in the manuscript. No equation reduces the target Φ-stability quantity to a quantity defined inside the paper by construction, and the self-citation is not load-bearing for the central local-optimality claim. The paper is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Central claims rest on standard hypercontractivity inequalities and majorization properties of the Bonami-Beckner operator; no free parameters or new entities are introduced.

axioms (2)
  • standard math Hypercontractivity inequalities for the Bonami-Beckner operator
    Invoked to bound noise stability (abstract).
  • standard math Majorization ordering of noise operators
    Used to establish local optimality (abstract).

pith-pipeline@v0.9.0 · 5793 in / 1317 out tokens · 25210 ms · 2026-05-23T19:09:48.897579+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

36 extracted references · 36 canonical work pages · 1 internal anchor

  1. [1]

    Anantharam, A

    V . Anantharam, A. Bogdanov, A. Chakrabarti, T. Jayaram, and C. Nair. A conjecture regarding optimality of the dictator function under Hellinger distance. In Information Theory and Applications Workshop) . Available at http://chandra.ie.cuhk.edu.hk/pub/papers/HC/hel-conj.pdf, 2017

    work page 2017

  2. [2]

    Anantharam, A

    V . Anantharam, A. A. Gohari, S. Kamath, and C. Nair. On hypercontractivity and the mutual information between Boolean functions. In Communication, Control, and Computing (Allerton), 2013 51th Annual Allerton Conference on , pages 13–19. IEEE, 2013

    work page 2013

  3. [3]

    L. P. Barnes and A. Özgür. The Courtade-Kumar most informative Boolean function conjecture and a symmetrized Li- Médard conjecture are equivalent. In 2020 IEEE International Symposium on Information Theory (ISIT) , pages 2205–2209. IEEE, 2020

    work page 2020

  4. [4]

    Beltran, P

    D. Beltran, P. Ivanisvili, and J. Madrid. On sharp isoperimetric inequalities on the hypercube. arXiv preprint arXiv:2303.06738, 2023

    work page arXiv 2023

  5. [5]

    S. G. Bobkov and F. Götze. Discrete isoperimetric and Poincaré-type inequalities. Probability theory and related fields , 114:245–277, 1999

    work page 1999

  6. [6]

    C. Borell. Geometric bounds on the Ornstein–Uhlenbeck velocity process. Probability Theory and Related Fields, 70(1):1– 13, 1985

    work page 1985

  7. [7]

    M.-C. Chang. A polynomial bound in Freiman’s theorem. Duke mathematical journal , 113(3):399–419, 2002

    work page 2002

  8. [8]

    Chen and C

    Z. Chen and C. Nair. On the optimality of dictator functions and isoperimetric inequalities on boolean hypercubes. In 2024 IEEE International Symposium on Information Theory (ISIT) , pages 3380–3385. IEEE, 2024

    work page 2024

  9. [9]

    T. A. Courtade and G. R. Kumar. Which Boolean functions maximize mutual information on noisy inputs? IEEE Trans. Inf. Theory, 60(8):4515–4525, 2014

    work page 2014

  10. [10]

    Durcik, P

    P. Durcik, P. Ivanisvili, and J. Roos. Sharp isoperimetric inequalities on the Hamming cube near the critical exponent. arXiv preprint arXiv:2407.12674 , 2024

    work page arXiv 2024

  11. [11]

    R. Eldan. A two-sided estimate for the Gaussian noise stability deficit. Inventiones Mathematicae, 201(2):561–624, 2015

    work page 2015

  12. [12]

    Eldan, D

    R. Eldan, D. Mikulincer, and P. Raghavendra. Noise stability on the Boolean hypercube via a renormalized Brownian motion. pages 661–671, 2023. 42

    work page 2023

  13. [13]

    F.-W. Fu, V . K. Wei, and R. W. Yeung. On the minimum average distance of binary codes: Linear programming approach. Discrete Applied Mathematics , 111(3):263–281, 2001

    work page 2001

  14. [14]

    Gács and J

    P. Gács and J. Körner. Common information is far less than mutual information. Problems of Control and Information Theory, 2(2):149–162, 1973

    work page 1973

  15. [15]

    Kahn and J

    J. Kahn and J. Park. An isoperimetric inequality for the Hamming cube and some consequences. Proceedings of the American Mathematical Society , 148(10):4213–4224, 2020

    work page 2020

  16. [16]

    Remarks on the Most Informative Function Conjecture at fixed mean

    G. Kindler, R. O’Donnell, and D. Witmer. Remarks on the most informative function conjecture at fixed mean. arXiv preprint arXiv:1506.03167, 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  17. [17]

    E. N. Laguerre. Sur la théorie des équations numériques. Journal de Mathématiques pures et appliquées. [Online]. Available: http://sepwww.stanford.edu/oldsep/stew/laguerre.pdf, 1883

    work page

  18. [18]

    M. Ledoux. Semigroup proofs of the isoperimetric inequality in Euclidean and Gauss space. Bulletin des sciences mathématiques, 118(6):485–510, 1994

    work page 1994

  19. [19]

    M. Ledoux. Remarks on Gaussian noise stability, Brascamp-Lieb and Slepian inequalities. In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2011-2013 , pages 309–333. Springer, 2014

    work page 2011

  20. [20]

    Li and M

    J. Li and M. Médard. Boolean functions: noise stability, non-interactive correlation distillation, and mutual information. IEEE Trans. Inf. Theory , 67(2):778–789, 2020

    work page 2020

  21. [21]

    A. W. Marshall, I. Olkin, and B. C. Arnold. Inequalities: theory of majorization and its applications . Springer, New York, 2011

    work page 2011

  22. [22]

    Mossel and R

    E. Mossel and R. O’Donnell. Coin flipping from a cosmic source: On error correction of truly random bits. Random Structures & Algorithms , 26(4):418–436, 2005

    work page 2005

  23. [23]

    C. Nair. Equivalent formulations of hypercontractivity using information measures. In International Zurich Seminar (IZS) Workshop, 2014

    work page 2014

  24. [24]

    O’Donnell

    R. O’Donnell. Analysis of Boolean Functions . Cambridge University Press, 2014

    work page 2014

  25. [25]

    Ordentlich, O

    O. Ordentlich, O. Shayevitz, and O. Weinstein. An improved upper bound for the most informative Boolean function conjecture. In 2016 IEEE International Symposium on Information Theory (ISIT) , pages 500–504. IEEE, 2016

    work page 2016

  26. [26]

    Pichler, P

    G. Pichler, P. Piantanida, and G. Matz. Dictator functions maximize mutual information. The Annals of Applied Probability, 28(5):3094–3101, 2018

    work page 2018

  27. [27]

    Polyanskiy, H

    Y . Polyanskiy, H. V . Poor, and S. Verdú. Channel coding rate in the finite blocklength regime. IEEE Trans. Inf. Theory , 56(5):2307–2359, 2010

    work page 2010

  28. [28]

    Samorodnitsky

    A. Samorodnitsky. On the entropy of a noisy function. IEEE Trans. Inf. Theory , 62(10):5446–5464, 2016

    work page 2016

  29. [29]

    Talagrand

    M. Talagrand. Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem. Geometric & Functional Analysis GAFA , 3(3):295–314, 1993

    work page 1993

  30. [30]

    C. Tsallis. What are the numbers that experiments provide. Quimica Nova, 17(6):468–471, 1994

    work page 1994

  31. [31]

    H. S. Witsenhausen. On sequences of pairs of dependent random variables. SIAM Journal on Applied Mathematics , 28(1):100–113, 1975

    work page 1975

  32. [32]

    L. Yu. The Entropy Method . DOI: 10.13140/RG.2.2.26552.11527/1, 2023

    work page doi:10.13140/rg.2.2.26552.11527/1 2023

  33. [33]

    L. Yu. On the Φ-stability and related conjectures. Probability Theory and Related Fields , 186(3):1045–1080, 2023

    work page 2023

  34. [34]

    L. Yu. Matlab codes. https://lei-yu.github.io/, 2024

    work page 2024

  35. [35]

    Yu and V

    L. Yu and V . Y . F. Tan. An improved linear programming bound on the average distance of a binary code. arXiv preprint arXiv:1910.09416, 2019

    work page arXiv 1910

  36. [36]

    Yu and V

    L. Yu and V . Y . F. Tan. Common information, noise stability, and their extensions. Foundations and Trends in Communications and Information Theory , 19(2):107–389, 2022. 43

    work page 2022