Let $H_0$ be $\log_2(|A|)$, where $A$ is a set.

Let $C$ be a compressor $C\colon A \to \{1,0\}^l \cup \bot$.

This is a silly question, because intuitively it seems obvious.

How can I prove that $l$ can't be less than $H_0$?

I can prove that $l = H_0$ is sufficient, but how can I prove that it can't be less.

  • $\begingroup$ Unless you put some conditions on $C$, you can even choose $l = 0$. $\endgroup$ Commented Apr 9, 2021 at 11:38

1 Answer 1


The function wouldn't be one-to-one otherwise.

The size of the set in the left is $|A|$, and its image would be of size at most $2^l<2^{H_0}=|A|$, therefore, the function wouldn't be injective and thus you wont be able to de-compress some of the data.

Therefore it will be a lossy-compression for any $l<H_0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.