Pith. sign in

REVIEW 2 major objections 5 minor 23 references

Level-k Boolean functions maximize the divergence and Fisher information that two one-bit compressions can extract from correlated sources, at least for unbiased pairs and for identical pairs under nonnegative correlation.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-31 15:56 UTC pith:QDCWS7ZG

load-bearing objection Solid partial resolution of Amari–Kobayashi via level-k optimality, with clean proofs and an honest scope on what remains open. the 2 major comments →

arxiv 2607.28162 v1 pith:QDCWS7ZG submitted 2026-07-30 cs.IT math.IT

On The Most Discriminative Boolean Functions for Correlated Sources

Jun Chen , Shun Watanabe , Lei Yu This is my paper
classification cs.IT math.IT MSC 94A1794A1568Q8762B10
keywords Boolean functionsKullback-Leibler divergenceFisher informationFourier analysislevel-k functionsdistributed hypothesis testingnoise stabilitymaximal correlation difference
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

When two correlated binary strings are each reduced to a single bit by Boolean functions, which pair of functions best distinguishes two different correlation strengths? The paper shows that the answer is given by level-k functions: Boolean functions whose Fourier mass sits entirely on sets of a fixed size k. For unbiased functions, and for identical (or opposite) functions when correlations are nonnegative, both Kullback-Leibler divergence and Fisher information are maximized by some level-k pair, and the same class is optimal for Bayesian one-bit distributed hypothesis testing among all pairs. Because parity functions are special cases of level-k functions, this partially confirms a conjecture of Amari and Kobayashi that parities maximize Fisher information. The one-function analogue, by contrast, does not always favor level-k functions, so the two-function and one-function problems behave differently.

Core claim

For unbiased Boolean pairs, and for identical or opposite pairs in the nonnegative-correlation regime, the KL divergence between the two induced output distributions is at most the binary divergence achieved by any identical level-k pair, and the same bound holds for Fisher information; level-k functions are moreover optimal among all pairs for Bayesian one-bit distributed hypothesis testing.

What carries the argument

Level-k functions (Fourier support concentrated on degree k) together with a two-weight convexity comparison for binary divergence (Lemma 1) and a reduction from biased identical pairs to the unbiased case via η-biased τ-correlated pairs (Lemma 2).

Load-bearing premise

The biased identical-function bound needs both correlations to be nonnegative; the key comparison that unbiased pairs dominate fails once either induced correlation parameter becomes negative.

What would settle it

Exhibit a biased pair f ≠ g, or an identical biased pair under a negative correlation, whose output divergence or Fisher information strictly exceeds the maximum binary divergence (or Fisher value) attained by level-k functions for the same (ρ0, ρ1).

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Parity functions remain competitive candidates for maximizing Fisher information, but the optimum is attained by the larger class of all level-k functions.
  • In Bayesian one-bit distributed hypothesis testing of two correlations, the minimal Bayes error is achieved by matching level-k encodings and a simple agreement/disagreement decoder.
  • When the reference correlation is zero the problem collapses to mutual-information maximization, recovering the known optimality of dictators as the k = 1 case.
  • The one-function divergence problem is not settled by the same level-k candidates and can favor majority for some parameter pairs.

Where Pith is reading between the lines

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

  • Closing the remaining biased f ≠ g case will likely require tighter Fourier constraints than the relaxed nonnegativity and Cauchy–Schwarz conditions already considered, since those relaxations can make the objective unbounded.
  • The singular-value characterization of maximal correlation difference suggests that similar level-k optimality may hold for other f-divergences or Rényi divergences whose generators preserve the same averaging argument.
  • Numerical counter-examples already show that the one-function problem can prefer majority over level-k; a clean phase diagram separating those regimes would complete the analogy with the Courtade–Kumar conjecture.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies pairs of Boolean functions f,g that maximize the KL divergence between the push-forward distributions of a ρ0-correlated pair and a ρ1-correlated pair after one-bit compression. When ρ1=0 this recovers mutual-information maximization (dictators optimal). The local (Fisher-information) version is the Amari–Kobayashi conjecture that parities are optimal. Using Fourier analysis on the cube, the authors prove that level-k functions maximize both divergence and Fisher information for unbiased pairs (Theorems 1, 4) and for identical (or opposite) pairs under nonnegative correlation (Theorems 2, 5). Level-k functions also minimize Bayes error among all pairs in one-bit Bayesian distributed hypothesis testing (Theorem 6). Local optimality when one function is already level-k is shown by data processing (Theorem 3). The one-function analogue (a divergence form of Courtade–Kumar) is discussed and shown to behave differently; majority can beat level-k for some parameters.

