The Multibit Most Informative Function Problem at High Noise

Let X be uniform on {0, 1} n and let Y be the output of a binary symmetric channel with crossover probability p. Mahdavifar and Beirami conjectured that for 2 ≤ k ≤ 7 no function f : {0, 1} n → {0, 1} k has I(f(X); Y ) > k(1 − h(p)), the value of k coordinates, and showed that this fails for k ≥ 8. We prove the case k = 2 for all p close to 1 2 , uniformly in n, in a stable form: there are absolute constants ρ0, c > 0 such that every f : {0, 1} n → {0, 1} 2 satisfies I(f(X); Y ) ≤ 2(1 − h(p)) − c(1 − 2p) 2 dist(f) whenever 1 − 2p ≤ ρ0, where dist(f) is the fraction of inputs on which f differs from the nearest depth-two decision tree. So for p < 1 2 only these trees are optimal, and every departure from them costs information. At leading order the conjecture becomes the inequality B(f) ≤ k for the between-cell variance of the partition induced by f. For coset quantizers, whose cells are the translates of a transversal of a linear code, the supremum of B is a constant βk attained by soft-decision decoding of the simplex code, so the coset case for all k ≤ 7 is the single inequality β7 ≤ 7. We prove β3 = 3 and the case k = 3 for all coset quantizers near p = 1 2 , uniformly in n, in the same stable form with coordinate projections in place of trees. This follows from a transfer principle: if equal weights on a basis are the only maximizers of the k-bit simplex decoding functional, then all coset k-bit quantizers satisfy the conjecture near p = 1 2 , uniformly in n and with stability. The case k = 7 of this rigidity statement implies all cases k ≤ 7. Simplex quantizers also attain the optimal constant 2 ln 2 of B/k as k → ∞.