{"id":"2b4e4d9a-7642-4d77-977e-0ad76a9da77b","arxiv_id":"2607.28162","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Level-k Boolean functions maximize KL divergence and Fisher information for unbiased pairs and identical pairs under nonnegative correlation, and minimize Bayes error in one-bit distributed hypothesis testing.","lead":"Pairs of Boolean functions that best tell two correlation strengths apart are level-k functions (including parities) in the unbiased and identical-function cases. The result partly settles Amari–Kobayashi’s Fisher-information conjecture and fully settles the Bayesian one-bit testing version.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the genuine scope limitation (nonnegative τ needed for the biased identical reduction) while recognizing that every theorem the paper asserts is proved under precisely the hypotheses it states. Re-examination of the Fourier expansions (16)–(19), the two proofs of Thm 1 (Lemma 1 and the joint-convexity argument of Remark 1), the Markov/data-processing argument of Thm 3, the direct Fisher bounds (53)–(58) and (61)–(65), and the MCD/Cauchy–Schwarz argument of Thm 6 reveals no algebraic error or unjustified step. The one-function counter-examples and the unboundedness of the naïve relaxation are reported honestly. Consequently the ACCEPT / high-confidence verdict stands; the concrete numerical check above is only a prudent sanity test, not a repair.","tokens_in":22284,"tokens_out":497,"duration_ms":39900,"concrete_test":"Numerically verify Lemma 2 on a dense grid: for η∈(0,1/2], τ0,τ1∈[0,1), confirm D(P_{UV,η,τ0}||P_{UV,η,τ1})≤D(P_{UV,1/2,τ0}||P_{UV,1/2,τ1}) to machine precision; simultaneously exhaust all unbiased Boolean pairs on n≤4 and check that none exceed max_k d((1+ρ0^k)/2||(1+ρ1^k)/2) for a sample of (ρ0,ρ1) pairs.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proved claims (Thms 1, 3, 4, 6 fully; Thms 2 and 5 under the stated nonnegative-correlation restriction) rest on standard Fourier identities, Cauchy–Schwarz/Parseval, joint convexity of KL, and elementary second-derivative comparisons (Lemmas 1–4). The arguments are elementary, non-circular, and scoped exactly to the hypotheses under which they hold. The paper explicitly flags the open biased-unequal and negative-τ regimes (Remark 2, §III-D) and the fact that level-k properly contains parities. No hidden assumption, algebraic gap, or overclaim was found that would undermine the central theorems as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":22414,"tokens_out":1148,"duration_ms":35407,"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":[{"comment":"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.","section":"Abstract; §I; after (19); Theorems 1–2, 4–5"},{"comment":"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.","section":"Theorem 2; Lemma 2; Remark 2; Theorem 5; §III-D"}],"minor_comments":[{"comment":"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.","section":"Fig. 2"},{"comment":"In the alternative proof of Theorem 1 (Remark 1), “Cauchu–Schwarz” should be “Cauchy–Schwarz”.","section":"Remark 1"},{"comment":"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.","section":"§IV-B, Eq. (60)"},{"comment":"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.","section":"§VI"},{"comment":"Reference [11] is listed as “in IEEE ISIT 2026, arXiv:2601.10526”; confirm final venue/year consistency before camera-ready.","section":"References"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is technically solid and appropriately scoped; the reader’s accept verdict is reasonable. I recommend minor revision mainly to tighten the statement of what is proved versus the original parity conjecture and to surface the negative-correlation gap more prominently. Fit for a strong information-theory journal is good. No integrity or citation-pattern concerns."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The real news is that Chen–Watanabe–Yu give checkable upper bounds showing level-k Boolean functions maximize KL divergence and Fisher information for unbiased pairs (any ρ) and for identical pairs under nonnegative correlation, plus a complete Bayes-error optimality result for one-bit distributed HT among all pairs. That is a genuine advance on the Amari–Kobayashi parity conjecture and a clean extension of the Pichler–Piantanida–Matz dictator theorem beyond mutual information.\n\nWhat they do well is elementary and transparent. Lemma 1 (two-weight convexity for binary divergence) and the bias-reduction Lemma 2 let them reduce to averages over Fourier levels; Cauchy–Schwarz/Parseval plus joint convexity finish the job. The local-optimality argument via data processing (Thm 3) is short and sharp. The Bayesian HT section is especially clean: optimal decoder is just the sign of uv, and the correct-probability bound collapses to max |ρ0^k − ρ1^k|. They introduce MCD as a natural singular-value generalization of maximal correlation and show it is tight for the binary case. Equality cases and the fact that level-k properly contains pure parities are stated without hype. The one-function discussion honestly reports majority counter-examples outside certain regimes.\n\nSoft spots are real but scoped. The biased identical-function proofs need ρ ≥ 0 because the (η,τ) comparison fails for negative τ (Remark 2); biased unequal pairs stay open and their relaxed program in §III-D can become unbounded. That is not a hidden gap—they flag it. No circularity, no free parameters, citations are the right background.\n\nThis is for people who already care about Fourier methods in IT, noise stability, or multiterminal inference. Worth a reading-group slot if that is your circle. I would cite the unbiased/Fisher/Bayes theorems. Send it to referees; the proved claims are solid and the open cases are clearly marked.","headline":"Solid partial resolution of Amari–Kobayashi via level-k optimality, with clean proofs and an honest scope on what remains open.","tokens_in":23054,"tokens_out":485,"would_cite":true,"duration_ms":9259,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A17","94A15","68Q87","62B10"],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["Boolean functions","Kullback-Leibler divergence","Fisher information","Fourier analysis","level-k functions","distributed hypothesis testing","noise stability","maximal correlation difference"],"falsifier":"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).","tokens_in":23150,"feed_emoji":"🔢","tokens_out":897,"duration_ms":21446,"temperature":0.7,"pith_summary":"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.","feed_headline":"Level-k bits best tell two correlations apart","feed_subtitle":"Unbiased or identical one-bit compressions maximize divergence and Fisher information via degree-k Fourier support","key_machinery":"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).","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Level-k Boolean pairs maximize KL for correlated sources","Unbiased pairs: degree-k Fourier support tops divergence","Identical level-k functions maximize Fisher information","Level-k optimal for Bayesian one-bit hypothesis testing","Parity included: level-k resolves Amari-Kobayashi case"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Level-k Boolean pairs maximize KL for correlated sources","Unbiased pairs: degree-k Fourier support tops divergence","Identical level-k functions maximize Fisher information","Level-k optimal for Bayesian one-bit hypothesis testing","Parity included: level-k resolves Amari-Kobayashi case"]},"model":"grok-4.5","effort":"low","cost_usd":0.003702,"raw_usage":{"total_tokens":1168,"prompt_tokens":772,"num_sources_used":0,"completion_tokens":81,"cost_in_usd_ticks":37024000,"prompt_tokens_details":{"text_tokens":772,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":315,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":772,"tokens_out":81,"duration_ms":5188,"temperature":1.0,"reasoning_tokens":315,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T15:56:19.066344+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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).","supporting_citations":[],"review_version":1}