Significance. The work gives a clean, partial resolution of the Amari–Kobayashi conjecture and places it in a broader divergence-maximization framework that unifies mutual information, Fisher information, and Bayesian one-bit HT. The proofs are elementary and non-circular: a two-weight convexity lemma for binary divergence (Lemma 1), a bias-reduction comparison for (η,τ)-pairs (Lemma 2), Cauchy–Schwarz/Parseval arguments, and data processing. Equality is attained by the stated class, and the paper is explicit that level-k properly contains parities and that biased unequal / negative-τ regimes remain open. The Bayesian HT result (Theorem 6) and the maximal-correlation-difference characterization are operationally sharp. These are solid, citable contributions to the Fourier-analytic information-theory literature.

major comments (2)
  1. [Abstract; §I; after (19); Theorems 1–2, 4–5] The Amari–Kobayashi conjecture is stated for parity functions, yet the proved upper bounds are attained by the strictly larger class of level-k functions (explicit non-parity level-2 example after (19)). Theorems 1–2 and 4–5 therefore resolve a natural strengthening rather than the original claim. The manuscript should state clearly whether the authors conjecture that every maximizer is a parity (or only that the value is the parity value), and whether non-parity level-k functions can be optimal for some (ρ0,ρ1) while parities are not. This is load-bearing for how the partial resolution is advertised in the abstract and introduction.
  2. [Theorem 2; Lemma 2; Remark 2; Theorem 5; §III-D] Theorem 2 and Lemma 2 require ρ0,ρ1∈[0,1) so that the induced correlation parameters τc stay nonnegative; Remark 2 correctly notes that the bias-reduction inequality fails in general for negative τ. Consequently the biased identical-function case under negative correlation (and the corresponding Fisher bound of Theorem 5 for ρ<0) remains open. Given that the Amari–Kobayashi conjecture is stated for all ρ∈(−1,1), the open negative-correlation biased regime should be listed explicitly among the remaining cases in §III-D / §VI rather than only in a remark, so that the scope of the partial resolution is unambiguous.
minor comments (5)
  1. [Fig. 2] Figure 2 (optimal k for the level-k divergence) is useful but the color legend is hard to parse in grayscale; a contour or numeric annotation for the k=1 vs k≥2 transition would help.
  2. [Remark 1] In the alternative proof of Theorem 1 (Remark 1), “Cauchu–Schwarz” should be “Cauchy–Schwarz”.
  3. [§IV-B, Eq. (60)] Equation (60) and the subsequent display for G(n,f,f,ρ) are dense; a short sentence recalling that the four atoms of the (η,τ)-pair produce the three distinct summands would improve readability.
  4. [§VI] The one-function discussion in §VI reports numerical optimality of majority for selected (ρ0,ρ1) on n=3 but gives no table or reproducible enumeration protocol; a brief appendix or pointer would make the counterexamples checkable.
  5. [References] Reference [11] is listed as “in IEEE ISIT 2026, arXiv:2601.10526”; confirm final venue/year consistency before camera-ready.

Circularity Check

0 steps flagged

No circularity: bounds derived from Fourier identities, Cauchy–Schwarz/Parseval, and KL convexity without assuming the target optima

full rationale

