Compressing a short list of very large numbers?

Question

Suppose that we are dealing with integers drawn from a random uniform distribution, on the range $[1 , 2^{30}]$. Is it possible to effectively compress a short list of random numbers, say $2^4$ numbers in the list. Comment - The list can be assumed to be sorted, ascending. With a very long list delta encoding can be effective, but here the list is short and the deltas are expected to be huge. There is very little opportunity to exploit delta encoding of small numbers, with gap values expected to be of the order of $2^{26}$.

Answer 1

The complexity of a list of $n$ numbers drawn uniformly from $[1,N]$ is $n \log_2 N$ bits, since you have to distinguish between $N^n$ equally likely possibilities. If the numbers have been sorted into ascending order, you can save $\log_2 (n!) \approx n \log_2 n$ bits. In your case, supposing $N=2^{30}$ and $n\approx 2^{4}$, the naive length is $2^4\cdot 30 = 480$ bits, and you can save $2^4 \cdot 4=64$ bits, or about $13\%$, by sorting before compression.