VibeMathedMath problems solved with AI
Sign in

Entropy of Bernoulli Measures Conditioned on Affine Subspaces and a Problem of Ancheta-Massey

A textbook result in information theory is that linear encoders achieve the entropy for lossless compression of Bernoulli source with parameter pp. For lossy compression, however, linearity is known to incur strict suboptimality compared to the rate-distortion function. Massey asked whether the optimal rate for linear encoding is achieved simply by compressing a fraction of the bits linearly and losslessly and estimating the rest by zero. For p=12p=\frac{1}{2}, Ancheta answered this question affirmatively. This note extends Ancheta's result to all p<12p<\frac{1}{2}. The key argument is to bound the entropy of the posterior distribution conditioned on an affine subspace in terms of its marginals. The proof was discovered by GPT-5.6 Sol in an interactive process guided by the author.

Result
Proved(see note)
Status
Resolved
AI contribution
AI-discovered
Method
Argument
Field
Coding theory
Posed by
James L. Massey
Year posed
1978
Years open
48y
Solved
2026-08-24
Model
GPT-5.6 Sol
Vendor
OpenAI
Collaborators
Yihong Wu
Verification
Unreviewed
Publication
Preprint
Significance
15 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

For a Bernoulli(p)(p) source with 0<p<120<p<\frac12, the paper proves that the best lossy compression achievable by a linear encoder is exactly the simple time-sharing strategy that losslessly compresses a fraction of the bits and estimates the rest as zero. Equivalently, every full-row-rank H∈F2k×nH\in\mathbb F_2^{k\times n} satisfieskn≥h(p)(1−D(H)p).\frac{k}{n}\ge h(p)\left(1-\frac{D(H)}p\right).This resolves Massey's question affirmatively for all p<12p<\frac12; Ancheta had already proved the p=12p=\frac12 case.

What the AI did

GPT-5.6 Sol discovered the first version of the proof in an interactive process guided by Yihong Wu. Wu subsequently simplified the argument and developed the self-contained proof in the paper. A later literature search aided by Codex identified that several proof ingredients had appeared previously or could be deduced from earlier work. The author wrote the final paper and assumes responsibility for its technical content.

Verification

Unreviewed. A short preprint with a self-contained argument, by a researcher who works on exactly this. The author reports that a later literature search found several ingredients had appeared before or followed from earlier work, and says so in the paper; that is a caution about novelty of the components, not about the result. No independent check.

Source

Submitted by VibeGene on

Changelog2 changes

Discussion