A floor one pass cannot get under

This collection has five lower-bound arguments and this is the sixth. Three of them are now of the same kind — a counting argument on memory states — and it is worth saying what makes each different, because the family looks uniform from a distance and the constructions are not.

The floor under exact distinct counting separates two prefixes by appending a single item. The floor under a window separates them the same way and is tidier, because a window is the state. This one needs a suffix built for each pair, and the reason is that selection’s answer does not move when one item is appended.

The construction #

Fix a universe $[0, u)$ and let the prefix be some $h$-subset $A$ of it. Follow it with a suffix of $h - 1$ sentinels — $(h - c)$ of them below every element of the universe and $(c - 1)$ above every element — so the stream has length $2h - 1$ and its median is exactly the $c$-th smallest element of $A$.

That is the whole device: the sentinels are a rank shift, chosen so that the fixed question “what is the median” reads out the order statistic of interest.

Now take two distinct subsets $A \ne B$ and let $d$ be the smallest element on which they differ, say $d \in A \setminus B$. Let $c = |A \cap [0, d]|$. Then:

• the $c$-th smallest of $A$ is $d$, because $A$ has exactly $c$ elements at or below $d$ and $d$ is the largest of them;
• the $c$-th smallest of $B$ is strictly larger, because $A$ and $B$ agree below $d$ and $B$ is one short there.

Choose the suffix for that $c$ and the two streams have different medians while sharing everything after the prefix. An algorithm in the same memory state after both prefixes reads the same suffix, performs the same computation, and emits the same number — so it is wrong on one of them.

Every $h$-subset therefore needs its own state, and the state needs at least $\log_2 \binom{u}{h}$ bits.

Performed, not quoted #

$\binom{12}{6} = 924$, so $\log_2 924 = 9.85$ bits, so nine bits cannot be enough. That is small enough to check by exhaustion rather than by argument, and this collection’s standing preference is to check.

The witness on that plate is worth reading in full because it is the whole argument made concrete.

• $A = \{0, 1, 2, 3, 4, 7\}$ and $B = \{0, 1, 2, 4, 8, 11\}$.
• They first differ at 3, which is in $A$ and not in $B$.
• $A$ has four elements at or below 3, so $c = 4$.
• The suffix is $\{-1, -2\}$ below everything and $\{12, 13, 14\}$ above it: two low sentinels and three high ones, eleven items in all.
• The median of $A$ plus the suffix is 3. The median of $B$ plus the suffix is 4.
• The candidate is in the same state after both prefixes and reads the same suffix. It answers one number.

There is nothing left to argue about. It is a complete refutation of a specific candidate rather than an existence claim about all of them, and it is what “performed rather than quoted” means here.

And it is tight #

A bound that says nine bits are not enough is not, on its own, evidence that ten are. So the same exhaustion is run the other way.

Ten bits, which is $\lceil 9.85 \rceil$, distinguish all 924 prefixes. So the counting argument is not merely a bound; it is the answer.

The third row is the interesting one and it is why the bitmap is on the plate. An encoding a stream can actually maintain costs an extra bit here. The colex rank is the information-theoretic optimum and updating it as items arrive is not a one-line operation; a bitmap is trivial to maintain and needs eleven bits for the same job, because it wastes the states corresponding to subsets of the wrong size.

That gap is small and it is real, and it is the same distinction this collection draws elsewhere between what a bound permits and what a structure can be built to reach.

One size proves one size, and the argument is about a family. The same exhaustion runs at any universe small enough to enumerate, so it is run twice more — once smaller and once larger — and the point of doing so is that the floor is $\lceil \log_2 \binom{u}{h} \rceil$ at every one of them, computed rather than fitted.

What the bound says, at scale #

For a stream of $n$ values drawn without repetition from a universe of $u$, the same argument with $h = n/2$ gives

$$\log_2 \binom{u}{n/2} \;=\; \Omega(n)$$

whenever $u$ is a constant factor above $n$ — which is $\Theta(n)$ bits, and for thirty-two thousand thirty-two-bit values is on the order of a million.

That is not “keep the stream” as an upper bound; it is “keep something the size of the stream” as a lower one, and the two are close enough that the one-pass problem is settled. An exact one-pass selector is not a summary and cannot be made into one.

Why appending one item is not enough #

