Information-theoretic bound — where it appears
Named by 6 essays across one field — each of them below, with the objects they name alongside it.
A floor on the bits
Answering membership for n keys with a false-positive rate of 1% and no false negatives requires at least 6.64 bits per key, whatever the structure. A Bloom filter uses 9.59. The gap is 44.27% at that rate and at every other rate, and it is the first bound on this site that a real structure comes close to.
The floor under moving data
The information-theoretic floor for comparison sorting is log₂(n!) and it says nothing about a file on a disk. In the external model the floor is (n/B)·log_{M/B}(n/B), it is a bound on every algorithm rather than on merge sorts, and a measured external sort sits 2.40 to 2.97 times above it. Both numbers are computable, and the gap between them is what a real implementation costs.
What a reordering costs to undo
Sorting the characters of a text clusters them perfectly: a move-to-front pass then leaves 289 bits where the text's own floor is 31,931. Naming which arrangement of those characters the text was costs 31,827 bits, and the two numbers add to the floor it started from. The Burrows–Wheeler transform clusters less and costs nothing to undo, which is the only reason it is the one that is used.
The bits a coder emits
A stream of 16,384 symbols with a zeroth-order entropy of 3.891 bits per symbol was coded by a Huffman coder into 3.937 and by an arithmetic coder into 3.898, and neither went under 3.891 because neither can. That floor is a third kind of limit, the first that is a property of a model rather than of a question, and the same stream has a different one under every model of it.
The floor under a summary
An exact one-pass distinct-counter over a universe of u keys needs at least log2 of u-choose-u-over-2 bits of state — the same counting argument as the sorting floor, applied to memory states instead of outcomes. At u = 12 that is 9.85 bits, and an eight-bit candidate is shown to collide by running all 924 subsets.
The floor under a window
An exact count of the ones in the last W arrivals needs W bits, and the argument is a pigeonhole that can be performed rather than quoted — 1,024 windows, an eight-bit state, the colliding pair produced, and the two answers it cannot tell apart.
Named alongside it
The objects these essays reach for when they reach for this one.
Counting argumentLower boundSpace lower boundBits per symbolEntropyGuaranteePigeonholeState bitsStreaming algorithmAdversarial inputApproximate membershipArithmetic coding