The paper’s central claims (Thms 1–6) are upper bounds on KL divergence, Fisher information, and Bayes correct probability for Boolean compressions of ρ-correlated sources. Each bound is obtained from the standard Fourier expansion on the Boolean cube, the noise operator T_ρ, Plancherel/Parseval, Cauchy–Schwarz on Fourier coefficients, joint convexity of KL (Lemma 1 and the alternative Remark 1 argument), a reduction of biased (η,τ)-pairs to the unbiased case (Lemma 2), data-processing (Thm 3), and elementary second-derivative/convexity comparisons (Lemmas 3–4). Level-k optimality is the conclusion of these inequalities, not an input: the paper never defines the objective in terms of level-k functions, nor does it fit parameters to data and relabel the fit as a prediction. Citations to Amari–Kobayashi, Courtade–Kumar, and Pichler–Piantanida–Matz supply motivation and known special cases (ρ1=0 → mutual information; local limit → Fisher); they are not used as unproved uniqueness theorems that force the new inequalities. Open regimes (biased unequal f≠g; negative τ) are explicitly flagged rather than papered over. The derivation chain is therefore self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 1 invented entities

Load-bearing content is standard Fourier analysis on the hypercube plus classical information-theoretic inequalities. No fitted parameters. The only named new object is maximal correlation difference (MCD), introduced as a convenient singular-value packaging of an already-proved bound, not as an explanatory entity.

axioms (6)
  • standard math Fourier basis {χ_S} is orthonormal on the uniform Boolean cube; Plancherel/Parseval hold.
    Section II; used throughout to expand f,g and express Stab_ρ and E[f(X)g(Y)].
  • standard math Noise operator T_ρ multiplies the degree-|S| coefficient by ρ^{|S|}.
    Eq. (7)–(8); standard fact for the binary symmetric noise model (6).
  • standard math KL divergence is jointly convex; binary divergence d(·||·) inherits the needed second-derivative comparisons.
    Used in Lemma 1, Remark 1, and the proof of Theorem 2.
  • standard math Data-processing inequality for KL under Markov kernels.
    Proof of Theorem 3 (local optimality).
  • domain assumption Sources are i.i.d. coordinatewise ρ-correlated bits on {0,1}^n (model (6)).
    Defines the entire problem; standard DSBS / BSC correlation model in this literature.
  • domain assumption For biased identical pairs, correlations ρ0,ρ1 lie in [0,1) so induced τ_c ≥ 0.
    Hypothesis of Theorem 2; Remark 2 notes failure when τ can be negative.
invented entities (1)
  • Maximal correlation difference (MCD) independent evidence
    purpose: Package the sharp bound on |E_ρ0[fg]−E_ρ1[fg]| as the top singular value of a difference kernel; unify with classical maximal correlation.
    Defined in §V-A; for the binary DSBS it equals max_k |ρ0^k−ρ1^k| and is attained by level-k functions, so it restates Theorem 6 rather than adding independent ontology.

pith-pipeline@v1.2.0-daily-grok45 · 26262 in / 2852 out tokens · 64934 ms · 2026-07-31T15:56:19.066344+00:00 · methodology

0 comments
read the original abstract

Motivated by a conjecture of Amari and Kobayashi, we study the problem of identifying pairs of Boolean functions that maximize the Kullback-Leibler divergence between two distributions obtained by separately compressing two correlated sources. When the reference distribution corresponds to independent sources, this problem reduces to the problem of maximizing mutual information, for which the optimality of dictator functions has been proved by Pichler, Piantanida, and Matz. For the problem of maximizing Fisher information, which can be viewed as a local version of the problem studied in this paper, Amari and Kobayashi conjectured that parity functions are optimal. For unbiased pairs of Boolean functions, and for identical pairs in the nonnegative correlation regime, we prove that both the divergence and the Fisher information are maximized by level-$k$ functions, namely, functions whose Fourier coefficients are supported only on level $k$. Since level-$k$ functions include parity functions, this gives a partial resolution of the conjecture of Amari and Kobayashi. Furthermore, in the framework of Bayesian distributed one-bit hypothesis testing, we prove that level-$k$ functions are optimal among all pairs of functions. Finally, we also discuss the one function version of the problem studied in this paper, which can be regarded as the divergence analogue of the Courtade and Kumar conjecture.