The difference between this construction and its two siblings is one sentence and it is the interesting part of the essay, so it is worth doing slowly.

For distinct counting, take two half-sized subsets $S \ne T$ reaching the same state, pick $x \in S \setminus T$, and append it. The true counts are then $|S|$ and $|T| + 1$, which differ by one. One item, no computation, done.

For a window, take two distinct windows of length $W$ differing first at position $d$ and feed $W - d$ zeros. The windows then agree everywhere except at $d$, so their counts differ by exactly one. A little more work, still a suffix that depends only on $d$.

For selection, appending one item does almost nothing. The median of a set and the median of that set plus one element are usually equal or adjacent, and — crucially — they are equal or adjacent for both $S$ and $T$. The answer is a value in the middle of the data and it is insensitive to what happens at the edges, which is exactly the property that makes a median useful and exactly what blocks the easy separation.

So the suffix has to do something else: it has to move the question. The sentinels do not add information about the prefix; they shift which order statistic the fixed query reads out, and they shift it to the one position where $A$ and $B$ are known to differ. The construction is therefore a small reduction — from “distinguish these two prefixes” to “ask the median about rank $c$” — rather than a direct appeal.

That reduction is what costs $h - 1$ extra items, and it is the reason this floor is stated for a stream of length $2h - 1$ over a universe of $u$ rather than for a stream of length $h$. The bound is $\log_2\binom{u}{h}$ bits for a stream of $2h-1$ items, which is still $\Theta(n)$ and is a constant factor weaker than the arithmetic would suggest if the sentinels were free.

And a second pass walks under it #

Which is the reason this floor is in the same group as the two multi-pass essays rather than beside the others.

A factor of ninety at two passes and three thousand at nine, against a bound that is not loose — the tightness check above says the one-pass number cannot be improved by more than an encoding’s worth.

The reason the argument does not survive is exactly where it uses the model. The pigeonhole is over the states an algorithm can be in after reading a prefix, and it depends on the algorithm never seeing that prefix again. A two-pass algorithm reads it twice; the state after the first pass no longer has to determine the answer, only to determine what the second pass should look for; and the second pass supplies everything the state threw away.

A lower bound is a statement about a model, and this one names its model in a single clause. That is the same lesson as the essay on turnstiles, arriving in a place where the clause is a number rather than a property of the data.

What is quoted rather than performed #

The $p$-pass version of the bound is not demonstrated here and it is worth being exact about which part is missing.

Munro and Paterson proved in 1980 that $p$-pass selection in a comparison-based model requires $\Omega(n^{1/p})$ storage. The measurements in the previous essay sit on that shape — the fitted exponent is 13.5 against a predicted 15, over a range of thirty-six times — and sitting on a shape is not a demonstration of a bound. It is a prediction being met.

The argument itself is an adversary argument over comparison outcomes, and the smallest instance that would demonstrate anything is far past what an exhaustive search can walk: the one-pass case above needs $\binom{12}{6} = 924$ subsets and the two-pass case would need to quantify over every possible pair of state maps as well.

So this collection has, on this question:

• the one-pass floor, performed — the pigeonhole run to exhaustion, the collision produced with its witness, and the tightness checked from both sides;
• the multi-pass floor, quoted — stated with its author, marked as quoted, and not drawn under any measured curve;
• and the gap between them, measured — the factor of ninety above.

That is the same division the conditional floor makes between a link performed and a link quoted, and it is made for the same reason: a plate that put a quoted bound under a measured curve would be presenting a citation as a demonstration.

The suffix has to depend on the pair #

There is a quiet quantifier in the construction and it carries most of the bound’s strength, so it is worth pulling out and pricing.

The suffix is built after the pair is chosen: $c$ is computed from the first element on which $A$ and $B$ differ, and a different pair generally needs a different $c$. Nothing in the argument produces one stream that is hard. It produces a family, and for each colliding pair somewhere in the family there is a suffix that separates that pair.

Ask what the same pigeonhole proves if the suffix is fixed in advance — one $c$, one set of sentinels, chosen before the algorithm is. Two prefixes then need different states only when they give different answers to that one question, and the number of distinct answers is at most the size of the universe. The floor collapses to $\lceil \log_2 u \rceil$:

