ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.