Figures

Figures reproduced from arXiv: 2607.28162 by Jun Chen, Lei Yu, Shun Watanabe.

Figure 1
Figure 1. Figure 1: A description of the problems studied by Amari and thi [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A plot of 1 ≤ k ≤ 10 that maximizes (20) for −1 ≤ ρ0, ρ1 ≤ 1; the horizontal axis is ρ1 and the vertical axis is ρ0; the left-top is (−1, −1) and the right-bottom is (1, 1); White → 1, Cyan → 2, Blue → 3, Yellow → 4, Green → 5, Magenta → 6, Red → 7, Orange → 8, Brown → 9, and Black → 10. Furthermore, for g = −f, we have D(Pf(Xn)g(Y n),ρ0 kPf(Xn)g(Y n),ρ1 ) ≤ max 1≤k≤n d  1 + ρ k 0 2 [PITH_FULL_IMAGE:figu… view at source ↗

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

23 extracted references · 3 linked inside Pith

  1. [1]

    On optimal data compression in multiterminal statistical inference,

    S. Amari, “On optimal data compression in multiterminal statistical inference,” IEEE Trans. Inform. Theory , vol. 57, no. 9, pp. 5577–5587, September 2011. July 31, 2026 DRAFT 24

    2011

  2. [2]

    Multiterminal statistical inference: An unsolved problem,

    ——, “Multiterminal statistical inference: An unsolved problem,” in Mathematics Going F orward: Collected Mathematical Brushs trokes, ser. Lecture Notes in Mathematics, vol. 2313. Springer, 202 3, pp. 361–366

  3. [3]

    Science Publishing Company, 2024

    ——, The Fascinating W orld of Mathematics: Information Geometr y, Artificial Intelligence, and Neural Network Theory (in Ja panese). Science Publishing Company, 2024

    2024

  4. [4]

    A conjecture regarding optimality of the dicta tor function under Hellinger distance,

    V . Anantharam, A. Bogdanov, A. Chakrabarti, T. Jayaram, and C. Nair, “A conjecture regarding optimality of the dicta tor function under Hellinger distance,” in Information Theory and Applications W orkshop , July 2017

    2017

  5. [5]

    On hype rcontractivity and mutual information between Boolean fun ctions,

    V . Anantharam, A. Gohari, S. Kamath, and C. Nair, “On hype rcontractivity and mutual information between Boolean fun ctions,” in Proc. Allerton Conference on Communication, Control and Computi ng, 2013, pp. 13–19

    2013

  6. [6]

    On maximal correlation, hypercontractivity, and t he data processing inequality studied by Erkip and Cover,

    ——, “On maximal correlation, hypercontractivity, and t he data processing inequality studied by Erkip and Cover,” a pr 2013. [Online]. Available: https://arxiv.org/abs/1304.6133

    Pith/arXiv arXiv 2013

  7. [7]

    The Courtade-Kumar most informative Boolean function conjecture and a symmetrized Li-M´ edard conjecture are equivalent,

    L. P . Barnes and A. ¨Ozg¨ ur, “The Courtade-Kumar most informative Boolean function conjecture and a symmetrized Li-M´ edard conjecture are equivalent,” in Proceedings of IEEE International Symposium on Informatio n Theory , June 2020, pp. 2223–2227

    2020

  8. [8]

    A differential equation approach to the most-informative Boolean function conject ure,

    Z. Chen, A. Gohari, and C. Nair, “A differential equation approach to the most-informative Boolean function conject ure,” in Proceedings of IEEE International Symposium on Information Theory , Ann Arbor, USA, July 2025, arXiv:2502.10019

    Pith/arXiv arXiv 2025

  9. [9]

    On the optimality of dictator functi ons and isoperimetric inequalities on Boolean hypercubes,

    Z. Chen and C. Nair, “On the optimality of dictator functi ons and isoperimetric inequalities on Boolean hypercubes, ” in Proceedings of IEEE International Symposium on Information Theory , Athens, Greece, July 2024

    2024

  10. [10]

    Which Boolean functions maximize mutual information on noisy inputs?

    T. A. Courtade and G. R. Kumar, “Which Boolean functions maximize mutual information on noisy inputs?” IEEE Trans. Inform. Theory , vol. 60, no. 8, pp. 4515–4525, August 2014

    2014

  11. [11]

    On the suboptimal ity of linear codes for binary distributed hypothesis testi ng,

    A. Girish, D. H. Cung, and E. Telatar, “On the suboptimal ity of linear codes for binary distributed hypothesis testi ng,” in IEEE International Symposium on Information Theory , 2026, arXiv:2601.10526

    Pith/arXiv arXiv 2026

  12. [12]

    Statistical inference under mul titerminal data compression,

    T. S. Han and S. Amari, “Statistical inference under mul titerminal data compression,” IEEE Trans. Inform. Theory , vol. 44, no. 6, pp. 2300–2324, October 1998

    1998

  13. [13]

    Progress on the Courta de-Kumar conjecture: Optimal high-noise entropy bounds an d gener- alized coordinate-wise mutual information,

    A. Javanmard and D. P . Woodruff, “Progress on the Courta de-Kumar conjecture: Optimal high-noise entropy bounds an d gener- alized coordinate-wise mutual information,” in Proceedings of IEEE International Symposium on Informatio n Theory , July 2026, arXiv:2601.09679

    arXiv 2026

  14. [14]

    Achievable lower bounds of F isher information in multiterminal statistical inference ,

    K. Kobayashi and S. Amari, “Achievable lower bounds of F isher information in multiterminal statistical inference ,” in Proceedings of 12th Shannon Theory W orkshop, Ishikawa, Japan, October 2023, pp. 1–25

    2023

  15. [15]

    Boolean functions: Noise stabili ty, non-interactive correlation distillation, and mutual information,

    J. Li and M. M´ edard, “Boolean functions: Noise stabili ty, non-interactive correlation distillation, and mutual information,” IEEE Trans. Inform. Theory , vol. 67, no. 2, pp. 778–789, February 2021

    2021

  16. [16]

    O’Donnell, Analysis of Boolean Functions

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

    2014

  17. [17]

    An impr oved upper bound for the most informative Boolean function c onjecture,

    O. Ordentlich, O. Shayevitz, and O. Weinstein, “An impr oved upper bound for the most informative Boolean function c onjecture,” in IEEE International Symposium on Information Theory , 2016, pp. 500–504

    2016

  18. [18]

    Clustering by mutual information,

    G. Pichler, “Clustering by mutual information,” Ph.D. dissertation, Vienna University of Technology, 2017

    2017

  19. [19]

    Dictator funct ions maximize mutual informations,

    G. Pichler, P . Piantanida, and G. Matz, “Dictator funct ions maximize mutual informations,” The Annals of Applied Probability , vol. 28, no. 5, pp. 3094–3101, 2018

    2018

  20. [20]

    On the entropy of a noisy function,

    A. Samorodnitsky, “On the entropy of a noisy function,” IEEE Trans. Inform. Theory , vol. 62, no. 10, pp. 5446–5464, October 2016

    2016

  21. [21]

    On sequences of pairs of dependent random variables,

    H. S. Witsenhausen, “On sequences of pairs of dependent random variables,” SIAM Journal of Applied Mathematics , vol. 28, no. 1, pp. 100–113, January 1975

    1975

  22. [22]

    On the Φ-stability and related conjectures,

    L. Y u, “On the Φ-stability and related conjectures,” Probability Theory and Related Fields , vol. 186, pp. 1045–1080, May 2023

    2023

  23. [23]

    Y u and V

    L. Y u and V . Y . F. Tan, Common Information, Noise Stability, and Their Extensions . NOW Publishers: Foundation and Trends in Communication and Information Theory, 2022, vol. 19, no. 2. July 31, 2026 DRAFT

    2022