Six of the ten bits in the demonstrated floor are bought by letting the suffix vary, and the share grows with the universe — the left column climbs like $\log_2\binom{u}{h}$ and the right one is stuck at $\log_2 u$, because a fixed question has only as many answers as there are values to give.

So the adversary here is adaptive in a specific and limited sense. It does not watch the algorithm run and it does not choose values in response to comparisons, which is what an adversary does in the argument that hides an edge. It reads the algorithm’s state map once, finds two prefixes that land in the same state, and only then writes the ending. That is weaker than a running adversary and enough for this bound, and it is worth naming because a reader who has met the edge-hiding argument will otherwise import the stronger machinery and wonder where it is used.

It also settles a question the plates invite. There is no single stream on which every nine-bit selector fails — each of the 924 prefixes is an ordinary six-element walk and any one of them can be handled in nine bits by a candidate built for it. The hardness is a property of the set, which is why the plate names a pair and a suffix rather than an input.

A floor the trivial algorithm already meets #

Most floors on this site leave room. The comparison-sorting floor is a target that real sorts approach and do not reach, and the size of the remaining gap is interesting enough to have its own essay. The distance is where engineering lives: a better merge policy, a better pivot, a better cutoff, each recovering a little of it.

This floor has no such room, and the tightness check above is what says so.

The dumbest correct thing — remember which values have arrived — is two bits above a bound that no cleverness can improve. A floor that the naive algorithm already matches is not an invitation to optimise; it is a statement that the problem as posed is finished, and reading it as the first kind is how effort gets spent on a constant that is not there.

What follows from that is the shape of the rest of the field. When a bound is tight against the trivial algorithm the only moves left are to change what is being asked, and there are exactly three of them here, each measured elsewhere on the site:

• spend a pass — the table below drops the state by a factor of ninety for one extra read of the input, and what a second pass buys is the measurement;
• give up exactness — an approximate median needs state governed by $\varepsilon$ and not by $n$ at all, which is a floor of an entirely different kind and is why the two cannot be compared directly;
• change the model — the pigeonhole assumes the algorithm is deterministic and the arrivals are unrepeated, and a bound is a statement about the model it was quoted in.

The three exits are not equally cheap and the site’s numbers say which is cheapest: a second pass is a factor of ninety and costs one more read, while a tolerance buys unbounded savings and costs an answer that can be wrong. Nothing on the list is a better one-pass exact selector, because the row above says there is not one.

The six floors, and what kind each is #

Worth collecting, because this is the sixth and the family has become various enough that “there is a floor” no longer says what sort of thing is meant.

Three of the six are the same argument with a different separating construction, and the constructions are where the work is. Appending one item separates two distinct-count prefixes and two window prefixes; separating two selection prefixes needs a suffix computed from the pair.

The floor is on the state and not on the work #

One more thing the bound does not say, and it is the sort of omission that gets read as a claim.

Nothing above constrains how much computation a one-pass selector does. The pigeonhole counts the states an algorithm can be in between items and says there must be many of them; it is indifferent to what happens inside a step, and an algorithm allowed unbounded time per arrival is bound by exactly the same number. So the floor is a memory statement in the strict sense, and the two resources this collection usually reports together come apart here.

That is not a technicality on a stream. The selector that meets the floor by holding a colex rank has to update that rank as each item arrives, which is a genuine computation over the whole encoded subset; the bitmap two bits above it updates in one instruction. The encoding that reaches the bound is the expensive one to maintain, and the two extra bits buy a per-item cost that does not grow with what has been seen. That trade — a little more state for far less work per arrival — is the same one the sampling that goes the other way makes in an index, and it is invisible to any bound that counts only bits.

What is not measured here #

Repetitions. The construction uses subsets, so every value in the prefix is distinct. A stream with repeated values has fewer distinguishable prefixes and a correspondingly lower floor, and none of the arithmetic here covers it.

Approximate selection. Everything above is about exactness. An approximate median is available in one pass and very little state, and there is a separate floor under that — it is a statement about $\varepsilon$ rather than about $n$, and this collection has several of those.

Randomised algorithms. The pigeonhole applies to deterministic algorithms. A randomised one has a distribution over states and the argument needs the usual repair, which is not made here — so the bound as demonstrated is a deterministic one, and every algorithm measured against it is deterministic too.