Entropy of Bernoulli Measures Conditioned on Affine Subspaces and a Problem of Ancheta--Massey
Yihong Wu
cs.IT
2026-08-24
Yihong Wu proves a nonasymptotic converse: linear lossy compression of Bernoulli sources is no better than time-sharing. GPT-5.6 Sol found the first proof.
For lossless compression of a Bernoulli source, linear encoders already meet Shannon entropy h(p): n biased coin flips can be recovered from about n h(p) linear checks. Lossy compression is different. If a fraction D of bits may be wrong, the rate-distortion function is R(D)=h(p)−h(D), and a linear encoder cannot reach it.
Ancheta proved a distortion lower bound for linear encoders in 1978. At p=1/2 the bound is (1−R)/2, and keeping the first R n bits while guessing the rest meets it. For general p the matching naive scheme is time-sharing: compress an R/h(p) fraction of the bits linearly and losslessly, decode the rest as zero, and accept distortion D=p(1−R/h(p)). Massey asked in 1978, and again in 2009, whether any linear encoder can beat that scheme. Ancheta settled p=1/2. The case p<1/2 stayed open.
A linear compressor is a full-row-rank matrix H mapping n bits to k bits. The Hamming-optimal decoder is bitwise MAP on the posterior: given HX=s, each bit takes the more likely of 0 and 1. The resulting bit-error rate D(H) is the average, over coordinates, of the smaller posterior mass.
The key lemma bounds the entropy of that posterior by those marginals. Conditioning on HX=s is conditioning a Bernoulli measure on an affine subspace (a coset) A. Write PA for the conditional law and e(A) for its Hamming radius under bitwise MAP. The lemma says H(PA) ≤ (h(p)/p) e(A). Averaging over s and using H(S)=H(X)−H(X|S)≤k yields a nonasymptotic converse: k/n ≥ h(p)(1−D(H)/p). That is exactly the time-sharing curve, so time-sharing is optimal among linear encoders.
The proof reduces an arbitrary coset to the zero coset. A Fourier argument shows that the syndrome puts the most mass at 0. An induction then bounds the Bernoulli mass of a linear subspace by its radius. The same bound can be read from the Griffiths-Kelly-Sherman correlation inequality: the posterior on the zero coset is a ferromagnetic Ising model, so the probability of the all-zero string is at least the product of the one-bit marginals.
The theorem holds for every full-rank H. It does not need large n, random matrices, or a named code family. Time-sharing meets the bound, so Massey's question has a yes: the best a linear encoder can do for this lossy problem is to compress some bits losslessly and estimate the rest as zero.
The dual statement is for the binary symmetric channel with crossover p, whose capacity is CBSC=1−h(p). For a linear code of rate R between capacity and 1, bitwise MAP satisfies Pb ≥ (p/h(p))(R−CBSC). Above capacity, bit error for linear codes grows at least linearly in the excess rate, with slope p/h(p).
There is no simulation. Tightness is the matching of a known scheme to a new converse. Figure 1 plots Shannon's R(D), Ancheta's converse, and the now-tight linear time-sharing curve at p=1/2 and p=0.11. The three curves stay apart.
For coding theory this is a clean negative: force the encoder to be linear and lossy Bernoulli compression cannot meet Shannon's curve, and the optimum is the obvious scheme. For people who train models, the provenance is the sharper point. GPT-5.6 Sol found the first version of the proof in an interactive session the author steered. The author then simplified it into the self-contained argument here and takes full responsibility for the mathematics. A later literature search with Codex showed that several lemmas already sat in coding theory and spin-glass papers, including Sullivan's 1967 mode-at-zero fact, Cammarota and Russo 1991 on Bernoulli measures of cosets, and the GKS inequality.
The honest reading is a model, guided by a specialist, writing a proof whose parts can later be traced in the literature. That is short of a machine closing a cold conjecture on its own. It is still a compact, checkable write-up of a question that had been open since 1978, and a useful sample of what theorem-proving models currently do.
This is a short theoretical note: no experiments, no finite-blocklength plots, no comparison with nonlinear or approximately linear encoders. Distortion is Hamming, the alphabet is binary, and the encoder must be linear over F2. The p=1/2 case is not new. The author states that several supporting facts follow from prior work; GPT-5.6's contribution is assembling them into the entropy inequality and finishing the theorem, not inventing the whole toolkit from scratch. The interactive trace, prompts, and failed attempts are not released, so the "discovery" step cannot be reproduced from outside. The channel dual covers linear codes under bitwise MAP only, not maximum-likelihood codeword decoding or finite-length bounds.